(57)【要約】【課題】すでに不要となったデータもつキャッシュラインを優先的にリフィルするキャッシュライン選択方法を提供すること【解決手段】実行中のプログラムにおけるサブルーチンの呼び出し情報であるコールスタックの情報をＣＰＵ３０から受け付ける。キャッシュライン選択処理部４０は、コールスタックの情報を参照することにより、以後のプログラムの実行において参照されることがないデータを保持するキャッシュラインを選択し、前記キャッシュラインを優先的に入れ替え対象とする。【選択図】図１
2011022746.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュメモリにおけるデータの管理の単位であるキャッシュラインの入れ替え方法であって、
実行中のプログラムにおけるサブルーチンの呼び出し情報であるコールスタックの情報を参照することにより、以後のプログラムの実行において参照されることがないデータを保持するキャッシュラインを対象キャッシュラインとして選択し、前記対象キャッシュラインを優先的に入れ替え対象とするキャッシュライン入れ替え方法。
【請求項２】
前記キャッシュラインの選択の際に、
前記コールスタックの情報を格納するスタック領域の開始アドレスおよび終了アドレスと、前記キャッシュラインに保持されたデータのアドレス情報と、を比較し、
前記キャッシュラインに保持されたデータのアドレスの値が前記スタック領域内に存在し、前記キャッシュラインに保持されたデータのアドレスの値が前記スタックポインタの値よりも低い値を持つ前記キャッシュラインを前記対象キャッシュラインとして選択する請求項１に記載のキャッシュライン選択方法。
【請求項３】
作業スタック位置として、前記コールスタックのスタックフレーム解放時に、前記スタックポインタの値を記憶し、
最終最上スタック位置として、前記コールスタックのスタックフレーム確保時に、前記作業用スタック位置と等しい値を設定した値を記憶し、
最終最上スタック操作回数として、前記コールスタックのスタックフレーム確保時に、最終最下スタック操作回数に１を加算した値を設定した値を記憶し、
前記最終最下スタック操作回数として、前記コールスタックのスタックフレーム解放時に、前記最終最上スタック操作回数と等しい値を設定した値を記憶し、
前記キャッシュラインに保持されたデータが前記スタック領域内に存在し、前記キャッシュラインに保持されたデータのアドレスの値が前記スタックポインタの値よりも高い、または等しい値であり、前記スタック操作回数と前記最終最上スタック操作回数との差が０ではなく、かつ前記キャッシュラインのアドレスが前記最終最上スタック位置よりも低い値を持つ前記キャッシュラインを前記対象キャッシュラインとして選択する請求項２に記載のキャッシュライン入れ替え方法。
【請求項４】
作業スタック位置として、前記コールスタックのスタックフレーム解放時に、前記スタックポインタの値を記憶し、
最終最上スタック位置として、前記コールスタックのスタックフレーム確保時に、前記作業用スタック位置と等しい値を設定した値を記憶し、
最終最上スタック操作回数として、前記コールスタックのスタックフレーム確保時に、最終最下スタック操作回数に１を加算した値を設定した値を記憶し、
前記最終最下スタック操作回数として、前記コールスタックのスタックフレーム解放時に、前記最終最上スタック操作回数と等しい値を設定した値を記憶し、
残存最上スタック位置として、前記コールスタックのスタックフレーム確保時に、実行中のプログラムの開始時から現在の実行時までの範囲において、前記範囲の前半のプロセス実行時に格納されたキャッシュラインのデータ数が前記範囲の後半のプロセス実行時に格納されたキャッシュラインのデータ数以上となる時点の前記スタックポインタの値を記憶し、
残存ライン数として、前記最上スタック位置を設定した範囲以前に、前記スタック領域に格納したキャッシュラインの数を設定した値を記憶し、
留保ライン数として、前記最上スタック位置を設定した範囲以後に、前記スタック領域に格納したキャッシュラインの数を設定した値を記憶し、
残存最上スタック操作回数として、前記残存最上スタック位置が設定された際に、前記最終最上スタック操作回数と等しい値を設定した値を記憶し、
前記キャッシュラインに保持されたデータが前記スタック領域内に存在し、前記キャッシュラインに保持されたデータのアドレスの値が前記スタックポインタの値よりも高い、または等しい値であり、前記スタック操作回数が前記残存最上スタック操作回数よりも小さく、かつ前記キャッシュラインのアドレスが前記残存最上スタック位置よりも低い値を持つ前記キャッシュラインを前記対象キャッシュラインとして選択する請求項２に記載のキャッシュライン入れ替え方法。
【請求項５】
作業スタック位置として、前記スタック領域の解放時に、前記スタックポインタの値を記憶し、
最終最上スタック操作回数として、前記コールスタックのスタックフレーム確保時に、最終最下スタック操作回数に１を加算した値を設定した値を記憶し、
最終最下スタック操作回数として、前記コールスタックのスタックフレーム解放時に、前記最終最上スタック操作回数と等しい値を設定した値を記憶し、
残存最上スタック位置として、前記コールスタックのスタックフレーム確保時に、実行中のプログラムの開始時から現在の実行時までの範囲において、前記範囲の前半のプロセス実行時に格納されたキャッシュラインのデータ数が前記範囲の後半のプロセス実行時に格納されたキャッシュラインのデータ数以上となる時点の前記スタックポインタの値を記憶し、
残存ライン数として、前記最上スタック位置を設定した範囲以前に、前記スタック領域に格納したキャッシュラインの数を設定した値を記憶し、
留保ライン数として、前記最上スタック位置を設定した範囲以後に、前記スタック領域に格納したキャッシュラインの数を設定した値を記憶し、
前記キャッシュラインは、キャッシュライン内に格納したデータが前記留保ライン数にカウントされているか否かを示す留保ラインフラグを備え、
前記キャッシュラインに保持されたデータが前記スタック領域内に存在し、前記キャッシュラインに保持されたデータのアドレスの値が前記スタックポインタの値よりも高い、または等しい値であり、
前記キャッシュラインのアドレスが前記残存最上スタック位置よりも低い値を持ち、前記キャッシュライン内の前記留保フラグが前記留保ライン数にカウントされていないことを表す値である前記キャッシュラインを前記対象キャッシュラインとして選択する請求項２に記載のキャッシュライン入れ替え方法。
【請求項６】
選択された前記キャッシュラインの中から、前記キャッシュラインに保持されたデータへのアクセス状況に基づいて入れ替えを行うキャッシュラインを決定する請求項２から請求項５のいずれか一に記載のキャッシュライン選択方法。
【請求項７】
前記アクセス状況はＬＲＵ(Least Recently Used)であることを特徴とする請求項６に記載のキャッシュライン入れ替え方法。
【請求項８】
実行中のプログラムにおけるサブルーチンの呼び出し情報であるコールスタックの情報をＣＰＵ（Central Processing Unit）から受け付け、キャッシュメモリ内のデータの管理の単位であるキャッシュラインの情報を取得し、前記コールスタックの情報と、前記キャッシュラインの情報とに基づき、以後のプログラム実行において参照されることがないデータを保持するキャッシュラインを選択するキャッシュライン選択処理部、を備えるキャッシュ選択処理装置。
【請求項９】
請求項８に記載のキャッシュ選択処理装置と、キャッシュメモリと、を備えるキャッシュ装置。
【請求項１０】
請求項９に記載のキャッシュ装置を備えるＣＰＵ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はキャッシュメモリにおけるキャッシュラインの入れ替え方法に関する。
【背景技術】
【０００２】
キャッシュメモリは、小容量の記憶装置で構成されるため、主記憶装置よりも記憶できるデータ容量が少ない。しかし、キャッシュメモリへはデータに拘束にアクセスすることができる。そのため、頻繁に参照するデータをキャッシュメモリに格納しておくことにより、ＣＰＵ（Central Processing Unit: 中央演算処理装置）からメモリへのアクセスタイムを短縮することができ、システム性能を向上させることができる。キャッシュメモリは、データをラインと呼ばれる（以後、キャッシュラインと表現する。）ある程度まとまった単位で管理し、必要に応じて保持するキャッシュラインのデータを入れ替える（以下、キャッシュラインのデータの入れ替えを、キャッシュラインをリフィルする、という。）。
【０００３】
ここで、非特許文献１に記載のキャッシュラインの入れ替え方法について説明する。図３３の構成図は一般的なＬＲＵ（Least Recently Used）アルゴリズムを用いたキャッシュラインの入れ替えを行うキャッシュを含むキャッシュメモリシステムの基本構成を示す図である。図３３には、キャッシュ１０と、メモリ２０と、ＣＰＵ３０と、キャッシュライン選択処理部４０と、が示されている。
【０００４】
キャッシュ１０は、キャッシュライン１０１と、キャッシュライン１０２と、ＬＲＵ情報テーブル１０３と、を備える。なお、キャッシュラインサイズは任意の大きさでよく、複数のキャッシュラインを有することができる。
【０００５】
キャッシュライン１０１は、メモリアクセス先のアドレス情報１１１と、データ１１２との組を複数保持する。同様に、キャッシュライン１０２は、メモリアクセス先のアドレス情報１２１と、データ１２２との組を複数保持する。ＬＲＵ情報テーブル１０３は、キャッシュラインのリフィルにおいて、選択対象毎のＬＲＵ情報１３１を保持する。ＬＲＵ情報１３１は、リフィルの対象となるキャッシュラインの中で、データアクセスがされてから最も時間が経過しているキャッシュラインを示す。
【０００６】
メモリ２０は、実行されるプログラム、その他のデータを格納するＲＡＭ（Random Access Memory）等の記憶装置である。ＣＰＵ３０は、制御プログラムに基づいて、このシステム内の各種処理を実行する中央制御装置である。
【０００７】
キャッシュライン選択処理部４０は、キャッシュラインのリフィルの必要が生じた際に、リフィル対象とするキャッシュラインを選択する処理部である。キャッシュライン選択処理部４０は、ＬＲＵ情報１３１に基づいて、リフィル対象となるキャッシュラインを選択する。
【０００８】
キャッシュ２０のデータ格納構造について説明する。図３４は、２Ｗａｙのセット・アソシアティブ方式のデータ格納構造をもつキャッシュの図である。図示したデータ格納構造では、アドレス0x10*n+N (nは0以上の整数、N は0x0から0xf)のデータが、２つあるキャッシュラインのアドレスNに対応しており、ここにデータを格納する。
【０００９】
ＣＰＵ３０は、プログラムカウンタにより命令を順次実行し、命令にメモリアクセスがある場合、以下の動作を行う。
【００１０】
アクセスするアドレスに対応するキャッシュラインが、キャッシュテーブルに存在する場合、そのキャッシュラインに格納されたデータを用いる。アクセスするアドレスに対応するキャッシュラインが、キャッシュテーブルに存在しない場合、メモリアクセス先のアドレスからキャッシュラインのリフィルに用いる選択対象のＬＲＵ情報を取得する。キャッシュライン選択処理部４０は、取得したＬＲＵ情報に基づき、アクセスが最も古いキャッシュラインを選択する。キャッシュライン選択処理部４０は、選択したキャッシュラインのアドレス情報と、データと、を更新する。
【００１１】
ＬＲＵ情報テーブル１０３は、アクセスするアドレスに対応するキャッシュラインの情報から、キャッシュラインに対応するＬＲＵ情報１３１に対して最後に利用したキャッシュラインの情報を反映する。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】John L. Hennessy, David A. Patterson著、コンピュータの構成と設計―ハードウエアとソフトウエアのインタフェース  第３版（上）（下）ISBN-13: 978-4822282660、ISBN-13: 978-4822282677
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、非特許文献１のキャッシュラインの入れ替え方法では、リフィルの対象とすべきキャッシュラインの選択を誤り、キャッシュミスを起こす場合があるという問題がある。以下に、非特許文献１のキャッシュラインの入れ替え方法では、キャッシュミスを引き起こす具体例を説明する。
【００１４】
図３５は、以後の説明に用いる実行プログラムを、（簡易的な記載をした）Ｃ言語のソースプログラム（Ｃソース）と、アセンブリコード（asmソース）と、を用いて示す図である。また、図３５には、命令がロードされるアドレス情報（アドレス）も図示している。図３６は、asmソース内の命令動作を記述したものである。図３５に示したasmソースは、図３５に示したＣソースの動作を図３６に示す命令で記述したものである。図３７は、図３５に示したasmソースの命令を実行した際の実行トレース結果を示す図である。図３７の実行トレース結果は、アドレスで参照されるasmソースの命令を実行した際の、sp（スタックポインタ）の値と、キャッシュラインの内容と、ＬＲＵ情報と、を示している。図３７内の、「キャッシュライン１」、「キャッシュライン２」は、そのＳｔｅｐでのキャッシュラインに設定されているデータと、アドレスと、を示す。キャッシュラインをリフィルする際の、キャッシュラインの選択にはＬＲＵ情報を利用する。
【００１５】
非特許文献１に記載のＬＲＵ情報を利用したキャッシュラインの選択では、最後にアクセスしたデータをキャッシュラインに残す。そのため、図３５に示すようなプログラムのケースでは、図３７のＳｔｅｐ８において、最後にアクセスしたデータ（ｃ）をキャッシュラインに残してしまう。
【００１６】
以下に、図３７の実行トレースの詳細を説明する。以下の例では、コールスタックの開始位置（スタック開始位置）を0x8000、コールスタックの終了位置（スタック終了位置）を0x7000、スタックポインタの初期値を0x80000とする。また、ＬＲＵ情報１３１の初期値は、「キャッシュライン１」を指すものとする。変数に割り当てられるアドレスにより、変数a,b,cはキャッシュライン上で同じ領域を示すものとする。
【００１７】
Ｓｔｅｐ１では、関数Func1のスタックフレーム確保のため、sub命令でspの値は0x7fe0となる。また、変数aのアドレスは0x7ff0、変数bのアドレスは0x7fe0に割り当てるものとする。
【００１８】
Ｓｔｅｐ２では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、ＬＲＵ情報が指すキャッシュラインが「キャッシュライン１（ライン１）」であるため、キャッシュライン１に変数aのデータと、アドレスと、を設定する。また、ＬＲＵ情報１３１は、アクセスがされていない「キャッシュライン２（ライン２）」に変更される。Ｓｔｅｐ３では、関数の呼び出し命令のため、関数Func2の処理へ分岐する。
【００１９】
Ｓｔｅｐ４では、関数Func2のスタックフレーム確保のため、sub命令によってspの値は、0x7fc0になる。また、変数cのアドレスは、0x7fd0に割り当てるものとする。Ｓｔｅｐ５では、変数cを利用するため、アドレス0x7fd0のデータをロードする。その際に、ＬＲＵ情報１３１が指すキャッシュラインが「キャッシュライン２（ライン２）」であるため、キャッシュライン２に変数cのデータと、アドレスと、を設定する。また、ＬＲＵ情報は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン１（ライン１）」に変更される。
【００２０】
Ｓｔｅｐ６では、関数Func2のスタックフレーム解放のため、add命令によりspの値は、0x7fe0となる。Ｓｔｅｐ７では、return命令により、関数Func1に処理が戻る。
【００２１】
Ｓｔｅｐ８では、変数bを利用するため、アドレス0x7fe0のデータをロードする。その際、キャッシュライン１およびキャッシュライン２には、変数bのデータが存在しないため、ＬＲＵ情報１３１が指すキャッシュライン１をリフィルして、変数bのデータと、アドレスと、を設定する。また、ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン２（ライン２）」に変更される。
【００２２】
Ｓｔｅｐ９では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際、キャッシュライン１およびキャッシュライン２には、変数aのデータが存在しないため、ＬＲＵ情報１３１が指すキャッシュライン２をリフィルして、変数aのデータと、アドレスと、を設定する。また、ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン１（ライン１）」に変更される。
【００２３】
Ｓｔｅｐ１０では、関数Func1のスタックフレーム解放のため、add命令によりspの値は、0x8000となる。Ｓｔｅｐ１１では、プログラムの実行を終了する。
【００２４】
Ｓｔｅｐ８で変数bを利用する際には、関数Func2から処理がFunc1に戻っているため、以降の処理で変数cを利用することはない。しかし、非特許文献１に記載のＬＲＵ情報を利用したキャッシュラインの選択では、Ｓｔｅｐ８において、ＬＲＵ情報１３１が指すキャッシュライン１（変数a）を選択してリフィルする。そのため、Ｓｔｅｐ９で変数aを利用する時点でキャッシュミスとなる。すなわち、ＬＲＵ情報のみに基づいてリフィルするキャッシュラインの選択を行っているため、すでに不要となったデータもつキャッシュラインをリフィルしないという問題点がある。
【課題を解決するための手段】
【００２５】
本発明にかかるキャッシュライン入れ替え方法の一態様は、キャッシュメモリにおけるデータの管理の単位であるキャッシュラインの入れ替え方法であって、実行中のプログラムにおけるサブルーチンの呼び出し情報であるコールスタックの情報を参照することにより、以後のプログラムの実行において参照されることがないデータを保持するキャッシュラインである対象キャッシュラインとして選択し、前記対象キャッシュラインを優先的に入れ替え対象とするものである。
【００２６】
本発明は、サブルーチンの呼び出し情報であるコールスタックの情報を参照することにより、ＬＲＵ情報を用いたキャッシュの選択に優先して、すでに不要となったデータを持つキャッシュラインを選択することができる。
【発明の効果】
【００２７】
本発明により、すでに不要となったデータもつキャッシュラインを優先的にリフィルするキャッシュライン入れ替え方法を提供することができる。
【図面の簡単な説明】
【００２８】
【図１】実施の形態１にかかるキャッシュメモリシステムの構成図である。
【図２】実施の形態１にかかるプログラム開始処理のフローチャートである。
【図３】実施の形態１にかかるキャッシュラインのリフィル手順の図である。
【図４】実施の形態１にかかるキャッシュのリフィル手順を利用した場合の、プログラムの実行トレース結果の図である。
【図５】実施の形態２において、説明に利用するプログラムの図である。
【図６】実施の形態２において、プログラムの実行内で注目するspの値を示す図である。
【図７】実施の形態２にかかるキャッシュメモリシステムの構成図である。
【図８】実施の形態２にかかるキャッシュの構成で追加された情報の初期値を説明する図である。
【図９】実施の形態２にかかるプログラム開始処理のフローチャートである。
【図１０】実施の形態２にかかるスタックフレーム確保・解放時の処理のフローチャートである。
【図１１】実施の形態２にかかるキャッシュラインのリフィル手順の図である。
【図１２】実施の形態２にかかるキャッシュのリフィル手順を利用した場合の、プログラムの実行トレース結果の図である。
【図１３】実施の形態２にかかるspの遷移を表す図である。
【図１４】実施の形態２、実施の形態３の説明に利用するプログラムの図である。
【図１５】実施の形態３において、プログラムの実行内で注目するspの値を示す図である。
【図１６】実施の形態３において、プログラムの実行内で注目するspの値を示す図である。
【図１７】実施の形態３にかかるキャッシュメモリシステムの構成図である。
【図１８】実施の形態３にかかるキャッシュの構成で追加された情報の初期値を説明する図である。
【図１９】実施の形態３にかかるプログラム開始処理のフローチャートである。
【図２０】実施の形態３にかかるスタックフレーム確保、解放時の処理のフローチャートである。
【図２１】実施の形態３にかかるキャッシュリフィル処理に用いる条件を表す図である。
【図２２Ａ】実施の形態３にかかるにかかるキャッシュラインのリフィル手順の図である。
【図２２Ｂ】実施の形態３にかかるにかかるキャッシュラインのリフィル手順の図である。
【図２３Ａ】実施の形態３にかかるキャッシュのリフィル手順を利用した場合の、プログラムの実行トレース結果の図である。
【図２３Ｂ】実施の形態３にかかるキャッシュのリフィル手順を利用した場合の、プログラムの実行トレース結果の図である。
【図２４】実施の形態３にかかるspの遷移を表す図である。
【図２５】実施の形態４にかかるキャッシュメモリシステムの構成図である。
【図２６】実施の形態４にかかるキャッシュの構成で追加された情報の初期値を説明する図である。
【図２７】実施の形態４にかかるプログラム開始処理のフローチャートである。
【図２８】実施の形態４にかかるスタックフレーム確保、解放時の処理のフローチャートである。
【図２９】実施の形態４にかかるキャッシュリフィル処理に用いる条件を表す図である。
【図３０Ａ】実施の形態４にかかるにかかるキャッシュラインのリフィル手順の図である。
【図３０Ｂ】実施の形態４にかかるにかかるキャッシュラインのリフィル手順の図である。
【図３１Ａ】実施の形態４にかかるキャッシュのリフィル手順を利用した場合の、プログラムの実行トレース結果の図である。
【図３１Ｂ】実施の形態４にかかるキャッシュのリフィル手順を利用した場合の、プログラムの実行トレース結果の図である。
【図３２】実施の形態４にかかるspの遷移を表す図である。
【図３３】従来のＬＲＵを用いたキャッシュメモリシステムの構成図である。
【図３４】キャッシュのデータ格納構造の図である。
【図３５】従来のＬＲＵを用いたキャッシュライン入れ替え、および実施の形態１の説明に用いる実行プログラムの図である。
【図３６】実施の形態１、実施の形態２、実施の形態３、および実施の形態４にかかるasmソース内の命令動作の説明である。
【図３７】従来のＬＲＵアルゴリズムを利用した場合の、プログラムの実行トレース結果の図である。
【発明を実施するための形態】
【００２９】
実施の形態１
以下、図面を参照して本発明の実施の形態について説明する。まず、図１を参照して、本実施の形態１にかかるキャッシュメモリシステムの基本構成について説明する。図１に示すキャッシュメモリシステムの基本構成は、キャッシュライン選択処理部４０に、スタック開始位置４０１と、スタック終了位置４０２と、を備える。スタック開始位置４０１は、コールスタックの格納領域の開始アドレスを示す。スタック開始位置４０２は、コールスタックの格納領域の終了アドレスを示す。ＣＰＵ３０は、キャッシュライン選択処理部４０に対して、実行プログラムのロード・ストア命令を実行する際に、スタックポインタの値を通知する。
【００３０】
本実施の形態にかかるキャッシュラインのリフィルは、ＡＢＩ(Application Binary Interface)の情報を利用するものである。ＡＢＩは、アプリケーションプログラムとＯＳ（Operating System）間のインターフェイスを表すものである。ＡＢＩは、data領域、bss（Block Started by Symbol）領域、およびスタック領域を指す自動変数の仕様を保持する。プログラム実行時に関数がネストする場合、スタックポインタは、スタックフレーム確保のために下方向へ伸びる、すなわちアドレスの低い値に推移する。スタックフレームとは、サブルーチン（関数）毎にコールスタックに格納する情報を指す。ここで、本実施の形態は、スタック領域（スタック開始位置からスタック終了位置の間）のアドレスのうち、プログラム実行時にスタックポインタよりも低い値をアドレスにもつデータにアクセスすることはない、という特性を利用し、リフィルするキャッシュラインを選択する。
【００３１】
図２は、本実施の形態にかかるプログラムの開始処理を示す図である。プログラムの開始時に、プログラム情報（ロードする位置、サイズ、プログラム開始位置、スタック開始位置、スタック終了位置）を取得し（Ｓ２０１）、プログラムのロードを行う（Ｓ２０２）。スタック開始位置およびスタック終了位置をキャッシュライン選択処理部４０に通知し（Ｓ２０３）、プログラムの開始位置へ分岐する（Ｓ２０４）。
【００３２】
図３は、本実施の形態にかかるキャッシュラインのリフィル手順を示す図である。キャッシュライン選択処理部４０は、各キャッシュラインのアドレスを参照し、アドレスがスタック開始位置とスタック終了位置の間にあるか否かを判定する（Ｓ３０１）。キャッシュラインのアドレスがスタック領域に存在し（Ｓ３０１：Ｙｅｓ）、スタックポインタよりも低い値のアドレスを持つキャッシュラインが存在する場合（Ｓ３０２：Ｙｅｓ）、このキャッシュラインをリフィルの対象とする。対象となるキャッシュラインが複数ある場合、これらのキャッシュラインの中からＬＲＵ情報１３１を利用して、キャッシュライン選択処理部４０は、１つのキャッシュラインを選択する（Ｓ３０３）。一方、対象となるキャッシュラインが一つもない場合（Ｓ３０２：Ｎｏ）、従来と同様に、キャッシュライン選択処理部４０は、ＬＲＵ情報１３１を利用してリフィルの対象とするキャッシュラインを選択する（Ｓ３０４）。
【００３３】
図４は、本実施の形態にかかるキャッシュラインの入れ替え方法により、図３５に示すプログラムを実行した際の実行トレース結果を示す図である。なお、キャッシュ１０のデータ格納構造は図３４に示したものと同様とする。
【００３４】
図４に示した実行トレース結果について説明する。以下の例では、スタック開始位置４０１を0x8000、スタック終了位置４０２を0x7000、スタックポインタの初期値を0x80000とする。また、ＬＲＵ情報１３１の初期値は、「キャッシュライン１」を指すものとする。変数に割り当てられるアドレスにより、変数a,b,cはキャッシュライン上で同じ領域を示すものとする。
【００３５】
Ｓｔｅｐ１では、関数Func1のスタックフレーム確保のため、sub命令でspの値は0x7fe0となる。また、変数aのアドレスは0x7ff0、変数bのアドレスは0x7fe0に割り当てるものとする。
【００３６】
Ｓｔｅｐ２では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、ＬＲＵ情報１３１が指すキャッシュラインが「キャッシュライン１（ライン１）」であるため、キャッシュライン１に変数aのデータと、アドレスと、を設定する。また、ＬＲＵ情報は、アクセスがされていない「キャッシュライン２（ライン２）」に変更される。Ｓｔｅｐ３では、関数の呼び出し命令のため、関数Func2の処理へ分岐する。
【００３７】
Ｓｔｅｐ４では、関数Func2のスタックフレーム確保のため、sub命令によってspの値は、0x7fc0になる。また、変数cのアドレスは、0x7fd0に割り当てるものとする。Ｓｔｅｐ５では、変数cを利用するため、アドレス0x7fd0のデータをロードする。その際に、ＬＲＵ情報１３１が指すキャッシュラインが「キャッシュライン２（ライン２）」であるため、キャッシュライン２に変数cのデータと、アドレスと、を設定する。また、ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン１（ライン１）」に変更される。
【００３８】
Ｓｔｅｐ６では、関数Func2のスタックフレーム解放のため、add命令によりspの値は、0x7fe0となる。Ｓｔｅｐ７では、return命令により、関数Func1に処理が戻る。
【００３９】
Ｓｔｅｐ８では、変数bを利用するため、アドレス0x7fe0のデータをロードする。その際、キャッシュライン１およびキャッシュライン２には、変数bのデータが存在しないため、図３に示した手順でキャッシュラインのリフィルを行う。図３に示した手順によると、キャッシュラインのアドレスがスタック開始位置から終了位置の間であり（Ｓ３０１：Ｙｅｓ）、かつspの値0x7fe0よりも低いアドレスの値を持つキャッシュライン２がリフィルの対象として選択される（Ｓ３０２：Ｙｅｓ、Ｓ３０３）。よって、キャッシュライン２に変数bのデータと、アドレスと、を設定する（Ｓ３０５）。ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン１（ライン１）」に変更される。
【００４０】
Ｓｔｅｐ９では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、キャッシュライン１に変数aのデータが存在するため、この値を参照する。ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン２（ライン２）」に変更される。
【００４１】
Ｓｔｅｐ１０では、関数Func1のスタックフレーム解放のため、add命令によりspの値は、0x8000となる。Ｓｔｅｐ１１では、プログラムの実行を終了する。
【００４２】
上記一連の処理により、図４のＳｔｅｐ８で変数bを利用する際に、ＬＲＵ情報１３１はキャッシュライン１を示しているが、キャッシュライン２に格納された変数cのアドレスが0x7fd0で、spの値0x7fe0よりも低い値であるため、キャッシュライン２をリフィルしている。そのため、Ｓｔｅｐ９で変数aを利用する際にキャッシュヒットとなり、従来のキャッシュ入れ替え方法の実行時（図３７）にキャッシュミスとなっていた問題が解決される。すなわち、アクセス頻度を示すＬＲＵ情報のみならず、スタックポインタの値と、キャッシュライン内に保持されているデータのアドレス情報を参照して、不要となったデータを持つキャッシュラインを優先的にリフィルの対象としている。これにより、従来ではキャッシュミスとなっていた問題が解決される。
【００４３】
なお、本実施の形態では、キャッシュラインのリフィルの選択を、ＬＲＵアルゴリズムにより実現したが、これに限らず、ＬＦＵ（Least Frequently Used: 各データの参照頻度を保持し、もっとも参照頻度の低いデータを選択する方式）アルゴリズム等、１つのデータを選択する方法であればよい。
【００４４】
実施の形態２
本発明の実施の形態２は、解放したスタックフレームのアドレスを持つキャッシュラインを優先的にリフィルの対象とすることを特徴とする。
【００４５】
関数呼び出しによりスタックフレームを確保（spの値は低下）し、その後にスタックフレームを解放（spの値は増加）した場合、解放した時点で解放されたスタックフレームのアドレスを持つデータは参照されることがなくなる。そのため、本実施の形態では、解放されたアドレスを持つデータが格納されたキャッシュラインを優先的にリフィルの対象とする。
【００４６】
図５は、本実施の形態において、実行されるプログラムを示す図である。図６は、プログラム実行の流れの中で注目するスタックポインタの値（spの値）を示す図である。図６において、縦軸はspの値を示し、横軸はプログラム実行の流れを示す。現在実行中のＳｔｅｐ（６０３）において、解放されているスタックフレーム範囲（６０１）のアドレスを持つデータは参照されることはない。そのため、その範囲を解放した後のspの値（６０２）を保持し、リフィルするキャッシュラインの選択の条件に利用する。これにより、このspの値（６０２）よりも低いアドレスの値を持つデータの格納されたキャッシュラインをリフィル対象とできる。この際、現在のＳｔｅｐ（６０３）のスタックフレーム（６０４）のアドレスと、解放したスタックフレーム範囲（６０１）のアドレスと、が同じになる場合がある。そのため、キャッシュラインに格納するデータに、プログラムのどの時点においてスタックフレームに格納されたかを判別できる情報（スタックフレームの操作回数）を追加する。スタックフレームの操作回数の詳細は、後述する。
【００４７】
図７を参照して、本実施の形態にかかるキャッシュメモリシステムの基本構成について説明する。図７に示すキャッシュメモリシステムの基本構成は、実施の形態１と以下の点で相違する。キャッシュライン１（１０１）は、メモリアクセス先のアドレス情報１１１と、データ１１２とに加え、データが参照された時点のスタック操作回数１１３の情報を保持する。同様にキャッシュライン２（１０２）は、メモリアクセス先のアドレス情報１２１と、データ１２２と、に加え、データが参照された時点のスタック操作回数１２３の情報を保持する。ＣＰＵ３０は、プログラムのロード・ストア命令において、spの値を通知することに加えて、スタックフレームの確保および解放時にspの値をキャッシュライン選択処理部４０に通知する。
【００４８】
キャッシュライン選択処理部４０は、実施の形態１の構成に加え、最終最上スタック操作回数４０３と、最終最下スタック操作回数４０４と、最終最上スタック位置４０５と、作業用スタック位置４０６と、を更に備える。
【００４９】
作業用スタック位置４０６は、スタックフレームの解放によってspの値が増加した場合に、spと同じ値をとるものである。最終最上スタック位置４０５ は、スタックフレームの確保によってspの値が低下したときに、作業用スタック位置４０６と同じ値をとるものである。最終最上スタック位置４０５は、プログラム開始から現在の実行位置の間で、spの値を線グラフで見た場合に、最後に極大値となったときのspの値を示す。
【００５０】
最終最上スタック操作回数４０３は、spの値が低下したときに、最終最下スタック操作回数４０４に「１」を加算した値をとる。最終最下スタック操作回数４０４は、spの値が増加した時に、最終最上スタック操作回数４０３と同じ値をとる。これにより、最終最上スタック操作回数４０３は、spの値が極大値から低下するごとにカウントすることを示す。
【００５１】
スタック操作回数１１３、１２３は、キャッシュラインにデータを設定した際に、最終最上スタック操作回数４０３の値を代入するものである。これにより、このキャッシュラインに保持されたデータが、プログラム中のどの時点でキャッシュラインに格納されたかを判別することができる。
【００５２】
図８は、本実施の形態において追加される情報の初期値を示す図である。作業用スタック位置４０６の初期値は、スタック開始位置４０１と同じ値となる。スタック操作回数の初期値は、キャッシュラインにデータを設定したときの最終最上スタック操作回数４０３の値と同じ値となる。最終最上スタック操作回数４０３、最終最下スタック操作回数４０４、および最終最上スタック位置４０５の初期値は「０」となる。
【００５３】
図９は、本実施の形態にかかるプログラムの開始処理を示す図である。図２に示す実施の形態１の処理に加え、最終最上スタック操作回数４０３と、最終最下スタック操作回数４０４と、最終最上スタック位置４０５と、作業用スタック位置４０６と、の初期化処理（Ｓ２０５）を実行する。初期化処理（Ｓ２０５）とは、各情報を上述（図８）の初期値に設定する処理である。
【００５４】
図１０は、スタックフレーム確保・解放時に、ＣＰＵ３０からspの値の通知があった場合の、キャッシュライン選択処理部４０の処理を示すフローチャートである。spの値が低下した通知を受けた場合（Ｓ４０１：Ｙｅｓ）、最終最下スタック操作回数４０４に「１」を加算した値を、最終最上スタック操作回数４０３に設定する。また、最終最上スタック位置４０５に、作業用スタック位置４０６の値を設定する（Ｓ４０３）。一方、spの値が増加した通知を受けた場合（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４に、最終最上スタック操作回数４０３の値を設定する。また、作業用スタック位置４０６に、spの値を設定する（Ｓ４０４）。
【００５５】
図１１は、本実施の形態にかかるキャッシュラインのリフィル手順を示す図である。っこでは、実施の形態１と異なる処理について以下に記載する。実施の形態１において、キャッシュラインに格納されたデータのアドレスが、spの値よりも低いものがない場合（Ｓ３０２：Ｎｏ）には、次の処理を行う。
【００５６】
キャッシュライン内のスタック操作回数から最終最上スタック操作回数４０３を引いた値が「０」ではないデータがあるか否かを判定する（Ｓ３０６）。Ｓ３０６の条件に合致するキャッシュラインがある場合、該当するキャッシュラインの中で、アドレス１１１が最終最上スタック位置４０５よりも低いものが存在するか否かを判定する（Ｓ３０７）。Ｓ３０６およびＳ３０７の条件を満たすキャッシュラインの中から、キャッシュライン選択処理部４０は、ＬＲＵ情報１３１に基づき、リフィルするキャッシュラインを選択する（Ｓ３０８）。
【００５７】
spの値より低い値を持つアドレス１１１が格納されたキャッシュラインがある場合（Ｓ３０２：Ｙｅｓ）、およびキャッシュラインのアドレス１１１がスタック開始位置と終了位置との間にない場合（Ｓ３０１：Ｎｏ）、図３と同様の処理を行う。
【００５８】
キャッシュラインをリフィル（Ｓ３０５）した後、キャッシュライン選択処理部４０は、リフィルの対象となったキャッシュラインのスタック操作回数に、最終最上スタック操作回数４０３の値を設定する（Ｓ３０９）。
【００５９】
図１２は、本実施の形態にかかるキャッシュラインの入れ替え方法により、図５に示すプログラムを実行した際の実行トレース結果を示す図である。なお、キャッシュ１０のデータ格納構造は図３４に示したものと同様とする。
【００６０】
図１２に示した実行トレースについて説明する。以下の例では、スタック開始位置４０１を0x8000、スタック終了位置４０２を0x7000、スタックポインタの初期値を0x8000とする。また、ＬＲＵ情報１３１の初期値は、「キャッシュライン１」を指すものとする。変数に割り当てられるアドレスにより、変数a,b,cはキャッシュライン上で同じ領域を示すものとする。
【００６１】
Ｓｔｅｐ１では、関数Func1のスタックフレーム確保のため、sub命令でspの値は0x7fe0となる。また、変数aのアドレスは0x7ff0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「０」に「１」を加算した「１」が設定される。また、最終最上スタック位置４０５には、作業用スタック位置４０６の値である0x8000が設定される。
【００６２】
Ｓｔｅｐ２では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、ＬＲＵ情報１３１が指すキャッシュラインが「キャッシュライン１（ライン１）」であるため、キャッシュライン１に変数aのデータと、アドレスと、を設定する。また、ＬＲＵ情報１３１は、アクセスがされていない「キャッシュライン２（ライン２）」に変更される。Ｓｔｅｐ３では、関数の呼び出し命令のため、関数Func2の処理へ分岐する。
【００６３】
Ｓｔｅｐ４では、関数Func2のスタックフレーム確保のため、sub命令によってspの値は、0x7fc0になる。また、変数bのアドレスは、0x7fd0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「０」に「１」を加算した「１」が設定される。また、最終最上スタック位置４０５には、作業用スタック位置４０６の値である0x8000が設定される。
【００６４】
Ｓｔｅｐ５では、変数bを利用するため、アドレス0x7fd0のデータをロードする。その際に、ＬＲＵ情報１３１が指すキャッシュラインが「キャッシュライン２（ライン２）」であるため、キャッシュライン２に変数bのデータと、アドレスと、を設定する。また、スタック操作回数１１３に最終最上スタック操作回数４０３の値である「１」を設定する。ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン１（ライン１）」に変更される。
【００６５】
Ｓｔｅｐ６では、関数Func2のスタックフレーム解放のため、add命令によりspの値は、0x7fe0となる。また、スタックフレームの解放によりspの値が増加したため、最終最下スタック操作回数４０４は、最終最上スタック操作回数４０３と同じ値である「１」が設定される。また、作業用スタック位置４０６は、spの値である0x7fe0に設定される。
【００６６】
Ｓｔｅｐ７では、return命令により、関数Func1に処理が戻る。Ｓｔｅｐ８では、関数の呼び出し命令のため、関数Func2の処理へ分岐する。
【００６７】
Ｓｔｅｐ９では、関数Func3のスタックフレーム確保のため、add命令によりspの値は、0x7fc0となる。また、変数cのアドレスは、0x7fd0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「１」に「１」を加算した「２」が設定される。また、最終最上スタック位置４０５には、作業用スタック位置４０６の値である0x7fe0が設定される。
【００６８】
Ｓｔｅｐ１０では、変数cを利用するため、アドレス0x7fd0のデータをロードする。その際、キャッシュライン１およびキャッシュライン２には、変数cのデータが存在しないため、図１１に示した手順でキャッシュラインのリフィルを行う。図１１に示した手順によると、キャッシュラインのアドレスがスタック開始位置から終了位置の間に存在するが（Ｓ３０１：Ｙｅｓ）、キャッシュラインのアドレスがいずれもspの値0x7fc0よりも低くない（Ｓ３０２：Ｎｏ）。そのため、キャッシュライン内に保持するスタック操作回数と最終最上スタック操作回数４０３の差が「０」ではなく（Ｓ３０６：Ｙｅｓ）、キャッシュラインのアドレスが最終最上スタック位置４０５の値である0x7fe0よりも低い値を持つ（Ｓ３０７：Ｙｅｓ）、キャッシュライン２がリフィル対象となる。よって、キャッシュライン２に変数cのデータと、アドレスと、スタック操作回数と、を設定する。キャッシュライン２のスタック操作回数には、最終最上スタック操作回数４０３の値である「２」が設定される。ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン１（ライン１）」に変更される。
【００６９】
Ｓｔｅｐ１１では、関数Func3のスタックフレーム解放のため、add命令によりspの値は、0x7fe0となる。また、スタックフレームの解放によりspの値が増加したため、最終最下スタック操作回数４０４は、最終最上スタック操作回数４０３と同じ値である「２」が設定される。また、作業用スタック位置４０６は、spの値である0x7fe0に設定される。
【００７０】
Ｓｔｅｐ１２では、return命令により、関数Func1に処理が戻る。Ｓｔｅｐ１３では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、キャッシュライン１に変数aのデータが存在するため、この値を参照する。ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン２（ライン２）」に変更される。
【００７１】
Ｓｔｅｐ１４では、関数Func1のスタックフレーム解放のため、add命令によりspの値は、0x8000となる。また、スタックフレームの解放によりspの値が増加したため、最終最下スタック操作回数４０４は、最終最上スタック操作回数４０３と同じ値である「２」が設定される。また、作業用スタック位置４０６は、spの値である0x8000に設定される。Ｓｔｅｐ１５では、プログラムの実行を終了する。
【００７２】
次に、本実施の形態におけるキャッシュライン入れ替え方法の効果について説明する。まず、非特許文献１に記載のキャッシュライン入れ替え方法および実施の形態１に記載のキャッシュライン入れ替え方法によって、図５に示すプログラムを実行した際の、キャッシュ１０の動作の概要について述べる。
【００７３】
非特許文献１に記載のキャッシュライン入れ替え方法では、Ｓｔｅｐ１０で変数cを利用する際に、ＬＲＵ情報１３１に基づいてリフィルするキャッシュラインを選択するため、変数aを保持するキャッシュライン１がリフィルの対象となる。その結果、Ｓｔｅｐ１３において、変数aを利用する際に、キャッシュミスとなる。
【００７４】
実施の形態１に記載のキャッシュライン入れ替え方法では、Ｓｔｅｐ１０で変数cを利用する際に、キャッシュライン２のアドレスは0x7fd0であり、spの値よりも低い値ではない。そのため、ＬＲＵ情報１３１に基づいてリフィルするキャッシュラインを選択するため、変数aを保持するキャッシュライン１がリフィルの対象となる。その結果、Ｓｔｅｐ１３において、変数aを利用する際に、キャッシュミスとなる。
【００７５】
本実施の形態に記載のキャッシュライン入れ替え方法では、Ｓｔｅｐ１０で変数cを利用する際に、スタック操作回数が最終最上スタック操作回数４０３と異なり、最終最上スタック位置４０５の0x7fe0より低いアドレス0x7fd0を持つキャッシュライン２がリフィルの対象となる。その結果、Ｓｔｅｐ１３において、変数aを利用する際に、キャッシュヒットとなる。
【００７６】
本実施の形態にかかるキャッシュライン入れ替え方法は、コールスタックからの解放済みキャッシュラインを算出するための変数（最終最上スタック位置）を用いて、リフィルするキャッシュラインを選択している。このように、コールスタックからすでに解放され、キャッシュヒットとなることのないキャッシュラインを優先的にリフィルの対象とすることでキャッシュヒット率を高めることができる。
【００７７】
実施の形態３
本発明の実施の形態３は、実施の形態２のキャッシュライン入れ替え方法ではリフィル対象とできなかった、スタックフレームからの解放済みキャッシュラインを、後述の残存ライン数を考慮することによりリフィル対象とできることを特徴とする。
【００７８】
実施の形態２に記載のキャッシュライン入れ替え方法では、現在実行中のＳｔｅｐにおいて、最後にスタックフレームを解放した後、スタックフレームを確保する前のspの値を保存し、このspの値をリフィルするキャッシュラインの選択条件に用いている。しかし、このspの値よりも高い値を持ち、かつ、すでにコールスタックから解放されているデータがキャッシュラインに残っている場合、実施の形態２によっては、当該キャッシュラインをリフィル対象とできない。本実施の形態にかかるキャッシュライン入れ替え方法は、当該キャッシュラインを優先的にリフィル対象とできるように改良したものである。
【００７９】
本実施の形態では、プログラムの開始から現在のＳｔｅｐまでの範囲を、スタックフレームを確保した時を境界として、前後の２つの範囲に分ける。この境界は、現在のＳｔｅｐでキャッシュラインに格納されているデータのうち、前半の範囲でアクセスしたデータ数の方が、後半の範囲でアクセスしたデータ数より多くなっている箇所とする。本実施の形態にかかるキャッシュライン入れ替え方法は、この境界の直前のspの値を、リフィルするキャッシュラインの選択条件に利用する。これにより、前半の範囲で設定されたキャッシュラインは、優先的にリフィル対象とすることができ、複雑な関数呼び出しを行うプログラムに対応可能となる。
【００８０】
図１５は、プログラム実行の流れの中で注目するスタックポインタの値（spの値）を示す図である。図１５において、縦軸はspの値を示し、横軸はプログラム実行の流れを示す。ＳｔｅｐＢ（６１２）でスタックフレームを確保した際に、全キャッシュラインのうち、ＳｔｅｐＡ（６１２）よりも前の範囲（６１５）でアクセスしてキャッシュラインに残っているデータ数（後述の残存ライン数）が、ＳｔｅｐＡ（６１１）からＳｔｅｐＢ（６１２）の範囲（６１６）でアクセスしてキャッシュラインに残っているデータ数（後述の留保ライン数）よりも多い場合、ＳｔｅｐＡ（６１１）でのspの値（６１３）を保存する（後述の残存最上スタック位置）。本実施の形態にかかるキャッシュライン入れ替え方法は、この残存最上スタック位置をリフィルするキャッシュラインの選択条件に利用する。
【００８１】
図１６は、残存最上スタック位置を更新する時の動作を示す図である。ＳｔｅｐＣ（６１７）でスタックフレームを確保した際に、全キャッシュラインのうち、ＳｔｅｐＡ（６１１）よりも前の範囲（６１５）でアクセスしてキャッシュラインに残っているデータ数より、ＳｔｅｐＡ（６１１）からＳｔｅｐＣ（６１７）の間でアクセスしてキャッシュラインに残っているデータ数が多くなった場合、ＳｔｅｐＣ（６１７）のspの値（６１４）を、残存最上スタック位置として保存する。なお、図１５および図１６の説明中にある「アクセスするアドレス」は、スタック領域のアドレスを指す。
【００８２】
図１７を参照して、本実施の形態にかかるキャッシュメモリシステムの基本構成について説明する。図１７に示すキャッシュメモリシステムの基本構成は、キャッシュライン選択処理部４０に、実施の形態２の構成に加え、残存ライン数４０７と、留保ライン数４０８と、残存最上スタック操作回数４０９と、残存最上スタック位置４１０と、を更に備える。
【００８３】
残存最上スタック位置４１０は、プログラムの開始から現在位置までを、spの値が極大を取る箇所を境に２つの範囲に分けたときの、境界のspの値を示す。この２つの範囲は、キャッシュライン中に残っているデータを見たとき、プログラム開始から残存最上スタック位置４１０を設定した前半の範囲で利用したデータの方が、後半の範囲で利用したデータ数より多く残っている状態を示す。
【００８４】
残存最上スタック操作回数４０９は、残存最上スタック位置４１０が設定されたときの最終最上スタック操作回数４０３を示す。残存ライン数４０７は、残存最上スタック位置４１０を設定したプログラムの実行位置（Ｓｔｅｐ）より前にアクセスされたスタック領域のアドレスを持つデータの中で、キャッシュラインに残っているデータのデータ数を表す。留保ライン数４０８は、残存最上スタック位置４１０を設定したプログラムの実行位置（Ｓｔｅｐ）から、現在のプログラム実行箇所までの間にアクセスされたスタック領域のアドレスを持つデータの中で、キャッシュラインに残っているデータのデータ数を表す。
【００８５】
図１８は、本実施の形態において追加される情報の初期値を示す図である。残存ライン数４０７と、留保ライン数４０８と、残存最上スタック操作回数４０９と、残存最上スタック位置４１０と、の初期値は全て「０」である。
【００８６】
図１９は、本実施の形態にかかるプログラムの開始処理を示す図である。図2に示す実施の形態１の処理に加え、残存ライン数４０７と、留保ライン数４０８と、残存最上スタック操作回数４０９と、残存最上スタック位置４１０と、の初期化処理（Ｓ２０６）を実行する。初期化処理（Ｓ２０６）とは、各情報を上述（図１８）の初期値に設定する処理である。
【００８７】
図２０は、スタックフレーム確保・解放時に、ＣＰＵ３０からspの値の通知があった場合の、キャッシュライン選択処理部４０の処理を示すフローチャートである。実施の形態２における処理（図１０）のＳ４０３の処理の後に、以下の処理が追加される。
【００８８】
Ｓ４０３に示す処理により、最終最上スタック操作回数４０３の値が変化したか否かを判定する（Ｓ４０５）。変化がある場合、spの値が極大値から低下したことを表す。最終最上スタック操作回数４０３の値が変化した場合（Ｓ４０５：Ｙｅｓ）、最終最上スタック操作回数４０３の値がオーバーフローしているか否かを判定する（Ｓ４０６）。
【００８９】
最終最上スタック操作回数４０３の値がオーバーフローしている場合（Ｓ４０６：Ｙｅｓ）、以下の設定を行う（Ｓ４０７）。最終最上スタック操作回数４０３に「１」を設定する。最終最下スタック操作回数４０４に「０」を設定する。キャッシュライン内のすべてのスタック操作回数に「０」を設定する。残存最上スタック位置４１０に、最終最上スタック位置４０５の値を設定する。残存最上スタック操作回数４０９に、最終最上スタック操作回数４０３の値を設定する。残存ライン数４０７に、残存ライン数４０７の値に留保ライン数４０８の値を加算した結果を設定する。さらに、留保ライン数４０８を「０」に設定する。上記の処理（Ｓ４０７）により、キャッシュライン内のすべてのスタック操作回数について初期化を行い、全てのキャッシュライン内のデータが残存ライン数４０７にカウントされているものとして扱う。
【００９０】
最終最上スタック操作回数４０３の値がオーバーフローしていない場合（Ｓ４０６：Ｎｏ）、留保ライン数４０８の値が、残存ライン数４０７の値以上であるか否かを判定する（Ｓ４０８）。
【００９１】
留保ライン数４０８の値が、残存ライン数４０７の値以上である場合（Ｓ４０８：Ｙｅｓ）、以下の設定（Ｓ４０９）を行う。残存最上スタック位置４１０に、最終最上スタック位置４０５の値を設定する。残存最上スタック操作回数４０９に、最終最上スタック操作回数４０３の値を設定する。残存ライン数４０７に、残存ライン数４０７の値に留保ライン数４０８の値を加算した結果を設定する。さらに、留保ライン数４０８を「０」に設定する。
【００９２】
留保ライン数４０８の値が、残存ライン数４０７の値未満である場合（Ｓ４０８：Ｎｏ）、処理を終了する。
【００９３】
続いて、図２２Ａおよび図２２Ｂを参照し、本実施の形態にかかるキャッシュラインのリフィル手順について説明する。図２２Ａおよび図２２Ｂ内で用いる分岐条件を図２１に示す。条件１は、キャッシュラインのアドレスが、スタック開始位置と終了位置との間にあるか否かを判定する。条件２は、キャッシュラインのアドレスが、現在のspの値よりも低い値か否かを判定する。条件３は、キャッシュライン内のスタック操作回数が残存最上スタック操作回数４０９よりも小さいか否かを判定する。条件４は、キャッシュラインのアドレスが、残存最上スタック位置４１０よりも低い値か否かを判定する。ここでは、実施の形態２と異なる処理について以下に記載する。
【００９４】
各キャッシュラインのアドレスを参照し、アドレスがスタック開始位置とスタック終了位置の間にあり（条件１）、残存ライン数４０７にカウントされているデータを保持しており（条件３）、アドレスが残存最上スタック位置４０５よりも低い値を持つ（条件４）、キャッシュラインを選択する（Ｓ３１０、Ｓ３１１、Ｓ３１２）。上記の条件に当てはまるキャッシュラインが存在しない場合には、ＬＲＵ情報１３１からキャッシュラインを選択する（Ｓ３０４）。
【００９５】
選択されたキャッシュラインが、上述の条件１、および条件３を満たす場合、すなわち残存ライン数４０７にカウントされているデータを保持しているキャッシュラインである場合（Ｓ３１３：Ｙｅｓ）、残存ライン数４０７の値を「１」を減算する（Ｓ３１４）。
【００９６】
選択されたキャッシュラインが、上述の条件１を満たし、条件３を満たさない場合、すなわち残存ライン数４０７にカウントされているデータを保持しているキャッシュラインではない場合（Ｓ３１５：Ｙｅｓ）、留保ライン４０８の値を「１」を減算する（Ｓ３１６）。この処理は、後の処理（Ｓ３１８）において留保ライン４０８の値を「１」を加算するため、留保ライン４０８の値を増加させないために予め「１」を減算するものである。
【００９７】
キャッシュラインをリフィルして新しいデータを設定した際に、このデータのアドレスがスタック領域に含まれる場合（Ｓ３１７：Ｙｅｓ）、リフィル対象のキャッシュラインのスタック操作回数に最終最上スタック操作回数４０３の値を設定する。また、留保ライン数４０８の値に「１」を加算する（Ｓ３１８）。
【００９８】
図２３Ａおよび図２３Ｂは、本実施の形態にかかるキャッシュラインの入れ替え方法により、図１４に示すプログラムを実行した際の実行トレース結果を示す図である。また、図２４は、図１４に示すプログラムを実行した際のspの値の推移を示す図である。なお、キャッシュ１０のデータ格納構造は図３４に示したものと同様とする。
【００９９】
図２３Ａおよび図２３Ｂに示した実行トレース結果について説明する。以下の例では、スタック開始位置４０１を0x8000、スタック終了位置４０２を0x7000、スタックポインタの初期値を0x8000とする。また、ＬＲＵ情報１３１の初期値は、「キャッシュライン１」を指すものとする。変数に割り当てられるアドレスにより、変数a,b,cはキャッシュライン上で同じ領域を示すものとする。
【０１００】
Ｓｔｅｐ１では、関数Func1のスタックフレーム確保のため、sub命令でspの値は0x7fe0となる。また、変数aのアドレスは0x7ff0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「０」に「１」を加算した「１」が設定される（Ｓ４０３）。最終最上スタック位置４０５には、作業用スタック位置４０６の値である0x8000が設定される（Ｓ４０３）。また、最終最上スタック操作回数４０３の値が変化し（Ｓ４０５：Ｙｅｓ）、最終最上スタック操作回数４０３の値がオーバーフローせず（Ｓ４０６：Ｎｏ）、留保ライン数４０８の値が残存ライン数４０７の値以上となっているため（Ｓ４０８：Ｙｅｓ）、残存最上スタック位置４１０には、最終最上スタック位置４０５の値である0x0000が設定される（Ｓ４０９）。また、残存最上スタック操作回数４０９には、最終最上スタック操作回数４０３の値である「１」が設定される（Ｓ４０９）。残存ライン数４０７、および留保ライン数４０８はともに０であるため、値は変化しない（Ｓ４０９）。
【０１０１】
Ｓｔｅｐ２では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、スタック開始位置と終了位置との間のアドレス値を持つキャッシュラインが存在しないため（Ｓ３０１：Ｎｏ）、ＬＲＵ情報１３１が指すキャッシュラインである「キャッシュライン１（ライン１）」を選択し（Ｓ３０４）、キャッシュライン１に変数aのデータと、アドレスとを設定する（Ｓ３０５）。また、キャッシュライン１のスタック操作回数に最終最上スタック操作回数４０３の値である「１」を設定する（Ｓ３１７：Ｙｅｓ、Ｓ３１８）。また、留保ライン数４０８に「１」を加算した「１」を設定する（Ｓ３１８）。ＬＲＵ情報１３１は、アクセスがされていない「キャッシュライン２（ライン２）」に変更される。Ｓｔｅｐ３では、関数の呼び出し命令のため、関数Func2の処理へ分岐する。
【０１０２】
Ｓｔｅｐ４では、関数Func2のスタックフレーム確保のため、sub命令によってspの値は、0x7fc0になる。また、変数bのアドレスは、0x7fd0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「０」に「１」を加算した「１」が設定される（Ｓ４０３）。最終最上スタック位置４０５には、作業用スタック位置４０６の値である0x8000が設定される（Ｓ４０３）。最終最上スタック操作回数４０３の値は変化しないため（Ｓ４０５：Ｎｏ）、処理は終了する。
【０１０３】
Ｓｔｅｐ５では、変数bを利用するため、アドレス0x7fd0のデータをロードする。その際に、スタック開始位置と終了位置との間のアドレス値を持つキャッシュラインが存在し（Ｓ３０１：Ｙｅｓ）、現在のspの値よりも低いアドレスを持つキャッシュラインが存在せず（Ｓ３０２：Ｎｏ）、キャッシュライン内のスタック操作回数が、残存最上スタック操作回数４０９よりも大きい（Ｓ３１０：Ｎｏ）ため、ＬＲＵ情報１３１が指すキャッシュラインである「キャッシュライン２（ライン２）」を選択する（Ｓ３０４）。ここで、留保ライン数４０８の減算は行わず（Ｓ３１５：Ｎｏ）、キャッシュライン２に変数bのデータと、アドレスと、を設定する（Ｓ３０５）。また、キャッシュライン２のスタック操作回数に最終最上スタック操作回数４０３の値である「１」を設定する（Ｓ３１７：Ｙｅｓ、Ｓ３１８）。また、留保ライン数４０８に「１」を加算した「２」を設定する（Ｓ３１８）。ＬＲＵ情報１３１は、アクセスがされていない「キャッシュライン１（ライン１）」に変更される。
【０１０４】
Ｓｔｅｐ６では、関数Func2のスタックフレーム解放のため、add命令によりspの値は、0x7fe0となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「１」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x7fe0が設定される（Ｓ４０４）。
【０１０５】
Ｓｔｅｐ７では、return命令により、関数Func1に処理が戻る。Ｓｔｅｐ８では、関数の呼び出し命令のため、関数Func3の処理へ分岐する。
【０１０６】
Ｓｔｅｐ９では、関数Func3のスタックフレーム確保のため、sub命令によってspの値は、0x7fc0になる。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「１」に「１」を加算した「２」が設定される（Ｓ４０３）。最終最上スタック位置４０５には、作業用スタック位置４０６の値である0x7fe0が設定される（Ｓ４０３）。最終最上スタック操作回数４０３の値が変化しており（Ｓ４０５：Ｙｅｓ）、最終最上スタック操作回数４０３の値がオーバーフローせず（Ｓ４０６：Ｎｏ）、留保ライン数４０８が残存ライン数４０９以上であるため（Ｓ４０８：Ｙｅｓ）、以下の処理（Ｓ４０９）を行う。
【０１０７】
Ｓ４０９の処理では、残存最上スタック位置４１０には、最終最上スタック位置４０５の値である0x7fe0を設定する。残存最上スタック操作回数４０９には、最終最上スタック操作回数４０３の値である「２」を設定する。残存ライン数４０７には、残存ライン数４０７と留保ライン数４０８を加算した値である「２」を設定する。また、留保ライン数４０８には、「０」を設定する。Ｓｔｅｐ１０では、関数の呼び出し命令のため、関数Func4の処理へ分岐する。
【０１０８】
Ｓｔｅｐ１１では、関数Func4のスタックフレーム確保のため、sub命令によってspの値は、0x7fa0になる。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「１」に「１」を加算した「２」が設定される（Ｓ４０３）。最終最上スタック位置４０５には、作業用スタック位置４０６の値である0x7fe0が設定される（Ｓ４０３）。最終最上スタック操作回数４０３の値は変化しないため（Ｓ４０５：Ｎｏ）、処理は終了する。
【０１０９】
Ｓｔｅｐ１２では、関数Func4のスタックフレーム解放のため、add命令によりspの値は、0x7fc0となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「２」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x7fc0が設定される（Ｓ４０４）。
【０１１０】
Ｓｔｅｐ１３では、return命令により、関数Func3に処理が戻る。Ｓｔｅｐ１４では、関数の呼び出し命令のため、関数Func5の処理へ分岐する。
【０１１１】
Ｓｔｅｐ１５では、関数Func5のスタックフレーム確保のため、sub命令によってspの値は、0x7fa0になる。また、変数cのアドレスは、0x7fb0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「２」に「１」を加算した「３」が設定される（Ｓ４０３）。最終最上スタック位置４０５には、作業用スタック位置４０６の値である0x7fc0が設定される（Ｓ４０３）。最終最上スタック操作回数４０３の値は変化しており（Ｓ４０５：Ｙｅｓ）、最終最上スタック操作回数４０３の値がオーバーフローしないが（Ｓ４０６：Ｎｏ）、留保ライン数４０８が残存ライン数４０７未満であるため（Ｓ４０８：Ｎｏ）、処理は終了する。
【０１１２】
Ｓｔｅｐ１６では、変数cを利用するため、アドレス0x7fb0のデータをロードする。その際に、スタック開始位置と終了位置との間のアドレス値を持つキャッシュラインが存在し（Ｓ３０１：Ｙｅｓ）、現在のspの値よりも低いアドレスを持つキャッシュラインが存在せず（Ｓ３０２：Ｎｏ）、キャッシュライン内のスタック操作回数が、残存最上スタック操作回数４０９よりも小さく（Ｓ３１０：Ｙｅｓ）、キャッシュラインのアドレスが残存最上スタック位置４１０よりも低い値を持つキャッシュライン２を選択する（Ｓ３１１：Ｙｅｓ、Ｓ３１２）。選択したキャッシュライン２が、スタック開始位置と終了位置との間のアドレス値を持ち、キャッシュライン内のスタック操作回数が、残存最上スタック操作回数４０９よりも少ないため（Ｓ３１３：Ｙｅｓ）、残存ライン数４０７を「２」から「１」を減算して、「１」を設定する（Ｓ３１４）。その後、キャッシュライン２に変数cのデータと、アドレスと、を設定する（Ｓ３０５）。また、キャッシュライン２のスタック操作回数に最終最上スタック操作回数４０３の値である「３」を設定する（Ｓ３１７：Ｙｅｓ、Ｓ３１８）。また、留保ライン数４０８に「１」を加算した「１」を設定する（Ｓ３１８）。ＬＲＵ情報１３１は、アクセスがされていない「キャッシュライン１（ライン１）」に変更される。
【０１１３】
Ｓｔｅｐ１７では、関数Func5のスタックフレーム解放のため、add命令によりspの値は、0x7fc0となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「３」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x7fc0が設定される（Ｓ４０４）。Ｓｔｅｐ１８では、return命令により、関数Func3に処理が戻る。
【０１１４】
Ｓｔｅｐ１９では、関数Func3のスタックフレーム解放のため、add命令によりspの値は、0x7fe0となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「３」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x7fe0が設定される（Ｓ４０４）。Ｓｔｅｐ２０では、return命令により、関数Func1に処理が戻る。
【０１１５】
Ｓｔｅｐ２１では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、キャッシュライン１に変数aのデータが存在するため、この値を参照する。ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン２（ライン２）」に変更される。
【０１１６】
Ｓｔｅｐ２２では、関数Func1のスタックフレーム解放のため、add命令によりspの値は、0x8000となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「３」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x8000が設定される（Ｓ４０４）。Ｓｔｅｐ２３では、プログラムの実行を終了する。
【０１１７】
次に、本実施の形態におけるキャッシュライン入れ替え方法の効果について説明する。まず、非特許文献１に記載のキャッシュライン入れ替え方法、実施の形態１に記載のキャッシュライン入れ替え方法、および実施の形態２に記載のキャッシュライン入れ替え方法によって、図１４に示すプログラムを実行した際の、キャッシュ１０の動作の概要について述べる。
【０１１８】
非特許文献１に記載のキャッシュライン入れ替え方法では、Ｓｔｅｐ１６で変数cを利用する際に、ＬＲＵ情報１３１に基づいてリフィルするキャッシュラインを選択するため、変数aを保持するキャッシュライン１がリフィルの対象となる。その結果、Ｓｔｅｐ２１において、変数aを利用する際に、キャッシュミスとなる。
【０１１９】
実施の形態１に記載のキャッシュライン入れ替え方法では、Ｓｔｅｐ１６で変数cを利用する際に、キャッシュライン２のアドレスは0x7fd0であり、spの値よりも高い。そのため、ＬＲＵ情報１３１に基づいてリフィルするキャッシュラインを選択するため、変数aを保持するキャッシュライン１がリフィルの対象となる。その結果、Ｓｔｅｐ２１において、変数aを利用する際に、キャッシュミスとなる。
【０１２０】
実施の形態２に記載のキャッシュライン入れ替え方法では、Ｓｔｅｐ１６で変数cを利用する際に、キャッシュライン２のアドレスは0x7fd0であり、最終最上スタック位置４０５の値0x7fc0よりも高い。そのため、ＬＲＵ情報１３１に基づいてリフィルするキャッシュラインを選択するため、変数aを保持するキャッシュライン１がリフィルの対象となる。その結果、Ｓｔｅｐ２１において、変数aを利用する際に、キャッシュミスとなる。
【０１２１】
本実施の形態に記載のキャッシュライン入れ替え方法では、Ｓｔｅｐ１６で変数cを利用する際に、キャッシュライン内のスタック操作回数が、残存最上スタック操作回数４０９と異なり、残存最上スタック位置４１０の0x7fe0より低いアドレス0x7fd0を持つ、変数bを格納したキャッシュライン２がリフィルの対象となる。その結果、Ｓｔｅｐ２１において、変数aを利用する際に、キャッシュヒットとなる。
【０１２２】
本実施の形態に記載のキャッシュライン入れ替え方法では、残存ライン数と、留保ライン数と、残存最上スタック操作回数と、残存最上スタック位置と、を新たに考慮することにより、複雑な関数の呼び出しを行うプログラムの実行時であっても、キャッシュヒット率を高めることができる。
【０１２３】
実施の形態４
本発明の実施の形態４は、実施の形態３と比べ、オーバーフローをする恐れのあるスタック操作回数１１３と、残存最上スタック操作回数４０９と、を削除し、かつ実施の形態３と同様の処理を行えることを特徴とする。
【０１２４】
図２５を参照して、本実施の形態にかかるキャッシュメモリシステムの基本構成について説明する。図２５に示すキャッシュメモリシステムの基本構成は、実施の形態２にかかるキャッシュメモリシステムの構成と比べ、キャッシュライン選択処理部４０から最終最上スタック位置４０５と、残存ライン数４０９と、を削除している。また、キャッシュライン１０１のスタック操作回数１１３を削除し、留保ラインフラグ１１４を備える。同様に、キャッシュライン１０２のスタック操作回数１２３を削除し、留保ラインフラグ１２４を備える。留保ラインフラグ１１４、および留保ラインフラグ１２４は、「０」または「１」の値をとるものである。留保ラインフラグが「１」である場合、キャッシュライン内のデータが留保ライン数４０８にカウントされていることを示す。
【０１２５】
図２６は、本実施の形態において追加される情報の初期値を示す図である。留保ラインフラグ１１４、および留保ラインフラグ１２４の初期値は、キャッシュラインのアドレスがスタック領域内である場合は「１」となり、それ以外は「０」となる。
【０１２６】
図２７は、本実施の形態にかかるプログラムの開始処理を示す図である。実施の形態１の処理に加え、最終最上スタック操作回数４０３と、最終最下スタック操作回数４０４と、作業用スタック位置４０６と、残存ライン数４０７と、留保ライン数４０８と、残存最上スタック位置４１０と、の初期化処理（Ｓ２０７）を実行する。初期化処理（Ｓ２０７）とは、各情報を上述の初期値（図８、図１８）に設定する処理である。
【０１２７】
図２８は、スタックフレーム確保・解放時に、ＣＰＵ３０からspの値の通知があった場合の、キャッシュライン選択処理部４０の処理を示すフローチャートである。スタックフレーム解放時の処理は、実施の形態２における処理と同じである。以下に、スタックフレーム確保時の処理について説明する。
【０１２８】
関数呼び出しによりスタックフレームが確保され、spの値が低下した場合（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４に「１」を加算した値が設定される（Ｓ４１０）。
【０１２９】
最終最上スタック操作回数４０３への値の設定（Ｓ４１０）により、最終最上スタック操作回数４０３の値に変化があったか否かを判定する（Ｓ４０５）。ここで、実施の形態３における処理（図２０）と異なり、最終最上スタック操作回数４０３がオーバーフローとなる場合であっても、問題は生じない。
【０１３０】
最終最上スタック操作回数４０３の値に変化があった場合（Ｓ４０５：Ｙｅｓ）、留保ライン数４０８が残存ライン数４０７以上であるか否かを判定する（Ｓ４０８）。留保ライン数４０８が残存ライン数４０７以上である場合（Ｓ４０８：Ｙｅｓ）、以下の設定（Ｓ４１１）を行う。残存最上スタック位置４１０には、作業用スタック位置４０６の値が設定される。ここで、キャッシュライン中のデータは、全て残存ライン数４０７のデータとして扱う。そのため、残存ライン数４０７には、残存ライン数４０７に留保ライン数４０８を加算した値を設定する。また、留保ライン数４０８には、「０」を設定する。全てのキャッシュラインの留保ラインフラグには、「０」を設定する。
【０１３１】
続いて、図３０Ａおよび図３０Ｂを参照し、本実施の形態にかかるキャッシュラインのリフィル手順について説明する。図３０Ａおよび図３０Ｂ内で用いる分岐条件を図２９に示す。本実施の形態で用いる分岐条件（図２９）は、実施の形態３の分岐条件（図２１）と比べ、条件３が条件５に入れ替わったものである。条件５は、キャッシュライン内の留保ラインフラグが「０」であるか否かを判定する条件である。ここでは、実施の形態３と異なる処理を中心に説明する。
【０１３２】
図３０Ａおよび図３０ＢにおけるＳ３１９、Ｓ３２０、Ｓ３２１、Ｓ３２２、およびＳ３２３の処理は、実施の形態３で残存最上スタック操作回数４０９とスタック操作回数との比較を行っていた処理（条件３）を、留保ラインフラグが「０」であるか否かを判定する処理（条件５）に変更したものである。
【０１３３】
リフィル処理の後（Ｓ３０５）、リフィルしたキャッシュラインがスタック領域に存在する場合（Ｓ３１７：Ｙｅｓ）、リフィルしたキャッシュラインの留保ラインフラグに「１」を設定する（Ｓ３２４）。また、留保ライン数４０８を「１」増加する（Ｓ３２４）。
【０１３４】
図３１Ａおよび図３１Ｂは、本実施の形態にかかるキャッシュラインの入れ替え方法により、図１４に示すプログラムを実行した際の実行トレース結果を示す図である。また、図３２は、図１４に示すプログラムを実行した際のspの値の推移を示す図である。なお、キャッシュ１０のデータ格納構造は図５に示したものと同様とする。
【０１３５】
図３１Ａおよび図３１Ｂに示した実行トレース結果について説明する。以下の例では、スタック開始位置４０１を0x8000、スタック終了位置４０２を0x7000、スタックポインタの初期値を0x8000とする。また、ＬＲＵ情報１３１の初期値は、「キャッシュライン１」を指すものとする。変数に割り当てられるアドレスにより、変数a,b,cはキャッシュライン上で同じ領域を示すものとする。
【０１３６】
Ｓｔｅｐ１では、関数Func1のスタックフレーム確保のため、sub命令でspの値は0x7fe0となる。また、変数aのアドレスは0x7ff0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「０」に「１」を加算した「１」が設定される（Ｓ４１０）。また、最終最上スタック操作回数４０３の値が変化し（Ｓ４０５：Ｙｅｓ）、留保ライン数４０８が残存ライン数４０７以上となっているため（Ｓ４０８：Ｙｅｓ）、残存最上スタック位置４１０には、作業用スタック位置４０６の値である0x8000が設定される（Ｓ４１１）。残存ライン数４０７、および留保ライン数４０８はともに「０」であるため、値は変化しない（Ｓ４１１）。キャッシュライン中の留保ラインフラグは全て「０」に設定される（Ｓ４１１）。
【０１３７】
Ｓｔｅｐ２では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、スタック開始位置と終了位置との間のアドレス値を持つキャッシュラインが存在しないため（Ｓ３０１：Ｎｏ）、ＬＲＵ情報１３１が指すキャッシュラインである「キャッシュライン１（ライン１）」を選択し（Ｓ３０４）、キャッシュライン１に変数aのデータと、アドレスとを設定する（Ｓ３０５）。リフィルしたキャッシュラインが、スタック領域に存在するため（Ｓ３１７：Ｙｅｓ）、キャッシュライン１の留保ラインフラグに「１」を設定する（Ｓ３２４）。また、留保ライン数４０８に「１」を加算した「１」を設定する（Ｓ３２４）。ＬＲＵ情報１３１は、アクセスがされていない「キャッシュライン２（ライン２）」に変更される。Ｓｔｅｐ３では、関数の呼び出し命令のため、関数Func2の処理へ分岐する。
【０１３８】
Ｓｔｅｐ４では、関数Func2のスタックフレーム確保のため、sub命令によってspの値は、0x7fc0になる。また、変数bのアドレスは、0x7fd0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「０」に「１」を加算した「１」が設定される（Ｓ４１０）。最終最上スタック操作回数４０３の値は「１」のまま変化しないため（Ｓ４０５：Ｎｏ）、処理を終了する。
【０１３９】
Ｓｔｅｐ５では、変数bを利用するため、アドレス0x7fd0のデータをロードする。その際に、スタック開始位置と終了位置との間のアドレス値を持つキャッシュラインが存在し（Ｓ３０１：Ｙｅｓ）、現在のspの値よりも低いアドレスを持つキャッシュラインが存在せず（Ｓ３０２：Ｎｏ）、キャッシュライン中の留保ラインフラグが「０」であるキャッシュラインが存在しないため（Ｓ３１９：Ｎｏ）、ＬＲＵ情報１３１が指すキャッシュラインである「キャッシュライン２（ライン２）」を選択する（Ｓ３０４）。ここで、留保ライン数４０８の減算は行わず（Ｓ３２３：Ｎｏ）、キャッシュライン２に変数bのデータと、アドレスと、を設定する（Ｓ３０５）。また、キャッシュライン２の留保ラインフラグに「１」を設定する（Ｓ３１７：Ｙｅｓ、Ｓ３２４）。また、留保ライン数に「１」を加算した「２」を設定する（Ｓ３２４）。ＬＲＵ情報１３１は、アクセスがされていない「キャッシュライン１（ライン１）」に変更される。
【０１４０】
Ｓｔｅｐ６では、関数Func2のスタックフレーム解放のため、add命令によりspの値は、0x7fe0となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「１」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x7fe0が設定される（Ｓ４０４）。
【０１４１】
Ｓｔｅｐ７では、return命令により、関数Func1に処理が戻る。Ｓｔｅｐ８では、関数の呼び出し命令のため、関数Func3の処理へ分岐する。
【０１４２】
Ｓｔｅｐ９では、関数Func3のスタックフレーム確保のため、sub命令によってspの値は、0x7fc0になる。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「１」に「１」を加算した「２」が設定される（Ｓ４１０）。最終最上スタック操作回数４０３の値が変化し（Ｓ４０５：Ｙｅｓ）、留保ライン数４０８が残存ライン数４０７以上であるため（Ｓ４０８：Ｙｅｓ）、以下の処理（Ｓ４１１）を行う。
【０１４３】
残存最上スタック位置４１０には、作業用スタック位置４０６の値である0x7fe0を設定する。残存ライン数４０７には、残存ライン数４０７に留保ライン数４０８を加算した値である「２」を設定する。また全てのキャッシュラインの留保ラインフラグには、「０」を設定する。Ｓｔｅｐ１０では、関数の呼び出し命令のため、関数Func4の処理へ分岐する。
【０１４４】
Ｓｔｅｐ１１では、関数Func4のスタックフレーム確保のため、sub命令によってspの値は、0x7fa0になる。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「１」に「１」を加算した「２」が設定される（Ｓ４１０）。最終最上スタック操作回数４０３の値は変化しないため（Ｓ４０５：Ｎｏ）、処理は終了する。
【０１４５】
Ｓｔｅｐ１２では、関数Func4のスタックフレーム解放のため、add命令によりspの値は、0x7fc0となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「２」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x7fc0が設定される（Ｓ４０４）。
【０１４６】
Ｓｔｅｐ１３では、return命令により、関数Func3に処理が戻る。Ｓｔｅｐ１４では、関数の呼び出し命令のため、関数Func5の処理へ分岐する。
【０１４７】
Ｓｔｅｐ１５では、関数Func5のスタックフレーム確保のため、sub命令によってspの値は、0x7fa0になる。また、変数cのアドレスは、0x7fb0に割り当てるものとする。ここで、スタックフレームの確保によりspの値が低下したため（Ｓ４０１：Ｙｅｓ）、最終最上スタック操作回数４０３には、最終最下スタック操作回数４０４の値「２」に「１」を加算した「３」が設定される（Ｓ４１０）。最終最上スタック操作回数４０３の値は変化したが（Ｓ４０５：Ｙｅｓ）、留保ライン数４０８が残存ライン数４０７未満であるため（Ｓ４０８：Ｎｏ）、処理を終了する。
【０１４８】
Ｓｔｅｐ１６では、変数cを利用するため、アドレス0x7fb0のデータをロードする。その際に、スタック開始位置と終了位置との間のアドレス値を持つキャッシュラインが存在し（Ｓ３０１：Ｙｅｓ）、現在のspの値よりも低いアドレスを持つキャッシュラインが存在せず（Ｓ３０２：Ｎｏ）、キャッシュライン中の留保ラインフラグが「０」であるキャッシュラインが存在し（Ｓ３１９：Ｙｅｓ）、キャッシュラインのアドレスが、残存最上スタック位置４１０よりも低い値であるキャッシュラインがあるため（Ｓ３２０：Ｙｅｓ）、条件を満たす「キャッシュライン２（ライン２）」を選択する（Ｓ３２１）。選択したキャッシュライン２が、スタック開始位置と終了位置との間のアドレス値を持ち、留保ラインフラグが「０」であるため（Ｓ３２２：Ｙｅｓ）、残存ライン数４０７を「１」減らす（Ｓ３１４）。その後、キャッシュライン２に変数cのデータと、アドレスとを設定する（Ｓ３０５）。リフィルしたキャッシュラインが、スタック領域に存在するため（Ｓ３１７：Ｙｅｓ）、キャッシュライン２の留保ラインフラグに「１」を設定する（Ｓ３２４）。また、留保ライン数４０８に「１」を加算した「１」を設定する（Ｓ３２４）。ＬＲＵ情報１３１は、アクセスがされていない「キャッシュライン１（ライン１）」に変更される。
【０１４９】
Ｓｔｅｐ１７では、関数Func5のスタックフレーム解放のため、add命令によりspの値は、0x7fc0となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「３」が設定される。また、作業用スタック位置４０６の値には、spの値である0x7fc0が設定される。Ｓｔｅｐ１８では、return命令により、関数Func3に処理が戻る。
【０１５０】
Ｓｔｅｐ１９では、関数Func3のスタックフレーム解放のため、add命令によりspの値は、0x7fe0となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「３」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x7fe0が設定される（Ｓ４０４）。Ｓｔｅｐ２０では、return命令により、関数Func1に処理が戻る。
【０１５１】
Ｓｔｅｐ２１では、変数aを利用するため、アドレス0x7ff0のデータをロードする。その際に、キャッシュライン１に変数aのデータが存在するため、この値を参照する。ＬＲＵ情報１３１は、もっとも古くアクセスされたキャッシュラインである「キャッシュライン２（ライン２）」に変更される。
【０１５２】
Ｓｔｅｐ２２では、関数Func1のスタックフレーム解放のため、add命令によりspの値は、0x8000となる。ここで、スタックフレームの確保によりspの値が増加したため（Ｓ４０１：Ｎｏ、Ｓ４０２：Ｙｅｓ）、最終最下スタック操作回数４０４には、最終最上スタック操作回数４０３の値である「３」が設定される（Ｓ４０４）。また、作業用スタック位置４０６の値には、spの値である0x8000が設定される（Ｓ４０４）。Ｓｔｅｐ２３では、プログラムの実行を終了する。
【０１５３】
次に、本実施の形態におけるキャッシュライン入れ替え方法の効果について説明する。上記の一連の処理により、実施の形態３における最終最上スタック位置４０５と、残存最上スタック操作回数４０９とを、削除し、オーバーフローの判定（図２０のＳ４０６）を行わない場合であっても、Ｓｔｅｐ２１において、変数aがキャッシュヒットできる。これは、各キャッシュラインが、留保ラインフラグを備えたことによる。オーバーフローの判定を行わないことにより、本実施の形態にかかるキャッシュライン選択方法は、実施の形態３に比べて処理の高速化が図れる。
【０１５４】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【０１５５】
１０  キャッシュ
１０１  キャッシュライン１
１０２  キャッシュライン２
１０３  ＬＲＵ情報テーブル
１３１  ＬＲＵ情報
２０  メモリ
３０  ＣＰＵ
４０  キャッシュライン選択処理部
４０１  スタック開始位置
４０２  スタック終了位置
【図１】
2011022746.tif 000003
【図２】
2011022746.tif 000004
【図３】
2011022746.tif 000005
【図４】
2011022746.tif 000006
【図５】
2011022746.tif 000007
【図６】
2011022746.tif 000008
【図７】
2011022746.tif 000009
【図８】
2011022746.tif 000010
【図９】
2011022746.tif 000011
【図１０】
2011022746.tif 000012
【図１１】
2011022746.tif 000013
【図１２】
2011022746.tif 000014
【図１３】
2011022746.tif 000015
【図１４】
2011022746.tif 000016
【図１５】
2011022746.tif 000017
【図１６】
2011022746.tif 000018
【図１７】
2011022746.tif 000019
【図１８】
2011022746.tif 000020
【図１９】
2011022746.tif 000021
【図２０】
2011022746.tif 000022
【図２１】
2011022746.tif 000023
【図２２Ａ】
2011022746.tif 000024
【図２２Ｂ】
2011022746.tif 000025
【図２３Ａ】
2011022746.tif 000026
【図２３Ｂ】
2011022746.tif 000027
【図２４】
2011022746.tif 000028
【図２５】
2011022746.tif 000029
【図２６】
2011022746.tif 000030
【図２７】
2011022746.tif 000031
【図２８】
2011022746.tif 000032
【図２９】
2011022746.tif 000033
【図３０Ａ】
2011022746.tif 000034
【図３０Ｂ】
2011022746.tif 000035
【図３１Ａ】
2011022746.tif 000036
【図３１Ｂ】
2011022746.tif 000037
【図３２】
2011022746.tif 000038
【図３３】
2011022746.tif 000039
【図３４】
2011022746.tif 000040
【図３５】
2011022746.tif 000041
【図３６】
2011022746.tif 000042
【図３７】
2011022746.tif 000043