(57)【要約】      （修正有）【課題】強連結成分の内部の並列性も活かして、高速な動作を可能とする並列化技法を提供する。【解決手段】実行すべき処理を、複数の制御ブロックと、その制御ブロックをつなぐエッジで記述し、前記エッジのうち、予測性が高いエッジを選び、強連結クラスタを識別し、各強連結クラスタと、該強連結クラスタの間の孤立した非強連結クラスタのノード毎に、プロセッサ数と、そのコストと、対応クラスタをエントリとしてもつ並列化テーブル１１０２〜１１１６からなるグラフを作成してシリーズパラレルグラフに変換し、シリアルパス毎に、および、並列セクション毎にマージして、統合された並列化テーブルを形成する。その統合された並列化テーブルのプロセッサ数とコストの値に応じて、最良のエントリを選択し、そのエントリのクラスタに基づき、各プロセッサに割り当てるための実行可能コードを生成する。【選択図】図１１
2011081539.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理によって、マルチプロセッサ・システムで、個々のプロセッサに割当てて並列実行させるためのコードを生成する方法であって、
実行すべき処理を、複数の制御ブロックと、その制御ブロックをつなくエッジで記述するステップと、
強連結クラスタを識別するステップと、
各強連結クラスタと、該強連結クラスタの間の孤立した非強連結クラスタのノード毎に、プロセッサ数と、そのコストと、対応クラスタをエントリとしてもつ並列化テーブルを作成するステップと、
並列化テーブルからなるグラフを作成するステップと、
該並列化テーブルからなるグラフをシリーズパラレルグラフに変換するステップと、
シリアルパス毎に、前記並列化テーブルをマージするステップと、
並列セクション毎に、前記並列化テーブルをマージするステップとを有する、
コード生成方法。
【請求項２】
前記マージされた並列化テーブルのエントリのプロセッサ数とコストに基づき、利用可能なプロセッサの数の範囲でコスト的に最良のエントリを選ぶステップと、
該最良のエントリのクラスタに基づき、個々のプロセッサに割り当てるための実行可能コードを生成するステップをさらに有する、請求項１に記載のコード生成方法。
【請求項３】
コンピュータの処理によって、マルチプロセッサ・システムで、個々のプロセッサに割当てて並列実行させるためのコードを生成するシステムであって、
実行すべき処理を、複数の制御ブロックと、その制御ブロックをつなくエッジで記述する手段と、
強連結クラスタを識別する手段と、
各強連結クラスタと、該強連結クラスタの間の孤立した非強連結クラスタのノード毎に、プロセッサ数と、そのコストと、対応クラスタをエントリとしてもつ並列化テーブルを作成する手段と、
並列化テーブルからなるグラフを作成するステップと、
該並列化テーブルからなるグラフをシリーズパラレルグラフに変換するステップと、
シリアルパス毎に、前記並列化テーブルをマージする手段と、
並列セクション毎に、前記並列化テーブルをマージする手段とを有する、
コード生成システム。
【請求項４】
前記マージされた並列化テーブルのエントリのプロセッサ数とコストに基づき、利用可能なプロセッサの数の範囲でコスト的に最良のエントリを選ぶ手段と、
該最良のエントリのクラスタに基づき、個々のプロセッサに割り当てるための実行可能コードを生成する手段をさらに有する、請求項３に記載のコード生成システム。
【請求項５】
マルチプロセッサをもち、請求項４に記載の実行可能コードを生成する手段によって生成されたコードを個々のプロセッサに割り当て実行させるための実行環境を提供するコンピュータ・システム。
【請求項６】
コンピュータの処理によって、マルチプロセッサ・システムで、個々のプロセッサに割当てて並列実行させるためのコードを生成するプログラムであって、
前記コンピュータをして、
強連結クラスタを識別するステップと、
各強連結クラスタと、該強連結クラスタの間の孤立した非強連結クラスタのノード毎に、プロセッサ数と、そのコストと、対応クラスタをエントリとしてもつ並列化テーブルを作成するステップと、
並列化テーブルからなるグラフを作成するステップと、
該並列化テーブルからなるグラフをシリーズパラレルグラフに変換するステップと、
シリアルパス毎に、前記並列化テーブルをマージするステップと、
並列セクション毎に、前記並列化テーブルをマージするステップとを実行させる、
コード生成プログラム。
【請求項７】
前記マージされた並列化テーブルのエントリのプロセッサ数とコストに基づき、利用可能なプロセッサの数の範囲でコスト的に最良のエントリを選ぶステップと、
該最良のエントリのクラスタに基づき、個々のプロセッサに割り当てるための実行可能コードを生成するステップをさらに有する、請求項６に記載のコード生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、マルチコアまたはマルチプロセッサ・システムにおいて、プログラムの実行を高速化する技法に関する。
【背景技術】
【０００２】
近年、科学技術計算、シミュレーションなどの分野で、複数のプロセッサをもつ、いわゆるマルチプロセッサ・システムが使用されている。そのようなシステムでは、アプリケーション・プログラムは、複数のプロセスを生成して、個別のプロセッサに、プロセスを割り当てる。それらのプロセッサは、例えば、共有のメモリ空間を利用して互いに通信しながら、処理を進める。
【０００３】
最近になって特に盛んに開発されるようになってきたシミュレーションの分野として、ロボット、自動車、飛行機などのメトカトロニクスのプラントのシミュレーション用ソフトウェアがある。電子部品とソフトウェア技術に発展の恩恵により、ロボット、自動車、飛行機などでは、神経のように張り巡らされたワイヤ結線や無線ＬＡＮなどを利用して、大部分の制御が電子的に行われる。
【０００４】
それらは、本来的には機械的装置であるのに、大量の制御ソフトウェアをも内蔵している。そのため、製品の開発に当たっては、制御プログラムの開発とそのテストに、長い時間と、膨大な費用と、多数の人員を費やす必要が出てきた。
【０００５】
このようなテストにために従来行われている技法として、ＨＩＬＳ(Hardware In the Loop Simulation)がある。特に、自動車全体の電子制御ユニット（ＥＣＵ）をテストする環境は、フルビークルＨＩＬＳと呼ばれる。フルビークルＨＩＬＳにおいては、実験室内で、本物のＥＣＵが、エンジン、トランスミッション機構などをエミュレーションする専用のハードウェア装置に接続され、所定のシナリオに従って、テストが行われる。ＥＣＵからの出力は、監視用のコンピュータに入力され、さらにはディスプレイに表示されて、テスト担当者がディスプレイを眺めながら、異常動作がないかどうか、チェックする。
【０００６】
しかし、ＨＩＬＳは、専用のハードウェア装置を使い、それと本物のＥＣＵの間を物理的に配線しなくてはならないので、準備が大変である。また、別のＥＣＵに取り替えてのテストも、物理的に接続し直さなくてはならないので、手間がかかる。さらに、本物のＥＣＵを用いたテストであるため、テストに実時間を要する。従って、多くのシナリオをテストすると、膨大な時間がかかる。また、ＨＩＬＳのエミュレーション用のハードウェア装置は、一般に、非常に高価である。
【０００７】
そこで近年、高価なエミュレーション用ハードウェア装置を使うことなく、ソフトウェアで構成する手法が提案されている。この手法は、ＳＩＬＳ(Software In the Loop Simulation)と呼ばれ、ＥＣＵに搭載されるマイクロコンピュータ、入出力回路、制御のシナリオ、エンジンやトランスミッションなどのプラントを全て、ソフトウェア・シミュレータで構成する技法である。これによれば、ＥＣＵのハードウェアが存在しなくても、テストを実行可能である。
【０００８】
このようなＳＩＬＳの構築を支援するシステムとして例えば、MathWorks社から入手可能なシミュレーション・モデリング・システムである、MATLAB(R)/Simulink(R)がある。MATLAB(R)/Simulink(R)を使用すると、図１に示すように、画面上にグラフィカル・インターフェースによって、矩形で示す機能ブロックを配置し、矢印のようにその処理の流れを指定することによって、シミュレーション・プログラムを作成することができる。これらのブロック線図は、シミュレーションの１タイムステップ分の処理を表しており、これが所定回繰り返されることにより、シミュレーション対象となるシステムの時系列における振る舞いを得ることができる。
【０００９】
こうして、MATLAB(R)/Simulink(R)上で、機能ブロックなどのブロック線図が作成されると、Real-Time Workshop(R)の機能により、等価な機能のＣ言語のソース・コードに変換することができる。このＣ言語のソース・コードをコンパイルすることにより、別のコンピュータ・システムで、ＳＩＬＳとして、シミュレーションを実行することができる。
【００１０】
そこで、図２(a)に示すように、機能ブロックを、クラスタＡ、Ｂ、Ｃ及びＤのように複数のクラスタに分け、それぞれを個別のＣＰＵにアサインする技法が従来より実施されている。このようなクラスタリングのために、例えば、コンパイラの技術で知られている強連結成分の検出などの技法が用いられる。クラスタリングする主要な目的は、同一クラスタ内の機能ブロックの通信コスト削減である。図２(b)は、個々のクラスタＡ、Ｂ、Ｃ及びＤをブロックで表現した図である。
【００１１】
ところで、マルチプロセッサシステムにおいて、複数のタスクまたはプロセスを、個々のプロセッサに割り当てることによって処理を並列化することに関する技術は、下記の文献に記載されている。
【００１２】
特開平９−９７２４３号公報は、マルチプロセッサシステムにおいて並列タスクで構成されたプログラムのターンアラウンドタイムを短縮することを課題とするものであり、開示されているシステムにおいて、並列タスクで構成されるプログラムのソースプログラムをコンパイラがコンパイルして目的プログラムを生成し、コンパイラは、並列タスクの各タスク間で行われるタスク間通信のデータ量を保持するタスク間通信量テーブルを生成する。タスクスケジューラは、タスク間通信量テーブルとマルチプロセッサシステムの全プロセッサの組における単位データ当たりのデータ通信時間を定義するプロセッサ通信コストテーブルとからタスク間通信の通信時間が最短となるプロセッサを並列タスクのタスクに割り当てる旨決定し、プロセッサ管理テーブルに登録する。
【００１３】
特開平９−１６７１４４号公報は、複数種類の演算手順、および、プロセッサ間での通信処理に対応する、複数種類の通信手順を記述した、並列処理を行なうための並列プログラムを変更する方法であって、現在使用している通信手順にしたがって行なわれている通信処理の通信量を増加したと仮定すると、前記並列処理の開始から終了までの時間が短くなる場合、並列プログラム内での通信手順の並べ替えを行ない、２以上の通信手順を合体するように、記述内容を変更する、プログラム作成方法を開示する。
【００１４】
特開２００７−０４８０５２号公報は、並列処理を最適化するコンパイラに関するものであって、コンパイラは、対象プログラムを実行するプロセッサ・コアの個数である実行コア数を記録している。コンパイラは、まず、対象プログラムの中から単一のプロセッサ・コアで連続して実行すべき実行パスの候補である支配的パスを検出する。次に、実行コア数以下の数の支配的パスを選択することによりマルチコア・プロセッサにおいて並列にまたは連続して実行すべきタスクのクラスタを生成する。次に、生成されたクラスタ毎に、実行コア数以下の１つまたは複数の自然数の各々について、当該クラスタを当該自然数に等しい個数のプロセッサ・コアで実行した場合の実行時間を算出する。そして、算出された実行時間に基づいて各クラスタの実行のために割り当てるべきプロセッサ・コアの個数を選択する。
【００１５】
しかし、これらの開示技術は、シミュレーションプログラムの実行のように、図２(b)に示すような有効グラフの処理が繰り返し実行される場合には、必ずしも効率的な並列化を達成しない。
【００１６】
一方、Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni, David I. August, “Speculative Decoupled Software Pipelining”, In proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, 2007に記述されている技術は、図２(b)に示すクラスタの並列化に適合する。すなわち、複数のクラスタをそれぞれ、個々のプロセッサに割当てることによって、図３に示すように、パイプライン実行することができる。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】特開平９−９７２４３号公報
【特許文献２】特開平９−１６７１４４号公報
【特許文献３】特開２００７−０４８０５２号公報
【非特許文献】
【００１８】
【非特許文献１】Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni, David I. August, “Speculative Decoupled Software Pipelining”, In proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, 2007
【発明の概要】
【発明が解決しようとする課題】
【００１９】
しかし、非特許文献１に示す技法では、強連結成分のクラスタのサイズが大きくなる傾向にあるシステムでは最適解が得にくいという問題がある。
【００２０】
これは、非特許文献１に示す技法では、強連結成分の内部にある並列性を活かすことができないためである。
【００２１】
従って、この発明の目的は、強連結成分のサイズが大きくなる傾向がある、シミュレーション・モデルにおいて、強連結成分の内部の並列性も活かして、高速な動作を可能とする並列化技法を提供することにある。
【課題を解決するための手段】
【００２２】
この発明の実施の前提として、マルチコアまたはマルチプロセッサの環境にあるものとする。このようなシステムにおいて、並列化するためのプログラムは、これには限定されないが、MATLAB(R)/Simulink(R)などのシミュレーション・モデリング・ツールで作成されているものとする。すなわち、プログラムは、処理の流れを示す有向のエッジで結ばれた制御ブロックで記述されている。
【００２３】
すると、本発明に従う最初のステップは、前記エッジのうち、予測性が高いエッジを選ぶことである。
【００２４】
次のステップでは、本発明に係る処理プログラムが、強連結クラスタを見出す。その後、ブロックを１つだけ含む、互いに隣接する強連結クラスタを、並列化を阻害しないように結合し、これを非強連結クラスタとする。
【００２５】
次のステップでは、本発明に係る処理プログラムが、形成された強連結クラスタと、非強連結クラスタの各々につき、並列化テーブルを作成する。
【００２６】
次のステップでは、本発明に係る処理プログラムが、強連結クラスタと非強連結クラスタをノードとしたグラフを、シリーズパラレルグラフに変換する。
【００２７】
次のステップでは、本発明に係る処理プログラムが、シリーズパラレルグラフの階層に基づき、並列化テーブルをマージする。
【００２８】
次のステップでは、本発明に係る処理プログラムが、得られた並列化テーブルから最善の構成を選び、この構成に基づき、実際にクラスタをコアまたはプロセッサに個々に割り当てる。
【発明の効果】
【００２９】
この発明によれば、強連結成分のサイズが大きくなる傾向があるシミュレーション・モデルにおいて、強連結成分の並列性も活かした並列化技法によって、動作の高速化が図られる。
【図面の簡単な説明】
【００３０】
【図１】ブロック線図の例を示す図である。
【図２】クラスタ化されたブロック線図の例を示す図である。
【図３】パイプライン化されたブロック線図の例を示す図である。
【図４】本発明を実施するためのハードウェアの例を示す図である。
【図５】機能ブロック図を示す図である。
【図６】全体の処理の概要フローチャートを示す図である。
【図７】ブロック線図の例を示す図である。
【図８】予測可能なエッジが除去されたブロック線図の例を示す図である。
【図９】クラスタ化されたブロック線図の例を示す図である。
【図１０】並列化テーブルの例を示す図である。
【図１１】クラスタと並列化テーブルの対応を示す図である。
【図１２】並列化テーブルから生成されたグラフを示す図である。
【図１３】並列化テーブルのマージ処理を示す図である。
【図１４】マージされた並列化テーブルの例を示す図である。
【図１５】ＳＣＣ検出処理のフローチャートを示す図である。
【図１６】ＳＣＣを統合する処理のフローチャートを示す図である。
【図１７】Clear_path_and_assign()処理のフローチャートを示す図である。
【図１８】クラスタ毎に並列化テーブルを計算する処理のフローチャートを示す図である。
【図１９】クラスタ毎に並列化テーブルを計算する処理のフローチャートを示す図である。
【図２０】並列化テーブルのグラフを構成する処理のフローチャートを示す図である。
【図２１】並列化テーブルを統合する処理のフローチャートを示す図である。
【図２２】get_series_parallel_nested_tree()処理のフローチャートを示す図である。
【図２３】get_table()処理のフローチャートを示す図である。
【図２４】series_merge()処理のフローチャートを示す図である。
【図２５】parallel_merge()処理のフローチャートを示す図である。
【図２６】merge_clusters_in_shared()処理のフローチャートを示す図である。
【図２７】統合された並列化テーブルから最良の構成を選択する処理のフローチャートを示す図である。
【発明を実施するための形態】
【００３１】
以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。
【００３２】
先ず、図４を参照して、本発明を実施するために使用されるコンピュータのハードウェアについて説明する。図４において、ホスト・バス４０２には、複数のＣＰＵ１  ４０４ａ、ＣＰＵ２  ４０４ｂ、ＣＰＵ３  ４０４ｃ、・・・ＣＰＵｎ  ４０４ｎが接続されている。ホスト・バス４０２にはさらに、ＣＰＵ１  ４０４ａ、ＣＰＵ２  ４０４ｂ、ＣＰＵ３  ４０４ｃ、・・・ＣＰＵｎ  ４０４ｎの演算処理のためのメイン・メモリ４０６が接続されている。
【００３３】
一方、Ｉ／Ｏバス４０８には、キーボード４１０、マウス４１２、ディスプレイ４１４及びハードティスク・ドライブ４１６が接続されている。Ｉ／Ｏバス４０８は、Ｉ／Ｏブリッジ４１８を介して、ホスト・バス４０２に接続されている。キーボード４１０及びマウス４１２は、オペレータが、コマンドを打ち込んだり、メニューをクリックするなどして、操作するために使用される。ディスプレイ４１４は、必要に応じて、後述する本発明に係るプログラムをＧＵＩで操作するためのメニューを表示するために使用される。
【００３４】
この目的のために使用される好適なコンピュータ・システムのハードウェアとして、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｘがある。その際、ＣＰＵ１  ４０４ａ、ＣＰＵ２  ４０４ｂ、ＣＰＵ３  ４０４ｃ、・・・ＣＰＵｎ  ４０４ｎは、例えば、インテル（Ｒ）Ｘｅｏｎ（Ｒ）であり、オペレーティング・システムは、Ｗｉｎｄｏｗｓ（商標）Ｓｅｒｖｅｒ  ２００３である。オペレーティング・システムは、ハードティスク・ドライブ４１６に格納され、コンピュータ・システムの起動時に、ハードティスク・ドライブ４１６からメイン・メモリ４０６に読み込まれる。
【００３５】
本発明を実施するためには、マルチプロセッサ・システムを用いることが必要である。ここでマルチプロセッサ・システムとは、一般に、独立に演算処理し得るプロセッサ機能のコアを複数もつプロセッサを用いるシステムを意図しており、従って、マルチコア・シングルプロセッサ・システム、シングルコア・マルチプロセッサ・システム、及びマルチコア・マルチプロセッサ・システムのどれかでよいことを理解されたい。
【００３６】
なお、本発明を実施するために使用可能なコンピュータ・システムのハードウェアは、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｘに限定されず、本発明のシミュレーション・プログラムを走らせることができるものであれば、任意のコンピュータ・システムを使用することができる。オペレーティング・システムも、Ｗｉｎｄｏｗｓ（Ｒ）に限定されず、Ｌｉｎｕｘ（Ｒ）、Ｍａｃ  ＯＳ（Ｒ）など、任意のオペレーティング・システムを使用することができる。さらに、シミュレーション・プログラムを高速で動作させるために、ＰＯＷＥＲ（商標）６ベースで、オペレーティング・システムがＡＩＸ（商標）のＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｐなどのコンピュータ・システムを使用してもよい。
【００３７】
ハードティスク・ドライブ４１６にはさらに、MATLAB(R)/Simulink(R)、Ｃコンパイラまたは、Ｃ＋＋コンパイラ、後述する本発明に係る解析、平坦化、クラスタリング、展開のためのモジュール、ＣＰＵ割り当て用コード生成モジュール、処理ブロックの期待される実行時間を測定するためのモジュールなどが格納されており、オペレータのキーボードやマウス操作に応答して、メイン・メモリ４０６にロードされて実行される。
【００３８】
尚、使用可能なシミュレーション・モデリング・ツールは、MATLAB(R)/Simulink(R)に限定されず、オープンソースのScilab/Scicosなど任意のシミュレーション・モデリング・ツールを使用することが可能である。
【００３９】
あるいは、場合によっては、シミュレーション・モデリング・ツールを使わず、直接、Ｃ、Ｃ＋＋などでシミュレーション・システムのソース・コードを書くことも可能であり、その場合にも、個々の機能が、互いに依存関係にある個別の機能ブロックとして記述できるなら、本発明は適用可能である。
【００４０】
図５は、本発明の実施例に係る機能ブロック図である。各々のブロックは、基本的に、ハードティスク・ドライブ４１６に格納されているモジュールに対応する。
【００４１】
図５において、シミュレーション・モデリング・ツール５０２は、MATLAB(R)/Simulink(R)、Scilab/Scicosなどの既存の任意のツールでよい。シミュレーション・モデリング・ツール５０２は、基本的には、オペレータが、ディスプレイ４１４上でＧＵＩ的に機能ブロックを配置し、数式など必要な属性を記述し、必要に応じて、機能ブロック間を関連付けてブロック線図を記述することを可能ならしめるような機能をもつ。シミュレーション・モデリング・ツール５０２はさらに、記述されたブロック線図に等価な機能を記述するＣのソースコードを出力する機能をもつ。Ｃ以外にも、Ｃ＋＋、ＦＯＲＴＲＡＮなどを使用することができる。特に、後述するＭＤＬファイルは、Simulink(R)独自のフォーマットであり、機能ブロック間の依存関係を記述するためのものである。
【００４２】
なお、シミュレーション・モデリング・ツールは、別のパーソナル・コンピュータに導入して、そこで生成されたソース・コードを、ネットワークなどを経由して、ハードティスク・ドライブ４１６にダウンロードするようにすることもできる。
【００４３】
こうして出力されたソース・コード５０４は、ハードティスク・ドライブ４１６に保存される。
【００４４】
解析モジュール５０６は、ソースコード５０４を入力して構文解析し、ブロックのつながりを、グラフ表現５０８に変換する。グラフ表現５０８のデータは、好適には、ハードディスク・ドライブ４１６に格納される。
【００４５】
クラスタリング・モジュール５１０は、グラフ表現５０８を読み取って、強連結成分（ＳＣＣ）を見出すことによるクラスタリングを行う。強連結とは、ある有向グラフにおいて、任意の二点間に有向路が存在することである。そして、強連結成分とは、与えられたグラフの部分グラフであって、それ自体では強連結で、それ以上頂点を追加すると強連結でなくなるような部分グラフのことである。
【００４６】
並列化テーブル処理モジュール５１４は、クラスタリング・モジュール５１０によってクラスタリングされたクラスタに基づき、後で詳細に説明する処理によって、並列化テーブル５１６を作成する機能をもつ。
【００４７】
作成された並列化テーブル５１６は、好適にはメイン・メモリ４０６に配置されるが、ハードディスク・ドライブ４１６に配置してもよい。
【００４８】
コード生成モジュール５１８は、グラフ表現５０８と、並列化テーブル５１６を参照して、コンパイラ５２０がコンパイルするためのソースコードを生成する。コンパイラ５２０が想定するプログラミング言語としては、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）などのマルチコア、またはマルチプロセッサに対応したプログラミングが可能な任意のプログラミング言語を使用することができ、コード生成モジュール５１８はそれに対応して、クラスタ毎に、ソースコードを生成することになる。
【００４９】
コンパイラ５２０が生成したクラスタ毎の実行可能バイナリ・コード（図示しない）は、並列化テーブル５１６などに記述された内容に基づき、異なるコアまたはプロセッサに割り当てられて、オペレーティング・システムの作用により、実行環境５２２で実行される。
【００５０】
以下、一連のフローチャートに従い、本発明の処理をより詳細に説明するが、その前に、用語と記法の定義を与えておく。
【００５１】
＜定義＞
・集合
|Ｘ|は、集合Ｘに含まれている要素の数をあらわす。
¬Ｘは、集合Ｘの補集合をあらわす。
Ｘ−Ｙ = Ｘ∩¬Ｙ
Ｘ[i]は、集合Ｘのi番目の要素である。
MAX(Ｘ)は、集合Ｘに記録された最大値である。
FIRST(Ｘ)は、集合Ｘの最初の要素である。
SECOND(Ｘ)は、集合Ｘの最初の要素である。
【００５２】
・グラフ
グラフＧは、＜Ｖ，Ｅ＞であらわす。
Ｖは、グラフＧのノードの集合である。
Ｅは、グラフＧの頂点（ノード）を結ぶエッジの集合である。
PARENT(ｖ)は、グラフＧにおけるノードｖ(∈Ｖ)の親ノードの集合である。
CHILD(ｖ)は、グラフＧにおけるノードｖ(∈Ｖ)の子ノードの集合である。
SIBLING(ｖ)は、{ｃ：ｃ!=ｖ, ｃ∈CHILD(ｐ),ｐ∈PARENT(ｖ)｝で定義される。
エッジｅ = (ｕ,ｖ),(ｕ∈Ｖ,ｖ∈Ｖ)について、
SRC(ｅ) := ｕ
DEST(ｅ) := ｖ
【００５３】
・クラスタ
クラスタとは、ブロックの集合を意味する。ＳＣＣもブロックの集合であり、クラスタの一種である。
WORKLOAD(Ｃ)とは、クラスタＣのワークロードのことである。クラスタＣのワークロードとは、クラスタＣにおける全てのブロックのワークロードを足し合わせることによって計算される。
START(Ｃ)は、クラスタＣを含むクラスタの集合に対して、静的なスケジューリングが実行された際に、クラスタＣの開始時刻を表す。
END(Ｃ)は、クラスタＣを含むクラスタの集合に対して、静的なスケジューリングが実行された際に、クラスタＣの終了時刻を表す。
【００５４】
・並列化テーブルＴ
Ｔは、下記のようなエントリＩの集合である。
Ｉ := ＜プロセッサの数, スケジュール長, クラスタの集合＞
ENTRY(Ｔ,ｉ)とは、並列化テーブルＴにおいて、最初の要素がｉであるエントリである。
LENGTH(Ｔ,ｉ)とは、並列化テーブルＴにおいて、最初の要素がｉであるエントリの第２の要素である。そのようなエントリがないなら、∞を返す。
CLUSTERS(Ｔ,ｉ)とは、並列化テーブルＴにおいて、プロセッサのフィールドがｉであるエントリに記録されているクラスタの集合である。
【００５５】
・シリーズパラレルグラフ
シリーズパラレル入れ子ツリーＧsp-treeは、＜Ｖsp-tree,Ｅsp-tree＞で表される、バイナリ・ツリーである。
Ｖsp-treeは、Ｇsp-treeのノードの集合を表し、各ノードはエッジと記号の組(ｆ,ｓ)となる。ここで、ｆ∈Ept-sp（ここで、Ept-spは、あるグラフのエッジを要素とする集合）であり、ｓ∈{"L","S","P"}である。
"L"は、葉(leaf)、"S"は直列(series)、"P"は並列(parallel)という種別をあらわす記号である。
Ｅsp-treeは、ツリーＧsp-treeのエッジ(ｕ,ｖ)の集合である。
EDGE(ｎ)(ｎ∈Ｖsp-tree)は、ｎの最初の要素である。
SIGN(ｎ)(ｎ∈Ｖsp-tree)は、ｎの２番目の要素である。
LEFT(ｎ)(ｎ∈Ｖsp-tree)は、ツリーＧsp-treeにおけるノードｎの左の子ノードである。
RIGHT(ｎ)(ｎ∈Ｖsp-tree)は、ツリーＧsp-treeにおけるノードｎの右の子ノードである。
【００５６】
次に、図６を参照して、本発明の全体的な概要フローチャートについて説明する。図７に、シミュレーション・モデリング・ツール５０２で作成した、ブロック線図を、解析モジュールがグラフ表現に変換した図を示す。
【００５７】
先ず最初に、このグラフＧ := ＜Ｖ,Ｅ＞によってあらわす。Ｖはブロックの集合で、Ｅはエッジの集合である。
【００５８】
図６に戻って、ステップ６０２では、予測可能なエッジが除去される。予測可能なエッジは、シミュレーションモデルを作成した人が、モデルの性質を考慮して予め、手作業で選択することを想定している。
【００５９】
そのようにして予測可能なエッジを除去した後のグラフ表現を、
Ｇpred := ＜Ｖpred,Ｅpred＞とあらわす。すると、Ｖpred = Ｖであるが、Ｅpred = Ｅ - 予測可能なエッジの集合となる。
【００６０】
予測可能なエッジとは、一般的には物体の速度など、連続的で、短時間で急激な変化を示さないようなシグナル（ブロック線図上のエッジ）を選択するものである。典型的には、モデル作成者に、モデル上でアノテーションを書いてもらうことで、コンパイラがどのエッジが予測可能であるかを知ることができる。
【００６１】
図８に、図７のグラフから予測可能なエッジを取り除いたブロック線図を示す。図７において、７０２が予測可能なエッジである。
【００６２】
ステップ６０４では、クラスタリング・モジュール５１０が、強連結成分（ＳＣＣ）を検出する。図９において、そのようにして検出された、一つ以上のブロックを含むＳＣＣは、クラスタ９０２、９０４、９０６及び９０８で示されている。また、クラスタ９０２、９０４、９０６及び９０８に含まれないブロックは、それぞれが一つのブロックからなるＳＣＣであるとする。
このように検出されたＳＣＣを以って、ＳＣＣのグラフを、
ＧSCC := ＜ＶSCC,ＥSCC＞とあらわす。
ここで、ＶSCCは、このアルゴリズムによって作成されたＳＣＣの集合であり、
ＥSCCは、ＶSCCにおいてＳＣＣを接続するエッジの集合である。
さらにまたここでは、ノードがループを構成するＳＣＣ（すなわち、二つ以上のブロックを含むＳＣＣ）の集合であるＶloopも作成される。
【００６３】
ステップ６０６では、クラスタリング・モジュール５１０によって、ブロックを一つだけ含む隣接するＳＣＣが、その後の並列化を妨げないように統合され、非ＳＣＣクラスタが形成される。その状況は、図１１に示されている。
このように統合されたグラフを、Ｇarea := ＜Ｖarea,Ｅarea＞とあらわす。
ここで、Ｖareaは、このアルゴリズムによって統合されて新たにできた非ＳＣＣクラスタと、このアルゴリズムで変化の無かったＳＣＣクラスタの集合であり、
Ｅareaは、Ｖareaの要素間を接続するエッジの集合である。
さらにまたここでは、新しく作成された非ＳＣＣクラスタの集合である、Ｖnon-loopも作成される。
【００６４】
ステップ６０８では、並列化テーブル処理モジュール５１４が、Ｖloopにおける各クラスタ毎に並列化テーブルを計算する。これにより、並列化テーブルの集合Ｖpt-loopが得られる。
【００６５】
ステップ６１０では、並列化テーブル処理モジュール５１４が、Ｖnon-loopにおける各クラスタ毎に並列化テーブルを計算する。これにより、並列化テーブルの集合Ｖpt-non-loopが得られる。
【００６６】
このようにして得られた並列化テーブルを図１１に示す。並列化テーブル１１０２、１１０４、１１０６、１１０８がＶpt-loopの要素であり、並列化テーブル１１１０、１１１２、１１１４、１１１６がＶpt-non-loopの要素である。なお、並列化テーブルのフォーマットは、図１０に示すように、各エントリが、可用なプロセッサの数と、ワークロード、クラスタの集合からなる。
【００６７】
ステップ６１２では、並列化テーブル処理モジュール５１４が、並列化テーブルをノードとするグラフを構築する。
【００６８】
このように構築されたグラフを、Ｇpt := ＜Ｖpt,Ｅpt＞とあらわす。
ここで、Ｖptは、このアルゴリズムによって作成された並列化テーブルの集合であり、
Ｅptは、Ｖptの要素間を接続するエッジの集合である。
【００６９】
ステップ６１４では、並列化テーブル処理モジュール５１４が、Ｖpt中の並列化テーブルを１つに統合する。そのような統合処理は、まずGptをシリーズパラレルグラフに変換し、そこから、シリーズパラレル入れ子ツリーを生成する。ここで生成されるシリーズパラレル入れ子ツリーの例を、図１２の１２０２に示す。この例では、元々Ｇptがシリーズパラレルグラフであったため、シリーズパラレルグラフへの変換過程は示されていない。このように生成されたシリーズパラレル入れ子ツリーの構造に従い、並列化テーブルが統合されていく。この例を、図１３に示す。例えば、並列化テーブルＦ，Ｇを統合し、新しい並列化テーブルＳＰ６を作成する。続いて、ＳＰ６と並列化テーブルＥが結合され、新しい並列化テーブルＳＰ４が作成される。このように、シリーズパラレル入れ子ツリーの構造に従って並列化テーブルの結合が進むと、最終的に一つの並列化テーブルＳＰ０が出来上がり、この最終的な一つの並列化テーブルをTunifiedとする。
【００７０】
統合された並列化テーブルＴunifiedの例を、図１４に示す。
【００７１】
並列化テーブル処理モジュール５１４は、統合された並列化テーブルＴunifiedから最良の構成を選択する。その結果、結果のクラスタの集合Ｒfinalが得られる。
図１４の例では、集合Ｒfinal = { C'''1, C''2, C'3, C4} である。
【００７２】
以下、図６の概要フローチャートの各ステップを、個別のフローチャートを使用して、より詳細に説明する。
【００７３】
図１５は、図６における、ＳＣＣを見出すためのステップ６０４をより詳細に説明するフローチャートである。この処理は、図５のクラスタリング・モジュール５１０が実行する。
示されているステップ１５０２において、以下の処理が行われる。
SCCアルゴリズムを Gpredに適用する。このSCCアルゴリズムとしては、例えば、R. Tarjan, “Depth-first search and linear graph algorithms” SIAM Journal on Computing, pp. 146-160, 1972に記載されている。
Vscc = そのアルゴリズムによって得られたSCCの集合
Escc = { (C, C’) : C∈Vscc  , C’∈Vscc  , C!=C’, 
∃(u, v) ∈Epred, u∈C, v∈C’}
Gscc = <Vscc , Escc>
Vloop = {C : C∈Vscc , |C| > 1}
【００７４】
図１６は、図６における、ブロックを１つだけ含むＳＣＣを統合ためのステップ６０６をより詳細に説明するフローチャートである。この処理も、クラスタリング・モジュール５１０が実行する。
【００７５】
ステップ１６０２では、下記のように変数がセットされる。
H = {C : C ∈ {Vloop ∪{C’: C’ ∈Vscc - Vloop , |PARENT(C’)| = 0}} }
S = スタック, T = SCCと新しいクラスタの間の空の写像.
Varea = 新しいクラスタの空集合
【００７６】
ステップ１６０４では、Hの全ての要素が処理されたかどうかが判断され、もしそうでないなら、ステップ１６０６に進み、そこで、Hにおける未処理SCCを１つ取り出しCとする。
【００７７】
ステップ１６０８では、C∈Vloopかどうかが判断され、もしそうなら、ステップ１６１０に進み、そこで、{C’ : C’∈{CHILD(C)∩¬Vloop }} における全ての要素をSに入れる、という処理が行われる。
ここで¬Vloopは、VSCCを全体集合としたときのVloopの補集合である。
【００７８】
次に、ステップ１６１２に進んで、新しい空クラスタCnewを作成することと、CnewをVareaに加えることが行われる。
【００７９】
ステップ１６０８に戻って、C∈Vloopでないなら、ステップ１６１４で、CがSに入れられて、ステップ１６１２に進む。
【００８０】
ステップ１６１６では、|S| = 0かどうかが判断され、もしそうなら、ステップ１６０４に戻る。
【００８１】
ステップ１６１６で、|S| = 0でないと判断されると、ステップ１６１８に進み、そこで、次のような処理が行われる。
SからCを取り出す
(C, Cnew) をTに入れる
F = CHILD(C)
【００８２】
次に、ステップ１６２０に進み、そこで、|F| = 0かどうかが判断され、もしそうなら、ステップ１６２０に戻る。
【００８３】
ステップ１６２０で、|F| = 0でないと判断されると、ステップ１６２２に進み、そこで、Fから１つの要素Cchildを取得する処理が行われる。
【００８４】
次にステップ１６２４で、Cchild∈Hかどうかが判断され、もしそうなら、ステップ１６２０に戻る。
【００８５】
ステップ１６２４で、Cchild∈Hでないと判断されると、ステップ１６２６で、
|{(Cchild, C’) ∈T : C’ ∈Varea }| = 0かどうか判断され、もしそうなら、ステップ１６２８で、CchildをSに入れた後、ステップ１６２０に戻る。
【００８６】
ステップ１６２６で、|{(Cchild, C’) ∈T : C’ ∈Varea }| = 0でないと判断されたら、ステップ１６３０で、C’== Cnew かどうか判断し、もしそうなら、ステップ１６２０に戻る。
【００８７】
ステップ１６３０で、C’== Cnewでないと判断されると、ステップ１６３２で、
Clear_path_and_assign(Cchild,T)という関数を呼び出し、ステップ１６２０に戻る。
Clear_path_and_assign(Cchild,T)の詳細は、後で詳しく説明する。
【００８８】
ステップ１６０４に戻って、Hの全てのCが処理されたと判断されると、ステップ１６３４に行って、
Tにおけるすべての要素 (C, Cnew) について, Cの全てのブロックをCnewに入れる
Varea = { Varea - {C’ : C’ ∈Varea ,  |C’| = 0} } ∪Vloop
Earea = {(C, C’) : C ∈Varea , C’ ∈Varea , C!=C’ , ∃(u, v) ∈Epred , u∈C, v∈C’}
Garea = <Varea, Earea>
Vnon-loop = Varea - Vloop
という処理を行って、終わる。
【００８９】
図１７は、図１６のフローチャートで呼び出されるClear_path_and_assign(Cchild,T)という関数の処理の内容を示すフローチャートである。
【００９０】
ステップ１７０２では、下記のセットアップが行われる。
S1 = スタック
Cchild を S1に入れる。
Tから第一要素がCchildである要素 (Cchild, Cprev_new) を見つける。
新しい 空クラスタCnewを作成する。
CnewにVareaを入れる。
【００９１】
ステップ１７０４では、|S1| = 0かどうかが判断され、もしそうなら、処理は終了する。
【００９２】
ステップ１７０４で、|S1| = 0でないと判断されると、ステップ１７０６で、下記の処理が行われる。
CをS1から取り出す。
Tから第一要素がCである要素 (C, X)を除く,ただし、X∈Varea
(C, Cnew)をTに加える。
F1 = CHILD(C)
【００９３】
ステップ１７０８では、|F1| = 0かどうかが判断され、もしそうなら、ステップ１７０４に戻り、そうでなければ、ステップ１７１０に進み、そこでF1からCgcを取得する処理が行われる。
【００９４】
次にステップ１７１２に進み、そこで、Cgc∈Hかどうか判断され、もしそうなら、ステップ１７０８に戻る。
【００９５】
ステップ１７１２で、Cgc∈Hでないと判断されると、ステップ１７１６で、Tから 第１要素がCgcであるような要素(Cgc,Cgca) が見つけられ、次にステップ１７１８でCprev_new == Cgcaかどうか判断される。もしそうなら、ステップ１７１４に進み、そこで、CgcがS1に入れられ、そこから処理は、ステップ１７０８に戻る。そうでないなら、直ちにステップ１７０８に戻る。
【００９６】
次に、図１８のフローチャートを参照して、図６におけるステップ６０８における、Vloopにおける各クラスタ毎に並列化テーブルを計算する処理をより詳細に説明する。この処理は、図５の並列化テーブル処理モジュール５１４が実行する。
【００９７】
図１８において、ステップ１８０２では、mに、ターゲット・システムで利用可能なプロセッサの数がセットされる。
【００９８】
ステップ１８０４では、|Vloop| = 0かどうかが判断され、もしそうなら、この処理は完了する。
【００９９】
次のステップ１８０６では、次の処理が行われる。
i = 1
VloopからクラスタCを得る。
L = { (u, v) : u∈C, v∈C, (u, v) ∈Epred }
Gtmp = <C, L>
Tc = 0エントリの新しい並列化テーブル
ここで、Gtmp = <C, L>とは、Cに含まれるブロックをノードとし、Lに含まれるエッジをエッジとするグラフをGtmpとすることを表している。
【０１００】
ステップ１８０８では、i <= mかどうかが判断され、もしそうでなければ、ステップ１８１０で、TcをVpt-loopに入れてから、ステップ１８０４に戻る。
【０１０１】
ステップ１８０８で、i <= mであると判断されると、ステップ１８１２に進み、そこで、S = {s : s ∈C, | PARENT(s) ∩¬C | > 0 }とセットされる。
【０１０２】
次のステップ１８１４では、|S| = 0かどうかが判断され、もしそうなら、ステップ１８１６で、iを1増やして、ステップ１８０８に戻る。
【０１０３】
ステップ１８１４で、|S| = 0でないと判断されたなら、ステップ１８１８で、Sからsを得て、ステップ１８２０で、Gtmpからバックエッジの集合を検出する処理が行われる。これは例えば、Gtmpのエントリ・ノードがsであるという条件で、Alfred V. Aho , Monica S. Lam , Ravi Sethi ,and Jeffrey D. Ullman, “Compilers: Principles, Techniques, and Tools (2nd Edition)”, Addison Wesleyに記述されているような方法で行われる。
ここで、検出されたバックエッジの集合は、Bとおく。
そして、Gc = ＜C,L-B＞
【０１０４】
ステップ１８２２では、C中のブロックを、 i個のクラスタにクラスタ化する処理が行われる。これは例えば、Sih G. C., and Lee E. A , A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parallel Distrib. Syst. 4, 2 (Feb.), 75-87に記述されているようなマルチプロセッサ・スケジューリング方法を、利用可能なプロセッサの数がiであるという条件でGcに適用することによって、行われる。このようなスケジューリングの結果、各ブロックはいずれかのプロセッサで実行される形となり、一つのプロセッサによって実行されることとなったブロックの集合を一つのクラスタとする。
そうして、結果のクラスタの集合(i個のクラスタ)をRとおき、Gcの結果のスケジュール長をtとおく。
ここで、スケジュール長とは、上記のスケジューリングの結果、処理の開始から終了までに要する時間である。
またこのとき、上記のスケジューリングの結果、最も最初に実行されるブロックの処理の開始時刻を０とし、各クラスタの開始時刻と終了時刻を、それぞれ、そのクラスタが対応するプロセッサ上で最初にブロックの処理が実行される時刻と、最後のブロックの処理が終了する時刻として記録し、参照可能な状態にしておく。
【０１０５】
ステップ１８２４では、t’= LENGTH(Tc, i)として、ステップ１８２６に進み、そこで、t < t’かどうかが判断される。もしそうなら、ステップ１８２８でエントリ (i,t,R) をTCに入れてから、ステップ１８１４に戻る。そうでなければ、直ちにステップ１８１４に戻る。
【０１０６】
次に、図１９のフローチャートを参照して、図６におけるステップ６１０における、
Vnon-loopにおける各クラスタ毎に並列化テーブルを計算する処理をより詳細に説明する。この処理は、図５の並列化テーブル処理モジュール５１４が実行する。
【０１０７】
図１９において、ステップ１９０２では、mに、ターゲット・システムで利用可能なプロセッサの数がセットされる。
【０１０８】
ステップ１９０４では、|Vnon-loop| = 0かどうかが判断され、もしそうなら、この処理は完了する。
【０１０９】
ステップ１９０６で、|Vnon-loop| = 0でないと判断されると、ステップ１９０６で、iに1をセットし、Vnon-loopからクラスタCを取得し、Tcに0エントリの新しい並列化テーブルをセットする処理が行われる。
【０１１０】
ステップ１９０８では、i <= mかどうかが判断され、そうでなければ、ステップ１９１０に進んで、TcをVpt-non-loopに入れた後、処理はステップ１９０４に戻る。
【０１１１】
ステップ１９０８で、i <= mであると判断されると、ステップ１９１２では、C中のノードを、i個のクラスタにクラスタ化する処理が行われる。これは、これは例えば、G. Ottoni, R. Rangan, A. Stoler, and D. I. August, “Automatic Thread Extraction with Decoupled Software Pipelining”, In Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture, November 2005に記述されているようなマルチプロセッサ・スケジューリング方法を、利用可能なプロセッサの数がiであるという条件でGcに適用することによって、行われる。
【０１１２】
そして、Rに、i個のクラスタからなる結果の集合がセットされ、tにMAX_WORKLOAD(R)がセットされ、(i, t, R)をTCに入れた後、iを1だけ増分して、ステップ１９０８に戻る。またこのとき、上記のスケジューリングの結果、最も最初に実行されるブロックの処理の開始時刻を０とし、各クラスタの開始時刻と終了時刻を、それぞれ、そのクラスタが対応するプロセッサ上で最初にブロックの処理が実行される時刻と、最後のブロックの処理が終了する時刻として記録し、参照可能な状態にしておく。
【０１１３】
図２０は、並列化テーブルからなるグラフを構成するための処理を示すフローチャートである。この処理は、図５の並列化テーブル処理モジュール５１４が実行する。そのステップ２００２ではまず、
Vpt := Vpt-loop ∪ Vpt-non-loopによって、２つのクラスタの合弁が得られる。
【０１１４】
次に、下記の式によって、並列化テーブルからなるグラフのエッジの集合を与える。
Ept := { (T, T’) : T ∈Vpt, T’∈Vpt, T!=T’,∃(u, v) ∈Epred, 
u∈FIRST(CLUSTERS(T,1)) , v∈FIRST(CLUSTERS(T’,1)) }
【０１１５】
以上から、Gpt := <Vpt,Ept>によって、並列化テーブルからなるグラフが構成される。
なお、CLUSTERS(T,1)は、常に１つのクラスタを返す。なぜなら、二番目の引数が示すように、利用可能なプロセッサの数が１だからである。
また、同一の終点の対をもつエッジが、１つに統合される。
【０１１６】
次に、図２１のフローチャートを参照して、並列化テーブルの統合処理について説明する。この処理は、図５の並列化テーブル処理モジュール５１４が実行する。
【０１１７】
ステップ２１０２ではまず、
Gpt を、直接−並列グラフ Gpt-sp = <Vpt-sp, Ept-sp> に変換する処理が行われる。これは例えば、Arturo Gonzalez Escribano, Valentin Cardenoso Payo, and Arjan J.C. van Gemund, “Conversion from NSP to SP graphs”, Tech. Rep. TRDINFO -01-97, Universidad de Valladolid, Valladolid (Spain), 1997に記述されているような方法で、行われる。
【０１１８】
次に、下記によって、Vpt-spがえられる。
Vpt-sp = Vpt∪Vdummy
ここで、Vdummyは、このアルゴリズムによって追加されるダミー・ノードの集合である。各ダミー・ノードは、並列化テーブル{(i,0,φ):i=1,...,m}であり、mは、ターゲット・システムにおける利用可能なプロセッサの数である。
また、下記によって、Ept-spがえられる。
Ept-sp = Ept∪Edummy
ここで、Edummyは、Vpt-spの要素を接続する、このアルゴリズムによって追加されたダミー・エッジである。
【０１１９】
ステップ２１０４では、下記の式によって、Gsp-treeを得る。
Gsp-tree := get_series_parallel_nested_tree(Gpt-sp)
なお、get_series_parallel_nested_tree()という関数については、後で詳細に説明する。
【０１２０】
ステップ２１０６では、nroot := Gsp-treeのルート・ノードとセットされる。このルート・ノードとは、親ノードをもたないノードであり、そのようなノードは、Gsp-treeに唯一存在する。
次に、下記の式によって、Tunifiedを得る。
Tunified := get_table(nroot)
なお、get_table()という関数については、後で詳細に説明する。
【０１２１】
次に、図２２のフローチャートを参照して、get_series_parallel_nested_tree(Gpt-sp)の動作について、説明する。
【０１２２】
まず、ステップ２２０２では、Vcpy = Vpt-sp, Ecpy = Ept-spと、一旦コピーする。
【０１２３】
ステップ２２０４では、Scand = { T: T∈Vcpy , |{e=(T’,T) : e∈Ecpy}|=1 
∧ |{e=(T, T'') : e∈Ecpy}|=1 }によって、集合を更新する。
【０１２４】
ステップ２２０６では、|Scand| = 0かどうかが判断され、もしそうなら、
Gsp-tree := <Vsp-tree, Esp-tree>として、処理を終る。
【０１２５】
ステップ２２０６で、|Scand| = 0でないと判断されたなら、ステップ２２１０に進んで、以下の処理が行われる。
まず、ScandからTを取得し、
f := (T’, T ), f’ := (T, T'')  とし、
ここで (T’, T)∈Ecpy , (T, T'')∈Ecpy 
新しいエッジ f’’ = (T’, T'')を作成し、
nsnew = (f'',“S”)
nsnewを、Vsp-treeに入れる。
【０１２６】
次に、ステップ２２１２に進んで、そこで、fは新しく作成されたエッジかどうかが判断される。もしそうなら、ステップ２２１４に進んで、Vsp-treeからFIRST(n)=fであるようなノードnを見つける処理が行われる。
【０１２７】
一方、ステップ２２１２で、fは新しく作成されたエッジでないと判断されたなら、ステップ２２１６に進み、新しいツリーノード n = (f, “L”)を作成し、nをVsp-treeに入れる。
【０１２８】
ステップ２２１４または２２１６からは、ステップ２２１８に進み、そこで、(nsnew , n) を Esp-treeに入れる処理が行われる。
【０１２９】
次にステップ２２２０に進み、そこで、f'は新しく作成されたエッジかどうかが判断される。もしそうなら、ステップ２２２２に進み、Vsp-treeからFIRST(n')=f'であるようなノードn'を見つける処理が行われる。
【０１３０】
一方、ステップ２２２０で、f'は新しく作成されたエッジでないと判断されたなら、ステップ２２２４に進み、新しいツリーノード n' = (f', “L”)を作成し、n'をVsp-treeに入れる。
【０１３１】
ステップ２２２２または２２２４からは、ステップ２２２６に進み、そこで、(nsnew , n') を Esp-treeに入れる処理が行われる。さらに、P = { p=(T’, T'') : p∈Ecpy}とセットされる。
【０１３２】
次に、ステップ２２２８では、|P| = 0かどうかが判断され、もしそうなら、ステップ２２３０に進んで、そこで、f''をVcpyに入れ、次にステップ２２３２で、TをVcpyから除去してf'及びf''をEcpyから除去し、ステップ２２０４に戻る。
【０１３３】
ステップ２２２８に戻って、|P| = 0でないと判断されたなら、ステップ２２３４に進み、そこでPから１つの要素pを取得する。
【０１３４】
次にステップ２２３６で、Pが新しく作成されたエッジかどうかが判断され、もしそうなら、ステップ２２３８で、Vsp-treeからFIRST(r) = pであるようなノードrを見つける処理が行われる。
【０１３５】
ステップ２２３６で、pが新しく作成されたエッジでないと判断されると、ステップ２２４０に進み、そこで、新しいツリーノード r = (p, “L”)を作成し、rをVsp-treeに入れる処理が行われる。
【０１３６】
ステップ２２３８またはステップ２２４０からは、ステップ２２４２に進み、そこで、新しいエッジ f''' = (T',T'')を作成を作成し、npnew = (f''',"P")とセットし、 (npnew,nsnew) をETに入れ、(npnew, r)をETに入れ、pをEcpyから除去し、f'''をEcpyに入れる処理が行われる。
【０１３７】
ステップ２２４２からは、既に説明したステップ２２３２を経て、ステップ２２０４に戻る。
【０１３８】
図２３は、図２１のステップ２１０６で呼ばれる、get_table()という関数の処理の内容を示すフローチャートである。
【０１３９】
図２３において、ステップ２３０２ではまず、SIGN(l) =“L”かどうかが判断される。ここで、SIGN()という関数は、前に、ツリーＧsp-treeの対(ｆ,ｓ)としてあらわされるノードの集合において、ｓ∈{"L","S","P"}として説明した集合の要素を返す。ここの"L"は、葉(leaf)、"S"は直列(series)、"P"は並列(parallel)という種別をあらわす。
【０１４０】
ステップ２３０２でSIGN(l) ="L"であると判断されたなら、ステップ２３０４に進み、そこでTc = NULLとし、ステップ２３０６でTcを返して、処理を終わる。
【０１４１】
ステップ２３０２でSIGN(l) ="L"でないと判断されたなら、ステップ２３０８に進み、そこで、l = LEFT(n), r = RIGHT(n), Tl = get_table(l), Tr = get_table(r)という演算を行なう。このフローチャートはget_table()について処理なので、ここのget_table(l)とget_table(r)は、再帰呼び出しである。
【０１４２】
次にステップ２３１０に進んで、そこで、SIGN(l) ="S"かどうか判断する。そうでなければ、ステップ２３１２でTc = parallel_merge(Tl,Tr)として、ステップ２３０６でTcを返して、処理を終わる。parallel_merge()の詳細は、後で説明する。
【０１４３】
ステップ２３１０で、SIGN(n) ="S"であると判断されたなら、ステップ２３１４でel = EDGE(l), Tc = DEST(el)とし、ステップ２３１６でTl = NULLかどうか判断される。もしそうでないなら、ステップ２３１８で、Tc = series_merge(Tl,Tc)として、ステップ２３２０に進む。もしそうなら、直ちにステップ２３２０に進む。series_merge()の詳細は、後で説明する。
【０１４４】
次に、ステップ２３２０で、Tr = NULLかどうか判断され、もしそうでないなら、ステップ２３２２で、Tc = series_merge(Tc,Tr)として、ステップ２３０６に進む。もしそうなら、直ちにステップ２３０６に進む。こうして、Tcを返して、処理を終わる。
【０１４５】
次に、図２４のフローチャートを参照して、series_merge(Tl,Tr)の処理を説明する。まず、ステップ２４０２では、Tl == NULLまたはTr == NULLであるかどうかが判断される。もしそうなら、ステップ２４０４に進んで、Tl == NULLかどうかが判断され、もしそうでないなら、ステップ２４０６で、Tnew = Tlとして、ステップ２４０８でTnewを返して、処理を終わる。
【０１４６】
Tl == NULLであるなら、ステップ２４１０に進み、そこで、Tr == NULLであるかどうかが判断される。もしそうでないなら、ステップ２４１２で、Tnew = Trとして、ステップ２４０８でTnewを返して、処理を終わる。
【０１４７】
もしTr == NULLであるなら、ステップ２４１４に進み、Tnew = NULLとして、ステップ２４０８でTnewを返して、処理を終わる。
【０１４８】
ステップ２４０２で、Tl == NULLでもないしTr == NULLでもないと判断されたなら、ステップ２４１６に進んで、mに、利用可能なプロセッサの数がセットされ、Tnewに、新しい空の並列化テーブルがセットされる。
【０１４９】
ステップ２４１７では、iに1がセットされ、ステップ２４１８では、i <= mかどうか判断される。i <= mでなければ、処理は、ステップ２４０８に行って、Tnewを返して、処理を終わる。
【０１５０】
i <= mであるなら、ステップ２４２０で、j = 1とセットして、ステップ２４２２でj<=mかどうか判断し、そうでなければ、ステップ２４２４でiを1だけ増分して、ステップ２４１８に戻る。
【０１５１】
ステップ２４２２でj<=mであると判断されると、ステップ２４２６に進み、そこで、i+j<=mかどうかが判断される。もしそうなら、ステップ２４２８に進み、そこで、下記の処理が行なわれる。
lsl = LENGTH(Tl,i)
lsr = LENGTH(Tr,j)
ls = MAX(lsl,lsr)
Rl = CLUSTERS(Tl,i)
Rr = CLUSTERS(Tr,j)
Rnew = Rl ∪ Rr
【０１５２】
ステップ２４２８に続いて、ステップ２４３０では、ls < LENGTH(Tnew, i+j)かどうかが判断され、もしそうなら、ステップ２４３２で、(i+j,ls,Rnew)が、Tnewに記録される。そして処理は、ステップ２４３４に進む。ステップ２４３０で、ls < LENGTH(Tnew, i+j)でないと判断した場合は、処理は直ちにステップ２４３４に進む。
【０１５３】
ステップ２４３４では、i = jかどうかが判断され、もしそうなら、ステップ２４３６で、下記の処理が行なわれる。
Rl = CLUSTERS(Tl,i)
Rr = CLUSTERS(Tr,j)
(Rnew,ls) = merge_clusters_in_shared(Rl,Rr,i)
なお、merge_clusters_in_shared()の処理の詳細については、後で説明する。
【０１５４】
ステップ２４３６に続いて、ステップ２４３８では、ls < LENGTH(Tnew, i)かどうかが判断され、もしそうなら、ステップ２４４０で、(i,ls,Rnew)が、Tnewに記録される。そして処理は、ステップ２４４２に進む。ステップ２４３０で、ls < LENGTH(Tnew, i)でないと判断した場合は、処理は直ちにステップ２４４２に進む。
【０１５５】
ステップ２４３４で、i = jでないと判断された場合も、ステップ２４３４から直ちにステップ２４４２に進む。ステップ２４４２では、jを1だけ増分して、ステップ２４２２に戻る。
【０１５６】
次に、図２５のフローチャートを参照して、parallel_merge(Tl,Tr)の処理を説明する。まず、ステップ２５０２では、Tl == NULLまたはTr == NULLであるかどうかが判断される。もしそうなら、ステップ２５０４に進んで、Tl == NULLかどうかが判断され、もしそうでないなら、ステップ２５０６で、Tnew = Tlとして、ステップ２５０８でTnewを返して、処理を終わる。
【０１５７】
Tl == NULLであるなら、ステップ２５１０に進み、そこで、Tr == NULLであるかどうかが判断される。もしそうでないなら、ステップ２５１２で、Tnew = Trとして、ステップ２５０８でTnewを返して、処理を終わる。
【０１５８】
もしTr == NULLであるなら、ステップ２５１４に進み、Tnew = NULLとして、ステップ２５０８でTnewを返して、処理を終わる。
【０１５９】
ステップ２５０２で、Tl == NULLでもないしTr == NULLでもないと判断されたなら、ステップ２５１６に進んで、mに、利用可能なプロセッサの数がセットされ、Tnewに、新しい空の並列化テーブルがセットされる。
さらに、
T1 = series_merge(Tl,Tr)
T2 = series_merge(Tr,Tl)
とセットされる。series_mergeについては、図２４で説明済みである。
【０１６０】
ステップ２５１８では、iに1がセットされ、ステップ２５２０では、i <= mかどうか判断される。i <= mでなければ、処理は、ステップ２５０８に行って、Tnewを返して、処理を終わる。
【０１６１】
i <= mであるなら、ステップ２５２２に進んで、そこで、下記の式により、l1と、l2がセットされる。
l1 = LENGTH(T1,i)
l2 = LENGTH(T2,i)
【０１６２】
ステップ２５２４では、l1 < l2かどうか判断され、もしそうなら、ステップ２５２６で、
R = CLUSTERS(T1,i)とされ、(i,l1,R)がTnewに記録される。
【０１６３】
l1 < l2でないなら、ステップ２５２８で、R = CLUSTERS(T2,i)とされ、(i,l2,R)がTnewに記録される。
【０１６４】
次に、ステップ２５３０でiを1増分してから、ステップ２５２０に戻る。
【０１６５】
次に、図２６のフローチャートを参照して、merge_clusters_in_shared(Rl,Rr,i)の処理を説明する。
【０１６６】
先ず、ステップ２６０２では、Rl中のクラスタを、その終了時間で昇順にソートする。
また、Rr中のクラスタを、その終了時間で昇順にソートする。
次に、END(Rl[x]) - START(Rr[x]) が最大となるように、1からiの中から、インデックスxを選ぶ。
さらに、以下の計算を行なう。
w = MAX({ v = END(Rl[u])+gap[u]+WORKLOAD(Rr[u]) : 
gap[u] = END(Rl[x])-START(Rr[x])+START(Rr[u])-END(Rl[u]), u=1,…,i})
R := {Ru: Ru:=Rl[u]∪Rr[u], u = 1,…,i}
【０１６７】
ステップ２６０４では、(R,w)を返して、処理を終了する。
【０１６８】
次に、図２７のフローチャートを参照して、Tunifiedから最良の構成を選択する処理について説明する。Tunifiedは、図２１のステップ２１０６から得られたものである。この処理は、図５の並列化テーブル処理モジュール５１４が実行する。
【０１６９】
ステップ２７０２では、利用可能なプロセッサの数をmとセットする。また、i = 1とし、min = ∞とおく。∞は実際上、非常に大きい数である。
【０１７０】
ステップ２７０４では、i <= mかどうか判断され、もしそうなら、ステップ２７０６で、w = LENGTH(Tunified,i)が計算され、ステップ２７０８では、w < minかどうかが判断される。
【０１７１】
w < minでないなら、ステップ２７０４に戻る。w < minならステップ２１７０でmin = wとセットし、ステップ２７１２で、Rfinal = CLUSTERS(Tunified,i)を計算してステップ２７０４に戻る。
【０１７２】
ステップ２７０４で、i <= mでないと判断されると、処理は終了する。その時点のRfinalが、求める結果となる。図１４には、このようにして選ばれた構成の例が示されている。
【０１７３】
図５に戻って、コンパイラ５２０は、Rfinalに基づきクラスタ毎にコードをコンパイルして、実行環境５２２に引き渡す。実行環境５２２は、クラスタ毎にコンパイルされた実行可能コードを個別のプロセッサにアサインして、実行させる。
【０１７４】
以上、この発明を特定の実施例に基づき説明してきたが、この発明は、この特定の実施例に限定されず、当業者が自明に思いつく様々な変形、置換などの構成、技法適用可能であることを理解されたい。例えば、特定のプロセッサのアーキテクチャ、オペレーティング・システムなどに限定されない。
【０１７５】
また、上記実施例は、主として、自動車のＳＩＬＳのシミュレーション・システムにおける並列化に関連するものであったが、このような例には限定されず、航空機、ロボットその他の物理システムのシミュレーション・システムに広く適用可能であることを理解されたい。
【符号の説明】
【０１７６】
４０２  ホスト・バス
４０４ａ、４０４ｂ、４０４ｃ、４０４ｎ・・・  ＣＰＵ
４０６  メイン・メモリ
４０８  バス
４１０  キーボード
４１２  マウス
４１４  ディスプレイ
４１６  ハードティスク・ドライブ
４１８  ブリッジ
５０２  シミュレーション・モデリング・ツール
５０４  ソース・コード
５０６  解析モジュール
５０４  ソースコード
５０８  グラフ表現
５１０  クラスタリング・モジュール
５１２  変形モジュール
５１４  並列化テーブル処理モジュール
５１６  並列化テーブル
５１８  コード生成モジュール
５２０  コンパイラ
５２２  実行環境
８０２  エッジ
９０２  クラスタ
１１０２  並列化テーブル
１１１０  並列化テーブル
１２０２  並列化テーブルのグラフ
【図１】
2011081539.tif 000003
【図２】
2011081539.tif 000004
【図３】
2011081539.tif 000005
【図４】
2011081539.tif 000006
【図５】
2011081539.tif 000007
【図６】
2011081539.tif 000008
【図７】
2011081539.tif 000009
【図８】
2011081539.tif 000010
【図９】
2011081539.tif 000011
【図１０】
2011081539.tif 000012
【図１１】
2011081539.tif 000013
【図１２】
2011081539.tif 000014
【図１３】
2011081539.tif 000015
【図１４】
2011081539.tif 000016
【図１５】
2011081539.tif 000017
【図１６】
2011081539.tif 000018
【図１７】
2011081539.tif 000019
【図１８】
2011081539.tif 000020
【図１９】
2011081539.tif 000021
【図２０】
2011081539.tif 000022
【図２１】
2011081539.tif 000023
【図２２】
2011081539.tif 000024
【図２３】
2011081539.tif 000025
【図２４】
2011081539.tif 000026
【図２５】
2011081539.tif 000027
【図２６】
2011081539.tif 000028
【図２７】
2011081539.tif 000029