JPH06507744A - 大量並列プロセッサ間の、階層的プロセッサ相互間通信ネットワークのための手順決定技術 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 １プロセ・す日の ・プロセ・・サ　日゛　−・　−り Ω友かγＩす部且歪 本発明は、国防省高等プロジェクト局により与えられた契約第ＭＤＡ９７２−９ ０−Ｃ−００２２の下に、政府の支持でなされた。政府は本発明に一定の権利を 有する。

大量並列コンピュータ・プロセッサ間の、プロセッサ相互間通信（ＩＰＣ）のた めの数多くの型の相互連結ネットワークが当該技術において公知である。これら の内には、トリー樺構造に構成し得る階層型通信ネットワークがあり、その中で は個別プロセッサが階層の最低レベル（）まり、レベルＯ）に位置し、木の葉を 表している。この個別プロセッサは、レベル０クラスタのグループに編成され、 各個別レベル０クラスタの各単独プロセッサが、それ自身の通信チャンネルを通 し、階層トリーのレベル１に位置しているレベル０クラスタのためのノードに相 互連結されている。同様な手法で、レベル１ノードは、レベル１クラスタのグル ープに編成されていても良く、その各個別レベル１クラスタの各単−ノーロよ、 それ自身の通信チャンネルを通し、階層トリーのレベル２に位置しているレベル １クラスタのためのノードと相互連結されている０階層トリーの最高レベル（レ ベルｎ）は、少なくとも二つの相互連結ノードを含み、それは、個別通信チャン ネルを通じ（ｎ−１）レベルのノードの各車−の一つを相互連結している。この ノードの各々は、適当なネットワーク・ルータまたはスイッチを含み、任意の選 択された送信レベルＯプロセッサが、任意の選択された受信レベルＯプロセッサ に相互連結されて、地球的ＩＰＣ能力を備えるようにする。

公知の様に、大量並列プロセッサ群を採用したコンピュータは、多数命令・多数 データ（ＭＩＭＤ）機の形を採るか、または単一命令・多数データ（ＳＩＭＤ） 機の形を採っても良い、ＭＩＭＤコンピュータにおいては、ネットワーク中のパ ケットは、多くのプロセッサの一つにより独立に発生させられたｒｓｅｎｄｊま たはｒｇｅｔＪ命令からである。成るＭＩＭＤコンピュータは、若し平均の手順 決定待ち時間またはパケットの遅れ時間が低ければ最適に稼働する。成るＳｌＭ Ｄ機は、一時に只一つの未決ｒｓｅｎｄＩＬか許容しない。ネットワーク中の全 てのパケットは、同一のｒｓｅｎｄ１命令に起源している。このｒｓｅｎｄｌは 、全てのパケットが配達されるまで完結しない。それ故、ＳＩＭＤＩｌは、ｒＳ ｅｎｄＪの全てのパケットに対し、低い最悪ケースの待ち時間を要する。この特 性は、ＳＩＭＤコンピコンピュータの手順決定プロトコルが、それらの寿命また はネットワーク中で過ごした時間に従ってパケットの優先順位決定をする必要が ないことを含蓄している。これに加えて、このネットワークは、何時でも限定さ れた数のパケットを有することを予期することが出来る。

ＳＩＭＤおよびＭＩＭＤプロセッサ相互間通信は又、期待パケット・サイズにお いても異なる。成るＭＩＭＤシステムにおいては、プロセス同期情報を含むもの の様な成るパケットは、もはや数バイト長さを越えるものでない、データを含む 他のものは、数キロバイト長さでも良い、ＳＩＭＤシステムにおけるパケットは 、しばしば只１語長であるように短い、それらは、隣接している画素またはマト リックス係数の値を含むことがある。

高い帯域幅の相互連結ネットワークは、高価で構築に複雑であるので、スケラビ イテイ（達成可能性）の問題が、全ての設計の中心となる。この相互連結ネット ワークの速度は、取り分けＳｌＭＤ機の様なＩＰＣ遅れを良くマスクしないコン ピュータにとって、性能の主要なファクタである０本発明は、ＳｌＭＤ機の階層 プロセッサ相互間通信のための改良された手順決定技術に向けられ、それはロー コストおよび低い待ち時間（つまり、低いＩＰＣ遅れを挿入すること）の両観点 から、ネットワークの動作を改良するのに効率的である。

発朋■概要 本発明は、単一命令・多数データ（ＳＩＭＤ）並列プロセッサ・コンピュータに おいて、アドレス情報を含むデータのパケットを、コンピュータの引き続く手順 決定サイクルの間、コンピュータの並列プロセッサの任意の一つとコンピュータ の並列プロセッサの他の任意の一つとの間で手順決定するための手順決定方法に 向けられている。この並列プロセッサ群は、ノードの少なくとも二つの階層レベ ルと一つの相互連結チャンネルのネットワークとを有する階層プロセッサ相互連 結トリー構造の葉を形成している。この階層プロセッサ相互連結トリー構造の最 高レベルは、少なくとも二つのノードを含み、且つノードの第一の階層レベルの 上位の階層レベルの各ノードは、次に低い階層レベルの複数の子孫ノードの親ノ ードである。第一レベル・ノードの各々は、ネットワークのチャンネルによって 、並列プロセッサ群の別々の一つと個別に相互連結されており、且つ各子孫ノー ドは、ネットワークのチャンネルによって、その親ノードと相互連結されている 。加えて、成る共通の親ノードの各子孫ノードは、ネットワークのチャンネルに よって、その共通の親ノードの少なくとも一つの他の子孫ノードと相互連結され ており、且つ最高階層レベルの各ノードは、ネットワークのチャンネルによって 、最高階層レベルの他のノードの少なくとも一つと相互連結されている。更に全 てのネットワーク・チャンネルは二重の単方向性リンクで、二つのパケットの反 対方向への同時伝送を可能としており、且つ、各ノードは、（１）そのレベルに おけるネットワーク・チャンネルの合計数より一つ多いパケットを記憶する記憶 容量を有するバッファ、および（２）前記並列プロセッサ群の送信する一つでそ のノードから起源し、ネットワーク・チャンネルを通じ前記並列プロセッサ群の 受信する一つに向かう接続を、そのノードのバッファに記憶されたパケットに含 まれたアドレス情報に従って、延長するためのルータ−を含むものである。

本発明の手順決定方法は、コンピュータの引き続く手順決定サイクルの間に、次 のステップを含む： （ａ）階層プロセッサ相互連結トリー構造の各親ノードにおいて、その親ノード のバッファに記憶され、送信プロセッサから受信プロセッサに向かう接続を延長 するために、その子孫ノードに送られるべきことを要求するアドレス情報を含む パケットを、チャンネル・ダウン・リンクを通じ、その子孫ノードの各々に、そ の親ノードのバッファが、一つの空き記憶スペースを有するようになるか、その 子孫ノードがそれに送られるべきパケットを有しなくなる迄、伝送するステップ ； （ｂ）成る親ノードのバッファが、一つの空き記憶スペースを有するようになる か、その子孫ノードがそれに送られるべきパケットを有しなくなることに応じて 、その子孫ノードにその親ノードから、その子孫ノードの各々がそれに、その子 孫ノードのバッファに前原て記憶されていた、そのパケットが送信プロセッサか ら受信プロセッサに向かう接続を延長するために、その親ノードから送られるべ きことを要求するアドレス情報を含むパケットを、チャンネル・アップ・リンク を通し、送ることを試みても良いと合図するステップ；および（ｃ）ステップ（ ｂ）に述べられた試みが、その親ノードの子孫ノードの与えられた一つによる現 行手順決定サイクルの間に、成るパケットがその時、その親ノードにその子孫ノ ードの他のバッファから送られてきたために、達成出来ない場合、その現行手順 決定サイクルの間、その親ノードの子孫ノードの、その与えられた一つのバッフ ァからのパケットを、その親ノードの子孫ノードのその他のバッファに記憶させ るために伝送するステップ。

区血少旦単猛説所 図１は、４０９６個のプロセッサ群間のプロセッサ相互間通信のための階層間接 ネットワークを示すダイヤグラム表示；図２は、８個のキャビネットに収められ 、各キャビネットあたり８枚の回路ボード、各回路ボードあたり６４個のプロセ ッサがある、４０９６個のプロセッサ群の相互連結に所要の各数を、相互連結ネ ットワークの幾つかの異なる型に対して示す表；および 図３は、本発明の手順決定技術を図解する簡単化した機能ダイヤグラム図である 。

しい　の　な量゛ 本発明の記述における図解の目的だけに限るが、４０９６個のプロセッサ群は、 図１に示すように、６４個のプロセッサの各クラスタが、８個のキャビネットの 別々の一つに収められた８枚の回路ボードの別々の一つに置かれて、成る階層プ ロセッサ相互間通信ネットワーク中に相互連結されているものと仮定する。この 階層のレベルＯのクラスタの６４個のプロセッサの各々が、この階層のレベルｌ のそれ自身の個別ノードに相互連結され、そのクラスタの回路ボードに位置して いる６４個のレベル１ノードをもたらしている。各個別キャビネット内に収めら れた８枚の回路ボードに対応する、この階層の６４個のレベル１ノードの８個の 各クラスタが、この階層のレベル２における個別ノードに相互連結され、合計で ８レベル２ノードをもたらしている。８個の個別キャビネットに対応する、この 階層のレベル２ノードの全８個はこの階層のレベル３において他の一つと相互連 結されている。

合計して６４枚の回路ボードの各々は、６４個のプロセッサの関連するクラスタ を含むことに加えて、その関連したクラスタの個別のレベル１ノードを含むオン ボード・ルータ集積回路も含んでいて良い、８個のキャビネットの任意の与えら れた一つに収められた８枚の回路ボードに関連するレベル２ノードは、それが関 連しているキャビネットの背面に配置されたルータ集積回路を設けられていて良 い、これは、８個のキャビネットのクラスタに関連し、集積回路だけに限らない 手段で装備されるべき、単一レベル３ノード・ルータのみを与える。

上述の４０９６便のプロセッサ群のための階層プロセンサ相互間通信ネットワー クが、より精巧な地球的通信を必要とする応用を裏付けることが出来ることは望 ましい。例えば、急速フーリエ変換（ＦＦＴｓ）、ラスタ・マツピング、および パラレル・データ・シフトの様なコンパイラ作業は、全て不規則なパターンにあ る遠隔プロセッサ間で、データを移動させることを必要とする。また、多くの応 用は、手順決定パターンが実行時まで知られていない通信のための裏付けを必要 とする。かような必要性が、手順決定制御のためにプロセッサ群自身に依存せず 、少しの空間的局在性で、手順決定パターンを扱うことの出来るＩＶＣシステム への研究を促進した。更に、階層ネットワークは、ネットワーク・レベルの数に 加えて、各レベルにおけるクラスタのトポロジー（位相幾何学）の様に、無数の パラメータを有している。実際上、これらのパラメータの最適な選択は、自然ま たは予期した手順決定パターンに依存する。

地球的［ＰＣのための相互連結ネットワークは、かなりの研究活動の話題であっ て来た。相互連結ネットワークの二つの主要なりラス：直接および間接、が提案 されている０間接ネットワークの例は、オメガ（Ｏｍｅｇａ）、ベネス（Ｂｅｎ ｅｓ）およびパーフェクト・シ＋７フル（ｐｅｒｆｅｃｔ　５ｈｕｆｆ　ｌｅ） 矛ノドワークである０間接ネットワークは、ＢＢＮバタフライ（Ｂｕｔｔｅｒｆ ｌｙ）およびＩＢＭ　ＲＰ３に装備されて来た。直接またはスタティック・ネッ トワークは、リング、二次元的メツシュまたはトーラス（円形隆起）、直接ケー ーアレー（ｋ−ａｒｙ）、ハイパーキューブに例示されるｎ−キューブ、および 完全接続またはクロスバ−の様な種々のトポロジーを用いる。テラ（Ｔｅｒａ） コンピユーテイング・システム、アイワープ（ｉＷａｒｐ）およびコスミック・ キューブ（Ｃｏｓｍｉｃ　Ｃｕｂｅ）は二次元的トーラスを用いる。十三次元的 ハイパーキューブはコネクション・マシーン（Ｃｏｎｎｅｃｔｉｏｎ　Ｍａｃｈ ｉｎｅ）に装備されている。

これらの相互連結ネットワークの各々の記述および議論の中心には、ネットワー ク装備のコストおよび、そのコストが性能をもって発揮する機能がある。コスト は、コントローラの複雑性、接続の長さ、または接続の数で測定出来る。大きな ＳＩＭＤシステムに関して、接続の数は、そのシステムが数千のプロセッサ群に 成長し、多数のボードおよびキャビネットにおよぶので、臨界的なコストである 。接続の数またはコストを制限することはシステム性能を制限することになり得 る。

階層ネットワーク（それ自身は新規でない）は、このコスト・パーフォーマンス ・トレイドオフ（かねあい）問題に一つの解決を提供する０例えば、階層ネット ワークは、過去においてヘクター（Ｈｅｃｔｏｒ）、シーエム（Ｃｍ＊）および シダー（Ｃｅｄａｒ）システムに装備されて来た。大量並列システムの着実な成 長および成熟とともに、階層ネットワークは、高速通信に特別の嘱望を維持して いる。

再び図１を参照すると、上で議論した仮定の４０９６個のプロセッサ階層ネット ワークの機能的ブロック・ダイヤグラムが示されている０図１に示すように、こ の階層ネットワークは、トリ一様構造を有している。木の葉はプロセッサで、内 部ノードはネットワーク・ルータまたはスイッチである。共通の親を有するノー ドのグループはクラスタと呼ばれ、成るクラスタの各ノードは、その共通の親の 子孫と呼ばれる。成るトリー・レベル内の全てのクラスタは、同一のトポロジー で相互連結されるが、異なるトリー・レベルは、場合により、二次元的トリ、ハ イパーキューブまたはクロスバ−の欅な異なるトポロジーを存し得る。

ネットワーク・レベルの数、およびクラスタのサイズおよびトポロジーは、ハー ドウェアの複雑性およびネットワーク性能の両者に深い影響を及ぼす、これらの パラメータは、ボード間およびキャビネット間接続の様なオフチップ・ハードウ ェアの量を最小限にするように選ぶべきである。これらの接続は、インボードま たはインチツブ接続より高価で低速なので、避けるべきである。

この点に関し、図２は、上述の４０９６個のプロセッサ相互連結ネットワークの ためのオフチップ・ハードウェア・コストにおける差を示す表で、そこでは、完 成コンピュータが１枚に６４個のプロセッサを有する８枚の回路ボードを８個の キャビネットに収められているものと仮定し、採用した特定のトポロジーに依存 している。試験したトポロジーは、バイナリ−・ハイパーキューブ、二次元的ト ーラス、および二つの階層ネットワークである。この階層ネットワークのための クラスタ・サイズの選択は、先に示したハードウェア・レイアウトに直接対応す る。各最低レベル・クラスタは、単一のＩＣに装備されたルータを用いてボード の６４個のプロセッサを相互連結する。第２レベル・クラスタは、共通のキャビ ネ、トの８枚のボードを相互連結し、第３レベルの単一のクラスタは、８個のキ ャビネット全てを相互連結する。

図２は、この階層トポロジーが、単一レベル・トポロジーよりかなり低い接続の 数を有することを示している。取り分は重要なことは、この階層ネットワークの キャビネット間接続の数における節約である。

ＳＩＭＤ階層ネ階層ラントワークの本発明の新規な手順決定技術を徒示する前に 、この手順決定技術により利用されてるＳＩＭＤコンピコントローラるＩＰＣの 幾つかの特徴を指摘することは価値がある。この手順決定技術において、パケッ トは、送信プロセッサから受信プロセッサへ、一連のｒホップ１により中間のノ ードを通して発送される。このパケットは、各ノードにおいて「ホラ１１間でバ ッファされる。この「ホップＪは、ネットワークを通しるパケットの経路を構成 する。この経路は、伝統的なトリー横断アルゴリズムを用いて発生させられる、 成るパケットは、その転送先に達するのに必要な最低限可能なりラスタまで上昇 し、そのクラスタを横断し、その後、その転送先プロセッサまで下降する。

加えて、当該技術において公知の強制または自棄的手順決定のバージョンがクラ スタ横断のために使用される。各クラスタ・ノードは、そのイン・クラスタ・チ ャンネルの各々のためのバッファ・スペースを有している。各手順決定サイクル において、全てのバケ７）は、これらのチャンネルの一つに送り出され、「古い ｊパケットのバッファ欠所を残す、各パケットは、それが必要としているチャン ネル上に伝送されるべき他のものと競い合う、若し成るパケットが、それが必要 としているチャンネルを得られないならば、それは強制的に、使用されていない イン・クラスタ・チャンネルに発送される。成るパケツトは、１サイクル間に各 イン・クラスタ・チャンネルに達し得るので、入って来るパケットの最大数は、 チャンネルの数に等しいか、或いはノードのバッファ・スペースと同等である、 バッファのオーバーフローの可能性は無い。

強制的手順決定は、そこに恐ら（その長さが変化しており、ノードの各対の間に 存在しているクロスバ−またはハイパーキューブの様な多数の経路があるトポロ ジーについて効果的である。かような場合において、成る特定のチャンネルのた めに並んで待っているパケットは、より長い経路を採ることによりより早く進行 出来る。クロスバ−の場合、その転送先までのバケット経路は、若しそれが強制 的に発送されるならば、長くなることは無い０代わりの経路を使用することによ り、強制的手順決定は、ホット・スボント・トラフィック混雑を軽減し、それ故 、手順決定時間を低下させる。

ここで、本発明の手順決定技術により採用された手順決定経路の型の単純化した ダイヤグラムである図３を参照する０図解の目的で、三しベル階層構造が図３に 仮定されており、そのレベル３は、クラスタ・ノードＮ３１１およびＮ３１２を 含んでいる。レベル２は、親ノードＮ３１１の子孫であるクラスタ・ノードＮ２ １１およびＮ２１２並びに親ノードＮ３１２の子孫であるクラスタ・ノードＮ２ ２１およびＮ２２２を含んでいる。レベル１は、親ノードＮ２１１の子孫である クラスタ・ノードＮ１１１、Ｎ１１２およびＮ１１３ｉ親ノードＮ２１２の子孫 であるクラスタ・ノードＮ１２１．Ｎ１２２およびＮ１２３；親ノードＮ２２１ の子孫であるクラスタ・ノードＮ１３１、Ｎ１３２およびＮ１３３ｉ並びに親ノ ードＮ２２２の子孫であるクラスタ・ノードＮ１４１．、Ｎ１４２およびＮ１４ ３を含んでいる。

図３に示した樺に、レベル１ノードの各々は、個別の専用チャンネルを通してレ ベルＯプロセッサの対応する一つと相互連結されている。取り分け、プロセッサ ＰＯ１２はノードＮｌ　１２と、それ自身の専用チャンネルＣＩ２を通して相互 連結され、且つ、プロセッサＰＯ４３は）〜ドＮ１１２と、それ自身の専用チャ ンネルＣ４３を通して相互連結されている。更に、図３に示した様に、発送され たデータ・パケットに割当られたネットワーク・チャンネルは、次に高しルベル における共通の親ノードの子孫であり、且つこれらの子孫ノードの各々をその共 通の親ノードに相互連結している、同一レベルの全てのクラスタ・ノードに相互 連結されている。

図３に示した階層構造は、全てのネットワーク・チャンネルが、二つのパケット の反対方向への同時伝送を可能とする二重の一方向性リンクであることを仮定し ている。それは又、各リンクが、クラスタ内またはレベル間のいずれにあっても 、コンピュータ・マシーンの１サイクルにつき正確に１個のパケットを配送出来 ることも仮定している。更に、各クラスタ・ノードが、パケット・データ（手順 決定アドレス情報を含む）を記憶するための与えられたサイズのバッファ、およ び各コンピュータ・マシーン・サイクルの間、そのコンピュータ・マシーン・サ イクルの間、チャンネルを通じる接続を延長する目的で、その手順決定アドレス 情報により制御される適当なスイッチング手段を含む。

本発明の手順決定技術の次の説明において、ｒｎｏｃｈａｎｓ）は、与えられた 階層レベルにおける与えられたクラスタのノードを、その与えられた階層レベル の直ぐ上または下の階層レベルにおけるクラスタ・ノードに、または、レベル１ の場合、レベル０における個別プロセッサに相互連結するチャンネルの合計数を 指示するものである。各バッファのサイズは、ｒｎｏｃｈａｎｓ＋ＩＪに等しい 。

本発明の手順決定技術によれば、各手順決定サイクルの間、各クラスタ・ノード において、送信プロセッサがら、手順決定アドレス情報により同定された受信プ ロセッサに向かう接続を延長する為に、次のプロセス・ステップが起こる：（１ ）各クラスタの親ノードの各々につき、チャンネル・ダウン・リンクにわたりそ の子孫ノードに、その親ノードのバッファに記憶されていた、そのパケットが、 送信プロセッサがら受信プロセッサに向かう接続を、その親ノードのバッファが 一つの空きの記憶空間を有するようになるが、又はその子孫ノードがそこに送ら れるべきパケットをもはや持たなくなるまで、延長するために、そのパケットが その子孫ノードに送られるべきことを要求するアドレス情報を含むパケットが送 られる。

（２）成る親ノードのバッファが一つの空きの記憶空間を有するようになるか又 はその子孫ノードがそこに送られるべきパケットをもはや持たなくなった時は何 時でも、その親ノードはその子孫ノードに、その子孫ノードの各々が、そこに「 古い１送信プロセンサから受信プロセンサに向かう接続を延長するために、その パケットがその親ノードから伝送されるべきことを要求するアドレス情報を含む パケット（つまり、現行の手順決定サイクルの開始に先立ってその子孫ノードの バッファに記憶されていたパケット）を、チャンネル・アップ・リンクにわたり 送るように試みても良いと合図する。

（３）ステップ（２）に述べられた試みが、成るパケットがその時、その親ノー ドにその子孫ノードの他のバッファから送られてきたために、その親ノードの子 孫ノードの与えられた一つによる現行手順決定サイクルの間に達成出来ない場合 、その現行手順決定サイクルの間、その親ノードの子孫ノードの、その与えられ た一つのバッファからのパケットを、その親ノードの子孫ノードのその他のバッ ファに記憶させるように伝送する（つまり、これらの場合には、強制的または自 棄的手順決定が鯨りにされる）。

図３に戻ると、そこには、送信プロセッサＰ０１２が受信プロセッサＰＯ４３と 、図３に実線で示した相互連結チャンネルを通じ相互連結されるべきこと、一方 、−以上の他の送信プロセッサが一以上の他の受信プロセッサと、図３に破線で 示した相互連結チャンネルを通じ相互連結されることをめていて良いことが仮定 されている。最初の手順決定サイクルの間、所望の手順決定アドレス情報ととも に受信プロセッサＰＯ４３により使われるためのデータを含む与えられたパケッ トが、ノードＮｌＩ２まで、その間の相互連結専用チャンネルＣＩ２を通じ上昇 し、そのバッファ内に記憶される。第２の手順決定サイクルの間、その親ノード Ｎ２１１が、それにその子孫ノードＮ１１２からそのチャンネルを割当るのに成 る理由、例えば親ノードＮ２１１のバッファがその時完全に満たされ、あるいは 親ノードＮ２１１のルータ−がその時他のパケットで塞がっていたと言う様なこ とで、自由でないと仮定すると、その与えられたパケットをノードＮ１１２のバ ッファからノードＮ１１ｌのバッファに移送するために強制的手順決定が採用さ れる。再び、強制的手順決定が、第３の手順決定サイクルの間に必要であると仮 定され、そしてノードＮ１１１のバッファからのその与えられたパケットは、ノ ードＮ１１３のバッファに移送される。しかしながら、第４の手順決定サイクル に際しては、親ノードＮ２１１は最終的に、それをその子孫ノードＮ１１３に相 互連結するチャンネルを割当て、そしてその与えられたパケットは、ノードＮ２ １１のバッファまで上昇し、そこで記憶される。同様な手法で、パケットは、第 ５ないし第８の各手順決定サイクルの間、引き続いて、子孫ノードＮ２１１から その親ノードＮ３１１に上向きに動がされ、ノードＮ３１２を横切り、次いで、 親ノードＮ３１２の子孫ノードＮ２２２を通過し、親ノードＮ２２２の子孫ノー ドＮ】４３に下る、そして第９の手順決定サイクルの間に、最終的に、受信プロ セッサＰＯ４３まで専用のチャンネルＣ４３を通じて下る。

上述の手順決定プロセスにおいて、上向きの動きは明示のフロー制御を必要とす る。上昇を望む各パケットは、その親が占有されていないバッファ・スペースを 持つ迄待たなければならない、他方、下向きの動きは、何らのフロー制御を必要 としない。下降を望むパケットは、若しそのノードにある他のパケットが、その チャンネルに対する権利を与えられているならば、進行を許されない、この下向 きの動きに対する制約は、下向きプロッヶージと呼ばれる。ある与えられたレベ ルのクラスタを横断することを望むか、あるいはより高いレベルへの上昇または より低いレベルへの下降を待っている全てのパケットは、強制的手順決定を用い て発送される。

かように、上述の手順決定プロセスは、レベル間のデッドロック及びバッファ・ オーバーフローの防止を保証している。成るレベルは常に成る固定された数のパ ケットをより低いレベルへ送ることを許されている。それ故、成るレベルにおけ るパケツトは、決して完全にはトラップされることは無い、それらが去った時、 それらは、より低いレベルから上昇するパケットのためのスペースを作る。

各ノード・バッファが、ｒｎｏｃｈａｎｓ＋１１パケットのためのスペースを有 している条件で、バッファ・オーバーフローが無いように保証されている。クラ スタ内で使用される強制的手順決定プロトコルは、クラスタ内で動いているパケ ラトがｒｎｏｃｈａｎｓＪバッファ・スペース以上を消費しないことを保証して いる。余分のスペースが、成るパケットが次に高いレベルから下降してくる場合 のためにリザーブされている０次の手順決定サイクルの間のその下向きの動きは 、若しクラスタからの他のパケットにより阻止されるならば、損なわれる。若し そのパケットが阻止されるならば、それは、それを損なったパケットのバッファ ・スペースを取ることが出来る。いずれの場合でも、サイクルの終わりではこの 特別のバッファ・スペースは常に空いている。それ故、クラスタを横断し下向き に動くパケットは、決してバッファ・オーバーフローを生じることは無い。

更に、上述の手順決定プロセスは、フロー制御ラインの数を殆ど除去することに よりハードウェア？３［９１１１性を減少させる。それは、合計の手順決定待ち 時間を、ネットワーク内に存在しているパケットの数を常に最大限にすることに より、最小化するように試みる。バッファを出来るだけ満たすように維持するこ とにより、パケットの多数のものが進行出来る。かような戦略は、クラスタ・ノ ードが、冗長な経路を僅かだけしか含まない場合に限り失敗に終わる。この場合 において、若し強制（自棄）的手順決定が大量に生じるならば、前向きの進行の 量は、必ずしもかような強制的手順決定により失われた進行を越えることは無い 。

前述の事柄から、手順決定順列における局在性の量が知られているなら、コスト ・エフエクテイブなネットワークを見出し得ることは明らかである。成る手順決 定順列およびレベルに対しては、高いピーク帯域幅およびそれに対応する高いハ ードウェア・コストを有するトポロジーは、成る経済的なより遅いトポロジーよ り良い性能を与えないことがある。成る三レベル階層に対して、レベル１のため のリング（トロイド）トポロジー構造、およびレベル２および３の各々のための クロスバ−・トポロジー構造が、レベル１．２および３の全てのためのクロスバ −・トポロジー構造に殆ど匹敵する性能を発揮するが、装備するのは有意により 容易である０期待された手順決定パターンが、その性質において一般的に地球的 であるような場合においては、最高のトポロジーが、クロスバ−のように高い程 度の接続性を有する一つであるべきである。より低いトポロジーも、性能に有意 に影響するものでないので、リング、バイナリ−・ハイパーキューブおよびクロ スバ−・トポロジー構造が、各階層レベル１．２および３に対する良い候補であ る。

上述の手順決定プロセスを採用した階層ネットワークは、ＳＩＭＤコンピュータ に対する高速、低コストのプロセッサ相互間通信を提供する。シミュレーション は、この階層ネットワークがハードウェアのために仕立てられた時、このコスト 潜在製品は成る単一レベル・トポロジーに匹敵するが、成る場合にはより低いこ とを示している。

一旦ネノドワーク構造が決定されると、クラスタ・トポロジーは、各レベルの実 際の処理能力がそのトラフィック負荷とバランスするように選ばれなければなら ない。適切なバランスをもって、ネットワークのチャンネルは高い利用率で動作 し、ネットワーク性能がネットワーク・コストを正当化することを保証する。

ｌ：Ｉｏ　Ｏｃ’−ｔ　寸 へや−へ　寸

Claims (2)

【特許請求の範囲】
1. １．単一命令・多数データ（ＳＩＭＤ）並列プロセッサ・コンピュータにおいて 、アドレス情報を含むデータのパケットを、前記コンピュータの引き続く手順決 定サイクルの間、前記コンピュータの並列プロセッサの任意の一つと前記コンピ ュータの並列プロセッサの他の任意の一つとの間で手順決定するための手順決定 方法であって；そこでは前記並列プロセッサ群が、ノードの少なくとも二つの階 層レベルと一つの相互連結チャンネルのネットワークとを有する階層プロセッサ 相互連結トリ−構造の葉を形成しており；前記階層プロセッサ相互連結トリ−構 造の前記最高レベルは、少なくとも二つのノードを含み、そこで、ノードの第一 の階層レベルの上位の階層レベルのノードの各々は、次に低い階層レベルの複数 の子孫ノードの親ノードであり；前記第一レベル・ノードの各々は、前記ネット ワークのチャンネルによって、前記並列プロセッサ群の別々の一つと個別に相互 連結されており、各子孫ノードは、前記ネットワークのチャンネルによって、そ の親ノードと相互連結されており、或る共通の親ノードの各子孫ノードは、前記 ネットワークのチャンネルによって、その共通の親ノードの少なくとも一つの他 の子孫ノードと相互連結されており、且つ最高階層レベルの各ノードは、前記ネ ットワークのチャンネルによって、最高階層レベルの少なくとも一つの他のノー ドと相互連結されており；更に、全ての前記ネットワーク・チャンネルは二重の 単方向性リンクで、二つのパケットの反対方向への同時伝送を可能としており； 且つ各ノードは、（１）そのレベルにおけるネットワーク・チャンネルの合計数 より一多いパケットを記憶する記憶容量を有するバッファ、および（２）前記並 列プロセッサ群の送信する一つでそのノードから起源し、前記ネットワーク・チ ャンネルを通じ前記並列プロセッサ群の受信する一つに向かう接続を、そのノー ドのバッファに記憶されたパケットに含まれたアドレス情報に従って、延長する ためのルーターを含むものであり；更に前記手順決定方法は、前記コンピュータ の前記引き続く手順決定サイクルの各々の間に、次のステップを含んでいる：（ ａ）階層プロセッサ相互連結トリ−構造の名親ノードにおいて、その親ノードの バッファに記憶され、送信プロセッサから受信プロセッサに向かう接続を延長す るために、その子孫ノードに送られるべきことを要求するアドレス情報を含むパ ケットを、チャンネル・ダウン・リンクを通じ、その子孫ノードの各々に、その 親ノードのバッファが、一つの空き記憶スペースを有するようになるか、その子 孫ノードがそれに送られるべきパケットを有しなくなる迄、伝送するステップ； （ｂ）或る親ノードのバッファが、一つの空き記憶スペースを有するようになる か、その子孫ノードがそれに送られるべきパケットを有しなくなることに応じて 、その子孫ノードにその親ノードから、その子孫ノードの各々がそれに、その子 孫ノードのバッファに前以て記憶されていた、そのパケットが送信プロセッサか ら受信プロセッサに向かう接続を延長するために、その親ノードから送られるべ きことを要求するアドレス情報を含むパケットを、チャンネル・アップ・リンク を通じ、送ることを試みても良いと合図するステップ；および（ｃ）ステップ（ ｂ）に述べられた試みが、その親ノードの子孫ノードの与えられた一つによる現 行手順決定サイクルの間に、或るパケットがその時、その親ノードにその子孫ノ ードの他のバッファから送られてきたために、達成出来ない場合、その現行手順 決定サイクルの間、その親ノードの子孫ノードの、その与えられた一つのバッフ ァからのパケットを、その親ノードの前記子孫ノードのその他のバッファに記憶 させるために伝送するステップ。
2. ２．単一命令・多数データ（ＳＩＭＤ）大量並列プロセッサ・コンピュータにお いて、アドレス情報を含むデータのパケットを、前記コンピュータの引き続く手 順決定サイクルの間、前記コンピュータの並列プロセッサの任意の一つと前記コ ンピュータの並列プロセッサの他の任意の一つとの間で手順決定するための手順 決定方法であって；そこでは前記コンピュータが、４０９６個の並列プロセッサ 群を含み、それらが、ノードの三つの階層レベルと一つの相互連結チャンネルの ネットワークとを有する、階層プロセッサ相互連結トリ−構造の葉を形成してお り；前記階層プロセッサ相互連結トリ−構造の前記第三レベルは、８個のノード を含み、そこで前記第三階層レベルの前記８個のノードの各々は、第二階層レベ ルにおける８個の子孫ノードのクラスタの親ノードであり、且つ前記第二階層レ ベルにおける８個の子孫ノードの前記クラスタの各々は、第一階層レベルにおけ る６４個の子孫ノードのクラスタの親ノードであり；前記第一レベル・ノードの 各々は、前記ネットワークのチャンネルによって、前記４０９６個の並列プロセ ッサ群の別々の一つと個別に相互連結されており、第一階層レベルにおける子孫 ノードの各クラスタは、前記ネットワークのチャンネルによって、第二階層レベ ルにあるその親ノードと相互連結されており、第二階層レベルにおける子孫ノー ドの各クラスタは、前記ネットワークのチャンネルによって、第三階層レベルに あるその親ノードと相互連結されており、且つ第三階層レベルのノードの各々は 、前記ネットワークのチャンネルによって、第三階層レベルの他のノードと相互 連結されている；更に、全ての前記ネットワーク・チャンネルは二重の単方向性 リンクで、二つのパケットの反対方向への同時伝送を可能としており；且つ各ノ ードは、（１）そのノードで終結するネットワーク・チャンネルの合計数より一 多いパケットを記憶する記憶容量を有するバッファ、および（２）前記並列プロ セッサ群の送信する一つでそのノードから起源し、前記ネットワーク・チャンネ ルを通じ前記並列プロセッサ群の受信する一つに向かう接続を、そのノードのバ ッファに記憶されたパケットに含まれたアドレス情報に従って、延長するための ルーターを含むものであり；更に前記手順決定方法は、前記コンピュータの前記 引き続く手順決定サイクルの各々の間に、次のステップを含んでいる：（ａ）階 層プロセッサ相互連結トリ−構造の各親ノードにおいて、その親ノードのバッフ ァに記憶され、送信プロセッサから受信プロセッサに向かう接続を延長するため に、その子孫ノードに送られるべきことを要求するアドレス情報を含むパケット を、チャンネル・ダウン・リンクを通じ、その子孫ノードの各々に、その親ノー ドのバッファが、一つの空き記憶スペースを有するようになるか、その子孫ノー ドがそれに送られるべきパケットを有しなくなる迄、伝送するステップ； （ｂ）或る親ノードのバッファが、一つの空き記憶スペースを有するようになる か、その子孫ノードがそれに送られるべきパケットを有しなくなることに応じて 、その子孫ノードにその親ノードから、その子孫ノードの各々がそれに、その子 孫ノードのバッファに前以て記憶されていた、そのパケットが送信プロセッサか ら受信プロセッサに向かう接続を延長するために、その親ノードから送られるべ きことを要求するアドレス情報を含むパケットを、チャンネル・アップ・リンク を通じ、送ることを試みても良いと合図するステップ；および（ｃ）ステップ（ ｂ）に述べられた試みが、その親ノードの子孫ノードの与えらたに一つによる現 行手順決定サイクルの間に、或るパケットがその時、その親ノードにその子孫ノ ードの他のバッファから送られてきたために、達成出来ない場合、その現行手順 決定サイクルの間、その親ノードの子孫ノードの、その与えられた一つのバッフ ァからのパケットを、その親ノードの前記子孫ノードのその他のバッファに記憶 させるために伝送するステップ。