(57)【特許請求の範囲】
【請求項１】
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、
取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるＣＰＵにおけるキャッシュの連想数を含むキャッシュ情報とを入力として第１の外部プログラムを実行させることにより、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒット条件式を入力として第２の外部プログラムを実行させることにより、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、
前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と、該ループ変数に対応する前記パラメータ変数とを入力として第３の外部プログラムを実行させることにより、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、
生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とを入力として第４の外部プログラムを実行させることにより、前記特定の位置の実行回数を示す第１回数式を生成し、
前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とを入力として第５の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第２回数式を生成し、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力として第６の外部プログラムを実行させることにより、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因候補式を入力として第７の外部プログラムを実行させることにより、前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因式を入力として第８の外部プログラムを実行させることにより、前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した後の前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とを入力として第９の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第３回数式を、前記ソースコード上の位置毎に生成し、
前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、
前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式を入力として第１０の外部プログラムを実行させることにより、前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、
生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とを入力として第１１の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第４回数式を生成し、
前記第１回数式から前記第２回数式を減算した式と、前記第３回数式から前記第４回数式を減算した式とを生成する、
処理をコンピュータに実行させることを特徴とするキャッシュミス推定プログラム。
【請求項２】
請求項１において、
前記ヒット条件式を生成する処理では、前記キャッシュの状態集合を示す式を生成するプログラムを、前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力としてコンピュータに実行させ、
前記キャッシュの状態集合を示す式を生成するプログラムの実行によって生成された式を、前記ヒット条件式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項３】
請求項１において、
前記ヒットソース候補式を生成する処理では、前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムを、前記ヒット条件式と、前記ヒット条件式に含まれる前記ループ変数を特定する情報と、前記ヒット条件式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムの実行によって生成された式を、前記ヒットソース候補式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項４】
請求項３において、
前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムは、パラメトリック整数線形計画法を用いたプログラムである、
ことを特徴とするキャッシュミス推定プログラム。
【請求項５】
請求項１において、
前記ヒットソース式を生成する処理では、複数の式がそれぞれ示す範囲の重複を排除するプログラムを、前記ヒットソース候補式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、前記ヒットソース式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項６】
請求項１において、
前記第１回数式を生成する処理では、
前記変数範囲式を生成するプログラムを、前記特定の配列に対応する前記ループ変数と、前記特定の配列に対応する前記ループ変数に対応する前記パラメータ変数とを入力としてコンピュータに実行させ、
前記変数範囲式を生成するプログラムによって生成された式を、前記変数範囲式として生成し、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第１回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項７】
請求項１において、
前記第２回数式を生成する処理では、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第２回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項８】
請求項６または７において、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムは、パラメトリック離散体積計算手法を用いたプログラムである、
ことを特徴とするキャッシュミス推定プログラム。
【請求項９】
請求項１において、
前記競合ミス要因候補式を生成する処理では、前記キャッシュの状態集合を示す式を生成するプログラムを、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力として実行させ、
前記キャッシュの状態集合を示す式を生成するプログラムの実行によって生成された式を、前記競合ミス要因候補式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１０】
請求項１において、
前記競合ミス要因式を生成する処理では、
前記競合ミス要因候補式から、前記特定の配列におけるアクセス対象のデータを前記キャッシュから消去するアクセスを表す前記ループ変数を消去して、ループ変数を消去した前記競合ミス要因候補式を生成し、
ループ変数を消去した競合ミス要因候補式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因候補式を生成し、
重複を排除した前記競合ミス要因候補式から、アクセス対象のデータを識別する識別変数を消去して、前記競合ミス要因式を生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１１】
請求項１において、
前記競合ミス要因式を生成する処理では、
式に含まれる変数を消去するプログラムを、前記競合ミス要因候補式と、前記特定の配列におけるアクセス対象のデータを前記キャッシュから消去するアクセスを表す前記ループ変数を特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって前記ループ変数が消去された式を、ループ変数を消去した前記競合ミス要因候補式として生成し、
複数の式がそれぞれ示す範囲の重複を排除するプログラムを、ループ変数を消去した前記競合ミス要因候補式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、重複を排除した前記競合ミス要因候補式として生成し、
前記式に含まれる変数を消去するプログラムを、重複を排除した前記競合ミス要因候補式と、アクセス対象のデータを識別する識別変数を特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって前記識別変数が消去された式を、前記競合ミス要因式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１２】
請求項１において、
前記第３回数式を生成する処理では、
前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した後の前記競合ミス要因式を生成し、
重複を排除した後の前記競合ミス要因式から、重複を排除した後の前記競合ミス要因式に含まれる前記ループ変数が取り得る値の組み合わせの数を示す式を、前記第３回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１３】
請求項１において、
前記第３回数式を生成する処理では、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムを、前記競合ミス要因式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、重複を排除した後の前記競合ミス要因式として生成し、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、重複を排除した後の前記競合ミス要因式と、重複を排除した後の前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した後の前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第３回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１４】
請求項１において、
前記競合ミス要因分割式を生成する処理では、
前記データの種類の数毎に、前記競合ミス要因式を、アクセス対象のデータを識別する識別変数を含む第１の式と前記識別変数を含まない第２の式とに分類し、分類した前記第１の式を前記データの種類の数と同じ数に複製し、
前記データの種類の数毎に、複製した前記第１の式それぞれに含まれる前記識別変数を、複製した前記第１の式毎に異なる識別変数に変更し、
前記データの種類の数毎に、前記識別変数を変更した前記第１の式それぞれと、前記第２の式と、変更された前記識別変数それぞれの大小関係を示す式とから、変更された前記識別変数それぞれを消去した式を、第３の式として生成し、
前記データの種類の数毎に、各データの種類の数に対応する前記第３の式が示す範囲と、各データの種類の数よりも１大きい数に対応する前記第３の式が示す範囲との差を、各データの種類の数に対応する前記競合ミス要因分割式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１５】
請求項１４において、
前記第３の式を生成する処理では、
前記データの種類の数毎に、式に含まれる変数を消去するプログラムを、前記識別変数を変更した前記第１の式それぞれと、前記第２の式と、変更された前記識別変数それぞれの大小関係を示す式と、変更された前記識別変数それぞれを特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって生成された式を、第３の式として生成し、
前記競合ミス要因分割式を生成する処理では、
前記データの種類の数毎に、複数の式がそれぞれ示す範囲の差を示す式を生成するプログラムに、各データの種類の数に対応する前記第３の式と、各データの種類の数よりも１大きい数に対応する前記第３の式とを入力としてコンピュータに実行させ、
前記データの種類の数毎に、前記複数の式がそれぞれ示す範囲の差を示す式を生成するプログラムの実行によって生成された式を、各データの種類の数に対応する前記競合ミス要因分割式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１６】
請求項１において、
前記競合ミス要因共通式を生成する処理では、複数の式がそれぞれ示す範囲の共通部分を示す式を生成するプログラムを、前記組み合わせに含まれる前記競合ミス要因分割式それぞれを入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の共通部分を示す式を生成するプログラムによって生成された式を、前記競合ミス要因共通式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１７】
請求項１において、
前記第４回数式を生成する処理では、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第４回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【請求項１８】
請求項１において、さらに、
前記パラメータ変数に対応する値を受け付け、
受け付けた前記パラメータ変数に対応する値を、前記第１回数式から前記第２回数式を減算して生成した式に代入して算出された値と、受け付けた前記パラメータ変数に対応する値を、前記第３回数式から前記第４回数式を減算して生成した式に代入して算出された値との総和を算出する、
処理をコンピュータに実行させることを特徴とするキャッシュミス推定プログラム。
【請求項１９】
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるＣＰＵにおけるキャッシュの連想数を含むキャッシュ情報とを入力として第１の外部プログラムを実行させることにより、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒット条件式を入力として第２の外部プログラムを実行させることにより、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と、該ループ変数に対応する前記パラメータ変数とを入力として第３の外部プログラムを実行させることにより、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とを入力として第４の外部プログラムを実行させることにより、前記特定の位置の実行回数を示す第１回数式を生成し、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とを入力として第５の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第２回数式を生成する第１式生成部と、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力として第６の外部プログラムを実行させることにより、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因候補式を入力として第７の外部プログラムを実行させることにより、前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因式を入力として第８の外部プログラムを実行させることにより、前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した後の前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とを入力として第９の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第３回数式を、前記ソースコード上の位置毎に生成し、前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式を入力として第１０の外部プログラムを実行させることにより、前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とを入力として第１１の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第４回数式を生成する第２式生成部と、
前記第１回数式から前記第２回数式を減算した式と、前記第３回数式から前記第４回数式を減算した式とを生成する第３式生成部と、を有する、
ことを特徴とする情報処理装置。
【請求項２０】
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、
取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるＣＰＵにおけるキャッシュの連想数を含むキャッシュ情報とを入力として第１の外部プログラムを実行させることにより、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒット条件式を入力として第２の外部プログラムを実行させることにより、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、
前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と、該ループ変数に対応する前記パラメータ変数とを入力として第３の外部プログラムを実行させることにより、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、
生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とを入力として第４の外部プログラムを実行させることにより、前記特定の位置の実行回数を示す第１回数式を生成し、
前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とを入力として第５の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第２回数式を生成し、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力として第６の外部プログラムを実行させることにより、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因候補式を入力として第７の外部プログラムを実行させることにより、前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因式を入力として第８の外部プログラムを実行させることにより、前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した後の前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とを入力として第９の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第３回数式を、前記ソースコード上の位置毎に生成し、
前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、
前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式を入力として第１０の外部プログラムを実行させることにより、前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、
生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とを入力として第１１の外部プログラムを実行させることにより、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第４回数式を生成し、
前記第１回数式から前記第２回数式を減算した式と、前記第３回数式から前記第４回数式を減算した式とを生成する、
処理をコンピュータに実行させることを特徴とするキャッシュミス推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュミス推定プログラム、キャッシュミス推定方法及び情報処理装置に関する。
【背景技術】
【０００２】
近年、大規模な並列計算機システム（以下、ＨＰＣ（Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｍｐｕｔｉｎｇ）システムとも呼ぶ）において動作するプログラム（以下、アプリケーションプログラムとも呼ぶ）を高速に動作させるための研究が行われている。
【０００３】
具体的に、ＨＰＣシステムにおいてアプリケーションプログラムを高速に動作させるための方法として、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）のキャッシュを有効利用する方法についての研究が行われている。この場合、ＨＰＣシステムの研究者等（以下、単に研究者とも呼ぶ）は、例えば、ＨＰＣシステムにおいてアプリケーションプログラムを動作させ、動作中のアプリケーションプログラムによるキャッシュの利用状況を含むプロファイルデータの取得を行う。そして、研究者は、例えば、取得したプロファイルデータの解析を行うことにより、キャッシュを有効利用するための方法の模索を行う。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平８−２４１２０８号公報
【非特許文献】
【０００５】
【非特許文献１】Ｓｉｄｄｈａｒｔｈａ  Ｃｈａｔｔｅｒｊｅｅ，Ｅｒｉｎ  Ｐａｒｋｅｒ，Ｐｈｉｌｉｐ  Ｊ．Ｈａｎｌｏｎ，ａｎｄ  Ａｌｖｉｎ  Ｒ．Ｌｅｂｅｃｋ．  Ｅｘａｃｔ  ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅ  ｃａｃｈｅ  ｂｅｈａｖｉｏｒ  ｏｆ  ｎｅｓｔｅｄ  ｌｏｏｐｓ．  Ｉｎ  Ｃｉｎｄｙ  Ｎｏｒｒｉｓ  ａｎｄ  Ｊｒ．Ｊａｍｅｓ  Ｂ．Ｆｅｎｗｉｃｋ，ｅｄｉｔｏｒｓ，Ｐｒｏ−ｃｅｅｄｉｎｇ  Ｌａｎｇｕａｇｅ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ（ＰＬＤ１−０１），ｖｏｌｕｍｅ  ３６．５  ｏｆ  ＡＣＭ  ＳＩＧＰＬＡＮ  Ｎｏｔｉｃｅｓ，Ｐａｇｅｓ  ２８６−２９７，Ｎ．Ｙ．，Ｊｕｎｅ  ２０−２２  ２００１．ＡＣＭＰｒｅｓｓ．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記のようにプロファイルデータの作成を行う場合、研究者は、ＨＰＣシステム（以下、実機とも呼ぶ）を長時間利用する必要がある場合がある。そのため、研究者は、実機を利用することができる時間等の制約によっては、実機を利用することによるプロファイルデータの作成を十分に行うことができない場合がある。
【０００７】
これに対し、ＨＰＣシステムのシミュレータを利用することにより、プロファイルデータの作成を行う方法が存在する。この場合、研究者は、アプリケーションプログラムをシミュレータにおいて実行させ、プロファイルデータの作成に要する情報の収集を行う。これにより、研究者は、ＨＰＣシステムを長時間利用することなく、プロファイルデータを取得することが可能になる。
【０００８】
しかしながら、シミュレータの実行速度は、実機の実行速度よりも大幅に遅い場合がある。そのため、研究者は、シミュレータを利用してプロファイルデータの作成を行う場合、プロファイルデータの作成を効率的に行うことができない場合がある。
【０００９】
そこで、一つの側面では、プログラムの実行中に発生したキャッシュミスに関する情報を効率的に取得することを可能とするキャッシュミス推定プログラム、キャッシュミス推定方法及び情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
実施の形態の一つの態様によれば、プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるＣＰＵにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第１回数式を生成し、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第２回数式を生成し、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第３回数式を、前記ソースコード上の位置毎に生成し、前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第４回数式を生成し、前記第１回数式から前記第２回数式を減算した式と、前記第３回数式から前記第４回数式を減算した式とを生成する、処理をコンピュータに実行させる。
【発明の効果】
【００１１】
一つの側面によれば、プログラムの実行中に発生したキャッシュミスに関する情報を効率的に取得することを可能とする。
【図面の簡単な説明】
【００１２】
【図１】図１は、情報処理システム１０の構成を示す図である。
【図２】図２は、プログラム情報１３１について説明する図である。
【図３】図３は、データ情報１３２について説明する図である。
【図４】図４は、位置情報１３３について説明する図である。
【図５】図５は、キャッシュ情報１３４の具体例を説明する図である。
【図６】図６は、ループ情報１３５の具体例を説明する図である。
【図７】図７は、配列情報１３６の具体例を説明する図である。
【図８】図８は、情報処理装置１のハードウエア構成を説明する図である。
【図９】図９は、第１の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
【図１０】図１０は、第１の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
【図１１】図１１は、第１の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
【図１２】図１２は、第１の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
【図１３】図１３は、第１の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
【図１４】図１４は、第１の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
【図１５】図１５は、第１の実施の形態におけるキャッシュミス推定処理を説明する図である。
【図１６】図１６は、式利用処理を説明するフローチャートである。
【図１７】図１７は、式利用処理を説明する図である。
【図１８】図１８は、式利用処理を説明する図である。
【発明を実施するための形態】
【００１３】
［情報処理システムの構成］
図１は、情報処理システム１０の構成を示す図である。図１に示す情報処理システム１０は、情報処理装置１（以下、キャッシュミス推定装置１とも呼ぶ）と、記憶装置１ａとを有する。情報処理装置１は、例えば、インターネットやイントラネット等からなるネットワークＮＷを介して研究者端末１１にアクセスすることが可能である。
【００１４】
情報処理装置１は、例えば、アプリケーションプログラムを実行中のＨＰＣシステムにおいて発生するキャッシュミスの回数等を推定する式（以下、キャッシュミス推定式とも呼ぶ）の生成を含む処理（以下、キャッシュミス推定処理とも呼ぶ）を実行する。情報処理装置１は、例えば、ＨＰＣシステムが動作する物理マシンとは異なる物理マシンである。
【００１５】
記憶装置１ａは、例えば、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）やＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等からなる外部ディスク装置である。具体的に、記憶装置１ａは、例えば、情報処理装置１がキャッシュミス推定処理を実行する際に参照する各種情報を記憶する。また、記憶装置１ａは、例えば、情報処理装置１が生成したキャッシュミス推定式を記憶する。なお、記憶装置１ａは、情報処理装置１の内部に設けられたディスク装置であってもよい。
【００１６】
研究者端末１１は、例えば、事業者が必要な情報の入力を行う端末である。そして、研究者端末１１は、事業者による情報の入力があった場合、例えば、入力された情報を情報処理装置１に送信する。
【００１７】
［各種情報の具体例］
次に、情報処理装置１がキャッシュミス推定処理を実行する際に参照する各種情報について説明を行う。なお、以下、各情報（プログラム情報１３１、データ情報１３２、位置情報１３３、キャッシュ情報１３４、ループ情報１３５及び配列情報１３６）は、キャッシュミス推定処理が実行される前に予め記憶装置１ａに記憶されているものとして説明を行う。
【００１８】
［プログラム情報］
初めに、ＨＰＣシステムが実行するアプリケーションプログラムのソースコードであるプログラム情報１３１について説明を行う。図２は、プログラム情報１３１について説明する図である。
【００１９】
具体的に、ステップＳ１では、ループ変数ｉが０からＸ−１までの間においてインクリメントする毎に、配列Ａの要素に０を設定する処理が行われる。また、ステップＳ２では、ループ変数ｊが０からＹ−１までの間においてインクリメントする毎に、配列Ｂの要素に０を設定する処理が行われる。さらに、ステップＳ３では、ループ変数ｋが０からＺ−１までの間においてインクリメントする毎に、配列Ａの要素に設定されている値を配列Ｃの要素に設定する処理が行われる。なお、パラメータ変数Ｘ、Ｙ及びＺは、キャッシュ推定式によるキャッシュミスの回数の推定が行われる際に、キャッシュ推定式を利用する者（例えば、研究者）によって入力される変数である。
【００２０】
［データ情報］
次に、図２で説明したソースコード（プログラム情報１３１）における各配列に割当てられるメモリ内のサイズ及びアドレスを含むデータ情報１３２について説明を行う。図３は、データ情報１３２について説明する図である。
【００２１】
図３に示すデータ情報１３２において、配列Ａの開始アドレスμＡが０であり、配列Ａの要素（以下、配列要素とも呼ぶ）あたりのバイト数βＡが８であり、配列Ａの要素総数αＡが１００である。また、図３に示すデータ情報１３２において、配列Ｂの開始アドレスμＢが８００であり、配列Ｂの要素あたりのバイト数βＢが８であり、配列Ｂの要素総数αＢが１００である。さらに、図３に示すデータ情報１３２において、配列Ｃの開始アドレスμＣが１６００であり、配列Ｃの要素あたりのバイト数βｃが８であり、配列Ａの要素総数αｃが１００である。
【００２２】
［位置情報］
次に、図２で説明したソースコードにおける特定の位置を示す位置情報１３３（以下、特定位置情報１３３とも呼ぶ）について説明を行う。位置情報１３３は、例えば、図２で説明したソースコードにおいて、研究者によってキャッシュミスに関する調査が行われる位置（キャッシュミスの発生回数の推定が行われる位置）を示す情報である。図４は、位置情報１３３について説明する図である。
【００２３】
図４に示す位置情報１３３は、図２で説明したプログラム情報１３１において、「文」に対応して「Ｓ３」が設定され、「サイド」に対応して「ｒｉｇｈｔ」が設定され、「位置」に対応して「１」が設定されている。すなわち、図４に示す位置情報１３３は、例えば、ステップＳ３に記述された式の右辺に含まれる項のうち、左端から１番目に記述された項を示す位置におけるキャッシュミスの調査が行われることを示している。
【００２４】
［キャッシュ情報］
次に、プログラムが実行されるＣＰＵにおけるキャッシュの連想数を含むキャッシュ情報１３４について説明を行う。図５は、キャッシュ情報１３４の具体例を説明する図である。
【００２５】
図５に示すキャッシュ情報１３４は、キャッシュの連想数Ａが２であり、キャッシュのブロックサイズＢが３２であり、キャッシュのセット数Ｓが４であることを示している。
【００２６】
［ループ情報］
次に、図２で説明したソースコードにおけるループ変数と、各ループ変数に対応するパラメータ変数とを含むループ情報１３５について説明を行う。図６は、ループ情報１３５の具体例を説明する図である。
【００２７】
図６に示すループ情報１３５は、ループ変数ｉが０からＸ−１までの間においてインクリメントし、ループ変数ｊが０からＹ−１までの間においてインクリメントし、ループ変数ｋが０からＺ−１までの間においてインクリメントすることを示している。
【００２８】
［配列情報］
次に、図２で説明したソースコード上の位置と、その位置を囲むループに関連するループ変数を示す情報と、その位置の配列の要素を特定する情報とを含む配列情報１３６について説明を行う。図７は、配列情報１３６の具体例を説明する図である。
【００２９】
図７に示す配列情報１３６における「位置番号」が「Ｐ０」である情報には、「文」として「Ｓ１」が設定され、「サイド」として「ｌｅｆｔ」が設定され、「位置」として「１」が設定され、「配列」として「Ａ」が設定されている。さらに、図７に示す配列情報１３６における「位置番号」が「Ｐ０」である情報には、「配列の添え字式」として「ｉ」が設定され、「関連するループ変数」として「ｉ」が設定されている。すなわち、図７に示す配列情報１３６のうち、「位置番号」が「Ｐ０」である情報は、ステップＳ１に記述された式の左辺に含まれる項のうち、左端から１番目に記述された項が配列Ａであることを示している。また、図７に示す配列情報１３６のうち、「位置番号」が「Ｐ０」である情報は、配列Ａの添え字式及びループ変数がｉであることを示している。図７に含まれる他の情報については説明を省略する。
【００３０】
［情報処理装置のハードウエア構成］
次に、情報処理装置１のハードウエア構成について説明する。図８は、情報処理装置１のハードウエア構成を説明する図である。
【００３１】
情報処理装置１は、プロセッサであるＣＰＵ１０１と、メモリ１０２と、外部インターフェース（Ｉ／Ｏユニット）１０３と、記憶媒体（ストレージ）１０４とを有する。各部は、バス１０５を介して互いに接続される。
【００３２】
記憶媒体１０４は、記憶媒体１０４内のプログラム格納領域（図示しない）に、キャッシュミス推定処理を行うためのプログラム１１０を記憶する。
【００３３】
ＣＰＵ１０１は、図８に示すように、プログラム１１０の実行時に、プログラム１１０を記憶媒体１０４からメモリ１０２にロードし、プログラム１１０と協働してキャッシュミス推定処理を行う。具体的に、ＣＰＵ１０１は、プログラム１１０と協働することにより、キャッシュミス推定式を生成する式生成部１２１と、キャッシュミス推定式を利用してキャッシュミスの回数の推定を行う式評価部１２２として動作する。
【００３４】
記憶媒体１０４は、例えば、キャッシュミス推定処理を行う際に用いられる情報（図２で説明したプログラム情報１３１等）を記憶する情報格納領域１３０（以下、記憶部１３０とも呼ぶ）を有する。また、外部インターフェース１０３は、研究者端末１１等と通信を行う。なお、図１で説明した記憶部１ａは、記憶媒体１０４に対応するものであってよい。
【００３５】
[第１の実施の形態］
次に、第１の実施の形態について説明する。図９から図１４は、第１の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。また、図１５は、第１の実施の形態におけるキャッシュミス推定処理を説明する図である。なお、以下、Ｓ１からＳ１４までの処理を行う式生成部１２１を第１式生成部１２１とも呼び、Ｓ２１からＳ３３までの処理を行う式生成部１２１を第２式生成部１２１とも呼び、Ｓ３４の処理を行う式生成部１２１を第３式生成部１２１とも呼ぶ。
【００３６】
式生成部１２１は、式生成タイミングになるまで待機する（Ｓ１のＮＯ）。式生成タイミングは、例えば、研究者が研究者端末１１を介して情報処理装置１にキャッシュミス推定処理を行う旨の入力を行ったタイミングでよい。
【００３７】
そして、式生成タイミングになった場合（Ｓ１のＹＥＳ）、式生成部１２１は、プログラム情報１３１のソースコード上の位置とその位置を囲むループに関連するループ変数を示す情報とその位置の配列の要素を特定する情報とを含む配列情報１３６と、プログラム情報１３１のソースコード上の特定の位置を示す位置情報１３３とに基づき、特定の位置に対応する特定の配列の特定する（Ｓ２）。
【００３８】
具体的に、図４に示す位置情報１３３では、「文」として「Ｓ３」が設定され、「サイド」として「ｒｉｇｈｔ」が設定され、「位置」として「１」が設定されている。そして、図７に示す配列情報１３６において、「文」に「Ｓ３」が設定され、「サイド」に「ｒｉｇｈｔ」が設定され、「位置」に「１」が設定された情報は、「位置情報」に「Ｐ２」が設定された情報である。そのため、式生成部１２１は、特定の位置としてＰ２を特定する。また、「位置情報」に「Ｐ２」が設定された情報の「配列」には「Ａ」が設定されている。そのため、式生成部１２１は、Ｓ２の処理において、特定の配列として配列Ａを特定する。
【００３９】
続いて、式生成部１２１は、Ｓ２の処理で特定した特定の配列に対応するソースコード上の位置毎に、特定の配列に対応する情報を配列情報１３６から取得する（Ｓ３）。
【００４０】
具体的に、図７に示す配列情報１３６において、「配列」に「Ａ」が設定された情報は、「位置番号」に「Ｐ０」及び「Ｐ２」が設定された情報である。そのため、式生成部１２１は、特定の配列である配列Ａが記述された位置として、Ｐ０及びＰ２（以下、特定の位置であるＰ２と区別するためにＰ２´とも呼ぶ）を特定する。そして、式生成部１２１は、「位置情報」が「Ｐ０」及び「Ｐ２」である情報を配列情報１３６から取得する。
【００４１】
すなわち、特定の位置であるＰ２におけるアクセスがキャッシュヒットとなるためには、そのアクセス対象のデータを、プログラムの実行において先行するアクセスがキャッシュに格納している必要がある。そのため、式生成部１２１は、Ｓ３の処理において、特定の位置であるＰ２におけるアクセス対象のデータをキャッシュに格納した可能性がある位置として、Ｐ０及びＰ２´を特定する。
【００４２】
続いて、式生成部１２１は、Ｓ３の処理で取得した特定の配列に対応する情報等に基づいて、特定の配列においてアクセスが行われる場合に、そのアクセス対象のデータがキャッシュに格納されている条件を算出するヒット条件式を、特定の配列に対応するソースコード上の位置毎に生成する（Ｓ４）。なお、以下、ヒット条件式等の各式は、テキスト形式によって凸多面体を表現する凸多面体フォーマットのデータとして生成されるものとして説明を行う。
【００４３】
具体的に、式生成部１２１は、Ｓ３の処理で取得した情報のうちの「位置情報」が「Ｐ０」である情報と、図４で説明した位置情報１３３と、図６で説明したループ情報１３５と、図３で説明したデータ情報１３２と、図５で説明したキャッシュ情報１３４とを、キャッシュの状態集合（振る舞い）を定式化するプログラムに入力する。そして、キャッシュの振る舞いを定式化するプログラムによる出力結果を、下記の式（１）に示すように、Ｐ０とＰ２との関係におけるヒット条件式Γ１とする。なお、式（１）には、キャッシュセットを識別する変数ｓと、キャッシュに格納されたデータを識別する変数ｗとが含まれている。
【００４４】
【数１】
0006730587.tif 000002
【００４５】
また、式生成部１２１は、Ｓ３の処理で取得した情報のうちの「位置情報」が「Ｐ２」である情報と、図４で説明した位置情報１３３と、図６で説明したループ情報１３５と、図３で説明したデータ情報１３２と、図５で説明したキャッシュ情報１３４とを、キャッシュの振る舞いを定式化するプログラムに入力する。そして、式生成部１２１は、キャッシュの振る舞いを定式化するプログラムによる出力結果を、下記の式（２）に示すように、Ｐ２´とＰ２との関係におけるヒット条件式Γ２とする。なお、式（２）において、Ｐ２´に対応するループ変数ｋをループ変数ｋ´と表記する。
【００４６】
【数２】
0006730587.tif 000003
【００４７】
そして、式生成部１２１は、Ｓ４の処理で生成したヒット条件式に基づき、キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、特定の配列に対応するソースコード上の位置毎に生成する（Ｓ５）。
【００４８】
すなわち、Ｓ４の処理で生成したヒット条件式を満たすアクセスが複数存在する場合において、特定の配列におけるアクセスのキャッシュヒットに寄与するアクセスは、特定の配列におけるアクセスに最も近いアクセスである。そのため、式生成部１２１は、ヒット条件式に含まれるループ変数のリストの辞書式順序の値が最大となる場合のヒット条件式を、ヒットソース候補式とする。
【００４９】
具体的に、式生成部１２１は、ヒット条件式Γ１（凸多面体フォーマットのデータ）と、ヒット条件式Γ１に含まれるループ変数のリストに含まれるループ変数ｉと、ヒット条件式Γ１に含まれるパラメータ変数のリストに含まれるパラメータ変数Ｘ及びＺとを、ＰＩＰ処理として利用可能なパラメトリック整数線形計画法を実行するプログラムに入力する。ＰＩＰ処理は、ヒット条件式に含まれるループ変数のリストにおける辞書式順序の最大値を表す凸多面体フォーマットのデータリストを出力する処理である。そして、式生成部１２１は、パラメトリック整数線形計画法を実行するプログラムによる出力結果を、下記の式（３）及び式（４）に示すように、ヒット条件式Γ１に対するヒットソース候補式Γ１，１´及びΓ１，２´としてそれぞれ生成する。
【００５０】
【数３】
0006730587.tif 000004
【００５１】
【数４】
0006730587.tif 000005
【００５２】
同様に、式生成部１２１は、下記の式（５）に示すように、Ｓ４の処理で生成したヒット条件式Γ２に対するヒットソース候補式Γ２，１´を生成する。
【００５３】
【数５】
0006730587.tif 000006
【００５４】
続いて、式生成部１２１は、図１０に示すように、Ｓ５の処理で生成したヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成する（Ｓ１１）。
【００５５】
すなわち、Ｓ５の処理において、式生成部１２１は、プログラムの実行において先行するアクセスの位置（例えば、Ｐ０及びＰ２´）を個々に考慮している。しかしながら、これらの位置に対応して生成されたヒットソース候補式が示すアクセスには、重複部分が存在する可能性がある。そのため、式生成部１２１は、Ｓ１１の処理において、ヒットソース候補式の重複部分の除去を行う。
【００５６】
具体的に、式生成部１２１は、Ｓ５の処理で生成した凸多面体フォーマットのデータリストであるヒットソース候補式Γ１，１´、Γ１，２´及びΓ２，１´を、ｄｉｓｊｏｉｎｔ処理を実行するプログラムに入力する。ｄｉｓｊｏｉｎｔ処理は、凸多面体フォーマットのデータリストから重複を除去する処理である。そして、式生成部１２１は、ｄｉｓｊｏｉｎｔ処理を実行するプログラムによる出力結果を、下記の式（６）から式（１０）に示すように、それぞれヒットソース式Ｃ１、Ｃ２、Ｃ３、Ｃ４及びＣ５とする。
【００５７】
【数６】
0006730587.tif 000007
【００５８】
【数７】
0006730587.tif 000008
【００５９】
【数８】
0006730587.tif 000009
【００６０】
【数９】
0006730587.tif 000010
【００６１】
【数１０】
0006730587.tif 000011
【００６２】
なお、式生成部１２１は、Ｓ１１の処理において、ヒットソース候補式Γ１，１´、Γ１，２´及びΓ２，１´に含まれるループ変数ｉ及びループ変数ｋ´（Ｐ０及びＰ２´に対応するループ変数）を、ループ変数ｋに置き換えることによって消去してから、ｄｉｓｊｏｉｎｔ処理を実行する。これにより、ヒットソース候補式Γ１，１´、Γ１，２´及びΓ２，１´は、それぞれ同じ変数（ｋ、ｗ、ｓ）と同じパラメータ変数（Ｘ、Ｙ、Ｚ）のみを含む凸多面体フォーマットのデータとして表現される。
【００６３】
そして、式生成部１２１は、Ｓ２の処理で特定した特定の配列に対応するソースコード上の位置を囲むループに関連するループ変数と、そのループ変数に対応するパラメータ変数とから、そのループ変数が取り得る値の範囲を示す変数範囲式を生成する（Ｓ１２）。
【００６４】
具体的に、式生成部１２１は、例えば、コンパイラがソースコードのコンパイルを実行する場合において利用されるプログラム解析処理を実行するプログラムに、位置情報１３３とループ情報１３５とを入力する。そして、式生成部１２１は、プログラム解析処理を実行するプログラムによる出力結果を、下記の式（１１）に示すように、ループ変数ｋが取り得る値の範囲を示す変数範囲式Ｇとする。
【００６５】
【数１１】
0006730587.tif 000012
【００６６】
その後、式生成部１２１は、Ｓ１２の処理で生成した変数範囲式と、その変数範囲式に含まれるループ変数を特定する情報と、その変数範囲式に含まれるパラメータ変数を特定する情報とから、Ｓ２の処理で特定した特定の位置の実行回数を示す第１回数式を生成する（Ｓ１３）。
【００６７】
具体的に、式生成部１２１は、Ｓ１２の処理で算出した変数範囲式Ｇと、変数範囲式Ｇにループ変数ｋとパラメータ変数Ｚとが含まれることを示す情報とを、ｖｏｌｕｍｅ処理として利用可能なパラメトリック離散体積計算手法を実行するプログラムに入力する。ｖｏｌｕｍｅ処理は、ループ変数の取り得る値の組み合わせの個数を表す式を生成する処理である。そして、式生成部１２１は、パラメトリック離散体積計算手法を実行するプログラムによる出力結果であるループ変数ｋの値の個数を表す条件と式の対のリストを、下記の式（１２）に示すように、第１回数式ＶＧとする。
【００６８】
【数１２】
0006730587.tif 000013
【００６９】
続いて、式生成部１２１は、Ｓ１１の処理で生成したヒットソース式と、そのヒットソース式に含まれるループ変数を特定する情報と、そのヒットソース式に含まれるパラメータ変数を特定する情報とから、Ｓ２の処理で特定した特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュに格納されている回数を示す第２回数式を生成する（Ｓ１４）。
【００７０】
具体的に、式生成部１２１は、Ｓ１３の処理と同様に、Ｓ１１の処理で生成したヒットソース式Ｃ１と、ヒットソース式Ｃ１にループ変数ｋとパラメータ変数Ｘとパラメータ変数Ｚとが含まれることを示す情報とを、パラメトリック離散体積計算手法を実行するプログラムに入力する。そして、式生成部１２１は、下記の式（１３）に示すように、パラメトリック離散体積計算手法を実行するプログラムによる出力結果であるループ変数ｋの値の個数を表す条件と式の対のリストを、第２回数式ＶＣ１とする。
【００７１】
【数１３】
0006730587.tif 000014
【００７２】
同様に、式生成部１２１は、Ｓ１１の処理で生成したヒットソース式Ｃ２、ヒットソース式Ｃ３、ヒットソース式Ｃ４及びヒットソース式Ｃ５から、それぞれ第２回数式ＶＣ２、第２回数式ＶＣ３、第２回数式ＶＣ４及び第２回数式ＶＣ５を生成する。
【００７３】
すなわち、式生成部１２１は、Ｓ１３の処理において、プログラム情報１３１のソースコード上の特定の位置における実行回数（特定の位置において行われるデータに対するアクセス回数）を示す式を生成する。また、式生成部１２１は、Ｓ１４の処理において、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュに格納されている回数を示す式を生成する。そして、式生成部１２１は、後述するように、Ｓ１３の処理で生成した式からＳ１４の処理で生成した式を減算した式を生成する。これにより、式生成部１２１は、後述するように、特定の位置の実行が行われる場合において、アクセス対象のデータが一度もキャッシュに格納されていないためにキャッシュミスになった回数を推定することが可能になる（以下、このキャッシュミスを初期参照ミスとも呼ぶ）。
【００７４】
続いて、式生成部１２１は、図１１に示すように、Ｓ１１の処理で生成したヒットソース式等に基づき、Ｓ２の処理で特定した特定の配列におけるアクセス対象のデータをキャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、ソースコード上の位置毎に生成する（Ｓ２１）。
【００７５】
すなわち、特定の位置の実行が行われる場合において発生するキャッシュミスには、アクセス対象のデータが以前はキャッシュに格納されていたが、その後のアクセスによってキャッシュから消去されているために発生するキャッシュミスが含まれる。そのため、式生成部１２１は、Ｓ２１以降の処理において、アクセス対象のデータが消去されたことに伴ってキャッシュミスになった回数を推定するための式の生成を行う（以下、このキャッシュミスを競合ミスとも呼ぶ）。
【００７６】
具体的に、式生成部１２１は、例えば、Ｓ１１の処理で生成したヒットソース式Ｃ４と、図４で説明した位置情報１３３と、図６で説明したループ情報１３５と、図３で説明したデータ情報１３２と、図５で説明したキャッシュ情報１３４とを、キャッシュの振る舞いを定式化するプログラムに入力する。そして、式生成部１２１は、下記の式（１４）から式（１６）に示すように、キャッシュの振る舞いを定式化するプログラムの出力結果である、競合ミス要因候補式Ｈ４，１、Ｈ４，２及びＨ４，３をそれぞれ生成する。なお、式（１４）から式（１６）には、Ｓ２の処理で特定した特定の配列におけるアクセス対象のデータをキャッシュから消去するアクセスの候補を表すループ変数ｘ（ループ変数ｉ、ｊ及びｋの総称である変数）と、各データを識別するラップアラウンド変数（以下、識別変数とも呼ぶ）であるラップアラウンド変数Ｑとが含まれている。
【００７７】
【数１４】
0006730587.tif 000015
【００７８】
【数１５】
0006730587.tif 000016
【００７９】
【数１６】
0006730587.tif 000017
【００８０】
そして、式生成部１２１は、ヒットソース式Ｃ１、ヒットソース式Ｃ２、ヒットソース式Ｃ３及びヒットソース式Ｃ５についてもＳ１３の処理を行う。
【００８１】
その後、式生成部１２１は、Ｓ２１の処理で生成した競合ミス要因候補式それぞれが示すアクセスの重複を排除して、特定の位置におけるアクセス対象のデータをキャッシュから消去するアクセスを示す競合ミス要因式を、ソースコード上の位置毎に生成する（Ｓ２２）。以下、Ｓ２２の処理の詳細について説明を行う。
【００８２】
[Ｓ２２の処理の詳細］
図１３は、Ｓ２２の処理の詳細を説明する図である。式生成部１２１は、Ｓ２１で生成した競合ミス要因候補式に含まれるループ変数のうち、特定の配列におけるアクセス対象のデータをキャッシュから消去するアクセスを表すループ変数を消去する（Ｓ４１）。すなわち、式生成部１２１は、キャッシュミスの回数を推定するために不要であるループ変数の消去（他のループ変数への置き換え）を行う。
【００８３】
その後、式生成部１２１は、Ｓ４１の処理でループ変数を消去した競合ミス要因候補式それぞれが示すアクセスの重複を排除した競合ミス要因候補式を生成する（Ｓ４２）。すなわち、Ｓ２１の処理で生成された競合ミス要因候補式は、ソースコードにおいてアクセスを行う可能性のある位置それぞれにおけるアクセスから生成される。そして、これらのアクセスは、同じキャッシュセットの同じデータに対するアクセスが含まれている場合がある。そのため、式生成部１２１は、Ｓ４２の処理において、Ｓ４１の処理でループ変数を消去した競合ミス要因候補式それぞれの重複の排除を行う。
【００８４】
具体的に、式生成部１２１は、競合ミス要因候補式Ｈ４，１と、特定の位置であるＰ２におけるアクセス対象のデータをキャッシュから消去するアクセスを表すループ変数であるループ変数ｘを特定する情報とを、ｐｒｏｊｅｃｔｏｕｔ処理を実行するプログラムに入力する。ｐｒｏｊｅｃｔｏｕｔ処理は、凸多面体フォーマットのデータリストからループ変数を消去する処理である。そして、式生成部１２１は、ｐｒｏｊｅｃｔｏｕｔ処理を実行するプログラムの出力結果を、ループ変数ｘを消去した競合ミス要因候補式Ｈ４，１´とする。同様に、式生成部１２１は、競合ミス要因候補式Ｈ４，２及びＨ４，３から、ループ変数ｘを消去した競合ミス要因候補式Ｈ４，２´及びＨ４，３´をそれぞれ生成する。
【００８５】
その後、式生成部１２１は、Ｓ４２の処理において、ループ変数ｘを消去した競合ミス要因候補式Ｈ４，１´、Ｈ４，２´及びＨ４，３´を、ｄｉｓｊｏｉｎｔ処理を実行するプログラムに入力する。そして、式生成部１２１は、ｄｉｓｊｏｉｎｔ処理を実行するプログラムによる出力結果を、下記の式（１７）、式（１８）及び式（１９）に示すように、重複を排除した競合ミス要因候補式Ｊ４，１、Ｊ４，２及びＪ４，３とする。
【００８６】
【数１７】
0006730587.tif 000018
【００８７】
【数１８】
0006730587.tif 000019
【００８８】
【数１９】
0006730587.tif 000020
【００８９】
図１３に戻り、式生成部１２１は、Ｓ４２の処理で重複を排除した競合ミス要因候補式に含まれるループ変数のうち、アクセス対象のデータを識別する識別変数を消去する（Ｓ４３）。そして、式生成部１２１は、Ｓ４３の処理で識別変数を消去した競合ミス要因候補式それぞれが示すアクセスの重複を排除した競合ミス要因式を生成する（Ｓ４４）。
【００９０】
すなわち、式生成部１２１は、Ｓ４２の処理において、Ｓ２１の処理で生成された競合ミス要因候補式から、ループ変数ｋとラップアラウンド変数Ｑとの組み合わせについての重複を排除しているが、ループ変数ｋのみを考慮した場合の重複についても排除を行う必要がある。そのため、式生成部１２１は、Ｓ４３の処理において、ラップアラウンド変数Ｑの消去を行い、Ｓ４４の処理において、ループ変数ｋのみを考慮した場合の重複の排除を行う。
【００９１】
具体的に、式生成部１２１は、重複を排除した競合ミス要因候補式Ｊ４，１と、アクセス対象のデータを識別する識別変数であるラップアラウンド変数Ｑとを、ｐｒｏｊｅｃｔｏｕｔ処理を実行するプログラムに入力する。そして、式生成部１２１は、下記の式（２０）に示すように、ｐｒｏｊｅｃｔｏｕｔ処理を実行するプログラムの出力結果を、競合ミス要因式Ｊ４，１´とする。同様に、式生成部１２１は、下記の式（２１）及び式（２２）に示すように、競合ミス要因候補式Ｊ４，２及びＪ４，３から、ラップアラウンド変数Ｑを消去した競合ミス要因式Ｊ４，２´及びＪ４，３´をそれぞれ生成する。なお、式（２１）には、ｐｒｏｊｅｃｔｏｕｔ処理によって自動的に導入される変数（作業用の変数）である変数ｅ０が含まれている。
【００９２】
【数２０】
0006730587.tif 000021
【００９３】
【数２１】
0006730587.tif 000022
【００９４】
【数２２】
0006730587.tif 000023
【００９５】
その後、式生成部１２１は、Ｓ４４の処理において、競合ミス要因式Ｊ４，１´、Ｊ４，２´及びＪ４，３´を、ｄｉｓｊｏｉｎｔ処理を実行するプログラムに入力する。そして、式生成部１２１は、ｄｉｓｊｏｉｎｔ処理を実行するプログラムによる出力結果を、下記の式（２３）、式（２４）及び式（２５）に示すように、重複を排除した後の競合ミス要因式Ｊ４，１´´、Ｊ４，２´´及びＪ４，３´´とする。
【００９６】
【数２３】
0006730587.tif 000024
【００９７】
【数２４】
0006730587.tif 000025
【００９８】
【数２５】
0006730587.tif 000026
【００９９】
図１１に戻り、式生成部１２１は、Ｓ２２の処理で生成した競合ミス要因式等から、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第３回数式を、ソースコード上の位置毎に生成する（Ｓ２３）。
【０１００】
具体的に、式生成部１２１は、重複を排除した後の競合ミス要因式Ｊ４，１´´と、重複を排除した後の競合ミス要因式Ｊ４，１´´にループ変数ｋとパラメータ変数Ｘとパラメータ変数Ｚとが含まれることを示す情報とを、ｖｏｌｕｍｅ処理として利用可能なパラメトリック離散体積計算手法を実行するプログラムに入力する。そして、式生成部１２１は、パラメトリック離散体積計算手法を実行するプログラムによる出力結果であるループ変数ｋの値の個数を表す条件と式の対のリストを、下記の式（２６）及び式（２７）に示すように、第３回数式ＶＪ４，１´´とする。
【０１０１】
【数２６】
0006730587.tif 000027
【０１０２】
【数２７】
0006730587.tif 000028
【０１０３】
同様に、式生成部１２１は、重複を排除した後の競合ミス要因式Ｊ４，２´´及び重複を排除した後の競合ミス要因式Ｊ４，３´´から、それぞれ第３回数式ＶＪ４，２´´及び第３回数式ＶＪ４，３´´を生成する。
【０１０４】
その後、式生成部１２１は、キャッシュの連想数に基づき、競合ミス要因式毎に、各競合ミス要因式をアクセス対象のデータの種類の数毎のアクセスを示す競合ミス要因分割式にそれぞれ分割する（Ｓ２４）。
【０１０５】
すなわち、競合ミス要因式が示すアクセスによってキャッシュにデータが格納された場合であっても、競合ミス要因式が示すアクセスによってキャッシュに格納されたデータの種類の数がキャッシュの連想数よりも小さい場合、特定の位置におけるアクセスによるキャッシュミスは発生しない。この点、Ｓ２３の処理で生成した第３回数式には、競合ミス要因式が示すアクセスによってキャッシュに格納されたデータの数がキャッシュの連想数よりも小さい場合について考慮されていない。そのため、式生成部１２１は、Ｓ２４以降の処理において、競合ミス要因式が示すアクセスによってキャッシュに格納されたデータの数がキャッシュの連想数よりも小さいことにより、キャッシュミスにならなかった回数の推定するための式の生成を行う。これにより、式生成部１２１は、後述するように、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数をより精度良く推定することが可能になる。
【０１０６】
具体的に、式生成部１２１は、Ｓ２４の処理において、競合ミス要因式をキャッシュの連想数以下の数毎に分割する。さらに具体的に、式生成部１２１は、図６のキャッシュ情報１３４に示すように、キャッシュの連想数Ａが２である場合、競合ミス要因式Ｊ４，１´を、１個の種類のデータをキャッシュに格納する場合に対応する競合ミス要因分割式ΨＪ４，１´＝１と、０個の種類のデータをキャッシュに格納する場合に対応する競合ミス要因分割式ΨＪ４，１´＝０とを含む複数の式に分割する。同様に、式生成部１２１は、競合ミス要因式Ｊ４，２´及び競合ミス要因式Ｊ４，３´についても分割を行う。以下、Ｓ２４の処理の詳細について説明を行う。
【０１０７】
[Ｓ２４の処理の詳細］
図１４は、Ｓ２４の処理の詳細を説明する図である。式生成部１２１は、競合ミス要因式に対応するアクセス対象のデータの種類の数毎に、競合ミス要因候補式を、アクセス対象のデータを識別する識別変数を含む第１の式と識別変数を含まない第２の式とに分類する（Ｓ５１）。すなわち、式生成部１２１は、キャッシュの連想数以下の数毎に、競合ミス要因候補式の分割を行う。
【０１０８】
具体的に、式生成部１２１は、競合ミス要因式Ｊ４，１´を、下記の式（２８）及び式（２９）に示すように、ラップアラウンド変数Ｑを含む第１の式とラップアラウンド変数Ｑを含まない第２の式とに分類する。
【０１０９】
【数２８】
0006730587.tif 000029
【０１１０】
【数２９】
0006730587.tif 000030
【０１１１】
その後、式生成部１２１は、Ｓ５１の処理において分類した第１の式を、競合ミス要因式に対応するアクセス対象のデータの種類の数と同じ数に複製する（Ｓ５２）。そして、式生成部１２１は、データの種類の数毎に、Ｓ５２の処理で複製した第１の式それぞれに含まれる識別変数を、第１の式毎に異なる識別変数に変更する（Ｓ５３）。
【０１１２】
具体的に、式生成部１２１は、図６のキャッシュ情報１３４に示すように、キャッシュの連想数Ａが２である場合、Ｓ５１の処理において分類した第１の式を２つの式に複製する。そして、式生成部１２１は、下記の式（３０）及び式（３１）に示すように、複製した式に含まれるラップアラウンド変数Ｑを、それぞれラップアラウンド変数Ｑ１及びラップアラウンド変数Ｑ２に変更する。
【０１１３】
【数３０】
0006730587.tif 000031
【０１１４】
【数３１】
0006730587.tif 000032
【０１１５】
続いて、式生成部１２１は、競合ミス要因式に対応するアクセス対象のデータの種類の数毎に、Ｓ５３の処理で識別変数を変更した第１の式それぞれと、Ｓ５１の処理で分類された第２の式と、変更された識別変数それぞれの大小関係を示す式とから、Ｓ５３の処理で変更された識別変数を消去した第３の式を生成する（Ｓ５４）。
【０１１６】
具体的に、式生成部１２１は、ラップアラウンド変数Ｑ１を含む第１の式と、ラップアラウンド変数Ｑ２を含む第２の式と、ラップアラウンド変数Ｑ１とラップアラウンド変数Ｑ２との大小関係を示す式と、ラップアラウンド変数Ｑ１とラップアラウンド変数Ｑ２とを特定する情報とを、変数を消去するプログラムに入力する。そして、式生成部１２１は、変数を消去するプログラムによる出力結果を、競合ミス要因式から分割された式であって、競合ミス要因式に対応するアクセス対象のデータの種類の数が２以上である場合の式である第３の式ΨＪ４，１´≧２として取得する。
【０１１７】
そして、式生成部１２１は、データの種類の数毎に、各データの種類の数に対応する第３の式と、各データの種類の数よりも１大きい数に対応する第３の式の差分を、各データの種類の数に対応する競合要因分割式として生成する（Ｓ５５）。
【０１１８】
具体的に、式生成部１２１は、Ｓ５４の処理で取得された第３の式ΨＪ４，１´≧２と、第３の式ΨＪ４，１´≧１とを、式が示す範囲の差分を算出するプログラムに入力する。そして、式生成部１２１は、下記の式（３２）に示すように、式が示す範囲の差分を算出するプログラムによる出力結果を、競合ミス要因分割式ΨＪ４，１´＝１として取得する。
【０１１９】
また、式生成部１２１は、第３の式ΨＪ４，１´≧１と、第３の式ΨＪ４，１´≧０（ヒットソース式Ｃ４）とを、式の差分を算出するプログラムに入力する。そして、式生成部１２１は、下記の式（３３）に示すように、式の差分を算出するプログラムによる出力結果を、競合ミス要因分割式ΨＪ４，１´＝０として取得する。
【０１２０】
【数３２】
0006730587.tif 000033
【０１２１】
【数３３】
0006730587.tif 000034
【０１２２】
図１２に戻り、式生成部１２１は、Ｓ２２の処理で生成した競合ミス要因式それぞれに対応する競合ミス要因分割式のデータの種類の数の総和が、キャッシュの連想数を下回る競合ミス要因分割式の組み合わせを特定する（Ｓ３１）。
【０１２３】
具体的に、競合ミス要因分割式ΨＪ４，１´＝０と、競合ミス要因分割式ΨＪ４，１´＝１と、競合ミス要因分割式ΨＪ４，２´＝０と、競合ミス要因分割式ΨＪ４，２´＝１と、競合ミス要因分割式ΨＪ４，３´＝０とが存在する場合、式生成部１２１は、競合ミス要因分割式ΨＪ４，１´＝１と、競合ミス要因分割式ΨＪ４，２´＝０と、競合ミス要因分割式ΨＪ４，３´＝０との組み合わせを特定する。また、式生成部１２１は、この場合、競合ミス要因分割式ΨＪ４，１´＝０と、競合ミス要因分割式ΨＪ４，２´＝１と、競合ミス要因分割式ΨＪ４，３´＝０との組み合わせを特定する。
【０１２４】
そして、式生成部１２１は、Ｓ３１の処理で特定した組み合わせに含まれる競合ミス要因分割式それぞれにおいて共通する式である競合ミス要因共通式を、競合ミス要因式毎に生成する（Ｓ３２）。
【０１２５】
具体的に、式生成部１２１は、競合ミス要因分割式ΨＪ４，１´＝１と、競合ミス要因分割式ΨＪ４，２´＝０と、競合ミス要因分割式ΨＪ４，３´＝０とを、式が示す範囲の共通部分を算出するプログラムに入力する。そして、式生成部１２１は、下記の式（３４）に示すように、式が示す範囲の共通部分を算出するプログラムによる出力結果を、競合ミス要因共通式Ｚ４，１とする。同様に、式生成部１２１は、競合ミス要因分割式ΨＪ４，１´＝０と、競合ミス要因分割式ΨＪ４，２´＝１と、競合ミス要因分割式ΨＪ４，３´＝０とを、式が示す範囲の共通部分を算出するプログラムに入力する。そして、式生成部１２１は、下記の式（３５）に示すように、式が示す範囲の共通部分を算出するプログラムによる出力結果を、競合ミス要因共通式Ｚ４，２とする。
【０１２６】
【数３４】
0006730587.tif 000035
【０１２７】
【数３５】
0006730587.tif 000036
【０１２８】
その後、式生成部１２１は、Ｓ３２の処理で生成した競合ミス要因共通式等から、Ｓ２の処理で特定した特定の配列のデータがキャッシュに格納されている場合に、特定の位置に対応する配列のデータに対して行われる回数を示す第４回数式を生成する（Ｓ３３）。
【０１２９】
具体的に、式生成部１２１は、Ｓ３２の処理で生成した競合ミス要因共通式Ｚ４，１と、競合ミス要因共通式Ｚ４，１にループ変数ｋとパラメータ変数Ｘとパラメータ変数Ｙとパラメータ変数Ｚとが含まれることを示す情報とを、ｖｏｌｕｍｅ処理として利用可能なパラメトリック離散体積計算手法を実行するプログラムに入力する。そして、式生成部１２１は、パラメトリック離散体積計算手法を実行するプログラムによる出力結果であるループ変数ｋの値の個数を表す条件と式の対のリストを、下記の式（３６）、式（３７）及び式（３８）に示すように、第４回数式ＶＺ４，１とする。同様に、式生成部１２１は、Ｓ３２の処理で生成した競合ミス要因共通式Ｚ４，２から、第４回数式ＶＺ４，２を生成する。
【０１３０】
なお、上記の例では、Ｓ２１からＳ３３の処理をヒットソース式Ｃ４について実行する場合について説明したが、式生成部１２１は、ヒットソース式Ｃ１、ヒットソース式Ｃ２、ヒットソース式Ｃ３及びヒットソース式Ｃ５についても同様に、Ｓ２１からＳ３３の処理を実行する。
【０１３１】
【数３６】
0006730587.tif 000037
【０１３２】
【数３７】
0006730587.tif 000038
【０１３３】
【数３８】
0006730587.tif 000039
【０１３４】
そして、式生成部１２１は、Ｓ１３の処理で生成した第１回数式からＳ１４の処理で生成した第２回数式を減算した式と、Ｓ２３の処理で生成した第３回数式からＳ３３の処理で生成した第４回数式とを減算した式を生成する（Ｓ３４）。
【０１３５】
具体的に、式生成部１２１は、下記の式（３９）に示すように、第１回数式ＶＧから、第２回数式ＶＣ１と、第２回数式ＶＣ２と、第２回数式ＶＣ３と、第２回数式ＶＣ４と、第２回数式ＶＣ５とを減算した式を生成する。
【０１３６】
【数３９】
0006730587.tif 000040
【０１３７】
すなわち、第１回数式ＶＧは、プログラム情報１３１のソースコードにおける特定の位置の実行回数を示す式である。そして、第２回数式ＶＣ１、第２回数式ＶＣ２、第２回数ＶＣ３、第２回数ＶＣ４及び第２回数ＶＣ５は、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュに格納されている回数を示す式である。そのため、上記の式（３９）は、特定の位置の実行が行われる場合において、アクセス対象のデータが一度もキャッシュに格納されていないために、キャッシュミスになった回数を示す式になる。
【０１３８】
また、式生成部１２１は、下記の式（４０）に示すように、ヒットソース式Ｃ４について、第３回数式ＶＪ４，１´´と、第３回数式ＶＪ４，２´´と、第３回数式ＶＪ４，３´´との総和から、第４回数式ＶＺ４，１と、第４回数式ＶＺ４，２とを減算した式を生成する。
【０１３９】
【数４０】
0006730587.tif 000041
【０１４０】
すなわち、第３回数式ＶＪ４，１´´、第３回数式ＶＪ４，２´´及び第３回数式ＶＪ４，３´´は、競合ミス要因式が示すアクセスによって、特定の位置におけるアクセス対象のデータが消去されたことに伴い、キャッシュミスになった回数の最大値を示す式である。そして、第４回数式ＶＺ４，１及び第４回数式ＶＺ４，２は、競合ミス要因式が示すアクセスによってキャッシュに格納されたデータの種類の数がキャッシュの連想数よりも小さいため、キャッシュミスにならなかった回数（キャッシュヒットになった回数）を示す式である。そのため、上記の式（４０）は、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されたために、キャッシュミスになった回数を示す式になる。
【０１４１】
続いて、式生成部１２１は、ヒットソース式Ｃ１、ヒットソース式Ｃ２、ヒットソース式Ｃ３及びヒットソース式Ｃ５のそれぞれについても、式（４０）と同様の式を生成する。そして、式生成部１２１は、下記の式（４１）に示すように、各ヒットソース式について生成した式をそれぞれ加算した式を生成する。
【０１４２】
【数４１】
0006730587.tif 000042
【０１４３】
なお、式生成部１２１は、図１５に示すように、上記の式（３９）及び上記の式（４１）を、キャッシュ推定式情報１３７として情報格納領域１３０に記憶するものであってもよい。以下、式（３９）を初期参照ミス推定式とも呼び、式（４１）を競合ミス推定式とも呼ぶ。
【０１４４】
[式利用処理］
次に、第１の実施の形態におけるキャッシュミス推定処理のうち、キャッシュミス推定式を利用してキャッシュミスの回数を推定する処理（以下、式利用処理とも呼ぶ）について説明を行う。図１６は、式利用処理を説明するフローチャートである。また、図１７及び図１８は、式利用処理を説明する図である。
【０１４５】
情報処理装置１の式評価部１２２は、パラメータ情報を受け付けるまで待機する（Ｓ１０１のＮＯ）。具体的に、式評価部１２２は、例えば、研究者が情報処理装置１にパラメータ情報を入力するまで待機する。パラメータ情報は、プログラム情報１３１のソースコードに含まれるパラメータ変数の具体的な値を含む情報である。具体的に、図１７に示すパラメータ情報は、パラメータ変数Ｘが１０であり、パラメータ変数Ｙが１０であり、パラメータ変数Ｚが６であることを示している。
【０１４６】
すなわち、初期参照ミス推定式及び競合ミス推定式に含まれている変数は、式（２６）等に示すように、パラメータ変数のみである。そのため、式評価部１２２は、初期参照ミス推定式及び競合ミス推定式に、パラメータ情報を代入することにより、図２で説明したプログラム情報１３１のソースコードを実行した場合における初期参照ミスの回数及び競合ミスの回数を推定することが可能になる。
【０１４７】
そして、パラメータ情報が入力された場合（Ｓ１０１のＹＥＳ）、式評価部１２２は、Ｓ３４の処理で生成した初期参照ミス推定式及び競合ミス推定式に、Ｓ１０１の処理で入力されたパラメータ情報を代入し、キャッシュミスの回数を推定する（Ｓ１０２）。
【０１４８】
これにより、情報処理装置１は、実機やシミュレータにおいてプログラムを実行することなく、キャッシュミスの回数の算出を行うことが可能になる。そのため、情報処理装置１は、キャッシュミスの回数の算出を効率的に行うことが可能になる。
【０１４９】
[式利用処理の具体例］
次に、式利用処理の具体例について説明を行う。以下、Ｓ１０１の処理において、パラメータ変数Ｘ、パラメータ変数Ｙ及びパラメータ変数Ｚの全てが１０であることを示すパラメータ情報が入力されたものとして説明を行う。
【０１５０】
式評価部１２２は、この場合、Ｚ≧１の条件（Ｃｏｎｄｉｔｉｏｎ）が満たされるものと判定する。そのため、式評価部１２２は、式（１２）より、変数範囲式ＶＧの値として１０を算出する。また、式評価部１２２は、この場合、Ｘ≧５、−Ｘ＋Ｚ≧０及び−Ｘ≧−１０１の条件がみたされているものと判定する。そのため、式評価部１２２は、式（１３）より、第１回数式ＶＣ１の値として６を算出する。なお、ｆ（ｘ）は、ｘの床関数を示すものである。同様に、式評価部１２２は、第１回数式ＶＣ２、第１回数式ＶＣ３、第１回数式ＶＣ４及び第１回数式ＶＣ５として、それぞれ０、１、１及び２を算出する。
【０１５１】
したがって、式評価部１２２は、この場合、図１８に示すように、初期参照ミスの回数として０を算出する。また、式評価部１２２は、同様に、競合ミスの回数として１を算出する。
【０１５２】
なお、図２に示すプログラム情報１３１のソースコードにおいて、最初のループ（ステップＳ１を含むループ）及び２番目のループ（ステップＳ２を含むループ）が終了し、３番目のループ（ステップＳ３を含むループ）のループ変数ｋが５である場合のキャッシュミスの回数の推定を行う場合、研究者は、パラメータ変数Ｘ及びパラメータ変数Ｙが１０であり、パラメータ変数Ｚが６であることを示すパラメータ情報を情報処理装置１に入力する。これにより、研究者は、情報処理装置１から出力された回数を、３番目のループのループ変数ｋが５である場合のキャッシュミスの回数として取得することが可能になる。
【０１５３】
一方、３番目のループ変数ｋの値が３から７に変化する間に発生したキャッシュミスの回数の推定を行う場合、研究者は、パラメータ変数Ｘ及びパラメータ変数Ｙが１０であり、パラメータ変数Ｚが３であることを示すパラメータ情報を情報処理装置１に入力する。また、研究者は、この場合、パラメータ変数Ｘ及びパラメータ変数Ｙが１０であり、パラメータ変数Ｚが８であることを示すパラメータ情報を情報処理装置１に入力する。そして、研究者は、パラメータ変数Ｚが８であることを示すパラメータ情報の入力に応じて情報処理装置１から出力された回数から、パラメータ変数Ｚが３であることを示すパラメータ情報の入力に応じて情報処理装置１から出力された回数を減算する。これにより、研究者は、情報処理装置１から出力された回数を、３番目のループ変数ｋの値が３から７に変化する間に発生したキャッシュミスの回数として取得する。
【０１５４】
このように、第１の実施の形態における情報処理装置１は、配列情報１３６と、特定位置情報１３３とに基づき、特定の位置に対応する特定の配列の特定し、特定の配列に対応するソースコード上の位置毎に、特定の配列に対応する情報を配列情報１３６から取得する。
【０１５５】
そして、情報処理装置１は、取得した特定の配列に対応する情報と、特定位置情報１３３と、ループ情報１３５と、データ情報１３２と、キャッシュ情報１３４とに基づき、ヒット条件式を、特定の配列に対応するソースコード上の位置毎に生成する。また、情報処理装置１は、生成した前記ヒット条件式に基づき、ヒットソース候補式を、特定の配列に対応するソースコード上の位置毎に生成する。さらに、情報処理装置１は、生成したヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、ヒットソース式を生成する。
【０１５６】
続いて、情報処理装置１は、特定の配列に対応するソースコード上の位置を囲むループに関連するループ変数と、そのループ変数に対応するパラメータ変数とから、変数範囲式を生成する。そして、情報処理装置１は、生成した変数範囲式と、変数範囲式に含まれるループ変数を特定する情報と、変数範囲式に含まれるパラメータ変数を特定する情報とから、第１回数式を生成する。さらに、情報処理装置１は、ヒットソース式と、ヒットソース式に含まれるループ変数を特定する情報と、ヒットソース式に含まれるパラメータ変数を特定する情報とから、第２回数式を生成する。
【０１５７】
その後、情報処理装置１は、ヒットソース式と、特定位置情報１３３と、ループ情報１３５と、データ情報１３２と、キャッシュ情報１３４とに基づき、競合ミス要因候補式を、ソースコード上の位置毎に生成する。そして、情報処理装置１は、生成した競合ミス要因候補式それぞれが示すアクセスの重複を排除し、競合ミス要因式を、ソースコード上の位置毎に生成する。さらに、情報処理装置１は、生成した競合ミス要因式と、競合ミス要因式に含まれるループ変数を特定する情報と、競合ミス要因式に含まれるパラメータ変数を特定する情報とから、第３回数式を、ソースコード上の位置毎に生成する。
【０１５８】
続いて、情報処理装置１は、キャッシュの連想数に基づき、競合ミス要因式毎に、各競合ミス要因式を競合ミス要因分割式にそれぞれ分割する。そして、情報処理装置１は、競合ミス要因式それぞれに対応する競合ミス要因分割式の種類の数の総和が、連想数を下回る競合ミス要因分割式の組み合わせを特定し、競合ミス要因共通式を、競合ミス要因式毎に生成する。さらに、情報処理装置１は、生成した競合ミス要因共通式と、競合ミス要因共通式に含まれるループ変数を特定する情報と、競合ミス要因共通式に含まれるパラメータ変数を特定する情報とから、第４回数式を生成する。
【０１５９】
その後、情報処理装置１は、第１回数式から第２回数式を減算して生成した第１の式と、第３回数式から第４回数式を減算して生成した第２の式とを生成する。
【０１６０】
これにより、情報処理装置１は、実機やシミュレータにおいてプログラムを実行することなく、キャッシュミスの回数の算出を行うことが可能になる。そのため、情報処理装置１は、キャッシュミスの回数の算出を効率的に行うことが可能になる。
【０１６１】
また、情報処理装置１は、実機やシミュレータにおいてプログラムを実行させることなく、キャッシュミスが発生するアクセスを行うソースコード上の位置を特定することが可能になる。さらに、情報処理装置１は、実機やシミュレータにおいてプログラムを実行させることなく、発生したキャッシュミスの要因を特定することが可能になる。
【０１６２】
以上の実施の形態をまとめると、以下の付記のとおりである。
【０１６３】
（付記１）
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、
取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるＣＰＵにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、
前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、
生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第１回数式を生成し、
前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第２回数式を生成し、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第３回数式を、前記ソースコード上の位置毎に生成し、
前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、
前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、
生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第４回数式を生成し、
前記第１回数式から前記第２回数式を減算した式と、前記第３回数式から前記第４回数式を減算した式とを生成する、
処理をコンピュータに実行させることを特徴とするキャッシュミス推定プログラム。
【０１６４】
（付記２）
付記１において、
前記ヒット条件式を生成する処理では、前記キャッシュの状態集合を示す式を生成するプログラムを、前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力としてコンピュータに実行させ、
前記キャッシュの状態集合を示す式を生成するプログラムの実行によって生成された式を、前記ヒット条件式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１６５】
（付記３）
付記１において、
前記ヒットソース候補式を生成する処理では、前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムを、前記ヒット条件式と、前記ヒット条件式に含まれる前記ループ変数を特定する情報と、前記ヒット条件式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムの実行によって生成された式を、前記ヒットソース候補式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１６６】
（付記４）
付記３において、
前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムは、パラメトリック整数線形計画法を用いたプログラムである、
ことを特徴とするキャッシュミス推定プログラム。
【０１６７】
（付記５）
付記１において、
前記ヒットソース式を生成する処理では、複数の式がそれぞれ示す範囲の重複を排除するプログラムを、前記ヒットソース候補式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、前記ヒットソース式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１６８】
（付記６）
付記１において、
前記第１回数式を生成する処理では、
前記変数範囲式を生成するプログラムを、前記特定の配列に対応する前記ループ変数と、前記特定の配列に対応する前記ループ変数に対応する前記パラメータ変数とを入力としてコンピュータに実行させ、
前記変数範囲式を生成するプログラムによって生成された式を、前記変数範囲式として生成し、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第１回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１６９】
（付記７）
付記１において、
前記第２回数式を生成する処理では、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第２回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１７０】
（付記８）
付記６または７において、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムは、パラメトリック離散体積計算手法を用いたプログラムである、
ことを特徴とするキャッシュミス推定プログラム。
【０１７１】
（付記９）
付記１において、
前記競合ミス要因候補式を生成する処理では、前記キャッシュの状態集合を示す式を生成するプログラムを、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力として実行させ、
前記キャッシュの状態集合を示す式を生成するプログラムの実行によって生成された式を、前記競合ミス要因候補式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１７２】
（付記１０）
付記１において、
前記競合ミス要因式を生成する処理では、
前記競合ミス要因候補式から、前記特定の配列におけるアクセス対象のデータを前記キャッシュから消去するアクセスを表す前記ループ変数を消去して、ループ変数を消去した前記競合ミス要因候補式を生成し、
ループ変数を消去した競合ミス要因候補式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因候補式を生成し、
重複を排除した前記競合ミス要因候補式から、アクセス対象のデータを識別する識別変数を消去して、前記競合ミス要因式を生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１７３】
（付記１１）
付記１において、
前記競合ミス要因式を生成する処理では、
式に含まれる変数を消去するプログラムを、前記競合ミス要因候補式と、前記特定の配列におけるアクセス対象のデータを前記キャッシュから消去するアクセスを表す前記ループ変数を特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって前記ループ変数が消去された式を、ループ変数を消去した前記競合ミス要因候補式として生成し、
複数の式がそれぞれ示す範囲の重複を排除するプログラムを、ループ変数を消去した前記競合ミス要因候補式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、重複を排除した前記競合ミス要因候補式として生成し、
前記式に含まれる変数を消去するプログラムを、重複を排除した前記競合ミス要因候補式と、アクセス対象のデータを識別する識別変数を特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって前記識別変数が消去された式を、前記競合ミス要因式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１７４】
（付記１２）
付記１において、
前記第３回数式を生成する処理では、
前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した後の前記競合ミス要因式を生成し、
重複を排除した後の前記競合ミス要因式から、重複を排除した後の前記競合ミス要因式に含まれる前記ループ変数が取り得る値の組み合わせの数を示す式を、前記第３回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１７５】
（付記１３）
付記１において、
前記第３回数式を生成する処理では、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムを、前記競合ミス要因式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、重複を排除した後の前記競合ミス要因式として生成し、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、重複を排除した後の前記競合ミス要因式と、重複を排除した後の前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した後の前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第３回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１７６】
（付記１４）
付記１において、
前記競合ミス要因分割式を生成する処理では、
前記データの種類の数毎に、前記競合ミス要因式を、アクセス対象のデータを識別する識別変数を含む第１の式と前記識別変数を含まない第２の式とに分類し、分類した前記第１の式を前記データの種類の数と同じ数に複製し、
前記データの種類の数毎に、複製した前記第１の式それぞれに含まれる前記識別変数を、複製した前記第１の式毎に異なる識別変数に変更し、
前記データの種類の数毎に、前記識別変数を変更した前記第１の式それぞれと、前記第２の式と、変更された前記識別変数それぞれの大小関係を示す式とから、変更された前記識別変数それぞれを消去した式を、第３の式として生成し、
前記データの種類の数毎に、各データの種類の数に対応する前記第３の式が示す範囲と、各データの種類の数よりも１大きい数に対応する前記第３の式が示す範囲との差を、各データの種類の数に対応する前記競合要因分割式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１７７】
（付記１５）
付記１４において、
前記第３の式を生成する処理では、
前記データの種類の数毎に、式に含まれる変数を消去するプログラムを、前記識別変数を変更した前記第１の式それぞれと、前記第２の式と、変更された前記識別変数それぞれの大小関係を示す式と、変更された前記識別変数それぞれを特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって生成された式を、第３の式として生成し、
前記競合要因分割式を生成する処理では、
前記データの種類の数毎に、複数の式がそれぞれ示す範囲の差を示す式を生成するプログラムに、各データの種類の数に対応する前記第３の式と、各データの種類の数よりも１大きい数に対応する前記第３の式とを入力としてコンピュータに実行させ、
前記データの種類の数毎に、前記複数の式がそれぞれ示す範囲の差を示す式を生成するプログラムの実行によって生成された式を、各データの種類の数に対応する前記競合要因分割式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１７８】
（付記１６）
付記１４において、
前記データの種類の数は、前記キャッシュの連想数よりも小さい数である、
ことを特徴とするキャッシュミス推定プログラム。
【０１７９】
（付記１７）
付記１において、
前記競合ミス要因共通式を生成する処理では、複数の式がそれぞれ示す範囲の共通部分を示す式を生成するプログラムを、前記組み合わせに含まれる前記競合ミス要因分割式それぞれを入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の共通部分を示す式を生成するプログラムによって生成された式を、前記競合ミス要因共通式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１８０】
（付記１８）
付記１において、
前記第４回数式を生成する処理では、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第４回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。
【０１８１】
（付記１９）
付記１において、さらに、
前記パラメータ変数に対応する値を受け付け、
受け付けた前記パラメータ変数に対応する値を、前記第１回数式から前記第２回数式を減算して生成した式に代入して算出された値と、受け付けた前記パラメータ変数に対応する値を、前記第３回数式から前記第４回数式を減算して生成した式に代入して算出された値との総和を算出する、
処理をコンピュータに実行させることを特徴とするキャッシュミス推定プログラム。
【０１８２】
（付記２０）
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるＣＰＵにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第１回数式を生成し、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第２回数式を生成する第１式生成部と、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第３回数式を、前記ソースコード上の位置毎に生成し、前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第４回数式を生成する第２式生成部と、
前記第１回数式から前記第２回数式を減算して生成した式と、前記第３回数式から前記第４回数式を減算して生成した式とを生成する第３式生成部と、を有する、
ことを特徴とする情報処理装置。
【０１８３】
（付記２１）
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、
取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるＣＰＵにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、
前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、
生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第１回数式を生成し、
前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第２回数式を生成し、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第３回数式を、前記ソースコード上の位置毎に生成し、
前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、
前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、
生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第４回数式を生成し、
前記第１回数式から前記第２回数式を減算して生成した式と、前記第３回数式から前記第４回数式を減算して生成した式とを生成する、
ことを特徴とするキャッシュミス推定方法。
【符号の説明】
【０１８４】
１：情報処理装置              １ａ：記憶装置
１１：研究者端末              ＮＷ：ネットワーク
【図１】
0006730587.tif 000043
【図２】
0006730587.tif 000044
【図３】
0006730587.tif 000045
【図４】
0006730587.tif 000046
【図５】
0006730587.tif 000047
【図６】
0006730587.tif 000048
【図７】
0006730587.tif 000049
【図８】
0006730587.tif 000050
【図９】
0006730587.tif 000051
【図１０】
0006730587.tif 000052
【図１１】
0006730587.tif 000053
【図１２】
0006730587.tif 000054
【図１３】
0006730587.tif 000055
【図１４】
0006730587.tif 000056
【図１５】
0006730587.tif 000057
【図１６】
0006730587.tif 000058
【図１７】
0006730587.tif 000059
【図１８】
0006730587.tif 000060