(57)【特許請求の範囲】
【請求項１】
コンピュータ・システムのためのＰＣＩバス・アービタであって、前記コンピュータ・システムが、複数のＰＣＩバス・デバイスに接続するためのＰＣＩバスを有し、各ＰＣＩバス・デバイスが、バス要求信号の使用によって前記ＰＣＩバスの制御を要求し、
前記ＰＣＩバス・アービタは、
データ・レジスタ・ユニットと、
再試行活動記録手段と、
前記データ・レジスタ・ユニット内のビットからなるフラグであって、各ＰＣＩバス・デバイスに夫々対応するフェアネス・フラグと、各ＰＣＩバス・デバイスの所定の優先順位とに基づいて、バス要求信号を調停して優先順位を付けるためのフェアネス方式を組み込んだ論理であって、前記フェアネス・フラグは、対応するＰＣＩバス・デバイスにより再試行信号が受け取られている場合には、セットされず、受け取られていない場合には、セットされ、それによって他の要求信号の優先順位より下に下げられる、論理と、
前記フェアネス・フラグがセットされておらず、且つ、前記所定の優先順位が高いバス・デバイスに前記バスの制御を許可する論理と、
を含む、ＰＣＩバス・アービタ。
【請求項２】
前記ＰＣＩバス・アービタに結合されたタイマをさらに含み、前記タイマが、再試行信号がＰＣＩバス・デバイスに送られた時に始動され、前記タイマによって判定される所定の期間の経過の後に、すべてのフェアネス・フラグが、セットされない論理状態に戻る、請求項１に記載のＰＣＩバス・アービタ。
【請求項３】
前記所定の期間が、プログラム可能である、請求項２に記載のＰＣＩバス・アービタ。
【請求項４】
フェアネス・サイクルが、前記ＰＣＩバスがアイドルである時の少なくとも１つのバス要求に応答して開始され、各要求元バス・デバイスが前記バス上で成功裡にデータ転送を完了した時に終了する、請求項１〜３のいずれか１項に記載のＰＣＩバス・アービタ。
【請求項５】
請求項１〜４のいずれか１項記載のＰＣＩバス・アービタを含むコンピュータ・システム。
【請求項６】
複数のＰＣＩバス・デバイスへの接続のためのＰＣＩバスを有するコンピュータ・システム内でのフェアネス論理に基くＰＣＩバス・アービトレーションの方法であって、各ＰＣＩバス・デバイスが、バス要求信号の使用によって前記ＰＣＩバスの制御を要求し、
（ａ）前記複数のＰＣＩバス・デバイスの各々の他のＰＣＩデバイスに関するＰＣＩバス・デバイスの所定の優先順位と、対応するフェアネス・フラグの状態とに応答して、前記ＰＣＩバスへのアクセスに関して前記複数のＰＣＩバス・デバイスから第１バス・デバイスを選択するステップであって、前記フェアネス・フラグがセットされておらず、且つ、前記所定の優先順位が高いＰＣＩバス・デバイスが前記第１バス・デバイスとして選択される、ステップ
（ｂ）前記第１バス・デバイスにより再試行信号が受け取られたかどうかを、再試行活動記録に基いて判定し、前記再試行信号が受け取られていない場合には、前記対応するフラグをセットし、それによって前記第１バス・デバイスのバス要求が他の要求信号の優先順位より下に下げられ、前記再試行信号が受け取られている場合には、セットされないステップと、
とを含み、すべての要求が処理されるまで、ステップ（ａ）ないし（ｂ）が繰り返される、ＰＣＩバス・アービトレーションの方法。
【請求項７】
ステップ（ａ）がさらに、前記第１バス・デバイスを選択する前記ステップの前に、フェアネス・サイクルを開始するステップをさらに含む、請求項６に記載の方法。
【請求項８】
ステップ（ａ）がさらに、前記フェアネス・サイクルを開始した後に、複数のフェアネス・フラグを初期状態にセットするステップをさらに含む、請求項７に記載の方法。
【請求項９】
前記フェアネス・フラグが、ＰＣＩバス・アービタ内のレジスタ・ビットである、請求項６〜８のいずれか１項に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全般的にはデータ処理全般の方法およびシステムに関し、具体的には、可変優先順位プロトコルおよびフェアネス・プロトコルに基づくバス・アービトレーションのための方法およびシステムに関する。
【０００２】
【従来の技術】
コンピュータ・システムには、通常は、システム・バス、ローカル・バス、および周辺バスなどの複数の種類のバスが含まれる。さまざまな電子回路デバイスおよび電子回路構成要素が、これらのバスを介して互いに接続され、これらのデバイスおよび構成要素のすべての間での相互接続が可能になる。
【０００３】
一般に、中央処理装置（ＣＰＵ）は、システム・バスに接続され、このシステム・バスを介して、ＣＰＵは、やはりシステム・バスに接続されるシステム・メモリと直接に通信する。ローカル・バスは、一部の集積度の高い周辺構成要素をＣＰＵと同一のバス上で接続することを目的とする。そのようなローカル・バスの１つが、ＰＣＩ（Peripheral Component Interconnect）バスとして知られている。ＰＣＩローカル・バス規格の下では、周辺構成要素を、グルー・ロジック（glue logic）の必要なしにＰＣＩローカル・バスに直接に接続することができる。したがって、ＰＣＩは、その上でグラフィックス・デバイスおよびハード・ディスク装置などの高性能周辺デバイスをＣＰＵに結合でき、これによって、これらの高性能周辺デバイスが、周辺バスに関連する一般的なアクセス待ち時間制約および帯域幅制約を回避できるようにする、バス規格を提供する。ＩＳＡ（Industry Standard Architecture）バスなどの周辺バスは、さまざまな周辺デバイスをコンピュータ・システムに接続するためのものである。これらの周辺デバイスには、通常は、キーボード、フロッピ駆動装置、およびプリンタなどの入出力デバイスが含まれる。
【０００４】
一般に、システム・バス、ローカル・バス、および周辺バスのそれぞれは、それに接続されたさまざまなデバイスの間でデータ転送を行うために、独立の組のプロトコル（または規則）を使用する。これらのプロトコルのそれぞれが、設計上直接にバスに組み込まれており、一般にバスの「アーキテクチャ」と呼ばれる。異なるバス・アーキテクチャの間のデータ転送では、第１のバス・アーキテクチャから転送されるデータが、受取り側の第２のバス・アーキテクチャによって使用可能または理解可能な形でない場合がある。したがって、あるバス・アーキテクチャから別のバス・アーキテクチャへ転送する必要があるデータを「変換」するための機構が開発されている。この変換機構は、通常は、バス対バス・ブリッジ（またはインターフェース）の形でハードウェア・デバイスに含まれ、このバス対バス・ブリッジを介して、２つの異なる種類のバスが接続される。
【０００５】
これに付随して、異なるバス上のデバイス間のシステム全体にわたる通信を可能にするために、あるバスの通信プロトコルを別のバスの通信プロトコルに一致させるためのさまざまなバス対バス・ブリッジが設計されてきた。たとえば、システム・バスとＰＣＩローカル・バスの間を接続するバス対バス・ブリッジを、ＰＣＩホスト・ブリッジと呼ぶ。ＰＣＩホスト・ブリッジには、システム・バスとＰＣＩローカル・バスの間でデータ通信を変換するための論理およびハードウェアのすべてが含まれ、この２つのバスの間でデータが理解可能に転送されることが保証される。異なるバスに接続された複数のデバイスが、ＣＰＵまたはローカル・バスへのアクセス権を同時に得る場合に、混乱が生じる。混乱は、システムに１つまたは複数のバス・マスタを導入することによって回避される。バス・マスタは、バスへのアクセスを制御する。言い換えると、バス・マスタは、すべてのバス要求を開始し、制御する。
【０００６】
どのデバイスまたはバス・マスタが次にバスを使用するかの決定を、バス・アービトレーションと呼ぶ。バス・アービトレーション方式では、バスを使用することを求めるデバイス（またはプロセッサ）が、バス要求の信号を送る。それに応答して、その後の時点で、アービタが、許可信号をデバイスに送る。許可が受け取られた後に、デバイスは、バスを使用することができる。デバイスは、後に、バスがもはや不要であることをアービタに知らせる。その後、アービタは、別のデバイスにバスを許可することができる。
【０００７】
アービトレーション方式では、通常は、バスを許可されるデバイスを選択する際に、２つの要因のバランスをとろうとする。第１に、各デバイスは、バス優先順位を有し、最高の優先順位のデバイスが最初にサービスされなければならない。第２に、優先順位が低いものであっても、デバイスが絶対に完全にはロック・アウトされないことを保証するために、ＰＣＩなどのほとんどの入出力バスでは、アービタがなんらかの種類のフェアネス・プロトコルを実施することも必要である。フェアネス・プロトコルの目的は、すべてのデバイスがバスのターンを受け取ることを保証することである。たとえば、従来のフェアネス・プロトコルの１つが、ラウンド・ロビン方式である。ラウンド・ロビン・フェアネス・プロトコルの下では、バス動作を完了したばかりのデバイスは、まずすべての要求元デバイスがバスへのアクセスを許可されるまで、第２の動作のためのバスへのアクセスを許可されない。
【０００８】
バスが、アービタ内でのバスへのアクセスを制御するフェアネス・プロトコルを提供できる場合であっても、許容可能なバスへのアクセスが、１つまたは複数のデバイスに対して、他の高性能デバイスによって効果的に拒否される可能性がある。これは、フェアネス・プロトコルが回避するはずであった、予想外の問題である。これは、デバイスのバスへのアクセスに干渉する「ビート」周波数の問題である。この「ビート」周波数の概念は、下で説明する。
【０００９】
ＰＣＩなどの一部のバスは、通常は「バックオフ」機能と呼ばれるパフォーマンス機能を備える。この「バックオフ」機能によって、デバイスは、その時点で要求を処理できない場合にバスから切断することができるようになる。ＰＣＩでは、この機能をRetry（再試行）と呼ぶ。ＰＣＩデバイスが、要求の発生時にその要求を処理できない場合には、要求のターゲットは、バス上で要求を発行したマスタに、後でもう一度試行するように指示する「Retry」を発行することができる。
【００１０】
ＰＣＩの場合、通常のプラットフォームは、システム・バスとＰＣＩバスの間のバス同期化をもたらすためにＰＣＩホスト・ブリッジを備える。プラットフォームは、追加のＰＣＩバス・セグメントを提供するために複数のＰＣＩ対ＰＣＩバス・ブリッジも備える場合がある。通常、各ＰＣＩバス・セグメントは、それ自体のアービタ（フェアネス・プロトコルを備える）を有する。各ブリッジは、通常は、バス・トランザクションがブリッジを介して両方向に（ブリッジのプライマリ側からセカンダリ側へ、および、セカンダリ側からプライマリ側へ）流れる際に、バス・トランザクションを一時的にバッファリングするためのポスティング・バッファを有する。
【００１１】
ビート周波数が、効果的にデバイスがバスにアクセスするのを拒否する仕方には、ブリッジ内のバッファの組と、ブリッジ・アービタと、バス上のデバイスによるバス・トラフィックとの間の相互作用が含まれる。たとえば、ＰＣＩホスト・ブリッジまたはＰＣＩ対ＰＣＩブリッジの下のバスが、ブリッジの下の４つのデバイス（デバイスＡ、デバイスＢ、デバイスＣ、およびデバイスＤ）に対するラウンド・ロビン・フェアネス・プロトコルを有すると仮定する。また、ブリッジに最高の優先順位（優先順位０）が割り当てられ、デバイスＡに次に高い優先順位（優先順位１）が割り当てられ、デバイスＢに次に高い優先順位（優先順位２）が割り当てられ、デバイスＣに次に高い優先順位（優先順位３）が割り当てられ、デバイスＤに次に高い優先順位（優先順位４）が割り当てられると仮定する。すべてのデバイスが、同時にバスを要求した場合、フェアネス・プロトコルは、各デバイスがバスの使用を試みる機会を得ることを保証する。この例のアービトレーション優先順位は、単純に、デバイスがバスの使用を試みるターンを得る順序を決定する。この例では、すべてのデバイスがバスの使用を要求する時に、ブリッジが最初にアクセスを許可され、その後はデバイスＡからデバイスＤの順になる。この方式の下では、デバイスＡおよびデバイスＢの両方が、バスのターンを得、ブリッジのバッファを満たし、その結果、デバイスＣがバスを得た時に、デバイスＣは、ブリッジのバッファが満杯なのでRetryを得る。結果的に、ブリッジは、ブリッジの反対側のトランザクションに応じて、バッファの一部を空にする。その後、デバイスＤ、デバイスＡ、およびデバイスＢがバスのターンを得、やはりバッファを満たす。デバイスＣがもう一度回転式にバスのターンを得る時には、デバイスＣは、やはりブリッジのバッファが満杯なので、もう一度Retryを受け取る。特定のデバイスがバスのターンを得るたびに、他のデバイスがブリッジ・バッファを満杯にしているのでRetry（または、バスの種類に応じた同等物）によって退けられるような、ビート周波数が発生する恐れがある。Retryの数が比較的多い時には、デバイスは、オーバーランまたはアンダーランを起こし、ソフトウェアがオーバーランまたはアンダーランを検出し、動作を繰り返すことからかなりの性能低下が生じる可能性がある。
【００１２】
単純にブリッジにバッファを追加するだけでは、デバイスＡ、デバイスＢ、およびデバイスＤが「ビート」周波数問題を起こすために転送する必要があるデータの量が変化するに過ぎない。非常に多数のバッファの追加によって、この問題は除去されるはずであるが、これは、あまりに高価なので実用的ではない。
【００１３】
【発明が解決しようとする課題】
したがって、ビート周波数からの干渉なしに各デバイスがバスのフェアネス・ターンを得る確率を高めるために回転シーケンスが変更されるようにする、アービトレーション優先順位レベルを変更する方式が必要である。
【００１４】
【課題を解決するための手段】
前に述べた必要は、本発明によって満たされる。したがって、第１の形態では、バス・ブリッジを介してＣＰＵと通信するローカル・バスを有するコンピュータ・システムであって、バス・ブリッジが、バスに接続された複数のバス・デバイスからのバス要求信号を制御し、優先順位を付けるためのバス・アービタを含む、コンピュータ・システムを提供する。バスの許可は、各デバイスの優先順位、フェアネス・サイクル内の前のアクセス、および再試行活動記録に基づく。また、各バス・デバイスの所定の優先順位と、各バス・デバイスのフェアネス・サイクル内の前のアクセスとに基づいてバス要求信号を制御し、優先順位を付けるためのフェアネス論理を含むバス・アービタを開示する。このアービタには、フェアネス論理に基づいてバス・デバイスにバスの制御を許可するための論理が含まれる。
【００１５】
本発明には、複数のバス・デバイスからバス要求信号を受け取るステップと、フェアネス・サイクルを開始するステップと、他のデバイスに関するバス・デバイスの最高の優先順位と、フェアネス・フラグがバス・デバイスに関してセットされているか否かに基づいて、バス・デバイスから単一のバス・デバイスを選択するステップとを含む、コンピュータ・システム内のバス・アービトレーションの方法も含まれる。フラグがセットされている場合には、優先順位が下げられる。フラグは、デバイスがバスへのアクセスを許可され、再試行信号を受け取らない場合に限ってセットされる。
【００１６】
【発明の実施の形態】
本発明の原理およびその長所は、図面の図１ないし５に示された例示的実施形態を参照することによって最もよく理解される。図面では、同様の符号が同様の部分を示す。以下の説明では、不要な詳細で本発明が不明瞭にならないようにするために、周知の要素は詳細な説明なしで提示する。ほとんどの部分で、本発明の完全な理解を得るのに必要でない詳細は、そのような詳細が当業者の技術の範囲内である限りは省略した。本明細書に記載のさまざまな要素の回転を制御するのに使用される制御回路または機構に関する詳細は、そのような制御回路が当業者の技術の範囲内であるので省略する。
【００１７】
本発明は、多数の異なるオペレーティング・システムの下でさまざまなコンピュータ内で適用することができる。コンピュータは、たとえば、パーソナル・コンピュータ、ミニコンピュータ、またはメインフレーム・コンピュータとすることができる。
【００１８】
ここで図面、具体的には図１を参照すると、本発明の好ましい実施形態を使用することができる、ＰＣＩローカル・バス・アーキテクチャを有する通常のコンピュータ・システムのブロック図が示されている。図からわかるように、プロセッサ１１２、キャッシュ・メモリ１１３、メモリ・コントローラ１１４、およびダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）１１５が、コンピュータ・システム１０１のシステム・バス１２８に接続される。プロセッサ１１２、キャッシュ・メモリ１１３、メモリ・コントローラ１１４、およびＤＲＡＭ１１５は、ＰＣＩホスト・ブリッジ１１１を介してコンピュータ・システム１０１のＰＣＩローカル・バス１２０にも結合される。ＰＣＩホスト・ブリッジ１１１は、低待ち時間経路を提供し、この低待ち時間経路を介して、プロセッサ１１２は、バス・メモリ・アドレス空間内または入出力アドレス空間内もしくはその両方のどこかにマッピングされたＰＣＩデバイスに直接アクセスすることができる。ＰＣＩホスト・ブリッジ１１１は、ＰＣＩデバイスがＤＲＡＭ１１５に直接にアクセスできるようにするための高帯域幅経路も提供する。ＰＣＩホスト・ブリッジ１１１には、データ・バッファリング／ポスティングおよびアービトレーションなどのさまざまな機能を含めることができる。
【００１９】
ＰＣＩローカル・バス１２０には、ローカル・エリア・ネットワーク（ＬＡＮ）インターフェース１１６および拡張バス・インターフェース１２７などの他のデバイスも接続することができる。ＬＡＮインターフェース１１６は、コンピュータ・システム１０１を、イーサネットまたはトークン・リングなどのローカル・エリア・ネットワーク１１７に接続するためのものである。この構成では、別々のＰＣＩホスト・ブリッジの下で別々のＰＣＩローカル・バスをサポートすることもできる。たとえば、ＰＣＩ対ＰＣＩブリッジ１１８を用いると、ＰＣＩローカル・バス１３０を、ＰＣＩローカル・バス１２０に接続することができるようになる。さまざまなＰＣＩデバイス１３１、１３２、１３３、および１３４が、ＰＣＩローカル・バス１３０に接続される。拡張バス・インターフェース１２７は、ＩＳＡバス、ＥＩＳＡバス、またはマイクロチャネル・アーキテクチャ（ＭＣ−Ａ）バスなどのＰＣＩ以外の周辺バス１２１を、ＰＣＩローカル・バス１２０に接続する。通常、ある基本入出力機能を実行するためのさまざまなＰＣＩ以外の周辺デバイスが、周辺バス１２１などの周辺バスの１つに接続される。
【００２０】
一般に、ＰＣＩローカル・バス１２０とＰＣＩローカル・バス１３０は、拡張機能を必要とせずに、４つまでのアドイン・ボード・コネクタをサポートすることができる。オーディオ・アダプタ・ボード１２２、モーション・ビデオ・アダプタ・ボード１２３、およびグラフィックス・アダプタ・ボード１２４が、アドイン・ボード・コネクタを介してＰＣＩローカル・バス１２０またはＰＣＩローカル・バス１３０に接続することのできるデバイスの例である。
【００２１】
ここで図２を参照すると、ホスト・ブリッジとＰＣＩ対ＰＣＩブリッジの下の別々のＰＣＩローカル・バスを示すＰＣＩ構成の詳細図が示されている。ＰＣＩホスト・ブリッジ１１１は、システム・バス１２８に結合されたバス・エージェントと、ＰＣＩローカル・バス１２０に結合されたバス・エージェントの間の通信を可能にする。さらに、ＰＣＩ対ＰＣＩブリッジ１１８は、ＰＣＩローカル・バス１３０に結合されたバス・エージェント（ＰＣＩローカル・バス１３０は周辺バスである）と、メモリ・コントローラ１１４（図１）の間の通信を可能にする。ＰＣＩ対ＰＣＩブリッジ１１８は、プロセッサ１１２と、ＰＣＩローカル・バス１３０に結合されたバス・エージェントの間の通信も可能にする。
【００２２】
ＬＡＮインターフェース１１６、周辺バス１２１、およびグラフィックス・アダプタ・ボード１２４は、ＰＣＩローカル・バス１２０を介する通信のために結合されたバス・エージェントである。さらに、ＰＣＩホスト・ブリッジ１１１およびＰＣＩ対ＰＣＩブリッジ１１８は、ＰＣＩローカル・バス１２０を介する通信のためのバス・エージェントとして結合される。ＰＣＩホスト・ブリッジ１１１およびＰＣＩ対ＰＣＩブリッジ１１８は、ＰＣＩローカル・バス１２０を介するアクセス・サイクルのイニシエータおよびターゲットになる能力を有する。好ましい実施形態では、ＰＣＩローカル・バス１２０は、３２ビット・メモリ・アドレス空間および３２ビット入出力アドレス空間を備え、アドレスとデータが同一のバス上で多重化されている。
【００２３】
ＰＣＩホスト・ブリッジ１１１およびＰＣＩ対ＰＣＩブリッジ１１８などのバス・ブリッジは、通常は、プライマリ・バスとセカンダリ・バスの間に結合される。バス・ブリッジは、プライマリ・バス上で開始されたアクセス要求がセカンダリ・バス上の宛先を有することを可能にし、セカンダリ・バス上で開始されたアクセス要求がプライマリ・バス上の宛先を有することを可能にする。たとえば、システム・バス１２８からアクセス要求を受け取った後に、ＰＣＩホスト・ブリッジ１１１は、ＰＣＩローカル・バス１２０上でアクセス要求を開始して、ＬＡＮインターフェース１１６、ＰＣＩ対ＰＣＩブリッジ１１８、拡張バス・インターフェース１２７、またはグラフィックス・アダプタ・ボード１２４のうちの１つまたは複数と通信する。また、ＰＣＩローカル・バス１２０からアクセス要求を受け取った後に、ＰＣＩホスト・ブリッジは、システム・バス１２８上でアクセス要求を開始して、メモリ・コントローラ１１４と通信する。同様に、ＰＣＩローカル・バス１３０からアクセス要求を受け取った後に、ＰＣＩ対ＰＣＩブリッジ１１８は、ＰＣＩローカル・バス１２０上でアクセス要求を開始して、ＰＣＩホスト・ブリッジ１１１と通信する。また、ＰＣＩローカル・バス１２０からアクセス要求を受け取った後に、ＰＣＩ対ＰＣＩブリッジ１１８は、ＰＣＩローカル・バス１３０上でアクセス要求を開始して、ＰＣＩデバイス１３１と通信する。
【００２４】
要するに、ＰＣＩホスト・ブリッジ１１１は、システム・バス１２８に結合されたバス・エージェントと、ＰＣＩローカル・バス１３０に結合されたバス・エージェントの間の通信を可能にする。ＰＣＩローカル・バス１３０には、ＰＣＩデバイス１３１ないし１３４などのＰＣＩデバイスが接続されている。
【００２５】
ここで図３を参照すると、本発明の好ましい実施形態と共に使用することができる、ＰＣＩ対ＰＣＩブリッジ１１８の機能ブロック図が示されている。図からわかるように、ＰＣＩ対ＰＣＩブリッジ１１８は、２つの側面すなわち、プライマリＰＣＩバスまたはＰＣＩローカル・バス１２０との間のトラフィックを通信するプライマリ側３０２と、セカンダリＰＣＩバスまたはＰＣＩローカル・バス１３０との間のトラフィックを通信するセカンダリ側３０４を有する（ＰＣＩアーキテクチャでは、用語「プライマリ側」は、単にブリッジのＣＰＵおよびメモリに近い側を表すのに使用され、用語「セカンダリ側」は、ＣＰＵおよびメモリから遠い側を指す）。一連のデータ・バッファ３０６が、ＰＣＩローカル・バス１２０からＰＣＩローカル・バス１３０へ（すなわち、プライマリ・バスからセカンダリ・バスへ）向かう通信の要求、データ、および命令を一時的に記憶するために設けられる。同様に、ＰＣＩローカル・バス１３０からＰＣＩローカル・バス１２０へ（すなわち、セカンダリ・バスからプライマリ・バスへ）向かう通信の要求、データおよび命令を一時的に記憶するための、一連のデータ・バッファ３０８もある。プライマリおよびセカンダリ・バス・シーケンス制御またはシーケンス制御ユニット３１０は、米国オレゴン州ポートランドのＰＣＩ Special Interest Groupが発行するＰＣＩ Local Bus Specification, Revision 2.2（以下では「ＰＣＩ Bus Specification」と呼称する）に記載されているように、ＰＣＩ対ＰＣＩブリッジ１１８のプライマリ・インターフェースとセカンダリ・インターフェースでマスタ・トランザクションを開始し、ターゲット・トランザクションに応答する。シーケンス制御ユニット３１０は、ＰＣＩ対ＰＣＩブリッジのセカンダリ側３０４でのバス・アクセスの要求を開始する。デバイス（ＡないしＤ）のそれぞれも、ＰＣＩ Bus Specificationの要件に適合するシーケンス制御ユニット（図示せず）を有する。シーケンス制御ユニットは、マスタとしてバスを許可された後、または、別のマスタによってターゲットとしてアドレッシングされた後に、それぞれのＰＣＩバス信号シーケンシングを制御する。セカンダリ・バス・アービタ３１２は、信号ＲＥＱ＃およびＧＮＴ＃（図３）を使用してＰＣＩ対ＰＣＩブリッジのセカンダリ側３０４のアービトレーションを実行し、ＰＣＩ Bus Specificationのアービトレーション要件に適合する。セカンダリ・バス・アービタ３１２には、複数のデータ値を記憶するために設けられるフェアネス・レジスタ３１４も含まれる。本発明の一実施形態では、ＰＣＩローカル・バス１３０上にＰＣＩデバイス１３１ないし１３４を有する図２のＰＣＩ構成に対応する、５ビットの情報を含むレジスタを有することができる。シーケンス制御ユニット３１０とセカンダリ・バス・アービタ３１２の間の相互協調処理は、ＰＣＩ Bus Specificationの要件に適合し、本明細書に記載のフェアネス・レジスタ３１４によって機能強化される。セカンダリ・バス・アービタ３１２がサポートする信号ＲＥＱ＃ＡないしＲＥＱ＃ＤおよびＧＮＴ＃ＡないしＧＮＴ＃Ｄは、デバイスＡないしＤ（図２では、それぞれＰＣＩデバイス１３１ないし１３４）がＰＣＩローカル・バス１３０へのアク��スを要求するのに使用する要求信号および許可信号である。
【００２６】
セカンダリ・バス・アービタ３１２には、要求信号線３１６、３１７、３１８、および３１９（各デバイスが、バス上にそれ自体の要求信号を有する）のそれぞれのフェアネス・ビットを含むフェアネス・レジスタ３１４が含まれる。フェアネス・レジスタ３１４のビット割当は、ビット０がＰＣＩ対ＰＣＩブリッジ１１８に割り当てられ、ビット１がデバイスＡに割り当てられ、ビット２がデバイスＢに割り当てられ、ビット３がデバイスＣに割り当てられ、ビット４がデバイスＤに割り当てられている。
【００２７】
セカンダリ・バス・アービタによって使用されるアービトレーション・アルゴリズムは、ＰＣＩ Bus Specificationの要件を満足するものであればどのアルゴリズムでもよい。このアルゴリズムは、フェアネス・レジスタ３１４と共に使用される時に、単純な線形優先順位アルゴリズムとすることもできる。フェアネス・レジスタ３１４の使用は、単純な線形優先順位アルゴリズムをＰＣＩ Bus Specification適合にするために必要な、単純な線形優先順位アルゴリズムへの追加である。この説明の残りでは、フェアネス・レジスタ３１４の効果によって変更された単純な線形優先順位を論ずる。
【００２８】
ＰＣＩ対ＰＣＩブリッジ１１８は、最高の優先順位を与えられる。デバイスＡ（すなわち、図２のＰＣＩデバイス１３１）は、要求信号線ＲＥＱ＃Ａに関連するが、次に高い優先順位を与えられる。したがって、デバイスＡは、ほぼ同時にアクセスを要求する他の競合デバイスより優先されて、最初にバスへのアクセス権を得る。デバイスＢ（すなわち図２のＰＣＩデバイス１３２）、次にデバイスＣ（すなわち図２のＰＣＩデバイス１３３）、最後にデバイスＤ（すなわち図２のＰＣＩデバイス１３４）というのが、ＰＣＩローカル・バス１３０の残りのデバイスの優先順位の順序である。
【００２９】
図４および５は、セカンダリ・バス・アービタ３１２の論理方式を示す図である。複数のデバイスが同時にバスを要求した時に、フェアネス・プロトコル・シーケンスが開始される（ステップ４００）。セカンダリ・バス・アービタ３１２は、フェアネス・レジスタ３１４（図３）のすべてのビットを０にリセットする（ステップ４０２）ことによってフェアネス・プロトコル・シーケンス（ステップ４００）を開始する。セカンダリ・バス・アービタ３１２は、デバイス（ＡないしＤおよびブリッジ）のそれぞれからの、図３に示されたＲＥＱ＃信号のそれぞれを検査して、要求信号（ＲＥＱ＃）がアサートされたかどうかを判定する（ステップ４０４）。アサートされた要求信号（ＲＥＱ＃）がない場合には、セカンダリ・バス・アービタ３１２は、タイマ（図示せず）の使用によって、時間の所定の経過が満了したかどうかを判定する（ステップ４０５）。タイマの使用によって、Retryの後のバスのアイドル時間が、簡単にセットまたは事前プログラムすることのできる所定の時間の量までに制限される。Retryを受け取ったデバイスの１つが、タイマがタイム・アウトした時にバスの使用を試みていない場合には、すべてのデバイスのフェアネス・ビットを０にリセットし、新しいフェアネス・サイクルを開始できるようにする。そのようなタイマは、従来からコンピュータ・システム内に存在するものとすることができ、当業者によく知られている。
【００３０】
要求信号（ＲＥＱ＃）がある場合には、セカンダリ・バス・アービタ３１２は、アサートされている現在の許可信号（ＧＮＴ＃）のすべてをデアサートする。セカンダリ・バス・アービタ３１２は、対応するフェアネス・レジスタ・ビットに１がセットされていない、最も高い優先順位の要求元（すなわちＲＥＱ＃がアサートされている）への許可信号をアサートする（ステップ４０６）。その後、セカンダリ・バス・アービタ３１２は、次のバス・トランザクションが開始されるのを待つ（ステップ４０８）。次のトランザクションが開始された後に、セカンダリ・バス・アービタ３１２は、関連するフェアネス・レジスタ３１４のビットに１がセットされていない他のデバイスの要求信号がアサートされているかどうかを判定する（ステップ４１０）。そうである場合には、セカンダリ・バス・アービタ３１２は、ステップ４１０の要求のターゲットがRETRYを応答したかどうかを判定する（ステップ４１４）。ステップ４１４の判定が肯定の場合、セカンダリ・バス・アービタ３１２は、ステップ４０４に戻る。その一方で、ステップ４１４の判定が否定の場合、セカンダリ・バス・アービタ３１２は、このデバイスのフェアネス・ビットに１をセットし（ステップ４１６）、ステップ４０４に戻る。
【００３１】
ステップ４１０の判定が否定の場合、セカンダリ・バス・アービタ３１２は、ターゲットが再試行を応答したかどうかを判定する（ステップ４１２）。ステップ４１２の判定が否定の場合、セカンダリ・バス・アービタ３１２は、ステップ４０２に戻り、フェアネス・レジスタのすべてのビットをリセットする。その一方で、セカンダリ・バス・アービタ３１２が、ターゲットが再試行を応答したと判定する場合（ステップ４１２）、セカンダリ・バス・アービタ３１２は、要求信号をアサートされている別のデバイスが、そのフェアネス・ビットに１がセットされているかどうかを調べる（ステップ４１８）。要求信号がアサートされ、フェアネス・ビットに１がセットされている別のデバイスがない場合には、このルーチンはステップ４０２に戻り、フェアネス・レジスタのすべてのビットに０をセットする。しかし、要求信号がアサートされ、フェアネス・ビットに１がセットされている別のデバイスがある場合には、セカンダリ・バス・アービタ３１２は、現在の許可信号をデアサートし、フェアネス・レジスタ・ビットに１がセットされている、最も高い優先順位の要求元への許可信号をアサートする（フェアネス・アルゴリズムを使用して）（ステップ４２０）。セカンダリ・バス・アービタ３１２は、その後、ステップ４０８を繰り返す。
【００３２】
動作
アービタを使用する形は、例によって最もよく示すことができる。複数のデバイス（たとえばデバイスＡ、デバイスＢ、およびデバイスＣ）が同時にバスを要求する時に、フェアネス・ルーチンが開始される。デバイスが、Retryなしでバスのターンを受け取った（進行する）後に、セカンダリ・バス・アービタ３１２は、そのデバイスのRequest信号線（フェアネス・ビットに１がセットされている）を、やはりRequest信号線をアクティブにしている他のデバイスがバスのターンを受け取るまで、無視する。表１に、最初のフェアネス判定時の各デバイスの、アービトレーション・レベル、要求の状況、ターゲットが再試行を応答したかどうか、およびフェアネス・ビットを示す。この例では、「フェアネス・ビット  前／後」と記された列に、フェアネス・レジスタ３１４（図３）のビットの値が含まれる。この値は、ステップ４１６（図４）で１にセットされ、ステップ４０２（図４）で０にリセットされる。
【００３３】
【表１】
0004010476.tif 000002
【００３４】
表１に示された例では、デバイスＡが、優先順位を有し、再試行を受け取らなかった。アービトレーション処理に入る唯一のデバイスは、要求をアサートし（「要求の状況」列の「○」）、フェアネス・ビット（表の「フェアネス・ビット前／後」列に示されたビット）に０をセットされているデバイスである。その結果、デバイスＡは、バスへのアクセスを許可され、そのフェアネス優先順位ビットに「１」がセットされた。したがって、将来の要求は無視される。次にターンを得るデバイスは、表２からわかるようにデバイスＢである。
【００３５】
【表２】
0004010476.tif 000003
【００３６】
表２からわかるように、デバイスＡは、優先順位を有するが、フェアネス・ビットに１がセットされているので、バスのターンを得ない。したがって、デバイスＢが、バスのターンを許可される。デバイスＢがアクセスを許可された後に、バスのターンを得るのはデバイスＣである。しかし、例示のために、デバイスＣがターゲットから再試行を受け取ると仮定する。したがって、デバイスＣのフェアネス・ビットには、「１」がセットされない（表３に示されている）。すなわち、公平さの観点からは、デバイスＣがバスのターンを受け取らなかった場合と同様であり、セカンダリ・バス・アービタ３１２は、デバイスＣのRequestを認識し、デバイスＣは、バス上で進行する（バスを介してターゲットと情報を交換する）まで、同一のフェアネス・サイクル内でバスへのアクセスを取得し続けることができる。
【００３７】
【表３】
0004010476.tif 000004
【００３８】
デバイスＣがRetryなしでバスのターンを得た後に、他のデバイスもバスを求める場合には、デバイスＣのフェアネス・ビットに「１」がセットされ、デバイスＣのRequestが無視されるようになる。
【００３９】
【表４】
0004010476.tif 000005
【００４０】
最後に、フェアネス・ビット＝０でアクティブのRequest信号線を有する追加のデバイスがバス上に存在しない状態（表４に示された状態）が存在する。その時点で、すべてのフェアネス・ビットが、セカンダリ・バス・アービタ３１２によって「０」にリセットされ、表５に示されているように、もう一度フェアネス・サイクルを開始できるようになる。
【００４１】
【表５】
0004010476.tif 000006
【００４２】
この解決策を用いると、セカンダリ・バス・アービタ３１２が、進行したデバイスのバスへのアクセスを拒否する（そのデバイスのRequestを無視することによって）が、前にRetryを受け取ったデバイスの、フェアネス・サイクル中のバスへの余分なアクセスを許可することに留意されたい。タイマによって、Retryの後のバス上のアイドル時間が制限される。したがって、デバイスのうちでRetryを受け取った１つが、タイマがタイム・アウトした時にバスの使用を試みていない場合には、すべてのデバイスのフェアネス・ビットが０にリセットされ、新しいフェアネス・サイクルを開始できるようになる。
【００４３】
要するに、このアービタは、従来技術に対する複数の実質的な長所を有する。この解決策を用いると、アービトレーション・レベルを同一に保つことができ、バスのターンでRetryを受け取ったデバイスのそれぞれが、バス上でトランザクションが処理される（そのデバイスが進行する）まで、同一のフェアネス・サイクル中にバスの余分のターンを受け取ることができる。したがって、Retry信号が原因でバスへのアクセスを拒否されるデバイスがなくなる。
【００４４】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４５】
（１）マイクロプロセッサと、
バス・ブリッジを介して前記マイクロプロセッサに結合されたローカル・バスであって、前記バス・ブリッジが、前記マイクロプロセッサと前記ローカル・バスとの間のデータ転送を適応させるように構成される、ローカル・バスと、
前記ローカル・バスに結合された複数のバス・デバイスからのバス要求信号を制御し、優先順位を付けるための、前記バス・ブリッジ内のバス・アービタであって、前記バス・アービタが、前記複数のバス・デバイスの第１バス・デバイスの、他のバス・デバイスに対する相対的な所定の優先順位と、フェアネス・サイクル内の前記ローカル・バスへの前記第１バス・デバイスの前のアクセスとに基づいて、前記第１バス・デバイスに前記バスの制御を許可するための論理を含む、バス・アービタと
を含むコンピュータ・システム。
（２）前記バス・アービタが、さらに、制御論理を含み、この論理において、前記バスの制御は、前記フェアネス・サイクル内の前記ローカル・バスへのバス・デバイスの前の不成功のアクセスに応答して許可され、各バス・デバイスが前記フェアネス・サイクル内に成功した場合には、他のバス・デバイスに対する相対的な前記第１バス・デバイスの前記所定の優先順位に応答して許可される、上記（１）に記載のコンピュータ・システム。
（３）前記前のアクセスが、前記第１バス・デバイスが前記バスへのアクセス権を受け取り、前記第１バス・デバイスが再試行信号を受け取らない時に、少なくとも１つのフェアネス・フラグをセットすることによって記録される、上記（２）に記載のコンピュータ・システム。
（４）前記第１バス・デバイスの優先順位が、前記フェアネス・フラグがセットされている時に、他の要求信号の優先順位未満に下げられる、上記（３）に記載のコンピュータ・システム。
（５）各前記フェアネス・フラグが、前記バス・アービタによって制御可能なデータ・レジスタ・ユニット内のビットを含む、上記（３）に記載のコンピュータ・システム。
（６）前記バス・アービタに結合されたタイマをさらに含み、前記タイマが、再試行信号がバス・デバイスに送られた時に始動され、前記タイマによって判定される所定の期間の経過の後に、すべてのフェアネス・フラグが、セットされない位置に戻る、上記（４）に記載のコンピュータ・システム。
（７）前記所定の期間が、プログラム可能である、上記（６）に記載のコンピュータ・システム。
（８）前記フェアネス・サイクルが、前記バスがアイドルである時の少なくとも１つのバス要求に応答して開始され、各要求元バス・デバイスが前記バス上で成功裡に転送を完了した時に終了する、上記（１）に記載のコンピュータ・システム。
（９）コンピュータ・システムのためのバス・アービタであって、前記コンピュータ・システムが、複数のバス・デバイスに接続するためのバスを有し、各バス・デバイスが、バス要求信号の使用によって前記バスの制御を要求し、
各バス・デバイスの所定の優先順位と、フェアネス・サイクル内の各バス・デバイスの前のアクセスとに基づいて、バス要求信号を制御し、優先順位を付けるためのフェアネス方式を組み込んだ論理と、
前記優先順位およびフェアネス方式に基づいて、バス・デバイスに前記バスの制御を許可する論理と
を含む、バス・アービタ。
（１０）前記前のアクセスが、第１バス・デバイスが前記バスへのアクセス権を受け取り、前記第１バス・デバイスが再試行信号を受け取らない時に、対応するフラグをセットすることによって記録される、上記（９）に記載のバス・アービタ。
（１１）前記第１バス・デバイスの優先順位が、前記フェアネス・フラグがセットされている時に、他の要求信号の優先順位より下に下げられる、上記（１０）に記載のバス・アービタ。
（１２）各前記フラグが、前記バス・アービタによって制御可能なデータ・レジスタ・ユニット内のビットを含む、上記（１０）に記載のバス・アービタ。
（１３）前記バス・アービタに結合されたタイマをさらに含み、前記タイマが、再試行信号がバス・デバイスに送られた時に始動され、前記タイマによって判定される所定の期間の経過の後に、すべてのフェアネス・フラグが、セットされない論理状態に戻る、上記（１１）に記載のバス・アービタ。
（１４）前記所定の期間が、プログラム可能である、上記（１３）に記載のバス・アービタ。
（１５）前記フェアネス・サイクルが、前記バスがアイドルである時の少なくとも１つのバス要求に応答して開始され、各要求元バス・デバイスが前記バス上で成功裡にデータ転送を完了した時に終了する、上記（９）に記載のバス・アービタ。
（１６）複数のバス・デバイスへの接続のためのバスを有するコンピュータ・システム内でのバス・アービトレーションの方法であって、各バス・デバイスが、バス要求信号の使用によって前記バスの制御を要求し、
（ａ）前記複数のバス・デバイスの他のデバイスに関するバス・デバイスの所定の優先順位と、対応するフラグの第１論理状態とに応答して、前記バスへのアクセスに関して前記複数のバス・デバイスから第１バス・デバイスを選択するステップであって、前記フラグが、前記バスを介する情報の交換をもたらす対応するバス・トランザクションに応答して、第２論理状態にセットするために動作可能である、第１バス・デバイスを選択するステップ
を含む方法。
（１７）（ｂ）再試行信号が受け取られたかどうかを判定し、前記再試行信号が受け取られていない場合に、前記対応するフラグを前記第２論理状態にセットするステップと、
（ｃ）すべての要求が処理されるまで、ステップ（ａ）ないし（ｃ）を繰り返すステップと
をさらに含む、上記（１６）に記載の方法。
（１８）ステップ（ａ）がさらに、前記第１バス・デバイスを選択する前記ステップの前に、フェアネス・サイクルを開始する追加ステップを含む、上記（１６）に記載の方法。
（１９）ステップ（ａ）がさらに、前記フェアネス・サイクルを開始した後に、複数のフラグを初期状態にセットする追加ステップを含む、上記（１８）に記載の方法。
（２０）前記フラグが、バス・アービタに結合されたレジスタ・ビットである、上記（１６）に記載の方法。
（２１）（ｄ）ステップ（ａ）での前記バス・デバイスの選択に基づいて、前記バスへのアクセスを許可するステップ
をさらに含む、上記（１７）に記載の方法。
（２２）要求がアサートされない場合に所定の時間期間が満了したかどうかを判定し、ステップ（ａ）を繰り返さない場合に、前記所定の時間期間が満了したならば、ステップ（ａ）ないし（ｄ）を繰り返すステップをさらに含む、上記（２１）に記載の方法。
（２３）前記所定の時間期間が、前記バス・アービタに結合されたタイマによって決定される、上記（２２）に記載の方法。
（２４）前記所定の時間期間が、プログラム可能である、上記（２３）に記載の方法。
（２５）対応するフラグのすべてが前記第２論理状態にある場合に、現在のフェアネス・サイクルが終了し、前記バス・アクセスが、前記所定の優先順位に応答して決定されるステップ
をさらに含む、上記（１６）に記載の方法。
（２６）前記複数のデバイスのうちで前記バスへのアクセスを要求する各バス・デバイスに対応するすべてのフラグが前記第２論理状態になるまで、ステップ（ａ）を繰り返すステップ
をさらに含む、上記（１６）に記載の方法。
（２７）前記現在のフェアネス・サイクルが、バス・アクセスを要求する各バス・デバイスが前記バス上でデータ転送を成功裡に完了した時に終了する、上記（１８）に記載の方法。
（２８）要求がアサートされない場合に所定の時間期間が満了したかどうかを判定し、ステップ（ｂ）を繰り返さない場合に、前記所定の時間期間が満了したならば、ステップ（ｄ）、（ｂ）、および（ｃ）を繰り返すステップをさらに含む、上記（２１）に記載の方法。
（２９）計算機可読媒体内で実施されるコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品が、
（ａ）フェアネス・サイクルを開始するステップと、
（ｂ）複数のフラグを初期状態にセットするステップと、
（ｃ）複数のバス・デバイスの他のデバイスに関するバス・デバイスの最高の優先順位と、対応するフラグが前にセットされてないかどうかとに基づいて、前記複数のバス・デバイスから単一のバス・デバイスを選択するステップと、
（ｄ）再試行信号が受け取られたかどうかを判定し、前記再試行信号が受け取られない場合に、前記対応するフラグをセットし、ステップ（ｄ）ないし（ｅ）を繰り返すステップと、
（ｅ）前記フェアネス・サイクル内のすべての要求が処理されるまで、ステップ（ｃ）ないし（ｅ）を繰り返すステップと
を含む、バスの制御に関する前記複数のバス・デバイスの要求のアービトレーションのための方法を実行するために計算機によって実行可能である、コンピュータ・プログラム製品。
（３０）ステップ（ｃ）が、さらに、要求がアサートされていない場合に所定の時間期間が満了したかどうかを判定し、ステップ（ｃ）を繰り返さない場合に、前記所定の時間期間が満了したならば、ステップ（ｂ）ないし（ｃ）を繰り返すステップを含む、上記（２９）に記載のコンピュータ・プログラム製品。
（３１）前記所定の時間期間が、バス・アービタに結合されたタイマによって決定される、上記（３０）に記載のコンピュータ・プログラム製品。
（３２）前記所定の時間期間が、プログラム可能である、上記（３１）に記載のコンピュータ・プログラム製品。
（３３）前記方法がさらに、前記フラグのすべてがセットされている場合に、前記所定の優先順位に応答して、バス・アクセスに関してバス・デバイスを選択するステップを含む、上記（２９）に記載のコンピュータ・プログラム製品。
（３４）前記方法がさらに、
バス・アクセスを要求する前記複数のバス・デバイスの各デバイスに対応するフラグのすべてがセットされるまで、ステップ（ａ）を繰り返すステップ
を含む、上記（２９）に記載のコンピュータ・プログラム製品。
（３５）前記フェアネス・サイクルが、前記バスがアイドルである時の少なくとも１つのバス要求に応答して開始され、各要求元バス・デバイスが前記バス上で成功裡に転送を完了した時に終了する、上記（２９）に記載のコンピュータ・プログラム製品。
【図面の簡単な説明】
【図１】本発明の好ましい実施形態を使用することができる、ＰＣＩローカル・バス・アーキテクチャを有する通常のコンピュータ・システムのブロック図である。
【図２】本発明の好ましい実施形態を使用することができる、ＰＣＩホスト・ブリッジとＰＣＩ対ＰＣＩブリッジの下の別々のＰＣＩローカル・バスを示す、分離されたコンピュータ構成の詳細ブロック図である。
【図３】本発明の好ましい実施形態を使用することができる、ＰＣＩ対ＰＣＩブリッジの機能ブロック図である。
【図４】本発明の例示的実施形態でのアービトレーション方式の論理を示す流れ図である。
【図５】本発明の例示的実施形態でのアービトレーション方式の論理を示す流れ図である。
【符号の説明】
１１１  ＰＣＩホスト・ブリッジ
１１８  ＰＣＩ対ＰＣＩブリッジ
１２０  ＰＣＩローカル・バス
１２８  システム・バス
１３０  ＰＣＩローカル・バス
３０２  プライマリ側
３０４  セカンダリ側
３０６  データ・バッファ
３０８  データ・バッファ
３１０  シーケンス制御ユニット
３１２  セカンダリ・バス・アービタ
３１４  フェアネス・レジスタ
３１６  要求信号線
３１７  要求信号線
３１８  要求信号線
３１９  要求信号線
【図１】
0004010476.tif 000007
【図２】
0004010476.tif 000008
【図３】
0004010476.tif 000009
【図４】
0004010476.tif 000010
【図５】
0004010476.tif 000011