(57)【要約】【課題】パイプライン形態で処理しうるメモリ要求を無限個発行しうるプロセッサを構築する。【解決手段】コンピュータ・システムにおいて、（１）高度にパイプライン化したメモリに発行する要求の個数を最大化し、唯一の限界がプログラムにおけるデータ依存性のみであるようにするとともに、（２）メモリ（１０）への対応するライトより前のメモリからのリードを避けうるようにメモリ命令を発行し実行する方法と装置を提供する。メモリ命令は明示的に移動（ｍｏｖｅ）命令（２１）を使用してメモリに対するリードとライトを構成する。これにより、プロセッサ（９）におけるデータ記憶の限界を避けることができる。メモリ要求は完全な情報を運ぶように構成する。これにより、メモリが要求されたデータを返したらすぐにメモリ要求を処理することが可能になる。メモリは多数の領域に分割する。各領域はフェンス・カウンタ（１８）に関連付けられている。あるメモリ領域用のフェンス・カウンタは当該メモリ領域を目標とするメモリ命令を発行するごとにインクリメントし、当該メモリ領域へのライトが存在するごとにデクリメントする。フェンス命令を発行したら、フェンス命令が特定しているメモリ領域用のカウンタがしきい値を超えている場合にはさらなるメモリ命令（２３）を発行しない。未決の発行済み命令を十分な個数実行すると、カウンタはしきい値未満にデクリメントされているから、さらなる命令を発行することができる。【選択図】図１
2004527054.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ・システムにおいて命令を処理する方法であって、
前記プロセッサが発行し指定したメモリ領域を目標とする未決のライト命令の個数がしきい値を超えているか否かを判断するステップと、
前記メモリ領域を指定したフェンス命令を発行するステップと
を備え、
前記指定した領域を目標とする未決のライトの前記個数が前記しきい値未満になるまで前記プロセッサがさらなる命令を発行しない、
方法。
【請求項２】
コンピュータ・システムにおいて命令を処理する装置であって、
前記プロセッサが発行し指定したメモリ領域を目標とする未決のライト命令の個数がしきい値を超えているか否かを判断するとともに、前記メモリ領域を指定したフェンス命令を発行する発行ユニット
を備え、
前記指定した領域を目標とする未決のライトの前記個数が前記しきい値未満になるまで前記プロセッサがさらなる命令を発行しない
装置。
【請求項３】
命令を処理するシステムであって、
データを格納するメモリと、
発行ユニットであって、多数の命令の各々に応答して前記メモリからオペランド・データを取得し、前記メモリまたは前記発行ユニットに格納することなく、前記各命令の演算コードおよび前記各命令の目標の場所を転送する発行ユニットと、
前記演算コードに従い前記データをオペレーションし、前記データについての前記オペレーションの結果を前記目標の場所が特定している前記メモリ中の場所に格納する実行ユニットと
を備え、
前記目標の場所、前記演算コード、および前記オペランド・データを前記実行ユニットが取得する
システム。
【請求項４】
コンピュータ・システムにおいて命令を処理する方法であって、
多数の命令の各々に応答して、
メモリからオペランド・データを取得し、該オペランド・データ、演算コード、および目標の場所を前記システムに関連付けられた実行ユニットに転送するステップと、
前記演算コードに従い前記オペランド・データについてオペレーションすることにより各命令を実行し、前記オペランド・データについてのオペレーション結果を前記目標の場所が特定している前記メモリ中の場所に格納するステップと
を備えた
方法。
【請求項５】
コンピュータ・システムにおいてメモリ命令を処理する方法であって、
多数のメモリ命令の各々に応答して、
メモリからオペランド・データを取得し、該オペランド・データ、演算コード、および目標の場所を前記システムに関連付けられた実行ユニットに転送し、前記演算コードに従い前記オペランド・データについてオペレーションすることにより各命令を実行し、前記オペランド・データについてのオペレーション結果を前記目標の場所が特定している前記メモリ中の場所に格納するステップと、
メモリ領域を指定したフェンス命令を発行するステップと
を備え、
前記指定した領域へのライトの個数が前記しきい値未満になるまでプロセッサがさらなる命令を発行しない
方法。
【請求項６】
命令を処理するシステムであって、
データを格納するメモリと、
多数のメモリ命令の各々に応答して、前記メモリからオペランド・データ、前記各メモリ命令の演算コード、および前記各メモリ命令の目標の場所を取得する発行ユニットと、
前記演算コードに従い前記データについてオペレーションすることにより前記多数のメモリ命令の各々を実行し、前記目標の場所が特定している前記メモリ中の場所に前記データについてのオペレーション結果を格納する実行ユニットと
を備え、
前記目標の場所、前記演算コード、および前記オペランド・データは前記実行ユニットが前記メモリを通じて前記発行ユニットから取得し、
前記発行ユニットはメモリ領域を指定するフェンス命令をも発行し、前記指定した領域の各々について、前記各領域への未決のライトの個数が対応するしきい値未満になるまでさらなるメモリ命令を発行しない
システム。
【請求項７】
コンピュータ・システムにおいて命令を処理する方法であって、
前記システムのプロセッサが、メモリに対してリードまたはライトするメモリ命令を発行したら、前記発行した命令の目標アドレスが特定しているメモリ上の場所を含むメモリ領域に関連付けられたカウンタをインクリメントするステップと、
前記システムのプロセッサがメモリ命令を実行したら、前記実行した命令の目標アドレスが特定しているメモリ上の場所を含むメモリ領域に関連付けられたカウンタをデクリメントするステップと、
メモリ領域を指定したフェンス命令を発行するステップと
を備え、
前記指定した領域に関連付けられた前記カウンタがしきい値未満になるまで、さらなる命令を発行しない
方法。
【請求項８】
コンピュータ・システムにおいて命令を処理する装置であって、
前記システムのプロセッサが、メモリに対してリードまたはライトするメモリ命令を発行したら、前記発行した命令の目標アドレスが特定しているメモリ上の場所を含むメモリ領域に関連付けられたカウンタをインクリメントする手段と、
前記システムのプロセッサがメモリ命令を実行したら、前記実行した命令の目標アドレスが特定しているメモリ上の場所を含むメモリ領域に関連付けられたカウンタをデクリメントする手段と、
フェンス命令を発行する手段と
を備え、
前記指定した領域に関連付けられた前記カウンタがしきい値未満になるまで、さらなる命令を発行しない
装置。
【請求項９】
コンピュータ・システムにおいて命令を処理する方法であって、
前記システムのプロセッサが、メモリに対してリードまたはライトする命令を発行したら、前記発行した命令の目標アドレスが特定しているメモリ上の場所を含むメモリ領域に関連付けられたカウンタをインクリメントするステップと、
前記システムのプロセッサがメモリ命令を実行したら、前記実行した命令の目標アドレスが特定しているメモリ上の場所を含むメモリ領域に関連付けられたカウンタをデクリメントするステップと、
メモリ領域を指定したフェンス命令を発行するステップと
を備え、
前記発行した各命令は前記メモリから取得したデータ、演算コード、および目標の場所を含み、
前記指定した領域に関連付けられた前記カウンタがしきい値未満になるまで、さらなる命令を発行しない
方法。
【請求項１０】
コンピュータ・システムにおいて命令を処理する装置であって、
前記システムのプロセッサが、メモリに対してリードまたはライトする命令を発行したら、前記発行した命令の目標アドレスが特定しているメモリ上の場所を含むメモリ領域に関連付けられたカウンタをインクリメントする手段と、
前記システムのプロセッサがメモリ命令を実行したら、前記実行した命令の目標アドレスが特定しているメモリ上の場所を含むメモリ領域に関連付けられたカウンタをデクリメントする手段と、
メモリ領域を指定したフェンス命令を発行する手段と
を備え、
前記発行した各命令は前記メモリから取得したデータ、演算コード、および目標の場所を含み、これにより前記発行した各命令は発行した各命令に含まれていない情報とは無関係に実行することができ、
前記指定した領域に関連付けられた前記カウンタがしきい値未満になるまで、さらなる命令を発行しない
装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータ・システムにおいて命令を発行し実行する方法と装置に関する。
【背景技術】
【０００２】
現在のプロセッサが複雑なのはメモリ・アクセスの待ち時間を覆い隠そうとしている点にその理由の大部分があるといえる。マルチスレッド、アウト・オブ・オーダー処理、メモリ・データのプリフェッチ、投機的実行はすべてこれの例である。技術動向が示すところによれば、メモリ速度はプロセッサ速度に追いつきそうもない。現在のメモリ設計はパイプライン機能と階層機能の極限を呈しているが、本発明者らは同時係属出願において一定の帯域幅で線形の待ち時間機能を実現するスケーラブル（拡張が容易な）パイプライン階層の設計を提示した。その同時係属出願（ＩＢＭドケット番号ＹＯＲ９２００１０４３９ＵＳ１）は本願と同時に出願したが、「スケーラブル・メモリ」なる名称である。しかし、現在のプロセッサは未処理のメモリ要求を記憶しておこうとするから、このような無限のパイプラインを利用することはできない。現在のプロセッサは限られたリソースしか保持していないから、メモリ・パイプラインをきわめて限定された程度にしか利用することができない。リソースはタグに付随する命令に関する情報を格納するバッファを有限個備えている。たとえば、ＩＢＭ  ＰｏｗｅｒＰＣ（Ｒ）が保持しうる未処理のメモリ・オペレーションは高々８〜１６個であるが、競合する他のプロセッサが保持しうる限界はこれより少ない。この限界が存在する理由は、プロセッサは、保留中のメモリ要求を記憶しておきそれが到着したらデータをさらに処理するよう指示する専用のリソースを備えているからである。たとえば、発行済みのメモリ命令に対する応答がコンピュータ・システムのメモリから返ってくるとき、その応答にはメモリから取得したデータとメモリ・タグしか含まれていない。上記発行済みの命令を実行するためには、タグを用いて命令コードとプロセッサのバッファに格納されている目標アドレスを取得する。限界の別の要因はプロセッサに設けられているレジスタが有限個であること、およびプロセッサはレジスタに存在しないデータを処理できないことである。現在のプロセッサでは命令はプロセッサのレジスタに存在するオペランドを用いないと実行できないから、レジスタの個数によって同時並行的に実行しうる命令の個数の限界が決まる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明の目的はパイプライン形態で処理しうるメモリ要求を無限個発行しうるプロセッサを構築することである。
【課題を解決するための手段】
【０００４】
本発明の一側面はパイプライン形態で処理しうるメモリ要求を無限個発行しうるプロセッサを構築することである。この側面はすべての命令をメモリからのデータを操作しうるように構成し、返りデータを独立に処理するのに十分な情報をメモリ要求に詰め込むことにより達成する。この側面によって、プロセッサの命令発行コンポーネントと命令実行コンポーネントとが分離される。これらの各々はきわめて少ない状態情報しか保持しておらず、ほとんど「無状態」の形態で動作する。このきわめて少ない状態情報にはプログラム・カウンタといくつかのフェンス・カウンタが含まれる。
【０００５】
本発明の別の側面はメモリへの対応するライトの前にメモリからデータをリードするのを避けること、すなわち、いわゆるリード・アフター・ライト・ハザードを避けることである。この側面は、プロセッサが多数の命令を発行するが、発行した命令のすべてが実行されるわけではない、すなわち、完了していないメモリへの未決のライトが多数個存在する場合に特に重要である。このような多数個の扱いは（本願の譲受人と同じ譲受人に承継された）上述した同時係属出願に記載されている線形メモリを使用することにより可能になる。本発明ではフェンス・カウンタすなわち多数のメモリ領域の各々用のカウンタを保持することにより、リード・アフター・ライト・ハザードを避けている。この場合、カウンタ値を用いてプロセッサが命令をさらに発行するのを制御している。本発明によると、特定のメモリ領域を指定したフェンス命令を発行すると、その特定のメモリ領域用のカウンタがしきい値を超えている場合にはさらなる命令を発行しない。各メモリ領域について、その目標の場所があるメモリ領域に存在する命令を発行するごとに、当該メモリ領域用のカウンタをインクリメントする。そして、ある命令が当該メモリ領域へのライトを実行するごとに、当該メモリ領域用のカウンタをデクリメントする。
しきい値は通常、ゼロに設定する。
【発明を実施するための最良の形態】
【０００６】
図１はスケーラブル・プロセッサ・システム１００の一般的な概略図である。それは上述したＩＢＭドケット番号ＹＯＲ９２００１０４３９に記載されている線形メモリ１６を使用している。説明を便宜にするために、リード要求用に１つのポート３を備え、ライト要求用に２つのポート４を備えるように当該メモリを拡張した。このようにしたのは純粋に各サイクルで２つの結果を供給しうる線形メモリ１６に適合するためである。２つの実行ユニット１７はこれらの結果１４を利用し、ライト要求を独立に出す。この構成により、これらの線１２上にある要求は互いに干渉しないことが保証される。
【０００７】
上（のぼ）り経路は３つの同時並行的な経路１１〜１２に分割されている。１つの経路１１はメモリへのリード要求を運び、残りの２つの経路１２はメモリへのライト要求を運ぶ。こうするのは純粋に便宜上であり、こうすることにより入力帯域幅が広くなることは全くない。
【０００８】
リード要求は２つの目標アドレスｘとｙを運ぶ。リード要求はまず始めの場所に行ってデータを収集し、次いで上り経路を辿り第２の場所へ行って第２のデータ片をを収集する。結果は要求されたデータ項目対を運びながら下り経路１３を辿る。この結果、経路の待ち時間は確実に増大するが、帯域幅に対する配慮は全く変化しない。
【０００９】
〔命令形式：〕
プロセッサはレジスタを持たず、そのすべてのデータに対して線形メモリ階層（レジスタを表わす最下層レベル）を使用する。命令の一般形式は、
ｏｐ（ｘ，ｙ，ｚ）（ただしｘ、ｙ、ｚはメモリ上の場所のアドレスである）
である。その意味は場所ｘおよびｙにあるデータについて演算（ｏｐ）を実行し、その結果を場所ｚにストアするということである。単項演算の場合には第２のオペランドを省略してもよい。単項命令が頻繁に使用されるのはｍｏｖｅ（ｘ，ｚ）命令である。この命令は場所ｘから場所ｚにデータをコピーするものである。
【００１０】
〔命令の発行と実行〕
図１を参照する。プロセッサ９は命令５０を発行する単一の発行ユニット１９と２つの実行ユニット１７から成る。各実行ユニット１７はデータが利用できるときにはすべての演算を実行することができる。発行ユニットと実行ユニットのうちのいくつかは単一のハードウェア・チップ上に形成されるハードウェアに実装することができる。命令は２つのフェーズすなわち発行フェーズと実行フェーズを経る。発行フェーズでは、線形メモリ１０にデュアル・オペランド・フェッチを依頼する。その要求には演算コードと宛先情報を付加するが、それらはデータとともに返される。実行フェーズはメモリがデュアル・オペランド・データを返したときに始まる。各実行ユニットはオペランド・データ１４を受け取り、演算を実行し、結果をストアするライト要求をメモリ１０に出す。命令はプログラム中に列挙されているのと同じ順序で発行する。メモリは命令が特定している以外のデータ移動を行わないから、プログラムはメモリを完全に制御しており、それが必要なときおよび場合にデータをプロセッサに近づける移動命令を発行することにより明示的にメモリ管理を行う。メモリのパイプライン化された性質により、他の命令の実行中にデータを同時並行的に移動させることが容易になる。通常、本発明を使用すると、プログラマーは移動命令を使用してプロセッサがあるデータを必要とするときまでに当該データを当該プロセッサに届けることができるようになる。
【００１１】
〔リード・アフター・ライト・ハザード〕
発行ユニットと実行ユニットは同時並行的に動作しているから、ある場所へのライト・オペレーションを実行依頼したあとに該場所への対応するリード・オペレーションを実行依頼することを保証する必要がある。以下、図２を参照して説明する。命令ｏｐ（ｘ，ｙ，ｚ）の場合、ｚへのライト要求は当該命令の発行と実行の間は未決であると言われる。後述するように、メモリ領域への未決のライトを追跡することによりハザードを避けることができる。図２では、実線の経路で移動（ｍｏｖｅ）命令２１の実行方法を示している。移動（ｍｏｖｅ）命令２１が発行されると、場所ｙがリード（ｒｅａｄ）され、データは実行ユニット１７に流入する。実行ユニット１７が実行すると、結果は場所ｘに送られてストア（ｓｔｏｒｅ）される。しかし、発行ユニットが同時並行的に進行しており、移動（ｍｏｖｅ）命令２１に続いて別の命令を発行する。引き続く命令の一例は加算（ａｄｄ）命令２２である。加算（ａｄｄ）命令２２の経路を破線１１ａで示す。もし、この加算（ａｄｄ）命令が先行するｘへのストア（ｓｔｏｒｅ）を実行する前に発行されると、ハザードが発生する。
【００１２】
〔フェンス（fence)カウンタ〕
プロセッサは有限組のフェンス・カウンタを備えている。各フェンス・カウンタは１つのメモリ領域に関連付けられている。メモリ領域のサイズを２の巾（べき）乗で選定すると、ｌｏｇ  Ｎ個必要になるだけである。したがって、ｌｏｇ  Ｎ個のカウンタを保持することは実際上、深刻な限界ではない。図３を参照する。ｏｐ（ｘ，ｙ，ｚ）のような命令を発行する（３１）ごとに、ｚを含む範囲に関連付けられたフェンス・カウンタをインクリメントする（３６）。そして、たとえば場所ｘとｙにあるデータをリードする要求をメモリに送る（図３の３７を参照）。取得したデータたとえば（データ１，データ２）は実行ユニットに転送する（図３の３８を参照）。実行ユニットが当該演算すなわちｏｐ（データ１，データ２）を実行し（３３）、場所ｚにライト要求を出したら（３３）、対応するフェンス・カウンタ（図１の１８を参照）をデクリメントする（３４）。したがって、フェンス・カウンタはそれに関連付けられた範囲の場所への未決のライトの個数を保持している。フェンス（fencing:防護）は（リリース・コンシステンシー・モデル（release consistency model)様式の) プログラムによって、ｆｅｎｃｅ（メモリ領域）なる形をした特別の命令を挿入することにより明示的に行う（図２の２３を参照）。発行ユニットがフェンス命令に遭遇すると（３２）、発行ユニットは対応するフェンス・カウンタがゼロになるまでストールする（３５）。プログラムはリード・ライト・ハザードを避けるためにこのメカニズムを使用することができる。また、このメカニズムはフェンス・オペレーション用に範囲と配置を賢明に選定することにより効果的に実現することができる。通常、カウンタはハードウェアで実装する。
【００１３】
極端な場合、すべての演算がその目標の場所についてフェンスによってうまくいく。これが正しく機能している間、実行はほとんど順次に行われる。ある領域にライトしたのち、その領域から別の領域にアクセスする前にフェンス命令を提示する命令群をできるかぎり多く集積するようにプログラムを構成することができる。フェンス・オペレーションの位置を賢明に選定しうるようにコンパイラ技術を開発することができる。
【００１４】
図４はスケーラブル・プロセッサ・システム１００の一般的な概略図である。それは線形メモリ１６を使用している。説明を便宜にするために、リード要求用に１つのポート３を備え、ライト要求用に２つのポート４を備えるように当該メモリを拡張した。このようにしたのは純粋に各サイクルで２つの結果を供給しうる線形メモリ１０に適合するためである。２つの実行ユニット１７はこれらの結果１４を利用し、ライト要求を独立に出す。この構成により、これらの線１２上にある要求は互いに干渉しないことが保証される。
【００１５】
リード要求は２つの目標アドレスｘとｙを運ぶ。リード要求はまず始めの場所に行ってデータを収集し、次いで上り経路を辿り第２の場所へ行って第２のデータ片をを収集する。結果は要求されたデータ項目対を運びながら下り経路１３を辿る。
【００１６】
ここで提案するメモリ・システム１０の構造を図４に示す。説明を容易にするために、システムは１次元に並べた一連の基本構成要素を備えているように示してある。基本構成要素はプロセッサに近いＬ1から始まりプロセッサから離れるのにつれて増加するように番号が付されている。ｉ番目の基本構成要素Ｌiは各々、ｍiと表記された単位メモリおよび２つのコントローラｕiとｄiを備えている。コントローラｕiはすべて単一のリンク５によって接続され、プロセッサからメモリ・セルまで要求を運ぶ「上り経路」を形成している。コントローラｄiはリンク対７によって接続され、メモリ・セルからプロセッサまで応答を運ぶ「帰り経路」を形成している。この構成では、プロセッサからの上り経路に単位時間に１つの要求を保持するが、プロセッサは帰り経路には単位時間に最大２つの応答を受け取りうることが必要である。したがって、この構成では、入力帯域幅の２倍の出力帯域幅を必要とする。また、このメモリ・システムに接続された単一のプロセッサ９が示してある。本発明のメモリ・システムには、（本願の譲受人が同時並行的に出願した）関連出願に記載したようなプロセッサを用いることができる。メモリ要求には目標メモリ・セル・アドレス、オペレーション（リード／ライト）、およびデータ（ライト・オペレーションの場合）が特定されている。サイズｎのメモリの場合、目標アドレスは１〜ｎの任意の整数である。ｎより大きな任意の数を用いてノーオペレーション（すなわちプロセッサが実際の要求を出さなかった）をシミュレートすることができる。
【００１７】
要求と応答はメモリが解釈しない追加の情報も運ぶ。たとえば、プロセッサが
ｏｐ（ｘ，ｚ）（ただし、ｘ、ｚはメモリ上の場所のアドレス）
という形の命令を実行する場合、その意味はメモリ上の場所ｘからデータを取得し演算（ｏｐ）を実行し結果をメモリ上の場所ｚにストアするということである。この命令の場合、出されるメモリ要求は
［ｒｅａｄ，ｘ，データなし，＜ｏｐ，ｚ＞］
という形をしている。この要求に対する応答は
［ｒｅａｄ，ｘ，データ，＜ｏｐ，ｚ＞］
という形をしている。この場合、データは場所ｘから取得した情報である。この応答は帰り経路上を一連の第２のコントローラを通りプロセッサに転送される。上に示した例において、プロセッサが応答を受け取ると、データについて演算を実行し結果たとえばｗを得る。次いで、結果ｗをメモリ上の場所ｚにストアする別の要求がプロセッサから上り経路上を第１のコントローラを通って転送される。この要求の形式は
［ｗｒｉｔｅ，ｚ，ｗ，情報なし］
のような形をしている。これは値ｗを場所ｚに格納するということを意味している。
【００１８】
目標アドレスｉを備えた要求は各々、上り経路を辿り、そのコピーがあらゆるレベルのメモリ・ユニットに到達する。メモリ・ユニットｍiはオペレーションに応じてデータをリードまたはストアし、それをコントローラｄiに転送する。ライト・オペレーションは応答を生成することなくここで終了する。一方、リード・オペレーションは要求を応答に変換させる。この応答は帰り経路を辿ってプロセッサに到達する。いま１通信リンクを行くのに１単位時間を要しメモリをリードするのに１単位時間要するものと仮定すると、目標アドレスｉに対するリード要求はその行程の間に輻輳（ふくそう）がない場合、（２ｉ＋１）単位時間要する。コントローラは輻輳を処理し、かつ、要求または応答の流れが先行する節で述べた要件に従うことを保証するように設計されている。以下、図５を参照してｕi、ｍi、およびｄiの詳細な論理を詳述する。
【００１９】
〔各サイクルにおけるオペレーション〕
〔図４参照〕
・  ｕiが各要求を受け取るごとに、１つのコピーをｍiに送り別のコピーをｕi+1に送る。最上位では（すなわちｉがｎの場合）、第２のコピーは単に破棄する。
・  ｍiはリード・オペレーションの場合にはメモリから要求にデータをコピーしたのち、ライト・オペレーションの場合には要求からメモリにデータをコピーしたのち要求を常にｄiに転送する。
・  図４に示すように、ｄiはＦＩＦＯキューとして構成された内部バッファ６を３個備えている。各サイクルの始めに、ｄiはｄi+1からの２つのリンクに存在する要求に対する応答をすべてその内部バッファに転送する。次いで、次に示すアルゴリズム（図５のフローチャートを参照）を用いて応答をｄi-1へ外出する２つのリンクにのせる。
（１）ｍiが出す要求が場所ｉに対するリードである場合、それを応答に変換したのち外出するリンクにのせる。さらに、（もしあれば）ｄiの内部バッファが出す応答を１つ除去して外出するリンクにのせる（図５の５１を参照）。
（２）ｍiが出す要求が場所ｉに対するライトである場合（５２）、あるいは要求がより高い場所を目標としている場合、（もしあれば）ｄiの内部バッファが出す応答を最大限２つ除去して外出するリンクにのせる（５４）。
（３）ｍiが出す要求が低い場所に対するものである場合（５５）、（もしあれば）ｄiの内部バッファが出す応答を１つ除去して外出するリンクにのせる（５６）。
【００２０】
〔モデルの性質〕
次に、スケーラビリティ（拡張容易性）に必要な２つの性質、すなわち各ユニットにおけるバッファ・サイズが一定でるあこと、およびアクセス待ち時間が線形であることを示す。
・  すべてのｄiの内部バッファのサイズは決して３を超えることがない。図６は各サイクル後のｄiにおける満たされたバッファの個数であるｘiに対する可能な遷移を示す図である。状態ｘi＝３に対するインバリアント（不変数）が明確に示すところによれば、該状態では入来するリンクを通じて入来しうる応答は高々１個であり、これによりｘiは決して３を超えることがないことが保証される。このインバリアントを示すために、状態ｘi＝３に入る２つの可能な遷移を調べる。まず、状態ｘi＝３への第１の遷移を考える。この遷移は始めにｘi＝２のときに起こり、ｄi+1からのリンクである２つの入来する弧（図４の７を参照）は両方とも応答を運んでおり、ｍiへの要求は場所ｉ以下へのものである。これにより、次のサイクルでは、ｄi+1から入来する弧には高々１つの応答しか存在しえないということが保証される。その理由は、ｍi+1は次のサイクルで、ｍiがこのサイクルで処理したのと同じ応答のコピーを処理するから、ｄi+1は上述したアルゴリズムの場合３を行い、１つの応答しか出力しない（図５の５５と５６を参照）からである。次に、状態ｘi＝３への第２の遷移を考える。この遷移は始めにｘi＝３のときに起こり、ｄi+1から入来する要求は１つであり、ｍiへの要求は場所ｉ以下のものである。これによりここでも、次のサイクルでは、ｄi+1から入来する弧には高々１つの応答しか存在しえないということが保証される。
・  場所ｉに対するリード要求は対応する応答を（４ｉ＋１）サイクル以内にプロセッサに返す。リード要求に対する応答は（ｉ＋１）サイクル後にｄiに到達する。なぜなら、その経路長が（ｉ＋１）であり、これらの経路における遅延はないからである。コントローラｄiはそれをすぐに外出する弧にのせる。というのは、コントローラｄiは上記アルゴリズムの場合１を実行するからである。上記アルゴリズムによると、バッファはすべてＦＩＦＯ順に空（から）にし、毎サイクルごとに１つのバッファが出す少なくとも１つの応答を除去する。したがって、ｄiが出す応答はプロセッサに到達する前に最大３ｉ単位時間の遅延に遭遇する。それゆえ、上り経路に要求を転送し対応する応答をプロセッサへの帰り経路に転送するのに要する合計遅延は高々（４ｉ＋１）である。
【００２１】
この構成によれば各場所におけるメモリ・オペレーションの順序が保存されるが、様々な場所におけるオペレーション完了の順序は不明であることが観察される。ここで提案するメモリ・システムはメモリ・チップに組み込まれている標準のメモリ論理回路を用いて実装することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明に係るスケーラブル・プロセッサの概略図である。
【図２】リード・オペレーションが対応するライト・オペレーションより前に出されると起こるリード・アフター・ライト・ハザードの概略を説明する図である。
【図３】本発明のプロセッサとともに使用しうる線形メモリ・システムの概略図である。
【図４】プロセッサへの要求に対する応答を転送する、コントローラで使用する論理のフローチャートを示す図である。
【図５】各状態が、コントローラｄiのバッファに格納されている応答の個数を示す状態図である。
【符号の説明】
【００２３】
３  リード要求用のポート
４  ライト要求用のポート
５  リンク
６  バッファ
７  リンク
９  プロセッサ
１０  線形メモリ
１１  上り経路
１２  上り経路
１３  下り経路
１４  オペランド・データ
１７  実行ユニット
１８  フェンス・カウンタ
１９  発行ユニット
２１  移動（ｍｏｖｅ）命令
２２  加算（ａｄｄ）命令
２３  フェンス（ｆｅｎｃｅ）命令
５０  命令
１００  スケーラブル・プロセッサ・システム
【図１】
2004527054.tif 000003
【図２】
2004527054.tif 000004
【図３】
2004527054.tif 000005
【図４】
2004527054.tif 000006
【図５】
2004527054.tif 000007
【国際公開パンフレット】
2004527054.tif 000008
2004527054.tif 000009
2004527054.tif 000010
2004527054.tif 000011
2004527054.tif 000012
2004527054.tif 000013
2004527054.tif 000014
2004527054.tif 000015
2004527054.tif 000016
2004527054.tif 000017
2004527054.tif 000018
2004527054.tif 000019
2004527054.tif 000020
2004527054.tif 000021
2004527054.tif 000022
2004527054.tif 000023
2004527054.tif 000024
2004527054.tif 000025
2004527054.tif 000026
2004527054.tif 000027
2004527054.tif 000028
【国際調査報告】
2004527054.tif 000029
2004527054.tif 000030