(57)【要約】【課題】キャッシュミスの発生を抑制して性能向上を図ること。【解決手段】情報処理装置１０１は、ソースプログラムｓｃをコンパイルする際に、それぞれの繰り返しで、配列のデータにアクセスするとともにＭ回先の繰り返しでアクセスする配列のデータのプリフェッチを行うループ処理を、第１ループ処理と第２ループ処理とに分割する。第１ループ処理は、ループ処理の先頭からＭ回目までの処理の繰り返しを含む部分である。第２ループ処理は、ループ処理の（Ｍ＋１）回目から最後までの処理の繰り返しを含む部分である。情報処理装置１０１は、第１ループ処理において、キャッシュメモリ内の第１領域を用いて配列のデータのアクセスを行うとともに、キャッシュメモリ内の第２領域を用いて配列のデータのプリフェッチを行い、第２ループ処理において、第２領域を用いて配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する。【選択図】図１
2018010540.tif 000002
【特許請求の範囲】
【請求項１】
プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
制御部を有することを特徴とする情報処理装置。
【請求項２】
前記制御部は、
生成した前記中間言語コードに基づいて、前記プログラムの実行可能ファイルを生成する、ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記制御部は、
前記第１領域のサイズを変えながら、生成した前記実行可能ファイルを実行して、前記サイズに対応する前記第１領域についてのキャッシュミスの数を測定し、
測定した前記キャッシュミスの数が、前記サイズをキャッシュラインで割った値以下となる最小のサイズを前記第１領域のサイズに決定し、
決定した前記第１領域のサイズを示す情報を前記実行可能ファイルと対応付けて出力する、ことを特徴とする請求項２に記載の情報処理装置。
【請求項４】
コンピュータに、
プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
処理を実行させることを特徴とするコンパイルプログラム。
【請求項５】
コンピュータが、
プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
処理を実行することを特徴とするコンパイル方法。
【請求項６】
コンピュータが、
プログラムを実行する際に、ループ処理の先頭から所定回先の繰り返しの直前までの第１ループ処理において、キャッシュメモリ内の第１領域を用いて、それぞれの繰り返しで配列のデータにアクセスするとともに、前記キャッシュメモリ内の第２領域を用いて、前記所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行い、
前記ループ処理の前記所定回先の繰り返しから最後までの第２ループ処理において、前記第２領域を用いて、それぞれの繰り返しで前記配列のデータにアクセスするとともに、前記所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行う、
処理を実行することを特徴とするキャッシュ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法に関する。
【背景技術】
【０００２】
従来、先の処理において利用が予測されるデータを、あらかじめキャッシュメモリに読み出しておくプリフェッチと呼ばれる機能がある。また、キャッシュメモリの一種として、メモリ領域を複数のセクタと呼ばれる単位に分割して、キャッシュラインごとに使用するセクタを選択することができるセクタキャッシュと呼ばれるものがある。
【０００３】
先行技術としては、キャッシュメモリを有効的に利用するための技術がある。例えば、セクタ機能付きキャッシュメモリを搭載する情報処理装置にて実行されるソースプログラムを解析して、各ループにて処理されるデータ集合のループ処理実行時における再利用性の有無を判定するコンパイラ装置がある。このコンパイラ装置は、再利用性の有無を判定したデータ集合を格納するために要するウェイ数とシステムの最大ウェイ数とから、セクタ分割比およびセクタ番号を決定して、ループにおいて、セクタ分割命令およびセクタ番号を付加した命令文を挿入する。
【０００４】
また、データの再利用度に応じて分割されるセクタ機能を備える共有キャッシュメモリと、共有キャッシュメモリのセクタの分割比を変更する制御ユニットと、を有する情報処理装置がある。この制御ユニットは、第１のジョブ、第２のジョブの実行中に、第２のジョブのプログラムの指定に応じて、第１、第２のジョブがアクセスするデータのサイズおよびアクセス回数を有するデータアクセス量と、共有キャッシュメモリの容量とに基づいて、セクタの分割比を算出し、算出したセクタの分割比に変更する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−２４４２０５号公報
【特許文献２】特開２０１５−２２２４７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術では、ソースコード上で連続的に発生することが分かるメモリアクセスであっても、初めの一部分に対しては、その部分で使用するデータをプリフェッチすることが難しく、キャッシュミスが発生して性能低下を招くという問題がある。
【０００７】
一つの側面では、本発明は、キャッシュミスの発生を抑制して性能向上を図ることを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様によれば、プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに、所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する情報処理装置、コンパイルプログラム、およびコンパイル方法が提案される。
【０００９】
また、本発明の一態様によれば、プログラムを実行する際に、ループ処理の先頭から所定回先の繰り返しの直前までの第１ループ処理において、キャッシュメモリ内の第１領域を用いて、それぞれの繰り返しで配列のデータにアクセスするとともに、前記キャッシュメモリ内の第２領域を用いて、前記所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行い、前記ループ処理の前記所定回先の繰り返しから最後までの第２ループ処理において、前記第２領域を用いて、それぞれの繰り返しで前記配列のデータにアクセスするとともに、前記所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うキャッシュ制御方法が提案される。
【発明の効果】
【００１０】
本発明の一側面によれば、キャッシュミスの発生を抑制して性能向上を図ることができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、実施の形態にかかるコンパイル方法の一実施例を示す説明図である。
【図２】図２は、情報処理装置１０１のハードウェア構成例を示すブロック図である。
【図３】図３は、情報処理装置１０１の機能的構成例を示すブロック図である。
【図４】図４は、ループ変形後のソースプログラムｓｃの具体例を示す説明図である。
【図５】図５は、情報処理装置１０１のコンパイル処理手順の一例を示すフローチャートである。
【図６】図６は、ループ変形処理の具体的処理手順の一例を示すフローチャート（その１）である。
【図７】図７は、ループ変形処理の具体的処理手順の一例を示すフローチャート（その２）である。
【図８】図８は、ライン数探索処理の具体的処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下に図面を参照して、本発明にかかる情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法の実施の形態を詳細に説明する。
【００１３】
（実施の形態）
図１は、実施の形態にかかるコンパイル方法の一実施例を示す説明図である。図１において、情報処理装置１０１は、ソースプログラムｓｃをコンパイルして実行可能ファイルｆを生成するコンピュータである。情報処理装置１０１は、例えば、ＰＣ（パーソナル・コンピュータ）、タブレットＰＣなどの汎用演算装置であってもよく、また、サーバであってもよい。
【００１４】
ソースプログラムｓｃは、プログラミング言語を用いて記述されたコンピュータプログラムであり、コンピュータを動作させる命令、手順などを記述したものである。コンパイルとは、プログラミング言語で記述されたソースコードを、コンピュータが解釈可能な機械語（マシン語）としてのオブジェクトコードに変換することである。実行可能ファイルｆは、変換されたオブジェクトコードに、ライブラリなどを付け加えて生成される、実行形式のファイルである。プログラミング言語としては、例えば、Ｃ言語、Ｆｏｒｔｒａｎ、Ｊａｖａ（登録商標）、Ｃ＋＋などがある。
【００１５】
情報処理装置１０１によって生成される実行可能ファイルｆは、セクタキャッシュと呼ばれるキャッシュメモリを有するコンピュータで実行される。セクタキャッシュは、メモリ領域を複数のセクタと呼ばれる単位に分割して、キャッシュラインごとに使用するセクタを選択することができるキャッシュメモリである。
【００１６】
なお、実行可能ファイルｆは、情報処理装置１０１をターゲットとするものでもよいし、他のコンピュータをターゲットとするものでもよい。
【００１７】
ここで、キャッシュミスは、あるデータが必要となったときに、そのデータがキャッシュメモリ上に存在せず、キャッシュメモリからデータを読むことができないことである。キャッシュミスが発生すると、メインメモリからデータを転送してくる時間が待ち時間となるため性能上大きな問題となることがある。
【００１８】
なお、本実施の形態において、単に「キャッシュミス」と表記した場合、デマンドリクエストにより発生するキャッシュミス、すなわち、プリフェッチのときに発生するキャッシュミス以外のキャッシュミス（デマンドミス）を表すものとする。
【００１９】
キャッシュミスを防ぐには、データが必要になる前に、キャッシュメモリにデータを読み出しておくプリフェッチを行うことが有効である。例えば、ソースコード上でメモリアクセスが連続的に発生することが分かっていれば、先の処理で必要となるデータを、あらかじめキャッシュメモリに読み出しておくことができる。
【００２０】
ところが、ソースコード上で連続的に発生することが分かるメモリアクセスであっても、その初めの一部分のものについてはプリフェッチすることが難しい。例えば、データが必要になる十分前のプログラム上の位置が特定できない、もしくは、位置を特定できてもプリフェッチを行う命令を配置するのが難しい場合がある。
【００２１】
より具体的には、例えば、ループ処理の繰り返しの初めの部分で使用するデータをプリフェッチすることは難しい。ループ処理とは、何らかの条件下で処理を繰り返す処理である。例えば、ループ処理は、ｆｏｒ文やｗｈｉｌｅ文によって表現される。また、繰り返しの初めの部分とは、例えば、ループ処理の繰り返しのｉ番目で（ｉ＋Ｍ）番目のデータをプリフェッチする場合、先頭からＭ番目までの繰り返しの部分のことである。
【００２２】
メインメモリからキャッシュメモリにデータを転送するのにかかる時間と、ループ処理の繰り返しがＭ回進む時間とが等しい場合、ｉ番目の繰り返しのときに（ｉ＋Ｍ）番目のデータをプリフェッチすることが多い。したがって、この場合は、先頭からＭ番目までの繰り返しで使用するデータはプリフェッチされない。
【００２３】
例えば、図１に示すプログラム１１０は、ソースプログラムｓｃの一例である。プログラム１１０は、ループＡと、ループＢと、ループＣと、を含む。ｐｒｅｆｅｔｃｈ（ａ［ｉ＋Ｍ］）は、その時点でａ［ｉ＋Ｍ］のデータのメインメモリからキャッシュメモリへの転送を始める、すなわち、プリフェッチすることを意味する。
【００２４】
各ループＡ，Ｂ，Ｃでは、それぞれＭ１，Ｍ２，Ｍ３回先のデータをプリフェッチしている。メインメモリからキャッシュメモリへのデータ転送の時間と同じ時間がかかる各ループＡ，Ｂ，Ｃの繰り返しの数だけ事前にプリフェッチすることで、そのデータを実際に使う処理（ａ［ｉ］＝．．．；）の前にキャッシュメモリに用意しておくことができる。
【００２５】
しかし、各ループＡ，Ｂ，Ｃによってａ［１］からそれぞれａ［Ｍ１］，ａ［Ｍ２］，ａ［Ｍ３］までのデータはプリフェッチされない。これらのデータは、先のループで一旦キャッシュメモリに載るが、ａ［Ｍ１］，ａ［Ｍ２］，ａ［Ｍ３］以降のデータによって、次のループが始まる前に追い出される場合がある。このため、各ループＡ，Ｂ，Ｃにおいて、先頭からそれぞれＭ１，Ｍ２，Ｍ３回目までの繰り返しのときにキャッシュミスが起こる可能性がある。
【００２６】
そこで、本実施の形態では、セクタキャッシュを利用して、連続的に発生するメモリアクセスの初めの一部分に対して専用のセクタを割り当てることにより、その部分におけるキャッシュミスの発生を抑制して性能向上を図るコンパイル方法について説明する。以下、情報処理装置１０１の処理例について説明する。
【００２７】
（１）情報処理装置１０１は、ソースプログラムｓｃをコンパイルする際に、ソースプログラムｓｃ内のループ処理を、第１ループ処理と第２ループ処理とに分割する。ここで、分割対象となるループ処理は、それぞれの繰り返しで、配列のデータにアクセス（参照）するとともに、所定回先の繰り返しでアクセスする配列のデータのプリフェッチを行うループ処理である。配列とは、同じ種類の値を並べて記憶するデータ構造である。配列のデータは、例えば、メインメモリ上に順番に並べて記憶される。
【００２８】
第１ループ処理は、ループ処理の先頭からＭ回目（Ｍ回先の繰り返しの直前）までの処理の繰り返しを含む部分である。第２ループ処理は、ループ処理の（Ｍ＋１）回目（Ｍ回先の繰り返し）から最後までの処理の繰り返しを含む部分である。また、Ｍは、プリフェッチする繰り返し番号の相対位置を示す整数であり、どれだけ先の繰り返しでアクセスする配列のデータをプリフェッチするのかを表す。
【００２９】
Ｍの値は、任意に設定することができる。例えば、Ｍの値として、ソースプログラムｓｃ内の各ループ処理に定義されている値（プログラム１１０では、Ｍ１，Ｍ２，Ｍ３）がそれぞれ設定されることにしてもよい。また、Ｍの値として、ソースプログラムｓｃ内の各ループ処理に定義されている値のうちの最大値（プログラム１１０では、Ｍ１，Ｍ２，Ｍ３のうちの最大値）が設定されることにしてもよい。
【００３０】
一例として、プログラム１１０のループＡを例に挙げると、符号１２０に示すように、ループＡが、先頭からＭ回目までの第１ループ処理と、（Ｍ＋１）回目から最後までの第２ループ処理とに分割される。ただし、Ｍは、プログラム１１０内のループＡ，Ｂ，Ｃに定義されているＭ１，Ｍ２，Ｍ３のうちの最大値である。
【００３１】
（２）情報処理装置１０１は、第１ループ処理において、キャッシュメモリ内の第１領域を用いて配列のデータのアクセスを行うとともに、キャッシュメモリ内の第２領域を用いて配列のデータのプリフェッチを行う中間言語コードを生成する。また、情報処理装置１０１は、第２ループ処理において、第２領域を用いて配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する。
【００３２】
ここで、第１領域は、キャッシュメモリを区切って分割した複数のセクタのうちのいずれかのセクタ（以下、「セクタＡ」という）である。また、第２領域は、キャッシュメモリ内の第１領域と重複しない領域であり、キャッシュメモリを区切って分割した複数のセクタのうちのセクタＡとは異なる他のセクタ（以下、「セクタＢ」という）である。また、中間言語コードは、プログラミング言語で記述されるソースコードと、機械語としてオブジェクトコードとの中間にあたる中間表現の言語で表現されたコードである。
【００３３】
一例として、プログラム１１０のループＡを例に挙げると、符号１３０に示すように、第１ループ処理において、セクタＡを用いて配列のデータのアクセスを行うとともに、セクタＢを用いて配列のデータのプリフェッチを行う中間言語コードが生成される。また、符号１３０に示すように、第２ループ処理において、セクタＢを用いて配列のデータのアクセスおよびプリフェッチを行う中間言語コードが生成される。
【００３４】
なお、実際には、符号１２０のようにソースレベルでループ処理が変形されるのではなく、コンパイラ内部の表現に対する処理が行われる。例えば、符号１２０では、どちらのセクタを使用するかが、行ごとに括弧内に表現されているが、実際はコンパイラの内部で記録され、マシン語に変換される際にその情報に従って命令が選択される。
【００３５】
（３）情報処理装置１０１は、生成した中間言語コードに基づいて、ソースプログラムｓｃの実行可能ファイルｆを生成する。具体的には、例えば、情報処理装置１０１は、生成した中間言語コードを機械語の命令の列に変換することにより、ソースプログラムｓｃの実行可能ファイルｆを生成する。
【００３６】
生成された実行可能ファイルｆは、例えば、情報処理装置１０１の記憶装置に記憶される、あるいは、他のコンピュータに出力される。
【００３７】
このように、情報処理装置１０１によれば、ソースプログラムｓｃ上で連続的に発生するメモリアクセスの初めの一部分に対して専用のセクタを割り当てることにより、その部分におけるキャッシュミスの発生を抑制して性能向上を図ることができる。
【００３８】
プログラム１１０の例では、ループＢ，Ｃについても、符号１２０に示すループＡのように変形することで、ａ［ｉ］からａ［Ｍ］のデータはループＡでキャッシュミス（デマンドミス）するが、他のデータがセクタＡを使わないため追い出されず、ループＢとループＣではデマンドミスが発生しないことになる。
【００３９】
（情報処理装置１０１のハードウェア構成例）
図２は、情報処理装置１０１のハードウェア構成例を示すブロック図である。図２において、情報処理装置１０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２０１と、メモリ２０２と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）２０３と、ディスクドライブ２０４と、ディスク２０５と、を有する。また、各構成部は、バス２００によってそれぞれ接続される。
【００４０】
ここで、ＣＰＵ２０１は、情報処理装置１０１の全体の制御を司る。メモリ２０２は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）およびフラッシュＲＯＭなどを有する。具体的には、例えば、フラッシュＲＯＭやＲＯＭが各種プログラムを記憶し、ＲＡＭがＣＰＵ２０１のワークエリアとして使用される。ＲＡＭは、例えば、メインメモリとキャッシュメモリ（セクタキャッシュ）とを含む。メモリ２０２に記憶されるプログラムは、ＣＰＵ２０１にロードされることで、コーディングされている処理をＣＰＵ２０１に実行させる。また、メモリ２０２は、メインメモリと、ＣＰＵ２０１とメインメモリとの間に置かれるキャッシュメモリとを含む。キャッシュメモリは、例えば、セクタキャッシュである。
【００４１】
Ｉ／Ｆ２０３は、通信回線を通じてネットワーク２１０に接続され、ネットワーク２１０を介して外部のコンピュータに接続される。ネットワーク２１０は、例えば、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、移動体通信網などを含む。そして、Ｉ／Ｆ２０３は、ネットワーク２１０と装置内部とのインターフェースを司り、外部のコンピュータからのデータの入出力を制御する。Ｉ／Ｆ２０３には、例えば、モデムやＬＡＮアダプタなどを採用することができる。
【００４２】
ディスクドライブ２０４は、ＣＰＵ２０１の制御に従ってディスク２０５に対するデータのリード／ライトを制御する。ディスク２０５は、ディスクドライブ２０４の制御で書き込まれたデータを記憶する。ディスク２０５としては、例えば、磁気ディスク、光ディスクなどが挙げられる。
【００４３】
なお、情報処理装置１０１は、上述した構成部のほかに、例えば、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、入力装置、ディスプレイ等を有することにしてもよい。
【００４４】
（情報処理装置１０１の機能的構成例）
図３は、情報処理装置１０１の機能的構成例を示すブロック図である。図３において、情報処理装置１０１は、取得部３０１と、解析部３０２と、第１の生成部３０３と、最適化部３０４と、第２の生成部３０５と、決定部３０６と、出力部３０７と、を含む構成である。取得部３０１〜出力部３０７は制御部となる機能であり、具体的には、例えば、図２に示したメモリ２０２、ディスク２０５などの記憶装置に記憶されたプログラムをＣＰＵ２０１に実行させることにより、または、Ｉ／Ｆ２０３により、その機能を実現する。各機能部の処理結果は、例えば、メモリ２０２、ディスク２０５などの記憶装置に記憶される。
【００４５】
取得部３０１は、ソースプログラムｓｃを取得する。具体的には、例えば、取得部３０１は、不図示の入力装置を用いたユーザの操作入力により、ソースプログラムｓｃ（例えば、図１に示したプログラム１１０）を取得する。また、例えば、取得部３０１は、Ｉ／Ｆ２０３により、外部のコンピュータからソースプログラムｓｃを取得することにしてもよい。
【００４６】
解析部３０２は、ソースプログラムｓｃの構文解析および意味解析を行う。ここで、構文解析とは、ソースプログラムｓｃに記述された文や構造が言語仕様に沿っているか否かをチェックすることである。意味解析とは、ソースプログラムｓｃに記述された変数の型や文が意味的に正しいか否かをチェックすることである。
【００４７】
具体的には、例えば、まず、解析部３０２は、ソースプログラムｓｃの字句解析を行う。字句解析とは、ソースプログラムｓｃを構成する文字の並びを、例えば、キーワード、変数、演算子などのトークンの並びに変換することである。そして、解析部３０２は、字句解析により得られるトークンの並びについて、トークン間の関係を解析することにより、ソースプログラムｓｃの構文解析および意味解析を行う。
【００４８】
第１の生成部３０３は、ソースプログラムｓｃの構文解析および意味解析により得られる中間言語コードに基づいて、ソースプログラムｓｃ内のループ処理を、第１ループ処理と第２ループ処理とに分割する。ここで、分割対象となるループ処理は、それぞれの繰り返しで、配列のデータにアクセスするとともに、Ｍ回先の繰り返しでアクセスする配列のデータのプリフェッチを行うループ処理である。
【００４９】
また、第１ループ処理は、ループ処理の先頭からＭ回目までの処理の繰り返しを含む部分である。第２ループ処理は、ループ処理の（Ｍ＋１）回目から最後までの処理の繰り返しを含む部分である。Ｍは、プリフェッチする繰り返し番号の相対位置を示す整数であり、どれだけ先の繰り返しでアクセスする配列のデータをプリフェッチするのかを表す。
【００５０】
以下の説明では、ソースプログラムｓｃ内のループ処理であって、それぞれの繰り返しで配列のデータにアクセスするとともに、Ｍ回先の繰り返しでアクセスする配列のデータのプリフェッチを行うループ処理を「ループＲ」と表記する場合がある。
【００５１】
具体的には、例えば、第１の生成部３０３は、ループリストに登録されたループＲそれぞれについて、第１ループＲ１と第２ループＲ２とに分割する。ループリストは、ソースプログラムｓｃ内のループＲがリスト構造で記録されたものである。
【００５２】
より詳細に説明すると、第１の生成部３０３は、例えば、ループＲを複製して第１ループＲ１を生成する。つぎに、第１の生成部３０３は、第１ループＲ１の繰り返し開始番号として、ループＲの繰り返し開始番号「Ｂ」を設定する。ここで、繰り返し開始番号とは、初めに処理を行うときの変数の値であり、例えば、ｆｏｒ文におけるループ変数の初期値である。
【００５３】
また、第１の生成部３０３は、第１ループＲ１の繰り返し終了番号として、「Ｂ＋Ｍ」を設定する。ここで、繰り返し終了番号とは、繰り返しの処理を終了するときの変数の値であり、例えば、ｆｏｒ文におけるループ変数の上限値である。Ｍの値としては、例えば、全てのループＲで最大の値が設定される。
【００５４】
つぎに、第１の生成部３０３は、第１ループＲ１がループＲの直前に実行されるように、中間言語コードにおけるループＲの直前に第１ループＲ１を挿入する。そして、第１の生成部３０３は、中間言語コードにおけるループＲの繰り返し開始番号を「Ｂ＋Ｍ＋１」に変更することにより、第２ループＲ２（ループＲ）を生成する。
【００５５】
また、第１の生成部３０３は、第１ループＲ１において、キャッシュメモリ内のセクタＡを用いて配列のデータにアクセスするとともに、キャッシュメモリ内のセクタＢを用いて配列のデータのプリフェッチを行う中間言語コードを生成する。また、第１の生成部３０３は、第２ループＲ２において、セクタＢを用いて、配列のデータにアクセスするとともに、配列のデータのプリフェッチを行う中間言語コードを生成する。
【００５６】
ここで、セクタＡは、上述したように、キャッシュメモリ（セクタキャッシュ）を区切って分割した複数のセクタのうちのいずれかのセクタである。また、セクタＢは、キャッシュメモリを区切って分割した複数のセクタのうちのセクタＡとは異なる他のセクタである。
【００５７】
具体的には、例えば、第１の生成部３０３は、第１ループＲ１において、配列のデータへのアクセスに使用するセクタを「セクタＡ」とする情報を第１ループＲ１に付加する。すなわち、第１ループＲ１における全てのメモリアクセスに使用するセクタを「セクタＡ」とする。
【００５８】
より詳細に説明すると、例えば、メインメモリにはロードストア命令でアクセスすることになる。このロードストア命令には、どのセクタを使うかを指定するフィールドがある。第１の生成部３０３は、そのフィールドに「セクタＡ」を設定したマシン語を生成するように、中間言語コードにおいて情報を第１ループＲ１に付加する。
【００５９】
また、第１の生成部３０３は、第１ループＲ１において、先の繰り返しでアクセスする配列のデータのプリフェッチに使用するセクタを「セクタＢ」とする情報を第１ループＲ１に付加する。すなわち、第１ループＲ１における全てのプリフェッチに使用するセクタを「セクタＢ」とする。
【００６０】
また、第１の生成部３０３は、第２ループＲ２において、配列のデータへのアクセスおよび先の繰り返しでアクセスする配列のデータのプリフェッチに使用するセクタを「セクタＢ」とする情報を第２ループＲ２に付加する。すなわち、第２ループＲ２における全てのメモリアクセスおよびプリフェッチに使用するセクタを「セクタＢ」とする。
【００６１】
これにより、ソースプログラムｓｃ内の各ループＲについて、繰り返しの初めの一部分（第１ループＲ１）に対してセクタＡを割り当て、残りの部分に対してセクタＢを割り当てるように、各ループＲを変形することができる。
【００６２】
一例として、図１に示したプログラム１１０を例に挙げると、第１の生成部３０３によって生成される中間言語コードをソースレベルで表現すると、図４のようになる。
【００６３】
図４は、ループ変形後のソースプログラムｓｃの具体例を示す説明図である。図４において、プログラム４００は、プログラム１１０内の各ループＡ，Ｂ，Ｃについてのループ変形をソースレベルで表現したものである。プログラム４００のように、各ループＡ，Ｂ，Ｃを変形することにより、ａ［ｉ］からａ［Ｍ］のデータはループＡでキャッシュミスするが、他のデータがセクタＡを使わないため追い出されず、ループＢとループＣではデマンドミスが発生しないことになる。
【００６４】
なお、プログラム４００において、どちらのセクタを使用するかを行ごとに括弧内に表現しているが、実際はコンパイラの内部で記録され、マシン語に変換される際にその情報に従って命令が選択される。すなわち、実際にはソースレベルでループＲが変形されるのではなく、上述したように、コンパイラ内部の表現（中間言語コード）に対する処理が行われる。
【００６５】
ただし、ここでは、コンパイラ内部の表現（中間言語コード）に対して、ソースプログラムｓｃの全てのループＲがリスト構造で記録され操作できること、ループＲの繰り返し開始／終了番号を操作できることを前提としている。また、ループＲのメモリアクセスやプリフェッチの処理に、後のマシン語生成で参照する情報を付加できること、ループＲ中に新たな処理を追加することができることを前提としている。このようなことができることは、既存のコンパイラ技術では一般的である。
【００６６】
図３の説明に戻り、最適化部３０４は、第１の生成部３０３によって生成されたソースプログラムｓｃの中間言語コードの最適化処理を行う。具体的には、例えば、最適化部３０４は、生成された中間言語コードから、どこからも呼び出しがないメソッドを不要なメソッドと見なして削除したりする。
【００６７】
なお、上述した第１の生成部３０３による処理は、最適化部３０４によって最適化処理が施されたソースプログラムｓｃの中間言語コードに基づいて行われることにしてもよい。すなわち、最適化部３０４は、例えば、ソースプログラムｓｃの構文解析および意味解析により得られる中間言語コードの最適化処理を行って、第１の生成部３０３に出力することにしてもよい。
【００６８】
第２の生成部３０５は、ソースプログラムｓｃの中間言語コードに基づいて、ソースプログラムｓｃの実行可能ファイルｆを生成する。具体的には、例えば、第２の生成部３０５は、最適化部３０４または第１の生成部３０３から出力される中間言語コードを機械語の命令の列に変換することにより、ソースプログラムｓｃの実行可能ファイルｆを生成する。
【００６９】
決定部３０６は、キャッシュメモリ（セクタキャッシュ）内のセクタＡのサイズと、セクタＢのサイズとを決定する。ここで、セクタＡおよびセクタＢのサイズ（記憶容量）は、例えば、キャッシュラインのライン数によって表される。また、キャッシュメモリ内のセクタ数を「２」とすると、セクタＢのサイズは、キャッシュメモリの全体サイズからセクタＡのサイズを引くことで求めることができる。
【００７０】
具体的には、例えば、決定部３０６は、セクタＡのサイズをある値に設定して、生成された実行可能ファイルｆを実行することにより、セクタＡについてのキャッシュミスの数（以下、「キャッシュミス数ｄ」という）を測定する。つぎに、決定部３０６は、測定したキャッシュミス数ｄが、セクタＡのサイズをキャッシュラインで割った値、すなわち、セクタＡのライン数以下となるか否かを判断する。
【００７１】
決定部３０６は、セクタＡのサイズ（ライン数）を変えながら、キャッシュミス数ｄが、セクタＡのライン数以下となる最小のサイズ（ライン数）を探索する。そして、決定部３０６は、探索した最小のサイズを、セクタＡのサイズに決定する。これにより、セクタＡで発生するキャッシュミスの数が最小となる中で、最小のサイズとなるセクタＡのサイズを求めることができる。
【００７２】
なお、セクタＡのライン数をある値に設定したとき、キャッシュミス数ｄよりライン数が大きい場合は、探索したいライン数はそれ以下の値であり、キャッシュミス数ｄより小さい場合は、探索したいライン数はそれ以上の値である。このため、最小のサイズの探索については、二分法などを利用することができる。
【００７３】
また、セクタＡのサイズが大きくなりすぎると、セクタＡを設けないときはキャッシュメモリに載っていたデータが追い出されて処理時間が増加する可能性がある。このため、セクタＡのサイズとして設定し得る最大サイズをあらかじめ設定することにしてもよい。例えば、不図示の入力装置を用いたユーザの操作入力により、セクタＡの最大サイズを、セクタキャッシュ全体の２割程度に設定することにしてもよい。
【００７４】
そして、情報処理装置１０１は、探索したセクタＡの最小サイズが、あらかじめ設定した最大サイズ以上となる場合には、本手法を適用せず、ソースプログラムｓｃに対して既存のコンパイル処理を行うことにしてもよい。既存のコンパイル処理は、例えば、構文・意味解析処理、最適化処理およびコード生成処理を含む。
【００７５】
なお、セクタＡのサイズ（最小サイズ）を探索する具体的な処理内容については、図８を用いて後述する。
【００７６】
出力部３０７は、生成されたソースプログラムｓｃの実行可能ファイルｆを出力する。出力部３０７の出力形式としては、例えば、メモリ２０２、ディスク２０５などの記憶装置への記憶、Ｉ／Ｆ２０３による外部のコンピュータへの送信などがある。
【００７７】
具体的には、例えば、出力部３０７は、ソースプログラムｓｃの実行可能ファイルｆと、決定されたセクタＡおよびセクタＢのライン数を示すライン情報とを対応付けて出力することにしてもよい。これにより、セクタキャッシュを有するコンピュータにおいて、ライン情報が示すセクタＡおよびセクタＢのライン数を設定して、ソースプログラムｓｃの実行可能ファイルｆを実行することができる。
【００７８】
例えば、情報処理装置１０１は、ソースプログラムｓｃ内のループＲそれぞれについて、先頭からＭ回目までの第１ループＲ１において、セクタＡを用いて配列のデータにアクセスするとともに、セクタＢを用いて配列のデータのプリフェッチを行うことができる。また、情報処理装置１０１は、（Ｍ＋１）回目から最後までの第２ループＲ２において、セクタＢを用いて配列のデータにアクセスするとともに配列のデータのプリフェッチを行うことができる。このため、既存のコンパイル処理を施した場合に比べて、ループＲの繰り返しの初めの一部分のデータについてのキャッシュミスの発生を抑制して性能向上を図ることができる。
【００７９】
（情報処理装置１０１のコンパイル処理手順）
つぎに、情報処理装置１０１のコンパイル処理手順について説明する。
【００８０】
図５は、情報処理装置１０１のコンパイル処理手順の一例を示すフローチャートである。図５のフローチャートにおいて、まず、情報処理装置１０１は、ソースプログラムｓｃを読み込む（ステップＳ５０１）。
【００８１】
つぎに、情報処理装置１０１、ソースプログラムｓｃの字句解析を行う（ステップＳ５０２）。そして、情報処理装置１０１は、字句解析により得られるトークンの並びについて、トークン間の関係を解析することにより、ソースプログラムｓｃの構文解析および意味解析を行う（ステップＳ５０３）。
【００８２】
つぎに、情報処理装置１０１は、ソースプログラムｓｃの構文解析および意味解析により得られる中間言語コードに基づいて、ソースプログラムｓｃ内のループＲを第１ループＲ１と第２ループＲ２とに変形するループ変形処理を実行する（ステップＳ５０４）。ループ変形処理の具体的な処理手順については、図６および図７を用いて後述する。
【００８３】
つぎに、情報処理装置１０１は、ソースプログラムｓｃの中間言語コードの最適化処理を行う（ステップＳ５０５）。なお、最適化処理は、例えば、ステップＳ５０４のループ変形処理の直前に実行することにしてもよい。そして、情報処理装置１０１は、ソースプログラムｓｃの中間言語コードに基づいて、ソースプログラムｓｃの実行可能ファイルｆを生成する（ステップＳ５０６）。
【００８４】
つぎに、情報処理装置１０１は、キャッシュメモリ（セクタキャッシュ）内のセクタＡのライン数（サイズ）を探索するライン数探索処理を実行する（ステップＳ５０７）。ライン数探索処理の具体的な処理手順については、図８を用いて後述する。そして、情報処理装置１０１は、セクタＡのライン数が探索されたか否かを判断する（ステップＳ５０８）。
【００８５】
ここで、セクタＡのライン数が探索された場合（ステップＳ５０８：Ｙｅｓ）、情報処理装置１０１は、ソースプログラムｓｃの実行可能ファイルｆと、セクタＡおよびセクタＢのライン数を示すライン情報とを対応付けて出力する（ステップＳ５０９）。そして、情報処理装置１０１は、本フローチャートによる一連の処理を終了する。
【００８６】
一方、ステップＳ５０８において、セクタＡのライン数が探索されなかった場合（ステップＳ５０８：Ｎｏ）、情報処理装置１０１は、ソースプログラムｓｃに対して、既存のコンパイル処理を実行する（ステップＳ５１０）。そして、情報処理装置１０１は、既存のコンパイル処理により得られるソースプログラムｓｃの実行可能ファイルｆを出力して（ステップＳ５１１）、本フローチャートによる一連の処理を終了する。
【００８７】
これにより、ソースプログラムｓｃ内の各ループＲにおいて連続的に発生するメモリアクセスの初めの一部分に対して専用のセクタＡを割り当てて、プログラム実行時におけるキャッシュミスの発生を抑制する実行可能ファイルｆを生成することができる。
【００８８】
＜ループ変形処理手順＞
つぎに、図５に示したステップＳ５０４のループ変形処理の具体的な処理手順について説明する。
【００８９】
図６および図７は、ループ変形処理の具体的処理手順の一例を示すフローチャートである。図６のフローチャートにおいて、まず、情報処理装置１０１は、ソースプログラムｓｃのループリストに含まれる各ループＲでプリフェッチする繰り返し番号の相対位置を示す整数Ｍを特定する（ステップＳ６０１）。
【００９０】
つぎに、情報処理装置１０１は、特定した各ループＲの整数Ｍのうちの最大値Ｍmaxを、全ループＲで共通の整数Ｍの値に設定する（ステップＳ６０２）。そして、情報処理装置１０１は、ループリストの先頭から未選択のループＲ（以下、「ｌｏｏｐ」という）を選択する（ステップＳ６０３）。
【００９１】
つぎに、情報処理装置１０１は、選択したｌｏｏｐの繰り返し開始番号Ｂを特定する（ステップＳ６０４）。そして、情報処理装置１０１は、選択したｌｏｏｐを複製してｌｏｏｐ’を生成する（ステップＳ６０５）。
【００９２】
つぎに、情報処理装置１０１は、ｌｏｏｐ’の繰り返し開始番号に、特定したｌｏｏｐの繰り返し開始番号Ｂを設定する（ステップＳ６０６）。そして、情報処理装置１０１は、ｌｏｏｐ’の繰り返し終了番号に、「Ｂ＋Ｍ」を設定する（ステップＳ６０７）。なお、整数Ｍの値は、ステップＳ６０２において設定されたＭmaxである。
【００９３】
つぎに、情報処理装置１０１は、ｌｏｏｐ’の全てのメモリアクセスの使用セクタをセクタＡとする情報をｌｏｏｐ’に付加する（ステップＳ６０８）。そして、情報処理装置１０１は、ｌｏｏｐ’の全てのプリフェッチの使用セクタをセクタＢとする情報をｌｏｏｐ’に付加して（ステップＳ６０９）、図７に示すステップＳ７０１に移行する。
【００９４】
図７のフローチャートにおいて、まず、情報処理装置１０１は、ｌｏｏｐ’がｌｏｏｐの直前に実行されるように、ｌｏｏｐの直前にｌｏｏｐ’を挿入する（ステップＳ７０１）。つぎに、情報処理装置１０１は、ｌｏｏｐの繰り返し開始番号に「Ｂ＋Ｍ＋１」を設定する（ステップＳ７０２）。
【００９５】
つぎに、情報処理装置１０１は、ｌｏｏｐの全てのメモリアクセス、プリフェッチの使用セクタをセクタＢとする情報をｌｏｏｐに付加する（ステップＳ７０３）。そして、情報処理装置１０１は、ループリストから選択されていない未選択のｌｏｏｐがあるか否かを判断する（ステップＳ７０４）。
【００９６】
ここで、未選択のｌｏｏｐがある場合（ステップＳ７０４：Ｙｅｓ）、情報処理装置１０１は、図６に示したステップＳ６０３に戻る。一方、未選択のｌｏｏｐがない場合（ステップＳ７０４：Ｎｏ）、情報処理装置１０１は、ループ変形処理を呼び出したステップに戻る。
【００９７】
これにより、ソースプログラムｓｃ内の各ループＲを、先頭からＭ回目までのｌｏｏｐ’と、（Ｍ＋１）回目から最後までのｌｏｏｐとに分割することができる。また、ｌｏｏｐ’において、キャッシュメモリ内のセクタＡを用いて配列のデータのアクセスを行わせ、キャッシュメモリ内のセクタＢを用いて配列のデータのプリフェッチを行わせることができる。また、ｌｏｏｐにおいて、キャッシュメモリ内のセクタＢを用いて配列のデータのアクセスおよびプリフェッチを行わせることができる。
【００９８】
＜ライン数探索処理手順＞
つぎに、図５に示したステップＳ５０７のライン数探索処理の具体的な処理手順について説明する。ここでは、二分法を利用して、キャッシュメモリ内のセクタＡの最小のサイズ（ライン数）を探索する場合を例に挙げて説明する。
【００９９】
図８は、ライン数探索処理の具体的処理手順の一例を示すフローチャートである。図８において、まず、情報処理装置１０１は、変数ｌ（ｌｅｆｔ）を「ｌ＝０」とし（ステップＳ８０１）、変数ｒ（ｒｉｇｈｔ）を「ｒ＝ＬA_max＋１」とする（ステップＳ８０２）。ＬA_maxは、セクタＡのサイズとして設定し得る最大サイズを示す閾値である。
【０１００】
つぎに、情報処理装置１０１は、キャッシュメモリ内のセクタＡのライン数ＬAを「ＬA＝切り上げ（（ｌ＋ｒ）／２）」とし（ステップＳ８０３）、キャッシュメモリ内のセクタＢのライン数ＬBを「ＬB＝Ｌtotal−ＬA」とする（ステップＳ８０４）。なお、切り上げ（）は、小数点以下を切り上げることを表す。Ｌtotalは、キャッシュメモリ全体のサイズ（ライン数）を示す。
【０１０１】
つぎに、情報処理装置１０１は、図５に示したステップＳ５０６において生成されたソースプログラムｓｃの実行可能ファイルｄを実行して、セクタＡについてのキャッシュミス数ｄを測定する（ステップＳ８０５）。そして、情報処理装置１０１は、測定したキャッシュミス数ｄがライン数ＬA以下であるか否かを判断する（ステップＳ８０６）。
【０１０２】
ここで、キャッシュミス数ｄがライン数ＬA以下の場合（ステップＳ８０６：Ｙｅｓ）、情報処理装置１０１は、変数ｒを「ｒ＝切り上げ（（ｌ＋ｒ）／２）」として（ステップＳ８０７）、ステップＳ８０９に移行する。一方、キャッシュミス数ｄがライン数ＬAより大きい場合（ステップＳ８０６：Ｎｏ）、情報処理装置１０１は、変数ｌを「ｌ＝切り上げ（（ｌ＋ｒ）／２）」とする（ステップＳ８０８）。
【０１０３】
そして、情報処理装置１０１は、「ｌ＋１＝ｒ」となったか否かを判断する（ステップＳ８０９）。ここで、「ｌ＋１＝ｒ」となっていない場合（ステップＳ８０９：Ｎｏ）、情報処理装置１０１は、ステップＳ８０３に戻る。一方、「ｌ＋１＝ｒ」となった場合（ステップＳ８０９：Ｙｅｓ）、情報処理装置１０１は、変数ｒが閾値ＬA_max以下であるか否かを判断する（ステップＳ８１０）。
【０１０４】
ここで、変数ｒが閾値ＬA_max以下の場合（ステップＳ８１０：Ｙｅｓ）、情報処理装置１０１は、セクタＡのライン数ＬAを「ＬA＝ｒ」に決定し（ステップＳ８１１）、セクタＢのライン数ＬBを「ＬB＝Ｌtotal−ＬA」に決定して（ステップＳ８１２）、ライン数探索処理を呼び出したステップに戻る。
【０１０５】
一方、変数ｒが閾値ＬA_maxより大きい場合（ステップＳ８１０：Ｎｏ）、情報処理装置１０１は、ソースプログラムｓｃに対して本手法を適用不可であると判断して（ステップＳ８１３）、ライン数探索処理を呼び出したステップに戻る。
【０１０６】
これにより、セクタＡで発生するキャッシュミスの数が最小となる中で、最小のサイズとなるセクタＡのサイズを探索することができる。
【０１０７】
以上説明したように、実施の形態にかかる情報処理装置１０１によれば、ソースプログラムｓｃ内のループＲを、先頭からＭ回先の繰り返しの直前までの第１ループＲ１と、Ｍ回先の繰り返しから最後までの第２ループＲ２とに分割することができる。また、情報処理装置１０１によれば、第１ループＲ１において、キャッシュメモリ内のセクタＡを用いて配列のデータのアクセスを行うとともに、キャッシュメモリ内のセクタＢを用いて配列のデータのプリフェッチを行い、第２ループＲ２において、セクタＢを用いて、配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成することができる。そして、情報処理装置１０１によれば、生成した中間言語コードに基づいて、ソースプログラムｓｃの実行可能ファイルｆを生成することができる。
【０１０８】
これにより、ソースプログラムｓｃ内の各ループＲにおいて連続的に発生するメモリアクセスの初めの一部分に対して、キャッシュメモリ（セクタキャッシュ）内の専用のセクタＡを割り当てることができる。このため、その部分のデータがキャッシュメモリから追い出されにくくなり、プリフェッチしなくてもデマンドミスの発生を抑制して性能向上を図ることができる。
【０１０９】
また、情報処理装置１０１によれば、セクタＡのサイズを変えながら、生成した実行可能ファイルｆを実行して、当該サイズに対応するセクタＡについてのキャッシュミス数ｄを測定することができる。そして、情報処理装置１０１によれば、測定したキャッシュミス数ｄがライン数ＬA以下となる最小のサイズを、セクタＡのサイズに決定して、決定したセクタＡのサイズを示すライン情報を実行可能ファイルｆと対応付けて出力することができる。ライン数ＬAは、セクタＡのサイズをキャッシュラインで割った値である。
【０１１０】
これにより、キャッシュメモリ内のセクタＡで発生するキャッシュミスの数が最小となる中で、最小のサイズとなるセクタＡのサイズを探索して、当該サイズをセクタＡのサイズに設定することができる。
【０１１１】
また、情報処理装置１０１によれば、ライン情報に基づいて、キャッシュメモリ内のセクタＡおよびセクタＢのサイズを設定して、実行可能ファイルｆを実行することができる。具体的には、情報処理装置１０１は、ループＲの先頭からＭ回先の繰り返しの直前までの第１ループＲ１において、セクタＡを用いて、配列のデータにアクセスするとともに、セクタＢを用いて、Ｍ回先の繰り返しでアクセスする配列のデータのプリフェッチを行う。また、情報処理装置１０１は、ループＲのＭ回先の繰り返しから最後までの第２ループＲ２において、セクタＢを用いて、配列のデータにアクセスするとともに、Ｍ回先の繰り返しでアクセスする配列のデータのプリフェッチを行う。
【０１１２】
これにより、セクタＡのサイズとして必要十分なサイズを割り当てることができ、ソースプログラムｓｃの実行時に、セクタＡのサイズが大きくなりすぎることにより生じるキャッシュミスを抑制して性能向上を図ることができる。
【０１１３】
ここで、キャッシュ容量が「５１２［ＫｉＢ／スレッド］」、ラインサイズ（キャッシュライン）が「１２８［Ｂ］」、メモリ帯域が「１０［ＧｉＢ／ｓ／スレッド］」、メモリレイテンシが「１００［ｎｓ］」であるコンピュータがあるとする。このコンピュータを使用して、ループ全体で１２８［ＫｉＢ／スレッド］の配列１つを昇順にアクセスするソースプログラムｓｃを実行する場合を想定する。
【０１１４】
ループの開始時点で配列の一部もキャッシュメモリに載っていないが、デマンドミスによるメインメモリからのデータ転送待ち時間を無視した理想的な実行時間は、転送サイズとメモリ帯域より、「１２８［ＫｉＢ］／１０［ＧｉＢ／ｓ］＝１２［μｓ］」となる。なお、実際はキャッシュメモリからＣＰＵにデータを転送する待ち時間が存在するが、メインメモリの待ち時間に比べて非常に小さいため無視できるものとする。
【０１１５】
メモリレイテンシ分の１００［ｎｓ］手前でプリフェッチをする必要があるため、プリフェッチを行うタイミングは、１０［ＧｉＢ／ｓ］＊１００［ｎｓ］／１２８［Ｂ］＝９ライン手前となる。したがって、図１に示したようなプログラム１１０のプリフェッチでは、繰り返しの最初の９ラインはデマンドミスすることになる。
【０１１６】
理想的な実行時間１２［μｓ］に対して、デマンドミスによる待ち時間を含めると、「１２．９［μｓ］（＝９＊１００［ｎｓ］＋１２［μｓ］）」かかるため、８％の影響がある。本手法を使うと、理想的な実行時間を達成でき、さらにそのために消費するキャッシュ容量も全体の「０．２％（９ライン＊１２８［Ｂ／ライン］／５１２［ＫｉＢ］）」で済む。
【０１１７】
なお、本実施の形態で説明したコンパイル方法およびキャッシュ制御方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本コンパイルプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）メモリ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また、本コンパイルプログラムは、インターネット等のネットワークを介して配布してもよい。
【０１１８】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１１９】
（付記１）プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
制御部を有することを特徴とする情報処理装置。
【０１２０】
（付記２）前記制御部は、
生成した前記中間言語コードに基づいて、前記プログラムの実行可能ファイルを生成する、ことを特徴とする付記１に記載の情報処理装置。
【０１２１】
（付記３）前記制御部は、
前記第１領域のサイズを変えながら、生成した前記実行可能ファイルを実行して、前記サイズに対応する前記第１領域についてのキャッシュミスの数を測定し、
測定した前記キャッシュミスの数が、前記サイズをキャッシュラインで割った値以下となる最小のサイズを前記第１領域のサイズに決定し、
決定した前記第１領域のサイズを示す情報を前記実行可能ファイルと対応付けて出力する、ことを特徴とする付記２に記載の情報処理装置。
【０１２２】
（付記４）メモリ領域を第１領域と第２領域とに分割して、キャッシュラインごとに使用する領域を選択可能なキャッシュメモリを有し、
前記制御部は、
前記第１領域のサイズを示す情報に基づいて、前記キャッシュメモリ内の前記第１領域および前記第２領域のサイズを設定して、前記実行可能ファイルを実行する、ことを特徴とする付記３に記載の情報処理装置。
【０１２３】
（付記５）コンピュータに、
プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
処理を実行させることを特徴とするコンパイルプログラム。
【０１２４】
（付記６）コンピュータが、
プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
処理を実行することを特徴とするコンパイル方法。
【０１２５】
（付記７）コンピュータが、
プログラムを実行する際に、ループ処理の先頭から所定回先の繰り返しの直前までの第１ループ処理において、キャッシュメモリ内の第１領域を用いて、それぞれの繰り返しで配列のデータにアクセスするとともに、前記キャッシュメモリ内の第２領域を用いて、前記所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行い、
前記ループ処理の前記所定回先の繰り返しから最後までの第２ループ処理において、前記第２領域を用いて、それぞれの繰り返しで前記配列のデータにアクセスするとともに、前記所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行う、
処理を実行することを特徴とするキャッシュ制御方法。
【符号の説明】
【０１２６】
１０１  情報処理装置
１１０，４００  プログラム
２００  バス
２０１  ＣＰＵ
２０２  メモリ
２０３  Ｉ／Ｆ
２０４  ディスクドライブ
２０５  ディスク
２１０  ネットワーク
３０１  取得部
３０２  解析部
３０３  第１の生成部
３０４  最適化部
３０５  第２の生成部
３０６  決定部
３０７  出力部
【図１】
2018010540.tif 000003
【図２】
2018010540.tif 000004
【図３】
2018010540.tif 000005
【図４】
2018010540.tif 000006
【図５】
2018010540.tif 000007
【図６】
2018010540.tif 000008
【図７】
2018010540.tif 000009
【図８】
2018010540.tif 000010