図面 (/)

技術 キャッシュミス推定プログラム、キャッシュミス推定方法及び情報処理装置

出願人 富士通株式会社
発明者 新井正樹
出願日 2016年6月13日 (5年6ヶ月経過) 出願番号 2016-117149
公開日 2017年12月21日 (4年0ヶ月経過) 公開番号 2017-224038
状態 特許登録済
技術分野 ストアードプログラム 階層構造のメモリシステム
主要キーワード 共通式 整数線形計画法 識別変数 ヒット条件 体積計算 パラメータ変数 外部ディスク装置 凸多面体
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年12月21日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (19)

課題

プログラムの実行中に発生したキャッシュミスに関する情報を効率的に取得することを可能とするキャッシュミス推定プログラム、キャッシュミス推定方法及び情報処理装置を提供する。

解決手段

特定の配列に対応するループ変数から、ループ変数がと取り得る値の範囲を示す変数範囲式を生成し、生成した変数範囲式から、特定の位置の実行回数を示す第1回数式を生成し、ヒットソース式から、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュに格納されている回数を示す第2回数式を生成し、競合ミス要因式から、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を生成し、競合ミス要因共通式から、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成する。

概要

背景

近年、大規模並列計算機システム(以下、HPC(High Performance Computing)システムとも呼ぶ)において動作するプログラム(以下、アプリケーションプログラムとも呼ぶ)を高速に動作させるための研究が行われている。

具体的に、HPCシステムにおいてアプリケーションプログラムを高速に動作させるための方法として、例えば、CPU(Central Processing Unit)のキャッシュを有効利用する方法についての研究が行われている。この場合、HPCシステムの研究者等(以下、単に研究者とも呼ぶ)は、例えば、HPCシステムにおいてアプリケーションプログラムを動作させ、動作中のアプリケーションプログラムによるキャッシュの利用状況を含むプロファイルデータの取得を行う。そして、研究者は、例えば、取得したプロファイルデータの解析を行うことにより、キャッシュを有効利用するための方法の模索を行う。

概要

プログラムの実行中に発生したキャッシュミスに関する情報を効率的に取得することを可能とするキャッシュミス推定プログラム、キャッシュミス推定方法及び情報処理装置を提供する。特定の配列に対応するループ変数から、ループ変数がと取り得る値の範囲を示す変数範囲式を生成し、生成した変数範囲式から、特定の位置の実行回数を示す第1回数式を生成し、ヒットソース式から、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュに格納されている回数を示す第2回数式を生成し、競合ミス要因式から、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を生成し、競合ミス要因共通式から、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成する。

目的

そこで、一つの側面では、プログラムの実行中に発生したキャッシュミスに関する情報を効率的に取得することを可能とするキャッシュミス推定プログラム、キャッシュミス推定方法及び情報処理装置を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

プログラムソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるCPUにおけるキャッシュ連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第1回数式を生成し、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第2回数式を生成し、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を、前記ソースコード上の位置毎に生成し、前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成し、前記第1回数式から前記第2回数式を減算した式と、前記第3回数式から前記第4回数式を減算した式とを生成する、処理をコンピュータに実行させることを特徴とするキャッシュミス推定プログラム

請求項2

請求項1において、前記ヒット条件式を生成する処理では、前記キャッシュの状態集合を示す式を生成するプログラムを、前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力としてコンピュータに実行させ、前記キャッシュの状態集合を示す式を生成するプログラムの実行によって生成された式を、前記ヒット条件式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項3

請求項1において、前記ヒットソース候補式を生成する処理では、前記ループ変数の辞書式順序最大値を示す式を生成するプログラムを、前記ヒット条件式と、前記ヒット条件式に含まれる前記ループ変数を特定する情報と、前記ヒット条件式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムの実行によって生成された式を、前記ヒットソース候補式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項4

請求項3において、前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムは、パラメトリック整数線形計画法を用いたプログラムである、ことを特徴とするキャッシュミス推定プログラム。

請求項5

請求項1において、前記ヒットソース式を生成する処理では、複数の式がそれぞれ示す範囲の重複を排除するプログラムを、前記ヒットソース候補式を入力としてコンピュータに実行させ、前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、前記ヒットソース式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項6

請求項1において、前記第1回数式を生成する処理では、前記変数範囲式を生成するプログラムを、前記特定の配列に対応する前記ループ変数と、前記特定の配列に対応する前記ループ変数に対応する前記パラメータ変数とを入力としてコンピュータに実行させ、前記変数範囲式を生成するプログラムによって生成された式を、前記変数範囲式として生成し、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第1回数式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項7

請求項1において、前記第2回数式を生成する処理では、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第2回数式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項8

請求項6または7において、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムは、パラメトリック離散体積計算手法を用いたプログラムである、ことを特徴とするキャッシュミス推定プログラム。

請求項9

請求項1において、前記競合ミス要因候補式を生成する処理では、前記キャッシュの状態集合を示す式を生成するプログラムを、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力として実行させ、前記キャッシュの状態集合を示す式を生成するプログラムの実行によって生成された式を、前記競合ミス要因候補式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項10

請求項1において、前記競合ミス要因式を生成する処理では、前記競合ミス要因候補式から、前記特定の配列におけるアクセス対象のデータを前記キャッシュから消去するアクセスを表す前記ループ変数を消去して、ループ変数を消去した前記競合ミス要因候補式を生成し、ループ変数を消去した競合ミス要因候補式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因候補式を生成し、重複を排除した前記競合ミス要因候補式から、アクセス対象のデータを識別する識別変数を消去して、前記競合ミス要因式を生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項11

請求項1において、前記競合ミス要因式を生成する処理では、式に含まれる変数を消去するプログラムを、前記競合ミス要因候補式と、前記特定の配列におけるアクセス対象のデータを前記キャッシュから消去するアクセスを表す前記ループ変数を特定する情報とを入力としてコンピュータに実行させ、前記式に含まれる変数を消去するプログラムの実行によって前記ループ変数が消去された式を、ループ変数を消去した前記競合ミス要因候補式として生成し、複数の式がそれぞれ示す範囲の重複を排除するプログラムを、ループ変数を消去した前記競合ミス要因候補式を入力としてコンピュータに実行させ、前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、重複を排除した前記競合ミス要因候補式として生成し、前記式に含まれる変数を消去するプログラムを、重複を排除した前記競合ミス要因候補式と、アクセス対象のデータを識別する識別変数を特定する情報とを入力としてコンピュータに実行させ、前記式に含まれる変数を消去するプログラムの実行によって前記識別変数が消去された式を、前記競合ミス要因式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項12

請求項1において、前記第3回数式を生成する処理では、前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した後の前記競合ミス要因式を生成し、重複を排除した後の前記競合ミス要因式から、重複を排除した後の前記競合ミス要因式に含まれる前記ループ変数が取り得る値の組み合わせの数を示す式を、前記第3回数式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項13

請求項1において、前記第3回数式を生成する処理では、前記複数の式がそれぞれ示す範囲の重複を排除するプログラムを、前記競合ミス要因式を入力としてコンピュータに実行させ、前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、重複を排除した後の前記競合ミス要因式として生成し、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、重複を排除した後の前記競合ミス要因式と、重複を排除した後の前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した後の前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第3回数式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項14

請求項1において、前記競合ミス要因分割式を生成する処理では、前記データの種類の数毎に、前記競合ミス要因式を、アクセス対象のデータを識別する識別変数を含む第1の式と前記識別変数を含まない第2の式とに分類し、分類した前記第1の式を前記データの種類の数と同じ数に複製し、前記データの種類の数毎に、複製した前記第1の式それぞれに含まれる前記識別変数を、複製した前記第1の式毎に異なる識別変数に変更し、前記データの種類の数毎に、前記識別変数を変更した前記第1の式それぞれと、前記第2の式と、変更された前記識別変数それぞれの大小関係を示す式とから、変更された前記識別変数それぞれを消去した式を、第3の式として生成し、前記データの種類の数毎に、各データの種類の数に対応する前記第3の式が示す範囲と、各データの種類の数よりも1大きい数に対応する前記第3の式が示す範囲との差を、各データの種類の数に対応する前記競合要因分割式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項15

請求項14において、前記第3の式を生成する処理では、前記データの種類の数毎に、式に含まれる変数を消去するプログラムを、前記識別変数を変更した前記第1の式それぞれと、前記第2の式と、変更された前記識別変数それぞれの大小関係を示す式と、変更された前記識別変数それぞれを特定する情報とを入力としてコンピュータに実行させ、前記式に含まれる変数を消去するプログラムの実行によって生成された式を、第3の式として生成し、前記競合要因分割式を生成する処理では、前記データの種類の数毎に、複数の式がそれぞれ示す範囲の差を示す式を生成するプログラムに、各データの種類の数に対応する前記第3の式と、各データの種類の数よりも1大きい数に対応する前記第3の式とを入力としてコンピュータに実行させ、前記データの種類の数毎に、前記複数の式がそれぞれ示す範囲の差を示す式を生成するプログラムの実行によって生成された式を、各データの種類の数に対応する前記競合要因分割式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項16

請求項1において、前記競合ミス要因共通式を生成する処理では、複数の式がそれぞれ示す範囲の共通部分を示す式を生成するプログラムを、前記組み合わせに含まれる前記競合ミス要因分割式それぞれを入力としてコンピュータに実行させ、前記複数の式がそれぞれ示す範囲の共通部分を示す式を生成するプログラムによって生成された式を、前記競合ミス要因共通式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項17

請求項1において、前記第4回数式を生成する処理では、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第4回数式として生成する、ことを特徴とするキャッシュミス推定プログラム。

請求項18

請求項1において、さらに、前記パラメータ変数に対応する値を受け付け、受け付けた前記パラメータ変数に対応する値を、前記第1回数式から前記第2回数式を減算して生成した式に代入して算出された値と、受け付けた前記パラメータ変数に対応する値を、前記第3回数式から前記第4回数式を減算して生成した式に代入して算出された値との総和を算出する、処理をコンピュータに実行させることを特徴とするキャッシュミス推定プログラム。

請求項19

プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるCPUにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第1回数式を生成し、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第2回数式を生成する第1式生成部と、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を、前記ソースコード上の位置毎に生成し、前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成する第2式生成部と、前記第1回数式から前記第2回数式を減算して生成した式と、前記第3回数式から前記第4回数式を減算して生成した式とを生成する第3式生成部と、を有する、ことを特徴とする情報処理装置

請求項20

プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるCPUにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第1回数式を生成し、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第2回数式を生成し、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を、前記ソースコード上の位置毎に生成し、前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成し、前記第1回数式から前記第2回数式を減算して生成した式と、前記第3回数式から前記第4回数式を減算して生成した式とを生成する、ことを特徴とするキャッシュミス推定方法

技術分野

0001

本発明は、キャッシュミス推定プログラム、キャッシュミス推定方法及び情報処理装置に関する。

背景技術

0002

近年、大規模並列計算機システム(以下、HPC(High Performance Computing)システムとも呼ぶ)において動作するプログラム(以下、アプリケーションプログラムとも呼ぶ)を高速に動作させるための研究が行われている。

0003

具体的に、HPCシステムにおいてアプリケーションプログラムを高速に動作させるための方法として、例えば、CPU(Central Processing Unit)のキャッシュを有効利用する方法についての研究が行われている。この場合、HPCシステムの研究者等(以下、単に研究者とも呼ぶ)は、例えば、HPCシステムにおいてアプリケーションプログラムを動作させ、動作中のアプリケーションプログラムによるキャッシュの利用状況を含むプロファイルデータの取得を行う。そして、研究者は、例えば、取得したプロファイルデータの解析を行うことにより、キャッシュを有効利用するための方法の模索を行う。

0004

特開平8−241208号公報

先行技術

0005

Siddhartha Chatterjee,Erin Parker,Philip J.Hanlon,and Alvin R.Lebeck. Exact analysis of the cache behavior of nested loops. InCindy Norris and Jr.James B.Fenwick,editors,Pro−ceeding Language Design and Implementation(PLD1−01),volume 36.5 ofACMIGPLAN Notices,Pages 286−297,N.Y.,June 20−22 2001.ACMPress.

発明が解決しようとする課題

0006

しかしながら、上記のようにプロファイルデータの作成を行う場合、研究者は、HPCシステム(以下、実機とも呼ぶ)を長時間利用する必要がある場合がある。そのため、研究者は、実機を利用することができる時間等の制約によっては、実機を利用することによるプロファイルデータの作成を十分に行うことができない場合がある。

0007

これに対し、HPCシステムのシミュレータを利用することにより、プロファイルデータの作成を行う方法が存在する。この場合、研究者は、アプリケーションプログラムをシミュレータにおいて実行させ、プロファイルデータの作成に要する情報の収集を行う。これにより、研究者は、HPCシステムを長時間利用することなく、プロファイルデータを取得することが可能になる。

0008

しかしながら、シミュレータの実行速度は、実機の実行速度よりも大幅に遅い場合がある。そのため、研究者は、シミュレータを利用してプロファイルデータの作成を行う場合、プロファイルデータの作成を効率的に行うことができない場合がある。

0009

そこで、一つの側面では、プログラムの実行中に発生したキャッシュミスに関する情報を効率的に取得することを可能とするキャッシュミス推定プログラム、キャッシュミス推定方法及び情報処理装置を提供することを目的とする。

課題を解決するための手段

0010

実施の形態の一つの態様によれば、プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるCPUにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第1回数式を生成し、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第2回数式を生成し、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を、前記ソースコード上の位置毎に生成し、前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成し、前記第1回数式から前記第2回数式を減算した式と、前記第3回数式から前記第4回数式を減算した式とを生成する、処理をコンピュータに実行させる。

発明の効果

0011

一つの側面によれば、プログラムの実行中に発生したキャッシュミスに関する情報を効率的に取得することを可能とする。

図面の簡単な説明

0012

図1は、情報処理システム10の構成を示す図である。
図2は、プログラム情報131について説明する図である。
図3は、データ情報132について説明する図である。
図4は、位置情報133について説明する図である。
図5は、キャッシュ情報134の具体例を説明する図である。
図6は、ループ情報135の具体例を説明する図である。
図7は、配列情報136の具体例を説明する図である。
図8は、情報処理装置1のハードウエア構成を説明する図である。
図9は、第1の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
図10は、第1の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
図11は、第1の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
図12は、第1の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
図13は、第1の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
図14は、第1の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。
図15は、第1の実施の形態におけるキャッシュミス推定処理を説明する図である。
図16は、式利用処理を説明するフローチャートである。
図17は、式利用処理を説明する図である。
図18は、式利用処理を説明する図である。

実施例

0013

[情報処理システムの構成]
図1は、情報処理システム10の構成を示す図である。図1に示す情報処理システム10は、情報処理装置1(以下、キャッシュミス推定装置1とも呼ぶ)と、記憶装置1aとを有する。情報処理装置1は、例えば、インターネットイントラネット等からなるネットワークNWを介して研究者端末11にアクセスすることが可能である。

0014

情報処理装置1は、例えば、アプリケーションプログラムを実行中のHPCシステムにおいて発生するキャッシュミスの回数等を推定する式(以下、キャッシュミス推定式とも呼ぶ)の生成を含む処理(以下、キャッシュミス推定処理とも呼ぶ)を実行する。情報処理装置1は、例えば、HPCシステムが動作する物理マシンとは異なる物理マシンである。

0015

記憶装置1aは、例えば、HDD(Hard Disk Drive)やSSD(Solid State Drive)等からなる外部ディスク装置である。具体的に、記憶装置1aは、例えば、情報処理装置1がキャッシュミス推定処理を実行する際に参照する各種情報を記憶する。また、記憶装置1aは、例えば、情報処理装置1が生成したキャッシュミス推定式を記憶する。なお、記憶装置1aは、情報処理装置1の内部に設けられたディスク装置であってもよい。

0016

研究者端末11は、例えば、事業者が必要な情報の入力を行う端末である。そして、研究者端末11は、事業者による情報の入力があった場合、例えば、入力された情報を情報処理装置1に送信する。

0017

[各種情報の具体例]
次に、情報処理装置1がキャッシュミス推定処理を実行する際に参照する各種情報について説明を行う。なお、以下、各情報(プログラム情報131、データ情報132、位置情報133、キャッシュ情報134、ループ情報135及び配列情報136)は、キャッシュミス推定処理が実行される前に予め記憶装置1aに記憶されているものとして説明を行う。

0018

[プログラム情報]
初めに、HPCシステムが実行するアプリケーションプログラムのソースコードであるプログラム情報131について説明を行う。図2は、プログラム情報131について説明する図である。

0019

具体的に、ステップS1では、ループ変数iが0からX−1までの間においてインクリメントする毎に、配列Aの要素に0を設定する処理が行われる。また、ステップS2では、ループ変数jが0からY−1までの間においてインクリメントする毎に、配列Bの要素に0を設定する処理が行われる。さらに、ステップS3では、ループ変数kが0からZ−1までの間においてインクリメントする毎に、配列Aの要素に設定されている値を配列Cの要素に設定する処理が行われる。なお、パラメータ変数X、Y及びZは、キャッシュ推定式によるキャッシュミスの回数の推定が行われる際に、キャッシュ推定式を利用する者(例えば、研究者)によって入力される変数である。

0020

[データ情報]
次に、図2で説明したソースコード(プログラム情報131)における各配列に割当てられるメモリ内のサイズ及びアドレスを含むデータ情報132について説明を行う。図3は、データ情報132について説明する図である。

0021

図3に示すデータ情報132において、配列Aの開始アドレスμAが0であり、配列Aの要素(以下、配列要素とも呼ぶ)あたりのバイト数βAが8であり、配列Aの要素総数αAが100である。また、図3に示すデータ情報132において、配列Bの開始アドレスμBが800であり、配列Bの要素あたりのバイト数βBが8であり、配列Bの要素総数αBが100である。さらに、図3に示すデータ情報132において、配列Cの開始アドレスμCが1600であり、配列Cの要素あたりのバイト数βcが8であり、配列Aの要素総数αcが100である。

0022

[位置情報]
次に、図2で説明したソースコードにおける特定の位置を示す位置情報133(以下、特定位置情報133とも呼ぶ)について説明を行う。位置情報133は、例えば、図2で説明したソースコードにおいて、研究者によってキャッシュミスに関する調査が行われる位置(キャッシュミスの発生回数の推定が行われる位置)を示す情報である。図4は、位置情報133について説明する図である。

0023

図4に示す位置情報133は、図2で説明したプログラム情報131において、「文」に対応して「S3」が設定され、「サイド」に対応して「right」が設定され、「位置」に対応して「1」が設定されている。すなわち、図4に示す位置情報133は、例えば、ステップS3に記述された式の右辺に含まれる項のうち、左端から1番目に記述された項を示す位置におけるキャッシュミスの調査が行われることを示している。

0024

[キャッシュ情報]
次に、プログラムが実行されるCPUにおけるキャッシュの連想数を含むキャッシュ情報134について説明を行う。図5は、キャッシュ情報134の具体例を説明する図である。

0025

図5に示すキャッシュ情報134は、キャッシュの連想数Aが2であり、キャッシュのブロックサイズBが32であり、キャッシュのセット数Sが4であることを示している。

0026

[ループ情報]
次に、図2で説明したソースコードにおけるループ変数と、各ループ変数に対応するパラメータ変数とを含むループ情報135について説明を行う。図6は、ループ情報135の具体例を説明する図である。

0027

図6に示すループ情報135は、ループ変数iが0からX−1までの間においてインクリメントし、ループ変数jが0からY−1までの間においてインクリメントし、ループ変数kが0からZ−1までの間においてインクリメントすることを示している。

0028

[配列情報]
次に、図2で説明したソースコード上の位置と、その位置を囲むループに関連するループ変数を示す情報と、その位置の配列の要素を特定する情報とを含む配列情報136について説明を行う。図7は、配列情報136の具体例を説明する図である。

0029

図7に示す配列情報136における「位置番号」が「P0」である情報には、「文」として「S1」が設定され、「サイド」として「left」が設定され、「位置」として「1」が設定され、「配列」として「A」が設定されている。さらに、図7に示す配列情報136における「位置番号」が「P0」である情報には、「配列の添え字式」として「i」が設定され、「関連するループ変数」として「i」が設定されている。すなわち、図7に示す配列情報136のうち、「位置番号」が「P0」である情報は、ステップS1に記述された式の左辺に含まれる項のうち、左端から1番目に記述された項が配列Aであることを示している。また、図7に示す配列情報136のうち、「位置番号」が「P0」である情報は、配列Aの添え字式及びループ変数がiであることを示している。図7に含まれる他の情報については説明を省略する。

0030

[情報処理装置のハードウエア構成]
次に、情報処理装置1のハードウエア構成について説明する。図8は、情報処理装置1のハードウエア構成を説明する図である。

0031

情報処理装置1は、プロセッサであるCPU101と、メモリ102と、外部インターフェース(I/Oユニット)103と、記憶媒体ストレージ)104とを有する。各部は、バス105を介して互いに接続される。

0032

記憶媒体104は、記憶媒体104内のプログラム格納領域(図示しない)に、キャッシュミス推定処理を行うためのプログラム110を記憶する。

0033

CPU101は、図8に示すように、プログラム110の実行時に、プログラム110を記憶媒体104からメモリ102にロードし、プログラム110と協働してキャッシュミス推定処理を行う。具体的に、CPU101は、プログラム110と協働することにより、キャッシュミス推定式を生成する式生成部121と、キャッシュミス推定式を利用してキャッシュミスの回数の推定を行う式評価部122として動作する。

0034

記憶媒体104は、例えば、キャッシュミス推定処理を行う際に用いられる情報(図2で説明したプログラム情報131等)を記憶する情報格納領域130(以下、記憶部130とも呼ぶ)を有する。また、外部インターフェース103は、研究者端末11等と通信を行う。なお、図1で説明した記憶部1aは、記憶媒体104に対応するものであってよい。

0035

[第1の実施の形態]
次に、第1の実施の形態について説明する。図9から図14は、第1の実施の形態におけるキャッシュミス推定処理を説明するフローチャートである。また、図15は、第1の実施の形態におけるキャッシュミス推定処理を説明する図である。なお、以下、S1からS14までの処理を行う式生成部121を第1式生成部121とも呼び、S21からS33までの処理を行う式生成部121を第2式生成部121とも呼び、S34の処理を行う式生成部121を第3式生成部121とも呼ぶ。

0036

式生成部121は、式生成タイミングになるまで待機する(S1のNO)。式生成タイミングは、例えば、研究者が研究者端末11を介して情報処理装置1にキャッシュミス推定処理を行う旨の入力を行ったタイミングでよい。

0037

そして、式生成タイミングになった場合(S1のYES)、式生成部121は、プログラム情報131のソースコード上の位置とその位置を囲むループに関連するループ変数を示す情報とその位置の配列の要素を特定する情報とを含む配列情報136と、プログラム情報131のソースコード上の特定の位置を示す位置情報133とに基づき、特定の位置に対応する特定の配列の特定する(S2)。

0038

具体的に、図4に示す位置情報133では、「文」として「S3」が設定され、「サイド」として「right」が設定され、「位置」として「1」が設定されている。そして、図7に示す配列情報136において、「文」に「S3」が設定され、「サイド」に「right」が設定され、「位置」に「1」が設定された情報は、「位置情報」に「P2」が設定された情報である。そのため、式生成部121は、特定の位置としてP2を特定する。また、「位置情報」に「P2」が設定された情報の「配列」には「A」が設定されている。そのため、式生成部121は、S2の処理において、特定の配列として配列Aを特定する。

0039

続いて、式生成部121は、S2の処理で特定した特定の配列に対応するソースコード上の位置毎に、特定の配列に対応する情報を配列情報136から取得する(S3)。

0040

具体的に、図7に示す配列情報136において、「配列」に「A」が設定された情報は、「位置番号」に「P0」及び「P2」が設定された情報である。そのため、式生成部121は、特定の配列である配列Aが記述された位置として、P0及びP2(以下、特定の位置であるP2と区別するためにP2´とも呼ぶ)を特定する。そして、式生成部121は、「位置情報」が「P0」及び「P2」である情報を配列情報136から取得する。

0041

すなわち、特定の位置であるP2におけるアクセスがキャッシュヒットとなるためには、そのアクセス対象のデータを、プログラムの実行において先行するアクセスがキャッシュに格納している必要がある。そのため、式生成部121は、S3の処理において、特定の位置であるP2におけるアクセス対象のデータをキャッシュに格納した可能性がある位置として、P0及びP2´を特定する。

0042

続いて、式生成部121は、S3の処理で取得した特定の配列に対応する情報等に基づいて、特定の配列においてアクセスが行われる場合に、そのアクセス対象のデータがキャッシュに格納されている条件を算出するヒット条件式を、特定の配列に対応するソースコード上の位置毎に生成する(S4)。なお、以下、ヒット条件式等の各式は、テキスト形式によって凸多面体表現する凸多面体フォーマットのデータとして生成されるものとして説明を行う。

0043

具体的に、式生成部121は、S3の処理で取得した情報のうちの「位置情報」が「P0」である情報と、図4で説明した位置情報133と、図6で説明したループ情報135と、図3で説明したデータ情報132と、図5で説明したキャッシュ情報134とを、キャッシュの状態集合(振る舞い)を定式化するプログラムに入力する。そして、キャッシュの振る舞いを定式化するプログラムによる出力結果を、下記の式(1)に示すように、P0とP2との関係におけるヒット条件式Γ1とする。なお、式(1)には、キャッシュセット識別する変数sと、キャッシュに格納されたデータを識別する変数wとが含まれている。

0044

0045

また、式生成部121は、S3の処理で取得した情報のうちの「位置情報」が「P2」である情報と、図4で説明した位置情報133と、図6で説明したループ情報135と、図3で説明したデータ情報132と、図5で説明したキャッシュ情報134とを、キャッシュの振る舞いを定式化するプログラムに入力する。そして、式生成部121は、キャッシュの振る舞いを定式化するプログラムによる出力結果を、下記の式(2)に示すように、P2´とP2との関係におけるヒット条件式Γ2とする。なお、式(2)において、P2´に対応するループ変数kをループ変数k´と表記する。

0046

0047

そして、式生成部121は、S4の処理で生成したヒット条件式に基づき、キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、特定の配列に対応するソースコード上の位置毎に生成する(S5)。

0048

すなわち、S4の処理で生成したヒット条件式を満たすアクセスが複数存在する場合において、特定の配列におけるアクセスのキャッシュヒットに寄与するアクセスは、特定の配列におけるアクセスに最も近いアクセスである。そのため、式生成部121は、ヒット条件式に含まれるループ変数のリスト辞書式順序の値が最大となる場合のヒット条件式を、ヒットソース候補式とする。

0049

具体的に、式生成部121は、ヒット条件式Γ1(凸多面体フォーマットのデータ)と、ヒット条件式Γ1に含まれるループ変数のリストに含まれるループ変数iと、ヒット条件式Γ1に含まれるパラメータ変数のリストに含まれるパラメータ変数X及びZとを、PIP処理として利用可能なパラメトリック整数線形計画法を実行するプログラムに入力する。PIP処理は、ヒット条件式に含まれるループ変数のリストにおける辞書式順序の最大値を表す凸多面体フォーマットのデータリストを出力する処理である。そして、式生成部121は、パラメトリック整数線形計画法を実行するプログラムによる出力結果を、下記の式(3)及び式(4)に示すように、ヒット条件式Γ1に対するヒットソース候補式Γ1,1´及びΓ1,2´としてそれぞれ生成する。

0050

0051

0052

同様に、式生成部121は、下記の式(5)に示すように、S4の処理で生成したヒット条件式Γ2に対するヒットソース候補式Γ2,1´を生成する。

0053

0054

続いて、式生成部121は、図10に示すように、S5の処理で生成したヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成する(S11)。

0055

すなわち、S5の処理において、式生成部121は、プログラムの実行において先行するアクセスの位置(例えば、P0及びP2´)を個々に考慮している。しかしながら、これらの位置に対応して生成されたヒットソース候補式が示すアクセスには、重複部分が存在する可能性がある。そのため、式生成部121は、S11の処理において、ヒットソース候補式の重複部分の除去を行う。

0056

具体的に、式生成部121は、S5の処理で生成した凸多面体フォーマットのデータリストであるヒットソース候補式Γ1,1´、Γ1,2´及びΓ2,1´を、disjoint処理を実行するプログラムに入力する。disjoint処理は、凸多面体フォーマットのデータリストから重複を除去する処理である。そして、式生成部121は、disjoint処理を実行するプログラムによる出力結果を、下記の式(6)から式(10)に示すように、それぞれヒットソース式C1、C2、C3、C4及びC5とする。

0057

0058

0059

0060

0061

0062

なお、式生成部121は、S11の処理において、ヒットソース候補式Γ1,1´、Γ1,2´及びΓ2,1´に含まれるループ変数i及びループ変数k´(P0及びP2´に対応するループ変数)を、ループ変数kに置き換えることによって消去してから、disjoint処理を実行する。これにより、ヒットソース候補式Γ1,1´、Γ1,2´及びΓ2,1´は、それぞれ同じ変数(k、w、s)と同じパラメータ変数(X、Y、Z)のみを含む凸多面体フォーマットのデータとして表現される。

0063

そして、式生成部121は、S2の処理で特定した特定の配列に対応するソースコード上の位置を囲むループに関連するループ変数と、そのループ変数に対応するパラメータ変数とから、そのループ変数が取り得る値の範囲を示す変数範囲式を生成する(S12)。

0064

具体的に、式生成部121は、例えば、コンパイラがソースコードのコンパイルを実行する場合において利用されるプログラム解析処理を実行するプログラムに、位置情報133とループ情報135とを入力する。そして、式生成部121は、プログラム解析処理を実行するプログラムによる出力結果を、下記の式(11)に示すように、ループ変数kが取り得る値の範囲を示す変数範囲式Gとする。

0065

0066

その後、式生成部121は、S12の処理で生成した変数範囲式と、その変数範囲式に含まれるループ変数を特定する情報と、その変数範囲式に含まれるパラメータ変数を特定する情報とから、S2の処理で特定した特定の位置の実行回数を示す第1回数式を生成する(S13)。

0067

具体的に、式生成部121は、S12の処理で算出した変数範囲式Gと、変数範囲式Gにループ変数kとパラメータ変数Zとが含まれることを示す情報とを、volume処理として利用可能なパラメトリック離散体積計算手法を実行するプログラムに入力する。volume処理は、ループ変数の取り得る値の組み合わせの個数を表す式を生成する処理である。そして、式生成部121は、パラメトリック離散体積計算手法を実行するプログラムによる出力結果であるループ変数kの値の個数を表す条件と式の対のリストを、下記の式(12)に示すように、第1回数式VGとする。

0068

0069

続いて、式生成部121は、S11の処理で生成したヒットソース式と、そのヒットソース式に含まれるループ変数を特定する情報と、そのヒットソース式に含まれるパラメータ変数を特定する情報とから、S2の処理で特定した特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュに格納されている回数を示す第2回数式を生成する(S14)。

0070

具体的に、式生成部121は、S13の処理と同様に、S11の処理で生成したヒットソース式C1と、ヒットソース式C1にループ変数kとパラメータ変数Xとパラメータ変数Zとが含まれることを示す情報とを、パラメトリック離散体積計算手法を実行するプログラムに入力する。そして、式生成部121は、下記の式(13)に示すように、パラメトリック離散体積計算手法を実行するプログラムによる出力結果であるループ変数kの値の個数を表す条件と式の対のリストを、第2回数式VC1とする。

0071

0072

同様に、式生成部121は、S11の処理で生成したヒットソース式C2、ヒットソース式C3、ヒットソース式C4及びヒットソース式C5から、それぞれ第2回数式VC2、第2回数式VC3、第2回数式VC4及び第2回数式VC5を生成する。

0073

すなわち、式生成部121は、S13の処理において、プログラム情報131のソースコード上の特定の位置における実行回数(特定の位置において行われるデータに対するアクセス回数)を示す式を生成する。また、式生成部121は、S14の処理において、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュに格納されている回数を示す式を生成する。そして、式生成部121は、後述するように、S13の処理で生成した式からS14の処理で生成した式を減算した式を生成する。これにより、式生成部121は、後述するように、特定の位置の実行が行われる場合において、アクセス対象のデータが一度もキャッシュに格納されていないためにキャッシュミスになった回数を推定することが可能になる(以下、このキャッシュミスを初期参照ミスとも呼ぶ)。

0074

続いて、式生成部121は、図11に示すように、S11の処理で生成したヒットソース式等に基づき、S2の処理で特定した特定の配列におけるアクセス対象のデータをキャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、ソースコード上の位置毎に生成する(S21)。

0075

すなわち、特定の位置の実行が行われる場合において発生するキャッシュミスには、アクセス対象のデータが以前はキャッシュに格納されていたが、その後のアクセスによってキャッシュから消去されているために発生するキャッシュミスが含まれる。そのため、式生成部121は、S21以降の処理において、アクセス対象のデータが消去されたことに伴ってキャッシュミスになった回数を推定するための式の生成を行う(以下、このキャッシュミスを競合ミスとも呼ぶ)。

0076

具体的に、式生成部121は、例えば、S11の処理で生成したヒットソース式C4と、図4で説明した位置情報133と、図6で説明したループ情報135と、図3で説明したデータ情報132と、図5で説明したキャッシュ情報134とを、キャッシュの振る舞いを定式化するプログラムに入力する。そして、式生成部121は、下記の式(14)から式(16)に示すように、キャッシュの振る舞いを定式化するプログラムの出力結果である、競合ミス要因候補式H4,1、H4,2及びH4,3をそれぞれ生成する。なお、式(14)から式(16)には、S2の処理で特定した特定の配列におけるアクセス対象のデータをキャッシュから消去するアクセスの候補を表すループ変数x(ループ変数i、j及びkの総称である変数)と、各データを識別するラップアラウンド変数(以下、識別変数とも呼ぶ)であるラップアラウンド変数Qとが含まれている。

0077

0078

0079

0080

そして、式生成部121は、ヒットソース式C1、ヒットソース式C2、ヒットソース式C3及びヒットソース式C5についてもS13の処理を行う。

0081

その後、式生成部121は、S21の処理で生成した競合ミス要因候補式それぞれが示すアクセスの重複を排除して、特定の位置におけるアクセス対象のデータをキャッシュから消去するアクセスを示す競合ミス要因式を、ソースコード上の位置毎に生成する(S22)。以下、S22の処理の詳細について説明を行う。

0082

[S22の処理の詳細]
図13は、S22の処理の詳細を説明する図である。式生成部121は、S21で生成した競合ミス要因候補式に含まれるループ変数のうち、特定の配列におけるアクセス対象のデータをキャッシュから消去するアクセスを表すループ変数を消去する(S41)。すなわち、式生成部121は、キャッシュミスの回数を推定するために不要であるループ変数の消去(他のループ変数への置き換え)を行う。

0083

その後、式生成部121は、S41の処理でループ変数を消去した競合ミス要因候補式それぞれが示すアクセスの重複を排除した競合ミス要因候補式を生成する(S42)。すなわち、S21の処理で生成された競合ミス要因候補式は、ソースコードにおいてアクセスを行う可能性のある位置それぞれにおけるアクセスから生成される。そして、これらのアクセスは、同じキャッシュセットの同じデータに対するアクセスが含まれている場合がある。そのため、式生成部121は、S42の処理において、S41の処理でループ変数を消去した競合ミス要因候補式それぞれの重複の排除を行う。

0084

具体的に、式生成部121は、競合ミス要因候補式H4,1と、特定の位置であるP2におけるアクセス対象のデータをキャッシュから消去するアクセスを表すループ変数であるループ変数xを特定する情報とを、projectout処理を実行するプログラムに入力する。projectout処理は、凸多面体フォーマットのデータリストからループ変数を消去する処理である。そして、式生成部121は、projectout処理を実行するプログラムの出力結果を、ループ変数xを消去した競合ミス要因候補式H4,1´とする。同様に、式生成部121は、競合ミス要因候補式H4,2及びH4,3から、ループ変数xを消去した競合ミス要因候補式H4,2´及びH4,3´をそれぞれ生成する。

0085

その後、式生成部121は、S42の処理において、ループ変数xを消去した競合ミス要因候補式H4,1´、H4,2´及びH4,3´を、disjoint処理を実行するプログラムに入力する。そして、式生成部121は、disjoint処理を実行するプログラムによる出力結果を、下記の式(17)、式(18)及び式(19)に示すように、重複を排除した競合ミス要因候補式J4,1、J4,2及びJ4,3とする。

0086

0087

0088

0089

図13戻り、式生成部121は、S42の処理で重複を排除した競合ミス要因候補式に含まれるループ変数のうち、アクセス対象のデータを識別する識別変数を消去する(S43)。そして、式生成部121は、S43の処理で識別変数を消去した競合ミス要因候補式それぞれが示すアクセスの重複を排除した競合ミス要因式を生成する(S44)。

0090

すなわち、式生成部121は、S42の処理において、S21の処理で生成された競合ミス要因候補式から、ループ変数kとラップアラウンド変数Qとの組み合わせについての重複を排除しているが、ループ変数kのみを考慮した場合の重複についても排除を行う必要がある。そのため、式生成部121は、S43の処理において、ラップアラウンド変数Qの消去を行い、S44の処理において、ループ変数kのみを考慮した場合の重複の排除を行う。

0091

具体的に、式生成部121は、重複を排除した競合ミス要因候補式J4,1と、アクセス対象のデータを識別する識別変数であるラップアラウンド変数Qとを、projectout処理を実行するプログラムに入力する。そして、式生成部121は、下記の式(20)に示すように、projectout処理を実行するプログラムの出力結果を、競合ミス要因式J4,1´とする。同様に、式生成部121は、下記の式(21)及び式(22)に示すように、競合ミス要因候補式J4,2及びJ4,3から、ラップアラウンド変数Qを消去した競合ミス要因式J4,2´及びJ4,3´をそれぞれ生成する。なお、式(21)には、projectout処理によって自動的に導入される変数(作業用の変数)である変数e0が含まれている。

0092

0093

0094

0095

その後、式生成部121は、S44の処理において、競合ミス要因式J4,1´、J4,2´及びJ4,3´を、disjoint処理を実行するプログラムに入力する。そして、式生成部121は、disjoint処理を実行するプログラムによる出力結果を、下記の式(23)、式(24)及び式(25)に示すように、重複を排除した後の競合ミス要因式J4,1´´、J4,2´´及びJ4,3´´とする。

0096

0097

0098

0099

図11に戻り、式生成部121は、S22の処理で生成した競合ミス要因式等から、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を、ソースコード上の位置毎に生成する(S23)。

0100

具体的に、式生成部121は、重複を排除した後の競合ミス要因式J4,1´´と、重複を排除した後の競合ミス要因式J4,1´´にループ変数kとパラメータ変数Xとパラメータ変数Zとが含まれることを示す情報とを、volume処理として利用可能なパラメトリック離散体積計算手法を実行するプログラムに入力する。そして、式生成部121は、パラメトリック離散体積計算手法を実行するプログラムによる出力結果であるループ変数kの値の個数を表す条件と式の対のリストを、下記の式(26)及び式(27)に示すように、第3回数式VJ4,1´´とする。

0101

0102

0103

同様に、式生成部121は、重複を排除した後の競合ミス要因式J4,2´´及び重複を排除した後の競合ミス要因式J4,3´´から、それぞれ第3回数式VJ4,2´´及び第3回数式VJ4,3´´を生成する。

0104

その後、式生成部121は、キャッシュの連想数に基づき、競合ミス要因式毎に、各競合ミス要因式をアクセス対象のデータの種類の数毎のアクセスを示す競合ミス要因分割式にそれぞれ分割する(S24)。

0105

すなわち、競合ミス要因式が示すアクセスによってキャッシュにデータが格納された場合であっても、競合ミス要因式が示すアクセスによってキャッシュに格納されたデータの種類の数がキャッシュの連想数よりも小さい場合、特定の位置におけるアクセスによるキャッシュミスは発生しない。この点、S23の処理で生成した第3回数式には、競合ミス要因式が示すアクセスによってキャッシュに格納されたデータの数がキャッシュの連想数よりも小さい場合について考慮されていない。そのため、式生成部121は、S24以降の処理において、競合ミス要因式が示すアクセスによってキャッシュに格納されたデータの数がキャッシュの連想数よりも小さいことにより、キャッシュミスにならなかった回数の推定するための式の生成を行う。これにより、式生成部121は、後述するように、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数をより精度良く推定することが可能になる。

0106

具体的に、式生成部121は、S24の処理において、競合ミス要因式をキャッシュの連想数以下の数毎に分割する。さらに具体的に、式生成部121は、図6のキャッシュ情報134に示すように、キャッシュの連想数Aが2である場合、競合ミス要因式J4,1´を、1個の種類のデータをキャッシュに格納する場合に対応する競合ミス要因分割式ΨJ4,1´=1と、0個の種類のデータをキャッシュに格納する場合に対応する競合ミス要因分割式ΨJ4,1´=0とを含む複数の式に分割する。同様に、式生成部121は、競合ミス要因式J4,2´及び競合ミス要因式J4,3´についても分割を行う。以下、S24の処理の詳細について説明を行う。

0107

[S24の処理の詳細]
図14は、S24の処理の詳細を説明する図である。式生成部121は、競合ミス要因式に対応するアクセス対象のデータの種類の数毎に、競合ミス要因候補式を、アクセス対象のデータを識別する識別変数を含む第1の式と識別変数を含まない第2の式とに分類する(S51)。すなわち、式生成部121は、キャッシュの連想数以下の数毎に、競合ミス要因候補式の分割を行う。

0108

具体的に、式生成部121は、競合ミス要因式J4,1´を、下記の式(28)及び式(29)に示すように、ラップアラウンド変数Qを含む第1の式とラップアラウンド変数Qを含まない第2の式とに分類する。

0109

0110

0111

その後、式生成部121は、S51の処理において分類した第1の式を、競合ミス要因式に対応するアクセス対象のデータの種類の数と同じ数に複製する(S52)。そして、式生成部121は、データの種類の数毎に、S52の処理で複製した第1の式それぞれに含まれる識別変数を、第1の式毎に異なる識別変数に変更する(S53)。

0112

具体的に、式生成部121は、図6のキャッシュ情報134に示すように、キャッシュの連想数Aが2である場合、S51の処理において分類した第1の式を2つの式に複製する。そして、式生成部121は、下記の式(30)及び式(31)に示すように、複製した式に含まれるラップアラウンド変数Qを、それぞれラップアラウンド変数Q1及びラップアラウンド変数Q2に変更する。

0113

0114

0115

続いて、式生成部121は、競合ミス要因式に対応するアクセス対象のデータの種類の数毎に、S53の処理で識別変数を変更した第1の式それぞれと、S51の処理で分類された第2の式と、変更された識別変数それぞれの大小関係を示す式とから、S53の処理で変更された識別変数を消去した第3の式を生成する(S54)。

0116

具体的に、式生成部121は、ラップアラウンド変数Q1を含む第1の式と、ラップアラウンド変数Q2を含む第2の式と、ラップアラウンド変数Q1とラップアラウンド変数Q2との大小関係を示す式と、ラップアラウンド変数Q1とラップアラウンド変数Q2とを特定する情報とを、変数を消去するプログラムに入力する。そして、式生成部121は、変数を消去するプログラムによる出力結果を、競合ミス要因式から分割された式であって、競合ミス要因式に対応するアクセス対象のデータの種類の数が2以上である場合の式である第3の式ΨJ4,1´≧2として取得する。

0117

そして、式生成部121は、データの種類の数毎に、各データの種類の数に対応する第3の式と、各データの種類の数よりも1大きい数に対応する第3の式の差分を、各データの種類の数に対応する競合要因分割式として生成する(S55)。

0118

具体的に、式生成部121は、S54の処理で取得された第3の式ΨJ4,1´≧2と、第3の式ΨJ4,1´≧1とを、式が示す範囲の差分を算出するプログラムに入力する。そして、式生成部121は、下記の式(32)に示すように、式が示す範囲の差分を算出するプログラムによる出力結果を、競合ミス要因分割式ΨJ4,1´=1として取得する。

0119

また、式生成部121は、第3の式ΨJ4,1´≧1と、第3の式ΨJ4,1´≧0(ヒットソース式C4)とを、式の差分を算出するプログラムに入力する。そして、式生成部121は、下記の式(33)に示すように、式の差分を算出するプログラムによる出力結果を、競合ミス要因分割式ΨJ4,1´=0として取得する。

0120

0121

0122

図12に戻り、式生成部121は、S22の処理で生成した競合ミス要因式それぞれに対応する競合ミス要因分割式のデータの種類の数の総和が、キャッシュの連想数を下回る競合ミス要因分割式の組み合わせを特定する(S31)。

0123

具体的に、競合ミス要因分割式ΨJ4,1´=0と、競合ミス要因分割式ΨJ4,1´=1と、競合ミス要因分割式ΨJ4,2´=0と、競合ミス要因分割式ΨJ4,2´=1と、競合ミス要因分割式ΨJ4,3´=0とが存在する場合、式生成部121は、競合ミス要因分割式ΨJ4,1´=1と、競合ミス要因分割式ΨJ4,2´=0と、競合ミス要因分割式ΨJ4,3´=0との組み合わせを特定する。また、式生成部121は、この場合、競合ミス要因分割式ΨJ4,1´=0と、競合ミス要因分割式ΨJ4,2´=1と、競合ミス要因分割式ΨJ4,3´=0との組み合わせを特定する。

0124

そして、式生成部121は、S31の処理で特定した組み合わせに含まれる競合ミス要因分割式それぞれにおいて共通する式である競合ミス要因共通式を、競合ミス要因式毎に生成する(S32)。

0125

具体的に、式生成部121は、競合ミス要因分割式ΨJ4,1´=1と、競合ミス要因分割式ΨJ4,2´=0と、競合ミス要因分割式ΨJ4,3´=0とを、式が示す範囲の共通部分を算出するプログラムに入力する。そして、式生成部121は、下記の式(34)に示すように、式が示す範囲の共通部分を算出するプログラムによる出力結果を、競合ミス要因共通式Z4,1とする。同様に、式生成部121は、競合ミス要因分割式ΨJ4,1´=0と、競合ミス要因分割式ΨJ4,2´=1と、競合ミス要因分割式ΨJ4,3´=0とを、式が示す範囲の共通部分を算出するプログラムに入力する。そして、式生成部121は、下記の式(35)に示すように、式が示す範囲の共通部分を算出するプログラムによる出力結果を、競合ミス要因共通式Z4,2とする。

0126

0127

0128

その後、式生成部121は、S32の処理で生成した競合ミス要因共通式等から、S2の処理で特定した特定の配列のデータがキャッシュに格納されている場合に、特定の位置に対応する配列のデータに対して行われる回数を示す第4回数式を生成する(S33)。

0129

具体的に、式生成部121は、S32の処理で生成した競合ミス要因共通式Z4,1と、競合ミス要因共通式Z4,1にループ変数kとパラメータ変数Xとパラメータ変数Yとパラメータ変数Zとが含まれることを示す情報とを、volume処理として利用可能なパラメトリック離散体積計算手法を実行するプログラムに入力する。そして、式生成部121は、パラメトリック離散体積計算手法を実行するプログラムによる出力結果であるループ変数kの値の個数を表す条件と式の対のリストを、下記の式(36)、式(37)及び式(38)に示すように、第4回数式VZ4,1とする。同様に、式生成部121は、S32の処理で生成した競合ミス要因共通式Z4,2から、第4回数式VZ4,2を生成する。

0130

なお、上記の例では、S21からS33の処理をヒットソース式C4について実行する場合について説明したが、式生成部121は、ヒットソース式C1、ヒットソース式C2、ヒットソース式C3及びヒットソース式C5についても同様に、S21からS33の処理を実行する。

0131

0132

0133

0134

そして、式生成部121は、S13の処理で生成した第1回数式からS14の処理で生成した第2回数式を減算した式と、S23の処理で生成した第3回数式からS33の処理で生成した第4回数式とを減算した式を生成する(S34)。

0135

具体的に、式生成部121は、下記の式(39)に示すように、第1回数式VGから、第2回数式VC1と、第2回数式VC2と、第2回数式VC3と、第2回数式VC4と、第2回数式VC5とを減算した式を生成する。

0136

0137

すなわち、第1回数式VGは、プログラム情報131のソースコードにおける特定の位置の実行回数を示す式である。そして、第2回数式VC1、第2回数式VC2、第2回数VC3、第2回数VC4及び第2回数VC5は、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュに格納されている回数を示す式である。そのため、上記の式(39)は、特定の位置の実行が行われる場合において、アクセス対象のデータが一度もキャッシュに格納されていないために、キャッシュミスになった回数を示す式になる。

0138

また、式生成部121は、下記の式(40)に示すように、ヒットソース式C4について、第3回数式VJ4,1´´と、第3回数式VJ4,2´´と、第3回数式VJ4,3´´との総和から、第4回数式VZ4,1と、第4回数式VZ4,2とを減算した式を生成する。

0139

0140

すなわち、第3回数式VJ4,1´´、第3回数式VJ4,2´´及び第3回数式VJ4,3´´は、競合ミス要因式が示すアクセスによって、特定の位置におけるアクセス対象のデータが消去されたことに伴い、キャッシュミスになった回数の最大値を示す式である。そして、第4回数式VZ4,1及び第4回数式VZ4,2は、競合ミス要因式が示すアクセスによってキャッシュに格納されたデータの種類の数がキャッシュの連想数よりも小さいため、キャッシュミスにならなかった回数(キャッシュヒットになった回数)を示す式である。そのため、上記の式(40)は、特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されたために、キャッシュミスになった回数を示す式になる。

0141

続いて、式生成部121は、ヒットソース式C1、ヒットソース式C2、ヒットソース式C3及びヒットソース式C5のそれぞれについても、式(40)と同様の式を生成する。そして、式生成部121は、下記の式(41)に示すように、各ヒットソース式について生成した式をそれぞれ加算した式を生成する。

0142

0143

なお、式生成部121は、図15に示すように、上記の式(39)及び上記の式(41)を、キャッシュ推定式情報137として情報格納領域130に記憶するものであってもよい。以下、式(39)を初期参照ミス推定式とも呼び、式(41)を競合ミス推定式とも呼ぶ。

0144

[式利用処理]
次に、第1の実施の形態におけるキャッシュミス推定処理のうち、キャッシュミス推定式を利用してキャッシュミスの回数を推定する処理(以下、式利用処理とも呼ぶ)について説明を行う。図16は、式利用処理を説明するフローチャートである。また、図17及び図18は、式利用処理を説明する図である。

0145

情報処理装置1の式評価部122は、パラメータ情報受け付けるまで待機する(S101のNO)。具体的に、式評価部122は、例えば、研究者が情報処理装置1にパラメータ情報を入力するまで待機する。パラメータ情報は、プログラム情報131のソースコードに含まれるパラメータ変数の具体的な値を含む情報である。具体的に、図17に示すパラメータ情報は、パラメータ変数Xが10であり、パラメータ変数Yが10であり、パラメータ変数Zが6であることを示している。

0146

すなわち、初期参照ミス推定式及び競合ミス推定式に含まれている変数は、式(26)等に示すように、パラメータ変数のみである。そのため、式評価部122は、初期参照ミス推定式及び競合ミス推定式に、パラメータ情報を代入することにより、図2で説明したプログラム情報131のソースコードを実行した場合における初期参照ミスの回数及び競合ミスの回数を推定することが可能になる。

0147

そして、パラメータ情報が入力された場合(S101のYES)、式評価部122は、S34の処理で生成した初期参照ミス推定式及び競合ミス推定式に、S101の処理で入力されたパラメータ情報を代入し、キャッシュミスの回数を推定する(S102)。

0148

これにより、情報処理装置1は、実機やシミュレータにおいてプログラムを実行することなく、キャッシュミスの回数の算出を行うことが可能になる。そのため、情報処理装置1は、キャッシュミスの回数の算出を効率的に行うことが可能になる。

0149

[式利用処理の具体例]
次に、式利用処理の具体例について説明を行う。以下、S101の処理において、パラメータ変数X、パラメータ変数Y及びパラメータ変数Zの全てが10であることを示すパラメータ情報が入力されたものとして説明を行う。

0150

式評価部122は、この場合、Z≧1の条件(Condition)が満たされるものと判定する。そのため、式評価部122は、式(12)より、変数範囲式VGの値として10を算出する。また、式評価部122は、この場合、X≧5、−X+Z≧0及び−X≧−101の条件がみたされているものと判定する。そのため、式評価部122は、式(13)より、第1回数式VC1の値として6を算出する。なお、f(x)は、xの床関数を示すものである。同様に、式評価部122は、第1回数式VC2、第1回数式VC3、第1回数式VC4及び第1回数式VC5として、それぞれ0、1、1及び2を算出する。

0151

したがって、式評価部122は、この場合、図18に示すように、初期参照ミスの回数として0を算出する。また、式評価部122は、同様に、競合ミスの回数として1を算出する。

0152

なお、図2に示すプログラム情報131のソースコードにおいて、最初のループ(ステップS1を含むループ)及び2番目のループ(ステップS2を含むループ)が終了し、3番目のループ(ステップS3を含むループ)のループ変数kが5である場合のキャッシュミスの回数の推定を行う場合、研究者は、パラメータ変数X及びパラメータ変数Yが10であり、パラメータ変数Zが6であることを示すパラメータ情報を情報処理装置1に入力する。これにより、研究者は、情報処理装置1から出力された回数を、3番目のループのループ変数kが5である場合のキャッシュミスの回数として取得することが可能になる。

0153

一方、3番目のループ変数kの値が3から7に変化する間に発生したキャッシュミスの回数の推定を行う場合、研究者は、パラメータ変数X及びパラメータ変数Yが10であり、パラメータ変数Zが3であることを示すパラメータ情報を情報処理装置1に入力する。また、研究者は、この場合、パラメータ変数X及びパラメータ変数Yが10であり、パラメータ変数Zが8であることを示すパラメータ情報を情報処理装置1に入力する。そして、研究者は、パラメータ変数Zが8であることを示すパラメータ情報の入力に応じて情報処理装置1から出力された回数から、パラメータ変数Zが3であることを示すパラメータ情報の入力に応じて情報処理装置1から出力された回数を減算する。これにより、研究者は、情報処理装置1から出力された回数を、3番目のループ変数kの値が3から7に変化する間に発生したキャッシュミスの回数として取得する。

0154

このように、第1の実施の形態における情報処理装置1は、配列情報136と、特定位置情報133とに基づき、特定の位置に対応する特定の配列の特定し、特定の配列に対応するソースコード上の位置毎に、特定の配列に対応する情報を配列情報136から取得する。

0155

そして、情報処理装置1は、取得した特定の配列に対応する情報と、特定位置情報133と、ループ情報135と、データ情報132と、キャッシュ情報134とに基づき、ヒット条件式を、特定の配列に対応するソースコード上の位置毎に生成する。また、情報処理装置1は、生成した前記ヒット条件式に基づき、ヒットソース候補式を、特定の配列に対応するソースコード上の位置毎に生成する。さらに、情報処理装置1は、生成したヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、ヒットソース式を生成する。

0156

続いて、情報処理装置1は、特定の配列に対応するソースコード上の位置を囲むループに関連するループ変数と、そのループ変数に対応するパラメータ変数とから、変数範囲式を生成する。そして、情報処理装置1は、生成した変数範囲式と、変数範囲式に含まれるループ変数を特定する情報と、変数範囲式に含まれるパラメータ変数を特定する情報とから、第1回数式を生成する。さらに、情報処理装置1は、ヒットソース式と、ヒットソース式に含まれるループ変数を特定する情報と、ヒットソース式に含まれるパラメータ変数を特定する情報とから、第2回数式を生成する。

0157

その後、情報処理装置1は、ヒットソース式と、特定位置情報133と、ループ情報135と、データ情報132と、キャッシュ情報134とに基づき、競合ミス要因候補式を、ソースコード上の位置毎に生成する。そして、情報処理装置1は、生成した競合ミス要因候補式それぞれが示すアクセスの重複を排除し、競合ミス要因式を、ソースコード上の位置毎に生成する。さらに、情報処理装置1は、生成した競合ミス要因式と、競合ミス要因式に含まれるループ変数を特定する情報と、競合ミス要因式に含まれるパラメータ変数を特定する情報とから、第3回数式を、ソースコード上の位置毎に生成する。

0158

続いて、情報処理装置1は、キャッシュの連想数に基づき、競合ミス要因式毎に、各競合ミス要因式を競合ミス要因分割式にそれぞれ分割する。そして、情報処理装置1は、競合ミス要因式それぞれに対応する競合ミス要因分割式の種類の数の総和が、連想数を下回る競合ミス要因分割式の組み合わせを特定し、競合ミス要因共通式を、競合ミス要因式毎に生成する。さらに、情報処理装置1は、生成した競合ミス要因共通式と、競合ミス要因共通式に含まれるループ変数を特定する情報と、競合ミス要因共通式に含まれるパラメータ変数を特定する情報とから、第4回数式を生成する。

0159

その後、情報処理装置1は、第1回数式から第2回数式を減算して生成した第1の式と、第3回数式から第4回数式を減算して生成した第2の式とを生成する。

0160

これにより、情報処理装置1は、実機やシミュレータにおいてプログラムを実行することなく、キャッシュミスの回数の算出を行うことが可能になる。そのため、情報処理装置1は、キャッシュミスの回数の算出を効率的に行うことが可能になる。

0161

また、情報処理装置1は、実機やシミュレータにおいてプログラムを実行させることなく、キャッシュミスが発生するアクセスを行うソースコード上の位置を特定することが可能になる。さらに、情報処理装置1は、実機やシミュレータにおいてプログラムを実行させることなく、発生したキャッシュミスの要因を特定することが可能になる。

0162

以上の実施の形態をまとめると、以下の付記のとおりである。

0163

(付記1)
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、
取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるCPUにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、
前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、
生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第1回数式を生成し、
前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第2回数式を生成し、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を、前記ソースコード上の位置毎に生成し、
前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、
前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、
生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成し、
前記第1回数式から前記第2回数式を減算した式と、前記第3回数式から前記第4回数式を減算した式とを生成する、
処理をコンピュータに実行させることを特徴とするキャッシュミス推定プログラム。

0164

(付記2)
付記1において、
前記ヒット条件式を生成する処理では、前記キャッシュの状態集合を示す式を生成するプログラムを、前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力としてコンピュータに実行させ、
前記キャッシュの状態集合を示す式を生成するプログラムの実行によって生成された式を、前記ヒット条件式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0165

(付記3)
付記1において、
前記ヒットソース候補式を生成する処理では、前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムを、前記ヒット条件式と、前記ヒット条件式に含まれる前記ループ変数を特定する情報と、前記ヒット条件式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムの実行によって生成された式を、前記ヒットソース候補式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0166

(付記4)
付記3において、
前記ループ変数の辞書式順序の最大値を示す式を生成するプログラムは、パラメトリック整数線形計画法を用いたプログラムである、
ことを特徴とするキャッシュミス推定プログラム。

0167

(付記5)
付記1において、
前記ヒットソース式を生成する処理では、複数の式がそれぞれ示す範囲の重複を排除するプログラムを、前記ヒットソース候補式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、前記ヒットソース式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0168

(付記6)
付記1において、
前記第1回数式を生成する処理では、
前記変数範囲式を生成するプログラムを、前記特定の配列に対応する前記ループ変数と、前記特定の配列に対応する前記ループ変数に対応する前記パラメータ変数とを入力としてコンピュータに実行させ、
前記変数範囲式を生成するプログラムによって生成された式を、前記変数範囲式として生成し、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第1回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0169

(付記7)
付記1において、
前記第2回数式を生成する処理では、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第2回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0170

(付記8)
付記6または7において、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムは、パラメトリック離散体積計算手法を用いたプログラムである、
ことを特徴とするキャッシュミス推定プログラム。

0171

(付記9)
付記1において、
前記競合ミス要因候補式を生成する処理では、前記キャッシュの状態集合を示す式を生成するプログラムを、前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とを入力として実行させ、
前記キャッシュの状態集合を示す式を生成するプログラムの実行によって生成された式を、前記競合ミス要因候補式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0172

(付記10)
付記1において、
前記競合ミス要因式を生成する処理では、
前記競合ミス要因候補式から、前記特定の配列におけるアクセス対象のデータを前記キャッシュから消去するアクセスを表す前記ループ変数を消去して、ループ変数を消去した前記競合ミス要因候補式を生成し、
ループ変数を消去した競合ミス要因候補式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因候補式を生成し、
重複を排除した前記競合ミス要因候補式から、アクセス対象のデータを識別する識別変数を消去して、前記競合ミス要因式を生成する、
ことを特徴とするキャッシュミス推定プログラム。

0173

(付記11)
付記1において、
前記競合ミス要因式を生成する処理では、
式に含まれる変数を消去するプログラムを、前記競合ミス要因候補式と、前記特定の配列におけるアクセス対象のデータを前記キャッシュから消去するアクセスを表す前記ループ変数を特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって前記ループ変数が消去された式を、ループ変数を消去した前記競合ミス要因候補式として生成し、
複数の式がそれぞれ示す範囲の重複を排除するプログラムを、ループ変数を消去した前記競合ミス要因候補式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、重複を排除した前記競合ミス要因候補式として生成し、
前記式に含まれる変数を消去するプログラムを、重複を排除した前記競合ミス要因候補式と、アクセス対象のデータを識別する識別変数を特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって前記識別変数が消去された式を、前記競合ミス要因式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0174

(付記12)
付記1において、
前記第3回数式を生成する処理では、
前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した後の前記競合ミス要因式を生成し、
重複を排除した後の前記競合ミス要因式から、重複を排除した後の前記競合ミス要因式に含まれる前記ループ変数が取り得る値の組み合わせの数を示す式を、前記第3回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0175

(付記13)
付記1において、
前記第3回数式を生成する処理では、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムを、前記競合ミス要因式を入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の重複を排除するプログラムの実行によって生成された式を、重複を排除した後の前記競合ミス要因式として生成し、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、重複を排除した後の前記競合ミス要因式と、重複を排除した後の前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した後の前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第3回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0176

(付記14)
付記1において、
前記競合ミス要因分割式を生成する処理では、
前記データの種類の数毎に、前記競合ミス要因式を、アクセス対象のデータを識別する識別変数を含む第1の式と前記識別変数を含まない第2の式とに分類し、分類した前記第1の式を前記データの種類の数と同じ数に複製し、
前記データの種類の数毎に、複製した前記第1の式それぞれに含まれる前記識別変数を、複製した前記第1の式毎に異なる識別変数に変更し、
前記データの種類の数毎に、前記識別変数を変更した前記第1の式それぞれと、前記第2の式と、変更された前記識別変数それぞれの大小関係を示す式とから、変更された前記識別変数それぞれを消去した式を、第3の式として生成し、
前記データの種類の数毎に、各データの種類の数に対応する前記第3の式が示す範囲と、各データの種類の数よりも1大きい数に対応する前記第3の式が示す範囲との差を、各データの種類の数に対応する前記競合要因分割式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0177

(付記15)
付記14において、
前記第3の式を生成する処理では、
前記データの種類の数毎に、式に含まれる変数を消去するプログラムを、前記識別変数を変更した前記第1の式それぞれと、前記第2の式と、変更された前記識別変数それぞれの大小関係を示す式と、変更された前記識別変数それぞれを特定する情報とを入力としてコンピュータに実行させ、
前記式に含まれる変数を消去するプログラムの実行によって生成された式を、第3の式として生成し、
前記競合要因分割式を生成する処理では、
前記データの種類の数毎に、複数の式がそれぞれ示す範囲の差を示す式を生成するプログラムに、各データの種類の数に対応する前記第3の式と、各データの種類の数よりも1大きい数に対応する前記第3の式とを入力としてコンピュータに実行させ、
前記データの種類の数毎に、前記複数の式がそれぞれ示す範囲の差を示す式を生成するプログラムの実行によって生成された式を、各データの種類の数に対応する前記競合要因分割式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0178

(付記16)
付記14において、
前記データの種類の数は、前記キャッシュの連想数よりも小さい数である、
ことを特徴とするキャッシュミス推定プログラム。

0179

(付記17)
付記1において、
前記競合ミス要因共通式を生成する処理では、複数の式がそれぞれ示す範囲の共通部分を示す式を生成するプログラムを、前記組み合わせに含まれる前記競合ミス要因分割式それぞれを入力としてコンピュータに実行させ、
前記複数の式がそれぞれ示す範囲の共通部分を示す式を生成するプログラムによって生成された式を、前記競合ミス要因共通式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0180

(付記18)
付記1において、
前記第4回数式を生成する処理では、前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムを、前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とを入力としてコンピュータに実行させ、
前記ループ変数が取り得る値の組み合わせの数を示す式を生成するプログラムの実行によって生成された式を、前記第4回数式として生成する、
ことを特徴とするキャッシュミス推定プログラム。

0181

(付記19)
付記1において、さらに、
前記パラメータ変数に対応する値を受け付け、
受け付けた前記パラメータ変数に対応する値を、前記第1回数式から前記第2回数式を減算して生成した式に代入して算出された値と、受け付けた前記パラメータ変数に対応する値を、前記第3回数式から前記第4回数式を減算して生成した式に代入して算出された値との総和を算出する、
処理をコンピュータに実行させることを特徴とするキャッシュミス推定プログラム。

0182

(付記20)
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるCPUにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第1回数式を生成し、前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第2回数式を生成する第1式生成部と、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を、前記ソースコード上の位置毎に生成し、前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成する第2式生成部と、
前記第1回数式から前記第2回数式を減算して生成した式と、前記第3回数式から前記第4回数式を減算して生成した式とを生成する第3式生成部と、を有する、
ことを特徴とする情報処理装置。

0183

(付記21)
プログラムのソースコード上の位置と該位置を囲むループに関連するループ変数を示す情報と前記位置の配列の要素を特定する情報とを含む配列情報と、前記ソースコード上の特定の位置を示す特定位置情報とに基づき、前記特定の位置に対応する特定の配列を特定し、前記特定の配列に対応する前記ソースコード上の位置毎に、前記特定の配列に対応する情報を前記配列情報から取得し、
取得した前記特定の配列に対応する情報と、前記特定位置情報と、前記ループ変数と該ループ変数に対応するループ回数を示すパラメータ変数とを含むループ情報と、前記ソースコードにおける各配列に割り当てられるメモリ内のサイズ及びアドレスを含むデータ情報と、前記プログラムが実行されるCPUにおけるキャッシュの連想数を含むキャッシュ情報とに基づき、前記特定の位置においてアクセスが行われる場合に、アクセス対象のデータが前記特定の配列におけるアクセスによって前記キャッシュに格納されている条件を算出するヒット条件式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒット条件式に基づき、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスの候補を示すヒットソース候補式を、前記特定の配列に対応する前記ソースコード上の位置毎に生成し、
生成した前記ヒットソース候補式それぞれが示すアクセスの候補の重複を排除して、前記キャッシュにデータを格納したアクセスのうち、最後に行われたアクセスを示すヒットソース式を生成し、
前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数と該ループ変数に対応する前記パラメータ変数とから、前記特定の配列に対応する前記ソースコード上の位置を囲むループに関連する前記ループ変数が取り得る値の範囲を示す変数範囲式を生成し、
生成した前記変数範囲式と、前記変数範囲式に含まれる前記ループ変数を特定する情報と、前記変数範囲式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行回数を示す第1回数式を生成し、
前記ヒットソース式と、前記ヒットソース式に含まれる前記ループ変数を特定する情報と、前記ヒットソース式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第2回数式を生成し、
前記ヒットソース式と、前記特定位置情報と、前記ループ情報と、前記データ情報と、前記キャッシュ情報とに基づき、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスの候補を示す競合ミス要因候補式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因候補式それぞれが示すアクセスの重複を排除して、前記特定の位置におけるアクセス対象のデータを前記キャッシュから消去するアクセスを示す競合ミス要因式を、前記ソースコード上の位置毎に生成し、
生成した前記競合ミス要因式それぞれが示すアクセスの重複を排除して、重複を排除した前記競合ミス要因式と、重複を排除した前記競合ミス要因式に含まれる前記ループ変数を特定する情報と、重複を排除した前記競合ミス要因式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータがキャッシュから消去されている回数を示す第3回数式を、前記ソースコード上の位置毎に生成し、
前記キャッシュの連想数に基づき、前記競合ミス要因式毎に、前記競合ミス要因式を、前記特定の位置におけるアクセス対象のデータが前記キャッシュに格納された後に前記キャッシュに格納されたデータの種類の数毎のアクセスに対応する競合ミス要因分割式に分割し、
前記競合ミス要因式それぞれに対応する前記競合ミス要因分割式の前記種類の数の総和が、前記連想数を下回る前記競合ミス要因分割式の組み合わせを特定し、特定した前記組み合わせに含まれる前記競合ミス要因分割式それぞれが示すアクセスにおいて共通するアクセスに対応する競合ミス要因共通式を、前記競合ミス要因式毎に生成し、
生成した前記競合ミス要因共通式と、前記競合ミス要因共通式に含まれる前記ループ変数を特定する情報と、前記競合ミス要因共通式に含まれる前記パラメータ変数を特定する情報とから、前記特定の位置の実行が行われる場合において、アクセス対象のデータが前記キャッシュに格納されている回数を示す第4回数式を生成し、
前記第1回数式から前記第2回数式を減算して生成した式と、前記第3回数式から前記第4回数式を減算して生成した式とを生成する、
ことを特徴とするキャッシュミス推定方法。

0184

1:情報処理装置1a:記憶装置
11:研究者端末NW:ネットワーク

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ