プロセッサアレイ及びその形成方法

【課題】プロセッサの並列アレイ内の処理エレメント間に高度の接続性を提供し、同時に、処理エレメントを相互接続するために必要な配線を最小限化し、かつＰＥ間通信が遭遇する通信待ち時間を最小限化する。
【解決手段】マニフォルドアレイトポロジは、クラスタ５２内に配列された処理エレメント、ノード、メモリ等を含む。クラスタは、処理エレメントを物理的に再配列することなく、組織の有利な変更を可能にするクラスタスイッチ配置構成９８６Ａによって接続される。既存アレイ用の相互接続部の一般的な個数をかなり減少させることも達成される。容易なスケーラビリティの追加利益を伴い、高速、効率的、かつコストの点でも効果的な処理および通信が得られる。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理システム及び方法の改良に関し、更に詳細には、改良された並列データの処理アーキテクチャに関するものである。
【背景技術】
【０００２】
多くの計算タスクは、データを並列演算するように開発できる。並列プロセッサの効率は、並列プロセッサのアーキテクチャ、コード化されたアルゴリズム、および、並列エレメント内データ配置に依存する。例えば、イメージ処理、パターン認識、および、コンピュータグラフィックスは、全て、２次元または３次元グリッド内に自然配列されたデータに作用する適用方法である。データは、オーディオ、ビデオ、ＳＯＮＡＲ信号、または、ＲＡＤＡＲ信号のような多種多様な信号を表す。離散コサイン変換（ＤＣＴ）、離散逆コサイン変換（ＩＤＣＴ）、コンボリューション、および、この種データに関して一般に実施される演算等は異なるグリッドセグメント上で同時に実施可能であるので、一時に複数のプロセッサが特定タスクに作用できるようにすることによって、この種の演算を著しく加速できるマルチプロセッサーアレイシステムが開発された。並列処理は、ここに参考として組込み済みの米国特許第５，０６５，３３９号、第５，１４６，５４３号、第５，１４６，４２０号、第５，１４８，５１５号、第５，５７７，２６２号、第５，５４６，３３６号、及び、第５，５４２，０２６号を含む多数の特許の対象とされている。
【０００３】
並列処理アーキテクチャに関する従来型の一方法は、最隣接メッシュ接続コンピュータであり、これについては、全て参考としてここに組込み済みであるＲ．Ｃｙｐｈｅｒ、及び、Ｊ．Ｌ．Ｃ．Ｓａｎｚ、「ＳＩＭＤＡｒｃｈｉｔｅｃｔｕｒｅｓａｎｄＡｌｇｏｒｉｔｈｍｓｆｏｒＩｍａｇｅＰｒｏｃｅｓｓｉｎｇａｎｄＣｏｍｐｕｔｅｒＶｉｓｉｏｎ」（イメージ処理およびコンピュータビジョン用ＳＩＭＤアーキテクチャ及びアルゴリズム）音響効果に関するＩＥＥＥ議事録、音声および信号処理Ｖｏｌ．３７、Ｎｏ．１２、ｐｐ．２１５８－２１７４、１９８９年１２月、及び、Ｋ．Ｅ．Ｂａｔｃｈｅｒ「ＤｅｓｉｇｎｏｆａＭａｓｓｉｖｅｌｙＰａｒａｌｌｅｌＰｒｏｃｅｓｓｏｒ」（大量並列プロセッサの設計）コンピュータに関するＩＥＥＥ議事録Ｖｏｌ．Ｃ－２９、Ｎｏ．９、ｐｐ．８３６－８４０、１９８０年９月、及び、Ｌ．Ｕｈｒ「Ｍｕｌｔｉ－ＣｏｍｐｕｔｅｒＡｒｃｈｉｔｅｃｔｕｒｅｓｆｏｒＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ」（人工知能用マルチコンピュータアーキテクチャ）ＮｅｗＹｏｒｋ、Ｎ．Ｙ．、ＪｏｈｎＷｉｌｅｙ＆Ｓｏｎｓ，Ｃｈ．８、ｐ．９７、１９８７年において検討されている。
【０００４】
図１Ａの最隣接トーラス接続コンピュータにおいて、多重処理エレメント（ＰＥ）はトーラス接続経路ＭＰを介して、それらの北、南、東、西隣接ＰＥへ接続され、全てのＰＥは同期的単一命令多重データ（ＳＩＭＤ）様式において処理される。トーラス接続コンピュータは、循環（ラップアラウンド）接続コンピュータにメッシュ接続コンピュータを加えることによって得られるので、メッシュ接続コンピュータは、トーラス接続コンピュータの部分集合を見なすことができる。図１Ｂに示すように、各経路ＭＰはＴ送信ワイヤ及びＲ受信ワイヤを含み、または、図１Ｃに示すように、各経路ＭＰはＢ双方向ワイヤを含むことができる。単方向および双方向通信は両方とも本発明の対象であるが、１つの経路において制御信号を除くバスワイヤの全個数は、今後一般的に、Ｋワイヤと称することとし、ここに、双方向バス設計においてはＫ＝Ｂであり、単方向バス設計においてはＫ＝Ｔ＋Ｒである。ＰＥはその近傍ＰＥの任意のＰＥにデータを伝送できるが、一時にただ１つに限られるものと仮定する。例えば、各ＰＥは、１通信サイクルにおいてデータをその東隣に伝送可能である。更に、データ及び命令は１つの同報通信（ブロードキャスト）発送期間内にコントローラから全てのＰＥへ同時に発送可能であるような同報通信（ブロードキャスト）メカニズムが存在するものと仮定する。
【０００５】
通常、ビット直列ＰＥ間通信は配線の複雑性を最小限化するために用いられるが、それでもなお、トーラス接続アレイの配線の複雑性は実現上の問題を提起する。図１Ａの従来型トーラス接続アレイは、ＰＥの４×４アレイ１０に接続される１６個の処理エレメントを含む。各処理エレメントＰＥ_i,jは、それぞれ、その行番号ｉと列番号ｊがラベル付けされる。各ＰＥは、２点間接続におけるそれぞれ北（Ｎ）、南（Ｓ）、東（Ｅ）、西（Ｗ）最隣ＰＥに通信する。例えば、図１Ａに示すＰＥ_0,0とＰＥ_3,0の間の接続は、ＰＥ_0,0のＮインタフェースとＰＥ₃
_,0のＳインタフェースの間の循環部接続であり、アレイをトーラス構成に形成する循環インタフェースの１つを表す。この種の構成において、各行は１組のＮ相互接続部を含み、Ｎ行にはＮ²の水平接続部がある。同様に、それぞれＮ垂直相互接続部を有するＮ列にはＮ²の垂直相互接続部がある。例えば、図１Ａの場合、Ｎ＝４である。従って、例えば、循環接続部を含むＮ×Ｎトーラス接続コンピュータの集積回路具体化における金属化ラインのようなワイヤの全個数は２ｋＮ²である。ここに、ｋは各相互接続におけるワイヤの個数である。ビット直列相互接続において数ｋは１に等しくてもよい。例えば、図１Ａに示すように、４×４アレイ１０においてｋ＝１の場合、２ｋＮ²＝３２である。
【０００６】
Ｎが比較的小さい幾つかの用途において、ＰＥアレイ全体が１つの単一集積回路に組み込まれることが望ましい。ただし本発明は、各ＰＥが、例えば、個別のマイクロプロセッサチップであるような実施形態を排除するものではない。トーラス接続されたコンピュータ内のワイヤの全個数は重要な意味をもつので、相互接続部が多量の貴重な集積回路の「不動産」又はチップの有効領域を消費することもあり得る。その上、ＰＥ相互接続経路は非常に頻繁に相互に交差し、ＩＣレイアウトプロセスを複雑化し、おそらくは、漏話を介して通信線にノイズを導入する。更に、アレイの北と南および東と西端部におけるＰＥを接続する循環リンクの長さは、アレイサイズの増大につれて増大する。この長さが増大すると各通信ラインのキャパシタンスを増大させ、それによって、ラインの最大ビットレートを低下させ、当該ラインに更にノイズを導入することになる。
【０００７】
トーラスアレイの別の欠点は、転置操作に関連して起きる。処理エレメントとその転置は、通信経路における少なくとも１つの介在エレメントによって分離されるので、転置を用いる演算に待ち時間が導入される。例えば、ＰＥ_2,1がその転置ＰＥ_1,2からデータを必要とする場合には、当該データは介在するＰＥ_1,1又はＰ_2,2を経て移動しなければならない。ＰＥ_1,1及びＰＥ_2,2が占有されていない場合であっても、これは演算に遅延を自然に導入する。ただし、ＰＥがマイクロプロセッサエレメントとして実現される一般的な場合には、ＰＥ_1,1とＰＥ_2,2が他の演算を実施し、データ又はコマンドをＰＥ_1,2からＰＥ_2,1へ転送するために、これらは、整然とした様式において、これらの演算またはコマンドを無視しなければならないという確率が極めて高い。従って、ＰＥ_1,2からＰＥ_1,1にデータを転送し始めるためであってさえも幾つかの演算が実施され、転置したデータを転送するために演算ＰＥ_1,1が強制的に取り消され、これが遅延となる。この種の遅延は、全ての介在ＰＥと共に雪だるま式に増大し、最遠方の転置対に関してかなりの待ち時間が導入される。例えば、図１ＡのＦＥ_3,1／ＰＥ_1,3転置対は、最小限３つの介在ＰＥを持ち、４つの通信ステップに相当する待ち時間を必要とし、なおその上に、一般的な場合には、ＰＥ_3,1とＰＥ_1,3の間でデータを転送するために、これら全てのＰＥにおいて取り消されるべき全てのタスクの待ち時間が生じる。
【０００８】
トーラス接続アレイのこの種の限界を認識することによるアレイに関する新規技法が、参考としてそれらの全体がここに組込み済みの「ＭａｓｓｉｖｅｌｙＰａｒａｌｌｅｌＤｉａｇｏｎａｌＦｏｌｄＡｒｒａｙＰｒｏｃｅｓｓｏｒ」、Ｇ．Ｇ．Ｐｅｃｈａｎｅｋ等、アプリケーション特定アレイプロセッサに関する１９９３年国際会議、ｐｐ．１４０－１４３、１０月２５－２７、１９９３年、ベニス、イタリア、及び、「ＭｕｌｔｉｐｌｅＦｏｌｄＣｌｕｓｔｅｒｅｄＰｒｏｃｅｓｓｏｒＴｏｒｕｓＡｒｒａｙ」、Ｇ．Ｇ．Ｐｅｃｈａｎｅｋ等、ＶＬＳＩ設計に関する第５ＮＡＳＡシンポジウム議事録、ｐｐ．８．４．１－１１、１１月４－５、１９９３年、ニューメキシコ大学、Ａｌｂｕｑｕｅｒｑｕｅ、ニューメキシコに開示されている。これらのトーラスアレイ組織の演算技法は、フォールドオーバエッジとして従来型の最隣接トーラスの対角ＰＥを用いるＰＥアレイのフォールディングである。図２Ａのアレイ２０に示すように、これらの技法は、循環接続部の個数および長さが減少し、それらの転置ＰＥに密接に近接してＰＥが位置するようにＰＥ間配線を実質的に減少させるために利用可能である。このプロセッサアレイアーキテクチャは、例えば、それらの全体が参考としてここに組み込まれている米国特許第５，５７７，２６２号、第５，６１２，９０８号、ＥＰ０，７２６，５３２、ＥＰ０，７２６，５２９に開示されている。この種のアレイは、例えば、単フォールド対角フォールドメシュのようなＰＥ組合わせの不規則性により、従来型トーラスアーキテクチャよりも実質的に優れた利益を提供すると同時に、幾らかのＰＥは２つのグループとしてまとめられ、その他のＰＥは単独のままである。３フォールド対角フォールドメシュにおいては、４個のＰＥおよび８個のＰＥで構成されるクラスタがある。アレイ全体は三角形であるので、対角フォールド型アレイは、効率的で安価な集積回路の実現にとって本質的な障害となる。なおその上に、対角フォールドメシュ及び他の従来型メッシュアーキテクチャにおいては、相互接続トポロジーは本質的にＰＥ定義の一部分である。この技法は、トポロジにおけるＰＥの位置を固定し、結果的に、ＰＥのトポロジおよび実現される固定したコンフィギュレーションへのそれらの接続性を限定する。
【０００９】
多くの並列データ処理システムは超立方体相互接続トポロジを用いる。超立方体コンピュータは、高度の接続性を供給する方式で相互接続されるＰ＝２^dＰＥを含む。接続部は幾何学的または算術的にモデル化できる。幾何学モデルにおいて、ＰＥはｄ次元超立方体の角に相当し、リンクは超立方体の縁に相当する。Ｐ＝２^dＰＥの超立方体は、各々が更に小さい超立方体の対応する角の間の接続部をもつ、２^d-1ＰＥの２つの超立方体とみなすことができる。
【００１０】
算術モデルにおいて、各ＰＥは、０からｄ－１までの一意的２進インデックスを割り当てられる。それらのインデックスの２進表現が厳密にただ１ビット位置だけ異なりさえすれば、任意の２つのＰＥが接続される。幾何学および算術モデルは、ｄ次元の各々を一意的ビット位置と提携させることにより相互に関連付けることができる。従って、１ビット位置だけ異なるインデックスを持つプロパティは２つの（ｄ－１）次元超立方体の対応する角を占有することに等価である。例えば、１つのＰＥには、トポロジ内のその位置を示すラベルを割り当てることができる。このラベル｛Ｄ_0,Ｄ_1,...Ｄ_r-1｝は２進表現であり、ここに、各数字はｒ－Ｄ超立方体上の通信に利用可能な１つのｒ次元接続経路を示す。殆どの場合、超立方体における各ノードは、その直接接続されたノードとＤだけ異なる１つの数字である。例えば、超立方体における最長経路は、ＰＥ｛Ｄ_0,Ｄ_1,...Ｄ_r-1｝とその補数｛￢Ｄ₀,￢Ｄ₁,...￢Ｄ_r-1｝の間、例えば、ＰＥ１０１１０１とＰＥ０１００１０の間の経路である。超立方体トポロジについては、ここに参考として組込み済みのＲｏｂｅｒｔＣｙｐｈｅｒ、及び、ＪｏｒｇｅＬ．Ｃ．Ｓａｎｚ「ＴｈｅＳＩＭＤＭｏｄｅｌｏｆＰａｒａｌｌｅｌＣｏｍｐｕｔａｔｉｏｎ」（並列コンピュータのＳＩＭＤモデル）１９９４年Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ、ＮｅｗＹｏｒｋ、ｐｐ．６１－６８、及び、Ｆ．ＴｈｏｍａｓＬｅｉｇｈｔｏｎ、「ＩｎｔｒｏｄｕｃｔｉｏｎＴｏＰａｒａｌｌｅｌＡｌｇｏｒｉｔｈｍｓａｎｄＡｒｃｈｉｔｅｃｔｕｒｅｓ：Ａｒｒａｙｓ，Ｔｒｅｅｓ，Ｈｙｐｅｒｃｕｂｅｓ，」（並列アルゴリズム及びアーキテクチャ概論：アレイ、トリー、超立方体）１９９２年、ＭｏｒｇａｎＫａｕｆｍａｎＰｕｂｌｉｓｈｅｒｓ、Ｉｎｃ．、ＳａｎＭａｔｅｏ、ＣＡ、ｐｐ．３８９－４０４に論じられている。超立方体トポロジの１つの欠点は、各プロセッサへの接続部の個数がネットワークのサイズと共に対数的に増大するということである。その上、超立方体内のＰＥ間通信には、特に、ＰＥが相互に補数である場合、実質的な待ち時間が課される。
【００１１】
多次元超立方体は、トーラス、対角フォールドトーラス、又は、他のＰＥ配列構成にマップ可能である。この種のマッピングについて、以下に簡単に検討することとする。この検討に関係する図面およびこの出願に含まれる他の全ての図面においては、別途注記しない限り、各ＰＥ相互接続を単線として示すが、線（ライン）は双方向トライステートリンク又は２つの単方向リンクである相互接続リンクを表す。双方向トライステートリンクは、当該リンク上におけるデータ衝突を防止する制御スキーム下における、１つのリンク上での多重点における信号源（ソース）の生成をサポートする。単方向リンクは、あらゆるインターフェイス信号用として、二点間単一源および単一受信機対を用いる。更に、ビット直列および多重ビット並列具体化例についても検討する。
【００１２】
超立方体は、トーラス上にマッピング可能で、２次元トーラスはプロセッサエレメント（ＰＥ）で構成され、図１Ａ及び１Ｄに示すように、各ＰＥは、頂部ＰＥラベルによって示されるように、トーラスノード（行と列）、及び、各ＰＥ内の底部ラベルによって示される超立方体ＰＥ番号と連携する。超立方体ＰＥ番号またはノードアドレスは、各数字が接続性次元を表すｒ次元（ｒＤ）超立方体に関するｒ数字表現として与えられる。超立方体内の各ＰＥは、それらのノードアドレスがそれ自体から厳密に１つの数字だけ変化するこれらのＰＥのみに接続される。この相互接続スキームは、図１Ａ及び１Ｄに示すように、４Ｄ超立方体が４×４トーラスにマッピングされることを可能にする。図１Ａは、ただ１つの単一２進数字のみが順次数の間で変化するグレイコード符号化ＰＥ_G(i),G(j)を用いてＰＥ_i,jノードをコード化する。例えば、１０進数列０、１、２、３は、２進数列では００、０１、１０、１１と表されるが、グレイコード数列は００、０１、１０、１１となるはずである。図１Ｄは、最隣接トーラスへの代替超立方体マッピングを示す。
【００１３】
超立方体マシンの最も初期の具体化例の１つは、Ｃａｌｔｅｃｈ，Ｃ．Ｓｅｉｔｚ「ＴｈｅＣｏｓｍｉｃＣｕｂｅ」ＡＣＭ通信、Ｖｏｌ．２８、Ｎｏ．１、ｐｐ．２２－３３、１９８５年記載の６Ｄ超立方体であるコスミックキューブであった。コスミックキューブは、複数命令列複数データ（ＭＩＭＤ）モードで実行し、超立方体接続プロセッサ間で通信するためにメッセージ受け渡しを用いるインテル８０８６プロセッサによって実現された。他の超立方体具体化例ＮＣＵＢＥは、特注プロセッサが超立方体のノードを形式するチップを用いる１つの大型コンフィギュレーションとしての１０－Ｄ超立方体から成る。ＮＣＵＢＥはＭＩＭＤ型マシンであるが、単一プログラム複数データ（ＳＰＭＤ）モード作動もサポートする。この場合、各ノードプロセッサは同一プログラムのコピーを持つので、異なる条件付きコードストリームを独立的に処理することができる。ＴｈｉｎｋｉｎｇＭａｃｈｉｎｅｓＣｏｒｐｏｒａｔｉｏｎによって作成されたコネクションマシン（ＣＭ）は別の超立方体具体化例であった。初期のＣＭ－１マシンは、ビット直列処理セルの４×４グリッドを含む各ノードを有する１２Ｄ超立方体であった。
【００１４】
これらのような従来型の超立方体具体化例の１つの欠点は、各処理エレメントが、各超立方体次元に関する少なくとも１つの双方向性データポートを所有しなければならないことである。
【００１５】
以下に、更に詳細に検討するように、本発明の１つの態様は、我々のＰＥがネットワークトポロジから結合解除され、ただ１つの入力ポートと１つの出力ポートだけを必要とすることである。
【００１６】
更に、各追加された超立方体次元は、各ＰＥにおけるポートの個数を増大するので、データポート専用ＰＥの占める割合が過度に大きくなって各ＰＥの設計が早急に非実際的となる。更にその上、「直径」としての待ち時間が更に一層大きくなることによって補足ＰＥ間通信の負担が大きくなる。即ち、超立方体の補足ＰＥ間の通信ステップの個数が拡大する。換言すれば、ノードアドレスとその補集合の間の接続を提供することにより、超立方体ＰＥノード間の最長経路は、難しく、かつ高価になり、スケーラブルでなくなるはずである。
【００１７】
従って、プロセッサの並列アレイ内の処理エレメント間に高度の接続性を提供し、同時に、処理エレメントを相互接続するために必要な配線を最小限化し、かつＰＥ間通信が遭遇する通信待ち時間を最小限化することが非常に望ましい。多重プロセッサアレイのアーキテクチャ及びプロセッサ相互接続の更なる改良の必要性が存在し、以下に、一層十分に検討するように、本発明は、これら及び他のこの種の必要性を扱う。
【発明の概要】
【００１８】
本発明は、処理エレメント間の接続性を改良する処理エレメントのアレイに向けられ、同時に、従来型トーラス又は超立方体処理エレメントアレイの配線必要条件と比較して、アレイの相互接続の配線必要条件を実質的に軽減することに向けられる。好ましい実施形態において、１つのアレイは、転置操作の待ち時間およびＰＥノードとその超立方体補足(hypercube complement)ノードの間の通信待ち時間の実質的な減少を達成する。その上、このアレイは、循環配線の長さをアレイ全体の次元から切り離し、それによって、最長相互接続配線の長さを減少させる。同様に、通信ＰＥ間で衝突を引き起こすことのないアレイ通信パターンであるためには、特定のトポロジがそのＰＥノードから必要とする近傍接続部の個数と関係なく、１つのＰＥ当たり、ただ１つの送信ポートと１つの受信ポートだけが必要である。そのアレイの好ましい集積回路具体化例は、矩形または方形アウトラインを呈示するように組合わされた類似の処理エレメントクラスタの組合わせを含む。処理エレメントの類似性、処理エレメントクラスタの類似性、および、アレイ全体のアウトラインの規則性は、本アレイを特にコスト的にも効率的な集積回路の製造に適している。
【００１９】
本発明に従ってアレイを形成するには、先ず、処理エレメントを、単一命令多重データ（ＳＩＭＤ）演算の通信必要条件を利用するクラスタに組み合わせる。次に、そのクラスタ内で処理エレメントを完全に接続する。次に、処理エレメントをグループ化し、１つのクラスタのエレメントがクラスタ内において、および、ただ２つの他のクラスタの構成メンバと通信するようにしてもよい。更に、各クラスタの構成処理エレメントは、ただ２つの相互に排他的な方向のみにおいて、他のクラスタの各々の処理エレメントと通信する。定義により、単方向能力を有するＳＩＭＤトーラスにおいて、北／南方向は東／西と相互に排他的である。処理エレメントクラスタは、名称が示唆するように、相互に物理的に密接に近接して形成されることが好ましいプロセッサのグループである。集積回路の具体化例において、例えば、クラスタの処理エレメントは相互に出来る限り近接して配置されることが好ましく、アレイ内の他の任意の処理エレメントよりも相互に一層近接していることが好ましい。例えば、処理エレメント従来型４×４トーラスアレイに対応するアレイは、それぞれ４つのエレメントで構成される４つのクラスタを含み、各クラスタは北および東方にのみ相互に通信し、南および西方に他のクラスタと通信し、または、南および東方に他のクラスタと通信し、北および西方に他のクラスタと通信する。このようにＰＥをクラスタ化することにより、多重化を介して、ＰＥクラスタ間の通信経路は共用可能であり、従って、アレイに必要な相互接続配線を実質的に減少させることができる。
【００２０】
好ましい実施の形態において、クラスタを構成するＰＥは、処理エレメント、それらの転置、及び、超立方体補足ＰＥが同一クラスタ内に所在し、クラスタ間通信路経を介して相互に通信し、それによって、従来型トーラスアレイ上で実行される転置操作および従来型超立方体アレイ上で実施される超立方体補足ＰＥ間通信と連携した待ち時間を除去するように選定される。その上、従来型循環経路は任意のＰＥからＰＥへの経路と同様に扱われるので、最長通信路経路は、アレイ全体の大きさに関係なく、クラスタ間スペーシングと同じ程度に短い。
【００２１】
各ＰＥは、仮想ＰＥアドレス記憶ユニット及びコンフィギュレーションコントローラを含む。仮想ＰＥ数およびコンフィギュレーション制御情報は、クラスタスイッチの設定を決定し、それによってＰＥアレイのトポロジを再構成するように組合わされる。この再構成は、例えば、コントローラからディスパッチされた命令に応答してなされても良い。アレイ内ＰＥはクラスタ化され、ＰＥとその転置がクラスタ内で組合わされ、ＰＥとその超立方体補集合が同一クラスタ内に含まれる。その上、各クラスタ内で完全にＰＥ間を接続するためのクラスタスイッチと組合わされた動的再構成は、多種多様なトポロジでアレイを再構成する能力を提供する。
【００２２】
他の態様において、クラスタ内ＰＥは、当該クラスタ内でＰＥを完全に接続し、当該クラスタ内における各仮想ＰＥに２つの外部直交クラスタへの同一アクセスを可能にするクラスタスイッチに対して同一インタフェースを有利に所有することができる。さて、本発明の教示に従い、適所にクラスタスイッチを備えた２つのネットワークが実際に所在する。１つはクラスタ内ＰＥを相互に完全に接続するネットワーク、及び、もう１つはＰＥを他のクラスタＰＥへ接続するネットワークであり、これによって、トーラスと超立方体の接続性に必要な接続経路を提供する。クラスタスイッチに対する内部接続経路は、転置と超補足体の接続性を提供する。異なる仮想ＰＥ配列構成に関して、転置はクラスタを横断して実施される。この種の４ＰＥクラスタスイッチ、及び、他の４ＰＥクラスタへのその相互接続に関して、任意のクラスタに対して生成されるただ４つの出力バスが有っても差し支えない。これら４つのバスの各々は、任意のクラスタにおいて、２つの直交クラスタ接続点を持つ。本発明に係るマニフォルドアレイ処理において、強化された接続性超立方体が提供可能であり、この超立方体内には４個のノードの各クラスタはわずか４つの出力バスを持ち、各バスのファンアウトは３であり、１つはスイッチに対し、１つは直交クラスタの各々に対する。１つの仮想ノード当たり３つの受信される信号がある。１つはスイッチにとって内部信号であり、１つは直交クラスタの各々からの信号である。
【００２３】
本発明のこれら及び他の特徴、態様、及び、利点は、添付図面と共に次の詳細な記述から、当該技術分野における当業者にとって明白となるであろう。
【図面の簡単な説明】
【００２４】
【図１Ａ】従来の４×４最隣接接続型トーラス処理エレメント（ＰＥ）アレイのブロック図である。
【図１Ｂ】図１Ａの従来のトーラス接続経路が、どのようにＴ送信およびＲ受信結線を含むかを例示する図である。
【図１Ｃ】図１Ａの従来のトーラス接続経路が、どのようにＢの２双方向性結線を含むかを例示する図である。
【図１Ｄ】第２の従来の４×４最隣接接続型トーラスＰＥアレイの構成図である。
【図２Ａ】従来の折り畳まれたＰＥアレイの構成図である。
【図２Ｂ】従来の折り畳まれたＰＥアレイの構成図である。
【図３Ａ】本発明に係るＰＥアレイ内で適宜使用される処理エレメントの構成図である。
【図３Ｂ】本発明に係るＰＥアレイ内で適宜使用される処理エレメントの構成図である。
【図３Ｃ】本発明に係るＰＥアレイ内で適宜使用される処理エレメントの構成図である。
【図３Ｄ】本発明に係るクラスタスイッチ制御の更なる態様を示す図である。
【図４】マニフォルドアレイ内ＰＥのクラスタリングおよびＰＥのクラスタ間通信を示す構成図である。
【図５】クラスタスイッチの更なる詳細を示す、図４の個別ＰＥクラスタの構成図である。
【図６】改良されたクラスタスイッチを備えた、本発明に係る改良されたＰＥクラスタの構成図である。
【図７】ＰＥクラスタ間の相互接続経路をより詳細に示すブロック図である。
【図８Ａ】バッファを含まないクラスタスイッチの具体例を示すブロック図である。
【図８Ｂ】バッファ含まないクラスタスイッチを用いる、ＰＥクラスタ間の相互接続経路をより詳細に示すブロック図である。
【図８Ｃ】バッファ含まないクラスタスイッチを用いる、ＰＥクラスタ間の相互接続経路をより詳細に示すブロック図である。
【図９Ａ】大型アレイを形成するもう他の直交２×２クラスタへの相互接続経路を示す２×２クラスタのブロック図である。
【図９Ｂ】２×２マニフォルドアレイのブロック図である。
【図１０】４×４トーラス用の東側の通信経路を示す構成図である。
【図１１】４×４トーラス用の西側の通信経路を示す構成図である。
【図１２】４×４トーラス用の北側の通信経路を示す構成図である。
【図１３】４×４トーラス用の南側の通信経路を示す構成図である。
【図１４】４×４マニフォルドアレイの転置通信経路を示すブロック図である。
【図１５】４×４マニフォルドアレイ上の４個の独立した１×４線形リングを示す構成図である。
【図１６】アレイコンフィギュレーションにおけるｚ軸送信演算用の通信経路を示すブロック図である。
【図１７】４×４マニフォルドアレイの超立方体ノードラベルを例示するブロック図である。
【図１８】４×４マニフォルドアレイの超立方体補集合通信を示す構成図である。
【図１９】５Ｄ超立方体を示す構成図である。
【図２０】マニフォルドアレイにマッピングされた５Ｄ超立方体を例示するブロック図である。
【図２１Ａ】トーラスに埋め込まれた４Ｄ超立方体のノードエレメントを示す表を示す図である。
【図２１Ｂ】埋め込まれた超立方体ノードの配置を示す改良されたマニフォルドアレイの表を示す図である。
【図２１Ｃ】頂部ＰＥラベル（ＰＥ-x,y）付き８×８の２Ｄトーラス、中央ＰＥラベル（x,y,z）付き３Ｄ立方体、および、底部ＰＥラベルＧ_xＧ_yＧ_z＝ｄ₅ｄ₄ｄ₃ｄ₂ｄ₁ｄ₀ラベル付き６Ｄ超立方体の４×４×４の表現図である。
【図２２】列の１Ｄ下方回転後における４×４×４表現図である。
【図２３】図２２のノードの４×４×４ｚ平面表現図である。
【図２４】列の１Ｄ下方回転後における４×４×４ｚ平面表現図である。
【図２５】レイアウト接続性に関するｚ平面表現の再順序付けを示す図である。
【図２６】ｚ平面の２×２サブクラスタへの分離を示す図である。
【図２７Ａ】２×２サブクラスタの４個の４×４マニフォルドアレイへの相互接続を示す図である。
【図２７Ｂ】４×４×４ＰＥノード入力（受信）接続性の一例を示す図である。
【図２８Ａ】クラスタ構成当たり１つの単一コントローラおよび典型的インタフェースを示す４×４マニフォルドアレイの構成図である。
【図２８Ｂ】その外部インターフェイス内へ３２個のデータアイテムを受け取る図２８Ａの４×４多重コントローラマニフォルドアレイを示す図である。
【図２９】一例における３２個のデータアイテムの４個のメモリコントローラへのローディングを示す図２８Ａの４×４多重コントローラマニフォルドアレイを示す図である。
【図３０】各クラスタにおける個別ＰＥへの３２個のデータアイテムのロード配分を例示する、図２８Ａの４×４多重コントローラマニフォルドアレイを示す図である。
【図３１】図２８Ａ～図３０に関する完全シャッフル例の各ステップの後における３２個の典型的データをリストする表を示す図である。
【図３２】スワップ北側通信演算を実行するためにＰＥ間でデータが通る経路および完全シャッフル例の通信演算完了時におけるＰＥレジスタにおける結果を示す４×４マニフォルドアレイを示す図である。
【図３３】スワップ南側通信演算を実行するためにＰＥの間でデータが通る経路および完全シャッフル例の通信演算完了時におけるＰＥレジスタ内の結果を示す４×４マニフォルドアレイを示す図である。
【発明を実施するための形態】
【００２５】
一実施形態において、本発明に係るマニフォルドアレイプロセッサは、一方の１つのクラスタのエレメントが、他方のただ２つのクラスタの部材と直接通信するようにクラスタまたはグループとしてのＰＥを組み合わせ、各クラスタの組成処理エレメントは、ただ２つの相互に排他的な方向において、もう一方のクラスタの各々の処理エレメントと直接通信する。このようにＰＥをクラスタ化することにより、ＰＥクラスタ間の通信経路は共用可能であり、従って、アレイにとって必要な相互接続配線を実質的に減少させることができる。その上、各ＰＥは単一の送信ポートと単一の受信ポート、又は、２方向性の場合、順次的、又は、タイムスライス通信実施の場合には、単一の送受信ポートを有する。その結果、個別ＰＥはアレイアーキテクチャから切り離される。即ち、各ＰＥがＮ通信ポートを有する従来型のＮ次元ハイパキューブ接続アレイとは異なる。単一の送信ポートおよび単一の受信ポートを用いる具体化例においては、アレイ内の全てのＰＥは送信と受信を同時に実施する。従来の６Ｄハイパキューブの場合において、これは、各ＰＥに対して、６個の送信ポートと６個の受信ポートからなる、合計１２個のデータポートを必要とする。本発明の場合には、ハイパキューブ（超立方体）の大きさに関係なく、ただ１つの送信ポートと１つの受信ポートからなる、合計２つのがデータポートだけが必要である。上記のとおり、２方向、順次的、または、タイムスライスデータ通信が用いられる場合には、送受信データポートを１つの送受信データポートに組合わすことができる。各ＰＥは仮想ＰＥ記憶ユニット及びコンフィギュレーション制御ユニットを含む。仮想ＰＥ番号およびコンフィギュレーション制御情報は、通信の方向を制御し、ＰＥアレイのトポロジを再構成するために、クラスタスイッチの設定を決定するように組合わされる。この再構成は、例えば、コントローラから発送された命令に応答してなされても差し支えない。１つのＰＥとその転置（トランスポーズ）が１つのクラスタ内で組合わされるようにアレイ内のＰＥがクラスタ化され、ＰＥおよびそのハイパーキューブ補集合は同じクラスタに含まれる。
【００２６】
本実施形態において、クラスタを含むＰＥは、処理エレメントとそれらの転置が同一クラスタ内に配置され、クラスタ内通信経を介して相互に交信するように選択される。説明のために、処理エレメントは従来のトーラスアレイであるとみなされ、例えば、処理エレメントＰＥ_0,0は、従来型のトーラスアレイの「北西」コーナ、即ち、行０と列０に位置する処理エレメントとみなされる。従って、新規クラスタアレイのレイアウトは、従来型のアレイプロセッサのレイアウトとは実質的に異なるが、従来のトーラス及び新規なクラスタアレイの対応する処理エレメントに同一データが供給される。例えば、新規なクラスタアレイの０，０エレメントは、従来型のトーラス接続アレイの０，０エレメントを作動させるのと同じデータを受け取るはずである。その上、本記述で用いる方向はトーラス接続アレイの方向を意味するものとする。例えば、エレメント間の通信が北から南へ実施される場合に、これらの方向は、従来型のトーラス接続アレイ内通信の方向を意味する。
【００２７】
ＰＥは、単一命令ストリーム・単一データストリーム（ＳＩＳＤ）型の単一マイクロプロセッサチップであっても差し支えない。包含されるコンセプトを示すために、以下の記述に限定されることなく、基本的なＰＥについて記述することとする。図３Ａは、本発明の新規ＰＥアレイ用の各ＰＥとして用いられる適当な実施形態を示すＰＥ４０の基本構造を示す。説明を簡単にするために、インタフェース論理回路およびバッファは図示されていない。命令バス３１は、ＳＩＭＤコントローラ２９からディスパッチされた命令を受け取るように接続され、データバス３２は、メモリ３３又はＰＥ４０にとって別の外部のデータソースからのデータを受け取るように接続される。レジスタファイル記憶媒体３４は、実行ユニット３６にソースオペランドデータを供給する。命令デコーダ／コントローラ３８は、命令バス３１を介して命令を受け取るように、かつバス２１を経てレジスタファイル３４内のレジスタに制御信号を供給するように接続される。ファイル３４のレジスタは、経路２２を経てそれらの内容をオペランドとして実行ユニット３６へ供給する。実行ユニット３６は、命令デコーダ／コントローラ３８から制御信号２３を受け取り、レジスタファイル３４に経路２４を経て結果を供給する。更に、命令デコーダ／コントローラ３８は、ＳｗｉｔｃｈＥｎａｂｌｅ（スイッチイネーブル）とラベルを付した出力ライン３９にクラスタスイッチイネーブル信号を供給する。クラスタスイッチの機能については、図５及び図６の検討に関連して以下に更に詳細に検討することとする。データ又はコマンドのＰＥ間通信は、Ｒｅｃｅｉｖｅ（受信）とラベル付けされた入力３７において受け取られ、Ｓｅｎｄ（送信）とラベル付けされた送信出力３５から送信される。
【００２８】
仮想ＰＥ記憶ユニット４２は、それぞれのストア４３及び読み出し４５ラインを介して命令デコーダ／コントローラ３８へ接続される。仮想ＰＥ番号は、新規仮想ＰＥ番号を記憶ユニット４２へ送るデコーダ／コントローラ３８で受け取られた命令を介して、コントローラ２９によってプログラム可能である。仮想ＰＥ番号は、接続ネットワークによって課される限界内において、コントローラ２９によってトポロジ内の各ＰＥの位置を動的に制御するために使用可能である。
【００２９】
コンフィギュレーションコントローラ４４は、それぞれのストア４７及び読み出し４９ラインを介して命令デコーダ／コントローラ３８へ接続される。コンフィギュレーションコントローラ４４は、例えば現行コンフィギュレーションのようなコンフィギュレーション情報を供給し、制御情報をクラスタスイッチへ供給する。これらクラスタスイッチは、アレイ内の他のＰＥへのＰＥの接続を制御する。デコーダ／コントローラ３８は、コンフィギュレーションコントローラ４４からの現行コンフィギュレーションと、仮想ＰＥ記憶ユニット４２からの仮想ＰＥアドレスと、コントローラ２９からの命令によって運ばれた、例えば「転置ＰＥ間通信」のような通信操作情報を組み合わせ、この情報をクラスタスイッチに伝達する。デコーダ／コントローラ３８は、図６に関連してさらに詳細に検討するように、この情報を使用してクラスタスイッチに関する適切な設定を決定し、スイッチイネーブルインタフェース３９を介してこの情報を伝送するスイッチ制御論理回路を含む。スイッチ制御論理回路、クラスタスイッチ命令デコーダ／コントローラ、および、コンフィギュレーションコントローラは、ＰＥの境界外において、クラスタスイッチに組み込み可能である。新規ＰＥノードはトポロジ接続から独立して定義されるので、これらの機能は分離可能である。本実施の形態において、全体の論理と全体の機能性は、制御機能が独立している場合であっても、制御機能を分離しないことによって改良される。
【００３０】
図３Ｄにおいて、クラスタスイッチ制御の更なる詳細を示すために、例えば、適当なクラスタスイッチ６０を示す。このクラスタスイッチ６０は、図示されるように、Ａ、Ｂ、Ｃ、Ｄの４グループに分割され、各グループは４入力マルチプレクサと３入力マルチプレクサから成る。これらのグループの各々は、ＰＥクラスタ内の特定のＰＥと連携し、この連携は点線矢印によって示される。例えば、ＰＥ_0,0は「Ａ」グループのマルチプレクサａ１およびａ２と連携する。これらグループ内のマルチプレクサは、それらに関連するＰＥによって制御される。図に示すように、これらのマルチプレクサを制御することにより、正常なＳＩＭＤ動作モードが保存される。
【００３１】
ＳＩＭＤモードの動作時において、全てのＰＥはコントローラ発送命令を受け取り、同期して作動する。ＰＥのＩＤに依存する演算を一意的に指定する命令を含む全ての命令が、全てのＰＥにディスパッチされる。これらの命令は、全てのＰＥによって受け取られ、復号されてから、コントローラ２９から発送された命令によるプログラム制御の下で選択可能なＰＥイネーブル／ディスエイブルフラグを用いて、命令内のオペコード、その命令コードの拡張フィールドオペコードに依存するＰＥの全て又はＰＥの部分集合によって実行される。オペコード及びその拡張フィールドは、受け取った命令を実行する１つのセットを含むＰＥの集合を指定する。ＰＥイネーブル／ディスイネーブルフラグは、ＰＥが応答し得る活動レベルを決定する。例えば、以下に、適宜使用できるフラグを示す。
・レベル０：完全に不能化されたＰＥ。
・受け取った全ての命令がＮＯＰとして扱われる。
・レベル１：部分的にイネーブルにされたＰＥ：ＰＥが制御情報を受け取る：
・例えば仮想ＰＥのＩＤ、飽和／未飽和モード、等のような制御情報のローディングを可能にする。
・例えば読取り状態レジスタのように制御情報の記憶を可能にする。
・全ての演算および通信命令がＮＯＰとして扱われる。
・レベル２：部分的にイネーブルにされたＰＥ；ＰＥが制御情報を受け取る：
・例えば、仮想ＰＥのＩＤ、飽和／未飽和モード、等のような制御情報のローディングを可能にする。
・例えば読取り状態レジスタのように制御情報の記憶を可能にする。
・全ての演算命令はＮＯＰとして扱われる。
・全ての通信命令が実行される。
・レベル３：完全にイネーブルにされたＰＥ：
・受取られた全ての命令が実行される。
【００３２】
所与サイズのマニフォルドアレイに関しては、例えば４Ｄ、５Ｄ、または、６Ｄハイパキューブの選定により、許容されたコンフィギュレーションが前以て決定されていても差し支えない。この種の一実施形態において、可能なノード識別は「ハードワイヤード(hardwired)」である。即ち、集積回路具体化例の一部として不揮発に固定される。次に、所与のコンフィギュレーションに関する仮想ＰＥ番号は、コントローラ２９からアレイ内の全てのＰＥ４０に送られる単一命令によって示唆される。この命令は、適当な仮想ＰＥ番号をそれぞれのＰＥに割り当てるために、各ＰＥ内のデコーダ／コントローラ３８によって解釈されることが好ましい。各デコーダ／コントローラ３８は、ＰＥおよびコンフィギュレーションに関する仮想ＰＥ番号を含む各ＰＥ記憶エリア４２内のそれぞれのロケーションに関して、効果的にテーブルルックアップ動作を実施できる。
【００３３】
その中で類似エレメントが、図３ＡのＰＥ４０の指定番号を共有する図３ＢのＰＥ４０’は、命令デコーダ／コントローラ３８、および、レジスタファイル３４に接続されたインタフェース制御ユニット５０を含む。この制御ユニット５０は、信号ライン２５を経てデコーダ／コントローラ３８から獲得された制御信号に基づいて、例えば並直列変換、データ暗号化、および、データフォーマット変換のようなデータフォーマット変換を提供する。ＰＥ４０”を示す図３Ｃの別の実施形態において、送信経路３７は１つ又は複数の実行ユニット３６によって生成され、受信経路３５は、直接またはインタフェース制御ユニット５０を介してレジスタファイル３４に接続される。インタフェース制御ユニット５０は、１つ又は複数のライン２５を経て命令デコーダ／コントローラ３８から受信した制御信号に基づいてデータをフォーマット化する。このインタフェース制御ユニットによって実施されるデータフォーマット化は、例えば、並列から直列変換、直列から並列への変換、データ暗号化、および、データフォーマット変換を含んでもよい。
【００３４】
更に、代替ＰＥ４０”は、各ＰＥ４０”へのローカルメモリブロック４８および５２の追加を含む。図３Ａ及び３Ｂからの、ロード経路バス２６及びストア経路バス２６’の両方を含むデータバス３２の詳細を図３Ｃに示す。これらのバスは両方とも、３状態（トライステート）技術を用いるか、多重一方向のバスで実現されても良く、また例えば１６ビット、３２ビット、６４ビットのように、種々のバス幅を持つことができる。例えばアドレスおよびバスプロトコル信号のような様々な制御信号を適宜用いることができる。更に、バス２６及び２６’の各々は、１つがコントローラ２９ａのＤＭＡユニットによって直接的に制御される２つのバスとして実現可能である。コントローラロードバスは、例えば、内部コントローラレジスタの内容をＰＥへロードするために使用可能であり、読取りバスは、例えば状態ビットのような内部ＰＥレジスタの読み取り用に使用できる。コントローラ２９は、コントローラ２９をメモリへ接続するインタフェースライン６１を経てこれらのバスへのアクセスを持つ。ＤＭＡロードバスは、メモリ３３からＰＥローカルメモリ４８へメモリのブロックのローディングに用いられ、ＤＭＡ読取りバスは、ローカルメモリ４８からデータのブロックをメモリ３３に記憶するために用いられる。ＤＭＡ機能はコントローラ２９の一部分であることが好ましい。メモリスイッチ４６は、バス５１と５３およびバス５５と５７を介してＰＥローカルメモリ４８をＰＥレジスタファイル３４へ接続するために用いられる。同様に、メモリスイッチ４６は、バス２６と２６’及びバス５５と５７を介してメモリ３３をＰＥレジスタファイル３４へ接続する。メモリスイッチ制御信号は制御インタフェース５９を経て、ロードおよびストアユニット２８から受け取られる。ロードおよびストアユニット２８は、インタフェース２７を介して命令デコーダ／コントローラ３８からロードおよびストア命令情報を受け取る。この受信した命令情報に基づき、ロードおよびストアユニット２８は、メモリスイッチ４６のためのスイッチ制御を生成する。コントローラ２９からＰＥのアレイに発送される全ての命令は、アレイの各ＰＥ内で同じ仕方で解釈される。この発送されたＰＥ命令は個別ＰＥまたはＰＥのグループへ結合されない。
【００３５】
ＰＥの４×４アレイを図４に示す。それぞれ４つのＰＥを含む４つのクラスタ５２、５４、５６、５８は、図４のアレイに組合わされる。クラスタスイッチ８６及び通信経路８８は、１９９７年６月３０日付けで提出され、参考としてその全体がここに組込み済みである米国係属出願０８／８８５，３１０にさらに詳細に説明された仕方においてクラスタを接続する。ただし、この図において、各処理エレメントは、２つの入力と２つの出力ポートを有する好ましい実施形態として示されているが、クラスタスイッチ内での多重化にための他の層は、各ＰＥに関して入力用として１つ、及び出力用として１つの所定数の通信ポートを装備する。ＰＥ当たり４つの近傍伝送接続部を有する一方向通信の標準トーラスにおいて、すなわち、ＰＥ当たりただ１つの送信方向がイネーブルにされる場合、各ＰＥにおいて、４つの多重化伝送経路が必要とされる。これは、ＰＥの一部分として定義される相互接続トポロジに起因する。最終結果として、標準トーラス内に４Ｎ²個の多数の伝送経路が所在する。マニフォルドアレイにおいて、等価接続性および無制限通信である場合、わずかに２Ｎ²個の多重化伝送通路が必要とされる。マルチプレクサおよび２Ｎ²個の伝送経路によって消費される領域は、４Ｎ²伝送経路によって消費される領域よりも著しく少ないので、このように伝送経路を減少させることは、集積回路の不動財部分を大幅に節減することを意味する。通信経路は、トーラス接続アレイ内の通信方向に対応してＮ、Ｓ、Ｅ、Ｗとラベル付けされる。
【００３６】
完全なクラスタスイッチ８６の一実施の形態を図５の構成図に示す。北、南、東、西方向の出力は既に図示したとおりである。クラスタスイッチ８６には他の多重化層１１２が追加される。この多重化層はＡとラベル付けされた東／南方向の受信と、Ｂとラベル付けされた北／西方向の受信との間で選択し、それによって、各ＰＥの通信ポートの必要条件を受信ポート１つ及び送信ポート１つに減少させる。その上、Ｔとラベ付けされたクラスタ間の転置接続部を介して転置ＰＥ_1,3とＰＥ_3,1の間の多重化された接続が実施される。特定のマルチプレクサに関してＴマルチプレクサイネーブル信号が出力されると、転置ＰＥからの通信は、そのマルチプレクサと連携したＰＥにおいて受信される。
【００３７】
好ましい実施の形態において、全てのクラスタは、例えばＰＥとその転置ＰＥの間の経路のような転置経路を含む。これらの図は、全体の接続スキームを示すものであり、多層集積回路の具体例は、一般な設計上の定例的な選択問題として実施されるルーチンアレイの相互接続を如何にして完全に達成するかを説明することを意図しない。集積回路のレイアウトに際して、ＩＣ設計者は、本発明に係る実際のＩＣにより実現されるアレイを取り入れるプロセスにおいて、各種のトレードオフを分析するであろう。例えば、多数のインタフェースの配線長さを減少させるために、クラスタスイッチはＰＥクラスタ１内に分散させてもよい。
【００３８】
多次元アレイをサポートし、かつ実現を簡素化する４ＰＥクラスタにおける接続性の拡張に必要な多重化の変化を図６のクラスタスイッチ６８６に示す。説明を簡明にするために、別途注記されない限り、単方向性リンクであるものと仮定する。図６におけるマルチプレクサは、各データ経路入力と連携したイネーブル信号を有する。これらのイネーブル信号は、ＳＩＭＤコントローラからの個別信号ラインによって、個別ＰＥ内において受信されて復号され、かつディスパッチ済み命令から、または、スイッチクラスタから間接的に生成可能である。個別制御メカニズムは、ＳＩＭＤコントローラからのディスパッチ済み命令を受け取り、その命令を復号し、多重化イネーブル信号を生成するスイッチクラスタ内に、個別のデコーダ／コントローラメカニズムによって提供され得る。好適な本実施形態においては、クラスタスイッチ多重化イネーブル信号がＰＥ内で生成される。それぞれ４つの４から１への(4 to 1)送信マルチプレクサ、及び４つの３から１(3 to 1)のマルチプレクサが、それぞれ４／１，３／１とラベル付けされ、この好ましい実施形態内に用いられる。
【００３９】
図５に示すクラスタスイッチ５８６までの図６に示す拡張部は、８個の２入力送信マルチプレクサ｛x1,x3,x5,x7,x2,x4,x6,x8｝を、４個の４入力マルチプレクサ４／１により置換えられる。｛Ａ，Ｂ｝および｛Ａ，Ｂ，Ｔ｝とラベル付けされたイネーブル信号と関連する、図５に示す４個の２入力および３個の３入力の受信マルチプレクサは、４個の３入力受信マルチプレクサ３／１によって置き換えられ、送信ラインのゲート／バッファリングがゲート／バッファＢ１－Ｂ８によって追加される。４個の４入力送信マルチプレクサは、クラスタ５２内の４個のＰＥの間で完全な接続性を提供する。図６のクラスタスイッチ６８６は、図５のクラスタスイッチ５８６によって提供される接続性のスーパーセットを表す。クラスタスイッチにおいて、内部配線をレイアウトするには多くの方法があり、図６の表現は接続点を示すが、多層シリコンにより如何にして接続部を実現するかは示さない。
【００４０】
ＰＥクラスタ５２、５４、５６、５８は、図７の構成図における４×４マニフォルドアレイに組織される。送信ラインのゲート／バッファリングは、一般的な場合、即ち、ＰＥクラスタ及びそれらのクラスタスイッチが同一シリコン上に配置されることなく、クラスタ間の信号用配線またはケーブル配置に要求される物理的距離だけ分離される場合に、必要とされる。更に、電力およびレイアウトの観点から、ノイズ、及び電力を減少させるために送信信号をゲート／バッファリングすることが重要であることもあり得る。ただし、本実施形態において、マニフォルドアレイ組織は、単一チップまたは集積回路に組み込まれ、４個のＰＥクラスタから成るクラスタスイッチは、ゲート／バッファリング回路が除去可能であるように、物理的に近接してまとめて配置される。図６のクラスタ組織は、図９Ａのクラスタ９８６Ａにおいて、このバッファリングが除去された状態を示す。
【００４１】
同様に、図７の４×４マニフォルドアレイのバッファリングは、図８Ａに示すマニフォルドアレイ８００Ａの好ましい単一チップ実現のために除去される。４×４マニフォルドアレイ８００Ａが図８Ａに示すように接続される場合には、クラスタ内の各ＰＥは、相互に直交する他の２つのクラスタへ接続可能である。図８Ｂは、４×４マニフォルドアレイ８００Ｂにおける１個のＰＥ、即ちＰＥ_1,3に関する出力送信接続性を示す。４×４マニフォルドアレイ８００Ｂにおける各ＰＥは、そのクラスタ内の別のＰＥに到達可能であり、他の２つのクラスタへ接続可能である。図８Ｃは、アレイ８００Ｃのための４×４ＰＥノード入力（受け取る）接続性を示す。本発明に係る４×４マニフォルドアレイの好ましい一実施形態において、任意の２つのノード間の最大通信距離は２である。
【００４２】
クラスタ９５２内のＰＥを接続するクラスタスイッチ９８６Ｂを含む２×２マニフォルドアレイ９００Ｂを図９Ｂの構成図に示す。この図における任意のＰＥは、クラスタ９５２内のあらゆる他のＰＥと通信可能である。例えば、ＰＥ₀₀はデータを自分自身、ＰＥ₀₁、ＰＥ₁₀、又はＰＥ₁₁に送ることが可能であり、ＰＥ₀₁は、ＰＥ₀₀、それ自身、ＰＥ₁₀、または、ＰＥ₁₁と通信可能であり、当該クラスタ内の他の２個のＰＥに関しても同様である。転置操作に関しては、ＰＥ₀₀及びＰＥ₁₁は何もしないか、ＰＥ₀₁がＰＥ₁₀と通信し、せいぜいこれら自身と通信するに過ぎない。超立方体（ハイパーキューブ）の状況に関して、ＰＥ₀₀はＰＥ_1,1と通信し、ＰＥ_0,1はＰＥ₁₀と通信する。図９Ｂの２×２マニフォルドアレイ９００Ｂから４×４マニフォルドアレイへの移行は、図９Ａにおいてクラスタ５２に関して示すように、４個の２×２を接続するようにマルチプレクサの追加集合を加えることに関連する。図９Ａのクラスタスイッチ９８６Ａは、マルチプレクサ９９０の追加集合を含む。従って、本発明は、プロセッサ、ノード等の相互接続に、高度に柔軟かつスケーラブルな方法を提供することが理解されるはずである。
【００４３】
図１０～図１３の構成図は、マニフォルドアレイ１０００に関するそれぞれの最隣接東、西、北、南通信のためのそれぞれの経路を示す。各経路は矢印によって示される。各マルチプレクサにおけるただ１つの入力経路が、所与の時点においてイネーブルにされる。データ転送を選定された経路上で実施するには、通信命令がコントローラ２９から全てのＰＥへ発信される。ＰＥは、この発信されたＰＥ命令を受け取り、それを復号し、それぞれのそれらレジスタファイル３４から選定済みデータを検索して取り出し、それをそれぞれのそれらクラスタスイッチ８６に送る。図３Ａに示すように、スイッチイネーブル信号は、既にプログラムされている仮想ＰＥ番号およびコンフィギュレーション制御４４出力と組合わされた、受信した命令から選定された通信情報に基づいて作られる。
【００４４】
図１４の構成図において、同じ４×４マニフォルドアレイ１０００に関する転置操作のための通信経路が示される。再び、アクティブなデータ経路は、経路に沿った方向性矢印によって示され、各マルチプレクサに対して、ある時間ではただ１つの入力がアクティブである。スイッチイネーブル信号は、図１０～図１３に関して述べたのと同じ方法で形成される。図１５は、４×４マニフォルドアレイ１５００における４個の独立した１×４線形リング１５５２、１５５４、１５５６、１５５８のための通信経路を示す。１×４線形リングは、行優先順を用いて２×２から形成される。即ち、行優先順は、ＰＥ₀₀（Ａ，Ｂ，Ｃ、または、Ｄ）から、ＰＥ₀₁（Ａ，Ｂ，Ｃ、または、Ｄ）とＰＥ₁₀（Ａ，Ｂ，Ｃ、または、Ｄ）とＰＥ_1,1（Ａ，Ｂ，Ｃ、または、Ｄ）とＰＥ₀₀（Ａ，Ｂ，Ｃ、または、Ｄ）に至る線形経路である。ＰＥ００、０１、１０、１１の集合Ａ－Ｄの各々は、ＰＥの１×４線形リングを構成する。
【００４５】
図１６の構成図は、本発明に係るマニフォルドアレイによって提供される融通性に関する更なる態様を示す。図１６は、２つのアレイとして構成される４×４マニフォルドアレイ１６００用の通信経路を示す。最上２×２×２アレイは「Ａ」ＰＥから成る。最下または「Ｂ」ＰＥは、第２の２×２×２アレイを構成する。図１６は、ｚ軸を介して通信する平面を用いた参照表記法(reference notation)（行）×（列）×（平面）を用いる。ＰＥ間のこの種の通信は一般に、双方向性または単方向性どちらのポートが用いられるかに応じて、３個または６個の通信ポート軸を必要とする。これとは対照的に、好ましいマニフォルドアレイの実施には、ＰＥ当たり１つの入力ポートと１つの出力ポートを必要とするだけである。アレイ１６００は、図１６の相互接続スキームを作成するために、修正済みクラスタスイッチのスイッチ設定を用いて、図１１～１４に示すアレイ１０００の最隣接通信のために用いられたのと同じ物理的配置のＰＥを備えたＰＥ１６５２、１６５４、１６５６のクラスタを使用できることが注記される。本発明に係るマニフォルドアレイ組織の多くの利点の１つは、コンフィギュレーション及び接続方法から強力な新規能力が生じることである。
【００４６】
この強力な能力の更なる一例として、図１７は、図に示すようにクラスタスイッチによって相互接続されたクラスタ１７５２，１７５４，１７５６，１７５８を備えたマニフォルドアレイ１７００の４Ｄ超立方体の具体化例を示す。図１７において、最上ＰＥ番号、例えば０，０又は３，１は、図１及び２のように、トーラスにおけるＰＥの位置を表し、下位のＰＥ番号、例えば００００又は１００１は、超立方体におけるその位置またはアドレスを表す。標準超立方体ＰＥ間通信において、超立方体ＰＥ番号において、ただ１つのビットが変化するだけである。例えば図１において、ＰＥ０１１１（ＰＥ１２）は、ＰＥ００１１、０１１０、１１１１、０１０１と通信する。ここで各個別経路は、超立方体番号における１つのビットだけが変化している。図１７において、同一クラスタ内に位置するのはＰＥとそれらの転置ＰＥだけでなく、ＰＥｓとそれらの超立方体補足ＰＥもその中に位置することが有利である。図７のアレイは、超立方体とその補集合の間の経路を含まない。
【００４７】
図１８は、本発明に係るマニフォルドアレイ１８００を示す。このアレイにおいて、４個のＰＥのクラスタ１８５２、１８５４、１８５６、１８５８の各々におけるＰＥは完全に接続されている。Ｎ個のＰＥのＮ個のクラスタを有するＮ×Ｎマニフォルドの場合、クラスタのグループ化は、１つのｉと１つのｊを選定し、次の論式を用いることによって形成され得る：任意のi,jおよび全ての”ａ”＋∈｛0,1,...,N-1｝に関して：ＰＥ_{(i+a)modN,(j+N+a)modN}。例えばマニフォルドアレイ１８００のような４Ｄ超立方体の場合には、クラスタノードは次のように適切にグレー符号化可能である：ＰＥ_{G((i+a)modN),G((j+N-a)modN}。ここで、Ｇ（ｘ）はｘのグレーコード（交番２進コード）である。一般的な場合への拡張については、次に簡単に説明するマニフォルドアレイの数学的表現において検討することとする。
【００４８】
Ｎ＝４の場合における、超立方体ノードを持つ適当なマニフォルドアレイ１８００を図１８に示す。４×４マニフォルドアレイ１８００は、超立方体補集合を接続する接続経路を含む。換言すれば、超立方体ＰＥとその補足超立方体ＰＥの間の通信経路がイネーブルされる。例えば、ＰＥ０１１１（ＰＥ_1,2）は、ＰＥ１０００（ＰＥ_3,0）並びにそのクラスタの他のメンバと通信可能である。超立方体ＰＥとその補足超立方体ＰＥの間の通信の意味を考察すれば、この場合の４ステップに相当する最長経路用超立方体通信経路は１ステップに短縮される。この経路長短縮は、本発明に係る処理エレメントのマニフォルドアレイ組織に関する非常に効率的な超立方体型アルゴリズムの作成に関して大きい意味を持つ。その上、４個のＰＥで構成される４×４マニフォルドアレイクラスタは、従来技術における折畳みアレイの場合、同様の４Ｄ超立方体接続性のために８個のＰＥで構成されるクラスタを必要とする従来技術における実現と比較すると、ＰＥとその超立方体補集合の間の通信リンクに関して低コストの解決方法を提供する。
【００４９】
ＰＥにおける上部ラベルが４×４×２（行、列、平面）ＰＥ番号であり、底部ＰＥ番号が５Ｄ超立方体番号であるような５Ｄ超立方体１９００を図１９に示す。従来型５Ｄ超立方体の場合、各ＰＥにおいて５個の双方向性、又は１０個の単方向性接続ポートが必要とされる。５Ｄ超立方体が４×４×２マニフォルドアレイにマッピングされる図２０に示すマニフォルドアレイ２０００の場合、各ＰＥにおいて、わずかに１個の単方向性または２個の双方向性ポートが必要とされる。更に、標準超立方体は、合計５Ｎ²（Ｎ＝４）個の双方向性バス又は１０Ｎ²（Ｎ＝４）個の単方向性バスを備えた２⁵、即ち３２個のＰＥを必要とする。図２０の５Ｄ超立方体マニフォルドアレイ２０００は、わずかに合計２Ｎ²（Ｎ＝４）個の双方向性バス又は４Ｎ²（Ｎ＝４）個の、ＰＥの全てのクラスタ間単方向性バスを必要とする。図２０は、各クラスタの間に８個の送信および８個の受信経路を備えた単方向バスの場合を示す。図２０に示すように、超立方体ＰＥとそれらの補集合ＰＥが、ＰＥの同一クラスタ内に所在することが有利であることに注意されたい。その上、ＰＥの各平面に関して、各ＰＥとその最近隣接転置ＰＥは、ＰＥの同一クラスタ内に位置している。更に、各平面からの対応するクラスタエレメントは一緒にグループ化される。このグループ化は、図示されていない６Ｄ超立方体における、クラスタ当たり１６個のＰＥに関しても真であることが保持される。
【００５０】
クラスタスイッチは、５Ｄの場合は４Ｄの場合と異なるが、同じレベルの相互接続性を提供する４Ｄの方法に類似した手法により組み立てられることに注意されたい。マニフォルドアレイ形成技法は、種々のサイズのクラスタを形成可能であることに注意されたい。クラスタサイズは用途および製品の必要条件に応じて選択される。
【００５１】
北、南、東、西、及び、Ｚ軸入力／出力（Ｉ／Ｏ）ポートを備えた３Ｄトーラストポロジは、ＰＥにつき６個の双方向性トライステート型リンクまたは１２個の単方向リンクを必要とする。これは、Ｎ×Ｎ×Ｎの３Ｄトーラスに関して、合計３（Ｎ³）個の双方向性トライステート型リンクおよび６（Ｎ³）単方向リンクが必要とされることを意味する。４×４×４の３Ｄトーラスに関するマニフォルドアレイトポロジは、６Ｄ超立方体に関するマニフォルドアレイトポロジと区別できない。ＰＥは、トーラスまたは超立方体の必要条件に従ってラベル付けされる。更に、８×８トーラスは、接続性必要条件の低下した４×４×４の３Ｄトーラスのサブグラフと見なすことができる。３Ｄ立方体または６Ｄ超立方体トポロジのマニフォルドアレイ実現に際して、ＰＥは１つの送信ポート及び１つの受信ポートのみを必要とし、それぞれ、当該トポロジによって必要とされるポート数とは関係無い。３Ｄ立方体トポロジにおける必要位置へＰＥを配置することは、当該ＰＥにとって外部メカニズムをスイッチングすることによって、適宜取り扱うことが可能である。マニフォルドアレイ３Ｄトーラスに関しては、クラスタ間の配線複雑性は、現在一般的に必要とされる６（Ｎ³）の代りに、３（Ｎ³）リンクまたは（Ｎ³）双方向性トライステート型リンクのわずかに３分の１、および、単方向リンクに関してはわずかに２（Ｎ³）だけを必要とするスイッチングメカニズムにおいて軽減される。これは、実現コストの実質的な減少を表す。
【００５２】
次に、本発明に係るマニフォルドアレイの様々な態様について数学的に説明する。超立方体は、次元につきサイズ２の正規トーラスである。例えば、１つの４次元超立方体は、１つの２×２×２×２トーラスとみなされる。ただし、トーラスが比較的小さい次元である場合についての後続する討論においては埋込み（同相写像）を扱う。２ｄ次元の超立方体は、次元ｄおよび辺長４の正規トーラスに等価であるが、（２ｄ＋１）次元の超立方体は（ｄ＋１）次元および最終次元においてサイズ２である以外は、全次元における辺サイズ４のトーラスに等価である。最初に、ｄが自然数である場合、２ｄ次元超立方体は、次元につきサイズ４のｄ次元正規トーラスに等価である。
【００５３】
２ｄ次元超立方体Ｈは、４^d＝（２²）^dに等しい２^2d個のノードから成る。前記ノード個数は、辺につきサイズ４のｄ次元正規トーラスＴのノード個数である。定義により、Ｈの全てのノードは、各次元につき１ノードの割合で２ｄ個の他のノードに隣接する。Ｔの全てのノードは、次元当たり２個の他のノードに隣接する。即ち、ｄ次元の正規トーラスにおいて、各ノードは他の２ｄ個のノードに隣接する。従って、ＨとＴのノード数およびエッジ数は等しい。
【００５４】
それらの間における一対一の対応を定義するために、（ｉ₁,ｉ₂,...,ｉ_d）をＴのノードであるものとし、ここでｉ_jは次元ｊに関するノード座標を表す。Ｔは辺当たりサイズ４のｄ次元正規トーラスであるので、ｉ_ｊは、１からｄまでの全てのｊに関して０から３までの値をとる。次元ｋにおいて、このノードは、ノード（ｉ₁,ｉ₂,...,ｉ_k-1,...ｉ_d）およびノード（ｉ₁,ｉ₂,..,,ｉ_k+1,...,ｉ_d）に隣接する。ここで、演算ｉ_k-1及びｉ_k+1はモジュロ(modulo)４、即ち、トーラスの循環エッジをカバーするように、３＋１＝０及び０－１＝３として実施されるものと仮定する。
【００５５】
Ｔのノード（ｉ₁,ｉ₂,..,ｉ_d）とＨのノード（（Ｇ（ｉ₁）,Ｇ（ｉ₂）,...,Ｇ（ｉ_d））の間における一対一のマッピングについて考察することとする。ここに、Ｇ（0）＝00、Ｇ（1）＝01、Ｇ（2）＝11、Ｇ（3）＝10は、２数字グレーコード（交番２進符号）である。トーラスノードはタプル(tuple:集合)によりラベル付けされ、超立方体ノードは２進ストリングによりラベル付けされるが、（Ｇ（ｉ₁）,Ｇ（ｉ₂）, ...,Ｇ（ｉ_d））と表記する場合には、実際には、対応する２進ストリングの連結を意味する。この点および一対一マッピングの説明を明瞭にするために、３次元正規トーラスからのノード（３，１，０）および（Ｇ（３）,Ｇ（１）,Ｇ（０））を連結することによって導出される６次元超立方体１００１００に関して対応するラベルについて考察することを提案する。
【００５６】
連続するグレーコードは１つの単一２進数字だけ異なるので、隣接するトーラスノードは同様に隣接超立方体ノードであり、その逆でもある。従って、Ｈのノードとエッジの間、及び、Ｔのノードとエッジの間の一対一マッピングが存在し、２つのグラフが同じであることを意味する。従って、次元２ｄの超立方体は、次元につきサイズ４のｄ次元正規トーラスに埋め込み可能である。
【００５７】
グレーコード（交番２進符号）およびグレーコードを用いた超立方体ノードのラベル表示スキームについての更なる定義に関しては、例えば、参考としてここに組み込み済みのＦ．ＴｈｏｍｓｏｎＬｅｉｇｈｔｏｎ「ＩｎｔｒｏｄｕｃｔｉｏｎｔｏＰａｒａｌｌｅｌＡｌｇｏｒｉｔｈｍｓａｎｄＡｒｃｈｉｔｅｃｔｕｒｅｓ：Ａｒｒａｙｓ，Ｔｒｅｅｓ，Ｈｙｐｅｒｃｕｂｅｓ」（並列アルゴリズム及びアーキテクチャ入門：アレイ、トリー、超立方体）ＭｏｒｇａｎＫａｕｆｌｎａｎｎ、１９９２年、Ｃｈ．３を参照されたい。
【００５８】
（２ｄ＋１）次元の超立方体は、少なくともサイズ２を除く全ての次元に関してサイズ４の（ｄ＋１）次元トーラスに等価である。Ｌｅｉｇｈｔｏｎ資料から、（２ｄ＋１）次元の超立方体は、ページ３９３で検討されているように、接続されるそれらの対応するノードを持つ２つの２ｄ次元超立方体とみなすことができることが分かる。しかし、２ｄ次元の超立方体は、辺につきサイズ４のｄ次元正規トーラスに等価であるので、それらの対応するノードを接続することによる２つのｄ次元トーラスの併合集合は、最後の次元に関してサイズ２の（ｄ＋１）次元トーラスである。
【００５９】
上記の検討から、２ｄ次元の超立方体は、次元ｄおよび辺長４の正規トーラスに等価であることが理解されるはずである。同様に、（２ｄ＋１）次元の超立方体は、サイズ２の最後の次元を除く全ての次元において辺サイズ４の（ｄ＋１）次元トーラスに等価である。
【００６０】
マニフォルドアレイグループ又はクラスタは、次に示すように、一般に、直径的に対面するノードを形成することが好ましい。ｄ次元超立方体の隣接するノードは、１つの単一２進数字だけが異なるので、それらのノードアドレスにおいて厳密にｄ数字だけ異なるノードは相互に最も遠く離れて所在し、それらは相互に直径的に対面する。最も遠く離れたノードのアドレスは、相互に２進補数である。従って、１つの所与ノードに直径的に対面するノードを、その補集合とも称する。
【００６１】
一例として、１つの２次元４×４トーラス、及び、図２１Ａに示すように、超立方体ノードラベルを付けた４×４の表として表記される対応する埋込み済み４次元超立方体について考察することとする。この表の行および列に沿った隣接エレメント間距離は１である。列２、３、４が１つの位置だけ上方回転された場合、第１と第２列の間の対応するエレメントの距離は２になる。列３及び４、次いで列４に対して同様に反復することにより求められる隣接列の対応エレメントを持つ列のエレメント間距離は２である。結果として得られる４Ｄマニフォルドアレイの表を図２１Ｂに示す。
【００６２】
その表の各列は、４個のノードで構成される１つのグルーピング、又は、換言すれば、４次元超立方体上の最大距離は４であるので、直径的に対面する２対のノードを含むことが重要である点に注目されたい。直径的に対面する超立方体ノードが同じグループに属する場合には、その表の列がグループを定義する。
【００６３】
比較的高い次元のトーラス、そして超立方体において、直径的に対面するノードのグルーピングは、最後の次元を除く各新規次元に沿った同じ回転によって達成される。
【００６４】
グループ形成のための置換を数学的に表記するために、テンソル多次元アレイを分解し、そのエレメントからベクトルを作るか、その逆を実施する２つの演算子が定義される。ｖｅｃ（）演算子は、単一のアーギュメント、即ち、テンソルＴをとり、テンソルの第１次元である列に沿ってＴのエレメントを積み重ねることによりベクトルを以下の式で返す。
【００６５】
【数１】

【００６６】
例えば、Ｔが２次元テンソルである場合には、ｖ＝ｖｅｃ（Ｔ）＝［11 21 31 12 22 32 13 23 33］^T である。一方、テンソルＴは、アーギュメントとしてソース構造および次元のリストをとる演算子ｒｅｓｈａｐｅ（）を用いることにより、ベクトルｖから復元される。最後の例から、Ｔは、ｒｅｓｈａｐｅ（v,3,3）を用いて再構築される。
【００６７】
２つのマトリックスＡとＢのクロネッカー積は、Ａの対応エレメントによって基準化されたＢのコピーから成るブロックマトリックスである。即ち：
【００６８】
【数２】

【００６９】
所要のグルーピングを表わすための多重アレイＴの操作は、マトリックスが順列マトリックスであり、行、列、及び、ベクトル当たり厳密に１つの単一ノンゼロエレメントを持つ直交マトリックスで、ベクトルがｖｅｃ（Ｔ）である場合における、マトリックス・ベクトル積として定義される。先ず、マトリックスＳを求めるために、サイズ４の上回転順列マトリックスが決定される。
【００７０】
【数３】

【００７１】
同様に、マトリックスＧ、即ち、実際にグルーピング置換を実施するブロック対角マトリックスが決定される。Ｇの対角ブロックはＳのべき乗（パワー）である。
【００７２】
【数４】

【００７３】
Ｔが４×４トーラスである場合において、ｒｅｓｈａｐｅ（Ｇｖｅｃ（Ｔ），４，４）は、上述の要求されるグルーピング特質を有する結果として得られるトーラスである。同様に、Ｔが４×４×４トーラスを表す場合において、要求されるグルーピングを定義する演算を次に示す：
【００７４】
【数５】

【００７５】
ここで、Ｉ₄は４×４識別マトリックスである。
【００７６】
一般に、１次元につきサイズ４のｄ次元正規トーラスＴの場合における、グループ現示置換を次に示す：
【００７７】
【数６】

【００７８】
グルーピング置換えを４×４×４トーラスに適用する例を次に示す：
（Ｉ₄×Ｇ）による第１マトリックス乗算後の、４つの平面を次表に示す：ここで×はクロネッカー積を示す。
【００７９】
【表１】

【００８０】
（Ｇ×Ｉ_４）による第２マトリックス乗算後の結果を次表に示す：
ここで×はクロネッカー積を示す。
【００８１】
【表２】

【００８２】
上回転の代りに下回転した場合には、直径的に対面するノードをまとめるという同じグルーピング特質が維持される。更に、ノード（i,j）がその転置対，ノード（j,i）と共にグルーピング化される場合には、そのグループはノードの対称対を含む。数学的には、下回転置換は上回転置換の転置である。同様に、順列マトリックスが直交する場合には、下回転置換は上回転置換の逆である。更に明確に、サイズ４の下回転順列マトリックスを次に示す：
【００８３】
【数７】

【００８４】
ここに、サイズ４に関しては一切制約されないので、マトリックスのサイズについて言及することが必要であり、あらゆるサイズの２次元トーラス、又はより高い次元のトーラスの２次元サブグラフに回転を適用できる。同様に、対角線ブロックがＳ^Tのべき乗（パワー）である場合には、全ての列に対応する回転を適用するために、マトリックスＧの転置を決定する。
【００８５】
図２１Ｃに示す辺当たりサイズ４の３次元正規トーラスの前例に関して、第１マトリックスに（Ｉ_４×Ｇ^T）を乗算することによって得られる４つの平面を次に示す：ここで×はクロネッカー積を示す。
【００８６】
【数８】

【００８７】
【表３】

【００８８】
前述のグルーピングは、Ｚ軸からの斜視図として図２２および図２３に示される。第２マトリックスに（Ｇ^T×I₄）を乗算することによって得られる結果を次に示す：ここで×はクロネッカー積を示す。
【００８９】
【表４】

【００９０】
この場合、直径的に対面するノードが第三次元、即ち、図２４に示すように異なる平面内の同じ位置に沿ってグループ化されるばかりでなく、最初から２つの次元に関して対称的なノードも平面の第２の次元または行に沿ってグループ化される。図２４においては、１つのグルーピング８９がハイライトされている。グルーピング８９は、図のその次の集合に関する基準点として用いられる。図２５は、クラスタの間で面が所有する接続性に基づいてＡ、Ｂ、Ｃ、Ｄ平面を再整列する。図２６は、サブクラスタの間の局部接続性に基づいて、各平面を２×２サブクラスタに分割する。グループ８９は、平面Ａ内のサブクラスタとして示される。この段階においてマニフォルドアレイコアアーキテクチャは、図２７Ａに示すように、識別された２×２サブクラスタの各々を直接交換するために用いられる。４×４×４のＰＥノードＰＥ_2,2,2入力（受信）接続性を図２７Ｂに示す。マルチプレクサの追加集合は、ラベルｘｘ１、ｘｘ２、ｘｘ３が追加されていることに注意されたい。４×４×４の各４×４マニフォルドアレイ部分集合の場合には、追加されたｘｘ＃型の１６個のマルチプレクサの追加集合がある。これらのマルチプレクサは全て、ハイライトされたＰＥノード２、２、２に関して、図２７Ｂに示されると同じ仕方において接続される。
【００９１】
ノードの同じグルーピングは、異なる置き換え順序を経て到達可能であることに注意することが重要である。以上に示したステップにおいて必要とされた置き換えを一緒に乗算する結果として得られる順列マトリックスをＰとする。このマトリックスのあらゆる因数分解は、同じ結果を達成する異なる順序のステップに対応する。例えば、Ｐ＝Ａ₁Ａ₂Ａ₃を仮定する。ランダム順列マトリックスＱ、Ｒについて考察することとする。順列Ｐのようなノードの同じグルーピングを達成する一連の異なる順列を得ることができる。例えば、Ｐ＝Ａ₁Ｑ^TＱＡ₂Ｒ^TＲＡ₃であるので、Ｂ₁＝Ａ₁Ｑ^T、Ｂ₂＝ＱＡ₂Ｒ^T、及び、Ｂ₃＝ＲＡ₃と命名して、Ｐ＝Ｂ₁Ｂ₂Ｂ₃を得ることができる。更に、グループのエレメント、又は、グループの相対的順序付け、又は、両方の置換えを実施し、実質的に同じであるが異なって見えるノードのグルーピングに到達できる。
【００９２】
同様に、本発明に係るネットワークに基づくマニフォルドアレイの特質は、更に次に検討するように、多くの利点を有するネットワークを形成するためにノードを接続することにも有利に適用できる。
【００９３】
ネットワークの直径は、ノードの任意の対の間の最大距離である。ネットワークの直径は、２つのノード間通信に必要な最悪場合数のステップを含む。直径が小さければ小さい程、遠く離れたノード間通信に必要とされるステップ数は少なくなる。ネットワークの直径は小さいことが望ましい。ｄ次元超立方体の場合、Ｈ’は相補ノードを接続するエッジをＨに加えることによって生成される新規グラフである。ｓ及びｔはＨの２つの相補ノードであり、ｖはＨの他の任意のノードであるものとする。相補超立方体ノードの任意の対から任意の超立方体ノードｖまでの距離の和は、超立方体の次元に等しいことが実証できる。即ち、相補ノードｓとｔ、及び、ノードｖを所与の１対であるとすれば、ｖからｓとｔを通る最短経路がある。
【００９４】
ｓからｖまでの距離は、ｓとｖの２進表現の差、例えばｋである数字の個数に等しい。ｔはｓの補集合数であるので、ｔとｖの２進表現の差に相当する数字の個数は（ｄ－ｋ）に等しい。従って、ｓからｖまでの距離はｋであり、ｔからｖまでの距離は（ｄ－ｋ）である。すなわち、２つの距離の和はｄである。更に、ｓからｖを経たｔまでの経路は長さｄであり、これが最短経路である。
【００９５】
更に、ｄ次元超立方体の相補ノードを接続するエッジを追加すればグラフの直径を、ｄが偶数であれば半分に、ｄが奇数であれば（ｄ＋１）／２に減少させることができる。ｖをＨのノードとして定義すれば、ｋおよび（ｄ－ｋ）は、Ｈの２つの相補ノードｓとｔからのそれぞれの距離である。一般性を失うことなしに、ｋ＜（ｄ－ｋ）と仮定する。そうすれば、Ｈの場合と同じ最短経路を使用できるので、Ｈ’におけるｓからｖまでの距離はｋである。新規エッジを経てｓを通る経路が相補ノードを接続するので、Ｈ’におけるｔからｖまでの距離は（ｋ＋１）である。これは、Ｈ’のノードｖとｓのあらゆる対に関して、それらの距離は、ｄが偶数であればｄ／２、又は、ｄが奇数であれば（ｄ＋１）／２を超過し得ないことを意味する。Ｈにおけるｓからｖまでの距離が（ｄ＋１）／２を越える場合には、Ｈ’におけるｓの相補ノードｔを通る最短経路は、ｄ／２未満の長さである。
【００９６】
ｄ次元超立方体のネットワークの直径はｄであり、相補ノード接続部の追加により、上記のように［ｄ／２］になる。前述の結果を下表に要約する。エッジ接続相補ノードだけが中央列において取り扱われることに注意されたい。第３列ラベル付けされたマニフォルドアレイは、本発明のこの態様に基づく構造に含まれるエッジの個数並びに２の一定ネットワーク直径を示す。
【００９７】
【表５】

【００９８】
上記の表は、超立方体ネットワークの相補ノードを接続する超立方体より多くの２^d-1個のエッジを含むサブグラフが劇的な改良を起こすことを示す。ネットワークの直径は、超立方体に比較して、その元のサイズの半分に短縮される。本発明に従い上記の第３列に示すように、全個数のマニフォルドアレイエッジを備えている場合には、ネットワークの直径は、全てのｄに関して一定な直径２に短縮される。超立方体および相補エッジを備えた超立方体は、マニフォルドアレイの適当なサブグラフである。
【００９９】
仮想ノードのエミュレーションは次のように実現可能である。より小さいネットワークによってエミュレートされることが必要な高次元ネットワークがあるものと仮定する。この必要条件は、多重仮想ノードが各物理的ノードによってエミュレートされなければならないことを意味する。エミュレーションが超立方体近傍並びに超立方体ネットワーク上の超立方体補集合および２次元トーラスネットワーク上のマトリックス転置を維持するように、仮想ネットワークを物理的ネットワークへマップするための幾つかの方法が以下に呈示される。超立方体エミュレーションは比較的簡単に達成可能である。ｑ次元の小さい方の超立方体にエミュレートすることが必要なｄ次元超立方体を仮定する。次に、２^d-q個の仮想ノードが、各物理ノードによってエミュレートされなければならない。本発明に係る方法を非常に簡単に説明する方法は、ノードの２進アドレスについて考察することである。ｄ次元超立方体ノードは、ｄ桁の数字による２進アドレスを必要とする。それらｄ桁の数字のうちのｑ桁の数字がエミュレーションを実施する物理ノードのアドレスを定義し、残りの（ｄ－ｑ）桁の数字が物理ノード内のローカル仮想ノードＩＤを定義する。実際には、ｄ桁の数字アドレス

を持つ仮想ノードｖに関して、このアドレスの最初のｑビットは、仮想アドレスのローカルＩＤセクションによって区別される２^d-q個の仮想ノードのグループをエミュレートする物理ノードのＩＤを示す。ｖのあらゆる隣接ノードｗは、ｖのアドレスと単一の数字だけ異なる。この数字は、仮想ＩＤの最初のｑ個の数字のなかのいずれか１つであり、従って物理ノードの近隣に所属するか、または、ｗのアドレスは（ｄ－ｑ）個のローカル数字のなかの１つだけ異なり、従って同じ物理ノードによってエミュレートされることを意味する。更に、仮想ノードｖの補集合は、仮想アドレスの補数が物理アドレスおよびローカルアドレスの補数の連結に等しいので、ｖを賄う(host)物理ノードの補集合によってエミュレートされる。相補物理ノードは、マニフォルドアレイ内の同じクラスタに属するので、相補仮想ノードも同様に同一クラスタに属する。
【０１００】
一般に、仮想ノードＩＤは、必ずしも隣接していない物理およびローカルノードＩＤの２つの部分に有利に分割可能である。仮想ノードの隣接ノードは、ＩＤの物理またはローカル部分のどちらかが異なる１つのノードＩＤを持つはずである。従って、仮想ノードは、それぞれ物理ノードの隣接ノード、又は同じ物理ノードによってエミュレートされる。更に、仮想ＩＤの補集合はローカルおよび物理ＩＤの補集合に等しいので、仮想ノードの補集合は、マニフォルドアレイ上の隣接でもある物理ノードの補集合によって常にエミュレートされる。
【０１０１】
その代わりに、小さい方の超立方体が大きい方の超立方体によってエミュレートされる場合には、マニフォルドアレイネットワークは帰納的に定義されるので、全てがマニフォルドアレイのサブセットに予測通りに作用する。これは、前述の論理が保持される場合には、エミュレートされる超立方体に等しいサイズのマニフォルドアレイのサブグラフが存在することを意味する。
【０１０２】
同じ概念がトーラスのエミュレーションに有効であるので、トーラスエミュレーションも同様に容易に扱うことができる。隣接して選定された仮想ノードＩＤ（次元当たり）は、物理およびローカルＩＤに相当する。物理ノードＩＤが仮想ノードＩＤの最上位ビットを含む場合には、仮想ノードがブロック分布している。そうではなくて、物理ノードＩＤが仮想ノードＩＤの最下位ビットを含む場合には、仮想ノードが循環分布している。ブロック分布の場合には、連続するＩＤを持つ仮想ノードのグループは、同じ物理ノードによってエミュレートされる。１６個の仮想ノードが４個の物理ノード上にブロック分布している場合には、物理ノード０が仮想ノード０、１、２、及び、３をエミュレートし、物理ノード１が仮想ノード４、５、６、及び、７をエミュレートする等々である。循環分布の場合には、連続ＩＤを持つノードのグループが異なる物理ノードによってエミュレートされる。１６個の仮想ノードが４個の物理ノード上に循環分布している場合には、物理ノード０が仮想ノード０、４、８、及び、１２をエミュレートし、物理ノード１が仮想ノード１、５、９、及び、１３をエミュレートする等々である。
【０１０３】
仮想アドレスに対して１を加算または減算することにより、指定された次元に沿ったこのノードの隣接ノードが見付けられる。この加算／減算は、仮想アドレスのローカルまたは物理部分のどちらか、又は、両方に１を加算／減算することに等価であり、同じ物理ノード又は隣接物理ノードのどちらかによって隣接仮想ノードがエミュレートされることを保証する。転置仮想ノードが、同じ物理ノード、又は隣接物理ノードによってエミュレートされることを保証するために、仮想アドレスの物理およびローカルセクションの割当は、全ての次元に関して同じでなければならない。すなわち、仮想ノードのブロック―ブロックまたは循環―循環分布は、転置の近隣性を保存する。
【０１０４】
並列マシンにおける超立方体マニフォルドアレイの例に戻って、データの配置は、アルゴリズムの高性能計算に関して最高の重要性を持つ。アレイプロセッサにおいては、処理エレメント間のデータ移動に起因する待ち時間を最小限化するために、最初データを適当なＰＥ内に配置し、計算期間中に、直接接続されたＰＥ間で移動させる。従って、全アルゴリズムに関して全体の通信待ち時間を最小限化するために、アルゴリズムがその計算段階を経て進行するにつれて、データの移動が最適化される必要がある。マニフォルドアレイの能力を実証するために、完全なシャッフルアルゴリズム及びＰＥとその超立方体補集合間の通信アルゴリズムが、図２８Ａ～図３０に示す４×４マニフォルドアレイ２８００上で調査されるはずである。テンソル積代数は、完全なシャッフルアルゴリズムをマニフォルドアレイプロセッサ上にマップするために用いられる。
【０１０５】
テンソル積代数はクロネッカー積とも呼ばれ、数学方程式を目的のマシンアーキテクチャへのアルゴリズム的コーディングに適したマトリックス形式にマッピングするための方法を表す。例えば、Ｊ．Ｇｒａｎａｔａ、Ｍ．Ｃｏｎｎｅｒ、Ｒ．Ｔｏｌｉｍｉｅｒｉ「The Tensor Product: A Mathematical Programming Language for FFTs and other Fast DSP operations」（テンソル積：ＦＦＴおよび高速ＤＳＰ演算のための数学的プログラム言語）ＩＥＥＥＳＰマガジン、ｐｐ．４０－４８、１９９２年１月、及び、Ｊ．Ｒ．Ｊｏｈｎｓｏｎ、Ｒ．Ｗ．Ｊｏｈｎｓｏｎ、Ｄ．Ｒｏｏｄｒｉｇｕｅｚ、および、Ｒ．Ｔｏｌｉｍｅｉｒｉによる「A Methodology for Designing, Modifying, and Implementing Fourier Transform Algorithms on Various Architectures」（各種アーキテクチャにおけるフーリエ変換アルゴリズムの設計、修正、および実行のための方法論）回路システム信号プロセスＶｏｌ．９、Ｎｏ．４、ｐｐ．４４９－５００、１９９０年を参照のこと。これらの論文は両方とも参考としてここに組み込み済みである。
【０１０６】
マニフォルドアレイ完全シャッフル例のためのテンソル表記法による完全シャッフルは、Ｊ．Ｒ．Ｊｏｈｎｓｏｎ等による参考資料のｐ．４７２に用いられている

によって表される順列マトリックスとして定義されている。順列マトリックスは、特定マシン組織に対してロード又はストアされるべきデータにアクセスするためのアドレッシングメカニズムを定義すると一般的に解釈される。一般に、順列マトリックスは、その次に意図された計算的オペレーションに関して、データを適切な場所に置くために必要なデータの移動を表す。従って、データの移動、即ち順列マトリックスの目標アーキテクチャへのマッピングを最適化することが重要である。マニフォルドアレイ組織に関する、単一命令多重データ処理（ＳＩＭＤ）超立方体マシンとしての演算、即ち、完全シャッフルは、アレイ内にデータが適切に配置されれば容易に実行され得る。

ｎ＝５（Ｐ³²₁₆）の完全シャッフル例は、図２８～図３３を用いて記述される。図２８Ａは、完全シャッフルアルゴリズムを記述するために用いられるバス構造および演算ユニットを示す。図２８Ａには、多重コントローラ、メモリユニット０～３、および、特殊目的ＦＩＦＯバッファが含まれる。この組織の好ましい実施形態では、メモリユニット、コントローラ、および、ＦＩＦＯバッファがＰＥのアレイと同じチップ上に配置される。ただし、本発明は更に一般的であり、単一チップの実現を越えるものであることを理解されたい。マニフォルドアレイコンセプトは、マイクロプロセッサチップＰＥのアレイによって、ケーブル付きバス、外部メモリ、および、外部コントローラと共に容易に使用可能である。この検討のために、この種マシンのファミリ全体に亙ってスケーラブルであると定義される単一アーキテクチャ及びマシン組織を可能にする単一チップ高性能アレイプロセッサが記述される。
【０１０７】
従って、低コストのために、コントローラ、メモリユニット、例えばＦＩＦＯのようなデータバッファ、および、ＰＥは、全て単一チップに含まれる。コントローラは、それらのアレイクラスタ、メモリ、および、Ｉ／Ｏ機能へ、例えばメモリアドレス及びロード／ストア信号のような制御信号を介して、または、命令バス上で、例えば、ＰＥに送られるディスパッチされた命令を介して制御を提供する。コントローラは、それぞれＳＩＭＤマシンにおける１つの一般的な機能ユニットであり、後続アルゴリズムのサポートという観点からのみ記述される。図２８～図３０において、特殊目的ＦＩＦＯバッファとして示されるデータバッファは、一般に、メモリ／直接メモリアクセス（ＤＭＡ）インタフェースユニットに同様に組み込まれ、この場合にも、ここではただ一般的にのみ記述される。
【０１０８】
図２８Ａは、クラスタ化されたＰＥの再構成可能なトポロジをサポートするために、多重コントローラがどのようにして適宜実行されるかを実証する。図２８Ａにおいて、コントローラは、４個のＰＥの各クラスタと連携する。他のスキームが使用可能であるが、コントローラ０はマスタコントローラとみなされる。命令バスＩ０は、それ自身のクラスタ、並びに、他のコントローラの各々と連携した命令スイッチ（ＩＳＷ）に接続される。図２８Ａにおける各Ｉｓｗは、命令バスＩ０のための出力Ｃ、または、コントローラの入力命令バスＩ１、Ｉ２、または、Ｉ３からそれぞれのＩｓｗの出力Ｃへの接続経路をイネーブルする。Ｉｓｗは、マスタコントローラによって直接または間接的に供給される制御信号を用いて構成される。マスタコントローラも同様に、システム含まれ、かつこの種の情報を提供するように命じられた、例えばホストプロセッサのような他のプロセッサから、この情報を直接的または間接的に受け取る。この完全シャッフルの例のために、ＩｓｗはＩ０を全ての命令バス経路に接続するように設定される。これによって、コントローラ０は、図２８Ａに示すように、４個全てのＰＥクラスタ２８５２、２８５４、２８５６、２８５８のために、単一コントローラとして作動する。例えば、メモリサブシステムをデータソースへ接続する外部インタフェース経路を図２８Ａに示す。
【０１０９】
一例として、図２８Ｂの底部において始まる、ＦＩＦＯアドレス当たり８個のデータアイテムで構成されるグループとしてオンチップＦＩＦＯへ受信される一連のデータアイテムを示す。このアドレスは、ＦＩＦＯ内の各列の最上部に表示される。図２８Ｂに示すように、データ項目｛０－７｝の第１グループはＦＩＦＯ－０に記憶され、その次のグループ｛８－１５｝はＦＩＦＯ－１に記憶される、等々。この例において、ＦＩＦＯは、次の図２９に関連して次に記述される様式においてデータをロードするためのコントローラ、即ちこの例においてはコントローラ０、または、ローカルバッファ制御機能によってイネーブルされる４個のマルチプレクサに、各列データアイテムに対して１つずつ合計８個の出力経路を供給する。図２８Ｂにおいて、図示される各バス、Ｄ０、Ｄ１、Ｄ２、Ｄ３はトライステート双方向性バス、又は、個別的にロードおよび個別的にストアするバスであり得る。１つ又は複数のバスは、意図した用途に適合する任意のデータ幅、一般に８ビット、１６ビット、３２ビット、または、６４ビットであり。ただし、他の幅であっても差し支えない。
【０１１０】
説明を明瞭にするために、ＰＥクラスタ間の相互接続は図示しない。図３Ａ～３Ｃの基礎メモリブロックは、超立方体パターンにおけるデータ配置をサポートし、クラスタへのデータインターフェイス帯域を増大するために、図２８の４×４マニフォルドアレイ２８００におけるＮ＝４のメモリブロックに拡大されている。メモリブロックは０－３にラベル付けされ、バス経路はクラスタ当たり１つに整理されている。例えばデータバスＤ０を備えたメモリ０は、クラスタＡ２８５２ＰＥ｛（０，０）、（３，１）、（１，３）、（２，２）｝へ接続され、データバスＤ１を備えたメモリ１は、クラスタＢ２８５４ＰＥ｛（３，２）、（０，１）、（２，３）、（ｌ，０）｝に接続される等々。他のバス構造が可能であり、この典型的な記述によって排除されないことに注意されたい。
【０１１１】
ＦＩＦＯバッファにデータがロードされた場合、図２９に示すように、プロセスのその次のステップは、データを内部メモリ０－３（Ｍ０、Ｍ１、Ｍ２、Ｍ３）へロードする。この記述のために、データは３２ビット、データバスは３２ビットであるものと仮定する。次に示すシーケンスにおいて、一時に４個のデータアイテムを並列ロードするために、表記法メモリ―データアイテム又はＭｘ-ａを用いた８回のＦＩＦＯからメモリへのロードサイクルが用いられる。図２９に示すメモリユニットへロードされるデータパターンを生成するために用いられるシーケンスは、１^st（Ｍ０－０、Ｍ１－１、Ｍ２－３、Ｍ３－２）、２^nd（Ｍ０－６、Ｍ１－４、Ｍ２－５、Ｍ３－７）というように、これが８^th（Ｍ０－３１、Ｍ１－３０、Ｍ２－２８、Ｍ３－２９）まで続く。例えば、メモリ２（Ｍ２）は、図２９に示す囲まれたアイテム５７によって示されるＦＩＦＯラインからデータがロードされる。ここで、メモリデータはＰＥアレイ２８００にロードされなければならない。メモリブロックはアドレスされ、コントローラ０によって制御される。ＰＥへデータをロードするために、コントローラ０は、命令をＰＥへディスパッチし、それらのデータバスからデータがロードされるべきであること、および、ＰＥ内部のどの場所へ当該データがロードされるべきかを通知する。次に、コントローラ０は、同期して、アドレスをメモリブロックに供給する。この場合には４個のメモリ０－３の各々に関して同じアドレスである。このアドレスと同期して、次に、コントローラ０は、アドレスされたロケーションからデータを読み出すため、またそのデータをメモリユニット自体のデータバスに配置するために、メモリユニットにとって必要な信号を生成する。
【０１１２】
同期を保って、適当なＰＥｓは、それらのデータバスからデータを取り、コントローラ０からディスパッチされた命令による指定に従って、それをロードする。コントローラ０は適当なＰＥの選択を識別する。この選択は、コントローラがＰＥへ送るディスパッチされた命令内の識別を介して、または、ＰＥ内に位置するプログラム可能なイネーブル／ディスイネーブルビットを介して、等、幾つかの方法で実施できる。コントローラは、この結果を達成するために、一連のＰＥロード命令を命令バスを介して各ＰＥへディスパッチする。３２データをロードするために、表記法：メモリユニット―データアイテム―ＰＥ＃によって示される順序で並列に、ロードサイクル当たり４個のデータアイテムで、合計８回のメモリからＰＥへのロードサイクルが用いられる。図３０に示すＰＥにロードされるデータパターンを生成するために用いられる順序を次に示す：１^ｓｔ（Ｍ０－０－ＰＥ_0,0，Ｍ１－１－ＰＥ_0,1，Ｍ２－３－ＰＥ_0,2，Ｍ３－２－ＰＥ_0,3），２^ｎｄ（Ｍ０－６－ＰＥ_1,3，Ｍ１－４－ＰＥ_1,0，Ｍ２－５－ＰＥ_1,1，Ｍ３－７－ＰＥ_1,2），３^ｒｄ（Ｍ０－９－ＰＥ_3,1，Ｍ１－１１－ＰＥ_3,2，Ｍ２－１０－ＰＥ_3,3，Ｍ３－８－ＰＥ_3,0），４^ｔｈ（Ｍ０－１５－ＰＥ_2,2，Ｍ１－１４－ＰＥ_2,3，Ｍ２－１２－ＰＥ_2,0，Ｍ３－１３－ＰＥ_2,1），図３０に示すように３２個のデータアイテムがＰＥアレイにロードされるまで継続する。データアイテムが正しい順序で読みとられた場合には、このロードパターンは完全シャッフルを実施する。完全シャッフル演算を順々に３２のデータリストに実行することを図３１に示す。
【０１１３】
Ｘ＝（Ｐ³²₁₆）（Ｐ³²₁₆）（Ｐ³²₁₆）（Ｐ³²₁₆）（Ｐ³²₁₆）Ｘが知られている。この方程式は、マニフォルドアレイ上での通信事例を示すために用いられる。Ｘの第１順列、即ち３２―エレメントベクトルは、図３０に示すように、ロード操作によって達成される。次の順列は、４つの隣接方向の各々に関して次のリストに定義済みであるように、ＰＥの隣接対の間のス北ワップ演算によって実施される。
・東スワップ {0,0 ＆ 0,1}, {0,2 ＆ 0,3}, {1,0 ＆ 1,1}, {1,2 ＆ 1,3},
{2,0 ＆ 2,1}, {2,2 ＆ 2,3}, {3,0 ＆ 3,1}, {3,2 ＆ 3,3},
・南スワップ {0,0 ＆ 1,0}, {2,0 ＆ 3,0}, {0,1 ＆ 1,1}, {2,1 ＆ 3,1},
{0,2 ＆ 1,2}, {2,2 ＆ 3,2}, {0,3 ＆ 1,3}, {2,3 ＆ 3,3},
・西スワップ {0,0 ＆ 0,3}, {0,1 ＆ 0,2}, {1,0 ＆ 1,3}, {1,1 ＆ 1,2},
{2,0 ＆ 2,3}, {2,1 ＆ 2,2}, {3,0 ＆ 3,3}, {3,1 ＆ 3,2},
・北スワップ {0,0 ＆ 3,0}, {1,0 ＆ 2,0}, {0,1 ＆ 3,1}, {1,1 ＆ 2,1},
{0,2 ＆ 3,2}, {1,2 ＆ 2,2}, {0,3 ＆ 3,3}, {1,3 ＆ 2,3},
スワップ演算は、指定されたＰＥ間におけるレジスタデータ値の交換を引き起こす。交換するレジスタ値の選択は、各ＰＥにおいて受信されたディスパッチ命令に定義されている。この例の場合には、一方のＰＥにおけるレジスタＲ１は、もう一方のＰＥにおけるレジスタＲ２と交換またはスワップされる。図３１は完全なシャッフルシーケンスを示し、ＰＥの超立方体番号およびそれらに含まれるレジスタＲ１及びＲ２を列形式においてリストする。スワップ（方向）命令によって分離された各列は、スワップ演算の結果を示す。図３１に示すように、完全なシャッフルは、対構成されたＰＥの間におけるただ１回の最隣接データ移動の単一サイクルのみを必要とする各スワップ演算において実施される。
【０１１４】
この記述を更に拡張するために図３２及び３３が提供される。図３２は、ＰＥにディスパッチされた北スワップ命令の完了に際して得られるレジスタ結果を示す。図３３は、ＰＥにディスパッチされた南スワップ命令の完了に際して得られるレジスタ結果を示す。西スワップと東スワップは同様の仕方において処理される。この記述された事例の重要性は、データが指示通りの超立方体パターンでロード可能であれば、データの完全シャッフルを必要とする多くのアルゴリズムにとって、マニフォルドアレイ２０００において非常に高速の処理が得られることである。
【０１１５】
最後に、マニフォルドアレイ超補足事例について記述する。この例においては、上記の完全シャッフル事例において指示されたようなスワップコマンドを用いて、超立方体ＰＥと上述したそれらの補足超立方体ＰＥとの間におけるレジスタ値の交換が実施される。超立方体ノード当たり単一のＰＥが存在するものと仮定すれば、超補足集合は超立方体マシンにおける最長経路に最適短縮を提供する。図１８は、接続されたＰＥ間における簡単な交換が１つの単一サイクルにおいて発生可能にするために超補足集合によって用いられる経路を示す。
【０１１６】
本発明は特定の好ましい実施形態および典型的なアプリケーションについて記述したが、本発明が多数のアプリケーションに適用可能であり、添付特許請求の範囲によってのみ限定されることが理解されるはずである。一例として、本実施形態は処理エレメントのクラスタを扱うが、ノードのクラスタも考慮対象とされる。この種のノードは、記憶されている多重ブロックのデータへの同時アクセスを可能にするタイル状のメモリシステムを形成するためのメモリエレメントであってもよい。更に、ノードは、接続ポート、入力／出力デバイス等であってもよい。一例として再度記述すれば、ノードは、通信ネットワークにおける複数の通信チャネルを接続するものでも良い。

【特許請求の範囲】
【請求項１】
Ｎ×Ｍアレイに接続された複数の処理エレメント（ＰＥ）用相互接続システムであって、ここにＮとＭは両方とも１より大きく、各ＰＥはデータ及びコマンドを送受信するための通信ポートを備えＰＥはクラスタにグループ化された相互接続システムにおいて、
ＰＥ間接続経路と、
クラスタの間の排他的なＰＥ間接続経路を相互に組み合わせ、従来型トーラス接続ＰＥアレイの接続性に等価なＰＥ間接続性を提供するために必要な通信経路の個数を実質的に減少させるように前記ＰＥへ接続されたクラスタスイッチとを有し、
前記クラスタスイッチが更に転置ＰＥ間および超立方体補足ＰＥ間に直接通信を提供するための接続部を有することを特徴とする相互接続システム。
【請求項２】
データ及びコマンドが８つの選択モードのうちの１つにおける前記通信ポートにおいて送受信可能であり、前記選択モードにおいて、
ａ）通信ポートを介して東ＰＥへデータを送信し、同時に、通信ポートを介して西ＰＥからデータを受信するための１つの送信東／受信西モードと、
ｂ）通信ポートを介して北ＰＥへデータを送信し、同時に、通信ポートを介して南ＰＥからデータを受信するための１つの送信北／受信南モードと、
ｃ）通信ポートを介して南ＰＥへデータを送信し、同時に、通信ポートを介して北ＰＥからデータを受信するための１つの送信南／受信北モードと、
ｄ）通信ポートを介して西ＰＥへデータを送信し、同時に、通信ポートを介して東ＰＥからデータを受信するための１つの送信西／受信東モードと、
ｅ）転置されたＰＥ間の送受信のための転置送信／受信モード、及び、距離１超立方体ＰＥ間の送受信のための超立方体送信／受信モードと、
ｆ）選定距離２超立方体ＰＥ間の送受信のための超立方体送信／受信モードと、
ｇ）距離ｄ、ｄ次元超立方体補足ＰＥ間の送受信のための超立方体補集合送信／受信モードと
を含むことを特徴とする請求項１に記載の相互接続システム。
【請求項３】
前記モードが前記ＰＥ間に直接接続経路が確立されることを可能にすることを特徴とする請求項２に記載の相互接続システム。
【請求項４】
更に、各ＰＥ制御ポートに制御情報を同時に送り、かつ各ＰＥにおいてレジスタにロードするために各ＰＥデータポートにデータを送るように接続されたコントローラ及びメモリシステムを有することを特徴とする請求項３に記載の相互接続システム。
【請求項５】
各通信ポートがＢビット幅の送受信経路を含み、前記Ｂは１以上の整数であることを特徴とする請求項３に記載の相互接続システム。
【請求項６】
各ＰＥは、ある通信ポートを経てデータ又はコマンドを選択的に送り、制御ポートを介して受信し各々のＰＥに存在する制御論理により復号された通信命令に基づいて、同時に、別の通信ポートを経てデータ又はコマンドを受信するように接続されたことを特徴とする請求項３に記載の相互接続システム。
【請求項７】
前記通信命令は、コントローラから前記制御ポートを経て前記制御論理によって受信されることを特徴とする請求項６に記載の相互接続システム。
【請求項８】
前記クラスタスイッチがオペレーションをサポートし、前記ＰＥはそれぞれ同時にコマンド又はデータを送り、同時に、コマンド又はデータを受け取ることを特徴とする請求項６に記載の相互接続システム。
【請求項９】
前記ＰＥはそれぞれ前記通信ポートの送信部分を経てコマンド又はデータを同時に送り、同時に、前記通信ポートの受信部分を経てデータ又はコマンドを受け取るように、前記同時オペレーションが選択的にスイッチされることを特徴とする請求項８に記載の相互接続システム。
【請求項１０】
並列プロセッサであって、
それぞれが１つの単一ＰＥ間通信ポートを備える複数の処理エレメント（ＰＥ）を有し、
従来型トーラス接続アレイの接続性に等価なＰＥ間接続性を提供するように、かつ、直接転置間および直接超立方体距離１と選定距離２と超立方体間補足ＰＥ通信とを提供するように接続されたＰＥ間通信経路を有することを特徴とする並列プロセッサ。
【請求項１１】
並列プロセッサであって、
各処理エレメントが合計Ｂ本のワイヤを経てデータを送受信する通信ポートを有するＭ個の処理エレメントのＮ個のクラスタと、
前記クラスタ対の間に接続された幅（Ｍ）（Ｂ）に等しいか、それ以下の個数の通信経路であって、対内の各クラスタメンバが対のもう一方のクラスタ内処理エレメントに対してトーラス最隣接体である処理エレメントを含み、各経路が相互に排他的な２つのトーラス方向、即ち、南と東、又は、南と西、又は、北と東、又は、北と西における前記クラスタ対間通信を可能にする通信経路と、
前記クラスタ対間の幅２（Ｍ）（Ｂ）のワイヤによる通信を、幅（Ｍ）（Ｂ）のワイヤ経路数以下に組み合わせるように接続されたマルチプレクサと、
を有することを特徴とする並列プロセッサ。
【請求項１２】
各クラスタの処理エレメントが北および西トーラス方向で一方のクラスタと、南および東トーラス方向でもう一方のクラスタと通信することを特徴とする請求項１１に記載の並列プロセッサ。
【請求項１３】
各クラスタの処理エレメントが北および東トーラス方向で一方のクラスタと、南および西トーラス方向でもう一方のクラスタと通信することを特徴とする請求項１１に記載の並列プロセッサ。
【請求項１４】
各クラスタの処理エレメントが２つの超立方体方向で一方のクラスタと、２つの超立方体方向でもう一方のクラスタと通信することを特徴とする請求項１１に記載の並列プロセッサ。
【請求項１５】
少なくとも１つのクラスタが超立方体補足対を含むことを特徴とする請求項１１に記載の並列プロセッサ。
【請求項１６】
クラスタスイッチが前記マルチプレクサを有し、相互に排他的な２つのトーラス方向から受信した通信を、１つのクラスタ内の処理エレメントに多重化するように前記クラスタスイッチが接続されることを特徴とする請求項１１に記載の並列プロセッサ。
【請求項１７】
前記クラスタスイッチが１つのクラスタ内の処理エレメントからの通信をもう一方のクラスタへ送信するために多重化するように接続されることを特徴とする請求項１６に記載の並列プロセッサ。
【請求項１８】
前記クラスタスイッチが、１つのクラスタ内の転置処理エレメント間で通信を多重化するように接続されることを特徴とする請求項１７に記載の並列プロセッサ。
【請求項１９】
前記ＮがＭ以上であることを特徴とする請求項１１に記載の並列プロセッサ。
【請求項２０】
前記ＮがＭ未満であることを特徴とする請求項１１に記載の並列プロセッサ。
【請求項２１】
並列プロセッサであって、
各処理エレメントが合計Ｂ本のワイヤを経てデータを送受信する通信ポートを有し、１つのクラスタ内の各処理エレメントが１つのクラスタ内において前記クラスタの外部の処理エレメントに対するよりも他の処理エレメントに対して物理的に一層近接して形成された、Ｍ個の処理エレメントのＮ個のクラスタと、
前記クラスタ対の間に接続された幅（Ｍ）（Ｂ）のワイヤの数に等しいかそれ以下の数であって、対内の各クラスタメンバが、対のもう一方のクラスタ内処理エレメントに対してトーラス最隣接体である処理エレメントを含み、各経路が相互に排他的な２つのトーラス方向、即ち、南と東、又は、南と西、又は、北と東、又は、北と西、または、２つの超立方体次元の間における前記クラスタ対間通信を可能にした通信経路と、
、前記クラスタ対間の幅２（Ｍ）（Ｂ）のワイヤによる通信を幅（Ｍ）（Ｂ）のワイヤ経路数以下に組み合わせるように接続されたマルチプレクサと、
を有することを特徴とする並列プロセッサ。
【請求項２２】
各クラスタの処理エレメントが北および西トーラス方向で一方のクラスタと、南および東トーラス方向でもう一方のクラスタと通信することを特徴とする請求項２１に記載の並列プロセッサ。
【請求項２３】
各クラスタの処理エレメントが北および東トーラス方向で一方のクラスタと、南および西トーラス方向でもう一方のクラスタと通信することを特徴とする請求項２１に記載の並列プロセッサ。
【請求項２４】
少なくとも１つのクラスタが超立方体補足対を含むことを特徴とする請求項２１に記載の並列プロセッサ。
【請求項２５】
クラスタスイッチが前記マルチプレクサを有し、２つの超立方体方向から受信した通信を１つのクラスタ内の処理エレメントに多重化するように前記クラスタスイッチが接続されることを特徴とする請求項２１に記載の並列プロセッサ。
【請求項２６】
前記クラスタスイッチが１つのクラスタ内の処理エレメントからの通信を、もう一方のクラスタへ送信するために多重化するように接続されることを特徴とする請求項２５に記載の並列プロセッサ。
【請求項２７】
前記クラスタスイッチが１つのクラスタ内の超立方体補足処理エレメント間での通信を多重化するように接続されることを特徴とする請求項２６に記載の並列プロセッサ。
【請求項２８】
前記ＮがＭに等しいか、それ以下であることを特徴とする請求項２１に記載の並列プロセッサ。
【請求項２９】
前記ＮがＭ以上であることを特徴とする請求項２１に記載の並列プロセッサ。
【請求項３０】
前記処理エレメント間通信がビット直列であり、各処理エレメントのクラスタが前記通信経路を経て他の２つのクラスタと通信することを特徴とする請求項２１に記載の並列プロセッサ。
【請求項３１】
処理エレメント間の通信経路がデータバスを有することを特徴とする請求項２１に記載の並列プロセッサ。
【請求項３２】
前記通信経路が双方向性であることを特徴とする請求項２１に記載の並列プロセッサ。
【請求項３３】
前記通信経路が単方向性であることを特徴とする請求項２１に記載の並列プロセッサ。
【請求項３４】
ＰとＱが、トーラス接続アレイと同数のＰＥを備えるそれぞれ行と列の個数であり、ＰとＱがそれぞれＮとＭに等しいことを特徴とする請求項２１に記載の並列プロセッサ。
【請求項３５】
ＰとＱが同数のＰＥを備えたトーラス接続アレイのそれぞれ行と列の個数であり、ＱがそれぞれＭとＮに等しいことを特徴とする請求項２１に記載の並列プロセッサ。
【請求項３６】
並列プロセッサであって、
次式によって定義された次元に従ったサイズ４のｄ次元正規トーラスに関する処理エレメントＰＥのクラスタを有し、
【数１２】

前記クラスタ間のＰＥ間通信経路を多重化するように接続され、それによって、トーラス接続アレイの接続性に等価のＰＥ間接続性を提供するクラスタスイッチを有することを特徴とする並列プロセッサ。
【請求項３７】
前記クラスタスイッチは更に、１つのクラスタ内の転置ＰＥ対におけるＰＥ間直接通信を提供するように接続されることを特徴とする請求項３６に記載の並列アレイプロセッサ。
【請求項３８】
前記クラスタを組み合わせ、同時に、多重化を維持し、或いは前記クラスタスイッチによって、前記クラスタがスケーラブルであることを特徴とする請求項３７に記載の並列プロセッサ。
【請求項３９】
前記クラスタスイッチは更に１つのクラスタ内超立方体補足対におけるＰＥ間直接通信を提供するように接続されることを特徴とする請求項３８に記載の並列プロセッサ。
【請求項４０】
並列プロセッサを形成する方法であって、
各クラスタが次式によって定義され、
reshape(G_Nvec(T),N,N)
クラスタが他の少なくとも１つのクラスタの処理エレメントと相互に排他的な方向においてのみ通信する、Ｍ個の処理エレメントのＮ個のクラスタにおいて処理エレメントを配列するステップと、
前記の相互に排他的な方向の通信を多重化するステップと、
を含むことを特徴とする並列プロセッサを形成する方法。
【請求項４１】
それぞれがデータ及びコマンドを送受信するための通信ポートを備えるＰＥがクラスタにグループ化され、共に１より大きいＮ，ＭによりＮ×Ｍアレイに接続された複数の処理エレメント（ＰＥ）のための相互接続システムであって、
ＰＥ間接続経路と、
クラスタの間における相互に排他的なＰＥ間接続経路を組み合わせ、それによって、従来型トーラス接続ＰＥアレイの接続性に等価なＰＥ間接続性を提供するために必要な通信経路の個数を実質的に減少させるように前記ＰＥへ接続されたクラスタスイッチとを有し、
前記クラスタスイッチが更に転置ＰＥの間および超立方体補足ＰＥの間および各クラスタ内ＰＥの任意の対の間に直接通信を提供するように各クラスタ内ＰＥに完全に接続するための接続部を有することを特徴とする相互接続システム。
【請求項４２】
クラスタ内に配列された複数の処理エレメント（ＰＥ）を有する並列プロセッサであって、
ＰＥの対が、クラスタ内、および、１つのクラスタ内の第１ＰＥと前記第１ＰＥを含むクラスタに隣接する２つのクラスタの１つのクラスタ内の第２ＰＥとの間の利用可能な通信経路上で、単一ステップで通信するように前記ＰＥを接続するＰＥ間通信経路を有することを特徴とする並列プロセッサ。
【請求項４３】
１つのクラスタ内の全てのＰＥが完全に接続されることを特徴とする請求項４２に記載の並列プロセッサ。
【請求項４４】
前記ＰＥが分離された送信および受信ポートを備え、第１クラスタ内の任意のＰＥと隣接する第２クラスタ内の任意のＰＥとの間の通信が前記第１および第２クラスタ内の全てのＰＥに関して同時に実施可能であることを特徴とする請求項４３に記載の並列プロセッサ。
【請求項４５】
第１クラスタ内の任意のＰＥが第２の隣接クラスタ内の任意のＰＥに送信可能であり、第２クラスタ内の前記ＰＥが、第３隣接クラスタ内の任意のＰＥに送ることが可能であることを特徴とする請求項４２に記載の並列プロセッサ。
【請求項４６】
それぞれがデータ及びコマンドを送受信するための通信ポートを備え、かつクラスタにグループ化され、共に１より大きいＮ，Ｍで規定されるＮ×Ｍアレイ内の複数のノードを接続するための相互接続システムであって、
ノード間接続経路と、
クラスタ間の相互に排他的なノード間接続経路を組み合わせ、クラスタ間においてノード間接続経路を提供するために必要な通信経路の個数を実質的に減少させ、それによって従来型トーラス接続ノードアレイの接続性に等価なノード間接続性を提供するために必要な通信経路の個数を実質的に減少させるように前記ノードへ接続されたクラスタスイッチを有し、前記クラスタスイッチが更に転置ノード間および超立方体補足ノード間に直接通信を提供するための接続部を有することを特徴とする相互接続システム。
【請求項４７】
前記ノードが、グレイ符号化アドレスを備え、各最隣接ノードがただ１つの単一ビットだけ異なるアドレスを持つようにクラスタ内において配列されたことを特徴とする請求項４６に記載の相互接続システム。
【請求項４８】
各メモリがデータ及びコマンドを送受信するための通信ポートを備え、かつメモリがクラスタにグループ化され、タイル張り様メモリシステムを形成するようにＮ×Ｍアレイ内の複数のメモリエレメントを接続するための相互接続システムであって、
メモリ間接続経路と、
クラスタの間の相互に排他的なメモリ間続部経路を組み合わせ、それによって、従来型トーラス接続メモリアレイの接続性に等価なメモリ間接続性を提供するために必要な通信経路の個数を実質的に減少させるように前記メモリへ接続されたクラスタスイッチとを有し、
前記クラスタスイッチが更に転置メモリ間および超立方体補足メモリ間に直接通信を提供するための接続部を有することを特徴とする相互接続システム。

【図１Ａ】

【図１Ｂ】

【図１Ｃ】

【図１Ｄ】

【図２Ａ】

【図２Ｂ】

【図３Ａ】

【図３Ｂ】

【図３Ｃ】

【図３Ｄ】

【図４】

【図５】

【図６】

【図７】

【図８Ａ】

【図８Ｂ】

【図８Ｃ】

【図９Ａ】

【図９Ｂ】

【図１０】

【図１１】

【図１２】

【図１３】

【図１４】

【図１５】

【図１６】

【図１７】

【図１８】

【図１９】

【図２０】

【図２１Ａ】

【図２１Ｂ】

【図２１Ｃ】

【図２２】

【図２３】

【図２４】

【図２５】

【図２６】

【図２７Ａ】

【図２７Ｂ】

【図２８Ａ】

【図２８Ｂ】

【図２９】

【図３０】

【図３１】

【図３２】

【図３３】