(57)【特許請求の範囲】
【請求項１】
複数の命令ソースからの、マルチスレッドプロセッサシステムにおける複数の実行命令スレッドの各々に対する命令のフェッチングに優先順位を付ける方法であって、
複数の命令をバッファするためのバッファを各々含む個々のスレッド毎に、そのスレッドでの実行のために現在バッファされている命令の数に基づいて第１のメトリックを決定するステップと、
前記個々のスレッドからの前記第１のメトリックから、命令をフェッチするための優先順位を決定するステップと、
前記優先順位のリストを、個々のスレッド毎の実行ベースの優先順位メトリックと組み合わせて、スレッドの優先順位の順番リストを決定するステップと、
命令を要求しているスレッドのうちで前記決定された優先順位が最も高い前記スレッドのために、前記命令のソースから、命令をフェッチするステップと、
を含み、
前記第１のメトリックが個々のスレッド毎の充満度に基づいており、前記第１のメトリックが前記優先順位を最初に決定し、前記実行ベースの優先順位メトリックが前記第１のメトリックからでは競合が存在するスレッド間の優先順位を決定し、スレッドが、前記複数の命令ソースのいずれか１つから、前記複数の命令ソースの各々に設けられた優先順位アービタを介して、命令を要求することができ、２以上のスレッドが、個々のクロックサイクルで命令を実行することができる、ことを特徴とする方法。
【請求項２】
スレッドが、個々のクロックサイクルで命令ソースから命令を要求することができる、
ことを特徴とする請求項１に記載の方法。
【請求項３】
第１の命令ソースから命令を要求したスレッドは、前記第１の命令ソースに対する要求が完了するまで第２の命令ソースから命令を要求することができない、
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記スレッドが、自身のバッファ内に命令を含むいずれのスレッドを個々のクロックサイクルで実行すべきかを決定するための実行ランクの順序を有する、
ことを特徴とする請求項１に記載の方法。
【請求項５】
複数の命令ソースからの、マルチスレッドプロセッサシステムにおける複数の実行命令スレッドの各々に対する命令のフェッチングに優先順位を付けるシステムであって、前記システムが、
複数の命令をバッファするためのバッファを各々含む個々のスレッド毎に、そのスレッドでの実行のために現在バッファされている命令の数に基づいて第１のメトリックを決定して、個々のスレッドからの前記第１のメトリックから、命令をフェッチするための優先順位を決定する優先順位アービタ（２４）であって、前記優先順位と実行ベースの優先順位メトリックとを組み合わせて、スレッドの優先順位の順番リストを決定する、前記複数の命令ソースの各々に設けられた複数の優先順位アービタ（２４）と、
命令を要求しているスレッドのうちで前記決定された優先順位が最も高い前記スレッドのために、前記命令のソースから、命令をフェッチするための命令フェッチユニット（２６）と、を備え、
前記第１のメトリックが個々のスレッド毎の充満度に基づいており、前記第１のメトリックが前記優先順位を最初に決定し、前記実行ベースの優先順位メトリックが前記第１のメトリックからでは競合が存在するスレッド間の優先順位を決定し、スレッドが、前記複数の命令ソースのいずれか１つから、該命令ソースに設けられた優先順位アービタを介して、命令を要求することができ、２以上のスレッドが、個々のクロックサイクルで命令を実行する、ことを特徴とするシステム。
【請求項６】
スレッドが、個々のクロックサイクルで命令ソースから命令を要求することができる、
ことを特徴とする請求項５に記載のシステム。
【請求項７】
第１の命令ソースから命令を要求したスレッドは、前記第１の命令ソースに対する要求が完了するまで第２の命令ソースから命令を要求することができない、
ことを特徴とする請求項５に記載のシステム。
【請求項８】
スレッドが、自身のバッファ内に命令を含むいずれのスレッドを個々のクロックサイクルで実行すべきかを決定するための実行ランクの順序を有する、
ことを特徴とする請求項５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マイクロプロセッサシステムにおける命令フェッチングの優先順位付けに関し、特にマルチスレッドマイクロプロセッサシステムにおけるこの実装に関する。
【背景技術】
【０００２】
本発明者らの欧州特許出願ＥＰ０８９１５８８号には、複数のデータ入力と複数のデータ出力との間でデータ処理手段を介して複数の実行スレッドをルーティングするマルチスレッドマイクロプロセッサ及びデータ処理管理システムについての記載がある。データ処理手段はデータ記憶手段にアクセスすることができ、システムは、実行できるルーティング動作及びデータ処理動作を繰り返し決定して、ルーティング及びデータ処理動作の少なくとも一方の実行をそれぞれのクロックサイクルで開始する。
【０００３】
このようなシステムでは、メモリ管理ユニットを使用して、内部メモリキャッシュ又は外部メモリのいずれかからデータをフェッチする。通常、外部メモリは単一のデータ経路しか持たず、従ってメモリプレアービタを使用して、メモリからのデータに関して異なるスレッドからの要求間でアービトレーションを行う。
【０００４】
本発明者らの欧州特許出願ＥＰ１７３８２５９号では、実行中の様々なスレッドに付随する様々なメトリックを使用してメモリアービトレーションを改善するためのスキームを提案している。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述した種類のマルチスレッドプロセッサに対する改善として、本発明者らが「スーパースレッディング」と呼ぶ概念が導入されてきた。この概念では、所与のクロックサイクルで２以上の実行スレッドに対して命令が出される。全ての実行スレッドに対する命令を単一のクロックサイクルで出すことができ、４スレッドの実施構成では最大で１クロックサイクル当たり４つの命令が出される。しかしながら、このような実施構成は、全ての実施可能なスレッドが、利用可能ないつでも実行できる命令を有している場合にしか完全に利用されることはない。
【０００６】
マルチスレッドプロセッサのいくつかの実施構成では、例えば１つのスレッドに対して８つまでの命令を保持できる命令バッファがスレッドに提供される。この命令バッファは命令フェッチルーチンを使用することによって満たされ、この命令フェッチルーチンは、使用される現在の命令に先だって命令をフェッチすることができ、さらに命令によって生じ得る分岐又はハードウェアループ予測などの動作も決定できることが好ましい。
【０００７】
複数のスレッドを利用する場合、通常、命令データをフェッチできるソースは１つ又は２つしか存在しない。これらは、命令キャッシュ及び組み込み命令ＲＡＭメモリである。したがって、４つの実行スレッドを有する装置では、命令データのソースよりも多くのスレッドが存在するため、スレッド間アービトレーションを実施して命令データへのアクセスを最適化することが必要となる。
【課題を解決するための手段】
【０００８】
本発明の好ましい実施形態は、異なる実行スレッドのための命令フェッチング間の効率的なアービトレーションの問題に対処する一方で、できるだけ多くのスレッドがそのバッファ内に次の実行のための少なくとも１つの命令を有することを確実にしようと試みる。
【０００９】
本発明の１つの態様によれば、少なくとも１つの命令ソースからの、マルチスレッドプロセッサシステムにおける複数の実行命令スレッドの各々に対する命令のフェッチングに優先順位を付ける方法が提供され、この方法は、個々のスレッドに関して、そのスレッドでの実行のために現在バッファされている命令の数に基づいて第１のメトリックを決定するステップと、個々のスレッドに関して実行ベースの第２のメトリックを決定するステップと、第１及び第２のメトリックからスレッドの優先順位を決定するステップと、命令を要求している決定優先順位の最も高いスレッドのソースから命令をフェッチするステップとを含む。
【００１０】
本発明の上記の及びその他の態様は、ここで参照すべき添付の特許請求の範囲で定義される。
【００１１】
以下、添付図面への参照の一例として本発明の好ましい実施形態の詳細な説明を示す。
【図面の簡単な説明】
【００１２】
【図１】本発明を具体化するマルチスレッドプロセッサを示す図である。
【図２】図１のシステムで使用する命令フェッチサブシステムを示す図である。
【図３】図２の命令フェッチサブシステムで使用する命令フェッチユニットを示す図である。
【図４】図２の命令フェッチサブシステムと共に使用するプライオリティアービタを示す図である。
【発明を実施するための形態】
【００１３】
図１に示すシステムはマルチスレッドプロセッサコアを含む。このマルチスレッドプロセッサコアは、各々が命令フェッチユニット２を介して命令を提供するいくつかのスレッドを実行することができる。複数の実行スレッドの各々により実行される命令は、各スレッドごとに１つのスレッド命令フェッチユニット２によりフェッチされる。システムはあらゆる数のスレッドを有することができるが、現在では通常２又は４が使用される。一般に、これらのスレッドは、スレッド命令スケジューラ４を介してこれらの命令を出す能力に従って並行して動作するように構成されるが、個々のクロックサイクルで１つのスレッドのみが実行できるシステムでこれらを使用することもできる。本例では２つの命令ソースが存在し、命令キャッシュ６が外部メモリから命令を読み出し、コアコードメモリ８が、オペレーティングシステム命令及びこの種のその他の命令を記憶する。命令キャッシュとスレッド命令フェッチユニットとの間にはアービトレータが位置し、コアコードメモリ８とスレッド命令フェッチユニットとの間にはさらなるアービトレータが位置する。このアービトレータを使用して、いずれのスレッドが次に個々の命令ソースから命令を読み出すべきかを決定する。
【００１４】
この例では、スレッド命令スケジューラ４が、この図では演算／論理ユニット（ＡＬＵ）１２で表される４つの実行パイプラインの各々に命令を出す。これらが複数の実行スレッドを実行する。
【００１５】
実行スレッド上のデータメモリに対する要求が命令として開始され、この命令は出された後に、要求をデータキャッシュ１４へルーティングするか、又はＲＡＭコアコードデータメモリ１６へルーティングするかの決定ポイントに命令スケジューラを介して渡される。ＭＭＵ１８が、データキャッシュ１４及び命令キャッシュ６からの要求を処理して外部メモリからデータを読み出す。
【００１６】
この構成の変形例として、コードとデータとの間でＲＡＭを共有することができる。しかしながら、この場合実施構成が複雑になり、現在では使用されていない。当然ながら実行ユニット間には、本発明の表現を理解する必要がないという理由で明確化のためにこの図には示していない多くの相互接続が存在する。
【００１７】
完全な実施構成では、キャッシュサブシステム３の代わりにアクセスできる少量のオンチップＲＡＭを組み込むことができる。いくつかのシステムでは、命令ＲＡＭ及びデータＲＡＭも組み込むことができる。
【００１８】
マルチスレッドプロセッサは多くの他の文献に記載されており、当業者には周知であろう。本明細書で説明する本発明の実施形態は、好ましくは２以上のスレッドに対する命令をあらゆる所与のクロックサイクルで出すことができる命令スケジューラに供給するための命令のフェッチの優先順位付けに焦点を合わせている。本発明を具体化する適当なシステムのブロック図を図２に示す。この図は、命令フェッチサブシステムにおける主要素を全て示している。
【００１９】
この実施形態では２つの命令データソースが存在するが、これは１つのみであっても又は３以上であってもよい。これらは、命令キャッシュ２０及びオンチップＲＡＭ２２であり、オンチップＲＡＭ２２は、実行命令スレッドの様々なスレッド上で実行される必要があり得るマイクロプロセッサのための組み込み命令を搭載する。スレッドが命令を要求した場合、命令キャッシュ２０又はオンチップＲＡＭ２２のいずれかから命令をフェッチする必要がある。命令を要求するスレッドは、利用可能な命令ソースの１つ、すなわち要求された命令を含むソースへこの要求を送信する。個々のスレッドは、クロックサイクルにつき１つの命令フェッチしか出すことができない。
【００２０】
２つの命令ソースが存在する場合、異なるスレッドが別のものとして個々の命令ソースに同時にアクセスすることができる。命令キャッシュ２０又はオンチップＲＡＭ２２のいずれかから命令にアクセスすべきスレッドを決定するために、個々の命令ソースは、これらとスレッドの各々の命令フェッチユニットとの間に結合されたプライオリティアービタ２４を有する。
【００２１】
個々のプライオリティアービタは、スレッドの各々（スレッド０〜スレッドｎ）の命令フェッチユニット２６に結合される。この接続を介して、プライオリティアービタは、命令に対する要求を関連する優先順位付けデータと共に受け取り、フェッチされた命令を命令フェッチユニット２６に提供することができる。
【００２２】
個々の命令フェッチユニット２６は命令バッファを含み、この命令バッファは、命令デコーダ及びリソース連動ユニット２８に供給する準備が整っている命令を８つまで保持することができ、その後命令スケジューラ３０に命令を出して、この命令スケジューラ３０がさらに個々の命令をプロセッサに渡して命令が実行される。
【００２３】
プライオリティアービタ２４は、個々のスレッドの命令スレッドフェッチユニット２６から、命令フェッチユニット２６が命令バッファ内に、又は命令バッファ内にロードする処理において残した命令データがいくつ存在するかについての測定値、すなわち現在バッファ済みの命令の数に関するデータを受け取ることによって動作する。したがって、命令バッファが８つの命令を含むことができ、現在のところ５つの命令を含んでいる場合、現在スレッドが５つのバッファ済み命令（又はそのバッファ内に３つのさらなる命令用のスペース）を有する旨を示すデータがプライオリティアービタへ送信される。次に、プライオリティアービタは、他のスレッドから受け取ったデータとこのデータを比較して、スレッドの優先順位を決定する。その後、プライオリティアービタは、優先順位が最も高く命令の要求も行っているスレッドに優先権を与える。
【００２４】
プライオリティアービタ２４は、この命令を出すための第１の優先順位付けの測定値をさらなる測定値と組み合わせることができる。この第２の測定値は、スレッドに与えられる総合的な優先順位のより高度な測定値である。通常、この測定値は、スレッドのいくつかの異なる特性の組み合わせである。これらの特性は、スレッドを実行しなければならない期限であるデッドラインカウント、スレッドの実行が最初に要求されてからの遅延である遅延カウント、これから実行すべき命令の数、及びスレッドに与えられる公称優先順位である優先順位を含むことができる。デッドラインカウントは、スレッドの実行をいつ完了させる必要があるかを決定するので、これらの中で最も重要である。この種の測定値では、スレッドの優先順位に関するその他の要素を使用することもできる。
【００２５】
したがって、本発明の好ましい実施形態では、個々のプライオリティアービタ２４が、命令の必要性に関する優先順位の測定値、すなわちスレッドの命令バッファの充満度に基づく測定値と、いくつかの異なる因子に基づくことができる総合的なスレッドの優先順位とを組み合わせる。これらを使用して、個々のプライオリティアービタが、命令キャッシュ又はオンチップＲＡＭのいずれかから個々のサイクルで命令を要求する場合、いずれの所与のサイクルにおいても、決定優先順位が最も高いスレッドが命令キャッシュ又はオンチップＲＡＭに適宜アクセスできるスレッドとなるようにスレッドの優先順位の順番リストを決定することができる。スレッドは、一度にこれらの命令ソースの１つにしかアクセスしない。スレッドが両方から同時に命令をフェッチすることはできない。
【００２６】
この例では、命令キャッシュに１つ及びオンチップＲＡＭに１つの、２つのプライオリティアービタを示している。各々には同じメトリックが提供される。各々が、クロックサイクルごとに同じ優先順位リストを生成する。しかしながら、これらのプライオリティアービタは、関連するソースから命令を要求する相互に排他的なスレッドの組を有する。単一のソースを含むあらゆる数の命令ソースによって本発明の実施形態を実施することができる。
【００２７】
より具体的には、本発明の実施形態は、２又はそれ以上のスレッド（通常は４）を有するマルチスレッドプロセッサ上で実行される。マルチスレッドプロセッサとは、実行ユニット、キャッシュ及びメモリを備え、付加的に複数の実行命令のスレッドの概念を組み入れたマイクロプロセッサのことである。スレッドは、マイクロプロセッサのリソースを利用するように作用する数々の命令で構成され、これらのリソースのいくつかはこの特定のスレッドに固有のものとすることができ、いくつかはスレッド間で共有することができる。リソースは、キャッシュ及び関連メモリ内のレジスタ、帯域幅、及び空間を含む。
【００２８】
マルチスレッドプロセッサにおける個々のスレッドは固有のプログラムカウンタを有し、これをさらに使用して、このスレッドの命令フェッチを制御する。したがって、全てのスレッドが、命令メモリ又は命令キャッシュから命令をフェッチしてこのスレッド上で実行するための１つのハードウェアを有する。個々のスレッドが固有の命令メモリ又は命令キャッシュを有することは可能であるが、全てのスレッド間で命令メモリ及び命令キャッシュを共有し、メモリ又はキャッシュへのアクセス権に関してこれらの間でアービトレーションを行うことにより、コスト及びサイズが最小化される。
【００２９】
ラウンドロビンなどの単純なアービトレーション法は、ある程度まで十分機能することができる。異なるスレッドが異なる作業負荷を有し、最も需要の高いスレッドが命令にアクセスする際に他のスレッドよりも上の優先順位を得るようにスレッドの優先順位間のバランスを取る必要がある場合に困難が生じる。
【００３０】
上述した本発明者らの欧州特許出願第ＥＰ１７３８２５９号では、より高度なアービトレーションの１つの形について説明しており、この場合、ハードウェアが時間に伴うスレッドの負荷をモニタし、これを定められたリソース要件と照合する。この欧州特許では、この形を使用してメモリなどのリソースへのアクセスを決定する。
【００３１】
本発明者らは、２以上のスレッドがあらゆる所与のサイクルで命令を出すことができることを理解している。これが行われるためにはいくつかの基準を満たす必要があり、まず第１に、全てのスレッドが発行可能な命令を有している必要があり、第２に、２つのスレッドが同じリソースを同時に使用することを試みないようにこれらの命令が互いに両立し得る必要がある。この状況では、リソースが、実行ユニット、データキャッシュアクセス、コプロセッサアクセスなどをカバーする。したがって、ｎ個のスレッドのシステムでは、単一のサイクル中に０とｎの間のあらゆる数のスレッドが命令を出し得る。
【００３２】
特に２以上のスレッドが同時に命令を実行できるスーパースレッディングプロセッサでは、いずれのスレッドがいずれのリソースを必要としているかを判断するための処理が複雑となる。しかしながら、個々の命令を実行予定候補として命令スケジューラ４に対して利用可能にする前のプレデコード段階を通じてこれらの命令を渡すことにより判断が開始される。このプレデコード段階を使用して、命令が必要とするリソースを選出する。
【００３３】
スーパースレッディングプロセッサでは、減少したこれらのリソース要件の組がテストされる。単純な例を選択すると、スレッドが、実行ユニットを使用してデータメモリのフェッチ要求を送信し、いくつかのデータをロード又は記憶したいと望むことがある。別のスレッドが、同じ実行ユニット又はデータメモリポートを使用してデータメモリをフェッチしたいと望む場合、第１のスレッドの実行と両立しなくなることにより、これらの２つは同時には発行されなくなる。しかしながら、別のスレッドが、これらのリソースを必要としないプログラム分岐などの異なる命令セットを実行したいと望む場合には両立可能と見なされ、スレッドを使用してデータメモリのフェッチを要求するのと同時に、実行のために別のスレッドが発行される。
【００３４】
適切な判断を行うために、存在するスレッドは全て、互いに並行してテストされた定められた全てのリソース要件を有する。この処理は、スレッドＡがスレッドＢと両立できる場合には定義によりスレッドＢがスレッドＡと両立することもできるという点で対称的である。したがって、このテストは、個々のスレッドのペア間で一度行うだけでよい。
【００３５】
この両立性テストの結果、個々のスレッドのペアリングに対してフラグが生成され、このフラグの状態により、スレッドに両立性があるかどうかが判断される。したがって、個々のスレッドを他の全てのスレッドに対してテストした結果、個々のスレッドのペアごとに両立性フラグが生成され、この状態により、スレッドが実行に関して両立性があるかどうか、すなわち同時にリソース要件と重複するスレッドが２つのみであるかどうかが判定される。
【００３６】
また、スレッドはランク付けされた順序を有する。両立性状態の情報を使用して、より低いランクの各々を順々に検討することにより、この順序における個々のランク、最終的な両立性の設定が作成されるようになる。あるランクが、優先順位の最も高いスレッドと両立性がある場合、このスレッドが実行のための設定に追加され、両立性がなければ、このスレッドはスキップされ次のスレッドが検討される。実際の命令の予定への最終ステップでは、ランキングの最も高い発行できるスレッドが決定され、すなわちリソース又はレジスタが利用可能になるのを待つことはない。その後、このスレッドが、そのスーパースレッディングセット（このスレッドと共に実行できる他のスレッド）と共に発行される。
【００３７】
スレッドが同時に命令を出す能力を最大にするためには、できる限り全てのスレッドが発行可能な命令を有していることが重要である。したがって、プライオリティアービタは、スレッド命令バッファ内に何も有していない、又はスレッド命令バッファのスレッド命令外で実行されているスレッドのフェッチング命令に適宜優先権を与えるように構成される。この結果、これらのスレッドは、総合的な優先順位ランキングがより高いスレッドを含む命令をフェッチする際に他のスレッドよりも優先される。
【００３８】
スレッド命令フェッチユニットの好ましい実施形態を図３に示している。個々のスレッドには、このような命令フェッチユニットが提供される。命令キャッシュから命令を取得することに関連してこの特定の例を示しているが、同様にこの例を図２に示すようなオンチップＲＡＭと共に使用することもできる。
【００３９】
命令フェッチユニットは命令アドレス供給ユニット３２を含み、これが命令に対する要求を命令キャッシュへ送信する。命令キャッシュ内で命令を検索する時間に起因して、命令アドレス供給ユニット３２からの命令の発行間にはいくらかの待ち時間が存在し、数々の発行命令から待ち時間を低減又は全く排除するのに十分な頻度で命令を要求するように命令フェッチエンジンを構成することが好ましい。
【００４０】
非マルチスレッドマイクロプロセッサでは、命令の消費が最大要求レートよりも低い場合、命令フェッチのパイプラインが失速することがある。しかしながら、スレッド間で命令キャッシュを共有するマルチスレッドシステムでは、このような失速によりスレッド間に依存関係が生じ、いくつかの命令を要求したもののこれらを使用していないスレッドがシステム内の全ての他のスレッドを失速得るようになるので、通常このような失速が起きる可能性はない。したがって、個々のスレッド命令フェッチユニットは、一定数の命令要求の戻りデータを保持できる命令バッファを組み込んでいる。命令バッファ内に存在する記憶できるスロットと同じ数の命令要求を送信中とすることができる。命令バッファは３４で示している。命令バッファを経て、命令は、命令データ供給ユニット３６を介して命令スケジューラに渡される。
【００４１】
本発明の好ましい実施形態では、３８における命令バッファの充満度に関するデータが、スレッド命令フェッチユニットから抽出される。このデータは、命令バッファ内で利用可能なスロットの数を示すデータ値、又はいくつのスロットがすでに占有されているかを示すデータ値であってもよい。このデータは、図２に示す種類のプライオリティアービタ２４に提供され、このプライオリティアービタがこのデータを使用して、他のスレッドと比較して命令が不足しつつあるスレッドの命令フェッチに優先順位を付ける。この結果、このスレッドの命令バッファにできるだけ早くさらなる要求が提供されて、命令スケジューラに対して大量の命令が利用可能となることを確実にする。
【００４２】
したがって、いくつかのスレッドの各々に図３の命令フェッチユニットを使用して、どのスレッドの命令バッファが最も多くの命令を有し、どれが最も少ないかを示すデータを提供することができる。これらのデータがプライオリティアービタによって比較され、優先順位付けリストが生成される。この結果、命令バッファ内の命令が最も少ないスレッドを、（このスレッドが命令を要求しているとした場合）次のクロックサイクルの次の命令フェッチに対して優先させることができる。同時に、スレッドの少なくとも１つが命令スケジューラに命令を出し、この結果さらに次のクロックサイクルの優先順位を変更することができる。したがって、優先順位が最も高く、命令ソースからの命令も要求しているスレッドが、命令をフェッチすることになる。
【００４３】
上述したように、このシステムは、スレッドを個々の命令フェッチユニット内の命令バッファ３４の充満度に基づく順序にソートすることにより、スレッドに優先順位を付ける。本発明の好ましい実施形態は、付加的なアービトレーションのレベルを追加することによりこれを修正する。
【００４４】
図２に示す種類のプライオリティアービタを図４にさらに詳細に示す。プライオリティアービタ２４は命令要求を受け取り、その関連するオンチップＲＡＭ又は命令キャッシュからの命令を、マルチスレッドプロセッサにおいて提供されるそれぞれのスレッドの命令フェッチエンジンの各々に与える。プライオリティアービタへの入力は、それぞれの命令バッファの充満度により個々のスレッドの命令フェッチエンジンに関して決定された優先順位である。この入力を別個のユニットで得ることができる。或いは、関連データ値をプライオリティアービタ自体に提供し、その後このプライオリティアービタが必要な優先順位を計算するようにしてもよい。
【００４５】
個々の命令フェッチユニットは、自身の命令バッファを満たすのに十分な命令しかフェッチできないので、命令バッファが満たされたスレッドは、各サイクルにおいて新しいフェッチを要求することはない。したがって、プライオリティアービタは、新しい命令を要求している最も高い優先順位のスレッドを、このスレッドの要求信号を介して決定する。
【００４６】
プライオリティアービタ２４により決定された、又は別個のユニットから受け取った優先順位は、発明者らが自動ＭＩＰＳアロケーション（ＡＭＡ）メトリックと呼ぶ上述した優先順位に関する付加的な測定値と組み合わされる。これは、例えば、デッドラインカウント、遅延カウント、及びスレッドの実行に影響を与えるその他の考えられる因子の組み合わせであってもよい。事実上、命令バッファの充満度から決定されたプライオリティメトリックと組み合わせることができるのは実行ベースのメトリックである。
【００４７】
ＡＭＡメトリックは、単純なスレッドの順序に容易化され、すなわちこれはソートしたスレッドのリストである。これは、バッファ容量に関するデータのリストを有する個々のスレッドの各々の命令バッファの充満度とは対照的である。次に、プライオリティアービタ２４により、これらの２つの情報を使用して優先順位が決定される。
【００４８】
バッファ容量は極めて重要であり、リストが形成され、最も満たされたスレッドの命令バッファから最も空に近いものへの順序でソートされる。最も空に近いものに高い優先順位がある。スレッドが全て異なるバッファ充満度を有する場合、本発明の好ましい実施形態では、これで処理が終了する。ＡＭＡメトリックは、同じバッファ充満度を有するスレッドの正しい順序を決定するためにのみ使用される。
【００４９】
例えば、４つのスレッドを有し、各々の命令バッファが空である場合、各々に命令がフェッチされる必要性は等しい。したがって、次にアービタは、個々のスレッドのＡＭＡメトリックについて検討する必要がある。これらは、３、２、１、及び０にランク付けされる。３を最も高い優先順位のメトリックとし、０を最も低い優先順位のメトリックとした場合、３のＡＭＡを有するスレッドが、次の命令フェッチに対して最も高い優先順位を有することになる。
【００５０】
別の例では、スレッド０、１、２、及び３の命令に対する必要性にそれぞれ１、２、２、０の優先順位が与えられ、個々のスレッドのＡＭＡメトリックがそれぞれ３、２、１、及び０である場合、最終的な優先順位は、１、３、２、及び０になる。これは、スレッド１及び２が命令に対する最も高い必要性を有し、これらの２つのスレッドのうち、スレッド１は３のＡＭＡ優先順位を有し、スレッド２は２のＡＭＡ優先順位を有するからである。
【００５１】
全てのスレッドが異なる必要性を有する場合、命令をフェッチする順序が決定され、ＡＭＡメトリックは命令をフェッチする順序には影響を与えない。プライオリティアービタは、より速い優先順位の決定を可能にするので、現在ではハードウェアに実装することが好ましい。しかしながら、ソフトウェアの方がより速くなる場合、アービタをソフトウェアの形で実装することもでき、実際にいくつかのアプリケーションでは、現在ソフトウェアの実施形態により許容できるパフォーマンスが与えられることがある。動作時には、スレッドの各々を個々のクロックサイクルで内部的にチェックして、これらがいずれかの特定のメモリから命令を要求しているかどうかを判定する。最も高い優先順位のスレッドが命令を要求しており、これが何らかの方法でブロックされていなければ要求が出される。これは、将来のサイクルで使用される必要なメトリックを変えることになる。最も高い優先順位のスレッドが要求を作成していなければ、他の全ての優先順位を順々に検討して、これらを使用できるかどうかを確認する。命令を要求できるスレッドがない場合、このサイクルでは要求は作成されない。
【００５２】
命令がフェッチされると、この命令はオンチップＲＡＭ又は命令キャッシュからスレッド命令フェッチユニットに直接供給される。命令が命令フェッチユニットに到達する順序は、フェッチされる命令のソース及び個々のソース内の命令の場所によって様々であってもよい。
【００５３】
命令キャッシュから又は専用の命令メモリから命令をフェッチできる図２のシステムを使用して、異なるスレッドが命令キャッシュ及び命令メモリにそれぞれ同時にアクセスできることが理解されるであろう。これには、２つのプライオリティアービタが必要となる。２つの装置間でアービタの優先順位リストを共有することができる。
【００５４】
したがって、好ましい実施形態では、スレッドを実行するための命令フェッチユニットの各々に結合された個々の命令ソースごとにアービタが提供される。これらは、命令を要求する個々のスレッドから様々な時点で命令フェッチ要求を受け取り、要求間でアービテーションを行っていずれのスレッドがこのソースから命令を受け取るべきかを決定する。個々のスレッドは、１クロックサイクル当たり１つの命令フェッチしか出すことができない。スレッドは、異なるソースからの命令を要求しないと同時に、依然として第１のソースからの未処理の要求を有していることが好ましい。
【符号の説明】
【００５５】
２０  命令キャッシュ
２２  オンチップＲＡＭ
２４  プライオリティアービタ
２６  命令フェッチ
２８  命令デコード及びリソース連動
３０  命令スケジューラ
【図１】
0005607545.tif 000002
【図２】
0005607545.tif 000003
【図３】
0005607545.tif 000004
【図４】
0005607545.tif 000005