JPH0719244B2 - アレイ・プロセツサ - Google Patents

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

A.産業上の利用分野 B.従来技術 C.発明が解決しようとする問題点 D.問題点を解決するための手段 Ｄ−1.データ従属並列処理 Ｄ−2.空間従属並列処理 E.実施例 Ｅ−1.全体的構成（第１図） Ｅ−2.命令アダプタ（第２図） Ｅ−3.簡易化された適応性処理要素の構成（第３図） Ｅ−4.多重次元ネットワークのための構成（第４図） Ｅ−5.データ従属及び空間従属並列処理 Ｅ−6.汎用ネットワークのエミュレーション Ｅ−7.相補的動作 Ｅ−8.適応性スーパーコンピュータ Ｅ−9.より詳細な実施例 Ｅ−91.命令フォーマット Ｅ−92.本発明のための例示的な設計構造（第５図） F.発明の効果 A.産業上の利用分野 この発明は、各々が割りあてられた命令を実行する処理
要素のアレイを通過するデータ・ストリームを処理する
イメージ・プロセッサに関し、特に、処理識別（identi
fication）及び状況と、データ・ストリームの複合機能
として新しい命令を得るために、命令アダプタを用い
て、データ・ストリーム中の空間及びデータ値に応答し
て各処理要素の命令割当てを適合的に操作するためのア
ーキテクチャに関する。

B.従来技術 次に示すものが、従来技術として代表的である。

米国特許第3287702号は、慣用的な処理要素のアレイを
コンピュータ制御するようにしたアレイ・プロセッサを
示す。

米国特許第3287703号も、同様なアレイ・プロセッサを
示す。

米国特許第3970993号は、各処理要素が、共通の制御ラ
イン上の動作を変更し得るフラグ・レジスタを有するよ
うなアレイ・プロセッサを開示する。

米国特許第4187539号は、各データ・フローがマイクロ
命令の列を与えるシフト・レジスタを含み、共通のマイ
クロプログラム制御ユニットが、頻繁に変わらない命令
情報を与えることによって命令サイズを小さく保つこと
を援助するフラグ・レジスタを有するような、複数デー
タフローでパイプライン化されたプロセッサを開示す
る。

米国特許第4287566号は、ベクトル・アドレスを計算す
るために使用されるサブアレイをもつアレイ・プロセッ
サを示す。

米国特許第4344134号は、データフローがノード・トリ
ーを通過した時にそのノード・トリー中の各プロセッサ
がレディ（ready）信号を発生するような、区分可能な
アレイ・プロセッサを開示する。

米国特許第4380046号は、各処理要素が、Ｇレジスタと
して識別されるマスク・ビット・レジスタを装備してい
るアレイ・プロセッサを開示する。その構成は、処理要
素を無効化し以て現在の命令の実行とノー・オペレーシ
ョンとの間を区別するためである。すなわち、各処理要
素は、動作／不動作（OP/NOP）フラグを備えたＧレジス
タを有している。

米国特許第4467409号は、コマンドのためのユニットを
設定する“ソフト機能構造（softfunctional structure
s）”をもつ標準化されたユニットを利用する、直列プ
ロッセッサのためのフレキシブル・アーキテクチャを開
示する。

米国特許第4558411号は、例えば入出力モードから処理
モードに変更し、あるいは異なる言語で書かれたプログ
ラムを実行するべく、マイクロプログラミングの命令サ
ブセットの階層を与えるための多重レベル・プログラム
可能ユニットを開示する。

欧州特許出願第84301600.7号は、各処理要素がフル・ア
ダー（full adder）と、Ｎ−Ｓ（南北）、Ｅ−Ｗ（東
西）及びＣ（キャリー）のための記憶装置を有し、以て
処理要素が算術及び論理機能の両方を実行し得るような
アレイ・プロセッサを開示する。

ソ連邦発明者証第83−721416/30は、同一のマイクロ命
令を異なる命令のために使用できるようにし、以てメモ
リ全体の容量を低減をはかるようにした、命令メモリ中
の第１及び第２の制御命令レジスタを開示する。

エレクトロニック・デザイン（Electronic Design）、1
984年10月31日、デービス（Davis）他の“収縮的アレイ
・チップが高速処理のペースに一致する（Systolic Arr
ay Chip Matches the Pace of High−Speed Processin
g）。”と題する論文は、代表的なアレイ・プロセッサ
を開示する。

NCR社の1984年刊の製品仕様NCR45CG72、NCR幾何的算術
パラレル・プロセッサ（Geometric Arithmetic Paralle
l Processor）pp.1−12は、代表的なアレイ・プロセッ
サの物理的特性を示す。

NCR社のマイクロエレクトロニクス部門によって刊行さ
れたIEEE Southconの、クラウド（Cloud）他の“並列プ
ロセッサのための効率向上（Higher Efficiency for Pa
rallel Processors）”、pp.1−７には、NCRの幾何的算
術並列プロセッサ（GAPP）の動作の詳細が示されてい
る。

以上示したように、従来技術は、さまざまの方法で外部
的に制御可能な個別の処理要素をもち、その個別の処理
要素におけるフラグに従ってOP/NOPの可能性を有するさ
まざまアレイ・プロセッサを示すが、従来技術は、適応
的処理要素の内の得られた命令を通じて、アレイ・プロ
セッサを動的に最適化するために、個々の適応的処理要
素中で命令の適応を利用することを教示しない。

ところで、現在のコンピュータ・システムは、命令スト
リームとデータ・ストリームに応じて次の４つのクラス
に分類される。すなわち、 SISD（単一命令ストリーム単一データ・ストリーム） SIMD（単一命令ストリーム多重データ・ストリーム） MISD（多重命令ストリーム単一データ・ストリーム） MIMD（多重命令ストリーム多重データ・ストリーム） SISDを除くと、これらのアーキテクチャは、並列処理シ
ステムである。しかし、これらのうちどれも処理要素の
空間的条件（空間的適応、例えばデータが、イメージの
境界にあるか、または処理要素がアレイの第１列にある
場合など）に適応する並列動作を実行することはできな
い。また、それらのうちどれも、データの性質（データ
適応、例えば、データの正負、フラグの真偽など）に適
応的な並列動作を実行することはできない。

現在、スーパー・コンピュータが市販されており、例え
ばCDC社のCyberシリーズ・CRAYリサーチ社のCRAYシリー
ズ及び日本電気のAPシリーズがある。これらのマシンは
すべてMISDアーキテクチャに基づいており、ベクトルを
処理するべく命令パイプをセット・アップするために、
長いセットアップ時間を要する。すなわち、パイプ・セ
ットアップが頻繁であるかベクトルが短いと、オーバー
ヘッドが大きい。よって、そのような場合、結果的に性
能が低下する。

ループにおけるデータ従属が、これらのスーパー・コン
ピュータの性能を低下させる。これらのマシンは、デー
タ従属が解決される（例えば、状況が厳密に知られる）
までパイプのプリセットを禁止されるか、または高い確
率をもつ（例えば状況が真）１つの経路のパイプをセッ
トアップすることになる。その前者の場合実行が遅延
し、後者の場合、“推測”が正しくないならパイプのリ
セットが行なわれる（すなわち、パイプ・セットアップ
の頻度を増大する）。どちらの場合にも性能の低下につ
ながる。

空間的またはデータの適応性がないことは次のような欠
点となる。

（１） データ従属動作が順次的に処理され、それは並
列ハードウェアの浪費、すなわち性能の低下につなが
る。

（２） 空間的な意味をもつデータが例外として処理さ
れ、そのことは並列的機会を阻む。

（３） 並列コンピュータの相互接続が固定化され、そ
のことはアルゴリズムの可変性を限定する。

（４） データまたは空間的従属によってひき起こされ
る相補的動作（例えば、送信／受信対）が順次的に実行
され、そのことは実行時間が長いことを意味する。

（５） 従って、送信帯域が浪費される。

（６） 異なる空間的条件をもつ処理要素（PE）のため
にプログラムの異なるコピーを生成しなくてはならず、
そのことはソフトウェアの労力の増大につながる。

本発明は、有限個数の処理要素の各々に条件的命令変更
手段を設けることによって、処理要素レベルにおける、
空間的及びデータ従属に対する命令の適合をはかるもの
であり、従来技術はこのような本発明を教示も示唆もし
ない。

C.発明が解決しようとする問題点 この発明の目的は、空間的あるいはデータ従属に関連す
る遅延を解消することによって、イメージ処理システム
の動作を高速化するイメージ・プロセッサ・アーキテク
チャを与えることにある。

D.問題点を解決するための手段 この発明の特徴は、有限個の処理要素の各々に、命令及
びデータ・ストリーム中のビット値の複合に応答する。
アドレス可能命令導出手段をもつ命令アダプタを設ける
ことである。

この発明の長所は、各項目が処理のため個々の処理要素
に到達するときに、異なる項目の空間的またはデータの
パラメータに適応された異なる命令を個々の処理要素が
得ることができるという点において、イメージ処理シス
テムがデータ・ストリームのパラメータに自己適応的で
あるということである。

この発明の別の長所は、データ従属のために処理遅延時
間を必要としない、ということである。

本発明を手短かに理解することを容易にするためには、
データ従属並列処理及び空間従属並列処理が関与し、本
発明の手段による解決が最も望ましいような状況を記述
することが役に立つであろう。

適応的命令処理を用いると、上述の問題は次のようにし
て並列様式で処理することができる。すなわち、命令は
＋または−（加算または減算）として定義され、一方、
“状況”を“承認ビット”として使用することにより、
得られた命令は、もし“状況”が真なら＋（加算）と定
義され、もし偽なら−（減算）として定義される。する
と、データ従属を有するループは、次のように書き直さ
れる。

for（ｉ＝O;i＜300;i＋＋） for（ｊ＝O;j＜500;j＋＋） ｃ〔ｉ、ｊ〕＝ａ〔ｉ、ｊ〕＋／−ｂ〔ｉ、ｊ〕； そして、並列が効率的に適用され得る。

この例は、どのようにしてデータ従属が解決され、順次
処理されていたデータ従属ループがどのようにして並列
化され得るかを例示するものである。尚、データ従属に
関与する並列動作を活用する機会は上記の例に限定され
ず、その適用はより広汎である。

Ｄ−1.データ従属並列処理 現在の並列コンピュータは、長い走行インデックスをも
つループの処理には有効であるが、データ従属をもつル
ープは有効にはサポートしない。特に、データ独立ルー
プの１つのタイプとして次のようなものがある。

for（ｉ＝O;i＜300;i＋＋） for（ｊ＝O;j＜500;j＋＋） ｃ〔ｉ、ｊ〕＝ａ〔ｉ、ｊ〕＋ｂ〔ｉ、ｊ〕； この処理は、よく知られたSIMD、MISD及びMIMDマシンに
よってきわめて好適にサポートすることができる。

しかし、以下に示すようにデータ従属がプログラムに付
け加えられると、最早、現在する並列マシンはそれを効
率的に処理することはできない。

for（ｉ＝O;i＜300;i＋＋） for（ｊ＝O;j＜500;j＋＋） if（状況） ｃ〔ｉ、ｊ〕＝ａ〔ｉ、ｊ〕＋ｂ〔ｉ、ｊ〕； else ｃ〔ｉ、ｊ〕＝ａ〔ｉ、ｊ〕−ｂ〔ｉ、ｊ〕； Ｄ−2.空間従属並列処理 イメージ処理及びデータが空間的条件と関連づけられて
いるような他の適用分野において、データは均質的に処
理されるのではなく、空間的従属を被ることになる。例
えば、イメージの境界上にあるデータは、他の境界上に
はないデータとは異なる洋式で処理される。このこと
は、データにより反映される空間従属の１タイプであ
る。このような状況においては、並列を処理した場合、
次のような欠点がある。

（１） 並列処理の範囲が、データの同種部分のみにし
か拡張できない。その結果、異種（例えば境界）データ
は、止むを得ず順次処理するよりない。このことは、並
列システムの性能低下をもたらす。

（２） 異種データのためのプログラム（コーティン
グ）が、同種データのためのプログラムとは異なる。そ
れゆえ、コーディングのコピーが２つ以上用意されなく
てはならない。このことは、ソフトウェア労力の増大に
つながる。

もし命令が適合化され得るなら、空間従属についての処
理は、次に示すような、問題を解決することができよ
う。

for（ｉ＝O;i＜300;i＋＋） for（ｊ＝O;j＜500;j＋＋） if（空間条件） 動作1; then 動作2. 適応性命令処理を用いると、どちらの欠点も解消され
る。すなわち、異種性（例えば境界）の空間的条件はｘ
＜Ｂまたはｘ＞Ｎ−Ｂまたはｙ＜Ｂまたはｙ＞Ｎ−Ｂの
ような条件としてあらわされ、ここで（ｘ、ｙ）はＮ×
Ｎイメージの画素の座標であり、Ｂは境界の幅である。

E.実施例 Ｅ−1.全体的構成 適応性命令プロセッサは、並列コンピュータ中の各適応
的処理要素に、プロセッサ識別（PID）を割当てる。そ
のプロセッサは、適応的処理要素の算術論理ユニット
（ALU）から、データ従属状況（DDS）の組を収集し、次
に、PIP、DDS及びもとの命令によって反映される空間的
従属及びデータ従属に従う命令を得るために命令アダプ
タ（IA）を利用する。

第１図は、データ従属及び空間従属の処理が関与するこ
とを除けば、概念と動作において当分野で知られている
アレイ・プロセッサに類似するアレイ・プロセッサを示
すブロック図である。このイメージ・プロセッサは、適
応的処理要素アレイ（APEA）１及びアレイ・コントロー
ラ（AC）２を有し、その各々は概略的に示されている。
アレイ・コントローラ２は、命令ライン３上に一組の命
令を与え、また入力及び出力データのための通信経路４
を与える。処理要素アレイ１は、個別の多数の適応性処
理要素５を有し、その各々には本発明に従う適応手段が
組み込まれている。処理要素アレイ１のうちのいくつか
の処理要素は、その位置が予め知られており、それに従
って段取りがなされる限りは、慣用的なものでよいが、
しかしそのことは好ましくはない。やはりすべての処理
要素を同一の適応的処理要素とし、慣用的な性能が要望
されるときは、例えば符号６で示す処理要素を慣用的に
動作させるようにするのが好適である。

イメージ処理は、データ・フローに関する限り慣用的な
イメージ・プロセッサ様式で進められる。すなわち、デ
ータは処理要素に入り、システム・メモリへのアクセス
に介入することなく、データが通過する処理要素によっ
て変更された初期値に従って、データは処理要素から処
理要素へと流れる。個々の処理要素は、データ・フロー
の開始の前にセットアップされる。従来のイメージ・プ
ロセッサにおいては、どのような目的に際しても、実行
の間のデータの正確な位置が知られていないので、実行
の間にセットアップを変更する機会がほとんどない。従
来においては、本質的に、イメージ・プロセッサは、一
たんセットアップされると実行期間中、特殊化された一
定動作を行うコンピュータとなる。一方、本発明は、複
数の適応性処理要素の各々に、それ固有のプロセッサ識
別レジスタと、固有のデータ従属状況レジスタと、固有
の命令適応機構を設けることによって、実行中のセット
アップの動的変更を可能ならしめる。すなわち、その固
有の命令適応機構は、プロセッサ識別データと、状況デ
ータと、加えられた命令に応答して、適応性処理要素の
ために動作の内部選択を行う。システム・レベルで見る
と、このことは、空間的及びデータ従属に好都合な適合
性を与え、これにより、処理されているデータのタイプ
に対してシステムの最適化が可能となる。

第１図には、多くの適応性処理要素５のうちの代表とし
て、１個の処理要素７がより詳細に示されている。この
構成において、通信経路70と、局所メモリ71と、算術論
理ユニット（ALU）72は慣用的であり、その作用におい
て、慣用的な処理要素中の類似の部分と同様である。一
般的には、これらの部分は、割当て（命令）を受け取
り、データが与えられたときにそのデータにつき命令を
実行する機能を果たす。

ライン８として示す計算サイクルは、命令９として簡易
化して図示するように、実行用の命令を導出するために
原命令（original instruction）を使用する。動作にお
いては、原命令と、空間従属状況と、データ従属状況
が、時間ライン８上の値Ｘ、Ｙ、Ｚにより示されるよう
に、サイクルの前半で利用可能である。次に、計算Ｃの
制御のために、導出された命令が利用可能となる。

さて、適応性は命令アダプタ（IA）73によって与えられ
る。すなわち、IA73は、原命令ライン74から命令呼び出
し適応性を受け取り、与えられたデータ上で適当なテス
トを実行し、そのテスト結果から、代わりの命令を導出
することにより適応をはかるか否かを判断し、導出命令
ライン75を介してALU72に導出された代わりの命令を与
える。ALU72は、DDSテスト・データ・ライン76を介して
IA73に、新たに処理されたデータ従属状況ビットを与え
るためのデータ従属状況レジスタとして働くか、または
そのようなレジスタを含む。適応性呼び出し命令は、適
応性制御ライン74上に与えられると、空間従属状況ブロ
ック（SDS）77、従属選択検証ブロック（DSV）78及び命
令変更拡張ブロック（IME）79がその命令を利用可能と
なる。命令アダプタ（IA）ブロック73は、（特殊な環境
下で自己の変更を呼び出すようなタイプの）原命令を受
け取り、出力としてライン75を介して、導出された命令
をALUブロック72へ送る。これにより、適応性処理要素
の動作が制御される。

典型的な命令セットとしては、NCR45CG72、1984年、P.7
に示されているように、マイクロNOP命令、処理要素間
の通信のためのいくつかのLOAD/STORE命令、及び算術／
論理命令がある。第１図には、符号80で示す箇所に導出
された命令の命令フォーマットが示されている。導出さ
れた命令は、１つまたはそれ以上の規定されたビット位
置において入力命令に挿入された“承認ビット”を持っ
ている。承認ビットはPID、DDS及び入力命令の関数であ
り、規定ビット位置は、入力命令と導出命令のフォーマ
ットから予め定めることができる。承認ビットはまた、
規定位置において入力命令のビットに重ね書きすること
もできる。

個々の適応性処理要素は依然としてきわめて単純であ
る。すなわち、付加された３つのブロックはそれぞれレ
ジスタとシフト・レジスタとマルチプレクサであり、そ
れらはすべて多数のメーカーから入用可能で当業者には
よく知られた部品である。それらの部品は例えば、テキ
サス・インスツルメント社（Texas Instruments Corpor
ation）、設計技術者のためTTLデータ・ブック（THE TT
L DATA BOOK FOR DESIGN ENGINEERS）第２版、LCC411
2、74062−116−AI、pp.7−471、７−316及び７−181に
記載されている。次の表に示す例が、典型的な選択例で
ある。部品番号 構成ブロック 74374 ８ビット・レジスタ 74194 ４ビット双方向シフト・レジスタ 74157 マルチプレクサ Ｅ−2.命令アダプタ 第２図は、命令アダプタ（IA）73の構成を示し、それは
次のような機能ブロックからなる。

（１） 空間従属状況ブロック（SDS）77 （２） 従属選択検証ブロック（DSV）78 （３） 命令変更拡張ブロック（Ｂ）79 空間従属状況ブロック（SDS）77は、制御として入力命
令の一部を受け入れ、空間従属を示すために出力として
SDSビットを発生する。このブロックは、PIDレジスタ81
を含み、そのレジスタ81の内容が、その処理要素の識別
子となる。PIDレジスタには、入力命令によって予めロ
ードすることができる。PIDレジスタ81の内容は、空間
的位置（例えば、ｘ−ｙ座標）に関連づけられていなく
てはならない。SDS77はまた、PIDレジスタ81と同一サイ
ズのシフトレジスタ82を含んでいる。シフトレジスタ82
は、一度に１ビットづつ、どちらの方向にも論理シフト
動作を行うことができる。この機構により、ライン88を
介してDSVブロック78がPIDレジスタの任意のビット・グ
ループを入力として利用することが可能となる。

第２の機能ブロックは“従属選択検証（DSV）”ブロッ
ク78である。DSV78は、SDSビットまたはDDSビットのう
ちのいくつかを選択するためのマルチプレクサ83を含ん
でいる。このブロックには、照合、マスキング及び比較
のためにテンプレート・レジスタ84が含まれている。そ
して、選択された従属ビット及びテンプレートは、承認
ピットを発生するために承認検証ブロック85へ渡され
る。テンプレート・レジスタ84は、初期化の際にプリセ
ットされる決定しきい値情報を含んでいる。典型的な動
作においては、ビットのあるサブグループをマスクする
ために、すべてのテンプレート・レジスタは同一の値に
セットされる。特定のサイクル上では、関連するPIDレ
ジスタ中のビット・グループのサンプリングを実行し、
それらのビットを適当に整列させるために、命令に従っ
てすべてのシフト・レジスタは同様に動作される。

テンプレート・レジスタとシフト・レジスタはともにPI
Dから関連ビットを選択するように機能する。テンプレ
ート・レジスタの通常の動作は、ハードウェアに、異な
るイメージ・サブセット等に異なる割り当てを行うため
の２個の連続ビットを含む、可動窓としてのものであ
る。

承認検証ブロックは、比較（COMPARE）、AND、OR及びXO
R動作を行うことができる。要約すると、DSVブロック
は、入力としてSDSビット及びDDSビットを受け取り、出
力として承認ビットを発生する。DSVブロックは、入力
命令の一部を制御信号として受け取る。

DDSビットは、データの性質を示し、データ適応のため
に使用される。共通のDDSビットには、正／負、ゼロ／
非ゼロ、正／非正、真／偽、大／等／小、偶／奇があ
る。適応的処理要素７のALU72から導出され得る他の状
況は状況ビットによって識別することができる。

第３のブロックは、命令変更拡張（IME）ブロック79で
ある。IMEブロック79は、承認ビットと入力命令とを入
力として受け取り、導出された命令を出力として発生す
る。IMEブロック79は、入力命令のいくつかのビット
を、規定された位置で承認ビットによって置き換えるた
めの重ね書きブロックを有している。IMEはまた、規定
された位置において入力命令に承認ビットを挿入するた
めの、ビット挿入ブロックを有している。重ね書きまた
は挿入またはその両方の選択、及び位置を予め規定する
ことは、入力命令の一部によって制御される。

上記SDS77、DSV78及びIME79という３つの機能ブロック
を用いて、命令アダプタ（IA）は、空間的またはデータ
適応を容易化するために次のような“従属動作”を行
う。

（１） DDSの任意のビットが“1"であることを検出す
ること。

（２） PIDレジスタの、ｉ番目のビットが“1"である
ことを検出すること。

（３） テンプレートに一致するPIDレジスタの任意の
連続するＭ個のビット（Ｍは、PIDのビットの全数に等
しいかそれよりも小さい）を検出すること。

Ｅ−3.簡易化された適応性処理要素の構成 第３図には、きわめて効率的且つ簡易化された命令アダ
プタ（IA）の構成が示されている。この構成において、
PIDレジスタ81の内容が論理的シフトレジスタ（LSR）91
にコピーされ、LSR91は、双方向に論理シフト動作を行
う。LSR91からシフトに送出されたビットと右端のビッ
トがSDSビットである。次にマルチプレクサ83が、承認
ビットとしてSDSまたはDDSのどちらを選択する。そのよ
うな構成は、一次元及び二次元動作を実行することがで
きる。この構成は、より簡単な適応性処理要素に適して
いる。なぜなら、テンプレート・レジスタ84（第２図）
及び承認検証ブロック85が省略されているからである。

Ｅ−4.多次元ネットワークのための構成 第４図は、二次元中のアレイまたは三次元中のピラミッ
ドなどのような、並列コンピュータの多次元相互接続ネ
ットワークの空間従属を検出するために構成された空間
従属状況ブロックを示す図である。PIDレジスタはＫ個
のセクション１〜Ｋをもつと考えることができる。第
１、２図中のシフトレジスタ82及び91に類似する、SDS
ブロック77中のシフトレジスタ92は、Ｋ個のセクション
（ここでＫはネットワークの次元）に分割されている。
そして、各セクションが、ネットワークの１つの次元の
空間従属を扱う。各セクションの右端と左端のビット
は、空間従属検出のためにDSVブロック78中のマルチプ
レクサ83に渡されるSDSビットである。

Ｅ−5.データ従属及び空間従属並列処理 本発明の基づく適応性命令処理によれば、次のような再
構成が可能である。すなわち、 「for（ｉ＝0;i＜300;i＋＋） for（ｊ＝0;j＜500;j＋＋） if（条件） 動作1; else 動作2;（もし動作１及び２が相補的なら）」 を 「for（ｉ＝0;i＜300;i＋＋） for（ｊ＝0;j＜500;j＋＋） 動作3.」 に再構成する。

これによれば相補的動作が可能である。相補的動作の例
としては、＋／−（和または差）の対がある。“承認”
ビットが“条件”から導出され、その“条件”はデータ
従属または空間従属のどちらかであり得る。この再構成
の結果として、動作1/動作２の順次的処理を単一化され
た動作３へと完全に並列化することができる。

この問題はまた、次のようにしても再構成することがで
きる。すなわち、 “承認”ビットが“条件”から得られ、入力された命令
に適当なフィールドを重ね書きするかまたは挿入するこ
とによって“アドレス・オフセット”を生成するために
その“承認”ビットが使用される。次に、動作１と動作
２のコードが距離Ｄだけ離れて構成される。ここでＤ
は、“アドレス・オフセット”に等しい。実行時間の間
に、各処理要素は、データの空間的条件に応じてそのコ
ードの右のエントリへと“ジャンプ”する。尚、コーデ
ィングの改訂は一回だけしか必要ないことに注意された
い。この発明によれば、空間従属に起因する異種性の問
題が同種性の問題に変換され、これにより並列化の適度
を向上しソフトウェアの労力を低減することが可能であ
る。

Ｅ−6.汎用ネットワークのエミュレーション 本発明は、システム中の処理要素（PE）を接続するため
の単一の固定ベースライン・ネットワークをもつ並列コ
ンピュータ中のPEの相対的または絶対的位置（座標）に
起因する空間従属を解決する。アルゴリズムの進歩の観
点から、並列処理システム中に２つ以上のネットワーク
（または相互接続）を埋め込むことが好都合である。な
ぜなら、単一ネットワークはさまざまなアルゴリズムに
最適には適合しないからである。そのようなネットワー
ク・エミュレーション能力をもつ並列システムにおいて
は、ネットワークは、適応性命令プロセッタを利用して
ベースライン相互接続からエミュレートすることができ
る。

例えば、適応性命令プロセッサによって、Ｎ×Ｎサイズ
のベースライン・アレイ相互接続からピラミッド・ネッ
トワークをエミュレートすることができる。このとき、
アレイ中の各適応性処理要素のPIDレジスタには、適当
なデカルト座標値（ｘ、ｙ）がロードされる。すなわ
ち、時間ｔ＝１ではすべてのPEが活動状態にある。ｔ＝
２では、２の倍数に等しいｘまたはｙ座標をもつ適応性
処理要素のみが活動状態にある。ｔ＝３では、４の倍数
に等しいｘまたはｙ座標をもつ適応性処理要素のみが活
動状態にある。要素すると、ｔ＝ｉでは、２×（ｉ−
１）の倍数に等しいｘまたはｙ座標をもつ適応性処理要
素のみが活動状態にある。上述の手続は、ベースライン
・アレイ・ネットワークから縮小率２のピラミッド・ネ
ットワークをエミュレートする（すなわち、時間ステッ
プが進む毎に、全PEのうちの1/4のみが離隔するPEと接
続される）。エミュレーションの制御は、二次元PIDレ
ジスタの内容を検査し、“承認”ビットが真ならそのPE
を活動化することによって行なうことができる。それと
同一の適応性命令プロセッサはまた、ベースライン・交
互接続からトリー、リング、パーフェクト・シャッフル
（perfact shuffle）などのネットワークのエミュレー
ションにも適用することができる。

ネットワーク・エミュレーションは単一のPEタイプから
多数の並列アーキテクチャを形成するという点できわめ
て強力な機構である。経済的且つ論理的恩恵に加えて、
このアルゴリズムは並列アーキテクチャによりよく適合
し、以て性能の向上をはかることができる。このとき一
種類のタイプのPEがあればよいので、そのようなエミュ
レーション・スキームは特にVLSIに適する。

Ｅ−7.相補的動作 相補的動作は、２つの適応性処理要素の間で配分され同
時に実行できる一対の動作である。相補的動作の例とし
ては、プロセッサ間の通信のためのSEND/RECEIVE対及び
FFT（高速フーリエ交換）のためのバタフライ（Butterf
ly）演算がある。別の例としては、Ｅ−5.の適応例に記
載された＋／−命令がある。適応性命令の構成は、相補
的動作に適用されると、実行速度を向上し通信帯域を節
約することができる。

SIMDアレイ・アーキテクチャの場合に、SEND/RECEIVEの
例について考慮してみよう。１個の適応的処理要素は
（アレイにおけるそれの位置に関する情報、すなわち空
間的情報に基づき）隣接する処理要素に相互結線を介し
てデータを送り、一方、隣接するPEは（この空間的情報
に基づき）隣接する処理要素に相互結線を介してデータ
を送り、一方、隣接するPEは（この空間的情報に基づ
き）同一の相互結線を介してこれらのデータを受け取
る。その動作は、１個のデータにつき一単位の通信帯域
を利用して１サイクル中で実行することができる。位置
従属適応性をもたないSIMDアーキテクチャの場合、それ
と同一の動作には２つの実行サイクルまたは２単位の通
信帯域が必要である。

バタフライ演算の場合、従来のイメージ・プロセッサに
おける順次的実行では４サイクルが必要である。ところ
が、適応性命令プロセッサによれば、必要なサイクル
は、（２個の適応性処理要素を用いると）２サイクル、
または（４個の適応性処理要素を用いると）１サイクル
に低減することができる。このことは、先ずすべての適
応性処理要素にADD/SUB（加法／減法）命令を送ること
によって達成される。次に、各適応性処理要素は、自己
の空間的条件に応じて命令をADDまたはSUBのどちらかに
割り当てる。

相補的命令の適用は、上述の例に限定されない。実際、
イメージ処理、コンピュータ・ビジョン、ディジタル信
号処理、数学的変換及び一般的な科学的計算において他
の多くの応用例を見出すことができる。

Ｅ−8.適応性スーパーコンピュータ 適応性命令処理はデータ従属の問題を解決し、スーパー
コンピュータの性能向上をはかることができる。このと
き、OPA/OPB（動作A/動作Ｂ）と呼ばれる命令を定義す
ることができ、命令を適応化するために１つの承認ビッ
トが選択される。すなわち、承認ビットが“1"であれ
ば、導出された命令はOPAを実行し、承認ビットが“0"
であれば、導出された命令はOPBを実行する。スーパー
コンピュータ内のパイプは命令のOPA/OPBのために予め
セットアップすることができ、ベクトルの実行は、一た
ん承認ビットが利用可能になると開始できる。尚、デー
タ適応性のため、“正しく言いあてる（guessing righ
t）”確率は常に“1"である。

Ｅ−9.より詳細な実施例 この実施例は、空間的適応の場合において動作する適応
性命令プロセッサを示す。第５図を参照すると、この実
施例は、原命令が、プロセッサ識別（PID）の関数とし
て変更される様子を示している。その結果、次のような
計算が有効に実行され得ることになる。

for（ｉ＝0;i＜300;i＋＋） for（ｊ＝0;j＜500;j＋＋） if（PID＜０＞＝＝１） ｃ［ｉ、ｊ］＝ａ［ｉ、ｊ］＋ｂ［ｉ、ｊ］ else ｃ［ｉ、ｊ］＝ａ［ｉ、ｊ］−ｂ［ｉ、ｊ］ そこで先ず、簡易化された原命令と導出された命令をバ
ックグラウンドとして示し、次に本発明を実現する設計
構造を第５図を参照して説明する。

Ｅ−91.命令フォーマット 原命令のＭビットのうちで、以下に記述するようにＫ番
目のビットがSEND/RECまたは＋／−の動作を制御する。
すなわち、 もしビット＜Ｋ＞＝１なら、PEの局所状況Ｓが真のとき
PEはSENDを実行し、PEの局所状況Ｓが偽のときPEはREC
を実行する。

また、もしビット＜Ｋ＞＝０なら、PEの局所状況Ｓが真
のときPEは“＋”を実行し、PEの局所状況Ｓが偽のとき
PEは“−”を実行する。

原命令とは対照的に、導出された命令は、この実施例に
関連する。ｒ番目とｒ＋１番目の２つのビットを有す
る。適応性処理要素のこの動作は次のように表示され
る。

ｒ番目 ｒ＋１番目 動作 ０ ０ − ０ １ ＋ １ ０ REC １ １ SEND 例えば、変更された命例のｒ番目のビットが“0"であ
り、ｒ＋１番目のビットが“1"であるとき、PEは“＋”
を実行する。

Ｅ−92.本発明のための例示的な設計構造 第５図は、多数のマルチプレクサを用いた別の実施例を
示す。すなわち、原命令の一部が、そのプロセッサ識別
（PID）をもつシフトレジスタ91に１ビット位置だけ右
にシフトするように指令する。その結果、プロセッサ識
別レジスタ中の最下位ビット（LSBPID）が従属選択検証
（DSV）ブロック78への入力の一つに収まる。

第５図は、原命令のＫ番目のビット（Ｉ＜Ｋ＞）を、PI
DのLSB（LSBPID、すなわちPID＜０＞）に従って変更さ
れた命令のｒ番目及びｒ＋１番目のビット（IM＜ｒ＞及
びIM＜ｒ＋１＞）に変換するための例示的な設計構造が
示されている。

適応性制御ライン74上にある原命令の別の部分は次に、
DSVブロック78に、DSVブロック中のマルチプレクサの出
力としてLSBPIDを選択するように指令する。その結果、
LSBPIDは“承認ビット”のライン上に配置される。

命令変更拡張（IME）ブロック79の入力として、（現在L
SBPIDを有する）“承認ビット”及び原命令（Ｉ＜Ｋ＞
及び他のビットを有する）が一組のマルチプレクサ84〜
86中に導かれて、導出された命令が得られる。尚、Ｊビ
ットの導出命令を得るためにはＪ個のマルチプレクサが
必要であり、このとき１個のマルチプレクサが導出命令
の１ビットを生成する。IM＜ｒ＞を生成するために、原
命令は、マルチプレクサｒに、出力としてＩ＜Ｋ＞を選
択するように指令する。同様に、原命令はマルチプレク
サｒ＋１に、IM＜ｒ＋１＞として“承認ビット”を選択
するように指令する。

下記の表は、原命令（Ｉ＜Ｋ＞）と、LSBPIDと、変更さ
れた命令（IM＜ｒ＞及びIM＜ｒ＋１＞）間の関係を示
し、この表には、第５図の設計構造により本発明が実現
されることが例示されている。

”−” ０ ０ ０ ０ ”＋” ０ １ ０ １ REC １ ０ １ ０ SEND １ １ １ １ F.発明の効果 以上のように、この発明によれば、データ従属あるいは
空間従属のループを含む処理を並列的に実行できるの
で、処理速度を高めることができる。

また、異なる空間的条件をもつ処理要素のためにプログ
ラムの異なるコプーを作成する必要がなくなるので、ソ
フトウェアの労力が低減する。

【図面の簡単な説明】

第１図は、本発明のアレイ・プロセッサの全体的な概要
のブロック図、 第２図は、命令アダプタのブロック図、 第３図は、適応性処理要素のブロック図、 第４図は、多次元ネットワークのための命令プロセッサ
のブロック図、 第５図は、命令アダプタの他の実施例のブロック図であ
る。 １……処理要素（PE）アレイ、２……アレイ・コントロ
ーラ、73……命令アダプタ、77……空間従属状況ブロッ
ク、78……従属選択検証ブロック、79……命令変更拡張
ブロック。

Claims (1)

【特許請求の範囲】
1. 【請求項１】命令発生能力を持つ制御ユニットと、個々
   の処理要素からなるアレイとを有し、該処理要素は入力
   手段と、処理手段と、他の処理要素に接続された出力手
   段とを持ち、上記制御ユニットによって上記アレイに同
   時に加えられた命令にしたがってデータを処理するもの
   であるアレイ・プロセッサにおいて、 上記各々の処理要素は、その各処理要素が原命令を受信
   し、命令を導出し、該命令を実行するという点で適応性
   であり、 上記原命令を受信するように接続され、空間従属状況動
   作パラメータを示す第１の信号を供給する空間従属状況
   手段と、 上記導出された命令を実行し、上記出力手段に結果を供
   給し、さらにデータ従属状況動作パラメータを表す第２
   の信号を供給する、処理手段を含む実行手段と、 上記原命令を受信するように接続され、上記原命令、上
   記第１の信号及び上記第２の信号を受信するように接続
   され、上記第１の信号及び上記第２の信号に応答して合
   成された命令を導出する従属選択検証手段と、 上記原命令を受信するように接続され、かつ上記合成命
   令を受信するように接続され、上記処理手段へ上記導出
   された命令を供給する命令変更拡張手段と、 を有するアレイ・プロセッサ。