(57)【特許請求の範囲】
【請求項１】
プログラミング言語で記述されたソースプログラムをコンパイルするコンパイラにおいて，ソースプログラムに含まれる多重ループに対するブロッキングによる最適化の処理をコンピュータに実行させるためのプログラムであって，
前記コンピュータに，
前記ソースプログラムに含まれる多重ループから，最内ループにのみ実行文を有する構造のループを，ブロッキング対象ループとして抽出する手順と，
前記ブロッキング対象ループ内に存在する配列を抽出する手順と，
前記抽出された配列の中に，添え字として出現する制御変数の順序が，前記ブロッキング対象ループの最内ループから最外ループに向かって出現する制御変数の順序と異なる配列が存在する場合に，前記ブロッキング対象ループに対するブロッキングが有効であると判定する手順と，
ブロッキングが有効であると判定された前記ブロッキング対象ループについて，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で配列が使用するメモリサイズを算出する計算式を，前記配列ごとに生成する手順と，
前記配列ごとに生成された計算式から，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で前記ブロッキング対象ループ内の全配列が使用するメモリサイズを計算する計算式を生成する手順と，
前記全配列が使用するメモリサイズを計算する計算式を用いて，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で，配列に対するアクセスによってキャッシュミスが発生しない分割ブロック長を自動計算する手順と，
前記自動計算された分割ブロック長を用いて，前記ブロッキング対象ループに対するブロッキングによる最適化を行う手順とを
実行させるための最適化処理プログラム。
【請求項２】
前記配列ごとに計算式を生成する手順では，ブロッキングが有効であると判定された前記ブロッキング対象ループについて，ブロッキングを実行しない旨が指示されたループを除いた前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で配列が使用するメモリサイズを算出する計算式を，前記配列ごとに生成し，
前記ブロッキングによる最適化を行う手順では，前記自動計算された分割ブロック長を用いて，前記ブロッキングを実行しない旨が指示されたループを除外して，前記ブロッキング対象ループに対するブロッキングによる最適化を行う
ことを特徴とする請求項１に記載された最適化処理プログラム。
【請求項３】
前記配列ごとに計算式を生成する手順では，ブロッキングが有効であると判定された前記ブロッキング対象ループについて，固定の分割ブロック長が指示されたループを含む前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で配列が使用するメモリサイズを算出する計算式を，前記配列ごとに生成し，
前記ブロッキングによる最適化を行う手順では，前記ブロッキング対象ループに含まれる前記固定の分割ブロック長が指示されたループに対しては，前記指示された固定のブロック長を用いてブロッキングによる最適化を行い，前記ブロッキング対象ループに含まれる前記固定の分割ブロック長が指示されていないループに対しては，前記自動計算された分割ブロック長を用いてブロッキングによる最適化を行う
ことを特徴とする請求項１または請求項２に記載された最適化処理プログラム。
【請求項４】
プログラミング言語で記述されたソースプログラムをコンパイルするコンパイラにおいて，ソースプログラムに含まれる多重ループに対するブロッキングによる最適化の処理を実行する最適化処理装置であって，
前記ソースプログラムに含まれる多重ループから，最内ループにのみ実行文を有する構造のループを，ブロッキング対象ループとして抽出する処理対象ループ解析部と，
前記ブロッキング対象ループ内に存在する配列を抽出する配列解析部と，
前記抽出された配列の中に，添え字として出現する制御変数の順序が，前記ブロッキング対象ループの最内ループから最外ループに向かって出現する制御変数の順序と異なる配列が存在する場合に，前記ブロッキング対象ループに対するブロッキングが有効であると判定するアクセスパターン解析部と，
ブロッキングが有効であると判定された前記ブロッキング対象ループについて，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で配列が使用するメモリサイズを算出する計算式を，前記配列ごとに生成し，その配列ごとに生成された計算式から，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で前記ブロッキング対象ループ内の全配列が使用するメモリサイズを計算する計算式を生成するメモリサイズ計算式生成部と，
前記全配列が使用するメモリサイズを計算する計算式を用いて，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で，配列に対するアクセスによってキャッシュミスが発生しない分割ブロック長を自動計算する分割ブロック長計算部と，
前記自動計算された分割ブロック長を用いて，前記ブロッキング対象ループに対するブロッキングによる最適化を行う最適化実行部とを備える
ことを特徴とする最適化処理装置。
【請求項５】
プログラミング言語で記述されたソースプログラムをコンパイルするコンパイラにおいて，ソースプログラムに含まれる多重ループに対するブロッキングによる最適化の処理を，コンピュータが実行する最適化処理方法であって，
前記コンピュータが，
前記ソースプログラムに含まれる多重ループから，最内ループにのみ実行文を有する構造のループを，ブロッキング対象ループとして抽出する過程と，
前記ブロッキング対象ループ内に存在する配列を抽出する過程と，
前記抽出された配列の中に，添え字として出現する制御変数の順序が前記ブロッキング対象ループの最内ループから最外ループに向かって出現する制御変数の順序と異なる配列が存在する場合に，前記ブロッキング対象ループに対するブロッキングが有効であると判定する過程と，
ブロッキングが有効であると判定された前記ブロッキング対象ループについて，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で配列が使用するメモリサイズを算出する計算式を，前記配列ごとに生成する過程と，
前記配列ごとに生成された計算式から，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で前記ブロッキング対象ループ内の全配列が使用するメモリサイズを計算する計算式を生成する過程と，
前記全配列が使用するメモリサイズを計算する計算式を用いて，前記ブロッキング対象ループに対するブロッキングによって最適化される範囲で，配列に対するアクセスによってキャッシュミスが発生しない分割ブロック長を自動計算する過程と，
前記自動計算された分割ブロック長を用いて，前記ブロッキング対象ループに対するブロッキングによる最適化を行う過程とを実行する
ことを特徴とする最適化処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，プログラミング言語で記述されたソースプログラムに含まれるループの最適化を行う最適化処理プログラム，最適化処理装置および最適化処理方法に関するものである。
【背景技術】
【０００２】
コンパイラには，キャッシュメモリをソフトウェアから有効活用するための技術として，ブロッキングと呼ばれる最適化の技術が用意されている。ブロッキングは，ソースプログラム中に存在する多重ループの処理構造に対して，その最内ループ内で使用する配列に対するメモリアクセスがキャッシュメモリのサイズに収まるように，多重ループの回転数を分割する技術である。コンパイラがソースプログラムに対してブロッキングによる最適化を実行することにより，配列のデータが常にキャッシュメモリ上に保持されるようになり，キャッシュヒット率が向上する。
【０００３】
なお，最適化の対象となる多重ループについて，その最内ループと最内の１つ外側のループに関してのみ最適化を行うブロッキングの技術が知られている。また，３次元以上の配列を含む多重ループについて，その最内ループに関してのみ最適化を行うブロッキングの技術が知られている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平５−２６５７７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述の従来のブロッキングによる多重ループの最適化の技術には，３重以上のループに対してブロッキングを適用することができない，３次元以上の配列を含む多重ループに対してブロッキングを適用することができないという問題があった。
【０００６】
近年，ハードウェア性能の向上に合わせて，より高度で複雑な科学演算が行われる傾向がある。このようなニーズに答えるためには，上記の従来技術の問題を解決する必要がある。
【０００７】
本発明は，上記の問題の解決を図り，３重ループ以上のループに対して，また３次元以上の配列を含む多重ループに対して，広範囲にブロッキングによる最適化の実行を可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
開示するプログラムは，プログラミング言語で記述されたソースプログラムをコンパイルするコンパイラにおいて，ソースプログラムに含まれる多重ループに対するブロッキングによる最適化の処理を行うコンピュータを，次のように機能させる。
【０００９】
すなわち，前記プログラムは，前記プログラムがインストールされて実行されるコンピュータに，ソースプログラムに含まれる多重ループから最内ループにのみ実行文を有する構造のループをブロッキング対象ループとして抽出する手順と，ブロッキング対象ループ内に存在する配列を抽出する手順と，抽出された配列の中に添え字として出現する制御変数の順序がブロッキング対象ループの最内ループから最外ループに向かって出現する制御変数の順序と異なる配列が存在する場合に，ブロッキング対象ループに対するブロッキングが有効であると判定する手順と，ブロッキングが有効であると判定されたブロッキング対象ループについて，ブロッキング対象ループに対するブロッキングによって最適化される範囲で配列が使用するメモリサイズを算出する計算式を配列ごとに生成する手順と，配列ごとに生成された計算式からブロッキング対象ループに対するブロッキングによって最適化される範囲でブロッキング対象ループ内の全配列が使用するメモリサイズを計算する計算式を生成する手順と，全配列が使用するメモリサイズを計算する計算式を用いて，ブロッキング対象ループに対するブロッキングによって最適化される範囲で配列に対するアクセスによってキャッシュミスが発生しない分割ブロック長を自動計算する手順と，自動計算された分割ブロック長を用いてブロッキング対象ループに対するブロッキングによる最適化を行う手順とを実行させる。
【発明の効果】
【００１０】
上記の技術によって，３重以上のループに対して，最内ループ内に含まれる配列の次元数に影響なく，広範囲にブロッキングによる最適化を実行することが可能となる。これにより，従来はブロッキングによる最適化の実行が不可能であったループに対してもブロッキングを適用して，キャッシュメモリのヒット率が改善することで，最適化されるプログラムの実行性能が向上する。
【図面の簡単な説明】
【００１１】
【図１】３重ループに対する従来のブロッキングの例を説明する図である。
【図２】メモリアクセスの例を示す図である。
【図３】３重ループのすべてに対してブロッキングを行った場合のブロッキング後の最適化対象ループの例を示す図である。
【図４】メモリアクセスの例を示す図である。
【図５】３次元の配列を含む多重ループに対する従来のブロッキングの例を説明する図である。
【図６】３次元の配列を含む多重ループに対して，最内ループ以外のループもブロッキングを行った場合のブロッキング後の最適化対象ループの例を示す図である。
【図７】本実施の形態によるコンパイラの機能構成例を示す図である。
【図８】本実施の形態によるコンピュータのハードウェア構成例を示す図である。
【図９】本実施の形態によるソース解析部の機能構成例を示す図である。
【図１０】本実施の形態の最適化処理部によるブロッキング最適化処理フローチャートである。
【図１１】本実施の形態による最適化の対象となるループとブロッキングによる最適化実行後のループとの例を示す図である。
【図１２】本実施の形態によるループデータのデータ構造の例を示す図である。
【図１３】本実施の形態によるタイトなループを説明する図である。
【図１４】本実施の形態の処理対象ループ解析部による処理対象ループ解析処理フローチャートである。
【図１５】本実施の形態による配列データの管理を説明する図である。
【図１６】本実施の形態の配列解析部による配列解析処理フローチャートである。
【図１７】本実施の形態によるアクセスパターンを説明する図である。
【図１８】本実施の形態によるループデータにおける有効フラグを設定した例を示す図である。
【図１９】本実施の形態のアクセスパターン解析部によるアクセスパターン解析処理フローチャートである。
【図２０】本実施の形態のアクセスパターン解析部による添え字の連鎖作成処理フローチャートである。
【図２１】本実施の形態による配列別メモリ計算式の生成を説明する図である。
【図２２】本実施の形態による配列別メモリ計算式からのメモリサイズ計算式の生成を説明する図である。
【図２３】本実施の形態のメモリサイズ計算式生成部によるメモリサイズ計算式生成処理フローチャートである。
【図２４】本実施の形態のメモリサイズ計算式生成部による配列別メモリ計算データ生成処理フローチャートである。
【図２５】本実施の形態によるメモリサイズ計算式を用いて分割ブロック長を自動計算する例を説明する図である。
【図２６】本実施の形態の分割ブロック長計算部による分割ブロック長計算処理フローチャートである。
【図２７】本実施の形態によるブロッキング指示部によるブロッキング指示処理フローチャートである。
【図２８】本実施の形態のブロッキングによる最適化を３重以上のループに対して実行した例である。
【図２９】本実施の形態のブロッキングによる最適化を３次元以上の配列を含む多重ループに対して実行した例である。
【図３０】本実施の形態のブロッキングによる最適化をブロッキング抑止の最適化指示行を含む多重ループに対して実行した例である。
【図３１】本実施の形態のブロッキングによる最適化を固定の分割ブロック長の最適化指示行を含む多重ループに対して実行した例である。
【発明を実施するための形態】
【００１２】
以下，本実施の形態について，図を用いて説明する。
【００１３】
まず，本実施の形態によるブロッキングの技術を説明する前に，従来のブロッキングの技術について，簡単に説明する。
【００１４】
図１は，３重ループに対する従来のブロッキングの例を説明する図である。
【００１５】
図１（Ａ）は，最適化対象ループの例を示す。図１（Ａ）に示す最適化対象ループは，ループＩ，ループＪ，ループＫの３重ループである。図１（Ａ）に示す最適化対象ループでは，最内ループ内にのみ，２次元の配列を用いた演算の実行文が含まれている。
【００１６】
なお，本実施の形態では，制御変数をループの名称に用いるものとする。具体的には，本実施の形態では，制御変数ＩのループをループＩと呼ぶものとする。
【００１７】
図１（Ｂ）は，図１（Ａ）に示す最適化対象ループに対して，インデックス交換を行った結果を示す。インデックスとは，制御変数のことである。インデックス交換は，配列へのアクセスがメモリ上の連続領域へのアクセスとなるように，内側のループと外側のループとを入れ換える処理である。ブロッキングは連続領域へのメモリアクセスに対して効果が高いため，インデックス交換により連続領域へのメモリアクセスとなる場合は，事前にインデックス交換を行う必要がある。インデックス交換の詳細については，特許文献１の段落［００３４］〜［００４３］，図３に記載されている。
【００１８】
図１（Ｃ）は，図１（Ｂ）に示すインデックス交換後の最適化対象ループに対して，従来のブロッキングを行った結果を示す。従来の技術では，最内ループとその１つ外側のループとに対してのみ，すなわち図１に示す例ではループＩとループＪとに対してのみ，ブロッキングが行われる。図１（Ｃ）に示すブロッキング後の最適化対象ループにおいて，ループの分割単位を示す分割ブロック長ｂｌｏｃｋには，コンパイラのブロッキング機能によって，適切な値が求められる。
【００１９】
図２は，メモリアクセスの例を示す図である。
【００２０】
図２に示すメモリアクセスの例は，図１（Ｃ）に示すブロッキング後の最適化対象ループにおけるメモリアクセスの例である。図２において，太線の枠は，各配列のデータが記憶されたメモリ領域を示し，細線の枠は，一辺が分割ブロック長ｂｌｏｃｋである領域を示している。図２において，網掛けの領域は，図１（Ｃ）に示すブロッキング後の最適化対象ループにおいて，制御変数ＪＪ，ＩＩを固定して，ループＩ，ループＪ，ループＫとが回転したときの，演算の実行文に含まれる配列ごとのアクセス領域を示す。
【００２１】
図２に示すように，ブロッキングが行われたループの制御変数ＩとＪとを添え字とする配列Ａについては，メモリアクセスが局所化されているため，キャッシュメモリに効率的にデータをのせることができる。しかし，ブロッキングが行われなかったループの制御変数Ｋを添え字に含む配列Ｂ，配列Ｃについては，メモリアクセスが局所化されないため，キャッシュメモリに効率的にデータをのせることができない。
【００２２】
このように，従来のブロッキングの技術では，３重以上のループを対象としたブロッキングができないため，キャッシュメモリに効率的にデータをのせることができる配列の範囲が，狭い範囲に限られていた。
【００２３】
図３は，３重ループのすべてに対してブロッキングを行った場合のブロッキング後の最適化対象ループの例を示す図である。
【００２４】
図３に示すブロッキング後の最適化対象ループの例は，図１（Ｂ）に示すインデックス交換後の最適化対象ループにおいて，３重ループのすべてに対してブロッキングを行ったと仮定した場合の結果の例である。
【００２５】
例えば，実行文に含まれる配列の添え字において，各ループの制御変数の登場回数があまり変わらないような場合には，すべてのループに対してブロッキングを行うことにより，よりよいメモリ効率が得られる場合がある。
【００２６】
図４は，メモリアクセスの例を示す図である。
【００２７】
図４に示すメモリアクセスの例は，図３に示すブロッキング後の最適化対象ループにおけるメモリアクセスの例である。すなわち，図４に示すメモリアクセスの例は，図１（Ｂ）に示すインデックス交換後の最適化対象ループにおいて，３重ループのすべてに対してブロッキングを行ったと仮定した場合のブロッキング後の最適化対象ループにおけるメモリアクセスの例である。
【００２８】
図４において，太線の枠は，各配列のデータが記憶されたメモリ領域を示し，細線の枠は，一辺が分割ブロック長ｂｌｏｃｋである領域を示している。図２において，網掛けの領域は，図３に示すブロッキング後の最適化対象ループにおいて，制御変数ＪＪ，ＩＩ，ＫＫとを固定して，ループＩ，ループＪ，ループＫとが回転したときの，演算の実行文に含まれる配列ごとのアクセス領域を示す。
【００２９】
図４に示すように，３重ループのすべてに対してブロッキングを行ったと仮定すると，配列Ａ，配列Ｂ，配列Ｃのすべてについて，メモリアクセスが局所化されるため，すべての配列のデータを，キャッシュメモリに効率的にのせることができる。
【００３０】
図３に示すような３重以上のループを対象としたブロッキングを行うことができれば，従来のブロッキングの技術と比較して，よりメモリ効率が高いループの最適化を行うことができるようになる。
【００３１】
図５は，３次元の配列を含む多重ループに対する従来のブロッキングの例を説明する図である。
【００３２】
図５（Ａ）は，最適化対象ループの例を示す。図５（Ａ）に示す最適化対象ループは，ループＩ，ループＪ，ループＫの３重ループである。図５（Ａ）に示す最適化対象ループでは，最内ループ内にのみ，３次元の配列を含む演算の実行文が含まれている。
【００３３】
図５（Ｂ）は，図５（Ａ）に示す最適化対象ループに対して，従来のブロッキングを行った結果を示す。従来の技術では，最内ループ内で３次元以上の配列が使用されている場合に，翻訳コストの問題から，最内ループのみ，すなわち図５に示す例ではループＩのみをブロッキングの対象とする。しかし，実際には，制御変数Ｊを更新するループＪに対してもブロッキングは有効である。
【００３４】
このように，従来のブロッキングの技術では，３次元の配列を含む多重ループに対しては，最内ループを対象としたブロッキングしかできないため，あまり効果的なループの最適化はできなかった。
【００３５】
図６は，３次元の配列を含む多重ループに対して，最内ループ以外のループもブロッキングを行った場合のブロッキング後の最適化対象ループの例を示す図である。
【００３６】
図６に示すブロッキング後の最適化対象ループの例は，図５（Ａ）に示す３次元の配列を含む最適化対象ループにおいて，ループＩとループＪとに対してブロッキングを行ったと仮定した場合の結果の例である。
【００３７】
図６に示すように，３次元以上の配列を含む多重ループにおいて，最内ループ以外のループもブロッキングの対象とすることで，よりメモリ効率が高いループの最適化を行うことができるようになる。
【００３８】
近年，ハードウェア性能の向上に合わせて，より高度で複雑な科学演算が行われる傾向がある。このようなニーズに応えるためには，図３や図６に示すように，３重以上の多重ループや３次元以上の配列を含む多重ループに対しても，ブロッキングの範囲を広げることにより，プログラムの実行性能を向上させる必要がある。
【００３９】
以下では，３重以上の多重ループや３次元以上の配列を含む多重ループに対するブロッキングの問題の解決を図った，本実施の形態のブロッキングの技術について説明する。
【００４０】
図７は，本実施の形態によるコンパイラの機能構成例を示す図である。
【００４１】
図７において，実線の矢印は主に制御の流れを示し，破線の矢印は主にデータの流れを示す。
【００４２】
コンピュータ１は，コンパイラ１０，記憶部２０，リンカ３０，オペレーティングシステム４０を備える。オペレーティングシステム４０は，アプリケーションが共通して利用する基本的な機能を提供する。
【００４３】
記憶部２０は，ソースプログラム２１，オブジェクトファイル２２，実行ファイル２３などを記憶する，コンピュータ１がアクセス可能な記憶装置である。ソースプログラム２１は，Ｆｏｒｔｒａｎなどのプログラミング言語で記述されたアプリケーションのプログラムである。オブジェクトファイル２２は，コンパイラ１０によってソースプログラム２１から生成された，アプリケーションのオブジェクトコードのファイルである。実行ファイル２３は，リンカ３０によってオブジェクトファイル２２とライブラリとがリンクされた，アプリケーションの実行形式プログラムのファイルである。
【００４４】
コンパイラ１０は，ソースプログラム２１をコンパイルし，オブジェクトファイルを生成する。リンカ３０は，オブジェクトファイル２２とライブラリとをリンクし，実行ファイル２３を生成する。
【００４５】
コンパイラ１０は，ソースプログラム入力部１１，入出力制御部１２，中間言語生成部１３，中間言語記憶部１４，最適化処理部１５，コード生成部１８，オブジェクトファイル出力部１９を備える。
【００４６】
ソースプログラム入力部１１は，コンパイルが指定されたソースプログラム２１をオープンする。入出力制御部１２は，オプション，ファイルの種別に応じて必要な処理を選択する。
【００４７】
中間言語生成部１３は，ソースプログラム２１を，最適化処理部１５による最適化の処理で利用する中間コードに変換し，中間言語記憶部１４に格納する。中間言語記憶部１４は，中間言語生成部１３によりソースプログラム２１から変換された中間コードを記憶する，コンピュータ１がアクセス可能な記憶装置である。高級言語で記述されたソースプログラム２１に対してそのまま最適化の処理を施すことは，非常に困難である。そのため，コンパイラ１０は，最適化の処理が施しやすいデータ構造体でソースプログラム２１を表現する中間コードに変換してから，その中間コードに対して最適化の処理を施す。
【００４８】
最適化処理部１５は，中間言語記憶部１４に記憶された中間コードに対して，最適化の処理を行う。最適化処理部１５は，ソース解析部１６，最適化実行部１７を備える。ソース解析部１６は，中間言語記憶部１４に記憶された中間コードを解析して，有効な最適化を選択し，最適化実行部１７に指示する。最適化実行部１７は，指示された最適化を，中間言語記憶部１４に記憶された中間コードに対して適用する。
【００４９】
コード生成部１８は，最適化された中間コードから，アセンブラコードを生成する。オブジェクトファイル出力部１９は，アセンブラコードからオブジェクトファイル２２を生成する。
【００５０】
図８は，本実施の形態によるコンピュータのハードウェア構成例を示す図である。
【００５１】
コンピュータ１は，ＣＰＵ（Central Processing Unit ）２，ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）などのメモリ３，ＨＤＤ（Hard Disk Drive ）４などのハードウェアを備える。メモリ３の一部は，ＣＰＵ２が高速にアクセス可能なキャッシュメモリである。また，コンピュータ１には，キーボードやマウスなどの入力装置５，ディスプレイなどの表示装置６が接続されている。
【００５２】
図７に示すコンピュータ１が備えるコンパイラ１０，記憶部２０，リンカ３０，オペレーティングシステム４０等が提供する機能は，図８に示すコンピュータ１のハードウェアとソフトウェアプログラムとによって実現される。
【００５３】
図９は，本実施の形態によるソース解析部の機能構成例を示す図である。
【００５４】
本実施の形態では，ソース解析部１６は，多重ループを最適化するブロッキングに関する処理として，アクセスパターンの解析，メモリサイズ計算式の作成，分割ブロック長の算出などの処理を実施する。最適化処理部１５は，ソース解析部１６により得られた情報を最適化実行部１７に伝播することで，ソースプログラム２１に含まれるループの最適化を実行し，コンパイラ１０により生成されるプログラムの高速化を図る。
【００５５】
ソース解析部１６は，多重ループを最適化するブロッキングに関する処理として，中間言語記憶部１４に記憶された中間コードを解析して，ブロッキングによるループ分割の単位である分割ブロック長を自動計算する。中間言語記憶部１４は，ソースプログラム２１に含まれるループに関する中間コードのデータとして，ループデータを記憶する。図９に示すループデータ記憶部２００は，中間言語記憶部１４におけるループデータの記憶領域である。
【００５６】
なお，本実施の形態では，最適化処理部１５によるブロッキングに関する処理の前に，ループの内外を交換するインデックス変換や，並列するループを含む多重ループを直列の入れ子構造に変形するループ分割等の最適化が，すでに実行されているものとする。
【００５７】
ソース解析部１６は，ブロッキングに関する機能部として，処理対象ループ解析部１００，配列解析部１１０，アクセスパターン解析部１２０，メモリサイズ計算式生成部１３０，分割ブロック長計算部１４０，ブロッキング指示部１５０等の各機能部を有する。また，ソース解析部１６は，配列情報記憶部１６０，配列別メモリ計算情報記憶部１７０，メモリサイズ計算情報記憶部１８０等の各記憶部を有する。ソース解析部１６が有する各機能部，各記憶部は，コンピュータ１が備えるＣＰＵ２，メモリ３，ＨＤＤ４等のハードウェアと，ソフトウェアプログラムとによって実現される。
【００５８】
処理対象ループ解析部１００は，最適化の対象となるループからタイトな構造を持つループを抽出する。以下では，中間コードで表現されたソースプログラム２１に含まれる最適化の対象となるループを，最適化対象ループと呼ぶものとする。また，処理対象ループ解析部１００によって，最適化対象ループから抽出されるタイトな構造を持つループを，ブロッキング対象ループと呼ぶものとする。
【００５９】
配列解析部１１０は，ブロッキング対象ループの最内ループ内を解析し，ブロッキング対象ループ内に存在する配列を抽出する。配列解析部１１０は，ブロッキング対象ループ内から抽出された配列の情報を配列情報記憶部１６０に記憶する。配列情報記憶部１６０は，ブロッキング対象ループ内から抽出された配列の情報を記憶する，コンピュータがアクセス可能な記憶装置である。
【００６０】
アクセスパターン解析部１２０は，ブロッキング対象ループにおいて最内ループから最外ループに向かって出現する制御変数の順序と，ブロッキング対象ループ内から抽出された配列の添え字に出現する制御変数の順序との関係を解析する。アクセスパターン解析部１２０は，添え字に出現する制御変数の順序が，最内ループから最外ループに向かって出現する制御変数の順序とは異なる配列が存在する場合に，ブロッキング対象ループに対するブロッキングによる最適化が有効であると判定する。
【００６１】
メモリサイズ計算式生成部１３０は，ブロッキング対象ループ内の配列ごとに，ブロッキング対象ループに対するブロッキングによって最適化される範囲で，配列が使用するメモリサイズを算出する計算式を生成する。以下では，ブロッキングによって最適化される範囲で配列が使用するメモリサイズを算出する計算式を，配列別メモリ計算式と呼ぶものとする。メモリサイズ計算式生成部１３０は，配列別メモリ計算式の情報を配列別メモリ計算情報記憶部１７０に記憶する。配列別メモリ計算情報記憶部１７０は，配列別メモリ計算式の情報を記憶する，コンピュータがアクセス可能な記憶装置である。
【００６２】
また，メモリサイズ計算式生成部１３０は，配列別メモリ計算式から，ブロッキング対象ループに対するブロッキングによって最適化される範囲で，ブロッキング対象ループ内の全配列が使用するメモリサイズを算出する計算式を生成する。以下では，ブロッキングによって最適化される範囲でブロッキング対象ループ内の全配列が使用するメモリサイズを算出する計算式を，メモリサイズ計算式と呼ぶものとする。メモリサイズ計算式生成部１３０は，メモリサイズ計算式の情報をメモリサイズ計算情報記憶部１８０に記憶する。メモリサイズ計算情報記憶部１８０は，メモリサイズ計算式の情報を記憶する，コンピュータがアクセス可能な記憶装置である。
【００６３】
分割ブロック長計算部１４０は，メモリサイズ計算式を用いて，ブロッキング対象ループに対するブロッキングによって最適化される範囲で，配列に対するアクセスによってキャッシュミスが発生しない分割ブロック長を自動計算する。
【００６４】
ブロッキング指示部１５０は，分割ブロック長計算部１４０によって得られた分割ブロック長を用いた，ブロッキング対象ループに対するブロッキングによる最適化の指示を行う。
【００６５】
最適化実行部１７は，ソース解析部１６により求められた分割ブロック長を用いて，ブロッキング対象ループに対するブロッキングによる最適化を実行する。より具体的には，最適化実行部１７は，ソース解析部１６により求められた分割ブロック長を用いて分割数を指示するループをもとのブロッキング対象ループの外に生成して，もとのブロッキング対象ループを変形する。
【００６６】
図１０は，本実施の形態の最適化処理部によるブロッキング最適化処理フローチャートである。
【００６７】
最適化処理部１５のソース解析部１６において，処理対象ループ解析部１００は，処理対象ループ解析処理を行う（ステップＳ１）。処理対象ループ解析処理は，最適化の対象となるループからタイトな構造を持つループを抽出する処理である。処理対象ループ解析処理の詳細については，後述する。
【００６８】
配列解析部１１０は，配列解析処理を行う（ステップＳ２）。配列解析処理は，ブロッキング対象ループ内に存在する配列を抽出する処理である。配列解析処理の詳細については，後述する。
【００６９】
アクセスパターン解析部１２０は，アクセスパターン解析処理を行う（ステップＳ３）。アクセスパターン解析処理は，ブロッキング対象ループ内のループの制御変数の出現順と，ブロッキング対象ループ内の配列の制御変数の出現順との関係から，ブロッキング対象ループに対するブロッキングによる最適化の有効／無効を判定する処理である。アクセスパターン解析処理の詳細については，後述する。
【００７０】
メモリサイズ計算式生成部１３０は，メモリサイズ計算式生成処理を行う（ステップＳ４）。メモリサイズ計算式生成処理は，ブロッキング対象ループに対するブロッキング対象ループに対するブロッキングによって最適化される範囲で，ブロッキング対象ループ内の全配列が使用するメモリサイズを算出する計算式を生成する処理である。メモリサイズ計算式生成処理の詳細については，後述する。
【００７１】
分割ブロック長計算部１４０は，分割ブロック長計算処理を行う（ステップＳ５）。分割ブロック長計算処理は，メモリサイズ計算式を用いて，ブロッキング対象ループに対するブロッキングによって最適化される範囲のループの処理で，配列に対するアクセスによってキャッシュミスが発生しない分割ブロック長を自動計算する処理である。分割ブロック長計算処理の詳細については，後述する。
【００７２】
ブロッキング指示部１５０は，ブロッキング指示処理を行う（ステップＳ６）。ブロッキング指示処理は，求めた分割ブロック長を用いた，ブロッキング対象ループに対するブロッキングによる最適化の指示を行う処理である。ブロッキング指示処理の詳細については，後述する。
【００７３】
最適化処理部１５の最適化実行部１７は，ソース解析部１６により得られた分割ブロック長を用いた，ブロッキング対象ループに対するブロッキングによる最適化を実行する（ステップＳ７）。
【００７４】
以下では，本実施の形態によるソース解析部１６が備えるブロッキングに関する各機能部の処理について，具体的な例を用いて説明する。
【００７５】
図１１は，本実施の形態による最適化の対象となるループとブロッキングによる最適化実行後のループとの例を示す図である。
【００７６】
図１１（Ａ）は，ソースプログラム２１における最適化の対象となるループの例を示す。以下では，最適化の対象となるループを，最適化対象ループと呼ぶものとする。図１１（Ａ）に示す最適化対象ループは，最内ループ内に３次元の配列を持つ，３重の多重ループである。
【００７７】
図１１（Ｂ）は，図１１（Ａ）に示す最適化対象ループに対して本実施の形態のブロッキングによる最適化を実行した場合の，目標となる最適化実行後のループの例を示す。図１１（Ｂ）に示す最適化実行後のループは，図（Ａ）に示す最適化対象ループのループＩ，ループＪ，ループＫのすべてのループについて，分割ブロック長ｂｌｏｃｋを用いたブロッキングによる最適化が実行された状態となっている。
【００７８】
図１１（Ｂ）に示すように，最適化実行後のループでは，分割ブロック長ｂｌｏｃｋを用いて分割数を指示するループＩＩ，ループＪＪ，ループＫＫがもとのループＩ，ループＪ，ループＫの外に生成され，もとのループＩ，ループＪ，ループＫが変形されている。図１１（Ｂ）における最適化実行後のループにおいて，内側のループＩ，ループＪ，ループＫからなる多重ループが，ブロッキングによって最適化される範囲のループとなる。本実施の形態によるソース解析部１６では，ブロッキングによって最適化される範囲のループ内の処理では，配列に対するアクセスによってキャッシュミスが発生しないような分割ブロック長ｂｌｏｃｋを，自動計算する。
【００７９】
以下では，本実施の形態によるソース解析部１６によって，図１１（Ａ）に示す最適化対象ループに対するブロッキングによる最適化で用いる分割ブロック長ｂｌｏｃｋを，自動的に計算する例を説明する。
【００８０】
なお，図１１に示すループのプログラムは，ソースプログラム２１の形式で表現しているが，実際の最適化処理部１５では，中間コードに変換されたループのプログラムに対して処理が行われる。
【００８１】
図１２は，本実施の形態によるループデータのデータ構造の例を示す図である。
【００８２】
図１２に示すループデータ２１０は，ソースプログラム２１に含まれるループが中間コードに変換されたデータテーブルの例である。図１２に示すループデータ２１０ｋは，図１１（Ａ）に示す最適化対象ループのループＫについてのループデータ２１０である。図１２に示すループデータ２１０ｊは，図１１（Ａ）に示す最適化対象ループのループＪについてのループデータ２１０である。図１２に示すループデータ２１０ｉは，図１１（Ａ）に示す最適化対象ループのループＩについてのループデータ２１０である。
【００８３】
図１２に示すループデータ２１０は，ループ名，ｐｒｅｖ（previous），ｎｅｘｔ，配列データ，ブロッキングフラグ，分割ブロック長，有効フラグ等の情報を有する。なお，実際のループデータ２１０は，ループに関する膨大な量の情報を有するデータである。図１２には，ループに関する膨大な量の情報を有するループデータ２１０の一部のみが記載されている。
【００８４】
図１２に示すループデータ２１０におけるループ名は，ループで値が更新される制御変数の名前を示す。
【００８５】
図１２に示すループデータ２１０におけるｐｒｅｖは，外側のループのループデータ２１０に対するポインタを示す。図１２において，例えばループデータ２１０ｊのｐｒｅｖにおける“＊Ｋ”は，ループＪの外側のループであるループＫのループデータ２１０ｋに対するポインタを表している。なお，図１２において，外側にループを持たないループＫのループデータ２１０ｋのｐｒｅｖは，“ＮＵＬＬ”である。
【００８６】
図１２に示すループデータ２１０におけるｎｅｘｔは，内側のループのループデータ２１０に対するポインタを示す。例えば，ループデータ２１０ｊのｎｅｘｔにおける“＊Ｉ”は，ループＪの内側のループであるループＩのループデータ２１０ｉに対するポインタを表している。なお，図１２において，内側にループを持たないループＩのループデータ２１０ｉのｎｅｘｔは，“ＮＵＬＬ”である。
【００８７】
図１２に示すループデータ２１０における配列データは，最内ループ内に存在する配列に関する情報である配列データに対するポインタを示す。ループデータ２１０の配列データのデフォルトは，“ＮＵＬＬ”である。ループデータ２１０における配列データは，後述の配列解析部１１０の処理によって設定される。
【００８８】
図１２に示すループデータ２１０におけるブロッキングフラグは，ブロッキング実行可否の指示の有無を示す。本実施の形態では，ループごとに，外部的にブロッキングによる最適化の有無を指示できるケースも想定している。本実施の形態では，特に指示のないループについては，ループデータ２１０のブロッキングフラグに“ＴＲＵＥ”が設定される。最適化指示行などによりブロッキングが抑止されたループについては，ループデータ２１０のブロッキングフラグに“ＦＡＬＳＥ”が設定される。
【００８９】
図１２に示すループデータ２１０における分割ブロック長は，ブロッキングで用いる分割ブロック長を示す。本実施の形態では，ループごとに，外部的に固定の分割ブロック長を指示できるケースも想定している。本実施の形態では，特に固定の分割ブロック長の指示がないループについては，ループデータ２１０の分割ブロック長に，ブロッキングで用いる分割ブロック長を自動計算することを示す“０”が設定される。最適化指示行などにより固定の分割ブロック長が指示されたループについては，ループデータ２１０の分割ブロック長に指示された値が設定される。なお，ループデータ２１０のブロッキングフラグが“ＦＡＬＳＥ”であるループについては，ループデータ２１０の分割ブロック長に，ブロッキングを実行しない旨を示す“−１”が設定される。
【００９０】
図１２に示すループデータ２１０における有効フラグは，ブロッキングによる最適化が有効であるか否かを示す。ループデータ２１０の有効フラグのデフォルトは，“ＮＵＬＬ”である。ループデータ２１０の有効フラグは，後述のアクセスパターン解析部１２０の処理によって設定される。
【００９１】
本実施の形態の処理対象ループ解析部１００による処理の例を説明する。
【００９２】
処理対象ループ解析部１００は，まず，プログラムに含まれるＤＯループやＦＯＲループなどのループの入れ子関係を解析し，多重ループにおける最内ループを探し出す。より具体的には，処理対象ループ解析部１００は，ループデータ記憶部２００に記憶されたループデータ２１０を，外側のループから順にｎｅｘｔのポインタを辿って，ｎｅｘｔが“ＮＵＬＬ”である最内ループを見つけ出す。例えば，処理対象ループ解析部１００は，図１１（Ａ）に示す最適化対象ループにおいて，最外のループＫからループＪ，ループＩへと順に辿り，子ループがないループＩを最内ループとして抽出する。
【００９３】
次に，処理対象ループ解析部１００は，抽出された最内ループから順に外側にループを広げながら，タイトな構造を持つループの範囲を抽出する。処理対象ループ解析部１００は，抽出されたタイトな構造を持つループの範囲を，ブロッキングによる最適化の対象ループとする。以下では，ブロッキングによる最適化の対象ループを，ブロッキング対象ループと呼ぶものとする。
【００９４】
ループにおけるタイトな構造とは，ループが直列の入れ子構造をなし，最内ループにのみ実行文を有する構造である。本実施の形態では，タイトな構造を持つ多重ループをタイトなループと呼ぶものとする。途中のループとループとの間に実行文が含まれる場合には，実行文を含むループよりも下のループがタイトなループとみなされる。
【００９５】
図１３は，本実施の形態によるタイトなループを説明する図である。
【００９６】
図１３（Ａ）に示すループは，ループＸとループＹからなる２重ループである。図１３（Ａ）に示すループは，最内のループＹの内側にのみ演算の実行文を有している。すなわち，ループＸとループＹとからなる多重ループは，タイトなループである。
【００９７】
図１３（Ｂ）に示すループは，ループＸとループＹからなる２重ループである。図１３（Ｂ）に示すループでは，ループＸとループＹとの間に演算の実行文が含まれている。そのため，ループＸとループＹとからなる多重ループは，タイトなループではない。
【００９８】
図１３（Ｃ）に示すループは，ループＸ，ループＹ，ループＺからなる３重ループである。図１３（Ｃ）に示すループでは，ループＸとループＹとの間に演算の実行文が含まれており，ループＸ，ループＹ，ループＺからなる多重ループは，タイトなループではない。ただし，ループＹとループＺとの間には実行文が含まれていないので，ループＹとループＺとからなる多重ループは，タイトなループである。処理対象ループ解析部１００は，このようなタイトなループの範囲を抽出する。
【００９９】
例えば，図１１（Ａ）に示す最適化対象ループでは，最内のループＩの内側にのみ演算の実行分が存在する。処理対象ループ解析部１００は，図１１（Ａ）に示す最適化対象ループからループＫ，ループＪ，ループＩの３重ループをタイトなループとして抽出し，  ブロッキング対象ループとする。すなわち，図１１（Ａ）に示す最適化対象ループは，そのままブロッキング対象ループとなる。
【０１００】
図１４は，本実施の形態の処理対象ループ解析部による処理対象ループ解析処理フローチャートである。
【０１０１】
処理対象ループ解析部１００は，処理対象の多重ループから最内ループを抽出する（ステップＳ１０）。処理対象ループ解析部１００は，抽出された最内ループをタイトな最外ループとする（ステップＳ１１）。ここでのタイトな最外ループは，その時点でタイトなループであることが確認されているループのうち，最外のループを示す。
【０１０２】
処理対象ループ解析部１００は，現在のタイトな最外ループの外側に，ループがあるかを判定する（ステップＳ１２）。
【０１０３】
現在のタイトな最外ループの外側にループがある場合には（ステップＳ１２のＹＥＳ），処理対象ループ解析部１００は，現在のタイトな最外ループの１つ外側のループを含む多重ループがタイトなループであるかを判定する（ステップＳ１３）。
【０１０４】
現在のタイトな最外ループの１つ外側のループを含む多重ループがタイトなループであれば（ステップＳ１３のＹＥＳ），処理対象ループ解析部１００は，タイトな最外ループを，現在のタイトな最外ループのその１つ外側のループに更新する（ステップＳ１４）。処理対象ループ解析部１００は，ステップＳ１２に戻って，更新されたタイトな最外ループの処理に移る。
【０１０５】
現在のタイトな最外ループの外側にループがない場合には（ステップＳ１２のＮＯ），処理対象ループ解析部１００は，最内ループからタイトな最外ループまでのループをブロッキング対象ループとする（ステップＳ１５）。また，現在のタイトな最外ループの１つ外側のループを含む多重ループがタイトなループでなければ（ステップＳ１３のＮＯ），処理対象ループ解析部１００は，最内ループからタイトな最外ループまでのループをブロッキング対象ループとする（ステップＳ１５）。
【０１０６】
次に，本実施の形態の配列解析部１１０による処理の例を説明する。
【０１０７】
配列解析部１１０は，処理対象ループ解析部１００の処理によって抽出された，ブロッキング対象ループの最内ループ内で利用されている配列を抽出する。このとき，配列解析部１１０は，演算の実行によってメモリ３を更新する配列と，メモリ３を参照する配列とのすべてを列挙する。
【０１０８】
例えば，図１１（Ａ）のブロッキング対象ループにおいて，最内ループ内から，以下の６つの配列が抽出される。
【０１０９】
配列Ａ（Ｉ，Ｊ，Ｋ）
配列Ａ（Ｉ，Ｊ，Ｋ）
配列Ｂ（Ｊ，Ｋ，Ｉ）
配列Ｃ（Ｋ，Ｉ，Ｊ）
配列Ｄ（Ｉ，Ｘ，Ｊ）
配列Ｄ（Ｉ，Ｙ，Ｊ）
このうち，最内ループ内の演算の実行文の左辺にある配列Ａ（Ｉ，Ｊ，Ｋ）が演算の実行によってメモリ３を更新する配列であり，演算の実行文の右辺にある残りの５つの配列がメモリ３を参照する配列である。
【０１１０】
配列解析部１１０は，抽出された配列のうち，配列名と添え字とが全く同じ配列が複数ある場合には，それらの配列をまとめて１つの配列とみなす。配列名と添え字とが全く同じ配列に対するアクセスは，すべてメモリ３上の同じ領域へのアクセスとなる。すなわち，ブロッキング対象ループ内の処理で，配列名と添え字とが全く同じ配列に何度アクセスしても，アクセスするメモリ３は変わらない。そのため，後述のブロッキングによる最適化が行われたループ内の処理で配列が使用するメモリサイズを計算する手順では，配列名と添え字とが全く同じ配列が複数あっても，１つ分だけ計算すれば十分となる。
【０１１１】
例えば，図１１（Ａ）において，最内ループから抽出された配列には，配列Ａ（Ｉ，Ｊ，Ｋ）が２つある。このとき，配列解析部１１０は，１つの配列Ａ（Ｉ，Ｊ，Ｋ）が抽出されたものとみなす。
【０１１２】
配列解析部１１０は，最内ループ内から抽出された各配列について，配列データを生成する。配列解析部１１０は，生成された配列データを，ブロッキング対象ループ内から抽出された配列の情報として，配列情報記憶部１６０に記憶する。
【０１１３】
図１５は，本実施の形態による配列データの管理を説明する図である。
【０１１４】
図１５に示す配列データ１６５は，配列解析部１１０によって，図１１（Ａ）における最内ループ内から抽出された配列データ１６５の例である。配列データ１６５ａは，配列Ａ（Ｉ，Ｊ，Ｋ）の配列データである。配列データ１６５ｂは，配列Ｂ（Ｊ，Ｋ，Ｉ）の配列データである。配列データ１６５ｃは，配列Ｃ（Ｋ，Ｉ，Ｊ）の配列データである。配列データ１６５ｄ1 は，配列Ｄ（Ｉ，Ｘ，Ｊ）の配列データである。配列データ１６５ｄ2 は，配列Ｄ（Ｉ，Ｙ，Ｊ）の配列データである。このように，配列解析部１１０は，抽出された配列の数だけ，配列データ１６５を生成する。
【０１１５】
図１５に示す配列データ１６５は，該当配列についての配列名，添え字等の情報を有する。配列データ１６５において，添え字のフィールドは，配列の次元数分だけ用意される。すなわち，図１５に示すように，３次元の配列の配列データ１６５であれば，添え字＃１，添え字＃２，添え字＃３の３つの添え字のフィールドが存在する。
【０１１６】
また，図１５に示すように，配列解析部１１０は，ループデータ記憶部２００に記憶されたループデータ２１０における配列データのフィールドに，生成した配列データ１６５へのポインタを設定する。ここでは，最内ループのループデータ２１０に対してのみ，生成した配列データ１６５へのポインタが設定されるものとする。例えば，図１５に示すように，ブロッキング対象ループの最内ループであるループＩのループデータ２１０ｉにおける配列データのフィールドに，５つの配列データ１６５へのポインタが設定される。
【０１１７】
図１６は，本実施の形態の配列解析部による配列解析処理フローチャートである。
【０１１８】
配列解析部１１０は，ブロッキング対象ループの最内ループ内に存在する配列を１つ選択する（ステップＳ２０）。配列解析部１１０は，選択した配列の配列名を取得する（ステップＳ２１）。配列解析部１１０は，選択した配列の次元数，すなわち添え字の数を取得する（ステップＳ２２），配列解析部１１０は，選択した配列の添え字を登場順に取得する（ステップＳ２３）。
【０１１９】
配列解析部１１０は，配列名と添え字とが，選択された配列と全く同じである配列の配列データ１６５がすでにあるかを判定する（ステップＳ２４）。配列名と添え字とが，選択された配列と全く同じである配列の配列データ１６５がまだなければ（ステップＳ２４のＮＯ），配列解析部１１０は，選択された配列の配列データ１６５を生成する（ステップＳ２５）。このとき，配列解析部１１０は，取得された配列の次元数分の添え字フィールドを有する配列データ１６５を用意する。生成された配列データ１６５は，配列情報記憶部１６０に記憶される。
【０１２０】
配列解析部１１０は，最内ループ内に存在するすべての配列について処理が終了したかを判定する（ステップＳ２６）。すべての配列についてまだ処理が終了していなければ（ステップＳ２６のＮＯ），配列解析部１１０は，ステップＳ２０に戻って次の配列の処理に移る。すべての配列について処理が終了していれば（ステップＳ２６のＹＥＳ），配列解析部１１０は，処理を終了する。
【０１２１】
次に，本実施の形態のアクセスパターン解析部１２０による処理の例を説明する。
【０１２２】
アクセスパターン解析部１２０は，配列解析部１１０によって抽出された配列のアクセスパターンを解析する。
【０１２３】
アクセスパターンは，配列に対するメモリアクセスのパターンを示す。本実施の形態では，配列に対するメモリアクセスにおいて，アドレスに沿って順次メモリ３にアクセスするパターンをストレートと呼び，アドレスの間隔を空けて点々とメモリ３にアクセスするパターンをクロスと呼ぶものとする。アクセスパターンは，配列の添え字に登場する制御変数によって判断することができる。
【０１２４】
図１７は，本実施の形態によるアクセスパターンを説明する図である。
【０１２５】
図１７に示すループＫ，ループＪ，ループＩからなる多重ループにおいて，制御変数Ｋ，Ｊ，Ｉを更新するテンポが速い順に並べると，最内ループから最外ループに向かって出現する制御変数の順序で，Ｉ→Ｊ→Ｋとなる。本実施の形態では，ブロッキング対象ループの最内ループから最外ループに向かう順序で出現する制御変数を並べたものを，制御変数の連鎖と呼ぶものとする。
【０１２６】
図１７（Ａ）に示す多重ループにおいて，最内のループＩの内側には配列Ａ（Ｉ，Ｊ，Ｋ）が存在する。この配列Ａ（Ｉ，Ｊ，Ｋ）の添え字として使われている制御変数を，その登場する次元の順に並べると，Ｉ→Ｊ→Ｋとなる。本実施の形態では，ブロッキング対象ループの最内ループ内にある配列において，その配列に添え字として使われている制御変数をその出現順に並べたものを，添え字の連鎖と呼ぶものとする。このように，添え字の連鎖が制御変数の連鎖と同じ配列のアクセスパターンが，ストレートである。
【０１２７】
図１７（Ｂ）に示すブロッキング対象ループにおいて，上述したように制御変数の連鎖は，Ｉ→Ｊ→Ｋである。また，最内ループ内にある配列Ｂ（Ｊ，Ｋ，Ｉ）の添え字の連鎖は，Ｊ→Ｋ→Ｉである。このように，添え字の連鎖が制御変数の連鎖と異なる配列のアクセスパターンが，クロスである。
【０１２８】
ブロッキングによる最適化は，配列に対するメモリアクセスがメモリ３のアドレス順序ではなく，点在するようなケースにおいて，メモリ３へのアクセス範囲を局所化することで，キャッシュヒット率を向上させる最適化である。そのため，アクセスパターンがメモリ３を順次アクセスするストレートの配列しかないような多重ループに対してブロッキングによる最適化を適用しても，効果が出ない場合が多い。
【０１２９】
そこで，本実施の形態では，アクセスパターン解析部１２０によって，ブロッキング対象ループ内の各配列のアクセスパターンを解析することにより，ブロッキング対象ループに対してブロッキングによる最適化を適用することの有効性をチェックする。アクセスパターン解析部１２０は，ブロッキング対象ループが，アクセスパターンがメモリ３を点々とアクセスするクロスの配列を内側に持つような場合に，そのブロッキング対象ループに対するブロッキングによる最適化が有効であると判定する。
【０１３０】
アクセスパターン解析部１２０は，ブロッキング対象ループに対するブロッキングによる最適化が有効であると判定すれば，そのブロッキング対象ループの最内ループのループデータ２１０における有効フラグを“ＴＲＵＥ”に設定する。
【０１３１】
例えば，前述したように，配列解析部１１０は，図１１（Ａ）に示すブロッキング対象ループの内部から５つの配列を抽出し，５つの配列データ１６５を作成する。アクセスパターン解析部１２０は，配列解析部１１０により生成された５つの配列データ１６５を配列情報記憶部１６０から取得し，取得された配列データ１６５から各配列の添え字の連鎖を作成する。
【０１３２】
このとき，アクセスパターン解析部１２０は，添え字にブロッキング対象ループ内で値が不変のものがあれば，その添え字を省いて添え字の連鎖を作成する。ブロッキング対象ループ内で値が不変のものは，ブロッキング対象ループに含まれるループの制御変数以外のもの，例えば固定値やブロッキング対象ループより外側のループの制御変数などである。
【０１３３】
図１１（Ａ）に示すブロッキング対象ループの内部から抽出された５つの配列についての添え字の連鎖は，次のようになる。
【０１３４】
配列Ａ（Ｉ，Ｊ，Ｋ）：  Ｉ→Ｊ→Ｋ
配列Ｂ（Ｊ，Ｋ，Ｉ）：  Ｊ→Ｋ→Ｉ
配列Ｃ（Ｋ，Ｉ，Ｊ）：  Ｋ→Ｉ→Ｊ
配列Ｄ（Ｉ，Ｘ，Ｊ）：  Ｉ→Ｊ
配列Ｄ（Ｉ，Ｙ，Ｊ）：  Ｉ→Ｊ
配列Ｄ（Ｉ，Ｘ，Ｊ），配列Ｄ（Ｉ，Ｙ，Ｊ）については，それぞれＸ，Ｙがブロッキング対象ループ内で不変値であるので，添え字の連鎖から省かれる。
【０１３５】
ここで，図１１（Ａ）に示すブロッキング対象ループに含まれるループは，内側から順に，ループＩ，ループＪ，ループＫである。よって，図１１（Ａ）に示すブロッキング対象ループの制御変数の連鎖は，Ｉ→Ｊ→Ｋとなる。
【０１３６】
図１１（Ａ）に示すブロッキング対象ループの制御変数の連鎖と，各配列の添え字の連鎖とを比較すると，各配列のアクセスパターンは，次のようになる。
【０１３７】
配列Ａ（Ｉ，Ｊ，Ｋ）：  ストレート
配列Ｂ（Ｊ，Ｋ，Ｉ）：  クロス
配列Ｃ（Ｋ，Ｉ，Ｊ）：  クロス
配列Ｄ（Ｉ，Ｘ，Ｊ）：  ストレート
配列Ｄ（Ｉ，Ｙ，Ｊ）：  ストレート
このように，配列Ｂ（Ｊ，Ｋ，Ｉ）と配列Ｃ（Ｋ，Ｉ，Ｊ）のアクセスパターンがクロスであるので，アクセスパターン解析部１２０は，図１１（Ａ）に示すブロッキング対象ループに対するブロッキングによる最適化が有効であると判定する。
【０１３８】
図１８は，本実施の形態によるループデータにおける有効フラグを設定した例を示す図である。
【０１３９】
図１８に示すように，アクセスパターン解析部１２０は，ブロッキングによる最適化が有効であると判定された図１１（Ａ）に示すブロッキング対象ループについて，最内ループＩのループデータ２１０ｉにおける有効フラグを，“ＴＲＵＥ”に設定する。
【０１４０】
図１９は，本実施の形態のアクセスパターン解析部によるアクセスパターン解析処理フローチャートである。
【０１４１】
アクセスパターン解析部１２０は，ブロッキング対象ループの最内ループのループデータ２１０における有効フラグを，無効を示す“ＦＡＬＳＥ”で初期化する（ステップＳ３０）。
【０１４２】
アクセスパターン解析部１２０は，ブロッキング対象ループが多重ループであるかを判定する（ステップＳ３１）。ブロッキング対象ループが多重ループでなければ（ステップＳ３１のＮＯ），アクセスパターン解析部１２０は，処理を終了する。ブロッキング対象ループが１重のループである場合には，そのブロッキング対象ループにブロッキングによる最適化を適用しても，効果が出ない場合が多い。本実施の形態では，このような１重ループであるブロッキング対象ループに対するブロッキングを行わない。なお，上述の処理対象ループ解析部１００の処理において，タイトなループが１重ループである場合に，ブロッキング対象ループから外すようにしてもよい。
【０１４３】
ブロッキング対象ループが多重ループであれば（ステップＳ３１のＹＥＳ），アクセスパターン解析部１２０は，ブロッキング対象ループのループデータ２１０から，制御変数の連鎖を作成する（ステップＳ３２）。
【０１４４】
アクセスパターン解析部１２０は，配列情報記憶部１６０から，ブロッキング対象ループの最内ループ内にある配列の配列データ１６５を１つ選択する（ステップＳ３３）。アクセスパターン解析部１２０は，選択された配列データ１６５の添え字の連鎖作成処理を行う（ステップＳ３４）。添え字の連鎖作成処理については，後述する。
【０１４５】
アクセスパターン解析部１２０は，制御変数の連鎖と選択された配列データ１６５の添え字の連鎖とを比較し，アクセスパターンを確認する（ステップＳ３５）。アクセスパターンがクロスであれば（ステップＳ３５のクロス），アクセスパターン解析部１２０は，ブロッキング対象ループの最内ループのループデータ２１０における有効フラグに，有効を示す“ＴＲＵＥ”を設定し（ステップＳ３６），処理を終了する。
【０１４６】
アクセスパターンがストレートであれば（ステップＳ３５のストレート），アクセスパターン解析部１２０は，ブロッキング対象ループの最内ループ内にあるすべての配列の配列データ１６５について処理が終了したかを判定する（ステップＳ３７）。すべての配列データ１６５についてまだ処理が終了していなければ（ステップＳ３７のＮＯ），アクセスパターン解析部１２０は，ステップＳ３３に戻って次の配列データ１６５の処理に移る。すべての配列データ１６５について処理が終了していれば（ステップＳ３７のＹＥＳ），アクセスパターン解析部１２０は，処理を終了する。
【０１４７】
図２０は，本実施の形態のアクセスパターン解析部による添え字の連鎖作成処理フローチャートである。
【０１４８】
アクセスパターン解析部１２０は，添え字の連鎖を作成する対象配列の配列データ１６５から，出現順に添え字を１つ取得する（ステップＳ３４０）。アクセスパターン解析部１２０は，取得された添え字がブロッキング対象ループに含まれるループの制御変数であるかを判定する（ステップＳ３４１）。
【０１４９】
取得された添え字がブロッキング対象ループに含まれるループの制御変数であれば（ステップＳ３４１のＹＥＳ），アクセスパターン解析部１２０は，取得された添え字を添え字の連鎖に追加する（ステップＳ３４２）。
【０１５０】
アクセスパターン解析部１２０は，配列データ１６５内のすべての添え字について処理が終了したかを判定する（ステップＳ３４３）。すべての添え字についてまだ処理が終了していなければ（ステップＳ３４３のＮＯ），アクセスパターン解析部１２０は，ステップＳ３４０に戻って次の添え字の処理に移る。すべての添え字について処理が終了していれば（ステップＳ３４３のＹＥＳ），アクセスパターン解析部１２０は，処理を終了する。
【０１５１】
次に，本実施の形態のメモリサイズ計算式生成部１３０による処理の例を説明する。
【０１５２】
メモリサイズ計算式生成部１３０は，アクセスパターン解析部１２０による判定の結果，ループデータ２１０における有効フラグが“ＴＲＵＥ”となっているブロッキング対象ループについて，メモリサイズ計算式を生成する。メモリサイズ計算式は，ブロッキング対象ループに対するブロッキングによって最適化される範囲で，ブロッキング対象ループ内の全配列が使用するメモリサイズを計算する計算式である。
【０１５３】
例えば，図１１（Ｂ）に示すブロッキング後の最適化対象ループにおいて，ループＫ，ループＪ，ループＩが，分割ブロック長ｂｌｏｃｋを用いたブロッキングによって最適化された範囲である。このとき，メモリサイズ計算式は，図１１（Ｂ）に示すブロッキング後の最適化対象ループにおけるループＫ，ループＪ，ループＩのみが回転する範囲で，その最内ループ内の全配列が使用するメモリサイズを計算する計算式である。
【０１５４】
メモリサイズ計算式生成部１３０は，ブロッキング対象ループ内の配列ごとに生成される配列別メモリ計算式から，メモリサイズ計算式を生成する。配列別メモリ計算式は，配列ごとに生成される，ブロッキング対象ループに対するブロッキングによって最適化される範囲で，それぞれの配列が使用するメモリサイズを計算する計算式である。
【０１５５】
図２１は，本実施の形態による配列別メモリ計算式の生成を説明する図である。
【０１５６】
図２１（Ａ）は，最内ループＩの内側に４次元の配列Ａ（Ｉ，Ｊ，Ｋ，Ｌ）を有する，ループＬ，ループＫ，ループＪ，ループＩからなるタイトな４重ループの例を示す。ここでは，図２１に示す４重ループに対してブロッキングによる最適化を行った場合に，ブロッキングによって最適化された範囲で，配列Ａ（Ｉ，Ｊ，Ｋ，Ｌ）が使用するメモリサイズを計算する計算式を生成する例を説明する。
【０１５７】
なお，図２１（Ａ）に示すように，配列Ａ（Ｉ，Ｊ，Ｋ，Ｌ）は，配列の型が実数（ｒｅａｌ）であることが宣言されており，配列Ａ（Ｉ，Ｊ，Ｋ，Ｌ）の型サイズは，８バイトとなる。また，ループＬにはブロッキングを実行しない旨が指示されており，そのループデータ２１０におけるブロッキングフラグには，“ＦＡＬＳＥ”が設定されている。また，ループＪには固定の分割ブロック長２０が指示されており，そのループデータ２１０における分割ブロック長のフィールドには，２０が設定されている。ループＫとループＩに対しては，特定の指示がないので，そのループデータ２１０における分割ブロック長のフィールドには，自動計算を示す０が設定されている。
【０１５８】
図２１（Ｂ）は，配列別メモリ計算データ１７５の例を示す。配列別メモリ計算データ１７５は，本実施の形態において，配列別メモリ計算式を表すデータである。配列別メモリ計算データ１７５は，可変部と固定部とを有する。
【０１５９】
可変部は，配列別メモリ計算式において，自動計算される分割ブロック長の値によって，配列が使用するメモリサイズが変化する部分を示している。図２１（Ｂ）に示す配列別メモリ計算データ１７５において，ｎは自動計算する分割ブロック長を示す。計算式を生成する配列において，自動計算される分割ブロック長で最適化を行うループの制御変数である添え字の個数をＺとすると，配列別メモリ計算データ１７５の可変部は，ｎZ で表される。ここでは，Ｚを指数部と呼ぶ。
【０１６０】
固定部は，配列別メモリ計算式において，自動計算される分割ブロック長の値によって，配列が使用するメモリサイズが変化しない部分を示している。配列別メモリ計算データ１７５の固定部は，計算式を生成する配列において固定の分割ブロック長が指定されたループの制御変数が添え字に含まれていない場合には，配列の型サイズの値となる。また，配列別メモリ計算データ１７５の固定部は，計算式を生成する配列において固定の分割ブロック長が指定されたループの制御変数が添え字に含まれている場合には，その固定のブロック長と配列の型サイズとを掛け合わせた値となる。
【０１６１】
なお，ブロッキングを実行しない旨が指定されたループの制御変数である添え字は，配列別メモリ計算式に含めない。また，ブロッキング対象ループ内で値が不変の添え字は，ブロッキングによる最適化の影響を受けないので，配列別メモリ計算式の生成では無視される。
【０１６２】
例えば，図２１（Ａ）に示す多重ループ内の配列Ａ（Ｉ，Ｊ，Ｋ，Ｌ）において，添え字Ｉと添え字Ｋの２つが，自動計算される分割ブロック長で最適化を行うループの制御変数である。よって，指数部Ｚ＝２となり，配列別メモリ計算式における可変部は，ｎ2 となる。また，添え字Ｊは，固定の分割ブロック長として２０が指定されたループの制御変数である。配列Ａの型サイズが８バイトであるので，配列別メモリ計算式における固定部は，８（配列の型サイズ）×２０（固定の分割ブロック長）＝１６０となる。なお，添え字Ｌについては，ブロッキングを実行しない旨が指定されたループの制御変数であるので，配列別メモリ計算式における可変部にも固定部にも含まれない。
【０１６３】
配列別メモリ計算データ１７５には，可変部の計算結果を示すフィールドに，固定部の計算結果が格納される。すなわち，図２１（Ｂ）に示すように，可変部の計算結果ｎ2 のフィールドに，固定部の計算結果１６０が格納される。なお，配列別メモリ計算データ１７５において，各フィールドの固定部の初期値は０である。
【０１６４】
図２１（Ｂ）に示す配列別メモリ計算データ１７５が表す配列別メモリ計算式は，
（ｎ0 ×０）＋（ｎ1 ×０）＋（ｎ2 ×１６０）＋（ｎ3 ×０）＋（ｎ4 ×０）
＝１６０ｎ2 
となる。この配列別メモリ計算式１６０ｎ2 が，図２１（Ａ）に示す多重ループに対して分割ブロック長ｎを用いたブロッキングによる最適化を実行した場合の，配列Ａ（Ｉ，Ｊ，Ｋ，Ｌ）が使用するメモリサイズを計算する計算式となる。
【０１６５】
図２２は，本実施の形態による配列別メモリ計算式からのメモリサイズ計算式の生成を説明する図である。
【０１６６】
メモリサイズ計算式生成部１３０は，図１１（Ａ）に示すブロッキング対象ループから抽出された各配列について，配列情報記憶部１６０に記憶された各配列データ１６５と，ループデータ記憶部２００に記憶された各ループデータ２１０とを用いて，配列別メモリ計算式を生成する。
【０１６７】
ここでは，配列Ａ，配列Ｂ，配列Ｃ，配列Ｄのすべてについて，配列の型としてｒｅａｌ型が宣言されており，すべての配列の型サイズが８バイトであるものとする。
【０１６８】
配列Ａ（Ｉ，Ｊ，Ｋ），配列Ｂ（Ｊ，Ｋ，Ｉ），配列Ｃ（Ｋ，Ｉ，Ｊ）については，すべての添え字がブロッキング対象ループに含まれるループの制御変数であるので，配列別メモリ計算式の可変部はｎ3 となる。また，ブロッキング対象ループに固定の分割ブロック長が指示されたループがないので，配列別メモリ計算式の固定部は配列の型サイズのみで８となる。なお，ブロッキング対象ループに含まれる各ループのループデータ２１０におけるブロッキングフラグは，すべて“ＴＲＵＥ”である。よって，配列Ａ（Ｉ，Ｊ，Ｋ），配列Ｂ（Ｊ，Ｋ，Ｉ），配列Ｃ（Ｋ，Ｉ，Ｊ）の配列別メモリ計算式は，すべて８ｎ3 となる。
【０１６９】
配列Ｄ（Ｉ，Ｘ，Ｊ），配列Ｄ（Ｉ，Ｙ，Ｊ）については，それぞれ，添え字Ｘ，添え字Ｙが，ブロッキング対象ループに含まれるループの制御変数ではなく，ブロッキング対象ループ内で不変の値となる。添え字Ｉと添え字Ｊはブロッキング対象ループに含まれるループの制御変数であるので，配列別メモリ計算式の可変部はｎ2 となる。また，ブロッキング対象ループに固定の分割ブロック長が指示されたループがないので，配列別メモリ計算式の固定部は配列の型サイズのみで８となる。よって，配列Ｄ（Ｉ，Ｘ，Ｊ），配列Ｄ（Ｉ，Ｙ，Ｊ）の配列別メモリ計算式は，それぞれ８ｎ2 となる。
【０１７０】
各配列について生成された配列別メモリ計算式を表す配列別メモリ計算データ１７５は，図２２に示す通りとなる。配列別メモリ計算データ１７５ａは，配列Ａ（Ｉ，Ｊ，Ｋ）が使用するメモリサイズを計算する配列別メモリ計算式を表すデータである。配列別メモリ計算データ１７５ｂは，配列Ｂ（Ｊ，Ｋ，Ｉ）が使用するメモリサイズを計算する配列別メモリ計算式を表すデータである。配列別メモリ計算データ１７５ｃは，配列Ｃ（Ｋ，Ｉ，Ｊ）が使用するメモリサイズを計算する配列別メモリ計算式を表すデータである。配列別メモリ計算データ１７５ｄ1 は，配列Ｄ（Ｉ，Ｘ，Ｊ）が使用するメモリサイズを計算する配列別メモリ計算式を表すデータである。配列別メモリ計算データ１７５ｄ2 は，配列Ｄ（Ｉ，Ｙ，Ｊ）が使用するメモリサイズを計算する配列別メモリ計算式を表すデータである。メモリサイズ計算式生成部１３０は，生成された各配列別メモリ計算データ１７５を，配列別メモリ計算情報記憶部１７０に記憶する。
【０１７１】
次に，メモリサイズ計算式生成部１３０は，配列ごとの配列別メモリ計算式から，全配列が使用するメモリサイズを計算するメモリサイズ計算式を生成する。メモリサイズ計算式は，配列ごとに生成されたすべての配列別メモリ計算式を加算することで得られる。
【０１７２】
図２２において，メモリサイズ計算データ１８５は，メモリサイズ計算式を表すデータである。メモリサイズ計算データ１８５のデータ構造は，配列別メモリ計算データ１７５のデータ構造と同様である。
【０１７３】
メモリサイズ計算式生成部１３０は，図２２に示すように，配列別メモリ計算情報記憶部１７０に記憶された全配列の配列別メモリ計算データ１７５の固定部を，メモリサイズ計算データ１８５上でマージする。なお，メモリサイズ計算データ１８５において，各フィールドの固定部の初期値は０である。
【０１７４】
このように，メモリサイズ計算式生成部１３０により，図１１に示すブロッキング対象ループ内の全配列が使用するメモリサイズを計算する計算式を表すデータとして，図２２に示すメモリサイズ計算データ１８５が生成される。メモリサイズ計算式生成部１３０は，生成されたメモリサイズ計算データ１８５を，メモリサイズ計算情報記憶部１８０に記憶する。
【０１７５】
図２２に示すメモリサイズ計算データ１８５が表すメモリサイズ計算式は，
（ｎ0 ×０）＋（ｎ1 ×０）＋（ｎ2 ×１６）＋（ｎ3 ×２４）
＝１６ｎ2 ＋２４ｎ3 
となる。なお，配列の型サイズの単位をバイトで計算しているので，このメモリサイズ計算式で得られるサイズの単位は，バイトである。
【０１７６】
図２３は，本実施の形態のメモリサイズ計算式生成部によるメモリサイズ計算式生成処理フローチャートである。
【０１７７】
メモリサイズ計算式生成部１３０は，配列情報記憶部１６０に記憶された，ブロッキング対象ループ内から抽出された配列の配列データ１６５を，１つ選択する（ステップＳ４０）。メモリサイズ計算式生成部１３０は，選択された配列データ１６５について，配列別メモリ計算データ生成処理を行う（ステップＳ４１）。配列別メモリ計算データ生成処理の詳細については，後述する。
【０１７８】
メモリサイズ計算式生成部１３０は，ブロッキング対象ループ内から抽出されたすべての配列の配列データ１６５について処理が終了したかを判定する（ステップＳ４２）。すべての配列の配列データ１６５についてまだ処理が終了していなければ（ステップＳ４２のＮＯ），メモリサイズ計算式生成部１３０は，ステップＳ４０に戻って次の配列の配列データ１６５の処理に移る。
【０１７９】
すべての配列の配列データ１６５について処理が終了していれば（ステップＳ４２のＹＥＳ），メモリサイズ計算式生成部１３０は，生成されたすべての配列別メモリ計算データ１７５から，固定部に値が格納された可変部における最大の指数部の値を取得する（ステップＳ４３）。メモリサイズ計算式生成部１３０は，指数部が，０から取得された最大の指数部までの可変部のフィールドを有するメモリサイズ計算データ１８５を生成する（ステップＳ４４）。
【０１８０】
メモリサイズ計算式生成部１３０は，配列別メモリ計算データ１７５を１つ選択する（ステップＳ４５）。メモリサイズ計算式生成部１３０は，選択された配列別メモリ計算データ１７５を，メモリサイズ計算データ１８５にマージする（ステップＳ４６）。
【０１８１】
メモリサイズ計算式生成部１３０は，生成されたすべての配列別メモリ計算データ１７５について処理が終了したかを判定する（ステップＳ４７）。すべての配列別メモリ計算データ１７５についてまだ処理が終了していなければ（ステップＳ４７のＮＯ），メモリサイズ計算式生成部１３０は，ステップＳ４５に戻って次の配列別メモリ計算データ１７５の処理に移る。すべての配列別メモリ計算データ１７５について処理が終了していれば（ステップＳ４７のＹＥＳ），メモリサイズ計算式生成部１３０は，処理を終了する。
【０１８２】
図２４は，本実施の形態のメモリサイズ計算式生成部による配列別メモリ計算データ生成処理フローチャートである。
【０１８３】
メモリサイズ計算式生成部１３０は，ａを１に，Ｚを０に初期化する（ステップＳ４１０）。
【０１８４】
メモリサイズ計算式生成部１３０は，配列データ１６５から添え字を１つ選択する（ステップＳ４１１）。
【０１８５】
メモリサイズ計算式生成部１３０は，ループデータ記憶部２００に記憶されたブロッキング対象ループのループデータ２１０を参照し，選択された添え字がブロッキング対象ループに含まれるループの制御変数であるかを判定する（ステップＳ４１２）。選択された添え字が制御変数でなければ（ステップＳ４１２のＮＯ），メモリサイズ計算式生成部１３０は，ステップＳ４１７の処理に進む。
【０１８６】
選択された添え字が制御変数であれば（ステップＳ４１２のＹＥＳ），メモリサイズ計算式生成部１３０は，選択された添え字を制御変数とするループのループデータ２１０におけるブロッキングフラグが“ＴＲＵＥ”であるかを判定する（ステップＳ４１３）。ブロッキングフラグが“ＴＲＵＥ”でなければ（ステップＳ４１３のＮＯ），メモリサイズ計算式生成部１３０は，ステップＳ４１７の処理に進む。
【０１８７】
ブロッキングフラグが“ＴＲＵＥ”であれば（ステップＳ４１３のＹＥＳ），メモリサイズ計算式生成部１３０は，選択された添え字を制御変数とするループのループデータ２１０における分割ブロック長に固定の分割ブロック長が設定されているかを判定する（ステップＳ４１４）。固定の分割ブロック長が設定されていれば（ステップＳ４１４のＹＥＳ），メモリサイズ計算式生成部１３０は，ａの値を，ａ×指定された固定の分割ブロック長の値で更新する（ステップＳ４１５）。固定の分割ブロック長が指定されていなければ（ステップＳ４１４のＮＯ），メモリサイズ計算式生成部１３０は，Ｚの値をインクリメントする（ステップＳ４１６）。
【０１８８】
メモリサイズ計算式生成部１３０は，配列データ１６５のすべての添え字について処理が終了したかを判定する（ステップＳ４１７）。すべての添え字についてまだ処理が終了していなければ（ステップＳ４１７のＮＯ），メモリサイズ計算式生成部１３０は，ステップＳ４１１に戻って次の添え字の処理に移る。
【０１８９】
すべての添え字について処理が終了していれば（ステップＳ４１７のＹＥＳ），メモリサイズ計算式生成部１３０は，配列の型サイズｂを取得する（ステップＳ４１８）。メモリサイズ計算式生成部１３０は，ｃ＝ａ×ｂを計算する（ステップＳ４１９）。メモリサイズ計算式生成部１３０は，配列別メモリ計算データ１７５の可変部がｎZ であるフィールドの固定部に，算出されたｃを設定する（ステップＳ４２０）。
【０１９０】
次に，本実施の形態の分割ブロック長計算部１４０による処理の例を説明する。
【０１９１】
分割ブロック長計算部１４０は，メモリサイズ計算式生成部１３０により生成されたメモリサイズ計算式に，分割ブロック長を入力し，メモリサイズを計算する。このとき，分割ブロック長計算部１４０は，メモリサイズ計算式に入力する分割ブロック長を小さい値から徐々に大きくしていき，得られたメモリサイズがキャッシュメモリのサイズを超えない，適切な分割ブロック長を求める。
【０１９２】
図２５は，本実施の形態によるメモリサイズ計算式を用いて分割ブロック長を自動計算する例を説明する図である。
【０１９３】
図２５において，メモリサイズ計算データ１８５は，図１１（Ａ）に示すブロッキング対象ループに基づいて生成された，図２２に示すメモリサイズ計算データ１８５である。すなわち，図２５に示すメモリサイズ計算データ１８５は，メモリサイズ計算式１６ｎ2 ＋２４ｎ3 を表すメモリサイズ計算データ１８５である。
【０１９４】
図２５において，キャッシュサイズは，コンピュータ１が備える階層型のメモリ３における１次キャッシュメモリのサイズを示す。ここでは，キャッシュサイズが１３１０７２バイトであるものとする。
【０１９５】
分割ブロック長計算部１４０は，メモリサイズ計算データ１８５のｎに，分割ブロック長として仮定した値を入力し，メモリサイズを算出する。分割ブロック長計算部１４０は，算出されたメモリサイズとキャッシュサイズとを比較し，メモリサイズがキャッシュサイズを超えているかをチェックする。
【０１９６】
メモリサイズ計算データ１８５に分割ブロック長と仮定して入力する値は，任意である。本実施の形態では，キャッシュラインやアライメントを意識して，メモリサイズ計算データ１８５に８の倍数を入力していくものとする。また，図２５では，算出されたメモリサイズとキャッシュサイズとの比較結果として，メモリサイズがキャッシュサイズ以下の場合には○が，メモリサイズがキャッシュサイズを超えている場合には×が記載されている。
【０１９７】
まず，分割ブロック長計算部１４０は，メモリサイズ計算データ１８５のｎに，分割ブロック長として８を入力する。このとき，メモリサイズ計算データ１８５によって得られるメモリサイズは，１３３１２バイトとなる。算出されたメモリサイズは，キャッシュサイズ以下であるので，比較結果は○となる。
【０１９８】
次に，分割ブロック長計算部１４０は，メモリサイズ計算データ１８５のｎに，分割ブロック長として１６を入力する。このとき，メモリサイズ計算データ１８５によって得られるメモリサイズは，１０２４００バイトとなる。算出されたメモリサイズは，キャッシュサイズ以下であるので，比較結果は○となる。
【０１９９】
次に，分割ブロック長計算部１４０は，メモリサイズ計算データ１８５のｎに，分割ブロック長として２４を入力する。このとき，メモリサイズ計算データ１８５によって得られるメモリサイズは，３４０９９２バイトとなる。算出されたメモリサイズは，キャッシュサイズを超えているので，比較結果は×となる。
【０２００】
分割ブロック長計算部１４０は，キャッシュサイズを超えない最大のメモリサイズが得られた入力値１６を，図１１（Ａ）に示すブロッキング対象ループに対するブロッキングによる最適化で用いる，自動計算された分割ブロック長として決定する。
【０２０１】
図２６は，本実施の形態の分割ブロック長計算部による分割ブロック長計算処理フローチャートである。
【０２０２】
分割ブロック長計算部１４０は，分割ブロック長の値を−１に設定する（ステップＳ５０）。分割ブロック長計算部１４０は，−１に設定された分割ブロック長を，メモリ３上の退避領域に退避する（ステップＳ５１）。ここまでの処理は，メモリサイズ計算データ１８５に入力する分割ブロック長の値を初期化する処理である。メモリサイズ計算データ１８５に最初の分割ブロック長を入力して得られるメモリサイズがキャッシュサイズを超えてしまうような場合には，ブロッキング対象ループに対する自動計算されたブロック長を用いたブロッキングは行われない。そのため，分割ブロック長の初期値として，ブロッキングによる最適化を実行しない旨を示す−１が設定される。
【０２０３】
分割ブロック長計算部１４０は，分割ブロック長に最初の入力値を設定する（ステップＳ５２）。分割ブロック長計算部１４０は，オペレーティングシステム４０に対して問い合わせを行い，キャッシュサイズを取得する（ステップＳ５３）。
【０２０４】
分割ブロック長計算部１４０は，メモリサイズ計算データ１８５に分割ブロック長を入力して，メモリサイズを算出する（ステップＳ５４）。分割ブロック長計算部１４０は，算出されたメモリサイズが，取得されたキャッシュサイズを超えているかを判定する（ステップＳ５５）。
【０２０５】
メモリサイズがキャッシュサイズを超えていなければ（ステップＳ５５のＮＯ），分割ブロック長計算部１４０は，分割ブロック長の値をメモリ３上の退避領域に退避する（ステップＳ５６）。この処理で，退避領域に前に退避された分割ブロック長が更新される。分割ブロック長計算部１４０は，メモリサイズ計算データ１８５に入力する分割ブロック長の値を増加し（ステップＳ５７），ステップＳ５４に戻って，増加された分割ブロック長の処理に移る。
【０２０６】
メモリサイズがキャッシュサイズを超えていれば（ステップＳ５５のＹＥＳ），分割ブロック長計算部１４０は，その時点でメモリ３の退避領域に退避されている値を，自動計算された分割ブロック長の値として決定し（ステップＳ５８），処理を終了する。
【０２０７】
次に，本実施の形態のブロッキング指示部１５０による処理の例を説明する。
【０２０８】
ブロッキング指示部１５０は，分割ブロック長計算部１４０により決定された分割ブロック長を用いたブロッキングによる最適化実行の指示を行う。より具体的には，ブロッキング指示部１５０は，ループデータ記憶部２００に記憶されたブロッキング対象ループの各ループデータ２１０における分割ブロック長に対して，自動計算された分割ブロック長の値を設定する。このとき，ブロッキング指示部１５０は，ループデータ２１０における分割ブロック長に自動計算を示す０が設定されているものについてのみ，自動計算された分割ブロック長の設定を行う。
【０２０９】
例えば，本実施の形態では，ブロッキング指示部１５０は，図１２に示すブロッキング対象ループの各ループデータ２１０における分割ブロック長に対して，図２５に示す例で決定された分割ブロック長の値１６を設定する。
【０２１０】
図２７は，本実施の形態によるブロッキング指示部によるブロッキング指示処理フローチャートである。
【０２１１】
ブロッキング指示部１５０は，ループデータ記憶部２００に記憶された，ブロッキング対象ループに含まれるループのループデータ２１０を，１つ選択する（ステップＳ６０）。
【０２１２】
ブロッキング指示部１５０は，選択されたループデータ２１０におけるブロッキングフラグが“ＴＲＵＥ”であるかを判定する（ステップＳ６１）。また，ブロッキング指示部１５０は，選択されたループデータ２１０における分割ブロック長に，固定の分割ブロック長が設定されているかを判定する（ステップＳ６２）。
【０２１３】
ブロッキングフラグが“ＴＲＵＥ”であり（ステップＳ６１のＹＥＳ），かつ分割ブロック長に固定の分割ブロック長が設定されていない場合には（ステップＳ６２のＮＯ），ブロッキング指示部１５０は，選択されたループデータ２１０の分割ブロック長に，自動計算された分割ブロック長の値を設定する（ステップＳ６３）。
【０２１４】
ブロッキング指示部１５０は，ブロッキング対象ループに含まれるループのすべてのループデータ２１０について処理が終了したかを判定する（ステップＳ６４）。すべてのループデータ２１０についてまだ処理が終了していなければ（ステップＳ６４のＮＯ），ブロッキング指示部１５０は，ステップＳ６０に戻って次のループデータ２１０の処理に移る。すべてのループデータ２１０について処理が終了していれば（ステップＳ６４のＹＥＳ），ブロッキング指示部１５０は，処理を終了する。
【０２１５】
最適化実行部１７は，中間コードの一部としてループデータ記憶部２００に記憶されたループデータ２１０における分割ブロック長の値を用いて，ブロッキング対象ループに対するブロッキングによる最適化を実行する。
【０２１６】
以下，図２８〜図３１を用いて，本実施の形態のブロッキングによる最適化の具体的な実施例をいくつか説明する。
【０２１７】
図２８は，本実施の形態のブロッキングによる最適化を３重以上のループに対して実行した例である。
【０２１８】
図２８に示す最適化対象ループは，ループＫ，ループＪ，ループＩからなる。図２８に示す最適化対象ループは，最内のループＩ内にのみ演算の実行文を有するタイトなループであるので，処理対象ループ解析部１００は，図２８に示す最適化対象ループをそのままブロッキング対象ループとする。配列解析部１１０は，３つの配列を抽出する。アクセスパターン解析部１２０は，抽出された配列Ｃ（Ｋ，Ｊ）のアクセスパターンがクロスであるので，図２８に示す最適化対象ループに対するブロッキングによる最適化が有効であると判定する。
【０２１９】
抽出された３つの配列の型は，すべてｒｅａｌ（配列の型サイズは８バイト）で宣言されているものとする。また，３つの配列は，すべてブロッキング対象ループに含まれるループの制御変数を添え字とする，２次元の配列である。メモリサイズ計算式生成部１３０は，メモリサイズ計算式２４ｎ2 を生成する。
【０２２０】
キャッシュサイズとして，１３１０７２バイトが取得されたものとする。分割ブロック長計算部１４０は，メモリサイズ計算式２４ｎ2 に８の倍数を小さい値から順に入力していく。分割ブロック長計算部１４０は，メモリサイズ計算式２４ｎ2 から得られるメモリサイズが，キャッシュサイズを超えない最大のｎを，自動計算された分割ブロック長として，決定する。ここでは，ｎ＝７２のときに得られるメモリサイズ１２４４１６バイトが，キャッシュサイズを超えない最大のメモリサイズとなる。
【０２２１】
ブロッキング指示部１５０は，得られた値７２を自動計算される分割ブロック長として，最適化実行部１７に指示する。最適化実行部１７は，自動計算された分割ブロック長ｂｌｏｃｋ＝７２を用いて，図２８に示す最適化対象ループに対するブロッキングによる最適化を実行する。図２８に示す最適化対象ループに対するブロッキングによる最適化の実行結果として，図２８に示すブロッキング後ループが得られる。
【０２２２】
このように，本実施の形態のブロッキングによる最適化の技術によって，３重ループ以上に対するブロッキングによる最適化が可能となる。
【０２２３】
図２９は，本実施の形態のブロッキングによる最適化を３次元以上の配列を含む多重ループに対して実行した例である。
【０２２４】
図２９に示す最適化対象ループは，ループＫ，ループＪ，ループＩからなる。図２９に示す最適化対象ループは，最内のループＩ内にのみ，３次元の配列を持つ演算の実行文を有するタイトなループであるので，処理対象ループ解析部１００は，図２９に示す最適化対象ループをそのままブロッキング対象ループとする。配列解析部１１０は，５つの配列を抽出する。アクセスパターン解析部１２０は，抽出された配列Ｂ（Ｊ，Ｋ，Ｉ）のアクセスパターンがクロスであるので，図２９に示す最適化対象ループに対するブロッキングによる最適化が有効であると判定する。
【０２２５】
抽出された５つの配列の型は，すべてｒｅａｌ（配列の型サイズは８バイト）で宣言されているものとする。また，５つの配列のうちの３つは，すべてブロッキング対象ループに含まれるループの制御変数を添え字とする，３次元の配列である。５つの配列のうちの２つは，ブロッキング対象ループに含まれるループの制御変数でない添え字を１つ含む，３次元の配列である。メモリサイズ計算式生成部１３０は，メモリサイズ計算式１６ｎ2 ＋２４ｎ3 を生成する。
【０２２６】
キャッシュサイズとして，１３１０７２バイトが取得されたものとする。分割ブロック長計算部１４０は，メモリサイズ計算式１６ｎ2 ＋２４ｎ3 に８の倍数を小さい値から順に入力していく。分割ブロック長計算部１４０は，メモリサイズ計算式１６ｎ2 ＋２４ｎ3 から得られるメモリサイズが，キャッシュサイズを超えない最大のｎを，自動計算された分割ブロック長として，決定する。ここでは，ｎ＝１６のときに得られるメモリサイズ１０２４００バイトが，キャッシュサイズを超えない最大のメモリサイズとなる。
【０２２７】
ブロッキング指示部１５０は，得られた値１６を自動計算される分割ブロック長として，最適化実行部１７に指示する。最適化実行部１７は，自動計算された分割ブロック長ｂｌｏｃｋ＝１６を用いて，図２９に示す最適化対象ループに対するブロッキングによる最適化を実行する。図２９に示す最適化対象ループに対するブロッキングによる最適化の実行結果として，図２９に示すブロッキング後ループが得られる。
【０２２８】
このように，本実施の形態のブロッキングによる最適化の技術によって，３次元以上の配列を含む多重ループに対するブロッキングによる最適化が可能となる。
【０２２９】
図３０は，本実施の形態のブロッキングによる最適化をブロッキング抑止の最適化指示行を含む多重ループに対して実行した例である。
【０２３０】
図３０に示す最適化対象ループは，ループＫ，ループＪ，ループＩからなる。図３０に示す最適化対象ループは，最内のループＩ内にのみ，２次元の配列を持つ演算の実行文を有するタイトなループであるので，処理対象ループ解析部１００は，図３０に示す最適化対象ループをそのままブロッキング対象ループとする。配列解析部１１０は，３つの配列を抽出する。アクセスパターン解析部１２０は，抽出された配列Ｃ（Ｋ，Ｊ）のアクセスパターンがクロスであるので，図３０に示す最適化対象ループに対するブロッキングによる最適化が有効であると判定する。
【０２３１】
抽出された３つの配列の型は，すべてｒｅａｌ（配列の型サイズは８バイト）で宣言されているものとする。また，図３０に示す最適化対象ループは，ループＪに対するブロッキング抑止の最適化指示行を含んでいる。３つの配列のうちの１つは，すべてブロッキング抑止の対象となっていない，ブロッキング対象ループに含まれるループの制御変数を添え字とする，２次元の配列である。３つの配列のうちの２つは，ブロッキング抑止の対象となっているループの制御変数を１つ含む，すべてブロッキング対象ループに含まれるループの制御変数を添え字とする，２次元の配列である。メモリサイズ計算式生成部１３０は，メモリサイズ計算式８ｎ2 ＋１６ｎを生成する。
【０２３２】
キャッシュサイズとして，１３１０７２バイトが取得されたものとする。分割ブロック長計算部１４０は，メモリサイズ計算式８ｎ2 ＋１６ｎに８の倍数を小さい値から順に入力していく。分割ブロック長計算部１４０は，メモリサイズ計算式８ｎ2 ＋１６ｎから得られるメモリサイズが，キャッシュサイズを超えない最大のｎを，自動計算された分割ブロック長として，決定する。ここでは，ｎ＝１２０のときに得られるメモリサイズ１１７１２０バイトが，キャッシュサイズを超えない最大のメモリサイズとなる。
【０２３３】
ブロッキング指示部１５０は，得られた値１２０を自動計算される分割ブロック長として，最適化実行部１７に指示する。最適化実行部１７は，自動計算された分割ブロック長ｂｌｏｃｋ＝１２０を用いて，図３０に示す最適化対象ループに対するブロッキングによる最適化を実行する。このとき，最適化実行部１７は，ブロッキング抑止の対象となっているループＪに対しては，ブロッキングによる最適化を実行しない。図３０に示す最適化対象ループに対するブロッキングによる最適化の実行結果として，図３０に示すブロッキング後ループが得られる。
【０２３４】
このように，本実施の形態のブロッキングによる最適化の技術によって，あらかじめブロッキング抑止が指示されたループを除いた，最適化対象ループに対するブロッキングによる最適化が可能となる。
【０２３５】
図３１は，本実施の形態のブロッキングによる最適化を固定の分割ブロック長の最適化指示行を含む多重ループに対して実行した例である。
【０２３６】
図３１に示す最適化対象ループは，ループＫ，ループＪ，ループＩからなる。図３１に示す最適化対象ループは，最内のループＩ内にのみ，２次元の配列を持つ演算の実行文を有するタイトなループであるので，処理対象ループ解析部１００は，図３１に示す最適化対象ループをそのままブロッキング対象ループとする。配列解析部１１０は，３つの配列を抽出する。アクセスパターン解析部１２０は，抽出された配列Ｃ（Ｋ，Ｊ）のアクセスパターンがクロスであるので，図３１に示す最適化対象ループに対するブロッキングによる最適化が有効であると判定する。
【０２３７】
抽出された３つの配列の型は，すべてｒｅａｌ（配列の型サイズは８バイト）で宣言されているものとする。また，図３１に示す最適化対象ループは，ループＪに対して固定の分割ブロック長（値４８）を指示した最適化指示行を含んでいる。３つの配列のうちの１つは，すべて固定の分割ブロック長が指示されていない，ブロッキング対象ループに含まれるループの制御変数を添え字とする，２次元の配列である。３つの配列のうちの２つは，固定の分割ブロック長が指示されたループの制御変数を１つ含む，すべてブロッキング対象ループに含まれるループの制御変数を添え字とする，２次元の配列である。メモリサイズ計算式生成部１３０は，メモリサイズ計算式８ｎ2 ＋７６８ｎを生成する。
【０２３８】
キャッシュサイズとして，１３１０７２バイトが取得されたものとする。分割ブロック長計算部１４０は，メモリサイズ計算式８ｎ2 ＋７６８ｎに８の倍数を小さい値から順に入力していく。分割ブロック長計算部１４０は，メモリサイズ計算式８ｎ2 ＋７６８ｎから得られるメモリサイズが，キャッシュサイズを超えない最大のｎを，自動計算された分割ブロック長として，決定する。ここでは，ｎ＝８８のときに得られるメモリサイズ１２９５３６バイトが，キャッシュサイズを超えない最大のメモリサイズとなる。
【０２３９】
ブロッキング指示部１５０は，得られた値８８を自動計算される分割ブロック長として，最適化実行部１７に指示する。最適化実行部１７は，自動計算された分割ブロック長ｂｌｏｃｋ＝８８を用いて，図３１に示す最適化対象ループに対するブロッキングによる最適化を実行する。このとき，最適化実行部１７は，固定の分割ブロック長が指示されたループＪに対しては，その指示された固定の分割ブロック長の値４８を用いて，ブロッキングによる最適化を実行する。図３１に示す最適化対象ループに対するブロッキングによる最適化の実行結果として，図３１に示すブロッキング後ループが得られる。
【０２４０】
このように，本実施の形態のブロッキングによる最適化の技術によって，あらかじめ固定の分割ブロック長が指示されたループにはそれを用いて，それ以外のループには自動計算された分割ブロック長を用いて，最適化対象ループに対するブロッキングによる最適化が可能となる。
【０２４１】
以上説明した本実施の形態の最適化処理部１５による処理は，コンピュータが備えるＣＰＵ，メモリ等のハードウェアとソフトウェアプログラムとにより実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録することも，ネットワークを通して提供することも可能である。
【０２４２】
以上，本実施の形態について説明したが，本発明はその主旨の範囲において種々の変形が可能であることは当然である。
【符号の説明】
【０２４３】
１  コンピュータ
２  ＣＰＵ
３  メモリ
４  ＨＤＤ
５  入力装置
６  表示装置
１０  コンパイラ
１１  ソースプログラム入力部
１２  入出力制御部
１３  中間言語生成部
１４  中間言語記憶部
２００  ループデータ記憶部
１５  最適化処理部
１６  ソース解析部
１００  処理対象ループ解析部
１１０  配列解析部
１２０  アクセスパターン解析部
１３０  メモリサイズ計算式生成部
１４０  分割ブロック長計算部
１５０  ブロッキング指示部
１６０  配列情報記憶部
１７０  配列別メモリ計算情報記憶部
１８０  メモリサイズ計算情報記憶部
１７  最適化実行部
１８  コード生成部
１９  オブジェクトファイル出力部
２０  記憶部
２１  ソースプログラム
２２  オブジェクトファイル
２３  実行ファイル
３０  リンカ
４０  オペレーティングシステム
【図１】
0005402746.tif 000002
【図２】
0005402746.tif 000003
【図３】
0005402746.tif 000004
【図４】
0005402746.tif 000005
【図５】
0005402746.tif 000006
【図６】
0005402746.tif 000007
【図７】
0005402746.tif 000008
【図８】
0005402746.tif 000009
【図９】
0005402746.tif 000010
【図１０】
0005402746.tif 000011
【図１１】
0005402746.tif 000012
【図１２】
0005402746.tif 000013
【図１３】
0005402746.tif 000014
【図１４】
0005402746.tif 000015
【図１５】
0005402746.tif 000016
【図１６】
0005402746.tif 000017
【図１７】
0005402746.tif 000018
【図１８】
0005402746.tif 000019
【図１９】
0005402746.tif 000020
【図２０】
0005402746.tif 000021
【図２１】
0005402746.tif 000022
【図２２】
0005402746.tif 000023
【図２３】
0005402746.tif 000024
【図２４】
0005402746.tif 000025
【図２５】
0005402746.tif 000026
【図２６】
0005402746.tif 000027
【図２７】
0005402746.tif 000028
【図２８】
0005402746.tif 000029
【図２９】
0005402746.tif 000030
【図３０】
0005402746.tif 000031
【図３１】
0005402746.tif 000032