(57)【要約】【課題】複数の合流ノード間で並列動作を可能にするとともにパケット順序維持を可能にする。【解決手段】ＯＤ＝‘１’であれば、ノード１１１からの分岐先方向を示す、行先アドレスＤＡの対応するビットＤＡｉが、キュー１１３の入力段１１３ａの１ビットラッチのデータ入力端に供給される。ＤＡｉ＝‘１’のとき、ノード１１１は、ノード１１７へパケットを分岐転送させるとともにキュー１１３の入力段１１３ａにＤＡｉ＝‘１’を転送させる。Ｎ段経過後に、一方ではこれに対応するパケットがノード１１５に保持され、他方ではマルチプレクサ１１０Ｍの選択制御入力端に、前記ＤＡｉ＝‘１’に対応したＳＥＬ＝‘１’が供給されて、ノード１１０はノード１１５側を選択する。ノード１１０の転送制御回路１１０Ｃは、連接ビットＣＮが‘１’のときは例外として、キュー１１３の出力段１１３ｂへのＡＣＫをインアクティブに維持する。【選択図】図２６
2008123406.tif 000002
【特許請求の範囲】
【請求項１】
第１パケットが分流路内の分岐ノードを通れば、該第１パケットに対応した第２パケットが合流路内の合流ノードを通り、且つ、該分岐ノードでの該第１パケットの分岐方向と該合流ノードでの該第２パケットの合流方向とが対応しており、該分岐ノードと該合流ノードとの間のパイプライン段数がＮ（Ｎ≧１）であるデータ駆動型処理装置の該合流ノードでの入力選択を制御する順序合流制御回路を、該合流路内の複数の合流ノードのそれぞれに関して備えたデータ駆動型処理装置用順序合流制御装置であって、各順序合流制御回路は、
Ｎ段以上のキューと、
該分岐ノードでのパケットに含まれる分岐方向情報を該キューの入力段へ転送させる第１転送制御回路と、
該キューの出力段の出力を該合流ノードの入力選択制御信号として転送させる第２転送制御回路と、
を有することを特徴とするデータ駆動型処理装置用順序合流制御装置。
【請求項２】
該分岐方向情報は、行先アドレスのうち該分岐ノードから次段への行先を示すビットであることを特徴とする請求項１に記載の順序合流制御装置。
【請求項３】
該第１転送制御回路は、該パケットに含まれる順序情報が順序有りを示している場合に、該入力段への転送を有効にすることを特徴とする請求項１に記載の順序合流制御装置。
【請求項４】
該順序情報は、該パケットが該合流ノードへの途中のノードで消失する場合に順序無しを示すことを特徴とする請求項３に記載の順序合流制御装置。
【請求項５】
該第１転送制御回路は、該分岐ノードから次段ノードへのＳＥＮＤ信号をアクティブにするときに、該キューの入力段へのＳＥＮＤ信号をアクティブにすることを特徴とする請求項１に記載の順序合流制御装置。
【請求項６】
該第１転送制御回路は、該分岐ノードの後段からのＳＥＮＤ信号がアクティブであり、且つ、該分岐ノードの次段及び該キューの入力段からのＡＣＫ信号が共にアクティブであるときに、該分岐ノードにデータを取り込ませて保持させ、該次段及び該入力段へのＳＥＮＤ信号をアクティブにすることを特徴とする請求項５に記載の順序合流制御装置。
【請求項７】
該第２転送制御回路は、該合流ノードの後段へのＡＣＫ信号をアクティブにするときに、該キューの出力段に対するＡＣＫをアクティブにすることを特徴とする請求項１に記載の順序合流制御装置。
【請求項８】
該第２転送制御回路は、該キューの出力段及び該合流ノードの後段の一方からのＳＥＮＤ信号が共にアクティブになり且つ該合流ノードの次段からのＡＣＫ信号がアクティブになったときに、該合流段にデータを取り込ませて保持させ、該キューの出力段に対するＡＣＫをアクティブにすることを特徴とする請求項６に記載の順序合流制御装置。
【請求項９】
該第２転送制御回路は、該第１パケットに対応した第２パケットが複数パケットで構成され、該複数パケットの末尾パケット以外の連接ビットが後続有りを示している場合、例外として、該キューの出力段に対するＡＣＫをインアクティブに維持することを特徴とする請求項８に記載の順序合流制御装置。
【請求項１０】
分岐ノードと合流ノードとを複数対備え、各対について、第１パケットが分岐ノードを通れば、該第１パケットに対応した第２パケットが合流ノードを通り、且つ、該分岐ノードでの該第１パケットの分岐方向と該合流ノードでの該第２パケットの合流方向とが対応しているデータ駆動型処理装置であって、さらに、
該複数対のうち、分岐ノードと合流ノードとの間のパイプライン段数が１以上である対のそれぞれに請求項１乃至９のいずれかに記載の順序合流制御装置を備えていることを特徴とするデータ駆動型処理装置。
【請求項１１】
第１入口ノードに供給されるパケットを、パケット内の行先アドレスの値に応じ下流側のノードへ順次選択的に分流させて、複数の第１出口ノードのうちの該値に対応したものへ到達させるツリー形分流路と、
該複数の第１出口ノードのそれぞれに対応した第２入口ノードを有し、パケットを下流側のノードへ順次選択的に合流させて第２出口ノードに到達させるツリー形合流路と、
各第１出口ノードとこれに対応する第２入口ノードとの間に結合され、該第１出口ノードからのパケットの内容に応じたパケットを該第２入口ノードへ供給する第１機能エレメントと、
を有し、該ツリー形分流路及び該ツリー形合流路の各ノードはパイプラインステージを構成し、該ツリー形分流路及び該ツリー形合流路はいずれも３ステージ以上有し、
該ツリー形分流路を構成する複数の分岐ノードと該ツリー形合流路を構成する複数の合流ノードとが該複数対を構成していることを特徴とする請求項１０に記載のデータ駆動型処理装置。
【請求項１２】
該ツリー形分流路内において、互いに相補的な行先アドレスを有するパケットの経路が、流路方向の軸に関し互いに、論理的に対称になるように、該ツリー形分流路が形成されていることを特徴とする請求項１１に記載のデータ駆動型処理装置。
【請求項１３】
任意の行先アドレスについて、該ツリー形分流路内でのパケットの経路と該ツリー形合流路内でのパケットの経路とが、流路と直角な方向の軸に関し互いに、論理的に対称になるように、該ツリー形分流路及び該ツリー形合流路が形成されていることを特徴とする請求項１２に記載のデータ駆動型処理装置。
【請求項１４】
該第１入口ノードには互いに関連する複数のパケットが順次供給され、
該ツリー形合流路は、該第２出口ノードに到達した該複数のパケットの内容に応じたパケットを生成する第２機能エレメントを、少なくとも該第２出口ノードに備えている、
ことを特徴とする請求項１２又は１３に記載のデータ駆動型処理装置。
【請求項１５】
該パケットは系統値を有し、
該ツリー形分流路は、系統毎に異なる該第１入口ノードを有し、中間ノードで複数の系統からのパケットを選択的に合流させ、該複数の第１出口ノードが各系統で共通であり、
該ツリー形合流路は、該複数の第２入口ノードが各系統で共通であり、中間ノードで複数の系統からのパケットを該系統値に応じて選択的に分岐させ、系統毎に異なる該第２出口ノードを有する、
ことを特徴とする請求項１１に記載のデータ駆動型処理装置。
【請求項１６】
該ツリー形分流路内において、互いに相補的な行先アドレスを有するパケットの経路が、流路方向の軸に関し互いに、論理的に対称になるように、該ツリー形分流路が形成されていることを特徴とする請求項１５に記載のデータ駆動型処理装置。
【請求項１７】
任意の行先アドレスについて、該ツリー形分流路内でのパケットの経路と該ツリー形合流路内でのパケットの経路とが、流路と直角な方向の軸に関し互いに、論理的に対称になるように、該ツリー形分流路及び該ツリー形合流路が形成されていることを特徴とする請求項１６に記載のデータ駆動型処理装置。
【請求項１８】
各第１入口ノードには互いに関連する複数のパケットが順次供給され、
該ツリー形合流路は、少なくとも各第２出口ノードに、該第２出口ノードでの該複数のパケットの内容に応じたパケットを生成する第２機能エレメントを備えている、
ことを特徴とする請求項１５に記載のデータ駆動型処理装置。
【請求項１９】
該ツリー形合流路は、その各ノードに該第２機能エレメントを備えていることを特徴とする請求項１８に記載のデータ駆動型処理装置。
【請求項２０】
該互いに関連する複数のパケットはそれぞれ、該ツリー形合流路内で合流するノードを識別するパケット側合流段識別子を含み、
該ツリー形合流路の各ノードは、該パケット側合流段識別子が該ノード側合流段識別子に対応していれば該第２機能エレメンを動作させる、
ことを特徴とする請求項１９に記載のデータ駆動型処理装置。
【請求項２１】
該ツリー形分流路の各第１入口ノードの上流側に合流段識別子生成ノードをさらに備え、該合流段識別子生成ノードは、該互いに関連する複数のパケット内のそれぞれの行先アドレスの値に基づいて、該パケット側合流段識別子の値を生成することを特徴とする請求項２０に記載のデータ駆動型処理装置。
【請求項２２】
該ツリー形合流路の複数の第２出口ノードをそれぞれ、対応する該合流段識別子生成ノードに結合させる通信路をさらに有することを特徴とする請求項１５乃至２１のいずれか１つに記載のデータ駆動型処理装置。
【請求項２３】
該ツリー形分流路は、該複数の第１入口ノードのそれぞれから系統間で合流せずに分流した位置に次段のノードを有することを特徴とする請求項１５乃至２２のいずれか１つに記載のデータ駆動型処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ駆動型半導体装置に用いられ、データ駆動型処理装置及びその順序合流制御装置に係り、特に、分岐ノードでのパケット分岐方向に基づき、これに対応した合流ノードでのパケット合流方向を制御する順序合流制御装置及びこれを用いたデータ駆動型処理装置に関する。
【背景技術】
【０００２】
データ駆動型半導体装置では、ローカルな同期制御が複数の要素のそれぞれで自立分散的に行われるので、システムクロックに同期して各要素を集中制御する同期型半導体装置よりも、処理の並列度を容易に高くすることができるとともに、消費電力を低減できる。【０００３】
この装置の合流ノードでは、先着優先でパケットを選択的にラッチするので、パケットが混雑したノードを通って来たパケットとそうでないノードを通って来たパケットとの順番が入れ替わる。【０００４】
そこで、従来のデータ駆動型半導体装置では、下記特許文献１に開示されているように、パケットには行き先アドレスのみならず、例えば９ビットのペア識別用カラーを付加し、同文献の図８に示すようなＦＩＦＯメモリ、ハッシュメモリ、連想メモリ、演算部及び制御部等を備えたマッチングメモリで同一カラーのパケットを待ち合わせて、処理要素で処理を行っていた。【０００５】
このため、パケット待ち合わせの構成が複雑になるという問題があった。【０００６】
一般に、非同期型ではミクロにおいてもマクロにおいても、自律分散処理であればパケットの順序が入れ替わるのは当然と考えられ、ミクロの非同期型では上述のようなカラーを用いてパケット順序を後処理で整えていた。【０００７】
マクロの非同期型では、豊潤なハードウェアリソース及びソフトウェアリソースを用いてパケット順序を整えることができるが、ミクロの非同期型では、このような後処理は重荷となり、構成が複雑になるとともにスループットが低下する原因となる。【０００８】
もし、パケット順序を維持することができれば、パケット順を予測できるので、例えば図２２（Ａ）に示すようなループを図２２（Ｂ）又は図２３（Ａ）に示すようなループに分割して並列化及びコンポーネント化が可能となり、さらに、図２３（Ｂ）に示すような階層化も可能となる。すなわち、非同期型でパケット順序を維持することは、コンポーネント間で順序同期をとることを意味し、同期型でシステムクロックを使用するのと同じような効果を奏する。【０００９】
このため、ミクロの非同期型では、パケット順序を維持することが重要な技術的課題となる。【００１０】
下記特許文献２には、分配制御回路と収集制御回路との間に複数のメモリ部（メモリアクセス回路＋メモリ本体）を備えたデータフロー型装置に関する次のような構成が開示されている。すなわち、該複数のメモリ部に対応して１つのパケットキュー回路を備え、メモリアクセス情報を含むパケットＸと転送識別情報を含むパケットＹとの対をパケット入力線に順次供給し、パケットＸで複数のメモリ部のいずれかをアクセスして、加工されたパケットＺを読み出すと共に、パケットＹを順次パケットキュー回路に供給し、複数のメモリ部においてこのアクセスを並列に行い、それぞれパケットＺをメモリ部に待機させておき、収集制御回路において、複数のメモリ部で待機している複数のパケットＺのいずれかを、パケットキュー回路から読み出したパケットＹに基づき選択して読み出し、パケット出力線から出力する構成が開示されている。
【特許文献１】特開平５−２８２９１号公報
【特許文献２】特開平３-２３３７４０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、複数のメモリ部のいずれか１つを選択して収集制御回路側へデータを読み出すので、メモリ部で並列処理ができても、データ読み出しで動作が遅れ、データ駆動型の並列処理の利点を充分に活かすことができない。【００１２】
また、メモリ部の前段と後段との間のみで順序を維持しているので、収集制御回路が複数段のノードを備えている場合には、データの混雑が偏在すると、データの順序が狂うことがあり得る。【００１３】
さらに、パケット入力線が複数あって並列にパケットが供給される場合には、データの順序を維持することができない。【００１４】
本発明の目的は、このような問題点に鑑み、複数の合流ノード間で並列動作を可能にするとともにパケット順序維持を可能にする順序合流制御装置及びこれを備えたデータ駆動型処理装置を提供することにある。
【課題を解決するための手段】
【００１５】
本発明の第１態様は、第１パケットが分流路内の分岐ノードを通れば、該第１パケットに対応した第２パケットが合流路内の合流ノードを通り、且つ、該分岐ノードでの該第１パケットの分岐方向と該合流ノードでの該第２パケットの合流方向とが対応しており、該分岐ノードと該合流ノードとの間のパイプライン段数がＮ（Ｎ≧１）であるデータ駆動型処理装置の該合流ノードでの入力選択を制御する順序合流制御回路を、該合流路内の複数の合流ノードのそれぞれに関して備えたデータ駆動型処理装置用順序合流制御装置であって、各順序合流制御回路は、
Ｎ段以上のキューと、
該分岐ノードでのパケットに含まれる分岐方向情報を該キューの入力段へ転送させる第１転送制御回路と、
該キューの出力段の出力を該合流ノードの入力選択制御信号として転送させる第２転送制御回路と、を有する。【００１６】
本発明によるデータ駆動型処理装置用順序合流制御装置の第２態様では、第１態様において、該分岐方向情報は、行先アドレスのうち該分岐ノードから次段への行先を示すビットである。【００１７】
本発明によるデータ駆動型処理装置用順序合流制御装置の第３態様では、第１態様において、該第１転送制御回路は、該パケットに含まれる順序情報が順序有りを示している場合に、該入力段への転送を有効にする。【００１８】
本発明によるデータ駆動型処理装置用順序合流制御装置の第４態様では、第３態様において、該順序情報は、該パケットが該合流ノードへの途中のノードで消失する場合に順序無しを示す。【００１９】
本発明によるデータ駆動型処理装置用順序合流制御装置の第５態様では、第１態様において、該第１転送制御回路は、該分岐ノードから次段ノードへのＳＥＮＤ信号をアクティブにするときに、該キューの入力段へのＳＥＮＤ信号をアクティブにする。【００２０】
本発明によるデータ駆動型処理装置用順序合流制御装置の第６態様では、第５態様において、該第１転送制御回路は、該分岐ノードの後段からのＳＥＮＤ信号がアクティブであり、且つ、該分岐ノードの次段及び該キューの入力段からのＡＣＫ信号が共にアクティブであるときに、該分岐ノードにデータを取り込ませて保持させ、該次段及び該入力段へのＳＥＮＤ信号をアクティブにする。【００２１】
本発明によるデータ駆動型処理装置用順序合流制御装置の第７態様では、第１態様において、該第２転送制御回路は、該合流ノードの後段へのＡＣＫ信号をアクティブにするときに、該キューの出力段に対するＡＣＫをアクティブにする。【００２２】
本発明によるデータ駆動型処理装置用順序合流制御装置の第８態様では、第６態様において、該第２転送制御回路は、該キューの出力段及び該合流ノードの後段の一方からのＳＥＮＤ信号が共にアクティブになり且つ該合流ノードの次段からのＡＣＫ信号がアクティブになったときに、該合流段にデータを取り込ませて保持させ、該キューの出力段に対するＡＣＫをアクティブにする。【００２３】
本発明の第９態様では、第８態様において、該第２転送制御回路は、該第１パケットに対応した第２パケットが複数パケットで構成され、該複数パケットの末尾パケット以外の連接ビットが後続有りを示している場合、例外として、該キューの出力段に対するＡＣＫをインアクティブに維持する。【００２４】
本発明の第１０態様では、分岐ノードと合流ノードとを複数対備え、各対について、第１パケットが分岐ノードを通れば、該第１パケットに対応した第２パケットが合流ノードを通り、且つ、該分岐ノードでの該第１パケットの分岐方向と該合流ノードでの該第２パケットの合流方向とが対応しているデータ駆動型処理装置であって、さらに、
該複数対のうち、分岐ノードと合流ノードとの間のパイプライン段数が１以上である対のそれぞれに第１乃至９態様のいずれかに記載のデータ駆動型処理装置用順序合流制御装置を備えている。【００２５】
本発明の第１１態様では、第１０態様において、
第１入口ノードに供給されるパケットを、パケット内の行先アドレスの値に応じ下流側のノードへ順次選択的に分流させて、複数の第１出口ノードのうちの該値に対応したものへ到達させるツリー形分流路と、
該複数の第１出口ノードのそれぞれに対応した第２入口ノードを有し、パケットを下流側のノードへ順次選択的に合流させて第２出口ノードに到達させるツリー形合流路と、
各第１出口ノードとこれに対応する第２入口ノードとの間に結合され、該第１出口ノードからのパケットの内容に応じたパケットを該第２入口ノードへ供給する第１機能エレメントと、
を有し、該ツリー形分流路及び該ツリー形合流路の各ノードはパイプラインステージを構成し、該ツリー形分流路及び該ツリー形合流路はいずれも３ステージ以上有し、
該ツリー形分流路を構成する複数の分岐ノードと該ツリー形合流路を構成する複数の合流ノードとが該複数対を構成している。
【発明の効果】
【００２６】
パケットの順序の乱れは、選択的に合流するノードでのパケット追い越し、すなわち分岐ノードでのパケット順序が、これに対応した合流ノードでのパケット順序と相違することにより生ずる。【００２７】
上記第１態様の構成によれば、複数の分岐ノードのそれぞれについて、パケット分岐方向に基づき、これに対応した合流ノードでのパケット合流方向を制御するので、複数の合流ノード間で並列動作が可能になるとともに、場所によりパケット混雑度が異なっていても、パケットの順序を維持することが可能となるという効果を奏し、データ駆動型処理装置の基盤技術として寄与するところが大きい。【００２８】
上記第２態様の構成によれば、分岐方向情報が行先アドレスのうちの１ビットであるので、構成が簡単であるという効果を奏する。【００２９】
上記第３態様の構成によれば、パケットに含まれる順序情報が順序有りを示している場合のみパケット合流方向が制御されるので、順序に無関係なパケットを流路上に混在させることができるという効果を奏する。【００３０】
上記第４態様の構成によれば、合流ノードへの途中のノードで消失するパケットが存在しても本発明を適用できるという効果を奏する。【００３１】
上記第５又は６態様の構成によれば、一般的なハンドシェイクプロトコルによりキューの入力段へ分岐方向情報を転送することができるという効果を奏する。【００３２】
上記第７又は８態様の構成によれば、一般的なハンドシェイクプロトコルによりキューの出力段を制御することができるという効果を奏する。【００３３】
上記第９態様の構成によれば、分岐ノードでの１パケットが合流ノードでの複数パケットに対応する場合であっても、パケットの順序を維持することが可能となるという効果を奏する。【００３４】
上記第１０態様の構成によれば、流路が分岐ノードと合流ノードとを複数対備えた場合であっても、パケットの順序を維持することが可能となり、これによりパケット待ち合わせの構成を簡単化できるという効果を奏する。【００３５】
上記第１１態様の構成によれば、パイプラインステージ数が３以上のツリー形分流路とツリー形合流路とを備え、両者間に機能エレメントアレイを備えていても、上記効果を奏する。また、ツリー形分流路により多数の機能エレメントの１つに対しパケットを選択的に転送できるとともに、流路幅が比較的広い分流路出口側及び合流路入口側でパケットの混雑が避けられるので、機能エレメントでの処理の遅延が複数の機能エレメントでの分散並列処理により吸収され、ランダムアクセス又はランダム処理のスループットが比較的高いという効果を奏する。【００３６】
本発明の他の目的、構成及び効果は以下の説明から明らかになる。
【実施例１】
【００３７】
図１は、非同期（自己タイミング）式のデータ駆動型メモリ１０を示す概略ブロック図である。【００３８】
メモリ１０では、分流路２０の下流側に、機能エレメントアレイとしてのメモリ行アレイ３０を介して合流路４０が接続されている。【００３９】
図２（Ａ）は、メモリ行アレイ３０の配列の具体例を示す。【００４０】
メモリ行アレイ３０の行及び列をそれぞれセット番号及びページ番号で識別する。説明の簡単化のため、メモリ行アレイ３０が６４行、１ページが８ワード、１ワードが３２ビットであるとする。以下では、メモリ行アレイ３０に対するリード及びライトがそれぞれ、ページ単位及びワード単位で行われる場合を説明する。【００４１】
図１に戻って、分流路２０は、入口ノード２１１に供給されるパケットを、その行先アドレスに応じて順次選択的に分岐させるものであり、アドレスデコーダとして機能する。【００４２】
図２（Ｂ）は、分流路２０でのパケットのフォーマットを示す。【００４３】
パケット５０は、１ビットのコマンドフィールドと、１１ビットのアドレスフィールドと、３２ビットのデータフィールドとからなる。コマンドＣＭＤは、'０'のときリード、'１'のときライトを示す。アドレスＡＤＲは、上位６ビットの行先アドレスＤＡと、中位２ビットのページアドレスＰＡと、下位３ビットのワードアドレスＷＡとに分けられる。【００４４】
行先アドレスＤＡは、分流路２０の行先、すなわちメモリ行アレイ３０の行（セット番号）を示す。ページアドレスＰＡは、パケット５０が行先アドレスへ到達した後に、そのメモリ行におけるリード対象の識別に用いられる。ページアドレスＰＡとページ内ワードアドレスＷＡとの組は、パケット５０が行先アドレスへ到達した後に、メモリ行におけるライト対象の識別に用いられる。データＤＡＴＡは、ライトのデータであり、リードの場合にはダミーである。【００４５】
以下では、コマンドＣＭＤがリードの場合の分流路２０及び合流路４０でのパケットをそれぞれリードパケット及びリードデータパケット、ライトの場合の分流路２０でのパケットをライトデータパケットと称す。【００４６】
合流路４０でのリードデータパケットは、パケット５０からコマンドＣＭＤの１ビットを除いた４３ビットであり、アドレスＡＤＲは、合流路４０の出口ノードに到達したパケット内のデータの識別に用いられる。【００４７】
図１に戻って、分流路２０及び合流路４０はいずれも６段パイプラインであり、各パイプラインステージにおけるノードは、ラッチと、転送制御回路とを備えている。【００４８】
図３は、束データ方式で分流路２０を構成した場合の第１段と第２段とのノードで構成される分流回路を示す概略ブロック図である。【００４９】
第１段の入口ノード２１１は、ラッチ２１１Ｌと転送制御回路２１１Ｃとを備え、第２段のノード２２１は、ラッチ２２１Ｌと転送制御回路２２１Ｃとを備え、第２段のノード２２２は、ラッチ２２２Ｌと転送制御回路２２２Ｃとインバータ２２２Ｇとを備えている。転送制御回路２１１Ｃ、２２１Ｃ及び２２２Ｃはそれぞれ、ラッチ２１１Ｌ、２２１Ｌ及び２２２Ｌ内の入力段ゲート開閉をハンドシェイクプロトコルで行うものであり、段間が縦続接続されている。【００５０】
転送制御回路はいずれも、後段からのＳＥＮＤ−ＩＮ（転送要求入力）信号がアクティブ、すなわち後段からのデータが確定していて、前段からのＡＣＫ−ＩＮ（転送許可入力）信号がアクティブ、すなわち前段がエンプティである場合に、ラッチのクロック入力端ＣＫにパルスを供給して後段からのデータをラッチに取り込み保持し、特別な制限がなければ後段へのＡＣＫ−ＯＵＴ信号をアクティブにし、前段へデータが到達したと考えられる所定時間経過後に前段へのＳＥＮＤ−ＯＵＴ信号をアクティブにする。【００５１】
各転送制御回路は、出力を有効／無効にするための制御入力端を備えており、転送制御回路２２１Ｃ及び２２２Ｃの該制御入力端にはそれぞれ、ラッチ２１１Ｌに保持されたパケットの行先アドレス（ＤＡ５〜ＤＡ０）ＤＡの最上位ビットＤＡ５及びこれをインバータ２２２Ｇで反転させたものが供給される。したがって、ビットＤＡ５が'１'の場合、ラッチ２２１Ｌ及び２２２Ｌがそれぞれ有効及び無効になって、ラッチ２１１Ｌの内容がラッチ２２１Ｌに保持され、ビットＤＡ５が'０'の場合、ラッチ２２１Ｌ及び２２２Ｌがそれぞれ無効及び有効になって、ラッチ２１１Ｌの内容がラッチ２２２Ｌに保持される。【００５２】
各転送制御回路はさらに、不図示のリセット入力端を有し、システムリセット時にこれにリセットパルスが供給されて、ＡＣＫ−ＩＮ及びＡＣＫ−ＯＵＴがアクティブ、ＳＥＮＤ−ＩＮ及びＳＥＮＤ−ＯＵＴがインアクティブになる。【００５３】
転送制御回路は各種のものが公知であるので、その構成の説明を省略する。【００５４】
図１に戻って、例えばノード２２１に保持されたパケットは、行先アドレスＤＡの第２ビットに応じてノード２３１又はノード２３２に保持され、例えばノード２３２に保持されたパケットは、行先アドレスＤＡの第３ビットに応じてノード２４３又はノード２４４に保持される。以下同様にして、分流路２０の行先アドレスＤＡの内容に応じ、第６段に配置された３２個の出口ノードの１つにパケットが到達する。各出力ノードは２つの分岐出力を有する。【００５５】
各ノードにおいて、行先アドレスＤＡの対応するビットが'１'／'０'のとき図１においてそれぞれ上側／下側へデータが分岐するように定められているとする。例えば行先アドレスＤＡが'１１１１１１'の場合、このパケットは出力ノード２６１に到達する。ノード２６１において、行先アドレスＤＡの最下位ビットＤＡ０が'１'であるとき、メモリ行アレイ３０のメモリ行３１が有効にされ、ビットＤＡ０が'０'であるとき、メモリ行３２が有効にされる。【００５６】
メモリ行アレイ３０を構成する６４個のメモリ行は、互いに同一構成である。各メモリ行は、その入力端及び出力端がそれぞれ分流路２０及び合流路４０の対応する出力端及入力端に結合されている。分流路２０の出力端及び合流路４０の入力端のそれぞれにラッチを接続することもできるが、段数を少なくしてターンアランドタイムを短縮するために、図１ではこれらのラッチが省略された構成となっている。【００５７】
図５は、図１の分流路２０の出力ノード２６１と合流路４０の入口ノード４１１との間に接続されたメモリ行３１及び３２を示す概略ブロック図である。【００５８】
メモリ行３１及び３２は、ノード２６１と入口ノード４１１との間に接続されている。ノード２６１は、ラッチ２６１Ｌと、この入力ゲートを開閉する転送制御回路２６１Ｃとからなり、入口ノード４１１は、ラッチ４１１Ｌと、この入力ゲートを開閉する転送制御回路４１１Ｃとからなる。【００５９】
メモリ行３１及び３２には、ループ状の３２ビットのデータバスとアドレスＡＤＲの上位８ビットのアドレスバスからなるループ配線３１０が配設され、これがラッチ２６１Ｌのデータ出力端及びラッチ４１１Ｌのデータ入力端に接続されている。ループ配線３１０のデータバスには、メモリ行３１の構成要素である３２個のワードメモリ３１０Ｗ〜３１３１Ｗのそれぞれのデータ入力端及びデータ出力端が接続され、同様にメモリ行３２の構成要素である３２個のワードメモリ３２０Ｗ〜３２３１Ｗのそれぞれのデータ入力端及びデータ出力端が接続されている。【００６０】
これらワードメモリ３１０Ｗ〜３１３１Ｗ及び３２０Ｗ〜３２３１Ｗのそれぞれのクロック入力端ＣＫ及び出力イネーブル制御入力端ＯＥを制御するために、転送制御回路２６１Ｃと転送制御回路４１１Ｃとの間に制御回路３１１が接続されている。【００６１】
制御回路３１１には、ラッチ２６１Ｌに保持されたコマンドＣＭＤ、ページアドレスＰＡ、ワードアドレスＷＡ及びにラッチ４１１Ｌのクロック入力端ＣＫに供給されるクロックパルスＣＫ１が供給される。制御回路３１１は、このクロックパルスＣＫ１をカウントするカウンタ３１１ａを備え、リードの場合、そのカウントをワードアドレスＷＸとして、ラッチ４１１Ｌのデータ入力端のワードアドレスＷＡ部に供給する。【００６２】
制御回路３１１は、転送制御回路２６１ＣからのＳＥＮＤ１及び転送制御回路４１１ＣからのＡＣＫ２のいずれか一方又は両方がインアクティブの場合には、各ワードメモリのクロック入力端ＣＫ及び出力イネーブル制御入力端ＯＥをインアクティブに維持してその入力ゲート及び出力ゲートを閉じる（ワードメモリのアクセスを無効にする）。【００６３】
制御回路３１１は、転送制御回路２６１ＣからのＳＥＮＤ１及び４４１ＣからのＡＣＫ２が共にアクティブになると、カウンタ３１１ａをゼロクリアし、アドレスＡＤＲのうち、ビットＤＡ０が'１'であればワードメモリ３２０Ｗ〜３２３１Ｗのアクセスを無効にし、以下のような制御を行う。【００６４】
制御回路３１１は、コマンドＣＭＤがリードを示していれば、転送制御回路２６１Ｃに対するＡＣＫ１をインアクティブに維持した状態で、次のような制御を行う。【００６５】
（１）ワードメモリ３１３１Ｗ〜３１０Ｗのうち、ページアドレスＰＡとワードアドレスＷＸとで指定されるワードメモリの出力イネーブル制御入力端ＯＥをアクティブにさせて、このワードメモリの内容をループ配線３１０上に読み出させ、このデータがラッチ４１１Ｌのデータ入力端で確定したと考えられる所定時間経過後に、ＳＥＮＤ２をアクティブにさせる。転送制御回路４１１Ｃはこれに応答して、次段からのＡＣＫがアクティブであれば、クロックパルスＣＫ１をラッチ４１１Ｌのクロック入力端ＣＫに供給してループ配線３１０上のデータ（ＤＡＴＡ、ＤＡ及びＰＡ）及び制御回路３１１からのワードアドレスＷＸをラッチ４１１Ｌに取り込ませ保持させ、次いでＡＣＫ２をアクティブにさせる。制御回路３１１は、クロックパルスＣＫ１をカウンタ３１１ａでカウントしてワードアドレスＷＸをインクリメントし、ＡＣＫ２のアクティブに応答してＳＥＮＤ２をインアクティブにさせる。【００６６】
（２）入口ノード４１１から次段へのデータ転送が完了すると、ＡＣＫ２がアクティブになり、制御回路３１１はこれに応答して、カウンタ３１１ａの値が８未満であれば（１）へ戻る。【００６７】
カウンタ３１１ａの値が８になれば、転送制御回路２６１Ｃに対するＡＣＫ１をアクティブにして、ラッチ２６１Ｌがその後段からのデータを取り込めるようにさせる。【００６８】
このような処理により、ノード２６１に保持されたアドレスＡＤＲのページアドレスＰＡで示される８ワードの記憶内容が順次メモリ行３１からラッチ４１１Ｌへ転送される。【００６９】
制御回路３１１は、コマンドＣＭＤがライトを示していれば、ＳＥＮＤ２をインアクティブに維持した状態で、アドレスＡＤＲのページアドレスＰＡとワードアドレスＷＡとで指定されるワードメモリのクロック入力端ＣＫにパルスを供給して、ループ配線３１０上のデータをこのワードメモリに取り込ませ保持させ、次いでＡＣＫ１をアクティブにする。【００７０】
このようなメモリアクセスを、メモリ行アレイ３０のうち最大３２個のメモリ行に対し同時に行うことが可能である。【００７１】
リードパケットの場合、図１に戻って、合流路４０のどの入口ノードからでも、出口ノード４６１に到達する。すなわち、合流路４０では、経路選択に行先アドレスを用いる必要がない。合流路４０の各ノードでは、２入力のうち先に到達したデータを選択的に保持する。【００７２】
図４は、束データ方式で合流路４０を構成した場合の第２段と第３段の一部である合流回路を示す概略ブロック図である。【００７３】
第２段のノード４２１は、ラッチ４２１Ｌと転送制御回路４２１Ｃとを備え、第２段のノード４２２は、ラッチ４２２Ｌと転送制御回路４２２Ｃとインバータ４２２Ｇとを備え、第３段のノード４３１は、ラッチ４３１Ｌと転送制御回路４３１Ｃとを備えている。転送制御回路４２１Ｃ、４２２Ｃ及び４３１Ｃはそれぞれ、ラッチ４２１Ｌ、４２２Ｌ及び４３１Ｌ内の入力段ゲート開閉をハンドシェイクプロトコルで行うものであり、段間が縦続接続されている。【００７４】
図４の回路は、図３の回路において信号の方向を逆にしたものになっている。但し、行き先アドレスのビットによる制御は行われていない。また、ラッチ４２１Ｌの出力とラッチ４２２Ｌの出力との衝突を避けるため、各ラッチは出力イネーブル制御入力端ＯＥを備え、転送制御回路４３１Ｃからラッチ４２１Ｌの出力イネーブル制御入力端ＯＥへ直接、ラッチ４２２Ｌにはインバータ４２２Ｇを介して出力イネーブル制御入力端ＯＥへ、制御信号が供給される。転送制御回路４３１Ｃは、転送制御回路４２１ＣからのＳＥＮＤ−ＩＮと転送制御回路４２２ＣからのＳＥＮＤ−ＩＮのうち先にアクティブになった方に対応するラッチの出力イネーブル制御入力端ＯＥを'１'にし、他方を'０'にする。【００７５】
このような制御により、選択的（排他的）合流が行われる。【００７６】
上記の如く構成されたメモリ１０において、入口ノード２１１にライトデータパケットを供給するとともに、入口ノード２１１へのＳＥＮＤ−ＩＮ信号をアクティブにさせると、その行先アドレスに応じ分流路２０内のパイプラインステージを順次流れてメモリ行アレイ３０に到達し、ライトデータパケット内のアドレスＡＤＲで指定されたワードに、ライトデータパケット内のデータＤＡＴＡが書き込まれる。【００７７】
同様に、入口ノード２１１にリードパケットを供給するとともに、入口ノード２１１へのＳＥＮＤ−ＩＮ信号をアクティブにさせると、その行先アドレスＤＡに応じ分流路２０内のパイプラインステージを順次流れてメモリ行アレイ３０に到達し、リードパケット内のページアドレスＰＡで指定されたページのデータがワード単位で順次読み出され、行先アドレスＤＡの値とは無関係に、合流路４０内のパイプラインステージを順次通って出口ノード４６１に８ワード分のデータが到達する。【００７８】
入口ノード２１１内のパケットがノード２２１又はノード２２２に転送されてＡＣＫ−ＯＵＴ信号がアクティブになると、次のパケットを入口ノード２１１に保持させることができる。また、次に供給するパケットの種類は、先に供給したパケットがリードパケットであるかライトデータパケットであるかによらず、任意である。【００７９】
本実施例１のメモリ１０によれば、メモリ行アレイ３０を介してツリー形分流路２０及びツリー形合流路４０を配設するという簡単な構成で、集積配置されたメモリ行アレイ３０の任意の１行に対し、行き先アドレスを含むパケットを転送し、これに対応したパケットをツリー形合流路４０の出口ノード４６１から取り出すことができるという効果を奏する。【００８０】
また、流路幅が比較的広い分流路２０の出口側及び合流路４０の入口側でパケットの混雑が避けられるので、メモリ行での処理の遅延が複数のメモリ行での分散並列処理により吸収され、ランダムアクセスのスループットが比較的高いという効果を奏する。【００８１】
さらに、データ駆動型回路でプロセッサを構成した場合、非データ駆動型メモリを多数用いて並列度を上げるよりも１つのデータ駆動型メモリを用いた方が消費電力を大幅に低減できるので、特に長電池寿命が要求されるモバイル機器に用いて好適であるという効果を奏する。【００８２】
なお、本実施例１ではページ単位でのリードについて説明したが、行単位、ワード単位又はバイト単位等でのアクセスであってもよいことは勿論である。この点は、以下の実施例においても同様である。
【実施例２】
【００８３】
図１のメモリ１０では、並列度が高いにもかかわらず入口ノード及び出口ノードがそれぞれ１つである点がボトルネックとなっている。図６は、この点を改良した本発明の実施例２のメモリ１０Ａを示す。【００８４】
このメモリ１０Ａでは、分流路２０Ａに入口ノード２１２が追加され、入口ノード２１２の出力がノード２２１及び２２２Ａに供給されて、第２段のノード２２１Ａ及び２２２Ａが２合流・２分岐回路となっている。この合流は上述の選択型であり、例えばノード２２１Ａは、入口ノード２１１と２１２からのＳＥＮＤ−ＩＮのうち先にアクティブになったものに対応するデータを取り込んで保持する。この分流路２０Ａにおいても、図１の分流路２０と同様に、行先アドレスＤＡのみで定まる出口ノードへ到達する。したがって、ライトデータパケットについては新たな規則を設ける必要がない。【００８５】
合流路４０Ａでは、出力段に出口ノード４６２を追加し、ノード４５１Ａ又はノード４６２Ａから出口ノード４６２へ転送可能にしている。ノード４５１Ａ及び４６２Ａはいずれも、２合流・２分岐回路である。【００８６】
ここで、ノード４５１Ａから出口ノード４６１又は出口ノード４６２のいずれにデータを転送させるかの規則が必要になる。例えば、出口ノード４６１と４６２に優先順位を付け、両方がエンプティ（ＡＣＫ−ＩＮがアクティブ）である場合にはノード４５１Ａから優先順位の高いものの方へ転送させ、一方のみ空いている場合にはそちらへ転送させるように構成することもできる。【００８７】
本実施例では、データ流を整然とさせるため、図７（Ａ）に示すように、パケット５０Ａに１ビットの系統ＣＨを追加し、この値が'０'のときはノード４５１Ａ又はノード４５２Ａから出口ノード４６２へ転送させ、'１'のときには、ノード４５１Ａ又はノード４５２Ａから出口ノード４６１へ転送させる。系統ＣＨの値は、リードパケットを入口ノード２１１と２１２とのいずれに供給するかにより定める。例えば、入口ノード２１２にパケットを供給するとき、系統ＣＨに'１'をセットし、入口ノード２１１に供給するとき、系統ＣＨに'０'をセットする。【００８８】
このようにしてリードパケットを入口ノード２１１へ供給すると、メモリ行アレイ３０から読み出されるデータは必ず出口ノード４６１に到達し、リードパケットを入口ノード２１２へ供給すると、メモリ行アレイ３０から読み出されるデータは必ず出口ノード４６２に到達する。パケット経路は論理的対称性を有する。すなわち、メモリ行アレイ３０の列に関し分流路２０Ａと合流路４０Ａとでパケット経路が論理的に対称（第１の対称性）になる。また、互いに相補的な行先アドレス、例えば行先アドレス０１１０１１を有するパケットの経路と行先アドレス１００１００を有するパケットの経路とが、流路方向の軸に関し互いに、論理的に対称（第２の対称性）になる。本発明では、少なくとも第２の対称性を備えておればよい。【００８９】
図７（Ｂ）は、系統ＣＨが'０'である場合に分流路２０Ａの第１及び第２段を通り得るリードパケットの経路と、読み出されたリードデータパケットが通り得る、合流路４０Ａの第５段及び第６段の経路とを示している。点線は系統ＣＨが'０'である場合を示し、実線は系統ＣＨが'１'である場合を示す。【００９０】
リードパケットの行先は、系統ＣＨの値によらず、行先アドレスＤＡの値のみで定まる。例えば、系統ＣＨが'１'で行先アドレスＤＡの最上位ビットが'１'の場合、上述のように'１'で図７（Ｂ）の上側へ分岐し'０'で下側へ分岐すると定めると、入口ノード２１１に供給されたパケットはノード２２１Ａへ進む。【００９１】
合流路４０Ａでは、第５段まで合流はあっても分岐がないので、系統ＣＨや行先アドレスＤＡの値と無関係に経路が一意的に定まり、前記の場合、リードデータパケットはノード４５１Ａに到達する。【００９２】
系統ＣＨが'１'であるので、ノード４５１Ａから４６１Ａへ進む。行先アドレスＤＡの最上位ビットが'０'の場合についても同様にして、リードデータパケットは出口ノード４６１に到達する。すなわち、合流路４０Ａの第５〜６段での経路を系統ＣＨの値で定めると、メモリ行アレイ３０に関し分流路２０Ａと合流路４０Ａとで経路が対称になり、系統ＣＨが'１'の場合には必ず、分流路２０Ａの入口ノード２１１に対応した合流路４０Ａのノード４６１Ａに到達する。【００９３】
他の点は上記第１実施例と同一である。【００９４】
本実施例２によれば、上記のようなノードの追加及び変更により、メモリ１０Ａの入力ポート及び出力ポートの数が２倍になるので、スループットを大きく向上させることができるという効果を奏する。【００９５】
また、２系統で、流路幅が比較的広い分流路２０Ａの後段及び合流路４０Ａの前段を共用するので、パフォーマンス低下を抑制しつつ通信路の規模に対する並列度を高くすることができるという効果を奏する。【００９６】
さらに、パケット５０Ａに系統ＣＨを追加し、合流路４０Ａの出口側の合流・分岐回路で系統ＣＨの値に従って分岐させることにより、分流路２０Ａのどの入口ノードにリードパケットを供給すれば合流路４０Ａのどの出口ノードからリードデータパケットが得られるかが定まるので、合流路４０Ａから取り出されたデータの処理が容易になるという効果を奏する。
【実施例３】
【００９７】
図８は、入力ポート及び出力ポートの数を実施例２の場合の２倍にした、本発明の実施例３のメモリ１０Ｂを示す。【００９８】
このメモリ１０Ｂでは、パケットの流れの方向の軸に関し構成が対称になるように、図６の構成にノードが追加されている。【００９９】
すなわち、分流路２０Ｂの入力段に入口ノード２１３及び２１４が追加され、第２段にノード２２３Ａ及び２２４Ａが追加され、これらの間の接続が、ノード２１１及び２１２とノード２２１Ａ及び２２２Ａとの間の接続と同じになっている。また、分流路２０Ｂの第３段の各ノードも第２段と同様に２合流・２分岐回路にし、上記対称になるように第２段と第３段との間が接続されている。【０１００】
分流路２０Ｂを流れるパケットの経路は、実施例２の場合と同様に、行先アドレスＤＡのみにより定まる。したがって、ライトデータパケットについては新たな規則を設ける必要がない。【０１０１】
合流路４０Ｂについても分流路２０Ｂと同様に、出力段にノード４６３Ａ及び４６４Ａが追加され、この後段にノード４５３Ａ及び４５４Ａが追加され、これらの間の接続が、ノード４６１Ａ及び４６２Ａとノード４５１Ａ及び４５２Ａとの間の接続と同じになっている。また、合流路４０Ｂのさらに後段（第４段）の各ノードも第５段と同様に２合流・２分岐回路にし、上記対称になるように第４段と第５段との間が接続されている。【０１０２】
図９（Ａ）は、パケット５０Ｂのフォーマットを示す。このパケット５０Ｂは、系統ＣＨが２ビットであり、他の点は図７（Ａ）と同一である。リードパケットの場合、パケットが入口ノード２１４〜２１１に供給されるとき、それぞれ系統ＣＨの値を０〜３とする。これにより、メモリ行アレイ３０から読み出されたリードデータパケットは、メモリ行アレイ３０に関し分流路２０Ｂでの経路と対称な経路を通ることになる。【０１０３】
図９（Ｂ）は、系統ＣＨが'０１'である場合に分流路２０Ｂの第１〜３段を通り得るリードパケットの経路と、読み出されたリードデータパケットが通り得る経路とを点線で示している。【０１０４】
リードパケットの行先は、上述のように、系統ＣＨの値によらず行先アドレスＤＡの値のみで定まる。例えば、行先アドレスＤＡの上位２ビットが'１１'の場合、上述のように'１'で図１１（Ｂ）の上側へ分岐し'０'で下側へ分岐すると定めると、最上位ビットが'１'であるので入口ノード２１３からノード２２３Ａへ進み、次のビットが'１'であるのでノード２２３Ａから２３１Ａへ進む。【０１０５】
合流路４０Ｂでは、第４段まで合流はあっても分岐がないので、系統ＣＨや行先アドレスＤＡの値と無関係に経路が一意的に定まり、前記の場合、リードデータパケットはノード４４１Ａに到達する。【０１０６】
系統ＣＨが'０１'であり、この第２ビットが'０'であるので、ノード４４１Ａから４５３Ａへ進む。次に、第１ビットが'１'であるのでノード４５３Ａから４６３Ａへ進む。行先アドレスＤＡの上位２ビットが他の場合についても同様にして、リードデータパケットはノード４６３Ａに到達する。すなわち、合流路４０Ｂの第４〜６段での経路を系統ＣＨの値で定めると、メモリ行アレイ３０に関し分流路２０Ｂと合流路４０Ｂとで経路が対称になり、系統ＣＨが'０１'の場合には必ず、分流路２０Ｂの入口ノード２１３に対応した合流路４０Ｂのノード４６３Ａに到達する。【０１０７】
図９（Ｃ）は、系統ＣＨが'１１'である場合に分流路２０Ｂの第１〜３段を通り得るリードパケットの経路と、読み出されたリードデータパケットが通り得る経路とを点線で示している。【０１０８】
本実施例３によれば、上記実施例２の構成を少し変えただけで上記実施例２で述べた効果がさらに高められる。【０１０９】
また、４系統で分流路２０Ｂの流路幅が比較的広い第４〜６段及び合流路４０Ｂの流路幅が比較的広い第１〜４段のノードを共用するので、パフォーマンス低下を抑制しつつ通信路の規模に対する並列度を高くすることができるという効果を奏する。
【実施例４】
【０１１０】
図１０は、パイプライン段数を低減した、本発明の実施例４のメモリ１０Ｃを示す。【０１１１】
分流路２０Ｃでは、第３段の入力まで、図８の分流路２０Ｂのそれと同一である。分流路２０Ｂとの相違点は、第３段の各ノード及び第４段の各ノードの出力が４分岐となっている点である。これにより、分流路２０Ｂが６段パイプラインであるのに対し分流路２０Ｃは４段パイプラインとなる。合流路４０Ｃは、メモリ行アレイ３０に関し分流路２０Ｃと対称にし且つデータ流の方向を逆にした構成であり、４段パイプラインである。【０１１２】
実施例３の場合と同様に、分流路２０Ｃでのパケットの経路は、入口ノードが決まると、パケットの経路は行先アドレスのみで定まり、合流路４０Ｄについては、選択的分岐出力を持つノードからのパケット経路は、系統により定まる。【０１１３】
ノード入力端での合流の数が増えると、先着優先の選択的合流であるので、同一の合流ノードに転送されるパケット数が多くなると、転送待ちが生ずる。しかしながら、パケットが混雑していない時には、パイプライン段数が少ないので、レイテンシを短縮することができる。【０１１４】
ライトパケットのようにメモリ行アレイ３０への書き込みが１ワードで完了する場合には分流路２０Ｃの出口ノードでの待ち時間が比較的短いので効果的である。これに対し、リードデータパケットは、メモリ行３１から８ワードのデータが順次読み出されるので、合流路４０Ｃの入力ノードにおいて、他のメモリ行３１から同一入口ノードへの待ち時間が比較的長くなる。これを避けるためには、合流路４０Ｃの代わりに合流路４０Ｂを用いればよい。すなわち、分流路２０Ｃと合流路４０Ｃとを組み合わせればよい。
【実施例５】
【０１１５】
図１１は、選択的合流ノードへの転送待ちを短縮した、本発明の実施例５の２ポート入力・２ポート出力型のメモリ１０Ｄを示す。【０１１６】
図６の分流路２０Ａにおいて、選択的合流は第２段のノード２２１Ａ及び２２２Ａであり、第１段で待ちが生ずる。【０１１７】
そこで、分流路２０Ｄでは、第２段において選択的合流が生じないように、第２段にノード２２３及び２２４を追加している。ノード２２３からノード２３１Ａ又は２３３Ａへ分岐して合流し、ノード２２４からノード２３５Ａ又は２３７Ａへ分岐して合流する。【０１１８】
これにより、第３段の各ノードが選択的合流になるが、ノード数が４であるので、図６の分流路２０Ａの第１段でのパケット転送平均待ち時間よりも、分流路２０Ｄの第２段でのそれのほうが約半分になり、パケットの停滞を低減してスループットを向上させることができる。【０１１９】
他の点は、実施例２と同一である。
【実施例６】
【０１２０】
図１２は、入力ポート及び出力ポートの数を実施例５の場合の２倍にした、本発明の実施例６のメモリ１０Ｅを示す。【０１２１】
このメモリ１０Ｅでは、パケットの流れの方向の軸に関し構成が対称になるように、図１１の構成にノードが追加されている。【０１２２】
すなわち、分流路２０Ｅの入力段に入口ノード２１３及び２１４が追加され、第２段にノード２２５〜２２８が追加され、第３段に１つおきにノード２３２Ａ、２３４Ａ、２３６Ａ及び２３８Ａが追加され、これらとノード２２５〜２２８との間の接続が、図１１の分流路２０Ｄの第２段と第３段との間の接続と同じ形になっている。また、分流路２０Ｅの第４段の各ノードも第３段と同様に２合流・２分岐回路にし、上記対称になるように第３段と第４段との間が接続されている。【０１２３】
合流路４０Ｅは、メモリ行アレイ３０に関し分流路２０Ｅと対称にし且つデータ流の方向を逆にした構成である。【０１２４】
実施例５の場合と同様に、分流路２０Ｅでのパケットの経路は、入口ノードが決まると、パケットの経路は行先アドレスのみで定まり、合流路４０Ｅについては、選択的分岐出力を持つノードからのパケット経路は、系統により定まる。【０１２５】
本実施例６によれば、上記実施例５の構成を少し変えただけで上記実施例５で述べた効果がさらに高められる。
【実施例７】
【０１２６】
ＣＰＵでは一般に、２つのオペランドに対して処理を行う命令が多数有る。パイプライン段数が多いとレイテンシが長くなるが、１つのＣＰＵコアで時分割ｎ並列処理を行う場合、同期型では、切替時間がゼロであると仮定しても各処理の速度が１／ｎとなるので、例えばサーバーコンピュータのように並列度が高い場合には、非同期型の方が有利となる。【０１２７】
図１３は、本発明が適用された実施例７の、このような用途に用いて好適なプロセッサの一部であるデータ処理部１０ＡＰを示す概略ブロック図である。【０１２８】
この図に太線で示すように、合流路４０ＡＰのどの出口ノードにパケットが到達するかは系統値のみにより定まるので、同一系統に複数のパケットを連続して分流路２０Ａの入口ノードに供給することにより、これに対応したデータパケットを複数、合流路４０ＡＰの同一出口ノードに集めることができる。すなわち、系統値を同一にすることにより、出口ノードで複数のパケットの待ち合わせを自動的に行うことができる。【０１２９】
そこで、合流路４０ＡＰでは、出口ノード４６１ＡＰ〜４６４ＡＰのそれぞれに、処理要素を備えている。各処理要素での処理内容は、同一であっても、系統値により定まるものであってもよい。処理要素は、高機能であっても低機能であってもよい。３０Ｒは、レジスタファイルとして用いられる。レジスタファイル３０Ｒを、これら処理要素で共有する領域と個々に専用する領域とに、自由に分割することができる。【０１３０】
図１４（Ａ）は、コマンドＣＭＤを含む第１オペランドパケットＰ１と、第２オペランドパケットＰ２とを順次入口ノード２１１に投入したときに、これらに対応したパケットＰ１Ａ及びＰ２Ａがノード４６１Ｐに到達し、その処理要素により結果パケットＰ３が得られる場合を示している。第１オペランドパケットＰ１又は／及び第２オペランドパケットＰ２は、順次供給される複数のパケットであってもよい。【０１３１】
このパケットＰ３が、図１４（Ｂ）に示すパケットＰ１Ｎ及びＰ２Ｎのように、次のステップのパケットＰ１とＰ２とに対応したものである場合、これらを、ノード４７を介し入口ノード２１１にフィードバックさせることにより、処理を連続的に高速に行うことができる。ノード４７は、ノード４６１Ｐが出力したパケットＰ１Ｎに基づいて、処理が完了したか否かを判定し、肯定判定した場合には結果を出力し、パケットに含まれる処理モード（又はＣＭＤ）に基づいて、処理を打ち切り又は継続する。【０１３２】
分流路２０Ａは、デコーダとして機能するとともに、キューとしても機能する。また、合流路４０ＡＰの出口ノード以外のノードは、同一系統の処理要素へパケットを集配するとともに、キューとしても機能する。したがって、入口ノード２１１〜２１４にパケットが不定期に供給され、且つ、その平均時間が出口ノード４６１ＡＰ〜４６４ＡＰに備えられた処理要素の処理時間にほぼ等しい場合には、データ処理部１０ＡＰの外部にキューを設けることなく、効率よく処理を行うことができる。この平均時間は、入口ノード２１１〜２１４にパケットを供給する回路又は装置の並列度を調整することにより、適正な値に変更可能である。【０１３３】
また、１つのリードパケットに対しレジスタファイル３０Ｒから複数パケットが読み出される場合にも、合流路４０ＡＰの出口ノード以外のノードはこれらに対するキューとして機能し、キューを新たに設けることなく、効率よく処理を行うことができる。【０１３４】
したがって、データ処理部１０ＡＰ内の段数が比較的多くても、逆に利点となる場合がある。【０１３５】
並列度が高いと多数のデータを同時に使用するが、本実施例７のデータ処理部１０ＡＰによれば、比較的多数のレジスタを複数の処理要素において選択的に利用でき、かつ、実施例１で述べたように高スループットでランダムアクセスができるので、効率よく処理を行うことができるという効果を奏する。【０１３６】
また、従来ではＦＩＦＯメモリ、ハッシュメモリ、連想メモリ、演算部及び制御部等を備えたマッチングメモリで同一カラーのパケットを待ち合わせて処理要素で処理を行っていたので、構成が複雑であるとともに、処理が遅延してスループットが低下する原因となっていたが、本実施例７では、パケットペアが連続して合流するのでマッチングメモリを用いる必要が無く、構成が簡単になるとともにスループットが高くなるという効果を奏する。
【実施例８】
【０１３７】
図１４（Ａ）において、パケットＰ１に対しレジスタファイル３０Ｒから読み出されるデータが例えば上述のリードパケットのように８ワードである場合、通信路でデータが混雑する。この場合、演算結果のパケット数が少なければその下流側のデータ混雑度を低減することができる。【０１３８】
そこで、本発明のプロセッサのデータ処理部１０ＢＰでは、図１５において、合流路４０ＢＰの各ノードに処理要素を備え、パケットＰ１とＰ２（図１４）とが合流路４０ＢＰ上で合流したノードにおいて演算を行い、その結果を下流側に転送させる。【０１３９】
図１５に示す太線は、第１系統と第４系統でのパケットペアの経路を示す。これら経路は、行先アドレスＤＡと系統ＣＨとで定まる。レジスタファイル３０Ｒに関し分流路２０Ａ上の経路と合流路４０ＢＰ上の経路とが論理的に対称になるように系統ＣＨを定めれば、行先アドレスＤＡのみで合流路４０ＡＰ上の合流点が定まる。この合流点に対応する分流路２０Ａ上の分岐点は、パケットペアの行先アドレスＤＡの最上位ビットからの一致ビット数により定まる。【０１４０】
例えば図１５の上側のパケットペア経路Ｔ１及びＴ２の行先アドレスビットＤＡ１及びＤＡ２の一致部は、図１６（Ａ）に示すように上位２ビットの'１０'である。一致ビット数をｉで表すと、分流路２０Ａ上の第（ｉ＋１）段でパケットペアが分岐し、合流路４０ＡＰ上の第（６−ｉ）段でパケットペアが合流する。【０１４１】
パケット合流段識別子を、図１５中に示すように上記ｉの値で表し、合流路４０ＡＰ上の各ノードに、固定した合流段識別子の値を持たせ、これがパケットペアの合流段識別子ＭＡと一致する場合、そのノードの処理要素でパケットペアに対する処理を行う。図１６（Ｂ）は、合流段識別子ＭＡを含むパケットのフォーマットを示す。図１５中に示すように、後の実施例で用いる分流路２０Ａ上での分岐段ＩＤも、上記ｉの値で表す。【０１４２】
合流段識別子ＭＡの決定は、分流路２０Ａの後段側のノード２０１〜２０４において行う。図１４（Ｂ）に示すようにループを構成する場合には、ノード２０１〜２０４の配設位置は、合流路４０ＡＰの下流側であってもよい。【０１４３】
図１７は、ノード２０１の構成を示す概略ブロック図である。【０１４４】
このノード２０１は、ラッチ２０１Ｌと転送制御回路２０１Ｃとの基本構成のほかに、パケットペア判定部２０１Ｐと合流段ＩＤ決定部２０１Ｆとを備えている。【０１４５】
パケットペア判定部２０１Ｐは、ラッチ２０１Ｌの出力及びその後段のデータ出力が確定している場合、すなわちノード２０１から出力されるＳＥＮＤ２及び転送制御回路２０１Ｃに供給されるＳＥＮＤ１が同時にアクティブである場合、ラッチ２０１Ｌの下流側及び上流側のパケットに含まれるパケットタイプＰＴ（図１６（Ｂ））がそれぞれ第１オペランドパケット及び第２オペランドパケットであることを示していれば、パケットペアであると判定する。【０１４６】
合流段ＩＤ決定部２０１Ｆは、この判定に応答して、両パケットの行先アドレスＤＡに基づき、上述のようにして合流段識別子ＭＡを決定し、これを下流側ラッチに供給することにより、合流段識別子ＭＡを図１５のノード２１１のラッチに取り込ませ保持させる。
【実施例９】
【０１４７】
リードパケットのペア（第１オペランドパケット及び第２オペランドパケット）に対し、第１パケットに含まれるコマンドに応じた処理を行う場合、それぞれのリードパケットは、図１５の分流路２０Ａにおいて、図１６（Ｂ）に示すデータフィールドデータＤＡＴＡが空きになっている。一方、分流路２０Ｂでは入口ノード側の流路幅が比較的狭いので、パケット数が多いと混雑し易い。また、パケットペアを順次分流路２０Ｂに供給しても、合流ノードでは先着優先であるので、パケットペア間に他のパケットが割り込むことが考えられる。【０１４８】
そこで、リードパケットのペアを、図１８（Ａ）に示すように１パケットに圧縮する。図中、アドレスＡＤＲ１及びＡＤＲ２は、それぞれ第１オペランドアドレス及び第２オペランドアドレスである。これらの上位側ビットは、行先アドレスＤＡ１及びＤＡ２を除き、圧縮前の第１及び第２オペランドパケットに共通のフィールドであり、これにより圧縮率が高くなる。【０１４９】
図１８（Ａ）において、アドレスＡＤＲ１及びＡＤＲ２の上位ビットである行先アドレスＤＡ１及びＤＡ２がそれぞれページアドレスＰＡ１及びＰＡ２から離れた位置にあるのは、パケットをその先頭側の通信路層制御データとそれ以外の機能モジュール層データとに分けた為である。通信路層制御データは通信路のみで用いられ、機能モジュール層データは、機能モジュールとしてのレジスタファイル３０Ｒ、及び合流路４０ＢＰ上の各ノードに含まれる処理要素で用いられる。圧縮パケットの行先アドレスはＤＡ１とＤＡ２の上位側一致ビットであるので、これらの一方のみでよいが、上述のノード２０１〜２０４で用いられるので、両方とも通信路層制御データとしている。【０１５０】
ここで、アドレスＡＤＲ１とＡＤＲ２とは、行先アドレスＤＡが一般に異なるので、図１５において、分流路２０Ａ上のパケット経路Ｔ１及びＴ２の分岐点で、圧縮パケットをパケットペアに伸張する必要がある。どの段で分岐するかは、上述のようにノード２０１〜２０４で決定される合流段識別子ＭＡ（＝分岐段識別子）の値により定まる。【０１５１】
そこで、分流路２０Ａの各ノードに、圧縮パケットをパケットペアに伸張する機能を備え、そのノードに、固定の分岐段識別子を割り当てておき、パケット内の合流段識別子ＭＡ（＝分岐段識別子）の値が該ノードの分岐段識別子に一致したときに、圧縮パケットをパケットペアに伸張する。【０１５２】
図１８（Ａ）の圧縮パケット５０Ｄをパケットペアに伸張したパケット５０Ｅ及び５０Ｆをそれぞれ図１８（Ｂ）及び（Ｃ）に示す。パケット５０Ｅは、パケット５０Ｄをそのまま用いることができる。したがって、最初はパケット５０Ｄをコピーしたものをパケット５０Ｅとして次段へ転送させる。次いで、パケット５０Ｄ内の行先アドレスビットＤＡ１、ページアドレスＰＡ１及びワードアドレスＷＡ１をそれぞれ行先アドレスビットＤＡ２、ページアドレスＰＡ２及びワードアドレスＷＡ２に書き換えてこれをパケット５０Ｆとし、次段へ転送させる。【０１５３】
次に、レジスタファイル３０Ｒから１ページ分読み出したリードデータパケット及びレジスタファイル３０Ｒへの１ページ分のライトパケットについては、いずれも先頭パケットのフォーマットをパケット５０Ｅと同一にし、これに、図１８（Ｄ）に示すフォーマットのパケット５０Ｇを８個連接させる。そして、パケット５０Ｅの軌跡に沿ってパケット５０Ｇを転送させ、その各ノードで行き先方向を切り替えないことにより、転送中に他のパケットに割り込まれないようにして、これら９パケットを連続させる。【０１５４】
このような転送を可能にするために、一方では、各パケットに１ビットの連接ビットＣＮを備える。連接ビットＣＮが'１'のとき、これに後続するパケットが有ることを示し、'０'のとき、無いことを示す。図１９（Ａ）及び（Ｂ）はそれぞれ、パケットタイプＰＴが'０'の先頭パケットである第１オペランドパケット（レジスタファイル３０Ｒ内でコピーされた第１オペランドパケット）及びこれに続く、読み出された８ワードのリードデータパケットを示す。図１９（Ｃ）及び（Ｄ）はそれぞれ、パケットタイプＰＴが'１'の先頭パケットである第２オペランドパケット（レジスタファイル３０Ｒ内でコピーされた第２オペランドパケット）及びこれに続く、読み出された８ワードのリードデータパケットを示す。【０１５５】
なお、順序ビットＯＤの値は、分流路４０ＢＰを出た後に順序維持を必要とするか否かにより、機能エレメントアレイ３０Ｒにおいて決定される。【０１５６】
他方では、合流路４０ＢＰ上の各ノードに、連接ビットＣＮに対応したフリップフロップ（ノード側連接ビット）を備えておき、このフリップフロップの状態を次のように制御する。【０１５７】
図２１は、合流路４０ＢＰ上の入口ノード及び出口ノード以外の任意の合流ノードＮ１のノード側連接ビットＦ１に対する状態制御回路４７とこれに関連する要素を示すブロック図である。合流ノードＮ１の後段のノードＮ０１及びＮ０２並びに前段のノードＮ２のフリップフロップをそれぞれＦ０１、Ｆ０２及びＦ０３と表記する。【０１５８】
合流ノードＮ１は、フリップフロップＦ０１が'１'であれば先着優先の例外として、ノードＮ０１からのパケットを優先的に選択してラッチし、フリップフロップＦ０２が'１'であれば先着優先の例外として、ノードＮ０２からのパケットを優先的に選択してラッチする。【０１５９】
状態制御回路４７は以下のようにノード側連接ビットＦ１の状態を制御し、これにより、フリップフロップＦ０１及びＦ０２のうち一方が先に'１'になっているときに他方が後から'１'にならないようにする。【０１６０】
（１）状態制御回路４７は、フリップフロップＦ２が'０'であり、ノードＮ１がラッチしたパケットの連接ビットＣＮが'１'である場合、フリップフロップＦ１を'１'にする。【０１６１】
（２）状態制御回路４７は、ノードＮ１がラッチしたパケットの連接ビットＣＮが'０'であれば、フリップフロップＦ０１及びＦ０２を'０'にする。【０１６２】
（３）状態制御回路４７は、ノードＮ１がラッチしたパケットの連接ビットＣＮが'０'であり、ノードＮ１の合流段識別子がノードＮ１に保持されているパケットの合流段識別子ＭＡに一致していれば、フリップフロップＦ１を'０'にする。【０１６３】
合流路４０ＢＰ上の入口ノードのフリップフロップＦ１に対する状態制御回路４７は、上記（１）及び（３）のみの処理を行う。合流路４０ＢＰ上の出口ノードのフリップフロップＦ１に対する状態制御回路４７は、上記（２）及び（３）の処理を行い、上記（１）について、フリップフロップＦ２が'０'であるとみなした処理を行う。【０１６４】
図２０は、このようにしてセットされたフリップフロップをノード上の'１'で示す。【０１６５】
各処理要素は処理対象である９ワード×２のパケットを保持するキューを備えており、上述の制御により、２組の連接パケットの合流ノードでは、先着優先によりフリップフロップが先に'１'になった方のノードからの９パケットを連続して取り込み保持し、次いで他方のノードのフリップフロップが'１'になって、このノードからの９パケットを連続して取り込み保持することができ、２組の連接パケットの一方が他方に混入したり他のパケットが連接パケットに混入したりするのを防止することができる。【０１６６】
すなわち、第１オペランドの９パケットと第２オペランドの９パケットとがそれぞれ連接したものとなり、かつ、両者間が連接したものとなり、これらが処理要素に保持されて処理される。この処理要素で、処理結果が第１オペランドパケットと第２オペランドパケットとの２個になるとすると、処理結果を上述のように圧縮して１パケット化することにより、後流側でのパケットの混雑を避けるとともに、パケットに割り込みが生じないようにすることができる。【０１６７】
分流路２０Ａ上の９連接ライトパケットに関しても、リードデータパケットの場合と同様にして、フリップフロップが'１'のノードを通ってデータパケットを転送させる。この場合、分流ノードでは連接パケットへの割り込みが生じないので、その状態制御回路は上記合流ノードのそれよりも簡単になる。なお、ライトパケットに関しては、パケット間の演算を行わないので、連接ビットを用いずに、図１８（Ｂ）の下位１１ビットを３２ビットに変更し、パケット単位でライト処理を行うようにしてもよい。
【実施例１０】
【０１６８】
連接パケットに関しては、上記構成により連接パケット内でその順序が保たれる。【０１６９】
しかしながら、シングルパケット同士、連接パケット同士及びシングルパケットと連接パケットとの間では、先着優先であるので、同一系統であっても場所によるパケットの混み具合により、合流路の出力ノードでのパケット順序が分流路の入力ノードでのパケット順序と同一になるとは限らない。異なる系統間では、分流路の入り口ノード及び合流路の出口ノードでパケットの系統値がノード位置で定まるので、パケット順序は問題とならない。【０１７０】
次に、同一系統内でパケット順序が保たれている場合を、本発明の実施例１０として説明する。【０１７１】
図２２（Ａ）〜（Ｃ）及び図２３（Ａ）、（Ｂ）において、○印はパケットを示し、○印内の符号はパケットＩＤを示し、矢印はパケットの進む方向を示している。同じ符号のパケットは、同一パケットではなく、互いに対応していることを示している。パケットＩＤは、例えば処理対象のストリームＩＤである。簡単化のため、これらの図では１系統のみを示している。【０１７２】
データ駆動型処理回路では、一般に上述のように、互いに異なる処理対象のパケットを同一ループ内の各パイプラインステージで分散並列処理することができる。【０１７３】
図２２（Ａ）に示すように、ループ１００上の部分１０１で処理ＰＲ１を行い、次いでループ１００上の部分１０２で処理ＰＲ２を行う場合を考える。ループ１０１は、例えば図２４に示すような構成の１系統分を含んでいてもよい。【０１７４】
処理ＰＲ１の結果を処理ＰＲ２で用い又は処理ＰＲ２の結果を処理ＰＲ１で用いる場合に、図２２（Ｂ）に示すように、ループ１００を処理ＰＲ１のループ１０１Ａと処理ＰＲ２のループ１０２Ｂとに分割し、これらを結合ノード１０３で結合し、結合ノード１０３で、対応するパケット同士を待ち合わせて少なくとも一方から他方へ情報を伝達することにより、処理ＰＲ１とＰＲ２とで、少なくとも一方の処理結果を他方で利用する。【０１７５】
これにより、図２２（Ａ）の１直列処理が２並列処理となり、ループのパイプライン段数が低減するので、結合ノード１０３での待ち合わせ時間が短ければ、スループットが向上する。【０１７６】
例えばループ１０１Ａ上のパケット６が結合ノード１０３にラッチされたとき、これに対応したループ１０２Ａ上のパケット６が直ぐに結合ノード１０３に到達すれば、その結果を受け取って次のノードへ直ぐに移動できる。【０１７７】
しかし、例えばループ１０１Ａ上のパケット５がパケット６を追い越し、これが、対応するループ１０２Ａ上のパケット５と待ち合わせてその結果を取得し、結合ノード１０３から離れた後に、ループ１０１Ａ上のパケット６が結合ノード１０３でラッチされると、ループ１０２Ａ上のパケット６は結合ノード１０３を通過した後なので、その結果を用いることができなくなる。【０１７８】
これを避けるためにパケットを一時記憶させてそこからパケットの内容を取得するようにすると、処理が遅延するとともに、順次比較によりＩＤが一致するパケットを検索しなければならないので、構成が複雑になるとともに処理時間が長くなり、２並列化の意味がなくなる。【０１７９】
もし、パケットの順番が保たれれば、結合ノード１０３で相手パケットのＩＤを確認することなく、それぞれが対応するパケットの処理結果を用いることができ、スループットが向上するとともに、パケットのデータ幅を短縮して回路規模を縮小することができ、さらに、コンポーネント化が可能となるので、システムの構築が容易となる。【０１８０】
ループ１０２Ａ上のパケットは、加工されない定数であってもよい。すなわち、ループ１０２Ａはリングキュー（循環キュー）であってもよい。【０１８１】
例えば、ループ１０１Ａ上に第１パケットを投入し、ループ１０２Ａ上に該第１パケットと関係した第２パケットを投入し、結合ノード１０３は、ループ１０１Ａでのパケットに含まれるコマンド又は特定ビットが結合ノード１０３からの出力（分岐方向が出力側）を示している場合、これに対応してループ１０２Ａからパケットを取り出すことにより、ループ１０１Ａでの第１パケットに対応した処理結果のパケットとともに第２パケットを取り出す。これにより、ループ１０１Ａ上で常に第２パケットを同伴させる必要が無く、構成が簡単になる。【０１８２】
また、ループ１０２Ａがリングキューである場合、ループ１０１Ａはループ１０２Ａをスタックとして用いることができる。ループ１０１Ａと対応するループ１０２Ａ上のパケットが複数あっても、その個数ｎをループ１０１Ａ上のパケットに含ませておき、結合ノード１０３において、ループ１０２Ａ側のＳＥＮＤ−ＩＮがアクティブになったときにループ１０２Ａ側のＡＣＫ−ＯＵＴをアクティブにし、ループ１０１Ａ側のＡＣＫ−ＯＵＴをインアクティブに維持した状態でこれをｎ回繰り返すことにより、対応関係を保つことができる。【０１８３】
すなわち、ループ１０１Ａのパケットが個数ｎの情報を含み、このパケットを１個転送させるとともにループ１０２Ａのパケットをｎ個転送させることにより、ループ１０１Ａの１パケットをループ１０２Ａのｎパケットと対応させる。結合ノード１０３は、ループ１０１Ａのパケットのコマンド又は特定ビットが、このパケットの全部又は一部（処理結果）をコピーしてループ１０２Ａへ投入することを示している場合、これを実行してループ１０１Ａの該パケットに含まれる個数ｎをインクリメント（これは他のノードで行ってもよい）する。【０１８４】
前記の場合において、もし順序同期をとることができなければ、ループ１０２Ａを設けることができず、ループ１０１Ａ上のパケットは、対応するパケットをループ１０１Ａ上で連接させて引き連れていかなければならず、スループットが低下するとともに、ループ１０１Ａの構成及び処理が複雑になる。【０１８５】
順序同期は、条件によっては全てのパケットについてとる必要はない。このような場合、図１８に示すように、順序制御用の順序ビットＯＤをパケットに備え、これが'１'のとき順序制御有り、'０'のとき無しと定める。そして、結合ノード１０３においてループ１０２Ａ上の対応するパケットを待つ際に、順序ビットＯＤが'０'であればループ１０２Ａ側のＳＥＮＤ−ＩＮがアクティブのときにループ１０２Ａ側のＡＣＫ−ＯＵＴをアクティブにしてこれを通過させることにより、ループ１０２Ａ上に順序制御不要なパケットを混在させることができる。ループ１０１Ａ上についても同様である。【０１８６】
図２２及び２６中のパケットＡ〜Ｄは、順序ビットＯＤが'０'のものであり、その他のパケット１〜６は順序ビットＯＤが'１'のものを示している。【０１８７】
なお、ループ間でパケットの対応がとれればよいので、ループ１０１Ａへの初期パケットの投入とループ１０１Ｂへの初期パケットの投入は、異なるノードで行ってもよい。【０１８８】
また、ループ１０１Ａ及び１０２Ａは、条件分岐ノードを備え、パケットが含むコマンド又は特定ビットの値に応じてこのパケットの情報がループから外部へ取り出される。【０１８９】
図２２（Ｃ）は、より複雑な関係のループを示す。【０１９０】
この例では、ループ１０１Ａと１０１Ｂとが結合ノード１０３Ａで結合され、条件に応じて、ループ１０１Ａ上のパケットがループ１０１Ｂ上へ移動したり、その逆が行われたりするとする。同様に、ループ１０２Ａと１０２Ｂとが結合ノード１０３Ａで結合され、条件に応じて、ループ１０２Ａ上のパケットがループ１０２Ｂ上へ移動したり、その逆が行われたりするとする。また、同じ符号のパケットは同時に存在し得ず、ある時点ではどちらか一方のループに存在するとする。さらに、パケット１〜３はそれぞれパケット４〜６に対応しているとする。【０１９１】
このような複雑な場合でも、例えばループ１０１Ａ上のパケット３が結合ノード１０３Ａを通ってループ１０１Ｂ上へ移動する際に、結合ノード１０３Ａにおいてこれに対応するパケット６をループ１０２Ａ上から１０２Ｂ上へ上記同様の制御により移動させてパケット順序の同期を取ることにより、上述の利点を得ることができる。【０１９２】
待ち合わせ時間を短縮して順序同期の処理速度を速めるには、図２３（Ａ）に示すように、ループ１０２Ａと１０２Ｂとの間を、キュー１０４及び１０５を介して結合させ、処理結果のパケットを順次キューに格納し相手方が直ぐにこれから取り出せるようにすればよい。順序同期は、順序が予測できるので、予め処理結果をキューに入れておくことにより、処理結果を直ちに使用することが可能となる。【０１９３】
上述のようにループを分割することは、ハードウェアのコンポーネント化のみならず、階層構造化をも可能にする。すなわち、図２３（Ｂ）に示すように、上述のキュー１０４及び１０５を上階層のループ１０６で処理すれば、階層構造となる。この例では、上階層のループ１０６での処理結果がキュー１０７及び１０８を介してそれぞれ下階層のループ１０１Ａ及び１０２Ａにフィードバックされている。【０１９４】
以上のことは、各系統について成立するので、複数系統のそれぞれについて適用することができる。【０１９５】
なお、ループ処理は効率がよいが、ループを１回通る場合でも順序同期を適用できるので、処理はループでなくてもよい。【０１９６】
従来のデータ駆動型処理装置では、ローカルに同期を取って自律分散処理を行うことができるが、同期回路のシステムクロックに対応するものが存在しなかったので、自律分散処理に優れていても協調性が欠け、マイナーな存在であった。非同期回路において、パケットの順序を維持してループ間で順序同期をとることは、同期回路においてシステムクロックで同期をとることに対応している。【０１９７】
マクロのネットワークでの非同期通信では、通信路でのパケット順序を維持できなくても同期型のＣＰＵ及び記憶装置と、ソフトウェアとの組み合わせによる高級機能により、ＴＣＰ層で順序を復元でき、パケット順序とは直接関係なく高級機能で自律分散協調制御を行うことが出来る。これに対し、内部でミクロのネットワークが構成されるデータ駆動型処理装置では、パケットの順序維持が協調制御の基本となる。【０１９８】
本発明の順序同期は、自律分散による並列処理を維持しつつ簡単な構成で協調制御を可能にしデータ駆動型処理装置を高機能化するのに寄与するところが大きい。
【実施例１１】
【０１９９】
順序同期を実現するには、ループ状通信路でパケットの順序を同一系統内で維持する必要がある。パケットの順序を維持させるために順序合流を行わせる構成例を、本発明の実施例１１として説明する。【０２００】
分岐ノードでパケットが混雑していない方向へ分岐して先回りしても、同一系統ではその後、合流する。同一系統内でのパケットの順序の乱れは、選択的に合流するノードでのパケット追い越し、すなわち分岐ノードでのパケット順序が、これに対応した合流ノードでのパケット順序と相違することにより生ずる。【０２０１】
この相違が何に対応するかを調べるため、分岐ノードとこれに対応する合流ノードでのパケット進行方向に着目する。例えば図２４の合流路４０ＢＰ上のノード４３３Ｐを通過するパケットは、その前に、これに対応する分流路２０Ａ上のノード２４３を通過している。パケットがノード２４３から次の段のどちらへ進むかで、パケットがノード４３３Ｐの後段のどちらからノード４３３Ｐに進むかが定まるという規則性がある。図２４ではこの関係がレジスタファイル３０Ｒに関し対称になるが、必ずしもこれに限定されず、論理的な対応関係があればよい。【０２０２】
簡単化のため、リードデータパケットが１ワードの場合のリードパケットとこれに対応するリードデータパケットを考える。パケットの順序が保たれていれば、ノード２４３を順次通過するパケットのノード２４３での分岐方向の順序と、ノード４３３Ｐを順次通過するパケットのノード４３３Ｐでの分岐方向の順序とが対応する。【０２０３】
もし、全ての系統について、パケット順序が維持されていれば、合流路４０ＢＰ上の任意の合流ノードとこれに対応する分流路２０Ａ上の分岐ノード（ノードペア）とについて、この対応関係が成立する。もし、２つのパケット間の順序に乱れがあれば、いずれかのノードペアで該対応関係が不成立となる。【０２０４】
そこで、全てのノードペアについて、この対応関係を維持するように、合流路４０ＢＰ上のノードの切換を、これに対応する分流路２０Ａ上のノードの切換情報（Ｎ段前の時点での切換情報）に基づいて制御することにより、パケット順序を維持する。但し、分流路２０Ａの出口ノードと合流路４０ＢＰの入口ノードについては、Ｎ＝０であって、対応関係が既に維持されている。図２４の場合、Ｎは２、４、６、８及び１０である。【０２０５】
図２４において、例えば、ノード２４３を上側及び下側へ進むパケットの軌跡をそれぞれＴ１及びＴ２とする。軌跡Ｔ１のパケットが先にノード２４３に保持され、次に軌跡Ｔ２のパケットがノード２４３に保持されるとする。軌跡Ｔ１上でパケットが混雑し、軌跡Ｔ２上でパケットがすいていて、ノード４３３Ｐの後段には軌跡Ｔ２のパケットの方が先に到達したとする。この場合、ノード２４３で上側に切り替えたという情報がノード４３３Ｐへ伝達され、ノード４３３Ｐで上側からのパケットを待ち、これがノード４３３Ｐに保持された後に、ノード２４３で下側に切り替えたという情報がノード４３３へ伝達され、次にノード４３３Ｐで下側からのパケットを待つようにすれば、パケットの順序が維持される。全てのノードペアについて、このような制御を行えば、少なくとも同一系統内でパケットの順序が維持される。【０２０６】
図２５（Ａ）は、この順序を維持させるための合流路４０ＢＰの入口ノードを除く任意のノード１１０と、これに対応する分流路２０Ａ上のノード１１１との間に備えられた構成を示す。図２６は図２５（Ａ）の詳細ブロック図である。【０２０７】
図２５（Ａ）ではノード１１０とノード１１１との間でパケットが流れ得る流路を分岐合流ノード１１２と表す。【０２０８】
この構成では、ノード１１０と１１１との間にキュー１１３が備えられ、ＯＤ＝'１'であれば、ノード１１１からの分岐先方向を示す、行先アドレスＤＡの対応するビットＤＡｉ（図において上側分岐のとき'１'、下側分岐のとき'０'）が、キュー１１３の入力段１１３ａの１ビットラッチのデータ入力端に供給される。データ駆動型のキュー１１３は、転送制御回路で用いられるハンドシェイクプロトコルにより、途中にエンプティが存在すると自動的に詰められるという緩衝作用があるので、その段数は、ノード１１１とノード１１０との間のパイプライン段数Ｎ以上であればよい。キュー１１３の出力段から順次データを取り出せばよく、取り出す際に段数Ｎを考慮する必要はない。【０２０９】
ノード１１０とその後段１１５及び１１６との構成は、図４の対応する構成と実質的に同一である。すなわち、ノード１１０はラッチ１１０Ｌの入力側にマルチプレクサ１１０Ｍが接続されているが、これは図４のラッチ４２１Ｌ及び４２２Ｌ内の出力側のゲートと出力イネーブル制御入力端ＯＥとの構成に対応している。図４との相違点は、図２６ではマルチプレクサ１１０Ｍの選択制御をキュー１１３の出力段１１３ｂのラッチ出力ＳＥＬで行っている点である。【０２１０】
ノード１１１とその次段１１７及び１１８との構成は、図３の対応する構成と、ノード１１１の転送制御回路１１１Ｃを除き同一である。ノード１１１の転送制御回路１１１Ｃはキュー１１３の入力段１１３ａの転送制御回路との間についても信号授受を行っている点で、転送制御回路２１１Ｃと異なる。【０２１１】
なお、図２６の分岐合流回路１１２Ａは、図２５（Ａ）の分岐合流回路１１２からノード１１５〜１１８を除いた部分である。【０２１２】
ノード１１１から次段ノード１１７又は１１８へのＳＥＮＤをアクティブにするときに、同時にキュー１１３の入力段１１３ａへのＳＥＮＤをアクティブにする。すなわち、ノード１１１の転送制御回路１１１Ｃは、次段１１７又は１１８及び入力段１１３ａからのＡＣＫが共にアクティブであり且つ後段からのＳＥＮＤがアクティブであるときに次段１１７又は１１８及び入力段１１３ａへのＳＥＮＤをアクティブにする。【０２１３】
ノード１１０は、２入力のうち、キュー１１３の出力段１１３ｂの出力に基づいて、ノード１１０の後段１１５及び１１６のラッチ出力の一方を選択する。すなわち、キュー１１３の出力段１１３ｂの出力ＳＥＬが'１'であれば、ノード１１０の後段上側のノード１１５からのデータを選択し、'０'であれば、ノード１１０の後段下側のノード１１６からのデータを選択する。この選択は、キュー１１０の出力段１１３ｂのラッチ出力ＳＥＬによりノード１１０のマルチプレクサ１１０Ｍを選択制御することにより行われる。【０２１４】
ノード１１０は、その後段１１５又は１１６へのＡＣＫをアクティブにするときに、キュー１１３の出力段１１３ｂに対するＡＣＫをアクティブにする。すなわち、ノード１１０は、ノード１１０の後段１１５又は１１６及びキュー１１３の出力段１１３ｂからのＳＥＮＤが共にアクティブになり且つノード１１０の次段からのＡＣＫがアクティブになったときに、ノード１１０のラッチ１１０Ｌにデータを取り込ませて保持させ、キュー１１３の出力段１１３ｂ及びノード１１０の後段１１５又は１１６へのＡＣＫを共にアクティブにする。【０２１５】
図２５（Ｂ）及び図２６において、ＤＡｉ＝'１'のとき、ノード１１１は、ノード１１７へパケットを分岐転送させる（この分岐が第１段）とともにキュー１１３の入力段１１３ａにＤＡｉ＝'１'を転送させる。Ｎ段経過後に、一方ではこれに対応するパケットがノード１１５に保持され、他方ではマルチプレクサ１１０Ｍの選択制御入力端に、前記ＤＡｉ＝'１'に対応したＳＥＬ＝'１'が供給されて、ノード１１０はノード１１５側を選択する。図２５（Ｃ）においても同様である。【０２１６】
ここで、ライトパケットについては、レジスタファイル３０Ｒへの書き込みが終了し、合流路４０Ａ側へ対応するパケットが転送されないので、このパケットの順序ビットＯＤを'０'にしておく。転送制御回路１１１Ｃは、ノード１１１のラッチ１１１Ｌに保持した順序ビットＯＤが'０'であるとき、キューの入力段１１３へのＳＥＮＤをインアクティブに維持する。これによりキュー１１３の入力段１１３ａのラッチにはビットＤＡｉが転送されないので、順序維持の切り替えとは無関係になる。【０２１７】
一方、リードパケットのように分流路２０Ａ側の１パケットが合流路４０ＢＰ側の複数パケットに対応する場合、キュー１１３においてもこの対応関係を維持する必要がある。この対応関係を維持するために、ノード１１０の転送制御回路１１０Ｃは、連接ビットＣＮが'１'のときは例外として、キュー１１３の出力段１１３ｂへのＡＣＫをインアクティブに維持する。これにより、連接パケットについてもノード１１０とノード１１１とで切り替えの対応関係を保つことができる。連接パケットの末尾パケットは連接ビットＣＮが'０'であるが、その１つ前のパケットの連接ビットＣＮが'１'であるので、図２７（Ｊ）に示すように、末尾パケットに対してもノード１１０の選択方向は変わらない。【０２１８】
図２７（Ａ）〜（Ｊ）は、分流路２０Ａ側の１つのリードパケットの流れと、これに対応した合流路４０ＢＰ側の複数のリードデータパケット（連接パケット）の流れとを、時間を追って示す。図中の'１'は、上述のノード側フリップフロップの値を示す。図２７（Ａ）は４段分のデータ転送を纏めて示している。【０２１９】
（１）図２７（Ａ）で、ＤＡｉ＝'１'であればノード１１１から次段上側（'１'側）１１７へデータが転送されると共に、ＯＤ＝'１'であれば行先アドレスＤＡｉの値がキュー１１３の入力段１１３ａに転送される。【０２２０】
（２）図２７（Ｅ）で、連接先頭パケットがノード１１０の後段上側１１５に取り込まれて保持されるとともに、（１）で保持したＤＡｉ＝'１'がキュー１１３の出力段１１３ｂに取り込まれて保持され、ノード１１０のマルチプレクサ１１０Ｍはその選択制御入力端への'１'に応答して、ノード１１０の後段上側１１５のノードからのデータを選択する。【０２２１】
（３）これにより、図２７（Ｆ）で、ノード１１０はこのデータを取り込み保持する。【０２２２】
（４）その後、ノード１１０が保持しているパケットの連接ビットＣＮの値が'１'の間、ノード１１０の転送制御回路１１０Ｃからキュー１１３へのＡＣＫがインアクティブに維持されて、キュー１１３の出力段１１３ｂの出力ＳＥＬ＝'１'が維持され、ノード１１５（図２５）から連接パケットが順次ノード１１０へ到達する。【０２２３】
このようにして、分流路２０Ａの任意のノードから、合流路４０ＢＰの対応するノードへ、順序制御情報ＤＡｉ→ＳＥＬが伝達され、これに応じ合流ノードでの選択制御が行われ、これにより全ての系統についてパケットの順序が維持される。【０２２４】
したがって、この構成によれば、図２２及び図２３で述べた構成を実現して、その効果を達成することができる。【０２２５】
なお、順序ビットＯＤは、図２２及び図２３について説明した順序ビットＯＤとしても使用できる。【０２２６】
また、本発明の順序合流制御が行われるノード１１０とノード１１１との対は、ツリー形分流路とツリー形合流路の対応するノード対に限定されず、第１パケットが分岐ノードを通れば、該第１パケットに対応した第２パケットが合流ノードを通り、且つ、該分岐ノードでの該第１パケットの分岐方向と該合流ノードでの該第２パケットの合流方向とが対応しており、該分岐ノードと該合流ノードとの間のパイプライン段数がＮ（Ｎ≧１）であるという条件を満たす分岐ノードと合流ノードの対であればよい。【０２２７】
さらに、ノード１１０を通るパケットはノード１１１を通るパケットと対応しているが、この対応関係は、両者が同一パケットであってもよい。
【実施例１２】
【０２２８】
次に、本発明のデータ駆動型処理装置の適用例として、有限オートマトン動作を行うＣＰＵアクセラレータについて説明する。【０２２９】
有限オートマトンは、言語学、情報工学、生物学、数学、論理学など様々な領域で利用されている。有限オートマトンでは、現在状態と入力とにより、次状態が定まり、この状態遷移が繰り返し行われてパターン一致有無が判定される。【０２３０】
図３３は、簡単な有限オートマトンの例を示す状態遷移図である。【０２３１】
この例では、データストリームＤＳ＝"ＣＡＡＢＡＢＡＢＣＣＣＣＢＢＡＢＡＣＣ"の中に、検索データ集合ＲＤのパターン"ＡＢＡ"又は"ＡＢＣ"が含まれているか否かを決定する。現在の状態にデータストリームＤＳ中のエレメント"Ａ"、"Ｂ"又は"Ｃ"が入力されると、次の状態が定まり、これに次のエレメントが入力されるという処理が繰り返し行われ、出力時の状態が検出パターンに対応している。エレメントは文字コードに限定されず、所定のデータ幅のデータであればよい。【０２３２】
ウイルス検出の例で言うと、検索データ集合ＲＤに含まれるパターンのそれぞれがウイルスに対応している。入力データストリームＤＳが多数のウイルスのどれに感染しているかのパターンマッチング処理を、１つの状態遷移図で表すことができる（パターンマルチング）。【０２３３】
以下では、有限オートマトンをウイルス検出に適用した場合について説明するが、本発明のＣＰＵアクセラレータはこれに限定されるものではなく、全ての有限オートマトンに適用可能である。【０２３４】
本発明の装置では、並列度が高いので、同時に多数の入力データストリームＤＳを取り扱うことができる。【０２３５】
図２８は、行を状態Ｓ、入力である列を、データストリームを構成する１バイトのストリームエレメントＳＥとした状態遷移テーブルを示す。但し、この状態遷移テーブルには、１ビットの結果ビットＲが含まれている。【０２３６】
状態Ｓを上位ビット、ストリームエレメントＳＥを下位ビットとするアドレスに、次の状態が格納されたメモリを用いる。１６進数表記で、例えば状態Ｓの初期値を"００００"とし、ストリームエレメントＳＥが"０１"であった場合、次の状態Ｓは"０００２"となる。これと次のストリームエレメントＳＥとで、次の状態Ｓが定まる。【０２３７】
結果ビットＲは１ビットであり、ウイルスパターンが検出されたとき、Ｒ＝'１'となる。このときの状態Ｓで指定されるアドレスには、次の状態はなく、ウイルスコードＶＣが格納されている。ウイルスコードＶＣに対応したウイルス名は、ＣＰＵに管理させる。結果ビットＲは、パケット内のコマンドの役割を果たす。【０２３８】
図２９は、本発明が適用された、実施例１２のデータ駆動型ＣＰＵアクセラレータ６０Ｑを示す概略ブロック図である。【０２３９】
状態テーブルメモリ１２０は、例えば図８のメモリ１０Ｂの記憶容量を大きくしたものであり、その分流路１２１、メモリ行アレイ１２２及び合流路１２３はそれぞれ、図８の分流路２０Ｂ、メモリ行アレイ３０及び合流路４０Ｂに対応している。リードパケットに対するリードデータパケットは後述のように１ワードであり、これらのフォーマットは上述のものと異なる。メモリ行アレイ１２２には、図２８のテーブルが格納されている。【０２４０】
図３１は、図２９の装置における１系統に関するデータフローをデータフォーマットとともに示す図である。【０２４１】
系統ＣＨは、上述のように合流路１２３で用いられる定数である。結果ビットＲ及び状態Ｓは、状態テーブルメモリ１２０から読み出されたデータであり、これと、下位ビットとしてのストリームエレメントＳＥとで、状態テーブルメモリ１２０のアドレスが指定される。各系統で複数のデータストリームを処理することができ、そのストリーム識別子ＳＩＤをこの例では３ビットとしている。ストリーム識別子ＳＩＤ及び系統ＣＨは、状態テーブルメモリ１２０を含むループで、同一ストリームに対し不変である。【０２４２】
図２９に戻って、複数のデータストリームは、ＤＭＡＣにより、インターフェイス１２４及びメモリコントローラ１２５を介し、バッファとしてのＲＡＭ１２６に一時格納された後、ＣＰＵ１２７によりインターフェイス１２４及びメモリコントローラ１２５を介してＲＡＭ１２６の内容が読み出され、メモリコントローラ１２５、インターフェイス１２４及び１２８並びにストリームバッファ１３０の分流路１３１を介しキューアレイ１３２に供給され保持される。ＣＰＵ１２７、ＲＡＭ１２６、メモリコントローラ１２５及びインターフェイス１２８は同期型であり、インターフェイス１２８は、同期型と非同期型との相互変換部を備えている。【０２４３】
図３０は、図２９中のストリームバッファ１３０の概略ブロック図である。【０２４４】
このストリームバッファ１３０の分流路１３１及び合流路（マルチプレクサ）１３３０〜１３３３はそれぞれ、図１の分流路２０の第３〜５段を抽出したもの及び合流路４０の第２〜４段を抽出したものと同一である。分流路１３１は、インターフェイス１２４の端子数を少なくするためのものであり、この例では４組としているが、１組以上であればよい。【０２４５】
分流路１３１に供給されるパケットのフォーマットは、図３１に示す如く、３ビットのストリーム識別子ＳＩＤのフィールドと、８ビットのストリームエレメントＳＥのフィールドとからなる。【０２４６】
ストリーム識別子ＳＩＤは、４系統×８本のキューアレイ１３２の８本のキューＩＤと対応づけられている。このようなキューＩＤをストリーム識別子ＳＩＤと対応させることにより、分流路１３１で行先アドレス５ビットの下位３ビットとして用いられたストリーム識別子ＳＩＤは、分流路１３１を出ると不要となり、キューアレイ１３２では８ビットのストリームエレメントＳＥのみ保持される。マルチプレクサ１３３０〜１３３３はそれぞれ系統０〜３の８本のキューの１つを選択して、それぞれノード１４０〜１４３に供給する。この選択は、分流路１２１へ転送しようとするパケットに含まれるストリーム識別子ＳＩＤであるＳＩＤ０〜ＳＩＤ３をそれぞれデコーダ１４５〜１４８でデコードした制御信号により行われる。【０２４７】
マルチプレクサ１３３０〜１３３３は、通常の構成を用いることができるが、図３０に示すように８入力１出力の合流路を用いてもよい。この場合、ストリーム識別子ＳＩＤをデコードして、８本のキューのうちの対応する１つのキューの出力段に対してのみＡＣＫをアクティブにすればよい。この場合のデコーダは、１入力８出力の分流路を用いることができる。【０２４８】
キューアレイ１３２を構成する各キューについて、半空になったときには、これを半空検出回路１３４で検出し、そのキューの系統ＣＨとストリーム識別子ＳＩＤとを伴って、インターフェイス１２８及び１２４を介したＣＰＵ１２７への割込要求ＩＲＱ２をアクティブにする。これによりＣＰＵ１２７は、ＲＡＭ１２６からデータを読み出して、対応する系統ＣＨ及びストリーム識別子ＳＩＤのキューにこれを補給する。ＲＡＭ１２６からインターフェイス１２４にはＤＭＡ転送することができる。【０２４９】
半空検出は例えば、設定時間内におけるキューアレイ１３２の先頭でのＳＥＮＤ−ＯＵＴパルス数と中間部でのそれとの差が所定値以上となったことにより検出することができる。またキューアレイ１３２のそれぞれのキューについて、出力されるパケット数（ラッチパルス数）と供給されるパケット数（ラッチパルス数）とをカウントし、その差が設定値以上になったとき、同様に割込要求ＩＲＱ２をアクティブにする構成であってもよい。半空でなく、キューの所定割合が空になったことを検出してもよいことは勿論である。【０２５０】
ノード１５０〜１５３のパケットは、結果ビットＲを含む必要がない。合成ノード１４０〜１４３にはそれぞれ、一方ではノード１５０〜１５３からパケットが供給され、これらのストリーム識別子ＳＩＤがそれぞれＳＩＤ０〜ＳＩＤ３としてマルチプレクサ１３３０〜１３３３に対する選択制御信号として供給され、他方ではマルチプレクサ１３３０〜１３３３からのストリームエレメントＳＥが合成ノード１４０〜１４３に付加されて合成され、合成ノード１４０〜１４３に取り込まれ保持される。【０２５１】
合成ノード１４０〜１４３の出力が分流路１２１に転送される。合成ノード１４０〜１４３を省略し、これらの替わりに分流路１２１の入口ノードを用いてもよい。【０２５２】
ノード１５０〜１５３には、ＣＰＵ１２７からインターフェイス１２４及び１２８を介した初期パケットと、合流路１２３からのパケットとが選択的に合流する。この初期パケットは、ＣＰＵアクセラレータ６０Ｑを起動させるためのものであり、図３１において、例えばＳ＝０、Ｒ＝０とし、系統ＣＨ及びストリーム識別子ＳＩＤをそれぞれの系統ごとに与えたものである。【０２５３】
ストリーム識別子ＳＩＤの値は、ＣＰＵ１２７がインターフェイス１２４、１２８及び分流路１３１を介しキューアレイ１３２にデータストリームを供給したものであればよく、ＣＰＵ１２７が定めることができる。【０２５４】
ＣＰＵ１２７は、ノード１５０〜１５３のそれぞれに１つ又は複数の初期パケットを順次供給する。ＣＰＵ１２７はこの際、合流路１２３の対応する出口ノードに対するＡＣＫをインアクティブにして、出口ノードからのパケットの流れを停止させておく。次いでこの停止を解除すると、状態テーブルメモリ１２０を含むループ内でパケットがパイプライン処理される。各系統の初期パケットは、本実施例では最大８個である。実際には、ループ内にパケットを分散させることができるので、その最大値は状態テーブルメモリ１２０の全段数に２を加えたものとすることができる。【０２５５】
状態テーブルメモリ１２０の合流路１２３の各系統の出口ノードの出力は、出力回路１６０に供給される。【０２５６】
出力回路１６０は、４系統の結果ビットＲのいずれかが'１'となると、その系統ＣＨ、ストリーム識別子ＳＩＤ及びウイルスコードＶＣを取り込んで保持し、ＣＰＵ１２７に対し、これらを供給するとともに割込要求ＩＲＱ１をアクティブにする。各データストリームについて、１つのウイルスを検出すればそのストリームに対する処理を打ち切ることができる。この場合、ストリームバッファ１３０内の、ウイルスが検出されたストリームをフラッシュし又は／及びこのストリームの追加を停止し、未処理ストリームがあればストリームバッファ１３０へ他のストリームを供給し、これに対応して初期パケットを、上述のように供給し、該他のストリームに対する処理を開始する。【０２５７】
本実施例１２によれば、ＣＰＵアクセラレータ６０Ｑがデータ駆動型で構成されており、さらに状態テーブルメモリ１２０とストリームバッファ１３０とが並列動作するので、処理の並列度が高くてスループットが高いとともに、低消費電力であり、各種モバイル機器に好適である。
【実施例１３】
【０２５８】
図３２は、本発明が適用された、実施例１３の順序同期・データ駆動型ＣＰＵアクセラレータ６０ＱＡを示す概略ブロック図である。【０２５９】
このＣＰＵアクセラレータ６０ＱＡではまず、ストリームバッファ１３０Ａの分流路１３１Ａを、図１の６段分流路２０を５段にしたもので構成するとともに、インターフェイス１２８Ａから、一方では分岐ノード１６３を介して分流路１３１Ａへデータストリームを転送させ、他方では分岐ノード１６１及びデマルチプレクサ（分流路）１６２を介して初期パケットをノード１５０〜１５３へ供給することにより、インターフェイス１２８Ａの出力端子数を低減している。【０２６０】
ノード１６１でのパケットは、初期パケットであるか否かを示すビット及び系統ＣＨを有し、前者でノード１６１でのパケット分岐先が定まる。デマルチプレクサ１６２では、系統ＣＨが行先アドレスとして用いられ、これはその出力ノードで不要となる。【０２６１】
次に、ストリームバッファ１３０Ａのそれぞれのキューが順序を維持しているので、このＣＰＵアクセラレータ６０ＱＡでは、上述の順序合流制御が行われる分流路１２１Ａ及び合流路１２３Ａを備えた状態テーブルメモリ１２０Ａを用いて、状態テーブルメモリ１２０Ａでのパケット順序を維持させることにより、状態テーブルメモリ１２０Ａとストリームバッファ１３０Ａとの間で順序同期をとっている。【０２６２】
状態テーブルメモリ１２０Ａから出力されるパケットの順序が維持されるので、マルチプレクサ１３３０〜１３３３に対する選択制御を確実に予測することができる。この順序は、ＣＰＵ１２７がインターフェイス１２４、１２８、ノード１６１及びデマルチプレクサ１６２を介しノード１５０〜１５３へ供給する初期パケットの順序により定まる。すなわち、順序はＣＰＵ１２７が決定することになる。【０２６３】
ストリームＩＤ予測回路１６３は、系統ＣＨ毎に不図示のリングキューを備えており、系統ＣＨ毎に、ノード１６１からのパケット内のストリーム識別子ＳＩＤを順次このリングキューに保持し、その出力に基づき、マルチプレクサ１３３０〜１３３３へそれぞれストリーム識別子ＳＩＤ０〜ＳＩＤ３を供給するとともに該リングキュー内のパケットを１段進ませ、キュー１７０〜１７３の先頭からのＡＣＫがアクティブになる毎にこれを繰り返すことにより、予めキュー１７０〜１７３へストリームエレメントＳＥを複数取り込ませ保持させる。【０２６４】
合成ノード１４０〜１４３は、ノード１５０〜１５３へのＡＣＫをアクティブにするとき、同時に、対応するキュー１７０〜１７３の出力段へのＡＣＫをアクティブにする。【０２６５】
このようにして、パケットが状態テーブルメモリ１２０Ａからノード１５０〜１５３を介しそれぞれ合成ノード１４０〜１４３へ到達したときに、キュー１７０〜１７３からのパケットをこれと同時に合成ノード１４０〜１４３へ到達させることが可能となり、合成ノード１４０〜１４３での待ち合わせのタイムラグがなくなるので、上記実施例１２よりも高速処理を行うことができる。【０２６６】
なお、順序同期により合成ノード１４０〜１４３では、合成されるそれぞれのパケットのストリームＩＤが一致するので、状態テーブルメモリ１２０を含むループ内では、ストリームＩＤをパケットに含ませなくてもよい。【０２６７】
この場合、出力回路１６０でウイルスを検出した際にストリーム識別子ＳＩＤを出力する必要があるので、ＳＩＤ予測回路１６３と同様に系統ＣＨ毎にリングキューを出力回路１６０に備えてこれにストリームＩＤを保持させ、合流路１２３Ａの出口ノードからのＳＥＮＤパルスで、対応するリングキュー内の所定段に対するＡＣＫをアクティブにして該所定段でパケットを１個進ませ、合流路１２３Ａの出口ノードから出力されているパケットのストリームＩＤを識別する。【０２６８】
また、ＳＩＤ予測回路１６３でのリングキューと、マルチプレクサ１３３０から合流路１２３Ａの出口ノードまでのパイプライン段数と、出口ノードからのＳＥＮＤパルスの数とから、該出口ノードから出力されているパケットのストリームＩＤを識別することもできる。【０２６９】
さらに、ＣＰＵアクセラレータ以外の有限オートマトン装置として用いてもよい。【０２７０】
また、本発明の特徴の１つが予測回路を用いている点であることに着目すれば、本発明は、状態テーブルメモリ１２０Ａを含むループを、他の機能のループに置換した構成であってもよい。【０２７１】
なお、本発明には外にも種々の変形例が含まれる。【０２７２】
例えば、上記各実施例又はその変形例の構成要素の組み合わせを変えた構成も、その機能を達成できるものは本発明に含まれる。【０２７３】
また、分流路の行先アドレスをプロセッサの命令コードとし、分流路の出力側でこの命令コードに応じた処理手段を配置した構成であってもよい。この場合、レジスタファイル３０Ｒの各行をその命令コードに応じたレジスタ群として用いるこのができる。【０２７４】
さらに、ストリームバッファ１３０又は１３０Ａは、その中でのデータ流を逆流させて、他のループコンポーネントでの処理結果を分類してＣＰＵ等へ出力するのに用いることができる。【０２７５】
以上の説明から明らかなように、本発明には特許請求の範囲に記載したもの以外に、以下のような構成も含まれる。【０２７６】
［項目１−１］
分流路と、該分流路の下流側に配設され各ノードに処理要素及び合流段識別子を有する複数段の合流路と、該分流路の入口ノード又は該分流路の上流側に配設された合流段識別子生成ノードとを備え、
該合流段識別子生成ノードは、該分流路上の第１パケットペアのそれぞれの行先アドレスに基づいて合流段識別子を決定しこれを該第１パケットペアのそれぞれ又は該第１パケットペアを１パケットに圧縮した圧縮パケットに付加し、
該合流路の各ノードは、その合流段識別子が、該第１パケットペアに対応した第２パケットペアのそれぞれの合流段識別子と対応するとき、その処理要素が該第２パケットペアに対し処理を実行する、
ことを特徴とするデータ駆動型処理装置。【０２７７】
この構成によれば、パケットペアの待ち合わせの構成が簡単である。また、合流段での待ち合わせ時間を短縮できる。さらに、該合流段の下流側に流れるパケット数を低減して混雑を避け、これによりスループットを向上させることができる。【０２７８】
［項目１−２］
該第１パケットペアのそれぞれの行先アドレスは、該第１パケットペアのそれぞれに含まれていることを特徴とする項目１−１に記載のデータ駆動型処理装置。【０２７９】
この構成によれば、圧縮パケットを用いた場合の伸張処理が不要になる。【０２８０】
［項目１−３］
該第１パケットペアのそれぞれの行先アドレスは、該圧縮パケットに含まれており、該分流路は、該圧縮パケットを該第１パケットペアのそれぞれに伸張するノードを有することを特徴とする項目１−１に記載のデータ駆動型処理装置。【０２８１】
この構成によれば、パケット数を低減して混雑を避けることができ、また、該第１パケットペアのそれぞれの間にパケットが割り込むのを防止でき、さらに、１パケットに基づいて合流段識別子を決定できるのでその構成が簡単になる。【０２８２】
［項目１−４］
該分流路の各出口ノードと該合流路のこれに対応する入口ノードとの間に結合された機能エレメントをさらに有し、該機能エレメントは、該出口ノードのパケットに対応したパケットを該入口ノードへ供給することを特徴とする項目１−１に記載のデータ駆動型処理装置。【０２８３】
この構成によれば、より高度の処理を行うことができる。【０２８４】
［項目２−１］
パイプライン段数が３以上の分流路を備え、共通データと、第１行先アドレスと、第２行先アドレスと、パケット側分岐段識別子とを含む圧縮パケットが該分流路に供給されるデータ駆動型処理装置であって、
該分流路の各ノードにノード側分岐段識別子及びパケット伸張部が備えられ、
該パケット伸張部は、そのノード側分岐段識別子が圧縮パケットのパケット側分岐段識別子と対応するとき、該圧縮パケットを、その共通データとその第１行先アドレスとを含む第１パケットと、該共通データとその第２行先アドレスとを含む第２パケットとに伸張させて下流側へ供給する、
ことを特徴とするデータ駆動型処理装置。【０２８５】
この構成によれば、流路幅が比較的狭い分流路入口側では圧縮パケットが流れてパケットの混雑度が緩和され、これによりスループットが向上する。また、分流路入口側でパケットが混雑することによりパケットペアのそれぞれの間へ他のパケットが割り込むのを低減でき、これによって処理が容易となるのでスループットが向上する。【０２８６】
［項目２−２］
該分流路の上流側に配設された分岐段識別子生成ノードをさらに備え、
該分岐段識別子生成ノードは、圧縮パケットに含まれる第１行先アドレスと第２行先アドレスとに基づいて、該圧縮パケットを伸張すべき該分流路上の分岐段の識別子を決定しこれを該圧縮パケットに付加する、
ことを特徴とする項目２−１に記載のデータ駆動型処理装置。【０２８７】
この構成によれば、分流路上の各ノードに分岐段識別子生成機能を備える必要が無く、構成が簡単になる。【０２８８】
［項目２−３］
互いに相補的な行先アドレスを有するパケットの経路が、流路方向の軸に関し互いに、論理的に対称になるように、該分流路が形成されていることを特徴とする項目２−１又は２−２に記載のデータ駆動型処理装置。【０２８９】
この構成によれば、分流路の対称性により、分岐段識別子の決定論理が簡単になる。【０２９０】
［項目２−４］
該分岐段識別子生成ノードは、該第１行先アドレスと該第２行先アドレスとのヘッド側又はテイル側からの一致ビット数に基づいて該分岐段識別子を決定することを特徴とする項目２−３に記載のデータ駆動型処理装置。【０２９１】
この構成によれば、第１行先アドレスと第２行先アドレスとの一致ビット数に基づいて分岐段識別子を容易に決定することができる。【０２９２】
［項目３−１］
（１）連接有りを示す連接ビット、行先アドレス及びコマンドを含む先頭パケットが、パイプライン段数３以上の合流路上の合流ノードを通る毎に、そのノードが持つフリップフロップを第２状態から第１状態にさせ、
（２）該先頭パケットに後続する、連接有りを示す連接ビット及びデータを含む（ｎ−１）個（ｎ≧１）のデータパケットを順次、該第１状態のフリップフロップを持つ合流ノードを通って転送させ、
（３）該（ｎ−１）個のデータパケットに後続する、連接無しを示す連接ビット及びデータを含む末尾データパケットを、該第１状態のフリップフロップを持つ合流ノードを通って転送させながら該第１状態のフリップフロップを第２状態にさせる、
ことを特徴とするデータ駆動型処理方法。【０２９３】
この構成によれば、データパケットに行先アドレスが不要となり、パケットのデータ幅を短縮して回路規模を縮小することができる。【０２９４】
［項目３−２］
該合流路の１つの入口ノードに、該工程（１）〜（３）においてそれぞれ先頭パケット、（ｎ−１）個のデータパケット及び末尾データパケットを順次供給させることを特徴とする項目３−１に記載のデータ駆動型処理方法
この構成によれば、合流路の上流側にデータ記憶部を配設することができる。【０２９５】
［項目３−３］
ｎ＝ｎ１とし、該合流路の第１入口ノードに、該工程（１）〜（３）においてそれぞれ先頭パケット、（ｎ１−１）個のデータパケット及び末尾データパケットを順次供給させ、
ｎ＝ｎ２とし、該合流路の第２入口ノードに、該工程（１）〜（３）においてそれぞれ先頭パケット、（ｎ２−１）個のデータパケット及び末尾データパケットを順次供給させ、
該第１及び第２入口ノードのそれぞれからのパケット経路が合流するノードにおいて、該第１入口ノードからの（ｎ１＋１）個のパケット群と該第２入口ノードからの（ｎ２＋１）個のパケット群とに対し処理を行い、その結果のパケットを生成する、
ことを特徴とする項目３−１に記載のデータ駆動型処理方法。【０２９６】
この構成によれば、世代のような特別なＩＤを用いることなく両者を合流ノードで待ち合わせて処理することが可能になり、しかも、処理結果のパケット数が処理前よりも少なければ、合流路上の流路幅が比較的狭い出口側でのパケットのトラフィック量を低減して混雑を避けることができ、スループットを向上させることができる。【０２９７】
［項目３−４］
該合流路上の、次段及び後段を有する任意の合流ノードにおいて、
第１状態のフリップフロップを持つ後段ノードからのパケットを優先的に選択してラッチさせ
次段の合流ノードが持つフリップフロップが第２状態であり、本合流ノードがラッチしたパケットの連接ビットが後続有り場合、本合流ノードのフリップフロップを第１状態にさせ、
本合流ノードがラッチしたパケットの連接ビットが後続無しの値であれば、該第１状態のフリップフロップを持つ後段ノードの該フリップフロップを第２状態にさせ、
本合流ノードの処理要素で処理を行うことになっていてパケットの連接ビットが後続無しの値であれば本合流ノードのフリップフロップを第２状態にさせる、
ことにより工程（１）〜（３）を実施することを特徴とする項目２又は３に記載のデータ駆動型処理方法。【０２９８】
この構成によれば、末尾データパケットが第１状態のフリップフロップを目印に進んだ後に該フリップフロップを第２状態に戻すことができる。また、他方の連続パケットを一方の連続パケットに混入させることなく、該他方の連続パケット同様にして処理要素へ順次転送させることができる。【０２９９】
［項目４−１］
記憶行アレイと、
入口ノードに供給される第１パケットを、該第１パケットが含む行先アドレスに応じ下流側のノードへ順次選択的に分流させて、該記憶行アレイ内の１つの記憶行へ転送させるツリー形分流路と、
該記憶行で生成された第２パケットを、下流側へ順次選択的に合流させて出口ノードへ転送させるツリー形合流路と、
を有し、該記憶行は、
該第１パケットが含むコマンドがリードを示している場合、該第１パケットが含む記憶行内アドレスで指定される該記憶行内の一部の記憶データを読み出して該第１パケットに対応した該第２パケットを生成し、
該第１パケットのコマンドがライトを示している場合、該第１パケットが含む記憶行内アドレスで指定される該記憶行内の一部に、該第１パケットが含むデータを書き込み、
該ツリー形分流路及び該ツリー形合流路のパイプライン段数がそれぞれ３以上であることを特徴とするデータ駆動型半導体記憶装置。【０３００】
この構成によれば、ツリー形分流路により多数の記憶行に対しパケットを選択的に転送できるとともに、流路幅が比較的広い分流路出口側及び合流路入口側でパケットの混雑が避けられるので、記憶行での処理の遅延が複数の記憶行での分散並列処理により吸収され、ランダムアクセスのスループットが比較的高い。【０３０１】
［項目４−２］
該記憶行アレイは、複数の記憶行ペアを備え、各記憶行ペアは、
該ツリー形分流路の１つの出口ノードと、この出口ノードに対応した、該ツリー形合流路の１つの入口ノードとの間に結合され、
第１及び第２の記憶行と、制御回路とを有し、該制御回路は、該分流路の出口ノードに保持された第１パケットが含む行先アドレスの所定ビットの値に応じて該第１及び第２記憶行の一方をリード又はライトの制御対象とする、
ことを特徴とする項目４−１に記載のデータ駆動型半導体記憶装置。【０３０２】
この構成によれば、各記憶行ペアに対し１つの制御回路を共用することができる。【０３０３】
［項目４−３］
該制御回路は、該分流路の出口ノードに保持された第１パケットが含むコマンドがリードを示している場合、該分流路出口ノードの転送制御回路に対するＡＣＫ信号をインアクティブに維持した状態で、リード制御対象の記憶行からデータを読み出させ、該第１パケットの一部とともに該合流路入口ノードに転送させることを特徴とする項目４−２に記載のデータ駆動型半導体記憶装置。【０３０４】
この構成によれば、記憶行にはデータのみを格納すればよく、また、１つのリードパケットで複数のデータパケットを読み出すことができる。【０３０５】
［項目４−４］
該制御回路は、該分流路の出口ノードに保持された第１パケットが含むコマンドがライトを示している場合、該合流路入口ノードの転送制御回路に対するＳＥＮＤ信号をインアクティブに維持した状態で、ライト制御対象の記憶行の一部に、該第１パケットが含むデータを書き込ませることを特徴とする項目４−２に記載のデータ駆動型半導体記憶装置。【０３０６】
この構成によれば、１つの記憶行又はランダムな記憶行に対し複数パケットで連続して書き込みを行うことができる。【０３０７】
［項目５−１］
パケットの内容に応じてパイプライン処理を行うループに備えられたノードに、そのパケットが含む識別子に応じてデータを供給するデータ駆動型データバッファ装置であって、
それぞれの識別子に対応したキューに、データが順次格納されるキュー列と、
該ノードからのパケットに含まれる識別子に基づき、該キュー列のキューを選択して、このキューの出力段を該ノードに結合させるマルチプレクサと、
を有することを特徴とするデータ駆動型データバッファ装置。【０３０８】
この構成によれば、並列処理対象に応じ高速にキューを切り替えてデータを取り出し該ノードに供給することができる。【０３０９】
［項目５−２］
該キュー列の各キューについて、空きが所定量を超えた場合には該キューに対応した識別子とともに割込要求信号を出力する空検出回路をさらに有することを特徴とする項目６−１に記載のデータ駆動型データバッファ装置。【０３１０】
この構成によれば、該ノードへのデータ供給を途切れなく行うことができるとともにＣＰＵへの負担を軽減できる。【０３１１】
［項目５−３］
該マルチプレクサは、その入力が複数の入口ノードの入力であり、その出力が出口ノードの出力であるツリー形合流路を有することを特徴とする項目５−２に記載のデータ駆動型データバッファ装置。【０３１２】
この構成によれば、パイプライン処理が行われてスループットが向上する。【０３１３】
［項目６−１］
上位ビット及び下位ビットをそれぞれ状態及びデータストリーム要素とするアドレスに次状態が格納され、アドレスとデータストリーム識別子とを含むパケットが入力され、次状態と該データストリーム識別子とを含むパケットが出力されるデータ駆動型状態テーブルメモリと、
該状態テーブルメモリの出力を該状態テーブルメモリの入力にフィードバックさせる流路に介在され、データ入力端の第１部に供給されるデータを該データ入力端の第２部に供給される該次状態と合成する合成ノードと、
それぞれのキューにデータストリームが格納されるキュー列と、
該出力に含まれるデータストリーム識別子に基づき、該キュー列のキューを選択して、このキューの出力段を該第１部に結合させるマルチプレクサと、
を有することを特徴とする有限オートマトン装置。【０３１４】
この構成によれば、データ駆動型状態テーブルメモリと合成ノードとキュー列とマルチプレクサとの組み合わせにより、スループットを向上させると共に低消費電力化を図ることができる。【０３１５】
［項目６−２］
該フィードバック流路の、該状態テーブルメモリと該合成ノードとの間に、初期パケットと該次状態のパケットとを選択的に合流させる合流ノードをさらに有することを特徴とする項目６−１に記載の有限オートマトン装置。【０３１６】
この構成によれば、処理開始を容易に行うことができる。【０３１７】
［項目６−３］
該状態テーブルメモリには、パターン一致情報が含まれ、
該状態テーブルメモリの出力に含まれるパターン一致情報がパターン一致を示しているか否かを判定し、肯定判定した場合には該出力に含まれるデータストリーム識別子とともに割込要求信号を出力する出力回路をさらに有することを特徴とする項目６−２に記載の有限オートマトン装置。【０３１８】
この構成によれば、処理結果を高速に得ることができる。【０３１９】
［項目６−４］
該キュー列の各キューについて、空きが所定量を超えた場合には該キューに対応したデータストリーム識別子とともに割込要求信号を出力する空検出回路をさらに有することを特徴とする項目６−３に記載の有限オートマトン装置。【０３２０】
この構成によれば、多数のデータストリームを並列処理しても、キューに対しデータストリームを必要時に補給することができる。【０３２１】
［項目７−１］
パケット順序を維持してパケットの内容に応じた処理を行う第１ループと、
パケット順序を維持してパケットの内容に応じた処理を行う第２ループと、
該第１ループと該第２ループとを結合させてこれらの一方のループでのパケットに含まれる情報を他方のループに与える結合手段と、
を有することを特徴とする、順序同期を行うデータ駆動型処理装置。【０３２２】
この構成によれば、従来１つであったループを２つのループに分割することが可能となるので、パイプライン段数を低減してレイテンシを短縮するとともにスループットを向上させることができ、また、パケットのデータ幅を短縮して回路規模を縮小することができ、さらに、コンポーネント化が可能となるので、システムの構築が容易となる。【０３２３】
［項目７−２］
該結合手段は、該第１ループ内のパケットと該第２ループ内のパケットとを対応させてそれぞれのループ内で転送させる結合ノードであることを特徴とする項目７−１に記載の、順序同期を行うデータ駆動型処理装置。【０３２４】
この構成によれば、第１ループと第２ループとで結合ノードにおいて同期をとることができる。【０３２５】
［項目７−３］
該第２ループはリングキューであることを特徴とする項目７−２に記載の、順序同期を行うデータ駆動型処理装置。【０３２６】
この構成によれば、第２ループを第１ループのデータバッファとして用いることができる。【０３２７】
［項目７−４］
該第１ループに第１パケットが投入され、該第２ループに該第１パケットと関係した第２パケットが投入され、
該結合ノードは、該第１ループでのパケットに含まれるコマンド又は特定ビットが該結合ノードからの出力を示している場合、これに対応して該第２ループからパケットを取り出すことにより、該第１ループでの第１パケットに対応した処理結果のパケットとともに該第２パケットを取り出すことを特徴とする項目７−３に記載の、順序同期を行うデータ駆動型処理装置。【０３２８】
この構成によれば、第１ループで常に第２パケットを引き連れて行く必要がない。【０３２９】
［項目７−５］
該結合ノードは、該第１ループのパケットが個数ｎの情報を含むとき、このパケットを１個転送させるとともに該第２ループのパケットをｎ個転送させることにより、該第１ループの１パケットを該第２ループのｎパケットと対応させることを特徴とする項目７−３に記載の、順序同期を行うデータ駆動型処理装置。【０３３０】
この構成によれば、第１ループが第２ループを中間結果保存用スタックとして利用できる。【０３３１】
［項目７−６］
該第１ループ上又は該第２ループ上のパケットは、順序有無を示す順序情報を含み、
該結合ノードは、一方のループ上のパケットが含む順序情報が順序無しを示している場合、このパケットを転送させる際に、他方のループ上のパケットを転送させないことを特徴とする項目７−２に記載の、順序同期を行うデータ駆動型処理装置。【０３３２】
この構成によれば、順序を維持する必要がないパケット、例えばメモリへのライトパケットのように途中で消滅するパケットがループに含まれていても、本発明を適用できる。【０３３３】
［項目７−７］
該結合手段は、該第１ループと該第２ループとの一方のループ上のパケットを受け取る入力段と他方のループ上へパケットを供給する出力段とを備えたキューであることを特徴とする項目７−１に記載の、順序同期を行うデータ駆動型処理装置。【０３３４】
この構成によれば、ループ間での待ち時間を省略できるので、スループットを向上させることができる。
【図面の簡単な説明】
【０３３５】
【図１】本発明の実施例１の非同期（自己タイミング）データ駆動型メモリを示す概略ブロック図である。
【図２】メモリ行アレイの配列の具体例を示す図である。
【図３】束データ方式で分流路を構成した場合の第１段と第２段とで構成される分流回路を示す概略ブロック図である。
【図４】束データ方式で合流路を構成した場合の第２段と第３段の一部である合流回路を示す概略ブロック図である。
【図５】図１の分流路２０の出力ノード２６１と合流路４０の入口ノード４１１との間に接続されたメモリ行３１及び３２を示す概略ブロック図である。
【図６】本発明の実施例２のデータ駆動型メモリを示す概略ブロック図である。
【図７】（Ａ）はパケットのフォーマットを示し、（Ｂ）は系統とパケットフローの関係を示す説明図である。
【図８】入力ポート及び出力ポートの数を実施例２の場合の２倍にした、本発明の実施例３のメモリを示す概略ブロック図である。
【図９】パケットのフォーマットを示す図である。
【図１０】パイプライン段数を低減した、本発明の実施例４のメモリを示す概略ブロック図である。
【図１１】選択的合流ノードへの転送待ちを短縮した、本発明の実施例５の２ポート入力・２ポート出力型のメモリを示す概略ブロック図である。
【図１２】入力ポート及び出力ポートの数を実施例５の場合の２倍にした、本発明の実施例６のメモリを示す概略ブロック図である。
【図１３】本発明の実施例７の、プロセッサの一部であるデータ処理部を示す概略ブロック図である。
【図１４】（Ａ）及び（Ｂ）は、パケットペアを分流路入口ノードに投入した後の処理の流れを示す概略説明図である。
【図１５】本発明の実施例８の、プロセッサの一部であるデータ処理部を示す概略ブロック図である。
【図１６】（Ａ）はパケットペア行先アドレスに基づいて合流段ＩＤを決定する方法の説明図、（Ｂ）はパケットフォーマットを示す説明図である。
【図１７】合流段識別ノードの概略構成を示すブロック図である。
【図１８】（Ａ）〜（Ｄ）は本発明の実施例９に係るパケットフォーマット説明図であり、（Ａ）はパケットペアを１パケットに圧縮したもののフォーマット、（Ｂ）及び（Ｃ）はこのパケットを２パケットに伸張させたもののフォーマット、（Ｃ）は連接パケットでの先頭に続くデータパケットを示す図である。
【図１９】（Ａ）及び（Ｂ）はそれぞれ第１オペランドの連接パケットの先頭パケット及びこれに続くデータパケットを示す説明図、（Ｂ）及び（Ｃ）はそれぞれ第２オペランドの連接パケットの先頭パケット及びこれに続くデータパケットを示す説明図である。
【図２０】合流路のノードに備えられた連接ビットがパケットペアの連接ビットによりセットされている状態を示す説明図である。
【図２１】ノードＮ１のノード側連接ビットＦ１に対する状態制御回路とこれに関連する要素を示すブロック図である。
【図２２】（Ａ）〜（Ｃ）は本発明の実施例１０に係り、（Ａ）はデータ駆動型処理ループを示し、（Ｂ）は（Ａ）を２分割して並列結合した回路を示し、（Ｃ）は複雑な処理ループを並列結合した回路を示す概略図である。
【図２３】（Ａ）及び（Ｂ）はそれぞれ同層及び異層間において、順序同期が成立している並列処理ループ間でのキューを介した処理結果の伝達を示す図である。
【図２４】本発明の実施例１１に係る、合流路のノードとこれに対応する分流路のノードとの間で生ずる切替順序の乱れの説明図である。
【図２５】（Ａ）は合流路の任意のノードについて、これに対応する分流路のノードとの間で切替同期を行う構成を示し、（Ｂ）及び（Ｃ）はこの構成の動作を示す図である。
【図２６】図２５の（Ａ）の詳細ブロック図である。
【図２７】（Ａ）〜（Ｊ）は、分流路側の１つのリードパケットの流れと、これに対応した合流路側の複数のリードデータパケット（連接パケット）との流れとを、時間を追って示す説明図である。
【図２８】行を状態Ｓとし、入力である列を、データストリームを構成する１バイトのストリームエレメントＳＥとした出力コマンド付状態遷移テーブルを示す図である。
【図２９】本発明の実施例１２のＣＰＵアクセラレータを示す概略ブロック図である。
【図３０】図２９中のストリームバッファの概略ブロック図である。
【図３１】図２９の装置における１系統に関するデータフローをデータフォーマットとともに示す図である。
【図３２】本発明の実施例１３の順序同期型ＣＰＵアクセラレータを示す概略ブロック図である。
【図３３】簡単な有限オートマトンの例を示す状態遷移図である。
【符号の簡単な説明】
【０３３６】
１０、１０Ａ〜１０Ｅ、１２０、１２０Ａ  メモリ
１０ＡＰ、１０ＢＰ  データ処理部
２０、２０Ａ〜２０Ｅ、７１、１２１、１３１、１３１Ａ  分流路
２０１Ｃ、２１１Ｃ、２２１Ｃ、２２２Ｃ、２６１Ｃ、４１１Ｃ、３１１Ｃ、３１２Ｃ、３１３１Ｃ、４１１Ｃ、４２１Ｃ、４２２Ｃ、４３１Ｃ、７１１Ｃ、７３１Ｃ  転送制御回路
２０１Ｌ、２１１Ｌ、２２１Ｌ、２２２Ｌ、２６１Ｌ、３１１Ｌ、３１２Ｌ、３１３１Ｌ、４１１Ｌ、４２１Ｌ、４２２Ｌ、４３１Ｌ、７１１Ｌ、７３１Ｌ  ラッチ
１１０、１１１、１１５〜１１８、２０１〜２０４、２２１〜２２８、２２１Ａ、２２２Ａ、２２３Ａ、２２４Ａ、２３１〜２３４、２３１Ａ、２３２Ａ、２４１、２４８、２５１、２６１、４１１、４１１Ａ、４１１Ｂ、４２１、４３１、４４１〜４４４、４４１Ａ、４５１〜４５４、４４１Ａ、４４２Ａ、４４３Ａ、４４４Ａ、４５１Ａ、４５２Ａ、４５３Ａ、４５４Ａ、４６１Ａ、４６１ＡＰ、４６２Ａ、４６３Ａ、４６４Ａ、４７、７１１、７３１、７７、７７１〜７７４、８２、Ｎ０１、Ｎ０２、Ｎ１、Ｎ２  ノード
２０１Ｆ  合流段ＩＤ決定部
２０１Ｐ  パケットペア判定部
２１１〜２１４、４１１  入口ノード
２２２Ｇ、２６１Ｇ１、４１１Ｇ、４２２Ｇ  インバータ
２５１、４６１〜４６４  出口ノード
２６１Ｇ２、３１３１Ｇ  オアゲート
３０、１２２  メモリ行アレイ
３０Ｒ  レジスタファイル
３１０、７４０  ループ配線
３１、３２  メモリ行
３１１、７４１  制御回路
３１１ａ、３１０Ｃ  カウンタ
３１０Ｗ、３１１Ｗ、３１２Ｗ、３１３Ｗ、３２０Ｗ  ワードメモリ
４０、４０Ａ〜４０Ｅ、４０ＡＰ、４０ＢＰ、７３、１２３、１２３Ａ  合流路
４７  状態制御回路
５０、５０Ａ〜５０Ｇ、Ｐ１〜Ｐ３、Ｐ１Ａ、Ｐ２Ａ、Ｐ１Ｎ、Ｐ２Ｎ  パケット
６０、６０Ａ  キャッシュメモリ
６０Ｑ、６０ＱＡ  ＣＰＵアクセラレータ
７０、７０Ａ  タグテーブル
７２  タグアレイ
７２１、７２２  タグ行
７５０〜７５３、７５ｉ  ページ情報
７６０〜７６３  コンパレータ
７６４  オアゲート
７６５  エンコーダ
７６６  マルチプレクサ
８０、８０１〜８０４  入出力部
８１、１２４、１２８、１２８Ａ  インターフェイス
１００、１０１、１０１Ａ、１０１Ｂ、１０２、１０２Ａ、１０２Ｂ  ループ
１０３、１０３Ａ  結合ノード
１０４、１０５、１１３、１７０〜１７３  キュー
１２５  メモリコントローラ
１２６  ＲＡＭ
１２７  ＣＰＵ
１３０、１３０Ａ  ストリームバッファ
１３２  キューアレイ
１３３０〜１３３３  マルチプレクサ
１３４  半空検出回路
１４０〜１４３、１５０〜１５３  ノード
１６０  出力回路
１６３  ストリームＩＤ予測回路
１６２  デマルチプレクサ
ＣＫ  クロック入力端
ＣＫ１、ＣＫ２  クロックパルス
ＯＥ  出力イネーブル制御入力端
ＣＭＤ  コマンド
ＡＤＲ、ＡＤＲ１、ＡＤＲ２  アドレス
ＤＡ、ＤＡ１、ＤＡ２、ＤＡｉ  行先アドレス
ＤＡ０〜ＤＡ５、ＣＨ０、ＣＨ１  ビット
ＰＡ、ＰＡ１、ＰＡ２  ページアドレス
ＷＡ、ＷＸ、ＷＡ１、ＷＡ２  ワードアドレス
ＤＡＴＡ  データ
ＣＮ  連接ビット
ＯＤ  順序ビット
ＨＭ、ＨＭ１、ＨＭ２  ヒットビット
ＣＨ  系統
ＰＴ  パケットタイプ
ＴＡ、ＴＡＧ  タグアドレス
ＣＮＴ  カウンタ
ＭＡ  合流段識別子
ＰＲ１、ＰＲ２  処理
Ｖ  バリッドビット
Ｄ  ダーティビット
Ｌ  ロックビット
Ｒ  結果ビット
ＶＣ  ウイルスコード
Ｓ  状態
ＳＥ  ストリームエレメント
ＳＩＤ、ＳＩＤ０〜ＳＩＤ３  ストリーム識別子
ＩＲＱ１、ＩＲＱ２  割込要求
ＤＳ  入力データストリーム
ＲＤ  検索データ集合
Ｆ０１、Ｆ０２、Ｆ１、Ｆ２  フリップフロップ
【図１】
2008123406.tif 000003
【図２】
2008123406.tif 000004
【図３】
2008123406.tif 000005
【図４】
2008123406.tif 000006
【図５】
2008123406.tif 000007
【図６】
2008123406.tif 000008
【図７】
2008123406.tif 000009
【図８】
2008123406.tif 000010
【図９】
2008123406.tif 000011
【図１０】
2008123406.tif 000012
【図１１】
2008123406.tif 000013
【図１２】
2008123406.tif 000014
【図１３】
2008123406.tif 000015
【図１４】
2008123406.tif 000016
【図１５】
2008123406.tif 000017
【図１６】
2008123406.tif 000018
【図１７】
2008123406.tif 000019
【図１８】
2008123406.tif 000020
【図１９】
2008123406.tif 000021
【図２０】
2008123406.tif 000022
【図２１】
2008123406.tif 000023
【図２２】
2008123406.tif 000024
【図２３】
2008123406.tif 000025
【図２４】
2008123406.tif 000026
【図２５】
2008123406.tif 000027
【図２６】
2008123406.tif 000028
【図２７】
2008123406.tif 000029
【図２８】
2008123406.tif 000030
【図２９】
2008123406.tif 000031
【図３０】
2008123406.tif 000032
【図３１】
2008123406.tif 000033
【図３２】
2008123406.tif 000034
【図３３】
2008123406.tif 000035
【国際調査報告】
2008123406.tif 000036
2008123406.tif 000037