JPH0799515B2 - 命令フロ−コンピュ−タ - Google Patents

Description

【発明の詳細な説明】 発明の背景技術 1.発明の分野 この発明はデータ処理に関し、特に、高度なユーザープ
ログラム又は複数のユーザープログラムを直接的および
効果的に実行する多重命令ストリーム、多重データスト
リームコンピュータのアーキテクチャの改良に関する。

2.関連技術の背景 現在の技術における高性能処理は一般に、単一命令多重
データストリームベクトルプログラムを実行するのに最
適化したスーパコンピュータやアレイプロセッサに限ら
れる。これらのコンピュータは、更に特定の長さにベク
トル化したコードを実行するように最適化され、多重命
令ストリーム、多重データストリーム（MIMD）プログラ
ムを実行するようには設計されていない。

多重命令ストリーム、多重データストリームコンピュー
タについては、今迄に提案されており、いくつかのケー
スでは実現されている。米国特許第4,153,932号および
第4,145,733号はデータフローコンピュータについて記
載している。しかしながら、データフローコンピュータ
を実用化することは、１には、データフロー言語を効率
良く実行するコンピュータ組織を設計することが困難で
あるということもあって、難かしい。

多重命令ストリーム、多重データストリームコンピュー
タが実現化されている。一例としてはデネルコア（Dene
lcor）の異種エレメントプロセッサが挙げられ、この一
実施例が、ジリアンド他（Gilliand et al.）に付与さ
れた米国特許第4,229,790号に記載されている。異種エ
レメントプロセッサは相互接続された多重プロセッサコ
ンピュータである。各プロセッサはパイプライン制御お
よび機能ユニットを利用している。先行制約による不利
益は並列処理における命令文脈をパイプラインサイクル
レートで切換えることにより減少される。この異種エレ
メントプロセッサアーキテクチャは、コスト有効性が十
分で無く、又多くのアプリケーションに適用するには不
十分である。これは、主に、プロセッサの組織が複雑で
あることと、機能ユニットの利用化が低いことによる。
ジリアンド他により提案されたように、タスクスナップ
ショットレジスタを介してプロセッサパイプラインに接
続された多重データストリームを用いても、処理速度
が、単一プロセッサのリソースの有用性により限定され
てしまう。

他の初期のマルチプロセッサコンピュータとしては、２
種類、実現されている。第１の種類は、各データストリ
ームに対して１つのプロセッシングユニットを対応させ
た、独立したプロセッシングユニット群を用いている。
第２の種類は、いくつかのデータストリームにおいて、
有効に多重化される１つの中央処理装置を用いている。
独立したプロセッシングユニット群を用いた場合はコス
トが高くなり、先行の問題を受けやすい単一命令ストリ
ーム、単一データストリームアーキテクチャになる。第
２の種類の実現化を計った場合、先行の制約を減少する
ように、いくつかのデータストリームにおいて中央処理
装置を多重化することができる。

処理速度を改善し、競合の問題を最小にするその他の試
みとしては、1969年６月25日乃至27日の“並列プロセッ
サシステム、テクノロジー、およびアプリケーション”
のシンポジウムにおいて、13章の、エム・ジェー・フリ
ン（M.J.Flynn），エー・ポドヴィン（A.Podvin）およ
びケー・シミズ（K.Shimizu）著の“共有リソースを用
いた多重命令ストリームプロセッサ”に記載がある。こ
こには、個々のコンピュータが独自のデータと制御レジ
スタを有した並列コンピュータシステム組織が記述され
ているが、より実体的な実行機構群が欠けており、この
ためすべてのマシンにより、これらの実行機構群が共有
されている。この共有は、短かい時間間隔で同期がとら
れた時間フェーズ切換えにより行われる。実行リソース
を強力にパイプライン化して最大の動作帯域幅を得る努
力が成されている。実行リソースの各実行機能のパイプ
ラインファクタは、各コンピュータの同期ファクタに緊
密に関連付ける必要がある。この組織概念に基づいたシ
ステムは、共有リソースシステムに相関する多くの競合
の問題を避けることが要求される。

フリン他の文献によれば、各コンピュータは、それぞれ
独自のオペランドをフェッチし、それぞれ独自の命令を
作る機能を果すプロセッサとして記載されている。この
プロセッサは、命令は実行せず、命令を実行するように
実行リソース又は実行ユニットに要求する。この実行ユ
ニットは４つの時間フェーズアレイ又は各リングが８つ
のプロセッサから成るリングプロセッサにより共有され
る。この構成では、プロセッサ間の緊密な時間同期が必
要とされ、リング内の２つのプロセッサは、命令フェー
ズ、作成フェーズ、および実行フェーズが同じでない。
リングが異る各プロセッサは、特定のタイムスロットの
実行リソースに対して競合することができるので、競合
がオペランドフェッチ等と時間的にオーバラップさせる
必要がある。２つ以上のプロセッサが１つのオペレーシ
ョンしか受付けることのできないリソースを要求したと
き、プライオリティシステムを用いてこの衝突を回避す
る。

発明の開示 この発明は、データフロー概念と区別される命令フロー
概念を具現化した新しいコンピュータに関する。このコ
ンピュータは、高速並列計算が行え、高度の並列アルゴ
リズムを実現でき、独特のシステム構成により拡張的に
積重ねられる超大規模集積回路チップが2,3枚の設計
で、アーキテクチャが構成し得るという点で、超大規模
集積回路を用いて構成するのに便利な、独特のコンピュ
ータアーキテクチャを具現化する。

この命令フローコンピュータは、上述したように、プロ
セスコントロールユニット、関数実行ユニット、ローカ
ルメモリユニットおよびバス構造等のプロセッサコンポ
ーネント又はプロセッサユニットをプロセッサ内に伝統
的に取込み、各々が自己内蔵型ユニットである相互接続
ネットワークにより接続し、望しくは、アーキテクチャ
の構成において、論理的に等価に接続し、それによりユ
ニットがコンピュータのいずれかおよびすべてのリソー
スにより共有されることにより、マルチプロセッサアー
キテクチャと異る。

プロセスコントロールおよびファンクションユニットは
相互接続ネットワークのポートに接続された簡単なユニ
ットであり、大規模で複雑なプロセッサをネットワーク
ポートのユニットに置換えることができる。汎用プロセ
ッサ内部のバス構造は、通常のかつ大規模の相互接続ネ
ットワークにより置換えられる。相互接続ネットワーク
に結合される１つ以上のグローバルメモリは個々のプロ
セッサのメモリ機能を置換える。ユニット間のコミュニ
ケーションは、そのコンピュータのパイプライン構成の
相互接続ネットワークに生じる。従って、そのネットワ
ークに接続されたすべてのユニットは、クロック又はク
ロックに近い速度でパイプライン化できる。

プロセスコントロールを行うプロセスコントロールユニ
ットは、一連のプロセスが割当てられ、各プロセスは独
立したブロック又はパケットのシーケンシャルな命令群
を有している。各プロセスコントロールユニットは、割
当てられたプロセスを順次初期化し、相互接続ネットワ
ークを介して第１のプロセスのシーケンシャル命令パケ
ットの第１命令パケットを、前記命令によりアドレスさ
れたネットワーク内の他のユニットに送る。

第１のプロセスは、第１命令パケットの初期化された命
令群が実行され、そのプロセスに再リンクされる迄、即
保留される。

命令フローコンピュータは完全にパイプライン化されて
いるので、第２のプロセスの第１命令パケットが次のマ
シンサイクルで送られ、全プロセスが初期化される迄同
様に行われる。この実行シーケンスにより多重命令スト
リームにより単一パイプラインのタイムシェアリングが
得られる。

この命令フローコンピュータは、高度に競合したプログ
ラムを直接かつ効率良く実行するという点で、現在の並
列処理アーキテクチャよりも多くの利点を有している。
すなわち、実現技術によってのみ制限を受ける並列性と
拡張性を有している。モジュール化により設計および実
現コストを減少し、置換コストおよびプログラミングコ
ストを下げる効果がある。

この発明の他の利点は、添附図面並びに下記明細書の記
述から明らかである。

図面の簡単な説明 第１図は従来技術を代表するマルチプロセッサタイプの
コンピュータを示す図面； 第２図は多段相互接続ネットワークを採用した、この発
明による命令フローコンピュータを示す図面； 第３図は、第２図の命令フローコンピュータにおける代
表的な命令フローを示す図面； 第４図は命令パケットの１つの代表的なフォーマットを
示す図面； 第５図は命令フローコンピュータにおける並列命令スト
リームの命令群の１つの代表的なシーケンスを示す図
面； 第６図は、チェーニングを有した代表的な命令パケット
フォーマットおよびその実行を示す図面； 第７図は命令フローコンピュータに採用される代表的な
プロセスコントロールユニットのブロック図； 第８図は、この命令フローコンピュータにおけるグロー
バルメモリユニットにおけるフェッチ動作を視覚化した
図面； 第９図はこの命令フローコンピュータにおける代表的な
パイプラインプログラマブル関数ユニットにおける情報
のフローおよび作用を示す図面； 第10図はプログラムメモリおよび定数メモリを有したプ
ログラマブル関数ユニットのブロック図； 第11図は４×４スイッチノードで構成される16×16多段
相互接続ネットワークのブロック図； 第12図は４×４マルチポートメモリスイッチノードのブ
ロック図。

好適実施例の詳細な説明 従来のコンピュータ 第１図は、双方向相互接続ネットワークICNに並列に接
続されたプロセッサ１乃至プロセッサＮを使用する際の
従来技術の特徴を具現化する１種の並列処理コンピュー
タを示す。グローバルメモリユニット（GMU）はプロセ
ッサ外部の各メモリとして双方向ネットワークを介して
プロセッサと接続される。従って、プロセッサとグロー
バルメモリユニット間のデータは双方向相互接続ネット
ワークICNを両方向に移動する。プロセッサは、一般的
に、プロセッサ１に関連して示すように、プログラムメ
モリ（PGM）、命令デコードユニット（IDU）、ローカル
データメモリ（LDM）、コントロールユニット（CU）、
および関数ユニット（FU）で有している。

これらの機能ユニット、並びにレジスタ群および入出力
装置は、複雑なマルチバス構造を介して相互接続されて
いる。この構造は複雑な制御システムを必要とする。一
般には、このような制御システムを実行させるには高価
なランダムロジックおよび／又は低速の制御メモリが必
要になる。中間プログラミング；アセンブリプログラミ
ング、マイクロプログラミングおよびナノプログラミン
グがこの制御レベルを補助するために含まれる。

さらに、プロセッサの効率は、より高度なレベルの命令
に対して多くのクロックサイクルが必要になるので、制
限される。

一般には、プロセッサとグローバルメモリユニットは、
図示するように双方向型のネットワークにより接続され
るか、又は２つの単方向ネットワークにより接続され
る。

命令フローコンピュータ 第２図の独特な命令フローコンピュータにおいて、相互
接続されたプロセスコントロールユニット（PCU）、グ
ローバルメモリユニット（GMU）、およびプログラマブ
ル関数ユニット（PFU）のネットワークが示されてい
る。又命令フローコンピュータの一部に、オプションと
して命令デコードユニット（IDU）を含めることもでき
る。メモリマネージメントユニットおよび入出力ユニッ
トも又、スタンドアローンモードで動作する命令フロー
コンピュータに含めることができる。これらのユニット
はネットワークにより完全に相互接続され、ネットワー
クをはさんで互いに論理的に等距離にあり、命令ストリ
ーム群において共有できることが望ましい。命令ストリ
ーム群は、リアルタイムに各プロセスがそれぞれ割当て
られたプロセスコントロールユニット群により初期化さ
れる。各命令セットの命令群のブロック又はパケットは
相互接続ネットワークを介して径路が設定される。

第２図において実現される、完全に相互接続されたアー
キテクチャではユニット間に高コミュニケーション帯域
幅が必要になる。ユニットの数およびその動作レートが
帯域幅を決定する。例えば、ユニットが１命令あたり1M
Hzで動作するとすれば、16ユニット命令フローコンピュ
ータであればバスアーキテクチャにより得られるレート
として少くとも16MHzの相互接続帯域幅を要する。

さらに高速のユニットを用いたより大型の命令フローコ
ンピュータに要求されるより高い帯域幅では、多段相互
接続ネットワークアプローチを採用する必要がある。ク
ロスバーネットワーク、リングネットワークおよび多段
ネットワークは、それぞれ小型、中間、および大型の相
互接続のコストパーフォマンスが得られる。

第２図は、この発明の命令フローコンピュータの好適な
実現態様を示す。描かれた構成は、特にパイプライン組
織に適した第11図に示すタイプの多段ネットワークアー
キテクチャを表わしている。すべてのユニットを相互接
続すると共にパイプライン化することにより、非常に高
性能が得られる。理想的には、クロックレート命令が実
行できることが望しい。これによりファンクションユニ
ットの数およびベーシッククロックレートに直接比例し
た性能が得られる。主題が、参照符号（PD−84073）に
より、この明細書中に含まれる、この発明の譲受人に譲
渡された、 にファイルされたシリアル番号
のアール・ジェー・マクミラン（R.
J.McMillen）およびエー・ロスマン（A.Rosman）の共願
に記載されたＮ×Ｍパケット交換ノードにより構成され
る第11図のタイプの多段相互接続ネットワークは、全ユ
ニットの高帯域コミュニケーションを提供することがで
きる。このような相互接続ネットワークの性能は90％を
超える負荷条件の下で80％以上の効率を得ることができ
る。従って、命令フローコンピュータの性能は相互接続
ネットワークＥ（Ｎ）、ファンクションユニットの数Ｎ
（FU）、およびマシンサイクルレートＦの性能効率の積
になる。

性能＝Ｅ（Ｎ）×Ｎ（FU）×Ｆ 十分に区分けされた問題に対して得られるピークレート
は1.0に近い効率を生じる。

第２図の汎用コンピュータアーキテクチャを第１図のそ
れと比較するとわかるように、命令フローコンピュータ
は相互接続されたプロセッサネットワークではないとい
う点で、代表的な並列プロセッサコンピュータアーキテ
クチャと異る。この発明では、コンポーネントやユニッ
トをプロセッサ内に伝統的に取込み、制御、実行および
メモリ機能を提供すると共に、相互接続ネットワークに
より自己内蔵型簡素化ユニットとして論理的にコンポー
ネントやユニットを結合し、全リソースにより共有され
る。各プロセスコントロールユニット（PCU）のプロセ
スから発生した命令ストリームは実行が完了する迄ネッ
トワークを介してコンピュータの回りを連続的に移動す
る。ある時点をとらえると、それと同じだけの独立した
処理群に属する多くの命令群が各種の実行段階に存在す
る。

この構成では、プロセス群はサブルーチンのような独立
したブロック又はパケットのシーケンシャル命令群から
成る。プロセスのセットは、静的又は動的に各プロセス
コントロールユニットに割当てられる。従って、各プロ
セスは、識別番号又はアドレス、ステータス情報および
プログラムカウンタの等価物により表わされる。スター
ト時には、各プロセスコントロールユニットは第１プロ
セスからの第１命令をイニシャライズする。各プロセス
がプロセスコントロールユニットによりイニシャライズ
された後、第１のすなわち現在の命令パケットが、コン
パイル時に決められたアドレスに従って、所定のシーケ
ンスで他のユニットに送られる。この結果、第１のプロ
セスが保留になる。命令フローは例えば、コンピュータ
を介して、データをフェッチするためのメモリユニット
から、ファンクションユニット、メモリユニットへ進
み、プロセスコントロールユニットに戻る。同一プロセ
スの次の命令は、先行する命令の到着すなわち戻りによ
ってのみ開始されるので、シーケンシャル処理において
生じる先行の制約を避けることができる。

命令群は情報のパケットのフォーマットを取る。この命
令フローコンピュータは完全にパイプライン化されてい
るので、１つの命令パケットがコンピュータを介して移
動している間、プロセスコントロールユニットは他のプ
ロセスを開始し、そのプロセスの第１命令パケットはコ
ンピュータを介して、全プロセスが開始される迄、別の
プロセスの第１命令パケットが続くように経路が決めら
れる。この実行シーケンスは多重命令ストリームによる
単一パイプラインのタイムシェアリングと同等である。
コンピュータを介して流れる命令パケットは“空き”フ
ァンクションユニットに経路が設定され、非常に効率的
なハードウエアの利用が得られる。

この点に関する説明は後述する。

命令フロー この命令フローは、一般的な命令フローおよび対応する
命令フォーマットを示す第３図および第４図を参照する
ことによりさらに良く理解できる。第４図に示すよう
に、命令はプロセスコントロールユニット（PCU）にお
いて、始まりタグ（TAG）すなわちアドレスおよびリン
ク（LINK）が付けられ、この命令がプロセスコントロー
ルユニットに戻ってきたとき、この命令を特定のプロセ
スに再リンクさせるために用いられる。続いて特定の命
令がピックアップされるグローバルメモリユニットを識
別する命令アドレスおよびオペランド番号１とデータが
ピックアップされるグローバルメモリユニットアドレス
が続く。この後に、オペランド番号２のデータがピック
アップされるグローバルメモリユニットのアドレスが続
く。命令フォーマットの次段において使用されるプログ
ラマブルファンクションユニットのアドレス（TAG）が
識別され、実行されるファンクションを識別するオペレ
ーションコード（OP CODE）が識別される。命令フォー
マットの最後のブロックでは、この演算結果が格納され
るアドレスが識別される。すなわち、結果が格納される
グローバルメモリユニットが識別される。

命令フローを示した第３図において、この命令の実行は
明白である。プロセスはプロセスコントロールユニット
（PCU）において初期化され、第１の命令パケットが相
互接続ネットワークセクション（ICN）によりアドレッ
シングされた第１グローバルメモリユニット（GMU）に
渡される。ここで命令がピックアップされる。次に、命
令は第２グローバルメモリユニットに行き、オペランド
番号１がピックアップされ、もはや不要となったアドレ
スを置換える。そこから、命令は、相互接続ネットワー
クを介して次のアドレッシングされたグローバルメモリ
ユニット（GMU）に行き、そこでオペランド番号２がピ
ックアップされる。命令フローは、相互接続ネットワー
クを介して、アドレッシングされたプログラマブルファ
ンクションユニット（PFU）に進み、そこで命令フォー
マットのオペレーションコード（OP CODE）により識別
される処理機能が行われる。適切なファンクションユニ
ットに行くために、相互接続ネットワークは、以下述べ
るように、タグ（TAG）を用いて、命令を最もアクセス
可能なプログラマブルファンクションユニットに経路を
選定する。このファンクションユニットは浮動小数点演
算、固定小数点演算および超越関数発生のような特殊演
算機能を有している。ファンクションユニットとその数
の組合わせによりアプリケーションが依存する構成が決
まる。処理機能を完了すると、その結果が、相互接続ネ
ットワークを介してアドレッシングされたグローバルメ
モリユニット（GMU）に渡され、そこで処理機能の結果
が命令フォーマット（第４図）の最終ブロックにより識
別され格納される。命令フローは引き続きプロセスコン
トロールユニットに戻り、そこで第４図に示すフォーマ
ットで“結合（LINK）”により識別される初期化プロセ
スと再リンクする。

プロセスコントロールユニットのプログラムカウンタ
は、インクリメントされ、そのプロセスの次の命令がパ
イプラインすなわち相互接続ネットワークに入る準備が
される。特定のプロセスの最後の命令が、初期化するプ
ロセスコントロールユニットに戻ってくると、そのプロ
セスコントロールユニットにそのプロセスを終了するよ
うに知らせる。その最後の命令の状態が設定され、その
プロセスの完了が表示される。

以下の記述により、プロセスコントロールユニット（PC
U）は全プロセスを初期化し、終了させることがわか
る。ここでは、プロセスはそれぞれ命令パケットとして
配列されたシーケンシャルなリスト又は命令ブロック群
により定義される。各プロセスは一般に互いに独立して
いる。一般には、それらは大きなプログラムのサブルー
チンである。

命令のシーケンス 第５図は、多くの並列プロセッサに属する命令のシーケ
ンスを示す。プロセス１の命令１はI1（P1）として識別
され、プロセス１の命令９はI9（P1）として識別され
る。ここでは、複数のプロセスコントロールユニットが
相互接続ネットワークを介して結合された命令フローを
提供する。命令フローの方向は第５図の右側の破線によ
り示される。命令フローは、第３図に示すようにプロセ
スコントロールユニットから相互接続ネットワークを介
して１つ以上のグローバルメモリユニットに進み、さら
にプログラマブルファンクションユニットに進み、初期
化するプロセスコントロールユニットに戻る。第７図で
述べるように各プロセスコントロールユニットは、異る
プロセスを追跡する一連のプログラムカウンタを有して
いる。

チェーニングを有した命令フォーマット チェーニングを有した命令フォーマットを第６図に示
す。チェーニングを有した命令フォーマットは次の式の
処理で説明される。

Ｑ＜＝〔（Ａ×Ｂ）/C＋Ｄ〕/E Ｃは定数 IF（Q GT 1）THEN… ELSE… チェーニングは、コミュニケーションを最小化し、ファ
ンクションユニットの利用を最大にして性能効率を高め
る。チェーニングは、プロセスフローにメモリを通過さ
せて新オペランドをピックアップし、ファンクションユ
ニットを通って要求された演算を行うように指示する命
令フォーマットを提供することにより得られる。プログ
ラムメモリおよび定数メモリはファンクションユニット
に設けられ、共有機構および共有動作を支持および強化
する。

第６図（ａ）図はＱを得るために上記式を処理するチェ
ーニングされた命令を示す。このチェーニングされた命
令は第６（Ｊ）図でプロセスコントロールユニット（PC
U）により初期化される。（TAG）のラベルが付されたブ
ロックは相互接続ネットワークにより現在使用されてい
る相手先アドレスを示す。（ECC）のラベルが付された
ブロックはエラーチェックおよび訂正を示す。（SEQ）
のラベルが付されたブロックはシーケンスコードを示
す。オペランド１およびそのアドレス（OP1 ADR）はア
ドレスおよびデータ、および結果として生じるアドレス
およびデータにより識別される。オペランド２およびそ
のアドレス（OP2 ADR）は同様に識別される。プログラ
マブルファンクションユニット（PFU）はユニットおよ
びタイプにより識別される。プロセスコントロールユニ
ットの番号とリンクはブロック（PCU）で識別される。
第６（ａ）図の（PC）のラベルが付されたブロックはプ
ログラムカウンタを表わす。使用時には、チェーニング
された命令は右から左に読まれる。命令フローは第３図
および第４図の記述および下記記述から理解される。

プロセスコントロールユニットにより命令が初期化され
ると、命令は相互接続ネットワークを介して第１のアド
レッシングされたメモリ（MEM）に流れ、第６（ｂ）図
に示すタームＡがピックアップされる。命令フローは引
き続き、相互接続ネットワークを介して第２のアドレッ
シングされたメモリ（MEM）に流れ、第６（ｃ）図のタ
ームＢがピックアップされる。命令フローは相互接続ネ
ットワークを介して第１のアドレッシングされたプログ
ラマブルファンクションユニット（PFU）に流れ、ター
ムＡとタームＢが乗算される。ここで割算命令とオペラ
ンドＣが第６（ｄ）図に示すようにプログラムメモリお
よび定数メモリＣから抽出される。第２のプログラマブ
ルファンクションユニットにおいて、除算が行われ、第
６（ｅ）図に示す加算命令がピックアップされる。次に
アドレッシングされたメモリにおいて、第６（ｆ）図に
示すタームＤがピックアップされ、今迄展開されてきた
ように第６（ｇ）に示す次にアドレスされたプログラマ
ブルファンクションユニット（PFU）において算術式に
加算される。次にアドレッシングされたメモリ（MEM）
において、最後のタームが第６（ｈ）図に示すようにピ
ックアップされ、第６（ｇ）図に示す次の命令“除算”
が、最後にアドレッシングされたプログラマブルファン
クションユニット（PFU）におけるタームＥの値により
この時点で作られた式を割算し、第６（ｉ）図に示すＱ
を算出する。割算命令のステータスQGt1がセットされ、
命令がプロセスコントロールユニットと再リンクされこ
の式の一部であった処理の次の命令群が、条件分岐命令
から生じると初期化される。

プロセスコントロールユニット 代表的なプロセスコントロールユニットの詳細を第７図
に示す。ここでは、異るプロセスがプロセスキューに格
納される。このプロセスはプロセス番号により識別さ
れ、各命令はアドレスにより識別される。プログラムメ
モリは１つ以上のユーザプログラムを格納する。プロセ
スキュー１とプログラムメモリ２はダイレクトメモリア
クセスチャンネルを介してホストコンピュータにより制
御される。ホストコンピュータとダイレクトメモリアク
セスチャンネルは公知のアイテムであり、どちらもこの
発明を理解する上で必須のものではないので詳細に図示
しない。プロセスキュー１およびプログラムメモリ２
は、ホストコンピュータのダイレクトメモリアクセスチ
ャンネルと各制御ユニット3,4との間に接続されたバス
インタフェース５を介して制御ユニット3,4により制御
される。ホストコンピュータからプログラムメモリ２へ
の入力はレジスタ2aを介して接続され、プロセスキュー
１からプログラムメモリ２へのアドレスはコントロール
ユニット４により制御されるマルチプレクサ4aにより多
重化される。ランダムアクセスメモリ（RAM）６は保留
になっている処理を記憶している。プロセスが初期化さ
れると、プロセス番号がレジスタ７を介してランダムア
クセスメモリ６に接続される。各プロセス番号がランダ
ムアクセスメモリに格納されると、ランダムアクセスメ
モリの出力が回路８およびマルチプレクサ9,10を通って
プロセスキュー１を制御し、これらのプロセスからの以
後の命令を保留する。プロセスキューによる各プロセス
を初期化した後、その特定のプロセスに対する命令フロ
ーパケットが、プログラムメモリ２からレジスタ11を介
して出力フォーマットユニット12に結合され、出力フォ
ーマットユニット12はレジスタ13により相互接続ネット
ワーク（ICN）に接続される。従って、第４図又は第６
図に示すような一般的な命令フォーマットを有する命令
パケットは相互接続ネットワークに接続される。

第３図に示すように、前記特定命令パケットの処理機能
が完了し、その結果がグローバルメモリユニットに格納
されると、命令は、この命令を初期化したプロセスコン
トロールユニットに戻る。プロセスコントロールユニッ
トにこの命令が到達すると、レジスタ14およびコントロ
ールユニット15を介して前記命令が保留プロセスカウン
タ16に接続される。この結果、保留プロセスカウンタが
インクリメントされ、その出力がマルチプレクサ17によ
り、ランダムアクセスメモリのアドレスとなり、ランダ
ムアクセスメモリは初期化されたプロセスの番号を格納
する。現在出力されているランダムアクセスメモリ出力
は再び回路８およびマルチプレクサ９および10を介して
プロセスキューに接続され、実際には、相互接続ネット
ワーク（ICN）から戻ってきた命令に相関するプロセス
を再起動し、その結果そのプロセスにおける次の命令が
初期化され処理される。回路８は、プログラマブルファ
ンクションユニット（PFU）から戻った状態に応じて条
件付分岐を実行する。特定プロセスのエンド命令がプロ
セスコントロールユニットに戻ると、そのエンド命令
は、もちろんプロセスコントロールユニットに対して、
その処理を終了するように知らせる。

フェッチ動作 第８図は、グローバルメモリの命令パケットのアドレス
におけるデータを交換し、そのパケットステータスをリ
セットするフェッチ動作を示す。命令フローは相互接続
ネットワークを介して特定のグローバルメモリユニット
に接続される。この命令フォーマット（第４図参照）は
そのグローバルメモリユニットのロケーションアドレス
を有し、そのアドレスにおいて交換すべきデータを識別
する。その後、グローバルメモリユニットからの信号に
よりパケットステータスをリセットし、情報交換が行わ
れたことを表示する。この結果グローバルメモリユニッ
トの出力は相互接続ネットワークを介して次のアドレッ
シングされたコンピュータのユニットに接続される。

プログラマブルファンクションユニット プログラマブルファンクションユニットの代表的なパイ
プラインを第９図に示す。ここでは、入力データがオペ
レーションコードと共に、グローバルメモリユニットか
ら、相互接続ネットワークを介して、アドレスされたプ
ログラマブルファンクションユニットの入力に接続され
る。プログラマブルファンクションユニットのパイプラ
インは入力フォーマットセクション20および１乃至ｎの
番号が付された各プロセッシングステージから成る。各
デコードおよび格納ステージ（DC,SR）はオペレーショ
ンコード（OP CODE）を受取り、それぞれ受取ったオペ
レーションコードに応じてプロセッシングセグメント１
乃至ｎの１つを制御する。プロセスデータ又は出力デー
タは出力フォーマットセクション21を介して相互接続ネ
ットワークに接続される。クロック動作に応じてパイプ
ライン制御されるハードウエアにおいて浮動小数点“加
算”および浮動小数点“乗算”のような複雑な動作を行
うプログラマブル関数ユニットは単一のVLSIチップが市
販されている。

浮動小数点加算器を表わすプログラマブルファンクショ
ンユニットの例を第10図のブロック図に示す。相互接続
ネットワークからこのファンクションユニットへの入力
データはレジスタステージ23に受取られ、ステージ１ロ
ジック回路24に送られ、命令入力のフォーマット化が行
われる。ここでは、命令およびアドレスと共にオペラン
ド1,2が作られ、プログラムカウンタ（PC）が作られ、
さらにオペレーションコードが作られる。レジスタ25お
よび26はオペランド、それらのオペランドの命令および
アドレスを受取る。レジスタ27はプログラムカウンタを
受取り、レジスタ28はオペレーションコードを受取る。

ステージ２ロジックの一部を形成する比較および選択制
御回路29はオペランドデータを受取り、命令に定義され
た算術式に従って処理のためのアレンジを行い、その後
ファンクションユニットを介して、そのアドレスに応じ
たレジスタおよびロジック回路に供給される。レジスタ
30,31,32および33は比較選択ユニット29の出力を格納
し、必要に応じてシフトコードを含む指数値によりソー
トされる。

これらのレジスタの出力は、ステージ３ロジック回路の
一部を形成するシフト回路34を介して処理されバッファ
レジスタ35,36および37に格納される。

ステージ４ロジックの一部を形成する算術論理ユニット
は初期算術演算を行い、レジスタ39を含む算術チェーン
におけるレジスタ群の次段のレジスタ40に格納される。

次にステージ５ロジックプロセスにおいてプライオリテ
イエンコーダ41によるプライオリテイエンコーディング
が行われ、介在レジスタを介してステージ６ロジック回
路に送られ、算術ロジック回路45において算術処理が行
われ、指数が作られ、左シフト回路46の処理が実行さ
れ、正規化関数が作られ、算術処理を完了する。この処
理されたデータは出力フォーマットに接続される。

プログラムカウントPCはロジック２のプログラムカウン
トインクリメンタ50、プログラムメモリ51、レジスタ52
を介して増分から特定プログラムのアドレスを受取るロ
ジックステージ３を含むロジックステージを介して処理
される。

ロジックステージ４のデコーダ54はレジスタ53を介して
受取ったプログラムメモリデータをデコードし、プログ
ラムカウント値およびプログラムメモリアドレスを供給
する。

プログラムカウント値およびメモリアドレスはロジック
５において、それぞれカウント処理回路56およびコンス
タントメモリ57に接続される。ファンクションユニット
の最終レジスタステージのレジスタ群は現在プログラム
カウント値およびデータアドレスを出力フォーマッタ47
に接続する。

出力レジスタセクション60はフォーマット化されたデー
タを相互接続ネットワークに接続し、プログラムカウン
トおよびアドレスに従って他のメモリユニット又はファ
ンクションユニットに供給する。

オペレーションコード（OP CODE）に応答したレジスタ
ステージ61乃至65のファンクションは同一レジスタステ
ージの他のレジスタと連絡するデータをデコードし、ス
タートさせると共に他のレジスタファンクションの制御
を行う。

多段相互接続ネットワーク 第２図に示すような命令フローコンピュータの多段相互
接続ネットワークの一部から成る多段相互接続ネットワ
ークの一部の例を第11図に示す。

これは２段の４×４スイッチノードから構成される、16
×16多段相互接続ネットワークである。出力ポート14に
対する入力ポート１の接続が示される。この配列では情
報パケット交換が用いられている。パケット交換は、比
較的小さな固定サイズの“パケット”と呼ばれる情報単
位が、ノード間路が利用できる状態になると、交換ノー
ドから交換ノードへ移動する通信モードである。ネット
ワークの入力前に全通信路を確立する必要がない。パケ
ットは、第４図および第６図に示すように、径路指示情
報、および多少のデータ又はコマンドを含むヘッダから
成る。応用例によっては、パケットは全径路の命令を含
むことができる。その他の場合には、ポインタのみが必
要になる。パケット交換は、伝送される基本情報単位が
小さく、プロセッサの通信パターンが、計算の過程にお
いて急速に変化するアプリケーションに適用される。パ
ケット交換はさらに、適切に設計されたシステムは非常
な高性能を得るのに役立つ。

この多段相互接続ネットワークは４×４交換ノードで構
成される。Ｂ×Ｂ交換ノードで構成されたＮ×Ｎ多段相
互接続（Ｎは入力ポート数）は各々（Cla）Ｃ（N/B）交
換ノードのＣ（LOG_BN）ステージ、すなわち許容最高機
能を有し、最小整数（ａより大きい）に等しい。Ｂが増
大すると、ステージの数とステージあたりの交換ノード
の数が減少する。従って、出力遅延回路および潜在的に
はコンポーネントカウントへの入力を減少させるため
に、Ｂをできるだけ大きくすることが望しい。Ｂのサイ
ズの制限要因は交換ノードの複雑さである。パケット交
換クロスバーであるので、その複雑さはＢの関数として
指数的に増大する。

ネットワークの重要な特性は、径路指示タグ（第４図参
照）を用いて行われる分散態様で制御可能なことであ
る。各交換ノードは、各パケットの径路指示タグの一部
を調べて受取ったパケットをどのように径路指示するか
を決定する。タグのフォーマットは、各交換ノードのサ
イズおよびネットワークのステージの数により決定され
る。Ｂ×Ｂ交換ノードが用いられる場合、タグはベース
Ｂデジットで所望の相手先アドレスを表わすことにより
作られる。

４×４交換エレメントから構成される第11図に示す16×
16ネットワークにおいて、１ステージあたり16/4＝４交
換ノードがありLOG₄16＝２ステージある。このネットワ
ークの径路指示タグは所望の相手先をベース４に表わす
ことにより作られる。第11図に示す例はソースアドレス
ポート１から相手先ポート14＝32₄への径路である。０
乃至３の番号が付された４つの出力の１つを選択する各
ステージに相関するデジットがある。第11図において、
最上位桁はステージ１の交換ノードにより調べ、最下位
桁はステージ０において調べる。

ベースＢ＝４は２のべき乗であるので、各ベース４デジ
ットは２ビットのバイナリで表現できる。従って、従前
の例では径路指示タグ32₄は11₂,10₂のバイナリで表わせ
る。これらのビットが縦続接続されて1110が形成され、
14のバイナリ表示が得られる。それゆえ、４×４交換ノ
ードから構成されたネットワークに対する径路指示タグ
を得るための計算は必要無い。各交換ノードは、単にタ
グの２ビットを調べ、相関するパケットをどのように径
路指示するかを決める。

多重ポートメモリ交換ノード ４×４多重ポートメモリ交換ノードが第12図に示され
る。この交換ノードは８ポート,12ワードメモリとコン
トロールロジックセクション21とで構成される。４入力
（書込み）ポートの各々はメモリの３ワードに排他的に
アクセスし、同様に出力（読出し）ポートの各々は全ワ
ードに独立してアクセスする。

コントロールロジックは、自身と接続されている他の交
換ノードとハンドシェーキングを行い、多重ポートメモ
リにアドレスを発生し、情報パケット間の調停を行う。
交換ノードに入力される全リクエスト（R1,R2…）は、
ノードが調べる必要のあるタグビットを付加している。
４×４の設計の場合、２ビット必要である。これらのビ
ットは満杯／空ステータスビットと共に12セルを有した
ステータスレジスタ22に格納される。各セルはメモリロ
ケーションに対応し、タグとステータスビットを格納す
ることができる。プライオリテイエンコーダロジック
は、リクエストライン（Ｒ）上にリクエスト信号を受取
ると３つのセル（与えられた入力ポートに対して）のう
ち第１の利用可能なセルを選択する。３ビットのステー
タスビットがすべて“満杯”でない限り許可出力信号が
許可ライン（G1,G2…）の１つに出力される。この結果
リクエストしている情報パケットが８ポートメモリ20の
相関ロケーションに書込まれる。タグビットはステータ
スレジスタ22に書込まれ、対応する満杯／空ビットは
“満杯”にセットされる。

パケット間の調停は２ステップで行われる。第１に、所
望の出力ポートに従い、満杯セル内の全タグビットがデ
コードされグループ化される。この結果バッファ調停ユ
ニット23は、同一入力ポートに入力し、かつ同一出力ポ
ートを要求しているパケット間のいずれかのパケットを
選択する。第２ステップにおいて、ポート調停ユニット
24はランダムに、同一出力ポートを要求しているパケッ
ト間のいずれかのパケットを選ぶ。同一入力ポートに入
力されたパケットが異る出力ポートを要求する限り、全
パケットは調停の第２ステップに関与する。従って、メ
モリの位置によりパケットが阻止されることはない。パ
ケットは同一出力ポートを要求する他のパケットと競合
した場合にのみ阻止される。

ラッチ回路25は調停プロセスの結果をラッチし、リクエ
スト信号はパケットにより要求された出力ポートに対し
て発生される。適切な読出しアドレスが、使用される各
出力ポートに対して、アドレス発生セクション26により
発生される。許可されたリクエストに対して、適切な満
杯／空白ステータスビットが“空白”にリセットされ
る。リクエストが許可されなかった場合、パケットはメ
モリに残り、次のサイクルの期間調停処理を繰返す。こ
のアプローチは情報パケット当り１つ以上のワードによ
り使用することができる。この交換ノードの設計は各情
報パケットあたり４ワードとみなす。

ここに一般的に記述された交換ノードは立方体型の交換
ノードとして記述することもできるし、ネットワークも
立方体のネットワークとして記述することもできる。汎
用型のネットワークは、ロバート・ジエー・マクミラン
（Robert J.McMillen）およびハワードジエイ・シーゲ
ル（Howord Jay Siegel）著“ハイブリットキューブネ
ットワーク（The Hybrid Cube Network）"CH1571−9/80
/0000−0011,1980,IEEEの論文およびロバート・ジェー
・マクミラン（Robert J.McMillen），ジョージ・ビー
・アダムスIII（George B.Adams,III），およびハワー
ド・ジェイ・シーゲル（Howard Jay Siegel）著「PASM
用相互接続ネットワークにおける４×４交換ノードの性
能と実施（Performance and Implementation of 4 by 4
Switching Nodes in an Intercounection Network for
PASM",0190−3918/01/0000/0229,1981,IEEE,の論文に
記載されている。

このネットワークは、ロバート・ジェイ・マクミラン
（Robert J.McMillen）およびアンドリュー・ロスマン
（Andrew Rosman）の出願番号 出願日
であり、上記したこの発明（PD−84073）の譲受
人に譲渡された共願に詳細に記載されている。

この命令フローコンピュータは並列ソフトウエアを実行
するのに適している。理想的には、このアーキテクチャ
は、常にアイドル状態にあるアドレスされないメモリを
除いて、いかなる部品も用いずにフルクロックレートで
ハードウエアを走らせることができる。このスピード
は、命令実行（命令フェッチ、デコード、オペランドア
ドレス発生、オペランドフェッチ、実行、結果書込み、
および再結合）の全フェーズが独立した共有リソース内
でオーバラップしているために得ることができる。これ
らのリソース（例えばPFU）はパイプラインハードウエ
アにより基本クロックレートですべて実行することがで
きる。１クロックの同一のスループットレートでパイプ
ラインセグメントを設計することにより、コンピュータ
内の各リソースはフォールスルーファーストインファー
ストアウト（fall−through first in/first out）とし
て生じる。従って全コンピュータは、流れが全体に一定
に維持されたパイプの迷路を通して流れる流体のモデル
として見える。パイプラインの実行を先行の制限、分
岐、あるいはキャッシュミスのように、散らせる通常起
こる問題は避けられる。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 米国特許4365292（ＵＳ，Ａ) ＡＦＩＰＳ Ｊｏｉｎｔ Ｃｏｍｐｕｔ ｅｒ Ｃｏｎｆｅｒｅｎｃｅ 1976, （1976年６月），ＡＦＩＰＳ Ｍｏｎｔｖ ａｌｅ，Ｇ．Ｊ．Ｎｕｔｔ，“Ａ ｐａｒ ａｌｌｅｌ ｐｒｏｃｅｓｓｏｒ ｆｏｒ ｅｖａｌｕａｔｉｏｎ ｓｔｕｄｉｅ ｓ”，Ｐ．769−775

Claims (9)

【特許請求の範囲】
1. 【請求項１】各プロセスがシーケンシャル命令群からな
   るプロセス群を各々が有する複数のプロセスコントロー
   ルユニット群と； ファンクションユニット群と； メモリユニット群と； 前記プロセスコントロールユニット群、前記ファンクシ
   ョンユニット群、および前記メモリユニット群間で相互
   にデータをやりとりするように並列路で相互接続する相
   互接続ネットワークと； 前記少なくとも１つプロセスコントロールユニットの一
   部を形成し、前記シーケンシャル命令群を有するプロセ
   ス群のうちの第１プロセスを開始する手段と； 前記少なくとも１つのプロセスコントロールユニットの
   一部を形成し、前記第１プロセスの開始に応答して前記
   第１プロセスのシーケンシャル命令群の第１命令を前記
   相互接続ネットワークを介して前記他のユニット群へ伝
   送する手段とで構成され、前記伝送手段は、前記第１プ
   ロセスのシーケンシャル命令群の第１命令を前記プロセ
   スコントロールユニットからデータフェッチのためにメ
   モリユニットに伝送し、処理のためにファンクションユ
   ニットに伝送し、前記プロセスコントロールユニットへ
   戻すことを特徴とする命令フローコンピュータ。
2. 【請求項２】前記ユニット群間のすべての通信が前記相
   互接続ネットワーク上で行われるように、前記相互接続
   ネットワークは前記プロセスコントロールユニット群、
   前記ファンクションユニット群、および前記メモリユニ
   ット群を相互接続することを特徴とする請求の範囲１に
   記載の命令フローコンピュータ。
3. 【請求項３】前記伝送手段は、前記少なくとも１つのプ
   ロセスコントロールユニットにより第２プロセスを開始
   し、前記第１プロセスの第１命令が前記相互接続ネット
   ワークを介して移動している間に前記第２プロセスの第
   １命令を前記相互接続ネットワーク上に伝送する手段を
   さらに有することを特徴とする請求の範囲１に記載の命
   令フローコンピュータ。
4. 【請求項４】前記第１命令を伝送する手段は、先行する
   命令がプロセスコントロールユニットに戻されたときに
   のみ、そのプロセスコントロールユニットにおける前記
   第１プロセスの命令群の次の命令を開始する手段を有す
   ることを特徴とする請求の範囲１に記載の命令フローコ
   ンピュータ。
5. 【請求項５】前記相互接続ネットワークはＮ×Ｍパケッ
   トスイッチノードからなる多段相互接続ネットワークで
   構成され、前記ユニット群が各々接続される入力ポート
   および出力ポートを有することを特徴とする請求の範囲
   １に記載の命令フローコンピュータ。
6. 【請求項６】前記ファンクションユニット群はプログラ
   マブルファンクションユニット群であり、前記ファンク
   ションユニット群のいくつかはプログラムメモリを有す
   ることを特徴とする請求の範囲１に記載の命令フローコ
   ンピュータ。
7. 【請求項７】前記プログラマブルファンクションユニッ
   ト群は各々コンスタントメモリを有していることを特徴
   とする請求の範囲６に記載の命令フローコンピュータ。
8. 【請求項８】前記すべてのプロセス群が開始されるまで
   前記プロセス群の各プロセスの第１命令を連続的に開始
   する手段を各プロセスコントロールユニットに設けたこ
   とを特徴とする請求の範囲１に記載の命令フローコンピ
   ュータ。
9. 【請求項９】前記相互接続ネットワークは並列データ処
   理路を有し、各処理路はプロセスコントロールユニット
   と；少なくとも１つのメモリユニットと；および少なく
   とも１つのファンクションユニットを有し、各プロセス
   コントロールユニットは独立したシーケンシャル命令群
   を有する少なくとも１つのプロセスを開始し、前記各並
   列デー処理路における各命令が完了し、各プロセスコン
   トロールユニットに戻された後に、そのプロセスの次の
   命令が開始されることを特徴とする請求の範囲１に記載
   の命令フローコンピュータ。