(57)【要約】【課題】システムの運用中にソフトウェア/ハードウェア状態をモニタし、キャッシュ制御を動的に最適化する。【解決手段】キャッシュ制御装置において、プロセッサによる要求プログラムが、キャッシュメモリにプリフェッチされているかどうかを判定し、ヒット率を取得するヒット率取得手段と、該ヒット率が所定の閾値を下回った際に前記プロセッサが要求したプログラムを特定し、該プログラムをヒット率が前記所定の閾値を下回る次の推定周期より前に、前記キャッシュメモリにプリフェッチするプリフェッチ制御手段とを有する。【選択図】  図４
2010055458.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュ制御装置において、
プロセッサによる要求プログラムが、キャッシュメモリにプリフェッチされているかどうかを判定し、ヒット率を取得するヒット率取得手段と、
該ヒット率が所定の閾値を下回った際に前記プロセッサが要求したプログラムを特定し、該プログラムをヒット率が前記所定の閾値を下回る次の推定周期より前に、前記キャッシュメモリにプリフェッチするプリフェッチ制御手段とを、
有することを特徴とするキャッシュ制御装置。     
【請求項２】
請求項１において、
前記キャッシュメモリとプリフェッチ制御手段は、バスを通して接続され、
前記プリフェッチ制御手段は、更に前記バスの動作率の周期を求め、前記推定したプログラムのプリフェッチを前記バスの動作率の周期からバス動作率の下がったタイミングで実行するように制御する、
ことを特徴とするキャッシュ制御装置。
【請求項３】
請求項１において、
前記プリフェッチ制御手段は、前記推定したプログラムのプリフェッチのアドレスを前記キャッシュメモリに先にキャッシュされているプログラムであって、前記ヒット率の周期が大きいプログラムの格納アドレス位置とする、
ことを特徴とするキャッシュ制御装置。
【請求項４】
ヒット率取得手段により、プロセッサによる要求プログラムが、キャッシュメモリにプリフェッチされているかどうかを判定し、ヒット率を取得する工程と、
プリフェッチ制御手段により前記ヒット率が所定の閾値を下回った際に前記プロセッサが要求したプログラムを特定し、該プログラムをヒット率が前記所定の閾値を下回る次の推定周期より前に、前記キャッシュメモリにプリフェッチする工程を有する、
ことを特徴とするキャッシュ制御方法。
【請求項５】
請求項４において、
前記キャッシュメモリとプリフェッチ制御手段は、バスを通して接続され、
前記プリフェッチ制御手段により、更に前記バスの動作率の周期を求める工程と、
前記推定したプログラムのプリフェッチを前記バスの動作率の周期からバス動作率の下がったタイミングで実行する工程を有する、
ことを特徴とするキャッシュ制御方法。
【請求項６】
請求項４において、
前記プリフェッチする工程において、前記推定したプログラムのプリフェッチのアドレスを前記キャッシュメモリに先にキャッシュされているプログラムであって、前記ヒット率の周期が大きいプログラムの格納アドレス位置とする、
ことを特徴とするキャッシュ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ制御方法及びキャッシュ制御装置に関する。
【背景技術】
【０００２】
無線通信処理機能などが組み込まれたシステムは、ソフトウェア/ハードウェアともに複雑であり高い性能が要求される。
【０００３】
かかるシステムの多くは、プロセッサが、プログラム処理のためにメモリにアクセスしてデータを読出し演算処理し、必要により、メモリに書き戻すという処理を繰り返す。
【０００４】
したがって、メモリへのアクセス時間を短縮することは、システムの処理スピードを高めることにおいて重要である。かかるメモリへのアクセス時間の短縮のために、キャッシュ技術が採用されている。
【０００５】
キャッシュ技術では、例えば、低速な大容量のメモリとプロセッサとの間に、高速な小容量のキャッシュメモリを備え、次に予想されるプロセッサの処理に必要なデータを予め大容量のメモリから読み出し、キャッシュメモリに書き込んでおく（プリフェッチする）。
【０００６】
図１に、この手順の１例を示す。例えば、現在実行中のプログラムデータのメモリアドレス０１００に対し、次に実行されると予想されるプログラムデータのアドレス位置０１０１，０１０２が予想できる。したがって、このアドレスに対応するデータをメモリから先読みし、キャッシュメモリに格納しておく（プリフェッチする）し、プロセッサは、キャシュメモリにアクセスしてプリフェッチされたデータを読み出すことで、高速動作を可能にする。
【０００７】
また、システムとして上記の高速化性能と同時に厳しい電力制限も存在する。これらを両立するために、予めソフトウェア動作に必要最低限なキャッシュ容量/方式が見積もられたキャッシュメモリをハードウェアに実装することが行われる。
【０００８】
あるいは、試作チップの動作をトレースするなどにより分析し、キャッシュメモリを含むハードウェア仕様を決定することが行われる。
【０００９】
従来技術として、特許文献１に記載の発明がある。この従来の発明は、データ中に必要な先読みアドレスを計算するためのコードを埋め込んでおくものである。これにより、キャッシュ動作を可能にするとともに、キャッシュヒット率（要求アドレスとプリフェッチされたデータのアドレスとの一致割合）を高めて、実行速度の高速化を図る発明である。
【００１０】
また、特許文献２に記載の発明がある。この発明は、データキャッシュミスをしている命令(アドレス)を特定するものであり、実行履歴を取得し、当該命令が発行される前に必要なデータアドレスを算出してデータプリフェッチを行う。すなわち、命令のアドレスと、データのアドレスを関連付けてデータのプリフェッチを行うものである。
【特許文献１】特開平９−２５９,０４０号公報
【特許文献２】特開２００３−２２３,３５９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかし、近年のシステムではソフトウェア動作が複雑となり、あらかじめ最適なキャッシュ方式を決定することが困難になっている。また、最適な方式はシステムの運用状態などによっても変化するものである。
【００１２】
したがって、本発明の目的は、運用状態に応じたキャッシュ制御を行うことを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、マイクロプロセサならびにバス（Bus）動作の周期性に注目し、キャッシュの制御を最適化する。特に、
キャッシュヒット率
プログラム呼び出し率
バス（bus）動作率
の履歴を取得し、それぞれの周期性を抽出する。抽出された周期性の将来の動作を推定し、命令のプリフェッチを制御する。
【００１４】
一態様として、キャッシュ制御装置において、プロセッサによる要求プログラムが、キャッシュメモリにプリフェッチされているかどうかを判定し、ヒット率を取得するヒット率取得手段と、前記ヒット率が所定の閾値を下回った際に前記プロセッサが要求したプログラムを特定し、該プログラムをヒット率が前記所定の閾値を下回る次の推定周期より前に、前記キャッシュメモリにプリフェッチするプリフェッチ制御手段とを、有することを特徴とする。
【発明を実施するための最良の形態】
【００１５】
以下に図面に従い実施例を説明する。
【００１６】
図２は、第１の実施例に従うキャッシュ制御方法を適用するキャッシュ制御部を含むシステムのブロック図である。
【００１７】
外部メモリ等の大容量主メモリ２が、バス５を通して、キャッシュ制御部４に接続される。キャッシュ制御部４には更に、プロセッサ１、キャッシュメモリ３が接続される。
【００１８】
したがって、プロセッサ１は、キャッシュ制御部４を通してキャッシュメモリ３にアクセスする。
【００１９】
キャッシュ制御部４は、プロセッサ１の動作をモニタし、プロセッサ１からのアクセス要求アドレスがキャッシュメモリ３にプリフェッチされたプログラム命令のデータの格納アドレスに含まれるかどうかの判定結果（含まれる場合は、キャッシュヒット、含まれない場合は、キャッシュアンヒット）をキャッシュヒット率履歴取得部６Ａに通知する。
【００２０】
キャッシュヒット率履歴取得部６Ａは、キャッシュ制御部４から通知される判定結果に基づいて（キャッシュヒット率（アクセス要求に対して、キャッシュヒット回がどの程度の率で生じたか））を取得する。
【００２１】
キャッシュヒット率履歴取得部６Ａで取得されたキャッシュヒット率は、キャッシュヒット率履歴データベース７Ａにいったん格納してもよいし、キャッシュのヒット率の振る舞い（例えばキャッシュのヒット率の時間的な変化）を解析部８Ａに与えてもよい。
【００２２】
ついで、解析部８Ａは、キャッシュヒット率履歴データベース７Ａ又は、リアルタイムに入力されるキャッシュヒット率情報に基づいて、キャッシュヒット率の振る舞いを解析する。例えば、キャッシュヒット率の時間的な変化を解析する。
【００２３】
解析の例について、図３により説明する。図３は横軸に時間、縦軸にキャッシュヒット率を採っている。図３において、キャッシュヒット率が所定の閾値Ｔ以下となるタイミングが周期性を持って現れていることが理解できる。
【００２４】
そして、かかる周期性を抽出する方法として、例えば、フーリエ変換がある。すなわち、図３に示すようなヒット率の履歴波形からフーリエ変換により周波数成分を抽出する。これによりキャッシュヒット率が所定の閾値を割り込む周期を算出することが可能である。
【００２５】
その他の方法として試行錯誤の繰り返しにより周期性を見出すヒューリスティックな手法なども考えられ、これを解析部８Ａとして、ハードウェアまたはソフトウェアで実装することにより、周期性の抽出を行なうことが可能である。
【００２６】
さらに、図２において、キャッシュ制御部４は、プロセッサ１の動作をモニタし、プロセッサ１からのアクセス要求アドレス対象のプログラムを発行プログラム履歴取得部６Ｂに通知する。
【００２７】
履歴取得部６Ｂは、時間対応にプロセッサ１から通知されるプログラムを把握してプログラム履歴データベース７Ｂに格納する。
【００２８】
図４は、プログラム履歴データベース７Ｂに格納されるプログラム履歴の一例を示す図である。
【００２９】
図４において、上方部図４（Ａ）に図３に示したキャッシュヒット率の時間的な振る舞いについての周期性を表す図を示す。下方部図４（Ｂ）に時間対応に、プロセッサ１から呼び出し要求されるプログラムを示している。
【００３０】
図４に示す例では、プログラムＡ、Ｂ，Ｃの３つのプログラムが時間対応に発生している。
【００３１】
発行プログラム推定部８Ｂは、解析部８Ａからキャッシュヒット率の時間的な振る舞いについての周期性を受け、キャッシュヒット率が閾値以下となる際に要求されるプログラムを特定する。これによりプリフェッチすべきプログラムを推定することができる。
【００３２】
すなわち、図４に示す例では、キャッシュヒット率の時間的な周期性に対応し、現状のプリフェッチ動作制御では、所定の周期でキャッシュヒット率が低下してしまうことがわかる。そして、キャッシュヒット率がＴ以下となる際に、実際にプロセッサが必要とする（要求する）プログラムは、プログラムＣであることが、推定部８Ｂで把握できる。
【００３３】
図２に戻り、更にプリフェッチアドレス決定部９は、解析部８Ａ及び発行プログラム推定部８Ｂからそれぞれ、図３、図４（Ａ）に示したキャッシュヒット率が閾値以下となる周期と、図４（Ｂ）に示す、キャッシュヒット率が閾値以下となる場合に要求されるプログラムＣが通知される。
【００３４】
プリフェッチアドレス決定部９は、現時点のキャッシュヒット率から、まもなく周期性を持って出現するキャッシュヒット率の低下を予想し、その際に呼び出されるのは図４（Ｂ）からプログラムＣであることが判定できる。
【００３５】
したがって、プリフェッチアドレス決定部９は、このように判定されるプログラムＣのプログラム命令をキャッシュ制御部４に通知する。
【００３６】
キャッシュ制御部４は、プリフェッチアドレス決定部９からの通知に従い、メモリ２におけるプログラムＣに対応するアドレスにアクセスする。これにより、次に実行されると予想されるプログラムＣの命令をメモリ２から読み出し、キャッシュメモリ３に書き込み、プログラムＣについてプリフェッチを実行することができる。その際、Ｃに続いて実行されるであろうプログラムを更にプリフェッチしておくこともできる。
【００３７】
図５は、第２の実施例に従うキャッシュ制御方法を適用するキャッシュ制御装置のブロック図である。
【００３８】
上記のとおり命令プリフェッチでは、図２に示したようにバス５を通してメモリ２から命令を読み込む。この時、キャッシュ制御部４自身がデータにアクセス中である場合、あるいは他のマスタがバス使用中である場合は、競合が発生し性能を低下させてしまう。
【００３９】
図５に示す第２の実施例は、かかる不都合を回避するものである。すなわち、図５において、図２の実施例におけると同様に、キャッシュヒット率の時間的な振る舞いについての周期性の取得に関する構成（キャッシュヒット率履歴取得部６Ａ，キャッシュヒット率履歴データベース７Ａ，解析部８Ａ）及び、発行プログラムの周期性の取得に関する構成（発行プログラム履歴取得部６Ｂ，プログラム履歴データベース７Ｂ、発行プログラム推定部８Ｂ）を有する。
【００４０】
さらに、図５に示す構成では、上記キャッシュヒット率の時間的な振る舞いについての周期性の取得に関する構成及び、発行プログラムと周期との関係に関する構成に加え、バス（Bus）動作率の時間的な振る舞いについての周期性の取得に関する構成を有する。
【００４１】
バス（Bus）動作率の時間的な変化についての周期性の取得に関する構成として、バス動作率履歴取得部６Ｃ，バス動作率(プログラム読出し)履歴データベース７Ｃ及び、バス動作率（バス動作周期性）推定部８Ｃを有する。
【００４２】
そして、これら三つの情報即ち、キャッシュヒット率の周期性、発行プログラム(プログラム呼出し)の周期性及び、バス動作率の周期性からプリフェッチ実行のタイミングを制御する。
【００４３】
プリフェッチする関数(プログラム)は、図２で説明した第１の実施例と同様の方法即ち、キャッシュヒット率の時間的な振る舞いについての周期性（８Ａ）及び、周期に対応する発行プログラム(プログラム呼出し)（８Ｂ）に基づき決定する。
【００４４】
図５においては、更にそのプリフェッチの実施タイミングをバス動作率の履歴から決定する。
【００４５】
つまり、バス動作率推定部８Ｃにより、図６に示すようにバス動作率の履歴から周期性を抽出する。そして、バスの動作率が下がる(バスの競合が少ない)状態を待って、プリフェッチを実行する。
【００４６】
これにより、バスの競合を起こさずに、命令プリフェッチを実施することが可能である。
【００４７】
ここで、キャッシュメモリ３の容量は非常に限られており、プリフェッチを行って新たなプログラムをキャッシュメモリ３上に読み込む際には、キャッシュメモリ３から削除するプログラムが存在してもよい。
【００４８】
その際に、現在、あるいは近い将来に実行される有効な関数(プログラム)を削除してしまっては、結局キャッシュヒット率を低下させることになりかねない。
【００４９】
そこで、まずキャッシュヒット率と発行プログラムの履歴から、削除する対象の関数(プログラム)を決定する。
【００５０】
例えば、図４と同様の図７の周期性グラフにおいて、まもなくプログラムＣをプリフェッチすべきということが分かっている(図７（Ａ）)。このとき追い出すプログラムは、例えば周期が長く暫く呼び出されないことが分かっているプログラムＤが一つの候補である（図７（Ｂ））。
【００５１】
または、プログラムＡのように十分にキャッシュヒット率が高い箇所との関連が強いプログラムも候補として考えられる。すなわち、プログラムＡは、その周期性からヒット率の低下するタイミングでは実行使用されない可能性が高いからである。
【００５２】
ここで、通常、プログラム(関数)がキャッシュされるキャッシュメモリ３のアドレス(エントリ位置)は、プログラム自身の主メモリ２の下位アドレスにより一意に決定される。図８は、キャッシュメモリ３のアドレスを示す図である。図８に示す例では、主メモリ２に記憶されているプログラムのアドレスの下位２ビットをキャッシュメモリ３のアドレス位置に対応させている。
【００５３】
したがって、上記したようにキャッシュメモリ３から追い出す関数(プログラム)に対応する任意のエントリ位置に新たにプログラムをキャッシュしたい場合は、アドレスを変換(リマップ)する必要がある。上記により削除する関数(プログラム)が決定後、図９に示すように新しい関数(プリフェッチする関数)のアドレスを、その関数のアドレスにリマップする。
【００５４】
図９において、メインメモリ２上のアドレス０２に記憶されるプログラムＣをキャッシュする場合、図８で説明したように、通常は、キャッシュメモリ３の対応するエントリ位置０１である。しかし、図７で説明したように、読み出し頻度の少ないプログラムＤを追い出すことが好ましい。かかる場合、リマップ即ち、プログラムＤのキャッシュされているエントリ位置１０にアドレス変換を行って、プログラムＤをプログラムＣで上書きして、プログラムＣのキャッシュが行われる。
【００５５】
図１０は、かかるリマップのためのキャッシュ制御装置の構成例である。図２の第１の実施例構成を前提にして示している。すなわち、リマップテーブル作成部１０Ａ及びリマップテーブル１０Ｂを備えている。
【００５６】
図１０において、リマップテーブル作成部１０Ａは、解析部８Ａからキャッシュヒット率の周期性情報を、発行プログラム推定部８Ｂから前記キャッシュヒット率の周期性に対応して読出されるプログラム情報を得る。
【００５７】
さらに、キャッシュヒット率の周期性情報から周期性の低いプログラムを特定する。当該特定されるプログラムの格納されているキャッシュ位置に、前記読出されるプログラムのメインメモリ２のアドレスに対応するキャッシュメモリ３のエントリ位置を変換して、メインメモリ２のアドレスとリマップされたキャッシュのエントリ位置とのリマップテーブル１０Ａを作成する。
【００５８】
このように作成されたリマップテーブル１０Ａをリマップテーブルデータベース１１０Ｂに保持する。
【００５９】
キャッシュ制御部４は、リマップテーブルデータベース１１０Ｂを参照して、メインメモリ２から読み出すプログラムをキャッシュメモリ３のリマップされたエントリ位置にキャッシュする。
【００６０】
上記のように、システムの運用中にキャッシュ制御部４において、ソフトウエアまたはハードウエア状態をモニタすることにより、キャッシュ方式を動的に最適化することが可能である。
【図面の簡単な説明】
【００６１】
【図１】プログラムが順番に実行されることを説明する図である。
【図２】、第１の実施例に従うキャッシュ制御方法を適用するキャッシュ制御装置のブロック図である。
【図３】キャッシュヒット率周期性を説明する図である。
【図４】プログラム履歴データベース７Ｂに格納されるプログラム履歴の一例を示す図である。
【図５】第２の実施例に従うキャッシュ制御方法を適用するキャッシュ制御装置のブロック図である。
【図６】バス動作率の履歴から周期性を抽出することを説明する図である。
【図７】キャッシュの際に、キャッシュから追い出すプログラムの候補について説明する図である。
【図８】キャッシュメモリのアドレスを説明する図である。
【図９】新しい関数(プリフェッチする関数)のアドレスのリマップを説明する図である。
【図１０】リマップのためのキャッシュ制御装置の構成例である。
【符号の説明】
【００６２】
１  プロセッサ
２  メインメモリ
３  キャッシュメモリ
４  キャッシュ制御部
５  バス(Bus)
６Ａ  キャッシュヒット率履歴取得部
７Ａ  キャッシュヒット率データベース
８Ａ  解析部
６Ｂ  プログラム履歴取得部
７Ｂ  プログラム履歴データベース
８Ｂ  プログラム履歴推定部
６Ｃ  バス動作率履歴取得部
７Ｃ  バス動作率履歴データベース
８Ｃ  バス動作率推定部
９  プリフェッチアドレス決定部
１０Ａ  リマップテーブル作成部
１０Ｂ  リマップテーブル
【図１】
2010055458.tif 000003
【図２】
2010055458.tif 000004
【図３】
2010055458.tif 000005
【図４】
2010055458.tif 000006
【図５】
2010055458.tif 000007
【図６】
2010055458.tif 000008
【図７】
2010055458.tif 000009
【図８】
2010055458.tif 000010
【図９】
2010055458.tif 000011
【図１０】
2010055458.tif 000012