(57)【特許請求の範囲】
【請求項１】
それぞれがバス・アービタを備えている複数のサブシステムに結合されたシステム・バスへのアクセスのアービトレーションを行う方法において、
どのサブシステムが前記システム・バスの現行バス・マスタであるかを指示する第１の値と、どのサブシステムが最終ポート・ドライバであるかを指示する第２の値とを各サブシステムの前記バス・マスタ中に記憶するステップであって、前記最終ポート・ドライバは前記システム・バスの最終バス・マスタである、ステップと、
すべての前記バス・アービタは独立に同じ第１と第２の値を記憶する、ステップと、
各サブシステムにおいて、関連の前記サブシステムが前記システム・バスの使用を要求するときはいつでも前記システム・バスに対してバス要求をアサートするステップであって、各アサート・バス要求はすべての前記サブシステムの前記バス・アービタへ送られる、ステップと、
各バス・アービタ内において、現行バス・マスタが在ることを前記第１の記憶値が指示するときに、前記現行バス・マスタが前記システム・バスの制御を放棄するまで、いかなる前記サブシステムのいかなるアサート・バス要求も無視する、ステップと、
現行バス・マスタが在るときはいつでも、前記現行バス・マスタを含む前記サブシステムにおいて前記現行バス・マスタ・サブシステムが前記システム・バスの継続した使用を要求し、前記システム・バスの継続使用を可能にするための予め定めた基準が満たされるときに、割り込みなしで前記現行バス・マスタ・サブシステムによって前記システム・バスを継続駆動する、ステップと、
各バス・アービタ内において、現行バス・マスタがないときはいつでも、次のバス・マスタを決めるために、いかなるアサート・バス要求も検出し処理するステップであって、
第１システム・クロック・サイクル間に未処理の前記複数のサブシステムのいずれからもアサート・バス要求がないことを判断し、第１バス・サイクル間に、前記第２の値によって前記最終ポート・ドライバであると指示された前記サブシステムによるバス要求が検出されるときは、いかなる他のサブシステムによるいかなるバス要求にも関係なく前記現行バス・マスタが前記最終ポート・ドライバであることを指示するように前記第１の値をセットし、そして、第２システム・クロック・サイクル間に前記システム・バスを前記最終ポート・ドライバ・サブシステムが駆動することを可能にし、そして
前記第１のバス・サイクル間に、前記第２の値によって前記最終ポート・ドライバであると指示された前記サブシステムによるバス要求が検出されないで、他のサブシステムによる少なくとも１つのバス要求が検出されるときに、第２システム・クロック・サイクル間にバス・アービトレーションを実行して次のバス・マスタを選択し、前記選択された次のバス・マスタを指示するように前記第１と第２の値をセットして、そして、第３システム・クロック・サイクル間に前記選択された次のバス・マスタが前記システム・バスを駆動することを可能にする、ステップと、
を含む方法。
【請求項２】
請求項１に記載の方法において、
どのサブシステムが最終ポート・ドライバであるかを指示する前記第２の記憶値に一致したシステムの使用のための優先順位をサブシステムの各々に動的に割り当てるステップであって、前記最終ポート・ドライバ・サブシステムがシステム・バスの使用のための最も高い優先順位を割り当てられる、ステップ、
を更に含む方法。
【請求項３】
それぞれがバス・アービタを備えている複数のサブシステムに結合されたシステム・バスへのアクセスのアービトレーションを行う方法において、
サブシステムの第１の優先順位をシステム・バスの使用の永久割当の最高優先順位を有する前記サブシステムの特殊ポート・ドライバ・サブシステムであるように割り当てるステップと、
どのサブシステムが前記システム・バスの現行バス・マスタであるかを指示する第１の値と、どのサブシステムが最終ポート・ドライバであるかを指示する第２の値とを各サブシステムの前記バス・マスタ中に記憶するステップであって、前記最終ポート・ドライバは前記特殊ポート・ドライバ・サブシステム以外の前記システム・バスの最終バス・マスタである、ステップと、
すべての前記バス・アービタは独立に同一の第１と第２の値を記憶する、ステップと、
各サブシステムにおいて、関連の前記サブシステムが前記システム・バスの使用を要求するときはいつでも前記システム・バスに対してバス要求をアサートするステップであって、各アサート・バス要求はすべての前記サブシステムの前記バス・アービタへ送られる、ステップと、
各バス・アービタ内において、現行バス・マスタが在ることを前記第１の記憶値が指示するときに、前記現行バス・マスタが前記システム・バスの制御を放棄するまで、いかなる前記サブシステムのいかなるアサート・バス要求も無視する、ステップと、
現行バス・マスタが在るときはいつでも、前記現行バス・マスタを含む前記サブシステムにおいて前記現行バス・マスタ・サブシステムが前記システム・バスの継続した使用を要求し、前記システム・バスの継続使用を可能にするための予め定めた基準が満たされるときに、割り込みなしで前記現行バス・マスタ・サブシステムによって前記システム・バスを継続駆動する、ステップと、
各バス・アービタ内において、現行バス・マスタがないときはいつでも、次のバス・マスタを決めるために、いかなるアサート・バス要求も検出し処理するステップであって、
第１システム・クロック・サイクル間に未処理の前記複数のサブシステムのいずれからもアサート・バス要求がないことを判断し、
前記第１バス・サイクル間に、前記第２の値によって前記最終ポート・ドライバであると指示された前記サブシステムによるバス要求が検出されそして前記特殊ポート・ドライバ・サブシステムによるバス要求がないときは、いかなる他のサブシステムによるいかなるバス要求にも関係なく前記現行バス・マスタが前記最終ポート・ドライバであることを指示するように前記第１の値をセットし、そして、第２システム・クロック・サイクル間に前記システム・バスを前記最終ポート・ドライバ・サブシステムが駆動することを可能にし、そして
前記第１のバス・サイクル間に、前記第２の値によって前記最終ポート・ドライバであると指示された前記サブシステムによるバス要求が検出されないで、他のサブシステムによる少なくとも１つのバス要求が検出されるときに、第２システム・クロック・サイクル間にバス・アービトレーションを実行して次のバス・マスタを選択し、前記選択された次のバス・マスタを指示するように前記第１と第２の値をセットして、そして、第３システム・クロック・サイクル間に前記選択された次のバス・マスタが前記システム・バスを駆動することを可能にする、ステップと、
を含む方法。
【請求項４】
請求項３に記載の方法において、
どのサブシステムが最終ポート・ドライバであるかを指示する前記第２の記憶値に一致したシステムの使用のための優先順位をサブシステムの各々に動的に割り当てるステップであって、前記特殊ポート・ドライバ・サブシステムがシステム・バスの使用のための最高優先順位をいつも割り当てられ、そして前記最終ポート・ドライバ・サブシステムがシステム・バスの使用のための２番目に高い優先順位を割り当てられる、ステップ、
を更に含む方法。
【請求項５】
請求項３に記載の方法において、
前記現在のバス・マスタが前記特殊ポート・ドライバ・サブシステムでなく、且つ前記特殊ポート・ドライバ・サブシステムが前記システム・バスの使用要求をアサートしていない、ときはいつでも、前記現在のバス・マスタのバス・アービタが前記特殊ポート・ドライバの要求を検出した後の予め定めた時間に前記現在のバス・マスタが前記システムの制御を放棄する、と言う基準を、前記システム・バスの継続使用を可能にするための予め定めた基準が含む、
方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンピュータ・システム・アーキテクチャの分野に関する。詳細にいえば、本発明はシステム・バス・アービトレーション・プロトコルに関する。
【０００２】
【従来の技術】
たとえば、マルチプロセッサ・システムのような多数のサブシステムを備えた効率のよいシステム・アーキテクチャの設計にあたり、サブシステムが共用する一般的なシステム・バスを使用することは、いくつかの重要な設計の目標を満たすのに有用である。これらの目標にはサブシステム間の相互接続の総数およびコストの最小化、サブシステムのインタフェースにおけるモジュール性の維持、アドオン・サブシステム、たとえば、拡張メモリおよび周辺機器に対するインタフェースの統合の単純化などがある。しかしながら、システム・バスを共用すると、バス・アービトレーション・プロトコルを使用して、サブシステムによる必然的なバス競合を解決することが必要となる。
【０００３】
バス競合を解決する従来のバス・アービトレーション・プロトコルは、２つの一般的なクラス、すなわち、集中アービトレーション・プロトコルと分散アービトレーション・プロトコルに分けられる。図１Ａに示すような、例示的な従来の集中アービトレーション・システム１１０において、システム１１０はプロセッサ１１１、１１２、１１３、１１４、システム・バス１１８および集中アービタ１１９を含んでいる。システム・バス１１８、たとえば、Ａｄｄｒｅｓｓ＿ｂｕｓはプロセッサ１１１、１１２、１１３、１１４および集中アービタ１１９に結合されている。さらに、プロセッサ１１１、１１２、１１３、１１４の各々は、バス要求ラインＲｅｑ＿０、Ｒｅｑ＿１、Ｒｅｑ＿２、Ｒｅｑ＿３の１つおよびバス・グラント・ラインＢｕｓ＿Ｇｒａｎｔ＿０、Ｂｕｓ＿Ｇｒａｎｔ＿１、Ｂｕｓ＿Ｇｒａｎｔ＿２、Ｂｕｓ＿Ｇｒａｎｔ＿３の１つにそれぞれ結合されている。
【０００４】
集中アービタ１１９は唯一のバス・アービタであり、すべてのバス競合のアービトレーションを担う。プロセッサ１１１、１１２、１１３、１１４の１つがシステム・バス１１８を駆動することを必要とする場合、適切なバス要求ラインを介して集中アービタ１１９に要求を行う。他のプロセッサがシステム・バス１１８を使用していない場合、集中アービタ１１９はバス１１８を要求元プロセッサに割り当てる。逆に、２つ以上のプロセッサが所定の期間内にバス要求を行った場合、集中アービタ１１９は適切な割振り手法、たとえば、ラウンド・ロビン手法や所定の優先順位手法を使用して、どのプロセッサに次のバス・マスタを割り当てるかを決定する。いずれの場合にも、集中アービタ１１９はバス・グラントを適切なバス・グラント・ラインによって割り当てられたプロセッサに伝える。たとえば、プロセッサ１１１はバス要求ラインＲｅｑ＿０によってアービタ１１９に対して要求を行い、最終的に、バス・グラント・ラインＢｕｓ＿Ｇｒａｎｔ＿０によってアービタ１１９からグラントを受け取る。
【０００５】
図１Ｂは従来の分散アービトレーション・システム１２０を示しており、これはプロセッサ１２１、１２２、１２３、１２４およびシステム・バス１２８を含んでいる。システム・バス１２８、たとえばＡｄｄｒｅｓｓ＿ｂｕｓはプロセッサ１２１、１２２、１２３、１２４に結合されている。さらに、プロセッサ１２１、１２２、１２３、１２４はバス要求ラインＲｅｑ＿０、Ｒｅｑ＿１、Ｒｅｑ＿２、Ｒｅｑ＿３により、またバス制御ラインＢｕｓ＿Ｂｕｓｙ＿０、Ｂｕｓ＿Ｂｕｓｙ＿１、Ｂｕｓ＿Ｂｕｓｙ＿２、Ｂｕｓ＿Ｂｕｓｙ＿３によって互いに結合されている。
【０００６】
分散アービトレーション・プロトコルはすべてのプロセッサ１２１、１２２、１２３、１２４がバス競合の同時アービトレーションおよび同一のプロセッサが次のバス・マスタとなるように割り当てることを担うようにする。たとえば、プロセッサ１２１、１２２、１２３、１２４の１つがシステム・バス１２８を駆動することを必要とする場合、要求はバス１２８に結合されているその他のすべてのプロセッサに該当する適切なバス要求ラインによって同報通知する。他のプロセッサがシステム・バス１２８を競合していない場合、すべての他のプロセッサは独立してバス１２８を要求元プロセッサに割り当てる。逆に、２つ以上のプロセッサが所定の期間内にバス要求を行った場合、プロセッサ１２１、１２２、１２３、１２４の各々は適切な同一の割振り手法を使用して、どのプロセッサが次のバス・マスタになるべきかに関して独立して同一の結論に達する。いずれの場合でも、次のバス・マスタに割り当てられたプロセッサは、適切なバス・ビジィ・ラインをアサートすることによってシステム・バス１２８を取得し、これによって他のすべてのプロセッサにシステム・バス１２８が現在使用中である旨を通知する。たとえば、プロセッサ１２１はバス要求をバス要求ラインＲｅｑ＿０に同報通知する。システム・バス１２８が自由であり、他のバス要求ラインＲｅｑ＿１、Ｒｅｑ＿２およびＲｅｑ＿３がいずれも優先順位の高いプロセッサによってアサートされていない場合には、プロセッサ１２１はバス制御ラインＢｕｓ＿Ｂｕｓｙ＿０をアサートすることによってシステム・バス１２８を取得する。Ｉ．Ｅ．Ｅ．Ｅ．規格８９６．２−１９９１に基づく「Ｆｕｔｕｒｅｂｕｓ＋」は分散アービトレーション方式のこのような一例である。
【０００７】
上述のプロトコルなどのほとんどの従来のバス・アービトレーション・プロトコルにおいて、バス・アービトレーションから生じる全体的な遅延を最小限とするためには、バス要求の送信および受信、ならびに次のバス・マスタを割り当てるという順次タスクは、同一のシステム・クロック・サイクルで完了する。バス要求の処理および対応するバス・ドライバ割当てを１システム・クロック・サイクルで完了することを試みるのが有利であるが、システム・クロック速度は、より高速なプロセッサ・クロックを備えているプロセッサに応じて増加するので、バス要求を受け取り、単一の高速システム・クロック・サイクル内でアービトレーション処理を完了する能力はもはや達成できなくなる。それ故、これらの従来のバス・アービトレーション・プロトコルはより高速なプロセッサに対してスケーラブル（scalable）ではなくなる。システム設計者はバス競合を解決するためにシステム・クロック速度を遅くするか、あるいは複数のシステム・クロック・サイクルを使用するかのいずれかに集中している。その結果、遅いシステム・クロック・サイクルあるいはバス競合のアービトレーションのためだけに挿入される特別なシステム・クロック待ち時間のいずれかによって、パフォーマンスが抑制される。
【０００８】
【発明が解決しようとする課題】
それ故、プロセッサのクロック速度が速くなった場合に、効率がよく、費用効果が高く、モジュール性があり、スケーラブルなアービトレーションの解決策が必要である。
【０００９】
【課題を解決するための手段】
本発明は、共通システム・バスに結合されたサブシステム、たとえばプロセッサの間のバス競合を効率よく解決するスケーラブルで、モジュール性があるパイプライン分散バス・アービトレーション・システムを提供する。アービトレーション・システムは複数の分散バス・アービタを含んでおり、これらはサブシステムからのバス要求を受け取り、次のバス・マスタを独立して決定する。
【００１０】
本発明の実施の態様の１つによれば、３つの原理がシステム・バスによる転送に関連したシステム・クロックの待ち時間を最小とする。まず、アービトレーション・クロック・サイクル中のサブシステム間の変化はアービトレーション・クロック・サイクルの直前のクロック・サイクル中に活動状態のシステム・バス要求に基づいており、アービトレーション・クロック・サイクル中にアサートされるシステム・バス要求と無関係である。第２に、アービトレーション・プロトコルは、システム・バスを優先的に駆動する現行のバス・マスタを処理する。第３に、システム・バス上の出力バス信号、たとえば、バス要求および駆動許可信号は介入アービトレーション論理を何ら必要とすることなく、サブシステムの出力レジスタによって直接生成される。同様に、入力バス信号を受け取るための、システム・バスとサブシステムの入力レジスタの間に結合されたアービトレーション論理は存在しない。すなわち、入力レジスタはシステム・バスに直接結合される。
【００１１】
これらの原理によって、アービトレーション・プロセスをクリティカル・タイミング・パスから排除することが可能となり、これによってシステムが所与の集積回路（ＩＣ）技術で可能な最大システム周波数で作動することが可能となり、これによってシステム・クロック待ち時間全体が少なくなる。さらに、各アービトレーション・タスクはプロセッサの速度にかかわりなくシステム・クロック・サイクル内で完了する。その結果、現行のバス・マスタを維持するアービトレーション待ち時間は１システム・クロック・サイクルであり、バス・マスタを選択し、切り換える待ち時間は２システム・クロック・サイクルである。
【００１２】
アービトレーション・プロトコルによって、「リアルパーキング」モードも可能となり、これはシステム・バスで競合する可能性のあるバス・マスタが２つだけの単純なシステムでのアービトレーション待ち時間をさらに短縮する。単純なシステムの場合、現行のバス・マスタを維持するアービトレーション待ち時間をゼロ・システム・クロック・サイクルまで減らすことができるが、現行のバス・マスタを切り換える待ち時間は４システム・クロック・サイクルまで増加する。
【００１３】
この実施の態様においては、修正ラウンドロビン・プロトコルを使用して、システム・バスに対して競合するサブシステムのアクセスに優先順位をつける。各サブシステムはシステム・バス上のポート、すなわちロケーションを占め、一意の識別番号（ＩＤ）を割り当てられる。あらゆるポートはどのポートが最終ポート・ドライバであるかを追跡し、最終ポート・ドライバの識別に基づいてどのポートを次のバス・マスタに割り当てるか、すなわち選択するかを同時に（並行して）決定する。したがって、あるポートがアービトレーションに勝ち、現行バス・マスタになると、あらゆるポートごとに格納されている最終ポート・ドライバのアイデンティティが新しい現行バス・マスタのＩＤによって更新される。効率の点で、最終ポート・ドライバを優先順位割当て中に優先的に処理する。まず、システムのリセット時に、アービトレーション・システムは、あらゆるサブシステムによって最終ポート・ドライバと事前定義されたポートを選択することによって同期化される。
【００１４】
実施の形態の中には、アービトレーション・プロトコルによって、事前割り当てされた特別なポートを優先的に処理可能なものもある。すなわち、特殊ポートがラウンドロビン方式に関与する必要がない。その代わり、特殊ポートにはそのバス要求がアサートされたときにもっとも高い優先順位が与えられる。特殊ポート・プロトコルは高水準システム・アーキテクチャの設計に独特の融通性を提供して有利である。それ故、特殊ポートがアービトレーションに勝った場合、システムに結合されているすべてのポートによって維持されている最終ポート・ドライバのアイデンティティは、特殊ポートがラウンドロビン・プロトコルに関与しないため、更新されない。
【００１５】
この実施態様において、最終ポート・ドライバはクロック・サイクル内でバス要求をアサートすることが認められている唯一のサブシステムであり、すぐ次のクロック・サイクルでシステム・バスを直ちに駆動する。システム・バスの駆動時に、第１のサブシステムが現行バス・マスタになる。その後、現行バス・マスタはそのバス要求ラインを保持することだけによって、システム・クロックの待ち時間なしに複数のパケットを連続して伝送することを許可される。システム・バスのデッドロックの可能性を解消するために、現行バス・マスタはそのバスを放棄する前にゼロないし複数のトランザクション・パケットを駆動するが、現行バス・マスタは、有限数のクロック・サイクル内にバスを放棄しなければならない。さらに、現行ドライバにペンディングとなっているバス要求がもはやない場合、現行バス・マスタはそのバス要求ラインを放棄しなければならない。
【００１６】
逆に、最終ポート・ドライバではない第２のサブシステムが不活動なシステム・バスを駆動する必要がある場合、第２のサブシステムは第１のクロック・サイクルでそのバス要求ラインをアサートする。すべてのそれぞれのバス・アービタ内のアービトレーションが次のクロック・サイクル、すなわち第２のクロック・サイクルで生じる。他のサブシステムがいずれも第２のサブシステムよりも高い優先順位を有していないものと想定すると、第２のサブシステムに次のバス・マスタを割り当てることができ、このサブシステムが第３のシステム・クロック・サイクルでバスを駆動することが可能とされる。それ故、要求元サブシステムが最終ポート・ドライバでなく、システム・バスが不活動状態である場合、２つの遅延システム・クロック・サイクルが必要となる。
【００１７】
パイプライン・バス・アービトレーション・システムの利点としては、システム・クロック速度、たとえば、プロセッサ・クロック速度が上がったときにアービトレーションをスケーリングする、クリティカル・パスからアービトレーション論理を排除することによって達成される機能がある。スケーラビリティが有利なのは、ほとんどのディジタル・コンピュータが同期システム・クロックに基づいており、したがって、パフォーマンスを最適化するのに高いクロック速度が重要だからである。それ故、アービトレーション待ち時間を長くせずにアービトレーション・システムをスケーリングできることによって、システム・クロック・サイクルを最短化するとともに、最短のアービトレーション待ち時間を維持することが可能となる。システムのモジュラリティはシステム・バスを拡張し、サブシステムの数を増やすことを容易とする。他の利点としては、最終ポート・ドライバが現行バス・マスタになるまでの待ち時間が最短であることがあり、これはポートを占有するサブシステムがシステム・バスにおいてバースト・トラフィックを生成するプロセッサなどのシステムにおいて特に重要である。
【００１８】
本発明のシステムの目的、特徴および利点は以下の説明から明らかとなろう。
【００１９】
【発明の実施の形態】
表記および用語
システム・コントローラ（ＳＣ）：キャッシュ一貫性、データ・フロー、フロー制御、およびメモリ作動を調整するためにシステム・バスに結合されている中央コントローラ。
システム・バス・マスタ：システム・バスでデータ／アドレス転送を開始できるサブシステム。
次のバス・マスタ：次のシステム・クロック・サイクルでシステム・バスを駆動することを認められているサブシステム。
現行バス・マスタ：システム・バスを駆動することを現在認められているサブシステム。
最終ポート・ドライバ：システム・バスを駆動することを最後に認められていたサブシステム。
ポート：一意のポート識別子を有する、システム・バス上のサブシステムが占有しているロケーションまたは位置。
【００２０】
以下の説明において、さまざまな詳細によって本発明を完全に理解させる。これらの詳細は効率的なパイプライン分散バス・アービトレーション・システムを実施する際にシステム設計者を援助する機能ブロックおよび例示的な所定のアービトレーション優先順位方式を含んでいる。バス・アービトレーション・システムを特定のインプリメンテーションによって説明するが、本発明は広範囲にわたるシステム・アーキテクチャおよび環境に適用できるものである。他の場合においては、本発明を不必要に不明確としないため、周知の回路、構造およびプログラム・コードを詳細には説明しない。Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，  Ｉｎｃ．に譲渡された「Ｐａｃｋｅｔ  Ｓｗｉｔｃｈｅｄ  Ｃａｃｈｅ  Ｃｏｈｅｒｅｎｔ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ  Ｓｙｓｔｅｍ」という名称の米国特許第５６３４０６８号には、本発明によるパイプライン分散バス・アービトレーション・プロトコルに関する詳細な仕様が記載されている。
【００２１】
実施の形態の１つにおいて、図２のブロック図に示されているように、システム２００は複数のサブシステム、たとえばプロセッサ２１０、２２０、２３０、２４０、システム・バス２８０およびシステム・コントローラ２９０を含んでいる。各サブシステムはバス・トランシーバ、バス・リクエスタ、およびバス・アービタを含んでいる。たとえば、プロセッサ２１０はバス・トランシーバ２１２、バス・リクエスタ２１４およびバス・アービタ２１６を含んでいる。同様に、システム・コントローラ２９０はバス・トランシーバ２９２、バス・リクエスタ２９４およびバス・アービタ２９６を含んでいる。包括的にいうと、バス・アービタ２１６、２２６、．．．２９６が本発明の分散アービトレーション・システムを形成している。
【００２２】
この実施形態において、システム・バス２８０はアドレス・バスであり、これによってアドレス・バスがビジーである際に、データを個別のデータ・バス（図示せず）で同時に転送することを可能とする。これにかかわりなく、本発明はシステム・バス２８０が専用データ・バスまたは組合せアドレス／データ・バスである他のシステムにも同様に適用できる。さらに、記載されているサブシステムはすべてバス・マスタであるが、アービトレーション・プロトコルは、サブシステムがバス・マスタとバス・スレーブの両方を含んでいるシステムにも適用できる。それ故、システム２００のこの実施の形態の場合、現行バス・マスタは現行バス・マスタでもある。
【００２３】
システム・バス２８０はプロセッサ２１０、２２０、２３０、２４０のそれぞれのバス・トランシーバ２１２、２２２、２３２、２４２を、システム・コントローラ２９０のバス・トランシーバ２９２に相互接続している。プロセッサ２１０、２２０、２３０および２４０はそのそれぞれのバス修飾子ラインＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿０、ＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿１、ＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿２、およびＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿３によってシステム・コントローラ２９０にも結合されている。
【００２４】
プロセッサ２１０、２２０、２３０、２４０のバス・リクエスタ２１４、２２４、２３４、２４４、２９４およびバス・アービタ２１６、２２６、２３６、２４６、２９６、ならびにシステム・コントローラ２９０はそれぞれ以下のアービトレーション制御ラインを介して互いに結合されている。システム・アービトレーション・リセット・ラインＡｒｂ＿Ｒｅｓｅｔはシステム・コントローラ２９０をすべてのプロセッサ２１０、２２０、２３０、２４０に結合している。バス・リクエスタ２１４のＲｅｑ＿ｏｕｔ＿０ラインはシステム・コントローラのバス・アービタ２９６のＲｅｑ＿０ライン、およびバス・アービタ２２６、２３６、２４６それぞれのＲｅｑ＿ｉｎ＿２、Ｒｅｑ＿ｉｎ＿１、Ｒｅｑ＿ｉｎ＿０ラインに結合されており、またバス・リクエスタ２２４のＲｅｑ＿ｏｕｔ＿１ラインは、バス・アービタ２９６、２１６、２３６、２４６それぞれのＲｅｑ＿１、Ｒｅｑ＿ｉｎ＿０、Ｒｅｑ＿ｉｎ＿２、Ｒｅｑ＿ｉｎ＿１ラインに結合されている。同様に、バス・リクエスタ２３４のＲｅｑ＿ｏｕｔ＿２ラインはバス・アービタ２９６、２１６、２２６、２４６それぞれのＲｅｑ＿２、Ｒｅｑ＿ｉｎ＿１、Ｒｅｑ＿ｉｎ＿０、Ｒｅｑ＿ｉｎ＿２ラインに結合されており、バス・リクエスタ２４４のＲｅｑ＿ｏｕｔ＿３ラインはバス・アービタ２２６、２３６、２４６それぞれのＲｅｑ＿３、Ｒｅｑ＿ｉｎ＿２、Ｒｅｑ＿ｉｎ＿１、Ｒｅｑ＿ｉｎ＿０ラインに結合されている。最後に、システム・コントローラのバス・リクエスタ２９４のＳＣ＿Ｒｅｑラインはコントローラ２９０をプロセッサ２１０、２２０、２３０、２４０それぞれのバス・アービタ２１６、２２６、２３６、２４６に結合している。
【００２５】
明らかに直感に反しているが、パイプライン分散バス・アービトレーション・システムに使用されている基礎技法の１つは、アービトレーション・シーケンスを個別のクロック・サイクルで処理するため個別のタスクに分割することである。たとえば、未解決なバス要求の検知および次のバス・マスタの割当ては個別のクロック・サイクルで完了する。他の技法は現行バス・マスタの切換え頻度を最小限とすることである。さらに他の技法は現行バス・マスタの切換えが必要となったときのクロック・サイクル喪失の総数を最小限とすることである。これらの技法を適用することによって、各アービトレーション・タスクは、プロセッサのクロック速度およびアービトレーション・タスクをクリティカル・パスから排除できるかどうかにかかわりなくシステム・クロック・サイクル内で完了し、これによってバス・アービトレーションによるシステム・クロック・サイクル待ち時間が短くなる。
【００２６】
結果として、以下の最短のアービトレーション待ち時間がこの実施形態で可能となる。現行バス・マスタはシステム・クロック待ち時間なしに、データ・パケットを連続的に伝送することができる。最終ポート・ドライバは連続したシステム・クロックで、すなわち１システム・クロック待ち時間でシステム・バスを要求し、駆動することができる。プロセッサが最終ポート・ドライバでない場合、最小２システム・クロック待ち時間がある。最後に、異なる現行バス・マスタに変えるのに、最小３システム・クロック・サイクルが必要である。これらの最短のシステム・クロック待ち時間は次の規則によって達成される。
【００２７】
図３Ａはプロセッサ２１０、２２０、２３０、２４０それぞれのバス・アービタ２１６、２２６、２３６、２４６に対する例示的な修正ラウンドロビン優先順位方式を示す表である。アービトレーション・システムが優先順位方式を使用して、システム・バス２８０に対して競合するサブシステムのうちから次のバス・マスタを選択する。各プロセッサはシステム・バス２８０上のポート（ロケーション）を占有し、一意の識別番号（ＩＤ）が割り当てられる。システム同期のため、ポート・アドレス０のプロセッサ２１０が選択されて、リセット時に最終ポート・ドライバになる。その後、あらゆるポートはどのポートが最終ポート・ドライバなのかを追跡し、同時に（並行して）最終ポート・ドライバのアイデンティティに基づいてどのポートに次のバス・マスタを割り当てるべきか、すなわち次のバス・マスタになるように選択すべきかを決定する。したがって、あるポートがアービトレーションに勝って、現行バス・マスタになった場合、あらゆるプロセッサによって格納されている最終ポート・ドライバのアイデンティティは、新しい現行バス・マスタのＩＤによって更新される。効率の点で、最終ポート・ドライバを優先的に処理する。
【００２８】
図３Ｂおよび図４ないし図９は、アドレス転送を完了するのに２つのバス・クロック・サイクルが必要とされるように、アドレスバスの幅が選ばれているマルチプロセッサ・システム２００を説明する例示的なタイミング図を示している。それ故、以下の例示的な説明において、各データ転送量子（アドレス情報パケット・サイズ）は完了するのに２つのシステムクロック・サイクルを必要とするが、２サイクルのデータおよび／またはアドレス・バスの表記は本発明の基本となるものではない。たとえば、プロセッサ２１０は１システム・サイクル中に、アドレス情報の第１のサイクルをシステム・バス２８０上へ駆動し、第２のシステム・クロック・サイクル中にアドレス情報の第２のサイクルを駆動する。
【００２９】
当分野の技術者に周知のように、実施形態に応じて、データおよび／またはアドレス・パケットは１つまたは複数のシステム・クロック・サイクルでシステム・バスを介して転送される。他のシステム・バス幅が可能である。たとえば、他の実施の形態において、アドレス・バス幅はシステム・アドレス・スペースの幅と等しい。さらに他の実施の形態において、アドレス・バス幅はシステム・アドレス・スペースの幅の１／４である。さらに、プロセッサ２１０、２２０、２３０、２４０が類似したものであり、それ故、１つのサブシステム、たとえば、プロセッサ２１０または２２０の説明が他のサブシステム、すなわち、プロセッサ２２０、２３０、２４０に適用できることに留意されたい。
【００３０】
図３Ｂはバス・アービトレーション要求をシステム・リセット信号ＵＰＡ＿Ｒｅｓｅｔ＿１の後１クロック・サイクルでアサートできるリセット・タイミング・シーケンスを示す。プロセッサ２１０、２２０、２３０、２４０の各々はそれぞれ一意のポート・アドレス０、１、２、３を有している。Ａｒｂ＿ＲｅｓｅｔラインのＡｒｂ＿Ｒｅｓｅｔ信号はシステム・コントローラ２９０に、各サブシステムのあらゆる状態機械をリセットせずに、１つまたは複数のサブシステムの状態機械を選択的にリセットする機構をもたらす。たとえば、システム・コントローラ２９０からのＡｒｂ＿Ｒｅｓｅｔ信号によって、プロセッサ２１０、２２０、２３０、２４０がバス・アービタ２１６、２２６、２３６、２４６のそれぞれのアービトレーション状態マシンに同期することを可能とする。
【００３１】
図４は現行バス・マスタへの最終ポート・ドライバの変化を説明するタイミング図である。第１のクロック・サイクル前のクロック・サイクルで未解決なバス要求がないとバス・アービタ２１６、２２６、．．．２９６が判断したものと想定すると、最終ポート・ドライバが第１のクロック・サイクル中にバス要求をアサートすることが認められている唯一のサブシステムであり、第２のクロック・サイクル中にシステム・バス２８０を直ちに駆動する。たとえば、プロセッサ２１０が最終ポート・ドライバである場合、プロセッサ２１０はすでにもっとも高い優先順位を有しており、第１のクロック・サイクル中に他のプロセッサ２２０、２３０、２４０のバス要求ラインをポーリングすることを必要とせずに、次のバス・マスタを割り当てる、すなわち次のバス・マスタになるように選択することができる。したがって、バス・トランシーバ２１２は第１のシステム・クロック・サイクル中にそのバス要求ラインＲｅｑ＿ｏｕｔ＿０をアサートし、直後のクロック・サイクル、すなわち第２のシステム・クロック・サイクル中にシステム・バス２８０を駆動することを許可される。この実施形態において、プロセッサ２１０は第２のシステム・クロック・サイクル中にアドレスの第１の半部をアドレス・バス２８０へ駆動し、第３のシステム・クロック・サイクルでアドレスの第２の半部をアドレス・バス２８０に駆動する。
【００３２】
第２のシステム・クロック・サイクルでバス２８０を駆動した際に、プロセッサ２１０には現行バス・マスタの状態が割り当てられる。現行バス・マスタは、現在アドレス・バス２８０を駆動しており、またそのトランシーバのＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿ｘ修飾子ライン、たとえばトランシーバ２１２のＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿０をアサートしているサブシステムと定義される。現行バス・マスタになると、プロセッサ２１０はこのラインのアサートを継続するだけで、すなわち、バス・リクエスタ２１４のバス要求ラインＲｅｑ＿ｏｕｔ＿０を維持するだけで、システム・クロック待ち時間なしで、複数のデータ・パケットを連続して伝送できる。現行バス・マスタ、すなわちプロセッサ２１０は他のプロセッサ２２０、２３０、２４０またはシステム・コントローラ２９０からのバス要求が存在する際に、システム・バス２９０を放棄する前に任意の数のトランザクション・パケット（パケットが存在しない場合を含む）を駆動して、デッドロックの可能性を解消できるが、適正に挙動する現行バス・ドライバは有限数のクロック・サイクル以内にバス２８０を解放しなければならない。さらに、現行バス・マスタは現行バス・マスタに保留されている要求がない場合に、そのバス要求ラインを解放しなければならない。
【００３３】
図５に示すように、サブシステム、たとえばプロセッサ２１０が最終ポート・ドライバかつ現行バス・マスタの両方である場合、最終ポート・ドライバではないサブシステム、たとえばプロセッサ２２０がリクエスタ２２４のバス要求ラインＲｅｑ＿ｏｕｔ＿１をアサートすると、プロセッサ２２０のトランシーバ２２２がシステム・バス２８０を駆動できるようになるまでに、少なくとも３システム・クロック・サイクルの待ち時間が存在する。システム・バス２８０を駆動している現行バス・マスタを変えるのに、最小３つのシステム・クロックが必要とされるのには２つの理由がある。第１に、リクエスタ２２４が第１のシステム・クロック・サイクルまでにバス要求ラインＲｅｑ＿ｏｕｔ＿１をアサートしていても、プロセッサ２１０のアドレス情報の最後のデータ・パケットの伝送を完了するのに２つのシステム・クロックが必要である。第２に、アービトレーション・プロトコルは第３のクロック・サイクルでデッド・サイクルを強制する。
【００３４】
それ故、プロセッサ２２０よりも高い優先順位を持つ他のプロセッサがシステム・バス２８０に対して競合していないと想定すると、プロセッサ２２０に次のバス・マスタを割り当てることができ、かつプロセッサ２２０は第４のシステム・クロック・サイクルでシステム・バス２８０を駆動するようになる。したがって、活動現行バス・マスタを交換するには３つのクロック・サイクルが必要である。
【００３５】
上述のように、アービトレーション・プロトコルは現行バス・マスタの交換の間にシステム・バス２８０にアイドル・サイクルまたはデッド・サイクルをもたらす。デッド・サイクルは２つのバス・マスタ、すなわち現行バス・マスタおよび次のバス・マスタがシステム・バス２８０を同時に駆動する可能性を排除する。このような例の１つは第１のバス・マスタ、すなわちプロセッサ２１０のドライバ回路のオフ時間が第２のバス・マスタ、すなわちプロセッサ２２０のドライバ回路のオン時間よりも長い場合である。現行バス・マスタがそのバス要求ラインをアサートした場合、現行バス・マスタを切り換えるのに必要なバス・サイクルの総数もプロセッサ２１０の現行バス転送の状態、すなわちプロセッサ２１０のデータ転送の第１または第２半部中にアサートされるプロセッサ２２０からのバス要求などの要因によって決定される。
【００３６】
図６は、システム・バス２８０が不活動である、すなわち駆動されていないときに、最終ポート・ドライバとなり、かつ最終的に現行バス・マスタとなる異なるサブシステム、たとえばプロセッサ２２０を説明するタイミング図である。第１のクロック・サイクル中に、プロセッサ２１０、すなわち最終ポート・ドライバは不活動であり、システム・バス２８０を駆動していない。プロセッサ２２０のリクエスタ２２４が第２のクロック・サイクルでバス要求ラインＲｅｑ＿ｏｕｔ＿１をアサートした場合、アービトレーションが次のクロック・サイクル、すなわち第３のクロック・サイクルで生じる。プロセッサ２２０よりも優先順位の高いプロセッサがバス２８０を必要としていないと想定すると、プロセッサ２２０に次のバス・マスタを割り当て、第４のシステム・クロック・サイクルでバス２８０を駆動することを許可することができる。それ故、要求元プロセッサが最終ポート・ドライバでなく、システム・バス２８０が不活動である場合には、合計２つのシステム・クロック・サイクルがバス要求とバス２８０の所有権の間に必要となる。
【００３７】
ここで図７を参照すると、システム・コントローラ２９０がバス要求を行い、最終的に現行バス・マスタになる。プロセッサ２１０が最終ポート・ドライバであるが、不活動である際に、システム・コントローラ２９０が第２のクロック・サイクルでリクエスタ２９４の要求ラインＳＣ＿Ｒｅｑをアサートした場合、他のシステム・クロック・サイクル、すなわち第３のサイクルがアービトレーションに必要となる。その後、第４のクロック・サイクルで、システム・コントローラ２９０がアドレス・バス２８０を駆動することを許可される。それ故、２つの使用されないシステム・クロック・サイクルがあり、これは１つのサブシステムが不活動な最終ポート・ドライバである際に、他のサブシステムがバス２８０を駆動することを望んでいる場合に類似している。
【００３８】
本発明の他の実施の形態によれば、アービトレーション・プロトコルによって「リアルパーキング」モードが可能となり、これはシステム２００に可能なバス・ドライバが２つだけ、すなわち２つのバス・マスタだけの場合、たとえば、システム・バス２８０にプロセッサ２１０、２２０だけが結合されている場合に、アービトレーション待ち時間をさらに少なくする。この縮小システムの場合、現行バス・マスタを保持するためのアービトレーション待ち時間を、データ転送の完了後に現行バス・マスタのバス要求を維持するだけで、システム・クロック・サイクルをゼロまで減らすことができる。
【００３９】
ある実施形態では、システム２００のアービトレーション・プロトコルが事前割り当てされた特殊ポート、たとえば、システム・コントローラ２９０を優先的に処理することが可能となる。すなわち、ラウンドロビン方式に関与するのに、特殊ポートが必要なくなる。この例において、システム・コントローラ２９０にはそのバス要求がアサートされたときに、もっとも高い優先順位が与えられる。特殊ポートの指定はシステム２００の高水準のアーキテクチャの設計に独特な融通性をもたらすので有利である。それ故、システム・コントローラ２９０がアービトレーションに勝った場合に、システム、すなわち、プロセッサ２１０、２２０、２３０、２４０に結合されているすべてのポートによって維持されている最終ポート・ドライバ・アイデンティティが更新されないが、これはシステム・コントローラ２９０が修正ラウンドロビン・プロトコルに関与しないからである。
【００４０】
双方向バス修飾子信号ＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿０、ＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿１、ＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿２およびＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄ＿３が、特殊ポート、システム・コントローラ２９０およびプロセッサ２１０、２２０、２３０、２４０それぞれの間で交換され、システム・コントローラ２９０が現行バス・マスタが有効パケットを駆動している時期を検出できるようにする。逆に、システム・コントローラ２９０が現行バス・マスタである場合には、妥当性信号によって、スレーブ・サブシステムがシステム・コントローラ２９０からデータ・パケットを受け取る時期を知ることが可能となる。さらに、妥当性信号は各サイクル・パケット中の第１のシステム・クロックでアサートされ、第２のサイクル中にデアサートされる。活動バス・ドライバがない場合に、システム・コントローラ２９０の保持増幅器がＵＰＡ＿Ａｄｄｒ＿Ｖａｌｉｄラインの論理レベルを維持する。システム・コントローラ２９０に保持増幅器を使用する他の利点としては、システム・バス２８０のデバッグが容易となることなどがある。
【００４１】
図８は特殊ポート、たとえばシステム・コントローラ２９０からプロセッサ２１０へのデータ・パケット転送を説明するタイミング図である。システム・コントローラ２９０が要求ラインＳＣ＿Ｒｅｑをアサートするとともに、現行バス・マスタのトランシーバ、たとえば、プロセッサ２１０のトランシーバ２１２がバス２８０を駆動している場合、最終データ・パケットの継続転送を完了することが、プロセッサ２１０に認められる。システム・コントローラ２９０が特殊ポートであるから、プロセッサ２１０はリクエスタ２１４の要求ラインＲｅｑ＿ｏｕｔ＿０を解放するものと考えられる。上述したように、システム・コントローラ２９０は他のサブシステムに関して高い優先順位を常に有しており、それ故、次のバス・マスタを割り当てられる必要がない。したがって、システム・コントローラ２９０のトランシーバ２９２がシステム・バス２８０を駆動している場合、プロセッサ２１０は最終ポート・ドライバのままであることができる。システム・コントローラ２９０の観点からいうと、プロセッサ２１０による最終データ・パケットの転送の完了は２つの使用されないシステム・クロック・サイクルを招来する。システム・バスの争い、すなわち、複数のサブシステムによるシステム・バス２８０の同時駆動の試みを防止するためには、第３の使用されないクロック・サイクルが必要となる。その後、システム・コントローラ２９０は現行バス・マスタとなり、システム・バス２８０を駆動することが許可される。サブシステム２１０、２２０、２３０、２４０に関して優先順位がもっとも高い事前割当てシステム・コントローラ２９０が、実施形態上の任意選択物であることに留意されたい。本発明のアービトレーション・システムは、システム・コントローラ２９０がサブシステム２１０、２２０、２３０、２４０に関して同等またはこれらよりも低い優先順位を有している他のシステムにも適用可能である。
【００４２】
図９に示すように、システム・コントローラ２９０は最終ポート・ドライバであった不活動サブシステムからのバス要求に応じて、システム・バス２８０の所有権を放棄する。システム・コントローラ２９０が現行バス・マスタであり、不活動最終ポート・ドライバ、たとえばプロセッサ２１０からのバス要求を検出した場合、システム・コントローラ２９０は２つのシステム・クロック・サイクルで最終データ・パケットの転送を完了する。最終ポート・ドライバ、たとえばプロセッサ２１０がシステム・バス２８０の駆動を開始でき、現行バス・マスタになる前に、第３の潜在システム・クロック・サイクルが必要である。
【００４３】
本発明の精神を逸脱することなく、その他の改変および追加が可能である。たとえば、サブシステムの総数はもっと少なくても、多くてもよい。アドレス・バスはシステム・アドレス・スペースよりも広くても、狭くてもよい。さらに、サブシステムはビデオ・コントローラ、キャッシュ・コントローラ、および浮動小数点計算ユニットなどの数値演算コプロセッサを含んでいることもできる。それ故、本発明の範囲は首記の特許請求の範囲によって決定されるべきである。
【図面の簡単な説明】
【図１】  集中バス・アービトレーション・プロトコルを有する従来のシステムのブロック図である。
【図２】  本発明による分散同期バス・アービトレーション・プロトコルを使用しているシステム・バスのブロック図である。
【図３】  ４つのポートに対する最終ポート・ドライバのラウンドロビン割当てを示す表（Ａ）と、システム・リセット後のアービトレーション要求を示すタイミング図（Ｂ）である。
【図４】  現行バス・マスタに変化する最終ポート・ドライバを示すタイミング図である。
【図５】  現行バス・マスタと次のバス・マスタの間のバス・ドライバの変化を示すタイミング図である。
【図６】  最終ポート・ドライバおよび現行バス・マスタになる他のプロセッサを示すタイミング図である。
【図７】  現行バス・マスタとなる特殊ポートおよびシステム・コントローラを示すタイミング図である。
【図８】  最終ポート・ドライバへパケットを送るシステム・コントローラを示すタイミング図である。
【図９】  システム・コントローラと最終ポート・ドライバの間のバス・ドライバの変化を示すタイミング図である。
【符号の説明】
２００  システム
２１０  プロセッサ
２１２  バス・トランシーバ
２１４  バス・リクエスタ
２１６  バス・アービタ
２２０  プロセッサ
２３０  プロセッサ
２４０  プロセッサ
２８０  システム・バス
２９０  システム・コントローラ
２９２  バス・トランシーバ
２９４  バス・リクエスタ
２９６  バス・アービタ
【図１】
0003899142.tif 000002
【図２】
0003899142.tif 000003
【図３】
0003899142.tif 000004
【図４】
0003899142.tif 000005
【図５】
0003899142.tif 000006
【図６】
0003899142.tif 000007
【図７】
0003899142.tif 000008
【図８】
0003899142.tif 000009
【図９】
0003899142.tif 000010