(57)【要約】【課題】【解決手段】プロセッサは優先規則に従って命令をインタリーブする。この優先規則は、それぞれのスレッドからの命令を選択し、その命令を、データ・プロセッサで処理するインタリーブされた命令ストリームに加える頻度を決定する。規則に従ってそれぞれのスレッドを選択する頻度は、命令スレッドに割り当てられた優先度に基づいて決定することができる。このインタリービング・プロセスにランダム化が挿入され、その結果、任意のクロック・サイクルでの命令スレッドの選択が、優先規則だけに基づいてなされるのではなしに、ランダムまたは擬似ランダム要素にも基づいて決定される。このランダム化は、さまざまな命令スレッドから命令を選択する順序が変更され、同時に、優先規則によって設定される全体的なスレッド選択の頻度（すなわちスレッドをどのくらい頻繁に選択するか）が維持されるような方法で、命令スレッド選択プロセスに挿入される。【選択図】図２
2004326767.tif 000002
【特許請求の範囲】
【請求項１】
データ・プロセッサにおいて複数の命令スレッドを処理する方法であって、
（ａ）第１の命令スレッドからの命令と少なくとも１つの追加の命令スレッドからの命令を、前記第１の命令スレッドと前記少なくとも１つの追加の命令スレッドの間の優先規則に従ってインタリーブする段階と、
（ｂ）前記インタリービング段階にランダム化を挿入し、同時に前記優先規則を維持する段階と
を含む方法。
【請求項２】
命令をインタリーブする前記段階がサイクル単位で実施される、請求項１に記載の方法。
【請求項３】
優先規則に従って命令をインタリーブする前記段階が、処理するスレッドを指示するスレッド選択信号を生成する段階を含む、請求項１に記載の方法。
【請求項４】
ランダム化を挿入する前記段階が、前記スレッド選択信号をランダム化する段階を含む、請求項３に記載の方法。
【請求項５】
前記スレッド選択信号をランダム化する前記段階が、
（ａ）前記第１の命令スレッドに関連づけられた第１のスレッド優先度信号および追加の命令スレッドにそれぞれ関連づけられたそれぞれの追加のスレッド優先度信号から、マスクを生成する段階と、
（ｂ）乱数または擬似乱数を発生させる段階と、
（ｃ）前記マスクと前記乱数または擬似乱数とを比較して、ランダム化されたマスクを生成する段階と
を含む、請求項４に記載の方法。
【請求項６】
命令をインタリーブする前記段階が、
（ａ）前記マスクを反転させて反転されたマスクを生成する段階と、
（ｂ）前記ランダム化されたマスクと前記反転されたマスクを比較する段階と
を含む、請求項５に記載の方法。
【請求項７】
データ・プロセッサにおいて、処理する命令を複数の命令スレッドから選択する際に使用するスレッド選択出力を生成する方法であって、
（ａ）前記複数の命令スレッドに関連づけられ、前記複数の命令スレッドのそれぞれのスレッドの優先度を指示する優先度信号からマスクを生成する段階と、
（ｂ）前記マスクと比較するのに適した乱数または擬似乱数を発生させる段階と、
（ｃ）前記マスクと前記乱数または擬似乱数を比較してランダム化されたマスクを生成する段階と、
（ｄ）前記ランダム化されたマスクから前記スレッド選択出力を生成する段階と
を含む方法。
【請求項８】
マスクを生成する前記段階が、第１の優先度信号を第２の優先度信号と比較する段階を含む、請求項７に記載の方法。
【請求項９】
第１の優先度信号を第２の優先度信号と比較する前記段階の前に、前記第１の優先度信号および前記第２の優先度信号のうちの一方を反転させる段階をさらに含む、請求項８に記載の方法。
【請求項１０】
乱数または擬似乱数を発生させる前記段階が線形帰還シフト・レジスタを用いて実行される、請求項７に記載の方法。
【請求項１１】
マスクを生成する前記段階の前に前記優先度信号をビットごとに展開する段階をさらに含む、請求項７に記載の方法。
【請求項１２】
前記ランダム化されたマスクから前記スレッド選択出力を生成する前記段階がさらに、
（ａ）前記マスクを反転させて反転されたマスクを生成する段階と、
（ｂ）前記ランダム化されたマスクと前記反転されたマスクを比較する段階と
を含む、請求項７に記載の方法。
【請求項１３】
前記ランダム化されたマスクと前記反転されたマスクの前記比較の結果を結合する段階をさらに含む、請求項１２に記載の方法。
【請求項１４】
前記ランダム化されたマスクと前記反転されたマスクの前記比較の結果に、プロセッサのクロック・サイクル周波数で論理レベルが変化するトグル・ビットを結合する段階をさらに含む、請求項１３に記載の方法。
【請求項１５】
同時マルチスレッド・プロセッサにおいて、処理する命令を選択する際に使用するスレッド選択出力を生成する回路であって、
（ａ）前記マルチスレッド・プロセッサ内の第１の命令スレッドのスレッド優先度を指示する第１の優先度信号、および前記マルチスレッド・プロセッサ内の追加の命令スレッドのスレッド優先度を指示する追加の優先度信号を受け取り、前記第１の優先度信号のマスクを生成するマスク論理と、
（ｂ）前記マスクと比較するのに適した乱数または擬似乱数を発生させる乱数発生器と、
（ｃ）前記マスク論理および前記乱数発生器に結合され、前記マスクと前記乱数または擬似乱数とを比較してランダム化されたマスクを生成する比較論理と、
（ｄ）前記比較論理に結合され、前記ランダム化されたマスクから前記スレッド選択出力を生成する結合論理と
を含む回路。
【請求項１６】
前記マスク論理が、前記第１の優先度信号を、前記追加の優先度信号の反転された値を表す反転された優先度信号と比較する優先度信号比較器を含む、請求項１５に記載の回路。
【請求項１７】
前記マスク論理が、前記第１の優先度信号を展開して展開された第１の優先度信号を生成する第１のエキスパンダと、前記追加の優先度信号を展開して展開された追加の優先度信号を生成する第２のエキスパンダとを含む、請求項１５に記載の回路。
【請求項１８】
前記結合論理が、
（ａ）反転されたマスクを生成するマスク・インバータと、
（ｂ）前記ランダム化されたマスクと前記反転されたマスクを比較して比較出力を生成するマスク比較器と
を含む、請求項１５に記載の回路。
【請求項１９】
前記結合論理が、前記比較出力のビットに論理ＡＮＤ演算を実行する結合ＡＮＤ装置を含む、請求項１８に記載の回路。
【請求項２０】
トグル・ビットを発生させ、前記トグル・ビットを前記比較出力に追加するトグル・ビット発生器をさらに含み、前記トグル・ビットが、前記結合ＡＮＤ装置が実行する前記論理ＡＮＤ演算に含まれる、請求項１９に記載の回路。
【請求項２１】
同時マルチスレッド・プロセッサにおいて、処理する命令を選択する際に使用するスレッド選択出力を生成する回路であって、
（ａ）インタリーブ規則執行出力を生成するインタリーブ規則執行構成要素と、
（ｂ）前記インタリーブ規則執行出力を受け取り、前記同時マルチスレッド・プロセッサ内の複数の命令スレッド間のスレッド選択を制御するランダム化されたスレッド選択出力を生成するランダム化構成要素と
を含む回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の命令スレッドを処理する能力を有するプロセッサに関する。詳細には本発明は、処理のために命令スレッドをインタリーブする方法にランダム化を導入し、同時に命令スレッド間のインタリービングの全体的な比率または程度をある所望の比率または程度に維持する装置および方法に関する。
【背景技術】
【０００２】
データ・プロセッサがソフトウェア・プログラムを実行する速度を向上させる目的にはいくつかの技法が使用される。これらの技法には、プロセッサのクロック速度を高めること、キャッシュ・メモリを使用すること、および分岐予測を使用することが含まれる。プロセッサのクロック速度を高めると、プロセッサは、与えられた時間内に相対的に多くの演算を実行できるようになる。キャッシュ・メモリは、プロセッサのすぐ近くに置かれ、メイン・メモリよりも速く動作する。これによってプロセッサがデータおよび命令にアクセスするのに要する時間が短縮される。分岐予測では、プロセッサが、以前の命令の結果に関する予測に基づいてある種の命令を実行することができ、そのため実結果を待つ必要がなくなり、これによって処理速度が向上する。
【０００３】
いくつかのプロセッサはさらに、パイプライン方式の命令実行を使用してシステム性能を強化している。パイプライン命令実行では、処理タスクが、いくつかのパイプライン・ステップまたはステージに分割される。パイプライン処理では、以前に発行された命令が特定のプロセスを完了させる前に後続の命令が処理を開始できるようにすることによって、処理速度を高めることができる。プロセッサは、ある命令が完全に処理されるのを待つことなく次の命令の処理を開始することができる。
【０００４】
パイプライン処理を使用するプロセッサは、プロセッサ内での異なるアクティビティに充てられる異なるいくつかのパイプラインを含むことができる。例えばプロセッサは、一連の命令を、フェッチ・ステージ、解読／ディスパッチ・ステージ、発行ステージ、実行ステージ、終了ステージおよび完了ステージで処理することができる。これらの個々のステージはそれぞれ、自体のパイプライン・ステージ・セットを使用して、所望の処理タスクを実行することができる。
【０００５】
マルチスレッド命令処理は、パイプライン処理とともに使用して処理速度を高めることができる追加の技法である。マルチスレッド命令処理は、１つのプログラム命令セットを、２つ以上の別個の命令群ないし命令スレッドに分割することを含む。このマルチスレッド技法では、何らかの理由で１つのスレッドが処理できない場合でも、その間に、別の１つのスレッドからの命令をパイプライン処理することができる。これによって、シングル・スレッド命令処理において遭遇する、例えば特定の命令を実行するのに必要なデータがすぐには使用できないキャッシュ・ミス状況などで特定の命令を実行できない間、全ての命令が停止される状況が回避される。複数の命令スレッドを処理する能力を有するデータ・プロセッサはしばしば、同時マルチスレッディング（simultaneous multithreading：ＳＭＴ）プロセッサと呼ばれる。
【０００６】
ソフトウェア分野での用語「マルチスレッディング」の使用方法と、コンピュータ・アーキテクチャ分野での用語「マルチスレッディング」の使用方法とは異なることに留意されたい。ソフトウェア分野では用語「マルチスレッディング」が、複数の関連スレッドに細分されたある１つのタスクについて使用される。コンピュータ・アーキテクチャ分野では、用語「マルチスレッディング」が、互いに独立したスレッドを含むスレッドに対して使用される。本明細書では用語「マルチスレッディング」を、コンピュータ・アーキテクチャ分野で使用されている意味と同じ意味で使用する。
【０００７】
マルチスレッディングを容易にするため、異なるスレッドからの命令は、プロセッサ・パイプライン上のあるポイントで何らかの方法でインタリーブされる。ＳＭＴプロセッサで処理する命令をインタリーブする技法には一般に異なる２つの技法がある。１つの技法は、１つのスレッドの処理において遅延を引き起こすキャッシュ・ミスなどのある長い待ち時間事象（long latency event）に基づいてスレッドをインタリーブすることを含む。この技法では、ある長い待ち時間事象によって１つのスレッドの処理に遅延が生じるまで、全てのプロセッサ・リソースがその１つのスレッドに向けられる。長い待ち時間事象が出現すると、プロセッサはすぐに別のスレッドに切り替わり、そのスレッドに対してある長い待ち時間事象が生じるまで、または先のスレッドを停止させた状況が解決される場合、そのスレッドの処理を進める。
【０００８】
ＳＭＴプロセッサにおいて複数の命令スレッドからの命令をインタリーブするもう１つの一般的な技法は、命令を、あるインタリービング規則に従ってサイクル単位でインタリーブすることを含む。単純なサイクル単位のインタリービング技法は、異なるスレッドからの命令を１命令ずつ単純にインタリーブする。例えば２スレッドＳＭＴプロセッサでは、第１のクロック・サイクルで第１のスレッドから１つの命令を取り出し、第２のクロック・サイクルで第２のスレッドから１つの命令を取り出し、第３のクロック・サイクルで第１のスレッドの別の命令を取り出し、．．．というように、２つの命令スレッド間で交互に命令を処理することができる。より複雑なサイクル単位のインタリービング技法は、それぞれの命令スレッドに優先度を割り当て（通常ソフトウェアを介して）、次いでインタリーブして、相対的なスレッド優先度に基づくある規則を執行することを含む。例えば、２スレッドＳＭＴプロセッサにおいて、一方のスレッドに他方のスレッドよりも高い優先度が割り当てられている場合、単純なインタリービング規則は例えば、優先度が高いほうのスレッドからインタリーブされた命令ストリームに含める命令の数を、優先度が低いほうのスレッドから含める命令の数の２倍にすることを要求する。
【０００９】
現在使用されているより複雑なサイクル単位インタリービング規則では、それぞれのスレッドに「１」から「７」までの優先度を割り当て、優先度が低いほうのスレッドの要素を、関数１／（２｜Ｘ−Ｙ｜＋１）に基づいてインタリーブされた命令ストリームに入れる。ただし、Ｘ＝ソフトウェアによって第１のスレッドに割り当てられた優先度、Ｙ＝ソフトウェアによって第２のスレッドに割り当てられた優先度、である。２つのスレッドの優先度が等しい場合、例えばＸ＝３、Ｙ＝３のときには、この関数から比１／２が得られ、２つのスレッドからそれぞれ２クロック・サイクルに１回、１つの命令が、インタリーブされた命令ストリームに入れられる。スレッド優先度の差が２の場合、例えばＸ＝２、Ｙ＝４のときには、この関数から比１／８が得られ、優先度の低いほうのスレッドから、８クロック・サイクルに１回、１つの命令が、インタリーブされた命令ストリームに入れられる。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、優先規則の執行が、インタリーブされたストリームへのいずれかのスレッドの進入を妨げる競合を引き起こす、偶発的な状況またはシナリオがある。一般に「ライブ・ロック」状況と呼ばれるこれらの状況では、異なるスレッドからの命令が優先規則に従って、これらの異なる命令スレッドの全てが停止してしまう循環的な方法でインタリーブされる。例えば、マルチスレッド・プロセッサ内の異なる命令スレッドからの命令がともに、それらの間で共用されている１つのリソースを必要としているとする。この場合、さまざまなスレッドからの命令を優先規則に従って循環的にインタリーブさせると、これらの命令は、リソースにアクセスすることを互いに事実上妨害し、したがってプロセッサを停止させる可能性がある。
【課題を解決するための手段】
【００１１】
本発明は、データ・プロセッサにおいて複数の命令スレッドからの命令をインタリーブするための装置および方法を含む。命令は優先規則に従ってインタリーブされる。この優先規則は、それぞれのスレッドからの命令を選択し、その命令を、データ・プロセッサで処理するインタリーブされた命令ストリームに加える頻度を決定する。規則に従ってそれぞれのスレッドを選択する頻度は、命令スレッドに割り当てられた優先度に基づいて決定することができる。本発明によれば、このインタリービング・プロセスにランダム化が挿入され、その結果、任意のクロック・サイクルでの命令スレッドの選択が、優先規則だけに基づいてなされるのではなしに、ランダムまたは擬似ランダム要素にも基づいて決定される。このランダム化は、さまざまな命令スレッドから命令を選択する順序が変更され、同時に、優先規則によって設定される全体的なスレッド選択の頻度（すなわちスレッドをどのくらい頻繁に選択するか）が維持されるような方法で、命令スレッド選択プロセスに挿入される。スレッド選択プロセスにランダム化を挿入することによって、ライブ・ロック・シナリオの可能性が最小化し、優先規則によって決定されるスレッド選択の全体的な望ましい頻度が維持される。
【００１２】
優先規則とランダムまたは擬似ランダム要素の両方に基づいてスレッドを選択するスレッド選択出力は、インタリーブ規則執行構成要素とランダム化構成要素とを含む選択コントローラによって生成することができる。規則執行構成要素は、優先規則が組み込まれた基準スレッド選択出力信号を生成する。規則執行構成要素はこの基準スレッド選択出力信号をランダム化構成要素に送達する。ランダム化構成要素はランダム化を挿入して最終的な選択出力信号を生成する。したがって最終的な選択出力信号は、規則執行構成要素で確立された優先規則とランダム化構成要素によって挿入されたランダム化の両方を反映したものになる。
【００１３】
本発明は、別個の規則執行構成要素とランダム化構成要素とを使用して実施することができるが、本発明の好ましい一形態は、インタリーブ規則執行構成要素とランダム化構成要素とを結合した回路である。本発明の一形態では、結合されたこの回路が、マスクを含むスレッド選択信号を生成する。好ましい一実施態様では、マスク論理が、特定の命令スレッドに関連づけられた複数の優先度信号を使用してマスクを生成する。優先度信号は通常ソフトウェアによって生成され、優先度信号はそれぞれ、それぞれの命令スレッドに割り当てられた優先度を指示する。例えば、２つの優先度信号を使用してマスクを生成する場合には、一方の優先度信号が第１の命令スレッドの優先度を指示し、もう一方の優先度信号が第２の命令スレッドの優先度を指示する。本発明の少なくとも１つの例では、この２つの優先度信号を比較して２つの関連命令スレッドの優先度の差を求めることによってマスクが生成される。このように生成されたマスクは、両方の命令スレッドの優先度を考慮したものになり、マルチプレクサ・コントローラはこのマスクを使用して、所望の優先規則に基づくスレッド・インタリーブ比を設定することができる。
【００１４】
この結合された回路の一部である比較論理は、スレッド・インタリービング・プロセスにランダム化を挿入する。この比較論理は、乱数または擬似乱数発生器が発生させた乱数または擬似乱数を、マスク論理によって生成されたマスクと比較し、ランダム化されたマスクを生成する。このランダム化されたマスクはスレッド優先度を考慮し、同時に、処理する特定のスレッドがランダムに選択されることを保証する。
【００１５】
本発明のこれらの利点および特徴、ならびにその他の利点および特徴は、好ましい実施形態の以下の説明を添付の図面とともに検討することによって明白となろう。
【発明を実施するための最良の形態】
【００１６】
図１に、本発明の原理を具体化したプロセッサ１００を示す。プロセッサ１００はマルチスレッディングに対応し、第１の命令待ち行列１０１（Ｑｕｅｕｅ＿０）、第２の命令待ち行列１０２（Ｑｕｅｕｅ＿１）、選択マルチプレクサ（ＭＵＸ）１０５、および選択コントローラ１０６を含む。命令待ち行列１０１および１０２はそれぞれ、それぞれの命令スレッド中の命令の取扱いに携わる。具体的には、第１の命令待ち行列１０１は第１の命令スレッドＴ０からの命令を待ち行列に入れ、第２の命令待ち行列１０２は第２の命令スレッドＴ１からの命令を待ち行列に入れる。シーケンシャル・フェッチャ（sequential fetcher）１２０は、この２つの異なる命令スレッドを構成する命令群を、命令キャッシュ／メモリ管理ユニット（memorymanagement unit：ＭＭＵ）１１８から命令待ち行列１０１および１０２に転送する。命令待ち行列１０１および１０２は最終的に、それぞれの命令を選択ＭＵＸ１０５の２つの入力に供給する。選択コントローラ１０６は、この２つの異なる命令スレッドからの命令を、インタリーブされた処理のための単一の命令ストリームにインタリーブする選択ＭＵＸ１０５を制御する。
【００１７】
図２および３を参照して後に詳細に説明するとおり、それぞれの命令スレッドには優先度が割り当てられ、選択コントローラ１０６は、これらの優先度を使用して、それぞれの待ち行列（１０１または１０２）からの命令を、インタリーブされた処理ストリームに入れる頻度に関する規則を執行する。インタリーブされた命令ストリームを処理する際のライブ・ロック・シナリオを防ぐため、選択コントローラ１０６はさらに、この命令スレッド選択にランダム化を追加する。選択コントローラ１０６の出力は、スレッド選択制御経路１５４に適用される制御信号を含む。スレッド選択制御経路１５４上のこの制御信号は、後段の処理のために特定の１クロック・サイクルの間に通過させるＭＵＸ１０５の入力を指定する。ＭＵＸ１０５のそれぞれの入力は、異なるスレッドからの命令を含む命令待ち行列に結合されているので、ＭＵＸ１０５の特定の入力を選択することは、処理をおこなう特定の命令スレッドを選択する効果を有する。
【００１８】
図１に示した例示的な実施形態では、プロセッサ１００が、単一の集積回路スーパースカラ・マイクロプロセッサを含む。したがってプロセッサ１００は、さまざまな実行ユニット、レジスタ、バッファ、メモリ・デバイスおよび他の機能単位を含む。これらは全て集積回路設計によって形成される。本明細書では、マイクロプロセッサに適用するとして本発明を説明しているが、当然ながら、この選択コントローラ配置はマイクロプロセッサだけに限定されず、他のタイプのプロセッサに実装することもできる。さらに、図１に示した全体プロセッサ配置は、第１の命令待ち行列１０１、第２の命令待ち行列１０２および選択ＭＵＸ１０５に対する選択コントローラ１０６の動作を説明する際の例として示したに過ぎない。本明細書において説明し請求する選択コントローラは、複数の命令スレッドの同時処理をサポートする能力を有する実質的に任意のプロセッサ配置で利用することができることを当業者は理解されたい。
【００１９】
図１に示すプロセッサ１００は、バス・インタフェース・ユニット（ＢＩＵ）１１４およびプロセッサ・バス１１５を介してシステム・バス１１３に結合されている。システム・バス１１３およびプロセッサ・バス１１５はともに、個別に示されてはいないが、アドレス・バス、データ・バスおよび制御バスを含む。ＢＩＵ１１４はバス裁定に関与して、プロセッサ１００と、メイン・メモリ１１６、不揮発性大容量記憶装置１１７などのシステム・バス１１３に結合された他の装置との間の情報の転送を制御する。図１に示したデータ処理システムは、システム・バス１１３に結合した他の装置を含むことが好ましいが、本発明の理解にこれらの装置は不要であり、そのため無用な詳細によって本発明が不明瞭にならないようこれらは図面から除外した。
【００２０】
ＢＩＵ１１４は、命令キャッシュ／ＭＭＵ（メモリ管理ユニット）１１８およびデータ・キャッシュ／ＭＭＵ１１９に接続されている。命令キャッシュ／ＭＭＵ１１８およびデータ・キャッシュ／ＭＭＵ１１９中のキャッシュなどの高速キャッシュは、メイン・メモリ１１６から以前にキャッシュに転送されたデータまたは命令のサブセットにプロセッサ１００が相対的に高速にアクセスすることを可能にし、したがって全体的な処理速度を向上させる。それぞれデータ・キャッシュ１１９および命令キャッシュ１１８に記憶されたデータおよび命令は、メイン・メモリ１１６中のデータまたは命令の実アドレスに関係づけられた実効アドレスによって識別され、アクセスされる。
【００２１】
命令キャッシュ／ＭＭＵ１１８はさらに、シーケンシャル・フェッチャ１２０に結合されている。シーケンシャル・フェッチャ１２０は、実行する命令を、各プロセッサ・サイクルの間に命令キャッシ／ＭＭＵ１１８からフェッチする。シーケンシャル・フェッチャ１２０は、命令キャッシュ／ＭＭＵ１１８からフェッチした分岐命令を、これを実行する分岐処理ユニット（ＢＰＵ）１２１に伝送し、また、第１の命令待ち行列１０１および第２の命令待ち行列１０２中の一連の命令を一時的に記憶する。記憶された命令はいずれ、解読をする命令解読ユニット１２３、および実行ユニット１３０、１４０または１５０へのディスパッチする順序付けユニット１２４に転送される。
【００２２】
シーケンシャル・フェッチャ１２０は、第１の命令待ち行列１０１と第２の命令待ち行列１０２の両方に命令を供給する。命令待ち行列１０１および１０２はともに、後段の処理のために選択ＭＵＸ１０５を通して解読ユニット１２３に命令が発行されるたびに、その中の命令を、１つの待ち行列位置から次の待ち行列位置へシフトさせるように構成されている。第１の命令待ち行列１０１の最後の記憶要素は第１のラッチ１０３（ＬＣＨ＿０）を含み、第２の命令待ち行列１０２の最後の記憶要素は第２のラッチ１０４（ＬＣＨ＿１）を含む。ラッチ１０３および１０４は、ラッチされた命令を、選択ＭＵＸ１０５のそれぞれの入力で使用可能なように維持し、そのため、ＭＵＸの１つの入力が選択されると、選択された入力に存在する命令が命令解読ユニット１２３に転送される。なお、ラッチ１０３および１０４を含む図示のさまざまな要素は、一度に１つの命令だけを取り扱うように構成し、または複数の命令を取り扱うように構成することができることに留意されたい。本発明の好ましい一形態では、プロセッサ１００の図示のさまざまな要素が、複数の命令を同時に取り扱うことができる。例えば、命令待ち行列１０１および１０２中のそれぞれの待ち行列位置、ならびにラッチ１０３および１０４は、５つの命令を収容するのに十分な記憶要素を含むことができる。したがってこの例では、それぞれの命令スレッド（Ｔ０およびＴ１）、ならびに選択ＭＵＸ１０５の出力のインタリーブされた命令ストリームが実際に５つの命令に相当する幅を有する。本発明は、スレッドＴ０およびＴ１を通過する任意の命令幅を包含する。
【００２３】
プロセッサ１００の実行回路は、一連の命令を実行する３つの別個の実行ユニット１３０、１４０および１５０を含む。個々の実行ユニット１３０、１４０および１５０はそれぞれ、特定の実行ユニットに固有の一連のパイプライン・ステージで命令を実行することが好ましい。この例示プロセッサの第１の実行ユニット１３０（ＥＸＵ＿１）および第２の実行ユニット１４０（ＥＸＵ＿２）はともに、固定小数点数値演算および論理演算、ならびにメモリからデータをロードするロード操作を実行するように適合させることができる。プロセッサ１００の第３の実行ユニット１５０（ＥＸＵ＿３）は、複雑な固定小数点演算を実行するように適合させることができる。第３の実行ユニット１５０はさらに、メモリにデータを記憶する記憶操作を実行することができる。オペランドおよび演算結果を一時的に記憶するためにさまざまな汎用および浮動小数点レジスタが実行ユニット１３０、１４０および１５０に関連づけられていることを当業者は理解されたい。本発明の選択コントローラ配置を理解するのにこれらのレジスタの動作の理解は不要なので、図１にこれらのレジスタは示されていない。実行ユニット１３０、１４０および１５０には、命令のアウト・オブ・オーダ（out of order）実行をサポートするのに使用するさまざまな待ち行列、レジスタ、テーブルなど、他の数多くの要素を関連づけることができる。無用な詳細によって本発明が不明瞭にならないよう、これらの追加のプロセッサ要素も図１から除かれている。
【００２４】
プロセッサ１００は一連のそれぞれの命令を、別個のパイプライン・ステージ、すなわちフェッチ、解読／ディスパッチ、発行／順序付け、実行、終了および完了ステージで処理する。それぞれ２つの命令待ち行列１０１および１０２に記憶された２つのスレッドＴ０およびＴ１からの命令は、解読／ディスパッチ・ステージの直前に、選択コントローラ１０６が執行する優先規則に従って単一の命令ストリームにインタリーブされる。２つのスレッドからの命令は、解読ユニット１２３によって実行される解読／ディスパッチ・ステージの前にサイクル単位でインタリーブされるので、解読／ディスパッチ以降の各ステージは、所与のクロック・サイクルに、いずれかのスレッドから命令を受け取ることができる。例えば、所与のクロック・サイクルに、プロセッサ１００は、第１のスレッドからの命令を完了ユニット１９０で完了させ、第１または第２のスレッドからの命令を実行ユニット１３０、１４０および１５０で実行し、第２のスレッドからの命令を解読している。異なるスレッドからの命令を同時に処理することによって、一方の命令スレッドの中のある命令に関連した長い待ち時間事象によってその特定のスレッドが機能停止した場合でも、プロセッサ１００は命令を処理し続けることができる。例えば、（第１の命令待ち行列１０１に入れられた）スレッドＴ０からの命令が、この命令がすぐに処理されるのを妨げるある長い待ち時間事象を経験しているとする。（第２の命令待ち行列１０２に入れられた）第２の命令スレッドＴ１からの命令はスレッドＴ０からの命令とインタリーブされているので、第２の命令スレッドからの命令は処理され続け、第２の命令待ち行列Ｔ１を通過することができる。
【００２５】
フェッチ・ステージの間に、シーケンシャル・フェッチャ１２０は、１つまたは複数のメモリ・アドレスに関連づけられた１つまたは複数の命令を命令キャッシュ／ＭＭＵ１１８から取り出す。シーケンシャル・フェッチャ１２０は、命令キャッシュ／ＭＭＵ１１８からフェッチした一連の命令を、第１の命令待ち行列１０１に記憶して第１の命令スレッドＴ０の一部とするか、または第２の命令待ち行列１０２に記憶して第２の命令スレッドＴｌの一部とする。両方のスレッドの分岐命令はシーケンシャル・フェッチャ１２０によって抜き取られ（removed or folded out）、実行のためＢＰＵ１２１に送られる。ＢＰＵ１２１は、分岐予測機構（別個には示されていない）を含む。一実施形態では分岐予測機構が、分岐履歴テーブルなどの動的予測機構（図示せず）を含む。この分岐履歴テーブルによってＢＰＵ１２１は、分岐するかか否かを予測することによって未解決の条件付き分岐命令を推測で実行することができる。
【００２６】
第１および第２の命令待ち行列１０１および１０２を通過した２つの命令スレッドからの命令は単一の命令ストリームにインタリーブされ、後段の処理のために命令解読ユニット１２３に送達される。命令解読ユニット１２３はこれらの命令を解読し、順序付けおよび実行ユニット１３０、１４０および１５０へのディスパッチをおこなう順序付けユニット１２４に渡す。実行ユニット１３０、１４０および１５０は、順序付けユニット１２４から発行された命令を実行する。発行された命令が完全に実行されると、実行ユニット１３０、１４０および１５０は、結果があればそれを関連汎用レジスタまたは他のレジスタ（図示せず）に記憶し、さらに、命令の実行が終了したことを完了ユニット１９０に通知する。
【００２７】
図１に示した特定のプロセッサ構造は単に例示目的で示したに過ぎないこと、および本発明に基づくランダム化された指示スレッド選択はこの特定の構造とともに使用することだけに限定されないことを理解されたい。例えば、プロセッサ１００には、シーケンシャル・フェッチャ１２０が命令ストリームから抜き取った分岐命令が示されているが、別のプロセッサ構造はこの分岐命令ユニットを、他の実行ユニット１３０、１４０および１５０と一緒の別の実行ユニットとして取り扱うことができる。いずれにせよ、本発明に基づくランダム化された指示スレッド選択は、任意の同時マルチスレッド・プロセッサに組み込むことができる。
【００２８】
さらに、図示のプロセッサ１００は、２つの命令スレッドＴ０とＴ１をインタリーブして、フェッチ・ステージ後の各種プロセッサ・パイプライン・ステージで処理するインタリーブされた単一のストリームとするように適合されているが、他の実施形態では、２つ以上の命令スレッドをインタリーブして、インタリーブされた単一の命令ストリームとするように適合させることもできることに留意されたい。同時に処理している命令スレッドの数に関わらず、所与のクロック・サイクルにインタリーブされた命令ストリームに渡すことができる命令は一般に、単一のスレッドからの命令（またはパイプラインが複数の命令に相当する幅を有する場合には命令セット）だけであることに留意されたい。したがって、ＭＵＸ１０５などの選択装置を介して２つ以上のスレッドをインタリーブする場合には、装置は、ＭＵＸを通して転送する特定の１つのスレッドを選択するのに適したＭＵＸ制御信号を生成する論理を含んでいなければならない。図１に示した本発明の２スレッド形態では、信号経路１５４を通してＭＵＸ制御信号を適用することができる。しかし、２つ以上の入力を有する選択ＭＵＸに対する制御信号には、必要なＭＵＸ制御信号を収容する追加の信号経路が必要となる。
【００２９】
さらに、本発明のある実施形態は、一方または両方の命令スレッドＴ０、Ｔ１からの命令を保留し、それによって保留されたそれぞれのスレッドからの有効な命令が渡されて処理されないようにする能力を有することができることに留意されたい。この保留能力は、２つのラッチ１０３および１０４に適用された保留信号によって実装することができる。図１には、選択コントローラ１０６からそれぞれのラッチ１０３および１０４への破線１５２および１５３が示されている。保留能力が実装されている場合には、選択コントローラ１０６を使用して、必要な保留信号をそれぞれのスレッドに対して生成し、破線１５２および１５３にそれらの信号を適用することができる。
【００３０】
図２に、本発明の一形態に基づく選択コントローラ１０６を示す。選択コントローラ１０６は、２つの異なる命令スレッドのインタリービングを制御するように適合されており、ランダム化構成要素２１０に結合されたインタリーブ規則執行構成要素２０５を含んでいる。図示の選択コントローラ１０６はさらに、２つの入力２２０、２２５と、少なくとも１つの出力１５４とを含んでいる。追加の出力は、図１に関して先に論じた出力１５２および１５３に適用される保留信号を含むことができる。選択コントローラ１０６の入力は、インタリーブ中の２つのスレッドの優先度を指示する優先度信号を含む。例えばそれぞれの優先度信号は、ソフトウェアによって特定の命令スレッドに割り当てられた１から７の処理優先度を指示することができる。選択コントローラ１０６の出力１５４は、この２つのスレッドのインタリービングを制御するのに使用する制御信号を含む。選択コントローラ１０６のこれらの構成要素は、データ・プロセッサによって実行されている命令スレッドのインタリービングが、複数のスレッドから個々の命令が選択される頻度が短期的にはランダム化され、長期的には優先規則に従うような方法で実施されることを保証する。
【００３１】
インタリーブ規則執行構成要素２０５は、処理中のそれぞれの命令スレッドの優先度信号を受け取る。図２に示した実施形態では、これらの優先度信号が、入力２２０にＴ０  Ｐｒｉｏｒｉｔｙ  Ｉｎないし第１のスレッド優先度を、入力２２５にＴ１  Ｐｒｉｏｒｉｔｙ  Ｉｎないし第２のスレッド優先度を含む。本発明の好ましい一形態では、入力２２０の第１のスレッド優先度および入力２２５の第２のスレッド優先度がそれぞれ、７つの異なる優先度レベルのうちの１つを指示する３ビット論理信号を含む。インタリーブ規則執行構成要素２０５はこれらの優先度を使用して、それぞれの命令スレッドに割り当てるべきプロセッサ・タイムの部分、したがって複数の命令スレッドからの命令をインタリーブされた単一のストリームにインタリーブする頻度を決定する。例えば、２２０の第１のスレッド優先度が、第１の命令スレッドの優先度が４であることを指示し、２２５の第２のスレッド優先度が第２の命令スレッドの優先度が１であることを指示している場合、望ましい優先規則は、第１の命令スレッドの命令を、第２の命令スレッドの命令よりも高い頻度で（すなわちより頻繁に）選択してインタリーブされたストリームに入れるよう指示する。
【００３２】
インタリーブ規則は、単純な比率に従って命令をインタリーブするよう指示することができる。例えば、第１のスレッドの優先度が６、第２のスレッドの優先度が３であるとする。本発明に基づく１つのインタリーブ規則は、これらのスレッドの優先度を単純な比２対１、すなわち第１のスレッドの命令２に第２のスレッドの命令１の比に約分する。インタリーブ規則執行構成要素２０５によって執行される好ましい１つの規則は、式１／２（｜Ｘ−Ｙ｜＋１）を使用する。ただし、Ｘは第１のスレッド優先度、Ｙは第２のスレッド優先度である。優先度が高いほうのスレッドに対して優先度６、優先度が低いほうのスレッドに対して優先度３を使用するとこの式の答えは１／１６となり、これは、１６個の命令をインタリーブされたストリームに含める間に、優先度が低いほうのスレッドから１つの命令がこのストリームにインタリーブされることを意味する。本発明は、インタリーブ規則執行構成要素２０５によって執行されるこの特定の優先規則に限定されないことを理解されたい。さらに、これまでの例は、命令スレッドを１サイクル単位でインタリーブすることを含むが、インタリーブされたスレッドに他の方法でプロセッサ・タイムを割り当てる他のさまざまな優先規則を使用することができる。例えば、ある規則に従って、１サイクル単位ではなしにいくつかのサイクルごとに命令スレッドをインタリーブすることができる。
【００３３】
使用する優先規則とは無関係に、インタリーブ規則執行構成要素２０５の出力は、処理する特定のスレッドを選択するのに使用することができる出力信号を供給する。ランダム化構成要素２１０は、インタリーブ規則執行構成要素２０５から選択信号出力を入力として受け取り、次いでこれにランダム化を挿入して、ランダム化された選択信号を選択コントローラ出力１５４に生成する。ただし、全体に見れば、ランダム化構成要素２１０は、インタリーブ執行構成要素２０５が執行した優先規則を変更しない。
【００３４】
図３に、命令スレッド・インタリービング規則を執行し、インタリービング制御出力にランダム化を挿入する選択コントローラ１０６の好ましい一形態を示す。図３に示した回路は、図２に示したインタリーブ規則執行構成要素２０５の機能と図２に示したランダム化構成要素２１０の機能とを単一のインタリーブ規則執行／ランダム化回路として統合したものである。この好ましい選択コントローラ回路１０６は、入力２２０の第１のスレッド優先度信号（Ｔ０  Ｐｒｉｏｒｉｔｙ  Ｉｎ）および入力２２５の第２のスレッド優先度信号（Ｔ１  Ｐｒｉｏｒｉｔｙ  Ｉｎ）からマスクを生成するマスク論理、乱数または擬似乱数を発生させる乱数または擬似乱数発生器、乱数または擬似乱数をマスクと比較するための論理、ならびにこの比較の結果を結合してスレッド選択出力を生成するための論理を含む。
【００３５】
図３に示した選択コントローラ１０６の配置は２本のブランチ（枝）からなる。一方のブランチは、第１のスレッドＴ０および入力２２０の第１のスレッドの優先度信号に関連する。この回路１０６のブランチを第１のスレッドまたはＴ０ブランチと呼ぶ。他方のブランチは第２のスレッドＴ１および入力２２５の第２のスレッドの優先度信号に関連する。このブランチは入力２２５に関連し、第２のスレッドまたはＴ１ブランチと呼ぶ。Ｔ０ブランチとＴ１ブランチは同じ構成要素を含み、同じ機能を果たすので、特に指摘しない限り、Ｔ０ブランチを以下の議論の基礎として使用する。図３の左端を参照すると、第１のスレッド優先度信号を伝える入力２２０がラッチ３０２に結合されている。ラッチ３０２の出力は、スレッド選択制御回路１０６のブランチＴ０の入力ノード３０６に適用される。ラッチ３０２は、第１のスレッドないしＴ０スレッドの優先度が変化しない限り、その第１のスレッド優先度信号を入力ノード３０６のところにラッチする。このスレッド優先度はソフトウェアの制御の下で設定され、変更される。スレッド優先度はハードウェア制御によって変更することもできる。スレッド優先度入力のハードウェア変更は、本出願と同時に提出された「マルチスレッド・プロセッサにおいて処理する命令スレッドを選択するための方法および装置（METHOD AND APPARATUS FOR SELECTING AN INSTRUCTION THREAD FORPROCESSING IN A MULTI-THREAD PROCESSOR）」という名称の関連米国特許出願の主題である。
【００３６】
ノード３０６はエキスパンダ３１２の入力に接続されている。エキスパンダ３１２は、第１のスレッドの優先度値をビットごとに展開して、展開された優先度信号を生成する。図示の実施形態では、ノード３０６の優先度信号が、１から７までの優先度を指示する３ビットの２進化信号である。エキスパンダ３１２は、ノード３０６の３ビット信号を展開して、ノード３１３に、その優先度値に対応したいくつかのビットがセットされた７ビットの論理信号を生成する。例えば、ノード３０６の第１のスレッドの優先度が５、すなわち３ビット２進値が１０１の場合、ノード３１３の展開された７ビット信号は００１１１１１となる。第１のスレッドの優先度が３の場合、ノード３０６の３ビット論理信号は０１１、ノード３１３の展開された７ビット信号は００００１１１となる。
【００３７】
エキスパンダ３１２が、展開された７ビットの第１の優先度信号をノード３１３に生成すると、インバータ３１６が、この展開された優先度信号をビットごとに反転させ、反転された信号を、ノード３１７を介して、Ｔ１ブランチの一部であるＡＮＤゲート３２２の入力に導く。同様に第２のスレッドの優先度値を展開して展開された信号をノード３１５に生成し、この第２のスレッドの優先度信号をインバータ３１８で反転させたＴ１ブランチは、反転されたＴ１の優先度信号をノード３１９を介してＡＮＤゲート３２０の入力に導く。ＡＮＤゲート３２０は、ビットごとの論理ＡＮＤ演算を実行して、展開され反転された第２のスレッドの優先度信号と展開された第１のスレッドの優先度信号とを結合し、本明細書ではＴ０マスクと呼ぶ信号をノード３２１に生成する。ノード３２１の７ビットＡＮＤ演算の結果は、第１のスレッドの優先度値と第２のスレッドの優先度値の差を表すことに留意されたい。
【００３８】
ノード３２１の７ビット信号は、ＡＮＤゲート３２４の一方の入力およびインバータ３２８の入力に入力される。ノード３２１の信号はさらにＯＲゲート３５２の入力に結合される。ＯＲゲート３５２は、後に詳細に説明するように両方のブランチＴ０およびＴ１のＭＵＸコントローラの働きをする。ゲート３２４のもう一方の入力は、線形帰還シフト・レジスタ（ＬＦＳＲ）３３６の出力から供給される。ＬＦＳＲ３３６の出力は、１クロック・サイクルごとに生成される長さ７ビットまでの擬似乱数を含む。図３のランダム化スレッド選択制御回路１０６には、乱数または擬似乱数を発生させるＬＦＳＲ３３６が示されているが、ＬＦＳＲ３３６の代わりに他の適当な乱数または擬似乱数発生器を使用することができることを理解されたい。どんな方法で擬似乱数または乱数を発生させるにせよ、ＡＮＤゲート３２４は、この擬似乱数または乱数とノード３２１のＴ０マスクとの間のビットごとの論理ＡＮＤ演算を実行して、ランダム化されたマスク信号をノード３２５に生成する。例えば、ＬＦＳＲ３３６が発生させた擬似乱数が０００１００１、Ｔ０マスクが０００１０００である場合、ノード３２５のランダム化されたマスク信号は０００１０００となる。
【００３９】
ノード３２５のランダム化されたマスク信号は、ＯＲゲート３３２の一方の入力に入力される。インバータ３２８の出力は反転されたマスク信号をノード３２９に生成する。この信号はＯＲゲート３３２のもう一方の入力を表す。ＯＲゲート３３６の入力はともに７ビット長であることに留意されたい。ＯＲゲート３３６は、これらの２つの７ビット入力（ランダム化されたノード３２５のマスク信号および反転されたノード３２９のマスク信号）にビットごとの論理ＯＲ演算を実行し、その７ビット出力をノード３３３に適用する。このＯＲ演算の結果、反転されたＴ０マスクまたはランダム化されたＴ０マスクの特定のビット位置が論理１を含む場合、ノード３３３の信号の同じビット位置も論理１を含む。
【００４０】
図３の回路１０６はさらに、回路１０６を含むプロセッサの１クロック・サイクルごとに論理状態間を交互にトグルする１ビット論理信号を生成するトグル配置３３７を含む。トグルスイッチ配置３３７の出力はノード３３９に適用され、関連インバータ３３８によって反転されて、ノード３３９ａに１ビット信号を生成する。ノード３３９ａのこの１ビット信号はノード３３３の７ビット信号に追加され、ノード３４１に、結合ＡＮＤゲート（combining AND gate）３４０の入力となる８ビット入力が生成される。ＡＮＤゲート３４０は、ノード３４１の８ビット信号に論理ＡＮＤ演算を実行して、ノード３４５に１ビット出力を生成する。
【００４１】
図３に示した回路１０６のＴ０ブランチの議論をさらに進める前に、この回路のＴ１ブランチはＴ０ブランチと同様の回路要素を含み、入力２２５に適用された第２のスレッドの優先度信号に対して対応する演算を実行することに留意されたい。ラッチ３０４は３ビット優先度信号を保持し、エキスパンダ３０８はこの優先度値を展開してノード３１５に７ビット信号を生成する。ＡＮＤゲート３２２は、ノード３１５の７ビット信号とノード３１７の反転された７ビット信号のビットごとの論理積をとり、その７ビット出力をノード３２３に適用する。ノード３２３の信号は、入力２２５に適用した第２のスレッドの優先度の７ビット・マスクを表す。ＡＮＤゲート３２６は、ＬＦＳＲ３３６からの擬似乱数とノード３２３の信号のビットごとの論理積をとることによってランダム化された第２のスレッド・マスクを生成し、ＯＲゲート３３４で、このランダム化されたノード３２７の第２のスレッドのマスク出力とインバータ３３０からのノード３３１の反転された信号の論理和をとって、ノード３３５の７ビット信号を生成すること。ノード３３９の１ビットをノード３３５の７ビット信号に追加して、結合ＡＮＤゲート３４２の入力となる８ビット信号をノード３４３に生成する。ノード３４３で追加されるビットと、Ｔ０ブランチのノード３４１で追加されるビットとは常に逆であることに留意されたい。結合ＡＮＤゲート３４０で実行した演算と同様に、結合ＡＮＤゲート３４２はノード３４３の８ビット入力の論理積をとり、ノード３４７に１ビット出力を生成する。
【００４２】
ノード３４５の１ビット信号はＴ０ブランチのＭＵＸ３５３の一方の入力となり、ノード３４７の１ビット信号はＴ１ブランチのＭＵＸ３５５の一方の入力となる。Ｔ０ブランチＭＵＸ３５３の第２の入力は、ノード３４７の信号をインバータ３５０で反転させることによって生成された反転された信号を含む。同様に、Ｔ１ブランチＭＵＸ３５５の第２の入力は、ノード３４５の信号をインバータ３４８で反転させることによって生成された反転された信号を含む。ＯＲゲート３５２は、ノード３２１の第１のスレッドのマスク信号の論理和をとって１ビットのＭＵＸ選択信号を生成する。この信号は、ＭＵＸ３５３および３５５を制御するために適用される。ＯＲゲート３５２の出力は、第１のスレッドの優先度（入力２２０のＴ０スレッドの処理優先度）が第２のスレッドの優先度（入力２２５のＴ１スレッドの処理優先度）よりも大きいときに１になることに留意されたい。この２つの入力優先度が等しいか、または第２のスレッドの優先度が第１のスレッドの優先度よりも大きいときに、ＯＲゲート３５２の出力は０になる。このＭＵＸ選択信号は、ＭＵＸ３５３およびＭＵＸ３５５を制御して、それぞれがそれぞれの出力ノード３５４および３５６に１つの入力を接続するようにする。
【００４３】
出力ノード３５４の信号は、図１に示した選択ＭＵＸ１０５を制御するのに使用することができる２進信号を含む。したがって、ノード３５４の信号は、図１および２に示したノード１５４の選択制御信号を表す。ノード３５６の信号は、ノード３５４の信号の２進数の補数を表し、したがって、制御信号であるノード３５４の信号とともに使用される論理に関してＭＵＸの論理を単に逆にすることによって、ノード３５６の信号を、図１のスレッド選択ＭＵＸ１０５を制御する図１および２のノード１５４の制御信号として使用することもできる。
【００４４】
後に説明する実施例に示すとおり、出力３５４または３５６を使用して、２（｜Ｘ−Ｙ｜＋１）プロセッサ・クロック・サイクルに１度の割合で優先度が低いほうのスレッドを選択する命令インタリーブ規則を執行することができる。ただし｜Ｘ−Ｙ｜は、第１の命令スレッドに割り当てられた優先度値と第２の命令スレッドに割り当てられた優先度値の差の絶対値である。マスク値とＬＦＳＲ３３６で発生した擬似乱数との比較によって導入されるランダム化のため、出力ノード３５４および３５６の値はサイクルごとに予測不能に変化する。すなわち、ノード３２１または３２３のマスクがそれぞれの出力ノード３５４および３５６での値を決める場合、このランダム化によって、出力は、所望の命令インタリーブ規則に従って決定されるはずのものとは反対の出力にランダムに変化する。ただし、このランダム化によってノード３５４および３５６の最終的な出力が変更される確率と変更されない確率は同じなので、所望の命令インタリーブ規則は時間が経過しても維持される。
【００４５】
ノード３５４およびノード３５６のどちらかの信号を使用して、図１に示した第１および第２の待ち行列１０１および１０２からの命令を通過させるＭＵＸ１０５を制御することができる。図３に示した特定の回路の論理では、ノード３５４の値０によって、ＭＵＸ１０５は第１のスレッドを選択し、所与のクロック・サイクルに第１の待ち行列１０１からの１つまたは複数の命令を通過させる。ノード３５４の値１によって、ＭＵＸ１０５は、所与のクロック・サイクルに第２の待ち行列１０２からの命令を通過させる。ノード３５６の信号を使用してＭＵＸ１０５を制御する場合には、ノード３５６の値０によって、ＭＵＸ１０５は、所与のクロック・サイクルに第２の待ち行列１０２からの命令を通過させ、ノード３５６の値１によって、ＭＵＸ１０５は、所与のクロック・サイクルに第１の待ち行列１０１からの命令を通過させる。ノード３５４および３５６の信号を使用して、図１に示した１５２および１５３に適用される制御信号を生成することもできる。本明細書と同時に提出された「マルチスレッド・プロセッサにおいて処理する命令スレッドを選択するための方法および装置（METHOD AND APPARATUS FOR SELECTING AN INSTRUCTION THREAD FORPROCESSING IN A MULTI-THREAD PROCESSOR）」という名称の関連米国特許出願には、ノード３５４および３５６の信号を２つの命令待ち行列１０１および１０２の制御信号として使用する本発明の一実施形態が記載されている。
【００４６】
３つ以上の命令スレッドをインタリーブする本発明のいくつかの形態では、インタリーブされた命令ストリームにインタリーブする１つの命令スレッドを選択する追加の論理が必要であることを理解されたい。この追加の論理はいくつかの異なる方法で実装することができる。例えば、２スレッドを１組として命令スレッドを取り扱うことができる。こうすると、４つの命令スレッドをインタリーブするプロセッサでは、選択コントローラが図３に示した回路を２組使用し、追加の論理によって単一の命令スレッドの選択を執行することができる。
【００４７】
以下の実施例は、図３に示した特定の回路実装の動作のより完全な理解を提供する。
【実施例１】
【００４８】
ノード２２０の第１のスレッド優先度Ｔ０  Ｐｒｉｏｒｉｔｙ  Ｉｎが、第１のスレッドＴ０の優先度が３であることを指示し、ノード２２５の第２のスレッド優先度Ｔ１  Ｐｒｉｏｒｉｔｙ  Ｉｎが、第２のスレッドＴ１の優先度が２であることを指示していると仮定する。その場合、ノード３０６の信号は０１１、ノード３０８の信号は０１０となる。エキスパンダ３１２および３１４はこれらの信号を展開し、その結果、ノード３１３の信号は００００１１１、ノード３１５の信号は０００００１１となる。なお、この実施例では、優先度３が展開されると１が３つの７ビット信号となり、優先度２が展開されると１が２つの７ビット信号となる。インバータ３１６および３１８がこれらの信号をビットごとに反転させ、その結果、反転されたノード３１７の信号は１１１１０００となり、反転されたノード３１９の信号は１１１１１００となる。次いでＡＮＤゲート３２０がその２つの入力、すなわちノード３１３の００００１１１とノード３１９の１１１１１００のビットごとの論理ＡＮＤ演算を実行する。このビットごとの論理ＡＮＤ演算の結果、ノード３２１のＴ０マスクないし第１のスレッド・マスク信号は００００１００となる。同様にＡＮＤゲート３２２がその２つの入力、すなわちノード３１７の１１１１０００とノード３１５の０００００１１のビットごとの論理ＡＮＤ演算を実行し、その結果、ノード３２３のＴ１マスクないし第２のスレッド・マスクは０００００００となる。
【００４９】
ＬＦＳＲ３３６は、所与のクロック・サイクルに擬似乱数、例えば１１００１００を発生させ、これをＡＮＤゲート３２４の一方の入力に転送する。ＬＦＳＲ３３６によって出力された７つのビットのうち、Ｔ０マスクの論理１と同じ位置のビットだけが意味のある効果を有することに留意されたい。ＡＮＤゲート３２４のもう一方の入力は、値００００１００を有するノード３２１の信号である。ＡＮＤゲート３２４はその２つの入力信号にビットごとの論理ＡＮＤ演算を実行して、値００００１００を有する信号をノード３２５に生成する。インバータ３２８はノード３２１の信号を反転させて、ノード３２９に出力１１１１０１１を生成する。次いでＯＲゲート３３２が、ノード３２９の信号とノード３２５の信号にビットごとの論理ＯＲ演算を実行して、ノード３３３に、値１１１１１１１を有するランダム化された７ビットのマスク信号を生成する。
【００５０】
この特定のクロック・サイクルでのトグル３３７の出力が０であると仮定する。これによってインバータ３３８は１を生成する。この値１が、ランダム化された７ビットのマスク信号に追加され、ノード３４１に、ランダム化された８ビットのマスク信号１１１１１１１１が生成される。最後に、ＡＮＤゲート３４０が、ランダム化されたこの８ビット・マスクに論理ＡＮＤ演算を実行し、この８ビット比較出力を結合して値１を有する１ビット信号をノード３４５に生成する。
【００５１】
次にＴ１ブランチのノード３２３に移る。このノードは、先に説明したとおり値０００００００を保持している。ＬＦＳＲ３３６の出力値はやはり１１００１００なので、ＡＮＤゲート３２６への入力は１１００１００および０００００００となり、ノード３２７に出力０００００００が生成される。インバータ３３０はノード３３１に出力１１１１１１１を生成し、ＯＲゲート３３４が実行するビットごとの論理ＯＲ演算によって、ノード３３５に、ランダム化された７ビット・マスク信号１１１１１１１が生成される。対応するクロック・サイクルの間、トグル３３７は０にトグルされているので、ランダム化されたこの７ビット・マスク信号に０が追加されて、ノード３４１に、ランダム化された８ビット・マスク信号１１１１１１１０が生成される。最後に、ＡＮＤゲート３４２がノード３４３の８ビット比較出力信号を結合して、値０を有する１ビット信号をノード３４７に生成する。
【００５２】
ノード３４５および３４７の信号の値が決定されると、インバータ３４８および３５０が、これらの信号を反転した信号をマルチプレクサ３５３および３５５に交差結合する。この交差結合によって、ＭＵＸ３５３の両方の入力に論理１が入力され、ＭＵＸ３５５の両方の入力に論理０が入力される。ＯＲゲート３５２の入力は００００１００なのでその出力は１である。ＭＵＸ３５３および３５５の制御入力に１が置かれると、ノード３５４に１が出力され、ノード３５６に０が出力される。ノード３５４の信号とノード３５６の信号のうちの一方の信号を選択して、選択制御信号として使用することができる。
【実施例２】
【００５３】
図３に示した回路の動作を明らかにするためにＴ０スレッドの処理優先度（Ｔ０  Ｐｒｉｏｒｉｔｙ  Ｉｎ）を４と仮定する他は、以下の実施例では実施例１を踏襲する。Ｔ１スレッドの処理優先度（Ｔ１  Ｐｒｉｏｒｉｔｙ  Ｉｎ）は２のままである。これらのスレッド優先度が与えられると、ノード３０６の信号は１００、ノード３０８の信号は０１０となる。エキスパンダ３１２および３１４はこれらの信号を展開し、その結果、ノード３１３の信号は０００１１１１、ノード３１５の信号は０００００１１となる。なお、優先度４が展開されると１が４つの７ビット信号となり、優先度２が展開されると１が２つの７ビット信号となる。インバータ３１６および３１８がこれらの信号をビットごとに反転させ、その結果、反転されたノード３１７の信号は１１１００００となり、反転されたノード３１９の信号は１１１１１００となる。次いでＡＮＤゲート３２０がその２つの入力、すなわちノード３１３の０００１１１１とノード３１９の１１１１１００のビットごとの論理ＡＮＤ演算を実行する。このビットごとの論理ＡＮＤ演算の結果、ノード３２１のＴ０マスクないし第１のスレッド・マスク信号は０００１１００となる。同様にＡＮＤゲート３２２がその２つの入力、すなわちノード３１７の１１１００００とノード３１５の０００００１１のビットごとの論理ＡＮＤ演算を実行する。その結果、ノード３２３のＴ１マスクないし第２のスレッド・マスクは、実施例１と全く同じ０００００００となる。
【００５４】
比較のため、ＬＦＳＲ３３６が実施例１で使用したと同じ擬似乱数を発生させたと仮定する。したがって、ＬＦＳＲ３３６は値１１００１００を有する信号を生成し、この信号をＡＮＤゲート３２４の一方の入力に供給すると仮定する。ＡＮＤゲート３２４のもう一方の入力は、値０００１１００を有するＴ０マスクである。ＡＮＤゲート３２４はその２つの入力信号にビットごとの論理ＡＮＤ演算を実行して、実施例１と同じ値００００１００を有する信号をノード３２５に生成する。インバータ３２８はＴ０マスクを反転させて、ノード３２９に出力１１１００１１を生成する。次いでＯＲゲート３３２が、ノード３２９の信号とノード３２５の信号にビットごとの論理ＯＲ演算を実行して、ノード３３３に、値１１１０１１１を有するランダム化された７ビットのマスク信号を生成する。ＬＦＳＲ３３６が発生させた擬似乱数の第３および第４ビット位置によって追加されたランダム化のために、この実施例ではノード３３３に、実施例１とは異なる信号が生成されることに留意されたい。ＬＦＳＲ３３６からの擬似乱数の第３および第４ビット位置がともに１であれば、ノード３３３の結果は１１１１１１１となる。
【００５５】
トグル配置３３７の出力が実施例１と同じく０であると仮定する。これによってインバータ３３８は反転されたトグル・ビット１を生成する。この反転されたトグル・ビットが、ランダム化された７ビットのＴ０マスク信号に追加されて、ノード３４１に、ランダム化された８ビットのＴ０マスク信号１１１０１１１１が生成される。最後に、ＡＮＤゲート３４０が、ランダム化されたこの８ビット・マスクに論理ＡＮＤ演算を実行し、この８ビット比較出力を結合して値０を有する１ビット信号をノード３４５に生成する。この値を、ノード３４５の信号の値が１である実施例１と比べられたい。
【００５６】
この回路のＴ１ブランチは、第２のスレッド優先度に関して対応する演算を実行する。ＬＦＳＲ３３６がやはり値１１００１００の擬似乱数を発生させると仮定すると、ＡＮＤゲート３２６の入力は１１００１００と０００００００となる。ノード３２７のＡＮＤゲート３２６の出力は実施例１と同じ０００００００である。インバータ３３０はノード３３１に出力１１１１１１１を生成する。ＯＲゲート３３４が実行するビットごとの論理ＯＲ演算によって、ノード３３５に、ランダム化された７ビット・マスク信号１１１１１１１が生成される。トグル３３７の出力は０なので、ランダム化されたこの７ビットＴ１マスク信号７に０が追加されて、ノード３４１に、ランダム化された８ビットＴ１マスク信号１１１１１１１０が生成される。最後に、ＡＮＤゲート３４２がノード３４３の８ビットＴ１比較出力信号を結合して、論理値０を有する１ビット信号をノード３４７に生成する。
【００５７】
ノード３４５および３４７の信号の値が決定されると、インバータ３４８および３５０が、これらの信号を反転した信号をマルチプレクサ３５３および３５５に交差結合する。ＭＵＸ３５３の両方の入力が論理１、ＭＵＸ３５５の両方の入力が論理０である実施例１とは違い、このケースでは、ＭＵＸ３５３の入力１が０、ＭＵＸ３５３の入力０が１、ＭＵＸ３５５の入力１が１、ＭＵＸ３５５の入力０が０である。このケースでは、ＯＲゲート３５２の入力が０００１１００であり、実施例１のＯＲゲート３５２の入力とは異なる。しかし入力は異なっても出力は同じ１となり、これがＭＵＸ３５３および３５５の制御入力に適用される。ＭＵＸ３５３および３５５の制御入力に１が置かれると、ＭＵＸはその１入力をノード３５４または３５６に接続する。その結果、ノード３５４には０が置かれ、ノード３５６には１が置かれる。これは実施例１の結果とは正反対であることに留意されたい。このように、実施例１に比べて実施例２のほうが第１の命令スレッドの優先度が高く、したがって、実施例１と同じ命令スレッドが選択されると予測される場合であっても、マスクとＬＦＳＲ３３６からの擬似乱数の比較によって導入されるランダム化によって、スレッド選択の結果は実施例１とは異なってくる。
【００５８】
以上の実施例および図３に示した回路の説明から、回路のそれぞれのブランチが適当な出力を生成して所望のインタリーブ比を執行することに留意されたい。ただし、ブランチＴ０とＴ１からなる並行構造のブランチはそれぞれ、Ｔ０とＴ１の値が等しくない場合のインタリーブ比の代替の可能性を計算する。Ｔ０がＴ１よりも大きい場合、またはＴ１がＴ０よりも大きい場合の２つの可能性がある。ＭＵＸ３５３および３５５によって提供される最終的なＭＵＸ選択によって、より大きな優先度値を有するスレッドが執行されたインタリーブ比でより頻繁に選択される。スレッド選択をランダム化し、同時に所望のインタリーブ規則を全体として維持する本発明の方法は、この特定の並行ブランチ回路に限定されないことを理解されたい。本発明は、図３に示すような並行ブランチ回路を使用するか否かに関わらず所望のインタリーブ規則の範囲内でスレッド選択をランダム化する任意の回路、または所望のスレッド選択信号を生成する並行ブランチを含まない回路を包含する。
【００５９】
以上に記載した好ましい実施形態は、本発明の原理を説明することを意図したものであり、本発明の範囲を限定しようとするものではない。当業者であれば、上記請求項の範囲から逸脱することなく、他のさまざまな実施形態およびこれらの好ましい実施形態に対するさまざまな変更が可能である。例えば、図示の論理および他の回路は、開示の発明を実現する方法の具体的な例を提供するが、開示の回路は正または負論理で実現することもできる。さらに、異なる組合せの論理ゲートを使用して同じ結果を得ることができ、このような変更は開示の構造と等価であるとみなされるべきである。多数の異なる配置を使用して、所望のランダム化をスレッド選択方法に挿入し、または異なるスレッド間の選択を実施することができる。
【００６０】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００６１】
（１）データ・プロセッサにおいて複数の命令スレッドを処理する方法であって、
（ａ）第１の命令スレッドからの命令と少なくとも１つの追加の命令スレッドからの命令を、前記第１の命令スレッドと前記少なくとも１つの追加の命令スレッドの間の優先規則に従ってインタリーブする段階と、
（ｂ）前記インタリービング段階にランダム化を挿入し、同時に前記優先規則を維持する段階と
を含む方法。
（２）命令をインタリーブする前記段階がサイクル単位で実施される、上記（１）に記載の方法。
（３）優先規則に従って命令をインタリーブする前記段階が、処理するスレッドを指示するスレッド選択信号を生成する段階を含む、上記（１）に記載の方法。
（４）ランダム化を挿入する前記段階が、前記スレッド選択信号をランダム化する段階を含む、上記（３）に記載の方法。
（５）前記スレッド選択信号をランダム化する前記段階が、
（ａ）前記第１の命令スレッドに関連づけられた第１のスレッド優先度信号および追加の命令スレッドにそれぞれ関連づけられたそれぞれの追加のスレッド優先度信号から、マスクを生成する段階と、
（ｂ）乱数または擬似乱数を発生させる段階と、
（ｃ）前記マスクと前記乱数または擬似乱数とを比較して、ランダム化されたマスクを生成する段階と
を含む、上記（４）に記載の方法。
（６）命令をインタリーブする前記段階が、
（ａ）前記マスクを反転させて反転されたマスクを生成する段階と、
（ｂ）前記ランダム化されたマスクと前記反転されたマスクを比較する段階と
を含む、上記（５）に記載の方法。
（７）データ・プロセッサにおいて、処理する命令を複数の命令スレッドから選択する際に使用するスレッド選択出力を生成する方法であって、
（ａ）前記複数の命令スレッドに関連づけられ、前記複数の命令スレッドのそれぞれのスレッドの優先度を指示する優先度信号からマスクを生成する段階と、
（ｂ）前記マスクと比較するのに適した乱数または擬似乱数を発生させる段階と、
（ｃ）前記マスクと前記乱数または擬似乱数を比較してランダム化されたマスクを生成する段階と、
（ｄ）前記ランダム化されたマスクから前記スレッド選択出力を生成する段階と
を含む方法。
（８）マスクを生成する前記段階が、第１の優先度信号を第２の優先度信号と比較する段階を含む、上記（７）に記載の方法。
（９）第１の優先度信号を第２の優先度信号と比較する前記段階の前に、前記第１の優先度信号および前記第２の優先度信号のうちの一方を反転させる段階をさらに含む、上記（８）に記載の方法。
（１０）乱数または擬似乱数を発生させる前記段階が線形帰還シフト・レジスタを用いて実行される、上記（７）に記載の方法。
（１１）マスクを生成する前記段階の前に前記優先度信号をビットごとに展開する段階をさらに含む、上記（７）に記載の方法。
（１２）前記ランダム化されたマスクから前記スレッド選択出力を生成する前記段階がさらに、
（ａ）前記マスクを反転させて反転されたマスクを生成する段階と、
（ｂ）前記ランダム化されたマスクと前記反転されたマスクを比較する段階と
を含む、上記（７）に記載の方法。
（１３）前記ランダム化されたマスクと前記反転されたマスクの前記比較の結果を結合する段階をさらに含む、上記（１２）に記載の方法。
（１４）前記ランダム化されたマスクと前記反転されたマスクの前記比較の結果に、プロセッサのクロック・サイクル周波数で論理レベルが変化するトグル・ビットを結合する段階をさらに含む、上記（１３）に記載の方法。
（１５）同時マルチスレッド・プロセッサにおいて、処理する命令を選択する際に使用するスレッド選択出力を生成する回路であって、
（ａ）前記マルチスレッド・プロセッサ内の第１の命令スレッドのスレッド優先度を指示する第１の優先度信号、および前記マルチスレッド・プロセッサ内の追加の命令スレッドのスレッド優先度を指示する追加の優先度信号を受け取り、前記第１の優先度信号のマスクを生成するマスク論理と、
（ｂ）前記マスクと比較するのに適した乱数または擬似乱数を発生させる乱数発生器と、
（ｃ）前記マスク論理および前記乱数発生器に結合され、前記マスクと前記乱数または擬似乱数とを比較してランダム化されたマスクを生成する比較論理と、
（ｄ）前記比較論理に結合され、前記ランダム化されたマスクから前記スレッド選択出力を生成する結合論理と
を含む回路。
（１６）前記マスク論理が、前記第１の優先度信号を、前記追加の優先度信号の反転された値を表す反転された優先度信号と比較する優先度信号比較器を含む、上記（１５）に記載の回路。
（１７）前記マスク論理が、前記第１の優先度信号を展開して展開された第１の優先度信号を生成する第１のエキスパンダと、前記追加の優先度信号を展開して展開された追加の優先度信号を生成する第２のエキスパンダとを含む、上記（１５）に記載の回路。
（１８）前記結合論理が、
（ａ）反転されたマスクを生成するマスク・インバータと、
（ｂ）前記ランダム化されたマスクと前記反転されたマスクを比較して比較出力を生成するマスク比較器と
を含む、上記（１５）に記載の回路。
（１９）前記結合論理が、前記比較出力のビットに論理ＡＮＤ演算を実行する結合ＡＮＤ装置を含む、上記（１８）に記載の回路。
（２０）トグル・ビットを発生させ、前記トグル・ビットを前記比較出力に追加するトグル・ビット発生器をさらに含み、前記トグル・ビットが、前記結合ＡＮＤ装置が実行する前記論理ＡＮＤ演算に含まれる、上記（１９）に記載の回路。
（２１）同時マルチスレッド・プロセッサにおいて、処理する命令を選択する際に使用するスレッド選択出力を生成する回路であって、
（ａ）インタリーブ規則執行出力を生成するインタリーブ規則執行構成要素と、
（ｂ）前記インタリーブ規則執行出力を受け取り、前記同時マルチスレッド・プロセッサ内の複数の命令スレッド間のスレッド選択を制御するランダム化されたスレッド選択出力を生成するランダム化構成要素と
を含む回路。
【図面の簡単な説明】
【００６２】
【図１】本発明の原理を具体化した命令インタリービング配置を使用したプロセッサのブロック図である。
【図２】本発明の原理を具体化したスレッド選択コントローラのブロック図である。
【図３】図２に示したスレッド選択コントローラのインタリーブ規則執行要素とランダム化要素とを結合した回路の概略図である。
【符号の説明】
【００６３】
１００  プロセッサ
１０１  第１の命令待ち行列
１０２  第２の命令待ち行列
１０３  第１のラッチ
１０４  第２のラッチ
１０５  選択マルチプレクサ
１０６  選択コントローラ
１１３  システム・バス
１１４  バス・インタフェース・ユニット
１１５  プロセッサ・バス
１１６  メイン・メモリ
１１７  不揮発性大容量記憶装置
１１８  命令キャッシュ／メモリ管理ユニット
１１９  データ・キャッシュ／メモリ管理ユニット
１２０  シーケンシャル・フェッチャ
１２１  分岐処理ユニット
１２３  命令解読ユニット
１２４  順序付けユニット
１３０  実行ユニット
１４０  実行ユニット
１５０  実行ユニット
１５２  保留信号経路
１５３  保留信号経路
１５４  スレッド選択制御経路
１９０  完了ユニット
２０５  インタリーブ規則執行構成要素
２１０  ランダム化構成要素
２２０  選択コントローラの入力
２２５  選択コントローラの入力
３０２  ラッチ
３０４  ラッチ
３１２  エキスパンダ
３１４  エキスパンダ
３１６  インバータ
３１８  インバータ
３２０  ＡＮＤゲート
３２２  ＡＮＤゲート
３２４  ＡＮＤゲート
３２６  ＡＮＤゲート
３２８  インバータ
３３０  インバータ
３３２  ＯＲゲート
３３４  ＯＲゲート
３３６  線形帰還シフト・レジスタ
３３７  トグル
３３８  インバータ
３４０  ＡＮＤゲート
３４２  ＡＮＤゲート
３４８  インバータ
３５０  インバータ
３５２  ＯＲゲート
３５３  マルチプレクサ
３５５  マルチプレクサ
【図１】
2004326767.tif 000003
【図２】
2004326767.tif 000004
【図３】
2004326767.tif 000005