JPH0650530B2 - 対データ検出回路 - Google Patents

Description

【発明の詳細な説明】 〈産業上の利用分野〉 本発明は、非ノイマン形のデータフローコンピュータの
対データ検出回路に関する。

〈従来の技術〉 最近の情報処理技術の飛躍的発展に伴って、画像情報な
ど多量のデータを高速処理する要請が強まるなかで、従
来の逐次制御方式のノイマン形コンピュータに代って、
プログラム中のどの複数の命令でもその入力データが揃
った時点で並列演算できるハードウェア構成になった非
ノイマン形のデータフローコンピュータが研究，開発さ
れ、実用に供せられつつある。

上記データフローコンピュータとして、例えば第５図に
示すようなものが知られている。このコンピュータは、
コンパイラで翻訳された多数のパケットからなるプログ
ラムを収納するプログラム記憶部２１と、対データ検出
回路２２と、複数の加算器や乗算器からなる演算処理部
２３を通信ネットワーク２４でループ状に結合してな
る。そして、プログラム記憶部２１に収納された各パケ
ット２５は、第６図に示すような構造をなし、そのデー
タフィールド２８，２９に演算処理部２３からの演算結
果データが書き込まれると、対データ検出回路２２に送
られ、ここで全てのデータフィールド２８，２９が揃う
までデータ待ちされる。データフィールドが揃うと、パ
ケットは、演算処理部２３の所定の演算器に送られて、
その命令フィールド２７に書かれた演算命令に従って演
算処理され、演算結果データは、そのパケットの行先フ
ィールド２６に書かれた次処理のパケット番号に従っ
て、通信ネットワーク２４を経てプログラム記憶部２１
の次処理のパケットに供給され、このパケットが次に実
行される。つまり、ループ状の通信ネットワーク２４に
は、データフィールド２８，２９の揃ったいくつものパ
ケットがパイプライン的に流れ、演算処理部２３で並列
処理されるのである。

ところで、出願人は、上記対データ検出回路２２におけ
る高速なデータマッチングを実現すべく、この回路内の
マッチングメモリへのアクセスをデータ線のビット幅を
拡大することなく密にできる第８図の如き対データ検出
回路２２を最近提案した（特願昭６２−２６５７３７
号）。この対データ検出回路２２は、パケット番号に対
応するアドレスにそのパケットデータを格納するマッチ
ングメモリ６と、入力ポートＡ，Ｂから入力されたパケ
ットのパケット番号に対応する上記マッチングメモリ６
のアドレスからパケットデータを読み出すメモリ読み出
し部２ａ，２ｂと、読み出されたパケットデータと入力
されたパケットのデータを比較して両データの関係を判
定する比較判定部３ａ，３ｂと、この比較判定部３ａ，
３ｂの比較結果に基づいて入力されたパケットのデータ
と読み出されたパケットデータを処理するデータ処理部
４ａ，４ｂと、このデータ処理部４ａ，４ｂで処理され
たデータをパケット番号に対応する上記マッチングメモ
リ６のアドレスに書き込み、あるいは出力ポートＡ，Ｂ
を経て出力するメモリ書き込み部５ａ，５ｂとを、デー
タ伝送路１ａ，１ｂでループ状に結合し、上記マッチン
グメモリ６へのアクセスの競合をメモリアクセス制御回
路７で制御して、入力ポートＡ，Ｂから並列入力される
パケットデータをパイプライン処理するとともに高速テ
ンプレートマッチングするものである。

従って、例えば入力ポートＡから、第６図のデータ１フ
ィールド２８にオペランドが書き込まれたパケットが入
ってきた場合、メモリ読み出し部２ａは、そのパケット
番号に対応するマッチングメモリ６のアドレスからパケ
ットデータを読み出す。そして、対となるデータ２フィ
ールド２９のオペランドが読み出されれば、このパケッ
トは、比較判定部３ａ，データ処理部４ａを経て両オペ
ランドが揃ったパケットとしてメモリ書き込み部５ａに
よって出力ポートＡに出力され、同時にマッチングメモ
リ６の当該アドレスのデータがクリアされる。一方、対
となるデータ２フィールド２９のオペランドが読み出さ
れなければ、入力されたパケットのパケットデータは、
同様の経路を経てメモリ書き込み部５ａによってマッチ
ングメモリ６の当該アドレスに書き込まれ、対となるデ
ータが来るのを待つことになる。

〈発明が解決しようとする課題〉 さて、上記対データ検出回路２２は、上述のように演算
処理部２３での演算に必要なパケットの対データ（対オ
ペランド）を揃えるために用いられるほか、２つの処理
が共に終了したことを確認するためにも用いられる。こ
の場合、対データ検出回路２２が２つのデータの行先フ
ィールドの一致の検出を行うものであるため、第７図に
示すＡ，Ｂの処理が終ると、プログラム記憶部２１から
行先フィールド２６（第６図参照）を同じ＃ｉにし、命
令フィールド２７に同期コードＳＹＮＣを有し、データ
１，２フィールド２８，２９に特に意味のないデータの
入った同期命令パケットが夫々出力され、Ｃ，Ｄの処理
が終ると、行先フィールド２６を同じ＃ｊにした同様の
同期命令パケットが夫々出力される。そして、対データ
検出回路２２でＡ，ＢあるいはＣ，Ｄの同期がとられる
と、各同期命令パケットは、通信ネットワーク２４を回
ってプログラム記憶部２１に達し、次いでプログラム記
憶部２１から行先フィールドを同じ＃ｋにしたｉ番同期
命令パケットあるいはｊ番同期命令パケットが送出され
る。さらに、両同期命令パケットの同期が第７図の＃ｋ
で示すように対データ検出回路２２でとられると、同期
命令パケットは通信ネットワーク２４を回り、プログラ
ム記憶部２１から４つの処理Ａ，Ｂ，Ｃ，Ｄが終了した
ことを示すパケットＳＩＧが送出される。

ところが、上記対データ検出回路２２による同期確認処
理では、第７図に示すように４つの処理Ａ，Ｂ，Ｃ，Ｄ
の同期をとるのに３個の同期命令（ＳＹＮＣ）が必要
で、かつ通信ネットワーク２４を最低２度回る即ち２段
のパイプラインサイクルが必要になる。一般化すれば、
ｎ個の処理の同期をとるにはｎ−１個の同期命令が必要
で、log₂n段のパイプラインサイクルが必要になる。そ
のため、同期をとる処理の個数が多くなるほど、多数の
同期命令の送出と多段のパイプラインサイクルによっ
て、処理時間が激増し、処理の高速化が図れないという
欠点がある。

そこで、本発明の目的は、同期命令パケットの従来使用
されていなかったデータフィールド部をフラグとして用
い、３個以上の処理の同期を一度にとることによって、
データフロー計算機における同期処理の高速化を実現す
ることができる対データ検出回路を提供することであ
る。

〈課題を解決するための手段〉 上記目的を達成するため、本発明の対データ検出回路
は、マッチングメモリ、メモリ読み出し部、比較判定
部、データ処理部およびメモリ書き込み部をデータ伝送
路でループ状に結合し、マッチングメモリへのアクセス
の競合を制御して、並列入力されるパケットデータをパ
イプライン処理するとともに高速テンプレートマッチン
グを行うものにおいて、上記入力ポートから入力された
パケットの命令フィールドが３個以上の処理の同期をと
るための同期命令であるか否かを判定するとともに、肯
と判定したとき、上記データ処理部の通常処理を停止さ
せかつ同期命令信号を出力する一方、否と判定したと
き、上記データ処理部に通常処理を続行させる命令判定
部と、上記入力されたパケットおよびメモリ読み出し部
によって読み出されたパケットデータの所定データフィ
ールドに夫々記述され、同期をとるべき各処理を一定数
のビットからなるフラグ中の唯一フラグ位置で示した２
進数同士の論理和を上記命令判定部からの同期命令信号
を受けて算出し、算出した論理和を上記入力されたパケ
ットの所定データフィールドに書き込むとともに、算出
した論理和の全ビットにフラグが立ったとき、上記パケ
ットを上記メモリ書き込み部を介して出力ポートから出
力し、かつ上記マッチングメモリの当該アドレスのパケ
ットデータを消去する一方、算出した論理和のいずれか
のビットにフラグが立っていないとき、上記パケットを
上記メモリ書き込み部を介して上記マッチングメモリの
当該アドレスに書き込むデータフィールド論理和部を備
えたことを特徴とする。

〈作用〉 入力ポートから入力されたパケットが同期命令である場
合、命令判定部は、肯と判定して、データ処理部の通常
処理を停止させ、かつ同期命令信号を出力する。データ
フィールド論理和部は、上記同期命令信号を受けて、入
力されたパケットおよびメモリ読み出し部によってマッ
チングメモリの対応するアドレスから読み出されたパケ
ットデータの所定データフィールドに夫々記述された２
進数同士の論理和を算出する。上記２進数は、同期をと
るべき各処理を一定数のビットからなるフラグ中の唯一
フラグ位置で示したものであるから、算出された論理和
中の終了した処理に対応するビット位置には順次フラグ
が立つ。データフィールド論理和部は、この論理和を上
記入力されたパケットの所定データフィールドに書き込
む。そして、算出した論理和の全ビットにフラグが立っ
たとき、全処理の同期がとれたとして、そのパケットを
メモリ書き込み部を介して出力ポートから出力し、かつ
上記マッチングメモリの当該アドレスのパケットデータ
を消去する。一方、算出した論理和のいずれかのビット
にフラグが立っていないとき、未同期の処理があるとし
て、そのパケットのパケットデータを上記メモリ書き込
み部を介してマッチングメモリの当該アドレスに書き込
む。

一方、入力ポートから入力されたパケットが同期命令で
ない場合、命令判定部は、否と判定して、上記データ処
理部の通常処理を続行させ、入力されたパケットは、従
来例と同様に対となるデータ（オペランド）が揃った時
点で出力ポートから出力される。

〈実施例〉 以下、本発明を図示の実施例により詳細に説明する。

第１図は本発明の対データ検出回路の一実施例の上半分
を示すブロック図であり、１ａはデータ伝送路、２ａは
メモリ読み出し部、３ａは比較判定部、４ａはデータ処
理部、５ａはメモリ書き込み部、６はマッチングメモ
リ、７はメモリアクセス制御回路であり、これら各部
は、第８図で既述の従来例と同じ構成および作用をもつ
ので、同一部には同じ番号を付して説明を省略する。ま
た、この対データ検出回路１１の図示しない下半分は、
入力ポートＢ、出力ポートＢをもち、マッチングメモリ
６，メモリアクセス制御回路７に関して、上半分と対称
の構成をなす。

第１図において、命令判定部８ａは、入力ポートＡから
メモリ読み出し部２ａを経て入力されたパケットの命令
フィールド１７（第３図参照）が同期命令（ＳＹＮＣ）
であるか否かを判定する。そして、同期命令であると判
定したとき、データ処理部４ａへの通常命令信号Ａの出
力を停止して、通常処理を停止させ、かつ後述するデー
タフィールド論理和部９ａへ同期命令信号Ａを出力す
る。一方、同期命令でないと判定したとき、上記同期命
令信号Ａの出力を停止し、かつデータ処理部４ａへ通常
命令信号Ａを出力して、従来例と同様の通常処理を続行
させる。

一方、上記データフィールド論理和部９ａは、入力ポー
トＡから入力されたパケットおよびメモリ読み出し部２
ａによって読み出されたパケットデータのデータ１フィ
ールド１８（第３図参照）に夫々記述された終了処理表
示フラグを表わす２進数同士の論理和を、命令判定部８
ａからの上記同期命令信号Ａを受けて算出する。上記２
進数は、終了した処理を、同期をとるべき処理の数と同
数のビットからなるフラグ中のその処理に対応する唯一
のフラグ位置で示したものであり、例えば同期をとるべ
き処理がＡ，Ｂ，Ｃ，Ｄ（第２図参照）の４つなら、第
３図に示すように同期命令パケット１５のデータ１フィ
ールド１８の下４桁を“０”とし、そのうちの例えば終
了した処理Ｃに対応する下第２桁目にフラグ“１”を立
てるとともに、残る上位の桁を全て“１”でマスクして
いる。フラグ“１”を立てるビット位置は、第４図(a)
に示すように終了した処理が、Ａなら下第４桁，Ｂなら
下第３桁，Ｄなら下第１桁となる。従って、算出された
論理和たる２進数の終了処理に対応するビット位置には
順次フラグ“１”が立つことになる。データフィールド
論理和部９ａは、この算出された論理和を上記入力され
たパケットのデータ１フィールド１８に書き込む。そし
て、上記論理和の全ビットに第４図(b)に示すようにフ
ラグが立ったとき、上記パケットを上記メモリ書き込み
部５ａを介して出力ポートＡから出力し、かつマッチン
グメモリ６の当該アドレスのパケットデータを消去す
る。一方、上記論理和のいずれかのビットにフラグが立
っていないとき、上記パケットのパケットデータをメモ
リ書き込み部５ａを介してマッチングメモリ６の当該ア
ドレスに書き込むとともに、パケット消滅部１０ａにパ
ケット消滅信号Ａを出力して、未同期のパケットを消滅
させ、出力ポートＡから出力させないようになってい
る。

上記構成の対データ検出回路１１の動作について次に述
べる。

入力ポートＡから入力されたパケットが第３図の如き同
期命令である場合、命令判定部８ａは、同期命令だと判
定して、通常命令信号Ａを止めてデータ処理部４ａの通
常処理を停止させ、かつデータフィールド論理和部９ａ
に同期命令信号Ａを出力する。すると、データフィール
ド論理和部９ａは、入力されたパケットおよびメモリ読
み出し部２ａによってマッチングメモリ６の対応するア
ドレスから読み出されたパケットデータのデータ１フィ
ールド１８に夫々記述された２進数同士の論理和を算出
し、算出結果を上記パケットのデータ１フィールド１８
に書き込む。同期をとるべき処理Ａ，Ｂ，Ｃ，Ｄが全て
終了すれば、上記データ１フィールド１８の全ビットに
フラグ“１”が立つから、データフィールド論理和部９
ａは、上記パケットをメモリ書き込み部５ａを介して出
力ポートＡから出力し、かつマッチングメモリ６の当該
アドレスのパケットデータを消去する。一方、同期をと
るべき処理Ａ，Ｂ，Ｃ，Ｄのいずれかが未了なら、上記
データ１フィールド１８にフラグの立っていない“０”
のビットがあるから、データフィールド論理和部９ａ
は、上記パケットをメモリ書き込み部５ａを介してマッ
チングメモリ６の当該アドレスに書き込むとともに、パ
ケット消滅部１０ａにパケット消滅信号Ａを送って出力
ポートＡからの上記パケットの出力を阻止する。

一方、入力ポートＡから入力されたパケットが第６図の
如き通常の演算パケットである場合、命令判定部８ａ
は、同期命令でないと判定して、通常命令信号Ａを送っ
てデータ処理部４ａの通常処理を続行させ、入力された
パケットは、従来例と同様に対となるデータ（オペラン
ド）がデータ１フィールド１８およびデータ２フィール
ド１９に揃った時点で出力ポートＡから出力される。

このように、上記実施例では、従来使用されていなかっ
た同期命令パケットのデータ１フィールド部をフラグと
して用いて、４つのパケット（処理Ａ，Ｂ，Ｃ，Ｄ）の
同期を第４図(a)に示すように一度（１パイプラインサ
イクル）にとれるようにしているので、入力ポートＡ，
Ｂ（図示せず）から入力された同期命令パケットは、マ
ッチングメモリ６のパケットデータ部を作業領域にして
揃ったか否かが高速に確認でき、同期処理が著しく高速
化できる。なお、他の同期処理として、データ１フィー
ルド１８をカウントとして用い、待ち合わせ個数のデー
タが入ってきた時に同期完了とする手法も考えられる
が、この手法では同じ処理から２個以上のデータが来た
ときに誤って同期完了となる欠点がある。これに対し、
本発明の手法では、同期をとるべき各処理をビット位置
で区別しているので、既にフラグが立っているビットに
“１”が来たときにエラーとする機構を追加することに
より、上記誤動作を排除することができる。また、既に
フラグが立っているビットに“１”がきた時に、エラー
にはせずに未処理のままそのパケットを出力ポートから
出し、現在の１組の同期が終わって、当該アドレスのパ
ケットデータが消去されるまで、プログラム記憶部→対
データ検出回路→演算処理部を巡回させるようにするこ
とにより、同じデータ（この例ではＡ，Ｂ，Ｃ，Ｄ）の
同期を複数回取ることも可能である。

なお、上記実施例では、データ１フィールド１８のフラ
グが４ビットで４つの処理の同期をとる場合について述
べたが、データ１フィールドの全ビット幅をフラグに用
いればより多数の処理の同期をとることができる。ま
た、実施例では、フラグを“０”中の“１”で表わした
が、これを逆に“１”中の“０”で表わすこともでき
る。さらに、本発明が図示の実施例に限られないのはい
うまでもない。

〈発明の効果〉 以上の説明で明らかなように、本発明の対データ検出回
路は、マッチングメモリ，メモリ読み出し部，比較判定
部，データ処理部，メモリ書き込み部をデータ伝送路で
ループ状に結合し、並列入力されるパケットデータをパ
イプライン処理し、かつ高速テンプレートマッチングを
行う際、入力されたパケットの命令フィールドが３個以
上の処理の同期をとるための同期命令であるか否かを命
令判定部で判定し、肯と判定した場合、同期命令信号を
データフィールド論理和部に出力して、このデータフィ
ールド論理和部で、入力されたパケットおよびメモリ読
み出し部によってマッチングメモリの対応アドレスから
読み出されたパケットデータの所定データフィールドに
夫々記述された終了処理表示フラグを表わす２進数同士
の論理和を求め、その結果を入力されたパケットの所定
データフィールドに書き込むとともに、上記論理和の全
ビットにフラグが立ったとき、上記パケットをメモリ書
き込み部を介して出力ポートから出力し、かつマッチン
グメモリの当該アドレスのパケットデータを消去する一
方、上記論理和のいずれかのビットにフラグが立ってい
ないとき、上記パケットをメモリ書き込み部を介してマ
ッチングメモリの当該アドレスに書き込み、否と判定し
た場合、データ処理部に従来と同じ通常処理を続行させ
るようにしているので、１パイプラインサイクルで多数
（３個以上）の同期命令パケットの同期を一度にとるこ
とができ、確実な同期処理を従来例よりも格段に速く行
うことができ、データフロー計算機の演算高速化に大い
に貢献する。

【図面の簡単な説明】

第１図は本発明の対データ検出回路の一実施例の上半分
を示すブロック図、第２図は上記実施例の同期命令の実
行手法を示す図、第３図は上記実施例の同期命令パケッ
トの構成を示す図、第４図(a)，(b)は上記同期命令パケ
ットの終了処理表示フラグを説明する図、第５図はデー
タフローコンピュータの一般的構成を示す図、第６図は
一般的パケットの構成を示す図、第７図は従来の同期命
令の実行手法を示す図、第８図は従来の対データ検出回
路を示すブロック図である。 １ａ…データ伝送路、２ａ…メモリ読み出し部、 ３ａ…比較判定部、４ａ…データ処理部、 ５ａ…メモリ書き込み部、 ６…マッチングメモリ、 ７…メモリアクセス制御回路、 ８ａ…命令判定部、 ９ａ…データフィールド論理和部、 １０ａ…パケット消滅部、 １１…対データ検出回路。

Claims (1)

【特許請求の範囲】
1. 【請求項１】パケット番号に対応するアドレスにそのパ
   ケットデータを格納するマッチングメモリと、入力ポー
   トから入力されたパケットのパケット番号に対応する上
   記マッチングメモリのアドレスからパケットデータを読
   み出すメモリ読み出し部と、読み出されたパケットデー
   タと入力されたパケットのデータを比較して両データの
   関係を判定する比較判定部と、この比較判定部の比較結
   果に基づいて入力されたパケットのデータと読み出され
   たパケットデータを処理するデータ処理部と、このデー
   タ処理部で処理されたデータをパケット番号に対応する
   上記マッチングメモリのアドレスに書き込み、あるいは
   出力ポートを経て出力するメモリ書き込み部を、データ
   伝送路でループ状に結合し、上記マッチングメモリへの
   アクセスの競合を制御して、並列入力されるパケットデ
   ータをパイプライン処理するとともに高速テンプレート
   マッチングを行う対データ検出回路において、 上記入力ポートから入力されたパケットの命令フィール
   ドが３個以上の処理の同期をとるための同期命令である
   か否かを判定するとともに、肯と判定したとき、上記デ
   ータ処理部の通常処理を停止させかつ同期命令信号を出
   力する一方、否と判定したとき、上記データ処理部に通
   常処理を続行させる命令判定部と、 上記入力されたパケットおよびメモリ読み出し部によっ
   て読み出されたパケットデータの所定データフィールド
   に夫々記述され、同期をとるべき各処理を一定数のビッ
   トからなるフラグ中の唯一フラグ位置で示した２進数同
   士の論理和を上記命令判定部からの同期命令信号を受け
   て算出し、算出した論理和を上記入力されたパケットの
   所定データフィールドに書き込むとともに、算出した論
   理和の全ビットにフラグが立ったとき、上記パケットを
   上記メモリ書き込み部を介して出力ポートから出力し、
   かつ上記マッチングメモリの当該アドレスのパケットデ
   ータを消去する一方、算出した論理和のいずれかのビッ
   トにフラグが立っていないとき、上記パケットを上記メ
   モリ書き込み部を介して上記マッチングメモリの当該ア
   ドレスに書き込むデータフィールド論理和部を備えたこ
   とを特徴とする対データ検出回路。