JPH0695349B2 - プログラム実行制御方式 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明はプログラム実行制御方式に関し、特に、演算
の対象になるデータが揃い次第命令の実行が可能になる
データフロー型情報処理装置において、プログラムデー
タ記憶するプログラムメモリをアクセスする際のプログ
ラム実行制御方式に関する。

［従来の技術および発明が解決しようとする課題］ 従来のコンピュータは、プログラムとして種々を命令を
プログラムメモリに記憶しておき、プログラムカウンタ
によってプログラムメモリのアドレスを遂次指定して順
次命令を読出し、その命令を実行するというノイマン型
計算機が大部分である。

一方、データフロー型計算機は、プログラムカウンタや
遂次的な命令の実行という概念は持たない非ノイマン型
計算機の一種である。このようなデータフロー型計算機
は、命令の並列処理を基本にしたアーキテクチャを採用
してており、演算の対象になるデータが揃い次第命令の
実行が可能となり、データによって複数の命令を同時に
駆動するため、データの自然な流れに従って並列的にプ
ログラムが実行される。その結果、演算の所要時間が大
幅に短縮するとみなされている。

ところで、従来のデータフロー型計算機は、プログラム
メモリを内蔵するのが一般的であり、外部にプログラム
メモリを設けるという概念は存在しなかった。

それゆえに、この発明の主たる目的は、大容量のプログ
ラムメモリを外付けして、プログラムメモリを高速でア
クセスできるようなプログラム実行制御方式を提供する
ことである。

［課題を解決するための手段］ この発明はデータフロープログラムを記憶するプログラ
ム記憶手段と、プログラム記憶手段から対となるプログ
ラムおよび被処理データが入力されたことを判別する対
データ検出手段と、対データ検出手段によって対となる
プログラムデータおよび被処理データが検出されたこと
に応じて、そのプログラムデータおよび被処理データに
基づく演算を実行する演算処理手段と、プログラム記憶
手段にプログラムデータを与える外部プログラム記憶手
段とを備えた情報処理装置において、プログラム記憶手
段をアクセスするプログラム実行制御方式であって、対
データ検出手段によってプログラム記憶手段から対とな
るプログラムデータおよび被処理データの読出されたこ
とが判別されたことに応じて、外部プログラム記憶手段
のアクセスを実行するとともに、演算処理手段に処理す
べきプログラムデータおよび被処理データを送出し、演
算処理手段の演算処理結果データに対する次の命令をプ
ログラム記憶手段に対してフェッチし、該命令フェッチ
がミスヒットした場合、外部記憶手段に対して直接次の
命令を被処理データとともにアクセスするようにしたも
のである。

［作用］ この発明に係るプログラム実行制御方式においては、実
行に必要な命令はフェッチされる直前に外部プログラム
記憶手段からプログラム記憶手段ヘアップロードされて
確実にフェッチされ、たまたまミスヒットした場合に
は、直接外部プログラム記憶手段をアクセスすることに
より、極めて良好な効率で命令のフェッチを実行するこ
とが可能となる。

［実施例］ 第１図はこの発明の一実施例の概略ブロック図である。
まず、第１図を参照して、この発明の一実施例の構成に
ついて説明する。情報処理装置１には外部プログラムメ
モリ２が外付けされている。情報処理装置１は入出力制
御回路を構成する分岐結合部3,4,5,10およびバッファ11
を含む。分岐結合部３には入力データパケットが与えら
れ、この入力データパケットは分岐結合部３によって分
岐されて分岐結合部４または５に与えられる。分岐結合
部５は分岐結合部３から出力された入力データパケット
または後述のバッファ11から与えられるデータパケット
のいずれかをキャッシュプログラムメモリ６に与える。
キャッシュプログラムメモリ６はノードＮ＃とG/C（Gen
eration/Color）とを組合わせたキーコードを複数記憶
していて、該当するキーコードが入力されると、プログ
ラム上の行先ノードＮ＃とその行先ノードＮ＃でどのよ
うな処理をするかを示すTAGが対データ検出部７に出力
される。

対データ検出部７はキャッシュプログラムメモリ６から
読出されたプログラムデータおよび被処理データに対し
て対となるプログラムデータおよび被処理データが入力
されたか否かを判別するものである。１対のプログラム
データおよび被処理データが対データ検出部７で検出さ
れかつ生成されたとき、接点８が閉じられる。なお、プ
ログラムデータがnopの場合にも、対となるべきプログ
ラムデータが不要であるため、接点８は閉じられる。ま
た、対データ検出部７の出力は外部プログラムメモリ２
にも与えられている。対データ検出部７から出力された
プログラムデータおよび被処理データは、接点８を介し
てALU9に与えられて演算され、その演算結果は分岐結合
部10によってバッファ11または分岐結合部４に分岐され
る。バッファ11に記憶された演算結果は分岐結合部５を
介してキャッシュプログラムメモリ６に与えられる。

外部プログラムメモリ２は対データ検出部７から出力さ
れたプログラムデータに含まれるＮ＃とG/Cとをキーコ
ードとして、次の命令のプログラムデータを読出してキ
ャッシュプログラムメモリ６にアンプロードする。

前述のバッファ11は外部プログラムメモリ２がプログラ
ムデータを読出してから、ALU9の演算結果をキャッシュ
プログラムメモリ６に与えるための遅延動作を行なうも
のとして設けらている。なお、外部プログラムメモリ２
は、キャッシュプログラムメモリ６からプログラムデー
タの初期書込み（ダウンロード）が可能なように構成さ
れている。

第２図は第１図に示した情報処理装置によって処理され
るプログラムの一例を示す図であり、第３図ないし第10
図は第１図に示した情報処理装置１によって、第２図に
示したプログラムを実行するときの各部のプログラムデ
ータの変化を示す図である。

次に、第１図ないし第10図を参照して、この発明の一実
施例の具体的な動作について説明する。まず、第２図の
プログラムから明らかなように、ノードＮ＃Ａに続くプ
ログラムデータは、ノードでデータ０のnop命令を実
行するとともに、ノードＤから与えられかつノードで
NOP命令が実行されたデータとノードで加算命令を実
行できるようにキャッシュプログラムメモリ６に配され
ることが望まれる。

このために、第３図に示すように、情報処理装置１に
は、入力データパケットとして、データ0,TAGソース,G/
C0,N＃Ａが与えられる。ここで、ノードＮ＃ＡおよびG/
C0の各々の一部を併せたものがキャッシュプログラムメ
モリ６の物理アドレスを示しており、TAGソースはノー
ドＮ＃Ａがプログラムデータの入力部を指定するもので
あり、G/Cはデータ０がどの時刻でサンプリングされた
データであるのかを識別するための識別子として用いら
れている。

なお、ノードＮ＃ＡとG/C0はキャッシュプログラムメモ
リ６の前記物理アドレスを与えるとともに該メモリをア
クセスするためのキーコードとして取扱われている。上
述の入力データパケットは分岐結合部3,5を介してキャ
ッシュプログラムメモリ６に与えられる。キャッシュプ
ログラムメモリ６はノードＮ＃A,G/C0をキーコードとし
て、対応するプログラムデータをアクセスする。たとえ
ば、対応するプログラムデータとしてノードＮ＃3,TAG
＋Ｌがフェッチされる。

このプログラムデータは、第２図に示すプログラムのノ
ードにおける加算の左側入力を与えることを示してい
る。このとき、ノードにおけるnop命令を処理するた
めに同じデータ０が与えられるので、Ｎ＃A,G/C0のキー
コードに対して、予めコピーフラグがキャッシュプログ
ラムメモリ６内で設定されている。そして、キャッシュ
プログラムメモリ６によってＮ＃A,G/C0のキーコードに
対して、nopの命令を示すＮ＃8,TAGnopが続けてフェッ
チされる。

キャッシュプログラムメモリ６はフェッチされたＮ＃3,
TAG＋Ｌというプログラムデータに対して、入力データ
パケットに含まれるG/C0とデータ０を付加するととも
に、データが正常にフェッチされたことを示すフラグ０
を付加する。なお、ミスヒットしたときにはフラグ１が
付加される。対データ検出部７はこのプログラムデータ
に対して対となるプログラムデータが既にフェッチされ
ているか否かを判別する。すなわち、第２図に示すノー
ドにおける右側のデータがフェッチされている否かを
判別する。今、ノードにおける右側のデータは未だフ
ェッチされていないので、対データ検出部７はこのプロ
グラムデータを待機させる。

一方、ノードにおけるnop命令のためのプログラムデ
ータは、対となるべきプログラムデータを必要としない
ので、キャッシュプログラムメモリ６はフェッチされた
Ｎ＃8,TAGnopに対して、入力データパケットに含まれる
G/C0,データ０を付加するとともに正常にフェッチされ
たことを示すフラグ０を付加して出力する。また、キャ
ッシュプログラムメモリ６からプログラムデータがフェ
ッチされたことにより、接点８が閉じられる。したがっ
て、nop命令のためのプログラムデータはALU9と外部プ
ログラムメモリ２とに与えられる。

このとき、情報処理装置１には、次の入力データパケッ
トが与えられたものとする。すなわち、第２図に示すノ
ードＢにおける処理を次に行なうためのプログラムデー
タとして、データ1,TAGソース,G/C0,N＃Ｂが分岐結合部
3,5を介してキャッシュプログラムメモリ６に与えられ
る。このプログラムデータは、前述の第３図で説明した
Ｎ＃Ａとほぼ同じであり、ノードでデータ１のnop命
令を実行し、ノードにおいて、データ１をノードＤか
ら与えられかつノードでnop命令が実行されたデータ
と加算することになる。

このために、前述の第３図の説明と同様にして、キャッ
シュプログラムメモリ６はＮ＃B,G/C0を該メモリの物理
アドレスおよびキーコードとして、対応するプログラム
データＮ＃4,TAG＋Ｌをフェッチする。このプログラム
データは、第２図に示すプログラムのノードにおける
加算の左側入力を与えるデータである。ノードにおけ
るnop命令を処理するために同じプログラムデータ１が
与えられるので、キャッシュプログラムメモリ６には、
Ｎ＃B,G/C0のキーコードに対してコピーフラグが予め設
定されている。

したがって、同じＮ＃B,G/C0をキーコードとする次のno
pの命令を示すＮ＃9,TAGnopのプログラムデータが続け
てフェッチされる。さらに、キャッシュプログラムメモ
リ６でフェッチされたＮ＃4,TAG＋Ｌというプログラム
データに対して、入力データパケットに含まれるG/C0と
データ１と正常にフェッチされたことを示すフラグ０が
付加される。そして、対データ検出部７は、そのプログ
ラムデータに対して、対となるプログラムデータが既に
フェッチされているか否かを判別する。すなわち、第２
図に示すノードにおける右側のデータがフェッチされ
ているか否かを判別するが、未だフェッチされていない
ので、このプログラムデータを待機させる。

一方、前述の入力データパケットがキャッシュプログラ
ムメモリ６に入力されている間に、外部プログラムメモ
リ２は第３図に示すように、対データ検出部７から与え
られたnop命令のためのプログラムデータに含まれるＮ
＃8,G/C0の組合わせで決まるキーコードに対応するアド
レスから次の命令を読出す。すなわち、ノードでnop
命令の処理が行なわれたデータをノードＮ＃ｘに出力す
るために、Ｎ＃8,G/C0,N＃x,TAGシンクをキャッシュプ
ログラムメモリ６に出力する。

また、ALU9にはnop命令のためのデータが与えられる
が、nop命令は何ら演算を行なわないことを示す命令で
あるため、このプログラムデータをそのまま出力する。
nop命令のプログラムデータは分岐結合部10,バッファ1
1,分岐結合部５を介してキャッシュプログラムメモリ６
に与えられる。

キャッシュプログラムメモリ６には、外部プログラムメ
モリ２から読出されたプログラムデータが、バッファ11
を介して遅延が加えられたプログラムデータのフェッチ
よりも先に入力される。したがって、キャッシュプログ
ラムメモリ６は、、そのプログラムデータに含まれるＮ
＃8,G/C0のキーコードに対応するプログラムデータとし
て、第５図に示すように、Ｎ＃x,TAGシンクをフェッチ
することができ、続いてバッファ11を介して与えられる
プログラムデータに含まれるＮ＃9,G/C0のキーコードに
対応するプログラムデータであるＮ＃y,TAGシンクをフ
ェッチすることができる。

次に、情報処理装置１には、ノードＤのプログラムデー
タとして、第５図に示すように、データ3,TAGソース,G/
C0,N＃Ｄが与えられる。すなわち、ノードＤのプログラ
ムデータは、第２図に示すように、ノードでnop命令
を実行し、ノードでinc（インクリメント）命令を実
行するものである。このために、キャッシュプログラム
メモリ６はこのプログラムデータに含まれるＮ＃D,G/C0
をキーコードとして、プログラムＮ＃1,nopをフェッチ
し、同じキーコードＮ＃D,G/C0に対してコピー処理を行
なって、対応するプログラムデータＮ＃2,incをフェッ
チする。すなわち、キャッシュプログラムメモリ６は、
キーコードＮ＃2,TAGincに、入力データパケットに含ま
れるG/C0とデータ０とフラグ０を付加して対データ検出
部７に出力する。

これらの処理を実行している間において、外部プログラ
ムメモリ２からはキーコードＮ＃9,G/C0に対応するプロ
グラムＮ＃9,G/C0,N＃y,TAGシンクが読出されてキャッ
シュプログラムメモリ６に与えられる。このプログラム
データは、第２図に示すノードでnop命令が処理され
たデータをノードｙに出力することを示している。

また、ALU9は第５図に示すＮ＃1,G/C0,TAGnop,Lデータ
3,フラグ０のプログラムデータがnop命令であるため、
被処理データを素通りさせ、分岐結合部10,バッファ11,
分岐結合部10を介してキャッシュプログラムメモリ６に
与える。キャッシュプログラムメモリ６は、第６図に示
すようにそのプログラムデータのＮ＃1,G/C0をキーコー
ドとして、Ｎ＃3,TAG＋Ｒをフェッチする。そして、キ
ャッシュプログラムメモリ６は、Ｎ＃3,G/C0,TRG＋R,デ
ータ3,フラグ０からなるプログラムデータを対データ検
出部７に与える。

このような命令フェッチが可能となるのは外部プログラ
ムメモリ２が第５図に示すＮ＃1,G/C0,TAGnop,Lデータ
3,フラグ０からなるプログラムデータのキーコードＮ＃
1,G/C0に基づいて、対応する２組のプログラムデータ,G
/C0,N＃3,TAG＋R,N＃4,TAG＋Ｒを連続して読出し、これ
らの命令がフェッチされるよりも以前にキャッシュプロ
グラムメモリ６に与えられるからである。それゆえに、
キャッシュプログラムメモリ６はそのプログラムデータ
のＮ＃1,G/C0をキーコードとして、Ｎ＃4,TAG＋Ｒのデ
ータをもフェッチし、Ｎ＃4,G/C0,TAG＋R,データ３のプ
ログラムデータを対データ検出部７に与える。

すなわち、対データ検出部７には、第２図に示したノー
ドの左側の被処理データと、ノードの右側の被処理
データが与えられたことになる。前述の第３図で説明し
たように、ノードの左側のプログラムデータおよび被
処理データは既に対データ検出部７に与えられており、
また、前述の第４図で説明したように、ノードの左側
のプログラムデータおよび被処理データが既に対データ
検出部７に与えられている。したがって、対データ検出
部７はノードの２つの被処理データおよびノードの
２つの被処理データが揃ったことを検出し、第７図に示
すように、まずＮ＃3,G/C0,TAG＋,Lデータ0,Rデータ3,
フラグ０のプログラムデータをALU9に与える。応じて、
ALU9はノードにおける加算のための演算処理を実行す
る。さらに、対データ検出部７はＮ＃4,G/C0,TAG＋,Lデ
ータ1,Rデータ３のプログラムデータをALU9に与え、ノ
ードにおける演算処理を実行させる。

前述のごとく、ALU9はノード，の演算処理を行なっ
た後、第２図に示すように、ノード，でisel命令を
実行する。このisel命令は、整数タイプの読出命令であ
る。

次に、isel命令を実行するときに、キャッシュプログラ
ムメモリ６でハッシュ衝突が生じた場合の動作について
説明する。この実施例では、Ｎ＃とG/Cとを組合わせて
プログラムデータをフェッチするためのキーコードとし
た。この場合、Ｎ＃５とＮ＃６は４ビットのコードで表
わせば、“0101",“0110"となり、それぞれを識別する
ことは可能である。しかしながら、たとえば上位２ビッ
トをキーコードとし、下位２ビットを物理アドレスとし
て見た場合、ともに“01"であるため同じになる。すな
わち、上位２ビットをキーコードとして用いた場合に
は、Ｎ＃5,N＃６を識別することはできない。このため
に、第２図に示すノードでisel命令を実行した後、ノ
ードのisel命令を実行すると、ALU9は次のような処理
を実行する。

すなわち、ALU9はノードの演算を実行すると、第８図
に示すように、バッファ11にＮ＃5,G/C0,TAG★，データ
３の演算結果を出力する。キャッシュプログラムメモリ
６はＮ＃5,G/C0のキーコードに対応して、Ｎ＃7,TAG＊
Ｒのデータをフェッチする。一方、ALU9はノードでis
elの演算処理を実行した後、ノードでiselの演算処理
を実行し、その演算結果であるＮ＃6,G/C0,TAG★，デー
タ４をバッファ11に出力する。

ところで、キャッシュプログラムメモリ６は、まず最初
の演算結果のＮ＃5,G/C0をキーコードとして、対応する
プログラムデータをフェッチしようとするが、前述のご
とく、キャッシュメモリではＮ＃５とＮ＃６との識別が
できないためにもともとＮ＃5,G/C0のキーコードとして
外部プログラムメモリ２より与えられたプログラムデー
タの上にＮ＃6,G/C0をキーコードとして外部プログラム
メモリ２より与えられた次のプログラムデータが書込れ
ており、キャッシュプログラムメモリ６はＮ＃5,G/C0を
キーコードに対応する正常なデータをフェッチできず、
ミスヒットを生じる。このような場合であっても、正常
に動作させる必要がある。

そこで、この実施例では、キャッシュプログラムメモリ
６はミスヒットを生じた場合に、ハッシュ衝突の生じた
ことを示すために、第９図に示すようにプログラムデー
タにミスヒットフラグ３を立てる。対データ検出部７は
プログラムデータにミスヒットフラグが立っている場合
には、接点８を閉じない。このため、対データ検出部７
から出力されたプログラムデータは外部プログラムメモ
リ２にのみ与えられ、ALU9には与えられない。

外部プログラムメモリ２は第９図に示すように、対デー
タ検出部７から与えられたプログラムデータのキーコー
ドＮ＃5,G/C0に基づいて、第10図に示すように、ノード
の命令を実行するためのプログラムデータＮ＃7,G/C
0,TAG＊７を読出すばかりでなく、演算しようするデー
タ3,フラグ３も読出す。

すなわち、この実施例では、キャッシュプログラムメモ
リ６でミスヒットした場合、外部プログラムメモリ２を
直接アクセスして、次の命令とともにデータもキャッシ
ュプログラムメモリ６に与えることを特徴としている。

外部プログラムメモリ２から読出されたノードのプロ
グラムデータはキャッシュプログラムメモリ６に与えら
れるが、このプログラムデータにはデータも付加されて
いるので、ミスヒットフラグに従ってキャッシュプログ
ラムメモリ６を素通りし、対データ検出部７に与えられ
る。対データ検出部７はそのプログラムデータと対とな
るべきデータが入力されるまで待機する。外部プログラ
ムメモリ２はノードのプログラムデータを直接読出し
た後、第10図に示すようにノードのプログラムデータ
Ｎ＃6,G/C0,TAGR,フラグ０がキャッシュプログラムメモ
リ６に入力される。

キャッシュプログラムメモリ６はＮ＃6,G/C0をキーコー
ドとして、Ｎ＃7,TAG＊Ｒのプログラムデータをフェッ
チする。このプログラムデータは対データ検出部７に与
えられる。対データ検出部７はノードにおける演算を
実行するのに必要な２つのデータが揃ったことを検出
し、再び接点８を閉じ、その２つのプログラムデータを
ALU9に与え、演算処理を実行する。

以下、同様の動作を行ない、ノードの演算結果とノー
ドＣで入力されるプログラムデータに基づいて、ノード
における加算のための演算処理が行なわれ、ノードｕ
に出力される。

上述のごとく、この発明の一実施例によれば、キャッシ
ュプログラムメモリ６で命令フェッチのミスヒットが生
じた場合には、接点８を開いて、内部プログラムメモリ
２から命令のプログラムデータを読出すとともに、デー
タをもあわせてキャッシュプログラムメモリ６に与える
ようにしたので、ハッシュ衝突が生じても正常な動作を
実行することができる。

［発明の効果］ 以上のように、この発明によれば、必要な命令に対し
て、フェッチされるとともに、プログラム記憶手段へア
ップロードされて確実にフェッチされ、ミスヒットした
場合には、直接外部プログラム記憶手段をアクセスする
ことにより、命令とともにデータも読出すようにしたの
で、極めて良好な効率で命令のフェッチを実行すること
が可能となる。

【図面の簡単な説明】

第１図はこの発明の一実施例の概略ブロック図である。
第２図は第１図に示した情報処理装置によって処理され
るプログラムの一例を示す図である。第３図ないし第10
図は第２図に示したプログラムを実行するための手順を
説明するための図である。 図において、１は情報処理装置、２は外部プログラムメ
モリ、3,4,5,10は分岐結合部、６はキャッシュプログラ
ムメモリ、７は対データ検出部、８は接点、９はALU、1
1はバッファを示す。

Claims (1)

【特許請求の範囲】
1. 【請求項１】データフロープログラムを記憶するプログ
   ラム記憶手段と、前記プログラム記憶手段から対となる
   プログラムデータおよび被処理データが入力されたこと
   を判別する対データ検出手段と、前記対データ検出手段
   によって対となるプログラムデータおよび被処理データ
   が検出されたことに応じて、そのプログラムデータおよ
   び被処理データに基づく演算を実行する演算処理手段
   と、前記プログラム記憶手段にプログラムデータを与え
   る外部プログラム記憶手段とを備えた情報処理装置にお
   いて、前記プログラム記憶手段をアクセスするプログラ
   ム実行制御方式であって、 前記対データ検出手段によって前記プログラム記憶手段
   から対となるプログラムデータおよび被処理データの読
   出されたことが判別されたことに応じて、前記外部プロ
   グラム記憶手段のアクセスを実行するとともに、前記演
   算処理手段に処理すべきプログラムデータおよび被処理
   データを送出し、前記演算処理手段の演算処理結果デー
   タに対する次の命令を前記プログラム記憶手段に対して
   フェッチし、該命令フェッチがミスヒットした場合、前
   記外部記憶手段に対して直接前記次の命令を被処理デー
   タとともにアクセスするようにしたことを特徴とする、
   プログラム実行制御方式。