(57)【要約】  マルチプロセッサ・システムにおいて、並列化により、プログラムの実行を高速化する技法を提供するために、高速化したいプログラムのクリティカル・パスを適切にカットして、別プロセスとして分けて、個別のプロセッサに割り当てるようにする。  本発明の処理プログラムは、複数の処理ブロックからなる高速化したいプログラムのソース・コードを読み込んで、クリティカル・パスの可能なカットを全てテストして、結果のカットされたの処理ブロックの流れの処理時間が一番短くなるカットを見出す。これによって、複数の処理ブロックの群が得られる。こうして分割生成された個別のブロック・チャンクはコンパイルされて、実行環境で個別のプロセッサに各々割り当てられる。
2010047174.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理によって、マルチプロセッサ・システムで並列実行可能とするためのソース・コードを生成する方法であって、
プログラムのソース・コードを入力するステップと、
前記コンピュータの処理によって、前記プログラムのソース・コードの処理のクリティカル・パスを見つけるステップと、
前記クリティカル・パスをカットして、前記マルチプロセッサ・システムの個々のプロセッサ毎に対応して前記ソース・コードを分割するステップを有する、
ソース・コード処理方法。
【請求項２】
前記ソース・コードをコンパイルして実行し、前記ソース・コードの処理ブロック単位の処理時間を計測して記録するステップをさらに有し、
前記ソース・コードを分割するステップは、前記記録された処理時間を用いて、分割されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が、少なくとも元のソース・コードの処理時間より短くなるように分割を行う、請求項１の方法。
【請求項３】
処理が異なるプロセッサにまたがった際のメッセージングのコスト、投機実行のために必要な処理、、投機が失敗した際のロールバックのコスト、及び各ブロックへの入力の予測がどの程度当たるのかという投機成功確率のデータを更に計測して記録するステップを有する、請求項２の方法。
【請求項４】
前記ソース・コードを分割するステップは、前記記録された処理時間を用いて、分割されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が最小になるように分割を行う、請求項２の方法。
【請求項５】
前記分割されたソース・コードの間の変数及び引数の依存関係の情報を含む情報を出力するステップをさらに有する、請求項１の方法。
【請求項６】
前記マルチプロセッサ・システムのプロセッサの個数と、前記分割されたソース・コードの個数を比較し、前記分割されたソース・コードの個数がプロセッサの個数よりも多いことに応答して、前記分割されたソース・コードの個数がプロセッサの個数と等しいかそれ以下になるように、前記分割されたソース・コードを結合するステップをさらに有する、請求項２の方法。
【請求項７】
前記分割されたソース・コードを結合するステップは、前記記録された処理時間を用いて、結合されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が最小になるように結合を行う、請求項６の方法。
【請求項８】
前記ソース・コードは、シミュレーション・モデリング・ツールの機能により生成されたものであり、前記ソース・コードの処理ブロック単位は、シミュレーション・モデリング・ツール上のブロック線図のブロックに対応する、請求項１の方法。
【請求項９】
コンピュータの処理によって、マルチプロセッサ・システムで並列実行可能とするための複数のソース・コードを生成するシステムであって、
プログラムのソース・コードを保存する記録手段と、
前記コンピュータの処理によって、前記プログラムのソース・コードを読み取って、該ソース・コードの処理のクリティカル・パスを見つける手段と、
前記クリティカル・パスをカットして、前記マルチプロセッサ・システムの個々のプロセッサ毎に対応して前記ソース・コードを分割する手段を有する、
ソース・コード処理システム。
【請求項１０】
前記ソース・コードをコンパイルして実行し、前記ソース・コードの処理ブロック単位の処理時間を計測して記録する手段をさらに有し、
前記ソース・コードを分割する手段は、前記記録された処理時間を用いて、分割されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が、少なくとも元のソース・コードの処理時間より短くなるように分割を行う、請求項９のシステム。
【請求項１１】
前記処理時間を計測して記録する手段は、処理が異なるプロセッサにまたがった際のメッセージングのコスト、投機実行のために必要な処理、投機が失敗した際のロールバックのコスト、及び各ブロックへの入力の予測がどの程度当たるのかという投機成功確率のデータを更に計測して記録する、請求項１０のシステム。
【請求項１２】
前記ソース・コードを分割するシステムは、前記記録された処理時間を用いて、分割されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が最小になるように分割を行う、請求項１０のシステム。
【請求項１３】
前記分割されたソース・コードの間の変数及び引数の依存関係の情報を含む情報を出力する手段をさらに有する、請求項９のシステム。
【請求項１４】
前記マルチプロセッサ・システムのプロセッサの個数と、前記分割されたソース・コードの個数を比較し、前記分割されたソース・コードの個数がプロセッサの個数よりも多いことに応答して、前記分割されたソース・コードの個数がプロセッサの個数と等しいかそれ以下になるように、前記分割されたソース・コードを結合する手段をさらに有する、請求項１０のシステム。
【請求項１５】
前記分割されたソース・コードを結合する手段は、前記記録された処理時間を用いて、結合されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が最小になるように結合を行う、請求項１４のシステム。
【請求項１６】
前記ソース・コードは、シミュレーション・モデリング・ツールの機能により生成されたものであり、前記ソース・コードの処理ブロック単位は、シミュレーション・モデリング・ツール上のブロック線図のブロックに対応する、請求項９のシステム。
【請求項１７】
マルチプロセッサ・システムにより並列実行可能な複数のプログラムを実行するコンピュータ・システムであって、
プログラムのソース・コードを保存する記録手段と、
前記コンピュータの処理によって、前記プログラムのソース・コードを読み取って、該ソース・コードの処理のクリティカル・パスを見つける手段と、
前記クリティカル・パスをカットして、前記マルチプロセッサ・システムの個々のプロセッサ毎に対応して前記ソース・コードを分割する手段と、
前記分割されたソース・コードをコンパイルする手段と、
前記コンパイルされた実行可能プログラムを、前記マルチプロセッサ・システムの個別のプロセッサに割り当てる手段を有する、
コンピュータ・システム。
【請求項１８】
前記ソース・コードをコンパイルして実行し、前記ソース・コードの処理ブロック単位の処理時間を計測して記録する手段をさらに有し、
前記ソース・コードを分割する手段は、前記記録された処理時間を用いて、分割されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が、少なくとも元のソース・コードの処理時間より短くなるように分割を行う、請求項１７のコンピュータ・システム。
【請求項１９】
前記処理時間を計測して記録する手段は、処理が異なるプロセッサにまたがった際のメッセージングのコスト、投機実行のために必要な処理、投機が失敗した際のロールバックのコスト、及び各ブロックへの入力の予測がどの程度当たるのかという投機成功確率のデータを更に計測して記録する、請求項１８のコンピュータ・システム。
【請求項２０】
前記ソース・コードを分割するシステムは、前記記録された処理時間を用いて、分割されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が最小になるように分割を行う、請求項１８のコンピュータ・システム。
【請求項２１】
前記分割されたソース・コードの間の変数及び引数の依存関係の情報を含む情報を出力する手段と、
該依存関係の情報を、前記マルチプロセッサ・システムの個別のプロセッサが参照可能となるようにロードする手段、
をさらに有する、請求項１７のコンピュータ・システム。
【請求項２２】
前記マルチプロセッサ・システムのプロセッサの個数と、前記分割されたソース・コードの個数を比較し、前記分割されたソース・コードの個数がプロセッサの個数よりも多いことに応答して、前記分割されたソース・コードの個数がプロセッサの個数と等しいかそれ以下になるように、前記分割されたソース・コードを結合する手段をさらに有する、請求項１７のコンピュータ・システム。
【請求項２３】
コンピュータの処理によって、マルチプロセッサ・システムで並列実行可能とするためのソース・コードを生成するプログラムであって、
前記コンピュータに、
プログラムのソース・コードを入力するステップと、
前記コンピュータの処理によって、前記プログラムのソース・コードの処理のクリティカル・パスを見つけるステップと、
前記クリティカル・パスをカットして、前記マルチプロセッサ・システムの個々のプロセッサ毎に対応して前記ソース・コードを分割するステップを実行させる、
プログラム。
【請求項２４】
前記ソース・コードをコンパイルして実行し、前記ソース・コードの処理ブロック単位の処理時間を計測して記録するステップをさらに有し、
前記ソース・コードを分割するステップは、前記記録された処理時間を用いて、分割されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が、少なくとも元のソース・コードの処理時間より短くなるように分割を行う、請求項２３のプログラム。
【請求項２５】
処理が異なるプロセッサにまたがった際のメッセージングのコスト、投機実行のために必要な処理、、投機が失敗した際のロールバックのコスト、及び各ブロックへの入力の予測がどの程度当たるのかという投機成功確率のデータを更に計測して記録するステップを有する、請求項２４のプログラム。
【請求項２６】
前記ソース・コードを分割するステップは、前記記録された処理時間を用いて、分割されたソース・コードのうちの期待される処理時間が最大のものの期待される処理時間が最小になるように分割を行う、請求項２４のプログラム。
【請求項２７】
前記マルチプロセッサ・システムのプロセッサの個数と、前記分割されたソース・コードの個数を比較し、前記分割されたソース・コードの個数がプロセッサの個数よりも多いことに応答して、前記分割されたソース・コードの個数がプロセッサの個数と等しいかそれ以下になるように、前記分割されたソース・コードを結合するステップをさらに有する、請求項２４のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、マルチプロセッサ・システムにおいて、プログラムの実行を高速化する技法に関する。
【背景技術】
【０００２】
近年、科学技術計算、シミュレーションなどの分野で、複数のプロセッサをもつ、いわゆるマルチプロセッサ・システムが使用されている。そのようなシステムでは、アプリケーション・プログラムは、複数のプロセスを生成して、個別のプロセッサに、プロセスを割り当てる。それらのプロセッサは、例えば、共有のメモリ空間を利用して互いに通信しながら、処理を進める。【０００３】
最近になって特に盛んに開発されるようになってきたシミュレーションの分野として、ロボット、自動車、飛行機などのメトカトロニクスのプラントのシミュレーション用ソフトウェアがある。電子部品とソフトウェア技術に発展の恩恵により、ロボット、自動車、飛行機などでは、神経のように張り巡らされたワイヤ結線や無線ＬＡＮなどを利用して、大部分の制御が電子的に行われる。【０００４】
それは、本来的には機械的装置であるのに、大量の制御ソフトウェアを内蔵することを意味する。そのため、製品の開発に当たっては、制御プログラムの開発とそのテストに、長い時間と、膨大な費用と、多数の人員を費やす必要が出てきた。【０００５】
このようなテストにために従来行われている技法として、ＨＩＬＳ(Hardware In the Loop Simulation)がある。特に、自動車全体の電子制御ユニット（ＥＣＵ）をテストする環境は、フルビークルＨＩＬＳと呼ばれる。フルビークルＨＩＬＳにおいては、実験室内で、本物のＥＣＵが、エンジン、トランスミッション機構などをエミュレーションする専用のハードウェア装置に接続され、所定のシナリオに従って、テストが行われる。ＥＣＵからの出力は、監視用のコンピュータに入力され、さらにはディスプレイに表示されて、テスト担当者がディスプレイを眺めながら、異常動作がないかどうか、チェックする。【０００６】
しかし、ＨＩＬＳは、専用のハードウェア装置を使い、それと本物のＥＣＵの間を物理的に配線しなくてはならないので、準備が大変である。また、別のＥＣＵに取り替えてのテストも、物理的に接続し直さなくてはならないので、手間がかかる。さらに、本物のＥＣＵを用いたテストであるため、テストに実時間を要する。従って、多くのシナリオをテストすると、膨大な時間がかかる。また、ＨＩＬＳのエミュレーション用のハードウェア装置は、一般に、非常に高価である。【０００７】
そこで近年、高価なエミュレーション用ハードウェア装置を使うことなく、ソフトウェアで構成する手法が提案されている。この手法は、ＳＩＬＳ(Software In the Loop Simulation)と呼ばれ、ＥＣＵに搭載されるマイクロコンピュータ、入出力回路、制御のシナリオ、エンジンやトランスミッションなどのプラントを全て、ソフトウェア・シミュレータで構成する技法である。これによれば、ＥＣＵのハードウェアが存在しなくても、テストを実行可能である。【０００８】
このようなＳＩＬＳの構築を支援するシステムとして例えば、CYBERNET SYSTEMS CO.,LTD.から入手可能なシミュレーション・モデリング・システムである、MATLAB(R)/Simulink(R)がある。MATLAB(R)/Simulink(R)を使用すると、図１に示すように、画面上にグラフィカル・インターフェースによって、機能ブロックA,B,...,Jを配置し、矢印のようにその処理の流れを指定することによって、シミュレーション・プログラムを作成することができる。【０００９】
こうして、MATLAB(R)/Simulink(R)上で、機能ブロックA,B,...,Jなどのブロック線図が作成されると、Real-Time Workshop(R)の機能により、等価な機能のＣ言語のソース・コードに変換することができる。このＣ言語のソース・コードをコンパイルすることにより、別のコンピュータ・システムで、ＳＩＬＳとして、シミュレーションを実行することができる。【００１０】
特に、別のコンピュータ・システムが、マルチプロセッサ・システムである場合、可能限り、処理を分割して、個別のプロセッサに、別々のプロセスを割り当てて並列処理する方が、処理速度の向上に有利である。【００１１】
このため従来より、ＣＰスケジューリング手法が知られている。ここでいうＣＰとは、クリティカル・パスのことである。ＣＰスケジューリング手法を利用すると、図１に示すブロック線図が、図２に示すタスク・グラフに変換される。見て取れるように、図２のタスク・グラフは、縦四列であり、各々の列の処理を個別の４つのＣＰＵに並列的に割り当てて、１つのＣＰＵで処理したときに比べて、実質的に２倍の速度の処理を達成できる。【００１２】
しかし、図２で、B→D→F→H→Jというパスがクリティカル・パスであって、このクリティカル・パスを処理するＣＰＵの時間以上に、全体の処理時間を短縮できない。【００１３】
特開平６−８３６０８号公報は、並列計算機におけるプログラム実行のボトルネックとなっている箇所を、クリティカル・パス解析部によって見つけることを開示する。【００１４】
特開平７−２１２４０号公報は、論理回路のレイアウト設計に関し、クリティカル・パスを短くすると同時にカットラインを横切るネットの数を最小にするために、クリティカル・パスを抽出するクリティカル・パス抽出装置と、カットラインを作成するカットライン作成装置と各ブロックの結合度とクリティカル・パス情報から各ブロックのマージ相手を決定するマージ相手選択装置とマージ相手選択装置で求めた各ブロックのマージ相手からブロックのマージを行うマージ装置と、カットラインを横切るネットの数が最小になるようにペア交換を行うペアワイズ装置から構成されたシステムを開示する。【００１５】
特開平８−１８０１００号公報は、機械の割り当てを伴うジョブショップ・スケジューリング問題に対して、効率的な近傍を生成し、近似解法と組合わせることにより、最適解を高速に求めることを開示する。【００１６】
特開平６−８３６０８号公報及び特開平８−１８０１００号公報は、タスク・スケジューリングの概要を開示するにすぎない。【００１７】
また、特開平７−２１２４０号公報は、論理回路のレイアウト設計において、クリティカル・パスを短くする技法について説明するが、これは物理的レイアウトにおけるクリティカル・パスであり、ソフトウェアの論理的なクリティカル・パスの処理に適用できるものではない。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開平６−８３６０８号公報
【特許文献２】特開平７−２１２４０号公報
【特許文献３】特開平８−１８０１００号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
従って、この発明の目的は、マルチプロセッサ・システムにおいて、並列化により、プログラムの実行を高速化する技法を提供することにある。
【課題を解決するための手段】
【００２０】
上記目的は、高速化したいプログラムのクリティカル・パスを適切にカットして、別プロセスとして分けて、個別のプロセッサに割り当てるようにすることによって、達成される。これによって、シミュレーションの投機実行のために最適なコードを出力することが可能となる。【００２１】
すなわち、本発明の処理プログラムは、複数の処理ブロックからなる、高速化したいプログラムのソース・コードを読み込んで、クリティカル・パスの可能なカットを全てテストして、結果のカットされたの処理ブロックの流れの処理時間が一番短くなるカットを見出す。【００２２】
このような処理時間の見積もりを可能ならしめるために、予め、処理プログラムをコンパイルして、各処理ブロックの実行時間その他の値を計測しておくフェーズを行っておく。このとき計測される値には、処理が異なるプロセッサにまたがった際のメッセージングのコストや、投機実行のために必要な処理や、投機が失敗した際のロールバックのコスト、更には各ブロックへの入力の予測がどの程度当たるのか（すなわち、投機成功確率）といった計測データも含まれる。【００２３】
クリティカル・パスの可能なカットの処理は、カットした結果のパスに対して、再帰的に適用される。そうして、これ以上カットしても、プロセッサ間の通信時間などを加味すると却って全体の処理時間が長くなってしまうような段階で、カットを停止する。これによって、複数の処理ブロックの群が得られる。特に、この明細書の説明では、各処理ブロックの群を、ブロック・チャンク(block chunk)と呼ぶことにする。【００２４】
こうして分割生成されたブロック・チャンクの数が、マルチプロセッサ・システムのプロセッサの数と同等またはそれ以下であるなら、個々のブロック・チャンクは、そのままコンパイルされて、実行環境で、個別のプロセッサに各々、割り当てられる。【００２５】
しかし、もしブロック・チャンクの数が、プロセッサの数よりも多いと、本発明の処理プログラムは、ブロック・チャンクの数がプロセッサの数に等しくなるように、ブロック・チャンクの結合を試みる。このとき、好適には、結果の結合されたブロック・チャンクのうちのクリティカル・パスに係る処理時間の最大値が一番小さくなるような結合が選ばれる。【００２６】
この結果のブロック・チャンクは、コンパイルされて、実行環境で、個別のプロセッサに各々、割り当てられる。こうして、全てのブロック・チャンク１つに、１つのプロセッサがアサインされるので、最適な並列処理が行われる。
【発明の効果】
【００２７】
以上のように、この発明によれば、マルチプロセッサ環境で、クリティカル・パスの長さと、プロセッサ割り当ての両方につき改善された、高速なプログラムの実行が可能となる。また、シミュレーションの投機実行のために最適なコードを出力することができる。
【図面の簡単な説明】
【００２８】
【図１】シミュレーション・モデリング・ツールのブロック線図の例を示す図である。
【図２】ＣＰスケジューリング手法の例を示す図である。
【図３】本発明を実施するためのハードウェアのブロック図である。
【図４】本発明の一実施例の機能ブロック図である。
【図５】本発明の一実施例の処理の流れを示す図である。
【図６】クリティカル・パスをカットする処理のフローチャートである。
【図７】クリティカル・パスをカットする処理のフローチャートである。
【図８】クリティカル・パスをカットする処理の例の模式図である。
【図９】投機を含む場合の期待される実行時間を示す図である。
【図１０】ブロック・チャンク形成処理の例の模式図である。
【図１１】ＣＰＵ割当て用コード生成処理のフローチャートである。
【図１２】ＣＰＵ割当て用コード生成処理のフローチャートである。
【図１３】ブロック・チャンク結合処理の例の模式図である。
【図１４】ブロック・チャンク結合処理の例の模式図である。
【図１５】ブロックの間の依存関係を説明するための図である。
【発明を実施するための形態】
【００２９】
以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。
【００３０】
次に、図３を参照して、本発明を実施するために使用されるコンピュータのハードウェアについて説明する。図５において、ホスト・バス３０２には、複数のＣＰＵ１  ３０４ａ、ＣＰＵ２  ３０４ｂ、ＣＰＵ３  ３０４ｃ、・・・ＣＰＵｎ  ３０４ｎが接続されている。ホスト・バス５０２にはさらに、ＣＰＵ１  ３０４ａ、ＣＰＵ２  ３０４ｂ、ＣＰＵ３  ３０４ｃ、・・・ＣＰＵｎ  ３０４ｎの演算処理のためのメイン・メモリ３０６が接続されている。
【００３１】
一方、Ｉ／Ｏバス３０８には、キーボード３１０、マウス３１２、ディスプレイ３１４及びハードティスク・ドライブ３１６が接続されている。Ｉ／Ｏバス３０８は、Ｉ／Ｏブリッジ３１８を介して、ホスト・バス３０２に接続されている。キーボード３１０及びマウス３１２は、オペレータが、コマンドを打ち込んだり、メニューをクリックするなどして、操作するために使用される。ディスプレイ３１４は、必要に応じて、後述する本発明に係るプログラムをＧＵＩで操作するためのメニューを表示するために使用される。
【００３２】
この目的のために使用される好適なコンピュータ・システムのハードウェアとして、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｘがある。その際、ＣＰＵ１  ３０４ａ、ＣＰＵ２  ３０４ｂ、ＣＰＵ３  ３０４ｃ、・・・ＣＰＵｎ  ３０４ｎは、例えば、インテル（Ｒ）Ｘｅｏｎ（Ｒ）であり、オペレーティング・システムは、Ｗｉｎｄｏｗｓ（商標）Ｓｅｒｖｅｒ  ２００３である。オペレーティング・システムは、ハードティスク・ドライブ３１６に格納され、コンピュータ・システムの起動時に、ハードティスク・ドライブ３１６からメイン・メモリ３０６に読み込まれる。
【００３３】
なお、本発明を実施するために使用可能なコンピュータ・システムのハードウェアは、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｘに限定されず、本発明のシミュレーション・プログラムを走らせることができるものであれば、任意のコンピュータ・システムを使用することができる。オペレーティング・システムも、Ｗｉｎｄｏｗｓ（Ｒ）に限定されず、Ｌｉｎｕｘ（Ｒ）、Ｍａｃ  ＯＳ（Ｒ）など、任意のオペレーティング・システムを使用することができる。さらに、シミュレーション・プログラムを高速で動作させるために、ＰＯＷＥＲ（商標）６ベースで、オペレーティング・システムがＡＩＸ（商標）のＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｐなどのコンピュータ・システムを使用してもよい。
【００３４】
ハードティスク・ドライブ３１６にはさらに、MATLAB(R)/Simulink(R)、Ｃコンパイラまたは、Ｃ＋＋コンパイラ、本発明に係るクリティカル・パスをカットすためのモジュール、ＣＰＵ割り当て用コード生成モジュール、処理ブロックの期待される実行時間を測定するためのモジュールなどが格納されており、オペレータのキーボードやマウス操作に応答して、メイン・メモリ３０６にロードされて実行される。
【００３５】
尚、使用可能なシミュレーション・モデリング・ツールは、MATLAB(R)/Simulink(R)に限定されず、オープンソースのScilab/Scicosなど任意のシミュレーション・モデリング・ツールを使用することが可能である。
【００３６】
あるいは、場合によっては、シミュレーション・モデリング・ツールを使わず、直接、Ｃ、Ｃ＋＋などでシミュレーション・システムのソース・コードを書くことも可能であり、その場合にも、本発明は適用可能である。
【００３７】
図４は、本発明の実施例に係る機能ブロック図である。各々のブロックは、基本的に、ハードティスク・ドライブ３１６に格納されているモジュールに対応する。
【００３８】
図４において、シミュレーション・モデリング・ツール４０２は、MATLAB(R)/Simulink(R)、Scilab/Scicosなどの既存の任意のツールでよい。シミュレーション・モデリング・ツール４０２は、基本的には、オペレータが、ディスプレイ３１４上でＧＵＩ的に機能ブロックを配置し、数式など必要な属性を記述し、必要に応じて、機能ブロック間を関連付けてブロック線図を記述することを可能ならしめるような機能をもつ。シミュレーション・モデリング・ツール４０２はさらに、記述されたブロック線図に等価な機能を記述するＣのソース・コードを出力する機能をもつ。Ｃ以外にも、Ｃ＋＋、Ｆｏｒｔｒａｎなどを使用することができる。
【００３９】
なお、シミュレーション・モデリング・ツールは、別のパーソナル・コンピュータに導入して、そこで生成されたソース・コードを、ネットワークなどを経由して、ハードティスク・ドライブ３１６にダウンロードするようにすることもできる。
【００４０】
こうして出力されたソース・コード４０４は、ハードティスク・ドライブ３１６に保存される。ソース・コード４０４は、コンパイラ４０６でコンパイルされ、結果の実行可能プログラムは、テスト・モジュール４０８に渡される。
【００４１】
テスト・モジュール４０８は、実行テストを行う機能と、投機テストを行う機能を有する。実行テストでは、所定のシナリオにより、図１に示すような各ブロックの平均処理時間、プロセッサ間通信時間、及び投機成功確率が測定される。平均時間を測定するために、好適には同一のシナリオが、複数回実行される。その測定結果４１０は、後で使用するために、ハードティスク・ドライブ３１６に保存される。
【００４２】
投機テストでは、別の所定のシナリオにより、結果の実行可能プログラムを投機実行させる。そのシナリオを繰り返すことにより、投機準備の処理時間すなわち、投機が失敗してロールバックする場合に備えて、予測した入力値を保存したりする処理のための時間と、投機成否確認の処理時間すなわち、実際のデータが来たときにそれが予測していたデータと一致するかを確認する処理の時間と、ロールバック処理時間すなわち、投機が失敗した、つまり予測した入力と実際の値が異なっていたことが分かったときに、間違った入力に基づいて行われた処理を止めたり、データの消去などの後処理に要する時間が計測される。そのような値もまた、その測定結果４１０として、後で使用するために、ハードティスク・ドライブ３１６に保存される。
【００４３】
なお、投機成功確率は、実は実際に投機実行を行わなくても算出することができる。投機実行では、本来来るべき入力が来る前に処理が実行されるので、その入力を予測して処理が実行される。従って、投機が成功する確率は、入力に対する予測が的中する確率と等しくなる。その入力を予測するアルゴリズムが定まっていれば、実際に投機実行をしなくても（すなわち、予測した入力データに基づくブロックの処理を実行しなくとも）実際の入力データのみから、予測アルゴリズムの予測成功確率を算出することができる。すなわち、単に「実行テスト」において、各ブロックに対する入力を記録しておき、その入力データ系列から、入力予測アルゴリズムの予測成功率を算出することで、投機成功確率を求めることができる。一方、投機実行をしたとき、あるいは投機実行が失敗したときにどの程度の時間がかかるかは、実際に投機実行をしてみないと分からない。そのため、それらの情報を得るために投機テストが行なわれる。ただし、投機実行の実装が定まれば、投機準備や投機の成否確認、投機失敗時のロールバックに要する処理時間は、入力データ量に比例した処理時間となることが予想される。従って、「投機テスト」においては、全てのブロックを投機実行しなくてもよく、いくつかの、入力データ量の異なるブロックを投機実行してみることで、入力データ量と投機関連処理時間の関係が得られ、それに基づいて全てのケースのコストを算出することができる。
【００４４】
「クリティカル・パスのカット」モジュール４１２は、ソース・コード４０４を原則的にブロック単位で処理して、クリティカル・パスを見出し、カットを入れて、最適な実行時間になるカットを見出す機能をもつ。この際、測定結果４１０の情報が使用される。モジュール４１２はさらに、クリティカル・パスのカット機能を再帰的に適用して、図１０に示すような、小分けされたブロック・チャンクを得る。そうして生成されたブロック・チャンクの情報４１４は、後で使用するために、ハードティスク・ドライブ３１６に保存される。クリティカル・パスのカット機能は、後でフローチャートを参照して、詳細に説明する。
【００４５】
「ＣＰＵ割当て用コード生成」モジュール４１６は、ブロック・チャンクの情報４１４と、測定結果４１０とを用いて、ＣＰＵ１〜ＣＰＵｎに割当てるコード４１８ａ、４１８ｂ、・・・、４１８ｍを生成する。もしブロック・チャンクの数が、ＣＰＵ１〜ＣＰＵｎの数より少ないか等しいと、各ブロック・チャンクのコードは、そのままＣＰＵ１〜ＣＰＵｎに割当てられる。
【００４６】
しかし、もしブロック・チャンクの数が、ＣＰＵ１〜ＣＰＵｎの数より多いと、図１４に模式的に示すように、ブロック・チャンクの数がＣＰＵ１〜ＣＰＵｎの数と等しくなるように、ブロック・チャンク同士が結合される。但し、このときの結合は、好適には、結果のクリティカル・パスの期待される実行時間が最も少なくなるように、最適に選ばれる。ＣＰＵ割当て用コード生成機能も、後でフローチャートを参照して、詳細に説明する。
【００４７】
この結果生成されるのは、ＣＰＵ１〜ＣＰＵｎに割当てるコード４１８ａ、４１８ｂ、・・・、４１８ｍと、依存関係の情報４２０である。依存関係の情報４２０が必要である理由は、次のとおりである。すなわち、図１０に示すように、もともとの処理のフローが、クリティカル・パスのカット機能によって分断されると、もともとのブロック間の依存関係が切れてしまうことがある。これを補うために、モジュール４１６は、例えば、ＣＰＵ１〜ＣＰＵｎに割当てるコード４１８ａ、４１８ｂ、・・・、４１８ｍのうち、どのコードが、他のどのコードで使われている変数をリターンするか、などいう依存関係の情報４２０も提供する。実際上、依存関係の情報４２０は、「クリティカル・パスのカット」モジュール４１２によって、カット時に作成されるので、「ＣＰＵ割当て用コード生成」モジュール４１６は、それを利用することになる。
【００４８】
こうして生成されたコード４１８ａ、４１８ｂ、・・・、４１８ｍは、コンパイラ４２２で個別に実行可能プログラムとしてコンパイルされ、実行環境４２４では、対応するＣＰＵ１〜ＣＰＵｎ上で並列実行されるように、個別に割り当てられる。なお、依存関係の情報４２０は、ＣＰＵ１〜ＣＰＵｎによって共通に参照可能に、メイン・メモリ３０６の共通メモリ領域に配置され、ＣＰＵ１〜ＣＰＵｎがコード４１８ａ、４１８ｂ、・・・、４１８ｍを実行する際に、必要に応じて、他ＣＰＵ上で実行されているコードの情報を参照するために使用される。
【００４９】
図５は、この実施例の全体の処理の流れを示す。これは作業手順を示す流れであり、個々には必ずしもコンピュータの処理のフローとは対応しないことを理解されたい。
【００５０】
図５で、ステップ５０２では、開発者または作業者が、MATLAB(R)/Simulink(R)などのシミュレーション・モデリング・ツール４０２を使って、特定のシミュレーション対象のブロック線図を、図３に示すシステム、または別のコンピュータ上で、作成する。
【００５１】
ステップ５０４では、開発者または作業者が、作成したブロック線図に対応するソース・コード４０４を、シミュレーション・モデリング・ツール４０２の機能を使って生成し、ハードティスク・ドライブ３１６に保存する。
【００５２】
ステップ５０６では、開発者または作業者が、コンパイラ４０６を使って、ソース・コード４０４をコンパイルする。コンパイルされた実行可能プログラムは、図示しないが、一旦、ハードティスク・ドライブ３１６に保存される。
【００５３】
ステップ５０８では、開発者または作業者が、コンパイルされた実行プログラムを使用して、テスト・モジュール４０８で、実行テストを行う。この結果得られたブロックの平均処理時間、プロセッサ間通信時間、及び投機成功確率の実行時間の計測データは、ステップ５１０で、計測結果４１０として、ハードティスク・ドライブ３１６に保存される。
【００５４】
ステップ５１２では、開発者または作業者が、コンパイルされた実行プログラムを使用して、テスト・モジュール４０８で、投機テストを行う。この結果得られた投機準備の処理時間、投機成否確認の処理時間、及びロールバック処理時間の計測データは、ステップ５１４で、計測結果４１０として、ハードティスク・ドライブ３１６に保存される。
【００５５】
ステップ５１６では、開発者または作業者の操作に応答して、コンピュータの処理が開始される。すなわち、基本的に、ステップ５１６からステップ５２４までは、コンピュータの処理によって自動的に進行する。
【００５６】
ステップ５１６では、「クリティカル・パスのカット」モジュール４１２によって、ソース・コード４０４が処理される。具体的な処理は後述するが、ソース・コード４０４に記述されている全体の処理フローにおけるクリティカル・パスをアルゴリズムにより発見し、それを処理時間的に最適にカットし、カットした後の処理フローにおいて、クリティカル・パスをカットするという処理を再帰的に行う。この際に、測定結果４１０が用いられる。
【００５７】
この結果、図１０に示すような複数のブロック・チャンクが得られるので、ステップ５１８で、それらに関する情報が、ブロック・チャンク４１４として、ハードティスク・ドライブ３１６に保存される。なお、このとき保存されるデータ構造であるが、ＸＭＬなど、コンピュータ可読で、ソースコードの内容と連結関係（リンク）の両方を表現可能な任意のデータ構造を用いることができる。
【００５８】
ステップ５２０では、ブロック・チャンク４１４の情報を用いて、「ＣＰＵ割当て用コード生成」モジュール４１６が、ＣＰＵ１〜ＣＰＵｎに個別に割当てるためのコードを生成する。すなわち、もしブロック・チャンクの数がＣＰＵ１〜ＣＰＵｎの個数よりも少なければ、そのまま１つずつＣＰＵ１〜ＣＰＵｎに割当てる。一方、ＣＰＵ１〜ＣＰＵｎの個数よりも、ブロック・チャンクの数が多ければ、ＣＰＵ１〜ＣＰＵｎの個数と等しくなるように、ブロック・チャンクが、実行時間的に最短になるように結合される。この際に、測定結果４１０が用いられる。
【００５９】
ステップ５２２では、モジュール４１６によって生成されたコードが、コンパイラ４２２によってコンパイルされ、ステップ５２４で、個々に、対応するプロセッサＣＰＵ１〜ＣＰＵｎに割当てられて、各々実行される。
【００６０】
次に、図６と図７のフローチャートを参照して、図５のステップ５１６に対応する、クリティカル・パスのカットの処理を説明する。ステップ６０２では、クリティカル・パスの最適カットを見つける、という処理が行われる。ここで最適カットが何かということを説明するために、図８を参照する。
【００６１】
図８では、ブロックＡ〜Ｉからなる処理のフローが示されている。ここで、クリティカル・パスを見つけるアルゴリズムによって、Ｂ-Ｃ-Ｄ-Ｅ-Ｆがクリティカル・パスであると同定されたとすると、ステップ６０２では、Ｂ-Ｃ-Ｄ-Ｅ-Ｆに沿った可能なカットc1, c2, c3, c4を、「クリティカル・パスのカット」モジュール４１２が順次試すことになる。例えば、カットc3を試すとは、c3のところでクリティカル・パスをカットし、図８に示すように、カットされたフローを、論理的に、脇に移動される。すると、２つのフローが並置されることになる。そこでカットc3を評価する。カットc3を評価するとは、もし投機成功確率が１００％であると仮定すると、並置された２つのフローの期待される実行時間を比較して、長い方の値Tcを評価することである。しかし、一般的には、投機成功確率は、１００％より低いので、図９で説明するように、投機成功確率を考慮に入れて、Tcが評価される。このようなTcが一番短くなるようなカットを、最適カットと呼ぶことにする。
【００６２】
最適カットを見つけるためのより詳しい処理（サブルーチン）は、後で図７のフローチャートを参照して説明する。
【００６３】
なお、各ブロックの期待される実行時間は、図５のステップ５０８に示す実行テストで予め計測され、計測結果４１０としてハードディスク・ドライブ３１６に保存されている。そのような計測結果４１０が、所与のフローの期待される実行時間を計算する際に使用されることに留意されたい。
【００６４】
実際上、実行時間を見積もるためには、単純にフローに沿ってブロックの期待される実行時間を実行するだけでは済まない。そのことを図９を参照して説明する。
【００６５】
ここで、次のような変数を定義する。ここで、コストとは、時間とみなしてよい。
MSCxy : ブロックＸとブロックＹがカットされているときの、ブロックＸからブロックＹについてのメッセージ送信コスト。
MRCxy : ブロックＸとブロックＹがカットされているときの、ブロックＸからブロックＹについてのメッセージ受信コスト。
SCxy : ブロックＸからブロックＹについての投機コスト。
SCCxy : ブロックＸからブロックＹについての投機チェックコスト。
RBCxy : ブロックＸからブロックＹについての投機が失敗した場合のロールバック・コスト。
【００６６】
これらのブロック間のコストも、図５のステップ５０８に示す実行テスト及びステップ５１２で示す投機テストで予め計測され、計測結果４１０としてハードディスク・ドライブ３１６に保存されている。
【００６７】
すると、クリティカル・パスＢ-Ｃ-Ｄ-Ｅ-ＦのＣとＤの間にカットcを入れるということは、結果の期待される実行時間を、図９に示すように、投機が成功した場合と、投機が失敗した場合との期待値で見積もる必要がある。
【００６８】
投機が成功した場合は、カットした結果の２つのフローの長い方の実行時間が結果の期待される時間となって、それは、
Tcs = |D|+|E|+|F|+SCcd+MRCif+MRCcd+SCCcd
ここで、例えば|D|は、ブロックDの実行時間をあらわす。
【００６９】
一方、投機が失敗した場合は、Ｂ-Ｃと、Ｄ-Ｅ-Ｆが直列実行されるので、期待される時間は、
Tcf = |B|+|C|+|D|+|E|+|F|+MRCac+MSCcd+MRCcd+RBCcd+MRCif
【００７０】
ところで、このような投機の成功確率pcは、図５のステップ５０８に示す実行テストで予め計測され、計測結果４１０としてハードディスク・ドライブ３１６に保存されている。これを用いて、結果の期待される実行時間は、
Tc = pcTcs + (1-pc)Tcfと計算される。
【００７１】
図６のフローチャートに戻って、ステップ６０２の処理の結果をもって、ステップ６０４では、「クリティカル・パスのカット」モジュール４１２が、最適カットが存在するかどうかを判断する。最適カットが存在するとは、カットした結果、全体の期待される処理時間が短縮されることを意味する。どんな場合でもカットすると処理時間が短縮されるとは限らない。すなわち、上記した送信コスト、受信コスト、及び投機コストに鑑みると、カットしても処理時間の短縮が図れない場合がある。そのような場合、ステップ６０４で最適カットが存在しないと判断して、ステップ６０６で、現在評価しているブロック・チャンクの情報が、好適にはハードディスク・ドライブ３１６に保存される。
【００７２】
一方、ステップ６０４で最適カットが存在すると判断されると、「クリティカル・パスのカット」モジュール４１２は、ステップ６０８で、カットされたブロックを移動する。これは、図８に示すような処理である。
【００７３】
ステップ６１０では、カットされてできたパスの集合全体に対して、図６のフローチャートの処理が再帰呼び出しされる。図８のブロックで説明すると、先ずブロックＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉについて図６のフローチャートの処理が適用された結果、ブロックＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆと、ブロックＧ、Ｈ、Ｉに分けられ、そこで、図６のフローチャートの処理が再帰呼び出しされる。
【００７４】
次に、図７のフローチャートを参照して、図６のステップ６０２の処理を更に詳しく説明する。ステップ７０２では、クリティカル・パスを見つける処理が行われる。処理フローに対してクリティカル・パスを見つける処理自体は従来周知であり、
例えば、http://www.kogures.com/hitoshi/webtext/pt-pert/index.htmlに記述されているＰＥＲＴの方法などを使用することができる。
【００７５】
ステップ７０４では、tmin = クリティカル・パスに沿っての期待される時間、
cmin = null、Ｃ = クリティカル・パスの可能なカットの集合とセットされる。
【００７６】
ステップ７０６では、Ｃが空かどうかが判断され、そうでなければ、ステップ７０８に進んで、Ｃからカットcが取り出される。
【００７７】
ステップ７１０では、カットcの期待される実行時間が計算されて、それが、tcに代入される。ここでの実行時間の計算は、図９に関連して説明した、投機実行の場合も含む。
【００７８】
ステップ７１２では、tc < tminであるかどうかが判断され、もしそうなら、ステップ７１４で、tmin = tc、cmin = cとセットされる。
【００７９】
このように、Ｃの全てのカットについて、ステップ７０８、７１０、７１２及び７１４が実行され、結果のcminが、図６のステップ６０２に返される。このとき、Ｃのどのようなカットも、tmin = クリティカル・パスに沿っての期待される時間よりも処理時間を短縮させない場合がある。そのような場合、ステップ７１２での判断は肯定的にならないので、ステップ７１４は実行されず、よって、cmin = nullのままである。すると、図６のステップ６０４の判断が否定的になる。
【００８０】
このような処理の結果を模式的に示したのが、図１０である。図１０の左側に示すブロックの処理の流れが、図６のフローチャートに示す処理の再帰的手続きによって複数箇所でカットされ、図１０の右側に示すように、細分化された複数のブロック・チャンクが得られる。
【００８１】
次に、図１１と図１２のフローチャートを参照して、図５のステップ５２０に対応する、ＣＰＵ割当てコード生成の処理を説明する。これは、図４の「ＣＰＵ割当てコード生成」モジュール４１６によって実行される。
【００８２】
ステップ１１０２では、p = プロセッサ（ＣＰＵ）の数、b = ブロック・チャンクの数とセットされる。
【００８３】
ステップ１１０４では、p < bかどうかが判断される。それが否定的、すなわち p >= bであるなら、そのままでブロック・チャンクを個々に割り当てるだけの数のプロセッサがあるので、ステップ１１０６で、適宜個々のブロック・チャンクを、個々のプロセッサに割り当てて、処理は終わる。
【００８４】
ステップ１１０４で、p < bと判断されたなら、そのままでブロック・チャンクを個々に割り当てるにはプロセッサの数が不足することを意味するので、ステップ１１０８で、２つのブロック・チャンクを結合して、ブロック・チャンクの数を１つ減らす処理が行われる。
【００８５】
２つのブロック・チャンクを結合するということは、その結合したブロック・チャンクのところで、クリティカル・パスが長くなって期待される処理時間が長くなる場合がある。そこでステップ１１０８では、２つのブロック・チャンクを結合した結果の期待される処理時間が最短になるような最適な組み合わせが見出される。そのような処理を模式的に示すのが、図１４である。
【００８６】
ステップ１１１０では、bが1減らされて、ステップ１１０４の判断に戻る。こうして、p = bになるまで、ステップ１１０８とステップ１１１０が繰り返される。
【００８７】
p = bになると、ステップ１１０４が否定的になる。するといまや、そのままでブロック・チャンクを個々に割り当てるだけの数のプロセッサがあるので、ステップ１１０６で、その時点で保存されている結果の個々のブロック・チャンクを、個々のプロセッサに割り当てて、処理は終わる。
【００８８】
なお、何個かのＣＰＵを他の処理のために留保したい場合には、b < pとなるまでさらに、ブロック・チャンクの数を減らすことがある。
【００８９】
図１２は、図１１のステップ１１０８の処理をより詳細に示すフローチャートである。図１２において、ステップ１２０２では、Ｓ1 = 現在のブロック・チャンクの集合、tmin = ∞、umin = ∞、b1 = b2 = nullと置かれる。ここで、∞というのは、この状況で、実際的に想定される数よりも十分大きい適当な定数という意味である。
【００９０】
ステップ１２０４では、Ｓ1が空かどうかが判断され、もしそうなら処理が完了して、図１１のフローチャートのステップ１１０８に戻る。Ｓ1が空でないなら、ステップ１２０６で、Ｓ1から１つのブロック・チャンクs1が取り出される。
【００９１】
ステップ１２０８では、Ｓ2 = 現在のブロック・チャンクの集合とセットされる。ステップ１２１０では、Ｓ2が空かどうかが判断され、もしそうなら、ステップ１２０４に戻る。Ｓ2が空でないなら、ステップ１２１２で、Ｓ2から１つのブロック・チャンクs2が取り出される。
【００９２】
ステップ１２１４では、s2がs1の下に結合されたときの実行時間が、図４に示す各ブロックの計測結果４１０を使用して、計算され、Ts1s2に代入される。ここで、s2 = s1となる場合は省かれる。また、どのブロック・チャンクも、オリジナルのブロックのフローの一部であるから、任意の２つのブロック・チャンクの間で、どちらがもともと上流であったかが決定できる場合がある。そこで、好適には、ステップ１２１４では、オリジナルの上下流関係が判定できるなら、その上下流関係を維持するように、結合させるようにしてもよい。
【００９３】
ステップ１２１６では、Ts1s2がTminと等しいかどうかが判断される。もしそうなら、ステップ１２１８で、s2がs1の下に結合されたときの期待されるコストが計算され、us1s2に代入される。ここでコストとは、各ブロックの実行時間、異なるプロセッサにまたがるブロック間のメッセージ送受信コスト、投機コスト、投機チェックコスト、投機失敗時のロールバックコストに、可能な投機の成否の組み合わせ毎に投機成功確率で重み付けして算出する、全ＣＰＵ消費時間の期待値である。
【００９４】
次に、ステップ１２２０では、us1s2 < uminであるかどうかが判断され、もしそうなら、ステップ１２２２で、
Tmin = Ts1s2、b1 = s1、b2 = s2、uminには、s2がs1の下に結合されたときの期待されるコストが代入される。ステップ１２２２からは、ステップ１２１０の判断に戻る。
【００９５】
一方、ステップ１２１６で、Ts1s2がTminと等しくないなら、ステップ１２２４に進み、そこで、Ts1s2 < Tminかどうかが判断される。もしそうならステップ１２２２が実行されてからステップ１２１０の判断に戻る。そうでないなら、ステップ１２２４から直ちにステップ１２１０の判断に戻る。
【００９６】
図１３は、ブロック・チャンクの結合の例を示す。この例では、図示されているようにブロック・チャンクbc1, bc2, bc3, bc4の４つがあるとする。するとこれからは、オリジナルのフローの上下流に拘らないなら、１２通りの結合がありえるが、その全てを網羅して説明するのは冗長なので、代表的に、左下に示す、bc3がbc2の下に結合される場合と、右下に示すbc4がbc1の下に結合される場合について説明する。
【００９７】
先ず、bc3がbc2の下に結合される場合だと、期待される実行時間tbc2 bc3と、期待されるコストubc2 bc3はそれぞれ、次のように計算される。
tbc2 bc3 = |B|+|C|+|D|+|E|+|F|+MRCac+MRCif
ubc2 bc3 = |A|+|B|+|C|+|D|+|E|+|F|+|G|+|H|+|I|
+MRCac+MRCif+MSCac+MSCif
【００９８】
一方、bc4がbc1の下に結合される場合だと、期待される実行時間tbc1 bc4と、期待されるコストubc1 bc4はそれぞれ、次のように計算される。
tbc1 bc4 = p1p2(|D|+|E|+|F|+ SCcd + SCif + MRcd + SCCcd + MRCif + SCCif)+         p1(1-p2)(|A|+|G|+|H|+|I|+|F|+MSAac+MSCif+MRCif+SCCif+RBCif)+
(1-p1)(|B|+|C|+|D|+|E|+|F| + MRCac +
MSCcd + MRCcd + SCCcd + RBCcd + MRCif)
ubc1 bc4 = |A|+|B|+|C|+|D|+|E|+|F|+|G|+|H|+|I|+
p1p2(SCcd + SCif + MRcd + SCCcd + MRCif + SCCif)+
p1(1-p2)(MSAac+MSCif+MRCif+SCCif+RBCif)+
(1-p1)(MRCac + MSCcd + MRCcd + SCCcd + RBCcd + MRCif)
ここで、p1及びp2は、図示されている経路での投機の成功確率である。
【００９９】
上記の個々の値はすべて、計測結果４１０から取得される。
【０１００】
図１４は、ブロック・チャンクがbc1, bc2, bc3, bc4, bc5,bc6の６個あって、一方、ＣＰＵが５個しかない場合に、ブロック・チャンクを１つ減らすために、「ＣＰＵ割当てコード生成」モジュール４１６が、２つのブロック・チャンクの結合を試みる場合の処理を示す図である。
【０１０１】
図１４の左下の場合では、bc4の下にbc6が結合されて、結果的に、bc3が全体の最長の実行時間ts1s2を与える。
【０１０２】
図１４の右下の場合では、bc1の下にbc5が結合されて、結果的に、bc1が全体の最長の実行時間ts1s2を与える。
【０１０３】
「ＣＰＵ割当てコード生成」モジュール４１６は、可能な全てのブロック・チャンクの組み合わせに最長の実行時間ts1s2を計算して、結果的に最短のts1s2を示すブロック・チャンクの結合を選ぶ。
【０１０４】
このようにして生成されたＣＰＵ毎のコードは、各々、コンパイラ４２２によってコンパイルされ実行可能コードに変換されると、一旦ハードディスク・ドライブ３１６に保存される。
【０１０５】
ところで、もともと繋がっていたブロックのフローにカットを入れると、カットされた結果の各々のブロックの間の依存関係が切れてしまうことがあるので、そのような情報を補う必要がでてくる。図１５は、そのような依存関係を説明するための模式図である。
【０１０６】
図１５において、ブロックＡ及びブロックＣからなるコードをCode 1、ブロックＢ及びブロックＤからなるコードをCode 2、ブロックＦ、ブロックＨ及びブロックＪからなるコードをCode 3、ブロックＥ、ブロックＧ及びブロックＩからなるコードをCode 4とする。
【０１０７】
Code 1、Code 2、Code 3、Code 4の中身は、図１５に図示するとおりである。すると、Code 3の引数が、それぞれ、Code 1、Code 2、のCode 4の最初の返り値を使用していることが見てとれる。
【０１０８】
そのことは例えば、下記のように記述される。
1st output of Code 1 -> 1st argument of Code 3
1st output of Code 2 -> 2nd argument of Code 3
1st output of Code 3 -> 3rd argument of Code 3
【０１０９】
このような情報は、「ＣＰＵ割当てコード生成」モジュール４１６が、個々のＣＰＵ割当て用コードを生成するときに、併せて生成する。
【０１１０】
依存関係の情報は、個々のＣＰＵ割当て用コードに含めて、コンパイラ４２２に通知することもできるが、好適には、直接実行環境４２４の共有メモリ上に配置するなどして、ＣＰＵ１〜ＣＰＵｎが割当てられたコードを実行するときに、依存関係の情報を参照できるようにする。
【０１１１】
こうしておいて、オペレータの操作により、シミュレーション動作が開始されると、コンパイルされた各ＣＰＵ用の実行可能プログラムが順次、実行環境４２４によってメイン・メモリ３０６に読み込まれ、実行環境４２４は、個々の実行可能プログラムに関して生成されたプロセスを、個別のプロセッサに割り当てる。こうして、複数の実行可能プログラムに分割されたシミュレーション・プログラムは、個々のプロセッサによって並列的に実行される。
【０１１２】
以上の実施例では、シミュレーション・モデリング・ツールを用いて生成したプログラム・ソース・コードに基づき、複数のＣＰＵに割り当てて並列化する処理について説明したが、本発明は、そのようなシミュレーション・プログラムのソース・コードに限定されず、処理ブロック単位が同定でき、また、その流れが記述されているなら、任意のソース・コードに適用可能である。
【符号の説明】
【０１１３】
４０４・・・ソース・コード
４０６、４２２・・・コンパイラ
４１２・・・「クリティカル・パスのカット」モジュール
４１６・・・「ＣＰＵ割当て用コード生成」モジュール
４１８・・・ＣＰＵ用コード
４２０・・・依存関係情報
【図１】
2010047174.tif 000003
【図２】
2010047174.tif 000004
【図３】
2010047174.tif 000005
【図４】
2010047174.tif 000006
【図５】
2010047174.tif 000007
【図６】
2010047174.tif 000008
【図７】
2010047174.tif 000009
【図８】
2010047174.tif 000010
【図９】
2010047174.tif 000011
【図１０】
2010047174.tif 000012
【図１１】
2010047174.tif 000013
【図１２】
2010047174.tif 000014
【図１３】
2010047174.tif 000015
【図１４】
2010047174.tif 000016
【図１５】
2010047174.tif 000017
【国際調査報告】
2010047174.tif 000018
2010047174.tif 000019
2010047174.tif 000020
2010047174.tif 000021