JPH0620072A - データ駆動型情報処理装置およびそこに用いられるデータバッファ - Google Patents

Abstract

(57)【要約】 【目的】 縮退メモリ空間を利用して対データを検出す
る機能を備えるデータ駆動型情報処理装置のデータ処理
効率を向上させることを目的とする。 【構成】 巡回パスに設けられ、この巡回パスにおける
データのパケットの流量の揺らぎを吸収するために設け
られたバッファメモリ（１）は、格納されたデータパケ
ットの所定のキーデータの大小に応じてその出力順序を
再配列する再配列制御ユニット（１０）を含む。この再
配列制御ユニットは、対データ検出ユニット（５６２）
が利用する優先度判別基準と同じ判別基準に従って出力
データパケットの配列順序を変更する。 【効果】 データバッファにおける出力データパケット
の再配列により、発火する可能性の高いデータパケット
が早く対データ検出ユニットへ与えられるため、ハッシ
ュ衝突データパケットによる処理効率の低下を防止する
ことができ、高速でデータフロープログラムを実行する
ことのできるデータ駆動型情報処理装置が得られる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は与えられたデータに従
って処理を実行するデータフロー型情報処理装置および
データを一時的に格納するためのデータバッファに関
し、特に、縮退したメモリ空間を利用する対データ検出
機能を備えるデータフロー型情報処理装置およびそこに
用いるのに適したデータ並び換え機能を有するデータバ
ッファに関する。

【０００２】

【従来の技術】近年高精彩画像処理など様々な分野にお
いて大量のデータを高速で処理することが必要とされ
る。情報を高速で処理する手法の１つに、複数の演算を
並列に処理する並列処理がある。並列処理向きの処理装
置の１つにデータフロー型（データ駆動型）情報処理装
置がある。データフロー型情報処理装置は、データフロ
ープログラムに従って処理を実行する。

【０００３】データフロープログラムは、演算および制
御を示すノード（アクタと呼ばれる）と、ノードとノー
ドとの間を結ぶアークとで構成される有向グラフで記述
される。

【０００４】図１３は、データフロープログラム（デー
タフローグラフ）の一例を示す図である。図１３におい
て、ノードＮＤ１は入力アークａおよびｂに対し演算Ｏ
Ｐ１を施してノードＮＤ３へ出力する。ノードＮＤ２
は、入力アークｄに演算ＯＰ２を施し、その演算結果を
ノードＮＤ３およびＮＤ４へ与える。ノードＮＤ３は、
ノードＮＤ１からのデータ、入力アークｃおよびノード
ＮＤ２からのデータに対し演算ＯＰ３を施してその処理
結果を出力する。ノードＮＤ４は、ノードＮＤ２からの
データに演算ＯＰ４を施してその処理結果を出力する。
各ノードにおいては、入力アークにデータ（トークンと
呼ばれる）が揃ったときにそのノードに割り当てられた
演算が実行される。演算の実行をそのノードが「発火す
る」と称す。この発火の結果、入力データ（入力トーク
ン）は消費され、出力トークンが生成される。

【０００５】ノードＮＤ１は２つの入力アークａおよび
ｂを有する。ノードＮＤ１は、２つの入力アークａおよ
びｂに入力データがそれぞれ到着しかつ出力アークが空
いているときに発火する。すなわち、入力データ（入力
トークン）に演算ＯＰ１が施されてその演算結果が出力
トークンとなる。このときノードＮＤ２の入力アークｄ
に入力データが到着していれば、ノードＮＤ１とノード
ＮＤ２とは同時に発火することができる。ノードＮＤ３
は、ノードＮＤ１およびノードＮＤ２の演算が完了する
のを待つ必要がある。ノードＮＤ４は、ノードＮＤ２に
おいて演算ＯＰ２が実行された後に発火することができ
る。

【０００６】一般に、ｎ入力ｍ出力のノードは最大２入
力および２出力を有する基本ノードの組合せで実現する
ことができる。基本ノードとしては、入力アークに与え
られたデータに演算を施す演算ノードと、入力トークン
をコピーして複数の出力アークに出力する分配ノード
と、複数の入力アークに与えられたデータを出力アーク
へ伝達する合流ノードと、データの伝達経路を制御する
制御ノードなどがある。

【０００７】データフロー型処理では、データ駆動と呼
ばれる実行原理に基づいて処理が実行される。データ駆
動の原理においては、「すべての演算は、その実行に必
要なオペランド（データ）が揃ったときに実行され
る」。データ駆動方式は、或る処理に１組の入力データ
しか許さない静的データ駆動方式と、２組以上の入力デ
ータの組を許す動的データ駆動方式とを含む。動的デー
タ駆動方式においては、複数の入力データの組を識別す
るために、「世代番号」などの識別子が利用される。伝
送データは、行先ノードなどを特定する情報を含み、パ
ケットの形態で伝達される。

【０００８】図１４は、データパケットの構成を示す図
である。図１４において、データパケットは、未発火フ
ラグ、２出力命令識別フラグなどのデータの状態を示す
フラグを格納するフラグフィールドＦ１と、行先ノード
を特定する行先ノード番号を格納する行先ノード番号フ
ィールドＦ２と、その行先ノードにおける世代識別子で
ある世代番号を格納する世代番号フィールドＦ３と、実
行されるべき演算を特定する命令を格納する命令フィー
ルドＦ４と、処理されるべきデータすなわちオペランド
データを格納するオペランドデータフィールドＦ５およ
びＦ６を含む。命令フィールドは、その命令が２項演算
命令であるか単項演算命令であるかを識別する２項／単
項演算命令識別フラグを含む。この命令フィールドＦ４
に含まれる２項／単項演算命令識別フラグについては後
にまた説明する。

【０００９】図１５は、データ駆動型情報処理装置の全
体の構成を概略的に示す図である。図１５において、デ
ータ駆動型情報処理装置５００は、外部から与えられる
入力データを受けるための入力ポート５０２と、入力ポ
ート５０２からの入力データのうち、このデータ駆動型
情報処理装置５００を指定する入力データとそうでない
入力データとを分離する分岐ユニット５０４と、分岐ユ
ニット５０４からの入力データを受け、その入力データ
に含まれる演算命令に従って処理を行なうデータ駆動エ
ンジン５０６と、データ駆動エンジン５０６からの処理
データと分岐ユニット５０４からの入力データとを合流
する合流ユニット５０８と、合流ユニット５０８からの
データを出力する出力ポート５１０を含む。

【００１０】入力ポート５０２は、外部から与えられる
入力データを受ける。複数の処理装置が含まれるマルチ
プロセサシステムにおいては、入力ポート５０２は、異
なる処理装置からのデータを合流した後に出力する。分
岐ユニット５０４は、この処理装置５００を参照しない
入力データを合流ユニット５０８へ出力し、この処理装
置５００を参照する入力データをデータ駆動エンジン５
０６へ伝達する。

【００１１】データ駆動エンジン５０６は、この分岐ユ
ニット５０４から与えられたデータに従って処理を実行
する。このデータ駆動エンジン５０６は、その構成は後
に詳細に説明するが、命令コードの更新および次命令フ
ェッチに必要な行先情報（ノード番号）の更新を行なう
機能と、処理に必要なデータが揃ったこと（発火）の検
出を行なう発火制御機能と、必要なデータの待合せが完
了した命令に対し算術・論理演算などを行なう演算処理
機能とを備える。

【００１２】分岐ユニット５０４からのこの処理装置５
００を参照しない入力データおよびデータ駆動エンジン
５０６からの処理結果データは合流ユニット５０８で合
流される。合流ユニット５０８においては、分岐ユニッ
ト５０４およびデータ駆動エンジン５０６から排他的に
与えられるデータを出力ポート５１０へ伝達する。出力
ポート５１０は、与えられたデータに対し、所定のルー
ティング（マルチプロセサシステムにおける処理装置へ
の振り分け）を行ない、対応の処理装置へ伝達する。

【００１３】図１６は、図１５に示すデータ駆動エンジ
ンの構成を概略的に示すブロック図である。図１６にお
いて、データ駆動エンジン５０６は、与えられたデータ
パケットを入力順に出力する合流ユニット５５０と、合
流ユニット５５０からのデータパケットに対し、命令コ
ードの更新、ノード番号の更新および発火の検出を行な
うプログラム記憶付発火制御ユニット５５２と、このプ
ログラム記憶付発火制御ユニット５５２からの発火デー
タパケットに対しその命令フィールドＦ４に含まれる命
令に従った演算を行なう演算処理ユニット５５４と、演
算処理ユニット５５４からの処理データまたは未発火デ
ータパケットを受け、そのデータパケットに含まれる行
先情報（ノード番号）に従ってその行先をデータ駆動エ
ンジン５０６の外部または内部に振り分ける分岐ユニッ
ト５５６と、分岐ユニット５５６からのデータパケット
を順次格納し、その格納データを順次入力順に合流ユニ
ット５５０へ与えるデータバッファ５５８を含む。

【００１４】プログラム記憶付発火制御ユニット５５２
は、２項演算命令等で処理されるべき２つのオペランド
データの待合せを行なうための対データ検出ユニット５
６２と、行先情報（ノード番号等）および命令情報を格
納したレコードを複数個含むデータフロープログラムを
記憶するプログラム記憶ユニット５６４を含む。プログ
ラム記憶ユニット５６４は、また与えられたデータパケ
ットに含まれるノード番号データに基づいて生成された
アドレスに従ってこのプログラムメモリから対応のデー
タレコードを読出し、与えられたデータパケットの行先
ノード番号フィールドＦ２および命令フィールドＦ４の
内容を、読出したデータレコードの内容に更新して出力
する機能を備える。

【００１５】対データ検出ユニット５６２は、前述のご
とく２項演算命令等で処理されるべき２つのオペランド
データの待合せを行なう。すなわち、対となるデータを
検出する。ここで、対となるデータとは、同じ行先ノー
ド番号および同じ世代番号を有するデータパケットであ
る。この対データ検出ユニット５６２は、このデータの
待合せのための待合せメモリを備える。

【００１６】この図１６に示す構成においては、プログ
ラム記憶付発火制御ユニット５５２において発火が検出
されたデータに対してのみ演算処理ユニット５５４にお
いて処理が実行される。未発火データパケットは演算処
理ユニット５５４では処理は実行されない。この未発火
のデータパケットは分岐ユニット５５６によりデータバ
ッファ５５８へ格納される。分岐ユニット５５６は、ま
た、未発火状態でないデータパケットに対しても、その
行先番号フィールドＦ２に含まれるノード番号情報に従
ってデータパケットを装置外部またはデータバッファ５
５８へ伝達する。

【００１７】データバッファ５５８は、この処理装置５
０６を流れるデータパケットの数が増加した場合に、こ
の処理装置５０６のパイプラインから溢れ出ないように
するために、一時的にデータパケットを格納する。デー
タバッファ５５８は、通常、先入れ先出し型メモリで構
成される。データバッファ５５８は、この分岐ユニット
５５６から入力されるデータパケットを順次取込んで格
納し、合流ユニット５５０が空き状態にあれば、この格
納した順にデータパケット合流ユニット５５０を介して
プログラム記憶付制御ユニット５５２へデータパケット
を伝達する。処理装置５０６においては、通常このプロ
グラム記憶付発火制御５５２および演算処理５５４がパ
イプラインを構成しており、データ処理が互いにオーバ
ラップしながら実行され、データ処理の高速化が図られ
ている。

【００１８】図１７は、図１６に示すプログラム記憶付
発火制御ユニットの機能的構成を示す図である。図１７
において、対データ検出ユニット５６２は、与えられた
入力データパケットの命令フィールドＦ４の命令をデコ
ードし、その命令が単項演算命令であるか２項演算命令
であるかの判別を行なう命令識別部６０２と、命令識別
部６０２の制御の下に活性化され、入力データパケット
の行先ノード番号フィールドＦ２および世代番号フィー
ルドＦ３に含まれる行先ノード番号および世代番号に対
しハッシュ演算（これについては後述する）を施して待
合せメモリ６０４のアドレスを生成し、対応のアドレス
のデータ（データパケット）を読出す読出制御部６０６
と、読出制御部６０６により待合せメモリ６０４から読
出されたデータ（データパケット）と入力データパケッ
トとの優先順位を予め定められた条件に従って判別する
とともに、対となるデータであるか否かの判別をも合わ
せて行なう優先度判別部６０８と、優先度判別部６０８
の判別結果に従って、入力データパケットおよび読出デ
ータ（データパケット）に対し所定の処理を行なうパケ
ット制御部６１０を含む。パケット制御部６１０は、優
先度判別部６０８において、読出されたデータ（データ
パケット）と入力データパケットとが対をなすデータで
あることが判別された場合には、発火パケットを生成し
プログラム記憶ユニット５６４へ伝達する。

【００１９】命令識別部６０２は、命令フィールドＦ４
に含まれる単項演算命令／２項演算命令フラグを見て命
令を識別してもよい。

【００２０】待合せメモリ６０４は、通常対をなすデー
タを待受けるデータパケットに対しては、有効フラグ
（ＶＬＤ）を立てて格納する。優先度判別部６０８は、
この待合せメモリ６０４から読出されたデータと入力デ
ータパケットとのハッシュ衝突および発火命令の判別を
行なう。ハッシュ衝突時においては、優先度判別部６０
８は、予め定められた優先順位に従っていずれのデータ
パケットを待合せメモリ６０４に格納するかを判別す
る。ハッシュ衝突時において、待合せメモリ６０４に格
納されないデータパケットは、パケット制御部６１０に
おいて、未発火フラグＮＦＲが立てられて“１”とされ
てプログラム記憶ユニット５６４へ伝達される。ここ
で、読出制御部６０６がアドレス生成時に行なうハッシ
ュ演算および優先度判別部６０８におけるハッシュ衝突
について説明する。

【００２１】図１８は、ハッシュ演算の効果を示す図で
ある。動的データ駆動方式においては、或る処理に対し
複数組の入力データの組が許容される。この複数組の入
力データを識別するために世代番号などの識別子が導入
される。したがって、行先ノード番号および世代番号を
アドレスとするメモリの物理的空間が対データを待合せ
るための場所として利用される。このデータの待合せ領
域としては、使用されるすべての行先ノード番号と世代
番号の組合せのすべてを含むメモリ空間を持つことが望
ましい。しかしながら、取扱われる世代数およびノード
番号の数が多くなると、このような行先ノード番号およ
び世代番号すべての組をアドレスとするメモリ空間を有
することはメモリ利用効率の点からみて現実的ではなく
また経済的でもない。そこで、図１８に示すように、行
先ノード番号と世代番号とに対しハッシュ演算を施し、
その結果得られる値をアドレスとする待合せメモリアド
レス空間を作成する。

【００２２】ハッシュ演算とは、複数のフィールド（通
常キー）を異なった配置に変更するために行なわれる操
作を示す。たとえば元のキーを新しいキーに変形するた
めに、元のキーについて何らかの予め定められた操作を
行なうことをハッシュ演算と呼ぶ。このハッシュ演算に
は様々な方法がある。簡単なハッシュ演算に、除算剰余
法と呼ばれるものがある。この除算剰余法においては、
或る適当な数を選択し、この選択された数を除数として
被除数を割り、商と余りとを求める。この余りを変換後
のキーとする。この場合、除数として、たとえば１００
０を用いると、変換後のキーは元のキーのモジュロ１０
００となる。すなわち、たとえば除数を１０００とした
場合、行先ノード番号と世代番号をこのモジュロ１００
０の演算によりハッシュアドレスを生成する。この場
合、図１８に示すように、ノード番号／世代番号空間を
ハッシュ演算により待合せメモリアドレス空間へ圧縮し
たため、待合せメモリアドレス空間のアドレス（以下ハ
ッシュアドレスと呼ぶ）とノード番号／世代番号空間に
おけるアドレスとは１対多対応となる。このようにハッ
シュアドレスが重複することをハッシュ衝突と呼ぶ。ハ
ッシュ演算としては、上述の除算数剰余法の他に、折り
重ね法、基数変換法および数字再配置法などがある。

【００２３】図１９に示すように、ノード番号／世代番
号空間８００において、行先ノード番号ＮＤと世代番号
ＧＮがそれぞれ異なる領域ＮＤ１／ＧＮ１、ＮＤ２／Ｇ
Ｎ２、ＮＤ３／ＧＮ３、ＮＤ４／ＧＮ４が待合せメモリ
アドレス空間におけるハッシュアドレスＨＡｉに対応す
る状態が存在する。１つのハッシュアドレスに対し複数
のノード番号／世代番号アドレスが存在する状態を縮退
と称す。

【００２４】読出制御部６０６は上述のハッシュ演算を
施して待合せメモリ６０４に対するアドレスを生成して
いる。この場合、互いに異なる行先ノード番号および世
代番号を有するデータであっても、この待合せメモリ６
０４の同一アドレスの待合せ領域を利用する。したがっ
てハッシュ衝突が生じる。

【００２５】今、対データの待合せを行なうためにデー
タパケットがこの待合せメモリ６０４に書込まれている
とき（待合せデータは通常有効フラグが立てられてい
る）、行先ノード番号または世代番号が異なるが同一の
ハッシュアドレスを有するデータが与えられた場合に
は、どちらのデータを優先的に処理するのかを判別する
必要がある。この優先度の判別が優先度判別部６０８に
おいて実行される。優先度判別部６０８は、その待合せ
メモリ６０４から読出されたデータと入力データとの優
先度を比較し、優先度が高い方のデータパケットを待合
せメモリ６０４に書込み、優先度の低いデータパケット
は未発火フラグＮＦＲを立てて出力する。この待合せメ
モリ６０４へのデータパケットの書込および未発火フラ
グのオン／オフはパケット制御部６１０において実行さ
れる。以下の説明において、優先度判別部６０８が用い
る優先度の判別基準には、（１）世代番号が小さい方が
優先度が高い、（２）世代番号が同一の場合には、行先
ノード番号が小さい方が優先度が高いという基準が利用
されるものとする。

【００２６】ハッシュ衝突が生じず、対をなすデータが
検出された場合、パケット制御部６１０は、有効フラグ
をオフとし、かつ未発火フラグをもオフとしてデータパ
ケットをプログラム記憶ユニット５６４へ伝達する。

【００２７】プログラム記憶ユニット５６４は、対デー
タ検出ユニット５６２からのデータパケットを受け、そ
のデータパケットが発火しているか否かを識別する発火
識別部６２０と、発火識別部６２０からの発火／未発火
指示情報に従って、入力データパケットの行先ノード番
号フィールドＦ２に含まれる行先ノード番号に基づいて
アドレスを生成し、プログラムメモリ６２２から次の命
令をフェッチする次命令フェッチ部６２４と、この次命
令フェッチ部６２４でフェッチされたデータパケットに
対し、発火識別部６２０からの発火指示に従って、入力
データパケットの行先ノード番号フィールドＦ２および
命令フィールドＦ４の内容を、次命令フェッチ部６２４
によりプログラムメモリ６２２からフェッチされた次の
行先情報および命令情報により更新するパケット生成部
６２６を含む。パケット生成部６２６は、発火識別部６
２０が発火を識別しないとき、すなわち入力データパケ
ットの未発火フラグが立てられてオン状態の場合にはこ
の入力データパケットに対しては処理を行なわずそのま
ま出力する。

【００２８】このパケット生成部６２６からのデータパ
ケットが演算処理ユニット５５４へ伝達される。次に、
この対データ検出ユニット５５２およびプログラム記憶
ユニット５６４の動作についてその動作フロー図である
図２０および図２１を参照して説明する。

【００２９】図２０は対データ検出ユニットの動作を示
すフロー図である。以下、図１７および図２０を参照し
て対データ検出ユニットの動作について説明する。

【００３０】入力データパケットが与えられると、まず
命令識別部６０２において命令がデコードされ（ステッ
プＳ１）、その入力データパケットに含まれる演算命令
が２項演算命令であるか単項演算命令であるかの判別が
行なわれる（ステップＳ２）。このとき、２項演算命令
は２変数演算命令および定数演算命令両者を含んでもよ
い。また、命令デコード操作としては、単に単項演算命
令／２項演算命令フラグを見ることによりデコードおよ
び判別動作が行なわれてもよい。

【００３１】ステップＳ２において２項演算命令ではな
いと判別された場合、その命令は単項演算命令であり、
対データは待合せていないため、そのデータパケットの
未発火フラグはオフ状態にリセットされ（ステップＳ
４）出力される。

【００３２】ステップＳ２において、２項演算命令であ
ると判別された場合、読出制御部６０６において、入力
データパケットに含まれる行先ノード番号および世代番
号に対しハッシュ演算を施してハッシュアドレスが生成
され、待合せメモリ６０４へアクセスが行なわれる（ス
テップＳ６）。

【００３３】ステップＳ６において、優先度判別部６０
８により待合せメモリ６０４から読出制御部６０６によ
り読出されたデータパケットが有効なデータパケットで
あるか、すなわち待合せを行なっているデータパケット
であるか否かの判別が行なわれる（ステップＳ８）。こ
れは待合せメモリ６０４において待合せているデータパ
ケットには有効フラグが立てられており、この有効フラ
グを見ることにより実行される。

【００３４】ステップＳ８において、有効なデータパケ
ットが存在しない場合、その入力データパケットは待合
せのため、パケット制御部６１０によりこの生成された
ハッシュアドレスに従って待合せメモリ６０４に格納さ
れ、有効フラグが立てられる（ステップＳ１０）。この
とき、合わせて有効データであることを示す有効データ
フラグが立てられる。

【００３５】ステップＳ８において、有効な待合せデー
タパケットが存在する場合、優先度判別部６０８により
入力データパケットと読出されたデータパケットの行先
ノード番号および世代番号の一致／不一致が判別され
る。すなわち、ハッシュ衝突が生じたか否かの判別が行
なわれる（ステップＳ１２）。

【００３６】ステップＳ１２においてハッシュ衝突が生
じていないと判別された場合、それは対をなすデータで
ある。したがってこの状態では、パケット制御部６１０
により発火データパケットが生成され、未発火フラグは
オフ状態にリセットされて出力される（ステップＳ１
４）。

【００３７】ステップＳ１２においてハッシュ衝突が生
じていると判別された場合（これは図１７に示す優先度
判別部６０８が実行する）、この入力データパケットと
読出されたデータパケットとの優先順位の判別が行なわ
れる。優先順位基準に従って、世代番号の大小がまず比
較され、世代番号が小さい方が優先度が高いと判別され
る。世代番号が同じ場合には行先ノード番号が小さい方
が優先度が高いものと判定される。この判定基準に従っ
て優先度が高いと判別されたデータパケットは待合せメ
モリ６０４へ格納され、その有効データフラグがオン状
態とされる。

【００３８】一方、優先度が低いと判別されたデータパ
ケットは、その未発火フラグがオン状態に設定されて出
力される（ステップＳ１６）。

【００３９】上述の処理動作により、対データ検出ユニ
ット５６２においては、待合せのためのデータパケット
の格納、入力データパケットの保存（未発火フラグをオ
ン状態に設定して出力）、および発火パケットの生成の
いずれかが実行され、この処理結果がプログラム記憶ユ
ニット５６４へ伝達される。次に、図１７および図２１
を参照してプログラム記憶ユニットの動作について説明
する。

【００４０】まず、対データ検出ユニット５６２から伝
達されたデータパケットはその発火識別部６６０におい
て未発火フラグがオンであるかオフであるかの判別が行
なわれる（ステップＳ２０）。未発火フラグがオン状態
にあり、待合せデータパケットである場合には、そのま
ま出力される。未発火フラグがオフ状態にあり、発火デ
ータパケットの場合にはプログラム命令の次命令フェッ
チのため、プログラムメモリ６２２がアクセスされる
（ステップＳ２２）。このアクセスのためには、入力デ
ータパケットに含まれる行先ノード番号が利用される。
このとき、また対データ検出ユニット５６２と同様のハ
ッシュ演算が実行されてもよい。

【００４１】ステップＳ２２においてプログラムメモリ
６２２から読出されたデータ、すなわちデータフロープ
ログラムに従って、入力データパケットに対し以下の処
理が行なわれる。すなわち、入力データパケットの命令
フィールドＦ４および行先ノード番号フィールドＦ２の
行先ノード番号の更新が実行される。この更新の後、未
発火フラグはリセット状態とされて出力される。

【００４２】このプログラム記憶ユニットから出力され
るデータパケットは演算処理ユニット５５４へ与えられ
る。演算処理ユニット５５４は、入力されたデータパケ
ットの未発火フラグがオフ状態であれば、命令フィール
ドＦ４に含まれる命令に従ってそこに含まれるデータに
対し演算処理を施し、その処理結果をオペランドデータ
フィールドＦ５に格納する。

【００４３】演算処理ユニット５５４は、入力データパ
ケットの未発火フラグがオン状態の場合には演算処理は
実行しない。

【００４４】演算処理ユニット５５４の出力データパケ
ットは分岐ユニット５５６へ伝達される。分岐ユニット
５５６は、与えられたデータパケットの未発火フラグが
オフ状態にあれば、そこに含まれる行先ノード番号フィ
ールドＦ２に含まれる行先ノード番号に従って、装置外
部およびデータバッファ５５８の一方に選択的に出力す
る。与えられたデータパケットの未発火フラグがオン状
態の場合には、この分岐ユニット５５６は入力データパ
ケットをデータバッファ５５８へ伝達する。

【００４５】データバッファ５５８は、この処理装置５
０６を流れているデータパケットの揺らぎを吸収する。

【００４６】

【発明が解決しようとする課題】上述のように、データ
パケットが、対データ検出ユニット５６２→プログラム
記憶ユニット５６４→演算処理ユニット５５４→分岐ユ
ニット５５６→データバッファ５５８→合流ユニット５
５０→対データ検出ユニット５６２…と巡回し続けるこ
とによりプログラム記憶ユニット５６４に格納されたデ
ータフロープログラムに基づいた情報処理が進行する。
このデータパケットの巡回パスは、通常、パイプライン
化されている。

【００４７】対データ検出ユニット５６２において、未
発火フラグがオン状態とされたデータパケットも同様
に、対データ検出ユニット５６２→プログラム記憶ユニ
ット５６４→演算処理ユニット５５４→分岐ユニット５
５６→データバッファ５５８→合流ユニット５５０とこ
のデータ処理中のデータパケットと同様のパイプライン
化された巡回パスを巡回する。この未発火フラグがオン
状態のデータパケットはプログラム記憶ユニット５６４
および演算処理ユニット５５４で処理されることなく対
データ検出ユニット５６２における待合せメモリ６０４
の待合せ領域が利用可能となるまでこの巡回パスを巡回
し続ける。

【００４８】未発火状態のデータパケットが増加し、デ
ータバッファ５５８に格納されるデータパケットの数が
増加すると、この巡回パスにおけるパイプラインが長く
なる。このため、即座に処理することのできる可能性の
あるデータパケットがこの巡回パスを巡回する速度が低
下するという問題が生じる。

【００４９】また、すぐに処理可能なデータパケット
は、対データ検出ユニット５６２において検出され、速
やかに発火状態とされ、対データ検出ユニット６５２に
おける待合せメモリ６０４に空き領域を形成しなけれ
ば、未発火状態のデータパケットはいつまでも未発火状
態を維持することになり、処理が進行しない。この結
果、全体としての処理速度が低下する。この状態につい
て少し詳しく以下に説明する。

【００５０】図２２は、データ駆動型情報処理装置にお
ける巡回パスにおけるデータパケットの流れを例示する
図である。図２２において、データバッファ５５８は、
合流ユニット５５０、対データ検出ユニット５６２、プ
ログラム記憶ユニット５６４、演算処理ユニット５５４
および分岐ユニット５５６からなるパイプラインに収納
可能な数以上のデータパケットが存在するために、この
パイプラインのオーバフローを吸収するために複数のデ
ータパケットを格納する。データバッファ５５８に格納
されるデータパケットは合流ユニット５５０の入力に空
きが生じたときに合流ユニット５５０を介して対データ
検出ユニット５６２へ与えられる。

【００５１】今、データバッファ５５８に含まれるデー
タパケット１１０ａ、１０１ｂ、および１１０ｂに着目
する。これらのデータパケット１０１ｂ、１１０ａ、お
よび１１０ｂは、対データ検出ユニット５６２に含まれ
る待合せメモリ６０４の同一の待合せ領域を重複利用し
ているものとする。すなわち同一のハッシュアドレスを
生成するものとする。データパケット１０１ｂは、その
未発火フラグＮＲＦがオフ状態（“０”）にあり、対デ
ータ検出ユニット５６２において待っているデータパケ
ット１０１ａと対データとして検出されて発火する。デ
ータパケット１１０ａおよび１１０ｂは、未発火フラグ
ＮＲＦがオン状態（“１”）となっており、対データ検
出ユニット５６２においてデータパケット１０１ａが待
合せメモリ６０４の待合せ領域を使用しているため、未
発火フラグＮＲＦがオン状態とされ出力されたデータパ
ケットである。この仮定の下でデータパケットの処理の
流れについて説明する。

【００５２】データバッファ５５８は、先入れ先出し型
メモリである。データパケット１１０ａ、１０１ｂ、お
よび１１０ｂの出力順序は変化しない。

【００５３】まず、データパケット１１０ａが対データ
検出ユニット５６２へ与えられる。このデータパケット
１１０ａのための待合せ領域は優先度の高いデータパケ
ット１０１ａが利用している。したがって、データパケ
ット１１０ａは再び、未発火フラグをオン状態とされて
出力される。

【００５４】次に、データパケット１０１ｂが対データ
検出ユニット５６２へ与えられる。このデータパケット
１０１ｂは、待合せメモリ６０４に格納されているデー
タパケット１０１ａと対をなすため、対データとして検
出される。これにより、それまでデータパケット１０１
ａが格納されていた待合せ領域が空き領域となる。この
データパケット１０１ａおよび１０１ｂは対データとし
てプログラム記憶ユニット５６４へ出力される。

【００５５】その後、データパケット１１０ｂが対デー
タ検出ユニット５６２へ伝達されると、待合せメモリ６
０４の対応の待合せ領域へ格納される。再びデータパケ
ット１１０ａが対データ検出ユニット５６２へ入力され
るまで同一待合せ領域を共有しかつ優先順位の高い別の
データパケットが入力されなければ、データパケット１
１０ａが対データ検出ユニット５６２へ与えられると、
このデータパケット１１０ａとデータパケット１１０ｂ
が対データとして検出される。

【００５６】したがって、待合せメモリ６０４において
対応の待合せ領域が空き状態となるまで、優先順位の低
いデータパケットは未発火状態で巡回パス（パイプライ
ン）を巡回し続ける。また、データパケット１０１ｂ
は、データパケット１０１ａと対をなすデータである
が、データバッファ５５８へ入力された順序で対データ
検出ユニット５６２へ与えられるため、発火可能なデー
タパケットの処理が遅れ、この処理装置の処理速度が低
下する。また、未発火状態のデータパケット１１０ａお
よび１１０ｂはデータパケット１０１ａが対データとし
て検出されて消費されるまでこの巡回パスを巡回し続け
る。このデータパケット１１０ａおよび１１０ｂの処理
が遅れ、このため全体としての処理速度が低下する。

【００５７】また、データバッファ５５８はたとえばシ
フトレジスタ型の先入れ先出し型メモリで構成される。
この場合、データバッファ５５８において空き領域が存
在しても、入力データパケットがこのデータバッファ５
５８において受ける遅延時間は一定である。したがっ
て、このデータバッファ５５８における遅延により有効
データパケットが高速で巡回パスを巡回することができ
ず、このため処理速度が低下する。

【００５８】それゆえ、この発明の目的は、データフロ
ープログラムを高速かつ効率的に処理することのできる
データ駆動型情報処理装置を提供することである。

【００５９】この発明の他の目的は、未発火データパケ
ットの発生を抑制することのできるデータ駆動型情報処
理装置を提供することである。

【００６０】この発明のさらに他の目的は、格納データ
数に応じて遅延時間を変更することのできるデータバッ
ファを提供することである。

【００６１】この発明のさらに他の目的は、データフロ
ープログラムの処理効率を改善することのできるデータ
バッファを提供することである。

【００６２】

【課題を解決するための手段】請求項１に係るデータ駆
動型情報処理装置は、データ巡回パス上の一方からのデ
ータを受けて一時的に格納しかつ格納データをこの巡回
パスを介して対データ検出ユニットへ伝達するバッファ
メモリ回路を含む。このバッファメモリ回路は、データ
を格納するための格納部と、入力データおよび格納デー
タに含まれるキーデータに従って予め定められた順序で
格納データが格納されるようにこの受けた入力データに
含まれるキーデータと格納データのキーデータとに従っ
て格納部の格納データを再配列する回路手段を含む。

【００６３】請求項２に係るデータ駆動型情報処理装置
は、このデータ再配列手段が、対データ検出部において
実行される優先度判別基準と同様の判別基準に従って格
納データの再配列を行なう手段を含む。

【００６４】請求項３に係るデータバッファは、入力デ
ータを受ける入力部と、出力データを出力する出力部と
の間のデータ伝送路に沿って配置され、入力データを順
次格納しかつ出力するための、互いに縦続接続された複
数のデータメモリと、このデータ伝送路の鏡映対象の位
置のデータメモリに対して設けられ、出力部側のデータ
メモリに格納されたデータが存在しないとき入力部側デ
ータメモリのデータをこの読出出力部側データメモリに
転送する第１の転送手段と、鏡映対象の位置のデータメ
モリに設けられ、入力部側データメモリに格納されたデ
ータに含まれる所定のキーデータと出力部側データメモ
リに格納されるデータの所定のキーデータとを比較する
比較手段と、この比較手段の比較結果に従って出力部側
データメモリの格納データと入力部側データメモリの格
納データとを交換する手段とを含む。

【００６５】

【作用】請求項１に係るデータ駆動型情報処理装置にお
いては、再配列手段によりデータバッファ内のデータパ
ケットはそこに含まれるキーデータに従って所定の順序
で配列されて対データ検出ユニットへ順次伝達される。
これにより、データフロープログラムを効率的に処理す
る順序で対データ検出ユニットへデータパケットを与え
ることが可能となる。

【００６６】請求項２に係るデータ駆動型情報処理装置
においては、対データ検出ユニットで利用される優先度
判別基準と同様の判別基準に従ってデータバッファ内の
データパケットが再配列される。これにより、待合せ状
態のデータパケットに対し対を形成し発火する可能性の
大きいデータパケットが早く対データ検出ユニットへ伝
達される。

【００６７】請求項３に係るデータバッファにおいて
は、出力部側データメモリに格納データが存在しないと
き第１の転送手段により入力部側データメモリからその
出力部側データメモリへデータが転送されるため、デー
タバッファの記憶段数を格納データの数に応じて変更す
ることができ、高速でデータを出力することが可能とな
る。

【００６８】また、キーデータの大小に応じて入力部側
データメモリと出力部側データメモリとの交換を行なう
ことにより、出力データ列を常時キーデータの大小に応
じて配列することが可能となり、データ処理内容に応じ
たデータの再配列を容易かつ確実に実現することが可能
となる。

【００６９】

【実施例】図１はこの発明の一実施例であるデータ駆動
型情報処理装置の構成を示す図である。図１において
は、データ駆動エンジン部の構成が機能的に示される。
図１に示す構成において、図１６に示す構成と同一部分
には同一の参照番号を付しその詳細説明は省略する。図
１において、分岐ユニット５５６と合流ユニット５５０
との間に、データパケットの流れの揺らぎを吸収するた
めのデータバッファ１が設けられる。データバッファ１
は、分岐ユニット５５６からのデータパケットを格納す
るためのメモリユニット２と、このメモリユニット２に
格納されたデータパケットをキーデータの大小関係に従
って再配列する再配列制御ユニット１０を含む。

【００７０】再配列制御ユニット１０は、分岐ユニット
５５６から与えられる入力データパケットから予め定め
られたキー（データ）を検出するキー検出部４と、メモ
リユニット２に格納されたデータパケットの各キーを監
視するキーモニタ３と、キーモニタ３からのキー情報と
キー検出部４からのキー情報を比較しその大小関係を示
す信号を出力するキー比較部５と、このキー比較部５か
らの比較結果情報に従ってメモリユニット２内のデータ
パケットの配列順序を入れ替える配列制御部６を含む。

【００７１】用いられるキーとしては、図２に示すよう
に、上位から未発火フラグＮＦＲ（未発火時“１”）、
世代番号、および行先ノード番号を用いる。世代番号お
よび行先ノード番号は、対データ検出ユニット５６２に
おける優先度を判別するための判別基準として利用され
ている。したがって、この対データ検出ユニット５６２
に用いられる優先度判別基準と同様の判別基準がデータ
バッファ１におけるデータパケット再配列評価基準とし
て利用される。

【００７２】図１において、対データ検出ユニット５６
２は、待合せデータパケットを格納する待合せメモリ６
０４と、この待合せメモリへのデータパケットの格納お
よび読出ならびに優先度の判別とを実行する書込／制御
部２０を含む。この書込／読出制御部２０は、図１７に
示す構成において命令識別部６０２、読出制御部６０
６、優先度判別部６０８およびパケット制御部６１０を
含む。次に動作について説明する。データバッファ１を
除くユニットすなわち、合流ユニット５５０、対データ
検出ユニット５６２、プログラム記憶ユニット５６４、
演算処理ユニット５５４および分岐ユニット５５６の動
作は図１６および図１７に示す従来のデータ駆動型情報
処理装置のそれと同様である。したがって以下の説明に
おいてはこの発明において利用されるデータバッファ１
の動作についてのみ説明する。

【００７３】キー検出部４は、分岐ユニット５５６から
与えられる入力データパケットから所定のキーすなわち
未発火フラグＮＦＲ、世代番号および行先ノード番号を
抽出することによりキーデータを生成する。キーモニタ
３は、メモリユニット２に格納される各データパケット
のキーデータをモニタしている。データ入力時において
キー比較部５はこのキーモニタ３からのキーデータとキ
ー検出部４からのキーデータとを受け、その大小を比較
する。配列制御部６はこのキー比較部５からの比較情報
に従ってこのキーデータの小さい順に出力データパケッ
トが配列されるようにそのデータパケットを再配列す
る。したがって、メモリユニット２からデータパケット
が出力される場合には、（１）未発火フラグＮＦＲが立
っていないデータパケット（ＮＦＲ＝０）の方が未発火
フラグが立っているデータパケット（ＮＦＲ＝１）より
も先に、（２）未発火フラグＮＦＲが同じ状態にあるデ
ータパケットは世代番号が小さい方が先に、および
（３）未発火フラグＮＦＲが同じ状態にありかつ世代番
号が同じデータパケットは行先ノード番号が小さい方が
先に出力される。

【００７４】未発火フラグＮＦＲが立っていないすなわ
ちオフ状態のデータパケットは、待合せメモリ６０４に
対のデータパケットが格納されているかまたはこれから
待合せメモリ６０４に格納される可能性が高い。また、
未発火フラグＮＦＲが同じ状態にあれば、世代番号が小
さい方が先に実行される可能性が高い。また、未発火フ
ラグＮＦＲが同じ状態でありかつ世代番号が同じであれ
ば、行先ノード番号が小さい方が先に処理される可能性
が高い（データフロープログラムでは、通常データアー
クはノード番号の小さい方から大きい方へ流れる）。し
たがって、このような優先順位に従って出力データを再
配列して出力することにより、早く処理される可能性の
高いデータパケットを早く出力することができ、データ
フロープログラムの処理効率が高くなる。この動作を図
２２を参照して説明する。

【００７５】データバッファ１はデータ並べ換え機能す
なわちデータ再配列機能を備える。したがって、図２２
に示すように、データパケット１１０ａ、データパケッ
ト１０１ｂおよびデータパケット１１０ｂがこの順に入
力された場合、最も先に出力されるのは、未発火フラグ
ＮＲＦがオフ状態にあるデータパケット１０１ｂであ
る。このデータパケット１０１ｂは対データ検出ユニッ
ト５６２へ与えられ、待合せメモリ６０４内に格納され
ているデータパケット１０１ａと対を形成する。これに
よりデータパケット１０１ａおよび１０１ｂにより発火
パケットが生成され、データメモリ６０４の待合せ領域
に空きが生じる。

【００７６】次に、データパケット１１０ａが対データ
検出ユニット５６２へ与えられ、待合せメモリ６０４の
待合せ領域に格納される。

【００７７】その後、データパケット１１０ｂが対デー
タ検出ユニット５６２へ与えられる。出力データの再配
列により、データパケット１１０ａが与えられてからデ
ータパケット１１０ｂが対データ検出ユニット５６２へ
与えられる時間的な差は従来よりも小さくなっている。
データパケット１１０ａとデータパケット１１０ｂがメ
モリユニット２から出力される間にデータバッファ１に
対しより優先度の高いデータパケットの入力がないかま
たは合流ユニット５５０から外部から入力されたデータ
パケットがこのデータパケット１１０ａおよび１１０ｂ
の間に割り込まない限り、データパケット１１０ａとデ
ータパケット１１０ｂは連続して対データ検出ユニット
５６２へ与えられる。したがって、データパケット１１
０ａとデータパケット１１０ｂとが対データ検出ユニッ
ト５６２で対データとして検出されて発火するまでの間
に、待合せメモリ６０４の同一待合せ領域をアクセスす
るデータパケットが現われる可能性が小さくなってい
る。このデータパケットの出力再配列について具体的な
例について説明する。

【００７８】図３に、このデータバッファ１における出
力データの出力順序を並べ換える状態を概略的に示す。
待合せメモリ６０４においてキーデータ１０１０６Ｈが
待合せている状態を考える。今、メモリユニット２にお
ける出力データは００４０５Ｈ、００５０５Ｈ、１０２
０６Ｈ、１０３０７Ｈの順に配置されていた場合に新た
に００２０６Ｈのデータパケットが入力された状態を考
える。この新たに入力されたデータパケット００１０６
Ｈは待合せメモリ内の待合せデータパケット（キーデー
タ００１０６Ｈ）と対をなす。この場合、再配列制御ユ
ニットの機能の下に、新たに入力されたデータパケット
（キーデータ００１０６Ｈ）が未発火フラグＮＲＦがオ
フ（“０”）、世代番号が“０１”であるため最優先し
て出力される。この最優先して出力されるデータパケッ
トは待合せているデータパケットと対データを形成す
る。これにより待合せデータパケットの消費が行なわ
れ、待合せ領域に速やかに空き領域が生じ、未発火フラ
グがオン状態の未発火データパケットの巡回が防止され
る。ここで、対をなすデータはノード番号が同じであり
世代番号が同じデータパケットと想定している。出力デ
ータパケットとしてはキーデータ００４０５Ｈとキーデ
ータ１０４０５Ｈのデータパケットが対をなすため、対
をなすデータが短期間に対データ検出ユニットへ与えら
れる可能性が高い。これによりデータフロープログラム
の処理の高速化および処理効率の改善が得られる。

【００７９】上述のように、未発火フラグＮＦＲの大小
比較と、対データ検出ユニット５６２における優先度判
別と同様の優先度判別基準に従って優先順位を決定し、
この優先順位に基づいてメモリユニットに格納されてい
るデータパケットの順序を変更して出力することによ
り、すぐに処理される可能性のあるデータパケットは未
発火パケットに邪魔されることなく高速で巡回パス上に
送出することが可能となる。またこの出力データの順序
再配列により、データ待合せ領域が早く開放されること
が可能となる。さらに、対データとなる可能性の高いデ
ータパケット間の距離を近くすることが可能となり、対
データ検出ユニットにおけるデータ待合せ領域を効率的
に機能させることができ、データ処理のうえで無駄な動
きをしているように見える未発火データパケットの発生
を低減することが可能となる。これにより、データフロ
ープログラムの処理効率が向上する。

【００８０】次に、この出力データの再配列をキーデー
タの優先順位に従って行なうための構成について説明す
る。

【００８１】図４は、図１に示すデータバッファの具体
的構成の一例を示す図である。図４において、データバ
ッファ１は、入力データパケットを伝達するための互い
に縦続接続された選択入力機能付ラッチ１１０ａ、１１
０ｂ、１１０ｃ、…、および１１０ｎと、この入力デー
タパケット伝達用の選択入力機能付ラッチ１１０ａ〜１
１０ｎ各々に対応して設けられる互いに縦続接続された
出力データ伝達用選択入力機能付ラッチ２１０ａ、２１
０ｂ、２１０ｃ、…、および２１０ｎと、それぞれ対応
の選択入力機能付ラッチ１１０ｉおよび２１０ｉ（ｉ＝
ａ〜ｎ）の間に設けられ、この対応のラッチに格納され
たデータパケットのうちキーデータを抽出しその大小関
係を比較するとともにその比較結果に従って対応のラッ
チに格納されたデータの交換を制御するデータ入替え制
御回路３１０ａ、３１０ｂ、３１０ｃ、…、３１０ｎを
含む。

【００８２】入力部１０１ａへ与えられる入力データパ
ケットＤＩはｍ−１ビットのデータ幅を有し、信号線１
０２を介して与えられる有効データフラグＶＬＤが１ビ
ット付加される。したがって、この選択機能付ラッチの
一方入力Ａへはｍビットのデータが与えられる。この選
択入力機能付ラッチ１１０ａ〜１１０ｎは、クロック入
力１０３を介して与えられる入力データ転送クロックＣ
ＫＦに従ってその格納データを次段の選択入力機能付ラ
ッチへ転送する。このラッチ１１０ａ〜１１０ｎに格納
される有効データフラグＶＬＤが“１”（“Ｈ”レベ
ル）のときにはそのラッチに格納されているデータパケ
ットが有効であることを示す。有効データフラグＶＬＤ
が“０”（“Ｌ”レベル）のとき、そのラッチに含まれ
ているデータパケットは無効であることを示す。

【００８３】出力データパケットを出力するための選択
入力機能付ラッチ２１０ａ〜２１０ｎはクロック入力２
０３を介して与えられる出力データ転送クロックＣＫＢ
に応答してその格納データを前段のラッチ（出力部２０
１に近い出力用の選択入力機能付ラッチ）へ転送する。

【００８４】データ入替え制御回路３１０ａ〜３１０ｎ
は、対応のラッチに格納されたｎビットのデータのうち
キーデータとしてｎビットのデータを抽出しそのキーデ
ータの大小関係に応じて入力部側のラッチから出力部側
のラッチへのデータの転送および入力部側ラッチと出力
部側ラッチとの間のデータを交換を実行する。このデー
タ入替え制御回路３１０ａ〜３１０ｎの比較結果はクロ
ック入力３０１へ与えられるクロック信号ＣＫＣに応答
して確定状態となる。

【００８５】図４において、図の右側に示されている入
力データ出力部１０１ｂ、状態フラグＦＵＬＬ出力信号
線１０５、クロック信号ＣＫＦを伝達する信号線１０
６、クロック信号ＣＫＣを伝達する信号線３０２、クロ
ック信号ＣＫＢを伝達する信号線２０６および出力デー
タを入力する信号線２０４はそれぞれこのデータバッフ
ァが次段のデータバッファに接続される状態を示す。こ
の図４に示すデータバッファは同一構成の回路成分を含
んでおり、容易に拡張することが可能である。信号線１
０５上に現われる状態フラグＦＵＬＬが“１”の場合、
この入力データ用のラッチ１１０ａ〜１１０ｎのすべて
に対し有効データが格納されている状態を示す。また信
号線２０４から与えられるｍ−１ビットのデータは
“０”の有効性フラグＶＬＤ（信号線２０５から与えら
れる）とともにｍビットのデータとなり、ラッチ２１０
ｎへ与えられる。信号線２０２から与えられる状態フラ
グＥＭＰＴＹは、この出力データ用のラッチ２１０ａ〜
２１０ｎに出力すべき有効データパケットが存在するか
否かを示す。この状態フラグＦＵＬＬおよびＥＭＰＴＹ
は、それぞれ信号線１０２から与えられる有効性フラグ
ＶＬＤおよび信号線２０５から与えられる有効性フラグ
ＶＬＤに対応する。

【００８６】次にこの図４に示すデータバッファのデー
タ入力動作および出力動作について説明する。まずデー
タ入力時の動作についてその動作フロー図である図５を
併せて参照して説明する。

【００８７】まず、信号線１０５から出力される状態フ
ラグＦＵＬＬが“０”であるか否かの判別が行なわれる
（ステップＳ３０）。状態フラグＦＵＬＬが“１”の場
合には、この入力データのためのラッチ１１０ａ〜１１
０ｎすべてに有効データが格納されていることを示して
おり、新たにデータパケットを入力することができない
ことを示している。したがってこの状態フラグＦＵＬＬ
が“０”となるまでデータパケットの入力は行なわれな
い。

【００８８】状態フラグＦＵＬＬが“０”となると、信
号線１０１ａにデータパケットＤＩが入力される。ｍ−
１ビットのデータパケットＤＩは有効データフラグＶＬ
Ｄ（“１”）とともにラッチ１１０ａへ与えられる。こ
こで、初期状態においてはリセットＲＥＳＥＴがラッチ
１１０ａ〜１１０ｎおよび２１０ａ〜２１０ｎへ与えら
れ、これらのラッチ１１０ａ〜１１０ｎおよび２１０ａ
〜２１０ｎに含まれる有効データフラグＶＬＤは“０”
にリセットされる。

【００８９】状態フラグＦＵＬＬが“０”であると、信
号線１０１ａを介してデータパケットＤＩが与えられ
る。ｍ−１ビットのデータパケットは信号線１０２から
の有効性を示す有効性フラグＶＬＤと共にｍビットのデ
ータとなってラッチ１１０ａの一方入力Ａへ与えられ
る。ラッチ１１０ａ〜１１０ｎにおける入力データパケ
ットＤＩおよび格納データＤｉおよび有効データフラグ
ＶＬＤ（以下、両者を含めて単にデータと称す）の取込
みおよびシフト動作はクロック信号ＣＫＦにより制御さ
れる。すなわち、クロック信号ＣＫＦが信号線１０３を
介して与えられると、ラッチ１１０ａ〜１１０ｎはその
ラッチデータを次段のラッチへ転送するとともに新たに
与えられたデータをラッチする。たとえば、ラッチ１１
０ａに格納されていたデータはラッチ１１０ｂへ転送さ
れ、ラッチ１１０ｂに格納されていたデータはラッチ１
１０ｃへ転送される（ステップＳ３２）。

【００９０】次に図４において互いに向かい合ったラッ
チの格納データが比較される。データ入替え制御回路３
１０ａないし３１０ｎは、入力データ用ラッチ１１０ｉ
（ｉはａないしｎのいずれか）に有効データが存在し
（有効データフラグＶＬＤが“１”）かつ出力データ用
のラッチ２１０ｉに有効データが存在しない（有効デー
タフラグＶＬＤ＝“０”）か否かを判別する（ステップ
Ｓ３４）。入力データ用のラッチ１１０ｉに有効データ
が存在し、出力データ用のラッチ２１０ｉに有効データ
が存在しない場合には、そのラッチ１１０ｉに格納され
ているデータＤＩと出力側ラッチ２１０ｉに格納されて
いるデータＱｉとの交換が実行される（ステップＳ３
８）。

【００９１】入力データ用のラッチ１１０ｉに有効デー
タが存在し（ＶＬＤ＝１）かつ出力側のラッチ２１０ｉ
にも有効データが存在する場合、その格納データＤＩお
よびＱｉから所望のｎビットのキーデータを抽出しその
キーデータＤｉ（ｎ）およびＱｉ（ｎ）の大小を比較す
る（ステップＳ３６）。入力用データのラッチ１１０ｉ
に格納されているデータＤｉのキーデータＤｉ（ｎ）の
方が出力用データのラッチ２１０ｉに格納されているデ
ータＱｉのキーデータＱｉ（ｎ）よりも小さい場合に
は、このデータ入替え制御回路の制御の下にデータＤｉ
とデータＱｉの交換がその他方入力ポートＢを介して実
行される（ステップＳ３８）。

【００９２】ステップＳ３６において、入力用データの
ラッチ１１０ｉに格納されているＤｉのキーデータＤｉ
（ｎ）が出力用データのラッチ２１０ｉに格納されてい
るデータＱｉのキーデータＱｉ（ｎ）よりも大きいかま
たは等しい場合にはデータの交換は実行されない。次い
で、再び入力データが与えられるのを待つ。これによ
り、出力部２０１に最も近いラッチ２１０ａにおいては
常にキーデータＱｉ（ｎ）が最も小さいデータが格納さ
れる。たとえば、初期状態において、まずデータＤＩが
与えられた場合、入力用データラッチ１１０ａに格納さ
れる。このラッチ１１０ａに格納されたデータはラッチ
２１０ａに転送される（初めて入力データパケットＤＩ
が与えられたとき、出力用ラッチ２１０ａには有効デー
タは格納されていないためである）。次に入力データパ
ケットが与えられると、ラッチ２１０ａに格納されてい
るデータのキーデータと新たに与えられた入力データの
キーデータとの大小の比較が行なわれる。この大小の比
較結果に従ってデータの交換が行なわれるかまたは行な
われない。次にデータパケットが新たに格納されると、
この２番目のデータパケットがラッチ１１０ｂへ転送さ
れ次いでラッチ２１０ｂへ転送される（出力データがま
だ出力されていない状態）。３番目に入力されたデータ
パケットのキーデータとこのラッチ２１０ａに格納され
ているデータのキーデータとの大小比較が行なわれる。
この動作を繰返し行なうことにより出力データ用ラッチ
２１０ａには最小のキーデータを有するデータがラッチ
され、次段の出力用データラッチ２１０ｂには２番目に
小さいキーデータを有するデータがラッチされる。すな
わち、この出力側のデータラッチ２１０ａ〜２１０ｎに
おいてはこのキーデータの大小関係に従って出力データ
が再配列されて格納される。次にデータ読出動作につい
てその動作フロー図である図６を併せて参照して説明す
る。

【００９３】データを出力する場合には、まず信号線２
０２から与えられる状態フラグＥＭＰＴＹが“１”であ
るか否かの判別が行なわれる（ステップＳ４０）。この
状態フラグＥＭＰＴＹが“１”のとき、ラッチ２１０ａ
には有効データが格納されているため、データの出力が
可能である。状態フラグＥＭＰＴＹが“０”の場合に
は、出力すべきデータは存在しないため、この状態フラ
グＥＭＰＴＹが“１”となるまでそのデータ出力は待ち
状態となる。

【００９４】データ出力時においては、信号線２０３上
へ出力データ用クロック信号ＣＫＢを与える。これによ
りラッチ２１０ａ〜２１０ｎがシフト動作を行ない、そ
のラッチデータを出力端子Ｙを介して前段のラッチへ伝
達するとともに、出力部２０１から出力データパケット
ＱＯが出力される（ステップＳ４２）。

【００９５】次に再び入替え制御回路３１０ａ〜３１０
ｎにおいて各対応のラッチ１１０ｉとラッチ２１０ｉと
の間でのデータ転送および交換の判別が実行される。す
なわち、ステップＳ４４において、出力用データラッチ
２１０ｉに格納されるデータＱｉの有効データフラグＶ
ＬＤが“１”であるか否かの判別が行なわれる。有効デ
ータフラグＶＬＤが“０”の場合には出力データ用ラッ
チ２１０ｉに有効データが存在しないため、対応の入力
データ用のラッチ１１０ｉからデータの転送が行なわれ
る（ラッチ１１０ｉに有効データが存在する場合）。

【００９６】ステップＳ４４において、ラッチ２１０ｉ
に含まれるデータＱｉの有効データフラグＶＬＤが
“１”の場合、次いでこのデータＤｉおよびＱｉのキー
データＤｉ（ｌ）およびＱｉ（ｎ）の大小比較が行なわ
れる。入力データ用ラッチ１１０ｉに含まれるデータＤ
ｉのキーデータＤｉ（ｌ）が出力用データＱｉのキーデ
ータＱｉ（ｎ）よりも小さい場合にはラッチ１１０ｉと
ラッチ２１０ｉとの間でのデータの交換が行なわれる
（ステップＳ４８）。

【００９７】キーデータＤｉ（ｌ）がキーデータＱｉ
（ｌ）以上の場合にはデータの交換は行なわれない。こ
のステップＳ４６における判別動作およびステップＳ４
８におけるデータの交換動作によりラッチ２１０ａに確
実に最小のキーデータＱｉ（ｎ）を有するデータが配置
される。

【００９８】この図４に示すデータバッファにおいて
は、そのデータを記憶する段数は格納データ数に応じ可
変である。すなわちクロック信号ＣＫＦおよびＣＫＣを
与えるとデータが入力され、クロック信号ＣＫＢおよび
ＣＫＣを与えると直ちにデータが出力される。したがっ
て、シフトレジスタ構成のバッファメモリと異なり、そ
の有効データの数に応じてデータパケットが受ける伝達
遅延を変更することができ、常に即座に高速でデータパ
ケットを対データ検出ユニットへ伝達することができ
る。次に各回路部分の具体的構成および動作について説
明する。

【００９９】図７は、図４に示す選択入力機能付ラッチ
の構成を示す図である。この選択入力機能付ラッチ１１
０（および２１０）は、入力ポートＡに与えられる入力
データＤＡ（ｍビット）と入力ポートＢに与えられる入
力データＤＢ（ｍビット）の一方をそのクロック入力Ｃ
Ｋ１およびＣＫ２に与えられるクロック信号ＣＫ１およ
びＣＫ２に従って取込みかつ出力する。すなわち、クロ
ック信号ＣＫ１がクロック入力ＣＫ１に与えられたとき
には入力ポートＡに与えられた入力データＤＡを取込
み、クロック入力ＣＫ２にクロック信号ＣＫ２が与えら
れたとき入力ポートＢに与えられた入力データＢを取込
む。このラッチ１１０（２１０）は、対応のクロック信
号の立下がりで取込んだデータをその出力ポートＹから
出力する。このラッチ１１０（２１０）は、図４に示す
構成において、入力ポートＡに隣接ラッチからの出力デ
ータを受け、その入力ポートＢに対応の向かい合ったラ
ッチ（出力データ用ラッチまたは入力データ用ラッチ）
の出力を受ける。これにより、データの交換および転送
を行なうことができる。

【０１００】図８はこの選択入力機能付ラッチの具体的
構成の一例を示す図である。図８において、選択入力機
能付ラッチは、クロック入力ＣＫ１に与えられるクロッ
ク信号ＣＫ１に応答して入力ポートＡに与えられる信号
を通過させるｎチャネルＭＯＳトランジスタ（絶縁ゲー
ト型電界効果トランジスタ）４０１と、トランジスタ４
０１の出力を受ける２段の縦続接続されたインバータ回
路４０２および４０４と、クロック入力ＣＫ１に与えら
れた信号をインバータ回路４１０を介してそのゲートに
受け、インバータ回路４０４の出力をインバータ回路４
０２の入力へ伝達するｎチャネルＭＯＳトランジスタ４
０６と、クロック入力ＣＫ１およびＣＫ２にそれぞれ与
えられるクロック信号ＣＫ１およびＣＫ２を受けるＯＲ
回路４２８と、ＯＲ回路４２８の出力に応答してリセッ
トされかつインバータ回路４１０の出力に応答してセッ
トされるＲＳフリップフロップ４１２と、ＲＳフリップ
フロップ４１２の出力φ１に応答してインバータ回路４
０４の出力を出力ポートＹへ伝達するｎチャネルＭＯＳ
トランジスタ４０８を含む。ＲＳフリップフロップ４１
２は、セット入力Ｓへ与えられる信号の立上がりに応答
してセット状態とされ、その出力信号φ１を“Ｈ”に設
定し、リセット入力Ｒに与えられる信号の立上がりに応
答してリセット状態とされ、その出力信号φ１を“Ｌ”
に立下げる。

【０１０１】選択入力機能付ラッチはさらに、入力ポー
トＢに与えられる信号をクロック入力ＣＫ２に与えられ
るクロック信号ＣＫ２に応答して伝達するｎチャネルＭ
ＯＳトランジスタ４１４と、トランジスタ４１４が伝達
する信号を増幅する２段の縦続接続されたインバータ回
路４１６および４１８と、クロック信号ＣＫ２を反転す
るインバータ回路４２４と、インバータ回路４２４の出
力に応答してインバータ回路４１８の出力をインバータ
回路４１６の入力へ帰還させるｎチャネルＭＯＳトラン
ジスタ４２２と、インバータ回路４２４の出力に応答し
てセット状態とされ、ＯＲ回路４２８の出力に応答して
リセット状態とされるＲＳフリップフロップ４２６と、
ＲＳフリップフロップ４２６の出力信号φ２に応答し
て、インバータ回路４１８の出力を出力ポートＹへ伝達
するｎチャネルＭＯＳトランジスタ４２０を含む。

【０１０２】この選択入力機能付ラッチにおいては、イ
ンバータ回路４０４および４１８の駆動力はインバータ
回路４０２および４１６の駆動力よりも大きくされてい
る。これにより、トランジスタ４０６および４２２がオ
ン状態となったとき、ラッチ回路が構成される。

【０１０３】この選択入力機能付ラッチはさらに、リセ
ット入力ＲＥＳＥＴに与えられるリセット信号に応答し
て、インバータ回路４０２および４１６の入力をそれぞ
れ接地電位にリセットするｎチャネルＭＯＳトランジス
タ４３０および４３２を含む。次に、この図７および図
８に示す選択入力機能付ラッチの動作についてその動作
波形図である図９を合わせて参照して説明する。

【０１０４】今、フリップフロップ４１２がセット状態
にあり、信号φ１が“Ｈ”の状態を考える。この状態に
おいては、トランジスタ４０８がオン状態であり、出力
ポートＹからは入力ポートＡに与えられたデータが出力
されていると想定する。この状態においては、トランジ
スタ４０６がオン状態であり、インバータ回路４０２お
よび４０４とトランジスタ４０６とによりラッチ回路が
構成されている。ＲＳフリップフロップ４２６はリセッ
ト状態にあり、信号φ２は“Ｌ”のレベルである。

【０１０５】この状態で、クロック入力ＣＫ１に与えら
れたクロック信号ＣＫ１が“Ｈ”に立上がると、インバ
ータ回路４１０の出力が“Ｌ”、ＯＲ回路４２８の出力
が“Ｈ”となる。これにより、ＲＳフリップフロップ４
１２がリセット状態とされ、信号φ１が“Ｌ”に立下が
り、トランジスタ４０８がオフ状態となる。一方トラン
ジスタ４０１はクロック信号ＣＫ１に応答してオン状態
となり、入力ポートＡに与えられたデータＤＡを通過さ
せる。トランジスタ４０６はまだオフ状態であり、単に
このトランジスタ４０１からのデータはインバータ回路
４０２および４０４により増幅されているだけである。

【０１０６】クロック信号ＣＫ１が“Ｌ”へ立下がる
と、トランジスタ４０１がオフ状態、トランジスタ４０
６がオン状態となり、それまでに与えられていた信号が
インバータ回路４０２および４０４とトランジスタ４０
６からなるラッチ回路によりラッチされる。インバータ
回路４１０の出力信号が“Ｈ”に立上がり、ＲＳフリッ
プフロップ４１２がセット状態とされ、信号φ１が
“Ｈ”に立上がる。これにより、インバータ回路４０４
の出力が出力ポートＹへ伝達され、出力データＤＯとし
て出力される。

【０１０７】次に、クロック入力ＣＫ２に与えられるク
ロック信号ＣＫ２が“Ｈ”となると、ＯＲ回路４２８の
出力が“Ｈ”となり、ＲＳフリップフロップ４１２がリ
セットされ、信号φ１が“Ｌ”に立下がる。トランジス
タ４１４が、このクロック信号ＣＫ２に応答してオン状
態となり、入力ポートＢに与えられていた信号を通過さ
せる。トランジスタ４１４および４２２はまだオフ状態
であり、この入力ポートＢに与えられた信号はインバー
タ回路４１６および４１８により増幅される。

【０１０８】次にクロック信号ＣＫ２が“Ｌ”に立下が
ると、トランジスタ４１４がオフ状態となり、トランジ
スタ４２２がオン状態となる。これにより、それまでに
与えられていた信号がインバータ回路４１６および４１
８とトランジスタ４２２とによりラッチされる。クロッ
ク信号ＣＫ２の立下がりに応答してインバータ回路４２
４の出力が“Ｈ”に立上がり、ＲＳフリップフロップ４
２６がセットされ、信号φ２が“Ｈ”に立上がり、トラ
ンジスタ４２０がオン状態となる。これにより出力ポー
トＹへはインバータ回路４１８の出力が伝達される。

【０１０９】上述のようにして、クロック入力ＣＫ１に
クロック信号が与えられた場合には、入力ポートＡに与
えられた信号が選択され、クロック入力ＣＫ２にクロッ
ク信号が与えられると入力ポートＢに与えられた信号が
出力される。

【０１１０】なお、図８に示す構成において、クロック
信号ＣＫ１またはＣＫ２が“Ｈ”に立上がったとき、ト
ランジスタ４０８および４２０はオフ状態となり、出力
ポートＹの信号状態が不安定となることが考えられる。
この場合クロック信号ＣＫ１およびＣＫ２のＯＲをとっ
た信号により活性化されるラッチ回路がこの出力ポート
Ｙにさらに設けられてもよい。これにより、確実にデー
タを転送することが可能となる。このラッチ回路は、ク
ロック信号ＣＫ１およびＣＫ２が“Ｌ”のとき与えられ
た信号をそのまま通過させるスルー状態となる。

【０１１１】このようなラッチ回路の構成としては、イ
ンバータ回路４０２および４０４とトランジスタ４０６
からなるラッチ回路の構成を適用することができる。

【０１１２】この図７および図８に示す構成を図４に示
す構成に対応させれば、入力ポートＡには隣接するラッ
チ回路の出力が与えられ、入力ポートＢには、向かい合
った対応の入力部側または出力部側からのラッチの出力
が与えられる。クロック入力ＣＫ１は、クロック信号Ｃ
ＫＦまたはＣＫＢであり、クロック入力ＣＫ２へはデー
タ入替え制御回路からの比較結果指示信号が与えられ
る。

【０１１３】この選択入力機能付ラッチにラッチされる
データは、（ｍ−１）ビットのデータパケットと、この
ラッチされているデータが有効であるか否かを示す１ビ
ットの有効データフラグＶＬＤである。有効データフラ
グＶＬＤが“１”であれば、そのバッファに蓄えられて
いるデータが有効であることを示す。

【０１１４】図１０は、図４に示すデータ入替え制御回
路の構成を示す図である。図１０において、データ入替
え制御回路３１０は、信号線３０１および３０２を介し
てｎビットのデータを受ける。このｎビットのデータは
（ｎ−１）ビットのキーデータと１ビットの有効データ
フラグＶＬＤとを含む。図１０においては、この入力デ
ータを区別するため、一方の入力データの有効データフ
ラグをＶＬＤＡ、他方の入力データの有効データフラグ
をＶＬＤＢとして示す。

【０１１５】データ入替え制御回路３１０はさらに、こ
の信号線３０１から与えられたｎビットのデータうち
（ｎ−１）ビットのキーデータを受ける入力ポートＡ
と、信号線３０２を介して与えられるｎビットのデータ
のうち（ｎ−１）ビットのキーデータを受けるＢポート
と、この入力ポートＡおよびＢに与えられたキーデータ
の大小を比較しその比較結果を出力する出力ポートＬＴ
とを有する比較器３５０と、比較器３５０の出力ＬＴ
（出力ポートと出力信号とを同じ符号で示す）と有効デ
ータフラグＶＬＤＡおよびＶＬＤＢを受ける３入力ＡＮ
Ｄ回路３１０と、有効データフラグＶＬＤＡをその真入
力に受け、他方有効データフラグＶＬＤＢを偽入力に受
けるゲート回路３２０と、ＡＮＤ回路３１０の出力とゲ
ート回路３２０の出力を受けるＯＲ回路３３０と、比較
指示信号ＣＫＣとＯＲ回路３３０の出力とを受けるＡＮ
Ｄ回路３４０を含む。ＡＮＤ回路３４０からデータの交
換を行なう入替え指示信号ＣＫＣＨが発生される。この
信号ＣＫＣＨは図７および図８に示すクロック信号ＣＫ
２に対応する。

【０１１６】比較器３５０は入力ポートＡに与えられた
（ｎ−１）ビットのデータが入力ポートＢに与えられた
（ｎ−１）ビットのデータよりも小さいときにその出力
ポートＬＴから“１”の信号を出力する。この場合、比
較器３５０は、キーデータの昇順に出力データを再配列
する。比較器３５０の大小判断基準を逆にすれば降順に
再配列することが可能である。以下の説明においては、
データパケットをキーデータの小さい順に配列する必要
があるため、比較器３５０がデータを昇順に再配列する
場合の動作について説明する。データを降順に再配列す
る場合も容易に実現することができる。

【０１１７】２つのラッチ１１０および２１０からの出
力のうちｎビットのキーデータがデータ入替え制御回路
３１０へ与えられる。比較器３５０は入力ポートＡおよ
びＢにそれぞれ与えられた（ｎ−１）ビットのデータの
値の大小を比較する。入力ポートＡに与えられるデータ
値が入力ポートＢに与えられる（ｎ−１）ビットのデー
タ値よりも小さいときにその出力ポートＬＴが“１”と
なる。

【０１１８】ＡＮＤ回路３１０は、比較器３５０の出力
ＬＴと有効データフラグＶＬＤＡおよびＶＬＤＢを受け
る。有効データフラグＶＬＤＡは入力部側に設けられた
データラッチに格納されているデータの有効／無効を示
すフラグであり、有効データフラグＶＬＤＢは、出力部
側に設けられたラッチに格納されているデータの有効／
無効を示すフラグである。ＡＮＤ回路３１０は、その３
入力がすべて“Ｈ”（“１”）のとき、“Ｈ”の信号を
出力する。したがって、ＡＮＤ回路３１０から“１”の
信号が出力されるのは次の場合である。すなわち、有効
データフラグＶＬＤＡおよびＶＬＤＢが共に“１”にあ
り、比較器３５０の出力ＬＴが“１”の場合である。こ
の状態は、入力データ用ラッチ１１０に有効データが格
納されており、かつ出力データ用ラッチ２１０に有効デ
ータが格納されており、かつ入力データ用ラッチ１１０
に格納されたデータのキーデータが出力データ用ラッチ
２１０のラッチするデータのキーデータよりも小さい場
合である。

【０１１９】ゲート回路３２０は、有効データフラグＶ
ＬＤＡが“１”でありかつ有効データフラグＶＬＤＢが
“０”のときにのみ“１”の信号を出力する。ＯＲ回路
３３０は、ＡＮＤ回路３１０およびゲート回路３２０の
出力の一方が“１”であれば“１”の信号を出力する。
ＡＮＤ回路３４０は、クロック信号ＣＫＣに応答してＯ
Ｒ回路３３０の出力を伝達する。したがって、ＡＮＤ回
路３４０の出力ＣＫＣＨが“１”となるのは、次の２つ
の場合である。（１）入力データ用ラッチ１１０および
出力データ用ラッチ２１０に共に有効データがラッチさ
れており、かつその入力データ用ラッチ１１０に格納さ
れるキーデータが出力用ラッチ２１０に格納されるキー
データよりも小さいとき、および（２）入力データ用ラ
ッチ１１０に有効データがラッチされかつ出力データ用
ラッチ２１０に有効データがラッチされていない場合。

【０１２０】ＡＮＤ回路３４０の出力信号ＣＫＣＨは、
図７および図８に示すクロック入力ＣＫ２へ与えられ
る。これにより、データの交換が実現される。

【０１２１】図１１は、この図４に示す回路の全体の動
作を示す信号波形図である。以下、全体の動作について
簡単に説明する。

【０１２２】入力データＤＩを与える場合には、状態フ
ラグＦＵＬＬが“０”であることを確認した後にクロッ
ク信号ＣＫＦを与える。これにより入力データ用ラッチ
１１０ａ〜１１０ｎにおいて入力データの取込み、ラッ
チおよび出力が行なわれる。

【０１２３】次いで、比較制御信号ＣＫＣが与えられ、
データ入替え制御回路３１０が比較結果をこの制御信号
ＣＫＣに従って出力する。この制御信号ＣＫＣに従っ
て、入替え制御信号ＣＫＣＨが“１”または“０”とな
り、データの再配列が実行される。

【０１２４】状態フラグＦＵＬＬが“１”の場合には、
このデータバッファ１に有効データが一杯格納されてい
ることを示しており、新たにデータを入力することがで
きないことを示している。

【０１２５】データを出力する場合には、状態フラグＥ
ＭＰＴＹが“１”であることを確認した後に出力クロッ
ク信号ＣＫＢを与える。データを出力した後、制御信号
ＣＫＣを与える。これにより信号ＣＫＣＨが“１”また
は“０”となり、再び出力データの再配列が実行され
る。状態フラグＥＭＰＴＹが“０”の場合は、データバ
ッファ１においては有効出力データが存在しないことを
示しており、データを出力することができない。

【０１２６】この図４に示すデータバッファは、選択入
力機能付ラッチ１１０および２１０とデータ入替え制御
回路３１０が規則的に配置されている。すなわち、この
図４に示すデータバッファ１は、同じ回路構成を備える
単位回路が規則的に繰返し配置されている。したがっ
て、このデータバッファ１は、容易に拡張することがで
き、その収納することのできるデータの数を増加させる
ことができる。

【０１２７】さらに、このデータバッファは単にデータ
駆動型情報処理装置におけるデータパケットの再配列の
用途のみに適用されるものではない。一般に、データの
配列順序を予め定められた規則に従って変更する必要の
ある用途において適用可能である。データに含まれるキ
ーデータ（データそのものであってもよい）の大小関係
に応じてそのデータの配列順序が決定される用途に適用
可能である。

【０１２８】図１２は、このデータバッファの一般的構
成を示す。図１２において、データバッファ回路９００
は、３段のカスケード接続されたデータバッファ１ａ、
１ｂおよび１ｃと、このデータバッファのデータの入出
力を制御するための入出力制御部９５０を含む。データ
バッファ１ａ、１ｂおよび１ｃは図４に示すデータバッ
ファ１と同じ構成を備える。入出力制御部９５０は、入
力データ伝送路に沿って与えられる有効データフラグＶ
ＬＤを受ける入力ＦＵＬＬと、出力データ伝送路に沿っ
て出力される有効データフラグＶＬＤを受ける入力ＥＭ
ＰＴＹと、入力要求信号ＩＮＲＥＱを受ける入力ＰＵＳ
Ｈと、出力要求信号ＯＴＲＥＱを受ける入力ＰＯＰと、
入力許可信号ＩＮＡＣＫを出力する出力ＡＣＫＩと、出
力要求に対する許可を示す出力許可信号ＯＴＡＣＫを出
力する出力ＡＣＫＯと、クロック信号ＣＫＦ、ＣＫＣお
よびＣＫＢを出力するクロック出力ＣＫＦ、ＣＫＣ、お
よびＣＫＢを含む。

【０１２９】入出力制御部９５０は、入力ＦＵＬＬに与
えられる有効データフラグＶＬＤの“１”および“０”
に従って入力要求信号ＩＮＲＥＱに対する許可信号ＩＮ
ＡＣＫを“１”または“０”にし、入力データの受付の
許可および待機を制御する。

【０１３０】入出力制御部９５０はさらに、入力ＥＭＰ
ＴＹに与えられる有効データフラグＶＬＤの“１”およ
び“０”に従って、出力要求信号ＯＴＲＥＱに対する許
可信号ＯＴＡＣＫを“１”または“０”に設定する。こ
れにより、データバッファ１ａ〜１ｃにラッチされてい
るデータの格納状況に応じてデータの入出力が実行され
る。入出力制御部９５０は、インターフェイス回路であ
り、出力要求信号ＯＴＲＥＱが与えられ、出力許可信号
ＯＴＡＣＫを出力したとき、クロック信号ＣＫＢおよび
ＣＫＣを発生する。入出力制御部９５０はまた、入力要
求信号ＩＮＲＥＱが与えられかつ入力許可信号ＩＮＡＣ
Ｋが発生されたとき、クロック信号ＣＫＦおよびＣＫＣ
を発生する。

【０１３１】

【発明の効果】請求項１に係るデータ駆動型情報処理装
置によれば、データパケットに含まれるキーデータに従
って出力データパケットが再配列される。これにより、
データフロープログラムを効率的に処理する順序で対デ
ータ検出ユニットへデータパケットが与えられ、データ
処理効率が増大する。また、対データ検出ユニットにお
いて未発火フラグが立てられたデータパケットの数が増
大しても、この出力データパケットの再配列によりデー
タ処理の効率が低下することはない。

【０１３２】請求項２に係るデータ駆動型情報処理装置
においては、出力データパケットの配列は、対データ検
出ユニットにおける優先順位判別基準と同じ判別基準に
従って実行されている。このため、対データとなる可能
性のあるデータパケットを近接させることができ、対デ
ータ検出ユニットのデータ待合せ領域を効率的に利用す
ることが可能となり、未発火データパケットの発生を抑
制することができ、データフロープログラムの処理効率
を向上することが可能となる。

【０１３３】請求項３に係るデータバッファによれば、
格納されているデータの内容に従って出力データの配列
順序が変更可能であり、高速で処理内容に応じて配列さ
れた出力データ系列を得ることができる。また、格納デ
ータの数によりその記憶段数を変更することができるた
め、格納データの数にかかわらず、その記憶段に空きが
生じることがなく、高速でデータの出力を行なうことが
でき、データ処理効率を向上させることができる。また
このデータバッファは同じ構造を有する回路が規則的に
配列されているため、そのレイアウトが容易でありかつ
また規模も容易に拡張することができる。

【図面の簡単な説明】

【図１】この発明の一実施例であるデータ駆動型情報処
理装置のエンジンの構成を示す図である。

【図２】この発明の一実施例であるデータ駆動型情報処
理装置において利用されるキーデータの構成を示す図で
ある。

【図３】この発明の一実施例であるデータ駆動型情報処
理装置におけるデータ再配列動作を例示する図である。

【図４】図１に示すデータバッファの構成を示す図であ
る。

【図５】図４に示すデータバッファのデータ入力動作を
示すフロー図である。

【図６】図４に示すデータバッファのデータ出力動作を
示すフロー図である。

【図７】図４に示す選択入力機能付ラッチの外部構成を
示す図である。

【図８】図７に示す選択入力機能付ラッチの具体的構成
を示す図である。

【図９】図７および図８に示す選択入力機能付ラッチの
動作を示す信号波形図である。

【図１０】図４に示すデータ入替え制御回路の構成を示
す図である。

【図１１】図４に示すデータバッファの全体の動作を示
す信号波形図である。

【図１２】図４に示すデータバッファを拡張した際の構
成を示す図である。

【図１３】データフローグラフの一例を示す図である。

【図１４】データ駆動型情報処理装置のエンジンにおい
て利用されるデータパケットの構成を示す図である。

【図１５】データ駆動型情報処理装置の全体の構成を示
す図である。

【図１６】図１５に示すデータ駆動エンジンの構成を示
すブロック図である。

【図１７】図１６に示すプログラム記憶付発火制御部の
構成を示すブロック図である。

【図１８】ハッシュ演算を説明するための図である。

【図１９】メモリ空間の縮退を説明するための図であ
る。

【図２０】図１７に示す対データ検出ユニットの動作を
示すフロー図である。

【図２１】図１７に示すプログラム記憶ユニットの動作
を示すフロー図である。

【図２２】従来のデータ駆動型情報処理装置の問題点を
説明するための図である。

【符号の説明】 １ データバッファ ２ メモリユニット ３ キーモニタ ４ キー検出部 ５ キー比較部 ６ 配列制御部 １０ 再配列制御ユニット １１０ａ〜１１０ｎ 入力データ用選択入力機能付ラッ
チ ２１０ａ〜２１０ｎ 出力データ用選択入力機能付ラッ
チ ３１０ａ〜３１０ｎ データ入替え制御器 ５０６ データ駆動エンジン ５５０ 合流ユニット ５５２ プログラム記憶付発火制御部 ５５４ 演算処理ユニット ５５６ 分岐ユニット ５５８ データバッファ ５６２ 対データ検出ユニット ５６４ プログラム記憶ユニット ９００ データバッファ回路 ９５０ 入出力制御部

Claims (3)

【特許請求の範囲】
1. 【請求項１】 データ巡回パスを有しかつ前記データ巡
   回パス上のデータから対となるデータを検出する対デー
   タ検出手段を含み、前記対データ検出手段により対デー
   タが検出されたとき発火して対応の処理を実行する機能
   を有するデータ駆動型情報処理装置であって、 前記データ巡回パス上の一方からのデータを受けて一時
   的に格納しかつ格納データを前記巡回パスを介して前記
   対データ検出手段へ伝達するバッファメモリ手段を含
   み、前記データは配列順序を決定するキーデータを含
   み、 前記バッファメモリ手段は、各データに含まれる前記キ
   ーデータに従って予め定められた順序で格納データが配
   列されるように、受けたデータに含まれるキーデータと
   格納データのキーデータとに従って格納データを再配列
   する手段を含む、データ駆動型情報処理装置。
2. 【請求項２】 請求項１記載のデータ駆動型情報処理装
   置であって、 前記対データ検出手段は縮退したメモリ空間を有しかつ
   対を形成すべきデータを一時的に格納する待合せメモリ
   手段と、 対を形成すべきデータが与えられたとき、この受けた対
   を形成すべきデータを格納すべきアドレスに既にデータ
   が格納されているとき予め定められた優先順位に従って
   いずれのデータを前記待合せメモリ手段に格納すべきか
   否かを判別する優先度判別手段をさらに含み、 前記再配列手段は、前記優先順位判別手段が従う優先順
   位と同じ優先順位に従って前記キーデータに従って格納
   データを再配列する手段を含む。
3. 【請求項３】 入力データを順次格納しかつ出力するた
   めに、データ入力部とデータ出力部とを有するデータ伝
   送路に沿って配置される互いに縦続接続された複数のデ
   ータ格納手段、 前記データ伝送路に沿って鏡映対象の位置のデータ格納
   手段に対して設けられ、出力部側データ格納手段に有効
   格納データが存在しないとき、入力部側データ格納手段
   のデータを前記出力部側データ格納手段へ転送する転送
   手段、 前記データ伝送路に沿って鏡映対象の位置のデータ格納
   手段に対して設けられ、入力部側データ格納手段のデー
   タに含まれる所定のキーデータと出力部側データ格納手
   段のデータに含まれる所定のキーデータとを比較する比
   較手段、および前記比較手段の比較結果に従って対応の
   出力部側データ格納手段の格納データと対応の入力部側
   データ格納手段の格納データとを交換する交換手段を含
   む、データバッファ。