(57)【要約】      （修正有）【課題】互いにネットワークで接続されていてもよい、複数のコンピュータ・システムからなるハイブリッド・システム上で、リソースの利用及び実行速度の点で可能な限り最適化された実行可能コードを生成可能なコード生成技術を提供する。【解決手段】ソースコードのライブラリ部品について最適化表を作成する処理と、結果の最適化表を用いて、自動的な計算リソース割り当てと、互いにネットワークで接続されているハイブリッド・システムのための、ネットワーク・エンベディングを行うことによって、最適化された実行可能コードを生成する。【選択図】図１４
2011113449.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理により、該コンピュータ上で動作するアプリケーションを生成する方法であって、
前記アプリケーションを生成するためのライブラリ部品を用意するステップと、
利用可能なハードウェア・リソースの状況を取得するステップと、
前記ライブラリ部品中の処理単位に関して、前記利用可能なハードウェア・リソースの状況に基づき、１つ以上の実行パターンを生成するステップと、
前記実行パターン毎に、前記利用可能なハードウェア・リソースに関して実行速度を測定して、前記実行パターンと、前記利用可能なハードウェア・リソースと、前記実行速度をエントリとして含む最適化表を、前記コンピュータの記憶手段に保存するステップを有する、
アプリケーション生成方法。
【請求項２】
前記アプリケーションのソースコードを用意するステップと、
前記最適化表を参照して、前記ソースコードにおける処理単位に、最小の実行時間を達成するように前記最適化表の前記実行パターンを適用するステップと、
利用可能なハードウェア・リソースの制約を満たすように、前記最適化表を参照して、前記ソースコードにおける処理単位に適用される前記実行パターンを置き換えるステップとを更に有する、請求項１に記載の方法。
【請求項３】
前記ソースコードがストリーム・グラフ形式であり、該ストリーム・グラフ上の各ライブラリ部品の実行時間でソートしてリストするステップと、該リストの先頭から、前記最適化表を参照して、計算リソースをより消費しない実行パターンに置き換えるステップを更に有する、請求項２に記載の方法。
【請求項４】
前記ハードウェア・リソースが、互いにネットワークで接続され、異なるアーキテクチャのノードの混在を許容するハイブリッド・システムを含む、請求項３に記載の方法。
【請求項５】
通信サイズを基準にストリーム・グラフ上のエッジを降順に並べるステップと、前記リストの先頭エッジを共有する２つの処理単位を、同じハードウェア・リソースに割り当てるステップを更に有する、請求項４に記載の方法。
【請求項６】
コンピュータの処理により、該コンピュータ上で動作するアプリケーションを生成するプログラムであって、
前記コンピュータをして、
前記アプリケーションを生成するためのライブラリ部品を用意するステップと、
利用可能なハードウェア・リソースの状況を取得するステップと、
前記ライブラリ部品中の処理単位に関して、前記利用可能なハードウェア・リソースの状況に基づき、１つ以上の実行パターンを生成するステップと、
前記実行パターン毎に、前記利用可能なハードウェア・リソースに関して実行速度を測定して、前記実行パターンと、前記利用可能なハードウェア・リソースと、前記実行速度をエントリとして含む最適化表を、前記コンピュータの記憶手段に保存するステップを実行させる、
アプリケーション生成プログラム。
【請求項７】
前記アプリケーションのソースコードを用意するステップと、
前記最適化表を参照して、前記ソースコードにおける処理単位に、最小の実行時間を達成するように前記最適化表の前記実行パターンを適用するステップと、
利用可能なハードウェア・リソースの制約を満たすように、前記最適化表を参照して、前記ソースコードにおける処理単位に適用される前記実行パターンを置き換えるステップとを更に有する、請求項６に記載のプログラム。
【請求項８】
前記ソースコードがストリーム・グラフ形式であり、該ストリーム・グラフ上の各ライブラリ部品の実行時間でソートしてリストするステップと、該リストの先頭から、前記最適化表を参照して、計算リソースをより消費しない実行パターンに置き換えるステップを更に有する、請求項７に記載のプログラム。
【請求項９】
前記ハードウェア・リソースが、互いにネットワークで接続され、異なるアーキテクチャのノードの混在を許容するハイブリッド・システムを含む、請求項８に記載のプログラム。
【請求項１０】
通信サイズを基準にストリーム・グラフ上のエッジを降順に並べるステップと、前記リストの先頭エッジを共有する２つの処理単位を、同じハードウェア・リソースに割り当てるステップを更に有する、請求項９に記載のプログラム。
【請求項１１】
ハードウェア・リソースが、互いにネットワークで接続され、異なるアーキテクチャのノードの混在を許容するハイブリッド・システム上で動作するアプリケーションを生成するシステムであって、
記憶装置と、
前記記憶装置に記憶された前記アプリケーションを生成するためのライブラリ部品と、
前記ハイブリッド・システムの利用可能なハードウェア・リソースの状況を取得する手段と、
前記ライブラリ部品中の処理単位に関して、前記利用可能なハードウェア・リソースの状況に基づき、１つ以上の実行パターンを生成する手段と、
前記実行パターン毎に、前記利用可能なハードウェア・リソースに関して実行速度を測定して、前記実行パターンと、前記利用可能なハードウェア・リソースと、前記実行速度をエントリとして含む最適化表を、前記記憶装置に保存する手段を有する、
アプリケーション生成システム。
【請求項１２】
前記装置に保存された前記アプリケーションのソースコードと、
前記最適化表を参照して、前記ソースコードにおける処理単位に、最小の実行時間を達成するように前記最適化表の前記実行パターンを適用する手段と、
利用可能なハードウェア・リソースの制約を満たすように、前記最適化表を参照して、前記ソースコードにおける処理単位に適用される前記実行パターンを置き換える手段とを更に有する、請求項１１に記載のシステム。
【請求項１３】
前記ソースコードがストリーム・グラフ形式であり、該ストリーム・グラフ上の各ライブラリ部品の実行時間でソートしてリストする手段と、該リストの先頭から、前記最適化表を参照して、計算リソースをより消費しない実行パターンに置き換える手段を更に有する、請求項１２に記載のシステム。
【請求項１４】
通信サイズを基準にストリーム・グラフ上のエッジを降順に並べる手段と、前記リストの先頭エッジを共有する２つの処理単位を、同じハードウェア・リソースに割り当てる手段を更に有する、請求項１３に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータ上で動作するアプリケーションを作成するための技術に関し、特にネットワーク接続されたハイブリッド・システム上で動作するアプリケーションを作成するためのシステム、方法及びプログラムに関するものである。
【背景技術】
【０００２】
最近になって、IBM(R) Roadrunner, IBM BlueGene(R)などの並列高速コンピュータが製造され出荷されている。
【０００３】
また、異なるアーキテクチャのプロセッサを複数ネットワークまたはバスで接続した、いわゆるハイブリッド・システムによる並列高速コンピュータも構築されている。
【０００４】
このように、コンピュータ・ハードウェアの進化は著しいが、その一方で、問題になるのは、そのようなハイブリッド・システムに対応するアプリケーション・プログラムの開発である。
【０００５】
しかし、ハイブリッド・システムにおいては、プロセッサの種類、アクセレレータ機能、ハードウェア・アーキテクチャ、ネットワーク・トポロジなど様々で、これらの多様性を考慮に入れてアプリケーション・プログラムを人手で開発することは著しく困難である。例えば、上述のIBM(R) Roadrunnerは、１０万個もの、２タイプのコアを有する。このような複雑なコンピュータ・リソースに配慮して、アプリケーション・プログラムのコードと、リソース・マッピングを作成することは、非常に限られた専門家のみがなしえることである。
【０００６】
特開平８−１０６４４４号公報は、複数ＣＰＵからなる情報処理装置システムにおいて、異種ＣＰＵに交換する場合、自動的にそのＣＰＵに対応したロードモジュールを生成してローディングするようにすることを開示する。
【０００７】
特開２００６−３３８６６０号公報は、設計段階において、接続グラフの要素および要素間の接続を表すためのスクリプト言語を提供するステップと、実装段階において、アプリケーションの機能を実装するための事前に定義されたモジュールを提供するステップと、実装段階において、モジュールの実行の型を定義するための事前に定義されたエグゼキュータを提供するステップと、実装段階において、複数の演算装置上にアプリケーションを分散するための事前に定義されたプロセス・インスタンスを提供するステップと、試験段階において、試験段階中のアプリケーションを監視および試験するための事前に定義された抽象化レベルを提供するステップとをそれぞれ設けることによって、並列／分散型アプリケーションの開発を支援する方法を開示する。
【０００８】
特開２００６−５０５０５５号公報は、再構成可能なプロセッサのためのハードウェアロジック、従来のプロセッサ（命令プロセッサ）のための命令、およびハイブリッドハードウェアプラットフォームでの実行を管理するための関連したサポートコードを含む統一された実行可能要素を生成するために、高級言語標準に準拠して書き込まれたコンピュータコードをコンパイルするためのシステムおよび方法を開示する。
【０００９】
特開２００７−３２８４１５号公報は、命令セット及び構成の異なるプロセッサエレメントを複数備えたヘテロジニアス・マルチプロセッサシステムにおいて、予め設定した複数のタスクの依存関係に基づいて実行可能なタスクを抽出し、前記抽出したタスクの依存関係に基づいて前記複数の第１のプロセッサを汎用プロセッサグループに割り当て、前記第２のプロセッサをアクセラレータグループに割り当てて、予め設定したタスク毎の優先度に基づいて、前記抽出したタスクから割り当てを行うタスクを決定し、前記決定したタスクを前記第１のプロセッサで実行したときの実行コストと、前記タスクを前記第２のプロセッサで実行したときの実行コストとを比較し、前記比較の結果、前記実行コストが小さい方の汎用プロセッサグループまたはアクセラレータグループの一方に当該タスクを割り当てることを開示する。
【００１０】
特開２００７−３２８４１６号公報は、ヘテロマルチプロセッサシステムにおいて、コンパイラにより自動的に並列性を持つタスクを抽出すると共に、処理対象となる入力プログラムから専用プロセッサで効率良く処理できる部分の抽出と処理時間の見積もりを行うことで、ＰＵの特性に合わせて当該タスクを配置することで当該複数のＰＵを並行して効率よく動かすスケジューリングを実施することを開示する。
【００１１】
上記従来技術は、ハイブリッドハードウェアプラットフォーム向けにソースコードをコンパイルする技術は開示するが、利用リソースあるいは処理速度の点で最適化された実行可能コードを生成する技術は開示するものではない。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平８−１０６４４４号公報
【特許文献２】特開２００６−３３８６６０号公報
【特許文献３】特開２００７−３２８４１５号公報
【特許文献４】特開２００７−３２８４１６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
従って、この発明の目的は、互いにネットワークで接続されていてもよい、複数のコンピュータ・システムからなるハイブリッド・システム上で、リソースの利用及び実行速度の点で可能な限り最適化された実行可能コードを生成可能なコード生成技術を開示することにある。
【課題を解決するための手段】
【００１４】
本発明は、上記目的を達成するためになされたものであり、コンピュータの処理により、ソースコードのライブラリ部品に基づき最適化表を作成する処理と、結果の最適化表を用いて、自動的な計算リソース割り当てと、互いにネットワークで接続されているハイブリッド・システムのための、ネットワーク・エンベディングを行うことによって、最適化された実行可能コードを生成するものである。
【００１５】
最適化表を作成する処理においては、各ライブラリ部品に対して、最適化なし、及び最適化を適用した場合に必要なリソースとパイプライン・ピッチ、すなわち、パイプライン処理の１ステージの処理時間が計測され、実行パターンとして登録される。各ライブラリ部品には、複数のパターンがありえる。リソースを増やすことでパイプライン・ピッチが改善する実行パターンは登録されるが、好適には、リソースを増やしてもパイプライン・ピッチが改善されない実行パターンは登録されない。
【００１６】
ここで、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａなどの任意のプログラム言語で書かれて、あるまとまりのある機能を実行するプログラムの集まりを、ライブラリ部品と呼ぶ。例えば、Simulinkの機能ブロックと同等の場合もあるし、実現するアルゴリズムの単位で考えて、複数の機能ブロックからなる組み合わせを、１つのライブラリ部品とみなす場合もある。
【００１７】
一方、実行パターンとしては、データ並列化（並列度1,2,3,...,n)、アクセラレータと使用（グラフィックス・プロセッシング・ユニット）、それらの組合せなどからなる。
【００１８】
結果の最適化表を用いて、コンピュータの処理により、自動的な計算リソース割り当てを行うステップでは、実行すべき処理をストリーム・グラフで表すとして、そのストリーム・グラフ上の全ユーザ定義オペレータ（ＵＤＯＰ）に対して、最適化表から、パイプライン処理の１ステージの処理時間、特にストリーム・グラフ形式ソースコード上の全部品に対し、それぞれ、パイプライン・ピッチが最も短い実行パターンを仮選択するステップと、計算リソース制約を解くステップと、ネットワーク・エンベディングのステップが実行される。
【００１９】
ここでＵＤＯＰとは、例えば、行列の積和計算のような抽象的な処理の単位ことである。
【００２０】
また、計算リソース制約を解くステップは、ストリーム・グラフ上の各ライブラリ部品のパイプライン・ピッチを昇順にリストするステップと、そのリストの先頭から、最適化表を参照して、計算リソースをより消費しない実行パターンに置き換えるステップを有する。
【００２１】
ネットワーク・エンベディングのステップは、通信サイズを基準にストリーム・グラフ上のエッジを降順に並べるステップと、リストの先頭エッジを共有する２つのＵＤＯＰを、同じハードウェア・リソースに優先的に割り当てるステップを有する。
【発明の効果】
【００２２】
この発明によれば、ライブラリ部品に基づき生成された最適化表を参照することにより、ハイブリッド・システム上で、リソースの利用及び実行速度の点で可能な限り最適化された実行可能コードを生成することが可能となる。
【図面の簡単な説明】
【００２３】
【図１】本発明を実施するためのハードウェア構成の概要を示す図である。
【図２】本発明を実施するための機能ブロック図である。
【図３】最適化表を作成するための処理のフローチャートを示す図である。
【図４】実行パターンの生成の例を示す図である。
【図５】並列処理のために配列を分割する条件を示すデータ依存ベクトルの例を示す図である。
【図６】最適化表の例を示す図である。
【図７】ネットワーク・エンベディングの処理の概要のフローチャートを示す図である。
【図８】ＵＤＯＰに計算リソースを割り当てる処理のフローチャートを示す図である。
【図９】ストリームグラフと、利用可能なリソースの例を示す図である。
【図１０】ＵＤＯＰに計算リソースを割り当てた後の要求されたリソースの例を示す図である。
【図１１】割当て変更処理の例を示す図である。
【図１２】クラスタリング処理のフローチャートを示す図である。
【図１３】ストリームグラフにおいて、実行パターンで展開した例を示す図である。
【図１４】カーネルをノードに割り当てる例を示す図である。
【図１５】クラスタの割当て処理のフローチャートを示す図である。
【図１６】ハードウェア・コンフィギュレーションの例を示す図である。
【図１７】経路表及びネットワークの容量表の例を示す図である。
【図１８】クラスタ間の接続の例を示す図である。
【発明を実施するための形態】
【００２４】
以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。
【００２５】
図１は、本発明を実施するためのハードウェア構成を示すブロック図である。この構成は、チップレベル・ハイブリッド・ノード１０２と、従来型ノード１０４と、ＣＰＵとアクセラレータをもつハイブリッド・ノード１０６，１０８を有する。
【００２６】
チップレベル・ハイブリッド・ノード１０２は、バス１０２ａに、複数種のＣＰＵを含むハイブリッドＣＰＵ１０２ｂ、主記憶（ＲＡＭ）１０２ｃ、ハードディスク・ドライブ（ＨＤＤ）１０２ｄ、及びネットワーク・インターフェース・カード（ＮＩＣ）１０２ｅが接続された構成である。
【００２７】
従来型ノード１０４は、バス１０４ａに、同一の複数のコアからなるマルチコアＣＰＵ１０４ｂ、主記憶１０４ｃ、ハードディスク・ドライブ１０４ｄ、及びネットワーク・インターフェース・カード（ＮＩＣ）１０４ｅが接続された構成である。
【００２８】
ハイブリッド・ノード１０６は、バス１０６ａに、ＣＰＵ１０６ｂ、例えばグラフィック・プロセッシング・ユニットであるアクセラレータ１０６ｃ、主記憶１０６ｄ、ハードディスク・ドライブ１０６ｅ、及びネットワーク・インターフェース・カード１０６ｆが接続された構成である。
【００２９】
ハイブリッド・ノード１０８は、ハイブリッド・ノード１０６と同様の構成であり、バス１０８ａに、ＣＰＵ１０８ｂ、例えばグラフィック・プロセッシング・ユニットであるアクセラレータ１０８ｃ、主記憶１０８ｄ、ハードディスク・ドライブ１０８ｅ、及びネットワーク・インターフェース・カード１０８ｆが接続された構成である。
【００３０】
チップレベル・ハイブリッド・ノード１０２と、ハイブリッド・ノード１０６と、ハイブリッド・ノード１０８は、イーサネット(R)・バス１１０とそれぞれのネットワーク・インターフェース・カードを介して接続されている。
【００３１】
チップレベル・ハイブリッド・ノード１０２と、従来型ノード１０４は、サーバ/クラスター用高速Ｉ／Ｏバスアーキテクチャ及びインターコネクトである、InfiniBandで、それぞれのネットワーク・インターフェース・カードを介して接続されている。
【００３２】
ここで示したノード１０２、１０４、１０６、及び１０８は、IBM(R) System pシリーズ、IBM(R) System xシリーズ、IBM(R) System zシリーズ、IBM(R) Roadrunner、BlueGene(R)など、利用可能な任意のコンピュータ・ハードウェアを使用することができる。
【００３３】
また、オペレーティング・システムも、Windows(R) XP、Windows(R) 2003 server、Windows(R) 7、 AIX(R)、Linux(R)、Z/OSなど、利用可能な任意のオペレーティング・システムを使用することができる。
【００３４】
図示しないが、ノード１０２、１０４、１０６、及び１０８は、オペレータまたはユーザが操作するためのキーボード、マウス、及びディスプレイなどのインターフェース装置を有している。
【００３５】
なお、図１に示す構成は、ノードの数及び種類ともに、例示に過ぎず、より多くのノードや異なる種類のノードからなっていてもよい。また、ノード間の接続態様も、ＬＡＮ、ＷＡＮ、インターネット経由のＶＰＮなど、必要とされる通信速度を与える任意の構成を採用することができる。
【００３６】
図２は、本発明に構成に係る機能ブロックを示すものである。ここで示す各々の機能ブロックは、図１に示すノード１０２、１０４、１０６、及び１０８のハードディスクに保存されていてもよい。あるいは、主記憶にロードすることもできる。
【００３７】
また、本発明に係る処理の操作は、ノード１０２、１０４、１０６、及び１０８のうちのどれか上で、ユーザが、キーボードやマウスを操作することによって、行うことができる。
【００３８】
図２において、ライブラリ部品２０２は、一例では、Simulink(R)の機能ブロックと同等であり、実現するアルゴリズムの単位で考えて、複数の機能ブロックからなる組合せを、１つのライブラリ部品とみなす場合もある。しかし、Simulink(R)の機能ブロックには限定されず、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ(R)などの任意のプログラム言語で書かれて、あるまとまりのある機能を実行するプログラムの集まりを、ここではライブラリ部品と扱う。
【００３９】
ライブラリ部品２０２は、好適には、熟練したプログラマによって予め作成されて、好適には、ノード１０２、１０４、１０６、及び１０８以外の別のコンピュータ・システムのハードディスク・ドライブに保存される。
【００４０】
最適化表作成モジュール２０４もまた、好適には、ノード１０２、１０４、１０６、及び１０８以外の別のコンピュータ・システムのハードディスク・ドライブに保存され、ライブラリ部品２０２を参照して、コンパイラ２０６を利用しまた、実行環境２０８にアクセスして、最適化表２１０を生成する。生成された最適化表２１０もまた、好適には、ノード１０２、１０４、１０６、及び１０８以外の別のコンピュータ・システムのハードディスク・ドライブまたは主記憶に保存される。最適化表２１０の生成処理は、後で詳細に説明する。最適化表作成モジュール２０４は、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ(R)などの既知の適当な任意のプログラミング言語で書くことができる。
【００４１】
ストリーム・グラフ形式ソースコード２１２は、ユーザが、図１のハイブリッド・システムで実行したいプログラムのソースコードを、ストリーム形式で保存したものである。その典型的な形式は、Simulink(R)の機能ブロック図であらわされるものである。ストリーム・グラフ形式ソースコード２１２は、好適には、ノード１０２、１０４、１０６、及び１０８以外の別のコンピュータ・システムのハードディスク・ドライブに保存されている。
【００４２】
コンパイラ２０６は、ノード１０２、１０４、１０６、及び１０８の各環境向けに、コードをコンパイルして実行可能コードを生成する機能をもつだけではなく、計算リソースをノード構成に合わせてクラスタリングする機能と、論理ノードを、物理ノードのネットワークに割り当て、ノード間の通信方式を決定する機能も併せ持つ。コンパイラ２０６の機能については、後でより詳しく説明する。
【００４３】
実行環境２０８は、図１のハイブリッド・ハードウェア・リソースを総称的に示すブロック図である。
【００４４】
次に、図３のフローチャートを参照して、最適化表作成モジュール２０４が実行する最適化表作成処理について説明する。
【００４５】
図３において、ステップ３０２では、最適化表作成モジュール２０４が、ライブラリ部品２０２におけるＵＤＯＰ、すなわち、ある抽象的な処理の単位を選択する。ここで、ライブラリ部品２０２と、ＵＤＯＰの間の関係について説明すると、ライブラリ部品２０２とは、あるまとまりのある機能を実行するプログラムの集まりであり、例えば、高速フーリエ変換（ＦＦＴ）モジュール、逐次過緩和（ＳＯＲ）法モジュール、直交行列を求めるためのヤコビ法モジュールなどである。
【００４６】
そこでＵＤＯＰとは例えば、最適化表作成モジュール２０４が、行列の積和計算という抽象的な処理のことであり、これは例えば、ヤコビ法モジュールで使用される。
【００４７】
ステップ３０４では、選択したＵＤＯＰを実現するカーネル定義を取得する。ここで、カーネル定義とは、この実施例では、ＵＤＯＰに対応する、ハードウェア・アーキテクチャに依存した具体的なコードのことである。
【００４８】
ステップ３０６では、最適化表作成モジュール２０４が、実行環境２０８にアクセスして、実行対象のハードウェア・コンフィギュレーションを取得する。
【００４９】
ステップ３０８では、最適化表作成モジュール２０４が、使用アーキテクチャの組合せ、使用リソースの組Set{(Arch, R)}を、Set{(default, 1)}に初期化する。
【００５０】
次にステップ３１０で、全リソースに対する試行終了かどうか判断し、そうならば処理を終了し、そうでないなら、ステップ３１２で、最適化表作成モジュール２０４が、現在のリソースに対する実行可能なカーネルを選択する。
【００５１】
ステップ３１４では、最適化表作成モジュール２０４が、実行パターンを生成する。実行パターンとは、次のようなものである。
ループにする(Rolling loop):   A+A+A....A  =>  loop(n, A)
ここで、A+A+A....Aは、Aの直列処理であり、loop(n, A)は、Aをn回まわすループのことをあらわす。
ループを解く(Unrolling loop): loop(n, A) => A+A+A....A
ループの直列(Series Rolling): split_join( A, A... A ) => loop(n, A)
これは、並列に走るA, A... Aを、loop(n, A)にすることである。
ループの並列(Pararell unrolling loop):  loop(n, A) => split_joing( A, A, A ........A )
これは、loop(n, A)を、並列に走るA, A... Aにすることである。
ループの分割(Loop splitting): loop(n, A)  => loop(x, A)  +  loop(n-x, A)
並列ループ分割(Pararell Loop splitting): loop(n, A)  => split_join( loop(x, A),  loop(n-x, A) )
ループ融合(Loop fusion):  loop(n, A) + loop(n, B)  => loop(n, A+B)
ループ融合の直列(Series Loop fusion): split_join( loop(n, A), loop(n, B) )  => loop(n, A+B)
ループ分配(Loop distribution):  loop(n, A+B) => loop(n, A) + loop(n, B) 
並列ループ分配(Pararell Loop distribution): loop(n, A+B) => split_join( loop(n, A), loop(n, B) ) 
ノード結合(Node merging):   A+B => {A,B}
ノード分割(Node splitting):  {A,B} => A+B
ループ置換(Loop replacement): loop(n,A) => X /* X is lower cost */
ノード置換(Node replacement):  A => X /* X is lower cost */
【００５２】
ステップ３１４で、カーネルによっては、上記すべての実行パターンが生成可能とは限らない。そこで、ステップ３１４では、カーネルに基づき、生成可能な実行パターンだけが生成される。
【００５３】
ステップ３１６では、生成された実行パターンが、コンパイラ２０６でコンパイルされ、その結果得られた実行可能コードが実行環境２０８の選択されたリソースで実行され、パイプライン・ピッチ（時間）が計測される。
【００５４】
ステップ３１８では、最適化表作成モジュール２０４が、選択したＵＤＯＰ、選択したカーネル、実行パターン、計測したパイプライン・ピッチ、Set{(Arch, R)}を、データベース（最適化表）２１０に登録する。
【００５５】
ステップ３２０では、使用リソースの変更または、使用アーキテクチャの組み合せ変更を行う。例えば、使用するノード（図１参照）の組合せの変更、使用するＣＰＵ及びアクセラレータの組合せの変更、等である。
【００５６】
次に、ステップ３１０に戻って、全リソースに対する試行終了かどうか判断し、そうならば処理を終了し、そうでないなら、ステップ３１２で、最適化表作成モジュール２０４が、ステップ３２０で選ばれたリソースに対する実行可能なカーネルを選択する。
【００５７】
図４は、float[6000][6000]という大きい配列をもつライブラリ部品Ａについて、それの、
kernel_x86(float[1000][1000] in, float[1000][1000]  out)  {
...
} 
と、
kernel_cuda(float[3000][3000] in, float[3000][3000]  out)  {
...
} 
という、２つのカーネルに注目して、実行パターンを生成する例を示す図である。ここで、kernel_x86というのは、インテル(R)のx86アーキテクチャのＣＰＵを使用するカーネルであることを示し、kernel_cudaというのは、ＮＶＩＤＩＡ社が提供するCUDAアーキテクチャのグラフィック・プロセッシング・ユニット（ＧＰＵ）を使用するカーネルであることを示す。
【００５８】
図４において、実行パターン１は、loop(36,kernel_x86)により、kernel_x86を３６回実行するものである。
【００５９】
実行パターン２は、split_join(loop(18,kernel_x86),loop(18,kernel_x86))により、２つのloop(18,kernel_x86)に分けて２つのx86系ＣＰＵに処理を割り当てて並列実行した後、結果を結合するものである。
【００６０】
実行パターン３は、split_join(loop(2,kernel_cuda),loop(18,kernel_x86))により、loop(2,kernel_cuda)とloop(18,kernel_x86に分けて、それぞれcude系ＣＰＵと、x86系ＣＰＵに処理を割り当てて並列実行した後、結果を結合するものである。
【００６１】
このような実行パターンはいろいろあり得るので、可能なすべての組合せを実行すると組合せ爆発するかもしれない。そこで、この実施例では、すべての場合を尽くさなくても、許容される時間の範囲で、可能な実行パターンについて処理を行う。
【００６２】
図５は、図４のカーネルにおける、float[6000][6000]という配列を分割する場合の条件を示す図である。例えば、ラプラス方程式のような偏微分方程式の境界値問題を大きい配列を使用して解く場合は、計算される配列の要素に依存関係があるので、計算を並列化しようとすると、列の分割に依存関係が存在する。
【００６３】
そこで、配列の計算の内容に応じて、分割の条件を指定するd{in(a,b,c)}のようなデータ依存ベクトルを定義して使用する。d{in(a,b,c)}のa,b,cはそれぞれ、0か1の値をとり、a = 1は、１次元目の依存、すなわち、横方向にはブロック分割可能であることを示し、b = 1は、２次元目の依存、すなわち、縦方向にはブロック分割可能であることを示す。c = 1は、時間軸の依存、すなわち、入力側の配列に対する出力側の配列の依存性である。
【００６４】
図５は、そのような依存性の例を図示するものである。なお、d{in(0,0,0)}だと、任意の方向に分割可能ということを意味する。計算の性質に依存してこのようなデータ依存ベクトルを用意し、ステップ３１４で、データ依存ベクトルに規定された条件を満たす実行パターンのみを生成するようにする。
【００６５】
図６は、このようにして作成された最適化表２１０の例である。
【００６６】
次に、図７以下を参照して、作成された最適化表２１０を参照して、図１に示すようなハイブリッド・システムで実行可能なプログラムを生成する方法について説明する。
【００６７】
特に図７は、実行可能なプログラムを生成する処理の全体を示す概要フローチャートである。この一連の処理は、基本的に、コンパイラ２０６によって実行されるが、コンパイラ２０６は、ライブラリ部品２０２、最適化表２１０、ストリーム形式ソースコード２１２及び実行環境２０８を参照する。
【００６８】
ステップ７０２では、コンパイラ２０６は、オペレータ、すなわち、ＵＤＯＰに計算リソースを割り当てる処理を行う。この処理は、図８のフローチャートを参照して、後で詳細に説明する。
【００６９】
ステップ７０４では、コンパイラ２０６は、計算リソースを、ノード構成に合わせてクラスタリングする処理を行う。この処理は、図１２のフローチャートを参照して、後で詳細に説明する。
【００７０】
ステップ７０６では、コンパイラ２０６は、論理ノードを、物理ノードのネットワークに割当て、ノード間の通信方式を決定する処理を行う。この処理は、図１５のフローチャートを参照して、後で詳細に説明する。
【００７１】
次に、ステップ７０２のＵＤＯＰに計算リソースを割り当てる処理について、図８のフローチャートを参照して、より詳しく説明する。
【００７２】
図８において、ストリーム形式ソースコード（ストリーム・グラフ）２１２、リソース制約（ハードウェア・コンフィギュレーション）、及び最適化表２１０が事前に用意されるものとする。機能ブロックＡ，Ｂ，Ｃ．Ｄからなるストリーム・グラフ２１２とリソース制約の例を、図９に示す。
【００７３】
コンパイラ２０６は、ステップ８０２で、フィルタリングを行う。すなわち、与えられたハードウェア・コンフィギュレーションと最適化表２１０から実行可能なパターンのみ抽出し、最適化表(A)を作成する。
【００７４】
コンパイラ２０６は、ステップ８０４で、最適化表(A)を参照して、ストリームグラフ中の各ＵＤＯＰに もっともパイプラインピッチの短い実行パターンを割り当てた実行パターン群(B)を作成する。それを、ストリームグラフの各ブロックに割り当てた様子を示す例を、図１０に示す。
【００７５】
次にステップ８０６では、コンパイラ２０６は、実行パターン群(B)は与えられたリソース制約を満たしているかどうかを判断する。
【００７６】
ステップ８０６で、コンパイラ２０６が、実行パターン群(B)が与えられたリソース制約を満たしていると判断すると、この処理は完了する。
【００７７】
ステップ８０６で、コンパイラ２０６が、実行パターン群(B)が与えられたリソース制約を満たしてないと判断すると、ステップ８０８に進み、実行パターン群(B)中の実行パターン群をパイプラインピッチ順にソートしたリスト(C)を作成する。
【００７８】
次に、ステップ８１０に進み、コンパイラ２０６は、リスト(C)から一番パイプラインピッチが短い実行パターンを持つＵＤＯＰ (D)を選択する。
【００７９】
次に、ステップ８１２に進み、コンパイラ２０６は、ＵＤＯＰ(D)について、消費リソースのより少ない実行パターン（次候補）(E)が最適化表(A)に存在するかを判断する。
【００８０】
もしそうなら、ステップ８１４に進み、コンパイラ２０６は、ＵＤＯＰ(D)について、実行パターン（次候補）(E)のパイプラインピッチはリスト(C)内の最長値より小さいかどうかを判断する。
【００８１】
もしそうなら、ステップ８１６に進み、コンパイラ２０６は、実行パターン（次候補）(E)をＵＤＯＰ(D)の新しい実行パターンとして割り当て、実行パターン群(B)を更新する。
【００８２】
ステップ８１６からは、ステップ８０６の判断に戻る。
【００８３】
ステップ８１０あるいはステップ８１２での判断が否定的なら、ステップ８１８に進み、そこで、コンパイラ２０６は、当該ＵＤＯＰを(C)から外す。
【００８４】
次に、ステップ８２０に進み、そこでコンパイラ２０６は、リスト(C)に要素が存在するかどうかを判断する。もしそうなら、ステップ８０８に戻る。
【００８５】
ステップ８２０で、リスト(C)に要素が存在しないと判断されたなら、ステップ８２２に進み、そこでコンパイラ２０６は、実行パターン群(B)中の実行パターン群を、実行パターン群(B)の最長パイプラインピッチと次候補のパイプラインピッチの差の順にソートしたリスト(F)を作成する。
【００８６】
次に、ステップ８２４で、コンパイラ２０６は、リスト(F)のうちパイプラインピッチの差が一番短い実行パターン(G)について、それが要求するリソースが、現在注目しているリソースより少ないかどうかを判断する。
【００８７】
もしそうなら、ステップ８２６に進み、そこでコンパイラ２０６は、実行パターン(G)を新しい実行パターンとして割り当て、実行パターン群(B)を更新し、ステップ８０６に進む。そうでなければ、ステップ８２８で当該ＵＤＯＰを(F)から外して、ステップ８２２に戻る。
【００８８】
図１１は、このような実行パターン群の置き換えによる最適化の例を示す図である。図１１では、リソース制約を解くために、D4がD5に置き換えられている。
【００８９】
図１２は、ステップ７０４の、計算リソースをノード構成に合わせてクラスタリングする処理をより詳細に示す処理のフローチャートである。
【００９０】
先ず、ステップ１２０２では、コンパイラ２０６が、ストリームグラフを、図８のフローチャートの処理で割り当てた実行パターンで展開する。この結果の例を、図１３に示す。なお、図１３では、cudaが、cuと略記されている。
【００９１】
次に、ステップ１２０４では、コンパイラ２０６は、各実行パターン毎に実行時間+通信時間を新規パイプラインピッチとして算出する。
【００９２】
次に、ステップ１２０６では、コンパイラ２０６は、各実行パターンを新規パイプラインピッチの順にソートしリストを作成する。
【００９３】
次に、ステップ１２０８では、コンパイラ２０６は、リスト中から新規パイプラインピッチの最大のものを選択する。
【００９４】
次に、ステップ１２１０では、コンパイラ２０６は、ストリームグラフ上で、隣接するカーネルが論理ノードにすでに割り当てられているかどうかを判断する。
【００９５】
もし、ステップ１２１０で、ストリームグラフ上で、隣接するカーネルが論理ノードにすでに割り当てられていると判断されたなら、ステップ１２１２に進み、そこでコンパイラ２０６は、隣接するカーネルに割り当てられている論理ノードにアーキテクチャ制約を満たす空きはあるかどうかを判断する。
【００９６】
もしステップ１２１２で、隣接するカーネルに割り当てられている論理ノードにアーキテクチャ制約を満たす空きはあると判断されたなら、ステップ１２１４に進み、そこで、当該カーネルを隣接カーネルが割り当てられている論理ノードに割り当てる処理が行われる。
【００９７】
ステップ１２１４からは、ステップ１２１８に進む。一方、ステップ１２１０またはステップ１２１２での判断が否定的だと、そこから直接ステップ１２１６に進み、そこで、コンパイラ２０６は、当該カーネルをアーキテクチャ制約を満たす論理ノードのうち、もっとも空き容量の大きいものに割り当てる。
【００９８】
次にステップ１２１４またはステップ１２１６から進むステップ１２１８では、コンパイラ２０６は、リスト更新として、リストから割り当てられたカーネルを削除する。
【００９９】
次にステップ１２２０では、コンパイラ２０６が、すべてのカーネルを論理ノードに割り当てたかどうかを判断し、もしそうなら、処理を終了する。
【０１００】
ステップ１２２０で、すべてのカーネルを論理ノードに割り当てはいないと判断されると、ステップ１２０８に戻る。
【０１０１】
このようなノード割り当ての例を、図１４に示す。すなわち、全カーネルがノードに割り当てられるまで、繰り返される。なお、図１４の一部では、cudaが、cuと略記されている。
【０１０２】
図１５は、ステップ７０６の、論理ノードを物理ノードのネットワークに割当て、ノード間の通信方式を決定する処理をより詳細に示すフローチャートである。
【０１０３】
ステップ１５０２では、コンパイラ２０６が、クラスタリングされたストリームグラフ（図１２のフローチャートの結果）、ハードウェア・コンフィギュレーションを与える。この一例を、図１６に示す。
【０１０４】
ステップ１５０４では、コンパイラ２０６が、ハードウェア・コンフィギュレーションから各物理ノード間の経路表、ネットワークの容量表を作成する。図１７に、例として、経路表１７０２、容量表１７０４を示す。
【０１０５】
ステップ１５０６では、コンパイラ２０６が、通信量の大きなエッジに隣接する論理ノードから、物理ノードに割り当てる。
【０１０６】
ステップ１５０８では、コンパイラ２０６が、ネットワーク容量表から容量の大きいネットワークを割り当てる。この結果、図１８に示すように、クラスタ間の接続がはかられる。
【０１０７】
ステップ１５１０では、コンパイラ２０６が、ネットワーク容量表を更新する。このことは、図１８の囲み１８０２に示されている。
【０１０８】
ステップ１５１２では、コンパイラ２０６が、すべてのクラスタに対し、割り当てが完了したかどうかを判断し、もしそうなら、処理は終了する。そうでなければ、ステップ１５０６に戻る。
【０１０９】
以上、特定の実施例に従い本発明を説明してきたが、示されたハードウェア、ソフトウェア、ネットワーク構成は例示に過ぎず、本発明は、これらと機能的に等価な任意の構成で実現可能であることを理解されたい。
【符号の説明】
【０１１０】
１０２  チップレベル・ハイブリッド・ノード
１０４  従来型ノード
１０６  ハイブリッド・ノード
１０８  ハイブリッド・ノード
１１０  イーサネット・バス
２０２  ライブラリ部品
２０４  最適化表作成モジュール
２０６  コンパイラ
２０８  実行環境
２１０  最適化表
２１２  ストリーム・グラフ
１７０２  経路表
１７０４  容量表
【図１】
2011113449.tif 000003
【図２】
2011113449.tif 000004
【図３】
2011113449.tif 000005
【図４】
2011113449.tif 000006
【図５】
2011113449.tif 000007
【図６】
2011113449.tif 000008
【図７】
2011113449.tif 000009
【図８】
2011113449.tif 000010
【図９】
2011113449.tif 000011
【図１０】
2011113449.tif 000012
【図１１】
2011113449.tif 000013
【図１２】
2011113449.tif 000014
【図１３】
2011113449.tif 000015
【図１４】
2011113449.tif 000016
【図１５】
2011113449.tif 000017
【図１６】
2011113449.tif 000018
【図１７】
2011113449.tif 000019
【図１８】
2011113449.tif 000020