(57)【要約】　　　（修正有）【課題】待ち行列中のデータを管理するための技術を提供すること。【解決手段】一実施形態では、２つの書き込みホ゜インタが、メモリ待ち行列中へのテ゛ータの書き込みを制御し、１つの読み出しホ゜インタが待ち行列からの読み出しを制御する。該待ち行列に書き込まれる個々のエントリは、順序を変更して完成させることが可能であり、また様々な条件（該エントリに関連するホ゜インタがアクティフ゛かハ゜ッシフ゛か、他のホ゜インタがトランサ゛クションを追跡しているか否か、アクティフ゛ホ゜インタが非アクティフ゛ホ゜インタよりも低いか、高いか、又は等しいか、該テ゛ータがトランサ゛クションの最後のテ゛ータ片であるか否か等）に依存することが可能なものである。待ち行列から読み出されるテ゛ータは、該待ち行列に書き込まれたトランサ゛クションヘッタ゛の順序で読み出される。テ゛ータは、待ち行列をハ゛イハ゜スすることが可能であり、すなわち、テ゛ータを待ち行列に書き込まずに出力レシ゛スタに直接ロート゛することが可能である。【選択図】　図３Ａ
2004005471.tif 000002
【特許請求の範囲】
【請求項１】
複数のロケーション（１２０）を有する待ち行列（１１０）中のデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を管理するための方法であって、第２のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）とタイムインタリーブする第１のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を受信し、２つの識別子（ＷＰ１，ＷＰ２）を使用して第１のロケーション（１２０）を特定し、前記第１のトランザクションが受信される際に、該第１のトランザクション（１，２）に関連付けられることになる第１の識別子（ＷＰ１，ＷＰ２）がアクティブになる一方、第２の識別子（ＷＰ１，ＷＰ２）が非アクティブになり、
前記第１のトランザクションの第１のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を前記第１のロケーション（１２０）に格納し、次いでアクティブになる前記第１の識別子（ＷＰ１）を使用して、前記第１のトランザクションのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納するために前記第１のロケーション（１２０）を特定し、前記第１のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１のロケーション（１２０）に格納されるまで前記データ片の格納を行い、
前記第２の識別子（ＷＰ１，ＷＰ２）を使用して、前記第１のロケーション（１２０）よりも１つ高いロケーションである第２のロケーション（１２０）を特定する、
という各ステップを有する方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般にデータ管理に関し、特に待ち行列内のデータ管理に関する。
【０００２】
【従来の技術】
一般に、ポインタ及びレジスタは、メモリ待ち行列内の次に利用可能な書き込み場所を絶えず追跡する。しかし、先入れ先出し（ＦＩＦＯ）待ち行列を含む現行の様々な待ち行列機構は、あまりにも多くのポインタ及び／又はレジスタを使用する、逐次的にしかデータを書き込むことができない、といった問題点に直面している。
【０００３】
【発明が解決しようとする課題】
本発明の目的は、上記の欠点及びそれに関連する問題点を解決するための機構を提供することにある。
【０００４】
【課題を解決するための手段】
本発明は、様々な実施形態で待ち行列内のデータを管理するための技術を提供する。一実施形態では、２つの書き込みポインタがメモリ待ち行列への書き込みを制御し、１つの読み出しポインタが待ち行列からの読み出しを制御する。該待ち行列に書き込まれる個々のエントリは、順序を変更して完成させることが可能なものであり、また様々な条件（該エントリに関連するポインタがアクティブかパッシブか、他のポインタがトランザクションを追跡しているか否か、アクティブポインタが非アクティブポインタよりも低いか、高いか、又は等しいか、該データがトランザクションの最後のデータ片であるか否か等）に依存することが可能なものである。待ち行列から読み出されるデータは、該待ち行列に書き込まれたトランザクションヘッダの順序で読み出される。データは、待ち行列をバイパスすることが可能であり、すなわち、データを待ち行列に書き込まずに出力レジスタに直接ロードすることが可能である。
【０００５】
【発明の実施の形態】
以下で解説し図示する本発明は、その一例を示したものであって本発明の制限を意図したものではない。なお、図面においては、同様の符号は同様の構成要素を示している。
【０００６】
例示を目的とした以下の説明では、本発明を細かい点まで理解してもらうために、多数の具体的な細部が記載される。しかし、本発明がこれらの具体的な細部を用いることなく実施することが可能であることは当業者には明らかであろう。他の例では、本発明が不明瞭になるのを回避すべく、周知の構造及び素子はブロック図の形で示した。
【０００７】
システム概要
図１は、一実施形態によるシステム１００を示している。該システム１００は、待ち行列１１０と、２つの書き込みポインタＷＰ−１，ＷＰ−２と、１つの読み出しポインタＲＰと、２つの出力レジスタ１３０−１，１３０−２と、２つのマルチプレクサ（ＭＵＸ）１４０，１５０とを含む。該システム１００は、チップ、素子、及びネットワーク化されたシステム間のデータのバッファリング、転送、及びスイッチングやマルチプロセッサアプリケーションといった様々な用途、及びそれと同等の用途で用いることが可能である。
【０００８】
待ち行列１１０は、Ｎ個の場所のためのロケーション１２０−１，１２０−２，．．，１２０−Ｎを含む。一実施形態では、待ち行列１１０は循環し、すなわち、最後のロケーション（例えばロケーション１２０−Ｎ）が占有されている場合に次のトランザクションデータがロケーション１２０−１，１２０−２，１２０−３等に格納される。一例として、待ち行列１１０が満杯になり又は循環する度に、待ち行列１１０内の各ロケーションの接尾部が数Ｎだけインクリメントされる。例えば、ロケーション１２０−１は、第１の循環、第２の循環、及び第３の循環の場合に、それぞれロケーション１２０−（Ｎ＋１）、１２０−（２Ｎ＋１）及び１２０−（３Ｎ＋１）とみなされ、ロケーション１２０−２は、第１の循環、第２の循環、及び第３の循環の場合に、それぞれロケーション１２０−（Ｎ＋２）、１２０−（２Ｎ＋２）及び１２０−（３Ｎ＋２）とみなされる（以下同様）ことになります。大きな番号を有するロケーションは、小さな番号を有するロケーションよりも「高く」、例えば、ロケーション１２０−２はロケーション１２０−１よりも高く、ロケーション１２０−３はロケーション１２０−２よりも高くなります。しかし、待ち行列１１０が循環する場合には、ロケーション１２０−１はロケーション１２０−Ｎより高くなる。これは、かかる状況では上述のようにロケーション１２０−１がロケーション１２０−（Ｎ＋１）とみなされるためである。この図１の例では、ロケーション１２０は物理的に連続するものとして示されるが、ロケーション１２０は、論理的に連続するものとすることが可能であり、すなわち、各論理的なロケーションは、異なる場所にそれぞれ存在する物理的なロケーションに対応することが可能である。
【０００９】
出力レジスタ１３０は、ライン１０６０に出力するためのデータを格納する。一実施形態では、特定の１サイクルで、一方のレジスタ１３０のみがアクティブとなり、他方のレジスタ１３０が非アクティブとなる。例えば、レジスタ１３０−１がアクティブになる場合には、レジスタ１３０−２が非アクティブになる（逆もまた同様）。アクティブレジスタは（それが利用可能な場合には）、待ち行列１１０から読み出され又は待ち行列１１０をバイパスした、ライン１０５５上のデータを格納する。レジスタ１３０は、特定の１サイクルでレジスタが既に空であり又はクリアされている（すなわち該レジスタに格納されているデータが読み出されている）場合には、同サイクルで新たなデータを格納するために利用することができる。アクティブレジスタ１３０が新たなデータを受信する度に、該アクティブレジスタ１３０が非アクティブに切り替わり、非アクティブレジスタ１３０がアクティブに切り替わる。
【００１０】
各レジスタ１３０は、バイパス指示子、ロード指示子、及びクリア指示子（これらは一般にフラグと呼ばれる）に関連付けられる。バイパスフラグは、それがアサートされた際に、受信され対応するレジスタに格納されるデータが待ち行列１１０をバイパスすることを示すものである。一実施形態では、バイパスフラグは、対応するレジスタ１３０がアクティブであってデータを格納するために利用可能であり、該データが１つの要素からなるトランザクションであり、及び待ち行列１１０が空である場合に、アサートされる。ロードフラグは、そのアサート時に、対応するレジスタ１３０に格納されるデータがバイパスされずに待ち行列１１０から受信されたことを示すものである。結果的に、ロードフラグは、バイパスフラグがアサートされず、レジスタ１３０がアクティブであってデータを格納するために利用することが可能であり、及び待ち行列１１０の１つのロケーションにトランザクションデータが完全に書き込まれている場合に、アサートされる。クリアフラグは、そのアサート時に、対応するレジスタが新たなデータを格納するために利用可能であることを示す。該クリアフラグは、バイパスフラグ及びロードフラグがアサートされず、レジスタがアクティブレジスタであり、及び関連するトランザクションの第１の要素が現在のサイクルにおいてレジスタから読み出される場合に、アサートされる。換言すれば、新たなデータがロードされず、現在のレジスタの内容が除去されている場合に、クリアフラグがアサートされる。
【００１１】
Ｍｕｘ１４０は、ライン１０４５上の待ち行列１１０から、又は待ち行列１１０に書き込まれることになるデータを運ぶライン１０５０から、データを選択する。Ｍｕｘ１４０がライン１０５０からデータを選択する場合には待ち行列１１０はバイパスされる。Ｍｕｘ１５０は、ライン１０６０上に出力されることになるデータをレジスタ１３０−１，１３０−２の何れかから選択する。Ｍｕｘ１４０，１５０は、単なる一例として用いたものであり、様々な入力の中から１つの出力を選択するための任意の機構を用いることが可能である。
【００１２】
書き込みポインタＷＰは、データが書き込まれる待ち行列１１０のロケーションを特定する。読み出しポインタＲＰは、データが読み出される待ち行列１１０のロケーションを特定する。第１のポインタが第２のポインタのロケーションより高いロケーションを指す場合には、第１のポインタは第２のポインタよりも「高い」。逆に、第１のポインタが第２のポインタより低いロケーションを指す場合には、第１のポインタは第２のポインタよりも「低い」。同様に、第１のポインタが第２のポインタと同じロケーションを指す場合には、第１のポインタは第２のポインタと「等しい」。一例として、最初に又は待ち行列１１０がリセットされた際、書き込みポインタＷＰ−１，ＷＰ−２及び読み出しポインタＲＰは同じロケーション１２０−１を指す。例示のため「ポインタ」なる用語を用いるが、任意の識別子又は機構を用いて、待ち行列１１０に対して書き込み及び読み出しを行うためのロケーションを特定することができる。
【００１３】
データ
一実施形態では、待ち行列１１０は、様々なサイクル（例えばサイクル１からサイクルｎ）においてライン１０５０上のデータストリームを受信する。データストリームは、一般にトランザクションとして送信され、様々な部分又はデータ片（論理的には連続するが物理的には必ずしも連続しないもの）から構成される一組の情報を含むものである。すなわち、データの一部が、１つ又は２つ以上の他のストリームの幾つかの部分によって挟まれる場合がある。その結果、該データは、「タイムインタリーブ」と呼ばれる場合があり、トランザクションは、サイクル１〜ｎのうちの１つ又は２つ以上のサイクルにデータを含まない場合がある。データトランザクションの第１のデータ片が第１のサイクル（例えばサイクル１）において受信され、該データの最後のデータ片が最後のサイクル（例えばサイクルｎ）において受信される。トランザクションが１つのデータ片しか有さない場合には、該データ片は１サイクル（例えばサイクル１）において受信される。
【００１４】
一実施形態では、データストリーム又はトランザクションは、複数のチャネルでライン１０５０を介して待ち行列１１０に到着する。所与の１サイクルで、１つのチャネルは「アクティブ」又は「非アクティブ」となり、アクティブチャネルは、データが該チャネルから来ることを示し、非アクティブチャネルは、データが該チャネルから来ないことを示す。更に、一般に交互にアクティブになる２つのチャネル（例えばチャネルＡ，Ｂ）が存在する。特定の１サイクルで、１つのデータ片が存在する場合には、該データ片は、該サイクルでアクティブなチャネルに関連付けられる。データストリームのデータ片が特定の１チャネルに関連付けられると、該データストリームの残りのデータ片もまた同じチャネルに関連付けられる。１つのチャネルは、第１のデータストリームとの関連付けが終了するまで、第２のデータストリームと関連付けられることはない。
【００１５】
一実施形態では、データストリームは、任意の時点で停滞することができる。更に、特定の１つのデータ片が停滞する場合、該データ片に関連付けられたチャネルは、該データ片が到着するまでアクティブのままとなる。２つのチャネル（例えばチャネルＡ，Ｂ）を有し、停滞することがのない、２チャネルシステムでは、Ａ１，Ａ２，Ａ３，Ａ４が第１のトランザクションのデータ片であり、Ｂ１，Ｂ２，Ｂ３が第２のトランザクションのデータ片である場合には、それらデータ片は、データ片Ａ１　Ｂ１　Ａ２　Ｂ２　Ａ３　Ｂ３　Ａ４等に対応するチャネルＡ　Ｂ　Ａ　Ｂ　Ａ　Ｂ　Ａで交互に到着する。別の例では、データ片Ａ２が、１サイクル、２サイクル、及び３サイクルにわたり停滞する場合には、アクティブチャネルに関するシーケンスは、それぞれ、Ａ　Ｂ　Ａ　Ａ　Ｂ　Ａ　Ｂ　Ａ、Ａ　Ｂ　Ａ　Ａ　Ａ　Ｂ　Ａ　Ｂ　Ａ、及びＡ　Ｂ　Ａ　Ａ　Ａ　Ａ　Ｂ　Ａ　Ｂ　Ａとなる。
【００１６】
一実施形態では、待ち行列１１０によって受信されて格納されるデータは、他のロケーションに格納されるデータに対応する情報を含み、該情報から該データを特定することが可能となる。典型的な情報としては、状態、制御、ロケーション、タイプ、サイズ、品質（例えばデータが良いか悪いか）等が挙げられる。
【００１７】
１つのトランザクションに関する全てのデータ片は、該データ片が受信されるサイクルにかかわらずトランザクションベースで（例えば待ち行列の１つのロケーションに）格納される。例えば、１つのトランザクションは、５つのサイクルが完全に受信されることを必要とし、それゆえ、該５つのサイクルで受信されるデータが完全に格納されることを必要とする可能性がある。該トランザクションの全てのデータ片が待ち行列１１０に書き込まれたとき（通常は最後のデータ片が待ち行列１１０に書き込まれたとき）、該トランザクションが待ち行列１１０に完全に書き込まれたことになる。１つ又は２つ以上のトランザクションが完全に書き込まれていない場合であっても、多数のデータトランザクションを待ち行列１１０中への書き込み処理中とすることが可能である。トランザクションのヘッダ又は最初のデータ片を受信する順序は、該トランザクションのデータが書き込まれることになる待ち行列１１０のロケーションの順序を構成し、それゆえ待ち行列１１０から読み出されることになる順序を構成するものとなる。一実施形態では、トランザクションの第１のデータ片は、最初に、最も低いロケーション（例えばロケーション１２０−１）に書き込まれ、後続のトランザクションの第１のデータ片は、それよりも高いロケーションに書き込まれる。例えば、第１のトランザクションの第１のデータ片がロケーション１２０−１に書き込まれ、第２のトランザクションの第１のデータ片がロケーション１２０−２に書き込まれ、第３のトランザクションの第１のデータ片がロケーション１２０−３に書き込まる（以下同様）。トランザクションデータのサイズが変動するため、及び／又はデータ片が異なる時刻に到着するため、待ち行列１１０で最初に受信されて参照されるトランザクションは必ずしも待ち行列１１０に完全に書き込まれる最初のトランザクションとは限らない。
【００１８】
トランザクションデータが待ち行列１１０に格納される態様の例示
図２Ａを参照する。同図は、トランザクションデータが待ち行列１１０に如何に格納されるかを示している。同図は、ロケーション１２０−１，１２０−２，１２０−３，１２０−４にそれぞれ４つのトランザクション１，２，３，４のためのデータを有する待ち行列１１０を示している。トランザクション１は４つのデータ片１−１，１−２，１−３，１−４を有し、トランザクション２は２つのデータ片２−１，２−２を有し、トランザクション３は３つのデータ片３−１，３−２，３−３を有し、トランザクション４は１つのデータ片４−１を有する。トランザクション１，２，３，４のための第１のデータ片はそれぞれ１−１，２−１，３−１，４−１である。この例では、待ち行列１１０は、１−１，２−１，３−１，４−１の順序で、４つのトランザクションのための第１のデータ片を受信し、それらデータ片をそれぞれロケーション１２０−１，１２０−２，１２０−３，１２０−４の順序で格納する。各トランザクションに関し、待ち行列１１０は、トランザクション１の場合には１−１，１−２，１−３，１−４の順序でデータを受信し、トランザクション２の場合には２−１，２−２の順序でデータを受信し、トランザクション３の場合には３−１，３−２，３−３の順序でデータを受信する。これらデータ片が受信されるとき、該データ片はそれらに応じて格納され、例えば、データ片１−２，１−３，１−４はデータ片１−１と同じロケーションに格納され、データ片２−２はデータ片２−１と同じロケーションに格納され、データ片３−２，３−３はデータ片３−１と同じロケーションに格納される（以下同様）。
【００１９】
データが待ち行列１１０に到着することができる態様の例示
図２Ｂは、本発明の一実施形態に従って図２Ａのデータが待ち行列１１０に如何にして到着することが可能であるかの一例を示している。この例は、２チャネルシステム（例えばチャネルＡ及びチャネルＢ）を用いる。更に、データが停滞することなく、データ片はチャネルＡ，Ｂに交互に到着する。最初に、トランザクション１がチャネルＡに関連付けられて、データ片１−１，１−２，１−３，１−４がそれぞれサイクル１，３，５，７で到着する。トランザクション２はチャネルＢに関連付けられ、データ片２−１，２−２がそれぞれサイクル２，４で到着する。トランザクション３はチャネルＡに関連付けられ、データ片３−１，３−２，３−３がそれぞれサイクル９，１１，１４で到着する。トランザクション４はチャネルＢに関連付けられ、唯一のデータ片４−１がサイクル１０で到着する。
【００２０】
トランザクション１，３はチャネルＡに関連付けられるので、該トランザクション１，３の全てのデータ片はチャネルＡで到着する。同様に、トランザクション２，４はチャネルＢに関連付けられるので、該トランザクション２，４の全てのデータ片はチャネルＢで到着する。
【００２１】
チャネルＡはサイクル７の後にトランザクション１との関連付けを終了し、それゆえサイクル９を開始する際に利用可能となる。チャネルＢはサイクル４の後にトランザクション２との関係を終了し、それゆえサイクル６を開始する際に利用可能となる。しかし、この例では、サイクル６又はサイクル８ではデータは到着しない。トランザクション３，４はサイクル９，１０で開始し、それゆえ、その際に利用可能なチャネルＡ，Ｂにそれぞれ関連付けられる。チャネルＢはまたサイクル１０の後にトランザクション４との関係を終了し、それゆえ、サイクル１２を開始する際に利用可能となる。しかし、別の例として、サイクル１２では新たなトランザクションは到着しない。
【００２２】
サイクル１３では、トランザクション３に関するデータ片３−３が停滞する。それゆえ、該データ片３−３を運んでいるチャネルＡは次のサイクル１４でアクティブのままとなる。この例では、データ片３−３はサイクル１４で到着する。しかし、一例として、データ片３−３が更に長いサイクルにわたり停滞する場合には、チャネルＡは更に先のサイクル、例えばサイクル１５にわたりアクティブのままとなる。同様に、データ片３−３が１サイクルではなく２サイクルにわたり更に停滞する場合には、チャネルＡは、更なる２サイクル（例えばサイクル１５，１６）にわたりアクティブのままとなる（以下同様）。
【００２３】
書き込み動作
書き込みポインタＷＰは、データが書き込まれる待ち行列１１０の適当なロケーションを決定するためのロジックを制御する。書き込みポインタは、以前に指していたロケーションに留まる（すなわち該ロケーションを指す）こと、インクリメントする（すなわち待ち行列１１０中で１つ上のロケーションに移動する）こと、又はジャンプする（すなわち１つよりも多く上のロケーションに移動する）ことができる。一例として、１つのアクティブチャネルに関連付けられる書き込みポインタはアクティブポインタと呼ばれ、一方、非アクティブチャネルに関連付けられる書き込みポインタは非アクティブポインタと呼ばれる。一実施形態では、該２つのポインタＷＰのうちの一方のみが１サイクルでアクティブとなる。例えば、ポインタＷＰ−１がアクティブである場合にはポインタＷＰ−２は非アクティブであり、同様に、ポインタＷＰ−１が非アクティブである場合にはポインタＷＰ−２はアクティブである。書き込みポインタがトランザクションの第１のデータ片を指す際に、該ポインタは該トランザクションの追跡を開始し、該トランザクションが完了した際（すなわち該トランザクションに関する全てのデータ片が受信されて待ち行列１１０中の１ロケーションに格納されたとき）、該トランザクションの追跡を終了する。例えば、ポインタＷＰ−１が、ロケーション１１０−１を指しており、及びトランザクション１に関するデータ片１−１が到着した際に新たなトランザクションを追跡するために利用可能である場合には、該ポインタＷＰ−１は、該トランザクション１に関する全てのデータ片が該ロケーション１１０−１に格納されるまで該トランザクション１を追跡し、その後、ポインタＷＰ−１は新たなトランザクションを追跡するために利用可能となる。
【００２４】
一実施形態では、システム１００は以下の規則に従って動作する。
・リセット
待ち行列１１０がリセットされる場合には、ポインタＷＰ−１，ＷＰ−２の両者もリセットされる（例えば最も低いロケーション１２０−１を指す）。
・データが受信されない場合
１サイクル中にトランザクションデータが到着しない場合には、ポインタＷＰ−１，ＷＰ−２は何れもそれらが指しているのと同じロケーションを指したままとなる。
【００２５】
以下の動作では、待ち行列１１０に書き込まれることになる１つのデータ片が到着する（すなわちバイパスが存在しない）ものと仮定する。更に、特に明記しない限り、データ片はトランザクションの最後のデータではない。一般に、トランザクションを追跡するポインタは、該トランザクションが完全に受信されるまで、該トランザクションに関するデータを格納するためのロケーションを指したままとなる。
・書き込みポインタが等しい場合
ポインタＷＰ−１，ＷＰ−２が等しい場合、ポインタは何れも新たなトランザクショ　　　ンを追跡するために利用可能である。この状態の間、各ポインタは交互にアクティブ及び非アクティブになる。ある１サイクルで新たなトランザクションの第１のデータ片が到着した場合、該データ片は両方のポインタによって指し示されるロケーションに書き込まれる。次いで、アクティブポインタが、該データ片に関連するトランザクションの追跡を開始し、該トランザクションが完了するまで、該トランザクションを追跡したままとなる。非アクティブポインタは、新たなトランザクションを追跡するために１だけインクリメントされる。その結果として、２つのポインタが等しくなくなり、一方のポインタが新たなトランザクションのために利用可能となり、他方のポインタが進行中のトランザクションを追跡することになる。
【００２６】
しかし、データが１つのデータ片からなるトランザクションである（例えば、最初のデータ片が最後のデータ片でもある）場合には、該データ片は両方のポインタによって指し示されるロケーションに書き込まれ、両方のポインタが１だけインクリメントされ、新たなトランザクションを追跡するために利用可能となる。このため、両方のポインタは等しいままとなる。
・２つのポインタが等しくない場合
この場合には、少なくとも１つのポインタがトランザクションを追跡する。
・一方のポインタが進行中のトランザクションを追跡しており、もう一方のポインタが新たなトランザクションを追跡するために利用可能である場合
一実施形態では、利用可能なポインタの方が（ロケーションが）高く、トランザクションを追跡中のポインタは（該利用可能なポインタよりもロケーションが）低い。この実施形態では、トランザクションを追跡中のポインタは、高くなることが許されない、ということに留意されたい。
【００２７】
新たなトランザクションに関するデータが受信される場合、該データは、利用可能なポインタによって指し示されるロケーションに書き込まれ、該利用可能なポインタは、該トランザクションが完了するまで、該新たなトランザクションの追跡を開始する。その結果として、この時点で２つのトランザクションが進行中になる。しかし、データが１つのデータ片からなるトランザクションである場合には、該トランザクションは完了し、「利用可能な」ポインタも１だけインクリメントされる。この場合には、進行中のトランザクションが１つだけ存在する（例えば、一方のポインタのみがトランザクションを追跡しており、他方のポインタが新たなトランザクションを追跡するために利用可能である）状況に戻る。
【００２８】
しかし、該データが進行中のトランザクションに関するものである場合には、該データは、トランザクションを追跡中のポインタによって指し示されるロケーションに書き込まれ、このトランザクションを追跡中のポインタは、該トランザクションが完了するまで同じロケーションに指し示したままとなる。該データが最後のデータ片でもある（すなわち該トランザクションが完了する）場合には、トランザクションを追跡中のポインタは、「利用可能な」ポインタによって指し示されるロケーションにジャンプする。これにより、２つのポインタが等しい状況に戻る。
・各書き込みポインタがトランザクションを追跡している場合
受信されたデータは、該データのトランザクションに対応するロケーションに書き込まれる。ポインタは、該ポインタによって追跡されたトランザクションが完了するまで、同じロケーションを指し示したままとなる。高い方のポインタに対応するトランザクションが完了したとき、該高い方のポインタが１だけインクリメントされる。しかし、低い方のポインタに対応するトランザクションが完了したときには、該低い方のポインタは、前記高い方のポインタ＋１により指し示されるロケーションにジャンプする。両方の状況は、一方のポインタが新たなトランザクションのために利用可能であり、もう一方のポインタが進行中のトランザクションを追跡している状況に戻る。
【００２９】
待ち行列１１０にデータを書き込むための上記規則及び技術を用いることにより、書き込みを行うために次に利用可能なロケーションを追跡するための更なるポインタが必要となる。これは、次に利用可能なロケーションを上記の適用可能な条件に基づいて決定することができるからである。
・データ片を書き込む際の典型的なステップ
ここで図３Ａ〜３Ｃを参照する。同図は、データ片が図２Ｂの順序で待ち行列１１０に到着するものと仮定した場合に、図２Ａのデータ片が一実施形態に従って様々なステップを介して待ち行列１１０に如何にして格納されるかを示している。該図３Ａ〜３Ｃ中の各図は１サイクルに対応するものである。
【００３０】
最初にサイクル０で、待ち行列１１０は空であり、ポインタＷＰ−１，ＷＰ−２は何れも同じロケーション１２０−１を指す。データが到着するのを待つ間、各ポインタは交互にアクティブになり、例えば、あるサイクルではアクティブになり、次のサイクルでは非アクティブになる。更に、一方のポインタがアクティブであるとき、他方のポインタは非アクティブである（逆もまた同様）。
【００３１】
一例として、サイクル１では、ポインタＷＰ−１はアクティブであり、ポインタＷＰ−２は非アクティブであり、トランザクション１のデータ片１−１が到着する。次いで、データ片１−１はロケーション１２０−１に書き込まれる。ポインタＷＰ−１がアクティブであるので、この時点でポインタＷＰ−１はトランザクション１を追跡している。更に、データ片１−１はトランザクション１の最後のデータではないので、ポインタＷＰ−１はトランザクション１を追跡したまま（例えばロケーション１２０−１を指したまま）となる。ポインタＷＰ−２は、サイクル２に示すように、１つのロケーションだけ（例えばロケーション１２０−２へと）インクリメントされる。ポインタＷＰ−２は、新たなトランザクションが到着した際に該新たなトランザクションを追跡することになる。図２Ｂの例では、トランザクション１はチャネルＡに関連付けられるので、この時点でポインタＷＰ−１はチャネルＡに関連付けられる。次いで、ポインタＷＰ−２及びポインタＷＰ−１は、サイクル２で用いるためにそれぞれアクティブ及び非アクティブになる。
【００３２】
サイクル２では、トランザクション２のデータ片２−１が到着する。ポインタＷＰ−２は、アクティブであり、かつ利用可能であるので、トランザクション２の追跡を開始する。このため、データ片２−１は、ポインタＷＰ−２によって指し示されるロケーション１２０−２に書き込まれる。トランザクション２はチャネルＢに関連付けられるので、この時点でポインタＷＰ−２はチャネルＢに関連付けられる。トランザクション１及びトランザクション２が何れも完了していないので、ポインタＷＰ−１，ＷＰ−２は何れも、それぞれ同じロケーション１２０−１及びロケーション１２０−２を指したままとなる。次いで、ポインタＷＰ−１及びポインタＷＰ−２は、サイクル３で用いるためにそれぞれアクティブ及び非アクティブになる。
【００３３】
サイクル３では、データ片１−２が到着し、アクティブポインタＷＰ−１によって指し示されるロケーション１２０−１に書き込まれる。該データ片１−２は最後のデータ片ではないので、ポインタＷＰ−１は同じロケーション１２０−１を指し示したままとなる。次いで、ポインタＷＰ−２及びポインタＷＰ−１は、サイクル４で用いるためにそれぞれアクティブ及び非アクティブになる。
【００３４】
サイクル４では、データ片２−２が到着し、アクティブポインタＷＰ−２によって指し示されるロケーション１２０−２に書き込まれる。データ片２−２はトランザクション２の最後のデータ片であるので、トランザクション２は完了する。更に、ポインタＷＰ−２が高い方であるので、サイクル５に示すように、１だけ（例えばロケーション１２０−３へと）インクリメントされる。次いで、ポインタＷＰ−１及びポインタＷＰ−２は、サイクル５で用いるためにそれぞれアクティブ及び非アクティブになる。
【００３５】
サイクル５では、データ片１−３が到着し、アクティブポインタＷＰ−１によって指し示されるロケーション１２０−１に書き込まれる。該データ片１−３は最後のデータ片ではないので、ポインタＷＰ−１は同じロケーション１２０−１を指し示したままとなる。ポインタＷＰ−２及びポインタＷＰ−１は、サイクル６で用いるためにそれぞれアクティブ及び非アクティブになる。
【００３６】
図２Ｂに示されるように、サイクル６では、データは到着せず、それゆえポインタＷＰ−１，ＷＰ−２は何れも同じロケーション１２０−１及び１２０−３をそれぞれ指し示したままとなる。しかし、次いで、ポインタＷＰ−１及びポインタＷＰ−２は、サイクル７で用いるためにそれぞれアクティブ及び非アクティブになる。
【００３７】
サイクル７で、データ片１−４が到着し、アクティブポインタＷＰ−１によって指し示されるロケーション１２０−１に書き込まれる。該データ片１−４はトランザクション１に関する最後のデータであるので、トランザクション１は完了する。更に、ポインタＷＰ−１は低い方であり、書き込みポインタＷＰ−２はトランザクションを追跡中ではないので、書き込みポインタＷＰ−１は、サイクル８に示すように、ポインタＷＰ−２によって指し示されるロケーションに（例えば１２０−３へと）ジャンプする。
【００３８】
サイクル７の後、書き込みポインタＷＰ−１，ＷＰ−２は何れも利用可能であるので、一実施形態では、それらは交互にアクティブ及び非アクティブになる。サイクル８では、データが到着しないため、ポインタＷＰ−１，ＷＰ−２は同じロケーション１２０−３を指し示したままとなる。
【００３９】
サイクル９で、トランザクション３のデータ片３−１が到着し、一実施形態では、両方のチャネルＡ，Ｂが利用可能であるので、該データ片３−１は、チャネルＡ、チャネルＢの何れかに到着することができ、ポインタＷＰ−１，ＷＰ−２の何れか一方がアクティブになる（すなわち、ポインタＷＰ−１，ＷＰ−２の何れか一方をトランザクション３の追跡に用いる）ことができる。一例として、データ片３−１がチャネルＡに到着し、書き込みポインタＷＰ−２がアクティブであり、該ポインタＷＰ−２がトランザクション３の追跡を開始する。こうして、データ片３−１がロケーション１２０−３に書き込まれる。該データ片３−１はトランザクション３の最後のデータではないので、アクティブポインタＷＰ−２は、ロケーション１２０−３を指し示したままとなり、トランザクション３を追跡し続ける。しかし、非アクティブポインタＷＰ−１は、サイクル１０に示すように１だけインクリメントされ、新たなトランザクションが到着した際に該トランザクションを追跡するために利用可能である。次いで、ポインタＷＰ−１，ＷＰ−２は、サイクル１０で用いるためにそれぞれアクティブ及び非アクティブになる。
【００４０】
サイクル１０では、データ片４−１が到着し、アクティブポインタＷＰ−１によって指し示されるロケーション１２０−４に書き込まれる。該データ片４−１がトランザクション４の最後のデータ片であり、ポインタＷＰ−１が高い方であるので、ポインタＷＰ−１は、サイクル１１に示すように、１だけインクリメントされてロケーション１２０−５を指す。次いで、ポインタＷＰ−２，ＷＰ−１は、サイクル１１で用いるために、それぞれアクティブ及び非アクティブになる。
【００４１】
サイクル１１で、データ片３−２が到着し、アクティブポインタＷＰ−２によって指し示されるロケーション１２０−３に書き込まれる。該データ片３−２はトランザクション３の最後のデータ片ではないので、ポインタＷＰ−２は同じロケーション１２０−３を指し示したままとなる。次いで、ポインタＷＰ−１及びポインタＷＰ−２は、サイクル１２で用いるために、それぞれアクティブ及び非アクティブになる。
【００４２】
サイクル１２では、一例として、データが到着しないため、ポインタＷＰ−１，ＷＰ−２は何れもそれぞれ同じロケーション１２０−５，１２０−３を指し示したままとなる。しかし、ポインタＷＰ−２，ＷＰ−１は、サイクル１３で用いるためにそれぞれアクティブ及び非アクティブになる。
【００４３】
サイクル１３では、データ片３−３がチャネルＡに到着することが可能である。しかし、一例として、データ片３−３は停滞することとする。一実施形態では、データ片３−３が停滞するため、チャネルＡひいては書き込みポインタＷＰ−２はアクティブのままとなる。
【００４４】
サイクル１４では、データ片３−３がチャネルＡに到着し、アクティブポインタＷＰ−２によって指し示されるロケーション１２０−３に書き込まれる。該データ片３−３がトランザクション３の最後のデータ片であり、ポインタＷＰ−２が低い方であり、及びポインタＷＰ−１がトランザクションを追跡していないため、ポインタＷＰ−２は、サイクル１５に示すように、ポインタＷＰ−１によって指し示されるロケーション１１０−５にジャンプする。
【００４５】
上記の例では、サイクル０，８，１５において、２つのポインタＷＰ−１，ＷＰ２は、何れも新たなトランザクションを追跡するために利用可能であるため、同じロケーション（例えばロケーション１２０−１，１２０−３，１２０−５）を指し示している。
・バイパス動作
一実施形態では、レジスタ１３０のうちの１つがデータを格納するために利用可能な場合に、トランザクションのデータは、待ち行列１１０をバイパスする（例えば、該データが待ち行列１１０に書き込まれずに前記レジスタ１３０のうちの１つに直接ロードされる）ことが可能である。一実施形態では、待ち行列１１０が空であり１つのデータ片からなるトランザクションが受信される場合に、該データがバイパスされる。一般に、待ち行列１１０が空である場合には、読み出しポインタＲＰは２つの書き込みポインタＷＰ−１，ＷＰ−２と等しくなる。バイパスの後、読み出しポインタＲＰ及び２つの書き込みポインタＷＰは、それらが指し示しているロケーションと同じロケーションを指したままとなる。
・読み出し動作
読み出しポインタＲＰは、データが読み出されるロケーションを指す。一実施形態では、読み出しは受信されたトランザクションの順序どおりに行われるので、読み出しポインタＲＰは、低い方の書き込みポインタＷＰを通り越すことは許されない。すなわち、読み出しポインタＲＰによって指し示されるロケーションは、低い方の書き込みポインタによって指し示されるロケーションと等しいか、それよりも低いものとなる。２つの書き込みポインタが等しい場合には、読み出しポインタＲＰによって指し示されるロケーションは、両方の書き込みポインタによって指し示されるロケーションと等しいか、それより低くなる。
【００４６】
一実施形態では、トランザクションの第１の要素が読み出されるサイクルと同じサイクルにおける単一のイベントとして、該トランザクションの該第１の要素が待ち行列１１０に書き込まれた順序で、待ち行列１１０からデータが読み出される。代替的には、データは、低い方のロケーションから高い方のロケーションに向かう順序で読み出される。図２Ａの例では、トランザクション１、トランザクション２、トランザクション３、及びトランザクション４にそれぞれ関連するロケーション１、ロケーション２、ロケーション３、及びロケーション４の順序でデータが読み出される。データが読み出された後、読み出しポインタＲＰが１だけインクリメントされ、該データが読み出されたロケーションは、新たなデータを格納するために利用可能となる。最初に又はリセット時に、読み出しポインタＲＰは最も低いロケーション（例えばロケーション１２０−１）を指す。
【００４７】
上記の例では、２つの書き込みポインタが使用され、２つのデータチャネルに対応している。しかし、本発明は、２ポインタシステムには限定されず、１つの書き込みポインタが１つのチャネルに対応する様々な書き込みポインタを有するシステムに適用することが可能である。１つの書き込みポインタは、適当な場合には、１つのトランザクションを追跡する。例えば、５つのチャネルが存在する場合には、５つの書き込みポインタが存在し、その各々が、待ち行列１１０への書き込み過程にあるトランザクションを１つずつ追跡することが可能である。同様に、Ｍチャネルが存在する場合には、Ｍ個の対応する書き込みポインタが存在し、その各々が、待ち行列１１０への書き込み過程にあるトランザクションを１つずつ追跡することが可能である。１つのポインタは、１つのトランザクションが完全に受信されるまで、該トランザクションを追跡する。
【００４８】
一般に、新たなトランザクションを追跡するために利用することが可能な全てのポインタは等しく、１サイクル中では１つのポインタがアクティブになり、利用可能なポインタの残りが非アクティブになる。新たなトランザクションが到着した際に、該アクティブで利用可能なポインタが該到着したトランザクションの追跡を開始し、全ての利用可能な非アクティブポインタが１だけインクリメントされる。しかし、該トランザクションが１つのデータ片しか持たない場合には、全ての利用可能なポインタが１だけインクリメントされる。更に、新たなトランザクションを追跡するために利用することが可能なポインタは、進行中のトランザクションを追跡しているポインタよりも高くなる。トランザクションを追跡しているポインタは、該トランザクションが完了するまでロケーションを変更しない。
【００４９】
一実施形態では、少なくとも１つのポインタが１つのトランザクションを追跡している際に、１つのトランザクションを追跡する最も高いポインタが基準として用いられる。この最も高い書き込みポインタに対応するトランザクションが完了した場合には、該最も高い書き込みポインタが１だけインクリメントされる。しかし、この最も高い書き込みポインタではないポインタは、この最も高い書き込みポインタ＋１にジャンプする。
・コンピュータシステムの概要
図４は、本発明の一実施形態を実施することが可能なコンピュータシステム４００を示すブロック図である。例えば、コンピュータシステム４００は、本書に開示する技術等を実施し及び／又は実行するために、システム１００を含むよう実施することが可能である。一実施形態では、コンピュータシステム４００は、プロセッサ４０４、ランダムアクセスメモリ（ＲＡＭ）４０８、リードオンリーメモリ（ＲＯＭ）４１２、記憶装置４１６、及び通信インターフェース４２０を含み、これら全てがバス４２４に接続される。
【００５０】
プロセッサ４０４は、ロジックを制御し、情報を処理し、及びコンピュータシステム４００内の動きを調整する。一実施形態では、プロセッサ４０４は、例えば入力装置４２８から表示装置４３２へのデータの流れを調整することにより、ＲＡＭ４０８及びＲＯＭ４１２に格納されている命令を実行する。
【００５１】
ＲＡＭ４０８（通常はメインメモリとも呼ばれる）は、プロセッサ４０４によって実行されることになる情報及び命令を一時的に格納する。ＲＡＭ４０８内の情報は、入力装置４２８から得ることが可能であり、又はプロセッサ４０４によって実行される命令により必要とされるアルゴリズムプロセスの一部としてプロセッサ４０４により生成することが可能である。
【００５２】
ＲＯＭ４１２は、一旦ＲＯＭチップに書き込まれた後に読み出し専用となって変更も除去もされない情報及び命令を格納する。一実施形態では、ＲＯＭ４１２は、コンピュータシステム４００の構成及び初期動作のためのコマンドを格納する。
【００５３】
フロッピィディスク、ディスクドライブ、又はテープドライブといった記憶装置４１６は、コンピュータシステム４００により使用するための情報を永続的に格納する。
【００５４】
通信インターフェース４２０は、コンピュータシステム４００が他のコンピュータ又は装置と結合することを可能にする。通信インターフェース４２０には、例えば、モデム、ＩＳＤＮカード、ＬＡＮポート等を用いることが可能である。モデム又はＩＳＤＮカードが電話線を介したデータ通信を提供し、ＬＡＮポートがＬＡＮを介したデータ通信を提供することが、当業者には理解されよう。通信インターフェース４２０は、無線通信を可能にすることもできる。
【００５５】
バス４２４には、コンピュータシステム４００によって用いるための情報を通信するための任意の通信機構を用いることができる。図４の例では、バス４２４は、プロセッサ４０４、ＲＡＭ４０８、ＲＯＭ４１２、記憶装置４１６、及び通信インターフェース４２０等の間でデータを転送するための媒体である。
【００５６】
コンピュータシステム４００は、典型的には入力装置４２８、表示装置４３２、及びカーソル制御装置４３６に接続される。英数字その他のキーを含むキーボード等の入力装置４２８が、プロセッサ４０４に情報及びコマンドを伝達する。ＣＲＴ等の表示装置４３２は、コンピュータシステム４００のユーザに対して情報を表示する。マウス、トラックボール、又はカーソル方向キー（又は矢印キー）等のカーソル制御装置４３６は、プロセッサ４０４に対して方向に関する情報及びコマンドを伝達し、表示装置４３２上のカーソルの動きを制御する。
【００５７】
コンピュータシステム４００は、１つ又は２つ以上のネットワークを介して他のコンピュータ又は装置と通信することが可能である。例えば、コンピュータシステム４００は、通信インターフェース４２０を用いて、ネットワーク４４０を介してプリンタ４４８に接続された別のコンピュータ４４４と、又はワールドワイドウェブ４５２を介してサーバ４５６と通信する。ワールドワイドウェブ４５２は一般に「インターネット」と呼ばれる。代替的に、コンピュータシステム４００は、ネットワーク４４０を介してインターネット４５２にアクセスすることが可能である。
【００５８】
コンピュータシステム４００は、上記技術を実施するために用いることが可能である。様々な実施形態において、プロセッサ４０４は、ＲＡＭ４０８に提供される命令を実行することにより、該技術の各ステップを実行する。別の実施形態では、上記技術を実施するために、ソフトウェア命令の代わりに又はそれに組み合わせて、ハードワイヤード回路を用いることが可能である。従って、本発明の実施形態は、ソフトウェア、ハードウェア、又は回路の何れか１つ又はそれらの組み合わせに限定されるものではない。
【００５９】
プロセッサ４０４により実行される命令は、コンピュータによりデータを読み出すことが可能な１つ又は２つ以上の任意の媒体に格納して搬送することが可能である。かかる媒体としては、例えば、フロッピィディスク、ハードディスク、Ｚｉｐドライブカートリッジ、磁気テープ、又は任意の他の磁気媒体、ＣＤ−ＲＯＭ、ＣＤ−ＲＡＭ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、又は任意の他の光媒体、紙テープ、パンチカード、又は特定パターンの孔を有する任意の他の物理媒体、ＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、又は任意の他のメモリチップ又はカートリッジを用いることが可能である。かかる媒体はまた、同軸ケーブル、銅線、光ファイバ、音波、光波等を用いることが可能である。一例として、プロセッサ４０４により実行されることになる命令は、１つ又は２つ以上のソフトウェアプログラムという形をとり、最初に、バス４２４を介してコンピュータシステム４００とインターフェースするＣＤ−ＲＯＭに格納される。コンピュータシステム４００は、これらの命令をＲＡＭ４０８にロードし、幾つかの命令を実行し、通信インターフェース４２０（すなわちモデム及び電話線）を介して、ネットワーク（例えばネットワーク４４０、インターネット４５２等）に幾つかの命令を送信する。ネットワークケーブルを介してデータを受信するリモートコンピュータが、受信した命令を実行し、該データをコンピュータシステム４００に送信し、該データが記憶装置４１６に格納されることになる。
【００６０】
上記では、特定の実施形態を参照して本発明を説明してきた。しかし、本発明の広範な思想及び範囲から逸脱することなく、かかる実施形態に対して様々な変更及び改変を加えることが可能であることは明らかである。本書に開示する技術は、方法、装置、システム、素子、又はそれらの等価物、コンピュータによりデータを読み出すことが可能な媒体等として実施することが可能である。従って、本明細書及び図面は、本発明の限定ではなくその例示を目的としたものであるとみなされるべきである。
【００６１】
以下においては、本発明の様々な構成要件の組み合わせからなる例示的な実施態様を示す。
１．複数のロケーション（１２０）を有する待ち行列（１１０）中のデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を管理するための方法であって、第２のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）とタイムインタリーブする第１のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を受信し、
２つの識別子（ＷＰ１，ＷＰ２）を使用して第１のロケーション（１２０）を特定し、前記第１のトランザクションが受信される際に、該第１のトランザクション（１，２）に関連付けられることになる第１の識別子（ＷＰ１，ＷＰ２）がアクティブになる一方、第２の識別子（ＷＰ１，ＷＰ２）が非アクティブになり、
前記第１のトランザクションの第１のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を前記第１のロケーション（１２０）に格納し、次いでアクティブになる前記第１の識別子（ＷＰ１）を使用して、前記第１のトランザクションのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納するために前記第１のロケーション（１２０）を特定し、前記第１のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１のロケーション（１２０）に格納されるまで前記データ片の格納を行い、
前記第２の識別子（ＷＰ１，ＷＰ２）を使用して、前記第１のロケーション（１２０）よりも１つ高いロケーションである第２のロケーション（１２０）を特定する、
という各ステップを有する方法。
２．前記第１のロケーション（１２０）にデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が格納されていなかった場合に、前記第１の識別子（ＷＰ１，ＷＰ２）及び前記第２の識別子（ＷＰ１，ＷＰ２）を交互に選択して前記第１のトランザクションに関連付ける、前項１に記載の方法。
３．複数のロケーション（１２０）を有する待ち行列（１１０）中のデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を管理するための方法であって、第２のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）とタイムインタリーブする第１のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を受信し、２つの識別子（ＷＰ１，ＷＰ２）を使用して第１のロケーション（１２０）を特定し、前記第１のトランザクションが受信される際に、該第１のトランザクションに関連付けられることになる第１の識別子（ＷＰ１，ＷＰ２）がアクティブになる一方、第２の識別子（ＷＰ１，ＷＰ２）が非アクティブになり、
前記第１のトランザクションの最後のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）でもある該第１のトランザクションの第１のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を受信し、前記待ち行列（１１０）に以前に格納されたデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納するために通常使用されるレジスタ（１３０）が、データ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納するために利用可能である場合に、前記待ち行列（１１０）をバイパスして前記レジスタ（１３０）に前記第１のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納し、
前記第１の識別子（ＷＰ１，ＷＰ２）及び前記第２の識別子（ＷＰ１，ＷＰ２）を使用した前記第１のロケーション（１２０）の特定を続行する、
という各ステップを含む方法。
４．複数のロケーション（１２０）を有する待ち行列（１１０）中のデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を管理するための方法であって、第２のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）とタイムインタリーブする第１のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を受信し、第１の識別子（ＷＰ１，ＷＰ２）を使用して、前記第１のトランザクションに関するデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納するために前記第１のロケーション（１２０）を特定し、該第１のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１のロケーション（１２０）に格納されるまで前記データ片の格納を行い、該第１のロケーションが、前記第１のトランザクションに関する少なくとも１つのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納しており、第２の識別子（ＷＰ１，ＷＰ２）を使用して、第２のトランザクションに関するデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が到着する際に該データを格納するために利用可能な第２のロケーション（１２０）を特定し、該第２のロケーション（１２０）が前記第１のロケーション（１２０）よりも高いロケーションである、
という各ステップを含む方法。
５．前記第１のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１のロケーション（１２０）に格納される際に、前記第１の識別子（ＷＰ１，ＷＰ２）を使用して、前記第２の識別子（ＷＰ１，ＷＰ２）により特定される前記ロケーション（１２０）を特定する、というステップを含む、前項４に記載の方法。
６．複数のロケーション（１２０）を有する待ち行列（１１０）中のデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を管理するための方法であって、第２のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）とタイムインタリーブする第１のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を受信し、第１の識別子（ＷＰ１，ＷＰ２）を使用して、前記第１のトランザクションに関するデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納するために第１のロケーション（１２０）を特定し、該第１のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１のロケーション（１２０）に格納されるまで前記データの格納を行い、該第１のロケーション（１２０）が、前記第１のトランザクションの少なくとも１つのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納しており、
第２の識別子（ＷＰ１，ＷＰ２）を使用して、前記第２のトランザクションに関するデータを格納するために第２のロケーション（１２０）を特定し、該第２のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第２のロケーション（１２０）に格納されるまで前記データの格納を行い、該第２のロケーションが、前記第２のトランザクションに関する少なくとも１つのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納しており、
前記第１のトランザクション又は前記第２のトランザクションの何れかの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）がそれらの対応するロケーション（１２０）に格納される際に、前記対応するロケーション（１２０）を特定する前記識別子を動かして、前記第１のロケーション（１２０）及び前記第２のロケーション（１２０）の相対的な位置により特定される第３のロケーション（１２０）を特定する、という各ステップを含む方法。
７．前記第１のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１のロケーション（１２０）に格納される際に、前記第１のロケーション（１２０）が前記第２のロケーション（１２０）よりも高い場合には、前記第１の識別子（ＷＰ１，ＷＰ２）を動かして、前記第１のロケーション（１２０）よりも１つ高いロケーション（１２０）である第３のロケーション（１２０）を特定する、というステップを含む、前項６に記載の方法。
８．前記第１のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１のロケーション（１２０）に格納される際に、前記第１のロケーション（１２０）が前記第２のロケーション（１２０）よりも低い場合には、前記第１の識別子（ＷＰ１）を動かして、前記第２のロケーション（１２０）よりも１つ高いロケーションである第３のロケーション（１２０）を特定する、というステップを含む、前項６に記載の方法。
９．複数のロケーション（１２０）を有する待ち行列（１１０）中のデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を管理するための方法であって、第２のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）とタイムインタリーブする第１のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を受信し、新たなトランザクションを追跡するためにそれぞれ使用される複数の識別子を設け、第１の識別子がアクティブとなる一方で前記識別子の残りが非アクティブとなり、
前記新たなトランザクションを追跡するために利用可能な全ての識別子を使用して、該新たなトランザクションに関するデータを格納するための同じ第１のロケーション（１２０）を特定し、
第１の新たなトランザクションの第１のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が受信される際に、
該第１のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を前記第１のロケーション（１２０）に格納し、
アクティブな識別子を使用して、前記第１の新たなトランザクションを追跡し、及び前記第１のロケーション（１２０）を特定を続行することにより、前記第１の新たなトランザクションが進行中のトランザクションになり、
第２の新たなトランザクションを追跡するために利用可能な全ての識別子が、前記第１のロケーション（１２０）よりも高い第２のロケーション（１２０）を特定することを可能にする、
という各ステップを含む方法。
１０．前記トランザクションの前記第１のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を受信する順序が、前記トランザクションの前記データが書き込まれるロケーション（１２０）の順序を構成する、前項９に記載の方法。
１１．前記進行中のトランザクションを追跡する前記識別子が、該進行中のトランザクションのデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納するための前記第１のロケーションの特定を続行し、該進行中のトランザクションの全てのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が該第１のロケーション（１２０）に書き込まれるまで前記データの格納を行い、前記進行中のトランザクションの全てのデータ片が前記第１のロケーションに書き込まれた時点で、前記進行中のトランザクションを追跡する前記識別子が前記第２のロケーション（１２０）を特定するために移動する、前項９に記載の方法。
１２．複数のロケーション（１２０）を有する待ち行列（１１０）中のデータ（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を管理するための方法であって、１つのロケーション（１２０）に格納される少なくとも１つのデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を有するトランザクションを進行中のトランザクションとして特定し、
少なくとも１つのロケーション（１２０）が進行中のトランザクションに対応することを可能にし、該ロケーション（１２０）が、第１の進行中のトランザクションに対応する第１のロケーション（１２０）を含み、該第１のロケーション（１２０）が、他の進行中のトランザクションに対応する他のロケーションと比べて最も高く、
進行中のトランザクションに関するデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が受信される際に、
対応する識別子によって特定される前記進行中のトランザクションの同じロケーション（１２０）に前記データ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）を格納し、
前記データ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が最後のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）でない場合に、前記対応する識別子が前記同じロケーション（１２０）を特定し続け、
前記データ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が最後のデータ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）でもある場合には、前記データ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１の進行中のトランザクションに関するものである場合に、前記第１のロケーション（１２０）を特定する第１の識別子が、該第１のロケーション（１２０）よりも１つ高いロケーションである第２のロケーション（１２０）を特定するよう変更され、前記データ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）が前記第１の進行中のトランザクションに関するものでない場合には、前記データ片（１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１）の前記トランザクションに対応する前記識別子が、前記第１の識別子により特定される前記ロケーション（１２０）よりも１つ高いロケーションであるロケーション（１２０）を特定するよう変更される、
という各ステップを含む方法。
【図面の簡単な説明】
【図１】一実施形態による待ち行列機構を示す説明図である。
【図２Ａ】典型的なデータを格納する図１の待ち行列を示す説明図である。
【図２Ｂ】一実施形態により図２Ａのデータが図１の待ち行列に到着する態様を示す説明図である。
【図３Ａ】一実施形態に従い様々なステップを介してデータを格納する図１の待ち行列を示す説明図である（１／３）。
【図３Ｂ】一実施形態に従い様々なステップを介してデータを格納する図１の待ち行列を示す説明図である（２／３）。
【図３Ｃ】一実施形態に従い様々なステップを介してデータを格納する図１の待ち行列を示す説明図である（３／３）。
【図４】本発明を実施することが可能なコンピュータを示すブロックである。
【符号の説明】
１−１，１−２，１−３，１−４，２−１，２−２，３−１，３−２，３−３，３−４，４−１　データ
１００　　　　　システム
１１０　　　　　待ち行列
１２０　　　　　ロケーション
ＲＰ　　　　　　読み出しポインタ
ＷＰ−１，ＷＰ−２　　書き込みポインタ
【図１】
2004005471.tif 000003
【図２Ａ】
2004005471.tif 000004
【図２Ｂ】
2004005471.tif 000005
【図３Ａ】
2004005471.tif 000006
【図３Ｂ】
2004005471.tif 000007
【図３Ｃ】
2004005471.tif 000008
【図４】
2004005471.tif 000009