JPH07509085A - 統一されたパラレル処理アーキテクチャのための方法と装置 - 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. ２６．上記バッファ手段は、２Ｎ＋１の大きさを有し、ここで、Ｎは、上記クロ ック信号とデータ信号が伝送される構成要素間通信パスにおける伝送の不確定性 であり、 上記ライトポインタ手段と、上記リードポインタ手段とは、上記バッファ手段に おいて、少なくともＮ個の記憶ロケーションだけ間隔をおいて離れておかれる請 求項２５記載の拡張可能なクロック機構。