(57)【特許請求の範囲】
【請求項１】
データパケットを順に転送する、少なくとも第１段および第２段を含む複数段からなるパイプライン手段と、
演算に必要な組のデータを待ち合わせるデータパケットを格納するための待合せデータ格納手段と、
前記待合せデータ格納手段内にデータパケットが存在するか否かを示すデータを格納するためのＤフリップフロップと、
前記第１段に存在するデータパケットと組になるべきデータが前記待合せデータ格納手段内に格納されているか否かを、前記Ｄフリップフロップのデータを参照して判定するとともに前記Ｄフリップフロップのデータを更新するための判定手段と、
前記第１段から前記第２段に対して転送された前記データパケットに対して、前記判定手段の判定結果にしたがって、前記待合せデータ格納手段に記憶されたデータパケットとの間の待合せ処理を行なうための待合せ処理手段と、
前記待合せ処理手段による待合せ処理の結果生成されるデータパケットを出力するためのパケット出力手段とを含み、
前記待合せデータ格納手段は、複数個の部分待合せデータ格納手段を含み、
前記Ｄフリップフロップは、前記複数個の部分待合せデータ格納手段に対してそれぞれ設けられ、
前記パケット出力手段は、前記複数個の部分待合せデータ格納手段に格納されているデータのうちの、前記第１段および前記第２段を経て転送されて来たデータパケットと組になる少なくとも２つのデータと、前記第１段および前記第２段を経て転送されて来たデータパケットとから出力データパケットを生成するための手段を含む、データ駆動型情報処理装置の実行制御装置。
【請求項２】
前記Ｄフリップフロップは、リセット信号に応答して格納されたデータを予め定められた初期値にリセットする、請求項１に記載のデータ駆動型情報処理装置の実行制御装置。
【請求項３】
さらに、データパケットに対する命令実行に用いられる定数を記憶するための定数記憶手段を含み、
前記パケット出力手段の前記出力データパケットを生成するための手段は、前記定数記憶手段から読み出された定数をさらに含む前記出力データパケットを生成する、請求項１に記載のデータ駆動型情報処理装置の実行制御装置。
【請求項４】
前記定数は、前記データ駆動型情報処理装置における異なる種類の処理に用いられる互いに異なる第１および第２の種類の定数を含み、
前記定数記憶手段は、
前記第１の種類の定数を記憶する、第１の種類の定数記憶手段と、
前記第２の種類の定数を記憶する、第２の種類の定数記憶手段とを含み、
前記第１の種類の定数記憶手段と前記第２の種類の定数記憶手段とは、前記定数記憶手段内の互いに別個の領域に形成されている、請求項３に記載のデータ駆動型情報処理装置の実行制御装置。
【請求項５】
前記第１の種類の定数はスカラ定数であり、
前記第２の種類の定数はベクトル定数である、請求項４に記載のデータ駆動型情報処理装置の実行制御装置。
【請求項６】
前記第１の種類の定数は通常スカラ定数であり、
前記第２の種類の定数は長ビットスカラ定数である、請求項４に記載のデータ駆動型情報処理装置の実行制御装置。
【請求項７】
さらに、前記定数記憶手段内の各定数の記憶領域が有効か無効かを示す有効情報を記憶するための有効情報記憶手段を含み、前記有効情報が有効を示す値のときのみ対応の定数が前記定数記憶手段から読み出され、
前記定数を前記定数記憶手段から読み出してデータパケットに格納するための手段と、
前記データパケットに前記データパケット自身のパケット操作の内容を示す情報を格納するための手段とをさらに含み、
前記待合せ処理手段は、データパケットに含まれる前記データパケット自身のパケット操作の内容を示す情報が無効を示す場合には、当該データパケットに対する待合せ処理を行なわず通過させる、請求項３〜請求項６のいずれかに記載のデータ駆動型情報処理装置の実行制御装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はデータ駆動型情報処理装置の実行制御装置に関し、特に、画像処理、動画処理をはじめとする演算を行なう際に、パケットの待合せ処理機構とパケットの仕組みとを工夫することによって、処理の高速化および高効率化、演算の柔軟性の向上、コストパフォーマンスの向上を容易に図ることが可能なデータ駆動型情報処理装置の実行制御装置に関する。
【０００２】
【従来の技術】
データ駆動原理は、本来的に自然な情報処理方式であると考えられる。このデータ駆動原理を基本原理とするデータ駆動型情報処理装置は、実行可能な高位仕様記述から直接変換された対象プログラムを効果的に実行しようとする研究計画から生まれた一連の情報処理装置の総称である。
【０００３】
データ駆動原理とは以下のようなものである。プログラムは複数の命令から構成される。各命令は、それぞれの実行に必要な引き数データがトークン（データパケット）の形ですべて到着すると実行可能な状態になる。実行可能な状態になった命令は、その引き数データおよび実行結果の宛先とともに演算処理機構に送られる。
【０００４】
ここで、実行可能な状態となった命令があるか否かについての判定と、実行可能な状態になった命令が存在する場合に、その命令を、その引き数データおよび実行結果の宛先とともに演算処理機構に送る処理とを実現するのが、発火制御機構と呼ばれるものである。
【０００５】
演算処理機構では、当該命令が実行され、命令実行結果が、その宛先に従って、次に実行すべき命令の引き数データとしてトークンの形式で転送される。
【０００６】
図１に、一般的なデータ駆動型情報処理装置を画像処理に用いた際のシステム構成例を示す。図１を参照して、このシステムは、データ伝送路４およびデータ伝送路５にそれぞれ接続された入力ポートＩＡおよび入力ポートＩＢと、データ伝送路６およびデータ伝送路７にそれぞれ接続された出力ポートＯＡおよび出力ポートＯＢと、それぞれデータ伝送路８およびデータ伝送路９に接続された出力ポートＯＶおよび入力ポートＩＶとを有するデータ駆動型プロセッサ１と、データ伝送路８およびデータ伝送路９によってデータ駆動型プロセッサ１に接続されたメモリインタフェース２と、メモリアクセス制御線１Ａによってメモリインタフェース２と相互接続された画像メモリ３とを含む。
【０００７】
データ駆動型プロセッサ１は、データ伝送路４またはデータ伝送路５より、入力時刻の順序にしたがって付けられる世代番号と呼ばれる識別子を持つ入力データパケットを時系列的に受ける。データ駆動型プロセッサ１には、予め設定された処理内容が記憶されている。データ駆動型プロセッサ１は、入力データパケットが入力されると、データ駆動型プロセッサ１に記憶されている処理内容にしたがって処理を進める。データ駆動型プロセッサ１は、処理の中で画像メモリ３に対するアクセスが必要となると、そのアクセス要求（画像メモリ３の内容の参照／更新など）を出力ポートＯＶを介してデータ伝送路８上に出力する。メモリインタフェース２は、このアクセス要求を受けるとメモリアクセス制御線１Ａを介して画像メモリ３に対するアクセスを行ない、その結果をデータ伝送路９および入力ポートＩＶを介してデータ駆動型プロセッサ１に返す。
【０００８】
入力データパケットに対するデータ駆動型プロセッサ１内の処理が終了すると、データ駆動型プロセッサ１は出力ポートＯＡまたは出力ポートＯＢを介して、出力データパケットをデータ伝送路６またはデータ伝送路７に出力する。
【０００９】
図２はデータ駆動型情報処理装置の基本構成を示す図である。また図３は図２に示すデータ駆動型情報処理装置の入出力パケットの基本構成を示す図である。
【００１０】
図２を参照して、データ駆動型プロセッサ１は、外部からの入力データパケットと、データ駆動型プロセッサ１の内部を流れるデータパケットとを合流させるための合流部１０と、合流部１０からデータパケットを受け、命令の実行に必要なデータがそろったか否かを判定し、必要なデータがそろったデータを含むデータパケットを出力するための発火制御部１１と、発火制御部１１から与えられるデータパケットに含まれるデータに対して、当該データパケットに含まれる命令コードにより決定される処理を行ない、結果を、次の命令のノード番号を含むデータパケットとして再構成し出力するための演算部１２と、予め命令を記憶しており、演算部１２からのデータパケットを受け、当該データパケットに含まれるノード番号をアドレスとして、次に行なわれるべき命令コードと次のノード番号とを読出しデータパケットを構成して出力するためのプログラム記憶部１３と、プログラム記憶部１３からデータパケットを受け、その行先に応じて外部または合流部１０のいずれかに分岐させるための分岐部１４とを含む。
【００１１】
図３に示されるデータパケットは、合流部１０に入力されるデータパケットのものである。このデータパケットは発火制御部１１に与えられる。発火制御部１１には図２に示されるように、また特開平８−２７２７７１号公報にも示されるように、待合せ記憶領域と定数記憶領域とが含まれる。発火制御部１１に与えられたデータパケットは、対となって演算されるべき相手のデータパケットが到着するまで発火制御部１１の待合せ記憶領域１１ａに格納され待機する。対のデータパケットがそろった時点で、命令コードと対のデータとを含むデータパケットが再構成され演算部１２に送られる。演算されるべき相手がデータパケットでなく定数データである場合には、発火制御部１１での待機は行なわれない。すなわちこの場合には、定数記憶領域１１ｂから定数データを取得することによりデータパケットを再構成する。
【００１２】
演算部１２は、受取ったデータパケットのデータに対して命令コードによって決まる処理を行ない、結果のデータパケットを再構成して出力する。
【００１３】
プログラム記憶部１３は、演算部１２からデータパケットを受けると、そのデータパケットに含まれるノード番号をアドレスとして自己の持つプログラム記憶メモリをアクセスし、次に行なわれるべき命令コードと次のノード番号とを参照して、データパケットを構成し出力する。プログラム記憶部１３が出力するデータパケットは、そこに含まれるノード番号にしたがってデータ駆動型プロセッサ１の外部または合流部１０に分岐部１４によって振り分けられる。
【００１４】
図３を参照して、データ駆動型プロセッサ１に入力されるデータパケットはＰＥ番号１５（ＰＥはProcessing Elementの省略形である。）と、ノード番号１６と、世代番号１７と、データ１８とを含む。
【００１５】
ＰＥ番号１５は、図２に示される構成のデータ駆動型情報処理装置が複数個の入出力制御部（合流部１０および分岐部１４）を介して接続されたシステムにおいて、データ駆動型情報処理装置を互いに区別するための識別子である。
【００１６】
ノード番号１６は図２のプログラム記憶部１３に記憶されている命令コードを参照するためのアドレスとして使用される。
【００１７】
世代番号１７は、時系列的に入力されるデータパケットの識別子であるが、同時に画像メモリ３のアドレスとしての意味を有している。画像メモリ３のアドレスとしてみる場合、世代番号１７は図３に示すようにフィールド番号ＦＤと、ライン番号ＬＮと、ピクセル番号ＰＸとを含む。図１６に、画像と、フィールド番号ＦＤと、ライン番号ＬＮと、ピクセル番号ＰＸとの関係を示す。
【００１８】
図２に示す発火制御部１１に与えられるデータパケットの構成を図４に示す。図４を参照して、このデータパケットの構成は基本的に合流部１０へのデータパケット（図３）と同じであって、命令コード１９と、ノード番号２０と、世代番号２１と、データ２２とを含む。ここでは、図３のＰＥ番号１５に替えて、命令コード１９が設けられている。
【００１９】
図５に発火制御部１１の定数記憶領域１１ｂに格納されるデータの形式を示す。定数記憶領域１１ｂには、データパケットと対になるべきデータが定数の場合に、その定数データが記憶されている。図５を参照して、各レコードはＶＣＤ２３（ＶＣＤとはこの定数データの有効／無効を示すフラグであり、「１」のとき有効、「０」のとき無効）と、定数データ２４とを含む。
【００２０】
図６を参照して、待合せ記憶領域１１ａは、待合せデータパケットのハッシュアドレスを計算する際に使用しなかった部分を格納するハッシュ溢れアドレス２５と、待合せデータが存在していること、すなわちデータパケットが待機中であることを示すフラグであるＰＲＥ２６（「１」のとき有効、「０」のとき無効）と、待合せデータ２７とを含む。ハッシュ溢れアドレス２５には、待合せデータパケットのハッシュアドレスをノード番号１６と世代番号１７の一部から計算した際に用いられなかった部分が格納される。
【００２１】
プログラム記憶部１３から出力されるデータパケットの形式は図４に示すようなものとなる。このデータパケットが分岐部１４および合流部１０を巡回して発火制御部１１に入ると、まず図５の定数記憶領域１１ｂから定数データとＶＣＤとを取得する。次に、図６に示す待合せ記憶領域１１ａに対する動作として、格納／発火／通過のうちいずれを選択すべきかについての判定を行なう。判定のための材料は、命令コード１９と、定数記憶領域１１ｂから取得されたＶＣＤと、待合せ記憶領域１１ａ内のＰＲＥ２６とである。
【００２２】
まず、データパケット中の命令コードがデコードされ、演算部１２で実行される命令が１入力命令なのか、２入力命令なのかが判別される。１入力命令であればそのデータパケットが「通過」であることが分る。２入力であってもＶＣＤ＝１ならば、対データとしての相手データパケットが不要であるので同様に「通過」となる。
【００２３】
それ以外のとき、すなわち、２入力命令でありかつＶＣＤ＝０のときに、対データパケットとの待合せが必要となる。したがって待合せ記憶領域１１ａへのアクセスが発生する。このとき、ハッシュアドレス計算が行なわれる。該当するアドレスのＰＲＥが「０」であれば、対データパケットはまだ到着していない。したがってこのときのこのデータパケットに対する処理は「格納」となる。該当領域にデータとハッシュ溢れアドレスとを格納し、ＰＲＥ＝１に更新する。該当するアドレスのＰＲＥが「１」であれば対データパケットが待合せ記憶領域１１ａに存在している。したがって入力データパケットとあわせて演算に必要なデータがそろうので、処理は「発火」となる。待合せ記憶領域１１ａから待合せデータが取出され、パケットを再構成してＰＲＥ＝０と更新する。再構成されたデータパケットは図７に示される構成をとる。
【００２４】
図７を参照して、このデータパケットは、ＶＣＤ２８と、命令コード２９と、ノード番号３０と、世代番号３１と、左データ３２と、右データ３３とを含む。左データ３２および右データ３３が２入力命令の演算に必要なデータであり、待合せしていたデータパケットと、入力データパケットとから得られるものである。このデータパケットは演算部１２に送られる。
【００２５】
以下、上記した処理が順に繰返されてデータパケットがデータ駆動型情報処理装置の中を循環していく間にデータが処理されていく。
【００２６】
発火制御部１１では、待合せ記憶領域１１ａへのアクセスのスループットを維持するために、特開平８−２７２７７１号公報に示されるようにインターリーブ構成をとることがある。すなわち、図８に示されるように待合せ記憶領域１１ａは、ブロック３４と、二つの領域（メモリ部３５およびメモリ部３６）とを含む。ブロック３４によるデータパケットの振り分けによりアクセスが双方に分散するようにする。どちらの領域にアクセスするかは、ブロック３４内に設けられるレジスタにインターリーブビット（ＩＢ）と呼ばれるビットを設定して指定する。ＩＢは３ビットのＦＩＳパラメータと呼ばれるパラメータをブロック３４内の上記したレジスタにロードすることにより設定される。
【００２７】
ＦＩＳとＩＢとの関係をまとめて次の表１に示す。なおこのＦＩＳパラメータは、ハッシュアドレスを計算する際のハッシュ関数の種類を指定する機能も兼ねている。
【００２８】
【表１】
0003983455.tif 000002
【００２９】
なお、世代番号はＧ０〜Ｇ４の５ビットからなる。よってたとえばＧ１は世代番号の下位から２ビット目を表わしている。
【００３０】
【発明が解決しようとする課題】
上記したとおり、図８に示す従来技術では待合せ記憶をインターリーブ構成によって実現していた。各メモリ容量にはマージンを持たせる必要があり、その結果メモリに関するコストが高くつく。また、ストリーム状に到着するデータパケットの順序によっては、アクセスがメモリ部３５およびメモリ部３６の一方のみに集中して発生することがあり得る。そうした場合には目的のスループットを十分に維持することができない。
【００３１】
たとえば、表１においてＦＩＳ＝’０００’であるものと仮定する。このときＩＢは世代番号３１の第１ビットによって決定される。ここでデータパケットの世代番号が順に0(0b0...000000), 4(0b0...000100), 8(0b0...001000), 12(0b0...001100),...というようなストリームで発火制御部１１に到着すると、常にＩＢ＝０となる。その結果メモリ部３５にアクセスが集中してしまい十分なスループットが得られない。
【００３２】
さらに、データ駆動型情報処理装置においてはデータパケットは自己同期型転送制御回路（Ｃ素子）により、シーケンシャルに結合されたラッチ間の転送によってパイプライン的に転送されるが、ＰＲＥへの参照だけで、Ｃ素子間の転送に要する１クロックサイクルがかかる。さらに更新値検出と更新とで１クロックサイクルを要する。データパケットの到着順によるこうしたスループットの低下を避けるようなデータ駆動型情報処理装置の実行制御装置が望まれる。
【００３３】
また、画像処理、映像処理の処理性能に対する要求は日々大きくなっている。データ駆動型情報処理装置はそのような画像処理、映像処理に向いたアーキテクチャを持っている。そこで、他のアーキテクチャよりも高速に、より高いスループットでデータを処理することができ、なおかつ柔軟にプログラミングすることができるようなデータ駆動型情報処理装置の実行制御装置が望まれる。
【００３４】
求められる演算の複雑さがますます大きくなっているため、演算命令の複合の度合いも今後はより高いものが求められる。しかし、従来技術では最高でも２入力命令しか実装されていない。一方で、対等な３以上の入力から結果出力を得たい場合もある。そうした場合、従来のデータ駆動型情報処理装置では、１つのノード３７では図９（Ａ）のような２入力処理しかできないため、プログラミングにより図９(Ｂ）に示すようにノード３８およびノード３９を組み合わせて３入力命令を実現するしか術はない。１ノードで３入力処理が可能な場合と比較してレスポンス時間が無駄にかかり、実行が非効率的となる。
【００３５】
特に、図９（Ｂ）に示す構成では、入力Ａと入力Ｂとの間の演算をノード３８で行ない、その結果の出力Ｘと入力Ｃとの間でノード３９の演算を行なう。そのために入力Ｃはノード３８の処理が完了しＸが発火制御部１１に到着するまで待合せ記憶領域１１ａにて待機することとなる。その結果待合せ記憶領域１１ａの領域が無駄に使用されていることにもなる。３以上の入力を１ノードで処理できるようにすることにより、待合せ記憶領域を有効に利用し、さらに処理の効率をより高くすることが望まれる。
【００３６】
また、命令の複合度が増してくると、スカラデータだけではなくベクトルデータも演算対象として扱うことが多くなるであろう。それに対応して、定数記憶領域１１ｂに記憶しておく定数についてもベクトルデータとして扱いたいという要求が生じてくるであろう。その場合、複合命令を柔軟に扱うことを可能とするために、使用される定数の型がスカラまたはベクトルのどちらか一方のみに固定されるのでなく、同じ命令でも両者を切替えて使い分けられるようにできればより好ましい。
【００３７】
したがってこの発明の目的は、データパケットの到着順によって実行効率が影響を受けないようなデータ駆動型情報処理装置の実行制御装置を提供することである。
【００３８】
この発明の他の目的は、データパケットの到着順によって実行効率が影響を受けず、かつ待合せ記憶領域を有効に利用できるようなデータ駆動型情報処理装置の実行制御装置を提供することである。
【００３９】
この発明のさらに他の目的は、データパケットの到着順によって実行効率が影響を受けず、かつ待合せ記憶領域を有効に利用でき、定数データとしてスカラとベクトルとの両者を柔軟に切替えて使用できるようなデータ駆動型情報処理装置の実行制御装置を提供することである。
【００４０】
【課題を解決するための手段】
第１の発明にかかるデータ駆動型情報処理装置の実行制御装置は、データパケットを順に転送する、少なくとも第１段および第２段を含む複数段からなるパイプライン手段と、演算に必要な組のデータを待ち合わせるデータパケットを格納するための待合せデータ格納手段と、待合せデータ格納手段内にデータパケットが存在するか否かを示す情報を格納するための格納部と、第１段に存在するデータパケットと組になるべきデータが待合せデータ格納手段内に格納されているか否かを、格納部の内容を参照して判定するとともに格納部の情報を更新するための判定手段と、第１段から第２段に対して転送されたデータパケットに対して、判定手段の判定結果にしたがって、待合せデータ格納手段に記憶されたデータパケットとの間の待合せ処理を行なうための待合せ処理手段と、待合せ処理手段による待合せ処理の結果生成されるデータパケットを出力するためのパケット出力手段とを含む。
【００４１】
実行制御装置を複数段のパイプライン手段で構成し、パイプライン手段の第１段に存在するデータパケットに対して対応のデータパケットが待合せデータ格納手段に存在するか否かを判定し、そのデータパケットが第２段に転送された後に、当該判定結果に基づいて待合せ処理を行なう。結果として待合せ処理がパイプライン化されるため、スループットを高く維持することができる。
【００４２】
好ましくは、格納部はフリップフロップ回路を含む。簡単なフリップフロップを用いて、高速に待合せデータパケットの存在を判定することができる。
【００４３】
さらに好ましくは、格納部は、リセット信号に応答してその格納内容を予め定められた初期値にリセットする機能を有する。格納部の格納内容を初期化する際に、リセット信号を用いて直接初期化できる。わざわざ初期化のためのデータパケットを情報処理装置に入力する必要はない。
【００４４】
本発明の他の局面によれば、待合せデータ格納手段は、複数個の部分待合せデータ格納手段を含み、格納部は複数個の部分待合せデータ格納手段に対してそれぞれ設けられている。複数個の部分待合せデータ格納手段を設けることにより、少なくとも部分待合せデータ格納手段の個数に、入力データパケットの分である１を加えた数の入力を有する命令を１ノードで実行することが可能となる。
【００４５】
好ましくはデータ駆動型情報処理装置の実行制御装置はさらに、データパケットに対する命令実行に用いられる定数を記憶するための定数記憶手段を含み、パケット出力手段は、複数個の部分待合せデータ格納手段に格納されているデータのうちの、第１段および第２段を経て転送されて来たデータパケットと組になるデータと、定数記憶手段から読み出された定数と、第１段および第２段を経て転送されて来たデータパケットとから出力データパケットを生成するための手段を含む。
【００４６】
さらに定数の入力が加えられるので、少なくとも部分待合せデータ格納手段の個数に２を加えた数の入力を有する命令を１ノードで実行することが可能となる。
【００４７】
さらに好ましくは、定数は、データ駆動型情報処理装置における異なる種類の処理に用いられる互いに異なる第１および第２の種類の定数を含み、定数記憶手段は、第１の種類の定数を記憶する、第１の種類の定数記憶手段と、第２の種類の定数を記憶する、第２の種類の定数記憶手段とを含み、第１の種類の定数記憶手段と第２の定数記憶手段とは、定数記憶手段内の互いに別個の領域に形成されている。
【００４８】
定数が定数記憶手段のどの領域から読み出されるかによってその定数の種類を識別することができる。その結果、使用する定数の読出位置を適切に指定することにより、データ駆動型情報処理装置で行なわれる異なる種類の処理に、それぞれの処理の種類に応じた形式の定数を容易に利用することができる。
【００４９】
さらに好ましくは、第１の種類の定数はスカラ定数であり、第２の種類の定数はベクトル定数である。スカラ定数とベクトル定数とを適宜切替えて処理に用いることができる。
【００５０】
また、第１の種類の定数は通常スカラ定数であり、第２の種類の定数は長ビットスカラ定数であってもよい。通常スカラ定数と長ビットスカラ定数とを適宜切替えて処理に用いることができる。
【００５１】
好ましくは、データ駆動型情報処理装置の実行制御装置はさらに、定数記憶手段内の各定数の記憶領域が有効か無効かを示す有効情報を記憶するための有効情報記憶手段を含み、有効情報が有効を示す値のときのみ対応の定数が読み出され、定数を定数記憶手段から読み出してデータパケットに格納するための手段と、データパケットに、データパケットに格納されたデータパケットが無効であることを示す有効情報を格納するための手段とをさらに含み、待合せ処理手段は、データパケットに含まれる有効情報が無効を示す場合には、当該データパケットに対する待合せ処理に対する待合せ処理を行なわず通過させる。
【００５２】
定数データについて、あたかもそれが無効データであるかのようにすることにより、待合せ処理を通過させて３以上の入力を持つ命令への入力とすることができる。
【００５３】
好ましくは、パケット出力手段は、複数個の部分待合せデータ格納手段に格納されているデータのうちの、第１段および第２段を経て転送されて来たデータパケットと組になるデータと、第１段および第２段を経て転送されて来たデータパケットとから出力データパケットを生成するための手段を含む。
【００５４】
部分待合せデータ格納手段の個数に１加えた数の入力を有する命令を１ノードで実行することが可能となる。
【００５５】
【発明の実施の形態】
以下、パケット２系統の待合せ領域で４入力命令を実現し、かつスカラ定数とベクトル定数とを切替えて使用できるデータ駆動型情報処理装置の実行制御装置の実施の形態について説明する。なお、データ駆動型情報処理装置全体の構成は図２に示したものとほぼ同様で、発火制御部１１における待合せ制御が異なる。したがって、ここでは図２と同じ部品については同じ参照符号および名称で説明することとし、それらについての詳細な説明は繰返さない。
【００５６】
図１０に、発火制御部１１に入力されるデータパケットの基本形式を示す。図１０を参照して、このデータパケットは、命令コード４０と、このデータパケットが左入力データなのか、右入力データなのかを示すＬ／Ｒ４１と、ノード番号４２と、世代番号４２Ａと、８つのデータである第０〜第７データ４３とを含む。データパケットが第０〜第７データ４３を有し、８つのデータを格納することができるので、このデータパケットはベクトルデータとして用いることができる。
【００５７】
図１１を参照して、定数記憶領域１１ｂは、アドレス００〜0Ｆまでのベクトル定数を記憶する部分（図１１（Ａ））と、アドレス１０〜ＦＦまでのスカラ定数を記憶する部分（図１１（Ｂ））とを含む。
【００５８】
図１１（Ａ）に示されるようにベクトル定数は、ＶＣＤ４４と、第７定数４５〜第０定数５２とを含む。図１１（Ｂ）に示されるようにスカラ定数は、ＶＣＤ５３と、定数５４とを含む。
【００５９】
図１０に示されるデータパケットが発火制御部１１に到着すると、図１１に示されるような構成となっている発火制御部１１から定数データとＶＣＤとが取出され、データパケット内に埋込まれる。ノード番号４２、すなわち定数記憶領域１１ｂのアドレス（００〜０Ｆまたは１０〜ＦＦ）に応じて、取出す対象がスカラ定数なのかベクトル定数なのかが決まる。その結果、図１５に示される入力パケット８９のようなパケット形式となり、待合せ記憶部の処理に移る。
【００６０】
なおここではスカラ定数とベクトル定数との切替えをする場合について説明しているが、同様の方式によって通常のスカラ定数と、より長い長ビット定数とを切替えて処理することもできる。その場合の定数記憶領域１１ｂの構成例を図１２に示す。この場合にも、取出される定数が通常のスカラ定数なのか長ビット定数なのかは、それらが取出されるアドレスの値（たとえば００〜０Ｆなのか、１０〜ＦＦなのか）によって決まる。
【００６１】
待合せ記憶部２００での処理は図１５に示される構造により実現される。図１５を参照して、この待合せ記憶部２００は、データパケットを処理するためのパイプラインの第１段〜第４段をそれぞれ構成する、それぞれ入力パケット８９、パケット９４、パケット９７およびパケット９９を保持するための４つのラッチ回路と、これらラッチ回路の間のデータの転送を制御するためのＣ素子１００〜１０４と、入力パケット８９に含まれる第０〜第７データ４３命令コードＯＰＣをデコードし、命令コードＯＰＣが必要とする入力数ｉｎｓｔを出力するための命令デコーダ９０と、入力数ｉｎｓｔが４か否かを判定するための処理ブロック９１と、それぞれ部分的な領域を形成する第１待合せ領域９６Ａおよび第２待合せ領域９６Ｂを持つ、対パケットが格納される待合せ領域９６と、入力パケット８９のノード番号および世代番号からハッシュアドレスを計算し、その結果によって第１待合せ領域９６Ａ／第２待合せ領域９６Ｂの有効／無効をそれぞれ識別するためのフラグであるＰＲＥ１およびＰＲＥ０を参照し、さらに後に示す表２にしたがってその更新値を決定するためのハッシュ計算ブロック９２と、このＰＲＥ１およびＰＲＥ０をそれぞれ格納するための、それぞれ１ビットのＤフリップフロップからなるＰＲＥ１およびＰＲＥ０からなるＰＲＥ格納部２０２と、処理ブロック９１から出力される入力数ｉｎｓｔとＶＣＤとＰＲＥ１およびＰＲＥ０の値に基づいて第１待合せ領域９６Ａおよび第２待合せ領域９６Ｂにアクセスするか否かを判定する待合せ動作判定を行なうための待合せ動作判定ブロック９３と、パケット９４のデータ７〜０およびｓｅｌの値に基づいて第１待合せ領域９６Ａおよび第２待合せ領域９６Ｂのいずれか一方にアクセス（参照・更新）する処理を行なうための待合せ記憶部アクセスブロック９５と、パケット９７に対してデータ交換処理およびハッシュ衝突の検出処理を行なってパケット９９とするための処理ブロック９８とを含む。
【００６２】
待合せ領域９６の構造を図１４に示す。図１４を参照して、待合せ領域９６は、第１待合せ領域のデータの有効／無効フラグであるＰＲＥ０（６９）および第２待合せ領域のデータの有効／無効フラグであるＰＲＥ１（７０）と、ハッシュ溢れアドレス７１と、第１待合せ領域のデータの左右入力を識別するフラグであるＬ／Ｒ７２と、第１待合せ領域である第７データ７３〜第０データ８０と、第２待合せ領域である第７データ８１〜第０データ８８とを含む。
【００６３】
入力パケット８９は命令コードＯＰＣと、Ｌ／Ｒと、ノード番号ｎｏｄｅと、世代番号ｇｅｎと、データ（７〜０）と、ＶＣＤと、定数データ（７〜０）とを含む。
【００６４】
パケット９４は、命令コードＯＰＣと、Ｌ／Ｒと、ノード番号ｎｏｄｅと、世代番号ｇｅｎと、データ（７〜０）と、ＶＣＤと、定数（７〜０）と、待合せ動作の選択ｓｅｌと、入力数ｉｎｓｔとを含む。
【００６５】
パケット９７は、命令コードＯＰＣと、Ｌ／Ｒと、ノード番号ｎｏｄｅと、世代番号ｇｅｎと、データ（７〜０）と、ＶＣＤと、定数（７〜０）と、第１待合せ領域９６Ａから取出したデータ１（７〜０）と、第２待合せ領域９６Ｂから取出したデータ２（７〜０）と、入力数ｉｎｓｔとを含む。
【００６６】
パケット９９は、命令コードＯＰＣと、Ｌ／Ｒと、ノード番号ｎｏｄｅと、世代番号ｇｅｎと、左データＤａｔａＬ（７〜０）と、右データＤａｔａＲ（７〜０）と、制御データＤａｔａＣ（７〜０）とを含む。
【００６７】
この待合せ記憶部２００は以下のように動作する。まず、入力パケット８９に含まれる命令コードＯＰＣを命令デコーダ９０によってデコードし、何入力の命令かを判別する。命令デコーダ９０は判別結果を入力数ｉｎｓｔとして出力する。例えば入力数ｉｎｓｔ＝３であれば命令コードＯＰＣは３入力命令である。なお本実施の形態では入力数ｉｎｓｔは１〜４の範囲の値をとる。
【００６８】
もし入力数ｉｎｓｔ＝４であれば、命令コードＯＰＣは４入力命令である。しかしこの実施の形態の装置では、４入力命令への４つの入力は、必ず３つの変数と１つの定数とからなると規定されている。したがって、処理ブロック９１は、入力数ｉｎｓｔ＝４か否かを判定し、もし入力数ｉｎｓｔ＝４であればＶＣＤの値を０に更新し、入力数ｉｎｓｔ＝３に更新する。入力数ｉｎｓｔ＝３と更新された場合、最初から入力数ｉｎｓｔ＝３の場合と同じ処理がこれ以後に行なわれる。
【００６９】
ハッシュ計算ブロック９２は、入力パケット８９のノード番号と世代番号とからハッシュアドレス計算を行なって、対応のＰＲＥ格納部２０２のＰＲＥ０とＰＲＥ１との値を参照する。
【００７０】
待合せ記憶部２００に対するデータパケットの操作、ＰＲＥ０／１の更新値、待合せ領域９６の操作の対応を表２に示す。
【００７１】
【表２】
0003983455.tif 000003
【００７２】
なお表２において、ＰＲＥ更新値の２桁の数値のうち左側はＰＲＥ１に、右側はＰＲＥ０に、それぞれ対応する。また「パケットＷｒｉｔｅ」とは、パケットを第１待合せ領域９６Ａまたは第２待合せ領域９６Ｂに格納し、かつ対応するＰＲＥ０またはＰＲＥ１を「１」に更新する処理のことをいう。また表２において「ｘ」で示される部分はドントケアを表わす。
【００７３】
待合せ動作判定ブロック９３は、入力数ｉｎｓｔと、ＶＣＤと、ＰＲＥ０／１との値に基づいて、表２にしたがって待合せ領域９６におけるパケット操作と、ＰＲＥ０／１の更新値とを求め、表２の「パケット動作」で示されるパケット操作の内容を示す情報をパケット９４の「ｓｅｌ」のフィールドに設定する。さらに待合せ動作判定ブロック９３は、ＰＲＥ０／１の値を表２にしたがって更新する。
【００７４】
次に、処理ブロック９５が、パケット９４のｓｅｌに設定されているパケット操作の内容に基づいて、待合せ領域９６にアクセスする。
【００７５】
図１５に示す構成では、待合せ記憶領域へのアクセスタイムとしては、パイプライン２段分（Ｃ素子１０１〜１０２およびＣ素子１０３〜１０４）のタイムスロットが必要である。たとえば、１入力命令または２入力命令（１定数）の場合には、データパケットが待合せ記憶部２００を通過するのみで、第１待合せ領域９６Ａおよび第２待合せ領域９６Ｂの双方に対して処理内容が「Hold」のときにはアクセスの必要はない。
【００７６】
演算に必要な対（または３つ）のデータパケットがまだ待合せ記憶部２００にそろわないときには、当該パケットは待機するために第１待合せ領域９６Ａまたは第２待合せ領域９６Ｂに格納される。この動作は表２において「パケットWrite」と記載されている部分に相当する。
【００７７】
対（または３つ）のデータパケットがそろうと発火となり、待合せ領域９６からデータが取出される。このときＰＲＥ１／０は「００」に更新される。
【００７８】
最後の処理ブロック９８は、パケット９７に含まれる入力数ｉｎｓｔ、ＶＣＤ、Ｌ／Ｒの値を用いて、演算部１２での処理に間に合うようにパケット９９を再構成する。さらに処理ブロック９８は、ハッシュ衝突の判定を行なってパケット９９を演算部１２に送り、待合せ記憶部２００での処理を終了する。
【００７９】
上記したような実施の形態のシステムでは、待合せ記憶部２００の処理を複数段のパイプラインに分割している。したがってデータパケットストリームの入力順序に依存せず、待合せ記憶部２００でのスループットを一定に維持することができる。またＰＲＥビットをＰＲＥ格納部２０２に格納し、ハッシュアドレスの計算、待合せ判定の際にＰＲＥビットの参照／更新を行なう。さらにその後、ＰＲＥビットを待合せ領域９６に記憶する。そのため、従来のように待合せ記憶領域からの読出や待合せ記憶領域への書込みによる方法と比較して、ＰＲＥビットの参照および更新を高速に行なうことができる。特に、ＰＲＥ格納部２０２をＤフリップフロップで構成することにより、この参照および更新を高速に、かつ簡単な回路で実現している。上記実施の形態では１クロックサイクルでこの参照／更新を実現している。
【００８０】
さらに、ＰＲＥ格納部２０２をリセット入力を持つ回路で構成することもできる。従来は、たとえば初期化時にＰＲＥビットをリセットするためには、リセット用初期化パケットをデータ駆動型情報処理装置に与えていた。ＰＲＥ格納部２０２を、リセット入力を持ち、リセット入力から与えられるリセット信号に応答して自己をリセットする回路（たとえばフリップフロップ回路）とすることで、初期化用パケットを用いることなく、単にリセット信号をＰＲＥ格納部に与えることでＰＲＥビットをリセットすることができる。
【００８１】
なお、この実施の形態ではパケット２系統分の待合せ領域（第１待合せ領域９６Ａおよび第２待合せ領域９６Ｂ）で４入力命令を実現しているが、同様の考え方で１系統分の待合せ領域で３系統命令を実現することもできる。その場合には、待合せ領域として図１３に示すような構成を採用すればよい。図１３を参照して、この待合せ領域は、ＰＲＥ５９と、ハッシュ溢れアドレス６０と、第７データ６１〜第０データ６８とを含む。
【００８２】
さらに同様の考え方で、パケットｎ系統（第１待合せ領域、第２待合せ領域、…、第ｎ待合せ領域）を設けることで、（ｎ＋２）入力命令を実現することができる。
【００８３】
この実施の形態の方法および装置によれば、従来のように待合せ記憶領域に対するアクセスを高速化するためにインターリーブ方式をとる必要がない。必要なメモリ領域が削減され、かつ回路構成も簡単なものとなる。したがって装置の小型化およびメモリ量削減によるコストの提言を実現することができる。
【００８４】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【図１】  データ駆動型情報処理装置のシステム構成例を示す図である。
【図２】  データ駆動型情報処理装置の内部基本構成図である。
【図３】  従来のデータ駆動型情報処理装置への入出力パケットの基本構成を示す図である。
【図４】  従来のデータ駆動型情報処理装置の発火制御部への入力パケットの基本構成を示す図である。
【図５】  従来のデータ駆動型情報処理装置の発火制御部内の定数記憶領域を示す図である。
【図６】  従来のデータ駆動型情報処理装置の発火制御部内の待合せ記憶領域を示す図である。
【図７】  従来のデータ駆動型情報処理装置の発火制御部からの出力パケットの基本構成を示す図である。
【図８】  従来のデータ駆動型情報処理装置の、メモリインタリーブで実現された待合せ記憶部を示す図である。
【図９】  従来のデータ駆動型情報処理装置において３入力演算命令を実装する時の一例を示す図である。
【図１０】  本発明のデータ駆動型情報処理装置の発火制御部に入力されるデータパケットの基本形式を示す図である。
【図１１】  スカラ定数とベクトル定数とを切替えて使用可能な定数記憶部を示す図である。
【図１２】  スカラ定数と長ビット定数とを切替えて使用可能な定数記憶部を示す図である。
【図１３】  パケット１つ分の待合せ領域によって３入力命令を実現するための待合せ記憶部の構成を示す図である。
【図１４】  パケット２つ分の待合せ領域によって４入力命令を実現するための待合せ記憶部の構成を示す図である。
【図１５】  本発明の待合せ記憶部内の処理をパイプライン構成としたときの構成と処理の流れを示す図である。
【図１６】  データ駆動型情報処理装置における画像データと世代番号との間の関係を示す図である。
【符号の説明】
１１  発火制御部、９０  命令デコーダ、９２  ハッシュ計算ブロック、９３待合せ動作判定ブロック、９５  待合せ記憶部アクセスブロック、９６  待合せ記憶部、２００  待合せ記憶部、２０２  ＰＲＥ格納部。
【図１】
0003983455.tif 000004
【図２】
0003983455.tif 000005
【図３】
0003983455.tif 000006
【図４】
0003983455.tif 000007
【図５】
0003983455.tif 000008
【図６】
0003983455.tif 000009
【図７】
0003983455.tif 000010
【図８】
0003983455.tif 000011
【図９】
0003983455.tif 000012
【図１０】
0003983455.tif 000013
【図１１】
0003983455.tif 000014
【図１２】
0003983455.tif 000015
【図１３】
0003983455.tif 000016
【図１４】
0003983455.tif 000017
【図１５】
0003983455.tif 000018
【図１６】
0003983455.tif 000019