JPS6155707B2 - - Google Patents

Info

Publication number
JPS6155707B2
JPS6155707B2 JP56009752A JP975281A JPS6155707B2 JP S6155707 B2 JPS6155707 B2 JP S6155707B2 JP 56009752 A JP56009752 A JP 56009752A JP 975281 A JP975281 A JP 975281A JP S6155707 B2 JPS6155707 B2 JP S6155707B2
Authority
JP
Japan
Prior art keywords
instruction
register
priority
active
branch
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired
Application number
JP56009752A
Other languages
English (en)
Other versions
JPS56127266A (en
Inventor
Amando Roorii Reimondo
Reimondo Sutorongu Junia Habii
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPS56127266A publication Critical patent/JPS56127266A/ja
Publication of JPS6155707B2 publication Critical patent/JPS6155707B2/ja
Granted legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3885—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/76—Architectures of general purpose stored program computers
    • G06F15/80—Architectures of general purpose stored program computers comprising an array of processing units with common control, e.g. single instruction multiple data processors
    • G06F15/8007—Architectures of general purpose stored program computers comprising an array of processing units with common control, e.g. single instruction multiple data processors single instruction multiple data [SIMD] multiprocessors
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/3005—Arrangements for executing specific machine instructions to perform operations for flow control
    • G06F9/30058—Conditional branch instructions
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G06F9/3842—Speculative instruction execution
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3885—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units
    • G06F9/3887—Concurrent instruction execution, e.g. pipeline or look ahead using a plurality of independent parallel functional units controlled by a single instruction for multiple data lanes [SIMD]

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • Computing Systems (AREA)
  • Advance Control (AREA)
  • Multi Processors (AREA)
  • Complex Calculations (AREA)
  • Devices For Executing Special Programs (AREA)

Description

【発明の詳細な説明】 本発明は直線的に配列された諸プログラム・シ
ーケンスを実行する単一命令−多重データ・スト
リーム（SIMD）式計算機を制御するための方法
に係り、更に詳細に説明すればこのような計算機
における条件付きブランチ命令の実行を容易にす
ることに係る。
SIMD式並列計算機は、プログラム可能な制御
ユニツト、ベクトル情報を記憶する複数のレジス
タ、諸マスタ・レジスタ、制御ユニツトの１以上
の命令のシーケンスに応答して前記レジスタ中の
データを同時に操作するための手段を含む。米国
特許第3537074号に記載されたSIMD式並列計算
機は、ｎ個の並列プリセツサのアレイを駆動する
プログラム可能な制御ユニツトを含み、また該プ
ロセツサの各々はメモリ、算術ユニツト、プログ
ラム復号器及びＩ／Ｏ装置を備えている。
このような計算機で遂行することができるデー
タ処理の例は、刊行物であるIBM Technical
Disclosure Bulletin、Vol.22、No.6、pp.2489〜
2492、November 1979に記載されている。これ
らの例はテーブルに基く並列的な変換操作や、諸
マスクによつて決定された要素についての選択さ
れたベクトル操作を含んでいる。天気予報のよう
な他の適用業務は、このような計算機で利用可能
なマトリクス向きの処理に適している。
SIMD式計算機では、直線的に配列された各プ
ログラム・シーケンスは基本ブロツクと呼ばれ
る。各基本ブロツクは、その終了点を除くと、ブ
ランチ命令や目標命令によつて中断されないよう
な連続的な１組の命令から成る。これらの基本ブ
ロツクの制御の流れは、有向性の２進フローグラ
フ（flow graph）として表現することができ
る。アレイ型データの処理は強力なマトリクス演
算能力を活用して効率的に行うことができるが、
条件付きブランチ命令の処理はそうではない。デ
ータが並列的に処理されるのに対し、制御は直列
化する必要があり、そのため何らかの遅延が介在
することになるからである。
現在のSIMD式計算機では、基本ブロツクの実
行のスケジユーリングや活動的及び非活動的な並
列プロセツサを制御するマスクの管理を除いて、
条件付きブランチはサポートされていない。この
点については、刊行物であるStone et al：
“Introduction to Computer Architecture”、
SRA Research Associates、Inc.、1975の第333
頁〜第338頁を参照されたい。この著者は、
SIMD式計算機における条件付きブランチをマス
クすることを検討している。著者の主張を要約す
れば、外部のCPUによつて高水準命令のシーケ
ンスを処理するということである。このCPU
は、実行のために断片的な情報を制御ユニツト及
びアレイ・プロセツサへ選択的に送る。
諸プロセツサのアレイをＩ／Ｏチヤネルを介し
て結合する前置プロセツサの例は、IBM 3838ア
レイ・プロセツサへ接続されたIBMシステム／
370に見られる。これは、刊行物である“IBM
3838Array Processor Functional
Characteristics”、Form No.GA24−3639−１、
February 1977に記載されている。ここで注意す
べきは、IBM 3838アレイ：プロセツサは21種類
の論理及び指標付け命令を有しているが、条件付
きブランチ又はジヤンプ命令を有していない、と
いう点である。
発明の要約 本発明の目的は、SIMD式計算機における基本
ブロツクの処理に関連して、条件付きブランチ操
作をスケジユール及び実行するための方法を提供
することにある。本発明の他の目的は、計算機の
状況や条件を記録するためのアドレス可能なメモ
リを含み、そして命令ストリーム中の少くとも幾
つかの基本ブロツクが優先順位付けられているよ
うなSIMD式計算機で、諸基本ブロツクを実行す
ることである。このような計算機は、アレイ・プ
ロセツサの各々の実行状況を記録及び制御するた
めの活動マスクを含む必要がある。
本発明の装置は、１組の命令ポインタ・レジス
タ、１組の優先順位レジスタ、活動プロセツサを
指示する１組の活動ビツト・レジスタ、１組の条
件ビツト・レジスタを含む。
本発明は２つの方法ステツプを含む。第１のス
テツプはコンパイル時に行われるような命令スト
リームの前処理であつて、これは予定された基本
ブロツクの開始部にELSE Ｘ、JOIN Ｘ及び
DATUM Ｘの組からの命令を選択的に挿入する
ことを含む（但し、引数Ｘは基本ブロツクの優先
順位を表わす）。この結果、諸基本ブロツクの実
行に際し優先順位付けが強制される。第２のステ
ツプが呼出されるのは、現に実行されている基本
ブロツクの順位よりも低い順位の基本ブロツク
を、非活動プロセツサが指定する場合である。こ
の第２のステツプは活動マスクを変更し、これに
より低い順位の基本ブロツクへ制御を移す。
JOIN命令が実行されると、現ブロツクの実行
を待機しているすべてのプロセツサが活勢化され
る。一方、ELSE命令が実行されると、現ブロツ
クの優先順位が１組の優先順位レジスタのうちで
最小ベクトルとなるように変更される。一層具体
的に説明すると、JOIN命令は、活動的なプロセ
ツサの優先順位を更新し、活動的な命令ポインタ
を更新するとともに、優先順位Ｘを有するような
すべてのプロセツサをオンに転ずる。ELSE命令
もまた、活動的なプロセツサの優先順位及び活動
的な命令ポインタを更新するけれども、この命令
は最小の優先順位を有するプロセツサだけをオン
に転ずるという点がJOIN命令と異なる。
DATUM命令は、マスク・ブランチ型の命令（即
ち、JOIN及びELSE命令）以外の命令を参照す
る。
優先順位付けは、諸基本ブロツクが直線的に配
列されるように、各基本ブロツクへ一意的な数値
を割当てることを含む。またこの順位付けは、所
与のベクトル・プロセツサが実行すべき次の基本
ブロツクの選択権を有するとき、該プロセツサに
よつて常に一層低い順位の基本ブロツクが選択さ
れるようなものである。この順位付けの手続は、
条件付きブランチ節（node）の各々ごとに出力
枝（edge）の左／右順位付けを選択することを
含む。これは「左」をブランチ不成功と対応付
け、そして「右」をブランチ成功と対応付けるこ
とによつて行われる。
この前処理ステツプは、諸ブロツクがフローグ
ラフ（有向性グラフ）で表現されることを想定し
ている。この前処理ステツプは次のサブ・ステツ
プ、即ち(1)左ブランチの各目標の開始部にJOIN
命令を挿入するサブ・ステツプ、(2)任意の右ブラ
ンチの目標であつて、対応する左ブランチの目標
よりも高い順位を有するような目標の開始部に
ELSE命令を挿入するサブ・ステツプ、(3)その各
枝が次の２つの条件を満足するような目標節の開
始部にELSE命令を挿入するサブ・ステツプを含
む。但し、最後のサブ・ステツプの２つの条件と
は、(a)連続ブロツク（ｉ、Ｊ）によつて規定され
るインターバルがJOIN又はELSE命令を含むこ
と、(b)このインターバルが左ブランチでないか又
はこのインターバルが不完全若しくは保護されて
いないこと、である。
実施態様の説明 第１図は、米国特許第4101960号に記載された
ものを変形したSIMD式計算機の主要な構成要素
を示す。前置プロセツサ（FEP）２５は、経路
４５及び３５を介して、並列タスク・プロセツサ
（PTP）４１とプログラム及びデータ要素を授受
する。ｎ個の並列プロセツサのアレイ８１によつ
て実行可能な命令及びデータは、並列タスク・プ
ロセツサ４１の制御下で、複数の線３７及び特定
されていない他の線を介してアレイ８１へ供給さ
れる。本発明はSIMD計算機自体の方式に係るも
のではなく、SIMD式計算機における条件付きブ
ランチ命令の実行を制御するための方法に係るの
で、米国特許第4101960号に記載されたSIMD式
計算機の説明をそのまま借用することにする。従
つて、以下の説明は、このSIMD式計算機と組合
わされたとき、本発明の方法を実施するための装
置を構成するような複数の制御レジスタに向けら
れる。
米国特許第4101960号に記載されたSIMD式計
算機は、ｎ個の並列プロセツサのアレイ８１を含
む。各プロセツサは、第１図に図示されたメモ
リ・ユニツト（MU）、メモリ・インタフエー
ス、第１図に図示された命令及びデータを転送す
るバス３７、算術要素及び１対のマルチプレクサ
を有する。これらのマルチプレクサのうち、一方
はバス３７上のデータを直並列変換して算術要素
へ与え、他方は算術要素からのデータを並直列変
換してバス３７を介して並列タスク・プロセツサ
４１へ与える。
本発明は、諸基本ブロツクの実行をスケジユー
ル及び管理することを含む。こうするため、制御
ユニツトにより前処理ステツプとして選択された
基本ブロツクの開始部にELSE／JOIN命令を挿
入することが行われる。実行に際し、これらの挿
入命令は優先順位付けを強制する。このアレイに
対し、比較回路とともに諸状況レジスタが付加さ
れる。これらの状況レジスタは、アレイ８１にお
けるｎ個のプロセツサの各々ごとに、活動ビツ
ト、優先順位、条件付きビツト及び命令ポインタ
を含む。この点について、「活動マスク」とはｎ
個の活動ビツトの集合であることに注意された
い。制御ユニツトは、個別的な任意のビツトをセ
ツトすることによつて、関連するアレイ・プロセ
ツサをオン／オフ、即ち活動／非活動状態に転ず
ることができる。
第２図及び第１１図を参照すると、そこにはフ
ローグラフ関係にある複数の基本ブロツク及び各
ブロツクの開始部における可能な挿入点が示され
ている。図示された方法は、JOIN及びELSE命
令のみを挿入する。代替的に、ブロツクＢの箇所
に現われる命令「JOIN ４」を命令「DATUM
４」で置き換えてもよい。というのは、この特定
のJOIN命令は実行されないので、このブロツク
の順位「４」だけが必要となるにすぎないからで
ある。第３図は、第２図のサンプル・プログラム
に対する可能な１つの実行シーケンスを示す。こ
こでは優先順位が強制されていることに注意され
たい。
本発明の方法は、(1)所与の優先順位付けを強制
するためにELSE及びJOIN命令を使用するこ
と、(2)条件付きブランチ命令によつて生ぜられた
プログラムの多重経路を実行する際に任意の優先
順位付けを使用すること、を含んでいる。第１１
図に図示されたフローグラフは可能な多数の挿入
点を有するので、問題となるのは、指定された順
位を強制するためにELSE及びJOIN命令の小さ
いけれども十分な１組の挿入点をどのようにして
識別するかということである。
もし基本ブロツクＡ及びＢが節であれば、Ａか
らＢへの枝を表わすために記号〔Ａ、Ｂ〕を使用
することにする。インターバル（Ａ、Ｂ）は、Ａ
の順位よりも高く且つＢの順位よりも低い順位を
有する１組の節として定義される。もしＡの順位
がＢの順位よりも低ければ、枝〔Ａ、Ｂ〕は増大
方向にある。一方、もし基本ブロツクＡの順位が
Ｂの順位よりも高ければ、枝〔Ａ、Ｂ〕は減少方
向にある。Ｂは枝〔Ａ、Ｂ〕の目標と呼ばれる。
或るインターバルが完全であるのは、減少方向に
あるどの枝も当該インターバルを出て行かない
か、又は当該インターバルを出て行くような減少
方向にあるすべての枝が最大の順位を有する節か
ら出て行き且つこの節から当該インンターバルヘ
ブランチ復帰することがないような場合である。
同様に、条件付きブランチの不成功又は成功に対
応する枝は、左又は右ブランチにそれぞれ対応す
る。インターバル（Ａ、Ｂ）が保護されていると
いわれるのは、或る枝がＡからだけこのインター
バルに入ることができる場合である。
第２図及び第１１図に示された選択的挿入を含
む前処理ステツプは、以下の基準によつて管理さ
れる。
(1) 左ブランチの各目標の開始部にJOIN命令を
挿入する。
(2) 任意の右ブランチの目標であつて、対応する
左ブランチの目標よりも高い順位を有するよう
な目標の開始部にELSE命令を挿入する。
(3) 次の２つの条件を満足する各枝〔Ａ、Ｂ〕の
目標節の開始部にJOIN命令を挿入するか又は
この命令をELSE命令で置き換える。
(a) インターバル（Ａ、Ｂ）がJOIN又は
ELSE命令を含む場合、及び (b) 枝〔Ａ、Ｂ〕が左ブランチでないか、又は
インターバル（Ａ、Ｂ）が不完全であるか若
しくは保護されていない場合 (4) 変更がなくなるまでステツプ(3)を反復する。
ここで、第２図を考慮しつつ第３図を参照する
と、第１１図においてフローグラフとして表現さ
れたプログラムは図示の如く規定された優先順位
を有するものと仮定される。但し、各基本ブロツ
クのラベルＡ，Ｂ、等は、その記号アドレスでも
あるものとする。代表的な優先順位は、次のよう
に表わすことができる。
アドレス 順位 Ａ １ Ｂ ４ Ｃ ２ Ｄ ５ Ｅ ３ Ｆ ６ インターバル（１、４）は完全であり、しかも
保護されていることに注意されたい。インターバ
ル（２、５）は不完全で保護されていないのに対
し、インターバル（３、６）は完全で保護されて
いない。かくて、JOIN ４がｂに挿入され、
ELSE ５がｄに挿入され、そしてELSE ６がｆ
に挿入される。このことは第２図に示されてい
る。
ここで３つのプロセツサが存在し、そして以下
のように取られる３つの経路が存在するものとす
る。
経路１：ａ、ｂ、ｄ、ｆ 経路２：ａ、ｃ、ｄ、ｆ 経路３：ａ、ｃ、ｅ、ｃ、ｄ、ｆ 諸レジスタの状態は第３図に示す通りである。
各基本ブロツクの実行中、諸条件ビツトは対応
するアレイ・プロセツサの諸レジスタへセツトさ
れうる。条件付き（又は無条件）ブランチ命令
は、各ブロツクの終りでのみ生じうる。諸条件ビ
ツトはプログラム及びデータの相互作用が生ぜら
れ、そしてデータによつて決定された制御経路の
選択を表わす。
条件付きブランチ命令の実行中、次の３つのケ
ースが区別される。
(1) オール０；すべての条件ビツトが０。
(2) オール１；すべての条件ビツトが１。
(3) 混在；或る条件ビツトが０で、他の条件ビツ
トが１。
これらの条件を識別し且つ第５図に図示された
命令実行サイクルの(1)ステツプ11、(2)ステツプ12
又は(3)ステツプ４を活性化するための回路は、図
示されていない。オール０のケースは、あたかも
ブランチが存在しないかのように（ステツプ11
で）実行される。オール１のケースは、あたかも
無条件ブランチが存在するかのように（ステツプ
12で）実行される。混在したケースでは、諸プロ
セツサは対応する条件ビツトの値に応じて取扱わ
れる。以下では、第５図を参照して命令実行サイ
クルの詳細を説明する。
まず、米国特許第4101960号に記載されている
ような変形されていないSIMD式計算機で実行す
ることができる条件付きブランチ命令、JOIN、
ELSE、DATUM命令及び無条件ブランチ命令を
含む命令の実行を説明する。説明を簡単にするた
め、２ウエイのブランチが記述される。これを２
ウエイより多いブランチに拡大することは、本発
明の教示する処に従つて当業者が容易になしうる
筈である。
もし或るプロセツサのための条件ビツトが０で
あれば、その関連する活動ビツトはオフに転ぜら
れる。これと同時に、条件＝０に対する目標ブロ
ツクの第１命令（ELSE／JOIN／DATUM）の引
数が第４図の優先順位レジスタ（PO）１５３へ
ロードされる。この引数は、その時点で非活動プ
ロセツサが待機している次のブロツクの優先順位
を表わす。これと同時に、今読出されたばかりの
ELSE、JOIN又はDATUM命令の後の命令をアド
レスするように第４図の命令ポインタ・レジスタ
（IP）１５９がセツトされる。
もし所与のプロセツサに対する条件ビツトが１
であれば、それに関連する活動ビツトがオンに転
ぜられる。それと同時に、最初のELSE／JOIN
命令の引数は即時的な意味を持たなくなる。当該
プロセツサは今や活動状態にあるからである。優
先順位レジスタ１５３の内容は、非活動プロセツ
サの優先順位を指定するために使用される。命令
ポインタ・レジスタ１５９は、目標ブロツクの第
１命令の位置へセツトされる。
ELSE命令の実行中、比較回路は、所与の非活
動プロセツサ（活動ビツト＝０）の優先順位レジ
スタ１５３が、現に活動的なプロセツサ（活動ビ
ツト＝１）の優先順位レジスタ１５３に保持され
た順位よりも低い順位のブロツクを指定するか否
かを指示する。この場合、どのプロセツサの優先
順位レジスタ１５３が最小の順位を保持するかを
識別するとともに、それに関連する非活動プロセ
ツサを「オン」にマスクし、以前に活動的であつ
た諸プロセツサを「オフ」にマスクすることが必
要である。
ここで第４図を参照するに、そこには複数のレ
ジスタに対する制御及びデータ経路が示されてお
り、また本発明の方法を実現するために並列タス
ク・プロセツサ４１及びアレイ８１へ追加される
諸制御が示されている。図示の如く、引数レジス
タ（ARG）１５１はｎ個の優先順位レジスタ
（PO）１５３と並列タスク・プロセツサ４１を相
互接続する。また、優先順位レジスタ１５３はそ
れに対応するｎ個の活動ビツト・レジスタ
（AB）１５５へ接続され、後者のレジスタはｎ個
の条件ビツト・レジスタ（CB）１５７へ接続さ
れる。前記の引数レジスタ１５１、優先順位レジ
スタ１５３、活動ビツト・レジスタ１５５及び条
件ビツト・レジスタ１５７の複合体は、アレイ８
１におけるｎ個の並列プロセツサの処理条件を規
定する。命令ポインタ・レジスタ１５９は、アド
レス・バス１６１を介して、命令処理ユニツト
（IPU）６７並びに１組の目標レジスタ１６３，
１６５及び１６７へ結合される。
目標レジスタ１６３，１６５及び１６７は、１
以上の命令ポインタ・レジスタ１５９の内容を変
更する。この点について第５図を参照するに、そ
のステツプ３及び11では、０目標レジスタ
（0TGT）１６３の内容がアドレス・バス１６１
を介して活動的なすべての命令ポインタ・レジス
タ１５９へコピーされる。ステツプ１２では、１
目標レジスタ（１ TGT）１６５の内容もコピ
ーされる。ステツプ１３では、最も低い番号を有
する命令ポインタ・レジスタ１５９の内容が、第
１図のタスク・メモリ（TM）２７から取出すべ
き次の命令のアドレスとして、アドレス・バス１
６１を介して命令処理ユニツト６７へ送られる。
米国特許第4101960号に記載されたSIMD式計
算機を変形するに際しては、命令処理ユニツト６
７及びローカル・メモリ（LM）６９に関連する
特定のレジスタがタスク・メモリ２７から命令を
取出した後に予定の値を保持するように、スカラ
処理ユニツト（SPU）２９を変更しなければなら
ない。従つて、０目標レジスタ１６３は、現に実
行されている命令の直後に記憶された命令のタス
ク・メモリ２７におけるアドレスを保持する。
１目標レジスタ１６５は、現命令が無条件ブラ
ンチ命令（又は諸条件を満足された条件付きブラ
ンチ命令）であつた場合に制御が移されるような
命令のアドレスを保持する。
引数レジスタ１５１は、現命令の第１オペラン
ドの値を保持する。引数レジスタ１５１及び１目
標レジスタ１６５は、同一のレジスタであつても
よいことに注意されたい。
ELSE命令は、活動マスクを選択的に変更する
ことによつて、或る基本ブロツクから他の基本ブ
ロツクへ制御を移すことができる。つまり、活動
ビツト・レジスタ１５５のベクトルにおける諸ビ
ツトが変更されるのである。ELSE命令が実行さ
れると、現ブロツクの順位は１組の優先順位レジ
スタ１５３の中で最も低くなるように変更され
る。
命令実行サイクルの例 第３図のうち第５の矩形部分を参照するに、そ
こにはELSE ５命令を実行する直前の変形され
た計算機の状態が示されている。説明の便宜上、
この計算機は３つのプロセツサだけを備えている
ものと仮定する。以下では、第５図の対応する各
ステツプに沿つてELSE ５命令の実行サイクル
を説明する。
第５図のステツプ１において、ELSE ５命令
がタスク・メモリ２７のアドレスｄから取出され
る。代替的に、この命令は事前に取出されていて
もよく、又は命令処理ユニツト６７のバツフアに
置かれていてもよい。０目標レジスタ１６３はア
ドレスｄを受取り、１目標レジスタ１６５及び引
数レジスタ１５１は値５を受取る。図示されてい
ない復号論理は、(1)当該命令がELSE命令の形式
を有すること、(2)多義的な一致状態が存在しない
こと、を指示する。つまり、活動ビツト・レジス
タ１５５のうち１つだけが０であるということで
ある。かくて、実行サイクルの次のステツプはス
テツプ３である。この後、ステツプ10及び13に続
く。
ステツプ３では、（Ｘレジスタから活勢なＹレ
ジスタを更新するための）第６図の論理は第３の
命令ポインタ・レジスタ１５９(3)が値d′を受取る
ことを許容するが、第１及び第２の命令ポイン
タ・レジスタ１５９(1)及び１５９(2)は現在の値
b′及びd′をそれぞれ維持するようにされる。ま
た、第３の優先順位レジスタ１５３(3)が引数レジ
スタ１５１から値５を受取るのに対し、第１及び
第２の優先順位レジスタ１５３(1)及び１５３(2)は
値４及び５をそのまま維持する。
ステツプ10の開始時には、諸レジスタの状態は
次のようになつている。即ち、 第１活動ビツト・レジスタ１５５(1)＝０、第２
活動ビツト・レジスタ１５５(2)＝０、第３活動ビ
ツト・レジスタ１５５(3)＝１； 第１優先順位レジスタ１５３(1)＝４、第２優先
順位レジスタ１５３(2)＝５、第３優先順位レジス
タ１５３(3)＝５； 第１命令ポインタ・レジスタ１５９(1)＝b′、第
２命令ポインタ・レジスタ１５９(2)＝d′、第３命
令ポインタ・レジスタ１５９(3)＝d′； 第１条件ビツト・レジスタ１５７(1)＝０、第２
条件ビツト・レジスタ１５７(2)＝０、第３条件ビ
ツト・レジスタ１５７(3)＝０ ステツプ10では、第７図の線１９３及び１９１
が付勢されて、優先順位レジスタ１５３がそれら
の値を一般化された比較回路（MCOMP）１８３
へ転送する。比較回路１８３は、最低値を有する
優先順位レジスタ１５３に対応するその出力線に
１を供給する。かくて、第１活動ビツト・レジス
タ１５５(1)が１を受取るのに対し、第２及び第３
活動ビツト・レジスタ１５５(2)及び１５５(3)はそ
れぞれ０を受取る。この結果、第３図の第６の矩
形部分に示れた最終的構成が得られる。
ステツプ13では、第５図でステツプ13と表記さ
れたスイツチが１へセツトされ且つ第１活動ビツ
ト・レジスタ１５５(1)＝１となるので、第１命令
ポインタ・レジスタ１５９(1)に置かれたアドレス
がアドレス・バス１６１を介して命令処理ユニツ
ト６７へ送られる。これは、次の命令がタスク・
メモリ２７の位置b′から取出されることを指示す
る。これにより、このサイクルが完了する。
第６図乃至第８図には、第５図の命令実行ステ
ツプと関連付けられたレジスタ及び状況の変更を
実現するための装置が示されている。第６図に
は、ステツプ３、11及び12のレジスタ間転送が図
示される。ステツプ３は、２つの転送を行うため
のものである。第１の転送は引数レジスタ１５１
から優先順位レジスタ１５３へ向かうものであり
（Ｘレジスタ＝引数レジスタ１５１、Ｙレジスタ
＝優先順位レジスタ１５３）、第２の転送は０目
標レジスタ１６３から命令ポインタ・レジスタ１
５９へ向かうものである（Ｘレジスタ＝０目標レ
ジスタ１６３、Ｙレジスタ＝命令ポインタ・レジ
スタ１５９）。ステツプ11では、０目標レジスタ
１６３から命令ポインタ・レジスタ１５９へ向け
てデータが移動される（Ｘレジスタ＝０目標レジ
スタ１６３、Ｙレジスタ＝命令ポインタ・レジス
タ１５９）。一方、ステツプ１２では、１目標レ
ジスタ１６５から命令ポインタ・レジスタ１５９
へ向けてデータが移動される（Ｘレジスタ＝１目
標レジスタ１６５、Ｙレジスタ＝命令ポインタ・
レジスタ１５９）。これらのＸ及びＹレジスタ間
転送のために、この制御論理は複数のANDゲー
ト１６９，１７１，１７３を含み、アレイ・プロ
セツサが活動状態にある場合、つまりその対応す
る活動ビツト・レジスタ１５５が１を保持する場
合、ANDゲート１６９，１７１，１７３が線１
８１を介して適当なクロツク信号により付勢され
る時間にこれらのANDゲートを作動させ、かく
てスイツチ要素１７５，１７７，１７９を通して
対応するＹレジスタを付勢せしめる。
第７図には、ステツプ９及び10を実現するため
の論理が示されている。ステツプ９は、引数レジ
スタ１５１の内容に等しくされた優先順位レジス
タ１５３の内容に対応する活動ビツトを、活動ビ
ツト・レジスタ１５５に再書込みすることを必要
とする。ステツプ10は、優先順位レジスタ１５３
の最低の内容に従つて、活動ビツト・レジスタ１
５５の内容を再書込みすることを必要とする。優
先順位レジスタ１５３の最低の内容は、比較回路
１８３及び２０１(1)〜２０１（ｎ）によつて決定
される。
第８図には、並列タスク・プロセツサ４１にお
ける命令取出しのために、アドレス・バス１６１
で次のアドレスを得るための論理が示される。ア
ドレス・バス１６１は、ステツプ５、８及び13で
付勢される。
第９図及び第１０図には、１組の入力数値のう
ち最も低いものを識別するための比較回路が示さ
れる。この点については、刊行物であるJohn B.
Peatman：“Design of Digital Systems”、
McGraw−Hill、1972の第42頁及び第43頁を参照
されたい。第９図及び第１０図で注意すべきは、
図示された比較回路MCOMP（ｎ）がｎ個の優先
順位レジスタ１５３から加えられるｎ個の値を比
較してｎ個のシングル・ビツト出力を与えるとと
もに、１つの優先順位レジスタのサイズ出力を与
えるということである。第９図及び第１０図は複
数の比較回路の間の関係をも示す。
第５図のサイクル・ステツプは次のように要約
することができる。
ステツプ１：タスク・メモリ２７から命令処理ユ
ニツト６７へ命令を取出す。命令処理ユニツト
６７から、０目標、１目標及び引数を得る。
ステツプ２：標準的な機械命令を実行する。
ステツプ３：引数レジスタ１５１から活動的な優
先順位レジスタ１５３を更新する。０目標レジ
スタ１６３から活動的な命令ポインタ・レジス
タ１５９を更新する。
ステツプ４：１目標レジスタ１６５の内容を目標
保存レジスタ（STGT）１６７へコピーする。
ステツプ５：０目標レジスタ１６３からアドレス
を得る。
ステツプ６：非活動的な条件ビツト・レジスタ１
５７を０にする。活動的な活動ビツト・レジス
タ１５５が条件ビツト＝０に対応する処の以前
に活動的であつたレジスタの部分集合となるよ
うに、活動ビツト・レジスタ１５５に活動ビツ
ト及び条件ビツトを再書込みする。
ステツプ７：活動ビツトを条件ビツトに従つて再
書込みする。即ち、すべての条件ビツト・レジ
スタ１５７を対応する活動ビツト・レジスタ１
５５へコピーする。
ステツプ８：目標保存レジスタ１６７からアドレ
スを得る。
ステツプ９：活動ビツトを引数レジスタ１５１の
内容に等しくされた優先順位レジスタ１５３の
内容に従つて再書込みし、引数に見出される現
在の順位を有するような優先順位レジスタ１５
３に対応する活動ビツト・レジスタ１５５を活
勢にする。
ステツプ10：活動ビツトを最低の優先順位に従つ
て再書込みし、最低の優先順位を現に保持する
優先順位レジスタ１５３に対応する活動ビツ
ト・レジスタ１５５を活勢にする。
ステツプ11：０目標レジスタ１６３から活動的な
命令ポインタ・レジスタ１５９を更新する。
ステツプ12：１目標レジスタ１６５から活動的な
命令ポインタ・レジスタ１５９を更新する。
ステツプ13：最初の（又は活動的な任意の）命令
ポインタ・レジスタ１５９からアドレスを得
る。
以上のように、実行すべき諸基本ブロツクが最
初に優先順位付けされるようなSIMD式計算機に
おいて条件付きブランチを遂行するための方法が
説明された。この方法によれば、優先順位付けを
制御するための諸命令が予定の基本ブロツクの開
始部に挿入される。条件付きブランチ命令が生じ
且つ現に実行されている基本ブロツクの順位より
低い順位の基本ブロツクを少くとも１つの非活動
プロセツサが指定すると、ELSE／JOIN命令に
よつて活動マスクが変更され、かくてこの一層低
い順位を有する基本ブロツクへ制御が移される。
前述の本発明の実施態様は例示的なものであつ
て、これにより本発明の範囲が制限されるもので
はないことを理解すべきである。本発明の教示す
る処に従つて、当業者は本発明の原理を他の並列
プロセツサは容易に適用しうることは明らかであ
る。この点についての有用な例は下記の刊行物、
(1)K.J.Thurber：“Pararell Processor
Architectures………PartI：General Purpose
Systems、Computer Design”、pp.89〜97、
January 1979；(2)K.J.Thurber：“Parallel
Processor Architectures………Part：Special
Purpose Systems、Computer Design”、pp.103
〜114、February1979に見出される。
【図面の簡単な説明】
第１図は米国特許第4101960号に記載された
SIMD式計算機へ本発明に従つた複数のレジスタ
及び制御を追加したSIMD式計算機を示すブロツ
ク図、第２図は基本ブロツク及び第１１図のフロ
ーグラフの定義的特性に加えてELSE及びJOIN
命令を挿入するための１つの方法を示す図、第３
図は第２図のプログラムを実行する際の各ステツ
プにおけるレジスタ状態を示す図、第４図は本発
明の方法を実現するために並列タスク・プロセツ
サ及びアレイへ追加された複数のレジスタ及び制
御のデータ及び制御通路を示す図、第５図は活動
マスクの選択的変更を含む命令実行サイクルを示
す図、第６図乃至第８図は状況及びレジスタの変
更を実現するための装置を示す図、第９図及び第
１０図は優先順位付けを強制するために必要な比
較回路を示す図である。

Claims (1)

  1. 【特許請求の範囲】 １ フローグラフ関係にある複数の基本ブロツク
    から形成された命令ストリームを、複数の並列プ
    ロセツサ及び制御ユニツトを有する単一命令−多
    重データ・ストリーム式計算機で実行するに際
    し、前記命令ストリームに応答する前記制御ユニ
    ツトにより前記基本ブロツクの実行をスケジユー
    ルするとともに、前記並列プロセツサの活動マス
    クを変更して該並列プロセツサの活動又は非活動
    状態を調整するようにした単一命令−多重デー
    タ・ストリーム式計算機における命令ストリーム
    の実行制御方法であつて、 ELSE命令又はJOIN命令を予定された前記基
    本ブロツクの開始部に挿入することにより前記基
    本ブロツクの実行における優先順位付けを強制す
    るための第１段階と、 現在実行されている基本ブロツクの優先順位よ
    りも低い優先順位を有する基本ブロツクを非活動
    プロセツサが指定するとき前記活動マスクを選択
    的に変更して前記低い優先順位を有する基本ブロ
    ツクへ制御を移すための第２段階とから成る、単
    一命令−多重データ・ストリーム式計算機におけ
    る命令ストリームの実行制御方法。
JP975281A 1980-03-10 1981-01-27 Method of executing and controlling command stream Granted JPS56127266A (en)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
US12914880A 1980-03-10 1980-03-10

Publications (2)

Publication Number Publication Date
JPS56127266A JPS56127266A (en) 1981-10-05
JPS6155707B2 true JPS6155707B2 (ja) 1986-11-28

Family

ID=22438657

Family Applications (1)

Application Number Title Priority Date Filing Date
JP975281A Granted JPS56127266A (en) 1980-03-10 1981-01-27 Method of executing and controlling command stream

Country Status (3)

Country Link
EP (1) EP0035647B1 (ja)
JP (1) JPS56127266A (ja)
DE (1) DE3166883D1 (ja)

Families Citing this family (26)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4507748A (en) * 1982-08-02 1985-03-26 International Telephone And Telegraph Corporation Associative processor with variable length fast multiply capability
JPH0654505B2 (ja) * 1983-12-23 1994-07-20 株式会社日立製作所 並列型演算処理装置
GB2177526B (en) * 1985-06-24 1990-02-14 Pixar Selective operation of processing elements in a single instruction, multiple data stream (simd)computer system
CN1012297B (zh) 1985-11-13 1991-04-03 奥尔凯托N·V公司 具有内部单元控制和处理的阵列结构
US4907148A (en) * 1985-11-13 1990-03-06 Alcatel U.S.A. Corp. Cellular array processor with individual cell-level data-dependent cell control and multiport input memory
GB8610658D0 (en) * 1986-05-01 1986-06-04 British Petroleum Co Plc Flow control
GB8627490D0 (en) * 1986-11-18 1986-12-17 British Petroleum Co Plc Coordination
JPH07500437A (ja) * 1991-10-24 1995-01-12 インテル　コーポレイシヨン データ処理システム
US5361370A (en) * 1991-10-24 1994-11-01 Intel Corporation Single-instruction multiple-data processor having dual-ported local memory architecture for simultaneous data transmission on local memory ports and global port
US5949971A (en) * 1995-10-02 1999-09-07 International Business Machines Corporation Method and system for performance monitoring through identification of frequency and length of time of execution of serialization instructions in a processing system
US5751945A (en) * 1995-10-02 1998-05-12 International Business Machines Corporation Method and system for performance monitoring stalls to identify pipeline bottlenecks and stalls in a processing system
US5729726A (en) * 1995-10-02 1998-03-17 International Business Machines Corporation Method and system for performance monitoring efficiency of branch unit operation in a processing system
US5752062A (en) * 1995-10-02 1998-05-12 International Business Machines Corporation Method and system for performance monitoring through monitoring an order of processor events during execution in a processing system
US5797019A (en) * 1995-10-02 1998-08-18 International Business Machines Corporation Method and system for performance monitoring time lengths of disabled interrupts in a processing system
US5748855A (en) * 1995-10-02 1998-05-05 Iinternational Business Machines Corporation Method and system for performance monitoring of misaligned memory accesses in a processing system
US5691920A (en) * 1995-10-02 1997-11-25 International Business Machines Corporation Method and system for performance monitoring of dispatch unit efficiency in a processing system
US7506136B2 (en) 1999-04-09 2009-03-17 Clearspeed Technology Plc Parallel data processing apparatus
US7627736B2 (en) 1999-04-09 2009-12-01 Clearspeed Technology Plc Thread manager to control an array of processing elements
GB2394815B (en) * 1999-04-09 2004-08-25 Clearspeed Technology Ltd Parallel data processing systems
US7802079B2 (en) 1999-04-09 2010-09-21 Clearspeed Technology Limited Parallel data processing apparatus
US7526630B2 (en) 1999-04-09 2009-04-28 Clearspeed Technology, Plc Parallel data processing apparatus
US8171263B2 (en) 1999-04-09 2012-05-01 Rambus Inc. Data processing apparatus comprising an array controller for separating an instruction stream processing instructions and data transfer instructions
WO2006085277A2 (en) 2005-02-14 2006-08-17 Koninklijke Philips Electronics N.V. An electronic parallel processing circuit
US8312254B2 (en) * 2008-03-24 2012-11-13 Nvidia Corporation Indirect function call instructions in a synchronous parallel thread processor
US7856544B2 (en) * 2008-08-18 2010-12-21 International Business Machines Corporation Stream processing in super node clusters of processors assigned with stream computation graph kernels and coupled by stream traffic optical links
US9400650B2 (en) * 2012-09-28 2016-07-26 Intel Corporation Read and write masks update instruction for vectorization of recursive computations over interdependent data

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4149243A (en) * 1977-10-20 1979-04-10 International Business Machines Corporation Distributed control architecture with post and wait logic

Also Published As

Publication number Publication date
JPS56127266A (en) 1981-10-05
EP0035647A3 (en) 1982-04-28
EP0035647B1 (en) 1984-10-31
EP0035647A2 (en) 1981-09-16
DE3166883D1 (en) 1984-12-06

Similar Documents

Publication Publication Date Title
JPS6155707B2 (ja)
US4435758A (en) Method for conditional branch execution in SIMD vector processors
TWI758770B (zh) 靜止可重組態的資料處理器
US5710902A (en) Instruction dependency chain indentifier
US6829697B1 (en) Multiple logical interfaces to a shared coprocessor resource
US5555428A (en) Activity masking with mask context of SIMD processors
US5261113A (en) Apparatus and method for single operand register array for vector and scalar data processing operations
US5655096A (en) Method and apparatus for dynamic scheduling of instructions to ensure sequentially coherent data in a processor employing out-of-order execution
US5481746A (en) Vector shift functional unit for successively shifting operands stored in a vector register by corresponding shift counts stored in another vector register
US4562538A (en) Microprocessor having decision pointer to process restore position
US20040006683A1 (en) Register renaming for dynamic multi-threading
US6542989B2 (en) Single instruction having op code and stack control field
US5907693A (en) Autonomously cycling data processing architecture
KR100681199B1 (ko) 코어스 그레인 어레이에서의 인터럽트 처리 방법 및 장치
US5590359A (en) Method and apparatus for generating a status word in a pipelined processor
EP0496407A2 (en) Parallel pipelined instruction processing system for very long instruction word
US6405300B1 (en) Combining results of selectively executed remaining sub-instructions with that of emulated sub-instruction causing exception in VLIW processor
JP2004503872A (ja) 共同利用コンピュータシステム
EP1220092A2 (en) System and method for executing variable latency load operations in a data processor
US10990394B2 (en) Systems and methods for mixed instruction multiple data (xIMD) computing
US10073773B2 (en) Instruction paging in reconfigurable fabric
US20040128475A1 (en) Widely accessible processor register file and method for use
US6564312B1 (en) Data processor comprising an arithmetic logic unit
JP2638613B2 (ja) プログラマブル アクセラレータ及びその方法
US20030014474A1 (en) Alternate zero overhead task change circuit