(57)【特許請求の範囲】
【請求項１】
主記憶装置と、該主記憶装置と通信し且つ先取り命令を含む命令ストリームを受け取って実行するよう構成されたプロセッサと、該プロセッサと通信するキャッシュとを有し、該キャッシュが、可変のインクリメント情報を収容するよう構成されたキャッシュ・セット番号によって識別可能な複数のキャッシュ・セットを含むコンピュータ装置であって、
前記プロセッサと通信し、前記先取り命令にフィールドを提供し、該フィールドに初期デフォルト値を提供して拡張先取り命令を発生するための先取り実行ユニットと、
前記先取り実行ユニットと通信し、前記先取り命令の実行時の検索のために前記拡張先取り命令を記憶するための先取り命令バッファと、
を具備するコンピュータ装置。
【請求項２】
１つの前記フィールドがキャッシュ・セット番号に関連する値を収容するものである、請求項１記載のコンピュータ装置。
【請求項３】
１つの前記フィールドが先取りサイズ・インクリメントと関連する値を収容するものである、請求項１記載のコンピュータ装置。
【請求項４】
前記キャッシュが、データである情報のためのキャッシュ・セットと命令である情報のためのキャッシュ・セットとの異なるキャッシュ・セットを含み、１つの前記フィールドが前記情報がデータであるか命令であるかに関連する値を含むためのものである、請求項１記載のコンピュータ装置。
【請求項５】
前記プロセッサが、第１の拡張先取り命令を実行して第１の情報を主記憶装置から検索し、前記キャッシュ・セットのうちの１つに記憶させると共に、第２の拡張先取り命令を実行して第２の情報を主記憶装置から検索し、前記第２の情報で前記第１の情報を上書きするように前記キャッシュ・セットのうちの１つに記憶させ、もって第１の先取り犠牲情報を発生するようにした請求項１記載のコンピュータ装置であって、
前記先取り実行ユニットと通信し、前記第１の先取り犠牲情報に関連した情報を記憶するための先取り犠牲バッファ
をさらに備えるコンピュータ装置。
【請求項６】
前記第１の先取り犠牲情報が先取りタグによって識別可能である、請求項５記載のコンピュータ装置。
【請求項７】
前記先取り犠牲バッファが前記先取りタグを記憶する、請求項６記載のコンピュータ装置。
【請求項８】
前記先取り犠牲バッファが前記先取り犠牲情報を記憶する、請求項５記載のコンピュータ装置。
【請求項９】
前記プロセッサは、前記第２の情報によって既に上書きされた前記第１の情報を検索するために前記キャッシュにアクセスした後、前記先取り犠牲バッファにアクセスし、前記第１の先取り犠牲情報に関連した情報を検索するよう構成されている、請求項５記載のコンピュータ装置。
【請求項１０】
前記先取り実行ユニットが、前記先取り犠牲情報に関連した情報を受け取って、前記第１の拡張先取り命令のフィールドに関連した値を修正し、該値を前記先取り命令バッファに記憶する、請求項５記載のコンピュータ装置。
【請求項１１】
主記憶装置と、該主記憶装置と通信し且つ先取り命令を含む命令ストリームを受け取って実行するよう構成されたプロセッサと、該プロセッサと通信するキャッシュとを有し、該キャッシュが、可変のインクリメント情報を収容するよう構成されたキャッシュ・セット番号によって識別可能な複数のキャッシュ・セットを含むコンピュータ装置であって、
前記プロセッサと通信し、前記先取り命令にフィールドを提供するための手段と、
前記プロセッサと通信し、前記フィールドに初期デフォルト値を提供して拡張先取り命令を発生するための手段と、
前記プロセッサと通信し、前記先取り命令の実行時の検索のために前記拡張先取り命令を記憶するための手段と、
を具備するコンピュータ装置。
【請求項１２】
１つの前記フィールドがキャッシュ・セット番号に関連する値を収容するものである、請求項１１記載のコンピュータ装置。
【請求項１３】
１つの前記フィールドが先取りサイズ・インクリメントに関連する値を収容するものである、請求項１１記載のコンピュータ装置。
【請求項１４】
前記キャッシュが、データである情報のためのキャッシュ・セットと命令である情報のためのキャッシュ・セットとの異なるキャッシュ・セットを含み、１つの前記フィールドが前記情報がデータであるか命令であるかに関連する値を含むためのものである、請求項１１記載のコンピュータ装置。
【請求項１５】
前記プロセッサが、第１の拡張先取り命令を実行して第１の情報を主記憶装置から検索し、前記キャッシュ・セットのうちの１つに記憶させると共に、第２の拡張先取り命令を実行して第２の情報を主記憶装置から検索し、前記第２の情報で前記第１の情報を上書きするように前記キャッシュ・セットのうちの１つに記憶させ、もって第１の先取り犠牲情報を発生するようにした請求項１１記載のコンピュータ装置であって、
前記プロセッサと通信し、前記第１の先取り犠牲情報に関連した情報を記憶するための手段
をさらに備えるコンピュータ装置。
【請求項１６】
主記憶装置と、該主記憶装置と通信し且つ先取り命令を含む命令ストリームを受け取って実行するよう構成されたプロセッサと、該プロセッサと通信するキャッシュとを有し、該キャッシュが、可変のインクリメント情報を収容するよう構成されたキャッシュ・セット番号によって識別可能な複数のキャッシュ・セットを含むコンピュータ装置上で動作する方法であって、
先取り命令にフィールドを提供するステップと、
前記フィールドに初期デフォルト値を提供して拡張先取り命令を発生するステップと、
前記先取り命令の実行時の検索のために前記拡張先取り命令を記憶するステップと、
を具備する方法。
【請求項１７】
１つの前記フィールドがキャッシュ・セット番号に関連する値を収容するものである、請求項１６記載の方法。
【請求項１８】
１つの前記フィールドが先取りサイズ・インクリメントと関連する値を収容するものである、請求項１６記載の方法。
【請求項１９】
前記キャッシュが、データである情報のためのキャッシュ・セットと命令である情報のためのキャッシュ・セットとの異なるキャッシュ・セットを含み、１つの前記フィールドが前記情報がデータであるか命令であるかに関連する値を含むためのものである、請求項１６記載の方法。
【請求項２０】
前記プロセッサが、第１の拡張先取り命令を実行して第１の情報を主記憶装置から検索し、前記キャッシュ・セットのうちの１つに記憶させると共に、第２の拡張先取り命令を実行して第２の情報を主記憶装置から検索し、前記第２の情報で前記第１の情報を上書きするように前記キャッシュ・セットのうちの１つに記憶させ、もって第１の先取り犠牲情報を発生するようにした、請求項１６記載の方法であって、
前記第１の先取り犠牲情報に関連した情報を記憶するステップ
をさらに備える方法。
【請求項２１】
主記憶装置と、該主記憶装置と通信し且つ先取り命令を含む命令ストリームを受け取って実行するよう構成されたプロセッサと、該プロセッサと通信するキャッシュとを有し、該キャッシュが、可変のインクリメント情報を収容するよう構成されたキャッシュ・セット番号によって識別可能な複数のキャッシュ・セットを含むコンピュータ装置と結合して動作する先取り命令最適化デバイスであって、
前記プロセッサと通信し、前記先取り命令にフィールドを提供し、該フィールドに初期デフォルト値を提供して拡張先取り命令を発生するための先取り実行ユニットと、
前記先取り実行ユニットと通信し、前記先取り命令の実行時の検索のために前記拡張先取り命令を記憶するための先取り命令バッファと、
を具備する最適化デバイス。
【請求項２２】
１つの前記フィールドがキャッシュ・セット番号に関連する値を収容するものである、請求項２１記載の最適化デバイス。
【請求項２３】
１つの前記フィールドが先取りサイズ・インクリメントと関連する値を収容するものである、請求項２１記載の最適化デバイス。
【請求項２４】
前記キャッシュが、データである情報のためのキャッシュ・セットと命令である情報のためのキャッシュ・セットとの異なるキャッシュ・セットを含み、１つの前記フィールドが前記情報がデータであるか命令であるかに関連する値を含むためのものである、請求項２１記載の最適化デバイス。
【請求項２５】
前記プロセッサが、第１の拡張先取り命令を実行して第１の情報を主記憶装置から検索し、前記キャッシュ・セットのうちの１つに記憶させると共に、第２の拡張先取り命令を実行して第２の情報を主記憶装置から検索し、前記第２の情報で前記第１の情報を上書きするように前記キャッシュ・セットのうちの１つに記憶させ、もって第１の先取り犠牲情報を発生するように構成されている、請求項２１記載の最適化デバイスであって、
前記先取り実行ユニットと通信し、前記第１の先取り犠牲情報に関連した情報を記憶するための先取り犠牲バッファ
をさらに備える最適化デバイス。
【請求項２６】
前記第１の先取り犠牲情報が先取りタグによって識別可能である、請求項２５記載の最適化デバイス。
【請求項２７】
前記先取り犠牲バッファが前記先取りタグを記憶する、請求項２６記載の最適化デバイス。
【請求項２８】
前記先取り犠牲バッファが前記先取り犠牲情報を記憶する、請求項２５記載の最適化デバイス。
【請求項２９】
前記第２の情報によって既に上書きされた前記第１の情報を検索するために前記プロセッサが前記キャッシュにアクセスした後、前記プロセッサが前記第１の先取り犠牲情報に関連した情報を検索するように、前記先取り犠牲バッファが前記プロセッサによってアクセスされるよう構成されている、請求項２５記載の最適化デバイス。
【請求項３０】
前記先取り実行ユニットが、前記先取り犠牲情報に関連した情報を受け取って、前記第１の拡張先取り命令のフィールドに関連した値を修正し、該値を前記先取り命令バッファに記憶する、請求項２５記載の最適化デバイス。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、キャッシュ・メモリに関するもので、特に、キャッシュ・メモリへ先取りされたデータ又は命令によって生じるスラッシング（ｔｈｒａｓｈｉｎｇ）を回避するためのハードウェア機構に関する。
【０００２】
【従来の技術】
コンピュータ産業において、開発者は前の世代の製品よりも動作速度が速いコンピュータを設計するよう働く。処理チップの速度が上がるにつれ、プロセッサの速度と主記憶装置へのアクセス速度との間の格差も大きくなる。この格差は記憶待ち（ｍｅｍｏｒｙ  ｌａｔｅｎｃｙ）と呼ばれる。つまり、命令又はデータを主記憶装置から検索するよりも高速で、プロセッサは命令を実行することができる。記憶待ちの結果、主記憶装置から移送されるべきデータ又は命令を待つ間、プロセッサはアイドル状態にある。したがって、高速プロセッサの効率はデッド時間によって大幅に低減される。
【０００３】
次世代のＣＰＵは３ナノ秒のオーダーの極めて速いクロック速度で動作することになろう。しかし、主記憶装置のクロック速度は５０ナノ秒までは高まると予測されるにすぎない。つまり、次世代コンピュータの記憶待ちは１５：１という比よりも大きくなると予測される。
【０００４】
記憶待ちを回避するために、使用頻度の高いデータ又は命令（情報）は、主記憶装置よりもプロセッサの近くにあるキャッシュ・メモリに記憶される。開発者は、プログラムの実行期間に直ぐに必要とされると予測される情報を主記憶装置から検索するために、命令ストリームのコードに含まれる（ｎｅｓｔｌｅｄ）先取り命令を使うことが多い。先取り情報はキャッシュに記憶されてプロセッサに使用される。
【０００５】
しかしながら、キャッシュに記憶された情報は、その後に検索される他の情報によって上書きされることが多い。上書きされた情報へのアクセスが必要なとき、プロセッサはキャッシュ・ミス（ｃａｃｈｅ  ｍｉｓｓ）を経験する。上書きされた情報は主記憶装置から再び検索されなければならず、プログラムの実行速度を下げる。この速度低下はキャッシュ・ミス・ペナルティと呼ばれる。
【０００６】
キャッシュ・ミスを説明すると、図１は主記憶装置１０がキャッシュ・セット１２及びＣＰＵ（プロセッサ）１４と通信する。情報を記憶する行１４００がＣＰＵによって要求され、主記憶装置１０から検索され、キャッシュ・セット１２のオフセット４００に記憶される。その後、どこかの時点に、ＣＰＵ１４は主記憶装置１０から行２４００を検索し、それをキャッシュ・セット１２のオフセット４００にマッピングする。つまり、行２４００は以前に記憶されていた行１４００を上書きしたことになる。ＣＰＵ１４は、行１４００を探索するとき、行１４００を発見しない。ＣＰＵは主記憶装置１０から行１４００を再び検索しなければならない。したがって、ミス・ペナルティは、キャッシュが以前に記憶した行を含んでいなかったが故に引き起こされる。
【０００７】
上記の状況においては、ミス・ペナルティが生じる毎に、プログラムの実行速度は下がる。行１４００及び行２４００を必要とする頻度が高いとき、ミス・ペナルティは特に面倒である。反復される犠牲を伴う「ピンポン」的な状態は、スラッシング（ｔｈｒａｓｈｉｎｇ）として知られる極めて望ましくない状態を生じる。
【０００８】
図１に戻ると、スラッシングを説明するために、ＣＰＵ１４は２つの行１４００及び２４００を規則的に必要とするとする。先取り命令が実行コードの部分である場合、高価な処理帯域幅は、先取り命令を実行するので有効には使用されないが、こうしたことはキャッシュ・ミスがなければ無視されたであろう。複合ミス・ペナルティがＣＰＵのパフォーマンスを支配するとき、高速マイクロプロセッサの能力は最適化されないし、実現されることもない。
【０００９】
スラッシングの問題を除去しようとする努力の中で、多くの異なる形式のキャッシュ構造が紹介された。例えば、１つの広く普及した解は、図１の１組（１セット）のキャッシュの代わりに、「複数組（複数セット）のキャッシュ」を使用することである。図２は２組のキャッシュを示している。キャッシュ・セット１２とキャッシュ・セット１６とは情報を記憶するオフセット位置４００を有する。つまり、行１４００及び行２４００はキャッシュに同時に記憶され、これらの行のいずれか一方に対する交互の要求はスラッシングを起こさない。複数組のキャッシュの実際的な利益は、実行されるプログラムに依存する。しかし、一組のキャッシュよりも複数組のキャッシュの方が進歩していても、ミス・ペナルティに対するパフォーマンス・コストは、ＣＰＵの処理速度が上がるにつれて上昇し続ける。
【００１０】
データと命令に対して別々のキャッシュが存在するハーバード（Ｈａｒｖａｒｄ）アーキテクチャにおいては、スラッシングはデータが命令と拮抗する（ｔｈｒａｓｈ）程度以上に低減される。
【００１１】
時間に先立ってＣＰＵの要求を予測しようとする種々の機構が存在する。例えば、ハーバード・アーキテクチャのデータ・キャッシュを先取りするデータ先取り命令を実行する能力が、ＳＰＡＲＣ（Ｒ）バージョン９アーキテクチャに組み込まれている。しかし、先取り命令は不変であって固定サイズであり、他の融通のきく特性を提供しない。
【００１２】
１９９５年７月７日に出願された「先取り命令を用いたハーバード・アーキテクチャ・キャッシュの同調可能なソフトウェア制御」という名称の米国特許出願第０８／４９９３１２号、及び、同日に出願された「先取り制御と協働するメモリ管理ユニット」という名称の米国特許出願第０８／４９９３６４号は、スラッシングを最小化するためのアーキテクチャ及びソフトウェア先取り制御を開示している。これらの米国特許出願の記載内容は本明細書に援用される。
【００１３】
【発明が解決しようとする課題】
典型的な命令ストリームの先取り命令は不変で固定サイズの先取りを提供するにすぎないので、スラッシングを回避するために先取り命令の特性を操作するためのハードウェア機構が望まれている。
【００１４】
【課題を解決するための手段】
この発明は、スラッシングを最小にするためのハードウェア構成を含む。この発明によると、コンピュータは、主記憶装置、プロセッサ及びキャッシュを有するのに加えて、先取り命令バッファ及びそれに関連する先取り実行ユニット、先取り犠牲バッファを有する。
【００１５】
典型的には、先取り命令は、コンピュータ上で実行されているアプリケーションの命令ストリームに埋め込まれている。通常、こうした先取り命令はアドレス・フィールドを有する。先取り命令の実行中には、この発明の先取り実行ユニットは、拡張（ａｕｇｍｅｎｔｅｄ）先取り命令を生成するために、初期デフォルト設定を有する追加のフィールドを発生する。例えば、この追加のフィールドはキャッシュ・セット番号、サイズ・インクリメント及び／又は情報形式（データ又は命令）に対するものである。
【００１６】
先取り実行ユニットは、特定のキャッシュ・ミスの履歴のアカウンティング（ａｃｃｏｕｎｔｉｎｇ）に依存することによって先取り処理を最適化するよう動作する。キャッシュ・ミスを記録するために、犠牲にされた（上書きされた）行及び／又は先取りタグが先取り犠牲バッファに記憶される。プロセッサがキャッシュ・ミスを経験すると、プロセッサは先取り犠牲バッファをアクセスし、先取り犠牲情報に関する情報を検索する。そこで、先取り実行ユニットは追加のフィールドの値を修正し、修正された拡張先取り命令を先取り命令バッファに記憶する。次回にプロセッサが犠牲にされた行に対する先取り命令を実行するとき、修正された拡張先取り命令はどこに先取り命令が記憶されており、どのサイズ・インクリメントを有するかを指示する。拡張先取り命令を連続的に修正することにより、結局はスラッシングを除去することができる。
【００１７】
【発明の実施の形態】
典型的には、プログラマは高水準プログラミング言語でソフトウェアをプログラムする。図３において、高水準プログラム２０は、先取り命令２４を実行可能コードに挿入するためにコンパイラ２２によって動作される。アドレス・フィールド＜Ａｄｒ＞２８を有する先取り命令を含む機械コード２６はプロセッサによって処理される。アドレス・フィールドに含まれる主記憶装置１０での情報の記憶場所は静的である。
【００１８】
この発明は、セット番号やサイズ・インクリメントのような可変の特性を持つように、静的な先取り命令を拡張するもので、以下、その実施の形態をハードウェア要素の組み合わせとして説明する。ソフトウェア要素又はアーキテクチャ要素でも、この発明を実施することは可能である。
【００１９】
図４において、ＣＰＵ１４は、アドレス・フィールドを有する先取り命令を含む命令ストリームを受け取る。先取り命令を受け取ると、ＣＰＵは当該特定の命令を先取り命令バッファ５０において探索する。その特定の先取り命令が先取り命令バッファ５０にないとき、先取り実行ユニット５２は可変のフィールドを有するように当該先取り命令を拡張する。典型的には、先取り実行ユニット５２はＣＰＵの一部分であり、ＣＰＵの実行ユニットの１つである。図４においては、説明のために先取り実行ユニット５２は別個に図示されている。例えば、２進のフィールドは
ＰＲＥＦＥＴＣＨ<Ａddr Ｔranslation Ｉnfo><I/D Ｂit><Ｓet ♯><Ｓize>
のように構成される。
【００２０】
先取り命令は、拡張されると、初期フィールド値設定と共に先取り命令バッファ５０に記憶される。これらのフィールドに対する初期値は先取り実行ユニット５２によって発生される。Ｉ／Ｄビットの初期設定は情報がデータであるか命令であるかに依存する。図４においては、データ・キャッシュ３０は複数のセット３２、３４、３６を有する。命令キャッシュ４０は複数のセット４２、４４、４６を有する。
【００２１】
例えば、キャッシュ・セット番号フィールドに対する初期設定は、以前に記憶された行を上書きしないように、一連の先取り命令に対して逐次的である。サイズ・フィールドの設定は実行されているプログラムの形式、例えば、データ・フィールドが大きいか小さいかに依存する。
【００２２】
初期フィールド設定は、プロセッサ上で実行されている特定のアプリケーションに基づいて、スラッシングを回避するための能力を最適化するよう調整される。しかし、キャッシュ・ミスが存在すると、拡張先取り命令の設定は修正されなければならず、これについては後述する。
【００２３】
キャッシュに記憶されたラインを追い出す先取り命令が実行されると、犠牲となる行３８（Ｄ−セットＮ３６の行４００−６００）は先取り犠牲バッファ５４に記憶される。ＣＰＵ即ちプロセッサ１４によるプログラムの実行中に、犠牲にされた行３８に関するキャッシュ・ミスが次回に存在すると、プロセッサは犠牲にされた行に関する情報を先取り犠牲バッファから検索する。例えば、実際の犠牲にされた行は、先取りタグと共に先取り犠牲バッファに記憶される。代わりに、先取りタグのみを記憶するようにしてもよい。先取りタグは先取り命令バッファ５０に記憶された拡張先取り命令をマッピングするものである。そこで、先取り実行ユニット５２はフィールド値を変更することによって拡張先取り命令を修正する。
【００２４】
先取り命令バッファ５０においては、拡張先取り命令に対して行われた修正のレコードが維持される。例えば、セット番号のレコードが維持されるので、次回の修正においてセット・カウンタはセット番号フィールドに含まれる値にインクリメントを加えることができる。
【００２５】
次に、この発明の高水準のフローチャートを示す図５について説明する。先取り命令を含む命令ストリーム２６（図３参照）がＣＰＵ１４によって処理される。先取り命令２８が命令ストリーム２６の一部分であるとき、先取り実行ユニット５２は、判定ステップ６０において、当該先取り命令に対するエントリが先取り命令バッファ５０に既に存在するかどうかを決定する。既に存在するならば、実行中のプログラムはステップ６２において実行される。当該プログラム命令に対するエントリがプログラム命令バッファ５０に存在しないとき、ステップ６４において、先取り実行ユニット５２は先取り命令を追加のフィールドで拡張する。前述のとおり、フィールドが追加され、先取り命令はデータ／命令フィールド、セット番号フィールド及びサイズ・フィールドを含むことになる。
【００２６】
新たなフィールドには初期値が割り当てられる。割り当てられる初期セット番号は、以前に処理された先取り命令に割り当てられたセット番号に依存する。例えば、最初に処理された先取り命令のセット番号フィールドにセット番号Ｄ−セット１の値が割り当てられているとすると、次に処理される先取り命令のセット番号フィールドにはセット番号Ｄ−セット２の値が割り当てられる。サイズ・インクリメントの初期値はアドレス・フィールドによって与えられる値と等価である。
【００２７】
新たなフィールドに初期値が割り当てられると、拡張先取り命令はステップ６６において先取り命令バッファ５０に記憶される。先取り命令を拡張するステップが行われている期間又は行われた後、プログラムはステップ６２において実行される。
【００２８】
ステップ６２におけるプログラムの実行中に、ステップ６８でキャッシュ・ミスがないと判定されると、ステップ６２でのプログラムの実行が継続される。しかし、キャッシュ・ミスが存在すると、それに関連する拡張先取り命令を調整してスラッシングを回避しなければならない。この場合、ステップ７０において、プロセッサは、犠牲にされたデータ又は命令そのもの及び／又は先取りタグを先取り犠牲バッファ５４から検索し、最初にデータ・キャッシュ３０又は命令キャッシュ４０へのデータ又は命令の記憶の原因となった先取り命令を識別する。ステップ７２において、実際の拡張先取り命令が検索され、前述のようにフィールドが変更される。
【００２９】
ステップ７４において修正の処理が行われる。修正されると、拡張先取り命令はステップ６６において先取り命令バッファ５０に記憶される。したがって、次回に命令ストリームが先取り命令を含むとき、修正された拡張先取り命令が先取り命令バッファ５０からアクセスされて実行される。修正を最適化することにより、拡張先取り命令の反復修正は不要なスラッシングという状況を最終的に回避する。
【００３０】
図６は、図５に示すフローチャートに追加されるステップを示すフローチャートである。前述のとおり、ステップ７６でプログラムが実行を開始すると、ＣＰＵ１４はステップ７８において命令を主記憶装置１０から要求する。ステップ８０において、命令が先取り命令でないと判定されれば、該命令はステップ８２において単に実行されるだけである。ステップ８４においてキャッシュ・ミスが発生していないと判定されれば、プログラムは進行し、ＣＰＵ１４はステップ７８において命令を再び主記憶装置から要求する。しかし、ステップ８４においてキャッシュ・ミスが発生していると判定されれば、失われたキャッシュ行は先取り犠牲バッファ５４に存在するかどうかが質問される。失われたキャッシュ行が先取り犠牲バッファ５４に存在しないとステップ８６において判定されると、処理はステップ７８で再開されなければならない。つまり、データ又は命令を主記憶装置から検索しなければならない。
【００３１】
失われたキャッシュ行が先取り犠牲バッファ５４に存在するならば、次のステップは、失われたキャッシュ行の記憶の原因となった先取り命令のセット番号が以前に修正されたかどうかをステップ８８において質問することである。この質問に対する回答は、セット番号がインクリメントされるかどうか、及び、主記憶装置から検索されたデータ又は命令のサイズを縮小（又は、状況に応じてはインクリメント）すべきかどうかを決定する。セット番号が修正されたかどうかを指示するビットが先取り命令バッファに存在する。該ビットはそれぞれの先取り命令毎に最初はゼロにセットされる。先取り命令が修正されると、該ビットは１にセットされる。したがって、特定の先取り命令が修正されたことのレコードが先取り命令バッファに存在することになる。その代わりに、修正レコードは、キャッシュ・セットの数までカウントアップしてから何個のセットの修正が行われたかの指示を与える複数ビットであってもよい。
【００３２】
特定の先取り命令が修正され、利用可能なそれぞれのセット番号が使用された（ステップ７４ａ）がキャッシュ・ミスが発生している場合には、サイズ・フィールドの値が修正される（ステップ７４ｂ）。即ち、それぞれのセット番号が使用された場合、別の犠牲情報を作るために、サイズ・フィールドが修正される。拡張先取り命令のフィールドの値を修正することによって、次回に先取り命令が実行されるとき、先取り命令は犠牲にされたキャッシュ行を上書きしない。こうしてスラッシングが回避される。最後に、ステップ９０において、犠牲にされた行が先取り犠牲バッファからフラッシュ（ｆｌｕｓｈ）される。この行は犠牲情報ではないからである。
【００３３】
図６の左側においては、ステップ８０で命令が先取り命令であると判定された場合、ステップ６０で、ＣＰＵは先取り命令バッファ５０において先取り命令を探索する。ステップ６０において先取り命令が先取り命令バッファに存在しないと判定されたとき、ステップ６４において、先取り命令バッファでのエントリが作られる。先取り命令はステップ９２において実行される。先取り命令によって犠牲にされたキャッシュ行はステップ９４において先取り犠牲バッファ５４に置かれる。その代わりに、先取り命令が主記憶装置から検索され、当該先取り命令に対応するエントリが先取り命令バッファ５０にある場合（ステップ６０）、セット番号とサイズとの値が先取り命令バッファ５０から検索され、これらの値は、ステップ９６において、（デフォルト値を挿入する代わりに）拡張先取り命令のセット番号とサイズのフィールドに挿入される。この修正された先取り命令はステップ９２において実行される。当該先取り命令がキャッシュ行を犠牲にするならば、犠牲にされた行は先取り犠牲バッファ５４に記憶される。
【図面の簡単な説明】
【図１】公知の一組のキャッシュを示す。
【図２】公知の複数組のキャッシュを示す。
【図３】高水準プログラムと命令を挿入するコンパイラと該命令を含む機械コードとの間の関係を示す。
【図４】この発明のプログラム命令が実行されるハーバード・アーキテクチャ・システムを示す。
【図５】この発明を実行するためのステップを示すフローチャートである。
【図６】この発明を実行するための追加のステップを示すフローチャートである。
【符号の説明】
１０：主記憶装置、  １２、１６：キャッシュ・セット、１４：ＣＰＵ、
２０：プログラム、  ２２：コンパイラ、  ２４：先取り命令、
２６：機械コード、  ３０：データ・キャッシュ、  ４０：命令キャッシュ、
５０：先取り命令バッファ、  ５２：先取り実行ユニット、
５４：先取り犠牲バッファ
【図１】
0003718319.tif 000002
【図２】
0003718319.tif 000003
【図３】
0003718319.tif 000004
【図４】
0003718319.tif 000005
【図５】
0003718319.tif 000006
【図６】
0003718319.tif 000007