(57)【要約】【課題】  コンパイルまたはリンク時に，メモリアクセスする命令の構造体のアクセスパターンから，該構造体の要素の配列上の配置を変更できるようにする。【解決手段】  コンパイル処理装置１のコンパイル処理手段１１またはリンク手段１２の処理の際に，アクセスパターン取得部１３が，入力プログラムの解析結果からメモリアクセスする命令を解析し，構造体要素の配列上の配置，アクセス回数，アクセス順序を含むアクセスパターンを取得する。アクセスパターン変更部１４が，アクセスパターンに基づいて，構造体の要素の配列上の配置を変更する。【選択図】  図１
2010003031.tif 000002
【特許請求の範囲】
【請求項１】
プログラムのコンパイル処理またはリンク処理またはこれらの処理を行うコンパイル処理装置において，
入力されたプログラムの解析結果から，メモリアクセスする命令のアクセス動作を解析し，命令に関連する構造体の要素の配列上の配置，アクセス回数およびアクセス順序を含むアクセスパターンを取得するアクセスパターン取得部と，
前記アクセスパターンに基づいて，前記構造体の要素の配列上の配置を変更するアクセスパターン変更部とを備える
ことを特徴とするコンパイル処理装置。
【請求項２】
前記アクセスパターン変更部は，前記アクセスパターンのアクセス順序に基づいて，アクセスする構造体要素を，前記配列の先頭から連続する領域に割り付ける
ことを特徴とする請求項１記載のコンパイル処理装置。
【請求項３】
前記アクセスパターン変更部は，前記アクセスパターンのアクセス回数に基づいて，アクセス回数の高い構造体の要素を，前記配列の先頭の領域から優先して割り付ける
ことを特徴とする請求項１または請求項２に記載のコンパイル処理装置。
【請求項４】
前記アクセスパターン変更部は，前記構造体が関連する複数の関数内で，アクセスする構造体の要素に偏りがある場合に，該関数各々の処理内でアクセスする構造体の要素のみを前記配列の先頭から連続する領域に割り付け，該関数に関連する構造体の情報の同期処理を付加する
ことを特徴とする請求項１または請求項３のいずれか一項に記載のコンパイル処理装置。
【請求項５】
前記アクセスパターン変更部は，前記構造体が関連するループ処理内で，アクセスする構造体の要素に偏りがある場合に，該ループ処理内でのみ，アクセス回数が多い構造体の要素を前記配列の先頭から連続する領域に割り付ける
ことを特徴とする請求項１または請求項３のいずれか一項に記載のコンパイル処理装置。
【請求項６】
前記アクセスパターン取得部および前記アクセスパターン変更部は，前記コンパイル処理または前記リンク処理のいずれか一方の処理が実行されている間に起動および実行される
ことを特徴とする請求項１ないし請求項５のいずれか一項に記載のコンパイル処理装置。
【請求項７】
コンピュータが，プログラムのコンパイル処理またはリンク処理またはこれらの処理を行う間に実行するアクセスパターン変更処理方法であって，
入力されたプログラムの解析結果から，メモリアクセスする命令のアクセス動作を解析し，命令に関連する構造体の要素の配列上の配置，アクセス回数およびアクセス順序を含むアクセスパターンを取得するアクセスパターン取得処理過程と，
前記アクセスパターンに基づいて，前記構造体の要素の配列上の配置を変更するアクセスパターン変更処理過程とを備える
ことを特徴とするアクセスパターン変更処理方法。
【請求項８】
プログラムのコンパイル処理またはリンク処理またはこれらの処理を行うコンピュータを，
入力されたプログラムの解析結果から，メモリアクセスする命令のアクセス動作を解析し，命令に関連する構造体の要素の配列上の配置，アクセス回数およびアクセス順序を含むアクセスパターンを取得するアクセスパターン取得部と，
前記アクセスパターンに基づいて，前記構造体の要素の配列上の配置を変更するアクセスパターン変更部とを備えるコンパイル処理装置として機能させる
ことを特徴とするアクセスパターン変更処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，プログラムのコンパイル処理装置，ならびにアクセスパターン変更処理方法および処理プログラムに関するものである。より詳しくは，本発明は，プログラムのコンパイル処理またはリンク処理時に実行され，プログラムの動的データ構造の解析結果を用いてメモリアクセスを伴う構造体のアクセスパターンを取得し，該構造体の要素の配列上の位置を変更する処理を実現する処理に関する。
【背景技術】
【０００２】
プログラムのコンパイル処理やリンク処理における，配列要素の割り当て処理に関する従来技術として，ソースプログラム内の配列要素の参照順序と参照回数とを保持し，配列要素のインデックスを参照順序に合わせて入れ替え，連続領域になるように割り当てる方法が知られている（例えば，特許文献１参照）。
【０００３】
また，プログラムを一度予備的に実行し，プログラム内の配列要素へのアクセスパターンのグラフを作成し，アクセス数の大きい配列要素を活性化レコードの基底アドレスに近い位置に配置させ，または，アクセスが時間的に接近している複数の配列要素を同一キャッシュライン上に割り付ける方法が知られている（例えば，特許文献２参照）。
【０００４】
また，プログラム実行時にディスク・アクセスを監視し，アクセス回数の多いアドレス・ブロックをキャッシュメモリに常駐させる方法が知られている（例えば，特許文献３参照）。
【０００５】
キャッシュメモリ（キャッシュ）は，記憶装置の中で最も高速な記憶装置であり，使用頻度の高いデータを記憶させることで，データの読み込みを最適化することができる。
【特許文献１】特開平４−７７４８号公報
【特許文献２】特開平９−２１２３６９号公報
【特許文献３】特公平７−１０１４０２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
プログラムコンパイル処理装置において，例えば，図１５（Ａ）に示すＦｏｒｔｒａｎ言語によって記述されたプログラム例のように，構造体へのポインタを要素（ｃｈｉｌｄ１，ｃｈｉｌｄ２）に持つ構造体へアクセスする場合を考える。
【０００７】
このときに，構造体（ｓｔｒｕｃｔ）は，構造体の型が定義された入力プログラム［ｓｔｒｕｃｔ］ではなく，別の入力プログラム［ｍａｉｎ．ｆ９０］中で参照されるとする。図１５（Ｂ）に示すように，構造体（ｓｔｒｕｃｔ）は，配列（ｐａｒｅｎｔ）のｎ個分の要素としてアロケートされる。また，配列の要素となる構造体（ｓｔｒｕｃｔ）は，それぞれ，異なる構造体へのポインタを要素として持ち，定義された順に先頭の要素から順に参照するものとする。
【０００８】
図１５（Ｂ）は，構造体（ｓｔｒｕｃｔ）が割り当てられた配列（ｐａｒｅｎｔ）例を示す図である。図１５（Ｂ）に示す配列の横一列の矩形の連なりは，一つの構造体を表す。各矩形は，構造体が持つ成分（構造体要素）が割り当てられる領域を表す。
【０００９】
この配列（ｐａｒｅｎｔ）では，ｎ個の構造体の各構造体要素ｃｈｉｌｄ１，ｃｈｉｌｄ２，ｎｕｍ１の領域が，「ｃｈｉｌｄ１＿１，ｃｈｉｌｄ２＿１，ｎｕｍ１＿１，ｃｈｉｌｄ１＿２，ｃｈｉｌｄ２＿２，ｎｕｍ１＿２，…」という順序で確保される。
【００１０】
ここで，図１５（Ａ）のプログラム［ｍａｉｎ．ｆ９０］で，構造体要素ｃｈｉｌｄ１の領域「ｃｈｉｌｄ１＿１，ｃｈｉｌｄ１＿２，ｃｈｉｌｄ１＿３，…，ｃｈｉｌｄ１＿ｎ」を連続的にアクセスしようとする。
【００１１】
図１５（Ｂ）の配列では，構造体要素ｃｈｉｌｄ１が連続する領域に確保されていないことから，構造体要素ｃｈｉｌｄ１の領域が１次キャッシュにキャッシュされない可能性がある。
【００１２】
このように，配列上で，連続アクセスする構造体要素が連続領域として確保されない場合には，同時にキャッシュされない状態が生じうる。そのため，キャッシュメモリの使用効率を低下させるだけでなく，プログラムの実行性能を低下させる。
【００１３】
本発明の目的は，かかる問題に鑑みてなされたものであり，その目的は，プログラムのコンパイル処理またはリンク処理の際に，プログラムの動的データ構造を解析し，メモリアクセスを行う命令の構造体へのアクセスパターンを取得し，このアクセスパターンに基づいて，該構造体の要素を割り付ける配置を変更できるようにするプログラムコンパイル処理装置を提供することである。
【００１４】
また，本発明の別の目的は，前記プログラムコンパイル処理装置が実行するアクセスパターン変更処理方法，および，コンピュータを前記該アクセスパターン変更処理方法によって実行される処理の処理手段を備える処理装置として機能させるためのアクセスパターン変更処理プログラムを提供することである。
【課題を解決するための手段】
【００１５】
開示する処理装置は，プログラムのコンパイル処理またはリンク処理を行うコンパイル処理装置であって，入力されたプログラムの解析結果から，メモリアクセスする命令のアクセス動作を解析し，命令に関連する構造体の要素各々の配列上の配置，アクセス回数およびアクセス順序を含むアクセスパターンを取得するアクセスパターン取得部と，このアクセスパターンに基づいて，構造体の要素の配列上の配置を変更するアクセスパターン変更部とを備える。
【００１６】
アクセスパターン変更部は，アクセスパターンのアクセス順序に基づいて，アクセスする構造体の要素を，配列の先頭から連続する領域に割り付けることができる。これにより，連続してアクセスする構造体要素の領域が一次キャッシュに同時にキャッシュされる可能性がより高くなり，キャッシュメモリの使用効率が向上し，プログラムの実行性能も向上する。
【００１７】
また，アクセスパターン変更部は，アクセスパターンのアクセス回数に基づいて，アクセス回数の高い構造体の要素を，配列の先頭の領域から優先して割り付けることができる。これにより，高頻度でアクセスされる構造体要素が優先的に一次キャッシュにキャッシュされる可能性がより高くなる。よって，キャッシュメモリの使用効率が向上し，プログラムの実行性能も向上する。
【発明の効果】
【００１８】
開示する処理装置によれば，アクセス順序やアクセス回数に基づいて，アクセスする構造体の要素が一次キャッシュ上に同時にキャッシュされる可能性がきわめて高くなるため，キャッシュメモリの使用効率，ひいてはプログラムの実行性能の向上を図ることができる。
【発明を実施するための最良の形態】
【００１９】
図１は，本発明の実施の形態における構成例を示す図である。
【００２０】
コンパイル処理装置１は，コンパイル処理手段１１，リンク手段１２，アクセスパターン取得部１３およびアクセスパターン変更部１４を備える。
【００２１】
コンパイル処理手段１１は，ソース解析部１１１，最適化部１１３，およびコード生成部１１５を備え，ソースプログラムのコンパイル処理を行い，オブジェクトファイルを生成する。ソース解析部１１１，最適化部１１３，およびコード生成部１１５は既知手法による処理を実行するものであり，各処理の説明を省略する。
【００２２】
リンク手段１２は，コンパイル処理手段１１が生成したオブジェクトファイルのリンク処理を行い，実行ファイルを生成する。
【００２３】
アクセスパターン取得部１３は，入力されたプログラムの解析結果から，メモリアクセスする命令のアクセス動作を解析し，この命令の構造体の要素（構造体要素）各々の配列上の配置，アクセス回数およびアクセス順序を含むアクセスパターンを取得する。
【００２４】
アクセスパターン変更部１４は，アクセスパターンに基づいて，アクセスパターンの該構造体要素の配置を変更する。
【００２５】
アクセスパターン変更部１４は，アクセスパターンのアクセス順序またはアクセス回数に基づいて，アクセスする構造体要素を，配列の先頭から連続する領域に割り付け，この割り付けに基づいてアクセスパターンの構造体要素の配置を変更する。
【００２６】
例えば，アクセスパターンのアクセス順序に基づいて，アクセスする構造体要素を，配列の先頭から連続する領域に割り付ける
または，アクセスパターンのアクセス回数に基づいて，アクセス回数の高い構造体要素を，前記配列の先頭の領域から優先して割り付ける。
【００２７】
または，構造体が関連する複数の関数内で，アクセスする構造体要素に偏りがある場合に，関数各々の処理内でアクセスする構造体要素のみを，配列の先頭から連続する領域に割り付け，その関数に関連する構造体の情報の同期処理を付加する。
【００２８】
または，構造体が関連するループ処理内で，アクセスする構造体要素に偏りがある場合に，そのループ処理内でのみ，アクセス回数が多い構造体要素を，配列の先頭から連続する領域に割り付ける。
【００２９】
アクセスパターン取得部１３およびアクセスパターン変更部１４は，コンパイル処理手段１１またはリンク手段１２と協働して処理を実行することができる。
【００３０】
以下に，コンパイル処理装置１におけるアクセスパターン取得処理および変更処理について，より詳細に説明する。以下の例では，アクセスパターン取得処理および変更処理が，リンク手段１２の最適化処理の際に実行されるものとする。
【００３１】
〔第１の処理例〕
第１の処理例では，図１５（Ａ）に示すプログラムを処理対象とする。
【００３２】
アクセスパターン取得部１３は，コンパイル処理手段１１によって生成されたオブジェクトファイルの解析結果から，動的データ構造を解析し，メモリアクセスする命令を検出し，そのアクセス動作を解析してアクセスパターンを取得する。
【００３３】
図１５（Ａ）のプログラムの「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ１％ｎｕｍ１」がメモリアクセスを行う命令である。この命令のアクセス動作を解析し，図１５（Ｂ）に示すように，構造体ｓｔｒｕｃｔの構造体要素ｃｈｉｌｄ１，ｃｈｉｌｄ２，ｎｕｍ１の配列上の配置が，配列の先頭から何バイトの位置に割り付けられるかを特定する。さらに，各構造体のアクセス回数およびアクセス順序を解析する。これらの解析情報を，アクセスパターンとして取得する。
【００３４】
次に，アクセスパターン変更部１４は，アクセスパターンのアクセス順序に基づいて，連続してアクセスする構造体要素が，配列の連続する領域に割り付けられるように，構造体要素の配置を変更する。
【００３５】
図２に，構造体要素の割り付け変更例を示す。
【００３６】
図２に示すように，まず，構造体ｓｔｒｕｃｔの構造体要素ｃｈｉｌｄ１の「ｃｈｉｌｄ１＿１，ｃｈｉｌｄ１＿２，…，ｃｈｉｌｄ１＿ｎ」の領域が，配列の先頭から順に連続的に割り付けられる。続けて，構造体要素ｃｈｉｌｄ２の「ｃｈｉｌｄ２＿１，ｃｈｉｌｄ２＿２，…，ｃｈｉｌｄ２＿ｎ」の領域，ｎｕｍ１の「ｎｕｍ１＿１，ｎｕｍ１＿２，…，ｎｕｍ１＿ｎ」の領域が，次の位置から連続的に割り付けられる。
【００３７】
リンク手段１２では，領域の割り付け位置が変更されたアクセスパターンに基づいて最適化処理を行う。
【００３８】
これにより，アクセスが連続する構造体要素は，キャッシュの連続した領域に割り当てられ，一次キャッシュに同時にキャッシュされる可能性が高くなる。よって，キャッシュメモリの使用効率およびプログラムの実行性能を向上させることができる。
【００３９】
また，第１の処理例では，後述する処理例のように処理のオーバーヘッドを生ずるおそれがない。
【００４０】
〔第２の処理例〕
第２の処理例では，図３に示すプログラムを処理対象とする。
【００４１】
アクセスパターン取得部１３は，第１の処理例と同様に，図１５のプログラムについて，メモリアクセスする命令のアクセスパターンを取得する。
【００４２】
図３に示すプログラムでは，関数「ｃａｌｌ  ｓｕｂ１（）」内の「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ１％ｎｕｍ１」と，関数「ｃａｌｌ  ｓｕｂ２（）」内の「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ２％ｎｕｍ１」がメモリアクセスを行う命令である。
【００４３】
２つの関数において，命令に対応する同一の構造体ｓｔｒｕｃｔのアクセスパターンは異なる。
【００４４】
この場合には，各命令での構造体ｓｔｒｕｃｔのアクセスパターンを取得し，部分的に変更することによって，アクセスパターンを最適化できる。また，プログラム全体でのアクセス動作の解析が不要となる。
【００４５】
しかし，構造体が多重化するため，同期処理を行う必要がある。
【００４６】
アクセスパターン変更部１４は，関数内で，構造体ｓｔｒｕｃｔの構造体要素のアクセスに偏りがあるかを調べる。
【００４７】
関数「ｃａｌｌ  ｓｕｂ１（）」での命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ１％ｎｕｍ１」では，構造体要素ｃｈｉｌｄ１，ｎｕｍ１のみアクセスし，構造体要素ｃｈｉｌｄ２にはアクセスしないという偏りがある。同様に，関数「ｃａｌｌ  ｓｕｂ１（）」での命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ２％ｎｕｍ１」では，構造体要素ｃｈｉｌｄ２，ｎｕｍ１のみアクセスするという偏りがある。
【００４８】
そこで，アクセスパターン変更部１４は，関数内で，アクセスする構造体要素のみを要素として定義する構造体を作成する。
【００４９】
図４は，図３のプログラムの命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ１％ｎｕｍ１」と「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ２％ｎｕｍ１」とにおける構造体要素の偏りに基づいて，構造体ｓｔｒｕｃｔが作成された状態を示す図である。
【００５０】
図４のプログラムの破線の矩形の部分ｐ１に示すように，命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ１％ｎｕｍ１」に対応して，構造体要素ｃｈｉｌｄ１，ｎｕｍ１のみを要素とする構造体ｓｔｒｕｃｔの定義を作成している。また，破線の矩形の部分p２に示すように，命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ２％ｎｕｍ１」についても，同様に構造体ｓｔｒｕｃｔの定義を作成している。
【００５１】
アクセスパターン変更部１４は，これらの関数内で，作成した構造体ｓｔｒｕｃｔのアクセスパターンに基づいて，その構造体要素のみについて配列上の領域の割り付けを行う。ここで，第１の処理例と同様の処理を行って配列上の配置の割り付けを変更する。
【００５２】
図５（Ａ）および（Ｂ）は，それぞれ，命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ１％ｎｕｍ１」と命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ２％ｎｕｍ１」に対応する配列の構造体要素の割り付けの変更例を示す図である。
【００５３】
図５（Ａ）の配列では，構造体要素ｃｈｉｌｄ１，ｎｕｍ１のみを参照するため，配列の要素として，構造体要素ｃｈｉｌｄ１の「ｃｈｉｌｄ１＿１，ｃｈｉｌｄ１＿２，…，ｃｈｉｌｄ１＿ｎ」の領域分と構造体要素ｎｕｍ１の「ｎｕｍ１＿１，ｎｕｍ１＿２，…，ｎｕｍ１＿ｎ」の領域分のみが割り付けられる。
【００５４】
また，図５（Ｂ）の配列では，構造体要素ｃｈｉｌｄ２，ｎｕｍ１のみを参照するため，配列の要素として，構造体要素ｃｈｉｌｄ２の「ｃｈｉｌｄ２＿１，ｃｈｉｌｄ２＿２，…，ｃｈｉｌｄ２＿ｎ」の領域分と構造体要素ｎｕｍ１の「ｎｕｍ１＿１，ｎｕｍ１＿２，…，ｎｕｍ１＿ｎ」の領域分のみが割り付けられる。
【００５５】
このように，定義されているがアクセスしない不要な構造体要素を除去したアクセスパターンに変更して，配列上の構造体要素の配置を変更することができるため，キャッシュメモリの無駄な領域の割り当てを止めることができる。
【００５６】
第２の処理例では，構造体ｓｔｒｕｃｔが多重化されるため，複数の構造体間で情報の同期をとる必要がある。
【００５７】
アクセスパターン変更部１４は，本来の構造体ｓｔｒｕｃｔの構造体要素を配列として保持し，作成した構造体の構造体要素の値が変化した場合に，これらの情報の同期をとる。同期処理は，以下の３つのいずれかの処理方法で行われる。
【００５８】
図６は，第１の同期方法による同期処理例を示す図である。
【００５９】
アクセスパターン変更部１４は，第１の同期方法として，マスタ構造体ｓｔｒｕｃｔ＿ｍａｓｔｅｒＡを生成し，マスタ構造体の情報を，多重化した構造体ｓｔｒｕｃｔＡ１，ｓｔｒｕｃｔＡ２の全てに写像する。マスタ構造体ｓｔｒｕｃｔ＿ｍａｓｔｅｒＡを介して各構造体の情報の同期をとることができる。
【００６０】
図７は，第２の同期方法による同期処理例を示す図である。
【００６１】
アクセスパターン変更部１４は，第２の同期方法として，構造体の更新があったときに，更新された情報を，多重化した構造体各々に写像する。構造体ｓｔｒｕｃｔＡ１の情報が更新された場合に，更新された情報を構造体ｓｔｒｕｃｔＡ２，ｓｔｒｕｃｔＡ３，ｓｔｒｕｃｔＡ４，ｓｔｒｕｃｔＡ５にそれぞれ写像する。また，構造体ｓｔｒｕｃｔＡ２の情報が更新された場合に，更新された情報を構造体ｓｔｒｕｃｔＡ１，ｓｔｒｕｃｔＡ３，ｓｔｒｕｃｔＡ４，ｓｔｒｕｃｔＡ５にそれぞれ写像する。更新のたびに全ての構造体の情報が写像され，同期をとることができる。
【００６２】
図８は，第３の同期方法による同期処理例を示す図である。
【００６３】
アクセスパターン変更部１４は，第３の同期方法として，更新が生じた構造体をマスタとして設定し，更新された情報を他の構造体へ順次写像する。
【００６４】
構造体ｓｔｒｕｃｔＡ１の情報が更新された場合に，構造体ｓｔｒｕｃｔＡ１をマスタと設定し，更新された情報を構造体ｓｔｒｕｃｔＡ２に写像する。次に，構造体ｓｔｒｕｃｔＡ２の情報が更新されるので，構造体ｓｔｒｕｃｔＡ２がマスタとなり，更新された情報を構造体ｓｔｒｕｃｔＡ３に写像する。さらに，構造体ｓｔｒｕｃｔＡ３の更新された情報が，同様にして，構造体ｓｔｒｕｃｔＡ４に写像される。
【００６５】
情報の更新を契機に，構造体の情報が次の構造体に写像され，全体の同期をとることができる。
【００６６】
〔第３の処理例〕
第３の処理例では，図１５に示すプログラムを処理対象とする。
【００６７】
アクセスパターン取得部１３は，第１の処理例と同様に，図１５のプログラムについて，メモリアクセスする命令のアクセスパターンを取得する。
【００６８】
ループ処理内にある命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ１％ｎｕｍ１」では，対応する構造体の構造体要素ｃｈｉｌｄ１，ｎｕｍ１のみアクセスし，構造体要素ｃｈｉｌｄ２へアクセスしていない。したがって，アクセスする構造体要素を配列上で優先的に割り当てることによって，最適化することができる。
【００６９】
アクセスパターン変更部１４は，図１５に示すプログラムでループ処理内にある命令「ｐａｒｅｎｔ（ｉ）％ｃｈｉｌｄ１％ｎｕｍ１」の構造体のアクセスパターンから，アクセスする順に構造体要素を並べ替えて，構造体要素ｃｈｉｌｄ１，ｎｕｍ１，ｃｈｉｌｄ２とする。
【００７０】
さらに，アクセスパターン変更部１４は，作業用構造体として，配列ｐａｒｅｎｔの作業用配列ｐａｒｅｎｔ＿ｔｍｐを作成し，アクセスパターンのアクセス回数に基づいて並べ替えた構造体要素の順に，その領域分を，配列の先頭から順に連続する領域に割り付ける。
【００７１】
図９は，図１５（Ａ）のプログラムにおいて，構造体要素が並べ替えられた構造体と，配列ｐａｒｅｎｔの作業用配列ｐａｒｅｎｔ＿ｔｍｐとを付加した状態例を示す図である。
【００７２】
作業用構造体ｐａｒｅｎｔ＿ｔｍｐでは，置き換えられた順序に従って，各構造体要素の領域分が割り付けられる。また，ループ処理の終了時には，作業用配列ｐａｒｅｎｔ＿ｔｍｐの情報が，配列ｐａｒｅｎｔに写像される。
【００７３】
図１０は，作業用配列ｐａｒｅｎｔ＿ｔｍｐにおける構造体要素の割り付けの変更例を示す。
【００７４】
図１０に示すように，構造体の置き換えられた順序に従って，構造体要素ｃｈｉｌｄ１の「ｃｈｉｌｄ１＿１，ｃｈｉｌｄ１＿２，…，ｃｈｉｌｄ１＿ｎ」の領域分を作業用配列の先頭から連続する領域に割り付ける。続けて，構造体要素ｎｕｍ１の「ｎｕｍ１＿１，ｎｕｍ１＿２，…，ｎｕｍ１＿ｎ」の領域分を連続する領域に割り付ける。最後に，構造体要素ｃｈｉｌｄ２の「ｃｈｉｌｄ２＿１，ｃｈｉｌｄ２＿２，…，ｃｈｉｌｄ２＿ｎ」の領域分を，次の位置から連続する領域に割り付ける。
【００７５】
ループ処理内において，構造体要素のアクセス回数が多い順に，配列の領域を割り付けることによって，アクセス回数が多い構造体要素の領域が優先して一次キャッシュにキャッシュされる可能性が高くなる。そのため，キャッシュメモリの使用効率およびプログラム実行性能を向上させることができる。
【００７６】
以下に，アクセスパターン取得部１３およびアクセスパターン変更部１４の処理フローを説明する。
【００７７】
図１１は，アクセスパターン取得部１３の処理フローを示す図である。
【００７８】
アクセスパターン取得部１３は，入力されたプログラム（オブジェクトファイル）の解析結果から，メモリアクセスする命令を検出し（ステップＳ１），検出した命令に関連する構造体要素の型情報を取得する（ステップＳ２）。さらに，各構造体要素の配列上の位置（先頭からの何バイト先にあるかという配置）を取得する（ステップＳ３）。プログラムの制御から動的データフローを解析し，構造体要素のアクセス順序，アクセス回数を解析する（ステップＳ４）。構造体要素の配置，アクセス順序，アクセス回数などを含むアクセスパターンを取得する（ステップＳ５）。
【００７９】
図１２は，第１の処理例におけるアクセスパターン変更部１４の処理フローを示す図である。
【００８０】
アクセスパターン変更部１４は，入力プログラムのメモリアクセスする命令を検出し（ステップＳ１１），アクセスパターンから，命令が所定の条件を満たしているかを判断する（ステップＳ１２）。例えば，以下の条件を設定しておく。
【００８１】
「条件：ループ処理内に配列（構造体）のアクセスがあり，かつ，その配列のアクセスが一部分の領域にのみアクセスしている。」
この命令が，前記の条件を満たす場合にのみ（ステップＳ１２のＹＥＳ），命令の各構造体が，別の構造体へのポインタを要素として持っているかを判断する（ステップＳ１３）。
【００８２】
構造体が別の構造体へのポインタを要素として持つ場合にのみ（ステップＳ１３のＹＥＳ），アクセスパターンのアクセス順序に基づいて，アクセスする構造体要素の領域分を配列の先頭から連続して割り付ける（ステップＳ１４）。
【００８３】
図１３は，第２の処理例におけるアクセスパターン変更部１４の処理フローを示す図である。
【００８４】
ステップＳ２１〜Ｓ２２の処理は，図１２のステップＳ１１〜１２の処理と同様であるので，説明を省略する。
【００８５】
アクセスパターン変更部１４は，前記の条件の場合にのみ（ステップＳ２２のＹＥＳ），関数内で，アクセスする構造体要素に偏りがあるかをそれぞれ判定する（ステップＳ２３）。関数内で，アクセスする構造体要素に偏りがあると判断した場合にのみ（ステップＳ３３のＹＥＳ），その関数内で使用する構造体要素のみを要素とする構造体を，関数内の先頭部分に作成する（ステップＳ２４）。
【００８６】
さらに，アクセスパターンのアクセス順序に基づいて，アクセスする構造体要素の領域分を配列の先頭から連続して割り付ける（ステップＳ２５）。
【００８７】
さらに，多重化した構造体の情報の同期処理を付加する（ステップＳ２６）。
【００８８】
図１４は，第３の処理例におけるアクセスパターン変更部１４の処理フローを示す図である。
【００８９】
ステップＳ３１〜Ｓ３２の処理は，図１２のステップＳ１１〜１２の処理と同様であるので，説明を省略する。
【００９０】
アクセスパターン変更部１４は，前記の条件の場合にのみ（ステップＳ３２のＹＥＳ），ループ処理内で，アクセスする構造体要素に偏りがあるかをそれぞれ判定する（ステップＳ３３）。ループ処理内で，アクセスする構造体要素に偏りがあると判断した場合にのみ（ステップＳ３３のＹＥＳ），ループ処理前で，元の配列に対応する作業用配列（構造体）を作成し（ステップＳ３４），アクセスパターンのアクセス回数に基づいて，アクセス回数が多い構造体要素の領域分を作業用配列の先頭から連続して割り付ける（ステップＳ３５）。その後，ループ処理の終了時に，作業用配列の情報を元の配列に写像する（ステップＳ３６）。
【００９１】
以上，本発明をその実施の形態により説明したが，本発明はその主旨の範囲において種々の変形が可能であることは当然である。
【００９２】
また，本形態において開示するコンパイラ処理装置は，コンピュータによって読み取られ実行されるプログラムとして実施することができる。このプログラムは，コンピュータが読み取り可能な，可搬媒体メモリ，半導体メモリ，ハードディスクなどの適当な記録媒体に格納することができ，これらの記録媒体に記録して提供され，または，通信インタフェースを介して種々の通信網を利用した送受信により提供されうるものである。
【図面の簡単な説明】
【００９３】
【図１】本発明の実施の形態における構成例を示す図である。
【図２】第１の処理例における構造体要素の割り付けの変更例を示す図である。
【図３】第２の処理例における処理対象のプログラム例を示す図である。
【図４】図３のプログラムにおいて，各命令に対応して構造体の定義が作成され，構造体が多重化された状態例を示す図である。
【図５】第２の処理例における，部分ｐ１および部分ｐ２に対応する配列の割り付けの変更例を示す図である。
【図６】第１の同期方法による同期処理の例を示す図である。
【図７】第２の同期方法による同期処理の例を示す図である。
【図８】第３の同期方法による同期処理の例を示す図である。
【図９】第３の処理例において，ループ処理内に構造体要素が並べ替えられた構造体と作業用配列が作成された状態例を示す図である。
【図１０】第３の処理例における作業用配列の割り付けの変更例を示す図である。
【図１１】アクセスパターン取得部の処理フローを示す図である。
【図１２】第１の処理例におけるアクセスパターン変更部の処理フローを示す図である。
【図１３】第２の処理例におけるアクセスパターン変更部の処理フローを示す図である。
【図１４】第３の処理例におけるアクセスパターン変更部の処理フローを示す図である。
【図１５】入力されるプログラム例およびプログラム内のメモリアクセスを行う命令の構造体要素の配列の割り付け例を示す図である。
【符号の説明】
【００９４】
１  コンパイル処理装置
１１  コンパイル処理手段
１２  リンク手段
１３  アクセスパターン取得部
１４  アクセスパターン変更部
１１１  ソース解析部
１１３  最適化部
１１５  コード生成部
【図１】
2010003031.tif 000003
【図２】
2010003031.tif 000004
【図３】
2010003031.tif 000005
【図４】
2010003031.tif 000006
【図５】
2010003031.tif 000007
【図６】
2010003031.tif 000008
【図７】
2010003031.tif 000009
【図８】
2010003031.tif 000010
【図９】
2010003031.tif 000011
【図１０】
2010003031.tif 000012
【図１１】
2010003031.tif 000013
【図１２】
2010003031.tif 000014
【図１３】
2010003031.tif 000015
【図１４】
2010003031.tif 000016
【図１５】
2010003031.tif 000017