(57)【特許請求の範囲】
【請求項１】
第１のバスを第２のバスに接続して、該第１のバスから該第２のバスに一連のトランザクションを転送するためのするためのバス・ブリッジであって、該一連のトランザクションは、第１のタイプのトランザクションと第２のタイプのトランザクションを含んでおり、
前記第１のタイプのトランザクションを記憶するための第１の待ち行列であって、該第１のタイプのトランザクションは、前記第２のタイプのトランザクションによって飛び越される、第１の待ち行列と、
前記第２のタイプのトランザクションを記憶する第２の待ち行列と、
前記第１の待ち行列の各エントリに関連付けられたタグレジスタを有する第１のタグレジスタセットと、
前記第２の待ち行列の各エントリに関連付けられたタグレジスタを有する第２のタグレジスタセットと、を備え、
前記第２のタグレジスタセットの各タグレジスタは、キービットおよび非キービットのいずれかでロードされ、前記第１のタグレジスタセットの各タグレジスタは、ロックビットおよび非ロックビットのいずれかでロードされるよう構成されており、
前記バス・ブリッジは、
前記第２の待ち行列にロードされるトランザクションについて、前記非キービットで、前記第２のタグレジスタセットのタグレジスタをロードし、
前記第２の待ち行列にロードされた前記トランザクションの次のトランザクションが前記第１の待ち行列にロードされるときに、前記第２の待ち行列にロードされた前記トランザクションが該第２の待ち行列に存在しているならば、該第２の待ち行列に存在している該トランザクションについての前記タグレジスタを、前記キービットでリロードし、
前記第１の待ち行列にトランザクションがロードされるときに、該トランザクションの前のトランザクションであって、前記キービットでロードされたタグレジスタを有する該前のトランザクションが前記第２の待ち行列に存在するならば、該第１の待ち行列にロードされる該トランザクションについて、前記第１のタグレジスタセットのタグレジスタを前記ロックビットでロードし、該トランザクションの前のトランザクションであって、前記キービットでリロードされたタグレジスタを有する該前のトランザクションが前記第２の待ち行列に存在しないならば、該第１の待ち行列にロードされる該トランザクションについて、前記第１のタグレジスタセットのタグレジスタを前記非ロックビットでロードし、
前記第２の待ち行列にロードされ、かつ前記キービットでロードされたタグレジスタを有するトランザクションが前記第２のバスに送出されるまで、前記第１の待ち行列にロードされ、かつ前記ロックビットでロードされたタグレジスタを有するトランザクションが該第２のバスに送出されないようにする、よう構成されており、
該バス・ブリッジの該構成によって、前記第１のタイプのトランザクションは、前記第１のバスから直接前記第１の待ち行列に転送され、前記第２のタイプのトランザクションは、前記第１のバスから直接前記第２の待ち行列に転送され、該第１の待ち行列および該第２の待ち行列からのトランザクションは、直接該第２のバスに転送される、
バス・ブリッジ。
【請求項２】
前記バス・ブリッジに記憶されるトランザクションは、所定のフロー制御規則に従って前記第２のバスにアンロードされる、
請求項１に記載のバス・ブリッジ。
【請求項３】
前記フロー制御規則は、どのタイプのトランザクションが、どのタイプのトランザクションを飛び越えることができるかについての飛び越し規則を含む、
請求項２に記載のバス・ブリッジ。
【請求項４】
さらに、前記タグレジスタにキービットを有するトランザクションであって前記第２のバスに送出されたトランザクションの数と、前記タグレジスタにロックビットを有するトランザクションであって前記第２のバスに送出されたトランザクションの数と、を追跡するよう構成されたキー・レジスタを備える、
請求項１から３のいずれかに記載のバス・ブリッジ。
【請求項５】
前記バス・ブリッジは、さらに、前記タグレジスタにキービットを有するトランザクションであって前記第２のバスに送出されたトランザクションのそれぞれについて、前記キー・レジスタを増分し、前記タグレジスタにロックビットを有するトランザクションであって前記第２のバスに送出されたトランザクションのそれぞれについて、前記キー・レジスタを減分する、
請求項４に記載のバス・ブリッジ。
【請求項６】
第１のバスを第２のバスに接続して、該第１のバスから該第２のバスに一連のトランザクションを転送するためのするためのバス・ブリッジの動作のための方法であって、該一連のトランザクションは、第１のタイプのトランザクションと第２のタイプのトランザクションを含んでおり、
前記バス・ブリッジは、
前記第１のタイプのトランザクションを記憶するための第１の待ち行列であって、該第１のタイプのトランザクションは、前記第２のタイプのトランザクションによって飛び越される、第１の待ち行列と、
前記第２のタイプのトランザクションを記憶する第２の待ち行列と、
前記第１の待ち行列の各エントリに関連付けられたタグレジスタを有する第１のタグレジスタセットと、
前記第２の待ち行列の各エントリに関連付けられたタグレジスタを有する第２のタグレジスタセットと、を備え、
前記第２のタグレジスタセットの各タグレジスタは、キービットおよび非キービットのいずれかでロードされ、前記第１のタグレジスタセットの各タグレジスタは、ロックビットおよび非ロックビットのいずれかでロードされるよう構成されており、
該方法は、
前記第２の待ち行列にロードされるトランザクションについて、前記非キービットで、前記第２のタグレジスタセットのタグレジスタをロードし、
前記第２の待ち行列にロードされた前記トランザクションの次のトランザクションが前記第１の待ち行列にロードされるときに、前記第２の待ち行列にロードされた前記トランザクションが該第２の待ち行列に存在しているならば、該第２の待ち行列に存在している該トランザクションについての前記タグレジスタを、前記キービットでリロードし、
前記第１の待ち行列にトランザクションがロードされるときに、該トランザクションの前のトランザクションであって、前記キービットでロードされたタグレジスタを有する該前のトランザクションが前記第２の待ち行列に存在するならば、該第１の待ち行列にロードされる該トランザクションについて、前記第１のタグレジスタセットのタグレジスタを前記ロックビットでロードし、該トランザクションの前のトランザクションであって、前記キービットでリロードされたタグレジスタを有する該トランザクションが前記第２の待ち行列に存在しないならば、該第１の待ち行列にロードされる該トランザクションについて、前記第１のタグレジスタセットのタグレジスタを前記非ロックビットでロードし、
前記第２の待ち行列にロードされ、かつ前記キービットでロードされたタグレジスタを有するトランザクションが前記第２のバスに送出されるまで、前記第１の待ち行列にロードされ、かつ前記ロックビットでロードされたタグレジスタを有するトランザクションが該第２のバスに送出されないようにする、ことを含み、
前記第１のタイプのトランザクションは、前記第１のバスから直接前記第１の待ち行列に転送され、前記第２のタイプのトランザクションは、前記第１のバスから直接前記第２の待ち行列に転送され、該第１の待ち行列および該第２の待ち行列からのトランザクションは、直接該第２のバスに転送される、
方法。
【請求項７】
さらに、
前記バス・ブリッジに記憶されるトランザクションを、所定のフロー制御規則に従って前記第２のバスにアンロードすることを含む、
請求項６に記載の方法。
【請求項８】
さらに、
前記タグレジスタにキービットを有するトランザクションであって前記第２のバスに送出されたトランザクションの数と、前記タグレジスタにロックビットを有するトランザクションであって前記第２のバスに送出されたトランザクションの数と、を追跡するようキー・レジスタを操作することを含み、該追跡は、前記タグレジスタにキービットを有するトランザクションであって前記第２のバスに送出されたトランザクションのそれぞれについて、前記キー・レジスタを増分し、前記タグレジスタにロックビットを有するトランザクションであって前記第２のバスに送出されたトランザクションのそれぞれについて、前記キー・レジスタを減分することにより行われる、
請求項６または７に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的には，コンピュータ・システムに関するもので、特に、順位づけ制約を持つトランザクションを経路指定するメカニズムに関するものである。
【０００２】
【従来の技術】
相互に連結されるコンピュータ・ネットワークにおいて、諸装置はトランザクションを介して通信する。トランザクションは１つまたは複数のパケットを含み、何らかの意味のある情報を搬送する。例えば、マルチプロセッサ・ネットワークにおけるＣＰＵは、「詮索応答」トランザクションで詮索要求に応答する。相互接続構造における１つのパケットは、一般的には、固定数の転送またはサイクルから成る。異なるトランザクションは、異なる数のパケットを必要とする。
【０００３】
異なるタイプのトランザクションの流れは、順位づけ制約によって制御される。この制約は、あらゆるトランザクションに関する相互の順位づけ関係を指定する。ある種のトランザクション・タイプは、前進を保証するため他のトランザクション・タイプを飛び越えることを必要とし、また、別のトランザクション・タイプは、順位を保証するため他のトランザクション・タイプを飛び越えることを禁じられる。典型的には、このような順位づけ規則は、トランザクション・タイプのあらゆるペアの間の順位づけ関係を指定する順位づけテーブルによって提供される。
【０００４】
トランザクション・タイプの任意のペアＰおよびＱに関して、順位付けテーブルは、ＰがＱを飛び越えなければならないか、あるいは、ＰがＱを飛び越えてはならないか、あるいは、ＰがＱを飛び越えても問題ではないかを指定する。同様に、テーブルにおける別のエントリは、ＱがＰを飛び越えることができるか指定する。"PCI Local Bus Specification, Rev.2.1, PCI Special Interest Group, Portland, OR, June 1995"のＰＣＩローカル・バス仕様における順位付けテーブルにこのような順位づけ制約の例を見ることができる。順序づけ規則は、伝統的には、共通待ち行列にすべての到来トランザクションを書き込むことによって実施される。飛び越し可能なトランザクションが共通待ち行列の先頭へ移動する時、それは独立した別の飛び越し待ち行列(または待ち行列体系)に書き込まれる。
【０００５】
図４は、２つのＰＣＩバス、Ａ４２およびＢ４３を接続するＰＣＩ間ブリッジ４１にＰＣＩトランザクションのサブセットを実施する典型的従来技術構成４０を示している。この構成は、ポストされるメモリー書込み(すなわちＰＭＷ)および遅延される読み取り要求(すなわちＤＲＲ)という２つのタイプのＰＣＩトランザクションを取り扱う。ＰＭＷトランザクションは、デッドロックを避けるために前のＤＲＲトランザクションを飛び越すことを要求される。しかしながら、ＤＲＲトランザクションは、順序づけモデルに従わなければならず、ＰＭＷトランザクションを飛び越えることは許されない。ＰＣＩバスＡ４２からＰＣＩバス・ブリッジ４１に到着するトランザクションは、これらの制約を維持すような形態で待ち行列に書き込まれる必要がある。
【０００６】
従って、この手法は、ＤＲＲトランザクションだけのための飛び越え待ち行列４４とＰＭＷおよびＤＲＲトランザクションが書き込まれる共通待ち行列４５という２つの待ち行列を使用する。ＰＣＩバスＡからのＤＲＲおよびＰＭＷトランザクションの両者は共通待ち行列４５に記憶される。ＤＲＲトランザクションが共通待ち行列の先頭に達すると、それは、飛び越え待ち行列４４に書き込まれる。そのＤＲＲの後にＰＭＷがあれば、そのＰＭＷは、ＤＲＲを飛び越えて、ＰＣＩバスＢ４３上に送り出されることができる。ＰＭＷのすべてが送り出された後、ＤＲＲは送出される。
【０００７】
【発明が解決しようとする課題】
このような構成の問題は、この構成がＰＣＩ仕様の順序づけ必要条件に合致しているとはいえ、ＰＣＩバスＢ４３の利用可能なバンド幅を十分活用していないため処理性能を低下させる点である。ＤＲＲトランザクションが共通待ち行列から飛び越し待ち行列へ書き込まれる時ＰＣＩバスＢの利用度は十分でなくなる。ＦＩＦＯ構造である共通待ち行列は、ＤＲＲトランザクションが飛び越え待ち行列に書き込まれつつある時後続のＰＭＷトランザクションをＰＣＩバスへ送り出すことができない。このように、従来技術の構成は、ＰＣＩバスＢ上で利用できる最大限のバンド幅を達成することができない。
【０００８】
この構成のもう１つの問題は、共通待ち行列のサイズが大きい必要があるという点である。特定タイプの大きいトランザクションは多量の記憶空間を必要とする。これらの大きいトランザクションは待ち行列に入れられず、直ちにバスに送出されることが理想的である。しかしながら、順序づけを維持するため、これらのトランザクションは、他のトランザクションとともに共通待ち行列に納められなければならない。
【０００９】
従って、順序づけを維持しながら、上述のような処理性能隘路を除去し、共通待ち行列の所要のサイズを減少させるメカニズムに対する必要性が当業界に存在する。
【００１０】
【課題を解決するための手段】
上記課題を解決する本発明のシステムおよび方法は、飛び越し可能トランザクションを共通待ち行列を通過させることなく、ソースにおいて飛び越し待ち行列(または待ち行列体系)へ書き込むメカニズムを使用する。このメカニズムは付加的制御論理を用いて順序づけを維持する。従って、共通待ち行列は飛び越し待ち行列にトランザクションを供給しない。
【００１１】
トランザクションを書き込む時点で、制御論理はトランザクションが飛び越し可能か否か判断して、飛び越し可能なトランザクションであれば、それを直接飛び越し待ち行列に記憶する。トランザクションが飛び越し可能でない場合、制御論理はそのトランザクションを共通待ち行列に書き込む。このメカニズムは、異なる待ち行列に記憶された異なるトランザクションの間の順序づけを維持するため、待ち行列内で付加的フィールドを使用する。この付加されるフィールドは、特定のトランザクションが別のトランザクションの前に到来したか後に到来したかを判別する。各トランザクションは、順序づけを維持するために使用される付加ビットと共に記憶される。付加ビット・フィールドは、各トランザクションに対して１つのフィールドであり、共通待ち行列および飛び越し待ち行列の両方に存在する。
【００１２】
このようなメカニズムを備える本発明の利点として、共通待ち行列と飛び越し待ち行列を分岐することによる処理性能向上、飛び越し待ち行列への直接書き込み、飛び越しトランザクションの１回だけの書き込みによる資源利用度の向上、および、飛び越しトランザクションを記憶しないことによる共通待ち行列サイズの減少を通しての流れ制御の減少による処理性能の向上があげられる。
【００１３】
【発明の実施の形態】
図１は、２つのＰＣＩバス１２、１３を接続するＰＣＩ間ブリッジ１１上でＰＣＩトランザクションを実施する本発明の構成１０を示している。この構成は、ポストされるメモリー書込み(すなわちＰＭＷ)および遅延される読み取り要求(すなわちＤＲＲ)という２つのタイプのＰＣＩトランザクションを取り扱う。ＰＭＷトランザクションは、デッドロックを避けるため前のＤＲＲトランザクションを飛び越すことを要求される。しかしながら、ＤＲＲトランザクションは、順序づけモデルに従わなければならず、ＰＭＷトランザクションを飛び越えることは許されない。ＰＣＩバス１２からＰＣＩバス・ブリッジ１１に到着するトランザクションは、これらの制約を維持すような形態で待ち行列に書き込まれる必要がある。
【００１４】
従って、この手法は、ＤＲＲトランザクションだけのための飛び越え待ち行列１４とＰＭＷトランザクションが書き込まれる共通待ち行列１５という２つの待ち行列を使用する。制御論理(図示されていない)が、どの待ち行列に特定のトランザクションが記憶されているか判断する。ＰＭＷおよびＤＲＲという２つのトランザクションは例示の目的のためのものである点注意されるべきである。本発明のメカニズムは、いかなるプロトコルのいかなる数のトランザクション・タイプに関しても適用することができる。更に、用語「待ち行列」はＦＩＦＯ(先入れ先出し)構造を意味する点にも注意する必要がある。
【００１５】
図１は、ブリッジ１１に、Ｔ０、Ｔ１、Ｔ２、Ｔ３、Ｔ４、Ｔ５およびＴ６という一連のトランザクションがこの順番で到着していることを示している。Ｔ０、Ｔ３、Ｔ４およびＴ６はＤＲＲトランザクションで、従って、飛び越し可能であり、飛び越し待ち行列１４に書き込まれる。Ｔ１、Ｔ２およびＴ５はＰＭＷトランザクションであり、共通待ち行列１５に書き込まれる。本メカニズムは、異なる待ち行列における異なるトランザクションの間の順序づけを維持するため、タグ１６、１７を使用する。順序づけは、各トランザクションのエントリ位置によって各待ち行列の範囲内で維持される。例えば、共通待ち行列１５において、Ｔ１は先頭にあり、Ｔ２およびＴ５はその順番でＴ１の後にある。同じように、飛び越し待ち行列１４に関して、Ｔ３、Ｔ４およびＴ６はそれぞれの順番で記憶される。このように、タグ１６および１７は、待ち行列の間の順序を維持し、各待ち行列の先頭にあるどちらのエントリが相対的に以前のトランザクションであるかを標示する。
【００１６】
図１に示されるように、タグは共通待ち行列１５における最新のトランザクションのエントリ位置である。かくして、Ｔ０が飛び越し待ち行列に書き込まれる時、共通待ち行列は空きであるので、Ｔ０には０というタグをつけられる。次に、Ｔ１およびＴ２が共通待ち行列１５に書き込まれ、それぞれ１および２というタグをつけられる。Ｔ３が飛び越し待ち行列１４に到来する時、共通待ち行列における最新のエントリは２というタグを持つＴ２であるので、Ｔ３には２というタグがつけられる。同様に、Ｔ４が飛び越し待ち行列１４に到来する時、共通待ち行列における最新のエントリはまだなお２というタグを持つＴ２であるので、Ｔ４にも２というタグがつけられる。次に、Ｔ５は共通待ち行列に書き込まれ、３というタグを付けられる。従って、Ｔ６が飛び越し待ち行列１４に到来する時、共通待ち行列における最新のエントリは３というタグを持つＴ５であるので、Ｔ６には３というタグがつけられる。
【００１７】
タグ番号は、ある特定のＤＲＲトランザクションの送出が試みられる前に送出されなければならないＰＭＷトランザクションの番号を標示する。例えば、Ｔ０は０というタグを持っているので、Ｔ０が送出される前にいかなるＰＭＷトランザクションも送出してはならないことを標示する。しかしながら、ＤＲＲトランザクションの送出が試みられる前に送出できるＰＭＷが存在する。Ｔ３およびＴ４は２つのＰＭＷトランザクションＴ１およびＴ２が送出されるまで待機しなければならず、Ｔ６は３つのＰＭＷトランザクションの送出を待つ。注意されるべき点であるが、いずれかのＤＲＲトランザクションが送出される前にすべてのＰＭＷトランザクションを送出することができる。なぜなら、書き込みは読み取りを飛び越すが、読み取りは書き込みを飛び越すことはできない。かくして、フロー制御規則は次の通りとなる。すなわち、読み取りすなわち飛び越し待ち行列からのエントリは、そのタグが書込みすなわち共通待ち行列の先頭の書込みタグ値より小さい場合あるいは共通待ち行列が空の場合に、送出される。
【００１８】
従って、Ｔ０は、そのタグが書込み待ち行列１５の先頭のＴ１トランザクションのタグ値の１より小さいので、読み取り待ち行列１４から最初に取り出される。しかしながら、読み取りは飛び越されることことができるという点を強調して、Ｔ１が最初に取り出されると仮定することもできる。この規則は、特定のエントリに関して読取りが最新の値を常に取り出すことを保証する点に注意する必要がある。すなわち、もしも読み取りが書き込みを飛び越すとすれば、読み取りは古い値を読むことになる。次に、２というタグを持つＴ２が送り出される。このようにして、書込み待ち行列は３というタグを持つ１つのエントリＴ５だけを持つ。次に、Ｔ０が読み取り待ち行列から取り出される。制御論理(図示されていない)は、書き込み待ち行列の先頭にある３というタグを持つＴ５のタグとＴ０のタグを比較する。Ｔ０のタグがＴ５のタグより小さいので、Ｔ０を送り出すことができる。Ｔ３およびＴ４は、それらのタグがＴ５のタグより小さいので、送り出すことができる。制御論理は、また、送出されるべき最新の書き込みトランザクションのタグを読み取りトランザクションのタグと比較し、読み取りトランザクションのタグが送出される書き込みトランザクションのタグより小さいか否かを判断して、小さい場合読み取りトランザクションが送り出される。Ｔ６は、そのタグがＴ５のタグと等しいので、Ｔ５が送出されるまで、取り出すことはできない。Ｔ５が送出された後、制御論理はＴ６を解放する。読み取りトランザクションの取り出しが試みられる前に送出されなければならない書き込みトランザクションの番号をタグが標示する点に注意する必要がある。
【００１９】
注意すべき点であるが、各書き込みトランザクションが到着する毎に、逐次増加するタグの値が割り当てられるように、図１のタグは増加し続ける。従って、タグのサイズを制限するため、単一ビット構成を使用する。図２は、図１の構成の単一ビット版２０の待ち行列記憶を示す。トランザクションのシーケンスは図１と同じものである。図１のタグは、ここでは、キーおよびロックと呼ばれる。キー・ビット２１は書込みすなわち共通待ち行列１５と関連し、ロック・ビット２２は読み取りすなわち飛び越し待ち行列１４と関連する。このように、各トランザクションは、記憶される待ち行列に応じてロックまたはキーのいずれかの関連タグ・ビットを持つ。読み取りトランザクション上でのロックされたビットすなわち１というタグは、書き込みトランザクションが取り出されるまで読み取りトランザクションが取り出されることを防止する。
【００２０】
例えば、図２の(Ｇ)に示されるように、Ｔ０はロック・ビットを持っていないので、いつでも取り出されることができる。Ｔ１はキー・ビットを持っていないので、Ｔ１に続く読み取りトランザクションはない。読み取りＴ３は書き込みＴ２に引き続くトランザクションであるので、Ｔ２はキー・ビットを持ち、Ｔ３はロック・ビットを持つ。従って、Ｔ２が取り出されるまで、Ｔ３は取り出されることはできない。読み取りがロックされる毎に、キーが対応する書き込みに挿入される点に注意する必要がある。読み取りＴ４は、Ｔ２によってロックされている読み取りＴ３に引き続いているので、ロックされていない。従って、Ｔ４はＴ２が取り出されるまで、取り出されることはできない。読み取りＴ６は書き込みＴ５に引き続くトランザクションであるので、Ｔ５はキー・ビットを持ち、Ｔ６はロック・ビットを持つ。従って、Ｔ５が取り出されるまで、Ｔ６は取り出されることはできない。
【００２１】
このように、流れ制御は、書込みすなわち共通待ち行列から読み取りすなわち飛び越し待ち行列へ切り替えが行われる度毎に、切り替えに先行するトランザクションにキーがつけられ、後続のトランザクションにロックがかけられるというものである。注意すべき点であるが、この制御は、切り替えの時点で書き込みすなわち共通待ち行列にエントリがあると仮定する。ない場合には、タグ値にゼロが書き込まれる。
【００２２】
図２の(Ａ)において、トランザクションＴ０が読み取り待ち行列に記憶される。書き込み待ち行列が空であり切り替えが行われなかったので、ロック・ビット・タグは０である。図２の(Ｂ)において、トランザクションＴ１が書込み待ち行列１５に記憶される。書き込みから読み取りへの切り替えが行われなかったので、キー・ビット・タグは０である。図２の(Ｃ)において、トランザクションＴ２が書込み待ち行列１５に記憶される。書き込みから読み取りへの切り替えが行われなかったので、キー・ビット・タグは０である。
【００２３】
図２の(Ｄ)において、トランザクションＴ３が読み取り待ち行列１４に記憶される。書き込み待ち行列にエントリがある間に書き込みから読み取りへの切り替えが行われたので、Ｔ２のキー・ビットは１に変更され、Ｔ３のロック・ビットには１というタグが付けらる。このように、Ｔ３のロックはＴ２が取り出される前にＴ３が取り出されることを防止する。図２の(Ｅ)において、トランザクションＴ４が読み取り待ち行列１４に記憶される。書き込みから読み取りへの切り替えが行われなかったので、Ｔ４のロック・ビットは０というタグをつけられる。Ｔ３のロックはＴ２が取り出される前にＴ４が取り出されることを防止する点に注意する必要がある。
【００２４】
図２の(Ｆ)において、トランザクションＴ５が書込み待ち行列１５に記憶される。書き込みから読み取りへの切り替えが行われなかったので、Ｔ５のキー・ビット・タグは０である。図２の(Ｇ)において、トランザクションＴ６が読み取り待ち行列１４に記憶される。書込み待ち行列にエントリがある間に書き込みから読み取りへの切り替えが行われたので、Ｔ５のキー・ビットは１に変更され、Ｔ６のロック・ビットには１というタグが付けらる。このように、Ｔ６のロックはＴ５が取り出される前にＴ６が取り出されることを防止する。
【００２５】
図３は、図１の単一ビット版構成３０の記憶動作を示すものであるが、記憶動作と共に行われる取り出し動作をも含んでいる。取り出し決定は、トランザクションの宛先における待ち行列空間のような外的因子に従って、制御論理(図示されていない)によって行われる。トランザクションのシーケンスは図１および図２と同じものである。図３はキー・レジスタ３１を含む。キー・レジスタ３１は、書き込みトランザクションに関して取り出されたキーのカウントを維持する。１というキーを持つ書き込みトランザクションが取り出される毎にキー・レジスターは増分され、１というロックを持つ読み取りトランザクションが取り出される毎にキー・レジスタは減分される。
【００２６】
図３の構成は、次のような規則に従って動作する。但し、この規則はいかなるシステムにおいても使用することができる。
【００２７】
規則１：１にセットされたキーを持つ共通待ち行列のトランザクションが取り出される時、キーは解放される。キー・レジスタすなわちカウントは１増分される。
【００２８】
規則２：飛び越し待ち行列のトランザクションは、ロックされてないすなわちロック＝０であるかまたはキー・レジスタが０を超えていれば、取り出されることができる状態にあるとみなされる。
【００２９】
規則３：飛び越し待ち行列のトランザクションは、規則２で定義に従って取り出される状態にある場合にのみ、待ち行列から取り出される。
【００３０】
規則４：飛び越し待ち行列のトランザクションが取り出される時、キー・レジスターはｌ減分される。
【００３１】
規則５：キー・レジスタは起動時に０に設定される。
【００３２】
図３の(Ａ)に示されるように、トランザクションＴ０が読み取り待ち行列に記憶される。書き込み待ち行列が空であり切り替えが行われなかったので、ロック・ビット・タグは０である。キーもロックも取り出されなかったので、レジスタ・キーは初期設定のまま０である。図３の(Ｂ)において、トランザクションＴ１が書き込み待ち行列１５に記憶される。切り替えが行われなかったので、キー・ビット・タグは０である。図３の(Ｃ)において、トランザクションＴ２が書き込み待ち行列１５に記憶される。切り替えが行われなかったので、キー・ビット・タグは０である。図３の(Ｄ)において、トランザクションＴ１が取り出される。Ｔ１のキーは１でないので、キー・レジスタ３１は０のままとされる。図３の(Ｅ)において、トランザクションＴ３が読み取り待ち行列１４に記憶される。エントリが書き込み待ち行列にある間に書き込み待ち行列から読み取り待ち行列の記憶への切り替えが行われたので、Ｔ２のキー・ビットは１に変更され、Ｔ３のロック・ビットに１というタグがつけられる。従って、Ｔ３のロックは、Ｔ２が取り出される前にＴ３が取り出されることを防止する。
【００３３】
図３の(Ｆ)において、トランザクションＴ４が読み取り待ち行列１４に記憶される。書き込み待ち行列から読み取り待ち行列への切り替えが行われなかったので、Ｔ４のロック・ビットは０である。Ｔ３のロックは、Ｔ２が取り出される前にＴ４が取り出されることを防止する点注意する必要がある。図３の(Ｇ)において、トランザクションＴ２が取り出される。Ｔ２のキーは１であったので、キー・レジスタ３１は１増分される。図３の(Ｈ)において、トランザクションＴ０が取り出される。Ｔ０はロックされていなかったので、キー・レジスタは１のままとされる。
【００３４】
図３の(Ｉ)において、トランザクションＴ３が取り出される。Ｔ３はロックされていたので、キー・レジスタは１減分され、０とされる。図３の(Ｊ)において、トランザクションＴ５が書き込み待ち行列１５に記憶される。切り替えが行われなかったので、Ｔ５のキー・ビットは０というタグがつけられる。図３の(Ｋ)において、トランザクションＴ５が取り出される。Ｔ５にキーはつけられていなかったので、キー・レジスタ３１は０のままとされる。図３の(Ｌ)において、トランザクションＴ６が読み取り待ち行列１４に記憶される。切り替えが行われたが、書き込み待ち行列が空であるので、Ｔ６のロック・ビットは０である。図３の(Ｍ)および(Ｎ)におて、トランザクションＴ４およびＴ６がそれぞれ取り出される。
【００３５】
注意すべき点であるが、図２および図３に示されるシーケンスは例示のためのものにすぎず、待ち行列の記憶および取り出しは、順序づけおよび飛び越し規則が守られる限り、多くの異なるシーケンスで発生させることが可能である。
【００３６】
また、本発明のメカニズムは、単一の共通の待ち行列と複数の飛び越し待ち行列という形態についても動作する。その場合、飛び越し待ち行列の各々は特定のトランザクションを保有する。どのトランザクションがどのトランザクションを飛び越すことができるかということに関する対応する規則が、制御論理に含められなければならない。制御論理のテーブルは、トランザクションＴiおよびＴjというあらゆるペアに関して、ＴiがＴjを飛び越すことができるか、ＴiがＴjを飛び越すことができないか、ＴiがＴjを飛び越すことができるかできないか問題でないか、などの詳細を記述する。メカニズムは、飛び越し待ち行列の各々毎に共通待ち行列に別々のキー・ビットを用意する。このように、図２および図３の書き込み待ち行列は、各読み取り待ち行列に対して１つずつ、複数のキー・ビット・エントリを持つ。各読み取り待ち行列は単一のロック・ビットを持つ。このようにして、書き込み待ち行列の単一エントリが、読み取り待ち行列における複数の読み取りすなわち飛び越しエントリの取り出しを制御する。
【００３７】
更に注意すべき点であるが、本発明のメカニズムは、複数の共通待ち行列と単一の飛び越し待ち行列という構成についても動作する。メカニズムは、共通待ち行列の各々に対して飛び越し待ち行列に別々のロック・ビットを用意する。すなわち、図２および図３の書き込み待ち行列の各々は単一のキー・ビット・エントリを持ち、一方、読み取り待ち行列は、書き込み待ち行列の各々毎に１つ、複数のロック・ビット・エントリを持つ。従って、飛び越されるトランザクションの各々は、読み取り待ち行列から取り出しの前に書き込み待ち行列のトランザクションが取り出されることを保証する。
【００３８】
更にまた、本発明のメカニズムは、複数の共通待ち行列と複数の飛び越し待ち行列という構成についても動作する。１つの共通待ち行列に対応する各飛び越し待ち行列に関して１つのペアのロック・キー待ち行列が必要とされる。本発明のメカニズムは、また、１つまたは複数の飛び越し待ち行列を持つ共通待ち行列がより高いレベルの別の１つの共通待ち行列に供給されるような階層構造においても動作する。そのようなケースでは、より低いレベルの共通の待ち行列および飛び越し待ち行列の出力が、より高いレベルの共通待ち行列および飛び越し待ち行列に記憶される。
【００３９】
以上本発明の特定の実施形態を記述したが、上述された概念および特定の実施形態は本発明の同じ目的を達成するため他の構造を設計および修正する基礎として容易に活用することができることは当業者に認められることであろう。
【００４０】
本発明には、例として次のような実施様態が含まれる。
【００４１】
（１）第１のバスを第２のバスに接続させ、複数のタイプのトランザクションを含む一連のトランザクションを第１のバスから第２のバスへ転送するバス・ブリッジであって、上記複数のタイプのトランザクションのうちの少くとも１つの別のタイプのトランザクションによって飛び越され得る１つの特定タイプの少くとも１つのトランザクションを記憶する第１の待ち行列と、上記少くとも１つの別のタイプの少なくとも１つのトランザクションを記憶する第２の待ち行列と、を備え、上記少くとも１つの特定タイプのトランザクションが上記第１のバスから上記第１の待ち行列へ直接送られる、バス・ブリッジ。
【００４２】
（２）１つのタグ・レジスタが上記第１の待ち行列の各エントリに関連づけられている複数タグ・レジスタの第１セットと、１つのタグ・レジスタが上記第２の待ち行列の各エントリに関連づけられている複数タグ・レジスタの第２セットと、を更に備える上記（１）に記載のバス・ブリッジ。
【００４３】
（３）バス・ブリッジに記憶されているトランザクションがフロー制御に従って上記第２のバスへ取り出される、上記（２）に記載のバス・ブリッジ。
【００４４】
（４）上記流れ制御が、上記複数のトランザクション・タイプのうちのどのトランザクション・タイプが、上記複数のトランザクション・タイプのうちの他のトランザクション・タイプを飛び越えることができるかを定義する規則を含む、上記（３）に記載のバス・ブリッジ。
【００４５】
（５）上記第２のタグ・レジスタ・セットの各タグ・レジスタはキー・ビットおよび非キー・ビットを記憶し、第２の待ち行列に記憶される特定のトランザクションに関する上記第２セットの１つの特定のタグ・レジスタが非キー・ビットを持ち、上記特定のタグ・レジスタに関連する特定トランザクションに後続するトランザクションが上記第１の待ち行列に記憶され、かつ、上記後続トランザクションが記憶される時該特定トランザクションが上記第２の待ち行列に存在する場合、上記特定のタグ・レジスタのビットがキー・ビットに変更される、上記（２）に記載のバス・ブリッジ。
【００４６】
（６）上記第２のタグ・レジスタ・セットの各タグ・レジスタはキー・ビットおよび非キー・ビットを記憶し、上記第１のタグ・レジスタ・セットの各タグ・レジスタはロック・ビットおよびロック解放ビットを記憶し、第１の待ち行列に記憶される特定トランザクションに先行して第２の待ち行列に記憶されているトランザクションがキー・ビットを含むタグ・レジスタを持ち、かつ、該特定トランザクションが第１の待ち行列に記憶される時上記先行トランザクションが上記第２の待ち行列に存在する場合、第１の待ち行列に記憶される特定のトランザクションに関する上記第１セットの１つの特定のタグ・レジスタがロック・ビットを持ち、そうでない場合、ロック解放ビットを持つ、上記（２）に記載のバス・ブリッジ。
【００４７】
（７）上記第１のタグ・レジスタ・セットの各タグ・レジスタはロック・ビットおよびロック解放ビットを記憶し、第１の待ち行列に記憶される特定トランザクションに先行して第２の待ち行列に記憶されているトランザクションがキー・ビットを含むタグ・レジスタを持ち、かつ、該特定トランザクションが第１の待ち行列に記憶される時上記先行トランザクションが上記第２の待ち行列に存在する場合、第１の待ち行列に記憶される特定のトランザクションに関する上記第１セットの１つの特定のタグ・レジスタがロック・ビットを持ち、そうでない場合、ロック解放ビットを持つ、上記（５）に記載のバス・ブリッジ。
【００４８】
（８）タグ・レジスタにロック・ビットを有して上記第１の待ち行列に記憶されている１つ特定のトランザクションは、タグ・レジスタにキー・ビットを有して上記第２の待ち行列に記憶されている別のトランザクションが上記第２のバスへ取り出されるまでは、上記第２のバスへ取り出されることを禁じられる、上記（７）に記載のバス・ブリッジ。
【００４９】
（９）タグ・レジスタにキー・ビットを持って取り出されたトランザクションの数、および、タグ・レジスタにロック・ビットを持って取り出されたトランザクションの数の両方を追跡するキー・レジスタを更に備える、上記（８）に記載のバス・ブリッジ。
【００５０】
（１０）上記キー・レジスタが、タグ・レジスタにキー・ビットを持って取り出されるトランザクションの各々毎に増分され、タグ・レジスタにロック・ビットを持って取り出されるトランザクションの各々毎に減分される、上記（９）に記載のバス・ブリッジ。
【００５１】
【発明の効果】
本発明は、共通待ち行列と飛び越し待ち行列を分岐することによって、バス・ブリッジの処理性能向上および資源利用度の向上を実現する。
【図面の簡単な説明】
【図１】２つのＰＣＩバスを接続するＰＣＩ間ブリッジ上でＰＣＩトランザクションを実施する本発明の構成を示すブロック図である。
【図２】図１の構成の単一ビット版にトランザクションを書き込むシーケンスを示すブロック図である。
【図３】図１の構成の単一ビット版との間でトランザクションを書き込みおよび取り出しするシーケンスを示すブロック図である。
【図４】２つのＰＣＩバスを接続するＰＣＩ間ブリッジ上でＰＣＩトランザクションを実施する従来技術の構成を示すブロック図である。
【符号の説明】
１０    バス・ブリッジ
１２    第１のバス
１３    第２のバス
１４    第１の待ち行列または飛び越し待ち行列
１５    第２の待ち行列または共通待ち行列
【図１】
0004248661.tif 000002
【図２】
0004248661.tif 000003
【図３】
0004248661.tif 000004
【図４】
0004248661.tif 000005