(57)【要約】【課題】  本発明が解決すべき課題とするところは、将来予想される配線遅延を克服すること等である。【解決手段】  並列に動作する複数のクラスタを有するプロセッサにおいて、使用されるクラスタの数は動的に変わり得る。各プログラムフェーズの開始で、インターバルのための構成オプションが最適な構成を決定するために実行される。これは、次のフェーズ変化が検出されるまで用いられる。該最適な命令インターバルは、最小インターバルで始めて、ある低安定率が達成されるまでそれを倍加することにより決定される。【選択図】  図１
2008502083.tif 000002
【特許請求の範囲】
【請求項１】
複数のクラスタを備えるプロセッサを操作する方法であって、
（ａ）前記プロセッサ上でプログラムを操作するために前記クラスタの最適数を決定するステップと、
（ｂ）前記プロセッサから前記最適数のクラスタに対してのみ命令を送るステップと、
を備えたことを特徴とするプロセッサ操作方法。
【請求項２】
ステップ（ａ）は、該プログラムの操作中複数回行われることを特徴とする請求項１記載の方法。
【請求項３】
ステップ（ａ）は、該プログラムにおける複数のフェーズの各々の開始時に行われることを特徴とする請求項２記載の方法。
【請求項４】
ステップ（ａ）は、
（ｉ）該フェーズの各々において複数のインターバルを定義するステップと、
（ｉｉ）該複数のインターバルの少なくとも１つからプログラム統計を検出するステップと、
（ｉｉｉ）該プログラム統計から該クラスタの該最適数を決定するステップと、
を備えたことを特徴とする請求項３記載の方法。
【請求項５】
ステップ（ａ）（ｉ）は、インターバルの長さを選択するステップを備えることを特徴とする請求項４記載の方法。
【請求項６】
該インターバルの該長さは、予め定められた初期インターバル長で開始し、安定性閾値に届くか又は予め定められた最大インターバル長に届くまで該予め定められたインターバル長を増加することにより選択されることを特徴とする請求項５記載の方法。
【請求項７】
ステップ（ａ）は、
（ｉ）該フェーズの各々において複数のインターバルを定義するステップと、
（ｉｉ）該インターバルの最初のもののときに、利用可能な離れた命令レベル並列性の程度を検出するステップと、
（ｉｉｉ）該利用可能な離れた命令レベル並列性の程度から該クラスタの該最適数を決定するステップと、
を備えたことを特徴とする請求項３記載の方法。
【請求項８】
ステップ（ａ）は、Ｎを整数として、全てのＮ番目の分岐で行なわれることを特徴とする請求項７記載の方法。
【請求項９】
ステップ（ａ）は、全てのサブルーチンのコール及びリターンで行なわれることを特徴とする請求項７記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連する出願への言及）
本願は、２００４年６月８日に出願された米国仮特許出願第６０／５７７，６０７号の利益を主張するものであり、その開示は参照によりここにその全体が本願に取り入れられる。
【０００２】
（政府持分に関する陳述）
本発明へと至った研究は、ＮＳＦの助成ＥＩＡ−００８０１２４、ＣＣＲ−９８１１９２９、ＣＣＲ−９９８８３６１、ＣＣＲ−０２１９８４８及びＥＣＳ−０２２５４１３によって、ＡＦＲＬ契約Ｆ２９６０１−００−Ｋ−０１８２の下のＤＡＲＰＡ／ＩＴＯによって、並びに共同合意第ＤＥ−ＦＣ０３−９２ＳＦ１９４６０号の下で米国エネルギー省慣性閉じ込め核融合オフィスによって、一部支援されたものである。米国政府は本発明に一定の権利を有する。
【０００３】
（発明の技術分野）
本発明は、クラスタ化されたプロセッサの操作を処理する方法に関し、より詳細にはクラスタ化されたプロセッサにおける通信並列性トレードオフを動的に処理する方法に関する。
【背景技術】
【０００４】
現代のプロセッサ上の一般的アプリケーションから大量の命令レベル並列性（ＩＬＰ：ｉｎｓｔｒｕｃｔｉｏｎ−ｌｅｖｅｌ  ｐａｒａｌｌｅｌｉｓｍ）を抽出するには、発行キュー、レジスタファイル、キャッシュ、及び分岐予測器のような、多くの機能ユニットと大きなオンチップ構造を使用することが必要である。ＣＭＯＳプロセス技術が先細るにつれて、（論理遅延と比較すると）配線遅延が支配的になる。このことは、より高速のクロックスピードを志向する絶間なきトレンドと相俟って、通常のオンチップ構造（キャッシュ、レジスタファイル等）にアクセスするためのサイクル時間を増加させる。また、これは、サイクル当り命令（ＩＰＣ：ｉｎｓｔｒｕｃｔｉｏｎｓ  ｐｅｒ  ｃｙｃｌｅ）の性能を低下させるだけでなく、アクセスを複数のパイプラインステージへ分割する際に様々な設計問題を提示する。設計者に利用可能なトランジスタが増加の一途を辿っているにも拘らず、設計複雑性を高めることなく、クロックスピードを抑えることなく、且つ将来のプロセス技術におけるスケーラビリティを制限することなくＩＬＰ抽出を助ける大きな単一構造を設計することは益々困難になっている。
【０００５】
これらの設計課題に対する潜在的な解決策は、クラスタ化されたマイクロアーキテクチャである。そこでは、主要なプロセッサ資源が複数のクラスタにわたって分散され、それらの各々が発行キュー、レジスタファイル及び機能ユニットからなるサブセットを含む。かかる設計においては、リネーム命令時に、各命令はクラスタの１つにステアリングされる。発行キューとレジスタファイルのサイズ要件及びバンド幅要件を減少させる結果、これらのサイクル時間クリティカル構造に係るアクセス時間は大幅に削減され、これによって高速クロックが可能となる。これらの構造の単純化もまた、それらの設計複雑性を削減する。
【０００６】
クラスタ化マイクロアーキテクチャの魅力的な特徴は、次世代プロセッサを生産する際の設計労力が削減されるということである。１つのクラスタの設計が非常に簡素化されるだけでなく、１つのクラスタコアが一度設計されたならば、トランジスタ・バジェットが増えたときに、これらのコアの多くを（増加するフロントエンドのバンド幅を含め）低設計コストでプロセッサに加えることができる。各プログラムは共働する多くの資源を有するので、より多くのクラスタを加えることはＩＰＣ性能を潜在的に改善するであろう。クロックスピード上の何れもがこれを行うことから変わらないならば、各々別個のクラスタの実現は変わらないので、効果は殆どない。加えて、大きなクラスタ化プロセッサにおける資源を単一スレッドによって効果的に用いることができないとしても、複数のスレッドをクラスタ化プロセッサ上にスケジューリングすることで全体的命令スループットを著しく増加することができる。相対的に低い設計複雑性とスレッドレベル並列性を活用するポテンシャルとは、何十億ものトランジスタの時代における高度にクラスタ化されたプロセッサを非常に魅力的な選択肢とする。
【０００７】
クラスタ化マイクロアーキテクチャの主要な欠点は、同一資源を備えた単一体設計と比べた場合の削減されたＩＰＣである。単一クラスタ内の依存命令は逐次サイクルにおいて発行することができるが、余分なクラスタ間バイパス遅延は異なったクラスタに存在する依存命令が逐次サイクルにおいて発行することを妨げる。単一サイクルが全機能ユニット間をバイパスするのを可能とするために単一体プロセッサが潜在的に十分遅いクロックを使うかもしれない一方で、クラスタ化プロセッサはより高速のクロックを許容し、これによって機能ユニットの内の幾つかの間のサイクルに追加的レイテンシを導入する。ＩＰＣ低下がクロックスピードの向上を相殺しない場合のみ、クラスタ化設計は実行可能な選択肢である。
【０００８】
０．３５μテクノロジでのアルファ２１２６４のような現代のプロセッサは、既に限定的にクラスタ化された設計を使用しており、そこでは整数ドメインは、たとえば、２つのクラスタへ分割されている。最近の多くの研究は、クラスタへ命令をステアリングするために、ヒューリスティクスの設計を探究してきた。これらの進歩にも拘らず、これらの研究による成果は、次の理由により近い将来に恐らく再考されなければならないであろう。
【０００９】
１．配線遅延の増大支配と増加クロックスピードのトレンドとにより、各クラスタコアにおける資源は、従来の研究で想定されたものと比べ、大幅に削減される必要があるであろう。
【００１０】
２．大きなトランジスタ・バジェットとスレッドレベル並列性を活用する潜在的可能性とにより、従来の研究で想定されたものよりも多くのクラスタがダイ上に存在するであろう。
【００１１】
３．最も遠く離れた２クラスタ間でデータを通信するためのサイクル数は、配線遅延問題のため増加するであろう。さらに、通信遅延は、異質的となり、生産者及び消費者ノードの位置に従って変化するであろう。
【００１２】
４．増加した相互接続コストとキャッシュを他のクラスタ資源に対応してスケーリングしたいという願望とにより、殆どの従来の研究によって想定された集中型キャッシュと異なり、データキャッシュを複数のクラスタへ分散することが必要となるであろう。
【００１３】
多くのクラスタの使用は複数のスレッドにされた作業負荷のための全体的なスループットを大幅に押し上げることができたが、単一スレッドプログラムの性能に対するその影響は同じほどには明白でない。上記のトレンドの蓄積効果は、クラスタ化プロセッサが従前のモデルにおいて想定されたところよりも更に多くの通信に拘束されるであろうということである。チップ上のクラスタ数が増加するにつれて、スレッドに利用可能な資源の数もまた増加し、より大きなウィンドウのインフライト命令を支持することによってより離れた命令レベル並列性（ＩＬＰ）が活用されるのを可能とする。同時に、プログラムの様々な命令及びデータは、より大きなオンチップ空間上に分配される。データが様々なクラスタに亘って頻繁に通信されなければならない場合、この増加した通信からの性能ペナルティは、追加資源によって活用される並列性による全ての利益を相殺してしまう。
【００１４】
クラスタ化プロセッサに基づいた多くの提案は、過去十年の間に出現してきた。これらは、割り当てられる資源の種類、ヒューリスティクスをステアリングする命令、及びクラスタ間通信のためのセマンティクスにおいて異なる。キャッシュは、これらのすべてのモデルにおいて集中型構造である。これらの研究は、控え目な通信費用で少ない数の総クラスタを想定する。
【００１５】
最近の研究の多くの実質は、実行時間で適切な構成を選ぶ多重構成オプション及びアルゴリズムを備えたハードウェアユニットに焦点を合わせるものであった。これらのアルゴリズムの多くは、それらが命令又はサイクルの固定されたインターバルに関する様々な統計をモニタリングし、その情報に基づいて構成決定をするという点で、インターバルに基づくものである。サブルーチン境界での順応は、固定された命令間隔を用いるよりも効果的となりうる。
【００１６】
様々な最近の研究業績は、ハードウェアをプログラムフェーズ要件へ動的にチューニングするための実行時間アルゴリズムを提案してきた。これらの技術の殆どはインターバルに基づいたアルゴリズムを用い、そこでは最後の僅かのインターバルに関する測定が次のインターバルに関する構成の選択を指示する。そこでは、インターバルは、予め定められた数のコミットされた命令である。
【００１７】
将来世代のプロセッサは、配線遅延の高コストのためより低いＩＰＣに悩むであろう。
【発明の開示】
【発明が解決しようとする課題】
【００１８】
本発明は、従来技術の欠点を克服することを目的とする。
【課題を解決するための手段】
【００１９】
上記及びその他の目的を達成するために、本発明は、上記のトレンドに対峙し、改善された単一スレッド性能のための通信並列性トレードオフを最適化するダイナミックにチューニング可能なクラスタ化されたアーキテクチャに関する。そのバランスは、該スレッドのために利用可能なクラスタの合計数のサブセットのみを使用することによりもたらされる。
【００２０】
我々の成果は、クラスタの数の相関としての性能トレンドが、異なるプログラムに亘り、それらの中に存在する離れたＩＬＰの程度に依存して変化する、ということを示す。我々は、そこで、任意のプログラムフェーズに関するクラスタの最適な数を同定し、プログラムの要件にハードウェアを一致させる動的アルゴリズムを開発した。我々は、どのようなプログラムポジションでもアクティブなクラスタの数を変えるアルゴリズムを提示し、過去の僅かのインターバル上の性能履歴を見る簡単なアルゴリズムが利用可能な性能向上の殆どを往々にして与えることを示す。しかしながら、そのようなアルゴリズムは、再構成のための細粒度の機会を逃すので、我々は、逃された機会をターゲットとすべく試みることにより多くのハードウェアを投資する他の技術を提示する。最良の静的構成に対して、単一インターバルに基づくアルゴリズムは全体で１１％の改善を提供し、他方細粒度技術は１５％の改善を提供することができる。
【００２１】
単一スレッドの性能を改良するために所与のプログラムフェーズのためのクラスタのサブセットを不能にすることは、別の好ましい意味合いを有している。全クラスタはそれらの電源電圧を切断することができ、これによって漏れエネルギーをかなり節約する。これは、単一体プロセッサにおいては可能でなかったであろう技術である。選択的に、これらのクラスタは他のスレッド（の中で分割可能で）によって用いることができ、これによって、最適な単一の及び複数のスレッドのスループットに係る目標を同時に達成する。
【００２２】
我々は、将来のクラスタ化プロセッサの設計における先細るプロセス技術及び支配的配線遅延の影響を、提示して評価した。増加するチップ密度を利用するためにクラスタ数を増加することは複数のスレッドをサポートするプロセッサの能力を高めるが、単一スレッドの性能は逆に悪い影響を受けうる。これは、そのようなプロセッサがクラスタ間の通信コストによって束縛されることによるものである。これらの費用は、プロセッサが多くのクラスタにスケーリングされるにつれて、命令レベル並列性の全ての増加した抽出を支配する傾向を示しがちである。我々は、規則的インターバルで探索ベースのアプローチを用いて動的にクラスタの数を選択することが、単一スレッドのための通信並列性トレードオフを最適化するのに効果的であることを実証した。それは殆ど全てのプログラムに適用可能で、我々のベースアーキテクチャに対して平均１１％の性能改善を与えた。細粒でフェーズ変化を利用するためには、追加的なハードウェアを投資しなければならず、これは全体で１５％の改善を可能にする。平均８．３クラスタが再構成スキームによって無効になるので、単一スレッドモードにおいて多くの漏れエネルギーを節約する可能性がある。複数のスレッドにされた作業負荷のスループットも、各スレッドに動的に１セットのクラスタを供することによってスレッド間干渉を回避することにより改善可能である。我々は、多くの興味深いプロセッサモデルに対して我々の結果の妥当性を確認しており、これにより将来のプロセッサにおける通信並列性トレードオフの処理の重要性を強調する。
【００２３】
我々のものは、可変長命令間隔の重要性を識別し、選択アルゴリズムにこれを取り入れる初の提案である。また、我々は、分岐境界で細粒度の再構成を調べ、それを間隔ベースのスキームと対比する最初の者たちである。我々のものは、単一プロセス技術に注目し、多くの資源を加えることの効果を検討する最初の調査である。クラスタ化プロセッサモデルは、通信と並列性の間のクリアなトレードオフを呈して、それは低コストの再構成に簡単に適することができる。
【発明を実施するための最良の形態】
【００２４】
本発明とその変形例に係る好ましい実施形態を、図面を参照しつつ詳細に記載する。図中、同様の参照数字は同様のエレメントを参照する。
【００２５】
我々は、初期の研究において一般に用いられたベースラインとなるクラスタ化されたプロセッサモデルを記載することから始める。そのようなモデルは１００として図１に示され、４つのクラスタ１０２（個別に指定された１０２−１、１０２−２、１０２−３、及び１０２−４）を備えている。その４つのクラスタ１０２より上流には、命令キャッシュ１０４、分岐予測器１０６、命令フェッチキャッシュ１０８、ステアリング・レジスタ・リネーム装置１１０、及びリオーダバッファ１１２がある。各クラスタ１０２内には、発行キュー１１４、レジスタファイル１１６、及び機能ユニット１１８がある。クラスタ１０２より下流には、ロード／ストアキュー（ＬＳＱ）１２０及びデータキャッシュ１２２がある。
【００２６】
従来のプロセッサにおけるのと同様に、分岐予測器１０６と命令キャッシュ１０４は集中化された構造である。ステアリング・レジスタ・リネーム装置１１０においてレジスタリネームする際に、各命令は特定のクラスタに割り当てられる。各クラスタ１０２はそれぞれ、自身の発行キュー１１４、レジスタファイル１１６、１セットの機能ユニット１１８、及び自身のローカルバイパス・ネットワークを有する。クラスタ内で結果をバイパスすることは、追加のサイクルを取得しない（換言すれば、同じクラスタにおける依存命令は逐次的サイクルにおいて発行することができる）。しかしながら、消費命令が生産者と同じクラスタにない場合、結果が２つのクラスタに亘って通信されるまで、それは追加サイクルを待たなければならない。
【００２７】
従来のクラスタ化プロセッサは、クラスタ１０２の中に、レジスタファイル１１６、発行キュー１１４、及び機能ユニット１１８のみを分散する。データキャッシュ１２２は中心に設けられている。別の構造は各クラスタの中にキャッシュを分散し、これによって、設計をよりスケーラブルにするだけでなく実装複雑性を増加する。両構造は魅力的な設計オプションであるので、我々は両構造に対するダイナミックチューニングの効果を評価する。
【００２８】
従来のクラスタ化設計において、一旦ロードとストアが準備されると、それらは集中型のロード・ストア・キュー（ＬＳＱ）１２０に挿入される。ここから、ストアは実行する場合集中型のＬｌキャッシュに送られ、ロードは前のストアと衝突しないと判明した場合発行される。任意のクラスタにおけるロードが他のクラスタのうちの何れかからの前のストアと衝突するかもしれないので、ＬＳＱは集中化される。
【００２９】
我々が検討している積極的なプロセッサモデルについては、キャッシュは全てのサイクルで多くのリクエストをサービスしなければならない。高バンド幅のキャッシュを実現するために効率的な方法は、それをワード・インタリーブすることである。４ウェイのワード・インタリーブされたキャッシュについては、データ配列は４つのバンクへ分割され、各バンクは１サイクル当り１つのリクエストをサービスすることができる。４Ｎという形式のワードアドレスを備えたデータはバンク０に格納され、４Ｎ＋１という形式のものはバンク１に格納され、以降同様の具合で格納される。そのような構成は、最大４のバンド幅をサポートし、バンクへの衝突を最小限にするのを助ける。
【００３０】
集中型キャッシュを備えたプロセッサにおいて、ロード・レイテンシは、集中型キャッシュとロードを発行するクラスタとの間の距離に依存する。我々の研究において、我々は、集中化されたＬＳＱ及びキャッシュは、クラスタ１０２−１と共同して位置すると想定する。従って、クラスタ１０２−１からのロード発行は何らの通信コストを伴わない。クラスタ１０２−２からのロード発行は、ＬＳＱとキャッシュにアドレスを送るのに１サイクルを要し、そのデータを取り戻すのに別の１サイクルを要する（クラスタ間のやり取り（以下、ホップという。）がそれぞれ１サイクル要すると仮定した場合）。同様に、クラスタ１０２−３は、各ロードに対して総計４サイクルの通信コストを伴う。これは、キャッシュＲＡＭルックアップを行なうのに必要なわずかのサイクルに加えられている。
【００３１】
次に、ステアリング・ヒューリスティクスについて説明する。クラスタ化設計は、より高速のクロックを許容するが、クラスタ間通信およびロード不均衡のために顕著なＩＰＣの低下を招来する。スマートな命令ステアリングによってこれらのペナルティを最小限にすることが多くの最近の研究の焦点とされてきた。我々は、最大のオペランドを生成するクラスタへ命令（及びそのデスチネーションレジスタ）をステアリングする効果的なステアリング・ヒューリスティックを用いる。タイの場合又は発行キューの占有における不均衡が見られる状況下では、命令は最もロードされていないクラスタへステアリングされる。ロード不均衡を検出するために適切な閾値を選ぶことによって、Ｍｏｄ＿Ｎ及びＦｉｒｓｔ＿Ｆｉｔのようなアルゴリズムは他の提案されたステアリング・ヒューリスティクスに近似することもできる。前者は、Ｎ個の命令を１つのクラスタへステアリングし、次にそれに隣接するものにステアリングすることにより、ロード不均衡を最小限にする。後者は、隣接するものに命令をステアリングする前に１つのクラスタを満たすことにより通信を最小限にする。我々は、ロード均衡のための最適な閾値を経験的に決定した。さらに、我々のステアリング・ヒューリスティックはまた、クリティカルなソースオペランドを生成するクラスタにより高い優先順位を与えるためにクリティカリティ予測器を用いる。このように、我々のヒューリスティックは、ステアリング機構における最先端技術を表す。
【００３２】
高度にクラスタ化されたプロセッサにおいては、集中型キャッシュは主要なボトルネックになりえる。なぜなら、それは高バンド幅をサポートしなければならず、また要求クラスタへのその平均距離は増加するからである。従って、分散キャッシュモデルは魅力的な設計オプションである。
【００３３】
Ｎ−クラスタ・システムについて、我々は、Ｌ１キャッシュがＮ個のワード・インタリーブされたバンクに分割されていると想定する。各バンクは自身のクラスタに関係している。ＬＳＱもまた異なるクラスタに亘って分割されている。図２の例は、４つのクラスタを持った構造を示す。図２のプロセッサモデル２００は、各クラスタ２０２が分散されたＬＳＱ２２０及び分散されたデータキャッシュ２２２を含んでいる点で図１のプロセッサモデル１００と異なる。また、バンク予測器２０９が提供されている。様々なバンクがワード・インタリーブされているので、それらは相互に排他的なデータをキャッシュし、それらの間にキャッシュ・コヒーレンス・プロトコルを必要としない。ステアリング機構の目標は、対応するメモリアドレスをキャッシュするクラスタにロードかストアをステアリングすることである。我々は、キャッシュが分散されたことから生ずる追加的なステアリング複雑性について以下で議論する。
【００３４】
Ｌ２キャッシュはクラスタ１（２０２−１）とともに位置し続ける。また、Ｌ１キャッシュバンクの内の何れかにおけるミスは、このクラスタに関連したそれ以外のものについて、ホップ数に依存して付加的なレイテンシを招来する。
【００３５】
プロセス技術が収縮してクラスタの数が増加されるにつれて、通信遅延とクラスタ間相互連結トポロジーとに注意が払われなければならない。クラスタ間通信がフロントエンドで発生する。もちろん、複数のクラスタに亘ってレジスタ値を通信する場合又はキャッシュにアクセスする場合にも通信が発生する。前者はすべてのサイクルで生じるので、我々はこの目的のために別々のネットワークを想定し、フロントエンドに分岐ミス予測を通信する際の付加的レイテンシと同様に非同一ディスパッチ・レイテンシもモデル化する。後者の２つ（キャッシュ通信及びレジスタ間通信）はレジスタへの／からのデータ転送を含んでいるので、我々は同様な（別々の）ネットワークが用いられると想定する。
【００３６】
好ましい実施形態において、我々は、実装複雑性が小さいのでリング相互接続に注目する。各クラスタは、２つの他のクラスタに直接に接続される。我々は２つの一方向リングを想定する。つまり、１６のクラスタ機構は合計３２のリンクを有していて（１サイクルにおいて合計３２の転送を可能にする）、任意の２つのノード間のホップの最大数は８であることを意味する。
【００３７】
以下では、センシティビティ解析の一部として、我々はグリッド相互接続に関する結果もまた示す。これは、より高い実装コストを有するがより高い性能を有する。クラスタは２次元配列中にレイアウトされる。各クラスタは最大４つの他のクラスタに直接に接続されている。１６クラスタについては、合計４８のリンクがあり、ホップの最大数が６で、これにより全体的な通信コストを削減する。
【００３８】
我々のシミュレータは、Ａｌｐｈａ  ＡＸＰ命令セットのためのＳｉｍｐｌｅｓｃａｌａｒ−３．０に基づく。このシミュレータはアルファ２１２６４に類似するマイクロアーキテクチャを表現するべく修正されている。レジスタ更新ユニット（ＲＵＵ：ｒｅｇｉｓｔｅｒ  ｕｐｄａｔｅ  ｕｎｉｔ）は、発行キュー、物理レジスタファイル、及びリオーダバッファ（ＲＯＢ：ｒｅｏｒｄｅｒ  ｂｕｆｆｅｒ）へ分解されている。該発行キュー及び該物理レジスタファイルは更に整数及び浮動小数点へ分割されている。このように、我々の研究における各クラスタはそれ自体、整数と浮動小数点のクラスタへ分解される。メモリ階層も（ワード・インタリーブ・アクセス、バス及びポートの競合、ライトバック・バッファ等を含め）詳細にモデル化される。
【００３９】
このベースプロセッサ構造は、クラスタ化マイクロアーキテクチャをモデル化するために修正された。将来のテクノロジにおける配線遅延に拘束されたプロセッサを代表するために、各クラスタコアは、各種の１つの機能ユニット、３０の物理レジスタ（ｉｎｔとｆｐそれぞれ）、及び１５の発行キューエントリ（ｉｎｔとｆｐそれぞれ）を有していると想定する。利用可能な機能ユニットの数に従って多くの命令を１サイクルで発行することができる。我々は、相互接続上の各ホップが単一サイクルを要すると想定する。我々は、トレースキャッシュをモデル化しなかったが、他方で一度に最大２つの基本ブロックから命令をフェッチし得ると想定した。重要なシミュレーション・パラメータは、表１に下記のように要約される。
【００４０】
【表１】
2008502083.tif 000003
【００４１】
我々の研究は将来の配線制約されたテクノロジに注目するものであり、我々は０．０３５μに対する予測に従ってレイテンシを選ぶ。我々は、キャッシュ構造に対するアクセス時間を見積もるためにＣＡＣＴＩ−３．０を用いた。Ｓｉｍｐｌｅｓｃａｌａｒにより、我々は、最良のベースケースを決定するために、異なるサイズ及びポートパラメータ（従って異なるレイテンシ）のキャッシュ構造をシミュレートした。これらのパラメータは、表２に下記のように要約される。集中型キャッシュは、４ウェイワード・インタリーブの３２ｋＢキャッシュに対し最良の性能を与えた。そのようなキャッシュは、１サイクル当り４アクセスのバンド幅と６サイクルのアクセス時間とを有する。その最も分散されたキャッシュ構成は、各クラスタに単一ポート４サイクル１６ｋＢバンクを有している。
【００４２】
【表２】
2008502083.tif 000004
【００４３】
ベンチマークセットとして、我々は、４つのＳＰＥＣ２ｋＩｎｔｅｇｅｒプログラム、３つのＳＰＥＣ２ｋＦＰプログラム、及びＵＣＬＡ  Ｍｅｄｉａｂｅｎｃｈから２つのプログラムを用いた。これらのプログラムについての詳細は、下記表３に示されている。これらのプログラムは、高・低のＩＰＣコード、メモリにより制限されたコード、分岐誤予測等を含む様々なプログラムタイプを代表する。これらのプログラムの殆どは、測定値が取得される前に、最初の２０億の命令を通じて速く転送され、様々なプロセッサ構造を温めるために詳細にシミュレートされる。我々が積極的プロセッサモデルをシミュレートしている間、我々のすべてのベンチマークプログラムが高ＩＰＣを有するとは限らない。高ＩＰＣコードを実行する必要性及び複数のスレッドをサポートする必要性により、積極的プロセッサ設計が動機づけられることに留意されたい。何れの場合においても、単一の低ＩＰＣスレッドの迅速な完了は尚も重要であり−従ってベンチマークセットにそのようなプログラムを含める必要性がある。
【００４４】
【表３】
2008502083.tif 000005
【００４５】
簡単のために、我々は、集中型キャッシュ及びリング相互接続を備えた１６クラスタモデルに我々の初期解析を集中させる。図３は、クラスタの固定サブセットをプログラムに静的に用いる効果を示す。クラスタの数の増加は、集中型キャッシュからのロード／ストア命令の平均距離及び最悪の場合のクラスタ間バイパス遅延を増加し、これによって全体的な通信コストに大幅に影響している。ロード及びストアのための０のクラスタ間通信コストが３１％だけ性能を改善したと仮定して、他方レジスタ間通信のための０のコストが１１％だけ性能を改善したと仮定すると、増加したロード／ストア・レイテンシが通信オーバヘッドを支配することを示す。このレイテンシはキャッシュに近いクラスタにロード／ストア命令をステアリングすることによって削減することができるが、これはロード不均衡及びレジスタ通信を増加するであろう。１６クラスタ機構におけるクラスタ間のレジスタ通信に対する平均レイテンシは、４．１サイクルであった。同時に、多くのクラスタを用いることは、より多くの機能ユニット、レジスタ、及び発行キューエントリを備えたプログラムを提供もし、これによりそれがより大きなウィンドウのインフライト命令を送ることを可能とする。衝突する２つの力のどちらが支配的かにより、クラスタの数が増加されたときの性能は改善又は悪化する。ｄｊｐｅｇ（ＭｅｄｉａｂｅｎｃｈからデコードするＪＰＥＧ）、ｓｗｉｍ、ｍｇｒｉｄ、及びｇａｌｇｅｌ（ＳＰＥＣ２Ｋからのループベースの浮動小数点プログラム）のような離れたＩＬＰを備えたプログラムは、多くの資源を用いることから利益を得る。他方、低分岐予測精度の殆どの整数プログラムは、大きなウィンドウのインフライト命令を活用することができない。従って、資源の増加は追加的通信コストにより性能を下げるだけである。これは、クラスタ化プロセッサにおいて従来観察されていない現象である（４つを超えるクラスタを対象とした研究が殆どなかったことや、従前の研究が集中型キャッシュにアクセスする際の通信コストを想定しなかったことによる。）。
【００４６】
我々の目標は、プログラムに対してクラスタを動的に割り当てることにより、プログラム要求に対してハードウェアを適合させることである。これは、処理不能な（ディスエイブルの）クラスタに対する命令ディスパッチをさせないように、ステアリング・ヒューリスティックを修正することにより達成することができる。換言すれば、ディスエイブルすることは、クラスタに対して如何なる新規の命令をも割り当てないことに等しい。ディスエイブルのクラスタに既に割り当てられていた命令は完了することが許され、該クラスタの自然な排出に帰着する。
【００４７】
各プログラムフェーズの起動時に、我々は、あるインターバルに対して各構成オプションを実行してＩＰＣを記録する。我々は、その後、最も高いＩＰＣを備えた構成を選び、次のフェーズ変化が検出される迄それを用いる。そのような機構は、多くのインターバルに対して、均一な性能を保持するプログラム能力に大いに頼っている。我々は、浮動小数点プログラムが一般的にそのビヘイビアを示し、他方整数プログラムが非常により多くの可変性を示すことを発見した。従前の研究は固定されたインターバル長を想定していたが、我々はこのことが多くのプログラムに対して非常に貧弱な性能に帰着するであろうことを発見した。従って、適切なインターバル長を選ぶことは、構成選択アルゴリズムの成功にとって必須である（そして、クラスタの数に加えてプロセッサのその他の側面に関する構成に普遍的に適用可能となる）。
【００４８】
異なるインターバルに対するプログラム動作の可変性を調べるために、我々は、通常の１０Ｋ命令インターバルで様々な統計のトレースを生成する何十億もの命令のためのプログラムの各々を実行した。我々は、プログラムフェーズを定義するために３つの測定法を用いた。すなわち、ＩＰＣ、分岐周波数、及びメモリ参照周波数の３つを用いた。各プログラムフェーズの始まりでは、最初のインターバルの間に集められた統計を基準として用いた。続いて起こる各インターバルについて、そのインターバルに対する３つの測定値が基準点に類似していた場合、該インターバルを「安定的（ｓｔａｂｌｅ）」と呼ぶことにした。３つの測定値の内のどれかが大きく異なっていた場合、我々はそのインターバルを「不安定的（ｕｎｓｔａｂｌｅ）」と宣言して、新規のプログラムフェーズを開始した。この解析は多くのインターバル長に対して行われた。あるインターバル長に対する不安定率とは、「不安定的」とみなされたインターバルの割合（すなわちフェーズ変化の発生頻度）である。我々の研究において、我々は、可能な構成（２、４、８、及び１６のクラスタ）に係る限定的なサブセットを探索するだけで十分であるということを発見した。なぜなら、それらが興味深いケースの殆どをカバーしたからである。５％の不安定率は、インターバルの１５％未満が最適な構成より下位であることを保証する。
【００４９】
次の表４は、我々のプログラムの各々に対して受容可能な５％未満の不安定率を与える最も短いインターバル長を示す。表から分かるように、最高のものとして出現するインターバル長は、１０Ｋから４０Ｍまで変化する。我々は、１０Ｋ命令の固定インターバル長に対する不安定率をも示す。明らかに、このインターバル長は、多くのプログラムにとって貧弱に働き、極めて受け入れがたい性能に帰着するであろう。殆どのプログラムは通常、粗く十分なインターバル長の各インターバルに亘って一貫したビヘイビアを示し、インターバルに基づいたスキームを非常にロバストなものとして普遍的に適用可能にする。ビヘイビアが入力データによって劇的に変わってくるｐａｒｓｅｒのようなプログラムでさえ、大きな４０Ｍ命令インターバルに対して低い不安定率を有する。
【００５０】
【表４】
2008502083.tif 000006
【００５１】
実行時間で最適な命令インターバル長に辿り着くために、我々は簡単なアルゴリズムを用いる。まず、最小の命令インターバルによって開始する。不安定率が高すぎる場合インターバルのサイズを２倍にし、低い不安定率となるか又は予め定められた限界（たとえば１０億の命令）に達するまでこれを繰り返す。その限界に達したなら、選択アルゴリズムを使用するのを止めて最も頻繁に選ばれた構成を選ぶ。
【００５２】
インターバル長を一度選んだとしても、そのインターバル長に永久に留まる必要はない。該プログラムは、１つの大きなマクロフェーズから、完全に異なった最適命令インターバルを有するかもしれない別のものへ移動するかもしれない。これに対処するためには、更に、フェーズ検出アルゴリズムを階層的に構築することができる。粗い粒度（たとえば、１０００億の命令ごと）で統計を検査するアルゴリズムは、新規のマクロフェーズの検出をもたらすことができ、この点において、１０Ｋインターバル長の選択アルゴリズムを再開し、最適なインターバル長を至る所で再び見つけることができるであろう。
【００５３】
完全を期するために、下記に掲載されているコードにおいて、我々は、インターバル長を選択し、フェーズを検出し、及び実行時間で最良の構成を選択するアルゴリズムを記載する。フェーズの始まりにおいて、最初のインターバルで集められた統計は、その後の統計を比較してフェーズ変化を検出する基準点としての役割を果たす。分岐とメモリ参照の頻度は、マイクロアーキテクチャ非依存のパラメータであり、調査過程の間であってもフェーズ変化を検出するために用いることができる。調査後、最良の性能の構成が選ばれ、それのＩＰＣもまた基準として用いられる。分岐の数、メモリ参照の数、又はＩＰＣの何れかが基準点と大きく異なる場合、フェーズ変化が示される。時々、あるインターバルの間にＩＰＣ特性に僅かな変化があることがあり（恐らく分岐ミス予測のバースト又はキャッシュミスによってもたらされる。）、その後、ビヘイビアは前のフェーズのそれに戻る。このシナリオにおける不必要な調査を失くすために、我々は（ｎｕｍ  ｉｐｃ  ｖａｒｉａｔｉｏｎｓパラメータで）ＩＰＣ測定における一定のノイズを許容する。加えて、フェーズ変化が頻繁な場合、ｉｎｓｔａｂｉｌｉｔｙ変数はインクリメントされ、結果インターバル長は２倍になる。
【００５４】
（クラスタの数の動的選択のための実行時間アルゴリズム）
初期設定と定義：
ｉｎｔｅｒｖａｌ＿ｌｅｎｇｔｈ  ＝  １０Ｋ；（アルゴリズムを起動する前の設定され
た命令の数）
ｄｉｓｃｏｎｔｉｎｕｅ＿ａｌｇｏｒｉｔｈｍ  ＝  ＦＡＬＳＥ；（これが設定された場
合、更なる再構成は次のマクロフェーズまで試みられない）
ｈａｖｅ＿ｒｅｆｅｒｅｎｃｅ＿ｐｏｉｎｔ  ＝  ＦＡＬＳＥ；（新規フェーズにおける
最初のインターバルは、その後のインターバルを比較するための基
準点を提供する）
ｓｉｇｎｉｆｉｃａｎｔ＿ｃｈａｎｇｅ＿ｉｎ＿ｉｐｃ；（現在のインターバルにおける
ＩＰＣが基準点におけるそれと１０％超異なる場合、これが設定さ
れる）
ｓｉｇｎｉｆｉｃａｎｔ＿ｃｈａｎｇｅ＿ｉｎ＿ｍｅｍｒｅｆｓ；（現在のインターバル
におけるメモリ参照が基準点からｉｎｔｅｒｖａｌ＿ｌｅｎｇｔｈ
／１００超異なる場合、これが設定される）
ｓｉｇｎｉｆｉｃａｎｔ＿ｃｈａｎｇｅ＿ｉｎ＿ｂｒａｎｃｈｅｓ；（ｓｉｇｎｉｆｉｃ
ａｎｔ＿ｃｈａｎｇｅ＿ｉｎ＿ｍｅｍｒｅｆｓと同様）
ｎｕｍ＿ｉｐｃ＿ｖａｒｉａｔｉｏｎｓ  ＝  ０；（これはｓｉｇｎｉｆｉｃａｎｔ＿ｃ
ｈａｎｇｅ＿ｉｎ＿ｉｐｃがあった回数を示す）
ｓｔａｂｌｅ＿ｓｔａｔｅ  ＝  ＦＡＬＳＥ；（全ての構成が探索された後においてのみ
これが設定される）
ｎｕｍ＿ｃｌｕｓｔｅｒｓ；（有効なクラスタの数）
ｉｎｓｔａｂｉｌｉｔｙ  ＝  ０；（フェーズ変化頻度を示す数）
ＴＨＲＥＳＨ１  ＝  ＴＨＲＥＳＨ２  ＝  ５；  ＴＨＲＥＳＨ３  ＝  １  ｂｉｌｌｉｏｎ  ｉｎｓｔｒｕｃｔｉｏｎｓ；
１０００億の命令ごとに統計を検査する。
Ｉｆ  （ｎｅｗ  ｍａｃｒｏｐｈａｓｅ）
Ｉｎｉｔｉａｌｉｚｅ  ａｌｌ  ｖａｒｉａｂｌｅｓ；
Ｉｆ  （ｎｏｔ  ｄｉｓｃｏｎｔｉｎｕｅ＿ａｌｇｏｒｉｔｈｍ）
Ｅｘｅｃｕｔｅ  ｔｈｅ  ｆｏｌｌｏｗｉｎｇ  ａｆｔｅｒ  ｅｖｅｒｙ  ｉｎｔｅｒｖａｌ＿ｌｅｎｇｔｈ  ｉｎｓｔｒｕｃｔｉｏｎｓ；
Ｉｆ  （ｈａｖｅ＿ｒｅｆｅｒｅｎｃｅ＿ｊｐｏｉｎｔ）
Ｉｆ  （ｓｉｇｎｉｆｉｃａｎｔ＿ｃｈａｎｇｅ＿ｉｎ＿ｍｅｍｒｅｆｓ  ｏｒ  ｓｉｇ
ｎｉｆｉｃａｎｔ＿ｃｈａｎｇｅ＿ｉｎ＿ｂｒａｎｃｈｅｓ  ｏｒ  ｓｉｇｎ  ｉｆｉｃａｎｔ＿ｃｈａｎｇｅ＿ｉｎ＿ｉｐｃ  ａｎｄ  ｎｕｍ＿ｉｐｃ＿ｖ
ａｒｉａｔｉｏｎｓ  ＞  ＴＨＲＥＳＨ１））
ｈａｖｅ＿ｒｅｆｅｒｅｎｃｅ＿ｐｏｉｎｔ＝ｓｔａｂｌｅ＿ｓｔａｔｅ  ＝  ＦＡＬＳＥ；
ｎｕｍ＿ｉｐｃ＿ｖａｒｉａｔｉｏｎｓ  ＝  ０；
ｎｕｍ＿ｃｌｕｓｔｅｒｓ  ＝  ４；
ｉｎｓｔａｂｉｌｉｔｙ  ＝  ｉｎｓｔａｂｉｌｉｔｙ  ＋  ２；
ｉｆ  （ｉｎｓｔａｂｉｌｉｔｙ  ＞  ＴＨＲＥＳＨ２）
ｉｎｔｅｒｖａｌ＿ｌｅｎｇｔｈ＝ｉｎｔｅｒｖａｌ＿ｌｅｎｇｔ
ｈ  ＊  ２；
ｉｎｓｔａｂｉｌｉｔｙ  ＝  ０；
ｉｆ  （ｉｎｔｅｒｖａｌ＿ｌｅｎｇｔｈ  ＞  ＴＨＲＥＳＨ３）
Ｐｉｃｋ  ｍｏｓｔ  ｐｏｐｕｌａｒ  ｃｏｎｆｉｇｕｒａｔｉｏｎ；ｄｉｓｃｏｎｔｉｎｕｅ＿ａｌｇｏｒｉｔｈｍ  ＝  ＴＲＵＥ；
ｅｌｓｅ
ｉｆ  （ｓｉｇｎｉｆ  ｉｃａｎｔ＿ｃｈａｎｇｅ＿ｉｎ＿ｉｐｃ）
ｉｆ  （ｓｔａｂｌｅ＿ｓｔａｔｅ）  ｎｕｍ＿ｉｐｃ＿ｖａｒｉａｔｉｏｎｓ  −  ｎｕｍ＿ｉｐｃ＿ｖａｒｉａｔｉｏｎｓ  ＋  ２；
ｅｌｓｅ
ｎｕｍ＿ｉｐｃ＿ｖａｒｉａｔｉｏｎｓ  ＝  ＭＡＸ（−２，  ｎｕｍ＿ｉｐｃ＿ｖａｒｉａｔｉｏｎｓ−０．１２５）；
ｉｎｓｔａｂｉｌｉｔｙ  ＝  ｉｎｓｔａｂｉｌｉｔｙ  −  ０．１２５；
ｅｌｓｅ  
ｈａｖｅ＿ｒｅｆｅｒｅｎｃｅ＿ｐｏｉｎｔ  ＝  ＴＲＵＥ；
Ｒｅｃｏｒｄ  ｂｒａｎｃｈｅｓ  ａｎｄ  ｍｅｍｒｅｆｓ．
Ｉｆ  （ｈａｖｅ＿ｒｅｆｅｒｅｎｃｅ＿ｐｏｉｎｔ  ａｎｄ  ｎｏｔ  ｓｔａｂｌｅ＿
ｓｔａｔｅ）
ｒｅｃｏｒｄ  ＩＰＣ；
ｎｕｍ＿ｃｌｕｓｔｅｒｓ＝ｎｕｍ＿ｃｌｕｓｔｅｒｓ  ＊  ２；
ｉｆ  （ｎｕｍ＿ｃｌｕｓｔｅｒｓ  ＞  １６）
ｐｉｃｋ  ｔｈｅ  ｂｅｓｔ  ｐｅｒｆｏｒｍｉｎｇ  ｃｏｎｆｉｇｕｒａｔｉｏｎ；
ｍａｋｅ  ｉｔｓ  ＩＰＣ  ｔｈｅ  ＩＰＣ＿ｒｅｆｅｒｅｎｃｅ＿ｐｏｉｎｔ；
ｓｔａｂｌｅ＿ｓｔａｔｅ  ＝  ＴＲＵＥ；
【００５５】
実行時間再構成に係るこの全過程は、ハードウェア・イベントカウンタからの支援によりソフトウェアにおいて実施することができる。次の構成に対する決定をする前に様々なハードウェア・カウンタを検査する（ＴＬＢミス処理ソフトウェアに用いられる物のような）低オーバヘッドのソフトウェア・ルーチンが、全てのインターバルで起動される。アルゴリズムは約１００のアセンブリ命令に上り、そのごく一部のみが各呼出しで実行される。１０Ｋ命令の最小インターバル長についてでさえ、これは１％より遥かに小さい割合のオーバヘッドとなる。ソフトウェアにおいて選択アルゴリズムを実施することは、より大きな柔軟性を可能にし、適用目的のアルゴリズムのための可能性を開く。マクロフェーズにおける変化を検出するより高級レベルのアルゴリズムは、さらに低いオーバヘッドを有する。アルゴリズムはソフトウェアにおいて完璧に作動するので、殆どのプログラムに特有の状態はハードウェアレジスタに対立するものとしてのメモリに存在する。従って、イベントカウンタから離れて、コンテキストスイッチ上に追加的な状態を保存してレストアしてはならない。
【００５６】
次に結果を示す。図４において、３番目の棒は、各プログラムフェーズの起動時の探索によるインターバルベースの選択機構を用いることの影響を図示する。基準点として、最初の２本の棒は、４個及び１６個のクラスタを備えた不変構造を示す。我々は、殆ど全ての場合において、その最良の不変構造の性能に近似する非常に良いジョブを動的スキームが行うことを理解することができる。僅かな不安定性を備えた浮動小数点プログラムについては（ｇａｌｇｅｌ、ｍｇｒｉｄ、ｓｗｉｍ）、該動的スキームは、プログラム要求にハードウェアを容易に一致させる。整数プログラムについては、殆どの場合、インターバルサイズが不適当となっている初期不安定期間がある。我々の先の解析と調和しつつ、５％未満の不安定率を許容する所に落ち着くまで、インターバルサイズは増加される。ｐａｒｓｅｒにおいて、シミュレーション・インターバルは、該動的スキームを必要な４０Ｍ命令インターバルに落ち着かせる程には長くなかった。
【００５７】
ｄｊｐｅｇにおいて、インターバルサイズが小さな不安定率を許容することができる程十分に大きい（１．２８Ｍ命令）ため、それは多くのインターバルを取得する。さらに、インターバル長が大きいので、再構成のための多くの機会がミスされる。ＩＬＰ特性が異なる各インターバル内に小さなフェーズがある。これらの２つの理由により、該動的スキームは、ｄｊｐｅｇのための１６クラスタを備えた該固定不変構造の性能に達しない。
【００５８】
ｇｚｉｐの場合、多くの長く続くフェーズがあり、離れたＩＬＰ特性のものもあれば、離れたＩＬＰが少ないものもある。該動的スキームはどのようなときでも最良の構成を選ぶので、その性能は該最良の不変固定構造に対してさえ優れている。平均では、１６のクラスタの内の８．３は、該ベンチマークセットに亘っていつもディスエイブルとなった。他の作業負荷が一切無い状態において、これは、もしこれらの未使用のクラスタへの電源電圧を切ることができるのであれば、漏れエネルギーにおける多大な節約をもたらす。同様に、複数のスレッドにされた作業負荷については、単一スレッドの性能を最適化した後でさえ、８超のクラスタがその他のスレッドによる使用のために尚も残る。
【００５９】
全体として、探索を備えた該動的インターバルに基づいたスキームは、該最良の不変固定構造より約１１％良く行う。それはまた非常にロバストである―それらのインターバルに亘るビヘイビアがかなり一貫する程に粗く十分なインターバル長が通常はあるので、それは我々のベンチマークセットにおける全てのプログラムに当てはまる。しかしながら、マイナス面は相対的に短いフェーズをターゲットすることができないことである。我々はより小さな初期インターバル長で実験したが、該動的スキームがこれらの小さなインターバル長において大きな不安定性に遭遇することを発見したので、そこで、ちょうど以前のように、インターバル長を大きな値に増加した。インターバルサイズが削減されるに従って測定値がより乱れてしまい、インターバル間の同プログラムの測定値を検出し、そして任意のフェーズのための最良の構成を同定することがより難しくなるという事実によって、それは引き起こされる。
【００６０】
これらの問題を緩和するために、我々は別のインターバルベースのスキームを試みた。各プログラムフェーズの始まりに様々な構成を探索する代わりに、我々は、あるインターバルについて１６クラスタ構成を用いた。また、利用可能な離れたＩＬＰの程度に基づいて、次のフェーズ変化まで後続のインターバルについて４個又は１６個のクラスタ構成の何れかを我々は選択した（我々の先の結果は、これらが２つの最も意味のある構成であって殆どの場合にあてはまることを示す）。命令は、ＲＯＢにおける最も古い命令より少なくとも１２０命令若い場合、離れている（ｄｉｓｔａｎｔ）とマークされる。発行の時、命令は、これが離れている場合、そのＲＯＢエントリに１ビットをセットする。コミットの時、このビットは、「離れたＩＬＰの程度」をインクリメントするために用いられる。各クラスタは３０の物理レジスタを有するので、約１２０のインフライト命令をサポートするためには４つのクラスタで十分である。あるインターバルにおいて発行された離れた命令の数が一定の閾値を越える場合、それは利用可能な離れたＩＬＰを利用するためには１６のクラスタが必要とされるであろうことを示す。我々の実験において、我々は、１０００のインターバル長に対して１６０という閾値を用いる。探索フェーズがないので、ハードウェアはプログラムフェーズ変化に迅速に反応し、細粒度での再構成が意味のあるものとなる。そこで、我々は小さな固定された命令インターバルに焦点を合わせ、実行時間でインターバル長を増加することを試みない。しかしながら、探索の代わりにプログラム測定値に基づいて決定するので、一定の精度が損なわれる。さらに、より小さなインターバル長、フェーズ変化へのより速い反応、だがより乱れる測定値は、かなりの誤判定に帰着する。
【００６１】
図４はまた、３つの異なる固定インターバル長に対するかかる機構に関する結果を示す。１Ｋの命令のインターバル長は、精度とフェーズ変化に対する高速反応との間の最良のトレードオフを提供する。全体として、それは、最良の不変ベースケースに対して同様の１１％の改善を示す。しかしながら、ｄｊｐｅｇのようなプログラムにおいて、それはインターバルベースの探索を備えたスキームよりずっと良く（２１％）行う。これは、異なる要求を備えた小さなフェーズをターゲットとするその能力による。不幸なことに、小さなインターバル長及び乱れた測定が頻繁なフェーズ変化及び不正確な意思決定となるので、それはｇａｌｇｅｌとｇｚｉｐのようなプログラムにおいて性能障害を被る。
【００６２】
これに対する１次的理由の１つは、逐次的な１０００の命令インターバルにおいて実行された基本ブロックが必ずしも同じだとは限らないという事実である。その結果、離れたＩＬＰを決定するのを助けるために、頻繁なフェーズ変化が示され、各新規フェーズ変化は１６クラスタを備えたインターバルに帰着する。この問題を緩和するために、我々は基本ブロック境界において細粒再構成スキームを検討する。
【００６３】
細粒度で再構成を許容するために、我々はすべての分岐を潜在的なフェーズ変化とみなす。我々は、高度に離れたＩＬＰが分岐に従うかどうか判断する必要があり、その場合、ディスパッチは自由に継続すべきか、そうでなければ、ディスパッチは最初の４つのクラスタのみに制限されるべきである。探索の異なるステージにおいて各分岐に関する乱れた測定に帰着する多くの隣接する分岐があるであろうから、様々な構成を探索することは実現可能な選択肢でない。従って、我々が十分な情報を有するようになるまで、１６のクラスタへのディスパッチを想定し、すべての分岐に従う離れたＩＬＰ特性を求める。同様な分岐に後で遭遇する場合に正確な数のクラスタを選ぶことができるように、それは再構成を更新するために用いられる。その表にエントリを持たない分岐に遭遇すれば、我々は１６のクラスタ構造を仮定し、それの離れたＩＬＰの程度を決定できるようにする。
【００６４】
４つのクラスタがおよそ１２０の命令をサポートすることができると想定し、分岐が離れたＩＬＰによって従われているかどうかを判断するために、我々は、分岐に従う３６０のコミットされた命令の内のどれだけ多くが発行したときに離れているかを識別する必要がある。そこで、４又は１６の何れかのクラスタが適切であろう。この計算をするために、我々は、最後にコミットされた３６０命令の離れたＩＬＰ性質の跡を追う。３６０命令のこのキューに入出する命令によって１つのカウンタを更新して、離れたＩＬＰの実行数を維持することができるようにする。分岐が偶然これらの３６０命令の内の最も古いものであった場合、それの離れたＩＬＰの程度がカウンタの値によって示される。
【００６５】
隣接する分岐からの何らかの干渉が未だ存在する蓋然性がある。当該機構をよりロバストにするために、我々は、同一の分岐の多くの事象に対するビヘイビアを、再構成表においてそれに対するエントリを作成する前にサンプリングする。さらに、我々は、特定の分岐のためにのみ変化を試みることにより、再構成の粒度を微調整することができる。たとえば、我々は、５つ目の分岐毎にのみ変化を試みた場合に最良の性能が達成されることを発見した。また、我々は、サブルーチンのコールとリターンでのみ変化を試みる機構に対する結果を示す。我々は、以下、このアルゴリズムを形式化する。
【００６６】
（全ての第Ｎ番目の分岐のためのアルゴリズム）
全ての第Ｎ番目の分岐で、再構成表をルックアップする。
Ｉｆ  ｅｎｔｒｙ  ｆｏｕｎｄ，  ｃｈａｎｇｅ  ｔｏ  ａｄｖｉｓｅｄ  ｃｏｎｆｉｇｕｒａｔｉｏｎ．
Ｅｌｓｅ  ，  ｕｓｅ  １６  ｃｌｕｓｔｅｒｓ．
３６０のコミットされた命令のキューから分岐を取り除いている間、
Ｉｆ  Ｍ  ｓａｍｐｌｅｓ  ｏｆ  ｔｈｉｓ  ｂｒａｎｃｈ  ｈａｖｅ  ｂｅｅｎ  ｓｅｅｎ，  
Ｄｏ  ｎｏｔ  ｕｐｄａｔｅ  ｔａｂｌｅ．
Ｅｌｓｅ，
Ｒｅｃｏｒｄ  ｔｈｅ  ｌａｔｅｓｔ  ｓａｍｐｌｅ．
Ｉｆ  ｔｈｉｓ  ｉｓ  ｔｈｅ  Ｍｔｈ  ｓａｍｐｌｅ，
ｃｏｍｐｕｔｅ  ｔｈｅ  ａｄｖｉｓｅｄ  ｃｏｎｆｉｇｕｒａｔｉｏｎ．
Ｅｌｓｅ，  
ａｄｖｉｓｅｄ  ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｉｓ  １６  ｃｌｕｓｔｅｒｓ．
【００６７】
今記載したこのアプローチのマイナス面は、初期測定が将来のビヘイビアを規定するという事実である。分岐に従うコードの性質は、プログラムの間に変わり得る。特に４つのクラスタのみが用いられていて離れたＩＬＰの程度が明白でない場合、そのような変化を検出するのは必ずしも簡単だとは限らないかもしれない。この状況に対処するために、我々は周期的なインターバルで再構成表をフラッシュする。我々は、１０Ｍ命令毎で表を再構築することが、無視できるオーバヘッドに帰着することを発見した。
【００６８】
図５において、探索を備えたベースケース及びインターバルベースのスキームに加えて、我々は、２つの細粒度再構成スキームに関するＩＰＣを示す。１つ目のものは全ての第５番目の分岐で再構成を試みて、各分岐につき１０のサンプルを集めた後に表にエントリを作成する。エイリアシングによる効果を除去するために、我々は殆ど全ての場合において大きな１６Ｋエントリ表を用いるが、もっと小さな表もまた機能する。２つ目のスキームは全てのサブルーチンのコールとリターンで変化を試みて、３つのサンプルを用いる。数値は、フェーズ変化に迅速に反応する能力がｄｊｐｅｇ、ｃｊｐｅｇ、ｃｒａｆｔｙ、ｐａｒｓｅｒ及びｖｐｒのようなプログラムにおいて改善された性能に帰着することを示す。構成間における最大の変化数はｃｒａｆｔｙについて観察された（１５０万）。探索を備えないインターバルベースのスキームにおけるのとは異なり、不安定性は乱れた測定によってもたらされない。しかしながら、ｇｚｉｐは、インターバルベースのスキームによって達成された性能にマッチしない。これは、分岐に従うコードの性質がプログラムの実行中に変わるからである。従って、将来のための構成を選ぶために初期測定を用いるという我々のポリシーは、必ずしも正確だとは限らない。同様なビヘイビアは、ｇａｌｇｅｌにおいて緩い程度で観察される。全体として、これらの細粒度スキームは、インターバルベースのスキームで観察された１１％の改善に比べると、ベースケースに対して１５％の改善を与える。
【００６９】
これらの結果から、探索を備えたインターバルベースのスキームは実現するのが簡単であり、ロバストであり、可能なスピードアップの殆どを提供すると我々は結論付ける。粗いインターバル長を選ぶそれらの傾向のために、多くの再構成機会が失われる。小さなインターバル長の選択は、逐次的な小さなインターバルに亘る乱れた測定のため、それに対する解決法でない。細粒度再構成を許容するために、我々は再構成ポイントとして基本ブロック境界を選び、将来のビヘイビアを予測するための初期測定を用いる。ｇｚｉｐを除き、そのようなアプローチは、多くの精度をトレードオフせず、またハードウェアはプログラムのニーズに迅速に適応することができる。しかしながら、この追加的な４％の改善を得るためには、我々は一定の少なからぬ量のハードウェア−予測のトラックを保持するための表及び離れたＩＬＰ測定値を維持するためのロジック−を投資しなければならない。
【００７０】
分散型キャッシュモデルを、ここで、クラスタ化ＬＳＱ実装に関してまず記載する。分散型キャッシュモデルにおいて、メモリ命令がリネームされたときに実効アドレスが分かっているのであれば、該当データをキャッシュするクラスタにそれを導くことができる。
しかしながら、実効アドレスはリネーム時には一般的に分かっていないので、このメモリ操作がアクセスする予定のバンクを我々は予測する必要がある。この予測に基づいて、命令はクラスタの内の１つに送られる。一旦実効アドレスが求められると、バンク誤予測の場合には適切なリカバリ動作がなされなければならない。
【００７１】
命令がロードであれば、リカバリは簡単である―実効アドレスが正しいクラスタに送られ、メモリ衝突がＬＳＱにおいて解決され、データがキャッシュバンクからフェッチされ、要求するクラスタに戻される。メモリ操作がストアであれば、その誤指示は正確性問題に帰着しうる。同一のアドレスに対して誤指示されたストアの存在に気づかない間に、別のクラスタにおけるロードが進められているかも知れない。この問題に対処するために、我々は次の方針を採用する。リネーム時に、実効アドレスが未知のストアは（実効アドレスを求める）特定のクラスタに割り当てられ、しかし同時に、ダミースロットがその他のクラスタに生成される。潜在的に衝突をもたらしうる未決アドレスを備えた先行ストアがあるので、他のクラスタにおける該ダミースロットの背後の後続ロードは先に進むことを妨げられる。一旦実効アドレスが求められると、その情報はすべてのクラスタに伝えられ、すべてのＬＳＱの中のダミースロットは、１つを除き、除去される。その伝達は、（我々がモデル化する）レジスタとキャッシュ・データに関する相互接続におけるトラフィックを増加する。
【００７２】
バンク予測に関し、以前の研究は、ロード又はストアによってアクセスされるバンクを予測するために分岐予測器のような表の使用を提案してきた。我々のシミュレーションでは、我々は、第１レベルで１０２４エントリ及び第２で４０９６エントリを備えた２レベルバンク予測器を用いる。
【００７３】
ステアリング・ヒューリスティクスに関し、分散型キャッシュを備えたプロセッサにおいて、ステアリング・ヒューリスティックは、各ロード又はストアにつき３つのデータ依存関係を取り扱わなければならない−すなわち、２つのソースオペランド及びデータをキャッシュするバンクである。キャッシュ・データの転送は２つの通信（アドレスとデータ）を伴うので、ロードかストアが該当データをキャッシュするために予測されたクラスタへステアリングされた場合、性能は最大化される（集中型キャッシュモデルにおけるのと異なり、キャッシュは一つの場所にないので、そうすることはロード不均衡を増加しない点に留意されたい）。そうではあるが、頻繁なバンク誤予測及びストア・アドレス伝達からの増加トラフィックは、性能に多大な影響を与える。これらの効果の無視は、性能を２９％改善した。同時に、キャッシュバンクからの依存を好むことは、増加したレジスタ通信に帰着する。自由なレジスタ通信の想定は、性能を２７％改善した。このように、レジスタとキャッシュのトラフィックは、そのようなシステムにおける通信ボトルネックに等しく寄与する。
【００７４】
これまでのところ、我々の結果は、集中型キャッシュを備えたクラスタ化プロセッサを想定してきた。従って、再構成は、ステアリング・ヒューリスティックに全クラスタのサブセットへ送らせる問題だけである。分散型キャッシュについては、各クラスタはこれに関連したキャッシュバンクを有している。データは、ワード・インタリーブされた方法により、これらのキャッシュバンクに割り当てられる。１６個から４個のクラスタへと行く際に、キャッシュバンクの数、従って物理的キャッシュラインに対するデータのマッピングは変化する。この問題を解決するために、最も複雑でない解決法は、Ｌ１データキャッシュがＬ２にフラッシュされている間、プロセッサをストールすることである。幸運にも、バンク予測器をフラッシュする必要はない。１６個のクラスタに関し、バンク予測器は４ビットの予測を生成する。４個のクラスタが用いられる場合、２低位ビットの予測が正しいバンクを指示する。
【００７５】
データの物理的キャッシュ位置へのインデックシングは変化するので、再構成は集中型キャッシュモデルにおける程にはシームレスでない。全ての再構成は、プロセッサのストール及びキャッシュフラッシュを必要とする。従って、前のセクションからの細粒度再構成スキームは当てはまらない。図６は、ベースケース及びインターバルベース機構に関するＩＰＣを示す。３番目の棒は、探索及び最低１０Ｋインターバル長の命令を備えたスキームを示す。４番目と５番目の棒は、探索及び最良の構成を選ぶ離れたＩＬＰ測定法の使用のないインターバルベースのスキームを示す。分散型キャッシュのためのシミュレーション・パラメータは、表２に概説されている。我々は、結果のトレンドが集中型キャッシュモデルに関して先に観察されたものと類似していることに気付く。ｄｊｐｅｇの場合を除き、短いインターバルを用いて再構成することによる恩恵はない。全体として、探索を備えたインターバルベースのスキームは、ベースケースに対して１０％のスピードアップを与えた。
【００７６】
動的スキームは再構成を最小限にするように試みるので、キャッシュフラッシュは最小限に抑えられる。ｖｐｒは、フラッシュにより最大数のライトバックに遭遇し（４００Ｋ）、これは１％のＩＰＣ減速に帰着した。全体として、これらのフラッシュは０．３％のＩＰＣ低下に帰着した。
【００７７】
我々の結果は、クラスタの数が２つの重要なキャッシュ構造のために増加されるにつれて、通信並列性トレードオフが異なるプログラムのスケーラビリティに大幅に影響することを示した。このセクションにおいて、我々は、他の有意義なベースケースに対する我々の動的再構成アルゴリズムの適用可能性を確認する。通信の程度及び離れたＩＬＰの程度に影響する主要パラメータの内のいくつかは、クラスタ、ホップに亘る通信のレイテンシ、各クラスタにおける機能ユニットの数、及び各クラスタによってサポートされうる命令数（１クラスタ当りのレジスタ及び発行キューエントリの数）間の相互接続の選択である。
【００７８】
図７は、集中型キャッシュモデルを備えたグリッド相互接続を用いる効果を示す。より優れた連結性のために、通信はボトルネックがより少なく、１６クラスタ構造の性能は４クラスタ機構のそれより８％良い。簡単のため、我々は、探索を備えたインターバルベースのスキームによる結果を示すに止める。トレンドは前に観察されたとおりであるが、通信ペナルティは述べられたとおりでないので、最良のベースケースに対する全体的な改善は僅か７％である。細粒度再構成技術の使用は、リング相互接続に関するのと質的に類似した結果を与える。
【００７９】
また、我々は、クラスタ内の種々の資源のサイズに対する結果のセンシティビティを調べた。我々は、より少ない資源（１クラスタ当り、１０発行キューエントリと２０レジスタ）、及びより多くの資源（１クラスタ当り、２０発行キューエントリと４０レジスタ）を用いる効果を調べた。１クラスタ当りの資源が殆どない場合、利用可能な並列性を活用するために、より多くのクラスタが平均的に必要である。従って、１６クラスタ機構が好ましいベースケースであり、それに関するインターバルベースの動的機構の改善は僅か８％である。１クラスタ当り多くの資源がある場合、低ＩＬＰフェーズのために少数のクラスタを用いることは高度に有益である。その結果、１６クラスタベース上の改善は１３％である。各ホップに亘って通信のコストを２倍にすることは、高度に通信拘束された１６クラスタ機構に帰着する。動的機構を使用し、低ＩＬＰフェーズのためにより少ないクラスタを用いることによって、２３％の性能改善がみられた。
【００８０】
これらの結果は、インターバルベースのスキームに関して先のサブセクションでみられた改善に質的に類似しており、動的に調整可能な設計が広範囲のプロセッサ・パラメータに対して性能を大いに改善するのを助けることができることを示す。このように、通信並列性トレードオフ及びそのマネジメントは、将来の殆どのプロセッサにおいて重要となるであろう。
【００８１】
好ましい実施形態及びこれに対する変形例を上記で記載したが、本開示を検討した当業者は、本発明の範囲内においてその他の実施形態を実現することができることを容易に認識するであろう。たとえば、数値は、限定的でなく例示的であって、用いられたアルゴリズムの具体例である。したがって、本発明は、添付された特許請求の範囲によってのみ限定されると解釈されなければならない。
【図面の簡単な説明】
【００８２】
本発明とそれに対する変形例の好ましい実施形態は、図面との関係で開示されるであろう。
【００８３】
【図１】図１及び図２は、好ましい実施形態を実施することができる２つのクラスタ化プロセッサ構成を示すブロック図である。図１は、その内の一方を示すブロック図である。
【図２】図２は、その内のもう一方を示すブロック図である。
【図３】図３は、固定されたクラスタ構造に関するＩＰＣ（サイクル当り命令）性能を示すグラフである。
【図４】図４は、ベースケース及びインターバルベースのスキームのためのＩＰＣ性能を示すグラフである。
【図５】図５は、ベースケース、探索を備えたインターバルベースのアルゴリズム、及び２つの細粒度探索スキームに関するＩＰＣ性能を示すグラフである。
【図６】図６は、分散型キャッシュを備えたプロセッサモデルのためのダイナミックなインターバルベース機構に関するＩＰＣ性能を示すグラフである。
【図７】図７は、グリッド相互接続を備えたプロセッサモデルのためのダイナミックなインターバルベース機構に関するＩＰＣ性能を示すグラフである。
【符号の説明】
【００８４】
１００  プロセッサ
１０２（１０２−１〜１０２−４）  クラスタ
２００  プロセッサ
２０２（２０２−１）  クラスタ
【図１】
2008502083.tif 000007
【図２】
2008502083.tif 000008
【図３】
2008502083.tif 000009
【図４】
2008502083.tif 000010
【図５】
2008502083.tif 000011
【図６】
2008502083.tif 000012
【図７】
2008502083.tif 000013
【国際調査報告】
2008502083.tif 000014