(57)【特許請求の範囲】
【請求項１】
リスト内のアイテム一致検索のためのデバイスであって、
−  エントリアイテムを各自の内容と並列で比較するように構成される複数の連想メモリモジュール（５０１、５０２）であって、前記リストは、優先順位リストで定義された順番での前記モジュールの有効な内容の連結によって表される、連想メモリモジュールと、
−  前記優先順位リスト内で、エントリアイテムが前記モジュールに記憶されたアイテムに一致する１番目のモジュールを決定するためのモジュール（５０９）と、
−  エントリアイテムに一致する前記決定されたモジュールの１番目のアイテムを読み込むためのモジュール（５１４）とを含む、デバイス。
【請求項２】
−  前記１番目のアイテムを無効にするためのモジュール（５１４）と、
−  前記決定されたメモリと関連付けられているアイテムカウンタを更新するための更新モジュール（５１０）であって、前記アイテムカウンタは前記メモリに記憶された有効なアイテムの数を表す、更新モジュールとをさらに含む、請求項１に記載のデバイス。
【請求項３】
前記更新モジュールがさらに、モジュールが空の場合に前記優先順位リストの更新を開始するように構成され、前記更新により、前記モジュールが、空ではないモジュールの優先順位レベルよりも低い優先順位レベルに置かれることが可能になる、請求項２に記載のデバイス。
【請求項４】
前記メモリと関連付けられている優先順位インデックスが更新される、請求項２または３に記載のデバイス。
【請求項５】
前記更新が、前記モジュールとリスト内の後続モジュールとのシフトを含む、請求項４に記載のデバイス。
【請求項６】
前記優先順位リストが各モジュールのパラメータを含み、各モジュールが空かどうかを示す、請求項１から５のいずれか一項に記載のデバイス。
【請求項７】
モジュールが前記パラメータによって分類される、請求項６に記載のデバイス。
【請求項８】
前記優先順位リスト内のモジュールの順番は、配分順序を反映する、請求項１から７のいずれか一項に記載のデバイス。
【請求項９】
前記アイテム一致検索が、前記アイテムのタグと前記リストのアイテムのタグとの関連付けにより実施される、請求項１から８のいずれか一項に記載のデバイス。
【請求項１０】
前記モジュールが、３値の内容によりアドレス指定可能なメモリモジュールである、請求項１から９のいずれか一項に記載のデバイス。
【請求項１１】
ＳｘＮ個のアイテムのリストを処理するために、Ｎ個の連想メモリモジュールを含み、各モジュールがＳ個のアイテムを含むことができる、請求項１から１０のいずれか一項に記載のデバイス。
【請求項１２】
マルチプレクサのｌｏｇ２（Ｎ）個のステージから形成された、デバイスの少なくとも１つの処理モジュールを含み、Ｎは連想メモリモジュールの数である、請求項１から１１のいずれか一項に記載のデバイス。
【請求項１３】
リスト内のアイテム一致検索のための方法であって、
−  エントリアイテムを複数の連想メモリモジュールの内容と並列で比較するステップであって、前記リストは、優先順位リストで定義された順番での前記モジュールの有効な内容の連結によって表される、比較するステップと、
−  前記優先順位リスト内で、エントリアイテムが前記モジュールに記憶されたアイテムに一致する１番目のモジュールを決定するステップと、
−  エントリアイテムに一致する前記決定されたモジュールの１番目のアイテムを読み込むステップとを含む、方法。
【請求項１４】
−  前記１番目のアイテムを無効化するステップと、
−  前記決定されたメモリと関連付けられているアイテムカウンタを更新するステップであって、前記アイテムカウンタは前記メモリに記憶された有効なアイテムの数を表す、更新するステップとをさらに含む、請求項１３に記載の方法。
【請求項１５】
モジュールが空の場合に前記優先順位リストを更新するステップであって、前記更新により、前記モジュールが、空ではないモジュールの優先順位レベルよりも低い優先順位レベルに置かれることが可能になる、更新するステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記メモリと関連付けられている優先順位インデックスが更新される、請求項１４または１５に記載の方法。
【請求項１７】
前記更新が、前記モジュールとリスト内の後続モジュールとのシフトを含む、請求項１６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報技術の分野に関する。より具体的には、ハードウェアを使用する、リスト内でのアイテム検索の実装に関する。
【背景技術】
【０００２】
ＭＰＩインターフェイス（ＭＰＩは「Ｍｅｓｓａｇｅ  Ｐａｓｓｉｎｇ  Ｉｎｔｅｒｆａｃｅ（メッセージパッシングインターフェイス）」の略）をサポートするネットワークカードの実装には、リスト内でアイテム検索を大量に使用することが必要である。
【０００３】
これは例えば、ノードのストレージサイトについての指示とともに通信ネットワークのノードによって予期されるメッセージをリストすることと、ノードのすべての着信メッセージをリストのそれと比較することとを必要とする。したがって、メッセージが到着すると、それは処理のためにストレージサイトに移送され得る。
【０００４】
通常、各メッセージはリスト内のメッセージのタグと比較されなければならないタグを持っている。リストのメッセージのタグは、減少されたビット数に対してタグの比較が実施されるように、場合によりマスクされ得る。
【０００５】
メッセージが到着すると、そのタグはリストの１番目のアイテムのそれと比較され、次いで２番目のものと比較され、次いで３番目のものと比較され、以下同様に、タグの一致が見つかるまで継続される。
【０００６】
この場合、着信メッセージはストレージサイトに移送され、リストの一致するアイテムは削除される。次にリストが更新される。
【０００７】
したがって、予期されるメッセージのリストは、一致するメッセージが到着する場合には削除され得るアイテムを持ち、新しいメッセージが予期される場合には追加され得るアイテムを持つ、動的に修正されたリストである。
【０００８】
この種類のリスト内の検索は、リスト縦断を用いてソフトウェアにより実装され得るが、この種類の実装はコンピューティングリソースを大量に消費する。
【０００９】
さらに、着信メッセージはリストのすべてのアイテムと順番に比較されなければならず、処理時間はリストのサイズに比例する。極めて大量のプロセッサを採用する応用例（典型的にはスーパーコンピュータ）では、ソフトウェア実装はシステムを極めて遅くすることがある。
【００１０】
したがって、ハードウェア実装が好ましい可能性がある。例えば探索木を使用するなど、一致検索を並列で実施することが特に提案されてきた。
【００１１】
しかしながら、例えばＭＰＩインターフェイスのコンテキストでは着信メッセージと一致する最初のアイテムのみが得られなければならないため、一致を求める並列検索は複雑である。リストのアイテムの順序の概念は、一致を求める並列検索においてさえも維持されなければならない。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
したがって、リスト内のアイテム一致検索のための情報技術ハードウェアの実装を改善する必要がある。
【課題を解決するための手段】
【００１３】
本発明はこのコンテキスト内にある。
【００１４】
本発明の第１の態様は、リスト内のアイテム一致検索のためのデバイスに関連し、デバイスは：
−  エントリアイテムを各自の内容と並列で比較するように構成される複数の連想メモリモジュールであって、前記リストは、優先順位リストで定義された順番での前記メモリの有効な内容の連結によって表される、連想メモリモジュールと、
−  前記優先順位リスト内で、エントリアイテムがモジュールに記憶されたアイテムに一致する１番目のモジュールを決定するためのモジュールと、
−  エントリアイテムに一致する前記決定されたモジュールの１番目のアイテムを読み込むためのモジュールとを含む。
【００１５】
第１の態様に記載のデバイスは、アイテム一致検索がコンピュータシステムで減少された数のクロックサイクルで実行されることを可能にする。
【００１６】
例えば、１０２４個のアイテムのリスト内のアイテムに対する一致検索は、１０サイクル未満で実行され得る。
【００１７】
例えば、このデバイスはＡＬＰＵ（「Ａｓｓｏｃｉａｔｉｖｅ  Ｌｉｓｔ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（連想リスト処理ユニット）」の略）である。
【００１８】
いくつかの実施形態によれば、デバイスはさらに：
−  前記１番目のアイテムを無効にするためのモジュールと、
−  前記決定されたメモリと関連付けられているアイテムカウンタを更新するための更新モジュールであって、前記アイテムカウンタは前記メモリに記憶された有効なアイテムの数を表す、更新モジュールとを含む。
【００１９】
いくつかの実施形態によれば、前記更新モジュールはさらに、モジュールが空の場合に前記優先順位リストの更新を開始するように構成され、前記更新により、前記モジュールが、空ではないモジュールの優先順位レベルよりも低い優先順位レベルに置かれることが可能になる。
【００２０】
例えば、前記メモリと関連付けられている優先順位インデックスが更新される。
【００２１】
例えば、前記更新は、前記モジュールとリスト内の後続モジュールとのシフトを含む。
【００２２】
いくつかの実施形態によれば、前記優先順位リストは各モジュールのパラメータを含み、各モジュールが空かどうかを示す。
【００２３】
例えば、モジュールは前記パラメータによって分類される。
【００２４】
また例として、前記優先順リスト内のモジュールの順番は、配分順序を反映する。
【００２５】
いくつかの実施形態によれば、前記一致検索は前記アイテムのタグと前記リストのアイテムのタグとの関連付けにより実施される。
【００２６】
例えば、前記モジュールは、３値の内容によりアドレス指定可能なメモリモジュールである。
【００２７】
この種類のモジュールは、通常使用されるレジスタ（「フリップフロップ」として知られる）よりも少ないエネルギーを消費する。
【００２８】
ＳｘＮ個のアイテムのリストを処理するために、デバイスはＮ個の連想メモリモジュールを含むことができ、各モジュールはＳ個のアイテムを含むことができる。
【００２９】
例えば、デバイスの少なくとも１つの処理モジュールは、マルチプレクサのｌｏｇ２（Ｎ）個のステージ（ｌｏｇ２は２を底とする対数を表す）から形成され、Ｎは連想メモリモジュールの数である。
【００３０】
例えば処理ユニットは、再順序付けモジュール、選択モジュール、または他のモジュールである。
【００３１】
本発明の第２の態様は、リスト内のアイテム一致検索のための方法に関連し、方法は以下のステップを含む：
−  エントリアイテムを複数の連想メモリモジュールの内容と並列で比較するステップであって、前記リストは、優先順位リストで定義された順番での前記メモリの有効な内容の連結によって表される、比較するステップと、
−  前記優先順位リスト内で、エントリアイテムがモジュールに記憶されたアイテムに一致する１番目のモジュールを決定するステップと、
−  エントリアイテムに一致する前記決定されたモジュールの１番目のアイテムを読み込むステップ。
【００３２】
方法は、さらに以下のステップを含み得る：
−  前記１番目のアイテムを無効化するステップと、
−  前記決定されたメモリと関連付けられているアイテムカウンタを更新するステップであって、前記アイテムカウンタは前記メモリに記憶された有効なアイテムの数を表す、更新するステップ。
【００３３】
方法はさらに、モジュールが空の場合に前記優先順位リストを更新するステップを含むことができ、前記更新により、前記モジュールが、空ではないモジュールの優先順位レベルよりも低い優先順位レベルに置かれることが可能になる。
【００３４】
例えば、前記メモリと関連付けられている優先順位インデックスが更新される。
【００３５】
例えば、前記更新は、前記モジュールとリスト内の後続モジュールとのシフトを含む。
【００３６】
例えば、前記優先順位リストは各モジュールのパラメータを含み、各モジュールが空かどうかを示す。
【００３７】
いくつかの実施形態によれば、モジュールは前記パラメータによって分類される。
【００３８】
例えば、前記優先順リスト内のモジュールの順番は、配分順序を反映する。
【００３９】
いくつかの実施形態によれば、前記一致検索は、前記アイテムのタグと前記リストのアイテムのタグとの関連付けにより実施される。
【００４０】
いくつかの実施形態によれば、前記モジュールは、３値の内容によりアドレス指定可能なメモリモジュールである。
【００４１】
本発明の第３の態様は、コンピュータプログラムならびにコンピュータプログラム製品およびそのようなプログラムおよび製品の記憶媒体に関連し、本発明の第２の態様に記載の方法の実装を可能にする。
【００４２】
本発明の他の特徴と利点は、限定的でない例としての以下の本詳細な説明と、付随する図面から明らかになるであろう。
【図面の簡単な説明】
【００４３】
【図１】本発明のいくつかの実施形態の全体的な目的を示す図である。
【図２】いくつかの実施形態による、連想メモリモジュール内のリストのストレージを示す図である。
【図３Ａ】いくつかの実施形態による、優先順位リストの更新を示す図である。
【図３Ｂ】いくつかの実施形態による、優先順位リストの更新を示す図である。
【図４】いくつかの実施形態による、カウントテーブルを示す図である。
【図５】いくつかの実施形態による、ハードウェアの実装を示す図である。
【発明を実施するための形態】
【００４４】
図１に示される全体的な目的によれば、リスト１００は、対応するインデックス「０」、「１」、「２」などに従って順序付けられている特定の数のアイテム１０１、１０２、１０３などを含む。アイテム１０１のような、リストの各アイテムは、データ１０４（「０」）、タグ１０５（「ＴＡＧ」）、および場合によりマスク１０６（「ＭＳＫ」）を含む。
【００４５】
このリスト内で、データ１０８とタグ１０９を含むエントリアイテム１０７に一致する１番目のアイテムを決定するという問題である。
【００４６】
一致は、エントリアイテムのタグとリストのアイテムのタグとを比較することにより実施される。一致検索を簡略化するために、比較はリストのアイテムのマスクを用いて実施され得る。マスク付きで比較することで、一致は、少ない数のビットに対して実施され得る。
【００４７】
リストを縦断して１つずつ比較を実施することにより一致検索を実施するのではなく、並列検索を実施することが提案される。
【００４８】
この目的のために、図２に示されているように連想メモリ（ＣＡＭ）モジュールが使用される。例えば、これらはＴｅｒｎａｒｙ  Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ（ＴＣＡＭ、３値連想メモリ）モジュールである。
【００４９】
検索が実施されるリスト２００（「ＬＩＳＴ」）は、モジュール２０１（「ＴＣＡＭ０」）、２０２（「ＴＣＡＭ１」）、．．．、２０３（「ＴＣＡＭ３１」）の集合に記憶される。例えば、リスト２００は３２個のアイテムを持つ３２個のモジュールに分配される１０２４個のアイテムを含む。モジュールは初めに、例えばそのインデックス値に従って初期順序で配分される。したがって、インデックス「０」のモジュール２０１（「ＴＣＡＭ０」）が最初に配分され、インデックス「１」の２０２（「ＴＣＡＭ１」）が続き、以下同様にして、インデックス「３１」のモジュール２０３（「ＴＣＡＭ３１」）まで続く。他の初期配分順序が提供されてもよい。
【００５０】
リストのアイテムがエントリアイテムに一致する場合、それはリストから削除される。したがって、そのアイテムが記憶されているモジュールの行は無効化される。例えば、行が「空」であることを示すために、有効性ビットが更新される。また例えば、行はゼロに設定される。
【００５１】
モジュールのすべての行が無効化された場合、モジュールは再び新しいアイテムをその中に記憶できるようになる。
【００５２】
配分の順序で配置されたモジュールの有効な行を連結することにより、リストは現在の状態で再構成されることができるようになる。
【００５３】
ＮｘＳ個のアイテムのリストを処理するために、例えばＮ個のＴＣＡＭが使用され、それぞれはＳ個のエントリを含むことができる。
【００５４】
モジュールの動的配分を管理するために、優先順位リスト（図示されていない）はモジュールを識別し、初期リストが正確に再構成されることを可能にするように、それらが順に並べられることを可能にする。
【００５５】
図３Ａは、優先順位リスト３００を示している。第１列３０１は、モジュールのインデックスを、その優先順位順に含む。第２列３０２は、有効性パラメータ（Ｖ）を含み、モジュールが配分されている（Ｖ＝１）、つまりモジュールの少なくとも１つの行が、一致が検索されるリストのアイテムを記憶しているかどうか、またはモジュールが配分されていない（Ｖ＝０）、つまりモジュールがその中にリストの新しいアイテムを記憶できるかどうかを示す。
【００５６】
一致が検索されるリストを再構成するためには、優先順位リストで与えられた順序で、配分されたモジュールの有効な行を連結すれば十分である。
【００５７】
したがって、図３の例では、リストを再構成するために、インデックス「５」のモジュールの有効な行、次いでインデックス「２」の有効な行、次いでインデックス「４」の有効な行が連結されなければならない。優先順位リストでは、配分されたモジュールは配分されていないモジュールの前に配置される。
【００５８】
例えば、インデックス「５」のモジュール（ＴＣＡＭ５）が完全に空にされ、つまりそのすべての行が無効化（または消去）された場合、その有効性パラメータＶは「０」になり、リスト３００のすべての行は図３Ｂに示されているようにシフトされる。したがって、インデックス「２」のモジュールがリストの先頭となり、インデックス「５」のモジュールが優先順位リストの最後の配分されていないモジュールとなる。一致検索プロセスの過程で空にされたモジュールは、見つかった一致次第で優先順位リストの任意の場所にあり得る。
【００５９】
モジュールが空かどうかを決定するために、図４で示されているカウントテーブル４００が、モジュール内での記録および／または消去（もしくは無効化）に応じて更新される。
【００６０】
テーブル４００は、例えばインデックス「０」のモジュール（ＴＣＡＭ０）を最初にリストし、インデックス「１」のモジュール（ＴＣＡＭ１）をその次にリストするように、インデックスに従ってモジュールをリストする列４０１を含む。第２列はモジュール内の有効な行の数を表す各モジュールのカウント値を含む。したがって、例えばインデックス「０」のモジュール（ＴＣＡＭ０）が２０個の値の行を含む。つまり、一致が検索されるリストの２０個のアイテムがそのモジュールに記憶されている。インデックス「１」のモジュール（ＴＣＡＭ１）は、３１個の有効な行を含む。インデックス「３」のモジュール（ＴＣＡＭ３）は０個の有効な行を含む。つまり、モジュールは空であり、したがって、配分が可能である。
【００６１】
新しいアイテムがリストに統合される度に、モジュールのカウンタがインクリメントされる。着信アイテムとリストのアイテムとの間に一致が見つかる度に、リストのそのアイテムは削除され、それが記憶されているモジュールのカウンタはデクリメントされる。
【００６２】
エントリアイテムとリストのアイテムとの間の一致検索は、例えばＭＰＩインターフェイスを採用するルータなどで、連想リスト処理ユニット（ＡＬＰＵ）において実装され得る。
【００６３】
この種類のインターフェイスでは、通信ネットワークのノードに到着するメッセージは処理のために移送されなければならない。したがって、受信するメッセージの待機リストが作成され、それらのメッセージのストレージアドレスはその中で関連付けられる。メッセージがノードに到着すると、待機リストのそれと比較される（上述のタグを使用する）。一致が見つかると、待機リストの順序の中で１番目の一致メッセージがリストから削除される。メッセージは次いで関連付けられたアドレスに従って移送される。
【００６４】
図５を参照して、実施形態による一致検索のためのハードウェア実装が説明される。この実装は例えば、ＡＳＩＣ（「Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ（特定用途向け集積回路）」の頭文字）の形態で実施され得る。
【００６５】
アイテムのタグ５００（「ｈｄｒ」）は、一連の連想メモリモジュールに対して並列に与えられる。この例では、これらは「ＴＣＡＭ  ０」、．．．「ＴＣＡＭ  Ｎ−１」（例、Ｎ＝３２）という名前のＮ個の３値モジュール（ＴＣＡＭモジュール）５０１、．．．、５０２である。このタグはしたがって、モジュールに記憶されているデータのタグ（場合によりマスクされている）と比較される。モジュールに記憶されているアイテムは、タグ５００のアイテムとの一致が検索されるリストのアイテムであることが思い起こされよう。
【００６６】
各モジュールは出力として、モジュールに一致が見つかった場合は値が「１」、一致が見つからなかった場合は「０」である一致ビット５０３、．．．、５０４（「ｈｉｔ＿０」、．．．、「ｈｉｔ＿Ｎ−１」という名前）を提供する。各モジュールはまた、一致が見つかったモジュール内の１番目のアイテムのアドレスを表すワードｍｏｔ５０５、．．．、５０６（「ｈｉｔ＿０」、．．．、「ｈｉｔ＿ａｄｄｒ＿Ｎ−１」という名前）を提供する。
【００６７】
したがって、モジュールにより提供される一致ビットは、再順序付けモジュール５０７への入力として与えられる結果ベクトルを形成する。一致はいくつかのモジュールで見つかる可能性があるが、最初のものだけを保持することが望ましいことを思い起こされたい。
【００６８】
結果ベクトルの中で一致ビットが分類される順序は固定されているが、ビットの配分は動的である。したがって、モジュール５０７ｄは出力としてペアのリスト（Ｖ［Ｋ］＆ｈｉｔ＿［Ｋ］、Ｔ［Ｋ］）を与え、Ｔ［Ｋ］とＶ［Ｋ］は、図３Ａに関連してすでに説明したような、優先順位リスト管理のためのモジュール５０８の優先順位リストから来る。この優先順位リストでは、インデックスＱのＴＣＡＭモジュール（ＴＣＡＭＱ）がリスト内に優先順位Ｋを持っている場合、Ｔ［Ｋ］＝Ｑである。
【００６９】
この順序付けされたペアのリストにより、選択モジュール５０９はＶ［Ｋ］＝ｈｉｔ＿Ｋ＝１が確かめられたリストの１番目のＴＣＡＭモジュール、つまり有効（Ｖ［Ｋ］＝１）であり一致が見つかった（ｈｉｔ＿Ｋ＝１）、最高の優先順位のＴＣＡＭモジュールを選択することができる。
【００７０】
モジュール５０７と５０９は例えば、モジュール５０７についてはｌｏｇ２（Ｎ＋１）個のステージ、モジュール５０９についてはｌｏｇ２（Ｎ）個のステージである、マルチプレクサのステージを利用して実現され得る（ｌｏｇ２は２を底とする対数を表す）。これは、システムの他の処理要素に対しても一般化できる大きさである。これらの要素は、（ステージの）数がおよそｌｏｇ２（Ｎ）（Ｎは使用されるＴＣＡＭの数）であり得るマルチプレクサのステージにより実現され得る（ｌｏｇ２は２を底とする対数を表す）。
【００７１】
ある例では、一致がモジュールＴＣＡＭ２とＴＣＡＭ５で見つかると想定される（図３Ａで例示されている）。左から右に０から３１の位置を持つ結果ベクトルの例を考慮すると（通常、ハードウェアアーキテクチャでの慣例は、図５で表されているように逆である）、このベクトルはその最初の６つのビットとして０、０、１、０、０、１、０、．．．を持つ。再順序付けモジュールは、以下のペアを生成する（図３で図式的に示されている優先順位を採用）：＜１，５＞、＜１，２＞、＜０，４＞、＜０，１０＞、．．．（各ペアは、＜Ｖ［Ｋ］＆ｈｉｔ＿［Ｋ］、Ｔ［Ｋ］＞の形式である）。
【００７２】
モジュール５０９は、Ｖ［Ｋ］＝ｈｉｔ＿Ｋ＝１であるこのリスト（またはペアのベクトル）の１番目のアイテム、つまりこの例ではペア＜１，５＞を選択する。
【００７３】
図５に戻ると、ＴＣＡＭモジュールがモジュール５０９によって選択された場合、ＴＣＡＭモジュールに関連付けられているカウンタはデクリメントされる。したがって、モジュール５０９はそのＴＣＡＭモジュールのインデックスを更新モジュール５１０に提供する。この更新モジュールは、モジュール５０７により選択されたＴＣＡＭモジュールと関連付けられているカウント値をデクリメントするために、図４に関連して説明されているように、優先順位リスト管理のためにドキュメントシグナルをモジュール５１１に送信する。
【００７４】
応答として、モジュール５１１はモジュール５１０にカウント値が値「０」に達したことを示すことができる。この場合、モジュール５１０は、図３Ｂに関連してすでに説明されたように、問題とするＴＣＡＭモジュール（モジュール５０９により選択され、カウント値が「０」に達したもの）をモジュール５０８内のリストの最後に置き、またリストのすべての行をシフトするために、シフトシグナルをシフトモジュール５１２に送信する。このシフトシグナルは、有効性ビットを「０」に設定することでモジュールが無効化されなければならないことも示す。モジュール５１２は次いで、このシフトとこの無効化を実施するために、必要なシグナルをモジュール５０８に送信するタスクを引き受ける。
【００７５】
一致がモジュールＴＣＡＭ２とＴＣＡＭ５で見つかると想定されている上述の例では、カウント値が「０」に達しているので、モジュールＴＣＡＭ５のカウンタをデクリメントすることが必要であるとさらに想定される。
【００７６】
図５に戻ると、ＴＣＡＭモジュールが選択モジュール５０９により選択されると、それが記憶している値が配信されるべきである。
【００７７】
したがって、ＴＣＡＭモジュールのインデックスが選択シグナルとしてマルチプレクサ５１３に提供される。さらに、マルチプレクサが入力として、ＴＣＡＭモジュール５０１、．．．、５０２により配信される、ワード５０５、．．．、５０６（「ｈｉｔ＿ａｄｄｒ＿０」、．．．、「ｈｉｔ＿ａｄｄｒ＿Ｎ−１」）を受信する。
【００７８】
マルチプレクサはしたがって、選択モジュール５０９により示されたＴＣＡＭモジュールに対応するワードを、読み込みモジュール５１４に提供する。
【００７９】
読み込みモジュールは、モジュール５０９（モジュール５１３と同じ選択シグナルを受信する）により示されたＴＣＡＭに記憶された値を読み込み、その値を記憶しているメモリの行を無効化するタスクを引き受ける。無効化は、例えば行をゼロにすることで実現される。無効化は、行に関連付けられている有効性ビットをゼロにすることでも実現され得る。
【００８０】
本発明は、付随する図を参照しつつ、本詳細な説明で説明され、例示されてきた。しかしながら、本発明は示された実施形態に限定されない。本説明や付随する図を理解することにより、他の変形や実施形態が、当業者により推測され実装され得る。
【００８１】
請求項で、「含む」という用語は他の要素または他のステップを除外しない。不定冠詞「ａ」は、複数形を除外しない。単一のプロセッサまたは他のいくつかのユニットが、本発明を実装するために使用され得る。提示されているおよび／または特許請求の範囲の異なる機能は、有利に結合され得る。説明または異なる従属請求項にそれらが記載されていることは、実際にはそれらの結合の可能性を除外しない。参照記号は、本発明の範囲を限定すると理解されるものではない。
【図１】
0006495343.tif 000002
【図２】
0006495343.tif 000003
【図３Ａ】
0006495343.tif 000004
【図３Ｂ】
0006495343.tif 000005
【図４】
0006495343.tif 000006
【図５】
0006495343.tif 000007