[go: up one dir, main page]

JP6665720B2 - 情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法 - Google Patents

情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法 Download PDF

Info

Publication number
JP6665720B2
JP6665720B2 JP2016139830A JP2016139830A JP6665720B2 JP 6665720 B2 JP6665720 B2 JP 6665720B2 JP 2016139830 A JP2016139830 A JP 2016139830A JP 2016139830 A JP2016139830 A JP 2016139830A JP 6665720 B2 JP6665720 B2 JP 6665720B2
Authority
JP
Japan
Prior art keywords
loop
data
area
sector
array
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2016139830A
Other languages
English (en)
Other versions
JP2018010540A (ja
Inventor
優太 向井
優太 向井
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP2016139830A priority Critical patent/JP6665720B2/ja
Priority to US15/639,811 priority patent/US10353682B2/en
Publication of JP2018010540A publication Critical patent/JP2018010540A/ja
Application granted granted Critical
Publication of JP6665720B2 publication Critical patent/JP6665720B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
    • G06F8/451—Code distribution
    • G06F8/452—Loops
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0862—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with prefetch
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0875—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with dedicated cache, e.g. instruction or stack
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformation of program code
    • G06F8/41—Compilation
    • G06F8/44—Encoding
    • G06F8/443—Optimisation
    • G06F8/4441—Reducing the execution time required by the program code
    • G06F8/4442—Reducing the number of cache misses; Data prefetching
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/3004—Arrangements for executing specific machine instructions to perform operations on memory
    • G06F9/30047—Prefetch instructions; cache control instructions
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/3005—Arrangements for executing specific machine instructions to perform operations for flow control
    • G06F9/30065—Loop control instructions; iterative instructions, e.g. LOOP, REPEAT
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3802—Instruction prefetching
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3824—Operand accessing
    • G06F9/383—Operand prefetching
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/45—Caching of specific data in cache memory
    • G06F2212/452—Instruction code
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/60—Details of cache memory
    • G06F2212/6024—History based prefetching

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Devices For Executing Special Programs (AREA)

Description

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

Claims (6)

  1. プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
    前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
    制御部を有することを特徴とする情報処理装置。
  2. 前記制御部は、
    生成した前記中間言語コードに基づいて、前記プログラムの実行可能ファイルを生成する、ことを特徴とする請求項１に記載の情報処理装置。
  3. 前記制御部は、
    前記第１領域のサイズを変えながら、生成した前記実行可能ファイルを実行して、前記サイズに対応する前記第１領域についてのキャッシュミスの数を測定し、
    測定した前記キャッシュミスの数が、前記サイズをキャッシュラインで割った値以下となる最小のサイズを前記第１領域のサイズに決定し、
    決定した前記第１領域のサイズを示す情報を前記実行可能ファイルと対応付けて出力する、ことを特徴とする請求項２に記載の情報処理装置。
  4. コンピュータに、
    プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
    前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
    処理を実行させることを特徴とするコンパイルプログラム。
  5. コンピュータが、
    プログラムをコンパイルする際に、それぞれの繰り返しで配列のデータにアクセスするとともに所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行うループ処理を、先頭から前記所定回先の繰り返しの直前までの第１ループ処理と、前記所定回先の繰り返しから最後までの第２ループ処理とに分割し、
    前記第１ループ処理において、キャッシュメモリ内の第１領域を用いて前記配列のデータのアクセスを行うとともに、前記キャッシュメモリ内の第２領域を用いて前記配列のデータのプリフェッチを行い、前記第２ループ処理において、前記第２領域を用いて前記配列のデータのアクセスおよびプリフェッチを行う中間言語コードを生成する、
    処理を実行することを特徴とするコンパイル方法。
  6. コンピュータが、
    プログラムを実行する際に、ループ処理の先頭から所定回先の繰り返しの直前までの第１ループ処理において、キャッシュメモリ内の第１領域を用いて、それぞれの繰り返しで配列のデータにアクセスするとともに、前記キャッシュメモリ内の第２領域を用いて、前記所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行い、
    前記ループ処理の前記所定回先の繰り返しから最後までの第２ループ処理において、前記第２領域を用いて、それぞれの繰り返しで前記配列のデータにアクセスするとともに、前記所定回先の繰り返しでアクセスする前記配列のデータのプリフェッチを行う、
    処理を実行することを特徴とするキャッシュ制御方法。
JP2016139830A 2016-07-14 2016-07-14 情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法 Active JP6665720B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP2016139830A JP6665720B2 (ja) 2016-07-14 2016-07-14 情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法
US15/639,811 US10353682B2 (en) 2016-07-14 2017-06-30 Information processing device, storage medium, and method

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2016139830A JP6665720B2 (ja) 2016-07-14 2016-07-14 情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法

Publications (2)

Publication Number Publication Date
JP2018010540A JP2018010540A (ja) 2018-01-18
JP6665720B2 true JP6665720B2 (ja) 2020-03-13

Family

ID=60941013

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2016139830A Active JP6665720B2 (ja) 2016-07-14 2016-07-14 情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法

Country Status (2)

Country Link
US (1) US10353682B2 (ja)
JP (1) JP6665720B2 (ja)

Families Citing this family (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10409614B2 (en) 2017-04-24 2019-09-10 Intel Corporation Instructions having support for floating point and integer data types in the same register
US10474458B2 (en) 2017-04-28 2019-11-12 Intel Corporation Instructions and logic to perform floating-point and integer operations for machine learning
CN113424148A (zh) 2019-03-15 2021-09-21 英特尔公司 用于检测跨分片访问、提供多分片推理缩放和提供最佳页迁移的多分片存储器管理
WO2020190796A1 (en) 2019-03-15 2020-09-24 Intel Corporation Systems and methods for cache optimization
CN112905241B (zh) 2019-03-15 2024-03-29 英特尔公司 用于矩阵加速器架构的稀疏优化
US11934342B2 (en) 2019-03-15 2024-03-19 Intel Corporation Assistance for hardware prefetch in cache access
JP7230719B2 (ja) * 2019-07-19 2023-03-01 富士通株式会社 情報処理装置及び情報処理方法
US11861761B2 (en) 2019-11-15 2024-01-02 Intel Corporation Graphics processing unit processing and caching improvements
US11663746B2 (en) 2019-11-15 2023-05-30 Intel Corporation Systolic arithmetic on sparse data

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2003108386A (ja) * 2001-09-28 2003-04-11 Hitachi Ltd 間接参照データプリフェッチ方法
US20070083730A1 (en) * 2003-06-17 2007-04-12 Martin Vorbach Data processing device and method
US7657880B2 (en) * 2003-01-31 2010-02-02 Intel Corporation Safe store for speculative helper threads
JPWO2005078579A1 (ja) * 2004-02-12 2007-10-18 松下電器産業株式会社 プログラム変換装置およびプログラム変換方法
US7168070B2 (en) * 2004-05-25 2007-01-23 International Business Machines Corporation Aggregate bandwidth through management using insertion of reset instructions for cache-to-cache data transfer
US8706964B1 (en) * 2007-09-28 2014-04-22 The Mathworks, Inc. Automatic generation of cache-optimized code
US8239841B2 (en) * 2008-04-04 2012-08-07 International Business Machines Corporation Prefetching irregular data references for software controlled caches
JP5251689B2 (ja) 2009-04-02 2013-07-31 富士通株式会社 コンパイラプログラムおよびコンパイラ装置
US8893103B2 (en) * 2012-08-16 2014-11-18 Nec Laboratories America, Inc. Automatic asynchronous offload to many-core coprocessors
JP6248808B2 (ja) 2014-05-22 2017-12-20 富士通株式会社 情報処理装置、情報処理システム、情報処理装置の制御方法、及び、情報処理装置の制御プログラム

Also Published As

Publication number Publication date
US20180018153A1 (en) 2018-01-18
JP2018010540A (ja) 2018-01-18
US10353682B2 (en) 2019-07-16

Similar Documents

Publication Publication Date Title
JP6665720B2 (ja) 情報処理装置、コンパイルプログラム、コンパイル方法、およびキャッシュ制御方法
US9798528B2 (en) Software solution for cooperative memory-side and processor-side data prefetching
US8886887B2 (en) Uniform external and internal interfaces for delinquent memory operations to facilitate cache optimization
US6721943B2 (en) Compile-time memory coalescing for dynamic arrays
US6148439A (en) Nested loop data prefetching using inner loop splitting and next outer loop referencing
US20040093591A1 (en) Method and apparatus prefetching indexed array references
JP5966509B2 (ja) プログラム、コード生成方法および情報処理装置
CN101273332A (zh) 使用编译器的线程数据亲和性优化
US9483244B2 (en) Compiling method and compiling device
US20030088863A1 (en) Method and apparatus for selecting references for prefetching in an optimizing compiler
JP4177681B2 (ja) コンパイル方法、コンパイラ、およびコンパイル装置
US7257810B2 (en) Method and apparatus for inserting prefetch instructions in an optimizing compiler
Hong et al. Improving simd parallelism via dynamic binary translation
JP7060803B2 (ja) 情報処理装置、コンパイラプログラム及びコンパイル方法
US7313787B2 (en) Compiler and method for optimizing object codes for hierarchical memories
US20050086651A1 (en) Compiler apparatus and linker apparatus
JP2023045347A (ja) プログラムおよび情報処理方法
US9552197B2 (en) Computer-readable recording medium storing information processing program, information processing apparatus, and information processing method
US20220405110A1 (en) Non-transitory computer-readable recording medium and compilation method
JP6898556B2 (ja) 情報処理装置、コンパイル方法及びコンパイルプログラム
CN114041116A (zh) 数据移动任务优化的方法和装置
JP2014099108A (ja) 実行時間算出装置、実行時間算出方法、およびプログラム
Larrea et al. An in-depth evaluation of GCC’s OpenACC implementation on Cray systems
JPH05265770A (ja) 計算機言語処理方法
JP2019164704A (ja) コンパイラ

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20190409

TRDD Decision of grant or rejection written
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20200115

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20200121

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20200203

R150 Certificate of patent or registration of utility model

Ref document number: 6665720

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150