JPH0370034A - 順次プログラムの並列実行のためのコンピュータ・システム及び方法並びにデータ値割当方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は一般にプログラム記憶式ディジタル・コンピュ
ータに関し、さらに具体的には、順次プログラムを実行
する際に並行処理技術を利用することができるコンピュ
ータ・システムに関するものである。

Ｂ、従来技術及びその課題 並列処理は、ディジタル・コンビュータテ高い性能を実
現する手段として近年ますます一般的になってきた。最
少限のシーケンス間連絡または同期化しか必要とせず、
同時に実行することが可能な、大きくかつ明確な命令シ
ーケンスをユーザ・プログラム内で見つけることに主と
して関心が集まっていた。過去に提案された大部分のマ
ルチプロセッサ及び並列プロセッサの設計は、これらの
シーケンスについて行なわれた選択、及び提供された連
絡及び同期化機能により区別することができる。この並
列処理手法をさらに推し進めると、同時に実行される命
令シーケンス間の連絡及び同期化要件が増大するため、
高性能並列プロセッサに余分のプロセッサを追加するこ
との利点が減少する。

一般に、命令の実行は２つの独立したオペレーションに
区分することができる。第１のオペレーションは命令を
選択し、実行のためそれをＡＬＵにディスパッチするこ
とである。第２のオペレージ３ンは、選択された命令を
実際に実行することである。確立された規約によれば、
第１の命令が入力オペランドとして使用する中間結果を
もたらす命令、または、やはり第１の命令が更新する値
を参照または更新する命令がすべて実行を完了するまで
、命令を実行のために選択できない。初期のブロセッー
サ設計では、こうした制約（データ依存関係制約とも呼
ばれる）は、先行するすべての命令が実行を完了したと
きにのみ命令を出すことによって満たされる。この手法
は、浮動小数点演算などいくつかの種類の命令が専用の
浮動小数点プロセッサにより数サイクルに渡って実行さ
れるので、制限的である。浮動小数点命令の完了後まで
非浮動小数点命令の発行を制限すると、プロセッサの幾
つかの部分が不必要に遊休状態のままとなる可能性があ
る。

パイプライン式実行装置を使用する現在のプロセッサ設
計では、先行する命令が実行を完了する前に命令をディ
スパッチすることができる。そのような命令と、実行パ
イプラインで処理される別の命令の間にデータ依存関係
がある場合は、ハードウェア・インターロック機構を使
って、そのデータ依存関係が解消されるまで、ディスパ
ッチされた命令の実際の実行が阻止される。しかし、こ
の場合は、この阻止された命令に続く命令も、たとえそ
れが現在実行中のまたは阻止されている命令に依存する
ものでなくても、同様に阻止される。

上記の阻止現象のため、パイプライン式プロセッサでの
命令ディスパッチ速度が、１機械サイクル当たり１命令
よりも小さくなることがよくある。

さらに、ハードウェア・インターロック機構が複雑なた
め、この設計を、複数の命令のディスパッチを同時に可
能にする設計に拡張することができない。

超長命令ワード・アーキテクチャでは、複数の命令（一
定の最大数まで）を各機械サイクルでディスパッチする
ことができる。これらの機械では、コンパイル時間分析
を使って、連続した命令をグループにまとめる。グルー
プ内のすべての命令に同時にディスパッチすることがで
きる。この種のグループ化が適切に働くためには、ある
グープ内のある命令によって生成された結果を同じグル
ープ内の後続の命令が使用することはできない。この制
約により、同時にディスパッチ可能な命令の数が制限さ
れる。同時にディスパッチ可能な命令の数を制限するも
う１つの問題は、条件付き分岐命令である。これらの命
令は、論理条件に基づいてプロセッサによって実行され
る命令の順序を変更する可能性がある。条件付き分岐の
後にくる命令は、条件付き分岐が評価されるまで実行さ
れない。

上述の問題点に加えて、超長命令ワード機械上で実行さ
れる１つの命令グループは、前のグループ内のすべての
命令が実行を完了するまでディスパッチされない。この
制約が存在するのは、データ依存関係制約のため、及び
命令グループ全体のパイプライン化には極めて高価な処
理ハードウェアが必要となる可能性があるためである。

第３のタイプのプロセッサ設計は、データ・フロー（以
下ではデータ流れとも言う）コンピュータである。この
種のコンピュータでは、データを処理する命令が同時に
実行できる。たたし、命令は、その入力オペランドがす
べて使用可能になるまで実行できない。ある命令の出力
オペランドが、後続の命令の入力オペランドとなるので
、命令の順序付けは自動的に制御される。この種のコン
ピュータは、構造化されていない制御流れグラフを発生
する条件付き分岐オペレーション等の制御流れを扱う際
には非効率的である。これらの機械では、そのような制
御フロー（以下では制御流れとも言う）命令を処理する
ための最も効果的な方法は、制御流れの問題が解決され
るまで逐次処理モードに切り換えることである。

コンピュータ・アーキテクチャに関する第１３回年次国
際シンポジウム（１９８６年）報文集（Ｐｒｏｃ、　１
３ｔｈ　Ａｎｎｕａｌ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　
Ｓｙｍｐ、　ｏｎＣｏｍｐｕｔｅｒ　Ａｒｃｈｉｔｅｃ
ｔｕｒｅ、　１９８６）　、１）　Ｉ）　、　２９７−
３０６に所載のＷ、ツー（）１ｗｕ）等の論文”ＨＰＳ
ｍ。

ａ　Ｈ５ｇｈ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｒｅ５ｔｒｉ
ｃｔｅｄ　Ｄａｔａ　ＦｌｏｗＡｒｃｈｉｔｅｃｔｕｒ
ｅ　Ｈａｖｉｎｇ　Ｍｉｎｉｍａｌ　Ｆｕｎｃｔｉｏｎ
ａｌｉｔｙ”は、処理される制御情報及びデータが共に
単一のメモリに記憶されるシステムに関するものである
。

単一の命令デコーダが分岐予測を使って制御流れ命令を
処理し、それが出会う各データ処理命令に対してデータ
流れ命令を発生する。これらの命令が組み合わされて、
既存のデータ流れ命令を集中ノード・テーブル内に含む
データ流れグラフになる。ノード・テーブル内の命令は
、１群の並列データ主導型プロセッサによる実行を待っ
ている。ノード・テーブル内の命令の入力オペランドが
使用可能になると、その命令はデータ流れプロセッサの
１台によって実行すべく選択される。

米国特許第４４７６５２５号明細書は、命令が実行に先
立って取り出され、復号されるパイプライン制御式デー
タ処理システムに関するものである。命令が復号され、
評価されるとき、算術演算及び記憶命令が同時実行がで
きるように組み合わされ、したがって、全実行時間が減
少する。

米国特許第４２９５１９３号明細書は、２つ以上の命令
を同時に実行するように設計されたプロセッサに関する
ものである。実行される命令は、それぞれせいぜいＮ個
の命令を有するグループに分割される。これは、たとえ
ば、コンパイル中に行なうことができる。各グループは
（Ｎ個の命令を実行するために使用されるアクセスの数
よりも少ない）所定数のデータ・アクセスのみを行なう
ことができ、さらに各アクセスは異なるデータ値を対象
とする。グループ内の各命令は別々の命令実行ハードウ
ェアを使用する。

米国特許第３５７３８５４号明細書は、先にオペランド
がメモリから取り出されてから、それらのオペランドを
使用する演算式がＡＬＵによって評価される、パイプラ
イン式アーキテクチャに関するものである。オペランド
が事前に取り出されるので、オペランドがメモリから取
り出されるのをＡＬＵが待つのにかかる時間が大幅に減
少する。

この事前取出し機能は、分岐命令に出会う前にそれらの
分岐命令を評価して、プログラム実行速度を増大させる
のに有用である。

Ｃ０課題を解決するための手段 本発明は、第１及び第２の種類の混合した命令を含む順
次プログラムを並行して処理するコンピュータ・システ
ムで具体化される。このシステムは、１度にＮ個の命令
をＮ個のディスパッチ装置のグループに供給する命令バ
ソファを備える。

ディスパッチ装置は、第１の種類の命令を直接実行し、
第２の種類の命令は原始（プリミティブ）命令に変換し
て、それをＭ個の実行装置にディスパッチする。実行装
置は、原始命令を同時に実行するデータ主導型プロセッ
サである。

本発明のもう１つの実施態様によれば、処理システムに
よってアクセスされるデータ空間は、主としてディスパ
ッチ装置によってアクセスされる第１のセグメントと、
主として実行装置によってアクセスされる第２のセグメ
ントに分割される。

本発明のさらに別の実施態様によれば、条件付き（ｃｏ
ｎｄｉｔｉｏｎａｌ　）セクションからの命令が先に実
行されてから、このセクションを保護する条件が評価さ
れるという条件付き割当て命令が設けられる。この条件
の評価で、この命令の実行を行なうべきでなかったこと
がわかった場合は、結果は捨てられる。そうでない場合
は、その結果が条件付き割当てオペレーションのオブジ
ェクトに割り当てられる。

Ｄ、実施例 Ｄｌ、概説 以下に説明する本発明の実施例は、通常のプログラムか
らの複数の命令を各機械サイクルでディスパッチし、実
行することができるプロセッサ・アーキテクチャである
。このプロセッサは、科学技術用アプリケーション・プ
ログラムを効率的に実行するように設計されている。こ
のアーキテクチャは、科学技術用プログラムでは２１１
１類の異なるデータを使用するという傾向を利用したも
のである。第１の種類のデータは、プログラム内の制御
の流れを決定するために、または大きなアレイに対する
インデックスとして使用される、比較的少数のスカラー
変数からなる。第２の種類のデータは、主としてプログ
ラムによって操作される実際のデータを含む大きなアレ
イからなる。このデータは通常浮動小数点形式であり、
複数の機械サイクルに渡るオペレーションによって操作
される。

本発明で提案するアーキテクチャは、複数のディスパッ
チ装置及び複数の実行装置を使用する。プログラムの制
御流れを決定するために、及びアレイ要素のインデクシ
ングに使用されるデータを、操作される実データから区
別する。これら２種類のデータは、別々のアドレス空間
に割り当て、別々のメモリ・モジュールに記憶するが、
それらのアドレス空間の間でデータを移動することが可
能である。第１の種類のデータに対するオペレーション
は、主として通常の制御流れの形でディスパッチ装置で
実行される。第２の種類のデータに対するオペレージ田
ンは、主としてデータ主導式に実行装置で実行される。

したがって、前にディスパッチされた１組のオペレージ
研ンが実行を完了する前に、新しい１組の複サイクル浮
動小数点演算セットを実行装置にディスパッチすること
が可能である。条件付き割当て命令が命令セットに導入
される。これは、短い条件付きセクションからの命令を
、との全クシ１ンを保護する条件が評価される前に実行
するために使用される。この命令を使用することにより
、条件付き分岐命令によって生じる遅延を回避すること
ができる。

第１図を参照すると、順次プログラムで並列性を活用す
るための例示的アーキテクチャは、５つの基本的構成要
素を含む。すなわち、命令メモリ２０１１装置２０４と
２０８を含むＭ個のディスパッチ装置のグループ、クロ
スバ−・ネットワーク２０７、装置２０８と２１０を含
むＭ個の実行装置のグループ、及びデータ通信ネットワ
ーク２１２である。

データ通信ネットワーク２１２は、Ｃ−Ｌ、　　ウー（
ｌＪｕ）等の論文”Ｏｎ　ａ　Ｃ１ａｓｓ　ｏｆ　Ｍｕ
ｌｔｉｓｔａｇｅＩｎｔｅｒｃｏｎｎｅｃｔｉｏｎ　Ｎ
ｅｔｗｏｒｋｓ＋）ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎ
ｓｏｎ　Ｃｏｍｐｕｔｅｒｓｓ　Ｖ　ｏ　ｌ　、　　Ｃ
−２９、Ｎｏ、　　８　（１９８０年８月）、Ｉ）り、
８９４−７０２に記載された１群のネットワークの１つ
である。この論文を引用により本明細書に合体する。ま
た、ネットワーク２１２は、以下に説明するクロスバ−
・ネットワーク２０７等の通常のクロスバ−交換機ネッ
トワークでもよい。

命令メモＩＪ　２０１は、ディスパッチ装置に供給され
る命令のシーケンスを含む。これらの命令は２つの種類
に分けることができる。第１の種類の命令は、プログラ
ムの流れを制御し、アレイ・インデックスを決定する整
数演算である。第２の種類の命令は、大きなデータ構造
を操作するオペレーションである。

ディスパッチ装置２０４ないし２０６は、第１の種類の
命令を直接実行し、第２の種類の命令を原始オペレーシ
ョン・シーケンスに変換する。第２図を参照すると、各
ディスパッチ装置は定数メモリ３０２．３個のアドレス
・メモリ３０３．３０４．３０５、及び演算論理機構（
ＡＬＵ）３１０を含む。第１の種類の命令は、ＡＬＵ３
１０によって実行される。

クロスバ−・ネットワーク２０７は、ディスパッチ装置
２０４ないし２０６から供給された原始コマンド・シー
ケンスを実行装置２０８ないし２１０のうちの選択され
たものに転送する。

実行装置２０８ないし２１０は、これらの原始オペレー
ションを実行する。実行装置２０８−２１０はそれぞれ
、算術オペランドを記憶し、検索するデータ・メモリ２
１１−２１３を含む。第３図を参照すると、浮動小数点
ＡＬＵ４１１は、原始オペレーション・シーケンスで指
示されるように算術論理オペレーションを実行スる。Ａ
ＬＵ４１１は、データ・メモリ４１２に送られるオペラ
ンド値と、データ・メモリ制御装置４１６に送られる制
御信号を発生する。データ・メモリ制御装置は、メモリ
４１２へのデータの転送、及び実行装置２０８−２１０
のメモリ間でのデータの転送を制御する。データ通信ネ
ットワーク２１２は、実行装置間のデータ転送オペレー
ションを実行するために使用される。

Ｄ２．詳細な説明 第１図に示す例示的システムでは、コンピュータ・シス
テムによって実行される命令のシーケンスを表すプログ
ラムが、命令メモリ２０ｉ内に記憶される。命令メモリ
２０１内の各ワードは、命令グループと呼ばれ、複数の
命令からなる。各命令は、３つまたは４つのフィールド
を含む。すなわち、実行されるオペレーション（命令コ
ード、オペレーション・コード）、（オペレーションの
［ｉに応じて）１つまたは２つのソース・オペランド、
及び宛先オペランドである。第２の種類の命令の場合は
、これらのフィールドは原始命令または原始コマンドに
変換される。

命令グループは、命令メモリ２０１からディスパッチ装
置２０４−２０８に供給される。命令メモリ２０１は、
Ｍ個の命令（Ｍはプロセッサ内のディスパッチ装置の数
）からなる１つの命令グループを各機械サイクルで読み
出し、ディスパッチ装置に送る（１つのディスパッチ装
置当たり１命令）ことができるように構成されている。

第２図は、例示的ディスパッチ装置のブロック・ダイヤ
グラムである。第２図に示すように、各ディスパッチ装
置は３つのアドレス・メモリ３０３．３０４．３０５と
定数メモリ３０２を含む。各ディスパッチ装置のアドレ
ス・メモリ及び定数メモリは、それぞれ当該の単一デー
タ構造の複数のコピーを表す。

各ディスパッチ装置内の定数メモリは、同じ値を含む。

これらのメモリは、定数やデータ・メモリ２１１−２１
３内の構造化データの基底アドレス等、プログラムの実
行中変化しないデータを保持するために使用される。こ
の種のデータは頻繁にアクセスされるが、プログラムに
よって使用されるデータ記憶域の小さな部分しか占めな
い。したがって、定数メモリは、小型の高速メモリ・モ
ジュールとして実施され、各ディスパッチ装置に同じも
のが複数個設けられる アドレス・メモリ３０３．３０４及び３０５は、データ
・メモリ２１１−２１３内のオペランドのアドレス、ア
レイに対するオフセット、ループ定数等のデータ項目を
保持する。この種のデータは頻繁にアクセスされるが、
ときどきしか変更されない。この種のデータも、プログ
ラムによって使用されるデータ記憶域の比較的小さな部
分しか占めない。このメモリは、各ディスパッチ装装置
に同じものが複数個設けられる。ディスパッチ装置内で
、複数同時アクセス能力を与えるため、アドレス・メモ
リの内容が３回複製される。したがって、１機械サイク
ル中に、システム内の各ディスパッチ装置ごとに３回の
読取りオペレーションと１つノティスバッチ装置からの
１回の書込みオペレーシロンを実行するように、それぞ
れのアドレス・メモリを条件付けることができる。デー
タは、アドレス・メモリ３０３．３０４．３０５の各コ
ピーから別々に読み取ることができるが、すべてのディ
スパッチ装置２０４−２０６に渡る共通書込みバス３１
９から同時にすべてのコピーに書き込まれる。このアク
セス技術により、すべてのディスパッチ装置２０４−２
０６内のすべてのアドレス・メモリ３０３．３０４．３
０５で同じ内容が維持される。各機械サイクルで１回の
書込みオペレーションしか行なえないという制限は、す
べてのプロセッサに渡る複数の書込みバスと、複数ボー
トを有するアドレス・メモリ・モジュールとを設けて、
各バスによって運ばれる値を全メモリ・モジュールに同
時に書き込むことができるようにすることにより、なく
すことができる。さらに、ディスパッチ装置の３回の読
取りオペレーションは、もっと高速のメモリ回路または
複数ボート付きメモリ・モジュールを使用すれば、２個
以下のアドレス・メモリ・モジュールでサポートするこ
ともできる。

例示的ディスパッチ装置２０４のオペレーションは、命
令が命令メモリ２０１から命令レジスタ３０１に転送さ
れるときに開始する。命令フィールドＳ１及びＳ２の値
、すなわち、ソース・オペランドのアドレスが、それぞ
れ当該のアドレス・メモリ・モジュール３０３及び３０
４のアドレス入力ポートに供給される。これらの値は、
ディスパッチ装置２０４で命令を実行するためのアドレ
ス入力オペランドを直接アドレスすることができ、ある
いは実行装置２０８−２１０で命令を実行するためのア
ドレス・オペランドを直接または間接にアドレスするこ
とができる。これらの値が間接アドレスであるときは、
アドレス・メモリ３０３．３０４及び３０５から供給さ
れる値は、データ・メモリ２１１−２１３内の記憶セル
のアドレスである。第１のソース・オペランドのアドレ
スＳ１は、定数値を読み出すために定数メモリ２０２に
も送られる。

レジスタ３０１の命令コード（オペレーション・コード
）・フィールドに応じて、マルチプレクサ３０７及びマ
ルチプレクサ３０８は、現在の命令用のオペランドを供
給するため、メモリ３２０．３０３．３０４及び３０５
から供給される値のうちのある値を選択する。これらの
オペランドはディスパッチ装置２０４内のＡＬＵ３１０
によって使用され、あるいは実行装置２０８にディスパ
ッチされた命令用のオペランドまたは入力オペランドの
アドレスとして使用される入力値でもよい。

レジスタ３０１に保持された命令のフィールドＤの値が
、アドレス・メモリ３０５のアドレス入力ポートに供給
される。この値に応答して、メモリ３０５は、レジスタ
３０１に保持された命令の結果を記憶するためのアドレ
スを供給する。

マルチプレクサ３０８によって供給される値は、フィー
ルドＳ２で示される位置におけるアドレス・メモリ３０
４の内容か、またはフィールドＳ１で示される位置にお
ける定数メモリ３０２の内容のいずれかである。マルチ
プレクサ３０７によって供給される値は、フィールドＳ
１で示されるアドレスにおける定数メモリ３０２の内容
か、またはフィールドＳ１及びＳ２のいずれかで示され
る位置におけるアドレス・メモリ３０３及び３０４の内
容のいずれかである。

命令コード（オペレージ８ン・ツー１’）ニヨって示さ
れる演算（オペレーション）がディスパッチ装置２０４
で実行されるときは（すなわち、アドレス・メモリ３０
３または定数メモリ３０２に保持されたデータに関する
整数演算）　、ＡＬＵ３１０によって実行される。ＡＬ
Ｕ３１０で実行される演算の一例は、メモリ・アドレス
３０３から得られたアレイ・オフセット値を、定数メモ
リ３０２から得られた基底値に加算することである。

ＡＬＵ３１０から供給される出力値は、ドライバ３０９
を介して書戻しバス３１９に送られ、各ディスハツチ装
置２０４−２０６内のアドレス・メモリ・モジュール３
０３．３０４．３０５のすへてに書き込まれる。プロセ
ッサによって実行されるプログラムは、任意の機械サイ
クルで、１つのディスパッチ装置だけが書戻しバス３１
９を介して当該のアドレス・メモリにデータを送ること
ができるように書き、またはコンパイルすることが望ま
しいＯ 命令コードによって示される演算がディスパッチ装置で
実行されない場合は（たとえば、複雑な浮動小数点演算
）、ディスポ・ノチ装置によって１組の原始コマンドに
変換され、これらのコマンドが実行装置２０８−２１０
の１つまたは複数に送られる。

ディスパッチ装置は、各コマンド用のソース・オペラン
ド情報をマルチプレクサ３０７を介して送る。各コマン
ド用の宛先アドレス情報は、アドレス・メモリ３０５か
ら直接供給される。実行装置に転送される命令の場合は
、これらのオペランド及びオペランド・アドレスが、そ
れぞれＰＥ番号発生論理要素３１１．３１２．３１３に
供給される。これらの論理要素は、定数のデータ値を修
正せずにバスし、メモリ・アドレス値を当該のデータ・
メモリ・モジュールに対する識別番号（すなわち、デー
タ・メモリ・モジュールが存在する実行装置の番号及び
そのモジュール内のアドレス）に変換する。本発明のこ
の実施例では、データ・アドレスはそれぞれの実行装置
のデータ・メモリ・モジュール間に、一定の大きさのブ
ロックとしてインタリーブされる。したがって、ＰＥ番
号発生論理要素３１１．３１２．３１３は、アドレスさ
れたデータが存在する実行装置を決定するため、入力ア
ドレス値から所定の１組のビットを選択することができ
る。アドレス値の残りのビットは、選択された実行装置
のデータ・メモリ・モジュール内のアドレスとして扱わ
れる。別の実施例では、プログラム式論理（図示せず）
を使って各実行装置のデータ・メモリ・モジュール内で
より柔軟な３０の区画に区分し、上述の方法で避けるこ
とができない「一定の大きさのブロック」という制約を
取り除くことができる。

ノード番号発生論理要素３１４は、プログラム命令から
導出される各原始命令に共通な識別ノード番号を割り当
てるために使用される。任意の時間におけるすべてのノ
ード番号は一意的であるが、実行済みのプログラム命令
に対するノード番号は必要に応じて再利用することがで
きる。ノード番号は、たとえば、各ディスパッチ装置２
０４−２０６内の８ビツト・カウンタ（図示せず）によ
って発生することができる。このカウンタは、特定のデ
ィスパッチ装置に割り当てられた連続するアドレス空間
内の初期値にセットされ、機械サイクルごとに増分され
る。この方式はいつでも、ディスパッチされたがまだ実
行されていない命令の数があらかじめ指定された設計限
界よりも小さくなるのでうまく働く。

ディスパッチ装置２０４−２０８によってディスパッチ
されたプログラム命令は、３つのカテゴリ、すなわち、
算術論理命令、条件付き分岐命令、及び条件付き割当て
命令に分類される。無条件分岐命令は、命令バッファに
よって処理される。

各算術命令または論理命令は、ディスパッチ装置により
、３種類の原始オペレージ３ンまたは原始コマンド、ス
ナわち、オペレーション・コマンド、ロック・コマンド
、及び１つまたは２つの送［：ｌ　？　７　Ｆ　Ｉｔ：
　変換サレる。オペレーション・コマンドは、実行され
るオペレーション、親命令に対するノード番号、及びこ
のオーレージ３ンの結果が記憶される局所データ・メモ
リ４１２内の位置からなる。ノード番号は、ディスパッ
チされたがまだ実行されていないオペレーションを一意
的に識別する。ロック・コマンドは、親命令によって更
新されるデータ・メモリ位置を、この更新が実際に行な
われるまで、後続の命令が読み取り、または更新するの
を妨げる。

送信コマンドは、その命令の入力オペランドを含むデー
タ・メモリ・モジュールを有する実行装置ｉ！２０８−
２１０に送られる。このコマンドは、要求された入力オ
ペランド値を局所データ・メモリから親コマンドが実行
される実行装置に供給するように、実行装置２０８−２
１０を条件付ける。

送信コマンドは、３つのフィールドを有する。すなわち
、オペランドが取り出されるデータ・メモリ・モジュー
ル内のアドレス、オペランドが送られる先の実行装置２
０８−２１０を識別する値、及び同じプログラム命令か
ら発生されるすべての原始オペレーションに共通なノー
ド番号である。

プログラム命令が１つのソース・オペランドを使用する
か、それとも２つのソース・オペラントラ使用するかに
よって、各プログラム命令ごとに１つまたは２つの原始
送信コマンドが発生される。

原始オペレーション用のソース・オペランドは、いずれ
かの実行装置２０８−２１０のデータ・メモリ・モジュ
ールから得ることができる。本発明のこの実施例では、
原始コマンドによって指定されるオペレーションは常に
、そのオペレーションの結果が記憶されるデータ・メモ
リ・モジュールを有する実行装置で実行される。ただし
、どの実行装置もこのオペレーションを実行することが
できる。この場合、オペレーション・コマンドは、結果
を適当なデータ・メモリ・モジュールに記憶するために
使用される追加のフィールド（図示せず）を含むことが
できる。

条件付き分岐命令は、本発明のこの実施例では特別な扱
いをする。条件付き分岐命令を含むプログラムは、条件
付き分岐命令が常に特定のディスパッチ装置２０６（す
なわち、最後のディスパッチ装置）に送られるように、
命令メモリ２０ｉ内で物理的に並べられる。命令は同時
に実行されるが、コンピュータ・システムの構成は、任
意の機械サイクルでそれぞれのディスパッチ装置に供給
された命令が、順序外れで実行されないようになってい
る。条件付き分岐命令は、条件付き分岐命令の後に続く
命令が分岐の解決後まで実行されないようにするため、
最後のディスパッチ装ｆｉ１２０６に割り当てられる。

本発明のこの実施例では、分岐命令が常にディスパッチ
装ｆｆ！　２０−６に割り当てられるようにするための
命令の順序付けは、条件付き分岐命令の出現に基づいて
、プログラム命令をせいぜいＮ個のメンバを有するグル
ープ、（Ｎはディスパッチ装置の数）に分割することに
よって実現される。Ｎ個よりも少ないメンバを有する命
令グループは、条件付き分岐命令の前に空文字または「
ノー・オペレーション」命令を挿入することにより、Ｎ
個のメンバを有するように拡張される。これらのステッ
プにより、分岐命令が命令シーケンス内で所望の位置を
占めるようになる。

条件付き割当て命令は、その命令セットを保護する条件
を評価する前に命令セットを実行するために使用される
。この種の命令は不必要な取出し遅延を回避する。条件
付き割当て命令は、３オペランド命令、すなわち、２つ
のソース・オペランド及び１つの宛先アドレスを有する
命令である。

第１のソース・オペランドはプール値である。第２のソ
ース・オペランドと宛先オペランドは同じ形式であるこ
とが好ましい。第２のソース・オペランドの値は、第１
のオペランドが真である場合に、宛先アドレスで示され
る位置に割り当てられる。そうでない場合は、どのよう
な処置も取られない。

原始コマンドは、クロスバ−・ネットワーク２０７を介
して実行袋ｆｉｌｆｆｉ２０８−２１０にディスパッチ
される。ネットワーク２０７は、いずれかのディスパッ
チａｉ２ｏ４−２ｏｅの３つの出力ポートのうちの任意
の１つを実行装置２０８−２１０のいずれかに結合する
ことができる、通常のクロスバ−交換機を含むことがで
きる。適当な命令順序を維持するため、それぞれのディ
スパッチ装置から供給される原始コマンドは、機械サイ
クルを規定するクロック信号のそれぞれ異なる位相と同
時に、ネットワーク２０７に供給される。クロスバ−・
ネットワーク２０７は各ディスパッチ装置の出力ポート
を、クロック信号のそれぞれの位相と同時に、その要求
された実行装置に結合する。

ネットワーク２０７は１つの実行装置に対する要求を待
ち行列に入れ、連続するクロック位相の間の時間に２つ
のそのような要求を処理することができる。これらの要
求は、それらが命令グループで現れる順に待ち行列に入
れられる。ネットワーク２０７のこの機能により、プロ
グラム命令から発生されたすべての原始コマンドがそれ
ぞれ当該の実行装置にディスパッチされ、次の後続のプ
ログラム命令から発生された原始コマンドがディスパッ
チされる前に受け取られるようになる。クロスバ−・ネ
ットワーク２０７の代りに、多段ネットワーク等の他の
相互接続方式を使用してもよい。

第３図は、実行装置２０８−２１０の工っとして使用す
るのに適した回路のブロック・ダイヤグラムである。第
３図で、選択された実行装置に到着した原始コマンドが
、命令バッファ４０１に記憶される。バッファ４０１は
、たとえばノード番号によってアドレスされる高速ラン
ダム・アクセス・メモリまたは連想メモリ・アレイでよ
い。原始オペレーションは、他の実行装置２０８−２１
０のデータ・メモリ４１２からソース・オペランドが得
られ、宛先アドレスでロックが得られるまで、このバッ
ファで待つ。このバッファ４０１内の各ワードは３つの
フィールドに分割され、そのうちの２つ、すなわち４０
２と４０３は実際の入力オペランド値を保持し、残りの
１つ、すなわち４０４は命令コード及び宛先アドレスを
保持する。

この３つのフィールドはそれぞれ有効ビット４０５．４
０６．４０７を含む。オペレーション・コマンド及び宛
先アドレス・フィールド４０４もロック・ビット４０８
を含む。ロック・ビット４０８がセットされていないと
きは、命令はまだ実行の準備ができていない。このビッ
トは、前の命令が依然として要求しているデータを含む
メモリ位置がオペレーションによって変更されないよう
にするために使用される。

クロスバ−・ネットワーク２０７を介して供給される送
信原始コマンド及びロック原始コマンドは、データ・メ
モリ４１２内部の送信／ロック・コマンド・バッファ４
１５に供給される。次にこれらのコマンドの処理につい
て詳細に説明する。

たとえば、要求されたオペランドを別の実行装置から受
け取ったとき、命令バッファ４０１内のアドレスされた
位置に対して更新が行なわれるたびに、命令レディ回路
４０９はこの更新を知らされる。更新を知らされると、
命令レディ回路４０９は、更新された命令のアドレスに
おける有効ピッ）４０５，４０６．４０７及びロック・
ビット４０８を読み取って、命令が実行の準備ができて
いるかどうか判定する。命令が準備完了と判定すると（
すなわち、有効ピッ）４０５．４０６．４０７及びロッ
ク・ビット４０８がすべてセットされているとき）、命
令レディ論理回路は命令をレディ待ち行列４１０に置き
、命令は最終的にこの待ち行列から演算論理機構４１１
によって実行される。

データ・メモリ制御装置４１６は、ＡＬＵ４１１とデー
タ・メモリ４１２の間の連絡、ならびに送信原始オペレ
ーション及びロック原始オペレーションの処理に対して
責任を負う。

実行装置内のデータ・メモリ・モジュール４１２は、３
種類の情報を保持できるように区分された記憶セルのア
レイからなる。まず、算術論理演算のソース及びオペラ
ンドであるか、または算術論理演算によって発生された
結果であるデータ値を保持する全クシ３ン４１３がある
。次に、据置き（ｄｅｆｅｒｒｅｄ　）要求リストを保
持するセクション４１４がある。最後に、セクション４
１５は、ネットワーク４１８から到着し、データ・メモ
リ制御装置４１６によって検査されるのを待っている送
信コマンド及びロック・コマンドを保持する。

据置き要求リストは、データ依存関係の制約のために直
ちに処理することができない送信コマンド及びロック・
コマンドを保持する。これらの制約は、送信コマンド及
びロック・コマンドによって指定された、アドレスされ
た記憶セルがそれ自体前のロック・コマンドに応答して
ロックされているときに存在する。

データ・メモリ制御装置４１６は２種類の要求を受け取
る。すなわち、ＡＬＵ４１１から到来する書込み要求（
ＷＲ）と、送信／ロック・コマンド・バッファ４１５及
び据置き要求リスト４１４から到来する送信コマンド及
びロック・コマンド（ＳＬＲ）である。ＡＬＵ４１１か
ら到来する要求に優先権が与えられる。データ有効ピッ
）　４１７は、メモリの、データ値を保持するために使
用されるセクション４１３内の各位置と関連している。

このビットは、そのメモリ位置が有効データを有する場
合は“１゛である。その位置が有効データを含むときは
、その位置に関する送信コマンドは直ちに満足させるこ
とができる。

第４図は、原始送信コマンドの実行を示す流れ図である
。ステップ６０１で、送信コマンドを受け取る。次にス
テップ５０２で、そこからデータが送られる、アドレス
された位置のデータ有効ビ、。

トがテストされる。データ有効ビ・ソトが＋１“′であ
る場合は、ステップ５０３で、データ値を、そのデータ
値を受け取る実行装置及びそのデータが使われるオペレ
ーション・コマンドのノード番号の指示と共にネットワ
ーク２１２に供給することにより、送信コマンドが満足
される。そうでない場合は、ステップ５０４で、送信コ
マンドが据置き要求リスト４１４に記憶される。据置き
要求リスト４１４に置かれたコマンドは、連係リスト・
データ構造に記憶される。メモリ位置のデータ有効ビッ
トが“Ｏ“のとき、この位置の内容は据置き要求リスト
４１４を指すポインタとして扱われる。項目をまったく
有しないリストを指すポインタとして、またはリストの
最後の項目を指す次の連係ポインタとして、空白ポイン
タが使用される。

空白ポインタは、前に選んだ負の数で表すことができる
。

記憶セルのデータ有効ビットがロック・コマンドによっ
てオフにされると、記憶セルによって保持される値が、
空白の据置き要求リスト・ポインタに変更される。

第５図は、原始ロック・コマンドの実行を示す流れ図で
ある。ステップ６０１で、ロック・コマンドをデータ・
メモリ制御装置４１６が受け取る。

次にステップ６０２で、データ有効ビット４１７が評価
される。ステップ６０３で、データ有効ビットが“工“
′の場合は、データ記憶域４１３のデータ有効ビット４
１７が°Ｏ″に−ｋ　ントされ、口、ンク・ビット要求
（ＬＢＲ）命令が命令バッファ４０１に送られる。この
命令は、ロック・コマンドと同じメート番号を有する原
始オペレーションのロック・ビットをＩＩ　Ｉ　Ｔ＋に
セントする。ステノブ８０４で、無効データを有する位
置に関するロック・コマンドが、無効データに関する送
信コマンドが処理される（上述）のと同様にして据置き
要求として処理される。

第６図は、ＡＬＵ４１Ｌからの書込み要求の実行を示す
流れ図である。ステップ７０１で、書込み要求及び書き
込むべきデータ値をデータ・メモリ制御装置４１６が受
け取り、ステップ７０２で、データ記憶域４１３内の要
求された位置に関するデータ有効ビットが評価される。

データ有効ビットが１″の場合、ステップ７０３で、エ
ラーが発生する。データ有効ビットがＯの場合は、ステ
ップ７０４で、このメモリ位置に関する据え置かれた送
信コマンドまたはロック・コマンドが存在するかどうか
メモリ制御装置が判定する。そのようなコマンドが存在
しない場合は、ステップ７０８で、データ値がそのメモ
リ位置に書き込まれ、実行が完了する。しかし、据え置
かれた送信コマンドまたはロック・コマンドが存在する
場合は、これらのコマンドが、データ・メモリ制御装置
によって保持されたデータ値を使って処理される。ステ
ップ７０５でロック・コマンドに出会うまで、またはス
テップ７０４で据置き要求リストが空になるまで、ステ
ップ７０９で、リストからの送信コマンドが処理される
。

ステップ７０５でロック・コマンドに出会った場合は、
ステップ７０６で、アドレスされたメモリ位置が据置き
要求リストの残りの部分を指すようにセットされ（他に
据置き要求が存在しない場合は空白にセットされ）、デ
ータ有効ビットがｎＯ“°にセットされる。この場合、
入力データ値はアドレスされた記憶セルに記憶されない
。据置き要求がロック・コマンドをまったく含まない場
合は、送信コマンドが、データ・メモリ制御装置４１６
によって保持されたデータ値を使って処理される。次に
、データ値がアドレスされた記憶セルに記憶され、その
記憶セルに対する有効ビット４１フが”１″にセットさ
れる。データ・メモリ制御装置４１６によって保持され
たデータを使って要求リストを処理すると、データ・メ
モリ４１２のデータ記憶部分４１３に関する不必要な読
み書きが避けられる。

この種のプロセッサに十分適したプログラムの一例は、
ガラス・ザイデル反復手順を用いてＡｘ＝ｂの形の連立
工次方程式を解くプログラムである。Ａマトリックスは
通常線であり、したがって、各行は通常の行ポインタ及
び列インデックスの形で表される。プログラムの下記の
ステートメントバカラス・ザイデル・アルゴリズムを１
反復実行するものである。

１０　　ｄｏ　３０　ｉ＝１．１００ ｔｅ１００ｔｅ　：ｂ（ｉ） ｄｏ　２０　ｊ　：ｒｏｗｐｔｒ（ｉ）、　ｒｏｗｐｔ
ｒ（ｉ＋１）−１ｔｅｍｐ（ｉ）　＝ｔｅｍｐ（ｉ）　
−ｅｎｔｖａｌ（ｊ）　”ｘ（ｃｏｌｉｎｄｌ）） ２０　　　ｃｏｎｔｉｎｕｅ ｘ（ｉ）　　：ｔｅｍｐ（ｉ）　　／　ｄｉａｇ（ｉ）
３０　　　ｃｏｎｔｉｎｕｅ 最も内側のループに間接アドレツシングが含まれている
ため、このコードはベクトル化することが難しいことは
周知である。しかし、上述のプロセッサは、以下に示す
ように、最も内側のループの１反復に属するすべての命
令を２機械サイクルでディスパッチすることができる。

アレイｘｓ　ｔ・ｅｍｐｌｄｉａｇ及びｅｎｔｖａｌは
データ・メモリ２１１−２１３にあり、アレイの残りの
部分及びスカラー量はアドレス・メモリ３０３．３０４
．３０５及び定数メモリ３０２にあるものとする。

−時変数Ｉ　Ｉ、ＪＬＩＭ、ＣＪはアドレス・メモリ内
に割り振られ、ＦＴＥＭＰはデータ・メモ１ノ・モジュ
ール内に割り振られる。ＦＴＥＭＰをアレイにすること
により、このコードの実行を速くすることができる。

サイクル　　命令 ｉ　　＜−１； ＩＩ　＜−ｉ＋１；　　ｊ　＜−ｒｏｗｐｔｒ（ｉ）；
ｂｒａｎｃｈ　　（ｉｇｌｏｏ）−＞　　７；ｔｅｍｐ
（ｉ）　　＜−、ｂ（ｉ）　；ＪＬＩＭ　　＜−ｒｏｗ
ｐｔｒ　　　（ｉｉ）；ＣＪ　　＜−ｃｏｌｉｎｄ（ｊ
）； ｂｒａｎｃｈ　　（ｊ＞ＪＬＩＭ）１０　−＞　　６；
ｍｕｌ　ＦＴＥＭＰ　＜−、ｅｎｔｖａｌ（ｊ）、　　
ｘ（ＣＪ）；ｓｕｂ　ｔｅｍｐ（ｉ）　　＜−ｔｅｍｐ
（ｉ）、　　ＦＴＭＰ；ｊ　　＜−ｊ＋１；　　ｂｒａ
ｎｃｈ　　−＞　　４；６　　　　　　　　　ｄｉｖ　
　ｘ（ｉ）　　＜−、ｔｅｍｐ（ｉ）、　　ｄｉａｇ（
ｉ）；ｉ　　１５　　〈＝　ｉ＋１；　　ｂｒａｎｃｈ
　　−＞　　２；７　　　　　　　ｅｎｄ。

コンマ及びセミコロン区切り文字はプログラム命令間の
境界を示す。コンマの両側の命令はノード番号及び宛先
アドレスを共有する。したがって、サイクルはセミコロ
ンで終わる。サイクル２ないし６は上述のプログラムの
外側ループを含み、サイクル４及び５は内側ループを含
む。どのサイクルでも、アドレス・メモリ・モジュール
でただ１回の書込みオペレーションが実行されるだけで
ある。また、コード内のすべての条件付き分岐は、定数
メモリ３０２及びアドレス・メモリ３０３．３０４．３
０５で得られる情報を使って、ディスパッチ装置２０４
−２０６で解決することができる。したがって、内側ル
ープ及び外側ループはどちらも、実行が追い着くのを待
たずにタスク指定されることが可能である。したがって
、すべてのデータ依存関係を自動的に守り、外側ループ
を何回も反復して順序外れで完了することができる。

他のアーキテクチャでは、Ｘに関する間接アドレツシン
グのため、外側ループは強制的に順番に完了せざるを得
ない。

上述ノブログラム・セットで使用した例示的な１組の方
程式では、マトリックスＡは１００Ｘ１００の大きさを
有し、外側ループを１回反復するごとに内側ループは平
均１０回実行される。この例では、ガラス・ザイデル手
順をｔ回反復するごとに３１００機械サイクルで１１１
００個のプログラム命令がディスパッチされる。プログ
ラムを実行するプロセッサが６個のディスパッチ装置し
かもてないように制限されている場合は、同じ数の命令
が４１００機械サイクルでタスク指定されることになる
。以上、順次プログラムの処理で高水準の並列性を実現
するコンピュータ・アーキテクチャについて説明した。

Ｅ、効果 本発明によれば、順次プログラムを高度の並列性をもっ
て実行することが可能になる。

【図面の簡単な説明】

第１図は、本発明の一実施例を組み込んだ例示的コンピ
ュータ・システムのブロック・ダイヤグラムである。 第２図は、第工図に示すコンピュータ・システムでの使
用に適したディスパッチ装置のブロック・ダイヤグラム
である。 第３図は、第１図に示すコンピュータ・システムでの使
用に適した実行装置のブロック・ダイヤグラムである。 第４図、第５図及び第６図は、第３図に示す実行装置の
オペレージ３ンを説明する流れ図である。 ２０１・・・・命令メモリ、２０４−２０６・・・・デ
ィスパッチ装置、２０７・・・・クロスバ−・ネットワ
ーク、２０８−２１０・・・・実行装置、２１２・・・
・通信ネットワーク、３０２・・・・定数メモリ、３０
３−３０５・・・・アドレス・メモリ、４１１・・・・
演算論理機構（ＡＬＵ）　、４１２・・・・データ・メ
モリ、４１６・・・・データ・メモリ制御装置。 ′＄１図 某４図 第５図 第６函

Claims (10)

【特許請求の範囲】
1. （１）第１及び第２の種類の混合したプログラム命令の
   シーケンスを並行して処理するためのコンピュータ・シ
   ステムであって、 上記プログラム命令シーケンスを保持し、上記シーケン
   スからの連続した命令をＮ個（Ｎは整数）の命令からな
   るグループに分けて供給するための命令記憶手段と、 それぞれ上記命令記憶手段から供給されるＮ個の命令の
   うち異なるものを受け取るように接続され、それぞれが
   上記第１の種類の命令を直接実行し、且つ上記第２の種
   類の各命令を表す複数の原始オペレーションを発生する
   、Ｎ個の命令ディスパッチ手段と、 上記ディスパッチ手段に接続され、それらから供給され
   る原始オペレーションを並行して実行する、Ｍ個（Ｍは
   整数）の命令オペレーション手段と を含むコンピュータ・システム。
2. （２）上記第１の種類の命令が第１の種類のデータに作
   用し、第２の種類の命令が第２の種類のデータに作用し
   、 さらに、上記第１の種類のデータを保持するための第１
   の記憶手段と、 上記第２の種類のデータを保持するための第２の記憶手
   段を備えた、 請求項１に記載のコンピュータ・システム。
3. （３）上記第１の種類のデータが主として整数データで
   あり、上記第２の種類のデータが主として浮動小数点デ
   ータである、 請求項２に記載のコンピュータ・システム。
4. （４）上記第１の記憶手段が、Ｎ個の命令ディスパッチ
   手段の間にそれぞれ分配された上記第１の種類のデータ
   の同一のＮ個のコピーを含み、上記第２の記憶手段が、
   上記Ｍ個のオペレーション実行手段の間で区分される、 請求項２に記載のコンピュータ・システム。
5. （５）上記原始オペレーションが、 Ｍ個のオペレーション実行手段のうちの第１のものを、
   該第１のオペレーション実行手段に関連する上記第２の
   記憶手段の区画からのデータ値を上記Ｍ個のオペレーシ
   ョン実行手段のうち第２のものに供給するように条件付
   ける、第１の種類の原始オペレーションと、 上記第２のオペレーション実行手段に関連する上記第２
   の記憶手段の区画内の所定の記憶セルだけにアクセスを
   限定するように、上記第２のオペレーション実行手段を
   条件付ける、第２の種類の原始オペレーションと、 上記第１のオペレーション実行手段から供給されるデー
   タ値に対して算術オペレーションを実行し、上記算術オ
   ペレーションの結果を上記所定の記憶セルに記憶するよ
   うに、上記第２のオペレーション実行手段を条件付ける
   、第３の種類の原始オペレーションとを含む、 請求項４に記載のコンピュータ・システム。
6. （６）データ操作命令と混合された制御フロー命令を有
   するプログラム命令のシーケンスを並行して処理するた
   めのコンピュータ・システムであって、上記プログラム
   命令シーケンスを保持し、上記シーケンスからの連続し
   た命令をＮ個（Ｎは整数）の命令からなるグループに分
   けて供給するための命令記憶手段と、 それぞれ上記命令記憶手段から供給されるＮ個の命令の
   うち異なるものを受け取るように接続され、それぞれが
   上記制御フロー命令を直接実行し、且つ上記データ操作
   命令を処理してそれから原始オペレーションを発生する
   、Ｎ個の制御フロー処理手段と、 上記制御フロー処理手段に接続され、それらから供給さ
   れる原始オペレーションを並行して実行する、Ｍ個（Ｍ
   は整数）のデータ・フロー処理手段と を含むコンピュータ・システム。
7. （７）さらに、上記制御フロー命令によって操作される
   データを保持するための第１の記憶手段と、上記データ
   操作命令によって操作されるデータを保持するための第
   ２の記憶手段を備えた、請求項６に記載のコンピュータ
   ・システム。
8. （８）上記第１の記憶手段が、上記制御フロー命令によ
   って操作されるデータの同一のＮ個のコピーを保持する
   ための、それぞれ上記Ｎ個の制御フロー処理手段の間に
   分配された同一のＮ個の記憶手段を含み、 上記第２の記憶手段が、上記Ｍ個のデータ・フロー処理
   手段の間に分配され、それぞれが、上記データ操作命令
   によって操作されるデータのそれぞれ異なる部分を保持
   する、Ｍ個の別々の記憶手段を含む、 請求項７に記載のコンピュータ・システム。
9. （９）第１のデータ・セットを操作してプログラムの制
   御フローを決定する制御フロー命令と、第２のデータ・
   セットを操作してプログラムについての出力データ値を
   発生するデータ操作命令とが混在するシーケンスを保持
   するための命令メモリを備えたコンピュータ・システム
   において、 第１のデータ・セットを第１の記憶要素に記憶するステ
   ップと、 第２のデータ・セットを第２の記憶要素に記憶するステ
   ップと、 上記第１の記憶要素にアクセスして上記制御フロー命令
   を実行し、且つ上記データ操作命令をデータ・フロー・
   オペレーションに変換する、第１の処理要素で制御フロ
   ー命令とデータ操作命令が混在した上記シーケンスを処
   理するステップと、上記データ・フロー・オペレーショ
   ンを第２の処理要素で実行して上記出力データ値を発生
   するステップと を含む、命令シーケンスを処理する方法。
10. （１０）データ値をメモリ位置に条件付きで割り当てる
    ための方法であって、 第１の命令セットを復号し実行して上記データ値を発生
    するステップと、 上記第１の命令セットとは無関係に第２の命令セットを
    復号し実行して、上記第１及び第２の命令セットの復号
    及び実行を中断することなく論理的結果を発生するステ
    ップと、 所定の値を有する上記論理的結果に応答して、上記デー
    タ値を上記メモリ位置に記憶するステップとを含む方法
    。