JPH0528290A

JPH0528290A - データ駆動形計算機

Info

Publication number: JPH0528290A
Application number: JP20403291A
Authority: JP
Inventors: Hisakazu Sato; 尚和佐藤
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1991-07-18
Filing date: 1991-07-18
Publication date: 1993-02-05

Abstract

(57)【要約】【目的】オーバーフローパケットによる巡回パイプラ
インの不要な混雑を避けることができ、オーバーフロー
パケットによる混雑やハッシュ衝突に起因する実行停止
を回避することができるデータ駆動形計算機を得る。【構成】待ち合わせメモリとしてハッシュメモリを有
し、このハッシュメモリの各アドレスに当該ハッシュア
ドレスでハッシュ衝突が生じオーバーフローパケットを
出力した時にセットするＯＶフラグを設けた発火処理部
１０１を備えるとともに、待ち合わせメモリとして前記
発火処理部１０１から出力されたオーバーフローパケッ
トを前記ハッシュメモリと同一のハッシュ関数で、かつ
チェイン接続を用いて格納するハッシュメモリを有する
拡張発火処理器１０６を備える。パケットは発火処理部
１０１か拡張発火処理器１０６の何れかに格納され、Ｏ
Ｖフラグがセットされているアドレスに関しては発火処
理部１０１と拡張発火処理器１０６の両方をアクセスす
る。

Description

【発明の詳細な説明】

【０００１】

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

【０００２】

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

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

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

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

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

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

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

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

【００１０】

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

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

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

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

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

【００１５】そこで、本出願人はこのような問題を解決
する手段の１つとして、ハッシュメモリを用いた待ち合
わせメモリの他に、ハッシュメモリと同時にアクセスさ
れる小容量（３２ワード）の連想メモリを設け、ハッシ
ュ衝突で待ち合わせメモリに格納しえなかったパケット
については連想メモリに格納し、ここで待ち合わせを行
うようにしたものを既に提案している。しかし、この連
想メモリを設ける構成においては、連想メモリの容量以
上のハッシュ衝突がおこると、上述したような問題と同
様の問題が起こる。これは、連想メモリの容量を大きく
することにより解決することが可能であるが、ハードウ
ェアとしての構成が大規模になるばかりか、行き先ノー
ド番号が一致するパケットを検索する際に、常に全ての
アドレスを検索することになるので、全体のパイプライ
ン処理速度が著しく低下するという問題を引き起こす。

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

【００１７】

【課題を解決するための手段】本発明は、少なくとも次
に実行すべき命令の場所を示す行き先ノード番号を含む
識別情報及びデータを有するパケットを格納する待ち合
わせメモリを備え、この待ち合わせメモリに格納された
パケットと新たに入力されたパケットとの少なくとも行
き先ノード番号が一致するパケットを検出し、一致した
パケットを合体する発火処理を行う発火処理部を有する
巡回パイプライン構成のデータ駆動形計算機において、
前記待ち合わせメモリとしてハッシュメモリを有し、こ
のハッシュメモリの各アドレスに当該ハッシュアドレス
でハッシュ衝突が生じオーバーフローパケットを出力し
た時にセットするＯＶフラグを設けた第１の発火処理部
を備えるとともに、待ち合わせメモリとして前記第１の
発火処理部から出力されたオーバーフローパケットを前
記ハッシュメモリと同一のハッシュ関数で、かつチェイ
ン接続を用いて格納するハッシュメモリを有する第２の
発火処理部を備え、前記第１の発火処理部は、ハッシュ
衝突により生じたオーバーフローパケットを第２の発火
処理部に出力するとともに、ハッシュ衝突を起こしたア
ドレスのＯＶフラグをセットし、以降，ＯＶフラグがセ
ットされたハッシュアドレスで発火しないパケットは第
２の発火処理部に出力し、前記第２の発火処理部は、ハ
ッシュメモリに既に格納されているパケットと新たに入
力されたパケットとを比較し、少なくとも行き先ノード
番号が一致するパケットがあれば発火処理を行なうとと
もに、当該パケットが該ハッシュアドレスよりチェイン
に接続されている唯一のパケットの時は当該発火パケッ
トにその旨を示すために付加されたＯＶＣフラグをセッ
トして第１の発火処理部へ出力し、前記第１の発火処理
部は、入力された発火パケットのＯＶＣフラグがセット
されている時は当該ハッシュアドレスのＯＶフラグをク
リアするようにしたものである。

【００１８】

【作用】本発明においては、従来からある第１の発火処
理部をオーバーフローしたパケットは新たに設けられた
第２の発火処理部に送り、ここで発火処理を行なう。そ
の際、オーバーフローしたハッシュアドレスのＯＶフラ
グをセットし、以降，第１の発火処理部に与えられたパ
ケットは、ＯＶフラグのセットされたハッシュアドレス
となるパケットのみ第１の発火処理部と第２の発火処理
部の両方でマッチングを行なう。ＯＶフラグは、第２の
発火処理部の該当ハッシュアドレスに対応するチェイン
接続されたパケットが全て発火し出力された場合に、Ｏ
ＶＣフラグがセットされた発火パケットによりクリアさ
れる。このように、オーバーフローパケットを受け入れ
る第２の発火処理部を設け、一度オーバーフローが起こ
ったら両方の発火処理部をアクセスすることにより、オ
ーバーフローによるパイプラインの混雑やデッドロック
（実行停止）を防止することができる。

【００１９】

【実施例】以下、この発明の一実施例を図を参照して説
明する。図１は本発明を適用したデータ駆動形計算機の
一実施例を示すブロック図であり、発火処理部（第１の
発火処理部）１０１、演算処理部１０２、プログラム記
憶部１０３、分岐制御部１０４、合流制御部１０５、拡
張発火処理器（第２の発火処理部）１０６とから構成さ
れている。上記発火処理部１０１は、待ち合わせメモリ
としてハッシュメモリを有し、このハッシュメモリの各
アドレスに当該ハッシュアドレスでハッシュ衝突が生じ
オーバーフローパケットを出力した時にセットするＯＶ
フラグを設けたものであり、ハッシュ衝突が原因で生じ
たオーバーフローパケットには拡張発火処理器１０６へ
送出することを示すＥＸフラグを“１”にセットして出
力するとともに、ハッシュ衝突を起こしたアドレスのＯ
Ｖフラグをセットする。また、ＯＶフラグがセットされ
ているハッシュアドレスが発火して空になり新たなパケ
ットが格納された時は、当該パケットにその旨を示すた
めに付加されたＮＳフラグを“１”にセットし、かつ上
記ＥＸフラグもセットして出力する。発火処理部１０１
から巡回パイプライン上に出力されたパケットは分岐制
御部１０４に入力される。分岐制御部１０４では、パケ
ットに付加されたＥＸフラグに基づき、ＥＸフラグがセ
ットされていない時（ＥＸ＝０）は従来同様，データと
タグ（識別子）からなるパケットを演算処理部１０２に
送るが、ＥＸフラグがセットされている時（ＥＸ＝１）
はデータ，タグ及びＮＳフラグからなるパケットを拡張
発火処理器１０６に分岐させる。

【００２０】拡張発火処理器１０６は、待ち合わせメモ
リとして上記オーバーフローパケットを発火処理部１０
１のハッシュメモリと同一のハッシュ関数で、かつチェ
イン接続を用いて格納するハッシュメモリを有し、この
ハッシュメモリに既に格納されているパケットと新たに
入力されたパケットとを比較する。そして、少なくとも
行き先ノード番号が一致するパケットがあれば発火処理
を行い発火パケットとして出力するが、相手パケットが
該ハッシュアドレスよりチェインに接続されている唯一
のパケットの時は当該発火パケットにその旨を示すため
に付加されたＯＶＣフラグをセットして出力し、ＮＳフ
ラグがセットされたパケットの時は当該発火パケットに
その旨を示すために付加されたＰＫＣフラグをセットし
て出力する。また、オーバーフローパケットが発火しな
かった場合には格納されるが、ＮＳフラグがセットされ
た入力パケット（発火処理部１０１に既に格納されたパ
ケット）が発火しなかった時は、発火処理部１０１と拡
張発火処理器１０６の両方に格納されるのを防ぐため当
該パケットを消去する。

【００２１】拡張発火処理器１０６から出力された発火
パケットは、合流制御部１０５を介して発火処理部１０
１に入力される。発火処理部１０１では、入力された発
火パケットを素通りさせるが、ＰＫＣフラグがセットさ
れている時は当該ハッシュアドレスに格納されたパケッ
トをクリアし、ＯＶＣフラグがセットされている時は当
該ハッシュアドレスのＯＶフラグをクリアする。なお、
発火処理部１０１から出力される発火パケットは分岐制
御部１０４を介して演算処理部１０２に入力され、その
演算結果は、プログラム記憶部１０３でタグが更新され
て合流制御部１０５を通じて発火処理部１０１に再度入
力される。

【００２２】図２は発火処理部１０１のブロック構成図
であり、これはハッシュメモリの他に連想メモリを備え
た，既に本出願人が提案済みのもの（特願平３−１２２
３３８号等）に本発明を適用した概略構成を示すもので
あるが、ハッシュメモリのみのものにも適用できること
はもちろんである。図示のように、この発火処理部１０
１は、ハッシュメモリ１，連想メモリ２，ハッシュ処理
器３，比較器４，制御部５，セレクタ６，オペランド交
換器７等から構成され、上述した先の出願のものとほぼ
同様なものであるが、上述した機能を実現するために若
干の機能拡張が必要となる。拡張内容は、ハッシュメモ
リ１の各アドレスに上述したＯＶフラグを格納するフィ
ールドを追加し、新たに上述したＰＫＣ，ＯＶＣ，Ｎ
Ｓ，ＥＸの４つの信号を付加したことである。これによ
って制御部５の動作が多少複雑化している。図３にハッ
シュメモリ格納データフィールドを示し、図４に制御部
５の制御内容を示す。

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

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

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

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

【００２７】次に、図８のフローチャートを参照して上
記拡張発火処理器１０６の概略動作について説明する。
まず、ステップＳ１で入力パケット２０１のＮＳフラグ
が“１”にセットされているか否か，すなわち発火処理
部１０１に既に格納されたパケットであるかオーバーフ
ローパケットであるかを判定する。オーバーフローパケ
ットの場合はＮＳフラグがセットされておらず“０”で
あるので、ステップＳ２に進んで発火したか否かを判定
し、発火しなければ格納される（ステップＳ３）。ステ
ップＳ２の判定で発火しておれば、ステップＳ４に進ん
で発火の相手パケットが該ハッシュアドレスよりチェイ
ンに接続されている唯一のパケットであるか否かが判定
される。唯一のパケットでなければ、ＯＶＣフラグ，Ｐ
ＫＣフラグともセットせずに（ＯＶＣ＝０，ＰＫＣ＝
０）、発火パケット２２４として出力する（ステップＳ
５）。また、唯一のパケットであれば、ＯＶＣフラグの
みをセットして（ＯＶＣ＝１，ＰＫＣ＝０）、発火パケ
ット２２４として出力する（ステップＳ６）。一方、入
力パケット２０１が発火処理部１０１に既に格納済みの
パケットの場合はＮＳフラグがセットされており“１”
であるので、ステップＳ１からステップＳ７に進んで発
火したか否かを判定し、発火しなければ重複して格納さ
れるのを防ぐため消去される（ステップＳ８）。ステッ
プＳ７の判定で発火しておれば、ステップＳ９に進んで
発火の相手パケットが該ハッシュアドレスよりチェイン
に接続されている唯一のパケットであるか否かが判定さ
れる。唯一のパケットでなければ、ＰＫＣフラグのみを
セットして（ＯＶＣ＝０，ＰＫＣ＝１）、発火パケット
２２４として出力する（ステップＳ１０）。また、唯一
のパケットであれば、ＯＶＣフラグ，ＰＫＣフラグとも
セットして（ＯＶＣ＝１，ＰＫＣ＝１）、発火パケット
２２４として出力する（ステップＳ１１）。

【００２８】次に、オーバーフローパケットを例にとっ
て、チェイン接続を用いたパケットの格納及び発火処理
の詳細について図９のフローチャートを参照して説明す
る。なお、発火処理部１０１に既に格納済みでＮＳフラ
グがセットされた入力パケットについても、発火しない
場合に消去される点を除けばほぼ同様である。また、図
９において、（１），（２）を付した各処理の細かい内
容は図１０〜図１５に示す。まず、入力パケット２０１
としてオーバーフローパケットが入力されると、ハッシ
ュ処理器２０２においてオーバーフローパケットのタグ
を圧縮することによってハッシュアドレスが生成され、
生成されたハッシュアドレスによりアドレス変換テーブ
ル２０６を検索する（ステップＳ１）。この結果、ハッ
シュアドレスで示されるアドレス変換テーブル２０６に
おけるアドレスのプレゼンスビットＰＢが“０”であっ
たならば（ステップＳ２）、パケットは格納されていな
いことになるので、この時入力されたパケットを書き込
みアドレスポインタ２０７によって指示されているパケ
ットメモリ２１１のアドレスに格納すると共に、変換テ
ーブル２０６のプレゼンスビットＰＢを“１”に書き換
える（ステップＳ３，詳細は図１０を参照）。

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

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

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

【００３２】以上述べたように、本実施例では、ハッシ
ュメモリを用いた発火処理部１０１においてオーバーフ
ローを起こした時、オーバーフローパケットを拡張発火
処理器１０６に送り、衝突を起こしたハッシュメモリの
ＯＶフラグをセットする。発火処理部１０１にて発火せ
ず，かつ当該ハッシュアドレスが空アドレスの場合で、
ＯＶフラグが“１”の時には、パケットは発火処理部１
０１内に格納されるが、更に拡張発火処理器１０６をも
アクセスする。発火処理部１０１では発火せず、拡張発
火処理器１０６で発火したならば、拡張発火処理器１０
６で発火したパケットは発火処理部１０１内を素通りし
ていく時に、発火処理部１０１内に格納済みのパケット
をクリアする。また、拡張発火処理器１０６で発火しな
かったならば、重複して格納されるのを防ぐため当該パ
ケットは拡張発火処理器１０６内で消滅させる。発火処
理部１０１内に空アドレスがなかった場合には当然格納
される。ＯＶフラグは、拡張発火処理器１０６の該当ハ
ッシュアドレスに対応するチェイン接続されたパケット
が全て発火し出力された場合に、ＯＶＣフラグがセット
された発火パケットによりクリアされる。つまり、パケ
ットは発火処理部１０１か拡張発火処理器１０６の何れ
かに格納され、ＯＶフラグがセットされているアドレス
に関しては発火処理部１０１と拡張発火処理器１０６の
両方をアクセスする。

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

【００３４】なお、上記実施例では、発火処理部１０１
において、ＯＶフラグがセットされているハッシュアド
レスが発火して空になり新たなパケットが格納された時
は、当該パケットにその旨を示すために付加されたＮＳ
フラグを“１”にセットして拡張発火処理器１０６に出
力するようにしたが、ＯＶフラグがセットされているハ
ッシュアドレスが発火して空になってもＯＶフラグがセ
ットされている間は、当該ハッシュアドレスに新たなパ
ケットが到来しても格納せずにオーバーフローパケット
して拡張発火処理器１０６に出力するようにしてもよ
く、この場合、拡張発火処理器１０６や発火処理部１０
１での該当パケットの消去，クリアは不要となり、それ
に関するＮＳフラグ及びＰＫＣフラグも不要となる。ま
た、上記実施例では、発火処理部１０１から全てのパケ
ットを巡回パイプライン上に出力し、分岐制御部１０４
でＥＸフラグに基づきオーバーフローパケット等は拡張
発火処理器１０６に分岐させるようにしたが、該当パケ
ットは発火処理部１０１から拡張発火処理器１０６に直
接送出するようにしてもよく、この場合、分岐制御部１
０４やＥＸフラグは不要となる。

【００３５】

【発明の効果】以上説明したように、本発明では、待ち
合わせメモリとしてハッシュメモリを有し、このハッシ
ュメモリの各アドレスに当該ハッシュアドレスでハッシ
ュ衝突が生じオーバーフローパケットを出力した時にセ
ットするＯＶフラグを設けた第１の発火処理部を備える
とともに、待ち合わせメモリとして前記第１の発火処理
部から出力されたオーバーフローパケットを前記ハッシ
ュメモリと同一のハッシュ関数で、かつチェイン接続を
用いて格納するハッシュメモリを有する第２の発火処理
部を備え、前記第１の発火処理部は、ハッシュ衝突によ
り生じたオーバーフローパケットを第２の発火処理部に
出力するとともに、ハッシュ衝突を起こしたアドレスの
ＯＶフラグをセットし、以降，ＯＶフラグがセットされ
たハッシュアドレスで発火しないパケットは第２の発火
処理部に出力し、前記第２の発火処理部は、ハッシュメ
モリに既に格納されているパケットと新たに入力された
パケットとを比較し、少なくとも行き先ノード番号が一
致するパケットがあれば発火処理を行なうとともに、当
該パケットが該ハッシュアドレスよりチェインに接続さ
れている唯一のパケットの時は当該発火パケットにその
旨を示すために付加されたＯＶＣフラグをセットして第
１の発火処理部へ出力し、前記第１の発火処理部は、入
力された発火パケットのＯＶＣフラグがセットされてい
る時は当該ハッシュアドレスのＯＶフラグをクリアする
ようにしたので、オーバーフローパケットによるパイプ
ラインの不要な混雑を避けることができ、オーバーフロ
ーパケットによる混雑やハッシュ衝突に起因する実行停
止を回避することができるといった効果がある。

【図面の簡単な説明】

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

【図２】図１の発火処理部の一実施例を示す構成図であ
る。

【図３】図２のハッシュメモリ格納データフィールドを
示す図である。

【図４】図２の制御部の制御内容を示す図である。

【図５】図１の拡張発火処理器の一実施例を示す詳細構
成図である。

【図６】図５のアドレス変換テーブルの構成説明図であ
る。

【図７】図５のパケットメモリとチェインポインタメモ
リの構成説明図である。

【図８】実施例の拡張発火処理器の全体動作を示すフロ
ーチャートである。

【図９】実施例の拡張発火処理器の詳細動作を示すフロ
ーチャートである。

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

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

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

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

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

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

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

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

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

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

【符号の説明】

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

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成４年６月４日

【手続補正１】

【補正対象書類名】図面

【補正対象項目名】図４

【補正方法】変更

【補正内容】

【図４】

Claims

【特許請求の範囲】【請求項１】少なくとも次に実行すべき命令の場所を
示す行き先ノード番号を含む識別情報及びデータを有す
るパケットを格納する待ち合わせメモリを備え、この待
ち合わせメモリに格納されたパケットと新たに入力され
たパケットとの少なくとも行き先ノード番号が一致する
パケットを検出し、一致したパケットを合体する発火処
理を行う発火処理部を有する巡回パイプライン構成のデ
ータ駆動形計算機において、前記待ち合わせメモリとしてハッシュメモリを有し、こ
のハッシュメモリの各アドレスに当該ハッシュアドレス
でハッシュ衝突が生じオーバーフローパケットを出力し
た時にセットするＯＶフラグを設けた第１の発火処理部
を備えるとともに、待ち合わせメモリとして前記第１の
発火処理部から出力されたオーバーフローパケットを前
記ハッシュメモリと同一のハッシュ関数で、かつチェイ
ン接続を用いて格納するハッシュメモリを有する第２の
発火処理部を備え、前記第１の発火処理部は、ハッシュ
衝突により生じたオーバーフローパケットを第２の発火
処理部に出力するとともに、ハッシュ衝突を起こしたア
ドレスのＯＶフラグをセットし、以降，ＯＶフラグがセ
ットされたハッシュアドレスで発火しないパケットは第
２の発火処理部に出力し、前記第２の発火処理部は、ハ
ッシュメモリに既に格納されているパケットと新たに入
力されたパケットとを比較し、少なくとも行き先ノード
番号が一致するパケットがあれば発火処理を行なうとと
もに、当該パケットが該ハッシュアドレスよりチェイン
に接続されている唯一のパケットの時は当該発火パケッ
トにその旨を示すために付加されたＯＶＣフラグをセッ
トして第１の発火処理部へ出力し、前記第１の発火処理
部は、入力された発火パケットのＯＶＣフラグがセット
されている時は当該ハッシュアドレスのＯＶフラグをク
リアすることを特徴とするデータ駆動形計算機。