(57)【要約】  本発明の実施例は、依存性チェーンを低減された幅の依存性チェーンのセットに分割し、１以上のクラスタの命令発行幅が依存性チェーンのサイズを収容するよう構成される１以上の依存性チェーンを１以上のクラスタリングされた依存性チェーンプロセッサにマッピングし、及び／又はトレースの複数の依存性チェーンをパラレルに処理することを有する方法、装置及びシステムを提供する。他の実施例が記載及び主張される。
2008515051.tif 000002
【特許請求の範囲】
【請求項１】
依存性チェーンを低減された幅の依存性チェーンのセットに分割するステップを有する方法。
【請求項２】
前記依存性チェーンを分割するステップは、
前記依存性チェーンの１以上の分割シナリオを設計するステップと、
前記分割シナリオの１以上に関する１以上の加重インデックス値をそれぞれ取得するステップと、
前記加重インデックス値の最大のものに関する分割シナリオに従って、前記依存性チェーンを前記低減された幅の依存性チェーンのセットに分割するステップと、
を有する、請求項１記載の方法。
【請求項３】
最大幅の依存性チェーンの分割に関する前記加重インデックス値の最大のものが所定の値より小さくなるまで、前記低減された幅の依存性チェーンのセットの前記最大幅の依存性チェーンに対して、前記設計ステップ、前記取得ステップ及び前記分割ステップを繰り返すステップを有する、請求項２記載の方法。
【請求項４】
前記１以上の加重インデックス値を取得するステップは、
前記分割シナリオに関するインデックス値を計算するステップと、
前記低減された幅の依存性チェーンのセットの最大幅の依存性チェーンの分割に基づく加重係数を決定するステップと、
前記インデックス値と前記加重係数との和を前記加重インデックス値に適用するステップと、
を有する、請求項２記載の方法。
【請求項５】
前記加重係数を決定するステップは、
前記最大幅の依存性チェーンの１以上の可能な分割にそれぞれ関連する１以上のインデックス値を計算するステップと、
前記インデックス値の最大のものを前記加重係数に適用するステップと、
を有する、請求項４記載の方法。
【請求項６】
前記計算するステップは、前記最大幅の依存性チェーンの低減された幅の依存性チェーンのセットにおける重複命令数を、最小命令数を有する前記低減された幅の依存性チェーンのセットの１つにおける重複しない命令数から減算するステップを有する、請求項５記載の方法。
【請求項７】
前記計算するステップは、前記低減された幅の依存性チェーンのセットにおける重複命令数を、最小命令数を有する前記低減された幅の依存性チェーンのセットの１つにおける重複しない命令数から減算するステップを有する、請求項４記載の方法。
【請求項８】
依存性チェーンを低減された幅の依存性チェーンのセットに分割することが可能なプロセッサを有する装置。
【請求項９】
前記プロセッサは、最大加重インデックス値に関する分割シナリオに従って、前記依存性チェーンを前記低減された幅の依存性チェーンのセットに分割することが可能である、請求項８記載の装置。
【請求項１０】
前記プロセッサは、前記最大加重インデックス値が所定の値より小さくなるまで、前記低減された幅の依存性チェーンのセットの最大幅の依存性チェーンに対して、前記分割を繰り返すことが可能である、請求項９記載の装置。
【請求項１１】
前記プロセッサは、前記分割シナリオに関するインデックス値を計算し、前記低減された幅の依存性チェーンのセットの最大幅の依存性チェーンの分割に基づく加重係数を決定し、前記インデックス値と前記加重係数との和を前記加重インデックス値に適用することが可能である、請求項９記載の装置。
【請求項１２】
前記プロセッサは、前記最大幅の依存性チェーンの１以上の可能な分割にそれぞれ関連する１以上のインデックス値を計算し、前記インデックス値の最大のものを前記加重係数に適用することが可能である、請求項１１記載の装置。
【請求項１３】
前記プロセッサは、前記最大幅の依存性チェーンの低減された幅の依存性チェーンのセットにおける重複命令数を、最小命令数を有する前記低減された幅の依存性チェーンのセットの１つにおける重複しない命令数から減算することが可能である、請求項１２記載の装置。
【請求項１４】
前記プロセッサは、前記低減された幅の依存性チェーンのセットにおける重複命令数を、最小命令数を有する前記低減された幅の依存性チェーンのセットの１つにおける重複しない命令数から減算することが可能である、請求項１１記載の装置。
【請求項１５】
ターゲット命令のセットの依存性チェーンを低減された幅の依存性チェーンのセットに分割することが可能なプロセッサと、
前記ターゲット命令のセットを格納するメモリと、
を有する計算プラットフォーム。
【請求項１６】
前記プロセッサは、最大加重インデックス値に関する分割シナリオに従って、前記依存性チェーンを前記低減された幅の依存性チェーンのセットに分割することが可能である、請求項１５記載の計算プラットフォーム。
【請求項１７】
前記プロセッサは、前記低減された幅の依存性チェーンのセットの最大幅の依存性チェーンに対して、前記依存性チェーンの分割を繰り返すことが可能である、請求項１６記載の計算プラットフォーム。
【請求項１８】
前記プロセッサは、前記分割シナリオに関するインデックス値を計算し、前記低減された幅の依存性チェーンのセットの最大幅の依存性チェーンの分割に基づく加重係数を決定し、前記インデックス値と前記加重係数との和を前記加重インデックス値に適用することが可能である、請求項１６記載の計算プラットフォーム。
【請求項１９】
前記プロセッサは、前記最大幅の依存性チェーンの１以上の可能な分割にそれぞれ関連する１以上のインデックス値を計算し、前記１以上の可能な分割に関連する前記インデックス値の最大のものを前記加重係数に適用することが可能である、請求項１８記載の計算プラットフォーム。
【請求項２０】
マシーンにより実行されると、依存性チェーンを低減された幅の依存性チェーンのセットに分割する、マシーンにより可読な命令を有するプログラム記憶装置。
【請求項２１】
前記依存性チェーンを分割する命令は、最大加重インデックス値に関する分割シナリオに従って、前記依存性チェーンを前記低減された幅の依存性チェーンのセットに分割する、請求項２０記載のプログラム記憶装置。
【請求項２２】
前記依存性チェーンを分割する命令は、前記最大加重インデックス値が所定の値より小さくなるまで、前記分割を繰り返す、請求項２１記載のプログラム記憶装置。
【請求項２３】
トレースの複数の依存性チェーンをパラレルに処理するステップを有する方法。
【請求項２４】
前記処理するステップは、
所定のスキームに従って、前記依存性チェーンの少なくとも一部を複数の処理パスに割り当てるステップと、
前記処理パスの少なくとも一部を互いに独立に実行するステップと、
を有する、請求項２３記載の方法。
【請求項２５】
前記実行するステップは、前記処理パスの１以上の内部で中間データをローカルに読み書きするステップを有する、請求項２４記載の方法。
【請求項２６】
前記実行するステップは、前記処理パスの２以上によってグローバルデータを読み書きするステップを有する、請求項２４記載の方法。
【請求項２７】
前記処理するステップは、例外処理又は予測ミスが発生すると、非依存性チェーンモードにより前記依存性チェーンの１以上を実行するステップを有する、請求項２３記載の方法。
【請求項２８】
前記依存性チェーンの何れの一部ともならないプログラム命令を非依存性チェーンモードにより処理するステップを有する、請求項２３記載の方法。
【請求項２９】
前記プログラム命令を処理するステップは、複数の処理パスの１つにより前記プログラム命令を実行するステップを有する、請求項２８記載の方法。
【請求項３０】
前記プログラム命令を処理するステップは、複数の処理パスの最大幅のパスにおいて前記プログラム命令を実行するステップを有する、請求項２８記載の方法。
【請求項３１】
トレースの複数の依存性チェーンをパラレルに処理することが可能なプロセッサを有する装置。
【請求項３２】
前記プロセッサは、前記依存性チェーンの少なくとも１つを独立に実行するための複数のクラスタを有する、請求項３１記載の装置。
【請求項３３】
前記クラスタの１以上は、前記依存性チェーンの実行中に使用されるデータを格納するローカルメモリを有する、請求項３２記載の装置。
【請求項３４】
前記ローカルメモリは、ローカルレジスタを有する、請求項３３記載の装置。
【請求項３５】
前記プロセッサは、前記クラスタの２以上により使用されるデータを格納するグローバルメモリを有する、請求項３２記載の装置。
【請求項３６】
前記グローバルメモリは、グローバルレジスタを有する、請求項３５記載の装置。
【請求項３７】
前記プロセッサは、例外処理又は予測ミスが発生すると、非依存性チェーンモードにより前記依存性チェーンの１以上を実行することが可能である、請求項３１記載の装置。
【請求項３８】
前記プロセッサは、前記依存性チェーンの何れの一部ともならないプログラム命令を非依存性チェーンモードにより実行することが可能である、請求項３１記載の装置。
【請求項３９】
前記プロセッサは、複数のクラスタの１つにより前記プログラム命令を実行する、請求項３８記載の装置。
【請求項４０】
前記プロセッサは、複数のクラスタの最大幅のクラスタにおいて前記プログラム命令を実行する、請求項３８記載の装置。
【請求項４１】
ターゲット命令のセットのトレースの複数の依存性チェーンをパラレルに処理することが可能なプロセッサと、
前記ターゲット命令のセットを格納するメモリと、
を有する計算プラットフォーム。
【請求項４２】
前記プロセッサは、前記依存性チェーンの少なくとも１つを独立に実行するための複数のクラスタを有する、請求項４１記載の計算プラットフォーム。
【請求項４３】
前記プロセッサは、例外処理又は予測ミスが発生すると、非依存性チェーンモードにより前記依存性チェーンの１以上を実行することが可能である、請求項４１記載の計算プラットフォーム。
【請求項４４】
マシーンにより実行されると、トレースの複数の依存性チェーンをパラレルに処理する、マシーンにより可読な命令を有するプログラム記憶装置。
【請求項４５】
前記複数の依存性チェーンを処理する命令は、
所定のスキームに従って、前記依存性チェーンの少なくとも一部を複数の処理パスに割り当て、
前記処理パスの少なくとも一部を互いに独立に実行する、請求項４４記載のプログラム記憶装置。
【請求項４６】
複数の依存性チェーンを１以上のクラスタにマッピングするステップを有する方法であって、
前記クラスタの１以上の命令発行幅は、前記依存性チェーンのサイズを収容するよう構成される方法。
【請求項４７】
前記マッピングするステップは、
前記依存性チェーンを該依存性チェーンの幅によりソートするステップと、
前記クラスタを該クラスタの命令発行幅によりソートするステップと、
前記依存性チェーンと前記クラスタとをソートされた順序により関連付けるステップと、
を有する、請求項４６記載の方法。
【請求項４８】
最小ロード値を有するクラスタを特定するステップと、
マッピングされていない依存性チェーンを前記最小ロードクラスタに関連付けるステップと、
所定の基準が満たされるまで、前記特定するステップと前記関連付けるステップとを繰り返すステップと、
をさらに有する、請求項４７記載の方法。
【請求項４９】
前記マッピングするステップは、
プログラム命令のセットを識別子の文字列に変換するステップと、
前記複数の依存性チェーンを生成するため、前記識別子の文字列を圧縮するステップと、
を有する、請求項４６記載の方法。
【請求項５０】
少なくとも１つの命令トレースを取得するため、前記複数の依存性チェーンを構文解析するステップをさらに有する、請求項４９記載の方法。
【請求項５１】
前記圧縮するステップは、Ｓｑｕｉｔｕｒ圧縮アルゴリズムを利用して前記識別子の文字列を圧縮するステップを有する、請求項４９記載の方法。
【請求項５２】
前記変換するステップは、
前記プログラム命令を１以上のアトミックブロックに分割するステップと、
前記１以上のアトミックブロックに一意的な識別子を割り当てるステップと、
を有する、請求項４９記載の方法。
【請求項５３】
命令重複アルゴリズムを利用して、前記複数の依存性チェーンを最適化するステップを有する、請求項４９記載の方法。
【請求項５４】
複数の依存性チェーンを１以上のクラスタにマッピングすることが可能なプロセッサを有する装置であって、
前記クラスタの１以上の命令発行幅は、前記依存性チェーンのサイズを収容するよう構成される装置。
【請求項５５】
前記プロセッサは、前記依存性チェーンを該依存性チェーンの幅によりソートし、前記クラスタを該クラスタの命令発行幅によりソートし、前記依存性チェーンと前記クラスタとをソートされた順序により関連付けることが可能である、請求項５４記載の装置。
【請求項５６】
前記プロセッサは、最小ロード値を有するクラスタを特定し、マッピングされていない依存性チェーンを前記最小ロードクラスタに関連付けることを、所定の基準が満たされるまで繰り返すことが可能である、請求項５５記載の装置。
【請求項５７】
前記プロセッサは、プログラム命令のセットを識別子の文字列に変換し、前記複数の依存性チェーンを生成するため、前記識別子の文字列を圧縮することが可能である、請求項５４記載の装置。
【請求項５８】
前記プロセッサは、少なくとも１つの命令トレースを取得するため、前記複数の依存性チェーンを構文解析することが可能である、請求項５７記載の装置。
【請求項５９】
前記プロセッサは、前記プログラム命令を１以上のアトミックブロックに分割し、前記１以上のアトミックブロックに一意的な識別子を割り当てることが可能である、請求項５７記載の装置。
【請求項６０】
前記プロセッサは、命令重複アルゴリズムを利用して、前記複数の依存性チェーンを最適化することが可能である、請求項５７記載の装置。
【請求項６１】
ターゲット命令のセットの複数の依存性チェーンを１以上のクラスタにマッピングすることが可能なプロセッサと、
前記ターゲット命令のセットを格納するメモリと、
を有する計算プラットフォームであって、
前記クラスタの１以上の命令発行幅は、前記依存性チェーンのサイズを収容するよう構成される計算プロットフォーム。
【請求項６２】
前記プロセッサは、前記依存性チェーンを該依存性チェーンの幅によりソートし、前記クラスタを該クラスタの命令発行幅によりソートし、前記依存性チェーンと前記クラスタとをソートされた順序により関連付けることが可能である、請求項６１記載の計算プラットフォーム。
【請求項６３】
前記プロセッサは、最小ロード値を有するクラスタを特定し、マッピングされていない依存性チェーンを前記最小ロードクラスタに関連付けることを、所定の基準が満たされるまで繰り返すことが可能である、請求項６２記載の計算プラットフォーム。
【請求項６４】
マシーンにより実行されると、ターゲット命令のセットの複数の依存性チェーンを１以上のクラスタにマッピングする、マシーンにより可読な命令を有するプログラム記憶装置。
【請求項６５】
前記マッピングする命令は、
前記依存性チェーンを該依存性チェーンの幅によりソートし、
前記クラスタを該クラスタの命令発行幅によりソートし、
前記依存性チェーンと前記クラスタとをソートされた順序により関連付ける、請求項６４記載のプログラム記憶装置。
【請求項６６】
最小ロード値を有するクラスタを特定し、
マッピングされていない依存性チェーンを前記最小ロードクラスタに関連付け、
所定の基準が満たされるまで、前記特定と前記関連付けとを繰り返す、請求項６５記載のプログラム記憶装置。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［発明の背景］
従来のコンピュータは、逐次的順序によりモノリシックにコンピュータプログラム命令を実行するシングルパイプラインタイププロセッサを実現する。当該分野においてＩＬＰ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｌｅｖｅｌ  Ｐａｒａｌｌｅｌｉｓｍ）としても知られている命令レベルにおけるパラレル処理のパワーを最大化するため、このようなプロセッサはコンパイラにおけるアグレッシブな最適化を採用するかもしれない。プロセッサのパフォーマンスを向上させる他の方法は、非逐次的順序により命令を実行可能なアウト・オブ・オーダパイプラインプロセッサを実現することを含むかもしれない。しかしながら、このような実現は、ハードウェアとソフトウェアの双方における複雑さを増大させるという欠点を有している。他の選択肢は、より高い周波数により動作可能なプロセッサを設計することであるが、これはキャッシュ／メモリへのアクセス遅延の増大を招く可能性があり、及び／又はＩＰＣ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｐｅｒ  Ｃｙｃｌｅ）などによって測定される処理効率を低下させる可能性がある。
【０００２】
複雑さに関して効率的なマイクロアーキテクチャを設計するためのプロセッサリソースのクラスタリングに関する研究が最近行われている。１つの研究によると、モノリシックパイプラインを使用する代わりに、各クラスタがシングルモノリシックパイプラインより低い複雑さを有する複数のクラスタを利用することが提案されてきた。この研究によると、コンピュータプログラム命令が、遅延を低減するためクラスタ間の通信を最小化する目的により実行中に各クラスタにディスパッチされるかもしれない。他の研究によると、命令間の依存関係を利用した依存性チェーンに基づく実行が、プロセッサデザインの複雑さを軽減することが提案されてきた。
【０００３】
［発明の実施例の詳細な説明］
以下の詳細な説明では、本発明の実施例の完全なる理解を提供するため、多数の具体的詳細が与えられている。しかしながら、本発明の実施例がこれら具体的詳細なしに実現可能であるということは、当業者により理解されるであろう。他の実施例では、本発明の実施例を不明りょうにすることを回避するため、周知の方法及び処理については詳細には説明されない。
【０００４】
以下の詳細な説明のいくつかの部分は、コンピュータメモリ内のデータビット又はバイナリデジタル信号に対する処理のアルゴリズム及び記号表現に関して提供されている。これらのアルゴリズム的記述及び表現は、他の当業者に自らの研究の内容を伝えるのにデータ処理分野の当業者により利用されている技術であるかもしれない。
【０００５】
ここでの及び一般には、アルゴリズムは、所望の結果を導く動作又は処理の自己矛盾のないシーケンスであるとみなされる。これらは、物理量の物理的操作を含む。必要ではないが通常は、これらの量は格納、転送、合成、比較及び操作が可能な電気又は磁気信号の形態をとる。主に通常の使用のため、これらの信号をビット、値、要素、シンボル、文字、項、数などと参照することがときに便利であることがわかっている。しかしながら、上記及び同様の用語のすべてが適切な物理量に関連付けされ、これらの量に適用される単なる便宜上のラベルであるということが理解されるべきである。
【０００６】
特段断りがない場合、以下の説明から明らかなように、明細書全体を通じて、「処理」、「計算」、「決定」などの用語を使用した説明は、計算システムのレジスタ及び／又はメモリ内の電子などの物理量として表現されるデータを、計算システムのメモリ、レジスタ又は情報ストレージ、伝送装置、表示装置などの内部の物理量として同様に表現される他のデータに操作及び／又は変換するコンピュータ、計算システム又は同様の電子計算装置のアクション及び／又はプロセスを表すことが認識される。
【０００７】
本発明のいくつかの実施例は、例えば、マシーンにより実行される場合、当該マシーンに本発明の実施例による方法及び／又は処理を実行される命令又は命令セットを格納可能なマシーン可読媒体又は物を用いて実現可能である。このようなマシーンは、例えば、何れか適切な処理プラットフォーム、計算プラットフォーム、計算装置、処理装置、計算システム、処理システム、コンピュータ、プロセッサなどを含み、ハードウェア及び／又はソフトウェアの何れか適切な組み合わせを利用して実現可能である。マシーン可読媒体又は物は、例えば、メモリ、着脱可能若しくは着脱不可な媒体、消去可能若しくは消去不可な媒体、書き込み可能若しくは書き換え可能な媒体、デジタル若しくはアナログ媒体、ハードディスク、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅｃｏｒｄａｂｌｅ）、ＣＤ−ＲＷ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  ＲｅＷｒｉｔａｂｌｅ）、光ディスク、磁気媒体、各種ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、テープ、カセットなど、何れか適切なタイプの記憶ユニット、記憶装置、記憶物、記憶媒体、ストレージ装置、ストレージ物、ストレージ媒体及び／又はストレージユニットを含むかもしれない。命令は、ソースコード、コンパイルコード、インタープリットコード、実行可能コード、静的コード、動的コードなど何れか適切なタイプのコードを含み、Ｃ、Ｃ＋＋、Ｊａｖａ（登録商標）、ＢＡＳＩＣ、Ｐａｓｃａｌ、Ｆｏｒｔｒａｎ、Ｃｏｂｏｌ、アセンブリ言語、マシーンコードなど、何れか適切なハイレベル、ローレベル、オブジェクト指向、ビジュアル、コンパイル及び／又はインタープリットプログラミング言語を用いて実現可能である。
【０００８】
本発明の実施例は、ここでの処理を実行する装置を含むかもしれない。当該装置は、所望する目的のため特別に構成されるか、又はコンピュータに格納されるコンピュータプログラムにより選択的に動作又は再構成される汎用コンピュータを含むかもしれない。このようなコンピュータプログラムは、以下に限定されるものではないが、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）、ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｏｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）、磁気若しくは光カードなどを含む任意のタイプのディスク、又は電子命令を格納するのに適し、コンピュータシステムバスに接続可能な他の任意のタイプの媒体などのコンピュータ可読ストレージ媒体に格納されてもよい。
【０００９】
ここに提示されるプロセス及びディスプレイは、何れか特定のコンピュータ又は他の装置に固有に関連付けされるものではない。各種汎用システムが、ここでの教示に従ってプログラムにより利用可能であり、又は所望の方法を実行するより特化した装置を構成することが便利であるとわかるかもしれない。これら各種システムの所望の構成は、以下の記載から明らかとなるであろう。さらに、本発明の実施例は、何れか特定のプログラミング言語を参照して記載されるものでない。ここに記載されるような本発明の教示を実現するため、各種プログラミング言語が利用可能であるということは理解されるであろう。
【００１０】
以下の説明において、各種図面、フローチャート、モデル及び記載は、本出願において提案される本発明の各種実施例を説明し、その内容を効果的に伝えるための手段として提供される。それらが単なる一例となるサンプルとして提供され、本発明を限定するものとして解釈されるべきでないということは、当業者に理解されるであろう。
【００１１】
図１は、本発明の実施例によるクラスタリングされた依存性チェーンプロセッサ（ＤＣＰ）１２に動作可能に接続されるメモリ６を含む計算プラットフォームなどの装置２を示すブロック図である。メモリ６は、ソースコードなどのソース命令セット８と、ＤＣＰ１２に適したバイナリ実行可能コードなどのターゲット命令セット１０とを少なくとも格納可能であるかもしれない。装置２はさらに、以下に詳細に説明されるように、本発明の実施例による最適化アルゴリズム３０とマッピングアルゴリズム３２とを有するコンパイラ１１を含む。ソース命令セット８は、ダイナミックトランスレータ、バイナリ計測ツールなどを有するコンパイラ１１などによって、オンライン又はオフラインコンパイル処理を利用してターゲット命令セット１０にコンパイル可能である。ターゲット命令セット１０は、ＤＣＰ１２のマイクロアーキテクチャに従って構成される依存性チェーン（ＤＣ）トレース（ＤＣトレース）と呼ばれるトレースを含むかもしれない。ＤＣＰ１２に用いられるＤＣトレースは、数百の命令を有する物など比較的に長いトレースである。以下に詳細に説明されるようなオフラインコンパイル方法によって構成されるこのような長いトレースは、従来のトレースプロセッサによって使用されるトレースよりかなり長いものとなる。従来のトレースプロセッサは、ハードウェアを利用して実行中にトレースを構成し、ハードウェアの限定された命令ウィンドウによって、このように構成されるトレースの長さは一般には、トレース毎に１６〜３２の命令など短いものとなる。長いトレースは、本発明の実施例によると、アグレッシブトレーススケジューリングを介してＩＬＰ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｌｅｖｅｌ  Ｐａｒａｌｌｅｌｉｓｍ）を向上させるかもしれない。
【００１２】
ＤＣトレースは、１以上の依存性チェーン（ＤＣ）を含むかもしれない。当該分野において知られているように、依存性チェーン（ＤＣ）は、ＤＣトレースのデータ依存性のグラフィカル表示における最大接続コンポーネントである。本発明の実施例によると、ターゲット命令セット１０のＤＣトレース内部のＤＣは、より小さな幅を有するＤＣセットを生成するため、最適化アルゴリズム３０により処理される。最適化されたＤＣは、マッピングアルゴリズム３２に基づき、クラスタ１４、１６及び１８などのＤＣＰ１２のクラスタセットにマッピングされる。
【００１３】
本発明の実施例によると、ＤＣＰ１２は、所望のトレースベースの実行モデルに従って構成されたクラスタリングされたプロセッサを有するかもしれない。クラスタ１４、１６及び／又は１８などのＤＣＰのクラスタは、スーパースカラー（ｓｕｐｅｒｓｃａｌａｒ）イン・オーダ又はアウト・オブ・オーダパイプラインであっても良く、異質なＤＣＰを構成するため異なる命令発行幅を有してもよいし、又は同質なＤＣＰを構成するため同一の命令発行幅を有するようにしてもよい。ＤＣＰマイクロアーキテクチャ１２はさらに、キャッシュ２０とレジスタ２２とを有する。
【００１４】
図２は、本発明の実施例によるそれぞれ３ワイド、２ワイド及び１ワイドのイン・オーダパイプラインクラスタなどの３つの処理パスを有するよう構成される異質なクラスタリングされたＤＣＰ２００のマイクロアーキテクチャを示すブロック図である。ＤＣＰ２００は、２つの動作モード、すなわち、「ホット（ｈｏｔ）」パスを実行などするためのＤＣモードと、「コールド（ｃｏｌｄ）」パスを実行などするための非ＤＣモードにより動作可能である。「ホット」パスと「コールド」パスの両方が、バイナリ実行可能コードを含むターゲット命令セット１０（図１）に含まれるかもしれない。
【００１５】
コンピュータプログラムでは、「ホット」パスは、静的なプログラム命令の１０〜２０％などの相対的に小さな部分を構成するが、相対的に頻繁に実行される可能性があり、動的に実行される命令に関して全体の計算の８０〜９０％などの相対的に大きな部分を担うプログラムパスである。「コールド」パスは、静的なプログラム命令の８０〜９０％などの相対的に大きな部分を構成するが、相対的に頻繁には実行されず、動的に実行される命令に関して計算全体の１０〜２０％などの相対的に小さな部分を担うプログラムパスである。本発明の実施例によると、ＤＣＰ１２のマイクロアーキテクチャについて構成されたＤＣトレースは、プログラムの「ホット」パスを表すかもしれない。
【００１６】
非ＤＣ動作モードでは、ＤＣＰ２００は、命令フェッチ（Ｉキャッシュ）２０２から逐次的にコンピュータプログラム命令をフェッチする。フェッチされた命令の１以上は、ＤＣＰ２００のクラスタ２１２の最も幅の大きな処理パスなどの処理パスの１つに受け付けられた順序に従って発行されてもよい。クラスタ２１４やクラスタ２１６などの残りの処理パスは、ＤＣＰ２００の非ＤＣ動作モード中は未使用状態とされるかもしれない。本発明の実施例によると、ＤＣＰ２００は、命令実行中などに非ＤＣ動作モードからＤＣ動作モードにスイッチされるかもしれない。例えば、トレース予測装置（図示せず）は、トレースがまもなく実行されることを予測するのに利用可能であることが、当該技術においてしられている。トレース予測装置は、トレースが予測されると、非ＤＣ動作モードからＤＣ動作モードにＤＣＰ２００をスイッチするよう実現されるかもしれない。
【００１７】
ＤＣ動作モードでは、命令は、Ｉキャッシュ２０２の代わりに依存性チェーントレースキャッシュ（ＤＣキャッシュ）２０４からフェッチされる。その後、依存性チェーン（ＤＣ）は、所定の割当スキームに従って、図２のようなクラスタ２１２、２１４及び２１６などの適切な処理パスに向けられる。この予めの割当は、以下で詳細に説明されるように、ＤＣからクラスタへのマッピングプロセス中に実行されるかもしれない。
【００１８】
あるトレースのＤＣは、同一トレース内のＤＣ間にデータ依存性が存在しないように、本来的には互いに独立している。トレースの各ＤＣが、クラスタ２１２、２１４及び／又は２１６などの異なるクラスタに発行されると、１つのＤＣは他のクラスタの他のＤＣを参照することなく、クラス内で独立に実行されるかもしれない。このため、複数のＤＣがそれぞれ、異なるクラスタ内で異なるレートによりパラレルに実行されるかもしれない。例えば、クラスタ２１２内のＤＣは、クラスタ２１４又はクラスタ２１６の何れかの内部のＤＣに先行して実行されるかもしれない。
【００１９】
本発明の実施例によると、図２のＤＣＰ２００は、２レベルのレジスタ階層構造を有するかもしれない。このアーキテクチャの１以上のクラスタは、例えば、レジスタ２２２、２２４又は２２６などの８エントリレジスタなどである自らの１つのローカルレジスタを有するかもしれない。さらに、１以上のクラスタによってアクセス可能なグローバルレジスタ２３２が存在するかもしれない。あるクラスタ内のＤＣの実行中の中間値は、当該クラスタのローカルレジスタに対して読み書きされる。グローバルレジスタは、１以上のクラスタにより共有され、隣接するトレースにより生成及び／又は利用されるデータを読み書きするのに利用されるかもしれない。
【００２０】
異なるクラスタにおいて同時に実行されるＤＣが同一トレースから発行されるため、それらは互いに完全にデータ独立し、このようなＤＣ間において又は各自のクラスタ間において値を通信する必要はないかもしれない。ＤＣＰ２００は、グローバルレジスタ２３２の応答の遅延に対してあまり影響を受けないかもしれない。本発明の実施例によると、グローバルレジスタ２３２は、オンチップレベル１（Ｌ１）データキャッシュメモリなどの何れか適切なタイプのストレージ又は他のデータ格納媒体を用いて実現可能である（図２）。このような実現形態では、レジスタ２３２への読み書きは、明示的なロード及びストア処理となる。
【００２１】
本発明の実施例によると、ＤＣＰ２００は、オンチップストレージを使用して、あるＤＣトレースの再実行が必要となる状況などで使用されるべきグローバルレジスタ２３２の値のチェックポイントコピーを格納する。再実行は、例えば、トレースがＤＣ動作モードにより実行されているときの例外処理やＤＣトレースの予測ミスなどにより、必要となるかもしれない。その後、ＤＣＰ２００は、非ＤＣ動作モードに戻り、メモリにセーブされているグローバルレジスタ２３２のチェックポイントコピーからの値を利用して、最後に発行されたトレースの始めから命令を再実行することをスタートするかもしれない。このようなケースでは、Ｌ１データキャッシュなどのメモリとＤＣＰ２００との間の通信を処理するため、さらなるロード及び／又はストア命令が実現されるかもしれない（図２）。
【００２２】
図３は、本発明の実施例による長いＤＣトレースを構成する方法を示す概略的なフローチャートである。長いＤＣトレースの構成は、当該分野において知られるようなエンハンストＷＰＰ（Ｗｈｏｌｅ  Ｐｒｏｇｒａｍ  Ｐａｔｈ）アプローチ又は他の何れか適切な方法に基づくものであってもよく、より長いトレースのためなどオンライン又はオフラインにより実行されてもよい。
【００２３】
コンパイラ１１（図１）などのコンパイラは、ＤＣトレースを構成するため、ＤＣＰ１２（図１）などのプロセッサ上で実行される。本発明の他の実施例では、コンパイラ１１は、特定の実現形態及び／又は設計要求に従って、専用プロセッサ及び／又は汎用プロセッサなどの何れか適切なタイプのプロセッサ上で実行されるかもしれない。ＤＣトレースは、ブロック３１０により示されるように、命令実行プロファイルを収集し、命令実行プロファイルをストリームブロックに分割することによって構成される。本出願におけるストリームブロックは、コンピュータプログラムの取得されるブランチ間の命令シーケンスを表す。一意的な各ストリームブロックは、当該ストリームブロックにおけるすべての命令に対する命令アドレスシーケンスにより表される。１以上のストリームブロックの組み合わせが、その後、ブロック３２０に示されるように、一意的なストリーム識別子に割り当てられる。もとの命令実行トレースは、ブロック３３０に示されるように、ストリーム識別子の文字列に変換される。
【００２４】
ブロック３４０に示されるように、上述のように生成されるストリーム識別子の文字列は、その後に当該分野において知られているようなＳｅｑｕｉｔｕｒアルゴリズムなどの圧縮アルゴリズムにより処理される。Ｓｅｑｕｉｔｕｒアルゴリズムは、文脈自由文法により文字列を表現することによって、所与のストリーム識別子の入力文字列に対するコンパクトな表現を生成するかもしれない。当該アルゴリズムは、複数回繰り返されるストリーム識別子のシーケンス及び文法規則を１つの文法規則と置換する。当該圧縮アルゴリズムにより生成されるストリーム識別子の文字列の結果として得られる文法表現は、有向アサイクリックグラフ（ＤＡＧ）であるかもしれない（ブロック３５０）。その後、１以上の頻出するストリーム識別子のシーケンスが、ＤＡＧを構文解析することによって特定及び抽出される（ブロック３６０）。繰り返し出現するストリーム識別子のシーケンスは、効果的に連結された命令シーケンスに対応する。この一意的な繰り返し出現する命令シーケンスはＤＣトレースと呼ばれ、それから命令依存性チェーンがさらに抽出される。
【００２５】
ＤＣトレースの命令データ依存性は、独立した依存性チェーン（ＤＣ）のセットとしてグラフィカル表示される。トレースの依存性チェーンセットのグラフィカル表示は、ここではデータ依存性グラフ（ＤＤＧ）と呼ばれる。図４は、３つのＤＣ、すなわち、ＤＣ１、ＤＣ２及びＤＣ３を含むＤＤＧ４００の一例となるサンプルの図である。図４のＤＤＧを構文解析することによって取得可能な対応するサンプルＤＣトレースが、以下のテーブル１に示される。ＤＣトレースは、対応する文法規則セットに関して連続する識別子シーケンスによって表現されるかもしれない。
【００２６】
【表１】
2008515051.tif 000003
【００２７】
図５は、本発明の実施例によるＤＤＧを解析し、適切に選択された命令発行幅によるクラスタのＤＣを構成する方法を示すブロック図である。ＤＣの重要なトポロジー固有の性質は、「ＤＣ幅」として知られるメトリックであることが認識されている。ＤＣ幅は、例えば、ＤＣのデータ依存性のグラフィカル表現における最長のパス長により分割されるＤＣ内部の合計命令数として測定されるかもしれない。本発明の実施例によると、プロセッサは、ＤＣトレース内のＤＣの１以上のＤＣ幅の値を計算し（ブロック５１０）、ＤＣのＤＣ幅及び／又は命令数に従ってＤＣの相対的な優先順位を特定する（ブロック５２０）ことによって、ＤＣ解析方法を実現する。最大ＤＣ幅を有するＤＣはまた、最大命令数を有し、このため、優先的なＤＣであるかもしれない。従って、最大ＤＣ長を有するＤＣは、最も高い優先度のＤＣ、すなわち、第１優先ＤＣ（ドミナントＤＣ）であるかもしれない。２番目に大きなＤＣ幅を有するＤＣは、第２優先ＤＣと呼ばれ、以下同様とされる。図４に示される実施例では、ＤＣ２が最大ＤＣ幅を有し、このため、ドミナントＤＣであり、ＤＣ３が第２優先ＤＣである。
【００２８】
ＤＣＰ１２（図１）では、あるＤＣ内のすべての命令は、１つのクラスタ内で実行される。このため、すべてのＤＣのうちの最大ＤＣ幅は、利用可能なＩＬＰを最大化するため、クラスタに求められる最小命令発行幅のメトリックを表すかもしれない。本発明の実施例によると、もとのＤＣより小さなＤＣ幅を有する新たなドミナントＤＣセットを生成するため、ＤＣ最適化アルゴリズムがドミナントＤＣに適用される（ブロック５３０）。結果として得られるドミナントＤＣにＤＣ最適化アルゴリズムを繰り返し適用することによって、クラスタの最大命令発行幅に対するより低い制限によるより効率的なクラスタの設計が可能となる（ブロック５４０）。
【００２９】
本発明の実施例によると、第１優先ＤＣに対する１つのみの幅の大きなクラスタと、残りのＤＣに対するいくつかの幅の小さなクラスタとを有するものなどの異質なクラスタ構造を設計することが効果的であるかもしれない。異質なクラスタ構成は、例えば、異質なクラスタ構成はより小さなバイパスネットワークロジックを利用するため、同質なクラスタ構成より少ないエリアしか必要としないかもしれない。
【００３０】
図６は、本発明の実施例による命令重複処理に基づくＤＣ最適化アルゴリズムを示す概念的なブロック図である。命令重複アルゴリズムは、図６において「ａｂｃｄｅ」として示される依存性チェーンからスタートする（６１０）。
【００３１】
分割の有効数（ａｄｖａｎｔａｇｅ  ｎｕｍｂｅｒ）は、双方の命令セットにおいて検出される重複した命令の個数だけ減算され、他方の命令セットにおいて重複しないスプリットの結果として２つの結果として得られる命令セットの小さい方の命令セットによって表される真の命令の個数として規定される。ドミナントＤＣの命令「ａｂｃｄｅ」は、計算された有効数１１などの計算されたインデックス値などに基づき、ＤＣ「ａｂｃ」とＤＣ「ｄｅ」として示されるより小さな２つの命令セットに分割される（６２０）。図６に示されるように、命令セット「ａｂｃｄｅ」がより小さな２つの命令セット「ａｂｃ」と「ｄｅ」に分割されると、「ａｂｃ」と「ｄｅ」のうちより小さなセット「ａｂｃ」は、白い丸印により示されるような１２の真の命令を有する。「ａｂｃ」と「ｄｅ」の２つの命令セットは、黒い丸印により示されるような１つの重複した命令を有する。従って、この計算は１１の有効数を与える。
【００３２】
次のドミナントＤＣであるＤＣ「ｄｅ」が、その後に、分割に関連する４の有効数に基づき、例えば、ＤＣ「ｄ」とＤＣ「ｅ」に分割される（６３０）。同様に、ＤＣ「ａｂｃ」は、１の有効に対してはＤＣ「ａｂ」とＤＣ「ｃ」に分割される（６４０）。本例では、ＤＣ「ａｂ」の分割に係る有効数が、多数の命令が重複すると分割が要求することを示す負の数となるため、ＤＣ「ａｂ」に対してさらなる最適化は必要とされないことが認識される。上記実施例は、計算された有効数に基づきＤＣを分割することに関連するが、本発明の一実施例によると、ＤＣは他の何れか計算されたインデックス値に基づき分割されるかもしれない。
【００３３】
図７は、図６に概念的に示されるように、本発明の実施例によるプロセッサ１２（図１）などにより実行されるエンハンストＤＣ最適化プロセスをさらなる説明する概略的なフォローチャートである。最適化アルゴリズム、すなわち、命令重複アルゴリズムは、最適化後、結果として得られる最大のＤＣが可能な限り小さくなり、プロセス中の重複命令数が最小値に維持されるなど、低減されるという目的を実現するよう構成される。すなわち、最適化プロセスは、ＤＣをリーフＤＤＣの最適なグループ化に分割するプロセスとして理解されるかもしれない。
【００３４】
リーフ命令は、ＤＣの命令のサブセットを含む。ＤＣのリーフ命令のリーフＤＤＧ（ＬＤＤＧ）は、当該ＤＣに当該リーフ命令を実行するため入力値を生成するのに必要な命令サブセットを有する。ＬＤＤＧのセットは、所与のＤＣに対する可能な最大分割である。例えば、図６に示されるように、「ａ」、「ｂ」、「ｃ」、「ｄ」及び「ｅ」は、可能な最大分割を表すもとのＤＣ「ａｂｃｄｅ」の５つのリーフのＬＤＤＧである。しかしながら、図６に説明されるように、可能な最大分割を実行することは、いくつかのケースでは、多数の重複命令を生じさせる。
【００３５】
本発明の実施例によると、命令重複アルゴリズムは、すべてのＬＤＤＧを１つのセットにグループ化することから開始される（７０２）。複数の分割シナリオから、可能性のある分割が選択され、当該分割に関する有効数などのインデックス値Ａ１が計算される（７０４）。
【００３６】
アルゴリズムは、「加重係数」Ａ２を計算し続ける。Ａ２は、結果として得られるドミナントＤＣの分割に係るすべてのインデックス値の最大のものである（７０６）。この結果として得られるドミナントＤＣは、以前の処理における分割に対して考えられるＤＣの分割の直接的な結果となるかもしれない（７０４）。処理７０４のインデックス値Ａ１と処理７０６の加重係数Ａ２などの２つの値が、その後、「加重インデックス値」と呼ばれる合成値Ａを生成するため加算される（７０８）。
【００３７】
上述した分割プロセスは、すべての可能な分割の評価を要求するかもしれない。従って、本発明の実施例によると、評価される必要がある可能な分割が他に存在する限り（７１０）、本方法は、可能性のあるすべての分割シナリオに対して、合成値Ａが評価されるまで処理７０４、７０６及び７０８を繰り返す。
【００３８】
本方法は、例えば、可能性のある分割の少なくとも一部の評価が完了すると、最大荷重インデックス値Ａに関する分割シナリオを特定する（７１２）。さらに、本方法は、加重インデックス値Ａがゼロなどの所定の値より大きいかチェックすることを含む（１７４）。ブロック７１６に示されるように、本方法は、加重インデックス値が所定の値より大きいと判断される場合など、特定された分割シナリオに従ってＤＣを分割する。本方法はまた、中間的な分割から生じた最大命令発行幅を有する新たなドミナントＤＣを特定することを含むかもしれない（７１８）。本方法はまた、分割アルゴリズムを繰り返すことを含む（７０４）。
【００３９】
加重インデックス値Ａは、例えば、１以上の繰り返しの後、ゼロなどの所定の値とより小さくなるかもしれない（７１４）。このことは、分割によりＤＣにおける可能な命令の減少よりも多くの命令が重複する必要があることを示すかもしれない。これにより、分割プロセスは終了される。
【００４０】
図８は、本発明の実施例によるＤＣをクラスタにマッピングする方法の概略的なフローチャートである。ＤＣは、最も優先度の高いＤＣから開始されるなどその優先度に従ってソートされ、クラスタは、最も大きな幅のクラスタから開始するなど、それの命令発行幅によりソートされる（８１０）。その後、ＤＣは１つずつなど、対応する順位のクラスタにマッピングされる（８１２）。すなわち、最も優先度の高いＤＣが最も幅の大きなクラスタにマッピングされ、第２の優先度のＤＣが２番目に幅の大きなクラスタにマッピングされ、すべてのＤＣが各クラスタにマッピングされるか、又はすべてのクラスタがマッピングプロセスにおいて終了されるまで続けられる。１以上のマッピングされたＤＣは、当該ＤＣがマッピングされたクラスタを特定する識別子（ＩＤ）に割り当てられる。
【００４１】
その後、マッピングプロセスは、マッピングされるべきＤＣが残っているかチェックする（８１４）。マッピングプロセスは、例えば、すべてのＤＣがマッピングされた場合など、終了するかもしれない。クラスタの少なくとも一部は、複数のＤＣにマッピングされ、マッピングプロセスは、マッピングされるべきＤＣがさらに存在する場合など、以下のように進行する。
【００４２】
本発明の実施例によると、残りのＤＣをマッピングするため、クラスタロード値が利用されるかもしれない。クラスタのクラスタロード値は、当該クラスタの命令発行幅により分割されるクラスタにすでにマッピングされた命令の合計数として規定されるかもしれない。１以上のクラスタに対するクラスタロード値が計算されるかもしれない（８１６）。その後、クラスタは、所定の基準に基づき選択される。例えば、最小のクラスタロード値を有するクラスタが選択されるかもしれない（８１８）。いくつかのケースでは、同一のクラスタロード値を有する２以上のクラスタが存在するかもしれない（８２０）。このようなケースでは、同一のクラスタロード値を有するクラスタの最大となる命令発行幅（８２２）のクラスタが選択されるかもしれない。その後、マッピングプロセスは、次のドミナントＤＣを選択されたクラスタにマッピングする（８２４）。
【００４３】
ＤＣをクラスタにマッピングした後、マッピングされたＤＣには、当該ＤＣがマッピングされるクラスタを一意的に特定する識別子（ＩＤ）が割り当てられる（８２６）。上述したように、ＤＣＰ１２（図１）などのＤＣＰにおけるＤＣトレースの実行中、トレース内のＤＣが予め割り当てられたクラスタＩＤなどの所定のスキームなどに基づき、実行のためクラスタに割り当てられる。
【００４４】
ＤＣをクラスタにマッピングし、クラスタＩＤをＤＣに割り当てた後（８２６）、マッピングプロセスはさらに、すべてのＤＣがクラスタにマッピングされたか判断する（８２８）。まだマッピングされていないＤＣが存在する場合、当該プロセスは、新たに更新されたクラスタのクラスタロード値を計算するステップに戻る（８１６）。その後、次のドミナントＤＣが。上述した処理などに従って選択されたクラスタにマッピングされる。当該プロセスは、例えば、すべてのＤＣがクラスタにマッピングされるまで継続される。
【００４５】
本出願において開示されるような本発明の各種実施例に関して、各種ベンチマーク分析が、数量的なサポートとなる根拠を本発明の各実施例に提供するよう実行された。これらの分析の一例となる結果が、以下のセクションにおいて概略される。使用されたベンチマークは、以下のグラフに示されるように、「ｂｚｉｐ２」、「ｃｒａｆｔｙ」、「ｇａｐ」、「ｇｃｃ」、「ｇｚｉｐ」、「ｍｃｆ」、「ｔｗｏｌｆ」、「ｖｐｒ」など、ＣＩＮＴ２０００一式から選択された８つの整数ベンチマークを含む。この作業に使用されたバイナリコードは、本発明の実施例によるＩｔａｎｉｕｍアーキテクチャのためのＩｎｔｅｌ（登録商標）Ｅｌｅｃｔｒｏｎコンパイラによりコンパイルされた。この先進的なコンパイラは、コンパイラの分野において知られる最新の最適化技術と共に、Ｉｎｔｅｌ（登録商標）Ｉｔａｎｉｕｍ  Ｐｒｏｃｅｓｓｏｒ  Ｆａｍｉｌｙ（ＩＰＦ）アーキテクチャの各機能について具体的に設計された技術と含む。すべてのベンチマークは、可能とされる最大コンパイラ最適化によりコンパイルされた。この最適化は、当該分野において知られるようなアグレッシブソフトウェアプリフェッチ処理、ソフトウェアパイプライン処理、コントロールスペキュレーション及びデータスペキュレーションなどのプロフィットドリブンなフィードバックガイドに基づくものを含む。
【００４６】
図９は、エンハンストＷＰＰ（Ｗｈｏｌｅ  Ｐｒｏｇｒａｍ  Ｐａｔｈ）アプローチを利用することによって取得されるトレースにより実行される命令の累積パーセントを示す概略図である。それは、上記列挙した８つのベンチマークプログラムによる１００個の最も頻繁に実行されたトレースを示す。ｘ軸はトレース数を示し、ｙ軸は当該トレースの累積プログラムカバー率を示す。より大きなプログラムの軌跡を有するものを除いて、１００以下のトレースがすべてのプログラムに対して動的に実行される命令の８０％までをカバーすることが必要であることが明らかである。
【００４７】
図１０は、ｘ軸に示される各ベンチマークについて構成されたトレースに対して、各バーの上部の垂直線により示される最大及び最小トレース長と共に、構成されたトレースにおける平均命令数を示す概略図である。ｙ軸は対数スケールとなっていることに留意されたい。ＷＰＰアルゴリズムに基づく本発明の実施例によるオフラインコンパイル処理は、とエースベースプロセッサに対する他のアプローチに組み込まれたものよりかなり長いトレースを構成することが可能であるかもしれない。例えば、ＤＣＰ１２（図１）に使用されるようなこれら長いトレースは、イン・オーダクラスタに対するより良好な命令スケジューリングの実行を可能にする。
【００４８】
図１１は、調査されたベンチマークの７つの最も高い優先度のＤＣに分散されるプログラム命令の平均パーセンテージを示す概略図である。それは、何れかのトレースの第１優先ＤＣが、他のＤＣと対比したとき、多数の命令を有していることを証明している。第１優先ＤＣは、トレースのすべての命令の約５０〜６０％を説明し、第２優先ＤＣは、トレースの命令の約２０％しか説明せず、残りのＤＣは１０％以下しか説明しない。
【００４９】
図１２は、上述したすべてのベンチマークからトレース上で平均化された７つの最優先ＤＣのＤＣ幅に分散されたトレースのパーセンテージを示す概略図である。いくつかのトレースについては、第２優先ＤＣから上には、ＤＣが全く存在しないかもしれないため、これらのＤＣのバーは１００％までは加算されない。実行されたトレースの５５％の近傍では、第１優先ＤＣは２より大きなＤＣ幅を有する。すなわち、実行されるトレースの４５％の近傍では、ＤＣ幅は２より小さい。また、ＤＣ幅は、第１優先ＤＣについてのみ３より大きくなる傾向があるが、他のＤＣについては、２より大きくなることはまれである。このことは、クラスタリングされたマイクロアーキテクチャを設計する際、クラスタの命令発行幅が一様である必要がないことを意味する。例えば、図５を参照して上述されたように、おそらく１ワイドであるいくつかのより狭いクラスタと第１優先ＤＣの要求を満たす１つのみのワイドクラスタによって、異質なクラスタマイクロアーキテクチャを設計することによって、利用可能なＩＬＰを最大化することが可能である。
【００５０】
図１３は、すべてのベンチマークからトレース上で平均化された７つの最優先ＤＣのクリティカルパス長に分散するトレースのパーセンテージを示す概略図である。予想されるように、第１優先ＤＣのクリティカルパスは、その他のものより長い。従って、最優先ＤＣがワイドクラスタにおいて実行されている間、合成されたパス長は通常はドミナントＤＣのパス長を超えないため、他のすべてのものは１以上の狭いクラスタ上で逐次的にスケジューリングされる。第１優先ＤＣのクリティカルパス長は、構成されるトレースの長さの平方根としてほぼスケーリングされる。
【００５１】
図１４は、上述した８つのベンチマークに対するＤＣ幅に従ってソートされた２０個の最も頻繁に実行されるトレースの第１優先ＤＣのＤＣ幅分布を示す概略図である。それは、いくつかのケースでは、ドミナントＤＣのＤＣ幅が１２の最大値まで進捗することを示す。
【００５２】
図１５は、本発明の実施例による図１４に示されるＤＣ幅分布と比較して、命令重複アルゴリズムに基づきＤＣ最適化処理を適用した後、２０個の頻繁に実行されるトレースの第１優先ＤＣのＤＣ幅分布を示す概略図である。ＤＣ幅は大きく低下し、ほとんどのケースにおいて、ＤＣ幅は２以下となる。
【００５３】
図１６は、ベンチマークのすべてのトレース上で平均化される第１優先ＤＣの命令数を減少させることに関する本出願に開示されるような命令重複アルゴリズムの効果を示す概略図である。第１のバーはトレースにおける合計命令数の平均である。第２バーは、重複した追加的な命令の結果としての当該平均数の増大を示す。しかしながら、この重複による命令数の増加は、トレースの命令の合計の１０％未満である。次の２つのバーはそれぞれ、ドミナントＤＣの最適化前後のドミナントＤＣの命令数を示す。平均すると、ドミナントＤＣのサイズの約２０％が低減された。最後の２つのバーは、最適化アルゴリズムの適用前後の第２ドミナントＤＣにおける命令数を示す。もとの第１優先ＤＣの分割から生ずるＤＣは、新たな第２優先ＤＣとなるため、第２優先ＤＣの命令数は増大する。
【００５４】
本出願に開示されるように、ＤＣＰマイクロアーキテクチャの複雑さの有効性が、ＩＬＤＰ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｌｅｖｅｌ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｒｏｃｅｓｓｉｎｇ）マイクロアーキテクチャ並びに他のクラスタアウト・オブ・オーダ（ＯＯＯ）及びイン・オーダマイクロアーキテクチャと比較される。これらの結果は、以下のテーブル２に要約される。
【００５５】
【表２】
2008515051.tif 000004
上記テーブルから明らかなように、本出願に開示されるＤＣＰマイクロアーキテクチャは、リネーミング及びステアリングロジックの複雑さを有しないが、トレース構成中に、命令が予めスケジューリング及びリネームされているとき、アウト・オブ・オーダ実行の効果の一部を依然として取得することが可能である。また、図２を参照して上述されるように、トレースの命令の再実行が必要となる状況において使用するため、レジスタ値をセーブするのに使用されるリオーダバッファ（ＲＯＢ）は、例えば、ＩＬＤＰやアウト・オブ・オーダプロセッサと比較して不要となるかもしれない。６ワイドイン・オーダクラスタのベースライン設計と比較して、ＤＣＰは、それが高々３ワイドクラスタを使用するとき、複雑さの低いバイパスロジックを有する。他の研究は、バイパスロジックの複雑さは、命令発行幅の増加に関して２次的に増大することを示していた。また、ＤＣＰに使用されるグローバルレジスタファイルは、トラフィックの大部分がローカルレジスタファイルを介し処理されるとき、グローバルレジスタファイルに対して２つのリードポートと２つのライトポートしか必要としない。これは、１サイクルで６命令を発行するのに従来のイン・オーダモノリシック設計において必要な１２個のリードポートと６個のライトポートと比較すると、複雑さが大きく低減している。このような複雑さの効果的な構成は、高い周波数の実現を可能にするかもしれない。
【００５６】
図１７は、「（３，３）ＤＣＰ」と記される２つの３ワイドイン・オーダパイプラインクラスタと、「Ｔｒａｃｅ  Ｓｃｈ」と記される最適化されたトレースを実行するためのサポートを有する６ワイドイン・オーダプロセッサと、「ｉｏ」と記されたイン・オーダプロセッサと、「ｏｏｏ」と記されたアウト・オブ・オーダプロセッサとによるＤＣＰマイクロアーキテクチャのサイクル毎の命令のパフォーマンスを比較する概略図である。図１７から、「Ｔｒａｃｅ  Ｓｃｈ」のベースライン６ワイドイン・オーダプロセッサは、「ｉｏ」のイン・オーダプロセッサによって実現されるＩＰＣと比較してより高いＩＰＣを実現することに留意されたい。パフォーマンスの向上は、「ｇａｐ」のベンチマークについて１５％までとなるかもしれない。また、「（３，３）ＤＣＰ」などの２つの３ワイドイン・オーダクラスタによるＤＣＰマイクロアーキテクチャは、「Ｔｒａｃｅ  Ｓｃｈ」のＩＰＣと実質的に等しいＩＰＣを実現するかもしれないということに留意されたい。このパフォーマンスの効果は、長いトレースに対するスケジューリングと、最適化ＤＣ構成アルゴリズムを介し実現されるクラスタ間の一様な命令分散の結果であるかもしれない。
【００５７】
１つのトレースの実行が次のトレースのクラスタへの発行前に完了される逐次化されたトレースの実行と対比して、制御されたスペキュレーションアプローチに基づき、隣接するトレースの重複実行において、約１０〜１５％のパフォーマンスの向上が実現された。この結果は、図１７において「（３，３）ＤＣＰ  ｗ／ｏｖｅｒｌａｐ」として示されている。現在のトレースからのＤＣの実行が行われている間に、トレース予測装置が実行すべき次のトレースを選択しているように、制御されたスペキュレーションアプローチがＤＣの実行を管理する。選択されたトレースにおけるＤＣは、それらが現在実行されているＤＣとのデータ依存性を有しないと仮定されているため、すでに利用可能なクラスタリソースにおいて実行されるかもしれない。
【００５８】
ＩＰＣにより測定されるパフォーマンスの比較は、異質ＤＣＰマイクロアーキテクチャと同質ＤＣＰマイクロアーキテクチャとの間でも実行された。図１８は、同一の合計命令発行幅を有する（３，３）、（３，２，１）及び（２，２，２）として記される３つの異なるクラスタ構成間の結果を示す概略図である。（３，３）の構成は、２つの３ワイドクラスタを有し、（３，２，１）の構成は、３ワイド、２ワイド及び１ワイドのサイズの３つのクラスタを有し、（２，２，２）の構成は、３つの２ワイドクラスタを有している。
【００５９】
（３，２，１）クラスタ構成によるＤＣＰマイクロアーキテクチャは、（３，３）構成とほとんど同じパフォーマンスを有していた。これは、ＤＣの特徴付けに整合する。大きなＤＣ幅を有するドミナントＤＣは１つしか存在しないため、このドミナントＤＣを実行する１ワイドクラスタのみが、利用可能なＩＬＰを最大化するため要求される。
【００６０】
異質なクラスタ構成によるＤＣＰマイクロアーキテクチャは、同質なクラスタ構成に対してある長所を有する。（３，２，１）構成は、より小さなバイパスネットワークロジックしか使用しないため、（３，３）構成より小さなエリアしか必要としない。この結果、制限されたＩＬＰが利用可能であるとき、（３，２，１）構成はクラスタをオフにすることによってより少ないエネルギーしか消費しない。より狭いパイプラインが深さについてより小さく、より速くクロック動作するため、可変長のパイプラインを構成することによって、パフォーマンスがまた向上するかもしれない。
【００６１】
他方、（３，３）構成は、既存の３ワイドクラスタを複製することを通じて、３つの異なる幅を有する実質的に３つのパイプラインの設計を必要とする（３，２，１）構成より設計が容易であるかもしれない。
【００６２】
図１８はまた、（２，２，２）構成と（３，３）構成とを比較する。非ＤＣモードでは、すべての命令は利用可能な最も幅の大きなクラスタにおいて実行された。このため、非ＤＣモードの（２，２，２）構成では、命令はパフォーマンスの低下をもたらした２ワイドパイプラインにおいて実行された。図１８はまた、命令重複アルゴリズムを利用することから生じるパフォーマンスの効果を示す。図１８の最初のバーは、命令重複アルゴリズムを適用することなくシミュレートされた（２，２，２）構成に対応する。ベンチマーク「ｇａｐ」について、１３％までのＩＰＣの向上が実現された。平均的には、約５％の向上があった。
【００６３】
図１９は、ＤＣモードで実行された動的命令のパーセンテージを示す概略図である。ＤＣモードは、図１８と同様に、３つすべての構成、すなわち、構成（３，３）、構成（３，２，１）及び構成（２，２，２）に対して同一であった。それはまた、平均して約４％であった重複命令の動的な個数のパーセンテージを示し、重複した命令により生じるオーバヘッドが極めて小さかったことを意味する。
【００６４】
本発明の特徴が図示及び説明されたが、多数の改良、置換、変更及び均等が当業者に想起されるであろう。従って、添付した請求項は、そのような改良及び変更のすべてを本発明の趣旨の範囲内としてカバーするようイトされることが理解されるべきである。
【図面の簡単な説明】
【００６５】
【図１】図１は、本発明の実施例によるソース命令をターゲット命令にコンパイルし、クラスタリングされた依存性チェーンプロセッサ（ＤＣＰ）を利用してターゲット命令を実行することが可能な装置のブロック図である。
【図２】図２は、本発明の実施例による３ワイド、２ワイド及び１ワイドのサイズを３つのパイプラインクラスタを有するよう構成されるクラスタＤＣＰのブロック図である。
【図３】図３は、本発明の実施例によるクラスタＤＣＰと共に使用する依存性チェーン（ＤＣ）トレースを構成する方法のフローチャートである。
【図４】図４は、本発明の実施例によるＤＣトレースにおける３つの依存性チェーンの概念図である。
【図５】図５は、本発明の実施例による依存性チェーンを分析し、クラスタ命令発行幅を構成する方法のフローチャートである。
【図６】図６は、本発明の実施例による低減された幅の依存性チェーンのセットに依存性チェーンを分割する概念図である。
【図７】図７は、本発明の実施例による依存性チェーン最適化を実行する方法のフローチャートである。
【図８】図８は、本発明の実施例による依存性チェーンをクラスタにマッピングする方法のフローチャートである。
【図９】図９は、エンハンストＷＰＰ（Ｗｈｏｌｅ  Ｐｒｏｇｒａｍ  Ｐａｔｈ）アプローチを利用してキャプチャされたトレースによって実行されるプログラム命令の累積パーセンテージを示すグラフの概略図である。
【図１０】図１０は、エンハンストＷＰＰアプローチを利用することにより構成される１つのトレース内の平均命令数を示すグラフの概略図である。
【図１１】図１１は、トレース内の７つの最優先ＤＣ間に分散されるプログラム命令の平均パーセンテージを示すグラフの概略図である。
【図１２】図１２は、７つの最優先ＤＣのＤＣ幅間に分散されるトレースのパーセンテージを示すグラフの概略図である。
【図１３】図１３は、７つの最優先ＤＣのクリティカルパス長の間に分散されるトレースのパーセンテージを示すグラフの概略図である。
【図１４】図１４は、本発明の実施例によるＤＣ最適アルゴリズムを適用する前の２０個の最も頻繁に実行されたトレースの第１優先ＤＣのＤＣ幅分布を示すグラフの概略図である。
【図１５】図１５は、本発明の実施例によるＤＣ最適化アルゴリズムを適用した後の図１４の２０個の頻繁に実行されるトレースの第１優先ＤＣのＤＣ幅分布を示すグラフの概略図である。
【図１６】図１６は、本発明の実施例によるＤＣ最適化アルゴリズムを適用した後のドミナントＤＣにおける命令数のサイズ減少を示すグラフの概略図である。
【図１７】図１７は、従来のイン・オーダ及びアウト・オブ・オーダプロセッサのＩＰＣと比較した本発明の実施例によるＤＣＰマイクロアーキテクチャのＩＰＣ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｐｅｒ  Ｃｙｃｌｅ）を示すグラフの概略図である。
【図１８】図１８は、本発明の実施例による異質なＤＣＰマイクロアーキテクチャと同質なＤＣＰマイクロアーキテクチャとの間のＩＰＣにより測定されるパフォーマンス比較を示すグラフの概略図である。
【図１９】図１９は、ＤＣモードにより実行されるプログラム命令全体の動的命令数のパーセンテージと、重複した動的命令数のパーセンテージとを示すグラフの概略図である。
【図１】
2008515051.tif 000005
【図２】
2008515051.tif 000006
【図３】
2008515051.tif 000007
【図４】
2008515051.tif 000008
【図５】
2008515051.tif 000009
【図６】
2008515051.tif 000010
【図７】
2008515051.tif 000011
【図８】
2008515051.tif 000012
【図９】
2008515051.tif 000013
【図１０】
2008515051.tif 000014
【図１１】
2008515051.tif 000015
【図１２】
2008515051.tif 000016
【図１３】
2008515051.tif 000017
【図１４】
2008515051.tif 000018
【図１５】
2008515051.tif 000019
【図１６】
2008515051.tif 000020
【図１７】
2008515051.tif 000021
【図１８】
2008515051.tif 000022
【図１９】
2008515051.tif 000023
【国際調査報告】
2008515051.tif 000024
2008515051.tif 000025
2008515051.tif 000026
2008515051.tif 000027
2008515051.tif 000028
2008515051.tif 000029