(57)【要約】【課題】高速に処理可能なプログラムを生成することができるプログラム生成装置、プログラム生成方法およびプログラムを提供する。【解決手段】プログラム生成装置は、完全ネストループ構造を構成する複数のループで使用するデータのメインメモリ上の配置の候補ごとに、該候補を採用した場合にキャッシュメモリを含む演算装置が複数のループの実行に伴いメインメモリへアクセスする回数に関する指標を算出し、該指標に基づいて、候補の中からデータの配置を決定する配置決定部と、データの配置を採用した完全ネストループ構造を有するプログラムを生成する生成部と、を含む。【選択図】図１
2016110259.tif 000002
【特許請求の範囲】
【請求項１】
完全ネストループ構造を構成する複数のループで使用するデータのメインメモリ上の配置の候補ごとに、当該候補を採用した場合にキャッシュメモリを含む演算装置が前記複数のループの実行に伴い前記メインメモリへアクセスする回数に関する指標を算出し、前記指標に基づいて、前記候補の中から前記データの配置を決定する配置決定部と、
前記データの配置を採用した完全ネストループ構造を有するプログラムを生成する生成部と、を含むプログラム生成装置。
【請求項２】
前記配置決定部は、前記指標に基づいて、前記アクセスの回数が最小となる前記候補を前記データの配置として決定する、請求項１に記載のプログラム生成装置。
【請求項３】
前記アクセスの回数は、前記演算装置での前記複数のループの実行時における前記キャッシュメモリでのキャッシュヒットの増加に応じて減少する、請求項１または２に記載のプログラム生成装置。
【請求項４】
前記複数のループを用いた互いに異なるループネスト順序を列挙する列挙部と、
前記ループネスト順序ごとに、当該ループネスト順序を採用した場合に前記複数のループについてベクトル演算を実行した際に生じる処理の高速化の度合いを算出し、前記ループネスト順序の中から前記高速化の度合いが閾値以上のループネスト順序である該当順序を決定する順序決定部と、を含み、
前記配置決定部は、前記候補ごとに、当該候補を採用した場合に前記演算装置が前記該当順序での前記複数のループの実行に伴い前記メインメモリへアクセスする回数に関する情報を、前記指標として算出し、
前記生成部は、前記該当順序と前記データの配置とを採用した完全ネストループ構造を有するプログラムを生成する、請求項１から３のいずれか１項に記載のプログラム生成装置。
【請求項５】
前記順序決定部は、前記ループネスト順序ごとに、前記ベクトル演算を実行しない場合における当該ループネスト順序で最内のループの回転数と、前記ベクトル演算を実行する場合における前記最内のループの回転数と、の関係に基づいて、前記高速化の度合いを算出する、請求項４に記載のプログラム生成装置。
【請求項６】
前記列挙部は、不完全ネストループ構造を、前記完全ネストループ構造と、単一ループ構造と、に分割し、
前記生成部は、前記該当順序と前記データの配置とを採用した完全ネストループ構造と、前記単一ループ構造と、を有するプログラムを生成する、請求項４または５に記載のプログラム生成装置。
【請求項７】
前記ループ内のステートメントへの処理フローの到達確率を算出する算出部を含み、
前記順序決定部は、前記ループネスト順序ごとに、前記到達確率に基づいて前記高速化の度合いを算出する、請求項４から６のいずれか１項に記載のプログラム生成装置。
【請求項８】
前記ループを途中で打ち切る打ち切り処理の有無を判断する打ち切り処理判断部を含み、
前記列挙部は、前記打ち切り処理が有る場合、前記打ち切り処理が有る場合の前記ループネスト順序と、前記打ち切り処理が無い場合の前記ループネスト順序と、を列挙する、請求項４から７のいずれか１項に記載のプログラム生成装置。
【請求項９】
前記ループネスト順序ごとに、当該ループネスト順序で最内のループの回転数を、前記最内のループの全てを前記ベクトル演算で実行可能な回転数に変更するループ回転数変更部を含む、請求項４から８のいずれか１項に記載のプログラム生成装置。
【請求項１０】
前記ループ内のステートメントへの処理フローの到達確率が既定値以下の場合、当該ステートメントで使用する変数を初期化する初期化ステートメントを、前記変数を使用するステートメントの直前に配置する初期化位置決定部を含む、請求項１から９のいずれか１項に記載のプログラム生成装置。
【請求項１１】
前記配置決定部は、前記ループのうち最内のループのループ誘導変数でアクセスされるデータを前記メインメモリに配置したときに、該データのうちベクトル演算で一度に処理される連続する一群のデータがバイト境界を跨がないように、前記データの数を調整する、請求項１から１０のいずれか１項に記載のプログラム生成装置。
【請求項１２】
プログラム構造とデータ配置が決定済みの原始プログラムを受け付け、前記原始プログラムに多重ループが存在する場合、前記多重ループの各々のループに対応するプログラム情報とループ化情報とを生成する情報生成部を含む、請求項１から１１のいずれか１項に記載のプログラム生成装置。
【請求項１３】
前記複数のループで使用されるデータは、前記複数のループの各ループ誘導変数でアクセスされるデータである、請求項１から１２のいずれか１項に記載のプログラム生成装置。
【請求項１４】
プログラム生成装置が行うプログラム生成方法であって、
完全ネストループ構造を構成する複数のループで使用するデータのメインメモリ上の配置の候補ごとに、当該候補を採用した場合にキャッシュメモリを含む演算装置が前記複数のループの実行に伴い前記メインメモリへアクセスする回数に関する指標を算出し、前記指標に基づいて、前記候補の中から前記データの配置を決定し、
前記データの配置を採用した完全ネストループ構造を有するプログラムを生成する、プログラム生成方法。
【請求項１５】
コンピュータに、
完全ネストループ構造を構成する複数のループで使用するデータのメインメモリ上の配置の候補ごとに、当該候補を採用した場合にキャッシュメモリを含む演算装置が前記複数のループの実行に伴い前記メインメモリへアクセスする回数に関する指標を算出し、前記指標に基づいて、前記候補の中から前記データの配置を決定する配置決定手順と、
前記データの配置を採用した完全ネストループ構造を有するプログラムを生成する生成手順と、を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム生成装置、プログラム生成方法およびプログラムに関し、例えば、照合処理プログラムを生成するプログラム生成装置、プログラム生成方法およびプログラムに関する。
【背景技術】
【０００２】
ベクトル演算器ユニットとキャッシュメモリとを有するプロセッサ（以下「ベクトル演算プロセッサ」と称する）が知られている。
ベクトル演算プロセッサは、ベクトル演算器ユニットでの処理が効率的となるループ部分やキャッシュヒット率が高くなるデータ配置を規定する部分を有するプログラムを高速に実行できる。
このため、ベクトル演算プロセッサで実行されるプログラムは、ベクトル演算器ユニットでの処理が効率的となるループ部分、または、キャッシュヒット率が高くなるデータ配置を規定する部分を有することが重要になる。
【０００３】
図４７は、一般的な照合処理で扱われるデータの例を示した図である。
照合処理では、照合元の1つの特徴ベクトルと照合先の複数の特徴ベクトルが扱われる。図４７に示した各特徴ベクトルは、100個の要素を有するデータである。なお、特徴ベクトルの要素数は100に限らず適宜変更可能である。
1つの照合元と1つの照合先との照合処理（以下「1対1照合処理」と称する）では、まず、照合元の特徴ベクトルの各要素と照合先の1つの特徴ベクトルの各要素とを1つずつ乗算した乗算結果の総和を取る内積計算が行われる。次に、この内積計算によって得られた値がある閾値を超えるかが判定される。閾値を超えたと判定されたときには、照合元と照合先が合致したと決定される。一方、閾値を超えないと判定されたときには、照合元と照合先は合致しないと決定される。
1つの照合元と複数の照合先との照合処理では、1対1照合処理が照合先を変えながら繰り返される。そして、照合元のデータ（特徴ベクトル）が照合先のいずれのデータ（特徴ベクトル）と合致したかが判定される。
【０００４】
図４８は、1対1照合処理を繰り返す処理を規定したプログラム（以下「照合処理プログラム」と称する）１０１ａの例を示した図である。
照合処理プログラムは、多くの場合、多重ループネスト構造を有する。図４８に示した照合処理プログラム１０１ａは、2重ループネスト構造を有している。以下、照合処理プログラム１０１ａについて説明する。
ループ誘導変数i1を用いる外側ループは、照合元（s_v[100]）と2000個の照合先（f_v[2000][100]）との照合処理を示す。ループ誘導変数i2を用いる内側ループは、照合元の100要素の特徴ベクトルと1つの照合先の100要素の特徴ベクトルとの内積計算を示す。内側ループには、内積計算のためにループ内でのイテレーションごとに要素同士の積算結果が加算されるリダクション変数（図４８のscore[i1]）が存在する。そして、照合元と照合先の内積計算の結果が閾値（th1=1000）より大きい場合に、照合中の照合先のデータが照合元のデータと合致したと判断される。
【０００５】
図４９は、計算量削減のためのアルゴリズム最適化を適用した照合処理プログラム１０２ａの例を示した図である。
照合処理プログラム１０２ａは、照合処理プログラム１０１ａが有する機能に加えて、最初の20要素についての内積計算の結果が既定値（th1/5）以下の場合に、その内積計算の対象である照合先についての1対1照合処理を途中で打ち切るという特徴を有する。1対1照合処理が途中で打ち切られることで、プログラム全体の計算量を削減することができる。
【０００６】
特許文献１には、メインメモリ上でのデータ配置が固定された状況において処理速度が高速となるように並列プログラムを生成するコンパイラが記載されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０００−２３１５４５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
照合処理プログラムは、多重ループネスト構造を有する。
このため、照合処理プログラムがベクトル演算プロセッサによって高速に処理されるためには、例えば、多重ループネスト構造について、メインメモリからのデータのロード命令にかかるコストとなる「メインメモリに対するアクセス数」の削減が重要である。
メインメモリに対するアクセス数を削減するためには、多重ループネスト構造で扱うデータのメインメモリ上のデータ配置を、ベクトル演算プロセッサでのキャッシュヒット率が高くなるデータ配置に設定する必要がある。
ここで、特許文献１に記載の技術は、メインメモリ上でのデータ配置が固定された状況において、プログラムを生成する技術である。このため、特許文献１に記載の技術では、ベクトル演算プロセッサでのキャッシュヒット率が高くなるデータ配置を設定することができない。したがって、特許文献１に記載の技術では、高速に処理されるプログラムを生成できないという課題があった。
【０００９】
本発明の目的は、上記課題を解決可能なプログラム生成装置、プログラム生成方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００１０】
本発明のプログラム生成装置は、完全ネストループ構造を構成する複数のループで使用するデータのメインメモリ上の配置の候補ごとに、当該候補を採用した場合にキャッシュメモリを含む演算装置が前記複数のループの実行に伴い前記メインメモリへアクセスする回数に関する指標を算出し、前記指標に基づいて、前記候補の中から前記データの配置を決定する配置決定部と、前記データの配置を採用した完全ネストループ構造を有するプログラムを生成する生成部と、を含む。
【００１１】
本発明のプログラム生成方法は、プログラム生成装置が行うプログラム生成方法であって、完全ネストループ構造を構成する複数のループで使用するデータのメインメモリ上の配置の候補ごとに、当該候補を採用した場合にキャッシュメモリを含む演算装置が前記複数のループの実行に伴い前記メインメモリへアクセスする回数に関する指標を算出し、前記指標に基づいて、前記候補の中から前記データの配置を決定し、前記データの配置を採用した完全ネストループ構造を有するプログラムを生成する。
【００１２】
本発明のプログラムは、コンピュータに、完全ネストループ構造を構成する複数のループで使用するデータのメインメモリ上の配置の候補ごとに、当該候補を採用した場合にキャッシュメモリを含む演算装置が前記複数のループの実行に伴い前記メインメモリへアクセスする回数に関する指標を算出し、前記指標に基づいて、前記候補の中から前記データの配置を決定する配置決定手順と、前記データの配置を採用した完全ネストループ構造を有するプログラムを生成する生成手順部と、を実行させる。
【発明の効果】
【００１３】
本発明によれば、高速に処理可能なプログラムを生成することが可能になる。
【図面の簡単な説明】
【００１４】
【図１】本発明の第１実施形態のプログラム生成装置を示した図である。
【図２】入力情報Aの一例を示した図である。
【図３】図２に示した階層プログラム1〜3にて特定されるプログラムBと、プログラムBの一部を構成する不完全ネストループ構造B1と、を示した図である。
【図４】不完全ネストループ構造B1から分割された完全ネストループ構造C1および1重ループ構造C2〜C3を示した図である。
【図５】完全ネストループ構造C1について列挙された２種類のプログラム構造のループネスト順序を示した図である。
【図６】図５に示したループネスト順序の各々について、図２に示した入力情報Aを用いて算出された高速化評価値の一例を示した図である。
【図７】高速化ループネスト順序を有するループネスト構造についてのメインメモリ上でのデータ配置の候補と、そのデータアクセスコスト評価値と、を示した図である。
【図８Ａ】f_a[1000][10]の場合のメインメモリ上のデータ配置と、特定ループネスト構造で各配列要素へアクセスする順序と、を示す図である。
【図８Ｂ】f_a[10][1000]の場合のメインメモリ上のデータ配置と、特定ループネスト構造で各配列要素へアクセスする順序と、を示す図である。
【図９Ａ】f_a[1000][10]の場合にメインメモリアクセスが発生する要素を示す図である。
【図９Ｂ】f_a[10][1000]の場合にメインメモリアクセスが発生する要素を示す図である。
【図１０】プログラム出力部５の一例を示した図である。
【図１１】ログラム構造決定部５１の出力例（プログラム全体構造51a）を示した図である。
【図１２】ループ生成部５２の出力例を示した図である。
【図１３】ループ生成部５２の出力例を示した図である。
【図１４】ループ生成部５２の出力例を示した図である。
【図１５】ループ生成部５２の出力例を示した図である。
【図１６】変数宣言生成部５３が変数宣言プログラムを生成する例を示した図である。
【図１７】プログラム生成部５４がメインプログラム54aを生成する例を示した図である。
【図１８】本実施形態の動作を説明するためのフローチャートである。
【図１９】データ配置決定部４ａとプログラム出力部５ａとからなるプログラム生成装置の一例を示した図である。
【図２０】本発明の第２実施形態のプログラム生成装置を示した図である。
【図２１】入力情報Aに含まれる階層プログラム1（Layer1）の一例を示した図である。
【図２２】図２１に示されたような2つの条件分岐を有するフローについて変数属性分類部６が解析したコントロールフロー図の例を示した図である。
【図２３】変数属性分類部６が、ステートメントのグループ化とそのグループへの到達確率の算出を行った結果の例を示した図である。
【図２４】各ループネスト順序の最内側のループについて、ループネスト順序決定部３が行う、分岐（到達確率）を考慮した高速化評価値の算出例を示した図である。
【図２５】本実施形態の動作を説明するためのフローチャートである。
【図２６】本発明の第３実施形態のプログラム生成装置を示した図である。
【図２７】打ち切り処理の有無が判断される階層プログラム1（Layer1）の一例を示した図である。
【図２８】打ち切り処理判断部７の動作を説明するための図である。
【図２９】本実施形態の動作を説明するためのフローチャートである。
【図３０】ステップS302の一例を示した図である。
【図３１】本発明の第４実施形態のプログラム生成装置を示した図である。
【図３２】初期化位置決定部８が変数s_a2、f_a2の初期化ステートメントの位置を移動する前のプログラムの例を示した図である。
【図３３】初期化位置決定部８が変数s_a2、f_a2の初期化ステートメントの位置を移動した後のプログラムの例を示した図である。
【図３４】本実施形態の動作を説明するためのフローチャートである。
【図３５】本発明の第５実施形態のプログラム生成装置を示した図である。
【図３６】本実施形態の動作を説明するためのフローチャートである。
【図３７】本発明の第６実施形態のプログラム生成装置を示した図である。
【図３８】アライメント考慮データ配置部１０の機能を説明するための図である。
【図３９】アライメント考慮データ配置部１０の機能を説明するための図である。
【図４０】アライメント考慮データ配置部１０の機能を説明するための図である。
【図４１】本実施形態の動作を説明するためのフローチャートである。
【図４２】本発明の第７実施形態のプログラム生成装置を示した図である。
【図４３】ループ拡張変数判断部１１が有する機能を説明するための図である。
【図４４】ループ拡張変数判断部１１が有する機能を説明するための図である。
【図４５】ループ拡張変数判断部１１が有する機能を説明するための図である。
【図４６】本実施形態の動作を説明するためのフローチャートである。
【図４７】一般的な照合処理で扱われるデータの例を示した図である。
【図４８】1対1照合処理を繰り返す処理を規定したプログラム１０１ａの例を示した図である。
【図４９】計算量削減のためのアルゴリズム最適化を適用した照合処理プログラム１０２ａの例を示した図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について図面を参照して説明する。
【００１６】
［第１の実施の形態］
以下、本発明を実施するための形態について図面を参照して詳細に説明する。
図１は、本発明の第１実施形態のプログラム生成装置を示した図である。
第１実施形態のプログラム生成装置は、入力情報Aを受け付ける生成装置１を含む。
入力情報Aは、複数の階層プログラムA1と、複数のループ化情報A2と、を含む。図１では、説明の簡略化を図るため、1つの階層プログラムA1と、1つのループ化情報A2が示されている。以下「階層プログラム」を「Layer」とも称する。「ループ化情報」を「Loop」とも称する。
【００１７】
まず、階層プログラムA1について説明する。
階層プログラムA1は、スカラ変数で記述されたプログラム構成A1aと、各スカラ変数の変数情報A1bと、を含む。
プログラム構成A1aは、1つ以上のBasic Block（ベーシックブロック：以下「BB」と称する）部A1a1と、ループ部A1a2と、Control Flow（コントロールフロー：以下「CF」と称する）情報A1a3と、を含む。
BB部A1a1は、高級言語（例えばC言語）で記述されたステートメント（処理ステートメント）で構成される。高級言語はC言語に限らず適宜変更可能である。
ループ部A1a2は、ある階層プログラムA1と、該階層プログラムA1を1つ以上のスカラ変数についての繰り返し処理とするためのループ化情報と、で構成される。
CF情報A1a3は、例えば、1つ以上のBB部A1a1、または、BB部A1a1とループ部A1a2、についてのコントロールフロー情報である。
変数情報A1bは、変数情報A1bを含む階層プログラムA1でアクセスされるスカラ変数名と、スカラ変数の型と、を示す。
【００１８】
次に、ループ化情報A2について説明する。
ループ化情報A2は、ループ回転数情報A2aと、ループ拡張対象変数リストA2bと、ループリダクション対象変数リストA2cと、を含む。
ループ回転数情報A2aは、ループ化する対象の階層プログラムの繰り返し回数を示す。
ループ拡張対象変数リストA2bは、ループ化された際にループ誘導変数でアクセスされるスカラ変数名を示す。
ループリダクション対象変数リストA2cは、ループ化された際にイテレーションごとに値を加算される変数名を示す。
【００１９】
図２は、入力情報Aの一例を示した図である。
本実施形態では、階層プログラム（Layer）A1の数は3となっている。ループ化情報（Loop）の数は2となっている。
各階層プログラムや各ループ化情報に示された情報は上述した通りである。
例えば、階層プログラム3（Layer3）に示された情報は以下の通りとなる。
BB1（BB部A1a1）は、変数s_aと変数f_aの初期化関数である。本実施形態では、各初期化関数として、プログラム生成後に作成される外部関数が用いられる。
L1（ループ情報A1a2）は、階層プログラム2（Layer2）とループ化情報2（Loop2）とを示す。
CF（CF情報A1a3）は、階層プログラム3（Layer3）のBB1から階層プログラム3のL1へのフロー（処理フロー）を示す。
変数リストは、補足的にLayer2（階層プログラム2）を示す。
【００２０】
図１に示した生成装置１は、ループネスト順序列挙部２と、ループネスト順序決定部３と、データ配置決定部４と、プログラム出力部５と、を含む。
【００２１】
まず、ループネスト順序列挙部２について説明する。
ループネスト順序列挙部２は、列挙部の一例である。
ループネスト順序列挙部２は、入力情報Aに含まれる全ての階層プログラムを用いて、プログラム全体のうちの一部を構成する抽象的な不完全ネストループ構造（以下「不完全ネストループ構造」と称する）を特定する。ここで、語句「抽象的」は、プログラムをステートメント単位ではなく概略的に示すことを意味する。
図３は、図２に示した階層プログラム1〜3にて特定されるプログラムBと、プログラムBの一部を構成する不完全ネストループ構造B1と、を示した図である。図３では、ループ部分が点線で、各構造プログラム全体とBB部が実線で示されている。
続いて、ループネスト順序列挙部２は、不完全ネストループ構造B1を、完全ネストループ構造と、完全ネストループ構造でもなく不完全ネストループ構造でもない1重（単一）ループ構造（以下、単に「1重ループ構造」と称する）と、に分割する。
図４は、不完全ネストループ構造B1から分割された完全ネストループ構造C1および1重ループ構造C2〜C3を示した図である。
完全ネストループ構造C1では、完全ネストループ構造C1内においてループ順序の入れ替え（Loop2とLoop1の順序の入れ替え）が可能である。
なお、入力情報Aにて特定されるプログラム全体の中に完全ネストループ構造が存在する場合、ループネスト順序列挙部２は、その完全ネストループ構造を特定する。
続いて、ループネスト順序列挙部２は、完全ネストループ構造（ループ化情報（Loop）1およびループ化情報（Loop）2を有する完全ネストループ構造C1）について、互いに異なるループネスト順序となる複数のプログラム構造を列挙する。
完全ネストループ構造C1は、2重ネストループ（Loop1とLoop2）である。このため、ループネスト順序列挙部２は、Loop2（外側）からLoop1（内側）へのループネスト順序となるプログラム構造と、Loop1（外側）からLoop2（内側）へのループネスト順序となるプログラム構造と、を列挙する。
図５は、完全ネストループ構造C1について列挙された2種類のプログラム構造のループネスト順序を示した図である。図５において、番号1のループネスト順序は、Loop2（外側）からLoop1（内側）へのループネスト順序を示す。番号2のループネスト順序は、Loop1（外側）からLoop2（内側）へのループネスト順序を示す。
なお、完全ネストループ構造が3重ネストループである場合、ループネスト順序を示す3つのループの組合せの数（ループネスト順序の数）は、3の階乗で表される数となる。
【００２２】
次に、ループネスト順序決定部３について説明する。
ループネスト順序決定部３は、データ配置が未決定な抽象化された多重ループ処理の各ループネスト順序（例えば、図５参照）について、階層プログラムA1とループ化情報A2とを用いて、高速化評価値を算出する。
ループネスト順序決定部３は、ループネスト順序ごとに、ベクトル演算が実行されない場合におけるループネスト順序で最内のループの回転数と、ベクトル演算が実行される場合における最内のループの回転数と、の関係に基づいて、高速化評価値を算出する。なお、ベクトル演算は、ベクトル演算プロセッサにて実行される。
高速化評価値は、対象となるループネスト順序を採用した際に、そのループネスト順序で示された複数のループについてベクトル演算プロセッサでベクトル演算を実行した場合に生じる高速化の度合い一例である。
ループネスト順序決定部３は、高速化評価値が閾値以上となる1つ以上のループネスト順序を、高速化ループネスト順序として決定する。なお、ループネスト順序決定部３は、ループネスト順序列挙部２が列挙したすべてのループネスト順序を、高速化ループネスト順序として決定してもよい。
なお、高速化評価値として、ループネスト順序で特定される最内側ループの回転数、または、該最内側ループの非ベクトル化時の命令数（回転数）に対するベクトル化時の命令数（回転数）の比（ベクトル化による命令数の削減率）が用いられてもよい。高速化評価値は、これらに限らず適宜変更可能である。なお、用語「ベクトル化」は、ベクトル演算の実行を意味する。
ループネスト順序決定部３は、完全ネストループ構造の各ループの実行時に使用されるデータのメインメモリ上での配置が未決定であるために、ベクトル演算プロセッサでのキャッシュ効率は理想的であると仮定して高速化評価値を算出する。なお、完全ネストループ構造の各ループの実行時に使用されるデータのメインメモリ上での配置を「データ配置」とも称する。
図６は、図５に示したループネスト順序の各々について、図２に示した入力情報Aを用いて算出された高速化評価値の一例を示した図である。
図６では、高速化評価値として、ベクトル化前の最内側ループのループ回転数を、ベクトル化後の最内側ループのループ回転数で除算した値が用いられている。
本実施形態では、プログラムを実行するベクトル演算プロセッサが、256bitのベクトル演算器ユニットを持つとした。ここで、階層プログラムからBB1でアクセスされる変数がint型（32bit）であるために、ベクトル化によってまとめて処理されるデータ数（ループ回転数）は8（＝256/32）となる。なお、ベクトル演算器ユニットのスペックは、上記に限らず適宜変更可能である。
番号1のループネスト順序では、最内側ループの回転数が10回転（非ベクトル化時）である。そして、ベクトル化によって8データ（8回転）がまとめて処理される。このため、ベクトル化時には、ベクトル化されたループ回転数が1、ベクトル化されない余りループ回転数が2となる。したがって、ベクトル化が行われた場合、ループ回転数は3回転となる。このとき、高速化評価値は3.33（＝10/3）となる。
次に、番号2のループネスト順序では、最内側ループ回転数が1000回転（非ベクトル化時）である。そして、ベクトル化が行われた場合、ループ回転は125（=1000/8）回転となる。このとき、高速化評価値は8.00（＝1000/125）となる。
ここで、設定された閾値が4.00であるとする。この場合、ループネスト順序決定部３は、番号2のループネスト順序を、高速化ループネスト順序として決定する。閾値は4.00に限らず適宜変更可能である。
閾値以上の高速化評価を有するループネスト順序が複数存在する場合には、ループネスト順序決定部３は、それら複数のループネスト順序の各々を、高速化ループネスト順序として決定する。
閾値以上の高速化評価を有するループネスト順序が存在しない場合には、ループネスト順序決定部３は、入力された元のループ順序を、高速化ループネスト順序として決定する。入力された元のループ順序の一例としては、例えば、図４に示した完全ネストループ構造C1が有するループ順序（Loop2からLoop1）が挙げられる。
【００２３】
次に、データ配置決定部４について説明する。
データ配置決定部４は、配置決定部の一例である。
データ配置決定部４は、1つ以上の高速化ループネスト順序のそれぞれに対して、ループ化によって拡張された変数のメインメモリ上のデータ配置を、該データ配置についてのデータアクセスコスト評価値から決定する。
データアクセスコスト評価値は、指標の一例である。
データアクセスコスト評価値は、対象となるデータ配置が採用された際にキャッシュメモリを有する演算装置（ベクトル演算プロセッサ）が高速化ループネスト順序で示された複数のループを実行した場合でのメインメモリへのアクセス回数に関する指標である。なお、ベクトル演算プロセッサは、上述した通り、ベクトル演算器ユニットとキャッシュメモリとを有するプロセッサである。
本実施形態では、データアクセスコスト評価値は、メインメモリへアクセスする回数の増加に応じて増加する。
なお、メインメモリへアクセスする回数は、高速化ループネスト順序で示された複数のループのベクトル演算プロセッサによる実行に伴う該ベクトル演算プロセッサ内のキャッシュメモリでのキャッシュヒットの増加に応じて減少する。
例えば、データ配置についてのデータアクセスコスト評価値として、ベクトル演算プロセッサが高速化ループネスト順序の完全ネストループ構造を実行する場合に、そのデータ配置が適用されたメインメモリに対するベクトル演算プロセッサからのアクセス回数の総和が用いられる。なお、データアクセスコスト評価値は、これに限定されない。
データ配置決定部４は、データアクセスコスト評価値に基づいて、例えば最内ループのループ誘導変数でアクセスされる複数のデータがメインメモリ上に連続的に並ぶようなデータ配置を決定する。
図７は、高速化ループネスト順序（例えば、図６の番号2のループネスト順序）を有するループネスト構造についてのメインメモリ上でのデータ配置（多次元配列）の候補と、そのデータアクセスコスト評価値と、を示した図である。
本実施形態では、ループ化情報1およびループ化情報2に示されたように、複数ループ（Loop1とLoop2）によって拡張される変数（Loop1とLoop2との両方で使用される変数）はf_aの1つだけである。
この場合、2次元配列（データ配置）f_aの候補としては、f_a[1000][10]とf_a[10][1000]の2種類がある。[10]と[1000]は、ループ化情報1の回転数「10」と、ループ化情報2の回転数「1000」に対応する。
データ配置決定部４は、高速化ループネスト順序（Loop1（外側）からLoop2（内側）の順序）に対する2種類の2次元配列の候補ごと、データアクセスコスト評価値を算出する。
【００２４】
本実施形態では、多次元配列はrow-major order（行優先順）でメインメモリに配置されるとする。また、ラインサイズ64Byteの32KBのキャッシュメモリを有するアーキテクチャ（ベクトル演算プロセッサ）を対象としたメインメモリアクセス回数が、データアクセスコスト評価値として用いられる。なお、キャッシュメモリのスペックは上記に限らず適宜変更可能である。
【００２５】
図８Ａ、図８Ｂは、f_a[1000][10]とf_a[10][1000]のそれぞれの場合のメインメモリ上のデータ配置と、高速化ループネスト順序にて特定されるループネスト構造（以下「特定ループネスト構造」と称する）に従って各配列要素へアクセスする順序と、を示す図である。
以下では、説明の簡略化のため、変数f_aでアクセスされるデータが、10個の要素で構成された1000個の照会先特徴ベクトルであるとする。
【００２６】
データはrow-major order（行優先順）でメインメモリに配置される。このため、図８Ａに示したf_a[1000][10]の場合、特定ループネスト構造に従った使用順に並ぶデータ（要素）は、メインメモリ上ではf_a[0][0]，f_a[1][0]，f_a[2][0]，...，f_a[999][0]，f_a[0][1]，f_a[1][1]，...，f_a[999][9]の順序で連続に並ぶ。
_  したがって、ベクトル演算プロセッサが特定ループネスト構造に従った処理を行う場合、メインメモリ上のデータ（要素）は、f_a[0][0]，f_a[1][0]，f_a[2][0]，...，f_a[999][0]，f_a[0][1]，f_a[1][1]，...，f_a[999][9]の順序でアクセスされる。
f_a[1000][10]の場合、ベクトル演算プロセッサがf_a[0][0]にアクセスした時にベクトル演算プロセッサのキャッシュメモリ上にデータが無いために、メインメモリへのアクセスが発生する。
このアクセスにより、ベクトル演算プロセッサのキャッシュメモリ上には、キャッシュライン64Byte分となるf_a[0][0]からf[1][5]までのデータが配置される。
したがって、f_a[0][0]の次のf_a[1][0]のアクセスは、キャッシュアクセス（キャッシュヒット）となる。
しかしながら、f_a[1][0]の次のf_a[2][0]のアクセスは、キャッシュミスとなり、メインメモリへのアクセスが発生する。
f_a[1000][10]の場合、これらの処理を繰り返すために、2回に1度はメインメモリへのアクセスが発生することとなる。
【００２７】
一方、図８Ｂに示したf_a[10][1000]の場合、特定ループネスト構造に従った使用順に並ぶデータ（要素）は、メインメモリ上ではf_a[0][0]，f_a[0][1]，...，f_a[0][999]，f_a[1][0]，...，f_a[9][999]の順序で連続に並ぶ。
したがって、ベクトル演算プロセッサが特定ループネスト構造に従った処理を行う場合、メインメモリ上のデータ（要素）は、f_a[0][0]，f_a[0][1]，...，f_a[0][999]，f_a[1][0]，...，f_a[999][9]の順序でアクセスされる。
f_a[10][1000]の場合、ベクトル演算プロセッサがf_a[0][0]にアクセスした時にベクトル演算プロセッサのキャッシュメモリ上にデータが無いために、メインメモリへのアクセスが発生する。
このアクセスにより、ベクトル演算プロセッサのキャッシュメモリ上には、キャッシュライン64Byte分となるf_a[0][0]からf[0][15]までのデータが配置される。
したがって、f_a[0][0]の次のf_a[0][1]からf_a[0][15]までのアクセスは、キャッシュアクセス（キャッシュヒット）となる。
f_a[10][1000]の場合、この処理を繰り返すために、16回に1度、メインメモリへのアクセスが発生することとなる。
図９Ａ、図９Ｂは、f_a[1000][10]とf_a[10][1000]のそれぞれの場合にメインメモリアクセス（メモリアクセス）が発生する要素を示す図である。
【００２８】
図８Ａおよび図９Ａに示したように、図７に示したデータ配置番号1のデータ配置候補「f_a[1000][10]」は、1000回転の内側ループで10要素ごとのストライドアクセスとなる。よって、メインメモリアクセスは2回のループに対して1回発生する。このため、メインメモリアクセス回数は5000回（図７参照）となる。
また、図８Ｂおよび図９Ｂに示したように、データ配置番号2のデータ配置候補「f_a[10][1000]」は1000回転の内側ループで連続アクセスとなる。よって、メインメモリアクセスは16回のループに対して1回発生する。このため、メインメモリアクセス回数は630回（図７参照）となる。
データ配置決定部４は、図７に示されたデータアクセスコスト評価値に基づいて、データ配置番号2のデータ配置候補「f_a[10][1000]」を、データ配置として決定する。
【００２９】
次に、プログラム出力部５について説明する。
プログラム出力部５は、生成部の一例である。
プログラム出力部５は、不完全ネストループ構造B1の代わりに、1つ以上の高速化ループネスト順序とデータ配置を採用したプログラム部分（完全ネストループ構造）と、1重ループ構造部分（C2〜C3）と、を有するプログラムを生成する。プログラム出力部５は、生成したプログラムを出力する。
【００３０】
図１０は、プログラム出力部５の一例を示した図である。
プログラム出力部５は、プログラム構造決定部５１と、ループ生成部５２と、変数宣言生成部５３と、プログラム生成部５４と、を含む。
プログラム構造決定部５１は、階層プログラムA1とループ化情報A2と高速化ループネスト順序とを用いて、プログラム全体構造を決定する。
図１１は、プログラム構造決定部５１の出力例（プログラム全体構造51a）を示した図である。
ループ生成部５２は、プログラム全体構造51aと階層プログラムA1とループ化情報A2と決定されたデータ配置とを用いて、各ループのプログラムを生成する。
図１２〜図１５は、ループ生成部５２の出力例を示した図である。
図１２は、ループ生成部５２が、プログラム全体構造51a内の一重ループLoop2「Layer2：BB1」のプログラム（th1＝1000;）を、プログラム全体構造51aと階層プログラムA1とループ化情報A2とデータ配置とを用いて生成する例を示した図である。
図１３は、ループ生成部５２が、プログラム全体構造51a内の完全ネストループ構造のLoop1→Loop2のプログラムを、プログラム全体構造51aと階層プログラムA1とループ化情報A2とデータ配置とを用いて生成する例を示した図である。
図１４は、ループ生成部５２が、プログラム全体構造51a内の一重ループLoop2「Layer2：BB2」のプログラムを、プログラム全体構造51aと階層プログラムA1とループ化情報A2とデータ配置とを用いて生成する例を示した図である。
なお、本実施形態では、ループ生成部５２は、プログラム全体構造51aと階層プログラムA1とループ化情報A2と決定されたデータ配置とを用いて、ループ以外の部分（例えば、プログラム全体構造51a内のLayer3:BB1））のプログラムも生成する。
そして、ループ生成部５２は、ループ生成部５２が生成した各プログラムを、プログラム全体構造51aに従ってつなぎ合わせて、つなぎ合わせプログラムを生成する。
図１５は、つなぎ合わせプログラムの一例を示した図である。
変数宣言生成部５３は、決定されたデータ配置と、階層プログラムA1（変数リスト）と、を用いて、変数宣言プログラムを生成する。
図１６は、変数宣言生成部５３が変数宣言プログラムを生成する例を示した図である。
プログラム生成部５４は、変数宣言プログラムとつなぎ合わせプログラムとを用いて、メインプログラムを生成する。
図１７は、プログラム生成部５４がメインプログラム54aを生成する例を示した図である。なお、図１７に示されたメインプログラム54aは、図２に示した入力情報Aに対して出力されるプログラムの一例である。
【００３１】
次に、動作を説明する。
図１８は、本実施形態の動作を説明するためのフローチャートである。
ループネスト順序列挙部２は、階層プログラムA1を参照し、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を列挙する（ステップS101）。
続いて、ループネスト順序決定部３は、データ配置未決定な抽象化された多重ループ処理の各ループネスト順序に対して、階層プログラムA1とループ化情報A2とを用いて高速化評価値を算出する。そして、ループネスト順序決定部３は、設定された閾値以上となる高速化評価値を持つ1つ以上のループネスト順序を、高速化ループネスト順序として決定する（ステップS102）。
続いて、データ配置決定部４は、1つ以上の高速化ループネスト順序のそれぞれに対して、ループ化によって拡張された変数のメインメモリ上のデータ配置を、データアクセスコスト評価値を用いて決定する（ステップS103）。
続いて、プログラム出力部５は、1つ以上のループネスト順序とデータ配置を表すプログラムを出力する（ステップS104）。
【００３２】
本実施形態の生成装置１では、ループネスト順序列挙部２と、ループネスト順序決定部３と、データ配置決定部４と、プログラム出力部５は、以下のように機能する。
ループネスト順序列挙部２は、プログラムを特定するためのプログラム情報（入力情報A）に示された不完全ネストループ構造を、完全ネストループ構造と、単一ループ構造と、に分ける。
続いて、ループネスト順序列挙部２は、完全ネストループ構造に含まれる複数のループについて、ループネスト順序の組合せを列挙する。
続いて、ループネスト順序決定部３は、各ループネスト順序について、該ループネスト順序のループに対してベクトル演算が行われた場合の高速化に関する高速化評価値を算出する。本実施形態では、高速化評価値の値が大きいほど、高速化評価値に対応するループネスト順序の高速化の度合いが高くなる。
続いて、ループネスト順序決定部３は、ループネスト順序の中から、高速化評価値が閾値以上のループネスト順序である高速化ループネスト順序を、該当順序として決定する。
続いて、データ配置決定部４は、該当順序で順序づけされた複数のループの各ループ誘導変数でアクセスされる変数のメインメモリ上でのデータ配置の候補を決定する。
続いて、データ配置決定部４は、各候補について、その候補を採用した場合にベクトル演算プロセッサが該当順序の複数のループの実行時にメインメモリへアクセスする回数に関するデータアクセスコスト評価値を算出する。
続いて、データ配置決定部４は、データアクセスコスト評価値に基づいて、メインメモリへのアクセス数が最も少なくなる候補を、データ配置として決定する。
続いて、プログラム出力部５は、不完全ネストループ構造の代わりに、該当順序とデータ配置とを採用した完全ネストループ構造と単一ループ構造とを用いたプログラムを生成する。
【００３３】
次に、本実施形態の効果について説明する。
本実施形態では、ループネスト順序列挙部２は、プログラム中のループネスト順序の入れ替え可能なループネスト構造を発見する。ループネスト順序決定部３は、対象のループネスト構造に対してベクトル化効率の良いループネスト順序を自動的に決定する。データ配置決定部４は、決定されたループネスト順序でのベクトル化時のデータのメインメモリからのロードコスト（例えばメインメモリからのロード回数）を小さくするデータ配置を自動的に決定する。プログラム出力部５は、決定されたループネスト順序およびデータ配置を採用したプログラムを生成する。
このため、例えば、短期間で高速実行可能な照合プログラムを生成することができる。
【００３４】
本実施形態によれば、データ配置決定部４は、完全ネストループ構造に含まれる複数のループの各ループ誘導変数でアクセスされるデータのメインメモリ上でのデータ配置の複数の候補の各々について、データアクセスコスト評価値を算出する。ここで、データアクセスコスト評価値は、その候補（データ配置）が採用された場合に、ベクトル演算プロセッサが完全ネストループ構造の実行に伴いメインメモリへアクセスする回数に応じた指標である。また、複数のループの各ループ誘導変数でアクセスされるデータは、複数のループで使用されるデータの一例である。
データ配置決定部４は、データアクセスコスト評価値に基づいて、複数の候補の中から、メインメモリ上でのデータ配置を決定する。プログラム出力部５は、決定されたデータ配置を採用した完全ネストループ構造を有するプログラムを生成する。
このため、メインメモリへアクセスする回数に基づいて、データ配置を決定することが可能になる。よって、複数の候補のうち、メインメモリへアクセスする回数が相対的に少ない候補をデータ配置として決定可能になり、メインメモリへのアクセスに要する総時間を短くできる。したがって、短期間で高速実行可能なプログラム（例えば照合処理プログラム）を生成可能になる。
【００３５】
この効果は、データ配置決定部４ａとプログラム出力部５ａとからなるプログラム生成装置でも生じる。
図１９は、データ配置決定部４ａとプログラム出力部５ａとからなるプログラム生成装置の一例を示した図である。
データ配置決定部４ａは、完全ネストループ構造に含まれる複数のループの各ループ誘導変数でアクセスされるデータのメインメモリ上でのデータ配置の候補ごとに、データアクセスコスト評価値を算出する。データ配置決定部４ａは、データアクセスコスト評価値に基づいて、複数の候補の中から、メインメモリ上でのデータ配置を決定する。プログラム出力部５ａは、決定されたデータ配置を採用した完全ネストループ構造を有するプログラムを生成する。
【００３６】
図１に示したデータ配置決定部４は、データアクセスコスト評価値に基づいて、複数の候補のうち、メインメモリへのアクセス回数が最小となる候補を、データ配置として決定する。
このため、メインメモリへのアクセスに要する総時間を最も短くできる候補をデータ配置として決定することが可能になる。
なお、データ配置決定部４は、複数の候補のうち、データアクセスコスト評価値が既定値以下である候補を、データ配置として決定してもよい。
【００３７】
本実施形態では、ループネスト順序列挙部２は、完全ネストループ構造に含まれる複数のループについて、ループネスト順序の組合せを列挙する。
ループネスト順序決定部３は、ループネスト順序ごとに、ループネスト順序を採用した場合に複数のループについてベクトル演算を実行した際に生じる処理の高速化の度合いを示す高速化評価値を算出する。ループネスト順序決定部３は、ループネスト順序の中から高速化の度合いが閾値以上のループネスト順序である該当順序を決定する。
データ配置決定部４は、データ配置の候補ごとに、その候補を採用した場合にベクトル演算プロセッサが該当順序での複数のループの実行に伴いメインメモリへアクセスする回数に関する情報を、データアクセスコスト評価値として算出する。データ配置決定部４は、データ配置の候補の中から、データアクセスコスト評価値に基づいてメインメモリ上でのデータ配置を決定する。
プログラム出力部５は、該当順序とデータ配置とを採用した完全ネストループ構造を有するプログラムを生成する。
このため、ベクトル処理にて高速化が図れるプログラムを生成することが可能になる。
【００３８】
［第２の実施の形態］
図２０は、本発明の第２実施形態のプログラム生成装置を示した図である。
第２実施形態のプログラム生成装置が、図１に示した第１実施形態のプログラム生成装置と異なる点は、第２実施形態のプログラム生成装置が、第１実施形態のプログラム生成装置に加えて、変数属性分類部６をさらに含む点である。以下、第２実施形態のプログラム生成装置について、第１実施形態のプログラム生成装置と異なる点を中心に説明する。
変数属性分類部６は、算出部の一例である。
変数属性分類部６は、ループ内のステートメントへの処理フローの到達確率を算出する。本実施形態では、変数属性分類部６は、階層プログラムA1のCF情報A1a3やBB部A1a1をコントロールフロー解析することで得られるコントロールフロー情報に基づいて、ループ内の到達確率が異なるステートメントをグループ化する。変数属性分類部６は、ステートメントに属する変数を列挙し、変数のグループ化と、変数への処理フローの到達確率（ステートメントへの処理フローの到達確率）の算出を行う。なお、変数のグループ化と到達確率情報は、入力として与えられてもよい。
ループネスト順序決定部３は、ループネスト順序ごとに、ループネスト順序が示すループ内のステートメントへの処理フローの到達確率に基づいて高速化評価値を算出する。
【００３９】
図２１は、入力情報Aに含まれる階層プログラム1（Layer1）の一例を示した図である。図２１に示した階層プログラム1（Layer1）のBB1は、ネストループ構造の一部を構成するループ内で実行される。図２１に示した階層プログラム1（Layer1）のBB1には、2つの条件分岐（if文）が含まれている。
図２２は、図２１に示されたような2つの条件分岐を有するフローについて変数属性分類部６が解析したコントロールフローの例を示した図である。
図２２では、ステートメント1（S1）実行後に分岐1（B1）によって処理フローがステートメント2（S2）または終了へ分岐する。ステートメント2（S2）実行後に処理フローが分岐2（B2）によってステートメント3（S3）または終了へ分岐する。ステートメント3（S3）実行後、処理フローは終了に遷移する。
図２３は、変数属性分類部６が、ステートメントのグループ化とそのグループへの処理フローの到達確率の算出を行った結果の例を示した図である。
本実施形態では、各分岐は2つの分岐先を持ち、各分岐先へ分岐する確率は等しいとする。したがって、各分岐は50%の確率で次のステートメントへ、50%の確率で終了へ分岐する。このため、グループ番号1に属するステートメント番号S1は100%の到達確率となり、よって、ステートメント番号S1でアクセスされる変数s_a1とf_a1の到達確率は100%となる。
同様に1回の分岐の後に実行されるグループ番号2のステートメント番号S2は50%の到達確率となり、2回の分岐の後に実行されるグループ番号3のステートメント番号S3は25%の到達確率となる。
【００４０】
ループネスト順序決定部３は、第１実施形態で示したように、データ配置が未決定な抽象化された多重ループ処理の各ループネスト順序に対して、高速化評価値を算出する。
本実施形態では、ループネスト順序決定部３は、高速化評価値として、最内側のループについての非ベクトル化時の命令数に対するベクトル化時の命令数の比の逆数を算出する。
ループネスト順序決定部３は、各ループネスト順序の最内側のループについて、非ベクトル化時の命令数およびベクトル化時の命令数を、変数属性分類部６の算出結果（図２３参照）を利用して算出する。
【００４１】
図２４は、各ループネスト順序の最内側のループについて、ループネスト順序決定部３が行う、分岐（到達確率）を考慮した高速化評価値の算出例を示した図である。
例えば、ループ中のあるステートメントが分岐後に実行される場合、そのステートメントへの到達確率は変数属性分類部６によって50%と決定される。
このとき、1つの分岐を含むループでの該ステートメントでのスカラ実行時の命令数は、分岐が無い場合に対して1/2になる。このため、ループネスト順序決定部３は、非ベクトル化の状況でのスカラ実行時の高速化評価値として2（1/2の逆数）を算出する。
さらに、ベクトル化時の命令数を考えた時には、スカラ実行時（非ベクトル化時）の命令数に対するベクトル化時の命令数の比が状況によって異なる。
1つの状況としては、N回のループのうち前半N/2回で処理フローが分岐後のステートメントに到達し、後半N/2回で処理フローが終了に遷移する場合が考えられる。この状況では、ベクトル化が行われた際の命令数は、前半N/2回の命令実行回数の1/8となる（この場合、後半N/2回に対するベクトル化等は不要）。このため、この状況では、ベクトル化が行われた際の命令数は、分岐を考慮しないスカラ実行時の命令数Nの1/16（＝1/2*1/8）になる。よって、ループネスト順序決定部３は、高速化評価値として16（1/16の逆数）を算出する。
一方、2回に1回に頻度で分岐がステートメントに到達する状況を考えると、N回のループ全体にわたってベクトル化が行われる（ただし、1回のベクトル命令では8データのうち4データだけが有効な実行になる。）。このように、N回のループ全体にわたってベクトル化が行われる場合、ベクトル化が行われた際の命令数は、分岐を考慮しないスカラ実行時の命令数Nの1/8となる。よって、ループネスト順序決定部３は、高速化評価値として8（1/8の逆数）を算出する。
ここで、分岐を考慮したスカラ実行時（非ベクトル化時）の高速化評価値は2、分岐を考慮したベクトル化時の最大の高速化評価値は16、最小の高速化評価値は8となる。このため、分岐を考慮したスカラ実行時に対する、分岐を考慮したベクトル化時の高速化評価値は、4〜8となる。なお、4は、「分岐を考慮した非ベクトル化時の高速化評価値＝2」に対する「分岐を考慮したベクトル化時の最小の高速化評価値＝8」の比である。また、8は、「分岐を考慮した非ベクトル化時の高速化評価値＝2」に対する「分岐を考慮したベクトル化時の最小の高速化評価値＝16」の比である。
ループネスト順序決定部３は、各ループネスト順序の高速化評価値を、上述したように算出する。
その後、ループネスト順序決定部３は、高速化評価値が閾値以上となる1つ以上のループネスト順序を、高速化ループネスト順序として決定する。なお、ループネスト順序決定部３は、ループネスト順序列挙部２が列挙したすべてのループネスト順序を、高速化ループネスト順序として決定してもよい。
【００４２】
次に、動作を説明する。
図２５は、本実施形態の動作を説明するためのフローチャートである。
ループネスト順序列挙部２は、階層プログラムA1を参照し、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を列挙する（ステップS101）。
続いて、変数属性分類部６は、階層プログラムA1のCF情報やBB内部をコントロールフロー解析することで得られるコントロールフロー情報から、到達確率が異なるステートメントをグループ化する。続いて、変数属性分類部６は、入力情報Aを参照して、グループ化されたステートメントに属する変数を列挙する。続いて、変数属性分類部６は、変数の属するステートメントのグループ化結果に基づいて、変数のグループ化と、各グループへの処理フローの到達確率の算出を行う（ステップS201）。
続いて、ループネスト順序決定部３は、データ配置未決定な抽象化された多重ループ処理の各ループネスト順序に対して、階層プログラムA1とループ化情報A2と変数属性分類部６の算出結果とに基づいて高速化評価値を算出する。そして、ループネスト順序決定部３は、設定された閾値以上となる高速化評価値を有する1つ以上のループネスト順序を、高速化ループネスト順序として決定する（ステップS202）。
続いて、データ配置決定部４は、1つ以上の高速化ループネスト順序のそれぞれに対して、ループ化によって拡張された変数のメインメモリ上のデータ配置を、データアクセスコスト評価値を用いて決定する（ステップS103）。
続いて、プログラム出力部５は、少なくとも1つ以上のループネスト順序とデータ配置を表すプログラムを出力する（ステップS104）。
【００４３】
次に、本実施形態の効果について説明する。
本実施形態では、ループネスト順序列挙部２は、プログラム中のループネスト順序の入れ替え可能なループネスト構造を発見する。変数属性分類部６は、該ループネスト構造内の分岐に応じた各ステートメントおよび各ステートメントに属する変数のグループ化および到達確率を算出する。ループネスト順序決定部３は、変数属性分類部６の算出結果（例えば、図２３）を参照して、対象のループネスト構造に対して、分岐を考慮したベクトル化効率の良いループネスト順序を自動的に決定する。データ配置決定部４は、決定されたループネスト順序でのベクトル化時のデータのメインメモリからのロードコストを小さくするデータ配置を自動的に決定する。
このため、例えば、入力情報Aに依存して分岐確率が変わることで高速化効果が異なる複数種類の照合プログラムを短期間で生成することができる。
【００４４】
［第３の実施の形態］
図２６は、本発明の第３実施形態のプログラム生成装置を示した図である。
第３実施形態のプログラム生成装置が、図１に示した第１実施形態のプログラム生成装置と異なる点は、第３実施形態のプログラム生成装置が、第１実施形態のプログラム生成装置に加えて、打ち切り処理判断部７をさらに含む点である。以下、第３実施形態のプログラム生成装置について、第１実施形態のプログラム生成装置と異なる点を中心に説明する。
【００４５】
打ち切り処理判断部７は、ループネスト構造で規定されたループを途中で打ち切る打ち切り処理の有無を判断する。
本実施形態では、打ち切り処理判断部７は、ループネスト構造で規定されたループ内の分岐によってループ外、または、次イテレーションへジャンプする打ち切り処理（ループを途中で打ち切る打ち切り処理）の有無を階層プログラムA1ごとに判断する。
図２７は、打ち切り処理の有無が判断される階層プログラム1（Layer1）の一例を示した図である。図２７に示した階層プログラム1（Layer1）は、例えば、図２に示した階層プログラム1（Layer1）の代わりに用いられる。
図２８は、打ち切り処理判断部７の動作を説明するための図である。
まず、打ち切り処理判断部７は、BB部A1a1（BB1）中に分岐文を含むループについての階層プログラムから、分岐文によって階層プログラム終端へとジャンプする部分を検出する（ステップS1301）。図２７および図２８に示した例では、「if(y>4) [」の部分が、分岐文によって階層プログラム終端へとジャンプする部分として検出される。
続いて、打ち切り処理判断部７は、検出した分岐文の条件式で参照される変数がBB1内部でアクセスされていないことを検出する（ステップS1302）。図２７および図２８に示した例では、「d=s_a*f_a;」の部分から、検出した分岐文の条件式で参照される変数が内部でアクセスされていないことが検出される。
続いて、打ち切り処理判断部７は、検出した分岐文の条件式で参照される変数の定義ステートメントを検出する（ステップS1303）。図２７および図２８に示した例では、「y=s_a-f_a」が検出される。
続いて、打ち切り処理判断部７は、ステップS1301で検出した分岐文とステップS1303で検出したステートメントとの組合せを、打ち切り処理と判断する（ステップS1304）。図２７および図２８に示した例では、「y=s_a-f_a」と「if(y>4) [」との組合せが、打ち切り処理と判断される。
本実施形態では、ループネスト順序列挙部２は、ループネスト順序に示されたループに打ち切り処理が有る場合、さらに、打ち切り処理が有る場合の該ループネスト順序と、打ち切り処理が無い場合の該ループネスト順序と、を列挙する。
【００４６】
次に、動作を説明する。
図２９は、本実施形態の動作を説明するためのフローチャートである。
打ち切り処理判断部７は、ループ内の分岐によってループ外、または、次イテレーションへジャンプする打ち切り処理の有無を階層プログラムごとに判断する（ステップS301）。なお、ステップS301での処理は、図２８を用いて示した処理と同一である。
続いて、ループネスト順序列挙部２は、入れ替え可能なループネスト構造にて特定されるループに打ち切り処理がある場合、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を、打ち切り処理有りのBBと無しのBB'について列挙する（ステップS302）。なお、打ち切り処理判断部７が、打ち切り処理が無いと判断した場合、ループネスト順序列挙部２は、第１実施形態の動作と同様の動作を実行する。
図３０は、ステップS302の一例を示した図である。
図３０を参照すると、ループネスト順序列挙部２は、階層プログラムA1を参照し、入れ替え可能なループネスト構造内のループのうち打ち切り処理があるループについて、打ち切り処理がある場合のBBとない場合のBB'を生成する。図３０に示したBB1とBB1'は、打ち切り処理がある場合のBBとない場合のBB'の一例である。
続いて、ループネスト順序列挙部２は、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を、打ち切り処理有りのBBと無しのBB'について列挙する。図３０に破線で示した４つのループネスト順序は、打ち切り処理有りのBB1についての2つのループネスト順序（2つのプログラム構造）と、打ち切り処理無しのBB1'についての2つのループネスト順序（2つのプログラム構造）と、によって構成される。
続いて、ループネスト順序決定部３は、データ配置未決定な抽象化された多重ループ処理の各ループネスト順序（例えば、図３０に破線で示した４つのループネスト順序）に対して、階層プログラムA1とループ化情報A2とに基づいて高速化評価値を算出する。そして、ループネスト順序決定部３は、設定された閾値以上となる高速化評価値を有する1つ以上のループネスト順序を、高速化ループネスト順序として決定する（ステップS102）。
続いて、データ配置決定部４は、1つ以上の高速化ループネスト順序のそれぞれに対して、ループ化によって拡張された変数のメインメモリ上のデータ配置を、データアクセスコスト評価値を用いて決定する（ステップS103）。
続いて、プログラム出力部５は、少なくとも1つ以上のループネスト順序とデータ配置を表すプログラムを出力する（ステップS104）。
【００４７】
次に、本実施形態の効果について説明する。
本実施形態では、打ち切り処理判断部７は、ループネスト内のループ内の打ち切り処理の有無を判断する。ループネスト順序列挙部２は、プログラム中のループネスト順序の入れ替え可能なループネスト構造を発見する。ループネスト順序列挙部２は、ループ内に打ち切り処理がある場合、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を、打ち切り処理有りのBBと無しのBB'について列挙する。ループネスト順序決定部３は、各ループネスト構造についてベクトル化効率の良いループネスト順序を自動的に決定する。データ配置決定部４は、決定されたループネスト順序でのベクトル化時のデータのメインメモリからのロードコストを小さくするデータ配置に自動的に決定する。
このため、対象のループネスト構造について打ち切り処理を削除した場合の命令数削減効果も考慮してベクトル化効率の良いループネスト順序を自動的に決定することが可能になる。したがって、打ち切り処理が低確率でしか起こらない場合には打ち切り処理のための演算を削除することでより、例えば、高速化できる異なる複数種類の照合プログラムを短期間で生成することが可能になる。
【００４８】
次に、本実施形態の変形例について説明する。
本実施形態での打ち切り処理判断部７およびループネスト順序列挙部２が、第２実施形態で用いられてもよい。
【００４９】
［第４の実施の形態］
図３１は、本発明の第４実施形態のプログラム生成装置を示した図である。
第４実施形態のプログラム生成装置が、図２０に示した第２実施形態のプログラム生成装置と異なる点は、第４実施形態のプログラム生成装置が、第２実施形態のプログラム生成装置に加えて、初期化位置決定部８をさらに含む点である。以下、第４実施形態のプログラム生成装置について、第２実施形態のプログラム生成装置と異なる点を中心に説明する。
【００５０】
初期化位置決定部８は、ループ内のステートメントへの処理フローの到達確率が既定値以下の場合、該ステートメントで使用する変数を初期化する初期化ステートメントを、該変数を使用するステートメントの直前に配置する。初期化位置決定部８は、変数の初期化を規定する初期化関数も、初期化ステートメント位置に依存して作成する。
【００５１】
図３２は、初期化位置決定部８が変数s_a2、f_a2を初期化する初期化ステートメント（以下「初期化処理」とも称する）の位置を移動する前のプログラムの例を示した図である。
図３２に示した例では、「if (x<4) [」の分岐が例えば99％以上FALSEの場合、変数s_a2と変数f_a2はループ内では99％アクセスされない。このため、図３２に示した例では、変数s_a2、f_a2の初期化結果が実際に使用される可能性が低く、必要のない初期化処理が行われる可能性が高い。
図３３は、初期化位置決定部８が変数s_a2、f_a2の初期化処理（初期化ステートメント）の位置を移動した後のプログラムの例を示した図である。
図３３に示した例では、図３２に示されていた元々の変数s_a2、f_a2の初期化処理（初期化ステートメント）が削除され、「if (x<4) [」の分岐後の位置に、新しい初期化処理（初期化ステートメント）が作成されている。この初期化処理では、「if (x<4)」の内部で初期化の関数が呼び出される。
【００５２】
次に、動作を説明する。
図３４は、本実施形態の動作を説明するためのフローチャートである。
ループネスト順序列挙部２は、階層プログラムA1を参照し、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を列挙する（ステップS101）。
続いて、変数属性分類部６は、階層プログラムA1のCF情報やBB内部をコントロールフロー解析することで得られるコントロールフロー情報から、到達確率が異なるステートメントをグループ化する。続いて、変数属性分類部６は、入力情報Aを参照して、グループ化されたステートメントに属する変数を列挙する。続いて、変数属性分類部６は、変数の属するステートメントのグループ化結果に基づいて、変数のグループ化と、各グループへの到達確率の算出を行う（ステップS201）。
続いて、ループネスト順序決定部３は、データ配置未決定な抽象化された多重ループ処理の各ループネスト順序に対して、階層プログラムA1とループ化情報A2と変数属性分類部６の算出結果とに基づいて高速化評価値を算出する。そして、ループネスト順序決定部３は、設定された閾値以上となる高速化評価値を持つ1つ以上のループネスト順序を、高速化ループネスト順序として決定する（ステップS202）。
続いて、データ配置決定部４は、1つ以上の高速化ループネスト順序のそれぞれに対して、ループ化によって拡張された変数のメインメモリ上のデータ配置を、データアクセスコスト評価値を用いて決定する（ステップS103）。
続いて、初期化位置決定部８は、最初のループ内アクセスにおける処理フローの到達確率が既定値以下の変数の初期化処理を、その変数へのアクセス直前に移動する。例えば、初期化位置決定部８は、ループ内のステートメントへの処理フローの到達確率が既定値以下の場合、そのステートメントで使用する変数を初期化する初期化ステートメントを、その変数へのアクセス直前に移動する。初期化位置決定部８は、初期化関数も初期化位置に依存して作成する（ステップS401）。
続いて、プログラム出力部５は、1つ以上のループネスト順序とデータ配置を表し、到達確率に応じて初期化処理の実行位置が変更されたプログラムを出力する（ステップS104）。
【００５３】
次に、本実施形態の効果について説明する。
本実施形態では、ループネスト順序列挙部２は、プログラム中のループネスト順序の入れ替え可能なループネスト構造を発見する。ループネスト順序決定部３は、各ループネスト構造について分岐を考慮してベクトル化効率の良いループネスト順序を自動的に決定する。データ配置決定部４は、決定されたループネスト順序でのベクトル化時のデータのメインメモリからのロードコストを小さくするデータ配置に自動的に決定する。そして、初期化位置決定部８は、最初のループ内アクセスにおける到達確率が閾値以下の変数の初期化処理を、その変数へのアクセス直前に移動する。
このため、到達確率の低いステートメントで利用される変数についての初期化処理を、該変数を利用するステートメントの処理の直前に行うことで、初期化処理コストを減らすことができる。このため、例えば、入力データに依存して分岐確率が変わることでベクトル化による高速化効果と初期化処理コスト削減による高速化効果が異なる複数種類の照合プログラムを短期間で生成することが可能になる。
【００５４】
次に、本実施形態の変形例について説明する。
初期化位置決定部８が、第１実施形態や第３実施形態で用いられてもよい。
【００５５】
［第５の実施の形態］
図３５は、本発明の第５実施形態のプログラム生成装置を示した図である。
第５実施形態のプログラム生成装置が、図１に示した第１実施形態のプログラム生成装置と異なる点は、第５実施形態のプログラム生成装置が、第１実施形態のプログラム生成装置に加えて、ループ回転数変更部９をさらに含む点である。以下、第５実施形態のプログラム生成装置について、第１実施形態のプログラム生成装置と異なる点を中心に説明する。
ループ回転数変更部９は、最内ループのループ回転数をベクトル化によって余りループが発生しないループ回転数に変更する機能を有する。ループ回転数変更部９は、ループネスト順序列挙部２が列挙したループネスト順序ごとに、ループネスト順序で最内ループのループ回転数を、最内ループの全てをベクトル演算で実行可能なループ回転数に変更する。
本実施形態では、ループ回転数変更部９は、最内ループのループ回転数を、1回のベクトル演算にまとめられるループ数である「8」の倍数でありかつ最内ループのループ回転数よりも大きい数のうち、最も小さい数に変更する。
【００５６】
次に、動作を説明する。
図３６は、本実施形態の動作を説明するためのフローチャートである。
ループネスト順序列挙部２は、階層プログラムA1を参照し、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を列挙する。さらに、ループ回転数変更部９は、各ループネスト順序での最内ループのループ回転数を、ベクトル化によって余りループが発生しないループ回転数に変更する（ステップS501）。
続いて、ループネスト順序決定部３は、データ配置未決定な抽象化された多重ループ処理の各ループネスト順序に対して、階層プログラムA1とループ化情報A2とを用いて高速化評価値を算出する。そして、ループネスト順序決定部３は、設定された閾値以上となる1つ以上の高速化評価値を有するループネスト順序を、高速化ループネスト順序として決定する（ステップS102）。
続いて、データ配置決定部４は、1つ以上の高速化ループネスト順序のそれぞれに対して、ループ化によって拡張された変数のメインメモリ上のデータ配置を、データアクセスコスト評価値を用いて決定する（ステップS103）。
続いて、プログラム出力部５は、少なくとも1つ以上のループネスト順序とデータ配置を表すプログラムを出力する（ステップS104）。
【００５７】
次に、本実施形態の効果について説明する。
本実施形態では、ループネスト順序列挙部２は、プログラム中のループネスト順序の入れ替え可能なループネスト構造を発見する。ループ回転数変更部９は、各ループネスト順序での最内ループのループ回転数を、ベクトル化によって余りループが発生しないループ回転数に変更する。ループネスト順序決定部３は、最内ループのループ回転数がベクトル化によって余りループが発生しないループ回転数となっている複数のループネスト順序のうち、ベクトル化効率の良いループネスト順序を自動的に決定する。データ配置決定部４は、決定されたループネスト順序でのベクトル化時のデータのメインメモリからのロードコストを小さくするデータ配置を自動的に決定する。プログラム出力部５は、決定されたループネスト順序およびデータ配置を採用したプログラムを生成する。
このため、ベクトル化効率を高めることができ、例えな、照合プログラムを短期間で生成することが可能になる。
【００５８】
次に、本実施形態の変形例について説明する。
ループ回転数変更部９が、第２実施形態や第３実施形態や第４実施形態で用いられてもよい。
【００５９】
［第６の実施の形態］
図３７は、本発明の第６実施形態のプログラム生成装置を示した図である。
第６実施形態のプログラム生成装置が、図１に示した第１実施形態のプログラム生成装置と異なる点は、第６実施形態のプログラム生成装置が、第１実施形態のプログラム生成装置に加えて、アライメント考慮データ配置部１０をさらに含む点である。以下、第６実施形態のプログラム生成装置について、第１実施形態のプログラム生成装置と異なる点を中心に説明する。
アライメント考慮データ配置部１０は、データ配置決定部４に含まれる。アライメント考慮データ配置部１０は、最内ループのループ誘導変数でアクセスされるデータについて、ベクトル化のためにメモリアライメントが取れるように、最内ループ誘導変数でアクセスされるデータの数を拡張して配置する。アライメント考慮データ配置部１０は、図３７に示したようにデータ配置決定部４に含まれてもよいし、含まれなくてもよい。
メインメモリ上の64Bの倍数のアドレスに、ベクトル化するデータ（本実施形態では、8要素を1つにまとめたデータ。以下「連続する一群のデータ」とも称する）の先頭がない場合、ベクトルロード命令の実行が低速になることが知られている。ここで、64Bはバイト境界の一例である。連続する一群のデータは、最内側ループのループ誘導変数でアクセスされる複数のデータのうち、ベクトル演算で一度に処理される連続する一群のデータである。
本実施形態では、これを避けるために、バイト境界の倍数のアドレスには、連続する一群のデータのいずれかにおける先頭のデータが位置するように、該変数のデータの数を規定する配列サイズを変更する。
本実施形態では、アライメント考慮データ配置部１０は、最内側ループのループ誘導変数でアクセスされる複数のデータをメインメモリに配列したときに、一群のデータがバイト境界を跨がないように、該複数のデータのデータ数を調整する。
【００６０】
図３８は、アライメント考慮データ配置部１０の機能を説明するための図である。
図３８の左側のデータ数増加前プログラムにおいて変数f_aのデータ配置を示す配列f_a[10][15]では、図３９に示すように、メインメモリ上で64Bの倍数となるアドレスに、ベクトル化するデータ（連続する一群のデータ）の先頭が位置しないケースが生じる。このため、このデータ数（配列f_a[10][15]で定義されるデータ数）では、プログラムの実行が低速となる。
そこで、アライメント考慮データ配置部１０は、図３８および図４０に示すように、配列f_a[10][15]に、アクセスされない要素（データ）を追加することで、配列f_a[10][15]を配列f_a[10][16]に変更する。このため、メインメモリ上で64Bの倍数となるアドレスには、ベクトル化するデータ（連続する一群のデータ）の先頭の要素（データ）が位置するようになる。
【００６１】
次に、動作を説明する。
図４１は、本実施形態の動作を説明するためのフローチャートである。
ループネスト順序列挙部２は、階層プログラムA1を参照し、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を列挙する（ステップS101）。
続いて、ループネスト順序決定部３は、データ配置未決定な抽象化された多重ループ処理の各ループネスト順序に対して、階層プログラムA1とループ化情報A2とを用いて高速化評価値を算出する。そして、ループネスト順序決定部３は、設定された閾値以上となる高速化評価値を有する1つ以上のループネスト順序を、高速化ループネスト順序として決定する（ステップS102）。
続いて、データ配置決定部４は、1つ以上の高速化ループネスト順序のそれぞれに対して、ループ化によって拡張された変数のメインメモリ上のデータ配置を、データアクセスコスト評価値を用いて決定する。続いて、アライメント考慮データ配置部１０は、最内ループ誘導変数でアクセスされるデータについて、ベクトル化のためにメモリアライメントが取れるようにデータ数を拡張して配置する（ステップS601）。
続いて、プログラム出力部５は、1つ以上のループネスト順序とデータ配置を表すプログラムを出力する（ステップS104）。
【００６２】
次に、本実施形態の効果について説明する。
本実施形態では、ループネスト順序列挙部２は、プログラム中のループネスト順序の入れ替え可能なループネスト構造を発見する。ループネスト順序決定部３は、対象のループネスト構造に対してベクトル化効率の良いループネスト順序を自動的に決定する。データ配置決定部４は、決定されたループネスト順序でのベクトル化時のデータのメインメモリからのロードコストを小さくするデータ配置を自動的に決定する。そして、アライメント考慮データ配置部１０は、メモリアライメントをあわせることで効率の良いロード命令を生成可能とする。
このため、例えば、短期間で高速実行可能な照合プログラムを生成することが可能になる。
【００６３】
次に、本実施形態の変形例について説明する。
アライメント考慮データ配置部１０が、第２実施形態や第３実施形態や第４実施形態や第５実施形態で用いられてもよい。
【００６４】
［第７の実施の形態］
図４２は、本発明の第７実施形態のプログラム生成装置を示した図である。
第７実施形態のプログラム生成装置が、図１に示した第１実施形態のプログラム生成装置と異なる点は、第７実施形態のプログラム生成装置が、第１実施形態のプログラム生成装置に加えて、ループ拡張変数判断部１１をさらに含む点である。以下、第７実施形態のプログラム生成装置について、第１実施形態のプログラム生成装置と異なる点を中心に説明する。
ループ拡張変数判断部１１は、情報生成部の一例である。
ループ拡張変数判断部１１は、プログラム構造とデータ配置が決定済みの原始プログラムを受け付ける。ループ拡張変数判断部１１は、原始プログラムについて、字句解析・構文解析・データ依存解析・ループ解析を行う。ループ拡張変数判断部１１は、解析の結果、原始プログラムに多重ループが存在すると判断した場合、その多重ループの各々のループに対応するプログラム情報（階層プログラム）とループ化情報（図２参照）とを生成する。
【００６５】
ここで、ループ拡張変数判断部１１が有する機能について説明する。
図４３、図４４および図４５は、ループ拡張変数判断部１１が有する機能を説明するための図である。
ループ拡張変数判断部１１は、プログラム構造とデータ配置とが決定済みの原始プログラムを解析して、原始プログラムからループネスト構造を有するループ部分を検出する。
図４３に示した例では、ループ拡張変数判断部１１は、ループネスト構造４３ａを検出する。
続いて、ループ拡張変数判断部１１は、ループネスト構造４３ａの中間表現（例えば、図４３に示した中間表現４３ｂ）を生成する。
続いて、ループ拡張変数判断部１１は、ループネスト構造の階層を検出する。
図４３に示した例では、ループ拡張変数判断部１１は、ループネスト構造４３ａにfor文のネストが存在するので、ループネスト構造４３ａが2重（2階層）ループであることを検出する。
続いて、ループ拡張変数判断部１１は、ループネスト構造の階層数に応じた数のループ化情報および階層プログラムを生成する。なお、ここで生成されるループ化情報および階層プログラムには、数値等の情報は記載されていない。
例えば、図４３に示したループネスト構造４３ａについて、ループ拡張変数判断部１１は、内側ループに対応するループ化情報1（Loop1）および階層プログラム1（Layer1）と、外側ループに対応するループ化情報2（Loop2）および階層プログラム2（Layer2）と、を生成する。
続いて、ループ拡張変数判断部１１は、ループネスト構造の各ループ文から、ループ回転数とループ誘導変数を検出する。
例えば、ループ拡張変数判断部１１は、ループネスト構造４３ａの内側（最内側）ループ文から、ループ誘導変数「i2」とループ回転数「10」を検出する。また、ループ拡張変数判断部１１は、ループネスト構造４３ａの外側ループ文から、ループ誘導変数「i1」とループ回転数「1000」を検出する。
続いて、ループ拡張変数判断部１１は、各ループの回転数を、各ループ化情報に設定する。
例えば、ループ拡張変数判断部１１は、内側ループのループ回転数「10」をループ化情報1（Loop1）の回転数の欄に設定し（図４３参照）、外側ループのループ回転数「1000」をループ化情報2（Loop2）の回転数の欄に設定する（図４４参照）。
続いて、ループ拡張変数判断部１１は、各ループ文のループボディを解析して、ループ誘導変数でアクセスされる変数を特定する。
例えば、ループ拡張変数判断部１１は、内側ループについてループ誘導変数i2でアクセスされる変数「s_a，f_a」を特定し、外側ループについてループ誘導変数i1でアクセスされる変数「d，f_a」を特定する。
続いて、ループ拡張変数判断部１１は、各ループにおいてループ誘導変数でアクセスされる変数を、各ループ化情報の拡張の欄に設定する。
例えば、ループ拡張変数判断部１１は、内側ループの変数「s_a，f_a」をループ化情報1（Loop1）の拡張の欄に設定し（図４３参照）、外側ループの変数「d，f_a」をループ化情報2（Loop2）の拡張の欄に設定する（図４４参照）。
続いて、ループ拡張変数判断部１１は、各ループ文のループボディを解析して、ループ誘導変数でアクセスされずに加算される変数を特定する。
例えば、ループ拡張変数判断部１１は、内側ループにおいてループ誘導変数i2でアクセスされずに加算される変数dを特定する。なお、外側ループにおいてループ誘導変数i1でアクセスされずに加算される変数は存在しないので、ループ拡張変数判断部１１は、その変数は無いと判断する。
続いて、ループ拡張変数判断部１１は、各ループにおいてループ誘導変数でアクセスされずに加算される変数を、各ループ化情報のリダクションの欄に設定する。
例えば、ループ拡張変数判断部１１は、内側ループの変数「d」をループ化情報1（Loop1）のリダクションの欄に設定し（図４３参照）、ループ化情報2（Loop2）の拡張の欄には「無し」設定する（図４４参照）。
ループ拡張変数判断部１１は、全てのネストループのループ化情報の作成が完了したら、ループネスト構造の中間表現内のBBのうち、ループ誘導変数でアクセスされる変数をスカラ変数に置き換えた階層プログラム情報のBBを作成する。
例えば、ループ拡張変数判断部１１は、中間表現４３ｂ内のBB（図４５に示した「d[i1] += s_a[i2] * f_a[i1][i2]」の部分）のうち、ループ誘導変数i2，i1でアクセスされる変数をスカラ変数に置き換えた階層プログラム1（Layer1）のBB1「d=s_a*f_a」を作成する。
以下、ループ拡張変数判断部１１は、原始プログラム、ループ化情報1（Loop1）、ループ化情報2（Loop2）および中間表現４３ｂ等を参照して、階層プログラム1（Layer1）において、L1の欄に「無し」を、CFの欄に「BB1」とし、変数リストの欄に「d:int，s_a:int，f_a:int」を設定する。
また、ループ拡張変数判断部１１は、原始プログラム、ループ化情報1（Loop1）、ループ化情報2（Loop2）および中間表現４３ｂ等を参照して、階層プログラム2（Layer2）において、BBの欄に「無し」を、L1の欄に「Layer1+Loop1」を、CFの欄に「L1」を、変数リストの欄に「d:int，s_a:int，f_a:int」を設定する。
【００６６】
次に、動作を説明する。
図４６は、本実施形態の動作を説明するためのフローチャートである。
ループ拡張変数判断部１１は、プログラム構造とデータ配置が決定済みの原始プログラムを字句解析・構文解析・データ依存解析・ループ解析し、原始プログラム内の多重ループに対応する階層プログラムA1およびループ化情報A2を生成する（ステップS701）。
続いて、ループネスト順序列挙部２は、階層プログラムA1を参照し、入れ替え可能なループネスト構造について、互いに異なるループネスト順序となる複数のプログラム構造を列挙する（ステップS101）。
続いて、ループネスト順序決定部３は、データ配置未決定な抽象化された多重ループ処理の各ループネスト順序に対して、階層プログラムA1とループ化情報A2とを用いて高速化評価値を算出する。そして、ループネスト順序決定部３は、設定された閾値以上となる高層化評価値を有する1つ以上のループネスト順序を、高速化ループネスト順序として決定する（ステップS102）。
続いて、データ配置決定部４は、1つ以上の高速化ループネスト順序のそれぞれに対して、ループ化によって拡張された変数のメインメモリ上のデータ配置を、データアクセスコスト評価値を用いて決定する（ステップS103）。
続いて、プログラム出力部５は、1つ以上のループネスト順序とデータ配置を表すプログラムを出力する（ステップS104）。
【００６７】
次に、本実施形態の効果について説明する。
本実施形態では、ループ拡張変数判断部１１は、プログラム構造とデータ配置が決定済みの原始プログラム内の多重ループに対応する階層プログラムとループ化情報を生成する。ループネスト順序列挙部２は、ループ拡張変数判断部１１が生成した階層プログラムとループ化情報を参照して、ループネスト順序の入れ替え可能なループネスト構造を発見する。ループネスト順序決定部３は、対象のループネスト構造に対してベクトル化効率の良いループネスト順序を自動的に決定する。データ配置決定部４は、決定されたループネスト順序でのベクトル化時のデータのメインメモリからのロードコスト（例えば、メインメモリからのロード回数）を小さくするデータ配置を自動的に決定する。プログラム出力部５は、決定されたループネスト順序およびデータ配置を採用したプログラムを生成する。このため、プログラム構造とデータ配置が決定済みの原始プログラムを、短期間で高速実行可能なプログラムに変更することが可能になる。
【００６８】
次に、本実施形態の変形例について説明する。
ループ拡張変数判断部１１は、生成装置１に内蔵されてもよい。
また、ループ拡張変数判断部１１は、第２実施形態や第３実施形態や第４実施形態や第５実施形態や第６実施形態で用いられてもよい。
【００６９】
上記各実施形態は、生体認証処理や物体認識処理などの照合プログラムのチューニングといった用途に適用できる。また、複数の照合処理のチューニング実装が入力データに依存して最適な実装が決まらない時に複数パターンのチューニング実装を自動生成することで最適な実装をユーザが選択するといった用途にも適用可能である。
【００７０】
上記各実施形態において、生成装置１は、コンピュータにて実現されてもよい。この場合、コンピュータは、コンピュータにて読み取り可能な記録媒体に記録されたプログラムを読込み実行して、生成装置１４が有する機能を実行する。記録媒体は、例えば、CD-ROM（Compact Disk Read Only Memory）である。記録媒体は、CD-ROMに限らず適宜変更可能である。
以上説明した各実施形態において、図示した構成は単なる一例であって、本発明はその構成に限定されるものではない。
【符号の説明】
【００７１】
１        生成装置
２        ループネスト順序列挙部
３        ループネスト順序決定部
４、４ａ  データ配置決定部
５、５ａ  プログラム出力部
６        変数属性分類部
７        打ち切り処理判断部
８        初期化位置決定部
９        ループ回転数変更部
１０        アライメント考慮データ配置部
１１        ループ拡張変数判断部
Ａ        入力情報
Ａ１      階層プログラム
Ａ２      ループ化情報
【図１】
2016110259.tif 000003
【図２】
2016110259.tif 000004
【図３】
2016110259.tif 000005
【図４】
2016110259.tif 000006
【図５】
2016110259.tif 000007
【図６】
2016110259.tif 000008
【図７】
2016110259.tif 000009
【図８Ａ】
2016110259.tif 000010
【図８Ｂ】
2016110259.tif 000011
【図９Ａ】
2016110259.tif 000012
【図９Ｂ】
2016110259.tif 000013
【図１０】
2016110259.tif 000014
【図１１】
2016110259.tif 000015
【図１２】
2016110259.tif 000016
【図１３】
2016110259.tif 000017
【図１４】
2016110259.tif 000018
【図１５】
2016110259.tif 000019
【図１６】
2016110259.tif 000020
【図１７】
2016110259.tif 000021
【図１８】
2016110259.tif 000022
【図１９】
2016110259.tif 000023
【図２０】
2016110259.tif 000024
【図２１】
2016110259.tif 000025
【図２２】
2016110259.tif 000026
【図２３】
2016110259.tif 000027
【図２４】
2016110259.tif 000028
【図２５】
2016110259.tif 000029
【図２６】
2016110259.tif 000030
【図２７】
2016110259.tif 000031
【図２８】
2016110259.tif 000032
【図２９】
2016110259.tif 000033
【図３０】
2016110259.tif 000034
【図３１】
2016110259.tif 000035
【図３２】
2016110259.tif 000036
【図３３】
2016110259.tif 000037
【図３４】
2016110259.tif 000038
【図３５】
2016110259.tif 000039
【図３６】
2016110259.tif 000040
【図３７】
2016110259.tif 000041
【図３８】
2016110259.tif 000042
【図３９】
2016110259.tif 000043
【図４０】
2016110259.tif 000044
【図４１】
2016110259.tif 000045
【図４２】
2016110259.tif 000046
【図４３】
2016110259.tif 000047
【図４４】
2016110259.tif 000048
【図４５】
2016110259.tif 000049
【図４６】
2016110259.tif 000050
【図４７】
2016110259.tif 000051
【図４８】
2016110259.tif 000052
【図４９】
2016110259.tif 000053