JPH06502033A - スカラブル パラレル ベクトル コンピュータシステム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 スカラブルパラレルベクトルコンピュータシステム＆−二立野 本発明は、高速デジタルデータ処理システムに関し、より詳しくはベクトル処理 に対して採用されるスカラブルマルチブロセノサによるスーパーコンビニータン ステム関する。

介■五宣旦 膨大な科学データの処理作業には、整列されたデータアレイの拡張的な算術上の 操作か含まれる。一般に、この種の操作又は“ベクトル”処理には、セットした データの各々の連続的な要素に対して繰り返し的な同一の動作が含まれる。はと んどのコンピュータは、メモリおよび入出力部と交信できる、単一の中央処理ユ ニ、）（ＣＰＵ）で構成される。数学関数を実行するために、各オペランドは、 メモリからＣＰｔＪへ連続的に供給して、関数が実行され、そして処理結果をメ モリに転送しなくてはならない。しかしながら、指示やデータがメモリユニット からフエ’７チできる時間よりも短い時間で通常、ＣＰＵが指示やデータを処理 する。

この“メモリ固有の呼び出し時間”は、指示やデータがメモリから引き出される ための待時間のために多くのロス時間をＣＰＵに対して与える結果となる。この 種の機構、つまり、“スカラー”マシーンを利用する装置は、余りにも処理速度 が遅く、かつ、大規模な処理に対して実際に使用されるためには非効率なハード ウェアとなることが見いだされている。

整列されたデータアレイを扱う時に、処理速度を増し、ハードウェアの効率化を 図るために、“ベクトル“マシーンが開発されている。ベクトルマン−７は、そ のハードウェア機構の利点により整列されたデータアレイを処理するものであり 、これにより、スカラーマシーンよりも高速の処理速度を得ている。このような ベクトルマシーンの一つに、クレイ社による１９７８年１０月５日公告の米国特 許４．１２８．８８０があり、その開示を参考としてここで述べる。

クレイ社特許のベクトル処理マ／−ンは、ベクトル処理を実行するために特に設 計された３つのベクトル関数ユニットを有する単一プロセッサの装置である。

そのクレイ特許は又、８組みのベクトルレジスタを提供している。ベクトル処理 はベクトルレジスタからのデータを用いて直接に実行できるので、同一データの 繰り返し演算が要求される場合には、メモリアクセス（およびこれにより、メモ リ固有の呼び出し時間による遅延）における実買的な低減要求が達成される。

クレイ特許は又、指示およびデータを、隠しメモリ固有の呼び出し時間として、 予めフェッチ（ブリフェッチ）する手法を採用している。このテクニックは“パ イプライン“として知られ、プログラム指示のブリフェッチおよび、先の指示が 実行されて０る間に、ｎ長の指示“バイブの一端へのそれらの書き込みを含む。

前記指示の実行に対して必要な対応するデータも又、メモリからフェッチされ個 別データのパイプラインまたは“チェイン”の一端に書き込まれる。この結果、 指示がバイブの最終読み出しに到達する時間により、メモリから検索されるべき 実行に対して必要にデータが、データチェインの最終読み出しからの処理のため に、直ちに利用できる。指示のパイプライン化およびデータのチェイン化により 、実行時間の殆どをメモリフェ、チ時開とオーパーラ、ブすることができる。こ の結果、ブロモ、すの怠は時間が大幅に低減される。

マルチプロセッシング技術の使用により、スカラーおよびベクトルマシーン双方 でのコンピュータの処理速度および効率を更に向上することができる。マルチプ ロセッシングは、メインメモリのごとく、システムの資源を共用する二つまたは より多くのプロセッサの使用を含む。異なった仕事または一つの仕事での関連し た仕事の独立した仕事がマルチのプロセッサで実行されてもよい。各々のプロセ ッサは、自身の指示に従い、そして、プロセッサはそれらの指示を同時（″並列 ”）に行う。プロセッサおよび並列動作するブロモ／すの数を増すことにより、 より短い期間により多（の仕事を達成することができる。

Ｃｈｅｎの９４２の二つのプロセツサマンーンの別の態様として：ま、Ｃｈｅｎ およびその池による１９８７年４月２８日発表の米国特許４．６６１．９００が あり、参考としてここで述へる。４つのプロセッサを用いたマルチブロセノノノ グベクトルマ／−ン七しては、Ｓｃｈｉ（ｆｌｅｇｅｒによる１９８８年５月１ ７日発表の米国特＃４．７４５．５４５および、Ｐｒｉｂｎｏｗによる１９８８ 年６月２８日発表の米国特許４．７５４．３９８に開示されており、それらの双 方の特許を参考としてここで述べる。上述したすべての特許はクレイ　リサーチ 社に譲渡されている。

本発明の謬受入であるクレイ　リサーチ社からの別のマルチブロセｌンングベク トルマノーンは、Ｙ−ＭＰベクトルスーパーコンピュータがある。そのＹ−〜１ Ｐの様式の詳細な説明は、１９８９年２月７日出願の０７／３０７．８８２のタ イトル名“Ｙ−ＭＰのためのメモリアクセスの矛盾を解決するシステム”の特許 出願に見ることができ、ここで参考として述べる。Ｙ−ＭＰの設計において、各 ベクトルマンセ、す：よ、指示の実行のために一つのパイプラインを持つ。各プ ロセッサは、完全に接続されたトボロジイ内の共通のメモリにアクセスするのて 、同じエリアにアクセスしようとするブロモ、す間の避けられない衝突が起きる 。そのＹ−ＭＰは、衝突を最小にするために衝突回避／ステムを用い、かつ、矛 盾を可能な限り迅速に解消する。矛盾解ｌ１ｉｌ／ステムは、衝突を解決するも のの内蔵のプロセッサを非活性にし、かつ、ベクトルを封じ込める。プロセッサ は衝突を回避するために待たなくてはならず、それ故、衝突はブロモ、すに怠は 時間を生じさせる。

この問題のために、Ｙ−ＭＰのスーパーフンピユータは、単に８個の比較的少な いベクトルプロセッサに制限される。より多くのプロセッサを含むためにＹ−Ｍ Ｐの設計を拡張することは、ブロモ、す間のメモリアクセスの矛盾数を増加させ 、これにより、プロセッサに怠は時間を増加させる。Ｙ−ＭＰ様式は、それ故、 システム内に数百または数千のブロモ、すを持つことが望ましい、大量の並列ベ クトル処理に適していない。

マルチプロセッシングは、実行速度を増大するが、その増大は用いられたプロセ ッサの個数とリニアに関係しない。これはおおまかに二つのファクター　管理調 整用時間および“ロックアウトに起因する。プロセッサおよびプロセッサ機能を 調整するのに要求される制御および同期のレベルが増大するため、重要な管理調 整用時間は、マルチプロセッサ環境では導入されている。両者の交信およびすべ てのブロモ、すの制御は、マルチプロセッシングのシステムに対して性能の低下 をもたろす。仕事を実行するためにいくつかのプロセッサが共動するとき、両者 のデータの従属およびプロセッサ間のデータの通過は、避けられない。一つのプ ロセッサが、別のブロモ、すからのデータが当該ブロセ、サヘ通過する時間を待 たねばならない時にプロセッサの怠は時間が生じる。システムの性能はこれによ り低下する。

マルチプロセッサ／ステムの性能低下の他の重要な要因は、共通の資源を共用す るマルチプロセッサにつきもののプロセッサのロックアウトまたは“ブロッキン グである。これは、一つのプロセッサが、既に別のプロセッサが使用している共 用の資源をアクセスしようとした時に起きる。そのプロセッサは、これにより、 共用の資源の使用がブロックされ、他のプロセッサが完了するまで待たなくては ならない。再びプロセッサの怠は時間が生じ、システムの性能が低下する。

上述した技術の付随的な欠点は、一つのバイブラインの仕事を極めて高速に解決 する方向に向けられ、それ故、多くの仕事において、高いレベルの固有のバラレ リズム（同時処理）の利点を得ることができない。

いくつかのスカラーマルチブロセッシングマノーンは、別の様式のバラレリズム をマシーンに導入することにより、より大きな性能を得ようと試み発展してきた 。各々が一つの指示流れを有する、幾つかのブロモ・ノサを用いた標準のマルチ プロセッシング技術を用いるよりもむしろ、これらのスカラーマシーンが、各々 が多数の指示流れ又は“スレッド（糸）”を有する、いくつかのブロモ／すを用 いる。計算及びメモリ呼び出し時間は、プロセッサ内のスレッド間の“文脈（Ｃ ｏｎｔｅｘｔ）スイッチ“によりカバーされる。そのような７７−ンの一例とし ては、Ｄｅｎｅｌｃｏｒ　Ｈｅｔｅｒｏｇｅｎｏｕｓ　Ｅｌｅｍｅｎｔ　Ｐｒｏ ｃｅｓｓｏｒ（ＨＥ　Ｐ）がある。

Ｄｅｎｅ】ｃｏｒ　ＨＥ　Ｐは、各々が１２８までのバイブライン化された指示 スレッドを有するプロセッサを１６個まで保有する、スカラーマルチブロセノン ングマノーンである。各スレッドは、レジスタおよび機能的ユニットの目的のた めに自身のプログラムメモリを備える。そのＨＥＰ文脈スイッチは、プロセッサ 内のマルチのスレッドの時間切りにより、つまり、各クロックサイクル毎にプロ セッサがスレッドをスイッチすることにより、完成される。各クロックサイクル 毎に、円状に配列された次のスレ、ドが指示を出すことを許可する。ｎクロック サイクル後、すべてのｎ個のスレ、ドが指示を出すことを許可される。り０／ク サイクル（ｎ＋１）でプロセッサは文脈を第１のスレッドヘスイッチバックして そしてそれ自身の処理を繰り返す。例えば、１６スレノドの文脈切り替えプロセ ッサは、特定のスレッドが各１６の連続したクロックサイクルにアクティブとな るので、１５またはそれ以下のクロ、り期間長である、あらゆる呼び出し時間を 効率的に隠す。

Ｄｅｎｅｌｃｏｒ　ＨＥＰの文脈切り替えの機構は、短いメモリ呼び出し時間を 相対的に隠すことができるが、スレ、ドの個数よりも長い呼び出し時間は、長引 くデータの依存状況または、共用の資源を一つ以上のブロモ、すがアクセスしよ うとすることに起因するブロックのために、その分割時間の間にスレッドが通過 する結果となる。例えば、高速のクロック／ステムでは、メモリは、プロセッサ の最良の場合の状況から“隔たった”３０又はより以上のクロックサイクルであ る。そのようなシステムは、メモリアクセスの呼び出し時間をカバーするために 、３０またはより多くの独立したプログラムのスレ、ドを必要とする。もし、よ り少ないスレ、ドが使用されたならば、ブロックされたスレッドへの多くの無駄 なリターンが起きる。この結果、プロセッサに怠は時間および対応して性能の低 下が起きる。

ＨＥＰにおけるこのプログラムは、スレッド数を増加することにより解決される ことは明白であるが、その解決は他の問題を提起させる。第１に、オペレートの システム管理が、ブロモ、すのプロセッサ数が増大するにつれてより複雑となる 。第２に、１６個のプロセッサを効率的に使用するために、十分に関係してい多 くの困難を持つ。このため、一つのプロセンサが、最適なスレッド数より少ない 状態でしばしば実行する。この結果、処理のために再度スレッドが選択されるた めの時間によって、読み出し時間およびデータの依存状況が解決されないといっ た同様な９とが次に増大する。

ＨＥＰの文脈切り替えによる時間分割の性質は、更にＨＥＰの使用を制限する。

単純な時間分割技術における信頼は、計算およびメモリ呼び出し時間が固定され たという仮定に基づいている。しかしながら、これは、種々の呼び出し時間があ るマルチプロセッサの環境下では典型的な場合ではない。

更には、ＨＥＰが、最大で１６個のみのプロセッサを有する、スカラーマシーン であるので、多数のスカラーベクトルを有する仕事の処理に適していない。ベク トル演算を行うためには、スカラーマシーンがより多（の指示およびより多くの データを要求するので、ＨＥＰで実行されるベクトル動作は、より長く、がっよ り多くの非効率に実行する。又、ＨＥＰの設計が比較的少ないプロセッサ数（１ ６）に制限されるため、その設計を、数百または数千のプロセッサを持つことが 望ましい並列処理様式に拡張することはできない。

スカラーマルチプロセッサ／マルチスレッドのマシーンの他の例としては、スー パーコンピユーテイングリサーチセンターおよびテラコンピューターカンパニー での研究による水平概念の様式がある。水平様式は、その前身、前述したＤｅｎ ｅｌｃｏｒＨＥ　Ｐの様式と密接に関係しており、そこでは各プロセッサは＋２ ８までのバイブライン化した指示スレッドを何し、かつ、文脈スイッチは、各マ ン−７サイクル後に起動する。又、水平様式における各スレッドは、自身の一般 的な目的レジスタ、プログラムカウンタおよびプロセッサ状態を有する。

両者の基本的な差異の−っは、ＨＥＰが僅かに１６個までのプロセッサを有する のに対して、水平様式は２５６から１０２４個までのプロセッサを有することで ある。しかしながら、その様式がＨＥＰ様式と密接に関係しているので、ＨＥＰ に見い出される欠点の殆どが水平様式に今なお存在する。再び、プロセッサ当た りの多数のスレッド数の要求、多数の関連しないプログラムスレッドに見い出さ れる困難、固定した呼び出し時間の仮定、およびスカラーマ７−ンの限界に含ま れる問題が、大容量のスカラーベクトルブロセ、ノングの仕事の使用に対して、 水平様式の望ましい選択を少なくする。

７ンーン性能に全体的に影響するマルチブロセ、ンングマシーンの別の態様は、 メモリインクフェイスに対するプロセッサである。マルチプロセッサインタフェ イスの疑問に対する一つの解決は、ＢＢＮシステムおよびテクノロジ−コーホ１ ４フ 見いだすことができる。そのモナーチは、スカラー、単一スレッドのマルチブロ セノ７ング様式であり、ブロモｌすとメモリとで交信するために“回路切り替え ”と呼ばれる技術を用いる。回路切り替えのインタフニイス機構では、すべての プロセッサがメモリに対する同一の経路を共用する。モナーチ設計におけるプロ セッサがメモリ要求を持った時、プロセッサネットワークからメモリへの全体経 路が開放され、メモリおよびプロセッサか交信を終了するまでその開状態が維持 される。この機構は、回路切り替えネットワークを通じてメモリを参照しようと する他のプロセッサを抑制して、レファレンス転送速度を制限し、プロセッサの 多（怠は時間を生じさせる。このような設計は、それ故、大量のデータがブロモ 。

すとメモリとの間で転送されるマルチブロモ，す、マルチスレッド、ベクトルブ ロセノ／ングにおける使用に対して実際的できない。

マルチプロセッサメモリインタフェイスに対する別の解決は、水平手順性機構に 見いたすことができる。水平インクフェイスネットワークは、絶望手順法または ホットポテト手順法と呼ばれる機構を用いる。水平の絶望手順法は、マルチの入 力部および等価な出力部を有する。この手順法の機構は、各ネ，トワークサイク ル毎に、各入力部が出力部への手順を得ることである。例えば、もし４個のレフ ァレンス人力部かあり、その４個のレファレンス入力部が同一の出力を得ようと しているならば、４個のレファレンス入力部の一つが正しい選択を得て、そして 他のすべての入力部が他の所望されない選択を得る。これは、４個の入力部から ３個のへ内部が、ネットワークを通じてより多数の経路を取ることを意味する。

水平絶望ネットワークは、これらの他のレファレンスが所望の入力部に戻り、そ して、他の機会が所望の出力を得るように、手順化される。レファレンスがネッ トワーク内で決して消失しないように、水平手順化機構は、より長いレファレン スがネットワーク内に存在するような機構を持ち、結果的に同一出力に対して文 脈のレファレンスに打ち勝つようその優先度が上昇する。当業者であれば、この ような手順化機構は、単一のレファレンスが、所望の終端にいかに得るかのマル チの可能性を持つ結果となり、多くのレファレンスがネットワーク内で交通と衝 突するために長い時間を費やす。この結果、水平絶望手順化機構は、マルチスレ ッド化のベクトルブロセク／ングマ／−ンに使用することにも適していない。

それ故、ベクトルブロセノンングの利点を持ち、大容量のスカラーベクトルブロ セ，シノグの仕事においてバラレリズム固有の程度を極めて高くできる利点を更 に得るために、そして、オペレートシステムまたはプロセッサの拡張的な再設計 を必要とすることなく、任意のプロセッサ数で容易にスカラー計算できる、コン ピュータマシーンに対する必要性がある。

茜■Ω旦！ 上述した限界を克服するために、また、本明細書を読み理解することにより明ら かになる他の限界を克服するために、本発明は、関連しない多数のプログラムス レッドが同一のプロセッサ内て指示を実行できる、ベクトルブロセノンングのた めに適用されたスカラブルマルチブロセノサスーパーコンピュータマノーンを提 供する。コンビ二一夕は、いずれの個数のブロモ、すで構成することができ、モ ジュラ−の様式の性質は、単純な返答によってマンーンのいがなるスカラーの命 令をも許可する。

この様式は、関係しない多数のプログラムスレッドが同一のプロセッサ内で指示 を実行できる、構成を共用する資源を実行する。多数のスレッドの一つのみがい ずれかの時間でアクティブとなり、そして、メモリの衝突に起因する出力のブロ ックが生じるまでアクティブとなる。プロｌりが起きた時、プロセッサは現在の スレッドを非アクティブにし、そして文脈を次のスレ、ドに切り替える。各スレ ッドはロックが起きるまで実行が許可されるので、又、システムがベクトル処理 のために設計されているので、好ましい実施例における計算およびメモリ呼び出 り時間をカバーするためには、はんのわずかな関係しないプログラムスレッドが 必要となる。以前のマンーンでの可能な処理量より、少ないスレッドを育するよ り高い情報処理量がこのようにして得られる。

キーンステムの設計仮定は、マルチのプログラムスレッドからの関係しないコー ドを実行することにより、マルチスレノド化の文脈切り替えブロモ、すがメモリ アクセスの呼び出し時間をカバーしている。プロセッサ内で他のスレッドと関係 していないコードを有する各スレッドを動作させることは、文脈スイッチに起き るブロックがローカル（特定のスレッド）であり、プロセッサ内の他のスレッド の実行に影響を与えない。特定のスレッドは、それの解決されたブロックを持ち 、円の実行サイクル内で池のすべてのスレッドがターンした後、青変、アクティ ブにされることが期待される。

本発明の様式に用いられた共用されたメインメモリは、いくつかのメモリバンク に分割される。ブロモｌすはマルチ階層のクロスバー不／トワークを通じて共用 されたメモリと交信する。そのクロスバ−ネットワークは、各プロセッサからメ モリへのボートの独立を保持する。プロセサ間の交信および同期は、共用された メモリに位置する共用されたレジスタの使用を通じて、そして特定の指示を用い てクロスバ−ネットワークを通じて達成される。

図面の説明 図面において、いくつかの図を通じて同様なエレメントには同様な番号を付し図 ２は図１に示した階層の一つのより詳細なプロ、り図。

図３Ａおよび３Ｂは本発明の好ましい】実施例に使用されたタイプのプロセッサ のブロック図。

図４Ａ、４Ｂおよび４Ｃは本発明のプロセッサ部分に対する入力回路のブロック 図。

１ＺＩ５Ａ、５１よび５Ｃは本発明のプロセッサ部分に対する出力回路のブロッ ク図。

図６は図１に示した点線に沿った４×４のクロスバ−スイッチのより詳細なブロ ック図。

図７Ａおよび７Ｂは、本発明の−に使用されたタイプのメモリボードのブロック 図。

好ましい　絶倒の詳細な説明 好ましい実施例の以下の好ましい実施例において、記述は、発明の一部を形成す る添付図面に対してなされ、その図面には、本発明が実行される特定の実施例の 方法により示している。本発明の本旨からそれることなく、他の実施例が用いら れ構成されてもよく又は論理的な変化か適用されてもよいことが理解されるであ ろう。以下の詳細な記述はそれ故、限定した意味に取られることなく、本発明の 本旨は付記したクレームにより限定される。

さて図１を参照すると、本発明の全体様式を簡略化したプロ／り図を示す。図１ は、いくつかのクロスバ−ネットワーク４００を通じてコモンメモリ６００（こ インタフェイスされたマル壬のプロセッサネットワーク１００を示す。本発明の 好ましい実施例では、プロセッサネットワーク１００内の個々のプロセッサ（不 図示）は、コモンメモリに対する３個のボートＡ、Ｂ、Ｃを持つ。プロセッサ側 から見た時、メモリ容量を最小にし、かつ、プロ、キングするために、３個のボ ート経路は、コモンメモリ６００へのすべての経路で分割される。これは、各ボ ート−に対して、点１１１４４０で示した自身の分離した本国行きのクロスバ− ネットワークおよび点線４２０で示した外国行きのクロスパーネットワークに委 ねることにより達成される。（“外国行き”クロスバー不、トワークはプロセッ サからメモリ関連を扱い、他方、“本国行き”クロスパーネットワークはメモリ からプロセッサ関連を扱う。）例えば、ブロモ、すネットワーク１００における 個々のプロセッサよりの、プロセッサからメモリ関連に対するすべてのボートＡ を外国行キの経路４０２に委ねる。プロセッサからメモリレファレンスに対する すべてのボートＢを外国行きの経路４０６に委ねる。同様に、メモリからプロセ ッサレファレンスに対するすべてのボー）Ａを本国行きの経路４１２に委ねる、 等である。

本国行きおよび外国行きポート経路のすべてが分離しているので、本発明の設計 は、すべてのブロモ、すからの３個すべてのボートがメモリに対して同じアクセ スに対して争うようした設計に対して偉人な利点を持つ。後者のタイプの設計で は、３個すべてのボートがメモリに対して同じ経路を共用する場合で、次のボー トまたはプロセッサがブロモ、すからおよびメモリへの途中にメモリレファレン スを得ようとした時、メモリ経路が抑えられる。本発明の設計では、しかしなが ら、３個すべてのボートか委ねられた本国行きおよび外国行きクロスバ−ネット ワークの双方を持つので、経路が抑えられる可能性は極めて低い。それ故、ボー ト関連が互いに争わないため、ボートはプロセッサから出て行くことができる。

この結果、本発明の設計は、メモリ経路の争いおよびプロセッサの見地からのブ ロックを低減し、当業者には容易に理解できるように、別の設計に対しても偉人 な利点をもたらす。

本発明の好ましい実施例では、プロセッサネットワーク１００内の個々のプロセ ッサが３個のレファレンスボートを持つが、当業者であれば、各プロセッサが随 意の個数のレファレンスポートを含むことができることを理解できるであろう。

例えば、もし、プロセッサ当たりのレファレンスポート数が１０に増加されたな らば、本国行きのクロスバ−ネットワーク４００の個数も１０に増加され、外国 行きのクロスバ−ネットワーク数も１０個に増加され、その結果、レファレンス ポートの各セットは、自身の分離した本国行きおよび外国行きのメモリ経路を持 つ。当業者であれば、本発明の本旨からそれることな（、プロセッサ当たりいく つの個数のレファレンスポートを使用してもよいことが理解されよう。

図２は、単一のプロセッサからメモリへのクロスバ−ネットワーク４００のより 詳細なブロック図である。特に図２は、単一のマルチ層によるクロスバ−ネット ワーク４００を通じて、コモンメモリ６００にインタフェイスされた本発明の１ ６個のプロセッサのバージョンを示す。図示したクロスバ−ネットワーク４００ は、すべてのボートＡのプロセッサレファレンスに対する、外国行きのブロモ・ ／すからメモリへのクロスバ−ネットワークである。本発明の十分な実施例にお いて、図１におけるボートＢおよびＣに対するものと同じ外国行きの２１１以上 のクロスバ−ネットワークが存在し、又、３つのボートの各々に対して本国行き のレファレンスを扱うために３個以上の同一のクロスパーネットワーク４００を 有す本発明の様式は、容易にスカラ演算できるように設計されているので、当業 者にとっては、本発明を随意のプロセッサ数でもって構成できるということを容 易に認識しかつ理解できるであろう。しかし図面の簡略化のために本発明の実施 例では単に１６個のプロセッサを図２に示した。

本発明の好ましい実施例では、コモンメモリ８００は、メモリボード８００に分 割され、クロスバ−ネットワーク４００の最終階層における終段出力につき一つ のメモリボードが存在している。これにより、図２に示した本発明の１６個のプ ロセッサは６４個のメモリボード８ｏｏを含む。

本発明や好ましい実施例では、クロスバ−ネットワーク４００の各階層は、４× ４個のクロスバ−スイッチ５００のモジュールにより構成される。各クロスバ− スイッチ５００は、４つの入力部の一つからのデータを４つの出方部の一つに向 ける能力を持つ。プロセッサネットワーク１００と、本発明の４つのプロセッサ とした実施例（不図示）に対するコモンメモリ６００との間のクロスバ−ネット ワーク４００は、４×４個のクロスバ−スイッチ５００による単一の階層からな る。図２に示した本発明の１６個のプロセッサとした実施例は、クロスバ−スイ ッチ５００による２階層からなる。クロスバ−スイッチ５００の一つの階層は、 最終のものより４倍幅広く、このスイッチ５ｏｏは、プロセッサ１０１およびメ モリバンク８００の数が４だけ増加するように、ネットワークに加入される。こ れにより、本発明のプロセッサ１０２４個とした実施例は、４階層のクロスバ− λイノチ５００からなる。

本発明の好ましい実施例は、４×４個のクロスバ−スイッチ５００を使用するが 、当業者であれば、クロスバ−スイッチ５００は随意の個数の入力部および出力 部で構成することができることを容易に理解できるであろう。例えば、本発明の クロスバ−ネットワーク５００は、８Ｘ８．２Ｘ２．２×４．４×２等で構成す ることができる。更に当業者であれば、メモリボードに対するプロセッサの比率 は、クロスバ−スイッチ内の入力部および出方部の個数の変化に応じて変えるこ とができることを理解できるであろう。これらの当業者は、本発明の本旨から逸 脱することなく、特定の実施例のために別の他の実施例を代用することができる ということを理解できるであろう。これらの当業者であれば、本発明のモジュー ラ一方式および拡張性が様式内で固有である故に、これらは、実行のために選択 された技術と無関係である。

プロセッサの設計 図３Ａおよび３Ｂは、本発明に使用されたタイプのプロセッサ１０１のブロック 図を示す。本発明の好ましい実施例では、プロセッサ１０１は、本発明の譲受人 であるクレイリサーチ社製造の改良クレイ２型ブａセツサである。

各プロセッサ１０１は、８個の指示パイプラインまたは“スレッド”　１１０ａ −ｈの組みを含む。各スレ、ド１Ｉｏａ−ｈは自身に与えられた８個の指示バ。

ファ１１２を有する。その指示バッファは、高速の指示メモリによるブロックで あり、各スレッドに対して指示パイプラインを形成する。単一スレッド化マシー ンであるクレイリサーチ社の１組みの指示バッファの動作は、同一の譲受人に譲 渡されたクレイ社により１９７８年１２月５日に出願された米国特許４．１２８ ゜８８０により詳しく開示されているので、参考としてここで述べる。

本発明は、プロセッサ内のスレッド間の文脈切り替えにより、／ステムの呼び出 し時間を隠す。本発明は、“要求に応じた”文脈切り替えの手法を使用し、プロ セッサ１０１は、出力を停止するために、スレッドがコモンメモリよりのデータ に依存性を見い出さない限り、特定のスレ、ドを実行する。本発明の好ましい実 施例のプロセッサは、スレッドがコモンメモリから受け取ったものでないデータ により起きた出力保持状態に遭遇した時のみ、文脈を切り替える。指示が、コモ ンメモリからメモリ位置へのロードのために用意されたレジスタの使用を呼び出 した時、あるいは、プロセッサがコモンメモリからの合図信号を待っている時（ つまりブロモ／す同期のための遅延）に、そのような状態が起きる。ブロモ、す がコモンメモリに読み出しまたは書き込みを試みた時に起きるボートのプロ、り は、文脈の切り替えを生じさせない。スレッドがコモンメモリからのデータを使 用しようと試みている時および、そのデータがまだ受け取っていない時のみ、文 脈切り替えが起きる。一旦、ブロックに出会うと、ブロモ、す１０１は、現在の スレッドを非アクティブにし、文脈を円の順における次のスレッドに切り替える 。

スレッドは、コモツメモリからの出力ブロックに依存するデータのすべてが解決 されるまでは、スレッドはプロセッサへ文脈切り替えは起こらない。

例えば、仮想のプロセッサｌｏｔがスレッド１１０ａをアクティブにする。次に プロセッサ１０１は、コモンメモリよりの出力データのブロック状態が発生する まで、スレッド指示バッファに含まれるスレッド１１０ａ内の指示を実行し、そ の時点て、ブロモ、すはスレッド１ｌｏａを非アクティブにし、スレッド１１ｏ ｂのブロックのすべてが解決されたかを調べ、もし解決されたならば、文脈は次 のスレッド１１０ｂに切り替わる。プロセッサ１０１は、コモンメモリよりの出 力データのブロック状態が発生するまで、スレッド指示バッファに含まれるスレ ッド１１０ｂ内の指示を実行し、スレッド１１０ｃのブロックのすべてが解決さ れたかを調べ、もし解決されたならば、文脈は次のスレッド１１０ｃに切り替わ り、そのように続く。スレ、ド１１０ｈからプロセッサ１０１は、スレ、ド１］ Ｏａに文脈を戻す。上述の例で、スレッド１１０ａがブロックに遭遇した時、ス レッド１１０ｂが解決されたそのブロックを持たないならば、プロセッサ１０１ は、スレッド１１０ｃのブロックのすべてが解決されたか否かを単にチェックし 、もしそうならば、文脈をスレッド１１０ｃ、その他に切り替える。ブロモ。

す１０１は、プログラムの実行が遂行されるまで、この円の様式内でスレッドを 切り替えることを継続する。

本発明の好ましい実施例では、各プロ七ノサ１０１内のスレッド１１０の個数は 、一つのスレッドから別のスレッドに文脈切り替えを生じさせるプロ／りが、プ ロセッサ１０１が実行のために再度特定のスレッドを選択する時間によって解決 されることを確実とするために、８個に選択される。データ依存状態に関係する すべてのメモリの解決は、あらゆるスレッドがアクティブに留まる“典型的な” 時間合計である、プログラムスレッド時間以下で確実に行われなくてはなるない 。４×４のクロスバ−スイッチを用い、かつ、１３クロｌり期間のメモリバンク 号イクル時間と仮定した本発明の１６個のブロモ／すの実施例では、一つの平均 シングルメモリレファレンスの呼び出し時間がほぼ５３クロ／り期間であるとい うシミュレーンヨンが実証された。この結果、もし、システム内の各スレッドか 少な（とも７ブロック期間にブロックに遭遇することなく実行するなら、単に８ 個の関係したプログラムスレッドが、５３クロック期間の呼び出し時間をカバー するのに必要となる。本発明は、ベクトル処理を用いるので、単一ベクトル指示 は、６４クロ、りまでに対してプロセッサ資源は動作するが、当業者は、一つの スレッドが７またはより多くのクロック期間に対してアクティブとなる有利な条 件は大幅に改善される。たとえプロググラムが比較的小さいパーセントのベクト ルコードを含んでも（つまり、単一のスレッドがベクトル指示を含む）、はとん どすべての呼び出し時間は、まだ隠れている。それ故、本発明の好ましい実施例 におけるプロセッサ１０１固有のプログラムスレッドの数は、１６個のプロセッ サを有する／ステムに対しては８個が選択される。より多くのブロモ、すおよび ベクトルコードを同時に含む増加されたスレッド数を持つ高度のパラレルシステ ムでは、／ステムの呼び出し時間を十分に隠すためには単に４個のスレッドが必 要であるというノミュレーンヨンが実証された。当業者であれば、本発明に用い たプロセッサ当たりの比較的少ないスレッド数が、操作用システムの取り扱いお よびコンパイラの割り当て仕事に関連した／ステムの管理調整用時間を大幅に減 しることか理解されよう。　より少ないブロモ、すを存する別の実施例Ｊｉ、最 も大きいシステムのメモリ呼び出し時間が隠れている限り、より十分に役立つ。

本発明の他の別の実施例は、それぞれが異なった個数のスレッドを有する、異な った個数のプロセッサを結合することにより得てもよく、唯一の要求は、上記／ ステムの呼び出し時間が隠れているということである。当業者１ことっては、こ れらおよび他の実施例が、ここで述べた好ましい実施例と同じ目的を達成すべく 演算し、又、本発明の本旨から逸脱することなく、示した特定の実施例を置き換 えてもよいことが容易に理解されよう。

本発明の好ましい実施例では、文脈切り替えを行う単一のブロックは、メモリ読 み出しデータの依存性、分岐指示、またはプロセッサ同期の遅延である。設計に より、本発明の文脈切り替えのベクトルプロセッサは、処理時に起こるかもしれ ない、プロセッサへの内部パイプラインの呼び出し時間をカバーしない。しかし ながら、関数ユニットの呼び出し時間は、公知の値（浮動小数点の積算の呼び出 し時間または浮動小数点の加算の呼び出り時間のごとき）に固定されている。

完成したコンパイラ技術は、高い正確さを持つベクトル指示に隠れた、並列スレ ッド内のこれらの公知の呼び出し時間および隠れたスカラー指示に利点を持つ。

これにより、コンパイラは、文脈切り替えの利点を得るためにコードを最大限に 利用する極めた高い効率の仕事を行うことができる。関数ユニットの呼び出し時 間に起因して文脈を切り替えない別の理由は、ベクトル長のクロック期間に対し て大半の資源を忙しくするベクトルフードの十分な広がりの間に、無意味な文章 の“スピン（回転）”を防止し、これにより、すべてのスレッドに対し、あらゆ る指示を出力することを効果的に阻止する。

本発明のマルチスレッド化のブロモ、す設計は、又、それ自身特に、プログラマ −にコードの活用にうまく助力する。プログラマ−はプログラミング時に、コー ド実行時に起こるデータ依存性をしばしば知っているので、本発明のブロモ。

すの実行時の開に起こる文脈切り替えは、きわめてありきたりなことである。そ れ故、プログラマ−は、あるフードのスレッドが特定の時間にプロセッサの資源 の制御を完成させるので、本発明のマルチスレッド化した処理の利点を得るため に、最新技術を導入したプログラミング技術が適用され得る。例えば、プログラ マ−は、浮動小数点のベクトル加算を実行するためにコードを設計することがで き、文脈切り替えを生じない関数ユニットの呼び出し時間に起因する浮動小数点 の加算を待っている間に、その後、いくつかのスカラー指示をフードの後ろに隠 す。これを実行するために、プログラマ−は、スカラー指示が同じスレッド内に あり、そして直ちに浮動ベクトル加算に従うように単にフードを設計すれば良い 。

ブロセノ、す１０１内の各スレ、ドは、その完全なレジスタ資源の独立しかつ私 的なコピーを要求する。図３Ａは、プロセッサ１０１が８組みのアドレスレジス タ１２０ａ−ｈ、８組みのベクトルレジスタの組み１４０ａ−ｈを含む。各アド レスレジスタの組み（例えば組み１２０ａ）は、８個のアドレスレジスタ１２２ を含む。同様に、各スカラーレジスタの組み（例えば１３０ａ）および各ベクト ルレジスタの組み（例えば１４０ａ）は、８個のスカラーレジスタ１３２および ８個のベクトルレジスタ１４２をそれぞれ含む。アドレスレジスタ１２２、スカ ラーレジスタ１３２およびベクトルレジスタ１４２は、１９７８年１２月５日公 告のクレイ社によるタイトル名“コンピュータ　ベクトル　レジスタ　ブロセッ ンング“のＵＳ特許第４．１２８，８８０および１９８７年４月２８日公告のＣ ｈｅｎその他によるタイトル名“ＦＬＥＸＩＢＬＥ　Ｃ１（ＡＩ！ＩＩＮＧ　Ｉ ｌｌ　ＶＥＣＴＯＲＰＲＯＣＥＳＳＯＩ？　１１ＴＨ５ＥＬＥＣＴＩＶＥ　ＵＳ Ｅ　ＯＦ　ＶＥＣＴＯＩ？　ＲＥＧＩＳ丁ＥＲ３ＡＳ　０ＰＥＲＡＮＤ　Ａｎ　 Ｉ’１ＥＳＵＬＴ　ＲＥＧＩＳＴＥＲ３”に完全■Rン ピュータ　ベクトル　レジスタ　プロセ／シングのＵＳ特許第４，６６１，９０ ０に開示されており、これらの双方は、本発明の譲受人であるクレイリサーチ社 に譲渡されており、ここで参考として述べる。

つまり、プロセッサ１０１内の８個のスレッド１１０ａ−ｈの各々は、それ自身 に８組みのアドレスレジスタ！２０８−ｈ、８組みのスカラーレジスタ１３０ａ −ｈおよび８組みのベクトルレジスタ１４０ａ−ｈを持つ。これらのレジスタの 各組みは、スレッドに対して私的であり、それ故、本発明のブロモｌす＋０１内 の８組みの独立したレジスタの各々は、異なった指示スレッドに対応する。例え ば、アドレスレジスタの組み＋２０ａ、スカラーレジスタの組み１３０ａおよび ベクトルレジスタの組み１４０ａすべてが対応し、そして、スレッド１１０ａに 私的であり、アドレスレジスタの組み１２０ｂ、スカラーレジスタの組み１３０ ｂおよびベクトルレジスタの組み１４０ｂすへてか対応し、モしてスレ、ド１１ ０ｂに私的である、等。当業者であれば、各スレッドに対してレジ゛スタを用意 することは、マルチのスレッドが単一のレジスタの組みを共用する設計では、処 理速度および効率を増すことが理解されよう。該設計は、本発明の好ましい実施 例に使用され、そうでなくば、文脈切り替えが起こる毎に、各スレッドのレジス タ状態をセーブする処理に長く費やされる時間を排除する。

各スレ、ド１ｌｏａ−ｈは、本発明の文脈切り替えプロセッサのメモリ呼び出し 時間の隠れている能力故に、単に８種のレジスタ（アドレス、スカラーおよびベ クトル）を必要とする。当業者であれば、ブロモ、す当たりのレジスタの少ない 個数が本発明の好ましい実施例に用いられるプロセッサの複雑さおよび物理的な サイズを大幅に減じることが理解されよう。第１に、出力制御が大幅に簡略化さ れ、第２に、１６ビノト以上の指示単位が避けられ、これにより、バイブライン 化されたスレッドにより多（の指示を詰め込み、そして、指示のフェッチに起因 するクロスバ−内のネットワーク内におけるメモリのやりとりを低減する。

プロセッサ内の各スレッドは、その完全なレジスタの資源の、独立しかつ私的な コピーを要求するが、８通りのマルチ化回路に沿って、アクティブなスレッドと 関数ユニットとの間でデータを操作するために、すべてのレジスタの制御（ベク トル長およびアドレスカウンタ、保留フラグ等）の８個のフルコピーは必要でな い。当業者であれば、ブロモ、すの複雑さにおいて、マルチのスレ・ノド詰め込 みを最小にでき、かつ、ハードウェアレベルで劇的な効果を持つことになる、変 化する妥協レベルがあることが理解されよう。

例えば、本発明の一つの可能な実施例において、単一バンクのＲＡＭは、各レジ スタに対して使用され、ＲＡＭは、レジスタ内のエレメント数の数倍のスレッド 数とサイズが等しい。例えば、８個のスレッドのプロセッサ内のベクトルレジス タＶＯに対するＲＡ’、１は、８スレツドの６４倍のエレメントまたは５１２ワ ードの深さである。単一の基本アドレスレジスタは、ＲＡＭ内の６４エレメント 領域を指示することにより、アクティブなスレッドを選択する。このこの実行は 、スレッド指示器を除き、単一の文脈ブロモ／す以外に、レジスタ制御のノー− ドウエアを必要としないノ・−ドウエアの利点を持つ。現行のＲＡＭのみが成長 する。

この欠点は、いずれかのスレッドに対するＶＯ上の保留レジスタをすべてのスレ ッドに対して保留することである。文脈間のメモリ紛争に起因する不必要な出力 ブロックは、関数の資源がフリーであっても、付随的な従属レジスタにより引き 起こされる。

このレジスタは、この従属レジスタは、本発明の第２の実施例で回避することが でき、この第２の実施例では、各レジスタに対する複数の、＜ンクのＲＡＭが用 いられ、各バンクは更に、単一の指示器によって指示される複数のスレ・ノドの 組みを備える。上記単一バンクの例の改良は、２ノインクのＲＡＭを持つことで あり、その各々が４個のプログラムスレ、ドを含む。一方のノインクは偶数番号 のスレ・ノドを扱い、他のバンクは奇数番号を扱う。アクティブなスレッドは１ ．＜ンク間で切り替わる。連続的なアクティブのスレッドは、異なったノ〈ンク に属するので、従属スレッドは、最小化される。レジスタと関数資源との間に単 に、２組みのしする時、本構成の論理的な拡張により、文脈の増大する数を含む ことができる。

例えば１６スレノドが、各４スレツドの４バンク内に属することができ、または ６４スレツドが、８スレ、ドの８バンク内に属することができる。このような大 きい数の利用可能な文脈は、コンピュータに極めて大量のバラレリズムを許可し 、共用メモリの呼び出し時間を効果的に隠す。

本発明の好ましい実施例では、プロセッサ１０１は、アクティブスレッドからの １クロツク期間にっきｌ指示を実行し、又、ｌクロック期間につき２ＦＬＯＰＳ を実行する。これにより、例えば４ナノセカンドのクロック速度でもって本発明 の各プロセッサ１０１は、２５０ＭＩＰＳおよび５００ＭＦＬＯＰＳのピーク実 行速度ラフ可能である。４ナノセカンドの／ステムのピーク性能（プロセッサ１ ０２４個）は、２５６ＧｒＰＳおよび５１２ＧＦＬＯＰＳ（！：なる。５］２Ｇ ＩＰＳおよびＩＴＥＲＡＦＬＯＰの１０２４個のブロモｌすを有する対応するシ ステムのピークに対しては、２ナノセカンドのクロック期間で、プロセッサのピ ーク速度は５００ＭＩＰＳおよびＩＧＦＬＯＰである。１ナノセカンド設計のク ロック期間を持つシステムに対してはこれらの数値が２倍になる。

本発明の好ましい実施例では、各スレッド１１０ａ−ｈの各々は、小形ローカル 高速“スクラッチ　バッド”メモリ１６０ａ−ｈをアクセスする。もし必要なら ばレジスタは、これらのスクラッチバッドメモリ１６０ａ−ｈへ流し込むことが できる。又、スレッドの確認および管理に対する定数、テーブル値、タグ、その 他、も又そこへ保つことができる。スクラッチパッドメモリ１６０ａ−ｈへのア クセスはリアルタイムであり、それに関連した呼び出し時間は文脈切り替えを生 じない。

本発明のプロセッサ１０１の８個のスレッド１１０ａないしｈは、プロセッサ１ ０１内の関数ユニ、ト資源を共用する。個別のアドレス関数ユニット２００は、 アドレスレジスタ１２０ａないしｈの組みと関連し、スカラーレジスタ１３０ａ ないＬｈの組みは、スカラー関数ユニット２０２によりサポートされ、そしてベ クトルレジスタ１４０ａないしｈの組みは、ベクトル関数ユニット２０６により サポートされる。浮動小数点関数ユニット２０４は、スカラーおよびベクトルレ ジスタの組みによって共用される。当業者であれば、関数ユニット資源は、本発 明の本旨から外れることなく、図３Ａで示されたものより、より少ないか付随的 な関数ユニット動作を含むために拡張され得ることが理解されよう。本発明の好 ましい実施例では、すべてのオペランドは６４ビツト長である。

本発明の好ましい実施例における各プロセッサ１０１は、コモンメモリへの３個 のボートＡ、Ｂ、Ｃ（図１では不図示）を持つ。ボートＡは、マルチボートのベ クトルがメーモリレファレンスを読み出す時、およびＩ１０メモリがレファレン スを読み出す時に使用される読み出し専用ボートである。ボートＢも又、マルチ ボートのベクトルがメモリレファレンスおよび指示フェッチを読み出す時に使用 される読み出し専用メモリである。ボートＣは、読み出し／書き込みボートであ り、単一のボートベクトルの読み出し、ベクトル書き込み、スカラー読み出し及 び書き込み、およびコモンメモリへのＩ１０書き込みを扱う。各ボートは、二つ のメイン部、入力回路および出力回路を持つ。

図４Ａは、ボートＡの入力回路３００のブロック図を示し、図４Ｂは、ボートＢ の入力回路３０２のブロック図を示し、そして、図４Ｃは、ボートｃの入力回路 ３０４のブロック図を示す。読み出し時、メモリボートＡおよびＢ１入力回路３ ００および３０２のみがメモリから１クロツクにつき、８８ビツトデータ、１６ ビツトのバンクアドレス（失敗記録のための）、１６ビツトの行き先コードおよ び有効ビットからなる、■メツセージを受け取ることができる。読み出し／書き 込み時には、メモリ、ボートＣ１入力回路３０４は、メモリから１クロツクにつ き１メ、セージを受け取る能力を持つ。もし、オリジナルの要求が読み出された ならば、入力メツセージは、読み出し専用ボートに対する入カメ１セージと同一 の部分、レファレンスが読み出されたことを示すプラス１の付加ビットを持つ。

しかしながら、もし、要求がメモリ書き込みならば、入力メモリビットは、書き 込み完了のカウントのために単に十分な情報、つまり、３ビツトの文脈情報およ び有効ビットを与えるために、再定義される。書き込み完了のカウントのための 読み出し／書き込み入力ボート上のこの特別なタップを除けば、すべての３つの 入力回路はほぼ同一に見える。各々は、エラー訂正および発見ユニ、）３２０、 エラーアドレスラッチ３１４および、メモリデータを、目的コードで記されたプ ロセッサ資源に向けるための進路方向回路・３１２を持つ。

Ｃ１１５Ａは、ボー）Ａの出力回路３５０のブロック図を示し、図５Ｂはボート Ｂの出力回路３５２を示し、図５ＣはボートＣの出力回路３５４を示す。読み出 し専用メモリボートＡおよびＢ１出力回路３５０および３５２は、ｌクロック期 間に一つのメツセージをメモリへ転送することができる。各メツセージは、３４ ビ。

トのアドレス、２ビ、トのモード情報（共用されたレジスタに対する）、１６ビ ントの目的コードおよび有効ビットからなる。読み出し／書き込みメモリボート Ｃ１出力回路３５４は、１クロｌりの期間に一つのメツセージをメモリへ送る能 力を持つ。このメツセージは、読み出し要求または書き込み要求で構成してもよ い。

もしそれが書き込み要求ならば、メツセージは３４ビツトのアドレス、８８ビ／ トのデータ、２ビツトの共用されたレジスタモード情報、３ビツトの文脈情報（ 書き込み完了のカウントのための）、書き込みビットおよび有効ビットを持つ。

もし、メツセージが読み出し要求ならば、データ領域内のビットは、メツセージ が読み出し専用ボートからの出カメ、セージと同じ情報を伝えられるよう、再割 り当てされる。

入力回路を備えることで、メツセージのビット幅および、異なったボートに同け られるブロモ、す資源を有する、３つの出力回路の構成は、同様である。これに より、この明細書は、図５Ａを参照してボート出力回路の動作について記述する 。当業者にとっては、以下の記述が図５Ｂに示したボートＢの出力回路３５２お よび図５Ｃに示したボートＣの出力回路３５４にも同様に適用できることが理解 されよう。

図５Ａを斧照すると、プロセッサ資源からのデータはメモリポートのアドレス加 算器３６０ヘマージされる。この加算器３６０は、１クロツクの間に３つの数を 合計する。第１のクロック期間におけるベクトルまたはブロック転送、これらの 数は、ベースアドレス、方向アドレスおよびインクリメント値である。その後、 その数は、インクリメント値および再循環する絶対アドレスである。スカラーレ ファレンスアドレスの演算は、加算用ベースアドレス、指示流れからの定数およ び、絶対アドレスを形成するためにメモリアドレスを表すレジスタ値を含んでも よい。この絶対アドレスは、ベースアドレスよりも大きいか等しいか、リミット アドレスより小さいか等しいかかテストされる。そのベースおよびリレミツトア ドレスは、メモリ内の８個までの安全ブロックの一つを表す。選択されたブロッ クは、ユーザーの指示により安全にされる。アドレス操作と並行して、エラー訂 正および発見コードのビットが書き込みデータ上に発生される。

各ボートは、これに関連する二つのレファレンスバッファ、Ａ３６２およびＢ５ ６４を持つ。各レファレンスバッファは、もし必要ならば、６４エレメントのベ クトル流れ全体を吸収できる。そのレファレンスバッファは、メモリクロスバ− ネットワークが１クロツク期間でメツセージを受け取るこ七ができない場合に選 択的に使用される。

各レファレンスバッファＡ３６２およびＢ５６４への読み出しおよび書き込みポ インターがある。もし、これらのポインターが等しいならば、そのバッファは空 である。メモリクロスバ−ネットワークがメツセージの流れをボートアドレス加 算器３６０およびエラー訂正／発見回路からエマーンできない時は、メツセージ は、書き込みポインタにより指示されたバッファアドレスにてレファレンスバッ ファ内へ書き込まれ、そのポインタは各メツセージ毎にインクリメントする。第 １の“抵抗”が流れに遭遇する、クロック期間から開始するので、流れ内のすべ てのメツセージは、レファレンスバッファに書き込まれる。クロスバ−ネットワ ーク内へ注入されるべきメツセージは、ブロモ、すからのメツセージ流れから直 接の代わりに、読み出しポインタにより指示されたレファレンスバッファアドレ スから来る。読み出しポインタは、読み出しおよび書き込みポインタが等しくな り、かつ流れが完了するまで、メツセージがネットワークにより受け取られる毎 にインクリメントする。そのポインタは次のレファレンス流れに先立ちクリアー される。

一つのレファレンスバッファが空にされるプロセスにあるとき、メモリレファレ ンスの流れは、他のバックＴにロードできる。簗１のバッファが空のとき、第２ のバッファの頭からメツセージが遅延なく、メモリクロスバ−ネットワークへ送 られる。空の第１のバッファは、その後、プロセッサからの次のレファレンス流 れを受け取るために利用される。これにより、ふさがれたメモリボートは、プロ セッサの検知からの完了を進めるために、二つのフル長さのベクトルレファレン スを上記ボートに許可する。

本発明の好ましい実施例では、レファレンスバッファＡ３６２、Ｂ５６４または プロセッサからのメモリレファレンスメツセージは、アドレスを指すメノセー／ の下位２ビツトのデコードにより、４組みの象限バッファの一つに向けられる。

象Ｖａハ、ファの各組みは、３つのバッファからなり、各々が一つのメ・、セー ジを保持できる。メツセージはバッファＣ３７４がもし空ならバッファＣ３７４ に入り、もしバッファＣ３７４が占有され、バッファＢ５７２が空ならバッファ Ｂ５７２に入り、あるいは、Ｂ５７２およびＣ３７４が占有され、Ａ３７０が空 ならバッファＡ３７０に入る。データは又、バッファＡ３７０からＢ５７２へ、 ノ＼。

ファＢ５７２からＣ３７４へ移動することができる。命令するメツセージは、３ つの象限バッファの間で保たれる。３つすべてのバッファがデータを含み、バ。

ファＣ３７４が空ならば、Ｂ５７２はＣ３７４へ移動し、Ａ３７０が８３７２へ 移動し、そして、いずれかの新しいメツセージがバッファＡ３７０へ入る。

メモリメツセージは、それがメモリクロスバ−ネットワーク内の第１のレベルの ４Ｘ４クロスバ−スイッチに送信される時、象限バッファＣ３７４内の二つのバ ケットに分割される。象限バッファＣ３７４と、クロスバ−ネットワークの第】 のレベルの加入バッファとの間の通信は、以下に述べるように、いずれかの２つ の４Ｘ４クロスバースイ、チと同じである。この二つのバケット経路故に、象限 バッファ間のデータ移動がベストで各２クロック期間毎に起こる。しかし、象限 バッファは、１クロ、りの速度でプロセッサまたはレファレンスバッファから満 たされる。ボートを去るメモリメツセージの二つのバケットの機構は、４の倍数 であるベクトルまたはブロック転送の歩幅が、２クロツク毎にｌメ、セージの最 大速度で実行する。ｌクロｌりにつき１メツセージの速度で、奇数の歩幅、■ま たは２歩幅または二つすべての奇数の倍数が実行する。

ブロモ、すからメモリクロスバ−ネットワーク図６は、本発明の好ましい実施例 の４×４クロスバ−スイッチ５００のブロック図を示す。当業者であれば、本発 明のクロスバ−スイッチは、本発明の本旨から外れることなく、８×８．２×２ ．２×４．４×２、その他、実質的にいずれかのｍｘｎ数の人力部および出力部 で構成することも可能であることが理解されよう。本発明の好ましい実施例に使 用された各４×４クロスバースイツチ５００は、４つの入力経路５０２ａ−ｄの 各々から出力経路５１８ａ−ｄの一つにデータを向けることができる。同一のク ロスバ−スイッチ４００が内結合および外結合のクロスバ−ネットワークの双方 に使用される。以下の詳細な記述は単に外結合のクロスバ−ネットワークを通じ た外結合のブロモ、すからメモリへのレファレンス転送を述べているが、内結合 のクロスバー不、トワークも、以下に述べる外結合のクロスバー不、トワークを 通じて本質的に同じ方法により動作することが当業者であれば理解されよう。

本発明の好ましい実施例では、内結合および外結合のレファレンスは、二つの連 続的なバケット内のクロスバ−ネットワークにより受け取られる。読み出し／書 き込みボートのために、第１のバケットは、モードビット、目的フードバックま たは方向ビットおよびチップアドレスのごときすべての制御情報を含む。第２の バケットは、データを含む。読み出し専用ボートのために、第１のバケットは、 モードビット、目的コードおよびハングまたは方向ビットのごとき制御情報を含 む。当業者であれば、二つのバケット間のレファレンスビットを分配する方法は 、本発明のクロスハー不、トワークを実行するために要求される相互接続を最小 にするのに役立つことが理解されよう。

本発明の好ましい実施例では、第２のバケットは、クロック期間に追随した直ち に第１のバケットに追随し、第１のバケットと同じ経路でもって伝播する。この 理由のために、各データの移動か２クロック期間をとる。第２のバケットは、第 １のバケットよりも正確に１クロック期間後にクロスバ−スイッチ５００を切り 替える。

当業者であれば、メモリレファレンスのバケット化およびクロスバ−ネットワー ク４００を通じて連続的にそのバケット化を繰り返すことが、クロスバ−スイッ チを実行するのに要する相互接続の個数を２桁減じることが理解されよう。現代 の設計では、利用できる相互接続よりもより多いゲートをチップ内部に存在する 。

それ故、相互接続は、多数チップの設計では、乏しい資源である。例えば、内部 に４つの独立した経路および外部に４つの独立した経路および１２０ビ、ト幅の メモリレファレンスを持つ、４×４クロスバ−スイッチを仮定する。このような りロスバースイア千を構成するのに要する相互接続の数は、１２０の８倍である 。

当業者であれば、単一のチップに適応できる個数よりもかなり多い数であり、事 実、数個のチップに適応できる個数よりも多いことが理解されよう。メモリレフ ァレンスをバケット化することにより、１２０ビ、ト幅のメモリレファレンスは 、２桁減じられる。このことは、すべての／ステムの相互接続を同様に２桁減じ 、この減少はきわめて重要である。当業者であれば、本発明に使用されたこのバ ケット化方法は、システム設計を大幅にコンパクト化でき、クロスバ−スイッチ はより少ないチップで構成できる。

クロスバ−スイッチ５００の入力経路５０２ａ−ｄの各々は、少なくとも一つの 登録バッファで構成される。登録バッファの実際の個数は、クロスバー不、トワ ーク内でクロスバ−スイッチがいかに離れて位置しているかに依存して変化する 。クロ不バースイ、チ内の登録バッファ数は、クロスバ−スイッチ間の巡回時間 に依存して変化する。各クロック期間が交信時間に加算されるので、付随的な登 録バッファか必要となる。登録バッファの目的は、マルチのメツセージ毎ケ。

トを送出できるよう、クロスバ−スイッチ間の交信時間をカバーするためである 。

それ故、クロスバ−スイッチがＩクロ、夕期間で交信する、図６の本発明の好ま しい実施例では、二つの登録バッファＡ３０４およびＢ５０８がある。

これらの各バッファ５０４および５０６は、１メ、セージの双方のバケットを含 むことができる。人力経路５０２ａ−ｄの一つを通じてクロスバ−スイッチ５０ ０に入るメツセージは、バッファＢが既に他のメツセージを持っていないならば 、上記経路に対して、対応するバッファＢに最初にラッチされる。もしバッファ Ｂ５０６が占有されていたなろば、そのメツセージは代わりにバッファＡ３０４ にう、チされる。一旦、バッファＢ５０６が空になると、バッファＡ３０４に含 まれたメツセージは、バッファＢ５０８にラッチされる。もし、双方のバッファ ＢおよびＡが満杯ならば、別のメツセージがアクセスしようと試みた時、該メツ セージは、クロスバ−スイッチへ入る前に、バッファが空になるまで単に待つ。

第１のバケットのメツセージがバッファＢ５０４へ一旦うノチされると、バッフ ァＢ５０６は、４つの出力５１８ａ−ｄのいずれを発送するかを決定するために メツセージ方向ビットをデコードする。同様に、本発明の好ましい実施例では、 バッファＢ５０６は、双方のパケットのメツセージが存在する前に、メツセージ 全体を方向づけることかできる。

二つのメツビッジ方向ビットをデコードした後、バッファＢ５０６は、第１のバ ケット内の二つのメツセージ方向ビットを、４つの入力経路５０２ａ　−ｄから クロスバ−スイッチ５００に入るメツセージを表す二つのビットに置き換える。

同様に、始めるプロセッサヘパ、りさせるためのリターンアドレスは、メツセー ジがクロスバ−スイッチの連続する層を通じて、その経路上でコモンメモリへ移 動する時に、メツセビッ方向ビ、ト内で構築される。データがメモリから回復さ れた後、プロセッサリターンアドレスの情報は、回復したデータを元のブロモ。

サヘ戻すために、メツセージ方向ビット内で利用される。同様に、内結合のレフ ァレンスに対しては、リターンアドレスは、メツセージ方向ビット内で利用され る。

このように、もし、データにエラーがあると、プロセッサはどのメモリバンクか らエラーメツセージが来るかを知り、これにより、エラー発生ポイントを指示す るのに役立つ。

このビット置き換え計画は、／ステムの相互接続およびメツセージ長を減じ、こ れにより、プロセッサへメツセージと共にリターンアドレスを送る必要性を排除 する。代わりに、本発明の好ましい実施例のビット置き換え計画は、メツセージ を自動的にブロモ、すに発生させるか、メモリバンクにリターンアドレスを発生 するために、単に同じビットおよび相互接続を用いればよい。

バッファＢ５０６でデコードされたメツセージ方向ビットは、バッファＢ５０６ を去った後にメツセージが行くべき４つの象限バッファ５０８−５１４のいずれ かを選択する。入力バッファＡ３０４およびＢ５０６を備えているので、象限バ ッファ５０８−５１４の各々は、一つのメツセージの双方のバケットを持つこと ができる。もし目的の象限バッファ５０８−５１４が空ならば、レファレンスは バッファＢ５０６を去り、適切な象限バッファ５０８−５］４に入ることかでき る。

象限バッファ５０８〜５１４の目的は、メツセージの紛争およびタロスパーネッ トワーク内のブロックを低減することにある。例えば、もし、出力経路５１８ａ がブロックされたならば、出力バッファ５１６ａは、メツセージを含み、満杯と なり、経路をクリアするために待つ。出力経路５１８ａに向けられた別のメソセ ージが、入力経路５０２ａ上のクロスバ−スイッチ５００へ入った時、例えば、 該メ・／セージは、出力選択回路５１６ａをクリアするために待機している、象 限バッファ５．０８ａへ移動する。その後、もし、いずれかの他の経路に対して 予定されている付随的メツセージが経路５０２ａに入ったならば、そのメツセー ジは単に適切な象限バッファへ移動するので、該メツセージは、その目的の出力 へのアクセスがブロックされない。このようにして、より多くのメツセージがク ロスバ−ネットワーク内でブロックに“到達”することができる。単に、登録バ ッファへのすべての入力経路がブロックされたならば、その経路に入るメツセー ジは、すべての出力経路からブロックされる。もし、本発明のクワスバースイ、 チ５００内の象限バッファ５０８−５１４がそこに存在しないならば、４個すべ ての象限がブロックされる。象限バッファ５０８−５１４の使用を通じて、４つ の出力経路の一つのみが上記ポイントでブロックされる。当業者であれば、象限 バッファ５０Ｂ−５１４がクロスバ−ネットワーク内のメツセージの紛争およヒ フロックを大幅に減じることが容易に理解されよう。

メツセージの双方のバケットが象限バッファ５０８−５１４の一つに入った後、 そのメツセージは、適切な出力選択回路５１６ａ−ｄに向けられることが適確と なる。各出力選択回路５１６は、各入力経路５０２ａ−ｄから対応する象限バッ ファ５０８−５１４からメツセージを探す。例えば、出力選択回路５１６ａが象 限′０”バッファ５０８ａ、５０８ｂ、５０８ｄから適確なメツセージを探し、 そのメツセージは、それぞれ入力経路５０２ａ、５０２ｂ、５０２ｃ、５０２ｄ からクロスバ−スイッチ５００に入る。もし、適切な象限バッファ５０Ｂ−５１ ４内に一つの適確なメツセージがあったならば、出力選択回路５１６ａ−ｄは、 単にその７ノセージを対応する出力経路５１８へ送信する。本発明の好ましい実 施例では、もし、適切な象限バッファ５０８−５１４内に一つ以上の適確なメツ セージがあれば、出力選択回路５１６ａ−ｄは、円の順序の次のメツセージを、 選択された最後の象限バッファから送信する。例えば、もし出力選択回路５１６ ０が送信のために象限バッファ５１２ｂを選択するならば、象限バッファ５１２ Ｃが適確な、メツセージを持ち、一つ以上の適確なメツセージが存在するならば 、送信のために次に象限バッファ５１２Ｃを選択する。

クロスバ−スイッチ５００の出力部Ｂ５１８ａ−ｄを通じて一旦メノセージが伝 播すると、そのメツセージは、クロスバ−スイッチ（または、送信するクロスバ −スイッチが外結合のクロスバ−ネットワークの最終の層ならばコモンメモリ、 または、送信するクロスバ−スイッチが内結合のクロスバ−ネットワークの最終 の層ならばプロセッサ）の次の層に進む。

次のテーブルは、図６のクロスバ−スイッチ５００を通じて、入力経路０５０２ ａから他に紛争データを持たない象限３出力経路５１８ｄヘメノセージ（メ。

セージの二つのバケットは“バケット０″および“パケット１″）をトレースす る。

クロックＯメツセージバケットＯが経路５０２ａバツフアＢ５０６ａに入る。

クロックｌ　メツセージバケット１が経路５０２ａバツフア８５０６ａに入る。

メ、セージバケｙ）Ｏが経路５０２ａ象限３バツフア５１４ａに入る。

クロ、り２　メ、セージバケｙ）１が経路５０２ａ象限３バツフア５１４ａｌ、 −入る。

クロ、り３　メツセージバケットＯが象限３象限５１８ｄに向く。

クロ、り４：メツセージバケットｌが象限３ｉ限５１８ｄに向く。

本発明のクロスバ−ネットワークの連続する層間のスムーズな交信は、応答ビ。

トの使用により達成される。メツセージがバッファＢ５０６から目的のクロスバ −スイッチ内の象限バッファに移動した後、目的とするクロスバースイ・７チは 、一つの応答ビットを先のクロスバースイｌチの出力部に戻す。この方法では、 送信するクロスバ−スイッチは、応答ビットのために待つためにポーズしなけれ ばならない前に、目的のクロスバ−スイッチに二つ（一つはバッファＢ５０６に 入り、二つ目はバッファＡ３０４に入る）のメツセージを送ることができること を′知る”。付随メツセージが送信する前に受信された単一の応答ビットは、目 的のクロスバ−スイッチの登録バッファＡ３０４およびＢ５０６内の一つまたは より多くのメツセージのためのルームがあることを意味する。二つの応答ビット は、目的のクロスバ−スイッチ内に二つのメソセージのためのルームがあること を意味する。

クロスバ−スイッチ間の円の移動交信は、送信するクロスバ−スイッチから出て 行くレファレンスのための時間と、応答ビットが受信するクロスバースイｌチか ら受け取った時間との合計で決定される。１クロスバ−スイッチに要求される登 録パンファ数は、この円移動の交信時間の１／２である。本発明の好ましい実施 例では、スイッチ間の交信が、送信するスイッチが次のメツセージ（もし一つな らば）を送る間に応答ビット送信するクロスバ−スイッチにより受信されるよう 、計時される。もし、計時がこのようでないならば、当業者であれば、送信する クロスバースイｌチでのメツセージは待たなくてはならないことが理解されよう 。しかしながら、本発明の計時法を使用することにより、応答ビットは受信し、 これにより、利用できる出力メツセージが直ちに出て行く。

当業者であれば、本発明のクロスバ−ネットワークの設計は、様式のスカラー能 力を増すことが容易に理解され認識されるであろう。各クロスバ−スイッチが隣 接部との交信のみを必要とするのでこの様式は、極めてスカラー能力が高い。

個々のクロスバ−スイッチは、層全体についての情報を持っこと又は二三の層で 何が起こっているかを知る必要がない。各クロスバ−スイッチは、データを調停 し送出するためにローカルな情報のみを必要とする。同様に、ブロモ、すは、メ モリレファレンスを送る前に全体の知識を持つ必要がない。このように、プロセ ッサは、メツ、セージを送る前に、プロセッサからメモリバンクへの全体のデー タ経路が明瞭であることを確かめる必要がない。本発明のクロスバ一方法を用い ると、ブロモ／すは単に、“始動し、忘れる”。当業者であれば、本発明の様式 は、全体の調停を必要としないので、又、プロセッサ、クロスバ−スイッチまた はオペレート／ステムのいずれかの再設計が不必要なので、本発明のシステムは 、単純な復製により極めて容易となる。単に、異なった形態で再ホックするのみ である。

本発明のクロスバ−ネットワークの他の利点は、各クロスバ−スイッチが同様に 作用する限り、どのタイプのプロセッサを使用するか、またはいかに高速なメモ リであるかは重要ではない。あらゆる複数スレッドのタイプのプロセッサは、本 発明のシステムに適応可能である。たとえ各バンクのメモリが異なった速度であ っても、複雑な再設計の要なく本発明の様式は動作する。当業者であれば、本発 明の様式は、それ故、この観点で極めてフレキンプルであることが理解されよう 。

本発明の好ましい実施例では、クロスバ−回路は、各クロ、り期間に最大４つの ロジックレベルを実行できるよう設計される。この設計は、本発明の好ましい実 施例にり１して、ベストケースでクロスバ−スイッチ５００を通じ、４クロック 期間の送信時間となる。当業者であれば、１クロック期間に４つのロジックレベ ルとした設計がより遅い回路技術の使用を許可することを拘束するが、高速のク ロック速度を保持しているので、その結果、より低いシステムの電源および冷却 要求となり、大サイズの積分レベルの利用を許可することが理解されよう。本発 明のコノピユータマシーンの大きい分数のハードウェアは、クロスバースイチノ ング不ノトワークからなるので、当業者であれば、本発明の好ましい実施例にお ける大きいスケールの積分レベルの使用は、膨大な付随のハードウェアの節約、 大電源の節約、および低速、安価のハードウェア技術を可能にすることが理解さ れよう。

本発明のクロスバ−ネットワークの別の利点は、プロセッサの態様、文脈を切り 替えることである。当業者であれば、文脈切り替えプロセッサは、プロセッサの 怠は時間を大幅に減じ、実質的にブロモ、すの効率を増す。プロセッサは、はと んどゼロのデッド時間となるので、プロセッサは常にメモリ要求を出すため、信 じられない要求がメモリやクロスバーメそり調停ネットワーク上に位置する。

本発明に使用されたブロモ、すの態様の切り替えのために、プロセンサは最初の スレッドが待っている間に次のスレッドに切り替えることができるので、ブロモ 。

すは、そのスレッドの一つがそのメモリレファレンスが満たされるために待たな くてはならないことに対して注意を払わなくてよい。これにより、本発明の文脈 切り替えプロセッサは、時間に感知せず、又、それ故、より大きい呼び出し時間 であっも効率良く動作する。本質的に、本発明の設計は、増大されたバンド幅に 対してメモリ呼び出し時間の要求に取り替えられると、大容量のデータを移動す ることができる。当業者であれば、このような設計機構は、きわめて高いバンド 幅できわめて高いスルーブツトマシンとなり、その設計は特に高度な並列ベクト ル処理の仕事に適していることが容易に理解され認識されるであろう。

コモンメモリの設計 図７Ａおよび７Ｂは、本発明の好ましい実施例に使用されたタイプのメモリホー ド８００のブロック図である。メモリボード８００は、クロスバ−ネットワーク 、１６バンクのメモリおよび、メモリレファレンスメノセーンを、内結合のクロ スバーネｙトワークを通じて元のプロセッサに戻す出力方向回路からプロセッサ メツセージレファレンスを取り出す、入力回路を含む。

本発明の好ましい実施例では、各メモリバンク８４０は、２３のメモリチップお よび５つのバイト制御ロジ、クチノブからなる。２２個のメモリチップは、サイ クル時間が１３クロック期間以下の４ビツトのスタテイ、りによるＲＡ〜１２５ ６にである。これらの２２個のメモリチップは、エラー検出および修正のための １６チエノクビノトを有する６４ビツトデータを形成する。その１６チエノクビ ノトは、スタテイ、りＲＡｒシ１メモリデバイス内のすべての４ビ、トの失敗の 出来事の訂正を許可する。本発明の好ましい実施例に使用されたエラー検出機構 は、“チップ孤立”として霊位され、その記述は、Ｓｃｈｗｏｅｒｅｒよる、１ ９８９年８月３０日発効の米国の特許出願登録第４００．０７１の“ＢＩＴ　Ｄ ＥＴＥＣＴＩＯＮ　ＭＥＴｉｌＯＤ　ＦＯＲＥＮＨ入ＮＣＥＤ　５ＥＣ−ＤＥＤ 　ＥＲＲＯＲＤＥＴＥＣＴＩＯＮ　ＡＩＤ　Ｃ０ＲＩ！ＥＣＴｌ０Ｎ　Ｉ！ｌ　 ＭＵＬＴＩ−ＢＩＴ　戟IＥＭＯＲＹ　ＤＥ ＶＩＣＥＳ”にあり、これは本発明と同じ譲受人に譲渡されており、これを謬考 として述へる。２３個のメモリチップは、メモリバンクビノトを格納するＩビッ トチップによる２５６にである。

当業者であれば、メモリバンク８４０は、ここで述べた特定の実施例と同じロン ツク設計で構成される必要はなく、又、同じ目的を達成するために計算されたい ずれかの構成は、既述した特定の実施例に対して置き換えにれることか容易に理 解されよう。例えば、本発明の様式は、直接アドレス可能メモリである極めて多 数のＳ　ＲＡ〜１およびＤ　ＲＡ　Ｍを用いたメモリ設計をもサポートする。本 発明の本旨から逸脱することなく、他のメモリ設計も使用することかできる。

本発明の好ましい実施例におけるマルチブロモｌすからコモンメモリレファレン スを同期させる二つの方法がある。これらには、２３番目のメモリチップに位置 するメモリ口、クバイト、および５バンクの制御ロジ、クチ／プ内に位置する共 用レジスタがある。そのメモリロックバイトは、個々のメモリ位置を口、りし＄ 備する。本発明の好ましい実施例では、二つのタイプの指示があり、一つは口。

クバイトを用い、他の一つはそれを用いない。ロックされたメモリ書き込みレフ ァレンスは、データを口、りされていないメモリ位置へ書き込み、そしてその位 置がロックされるようになる。もし、メモリ位置がロックされたならば、そのメ モリ位置には、それをロック解除するために適切な読み出しレファレンスが添付 されなくてはならない。当業者であれば、これらのロックビットは、プロセッサ 間でデータ資同期させるために使用され得ることが理解されよう。口、りされた 位置の状態に起因するメモリにより拒絶されたレファレンスは、拒絶コードを伴 ってプロセッサへ戻される。そのブロモＩすは、その位置へのアクセスを得るま で、レファレンスを再出力する必要がある。

プロセッサの同期が達成される第２の方法は、共用レジスタの使用による。各メ モリバンク内の５バンクの制御ロジックチップは、メモリ系列化回路、メモリロ ック読み制御および、ブロモ、すの同期のために使用される特殊共用レジスタを 含む。この共用レジスタは、３つのモード、つまりフェッチおよびインクリメン ト（デクリメント）レジスタとして、アンロックデータレジスタとして、および 合図レジスタとして、いずれかで動作する。合図としてのレジスタの使用例は、 Ｐｒｉｂｎｏｗにより１９８８年６月２８日発効の米国特許４．７５４．３９８ の５ＹＳＴＥＷ　ＦＯＲＭｌ：ＬＴＩＰＲＯＣＥＳＳＯＲＣＯＭＭＵＷＩＣＡＴ ＩＯＮ　ｔｉｓＩＮＧ　ＬＯＣＡＬ　ＡＩＤ　ＣＯ’ｆｆ０Ｎ　ＳＥ蓋ＡoＨＯ ＲＥ　ＡＮＤ ＩＮＦＯＲ１４ＴＩｏ！ｉ　ＲＥＧＩＳＴＥＲ３“に見い出すことができ、この 特許は本発明と同じ譲受人に譲渡されており、ここで７考として述べる。

当業者であれば、共用レジスタをメモリバンク上に直接入力持つことはいくつか の際立った利点があることを容易に理解されよう。このように、プロセッサ間の 共用レジスタに対する調停の主旨は、プロセッサ自身を離陸させ、代わりにクロ スバ−ネットワークにより敢行させることである。共用レジスタがメモリバンク 上に位置し、各メモリバンク制御の一部であるため、プロセッサ間の調停にアク セスする共用のレジスタは、メモリレファレンス間を調停するのと同じクロスバ −ネットワークにより完成される。それ故、共用レジスタのアクセスが、単に別 のメモリレファレンスのごとく見えるので、共用されたメモリに対するプロセッ サ間の調停を達成するために必要となる付随的なハードウェアは不必要である。

当業者であれば、この構成は、慢数ブロセノサンステムを調整し、同期させるた めに、個別の経路および個別の調停ネットワークを用いる設計に対して格別な利 点を提供する。

ブロモ、す側よりもむしろ様式のメモリ側に共用レジスタすべてを持つ他の利点 は、設計か極めて容易になることである。それ故、本発明のシステムの設計が変 化した時、個々のブロセ、ｑ内に、または全体の様式に対して再設計を必要とシ ナイ。（本発明の様式は、全体の調停を必要としないためである）。むしろ、本 発明の共用レジスタの調停は、すべてのプロセッサが、所望される多数のプロセ ッサと会話でき、合図およびレジスタのいずれをもブロモ、す側に必要としない 。

共用レジスタのフェッチおよびインクリメントのモードでは、ループが種々のプ ロセッサ間で極めて容易にカウントする。実行することを必要とするすべてのプ ロセッサは、共用レジスタに読み出され、そしてレジスタを自動的にインクリメ ントし、プロセッサに更新されたループカウントを与える。次のプロセッサは、 共用レジスタを読み出し、次のループカウントを得て、そしてレジスタを自動的 にインクリメントする。当業者であれば、“自動インクリメント”のフェッチ特 性および共用レジスタのインクリメントモードは、共用レジスタの極めてパワフ ルな機能であり、過去使用されたループカウントの分配に対するフェッチおよび インクリメントを実施する別の方法に際立った利点を与える。例えば、一つの古 い手法により、共用レジスタかメモリに位置していないループカウントの分配に 対するフェッチおよびインクリメントを実行する時、ループカウンタである個別 のメモリ位置がなくてはならず、又、合図またはプロセッサがメモリ位置をロッ クし、メモリ位置をブロモ、す内へ読み出し、インクリメントし、書き込みが停 止され、メモリ位置を解除する。カウンタがロックされる全体のロック時間は、 数十または数百のクロ、り期間である。多数のブロモ、すを有するきわめて高度 な並列システムでは、ループカウントを数百のプロセッサに分配するために、可 変の時間をロックする時間の数百倍かかる。ロックの可変時間を低減するために 、本発明は、ループカウントの自動インクリメントおよび分配のために、メモリ での共用し？スタを用いる。プロセッサは、又、読み出しを行うことができ、本 発明の好ましい実施例では、各２クロック期間の速度で実行する。それ故、もし 、１００個のプロセッサがある場合、それらすべてが２００クロック期間内で新 しいループカウントを持つ。この時間は、システムの“粒状化”を決定する。（ この“粒状化“という語は、すべてのシステムのプロセッサが一度に動作できる 最小サイズのループを意味する。）過去の設計スタイルでは、例えば、百のプロ セッサのクロック期間の数倍の数百クロックとなるので、粒状化は、クロｌり期 間の十倍の千となる。本発明のシステムでは、しかしながら、粒状化は、はんの 百または２クロック期間である。当業者であれば、本発明の様式がシステムの粒 状化を大きく低減し、並列可能でより幅広い変化のあるアプリケーションプログ ラムを可能にすることが理解されよう。

本発明の共用レジスタの調停様式が効果的に機能する理由は、本発明に使用され たプロセッサの態様を文脈切り替えすることに結びついている。一つのスレ。

ドが共用レジスタをアクセスするために待っている時、プロセッサは、第１のス レッドが同期が起きるために待っている間に、単に別のスレッドに文脈切り替え すればよい。共用レジスタが戻るべくアクセスするために待っている間、スレッ ドは０眠る”ことかできるので、そのスレッドは、共用レジスタがメモリ上に出 て行くことや、レファレンスが戻るために少しの時間を取るといったことに注意 を払わなくてよい。別の例では、本発明の様式かメモリ呼び出し時間に関せず、 極めて効率的に機能することかできる。

本発明の共用レジスタの共用レジスタの同期設計の別の利点は、本発明に使用さ れたプロセッサ数に比例して極めて多数の共用レジスタを持つことである。本発 明の好ましい実施例ではロック時間が単に２クロック期間に低減されるが、もし 、ループカウントが例えば１０００個のプロセッサに分配されるならば、本シス テムの粒状化が極めて大きいクロック期間となるので、極めて大きい数の共有レ ジスタは重要である。ソフトウェア技術は、プロセッサをチームに押し込み、プ ロセッサがそられのループカウンタを異なるレジスタから得ることにより、大き い数の共用レジスタの利点を得ることかできる。当業者であれば、共用レジスタ の好ましい大きい数を認識できよう。分離した不、トワーク内で本発明の設計の 共用レジスタで達成されるタイプの機能を持つことで、増減しなくてはならない 極めて大きい個別のハードウェアを必要とする。それ故、本発明の好ましい実施 例は、メモリバンク上に共用レジスタを直接に設けることにより、途方もなくハ ードウェアを節約する結果となる。

メツセージは、３つのメモリポート入力経路８０１ａ−ｃの一つを通じてメモリ ボード８００へ入る。これらの経路は、プロセッサポートＡ、ＢおよびＣに対応 する。ボー）ＡおよびＢは、読み出し専用ポートなので、メモリポート入力経路 ８０１ａおよび８０１ｂに沿って入る各メツセージは、目的のタグに沿ったメモ リアドレスからなる。ポートＣは読み出し／書き込みポートなので、メモリポー ト入力経路８０１Ｃに沿って入るメツセージは、メモリに格納されるデータワー ドを伴ってもよい。本発明の好ましい実施例では、各プロセッサの３つのレファ レンスポートは、先に述べたように、各３つのポートへの内結合および外結合の クロスバ−ネットワークを委ねることにより、すべてがメモリバンク８４０への 経路である、それ自身の個別の交信経路を持つ。当業者であれば、この設計構成 は、メツセージの紛争およびブロックを最小に低減することが理解されよう。

本発明の好ましい実施例では、メモリボード８００へ入るメツセージは、先に述 べた本発明の４Ｘ４クロスバ−スイッチのかじとり法と同じ方法を用いて適した メモリバンク８４０へ導かれる。３つのメモリ入力経路８０１ａ−ｃの一つの中 にあるメモリボード８００へ入るメツセージは、前記経路のためのバッファＢ８ ０４が空ならばそこに入る。もしバッファＢ８０４が占有されておれば、そのメ ノセー／はＭａｔ２経路に対するバッファＡ３０２ヘラノチされる。バッファＢ ８０４が一旦空になると、バッファＡ３０２の内容がバッファＢ８０４へ移動す る。

第１のバケットのメツセージがバッファＢ８０４に一旦入ると、バッファＢ８０ ４は、方向ビットのメツセージをデコードし、そして、４つのメモリバンクのグ ループと関係している上記経路のために、そのメツセージを４グループのバッフ ァ８０８．８０８，８１０，８１２の一つに導く。例えば、入力ポート８０４ｂ を通してメモリボード８００に入り、そしてメモリバンクグループ２へ発送され るメツセージは、グループ２のバッファ８１０ｂへ向けられる。

別のレベルのかじとりは、先に述べたように、メツセージを空のバッファから本 発明の４×４クロスバ−スイッチ内の象限バッファへ移動させたのと同じ方法を 再度用いて、次に実行される。メツセージは、４つのメモリバンクのグループと 関係するグループバッファ８０６−８１２から、単一のメモリバンク８４０と関 係する入力バッファ８２０へ移動する。このレベルで、メツセージは、メモリバ ンクまたは共用レジスタのいずれかにアクセスするためにバンク制御ロジックチ ップにより選択されることで適確なものとなる。

メモリボード８００から要求しているプロセッサへ戻すために、レファレンスは 単にメモリバンクから出て、そして、先に述べたように、外結合のクロスバ−ネ ットワークを通じて外結合のプロセッサからメモリレファレンスへ移動するのと 本質的に同じ方法により、適した内結合のクロスバー不、トワークを通じて元の プロセッサに戻る。

ここでは特定の実施例について図示し開示したが、当業者であれば、同一の目的 を達成するために計算するいずれの構成であっても、図示した特定の実施例と置 き換えられることが理解されよう。例えば、本発明の様式は、異なった個数のプ ロセッサ、異なった量のメモリまたは１プロセツサにつき異なった個数のプログ ラムスレッドでもって達成してもよい。更に、当業者であれば、本発明の様式は 、詳細な説明で述べた、使用した特定のプロセッサのタイプ、メモリの速度また は特定のロジック設計に依存しないことが理解されよう。例えば、好ましい実施 例は、ここではクレイ２型プロセツサを用いて述べたが、本発明の本旨からそれ ることなく、異なるタイプのプロセッサを用いることができる。例えば、本発明 の別の実施例として、本発明の譲受人であるクレイリサーチ社製造のツレ４フり に用いることができる。クレイＹ−ＭＰのブクブク回路は、Ｌｅｅその他による 、１９８９年１１月１７日発効の米国特許第０　７／４　３　８，　６　７　９ ノ”ＶＥＣＴＯＲＢＩＴ　ＭＡＴＲＩＸ　ＭＩＴＹＰＬＹ　ＦＵＮＶＴＩＯＮＡ Ｌ　ＩＩＮＩＴ″に見ることができる。クレイ１型プロセツサも図示した特定の プロセッサで置き換えることができる。クレイ１のブロモ，すのプロ、り図は、 クレイ、Ｊｒによる上述した米国特許第４、１２８．　８８０に見ることができ る。

本出願は、本発明のあらゆる応用および変形をカバーするよう意図されている。

それ故、本発明はクレームおよびそれと等価なもののみによって限定されること を意図したことが明白である。

ＦＩＧ．　１ ＦＩＧ．　２ 平成　５年　４月　１９日

Claims (19)

【特許請求の範囲】
1. （１）デジタル情報を格納するためのコモンメモリ手段と；スカラーおよびベク トル指示を実行するため、及び多数の指示スレッド間で文脈を切り替えるための ベクトル処理手段と、伝送された情報が可変の呼び出し時間に対処できるように 、コモンメモリ手段とベクトル処理手段との間で情報を伝送するための交信手段 と；を備えたスカラブルパラレルベクトルコンピュータシステム。
2. （２）各ベクトル処理手段が、 交信手段から又は交信手段へ情報を受け取る又は送出するための多数のレファレ ンスポートと、 多数の指示スレッドと、 プログラムされた指示を格納するための指示バッファ手段と；通信手段に関連す る可変の呼び出し時間が、実質的に隠され、プロセッサの怠け時間が大幅に減じ られるよう、指示スレッド間で文脈を切り替えるための文脈切り替え手段と、 を備える請求の範囲第１項記載のスカラブルパラレルベクトルコンピュータシス テム。
3. （３）各指示スレッドが委ねられた指示バッファの組みを持つよう、指示バッフ ァ手段が多数の指示バッファの組みを含む請求の範囲第２項記載のスカラブルパ ラレルベクトルコンピュータシステム。
4. （４）各指示スレッドがアドレスレジスタ、スカラーレジスタおよびベクトルレ ジスタの対応する組みを持つ請求の範囲第３項記載のスカラブルパラレルベクト ルコンピュータシステム。
5. （５）多数の指示スレッドがスカラー、ベクトルおよびアドレス関数ユニットの グループを共用する請求の範囲第３項記載のスカラブルパラレルベクトルコンピ ュータシステム。
6. （６）出力のブロックが発生するまで、ベクトル処理手段が指示バッファ手段内 の指示を実行する請求の範囲第２項記載のスカラブルパラレルベクトルコンピュ ータシステム。
7. （７）文脈切り替えを生じさせる一つの出力ブロックが分岐指示、プロセッサ同 期の遅延およびメモリ読み出し依存データである、請求の範囲第６項記載のスカ ラブルパラレルベクトルコンピユータシステム。
8. （８）交信手段が、接続数が増える結果、呼び出し時間が増大する、多数のクロ スバーネットワークを含み、個々のプロセッサの性能に実質的に影響を及ぼすこ となく、より多いかより少ない数のプロセッサおよび、多少のメモリを持つこと ように設計することができる、請求の範囲第２項記載のスカラブルパラレルベク トルコンピュータシステム。
9. （９）交信手段が、文脈切り替えプロセッサからコモンメモリヘの交信のために 、１組みの外結合のｎ個のクロスバーネットワークと、コモンメモリから文脈切 り替えベクトルプロセッサへの交信のため、１組みの内部結合のｎ個のクロスバ ーネットワークとを備え、ｎはプロセッサに対するレファレンスポート数に等し い、請求の範囲第８項記載のスカラブルパラレルベクトルコンピュータシステム 。
10. （１０）クロスバーネットワークが更に少なくとも１段のクロスバースイッチを 含む請求の範囲第９項記載のスカラブルパラレルベクトルコンピュータシステム 。
11. （１１）各クロスバースイッチが更に、クロスバーネットワーク内での紛争およ びブロックを減じるための象限バッファ手段を含む請求の範囲第１０項記載のス カラブルパラレルベクトルコンピユータシステム。
12. （１２）コモンメモリ手段が更に、デジタル情報を格納するために、多数のメモ リバンクを含む、請求の範囲第１項記載のスカラブルパラレルベクトルコンピュ ータシステム。
13. （１３）コモンメモリ手段が更に、 プロセッサの同期のために共用された多数のレジスタを備え、該レジスタは個々 のメモリバンクに対応しており、 又、文脈切り替えベクトルプロセッサがメモリバンクを準備できるよう、多数の ロックビットを含む請求の範囲第１２項記載のスカラブルパラレルベクトルコン ピュータシステム。
14. （１４）各々が多数のスカラーおよびベクトル指示を含む、多数の指示スレッド を有する文脈切り替えベクトルプロセッサを扱うための方法であって、（ａ）指 示スレッドを選択し、 （ｂ）指示スレッド内のスカラーおよびベクトルを実行し、（ｃ）出力ブロック を発生させ、 （ｄ）次のスレッドに文脈を切り替え、（ｅ）すべての指示が敢行されるまで（ ｂ）、（ｃ）および（ｄ）のステップを繰り返す、 ステップを含む方法。
15. （１５）文脈切り替えステップ（ｄ）が、次のスレッドが解決された出力ブロッ クのすべてを持つか否かをチェックするステップを更に含む請求の範囲第１４項 記載の方法。
16. （１６）文脈切り替えステップ（ｄ）が、次の出力ブロックが解決されないなら ば、スレッドをバイパスさせるステップを更に含む請求の範囲第１５項記載の方 法。
17. （１７）次のスレッドが円の順序で選択される請求の範囲第１４項記載の方法。
18. （１８）出力ブロックがプロセッサの同期遅延、分岐指示、またはメモリ読み出 し依存データに起因する時のみ、発生ステップ（ｃ）が起こる、請求の範囲第１ ４項記載のスカラブルパラレルベクトルコンピュータシステム。
19. （１９）次のスレッドがランダムで選択される請求の範囲第１４項記載の方法。