(57)【特許請求の範囲】
【請求項１】
データ要求に応答してバス・トランザクションを行うよう外部バスに接続された、コアを有したエージェントにおいて使用されるトランザクション・マネージメント・システムであって、
データ要求を複数のソースから受けて１つのデータ要求を選択して出力とするアービタを備え、前記データ要求にはコア読み出し要求，コア書き込み要求，プリフェッチ要求が含まれ、
前記アービタに結合されそのアービタ出力を受け、当該アービタ出力をストアされたバス・トランザクションとして保持するトランザクション・キューを備え、そのトランザクション・キューは、動的優先順位スキームに従って動作するものであって、最初にデフォルトの第１優先順位スキーム、すなわち、コア読み出し要求がプリフェッチ要求に優先する順位にあり、プリフェッチ要求がコア書き込み要求に優先する順位にある第１優先順位スキームに従って動作し、そのトランザクション・キューに輻輳が生じると、コア読み出し要求がコア書き込み要求に優先する順位にあり、ポスティングされていないストアされたバス・トランザクションから選択したプリフェッチ要求が無効にされる第２優先順位スキームに従って動作するように構成されている
ことを特徴とする、トランザクション・マネージメント・システム。
【請求項２】
請求項１に記載のトランザクション・マネージメント・システムであって、前記プリフェッチ要求には、連続的に進むアドレスに向けられた複数のデータ要求の場合に次のアドレスでのデータ要求をするパターン化されたプリフェッチ要求、および、ある１つのアドレスに向けられたデータ要求の場合に次のアドレスでのデータ要求をするブラインド・プリフェッチ要求とが含まれる、ことを特徴とするトランザクション・マネージメント・システム。
【請求項３】
請求項２に記載のトランザクション・マネージメント・システムであって、新たなデータ要求が前記アービタに入来した場合において、もしもストアされたバス・トランザクションの数が所定の閾値を越えると、輻輳イベントの生成と決定され、前記第２優先順位スキームに従って、ストアされているがポスティングされていないブラインド・プリフェッチ要求が無効にされる、ことを特徴とするトランザクション・マネージメント・システム。
【請求項４】
請求項２に記載のトランザクション・マネージメント・システムであって、新たなデータ要求がアービタに入来した場合において、ストアされているトランザクションの待ち時間があらかじめ決めたスレッショルドを超えると、輻輳イベントの生成と決定され、前記第２優先順位スキームに従って、ストアされているがポスティングされていないブラインド・プリフェッチ要求が無効にされる、
ことを特徴とする、トランザクション・マネージメント・システム。
【請求項５】
請求項２に記載のトランザクション・マネージメント・システムであって、新たなデータ要求がアービタに入来した場合において当該新たなデータ要求をストアするスペースがないと、輻輳イベントの生成と決定され、第２の優先順位スキームに従って、ストアされているがポスティングされていないパターン化されたプリフェッチ要求が無効にされる、ことを特徴とするトランザクション・マネージメント・システム。
【請求項６】
請求項１〜５の何れか１項に記載のトランザクション・マネージメント・システムであって、前記第２優先順位スキームは、ポスティングされていないプリフェッチ要求を、関連のプリフェッチ要求がポスティングされていたとしても、無効にする、ことを特徴とするトランザクション・マネージメント・システム。
【請求項７】
請求項１〜６の何れか１項に記載のトランザクション・マネージメント・システムであって、エージェントが汎用プロセッサである、ことを特徴とするトランザクション・マネージメント・システム。
【請求項８】
請求項１〜６の何れか１項に記載のトランザクション・マネージメント・システムであって、エージェントがメモリ・コントローラである、ことを特徴とするトランザクション・マネージメント・システム。
【請求項９】
請求項１〜８の何れか１項に記載のトランザクション・マネージメント・システムであって、前記トランザクション・キューには、前記アービタに結合された複数のキュー・レジスタが含まれ、各キュー・レジスタは、ストアされたバストランザクションを表すデータをストアし且つアドレス・フィールドおよび状態フィールドを有する、ことを特徴とするトランザクション・マネージメント・システム。
【請求項１０】
請求項９に記載のトランザクション・マネージメント・システムであって、前記トランザクション・キューにはコントローラが含まれ、そのコントローラは、選択されたバス・トランザクションに対応するキュー・レジスタ中の状態フィールドを変更することによって当該選択されたバス・トランザクションを無効にする、ことを特徴とするトランザクション・マネージメント・システム。
【請求項１１】
請求項１〜１０の何れか１項に記載のトランザクション・マネージメント・システムであって、
前記アービタに結合された内部キャッシュと、
前記トランザクション・キューに結合された外部バス・コントローラと
が設けられている、
ことを特徴とするトランザクション・マネージメント・システム。
【請求項１２】
データ要求に応答してバス・トランザクションを行うよう外部バスに接続された、コアを有したエージェントにおけるトランザクション・マネージメントの方法であって、
前記エージェントは、データ要求をストアされたバス・トランザクションとして保持するトランザクション・キューを備えており、そのデータ要求にはコア読み出し要求，コア書き込み要求，プリフェッチ要求が含まれ、そして、前記トランザクション・キューは、動的優先順位スキームに従って動作するものであって、デフォルトの第１優先順位スキームでは、コア読み出し要求がプリフェッチ要求に優先する順位にあり且つプリフェッチ要求がコア書き込み要求に優先する順位にあり、一方、第２優先順位スキームでは、コア読み出し要求がコア書き込み要求に優先する順位にあり且つプリフェッチ要求は無効にされることがあり、
データ要求を、前記トランザクション・キューが、第１のトランザクションとして受けるステップと；
トランザクション・キューの輻輳がなければ、前記トランザクション・キューが前記第１優先順位スキームに従った動作を続け、そうでなく輻輳があれば、前記トランザクション・キューが前記第２優先順位スキームに従って前記第１のトランザクションよりも優先順位の低い第２のトランザクションを識別するステップと、
前記第２のトランザクションを、前記トランザクション・キューが、除去するステップと、
前記第１のトランザクションを、前記トランザクション・キューが、ストアするステップと
を含むことを特徴とするトランザクション・マネージメントの方法。
【請求項１３】
請求項１２に記載のトランザクション・マネージメントの方法であって、ストアされているトランザクションの待ち時間があらかじめ決めたスレッショルドを超えると、輻輳とされる、ことを特徴とするトランザクション・マネージメントの方法。
【請求項１４】
請求項１２に記載のトランザクション・マネージメントの方法であって、ストアされたバス・トランザクションの数が所定の閾値を越えると、輻輳とされる、ことを特徴とするトランザクション・マネージメントの方法。
【請求項１５】
請求項１２に記載のトランザクション・マネージメントの方法であって、前記トランザクション・キューが充満されると、輻輳とされる、ことを特徴とするトランザクション・マネージメントの方法。
【請求項１６】
請求項１２に記載のトランザクション・マネージメントの方法であって、前記第１のトランザクションはコア読み出し要求であり、一方、前記第２のトランザクションは、連続的に進むアドレスに向けられた複数のデータ要求の場合に次のアドレスでのデータ要求をするパターン化されたプリフェッチ要求か、または、ある１つのアドレスに向けられたデータ要求の場合に次のアドレスでのデータ要求をするブラインド・プリフェッチ要求である、ことを特徴とするトランザクション・マネージメントの方法。
【請求項１７】
請求項１２に記載のトランザクション・マネージメントの方法であって、前記第１のトランザクションは、連続的に進むアドレスに向けられた複数のデータ要求の場合に次のアドレスでのデータ要求をするパターン化されたプリフェッチ要求であり、一方、前記第２のトランザクションは、ある１つのアドレスに向けられたデータ要求の場合に次のアドレスでのデータ要求をするブラインド・プリフェッチ要求である、ことを特徴とするトランザクション・マネージメントの方法。
【請求項１８】
メモリシステムと、
前記メモリシステムに外部バスを介して接続され、データ要求に応答してバス・トランザクションを行うエージェントにして、コアを有し且つトランザクション・マネージメント・システムを有するエージェントと
を備えるシステムにおいて、前記エージェントに設けられるトランザクション・マネージメント・システムには：
データ要求を複数のソースから受けて１つのデータ要求を選択して出力とするアービタを備え、前記データ要求にはコア読み出し要求，コア書き込み要求，プリフェッチ要求が含まれ、
前記アービタに結合されそのアービタ出力を受け、当該アービタ出力をストアされたバス・トランザクションとして保持するトランザクション・キューを備え、そのトランザクション・キューは、動的優先順位スキームに従って動作するものであって、最初にデフォルトの第１優先順位スキーム、すなわち、コア読み出し要求がプリフェッチ要求に優先する順位にあり、プリフェッチ要求がコア書き込み要求に優先する順位にある第１優先順位スキームに従って動作し、そのトランザクション・キューに輻輳が生じると、コア読み出し要求がコア書き込み要求に優先する順位にあり、ポスティングされていないストアされたバス・トランザクションから選択したプリフェッチ要求が無効にされる第２優先順位スキームに従って動作するように構成されている、
ことを特徴とするシステム。
【発明の詳細な説明】
【０００１】
（背景）
周知のように、多くの近代的コンピューティング・システムは、マルチ‐エージェント・アーキテクチャを採用している。代表的なシステムを図１に示す。本システムは、複数のエージェント１１０〜１６０が、あらかじめ決定されたバス・プロトコルに従って、外部バス１７０を介して通信を行う。「エージェント」には、汎用プロセッサ１１０〜１４０、メモリ・コントローラ１５０、インターフェース・チップセット１６０、入出力デバイスおよび／またはデータ要求を処理するそのほかの集積回路（図示せず）を含めることができる。バス１７０によって、複数の外部バス・トランザクションが同時に進行することができる。
【０００２】
エージェント（たとえば１１０）は、通常、エージェントの別のコンポーネントから要求を受け取り、その要求を満たす外部バス・トランザクションを処理するトランザクション・マネジメント・システムを含んでいる。図２に示されているバス・シーケンシング・ユニット２００（「ＢＳＵ」）は、その種のトランザクション・マネジメント・システムの一例である。ＢＳＵ  ２００は、アービタ２１０、内部キャッシュ２２０、内部トランザクション・キュー２３０、外部トランザクション・キュー２４０、外部バス・コントローラ２５０、およびプリフェッチ・キュー２６０などを含んでいる。ＢＳＵ  ２００は、たとえばエージェント・コア（図２には示していない）によって発行されたデータ要求に応答して、外部バス１７０上のトランザクションをマネージする。
【０００３】
アービタ２１０は、コアからのデータ要求だけでなく、プリフェッチ・キュー２６０などの各種の別のソースからのデータ要求を受け取ることができる。アービタ２１０は、アービタ２１０が同時に受け取る可能性のあるデータ要求の中から選択を行って、その１つをＢＳＵ  ２００の残りの部分に向けて出力することができる。
【０００４】
内部キャッシュ２２０は、いくつかのキャッシュ・エントリ内にデータをストアすることができる。これは、データ要求に応答して、要求されたデータの有効なコピーをキャッシュ２２０がストアしているか否かを決定するロジックを有していてもよい。ここで使用している「データ」は、インストラクション・データおよびエージェントによる使用が可能な各種のデータを指す。内部キャッシュ２２０は、データ要求に応答して要求されたデータを供給することができる。
【０００５】
内部トランザクション・キュー２３０もまた、アービタ２１０によって発行されたデータ要求を受け取り、それをストアすることができる。読み出し要求の場合であれば、内部キャッシュ２２０との調整を行って、要求されたデータが内部キャッシュ２２０を「ヒットしたか」（それによって供給可能か）否かを決定する。否であれば、つまりデータ要求が内部キャッシュ２２０を「外した」場合には、内部トランザクション・キュー２３０がそのデータ要求を外部トランザクション・キュー２４０に転送する。
【０００６】
外部トランザクション・キュー２４０は、データ要求を解釈し、要求を実行するために外部バス・トランザクションを生成する。外部トランザクション・キュー２４０は、いくつかのキュー・レジスタによって占められることもある。これは、エージェントのトランザクションが外部バス１７０上において進行するとき、そのマネージを行う。たとえば、トランザクションに応じてデータが使用可能な場合には、外部トランザクション・キュー２４０がそのデータを検索してエージェント内の要求元（たとえばコア）に転送する。
【０００７】
プリフェッチ・キュー２６０は、コア（図示せず）によって発行された読み出し要求におけるあらかじめ決定されたパターンを識別することができる。たとえば、コアが連続的に進むメモリ・ロケーション（アドレスＡ、Ａ＋１、Ａ＋２、Ａ＋３、．．．）に向けられた読み出し要求を発行したとすれば、プリフェッチ・キュー２６０は、実際にコアがデータを要求する前にシーケンス内の次のアドレス（Ａ＋４）からデータを読み出すプリフェッチ要求を発行することができる。データの要求を予測することによって、プリフェッチ・キュー２６０は、コアがそのデータに関する要求を発行したとき、内部キャッシュ２２０内にそれが入手可能になっているようにすることができる。データは、外部メモリからではなく、内部キャッシュ２２０からコアに供給されることになる。これは、はるかに高速な動作である。ここでは、このタイプのプリフェッチ要求を「パターン化されたプリフェッチ」と呼ぶことにする。
【０００８】
ＢＳＵ  ２００は、「ブラインド・プリフェッチ」と呼んでいる第２のタイプのプリフェッチも実施することができる。コアが、外部バス・トランザクションによって実行される、あるアドレス（アドレスＢとする）のデータに対する読み出し要求を発行するとき、ブラインド・プリフェッチ・メカニズムは、第２のメモリ・アドレス（Ｂ＋１）のデータを、第２の外部バス・トランザクションに検索させることができる。ブラインド・プリフェッチは、内部的に実行することができないコアからのすべての読み出し要求に、外部バス・トランザクションのペアを生じさせることができる。ブラインド・プリフェッチは、コアの読み出し要求を実行するために必要なキャッシュ・ライン（またはキャッシュ・セクタ）の２倍の検索を行うことによって、プロセッサのパフォーマンスを向上させることができる。この場合も、コアが最終的に他方のアドレス（Ｂ＋１）からプリフェッチしたデータからのデータを要求する場合には、コアがそのデータに関する読み出し要求を発行した時点において、そのデータが内部キャッシュ２２０内に存在することになる。ブラインド・プリフェッチ要求は、パターン化されたプリフェッチ要求から生成されることもある。前述の例を使用すると、アドレスＡ＋４に対するパターン化されたプリフェッチ要求を、ブラインド・プリフェッチによってアドレスＡ＋５まで拡大することができる。
【０００９】
図１に戻るが、特にマルチプロセッサ・コンピュータ・システムにおいては、外部バス１７０がシステムのパフォーマンスを制限する可能性のあることがよく知られている。外部バス１７０は、エージェントの内部クロック速度よりはるかに遅いクロック速度で動作していることが少なくない。コアは、しばしば、外部バス１７０が単一の外部バス・トランザクションを完了できる時間内に、データに関するいくつかの要求を発行することがある。つまり、単一のエージェントは、１つの外部バス１７０より多くの帯域幅を消費することができる。複数のエージェントが外部バス１７０を共有しなければならない場合には、各エージェントには、バス１７０で使用可能な帯域幅の一部しか割り当てられない。複数エージェント・システムにおいては、先に進むために必要なデータを外部バスが検索している間、エージェントがアイドル状態で待機しなければならないということが頻繁に生じている。
【００１０】
外部トランザクション・キュー２４０（図２）は、外部バスにポスティングするためにペンディング要求の優先順位設定を行うコントロール・ロジックを含むことがある。一般的に、プリフェッチ読み出しよりコア読み出しが優先順位に設定され、書き込みよりプリフェッチ読み出しが優先順位に設定される。コア読み出し要求は、コアが直ちに必要とするデータを識別する。プリフェッチ読み出し要求は、コアが、将来における任意の時点において必要とする可能性のあるデータを識別する。書き込み要求は、エージェントがシステムのストレージに戻そうとしているデータを識別する。したがって、外部トランザクション・キュー２４０は、この優先順位に従って外部バス上に要求をポスティングするコントロール・ロジックを含むことができる。
【００１１】
あらかじめ決定された優先順位スキームは、内在する欠点を有する。要求は、通常、それが外部バス上において完了されるまで、外部トランザクション・キュー２４０内にストアされる。外部トランザクション・キュー２４０が完全に、もしくはほぼ充満される高い輻輳の期間においては、プリフェッチ要求ならびに書き込み要求によって、キュー２４０への新しいコア要求のストアが妨げられることがある。優先順位の低い要求が、その要求に対する外部バス・トランザクションが完了するまで、キュー内にストアされた状態でとどまることになる。つまり、より優先順位の低い要求によって、より優先順位の高い要求を実施することが妨げられることがある。これは、システムのパフォーマンスを制限することになる。
【００１２】
したがって、この分野では、エージェント内の外部トランザクション・キューに関する輻輳マネジメント・システムが必要となっている。またこの分野では、システムの輻輳がない場合には第１の優先順位スキームを維持するが、輻輳イベントが生じた場合には第２の優先順位を実施する動的な優先順位システムを提供するシステムが求められている。
【００１３】
（要約）
本発明の実施態様は、１つのエージェントに関してマルチ‐モードのトランザクション・キューを提供する。トランザクション・キューは、デフォルトの優先順位スキームに従って動作することができる。このトランザクション・キューは、輻輳イベントが検出された場合に、第２の優先順位スキームを使用することができる。
【００１４】
（詳細な説明）
本発明の実施形態は、輻輳イベントに対する均整のとれた応答をもたらすトランザクション・キューを提供する。このトランザクション・キューは、キュー内のペンディングされているトランザクションを選択的に無効にする。つまり、現在、外部バスにポスティングされていないトランザクションを選択的に無効にする。一実施形態においては、トランザクション・キューが、ブラインド・プリフェッチ要求を最初に無効にする。このトランザクション・キューは、関連のポスティングされているプリフェッチ要求とともにストアされているポスティングされていないプリフェッチ要求を無効にすることもできる。最後に、新しい要求に使用できるスペースがまったくないといった、極度に輻輳している場合においては、トランザクション・キューがポスティングされていないパターン化されたプリフェッチ要求を無効にすることができる。
【００１５】
これらの実施形態は、動的な優先順位スキームを有するトランザクション・キューを提供する。輻輳していない場合には、トランザクション・キューが第１の優先順位スキームに従って動作する。たとえば、トランザクション・キューは、すでに述べたように、プリフェッチ要求の上にコア読み出し要求の優先順位を設定し、書き込み要求の上にプリフェッチ要求の優先順位を設定することができる。しかしながら、輻輳イベントが生じたときには、トランザクション・キューが第２の優先順位スキームを採用することができる。たとえば、トランザクション・キューは、コア読み出し要求を最優先要求として維持する一方、書き込み要求を次に高い優先順位の要求として優先順位を再設定することができる。トランザクション・キューは、トランザクション・キュー内にストアされているプリフェッチ要求を無効にすることもできる。
【００１６】
図３は、本発明の一実施形態に従ったエージェントの外部トランザクション・キュー３００のブロック図である。外部トランザクション・キュー３００は、コントローラ３１０および複数のキュー・レジスタ３２０−１〜３２０−Ｎ（集合的に３２０というラベルを適用している）を含んでいる。各キュー・レジスタ内は、アドレス・フィールド３３０、第１のステータス・フィールド３４０および第２のステータス・フィールド３５０を含む複数のフィールドが占めている。
【００１７】
外部トランザクション・キュー３００は、ブラインド・プリフェッチを実行するエージェント内における使用に適している。ステータス・フィールド３４０、３５０が、それぞれ、ブラインド・プリフェッチ・ペアに従って実行されることになる外部バス・トランザクションのそれぞれに関する情報をストアしている。アドレス・フィールド３３０には、トランザクションが向けられているベース・アドレスをストアすることができる。通常、アドレス・フィールド３３０とステータス・フィールド３４０、３５０の間には、あらかじめ決められた関係が存在する。たとえば、アドレスＤがレジスタ３２０−１のアドレス・フィールド３３０にストアされる場合、ステータス・フィールド３４０は、アドレスＤに向けられているトランザクションに関するステータス情報を維持し、ステータス・フィールド３５０は、アドレスＤ＋１に向けられている第２のトランザクションに関するステータス情報を維持するという形が考えられる。
【００１８】
ステータス・フィールド３４０、３５０は、それぞれのトランザクションに関係する管理情報をストアすることができる。この種の情報は、要求のタイプ、外部バス上におけるそれぞれのトランザクションのステータスに関する情報（つまり、それがすでにポスティング済みか、要求がいずれのトランザクション段階にあるか、トランザクションは完了したか等）、およびトランザクションに従って受け取られることになるデータの行き先に関する情報を含むことができる。通常、ステータス・フィールド３４０、３５０がともに、それらに対応するトランザクションが完了したことを示したとき、そのトランザクションはレジスタ３２０からクリアされる。
【００１９】
本発明の一実施形態によれば、ステータス・フィールド３４０、３５０は、それぞれ対応するトランザクションがコア要求（「Ｃ」）に従って生成されたか否か、あるいはプリフェッチ要求（「Ｐ」）に従って生成されたか否かを識別するサブ‐フィールドを含むことができる。図３は、７つの要求がコア要求であり、残りがプリフェッチ要求であることを示している。この例においては、レジスタ３２０−１、３２０−４、３２０−５、３２０−６、３２０−８、３２０−１１、および３２０−Ｎが、コア要求によって開始されたトランザクションをストアしている。これらのレジスタの一方のステータス・フィールド３４０または３５０が、コア要求から開始されたものとしてトランザクションを識別し；他方のステータス・フィールドは、ブラインド・プリフェッチ要求を示している。
【００２０】
残りのレジスタ３２０−２、３２０−３、３２０−７、３２０−９、および３２０−１０は、ブラインド・プリフェッチによって拡大されたパターン化されたプリフェッチ要求を識別する。これらのステータス・フィールド３４０、３５０は、いずれも対応する要求がプリフェッチ要求であることを示している。
【００２１】
コントローラ３１０は、外部トランザクション・キュー３００とエージェント内の別のエレメント（たとえば図２を参照されたい）をインターフェースする。コントローラ３１０はキュー・レジスタ３２０にトランザクションを登録し、もしくはそれから削除し、かつアドレス・フィールド３３０内およびステータス・フィールド３４０、３５０にデータを書き込むことができる。またコントローラ３１０は、外部バス１７０（図１）上にポスティングされるトランザクションの順序をスケジュールすることもできる。一実施形態においては、コントローラ３１０を状態マシンとすることができる。
【００２２】
本発明の一実施形態によれば、ＢＳＵ  ２００内における輻輳イベントの間に、コントローラ３１０が選択的にプリフェッチ要求をディセーブルすることができる。第１の実施形態においては、トランザクション・キュー３００が輻輳状態にあるとき、まだ外部バス上にポスティングされていないブラインド・プリフェッチ・トランザクションをトランザクション・キューがディセーブルすることができる。これは、たとえば、トランザクションがまだポスティングされていなくても、そのブラインド・プリフェッチ・トランザクションのステータス・フィールドを完了としてマークすることによって達成することができる。この実施形態においては、外部バスでコア読み出し要求が完了したとき、そのトランザクションを外部トランザクション・キュー３００から追い出すことができる。
【００２３】
別の実施形態においては、トランザクション・キューが輻輳状態にあるとき、トランザクション・キュー３００は、キュー内にストアされているが、まだ外部バス上にポスティングされていないパターン化されたプリフェッチ要求をすべて追い出すことができる。外部トランザクション・キュー３００は、開始されていないプリフェッチ要求を、単純に、関連付けされたキュー・レジスタの割り当てを解くことによって追い出すことができる。
【００２４】
さらに別の実施形態においては、トランザクション・キューが輻輳状態にあり、かつトランザクション・キュー３００が、すでに開始されたパターン化されたプリフェッチ・トランザクションをストアしているとき、外部トランザクション・キュー３００は、プリフェッチ・ペア内のポスティングされていないプリフェッチ・トランザクションをディセーブルすることができる。ここで、図３のレジスタ３２０−２内に図示されているパターン化されたプリフェッチ要求について考える。これからわかるように、ステータス・フィールド３５０は、１番目のプリフェッチ・トランザクションはペンディングされているが、外部バス上にまだポスティングされていないことを示している。これに対して、ステータス・フィールド３４０は、２番目のプリフェッチ・トランザクションが外部バス上にポスティングされたことを示している。この実施形態においては、トランザクション・キュー３００が、輻輳イベントに応答して、１番目のトランザクションを完了としてマークすることができる。この場合の２番目のプリフェッチ要求は、完了するまで継続することが許容される。それが完了するとトランザクション・キュー３００は、ステータス・フィールド３４０、３５０がともに完了済みトランザクションを識別していることから、レジスタ３２０−２の割り当てを解除することができる。
【００２５】
図４は、本発明の実施形態に従ってトランザクション・キュー３００（図３）によって実行される方法１０００のフローチャートである。輻輳イベントに応答して、トランザクション・キューは、新しい要求がトランザクション・キュー内に入力されたか否かを決定することができる（ステップ１０１０）。新しい要求の受け取りに応答して、トランザクション・キューはその新しい要求にレジスタが使用可能であるか否かを決定することができる（ステップ１０２０）。可能であれば、その要求を使用可能なレジスタ内にストアする（ステップ１０３０）。要求のストアは、この分野における従来の方法に従って実行することができる。トランザクション・キュー３００は、その要求のベース・アドレスを決定し、割り当て済みレジスタの各種のフィールド３３０〜３５０内に適切な情報を入力することができる。
【００２６】
ステップ１０２０において使用可能なレジスタがなかった場合には、トランザクション・キュー３００は、ポスティングされていないパターン化されたプリフェッチ要求のペアに関連付けされたレジスタの割り当てを解除することができる（ステップ１０４０）。このステップの実行において、トランザクション・キュー３００は、ステータス・フィールド３４０、３５０がともに、それぞれのトランザクションがまだ外部バスにポスティングされていないことを示しているパターン化されたプリフェッチ要求の割り当てを解除することができる。開始されていないプリフェッチ要求のペアを識別しているレジスタ３２０がまったくない場合には、新しく受け取られた要求が停止される（このステップの図示はない）。この要求は、トランザクション・キュー内に入ることが妨げられる。
【００２７】
ステップ１０３０の結果、あるいはステップ１０１０において受け取った要求がなかった場合に、トランザクション・キューは、輻輳モードで動作しているか否かを決定する（ステップ１０５０）。否であれば、トランザクション・キュー３００は、方法１０００のこの繰り返しを終了する。
【００２８】
輻輳モードにおいてトランザクション・キュー３００が動作している場合には、トランザクション・キューは、ペンディングされているブラインド・プリフェッチ・トランザクションをストアしているか否かを決定する（ステップ１０６０）。ストアしている場合には、トランザクション・キュー３００は、ブラインド・プリフェッチ・トランザクションの１つをディセーブルすることができる（ステップ１０７０）。ステップ１０７０は、コア要求またはパターン化されたプリフェッチ要求に関連付けされたブラインド・プリフェッチに適用することができる。ストアしていない場合、あるいはステップ１０７０の結果として、この方法が終了する。
【００２９】
この方法１０００は、輻輳に対して均整のとれた応答を好適に提供する。第１の応答として、トランザクション・キューは、トランザクション・キューからのブラインド・プリフェッチ要求を無効にする。前述したように、プリフェッチ要求は、クラスとしてコア要求の下位に置かれる。経験から、ブラインド・プリフェッチをパターン化されたプリフェッチの下位に置くと適切であることもわかっている。パターン化されたプリフェッチは、ブラインド・プリフェッチより効率的である可能性が高い。パターン化されたプリフェッチは、メモリからのコア読み出しの確立されたパターンに応じて発行される。ブラインド・プリフェッチは、測定可能な特徴とまったく結びつけられていない。したがって、パターン化されたプリフェッチが、最終的にコアが要求するであろうデータを検索する可能性が高く、それを残してブラインド・プリフェッチの方を無効にすることを選ぶべきである。
【００３０】
ブラインド・プリフェッチが無効化されると、新しく受け取られる要求に対してレジスタ３２０が使用可能になるレートが増加する。すでに示したように、ブラインド・プリフェッチは、コア読み出し要求に関連付けされる。コア読み出し要求は、トランザクション・キューによって扱われる最優先の要求である。これらはもっとも高い優先順位で外部バス上にポスティングされる。
【００３１】
すべてのブラインド・プリフェッチを無効化した後に、なおも輻輳が続く場合には、トランザクション・キューが、２番目のレベルの優先順位において、進行中のプリフェッチ要求に関連付けされたペンディングされているパターン化されたプリフェッチ要求を無効にすることができる（ステップ１０８０）。プリフェッチ要求の１つがすでに外部バスに対してポスティングされていることから、所定の時間内にそれが終了することが見込まれる。しかしながら、それが終了した場合であっても、２番目のペンディングされたプリフェッチ要求（つまりステップ１０８０において無効化される要求）の状態によって、関連付けされたレジスタの割り当てが解除されることが防止される。ステップ１０８０は、ペンディングされているプリフェッチ要求を完了としてマークすることによって、ポスティングされたプリフェッチ要求が終了した時点においてレジスタの割り当てが解除されることを保証する。
【００３２】
３番目のレベルの優先順位において、トランザクション・キューは、新しく受け取られた要求のために、ペンディングされているプリフェッチ要求のペアをストアしているレジスタの割り当てを解除する。これは、新しく受け取られた要求のためのレジスタがない場合に限って行われる。
【００３３】
本発明の原理は、いくつかの異なるトリガ・イベントを許容してトランザクション・キュー３００に、輻輳モードにおいて動作していることを決定させることである。第１の実施形態においては、トランザクション・キュー３００が、キュー内の割り当て済みもしくは割り当てされていないレジスタ３２０の数を基礎として輻輳していることを決定する。たとえば、レジスタの９０％もしくは１００％が充満されているとトランザクション・キューが判断した場合には、それが輻輳モードで動作していると決定することができる。
【００３４】
第２の例においては、トランザクション・キューが、測定された外部バスの待ち時間に基づいて輻輳イベントの発生を決定することができる。周知のように、通常エージェントは、あらかじめ決定されたバス・プロトコルに従って動作する。バス・プロトコルは、新しい要求を外部バス上にいつポスティングできるかということ、および可能性のある多くのエージェントのいずれに対し、各要求「スロット」に関して、すなわちバス上に新しい要求をポスティングするそれぞれの機会に関して、バス上に新しい要求のポスティングが許されるかということを管理する規則を設定することができる。その種の実施形態においてトランザクション・キュー３００は、トランザクション・キュー３００がバスのオーナーシップを獲得するまでに通過する要求スロットの数を測定することができる。測定されたスロットの数があらかじめ決めたスレッショルドを超えていれば、トランザクション・キュー３００は、輻輳イベントが生じていると決定することができる。
【００３５】
別の実施形態によれば、トランザクション・キュー３００は、検出された輻輳のタイプに応じて輻輳イベントに対する応答を変化させることができる。例としてトランザクション・キューが、前述したうちの２つのタイプのトリガ・イベントの検出が可能な場合を考える：すなわち（１）使用可能なレジスタの数が特定のスレッショルド数を下回っている場合（つまり、トランザクション・キューが完全に充満されている場合）、および（２）外部バス上の測定された待ち時間がスレッショルド値を超えている場合である。一実施形態によれば、トランザクション・キュー３００が完全に充満されていれば、トランザクション・キュー３００がすべてのプリフェッチ要求を無効にすることになるが、測定された外部バス上の待ち時間がスレッショルドを超える場合には、ブラインド・プリフェッチ要求だけを無効にすればよい。この実施形態は、単純な実施を提供し、かつ深刻性に関して高低の輻輳イベントの間における明確な区別を提供することから有利なものとなり得る。
【００３６】
以上の議論は、ペンディング要求とポスティングされている要求を区別している。これにおいて、ポスティングされている要求とは、外部バス上においてすでに開始された要求である。通常、外部バスは、あらかじめ決定されたバス・プロトコルによって定義され、それは、トランザクションが完了に向かって通過して行く漸進的な段階を指定する。上記の実施形態において説明した輻輳マネジメント方法は、すでにポスティングされているトランザクションを妨害するものではない。これに対して、ペンディング要求は、ＢＳＵバス内にストアされているが外部バス上においてまだ開始されていない要求である。本発明の輻輳マネジメント方法は、上記の実施形態の中で説明したテクニックに従ってペンディング要求を無効にすることができる。
【００３７】
すでに示したように、本発明の実施形態は、動的な優先順位スキームに従って動作することができるトランザクション・キュー３００を提供する。第１の優先順位スキームは、輻輳のない状態におけるトランザクション・キューに対して定義することができる。しかしながら、輻輳が検出されたときには、トランザクション・キューが第２の優先順位スキームを実施することができる。上記の実施形態においてはトランザクション・キューがプリフェッチ要求を無効にする。
【００３８】
以上の実施形態において説明した輻輳マネジメント・テクニックは、トランザクション・マネジメント・システムによって処理される読み出し要求に向けられている。周知のように、ＢＳＵは別のタイプの要求、たとえばエージェント内にデータを読み込ませることが意図されていない書き込み要求といった別のタイプの要求を処理することもある。前述の実施形態において説明した輻輳マネジメント・テクニックには、トランザクション・マネジメント・システムが、こういったそのほかのタイプの要求を処理する方法を妨害することが意図されていない。
【００３９】
ここでは、本発明のいくつかの実施形態を詳細に示し、説明してきた。しかしながら、本発明の修正ならびに変形が上記の教示によってカバーされ、また本発明の精神ならびに意図された範囲から逸脱することなく、付随する特許請求の範囲内に含まれることを認識されるであろう。
【図面の簡単な説明】
【図１】  マルチ‐エージェント・コンピュータ・システムのブロック図である。
【図２】  エージェントのバス・シーケンシング・ユニットを例示したブロック図である。
【図３】  本発明の一実施形態に従ったエージェントの外部トランザクション・キューのブロック図である。
【図４】  本発明の一実施形態に従った輻輳マネジメント方法のフローチャートである。
【図１】
0004219106.tif 000002
【図２】
0004219106.tif 000003
【図３】
0004219106.tif 000004
【図４】
0004219106.tif 000005