(57)【特許請求の範囲】
【請求項１】
一次プロセッサの前に、補助プロセッサを用いてプリフェッチ動作を行うことによって命令をプリフェッチする方法であって、
該一次プロセッサ上で実行可能コードを実行する工程と、
該補助プロセッサ上で該実行可能コードの縮小バージョンを同時に実行する工程であって、該実行可能コードの該縮小バージョンが、該実行可能コードよりも速く行われ、該一次プロセッサが命令を必要とするときより前に該一次プロセッサ用のプリフェッチ動作を行う、工程と、
該プリフェッチされた命令をメインメモリから取り出す必要なしに、該一次プロセッサが、該プリフェッチされた命令にアクセスできるように、該プリフェッチされた命令を該一次プロセッサによってアクセス可能であるキャッシュに格納する工程と
を包含し、
前記実行可能コードの縮小バージョンの生成は、
前記実行可能コードについて、制御フローグラフを構成する工程と、
該制御フローグラフからループを取り除く工程と、
該制御フローグラフと関係がない実行可能コード命令を取り除く工程と、
前記プリフェッチ命令を、該実行可能コードの縮小バージョンに挿入して、前記一次プロセッサ用の該実行可能コードから命令をプリフェッチする工程と
を含む、方法。
【請求項２】
前記実行可能コードを実行する前に、
前記一次プロセッサについて、ソースコードを実行可能コードにコンパイルする工程と、
該実行可能コードをプロファイルして、該実行可能コードの頻繁に参照される部分について命令のトレースを作成する工程と、
前記一次プロセッサによってアクセス可能であるキャッシュに命令トレースの一部分をプリフェッチするようにプリフェッチ命令を生成することによって、前記補助プロセッサについて、該実行可能コードの縮小バージョンを生成する工程と、
通信命令を、前記一次プロセッサについて、前記実行可能コードに挿入し、該補助プロセッサについて、前記実行可能コードの縮小バージョンに挿入して、該一次プロセッサから該補助プロセッサに進行情報を転送する工程と
をさらに含み、該進行情報は、該補助プロセッサが前記プリフェッチ動作を行うようにトリガする、請求項１に記載の方法。
【請求項３】
前記ソースコードをコンパイルするプロセス、および前記実行可能コードの縮小バージョンを生成するプロセスは、コンパイラによって行われる、請求項２に記載の方法。
【請求項４】
前記補助プロセッサが誤った経路に沿って命令をプリフェッチしたことを前記進行情報が該補助プロセッサに示す場合に、前記実行可能コードの縮小バージョンは、該補助プロセッサがプリフェッチを中断するようにさせる、請求項２に記載の方法。
【請求項５】
前記実行可能コードの縮小バージョンが、
制御フロー履歴情報を、分岐履歴情報および呼び出し履歴情報を記録する専用ハードウェアから読み出し、
該制御フロー履歴情報に基づいて、該実行可能コードを通じて予測された経路を構成し、
前記一次プロセッサ用の命令をプリフェッチするために、予測された経路に沿ってプリフェッチ動作を行うように設定されている、請求項１に記載の方法。
【請求項６】
前記プリフェッチ動作を行う工程が、前記一次プロセッサ用の複数の命令を含むキャッシュブロックをプリフェッチする工程を含む、請求項１に記載の方法。
【請求項７】
前記進行情報を、一方向通信チャネルを介して、前記一次プロセッサから前記補助プロセッサに周期的に送る工程をさらに含む、請求項１に記載の方法。
【請求項８】
コンピュータによって実行されるときに、該コンピュータが一次プロセッサの前に、補助プロセッサを用いてプリフェッチ動作を行うことによって命令をプリフェッチする方法を行うようにさせる命令を格納するコンピュータ読み出し可能格納媒体であって、該方法は、
該一次プロセッサ上で実行可能コードを実行する工程と、
該補助プロセッサ上で該実行可能コードの縮小バージョンを同時に実行する工程であって、該実行可能コードの該縮小バージョンが、該実行可能コードよりも速く行われ、該一次プロセッサが命令を必要とするときより前に該一次プロセッサ用のプリフェッチ動作を行う、工程と、
該プリフェッチされた命令をメインメモリから取り出す必要なしに、該一次プロセッサが該プリフェッチされた命令にアクセスできるように、該プリフェッチされた命令を該一次プロセッサによってアクセス可能であるキャッシュに格納する工程と
を包含し、
前記実行可能コードの縮小バージョンの生成は、
前記実行可能コードについて、制御フローグラフを構成する工程と、
該制御フローグラフからループを取り除く工程と、
該制御フローグラフと関係がない実行可能コード命令を取り除く工程と、
前記プリフェッチ命令を、該実行可能コードの縮小バージョンに挿入して、前記一次プロセッサ用の該実行可能コードから命令をプリフェッチする工程と
を含む、コンピュータ読み出し可能格納媒体。
【請求項９】
前記方法は、前記実行可能コードを実行する工程の前に、
前記一次プロセッサについて、ソースコードを実行可能コードにコンパイルする工程と、
該実行可能コードをプロファイルして、該実行可能コードの頻繁に参照される部分について命令のトレースを作成する工程と、
前記一次プロセッサによってアクセス可能であるキャッシュに命令トレースの一部分をプリフェッチするようにプリフェッチ命令を生成することによって、前記補助プロセッサについて、該実行可能コードの縮小バージョンを生成する工程と、
通信命令を、前記一次プロセッサについて、前記実行可能コードに挿入し、該補助プロセッサについて、前記実行可能コードの縮小バージョンに挿入して、該一次プロセッサから該補助プロセッサに進行情報を転送する工程と
をさらに含み、該進行情報は、該補助プロセッサが前記プリフェッチ動作を行うようにトリガする、請求項８に記載のコンピュータ読み出し可能格納媒体。
【請求項１０】
前記ソースコードをコンパイルするプロセス、および前記実行可能コードの縮小バージョンを生成するプロセスは、コンパイラによって行われる、請求項９に記載のコンピュータ読み出し可能格納媒体。
【請求項１１】
前記補助プロセッサが誤った経路に沿って命令をプリフェッチしたことを前記進行情報が該補助プロセッサに示す場合、前記実行可能コードの縮小バージョンは、該補助プロセッサがプリフェッチを中断するようにさせる、請求項９に記載のコンピュータ読み出し可能格納媒体。
【請求項１２】
前記実行可能コードの縮小バージョンが、
制御フロー履歴情報を、分岐履歴情報および呼び出し履歴情報を記録する専用ハードウェアから読み出し、
該制御フロー履歴情報に基づいて、該実行可能コードを通じて予測された経路を構成し、
前記一次プロセッサ用の命令をプリフェッチするために、予測された経路に沿ってプリフェッチ動作を行うように設定されている、請求項８に記載のコンピュータ読み出し可能格納媒体。
【請求項１３】
前記プリフェッチ動作を行う工程が、前記一次プロセッサ用の複数の命令を含むキャッシュブロックをプリフェッチする工程を含む、請求項８に記載のコンピュータ読み出し可能格納媒体。
【請求項１４】
前記進行情報を、一方向通信チャネルを介して、前記一次プロセッサから前記補助プロセッサに周期的に送る工程をさらに含む、請求項８に記載のコンピュータ読み出し可能格納媒体。
【請求項１５】
メモリからのプリフェッチを容易にする装置であって、
実行可能コードを実行するように設定された一次プロセッサと、
該実行可能コードの縮小バージョンを同時に実行するように設定された補助プロセッサであって、該実行可能コードの該縮小バージョンが、該実行可能コードよりも速く行われ、該一次プロセッサが命令を必要とするときより前に該一次プロセッサ用のプリフェッチ動作を行う、補助プロセッサと、
該一次プロセッサによってアクセス可能であり、該プリフェッチされた命令をメインメモリから取り出す必要なしに、該一次プロセッサが該プリフェッチされた命令にアクセスできるように、該プリフェッチされた命令を格納するように設定されている、キャッシュと
を含み、
前記実行可能コードの縮小バージョンは、
前記実行可能コードについて、制御フローグラフを構成し、
該制御フローグラフからループを取り除き、
該制御フローグラフと関係がない実行可能コード命令を取り除き、
前記プリフェッチ命令を、該実行可能コードの縮小バージョンに挿入して、前記一次プロセッサ用の該実行可能コードから命令をプリフェッチする、
ことによって生成される、装置。
【請求項１６】
前記一次プロセッサについて、ソースコードを実行可能コードにコンパイルし、
該実行可能コードをプロファイルして、該実行可能コードの頻繁に参照される部分について命令のトレースを作成し、
前記一次プロセッサによってアクセス可能であるキャッシュに命令トレースの一部分をプリフェッチするようにプリフェッチ命令を生成することによって、前記補助プロセッサについて、該実行可能コードの縮小バージョンを生成し、
通信命令を、前記一次プロセッサについて、前記実行可能コードに挿入し、該補助プロセッサについて、前記実行可能コードの縮小バージョンに挿入して、該一次プロセッサから該補助プロセッサに進行情報を転送するように設定されたコンパイルメカニズムをさらに含み、
該進行情報は、該補助プロセッサが前記プリフェッチ動作を行うようにトリガする、請求項１５に記載の装置。
【請求項１７】
前記補助プロセッサが誤った経路に沿って命令をプリフェッチしたことを前記進行情報が該補助プロセッサに示す場合に、前記実行可能コードの縮小バージョンは、該補助プロセッサがプリフェッチを中断するようにさせる、請求項１６に記載の装置。
【請求項１８】
前記実行可能コードについて、分岐履歴情報および呼び出し履歴情報を記録する専用ハードウェアをさらに含む装置であって、前記実行能コードの縮小バージョンが、
制御フロー履歴情報を、分岐履歴情報および呼び出し履歴情報を記録する専用ハードウェアから読み出し、
該制御フロー履歴情報に基づいて、該実行可能コードを通じて予測された経路を構成し、
前記一次プロセッサ用の命令をプリフェッチするために、予測された経路に沿ってプリフェッチ動作を行うように設定されている、請求項１５に記載の装置。
【請求項１９】
前記プリフェッチ動作が、前記一次プロセッサ用の複数の命令を含むキャッシュブロックをプリフェッチするように設定されている、請求項１５に記載の装置。
【請求項２０】
前記一次プロセッサおよび前記補助プロセッサが、同じ半導体チップ上にある、請求項１５に記載の装置。
【請求項２１】
前記一次プロセッサおよび前記補助プロセッサが、別の半導体チップ上にある、請求項１５に記載の装置。
【請求項２２】
前記補助プロセッサが、前記一次プロセッサの、メモリアクセス動作に関係ないハードウェアを有さない簡略的なバージョンである、請求項１５に記載の装置。
【発明の詳細な説明】
【０００１】
（背景）
（発明の分野）
本発明は、コンピュータシステム性能を向上させる技術に関する。より具体的には、本発明は、一次プロセッサの前に、補助プロセッサを用いて、プリフェッチ操作を行うことによって、命令をメモリからプリフェッチする方法および装置に関する。
【０００２】
（関連技術）
半導体集積密度が高められることによって、マイクロプロセッサチップにより多くのトランジスタを集積することが可能になり、コンピュータ設計者は、コンピュータシステム性能を高めるために、これらのトランジスタを用いる異なる方法を研究している。この目的を達成するため、コンピュータ設計者は、複数の中央処理装置（ＣＰＵ）を単一の半導体チップに組み込み始めている。これによって、同時に実行され得る別々の部分に平行化（分割）することができる、計算タスクの性能利得を得ることができる。
【０００３】
不運なことに、平行化からの性能利得は、コードの固有シリアル部分を含む多くの用途において限定され得る。このコードの固有シリアル部分においては、メモリ待ち時間の問題によって、性能はさらに限定される。
【０００４】
メモリ待ち時間の問題は、プロセッサのクロックスピードが急激な速度で増大し続けるにつれて、段々ひどくなっている。今日のプロセッサクロックスピードにおいて、メインメモリからキャッシュラインを引き込むために、２００プロセッサクロックサイクルまでかかることもあり得る。
【０００５】
コンピュータ設計者は、現在では、複数の技術を用いて、メモリ待ち時間を低減している。（１）不適切の実行は、ロードをスケジューリングし、格納して、可能な限りメモリ待ち時間を隠すように用いられ得る。不運なことに、故障実行は、典型的には、メモリ待ち時間の数クロックサイクルを隠すことに限定される。（２）非故障ロード命令は、アドレスが有効でない場合に故障を引き起こすことなく、データ値を推論的にロードするように用いられ得る。（３）ステアリングロード命令は、Ｌ１キャッシュが用いられていないデータ値で汚染されないように、データ値を、Ｌ１キャッシュではなく、Ｌ２キャッシュに推論的にロードするように用いられ得る。不運なことに、非故障ロードおよびステアリングロードの使用は、不必要なロードにつながり得る。これは、命令キャッシュスペースを無駄にし、レジスタを拘束する。（４）何人かの研究者は、ハードウェアプリフェッチエンジンを用いることを調査したが、これらのハードウェアプリフェッチエンジンは、典型的には、不規則なメモリアクセスパターンには、有効でない。
【０００６】
メモリ待ち時間の遅延は、命令フェッチ動作中の問題ともなり得る。命令キャッシュのミスは、データキャッシュミスと同じ程度に、遅延を引き起こし得ることに留意されたい。また、今日のプログラム言語で書かれたプログラムコードに通常点在している多くの分岐および関数呼び出しのせいで、どの命令が次に実行される可能性が高いか予測することが非常に困難であることにも留意されたい。
【０００７】
命令フェッチ動作中のメモリ待ち時間を低減する方法および装置が必要とされている。
【０００８】
（要旨）
本発明の一実施形態は、一次プロセッサより前に、補助プロセッサを用いて命令をプリフェッチしてプリフェッチ動作を行うシステムを提供する。このシステムは、該一次プロセッサ上で実行可能コードを実行し、該補助プロセッサ上で該実行可能コードの縮小バージョンを同時に実行することによって動作する。該実行可能コードの該縮小バージョンが、該実行可能コードよりも速く行われ、該一次プロセッサセッサが命令を必要とするときより前に該一次プロセッサ用のプリフェッチ動作を行う。また、このシステムは、該プリフェッチされた命令をメインメモリから取り出す必要なしに、該一次プロセッサが、該プリフェッチされた命令にアクセスできるように、該プリフェッチされた命令を該一次プロセッサによってアクセス可能であるキャッシュに格納する。
【０００９】
本発明の一実施形態において、システムは、実行可能コードを実行する前に、前記一次プロセッサについて、ソースコードを実行可能コードにコンパイルする。次に、このシステムは、該実行可能コードをプロファイルして、該実行可能コードの頻繁に参照される部分について命令のトレースを作成する。その後、このシステムは、前記一次プロセッサによってアクセス可能であるキャッシュに命令トレースの一部分をプリフェッチするようにプリフェッチ命令を生成することによって、前記補助プロセッサについて、該実行可能コードの縮小バージョンを生成する。また、システムは、通信命令を、前記一次プロセッサについて、前記実行可能コードに挿入し、該補助プロセッサについて、前記実行可能コードの縮小バージョンに挿入して、該一次プロセッサから該補助プロセッサに進行情報を転送する。この進行情報は、該補助プロセッサが前記プリフェッチ動作を行うようにトリガする。
【００１０】
本発明の一実施形態において、前記ソースコードをコンパイルするプロセス、および前記実行可能コードの縮小バージョンを生成するプロセスは、コンパイラによって行われる。
【００１１】
本発明の一実施形態において、前記補助プロセッサが誤った経路に沿って命令をプリフェッチしたことを前記進行情報が該補助プロセッサに示す場合に、前記実行可能コードの縮小バージョンは、該補助プロセッサがプリフェッチを中断するようにさせる。
【００１２】
本発明の一実施形態において、前記実行可能コードの縮小バージョンが、制御フロー履歴情報を、分岐履歴情報および呼び出し履歴情報を記録する専用ハードウェアから読み出すように設定されている。次に、実行可能コードの縮小バージョンが、該制御フロー履歴情報に基づいて、該実行可能コードを通じて予測された経路を構成し、前記一次プロセッサ用の命令をプリフェッチするために、予測された経路に沿ってプリフェッチ動作を行うように設定されている。
【００１３】
本発明の一実施形態において、前記実行可能コードの縮小バージョンを生成する工程が、前記実行可能コードについて、制御フローグラフを構成する工程を含む。これを行うことにおいて、このシステムは、該制御フローグラフからループを取り除き、該制御フローグラフと関係がない実行可能コード命令を取り除く。また、このシステムは、前記プリフェッチ命令を、該実行可能コードの縮小バージョンに挿入して、前記一次プロセッサ用の該実行可能コードから命令をプリフェッチする。
【００１４】
本発明の一実施形態において、前記プリフェッチ動作を行う工程が、前記一次プロセッサ用の複数の命令を含むキャッシュブロックをプリフェッチする工程を含む。
【００１５】
本発明の一実施形態において、このシステムは、前記進行情報を、一方向通信チャネルを介して、前記一次プロセッサから前記補助プロセッサに周期的に送る。
【００１６】
本発明の一実施形態において、前記一次プロセッサおよび前記補助プロセッサが、同じ半導体チップ上にある。
【００１７】
本発明の一実施形態において、前記一次プロセッサおよび前記補助プロセッサが、別の半導体チップ上にある。
【００１８】
本発明の一実施形態において、前記補助プロセッサが、前記一次プロセッサの簡略的なバージョンである。
【００１９】
（詳細な説明）
以下の説明は、当業者が本発明を作成し、用いることを可能にするように提示され、特定の適用例およびその要件のコンテキストにおいて提供される。当業者であれば、開示された実施形態に対する各種の改変例が容易に理解され、本明細書において定義された一般的な原理が、本発明の精神および範囲から逸脱することなく、他の実施形態および用途に適応され得る。従って、本発明は、説明する実施形態に限定されず、本明細書において開示された原理および特徴に一致する最も広い範囲に一致するべきである。
【００２０】
この詳細な説明において記載されるデータ構造およびコードは、典型的には、
コンピュータ読み出し可能格納媒体に格納される。コンピュータ読み出し可能格納媒体は、コンピュータシステムによって用いられるコードおよび／またはデータを格納し得る任意のデバイスまたは媒体であり得る。これには、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、およびＤＶＤ（デジタルビデオディスク）のような磁気または光格納デバイスが含まれる。
【００２１】
（コンピュータシステム）
図１は、本発明の実施形態による、コンピュータシステム１０１を示す図である。コンピュータシステム１０１は、一次プロセッサ１０２および補助プロセッサ１０４を含む。これらの構造体の全ては、シリコンダイ１００上にある（本発明の他の実施形態においては、これらの構造体は、複数のシリコンダイ」上にあってもよい）。
【００２２】
プロセッサ１０２および１０４は、プロセッサ１０２および１０４によって実行される命令をそれぞれ含む命令キャッシュ１１２および１２０を含む。
【００２３】
プロセッサ１０２および１０４は、さらに、ロードバッファ１１４および１２２を含み、それぞれ、データキャッシュ１０７および１０６との通信をバッファリングする格納バッファ１１６および１２４を含む。より具体的には、一次プロセッサ１０２は、データキャッシュ１０７から受け取ったロードをバッファリングするロードバッファ１１４と、データキャッシュ１０７への格納をバッファリングする格納バッファ１１６とを含む。同様に、補助プロセッサ１０４は、データキャッシュ１０６から受け取ったロードをバッファリングするロードバッファ１２２と、データキャッシュ１０６への格納をバッファリングする格納バッファ１２４とを含む。
【００２４】
プロセッサ１０２および１０４は、さらに、一次プロセッサ１０２と補助プロセッサ１０４との間の高速通信を容易にする一方向通信チャネル１２８〜１２９によって結合されている。一次プロセッサ１０２が補助プロセッサ１０４内のレジスタ１２６に書き込むことを、通信チャネル１２８が可能にしていることに留意されたい。同様に、補助プロセッサ１０４が一次プロセッサ１０２内のレジスタ１２７に書き込むことを、通信チャネル１２９が可能にしている。
【００２５】
共有メモリ通信メカニズムの使用とは異なり、レジスタ１２６（または１２７）への書き込みは、キャッシュミスまたはコヒーレンストラフィックを引き起こさない。さらに、一次プロセッサ１０２は、処理を継続するために、補助プロセッサ１０４が通信を受け取るまで待機する必要がない。対照的に、一次プロセッサ１０２がメモリを介して補助プロセッサ１０４と通信しようとする場合、システムは、通信するために、格納バッファ１１６がクリアされるまで待機する必要がある。
【００２６】
本発明の一実施形態において、データキャッシュ１０６および１０７は、３２バイトキャッシュラインを有する１６Ｋバイト４方向セット連想データキャッシュである。
【００２７】
データキャッシュ１０６、データキャッシュ１０７、命令キャッシュ１１２および命令キャッシュ１２０は、スイッチ１１０を介して、Ｌ２キャッシュ１１３に結合される。スイッチ１１０は、信号ラインを切り換える、任意のタイプの回路を含み得る。本発明のある実施形態において、スイッチ１１０は、クロスバースイッチである。
【００２８】
Ｌ２キャッシュは、一次プロセッサ１０２および補助プロセッサ１０４用の両方の命令およびデータを格納する、大きい統一型キャッシュである。Ｌ２キャッシュ１１３は、メモリコントローラ１１１に結合されている。メモリコントローラ１１１自体は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）１０８（チップの外側に位置する）に結合されている。
【００２９】
ＤＲＡＭ１０８は、一次プロセッサ１０２用の実行可能コード１３０を含む。システム動作中、実行可能コード１３０は、メモリコントローラ１１１、Ｌ２キャッシュ１１３およびスイッチ１１０を介して、一次プロセッサ１０２の命令キャッシュ１１２にロードされる。ＤＲＡＭ１０８は、また、補助プロセッサ１０４用の縮小された実行可能コード１３２を含む。縮小された実行可能コード１３２は、実行可能コード１３０と同じメモリ参照のパターンを生成する、実行可能コード１３０の縮小バージョンである。システム動作中、縮小された実行可能コード１３２は、メモリコントローラ１１１、Ｌ２キャッシュ１１３およびスイッチ１１０を介して、補助プロセッサ１０４の命令キャッシュ１２０にロードされる。ＤＲＡＭ１０８は、さらに、メモリコントローラ１１１、Ｌ２キャッシュ１１３およびスイッチ１１０を介して、データキャッシュ１０６〜１０７に移動し、データキャッシュ１０６〜１０７から移動するデータ１３４を含む。
【００３０】
本発明は、複数のプロセッサを含む任意のコンピュータシステムにおいて用いられ得、例示したコンピュータシステム構造に限定されないことに留意されたい。
【００３１】
また、本発明の一実施形態において、補助プロセッサ１０４は、命令が一次プロセッサ１０２によって用いられる前に、命令アクセスを作成するために用いられることに留意されたい。この実施形態において、補助プロセッサ１０４は、プログラムによって指定された計算の全てを実際に行う必要はなく、補助プロセッサ１０４は、プログラムの命令アクセスパターンを補助プロセッサ１０４が決定するために充分な計算を行う必要があるに過ぎない。従って、補助プロセッサ１０４は、命令アドレス計算を行うために必要とされない回路（例えば、デバイダ、およびマルチプレクサ回路）を省いた、一次プロセッサ１０２のより簡略なバージョンであり得る。
【００３２】
（コンパイルプロセス）
図２は、本発明の実施形態による、コンパイルプロセスを示す図である。コンパイルプロセスの間、ソースコード２０２は、コンパイラ２０４に供給され、一次プロセッサ１０２用の実行可能コード１３０を生成する。その後、実行可能コード１３０が、縮小モジュール２０８に供給され、補助プロセッサ１０４用の縮小された実行可能コード１３２を生成する。縮小モジュール２０８は、コンパイラ２０４の一部であってもよいし、あるいは、コンパイラ２０４とは別でもよい。
【００３３】
本発明の一実施形態において、コンパイルおよび縮小プロセスは、ランタイムの前に行われる。他の実施形態において、コンパイルおよび縮小プロセスは、ランタイム中、プログラムが実行されている間に行われる。
【００３４】
（縮小された実行可能コードの生成）
図３は、本発明の実施形態による、縮小モジュール２０８内の縮小された実行可能コード１３２のフローチャートである。システムは、実行可能コード１３０をプロファイル（実行可能コード１３０の実行をシミュレーション）し、メモリ待ち時間が遅延を引き起こしているホットスポットを確認する工程（工程３０２）から開始する。システムは、プロセスをプロファイルする間に得た情報を用いて、実行可能コード１３０におけるホットスポットの命令のトレースを確立する。本発明の一実施形態において、システムは、それぞれ、約２０００個の命令の約１００個の分散したトレースを構成する。その後、システムは、これらのトレースを、対応するソースコードに戻って相関させる（工程３０４）。
【００３５】
次に、システムは、トレースをプリフェッチするコードを生成することによって、縮小された実行可能コード１３２を作成する（工程３０６）。このプロセスは、以下で、図４、５、および９を参照しながら、より詳細に説明される。
【００３６】
また、システムは、プロセッサからプロセッサへの通信コードを、実行可能コード１３０および縮小された実行可能コード１３２の両方に挿入し得る（工程３０８）。この通信コードは、一次プロセッサ１０２が進行（ｐｒｏｇｒｅｓｓ）情報を補助プロセッサ１０４に知らせるようにさせる。この進行情報は、補助プロセッサ１０４が、正しい経路に沿ってプリフェッチしているのか否か、プリフェッチを継続するために、一次プロセッサ１０２よりも早すぎないか否かを判定することを可能にする。
【００３７】
プリフェッチが早過ぎた命令は一次プロセッサ１０２によって用いられる可能性が低く、一次プロセッサ１０２の直後により必要とされるデータに取って代わる可能性があるので、補助プロセッサ１０４が、一次プロセッサ１０２よりも早すぎる状態で命令をプリフェッチすることが望ましくないことに留意されたい。用いられる可能性が低い命令をプリフェッチすることは、メモリの帯域幅を拘束し、コンピュータ性能を低下させるキャッシュ汚染につながり得る。従って、プリフェッチ命令を開始する前に、補助プロセッサ１０４の対応するコードに対して、一次プロセッサ１０２の実行経路が閉じられるまで、補助プロセッサ１０４は待機することが望ましい。
【００３８】
また、典型的には、単一のプリフェッチ動作が、複数の命令を含むキャッシュライン全体を取り出すことにも留意されたい。例えば、プリフェッチキャッシュラインは、１６個の４バイト命令を含む６４バイトを含み得る。
【００３９】
この進行情報が、補助プロセッサ１０４が実行可能コード１３０を介して誤った経路に沿ってプリフェッチしていることを示す場合、システムは、補助プロセッサ１０４が命令トレースのプリフェッチを停止させるようにさせる。
【００４０】
図４は、本発明の実施形態による、縮小された実行可能コード１３２の１つの可能な構成を示す図である。この実施形態において、縮小された実行可能コード１３２は、ループとして構成される。コードは、まず、変数「ｖａｌ」を読み出すことから開始する。「ｖａｌ」は、共有メモリ内、または、図１のレジスタ１２６内に位置し得る。ｖａｌが０と等しくない場合、システムは、ｖａｌに含まれる値に基づいて、プリフェッチ動作を含むコードの特定の部分を実行するスイッチステートメントを実行する。このようにして、一次プロセッサ１０２は、進行情報を、変数ｖａｌを通じて補助プロセッサ１０４に知らせ得る。この進行情報は、特定のプリフェッチ命令が実行されて、一次プロセッサ１０２が命令を必要とする前に、補助プロセッサ１０４が命令をプリフェッチするようにさせる。その後、コードは、ｖａｌを０にリセットして、ループを続ける。ｖａｌの読み出しおよび書き込みは、同期化されないことに留意されたい。
【００４１】
図５は、本発明の実施形態による、縮小された実行可能コード１３２をいかに構成するか詳細に示したフローチャートである。システムは、実行可能なコード１３０の制御フローグラフを構成する工程（工程５０２）から開始する。次に、小さいループはＬ２キャッシュ１１３にプリフェッチされることが想定されるため、システムは、制御フローグラフから小さいループを取り除く（工程５０４）。従って、小さいループが取り除かれた後、ループが終了するまで実行される。また、システムは、実行可能なコード１３０から、制御フローグラフに関係しない全ての命令を取り除く（工程５０６）。これは、関係ないコードが、コートを通じて実行経路に影響を与えず、必要なプリフェッチ動作に影響を与えないので、行われ得る。例えば、数学的な計算を行う決定論コードが取り除かれ得る。
【００４２】
次に、システムは、プリフェッチ命令を縮小された実行可能コード１３２に挿入して、実行可能コード１３０の対応する箇所の命令をプリフェッチする（工程５０８）。
【００４３】
（プロセスの停止）
図６は、本発明の実施形態による、縮小された実行可能コード１３２が、誤った経路に沿って処理していたと判定する場合にいかに停止するかを示すフローチャートである。システムは、補助プロセッサ１０４上で実行される縮小された実行可能コード１３２が、一次プロセッサ１０２によって書き込まれた進行情報を読み出すとき（工程６０２）に開始される。この進行情報は、一次プロセッサ１０２の実行経路が、実行可能コード１３０内で向かった場所を示す。
【００４４】
補助プロセッサ１０４が誤った経路に沿って処理していることをこの進行情報が示す場合、補助プロセッサ１０４は、トレースのプリフェッチを中断する（工程６０４）。補助プロセッサは、正しい経路に沿ったプリフェッチを、任意に開始する。
【００４５】
プリフェッチプロセス中、補助プロセッサ１０４は、分岐の片側のみをプリフェッチするように決定し得、一次プロセッサ１０２は、分岐の他方の側をプリフェッチすることを実際に決定し得ることに留意されたい。この場合、補助プロセッサ１０４は、誤った経路を選択している。
【００４６】
また、補助プロセッサ１０４が、必ずしも停止する必要がないことにも留意されたい。誤った経路に沿ってプリフェッチすることによる不利益は、キャッシュの汚染および不必要なメモリ転送のみであり、これは、非常に小さいトレースについては、大きなファクタになり得ない。
【００４７】
（履歴情報を格納する専用ハードウェア）
図７は、本発明の実施形態による、縮小された実行可能コード１３２がいかに動作するかを示すフローチャートである。システムは、実行可能コード１３０について制御フロー履歴情報を記録する専用ハードウェアから、制御フロー履歴情報を読み出す工程（工程７０２）から開始する。例えば、この制御フロー履歴情報は、いずれの分岐が選択され、いずれの関数呼び出しが実行されたかについての記録を含み得る。次に、システムは、制御フロー履歴情報に基づいて、実行可能コード１３０を通じる予測された経路を構成する（工程７０４）。例えば、予測された経路は、実行可能コード１３０を通じる選択された最後の経路に基づいて、あるいは、実行可能コード１３０を通じる、最も頻繁に選択される経路に基づいて、判定され得る。次に、縮小された実行可能コード１３２は、補助プロセッサ１０４が予測された経路に沿ってプリフェッチ動作を行うようにさせる（工程７０６）。
【００４８】
図８は、本発明の実施形態による、制御フロー履歴情報を格納する専用ハードウェアを示す図である。この実施形態においては、専用ハードウェアは、関数を呼び出し、または復帰用の呼び出しアドレスを格納する。全ての呼び出しについて、ハードウェアは、後続の分岐が選択されたか否かについての記録を格納する。例えば、第１のロウは、アドレス「Ｘ」にあり、選択された分岐、選択されていない分岐、その後に３つの選択された分岐が続く関数呼び出しを特定する。第２のロウは、アドレス「Ｙ」にあり、分岐がない関数呼び出しを特定する。第３のロウは、アドレス「Ｙ＋４」への関数呼び出しからの復帰を特定する。最終的に、第４のロウは、アドレス「Ｚ」にあり、２つの選択された分岐、および選択されていない分岐が続く関数呼び出しを特定する。
【００４９】
（サンプル縮小された実行可能コード）
図９は、本発明の実施形態による、プリフェッチ命令を含む実行可能コード１３２のサンプル部分を示す図である。
【００５０】
図９の左側に、実行可能コード１３０のある部分の構造を示す。この部分は、複数のブロック９０２、９０４、９０６、９０８、９１０、および９１２に分割され、各々のブロックは、長さが６４バイトであり、単一プリフェッチ動作でプリフェッチされ得る。実行可能コード１３０が、まず、ブロック９０２を実行し、ブロック９０２が、ブロック９０４またはブロック９０６への分岐を行うことに留意されたい。ブロック９０４および９０６の両方が、ブロック９０８への関数呼び出しを行う。その後、ブロック９０８は、ブロック９１０またはブロック９１２のいずれかへの分岐を行い得る。
【００５１】
図９の右側に、縮小された実行可能コード１３２の一部分の対応する構造を示す。縮小された実行可能コード１３２は、まず、ブロック９０２、９０４、および９０６をプリフェッチする。次に、変数「ａｄｄｒ」が、関数呼び出しの目標アドレスと共に、ロードされ、縮小された実行可能コード１３２は、ブロック９０８、９１０、および９１２をプリフェッチする。
【００５２】
縮小された実行可能コード１３２が、実行可能コード１３０の両側でプリフェッチすることに留意されたい。本発明の他の実施形態において、縮小された実行可能コード１３２は、不必要な命令ロードおよび命令キャッシュ汚染を無くすため、予測された分岐経路のみでプリフェッチする。
【００５３】
また、プリフェッチ動作が、実行可能コード１３０のブロックを、図１のＬ２キャッシュ１１３に移動させることに留意されたい。あるいは、プリフェッチ動作は、一次プロセッサ１０２について、命令キャッシュ１１２に向かって全体的に命令がプリフェッチされるようにさせ得る。
【００５４】
本発明の上記の説明は、例示および説明のためのみに提示されてきた。上記の説明は、網羅するものではなく、本発明を開示された形態に限定するものでもない。従って、多くの改変例および変形例が、当業者にとって明らかである。さらに、上記の開示内容は、本発明を限定するものではない。本発明の範囲は、添付の特許請求の範囲によって規定される。
【図面の簡単な説明】
【図１】    図１は、本発明の実施形態による、コンピュータシステムを示す図である。
【図２】  図２は、本発明の実施形態による、コンパイルプロセスを示す図である。
【図３】  図３は、本発明の実施形態による、実行可能コードの縮小バージョンを生成するプロセスを示すフローチャートである。
【図４】  図４は、本発明の実施形態による、縮小された実行可能コードの例示的な構造を示す図である。
【図５】  図５は、本発明の実施形態による、実行可能コードの縮小バージョンをいかに構成するかを詳細に示すフローチャートである。
【図６】  図６は、本発明の実施形態による、実行可能コードの縮小バージョンが、誤った経路に沿って処理していたと判定する場合にいかに停止するかを示すフローチャートである。
【図７】  図７は、本発明の実施形態による、専用ハードウェアから制御フロー履歴情報を読み出すことによって、実行可能コードの縮小バージョンがいかに動作するかを示すフローチャートである。
【図８】  図８は、本発明の実施形態による、制御フロー履歴情報を格納する専用ハードウェアを示す図である。
【図９】  図９は、本発明の実施形態による、縮小された実行可能コードのサンプル部分を示す図である。
【図１】
0004808910.tif 000002
【図２】
0004808910.tif 000003
【図３】
0004808910.tif 000004
【図４】
0004808910.tif 000005
【図５】
0004808910.tif 000006
【図６】
0004808910.tif 000007
【図７】
0004808910.tif 000008
【図８】
0004808910.tif 000009
【図９】
0004808910.tif 000010