(57)【要約】      （修正有）【課題】ブロック線図などで表されるプログラムを並列化する。【解決手段】ブロック線図において、内部状態をもたない機能ブロック１２１４、１２１６の出力が、内部状態をもつ機能ブロックAによって使用されるとき、機能ブロックAは、その内部状態をもたない機能ブロックの使用ブロックと呼ぶ。内部状態をもつ機能ブロックAの出力が、内部状態をもたない機能ブロックの入力として計算に使用されるとき、機能ブロックAは、その内部状態をもたない機能ブロックの定義ブロックと呼ぶ。各機能ブロックをノードとして訪問することにより、内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックとの接続関係に基づき、機能ブロック毎に、使用ブロック集合／定義ブロック集合の数を求め、その数に基づき、ストランド１２０２〜１２１２を割り当てる。これにより、ブロック線図を、ストランドに分けて処理を並列化する。【選択図】図１２
2011096107.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理により、内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックを連結して構成されたコードを並列化する方法であって、
前記機能ブロックをノードとし、前記機能ブロックの間の接続をリンクとするグラフ表現を作成して、前記コンピュータのメモリに格納するステップと、
前記グラフ表現上で前記ノードを順次訪問し、前記ノードが内部状態をもたない機能ブロックであることに応答して、該内部状態をもたない機能ブロックから内部状態をもつ機能ブロックへの入力を検出して該内部状態をもつ機能ブロックを使用ブロック集合として前記メモリに記憶し、内部状態をもつ機能ブロックから該内部状態をもたない機能ブロックへの入力を検出して該内部状態をもつ機能ブロックを定義ブロック集合として前記メモリに記憶するステップと、
前記機能ブロックに関連して記憶された前記使用ブロック集合の情報及び前記定義ブロック集合の情報に基づき、機能ブロックのストランドを形成するステップを有する、
コードを並列化する方法。
【請求項２】
前記グラフ表現上で前記ノードを順次訪問したときに、前記ノードが内部状態をもつ機能ブロックであることに応答して、前記ノードに関連して、前記ノード自身を、使用ブロック集合且つ定義ブロック集合として前記メモリに記憶するステップをさらに有する、請求項１に記載の方法。
【請求項３】
前記ストランドを形成するステップでは、下記の条件に従い前記ストランドが形成される、請求項１に記載の方法。
(1) 使用ブロック数 = 0で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する、使用ブロック数 = 0、定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(2) 使用ブロック数 = 0で、定義ブロック数 = 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(3) 使用ブロック数 = 0で、定義ブロック数 > 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(4) 使用ブロック数 = 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(5) 使用ブロック数 = 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。
(6) 使用ブロック数 = 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、使用ブロックと同じストランドに割り当てられる。
(7) 使用ブロック数 > 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数=0となるブロックと同じストランドに割り当てられる。
(8) 使用ブロック数 > 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。
(9) 使用ブロック数 > 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、重複して、使用ブロック集合の各使用ブロックのストランドに割り当てられる。
【請求項４】
マルチコアまたはマルチプロセッサの環境において、請求項１に記載の方法にさらに、前記ストランドを個別にコンパイルして実行可能コードを生成するステップと、前記生成された実行可能コードを、個別に前記コアまたはプロセッサに割り当てて実行させるステップを有する、並列化されたコードの実行方法。
【請求項５】
コンピュータの処理により、内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックを連結して構成されたコードを並列化するプログラムであって、
前記コンピュータをして、
前記機能ブロックをノードとし、前記機能ブロックの間の接続をリンクとするグラフ表現を作成して、前記コンピュータのメモリに格納するステップと、
前記グラフ表現上で前記ノードを順次訪問し、前記ノードが内部状態をもたない機能ブロックであることに応答して、該内部状態をもたない機能ブロックから内部状態をもつ機能ブロックへの入力を検出して該内部状態をもつ機能ブロックを使用ブロック集合として前記メモリに記憶し、内部状態をもつ機能ブロックから該内部状態をもたない機能ブロックへの入力を検出して該内部状態をもつ機能ブロックを定義ブロック集合として前記メモリに記憶するステップと、
前記機能ブロックに関連して記憶された前記使用ブロック集合の情報及び前記定義ブロック集合の情報に基づき、機能ブロックのストランドを形成するステップを実行させる、
コードを並列化するプログラム。
【請求項６】
前記グラフ表現上で前記ノードを順次訪問したときに、前記ノードが内部状態をもつ機能ブロックであることに応答して、前記ノードに関連して、前記ノード自身を、使用ブロック集合且つ定義ブロック集合として前記メモリに記憶するステップをさらに有する、請求項５に記載のプログラム。
【請求項７】
前記ストランドを形成するステップでは、下記の条件に従い前記ストランドが形成される、請求項５に記載のプログラム。
(1) 使用ブロック数 = 0で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する、使用ブロック数 = 0、定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(2) 使用ブロック数 = 0で、定義ブロック数 = 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(3) 使用ブロック数 = 0で、定義ブロック数 > 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(4) 使用ブロック数 = 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(5) 使用ブロック数 = 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。
(6) 使用ブロック数 = 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、使用ブロックと同じストランドに割り当てられる。
(7) 使用ブロック数 > 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数=0となるブロックと同じストランドに割り当てられる。
(8) 使用ブロック数 > 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。
(9) 使用ブロック数 > 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、重複して、使用ブロック集合の各使用ブロックのストランドに割り当てられる。
【請求項８】
マルチコアまたはマルチプロセッサの環境において、請求項５に記載のプログラムがさらに、前記ストランドを個別にコンパイルして実行可能コードを生成するステップと、前記生成された実行可能コードを、個別に前記コアまたはプロセッサに割り当てて実行させるステップを有する、プログラム。
【請求項９】
コンピュータの処理により、内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックを連結して構成されたコードを並列化するシステムであって、
前記コンピュータのメモリと、
前記機能ブロックをノードとし、前記機能ブロックの間の接続をリンクとするグラフ表現を作成して、前記コンピュータのメモリに格納する手段と、
前記グラフ表現上で前記ノードを順次訪問し、前記ノードが内部状態をもたない機能ブロックであることに応答して、該内部状態をもたない機能ブロックから内部状態をもつ機能ブロックへの入力を検出して該内部状態をもつ機能ブロックを使用ブロック集合として前記メモリに記憶し、内部状態をもつ機能ブロックから該内部状態をもたない機能ブロックへの入力を検出して該内部状態をもつ機能ブロックを定義ブロック集合として前記メモリに記憶する手段と、
前記機能ブロックに関連して記憶された前記使用ブロック集合の情報及び前記定義ブロック集合の情報に基づき、機能ブロックのストランドを形成する手段を有する、
コードを並列化するシステム。
【請求項１０】
前記グラフ表現上で前記ノードを順次訪問したときに、前記ノードが内部状態をもつ機能ブロックであることに応答して、前記ノードに関連して、前記ノード自身を、使用ブロック集合且つ定義ブロック集合として前記メモリに記憶する手段をさらに有する、請求項９に記載のシステム。
【請求項１１】
前記ストランドを形成する手段は、下記の条件に従い前記ストランドを形成する、請求項９に記載のシステム。
(1) 使用ブロック数 = 0で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する、使用ブロック数 = 0、定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(2) 使用ブロック数 = 0で、定義ブロック数 = 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(3) 使用ブロック数 = 0で、定義ブロック数 > 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(4) 使用ブロック数 = 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(5) 使用ブロック数 = 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。
(6) 使用ブロック数 = 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、使用ブロックと同じストランドに割り当てられる。
(7) 使用ブロック数 > 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数=0となるブロックと同じストランドに割り当てられる。
(8) 使用ブロック数 > 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。
(9) 使用ブロック数 > 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、重複して、使用ブロック集合の各使用ブロックのストランドに割り当てられる。
【請求項１２】
マルチコアまたはマルチプロセッサの環境において、請求項９に記載のシステムにさらに、前記ストランドを個別にコンパイルして実行可能コードを生成する手段と、前記生成された実行可能コードを、個別に前記コアまたはプロセッサに割り当てて実行させる手段を有する、並列化されたコードの実行システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、シミュレーション・システムにおいて、プログラムの実行を並列化により高速化する技法に関する。
【背景技術】
【０００２】
近年、科学技術計算、シミュレーションなどの分野で、複数のプロセッサをもつ、いわゆるマルチプロセッサ・システムが使用されている。そのようなシステムでは、アプリケーション・プログラムは、複数のプロセスを生成して、個別のプロセッサに、プロセスを割り当てる。それらのプロセッサは、例えば、共有のメモリ空間を利用して互いに通信しながら、処理を進める。
【０００３】
最近になって特に盛んに開発されるようになってきたシミュレーションの分野として、ロボット、自動車、飛行機などのメトカトロニクスのプラントのシミュレーション用ソフトウェアがある。電子部品とソフトウェア技術に発展の恩恵により、ロボット、自動車、飛行機などでは、神経のように張り巡らされたワイヤ結線や無線ＬＡＮなどを利用して、大部分の制御が電子的に行われる。
【０００４】
それらは、本来的には機械的装置であるのに、大量の制御ソフトウェアをも内蔵している。そのため、製品の開発に当たっては、制御プログラムの開発とそのテストに、長い時間と、膨大な費用と、多数の人員を費やす必要が出てきた。
【０００５】
このようなテストにために従来行われている技法として、ＨＩＬＳ(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)の機能により、等価な機能のＣ言語など既知のコンピュータ言語のソース・コードに変換することができる。このＣ言語のソース・コードをコンパイルすることにより、別のコンピュータ・システムで、ＳＩＬＳとして、シミュレーションを実行することができる。
【００１０】
図１は、典型的なMATLAB(R)/Simulink(R)の機能ブロックのループを模式的に示す図である。機能ブロックは大別して、内部状態をもつブロックと、内部状態をもたないブロックに分かれる。図１では、斜線をつけて示したブロックA、Bが内部状態をもつブロックであり、斜線をつけていないブロックa、b、cが、内部状態をもたないブロックである。
【００１１】
内部状態をもたないブロックでは、図２(a)に示すように、入力データから直ちに出力データが計算されて出力される。
【００１２】
一方、内部状態をもつブロックでは、図２(b)に示すように、前回の入力データに、ある所定の演算を施した値が内部データ２０２として保持され、出力データは、内部データ２０２をもちいて計算される。よって、今回の入力データは、今回の出力データの計算には使われず、次回の出力データの計算のために、今回の出力データの計算の完了後、内部データ２０２として保持される。
【００１３】
図１で示すブロック線図の構成の処理を、説明する。ここで、ブロックAの出力をf1、ブロックaの出力をf2、ブロックBの出力をf3、ブロックbの出力をf4、ブロックcの出力をf5とする。f1はブロックaに入力され、f2はブロックBに入力され、f3はブロックbに入力され、f4はブロックcに入力され、f5はブロックAに入力される。但し、ブロックAとブロックBは、内部状態をもつブロックなので、上述のように、各々、f1及びf3を計算するために、直接入力f5、f2を使うことはない。以上のことを擬似コードで書くと、以下のとおりである。
while (ts < EOS) {
// 出力
f1 = Aout(sA)
f2 = a(f1)
f3 = Bout(sB)
f4 = b(f3)
f5 = c(f4)
// 状態の更新
sA = Ain(f5)
sB = Bin(f2)
// 時間の更新
ts++
}
【００１４】
上記擬似コードは、時間tsが、EOS(シミュレーションの終わり)に達するまで、whileループを繰り返すことを示す。このコードで、Aout()は、ブロックAが内部状態に基づき出力を計算する関数、Ain()は、ブロックAが入力に基づき内部状態変数を計算する関数、a()は、ブロックaが入力に基づき、出力を計算する関数、等等である。
【００１５】
この擬似コードから見て取れるように、ブロックAは、出力を計算するのに、その内部状態を使い、ブロックaは、ブロックAの出力を使う。ここには、ブロックB、b、cの出力は使われていない。
【００１６】
一方、ブロックB、b、cも、ブロックA、aの出力を使用していない。このことは、A、aと、B、b、cをそれぞれ並列に実行できることを示唆する。図３に示すように、システムは、好適には異なるプロセッサまたはコアにそれぞれ、A、aとB、b、cの処理を割り当てて並列に実行した後、ブロックaの出力をブロックBに入力し、ブロックcの出力をブロックAに入力して次の並列実行に進む。すなわち、内部状態を持つブロックを終点とするフローを消去したときに、分断される各部分が１イテレーションに限り並列に実行可能となる。
【００１７】
ただし、単に内部状態を持つブロックを終点とするフローを消去しただけでは、十分にモデルを分割できないケース、すなわち並列化できないケースが多い。例えば、図１１のケースでは、結果的に全てのブロックが接続された状態で残り、まったく並列化できない。これは、複数のシグナルを統合する内部状態を持たないブロックが存在する場合に各部が分断されなくなるために発生する現象だが、多くのモデルにおいてこの傾向が強い。そのため、上記のような単純な方法だけでは高い並列性は期待できない。
【００１８】
特開２００３−９１４２２号公報は、多重ループ構造を有する非並列化ソースコードを複数のプロセッサが実行可能な並列化ソースコードに自動的に変換する方法に関し、ｎ（ｎは２以上の整数）重にネストされたループを含む非並列のソースコードから、ｍ（ｍは２以上の整数）個のプロセッサで並列実行可能な並列化ソースコードを自動的に生成する多重反復処理超並列化ソースコード自動生成プログラムＰ。非並列化ソースコードＳＣのｎ重ループそれぞれの初期値式を、ｍ個のプロセッサに与えた、各プロセッサを一意に識別する０から始まるｍ個の連続した整数ｉａｋ（ｋ＝０、・・・、ｍ−１）、およびループｊ（ｊ＝１、・・・、ｎ）毎に定められた増分値δｊを用いて表される初期値式Ｓｊに書き換え、書き換えた初期値式Ｓｊおよび増分値δｊを用いることにより、前記ｎ重ループ構造部分を、前記ｍ個のプロセッサで分担処理できる構造に変換する機能をＣＰＵに実現させることを開示する。
【００１９】
特開２００７−５１１８３５号公報は、ネットワークプロセッサをＤステージプロセッサパイプラインに構成し、シーケンシャルネットワークアプリケーションプログラムを複数のＤパイプラインステージに変換し、ＤパイプラインステージをＤステージプロセッサパイプライン内でパラレルに実行することを開示する。このとき例えば、シーケンシャルアプリケーションプログラムの変換は、シーケンシャルネットワークプログラムをフローネットワークモデルとしてモデリングし、複数の予備のパイプラインステージへとフローネットワークモデルから選択することによって実行される。
【００２０】
しかし、これらの従来技術は、ループをまたがって依存関係（loop carried dependence）を持つ機能ブロック間の、１イテレーション内での並列性を高める技法については、何も示唆しない。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００３−９１４２２号公報
【特許文献２】特開２００７−５１１８３５号公報
【発明の概要】
【発明が解決しようとする課題】
【００２２】
本発明の目的は、MATLAB(R)/Simulink(R)などのモデリング・ツールで作成された機能ブロックからなるプログラムを並列化する場合の並列性を高めることにある。
【課題を解決するための手段】
【００２３】
本発明は、上記目的を達成するためになされたものであり、内部状態をもたない各機能ブロックに、定義ブロック集合(definer)と、使用ブロック集合(user)の属性を付与することを特徴とする。
【００２４】
ある内部状態をもたない機能ブロックの出力が、ある内部状態をもつ機能ブロックAに
よって、直接・間接を問わず、他の内部状態を持つブロックを経由せずに使用されるとき、機能ブロックAは、その内部状態をもたない機能ブロックの使用ブロックと呼び、内部状態を持たない機能ブロックの使用ブロック集合の要素となる。
【００２５】
また、ある内部状態をもつ機能ブロックAの出力が、直接・間接を問わず、他の内部状態を持つブロックを経由せずに、ある内部状態をもたない機能ブロックの入力として計算に使用されるとき、機能ブロックAは、その内部状態をもたない機能ブロックの定義ブロックと呼び、定義ブロック集合の要素となる。
【００２６】
このような定義の下で、本発明に係るシステムは、ブロック線図をグラフとして、深さ優先探索、あるいは幅優先探索などの周知のアルゴリズムにより順次、すべての機能ブロックに亘って機能ブロックを訪問することによって、個々の内部状態をもたない機能ブロックについて、その定義ブロックと、使用ブロックを列挙する。
【００２７】
こうして、すべての内部状態をもたない機能ブロックについて、その定義ブロック集合と、使用ブロック集合が列挙されると、本発明に係るシステムは、再びブロック線図をグラフとして、すべての機能ブロックに亘って機能ブロックを訪問しながら、個々の機能ブロックについて、次のような方針で機能ブロックの集まりを形成する。すなわち、この発明では、そのような機能ブロックの集まりを特に、ストランド(strand)と呼ぶことにする。下記のルールによって得られるストランドは、元々存在する処理の依存関係を崩すことなく、シミュレーションの１回のイテレーション内で並列に実行することができる。これは、内部状態を持つブロックへの入力は、次の内部状態更新時に初めて使用されるという性質から、ある一つの内部状態を持つブロックにしか、その計算結果が利用されないようなブロックの計算は、内部状態を持つブロックの内部状態更新ロジックの一部と見なすことで、内部状態を持つブロックへの入力フロー以外も、依存関係を崩すことなく切断可能にしたことによる。
【００２８】
さて、ストランド作成のルールについて、より詳細に説明すると、個々の機能ブロックについて、関連する使用ブロック集合の要素数（使用ブロック数）と、定義ブロック集合の要素数（定義ブロック数）に基づき、次の条件に従い、ストランドに振り分けられる。
(1) 使用ブロック数 = 0で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する、使用ブロック数 = 0、定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(2) 使用ブロック数 = 0で、定義ブロック数 = 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(3) 使用ブロック数 = 0で、定義ブロック数 > 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(4) 使用ブロック数 = 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(5) 使用ブロック数 = 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。ただし、
後で負荷バランスのために、割当てし直すことがある。
(6) 使用ブロック数 = 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、使用ブロックと同じストランドに割り当てられる。
(7) 使用ブロック数 > 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数=0となるブロックと同じストランドに割り当てられる。
(8) 使用ブロック数 > 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。
(9) 使用ブロック数 > 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、重複して、使用ブロック集合の各使用ブロックのストランドに割り当てられる。
【００２９】
このようにして、機能ブロックのストランドが得られると、各々のストランドは、対応するＣなどのソースコードに変換され、さらにコンパイルされて実行のため、個別のコアまたはプロセッサに割り当てられる。
【発明の効果】
【００３０】
この発明によれば、内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックの接続関係に基づき、各機能ブロック毎に使用ブロック集合／定義ブロック集合を求め、その要素数に基づき、ストランドを割り当てるようにしたことにより、従来並列化が困難であったようなブロック線図も、ストランドに分けて処理を並列化することが可能になる。
【図面の簡単な説明】
【００３１】
【図１】内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックからなるループのブロック線図の例を示す図である。
【図２】内部状態をもつ機能ブロックと、内部状態をもたない機能ブロックの仕組みをそれぞれ示す図である。
【図３】ブロック線図の並列化の例を示す図である。
【図４】本発明を実施するためのハードウェアのブロック図である。
【図５】本発明を実施するための機能ブロック図である。
【図６】本発明の処理全体の概要フローチャートを示す図である。
【図７】定義ブロック集合を見出す処理のフローチャートを示す図である。
【図８】使用ブロック集合を見出す処理のフローチャートを示す図である。
【図９】ストランド形成処理のフローチャートを示す図である。
【図１０】ストランド形成処理のルールを示す図である。
【図１１】ブロック線図のグラフにつき、定義ブロック集合と使用ブロック集合を見出す例を示す図である。
【図１２】見出された定義ブロック集合と使用ブロック集合に基づき、ストランドを形成する処理の結果を示す図である。
【発明を実施するための形態】
【００３２】
以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。
【００３３】
先ず、図４を参照して、本発明を実施するために使用されるコンピュータのハードウェアについて説明する。図４において、ホスト・バス４０２には、複数のＣＰＵ１  ４０４ａ、ＣＰＵ２  ４０４ｂ、ＣＰＵ３  ４０４ｃ、・・・ＣＰＵｎ  ４０４ｎが接続されている。ホスト・バス４０２にはさらに、ＣＰＵ１  ４０４ａ、ＣＰＵ２  ４０４ｂ、ＣＰＵ３  ４０４ｃ、・・・ＣＰＵｎ  ４０４ｎの演算処理のためのメイン・メモリ４０６が接続されている。
【００３４】
一方、Ｉ／Ｏバス４０８には、キーボード４１０、マウス４１２、ディスプレイ４１４及びハードティスク・ドライブ４１６が接続されている。Ｉ／Ｏバス４０８は、Ｉ／Ｏブリッジ４１８を介して、ホスト・バス４０２に接続されている。キーボード４１０及びマウス４１２は、オペレータが、コマンドを打ち込んだり、メニューをクリックするなどして、操作するために使用される。ディスプレイ４１４は、必要に応じて、後述する本発明に係るプログラムをＧＵＩで操作するためのメニューを表示するために使用される。
【００３５】
この目的のために使用される好適なコンピュータ・システムのハードウェアとして、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｘがある。その際、ＣＰＵ１  ４０４ａ、ＣＰＵ２  ４０４ｂ、ＣＰＵ３  ４０４ｃ、・・・ＣＰＵｎ  ４０４ｎは、例えば、インテル（Ｒ）Ｘｅｏｎ（Ｒ）であり、オペレーティング・システムは、Ｗｉｎｄｏｗｓ（商標）Ｓｅｒｖｅｒ  ２００３である。オペレーティング・システムは、ハードティスク・ドライブ４１６に格納され、コンピュータ・システムの起動時に、ハードティスク・ドライブ４１６からメイン・メモリ４０６に読み込まれる。
【００３６】
本発明を実施するためには、マルチプロセッサ・システムを用いることが必要である。ここでマルチプロセッサ・システムとは、一般に、独立に演算処理し得るプロセッサ機能のコアを複数もつプロセッサを用いるシステムを意図しており、従って、マルチコア・シングルプロセッサ・システム、シングルコア・マルチプロセッサ・システム、及びマルチコア・マルチプロセッサ・システムのどれかでよいことを理解されたい。
【００３７】
なお、本発明を実施するために使用可能なコンピュータ・システムのハードウェアは、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｘに限定されず、本発明のシミュレーション・プログラムを走らせることができるものであれば、任意のコンピュータ・システムを使用することができる。オペレーティング・システムも、Ｗｉｎｄｏｗｓ（Ｒ）に限定されず、Ｌｉｎｕｘ（Ｒ）、Ｍａｃ  ＯＳ（Ｒ）など、任意のオペレーティング・システムを使用することができる。さらに、シミュレーション・プログラムを高速で動作させるために、ＰＯＷＥＲ（商標）６ベースで、オペレーティング・システムがＡＩＸ（商標）のＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｐなどのコンピュータ・システムを使用してもよい。
【００３８】
ハードティスク・ドライブ４１６にはさらに、MATLAB(R)/Simulink(R)、Ｃコンパイラまたは、Ｃ＋＋コンパイラ、後述する本発明に係る解析、ストランド作成のためのモジュール、ＣＰＵ割り当て用コード生成モジュールなどが格納されており、オペレータのキーボードやマウス操作に応答して、メイン・メモリ４０６にロードされて実行される。
【００３９】
尚、使用可能なシミュレーション・モデリング・ツールは、MATLAB(R)/Simulink(R)に限定されず、オープンソースのScilab/Scicosなど任意のシミュレーション・モデリング・ツールを使用することが可能である。
【００４０】
あるいは、場合によっては、シミュレーション・モデリング・ツールを使わず、直接、Ｃ、Ｃ＋＋などでシミュレーション・システムのソース・コードを書くことも可能であり、その場合にも、個々の機能が、互いに依存関係にある個別の機能ブロックとして記述できるなら、本発明は適用可能である。
【００４１】
図５は、本発明の実施例に係る機能ブロック図である。各々のブロックは、基本的に、ハードティスク・ドライブ４１６に格納されているモジュールに対応する。
【００４２】
図５において、シミュレーション・モデリング・ツール５０２は、MATLAB(R)/Simulink(R)、Scilab/Scicosなどの既存の任意のモデリング・ツールを使用することができる。シミュレーション・モデリング・ツール５０２は、基本的には、オペレータが、ディスプレイ４１４上でＧＵＩ的に機能ブロックを配置し、数式など必要な属性を記述し、必要に応じて、機能ブロック間を関連付けてブロック線図を記述することを可能ならしめるような機能をもつ。シミュレーション・モデリング・ツール５０２はさらに、記述されたブロック線図に等価な機能を記述するＣのソースコードを出力する機能をもつ。Ｃ以外にも、Ｃ＋＋、ＦＯＲＴＲＡＮなどを使用することができる。特に、ＭＤＬファイルは、Simulink(R)独自のフォーマットであり、機能ブロック間の依存関係を記述するために、ＭＤＬファイルを生成することができる。
【００４３】
なお、シミュレーション・モデリング・ツールは、別のパーソナル・コンピュータに導入して、そこで生成されたソース・コードを、ネットワークなどを経由して、ハードティスク・ドライブ４１６にダウンロードするようにすることもできる。
【００４４】
こうして出力されたソース・コード５０４は、ハードティスク・ドライブ４１６に保存される。なお、ソース・コード５０４以外に、機能ブロック間の依存関係を記述するためのＭＤＬファイルを保存してもよい。
【００４５】
解析モジュール５０６は、ソースコード５０４を入力して構文解析し、ブロックのつながりを、グラフ表現に変換する。グラフ表現のデータは、好適には、ハードディスク・ドライブ４１６に格納される。なお、コンピュータ上のグラフ表現のデータ構造は周知であるので、ここでは説明を省略する。
【００４６】
ストランド作成モジュール５０８は、解析モジュール５０６によって作成されたグラフ表現５０８を読み取って、内部状態をもたない機能ブロックの各々に関連して、内部状態を有する定義ブロック(definer)と、内部状態を有する使用ブロック(user)を決定し、その情報に基づき、ストランドを作成する。ストランド作成モジュール５０８のより詳しい処理は、後述する。
【００４７】
コード生成モジュール５１０は、ストランド作成モジュール５０８が生成したストランドの情報に基づき、コンパイラ５１２がコンパイルするためのソースコードを生成する。コンパイラ５１２が想定するプログラミング言語としては、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ（商標）などのマルチコア、またはマルチプロセッサに対応したプログラミングが可能な任意のプログラミング言語を使用することができ、コード生成モジュール５１０はそれに対応して、クラスタ毎に、ソースコードを生成することになる。
【００４８】
コンパイラ５１２が生成したクラスタ毎の実行可能バイナリ・コード（図示しない）は、好適にはストランド毎に、異なるコアまたはプロセッサに割り当てられて、オペレーティング・システムの作用により、実行環境５１４で実行される。
【００４９】
次に、図６以下のフローチャートを参照して、ストランド作成モジュール５０８の処理について説明する。図６において、ストランド作成モジュール５０８は、ステップ６０２で、ブロック線図のグラフ表現において、定義ブロックを見つける処理を行う。この処理は、後で図７のフローチャートを参照して、より詳細に説明する。
【００５０】
次に、ストランド作成モジュール５０８は、ステップ６０４で、ブロック線図のグラフ表現において、定義ブロックを見つける処理を行う。この処理は、後で図８のフローチャートを参照して、より詳細に説明する。
【００５１】
次に、ストランド作成モジュール５０８は、ステップ６０６で、ステップ６０２とステップ６０４で得られた情報をもとに、ストランドを作成する。この処理は、後で図９のフローチャートを参照して、より詳細に説明する。
【００５２】
図７は、ノード（機能ブロック）nに関して、定義ブロックを見つける、FindDefiners(n)の処理を示すフローチャートである。図７において、ステップ７０２では、ノードnに対して、空のノード集合Dnが用意される。
【００５３】
ステップ７０４では、ノードnの未処理の親ノードのうちの１つををnparentとする。
【００５４】
ステップ７０６では、ノードnparentが内部状態をもつブロックかどうかが判断され、もしそうなら、ステップ７０８で、Dnにnparentが加えられる。
【００５５】
ステップ７０６で、ノードnparentが内部状態をもたないブロックであると判断したなら、ステップ７１０で、FindDefiners(nparent)が再帰的に呼び出され、返されるノード集合の全要素がDnに加えられる。
【００５６】
次に、ステップ７０８とステップ７１０のどちらからも、ステップ７１２に進み、そこで、ノードnの全ての親ノードに対して処理が行われたかどうか判断され、そうでなければ、ステップ７０４に戻る。
【００５７】
ステップ７１２で、ノードnの全ての親ノードに対して処理が行われたと判断されると、ステップ７１４で、Dnを返して、FindDefiners(n)の処理を終わる。
【００５８】
図６のステップ６０２では、ストランド作成モジュール５０８が、ブロック線図のグラフの全てのノードを順次訪問して、ノードnが内部状態をもたないブロックである場合に、図７のFindDefiners(n)を適用し、返されたDnを、ノードnの定義ブロック集合として得る。また、ノードnが内部状態を持つブロックである場合には、ノードn自身を自身の空のブロック集合Dnに入れ、定義ブロック集合とする。各ノードnに対して得られた定義ブロック集合Dnおよびそれらの対応関係を、好適にはメイン・メモリ４０６に保存する。
【００５９】
図８は、ノード（機能ブロック）nに関して、使用ブロックを見つける、FindUsers(n)の処理を示すフローチャートである。図８において、ステップ８０２では、ノードnに対して、空のノード集合Unが用意される。
【００６０】
ステップ８０４では、ノードnの未処理の子ノードをnchildとする。
【００６１】
ステップ８０６では、ノードnchildが内部状態をもつブロックかどうかが判断され、もしそうなら、ステップ８０８で、Unにnchildが加えられる。
【００６２】
ステップ８０６で、ノードnchildが内部状態をもたないブロックであると判断したなら、ステップ７１０で、FindUsers(nchild)が再帰的に呼び出され、返されるノード集合の全要素がUnに加えられる。
【００６３】
次に、ステップ８０８とステップ８１０のどちらからも、ステップ８１２に進み、そこで、ノードnの全ての子ノードに対して処理が行われたかどうか判断され、そうでなければ、ステップ８０４に戻る。
【００６４】
ステップ８１２で、ノードnの全ての子ノードに対して処理が行われたと判断されると、ステップ８１４で、Unを返して、FindUsers(n)の処理を終わる。
【００６５】
図６のステップ６０４では、ストランド作成モジュール５０８が、ブロック線図のグラフの全てのノードを順次訪問して、ノードnが内部状態をもたないブロックである場合に、図８のFindDeUsers(n)を適用し、返されたUnを使用ブロック集合としてノードnに関連付けて、Unの内容とそれに対するリンクの情報を、好適にはメイン・メモリ４０６に保存する。また、ノードnが内部状態を持つブロックである場合には、ノードn自身を自身の空のブロック集合Unに入れ、使用ブロック集合とする。各ノードnに対して得られた使用ブロック集合Dnおよびそれらの対応関係を、好適にはメイン・メモリ４０６に保存する。
【００６６】
次に、図９のフローチャートを参照して、ストランド作成処理について説明する。この処理は、図６のステップ６０６に対応する。なお、図９のフローチャートの処理を実行する時点でステップ６０２と６０４の処理で、ブロックnには既に、定義ブロック集合Dnと使用ブロック集合Unが関連付けられていることを理解されたい。
【００６７】
図９において、ステップ９０２では、ストランド作成モジュール５０８が、ブロック線図のグラフ表現の次のノードnを訪問する。このときノードの訪問順序は特に問わず、最初のステップでは、任意のノードnが選択される。
【００６８】
次にステップ９０４に進み、そこで、DnとUnの情報を用いるルールに従い、ストランド形成処理を行う。
【００６９】
図１０に、そのルールまたは条件を示す。図示されているようにこれは、Unの要素の数である使用ブロック数と、Dnの要素の数である定義ブロック数に依存して、下記のような処理を行うものである。
(1) 使用ブロック数 = 0で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する、使用ブロック数 = 0、定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(2) 使用ブロック数 = 0で、定義ブロック数 = 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(3) 使用ブロック数 = 0で、定義ブロック数 > 1:
この場合は、その機能ブロックは、隣接する使用ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(4) 使用ブロック数 = 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数 = 0となるブロックと同じストランドに割り当てられる。
(5) 使用ブロック数 = 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。ただし、
後で負荷バランスのために、割当てし直すことがある。
(6) 使用ブロック数 = 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、使用ブロックと同じストランドに割り当てられる。
(7) 使用ブロック数 > 1で、定義ブロック数 = 0:
この場合は、その機能ブロックは、隣接する定義ブロック数=0となるブロックと同じストランドに割り当てられる。
(8) 使用ブロック数 > 1で、定義ブロック数 = 1:
この場合は、その機能ブロックは、定義ブロックと同じストランドに割り当てられる。
(9) 使用ブロック数 > 1で、定義ブロック数 > 1:
この場合は、その機能ブロックは、重複して、使用ブロック集合の各使用ブロックのストランドに割り当てられる。
【００７０】
このような複数の条件は、実際は、例えば：
if ( 定義ブロック数 == 0 && 使用ブロック数 == 0  ) { 
処理;
}  else if (  定義ブロック数 == 1 && 使用ブロック数 == 0  ) { 
処理;
}
・・・
のようなステートメントで記述することができる。
【００７１】
ステップ９０４で上記のストランド割当てを行うと、ステップ９０６では、ストランド作成モジュール５０８は、すべてのノードを訪問したかどうかを判断し、もしそうなら処理を終了し、そうでないなら、ステップ９０２に戻る。
【００７２】
このようにして作成された複数のストランドは、各々コンパイラ５１２でコンパイルされて、実行環境５１４で、好適には、個々のＣＰＵ１〜ＣＰＵｎに割り当てられて並列実行される。
【００７３】
図１１は、あるブロック線図にステップ６０２とステップ６０４を適用した結果を示す図である。図１１で、影線付きでA、B、C、Dなどと書かれているのが内部状態をもつブロックであり、白抜きのブロックが内部状態をもたないブロックである。
【００７４】
ステップ６０２とステップ６０４を適用した結果、各々の内部状態をもつブロックには、定義ブロック集合／使用ブロック集合として、０個以上の内部状態をもつブロックの関連性が計算される。
【００７５】
次に、ステップ６０６、すなわち図９のフローチャートの処理を、図１１のブロック線図のグラフに適用することで、図１２に示すようなストランド１２０２、１２０４、１２０６、１２０８、１２１０及び１２１２が形成される。特に、定義／使用ブロック集合 = A,D/A,B及び、定義／使用ブロック集合 = A,B/C,Bのように、定義ブロック集合と使用ブロック集合に各々複数のブロックが存在する場合は、複数のストランドによって共有されることに留意されたい。例えば、ブロック１２１４が、ストランド１２０４と、ストランド１２０６によって共有され、ブロック１２１６が、ストランド１２０８と、ストランド１２１０によって共有される、等である。
【００７６】
ここで作成されたストランドは、ＣＰＵに割り付けられて実行されることとなる。各ストランドを一つのＣＰＵに割り付けて全てを並列に（ただし、シミュレーションの各イテレーション毎に同期処理を要する）実行しても良いが、好適には、ＣＰＵ間の通信コストや利用可能なＣＰＵ数などを鑑み、いくつかのストランドからなるストランド集合を複数作成し、各ストランド集合を個別のＣＰＵに割り当てるなどする。
【００７７】
このとき、上記で共有されたブロックを含むストランドが、別のＣＰＵに割り当てられた場合、その共有されたブロックに対応する処理は、各々のＣＰＵで実行される（つまり処理が異なる複数のＣＰＵ上で重複して実行される）ことになる。
【００７８】
また、上記のように、複数のストランドまとめてストランド集合として一つのＣＰＵに割り当てて実行した場合、ストランド集合内の各ストランドの実行順序は任意でよく、他のストランド集合に所属するストランドから入力が必要なストランドをなるべく後に、他のストランド集合に所属するストランドに出力を与えるストランドをなるべく早く実行することで、ストランド集合（つまりＣＰＵ）をまたがってやり取りされるデータの準備ができてから、それが実際に必要となるまでの時間的間隔を拡大し、その間にシミュレーションの処理の裏で通信（例えばソフトウェアプリフェッチなど）を行い、プロセッサ間の通信遅延を隠蔽することもできる。
【００７９】
以上、この発明を特定の実施例に基づき説明してきたが、この発明は、この特定の実施例に限定されず、当業者が自明に思いつく様々な変形、置換などの構成、技法適用可能であることを理解されたい。例えば、特定のプロセッサのアーキテクチャ、オペレーティング・システムなどに限定されない。
【００８０】
また、上記実施例は、MATLAB(R)/Simulink(R)を例にとって説明したが、これに限らず、任意のモデリング・ツールに適用可能であることを理解されたい。
【符号の説明】
【００８１】
４０２  ホスト・バス
４０４ａ、４０４ｂ、・・・４０４ｎ  ＣＰＵ
４０６  メイン・メモリ
４０８  バス
４１０  キーボード
４１２  マウス
４１４  ディスプレイ
４１６  ハードティスク・ドライブ
５０２  シミュレーション・モデリング・ツール
５０４  ソース・コード
５０６  解析モジュール
５０４  ソースコード
５０８  ストランド作成モジュール
５１０  コード生成モジュール
５１２  コンパイラ
５１４  実行環境
１２０２〜１２１０  ストランド
【図１】
2011096107.tif 000003
【図２】
2011096107.tif 000004
【図３】
2011096107.tif 000005
【図４】
2011096107.tif 000006
【図５】
2011096107.tif 000007
【図６】
2011096107.tif 000008
【図７】
2011096107.tif 000009
【図８】
2011096107.tif 000010
【図９】
2011096107.tif 000011
【図１０】
2011096107.tif 000012
【図１１】
2011096107.tif 000013
【図１２】
2011096107.tif 000014