JPH03229381A - データ駆動形計算機 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、データの依存関係に基づいて処理を駆動する
方式を採用しているデータ駆動形計算機に関し、特に巡
回パイプライン構成において待合わせメモリに起因する
実行停止を回避する技術に関する。

（従来の技術〕 第７図はデータ駆動形計算機におけるデータ処理の概念
図であり、２つのデータの加算が行われる様子を示して
いる。図において“Ａ”　という値を持ち“ａ”という
識別子を付加されたパケット８１が発火処理部８７に与
えられると、識別子フィールド比較部８４は待合わせメ
モリ８５にパケット８１の識別子“ａ”と一致する識別
子を持つパケ−／　）が格納されているか否かを検索す
る。第７図では“Ｂ”という値を持ち“ａ”という識別
子を持つパケット８２が格納されているので、このパケ
ット８２が待合わせメモリ８５から読出され、入力され
たパケット８１と共にデータ対形成部８６へ送られる。

データ対形成部８６はパケット８１とパケット８２とを
合体し、“Ａ”という値と“Ｂ″という値とにａ”とい
う識別子を付加したデータ８３を形成しくこれを発火と
呼ぶ）、データ処理部８８でＡ＋Ｂの演算が実行される
。演算結果は図示しないプログラムメモリに識別子をア
ドレスとして与えられ、そこで更新処理を行った後、外
部に出力されるか、又は再度発火処理部８７に与えられ
る。これらの発火処理部８７、データ処理部８８及びプ
ログラムメモリから巡回パイプラインが構成される。

第７図の例では入力されたパケット８１と同じ識別子“
ａ”を有するパケット８２が待合わせメモリ８５に格納
されていたが、入力されたバケツ）８１と同じ識別子を
有するパケットが待合わせメモリ８５に格納されていな
い場合は、入力されたパケット８１は待合わせメモリ８
５に格納され、これと一致する識別子を有するパケット
が入力されるまで待合される。

このように発火処理部８７はデータ駆動形計算機におい
て演算すべきパケットを検索する役割を持っている。

通常データ駆動形計算機においては、識別子のビット幅
は数十ビットとなるため、識別子毎にメモリのアドレス
を割当てるとメモリ容量が膨大なものとなるため、従来
より待合わせメモリ８５に用いるメモリとしてビット幅
を圧縮（以下ハツシュという）し、これをメモリアドレ
スとして用いたメモリ　（以下ハツシュメモリという）
を用いている。

第８図は入力パケットの一例の構成を示すビットマツプ
図、第９図はハツシュメモリの一例の構成を示すブロッ
ク図である。

入力パケットは演算対象となる１８ビツトのオペランド
データＯＤ、演算内容を示すコードである７ビソトのオ
ペレーションコードＱＣ，１ビツトのプロセッサ選択ビ
ットＰＳ、入力パケットが２入力命令か１入力命令かを
示すＩビットのＦＣ処理選択ビット及び演算順に応して
演算場所（ノード）の左又は右に配置することを示す左
右データ選択ビットを含み、各種の選択を行うセレクシ
ョンコートＳＣ１入力データの入力順等の属性を示す９
ビツトのカラー／世代番号ＤＮ並びに演算の行われるべ
き場所を示す２１ビツトのノード番号ＮＮの６０ピント
にて構成されている。そしてプロセッサ選択ビットｐｓ
とカラー／世代番号ＤＮとノード番号ＮＮとから３１ビ
ツトの識別子が構成される。

ハツシュメモリ６０１はノード番号ＮＮの下位９ビツト
をハフシュアドレスとしてアクセスされるものであり、
リードライトサイクルを定めるリードライト信号Ｗ／Ｒ
−Ｈ，書込みデータ及び各アドレスの有効・無効の別を
示すプレゼンスビットＰＢの更新を行うセントリセット
信号Ｓ／πが与えられる。格納される書込みデータは１
８ピントのオペランドデータＯＤと、９ビツトのカラー
／世代番号ＤＮ及びノード番号ＮＮの残り１２ビツトの
２１ビツトの識別子と、１ビツトのプロセッサ選択ビッ
トＰＳの合計４０ビツトからなっている。またハツシュ
メモリ６０１には別に１ビツトのプレゼンスビットＰＢ
が格納されており、合計ｌワード４１ビツトとなってい
る。またアドレス空間は２９＝５１２となっており、ハ
ツシュメモリ６０１　は４１ビツト／ワード×５１２の
大きさを有している。

ハツシュメモリを用いた場合、ハ・ンシュしたアドレス
（以下ハツシュアドレスという）をアクセスしたときに
同一アドレスでの衝突、所謂ハツシュ衝突が起こる虞が
ある。

即ちハツシュ衝突とは識別子の一部をハツシュアドレス
とした場合にハツシュアドレスが既にハツシュメモリ内
に格納されたデータと一致しても、残りの識別子が一致
しないデータがアクセスされたとき、そのデータを記憶
するアドレスが既に占有されているために起こるもので
ある。

〔発明が解決しようとする課題〕

ここでハツシュメモリ６０１を待合わせメモリ８５に用
いたデータ駆動形計算機において、第１０図！ａ）に示
すデータフローグラフを実行する場合を考える。

なお、説明を平易にするためハツシュメモリ６０１はノ
ード番号の下位２ビツトをハツシュアトレスとしてアク
セスされ、４つのパケットを蓄えるだけの容量（アドレ
ス空間＝２２＝４）を持つこととして以下の説明を行う
。

第１０図（ａｌに示す如くこのデータフローではノート
数８で構成され、６つの入力パケットを演算処理してい
く。ここで特に番号０のノードの左入力となる第２パケ
ツトが番号７のノードの左入力にもなっている。ハツシ
ュメモリ６０１をアクセスするメモリアドレスは４メモ
リアドレスとなり、第１０図（ａ）のデータフローグラ
フのノード番号は同図（ｂ）に示すメモリアドレスとな
る。このとき第１０図（ａｌにおいて、番号３　（０１
１）のノードの左入力となる第１パケツトと番号７　（
１１１）のノートの左入力となる第２パケツトとは、ノ
ード番号の下位２ビツトが同じ値（＝１１）なのでハツ
シュメモリ６０１の同一メモリアドレス“３″（＝１１
）を指すこととなる。第２パケツトが第１パケツトより
も先にハツシュメモリ６０１に蓄えられた場合、第２パ
ケツトは番号７のノードの右入力となる第３バケツトを
待つことになるが、第３バケツトは番号３，５及び６の
ノードが実行されないと生成されない。

ところが、第２パケツトが第１パケツトより先に格納さ
れ、第２パケツトは待合わせの相手（第３バケツト）が
生成されないので、ハツシュメモリ６０１内に格納され
たままとなり、第１パケツトと第２パケツトとがハツシ
ュ衝突してしまうので、第１パケツトはハツシュメモリ
６０１へ蓄えられず、従って番号３のノードの演算は実
行されないこととなり、結局演算処理の実行が停止して
しまうことになる。

このようにハツシュメモリ６０１の容量より大きなデー
タフローグラフを実行する際、同一メモリアドレスを複
数のノードが発火のために使用するので、パケットの到
着順によってはハツシュ衝突を起こし、データフローグ
ラフの実行を途中で停止させてしまうという問題点があ
った。

本発明は上記のような問題点を解決するためになされた
ものであり、待合わせメモリであるハツシュメモリ内に
既に格納されているパケットのために、先に演算を実行
すべきパケットがハツシュメモリに格納することができ
ず、プログラムの実行が事実上停止状態となったことを
巡回パイプライン中にある全パケットの発火の有無によ
り検出し、停止状態が検出された場合、待合わせメモリ
内の全パケットを入れ換えることにより先に実行すべき
パケットを待合わせメモリ内に格納し、演算の実行を停
止させることなく継続して実行できるデータ駆動形計算
機を得ることを目的とする。

〔課題を解決するための手段〕

本発明に係るデータ駆動形計算機は、入力されたパケッ
トが少なくとも１つの待合わせメモリに格納できず、巡
回パイプラインを介して再度待合わされるまでに発火処
理されたか否かを検出する手段を設け、この間に発火処
理されなかった場合、データ処理が進んでおらず、待合
わせメモリから処理を実行するために出力されたパケッ
トがなく、データ処理が停止状態となる虞があると判定
し、この場合に待合わせメモリ内の全パケットを入換手
段により入換えるようにしたものである。

〔作用〕

本発明においては待合わせメモリに格納できないパケッ
トが発生すると、そのパケットは巡回パイプライン上の
各処理部を通過し、再度待合わせメモリに入力される。

この間に発火処理部で発火処理されたか否か、即ち待合
わせメモリからデータ処理を進めるためにパケットが出
力されたか否かを検出し、この間に発火処理されず、パ
ケットが出力されなかったときは、待合わせメモリ内の
全パケットを入換え、入力されたパケットが必ず待合わ
せメモリに格納されるようになり、処理の実行が停止さ
れることはなくなる。

〔実施例〕

以下、本発明の実施例を図に基づいて詳細に説明する。

第１図はこの発明に係るデータ駆動形計算機の構成図で
ある。図において１０１は発火処理部である。該発火処
理部１０１　はパケットが入力されると、パケットに付
属している識別子の内、行き先ノードを示すノード番号
及びカラー／世代番号が一致するパケットが待合わせメ
モリである連想メモリ１１２に、あるかどうかを検索し
、ノード番号及びカラー／世代番号が一致するパケット
が存在した場合、２つのパケットをマージし、発火パケ
ットを生成し、ノード番号及びカラー／世代番号が一致
するパケットが存在しなかった場合、入力パケットを連
想メモリ１１２に格納する機能を有する。

発火処理部１０１で発火した発火パケットは演算処理部
１０２に与えられ、発火パケットに付属している命令コ
ードに従って演算処理を施す。演算結果のパケットはプ
ログラムメモリ１０３に与えられ、パケットに付属して
いるノード番号を入力アドレスとしてプログラムメモリ
１０３の内容を読出し、読出した内容に基づき識別子の
ノード番号と命令コードとの更新を行う。

以上、発火処理部１０１、演算処理部１０２、プログラ
ムメモリ１０３は、発火処理部１０１は１段の、その他
は複数段のパイプライン構成となっており、全体として
巡回パイプライン構成となっている。

第２図はパケットのデータ構造を示す図であり、パケッ
トは全部で８１ビツトあり、上位から順に１８ビツトの
オペランドデータ２０Ｄ２、オペランドデータ１００１
．７ビツトのオペレーションコード０Ｃ１１ビツトの印
ビットＭＢ、各１ビツトのスルービットＴＨ１左／右デ
ータ選択ビットＳＬ及びＦＣ処理選択ビットを含む７ビ
ソトのセレクションビット５Ｃ１１９ヒツトのカラー／
世代番号ＤＮ並びに２１ビツトのノード番号ＮＮから構
成される。ここでビットＭＢは、これが発火処理部１０
１から出力されてから次に入力されるまでに、発火処理
がされたか否かを検出するための対象となるパケットを
示すためのものである。この巡回パイプライン上を第２
図に示すデータ構造のパケットが移動している。但し、
演算処理部１０２の出力から発火処理部１０１の入力ま
ではパケットはオペランドデータ２０Ｄ２を持たず、６
３ビツト構成となっているが、発火処理部１０１での処
理後は、発火前のパケットの２つのオペランドデータ０
０１．００２を夫々の左／右データ選択ビットＳＬに従
ってオペランドデータ１０Ｄ１及びオペランドデータ２
０Ｄ２として格納した状態で演算処理部１０２に送られ
る。演算処理部１０２では、２つのオペランドデータ０
０１　、　ＯＤ２の演算結果がオペランドデータ１０Ｄ
１　として格納されてまた元の６３ビツト構成となる。

但し、発火処理部１０１から演算処理部１０２の間のパ
ケットでも１オペランド演算のパケット又は連想メモリ
１１２が満杯のために巡回パイプラインを通過するスル
ーパケットの場合は、オペランドデータ２０Ｄ２にはな
にも保持されない。

また、発火処理部１０１から出力されたスルーパケット
は演算処理部１０２及びプログラムメモリ１０３では、
処理されずそのままの情報を保持して再び発火処理部１
０１に戻ってくる。

次に発火処理部１０１内部の構成について説明する。

１１１は、発火処理部１０１に入力されたパケットをラ
ッチするデータラッチである。入力パケットは、波ライ
ンの前段からの信号ＣＯが“Ｈ″のタイミングでラッチ
される。ラッチされたパケットのうち印ビア）ＭＢ、Ｆ
Ｃ処理選択ビット、左／右データ選択ピッ）ＳＬが制御
部１１８に出力される。また、印ピッ）ＭＢとスルービ
ットＴＦＩを除く入力パケットの各データは、識別子３
０ビツトとその他の３２ビツトに分けて連想メモリ１１
２に入力される。同じく印ビット問とスルーピッ１−Ｔ
Ｈを除く入力パケットの各データは、データ対形成器１
１６にも入力される。

第３図は、連想メモ１月１２の構成を示すブロック図で
ある。図において２０１はデータラッチ１１１を介して
入力されるパケ・ノドに含まれる３０ビツトの識別子と
一致するデータを検索する連想メモリ（以下ＣＡＭとい
う）であり、３１ビツト×３２アドレスの容量となって
いる。ＣＡＭ　２０１のうち１ビツトは格納されている
データの有効性を判別するためのプレゼンスビットＰＢ
の格納に用いられる。ＣＡＭ２０１には各アドレスに対
して一致／不一致信号線（以下マツチラインという）が
設けられており、与えられた３０ビツトの識別子と、Ｃ
ＡＭ　２０１に格納された識別子とが一致したアドレス
のマツチラインのみ“Ｈ”が出力される。またＣＡＭ　
２０１にはセレクタ２０５を介してプレゼンスビットＰ
Ｂの更新を行うセット信号Ｓ／πが与えられると共にリ
ードライトのサイクルを定めるリードライト信号Ｗ／π
が与えられる。セレクタ２０５は一端に基準電圧“Ｈ″
が、他端にセント信号Ｓ／πが与えられており、また切
替端子にリードライト信号Ｗ／πが与えられており、リ
ードサイクルのときは基準電圧“Ｈ”が、ライトサイク
ルのときはセント信号Ｓ／πが選択される。即ちリード
サイクルＷ／π＝４Ｌ″のときは、プレゼンスピッ）Ｐ
Ｂ＝１のアドレスだけを検索する必要があるので、検索
データのプレゼンスビットＰＢに相当するビットを常に
１とし、ライトサイクルＷ／π＝“Ｈ”のときのみプレ
ゼンスピントＰＢを更新する必要があるためにこのセレ
クタ２０５が用いられる。

またＣＡＭ　２０１からは３２ビツトのマツチラインに
識別子の一致、不一致の別を示す判定信号が出力される
と共に、空アドレス検出器２０３に各アドレスのプレゼ
ンスビットＰＢが出力され、そこでプレゼンスビットＰ
Ｂより有効なデータが格納されていないアドレスが検出
される。

空アドレス検出器２０３は、空アドレスを示す３２ビツ
トの検出信号をアドレスセレクタ２０６　及ヒ２０７の
一端に出力すると共に、空アドレスがなく　ＣＡＭ２０
１全アドレスにパケットが格納されたとき、そのことを
示す満杯信号ＦＬを制御部１１８に出力する。

なお、空アドレスを示す検出信号はＣＡＭ　２０１の３
２個のアドレスに対応する３２ビツトの出力であり、そ
の空アドレスのビットだけが“Ｈ”となっている。アド
レスセレクタ２０６及び同２０７には、マツチラインか
らの判定信号も与えられる。

追出アドレス発生器２０４は、連想メモリ１１２内に格
納されている全パケットを出力するための追出アドレス
を発生する。追出アドレス発生器２０４は、制御部１１
８から出力される信号Ｔｄのタイミングで、３２アドレ
スの各々を示す追出アドレスを順に生成し、アドレスセ
レクタ２０６及び２０７に与える。

アドレスセレクタ２０６では、切換端子に与えられたリ
ードライト信号Ｗ／π及び連想メモ１月１２内の全パケ
ットを出力するために制御部１１８から出力される追出
信号りに応じて、追出信号りが“Ｈ”のときには追出ア
ドレスを、追出信号りが“Ｌ”でありリードサイクルＷ
／π＝“Ｌ”のときは固定信号“０”を、また追出信号
りが“Ｌ”でありライトサイクルＷ／Ｒ＝　“Ｈ”のと
き、空アドレス検出器２０３の検出信号を各々選択する
。

また追出信号りは後述する出力セレクタ１１７にも出力
される。

アドレスセレクタ２０７では、切換端子に与えられたリ
ードライト信号Ｗ／Ｒ及び制御部１１８により入力され
る連想メモリ１１２内の全パケットを出力するための追
出信号りに応じて、追出信号りが“Ｈ”のときには追出
アドレスを、追出信号りがＬ″でありリードサイクルＷ
／π＝″Ｌ”のときは判定信号を、また追出信号りが“
Ｌ”でありライトサイクルＷ／π＝“Ｈ”のとき空アド
レス検出器２０３の検出信号を各々選択する。

ＲＡ門２０２は、オペランドデータ００１１８ビツト、
オペレーションコードＯＣ７ビノト及びセレクションコ
ードＳＣ７ビノトの合計３２ビツトを格納するものであ
り、３２ビツト×３２アドレスの容量となっている。リ
ードサイクルでは、アドレスセレクタ２０７から入力さ
れるアドレスのデータ３２ビツトがＣＡＭ２０１　のデ
ータ３０ビツトと共にデータラッチ１１３に出力される
。即ち、ＣＡＭ　２０１から出力される判定信号３２ビ
ツトと合計９４ビツトのデータがデータラッチ１１３に
出力される。一方、ライトサイクルではアドレスセレク
タ２０７の入力されるアドレスに従ってデータラッチ１
１１から与えられた入力パケットの内容が格納される。

またライトサイクルでは、ＣＡＭ　２０１がヒツトした
場合及び追出信号りの制御によってパケットが追い出さ
れた場合は、出力されたアドレスのプレゼンスビ・ント
ＰＢがクリアされる。

第１図において１１３はデータラッチであり、連想メモ
リ１１２より出力された９２ビツトのデータが信号ＴＩ
＝　“Ｈ”でラッチされる。９４ビツトのうち・判定信
号３２ビツトはヒツト検出に、それ以外の６２ビツトは
出力セレクタ１１７に出力される。オペランドデータ１
０Ｄ１の１８ビツトは同時にデータラッチ１１５にも出
力される。

ヒツト検出器１１４はＣＡＭ　２０１からの３２本のマ
ンチラインの反転信号をモニタし、その中の１ビツトで
も“Ｈ”に立ち上がったものがあった場合は（＝ＣＡＭ
　２０１がヒツトすれば）、ヒツト信号旧Ｔを制御部１
１８に与える。

データ対形成器１１６は、データラッチ１１３を介して
連想メモマ月１２から出力されたオペランドデータ１０
０１が一端に入力されると共に、他端にはデータラッチ
１１１からの６３ビツトの入力されたパケットのデータ
が与えられる。そして２つのデータがマージされ、２つ
のオペランドデータ００１　、００２を含む８１ビツト
のパケットが形成される。このとき２項演算の減算命令
の如くオペランドの順序関係が重要なものがあるので、
選択されたオペランドデータと入力されたオペランドデ
ータとは正しく左または右のオペランドとして配置され
る必要がある。

第４図はデータ対形成器１１６の構成を示すブロック図
である。データ対形成器１１６は２つのデータセレクタ
５０１，５０２からなり、各々の切換端子には入力され
たパケットの左／右データ選択ビットＳＬでその状態を
示すセレクタ制′４Ｂ信号Ｌ／πが与えられる。データ
セレクタ５０１のＡ端子及びデータセレクタ５０２のＢ
端子にはデータラッチ１１１からの入力されたパケット
のオペランドデータが各々与えられ、データセレクタ５
０１のＢ端子及びデータセレクタ５０２のＡ端子にはデ
ータラッチ１１５より格納されたオペランドデータが与
えられる。

そして入力されたパケットの左／右データ選択ビットＳ
Ｌがセレクタ制御信号Ｌ／πとして入力され、Ｌ／πが
“１″のときは夫々のデータセレクタ５０１゜５０２の
Ａ端子に与えられたオペランドデータが、またＬ／πが
“０”のときは夫々のデータセレクタ５０１　、５０２
のＢ端子に与えられたオペランドデータが選択され、デ
ータセレクタ５０１からの選択出力が左オペランド（オ
ペランドデータ１）となり、データセレクタ５０２から
の選択出力が右オペランド（オペランドデータ２）とな
り、それらと入力されたパケットのオペランドデータを
除く他のデータとがマージされ出力セレクタ１１７に入
力される。セレクタ制御信号Ｌ／πは、入力パケットが
１オペランド命令の場合又は連想メモリ１１２が満杯で
あり、入力パケットがそのまま出力される場合は入力パ
ケットの左／右データ選択ピッ）ＳＬに拘らず制御部１
１８により強制的にセレクタ制御信号Ｌ／πは“１”と
されるため入力パケットがそのまま出力される。

出力セレクタ１１７は、連想メモ１月１２から追い出さ
れたパケットを出力するか、発火したパケット、１オペ
ランド命令を含む入力パケット又は、スルーパケットを
出力するかを選択するものである。この選択は制御部１
１８から与えられた追出信号りによって選択される。こ
の追出信号りは、制御部１１８によって巡回パイプライ
ン中の全パケットが発火しなかったことを検出した場合
に“Ｈ”となる。

制御部１１８には、２つのレジスタ、即ち印カウンタ１
１９と発火フラグレジスタ１２０とが設けられている。

印カウンタ１１９は、印ビットＭＢが”１”のパケット
　（以下印付きパケットという）が巡回パイプライン上
にいくつあるかをカウントするレジスタであり、発火フ
ラグレジスタ１２０は直近に出力された印付きパケット
を出力してから発火が起こった場合には“１”が、起こ
っていない場合には“Ｏ”が保持されている。また、制
御部１１８は印ビットＭＢ、入力パケットの左／右選択
ビ・ノドＳＬ、入力パケットが２オペランド命令か１オ
ペランド命令かの別を示すＦＣ処理選択ビットの状態で
定まる入力選択信号ＦＣ（２入力命令ＦＣ＝１．１入力
命令ＦＣ＝０）、ヒツト信号旧Ｔ及び満杯信号ＰＬが与
えられる。また、パイプライン前段の処理が終了し、前
段の出力データをデータラッチ１１１にラッチしたこと
を示す信号ＣＯ、パイプライン次段の処理が終了し、次
段に発火処理部１０１の結果パケットを出力してもよい
という許可信号■が与えられる。これらの入力信号を判
断して追出信号Ｄ、リードライト信号Ｗ／Ｒ、セット信
号Ｓ／π、データ対形成器１１６に出力するセレクタ制
御信号し／Ｒ，出力パケットのスルービットＴ）ｌ及ヒ
印ビットＭＢ、データ出力信号ＣＩ及びデータ入力許可
信号■を出力する。

また処理のタイミングを決定するタイミング信号Ｔｌ、
Ｔ２．Ｔｄの出力も行う。

次に上記の如く構成されたこの発明のデータ駆動形計算
機の発火処理部１０１の動作について説明する。なお連
想メモリ１１２にはデータ対を待つ複数のパケットが格
納されているとする。第５図は発火処理部１０１の概略
動作を説明するフローチャートである。

パケットが入力されると入力パケットの印ビットＭＢが
制御部１１８に入力され、印ビットＭＢが“１″かどう
かが判断され（Ｓｌ）、印ピッ）ＭＢが”ビの場合、こ
のパケットは前回発火処理部１０１で処理が行われたと
き、連想メモリ１１２中に行き先ノード番号ＮＮとカラ
ー／世代番号ＤＮが一致するパケットは存在しなかった
が、連想メモリ１１２が満杯であったため入力されたパ
ケットがそのままスルーパケットとして出力されたこと
を示す。このため、制御部１１８では、前回このパケッ
トが発火処理部１０１から出力されてから巡回パイプラ
イン中の全パケットが発火しなかったかどうかを印カウ
ンタ１１９及び発火フラグレジスタ１２０により検出す
る必要がある。そこでまず、印付きパケットが発火処理
部１０１に入力され、巡回パイプライン上から印付きパ
ケットがひとつ減ったので印カウンタ１１９をデクリメ
ントする（Ｓ２）。次に印カウンタ１１９の内容をチエ
ツクする（Ｓ３）。この印カウンタ１１９が“０”以外
の場合は、この入力された印付きパケットが前回出力さ
れてから発火が起こり１度は連想メモ１月１２に空がで
きたが、また連想メモ１月１２への新たな格納により連
想メモ１月１２が再度満杯状態となり、新たなスルーパ
ケットが生成され印付きパケットとされたことを示して
いる。即ちこの印付きパケット出力以降に発火したパケ
ットが存在したことを示しているので、巡回パイプライ
ン上の全パケットが発火しなかったとは判断できず、通
常の処理Ｓ６へと処理は移る。印カウンタ１１９が“０
”の場合は、さらに発火フラグの内容をチエツクする（
Ｓ４）。発火フラグが“０”の場合、即ち最終に出力さ
れた印付きパケット以降発火が行われなかった場合、入
力された印付きパケットが前回発火処理部１０１から出
力されてから発火が起こらなかったことを示している。

即ち、前回この入力パケットが発火処理部１０１から出
力されたとき、巡回パイプライン上に存在した全パケッ
トが発火せず発火処理部１０１を通過したことがこのこ
とにより検出され、そこで連想メモ１月１２内に格納さ
れている全パケットを巡回パイプライン上に出力する（
Ｓ５）。連想メモリ１１２内に格納されたパケットの出
力は、まず追出信号りを“Ｈ”として、連想メモリ１１
２からの出力が出力セレクタ１１７で出力されるように
する。その後タイミング信号Ｔｄにより連想メモリ１１
２内の全アドレスを次々にアドレスセレクタ２０６　、
２０７に入力し、全アドレスのパケットをデータラッチ
１１３に出力する。その後パイプラインの次段の入力許
可信号■に従って出力セレクタ１１７を介して全アドレ
スのパケットを順に出力していく。連想メモ１月１２内
の全パテ・ノドが出力された後、ステップＳ６以降の通
常の入力パケットに対する処理を行う。

ヒツト検出器からの旧Ｔ信号により連想メモリ１１２内
に入力パケットの識別子と同一の識別子をもつパケット
があるかどうかを判断する（Ｓ６）。旧Ｔ信号が“１”
、即ち連想メモ１月１２内に大カパケ・ノドの識別子と
同一の識別子をもつパケットが存在した場合、制御部１
１８内の発火フラグを“ｌ”にセットしく５ＩＯ）　、
入力パケットと連想メモ１月１２内のデータとをマージ
し、発火パケットを出力セレクタ１１７を介して出力す
る（Ｓｌｌ）。一方ヒントしなかった場合、連想メモ１
月１２からの満杯信号ＦＬによって連想メモリ１１２が
満杯かどうかが判断される（Ｓ７）。連想メモリ１１２
が満杯でない場合は１、入力パケットが連想メモリ１１
２に格納される（Ｓ１４）連想メモ１月１２が満杯であ
った場合は、スルーパケットとして出力するが、このと
き印付きパケットとするかどうかの判断が行われる（Ｓ
８　、Ｓ９）。

まず、現在印付きパケットが巡回パイプライン上にはな
く、初めてのスルーパケットの場合、即ち印カウンタ１
１９が“Ｏ”の場合はステップＳ１２に進み、発火フラ
グレジスタ１２０をリセットし、印カウンタ１１９をイ
ンクリメントし、スルービットＴＨ及び印ビットＭＢを
セットして、印付きパケットとして出力される。印カウ
ンタ１１９が０”以外、即ちすでに印付きパケットが巡
回パイプライン上に出力されている場合には、最後に印
付きパケット出力されてから発火が起こったか否かがス
テップＳ９で発火フラグをチエツクすることで判断され
、発火が起こっていない場合は、そのままスルーピット
Ｔ）Ｉをセットして出力する。発火が起こっている場合
は、最後に印付きパケットが出力されてから発火が起こ
りさらに再度、連想メモ１月１２が満杯となり、スルー
パケットが生成されたと考えられるので、印カウンタ１
１９をインクリメントし、発火フラグをリセットし、ス
ルーピットＴＯ及び印ビットＭＢをセットして印付きパ
ケットとして出力する。

第６図は本発明装置の動作サイクルを説明するタイミン
グチャートであり、特に巡回パイプライン上の全パケッ
トが発火せずに発火処理部１０１を通過したことを検出
し、連想メモ１月１２内の全パケットを出力する場合の
タイミングチャートである。信号ＣＯが“Ｈ”のタイミ
ングで入力パケットがデータラッチ１１１にランチされ
る。制御部１１８によってこの入力パケットのデータ及
び制御部１１８内の印カウンタ１１９、発火フラグレジ
スタ１２０の情報から巡回パイプライン上の全パケット
が発火せずに発火処理部１０１を通過したことを検出す
ると、まず追出信号りが“Ｈ”となる。これにより、出
力セレクタ１１７からの出力は連想メモリ１１２内部か
らの出力が選択される。最初、信号Ｗ／πは“Ｌ″であ
り、リードサイクルである。そののち制御部１１８から
信号Ｔｄが連想メモリ１１２の追出アドレス発生器２０
４に与えられ、信号Ｔｄが“Ｈ”のタイミングで追出ア
ドレスがひとつ生成され、アドレスセレクタ２０６．２
０７に与えられる。アドレスセレクタにも追出信号りが
入力されており、これにより追出アドレスが選択される
。追出アドレスの発生からアドレス選択及び連想メモリ
１１２からの出力が決定するまでの遅延ののち信号Ｔｌ
が“Ｈ”とされ、連想メモリ１１２からの出力はデータ
ラッチ１１３にラッチされる。データがランチされたの
ち信号Ｗ／πは“Ｈ”　となり、出力されたアドレスの
プレゼンスビットＰＢがリセットされる。またタイミン
グ信号Ｔ１の“Ｈ”及びパイプライン次段からのデータ
入力許可信号■の入力が共に確認されると、データ出力
信号Ｃ１が出力され、データラッチ１１３にラッチされ
ていたパケットは出力セレクタ１１７を介して出力され
る。この動作を３２回繰り返すことで連想メモリ１１２
内の全パケットが巡回パイプライン上に出力される。そ
の後、リードサイクル、処理サイクル、ライトサイクル
を経て処理を終了する。処理が終了するとパイプライン
前段に入力許可信号■が出力され次のパケットの入力が
促される。

なお、上述の実施例ではオペランドの待合わせメモリと
してパケットの識別子全体をキーとじて待合わせを行う
連想メモ１月１２を用いたが、本発明はこれに限るもの
ではなく、識別子の一部、又は識別子からなんらかの演
算によって生成された数をアドレスとしてパケットを待
合わせメモリに格納しておき、同じアドレスとなるパケ
ットに対してだけ発火すべきパケットであるかを全識別
子を比較することで発火させるかどうかを決定するハツ
シュメモリを待合わせメモリとする構成でもよい。

また、待合わせメモリを通過したパケットが再び待合わ
せメモリに戻ってきたことの検出をパケットに印を付け
ることで実現したが、巡回パイプラインの段数以上のパ
ケットが待合わせメモリを通過したことを検出すること
で実行の停止状態を検出してもよい。

さらに、待合わせメモリの全パケット入れ換えとして、
全パケットを出力した後にパケットの入力を許す例を示
したが、パケットを一つ出力しては一つ入力するという
方法で入れ換えを実現することもできる。

〔発明の効果〕

以上説明したように、この発明によれば、待合わせメモ
リに先に実行すべきパケットが格納できない場合が生じ
、データ処理が停止状態となるのを検出するため、待合
わせメモリを通過したパケ・７トが再度待合わせメモリ
に戻ってくるまでに発火処理がなされたか否かを検出し
、発火処理がなされなかったときは、何ら状況が変化し
ておらず、停止状態となる虞があるので、待合わせメモ
リの全パケットを入れ換えるようにし、停止状態の検出
及び待合わせメモリの全パケットの入れ換えを繰り返す
ことで先に実行すべきパケットがいつか必ず待合わせメ
モリに格納されて実行が進み実行の停止が回避できる等
価れた効果を奏する。

【図面の簡単な説明】

第１図は本発明のデータ駆動形計算機の構成図、第２図
は本発明のデータ駆動形計算機上を動作するパケット構
成を示す図、第３図は本発明のデータ駆動形計算機の待
合わせメモリの構成を示すブロック図、第４図は本発明
のデータ駆動形計算機のデータ対形成器の構成を示すブ
ロック図、第５図は本発明の処理の流れを示したフロー
チャート、第６図は本発明のデータ駆動形計算機の発火
処理部のタイミングチャート、第７図は従来例のデータ
駆動形計算機における処理の概念図、第８図はパケット
の一例の構成を示すビットマツプ図、第９図はハツシュ
メモリの一例の構成を示すブロック図、第１０図（ａ）
はデータフローグラフの一例を示す図、第１０図（ｂ）
は従来例のメモリアドレスとノード番号との関係を示す
図である。 １０１・・・発火処理部　１０２・・・ＡＬＵ　　１０
３・・・プログラムメモリ　１１２・・・連想メモリ　
１１７・・・出力セレクタ　１１８・・・制御部　２０
４・・・追出アドレス発生器なお、図中、同一符号は同
一、又は相当部分を示す。

Claims (1)

【特許請求の範囲】
1. （１）少なくとも実行すべき演算内容を示す命令コード
   と、次に実行すべき命令の場所を示す行先ノード番号と
   を含む識別情報及びデータを有するパケットを格納し、
   格納されたパケットと入力されたパケットとの少なくと
   も行先ノード番号が一致する２つのパケットを検出する
   １又は複数の待合わせメモリを有し、一致した２つのパ
   ケットを合体する発火処理を行う発火処理部を含む複数
   の処理部を巡回パイプライン構造になしてあるデータ駆
   動形計算機において、 入力されたパケットがいずれかの待合わせ メモリに格納されずに前記発火処理部から出力されてか
   ら巡回パイプラインを介して再度格納されなかった待合
   わせメモリに入力されるまでに、前記巡回パイプライン
   中の全パケットが前記発火処理部で発火処理されたか否
   かを検出する手段と、 発火処理が検出されなかったとき、前記待 合わせメモリの内容を全て入換える手段と を備えることを特徴とするデータ駆動形計 算機。