(57)【要約】【課題】単一の記憶構造を使用してエントリの順序規則を維持し、必要な記憶空間を低減させるシンプルな構成を提供する。【解決手段】  単一のアドレス指定可能な記憶アレイ20を使用して、複数のエントリタイプのうちの１つを有するエントリを格納、及び読み出し、並びに格納されたエントリについての順序情報を格納するための方法及び装置。インデックスパイプ30は、アドレス指定可能な記憶アレイ20内に格納されたエントリの先入れ先出し順序を維持する。インデックスパイプ30内のステージは、記憶アレイ20内に格納されたエントリのアドレスと、格納されたエントリのタイプと、格納されたエントリの有効性とを表す値を格納する。追加の制御ロジック40、50が、エントリタイプ間の順序規則を実行する。【選択図】図１
2004348746.tif 000002
【特許請求の範囲】
【請求項１】
単一のアドレス指定可能な記憶アレイ（２０）を使用して、複数のタイプのエントリの格納及び読み出しと、格納されたエントリについての順序情報の格納とを行う方法であって、
前記アドレス指定可能な記憶アレイ（２０）の利用可能なアドレスにエントリを格納するステップと、
前記格納されたエントリの前記アドレスを表す値と、前記タイプを表す値とを格納するステップと、
前記エントリのタイプに基づいて、順序規則に従って前記アドレス指定可能な記憶アレイ２０からエントリを読み出すステップと、
前記読み出されたエントリを要求装置に転送するステップと、
前記アドレス指定可能な記憶アレイ（２０）からの前記エントリの取り出しを反映するように前記格納された値を更新するステップ、
とを含む、方法。
【請求項２】
前記順序規則は、先入れ先出し順序規則である、請求項１記載の方法。
【請求項３】
前記順序規則は、特定のエントリタイプの最も古いエントリが、先入れ先出し順序に関わりなく、前記アドレス指定可能な記憶アレイ（２０）から、他のエントリタイプのエントリに先行して読み出されることを指定する、請求項２記載の方法。
【請求項４】
前記値は、前記アドレス指定可能な記憶アレイ（２０）内のアドレスと、エントリタイプと、前記対応するエントリの有効性とに対応するビットを含むレジスタ（３０）に格納されることからなる、請求項１記載の方法。
【請求項５】
単一のアドレス指定可能な記憶アレイ（２０）を使用して、複数のエントリタイプの格納及び読み出し、ならびに格納されたエントリについての順序情報の格納を行うための装置であって、
前記アドレス指定可能な記憶アレイ（２０）と、
前記アドレス指定可能な記憶アレイ（２０）の各エントリ毎に１つのステージを含むインデックスパイプ（３０）であって、インデックスパイプ（３０）の各ステージは、前記アドレス指定可能な記憶アレイ（２０）内のエントリのアドレス及びタイプに対応する情報を格納することができることからなる、インデックスパイプと、
前記アドレス指定可能な記憶アレイ（２０）からエントリを読み出すための制御ロジック（４０）と、
取り出されたエントリを要求装置に戻すための制御ロジック（５０）
とを備える、装置。
【請求項６】
前記アドレス指定可能な記憶アレイ（２０）から、どのエントリが特定の時に読み出されることが可能なエントリであるかを指定するエントリタイプによる順序規則を維持するための制御ロジック（５０）を更に備える、請求項５に記載の装置。
【請求項７】
順序規則を維持するための前記制御ロジック（５０）は、エントリタイプによる先入れ先出し順序を維持するための先入れ先出し制御ロジックを含む、請求項６に記載の装置。
【請求項８】
前記インデックスパイプ（３０）内の各ステージは、前記アドレス指定可能な記憶アレイ（２０）内のアドレスに対応するビットと、エントリタイプに対応するビットと、前記エントリの有効性を示すビットとを含むレジスタである、請求項５乃至７のいずれかに記載の装置。
【請求項９】
エントリ順序情報及び順序規則を使用して異なるエントリタイプを有する複数のエントリに対して順序規則を提供することによって、バッファからエントリを要求装置に提供する方法であって、前記複数のエントリは、単一のアドレス指定可能な記憶アレイ（２０）に格納され、タイプ利用可能値は、第１のエントリタイプのエントリが利用可能であることを示すようセットされることからなり、該方法は、
前記第１のエントリタイプのエントリに対する要求を受け取るステップと、
前記要求されたエントリを前記要求装置に転送するステップと、
単一のアドレス指定可能な記憶アレイ（２０）から前記エントリを取り出すステップと、
前記第１のエントリタイプのエントリが前記利用不可能なことを示すために前記タイプ利用可能値をセットするステップと、
前記エントリ順序情報を使用して特定のエントリタイプの次に利用可能なエントリとなる前記単一のアドレス指定可能な記憶アレイ（２０）内のエントリを決定するステップと、
前記特定のエントリタイプのエントリが利用可能な場合には、前記特定のエントリタイプのエントリが利用可能であることを示すよう前記タイプ利用可能値をセットするステップ
とを含む、方法。
【請求項１０】
前記エントリ順序情報は、前記単一のアドレス指定可能な記憶アレイ（２０）に格納されている前記エントリの位置を表す位置値と、前記エントリの前記タイプを表すタイプ値とを含む、請求項９記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、単一のアドレス指定可能な記憶アレイを使用して複数のエントリタイプを表すエントリを格納するための方法及び装置に関する。
【背景技術】
【０００２】
バッファは、通常ランダムアクセスメモリ（ＲＡＭ）における一時的な記憶領域である。典型的には、バッファは保持領域として働き、中央演算処理装置（ＣＰＵ）が、バッファに保持されたデータを装置に転送する前にデータを処理できるようにする。特定タイプのバッファは、先入れ先出し（ＦＩＦＯ）キューである。ＦＩＦＯキューは、バッファに書き込まれた最初のエントリが、バッファから読み出される最初のエントリとなるバッファである。ＦＩＦＯキュー内に最も長い期間存在しているエントリが、キューから読み出される最初のエントリである。
【０００３】
複数のエントリタイプがＲＡＭ内のＦＩＦＯキュー内に格納される場合、複数のエントリタイプ内のＦＩＦＯの順序を維持するため、格納される各エントリタイプ毎に個別のバッファが必要になる。エントリは、エントリタイプによって異なる優先度を有する可能性がある。
【０００４】
複数のエントリタイプを処理するための従来における１つの解決策は、各エントリタイプ毎に１つの標準ＦＩＦＯキューを使用するというものである。例えば、２つの異なるエントリタイプ、すなわちタイプＡ及びタイプＢ、があるものと想定する。従来における解決策では、タイプＡのために１つのＦＩＦＯキューが、そしてタイプＢのために別のＦＩＦＯキューが必要であった。
【０００５】
任意の１つのエントリタイプ内でも厳密なＦＩＦＯ規則に従うが、多くの場合、複数のエントリタイプはそれらのエントリタイプ間で異なる順序規則に従う。例えば、２つの例示的なエントリタイプＡ及びＢのための順序規則は次の通りである。
１）各エントリタイプ内で、全てのエントリはキューに書き込まれた順序でキューから読み出されなければならない。
２）１つ又は複数のタイプＡエントリは、タイプＡエントリに先行するキューに書き込まれたタイプＢエントリに先行して、キューから読みだされることが可能であるが、タイプＢエントリは、読み出されることができない。
【０００６】
タイプＢエントリの格納に加えてこのような順序規則を処理するため、ＦＩＦＯキューＢは、エントリがＦＩＦＯキューＢに配置されたときにＦＩＦＯキューＡに対する書き込みインデックス（例えばポインタ）に対応する各エントリと共に、追加の「インデックス」フィールドもまた格納する。したがって、従来における解決策では、ＦＩＦＯキューＢからエントリ、すなわちキューの最初のエントリ（ヘッドエントリとも呼ばれる）を取り出そうとするときには、ＦＩＦＯキューＢエントリのインデックスフィールドをＦＩＦＯキューＡのヘッドエントリのインデックスフィールドと比較する。ヘッドＦＩＦＯキューＢエントリのインデックスフィールドが、ヘッドＦＩＦＯキューＡエントリのインデックスフィールドよりも古くなければ、ＦＩＦＯキューＢエントリはキューから取り出されない。
【０００７】
この従来技術によれば、ＦＩＦＯキューが単一の順序付けられてないバッファを使用して実施された場合、（１）キュー内の最も古いエントリのメモリ位置すなわちメモリアドレスを指す読み出しポインタと、（２）キュー内の最も新しいエントリの背後にある、１つのエントリを指す書き込みポインタ、とを保持しなければならない。この場合、キューの先頭及び末尾（それぞれ最古エントリ及び最新エントリ）はメモリ内のどこにでもおくことが可能である。典型的には、バッファは、読み出しポインタと、書き込みポインタとが同じアドレスを指している場合に空であるとみなされ、書き込みポインタが、読み出しポインタによって指し示されるアドレスの前の、メモリ内の１つのアドレスを指している場合に満杯であるとみなされる。書き込みポインタがバッファの終わりに進むまでエントリがキューに連続して配置され、更なるエントリをキューに配置させようとするときに、「ロールオーバ」というケースが発生する。読み出しポインタがバッファのちょうど先頭にある場合に、バッファは満杯であるとみなされ、更なるエントリはキューに配置されない。しかしながら、読み出しポインタがバッファの先頭にない場合、書き込みポインタはバッファの末尾を「ロールオーバさせて（ぐるりと転がして）」、先頭に戻る。この構成は非常に複雑であり、エラーを招く可能性が高まる。
【０００８】
この従来技術による解決策の主要な欠点は、エントリのストリームが、完全に１つのエントリタイプ、又はエントリタイプを混合したものからなる可能性があるため、同じ深さの複数のＦＩＦＯバッファ構造（レジスタアレイ、ＲＡＭ等のような）が必要となることである。この結果、各エントリタイプのためにメモリ空間を最大に割り当てる必要があるにもかかわらず、任意の時間に使用されている記憶空間はごくわずかである。別の欠点は、アドレスロールオーバのケースを処理するためのロジックが複雑であり、したがってエラーの可能性を増大させることである。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、本発明の目的は、単一の記憶構造を使用してエントリの順序規則を維持することである。
【００１０】
本発明の他の目的は、順序規則に従って複数のエントリタイプを格納し、必要とされる記憶空間を従来における手法と比較して低減する単一の記憶構造を提供することである。
【００１１】
本発明の別の目的は、実施エラーの可能性を従来における手法と比較して低減する比較的複雑性が低い構成を提供することである。
【課題を解決するための手段】
【００１２】
本発明のこれら及び他の目的は、単一のアドレス指定可能な記憶アレイを使用して、複数のエントリタイプを格納する方法と、格納されているエントリについての順序情報を格納する方法とによって達成される。入力エントリが、アドレス指定可能な記憶アレイ内のフリーなエントリに格納される。インデックスパイプ内のステージに、格納されたエントリのアドレスとタイプとを表す情報がロードされる。読み出し要求が１つ又は複数の要求装置から受け取られると、適切なエントリが、格納されている順序情報に従って、アドレス指定可能な記憶アレイから読み出されて、取り出されて、１つ又は複数の要求装置に戻される。インデックスパイプは、アドレス指定可能な記憶アレイからの要求されたエントリの取り出しを反映するように更新される。
【００１３】
本発明の前述の及び他の態様は、単一のアドレス指定可能な記憶アレイを使用して、複数のエントリタイプを格納するための装置と、格納されているエントリについての順序情報を格納するための装置とによって達成される。インデックスパイプは、アドレス指定可能な記憶アレイ内のエントリ毎に１つのステージを含む。各ステージは、アドレス指定可能な記憶アレイ内のエントリのアドレスと、エントリタイプとに対応する情報を保持することが可能である。アドレス指定可能な記憶アレイ内にエントリを格納し、アドレス指定可能な記憶アレイからエントリを読み出して取り出し、及び、取り出されたエントリを１つ又は複数の要求装置に戻すための機構が提供される。
【００１４】
本発明の更に他の態様及び利点が、本発明の好適な実施形態が本発明の実施に最良であると考えられる形態の単なる例示として示され説明される以下の詳細な説明から、当業者に容易に明らかになるであろう。理解されるように、本発明では他の異なる実施形態も可能であり、そのいくつかの詳細は、様々な明白な箇所について、本発明から逸脱することなく全ての修正が可能である。
【００１５】
本発明は、限定としてではなく例として、添付図面中の図の中に示される。図面内において同じ参照番号を有する要素は、全体を通して同じ要素を表す。
【発明の効果】
【００１６】
単一の記憶構造を使用してエントリ順序規則を維持することが可能となり、必要な記憶空間が低減され、比較的複雑性の低い構造が提供される。
【実施例】
【００１７】
図１は、本発明の一実施形態によるバッファ１０の上位レベルのブロック図である。アドレス指定可能な記憶アレイ２０、すなわちＲＡＭへのアクセスは、インデックスパイプ３０によって制御される。代替として、アドレス指定可能な記憶アレイは、エントリを格納するための任意の他のメモリ装置であってもよい。
【００１８】
インデックスパイプ３０は、エントリがバッファ１０から読み出されるときに、新しいエントリをどこに格納するか、すなわち書き込むか、及びどの格納されているエントリを記憶アレイ２０から取り出して別の装置（図示せず）に送るかを決定する記憶装置である。有利なことに、本発明は、従来技実で必要とされるようなエントリタイプ毎に１つのＦＩＦＯとなる複数のＦＩＦＯ構造の代わりに、単一のＦＩＦＯ構造のみ、すなわち記憶アレイ２０を使用して複数のエントリタイプを格納する。本発明は、有利なことに、記憶空間に存在する使用されない可能性のある記憶空間を低減し、ＦＩＦＯ構造内におけるロールオーバのケースを処理するために必要なロジックをシンプルにする。
【００１９】
実施例のインデックスパイプ３０は、４つのステージレジスタを含む。すなわち、エントリの格納のために使用可能な記憶アレイ２０内の各位置毎に１つのステージレジスタ３２ａ〜３２ｄを含む。説明を簡単にするために、記憶アレイ２０は４つのエントリを格納することが可能となっているものとして理解され、したがって図１のインデックスパイプ３０は４つのステージレジスタ３２ａ〜３２ｄを有する。代替として、記憶アレイ２０内のエントリ数が、インデックスパイプ３０内のステージレジスタ数に等しい限り、任意のサイズの記憶アレイ２０を使用することができる。
【００２０】
各ステージレジスタ３２ａ〜３２ｄは、（ａ）エントリタイプと、（ｂ）記憶アレイ２０内に格納されているエントリが参照されるアドレスと、（ｃ）ステージレジスタが有効であり、別の装置への書き込み又は別の装置からの読み出しを行うことができるかどうかとを指定するいくつかのビットに対する記憶領域を含む。
【００２１】
本発明の前述の実施例では、２つのエントリタイプＡ及びＢしかないため、エントリのタイプを指定するビット数は１である。代替として、当業者は理解されるであろうが、エントリタイプビットの数は格納されるためのエントリタイプの数に応じて変化する。例えば、１つの非限定的な実施例では、３ビットを使用して８つの異なるエントリタイプを識別することができ、４ビットを使用して１６の異なるエントリタイプを識別することができ、以下同様である。
【００２２】
本発明の実施例では、記憶アレイ２０内にエントリのための記憶場所はたったの４つしかないため、エントリが格納される記憶アレイ２０のアドレスを指定するビットの数は２である。代替として、アレイ２０のサイズが４よりも大きい場合、追加ビットを記憶アレイ２０内のエントリを指定するために使用することができる。
【００２３】
有効性ビットは、各ステージレジスタによって示されているエントリが有効である場合、値１を有する。有効なエントリとは、記憶アレイ２０に書き込まれており、そして読み出される準備ができているエントリか、又は別の装置に対して転送される準備ができているエントリのことである。無効なエントリとは、記憶アレイ２０からヘッドレジスタＡ７０又はヘッドレジスタＢ８０のような別の装置に既に送られてしまった（又は以前に使用されたことがない）エントリのことである。以下の表１に、前述の例におけるインデックスパイプ３０の特定のステージレジスタ３２ａ〜３２ｄのビット内に格納される情報を列挙する。
【００２４】
【表１】
2004348746.tif 000003
【００２５】
各ステージレジスタ３２ａ〜３２ｄは、入力を受け取るために対応するマルチプレクサ３４ａ〜３４ｄに接続される。各マルチプレクサ３４ａ〜３４ｄでの入力選択はロード制御ロジック４０によって制御される。各クロックサイクルでの各マルチプレクサへの入力の選択肢は、（１）ステージレジスタ３２ａ〜３２ｄの現在値、すなわちステージレジスタ内の値の「保持」、（２）ロード制御ロジック４０から来る入力値、すなわちバッファ１０に書き込まれる新しい値、及び（３）ステージレジスタ３２ａ〜３２ｃに関する次の上流のステージレジスタ３２ｂ〜３２ｄの値、である。最も上流にあるステージレジスタ３２ｄは、別のステージレジスタから入力を受け取るのではなくクリアされる。
【００２６】
記憶アレイ２０内の各エントリへの参照は、上流のステージレジスタ３２ｂ〜３２ｄから下流のステージレジスタ３２ａ〜３２ｃへと移され、キューから取り出されて、目標とする送り先へ送られたエントリへの参照を置き換える。新しい入力が受け取られると、ステージレジスタ値は連続的にステージレジスタ３２ａに向かって流れる。このようにして、インデックスパイプ３０は、記憶アレイ２０内のどのエントリが現在使用されているかに関わりなく、決してロールオーバのケースを作り出すことなく、記憶アレイ２０内のエントリのＦＩＦＯ順を維持する。
【００２７】
エントリ（ｔｘｎ＿ｄａｔａ＿ｉｎ）を受け取ると、ロード制御ロジック４０は、記憶アレイ２０にｔｘｎ＿ｄａｔａ＿ｉｎの値を受け取ることを可能にさせ、それをロジック４０によって指定される記憶アレイ２０内のアドレス（ｗｒｉｔｅ＿ａｄｄｒｅｓｓ）に格納することを可能にさせる。ロード制御ロジック４０は、次のフリーなステージレジスタ３２ａ〜３２ｄをｔｘｎ＿ｄａｔａ＿ｉｎへの参照の格納のために割り当てる。ステージレジスタ３２ａ〜３２ｄの有効性ビットがロード制御ロジック４０によって読み出され、どのステージレジスタ３２ａ〜３２ｄが次のフリーなステージレジスタであるかが決定される。ロード制御ロジック４０は、ｔｘｎ＿ｄａｔａ＿ｉｎのエントリタイプ（ｔｘｎ＿ｔｙｐｅ）を決定されたフリーなステージレジスタに書き込む。ロード制御ロジック４０は、ｔｘｎ＿ｄａｔａ＿ｉｎの値が決定された次のフリーなステージレジスタに書き込まれた記憶アレイ２０内のアドレス（ｗｒｉｔｅ＿ａｄｄｒｅｓｓ）もまた書き込む。決定された次のフリーなステージレジスタの有効性ビットは、レジスタの内容が有効であること、すなわち特定のエントリタイプ（ｔｘｎ＿ｔｙｐｅ）のエントリが記憶アレイ２０の特定のアドレス（ｗｒｉｔｅ＿ａｄｄｒｅｓｓ）に書き込まれていることを示すようにセットされる。
【００２８】
アンロード制御ロジック５０は、各々の有効なステージレジスタ３２ａ〜３２ｄによって示されている各記憶アレイ２０のアドレス内に保持されているエントリタイプを示す、各ステージレジスタ３２ａ〜３２ｄのエントリタイプビットを読み出すことによって、どのエントリタイプが各記憶アレイ２０のアドレスに保持されるかを追跡し続ける。上に述べた順序規則の例に従えば、特に留意すべきことは、最初のステージレジスタ（ステージレジスタ３２ａ）がタイプＢエントリを参照しているかどうか、及びどのステージレジスタ３２ａ〜３２ｄがタイプＡエントリを最初に参照するかである。
【００２９】
Ａ＿インデックスマルチプレクサ５２は、ステージレジスタ３２ａ〜３２ｄの各々にそれぞれ格納されている値から選択を行い、ＡＢ＿インデックスマルチプレクサ５４に書き込まれる値を選択する。ＡＢ＿インデックスマルチプレクサ５４は、Ａ＿インデックスマルチプレクサ５２の出力と、ステージレジスタ３２ａに格納されている値との中から選択する。記憶アレイ２０のどのエントリがキューからの取り出しに適格であるか（すなわち、好適な実施形態における順序規則に従って、最初のタイプＡエントリによって示される位置、及びステージレジスタ３２ａがタイプＢエントリを指す場合には、ステージレジスタ３２ａによって示される位置）に影響する変更がステージレジスタ３２ａ〜３２ｄのうちの１つに格納されている値に対して行われると常に、アンロード制御ロジック５０は信号（ｒｅａｄ＿ｅｎａｂｌｅ、図示せず）を記憶アレイ２０に送り、記憶アレイ２０から取り出すのに適格なエントリがしかるべきヘッドレジスタ、すなわちＡ＿ヘッドレジスタ７０又はＢ＿ヘッドレジスタ８０に読み込まれる。このようにして、Ａ＿ヘッドレジスタ７０及びＢ＿ヘッドレジスタ８０に、記憶アレイ２０内の次のＡタイプエントリ及びＢタイプエントリがプリロードされる。例えば、Ａ＿ヘッドレジスタ７０にロードされるか（キューからの取り出しに適格な新しいエントリがタイプＡエントリの場合）、又はＢ＿ヘッドレジスタ８０にロードされる（キューからの取り出しに適格な新しいエントリがタイプＢエントリの場合）。アンロード制御ロジック５０は、Ａ＿インデックスマルチプレクサ５２と、ＡＢ＿インデックスマルチプレクサ５４とを使用してステージレジスタ３２ａ〜３２ｄ内の全てのアドレスの中から選択を行って、キューからの取り出しに適格な新しいエントリの位置を選択する。
【００３０】
代替として、本発明に対して実質的な変更を行うことなく、Ａ＿ヘッドレジスタ７０と、Ｂ＿ヘッドレジスタ８０とが取り出されてもよい。この場合、エントリを記憶アレイ２０から要求装置に戻すために必要な時間は、記憶アレイ２０からデータを検索するために必要な時間に依存し、エントリは、要求が要求装置から受け取られるまで記憶アレイ２０から読み出されない。
【００３１】
アンロード制御ロジック５０は、バッファ１０から取り出される準備ができているタイプＡエントリが存在する場合は常に、信号をＡ＿ｖａｌｉｄ線６２に沿って、バッファ１０からエントリを受け取る装置（図示せず）に送る。アンロード制御ロジック５０は、バッファ１０から取り出される準備ができているタイプＢエントリが存在する場合は常に、Ｂ＿ｖａｌｉｄ線６４に沿って装置（図示せず）に信号を送る。本発明の上記実施形態に従って実施されるバッファ１０から読み出される１つ又は複数の装置（図示せず）は、Ａ＿ｖａｌｉｄ線６２上の信号と、Ｂ＿ｖａｌｉｄ線６４上の信号とを受け取り、任意の所与の時間に読み出し可能なエントリタイプを決定する。
【００３２】
受け取られた読み出し要求は、要求されるエントリタイプを指定する。好適な実施形態では、読み出し要求は、Ａ＿ｖａｌｉｄ線６２上、及びＢ＿ｖａｌｉｄ線６４上の各信号によって示されるように、整合するエントリタイプがバッファ１０から取り出すために利用可能なときにのみ受け取られる。代替として、利用不可能なエントリタイプに対する要求は、そのタイプのエントリがバッファ１０から取り出すため利用可能になるまで保持される。
【００３３】
要求されたエントリタイプが記憶アレイ２０内で利用可能であると想定すると、Ａ＿ヘッドレジスタ７０又はＢ＿ヘッドレジスタ８０内のエントリは、要求されたエントリタイプに従って要求装置に送られる。ロード制御ロジック４０は、当業者に既知の方法に従って記憶アレイ２０内のアドレスが現在フリーであることを通知される。ロード制御ロジック４０は、要求装置によって読み出されたエントリの位置を保持したステージレジスタから上流にある各ステージレジスタ３２ｂ〜３２ｄについて、ステージレジスタ値を一段分下流にあるレジスタに進める。すなわち、データがステージレジスタ３２ｂ内のアドレスから読み出された場合、ステージレジスタ３２ｂはステージレジスタ３２ｃの値を受け取り、ステージレジスタ３２ｃはステージレジスタ３２ｄの値を受け取り、（更にステージレジスタがある場合は）以下同様となる。最後のステージレジスタ値（図１の３２ｄ）はクリアされる。Ａ＿インデックスマルチプレクサ５２と、ＡＢ＿インデックスマルチプレクサ５４とによって選択された値は、上に述べたように、最初のＡタイプ及びＢタイプエントリそれぞれのアドレスを識別するために更新される。新しいエントリが記憶アレイ２０からの取り出しに適格である場合、その取り出しに適格な新しいエントリは、エントリタイプに依存して適するように、アレイ２０からＡ＿ヘッドレジスタ７０又はＢ＿ヘッドレジスタ８０に読み込まれる。
【００３４】
次に図２を参照すると、流れ図は、本発明の好適な実施形態に従ってタイプＡエントリを記憶アレイ２０内の空のＦＩＦＯキュー内に配置する例について実行されるステップの制御の流れを示す。本発明による記憶アレイ２０内の空のＦＩＦＯキューは、全てのステージレジスタ３２ａ〜３２ｄの有効性ビットが偽にセットされたものである。この状態では、Ａ＿ｖａｌｉｄ線６２と、Ｂ＿ｖａｌｉｄ線６４とが両方とも偽にセットされる。
【００３５】
プロセスはステップ２００で開始される。ステップ２０５において、ｔｘｎ＿ｄａｔａ＿ｉｎとして参照されるタイプＡエントリが、バッファ１０によって装置（図示せず）から受け取られる。ステップ２１０において、ロード制御ロジック４０は、ｔｘｎ＿ｄａｔａ＿ｉｎの値を記憶アレイ２０内のフリーアドレスに書き込めるようにする。ステージレジスタ３２ａが、最初の（最も下流の）フリーなステージレジスタである。ステップ２１５において、ロード制御ロジック４０は、本発明の好適な実施形態に従ってインデックスパイプ３０のステージレジスタ３２ａを空のインデックス位置として選択する。ロード制御ロジック４０がステージレジスタ３２ａを選択した後、ｔｘｎ＿ｄａｔａ＿ｉｎのタイプと、ｔｘｎ＿ｄａｔａ＿ｉｎの値がステップ２１０において書き込まれた記憶アレイ２０のアドレスとが、ステージレジスタ３２ａのタイプビットと、アドレスビットとにそれぞれ書き込まれる。ステップ２２０において、ロード制御ロジック４０はステージレジスタ３２ａの有効性ビットを真にセットする。ステップ２２５において、アンロード制御ロジック５０が記憶アレイ２０から読み出されるステージレジスタ３２ａ内のアドレスを選択し、記憶アレイ２０の対応するアドレスのデータがＡ＿ヘッドレジスタ７０にコピーされる。ステップ２３５において、アンロード制御ロジック５０はＡ＿ｖａｌｉｄ線６２を真にセットする。ステップ２４０において、プロセスは完了する。
【００３６】
次に図３を参照すると、流れ図は、図２の例を実行した後、タイプＢエントリが記憶アレイ２０内のＦＩＦＯキューに配置されるケースの例について実行されるステップの制御の流れを示す。この状態では、ステージレジスタ３２ａの有効性ビットは真にセットされ、タイプビットはタイプＡにセットされ、アドレスビットは記憶アレイ２０内のタイプＡエントリを指す。全ての他のステージレジスタ３２ｂ〜３２ｄの有効性ビットは偽にセットされる。Ａ＿ｖａｌｉｄ線６２は真にセットされ、Ｂ＿ｖａｌｉｄ線６４は偽にセットされる。
【００３７】
プロセスはステップ３００で開始される。ステップ３０５において、ｔｘｎ＿ｄａｔａ＿ｉｎとして参照されるタイプＢエントリがバッファ１０によって装置（図示せず）から受け取られる。ステップ３１０において、ロード制御ロジック４０が、ｔｘｎ＿ｄａｔａ＿ｉｎの値を記憶アレイ２０内の利用可能なアドレスに書き込めるようにする。ステップ３１５において、ロード制御ロジック４０は、図２のプロセスを実行した後で最初の（最も下流の）利用可能なステージレジスタであるステージレジスタ３２ｂを選択する。ｔｘｎ＿ｄａｔａ＿ｉｎが記憶アレイ２０内のアドレスに書き込まれた後、ｔｘｎ＿ｄａｔａ＿ｉｎのエントリタイプと、ｔｘｎ＿ｄａｔａ＿ｉｎの値がステップ３１０において書き込まれた記憶アレイ２０内のアドレスとが、ステージレジスタ３２ｂのタイプビットと、アドレスビットとにそれぞれ書き込まれる。ステップ３２０において、ロード制御ロジック４０はステージレジスタ３２ｂの有効性ビットを真にセットする。ステップ３２５において、アンロード制御ロジック５０が、エントリはＢタイプエントリであることをステージレジスタ３２ｂ内のタイプビットが示すことを決定し、上述の順序規則を適用して、ロジック５０が、ステージレジスタ３２ａによって識別されたＡタイプエントリに先行するキューからエントリを取り出すことができないことを決定する。ｔｘｎ＿ｄａｔａ＿ｉｎはステージレジスタ３２ｂにより示され、キューから取り出されるために利用することができず、Ｂ＿ｖａｌｉｄ線６４を偽にセットする。ステップ３３０において、プロセスは完了する。
【００３８】
次に図４を参照すると、流れ図は、図３の例を実行した後に、タイプＡエントリをバッファ１０から取り出す例について実行されるステップの制御の流れを示す。この状態では、ステージレジスタ３２ａの有効性ビットは真にセットされ、タイプビットはタイプＡにセットされ、アドレスビットは、記憶アレイ２０内のタイプＡエントリのアドレスを含む。ステージレジスタ３２ｂの有効性ビットは真にセットされ、タイプビットはタイプＢにセットされ、アドレスビットは記憶アレイ２０内にタイプＢエントリのアドレスを含む。他の全てのステージレジスタ３２ｃ〜３２ｄの有効性ビットは偽にセットされる。Ａ＿ｖａｌｉｄ線６２は真にセットされ、Ｂ＿ｖａｌｉｄ線６４は偽にセットされる。
【００３９】
プロセスはステップ４００で開始される。ステップ４０５において、装置（図示せず）からタイプＡエントリに対する読み出し要求がバッファ１０によって受け取られる。ステップ４１０において、Ａ＿ヘッドレジスタ７０内のｔｘｎ＿ｄａｔａ＿ｏｕｔとして参照されるエントリが要求装置に送られる。ステップ４１５において、ロード制御ロジック４０は、ｔｘｎ＿ｄａｔａ＿ｏｕｔがコピーされた記憶アレイ２０内のエントリが利用可能であることを決定する。ステップ４２０において、ロード制御ロジック４０は、ステージレジスタ３２ｂ内の値がステージレジスタ３２ａ内にコピーされ、ステージレジスタ３２ｃ内の値がステージレジスタ３２ｂ内にコピーされ、ステージレジスタ３２ｄ内の値がステージレジスタ３２ｃ内にコピーされるように、マルチプレクサ３４ａ〜３４ｄをセットする。ステップ４２５において、ステージレジスタ３２ｄがクリアされる。有利なことに、ステップ４２０及び４２５は、ロールオーバのケースに対応する必要なくＦＩＦＯキューの内容を進める。ステップ４３０において、アンロード制御ロジック５０が、記憶アレイ２０から読み出されるステージレジスタ３２ａ内のアドレスを選択し、記憶アレイ２０の対応するアドレス内におけるデータがＢ＿ヘッドレジスタ８０にコピーされる。ステップ４４０において、アンロード制御ロジック５０がＢ＿ｖａｌｉｄ線６４を真にセットする。ステップ４４５において、アンロード制御ロジック５０がＡ＿ｖａｌｉｄ線６２を偽にセットする。ステップ４５０において、プロセスは完了する。
【００４０】
次に図５を参照すると、流れ図は、図４の例を実行した後、タイプＡエントリをバッファ１０に配置する例について実行されるステップの制御の流れを示す。この状態では、ステージレジスタ３２ａの有効性ビットは真にセットされ、タイプビットはタイプＢにセットされ、アドレスビットは、記憶アレイ２０内にタイプＢエントリのアドレスを含む。他の全てのステージレジスタ３２ｂ〜３２ｄの有効性ビットは偽にセットされる。Ａ＿ｖａｌｉｄ線６２は偽にセットされ、Ｂ＿ｖａｌｉｄ線６４は真にセットされる。
【００４１】
プロセスはステップ５００で開始される。ステップ５０５において、装置（図示せず）からｔｘｎ＿ｄａｔａ＿ｉｎとして参照される新しいタイプＡエントリがバッファ１０によって受け取られる。ステップ５１０において、ロード制御ロジック４０がｔｘｎ＿ｄａｔａ＿ｉｎの値を記憶アレイ２０内の利用可能なアドレスに書き込む。ステップ５１５において、ロード制御ロジック４０は、図４のプロセスを実行した後で最初に利用可能な（最も下流の）ステージレジスタであるステージレジスタ３２ｂを選択する。ロード制御ロジック４０が、ｔｘｎ＿ｄａｔａ＿ｉｎを記憶アレイ２０内に書き込めるようにした後、ｔｘｎ＿ｄａｔａ＿ｉｎのタイプと、ｔｘｎ＿ｄａｔａ＿ｉｎの値がステップ５１０において書き込まれた記憶アレイ２０内のアドレスとが、ステージレジスタ３２ｂのタイプビットと、アドレスビットとにそれぞれ書き込まれる。ステップ５２０において、ロード制御ロジック４０はステージレジスタ３２ｂの有効性ビットを真にセットする。ステップ５２５において、アンロード制御ロジック５０が、記憶アレイ２０から読み出されるエントリのアドレスを識別するステージレジスタ３２ｂ内のアドレスを選択し、記憶アレイ２０の識別されたアドレス内におけるエントリがＡ＿ヘッドレジスタ７０に転送される（ＡタイプエントリをＢタイプエントリの前に取り出すことができることを指定する上記順序規則に従って）。ステップ５３５において、アンロード制御ロジック５０はＡ＿ｖａｌｉｄ線６２を真にセットする。ステップ５４０において、プロセスは完了する。
【００４２】
代替として、本発明の実施形態は、受け取ったエントリがすぐに、エントリ順序規則に従ってキューからの取り出しに適格である場合、アドレス指定可能な記憶アレイ構造を迂回することによってヘッドレジスタに転送されるエントリに対する１サイクルタイミングを可能にするように容易に拡張されることができる。上記実施形態のエントリ順序規則例に従って、こういったケースは、ＦＩＦＯキューが空であり且つタイプＢエントリが受け取られる時、又はＦＩＦＯキューがタイプＡエントリを含まず且つタイプＡエントリが受け取られる時が含まれる。
【００４３】
本発明の実施形態は、階層的な手法で拡張された順序規則によって任意の数のエントリタイプを処理するために拡張されることができる。例えば、エントリタイプの数がｎの場合、エントリタイプを指定する各ステージレジスタ３２ａ〜３２ｄ内のビット数はｌｏｇ２ｎでなければならない。同様に、ｎ個のヘッドレジスタ及びｎ個のインデックスマルチプレクサ（各エントリタイプに１つずつ）がなければならない。ロード制御ロジック４０及びアンロード制御ロジック５０は、当業者に既知の方法に従って変更する必要があるであろう。
【００４４】
本発明は前述で開示した態様の全てを実現することが通常の当業者により容易に認められるであろう。通常の当業者は、本明細書を読めば、各種変更、同等物の置換、及び本明細書において広義に開示した本発明の他の各種態様を行うことができるであろう。したがって、発明の保護範囲は添付の特許請求の範囲及びその同等物に含まれる規定によってのみ限定されるものであることを意図する。
【図面の簡単な説明】
【００４５】
【図１】本発明に従って使用される、単一のアドレス指定可能な記憶アレイと、本発明の原理に従ったインデックスパイプとを備えるＲＡＭの論理アーキテクチャを示すブロック図である。
【図２】本発明の好適な実施形態による、タイプＡエントリが空のＦＩＦＯキュー内に配置されている例において実行されるステップを示す流れ図である。
【図３】図２の例を実行した後の状態で、タイプＢエントリがＦＩＦＯキュー内に配置されている例において実行されるステップを示す流れ図である。
【図４】図３の例を実行した後の状態で、タイプＡのエントリがＦＩＦＯキューから取り出される例において実行されるステップを示す流れ図である。
【図５】図４の例を実行した後の状態で、タイプＡエントリがＦＩＦＯキュー内に配置されている例において実行されるステップを示す流れ図である。
【符号の説明】
【００４６】
２０  記憶アレイ
３０  レジスタ、インデックスパイプ
５０  制御ロジック
【図１】
2004348746.tif 000004
【図２】
2004348746.tif 000005
【図３】
2004348746.tif 000006
【図４】
2004348746.tif 000007
【図５】
2004348746.tif 000008