並列化方法、システム、及びプログラム
【課題】コード化対象外ブロックを含むブロック線図について、コード化後の実行速度を最適化するようにコード化対象外ブロックを配置変更して、領域分割する技法を提供する。
【解決手段】ブロック線図を、DAGのタスク・グラフに変換・抽象化する。タスク・グラフの構造を解析した後、直列−並列木(SPT)を得る。SPTは、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含み、コード化対象外ブロックの上位にPノードが存在しなくなるまで、別のSPTに変形される。結果のSPTのPノードの下に連なるブロックを並列に実行するように、対応する元のブロック線図を分割して、それぞれの領域に対してコードを生成しコンパイルして、異なるプロセッサまたはコアに割り当てて、並列実行される。DAGのタスク・グラフは、点在するコード化対象外ブロックをなるべくマージさせるように変形される。
【解決手段】ブロック線図を、DAGのタスク・グラフに変換・抽象化する。タスク・グラフの構造を解析した後、直列−並列木(SPT)を得る。SPTは、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含み、コード化対象外ブロックの上位にPノードが存在しなくなるまで、別のSPTに変形される。結果のSPTのPノードの下に連なるブロックを並列に実行するように、対応する元のブロック線図を分割して、それぞれの領域に対してコードを生成しコンパイルして、異なるプロセッサまたはコアに割り当てて、並列実行される。DAGのタスク・グラフは、点在するコード化対象外ブロックをなるべくマージさせるように変形される。
【発明の詳細な説明】
【技術分野】
【0001】
この発明は、シミュレーション・システムにおいて、並列化によりプログラムの実行を高速化する技法に関する。
【背景技術】
【0002】
近年、科学技術計算、シミュレーションなどの分野で、複数のプロセッサをもつ、いわゆるマルチプロセッサ・システムが使用されている。一方、最近になって特に盛んに開発されるようになってきたシミュレーションの分野として、ロボット、自動車、飛行機などのメトカトロニクスのプラントのシミュレーション用ソフトウェアがある。電子部品とソフトウェア技術の発展の恩恵により、ロボット、自動車、飛行機などでは、神経のように張り巡らされたワイヤ結線や無線LANなどを利用して、大部分の制御が電子的に行われる。
【0003】
それらは、本来的にはメカトロニクスの装置であるが、大量の制御ソフトウェアをも内蔵している。そのため、製品の開発に当たっては、制御プログラムの開発とそのテストに、長い時間と、膨大な費用と、多数の人員を費やす必要が出てきた。
【0004】
このようなテストにために従来行われている技法として、HILS(Hardware In the Loop Simulation)がある。特に、自動車全体の電子制御ユニット(ECU)をテストする環境は、フルビークルHILSと呼ばれる。フルビークルHILSにおいては、実験室内で、本物のECUが、エンジン、トランスミッション機構などをエミュレーションする専用のハードウェア装置に接続され、所定のシナリオに従って、テストが行われる。ECUからの出力は、監視用のコンピュータに入力され、さらにはディスプレイに表示されて、テスト担当者がディスプレイを眺めながら、異常動作がないかどうか、チェックする。
【0005】
しかし、HILSは、専用のハードウェア装置を使い、それと本物のECUの間を物理的に配線しなくてはならないので、準備が大変である。また、別のECUに取り替えてのテストも、物理的に接続し直さなくてはならないので、手間がかかる。さらに、本物のECUを用いたテストであるため、テストに実時間を要する。従って、多くのシナリオをテストすると、膨大な時間がかかる。また、HILSのエミュレーション用のハードウェア装置は、一般に、非常に高価である。
【0006】
そこで近年、高価なエミュレーション用ハードウェア装置を使うことなく、シミュレーション全体をソフトウェアで構成する手法が提案されている。その手法においては、エンジンやトランスミッションなどのプラント部分には連続系シミュレーション(continuous simulation)を利用し、また、コントローラ部分にはステート・チャート(state chart)あるいは実際のソフトウエアコードを利用する。コントローラ部分のシミュレーション方法に応じて、前者は MIL (Model-in-the-Loop) シミュレーション、後者は SIL (Software-in-the-Loop) シミュレーションと呼ばれる。MILやSILによればECUのハードウェアが存在しなくても、テストを実行可能である。
【0007】
このようなMIL/SILの構築を支援するシステムとして例えば、MathWorks社から入手可能なシミュレーション・モデリング・システムである、MATLAB(R)/Simulink(R)がある。MATLAB(R)/Simulink(R)を使用すると、画面上にグラフィカル・インターフェースによって、機能ブロックを配置し、その処理の流れを指定することによって、シミュレーション・プログラムを作成することができる。ここで、機能ブロックは、和や積などの基本演算や積分や条件分岐、さらには、ソフトウエア・コードを呼び出すブロックなどの種類があり、それぞれが入力あるいは・および出力を持つ。なお、コントローラの表現としてソフトウエア・ブロックを含むシミュレーションがSILである。
【0008】
こうして、MATLAB(R)/Simulink(R)上で、いったん機能ブロックを構成配置してブロック線図を作成すると、次に、Real-Time Workshop(R)の機能を利用して、シミュレーションの実行をさらに高速化することができる。すなわち、ソフトウエア・コード以外のブロックを、等価な機能のC言語など既知のコンピュータ言語のソース・コードに変換することにより、逐次解釈的な処理から、ホストに最適化された処理に置き換える。なお、Real-Time WOrkshop(R) の場合、コード変換を実施する単位は、モデルの全体あるいは、図1に参照番号102、104などで示すようなサブブロックの単位である。ここで、サブブロックは、モデルの可読性のために導入される階層的な構造を表現するための特別な境界を表す。例えば、サブブロック108は、参照番号108aで示すような内部的な構造をもつ。
【0009】
ところが、自動車や航空機などの制御システムは複雑なので、数千個〜数十万個の機能ブロックを含むことが普通である。従って、シミュレーション・モデルを設計して、所望のモデルを得るためには、何度も設計・コンパイル・実行を繰り返す必要がある。
【0010】
図1において、例えば、オペレータが、サブブロック102〜110などのうち、サブブロック110を編集してコンパイルして実行可能バイナリ・コードを得る。そして、その実行可能バイナリ・コードをコンピュータ・システム上で実行しで動作を確認し、所望の動作が得られないならば、再度サブブロック110を編集し、コンパイル&実行するということを繰り返す。
【0011】
機能ブロックの数が増えるにつれて、結果のソースコードが増大するが、すると、ソースコード全体をフル・コンパイルする際のコンパイル時間も長くなる。
【0012】
一般に大規模なモデルを編集するときは、編集の対象となるサブブロックは、例えば図1のサブブロック110のように、一部に限定されることが多い。特に、複合的なモデルの場合には、設計者が担当する部分を除いた他のサブブロックは、変更せずに固定化してブラックボックスのように扱われることが多い。そこで、編集の対象となるサブブロックを残して、それ以外をあらかじめコード変換しておくことで、実行速度と編集作業の両立を図ることができる。また、マルチ・プロセッサ、あるいは、マルチ・コアの環境で、分割コンパイルした個別の実行コードを、異なるプロセッサまたはコアに割り当てて並列実行させることにより、実行時間が短縮される。特に後者について、関連技術として次の特許公開公報に記述されている技法がある。
【0013】
特開平7−114486号公報は、デバッグ用の出力文を含む逐次ループを、並列化する方法に関し、逐次ループ内のI/O文を検出し、I/O文がループ不変式による条件節に含まれること検出して、I/O文を含む依存を解析し、実行順序を守るための同期文を挿入し、並列処理用のループに変換することを開示する。
【0014】
特開2011−96107号公報は、ブロック線図などで表されるプログラムにおいて、内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックとの接続関係に基づき、機能ブロック毎に、使用ブロック集合/定義ブロック集合の数を求め、その数に基づき、複数のストランドを割り当て、これにより、ブロック線図を、ストランドに分けて処理を並列化することを開示する。
【0015】
図2は、サブブロックにアラインした単純分割の例を示す。すなわち、図2では、領域202、204、206などに分割されている。しかしながら、MATLAB(R)/Simulink(R) のように、タイムステップに基づくシミュレーションの場合には、必ずしもサブブロックの単位でまとめてコード変換ができるとは限らない。たとえば、ブロックの実行順序をスケジュールするにはサブブロックの中(下位の階層)まで解析する必要があり、その結果、サブブロックの中ほど(途中)から計算を開始することが決定した場合には、実質的にサブブロックは前後に分断されなければならない。また、例えば、MATLAB(R)/Simulink(R)のScopeブロックのような結果を表示するブロックはコード変換することができず、したがって、そのようなコード化することができない機能ブロックを含むサブブロックは、その単位のままではコード化できない。以上のような制約を考慮して試みられた分割の例を図3に示す。すなわち、図3に示すように、分割は、コード化対象外ブロック314、316を除外し、スケジュールに合わせた実行開始コード310、312が先頭にくるように分割・再構成によりコード変換を適用することが、シミュレーションの高速化のためには望ましい。
【0016】
しかしながら、そのような分割および再構成の手法は自明ではなく、特に、並列化のための分割手順は組合せ問題となり、最適な組合せを短時間で計算することは一般に非常に困難である。そこで、限られた時間の中で準最適な解を求めることが強く求められる。
【先行技術文献】
【特許文献】
【0017】
【特許文献1】特開平7−114486号公報
【特許文献2】特開2011−96107号公報
【発明の概要】
【発明が解決しようとする課題】
【0018】
この発明の目的は、基本処理の流れを表すブロック線図について、その実行速度を最適化するように分割することである。
この発明の他の目的は、その際に、実行速度を損なわないように、コード化対象外ブロックを分割の境界に配置するための技法を提供することにある。
【課題を解決するための手段】
【0019】
この発明は、上記課題を解決するためになされたものであり、この発明に従うシステムは先ず、ブロック線図を、DAG(directed acyclic graph)のタスク・グラフに変換する。
【0020】
次に、この発明に従うシステムは、上記タスク・グラフを、既知のアルゴリズムに従い一旦直列−並列グラフ(SPG: series-parallel graph)に変換してから、構造(構文)解析を行い、一意の直列−並列木(SPT: series-parallel parse tree)を得る。SPTは、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む。また、末端のノードは、タスク・グラフのノードを表す。
【0021】
次に、この発明に従うシステムは、上記SPTを、コード化対象外ブロックの上位にPノードが存在しなくなるまで、別のSPTに変形する。
【0022】
こうして最適なSPTが得られると、発明に従うシステムは、結果のSPTのPノードの下に連なるブロックを並列に実行するように、コードを生成しコンパイルして、異なるプロセッサまたはコアに割り当てて、並列実行させる。
【0023】
なお、あるDAGのタスク・グラフに対して一般的に、ノード実行順序の前後関係に矛盾しないSPTは複数存在する。そこで、本発明の好適な一側面によれば、SPTに変換する前に、DAGのタスク・グラフは、点在するコード化対象外ブロックをなるべくマージさせるように変形される。これによって、結果のタスク・グラフの分割数の低減がはかられる。一般に、各分割のサイズが同程度であれば、全体におけるクリティカル・パスが小さくなって並列処理での高速化の効果が大きくなる。また、逐次処理であっても、分割数が小さければ、呼び出しのオーバヘッドが減少するために、実行の高速化に大いに貢献する。
【発明の効果】
【0024】
この発明によれば、ブロック線図であらわされるプログラム・コードにおいて、コード化対象外ブロックの存在を考慮して、コードの分割数を減らし、並列実行コストのバランスのとれた分割を与える技法が提供される。
【図面の簡単な説明】
【0025】
【図1】タスク・グラフのコンパイルと実行を説明するための図である。
【図2】サブブロックにアラインした単純分割を示す図である。
【図3】コード化対象外ブロックと実行スケジュールに合わせた最大分割を示す図である。
【図4】本発明を実施するためのハードウェアのブロック図である。
【図5】本発明を実施するための機能ブロック図である。
【図6】本発明の処理全体の概要フローチャートを示す図である。
【図7】タスク・グラフ変形処理のフローチャートを示す図である。
【図8】タスク・グラフ変形処理におけるリスト・スケジューリングの例を示す図である。
【図9】タスク・グラフをSPTに変換する処理のフローチャートを示す図である。
【図10】タスク・グラフをSPTに変換する処理の例を示す図である。
【図11】タスク・グラフをSPTに変換する処理の例を示す図である。
【図12】SPT変形処理のフローチャートを示す図である。
【図13】SPT変形処理の例を示す図である。
【図14】SPT変形処理の例を示す図である。
【図15】SPT変形処理における主要な処理を説明するための図である。
【図16】SPT変形処理における主要な処理を説明するための図である。
【図17】個別のプロセッサまたはコアに割り当てるコードを生成するための処理のフローチャートを示す図である。
【発明を実施するための形態】
【0026】
以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。
【0027】
先ず、図4を参照して、本発明を実施するために使用されるコンピュータのハードウェアについて説明する。図4において、ホスト・バス402には、複数のCPU1 404a、CPU2 404b、CPU3 404c、・・・CPUn 404nが接続されている。ホスト・バス402にはさらに、CPU1 404a、CPU2 404b、CPU3 404c、・・・CPUn 404nの演算処理のためのメイン・メモリ406が接続されている。
【0028】
一方、I/Oバス408には、キーボード410、マウス412、ディスプレイ414及びハードティスク・ドライブ416が接続されている。I/Oバス408は、I/Oブリッジ418を介して、ホスト・バス402に接続されている。キーボード410及びマウス412は、オペレータが、コマンドを打ち込んだり、メニューをクリックするなどして、操作するために使用される。ディスプレイ414は、必要に応じて、本発明に係るプログラムをGUIで操作するためのメニューを表示するために使用される。
【0029】
この目的のために使用される好適なコンピュータ・システムのハードウェアとして、IBM(R)System Xがある。その際、CPU1 404a、CPU2 404b、CPU3 404c、・・・CPUn 404nは、例えば、インテル(R)Xeon(R)であり、オペレーティング・システムは、Windows(商標)Server 2003である。オペレーティング・システムは、ハードティスク・ドライブ416に格納され、コンピュータ・システムの起動時に、ハードティスク・ドライブ416からメイン・メモリ406に読み込まれる。
【0030】
本発明を実施するためには、マルチプロセッサ・システムを用いることが必要である。ここでマルチプロセッサ・システムとは、一般に、独立に演算処理し得るプロセッサ機能のコアを複数もつプロセッサを用いるシステムを意図しており、従って、マルチコア・シングルプロセッサ・システム、シングルコア・マルチプロセッサ・システム、及びマルチコア・マルチプロセッサ・システムのどれでもよいことを理解されたい。
【0031】
なお、本発明を実施するために使用可能なコンピュータ・システムのハードウェアは、IBM(R)System Xに限定されず、本発明のシミュレーション・プログラムを走らせることができるものであれば、任意のコンピュータ・システムを使用することができる。オペレーティング・システムも、Windows(R)XP、Windows(R)7、Linux(R)、Mac OS(R)など、任意のオペレーティング・システムを使用することができる。さらに、シミュレーション・プログラムを高速で動作させるために、POWER(商標)6ベースで、オペレーティング・システムがAIX(商標)のIBM(R)System Pなどのコンピュータ・システムを使用してもよい。
【0032】
ハードティスク・ドライブ416にはさらに、MATLAB(R)/Simulink(R)、Cコンパイラまたは、C++コンパイラ、後述する、タスクグラフ生成、タスクグラフ変形直接−並列木(SPT)変換、SPT変形などのためのモジュール、CPU割り当て用コード生成モジュールなどが格納されており、オペレータのキーボードやマウス操作に応答して、メイン・メモリ406にロードされて実行される。タスクグラフ生成、タスクグラフ変形直接−並列木(SPT)変換、SPT変形などのためのモジュールは、Java(R)、C、C++、C#などの既存の任意のプログラミング言語で作成することができる。
【0033】
尚、使用可能なシミュレーション・モデリング・ツールは、MATLAB(R)/Simulink(R)に
限定されず、オープンソースのScilab/Scicosなど、タイム・ステップに基づくタスク・グラフで表現される任意のシミュレーション・モデリング・ツールを使用することが可能である。
【0034】
あるいは、場合によっては、シミュレーション・モデリング・ツールを使わず、直接、C、C++などでシミュレーション・システムのソース・コードを書くことも可能であり、その場合にも、個々の機能が、互いに依存関係にある個別の機能ブロックとして記述できるなら、本発明は適用可能である。
【0035】
図5は、本発明の実施例に係る機能ブロック図である。各々のブロックは、基本的に、ハードティスク・ドライブ416に格納されているモジュールに対応する。
【0036】
図5において、シミュレーション・モデリング・ツール502は、好適には、MATLAB(R)/Simulink(R)であり、それ以外に、Scilab/Scicosなど、コード化対象外ブロックを含み得る、任意のシミュレーション・モデリング・ツールを使用することができる。
【0037】
モデル・データ504は、シミュレーション・モデリング・ツール502を用いて作成され、好適にはブロック線図で記述され、ハードディスク・ドライブ416に保存されている。そのブロック線図に含まれるブロックにおいて、コード化対象外ブロックは、予めマークされている。
【0038】
メイン・ルーチン506は、本発明に係る処理の各種モジュールを呼び出し、実行するためのプログラムであり、好適には、ディスプレイ414上で、キーボード410やマウス412で操作して処理を行うためのGUIなどのインターフェースを与える。
【0039】
DAG変換モジュール508は、モデル・データ504を読み込んで、DAGのタスク・グラフに変換する機能をもつ。好適には、変換されたタスク・グラフのデータは、メイン・メモリ406上に必要な領域を確保して展開される。なお、コンピュータ・メモリ上にグラフを表現するデータ構造として、行列表現あるいはリスト表現などが知られているが、この実施例で、既知の任意のデータ構造を使用することができる。
【0040】
タスク・グラフ変形モジュール510は、DAG変換モジュール508によって変換して得られたタスク・グラフに含まれるコード化対象外ブロックを可能な範囲でマージする機能をもつ。変形された結果のタスク・グラフは、好適には、メイン・メモリ406上に必要な領域を確保して展開される。この処理は後で、図7のフローチャートを参照して、より詳細に説明する。
【0041】
SPT変換モジュール512は、タスク・グラフ変形モジュール510によって変形して得られたタスク・グラフを、直接−並列木(SPT)に変換する機能をもつ。SPTは、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む。変換された結果のタスク・グラフは、好適には、メイン・メモリ406上に必要な領域を確保して展開される。この処理は後で、図9のフローチャートを参照して、より詳細に説明する。
【0042】
SPT変形モジュール514は、SPT変換モジュール512によって得られたSPTのグラフを、別の直接−並列木(SPT)に変形する機能をもつ。変形は、コード化対象外ブロックの上位にPノードが存在しなくなるまで行われる。変形された結果のタスク・グラフは、好適には、メイン・メモリ406上に必要な領域を確保して展開される。この処理は後で、図12のフローチャートを参照して、より詳細に説明する。
【0043】
CPU割当てモジュール516は、SPT変形モジュール514の変形の結果得られたSPTに基づき、個別のプロセッサあるいはコアに割り当てるためのコードを抽出する。抽出されたコードは、好適には、ハードティスク・ドライブ416に書き出される。このコードは、機能ブロックに対応する、好適にはCまたはC++のソースコードである。CPU割当てモジュール516の処理は後で、図17のフローチャートを参照して、より詳細に説明する。
【0044】
コンパイラ518は、CPU割当てモジュール516によって書き出されたコードをコンパイルして、実行可能コードを生成する。実行環境520は、個別のプロセッサあるいはコアに割り当てて並列実行させる。実行環境520は、好適には、CPU割当てモジュール516が生成した補助的な情報を参照して実行可能コードを割り当てる。
【0045】
実行環境520の一部として、MATLAB(R)/Simulink(R)を利用する場合には、それが未コンパイルの(サブ)ブロックとコンパイル済みのサブブロックを区別して、前者はインタプリターとして実行し、後者はバイナリーコードとしてホスト実行する。
【0046】
図6は、本発明の処理の全体の流れを示す概要フローチャートである。この後の詳細な説明は、この流れに沿って説明することになる。
【0047】
ステップ602では、DAG変換モジュール508により、モデル・データがDAGのタスク・グラフに変換される。
【0048】
ステップ604では、タスク・グラフ変形モジュール510により、コード化対象外ブロックを可能な範囲でマージするように、タスク・グラフが変形される。
【0049】
ステップ606では、SPT変換モジュール512により、タスク・グラフがSPTに変換される。
【0050】
ステップ608では、SPT変形モジュール514により、SPTが、コード化対象外ブロックの上位にPノードが存在しなくなるように、別のSPTに変換される。
【0051】
ステップ610では、SPT変形モジュール514により生成されたSPTに基づき、CPU割当てモジュール516により、各CPUに割り当てるためのコードが生成される。
【0052】
ステップ612では、コンパイラ518により、生成されたコードがコンパイルされ、ステップ614では、コンパイルされたコードが実行される。
【0053】
以下、各ステップについて詳細に説明するが、その前に、DAG およびSPT上のノードに関する用語について定義を与えておく。
xノード : コード化対象外ノード
非xノード :コード化対象ノード
SPT上のノードに関する用語
ノードの順序 : 木の(Tree)左優先の深さ優先探索(Depth first search)で辿られる順番で決定する。SPT中のある二つのノードに対して、辿られる順番が他方より早いものを前、他方より遅い方を後ろとする。
根ノード : 一般的な定義に順ずる。
葉ノード : 子ノードを持たないノード。DAG上のノードに対応する。(一般的な定義と同じ)
内部ノード : 葉ノードでないノード (一般的な定義と同じ)
親ノード : 一般的な定義に順ずる
子ノード : 一般的な定義に順ずる
兄ノード : 親ノードが同じノードのうち、対象ノードより前にあるノード
弟ノード : 親ノードが同じノードのうち、対象ノードより後ろにあるノード
兄弟ノード : 兄ノードおよび弟ノード
祖父ノード : 親ノードの親ノード
曽祖父ノード : 祖父ノードの親ノード
Sノード : 子ノードの直列実行を表す内部ノード
Pノード : 子ノードの並列実行を表す内部ノード
【0054】
また、SPTの構成に関する補足について述べると、SPT上では、Sノード同士またはPノード同士が親子関係になることはないものとする。仮に同種の内部ノードが親子関係になった場合には、当該子ノードを切り離し、当該子ノードの子ノードを順序を維持したまま親ノードに移動させる(このとき移動されるノード以下のノードも引き連れて移動するものとする)処理を自動的に適用するものとする。上記処理は、木によって表現される直列・並列実行の意味合いを変化させない。
【0055】
以上の定義と補足に基づき、図6の各ステップを順に説明していく。先ず、モデル・データをDAGのタスク・グラフに変換するステップ602であるが、DAG変換モジュール508は、モデル・データ504を読み込んで、DAGのタスク・グラフに変換する。このとき、図3にあるような、スケジュールの先頭になるブロックを解釈して、自己ループのないDAG構造へと変換する。好適には、変換されたタスク・グラフのデータは、メイン・メモリ406上に必要な領域を確保して展開される。DAG変換モジュール508は、ブロック線図として記述されたモデル・データ504において、入力のない機能ブロックや実行のスケジュール上先頭に来る機能ブロックを全体のソースとして、またノード間の接続を有向エッジとしてDAG(無閉路有向グラフ)を構成する。全体のシンクとなるのは、出力のない機能ブロックや実行上、最後にスケジュールされる機能ブロックなどである。
【0056】
タスク・グラフ変形モジュール510が、コード化対象外ブロックを可能な範囲でマージするように、タスク・グラフを変形するステップ604は、タスク・グラフに対して以下の性質を持つリストスケジューリングを行い、スケジュール上で隣接するコード化対象外ノード(X)をひとつにマージする処理を行う。
【0057】
このとき、直前にスケジュールされたノードがxであれば可能な限りxをスケジュールし、直前にスケジュールされたノードがxでなければ可能な限りxでないノードをスケジュールする。
【0058】
ここでの目的は、タスクノードの前後関係に矛盾しない範囲でなるべくxをひとつの塊にすることである。これにより、次のステップで抽出されるSPT上で x が分散配置されて最終的なコードの分割数を増やしたり、最終的に利用(exploit)できないxとの並列性の抽出により本来利用できる並列性が抽出されない事態を極力回避する。
【0059】
図7は、図6のステップ604に対応する、タスク・グラフ変形モジュール510の処理のフローチャートを示す図である。この処理は、xノード、非xノードをもつDAGを入力とし、直列スケジュールSを出力する。直列スケジュールSは、タスク・グラフにおいて、マージされた単一のノードとして扱われる。
【0060】
さて、図7のステップ702において、タスク・グラフ変形モジュール510は、空のリストとしてS、DAGの全ノード(未スケジュールノード集合)としてCを用意する。
【0061】
ステップ704でタスク・グラフ変形モジュール510は、親をC中に持たないC中の非xノードの集合としてRoを、親をC中に持たないC中のxノードの集合としてRxを、それぞれ用意する。
【0062】
ステップ706でタスク・グラフ変形モジュール510は、Ro = φ ∧ Rx = φすなわち、Roが空集合且つRxが空集合かどうか判断する。
【0063】
そうでないなら、タスク・グラフ変形モジュール510は、ステップ708で、直前にSに加えられたノードがxノードかどうか判断し、そうならステップ710で、Rx = φかどうか判断する。
【0064】
ステップ710でRx = φでないと判断すると、タスク・グラフ変形モジュール510は、ステップ712で、Rxから1つノードを取り出し、そのノードはRxから削除し、そのノードをSの最後に加える。更にそのノードをCから削除する。そして、ステップ704に戻る。
【0065】
ステップ710に戻って、Rx = φであると判断すると、タスク・グラフ変形モジュール510は、ステップ714に進み、Ro = φかどうか判断する。
【0066】
ステップ714でRo = φでないと判断すると、タスク・グラフ変形モジュール510は、ステップ716で、Roから1つノードを取り出し、そのノードはRoから削除し、そのノードをSの最後に加える。更にそのノードをCから削除する。そして、ステップ704に戻る。
【0067】
ステップ708に戻って、直前にSに加えられたノードがxノードでないなら、ステップ714に進み、タスク・グラフ変形モジュール510はRo = φかどうか判断し、もしそうなら、ステップ710に進む。ステップ710での処理は、上述のとおりである。ステップ714でRx = φでないと判断された場合の処理も上述のとおりである。
【0068】
こうして、ステップ704を経由してステップ706に戻った時点で、Roが空集合且つRxが空集合であると判断すると、タスク・グラフ変形モジュール510は、ステップ718で、S中で隣接するxノードを1つの集合とし、その集合毎に含まれるxノードをDAG上で1つのノードにマージする処理を行い、処理を終わる。
【0069】
図8は、図7の処理の様子を模式的に示す図である。すなわち、図8(a)に示すようなタスク・グラフが与えられると、図7のフローチャートに示すステップ702〜716の処理で、図8(b)に示すリスト・スケジューリングが行われる。そこで、ステップ718の処理で、隣接するxノードを1つの集合とし、その集合毎に含まれるxノードをDAG上で1つのノードにマージすることで、図8(c)に示す変更されたタスク・グラフが得られる。
【0070】
図9は、SPT変換モジュール512の処理のフローチャートを示す図である。この処理は、図6のステップ606に対応する。この処理は、DAGを入力とし、SPTを出力する。
【0071】
ステップ902で、SPT変換モジュール512は、DAGを直列−並列グラフに変換して、それをSPGとおく。DAGを直列−並列グラフに変換する処理として、例えば、A. Gonzalez Escribano, V. Cardenoso and A.J.C. van Gemund, “Conversion from NSP to SP graphs”, Tech. Rep. TR-DINFO-01-97, Universidad de Valladolid, Valladolid (Spain), 1997などに記述されている技法を使用することができる。また、ステップ902では、SPGの構造を解析して、SPT(series-parallel parsed tree)を得る。
ここで、SPT上の葉ノードはSPGのノードに対応する。また、非端末(非葉)ノードはSPG上には存在しないが、間接的にノード間の接続順序を表す。
【0072】
次にステップ904で、SPT変換モジュール512は、SPG上のノード数が1以下かどうか判断し、そうでないなら、ステップ906に進む。
【0073】
ステップ906でSPT変換モジュール512は、以下の処理を行う。すなわち、SPG上で直列に接続しているノードのパスを見つける。ここで、直列に接続しているノードのパスとは、親を複数持つ、または親を持たないノードから、子を複数持つ、または子を持たないノードまでの、親と子を1つずつ持つノードによって構成されるパスを指す。
【0074】
そして、SPT変換モジュール512は、各々のパスLに対して、以下の処理を行う。
SPG上のLに属するすべてのノードを一つのノードSに置き換える(このとき、Lの外部のノードとの接続関係は維持される)。
同時に、SをSPT上の一つのノードとし、L中のノードに該当するSPT上のノードをL中での順序順にSPT上のSの子ノードとして加える。ここで、SPG上に構成されていくノードは、対応するノードがSPT上にも構築されていくため、つねに互いに対応関係が取れる。
【0075】
次に、SPT変換モジュール512は、ステップ908で、SPG上で並列関係にあるノードの集合を見つける。ここで、並列関係にあるノードの集合とは、親および子ノードが一致(存在しない場合を含む)しているノードの集合を指す。
【0076】
また、SPT変換モジュール512は、各々の集合Cに対して、以下の処理を行う。
SPG上のCに属するすべてのノードを一つのノードPに置き換える(このとき、Pの外部のノードとの接続関係は維持される)。
同時に、PをSPT上の一つのノードとし、C中のノードに該当するSPT上のノードを、SPT上のPの子ノードとして加える。ここでも、SPG上に構成されていくノードは、対応するノードがSPT上にも構築されていくため、つねに互いに対応関係が取れることに留意されたい。
【0077】
ステップ908の後は、SPT変換モジュール512は、ステップ904に戻り、SPT変換モジュール512は、SPG上のノード数が1以下かどうか判断し、もしそうなら、処理を終わる。
【0078】
図10は、図9に示すフローチャートの処理に従い、DAGをSPTに変換する例を示す図である。すなわち、図10(a)のDAGが、図10(b)のSPTに変換される。その際、SPTでは、子ノードの直列実行を表す内部ノードであるSノードと、子ノードの並列実行を表す内部ノードであるPノードが生成されていることが見て取れる。
【0079】
参考までに、図11は、タスク・グラフ変形モジュール510の変形を経ていないDAGをSPTに変換する例を示す図である。図11(b)に示すSPTは、図10(b)のSPTに比較して、xノードが葉ノードとして散在していることが見て取れる。
【0080】
図12は、SPT変形モジュール514の処理のフローチャートを示す図である。この処理は、図6のステップ608に対応する。この処理は、SPTを入力とし、SPTを出力する。
【0081】
ステップ1202で、SPT変形モジュール514は、SPTの根ノードがPノードである場合、新たな根ノードとしてSノードを設け、元の根であったPノードを当該Sノードの子ノードとする。また、上位にPノードを持つSPT上のすべてのxノードの集合をXとする。
【0082】
ステップ1204で、SPT変形モジュール514は、Xが空集合かどうか判断する。もし空集合なら、処理を終わる。
【0083】
もしXが空集合でないなら、ステップ1206に進み、SPT変形モジュール514は、Xから1つの要素xを取り出す(xはXから削除)。
【0084】
ステップ1208で、SPT変形モジュール514は、xの親がSかどうか判断する。そうでなければ、SPT変形モジュール514はステップ1210で、xを祖父ノードとして、親ノードの直前に移動する。このとき、SPT上のノードを移動する場合、その子ノード以下もすべて引き連れて移動することとする。
【0085】
ステップ1212で、SPT変形モジュール514は、xの祖先にPノードが存在するかどうか判断する。もしそうなら、処理はステップ1208に戻り、そうでなければ処理はステップ1204に戻る。
【0086】
ステップ1208に戻って、xの親がSであると判断すると、処理はステップ1214に進み、そこで、SPT変形モジュール514は、xの兄ノードの重みの和 < xの弟ノードの重みの和であるかどうか判断する。ここで、SPT上のノードの重みとは、そのノード以下の葉ノードの重みの和である。葉ノードは元のDAG上のノードであり、DAG上のノードはシミュレーション・モデル中の特定の処理と対応づいている。その処理の計算時間をDAG上のノードの重みとする。
【0087】
もしxの兄ノードの重みの和 < xの弟ノードの重みの和であると判断すると、SPT変形モジュール514は、ステップ1216で、xの兄ノードおよびxを、順序を維持したままxの曽祖父ノードの子として、xの祖父ノードの直前に移動し、ステップ1212に戻る。xの兄ノードの重みの和 < xの弟ノードの重みの和ではないと判断すると、SPT変形モジュール514は、ステップ1218で、xおよびxの弟ノードを、順序を維持したままxの曽祖父ノードの子として、xの祖父ノードの直後に移動し、ステップ1212に戻る。
【0088】
ステップ1212からは、そこでの判断に応じて、処理はステップ1208またはステップ1204に戻る。
【0089】
図13は、図12に示すフローチャートの処理に従い、SPTを変形する例を示す図である。すなわち、図13(b)では、変形後のSPTでは最早、コード化対象外ブロックxの上位にPノードが存在しないことが見て取れる。
【0090】
参考までに、図14は、タスク・グラフ変形モジュール510の変形を経ていないDAGから変換されたSPT(図14(a))を、図12に示すフローチャートの処理に従い、変形した例を示す図である。図14(b)ではやはり、変形後のSPTでは最早、コード化対象外ブロックxの上位にPノードが存在しているが、コード化対象外ブロックxが、トップのSノードの下に分散していることが見て取れる。
【0091】
図15及び図16は、SPTの変形の途中の様子を示すである。先ず、図15(a)に示すように、コード化対象外ブロックのノードxが、Pの直下にあるなら、変形処理は、図15(b)または図15(c)に示すように、ノードxを、祖父ノードSの子ノードとして、親ノードPの前または後ろに移動することである。すなわち、図15(b)がノードxを親ノードPの後ろに移動することに対応し、図15(c)がノードxを親ノードPの前に移動することに対応する。このようにしても、依存性の違反にはならない。
【0092】
すると、図16のような状態に移行する。これは、図16(a)に示すように、ノードxが、Sの直下にある場合である。この場合の変形処理は、図16(b)または図16(c)に示すように、ノードxと、その同一の親Sの下にある先行ノードまたは後続ノードを、曽祖父ノードSの子として、祖父ノードPの前または後ろに移動することである。図16(b)が後続ノードを祖父ノードPの後に移動することに対応し、図16(c)が先行ノードを祖父ノードPの前に移動することに対応する。このようにしても、依存性の違反にはならない。この際、移動の方向によってPの下から移動するノードのワークロードが異なるため、小さい方を選択して移動させる。
【0093】
図17は、CPU割当てモジュール516が、変形された結果のSPTに基づき、複数のCPUに個別に割り当てるコードに対応するSPTを生成する処理のフローチャートを示す図である。この処理は、図6のステップ610に対応する。この処理は、SPTを入力とし、SPTを出力する。以下で、maxは、利用可能なプロセッサまたはコアの数である。
【0094】
ステップ1702で、CPU割当てモジュール516は、SPTの根ノードの子ノードのうち、Pノードの集合としてTを用意する。
【0095】
ステップ1704で、CPU割当てモジュール516は、Tが空集合かどうか判断し、もしそうなら処理を終了する。そうでなければ、ステップ1706に進み、Tから一つのPノードqを取り出す。qはTから削除する。また、Yを、qおよび、qの下位にあるすべてのPノードの集合とする。
また、emax := 0,Umax := φ,pmax := nullとする。
【0096】
ステップ1708で、CPU割当てモジュール516は、Yが空集合かどうか判断し、そうでなければ、ステップ1710で、Yから1つのPノードpを取り出す。そしてpはYから削除する。さらに、利用可能なプロセッサ数(n)分の空集合(U1, …Un)を用意し、pの各子ノードを、各集合の重みがなるべく均等になるようU1, … Unに配分する(このために bin packing algorithmなどを利用する)
また、以下の変数を用意する。
m := 配分された集合ごとに属するノードの重みの和を計算し、その中で最大の値
e := pの全子ノードの重みの和 - m
emax < e なら emax := e, Umax = {U1, …, Un} , pmax := p とする。この後、処理は、ステップ1708に戻る。
【0097】
そこで、ステップ1708に戻って、Yが空集合であると判断されると、CPU割当てモジュール516は、ステップ1712で、l := q の下位の葉ノードで、pmaxの下位でない葉ノードの内、pmaxよりも前の葉ノードのリストとする。
また、r := q の下位の葉ノードで、pmax の下位でない葉ノードの内、pmaxよりも後ろの葉ノードのリストとする。
こうしておいて、CPU割当てモジュール516は、lに含まれる葉ノードを根ノードの子ノードとしてqの直前に、rに含まれる葉ノードを根ノードの子ノードとして qの直後にリスト内の順序を維持したまま移動する。そして、qをpmaxで置き換える。
そしてさらに、CPU割当てモジュール516は、以下の処理を行う。
pmaxの子ノードを切り離す(一度子ノードがいない状態になる)。
Umaxの要素のうち、空でない各集合Uiに対し、新しいSノードをpmaxの子ノードとして作成する。
各 Uiに含まれるすべてのノードの下位の葉ノードを、順序関係を維持したまま対応するSノードの子ノードとする。
【0098】
このステップ1712の処理が終わると、処理はステップ1704に戻る。そして、Tが空集合でないなら、ステップ1706に進み、Tが空集合であると判断されると、処理は終了する。この処理の結果、Umax = {U1, …, Un}の各々にSPTが与えられる。
【0099】
この処理が終わると、出力となるSPTは、以下のような構造となる。
根ノードがSノード
根ノードの子ノードは葉ノード(すなわちオリジナルのDAG上のノード)またはPノード
当該Pノードの子ノードの数はプロセッサ数n以下
当該Pノードの子ノードはすべてSノードで、葉ノードのみをその子ノードに持つ
SPT上に存在するすべてのPノードの子ノードの数はプロセッサ数以下であるため、各子ノード以下の葉ノード(元のDAG上のノード)をどのようにプロセッサに配分するかを示した構造になっている。
根ノードの子ノードのうち、連続する非xノードである葉ノード、および各Pノードが一つのコード化の単位となる。
【0100】
こうして、図6のステップ612では、Umax = {U1, …, Un}の各々にSPTがコードに展開されて、実行可能ファイルにコンパイルされ、ステップ614で個別のプロセッサまたはコアに割り当てられて実行される。この際、U1, …, Unのうちの、コード化対象外コードを含む要素は、実行可能ファイルにコンパイルにされず、MATLAB(R)/Simulink(R)のインタープリターにより実行されることになる。
【0101】
以上説明した実施例において、タスク・グラフをSPTに変換する前に、コード化対象外コードをマージするように、タスク・グラフを変形するようにしたが、これは望ましい処理ではあるが必須ではなく、タスク・グラフを変形する処理を省略しても、コンパイル結果の実行速度向上の効果は得られることを理解されたい。
【0102】
以上、この発明を特定の実施例に基づき説明してきたが、この発明は、この特定の実施例に限定されず、当業者が自明に思いつく様々な変形、置換などの構成、技法適用可能であることを理解されたい。例えば、特定のプロセッサのアーキテクチャ、オペレーティング・システムなどに限定されない。
【0103】
また、上記実施例は、MATLAB(R)/Simulink(R)を例にとって説明したが、これに限らず、任意のモデリング・ツールに適用可能であることを、この技術分野の当業者なら理解するであろう。
【符号の説明】
【0104】
302 コード化対象外ブロック
406 メイン・メモリ
416 ハードティスク・ドライブ
502 シミュレーション・モデリング・ツール
504 モデル・データ
508 DAG変換モジュール
510 タスク・グラフ変形モジュール
512 SPT変換モジュール
514 SPT変形モジュール
516 CPU割当てモジュール
518 コンパイラ
520 実行環境
【技術分野】
【0001】
この発明は、シミュレーション・システムにおいて、並列化によりプログラムの実行を高速化する技法に関する。
【背景技術】
【0002】
近年、科学技術計算、シミュレーションなどの分野で、複数のプロセッサをもつ、いわゆるマルチプロセッサ・システムが使用されている。一方、最近になって特に盛んに開発されるようになってきたシミュレーションの分野として、ロボット、自動車、飛行機などのメトカトロニクスのプラントのシミュレーション用ソフトウェアがある。電子部品とソフトウェア技術の発展の恩恵により、ロボット、自動車、飛行機などでは、神経のように張り巡らされたワイヤ結線や無線LANなどを利用して、大部分の制御が電子的に行われる。
【0003】
それらは、本来的にはメカトロニクスの装置であるが、大量の制御ソフトウェアをも内蔵している。そのため、製品の開発に当たっては、制御プログラムの開発とそのテストに、長い時間と、膨大な費用と、多数の人員を費やす必要が出てきた。
【0004】
このようなテストにために従来行われている技法として、HILS(Hardware In the Loop Simulation)がある。特に、自動車全体の電子制御ユニット(ECU)をテストする環境は、フルビークルHILSと呼ばれる。フルビークルHILSにおいては、実験室内で、本物のECUが、エンジン、トランスミッション機構などをエミュレーションする専用のハードウェア装置に接続され、所定のシナリオに従って、テストが行われる。ECUからの出力は、監視用のコンピュータに入力され、さらにはディスプレイに表示されて、テスト担当者がディスプレイを眺めながら、異常動作がないかどうか、チェックする。
【0005】
しかし、HILSは、専用のハードウェア装置を使い、それと本物のECUの間を物理的に配線しなくてはならないので、準備が大変である。また、別のECUに取り替えてのテストも、物理的に接続し直さなくてはならないので、手間がかかる。さらに、本物のECUを用いたテストであるため、テストに実時間を要する。従って、多くのシナリオをテストすると、膨大な時間がかかる。また、HILSのエミュレーション用のハードウェア装置は、一般に、非常に高価である。
【0006】
そこで近年、高価なエミュレーション用ハードウェア装置を使うことなく、シミュレーション全体をソフトウェアで構成する手法が提案されている。その手法においては、エンジンやトランスミッションなどのプラント部分には連続系シミュレーション(continuous simulation)を利用し、また、コントローラ部分にはステート・チャート(state chart)あるいは実際のソフトウエアコードを利用する。コントローラ部分のシミュレーション方法に応じて、前者は MIL (Model-in-the-Loop) シミュレーション、後者は SIL (Software-in-the-Loop) シミュレーションと呼ばれる。MILやSILによればECUのハードウェアが存在しなくても、テストを実行可能である。
【0007】
このようなMIL/SILの構築を支援するシステムとして例えば、MathWorks社から入手可能なシミュレーション・モデリング・システムである、MATLAB(R)/Simulink(R)がある。MATLAB(R)/Simulink(R)を使用すると、画面上にグラフィカル・インターフェースによって、機能ブロックを配置し、その処理の流れを指定することによって、シミュレーション・プログラムを作成することができる。ここで、機能ブロックは、和や積などの基本演算や積分や条件分岐、さらには、ソフトウエア・コードを呼び出すブロックなどの種類があり、それぞれが入力あるいは・および出力を持つ。なお、コントローラの表現としてソフトウエア・ブロックを含むシミュレーションがSILである。
【0008】
こうして、MATLAB(R)/Simulink(R)上で、いったん機能ブロックを構成配置してブロック線図を作成すると、次に、Real-Time Workshop(R)の機能を利用して、シミュレーションの実行をさらに高速化することができる。すなわち、ソフトウエア・コード以外のブロックを、等価な機能のC言語など既知のコンピュータ言語のソース・コードに変換することにより、逐次解釈的な処理から、ホストに最適化された処理に置き換える。なお、Real-Time WOrkshop(R) の場合、コード変換を実施する単位は、モデルの全体あるいは、図1に参照番号102、104などで示すようなサブブロックの単位である。ここで、サブブロックは、モデルの可読性のために導入される階層的な構造を表現するための特別な境界を表す。例えば、サブブロック108は、参照番号108aで示すような内部的な構造をもつ。
【0009】
ところが、自動車や航空機などの制御システムは複雑なので、数千個〜数十万個の機能ブロックを含むことが普通である。従って、シミュレーション・モデルを設計して、所望のモデルを得るためには、何度も設計・コンパイル・実行を繰り返す必要がある。
【0010】
図1において、例えば、オペレータが、サブブロック102〜110などのうち、サブブロック110を編集してコンパイルして実行可能バイナリ・コードを得る。そして、その実行可能バイナリ・コードをコンピュータ・システム上で実行しで動作を確認し、所望の動作が得られないならば、再度サブブロック110を編集し、コンパイル&実行するということを繰り返す。
【0011】
機能ブロックの数が増えるにつれて、結果のソースコードが増大するが、すると、ソースコード全体をフル・コンパイルする際のコンパイル時間も長くなる。
【0012】
一般に大規模なモデルを編集するときは、編集の対象となるサブブロックは、例えば図1のサブブロック110のように、一部に限定されることが多い。特に、複合的なモデルの場合には、設計者が担当する部分を除いた他のサブブロックは、変更せずに固定化してブラックボックスのように扱われることが多い。そこで、編集の対象となるサブブロックを残して、それ以外をあらかじめコード変換しておくことで、実行速度と編集作業の両立を図ることができる。また、マルチ・プロセッサ、あるいは、マルチ・コアの環境で、分割コンパイルした個別の実行コードを、異なるプロセッサまたはコアに割り当てて並列実行させることにより、実行時間が短縮される。特に後者について、関連技術として次の特許公開公報に記述されている技法がある。
【0013】
特開平7−114486号公報は、デバッグ用の出力文を含む逐次ループを、並列化する方法に関し、逐次ループ内のI/O文を検出し、I/O文がループ不変式による条件節に含まれること検出して、I/O文を含む依存を解析し、実行順序を守るための同期文を挿入し、並列処理用のループに変換することを開示する。
【0014】
特開2011−96107号公報は、ブロック線図などで表されるプログラムにおいて、内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックとの接続関係に基づき、機能ブロック毎に、使用ブロック集合/定義ブロック集合の数を求め、その数に基づき、複数のストランドを割り当て、これにより、ブロック線図を、ストランドに分けて処理を並列化することを開示する。
【0015】
図2は、サブブロックにアラインした単純分割の例を示す。すなわち、図2では、領域202、204、206などに分割されている。しかしながら、MATLAB(R)/Simulink(R) のように、タイムステップに基づくシミュレーションの場合には、必ずしもサブブロックの単位でまとめてコード変換ができるとは限らない。たとえば、ブロックの実行順序をスケジュールするにはサブブロックの中(下位の階層)まで解析する必要があり、その結果、サブブロックの中ほど(途中)から計算を開始することが決定した場合には、実質的にサブブロックは前後に分断されなければならない。また、例えば、MATLAB(R)/Simulink(R)のScopeブロックのような結果を表示するブロックはコード変換することができず、したがって、そのようなコード化することができない機能ブロックを含むサブブロックは、その単位のままではコード化できない。以上のような制約を考慮して試みられた分割の例を図3に示す。すなわち、図3に示すように、分割は、コード化対象外ブロック314、316を除外し、スケジュールに合わせた実行開始コード310、312が先頭にくるように分割・再構成によりコード変換を適用することが、シミュレーションの高速化のためには望ましい。
【0016】
しかしながら、そのような分割および再構成の手法は自明ではなく、特に、並列化のための分割手順は組合せ問題となり、最適な組合せを短時間で計算することは一般に非常に困難である。そこで、限られた時間の中で準最適な解を求めることが強く求められる。
【先行技術文献】
【特許文献】
【0017】
【特許文献1】特開平7−114486号公報
【特許文献2】特開2011−96107号公報
【発明の概要】
【発明が解決しようとする課題】
【0018】
この発明の目的は、基本処理の流れを表すブロック線図について、その実行速度を最適化するように分割することである。
この発明の他の目的は、その際に、実行速度を損なわないように、コード化対象外ブロックを分割の境界に配置するための技法を提供することにある。
【課題を解決するための手段】
【0019】
この発明は、上記課題を解決するためになされたものであり、この発明に従うシステムは先ず、ブロック線図を、DAG(directed acyclic graph)のタスク・グラフに変換する。
【0020】
次に、この発明に従うシステムは、上記タスク・グラフを、既知のアルゴリズムに従い一旦直列−並列グラフ(SPG: series-parallel graph)に変換してから、構造(構文)解析を行い、一意の直列−並列木(SPT: series-parallel parse tree)を得る。SPTは、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む。また、末端のノードは、タスク・グラフのノードを表す。
【0021】
次に、この発明に従うシステムは、上記SPTを、コード化対象外ブロックの上位にPノードが存在しなくなるまで、別のSPTに変形する。
【0022】
こうして最適なSPTが得られると、発明に従うシステムは、結果のSPTのPノードの下に連なるブロックを並列に実行するように、コードを生成しコンパイルして、異なるプロセッサまたはコアに割り当てて、並列実行させる。
【0023】
なお、あるDAGのタスク・グラフに対して一般的に、ノード実行順序の前後関係に矛盾しないSPTは複数存在する。そこで、本発明の好適な一側面によれば、SPTに変換する前に、DAGのタスク・グラフは、点在するコード化対象外ブロックをなるべくマージさせるように変形される。これによって、結果のタスク・グラフの分割数の低減がはかられる。一般に、各分割のサイズが同程度であれば、全体におけるクリティカル・パスが小さくなって並列処理での高速化の効果が大きくなる。また、逐次処理であっても、分割数が小さければ、呼び出しのオーバヘッドが減少するために、実行の高速化に大いに貢献する。
【発明の効果】
【0024】
この発明によれば、ブロック線図であらわされるプログラム・コードにおいて、コード化対象外ブロックの存在を考慮して、コードの分割数を減らし、並列実行コストのバランスのとれた分割を与える技法が提供される。
【図面の簡単な説明】
【0025】
【図1】タスク・グラフのコンパイルと実行を説明するための図である。
【図2】サブブロックにアラインした単純分割を示す図である。
【図3】コード化対象外ブロックと実行スケジュールに合わせた最大分割を示す図である。
【図4】本発明を実施するためのハードウェアのブロック図である。
【図5】本発明を実施するための機能ブロック図である。
【図6】本発明の処理全体の概要フローチャートを示す図である。
【図7】タスク・グラフ変形処理のフローチャートを示す図である。
【図8】タスク・グラフ変形処理におけるリスト・スケジューリングの例を示す図である。
【図9】タスク・グラフをSPTに変換する処理のフローチャートを示す図である。
【図10】タスク・グラフをSPTに変換する処理の例を示す図である。
【図11】タスク・グラフをSPTに変換する処理の例を示す図である。
【図12】SPT変形処理のフローチャートを示す図である。
【図13】SPT変形処理の例を示す図である。
【図14】SPT変形処理の例を示す図である。
【図15】SPT変形処理における主要な処理を説明するための図である。
【図16】SPT変形処理における主要な処理を説明するための図である。
【図17】個別のプロセッサまたはコアに割り当てるコードを生成するための処理のフローチャートを示す図である。
【発明を実施するための形態】
【0026】
以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。
【0027】
先ず、図4を参照して、本発明を実施するために使用されるコンピュータのハードウェアについて説明する。図4において、ホスト・バス402には、複数のCPU1 404a、CPU2 404b、CPU3 404c、・・・CPUn 404nが接続されている。ホスト・バス402にはさらに、CPU1 404a、CPU2 404b、CPU3 404c、・・・CPUn 404nの演算処理のためのメイン・メモリ406が接続されている。
【0028】
一方、I/Oバス408には、キーボード410、マウス412、ディスプレイ414及びハードティスク・ドライブ416が接続されている。I/Oバス408は、I/Oブリッジ418を介して、ホスト・バス402に接続されている。キーボード410及びマウス412は、オペレータが、コマンドを打ち込んだり、メニューをクリックするなどして、操作するために使用される。ディスプレイ414は、必要に応じて、本発明に係るプログラムをGUIで操作するためのメニューを表示するために使用される。
【0029】
この目的のために使用される好適なコンピュータ・システムのハードウェアとして、IBM(R)System Xがある。その際、CPU1 404a、CPU2 404b、CPU3 404c、・・・CPUn 404nは、例えば、インテル(R)Xeon(R)であり、オペレーティング・システムは、Windows(商標)Server 2003である。オペレーティング・システムは、ハードティスク・ドライブ416に格納され、コンピュータ・システムの起動時に、ハードティスク・ドライブ416からメイン・メモリ406に読み込まれる。
【0030】
本発明を実施するためには、マルチプロセッサ・システムを用いることが必要である。ここでマルチプロセッサ・システムとは、一般に、独立に演算処理し得るプロセッサ機能のコアを複数もつプロセッサを用いるシステムを意図しており、従って、マルチコア・シングルプロセッサ・システム、シングルコア・マルチプロセッサ・システム、及びマルチコア・マルチプロセッサ・システムのどれでもよいことを理解されたい。
【0031】
なお、本発明を実施するために使用可能なコンピュータ・システムのハードウェアは、IBM(R)System Xに限定されず、本発明のシミュレーション・プログラムを走らせることができるものであれば、任意のコンピュータ・システムを使用することができる。オペレーティング・システムも、Windows(R)XP、Windows(R)7、Linux(R)、Mac OS(R)など、任意のオペレーティング・システムを使用することができる。さらに、シミュレーション・プログラムを高速で動作させるために、POWER(商標)6ベースで、オペレーティング・システムがAIX(商標)のIBM(R)System Pなどのコンピュータ・システムを使用してもよい。
【0032】
ハードティスク・ドライブ416にはさらに、MATLAB(R)/Simulink(R)、Cコンパイラまたは、C++コンパイラ、後述する、タスクグラフ生成、タスクグラフ変形直接−並列木(SPT)変換、SPT変形などのためのモジュール、CPU割り当て用コード生成モジュールなどが格納されており、オペレータのキーボードやマウス操作に応答して、メイン・メモリ406にロードされて実行される。タスクグラフ生成、タスクグラフ変形直接−並列木(SPT)変換、SPT変形などのためのモジュールは、Java(R)、C、C++、C#などの既存の任意のプログラミング言語で作成することができる。
【0033】
尚、使用可能なシミュレーション・モデリング・ツールは、MATLAB(R)/Simulink(R)に
限定されず、オープンソースのScilab/Scicosなど、タイム・ステップに基づくタスク・グラフで表現される任意のシミュレーション・モデリング・ツールを使用することが可能である。
【0034】
あるいは、場合によっては、シミュレーション・モデリング・ツールを使わず、直接、C、C++などでシミュレーション・システムのソース・コードを書くことも可能であり、その場合にも、個々の機能が、互いに依存関係にある個別の機能ブロックとして記述できるなら、本発明は適用可能である。
【0035】
図5は、本発明の実施例に係る機能ブロック図である。各々のブロックは、基本的に、ハードティスク・ドライブ416に格納されているモジュールに対応する。
【0036】
図5において、シミュレーション・モデリング・ツール502は、好適には、MATLAB(R)/Simulink(R)であり、それ以外に、Scilab/Scicosなど、コード化対象外ブロックを含み得る、任意のシミュレーション・モデリング・ツールを使用することができる。
【0037】
モデル・データ504は、シミュレーション・モデリング・ツール502を用いて作成され、好適にはブロック線図で記述され、ハードディスク・ドライブ416に保存されている。そのブロック線図に含まれるブロックにおいて、コード化対象外ブロックは、予めマークされている。
【0038】
メイン・ルーチン506は、本発明に係る処理の各種モジュールを呼び出し、実行するためのプログラムであり、好適には、ディスプレイ414上で、キーボード410やマウス412で操作して処理を行うためのGUIなどのインターフェースを与える。
【0039】
DAG変換モジュール508は、モデル・データ504を読み込んで、DAGのタスク・グラフに変換する機能をもつ。好適には、変換されたタスク・グラフのデータは、メイン・メモリ406上に必要な領域を確保して展開される。なお、コンピュータ・メモリ上にグラフを表現するデータ構造として、行列表現あるいはリスト表現などが知られているが、この実施例で、既知の任意のデータ構造を使用することができる。
【0040】
タスク・グラフ変形モジュール510は、DAG変換モジュール508によって変換して得られたタスク・グラフに含まれるコード化対象外ブロックを可能な範囲でマージする機能をもつ。変形された結果のタスク・グラフは、好適には、メイン・メモリ406上に必要な領域を確保して展開される。この処理は後で、図7のフローチャートを参照して、より詳細に説明する。
【0041】
SPT変換モジュール512は、タスク・グラフ変形モジュール510によって変形して得られたタスク・グラフを、直接−並列木(SPT)に変換する機能をもつ。SPTは、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む。変換された結果のタスク・グラフは、好適には、メイン・メモリ406上に必要な領域を確保して展開される。この処理は後で、図9のフローチャートを参照して、より詳細に説明する。
【0042】
SPT変形モジュール514は、SPT変換モジュール512によって得られたSPTのグラフを、別の直接−並列木(SPT)に変形する機能をもつ。変形は、コード化対象外ブロックの上位にPノードが存在しなくなるまで行われる。変形された結果のタスク・グラフは、好適には、メイン・メモリ406上に必要な領域を確保して展開される。この処理は後で、図12のフローチャートを参照して、より詳細に説明する。
【0043】
CPU割当てモジュール516は、SPT変形モジュール514の変形の結果得られたSPTに基づき、個別のプロセッサあるいはコアに割り当てるためのコードを抽出する。抽出されたコードは、好適には、ハードティスク・ドライブ416に書き出される。このコードは、機能ブロックに対応する、好適にはCまたはC++のソースコードである。CPU割当てモジュール516の処理は後で、図17のフローチャートを参照して、より詳細に説明する。
【0044】
コンパイラ518は、CPU割当てモジュール516によって書き出されたコードをコンパイルして、実行可能コードを生成する。実行環境520は、個別のプロセッサあるいはコアに割り当てて並列実行させる。実行環境520は、好適には、CPU割当てモジュール516が生成した補助的な情報を参照して実行可能コードを割り当てる。
【0045】
実行環境520の一部として、MATLAB(R)/Simulink(R)を利用する場合には、それが未コンパイルの(サブ)ブロックとコンパイル済みのサブブロックを区別して、前者はインタプリターとして実行し、後者はバイナリーコードとしてホスト実行する。
【0046】
図6は、本発明の処理の全体の流れを示す概要フローチャートである。この後の詳細な説明は、この流れに沿って説明することになる。
【0047】
ステップ602では、DAG変換モジュール508により、モデル・データがDAGのタスク・グラフに変換される。
【0048】
ステップ604では、タスク・グラフ変形モジュール510により、コード化対象外ブロックを可能な範囲でマージするように、タスク・グラフが変形される。
【0049】
ステップ606では、SPT変換モジュール512により、タスク・グラフがSPTに変換される。
【0050】
ステップ608では、SPT変形モジュール514により、SPTが、コード化対象外ブロックの上位にPノードが存在しなくなるように、別のSPTに変換される。
【0051】
ステップ610では、SPT変形モジュール514により生成されたSPTに基づき、CPU割当てモジュール516により、各CPUに割り当てるためのコードが生成される。
【0052】
ステップ612では、コンパイラ518により、生成されたコードがコンパイルされ、ステップ614では、コンパイルされたコードが実行される。
【0053】
以下、各ステップについて詳細に説明するが、その前に、DAG およびSPT上のノードに関する用語について定義を与えておく。
xノード : コード化対象外ノード
非xノード :コード化対象ノード
SPT上のノードに関する用語
ノードの順序 : 木の(Tree)左優先の深さ優先探索(Depth first search)で辿られる順番で決定する。SPT中のある二つのノードに対して、辿られる順番が他方より早いものを前、他方より遅い方を後ろとする。
根ノード : 一般的な定義に順ずる。
葉ノード : 子ノードを持たないノード。DAG上のノードに対応する。(一般的な定義と同じ)
内部ノード : 葉ノードでないノード (一般的な定義と同じ)
親ノード : 一般的な定義に順ずる
子ノード : 一般的な定義に順ずる
兄ノード : 親ノードが同じノードのうち、対象ノードより前にあるノード
弟ノード : 親ノードが同じノードのうち、対象ノードより後ろにあるノード
兄弟ノード : 兄ノードおよび弟ノード
祖父ノード : 親ノードの親ノード
曽祖父ノード : 祖父ノードの親ノード
Sノード : 子ノードの直列実行を表す内部ノード
Pノード : 子ノードの並列実行を表す内部ノード
【0054】
また、SPTの構成に関する補足について述べると、SPT上では、Sノード同士またはPノード同士が親子関係になることはないものとする。仮に同種の内部ノードが親子関係になった場合には、当該子ノードを切り離し、当該子ノードの子ノードを順序を維持したまま親ノードに移動させる(このとき移動されるノード以下のノードも引き連れて移動するものとする)処理を自動的に適用するものとする。上記処理は、木によって表現される直列・並列実行の意味合いを変化させない。
【0055】
以上の定義と補足に基づき、図6の各ステップを順に説明していく。先ず、モデル・データをDAGのタスク・グラフに変換するステップ602であるが、DAG変換モジュール508は、モデル・データ504を読み込んで、DAGのタスク・グラフに変換する。このとき、図3にあるような、スケジュールの先頭になるブロックを解釈して、自己ループのないDAG構造へと変換する。好適には、変換されたタスク・グラフのデータは、メイン・メモリ406上に必要な領域を確保して展開される。DAG変換モジュール508は、ブロック線図として記述されたモデル・データ504において、入力のない機能ブロックや実行のスケジュール上先頭に来る機能ブロックを全体のソースとして、またノード間の接続を有向エッジとしてDAG(無閉路有向グラフ)を構成する。全体のシンクとなるのは、出力のない機能ブロックや実行上、最後にスケジュールされる機能ブロックなどである。
【0056】
タスク・グラフ変形モジュール510が、コード化対象外ブロックを可能な範囲でマージするように、タスク・グラフを変形するステップ604は、タスク・グラフに対して以下の性質を持つリストスケジューリングを行い、スケジュール上で隣接するコード化対象外ノード(X)をひとつにマージする処理を行う。
【0057】
このとき、直前にスケジュールされたノードがxであれば可能な限りxをスケジュールし、直前にスケジュールされたノードがxでなければ可能な限りxでないノードをスケジュールする。
【0058】
ここでの目的は、タスクノードの前後関係に矛盾しない範囲でなるべくxをひとつの塊にすることである。これにより、次のステップで抽出されるSPT上で x が分散配置されて最終的なコードの分割数を増やしたり、最終的に利用(exploit)できないxとの並列性の抽出により本来利用できる並列性が抽出されない事態を極力回避する。
【0059】
図7は、図6のステップ604に対応する、タスク・グラフ変形モジュール510の処理のフローチャートを示す図である。この処理は、xノード、非xノードをもつDAGを入力とし、直列スケジュールSを出力する。直列スケジュールSは、タスク・グラフにおいて、マージされた単一のノードとして扱われる。
【0060】
さて、図7のステップ702において、タスク・グラフ変形モジュール510は、空のリストとしてS、DAGの全ノード(未スケジュールノード集合)としてCを用意する。
【0061】
ステップ704でタスク・グラフ変形モジュール510は、親をC中に持たないC中の非xノードの集合としてRoを、親をC中に持たないC中のxノードの集合としてRxを、それぞれ用意する。
【0062】
ステップ706でタスク・グラフ変形モジュール510は、Ro = φ ∧ Rx = φすなわち、Roが空集合且つRxが空集合かどうか判断する。
【0063】
そうでないなら、タスク・グラフ変形モジュール510は、ステップ708で、直前にSに加えられたノードがxノードかどうか判断し、そうならステップ710で、Rx = φかどうか判断する。
【0064】
ステップ710でRx = φでないと判断すると、タスク・グラフ変形モジュール510は、ステップ712で、Rxから1つノードを取り出し、そのノードはRxから削除し、そのノードをSの最後に加える。更にそのノードをCから削除する。そして、ステップ704に戻る。
【0065】
ステップ710に戻って、Rx = φであると判断すると、タスク・グラフ変形モジュール510は、ステップ714に進み、Ro = φかどうか判断する。
【0066】
ステップ714でRo = φでないと判断すると、タスク・グラフ変形モジュール510は、ステップ716で、Roから1つノードを取り出し、そのノードはRoから削除し、そのノードをSの最後に加える。更にそのノードをCから削除する。そして、ステップ704に戻る。
【0067】
ステップ708に戻って、直前にSに加えられたノードがxノードでないなら、ステップ714に進み、タスク・グラフ変形モジュール510はRo = φかどうか判断し、もしそうなら、ステップ710に進む。ステップ710での処理は、上述のとおりである。ステップ714でRx = φでないと判断された場合の処理も上述のとおりである。
【0068】
こうして、ステップ704を経由してステップ706に戻った時点で、Roが空集合且つRxが空集合であると判断すると、タスク・グラフ変形モジュール510は、ステップ718で、S中で隣接するxノードを1つの集合とし、その集合毎に含まれるxノードをDAG上で1つのノードにマージする処理を行い、処理を終わる。
【0069】
図8は、図7の処理の様子を模式的に示す図である。すなわち、図8(a)に示すようなタスク・グラフが与えられると、図7のフローチャートに示すステップ702〜716の処理で、図8(b)に示すリスト・スケジューリングが行われる。そこで、ステップ718の処理で、隣接するxノードを1つの集合とし、その集合毎に含まれるxノードをDAG上で1つのノードにマージすることで、図8(c)に示す変更されたタスク・グラフが得られる。
【0070】
図9は、SPT変換モジュール512の処理のフローチャートを示す図である。この処理は、図6のステップ606に対応する。この処理は、DAGを入力とし、SPTを出力する。
【0071】
ステップ902で、SPT変換モジュール512は、DAGを直列−並列グラフに変換して、それをSPGとおく。DAGを直列−並列グラフに変換する処理として、例えば、A. Gonzalez Escribano, V. Cardenoso and A.J.C. van Gemund, “Conversion from NSP to SP graphs”, Tech. Rep. TR-DINFO-01-97, Universidad de Valladolid, Valladolid (Spain), 1997などに記述されている技法を使用することができる。また、ステップ902では、SPGの構造を解析して、SPT(series-parallel parsed tree)を得る。
ここで、SPT上の葉ノードはSPGのノードに対応する。また、非端末(非葉)ノードはSPG上には存在しないが、間接的にノード間の接続順序を表す。
【0072】
次にステップ904で、SPT変換モジュール512は、SPG上のノード数が1以下かどうか判断し、そうでないなら、ステップ906に進む。
【0073】
ステップ906でSPT変換モジュール512は、以下の処理を行う。すなわち、SPG上で直列に接続しているノードのパスを見つける。ここで、直列に接続しているノードのパスとは、親を複数持つ、または親を持たないノードから、子を複数持つ、または子を持たないノードまでの、親と子を1つずつ持つノードによって構成されるパスを指す。
【0074】
そして、SPT変換モジュール512は、各々のパスLに対して、以下の処理を行う。
SPG上のLに属するすべてのノードを一つのノードSに置き換える(このとき、Lの外部のノードとの接続関係は維持される)。
同時に、SをSPT上の一つのノードとし、L中のノードに該当するSPT上のノードをL中での順序順にSPT上のSの子ノードとして加える。ここで、SPG上に構成されていくノードは、対応するノードがSPT上にも構築されていくため、つねに互いに対応関係が取れる。
【0075】
次に、SPT変換モジュール512は、ステップ908で、SPG上で並列関係にあるノードの集合を見つける。ここで、並列関係にあるノードの集合とは、親および子ノードが一致(存在しない場合を含む)しているノードの集合を指す。
【0076】
また、SPT変換モジュール512は、各々の集合Cに対して、以下の処理を行う。
SPG上のCに属するすべてのノードを一つのノードPに置き換える(このとき、Pの外部のノードとの接続関係は維持される)。
同時に、PをSPT上の一つのノードとし、C中のノードに該当するSPT上のノードを、SPT上のPの子ノードとして加える。ここでも、SPG上に構成されていくノードは、対応するノードがSPT上にも構築されていくため、つねに互いに対応関係が取れることに留意されたい。
【0077】
ステップ908の後は、SPT変換モジュール512は、ステップ904に戻り、SPT変換モジュール512は、SPG上のノード数が1以下かどうか判断し、もしそうなら、処理を終わる。
【0078】
図10は、図9に示すフローチャートの処理に従い、DAGをSPTに変換する例を示す図である。すなわち、図10(a)のDAGが、図10(b)のSPTに変換される。その際、SPTでは、子ノードの直列実行を表す内部ノードであるSノードと、子ノードの並列実行を表す内部ノードであるPノードが生成されていることが見て取れる。
【0079】
参考までに、図11は、タスク・グラフ変形モジュール510の変形を経ていないDAGをSPTに変換する例を示す図である。図11(b)に示すSPTは、図10(b)のSPTに比較して、xノードが葉ノードとして散在していることが見て取れる。
【0080】
図12は、SPT変形モジュール514の処理のフローチャートを示す図である。この処理は、図6のステップ608に対応する。この処理は、SPTを入力とし、SPTを出力する。
【0081】
ステップ1202で、SPT変形モジュール514は、SPTの根ノードがPノードである場合、新たな根ノードとしてSノードを設け、元の根であったPノードを当該Sノードの子ノードとする。また、上位にPノードを持つSPT上のすべてのxノードの集合をXとする。
【0082】
ステップ1204で、SPT変形モジュール514は、Xが空集合かどうか判断する。もし空集合なら、処理を終わる。
【0083】
もしXが空集合でないなら、ステップ1206に進み、SPT変形モジュール514は、Xから1つの要素xを取り出す(xはXから削除)。
【0084】
ステップ1208で、SPT変形モジュール514は、xの親がSかどうか判断する。そうでなければ、SPT変形モジュール514はステップ1210で、xを祖父ノードとして、親ノードの直前に移動する。このとき、SPT上のノードを移動する場合、その子ノード以下もすべて引き連れて移動することとする。
【0085】
ステップ1212で、SPT変形モジュール514は、xの祖先にPノードが存在するかどうか判断する。もしそうなら、処理はステップ1208に戻り、そうでなければ処理はステップ1204に戻る。
【0086】
ステップ1208に戻って、xの親がSであると判断すると、処理はステップ1214に進み、そこで、SPT変形モジュール514は、xの兄ノードの重みの和 < xの弟ノードの重みの和であるかどうか判断する。ここで、SPT上のノードの重みとは、そのノード以下の葉ノードの重みの和である。葉ノードは元のDAG上のノードであり、DAG上のノードはシミュレーション・モデル中の特定の処理と対応づいている。その処理の計算時間をDAG上のノードの重みとする。
【0087】
もしxの兄ノードの重みの和 < xの弟ノードの重みの和であると判断すると、SPT変形モジュール514は、ステップ1216で、xの兄ノードおよびxを、順序を維持したままxの曽祖父ノードの子として、xの祖父ノードの直前に移動し、ステップ1212に戻る。xの兄ノードの重みの和 < xの弟ノードの重みの和ではないと判断すると、SPT変形モジュール514は、ステップ1218で、xおよびxの弟ノードを、順序を維持したままxの曽祖父ノードの子として、xの祖父ノードの直後に移動し、ステップ1212に戻る。
【0088】
ステップ1212からは、そこでの判断に応じて、処理はステップ1208またはステップ1204に戻る。
【0089】
図13は、図12に示すフローチャートの処理に従い、SPTを変形する例を示す図である。すなわち、図13(b)では、変形後のSPTでは最早、コード化対象外ブロックxの上位にPノードが存在しないことが見て取れる。
【0090】
参考までに、図14は、タスク・グラフ変形モジュール510の変形を経ていないDAGから変換されたSPT(図14(a))を、図12に示すフローチャートの処理に従い、変形した例を示す図である。図14(b)ではやはり、変形後のSPTでは最早、コード化対象外ブロックxの上位にPノードが存在しているが、コード化対象外ブロックxが、トップのSノードの下に分散していることが見て取れる。
【0091】
図15及び図16は、SPTの変形の途中の様子を示すである。先ず、図15(a)に示すように、コード化対象外ブロックのノードxが、Pの直下にあるなら、変形処理は、図15(b)または図15(c)に示すように、ノードxを、祖父ノードSの子ノードとして、親ノードPの前または後ろに移動することである。すなわち、図15(b)がノードxを親ノードPの後ろに移動することに対応し、図15(c)がノードxを親ノードPの前に移動することに対応する。このようにしても、依存性の違反にはならない。
【0092】
すると、図16のような状態に移行する。これは、図16(a)に示すように、ノードxが、Sの直下にある場合である。この場合の変形処理は、図16(b)または図16(c)に示すように、ノードxと、その同一の親Sの下にある先行ノードまたは後続ノードを、曽祖父ノードSの子として、祖父ノードPの前または後ろに移動することである。図16(b)が後続ノードを祖父ノードPの後に移動することに対応し、図16(c)が先行ノードを祖父ノードPの前に移動することに対応する。このようにしても、依存性の違反にはならない。この際、移動の方向によってPの下から移動するノードのワークロードが異なるため、小さい方を選択して移動させる。
【0093】
図17は、CPU割当てモジュール516が、変形された結果のSPTに基づき、複数のCPUに個別に割り当てるコードに対応するSPTを生成する処理のフローチャートを示す図である。この処理は、図6のステップ610に対応する。この処理は、SPTを入力とし、SPTを出力する。以下で、maxは、利用可能なプロセッサまたはコアの数である。
【0094】
ステップ1702で、CPU割当てモジュール516は、SPTの根ノードの子ノードのうち、Pノードの集合としてTを用意する。
【0095】
ステップ1704で、CPU割当てモジュール516は、Tが空集合かどうか判断し、もしそうなら処理を終了する。そうでなければ、ステップ1706に進み、Tから一つのPノードqを取り出す。qはTから削除する。また、Yを、qおよび、qの下位にあるすべてのPノードの集合とする。
また、emax := 0,Umax := φ,pmax := nullとする。
【0096】
ステップ1708で、CPU割当てモジュール516は、Yが空集合かどうか判断し、そうでなければ、ステップ1710で、Yから1つのPノードpを取り出す。そしてpはYから削除する。さらに、利用可能なプロセッサ数(n)分の空集合(U1, …Un)を用意し、pの各子ノードを、各集合の重みがなるべく均等になるようU1, … Unに配分する(このために bin packing algorithmなどを利用する)
また、以下の変数を用意する。
m := 配分された集合ごとに属するノードの重みの和を計算し、その中で最大の値
e := pの全子ノードの重みの和 - m
emax < e なら emax := e, Umax = {U1, …, Un} , pmax := p とする。この後、処理は、ステップ1708に戻る。
【0097】
そこで、ステップ1708に戻って、Yが空集合であると判断されると、CPU割当てモジュール516は、ステップ1712で、l := q の下位の葉ノードで、pmaxの下位でない葉ノードの内、pmaxよりも前の葉ノードのリストとする。
また、r := q の下位の葉ノードで、pmax の下位でない葉ノードの内、pmaxよりも後ろの葉ノードのリストとする。
こうしておいて、CPU割当てモジュール516は、lに含まれる葉ノードを根ノードの子ノードとしてqの直前に、rに含まれる葉ノードを根ノードの子ノードとして qの直後にリスト内の順序を維持したまま移動する。そして、qをpmaxで置き換える。
そしてさらに、CPU割当てモジュール516は、以下の処理を行う。
pmaxの子ノードを切り離す(一度子ノードがいない状態になる)。
Umaxの要素のうち、空でない各集合Uiに対し、新しいSノードをpmaxの子ノードとして作成する。
各 Uiに含まれるすべてのノードの下位の葉ノードを、順序関係を維持したまま対応するSノードの子ノードとする。
【0098】
このステップ1712の処理が終わると、処理はステップ1704に戻る。そして、Tが空集合でないなら、ステップ1706に進み、Tが空集合であると判断されると、処理は終了する。この処理の結果、Umax = {U1, …, Un}の各々にSPTが与えられる。
【0099】
この処理が終わると、出力となるSPTは、以下のような構造となる。
根ノードがSノード
根ノードの子ノードは葉ノード(すなわちオリジナルのDAG上のノード)またはPノード
当該Pノードの子ノードの数はプロセッサ数n以下
当該Pノードの子ノードはすべてSノードで、葉ノードのみをその子ノードに持つ
SPT上に存在するすべてのPノードの子ノードの数はプロセッサ数以下であるため、各子ノード以下の葉ノード(元のDAG上のノード)をどのようにプロセッサに配分するかを示した構造になっている。
根ノードの子ノードのうち、連続する非xノードである葉ノード、および各Pノードが一つのコード化の単位となる。
【0100】
こうして、図6のステップ612では、Umax = {U1, …, Un}の各々にSPTがコードに展開されて、実行可能ファイルにコンパイルされ、ステップ614で個別のプロセッサまたはコアに割り当てられて実行される。この際、U1, …, Unのうちの、コード化対象外コードを含む要素は、実行可能ファイルにコンパイルにされず、MATLAB(R)/Simulink(R)のインタープリターにより実行されることになる。
【0101】
以上説明した実施例において、タスク・グラフをSPTに変換する前に、コード化対象外コードをマージするように、タスク・グラフを変形するようにしたが、これは望ましい処理ではあるが必須ではなく、タスク・グラフを変形する処理を省略しても、コンパイル結果の実行速度向上の効果は得られることを理解されたい。
【0102】
以上、この発明を特定の実施例に基づき説明してきたが、この発明は、この特定の実施例に限定されず、当業者が自明に思いつく様々な変形、置換などの構成、技法適用可能であることを理解されたい。例えば、特定のプロセッサのアーキテクチャ、オペレーティング・システムなどに限定されない。
【0103】
また、上記実施例は、MATLAB(R)/Simulink(R)を例にとって説明したが、これに限らず、任意のモデリング・ツールに適用可能であることを、この技術分野の当業者なら理解するであろう。
【符号の説明】
【0104】
302 コード化対象外ブロック
406 メイン・メモリ
416 ハードティスク・ドライブ
502 シミュレーション・モデリング・ツール
504 モデル・データ
508 DAG変換モジュール
510 タスク・グラフ変形モジュール
512 SPT変換モジュール
514 SPT変形モジュール
516 CPU割当てモジュール
518 コンパイラ
520 実行環境
【特許請求の範囲】
【請求項1】
コンピュータの処理により、コード化対象外ブロックと、コード化対象ブロックを含む複数のブロックを連結して構成されたコードを並列化する方法であって、
前記コードを、DAGのタスク・グラフとして用意するステップと、
前記タスク・グラフを、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む、直接−並列木に変換するステップと、
前記コード化対象外ブロックの上位に前記Pノードが存在しなくなるまで前記直接−並列木を別の直接−並列木に変形するステップを有する、
コード並列化方法。
【請求項2】
前記直接−並列木に変換する前に、前記タスク・グラフにおいて、前記コード化対象外ブロックをマージするステップをさらに含む、
請求項1に記載のコード並列化方法。
【請求項3】
前記コード化対象外ブロックのマージが、リスト・スケジューリングにより行われる、請求項2に記載のコード並列化方法。
【請求項4】
請求項1のコード並列化方法で生成されたコードを、マルチプロセッサ環境で実行する方法であって、
前記Pノードの下位の個々のノードをコード化するステップと、
該コード化されたコードを実行可能コードに個別にコンパイルするステップと、
前記実行可能コードを個々のプロセッサに割り当てて実行するステップを有する、
コード並列実行方法。
【請求項5】
請求項1のコード並列化方法で生成されたコードを、前記コード化対象外ブロックのコードを実行するためのインタープリタをもつマルチプロセッサ環境で実行する方法であって、
前記Pノードの下位の個々のノードをコード化するステップと、
該コード化されたコードが前記コード化対象外ブロックを含まないなら、実行可能コードに個別にコンパイルするステップと、
前記実行可能コードを個々のプロセッサに割り当てて実行するステップと、
前記コード化されたコードが前記コード化対象外ブロックを含むなら、前記コード化されたコードを前記インタープリタで実行するステップを有する、
コード並列実行方法。
【請求項6】
コンピュータの処理により、コード化対象外ブロックと、コード化対象ブロックを含む複数のブロックを連結して構成されたコードを並列化するプログラムであって、
前記コンピュータに、
前記コードを、DAGのタスク・グラフとして用意するステップと、
前記タスク・グラフを、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む、直接−並列木に変換するステップと、
前記コード化対象外ブロックの上位に前記Pノードが存在しなくなるまで前記直接−並列木を別の直接−並列木に変形するステップを実行させる、
プログラム。
【請求項7】
前記直接−並列木に変換する前に、前記タスク・グラフにおいて、前記コード化対象外ブロックをマージするステップをさらに含む、
請求項6に記載のプログラム。
【請求項8】
前記コード化対象外ブロックのマージが、リスト・スケジューリングにより行われる、請求項7に記載のプログラム。
【請求項9】
コンピュータの処理により、コード化対象外ブロックと、コード化対象ブロックを含む複数のブロックを連結して構成されたコードを並列化するシステムであって、
記憶手段と、
前記記憶手段に保存された、DAGのタスク・グラフと、
前記タスク・グラフを、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む、直接−並列木に変換する手段と、
前記コード化対象外ブロックの上位に前記Pノードが存在しなくなるまで前記直接−並列木を別の直接−並列木に変形する手段とを有する、
コード並列化システム。
【請求項10】
前記タスク・グラフにおいて、前記コード化対象外ブロックをマージする手段をさらに含む、
請求項9に記載のコード並列化システム。
【請求項11】
前記コード化対象外ブロックのマージが、リスト・スケジューリングにより行われる、請求項10に記載のコード並列化システム。
【請求項12】
マルチプロセッサ環境と、
前記Pノードの下位の個々のノードをコード化する手段と、
該コード化されたコードを実行可能コードに個別にコンパイルする手段と、
前記実行可能コードを個々のプロセッサに割り当てて実行する手段をさらに有する、
請求項9に記載のコード並列化システム。
【請求項13】
前記コード化対象外ブロックのコードを実行するためのインタープリタをもつマルチプロセッサ環境と、
前記Pノードの下位の個々のノードをコード化する手段と、
該コード化されたコードが前記コード化対象外ブロックを含まないなら、実行可能コードに個別にコンパイルする手段と、
前記実行可能コードを個々のプロセッサに割り当てて実行する手段と、
前記コード化されたコードが前記コード化対象外ブロックを含むなら、前記コード化されたコードを前記インタープリタで実行する手段をさらに有する、
請求項9に記載のコード並列化システム。
【請求項1】
コンピュータの処理により、コード化対象外ブロックと、コード化対象ブロックを含む複数のブロックを連結して構成されたコードを並列化する方法であって、
前記コードを、DAGのタスク・グラフとして用意するステップと、
前記タスク・グラフを、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む、直接−並列木に変換するステップと、
前記コード化対象外ブロックの上位に前記Pノードが存在しなくなるまで前記直接−並列木を別の直接−並列木に変形するステップを有する、
コード並列化方法。
【請求項2】
前記直接−並列木に変換する前に、前記タスク・グラフにおいて、前記コード化対象外ブロックをマージするステップをさらに含む、
請求項1に記載のコード並列化方法。
【請求項3】
前記コード化対象外ブロックのマージが、リスト・スケジューリングにより行われる、請求項2に記載のコード並列化方法。
【請求項4】
請求項1のコード並列化方法で生成されたコードを、マルチプロセッサ環境で実行する方法であって、
前記Pノードの下位の個々のノードをコード化するステップと、
該コード化されたコードを実行可能コードに個別にコンパイルするステップと、
前記実行可能コードを個々のプロセッサに割り当てて実行するステップを有する、
コード並列実行方法。
【請求項5】
請求項1のコード並列化方法で生成されたコードを、前記コード化対象外ブロックのコードを実行するためのインタープリタをもつマルチプロセッサ環境で実行する方法であって、
前記Pノードの下位の個々のノードをコード化するステップと、
該コード化されたコードが前記コード化対象外ブロックを含まないなら、実行可能コードに個別にコンパイルするステップと、
前記実行可能コードを個々のプロセッサに割り当てて実行するステップと、
前記コード化されたコードが前記コード化対象外ブロックを含むなら、前記コード化されたコードを前記インタープリタで実行するステップを有する、
コード並列実行方法。
【請求項6】
コンピュータの処理により、コード化対象外ブロックと、コード化対象ブロックを含む複数のブロックを連結して構成されたコードを並列化するプログラムであって、
前記コンピュータに、
前記コードを、DAGのタスク・グラフとして用意するステップと、
前記タスク・グラフを、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む、直接−並列木に変換するステップと、
前記コード化対象外ブロックの上位に前記Pノードが存在しなくなるまで前記直接−並列木を別の直接−並列木に変形するステップを実行させる、
プログラム。
【請求項7】
前記直接−並列木に変換する前に、前記タスク・グラフにおいて、前記コード化対象外ブロックをマージするステップをさらに含む、
請求項6に記載のプログラム。
【請求項8】
前記コード化対象外ブロックのマージが、リスト・スケジューリングにより行われる、請求項7に記載のプログラム。
【請求項9】
コンピュータの処理により、コード化対象外ブロックと、コード化対象ブロックを含む複数のブロックを連結して構成されたコードを並列化するシステムであって、
記憶手段と、
前記記憶手段に保存された、DAGのタスク・グラフと、
前記タスク・グラフを、直列実行ノードがそこから分岐するSノードと、並列実行ノードがそこから分岐するPノードを含む、直接−並列木に変換する手段と、
前記コード化対象外ブロックの上位に前記Pノードが存在しなくなるまで前記直接−並列木を別の直接−並列木に変形する手段とを有する、
コード並列化システム。
【請求項10】
前記タスク・グラフにおいて、前記コード化対象外ブロックをマージする手段をさらに含む、
請求項9に記載のコード並列化システム。
【請求項11】
前記コード化対象外ブロックのマージが、リスト・スケジューリングにより行われる、請求項10に記載のコード並列化システム。
【請求項12】
マルチプロセッサ環境と、
前記Pノードの下位の個々のノードをコード化する手段と、
該コード化されたコードを実行可能コードに個別にコンパイルする手段と、
前記実行可能コードを個々のプロセッサに割り当てて実行する手段をさらに有する、
請求項9に記載のコード並列化システム。
【請求項13】
前記コード化対象外ブロックのコードを実行するためのインタープリタをもつマルチプロセッサ環境と、
前記Pノードの下位の個々のノードをコード化する手段と、
該コード化されたコードが前記コード化対象外ブロックを含まないなら、実行可能コードに個別にコンパイルする手段と、
前記実行可能コードを個々のプロセッサに割り当てて実行する手段と、
前記コード化されたコードが前記コード化対象外ブロックを含むなら、前記コード化されたコードを前記インタープリタで実行する手段をさらに有する、
請求項9に記載のコード並列化システム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【公開番号】特開2013−20580(P2013−20580A)
【公開日】平成25年1月31日(2013.1.31)
【国際特許分類】
【出願番号】特願2011−155616(P2011−155616)
【出願日】平成23年7月14日(2011.7.14)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MACHINES CORPORATION
【Fターム(参考)】
【公開日】平成25年1月31日(2013.1.31)
【国際特許分類】
【出願日】平成23年7月14日(2011.7.14)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MACHINES CORPORATION
【Fターム(参考)】
[ Back to top ]