JPH03501787A - データ並列処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 データ平行処理装置 且亙立互 本発明は、高速のデータ平行処理システム、特に、単一データピットで動作すべ く、相互に結合された同等の平行セル・アレイから成る、主制御装置の制御の下 に動作するデータ平行処理システムに関する。更に特徴的には、本発明は、セル のアーキテクチャ、及び独特の結合パターンに関わる。

且１１亘 或種のデータ処理タスクでは、実質的に同等の、論理演算又は算術演算を多量の データについて行う必要がある。この種タスクを実施する１つの方法として大い に注目されているのは、データ平行処理である。平行処理では、セルで構成され るアレイ・プロセッサの各エレメント又はセルが自身のデータビットの処理を行 うと同時に、アレイ・プロセッサの他の総てのセルが自身のデータビットについ て同一の処理を行う、これらの機械装置は、単一命令多重データ処理機（Ｓｉｎ ｇｌｅ　Ｉｎｓｔｒｕｃｔｉｏｎ−Ｍｕｌｔｉｐｌ＠Ｄａｔａ　ｍａｃｈｉｎｅ ｓ　（ＳＩＭＤ）　）という呼称を含めて、幾つかの呼称で呼ばれている。

これらの機械装置に関する一般的な配列は、各内部セルが至近の４つ６５隣接セ ルに結合され、各周縁のセルがデータ入出力装置に結合される、セルの直角アレ イのような配列である。各セルは、また、処理エレメントに速切な命令を与える ことによって当該アレイを通じてのデータの移動を調和させる、主制御装置にも 結合される。これらのアレイは、例えば高解儂度イメージ処理において有用であ ることが確認されている。これらのイメージ画素は、プロセッサのアレイによっ て、プロセッサにロードでき、迅速かつ効率的に処理できる、データマトリック スから成る。

総てが同一の機能で調和して動作するというセルのアレイについての同一属性概 念に総て基づいてはいるものの、データ平行処理装置はそれぞれセル設計の詳細 においては異なる。

例えば、ホルツィンスキその他（Ｈｏｌｓｔｚｉｎｓｋｉ　ｅｔ　ａｌ）による アメリカ合衆国特許第４，２１５，４０１号では、ランダム・アクセス・メモリ 　（ｒａｎｄｏｍ　ａｃｃｅｓｓ　ｍｅｍｏｒｙ：ＲＡＭ）、単一ビット累算器 、及び単−論理ゲートを含む、セルについて開示している。ここで開示されてい るセルは、極めて単純なので、安価であり容易に組み立てられる。しかし、この 単純さに伴う消極的な側面は、或計算アルゴリズムが非常に煩雑で、単純でしば しば反復するタスクを行うのにも多くの命令を要する場合があることである。

ホルツィンスキその池によるアメリカ合衆国特許第４゜７３９．４７４号では、 算術演算及び論理演算を共に行う能力を持つ全能の加算器で上記の論理ゲートを 置換した、更に複雑な機構が提示されている。この全能加算器に２重の仕事を強 いることによって、全能加算器を各セル中に含めることで付加された複雑さと費 用を償って余りある程に、効率を高めている。

論理ゲートを全能加算器で代替することによって、表面的には単純ではあるが、 現実には重大な変化が生じることに留意することが大切である。ここでは、セル 構造は余り複雑にはできない。これは、典型的なアレイでは、セルは、何百回で はないまでも、何十回も反復されるからである。付加された各エレメントに掛か る費用は、ＶＬＳＩチップに関する金額と容積の点で何倍にも増える。

したがって、上記の機能は十分育苗であるとはいうものの、これらの機能を見極 めて、セルへの組み込みを正当化することは単純な事柄ではない、また同様に、 組み込みの費用が極端に高くならないようにして、これらの機能を実施すること も単純な事柄ではない。

セルの相互結合の方法の点でも、平行処理装置はそれぞれ異なっている。上述し たように、典型的にはセルは物理的に隣接する至近のセルに結合している。全ア レイの周縁のセル以外のセルについては、総てのセルは４つの隣接セルに結合し ている。しかし、これによって、相互結合の代替的通路、特にプログラミング可 能な柔軟な結合関係がセル相互間に与えられることで著しい利益が生じる点につ いては、これまでは全く理解されていなかった。

」Ｌ肌Ｊと舅」１ 上述の状況から、セルの複雑さを最少に抑えてセルの効率を最大にする、セル・ アーキテクチャの種類を識別し、実行することへの必要性が続いている。本発明 では、区分化されたランダム・アクセス・メモリの各セル中で１クロック周期に ついて２回以上の読取り・書込みを可能にすべく用意することによって、この必 要性に対処している。更に、主処理エレメント中での処理に先立ってデータを条 件付きで処理するための回路を主処理エレメントの前に用意することによって、 この必要性に対処している。更に、主制御装置がセルを停止又は起動でき、ある いは、セルが停止又は起動していることについての標識をそれ自身で与えことが できる回路をセル中に用意することによって、この必要性に対処している。これ によって、個別のセルの各々が独立の条件付きの動作を行うことが可能となる。

本発明では、セル・アーキテクチャにおける変形を開発しただけではなく、セル の相互結合における変形をも開発した。改良例の１つでは、少なくとも１つのバ イパス・ネットワークを、必要又は要求に応じてセルをバイパスするためのアレ イに相互結合しである。セルをｎ×ｍアレイに配列しであるもう１つの実施例で は、少なくとも１つの縁のセルを、外部装置、又はアレイ中の池のセルの何れか に結合可能なように配列して、アレイの実質的なコンフィギユレーションを再成 形する能力を作り出している。

図面の簡単な説明 本発明の上述、及びその他の特徴は、本発明に関わる技術分野の技術に通じた者 にとって、以下の図面と関連して以下の詳細な叙述を読むことによって、明白と なろう。

第１図は、本発明によるプロセッサ・アレイの好ましい実施例のブロック線図で ある。

第２図は、本発明によるプロセッサ・アレイの第２の好ましい実施例の回路図で ある。

第３（ａ）図、第３（ｂ）図、及び第３（Ｃ）図は、本発明による好ましい実施 例の代替的なアレイ相互結合を示すブロック線図である。

第４図は、本発明によるセルの好ましい実施側の回路図である。

第５図は、本発明による区分化されたメモリの好ましい実施例の回路図である。

第６図は、本発明による条件付き論理ユニットの好ましい実施鈎の回路図である 。

第７図は、本発明によるプロセッサ・アレイの典型的な応用例のブロック線図で ある。

日　ｔ　た　の　−１，−ｙニー−ノ１足−Ｊは。

同等のセルのアレイとしての平行処理装置の配列に関する一般的な詳細について は、上述のホルツィンスキその他によるアメリカ合衆国特許第４，７３９．．４ ７４号から入手可能である。ここではその仕様を参照する。上記の特許、及び５ 第１因に示されるように、アレイ１０は、ｎｘｍ直角ネットワーク又はマトリッ クスを形成するために、Ｐｏ、。からｐ５．ｃここで、添え字″ｎ″及び”ｍ” は、任意の正の整数値を取り得る変数を表す）までの同等なプロセッサ、又は、 セルのｎ行とｍ桁から成る。

したがって、４つの近隣を持つセル（内部セル）と、３つ以下の近隣を持つセル （周辺セル）がある、均等な方向付けを行うために、図面中で上、下、右、左を それぞれ示すように北、南、東、西の方角を用い、至近の近隣セルをそれぞれＮ 、Ｓ、Ｅ、及びＷと呼ぶことにする。

図示するように、アレイ１０の周縁セルは、データ入出力装ｙ１２０に結合され ている。各セルは、命令信号Ｃ０からＣ，とアドレス信号Ａ、からＡ、とを制御 装置３０から受け取る。これに加えて、制御装＠３０によって各セルにクロック 信号を与えるようにもでき、データ入出力装置２０を制御装Ｎ３０によって制御 するようにもできる。これらの詳細については、上述のホルツィンスキその他に よるアメリカ合衆国特許第４，７３９，４７４号から入手可能である。

第１図はまた、セル・アレイに相互接続されるマルチプレクサ・ネットワークを も示す。第１のマルチプレクサ・ネットワークは、Ｍｌ、、からＭ　ｓ、　、ま で、及びＭ１１′からＭ１９．′まで（特記しない限り、ここ及び他の場所で、 ′ｎ″及び”ｍ″は、セルの標識に関して用いられる値とは必ずしも関係ない値 を取る〉のマルチプレクサで形成されている。下で展開するが、このネットワー クは、個々の行、桁又はブロックに関してセルを選択的にバイパスするために用 いられる。

第２のマルチプレクサ・ネットワークは、Ｍ、”からＭ、″まてのマルチプレク サで形成されていて、北側の周縁セルの相互結合を、データ入出力装置２０に、 又はアレイ中の他のアレイの何れかに選択的に転換するために用いられる。アレ イは、相互結合された煙・つかのチップで形成されており、その各々が主アレイ に対する自身のセクション又はサブアレイを供給する。この第２のマルチプレク サ・ネットワークは、プレイの実質的なコンフィギユレーションを変更する能力 を提供する。

事柄を明瞭にするためにここではその結合を省略しであるが、これらのマルチプ レクサ・ネットワークは総て、結合を通じて制御装置！３０に応答する。これら のマルチプレクサ・ネットワークで与えられる通信経路は両方向性であり、これ らのマルチプレクサはマルチプレクサ及びデマルチプレクサと見なされることを 銘記すべきである。また、マルチプレクサという術語は、ここでは、工ｌ／メン トの機能、すなわら、制御入力に基づく線路の選択に帰する機能を演じる総ての 装置を包括的に含めて用いられていることも銘記すべきである。したがって、単 純なスイッチでさえも、この機能を演じるように提供されている限り、マルチプ レクサであり得る。

第２図は、本発明によるアレイ１００更に詳細な表現であり、この場合Ｐ１１か らＰ、１．までの１２８個の同等のセルによる８×１６７レイである。事柄を明 瞭にするために、制御装置３０のような周辺機器及びこれとの結合関係は省略さ れているが、これらの結合関係があることは理解されるであろう。第２図の実施 例は、選択されたセル間に配列された群とのマルチプレクサ・バイパス・ネット ワークを有しており、これによって仲介セルをバイパスする。ここで分かるよう に、行、桁、又はブロックの全体をバイパスして、アレイの実質的な規模を事実 上個別の応用例に適合すべく変更するために、マルチプレクサが各セルとその近 隣セルとの間に存在する必要はない、ここに示す実施例では、８１１［のマルチ プレクサが１つの桁当たり１組と、１つの行当たり４＠のマルチプレクサが１つ の行当たり１組ある。かくして、−ａ的に、総ての行又は桁にあるセルの数に対 して半分の数のマルチプレクサしか必要としない、勿論、代替的な通信経路（以 下に述べるＣＭ経路のような）があれば、この経路にもマルチプレクサ・ネット ワークを与えることが望ましい。

セル・バイパスの助けが必要とされる時には、セル対セルの通信は、マルチプレ クサ選択線路の行と桁を連続的に駆動するラッチされたバイパス制御ワードに基 づく。

もし第１桁をバイパスすることを望むとすれば、例えば西側端の入出力ビンを論 理的に第２桁でセルの西側ポートに結合することになる。

行と桁のバイパスを独立に制御することができ、７×１２．４ｘ１０、ｌＸ１６ 、更にはＩＸＩ（７）ような実質的なアレイ規模を総て得ることができる。しか しながら、第２図の実施例は、アレイ１０を完全にバイパスすることができない ように設計されている。東側端の桁のセルは、セルの東側端の桁をデータが必ず 通過しなければならないように、常に東側入出力ビンに結合されている。

同様に、南側端の行のセルは、セルの南側端の行をデータが必ず通過しなければ ならないように常に南側入出力ビンに結合されている。したがって、ここには最 小１×１のコンフィギユレーションがある。

セル・バイパス・ネットワークの利点は、アレイ集計としても知られる平行デー タ集計のような作業で最も良く例証される。アレイ集計は、各セルで変化する同 一のデータ形式を全アレイにわたって集計することである。

プログラミングができるバイパスでは、この集計は以下のアルゴリズムを用いて 達成できる。

（１）　８　Ｘ　１６コンフイギユレーシヨンに対してセル・バイパス・ネット ワークをプログラムすること（２）変数を東側隣接セルにシフトすべく各セルに 命令すること （３）受は取った変数を保持している値に加算すべく各セルに命令することくこ れにより、桁２．４．６、及び８のセルが重複しない合計値の組を含むことにな る〉 （４）桁２．４．６、及び８に論理的に結合している４ｘ１６コンフイギユレー シヨンに対してセル・バイパス・ネットワークをプログラムすること（５）ステ ップ（２つ及び（３）を反復すること（これにより、４、及び８の桁の中のセル が重複しない合計値の組を含むことになる） （６）４の桁の中のセルを８の桁の中のセルに論理的に結合している２×１６コ ンフイギユレーシヨンに対してセル・バイパス・ネットワークをプログラムする こと （７）ステップ（５）を反復すること（これにより、桁８中のセルが西から東に かけてのアレイ全体に関する合計イ１を含むことになる） （８〕桁８中のセルを合計するように北から南にかけてアルゴリズムを反復して 、全アレイの合計値がアレイの南東側角のセル中に存在するまで各シフト後の行 コンフィギユレーションに加算させることセル・バイパス・ネットワークがない と、部分的なアレイ集計を行う際に、使用されていないセルを通じてデータを究 極の終点までシフトするために、付加的なりロック周期を大量に必要とする。セ ル・バイパス・ネットワークによって、アレイを再構成するために最低２周期の 最低のオーバーヘッド期間での直接的なセル間通信が可能になる。

その他のマルチプレクサ・ネットワークは、北端縁の８つのセル上の、双方向半 導体スイッチ又はマルチプレクサＭ０″からＭｔ−”までから成る。これらによ って、ｒ正常」化データ通路くデータ入出力装！！２０への〉か、若しくは、ｒ 代替的」化データ通路（同−又は異なるチップ上のもう１つのセルへの）かのど ちらかへの選択が可能になる。アレイ１０は、最早、北、南、東、西の結合性に 制約されない。例えば、各サブアレイの北周縁セルが第３（ａ）図に示すような 切り替え可能な北の代替的接続を与えられているとして、各６４（ｌＢのセルの ４×４サブアレイから成る３２Ｘ３２アレイを考えてみる。各サブアレイは、例 えば、別の半導体チップ上にあっても良い、北と北の代替的入力との適切な相互 接続によって、２つの１６Ｘ３２アレイ［第３（ｂ）図］、又は１０２４Ｘ１ア レイ［第３（Ｃ）図］に当該アレイを再構成することができる。このように、第 ２のマルチプレクサ・ネットワークは、複数チップ・アレイの接続を変更するこ とにおいて極めて有用である。

また、各セルのメモリ能力を論理的に拡張し、データ・オペランドを必要に応じ て繰入れたり繰り出したりするために、北の代替的コネクタをメモリ装置に接続 しても良い。北の代替的コネクタはまた、コーナ反転動作を可能にするために、 当該プレイ中の入出力装置又は他の処理用セルに接続できるポートをも提供する 。

本発明の好ましい実施例にはまた、個々のセルのアーキテクチャに関する１つ又 は２つ以上の改良を含めることもできる。第４図から分かるように、セルには、 １群のレジスタ、すなわち、北南（ＮＳ）レジスタ４０、東西（ＥＶ）レジスタ ５０、搬送（Ｃ）レジスタ６０、及び通信（ＣＭ）レジスタ７０を含めることが できる。セルはまた、対応する１群のマルチプレクサ、すなわち、ＮＳマルチプ レクサ４５、ＥＶマルチプレクサ５５、Ｃマルチプレクサ６５、及び０Ｍマルチ プレクサ７５をも含む。

これらのレジスタは、単一ビットで、セルに対して作業用の記憶及び通信機能を 提供する。ＮＳレジスタと０Ｍレジスタは、北又は南へ流れるデータの源又は軒 点となる。このように、ＮＳレジスタ４０は、北及び南に隣接するセルのＮＳレ ジスタと双方向で通信することができる。０Ｍレジスタは、北と南の軸に沿って 双方向に、入出力通信を各セルに対して提供する。これらの２つのレジスタの差 異は、同じくセル中に組み込まれている算術論理素子（ＡＬＵ）Ｉ　Ｎｏの動作 に０Ｍレジスタ７０の動作が影響しないことである。その結果、０Ｍレジスタ７ ０は、ＡＬＵＩＩＯを妨害せずに入出力機能を演じることができ、それによって 、通常の処理を妨害せずに入出力を発生することができる。ＥＶレジスタ５０は 、東又は西へ流れるデータの源又は終点となる。各マルチプレクサは、第１図の 制御装置３０のような制御装置から発生する制御信号によって、種々の源からそ れぞれのレジスタへのデータの流れを制御する。

セルには、種々の付加的なエレメントを組み込むことができる。これについて、 以下に詳細に述べる。これらエレメントにはメモリ１００が含まれるが、メモリ １００は、後述するようにデータの記憶と検索における柔軟性が得られるようＩ Ｘ″区分されている。セルには更に、以下に展開するように、或種のアルゴリズ ムに従ってデータ処理を単純化し、加速する条件付き論理素子（ＣＬＵ）１２０ も含まれる。セルにはまた、ＡＦ論理回路１３０をも組み込むことができる。Ａ Ｆ論理回路１３０には、単一ビットのレジスタの、ＡＰレジスタ１４０が含まれ る。この回路は、起動、及び停止の２つの状態を規定する。セルには更にまた、 大域ＯＲ回路（ＧＬＯＲ）１５０が含まれる。このＧＬＯＲは、アレイ中の活性 のセルの総てについて論理的なｒＯＲ，信号を形成するために用いられる。この 信号は、Ｃレジスタ６０の出力とＡＰレジスタ１４０の出力との「論理積」の結 果である。

以下、これらの回路の種々の機能について詳細に述べる。

セル内での算術的な機能は、主制御装置３０の制御の下に提供されるデータに基 づいて動作するＡＬＵＩＩＯによって演じられる。ＡＬＵＩＩＯへの入力は、Ｃ レジスタ６０からの出力と、以下に述べる条件付き論理素子１２０からの出力と であり、条件付き論理素子１２０はＮＳレジスタ４０及びＥＷレジスタ５０から データを取得する。ＡＬＵＩＩＯは、これらのレジスタの何れか、又はメモリ１ ００に出力を送ることができる。特に、ＡＬＵＩＩＯが単一ビット全能付加装置 である時には、ＳＵＭ出力をメモリ１００に書くことができ、ＣＡＲＲＹ及びＢ ＯＲＲＯＷ出力をＣレジスタ６０への入力として用いることができる。加算のよ うな複数ビット動作は、オペランドをビットごとに加算することによって実行さ れ、終結式を伝播する間に次の高次の加算に達する。

複数ビットのオペランドは、メモリ１００中に記憶されなければならない。した がって、殆ど総ての動作は、メモリ１００の能力に強く依存する。例えば、メモ リが単一のボートしか持っていなくて、読み出し又は書き込みを１クロック周期 当たり１回しか演じられないアーキテクチャにおいては、ｎビットの動作では２ つののオペランドを読み出すために２ｎ周期、各部分合計を書き込むためにｎ周 期、最後の値に達するために１周期、全体で３ｎ＋１周期を要することになる。

したがって、読み出し又は書き込みを１周期当たり１回しかできないメモリは、 計算主導梨のアルゴリズムにとって隘路となる。

セルの効率がメモリ１００の能力に強く依存しているので、本発明においてはメ モリ１００のように区分されたメモリを用いることが望ましい。「区分されてい る」ということは、実質的又は論理的に少なくとも半独立的に動作できるブロッ クにＲＡ　Ｍが分割されていることをここでは意味する。第５図に示す好ましい 実施例では、メモリ１００はＢＬＫ　ＯからＢｌ、Ｋ　３までの隣接する４つの ブロックに分割された１２８ビツトである。各ブロックは、１クロック周期中に １回の読み出し又は書き込みのどちらかを行う、独立の単一ボート・メモリであ ることが望ましい。しかし、ここで叙述する実施例において、ＲＡ　Ｍ全体に対 して１クロック周期当たり１回を超える書き込みが有り得ないことが理解される であろう。また、ブロックは、与えられる適応例に関して利点があるならば、複 数ボートを有するメモリでも良いことも理解されるであろう、ブロックＢＬＫ　 ＯからＢＬＫ　３まで１＝使われるのは、ＡＲＡ、Ｍ、ＢＲＡＭ、ＢＲＡＭ本の ３つの読み出しボート、及び１つのさき込みボートＡＲＡＭ＊である。この第１ のボート、Ａ、　Ａ　Ｄ　Ｒ又はＡＯからＡ６までは、ボートＡＲＡＭ、及びＡ ＲＡＭネで動作するためのアドレスの源となる。第２のボート、ＢＡＤＲ又はＢ ＯからＢＯまでは、ボートＢＲＡＭ、及びＢＲＡＭ本で動作するためのアドレス の源となる。メモリ・アドレス復号論理回路１６０及び１７０は、どのボートが どのブロックに接続されるべきかを選択するために、選択されたアドレス・ビッ ト、例えば、上アドレス・ビットを使用する。この復号論理は、バス上の与えら れたアドレスに関して各ブロック対しでボートが１つだけ配備されることを保証 すべく与えられる。信号ＷＥ＊は、内部で発生される書き込み可能ｆ３号である 。

２つのアドレス・バス、３つの読み出しポート、及び１つの書き込みポートを準 備することによって、疑似の複数ポート能力が作り出される。アドレス指定オプ ションによって、１クロック周期当たり１回、２回、又は３回の読み出しが可能 となる。同ｎ読み出し・書き込みを含めることは、加算のようなｎビット動作を ３ｎ＋１ではなく、ｎ＋２のクロック信号中で行うことができるこを意味する。

これは、８ビツトの加算の場合においては正味で２．５対１の改善となる。

メモリ１００を、Ｃレジスタ６０．０Ｍレジスタ７０、ＡＰレジスタ１４０、又 は、ＡＬＵＩＩＯのＳＵＭ出力からロードすることもできる。メモリ１００の出 力を、ＮＳレジスタ４０、Ｅ　Ｗレジスタ５０、Ｃレジスタ６０．０Ｍレジスタ ７０、Ｃレジスタ１９０、又はＡＦレジスタ１４０にロードすることもできる。

当然、セルもまた、ＡＬＵＩＩＯの能力に非常に依存している。このエレメント の能力を改良するために、第６図に示すように、セル中に条件付き論理素子（Ｃ ＬＵ）１２０を含めることが望ましい。ＣＬＵ１２０は、入力をＣマルチプレク サ６５の出力とＣレジスタ１９０の出力とに結合した、入力マルチプレクサ１８ ０を含む、入力マルチプレクサ１８０は、逍切な制御ａｌ信号で制御される。こ の出力は、Ｃレジスタ１９０の入力に結合される。

Ｄ　Ｉ／ジスタ〕２９０の出力はまた、第１の論理ゲート２００と第２の論理ゲ ート２１０とにも結合される。第６図の実施例において、これらのゲートはＡＮ Ｄゲートである。第１論理ゲート２００の１つの入力は、ＮＳレジスタ４０に結 合され、他の入力はＣレジスタ１９０に結合されており、第６図の実施例におい ては逆イ立相の入力になっている。第２論理ゲート２１００１つの入力はまた、 Ｃレジスタ１９００Å力にも結合されている。他の入力はＥＶレジスタ５０に結 合されている。

ＣＬＵ１２０はまた、第１の出力マルチプレクサ２２０と第２の出力マルチプレ クサ２３０をも含む。第１出力マルチプレクサ２２０に対する入力は、Ｎ　Ｓ　 ｌ／レジスタ４０第１論理ゲート２００の出力である。第２出力マルチブレクサ ２３０対する入力は、ＥＶレジスタ５０と第２論理ゲート２１０の出力である。

ＣＬＵ１２０によって、Ｃレジスタ１９０の内容に基づ＜、ＮＳレジスタ４０と ＥＷレジスタ５０のオペランドについての条件付きの算術演算と条件付きの選択 動作の両方を可能にする。この結果、積のような演算を非常に単純化する。例え ば、条件付きの論理がなければ、２つの複数ビットの数の積に関するアルゴリズ ムは、最初の部分合計を形成するために乗数の第１ビツトと被乗数との論理積を 行い、その情、第２の部分合計を形成するために乗数の第２ビツトと被乗数との 論理積を行い、その結果を最初の部分合計値に加算する処理を、最終結果を得る まで継続する各ビットについて継続する反復処理であった。

以下は、ビット配置について通常の右側位置ｉｆｌ１ｇを行った例を示す。

］０１　（被乗数） ０１１　（乗数） ０００１０１　（第１の部分合計〉 ００１１１１　（第２の部分合計） ００１１１１　（解） ＣＬＵ１２０は、条件付きの合計能力を与えることによって、論理積を行うこと に対する必要を排除する。これによって、そこにある乗数ビット値に基づいて部 分合計を条件付きて被乗数に加算することを可能にする。もし乗数ビットが０で あれば、ｏ”ｘ＝ｏであるので、その次の部分合計はそこにある部分合計となる 。もし乗数ビットが１であれば、その次の部分合計はそこにある部分合計と被乗 数との合計となる。ビット配置における右側位置調整は、各反復ごとに１つずつ 部分合計オペランドの開始アドレスの増分を取ることによって達成される。

第６図に示す機器の関係において、積の計算は、ＮＳレジスタ４０１：　Ｏを、 ＥＷレジスタ５０１：被乗数を、また、Ｃレジスタ１９０に少なくとも最下位乗 数ビ・ソトをロードすることによって進められよう。もし１〕レジスタ１９０の 内容が「１」であれば、その値、ＣＬＵ１２０は被乗数を選択する。その後、部 分合計がＮＳレジスタ４０に、被乗数がＥＶレジスタ５０に、また、その次の乗 数ビットがＣレジスタ１９０にロードされる。もしＣレジスタ１９０の内容が「 １」であれば、被乗数は部分合計に加算される。この過程は、必要に応じて最終 解が得られるまで反復される。

セルにはまた、アクティビティ・フラッグ（ＡＦ）論理又は回路１３０を含める ことが望ましい。この回路は、セルを活動中、又は停止中の２つの中の１つの状 態に置くために用いられる。活動中のセルは、アルゴリズムの実行に参与する。

停止中のセルは、参与しない。この状態は、ＡＦレジスタ１４０の内容によって 判定される。

例えば、設定レジスタが活動中のセルを表示し、対応して復帰レジスタが停止中 のセルを表示するようにしても良い。

ＡＦレジスタ１４０の内容は、内部アルゴリズムの実行の結果として、例えばこ こに示すようなＣマルチプレクサ６５を通じて、内部で発生することもできる。

これによって、内部アルゴリズムの実行状態の表示を提供することになろう。し かし、これに替えて、ＡＦレジスタ１４０の内容は、外部で発生することもでき 、ＡＦ論理ユニット２４０による復号の結果として、セルに向けること・もてき る。このＡＦ論理ユニットは、例えばここに示すようなアドレス・バスＡＡＤＲ 上に表われるアドレスを復号できる。これによって、行、桁、又は個別のセルを 均等に選択することを可能にする。ＡＦ論理ユニット２４０は、２つの選択線路 Ｘ、Ｙに応答することもできる。これらの線路は、複数チップ・アレイ中で、特 別なチップ、チップの行、又はチップの桁を選択するために用いられる。

ＡＦｉ４理ユニツユニット２４０Ｆレジスタ１４０の値が外部的に決定されるべ きものであるならば、次にＡＰレジスタ１４０の１点を決定すべくＡＦマルチプ レクサ２５０に与えられる値（セルを能動化する埴）を発生する。

このようなシステムが実際にどのように機能するかについての例として、ＡＦ論 理ユニット２４０が、ＡＡＤＲアドレス・バスと、ＢＡＤＲアドレス・バス上の ２つの線路上の制ｍｔａ号と、Ｃ１７及び０１８と指定された制−ｉ＃偽信号に 応答する、第４図のシステムを考えてみよう、ＡＡＤＲアドレス・バス上の信号 は、行、桁、又は個別のセルを選択する。Ｘ及びＹ選択線路は、複数チップ・ア レイ中のチップを選択する。その徨、表示されたアドレスでのＡＰレジスタ１４ ０の値が内部から発生したものか、また、セル（又は、セルを含む行又は桁）が 外部から起動又は停止されるべきものかを選択するたメニ、ｆｉｌｌｊ御信号Ａ ＤＲＩ、ＢＡＤＲＯＳＣ１７、及び０１８を用いることができる。セルが活動中 である際には、「大域」出力は、全体のＧＬＯＲ出力信号に寄与し、セルのメモ リ１００に能動状態であることを書く。停止中のセルの「大域」出力は、全体の ＧＬＯＲ出カ信号に寄与することができず、セルのメモリ１００に禁止状態であ ることを書く。

このように、ＡＦ論理回路１３０のアドレス符号化論理は、ＧＬＯＲ出力信号を 用いて、セルによるアルゴリズム実行に関する情報を得る手段を提供する。例え ば、上述のアレイの合計を行おうとして、もし南東のコーナーのセル以外の総て のセルが停止中であれば、最番冬合計をＧＬＯＲ出力を通じて得ることができる 。

ＡＰ論理回路１３０と組み合わせた状態のＧＬＯＲ出力の有用性のもう１つの例 として、内容にアドレス可能なメモリ機能の性能について考えてみよう、総ての セルが同時に検索した徨に、セルのどれかが整合性を失っていないかどうかだけ ではなく、セルの位置についても判定するために、ＡＦ論理回路とＧＬＯＲ出力 との組み合わせを用いることができる 第７図では、本発明によるデータ平行処理装置に関する、赤外線イメージ処理シ ステムとしての具体的な応用例を回路図で叙述している。このようなシステムで は典型的に、１フレーム当たり５１２Ｘ５１２ｍ素、１画素当たり８ビツト、及 び３０Ｈｚのフレーム更新率を要する。この性能のためには、実時間画素処理装 置は、３３゜３３ｍ５当たり２６２．１４４画素の平均スループット車を具えて いなければならない０本発明の平行処理装置は、この形式の２次元データ処理問 題を処理するのに理想的に通している。理論的な理想系は、１ｉｉｉ素当たり１ 処理装置、又は、言い換えると、５１２Ｘ５１２アレイのセルである。これによ れば、 ２０ＭＨｚのクロック・レートで、３３．３３ｍ５ごとに約６６’６，６６６命 令の実行が可能になる。しかし、通常、イメージを一連の重複するサブ・イメー ジとして処理することによって、より小規模の７レイを用いる。

このシステムには、アレイ１０と制御装置３０に加えて、赤外線センサ２６０、 センサ・インターフェイス及び制御装置２７０、及び上位ＣＰＵ２８０を含む。

データ人力バッファ及びフォーマツタ２９０とデータ出力バッファ及びフォーマ ツタ３００は、共に第１図のデータ入出力装置１１２０に帰する機能を演じる。

赤外線センサ２６０、及びセンサ・インターフェイス２７０は、この形式の殆ど の応用例に共通する前置モジュールである。赤外線センサ２６０によって受け取 られる赤外線エネルギーは、センサ・インターフェイス２７０によってディジタ ル・データに変換される。このディジタル・データは、その徨、処理のためにア レイｌＯへの転送を可能とすべく、データワード・ストリーム形式からデータ・ ビット・プレーン形式に転換されなければならない。ビット・プレーンは、アレ イ１０と同規模の、共通の重みを持つデータ・ビットの２次元ブレーン（すなわ ち、マトリックスのアレイ）である。画素・プレーン転換と呼ばれるこの転換は 、入力バッファ及びフォーマツク２９０によって行われる。出力バッファ及びフ ォーマツタ３００は、逆の動作を濱じ、出力をＣＰ　Ｕ　２８０が受容できる形 にする。アレイ制ｇ４装置３０は、ピッＩ・・プレーン入出力装置とプログラム 実行の調和を取る。

この制御装置の設計は、殆どのビット・スライス・システムにある制御装置と類 似である。

システムをこれ以外の形に峰飾することが可能である。

例えば、選択的に起動したり停止したりするように論理を組み込むことや、セル 又はアレイを池の平行処理装置と両立するように機能を改変することができる。

このような企ては、例えば、第４図の実７７！例において、区分されたＲＡＭ及 びＡＦ論理改良を停止するか、又は、少なくともこの改良がセルの動作を妨害す るのを防止する「モード」命令に応答して動作するよう１こ、マルチブｌ／クサ ３１０及びゲート３２０を図示されるように結合する、一連の装備を通じて実行 される。

単に解説する目的て、独特の実施例によって本発明を以上のように叙述した。以 上の叙述は、本発明を具体化又は実行するために上述の実施例が唯一の形態であ るかの如き意味を含むものではなく、また、そのように解釈されてはならない。

これと対照的に、当技術分野の通常の技量を有する者にとっては、上に叙述され ていない、本発明の原理と示唆を更に具体化するための多くの実施例を想定し得 ることは明白である。したがって、本発明は、上述の事柄に制限されるべきでは なく、以下の請求項の範囲によって完全に決定されると見なされるべきである。

ＦＩＧ、３ａ ＦＩＧ、３ｂ ＦＩＧ、３ｃ ＦＩＧ、６ ＦｉＧ。７ 一＾１−一・−ハ崗ＩＩ・−”’ｌ　ＰＣＴ／ＵＳ　８９１０４２１３１　２国 際調査報告

Claims (26)

【特許請求の範囲】
1. １．制御信号を発生するための制御装置と、各セルが、少なくとも１つの隣接す るセルと結合されて該制御装置に応答し、該制御信号に従つて少なくとも１つの 隣接するセルからのデータを処理すべく用いられ、該制御装置の命令で１クロッ ク周期当たり２回以上の読み出し・書き込み動作を行うことができるように少な くとも２つのブロックに分割されたメモリを含む、複数の同等のセル とから成るデータ平行処理装置。
2. ２．前記メモリがランダム・アクセス・メモリである、請求項１記載のデータ平 行処理装置。
3. ３．前記ランダム・アクセス・メモリが、４つのブロックに分割され、少なくと も２つのアドレス・バスと、少なくとも３つの読み出しポートと、少なくとも１ つの書き込みポートとから成る、請求項２記載のデータ平行処理装置。
4. ４．制御信号を発生するための制御装置と、各セルが、少なくとも１つの隣接す るセルヒ結合されて該制御装置に応答し、該制御信号に従って少なくとも１つの 隣接するセルからのデータを処理すべく用いられ、該制御装置の命令で１クロッ ク周期当たり２回以上の読み出し・書き込み動作を行うことができるように少な くとも２つのポートを有するメモリを含む、複数の同等のセル とから成るデータ平行処理装置。
5. ５．前記メモリがランダム・アクセス・メモリである、請求項４記載のデータ平 行処理装置。
6. ６．前記ランダム・アクセス′メモリが、少なくとも２つのアドレス・バスと、 少なくとも３つの読み出しポートと、少なくとも１つの書き込みポートとから成 る、請求項５記載のデータ平行処理装置。
7. ７．制御信号を発生するための制御装置と、各セルが、少なくとも１つの隣接す るセルと結合されて該制御装置に応答し、完全な加算器を含む、論理済算及び算 術演算を演じるための第１の装置と、該制御装置と該第１装置とに結合された、 選択的にディジタル・データを保持するための複数のメモリ装置とを含み、該メ モリ装置の少なくとも１つが、１クロック周期当たり２回以上の読み出し・書き 込み動作を行うための少なくとも２つのポートを有する、複数の同等のセル とから成る、データ平行処理装置。
8. ８．前記分割されたメモリ装置がサンダム・アクセス・メモリから成る、請求項 ７記載のデータ平行処理装置。
9. ９．前記ランダム・アクセス・メモリが、４つのブロックに分割され、少なくと も２つのアドレス・バスと、少なくとも３つの読み出しポートと、少なくとも１ つの書き込みポートとから成る、請求項８記載のデータ平行処理装置。
10. １０．制御信号を発生するための制御装置と、各セルが、少なくとも１つの隣接 するセルと結合されて該制御装置に応答し、論理及び算術演算を行うための、完 全な加算器を含む、選択的にディジタル・データを保持するための、第１の装置 と、該制御装置と該第１装置とに結合された、複数のメモリ装置とを含み、該メ モリ装置の少なくとも１つが、１クロック周期当たり２回以上の読み出し・書き 込み動作を行うための少なくとも２つのブロックに分割されている、複数の同等 のセル とから成るデータ平行処理装置。
11. １１．前記少なくとも１つのメモリ装置がランダム・アクセス・メモリから成る 、請求項１０記載のデータ平行処理装置。
12. １２．前記ランダム・アクセス・メモリが少なくとも３つの読み出しポートと、 少なくとも１つの書き込みポートとを有する、請求項１１記載のデータ平行処理 装置。
13. １３．制御信号を発生するための制御装置と、各セルが、少なくとも１つの隣接 するセルと結合されて該制御装置に応答し、論理的アルゴリスを行うための第１ の装置と、該第１装置がアルゴリスムを行うことに現在用いられているかどうか についての標識を選択的に発生するための、該制御装置に応答する、第２の装置 とを含む、複数の同等のセル とから成るデータ平行処理装置。
14. １４．大域信号を発生するために他のセルからの同種の信号に論理的に組み合わ されるべき信号を発生するための第３の装置を各セルが更に含み、セルが大域信 号に寄与しないように前記第２装置が該第３装置を更に選択的に無力化する、 請求項１３記載のチータ平行処理装置。
15. １５．選択的にディジタル・チータを保持し検索するためのメモリ装置を各セル が含み、該メモリ装置中での記憶を前記第２装置が選択的に禁止する、請求項１ ３記載のデータ平行処理装置。
16. １６．前記第２装置が、前記第１装置に更に応答し、前記制御装置か該第１装置 の何れかが発生する信号に応答して前記標識を更に発生する、請求項１３記載の データ平行処理装置。
17. １７．前記制御装置によつて前記第２装置に個別にアドレスできる、請求項１３ 記載のデータ平行処理装置。
18. １８．制御信号を発生するための制御装置と、各セルが、少なくとも１つの隣接 するセルと結合されて該制御装置に応答し、ディジタル・データを記憶するため の少なくとも２つのデータ・レジスタと、該データ・レジスタからのディジタル ・データについての予備的な動作を条件付きで行うための、該２つのデータレジ スタと該制御装置とに応答する、第１の装置と、該第１装置からのディジタル・ データについて論理及び算術機能を演じるための、該第１装置に応答する、第２ の装置とを含む、複数の同等のセルとから成るデータ平行処理装置。
19. １９．前記第２装置が完全な加算器から成る、請求項１８記載のデータ平行処理 装置。
20. ２０．前記少なくとも２つのデータ・レジスタが、第１のデータ・レジスタと第 ２のデータ・レジスタとから成り、 前記第１装置が、 前記第１データ・レジスタに結合された第１の入力端子を有する第１の論理ゲー トと、 前記第２データ・レジスタに結合された第１の入力端子を有する第２の論理ゲー トと、 該第１データ・レジスタの出力と該第１論理ゲートの出力の１つを選択するため の、該第１データ・レジスタの出力端子と該第１論理ゲートの出力端子とに結合 された、前犯制御装置とに応答する、第１の選択装置と、 該第２データ・レジスタの出力と該第２論理ゲートの出力の１つを選択するため の、該第２データ・レジスタの出力端子と該第２論理ゲートの出力端子とに結合 された、前記制御装置とに応答する、第２の選択装置と、 該第１論理ゲートの第２の入力端子と該第２論理ゲートの第２の入力端子とに結 合された、制御値を発生するための装置と を含む、 請求項１８記載のデータ平行処理装置。
21. ２１．前記制御値発生装置が、 前記第１論理ゲートの前記第２入力端子と前記第２論理ゲートの前記第２入力端 子とに結合される、第３のデータ・レジスタと 外部供給の信号と該第３データ・レジスタ内容の１つを該第３データ・レジスタ に対する出力として選択するための、前記制御装置とに応答する、第３の選択装 置 とから成る請求項２０記載のデータ平行処理装置。
22. ２２．前記第２装置が、第１と第２のデータ入力端子を有する完全な加算器から 成り、前記第ｉ選択装置の出力が第１データ入力端子に結合され、第２選択装置 の出力が第２データ入力端子に結合される、請求項２１記載のデータ平行処理装 置。
23. ２３．制御信号を発生するための制御装置と、ｎ及びｍが正の整数で、セルの各 々が少なくとも１つの隣接するセルに結合される、同等のセルのｎＸｍアレイと 、該ｎＸｍアレイのｎ個の外縁セルにそれぞれ結合され、応答する、該外縁セル の関連する工つを該制御信号に応答して少なくとも２つの外部入出力装置の１つ に選択的に結合するための選択装置 とから成るデータ平行処理装置。
24. ２４．制御信号を発生するための制御装置と、各々が該制御信号に応答し、セル ・アレイを形成するために選択的に該複数のセルに相互結合する、複数の同等の セルと、 該アレイをバイパスしてデータ通路を選択的に確立するための、該制御装置に応 答し、該アレイの予定したセルに相互結合された、バイパス装置 とから成るデータ平行処理装置。
25. ２５．前記バイパス装置が複数のそれぞれ前記アレイの前記部分に相互結合され たマルチプレクサ・デマルチプレクサから成る、 請求項２４記載のデータ平行処理装置。
26. ２６．前記アレイが行と桁に配列され、前記バイパス装置が選択された行と桁を 選択的にバイパスするために配列される、請求項２４記載のデータ平行処理装置 。