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