説明

有限オートマトン装置及びパターンマッチング方法

【課題】スループットを向上させると共に低消費電力化を図る。
【解決手段】データ駆動型状態テーブルメモリ120には、上位及び下位をそれぞれ状態及びデータストリーム要素とするアドレスに次状態が格納され、アドレスとデータストリーム識別子とを含むパケットが入力され、次状態とデータストリームIDとを含むパケットが出力される。合成ノード140〜143は、メモリ120の出力を入力にフィードバックさせる流路に介在され、この出力とマルチプレクサ1330〜1333の出力とを合成する。データストリームは、キュー列132の各キューに格納される。マルチプレクサ1330〜1333は、該出力に含まれるデータストリームIDに基づき、キュー列132のキューを選択して、このキューの出力段を合成ノード140〜143に結合させる。初期パケットと次状態のパケットとは、状態テーブルメモリ120と合成ノード140〜143との間の合流ノード150〜153に選択的に合流する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、データ駆動型半導体装置に用いられ、有限オートマトン装置及びパターンマッチング方法に係り、特に、データ駆動型状態テーブルメモリ及びデータストリームキュー列を備えCPUアクセラレータとして用いて好適な有限オートマトン装置及びパターンマッチング方法に関する。
【背景技術】
【0002】
インターネットの普及に伴い、スパムメールやファイルへのウイルス感染による被害が増大しており、メールサーバーでは大量のメール及びメール添付ファイルに対しメールフィルタリング及びウイルスチェックを高速に行う必要がある。
【0003】
ウィルススキャンは、シグネチャーと呼ばれる可変長パターンの検索処理であり、平均100〜150バイトのシグネチャーが約10万種類存在すると言われている。
【0004】
この検索でのパターンマッチングは、有限オートマトンを用いて行うことができる。有限オートマトンでは、現状態と入力とで次状態が定まり、これが繰り返し行われてパターンが検出される。ウィルススキャンの場合、入力はデータストリームのエレメント、例えば1バイトであり、データストリームに、多数のシグネチャーのどれが含まれているかのパターンマッチング処理を、1つの状態遷移テーブルで表すことができる(Aho−Corasick法)。
【0005】
この方法は、例えば下記特許文献1に開示されているように、メモリに状態遷移テーブルを格納しておき、現状態とデータストリームエレメントとをアドレスとしてメモリから次状態を読み出し、これに次のデータストリームエレメントを付加してアドレスとし次状態を読み出すという処理を繰り返すことにより、実施することができる。
【0006】
しかしながら、ランダムアクセスであるので、アクセス毎に遅延が生じ、また、並列処理が出来ず、充分なスループットが得られない。多数のメモリを並列に動作させることもできるが、高速処理を連続的に行う必要があるので、消費電力が大きくなる。
【0007】
有限オートマトン装置は、ウィルススキャンやメールフィルタリングだけでなく、XMLパースを行うこともでき、携帯電話などのモバイル機器に適用可能であり、このような用途では、処理の高速化のみならず低消費電力化が要求される。
【0008】
一方、データ駆動型半導体装置では、例えば下記特許文献2に開示されているように、ローカルな同期制御が複数の要素のそれぞれで自立分散的に行われるので、システムクロックに同期して各要素を集中制御する同期型半導体装置よりも、処理の並列度を容易に高くすることができるとともに、消費電力を低減できる。
【特許文献1】米国特許第7,082,044号公報
【特許文献2】特開平5−108852
【発明の開示】
【発明が解決しようとする課題】
【0009】
しかしながら、多並列パイプライン処理を行うデータ駆動型記憶装置が存在せず、また、このようなデータ駆動型記憶装置とマッチして多数のデータストリームを高速に記憶装置に供給することができないので、スループットを向上させると共に低消費電力化を図るということができない。
【0010】
本発明の目的は、このような問題点に鑑み、スループットを向上させると共に低消費電力化を図ることが可能な有限オートマトン装置及びパターンマッチング方法を提供することにある。
【課題を解決するための手段】
【0011】
本発明による有限オートマトン装置の第1態様では、
上位ビット及び下位ビットをそれぞれ状態及びデータストリーム要素とするアドレスに次状態が格納され、アドレスとデータストリーム識別子とを含むパケットが入力され、次状態と該データストリーム識別子とを含むパケットが出力されるデータ駆動型状態テーブルメモリと、
該状態テーブルメモリの出力を該状態テーブルメモリの入力にフィードバックさせる流路に介在され、データ入力端の第1部に供給されるデータを該データ入力端の第2部に供給される該次状態と合成する合成ノードと、
それぞれのキューにデータストリームが格納されるキュー列と、
該出力に含まれるデータストリーム識別子に基づき、該キュー列のキューを選択して、このキューの出力段を該第1部に結合させるマルチプレクサとを有する。
【0012】
本発明による有限オートマトン装置の第2態様では、第1態様において、
該フィードバック流路の、該状態テーブルメモリと該合成ノードとの間に、初期パケットと該次状態のパケットとを選択的に合流させる合流ノードをさらに有する。
【0013】
本発明による有限オートマトン装置の第3態様では、第2態様において、
該状態テーブルメモリには、パターン一致情報が含まれ、
該状態テーブルメモリの出力に含まれるパターン一致情報がパターン一致を示しているか否かを判定し、肯定判定した場合には該出力に含まれるデータストリーム識別子とともに割込要求信号を出力する出力回路をさらに有する。
【0014】
本発明の第4態様では、第3態様において、
該キュー列の各キューについて、空きが所定量を超えた場合には該キューに対応したデータストリーム識別子とともに割込要求信号を出力する空検出回路をさらに有する。
【0015】
本発明による有限オートマトン装置の第5態様では、第4態様において、
該マルチプレクサは、その入力が複数の入口ノードの入力であり、その出力が出口ノードの出力であるツリー形合流路を有する。
【0016】
本発明による有限オートマトン装置の第6態様では、第5態様において、
供給されるデータストリームを行先アドレスに基づき順次選択的に分流させて該キュー列の1つのキューに転送させるツリー形分流路をさらに有する。
【0017】
本発明による有限オートマトン装置の第7態様では、
上位ビット及び下位ビットをそれぞれ状態及びデータストリーム要素とするアドレスに次状態が格納され、アドレスを含むパケットが入力され、次状態を含むパケットが出力され、パケット順序が維持されるデータ駆動型状態テーブルメモリと、
該状態テーブルメモリの出力を該状態テーブルメモリの入力にフィードバックさせる流路に介在され、データ入力端の第1部に供給されるデータを該データ入力端の第2部に供給される該次状態と合成する合成ノードと、
該フィードバック流路の、該状態テーブルメモリと該合成ノードとの間に、初期パケットと該次状態のパケットとを選択的に合流させる合流ノードと、
それぞれの第1キューにデータストリームが格納されるキュー列と、
出力段を該第1部に結合させる第2キューと、
該合流ノードへの初期パケット投入順に基づき巡回する選択制御信号を順次生成する予測回路と、
該選択制御信号に応じ該キュー列の第1キューを選択して、この第1キューの出力段を該第2キューの入力段に結合させるマルチプレクサとを有する。
【発明の効果】
【0018】
上記第1態様の構成によれば、上述のようなデータ駆動型状態テーブルメモリと合成ノードとキュー列とマルチプレクサとの組み合わせにより、スループットを向上させると共に低消費電力化を図ることができるという効果を奏する。
【0019】
上記第2態様の構成によれば、初期パケット合流ノードを備えているので、処理開始を容易に行うことができるという効果を奏する。
【0020】
上記第3態様の構成によれば、状態テーブルメモリにパターン一致情報が含まれ、状態テーブルメモリの出力に含まれるパターン一致情報がパターン一致を示している場合には該出力に含まれるデータストリーム識別子とともに割込要求信号を出力するので、処理結果を高速に得ることができるという効果を奏する。
【0021】
上記第4態様の構成によれば、キュー列の各キューについて、空きが所定量を超えた場合には該キューに対応したデータストリーム識別子とともに割込要求信号を出力するので、多数のデータストリームを並列処理しても、キューに対しデータストリームを必要時に補給することができるという効果を奏する。
【0022】
上記第5態様の構成によれば、マルチプレクサがツリー形合流路を有するので、構成が簡単であるという効果を奏する。
【0023】
上記第6態様の構成によれば、ツリー形分流路を介してキュー列のキューにデータストリームを転送させるので、データ入力端の数を低減できるという効果を奏する。
【0024】
上記第7態様の構成によれば、データ駆動型状態テーブルメモリ自体での次状態検出並列処理とデータ駆動型状態テーブルメモリに対するストリームエレメント供給処理とを、待ち合わせることなく並列して行うことができるので、検索処理をより高速化することができるという効果を奏する。
【0025】
本発明の他の目的、構成及び効果は以下の説明から明らかになる。
【実施例1】
【0026】
図1は、非同期(自己タイミング)式のデータ駆動型メモリ10を示す概略ブロック図である。
【0027】
メモリ10では、分流路20の下流側に、機能エレメントアレイとしてのメモリ行アレイ30を介して合流路40が接続されている。
【0028】
図2(A)は、メモリ行アレイ30の配列の具体例を示す。
【0029】
メモリ行アレイ30の行及び列をそれぞれセット番号及びページ番号で識別する。説明の簡単化のため、メモリ行アレイ30が64行、1ページが8ワード、1ワードが32ビットであるとする。以下では、メモリ行アレイ30に対するリード及びライトがそれぞれ、ページ単位及びワード単位で行われる場合を説明する。
【0030】
図1に戻って、分流路20は、入口ノード211に供給されるパケットを、その行先アドレスに応じて順次選択的に分岐させるものであり、アドレスデコーダとして機能する。
【0031】
図2(B)は、分流路20でのパケットのフォーマットを示す。
【0032】
パケット50は、1ビットのコマンドフィールドと、11ビットのアドレスフィールドと、32ビットのデータフィールドとからなる。コマンドCMDは、'0'のときリード、'1'のときライトを示す。アドレスADRは、上位6ビットの行先アドレスDAと、中位2ビットのページアドレスPAと、下位3ビットのワードアドレスWAとに分けられる。
【0033】
行先アドレスDAは、分流路20の行先、すなわちメモリ行アレイ30の行(セット番号)を示す。ページアドレスPAは、パケット50が行先アドレスへ到達した後に、そのメモリ行におけるリード対象の識別に用いられる。ページアドレスPAとページ内ワードアドレスWAとの組は、パケット50が行先アドレスへ到達した後に、メモリ行におけるライト対象の識別に用いられる。データDATAは、ライトのデータであり、リードの場合にはダミーである。
【0034】
以下では、コマンドCMDがリードの場合の分流路20及び合流路40でのパケットをそれぞれリードパケット及びリードデータパケット、ライトの場合の分流路20でのパケットをライトデータパケットと称す。
【0035】
合流路40でのリードデータパケットは、パケット50からコマンドCMDの1ビットを除いた43ビットであり、アドレスADRは、合流路40の出口ノードに到達したパケット内のデータの識別に用いられる。
【0036】
図1に戻って、分流路20及び合流路40はいずれも6段パイプラインであり、各パイプラインステージにおけるノードは、ラッチと、転送制御回路とを備えている。
【0037】
図3は、束データ方式で分流路20を構成した場合の第1段と第2段とのノードで構成される分流回路を示す概略ブロック図である。
【0038】
第1段の入口ノード211は、ラッチ211Lと転送制御回路211Cとを備え、第2段のノード221は、ラッチ221Lと転送制御回路221Cとを備え、第2段のノード222は、ラッチ222Lと転送制御回路222Cとインバータ222Gとを備えている。転送制御回路211C、221C及び222Cはそれぞれ、ラッチ211L、221L及び222L内の入力段ゲート開閉をハンドシェイクプロトコルで行うものであり、段間が縦続接続されている。
【0039】
転送制御回路はいずれも、後段からのSEND−IN(転送要求入力)信号がアクティブ、すなわち後段からのデータが確定していて、前段からのACK−IN(転送許可入力)信号がアクティブ、すなわち前段がエンプティである場合に、ラッチのクロック入力端CKにパルスを供給して後段からのデータをラッチに取り込み保持し、特別な制限がなければ後段へのACK−OUT信号をアクティブにし、前段へデータが到達したと考えられる所定時間経過後に前段へのSEND−OUT信号をアクティブにする。
【0040】
各転送制御回路は、出力を有効/無効にするための制御入力端を備えており、転送制御回路221C及び222Cの該制御入力端にはそれぞれ、ラッチ211Lに保持されたパケットの行先アドレス(DA5〜DA0)DAの最上位ビットDA5及びこれをインバータ222Gで反転させたものが供給される。したがって、ビットDA5が'1'の場合、ラッチ221L及び222Lがそれぞれ有効及び無効になって、ラッチ211Lの内容がラッチ221Lに保持され、ビットDA5が'0'の場合、ラッチ221L及び222Lがそれぞれ無効及び有効になって、ラッチ211Lの内容がラッチ222Lに保持される。
【0041】
各転送制御回路はさらに、不図示のリセット入力端を有し、システムリセット時にこれにリセットパルスが供給されて、ACK−IN及びACK−OUTがアクティブ、SEND−IN及びSEND−OUTがインアクティブになる。
【0042】
転送制御回路は各種のものが公知であるので、その構成の説明を省略する。
【0043】
図1に戻って、例えばノード221に保持されたパケットは、行先アドレスDAの第2ビットに応じてノード231又はノード232に保持され、例えばノード232に保持されたパケットは、行先アドレスDAの第3ビットに応じてノード243又はノード244に保持される。以下同様にして、分流路20の行先アドレスDAの内容に応じ、第6段に配置された32個の出口ノードの1つにパケットが到達する。各出力ノードは2つの分岐出力を有する。
【0044】
各ノードにおいて、行先アドレスDAの対応するビットが'1'/'0'のとき図1においてそれぞれ上側/下側へデータが分岐するように定められているとする。例えば行先アドレスDAが'111111'の場合、このパケットは出力ノード261に到達する。ノード261において、行先アドレスDAの最下位ビットDA0が'1'であるとき、メモリ行アレイ30のメモリ行31が有効にされ、ビットDA0が'0'であるとき、メモリ行32が有効にされる。
【0045】
メモリ行アレイ30を構成する64個のメモリ行は、互いに同一構成である。各メモリ行は、その入力端及び出力端がそれぞれ分流路20及び合流路40の対応する出力端及入力端に結合されている。分流路20の出力端及び合流路40の入力端のそれぞれにラッチを接続することもできるが、段数を少なくしてターンアランドタイムを短縮するために、図1ではこれらのラッチが省略された構成となっている。
【0046】
図5は、図1の分流路20の出力ノード261と合流路40の入口ノード411との間に接続されたメモリ行31及び32を示す概略ブロック図である。
【0047】
メモリ行31及び32は、ノード261と入口ノード411との間に接続されている。ノード261は、ラッチ261Lと、この入力ゲートを開閉する転送制御回路261Cとからなり、入口ノード411は、ラッチ411Lと、この入力ゲートを開閉する転送制御回路411Cとからなる。
【0048】
メモリ行31及び32には、ループ状の32ビットのデータバスとアドレスADRの上位8ビットのアドレスバスからなるループ配線310が配設され、これがラッチ261Lのデータ出力端及びラッチ411Lのデータ入力端に接続されている。ループ配線310のデータバスには、メモリ行31の構成要素である32個のワードメモリ310W〜3131Wのそれぞれのデータ入力端及びデータ出力端が接続され、同様にメモリ行32の構成要素である32個のワードメモリ320W〜3231Wのそれぞれのデータ入力端及びデータ出力端が接続されている。
【0049】
これらワードメモリ310W〜3131W及び320W〜3231Wのそれぞれのクロック入力端CK及び出力イネーブル制御入力端OEを制御するために、転送制御回路261Cと転送制御回路411Cとの間に制御回路311が接続されている。
【0050】
制御回路311には、ラッチ261Lに保持されたコマンドCMD、ページアドレスPA、ワードアドレスWA及びにラッチ411Lのクロック入力端CKに供給されるクロックパルスCK1が供給される。制御回路311は、このクロックパルスCK1をカウントするカウンタ311aを備え、リードの場合、そのカウントをワードアドレスWXとして、ラッチ411Lのデータ入力端のワードアドレスWA部に供給する。
【0051】
制御回路311は、転送制御回路261CからのSEND1及び転送制御回路411CからのACK2のいずれか一方又は両方がインアクティブの場合には、各ワードメモリのクロック入力端CK及び出力イネーブル制御入力端OEをインアクティブに維持してその入力ゲート及び出力ゲートを閉じる(ワードメモリのアクセスを無効にする)。
【0052】
制御回路311は、転送制御回路261CからのSEND1及び441CからのACK2が共にアクティブになると、カウンタ311aをゼロクリアし、アドレスADRのうち、ビットDA0が'1'であればワードメモリ320W〜3231Wのアクセスを無効にし、以下のような制御を行う。
【0053】
制御回路311は、コマンドCMDがリードを示していれば、転送制御回路261Cに対するACK1をインアクティブに維持した状態で、次のような制御を行う。
【0054】
(1)ワードメモリ3131W〜310Wのうち、ページアドレスPAとワードアドレスWXとで指定されるワードメモリの出力イネーブル制御入力端OEをアクティブにさせて、このワードメモリの内容をループ配線310上に読み出させ、このデータがラッチ411Lのデータ入力端で確定したと考えられる所定時間経過後に、SEND2をアクティブにさせる。転送制御回路411Cはこれに応答して、次段からのACKがアクティブであれば、クロックパルスCK1をラッチ411Lのクロック入力端CKに供給してループ配線310上のデータ(DATA、DA及びPA)及び制御回路311からのワードアドレスWXをラッチ411Lに取り込ませ保持させ、次いでACK2をアクティブにさせる。制御回路311は、クロックパルスCK1をカウンタ311aでカウントしてワードアドレスWXをインクリメントし、ACK2のアクティブに応答してSEND2をインアクティブにさせる。
【0055】
(2)入口ノード411から次段へのデータ転送が完了すると、ACK2がアクティブになり、制御回路311はこれに応答して、カウンタ311aの値が8未満であれば(1)へ戻る。
【0056】
カウンタ311aの値が8になれば、転送制御回路261Cに対するACK1をアクティブにして、ラッチ261Lがその後段からのデータを取り込めるようにさせる。
【0057】
このような処理により、ノード261に保持されたアドレスADRのページアドレスPAで示される8ワードの記憶内容が順次メモリ行31からラッチ411Lへ転送される。
【0058】
制御回路311は、コマンドCMDがライトを示していれば、SEND2をインアクティブに維持した状態で、アドレスADRのページアドレスPAとワードアドレスWAとで指定されるワードメモリのクロック入力端CKにパルスを供給して、ループ配線310上のデータをこのワードメモリに取り込ませ保持させ、次いでACK1をアクティブにする。
【0059】
このようなメモリアクセスを、メモリ行アレイ30のうち最大32個のメモリ行に対し同時に行うことが可能である。
【0060】
リードパケットの場合、図1に戻って、合流路40のどの入口ノードからでも、出口ノード461に到達する。すなわち、合流路40では、経路選択に行先アドレスを用いる必要がない。合流路40の各ノードでは、2入力のうち先に到達したデータを選択的に保持する。
【0061】
図4は、束データ方式で合流路40を構成した場合の第2段と第3段の一部である合流回路を示す概略ブロック図である。
【0062】
第2段のノード421は、ラッチ421Lと転送制御回路421Cとを備え、第2段のノード422は、ラッチ422Lと転送制御回路422Cとインバータ422Gとを備え、第3段のノード431は、ラッチ431Lと転送制御回路431Cとを備えている。転送制御回路421C、422C及び431Cはそれぞれ、ラッチ421L、422L及び431L内の入力段ゲート開閉をハンドシェイクプロトコルで行うものであり、段間が縦続接続されている。
【0063】
図4の回路は、図3の回路において信号の方向を逆にしたものになっている。但し、行き先アドレスのビットによる制御は行われていない。また、ラッチ421Lの出力とラッチ422Lの出力との衝突を避けるため、各ラッチは出力イネーブル制御入力端OEを備え、転送制御回路431Cからラッチ421Lの出力イネーブル制御入力端OEへ直接、ラッチ422Lにはインバータ422Gを介して出力イネーブル制御入力端OEへ、制御信号が供給される。転送制御回路431Cは、転送制御回路421CからのSEND−INと転送制御回路422CからのSEND−INのうち先にアクティブになった方に対応するラッチの出力イネーブル制御入力端OEを'1'にし、他方を'0'にする。
【0064】
このような制御により、選択的(排他的)合流が行われる。
【0065】
上記の如く構成されたメモリ10において、入口ノード211にライトデータパケットを供給するとともに、入口ノード211へのSEND−IN信号をアクティブにさせると、その行先アドレスに応じ分流路20内のパイプラインステージを順次流れてメモリ行アレイ30に到達し、ライトデータパケット内のアドレスADRで指定されたワードに、ライトデータパケット内のデータDATAが書き込まれる。
【0066】
同様に、入口ノード211にリードパケットを供給するとともに、入口ノード211へのSEND−IN信号をアクティブにさせると、その行先アドレスDAに応じ分流路20内のパイプラインステージを順次流れてメモリ行アレイ30に到達し、リードパケット内のページアドレスPAで指定されたページのデータがワード単位で順次読み出され、行先アドレスDAの値とは無関係に、合流路40内のパイプラインステージを順次通って出口ノード461に8ワード分のデータが到達する。
【0067】
入口ノード211内のパケットがノード221又はノード222に転送されてACK−OUT信号がアクティブになると、次のパケットを入口ノード211に保持させることができる。また、次に供給するパケットの種類は、先に供給したパケットがリードパケットであるかライトデータパケットであるかによらず、任意である。
【0068】
本実施例1のメモリ10によれば、メモリ行アレイ30を介してツリー形分流路20及びツリー形合流路40を配設するという簡単な構成で、集積配置されたメモリ行アレイ30の任意の1行に対し、行き先アドレスを含むパケットを転送し、これに対応したパケットをツリー形合流路40の出口ノード461から取り出すことができるという効果を奏する。
【0069】
また、流路幅が比較的広い分流路20の出口側及び合流路40の入口側でパケットの混雑が避けられるので、メモリ行での処理の遅延が複数のメモリ行での分散並列処理により吸収され、ランダムアクセスのスループットが比較的高いという効果を奏する。
【0070】
さらに、データ駆動型回路でプロセッサを構成した場合、非データ駆動型メモリを多数用いて並列度を上げるよりも1つのデータ駆動型メモリを用いた方が消費電力を大幅に低減できるので、特に長電池寿命が要求されるモバイル機器に用いて好適であるという効果を奏する。
【0071】
なお、本実施例1ではページ単位でのリードについて説明したが、行単位、ワード単位又はバイト単位等でのアクセスであってもよいことは勿論である。この点は、以下の実施例においても同様である。
【実施例2】
【0072】
図1のメモリ10では、並列度が高いにもかかわらず入口ノード及び出口ノードがそれぞれ1つである点がボトルネックとなっている。図6は、この点を改良した本発明の実施例2のメモリ10Aを示す。
【0073】
このメモリ10Aでは、分流路20Aに入口ノード212が追加され、入口ノード212の出力がノード221及び222Aに供給されて、第2段のノード221A及び222Aが2合流・2分岐回路となっている。この合流は上述の選択型であり、例えばノード221Aは、入口ノード211と212からのSEND−INのうち先にアクティブになったものに対応するデータを取り込んで保持する。この分流路20Aにおいても、図1の分流路20と同様に、行先アドレスDAのみで定まる出口ノードへ到達する。したがって、ライトデータパケットについては新たな規則を設ける必要がない。
【0074】
合流路40Aでは、出力段に出口ノード462を追加し、ノード451A又はノード462Aから出口ノード462へ転送可能にしている。ノード451A及び462Aはいずれも、2合流・2分岐回路である。
【0075】
ここで、ノード451Aから出口ノード461又は出口ノード462のいずれにデータを転送させるかの規則が必要になる。例えば、出口ノード461と462に優先順位を付け、両方がエンプティ(ACK−INがアクティブ)である場合にはノード451Aから優先順位の高いものの方へ転送させ、一方のみ空いている場合にはそちらへ転送させるように構成することもできる。
【0076】
本実施例では、データ流を整然とさせるため、図7(A)に示すように、パケット50Aに1ビットの系統CHを追加し、この値が'0'のときはノード451A又はノード452Aから出口ノード462へ転送させ、'1'のときには、ノード451A又はノード452Aから出口ノード461へ転送させる。系統CHの値は、リードパケットを入口ノード211と212とのいずれに供給するかにより定める。例えば、入口ノード212にパケットを供給するとき、系統CHに'1'をセットし、入口ノード211に供給するとき、系統CHに'0'をセットする。
【0077】
このようにしてリードパケットを入口ノード211へ供給すると、メモリ行アレイ30から読み出されるデータは必ず出口ノード461に到達し、リードパケットを入口ノード212へ供給すると、メモリ行アレイ30から読み出されるデータは必ず出口ノード462に到達する。パケット経路は論理的対称性を有する。すなわち、メモリ行アレイ30の列に関し分流路20Aと合流路40Aとでパケット経路が論理的に対称(第1の対称性)になる。また、互いに相補的な行先アドレス、例えば行先アドレス011011を有するパケットの経路と行先アドレス100100を有するパケットの経路とが、流路方向の軸に関し互いに、論理的に対称(第2の対称性)になる。本発明では、少なくとも第2の対称性を備えておればよい。
【0078】
図7(B)は、系統CHが'0'である場合に分流路20Aの第1及び第2段を通り得るリードパケットの経路と、読み出されたリードデータパケットが通り得る、合流路40Aの第5段及び第6段の経路とを示している。点線は系統CHが'0'である場合を示し、実線は系統CHが'1'である場合を示す。
【0079】
リードパケットの行先は、系統CHの値によらず、行先アドレスDAの値のみで定まる。例えば、系統CHが'1'で行先アドレスDAの最上位ビットが'1'の場合、上述のように'1'で図7(B)の上側へ分岐し'0'で下側へ分岐すると定めると、入口ノード211に供給されたパケットはノード221Aへ進む。
【0080】
合流路40Aでは、第5段まで合流はあっても分岐がないので、系統CHや行先アドレスDAの値と無関係に経路が一意的に定まり、前記の場合、リードデータパケットはノード451Aに到達する。
【0081】
系統CHが'1'であるので、ノード451Aから461Aへ進む。行先アドレスDAの最上位ビットが'0'の場合についても同様にして、リードデータパケットは出口ノード461に到達する。すなわち、合流路40Aの第5〜6段での経路を系統CHの値で定めると、メモリ行アレイ30に関し分流路20Aと合流路40Aとで経路が対称になり、系統CHが'1'の場合には必ず、分流路20Aの入口ノード211に対応した合流路40Aのノード461Aに到達する。
【0082】
他の点は上記第1実施例と同一である。
【0083】
本実施例2によれば、上記のようなノードの追加及び変更により、メモリ10Aの入力ポート及び出力ポートの数が2倍になるので、スループットを大きく向上させることができるという効果を奏する。
【0084】
また、2系統で、流路幅が比較的広い分流路20Aの後段及び合流路40Aの前段を共用するので、パフォーマンス低下を抑制しつつ通信路の規模に対する並列度を高くすることができるという効果を奏する。
【0085】
さらに、パケット50Aに系統CHを追加し、合流路40Aの出口側の合流・分岐回路で系統CHの値に従って分岐させることにより、分流路20Aのどの入口ノードにリードパケットを供給すれば合流路40Aのどの出口ノードからリードデータパケットが得られるかが定まるので、合流路40Aから取り出されたデータの処理が容易になるという効果を奏する。
【実施例3】
【0086】
図8は、入力ポート及び出力ポートの数を実施例2の場合の2倍にした、本発明の実施例3のメモリ10Bを示す。
【0087】
このメモリ10Bでは、パケットの流れの方向の軸に関し構成が対称になるように、図6の構成にノードが追加されている。
【0088】
すなわち、分流路20Bの入力段に入口ノード213及び214が追加され、第2段にノード223A及び224Aが追加され、これらの間の接続が、ノード211及び212とノード221A及び222Aとの間の接続と同じになっている。また、分流路20Bの第3段の各ノードも第2段と同様に2合流・2分岐回路にし、上記対称になるように第2段と第3段との間が接続されている。
【0089】
分流路20Bを流れるパケットの経路は、実施例2の場合と同様に、行先アドレスDAのみにより定まる。したがって、ライトデータパケットについては新たな規則を設ける必要がない。
【0090】
合流路40Bについても分流路20Bと同様に、出力段にノード463A及び464Aが追加され、この後段にノード453A及び454Aが追加され、これらの間の接続が、ノード461A及び462Aとノード451A及び452Aとの間の接続と同じになっている。また、合流路40Bのさらに後段(第4段)の各ノードも第5段と同様に2合流・2分岐回路にし、上記対称になるように第4段と第5段との間が接続されている。
【0091】
図9(A)は、パケット50Bのフォーマットを示す。このパケット50Bは、系統CHが2ビットであり、他の点は図7(A)と同一である。リードパケットの場合、パケットが入口ノード214〜211に供給されるとき、それぞれ系統CHの値を0〜3とする。これにより、メモリ行アレイ30から読み出されたリードデータパケットは、メモリ行アレイ30に関し分流路20Bでの経路と対称な経路を通ることになる。
【0092】
図9(B)は、系統CHが'01'である場合に分流路20Bの第1〜3段を通り得るリードパケットの経路と、読み出されたリードデータパケットが通り得る経路とを点線で示している。
【0093】
リードパケットの行先は、上述のように、系統CHの値によらず行先アドレスDAの値のみで定まる。例えば、行先アドレスDAの上位2ビットが'11'の場合、上述のように'1'で図11(B)の上側へ分岐し'0'で下側へ分岐すると定めると、最上位ビットが'1'であるので入口ノード213からノード223Aへ進み、次のビットが'1'であるのでノード223Aから231Aへ進む。
【0094】
合流路40Bでは、第4段まで合流はあっても分岐がないので、系統CHや行先アドレスDAの値と無関係に経路が一意的に定まり、前記の場合、リードデータパケットはノード441Aに到達する。
【0095】
系統CHが'01'であり、この第2ビットが'0'であるので、ノード441Aから453Aへ進む。次に、第1ビットが'1'であるのでノード453Aから463Aへ進む。行先アドレスDAの上位2ビットが他の場合についても同様にして、リードデータパケットはノード463Aに到達する。すなわち、合流路40Bの第4〜6段での経路を系統CHの値で定めると、メモリ行アレイ30に関し分流路20Bと合流路40Bとで経路が対称になり、系統CHが'01'の場合には必ず、分流路20Bの入口ノード213に対応した合流路40Bのノード463Aに到達する。
【0096】
図9(C)は、系統CHが'11'である場合に分流路20Bの第1〜3段を通り得るリードパケットの経路と、読み出されたリードデータパケットが通り得る経路とを点線で示している。
【0097】
本実施例3によれば、上記実施例2の構成を少し変えただけで上記実施例2で述べた効果がさらに高められる。
【0098】
また、4系統で分流路20Bの流路幅が比較的広い第4〜6段及び合流路40Bの流路幅が比較的広い第1〜4段のノードを共用するので、パフォーマンス低下を抑制しつつ通信路の規模に対する並列度を高くすることができるという効果を奏する。
【実施例4】
【0099】
図10は、パイプライン段数を低減した、本発明の実施例4のメモリ10Cを示す。
【0100】
分流路20Cでは、第3段の入力まで、図8の分流路20Bのそれと同一である。分流路20Bとの相違点は、第3段の各ノード及び第4段の各ノードの出力が4分岐となっている点である。これにより、分流路20Bが6段パイプラインであるのに対し分流路20Cは4段パイプラインとなる。合流路40Cは、メモリ行アレイ30に関し分流路20Cと対称にし且つデータ流の方向を逆にした構成であり、4段パイプラインである。
【0101】
実施例3の場合と同様に、分流路20Cでのパケットの経路は、入口ノードが決まると、パケットの経路は行先アドレスのみで定まり、合流路40Dについては、選択的分岐出力を持つノードからのパケット経路は、系統により定まる。
【0102】
ノード入力端での合流の数が増えると、先着優先の選択的合流であるので、同一の合流ノードに転送されるパケット数が多くなると、転送待ちが生ずる。しかしながら、パケットが混雑していない時には、パイプライン段数が少ないので、レイテンシを短縮することができる。
【0103】
ライトパケットのようにメモリ行アレイ30への書き込みが1ワードで完了する場合には分流路20Cの出口ノードでの待ち時間が比較的短いので効果的である。これに対し、リードデータパケットは、メモリ行31から8ワードのデータが順次読み出されるので、合流路40Cの入力ノードにおいて、他のメモリ行31から同一入口ノードへの待ち時間が比較的長くなる。これを避けるためには、合流路40Cの代わりに合流路40Bを用いればよい。すなわち、分流路20Cと合流路40Cとを組み合わせればよい。
【実施例5】
【0104】
図11は、選択的合流ノードへの転送待ちを短縮した、本発明の実施例5の2ポート入力・2ポート出力型のメモリ10Dを示す。
【0105】
図6の分流路20Aにおいて、選択的合流は第2段のノード221A及び222Aであり、第1段で待ちが生ずる。
【0106】
そこで、分流路20Dでは、第2段において選択的合流が生じないように、第2段にノード223及び224を追加している。ノード223からノード231A又は233Aへ分岐して合流し、ノード224からノード235A又は237Aへ分岐して合流する。
【0107】
これにより、第3段の各ノードが選択的合流になるが、ノード数が4であるので、図6の分流路20Aの第1段でのパケット転送平均待ち時間よりも、分流路20Dの第2段でのそれのほうが約半分になり、パケットの停滞を低減してスループットを向上させることができる。
【0108】
他の点は、実施例2と同一である。
【実施例6】
【0109】
図12は、入力ポート及び出力ポートの数を実施例5の場合の2倍にした、本発明の実施例6のメモリ10Eを示す。
【0110】
このメモリ10Eでは、パケットの流れの方向の軸に関し構成が対称になるように、図11の構成にノードが追加されている。
【0111】
すなわち、分流路20Eの入力段に入口ノード213及び214が追加され、第2段にノード225〜228が追加され、第3段に1つおきにノード232A、234A、236A及び238Aが追加され、これらとノード225〜228との間の接続が、図11の分流路20Dの第2段と第3段との間の接続と同じ形になっている。また、分流路20Eの第4段の各ノードも第3段と同様に2合流・2分岐回路にし、上記対称になるように第3段と第4段との間が接続されている。
【0112】
合流路40Eは、メモリ行アレイ30に関し分流路20Eと対称にし且つデータ流の方向を逆にした構成である。
【0113】
実施例5の場合と同様に、分流路20Eでのパケットの経路は、入口ノードが決まると、パケットの経路は行先アドレスのみで定まり、合流路40Eについては、選択的分岐出力を持つノードからのパケット経路は、系統により定まる。
【0114】
本実施例6によれば、上記実施例5の構成を少し変えただけで上記実施例5で述べた効果がさらに高められる。
【実施例7】
【0115】
マルチCPUにおいて、それぞれのCPUが共有メモリに対するデータキャッシュメモリを持つと、コヒーレンシ(データの整合性)が保てなくなる。1つのデータキャッシュメモリに対し複数のCPUが参照できる共有キャッシュによれば、コヒーレンシを保つことが可能となる。
【0116】
しかし、同期型の場合、複数のCPUからのランダムな要求に対してもグローバルな同期をとる必要があるため、スループットが不充分となる。
【0117】
一方、非同期型パイプライン方式はスループットが高いが、パイプライン段数が増えるとレイテンシが増加してアクセスタイムが長くなるので、パイプライン方式は、通常のキャッシュメモリには向かない。
【0118】
しかし、マルチCPUの場合、非同期型パイプライン方式を用いても、レイテンシ増加の欠点が相対的に隠蔽され、逆に多並列処理の利点が生きてくる。マルチコアCPUについても同様である。
【0119】
図13は、本発明が適用されたキャッシュメモリ60の概略ブロック図である。このキャッシュメモリ60は、プロセッサの内部に埋め込まれ又はプロセッサの外部に配置される。マルチCPUでキャッシュメモリ60を用いる場合には、パケットにCPU識別子を含ませる必要があるが、説明の簡単化のため、以下ではCPU識別子が無い場合を説明する。
【0120】
キャッシュメモリ60には、実施例1のメモリ10が配設され、このメモリ10に対応してタグテーブル70が配設されている。タグテーブル70では、分流路71の下流側にタグアレイ72を介して合流路73が接続されている。分流路71及び合流路73はそれぞれ、メモリ10の分流路20及び合流路40と同一構成にすることができる。
【0121】
タグアレイ72を構成するタグ行721の行数は、メモリ行アレイ30のそれと同一である。リードパケット又はライトパケットは、キャッシュメモリ60の外部から入出力部80のインターフェイス81を介して分流路71に供給される。
【0122】
パケットのフォーマットが図2(B)のそれと異なる点は、アドレスADRにおいて上位側にタグアドレスTAが付加されている点と、ヒットビットHMが付加されている点である。メモリ10の分流路20に供給されるパケットのフォーマットは、分流路71に供給されるパケットのそれと同一である。
【0123】
タグテーブル70は、供給されるパケットに基づいて、外部メモリ上のタグアドレスTA、行先アドレスDA及びページアドレスPAで識別されるページのデータが、メモリ行アレイ30内の行先アドレスDAで識別される行及びこの行内のページアドレスPAで識別されるページに格納されているかどうかを判定し、その結果に応じた処理を行うものである。
【0124】
タグテーブル70は、供給されるパケットに含まれるタグアドレスTAの値が、行先アドレスDAで識別されるタグアレイ72内の行及びこの行内のページアドレスPAで識別される列のTAGに格納されているタグアドレスの値と一致するか否かでこの判定を行う。一致する場合にはヒットビットHMを'1'にセットし、そうでなければこれを'0'にセットして後述の追い出し/ライトバック/更新処理を行う。
【0125】
図14は、タグアレイ72内の隣り合うタグ行721と722との構成を示す概略ブロック図である。
【0126】
タグ行721及び722は、ノード711とノード731との間に接続されている。ノード711は、タグ行721及び722に対応する分流路71の出口ノードであり、ノード731は、タグ行721及び722に対応する合流路73の入口ノードである。
【0127】
タグ行721及び722は、ループ配線740を備え、これがラッチ711Lのデータ出力端及びラッチ731Lのデータ入力端に接続されている。ループ配線740は、コマンドCMD、ヒットビットHM及びページアドレスPA以外の信号線である。すなわち、コマンドCMD、ヒットビットHM及びページアドレスPA以外は、ラッチ711Lからラッチ731Lへ直接伝達される。ループ配線740に含まれるタグアドレス(TA)信号線は、タグ行721の構成要素であるコンパレータ760〜763の一方の入力端に接続され、タグ行722についても同様である。
【0128】
転送制御回路711Cと転送制御回路731Cとの間には、制御回路741が接続されている。タグ行721は、第0〜3ページに対応したページ情報記憶部750〜753を備え、これらはいずれも、タグTAG、バリッドビットV、ダーティビットD、ロックビットL及びカウンタCNTを備えている。
【0129】
ページ情報記憶部750〜753のタグTAGの内容はそれぞれ、コンパレータ760〜763の他方の入力端に供給される。コンパレータ760〜763は、いずれも2入力が互いに一致するときのみ'1'を出力する。コンパレータ760〜763の出力は、一方ではオアゲート764に供給されてヒットビットHMが生成され、他方ではエンコーダ765に供給されてページアドレスPA1が生成される。
【0130】
マルチプレクサ766には、タグ行721のページアドレスPA1及びヒットビットHM1、これらに対応するタグ行722のページアドレスPA2及びヒットビットHM2、並びに制御回路741からのページアドレスPA及びヒットビットHMが供給され、制御回路741からの選択制御信号によりこれらのうちの1組が選択されて、ラッチ731Lの対応するデータ入力端に供給される。ヒットビットHM1及びHM2は、制御回路741にも供給される。制御回路741にはさらに、ラッチ711Lから行先アドレスDAのビットDA0、ページアドレスPA、タグアドレスTA及びコマンドCMDが供給される。
【0131】
制御回路741は、ビットDA0が'1'のときタグ行721側を有効にしてタグ行722側を無効にし、'0'のときこの逆にする。以下においてはビットDA0が'1'である場合を説明する。
【0132】
ここで、図13のノード77は、次のような規則で、合流路73からのパケットを分岐転送させる。
【0133】
(R)コマンドCMDがリードコマンド又はライトコマンドでヒットビットHMが'1'、又は追い出しコマンドの場合、合流路73からのパケットをメモリ10の分流路20側へ転送させ、その他の場合、すなわち更新コマンド又は外部メモリへの書込コマンドの場合には、このパケットを入出力部80のノード82側へ転送させる。
【0134】
制御回路741は、転送制御回路711CからのSEND3がアクティブであり且つ転送制御回路731CからのACK4がアクティブであると、ビットDA0が'1'であればタグ行721側の回路の出力を有効にしタグ行722側の回路の出力を無効にして、後述の制御を行った後、次のような後処理を行う。
【0135】
(A)制御回路741は、ラッチ731Lの入力データが確定したと考えられる時間経過後に、転送制御回路731CへのSEND4をアクティブにする。転送制御回路731Cはこれに応答して、転送制御回路731Cの前段からのACKがアクティブであれば、ラッチ731Lのクロック入力端CKにパルスを供給して入力データをラッチ731Lに取り込ませ保持させ、ACK4をインアクティブにする。制御回路741はこれに応答してSEND4をインアクティブにする。制御回路741は次いで、ACK3をアクティブにして、ラッチ711Lがその後段からのデータを取り込めるようにさせる。
【0136】
制御回路741は、コマンドCMDがリードを示していれば、転送制御回路711Cに対するACK3をインアクティブに維持した状態で、次のような制御を行う。
【0137】
(a)リードでキャッシュヒット
制御回路741は、オアゲート764の出力が確定していると考えられる所定時間経過後にヒットビットHM1が'1'であれば、一方ではマルチプレクサ766に対し、ページアドレスPA1とヒットビットHM1との組を選択させ、ラッチ711LからのコマンドCMDをそのままノード731へ供給し、他方ではページアドレスPA1=iに対応したページ情報記憶部75iのカウンタCNTをインクリメントする。但し、カウンタCNTは、その値が最大値になるとインクリメントされない。
【0138】
制御回路741は、次いで上記後処理(A)を行う。パケットは、合流路73を通って図13のノード77へ転送される。ノード77では、上記規則(R)によりメモリ10側へ転送され、対応する1ページ分のデータが合流路40から読み出されて、これが入出力部80のノード82を介しインターフェイス81に供給され、インターフェイス81からCPU側へ出力される。
【0139】
(b)リードでキャッシュミスヒット且つページ内でV='0'有り
制御回路741は、ヒットビットHM1が'0'、且つ、ページ情報記憶部750〜753のいずれかのバリッドビットVが'0'(未使用)であれば、このバリッドビットVが属するタグTAGをこのパケットのタグアドレスTAで書き換え、コマンドCMDを更新コマンドにし、このバリッドビットVが属するページ情報75i(iは0〜3のいずれか)のiをページアドレスPAとし、これとHM='0'をマルチプレクサ766に供給するとともに、マルチプレクサ766に対しこれらPAとHMとの組を選択させ、次いで上記(A)の後処理を行う。
【0140】
上記規則(R)により、更新コマンドのパケットはノード77、82及びインターフェイス81を介し外部メモリコントローラ側へ供給され、外部メモリから、このパケットのタグアドレスTA及びページアドレスPAで指定される1ページ分のデータがバーストモードで読み出される。
【0141】
このデータは、一方ではリード要求を行ったCPUへ供給され、他方ではワード単位でインターフェイス81へ供給される。インターフェイス81では、前記更新パケットがこのデータの到着を待機しており、図15に示すように、この更新パケットのデータフィールドに1ワードのデータが書き込まれ、そのコピーが分流路71へ供給される。2回目以降は、更新パケット内のワードアドレスWAが1だけインクリメントされて同様の処理が、WA='11'になるまで繰り返される。
【0142】
タグアレイ72では、図14において、次のような処理が行われる。制御回路741は、コマンドCMDが更新コマンドである場合、ライトを示すコマンドCMDをラッチ731Lに供給するとともに、バリッドビットVが'0'であればこれを'1'にし、ロックビットLを'1'にし、次いで上記(A)の後処理を行う。
【0143】
上記規則(R)により、ライトコマンドのパケットはノード77からメモリ10へ分岐し、アドレスに応じた場所に1ワードのデータが順次書き込まれる。
【0144】
(c)リードでキャッシュミスヒット且つページ内で全てV='1'
制御回路741は、ヒットビットHM1が'0'、且つ、ページ情報記憶部750〜753のいずれのバリッドビットVも'1'であれば、次のようにして追い出しページを決定する。
【0145】
すなわち、ページ情報記憶部750〜753のカウンタCNTのうち、ロックビットLが'0'であるカウンタCNTの最小値がどれであるかを決定し、このカウンタCNTが属するページ情報75i(iは0〜3のいずれか)のiを追い出し/更新ページiと決定する。ロックビットLが'0'であることを追い出し/更新ページ決定対象の条件とすることにより、L='1'且つV='1'であればタグTAGの書き換えが禁止される。
【0146】
制御回路741は次いで、ダーティビットDが'1'であれば、追い出しを示すコマンドCMDをラッチ731Lに供給し、PA=i及びHM='1'をマルチプレクサ766に供給し、マルチプレクサ766にこの組を選択させる。次いで上記(A)の後処理を行う。
【0147】
上記規則(R)により、パケットはノード77を介しメモリ10側へ転送され、リードコマンドの場合と同じ処理が行われて、対応する1ページ分のデータがワード単位で合流路40から読み出され、ノード77、入出力部80のノード82及びインターフェイス81を介し外部メモリコントローラ側へ供給される。これにより、外部メモリ内の、パケットのタグアドレスTA及びページアドレスPAで指定されるページに、データがライトバックされる。
【0148】
制御回路741は、ダーティビットDが'0'である場合、又は、ダーティビットDが'1'で上記追い出しコマンドのパケットをラッチ731Lへ転送する直前又は直後に、ラッチ711LからのタグアドレスTAをページ情報75iのタグTAGに書き込み、ロックビットLを'1'にし、該転送の直後に、更新を示すコマンドCMDをラッチ731Lに供給し、上記(2R)で述べた更新コマンドのパケット生成処理を行う。
【0149】
したがって、ダーティビットDが'1'の場合、タグ行721から追い出しコマンドのパケットが出力された後直ぐに、更新コマンドのパケットが出力され、その後、追い出し処理と更新処理とが並列して行われる。
【0150】
制御回路741は、コマンドCMDがライトを示していれば、転送制御回路711Cに対するACK3をインアクティブに維持した状態で、次のような制御を行う。
【0151】
(d)ライトでキャッシュヒット
制御回路741は、オアゲート764の出力が確定していると考えられる所定時間経過後にヒットビットHM1が'1'であれば、一方ではマルチプレクサ766に対し、ページアドレスPA1とヒットビットHM1との組を選択させ、ラッチ711LからのコマンドCMDをそのままノード731へ供給し、他方ではカウンタCNTをインクリメントし、ダーティビットDに'1'をセットする。次いで上記(A)の後処理を行う。上記規則(R)により、パケットはノード77を介しメモリ10側へ転送され、パケット内の行先アドレスDA、ページアドレスPA及びワードアドレスWAで指定されるワードメモリにパケット内のデータDATAが書き込まれる。
【0152】
(b)ライトでキャッシュミスヒット
制御回路741は、ヒットビットHM1が'0'であれば、メモリへの書き込みを示すコマンドCMDをラッチ731Lに供給し、ヒットビットHM='0'及びラッチ711LからのページアドレスPAをマルチプレクサ766に供給し、マルチプレクサ766にこの組を選択させる。次いで上記(A)の後処理を行う。上記規則(R)により、パケットはノード77、入出力部80のノード82及びインターフェイス81を介し外部メモリコントローラ側へ供給され、外部メモリ内の、パケットのタグアドレスTA及びページアドレスPAで指定されるページに、パケット内のデータDATAが書き込まれる。
【0153】
本実施例7のキャッシュメモリ60によれば、メモリ10及びタグテーブル70内の各パイプライン段及びノード77、インターフェイス81及びノード82にパケットが分散しそれぞれのノードでローカルな同期をとってパイプライン処理を行うことができるので、複数のヒットと複数のミスヒットとに対する処理を同時に並列に行うことができ、スループットが高く、しかも構成が比較的簡単であるので、特に、同期型マルチCPUやデータ駆動型処理装置に用いて好適である。
【実施例8】
【0154】
図16は、本発明の実施例8のキャッシュメモリ60Aを示す概略ブロック図である。
【0155】
このキャッシュメモリ60Aでは、図13のメモリ10及びタグテーブル70の代わりに、4系統のメモリ10A及びタグテーブル70Aが配設されている。これに対応して、図13のノード77の代わりに、ノード771〜774が配設され、図13の入出力部80の代わりに、入出力部80と同一構成の入出力部801〜804が配設されている。
【0156】
キャッシュメモリ60Aの動作は、以上の説明から容易に理解できるので、これを省略する。
【0157】
本実施例8のキャッシュメモリ60Aによれば、系統が実施例7の場合の4倍になるので、スループットが高く、上記実施例で述べた効果が高くなる。しかも、各系統について、メモリ10A内及びタグテーブル70A内において第1〜4系統で共用されるノードが多く且つメモリ行アレイ30及びタグアレイ72が各系統で共用されるので、資源を有効利用できるとともに、構成の複雑化が避けられ、しかも、流路幅の比較的広い部分で共用されるので、パケットの混雑によるスループット低下が抑制されるという効果を奏する。
【実施例9】
【0158】
CPUでは一般に、2つのオペランドに対して処理を行う命令が多数有る。パイプライン段数が多いとレイテンシが長くなるが、1つのCPUコアで時分割n並列処理を行う場合、同期型では、切替時間がゼロであると仮定しても各処理の速度が1/nとなるので、例えばサーバーコンピュータのように並列度が高い場合には、非同期型の方が有利となる。
【0159】
図17は、本発明が適用された実施例9の、このような用途に用いて好適なプロセッサの一部であるデータ処理部10APを示す概略ブロック図である。
【0160】
この図に太線で示すように、合流路40APのどの出口ノードにパケットが到達するかは系統値のみにより定まるので、同一系統に複数のパケットを連続して分流路20Aの入口ノードに供給することにより、これに対応したデータパケットを複数、合流路40APの同一出口ノードに集めることができる。すなわち、系統値を同一にすることにより、出口ノードで複数のパケットの待ち合わせを自動的に行うことができる。
【0161】
そこで、合流路40APでは、出口ノード461AP〜464APのそれぞれに、処理要素を備えている。各処理要素での処理内容は、同一であっても、系統値により定まるものであってもよい。処理要素は、高機能であっても低機能であってもよい。30Rは、レジスタファイルとして用いられる。レジスタファイル30Rを、これら処理要素で共有する領域と個々に専用する領域とに、自由に分割することができる。
【0162】
図18(A)は、コマンドCMDを含む第1オペランドパケットP1と、第2オペランドパケットP2とを順次入口ノード211に投入したときに、これらに対応したパケットP1A及びP2Aがノード461Pに到達し、その処理要素により結果パケットP3が得られる場合を示している。第1オペランドパケットP1又は/及び第2オペランドパケットP2は、順次供給される複数のパケットであってもよい。
【0163】
このパケットP3が、図18(B)に示すパケットP1N及びP2Nのように、次のステップのパケットP1とP2とに対応したものである場合、これらを、ノード47を介し入口ノード211にフィードバックさせることにより、処理を連続的に高速に行うことができる。ノード47は、ノード461Pが出力したパケットP1Nに基づいて、処理が完了したか否かを判定し、肯定判定した場合には結果を出力し、パケットに含まれる処理モード(又はCMD)に基づいて、処理を打ち切り又は継続する。
【0164】
分流路20Aは、デコーダとして機能するとともに、キューとしても機能する。また、合流路40APの出口ノード以外のノードは、同一系統の処理要素へパケットを集配するとともに、キューとしても機能する。したがって、入口ノード211〜214にパケットが不定期に供給され、且つ、その平均時間が出口ノード461AP〜464APに備えられた処理要素の処理時間にほぼ等しい場合には、データ処理部10APの外部にキューを設けることなく、効率よく処理を行うことができる。この平均時間は、入口ノード211〜214にパケットを供給する回路又は装置の並列度を調整することにより、適正な値に変更可能である。
【0165】
また、1つのリードパケットに対しレジスタファイル30Rから複数パケットが読み出される場合にも、合流路40APの出口ノード以外のノードはこれらに対するキューとして機能し、キューを新たに設けることなく、効率よく処理を行うことができる。
【0166】
したがって、データ処理部10AP内の段数が比較的多くても、逆に利点となる場合がある。
【0167】
並列度が高いと多数のデータを同時に使用するが、本実施例9のデータ処理部10APによれば、比較的多数のレジスタを複数の処理要素において選択的に利用でき、かつ、実施例1で述べたように高スループットでランダムアクセスができるので、効率よく処理を行うことができるという効果を奏する。
【0168】
また、従来ではFIFOメモリ、ハッシュメモリ、連想メモリ、演算部及び制御部等を備えたマッチングメモリで同一カラーのパケットを待ち合わせて処理要素で処理を行っていたので、構成が複雑であるとともに、処理が遅延してスループットが低下する原因となっていたが、本実施例9では、パケットペアが連続して合流するのでマッチングメモリを用いる必要が無く、構成が簡単になるとともにスループットが高くなるという効果を奏する。
【実施例10】
【0169】
図18(A)において、パケットP1に対しレジスタファイル30Rから読み出されるデータが例えば上述のリードパケットのように8ワードである場合、通信路でデータが混雑する。この場合、演算結果のパケット数が少なければその下流側のデータ混雑度を低減することができる。
【0170】
そこで、本発明のプロセッサのデータ処理部10BPでは、図19において、合流路40BPの各ノードに処理要素を備え、パケットP1とP2(図18)とが合流路40BP上で合流したノードにおいて演算を行い、その結果を下流側に転送させる。
【0171】
図19に示す太線は、第1系統と第4系統でのパケットペアの経路を示す。これら経路は、行先アドレスDAと系統CHとで定まる。レジスタファイル30Rに関し分流路20A上の経路と合流路40BP上の経路とが論理的に対称になるように系統CHを定めれば、行先アドレスDAのみで合流路40AP上の合流点が定まる。この合流点に対応する分流路20A上の分岐点は、パケットペアの行先アドレスDAの最上位ビットからの一致ビット数により定まる。
【0172】
例えば図19の上側のパケットペア経路T1及びT2の行先アドレスビットDA1及びDA2の一致部は、図20(A)に示すように上位2ビットの'10'である。一致ビット数をiで表すと、分流路20A上の第(i+1)段でパケットペアが分岐し、合流路40AP上の第(6−i)段でパケットペアが合流する。
【0173】
パケット合流段識別子を、図19中に示すように上記iの値で表し、合流路40AP上の各ノードに、固定した合流段識別子の値を持たせ、これがパケットペアの合流段識別子MAと一致する場合、そのノードの処理要素でパケットペアに対する処理を行う。図20(B)は、合流段識別子MAを含むパケットのフォーマットを示す。図19中に示すように、後の実施例で用いる分流路20A上での分岐段IDも、上記iの値で表す。
【0174】
合流段識別子MAの決定は、分流路20Aの後段側のノード201〜204において行う。図18(B)に示すようにループを構成する場合には、ノード201〜204の配設位置は、合流路40APの下流側であってもよい。
【0175】
図21は、ノード201の構成を示す概略ブロック図である。
【0176】
このノード201は、ラッチ201Lと転送制御回路201Cとの基本構成のほかに、パケットペア判定部201Pと合流段ID決定部201Fとを備えている。
【0177】
パケットペア判定部201Pは、ラッチ201Lの出力及びその後段のデータ出力が確定している場合、すなわちノード201から出力されるSEND2及び転送制御回路201Cに供給されるSEND1が同時にアクティブである場合、ラッチ201Lの下流側及び上流側のパケットに含まれるパケットタイプPT(図20(B))がそれぞれ第1オペランドパケット及び第2オペランドパケットであることを示していれば、パケットペアであると判定する。
【0178】
合流段ID決定部201Fは、この判定に応答して、両パケットの行先アドレスDAに基づき、上述のようにして合流段識別子MAを決定し、これを下流側ラッチに供給することにより、合流段識別子MAを図19のノード211のラッチに取り込ませ保持させる。
【実施例11】
【0179】
リードパケットのペア(第1オペランドパケット及び第2オペランドパケット)に対し、第1パケットに含まれるコマンドに応じた処理を行う場合、それぞれのリードパケットは、図19の分流路20Aにおいて、図20(B)に示すデータフィールドデータDATAが空きになっている。一方、分流路20Bでは入口ノード側の流路幅が比較的狭いので、パケット数が多いと混雑し易い。また、パケットペアを順次分流路20Bに供給しても、合流ノードでは先着優先であるので、パケットペア間に他のパケットが割り込むことが考えられる。
【0180】
そこで、リードパケットのペアを、図22(A)に示すように1パケットに圧縮する。図中、アドレスADR1及びADR2は、それぞれ第1オペランドアドレス及び第2オペランドアドレスである。これらの上位側ビットは、行先アドレスDA1及びDA2を除き、圧縮前の第1及び第2オペランドパケットに共通のフィールドであり、これにより圧縮率が高くなる。
【0181】
図22(A)において、アドレスADR1及びADR2の上位ビットである行先アドレスDA1及びDA2がそれぞれページアドレスPA1及びPA2から離れた位置にあるのは、パケットをその先頭側の通信路層制御データとそれ以外の機能モジュール層データとに分けた為である。通信路層制御データは通信路のみで用いられ、機能モジュール層データは、機能モジュールとしてのレジスタファイル30R、及び合流路40BP上の各ノードに含まれる処理要素で用いられる。圧縮パケットの行先アドレスはDA1とDA2の上位側一致ビットであるので、これらの一方のみでよいが、上述のノード201〜204で用いられるので、両方とも通信路層制御データとしている。
【0182】
ここで、アドレスADR1とADR2とは、行先アドレスDAが一般に異なるので、図19において、分流路20A上のパケット経路T1及びT2の分岐点で、圧縮パケットをパケットペアに伸張する必要がある。どの段で分岐するかは、上述のようにノード201〜204で決定される合流段識別子MA(=分岐段識別子)の値により定まる。
【0183】
そこで、分流路20Aの各ノードに、圧縮パケットをパケットペアに伸張する機能を備え、そのノードに、固定の分岐段識別子を割り当てておき、パケット内の合流段識別子MA(=分岐段識別子)の値が該ノードの分岐段識別子に一致したときに、圧縮パケットをパケットペアに伸張する。
【0184】
図22(A)の圧縮パケット50Dをパケットペアに伸張したパケット50E及び50Fをそれぞれ図22(B)及び(C)に示す。パケット50Eは、パケット50Dをそのまま用いることができる。したがって、最初はパケット50Dをコピーしたものをパケット50Eとして次段へ転送させる。次いで、パケット50D内の行先アドレスビットDA1、ページアドレスPA1及びワードアドレスWA1をそれぞれ行先アドレスビットDA2、ページアドレスPA2及びワードアドレスWA2に書き換えてこれをパケット50Fとし、次段へ転送させる。
【0185】
次に、レジスタファイル30Rから1ページ分読み出したリードデータパケット及びレジスタファイル30Rへの1ページ分のライトパケットについては、いずれも先頭パケットのフォーマットをパケット50Eと同一にし、これに、図22(D)に示すフォーマットのパケット50Gを8個連接させる。そして、パケット50Eの軌跡に沿ってパケット50Gを転送させ、その各ノードで行き先方向を切り替えないことにより、転送中に他のパケットに割り込まれないようにして、これら9パケットを連続させる。
【0186】
このような転送を可能にするために、一方では、各パケットに1ビットの連接ビットCNを備える。連接ビットCNが'1'のとき、これに後続するパケットが有ることを示し、'0'のとき、無いことを示す。図23(A)及び(B)はそれぞれ、パケットタイプPTが'0'の先頭パケットである第1オペランドパケット(レジスタファイル30R内でコピーされた第1オペランドパケット)及びこれに続く、読み出された8ワードのリードデータパケットを示す。図23(C)及び(D)はそれぞれ、パケットタイプPTが'1'の先頭パケットである第2オペランドパケット(レジスタファイル30R内でコピーされた第2オペランドパケット)及びこれに続く、読み出された8ワードのリードデータパケットを示す。
【0187】
なお、順序ビットODの値は、分流路40BPを出た後に順序維持を必要とするか否かにより、機能エレメントアレイ30Rにおいて決定される。
【0188】
他方では、合流路40BP上の各ノードに、連接ビットCNに対応したフリップフロップ(ノード側連接ビット)を備えておき、このフリップフロップの状態を次のように制御する。
【0189】
図25は、合流路40BP上の入口ノード及び出口ノード以外の任意の合流ノードN1のノード側連接ビットF1に対する状態制御回路47とこれに関連する要素を示すブロック図である。合流ノードN1の後段のノードN01及びN02並びに前段のノードN2のフリップフロップをそれぞれF01、F02及びF03と表記する。
【0190】
合流ノードN1は、フリップフロップF01が'1'であれば先着優先の例外として、ノードN01からのパケットを優先的に選択してラッチし、フリップフロップF02が'1'であれば先着優先の例外として、ノードN02からのパケットを優先的に選択してラッチする。
【0191】
状態制御回路47は以下のようにノード側連接ビットF1の状態を制御し、これにより、フリップフロップF01及びF02のうち一方が先に'1'になっているときに他方が後から'1'にならないようにする。
【0192】
(1)状態制御回路47は、フリップフロップF2が'0'であり、ノードN1がラッチしたパケットの連接ビットCNが'1'である場合、フリップフロップF1を'1'にする。
【0193】
(2)状態制御回路47は、ノードN1がラッチしたパケットの連接ビットCNが'0'であれば、フリップフロップF01及びF02を'0'にする。
【0194】
(3)状態制御回路47は、ノードN1がラッチしたパケットの連接ビットCNが'0'であり、ノードN1の合流段識別子がノードN1に保持されているパケットの合流段識別子MAに一致していれば、フリップフロップF1を'0'にする。
【0195】
合流路40BP上の入口ノードのフリップフロップF1に対する状態制御回路47は、上記(1)及び(3)のみの処理を行う。合流路40BP上の出口ノードのフリップフロップF1に対する状態制御回路47は、上記(2)及び(3)の処理を行い、上記(1)について、フリップフロップF2が'0'であるとみなした処理を行う。
【0196】
図24は、このようにしてセットされたフリップフロップをノード上の'1'で示す。
【0197】
各処理要素は処理対象である9ワード×2のパケットを保持するキューを備えており、上述の制御により、2組の連接パケットの合流ノードでは、先着優先によりフリップフロップが先に'1'になった方のノードからの9パケットを連続して取り込み保持し、次いで他方のノードのフリップフロップが'1'になって、このノードからの9パケットを連続して取り込み保持することができ、2組の連接パケットの一方が他方に混入したり他のパケットが連接パケットに混入したりするのを防止することができる。
【0198】
すなわち、第1オペランドの9パケットと第2オペランドの9パケットとがそれぞれ連接したものとなり、かつ、両者間が連接したものとなり、これらが処理要素に保持されて処理される。この処理要素で、処理結果が第1オペランドパケットと第2オペランドパケットとの2個になるとすると、処理結果を上述のように圧縮して1パケット化することにより、後流側でのパケットの混雑を避けるとともに、パケットに割り込みが生じないようにすることができる。
【0199】
分流路20A上の9連接ライトパケットに関しても、リードデータパケットの場合と同様にして、フリップフロップが'1'のノードを通ってデータパケットを転送させる。この場合、分流ノードでは連接パケットへの割り込みが生じないので、その状態制御回路は上記合流ノードのそれよりも簡単になる。なお、ライトパケットに関しては、パケット間の演算を行わないので、連接ビットを用いずに、図22(B)の下位11ビットを32ビットに変更し、パケット単位でライト処理を行うようにしてもよい。
【実施例12】
【0200】
連接パケットに関しては、上記構成により連接パケット内でその順序が保たれる。
【0201】
しかしながら、シングルパケット同士、連接パケット同士及びシングルパケットと連接パケットとの間では、先着優先であるので、同一系統であっても場所によるパケットの混み具合により、合流路の出力ノードでのパケット順序が分流路の入力ノードでのパケット順序と同一になるとは限らない。異なる系統間では、分流路の入り口ノード及び合流路の出口ノードでパケットの系統値がノード位置で定まるので、パケット順序は問題とならない。
【0202】
次に、同一系統内でパケット順序が保たれている場合を、本発明の実施例12として説明する。
【0203】
図26(A)〜(C)及び図27(A)、(B)において、○印はパケットを示し、○印内の符号はパケットIDを示し、矢印はパケットの進む方向を示している。同じ符号のパケットは、同一パケットではなく、互いに対応していることを示している。パケットIDは、例えば処理対象のストリームIDである。簡単化のため、これらの図では1系統のみを示している。
【0204】
データ駆動型処理回路では、一般に上述のように、互いに異なる処理対象のパケットを同一ループ内の各パイプラインステージで分散並列処理することができる。
【0205】
図26(A)に示すように、ループ100上の部分101で処理PR1を行い、次いでループ100上の部分102で処理PR2を行う場合を考える。ループ101は、例えば図28に示すような構成の1系統分を含んでいてもよい。
【0206】
処理PR1の結果を処理PR2で用い又は処理PR2の結果を処理PR1で用いる場合に、図26(B)に示すように、ループ100を処理PR1のループ101Aと処理PR2のループ102Bとに分割し、これらを結合ノード103で結合し、結合ノード103で、対応するパケット同士を待ち合わせて少なくとも一方から他方へ情報を伝達することにより、処理PR1とPR2とで、少なくとも一方の処理結果を他方で利用する。
【0207】
これにより、図26(A)の1直列処理が2並列処理となり、ループのパイプライン段数が低減するので、結合ノード103での待ち合わせ時間が短ければ、スループットが向上する。
【0208】
例えばループ101A上のパケット6が結合ノード103にラッチされたとき、これに対応したループ102A上のパケット6が直ぐに結合ノード103に到達すれば、その結果を受け取って次のノードへ直ぐに移動できる。
【0209】
しかし、例えばループ101A上のパケット5がパケット6を追い越し、これが、対応するループ102A上のパケット5と待ち合わせてその結果を取得し、結合ノード103から離れた後に、ループ101A上のパケット6が結合ノード103でラッチされると、ループ102A上のパケット6は結合ノード103を通過した後なので、その結果を用いることができなくなる。
【0210】
これを避けるためにパケットを一時記憶させてそこからパケットの内容を取得するようにすると、処理が遅延するとともに、順次比較によりIDが一致するパケットを検索しなければならないので、構成が複雑になるとともに処理時間が長くなり、2並列化の意味がなくなる。
【0211】
もし、パケットの順番が保たれれば、結合ノード103で相手パケットのIDを確認することなく、それぞれが対応するパケットの処理結果を用いることができ、スループットが向上するとともに、パケットのデータ幅を短縮して回路規模を縮小することができ、さらに、コンポーネント化が可能となるので、システムの構築が容易となる。
【0212】
ループ102A上のパケットは、加工されない定数であってもよい。すなわち、ループ102Aはリングキュー(循環キュー)であってもよい。
【0213】
例えば、ループ101A上に第1パケットを投入し、ループ102A上に該第1パケットと関係した第2パケットを投入し、結合ノード103は、ループ101Aでのパケットに含まれるコマンド又は特定ビットが結合ノード103からの出力(分岐方向が出力側)を示している場合、これに対応してループ102Aからパケットを取り出すことにより、ループ101Aでの第1パケットに対応した処理結果のパケットとともに第2パケットを取り出す。これにより、ループ101A上で常に第2パケットを同伴させる必要が無く、構成が簡単になる。
【0214】
また、ループ102Aがリングキューである場合、ループ101Aはループ102Aをスタックとして用いることができる。ループ101Aと対応するループ102A上のパケットが複数あっても、その個数nをループ101A上のパケットに含ませておき、結合ノード103において、ループ102A側のSEND−INがアクティブになったときにループ102A側のACK−OUTをアクティブにし、ループ101A側のACK−OUTをインアクティブに維持した状態でこれをn回繰り返すことにより、対応関係を保つことができる。
【0215】
すなわち、ループ101Aのパケットが個数nの情報を含み、このパケットを1個転送させるとともにループ102Aのパケットをn個転送させることにより、ループ101Aの1パケットをループ102Aのnパケットと対応させる。結合ノード103は、ループ101Aのパケットのコマンド又は特定ビットが、このパケットの全部又は一部(処理結果)をコピーしてループ102Aへ投入することを示している場合、これを実行してループ101Aの該パケットに含まれる個数nをインクリメント(これは他のノードで行ってもよい)する。
【0216】
前記の場合において、もし順序同期をとることができなければ、ループ102Aを設けることができず、ループ101A上のパケットは、対応するパケットをループ101A上で連接させて引き連れていかなければならず、スループットが低下するとともに、ループ101Aの構成及び処理が複雑になる。
【0217】
順序同期は、条件によっては全てのパケットについてとる必要はない。このような場合、図22に示すように、順序制御用の順序ビットODをパケットに備え、これが'1'のとき順序制御有り、'0'のとき無しと定める。そして、結合ノード103においてループ102A上の対応するパケットを待つ際に、順序ビットODが'0'であればループ102A側のSEND−INがアクティブのときにループ102A側のACK−OUTをアクティブにしてこれを通過させることにより、ループ102A上に順序制御不要なパケットを混在させることができる。ループ101A上についても同様である。
【0218】
図26及び26中のパケットA〜Dは、順序ビットODが'0'のものであり、その他のパケット1〜6は順序ビットODが'1'のものを示している。
【0219】
なお、ループ間でパケットの対応がとれればよいので、ループ101Aへの初期パケットの投入とループ101Bへの初期パケットの投入は、異なるノードで行ってもよい。
【0220】
また、ループ101A及び102Aは、条件分岐ノードを備え、パケットが含むコマンド又は特定ビットの値に応じてこのパケットの情報がループから外部へ取り出される。
【0221】
図26(C)は、より複雑な関係のループを示す。
【0222】
この例では、ループ101Aと101Bとが結合ノード103Aで結合され、条件に応じて、ループ101A上のパケットがループ101B上へ移動したり、その逆が行われたりするとする。同様に、ループ102Aと102Bとが結合ノード103Aで結合され、条件に応じて、ループ102A上のパケットがループ102B上へ移動したり、その逆が行われたりするとする。また、同じ符号のパケットは同時に存在し得ず、ある時点ではどちらか一方のループに存在するとする。さらに、パケット1〜3はそれぞれパケット4〜6に対応しているとする。
【0223】
このような複雑な場合でも、例えばループ101A上のパケット3が結合ノード103Aを通ってループ101B上へ移動する際に、結合ノード103Aにおいてこれに対応するパケット6をループ102A上から102B上へ上記同様の制御により移動させてパケット順序の同期を取ることにより、上述の利点を得ることができる。
【0224】
待ち合わせ時間を短縮して順序同期の処理速度を速めるには、図27(A)に示すように、ループ102Aと102Bとの間を、キュー104及び105を介して結合させ、処理結果のパケットを順次キューに格納し相手方が直ぐにこれから取り出せるようにすればよい。順序同期は、順序が予測できるので、予め処理結果をキューに入れておくことにより、処理結果を直ちに使用することが可能となる。
【0225】
上述のようにループを分割することは、ハードウェアのコンポーネント化のみならず、階層構造化をも可能にする。すなわち、図27(B)に示すように、上述のキュー104及び105を上階層のループ106で処理すれば、階層構造となる。この例では、上階層のループ106での処理結果がキュー107及び108を介してそれぞれ下階層のループ101A及び102Aにフィードバックされている。
【0226】
以上のことは、各系統について成立するので、複数系統のそれぞれについて適用することができる。
【0227】
なお、ループ処理は効率がよいが、ループを1回通る場合でも順序同期を適用できるので、処理はループでなくてもよい。
【0228】
従来のデータ駆動型処理装置では、ローカルに同期を取って自律分散処理を行うことができるが、同期回路のシステムクロックに対応するものが存在しなかったので、自律分散処理に優れていても協調性が欠け、マイナーな存在であった。非同期回路において、パケットの順序を維持してループ間で順序同期をとることは、同期回路においてシステムクロックで同期をとることに対応している。
【0229】
マクロのネットワークでの非同期通信では、通信路でのパケット順序を維持できなくても同期型のCPU及び記憶装置と、ソフトウェアとの組み合わせによる高級機能により、TCP層で順序を復元でき、パケット順序とは直接関係なく高級機能で自律分散協調制御を行うことが出来る。これに対し、内部でミクロのネットワークが構成されるデータ駆動型処理装置では、パケットの順序維持が協調制御の基本となる。
【0230】
本発明の順序同期は、自律分散による並列処理を維持しつつ簡単な構成で協調制御を可能にしデータ駆動型処理装置を高機能化するのに寄与するところが大きい。
【実施例13】
【0231】
順序同期を実現するには、ループ状通信路でパケットの順序を同一系統内で維持する必要がある。パケットの順序を維持させるために順序合流を行わせる構成例を、本発明の実施例13として説明する。
【0232】
分岐ノードでパケットが混雑していない方向へ分岐して先回りしても、同一系統ではその後、合流する。同一系統内でのパケットの順序の乱れは、選択的に合流するノードでのパケット追い越し、すなわち分岐ノードでのパケット順序が、これに対応した合流ノードでのパケット順序と相違することにより生ずる。
【0233】
この相違が何に対応するかを調べるため、分岐ノードとこれに対応する合流ノードでのパケット進行方向に着目する。例えば図28の合流路40BP上のノード433Pを通過するパケットは、その前に、これに対応する分流路20A上のノード243を通過している。パケットがノード243から次の段のどちらへ進むかで、パケットがノード433Pの後段のどちらからノード433Pに進むかが定まるという規則性がある。図28ではこの関係がレジスタファイル30Rに関し対称になるが、必ずしもこれに限定されず、論理的な対応関係があればよい。
【0234】
簡単化のため、リードデータパケットが1ワードの場合のリードパケットとこれに対応するリードデータパケットを考える。パケットの順序が保たれていれば、ノード243を順次通過するパケットのノード243での分岐方向の順序と、ノード433Pを順次通過するパケットのノード433Pでの分岐方向の順序とが対応する。
【0235】
もし、全ての系統について、パケット順序が維持されていれば、合流路40BP上の任意の合流ノードとこれに対応する分流路20A上の分岐ノード(ノードペア)とについて、この対応関係が成立する。もし、2つのパケット間の順序に乱れがあれば、いずれかのノードペアで該対応関係が不成立となる。
【0236】
そこで、全てのノードペアについて、この対応関係を維持するように、合流路40BP上のノードの切換を、これに対応する分流路20A上のノードの切換情報(N段前の時点での切換情報)に基づいて制御することにより、パケット順序を維持する。但し、分流路20Aの出口ノードと合流路40BPの入口ノードについては、N=0であって、対応関係が既に維持されている。図28の場合、Nは2、4、6、8及び10である。
【0237】
図28において、例えば、ノード243を上側及び下側へ進むパケットの軌跡をそれぞれT1及びT2とする。軌跡T1のパケットが先にノード243に保持され、次に軌跡T2のパケットがノード243に保持されるとする。軌跡T1上でパケットが混雑し、軌跡T2上でパケットがすいていて、ノード433Pの後段には軌跡T2のパケットの方が先に到達したとする。この場合、ノード243で上側に切り替えたという情報がノード433Pへ伝達され、ノード433Pで上側からのパケットを待ち、これがノード433Pに保持された後に、ノード243で下側に切り替えたという情報がノード433へ伝達され、次にノード433Pで下側からのパケットを待つようにすれば、パケットの順序が維持される。全てのノードペアについて、このような制御を行えば、少なくとも同一系統内でパケットの順序が維持される。
【0238】
図29(A)は、この順序を維持させるための合流路40BPの入口ノードを除く任意のノード110と、これに対応する分流路20A上のノード111との間に備えられた構成を示す。図30は図29(A)の詳細ブロック図である。
【0239】
図29(A)ではノード110とノード111との間でパケットが流れ得る流路を分岐合流ノード112と表す。
【0240】
この構成では、ノード110と111との間にキュー113が備えられ、OD='1'であれば、ノード111からの分岐先方向を示す、行先アドレスDAの対応するビットDAi(図において上側分岐のとき'1'、下側分岐のとき'0')が、キュー113の入力段113aの1ビットラッチのデータ入力端に供給される。データ駆動型のキュー113は、転送制御回路で用いられるハンドシェイクプロトコルにより、途中にエンプティが存在すると自動的に詰められるという緩衝作用があるので、その段数は、ノード111とノード110との間のパイプライン段数N以上であればよい。キュー113の出力段から順次データを取り出せばよく、取り出す際に段数Nを考慮する必要はない。
【0241】
ノード110とその後段115及び116との構成は、図4の対応する構成と実質的に同一である。すなわち、ノード110はラッチ110Lの入力側にマルチプレクサ110Mが接続されているが、これは図4のラッチ421L及び422L内の出力側のゲートと出力イネーブル制御入力端OEとの構成に対応している。図4との相違点は、図30ではマルチプレクサ110Mの選択制御をキュー113の出力段113bのラッチ出力SELで行っている点である。
【0242】
ノード111とその次段117及び118との構成は、図3の対応する構成と、ノード111の転送制御回路111Cを除き同一である。ノード111の転送制御回路111Cはキュー113の入力段113aの転送制御回路との間についても信号授受を行っている点で、転送制御回路211Cと異なる。
【0243】
なお、図30の分岐合流回路112Aは、図29(A)の分岐合流回路112からノード115〜118を除いた部分である。
【0244】
ノード111から次段ノード117又は118へのSENDをアクティブにするときに、同時にキュー113の入力段113aへのSENDをアクティブにする。すなわち、ノード111の転送制御回路111Cは、次段117又は118及び入力段113aからのACKが共にアクティブであり且つ後段からのSENDがアクティブであるときに次段117又は118及び入力段113aへのSENDをアクティブにする。
【0245】
ノード110は、2入力のうち、キュー113の出力段113bの出力に基づいて、ノード110の後段115及び116のラッチ出力の一方を選択する。すなわち、キュー113の出力段113bの出力SELが'1'であれば、ノード110の後段上側のノード115からのデータを選択し、'0'であれば、ノード110の後段下側のノード116からのデータを選択する。この選択は、キュー110の出力段113bのラッチ出力SELによりノード110のマルチプレクサ110Mを選択制御することにより行われる。
【0246】
ノード110は、その後段115又は116へのACKをアクティブにするときに、キュー113の出力段113bに対するACKをアクティブにする。すなわち、ノード110は、ノード110の後段115又は116及びキュー113の出力段113bからのSENDが共にアクティブになり且つノード110の次段からのACKがアクティブになったときに、ノード110のラッチ110Lにデータを取り込ませて保持させ、キュー113の出力段113b及びノード110の後段115又は116へのACKを共にアクティブにする。
【0247】
図29(B)及び図30において、DAi='1'のとき、ノード111は、ノード117へパケットを分岐転送させる(この分岐が第1段)とともにキュー113の入力段113aにDAi='1'を転送させる。N段経過後に、一方ではこれに対応するパケットがノード115に保持され、他方ではマルチプレクサ110Mの選択制御入力端に、前記DAi='1'に対応したSEL='1'が供給されて、ノード110はノード115側を選択する。図29(C)においても同様である。
【0248】
ここで、ライトパケットについては、レジスタファイル30Rへの書き込みが終了し、合流路40A側へ対応するパケットが転送されないので、このパケットの順序ビットODを'0'にしておく。転送制御回路111Cは、ノード111のラッチ111Lに保持した順序ビットODが'0'であるとき、キューの入力段113へのSENDをインアクティブに維持する。これによりキュー113の入力段113aのラッチにはビットDAiが転送されないので、順序維持の切り替えとは無関係になる。
【0249】
一方、リードパケットのように分流路20A側の1パケットが合流路40BP側の複数パケットに対応する場合、キュー113においてもこの対応関係を維持する必要がある。この対応関係を維持するために、ノード110の転送制御回路110Cは、連接ビットCNが'1'のときは例外として、キュー113の出力段113bへのACKをインアクティブに維持する。これにより、連接パケットについてもノード110とノード111とで切り替えの対応関係を保つことができる。連接パケットの末尾パケットは連接ビットCNが'0'であるが、その1つ前のパケットの連接ビットCNが'1'であるので、図31(J)に示すように、末尾パケットに対してもノード110の選択方向は変わらない。
【0250】
図31(A)〜(J)は、分流路20A側の1つのリードパケットの流れと、これに対応した合流路40BP側の複数のリードデータパケット(連接パケット)の流れとを、時間を追って示す。図中の'1'は、上述のノード側フリップフロップの値を示す。図31(A)は4段分のデータ転送を纏めて示している。
【0251】
(1)図31(A)で、DAi='1'であればノード111から次段上側('1'側)117へデータが転送されると共に、OD='1'であれば行先アドレスDAiの値がキュー113の入力段113aに転送される。
【0252】
(2)図31(E)で、連接先頭パケットがノード110の後段上側115に取り込まれて保持されるとともに、(1)で保持したDAi='1'がキュー113の出力段113bに取り込まれて保持され、ノード110のマルチプレクサ110Mはその選択制御入力端への'1'に応答して、ノード110の後段上側115のノードからのデータを選択する。
【0253】
(3)これにより、図31(F)で、ノード110はこのデータを取り込み保持する。
【0254】
(4)その後、ノード110が保持しているパケットの連接ビットCNの値が'1'の間、ノード110の転送制御回路110Cからキュー113へのACKがインアクティブに維持されて、キュー113の出力段113bの出力SEL='1'が維持され、ノード115(図29)から連接パケットが順次ノード110へ到達する。
【0255】
このようにして、分流路20Aの任意のノードから、合流路40BPの対応するノードへ、順序制御情報DAi→SELが伝達され、これに応じ合流ノードでの選択制御が行われ、これにより全ての系統についてパケットの順序が維持される。
【0256】
したがって、この構成によれば、図26及び図27で述べた構成を実現して、その効果を達成することができる。
【0257】
なお、順序ビットODは、図26及び図27について説明した順序ビットODとしても使用できる。
【0258】
また、本発明の順序合流制御が行われるノード110とノード111との対は、ツリー形分流路とツリー形合流路の対応するノード対に限定されず、第1パケットが分岐ノードを通れば、該第1パケットに対応した第2パケットが合流ノードを通り、且つ、該分岐ノードでの該第1パケットの分岐方向と該合流ノードでの該第2パケットの合流方向とが対応しており、該分岐ノードと該合流ノードとの間のパイプライン段数がN(N≧1)であるという条件を満たす分岐ノードと合流ノードの対であればよい。
【0259】
さらに、ノード110を通るパケットはノード111を通るパケットと対応しているが、この対応関係は、両者が同一パケットであってもよい。
【実施例14】
【0260】
次に、本発明のデータ駆動型処理装置の適用例として、有限オートマトン動作を行うCPUアクセラレータについて説明する。
【0261】
有限オートマトンは、言語学、情報工学、生物学、数学、論理学など様々な領域で利用されている。有限オートマトンでは、現在状態と入力とにより、次状態が定まり、この状態遷移が繰り返し行われてパターン一致有無が判定される。
【0262】
図37は、簡単な有限オートマトンの例を示す状態遷移図である。
【0263】
この例では、データストリームDS="CAABABABCCCCBBABACC"の中に、検索データ集合RDのパターン"ABA"又は"ABC"が含まれているか否かを決定する。現在の状態にデータストリームDS中のエレメント"A"、"B"又は"C"が入力されると、次の状態が定まり、これに次のエレメントが入力されるという処理が繰り返し行われ、出力時の状態が検出パターンに対応している。エレメントは文字コードに限定されず、所定のデータ幅のデータであればよい。
【0264】
ウイルス検出の例で言うと、検索データ集合RDに含まれるパターンのそれぞれがウイルスに対応している。入力データストリームDSが多数のウイルスのどれに感染しているかのパターンマッチング処理を、1つの状態遷移図で表すことができる(パターンマルチング)。
【0265】
以下では、有限オートマトンをウイルス検出に適用した場合について説明するが、本発明のCPUアクセラレータはこれに限定されるものではなく、全ての有限オートマトンに適用可能である。
【0266】
本発明の装置では、並列度が高いので、同時に多数の入力データストリームDSを取り扱うことができる。
【0267】
図32は、行を状態S、入力である列を、データストリームを構成する1バイトのストリームエレメントSEとした状態遷移テーブルを示す。但し、この状態遷移テーブルには、1ビットの結果ビットRが含まれている。
【0268】
状態Sを上位ビット、ストリームエレメントSEを下位ビットとするアドレスに、次の状態が格納されたメモリを用いる。16進数表記で、例えば状態Sの初期値を"0000"とし、ストリームエレメントSEが"01"であった場合、次の状態Sは"0002"となる。これと次のストリームエレメントSEとで、次の状態Sが定まる。
【0269】
結果ビットRは1ビットであり、ウイルスパターンが検出されたとき、R='1'となる。このときの状態Sで指定されるアドレスには、次の状態はなく、ウイルスコードVCが格納されている。ウイルスコードVCに対応したウイルス名は、CPUに管理させる。結果ビットRは、パケット内のコマンドの役割を果たす。
【0270】
図33は、本発明が適用された、実施例14のデータ駆動型CPUアクセラレータ60Qを示す概略ブロック図である。
【0271】
状態テーブルメモリ120は、例えば図8のメモリ10Bの記憶容量を大きくしたものであり、その分流路121、メモリ行アレイ122及び合流路123はそれぞれ、図8の分流路20B、メモリ行アレイ30及び合流路40Bに対応している。リードパケットに対するリードデータパケットは後述のように1ワードであり、これらのフォーマットは上述のものと異なる。メモリ行アレイ122には、図32のテーブルが格納されている。
【0272】
図35は、図33の装置における1系統に関するデータフローをデータフォーマットとともに示す図である。
【0273】
系統CHは、上述のように合流路123で用いられる定数である。結果ビットR及び状態Sは、状態テーブルメモリ120から読み出されたデータであり、これと、下位ビットとしてのストリームエレメントSEとで、状態テーブルメモリ120のアドレスが指定される。各系統で複数のデータストリームを処理することができ、そのストリーム識別子SIDをこの例では3ビットとしている。ストリーム識別子SID及び系統CHは、状態テーブルメモリ120を含むループで、同一ストリームに対し不変である。
【0274】
図33に戻って、複数のデータストリームは、DMACにより、インターフェイス124及びメモリコントローラ125を介し、バッファとしてのRAM126に一時格納された後、CPU127によりインターフェイス124及びメモリコントローラ125を介してRAM126の内容が読み出され、メモリコントローラ125、インターフェイス124及び128並びにストリームバッファ130の分流路131を介しキューアレイ132に供給され保持される。CPU127、RAM126、メモリコントローラ125及びインターフェイス128は同期型であり、インターフェイス128は、同期型と非同期型との相互変換部を備えている。
【0275】
図34は、図33中のストリームバッファ130の概略ブロック図である。
【0276】
このストリームバッファ130の分流路131及び合流路(マルチプレクサ)1330〜1333はそれぞれ、図1の分流路20の第3〜5段を抽出したもの及び合流路40の第2〜4段を抽出したものと同一である。分流路131は、インターフェイス124の端子数を少なくするためのものであり、この例では4組としているが、1組以上であればよい。
【0277】
分流路131に供給されるパケットのフォーマットは、図35に示す如く、3ビットのストリーム識別子SIDのフィールドと、8ビットのストリームエレメントSEのフィールドとからなる。
【0278】
ストリーム識別子SIDは、4系統×8本のキューアレイ132の8本のキューIDと対応づけられている。このようなキューIDをストリーム識別子SIDと対応させることにより、分流路131で行先アドレス5ビットの下位3ビットとして用いられたストリーム識別子SIDは、分流路131を出ると不要となり、キューアレイ132では8ビットのストリームエレメントSEのみ保持される。マルチプレクサ1330〜1333はそれぞれ系統0〜3の8本のキューの1つを選択して、それぞれノード140〜143に供給する。この選択は、分流路121へ転送しようとするパケットに含まれるストリーム識別子SIDであるSID0〜SID3をそれぞれデコーダ145〜148でデコードした制御信号により行われる。
【0279】
マルチプレクサ1330〜1333は、通常の構成を用いることができるが、図34に示すように8入力1出力の合流路を用いてもよい。この場合、ストリーム識別子SIDをデコードして、8本のキューのうちの対応する1つのキューの出力段に対してのみACKをアクティブにすればよい。この場合のデコーダは、1入力8出力の分流路を用いることができる。
【0280】
キューアレイ132を構成する各キューについて、半空になったときには、これを半空検出回路134で検出し、そのキューの系統CHとストリーム識別子SIDとを伴って、インターフェイス128及び124を介したCPU127への割込要求IRQ2をアクティブにする。これによりCPU127は、RAM126からデータを読み出して、対応する系統CH及びストリーム識別子SIDのキューにこれを補給する。RAM126からインターフェイス124にはDMA転送することができる。
【0281】
半空検出は例えば、設定時間内におけるキューアレイ132の先頭でのSEND−OUTパルス数と中間部でのそれとの差が所定値以上となったことにより検出することができる。またキューアレイ132のそれぞれのキューについて、出力されるパケット数(ラッチパルス数)と供給されるパケット数(ラッチパルス数)とをカウントし、その差が設定値以上になったとき、同様に割込要求IRQ2をアクティブにする構成であってもよい。半空でなく、キューの所定割合が空になったことを検出してもよいことは勿論である。
【0282】
ノード150〜153のパケットは、結果ビットRを含む必要がない。合成ノード140〜143にはそれぞれ、一方ではノード150〜153からパケットが供給され、これらのストリーム識別子SIDがそれぞれSID0〜SID3としてマルチプレクサ1330〜1333に対する選択制御信号として供給され、他方ではマルチプレクサ1330〜1333からのストリームエレメントSEが合成ノード140〜143に付加されて合成され、合成ノード140〜143に取り込まれ保持される。
【0283】
合成ノード140〜143の出力が分流路121に転送される。合成ノード140〜143を省略し、これらの替わりに分流路121の入口ノードを用いてもよい。
【0284】
ノード150〜153には、CPU127からインターフェイス124及び128を介した初期パケットと、合流路123からのパケットとが選択的に合流する。この初期パケットは、CPUアクセラレータ60Qを起動させるためのものであり、図35において、例えばS=0、R=0とし、系統CH及びストリーム識別子SIDをそれぞれの系統ごとに与えたものである。
【0285】
ストリーム識別子SIDの値は、CPU127がインターフェイス124、128及び分流路131を介しキューアレイ132にデータストリームを供給したものであればよく、CPU127が定めることができる。
【0286】
CPU127は、ノード150〜153のそれぞれに1つ又は複数の初期パケットを順次供給する。CPU127はこの際、合流路123の対応する出口ノードに対するACKをインアクティブにして、出口ノードからのパケットの流れを停止させておく。次いでこの停止を解除すると、状態テーブルメモリ120を含むループ内でパケットがパイプライン処理される。各系統の初期パケットは、本実施例では最大8個である。実際には、ループ内にパケットを分散させることができるので、その最大値は状態テーブルメモリ120の全段数に2を加えたものとすることができる。
【0287】
状態テーブルメモリ120の合流路123の各系統の出口ノードの出力は、出力回路160に供給される。
【0288】
出力回路160は、4系統の結果ビットRのいずれかが'1'となると、その系統CH、ストリーム識別子SID及びウイルスコードVCを取り込んで保持し、CPU127に対し、これらを供給するとともに割込要求IRQ1をアクティブにする。各データストリームについて、1つのウイルスを検出すればそのストリームに対する処理を打ち切ることができる。この場合、ストリームバッファ130内の、ウイルスが検出されたストリームをフラッシュし又は/及びこのストリームの追加を停止し、未処理ストリームがあればストリームバッファ130へ他のストリームを供給し、これに対応して初期パケットを、上述のように供給し、該他のストリームに対する処理を開始する。
【0289】
本実施例14によれば、CPUアクセラレータ60Qがデータ駆動型で構成されており、さらに状態テーブルメモリ120とストリームバッファ130とが並列動作するので、処理の並列度が高くてスループットが高いとともに、低消費電力であり、各種モバイル機器に好適である。
【実施例15】
【0290】
図36は、本発明が適用された、実施例15の順序同期・データ駆動型CPUアクセラレータ60QAを示す概略ブロック図である。
【0291】
このCPUアクセラレータ60QAではまず、ストリームバッファ130Aの分流路131Aを、図1の6段分流路20を5段にしたもので構成するとともに、インターフェイス128Aから、一方では分岐ノード163を介して分流路131Aへデータストリームを転送させ、他方では分岐ノード161及びデマルチプレクサ(分流路)162を介して初期パケットをノード150〜153へ供給することにより、インターフェイス128Aの出力端子数を低減している。
【0292】
ノード161でのパケットは、初期パケットであるか否かを示すビット及び系統CHを有し、前者でノード161でのパケット分岐先が定まる。デマルチプレクサ162では、系統CHが行先アドレスとして用いられ、これはその出力ノードで不要となる。
【0293】
次に、ストリームバッファ130Aのそれぞれのキューが順序を維持しているので、このCPUアクセラレータ60QAでは、上述の順序合流制御が行われる分流路121A及び合流路123Aを備えた状態テーブルメモリ120Aを用いて、状態テーブルメモリ120Aでのパケット順序を維持させることにより、状態テーブルメモリ120Aとストリームバッファ130Aとの間で順序同期をとっている。
【0294】
状態テーブルメモリ120Aから出力されるパケットの順序が維持されるので、マルチプレクサ1330〜1333に対する選択制御を確実に予測することができる。この順序は、CPU127がインターフェイス124、128、ノード161及びデマルチプレクサ162を介しノード150〜153へ供給する初期パケットの順序により定まる。すなわち、順序はCPU127が決定することになる。
【0295】
ストリームID予測回路163は、系統CH毎に不図示のリングキューを備えており、系統CH毎に、ノード161からのパケット内のストリーム識別子SIDを順次このリングキューに保持し、その出力に基づき、マルチプレクサ1330〜1333へそれぞれストリーム識別子SID0〜SID3を供給するとともに該リングキュー内のパケットを1段進ませ、キュー170〜173の先頭からのACKがアクティブになる毎にこれを繰り返すことにより、予めキュー170〜173へストリームエレメントSEを複数取り込ませ保持させる。
【0296】
合成ノード140〜143は、ノード150〜153へのACKをアクティブにするとき、同時に、対応するキュー170〜173の出力段へのACKをアクティブにする。
【0297】
このようにして、パケットが状態テーブルメモリ120Aからノード150〜153を介しそれぞれ合成ノード140〜143へ到達したときに、キュー170〜173からのパケットをこれと同時に合成ノード140〜143へ到達させることが可能となり、合成ノード140〜143での待ち合わせのタイムラグがなくなるので、上記実施例14よりも高速処理を行うことができる。
【0298】
なお、順序同期により合成ノード140〜143では、合成されるそれぞれのパケットのストリームIDが一致するので、状態テーブルメモリ120を含むループ内では、ストリームIDをパケットに含ませなくてもよい。
【0299】
この場合、出力回路160でウイルスを検出した際にストリーム識別子SIDを出力する必要があるので、SID予測回路163と同様に系統CH毎にリングキューを出力回路160に備えてこれにストリームIDを保持させ、合流路123Aの出口ノードからのSENDパルスで、対応するリングキュー内の所定段に対するACKをアクティブにして該所定段でパケットを1個進ませ、合流路123Aの出口ノードから出力されているパケットのストリームIDを識別する。
【0300】
また、SID予測回路163でのリングキューと、マルチプレクサ1330から合流路123Aの出口ノードまでのパイプライン段数と、出口ノードからのSENDパルスの数とから、該出口ノードから出力されているパケットのストリームIDを識別することもできる。
【0301】
さらに、CPUアクセラレータ以外の有限オートマトン装置として用いてもよい。
【0302】
また、本発明の特徴の1つが予測回路を用いている点であることに着目すれば、本発明は、状態テーブルメモリ120Aを含むループを、他の機能のループに置換した構成であってもよい。
【0303】
なお、本発明には外にも種々の変形例が含まれる。
【0304】
例えば、上記各実施例又はその変形例の構成要素の組み合わせを変えた構成も、その機能を達成できるものは本発明に含まれる。
【0305】
また、分流路の行先アドレスをプロセッサの命令コードとし、分流路の出力側でこの命令コードに応じた処理手段を配置した構成であってもよい。この場合、レジスタファイル30Rの各行をその命令コードに応じたレジスタ群として用いるこのができる。
【0306】
さらに、ストリームバッファ130又は130Aは、その中でのデータ流を逆流させて、他のループコンポーネントでの処理結果を分類してCPU等へ出力するのに用いることができる。
【図面の簡単な説明】
【0307】
【図1】本発明の実施例1の非同期(自己タイミング)データ駆動型メモリを示す概略ブロック図である。
【図2】メモリ行アレイの配列の具体例を示す図である。
【図3】束データ方式で分流路を構成した場合の第1段と第2段とで構成される分流回路を示す概略ブロック図である。
【図4】束データ方式で合流路を構成した場合の第2段と第3段の一部である合流回路を示す概略ブロック図である。
【図5】図1の分流路20の出力ノード261と合流路40の入口ノード411との間に接続されたメモリ行31及び32を示す概略ブロック図である。
【図6】本発明の実施例2のデータ駆動型メモリを示す概略ブロック図である。
【図7】(A)はパケットのフォーマットを示し、(B)は系統とパケットフローの関係を示す説明図である。
【図8】入力ポート及び出力ポートの数を実施例2の場合の2倍にした、本発明の実施例3のメモリを示す概略ブロック図である。
【図9】パケットのフォーマットを示す図である。
【図10】パイプライン段数を低減した、本発明の実施例4のメモリを示す概略ブロック図である。
【図11】選択的合流ノードへの転送待ちを短縮した、本発明の実施例5の2ポート入力・2ポート出力型のメモリを示す概略ブロック図である。
【図12】入力ポート及び出力ポートの数を実施例5の場合の2倍にした、本発明の実施例6のメモリを示す概略ブロック図である。
【図13】本発明の実施例7のキャッシュメモリを示す概略ブロック図である。
【図14】タグアレイ内の隣り合うタグ行の構成を示す概略ブロック図である。
【図15】インターフェイスで待機中の更新パケットが、ワードデータを受け取ってそのデータフィールドに書き込みパッケット化する動作の説明図である。
【図16】本発明の実施例8のキャッシュメモリを示す概略ブロック図である。
【図17】本発明の実施例9の、プロセッサの一部であるデータ処理部を示す概略ブロック図である。
【図18】(A)及び(B)は、パケットペアを分流路入口ノードに投入した後の処理の流れを示す概略説明図である。
【図19】本発明の実施例10の、プロセッサの一部であるデータ処理部を示す概略ブロック図である。
【図20】(A)はパケットペア行先アドレスに基づいて合流段IDを決定する方法の説明図、(B)はパケットフォーマットを示す説明図である。
【図21】合流段識別ノードの概略構成を示すブロック図である。
【図22】(A)〜(D)は本発明の実施例11に係るパケットフォーマット説明図であり、(A)はパケットペアを1パケットに圧縮したもののフォーマット、(B)及び(C)はこのパケットを2パケットに伸張させたもののフォーマット、(C)は連接パケットでの先頭に続くデータパケットを示す図である。
【図23】(A)及び(B)はそれぞれ第1オペランドの連接パケットの先頭パケット及びこれに続くデータパケットを示す説明図、(B)及び(C)はそれぞれ第2オペランドの連接パケットの先頭パケット及びこれに続くデータパケットを示す説明図である。
【図24】合流路のノードに備えられた連接ビットがパケットペアの連接ビットによりセットされている状態を示す説明図である。
【図25】ノードN1のノード側連接ビットF1に対する状態制御回路とこれに関連する要素を示すブロック図である。
【図26】(A)〜(C)は本発明の実施例12に係り、(A)はデータ駆動型処理ループを示し、(B)は(A)を2分割して並列結合した回路を示し、(C)は複雑な処理ループを並列結合した回路を示す概略図である。
【図27】(A)及び(B)はそれぞれ同層及び異層間において、順序同期が成立している並列処理ループ間でのキューを介した処理結果の伝達を示す図である。
【図28】本発明の実施例13に係る、合流路のノードとこれに対応する分流路のノードとの間で生ずる切替順序の乱れの説明図である。
【図29】(A)は合流路の任意のノードについて、これに対応する分流路のノードとの間で切替同期を行う構成を示し、(B)及び(C)はこの構成の動作を示す図である。
【図30】図29の(A)の詳細ブロック図である。
【図31】(A)〜(J)は、分流路側の1つのリードパケットの流れと、これに対応した合流路側の複数のリードデータパケット(連接パケット)との流れとを、時間を追って示す説明図である。
【図32】行を状態Sとし、入力である列を、データストリームを構成する1バイトのストリームエレメントSEとした出力コマンド付状態遷移テーブルを示す図である。
【図33】本発明の実施例14のCPUアクセラレータを示す概略ブロック図である。
【図34】図33中のストリームバッファの概略ブロック図である。
【図35】図33の装置における1系統に関するデータフローをデータフォーマットとともに示す図である。
【図36】本発明の実施例15の順序同期型CPUアクセラレータを示す概略ブロック図である。
【図37】簡単な有限オートマトンの例を示す状態遷移図である。
【符号の説明】
【0308】
10、10A〜10E、120、120A メモリ
10AP、10BP データ処理部
20、20A〜20E、71、121、131、131A 分流路
201C、211C、221C、222C、261C、411C、311C、312C、3131C、411C、421C、422C、431C、711C、731C 転送制御回路
201L、211L、221L、222L、261L、311L、312L、3131L、411L、421L、422L、431L、711L、731L ラッチ
110、111、115〜118、201〜204、221〜228、221A、222A、223A、224A、231〜234、231A、232A、241、248、251、261、411、411A、411B、421、431、441〜444、441A、451〜454、441A、442A、443A、444A、451A、452A、453A、454A、461A、461AP、462A、463A、464A、47、711、731、77、771〜774、82、N01、N02、N1、N2 ノード
201F 合流段ID決定部
201P パケットペア判定部
211〜214、411 入口ノード
222G、261G1、411G、422G インバータ
251、461〜464 出口ノード
261G2、3131G オアゲート
30、122 メモリ行アレイ
30R レジスタファイル
310、740 ループ配線
31、32 メモリ行
311、741 制御回路
311a、310C カウンタ
310W、311W、312W、313W、320W ワードメモリ
40、40A〜40E、40AP、40BP、73、123、123A 合流路
47 状態制御回路
50、50A〜50G、P1〜P3、P1A、P2A、P1N、P2N パケット
60、60A キャッシュメモリ
60Q、60QA CPUアクセラレータ
70、70A タグテーブル
72 タグアレイ
721、722 タグ行
750〜753、75i ページ情報
760〜763 コンパレータ
764 オアゲート
765 エンコーダ
766 マルチプレクサ
80、801〜804 入出力部
81、124、128、128A インターフェイス
100、101、101A、101B、102、102A、102B ループ
103、103A 結合ノード
104、105、113、170〜173 キュー
125 メモリコントローラ
126 RAM
127 CPU
130、130A ストリームバッファ
132 キューアレイ
1330〜1333 マルチプレクサ
134 半空検出回路
140〜143、150〜153 ノード
160 出力回路
163 ストリームID予測回路
162 デマルチプレクサ
CK クロック入力端
CK1、CK2 クロックパルス
OE 出力イネーブル制御入力端
CMD コマンド
ADR、ADR1、ADR2 アドレス
DA、DA1、DA2、DAi 行先アドレス
DA0〜DA5、CH0、CH1 ビット
PA、PA1、PA2 ページアドレス
WA、WX、WA1、WA2 ワードアドレス
DATA データ
CN 連接ビット
OD 順序ビット
HM、HM1、HM2 ヒットビット
CH 系統
PT パケットタイプ
TA、TAG タグアドレス
CNT カウンタ
MA 合流段識別子
PR1、PR2 処理
V バリッドビット
D ダーティビット
L ロックビット
R 結果ビット
VC ウイルスコード
S 状態
SE ストリームエレメント
SID、SID0〜SID3 ストリーム識別子
IRQ1、IRQ2 割込要求
DS 入力データストリーム
RD 検索データ集合
F01、F02、F1、F2 フリップフロップ

【特許請求の範囲】
【請求項1】
上位ビット及び下位ビットをそれぞれ状態及びデータストリーム要素とするアドレスに次状態が格納され、アドレスとデータストリーム識別子とを含むパケットが入力され、次状態と該データストリーム識別子とを含むパケットが出力されるデータ駆動型状態テーブルメモリと、
該状態テーブルメモリの出力を該状態テーブルメモリの入力にフィードバックさせる流路に介在され、データ入力端の第1部に供給されるデータを該データ入力端の第2部に供給される該次状態と合成する合成ノードと、
それぞれのキューにデータストリームが格納されるキュー列と、
該出力に含まれるデータストリーム識別子に基づき、該キュー列のキューを選択して、このキューの出力段を該第1部に結合させるマルチプレクサと、
を有することを特徴とする有限オートマトン装置。
【請求項2】
該フィードバック流路の、該状態テーブルメモリと該合成ノードとの間に、初期パケットと該次状態のパケットとを選択的に合流させる合流ノードをさらに有することを特徴とする請求項1に記載の有限オートマトン装置。
【請求項3】
該状態テーブルメモリには、パターン一致情報が含まれ、
該状態テーブルメモリの出力に含まれるパターン一致情報がパターン一致を示しているか否かを判定し、肯定判定した場合には該出力に含まれるデータストリーム識別子とともに割込要求信号を出力する出力回路をさらに有することを特徴とする請求項2に記載の有限オートマトン装置。
【請求項4】
該キュー列の各キューについて、空きが所定量を超えた場合には該キューに対応したデータストリーム識別子とともに割込要求信号を出力する空検出回路をさらに有することを特徴とする請求項3に記載の有限オートマトン装置。
【請求項5】
該マルチプレクサは、その入力が複数の入口ノードの入力であり、その出力が出口ノードの出力であるツリー形合流路を有することを特徴とする請求項4に記載の有限オートマトン装置。
【請求項6】
供給されるデータストリームを行先アドレスに基づき順次選択的に分流させて該キュー列の1つのキューに転送させるツリー形分流路をさらに有することを特徴とする請求項5に記載の有限オートマトン装置。
【請求項7】
外部から供給されるデータストリームを該ツリー形分流路に供給し、該出力回路及び該空検出回路の出力を外部に供給するインターフェイスをさらに有することを特徴とする請求項6に記載の有限オートマトン装置。
【請求項8】
該状態テーブルメモリには、該パターン一致情報がパターン一致を示しているとき、次状態の替わりにパターン識別子が格納されており、
該出力回路は、該肯定判定した場合には該パターン識別子も出力することを特徴とすることを特徴とする請求項3に記載の有限オートマトン装置。
【請求項9】
該データ駆動型状態テーブルメモリは、
記憶行アレイと、
入口ノードに供給される第1パケットを、該第1パケットが含む行先アドレスに応じ下流側のノードへ順次選択的に分流させて、該記憶行アレイ内の1つの記憶行へ転送させるツリー形分流路と、
該記憶行から読み出された第2パケットを、下流側へ順次選択的に合流させて出口ノードへ転送させるツリー形合流路と、
を有し、該記憶行は、該第1パケットが含む記憶行内アドレスで指定される該記憶行内の一部の記憶データを読み出して該第2パケットとし、
該ツリー形分流路及び該ツリー形合流路のパイプライン段数がそれぞれ3以上であることを特徴とする請求項1乃至8のいずれか1つに記載の有限オートマトン装置。
【請求項10】
上位ビット及び下位ビットをそれぞれ状態及びデータストリーム要素とするアドレスに次状態が格納され、アドレスを含むパケットが入力され、次状態を含むパケットが出力され、パケット順序が維持されるデータ駆動型状態テーブルメモリと、
該状態テーブルメモリの出力を該状態テーブルメモリの入力にフィードバックさせる流路に介在され、データ入力端の第1部に供給されるデータを該データ入力端の第2部に供給される該次状態と合成する合成ノードと、
該フィードバック流路の、該状態テーブルメモリと該合成ノードとの間に、初期パケットと該次状態のパケットとを選択的に合流させる合流ノードと、
それぞれの第1キューにデータストリームが格納されるキュー列と、
出力段を該第1部に結合させる第2キューと、
該合流ノードへの初期パケット投入順に基づき巡回する選択制御信号を順次生成する予測回路と、
該選択制御信号に応じ該キュー列の第1キューを選択して、この第1キューの出力段を該第2キューの入力段に結合させるマルチプレクサと、
を有することを特徴とする有限オートマトン装置。
【請求項11】
該状態テーブルメモリには、パターン一致情報が含まれ、
該状態テーブルメモリの出力に含まれるパターン一致情報がパターン一致を示しているか否かを判定し、肯定判定した場合には該出力に対応した、予測されるデータストリーム識別子とともに割込要求信号を出力する出力回路をさらに有することを特徴とする請求項10に記載の有限オートマトン装置。
【請求項12】
該キュー列の各第1キューについて、空きが所定量を超えた場合には該第1キューに対応したデータストリーム識別子とともに割込要求信号を出力する空検出回路をさらに有することを特徴とする請求項11に記載の有限オートマトン装置。
【請求項13】
該マルチプレクサは、その入力が複数の入口ノードの入力であり、その出力が出口ノードの出力であるツリー形合流路を有することを特徴とする請求項12に記載の有限オートマトン装置。
【請求項14】
供給されるデータストリームを行先アドレスに基づき順次選択的に分流させて該キュー列の1つのキューに転送させるツリー形分流路をさらに有することを特徴とする請求項13に記載の有限オートマトン装置。
【請求項15】
外部から供給されるデータストリームを該ツリー形分流路に供給し、該出力回路及び該空検出回路の出力を外部に供給するインターフェイスをさらに有することを特徴とする請求項14に記載の有限オートマトン装置。
【請求項16】
該状態テーブルメモリには、該パターン一致情報がパターン一致を示しているとき、次状態の替わりにパターン識別子が格納されており、
該出力回路は、該肯定判定した場合には該パターン識別子も出力することを特徴とすることを特徴とする請求項11に記載の有限オートマトン装置。
【請求項17】
該データ駆動型状態テーブルメモリは、
記憶行アレイと、
入口ノードに供給される第1パケットを、該第1パケットが含む行先アドレスに応じ下流側のノードへ順次選択的に分流させて、該記憶行アレイ内の1つの記憶行へ転送させるツリー形分流路と、
該記憶行から読み出された第2パケットを、下流側へ順次選択的に合流させて出口ノードへ転送させるツリー形合流路と、
を有し、該記憶行は、該第1パケットが含む記憶行内アドレスで指定される該記憶行内の一部の記憶データを読み出して該第2パケットとし、
該第1パケットは該状態テーブルメモリに入力されるパケットであり、該第2パケットは該状態テーブルメモリから出力されるパケットであり、該ツリー形分流路及び該ツリー形合流路のパイプライン段数がそれぞれ3以上であることを特徴とする請求項10乃至16のいずれか1つに記載の有限オートマトン装置。
【請求項18】
上位ビット及び下位ビットをそれぞれ状態及びデータストリーム要素とするアドレスに次状態及びパターン一致情報が格納され、アドレスとデータストリーム識別子とを含むパケットが入力され、次状態とパターン一致情報と該データストリーム識別子とを含むパケットが出力されるデータ駆動型状態テーブルメモリを用意し、
(a)該状態テーブルメモリの出力を該状態テーブルメモリの入力にフィードバックさせる流路において、データ入力端の第1部に供給されるデータを該データ入力端の第2部に供給される該次状態と合成させ、
(b)該フィードバック流路において該合成を行う前に、初期パケットと該次状態のパケットとを選択的に合流させ、
(c)キュー列のそれぞれのキューにデータストリームを格納させ、
(d)該データ駆動型状態テーブルメモリの出力に含まれるデータストリーム識別子に基づき、該キュー列のキューを選択させて、このキューの出力段を該第1部に結合させ、
(e)該状態テーブルメモリの出力に含まれるパターン一致情報がパターン一致を示しているか否かを判定させ、肯定判定した場合には該出力に含まれるデータストリーム識別子とともに割込要求信号を出力させる、
工程を有することを特徴とするパターンマッチング方法。
【請求項19】
(f)該キュー列の各キューについて、空きが所定量を超えた場合には該キューに対応したデータストリーム識別子とともに割込要求信号を出力させる、
工程をさらに有することを特徴とする請求項18に記載のパターンマッチング方法。
【請求項20】
上位ビット及び下位ビットをそれぞれ状態及びデータストリーム要素とするアドレスに次状態及びパターン一致情報が格納され、アドレスを含むパケットが入力され、次状態及びパターン一致情報を含むパケットが出力され、パケット順序が維持されるデータ駆動型状態テーブルメモリを用意し、
(a)該状態テーブルメモリの出力を該状態テーブルメモリの入力にフィードバックさせる流路において、第1キューの出力段から出力されるデータを該次状態と合成させ、
(b)該フィードバック流路において、該合成を行う前に、初期パケットと該次状態のパケットとを選択的に合流させ、
(c)キュー列のそれぞれの第2キューにデータストリームを格納させ、
(d)該合流ノードへの初期パケット投入順に基づき巡回的に、該キュー列の第2キューを選択して、この第2キューの出力段の出力を該第1キューの入力段に供給させ、
(e)該状態テーブルメモリの出力に含まれるパターン一致情報がパターン一致を示しているか否かを判定させ、肯定判定した場合には、該出力に対応した、予測されるデータストリーム識別子とともに割込要求信号を出力させる、
工程を有することを特徴とするパターンマッチング方法。
【請求項21】
(f)該キュー列の各第2キューについて、空きが所定量を超えた場合には該第2キューに対応したデータストリーム識別子とともに割込要求信号を出力させる、
工程をさらに有することを特徴とする請求項20に記載のパターンマッチング方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate


【公開番号】特開2008−242901(P2008−242901A)
【公開日】平成20年10月9日(2008.10.9)
【国際特許分類】
【出願番号】特願2007−83598(P2007−83598)
【出願日】平成19年3月28日(2007.3.28)
【出願人】(307009115)株式会社ノディック (10)
【出願人】(504202472)大学共同利用機関法人情報・システム研究機構 (119)