(57)【特許請求の範囲】
【請求項１】
個々のクロックサイクルで複数の命令を発行できるマルチスレッドプロセッサにおいて、複数の利用可能な命令から個々のクロックサイクルでどの命令を発行すべきかを動的に決定する方法であって、
前記複数の利用可能な命令から最も優先度が高い命令を決定するステップと、
前記最も優先度が高い命令と前記利用可能な命令の各々との互換性を判断するステップと、
を含み、命令は、同じリソースを必要としない場合に互いに互換性があり、
前記最も優先度が高い命令を、前記最も優先度が高い命令と互換性があるとともに互いに互換性がある他の命令とともに同じクロックサイクルで発行するステップをさらに含み、
前記最も優先度が高い命令を投機的命令とすることはできないことを特徴とする方法。
【請求項２】
前記最も優先度が高い命令を決定するステップが、命令を発行できる最も優先度が高いスレッドを決定するステップと、このスレッドからの前記命令を前記最も優先度が高い命令として選択するステップとを含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
投機的命令、又は投機的命令を含むスレッドに、前記最も優先度が高い命令を決定するステップに利用できないものとしてマーク付けするステップをさらに含む、
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記複数の利用可能な命令の優先順位を決定するステップをさらに含み、前記最も優先度が高い命令と互換性のある命令が優先順位の順に発行される、
ことを特徴とする請求項１、２又は３に記載の方法。
【請求項５】
投機的命令に、非投機的命令よりも低い優先順位が与えられる、
ことを特徴とする請求項４に記載の方法。
【請求項６】
前記複数の利用可能な命令の優先順位を決定するステップが、利用可能な命令を含む個々のスレッドの優先順位を決定するステップを含む、
ことを特徴とする請求項４又は５に記載の方法。
【請求項７】
前記利用可能な命令ごとに互換性のある又は互換性のない命令のリストを決定するステップをさらに含む、
ことを特徴とする請求項１から６のいずれかに記載の方法。
【請求項８】
個々のクロックサイクルで複数の命令を発行できるマルチスレッドプロセッサにおいて命令を発行するためのシステムであって、
複数の利用可能な命令から最も優先度が高い命令を決定するための手段と、
前記最も優先度が高い命令と残りの前記利用可能な命令の各々との互換性を判断するための手段と、
を備え、命令は、同じリソースを必要としない場合に互いに互換性があり、
前記最も優先度が高い命令を、前記最も優先度が高い命令と互換性があるとともに互いに互換性がある他の命令とともに同じクロックサイクルで発行するための手段をさらに備え、
前記最も優先度が高い命令を投機的命令とすることはできないことを特徴とするシステム。
【請求項９】
前記最も優先度が高い命令を決定するための手段が、命令を発行できる最も優先度が高いスレッドを決定し、このスレッドからの前記命令を前記最も優先度が高い命令として選択するための手段を備える、
ことを特徴とする請求項８に記載のシステム。
【請求項１０】
投機的命令、又は投機的命令を含むスレッドに、前記最も優先度が高い命令としての検討に利用できないものとしてマーク付けするための手段をさらに備える、
ことを特徴とする請求項８又は９に記載のシステム。
【請求項１１】
前記複数の利用可能な命令の優先順位を決定するための手段をさらに備え、前記発行するための手段が、前記最も優先度が高い命令と互換性のある命令を優先順位の順に発行するように構成される、
ことを特徴とする請求項８、９又は１０に記載のシステム。
【請求項１２】
前記複数の利用可能な命令の優先順位を決定するための手段が、利用可能な命令を含む個々のスレッドの優先順位を決定するための手段を備える、
ことを特徴とする請求項１１に記載のシステム。
【請求項１３】
前記利用可能な命令ごとに互換性のある又は互換性のない命令のリストを決定するための手段をさらに備える、
ことを特徴とする請求項８から１２のいずれか１項に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチスレッドマイクロプロセッサにおける命令の発行を動的に最適化するための方法及び装置に関する。詳細には、本発明は、個々のクロックサイクルで１つよりも多くのスレッドからの命令を発行できるマルチスレッドマイクロプロセッサにおいて投機的命令を発行することに関する。
【背景技術】
【０００２】
マルチスレッドプロセッサは、他のいずれかのプロセッサのように実行ユニット、キャッシュ及びメモリなどを含むが、複数のスレッドを実行するという概念をさらに組み入れたマイクロプロセッサである。実行するスレッドは、マイクロプロセッサのリソースに基づいて機能する命令ストリームから成り、これらの命令ストリームには、この特定のスレッド固有のものもあればスレッド間で共有できるものもある。リソースとしては、レジスタ、帯域幅、及びキャッシュ又はメモリ内の空間がある。図１は、当業で公知のマルチスレッドマイクロプロセッサコアの概略図である。図１に示すようなマルチスレッドプロセッサコアでは、いくつかのスレッド２が、スレッド命令スケジューラ１を介して命令を発行するというこれらのスレッドの能力に従って並行して動作することができる。スレッドに優先順位を与えて、どの命令を最初に発行すべきかを決定できるようにすることができる。
【０００３】
プロセッサは、複数のスレッドが同じデータキャッシュ３などの同じリソースを同時に使用しなければ、これらの複数のスレッドからの命令を同じクロックサイクルで発行することができる。スケジューラは、個々のクロックサイクルでどの命令を一緒に発行できるかを判断するように構成されなければならない。
【０００４】
投機的命令は特殊な命令である。マイクロプロセッサの分野では、投機的命令をフェッチして発行するという概念が十分に理解されている。投機的命令のフェッチ及び発行は、以前のプログラム命令の結果の予測を立て、その後、予測が正しく行われたかどうかが分かる前に、この予測に基づいて命令をフェッチして発行するという形をとる。結果を予測する動作の最も一般的な例に、条件テストに基づいてどのコードパスをとるべきかに関して選択を行うプログラム内の分岐の予測がある。別の例には、リターン予測及びジャンプ予測がある。その後、予測が正しかったと判定された場合、プロセッサは継続する。予測が正しくなかったと判定された場合、予測した命令及びこれらの副作用を消去して、新たに決定された命令フェッチアドレスから命令のフェッチ及び発行を再開する必要がある。
【０００５】
投機的という用語は、プロセッサが、あらゆる直近に発行した命令の結果を知る前に動作を行う必要があるという理由で使用される。例えば、分岐は、比較又は条件テスト命令の直後に続くことが当然である。パイプラインプロセッサでは、パイプラインが多くのステージにわたることがあり、通常、条件テストの結果は、パイプラインをはるかに下った所で得られる。しかしながら、分岐は命令フェッチに直接影響を与え、従ってパイプラインの開始と同時に影響を及ぼす。この結果、条件テストの結果が分かるまで分岐を待機させる必要があるためバブル又はストールが生じ、この待機の代替案として、どの分岐が選択されそうであるかを推測し、この推測を、推測が正しかったか又は間違っていたかが分かるまでたどるべきルートとして採用する。推測を行ってからこの推測の正しさが分かるまでの間にフェッチ及び／又は発行された命令が必ずしも正しいとは限らず、解除する必要が生じることもあるため、投機的という用語を使用する。推測は、（逆方向のたどった分岐、順方向のたどっていない分岐などの）単純なルール、又はあるコードの部分が過去にどのようなことを最も一般的に行ったかを示す履歴データのいずれかに基づいて行われる。
【０００６】
本明細書で使用する「投機的命令」という用語は、以前のプログラム命令の結果がまだ分かっていないために不要となる可能性のあるフェッチ及び／又は発行された命令を意味する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】英国特許出願公開第０８０２３１４号明細書
【特許文献２】欧州特許第１６３９５５４号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、複数のスレッドからの命令を同じクロックサイクルで発行できるプロセッサにおいて投機的命令の発行をスケジュールする方法を課題とする。
【課題を解決するための手段】
【０００９】
本発明の第１の態様によれば、個々のクロックサイクルで複数の命令を発行できるマルチスレッドプロセッサにおいて、複数の利用可能な命令から個々のクロックサイクルでどの命令を発行すべきかを動的に決定する方法が提供され、この方法は、複数の利用可能な命令から最も優先度が高い命令を決定するステップと、最も優先度が高い命令と残りの利用可能な命令の各々との互換性を判断するステップとを含み、命令は、同じリソースを必要としない場合に互いに互換性があり、最も優先度が高い命令を、最も優先度が高い命令と互換性があるとともに互いに互換性がある他の命令とともに同じクロックサイクルで発行するステップをさらに含み、最も優先度が高い命令を投機的命令とすることはできない。
【００１０】
この方法の効果は、投機的命令が常に少なくとも１つの非投機的命令とともにしか発行されないことである。
【００１１】
本発明の第２の態様によれば、個々のクロックサイクルで複数の命令を発行できるマルチスレッドプロセッサにおいて命令を発行するためのシステムが提供され、このシステムは、複数の利用可能な命令から最も優先度が高い命令を決定するための手段と、最も優先度が高い命令と残りの利用可能な命令の各々との互換性を判断するための手段とを備え、命令は、同じリソースを必要としない場合に互いに互換性があり、最も優先度が高い命令を、最も優先度が高い命令と互換性があるとともに互いに互換性がある他の命令とともに同じクロックサイクルで発行するための手段をさらに備え、最も優先度が高い命令を投機的命令とすることはできない。
【００１２】
本発明の好ましい実施形態は、複数のスレッドから個々のクロックサイクルで命令を発行することができるマルチスレッドマイクロプロセッサにおいて投機的命令の効率的なスケジューリングを行うことを課題とする。
【００１３】
本発明のこの及びその他の態様については添付の特許請求の範囲で定義しており、ここではこれらを参照されたい。
【００１４】
以下、本発明の好ましい実施形態の詳細な説明を、添付図面を参照しながら一例として行う。
【図面の簡単な説明】
【００１５】
【図１】マルチスレッドプロセッサコアを示す図である。
【図２】本発明によるシステムで使用するのに適した命令フェッチサブシステムを示す図である。
【図３】投機的命令をフェッチするためのシステムを示す図である。
【図４】本発明による、投機的命令をフェッチして実行するためのシステムを示す図である。
【図５】本発明の態様による、命令の発行をスケジュールするための処理ステップを示す図である。
【発明を実施するための形態】
【００１６】
図１は、マルチスレッドマイクロプロセッサの概略図である。このマイクロプロセッサは、命令スケジューラ１を介して命令を発行する能力に従って並行して動作する複数のスレッドをサポートする。このシステムでは、異なるスレッドが同じリソースを同時に使用しようと試みなければ、これらのスレッドが命令を同時に発行することができる。スレッド命令が使用するリソースとして、算術演算装置４及び５、命令キャッシュ及びデータキャッシュを含むキャッシュサブシステム３、及びコプロセッサがある。また、システムは、単純なアドレスマッピングに基づいてキャッシュサブシステムの代わりにアクセスできる少量のオンチップランダムアクセスメモリ（ＲＡＭ）を含むこともできる。システムは、命令ＲＡＭ及びデータＲＡＭを組み込むことができる。
【００１７】
マイクロプロセッサは、並行して動作するいくつかのパイプライン又は実行ユニットを含む。１つのスレッドが１つのパイプラインに命令を発行している場合、他のスレッドは、同じクロックサイクルで他のパイプラインに命令を発行することができる。これを行うために、スケジューラが複数のスレッドからの命令を個々のクロックサイクルで利用できる必要があり、スケジューラは、あらゆる衝突するリソース要件を防ぐことができなければならない。
【００１８】
図２は、スケジューラが複数のスレッドからの命令を全てのクロックサイクルで利用できるように命令をフェッチすることに関与する要素を示している。このサブシステムは、同時継続中の英国特許出願公開第ＧＢ０８０２３１４．５号明細書に記載されている。図２に示す実施形態には、命令キャッシュ２０及びオンチップＲＡＭ２２という２つの主な命令データソースが存在する。パフォーマンスを最適化するために、両方のソースに同時にアクセスすることができる（但し、個々のスレッドは一方又は他方にしかアクセスせず、両方にアクセスすることはない）。２つの命令データソースを有することにより、サイクルごとに２つの異なるスレッドのために最大２つの命令を取得できるようになる。
【００１９】
命令キャッシュ２０又はオンチップＲＡＭ２２のいずれかからの命令にどのスレッドがアクセスすべきかを決定するために、個々の命令ソースは、これらの命令ソースとスレッドの各々の命令フェッチユニット２５との間に結合された優先度アービタ２４を有する。
【００２０】
個々の優先度アービタは、（スレッド０〜スレッドｎの）スレッドの各々の命令フェッチユニット２５に結合される。この接続を介して、優先度アービタは、命令を求める要求を関連する優先度付けデータとともに受け取り、フェッチした命令を命令フェッチユニット２５に与えることができる。
【００２１】
個々の命令フェッチユニット２５は、命令デコーダ及びリソースインターロックユニット２６に与える準備が整った最大８つの命令を保持することができる命令バッファを含み、その後この命令デコーダ及びリソースインターロックユニット２６が命令スケジューラ２８に命令を発行し、この命令スケジューラ２８が個々の命令を実行のためにさらにプロセッサに渡す。
【００２２】
命令スケジューラ２８は、複数のスレッドの命令を取得すると、これらの複数のスレッドの命令を同じサイクルで発行することができる。
【００２３】
命令スケジューラ２８は、複数のスレッドからの命令を同じクロックサイクルで発行できるようになるために、個々のスレッドの命令が必要とするリソースを、他の命令に必要なリソースに照らしてテストする必要がある。この結果、衝突する命令が同時に発行されないことが確実になる。このことは、命令デコードユニット２６が、対応する命令フェッチユニット２５から個々の命令が入って来たときにこの命令を予備デコードし、この命令に必要な規定のリソースを、装置内でアクティブな他の全てのスレッドのための並行して定められたリソースに照らしてＡＮＤｉｎｇすることによって管理することができる。
【００２４】
縮小したこれらのリソース要件の組をテストすることができる。単純な例を挙げると、あるスレッドが、何らかのデータをロード又は記憶するために、実行ユニットを使用してデータメモリをフェッチする要求を送信したいと望むとする。別のスレッドが、このデータメモリのフェッチに同じ実行ユニット又はデータメモリポートのいずれかを使用したいと望む場合、このスレッドは、最初のスレッドの実行と互換性がないことになり、これらの２つを同時に発行することはできなくなる。しかしながら、別のスレッドが、これらのリソースを必要としないプログラム分岐などの異なる命令セットを実行したいと望む場合、このスレッドは互換性があると見なされ、このスレッドを、あるスレッドを使用してデータメモリのフェッチを要求するのと同時に実行のために発行することができる。
【００２５】
適切な判断を行うために、全ての存在するスレッドは、互いに対して並行してテストした規定のリソース要件を全て有する。この処理は、スレッドＡがスレッドＢと互換性があり、当然スレッドＢもスレッドＡと互換性があるという点で対称的である。従って、個々のスレッドの対の間ではテストを１回行えばよい。この互換性テストの結果、個々のスレッドの組み合わせごとにフラグを生成し、このフラグの状態により、スレッドに互換性があるか否かを判断する。従って、個々のスレッドを他の全てのスレッドに対してテストした結果、スレッドの対ごとに互換性フラグが生成され、このフラグの状態によってスレッドに実行のための互換性があるか否か、すなわち同時に２つのスレッドのみが重複するリソース要件を有するかどうかが判断されるということになる。
【００２６】
次に、どの命令を発行すべきかを判断するために、個々のスレッドに優先順位を与える。この優先順位は、欧州特許第１６３９５５４号明細書に記載されている自動ＭＩＰＳ割り当て（ＡＭＡ）メトリックなどのいずれかの好適なメトリックに基づくことができる。この結果、レジスタ又はリソースのインターロックによって命令の発行が防げられない最も優先順位が高いスレッドが、発行するスレッドとして選択される。同じリソースを必要としないことが判明している他のいずれかのスレッドは、自由に発行できる最も優先度が高いスレッドからの（優位命令と呼ばれる）命令とともにグループ化して、このクロックサイクルで発行される命令セットに変えることができる。命令を、これらの命令とすでにセットに含まれている命令との互換性に従う優先順位でセットに追加することもできる。
【００２７】
個々の命令が必要とするリソースの判断は、命令デコードユニット２６における命令予備デコード動作によって行われる。デコードユニット２６は、個々の命令が必要とするリソースの概要を生成する。次に、命令スケジューラが、このリソース要件を別のスレッドに照らしてスレッド間の互換性があるかどうか、及び機械の状態に照らしてリソース及びレジスタの利用可能性があるかどうかをテストする。スケジューラは、これらのテストの結果を優先順位と組み合わせて、所与のサイクルでスケジュールするための最終的な命令セットを提供する。
【００２８】
当技術では、「投機」の概念は十分に理解されている。この投機は、予測を行い、その後この予測が正しく行われたかどうかが分かる前にこの予測に基づいて命令を発行するという形をとる。命令の結果を予測する動作の最も一般的な例に、条件テストに基づいてどのコードパスをとるべきかに関して選択を行う分岐がある。投機は短期間にのみ適用され、その後は命令の結果が分かり、通常のスケジューリングを再開することができる。
【００２９】
本発明の態様によれば、投機的に実行される命令は、上述した通常のスレッド命令の優先度ルールを使用しない。これらのルールを使用すべきでない理由は、投機が正しいかどうかが発行時に分からないからである。通常の優先度ルールを使用することの代替案は、これらのスレッドに最も低い優先度を与えることである。しかしながら、これによりいくつかの設計課題が生じ得る。従って、好ましい構成としては、投機的に実行される命令は、別のスレッドと対になっている場合を除き発行の機会を有するべきではない。
【００３０】
本発明の好ましい例は、２又はそれ以上のスレッド（具体的には２つ、３つ又は４つのスレッド）を有するマルチスレッドマイクロプロセッサで構成される。マイクロプロセッサ内の個々のスレッドは固有のプログラムカウンタ（ＰＣ）を有し、これをさらに使用して、そのスレッドの命令フェッチを、命令メモリ又は命令キャッシュから命令をフェッチするための１つのハードウェアを全てのスレッドが有するように制御する。全てのスレッドが固有の命令メモリ又は命令キャッシュを有するようにすることもできる。しかしながら、このためには、システム内のスレッドに必要なメモリが同じシステム内の他のスレッドよりも少なくて済むかどうかに関わらず、個々のスレッドが必要とするリソースでこれらのスレッドを構築する必要がある。これは望ましいことではない。望ましい戦略は、命令メモリ及び命令キャッシュを全スレッド間で共有して、これらのスレッド間の、このメモリ又はキャッシュへのアクセス権の問題を解決することである。
【００３１】
個々のスレッドは、これら自体の命令フェッチに特有の一定量のハードウェアを有するので、このハードウェアを、命令のフローに関する予測を行うように拡大することができる。例えば第１の例では、予測ハードウェアが、命令ストリーム内の分岐命令が発行のために送信されるのを監視し、この分岐が選択されるかどうかを予測することができる。その後、命令フェッチにおいて、この（分岐を選択するか又はしないかなどの）予測に基づいてフェッチパターンを変更することができる。この段階で、命令フェッチが（発行時に）分岐自体の結果を判定できるまで待機し、その後さらなる命令を与え、又は修正した場所からフェッチを再開するようにシステムを構成することができる。この手の予測される命令フェッチを図３に示す。
【００３２】
図３から分かるように、個々のスレッドの命令フェッチシステムは、新たな要求を生成するための状態機械３０（「アドレスフィード」）、並びにスレッド及びその命令スケジューラに命令を与えるための状態機械３２（「データフィード）で構成される。状態機械３２は、図２の命令予備デコード及びリソースインターロックテスト２６の機能を含む。また、図３には、返送するフェッチデータから分岐命令を取り出し、これらの分岐がどこへ続くのかについての予測に基づき、命令をどこから読み出すべきかに関してアドレスフィードを更新することができる分岐フィルタ及び予測ユニット３４も示している。
【００３３】
非マルチスレッドマイクロプロセッサでは、命令の消費量が最大要求率未満である場合、命令フェッチパイプラインがストールすることがある。しかしながら、命令キャッシュがスレッド間で共有されるマルチスレッドシステムでは、スレッドがいくつかの命令を要求したもののこれらを使用しない場合には、システム内の他の全てのスレッドがストールするようにスレッド間に依存状態が生じるので、通常このようなストールは考えられない。従って、個々のスレッド命令フェッチユニットは、一定数の命令要求のための返送データを保持することができる命令バッファを組み込む。命令バッファ内に存在するスロットに記憶できる数と同じ数の命令要求を送信中とすることができる。この命令バッファをブロック３６として示している。命令は、命令バッファから命令データフィードユニット３２を介して命令スケジューラに渡る。
【００３４】
このシステムでは、分岐の方向（順方向又は逆方向）などの単純なルールに基づいて、又は過去にこの分岐がどのルートをたどったかに関する何らかの形の簡易履歴を使用して予測を行うことができる。発行レジスタ３８における実際の分岐命令の発行は、結果が分かる（すなわち状態テストなどの断定を行うことができる）まで棚上げされる。結果が判定されると、分岐を発行し、その後命令のフローにより、予測したフェッチデータを取り出すか、又は命令フェッチが正しい命令アドレスから再開されるようにするかのいずれかを行うことができる。
【００３５】
このようなシステムは、分岐を選択することに関する待ち時間のいくつかを隠すために有用である。しかしながら、このようなシステムには、分岐状態テストの結果が判定されるのを待っている間に常にストールが生じ得るという大きな制限がある。
【００３６】
このシステムに対する改善として、分岐の結果、従って分岐予測の正しさが判明するよりも前に予測した命令を発行することが挙げられる。この場合、（発行時点では分岐予測が正しかったかどうかが分かっていないので）分岐の直後に発行された命令は投機的に実行される。プロセッサパイプラインにおいて分岐の結果が計算されると、予測が正しく行われたかどうかが最終的に明らかになる。予測が正しく行われていた場合、命令の発行は投機的ではなくなり、スレッドを通常通りに継続することができる。予測が正しく行われていなかったことが判明した場合、分岐後に発行した命令及びこれらの副作用を消去し、新たに判定された命令フェッチアドレスから命令フェッチを再開する必要がある。この投機的命令フェッチ及び発行を図４に示す。
【００３７】
図４には、図３と同じフェッチシステムの特徴を示しているが、投機的命令が発行されるという違いがある。図４には、命令スケジューラ２８の後に３段階の実行パイプライン４０を示し、さらに分岐予測ユニット３４へ戻る分岐予測検証データ経路４２を示している。図４から分かるように、分岐命令の評価にはいくつかのサイクルが必要となり得る。これらのサイクルがストールするのを避けるために、スレッドは、分岐以降ずっと命令を発行し続けることができる必要がある。これは、これらの命令の動作を解除できるという条件で行うことができる。図４から分かるように、通常、対象となる命令の数はかなり不足しており、図示のように多くても３つ又は４つの命令しか存在しない。
【００３８】
マルチスレッドマイクロプロセッサでは、所与のサイクルで発行できる命令を有するいくつかのスレッドが十分に存在することができる。従って、（発行すべきかどうかという点で）発行される命令の正しさに疑いの余地がない場合には、他のスレッドから非投機的命令を発行する方がよいと考えられる。しかしながら、投機的命令を絶対に発行しない場合、（まさにフェッチのみを予測する構成のように）スレッドの命令ストリームには常にストールが生じ得る。命令を投機的に発行する利点は、良好な予測を行うことができる場合には、命令ストリームにおけるｉｆ／ｔｈｅｎ決定に関するストールがより少ない状態でより有用な作業を行うことができるという点である。
【００３９】
このように、発行により、他の命令を実行する準備ができている他のスレッドに影響が及ばなければ、可能な場合には命令を投機的に実行できることが有益である。これを行うための１つの方法は、投機的に実行しているスレッドに最も低い優先度を与えることである。しかしながら、現在の命令発行と将来の優先順位との間にフィードバックループが存在するシステムでこれを行うことは困難となり得る。より容易に行うことができる代替案としては、投機的実行命令に、第１の又は主要な又は優位な発行物に適さないものとしてマーク付けすることである。これは、投機的に実行される命令を主な命令スケジューラにとって利用可能な命令として提示せず、代わりにスレッドがこの段階でスレッド自体にインターロックされたもの又は利用できないものとしてマーク付けするようにすることによって行うことができる。
【００４０】
実行の準備ができている命令を含む最も優先度の高いスレッドの選択と並行して、このスレッドと同時に他のどのスレッドを発行できるようにするかに関する決定を行う必要がある。この計算は、負荷バランシングメトリック一式を計算する場合と比較して関与するゲートが少ないので、全てのサイクルでスレッド全てに関して行うことができる。必要なゲートは、スレッドの規定のリソースをシステム内の他のスレッド全てに対してテストして、このスレッドの命令と互換性のある他のスレッドのリストを提供する。その後、この情報を事前に準備したスレッドの優先順位と組み合わせて、最初のスケジューリング決定に勝る場合、このスレッドとともにどのスレッドを発行するかについての絶対リストを作成する。
【００４１】
図５に、本発明の態様による、どの命令を使用すべきかを決定する上で行うステップを示す。ステップ５００において、利用可能な命令を有するスレッドの各々に関して優先順位を決定する。この段階では、リソース又はレジスタのインターロックが検討から外れているので、スレッドは命令を発行することができない。投機的命令を有するスレッドは、この段階で検討するのに適していないものとしてスレッド自体にマーク付けも行う。ステップ５１０において、命令を発行できる最も優先度の高いスレッドを選択する。このスレッドから発行される命令を優位命令と呼ぶ。上述したように、この優位命令は投機的命令であることはできない。ステップ５２０において、利用可能な命令を含むスレッドごとに互換性のあるスレッドのリストを作成する。ステップ５３０において、これらのリスト及び優先順位から、優位命令とともに発行するための命令セットを決定する。ステップ５４０において、命令スケジューラにより命令セットが発行される。
【００４２】
従って、本発明は、命令を投機的に実行する場合にスレッドが通常の命令スケジューリングルールをうまく回避できるようにする単純な手段を提供する一方で、従来であれば、分岐結果が判定されるのを待っている間にスケジューラがストールさせる必要があったであろう命令を発行できることによりスループットが改善される可能性はそのまま保持する。この解決策で使用する追加のゲートはわずかであり、この結果所定のマルチスレッドマイクロプロセッサ設計で達成できるクロックスピードに負の影響を与えることはない。
【符号の説明】
【００４３】
２０  命令キャッシュ
２２  オンチップＲＡＭ
２４  優先度アービタ
２５  命令フェッチ
２６  命令デコーダ及びリソースインターロック
２８  命令スケジューラ
【図１】
0005631976.tif 000002
【図２】
0005631976.tif 000003
【図３】
0005631976.tif 000004
【図４】
0005631976.tif 000005
【図５】
0005631976.tif 000006