(57)【特許請求の範囲】
【請求項１】
命令を処理するための複数の実行ユニットと、実行用の命令を前記実行ユニットのうちの１つに割り当てるための命令デコードおよび発行ロジックとを備えるプロセッサであって、前記プロセッサが、
後続の命令間のレジスタ・アクセス競合を解決するための制御ロジックと、
依存関係キャッシュと
を備え、前記依存関係キャッシュが、
前記命令が実行されることが予定されている実行ユニットを示す実行ユニット・インジケータを前記制御ロジックから受信するための受信ロジックと、
前記受信された実行ユニット・インジケータを格納するために前記受信ロジックに応答する格納ロジックと、
命令用の前記格納された実行ユニット・インジケータを提供するために前記命令デコードおよび発行ロジックからの要求に応答する取得ロジックと
を備え、
前記命令デコードおよび発行ロジックが、前記依存関係キャッシュに命令用の実行ユニット・インジケータを要求し、前記依存関係キャッシュから受信された前記実行ユニット・インジケータに応じて、前記命令を前記実行ユニットのうち対応する１つに割り当てるように構成される、プロセッサ。
【請求項２】
前記制御ロジックがスコアボード制御ロジックである、請求項１に記載のプロセッサ。
【請求項３】
前記依存関係キャッシュの前記格納ロジックも、前記予定された命令に応じて、命令用のインジケータを格納するように構成される、請求項１に記載のプロセッサ。
【請求項４】
命令の実行完了時に、前記命令と依存関係のある命令が認識される、請求項１に記載のプロセッサ。
【請求項５】
前記依存関係キャッシュが、前記認識された命令の依存関係を記録するように構成される、請求項４に記載のプロセッサ。
【請求項６】
前記依存関係キャッシュが、プロセッサのプログラム実行時間または消費電力が減少するように、最適な実行ユニットまたはプロセッサ・コアまたはプロセッサ・スライスまたはプロセッサ・パイプラインを選択するためのユニット選択モジュールを備える、請求項１に記載のプロセッサ。
【請求項７】
前記格納ロジックに書き込むために、前記依存関係キャッシュ内のエントリのアドレスが、第１のマッピング・ユニットによって決定される、請求項１に記載のプロセッサ。
【請求項８】
前記格納ロジックから読み取るために、前記依存関係キャッシュ内のエントリのアドレスが、第２のマッピング・ユニットによって決定される、請求項１に記載のプロセッサ。
【請求項９】
プロセッサを使用して命令を処理するための方法であって、前記プロセッサが実行用の命令を前記実行ユニットのうちの１つに割り当てるための命令デコードおよび発行ロジックを備え、前記方法が、
制御ロジックによって、後続の命令間のレジスタ・アクセス競合を解決するステップと、
依存関係キャッシュを提供するステップと、
前記制御ロジックから、前記依存関係キャッシュで、前記命令が実行されることが予定されている前記実行ユニットを示す実行ユニット・インジケータを受信するステップと、
前記受信された実行ユニット・インジケータを前記依存関係キャッシュに格納するステップと、
前記命令デコードおよび発行ロジックによって、命令用の前記実行ユニット・インジケータを前記依存関係キャッシュに要求するステップと、
命令用の前記格納された実行ユニット・インジケータを前記依存関係キャッシュから取得するステップと、
前記命令を、前記依存関係キャッシュから受信された前記実行ユニット・インジケータに応じて前記実行ユニットのうち対応する１つに割り当てるステップとを含む、方法。
【請求項１０】
前記制御ロジックがスコアボード制御ロジックとして実装される、請求項９に記載の方法。
【請求項１１】
前記予定された命令に応じて、命令用のインジケータを格納することも含む、請求項９に記載の方法。
【請求項１２】
命令の実行完了時に、前記命令の依存関係のある命令を認識するステップをさらに含む、請求項９に記載の方法。
【請求項１３】
前記認識された命令の依存関係を記録するステップをさらに含む、請求項１２に記載の方法。
【請求項１４】
プログラム実行時間が減少するように、最適な実行ユニットまたはプロセッサ・コアまたはプロセッサ・スライスまたはプロセッサ・パイプラインを選択するステップをさらに含む、請求項９に記載の方法。
【請求項１５】
前記格納ロジックに書き込むために、前記依存関係キャッシュ内のエントリのアドレスを、第１のマッピング・ユニットによって決定するステップをさらに含む、請求項９に記載の方法。
【請求項１６】
前記格納ロジックから読み取るために、前記依存関係キャッシュ内のエントリのアドレスを、第２のマッピング・ユニットによって決定するステップをさらに含む、請求項９に記載の方法。
【請求項１７】
請求項９〜１６のいずれかに記載の方法をプロセッサに実行させる、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にプロセッサに関し、より詳細には、命令を処理するための複数の実行ユニットを備えるプロセッサ、実行用の命令を実行ユニットのうちの１つに割り当てるための命令デコードおよび発行ロジック（instruction decode and issue logic）に関する。さらに、本発明は、プロセッサおよび設計構造を使用して命令を処理するための方法に関する。
【背景技術】
【０００２】
現在、プロセッサ（例えば、スーパースカラ・プロセッサ）は、スーパースカラ・プロセッサ内の複数の並列実行ユニットを使用できるため、１つのプロセッサ・サイクルの間に、複数の命令の並列実行を可能にする。一般に、このメカニズムによってプロセッサの性能が向上する。同じサイクル内で複数の命令を並列実行パイプラインに発行できる場合もある。しかし、２つの連続する命令は、互いに依存することがある。つまり、後の命令が先行する命令の結果を必要とする場合がある。したがって、後の命令のスケジューリングまたはディスパッチは、先行する命令が終了するのを待機する必要がある。これとは無関係に、異なる実行ユニットへの命令の発行は、特別な依存関係を反映することなく実行され得る。
【０００３】
従来の方法は、依存関係のある命令間の距離を最大化しようとする。最初に、アルゴリズムとプログラムは、基礎になるハードウェアに最も適合するように再設計される場合がある。しかし、この再設計は、非常に高価になる可能性があり、ソフトウェアを実行する必要のあるプロセッサ・アーキテクチャごとに再実行する必要がある。加えて、ソース・コードがすでに使用不可能になっている場合があり、また関連費用が発生するため、ユーザは自分のシステムを再コンパイルして再認証することを望まない。仮想マシン（ＶＭ）を使用する仮想環境またはマルチスレッド環境では、他のスレッドがそのような単一スレッドの最適化を無効にする場合がある。マルチスレッドまたはＶＭ（仮想マシン）環境では、同じコア上で他に何かが実行されるのを予測し、ハードウェア・リソースを得るために争うのは極めて困難であるため、どのような静的最適化も無効化される可能性がある。
【０００４】
一方、トランジスタ処理デバイスの性能および単一スレッドの性能は、物理的制限のため飽和しつつあるが、ムーアの法則は適用され、「シリコンの縮小」が続いている。したがって、さらに多くの回路を１つのチップ上に集積することができ、例えば並列実行ユニットを使用して命令ストリームの実行を並列化することができ、そのため、命令当たりの平均サイクル数を減らすことができる。並列性は、命令間の依存性に制限される。すなわち、１つの命令の結果が、後続の依存関係のある命令によって必要とされる場合があるため、複数の命令を任意に並列化することはできない。性能を最大化するには、個々の実行ユニットの結果を他の実行ユニットに転送する必要がある。プロセッサ設計者にとって、これは、配線の問題または転送経路上の追加サイクル遅延をもたらす。現在、使用可能な配線スタックが、相互接続されるユニットの数（つまり、性能の向上）を制限する可能性があり、統合のギャップを埋めるために、設計上の大きな労力が生じる場合がある。プロセッサ設計において、多くの金属層は、それらが使用できたとしても、極めて高価になる。
【０００５】
３番目に、依存関係検出範囲を伴うハードウェアの最適化が試みられてきた。しかし、そのようなアプローチでは、多くの追加ハードウェアが必要になり、限定的な結果しか得られない。必要な追加ハードウェア要素は、通常、指数関数的に増大する。静的依存関係検出範囲は、同程度に小さくすることができ、動的依存関係検出は存在しなくてもよい。
【０００６】
加えて、ユニットからユニットへの転送待ち時間は、プロセッシング・ユニットに必要な総面積が増えるに従って増加する。データを段階分けする必要があり、その結果、離れたユニット上で依存関係のある命令が実行された場合、性能が低下する。
【０００７】
コンパイラの最適化が、もう１つの選択肢になる可能性がある。その場合、プロセッサ・アーキテクチャごとにソース・コードを再コンパイルする必要がある。この場合も、ソース・コードが必要になる。また、この方法は、仮想環境およびマルチスレッド実行に対してあまり堅牢ではないことがあり、可変の依存関係の転送待ち時間を扱わない場合がある。
【０００８】
現在使用可能な技術の選択肢は、例えば文献米国第５，８０２，３８６号に記載されている。この文献は、スケジュールされる命令のオペランドとして必要とされる前の命令の結果が使用可能になったときに、最初のプロセッサ・サイクルの開始の識別に基づいて、命令が、実行のために効率的、静的にスケジュールされるということを開示している。命令の処理のための格納されたプロセッサ・サイクル識別を調べて、命令が実行可能になったときの最も早いプロセッサ・サイクルを明らかにする。
【０００９】
別の文献（米国第５，８３５，７４５号）は、命令ボックスを含んでいるパイプライン・プロセッサを開示している。この命令ボックスは、命令のセットのレジスタ・オペランド・フィールドをマッピングするためのレジスタ・マッパ、および命令プロセッサからの設定命令の発行を静的に並べ替えるための、命令のセットごとに適合される命令スケジュールを含んでいる。マッピングされるレジスタ・オペランド・フィールドは、命令の発行の前に、並べ替えられた命令のセットのうちの対応する命令と関連付けられる。
【００１０】
しかし、これらのアプローチも、実行時（例えば、アドレス計算が実行される時）またはプロセッサの複数実行ユニット環境内のマルチスレッドなどの動的環境においてのみ認識できる依存関係の問題を解決できない。したがって、複数の実行ユニットを備えるプロセッサの場合、複数の依存関係のある命令について、命令のディスパッチを最適化する必要がある。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】米国第５，８０２，３８６号
【特許文献２】米国第５，８３５，７４５号
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明の課題は、このような必要性に対処し、命令を処理するための複数の実行ユニットを備えるプロセッサ、プロセッサを使用して命令を処理するための方法、およびプロセッサの設計プロセスにおいて使用される設計構造を提供することである。
【課題を解決するための手段】
【００１３】
この必要性は、独立した特許請求の範囲に従って、命令を処理するための複数の実行ユニットを備えるプロセッサ、およびプロセッサを使用して命令を処理するための方法によって対処できる。
【００１４】
本発明の１つの態様によれば、命令を処理するための複数の実行ユニットを備えるプロセッサ、実行用の命令を実行ユニットのうちの１つに割り当てるための命令デコードおよび発行ロジックを提供できる。このプロセッサは、後続の命令間のレジスタ・アクセス競合を解決するための制御ロジックおよび依存関係キャッシュを備えることができる。
【００１５】
この依存関係キャッシュは、命令の実行を予定することができる実行ユニットを示す実行ユニット・インジケータを制御ロジックから受信するための受信ロジックと、受信された実行ユニット・インジケータを格納するために受信ロジックに応答する格納ロジックと、命令用の格納された実行ユニット・インジケータを提供するために命令デコードおよび発行ロジックからの要求に応答する取得ロジックとを備えることができる。命令デコードおよび発行ロジックは、依存関係キャッシュに命令用の実行ユニット・インジケータを要求し、依存関係キャッシュから受信された実行ユニット・インジケータに応じて命令を実行ユニットのうち対応する１つに割り当てるように構成できる。
【００１６】
本発明の別の態様によれば、プロセッサを使用して命令を処理するための方法を提供できる。プロセッサは、実行用の命令を実行ユニットのうちの１つに割り当てるための命令デコードおよび発行ロジックを備えることができる。この方法は、制御ロジックによって後続の命令間のレジスタ・アクセス競合を解決することと、依存関係キャッシュを提供することとを含むことができる。
【００１７】
さらに、この方法は、制御ロジックから依存関係キャッシュで、命令が実行されることが予定されている実行ユニットを示す実行ユニット・インジケータを受信することと、受信された実行ユニット・インジケータを依存関係キャッシュに格納することと、命令デコードおよび発行ロジックによって、命令用の実行ユニット・インジケータを依存関係キャッシュに要求することとを含むことができる。要求後に、この方法は、命令用の格納された実行ユニット・インジケータを依存関係キャッシュから取得することと、依存関係キャッシュから受信された実行ユニット・インジケータに応じて命令を実行ユニットのうち対応する１つに割り当てることとを含むことができる。
【００１８】
本発明のさらに別の態様によれば、命令を処理するための複数の実行ユニットを備えるプロセッサの設計プロセスにおいて使用される、機械可読記憶媒体内で有形に具現化された関連する設計構造、ならびに実行用の命令を実行ユニットのうちの１つに割り当てるための命令デコードおよび発行ロジックを提供できる。
【００１９】
制御ロジックがスコアボード制御ロジックとして実装されてもよいということに注意する。
【００２０】
本発明の実施形態が、さまざまな対象を参照して説明されるということに注意する必要がある。具体的には、一部の実施形態は、方法タイプの請求項を参照して説明され、他の実施形態は装置タイプの請求項を参照して説明されている。ただし、当業者は、前述の説明および以下の説明から、特に注記のない限り、対象の１つの種類に属している特徴の任意の組合せに加えて、異なる対象に関連する特徴間、具体的には、方法タイプの請求項の特徴と、装置タイプの請求項の特徴との間の任意の組合せも、本文書内で開示されると見なされるということを推測するであろう。
【００２１】
上で定義された態様および本発明のその他の態様は、以下に記載された実施形態の例から明らかになり、実施形態の例を参照して説明されるが、本発明はこれらに限定されない。
【００２２】
単なる例として、以下の図面を参照して本発明の好ましい実施形態について説明する。
【図面の簡単な説明】
【００２３】
【図１】異なる実行ユニット上の基本的な従来のラウンドロビン命令実行と共に命令ストリームを示す図である。
【図２】実行ユニットのユニット０、ユニット１、およびユニット２への同じ命令の最適化された発行と共に同じ命令ストリームを示す図である。
【図３】依存関係キャッシュを含んでいる本発明のアーキテクチャの概要を示す図である。
【図４】図３の他のプロセッサ・コンポーネントの文脈における依存関係キャッシュの第１の実装の拡張されたバージョンを示す図である。
【図５】依存関係キャッシュの代替の実装を示す図である。
【図６】依存関係キャッシュの更新に関して、フローチャートの形態で提案された概念を示す図である。
【図７】命令の依存関係を認識したスケジューリングのフローチャートを示す図である。
【発明を実施するための形態】
【００２４】
この説明の文脈では、以下の規則、用語、または表現あるいはこれらの組合せを使用できる。
【００２５】
「プロセッサ」という用語は、単一のプロセッサ（例えば、スーパースカラ・プロセッサ）内で命令レベル並列性と呼ばれる並列性の形態を作る複数のプロセッシング・ユニットが実装されているＣＰＵ（central processing units）を示すことができる。したがって、このプロセッサは、所与のクロック・レートで可能になる平均実行スループットよりも速い平均実行スループットを可能にすることができる。プロセッサは、複数の命令をプロセッサ上の異なる機能ユニットに同時にディスパッチすることによって、１クロック・サイクルの間に複数の命令を実行できる。各機能ユニットは、別々のＣＰＵコアではなく、算術論理演算ユニット、ビット・シフタ、または乗算器などの単一のＣＰＵ内の実行リソースである。このような概念をスーパースカラ・プロセッサ内で実現できる場合でも、提案された概念は、その他の種類のプロセッサ内でも機能できる。
【００２６】
「実行ユニット」という用語は、説明されたように、個別のユニットまたはプロセッサの一部である機能ユニットを示すことができる。複数の実行ユニットが、１つのプロセッサ内に存在することができ、それらはすべて並列で動作するように構成される。これらのユニットは、同一であってもなくてもよい。
【００２７】
「命令デコードおよび発行ロジック」という用語は、実行されるコマンドまたは命令を受信できる、プロセッサの一部としてのユニットを示すことができる。命令デコードおよび発行ロジックは、命令を受信すると、次に、命令を構成要素（例えば、命令自体、データまたはアドレスあるいはその両方、あるいはその他のパラメータ）にデコードすることができ、その後、コマンドまたはコマンドの一部をプロセッサ内の関連する実行ユニットに発行することができる。
【００２８】
「制御ロジック」という用語は、プロセッサ内で並列に使用可能な実行ユニット間で競合が発生しないことを保証するためのロジックを示すことができる。制御ロジックは、スコアボード・ロジックとして実装されてもよい。
【００２９】
「レジスタ・アクセス競合」という用語は、複数のプロセッシング・ユニットを備えるプロセッサにおいて使われる場合がある。命令のストリーム内の個々の命令は、互いに独立していないことがある。命令Ａ（命令ストリーム内で後方に位置付けられている）は、別の命令Ｂに依存する場合がある。そのため、Ａが実行されるには、まずＢが終了する必要がある場合がある。したがって、これらの命令は、受信された命令ストリームの順序で実行される必要がある。しかし、他の命令は、互いに完全に独立しているため、受信された命令ストリームと比較した場合に、逆の順序で実行されてもよい。つまり、これらの命令は、「異なる順序で」実行されてもよい。そのため、このような決定を可能にするメカニズムが、プロセッサ内に存在する必要がある。前の段落で定義された制御ロジックは、このような決定を引き受けることができる。
【００３０】
「依存関係キャッシュ」という用語は、プロセッサの一部としての新しい要素を示すことができる。具体的には、このプロセッサは、従来技術と比較して性能向上を実現するために、異なる使用可能なプロセッシング・ユニットへの命令または命令の一部の発行を最適化するのに役立つ。
【００３１】
「格納ロジック」という用語は、この出願の文脈においては、ストレージの位置を示すことができる。具体的には、このストレージの位置は、所与の命令が実行された実行ロジックを特定するインジケータを格納するための依存関係キャッシュの一部である。このようにして、すでに実行された命令に対して依存関係のある命令も、同じ実行ユニットまたは定義された他の実行ユニット上で実行できることを保証するために、特定の命令が実行された実行ユニットを再び取得することができる。
【００３２】
「取得ロジック」という用語は、次のようなロジックとして説明できる。つまり、プロセッサを通る命令のフローを最適化するために、命令が実行された実行ユニットを取得するためのロジックである。このようにして、ある命令とその後の命令（相互に依存している命令）との間で、実行ユニットの切り替えを防ぐことができる。これによって、貴重な処理時間を節約することができ、性能を向上させることができる。
【００３３】
「依存関係キャッシュ」という用語は、複数のタスクに役立つロジックを示すことができる。依存関係ロジックの実装の詳細は、図の説明の一部として下で示されている。ただし、依存関係キャッシュの機能の１つは、命令ストリームの一部として命令用のインジケータを格納することであり、複数の同一の実行ユニットまたは多様な実行ユニットを含む環境内で実行される。実行ユニットは、例えば、固定小数点実行ユニット、浮動小数点実行ユニット、または同じ命令を実行できるプロセッサの一部または２つの異なるユニットとして２回以上実装できる任意のその他の特別な実行ユニットであってもよい。
【００３４】
実行用の命令を実行ユニットのうちの１つに割り当てるために命令デコードおよび発行ロジックを備える複数の実行ユニットを含んでいる提案されたプロセッサは、いくつかの利点および技術的効果を提供することができる。
【００３５】
依存関係キャッシュを使用すると、プロセッサ環境において、従来の命令発行技術を大幅に上回る性能向上を可能にすることができる。プロセッサは、命令のストリームを実行しながら（つまり、既存の変更されていないソフトウェア・コードを実行しながら）、静的および動的な命令の依存関係を学習できる場合がある。学習した内容は、保存することができ、後の時点で、同じ依存関係が再び発生した場合に再利用することができる。したがって、コードが再び実行されるときに（例えば、プログラム・ループ内で）、ある実行ユニットから別の実行ユニット（最終的に、幾何学的に遠く離れた実行ユニット）への転送待ち時間を減らし、プロセッサの全体的性能を向上させるために、依存関係のある命令を、同じ実行ユニットまたは近接した実行ユニットに再び発行することができる。
【００３６】
プロセッサの好ましい実施形態によれば、制御ロジックは、スコアボード制御ロジックであってもよい。スコアボード制御ロジックは、マルチプロセッシング・ユニット環境内の依存関係のある命令を記録（keeping track）するのに役立ち、異なる順序でのスケジューリングおよび命令の発行をサポートすることができる。
【００３７】
プロセッサの有利な一実施形態によれば、依存関係キャッシュの格納ロジックは、予定された命令に応じて命令用のインジケータを格納するように構成させることもできる。このようにして、命令が繰り返し依存している場合、計算ループにおいてインジケータを取得することができる。固有のプロセッシング・ユニットへのスケジューリングは、最適化された方法で実行できる。
【００３８】
プロセッサの好ましい実施形態によれば、ある命令の実行完了時に、その命令の依存関係のある命令を認識できる。そのため、この認識に従って、次の命令を関連するプロセッシング・ユニットに発行またはスケジューリングすることができる。したがって、プロセッサのその他の有利な実施形態によれば、依存関係キャッシュを、認識された命令の依存関係を記録する（tracking）ように構成させることができる。
【００３９】
プロセッサのその他の有利な一実施形態によれば、依存関係キャッシュは、一連の依存関係のある命令を終了するために必要なサイクル数を減らし、それによってプロセッサの並列性を最適化することにより、プログラム実行時間を削減できるように、最適な実行ユニットまたはプロセッサ・コアまたはプロセッサ・スライスまたはプロセッサ・パイプラインを選択するためのユニット選択モジュールを備えることができる。
【００４０】
プロセッサのその他の実施形態によれば、依存関係キャッシュ内のエントリのアドレスは、第１のマッピング・ユニットによって決定できる。これは、ユニット・インジケータを格納ロジックに書き込む目的で、第１のハッシュ・ユニットによって実行することもできる。
【００４１】
それに応じて、プロセッサの別の許容される実施形態によれば、依存関係キャッシュ内のエントリのアドレスは、プロセッシング・ユニットのインジケータを格納ロジックから読み取るために、第２のマッピング・ユニットによって決定される。また、この第２のマッピング・ユニットは、プロセッシング・ユニットのインジケータを格納するための依存関係キャッシュ・テーブルへの高速アクセス用のハッシュ・ユニットとして実装できる。
【００４２】
設計構造のオプションの一実施形態によれば、設計構造は、プロセッサを表すネットリストを含むことができる。このネットリストは、ＳＲＡＭセルのメモリ・セル配置用の自動生産システムに必要になる場合がある。
【００４３】
設計構造の別のオプションの実施形態によれば、設計構造は、テスト・データ、特性評価データ、検証データ、または設計仕様の少なくとも１つのセットを含む。
【００４４】
以下では、各図について詳細に説明する。図内のすべての命令は概略図である。最初に、命令を処理するための複数の実行ユニットを備える本発明のプロセッサの実施形態に対して効果を比較するために、既存のスケジューリング方法および発行方法のブロック図について説明する。その後、その他の実施形態およびプロセッサを使用して命令を処理するための方法の実施形態について説明する。
【００４５】
図１に、異なる実行ユニット上の基本的な従来のラウンドロビン命令実行と共に命令ストリーム１００を示す。命令のストリーム１００は、複数の命令１０２、…、１２０を含んでいる。複数の依存関係が矢印で示されている。例えば、命令１０６は命令１０２に依存し、命令１０８は命令１０６に依存し、命令１１６は命令１０８に依存している。一方、命令１１０は命令１０４に依存し、命令１１６は命令１１０に依存している。したがって、命令１１６は命令１０８と命令１１０の両方に依存している。命令１２０は命令１１６に依存している。このように、命令ストリーム１００の例には、さまざまな命令の依存関係が存在している。
【００４６】
これらの依存関係は、実行ユニット０  １２２、実行ユニット１  １２４、および実行ユニット２  １２６に関して、異なる種類の実線および破線によっても示されている。図からわかるように、１０個の命令１０２、…、１２０は、９サイクルで実行できる。命令１２０は、元の直線的命令ストリーム１００の命令１１８と同じレベルでユニット０（１２２）において実行されるように示されている。したがって、従来のアーキテクチャにおいて性能向上が達成されるが、ある実行ユニットの結果をその実行ユニットから別の実行ユニットに転送する必要があるというように、異なる実行ユニット０、１、２間に依存関係が存在している。そのため、実行ユニットおよび命令の依存関係が調整される場合、改善の余地がある。
【００４７】
図２に、本発明の概念に従う実行ユニット０（１２２）、ユニット１（１２４）、およびユニット２（１２６）への同じ命令の最適化された発行と共に同じ命令ストリーム１００を示す。図からわかるように、依存関係のある命令１０２、１０６、１０８、１１６、１２０は、実行ユニット０（１２２）上で実行される。これらの命令は、１サイクルごとに順番に実行される。依存関係のある命令１０４および１１０の第２の部分的ストリームが、並行して、できるだけ早く開始されて、実行ユニット１（１２４）上で実行される。実行ユニット１（１２４）の結果が、依存関係のある命令の異なる部分的ストリーム（ここでは、実行ユニット０（１２２）上で実行される）と組み合わせて必要になった時点でのみ、１つの部分的実行ストリームの結果を、ある実行ユニットから別の実行ユニットに（具体的には、ユニット１からユニット０に）転送する必要がある。
【００４８】
依存関係のない残りの命令１１２、１１４、１１８は、実行ユニット２（１２６）上で、順序が異なる方法で、他の部分的に依存関係のある命令とは無関係に実行できる。
【００４９】
その結果、命令ストリーム１００の１０個の命令１０２、…、１２０は、従来のスケジューリング手法における９プロセッサ・サイクルではなく、５プロセッサ・サイクルの後に実行を終了できた。これは、従来の命令ディスパッチ・アルゴリズムと比較して、明白な性能的利点を示している。
【００５０】
図３に、依存関係キャッシュを含んでいる本発明のアーキテクチャの概要を示す。プロセッサは、複数の実行ユニット０〜ｎ（つまり、１２２〜３０８）を備えることができる。これらの実行ユニットは、図１および図２の実行ユニット０、１、および２を備えることができる。図１および図２の命令ストリーム１００などの命令ストリームは、スコアボード・ロジックの形態で実装できる制御ユニット３０６と共に命令デコードおよび発行ユニット３０２に入ることができる。スコアボード・ロジック３０６と依存関係キャッシュ３００の両方が、デコードおよび発行ユニット３０２と連携して動作する。
【００５１】
図４に、図３の他のプロセッサ・コンポーネントの文脈における依存関係キャッシュ３００の拡張されたバージョンを示す。依存関係終了ロジック４０４は、スコアボード３０６から少なくとも２つの入力値を受信することができる（４０２）。それらの入力値は、終了または中止する処理に応じて、アドレスまたはユニット番号４２２、およびアドレスまたは命令の種類あるいはその両方である。「命令」および「処理」という用語は、この文書の文脈では、交換可能な用語として使用できることに注意する。
【００５２】
依存関係キャッシュの機能を最適に説明するために、標準的な一連のステップを次のように説明できる。命令デコードおよび発行ユニット３０２から発行される命令の命令アドレスを使用して、依存関係キャッシュ３００にアクセスし、命令を発行する先、つまり実行ユニットを検出する。このために、命令デコードおよび発行ユニット３０２は、発行される命令のアドレスを依存関係発行制御ロジック４１６を介して第２のマッピング・ユニット４１４（ハッシュ・ユニットとして実装できる）に送信し（４３２）、命令を実行する必要のある実行ユニットのアドレスを依存関係キャッシュ・テーブル４１２から読み取る。ハッシュ／マッピング・ユニット４１４を使用して、依存関係キャッシュ・テーブル４１２にアクセスするためのアドレスを絞り込むことができる。
【００５３】
次に、依存関係キャッシュ３００は、実行ユニット識別子を、ユニット選択モジュール４２０を介して依存関係キャッシュ・テーブル４１２から命令デコードおよび発行ロジック３０２に返す（４２８）。依存関係発行制御ロジック４１６は、パラメータとして発行される命令の種類を使用して、ユニット選択モジュール４２０に影響を与える（４３０）。
【００５４】
命令が終了すると、スコアボードによってフラグが立てられた、今終了した命令の結果を待機しているすべての命令（つまり、依存関係のある命令の依存関係のある処理）を考慮できる。これらの命令ごとに、依存関係のある命令のアドレス４２４（スコアボードから取得される）が使用され、依存関係終了制御ロジック４０４を介して依存関係キャッシュ３００にアクセスする。具体的には、ハッシュ・モジュールとして実装できるユニット・マッピング・モジュール４０６および第１のマッピング・ユニット４１０を介して依存関係キャッシュ・テーブル４１２にアクセスする。ユニット・マッピング・モジュール４０６は、コンピュータ命令４２６のすべての依存関係のある命令に関して、近接した実行ユニットをターゲットにすることができる。この文脈では、「近接した」という用語は、実行ユニット間での短い配線（つまり、短い待ち時間）を保証するために、プロセッサ・チップ上で幾何学的に近いということを意味することができる。
【００５５】
依存関係のある命令の種類に基づいて、依存関係キャッシュ３００（具体的には、依存関係のある処理に関する依存関係キャッシュ・テーブル４１２のエントリ）を更新するために、終了した命令に最も近いユニットが選択される。等しいプロセッシング・ユニットまたは実行ユニットを備えるプロセッサ・チップの場合、依存関係のある命令が開始された実行ユニットは、その命令が終了した実行ユニットに一致するということに注意する。
【００５６】
図５に、依存関係キャッシュ３００の代替の実装または拡張された実装を示す。ユニットまたはモジュール依存関係終了制御ロジック４０４、第１のマッピング・ユニット４１０、第２のマッピング・ユニット４１４、依存関係発行制御ロジック４１６、およびユニット・マッピング・モジュール４２０は、図４の文脈で説明されたのと同じ方法で基本的に動作する。例えば、ユニット・マッピング・モジュール４２０は、発行される命令に使用される実行ユニット番号または実行ユニットの識別子（依存関係キャッシュ・テーブル４１２から受信される（５０４））を、命令デコードおよび発行ユニット３０２に返送する（５０８）。図４の文脈で説明された他の既知のプロセッサ・ユニットから、命令デコードおよび発行ユニット３０２のみが図５に示されているが、他のすべてのユニットも、本発明の概念のこの拡張された実装において使用できるということに注意する。
【００５７】
ただし、依存関係キャッシュ・テーブル４１２は、発行された命令用の実行ユニット識別子への並列なエントリを持つことができる。第２の並列な列５０２は、最も若い依存関係のある命令のアドレスに使用される。最も若い依存関係５０６のアドレスは、依存関係発行制御ロジック４１６の追加入力として使用される。ユニット・マッピング・モジュール４２０の出力が依存関係発行制御ロジック４１６へのフィードバック・ループであることにも注意する。
【００５８】
この実施形態では、前の依存関係のある命令を検出するために、命令デコードおよび発行ユニット３０２から発行される命令の命令アドレスが使用されて、依存関係キャッシュ３００にアクセスする。これも、依存関係発行制御ロジック４１６および第２のマッピング・ユニット４１４を介して実行される。前と同じマッピング／ハッシュ・アルゴリズムを使用して、命令アドレスを狭いアドレスに変換し、依存関係キャッシュ・テーブル４１２、５０２にアクセスできる。
【００５９】
最も若い依存関係のある命令のアドレスを使用して（５０６）、前の依存関係のある命令の命令アドレスが使用され、依存関係キャッシュ・テーブル４１２、５０２に再びアクセスし、依存関係のある命令が発行されたユニットを読み出す。依存関係キャッシュ・テーブル４１２、５０２は、例えば２０ビット幅であってもよいことに注意する。ただし、このビット数はプロセッサのアーキテクチャに依存する場合がある。
【００６０】
次に、依存関係キャッシュ・テーブル４１２、５０２は、ユニット・マッピング・モジュール４２０を介して実行ユニット識別子を返し、命令を発行することができる。依存関係キャッシュ・テーブル４２０、５０２内に、エントリごとに有効ビットが存在してもよい。この有効ビットが設定された場合、ユニット・マッピング・モジュール４２０は、例えばランダム／ラウンドロビン・ユニット・アルゴリズムを使用してユニットを選択できる。偽信号のため、選択された実行ユニットは、特定の種類の命令を実行できない場合がある。ただし、有効ビットが設定されていない場合にも同じことが発生することがある。
【００６１】
その後、ユニット・マッピング・モジュール４２０、依存関係発行制御ロジック４１６、および第２のマッピング・ユニット４１４を使用して書き込みアクセスを実行し、命令のエントリを更新し、命令の発行先になる実行ユニット識別子を含む依存関係キャッシュ・テーブル４１２内のアドレスを発行できる。
【００６２】
この実施形態において命令が終了すると、スコアボードによってフラグが立てられた、その結果を待機しているすべての命令（つまり、依存関係のある命令）が考慮される（上と比較されたい）。これらの命令ごとに、依存関係のある命令のアドレスが使用されて、上で説明されたように、発行される命令と同様の方法で、依存関係終了制御ロジック４０４および第１のマッピング・ユニット４１０を介して依存関係キャッシュにアクセスする。この場合、終了する命令の命令アドレスを、第１のマッピング・ユニットを介して、依存関係キャッシュ・テーブル４１２、５０２の列５１２に書き込むことができる。
【００６３】
図６に、依存関係キャッシュの更新に関するフローチャート６００の形態で、提案された概念を示す。命令実行の終了から、フローが開始される（６０２）（命令が完了する）。次に、依存関係のある命令が存在するかどうかが判定される（６０４）。「いいえ」の場合、更新を実行することはできない。「はい」の場合、依存関係のある命令のアドレスが依存関係キャッシュ・テーブル４１２内にすでに存在するかどうかが判定される（６０６）。「はい」の場合、現在の依存関係がより若いかどうかが判定される（６０８）。「いいえ」の場合、プロセスは、依存関係のある命令が存在するかどうかの判定６０４に戻る。「はい」の場合、依存関係が依存関係キャッシュ・テーブル４１２に追加される。
【００６４】
依存関係のある命令が依存関係キャッシュ内にすでに存在するかどうかの判定６０６が「いいえ」の場合、プロセスはステップ６１０に真っすぐ進み、ここで、依存関係が依存関係キャッシュ・テーブル４１２に追加される。その後、プロセスは、依存関係のある命令が存在するかどうかの判定６０４に戻る。
【００６５】
図７に、命令の依存関係を認識したスケジューリングのフローチャートを示す。命令の事前スケジューリングから入って、命令アドレスが依存関係キャッシュ３００（具体的には、依存関係キャッシュ・テーブル４１２）内に存在するかどうかの判定７０２を実行できる。「はい」の場合、依存関係のある命令がすでに完了したかどうかを判定できる（７０４）。「いいえ」の場合、依存関係のある命令の実行ユニットを特定できる（７０６）。次に、依存関係のある命令のユニットに基づいて最も良く適合する実行ユニットを決定できる（７０８）。この決定は、命令間での実行ユニットの変更の数、レジスタ内の内容の再利用、実行ユニット間の幾何学的距離などを最小にすることに基づくことができる。最後に、命令の発行またはスケジューリングあるいはその両方を行うことができる（７１２）。
【００６６】
判定７０２が「いいえ」の場合で、かつ判定７０４が「はい」の場合、プロセスは、現在の命令に最適な実行ユニットを決定するための決定処理７１０を実行する。この処理は、例えばランダム選択アルゴリズムまたはラウンドロビン・アルゴリズムを使用して実行できる。この決定処理の実行後、プロセスは命令のスケジューリング／発行を実行する（７１２）。
【００６７】
本発明のさまざまな実施形態の説明は、例示の目的で提示されているが、網羅的であることは意図されておらず、開示された実施形態に制限されない。説明された実施形態の範囲および主旨を逸脱することなく多くの変更および変形が、当業者にとって明らかとなる。本明細書で使用された用語は、実施形態の原理、実際の適用、または市場で見られる技術を超える技術的改良を最も適切に説明するため、または他の当業者が本明細書で開示された実施形態を理解できるようにするため選択されている。
【００６８】
本発明は、システム、方法、またはコンピュータ・プログラム製品あるいはこれらの組合せとして具現化されてもよい。コンピュータ・プログラム製品は、プロセッサに本発明の態様を実行させるためのコンピュータ可読プログラム命令を含んでいるコンピュータ可読記憶媒体を含んでもよい。
【００６９】
この媒体は、電気、磁気、光、電磁気、赤外線、または伝搬媒体用の半導体システムにしてもよい。コンピュータ可読媒体の例は、半導体メモリまたは固体メモリ、磁気テープ、取り外し可能コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ：andom accessmemory）、読み取り専用メモリ（ＲＯＭ：read-only memory）、剛体磁気ディスク、および光ディスクを含んでもよい。光ディスクの現在の例は、コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：compact disk-read only memory）、コンパクト・ディスク読み取り／書き込み（ＣＤ−Ｒ／Ｗ：compact disk-read/write）、ＤＶＤ、およびブルーレイディスクを含む。
【００７０】
コンピュータ可読記憶媒体は、命令実行デバイスによって使用するための命令を保持および格納できる有形のデバイスにしてもよい。コンピュータ可読記憶媒体は、例えば、電子ストレージ・デバイス、磁気ストレージ・デバイス、光ストレージ・デバイス、電磁ストレージ・デバイス、半導体ストレージ・デバイス、またはこれらの任意の適切な組合せにすることができるが、これらに限定されない。コンピュータ可読記憶媒体のさらに具体的な例の非網羅的リストは、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ：random access memory）、読み取り専用メモリ（ＲＯＭ：read-onlymemory）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭ：erasableprogrammable read-only memoryまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ：static random access memory）、ポータブル・コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：portable compact disc read-only memory）、デジタル多用途ディスク（ＤＶＤ：digital versatile disk）、メモリ・スティック、フロッピー（Ｒ）・ディスク、パンチカードまたは命令が記録されている溝の中の隆起構造などの機械的にエンコードされるデバイス、およびこれらの任意の適切な組合せを含む。本明細書において使用されているコンピュータ可読記憶媒体は、本質的に、電波またはその他の自由に伝搬する電磁波、導波管またはその他の送信媒体を伝搬する電磁波（例えば、光ファイバ・ケーブルを通過する光パルス）、あるいはワイヤを介して送信される電気信号などの一時的信号であると解釈されるべきではない。
【００７１】
本明細書に記載されたコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体から各コンピューティング・デバイス／処理デバイスへ、またはネットワーク（例えば、インターネット、ローカル・エリア・ネットワーク、広域ネットワーク、または無線ネットワークあるいはこれらの組合せ）を介して外部コンピュータまたは外部ストレージ・デバイスへダウンロードすることができる。このネットワークは、銅伝送ケーブル、光伝送ファイバ、無線送信、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、またはエッジ・サーバあるいはこれらの組合せを備えてもよい。各コンピューティング・デバイス／処理デバイス内のネットワーク・アダプタ・カードまたはネットワーク・インターフェイスは、コンピュータ可読プログラム命令をネットワークから受信し、それらのコンピュータ可読プログラム命令を各コンピューティング・デバイス／処理デバイス内のコンピュータ可読記憶媒体に格納するために転送する。
【００７２】
本発明の処理を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、マシン命令、マシン依存命令、マイクロコード、ファームウェア命令、状態設定データ、あるいは、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同様のプログラミング言語などの従来の手続き型プログラミング言語を含む１つまたは複数のプログラミング言語の任意の組合せで記述されたソース・コードまたはオブジェクト・コードにしてもよい。コンピュータ可読プログラム命令は、ユーザのコンピュータ上で全体的に実行すること、ユーザのコンピュータ上でスタンドアロン・ソフトウェア・パッケージとして部分的に実行すること、ユーザのコンピュータ上およびリモート・コンピュータ上でそれぞれ部分的に実行すること、あるいはリモート・コンピュータ上またはサーバ上で全体的に実行することができる。後者のシナリオでは、リモート・コンピュータを、ローカル・エリア・ネットワーク（ＬＡＮ：local area network）または広域ネットワーク（ＷＡＮ：wide areanetwork）を含む任意の種類のネットワークを介してユーザのコンピュータに接続することができ、または接続を、（例えば、インターネット・サービス・プロバイダを使用してインターネットを介して）外部コンピュータに対して行うことができる。一部の実施形態では、本発明の態様を実行するために、例えばプログラマブル論理回路、フィールドプログラマブル・ゲート・アレイ（ＦＰＧＡ：field-programmable gate arrays）、またはプログラマブル・ロジック・アレイ（ＰＬＡ）を含む電子回路は、コンピュータ可読プログラム命令の状態情報を利用することによって、電子回路をカスタマイズするためのコンピュータ可読プログラム命令を実行できる。
【００７３】
本発明の態様は、本明細書において、本発明の実施形態に記載された方法、装置（システム）、およびコンピュータ・プログラム製品のフローチャート図またはブロック図あるいはその両方を参照して説明される。フローチャート図またはブロック図あるいはその両方の各ブロック、ならびにフローチャート図またはブロック図あるいはその両方に含まれるブロックの組合せは、コンピュータ可読プログラム命令によって実装できると理解されるであろう。
【００７４】
これらのコンピュータ可読プログラム命令は、コンピュータまたはその他のプログラマブル・データ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて規定された機能／動作を実装するための手段を構築するように、汎用コンピュータ、専用コンピュータ、またはその他のプログラマブル・データ処理装置のプロセッサに提供されて、マシンを生成するものであってよい。これらのコンピュータ可読プログラム命令は、命令が格納されたコンピュータ可読記憶媒体が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて規定された機能／動作の態様を実装する命令を含む製品を備えるように、コンピュータ可読記憶媒体に格納され、コンピュータ、プログラマブル・データ処理装置、またはその他のデバイスあるいはこれらの組合せに特定の方法で機能するよう指示するものであってもよい。
【００７５】
コンピュータ可読プログラム命令は、コンピュータ、その他のプログラマブル装置、または別のデバイス上で実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて規定された機能／動作を実装するように、コンピュータ実装プロセスを生成すべく、コンピュータ、その他のプログラマブル・データ処理装置、あるいは別のデバイスにロードされ、コンピュータ、その他のプログラマブル装置、またはその他のデバイス上で一連の動作ステップを実行させるものであってもよい。
【００７６】
図内のフローチャートまたはブロック図あるいはその両方は、本発明のさまざまな実施形態に記載されているシステム、方法、およびコンピュータ・プログラム製品の可能な実装のアーキテクチャ、機能、および処理を示す。これに関連して、フローチャートまたはブロック図内の各ブロックは、規定された論理機能を実装するための１つまたは複数の実行可能な命令を備える、命令のモジュール、セグメント、または部分を表すことができる。一部の代替実装では、ブロックに示された機能は、図に示された順序とは異なる順序で発生させることができる。例えば、連続して示された２つのブロックは、実際には、含まれている機能に応じて、実質的に同時に実行されるか、または場合によっては逆の順序で実行されてもよい。ブロック図またはフローチャート図あるいはその両方の各ブロック、ならびにブロック図またはフローチャート図あるいはその両方に含まれるブロックの組合せは、規定された機能または動作を実行するか、または専用ハードウェアとコンピュータ命令の組合せを実行する専用ハードウェアベースのシステムによって実装できるということにも注意する。
【００７７】
本明細書で使用される用語は、特定の実施形態を説明することのみを目的としており、本発明を制限することを意図していない。本明細書で使用される単数形「ａ」、「ａｎ」、「ｔｈｅ」は、文脈で特に明示的に示されない限り、複数形も含むことが意図されている。「備える（ｃｏｍｐｒｉｓｅ）」または「備えている（ｃｏｍｐｒｉｓｉｎｇ）」あるいはその両方の用語は、本明細書で使用される場合、記載された機能、整数、ステップ、処理、要素、または構成要素あるいはそれらの組合せの存在を示すが、１つまたは複数のその他の機能、整数、ステップ、処理、要素、構成要素、またはこれらのグループあるいはそれらの組合せの存在または追加を除外していないとさらに理解されるであろう。
【００７８】
下の特許請求の範囲内のすべてのミーンズまたはステップ・プラス・ファンクション要素の対応する構造、材料、動作、および均等なものは、具体的に特許請求されるその他の特許請求される要素と組み合わせて機能を実行するための任意の構造、材料、または動作を含むことが意図されている。本発明の説明は、例示および説明の目的で提示されているが、網羅的であることは意図されておらず、開示された形態での発明に限定されない。本発明の範囲および主旨を逸脱することなく多くの変更および変形が、当業者にとって明らかとなる。本発明の原理および実際的な適用を最も適切に説明するため、およびその他の当業者が、企図されている特定の用途に適しているようなさまざまな変更を伴う多様な実施形態に関して、本発明を理解できるようにするために、実施形態が選択されて説明された。
【符号の説明】
【００７９】
１００  命令ストリーム
１０２  命令
１０４  命令
１０６  命令
１０８  命令
１１０  命令
１１２  命令
１１４  命令
１１６  命令
１１８  命令
１２０  命令
１２２  ユニット
１２４  ユニット
１２６  ユニット
３００  依存関係キャッシュ
３０２  命令デコードおよび発行ユニット
３０６  スコアボード
３０８  ユニット
４０２  データ
４０４  依存関係終了ロジック
４０６  ユニット・マッピング・モジュール
４１０  第１のマッピング・ユニット
４１２  依存関係キャッシュ・テーブル
４１４  第２のマッピング・ユニット
４１６  依存関係発行制御ロジック
４２０  ユニット・マッピング・モジュール
４２２  データ
４２４  データ
４２６  データ
４２８  データ
４３０  データ
４３２  データ
５０２  依存関係キャッシュ・テーブル
５０４  データ
５０６  データ
５０８  データ
６００  フローチャート
６０２  ステップ
６０４  ステップ
６０６  ステップ
６０８  ステップ
６１０  ステップ
７０２  ステップ
７０４  ステップ
７０６  ステップ
７０８  ステップ
７１０  ステップ
７１２  ステップ
【図１】
0006744199.tif 000002
【図２】
0006744199.tif 000003
【図３】
0006744199.tif 000004
【図４】
0006744199.tif 000005
【図５】
0006744199.tif 000006
【図６】
0006744199.tif 000007
【図７】
0006744199.tif 000008