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