(57)【要約】【課題】ループ最適化の制約式を満たす複数の解から適切な解を選択できるようにする。【解決手段】コンピュータ１０は、ソースコード１１ａに含まれるループ処理の記述に基づいて、何回目の繰り返し処理なのかを示す回数値ごとに、該回数値に対応する１ループ分の命令１を並べて表示する。またコンピュータ１０は、データの依存関係を有する命令対の間の依存関係を表示する。さらにコンピュータ１０は、依存関係のない複数の命令を含む命令群２の指定入力があると、命令群２を同一プロセッサで実行させた場合の、キャッシュメモリの利用効率などの評価値を算出し、表示する。そしてコンピュータ１０は、確定入力があると、ソースコード１１ａをコンパイルすると共に、ループ処理について、命令群２を同一プロセッサで実行させるという制約の下で、凸多面体モデルを利用したループ最適化を行う。【選択図】図１
2017004281.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
ソースコードに含まれるループ処理の記述に基づいて、何回目の繰り返し処理なのかを示す回数値ごとに、該回数値に対応する１ループ分の命令を並べて表示し、
データの依存関係を有する命令対の間の依存関係を表示し、
依存関係のない複数の命令を含む命令群を、同一プロセッサで実行するように指定する指定入力があると、前記命令群を同一プロセッサで実行させた場合の、キャッシュメモリの利用効率を示す第１の評価値、使用するデータの整列度合いを示す第２の評価値、および並列実行時のスレッド数を示す第３の評価値を算出し、
算出した前記第１の評価値、前記第２の評価値、および前記第３の評価値を表示し、
前記命令群を確定させる確定入力があると、前記ソースコードをコンパイルすると共に、前記ループ処理について、前記命令群を同一プロセッサで実行させるという制約の下で、凸多面体モデルを利用したループ最適化を行う、
処理を実行させるコンパイルプログラム。
【請求項２】
前記コンピュータに、さらに、
前記指定入力に応じて、指定された前記命令群を同一プロセッサで実行できるかどうかにより、指定の妥当性を評価し、
前記評価の結果を表示する、
処理を実行させる請求項１記載のコンパイルプログラム。
【請求項３】
前記妥当性の評価では、前記命令群内のすべての命令を同一プロセッサで実行することはできないが、前記命令群内の部分集合を構成する複数の命令について同一プロセッサで実行可能な場合、前記命令群のうちの、前記部分集合に含まれない命令を特定し、
前記評価の結果の表示では、特定した該命令についてエラー表示を行う、
請求項２記載のコンパイルプログラム。
【請求項４】
前記ループ最適化では、前記命令群内のすべての命令を同一プロセッサで実行することはできないが、前記命令群内の部分集合を構成する複数の命令について同一プロセッサで実行可能な場合、前記ループ処理について、前記部分集合を構成する複数の命令を同一プロセッサで実行させるという制約の下で、凸多面体モデルを利用したループ最適化を行う、
請求項１乃至３のいずれかに記載のコンパイルプログラム。
【請求項５】
前記第２の評価値は、同一プロセッサで実行する処理で使用するデータの配列が、ＳＩＭＤ（Single Instruction Multiple Data）命令により処理しやすいデータ配列であるほど、高い値とする、
請求項１乃至４のいずれかに記載のコンパイルプログラム。
【請求項６】
コンピュータが、
ソースコードに含まれるループ処理の記述に基づいて、何回目の繰り返し処理なのかを示す回数値ごとに、該回数値に対応する１ループ分の命令を並べて表示し、
データの依存関係を有する命令対の間の依存関係を表示し、
依存関係のない複数の命令を含む命令群を、同一プロセッサで実行するように指定する指定入力があると、前記命令群を同一プロセッサで実行させた場合の、キャッシュメモリの利用効率を示す第１の評価値、使用するデータの整列度合いを示す第２の評価値、および並列実行時のスレッド数を示す第３の評価値を算出し、
算出した前記第１の評価値、前記第２の評価値、および前記第３の評価値を表示し、
前記命令群を確定させる確定入力があると、前記ソースコードをコンパイルすると共に、前記ループ処理について、前記命令群を同一プロセッサで実行させるという制約の下で、凸多面体モデルを利用したループ最適化を行う、
コンパイル方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイルプログラム、およびコンパイル方法に関する。
【背景技術】
【０００２】
コンピュータに実行させるプログラムは、例えば高級言語によって作成され、コンパイラでコンパイルすることで、コンピュータで実行可能な形式に変換される。コンパイラでは、ソースコードから機械語への変換が行われると共に、実行時間やメモリ使用量が最小化されるように、最適化処理が行われる。
【０００３】
コンパイラによる最適化処理の１つとして、凸多面体モデルを利用したループ最適化手法が存在する。この手法では、ループ処理について、データを生成する命令とそのデータを使用する命令との関係が制約式で表され、多数の制約式を満たすプログラムが生成される。制約式は、最適化過程で連立方程式あるいは連立不等式である。
【０００４】
なお、ループ最適化に関連する技術としては、例えば２元有限体の直積を要素とする系列を求める最適化問題の解を探索する技術がある。また、評価関数が凸関数である要素を連携させて、全体で最適化する技術もある。また、コンパイラによる最適化をユーザが緻密に制御することを可能とする技術もある。また、情報処理システムで用いるシステムパラメータを、高速かつ高精度に最適化する技術もある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−１５０４６５号公報
【特許文献２】国際公開第２０１２／１６０９７８号
【特許文献３】特開２００６−１１４０６９号公報
【特許文献４】特開２０１３−８９０２５号公報
【非特許文献】
【０００６】
【非特許文献１】Ａ．Ｖ．エイホ，Ｒ．セシィ，Ｊ．Ｄ．ウルマン，Ｍ．Ｓ．ラム、「コンパイラ−原理・技法・ツール（第２版）」、サイエンス社、２００９年６月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
コンパイラによる凸多面体モデルを利用したループ最適化手法では、ループ最適化の際に、多数の制約式（最適化過程で連立方程式あるいは連立不等式）の解が計算される。なお、連立方程式あるいは連立不等式の解は、一般的には複数存在する。複数の解のうち、コンパイラがどの解を選ぶかににより、プログラムの処理効率が変わる。例えばコンパイラは、内部でヒューリスティックを利用したり、各種の見積もり計算を行ったりして、適切と思われる１つの解を選択する。
【０００８】
しかし、生成されるプログラムの処理効率の善し悪しは、生成されたプログラムの実行環境など様々な要因に依存する。そのため、一定の手法で選択した解が常に最良の解となるわけではない。一般にコンパイラは、プログラムの実行時に決まる情報、例えばメモリの使用状況やデータ整列情報などについての情報を持たない。そのためループ最適化の制約式を満たす複数の解の中から、プログラムの使用環境などの様々な要因に応じた最適な解を、コンパイラに自動選択させるのは困難である。
【０００９】
１つの側面では、本件は、ループ最適化の制約式を満たす複数の解から適切な解を選択できるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
１つの案では、コンピュータに、以下の処理を実行させるコンパイルプログラムが提供される。このコンパイルプログラムを実行するコンピュータは、ソースコードに含まれるループ処理の記述に基づいて、何回目の繰り返し処理なのかを示す回数値ごとに、該回数値に対応する１ループ分の命令を並べて表示する。次にコンピュータは、データの依存関係を有する命令対の間の依存関係を表示する。次にコンピュータは、依存関係のない複数の命令を含む命令群を、同一プロセッサで実行するように指定する指定入力があると、前記命令群を同一プロセッサで実行させた場合の、キャッシュメモリの利用効率を示す第１の評価値、使用するデータの整列度合いを示す第２の評価値、および並列実行時のスレッド数を示す第３の評価値を算出する。次にコンピュータは、算出した前記第１の評価値、前記第２の評価値、および前記第３の評価値を表示する。そしてコンピュータは、前記命令群を確定させる確定入力があると、前記ソースコードをコンパイルすると共に、前記ループ処理について、前記命令群を同一プロセッサで実行させるという制約の下で、凸多面体モデルを利用したループ最適化を行う。
【発明の効果】
【００１１】
１態様によれば、ループ最適化の制約式を満たす複数の解から適切な解を選択できる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態に係るコンピュータ構成例を示す図である。
【図２】第２の実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。
【図３】コンピュータのコンパイル機能を示すブロック図である。
【図４】ループ処理最適化処理の手順を示す図である。
【図５】最適化支援用の画面表示例を示す図である。
【図６】最適化支援処理の手順の一例を示すフローチャートである。
【図７】妥当性評価処理の手順の一例を示す図である。
【図８】ループ処理を含むプログラムの第１の例を示す図である。
【図９】繰り返し空間を表すグラフの一例を示す図である。
【図１０】グループ選択後のグラフの例を示す図である。
【図１１】グループ化のエラー表示の第１の例を示す図である。
【図１２】グループ化のエラー表示の第２の例を示す図である。
【図１３】ループ処理が最適化されたプログラムの一例を示す図である。
【図１４】ループ処理を含むプログラムの第２の例を示す図である。
【図１５】ループ変数が複数存在する場合のデータ依存関係のグラフの例を示す図である。
【図１６】ループ処理の繰り返し空間の第１の例を示す図である。
【図１７】ループ処理の繰り返し空間の第２の例を示す図である。
【図１８】グループ化するインスタンスの第１の選択例を示す図である。
【図１９】グループ化するインスタンスの第２の選択例を示す図である。
【発明を実施するための形態】
【００１３】
以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
第１の実施の形態は、凸多面体モデルを利用したループ最適化の際に、最適化の制約を満たす複数の解の中から、ユーザの意図を反映させた解を選択可能とし、選択した解に基づくループ最適化を行うものである。ユーザの意図を反映させることで、複数の解のうちの適切な解を用いたループ最適化が可能となる。
【００１４】
図１は、第１の実施の形態に係るコンピュータの構成例を示す図である。コンピュータ１０は、記憶装置１１、演算装置１２、および表示装置１３を有する。
記憶装置１１は、ソースコード１１ａを記憶する。ソースコード１１ａは、例えば高級言語で記述されており、ループ処理を含んでいる。
【００１５】
演算装置１２は、ソースコード１１ａをコンパイルし、機械語による実行プログラムを生成する。演算装置１２は、ソースコード１１ａをコンパイルする際に、ループ処理の最適化を行う。ループ処理の最適化は、例えば凸多面体モデルを利用して行われる。
【００１６】
また、演算装置１２は、凸多面体モデルを利用したループ最適化の際に、最適化の制約を満たす複数の解のうち、適切な解をユーザが容易に選択できるようにする。すなわち、演算装置１２は、ソースコード１１ａのコンパイル時に、以下の処理を行う。
【００１７】
まず演算装置１２は、ソースコード１１ａに含まれるループ処理の記述に基づいて、何回目の繰り返し処理なのかを示す回数値ごとに、該回数値に対応する１ループ分の命令１を並べて、表示装置１３のデータ依存関係表示部１３ａに表示させる（ステップＳ１）。例えば演算装置１２は、横軸に繰り返し処理の回数値を設定し、縦軸の方向に、各回数値に対する１ループ分の命令１を示すオブジェクト（図１では丸印）を配置する。
【００１８】
次に演算装置１２は、ソースコード１１ａを解析して、データの依存関係を有する２つの命令間の依存関係を、表示装置１３のデータ依存関係表示部１３ａに表示させる（ステップＳ２）。例えば、２つの命令のうちの一方の命令で生成したデータを、他方の命令で参照する場合、当該２つの命令間に依存関係が存在する。例えば演算装置１２は、データの依存関係がある２つの命令それぞれに対応するオブジェクト間を結ぶ線を表示する。線は、データを生成する命令からそのデータを参照する命令を示す矢印としてもよい。
【００１９】
次に演算装置１２は、依存関係のない複数の命令を含む命令群２を、同一プロセッサで実行するように指定する指定入力があると、その命令群２が同一プロセッサで実行させた場合の処理の効率化に関する評価値を算出する（ステップＳ３）。評価値は、例えば命令群２を同一プロセッサで実行させた場合の、キャッシュメモリの利用効率を示す第１の評価値１３ｂ、使用するデータの整列度合いを示す第２の評価値１３ｃ、および並列実行時のスレッド数を示す第３の評価値１３ｄである。第２の評価値１３ｃは、例えば、同一プロセッサで実行する処理で使用するデータの配列が、ＳＩＭＤ（Single Instruction Multiple Data）命令により処理しやすいデータ配列であるほど、高い値とする。各評価値を算出した後、演算装置１２は、算出した第１の評価値１３ｂ、第２の評価値１３ｃ、および第３の評価値１３ｄを、表示装置１３のデータ依存関係表示部１３ａに表示させる（ステップＳ４）。
【００２０】
そして演算装置１２は、命令群２を確定させる確定入力があると、命令群２を同一プロセッサで実行させるという制約の下、凸多面体モデルを利用したループ処理の最適化を行うことで、ソースコード１１ａをコンパイルする（ステップＳ５）。すなわち、演算装置１２は、凸多面体モデルを利用したループ処理の最適化における制約に、命令群２を同一プロセッサで実行させるという制約が追加され、すべての制約を満たすような解を算出する。演算装置１２は、算出した解に応じて、ループ処理の命令の並べ替えを行うことで、ループ最適化を行う。そして演算装置１２は、並べ替えられた命令を機械語に変換して、実行形式のプログラムを得る。
【００２１】
このようにして、ループ最適化の条件を満たす複数の解から適切な解を選択できる。すなわち、ソースコード１１ａのコンパイル時に、ユーザによる命令群２の指定に応じた制約を満たすように、ループ最適化が行われる。これは、ユーザは、命令群２に含める命令を指定することで、演算装置１２に対して、ループ最適化の条件を満たす複数の解のうちの特定の解を選択させることができることを意味する。
【００２２】
そして、指定された命令群２に応じた評価値が表示されるため、ユーザは、命令群２の指定の良否を容易に認識することができる。得られた評価値がユーザの要求を満たしていれば、ユーザが確定入力をすることで、演算装置１２により、そのとき指定されている命令群２を同一プロセッサで実行可能とする制約を満たすように、ループ処理が最適化され、実行形式のプログラムが生成される。生成されるプログラムは、ループ処理を効率的に実行できるプログラムであり、このようなプログラムの生成に適用したループ最適化の解は、複数の解のうちの適切な解である。
【００２３】
なお、演算装置１２は、命令群２の指定入力に応じて、指定された命令群２を同一プロセッサで実行できるかどうかにより、指定の妥当性を評価し、評価の結果を表示装置１３に表示させることもできる。これにより、命令群２の指定の誤りをユーザに知らせることができ、誤った構成の命令群２によってコンパイルが実行されることを抑止できる。
【００２４】
また、妥当性の評価において、命令群２内のすべての命令を同一プロセッサで実行することはできないが、命令群２内の部分集合を構成する複数の命令について同一プロセッサで実行可能な場合もあり得る。この場合、演算装置１２は、命令群２のうちの、部分集合に含まれない命令を特定し、特定した命令についてエラー表示を行ってもよい。これにより、命令群２の指定に誤りがあったときに、ユーザは、どの指定が誤りなのかを容易に把握することができる。
【００２５】
さらに演算装置１２は、指定された命令群２内のすべての命令を同一プロセッサで実行することはできないが、命令群２内の部分集合を構成する複数の命令について同一プロセッサで実行可能な場合にも、ループ最適化を実行してもよい。この場合、演算装置１２は、例えば、ループ処理について、部分集合を構成する複数の命令を同一プロセッサで実行させるという制約の下で、凸多面体モデルを利用したループ最適化を行う。これにより、ユーザがループ最適化の結果を正しくイメージできていない場合でも、ユーザの指定に近い内容でループ最適化を行うことができる。
【００２６】
なお、演算装置１２は、例えばコンピュータ１０が有するプロセッサである。また、記憶装置１１は、例えばコンピュータ１０が有するメモリまたはストレージ装置である。
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、コンパイラによる凸多面体モデルを利用したループ最適化を行う際に、ＧＵＩ（Graphical User Interface）を用いてユーザの意図を反映させるものである。
【００２７】
図２は、第２の実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。コンピュータ１００は、プロセッサ１０１によって装置全体が制御されている。プロセッサ１０１には、バス１０９を介してメモリ１０２と複数の周辺機器が接続されている。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、またはＤＳＰ（Digital Signal Processor）である。プロセッサ１０１がプログラムを実行することで実現する機能の少なくとも一部を、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現してもよい。
【００２８】
メモリ１０２は、コンピュータ１００の主記憶装置として使用される。メモリ１０２には、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０２には、プロセッサ１０１による処理に利用する各種データが格納される。メモリ１０２としては、例えばＲＡＭ（Random Access Memory）などの揮発性の半導体記憶装置が使用される。
【００２９】
バス１０９に接続されている周辺機器としては、ＨＤＤ（Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、機器接続インタフェース１０７およびネットワークインタフェース１０８がある。
【００３０】
ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、コンピュータ１００の補助記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、補助記憶装置としては、フラッシュメモリなどの不揮発性の半導体記憶装置（ＳＳＤ：Solid State Drive）を使用することもできる。
【００３１】
グラフィック処理装置１０４には、モニタ２１が接続されている。グラフィック処理装置１０４は、プロセッサ１０１からの命令に従って、画像をモニタ２１の画面に表示させる。モニタ２１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００３２】
入力インタフェース１０５には、キーボード２２とマウス２３とが接続されている。入力インタフェース１０５は、キーボード２２やマウス２３から送られてくる信号をプロセッサ１０１に送信する。なお、マウス２３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００３３】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク２４に記録されたデータの読み取りを行う。光ディスク２４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００３４】
機器接続インタフェース１０７は、コンピュータ１００に周辺機器を接続するための通信インタフェースである。例えば機器接続インタフェース１０７には、メモリ装置２５やメモリリーダライタ２６を接続することができる。メモリ装置２５は、機器接続インタフェース１０７との通信機能を搭載した記録媒体である。メモリリーダライタ２６は、メモリカード２７へのデータの書き込み、またはメモリカード２７からのデータの読み出しを行う装置である。メモリカード２７は、カード型の記録媒体である。
【００３５】
ネットワークインタフェース１０８は、ネットワーク２０に接続されている。ネットワークインタフェース１０８は、ネットワーク２０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００３６】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお、第１の実施の形態に示した装置も、図２に示したコンピュータ１００と同様のハードウェアにより実現することができる。
【００３７】
コンピュータ１００は、例えばコンピュータ読み取り可能な記録媒体に記録されたプログラムを実行することにより、第２の実施の形態の処理機能を実現する。コンピュータ１００に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、コンピュータ１００に実行させるプログラムをＨＤＤ１０３に格納しておくことができる。プロセッサ１０１は、ＨＤＤ１０３内のプログラムの少なくとも一部をメモリ１０２にロードし、プログラムを実行する。またコンピュータ１００に実行させるプログラムを、光ディスク２４、メモリ装置２５、メモリカード２７などの可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えばプロセッサ１０１からの制御により、ＨＤＤ１０３にインストールされた後、実行可能となる。またプロセッサ１０１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００３８】
このようなコンピュータ１００においてプログラムをコンパイルする際、凸多面体モデルを利用したループ処理の最適化が行われる。
図３は、コンピュータのコンパイル機能を示すブロック図である。コンピュータ１００は、記憶部１１０、コンパイラ１２０、および最適化支援部１３０を有する。
【００３９】
記憶部１１０は、ソースファイル１１１やオブジェクトファイル１１２を記憶する。ソースファイル１１１には、例えばＣ言語などの高級言語によって、プログラムが記述されている。オブジェクトファイル１１２には、機械語によるプログラムが記述されている。
【００４０】
コンパイラ１２０は、記憶部１１０内のソースファイル１１１をコンパイルし、オブジェクトファイル１１２を生成する。コンパイラ１２０は、コンパイルの際に、凸多面体モデルを利用したループ処理の最適化を行う。
【００４１】
最適化支援部１３０は、ＧＵＩを介したユーザからの操作に基づいて、コンパイラ１２０によるループ処理の最適化を支援する。例えば最適化支援部１３０は、対話的最適化制御用の画面上での、マウスなどの入力デバイスによる入力に応じ、インスタンスのグループ化を行う。インスタンスは、変数の値が特定された命令である。例えばユーザは、同一プロセッサで実行するインスタンスを同じグループに含めるように、入力を行う。
【００４２】
また最適化支援部１３０は、ユーザ指定のグループ化に対する妥当性を評価することもできる。最適化支援部１３０は、妥当性評価の結果、グループ化に誤りがある場合、エラーを表示させることができる。また最適化支援部１３０は、ユーザ指定のグループ化に対する各種評価指標による評価値を計算し、表示することもできる。
【００４３】
なお、図３に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。また、図３に示した各要素の機能は、例えば、その要素に対応するプログラムモジュールをコンピュータに実行させることで実現することができる。
【００４４】
次に、凸多面体モデルを利用したループ処理の最適化について詳細に説明する。凸多面体モデルを用いたループ最適化手法では、「同期無し並列性の抽出」と「同期有り並列性の抽出」とが行われる。
【００４５】
＜同期無し並列性の抽出＞
同期無し並列性の抽出には、例えば凸多面体解析パスで利用する内部データ構造の情報を利用したアフィン空間分割が用いられる。そして同期無し並列性に関する制約条件が作成される。制約条件の作成処理は以下の通りである。
【００４６】
まず、データ依存の存在するすべての文の対ＳとＴについて、同じ配列要素をアクセスすることを意味する制約集合を作成する。文Ｓのアクセスを（Ｘ，ＦS）、文Ｔのアクセスを（Ｙ，ＦT）とする。ここでＸ，Ｙはそれぞれ配列名を表す。２つのアクセスが同じ配列要素にアクセスする場合、次式が成り立つ。
【００４７】
【数１】
2017004281.tif 000003
【００４８】
ここでベクトルｉSとベクトルｉTは、それぞれ文Ｓ，Ｔのループ変数のベクトルである。ベクトルｉgvは、大域パラメータ変数のベクトルである。このとき，（Ｘ，ＦS）あるいは（Ｙ，ＦT）のどちらかもしくは両方が書き込み命令である場合に、データ依存が発生する可能性がある。この条件を書き換えると
【００４９】
【数２】
2017004281.tif 000004
【００５０】
となる。ここでＦ'SとＦ'Tは、ベクトル（ベクトルｉS，ベクトルｉT，ベクトルｉgv，１）Tの次元に合うように、それぞれＦSとＦTを拡張したものである。ガウスの消去法を使ってこの方程式を解くと、解は一般的に
【００５１】
【数３】
2017004281.tif 000005
【００５２】
となる。ここでＵは、有理数定数の行列である。ｔは自由変数のベクトルである。
文ＳのインスタンスのプロセッサｐSへの割り当てを
【００５３】
【数４】
2017004281.tif 000006
【００５４】
とし、文ＴのインスタンスのプロセッサｐTへの割り当てを
【００５５】
【数５】
2017004281.tif 000007
【００５６】
とすると、文Ｓと文Ｔを同じプロセッサで実行する条件ｐS＝ｐTは
【００５７】
【数６】
2017004281.tif 000008
【００５８】
となる。ここでＣSとＣTはそれぞれ文Ｓと文Ｔのスケジュール変数のベクトルである。式（６）の条件を書き換えると
【００５９】
【数７】
2017004281.tif 000009
【００６０】
となる。ここでＣ'SとＣ'Tとは、ベクトル（ベクトルｉS，ベクトルｉT，ベクトルｉgv，１）Tの次元に合うように、それぞれＣSとＣTを拡張したものである。アフィン空間分割は、データ依存関係にある文のインスタンスの実行を同一のプロセッサに割り当てる最適化である。その制約条件は、式（３）と式（７）を組み合わせた以下の式（８）
【００６１】
【数８】
2017004281.tif 000010
【００６２】
で表現できる。ここで求めるものはベクトルＣ'TとＣ'Sに関する制約なので、自由変数のベクトルｔは無視できる。したがって、
【００６３】
【数９】
2017004281.tif 000011
【００６４】
という制約が作成できる。
データ依存関係が存在するすべての文の集合と、すべてのアクセスの組み合わせから作成した式（９）の形式の制約をすべて結合することで、制約
【００６５】
【数１０】
2017004281.tif 000012
【００６６】
を作成できる。ここで、ベクトルｃはすべての文のスケジュール変数を含むベクトルであり、Ｅは定数行列である。
式（１０）を連立整数方程式として解くことによって、変数ベクトルの値を計算することができる。
【００６７】
＜同期有り並列性の抽出＞
同期有り並列性の抽出には、例えば凸多面体解析パスで利用する内部データ構造の情報を利用したアフィン時間分割が用いられる。そして同期有り並列性に関する制約条件が作成される。制約条件の作成処理は以下の通りである。
【００６８】
同期有り並列性の抽出における制約条件作成の手順は、式（３）の作成までは、同期無し並列性の抽出におけるアフィン空間分割と同等である。文Ｓのインスタンスの実行時刻ｔSを
【００６９】
【数１１】
2017004281.tif 000013
【００７０】
とし、文Ｔのインスタンスの実行時刻ｔTを
【００７１】
【数１２】
2017004281.tif 000014
【００７２】
とする。すると、文Ｓ以降に文Ｔを実行する条件ｔS≦ｔTは
【００７３】
【数１３】
2017004281.tif 000015
【００７４】
となる。ここでＣSとＣTはそれぞれ文Ｓと文Ｔのスケジュール変数のベクトルである。
式（１３）の条件を書き換えると
【００７５】
【数１４】
2017004281.tif 000016
【００７６】
となる。ここでＣ'SとＣ'Tは、ベクトル（ベクトルｉS，ベクトルｉT，ベクトルｉgv，１）Tの次元に合うようにそれぞれＣSとＣTを拡張したものである。各ループ変数のベクトルに対するループ繰り返し空間に関する制約条件とFarkasの補助定理を利用することにより、各文のスケジュール変数のベクトルについての不等式制約を作成することができる。データ依存関係が存在するすべての文の集合と、すべてのアクセスの組み合わせから作成した不等式の形式の制約をすべて結合することで、制約
【００７７】
【数１５】
2017004281.tif 000017
【００７８】
を作成できる。ここでベクトルｃはすべての文のスケジュール変数を含むベクトルであり、Ｅは定数行列である。
式（１５）を整数線形制約問題として解くことによって、変数ベクトルの値を計算することができる。
【００７９】
以上の手順で、各文Ｓにアフィン時間分割を適用する場合のスケジュール変数のベクトルｃの具体的な値を求めることができる。
以上のような「同期無し並列性の抽出」と「同期有り並列性の抽出」とのそれぞれで生成された制約問題の解に基づいて、ループ処理のパイプライン化などの最適化を行うことができる。ただし、ループ最適化には、以下のような課題がある。
【００８０】
コンパイラ１２０による凸多面体モデルを利用したループ最適化手法では、最適化過程で、連立方程式である式（１０）あるいは連立不等式である式（１５）を解く。このとき、各式の解は一般的には複数あり、コンパイラ１２０がどの解を選ぶのが適切なのかについて、明確な基準がない。アフィン時間分割の例では、解の選択方法によって、図１５の繰り返し空間をもつプログラムが図１６に示す繰り返し空間になるか、図１７に示す繰り返し空間になるかが決まる（図１５、図１６、図１７の詳細については後述する）。この問題についてコンパイラ１２０は内部でヒューリスティックを利用したり、各種の見積もり計算を行ったりして１つの解を選択する。しかし、最適化が適切かどうかは、最適化されたプログラムを実行する状況など、各種の要因に依存するので、予め規定された所定の基準を用いても、コンパイラ１２０が最も良い解を選択できるとは限らない。
【００８１】
また、複数の解の選択肢が存在するとしても、解の選択はコンパイラ１２０の内部で整数線形制約問題として実施される。そのため、コンパイラ１２０を利用するプログラマからは解の選択を制御することができないという問題がある。
【００８２】
さらに一般にコンパイラ１２０はプログラムの実行時に決まる情報、例えばメモリの使用状況やデータ整列情報などについての情報を持たない。それらの情報は性能向上に重要な場合があるが、コンパイラ１２０だけでは、それらの情報と凸多面体モデルを利用した最適化手法とを組み合わせることが難しい。
【００８３】
そこで第２の実施の形態では、最適化支援部１３０を設け、最適化支援部１３０とコンパイラ１２０とを連携動作させる。コンパイラ１２０は、最適化支援部１３０を利用して、コンパイル対象のプログラムにおけるループ処理の適切な最適化を実現する。
【００８４】
図４は、ループ処理最適化処理の手順を示す図である。まずユーザは、最適化前のプログラム３１（ソースコード）をコンパイラ１２０に入力し、プログラム３１に対して凸多面体モデルを利用したループ最適化を行う場合の最適化情報３２の作成を指示する。するとコンパイラ１２０が、プログラム３１に対して、凸多面体モデルを利用したループ最適化を行う（ステップＳ１１）。コンパイラ１２０は、ループ最適化の際に、最適化情報３２を生成する。最適化情報３２には、ループ最適化に関する制約式（連立方程式または連立不等式）や、データ依存グラフを表示するための情報が含まれる。コンパイラ１２０は、最適化支援部１３０に対して、生成した最適化情報３２を送信する。
【００８５】
ユーザは、最適化支援部１３０に対話的な入力を行い、最適化情報３２に基づいて、ループ処理に含まれる命令のインスタンスのグループ化を行う（ステップＳ１２）。例えば最適化支援部１３０は、プログラム３１に関するループの繰り返し空間とデータ依存関係とをモニタ２１に表示し、ユーザからの入力に従って凸多面体モデルによるループ最適化を支援する。例えば最適化支援部１３０は、ユーザの指定したインスタンスのグループを示すグループ化情報３３を、コンパイラ１２０に出力する。グループ化情報３３には、例えば、グループ化される各インスタンスがプログラム３１中のどの文に対応するのかを示す情報と、ループの繰り返し空間上での座標情報が含まれる。
【００８６】
コンパイラ１２０は、元のプログラム３１、最適化情報３２、および最適化支援部１３０が出力したグループ化情報３３を取得して、ユーザが指定した情報を生かしたループ最適化を行う（ステップＳ１３）。例えばグループ化情報３３に示されるグループに属するインスタンスを、同じプロセッサで実行するという制約の下、ループ最適化が行われる。そして最適化されたプログラム３４が出力される。
【００８７】
このようにして、最適化支援部１３０が出力したグループ化情報３３を反映したループ最適化を行うことができる。しかも、最適化支援部１３０は、ＧＵＩを介して、ユーザの指示を受けてグループ化を行うことができるため、ユーザの意図を反映させたループ最適化が行われることとなる。
【００８８】
図５は、最適化支援用の画面表示例を示す図である。最適化支援部１３０が表示する画面４０には、データ依存関係表示部４１、複数の評価値表示部４２〜４４、評価ボタン４５、リセットボタン４６、完了ボタン４７、および中止ボタン４８が含まれる。
【００８９】
データ依存関係表示部４１は、命令文のインスタンス間でのデータの依存関係の有無を示すグラフを表示する領域である。データ依存関係表示部４１には、ループの繰り返し空間と、インスタンス間のデータの依存関係とがグラフで表される。例えばデータ依存関係表示部４１には、ループ処理の繰り返し回数（ｉ）を横軸にして、各ループ処理における命令文のインスタンスを、縦方向に並べたグラフが表示される。図５の例では、命令文のインスタンスが白丸で表されている。またインスタンス間のデータ依存が、インスタンス間を接続する矢印で表現されている。ユーザは、例えば、データ依存関係表示部４１に表示されたインスタンス（データ依存関係表示部４１内の丸印）を選択することで、同一グループに含めるインスタンスを指定できる。
【００９０】
複数の評価値表示部４２〜４４それぞれには、インスタンスのグループ化結果を所定の評価指標で評価したときの、評価値が表示される。評価指標は、例えばキャッシュの利用効率の向上度合い、ＳＩＭＤ化の促進度合い、並列実行によるスレッド数の増加度合いなどである。
【００９１】
評価ボタン４５は、データ依存関係表示部４１内でのインスタンスのグループ化が、制約条件を満たすか否かの判定を指示するボタンである。評価ボタン４５が押下されると、最適化支援部１３０により、グループ化されたインスタンス群を同じプロセッサコアで実行することが、制約条件を満たすかどうかが評価される。制約条件が満たされない場合、データ依存関係表示部４１内で、不適合の原因となっているインスタンスが強調表示される。
【００９２】
リセットボタン４６は、グループ化するインスタンスの再選択を行うためのボタンである。リセットボタン４６が押下されると、最適化支援部１３０により、現在の選択中のインスタンスの選択状態が解除される。
【００９３】
完了ボタン４７は、グループ化を確定するためのボタンである。完了ボタン４７が押下されると、現在選択されているインスタンスのグループ化が確定し、最適化支援部１３０によるグループ化情報３３が出力される。
【００９４】
中止ボタン４８は、インスタンスのグループ化を中止するためのボタンである。中止ボタン４８が押下されると、最適化支援部１３０は、インスタンスのグループ化を行わずに画面４０を閉じる。
【００９５】
ユーザは、図５に示した画面４０を介して操作を行うことで、コンパイラ１２０に適切なループ最適化を実施させることができる。最適化支援部１３０は、画面４０を介した入力に応じて、最適化支援処理を実行する。
【００９６】
図６は、最適化支援処理の手順の一例を示すフローチャートである。
［ステップＳ１０１］最適化支援部１３０は、コンパイラ１２０から最適化情報３２を取得する。
【００９７】
［ステップＳ１０２］最適化支援部１３０は、入力された最適化情報３２から最適化対象のループの繰り返し空間とデータ依存関係とをグラフで表示する。例えば図５のデータ依存関係表示部４１に、グラフが表示される。
【００９８】
［ステップＳ１０３］最適化支援部１３０は、ユーザからの入力を待つ。すなわち最適化支援部１３０は、ユーザからの入力があれば、処理をステップＳ１０４に進め、ユーザからの入力がなければ、ステップＳ１０３の処理を繰り返すことで、ユーザからの入力を待つ。
【００９９】
［ステップＳ１０４］最適化支援部１３０は、入力内容を判断する。このときのユーザの入力の選択肢は、例えば次の２種類である。
１つ目は、インスタンスをグループ化する操作である。例えばユーザは、データ依存関係表示部４１に表示されている複数のインスタンスを、マウスなどの入力装置で指定する。最適化支援部１３０は、指定された複数のインスタンスを、グループ化対象のインスタンスとして認識する。
【０１００】
２つ目は、グループ化を中止する操作である。グループ化を中止する場合、ユーザは、
中止ボタン４８を押下する。
グループ化の操作が行われた場合、処理がステップＳ１０５に進められる。中止の操作が行われた場合、グループ化情報３３を生成せずに、最適化支援処理が終了する。
【０１０１】
［ステップＳ１０５］最適化支援部１３０は、ユーザにより、データ依存関係表示部４１内でグループ化するインスタンスが指定されるごとに、そのインスタンスについて、同一グループであることを視覚的に表示する。例えば最適化支援部１３０は、グループ化されたインスタンスを、他のインスタンスとは別の色で表示する。
【０１０２】
［ステップＳ１０６］最適化支援部１３０は、評価ボタン４５が押下されたか否かを判断する。評価ボタン４５が押下された場合、処理がステップＳ１０７に進められる。評価ボタン４５が押下されなければ処理がステップＳ１０５に進められ、グループ化するインスタンスの指定の受け付けと、指定されたインスタンスを含むグループの表示とが継続される。
【０１０３】
［ステップＳ１０７］最適化支援部１３０は、グループ化の作業を完了し、評価ボタン４５が押下されると、ユーザが選択したグループ化の妥当性を評価する。妥当性評価処理の詳細は後述する（図７参照）。
【０１０４】
［ステップＳ１０８］最適化支援部１３０は、妥当性の評価結果に応じて、処理を分岐させる。妥当性評価の結果は，次の３種類のいずれかになる。
第１の評価結果は、ユーザの選択したグループ化にエラーがないという評価結果である。このような評価結果が得られた場合、処理がステップＳ１１１に進められる。第２の評価結果は、ユーザの選択したグループ化の一部にエラーがあるという評価結果である。このような評価結果が得られた場合、処理がステップＳ１１０に進められる。第３の評価結果は、ユーザの選択したグループ化のすべてがエラーであるという評価結果である。このような評価結果が得られた場合、処理がステップＳ１０９に進められる。
【０１０５】
［ステップＳ１０９］最適化支援部１３０は、すべてエラーの場合には、グループ化されたすべてのインスタンスに対するエラー表示を行い、処理をステップＳ１０３に進める。
【０１０６】
［ステップＳ１１０］最適化支援部１３０は、一部のエラーの場合、エラーの原因となるインスタンスに対するエラー表示を行い、処理をステップＳ１１１に進める。すなわち、エラーが一部のみの場合、エラーとなったインスタンスの選択を無視することで、エラーのない場合と同様の処理に進められる。
【０１０７】
［ステップＳ１１１］最適化支援部１３０は、エラーがないか一部のエラーの場合、グループ化の結果について、評価指標ごとの評価値を計算し、評価値を表示する。
［ステップＳ１１２］最適化支援部１３０は、完了ボタン４７が押下されたか否かを判断する。完了ボタン４７が押下された場合、処理がステップＳ１１３に進められる。完了ボタン４７ではなくリセットボタン４６が押下された場合、処理がステップＳ１０３に進められる。
【０１０８】
［ステップＳ１１３］最適化支援部１３０は、グループ化情報３３を作成し、そのグループ化情報３３をコンパイラ１２０に対して出力する。これにより、コンパイル処理が継続される。
【０１０９】
このようにして、ユーザによる入力に応じたグループ化情報３３が、最適化支援部１３０によって作成される。
次に、グループ化の妥当性評価処理について詳細に説明する。
【０１１０】
図７は、妥当性評価処理の手順の一例を示す図である。
［ステップＳ１２１］最適化支援部１３０は、最適化情報３２に含まれる制約集合Ｅとグループ化情報３３とから、ユーザの指定したグループ化を意味する追加の制約集合Ａを作成する。
【０１１１】
［ステップＳ１２２］最適化支援部１３０は、グループ化前からある制約集合Ｅと、追加で作成された制約集合との論理積（Ｅ∧Ａ）となる解を求める。
［ステップＳ１２３］最適化支援部１３０は、ステップＳ１２２において解が存在するかどうかを判定する。解が存在する場合、処理がステップＳ１２４に進められる。解が存在しない場合、処理がステップＳ１２５に進められる。
【０１１２】
［ステップＳ１２４］最適化支援部１３０は、解が存在すれば、妥当性評価結果を「エラー無し」と判定して、処理を終了する。
［ステップＳ１２５］最適化支援部１３０は、解が存在しない場合、制約集合Ａから生成可能な部分集合ｂをすべて作成する。ここで、部分集合ｂの集合を、集合Ｂとする（ｂ∈Ｂ）。
【０１１３】
［ステップＳ１２６］最適化支援部１３０は、制約集合Ｅと部分集合ｂとの論理積に解が存在するという条件を満たす、最大のサイズの部分集合ｂを求める。
［ステップＳ１２７］最適化支援部１３０は、制約集合Ｅと部分集合ｂとの論理積に解が存在するという条件を満たす部分集合ｂが、少なくとも１つ存在するか否かを判断する。該当する部分集合ｂが存在する場合、処理がステップＳ１２８に進められる。該当する部分集合ｂが存在しない場合、処理がステップＳ１３０に進められる。
【０１１４】
［ステップＳ１２８］最適化支援部１３０は、妥当性評価結果を「一部エラー」とする。
［ステップＳ１２９］最適化支援部１３０は、制約集合Ａに含まれるインスタンスのうち、ステップＳ１２６で求められた最大のサイズの部分集合ｂに含まれないインスタンスを、エラーの原因と判定する。エラーの原因と判定されたインスタンスは、ステップＳ１１０の処理により、エラー表示（例えば×印の付与）が行われる。その後、妥当性評価処理が終了する。
【０１１５】
［ステップＳ１３０］最適化支援部１３０は、妥当性評価結果を「すべてエラー」とする。この場合、ステップＳ１０９の処理により、グループ化において選択されたすべてのインスタンスについてエラー表示が行われる。その後、妥当性評価処理が終了する。
【０１１６】
次に、制約集合Ｅについて説明する。コンパイラが生成する制約集合Ｅは、
【０１１７】
【数１６】
2017004281.tif 000018
【０１１８】
の形式をもつ。ここで△は＝（連立方程式の場合）あるいは≧（連立不等式の場合）である。ここで、Ｅは整数行列であり、ベクトルｃはコンパイラが求めるべき変数のベクトルである。また、最適化対象のループ内の文Ｓについて、それぞれスケジュール式
【０１１９】
【数１７】
2017004281.tif 000019
【０１２０】
が存在する。ここで、ベクトルｃSはベクトルｃに含まれる変数からなるベクトルであり、ベクトルｉSは文Ｓのイタレーション空間を表す変数ベクトルである。グループ化した点の座標情報を含む座標情報Ｇ内の各要素は、どの文の点であるか、また具体的な点の座標は何かを表す。例えば、文Ｓの座標情報であれば、
【０１２１】
【数１８】
2017004281.tif 000020
【０１２２】
の意味をもつ。ここで、ベクトルｇは位置情報を表す整数ベクトルである。この要素の情報から、追加の制約
【０１２３】
【数１９】
2017004281.tif 000021
【０１２４】
が得られる。ここでｔGはグループ全体を同じ時間に実行することを意味するパラメータ変数である。座標情報Ｇ内のすべての点に対して、これらの追加の制約集合Ａを作成することができる。制約集合Ａの各要素は
【０１２５】
【数２０】
2017004281.tif 000022
【０１２６】
の形式の制約である。元の問題の代わりに、追加の制約集合Ａと元の問題を結合した
【０１２７】
【数２１】
2017004281.tif 000023
【０１２８】
を解くことによって、アプリケーションプログラマが最適化支援部１３０で指定したグループ化に相当するループの最適化の解を選択することができる。
このようにして、コンパイラだけでは選択できない適切な解を用いたループ最適化を実現できる。またＧＵＩを利用して、テキストベースのツールでは指定困難な最適化を指示できる。さらに、ＧＵＩによるユーザからの入力が正確ではなくても、ユーザの要望に近い実行可能解を選択することで、最適化の可能性を広げることができる。
【０１２９】
以下、第２の実施の形態におけるループ最適化の具体例を説明する。
＜ループ最適化例１＞
説明をわかりやすくするため、簡単なループ処理を含むプログラムを想定する。
【０１３０】
図８は、ループ処理を含むプログラムの第１の例を示す図である。プログラム５１を最適化する場合、プログラム５１に対して、最適化支援部１３０によるデータ依存関係表示部４１に表示される、繰り返し空間を表すグラフは図９のようになる。
【０１３１】
図９は、繰り返し空間を表すグラフの一例を示す図である。図９において、丸印はループの繰り返し空間上での文の１つのインスタンスを示す。矢印は、文のインスタンス間のデータ依存関係の存在を示す。矢印の方向は、矢印が示す順序で各インスタンスを実行しなければならない制約を意味する。
【０１３２】
図８のプログラム５１から図９の表示を生成するための手順は次の通りである。図８に示すプログラム５１では、ループの回転数が変数ｎとなっている。この変数に対して、表示の大きさを考慮した適当な数値、例えばｎ＝７を定義する。図８のプログラムのループをｎ＝７として実行すると、文Ｓ1，Ｓ2，Ｓ3（プログラム５１中ではＳ１，Ｓ２，Ｓ３と表記）からは、それぞれ変数ｉが０から７まで変化したインスタンスが８個ずつ生成されることになる。例えば、文Ｓ1については（Ｓ1，０）、（Ｓ1，１）、（Ｓ1，２）、（Ｓ1，３）、（Ｓ1，４）、（Ｓ1，５）、（Ｓ1，６）、（Ｓ1，７）の８個のインスタンスが生成される。文Ｓ1を縦軸に、ｉの番号を横軸にした平面に、インスタンスを丸印で表示することで、図９の文Ｓ1に対応するインスタンスの丸印を表示することができる。同様にして、文Ｓ2，Ｓ3それぞれに対応するインスタンスの丸印も表示できる。
【０１３３】
文のインスタンス間の依存関係は、文のインスタンスが同じ配列要素をアクセスし、かつアクセスのどちらか、あるいは両方がwriteの場合に発生する。例えば、図８のプログラム５１で、文のインスタンス（Ｓ1，０）は配列Ａの要素Ａ［０］にwriteする。また、文のインスタンス（Ｓ2，０）は配列Ａの要素Ａ［０］をreadする。したがって、文のインスタンス（Ｓ1，０）から（Ｓ2，０）へ依存関係が存在することになる。文のインスタンス（Ｓ1，０）から（Ｓ2，０）へ依存関係が存在するため、図５の（Ｓ1，０）に対応する丸印から（Ｓ2，０）に対応する丸印へ矢印を描画する。描画したすべての文のインスタンスの丸印について、同様に依存関係があるかどうかを検査して、依存関係が存在する場合は矢印を描画することで、図９のグラフを生成することができる。
【０１３４】
図８のプログラム５１から、同期無し並列性を抽出する最適化を行う場合にコンパイラ１２０が計算する制約式は
【０１３５】
【数２２】
2017004281.tif 000024
【０１３６】
である。ここで、変数Ｃ1，Ｃ2，Ｃ3は図８の文の実行タイミングを表すスケジュール式
【０１３７】
【数２３】
2017004281.tif 000025
【０１３８】
の変数である。制約式に変数Ｃ3，定数ｃ3が出現しないのは、文Ｓ3には文Ｓ1，Ｓ2に対してデータ依存が存在しないため、任意のタイミングで実行してよいからである。
変数Ｃ1，Ｃ2，Ｃ3を満たす解は無限に存在する。コンパイラ１２０は一般に絶対値が小さい解で、かつ０ベクトルではない解を選択する。そのため、
【０１３９】
【数２４】
2017004281.tif 000026
【０１４０】
の解が選択される。
この解は図９のあるｉの値の座標を同一のプロセッサＰiに割り当てて、同期無しで並列実行する最適化を意味する。
【０１４１】
実際には、文Ｓ3の実行は文Ｓ1とＳ2に依存しないので、
【０１４２】
【数２５】
2017004281.tif 000027
【０１４３】
のように、文Ｓ3を文Ｓ1とＳ2に対して、１イタレーション先に実行するような解も正しい解である。このように実行するタイミングをずらしたい理由としては、
・データの利用効率が良くなる（キャッシュの利用効率の向上）
・データの整列状況が良くなる（ＳＩＭＤ化の促進）
・並列実行した場合のスレッド数が増加する
などが考えられる。しかし、コンパイラ１２０単独では、このような解を選択することをユーザが容易に行うことはできない。
【０１４４】
それに対して、第２の実施の形態では、最適化支援部１３０を利用することで、図９に表示されたインスタンスのグループ選択を行うことができる。
図１０は、グループ選択後のグラフの例を示す図である。選択したグループ内の座標（Ｓ，ｉ）は、それぞれ（Ｓ1，３）、（Ｓ2，３）、（Ｓ3，４）である。したがって、この座標情報Ｇから得られる新しい制約集合は
【０１４５】
【数２６】
2017004281.tif 000028
【０１４６】
となる。結果として、
【０１４７】
【数２７】
2017004281.tif 000029
【０１４８】
の解を、ＧＵＩを利用することで得ることができる。
なお、グループ化されたインスタンスを、同一のプロセッサで実行できない場合もあり得る。最適化支援部１３０は、このような場合、エラー表示を行うことができる。
【０１４９】
＜＜グループ化のエラー表示例＞＞
以下、エラーの検出とエラー表示とを実現する処理について、詳細に説明する。
図１１は、グループ化のエラー表示の第１の例を示す図である。例えば、図８に示すプログラム５１から、同期無し並列性を抽出する最適化を行う場合にコンパイラが計算する制約式は
【０１５０】
【数２８】
2017004281.tif 000030
【０１５１】
である。ユーザが図１１の黒丸で示すインスタンスについてグループ選択を行った場合、これらのインスタンスの座標情報Ｇから得られる新しい制約集合は
【０１５２】
【数２９】
2017004281.tif 000031
【０１５３】
となる。下の２つの制約式
【０１５４】
【数３０】
2017004281.tif 000032
【０１５５】
を同時に満たすためには、Ｃ3＝０とすることが要求される。ただし、ここで文の実行タイミングを表すスケジュール式
【０１５６】
【数３１】
2017004281.tif 000033
【０１５７】
でＣ3が０である場合は、文Ｓ3は変数ｉとは無関係に定数ｃ3のプロセッサに配置されることになり、並列性が存在しない解となる。このエラーを避けるためには、次の２つの制約
【０１５８】
【数３２】
2017004281.tif 000034
【０１５９】
のどちらか一方を外すこととなる。ここで、式（３２）の上の制約は、図１１で座標（Ｓ3，２）を選択した結果によるものであり、式（３２）の下の制約は、座標（Ｓ3，４）を選択した結果によるものである。図１１の例では、式（３２）の上の制約の元となった選択をエラーとして、座標（Ｓ3，２）の黒丸に×印が表示されている。
【０１６０】
グループ選択を行った結果の座標情報Ｇから得られた新しい制約集合がエラーになった場合は、一般にその中の制約の幾つかを外すことでエラーを解消できる。ただし、制約の大多数を外さなければエラーを解消できない場合もあり得る。
【０１６１】
図１２は、グループ化のエラー表示の第２の例を示す図である。例えばユーザが図１２の黒丸で示すグループ選択を行った場合を考える。この座標情報Ｇから得られる新しい制約集合は
【０１６２】
【数３３】
2017004281.tif 000035
【０１６３】
となる。この場合，Ｃ1，Ｃ2，Ｃ3，Ｃ4を０にすることなく選択できる解は
【０１６４】
【数３４】
2017004281.tif 000036
【０１６５】
のどれか１つと
【０１６６】
【数３５】
2017004281.tif 000037
【０１６７】
のどちらか一方からなる、対だけである。例えば、
【０１６８】
【数３６】
2017004281.tif 000038
【０１６９】
を選択して、残りの制約をすべてエラーとして外すことにすれば、Ｃ1，Ｃ2，Ｃ3，Ｃ4のすべてを０としない解を選択可能となる。しかし、この場合、ユーザが指定した選択の半分以上を捨てることになるので、ユーザの要望に合った結果であるとは考えられない。したがって、このような場合はすべてがエラーとして扱われ、図１２のようにすべての黒丸に×が表示される。
【０１７０】
＜＜グループ化の評価値の計算＞＞
図１０に示すようにグループ化にエラーがない場合、または図１１に示すように一部の選択を無視することでエラーが解消できる場合、エラーがない状態におけるグループ化の適切さについての評価値が算出される。第２の実施の形態では、このようなグループ化の評価値、例えば
・データの利用効率（キャッシュの利用効率）
・データの整列状況
・並列実行した場合のスレッド数
である。これらの値を図５の画面４０の各評価値表示部４２〜４４に表示することによって、コンパイラ単体では実現が困難な最適化方法の選択が容易となる。
【０１７１】
図５の画面に表示するグループ化の評価値とその計算方法の例について以下に示す。これらの評価値は，対象とするプログラムの性能向上に関して絶対的な評価値ではないけれども、ユーザが結果を調整するための重要なヒントとなる値である。
【０１７２】
＜＜＜データの利用効率（キャッシュの利用効率）＞＞＞
配列要素をアクセスする場合に、メモリ上である距離以内に存在する場合は同じキャッシュラインに載る可能性が高い。例えば、Ｃ言語のプログラムでは配列要素Ａ［Ｘ］［Ｙ］［Ｚ］と配列要素Ａ［Ｘ］［Ｙ］［Ｚ＋１］のデータは同じキャッシュライン上に載る可能性が高い。したがって、ユーザが選択したグループ化内の文のインスタンスが，同じ配列の要素で距離がｄ（ｄは０より大きい整数）以内にある場合は、１点加点することで評価値を計算することができる（距離の値は実行環境のＣＰＵのキャッシュの仕様によって決まる値である）。例えば、グループ化内の文のインスタンスが、次の５個の配列要素をアクセスする場合を考える。
【０１７３】
Ａ［３］［５］［０］
Ａ［３］［５］［３］
Ａ［３］［５］［６］
Ｂ［２］［７］
Ｂ［２］［１０］
このとき、ｄ＝４であれば，次の３つの組が作成できる。
【０１７４】
（Ａ［３］［５］［０］，Ａ［３］［５］［３］）
（Ａ［３］［５］［３］，Ａ［３］［５］［６］）
（Ｂ［２］［７］，Ｂ［２］［１０］）
この場合、データの利用効率の評価値「３」が得られる。この評価値が、図５の画面４０に表示される。
【０１７５】
＜＜＜データの整列状況＞＞＞
ＣＰＵのＳＩＭＤ命令は、一般に２の累乗個の隣接するデータを一度にメモリ転送したり、計算したりする命令である。したがって、ＣＰＵのＳＩＭＤ命令を有効利用するためには、一般に異なる配列にアクセスする場合に、アドレスの値の差が２の累乗になることが望ましい。例えば、配列要素Ａ［０］と配列要素Ｂ［２］のデータはループ変数ｉでＡ［ｉ］と配列要素Ｂ［ｉ＋２］のようにアクセスできる可能性があり、ＳＩＭＤ命令を利用する場合には都合がよいことが多い。逆に、配列要素Ａ［０］と配列要素Ｂ［３］のデータの処理にはＳＩＭＤ命令を利用できない可能性がある。
【０１７６】
したがって、ユーザが選択したグループ化内の文のインスタンスが、異なる配列にアクセスする場合に、その距離が２の累乗になる場合は、１点加点することで評価値を計算することができる。例えば、グループ化内の文のインスタンスが、次の５個の配列要素をアクセスする場合を考える。
【０１７７】
Ａ［０］
Ａ［３］
Ｂ［２］
Ｂ［８］
Ｂ［１１］
このとき、次の３つの組が作成できる。
【０１７８】
（Ａ［０］，Ｂ［２］，２）
（Ａ［０］，Ｂ［８］，８）
（Ａ［３］，Ｂ［１１］，８）
したがって、この場合は、データの整列状況の評価値「３」が得られる。この評価値が、図５の画面４０に表示される。
【０１７９】
＜＜＜並列実行した場合のスレッド数＞＞＞
凸多面体モデルを利用したループ最適化手法では、処理をパイプラインなどで並列実行できるように、ループ処理が最適化される。
【０１８０】
図１３は、ループ処理が最適化されたプログラムの一例を示す図である。プログラム５２は、例えば、『Ａ．Ｖ．エイホ，Ｒ．セシィ，Ｊ．Ｄ．ウルマン，Ｍ．Ｓ．ラム、「コンパイラ−原理・技法・ツール（第２版）」、サイエンス社、２００９年６月』に開示されているコンパイラにより最適化されたループ処理である。
【０１８１】
プログラム５２に示すループは並列実行が可能であり、変数ｐが各並列実行スレッドの番号に対応する。したがって、ユーザが選択したグループ化の結果として、図１３に示す形式のループを生成することによって、スレッド数の総数を変数ｐの初期値Ｓと終了値ＥからＥ−Ｓ＋１個と計算できる。
【０１８２】
一般には、初期値Ｓと終了値Ｅはプログラム中のパラメータ変数を含む式となる。すなわち、並列実行した場合のスレッド数としては、図５の画面４０に式Ｅ−Ｓ＋１の計算結果が表示される。並列実行した場合のスレッド数を表示することで、ユーザへの解の選択のヒントとすることができる。
【０１８３】
＜ループ最適化例２＞
次に、ループ最適化の第２の例について説明する。
図１４は、ループ処理を含むプログラムの第２の例を示す図である。例として、図１４のプログラム５３を最適化することを考える。このプログラム５３では、ループ変数が複数存在する。この場合、例えば、ループ変数ごとの軸を有するグラフによりデータの依存関係を表示することができる。
【０１８４】
図１５は、ループ変数が複数存在する場合のデータ依存関係のグラフの例を示す図である。図１４のプログラム５３には文がＳ1（プログラム５３中ではＳ１と表記）の１つしか存在しない。このため、図１５を生成する場合は、ループ変数ｉ，ｊを縦軸と横軸に取り、文の種類については軸を割り当てずに表示している。
【０１８５】
図１４のプログラム５３から、同期有り並列性を抽出する最適化を行う場合にコンパイラが計算する制約式は
【０１８６】
【数３７】
2017004281.tif 000039
【０１８７】
である。ここで、変数Ｃ1とＣ2は図１４の文の実行タイミングを表すスケジュール式
【０１８８】
【数３８】
2017004281.tif 000040
【０１８９】
の変数である。変数Ｃ1とＣ2を満たす解は無限に存在する。コンパイラ１２０は一般に絶対値が小さくなる解で、かつ０ベクトルではない解を選択する。そのため、
【０１９０】
【数３９】
2017004281.tif 000041
【０１９１】
あるいは
【０１９２】
【数４０】
2017004281.tif 000042
【０１９３】
の解が選択される。式（３９）の解を選択すると結果の繰り返し空間は図１６となる。
図１６は、ループ処理の繰り返し空間の第１の例を示す図である。この場合、図１６のあるｊの値の座標を同一のプロセッサＰjに割り当てて、同期有りで並列実行する最適化を意味する。
【０１９４】
２番目の解を選択すると結果の繰り返し空間は図１７となる。
図１７は、ループ処理の繰り返し空間の第２の例を示す図である。この場合、図１７のあるｉの値の座標を同一のプロセッサＰiに割り当てて、同期有りで並列実行する最適化を意味する。コンパイラ１２０単独では、この解の選択をユーザが容易に行うことはできない。また、２つの解が結果としてどのような繰り返し空間を作るのかを、ユーザは容易に知ることができない。
【０１９５】
それに対して、第２の実施の形態では、最適化支援部１３０を用いることで、図１５に示すデータ依存関係に対して、ＧＵＩを利用してグループ化するインスタンスを選択できる。
【０１９６】
図１８は、グループ化するインスタンスの第１の選択例を示す図である。選択したグループ内の座標（Ｓ，ｊ，ｉ）は、それぞれ（Ｓ１，１，３）、（Ｓ１，２，２）、（Ｓ１，３，１）、（Ｓ１，４，０）である。したがって、この座標情報Ｇから得られる新しい制約集合は
【０１９７】
【数４１】
2017004281.tif 000043
【０１９８】
となる。この新しい制約集合では、
【０１９９】
【数４２】
2017004281.tif 000044
【０２００】
は解であり、
【０２０１】
【数４３】
2017004281.tif 000045
【０２０２】
は解ではない。したがって、ＧＵＩを利用することで、図１７の繰り返し空間になる解を選択することができる。
また、図１５のデータ依存関係に対して、別のグループ選択もすることも可能である。
【０２０３】
図１９は、グループ化するインスタンスの第２の選択例を示す図である。例えば図１９のようにグループを選択すれば、選択したグループ内の座標（Ｓ，ｊ，ｉ）は、それぞれ（Ｓ１，０，２）、（Ｓ１，１，２）、（Ｓ１，２，２）、（Ｓ１，３，２）、（Ｓ１，４，２）である。したがって、この座標情報Ｇから得られる新しい制約集合は
【０２０４】
【数４４】
2017004281.tif 000046
【０２０５】
となる。この新しい制約集合では、
【０２０６】
【数４５】
2017004281.tif 000047
【０２０７】
は解であり、
【０２０８】
【数４６】
2017004281.tif 000048
【０２０９】
は解ではない。したがって、ＧＵＩを利用することで、図１６の繰り返し空間になる解を選択することができる。
ユーザが選択したグループに対して、常に解が存在する訳ではない。例えば、図１５のデータ依存関係に対して、座標（ｊ，ｉ）として、（１，３）、（２，２）、（３，１）、（４，０）、（５，０）を選択したと仮定する。この座標情報Ｇから得られる新しい制約集合は
【０２１０】
【数４７】
2017004281.tif 000049
【０２１１】
となり、この新しい制約集合では、
【０２１２】
【数４８】
2017004281.tif 000050
【０２１３】
も
【０２１４】
【数４９】
2017004281.tif 000051
【０２１５】
も解ではなくなり、解は存在しなくなる。このような場合、第２の実施の形態では、最適化支援部１３０が、座標情報の集合のすべての部分集合を作り、その各々について解が存在するか計算する。そして最適化支援部１３０は、解が存在する部分集合で、かつ最も制約数の多い部分集合を採用し、その部分集合に含まれていない制約が問題であったことをユーザに報告する。例えば、この場合は
【０２１６】
【数５０】
2017004281.tif 000052
【０２１７】
の制約だけを外せば
【０２１８】
【数５１】
2017004281.tif 000053
【０２１９】
の解が存在する。そこで最適化支援部１３０は、式（５１）の解を採用し、座標（５，０）が問題であったことをユーザに報告する。
このように選択するグループに問題がある場合でも状況を報告し、最適化を進めることで、次のような場合に対応することができる。
【０２２０】
・ユーザが正しい変換結果を完全にイメージできない場合でも、可能な限り最適化を進めることができる。
・ＧＵＩでループの繰り返し空間を表示したときのインスタンスの視認性が悪い場合がある。例えば３次元で繰り返し空間を表示する場合、インスタンスを示す各図形（例えば丸印）が近い位置に表示されたり、問題のある図形が、前方に表示された図形によって見えなくなったりする。このような場合でも、最適化を進めることができる。
【０２２１】
以上説明したように、第２の実施の形態によれば、コンパイラだけでは選択できない最適化を実現できる。しかもＧＵＩを利用して、テキストベースのツールでは指定困難な最適化を指示できる。さらに、ＧＵＩによるユーザからの入力が正確ではなくても、ユーザの要望に近い実行可能解を選択することで、最適化の可能性を広げることができる。
【０２２２】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【符号の説明】
【０２２３】
１  命令
２  命令群
１０  コンピュータ
１１  記憶装置
１１ａ  ソースコード
１２  演算装置
１３  表示装置
１３ａ  データ依存関係表示部
１３ｂ  第１の評価値
１３ｃ  第２の評価値
１３ｄ  第３の評価値
【図１】
2017004281.tif 000054
【図２】
2017004281.tif 000055
【図３】
2017004281.tif 000056
【図４】
2017004281.tif 000057
【図５】
2017004281.tif 000058
【図６】
2017004281.tif 000059
【図７】
2017004281.tif 000060
【図８】
2017004281.tif 000061
【図９】
2017004281.tif 000062
【図１０】
2017004281.tif 000063
【図１１】
2017004281.tif 000064
【図１２】
2017004281.tif 000065
【図１３】
2017004281.tif 000066
【図１４】
2017004281.tif 000067
【図１５】
2017004281.tif 000068
【図１６】
2017004281.tif 000069
【図１７】
2017004281.tif 000070
【図１８】
2017004281.tif 000071
【図１９】
2017004281.tif 000072