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

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データの依存関係に基
づいて処理を駆動する方式のデータ駆動形計算機に係り
、特に巡回パイプライン構成で待ち合わせメモリのあふ
れによる実行停止の回避に関するものである。

【０００２】

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

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

【０００４】図１３の例では、入力されたパケット８１
と同じ識別子“ａ”を持つパケット８２が待ち合わせメ
モリ８５に既に格納されていたが、入力されたパケット
８１と同じ識別子を持つパケットが待ち合わせメモリ８
５に格納されていなかった場合は、入力されたパケット
８１は待ち合わせメモリ８５に格納され、これと一致す
る識別子を持つパケットが入力されるまで待機させられ
る。

【０００５】このように発火処理部８７はデータ駆動形
計算機において演算すべきパケットを検索し、識別子が
一致するパケットについてはこれを合体して出力する機
能を持っている。

【０００６】ところで、かかるデータ駆動形計算機にあ
っては、識別子のビット幅はプログラム空間のビット幅
に相当するため、数１０ビットとなり、識別子毎にメモ
リの空間を割り当てると、メモリ容量が膨大なものにな
る。このため、従来から待ち合わせメモリ８５に用いる
メモリとして、一定のルールのもとにビット幅を圧縮（
ハッシュ）し、これをメモリアドレスとして用いたメモ
リ，すなわちハッシュメモリを用いている。

【０００７】図１４は入力パケットの一例の構成を示す
ビットマップ図、図１５はハッシュメモリの一例の構成
を示すブロック図である。図１４に示す入力パケットは
、演算対象となる１８ビットのオペランドデータＯＤと
、演算内容を示すコードである７ビットのオペレーショ
ンコードＯＣと、１ビットのプロセッサ選択ビットＰＳ
，入力パケットが２入力命令か１入力命令かを示す１ビ
ットのＦＣ処理選択ビット及び演算順に応じて演算場所
（ノード）の左または右に配置することを示す１ビット
の左右データ選択ビットを含み、各種選択を行う７ビッ
トのセレクションコードＳＣと、入力データの入力順等
の属性を示す９ビットのカラー／世代識別番号ＤＮと、
演算が行われるべき場所を示す２１ビットのノード番号
ＮＮの合計６２ビットから構成され、プロセッサ選択ビ
ットＰＳとカラー／世代識別番号ＤＮとノード番号ＮＮ
とから３１ビットの識別子が構成されている。但し、プ
ロセッサ選択ビットＰＳが“１”の場合、入力パケット
は処理後に出力されて他のプロセッサに送られるため、
ノード番号ＮＮの上位９ビットにプロセッサ番号が格納
されるようになっている。

【０００８】図１５に示すハッシュメモリ６０１は、ノ
ード番号ＮＮの下位９ビットをハッシュアドレスとして
アクセスされるものであり、リード／ライトサイクルを
定めるリード／ライト信号Ｗ／バーＲ・Ｈ、書き込みデ
ータ及び各アドレスの有効／無効の区別を示すプレゼン
スビットＰＢの更新を行うセット／リセット信号Ｓ／バ
ーＲが与えられる。

【０００９】このハッシュメモリ６０１に格納される書
き込みデータは１８ビットのオペランドデータＯＤと、
９ビットのカラー／世代識別番号ＤＮ及びノード番号Ｎ
Ｎの残り１２ビットの計２１ビットの識別子と、１ビッ
トのプロセッサ選択ビットＰＳの合計４０ビットからな
っている。また、これとは別に、１ビットのプレゼンス
ビットＰＢが格納されるようになっており、合計で１ワ
ード４１ビット構成となっている。また、そのアドレス
空間は２９＝５１２となっており、ハッシュメモリ６０
１は４１ビット／ワード×５１２の大きさを有している
。

【００１０】

【発明が解決しようとする課題】従来のデータ駆動形計
算機は以上のように構成され、発火処理部の待ち合わせ
メモリ内に納まり切れなかったパケットは、巡回パイプ
ライン構成のループ内を無為に周回することで待ち合わ
せメモリに空きができるのを待っていた。この様なオー
バーフローパケットがループ内を周回するとパイプライ
ンが混雑する。また、オーバーフローパケット同志では
発火できないのでデッドロック，すなわち実行停止の虞
があった。また、ハッシュメモリ６０１を用いた場合、
ハッシュしたアドレス（ハッシュアドレス）をアクセス
した時に同一アドレスでの衝突，いわゆるハッシュ衝突
が起こる虞れがある。すなわち、ハッシュ衝突とは、識
別子の一部をハッシュアドレスとした場合に、ハッシュ
アドレスが既にハッシュメモリ６０１内に格納されたデ
ータと一致しても、残りの識別子が一致しないデータが
アクセスされたとき、そのデータを記憶したアドレスが
既に占有されているために起こるものである。

【００１１】ここで、ハッシュメモリ６０１を図１３の
待ち合わせメモリ８５に適用したデータ駆動形計算機に
おいて、図１６の（ａ）に示すデータフローグラフを実
行する場合について考察する。なお、説明を簡単にする
ために、ハッシュメモリ６０１はノード番号の下位２ビ
ットをハッシュアドレスとしてアクセスされ、４つのパ
ケットを格納するだけの容量（アドレス空間＝２２＝４
）を持つものとして説明する。

【００１２】まず、図１６の（ａ）に示すように、この
データフローではノード数＝８で構成され、６つの入力
パケットを演算処理するようになっているが、ここでは
特に、番号０のノードの左入力となる第２パケットが番
号７のノードの左入力にもなっている。ハッシュメモリ
６０１をアクセスするメモリアドレスは４メモリアドレ
スとなり、図１６の（ａ）のデータフローグラフのノー
ド番号とメモリアドレスとは同図の（ｂ）に示すような
対応関係となる。このとき、図１６の（ａ）において、
番号３（“０１１”）のノードの左入力となる第１パケ
ットと番号７（“１１１”）のノードの左入力となる第
２パケットとは、ノード番号の下位２ビットが同じ値（
“１１”）であるので、ハッシュメモリ６０１の同一メ
モリアドレス「３（“１１”）」を指すことになる。

【００１３】データ駆動形計算機の場合、一般にデータ
の到着順によらず同一の結果を得られることが保証され
ている。ところが、ハッシュメモリの容量が小さいとき
は次のような問題が起こる。すなわち、第２パケットが
第１パケットよりも先にハッシュメモリ６０１に格納さ
れた場合、第２パケットは番号７のノードの右入力とな
る第３パケットを待つことになるが、第３パケットは番
号３，５及び６のノードが実行されないと生成されない
。しかし、第２パケットが第１パケットより先にハッシ
ュメモリ６０１に格納されてしまっているので、第２パ
ケットは待ち合わせの相手である第３パケットが何時ま
で経っても現れないことになる。このため、第２パケッ
トがハッシュメモリ６０１内に格納されたままになり、
第１パケットと第２パケットがハッシュ衝突を引き起こ
した状態となる。この結果、第１パケットはハッシュメ
モリ６０１に格納されなくなり、従って、番号３のノー
ドの演算は永久に実行されず、結局、演算処理が停止し
てしまうことになる。

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

【００１５】本発明の目的は、オーバーフローパケット
によるパイプラインの不要な混雑を避けることができ、
オーバーフローパケットによる混雑やハッシュ衝突に起
因する実行停止を回避することができるデータ駆動形計
算機を得ることにある。

【００１６】

【課題を解決するための手段】本発明は、少なくとも次
に実行すべき命令の場所を示す行き先ノード番号を含む
識別情報及びデータを有するパケットを格納する待ち合
わせメモリを備え、この待ち合わせメモリに格納された
パケットと新たに入力されたパケットとの少なくとも行
き先ノード番号が一致するパケットを検出し、一致した
パケットを合体する発火処理を行う発火処理部を有する
巡回パイプライン構成のデータ駆動形計算機において、
前記待ち合わせメモリに格納すべきパケットが格納でき
ずに出力された場合に当該パケットを一時格納するメモ
リを備え、このメモリに既に格納されているパケットと
新たに入力されたパケットとを比較し、少なくとも行き
先ノード番号が一致するパケットがあれば、これらを合
体して出力し、合体できなかったパケットについては所
定の条件に基づき前記発火処理部に転送する第２の発火
処理部を設けたものである。

【００１７】

【作用】上記構成によれば、従来からある第１の発火処
理部の待ち合わせメモリにてオーバーフローしたパケッ
トは、新たに設けられた第２の発火処理部に送出され、
第２の発火処理部では、受け取ったパケットと、既に受
け取りメモリに格納しているパケットとの比較を行なう
。比較の結果、一致したならば発火し合体して出力し、
発火しなければメモリ内に格納する。また、第２の発火
処理部のメモリに格納されているパケットは、発火する
ことが無くともある条件となると（例えば格納されてか
ら一定時間経過すると）、読み出され再び第１の発火処
理部に送出される。このように、自動読み出し再処理機
能を備えた第２の発火処理部を設けることにより、第１
の発火処理部のオーバーフローによるパイプラインの混
雑やデッドロック（実行停止）を防止する。

【００１８】自動的に読み出しを行なう理由は以下の通
りである。発火すべきパケットＡ，Ａ’が有り、先に第
１の発火処理部に到着したパケットＡは待ち合わせメモ
リ内でハッシュ衝突を起こした。故にパケットＡは第２
の発火処理部のメモリに格納される。この後、パケット
Ａがハッシュ衝突を起こしたパケットは発火して読み出
され、その後にパケットＡ’が第１の発火処理部に到着
すると、パケットＡ’はその待ち合わせメモリに格納さ
れる。この状態では、パケットＡとＡ’は永久に発火で
きない（デッドロックに陥る）。そのため、例えば定期
的に第２の発火処理部のメモリに格納されているパケッ
トを第１の発火処理部に送り出し再処理を行なうことで
、パケットＡとＡ’の発火が可能となり、デッドロック
が回避できる。

【００１９】

【実施例】以下、この発明の一実施例を図を参照して説
明する。図１は本発明を適用したデータ駆動形計算機の
一実施例を示すブロック図であり、発火処理部１０１、
演算処理部１０２、プログラム記憶部１０３、合流制御
部１０４及び１０５、拡張発火処理器（第２の発火処理
部）１０６とから構成されている。発火処理部１０１は
図１３で示した発火処理部８７と同様な構成であり、ハ
ッシュ衝突が原因でこの発火処理部１０１に格納できな
かったパケットはオーバフローパケット転送路１０７を
通じて拡張発火処理器１０６に転送される。そして、こ
の拡張発火処理器１０６内のメモリに一時格納される。 この際に、既に当該メモリに格納されているパケットと
比較され、少なくとも行き先ノード番号が一致するパケ
ットがあれば、これと合体して外部発火パケット転送路
１０９及び合流制御部１０４を通じて演算処理部１０２
に入力される。そして、その演算結果は、プログラム記
憶部１０３で識別子が更新されて合流制御部１０５を通
じて発火処理部１０１に再度入力される。しかし、拡張
発火処理器１０６内で発火できなかったパケットは、こ
の拡張発火処理器１０６内のメモリに一時格納され、新
たなパケットが入力されるまで検索待ちとなる。そして
、何回も検索したにも拘わらず発火できない状態を防止
するために、定期的に読み出され、再処理パケットとし
て再処理パケット転送路１０８及び合流制御部１０５を
通じて発火処理部１０１に転送され、この発火処理部１
０１内の待ち合わせメモリに発火可能なパケットがある
かどうかが検索される。

【００２０】図２は拡張発火処理器１０６の詳細構成を
示すブロック図である。図において、２０１は発火処理
部１０１でハッシュ衝突が原因で発火できず転送路１０
７を介して送られてきたオーバフローパケット、２０２
は識別子ＴＡＧの一部ビットで示されるアドレスを圧縮
してハッシュアドレスを生成するハッシュ処理器（ＨＡ
ＳＨ）、２０３は後述のアドレス変換テーブル２０６を
検索するためのアドレスを生成する読み出しアドレスジ
ェネレータ（ＡＧ）、２０４はアドレス変換テーブル検
索キーセレクタ、２０５はアドレス変換テーブル書き込
みデータセレクタ、２０６はアドレス変換テーブル（Ｃ
Ｔ）、２０７はパケットを格納するアドレスを指定する
書き込みアドレスポインタ（ＡＰ）、２０８は１つ前に
読み出しを行ったアドレスを記憶するチェイン書き換え
レジスタ（ＣＣＲ）、２０９は最後に読み出しを行った
アドレスを記憶した読み出しアドレスレジスタ（ＲＲ）
、２１０はアドレスセレクタ、２１１は入力されたパケ
ットを格納するパケットメモリ、２１２はパケットメモ
リ２１１の連鎖関係を記憶するチェインポインタメモリ
、２１３はチェインアドレスＣＡを記憶するチェインア
ドレスレジスタ（ＣＡＲ）、２１４はチェインビットＣ
Ｂを記憶するチェインビットレジスタ（ＣＢＲ）、２１
５はチェインポインタの書き込みデータを選択するチェ
インポインタ書き込みセレクタ、２１６は入力されたオ
ーバーフローパケット２０１のＴＡＧとパケットメモリ
２１１から読み出したＴＡＧを比較する比較器、２１７
は全体動作を制御する制御部である。なお、すべてのレ
ジスタはメモリの読み出し時に更新される。また、ハッ
シュ処理器２０２のハッシュ関数と発火処理部１０１の
ハッシュ関数は異なるものに設定されている。

【００２１】アドレス変換テーブル２０６の構成は、図
３に示すように、テーブル検索キーで指定し得る複数の
領域から構成され、パケットメモリ２１１におけるパケ
ットの格納アドレスを示すパケット格納アドレスＰＡを
記憶するパケット格納アドレス部２２３と、有効なパケ
ット格納アドレスＰＡが記憶されている時はＰＢ＝１，
記憶されていなければＰＢ＝０のプレゼンスビットＰＢ
を記憶するプレゼンスビット部２２２とからなり、ハッ
シュ生成器２０２から出力されるハッシュアドレスまた
はアドレスジェネレータ２０３から出力される読み出し
アドレスをテーブル検索キーとしてアクセスされ、この
検索キーが検索を行うべきパケットメモリ２１１のアド
レスに変換される。図３においては、テーブル検索キー
で検索されるパケットはパケットメモリ２１１のアドレ
スｎ１に格納されていることを示している。

【００２２】パケットメモリ２１１及びチェインポイン
タメモリ２１２の構成は、図４に示すように、パケット
格納アドレスＰＡで指定し得る複数の領域から構成され
、パケットメモリ２１１は識別子ＴＡＧを記憶するタグ
部２１８とデータＤＡＴＡを記憶するデータ部２１９と
からなり、またチェインポインタメモリ２１２はチェイ
ンビットＣＢを記憶するチェインビット部２２０とチェ
インアドレスＣＡを記憶するチェインアドレス部２２１
とからなっている。例えば、パケット格納アドレスＰＡ
によってアドレスｎ１がアクセスされたとすると、この
アドレスｎ１に格納されている識別子ＴＡＧ＝Ｔ１，デ
ータＤＡＴＡ＝Ｄ１とからなるパケットがパケットメモ
リ２１１から読み出され、チェインビットＣＢ＝１とチ
ェインアドレスＣＡ＝ｎ１１がチェインポインタメモリ
２１２から読み出される。

【００２３】チェインビットＣＢ＝１は識別子Ｔ１と同
一のハッシュアドレスとなるパケットが他に存在するこ
とを示し、チェインアドレスＣＡはそのパケットが格納
されているアドレスを示すもので、ＣＢ＝０の場合は同
一のハッシュアドレスとなるパケットがこれ以上存在し
ないことを示している。例えば、図４の例では、パケッ
ト格納アドレスＰＡがｎ１，ｎ１１，ｎ１３であるパケ
ットメモリ２１１のアドレスには、同一のハッシュアド
レスとなるパケットが格納されていることを表している
。

【００２４】次に、以上の構成に係る動作について図５
の発火処理のフローチャート及び図６の再処理読出しの
フローチャートを参照して説明する。図５において、（
１），（２）を付した各処理の細かい内容は図７〜図１
２に示す。なお、パケットの発火処理と再処理読出しは
排他的に行われ、再処理読出しにおいては１つのハッシ
ュアドレスに関して連鎖するパケット格納アドレスの最
終アドレスまで連続してアクセスされ、途中で中断する
ときは中断した時のパケット格納アドレスをアドレス変
換テーブル２０６に格納しておくようになっている。 この場合、再処理読出しを開始するタイミングは、発火
処理部１０１から送られて来るオーバフローパケットが
途絶えた時、あるいは所定時間ごとに１ハッシュアドレ
ス分のパケットを必ず送出するように設定されている。

【００２５】まず、図５の発火処理において、転送路１
０７からオーバフローパケット２０１が入力されると、
制御部２１７はアドレス変換テーブル検索キーセレクタ
２０４をハッシュ処理器２０２側へ切り換え、このハッ
シュ処理器２０２においてオーバフローパケット２０１
の識別子ＴＡＧを圧縮することによって生成されたハッ
シュアドレスによりアドレス変換テーブル２０６を検索
する（ステップＳ１）。この結果、ハッシュアドレスで
示されるアドレス変換テーブル２０６におけるアドレス
のプレゼンスビットＰＢが“０”であったならば（ステ
ップＳ２）、パケットは格納されていないことになるの
で、この時入力されたパケットを書き込みアドレスポイ
ンタ２０７によって指示されているパケットメモリ２１
１のアドレスに格納すると共に、変換テーブル２０６の
プレゼンスビットＰＢを“１”に書き換える（ステップ
Ｓ３，詳細は図７を参照）。

【００２６】ステップＳ２において、ハッシュアドレス
で示されるテーブルアドレスのプレゼンスビットＰＢが
“１”であったならば、制御部２１７はセレクタ２１０
をアドレス変換テーブル２０６の出力側に切り換え、Ｐ
Ｂ＝１となっているテーブルアドレスから読み出されて
いるパケット格納アドレスＰＡをセレクタ２１０を通じ
てパケットメモリ２１１の検索アドレスとして入力し、
該パケット格納アドレスＰＡで示されるアドレスに格納
されているパケットを読み出す（ステップＳ４，図８を
参照）。

【００２７】パケットメモリ２１１から読み出されたパ
ケットの識別子ＴＡＧは比較器２１６に入力され、ここ
で入力れたオーバフローパケット２０１の識別子ＴＡＧ
と比較され、この結果、識別子ＴＡＧが一致したならば
（ステップＳ５）、発火処理が行なわれるとともにアド
レスがクリアされる（ステップＳ６，図９を参照）。こ
れらのパケットは発火パケット２２４として合体され、
転送路１０９及び合流制御部１０４を通じて演算処理部
１０２に転送される。

【００２８】ステップＳ５において、パケットメモリ２
１１から読み出したパケットとオーバフローパケット２
０１の識別子ＴＡＧが一致していなかった場合は、チェ
インポインタメモリ２１２から読み出されてチェインビ
ットレジスタ（ＣＢＲ）２１４に格納されているチェイ
ンビットＣＢが“０”か“１”かによって他に同一ハッ
シュアドレスとなるパケットが存在するか否かを調べ（
ステップＳ７）、ＣＢ＝０ならばオーバフローパケット
２０１をパケットメモリ２１１に格納する（ステップＳ
８，図１０を参照）。一方、ＣＢ＝１ならば、他に同一
ハッシュアドレスとなるパケットが存在することになる
ので、チェインアドレスレジスタ（ＣＡＲ）２１３に格
納されているチェインアドレスＣＡに従ってパケットメ
モリ２１１を検索する（ステップＳ９，図１１を参照）
。これは、チェインポイタメモリ２１２から読み出され
、チェインアドレスレジスタ（ＣＡＲ）２１３にセット
されているチェインアドレスＣＡをセレクタ２１０を通
じてパケットメモリ２１１のアドレスとして入力するこ
とにより行う。これにより、チェインアドレスＣＡで示
されるアドレスから先に読み出したパケットと同一ハッ
シュアドレスとなるパケットが読み出される。このパケ
ットの識別子ＴＡＧは、先のパケットと同様にして比較
器２１６に入力され、ここでオーバフローパケット２０
１と比較される。この結果、識別子ＴＡＧが一致したな
らば（ステップＳ１０）、発火処理が行なわれるととも
にアドレスがクリアされる（ステップＳ１１，図１２を
参照）。これらのパケットは発火パケット２２４として
合体され、転送路１０９及び合流制御部１０４を通じて
演算処理部１０２に転送される。しかし、識別子ＴＡＧ
が一致しない場合、ステップＳ７に戻り、このステップ
Ｓ７以降の処理が繰り返される。

【００２９】次に、図６の再処理読出しについて説明す
る。まず、図６の再処理読出しが起動されると、制御部
２１７はアドレス変換テーブル検索キーセレクタ２０４
を読出しアドレスジェネレータ２０３側へ切り換え、こ
のアドレスジェネレータ２０３から出力されるアドレス
によりアドレス変換テーブル２０６の全アドレスをスキ
ャンすることによってパケットの格納アドレスを検索す
る（ステップＳ２０）。この結果、アドレス変換テーブ
ル２０６における全てのアドレスのプレゼンスビットＰ
Ｂが“０”であったならば、どのアドレスにも有効なパ
ケットは格納されていないことになるので、再処理読出
しを終了する。

【００３０】しかし、いずれかのアドレスのプレゼンス
ビットＰＢが“１”であったならば、制御部２１７はセ
レクタ２１０をアドレス変換テーブル２０６の出力側に
切り換える。ステップＳ２２において、この時のテーブ
ルアドレスより読み出されているパケット格納アドレス
ＰＡをセレクタ２１０を通じてパケットメモリ２１１，
チェインポインタメモリ２１２の検索アドレスとして入
力し、該パケット格納アドレスＰＡで示されるアドレス
に格納されているパケットを読み出す。そして、このパ
ケットを再処理パケット２２５として転送路１０８及び
合流制御部１０５を通じて発火処理部１０１に転送する
（ステップＳ２３）。これによって、再処理読出しされ
たパケットは、拡張発火処理器１０６において発火でき
なくても発火処理部１０１において発火するための機会
が与えられる。ステップ２４，２５では、再処理読み出
しされたパケットのアドレスクリア処理が行なわれる。

【００３１】次に、チェインポインタメモリ２１２にお
けるチェインビットＣＢによって連鎖関係のパケットが
存在するかどうかを調べ（ステップＳ２６）、ＣＢ＝１
の場合はチェインアドレスＣＡで示されるパケットメモ
リ２１１のアドレスに格納されているパケットを読み出
し（ステップＳ２７）、再処理パケット２２５として出
力する。これは、連鎖関係のパケットが全て読み出され
るまで繰り返し行われる。ステップＳ２６においてＣＢ
＝０の場合には、パケットメモリ２１１に格納されてい
た、アドレス変換テーブル２０６の該テーブルアドレス
のＰＡにより示され、あるいは連鎖により結ばれた全て
のパケットの再処理読み出しが完了したことを示す。こ
の時には、アドレス変換テーブル２０６で、該テーブル
アドレスのプレゼンスビットＰＢを“０”に書き換える
（ステップＳ２８）。

【００３２】したがって、この実施例によれば、発火処
理部１０１内蔵の待ち合わせメモリに格納されなかった
パケットは拡張発火処理器１０６内蔵のパケットメモリ
２１１に一時格納されるが、この際に、既に格納されて
いるパケットと比較され、少なくとも識別子ＴＡＧが一
致するパケットがあれば、これと合体して演算処理部１
０２に出力される。しかし、合体できなかった場合は一
時格納され、新たなパケットが入力されるまで検索待ち
となる。そして、何回も検索したにも拘わらず合体でき
ない状態を防止するために、再処理読出しによって定期
的に読み出されて発火処理部１０１に転送され、発火処
理部１０１において合体可能なパケットがあれば、これ
と合体されて演算処理部１０２に出力される。

【００３３】このようにした結果、オーバーフローパケ
ットによるパイプラインの不要な混雑を避けることがで
き、オーバーフローパケットによる混雑やハッシュ衝突
に起因するデッドロック，すなわち実行停止を回避する
ことができる。拡張発火処理器１０６は、少量のロジッ
クと、あとは通常のＤＲＡＭやＳＲＡＭで構成可能であ
り、リーズナブルである。

【００３４】

【発明の効果】以上説明したように、本発明では、従来
からの発火処理部の待ち合わせメモリに格納すべきパケ
ットが格納できずに出力された場合に当該パケットを一
時格納するメモリを備え、このメモリに既に格納されて
いるパケットと新たに入力されたパケットとを比較し、
少なくとも行き先ノード番号が一致するパケットがあれ
ば、これらを合体して出力し、合体できなかったパケッ
トについては所定の条件に基づき前記発火処理部に転送
する第２の発火処理部を設けたことので、オーバーフロ
ーパケットによるパイプラインの不要な混雑を避けるこ
とができ、オーバーフローパケットによる混雑やハッシ
ュ衝突に起因する実行停止を回避することができるとい
った効果がある。

【図面の簡単な説明】

【図１】この発明に係るデータ駆動形計算機の全体構成
図である。

【図２】この発明の主要部である拡張発火処理器の詳細
構成図である。

【図３】図２におけるアドレス変換テーブルの構成説明
図である。

【図４】図２におけるパケットメモリとチェインポイタ
メモリの構成説明図である。

【図５】この発明の主要部である拡張発火処理器の発火
処理を示すフローチャートである。

【図６】この発明の主要部である拡張発火処理器の再処
理読出しを示すフローチャートである。

【図７】図５のパケット格納（１）の詳細を示すフロー
チャートである。

【図８】図５のパケット検索（１）の詳細を示すフロー
チャートである。

【図９】図５のアドレスクリア（１）の詳細を示すフロ
ーチャートである。

【図１０】図５のパケット格納（２）の詳細を示すフロ
ーチャートである。

【図１１】図５のパケット検索（２）の詳細を示すフロ
ーチャートである。

【図１２】図５のアドレスクリア（２）の詳細を示すフ
ローチャートである。

【図１３】従来のデータ駆動形計算機のデータ処理の概
念を示す説明図である。

【図１４】パケットの一例の構成を示すビットマップ図
である。

【図１５】ハッシュメモリの一例の構成を示すブロック
図である。

【図１６】データフローグラフの一例とメモリアドレス
及びノード番号との関係を示す説明図である。

【符号の説明】

１０１　　発火処理部 １０２　　演算処理部 １０３　　プログラム記憶部 １０４，１０５　　合流制御部 １０６　　拡張発火処理器（第２の発火処理部）１０７
　　オーバフローパケット転送路１０８　　再処理パケ
ット転送路 １０９　　外部発火パケット転送路 ２０１　　オーバフローパケット ２０２　　ハッシュ処理器 ２０６　　アドレス変換テーブル ２１１　　パケットメモリ ２１２　　チェインポインタメモリ ２１６　　比較器 ２１７　　制御部 ２２４　　発火パケット ２２５　　再処理パケット

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　少なくとも次に実行すべき命令の場所
   を示す行き先ノード番号を含む識別情報及びデータを有
   するパケットを格納する待ち合わせメモリを備え、この
   待ち合わせメモリに格納されたパケットと新たに入力さ
   れたパケットとの少なくとも行き先ノード番号が一致す
   るパケットを検出し、一致したパケットを合体する発火
   処理を行う発火処理部を有する巡回パイプライン構成の
   データ駆動形計算機において、前記待ち合わせメモリに
   格納すべきパケットが格納できずに出力された場合に当
   該パケットを一時格納するメモリを備え、このメモリに
   既に格納されているパケットと新たに入力されたパケッ
   トとを比較し、少なくとも行き先ノード番号が一致する
   パケットがあれば、これらを合体して出力し、合体でき
   なかったパケットについては所定の条件に基づき前記発
   火処理部に転送する第２の発火処理部を設けたことを特
   徴とするデータ駆動形計算機。