(57)【要約】  プリフェッチ制御装置に、ネクストラインプリフェッチ制御装置３８を新たに設ける。プリフェッチアドレスキュー２６からあふれ出したアドレスは、ネクストラインプリフェッチ制御装置３８に格納される。レジスタ２５に格納されるプロセッサユニットの発行するアクセスアドレスとネクストラインプリフェッチ制御装置３８のアドレスとを比較し、一致が得られた場合には、ネクストラインプリフェッチ制御装置３８のアドレスにキャッシュメモリのデータのブロックサイズλを加算した値を再びネクストラインプリフェッチ制御装置３８に格納する。このようにして、プロセッサユニットの発行するアドレスがネクストラインプリフェッチ制御装置３８のアドレスと所定回数一致すると、連続アクセスが発生しているとし、プリフェッチアドレスキューにヒットしなかったすべてのアドレスについてプリフェッチを行うようにする。
2007099582.tif 000002
【特許請求の範囲】
【請求項１】
主記憶装置、キャッシュメモリ及びプロセッサを備えた情報処理装置における、主記憶装置からキャッシュメモリへのプリフェッチを制御するプリフェッチ制御装置において、
該キャッシュメモリへのプリフェッチを要求するために、該プロセッサからのアクセスアドレスとの比較用の複数のアドレスを格納するプリフェッチアドレスキュー手段と、
該プリフェッチアドレスキュー手段からあふれたアドレスを格納し、該プロセッサから、格納されたアドレスと一致するアドレスにアクセスがあった場合に、該アドレスを、これに連続する次のアドレスに書き換え、該プロセッサからの、格納されたアドレスと一致するアドレスへのアクセスが連続して所定回数あった場合に、以後のキャッシュミスしたアクセスアドレスに連続する次のアドレスのプリフェッチを行うネクストラインプリフェッチを実行させるネクストラインプリフェッチ制御手段と、
を備えることを特徴とするプリフェッチ制御装置。
【請求項２】
前記連続した所定回数のアクセスの計数においては、アクセスがあった時からカウント値をカウントし、次のアクセスが、該カウント値が所定値に達しない間にあった場合に、アクセスが連続しているとすることを特徴とする請求項１に記載のプリフェッチ制御装置。
【請求項３】
該カウント値が所定値になった場合には、前記ネクストラインプリフェッチ動作を解除することを特徴とする請求項２に記載のプリフェッチ制御装置。
【請求項４】
前記ネクストラインプリフェッチにおいては、キャッシュミスしたアクセスアドレスを前記プリフェッチアドレスキュー手段に格納させ、前記プロセッサからのアクセスアドレスとの比較を行わずに、前記キャッシュメモリへのプリフェッチ要求を行わせることを特徴とする請求項１に記載のプリフェッチ制御装置。
【請求項５】
前記次のアドレスは、元のアドレスに、キャッシュメモリのデータの格納単位であるデータブロックのサイズを加算した値であることを特徴とする請求項１に記載のプリフェッチ制御装置。
【請求項６】
前記キャッシュメモリは、一次キャッシュと二次キャッシュからなり、前記プリフェッチは、一次キャッシュにおいて発生したキャッシュミスに対して、二次キャッシュに前記主記憶からデータをフェッチさせることを特徴とする請求項１に記載のプリフェッチ制御装置。
【請求項７】
主記憶装置、キャッシュメモリ及びプロセッサを備えた情報処理装置における、主記憶装置からキャッシュメモリへのプリフェッチを要求するために、該プロセッサからのアクセスアドレスとの比較用の複数のアドレスを格納するプリフェッチアドレスキュー手段を備えたプリフェッチ制御装置の制御方法において、
該プリフェッチアドレスキュー手段からあふれたアドレスを格納し、
該プロセッサから、格納されたアドレスと一致するアドレスにアクセスがあった場合に、該アドレスを、これに連続する次のアドレスに書き換え、
該プロセッサからの、該格納されたアドレスと一致するアドレスへのアクセスが連続して所定回数あった場合に、以後のキャッシュミスしたアクセスアドレスに連続する次のアドレスのプリフェッチを行うネクストラインプリフェッチを実行させる
ことを特徴とする制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリを備えた情報処理装置におけるプリフェッチ制御装置に関する。
【背景技術】
【０００２】
従来から、コンピュータは、ＣＰＵと主記憶装置の間にキャッシュメモリを持ち、メモリアクセスの高速化をはかってきた。近年、主記憶装置に対するメモリアクセスに要する時間はＣＰＵの命令実行サイクルに比較して益々大きくなってきており、キャッシュメモリのヒット率向上やキャッシュミスレイテンシの改善がさらに望まれている。このような問題に対する一つの手段として、プリフェッチという方法が使われてきた。プリフェッチでは、近い将来必要とされている命令もしくはデータを予めキャッシュに読み込んでおくことで、キャッシュミス率を下げることを目的とするものである。【０００３】
しかし、不要なデータをプリフェチすると必要なデータをキャッシュから追い出す可能性もあり、かえってミス率を上げてしまうかもしれない。その為、プリフェッチするデータのアドレスを如何に予測するかが重要な課題となっている。例えば、特許文献１では、キャッシュアクセスしたアドレスをキューに登録することで、過去に連続したラインにアクセスしているアドレスを探し出し、それに基づいてプリフェッチアドレスを求めることによって無駄なプリフェッチを防いでいる。【０００４】
しかし、従来の技術では、プリフェッチアドレスキューのエントリ数を超えるメモリアクセスの系列がある場合にはキューからエントリがあふれ、プリフェッチが機能しない場合があった。
【特許文献１】特開２００４−３８３４５号公報
【発明の開示】
【０００５】
本発明の課題は、プリフェッチアドレスキューのエントリ数を超える連続メモリアクセスがあった場合にも、有効にプリフェッチを行うことができるプリフェッチ制御装置を提供することである。
【０００６】
本発明のプリフェッチ制御装置は、主記憶装置、キャッシュメモリ及びプロセッサを備えた情報処理装置における、主記憶装置からキャッシュメモリへのプリフェッチを制御するプリフェッチ制御装置において、該キャッシュメモリへのプリフェッチを要求するために、該プロセッサからのアクセスアドレスとの比較用の複数のアドレスを格納するプリフェッチアドレスキュー手段と、該プリフェッチアドレスキュー手段からあふれたアドレスを格納し、該プロセッサから、格納されたアドレスと一致するアドレスにアクセスがあった場合に、該アドレスを、これに連続する次のアドレスに書き換え、該プロセッサからの、格納されたアドレスと一致するアドレスへのアクセスが連続して所定回数あった場合に、以後のキャッシュミスしたアクセスアドレスに連続する次のアドレスのプリフェッチを行うネクストラインプリフェッチを実行させるネクストラインプリフェッチ制御手段とを備えることを特徴とする。
【図面の簡単な説明】
【０００７】
【図１】本発明の実施形態の動作の概略を説明する図（その１）である。
【図２】本発明の実施形態の動作の概略を説明する図（その２）である。
【図３】本発明の実施形態の動作の概略を説明する図（その３）である。
【図４】本発明の実施形態の動作の概略を説明する図（その４）である。
【図５】本発明の実施形態のプリフェッチ制御装置を含む情報処理装置の全体を示すブロック構成図である。
【図６】図５におけるプリフェッチ制御装置の内部構造を示した図である。
【図７】図６におけるプリフェッチアドレスキューの構成を示した図（その１）である。
【図８】図６におけるプリフェッチアドレスキューの構成を示した図（その２）である。
【図９】ネクストラインプリフェッチ制御装置の構成を示す図である。
【図１０】本発明の実施形態のプリフェッチ制御装置の動作を説明するタイムチャート（その１）である。
【図１１】本発明の実施形態のプリフェッチ制御装置の動作を説明するタイムチャート（その２）である。
【図１２】本発明の実施形態のプリフェッチ制御装置の動作を説明するタイムチャート（その３）である。
【図１３】本発明の実施形態のプリフェッチ制御装置の動作を説明するタイムチャート（その４）である。
【図１４】本発明の実施形態のプリフェッチ制御装置の動作を説明するタイムチャート（その５）である。
【発明を実施するための最良の形態】
【０００８】
本発明の実施形態では、プリフェッチアドレスキューからあふれたエントリを一定期間の間レジスタに保持し、その間にアクセスのあったアドレスとこのレジスタとのマッチの回数を計測する。そして、このマッチの回数をもとにしてプリフェッチを制御する。これによりエントリがあふれた時、アクセスが連続している場合はプリフェッチを要求し、ランダムアクセスであればプリフェッチを要求しないように制御する。すなわち、本発明の実施形態においては、特定の条件のもとで、キャッシュミスしたアドレスにブロックサイズλを加算したアドレスをプリフェッチする（以下、ネクストラインプリフェッチ）ように制御する。ここで、ブロックサイズλは、一次及び二次キャッシュにおけるデータの格納単位であるデータブロックのブロックサイズである。【０００９】
図１〜図４は、本発明の実施形態の動作の概略を説明する図である。
図１のように、アドレスＡ、Ｂ、Ｃ、Ｄ、Ｅから始まる連続した領域を平行してアクセスしている時のプリフェッチ制御装置の動きを説明する。プリフェッチアドレスキューのエントリ数が４の時は５個以上の連続したアクセスがある場合、次に示すように、プリフェッチアドレスキューは、あふれたアクセスについては、連続したアクセスであるにもかかわらずプリフェッチを要求できなくなる。【００１０】
図３の（１）〜（４）は、それぞれプリフェッチアドレスキューのエントリ１、エントリ２、エントリ３、エントリ４の状態を示す。（５）は、本発明の実施形態で設けるネクストラインプリフェッチ制御装置の状態を示す。図３の（ａ）は、まずアドレスＡがキャッシュミスをおこし、Ａ＋λがプリフェッチアドレスキューに登録された状態を示している。なお、ここで、λは、キャッシュメモリに格納されるデータブロックのサイズである。図３の（ｂ）は、アドレスＢがキャッシュミスをおこし、Ｂ＋λが登録された状態を示している。図３の（ｃ）は、アドレスＣがキャッシュミスをおこし、Ｃ＋λが登録された状態を示している。図３の（ｄ）は、アドレスＤがキャッシュミスをおこし、Ｄ＋λが登録された状態を示している。図３の（ｅ）はアドレスＥがキャッシュミスをおこし、Ｅ＋λが登録された状態を示している。この時、エントリ（４）のＡ＋λは、プリフェッチアドレスキューからあふれ、ネクストラインプリフェッチ制御装置（５）にセットされる。図３の（ｆ）は、Ａ＋λがキャッシュミスをおこしたときのキューの状態を示している。Ａ＋λは、図３の（ｅ）の段階でプリフェッチアドレスキューから追い出されているのでプリフェッチアドレスキューにヒットしない。従って、プリフェッチを要求することは出来ない。その代わり、ネクストラインプリフェッチ制御装置に登録されているアドレスにはヒットし、Ａ＋２λになる。【００１１】
図４は、実際にネクストラインプリフェッチを要求する様子を示している。図４の（１）〜（４）は、それぞれプリフェッチアドレスキューのエントリ１、エントリ２、エントリ３、エントリ４の状態を示す。図４の（５）は、ネクストラインプリフェッチ制御装置の状態を示す。図４（ａ）は、アドレスＡからＡ＋（ｍ−１）λ、ＢからＢ＋（ｍ−１）λ、ＣからＣ＋（ｍ−１）λ、ＤからＤ＋（ｍ−１）λ、ＥからＥ＋（ｍ−１）λまで連続したアクセスがありネクストラインプリフェッチ制御装置のアドレスにｍ−１回ヒットした状態を示す。各プリフェッチアドレスキュー（１）〜（４）及びネクストラインプリフェッチ制御装置（５）には、キャッシュミスしたアドレスの次のアドレスが設定されている。図４の（ｂ）は、Ａ＋ｍλでキャッシュミスした状態である。ネクストラインプリフェッチ制御装置にヒットし、Ａ＋（ｍ＋１）λに更新される。ヒット回数が閾値ｍを超えた為、ネクストラインプリフェッチを要求するモードに切り替わる。すると、本来プリフェッチアドレスキューにないアドレスであるＡ＋ｍλがキャッシュミスしたので、次のアドレスであるＡ＋（ｍ＋１）λに対しては、プリフェッチ要求は出されないはずであるが、今の場合では、ネクストラインプリフェッチを要求するモードとなっているので、Ａ＋（ｍ＋１）λに対してプリフェッチを要求し、プリフェッチアドレスキューにはＡ＋（ｍ＋１）λが登録される。図４の（ｃ）は、アドレスＢ＋ｍλがキャッシュミスした状態である。この場合、アドレスＢ＋ｍλは、プリフェッチアドレスキューにも、ネクストラインプリフェッチ制御装置にもヒットしないが、プリフェッチ制御装置がネクストプリフェッチ要求モードとなっているので、Ａ＋ｍλのときと同じように、Ｂ＋（ｍ＋１）λに対しプリフェッチを要求し、プリフェッチアドレスキューにはＢ＋（ｍ＋１）λが登録された状態を示す。図４の（ｄ）は、アドレスＣ＋（ｍ＋１）λがキャッシュミスした状態である。やはり、ネクストプリフェッチ要求モードになっているので、Ｃ＋（ｍ＋１）λに対しプリフェッチを要求し、プリフェッチアドレスキューには、Ｃ＋（ｍ＋１）λが登録される。図４の（ｅ）は、アドレスＤ＋（ｍ＋１）λがキャッシュミスした状態である。ネクストプリフェッチ要求モードであるので、Ｄ＋（ｍ＋１）λに対しプリフェッチを要求し、プリフェッチアドレスキューには、Ｄ＋（ｍ＋１）λが登録される。図４の（ｆ）は、ネクストプリフェッチ要求モードであるので、アドレスＥ＋（ｍ＋１）λがキャッシュミスした状態である。Ｅ＋（ｍ＋１）λに対しプリフェッチを要求し、プリフェッチアドレスキューには、Ｅ＋（ｍ＋１）λが登録される。このように、いったん、プリフェッチ制御装置が、ネクストプリフェッチ要求モードに入ると、それ以降にキャッシュミスするアドレスについては、すべてのアドレスについてプリフェッチ要求をおこなうようにする。【００１２】
以上により、図２に示されるように、アクセスアドレスがプリフェッチアドレスキューにヒットしなくても、ネクストラインプリフェッチモードにおいては、すべてのキャッシュミスしたアクセスアドレスについて、アクセスが連続アドレスアクセスであると仮定して、プリフェッチを実行するようになる。【００１３】
なお、以下の図面を用いた構成と動作の説明において、対応する制御信号やアドレスバスには同じ参照符号を付している。
図５は、本発明の実施形態のプリフェッチ制御装置を含む情報処理装置の全体を示すブロック構成図である。【００１４】
図５を参照すると、プリフェッチ制御装置１１は、一次キャッシュ１２へのリクエストアドレス２０を監視ながら、二次キャッシュ１３にプリフェッチを要求する構成となっている。プロセッサユニット１０から一次キャッシュ１２にアドレスバス２０を使用してデータを要求する時、同じアドレスでプリフェッチ制御装置１１は、プリフェッチアドレスキューを検索する。アドレスバス２０で伝えられたアドレスをX、キューに登録されているアドレスを仮にP、λをブロックサイズとした場合に
P≦X＜P＋λ
が成り立つ時ヒットしたといい、この時アドレスバス２１を使用して二次キャッシュ１３にプリフェッチを要求し、ヒットしない場合はプリフェッチを要求しない。後者の場合、制御信号２２でキャッシュミスが報告されると、プリフェッチ制御装置１１はこのアドレスの登録動作に入る。【００１５】
プロセッサユニット１０は、リクエストアドレス２０を一次キャッシュ１２に送り、データのフェッチやデータのストアを要求する。一次キャッシュ１２は、プロセッサユニット１０からの要求がデータフェッチである場合、リクエストアドレス２０を内部に格納されているデータのアドレスと比較し、自身の中に要求されたデータがあるか否かを判断する。要求されたデータがある場合には、一次キャッシュ１２はそのデータをプロセッサユニット１０に送る。要求されたデータがない場合には、キャッシュミス信号２２をプリフェッチ制御装置１１に送ると共に、二次キャッシュ１３に、データを一次キャッシュ１２に送ってくれるよう要求する。この要求は、リクエストバス２３に要求信号を載せることによって行う。一次キャッシュ１２と二次キャッシュ１３の間のデータのやり取りは、データバス２４−１、２４−２によって行われる。【００１６】
二次キャッシュ１３は、一次キャッシュ１２から要求されたデータが自身の中にあるか否かを確認し、あった場合には、そのデータを一次キャッシュに送る。要求されたデータがなかった場合には、二次キャッシュ１３は、主記憶装置１４にデータを要求し、主記憶装置１４から得たデータを一次キャッシュ１２に転送する。【００１７】
プリフェッチ制御装置１１は、プロセッサユニット１０からのリクエストアドレス２０と内部のプリフェッチアドレスキューのアドレスとを比較し、同じものがあった場合には、そのアドレスの次のアドレスをプリフェッチ要求アドレス２１として、二次キャッシュ１３に送り、二次キャッシュ１３に、当該アドレスのデータを主記憶装置１４から獲得させる。【００１８】
一次キャッシュ１２でキャッシュミスが発生すると、キャッシュミスを示す信号２２がプリフェッチ制御装置１１に送られる。キャッシュミスしたアドレスは、一次キャッシュ１２が直接二次キャッシュ１３にデータ要求するが、キャッシュミスしたアドレスの次のアドレスはプリフェッチ制御装置１１のプリフェッチアドレスキューに格納され、次に、同様のアクセスがあった場合に、プリフェッチ要求が出せるように準備される。【００１９】
本発明の実施形態では、上記したようなプリフェッチ制御装置１１にネクストラインプリフェッチ制御装置を設け、プリフェッチアドレスキューから漏れたアドレスを含む連続したアドレスに所定回のアクセスがあった場合には、プロセッサユニット１０のアクセスが連続したアドレスへのアクセスを多数行う状態にあると判断し、プリフェッチアドレスキューにないアドレスについてキャッシュミスが発生しても、プリフェッチを行うようにする。【００２０】
図６は、図５におけるプリフェッチ制御装置の内部構造を示した図である。
まず、アドレスバス２０により伝えられたアクセスアドレスはいったんレジスタ２５に記録される。このレジスタ２５と、プリフェッチアドレスキュー２６の各エントリアドレスとの比較を行う。ヒットした場合には、その後、そのエントリアドレスがレジスタ２７に読み出される。レジスタ２７の値に加算器２８で、ブロックサイズλが加算され、レジスタ２７のアドレスの次のアドレスが計算される。そのアドレスはアドレスバス２９を介してレジスタ３０に書き込まれ、アドレスバス２１を通じてプリフェチ要求アドレスとなる。この時、セレクタ３１は制御信号３２によってアドレスバス２９を選択するように制御され、アドレスバス４３を介して、プリフェッチアドレスキュー２６に、加算器２８の出力アドレスが登録される。【００２１】
一方プリフェッチアドレスキュー２６のアドレス検索においてヒットしなかった場合、エントリの読み出しは行われないため、何も行われない。但し、このアクセスアドレスがキャッシュミスを引き起こしたことが制御信号２２で報告されると、制御信号３３が、レジスタ２５のアドレスをレジスタ３４に登録するように指示する。レジスタ３４は、アドレスが登録されている場合、待機ビットがセットされ、制御信号３４を使用してプリフェッチキュー２６に新規登録を要求する。アドレスバス２９からの登録が無い場合、プリフェッチアドレスキュー２６は、制御信号３５により登録を許可し、待機ビットのリセットを行う。この時、プリフェッチアドレスキュー２６は制御信号３２によりセレクタ３１に対しアドレスバス３６を選択するように制御して、レジスタ３４の値に加算器３７でブロックサイズλを加算したアドレスを、アドレスバス４３を介してプリフェッチアドレスキュー２６に登録する。【００２２】
プリフェッチアドレスキュー２６にアドレスを登録していき、登録アドレスがいっぱいになると、あふれたアドレスは、アドレスバス３９を介して、ネクストラインプリフェッチ制御装置３８に設定される。制御信号４１は、アドレスのネクストラインプリフェッチ制御装置３８への書き込みを制御する信号である。【００２３】
レジスタ２５のアドレスは、アドレスバス４４を介して、レジスタ３４、プリフェッチアドレスキュー２６に入力されるだけではなく、ネクストラインプリフェッチ制御装置３８にも入力される。このアドレスがネクストラインプリフェッチ制御装置３８のアドレスに一致した場合には、ネクストラインプリフェッチ制御装置３８内部で、該アドレスにブロックサイズλを加算し、加算後のアドレスが再びネクストラインプリフェッチ制御装置３８内部に格納される。ネクストラインプリフェッチ制御装置３８では、アドレスが一致した回数を計数しており、所定回の一致を見ると、プリフェッチアドレスキュー２６にネクストラインプリフェッチモードに入るよう指示する制御信号４０が送られる。ネクストラインプリフェッチモードに入ったプリフェッチアドレスキュー２６は、制御信号３２を使って、セレクタ３１にアドレスバス４２を選択させ、アドレスバス４３を介して、レジスタ３４のアドレスを直接プリフェッチアドレスキュー２６に入力させる。直接プリフェッチアドレスキュー２６に入力されたアドレスは、レジスタ２７を介して、加算器２８に入力され、ブロックサイズλが換算された後、レジスタ３０を介して、プリフェッチ要求アドレスとして、アドレスバス２１に出力される。【００２４】
図７及び図８は、図６におけるプリフェッチアドレスキューの構成を示した図である。
図７のプリフェッチアドレスキューは、図８のような構成のエントリを複数個もつ。
図８において、アドレスバス５０を介して、登録アドレスがレジスタ５６に入力される。レジスタ５６には、アドレスの有効性を示す有効ビットが制御信号５２によって設定される。待機ビットは、エントリがプリフェッチ待機状態にあることを示し、制御信号５３が待機ビットの状態を示す。リクエストアドレスがアドレスバス４４を介して比較器５４に入力され、レジスタ５６のアドレスと比較される。比較の結果一致すると、制御信号５５が発行され、待機ビットをセットすると共に、比較結果が一致した旨の通知をプリフェッチアドレスキュー制御部６０に対して行う。【００２５】
図７のプリフェッチアドレスキューの動作は以下の通りとなる。アクセスアドレスはアドレスバス４４を通じてレジスタ５６のアドレスと比較器５４で比較される。有効ビットがセットされているエントリにヒットした場合には、エントリ５６の待機ビットをセットする。この待機ビットは制御信号５３（５３−１〜５３−４）を通じて各エントリから集められ、プリフェッチアドレスキュー制御部６０で読み出され、読み出すエントリの決定に使用される。エントリが決まると、制御信号６３を使ってセレクタ６１を制御して、そのエントリを読み出すと同時に、制御信号５２（５２−１〜５２−４）によって有効ビットをリセットする。また、プリフェッチアドレスキュー制御部６０は、制御信号２２を通じてキャッシュミスが報告された時、各エントリのアドレス比較の結果を制御信号５５（５５−１〜５５−４）から集め、どのエントリもヒットしない時、制御信号３３を使って、図６の通りレジスタ３４にレジスタ２５のアドレスを登録するように指示する。レジスタ３４から制御信号３４を使って登録を要求された場合、または、プリフェッチアドレスキューからの読み出しがレジスタ２７に格納された直後には、プリフェッチアドレスキュー制御部６０は、制御信号６４−１を使ってセレクタ６２−１に対しアドレスバス４３を選択するように制御して、アドレスバス４３の値をエントリに登録する。この時、エントリ１の有効ビットがセットされている場合は制御信号６４−２を使ってセレクタ６２−２を制御してエントリ２にその値をセットする。同様の操作をエントリ３、４に対しても行う。エントリ４から漏れたアドレスは、アドレスバス３９に出力される。それ以外の場合、セレクタ６２−１〜６２−４は、各エントリを書き戻すように制御される。すなわち、１マシンサイクルごとに、エントリ１〜４からは、アドレスが出力されるが、セレクタ６２−１〜６２−４がエントリ１〜４の出力を再びエントリ１〜４にそれぞれ入力し、複数マシンサイクルにわたって、各エントリが同じ値を保持できるようにする。【００２６】
図７のようにエントリ数が４の時、連続したアクセスの系列が５つ以上ある場合、プリフェッチアドレスキューにヒットする前にエントリがプリフェッチアドレスキューからあふれ、プリフェッチ制御装置が有効に働かない。そこで、図６のようにネクストラインプリフェッチ制御装置３８を付加し、特定の条件のもとで、キャッシュミスしたアドレスにブロックサイズλを加算したアドレスをプリフェッチするように制御する。【００２７】
図９は、ネクストラインプリフェッチ制御装置の構成を示す図である。
まず、プリフェッチアドレスキューがあふれたことをプリフェッチアドレスキュー制御部６０が検出すると制御信号４１を使って、ネクストラインプリフェッチ制御装置へのあふれたアドレスの登録を指示する。指示を受けると、制御回路７０は、有効ビット７１がセットされていない時、制御信号７２を使って、セレクタ７３にアドレスバス３９を選択するように制御し、制御信号７４を使って、アドレスをアドレスレジスタ７５にセットし有効ビット７１をセットする。【００２８】
有効ビットの情報は制御信号７６により制御回路７０に伝えられ、有効ビットがセットされた状態の時には、制御信号４１により新たなアドレスを登録するように要求があっても登録しない。また、有効ビットがセットされている間、制御信号７７により毎サイクル、カウンタ１をカウントアップするように指示する。アドレスが登録された状態でキャッシュアクセスがあった時、アドレス７８とアクセスアドレス４４を比較する。ヒットした場合、制御信号７９により、そのことが制御回路７０に伝えられる。その時、制御回路７０は、制御信号７２を制御し、アドレス７８に加算器８０で、ブロックサイズλを加算したアドレス８１をセレクトするように制御し、制御信号７４でレジスタ７５の更新を指示する。【００２９】
同時に、制御信号８２により、カウンタ1を０にリセットするように指示し、また制御信号８３により、カウンタ２をカウントアップするよう指示する。このように動作することで、カウンタ１は、ヒットしてから次にヒットするまでのサイクル数をカウントし、カウンタ２は、ヒットした回数をカウントする。ヒットを繰り返すうちにカウンタ２がある閾値ｍに達した時、制御信号８４でそのことを制御回路７０に伝える。カウンタ２は、そのカウント値がｍになると、それ以上カウントアップされずにリセットされるまでその値を保持するように作られている。カウンタ２が閾値ｍである間、制御回路７０は、制御信号４０を使って、プリフェッチアドレスキュー制御部６０に、ネクストラインプリフェッチを指示する。【００３０】
ネクストラインプリフェッチ有効信号である制御信号４０が有効な間は、プリフェッチアドレスキュー２６は、以下のように制御される。まず、キャッシュミスしたアドレスがプリフェッチアドレスキュー２６にヒットしなかった場合は、図６のキャッシュミスアドレスレジスタ３４からプリフェッチアドレスキュー２６にアドレスが登録されるが、その時、制御信号３２を使って、セレクタ３１を制御し、アドレス４２を選択する。こうすることで、プリフェッチアドレスキュー２６には、キャッシュミスアドレスがそのまま登録される。また、登録される時には、図８のレジスタ５６の待機ビットをセットする。このエントリは待機ビットがセットされているので読み出されて、図６のレジスタ２７にセットされる。そして、図６の加算器２８でブロックサイズλが加算され、図６のレジスタ３０にセットされる。このアドレスを用いて、アドレスバス２１を通じて、二次キャッシュ１３にプリフェッチを要求する。【００３１】
以上のように、カウンタ２が閾値ｍの間はキャッシュミスしたすべてのアドレスに対して、ブロックサイズλを加算したアドレスをプリフェッチするように制御される。また、ネクストラインプリフェッチ制御装置３８のアドレス７５にヒットしてから、次にヒットするまでのサイクル数をカウントしているカウンタ１が閾値ｎに達した時は、制御信号８５で、そのことが制御回路７０に伝えられる。その時、制御回路７０は、制御信号８２を使ってカウンタ１を、制御信号８６を使ってカウンタ２を０にリセットする。また、同時に、制御信号８７を使って有効ビット７１をリセットする。このようにすることで、無制限にネクストラインプリフェッチを要求することを防いでいる。【００３２】
図１０〜図１４は、本発明の実施形態のプリフェッチ制御装置の動作を説明するタイムチャートである。
図１０及び図１１に、アドレスＡ、Ｂ、Ｃ、Ｄ、Ｅから始まる連続したアクセスが順番に行われた場合のタイムチャートを示す。【００３３】
まず、図１０において、サイクル１でアドレスＡのアクセスがあり、キャッシュミス信号２２が発生している。その結果、キャッシュミスアドレスレジスタ３４にアドレスＡが登録され、サイクル３で、プリフェッチアドレスキューのエントリ０にアドレスＡ＋λが登録される。サイクル５でアドレスＢに、サイクル９でアドレスＣにサイクル１３でアドレスＤにそれぞれアクセスがあり、それぞれがキャッシュミスしており、サイクル１５の段階で、プリフェッチアドレスキューはエントリ０から順番にＤ＋λ、Ｃ＋λ、Ｂ＋λ、Ａ＋λが格納された状態になっている。【００３４】
この状態で、サイクル１７にアドレスＥによるアクセスがあり、キャッシュミスが起こった場合、サイクル１９で、プリフェッチアドレスキューがあふれ、アドレスＡ＋λがネクストラインプリフェッチ制御装置のアドレスレジスタ７５にセットされる。このサイクルからアドレスレジスタ有効ビット７１が有効になり、カウンタ1がカウントを始める。【００３５】
サイクル２１では、アドレスＡ＋λにアクセスがありアドレスレジスタ７５にヒットしている。その結果、図１１のサイクル２２で、アドレスレジスタ７５がＡ＋２λに更新され、カウンタ１がリセットされカウンタ2が１にカウントアップされる。【００３６】
以下同様にアクセスが行われ、ネクストラインプリフェッチ制御装置のアドレスレジスタ７５の保持するアドレスに、アクセスアドレスがｍ−１回ヒットした状態からのタイムチャートを図１２及び図１３に示す。【００３７】
図１２のサイクル５でＡ＋ｍλのアクセスがあり、アドレスレジスタ７５にヒットする。そして、サイクル６で、アドレスレジスタ７５がＡ＋（ｍ＋１）λに更新され、カウンタ２がｍにカウントアップされる。カウンタ２が閾値ｍになったことで、ネクストラインプリフェッチ有効信号４０が有効になる。その結果、サイクル７で、エントリ０にセットされるアドレスはアクセスアドレスＡ＋ｍλになる。また、同時に、エントリ０の待機ビットもセットされる。サイクル８で、エントリ０のアドレスは読み出されて、サイクル９でＡ＋（ｍ＋１）λがプリフェッチアドレスレジスタ３０にセットされる。同時にエントリ０へ同じアドレスが書き戻される。プリフェッチアドレスレジスタ３０にセットされたアドレスに対し、プリフェッチが行われる。このプリフェッチがネクストラインプリフェッチである。これ以後は、同様にキャッシュミスしたアドレスに対しネクストラインプリフェッチが要求される。【００３８】
図１３のサイクル２５では、もう一度アドレスレジスタ７５にヒットしているがアドレスレジスタ７５の更新とカウンタ１のリセットが行われるのみで、カウンタ２はｍのままでカウントアップもリセットもされない。アドレスレジスタ７５にヒットしたアドレスＡ＋（ｍ＋１）λについては、他のアドレスと同様にネクストラインプリフェッチが行われる。【００３９】
また、以下同様にアクセスが続いた後、一連の連続したアクセスは終わり、新たにアドレスＰ、Ｑ、Ｒ、Ｓ、Ｔから連続したアクセスが始まったところからのタイムチャートを図１４に示す。【００４０】
アドレスレジスタ７５とは違うアドレスによるアクセスである為ヒットせず、カウンタ１がカウントアップを続け、サイクル４で閾値ｎに達する。その為、サイクル５で、カウンタ１、カウンタ2、アドレスレジスタの有効ビット７１がリセットされ、ネクストラインプリフェッチ有効信号４０が無効になる。この状態になると、新しいアドレスをプリフェッチアドレスキューから登録できるようになり、ネクストラインプリフェッチも行われなくなる。サイクル７で、プリフェッチアドレスキューからアドレスがあふれＱ＋λがアドレスレジスタ７５に登録される。これ以後の動作は以上で説明してきた通りである。
【図１】
2007099582.tif 000003
【図２】
2007099582.tif 000004
【図３】
2007099582.tif 000005
【図４】
2007099582.tif 000006
【図５】
2007099582.tif 000007
【図６】
2007099582.tif 000008
【図７】
2007099582.tif 000009
【図８】
2007099582.tif 000010
【図９】
2007099582.tif 000011
【図１０】
2007099582.tif 000012
【図１１】
2007099582.tif 000013
【図１２】
2007099582.tif 000014
【図１３】
2007099582.tif 000015
【図１４】
2007099582.tif 000016
【手続補正書】
【提出日】平成21年5月18日(2009.5.18)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
主記憶装置、キャッシュメモリ及びプロセッサを備えた情報処理装置における、主記憶装置からキャッシュメモリへのプリフェッチを制御するプリフェッチ制御装置において、
該キャッシュメモリへのプリフェッチを要求するために、該プロセッサからのアクセスアドレスとの比較用の複数のアドレスを格納するプリフェッチアドレスキュー手段と、
該プリフェッチアドレスキュー手段からあふれたアドレスを格納し、該プロセッサから、格納されたアドレスと一致するアドレスにアクセスがあった場合に、該アドレスを、これに連続する次のアドレスに書き換え、該プロセッサからの、格納されたアドレスと一致するアドレスへのアクセスが連続して所定回数あった場合に、以後のキャッシュミスしたアクセスアドレスに連続する次のアドレスのプリフェッチを行うネクストラインプリフェッチを実行させるネクストラインプリフェッチ制御手段と、
を備えることを特徴とするプリフェッチ制御装置。
【請求項２】
前記連続した所定回数のアクセスの計数においては、前記ネクストラインプリフェッチ制御手段に格納されたアドレスへの前記プロセッサからのアクセスがあった時からカウント値をカウントし、前記ネクストらインプリフェッチ制御手段に格納されたアドレスへの前記プロセッサからの次のアクセスが、該カウント値が所定値に達しない間にあった場合に、アクセスが連続しているとすることを特徴とする請求項１に記載のプリフェッチ制御装置。
【請求項３】
前記ネクストラインプリフェッチ制御手段に格納されたアドレスへの前記プロセッサからの次のアクセスがないまま、該カウント値が所定値になった場合には、前記ネクストラインプリフェッチ動作を解除することを特徴とする請求項２に記載のプリフェッチ制御装置。
【請求項４】
前記ネクストラインプリフェッチにおいては、キャッシュミスしたアクセスアドレスを前記プリフェッチアドレスキュー手段に格納させ、前記プロセッサからのアクセスアドレスとの比較を行わずに、前記キャッシュメモリへのプリフェッチ要求を行わせることを特徴とする請求項１に記載のプリフェッチ制御装置。
【請求項５】
前記次のアドレスは、元のアドレスに、キャッシュメモリのデータの格納単位であるデータブロックのサイズを加算した値であることを特徴とする請求項１に記載のプリフェッチ制御装置。
【請求項６】
前記キャッシュメモリは、一次キャッシュと二次キャッシュからなり、前記プリフェッチは、一次キャッシュにおいて発生したキャッシュミスに対して、二次キャッシュに前記主記憶からデータをフェッチさせることを特徴とする請求項１に記載のプリフェッチ制御装置。
【請求項７】
主記憶装置、キャッシュメモリ及びプロセッサを備えた情報処理装置における、主記憶装置からキャッシュメモリへのプリフェッチを要求するために、該プロセッサからのアクセスアドレスとの比較用の複数のアドレスを格納するプリフェッチアドレスキュー手段を備えたプリフェッチ制御装置の制御方法において、
該プリフェッチアドレスキュー手段からあふれたアドレスをネクストラインプリフェッチ制御手段に格納し、
該プロセッサから、前記ネクストラインプリフェッチ制御手段に格納されたアドレスと一致するアドレスにアクセスがあった場合に、該アドレスを、これに連続する次のアドレスに書き換え、
該プロセッサからの、前記ネクストラインプリフェッチ制御手段に該格納されたアドレスと一致するアドレスへのアクセスが連続して所定回数あった場合に、以後のキャッスミスしたアクセスアドレスに連続する次のアドレスのプリフェッチを行うネクストラインプリフェッチを実行させる
ことを特徴とする制御方法。
【国際調査報告】
2007099582.tif 000017
2007099582.tif 000018
2007099582.tif 000019
2007099582.tif 000020