(57)【要約】      （修正有）【課題】メモリアクセス効率を向上する演算処理装置及び処理方法を提供する。【解決手段】キャッシュ制御部３２は、キャッシュヒット判定部と、演算処理部が実行したメモリアクセス命令が読み出し命令である場合、読み出し命令の計数値を増分させるリード計数部と、演算処理部が実行したメモリアクセス命令が書き込み命令である場合、書き込み命令の計数値を増分させるライト計数部とを有する。また、リード計数部が計数した読み出し命令の計数値と、ライト計数部が計数した書き込み命令の計数値とに基づき、キャッシュミス判定部が判定したキャッシュミスに応答して主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成する置換基準生成部と、目標の読み出し領域の容量と目標の書き込み領域の容量とに基づいて、キャッシュメモリ３５の領域の置換を制御する置換制御部とを有する。【選択図】図２
2016170682.tif 000002
【特許請求の範囲】
【請求項１】
主記憶装置にアクセス可能な演算処理装置において、
メモリアクセス命令を実行する演算処理部と、
前記主記憶装置が記憶するデータの一部を保持するキャッシュメモリと、
前記メモリアクセス命令に応答して前記キャッシュメモリを制御するキャッシュ制御部とを有し、
前記キャッシュ制御部は、
前記演算処理部が実行したメモリアクセス命令に基づき、前記キャッシュメモリ部におけるキャッシュヒット又はキャッシュミスを判定するキャッシュヒット判定部と、
前記演算処理部が実行したメモリアクセス命令が読み出し命令である場合、読み出し命令の計数値を増分させるリード計数部と、
前記演算処理部が実行したメモリアクセス命令が書き込み命令である場合、書き込み命令の計数値を増分させるライト計数部と、
前記リード計数部が計数した読み出し命令の計数値と、前記ライト計数部が計数した書き込み命令の計数値とに基づき、前記キャッシュミス判定部が判定したキャッシュミスに応答して前記主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成する置換基準生成部と、
前記目標の読み出し領域の容量と前記目標の書き込み領域の容量とに基づいて、前記キャッシュメモリの領域の置換を制御する置換制御部とを有する、演算処理装置。
【請求項２】
前記置換基準生成部は、
前記リード計数部が計数した読み出し命令の計数値に基づき、前記メモリアクセス命令のうち読み出し命令の発生確率である読み出し確率を算出するとともに、前記ライト計数部が計数した書き込み命令の計数値に基づき、前記メモリアクセス命令のうち書き込み命令の発生確率である書き込み確率を算出し、前記主記憶装置の読み出し時間と前記主記憶装置の書き込み時間と算出した前記読み出し確率と算出した前記書き込み確率に基づき、前記キャッシュヒット判定部が判定したキャッシュミスに応答して前記主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成する、請求項１に記載の演算処理装置。
【請求項３】
前記置換基準生成部は、前記目標の読み出し領域の容量と、前記目標の書き込み領域の容量と、前記読み出し命令の計数値に基づく読み出し確率と前記書き込み命令の計数値に基づく書き込み確率とに基づいて、読み出し重み値と書き込み重み値とを生成し、
前記キャッシュ制御部は、キャッシュヒットするたびに、前記キャッシュヒットしたキャッシュラインの修正アクセス頻度に前記読み出し重み値または前記書き込み重み値を命令の種類に応じて加算し、
前記置換制御部は、キャッシュミスした場合、前記修正アクセス頻度が最小のキャッシュラインを置換対象に選択する、請求項１に記載の演算処理装置。
【請求項４】
前記置換基準生成部は、前記目標の読み出し領域の容量と、前記目標の書き込み領域の容量と、前記読み出し命令の計数値に基づく読み出し確率と前記書き込み命令の計数値に基づく書き込み確率とに基づいて、読み出し重み値と書き込み重み値とを生成し、
前記キャッシュ制御部は、キャッシュヒットするたびに、前記キャッシュヒットしたキャッシュラインにアクセス時刻を記録し、
前記置換制御部は、キャッシュミスした場合、前記アクセス時刻とキャッシュミス時刻との時間差を前記読み出し重み値または書き込み重み値で除算した修正時間差が、最長のキャッシュラインを置換対象に選択する、請求項１に記載の演算処理装置。
【請求項５】
前記置換基準生成部は、前記目標の読み出し領域の容量を前記読み出し確率で除して前記読み出し重み値を生成し、前記目標の書き込み領域の容量を前記書き込み確率で除して前記書き込み重み値を生成する、請求項３または４に記載の演算処理装置。
【請求項６】
前記置換制御部は、前記キャッシュラインを置換したとき、新たなキャッシュラインの前記修正アクセス頻度をゼロに初期化する、請求項３に記載の演算処理装置。
【請求項７】
前記キャッシュ制御部は、前記演算処理部が処理対象のプロセスをリセットしたとき、前記読み出し確率と、前記書き込み確率と、前記キャッシュミス確率とをリセットし、
前記置換基準生成部は、前記プロセスの処理期間より短い頻度で、前記目標の読み出し領域の容量と前記目標の読み出し領域の容量と、前記読み出し重み値と前記書き込み重み値とを再生成する、請求項３または４に記載の演算処理装置。
【請求項８】
前記置換基準生成部は、前記読み出し命令の計数値に基づく読み出し確率及び前記書き込み命令の計数値に基づく書き込み確率と、前記読み出し時間及び書き込み時間と、前記読み出し命令のキャッシュミス確率及び前記書き込み命令のキャッシュミス確率とをそれぞれ乗算し当該乗算値を加算することで、前記平均メモリアクセス時間を生成する、請求項１〜４のいずれか一項に記載の演算処理装置。
【請求項９】
前記主記憶装置の書き込み時間と前記主記憶装置の読み出し時間とは異なる、請求項１〜８のいずれか一項に記載の演算処理装置。
【請求項１０】
前記主記憶装置の書き込み時間は、前記主記憶装置の読み出し時間よりも長い、請求項９に記載の演算処理装置。
【請求項１１】
メモリアクセス命令を実行する演算処理部と、キャッシュメモリと、前記メモリアクセス命令に応答して前記キャッシュメモリを制御するキャッシュ制御部とを有するとともに、主記憶装置にアクセス可能な演算処理装置の制御方法において、
前記キャッシュ制御部が有するキャッシュヒット判定部が、前記メモリアクセス命令がキャッシュヒットか否かを判定し、
前記キャッシュ制御部が有するリード計数部が、前記演算処理部が実行したメモリアクセス命令が読み出し命令である場合、読み出し命令の計数値を増分し、
前記キャッシュ制御部が有するライト計数部が、前記演算処理部が実行したメモリアクセス命令が書き込み命令である場合、書き込み命令の計数値を増分し、
前記キャッシュ制御部が有するキャッシュヒット判定部が、前記演算処理部が実行したメモリアクセス命令に基づき、前記キャッシュメモリ部におけるキャッシュヒット又はキャッシュミスを判定し、
前記キャッシュ制御部が有する置換基準生成部が、前記リード計数部が計数した読み出し命令の計数値と、前記ライト計数部が計数した書き込み命令の計数値とに基づき、前記キャッシュヒット判定部が判定したキャッシュミスに応答して前記主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成し、
前記キャッシュ制御部が有する置換制御部が、前記目標の読み出し領域の容量と前記目標の書き込み領域の容量とに基づいて、前記キャッシュメモリの領域の置換を制御する、演算処理装置の制御方法。
【請求項１２】
前記キャッシュ制御部は、さらに、
前記目標の読み出し領域の容量と、前記目標の書き込み領域の容量と、前記読み出し命令の計数値に基づく読み出し確率と前記書き込み命令の計数値に基づく書き込み確率とに基づいて、読み出し重み値と書き込み重み値とを生成し、
キャッシュヒットするたびに、前記キャッシュヒットしたキャッシュラインの修正アクセス頻度に前記読み出し重み値または前記書き込み重み値を命令の種類に応じて加算し、
前記置換制御は、前記修正アクセス頻度が最小のキャッシュラインを置換対象に選択する、請求項１１に記載の演算処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，演算処理装置及び演算処理装置の制御方法に関する。
【背景技術】
【０００２】
演算処理装置は、プロセッサまたはCPU(Central Processing Unit)チップである。演算処理装置は、単数または複数のCPUコアとキャッシュとメモリアクセス制御回路とを有し、主記憶装置（メインメモリ）と接続される。キャッシュは、キャッシュコントローラとキャッシュメモリとを有する。キャッシュコントローラは、CPUコアが発行するメモリアクセス命令に応答して、キャッシュヒット判定がヒットの場合にキャッシュメモリにアクセスし、ミスの場合にメインメモリにアクセスする。キャッシュコントローラは、キャッシュミスした場合にアクセス先のメインメモリのデータをキャッシュメモリに登録する。
【０００３】
メモリアクセス命令は、キャッシュヒットした場合はキャッシュメモリにアクセスするので短時間で完了するが、キャッシュミスした場合はメインメモリにアクセスするので長時間を要する。したがって、キャッシュメモリの領域を効率的に配置し且つ効率的に使用することで、メモリアクセス命令の処理時間を短くすることが提案されている。例えば、以下の特許文献１、２などである。
【０００４】
メインメモリは、一般的にDRAM（Dynamic Random Access Memory）が利用される。DRAMは大容量で読み出し時間と書き込み時間が短いため、メインメモリに適している。
【０００５】
一方、近年において、DRAMよりビット単価が安いSSD（Solid State Device,フラッシュメモリ）がHDD(Hard Disk Drive)に置き換えられる傾向にある。さらに、DRAMとSSDとの間のビット単価及びアクセス時間を有するストレージクラスメモリ（SCM：Storage Class Memory）の開発が行われている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２０１３−５０５４８８号公報
【特許文献２】特開２０００−１５５７４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、DRAMは読み出しに要する時間と書き込みに要する時間（以下、読み出し時間、書き込み時間、またはレイテンシと称する場合がある）がほぼ同じであるのに対して、SSDのフラッシュメモリは、書き込みに要する時間が読み出しに要する時間より１０倍程度長い。また、SCMの多くも同様に、書き込みに要する時間が読み出しに要する時間よりも長いことが予想される。
【０００８】
そのため、書き込み命令でキャッシュメモリに登録されたキャッシュラインが、読み出し命令のキャッシュミスにより解放され、その読み出し命令のキャッシュラインに置き換えられると、その後の同じアドレスへの書き込み命令がキャッシュミスとなり、メインメモリへのメモリアクセスが発生する。その結果、処理時間が長いメインメモリへの書き込み命令が実行され、システム全体のメモリアクセス時間を長くし性能低下を招く。
【０００９】
そこで，実施の形態の第１の側面の目的は，キャッシュラインの置換制御を適切に行ってメモリアクセス性能を向上させる演算処理装置および演算処理装置の制御方法と提供することにある。
【課題を解決するための手段】
【００１０】
実施の形態の第１の側面は，主記憶装置にアクセス可能な演算処理装置において、
メモリアクセス命令を実行する演算処理部と、
前記主記憶装置が記憶するデータの一部を保持するキャッシュメモリと、
前記メモリアクセス命令に応答して前記キャッシュメモリを制御するキャッシュ制御部とを有し、
前記キャッシュ制御部は、
前記演算処理部が実行したメモリアクセス命令に基づき、前記キャッシュメモリ部におけるキャッシュヒット又はキャッシュミスを判定するキャッシュヒット判定部と、
前記演算処理部が実行したメモリアクセス命令が読み出し命令である場合、読み出し命令の計数値を増分させるリード計数部と、
前記演算処理部が実行したメモリアクセス命令が書き込み命令である場合、書き込み命令の計数値を増分させるライト計数部と、
前記リード計数部が計数した読み出し命令の計数値と、前記ライト計数部が計数した書き込み命令の計数値とに基づき、前記キャッシュミス判定部が判定したキャッシュミスに応答して前記主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成する置換基準生成部と、
前記目標の読み出し領域の容量と前記目標の書き込み領域の容量とに基づいて、前記キャッシュメモリの領域の置換を制御する置換制御部とを有する、演算処理装置である。
【発明の効果】
【００１１】
第１の側面によれば，メモリアクセス性能を向上させることができる。
【図面の簡単な説明】
【００１２】
【図１】本実施の形態における演算処理装置（CPUチップ）の構成例を示す図である。
【図２】本実施の形態におけるCPUチップ内のL2キャッシュの構成例を示す図である。
【図３】本実施の形態におけるキャッシュメモリのキャッシュラインの構成例を示す図である。
【図４】キャッシュ制御部のキャッシュ制御回路の構成例を示す図である。
【図５】キャッシュ制御部３２内の置換基準生成回路３４の構成例を示す図である。
【図６】キャッシュミス確率生成回路３４７のキャッシュミス確率の生成について説明する図である。
【図７】第１の実施の形態におけるキャッシュメモリ内のキャッシュタグメモリの構成を示す図である。
【図８】第１の実施の形態におけるキャッシュ制御部３２によるキャッシュ制御のフローチャート図である。
【図９】第１の実施の形態におけるキャッシュラインの置換処理のフローチャート図である。
【図１０】第２の実施の形態の修正アクセス頻度と重み値を説明する図である。
【図１１】第２の実施の形態におけるキャッシュメモリ内のキャッシュタグメモリの構成を示す図である。
【図１２】第２の実施の形態におけるキャッシュ制御部３２によるキャッシュ制御のフローチャート図である。
【図１３】第２の実施の形態におけるキャッシュラインの置換処理のフローチャート図である。
【図１４】第２の実施の形態における最適重み値探索テーブルの一例を示す図である。
【図１５】第３の実施の形態におけるキャッシュメモリ内のキャッシュタグメモリの構成を示す図である。
【図１６】第３の実施の形態におけるキャッシュ制御部３２によるキャッシュ制御のフローチャート図である。
【図１７】第３の実施の形態におけるキャッシュラインの置換処理のフローチャート図である。
【図１８】CPU（演算処理装置）を有する情報処理装置が電源オンしてからアプリケーションが実行されるまでの状態遷移図である。
【図１９】アドレスAへの読み出し命令でキャッシュミスしたときの動作を示すタイミングチャート図である。
【図２０】アドレスAへの読み出し命令でキャッシュヒットしたときの動作を示すタイミングチャート図である。
【図２１】アドレスAへの書き込み命令でキャッシュミスしたときの動作を示すタイミングチャート図である。
【図２２】アドレスAへの書き込み命令でキャッシュヒットしたときの動作を示すタイミングチャート図である。
【図２３】ワーキングセット容量Mの更新処理を示すタイミングチャート図である。
【図２４】重み値の更新処理を示す図である。
【図２５】キャッシュミス時にクリーンなキャッシュラインを追い出す処理を示すタイミングチャート図である。
【図２６】キャッシュミス時にダーティなキャッシュラインを追い出す処理を示すタイミングチャート図である。
【発明を実施するための形態】
【００１３】
図１は、本実施の形態における演算処理装置（CPUチップ）の構成例を示す図である。図１のCPUチップ１０は、４個のCPUコア２０Ａ−２０Ｄと、L2キャッシュ３０と、メモリアクセスコントローラ１１とを有する。そして、CPUチップ１０は、メモリアクセスコントローラ１１を介して外部に設けられたメインメモリ（主記憶装置）１２に接続される。
【００１４】
メインメモリ１２は、例えばフラッシュメモリや、SCMの一つである抵抗変化型メモリ（ReRAM）や強誘電体メモリ（FeRAM）などであり、読み出しに要する時間（読み出しレイテンシ）より書き込みに要する時間（書き込みレイテンシ）が長い。
【００１５】
CPUコア２０は、アプリケーションプログラムを実行し、メモリアクセス命令を実行する。CPUコア２０は、L1キャッシュを有し、メモリアクセス命令のアドレスのキャッシュラインがL1キャッシュに存在しない場合、そのメモリアクセス命令はL2キャッシュ３０のキャッシュコントローラのパイプラインに入力される。
【００１６】
L2キャッシュ３０は、メモリアクセス命令に応答して、キャッシュヒットか否か判定し、キャッシュヒットの場合は、L2キャッシュ３０内のキャッシュメモリのキャッシュラインにアクセスする。一方、キャッシュミスの場合は、メモリアクセスコントローラ１１を介してメインメモリ１２にアクセスする。
【００１７】
図２は、本実施の形態におけるCPUチップ内のL2キャッシュの構成例を示す図である。L2キャッシュ（以下単にキャッシュ）３０は、キャッシュ制御を行うキャッシュ制御部３２と、キャッシュメモリ３５とを有する。キャッシュ制御部３２内のキャッシュ制御回路３３は、入力されたメモリアクセス命令に応答して、キャッシュヒット判定を行い、キャッシュヒットの場合キャッシュメモリ３５へのアクセス制御を行い、キャッシュミスの場合メモリアクセスコントローラ１１を介してメインメモリ１２へのアクセス制御を行う。また、キャッシュ制御回路３３は、キャッシュミスした場合、キャッシュメモリ３５内のいずれかのキャッシュラインを解放し、新たなキャッシュラインにメインメモリ内のデータ等を登録する。このキャッシュラインの入れ替えを、キャッシュラインの置換処理と称する。
【００１８】
キャッシュ制御部３２内の置換基準生成回路３４は、キャッシュラインの置換制御において解放するキャッシュラインの判定基準を生成する。この判定基準については後で詳述する。
【００１９】
キャッシュメモリ３５は、データを記憶するキャッシュデータメモリ３６と、タグ情報を記憶するキャッシュタグメモリ３７とを有する。キャッシュメモリ３５は、キャッシュ登録単位の容量を有する複数のキャッシュラインを有する。キャッシュタグメモリ３７は、各キャッシュラインのアドレス情報、ステータス情報などを記憶する。また、キャッシュデータメモリ３６は、各キャッシュラインにメモリアクセスされたデータを記憶する。
【００２０】
本実施の形態では、キャッシュメモリ３５は、読み出し命令のアドレスに対応する複数のキャッシュラインを有する読み出し領域３５＿rと、書き込み命令のアドレスに対応する複数のキャッシュラインを有する書き込み領域３５＿wとに分けられる。ここで、読み出し領域３５＿rは、読み出し命令で多く（例えばアクセス命令の５０％以上が読み出し命令）参照されるキャッシュラインの領域であり、書き込み領域３５＿wは、書き込み命令で多く（例えばアクセス命令の５０％以上が書き込み命令）参照されるキャッシュラインの領域である。つまり、キャッシュラインは、主に読み出し命令で参照されるキャッシュラインと、主に書き込み命令で参照されるキャッシュラインとを有する。しかし、読み出し領域のキャッシュラインは、読み出し命令のみで参照されるわけではなく、書き込み領域のキャッシュラインも、書き込み命令のみで参照されるわけではない。
【００２１】
なお、上記の５０％は、６０％以上が読み出し命令の場合は読み出し領域に、４０％以上が書き込み命令の場合は書き込み領域に選定されてもよい。一般に、アクセス命令の多くは読み出し命令だからである。さらに、適切な基準％を設定して読み出し領域と書き込み領域を判定してもよい。
【００２２】
本実施の形態では、CPUコアによりプログラム内のプロセスが実行されている間、メモリアクセス命令の読み出し命令と書き込み命令の回数をカウンタなどで監視し、実行中のプロセスに最適な目標とする読み出し領域の容量Drと目標とする書き込み領域の容量Dwを算出または生成する。例えば、最適な目標値は、読み出し命令と書き込み命令の回数に基づき、キャッシュミスに応答してメインメモリ１２へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量である。そして、キャッシュ制御部３２は、キャッシュミスした場合、キャッシュメモリ３５内の読み出し領域３５＿rと書き込み領域３５＿wとが、目標の読み出し領域の容量Drと目標の書き込み領域の容量Dwに近づくように、キャッシュラインの置換制御を行う。置換制御については後で詳述する。
【００２３】
図３は、本実施の形態におけるキャッシュメモリのキャッシュラインの構成例を示す図である。図３には、４つのキャッシュラインCL_0-CL_3が示されている。各キャッシュラインのキャッシュタグメモリ３７は、アドレス情報ADDRESSと、E,S,M,Iなどのデータのステータス情報STATEと、キャッシュラインの置換制御の基準である基準情報を記憶する。この基準情報は、後述する各実施の形態毎に異なる。また、各キャッシュラインのキャッシュデータメモリ３６はデータを記憶する。
【００２４】
図４は、キャッシュ制御部のキャッシュ制御回路の構成例を示す図である。キャッシュ制御回路３３は、キャッシュヒット判定回路３３１と、キャッシュライン置換制御回路３３２と、キャッシュコヒーレンス制御回路３３３とを有する。
【００２５】
キャッシュヒット判定回路３３１は、メモリアクセス命令に応答して、キャッシュタグメモリ３７のアドレス情報を検索して、命令に対応するアドレスのキャッシュラインが存在するか否かにより、キャッシュヒット判定をする。また、キャッシュヒット判定回路３３１は、メモリアクセス命令が発生すると後述する読み出しカウンタまたは書き込みカウンタを命令の種類に応じてインクリメントする。
【００２６】
キャッシュライン置換制御回路３３２は、キャッシュミスに応答して、キャッシュラインの置換制御を行う。詳細な処理は後述するが、キャッシュライン置換制御回路３３２は、置換基準に基づいて選択したキャッシュラインを解放し、新たなキャッシュラインとしてデータを登録する。
【００２７】
キャッシュコヒーレンス制御回路３３３は、キャッシュラインのデータのステータスを更新してキャッシュタグメモリに格納し、更に、ステータスに応じてキャッシュラインのデータをメインメモリにライトバックする処理などを制御する。ステータスは、例えば、キャッシュラインのデータが無効のI（Invalid）状態と、キャッシュラインのデータがそのキャッシュメモリだけに存在し、メインメモリのデータから変更されているM（Modified）状態と、キャッシュラインのデータが複数のL2キャッシュのキャッシュメモリに存在し、メインメモリのデータから変更されていないS（Shared）状態、キャッシュラインのデータが他のキャッシュメモリに存在しないE（Exclusive）状態などである。
【００２８】
例えば、キャッシュコヒーレンス制御回路３３３は、新たなデータがキャッシュに登録されると、ステータスをI状態からE状態に更新し、その登録されたキャッシュ内のデータが変更されるとステータスをE状態からM状態に更新する。また、キャッシュコヒーレンス制御回路３３３は、EやS状態のデータのキャッシュラインが解放される場合、そのデータをメインメモリにライトバックすることは行わないが、M状態のデータのキャッシュラインが解放される場合、そのデータをメインメモリにライトバックしてから解放する。
【００２９】
［本実施の形態におけるキャッシュライン置換制御］
キャッシュラインの置換処理は、一般に、キャッシュミスが発生した場合、キャッシュメモリのキャッシュラインのうち参照頻度が最も低いキャッシュラインを削除し、メインメモリにアクセスして取得したデータを新たなキャッシュラインに登録する。また、最も長い時間参照されていないキャッシュラインを削除対象のキャッシュラインに選択する方法もある。前者はLFU(Least Frequently Used)方式、後者はLRU(Least Recently Used)方式である。
【００３０】
上記の置換方法では、読み出し命令が書き込み命令より頻繁に発生した場合、書き込み命令で参照されるキャッシュラインが追い出され、書き込み命令でキャッシュミスが頻発する。メインメモリの読み出し時間より書き込み時間が長い場合、書き込み命令のキャッシュミスによるメインメモリアクセスが頻発することで、メモリアクセス命令の処理効率が低下する。
【００３１】
したがって、本実施の形態では、キャッシュ制御部は、書き込み命令で頻繁に参照されるキャッシュラインを読み出し命令で頻繁に参照されるキャッシュラインより優先的にキャッシュ内に残すようにキャッシュラインの置換制御を行う。しかし、（１）CPUコアが処理しているプロセスの読み出し確率Erと書き込み確率Ew、（２）メインメモリ内のユーザ領域のサイズM（ワーキングセット領域の容量）、（３）メインメモリの読み出しレイテンシTrと書き込みレイテンシTwなどに応じて、どの程度書き込み命令側のキャッシュラインを優先させるべきかが変動する。
【００３２】
そこで、本実施の形態では、上記の変動要因の（１）（２）を監視し、（３）を電源起動時等にメインメモリデバイスから取得する。そして、これら変動要因を利用してキャッシュミス発生時のペナルティであるメインメモリへの平均アクセス時間を算出し、メインメモリの平均アクセス時間を最小にする目標の読み出し領域の容量Drと書き込み領域の容量Dwを生成する。そして、キャッシュ制御部のキャッシュライン置換制御部は、置換処理で、キャッシュメモリが目標の読み出し領域の容量Drと書き込み領域の容量Dwになるように、キャッシュメモリから追い出されるキャッシュライン（置換対象キャッシュライン）を選択する。
【００３３】
メモリアクセス命令のアクセス時間の平均値Pは、以下の数式により求めることができる。
P=Er*(Tr*Hr+TCr*(1-Hr))+Ew*(Tw*Hw+TCw*(1-Hr))          （１）
ここで、Er,Ew,Tr,Tw,Hr,Hw,TCr,TCwは次のとおりである。
Er：メモリアクセス命令のうち読み出し命令が発生する確率
Ew：メモリアクセス命令のうち書き込み命令が発生する確率
Tr：メインメモリの読み出しに要する時間、読み出しレイテンシ
Tw：メインメモリの書き込みに要する時間、書き込みレイテンシ
Hr：読み出し命令のキャッシュミス確率、（１−Hr）はキャッシュヒット確率
Hw：書き込み命令のキャッシュミス確率、（１−Hw）はキャッシュヒット確率
TCr：読み出し命令でヒットしたときにキャッシュのデータがCPUコアに転送完了する時間
TCw：書き込み命令でヒットしたときにキャッシュのデータを上書き完了する時間
上記において、第一項は読み出しのアクセス時間の平均値であり、第二項は書き込みのアクセス時間の平均値である。第一項において、Tr*Hr*Erは読み出しレイテンシTrに読み出しのキャッシュミス確率Hrと読み出し発生確率Erを乗じたものであり、TCr*(1-Hr)*Erはキャッシュメモリの読み出し時間TCrに読み出しのキャッシュヒット確率（１−Hr）と読み出し発生確率Erを乗じたものである。また、第二項において、Tw*Hw*Ewは書き込みレイテンシTwに書き込みキャッシュミス確率Hwと書き込み発生確率Ewを乗じたものであり、TCw*(1-Hw)*Ewはキャッシュメモリの書き込み時間TCwに書き込みのキャッシュヒット確率（１−Hw）と書き込み発生確率Ewを乗じたものである。
【００３４】
キャッシュヒット時の処理時間TCr, TCwは、キャッシュミス時の処理時間Tr,Twより非常に小さい。そこで、キャッシュヒットした場合に要する時間を無視して、メモリアクセス命令がキャッシュミスした場合のアクセス時間の平均値P1を求める。すなわち、キャッシュミスによる平均メモリアクセス時間P1は、上記の式（１）からキャッシュヒットした場合の時間を除外することで求められる。
【００３５】
つまり、メモリアクセス命令がキャッシュミスした場合の平均アクセス時間P1は以下のとおりとなる。
P1= Er*(Tr*Hr)+Ew*(Tw*Hw)                              （２）
なお、このキャッシュミス時の平均アクセス時間P1は、キャッシュミスによるペナルティ時間である。
【００３６】
図５は、キャッシュ制御部３２内の置換基準生成回路３４の構成例を示す図である。キャッシュミスの場合のキャッシュラインの置換の基準の第１の例は、式（２）の平均アクセス時間P1を最小にする目標の読み出し領域の容量Dr,目標の書き込み領域Dwである。また、置換の基準の第２の例は、メモリアクセス命令のキャッシュメモリへのアクセス頻度を読み出しの重み値WVr及び書き込みの重み値WVwで修正した修正アクセス頻度である。第３の例は、最近のアクセス時刻とキャッシュミス時刻との時間差を重み値で修正した修正時間差である。
【００３７】
図５に示した置換基準生成回路３４は、読み出し命令をカウントするリードカウンタ（リード計数部）３４１と、書き込み命令をカウントするライトカウンタ（ライト計数部）３４２と、リードレイテンシTrを保持するレジスタ３４３と、ライトレイテンシTwを保持するレジスタ３４４と、メインメモリ内のユーザによりアクセスされるメモリ空間（ワーキングセット領域）のサイズMを保持するMレジスタ３４５である。
【００３８】
リードカウンタとライトカウンタについては、キャッシュ制御部にメモリアクセス命令が発行されると、キャッシュ制御部は命令の種類を判別し、読み出しの場合はリードカウンタ３４１をインクリメントし、書き込みの場合はライトカウンタ３４２をインクリメントする。両カウント値er,ewは、実行中のプロセスのメモリアクセス命令の読み出しと書き込みの割合を示す。
【００３９】
そして、図５に示されるとおり、Er、Ew生成回路３４６が、実行中のプロセスでのカウント値er,ewからそのプロセスでの読み出し確率Er,書き込み確率Ewを生成する。生成する式は、例えば、以下のとおりである。
Er=roundup(256*er/(er+ew))          （３）
Ew=roundup(256*ew/(er+ew))          （４）
すなわち、発生確率er/(er+ew), ew/(er+ew)を２５６倍して正規化した整数値である。roundupは切り上げである。
【００４０】
読み出しカウンタ３４１、書き込みカウンタ３４２は、プロセスが変更されるたびにリセットされる。また、桁あふれしたばあいは、例えばカウンタはいずれも０に初期化される。初期化後の直後は読み出しと書き込みの比率が不正確になるが、変換基準と適切な頻度で更新することで問題は少ない。
【００４１】
リードレイテンシTrとライトレイテンシTwは、例えばCPUの電源起動時にメインメモリから取得することができる。TrとTwの比をパラメータとして取得してもよい。TrとTwに対して線形に変動するパラメータであればよい。
【００４２】
メモリ空間（ワーキングセット領域）のサイズMは、プロセスがある時点で使用中の仮想メモリページの集合のサイズであり、プロセスに依存して変動する。このメモリ空間のサイズMは、CPUチップ内のメモリアクセスコントローラMAC（またはメモリマネージメントユニットMMU）に格納されている。よって、キャッシュ制御部３２は、メモリアクセスコントローラMACに実行中のプロセスIDに基づいてサイズMを問い合わせることができる。メモリ空間のサイズMは、OSがメモリ要求（page fault）した場合や、CPUのコンテキストスワップ（レジスタの情報の置き換え）が発生した場合に更新される。但し、変換基準を更新するタイミングでメモリアクセスコントローラMACに問い合わせることで、更新されたメモリ空間のサイズMを取得することができる。
【００４３】
図５に示されるとおり、キャッシュミス確率生成回路３４７は、メモリ空間のサイズMと、キャッシュラインの容量cと、目標の読み出し領域の容量Dr、目標の書き込み領域の容量Dwに基づいて、読み出しでのキャッシュミス確率Hrと読み出しでのキャッシュミス確率Hwを生成する。
【００４４】
図６は、キャッシュミス確率生成回路３４７のキャッシュミス確率の生成について説明する図である。キャッシュメモリ３５のキャッシュミス確率は、メインメモリ１２内のキャッシュラインCL_0〜CL_n-1に対応する領域がアクセスで選択されない確率を、キャッシュメモリ３５のキャッシュライン数でべき乗して求められる。
【００４５】
図６では、メインメモリ１２のユーザ領域であるワーキングセット領域の容量がMで、キャッシュラインの容量がｃであるので、ワーキングセット領域のキャッシュラインに対応するブロック領域の数ｎは、ｎ＝M/cである。したがって、各ブロック領域がアクセスにより選択される確率と非選択確率は、以下のとおりになる。
選択確率＝１／ｎ＝ｃ／Ｍ
非選択確率＝１−ｃ／Ｍ
次に、キャッシュメモリ３５においては、目標の読み出し領域の容量Drはキャッシュライン数Dr/cを有し、目標の書き込み領域の容量Dwはキャッシュライン数Dw/cを有する。したがって、上記の非選択確率をそれぞれのキャッシュライン数でべき乗すると、読み出し領域２５＿ｒと書き込み領域３５＿ｗのキャッシュミス確率Hr,Hwは、以下のとおりである。
Hr＝（１−c/M）Dr/c          （５）
Hw＝（１−c/M）Dw/c          （６）
上記式（５）（６）のキャッシュミス確率Hr,Hwは、CPUコアが管理するメインメモリ内のワーキングセット領域の容量Mに基づいて変動する。この容量Mは、処理されるプロセスなどに依存する。
【００４６】
図５に戻り、置換基準生成回路３４は、目標の読み出し領域の容量Drと目標の書き込み領域の容量Dwとを生成するDr,Dw生成回路３４８を有する。Dr,Dw生成回路３４８は、前述の式（２）のキャッシュミスが発生した場合のメインメモリへのアクセス時間の平均値を最小にする容量Dr,Dwを算出、またはルックアップテーブルを参照して生成する。
【００４７】
前述したキャッシュミス時の平均アクセス時間P1の式（２）は次のとおりである。
P1= Er*(Tr*Hr)+Ew*(Tw*Hw)                              （２）
そして、あるプロセスでの読み出し確率Er,書き込み確率Ewは、以下の前述の式（３）（４）のとおりである。
Er=roundup(256*er/(er+ew))          （３）
Ew=roundup(256*ew/(er+ew))          （４）
さらに、キャッシュミス確率Hr,Hwは、以下の前述の式（５）（６）のとおりである。
Hr＝（１−c/M）Dr/c          （５）
Hw＝（１−c/M）Dw/c          （６）
そして、メモリレイテンシTr,Twはメインメモリの特性により固定値として得られる。そこで、式（２）にレイテンシTr,Twと、プロセスの実行状態によって変動するEr,Ew、Hr,Hw（式（３）（４）（５）（６））とを代入すると、キャッシュミス時の平均アクセス時間P1は、Dr/Dwに応じて最小値をとることが分かる。そこで、Dr,Dw生成回路３４８は、キャッシュミス時の平均アクセス時間P1を最小値にする目標の読み出し領域と書き込み領域の容量Dr,Dwまたは容量比Dr/Dwを生成する。この目標の読み出し領域と書き込み領域の容量Dr,Dwは、後述する第１の実施の形態で置換基準として利用される。
【００４８】
置換基準生成回路３４は、さらに、重み値生成回路３４９を有する。重み値生成回路は、目標の読み出し領域と書き込み領域の容量Dr,Dwと、読み出し確率Er、書き込み確率Ewとに基づいて、読み出し用重み値WV_rと書き込み用重み値WV_wとを以下のとおり求める。
WV_r＝Dr/Er          （７）
WV_w＝Dw/Ew          （８）
この重み値は、後述する第２、第３の実施の形態で置換基準として利用される。
【００４９】
［第１の実施の形態］
第１の実施の形態では、図２，図４に示されるとおり、キャッシュ制御部３３は、メモリアクセス命令がキャッシュヒットか否かを判定するキャッシュヒット判定回路３３１と、キャッシュミス発生時に、キャッシュメモリ内のキャッシュラインの置換制御を行うキャッシュライン置換制御回路３３２とを有する。さらに、キャッシュ制御部３３は、置換基準を生成する置換基準生成回路３４とを有する。
【００５０】
そして、置換基準生成回路３４は、図５に示されるとおり、メモリアクセス命令のうち読み出し命令の発生確率である読み出し確率Erと書き込み命令の発生確率である書き込み確率Ewと、メインメモリの読み出し時間（レイテンシ）Tr及び書き込み時間（レイテンシ）Twと、キャッシュメモリ内の目標の読み出し領域３５＿ｒと目標の書き込み領域３５＿ｗそれぞれのキャッシュミス確率Hr,Hwとに基づいて、キャッシュミスに応答してメインメモリにアクセスするときに要する平均メモリアクセス時間P1を最小にする目標の読み出し領域の容量Dr及び目標の書き込み領域の容量Dwを生成する。
【００５１】
この容量Dr,Dwの生成は、Dr/Dwを可変させた場合のキャッシュミス時の平均メモリアクセス時間P1（式（２））を最小にするDr/Dwを算出することで行うことができる。または、容量Dr,Dwの生成は、複数のEr*Tr/Ew*Twと複数のMとの組合せに対して、平均メモリアクセス時間P1を最小にする容量比Dr/Dwのルックアップテーブルを予め作成しておき、そのルックアップテーブルを参照することで行うこともできる。
【００５２】
第１の実施の形態では、キャッシュライン置換制御回路３３２は、キャッシュミスが発生した場合、平均メモリアクセス時間P1を最小にする容量Dr,Dw（容量比Dr/Dw）に基づいて、キャッシュメモリから追い出される置換対象キャッシュラインを選択する。そして、その選択されたキャッシュラインのデータが必要に応じてメインメモリに書き出され、アクセスされたメインメモリのデータがそのキャッシュラインに登録される。
【００５３】
以下、第１の実施の形態におけるキャッシュ制御について具体的に説明する。
【００５４】
図７は、第１の実施の形態におけるキャッシュメモリ内のキャッシュタグメモリの構成を示す図である。図３と比較すると分かるとおり、図７のキャッシュタグメモリ３７の各キャッシュラインCLは、基準情報として、各キャッシュラインにアクセスしたメモリアクセス命令のうち読み出し回数Arと書き込み回数Awとを格納する。また、各キャッシュラインCLがアドレス情報ADDRESSとステータス情報STATEを有するのは、図３と同じである。
【００５５】
第１の実施の形態では、後に詳述するが、キャッシュ制御部が、キャッシュミス時に、キャッシュタグ内の読み出し回数Arと書き込み回数Awとを比較し、Ar>Awの場合はそのキャッシュラインは読み出し用キャッシュラインと判定し、Ar<Awの場合はそのキャッシュラインは書き込み用キャッシュラインと判定する。そして、キャッシュ制御部は、判定された読み出し用キャッシュラインの数と書き込み用キャッシュラインの数の比が、現在の読み出し領域と書き込み領域の比とみなす。さらに、現在の比と、目標の書き込み領域の容量Drと目標の書き込み領域の容量Dwとの比とを比較し、置換対象のキャッシュラインを読み出し領域から選択するか、書き込み領域から選択するかを判定する。最後に、判定されたいずれかの領域からLFU方式またはLRU方式で置換対象のキャッシュラインを選択する。
【００５６】
図８は、第１の実施の形態におけるキャッシュ制御部３２によるキャッシュ制御のフローチャート図である。図８のフローチャート図内の各処理は、キャッシュ制御部３２内のキャッシュ制御回路３３と置換基準生成回路３４の処理が含まれる。まず、キャッシュ制御部３２は、メモリアクセス命令がロード命令（読み出し命令）かストア命令（書き込み命令）かに応じて（S1）、それぞれ対応するリードカウンタ３４１またはライトカウンタ３４２を＋１インクリメントする（S2,S3）。図５で示されるとおり、リードカウンタ３４１とライトカウンタ３４２は、置換基準生成回路３４内に設けられる。
【００５７】
そして、目標の読み出し領域の容量Drと目標の書き込み領域の容量Dwとを更新すべきタイミングの場合（S4のYES）、置換基準生成回路３４が容量Dr,Dwを更新する。この更新処理は、置換基準生成回路３４が実行する。この容量Dr,Dwを更新すべきタイミングは、例えば次のとおりである。
【００５８】
まず、CPUコアが処理するプロセスが切り替えられるたびに、リードカウンタ３４１とライトカウンタ３４２がリセットされ、ワーキングセット領域の容量Mもリセットされる。そして、プロセスの処理が行われる間に、リードカウンタとライトカウンタのカウント値er,ewの比率が変動するとともに、ワーキングセット領域の容量Mも変動する。ワーキングセット領域の容量Mは、ワーキングセット領域の増大を要求するページフォルト命令（page_fault）により増大し、CPU内のレジスタ値であるコンテキストを切り替える場合にも変化する。したがって、プロセスの処理中に変動するこれらの値er,ew,Mに基づいて生成される領域Dr,Dwも変動する。そこで、本実施の形態では、プロセスの切替タイミングより十分に短いタイミングで、変動するカウント値er,ewとワーキングセット領域の容量Mに基づいて容量Dr,Dwを更新する。
【００５９】
したがって、容量Dr,Dwを更新すべきタイミングは、タイマーが更新周期を経過するタイミング、メモリアクセス回数er+ewが２５６回行われるタイミング、ページフォルト命令が発生したタイミングなどが選択可能である。
【００６０】
次に、キャッシュ制御部３２は、メモリアクセス命令のアドレスに基づいてキャッシュヒットしたか否か判定する（S6）。キャッシュヒットした場合（S6のHIT）、キャッシュ制御部３２は、メモリアクセス命令がロード命令（読み出し命令）なら（S7のLOAD）、キャッシュメモリのデータを読み出し、CPUコアにデータを返信し（データ応答）（S8）、ヒットしたキャッシュラインのタグ内のリード回数Arを＋１加算する（S9）。キャッシュヒットした場合（S6のHIT）、キャッシュ制御部３２は、メモリアクセス命令がストア命令（書き込み命令）なら（S7のSTORE）、キャッシュメモリに書き込みデータを書き込み（S10）、ヒットしたキャッシュラインのタグ内のライト回数Awを＋１加算する（S11）。
【００６１】
一方、キャッシュミスした場合（S6のMISS）、キャッシュ制御部３２のキャッシュ置換制御回路３３２が、キャッシュラインの置換処理を実行する（S12）。
【００６２】
図９は、第１の実施の形態におけるキャッシュラインの置換処理のフローチャート図である。キャッシュライン置換制御回路３２は、キャッシュに空きがある場合（S121のYES）、空いているキャッシュラインを新たに登録されるキャッシュラインに予約し（S126）、キャッシュラインのタグ情報を初期化する（S127）。
【００６３】
一方、キャッシュライン置換制御回路３３２は、キャッシュに空きがない場合（S121のNO）、次の処理S122を実行する。すなわち、キャッシュ置換制御回路３３２が、キャッシュタグ内の読み出し回数Arと書き込み回数Awとを比較し、Ar>Awの場合はそのキャッシュラインは読み出し用キャッシュラインと判定し、Ar<Awの場合はそのキャッシュラインは書き込み用キャッシュラインと判定する。
【００６４】
そして、キャッシュ置換制御回路３３２は、判定された読み出し用キャッシュラインの数と書き込み用キャッシュラインの数の比を、現在のキャッシュメモリの読み出し領域と書き込み領域の比とみなす。さらに、現在の両領域の比R:Wと、目標の書き込み領域の容量Drと目標の書き込み領域の容量Dwとの比（Dr:Dw）とを比較し、置換対象を読み出し領域にするか書き込み領域にするかを選択する。この読み出し領域か書き込み領域かの選択は、現在の比R:Wが目標とする比Dr:Dwに近づくように行われる。つまり、現在の比R/W＞目標の比Dr/Dwなら、読み出し領域が置換対象に選択され、R/W＜Dr/Dwなら、書き込み領域が置換対象に選択される。
【００６５】
最後に、キャッシュ置換制御回路３３２は、選択された読み出し領域または書き込み領域から、LFU方式またはLRU方式で置換対象のキャッシュラインを選択する（S122）。
【００６６】
そして、キャッシュ置換制御回路３３２は、置換対象のキャッシュラインのステータス情報STATEがM状態（Modified: キャッシュメモリは更新済みだがメインメモリは未更新）なら（S123のM）、メインメモリにライトバックし、E、S状態（Exclusive, Shared）ならライトバックせずに、置換対象のキャッシュラインを解放する（S125）。その後、キャッシュ置換制御回路は、解放したキャッシュラインを新たにデータエントリするキャッシュラインに予約し（S126）、そのキャッシュラインのタグの情報を初期化する（S127）。
【００６７】
以上の通り、第１の実施の形態では、キャッシュ置換制御回路は、キャッシュミス時の平均メモリアクセス時間P1を最小にする目標とする読み出し領域と書き込み領域の容量Dr,Dwに近づくように、キャッシュメモリ内の読み出し回数が多い読み出し領域か書き込み回数が多い書き込み領域かのキャッシュラインを置換対象のキャッシュラインに選択する。このような置換制御を行うことで、キャッシュメモリ内の読み出し領域と書き込み領域の比は、目標とする読み出し領域と書き込み領域の容量Dr,Dwの比に近づき、キャッシュミス時のメインメモリアクセス時間を最小にすることができる。
【００６８】
［第２の実施の形態］
第２の実施の形態では、図２，図４に示されるとおり、キャッシュ制御部３３は、メモリアクセス命令がキャッシュヒットか否かを判定するキャッシュヒット判定回路３３１と、キャッシュミス発生時に、キャッシュメモリ内のキャッシュラインの置換制御を行うキャッシュライン置換制御回路３３２とを有する。さらに、キャッシュ制御部３３は、置換基準を生成する置換基準生成回路３４とを有する。
【００６９】
そして、置換基準生成回路３４は、図５に示されるとおり、メモリアクセス命令のうち読み出し命令の発生確率である読み出し確率Erと書き込み命令の発生確率である書き込み確率Ewと、メインメモリの読み出し時間（レイテンシ）Tr及び書き込み時間（レイテンシ）Twと、キャッシュメモリ内の目標の読み出し領域３５＿ｒと目標の書き込み領域３５＿ｗそれぞれのキャッシュミス確率Hr,Hwとに基づいて、キャッシュミスに応答してメインメモリにアクセスするときに要する平均メモリアクセス時間P1を最小にする目標の読み出し領域の容量Dr及び目標の書き込み領域の容量Dwを生成する。ここまでは、第１の実施の形態と同じである。
【００７０】
第２の実施の形態では、置換基準生成回路３４は、さらに、重み値生成回路３４９が、読み出し確率Er、書き込み確率Ew、目標の読み出し領域の容量Dr及び目標の書き込み領域の容量Dwに基づいて、読み出し用の重み値WVrと書き込み用の重み値WVwとを生成する。この読み出し用重み値WVr、書き込み用重み値WVrは、前述したとおり、次のように算出される。
WVr＝Dr/Er        （７）
WVw＝Dw/Ew        （８）
そして、キャッシュ制御回路３３は、そのキャッシュラインへの読み出しまたは書き込みが発生するたびに、つまりキャッシュヒットするたびに、キャッシュラインのタグに格納している修正アクセス頻度に、読み出しまたは書き込みに対応する重み値WVr,WVwを加算して、加算値を上書きする。したがって、修正アクセス頻度CAFは、以下の式（９）になる。
CAF＝er * WVr + ew * WVw        （９）
このように、修正アクセス頻度CAFは、あるプロセスが開始したときからのアクセス回数er,ewを重み値で乗算して修正したものであり、修正アクセス回数と称する。但し、あるプロセス処理時間内でのアクセス回数を修正しているので、以下、修正アクセス頻度と称する。
【００７１】
さらに、キャッシュライン置換制御回路３３２は、キャッシュミスが発生すると、キャッシュメモリ内の全てのキャッシュラインのうち、最小の修正アクセス頻度CAFを有するキャッシュラインを置換対象キャッシュラインに選択する。つまり、第２の実施の形態では、キャッシュミス時の置換対象キャッシュラインをLFU方式で選択する。
【００７２】
第２の実施の形態は、第１の実施の形態のように、キャッシュラインを読み出しが多い読み出し領域と書き込みが多い書き込み領域とに区別することは行わない。第２の実施の形態は、全てのキャッシュラインの中から最小修正アクセス頻度CAFのキャッシュラインを置換対象に選択する。しかし、キャッシュタグに記録される修正アクセス頻度CAFは、読み出し回数erを読み出しの重み値WVrで修正し、書き込み回数ewを書き込みの重み値WVwで修正して合計した値になる。つまり、修正アクセス頻度CAFは、書き込み回数を見かけ上高く修正したアクセス頻度になる。したがって、キャッシュライン置換制御回路が最小の修正アクセス頻度のキャッシュラインを置換対象にすることで、書き込み回数が多いキャッシュラインは、読み出し回数が多いキャッシュラインより、より長くキャッシュメモリ内に留まる。さらに、書き込み回数が少なくてもある程度の回数であれば、長くキャッシュメモリ内に留まる。その結果、読み出しが多いキャッシュラインの数と書き込みが多いキャッシュラインの数の比は、目標の読み出し領域の容量Drと目標の書き込み領域の容量Dwと近づくように制御される。
【００７３】
図１０は、第２の実施の形態の修正アクセス頻度と重み値を説明する図である。図１０において、左側のキャッシュメモリ３５＿１は、単純にアクセス頻度に基づいて置換対象キャッシュラインを選択して入れ替えた例であり、その場合は、読み出し領域３５＿ｒと書き込み領域３５＿ｗの比率が読み出し確率Erと書き込み確率Ewの比率になる。例えば、全てのメモリアクセス命令のうち読み出し確率Erと書き込み確率Ewの比がEr:Ew＝３：２の場合、最小アクセス頻度のキャッシュラインを置換対象に選択すると、キャッシュメモリの読み出し領域３５＿ｒのキャッシュライン数と書き込み領域３５＿ｗのキャッシュライン数の比もEr:Ewと同じ３：２に近づく。
【００７４】
一方で、右側のキャッシュメモリ３５＿２は、平均メモリアクセス時間P1を最小にする目標の読み出し領域の容量Drと目標の書き込み領域の容量Dwとの比で分配されている。もしDr:Dw＝１：４であるなら、キャッシュメモリの読み出し領域３５＿ｒのキャッシュライン数と書き込み領域３５＿ｗのキャッシュライン数の比も１：４になるように制御することで、キャッシュミス時の平均メインメモリアクセス時間P1を最小にすることができる。
【００７５】
そこで、読み出し回数erに読み出しの重み値WVr＝Dr/Erを乗算し、書き込み回数ewに書き込みの重み値WVw＝Dw/Ewを乗算することで、修正読み出し回数er*（Dr/Er）と修正書き込み回ew*(Dw/Ew)との比は、以下のとおりDr:Dwになる。つまり、er:ew＝Er:Ewだからである。
er*（Dr/Er）：ew*(Dw/Ew)＝Dr:Dw
したがって、修正アクセス頻度CAFを以下の式（９）のように修正読み出し回数と修正書き込み回数を合算することで、
CAF＝er * WVr + ew * WVw        （９）
全てのキャッシュラインについて、同じアクセス回数なら、書き込みが多いキャッシュラインはキャッシュメモリ内に留まりやすくなり、読み出しが多いキャッシュラインはキャッシュメモリ内から追い出されやすくなる。さらに、全てのキャッシュラインについて、読み出しと書き込みの比率が同じなら、アクセス回数が多いほどキャッシュメモリ内に留まりやすくなり、アクセス回数が少ないほどキャッシュメモリから追い出されやすくなる。また、アクセス回数が多くても書き込み回数が少なければキャッシュメモリから追い出されやすくなる。
【００７６】
以下、第２の実施の形態におけるキャッシュ制御について具体的に説明する。
【００７７】
図１１は、第２の実施の形態におけるキャッシュメモリ内のキャッシュタグメモリの構成を示す図である。図３と比較すると分かるとおり、図１１のキャッシュタグメモリ３７の各キャッシュラインCLは、基準情報として、修正アクセス頻度CAFを格納する。また、各キャッシュラインCLがアドレス情報ADDRESSとステータス情報STATEを有するのは、図３と同じである。
【００７８】
図１２は、第２の実施の形態におけるキャッシュ制御部３２によるキャッシュ制御のフローチャート図である。図１２のフローチャート図内の各処理も、キャッシュ制御部３２内のキャッシュ制御回路３３と置換基準生成回路３４の処理が含まれる。また、図１２において、第１の実施の形態の図８の処理と異なる処理は、工程S4_2、S5_2、S9_2、S11_2、S12_2である。
【００７９】
まず、キャッシュ制御部３２は、メモリアクセス命令がロード命令（読み出し命令）かストア命令（書き込み命令）かに応じて（S1）、それぞれ対応するリードカウンタ３４１またはライトカウンタ３４２を＋１インクリメントする（S2,S3）。
【００８０】
そして、重み値WVr=Dr/Er,WVw=Dw/Ewを更新すべきタイミングの場合（S4_2のYES）、置換基準生成回路３４が容量Dr,Dwを更新し、重み値WVr,WVwを更新する（S5_2）。この更新処理は、置換基準生成回路３４が実行する。重み値の生成方法は図５で説明したとおりである。また、この重み値を更新すべきタイミングは、第１の実施の形態での容量Dr,Dwを更新すべきタイミングと同じである。
【００８１】
次に、キャッシュ制御部３２は、メモリアクセス命令のアドレスに基づいてキャッシュヒットしたか否か判定する（S6）。キャッシュヒットした場合（S6のHIT）、キャッシュ制御部３２は、メモリアクセス命令がロード命令（読み出し命令）なら（S7のLOAD）、キャッシュメモリのデータを読み出し、CPUコアにデータを返信し（データ応答）（S8）、ヒットしたキャッシュラインのキャッシュタグ内の修正アクセス頻度CAFに重み値WVrを加算する（S9_2）。キャッシュヒットした場合（S6のHIT）、キャッシュ制御部３２は、メモリアクセス命令がストア命令（書き込み命令）なら（S7のSTORE）、キャッシュメモリに書き込みデータを書き込み（S10）、ヒットしたキャッシュラインのキャッシュタグ内の修正アクセス頻度CAFに重み値WVrを加算する（S11_2）。
【００８２】
このように、第２の実施の形態では、キャッシュメモリにアクセスされるたびに、アクセスされたキャッシュラインのタグの修正アクセス頻度CAFを増加する。増加する量は＋１ではなく、読み出しなら重み値WVr＝Dr/Er、書き込みなら重み値WVw＝Dw/Ewである。
【００８３】
一方、キャッシュミスした場合（S6のMISS）、キャッシュ制御部３２のキャッシュ置換制御回路３３２が、キャッシュラインの置換処理を実行する（S12_2）。
【００８４】
図１３は、第２の実施の形態におけるキャッシュラインの置換処理のフローチャート図である。図９の第１の実施の形態でのキャッシュライン置換処理とは、工程S122_2が異なり、それ以外は同じである。
【００８５】
図１３では、キャッシュライン置換制御回路３２は、キャッシュに空きがない場合（S121のNO）、キャッシュメモリの全てのキャッシュラインのうち、修正アクセス頻度CAFが最小のキャッシュラインを置換対象のキャッシュラインに選択する。
【００８６】
図１４は、第２の実施の形態における最適重み値探索テーブルの一例を示す図である。図１２の重み値更新処理S5_2は、図５のDr,Dw生成回路３４８と重み値生成回路３４９で算出できる。ただし、別の手段として、図１４の最適重み値探索テーブルを参照し、読み出し確率Er、書き込み確率Ew、読み出し及び書き込みレイテンシTr,Tw、ワーキングセット容量Mに基づいて、最適な重み値WVr,WVwを抽出するようにしてもよい。
【００８７】
図１４のテーブルは、横方向はErTr/EwTw＝x、縦方向はワーキングセット容量Mであり、両値ｘ、Mの組合せから、最適な重み値WVr:WVwを抽出することができる。
【００８８】
以上の通り、第２の実施の形態では、キャッシュ置換制御回路は、アクセス回数を重み値で修正した修正アクセス頻度に基づいて、LFU方式でキャッシュラインの置換制御を行う。そして、重み値WVr,WVwには、キャッシュミス時の平均メモリアクセス時間P1を最小にする目標の読み出し領域の容量Drと目標の書き込み領域の容量Dwが反映されている。その結果、キャッシュメモリ内のキャッシュラインは、目標とする容量Dr,Dwに近づくように置換制御される。それにより、キャッシュミス時のメインメモリアクセス時間P1を最小にすることができる。
【００８９】
［第３の実施の形態］
第３の実施の形態では、図２，図４に示されるとおり、キャッシュ制御部３３は、メモリアクセス命令がキャッシュヒットか否かを判定するキャッシュヒット判定回路３３１と、キャッシュミス発生時に、キャッシュメモリ内のキャッシュラインの置換制御を行うキャッシュライン置換制御回路３３２とを有する。さらに、キャッシュ制御部３３は、置換基準を生成する置換基準生成回路３４とを有する。
【００９０】
そして、置換基準生成回路３４は、第２の実施の形態と同様に、図５の回路により読み出し用重み値WVrと書き込み用重み値WVwとを生成する。
【００９１】
第３の実施の形態では、キャッシュライン置換制御回路３３２は、LRU方式で置換対象のキャッシュラインを選択する。そのため、キャッシュヒットした場合に、キャッシュ制御部３２は、キャッシュラインのタグの基準情報として、読み出し回数Arまたは書き込み回数Awをインクリメントし、キャッシュヒット時の時刻であるアクセス時刻を更新する。そして、キャッシュミス発生時に、キャッシュライン置換制御回路３３２は、第１に、全てのキャッシュラインについて、読み出し回数Arと書き込み回数Awから各キャッシュラインが読み出しが多いラインか書き込みが多いラインかを判定する。キャッシュライン置換制御回路３３２は、第２に、全てのキャッシュラインについて、キャッシュタグのアクセス時刻とキャッシュミス時の現在時刻との時間差DTを重み値WVrまたはWVwで除した修正時間差DT/WVr、DT/WVwが最も長いキャッシュラインを置換対象に選択する。いずれの重み値WVr、WVwで時間差DTを除算するかは、読み出し回数Ar,書き込み回数Awに基づいて判定した結果、そのキャッシュラインが読み出しが多いキャッシュラインか書き込みが多いキャッシュラインかの判定結果、に対応する重み値を選択する。
【００９２】
図１５は、第３の実施の形態におけるキャッシュメモリ内のキャッシュタグメモリの構成を示す図である。図３と比較すると分かるとおり、図１５のキャッシュタグメモリ３７の各キャッシュラインCLは、基準情報として、アクセス時刻（またはアクセス時のアクセス回数er+ew）と、キャッシュラインへの読み出し回数Arと書き込み回数Awとを格納する。
【００９３】
図１６は、第３の実施の形態におけるキャッシュ制御部３２によるキャッシュ制御のフローチャート図である。図１６のフローチャート図内の各処理も、キャッシュ制御部３２内のキャッシュ制御回路３３と置換基準生成回路３４の処理が含まれる。また、図１６において、第１の実施の形態の図８の処理と異なる処理は、工程S4_3、S5_3、S9_3、S11_3、S12_3である。図１６の工程S4_3、S5_3は、第２の実施の形態の図１２の工程S4_2、S5_2と同じである。
【００９４】
まず、キャッシュ制御部３２は、メモリアクセス命令がロード命令（読み出し命令）かストア命令（書き込み命令）かに応じて（S1）、それぞれ対応するリードカウンタ３４１またはライトカウンタ３４２を＋１インクリメントする（S2,S3）。
【００９５】
そして、重み値WVr=Dr/Er,WVw=Dw/Ewを更新すべきタイミングの場合（S4_3のYES）、置換基準生成回路３４が容量Dr,Dwを更新し、重み値WVr,WVwを更新する（S5_3）。この更新処理は、置換基準生成回路３４が実行する。重み値の生成方法は図５で説明したとおりである。また、この重み値を更新すべきタイミングは、第2の実施の形態での重み値WVr,WVwを更新すべきタイミングと同じである。
【００９６】
次に、キャッシュ制御部３２は、メモリアクセス命令のアドレスに基づいてキャッシュヒットしたか否か判定する（S6）。キャッシュヒットした場合（S6のHIT）、キャッシュ制御部３２は、メモリアクセス命令がロード命令（読み出し命令）なら（S7のLOAD）、キャッシュメモリのデータを読み出し、CPUコアにデータを返信し（データ応答）（S8）、ヒットしたキャッシュラインのキャッシュタグ内のリード回数Arを＋１増加し、アクセス時刻を上書きする（S9_3）。キャッシュヒットした場合（S6のHIT）、キャッシュ制御部３２は、メモリアクセス命令がストア命令（書き込み命令）なら（S7のSTORE）、キャッシュメモリに書き込みデータを書き込み（S10）、ヒットしたキャッシュラインのキャッシュタグ内のライト回数Awを＋１増加し、アクセス時刻を上書きする（S11_3）。
【００９７】
一方、キャッシュミスした場合（S6のMISS）、キャッシュ制御部３２のキャッシュ置換制御回路３３２が、キャッシュラインの置換処理を実行する（S12_3）。
【００９８】
図１７は、第３の実施の形態におけるキャッシュラインの置換処理のフローチャート図である。図９、図１３の第１、第２の実施の形態でのキャッシュライン置換処理とは、工程S122_3が異なり、それ以外は同じである。
【００９９】
図１７では、キャッシュライン置換制御回路３２は、キャッシュに空きがない場合（S121のNO）、キャッシュメモリの全てのキャッシュラインのうち、修正時間差DT/WVr、DT/WVwが最も長いキャッシュラインを置換対象に選択する（S122_3）。
【０１００】
この時、キャッシュライン置換制御回路は、キャッシュタグ内の読み出し回数Arと書き込み回数Awとからそのキャッシュラインが読み出し用ラインか書き込み用ラインかを判定する。判定基準は、例えばAr>Awなら読み出し用ライン、Ar<Awなら書き込み用と判定する。または、判定基準は、Ar>Aw+αなら読み出し用ライン、Ar<Aw+αなら書き込み用ラインと判定してもよい。一般的なプロセスでは、読み出し回数が書き込み回数より多い傾向にあるので、それを修正するためにα値を上記のように利用する。
【０１０１】
さらに、キャッシュライン置換制御回路は、キャッシュタグ内のアクセス時刻と現在時刻の時間差DTを算出し、修正時間差DT/WVr、DT/WVwを算出する。そして、全てのキャッシュラインのうち修正時間差が最長のキャッシュラインを置換対象に選択する。
【０１０２】
図１７のキャッシュラインの置換処理では、上記の工程S22_3以外は、図９，図１３の第１、第２の実施の形態と同じである。
【０１０３】
第３の実施の形態では、時刻に代えて、読み出しカウンタのカウンタ値erと書き込みカウンタのカウンタ値ewとを合計したメモリアクセス回数er+ewを利用しても良い。つまり、キャッシュ制御部は、キャッシュヒット時に、タグにアクセス時刻に代えてアクセス時のメモリアクセス回数er+ewを記録し、キャッシュミス時に、タグ内のアクセス時のメモリアクセス回数er+ewと、キャッシュミス時のメモリアクセス回数er+ewとの回数差を算出し、重み値WVr,WVwで除算した修正回数差を算出する。そして、キャッシュライン置換制御回路は、全てのキャッシュラインのうち修正回数差が最も大きいキャッシュラインを置換対象に選ぶ。
【０１０４】
上記のとおり、第３の実施の形態では、キャッシュミス時に、キャッシュライン置換制御回路が、各キャッシュラインの直前のアクセス時刻（またはメモリアクセス回数）と現在時刻（または現在のメモリアクセス回数）との時間差（または回数差）を、重み値で除して修正時間差（修正回数差）を求め、修正時間差（修正回数差）が最も長い（多い）キャッシュラインを置換対象に選択する。その結果、キャッシュメモリを目標の読み出し領域の容量Dr、目標の書き込み領域の容量Dwに制御することができる。
【０１０５】
［各種のタイミングチャート］
以下、本実施の形態を適用した場合の各種の動作をタイミングチャートで説明する。
【０１０６】
図１８は、CPU（演算処理装置）を有する情報処理装置が電源オンしてからアプリケーションが実行されるまでの状態遷移図である。まず、情報処理装置の電源が投入されると（P-ON）、BIOS(Basic IO System)が実行される（BIOS）。CPUによりBIOSが実行されることにより、メインメモリの初期テストがメモリ内のセルフテスト回路により行われる。このとき、メインメモリから読み出しと書き込みのレイテンシが読み取られる。さらに、IOデバイスの接続が確認され、ブートデバイスが選択される。
【０１０７】
次に、ブートデバイスの最初に実行する部分がブートストラップローダから実行されて、カーネルモジュールがメインメモリにロードされる。これによりOSに実行権限が移され（OS）、ここから、メインメモリは仮想化され、本実施の形態が実行可能になる。
【０１０８】
次に、ユーザのログインに応答して、ユーザモードになり、OSは、メインメモリのユーザ空間にアプリケーションプログラムをロードし実行する（APPLICATION）。アプリケーションプログラムは、演算処理、CPUレジスタへのアクセス、メインメモリアクセス、分岐、IOアクセスなどの命令が組み合わせられている。本実施の形態は、メインメモリアクセスのときに実行される。
【０１０９】
メモリアクセスは、既に説明したとおりであり、図１８にも示されるように、キャッシュ制御部は、キャッシュ制御部がキャッシュヒット判定を行い、読み出しカウンタまたは書き込みカウンタをカウントアップし、重み値の更新タイミングで更新処理を行う。キャッシュミスした場合は、メインメモリへのアクセスが発生し、キャッシュラインの置換処理が行われ、新たなキャッシュエントリが登録される。また、キャッシュヒットの場合は、修正アクセス頻度を更新し、キャッシュメモリのデータにアクセスする。上記の説明は、修正アクセス頻度を利用する第２の実施の形態の場合の説明である。
【０１１０】
図１９は、アドレスAへの読み出し命令でキャッシュミスしたときの動作を示すタイミングチャート図である。まず、CPUコアが読み出し命令(Read)をアドレスAと共に発行する。キャッシュ制御部がキャッシュミスを判定すると、メモリアクセスコントローラを介して、メインメモリであるDIMMモジュールにリードアクセスを実行し、アドレスAのデータが出力される。キャッシュ制御部は、読み出しカウンタのカウント値erをer+1にインクリメントする。また、キャッシュ制御部は、メインメモリにアクセスして取得したデータを、置換されたキャッシュラインに登録するとともに、そのキャッシュタグのステータス情報をE状態に、修正アクセス頻度CAFを０にそれぞれ初期化する。
【０１１１】
図２０は、アドレスAへの読み出し命令でキャッシュヒットしたときの動作を示すタイミングチャート図である。CPUコアがアドレスAへの読み出し命令を発行し、キャッシュ制御部がキャッシュヒットを判定しキャッシュメモリのデータにアクセスする。この場合、キャッシュ制御部は、読み出しカウンタのカウント値erをer+1にインクリメントし、アクセスされたキャッシュラインのタグの修正アクセス頻度CAFに読み出し用重み値WVrを加算する。
【０１１２】
図２１は、アドレスAへの書き込み命令でキャッシュミスしたときの動作を示すタイミングチャート図である。キャッシュ制御部がキャッシュミスを判定し、書き込みカウンタのカウンタ値ewをインクリメントするとともに、キャッシュラインを置き換えて新たにエントリされたキャッシュラインのタグのステータス情報と修正アクセス頻度をE状態と０に初期化する。さらに、キャッシュ制御部は、新たなキャッシュラインにデータを書き込み、メインメモリにアクセスしてデータを書き込む。
【０１１３】
図２２は、アドレスAへの書き込み命令でキャッシュヒットしたときの動作を示すタイミングチャート図である。キャッシュ制御部がキャッシュヒットを判定し、書き込みカウンタのカウンタ値ewをインクリメントするとともに、キャッシュヒットしたキャッシュラインにデータを書き込み、そのタグのステータス情報をM状態に変更し、修正アクセス頻度CAFに重み値WVwを加算する。
【０１１４】
図２３は、ワーキングセット容量Mの更新処理を示すタイミングチャート図である。CPUコアがページフォルト命令を発行すると、メインメモリ内のワーキングセット領域の容量Mが増加され、ページテーブルが更新される。そして、キャッシュ制御部が、メモリコントローラから更新されたページテーブルを読み出し、ワーキングセット領域の容量レジスタに記録する。その結果、容量Mが４８バイトから５２バイトに増加している。
【０１１５】
図２４は、重み値の更新処理を示す図である。この例では、前述したとおり、読み出しカウンタのカウント値erと書き込みカウンタのカウント値ewの合計er+ewが２５６の倍数になると、メモリ制御部は、レジスタ群のパラメータTr,Tw,M,er,ewを読み出し、最適重み値テーブルを探索して最適な重み値を抽出し、重み値をWVr,WVw新しい重み値WVr',WVw'に更新する。
【０１１６】
図２５は、キャッシュミス時にクリーンなキャッシュラインを追い出す処理を示すタイミングチャート図である。キャッシュミス時に二次キャッシュメモリに空きがない場合、キャッシュ制御部は、アドレスA,B,Cのキャッシュラインの修正アクセス頻度CAFのうち最小の修正アクセス頻度CAF_Cのキャッシュライン（アドレスC）を追い出す。そのとき、図２５中のアドレスCのキャッシュラインのステータス情報がE,S状態であり、メインメモリのデータから変更されていない（M状態でない）クリーンな状態である。よって、メモリ制御部は、アドレスCのキャッシュラインのタグのステータス情報をI状態（Invalid）にして解放する。キャッシュライン内のデータはメインメモリに書き戻すことなく破棄される。
【０１１７】
図２６は、キャッシュミス時にダーティなキャッシュラインを追い出す処理を示すタイミングチャート図である。キャッシュミス時に二次キャッシュメモリに空きがない場合、キャッシュ制御部は、アドレスA,B,Cのキャッシュラインの修正アクセス頻度CAFのうち最小の修正アクセス頻度CAF_Bのキャッシュライン（アドレスB）を追い出す。そのとき、図２６中のアドレスBのキャッシュラインのステータス情報がM状態であり、メインメモリのデータから変更されているダーティな状態である。よって、メモリ制御部は、アドレスBのキャッシュラインのタグのステータス情報をI状態（Invalid）にして解放し、ライトバックを発行する。それに応答して、メインメモリのアドレスBに対してキャッシュメモリ内のデータを書き戻すライトバックが行われる。
【０１１８】
以上の通り、本実施の形態によれば、キャッシュミスしたときのペナルティであるメインメモリへのアクセス時間を最小にして演算処理装置の処理効率を向上することができる。
【０１１９】
以上の実施の形態をまとめると，次の付記のとおりである。
【０１２０】
（付記１）
主記憶装置にアクセス可能な演算処理装置において、
メモリアクセス命令を実行する演算処理部と、
前記主記憶装置が記憶するデータの一部を保持するキャッシュメモリと、
前記メモリアクセス命令に応答して前記キャッシュメモリを制御するキャッシュ制御部とを有し、
前記キャッシュ制御部は、
前記演算処理部が実行したメモリアクセス命令に基づき、前記キャッシュメモリ部におけるキャッシュヒット又はキャッシュミスを判定するキャッシュヒット判定部と、
前記演算処理部が実行したメモリアクセス命令が読み出し命令である場合、読み出し命令の計数値を増分させるリード計数部と、
前記演算処理部が実行したメモリアクセス命令が書き込み命令である場合、書き込み命令の計数値を増分させるライト計数部と、
前記リード計数部が計数した読み出し命令の計数値と、前記ライト計数部が計数した書き込み命令の計数値とに基づき、前記キャッシュミス判定部が判定したキャッシュミスに応答して前記主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成する置換基準生成部と、
前記目標の読み出し領域の容量と前記目標の書き込み領域の容量とに基づいて、前記キャッシュメモリの領域の置換を制御する置換制御部とを有する、演算処理装置。
【０１２１】
（付記２）
前記置換基準生成部は、
前記リード計数部が計数した読み出し命令の計数値に基づき、前記メモリアクセス命令のうち読み出し命令の発生確率である読み出し確率を算出するとともに、前記ライト計数部が計数した書き込み命令の計数値に基づき、前記メモリアクセス命令のうち書き込み命令の発生確率である書き込み確率を算出し、前記主記憶装置の読み出し時間と前記主記憶装置の書き込み時間と算出した前記読み出し確率と算出した前記書き込み確率に基づき、前記キャッシュヒット判定部が判定したキャッシュミスに応答して前記主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成する、付記１に記載の演算処理装置。
【０１２２】
（付記３）
前記置換基準生成部は、前記目標の読み出し領域の容量と、前記目標の書き込み領域の容量と、前記読み出し命令の計数値に基づく読み出し確率と前記書き込み命令の計数値に基づく書き込み確率とに基づいて、読み出し重み値と書き込み重み値とを生成し、
前記キャッシュ制御部は、キャッシュヒットするたびに、前記キャッシュヒットしたキャッシュラインの修正アクセス頻度に前記読み出し重み値または前記書き込み重み値を命令の種類に応じて加算し、
前記置換制御部は、キャッシュミスした場合、前記修正アクセス頻度が最小のキャッシュラインを置換対象に選択する、付記１に記載の演算処理装置。
【０１２３】
（付記４）
前記置換基準生成部は、前記目標の読み出し領域の容量と、前記目標の書き込み領域の容量と、前記読み出し命令の計数値に基づく読み出し確率と前記書き込み命令の計数値に基づく書き込み確率とに基づいて、読み出し重み値と書き込み重み値とを生成し、
前記キャッシュ制御部は、キャッシュヒットするたびに、前記キャッシュヒットしたキャッシュラインにアクセス時刻を記録し、
前記置換制御部は、キャッシュミスした場合、前記アクセス時刻とキャッシュミス時刻との時間差を前記読み出し重み値または書き込み重み値で除算した修正時間差が、最長のキャッシュラインを置換対象に選択する、付記１に記載の演算処理装置。
【０１２４】
（付記５）
前記置換基準生成部は、前記目標の読み出し領域の容量を前記読み出し確率で除して前記読み出し重み値を生成し、前記目標の書き込み領域の容量を前記書き込み確率で除して前記書き込み重み値を生成する、付記３または４に記載の演算処理装置。
【０１２５】
（付記６）
前記置換基準生成部は、さらに、前記キャッシュメモリ内の目標の読み出し領域と目標の書き込み領域それぞれのキャッシュミス確率とに基づいて、目標の読み出し領域の容量及び目標の書き込み領域の容量を生成し、
前記キャッシュミス確率は、前記主記憶装置内のワーキングセット領域の容量と、前記キャッシュメモリの目標の読み出し領域の容量と書き込み領域の容量とに基づいて算出される、付記２、３または４のいずれかに記載の演算処理装置。
【０１２６】
（付記７）
前記置換制御部は、前記キャッシュラインを置換したとき、新たなキャッシュラインの前記修正アクセス頻度をゼロに初期化する、付記３に記載の演算処理装置。
【０１２７】
（付記８）
前記キャッシュ制御部は、前記演算処理部が処理対象のプロセスをリセットしたとき、前記読み出し確率と、前記書き込み確率と、前記キャッシュミス確率とをリセットし、
前記置換基準生成部は、前記プロセスの処理期間より短い頻度で、前記目標の読み出し領域の容量と前記目標の読み出し領域の容量と、前記読み出し重み値と前記書き込み重み値とを再生成する、付記３または４に記載の演算処理装置。
【０１２８】
（付記９）
前記置換基準生成部は、前記読み出し命令の計数値に基づく読み出し確率及び前記書き込み命令の計数値に基づく書き込み確率と、前記読み出し時間及び書き込み時間と、前記読み出し命令のキャッシュミス確率及び前記書き込み命令のキャッシュミス確率とをそれぞれ乗算し当該乗算値を加算することで、前記平均メモリアクセス時間を生成する、付記２，３または４のいずれかに記載の演算処理装置。
【０１２９】
（付記１０）
前記キャッシュメモリは、キャッシュタグメモリとキャッシュデータメモリとを有し、
前記キャッシュタグメモリの各キャッシュラインがそれぞれの修正アクセス頻度を記憶する、付記３に記載の演算処理装置。
【０１３０】
（付記１１）
前記主記憶装置の読み出し時間と前記主記憶装置の書き込み時間とが異なる、付記１〜１０のいずれかに記載の演算処理装置。
【０１３１】
（付記１２）
前記主記憶装置の書き込み時間が前記主記憶装置の読み出し時間より長い、付記１１に記載の演算処理装置。
【０１３２】
（付記１３）
メモリアクセス命令を実行する演算処理部と、キャッシュメモリと、前記メモリアクセス命令に応答して前記キャッシュメモリを制御するキャッシュ制御部とを有するとともに、主記憶装置にアクセス可能な演算処理装置の制御方法において、
前記キャッシュ制御部が有するキャッシュヒット判定部が、前記メモリアクセス命令がキャッシュヒットか否かを判定し、
前記キャッシュ制御部が有するリード計数部が、前記演算処理部が実行したメモリアクセス命令が読み出し命令である場合、読み出し命令の計数値を増分し、
前記キャッシュ制御部が有するライト計数部が、前記演算処理部が実行したメモリアクセス命令が書き込み命令である場合、書き込み命令の計数値を増分し、
前記キャッシュ制御部が有するキャッシュヒット判定部が、前記演算処理部が実行したメモリアクセス命令に基づき、前記キャッシュメモリ部におけるキャッシュヒット又はキャッシュミスを判定し、
前記キャッシュ制御部が有する置換基準生成部が、前記リード計数部が計数した読み出し命令の計数値と、前記ライト計数部が計数した書き込み命令の計数値とに基づき、前記キャッシュヒット判定部が判定したキャッシュミスに応答して前記主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成し、
前記キャッシュ制御部が有する置換制御部が、前記目標の読み出し領域の容量と前記目標の書き込み領域の容量とに基づいて、前記キャッシュメモリの領域の置換を制御する、演算処理装置の制御方法。
【０１３３】
（付記１４）
前記置換基準生成部は、
前記リード計数部が計数した読み出し命令の計数値に基づき、前記メモリアクセス命令のうち読み出し命令の発生確率である読み出し確率を算出するとともに、前記ライト計数部が計数した書き込み命令の計数値に基づき、前記メモリアクセス命令のうち書き込み命令の発生確率である書き込み確率を算出し、前記主記憶装置の読み出し時間と前記主記憶装置の書き込み時間と算出した前記読み出し確率と算出した前記書き込み確率に基づき、前記キャッシュヒット判定部が判定したキャッシュミスに応答して前記主記憶装置へのアクセスに要する平均メモリアクセス時間を最小にする目標の読み出し領域の容量及び目標の書き込み領域の容量を生成する、付記１３に記載の演算処理装置の制御方法。
【０１３４】
（付記１５）
前記キャッシュ制御部は、さらに、
前記目標の読み出し領域の容量と、前記目標の書き込み領域の容量と、前記読み出し命令の計数値に基づく読み出し確率と前記書き込み命令の計数値に基づく書き込み確率とに基づいて、読み出し重み値と書き込み重み値とを生成し、
キャッシュヒットするたびに、前記キャッシュヒットしたキャッシュラインの修正アクセス頻度に前記読み出し重み値または前記書き込み重み値を命令の種類に応じて加算し、
前記置換制御は、前記修正アクセス頻度が最小のキャッシュラインを置換対象に選択する、付記１３に記載の演算処理装置の制御方法。
【符号の説明】
【０１３５】
１０：演算処理装置（CPUチップ）
１２：メインメモリ
２０：CPUコア
３０：キャッシュ
３２：キャッシュ制御部
３３：キャッシュ制御回路
３３１：キャッシュヒット判定回路
３３２：キャッシュライン置換制御回路
３４：置換基準生成回路
３５：キャッシュメモリ
35_r：読み出しが多いキャッシュ領域
35_w：書き込みが多いキャッシュ領域
P:平均メモリアクセス時間
er:読み出し回数
ew:書き込み回数
Er：読み出し確率（er/(er+ew)またはN* er/(er+ew)）
Ew：書き込み確率（ew/(er+ew) またはN* ew/(er+ew)）
Tr:読み出しレイテンシ（メインメモリの読み出しに要する時間）
Tw:書き込みレイテンシ（メインメモリの書き込みに要する時間）
TCr:読み出しキャッシュ応答時間（読み出し命令でキャッシュヒットしたときにキャッシュデータのコアへの転送時間）
TCw:書き込みキャッシュ上書き時間（書き込み命令でキャッシュヒットしたときにキャッシュデータを書き換える転送時間） 
Hr:読み出しキャッシュミス確率（読み出し命令でキャッシュミスする確率）
Hw:書き込みキャッシュミス確率（書き込み命令でキャッシュミスする確率）
Dr:目標の読み出し領域の容量（キャッシュメモリ内の読み出し命令で多くアクセスされるキャッシュラインのトータル容量）
Dw:目標の書き込み領域の容量（キャッシュメモリ内の書き込み命令で多くアクセスされるキャッシュラインのトータル容量）
M:ワーキングセット容量（メインメモリ内のワーキングセット（working set）の容量）
c:キャッシュライン容量（キャッシュメモリ内の１つのキャッシュラインの容量）
WVr＝Dr/Er:読み出し重み値（読み出し回数を修正する重み値）
WVw＝Dw/Ew:書き込み重み値（書き込み回数を修正する重み値）
CAF＝er*WVr+ ew*WVw：修正アクセス頻度または回数（メモリアクセス命令がキャッシュラインにアクセスした回数を重み値で修正した回数）
【図１】
2016170682.tif 000003
【図２】
2016170682.tif 000004
【図３】
2016170682.tif 000005
【図４】
2016170682.tif 000006
【図５】
2016170682.tif 000007
【図６】
2016170682.tif 000008
【図７】
2016170682.tif 000009
【図８】
2016170682.tif 000010
【図９】
2016170682.tif 000011
【図１０】
2016170682.tif 000012
【図１１】
2016170682.tif 000013
【図１２】
2016170682.tif 000014
【図１３】
2016170682.tif 000015
【図１４】
2016170682.tif 000016
【図１５】
2016170682.tif 000017
【図１６】
2016170682.tif 000018
【図１７】
2016170682.tif 000019
【図１８】
2016170682.tif 000020
【図１９】
2016170682.tif 000021
【図２０】
2016170682.tif 000022
【図２１】
2016170682.tif 000023
【図２２】
2016170682.tif 000024
【図２３】
2016170682.tif 000025
【図２４】
2016170682.tif 000026
【図２５】
2016170682.tif 000027
【図２６】
2016170682.tif 000028