JP3675623B2 - プログラム開発支援装置及び方法並びにプログラム開発支援用ソフトウェアを記録した記録媒体 - Google Patents
プログラム開発支援装置及び方法並びにプログラム開発支援用ソフトウェアを記録した記録媒体 Download PDFInfo
- Publication number
- JP3675623B2 JP3675623B2 JP29988697A JP29988697A JP3675623B2 JP 3675623 B2 JP3675623 B2 JP 3675623B2 JP 29988697 A JP29988697 A JP 29988697A JP 29988697 A JP29988697 A JP 29988697A JP 3675623 B2 JP3675623 B2 JP 3675623B2
- Authority
- JP
- Japan
- Prior art keywords
- scenario
- program
- parallel
- development support
- unit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Debugging And Monitoring (AREA)
- Multi Processors (AREA)
- Devices For Executing Special Programs (AREA)
- Stored Programmes (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、並行プログラムを開発する技術の改良に関し、より具体的には、複雑な並行プログラムについても優れた信頼性と効率で作成できるようにしたものである。
【０００２】
【従来の技術】
並行プログラムは、複数のプロセスが同時並行的に動作するプログラムであり、別々に動くプロセス間の相互関係によって全体の動作が決まるという複雑さがある。そのため、並行プログラムの作成は、プロセスが単一の流れに従って順次動作をする逐次プログラムに比べて困難である。特に、並行プログラムの挙動は、どのプロセスのどの部分がどのようなタイミングで実行されるかに応じて、実行ごとに非決定的に異なる。この結果、並行プログラムのバグには再現性が乏しく、また、テストするテストケースも極めて多数となるため、テストとデバッグが非常に困難である。
【０００３】
このような並行プログラムの作成を支援し、並行プログラムの信頼性を高める技術として、超逐次プログラミングが知られている（特開平８−１６４２９）。この技術では、並行プログラムを一旦逐次化して超逐次プログラムを作成する。超逐次プログラムとは、もとの並行プログラムをその並行構造に関する情報を保ちながら逐次化したプログラムである。そして、このような超逐次プログラムに対してプログラミング、テスト、デバッグを行い、その結果に基づいて超逐次プログラムを再び並行化することによって信頼性の高い並行プログラムを作成することができる。
【０００４】
例えば、並行プログラムにテストケースを与えるなどしてテストし、このテストの際の実行ログのうち、バグがないと判定された正しい実行ログを、もとの並行プログラムを一旦逐次化した超逐次プログラムの一種とみなす。そして、このような正しい実行ログを複数マージすることによって、超逐次プログラムの正しい振る舞いを表すシナリオグラフを作る。このシナリオグラフを、部分間の実行順序を指定する同期命令と共に、複数のプロセスに部分ごとに割り当てることによって再び並行化し、並行プログラムを作成する。
【０００５】
また、本出願人が出願した他の技術では、並行プログラムを、実行制御の単位となるセクションに分け、セクション間の正しい実行順序をシナリオグラフの経路で表す。この経路に含まれる個々の動作を、動作間の実行順序を指定する同期命令と共に各プロセスに割り当てることによって、正しい振る舞いを示す並行プログラムを作成する。なお、並行プログラムには違った実行順序を表すいくつかの経路が含まれることがあるが、経路ごとの実行結果が同じになる場合のようにシナリオグラフと等価な経路を自動的に復元することによって、生成される並行プログラムの振る舞いに柔軟性が増え、実行効率が向上する。
【０００６】
【発明が解決しようとする課題】
しかしながら、これらの従来技術では、プログラムの正しい振る舞いをシナリオグラフで表す際に、単一の階層のみを持つ平面的な構造のシナリオグラフを用いる。すなわち、このシナリオグラフは、プログラムの各部分をアークで表し、各状態を表すノードの間をアークで接続することによって、プログラムの部分間の実行順序を、平面的な構造の状態遷移グラフで表したものである。そして、ループや階層構造のような複雑な構造を平面的な構造のシナリオグラフで表そうとすると、構造の複雑さに応じてシナリオグラフが複雑で大規模なものとなるので、処理のアルゴリズムが複雑化したり処理効率が悪化するだけでなく、シナリオグラフ自体も理解しづらいものとなる。このため、上記のような従来技術は複雑な並行プログラムに適用することが困難という問題点があった。
【０００７】
本発明は、上記のような従来技術の問題点を解決するために提案されたもので、その目的は、複雑な並行プログラムについても優れた信頼性と効率で作成できる技術を提供することである。
【０００８】
上記の目的を達成するため、本発明は、入力装置及び記憶装置を有するコンピュータに、編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段を構成することによって実現され、前記入力装置が入力した情報に基づいて、前記編集手段が第１の並行プログラムを作成し、前記第１の並行プログラムを前記記憶装置が記憶し、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段が第２の並行プログラムを生成し、前記第２の並行プログラムを前記記憶装置が記憶するプログラム開発支援装置において、前記第１の並行プログラムから実行のシナリオを作成する前記作成手段と、前記第１の並行プログラムを解析することによって、前記第１の並行プログラムの部分間に存在する依存関係を抽出する前記解析手段と、前記シナリオを、ループを含まないブロックに階層的に分解する前記分解手段と、前記依存関係に基づいて、前記分解されたシナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化する前記並行化手段と、各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化する前記統合化手段と、統合化されたプロセスごとのシナリオから第２の並行プログラムを生成する前記生成手段と、を有することを特徴とする。また、本発明は、入力装置及び記憶装置を有するコンピュータに構成された編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段によって実現され、前記入力装置が入力した情報に基づいて、前記編集手段が第１の並行プログラムを作成し、前記第１の並行プログラムを前記記憶装置が記憶し、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段が第２の並行プログラムを生成し、前記第２の並行プログラムを前記記憶装置が記憶するプログラム開発支援方法において、前記作成手段が、前記第１の並行プログラムから実行のシナリオを作成するステップと、前記解析手段が、前記第１の並行プログラムを解析することによって、第１の並行プログラムの部分間に存在する依存関係を抽出するステップと、前記分解手段が、前記シナリオを、ループを含まないブロックに階層的に分解するステップと、前記並行化手段が、前記依存関係に基づいて、分解された前記シナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化するステップと、前記統合化手段が、各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化するステップと、前記生成手段が、統合化されたプロセスごとのシナリオから第２の並行プログラムを生成するステップと、を含むことを特徴とする。また、本発明は、入力装置及び記憶装置を有するコンピュータに、編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段を実現させるソフトウェアであって、前記入力装置から入力された情報に基づいて、前記編集手段に第１の並行プログラムを作成させ、前記第１の並行プログラムを前記記憶装置に記憶させ、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段に第２の並行プログラムを生成させ、前記第２の並行プログラムを前記記憶装置に記憶させるプログラム開発支援用ソフトウェアを記録した記録媒体において、前記プログラム開発支援用ソフトウェアは、前記作成手段に、前記第１の並行プログラムから実行のシナリオを作成させ、前記解析手段に、前記第１の並行プログラムを解析させることによって、前記第１の並行プログラムの部分間に存在する依存関係を抽出させ、前記分解手段に、前記シナリオを、ループを含まないブロックに階層的に分解させ、前記並行化手段に、前記依存関係に基づいて、分解された前記シナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化させ、前記統合化手段に、各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化させ、前記生成手段に、統合化されたプロセスごとのシナリオから第２の並行プログラムを生成させることを特徴とする。
以上の発明では、正しいことが確認されたシナリオという形で、並行プログラムを一旦逐次化し、このシナリオに基づいて並行プログラムを再び生成することによって並行プログラムの信頼性を向上させる。その際、シナリオを一旦、ループを含まないブロックに階層的に分解する。そして、分解されたブロック若しくは前記ブロックに属する命令を各プロセスに割り当てて並行化し、プロセスごとに再び統合化して並行プログラムを生成する。分解された個々のブロックはループや階層構造を含まないので、効率的に並行化処理でき、並行プログラム全体として効率的に開発を行うことができる。
【０００９】
本発明のプログラム開発支援装置は、前記分解手段は、前記作成手段から与えられたシナリオを正規化する手段を有することを特徴とする。
以上の発明では、シナリオを正規化することによって正規表現に変換されたシナリオとし、正規表現に変換されたシナリオは階層的に分解することが容易である。このため、並行プログラムの分解が効率化される。
【００１０】
本発明のプログラム開発支援装置は、前記並行化手段は、シナリオをプロセスに割り当てる際、前記依存関係に対応する同期命令をシナリオに埋め込むように構成されたことを特徴とする。
以上の発明では、同期命令を埋め込みながらシナリオをプロセスに割り当てるので、プロセス間において各部分の実行タイミングが、依存関係に基づく先行制約に合致するように制御され、最終的に得られる並行プログラムの信頼性が確保される。
【００１１】
本発明のプログラム開発支援装置は、前記並行化手段は、シナリオに埋め込んだ前記同期命令のうち、冗長な同期命令を除去するように構成されたことを特徴とする。また、本発明のプログラム開発支援方法は、前記並行化手段が並行化するステップは、シナリオをプロセスに割り当てる際、前記依存関係に対応する同期命令をシナリオに埋め込むサブステップと、シナリオに埋め込んだ前記同期命令のうち、冗長な同期命令を除去するサブステップと、を含むことを特徴とする。
以上の発明では、冗長な同期命令を除去することによって、各プロセスが互いにどのようなタイミングで動作するかの自由度が拡張される。これは、無害な非決定性を与えることによって並行プログラムを最適化することを意味し、シナリオという形で一旦逐次化された並行プログラムにおいて、並行性を可能な限り復元することができる。
【００１２】
本発明のプログラム開発支援装置は、前記並行化手段は、前記冗長な同期命令を除去する際、シナリオに埋め込んだ任意の同期命令の作用を抑制し、前記抑制の前と後の各シナリオの間で、前記依存関係を持つ動作が示し得る実行順序が同じかどうかを判断し、前記実行順序が同じである場合は、作用を抑制した前記同期命令を除去するように構成されたことを特徴とする。また、本発明のプログラム開発支援方法は、前記並行化手段が、冗長な同期命令を除去するサブステップは、シナリオに埋め込んだ任意の同期命令の作用を抑制し、前記抑制の前と後の各シナリオの間で、前記依存関係を持つ動作が示し得る実行順序が同じかどうかを判断し、前記実行順序が同じである場合は、作用を抑制した前記同期命令を除去することを特徴とする。
以上の発明では、依存関係を持つ動作の実行順序に影響しない同期命令が除去されるので、並行プログラムの動作の自由度を拡張しながら、依存関係を持つ動作の実行順序は正しく維持される。
【００１３】
本発明のプログラム開発支援装置は、前記並行化手段は、前記冗長な同期命令を除去する際、シナリオに埋め込んだ任意の同期命令の作用を抑制し、前記抑制の前と後の各シナリオの間で、シナリオが等価かどうかを判定する判定手段を含み、前記判定手段は、相互に依存関係を有する部分を含む２つのシナリオそれぞれについて、前記依存関係を有する部分がいつ実行されたかを表すカウンティングトレースの集合を計算する手段と、計算された前記２つの集合を比較し、２つの集合が等しい場合に２つのシナリオが等価であると判断する手段から構成され、シナリオが等価であると判断された場合は、作用を抑制した前記同期命令を除去するように構成されたことを特徴とする。
並行プログラムの開発において、シナリオが等価かどうかの判定は、シナリオの正規化や冗長な同期命令の除去などで用いることができる。本発明では、この等価性の判定を、依存関係を有する部分がいつ実行されたかを表すカウンティングトレースに基づいて行う。ここで、並行プログラムにおいて、依存関係を有する部分同士は実行順序が変わるとバグの原因になり得るが、それ以外の部分は実行順序を自由にしてもバグの原因とはならず、逆に並行プログラムの柔軟性を高める効果がある。本発明では、等価性の判定において依存関係を有する部分だけを問題とすることによって、バグの発生を防止する一方、バグを生じない部分については実行順序の自由度を増やして並行プログラムの柔軟性を高めることができる。
【００１４】
【発明の実施の形態】
次に、本発明の実施の形態であるプログラム開発支援装置（以下「本装置」という）について、図面を参照して説明する。
【００１５】
〔１．構成〕
〔１−１．本装置を実現するためのコンピュータシステムの構成〕
まず、本装置を実現するためのコンピュータシステムの構成例を図１に示す。このコンピュータシステムは、並行プログラムを構成する各プロセスを同時並行的に実行するためのＮ台のプロセッサ２１１，２１２，…，２１Ｎを有し、これら各プロセッサ２１１，２１２，…，２１Ｎには、Ｉ／Ｏインターフェース２２を介して、共有メモリ２３及び周辺装置が接続されている。周辺装置としては、入力装置２４、出力装置２５及び外部記憶装置２６を用いる。
【００１６】
上記の周辺装置のうち、入力装置４は、各種コマンドやデータの入力をする装置で、キーボードとマウスなどのポインティングデバイスを有する。また、出力装置５は、ＣＲＴディスプレイなどの表示画面に、ソースプログラムやデバッグ状況に関する情報等をテキスト又はグラフィック表示することにより、ユーザに提示する装置である。なお、出力装置としては、他にプリンタなどを適宜用いることができる。ユーザは、これら入力装置４及び出力装置５を用いて、対話的にコンピュータを操作することができる。また、外部記憶装置６は、磁気ディスクや光磁気ディスクなどの記録媒体を用いて、ソースプログラムやデバッグ状況に関する情報などを書き込み及び読み出す装置である。
【００１７】
本装置は、上記のようなコンピュータシステムの各種ハードウェア資源をソフトウェアで制御することによって実現されるが、コンピュータシステムや前記ソフトウェアの具体的な構成は種々考えられるので、以下、本装置の各機能を実現する仮想的回路ブロックを用いて本実施形態を説明する。
【００１８】
〔１−２．機能ブロック図に基づく構成〕
すなわち、図２は本装置の構成を示す機能ブロック図である。この図に示すように、本装置は、編集手段１と、作成手段３と、分解手段５と、を有する。このうち編集手段１は、第１の並行プログラム２を作成及び修正するための手段１である。また、作成手段３は、第１の並行プログラム２に基づいて実行のシナリオを作成し、シナリオを表すシナリオ情報４を提供する手段である。また、分解手段５は、正しいと判定されるシナリオを、ループを含まないブロックに階層的に分解することによって、ブロックに分解されたシナリオをブロック間の構造と共に表す構造的シナリオ情報６を提供する手段である。
【００１９】
また、本装置は、解析手段１２と、並行化手段７と、統合化手段８と、生成手段１０と、を有する。このうち解析手段１２は、第１の並行プログラム２を解析することによって第１の並行プログラム２の各部分間に存在する依存関係を抽出し、この依存関係を表す解析情報１３を提供する手段である。また、並行化手段７は、分解されたシナリオを、抽出された依存関係に対応する部分間の実行順序を維持しながら、ブロックを単位として複数のプロセスに割り当てることによって並行化する手段である。また、統合化手段８は、解析情報１３を参照しながら、各プロセスに割り当てられたシナリオをプロセスごとに統合することによって、統合されたプロセスごとのシナリオを表すローカルシナリオ情報９を提供する手段である。また、生成手段１０は、ローカルシナリオ情報９に基づいて第２の並行プログラム１１を生成する手段である。
【００２０】
〔２．全体的な処理手順〕
上記のような構成を有する本装置における全体的な処理手順を図３のフローチャートに示す。
〔２−１．第１の並行プログラムの作成〕
まず、ユーザは、編集手段１を用いて、第１の並行プログラム２を作成する（ステップ１）。ここで、並行プログラムを作成するプログラミング言語は自由に選択することができ、例えば、Ｊａｖａなどの並行プログラミング言語で記述してもよいし、あるいはＣ言語などの逐次プログラミング言語と、μ−ＩＴＲＯＮのようなオペレーティングシステムのシステムコールとを組み合わせることによって記述してもよい。
【００２１】
〔２−２．シナリオの作成〕
次に、作成手段３によって、第１の並行プログラム２を実行した場合のシナリオを作成する（ステップ２）。ここで、シナリオとは、プログラムの挙動を、実行されるプログラム中の命令からなる逐次的な列として表現したものである。
【００２２】
このようなシナリオを作成するには、例えば、テストケースを与えて第１の並行プログラム２を仮想的に実行し、その実行履歴をシナリオとしたり、第１の並行プログラム２が示し得る各部分間の実行順序を、枝別れするグラフの各経路として表し、許容できない実行順序に対応する経路をグラフから削除し、その結果として得られたグラフをシナリオ情報とするなどが考えられる。ここで、グラフに含まれる各経路が個々のシナリオに対応する。
【００２３】
また、このようなシナリオを表現する具体的な形式としては、例えば、状態遷移図形式のシナリオグラフが考えられる。シナリオグラフは、並行プログラムによって実現されるシステムの全体的な状態、すなわちグローバル状態をノードとし、プログラムの各動作はノードを接続するアークで表した有向グラフである。ここで、複数のプロセスから構成された並行プログラムにおいて、グローバル状態とは、個々のプロセスがどの位置を実行しているかの状態及び各プロセスのメモリの状態を組み合わせたものである。
以上のように作成されたシナリオは、シナリオの内容を表すシナリオ情報４として、後のステップに提供される。すなわち、本出願において、「シナリオ」というときは、プログラムが示し得るある１つの命令の列であり、「シナリオグラフ」というときは１又は２以上のシナリオの集合を一体に表したものである。この場合、シナリオグラフ中の１つの経路（パス）が１つのシナリオを表す。また、「シナリオ情報」は、上記のように１又は２以上のシナリオの集合をシナリオグラフなどの形式で表した情報である。
【００２４】
〔２−３．シナリオの挙動の確認〕
このように作成されたシナリオに対して、ユーザが、シナリオで表された並行プログラム２の挙動が仕様通りであって正しいことを確認する（ステップ３）。この確認は、従来から知られたプログラムのテスト方法を用いればよい。正しくないシナリオがある場合は（ステップ４）、シナリオの元となった第１の並行プログラム２にバグがあるので、編集手段１を用いて第１の並行プログラム２を修正したうえ（ステップ１）、再度シナリオを作成して（ステップ２）、正しいことを確認する。シナリオが正しいことが確認された場合（ステップ４）、さらにシナリオを作成するときはシナリオの作成（ステップ２）に戻り、シナリオの作成を終了するときは次のステップ６に進む。
【００２５】
このようにして、複数のシナリオを順次作成する場合、既に作成したシナリオと新たに作成したシナリオで相違している経路を、既に作成したシナリオに付加することによって、複数のシナリオを一体化して単一のシナリオ情報とすることができる。例えば、シナリオグラフでは、２つのシナリオの後半でプログラムの部分間の実行順序が異なっている場合、シナリオグラフを途中から２つに枝別れさせ、異なっているそれぞれの順序に対応した経路を枝別れの先に続けることによって、前記２つのシナリオを単一のシナリオ情報で表すことができる。また、複数のシナリオを作成する場合は、１つのシナリオを作成するごとにその正しさを確認してもよいが、連続して複数作成した後で、正しさの確認を一括して行ってもよい。
【００２６】
〔２−４．依存関係の抽出〕
上記のようにシナリオ情報で表される各シナリオの正しさが確認され、第１の並行プログラム２にバグがないと考えられる場合は、ステップ６において、解析手段１２が、第１の並行プログラム２を解析することによって、第１の並行プログラム２を構成する各命令間の依存関係を抽出する。
【００２７】
ここで、依存関係とは、プログラムの異なった部分同士が相手を前提とする関係であり、データ依存と制御依存とがある。また、依存関係は、プログラムの部分間に相互に存在する、すなわち対称性を持つ関係である。このような依存関係がある２つの命令については、その実行順序によって計算結果が異なる可能性があるため、一方が他方よりも先行して実行されなければならないという制約が存在する。このような制約を先行制約と呼ぶ。このような依存関係および先行制約を抽出するためのアルゴリズムは既に公知であり、具体的には文献「本多弘樹：自動並列化コンパイラ、情報処理Vol.34.No.9,1993」などに紹介されている。
【００２８】
すなわち、まず、どのプロセスが実行されるかが、プロセス間の条件分岐で決定されず、全てのプロセスが実行される場合、依存関係はプロセス間のデータ依存を求めることによって検出できる。データ依存とは、一方の命令が、他方の命令によって提供されるデータに依存する関係である。例えば、図４（ａ）に示すように、共有変数ＭにＸの値を書き込む命令write(M,X)と、同じ共有変数Ｍからデ−タを読み出す命令Y=read(M) の間には、直接的なデータ依存が存在する。
【００２９】
また、図４（ｂ）に示すように、上記の共有変数Ｍに書き込まれた値が一旦別の変数Ｍ２にコピーされ、読み出す命令はこの変数Ｍ２からデータを読み出す場合、書き込む命令と読み出す命令の間には、間接的なデータ依存が存在する。このような直接的なデータ依存や間接的なデータ依存は、各命令がどの変数についてどのような処理を行っているかを辿ることによって抽出することができる。
【００３０】
また、どのプロセスが実行されるかが、プロセス間の条件分岐で決定される場合は、前記のデータ依存に加えて、制御依存も求める必要がある。制御依存とは、一方のプロセスでの条件の評価が真になるまで、他方のプロセスの実行を開始できないという依存関係である。このような制御依存は、各プロセスに含まれる条件分岐命令と各プロセスとの関係を調べることによって検出する。
【００３１】
前記のような、並行プログラムＣの命令間の依存関係の集合をＤ（Ｃ）と表す。すなわち、（ｔｉ，ｔｊ）∈Ｄ（Ｃ）ということは、命令ｔｉとｔｊの間に依存関係が存在することを意味する。また、与えられた並行プログラムＣが示す動作列θにおいて、動作間の先行制約は次のように定義される。すなわち、先行制約を記号”＜＜”で表し、シナリオθのｉ番目の動作をｃ（θ，ｉ）のように表す場合、
c(θ,i) << c( θ,j)iff (θ[i],θ[j])∈Ｄ（Ｃ）and i<j
である。これは、シナリオθのｉ番目とｊ番目の動作が依存関係を持ち、かつ、ｉがｊより大きければ（先行するなら）ｉ番目の動作はｊ番目の動作に対して先行しなければならないという先行制約が存在することを意味する。なお、本発明で「動作」とは、具体的にはプログラムの命令を意味し、例えば、「ａ＝ｂ−１」のような演算と代入の命令や「ａ＝＝ｂ」のような評価などが命令の単位となる。
以上のように抽出された依存関係は、依存関係を表す解析情報１３として、後のステップに提供される。
【００３２】
〔２−５．シナリオの分解〕
正しいことが確認されたシナリオ情報は、分解手段５によって、ループを含まないブロックに階層的に分解される（ステップ７）。ここで、一般に、並行プログラムは永続的に動き続ける場合が多く、並行プログラムに基づくシナリオはループを持つ場合が多い。このため、シナリオの分解では、ループを含まない部分をブロックとし、ループは、このようなブロックの末尾と先頭をつなぐ経路として、ブロック自体とは区別する。また、ループは多重になっている場合があるので、分解は階層的に行われる。
【００３３】
このように分解されるもとのシナリオが、有向グラフであるシナリオグラフとして表現されている場合、分解でできる個々のブロック内は、下位のブロックをノードとするアサイクリックなグラフとして表現できる。このアサイクリックなグラフとは、ループを含まないグラフである。例えば、図５（ａ）に示すシナリオグラフは、図５（ｂ）に示すように、ループを含まないブロックＢ１とそれ以外の部分に分解され、このブロックＢ１がさらに、ループを含まないブロックＢ２とそれ以外の部分に分解される。このようにループを含まないブロックを、以下、アサイクリックブロックと呼ぶ。
【００３４】
また、分解されたシナリオは、図５（ｂ）のようなグラフで表現する以外に、このグラフと等価な下記のような正規表現で表すことも可能である。
t14 + (t1(t2 t3 t4 +
t7 t8(t12 t13 t14)* t9 t10 t11)t5 t6)*
ここで、ｔ１＋ｔ２は「ｔ１又はｔ２」を表し、ｔ１＊はｔ１の０回以上の繰り返しを表す。なお、シナリオを分解する詳細な手順及び正規表現については後述する。
【００３５】
以上のようにシナリオを分解した結果としては、各ブロックの内容を表す情報と、ブロック以外の例えばループやブロック間の上位下位の関係を表す情報が得られ、これらの情報を構造的シナリオ情報と呼ぶ。すなわち、分解手段５からは構造的シナリオ情報６が、後のステップに提供される。
【００３６】
〔２−６．シナリオの並行化〕
続いて、上記のように分解されたシナリオを各ブロックごとに、複数のプロセスに割り当てる処理、すなわち並行化を行なう（ステップ８）。ここでは、プロセスの構造、例えば用いるプロセスの数などは第一の並行プログラム２と同じだと仮定するが、もちろん、プロセスの構造は任意に設定することもできる。
【００３７】
この並行化の際は、プログラム解析情報１３によって表される命令間の依存関係を用いる。すなわち、並行化とは、シナリオのなかで依存関係のない部分同士を相互に並行に動かせるようにすることを意味する。例えば、あるシナリオでは直列関係（ａｂ）にあるプロセスＰ１の命令ａとプロセスＰ２の命令ｂにおいて、ａとｂの間に依存関係がなければ、ａとｂを異なるプロセスに割り当てることによって並行関係（ａ‖ｂ）にすることができる。一方、依存関係を持つ命令同士については、依存関係から導出される先行制約を満足するために、並行化の際、各命令の前後に同期命令を挿入する。
【００３８】
また、並行化手段７は、このように並行化されたシナリオから冗長な同期命令を除去する。ここで、同期命令が冗長か否かの基準は、シナリオからその同期命令を除去しても、除去されたシナリオを並行プログラムとみなして生成されるシナリオの集合が、除去前のシナリオを並行プログラムとみなして生成されるシナリオの集合と等価であるか否かであり、除去しても等価な同期命令は冗長と判断する。このように等価の概念を用いて冗長な同期命令を除去する詳細な手順は後述する。
【００３９】
〔２−７．シナリオの統合化〕
上記のような並行化の結果、各プロセスには、それぞれ異なったブロックから由来するシナリオの部分が、相互に別個独立のまま割り当てられている状態となる。そこで、統合化手段８が、各ブロックを単位として割り当てられているシナリオを、プロセスごとに統合化する（ステップ９）。この統合化の詳細な手順は後述する。また、統合化の結果としては、統合化されたプロセスごとのシナリオを表すローカルシナリオ情報（９）が、後のステップに提供される。
【００４０】
〔２−８．第２の並行プログラムの生成〕
最後に、上記のように統合化されたプロセスごとのローカルシナリオ情報９から、生成手段１０が、第二の並行プログラム１１を生成する（ステップ１０）。ここで生成される第二の並行プログラム１１は、元となったシナリオ情報４で表されるシナリオおよびそのシナリオと等価な挙動のみを再現するものであるから、ステップ２で与えられたシナリオが正しければ（ステップ４）、この第二の並行プログラムも正しいことが保証される。
【００４１】
〔３．詳細な手順〕
次に、シナリオが有向グラフで与えられた場合を例にとり、上記に説明したステップ１〜１０の手順のうち、シナリオの分解（ステップ７）について詳細な手順を説明し、続いて、シナリオの並行化（ステップ８）及びシナリオの統合（ステップ９）についても詳細な手順を説明する。
【００４２】
ここでは、与えられたシナリオは図５（ａ）に示したようなシナリオグラフであり、このシナリオグラフのノ−ドは第１のプログラム２のグロ−バルな実行状態を表し、ノード間のア−クが第１の並行プログラム２内のｔ１やｔ１４などの命令を表す。また、複数のシナリオが１つのシナリオグラフによって表されていて、１つのシナリオはシナリオグラフ上の１つの経路に対応するものとする。
【００４３】
〔３−１．シナリオの分解の詳細な手順〕
〔３−１−１．シナリオグラフの正規化〕
シナリオグラフを分解するには、まず、ユーザの作成したシナリオグラフＳＧから正規表現(regular expression)に変換されたシナリオグラフＳＧr を作成する。ここで、正規表現とは、例えば、ループ部分が０回以上の繰り返しをするというデータの構造であり、正規表現でないシナリオグラフＳＧから正規表現に変換されたシナリオグラフＳＧr を作成することをシナリオグラフの正規化と呼ぶ。このとき、ＳＧとＳＧr は意味的に等価であることが保証できるようにＳＧr を生成する。このように正規化されたシナリオグラフＳＧr はもとのＳＧと等価であるが、階層的な構造を抽出することによって分解することが容易な構造を有する。
【００４４】
ここで、２つのシナリオが意味的に等価であることをシナリオ等価と呼び、また、２つのシナリオが等価である特徴を等価性と呼び、等価性を記号「＝＝＝」で表す。この場合、等価性は次のように定義できる。すなわち、２つのシナリオθ１とθ２がシナリオ等価である（θ１＝＝＝θ２）とは下記の条件が成り立つことである。
（１）任意のｉに対して、あるｊが存在して、
c(θ1,i) = c( θ2,j)であり、かつ
任意のｊに対して、あるｉが存在して、
c(θ2,j) = c( θ1,i)である。
（２）任意のｉ１，ｉ２に対して、あるｊ１，ｊ２が存在して、
c(θ1,i1) = c(θ2,j1) かつ
c(θ1,i2) = c(θ2,j2) かつ
c(θ1,i1) << c( θ1,i2) → c( θ2,j1) << c( θ2,j2))である。
（３）任意のｊ１，ｊ２に対して、あるｉ１，ｉ２が存在して、
c(θ1,i1) = c(θ2,j1) かつ
c(θ1,i2) = c(θ2,j2) かつ
c(θ2,j1) << c( θ2,j2) → c( θ1,i1) << c( θ1,i2))である。
【００４５】
このようなシナリオ等価を前提として、シナリオをグラフで表したシナリオグラフが等価であることをシナリオグラフ等価と呼ぶ。そして、２つのシナリオグラフＳＧ１＝（Ｓ１，Ｔ１，δ１，ｓ０１）とＳＧ２＝（Ｓ２，Ｔ２，δ２，ｓ０２）に対して、ＳＧ１とＳＧ２がシナリオグラフ等価である（ＳＧ１＝＝＝ＳＧ２) とは下記の条件が成り立つことである。
すなわち、任意のＳＧ１のシナリオθ１に対して、あるＳＧ２のシナリオθ２が存在して、θ１＝＝＝θ２であり、かつ任意のＳＧ２のシナリオθ２に対して、あるＳＧ１のシナリオθ１が存在して、θ1 ＝＝＝θ２である。
【００４６】
次に、与えられたシナリオグラフを、上記のような等価性を維持しながら正規化する手順の一例を示す。まず、与えられたシナリオグラフから、全く実行されない場合があるループを、分岐構造などに基づいて検出する。次に、そのループの中で、そのループが実行されない場合も実行されるパスと共有しているアークを検出する。検出されたアークと同じアークを、当該ループに専属のものと持たせることによって、ループを他の部分から独立させる。
【００４７】
より具体的には、シナリオグラフは有限オ−トマトンであり、シナリオグラフの正規化に関しては、有限オ−トマトンから等価な正規表現を生成する公知のアルゴリズムを用いる（参考文献：福村、稲垣／オ−トマトン・形式言語理論と計算論、岩波書店、1982）。なお、このような等価な正規表現に変換されたシナリオグラフは、ループとそれ以外の部分が明確に区分されているので、階層的な構造の抽出が容易である。
【００４８】
〔３−１−２．ブロックへの階層的分解〕
上記のような正規化に続いて、正規なシナリオグラフＳＧr を図５（ｂ）に示すように、ループを含まないブロックに階層的に分解する。このような分解で得られる階層構造に含まれる各階層では、シナリオは下位のブロックをノ−ドとし、ル−プを含まないサブグラフとして表現できる。
【００４９】
すなわち、上記のように正規化されたシナリオを分解するには、シナリオから最も大きなループを探し出し、そのループを、ループを含まないブロックと、そのブロックの末尾と先頭をつなぐ経路とに分ける。そして、このように作られたブロックから次に大きなループを探し出し、このような手続きを、ループが見つからなくなるまで階層的に繰り返せばよい。例えば、図５（ａ）のシナリオが与えられた場合、最大のループとしてｔ１−ｔ２−ｔ３−ｔ４−ｔ５−ｔ６を含むループ構造が取り出され、図５（ｂ）に示すように、この部分がブロックＢ１となる。さらに、ブロックＢ１の中からループｔ１２−ｔ１３−ｔ１４が取り出され、この部分がブロックＢ２となる。
【００５０】
〔３−２．シナリオの並行化の詳細な手順〕
シナリオの並行化（ステップ８）では、上記のような分解で得られた各階層のアサイクリックブロックごとに、下記の手順で並行化を行なう。これは、ル−プを含む場合とそうでない場合を統一的な手順で並行化することは困難だからである。なお、従来の、ス−パ−コンピュ−タのコンパイラにおける逐次プログラム並列化においても同様のアプロ−チが採用されている（参考文献：M. Girkar and C.D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Trans. on Parallel and Distributed Systems, Vol.3, No.2, 1992）。
【００５１】
〔３−２−１．同期動作の挿入〕
例えば、アサイクリックブロックを構成するプロセスＰ１の命令ｔ１１とプロセスＰ２の命令ｔ２１の間に依存関係がなければ、これら２つの命令ｔ１１とｔ２１は、それぞれプロセスに割り当てることによって並行関係（ｔ１１‖ｔ２１）にすることができる。依存関係のない２つのブロックについても同様である。なお、各命令は、第１の並行プログラム２においてどのプロセスに所属するかが決まっているので、シナリオの並行化では、各命令をそれぞれ所属するプロセスに射影することになる。依存関係のある直列関係の命令やブロックを並行化したり、分岐を含むブロックを並行化する場合は、次のように同期命令を用いる。
【００５２】
まず、依存関係のある直列関係の命令やブロックの間に同期命令ｓi を挿入する。例えば、相互に依存関係を持つ動作ｔ１１とｔ２１が、シナリオのあるブロックで直列しているものとする（図６（ａ））。そして、動作ｔ１１とｔ２１の間の依存関係に基づいて、動作ｔ１１が動作ｔ２１に先行しなければならないという先行制約が存在するものとする。この場合、直列している動作ｔ１１とｔ１２の間に同期命令ｓ１を挿入することによって
t11 t21 → t11 s1 t21
とする（図６（ｂ））。また、例えば、ブロックＢ１とＢ２の間に同様の先行制約がある場合も、同期命令ｓ１を挿入して
B1 B2 → B1 s1 B2
とする。
【００５３】
また、各分岐にも同期命令を挿入する。例えば、図７（ａ）の例では、分岐命令による動作ｔ１１の内容に応じて、動作ｔ１２−ｔ１３を含む左側の経路と、動作ｔ２１−ｔ２２を含む右側の経路とに、動作列が分岐する。この場合、図７（ｂ）に示すように、それぞれの経路へ分岐する部分に同期命令ｓ１及びｓ２を挿入し、
t11 (t12 t13 + t21 t22) →
t11 (s1 t12 t13 + s2 t21 t22)
とする。また、例えば、ブロックＢ１における分岐の動作に基づいてブロックＢ２とＢ３とに分岐するような場合も、それぞれの経路へ分岐する部分に、同様に同期命令ｓ１及びｓ２を挿入し、
B1 (B2 + B3) → B1 (s1 B2 + s2 B3)
とする。
【００５４】
〔３−２−２．プロセスへの射影〕
次に、上記のように同期命令を挿入したシナリオを各プロセスに射影する。ここで、射影(projection)とは、各プロセスにシナリオの一部を割り当てることである。ここで、Ｂ｜ＰはブロックＢのプロセスＰへの射影を意味する。
【００５５】
例えば、図６（ｂ）では、同期命令ｓ１を挿入したシナリオに動作ｔ１１とｔ２１が含まれているが、このうち動作ｔ１１をあるプロセスＰ１に割り当て、動作ｔ２１を別のプロセスＰ２に割り当てる場合、図６（ｃ）に示すように、プロセスＰ１では動作ｔ１１に続けて同期命令ｓ１を割り当て、プロセスＰ２では動作ｔ２１の前に同期命令ｓ１を割り当て、
t11 s1 t21 → t11 s1 ‖s1 t21
とする。この場合、プロセスＰ２の同期命令ｓ１は、プロセスＰ１で同期命令ｓ１が実行されるまで待ち状態となるので、プロセスＰ２の動作ｔ２１は必ずプロセスＰ１の動作ｔ１１の実行終了を待って実行が開始される。このため、動作ｔ１１とｔ２１の実行順序は先行制約に合致するように維持される。
【００５６】
また、ブロックＢ１とＢ２の間に先行制約がある場合も同様に、挿入されている同期命令ｓ１を各ブロックＢ１，Ｂ２と共に各プロセスに割り当てることによって、
B1 s1 B2 → (B1｜P1)s1(B2｜P1) ‖(B1 ｜P2)s1(B2｜P2)
とする。
【００５７】
また、図７（ｂ）では、同期命令ｓ１及びｓ２を挿入したシナリオに、動作ｔ１２−ｔ１３を含む左側の経路と、動作ｔ２１−ｔ２２を含む右側の経路が含まれているが、この２つの経路をそれぞれ別々のプロセスＰ１とＰ２に割り当てるものとする。この場合、図７（ｃ）に示すように、プロセスＰ１では、動作ｔ１１による分岐のうち、プロセスＰ１で実行する左側の経路に同期命令ｓ１を挿入し、右側の経路は同期命令ｓ２を最後に終了するように構成する。プロセスＰ２では、これと反対に、同期命令ｓ１の経路は終了するように構成し、同期命令ｓ２に続けて動作ｔ２１以降の右側の経路を構成することによって、
t11(s1 t12 t13 + s2 t21 t22) →
t11(s1 t12 t13 + s2)‖(s1 + s2 t21 t22)
とする。この場合、プロセスＰ１で同期命令ｓ１に続いて動作ｔ１２以下が実行される場合は、プロセスＰ２は同期命令ｓ１で終了し、また、プロセスＰ２で同期命令ｓ２に続いて動作ｔ２１以下が実行される場合は、プロセスＰ１は同期命令ｓ２で終了する。このため、プロセスＰ１とＰ２を併せて観察しても、図７（ｂ）で示した右側と左側の双方の経路が同時に実行されることはなく、もとのシナリオに含まれていた分岐の構造が保存されている。
【００５８】
また、ブロックＢ１における分岐の動作に基づいてブロックＢ２とＢ３とに分岐するような場合も同様に、挿入されている同期命令ｓ１及びｓ２をブロックと共にそれぞれのプロセスへ割り当て、
B1 (s1 B2 + s2 B3) →
(B1 ｜P1)(s1(B2 ｜P1) + s2(B3 ｜P1))‖
(B1 ｜P2)(s1(B2 ｜P2) + s2(B3 ｜P2))
とする。この場合は、同期命令ｓ１に続いてブロックＢ２が実行される場合、ブロックＢ２の各部分のうちプロセスＰ１ではプロセスＰ１に射影された部分が実行され、プロセスＰ２ではプロセスＰ２に射影された部分が実行される。また、同期命令ｓ２に続いてブロックＢ３が実行される場合、ブロックＢ３の各部分のうちプロセスＰ１ではプロセスＰ１に射影された部分が実行され、プロセスＰ２ではプロセスＰ２に射影された部分が実行される。
【００５９】
上記のような射影を行った時点では、各プロセスには、第１の並行プログラム２において当該プロセスに対応する命令が割り当てられているほか、ブロックに挿入された全ての同期命令が、全てのプロセスに割り当てられている。
【００６０】
〔３−２−３．冗長な同期命令の除去〕
続いて、割り当てられた全ての同期命令の中から、各アサイクリックブロックごとに冗長な同期命令を抽出しそれを除去する。たとえば、図８（ａ）のシナリオをプロセスＰ１，Ｐ２へ射影し、
(s1 a s2 + s3 s4 a) ‖(s1 s2 b + s3 b s4)
とした結果を図８（ｂ）に示す。この例では、命令ａとｂに依存関係があることから同期命令ｓ１，ｓ２，ｓ３，ｓ４が用いられているが、実際には図８（ａ）のシナリオではａ→ｂという順序も、逆のｂ→ａという順序も双方許容されているので、同期命令ｓ１，ｓ２，ｓ３，ｓ４は冗長である。このため、これら同期命令を除去することによって図８（ｃ）の状態とすることができる。
【００６１】
〔３−２−３−１．原始的な手順〕
このような冗長な同期命令をシナリオグラフＳＧから除去する手順は、原始的には次のように表現することができる。すなわち、任意の同期命令ｓを選択し、それを除去する前のグラフＳＧと除去した後のグラフＳＧ’を比較し、両者がシナリオグラフ等価（ＳＧ＝＝＝ＳＧ’）であれば同期命令ｓを削除する、という処理を繰り返し、全ての同期命令についてこの処理を繰り返しても同期命令が１つの除去できなくなった時点で処理を終了する。
【００６２】
〔３−２−３−２．シナリオグラフ等価を判定する手順〕
上記の手順では、選択した同期命令を除去する前後のシナリオグラフが等価かどうかを判定する必要があり、本実施形態では、シナリオグラフの等価性の判定に次のようなカウンティングトレ−スを用いる。カウンティングトレースとは、シナリオにおいてどの動作が何度行われ、依存関係を持つ動作がいつ行われたかを示す情報である。ここで、与えられたシナリオθのカウンティングトレ−スｃｔ（θ）は以下のように定義される。
ct( θ) = (<動作の生起カウンタの組>,< 先行制約条件の集合>)
この定義において、動作の生起カウンタは、そのシナリオ中で当該動作が何回生起したかを表す項目であり、例えば、（ａ，ｋ）のような表現は、シナリオθにおいて動作ａがｋ回生起したことを意味する。また、先行制約条件は、依存関係を持つ動作がいつ生起したかを表す。例えば、並行プログラムＣが動作ａ→ｂ→ｃ→ｂ→ａの順に実行され、この実行順序を表すシナリオθ＝ａｂｃｂａに対して、依存関係の集合Ｄ（Ｃ）が依存関係（ａ，ｃ）を含む場合、θのカウンティングトレ−スは、
となる。この例において、動作の生起カウンタの組｛（ａ，２），（ｂ，２），（ｃ，１）｝は、シナリオθ＝ａｂｃｂａにおいて、動作ａが２回、動作ｂが２回、動作ｃが１回生起したことを意味し、１つ目の先行制約条件ｃ（θ，１）＜＜ｃ（θ，３）は、シナリオθにおいて、依存関係を持つ２つの動作ａ，ｃがそれぞれ１番目と３番目の動作として生起したことを意味し、また、２つ目の先行制約条件ｃ（θ，３）＜＜ｃ（θ，５）は、動作ｃ，ａがそれぞれ３番目と５番目の動作として生起したことを意味している。
【００６３】
このようなカウンティングトレースの集合をカウンティングトレ−ス集合と呼び、アサイクリックなシナリオグラフＳＧにおいて、カウンティングトレ−ス集合ｃｔｓｅｔ（ＳＧ）は以下のように定義される。
ctset(ＳＧ) = {ct(θ) ｜θはＳＧのシナリオ}
この定義は、シナリオグラフＳＧに基づくカウンティングトレース集合ｃｔｓｅｔ（ＳＧ）が、シナリオグラフＳＧの全てのシナリオθのカウンティングトレースｃｔ（θ）からなることを意味している。そして、アサイクリックなシナリオグラフＳＧにおいて、任意のシナリオは有限なので、このシナリオグラフＳＧを並行プログラムＣとみなし、ｃｔｓｅｔ（Ｃ）を計算することが可能である。ここで、アサイクリックなシナリオグラフＳＧ１とＳＧ２に対して、シナリオグラフ等価とカウンティングトレース集合との間には、下記の性質が成り立つ。
ＳＧ1 === ＳＧ2 iff ctset(C1)=ctset(C2)
これは、２つのシナリオグラフＳＧ１とＳＧ２の間でそれぞれに基づくカウンティングトレース集合ｃｔｓｅｔ（Ｃ１）とｃｔｓｅｔ（Ｃ２）が同じであれば、２つのシナリオグラフＳＧ１とＳＧ２は等価であることを意味する。
【００６４】
〔３−２−４．冗長な同期命令の除去を効率的に行う手順〕
シナリオグラフ等価を判定する上記のような手法を応用して、冗長な同期命令の除去を効率的に行う手順を次に示す。なお、ここでは、依存関係を有する動作ｔ１とｔ２の間に同期命令ｓｙｎｃ（ｓ１）の挿入されたアサイクリックブロックＳＧn （図９（ａ））から冗長な同期命令を除去するものとする。まず、ＳＧn をプロセスＰ１とＰ２に射影する。なお、射影されたプロセスは、並行プログラムＣn とみなすことができる。まず、冗長な同期命令の除去を効率的に行う手順を図１０に示す。
〔３−２−４−１．ダミー動作の挿入〕
図１０に示す手順では、まず、各プロセスＰｉに挿入してある各同期命令ｓｙｎｃ（ＩＤ）に１対１に対応させて、ダミー動作ｎｓｙｎｃ（Ｐｉ，ＩＤ）を挿入する（ステップ１０１）。ダミー動作とは、同期する命令である同期命令に対して、同期しない命令であり、言い換えれば、同期命令による同期を解除する動作である。このようなダミー動作は、例えば、同期命令の直前に、当該同期命令の直後へ選択的にジャンプする命令を挿入することによって実現する。例えば、図９（ａ）に示したシナリオグラフについては、各プロセスＰ１及びＰ２に割り当てて並行化する際、同期命令ｓｙｎｃ（ｓ１）の直前に、当該同期命令ｓｙｎｃ（ｓ１）をスキップしてその直後にジャンプするダミー動作ｎｓｙｎｃ（Ｐ１，ｓ１）及びｎｓｙｎｃ（Ｐ２，ｓ１）を各プロセスに挿入する（図９（ｂ））。このようなダミー動作を挿入したシナリオグラフをＳＧe とする。また、このように挿入した全てのダミー動作は、記録用の集合ＡＮＳに記録しておく（ステップ１０２）。
【００６５】
〔３−２−４−２．状態空間の生成〕
次に、上記のようにダミー動作を挿入したシナリオグラフＳＧe を、並行プログラムＣe とみなし、並行プログラムＣe が示し得る動作列の集合を表す状態空間ＳＳ（Ｃｅ）を生成する（ステップ１０３／図９（ｃ））。ここで、並行プログラムＣについて、状態空間ＳＳ（Ｃ）とは、下記に定義する状態遷移グラフＳＳ（Ｃ）＝（Ｓ，Ｔ，δ，ｍ０）である。
ＳはＣのグローバル状態の集合
ＴはＣの命令の集合
δは状態遷移関係。すなわち、この状態遷移関係δの要素（ｍ，ｔ，ｍ’）は、グローバル状態ｍで命令ｔが実行されるとグローバル状態ｍ’になることを意味する。
ｍ０はＣの初期グローバル状態
なお、シナリオグラフＳＧ＝（Ｓ，Ａ，δ’，ｓ０）は並行プログラムＣの状態空間ＳＳ（Ｃ）＝（Ｓ，Ａ，δ，ｓ０）のサブグラフである。すなわち、δ’がδの部分集合である。
【００６６】
〔３−２−４−３．違反パスの検出〕
続いて、生成された状態空間ＳＳ（Ｃｅ）から、カウンティングトレース集合ｃｔｓｅｔ（Ｃｎ）に含まれないカウンティングトレースｃｔ（θ）を生じる違反パスθ、すなわち先行制約に反するまたはデッドロックする違反パスθを検出する（ステップ１０４）。図９（ｃ）では、違反パスθを太線及び×印で示す。なお、ｃｔｓｅｔ（Ｃｎ）はダミー動作挿入前のシナリオグラフに対応するカウンティングトレース集合であり、違反パスθを検出する際に作成するか、それ以前に作成して保存しておく。
【００６７】
違反パスθが検出された場合（ステップ１０５）、この違反パスθをルート側に向かって遡り、遡る経路の最後に登場するダミー動作ｎｓｙｎｃ（Ｐｉ，ＩＤ）を検出する（ステップ１０６／図９（ｃ））。すなわち、違反パスθはダミー動作ｎｓｙｎｃ（Ｐｉ，ＩＤ）の挿入が原因で発生したと考えられることから、同期命令ｓｙｎｃ（ＩＤ）は不可欠であり、冗長でないことが判断できる。図９（ｃ）の例では、動作ｎｓ２１が、正しい動作からの逸脱(deviation) を生じさせたダミー動作として検出されている。
【００６８】
このように検出されたダミー動作は、記録用の集合ＤＮＳに追加する（ステップ１０７）。また、そのダミー動作をシナリオグラフＳＧe から除去（ステップ１０８）したうえで状態空間ＳＳ（Ｃe ）を再度生成するか、状態空間のうちそのダミー動作から始まる部分を枝刈りする。そのうえで再び違反パスθの検出からの手順を繰り返し、違反パスθが検出されなくなった時点で（ステップ１０５）以下の手順へ進む。
【００６９】
〔３−２−４−４．冗長性の判断〕
違反パスθが検出されなくなった時点では、それまでに検出された全てのダミー動作が集合ＤＮＳに含まれている。その結果、挿入した全てのダミー動作の集合ＡＮＳから、検出されたダミー動作の集合ＤＮＳを除いたＡＮＳ−ＤＮＳは、挿入したが違反パスを発生させなかったダミー動作の集合となる。そのようなダミー動作に対応する同期命令は、実際に削除してもシナリオグラフのカウンティングトレース集合には影響を与えない。
【００７０】
したがって、ダミー動作ｎｓｙｎｃ（Ｐｉ，ＩＤ）がＡＮＳ−ＤＮＳに含まれるならば、そのプロセスＰｉに挿入されている同期命令ｓｙｎｃ（ＩＤ）は冗長であるからシナリオグラフから除去する（ステップ１０９）。このように冗長な同期命令をすべて並行プログラムＣｎから除去することによって、並行プログラムＣｏが最終的に得られたとする。このとき、挿入した全ての同期命令を持ったままの並行プログラムＣｎと、冗長な同期命令を除去した並行プログラムＣｏはカウンティングトレース集合が共通することからシナリオグラフ等価であり、ＳＳ（Ｃｏ）＝＝＝ＳＳ（Ｃｎ）が満たされる。
【００７１】
〔３−３．統合化の詳細な手順〕
続いて、分解された各階層のブロックごとに並行化されたシナリオを、各プロセスごとに１つのシナリオに統合する。
【００７２】
〔３−３−１．ブロックの埋め込み〕
統合の際は、まず、下位の階層のブロックの詳細を上位の階層に埋め込む。例えば、
B1 = a1 (B2 ｜P1) a2‖b1 (B2｜P2) b2
B2 = a3 ‖b3
のとき、下位階層のブロックに関する
B2｜P1 = a3 、B2｜P2 = b3
を代入すると、全体として
B1 = a1 a3 a2 ‖b1 b3 b2
になる。
【００７３】
〔３−３−２．ループの展開〕
続いて、ブロックに対するループを、そのブロックの内側の各プロセスのループとする。例えば、
（ａ‖ｂ）＊ → ａ＊‖ｂ＊
とする。
【００７４】
〔４．具体例〕
以下に、本実施形態を並行プログラムを適用する場合の具体例を、図３に示すフローチャートの各ステップにしたがって説明する。ここで対象とするのは共有変数型の並行プログラムＣであり、この並行プログラムＣは少なくとも、２つのプロセスＰ１，Ｐ２から構成され、共有メモリを用いる２つの共有変数ｍ１，ｍ２を読み書きするものとする。
【００７５】
〔４−１．並行プログラムの作成〕
この具体例では、並行プログラムＣ＝Ｐ１‖Ｐ２を作成したとする（ステップ１）。このプログラムの命令間の依存関係の集合Ｄ（Ｃ）には、変数ｍ１を介したデータ依存に基づく依存関係（ａ２，ｂ２）と、変数ｍ２を介したデータ依存に基づく依存関係（ａ３，ｂ３）が含まれる。
【００７６】
m1 = 0 ; m2 = 0 ;
P1:
while(true){
a1: v11 = 1 ;
a2: write(m1,v11) ;
a3: v12 = read(m2) ;
}
P2:
while(true){
b1: v21 = 2 ;
b2: v22 = read(m1) ;
b3: write(m2,v21) ;
}
〔４−２．シナリオの作成〕
上記のような並行プログラムＣから、作成手段３を用いてシナリオを作成する（ステップ２）。ここでは、複数のシナリオをまとめたシナリオグラフ（図１１（ａ））が作成されたものとする。
【００７７】
〔４−３．シナリオの挙動の確認〕
ユーザは、このシナリオグラフ上の各シナリオは正しいことを確認し（ステップ３）、バグがあればステップ１に戻る（ステップ４）。ここでは、シナリオにはバグは発見されず、依存関係の抽出（ステップ６）に続いてシナリオの分解（ステップ７）が行われるものとする。
【００７８】
〔４−４．シナリオの分解〕
シナリオの分解（ステップ６）では、シナリオグラフの正規化と階層構造の抽出が行われる。すなわち、まず、シナリオグラフ（図１１（ａ））を正規化することによって正規表現に変換された次のシナリオを得る。ここで、ａ＊は「ａの０回以上の繰り返し」、ａ＋ｂは「ａまたはｂを実行する」を意味する。
ＳＧr=(b1(a1 a2 a3)* a1(a2 b2 + b2 a2)b3 a3)*
この正規表現に変換されたシナリオを等価なグラフで表したシナリオグラフを図１１（ｂ）に示す。正規表現に変換されたシナリオ
(b1(a1 a2 a3)* a1(a2 b2 + b2 a2)b3 a3)*
は以下のような階層的な構造を有する各ブロックに分解することができる。ここで、Ｂ１＊およびＢ２＊を１つの要素とみなせば、各階層の個々のブロックはル−プ構造を含まない。
ＳＧr = B1*
B1 = b1 B2* a1(a2 b2 + b2 a2)b3 a3
B2 = a1 a2 a3
〔４−５．シナリオの並行化〕
続いて、このように分解されたブロックを単位として、並行化を行なう（ステップ８）。この例では、ブロックＢ２は、
B2 = a1 a2 a3 ‖ε( εは空列の意味）
であり、プロセスＰ１の動作しか含まないので並行化の必要はない。一方、ブロックＢ１は次のように並行化される。まず、ブロックＢ１には同期命令ｓ１，ｓ２，ｓ３，ｓ４，ｓ５，ｓ６を導入する。
B1 = b1 B2* s1 a1(s2 a2 s3 b2 + s4 b2 s5 a2)b3 s6 a3
続いて、このように同期命令ｓ１〜ｓ６を挿入したブロックＢ１をプロセスＰ１，Ｐ２に射影する。
さらに、冗長な同期命令を除去する。ここで、(s2 a2 s3 b2 + s4 b2 s5 a2) に関しては、
(s2 a2 s3 + s4 s5 a2) ‖(s2 s3 b2 + s4 b2 s5) → a2 ‖b2
と簡約化できる。すなわち、同期命令ｓ２，ｓ３，ｓ４，ｓ５は冗長であるため除去される。この結果、ブロックＢ１の最終的な正規表現は下記のようになる。
B1 =(B2 ｜P1)* s1 a1 a2 s6 a3 ‖b1(B2 ｜P2)* s1 b2 b3 s6
〔４−６．シナリオの統合〕
次に、各ブロックごとに各プロセスに割り当てられているシナリオを統合化する。この統合化では、下位のブロックＢ２の内容を、上位の階層のブロックＢ１に埋め込むことによって、
ＳＧr = ((a1 a2 a3)* s1 a1 a2 s6 a3 ‖b1 s1 b2 b3 s6)*
となる。また、ル−プの展開を行なうことによって、
ＳＧr =
((a1 a2 a3)* s1 a1 a2 s6 a3)* ‖(b1 s1 b2 b3 s6)*
となる。このような統合化によって最終的に生成されたシナリオをシナリオグラフで表すと図１１（ｃ）のようになる。ここで、正規表現をそのままグラフで表したものは多少冗長性があるので、一部最適化されている。
【００７９】
〔４−７．第２の並行プログラムの生成〕
最後に、図１１（ｃ）に示したシナリオグラフから、下記の並行プログラムＣ＝Ｐ１‖Ｐ２を生成する。
【００８０】
〔５．効果〕
以上説明したように、本実施形態では、正しいことが確認されたシナリオという形で、並行プログラムを一旦逐次化し、このシナリオに基づいて並行プログラムを再び生成することによって並行プログラムの信頼性の向上させる。その際、シナリオを一旦、ループを含まないブロックに階層的に分解する。そして、分解されたブロックごとに各プロセスに割り当てて並行化し、プロセスごとに再び統合化して並行プログラムを生成する。このため、構造が複雑な並行プログラムについても、ブロックに分解して処理することによって逐次プログラミングと同程度の容易さで開発することが可能となる。また、分解された個々のブロックはループや階層構造を含まないので、効率的に処理でき、並行プログラム全体として効率的に開発を行うことができる。
【００８１】
特に、本実施形態では、シナリオを正規化することによって正規表現に変換されたシナリオとし、正規表現に変換されたシナリオは階層的に分解することが容易である。このため、並行プログラムの分解が効率化される。
【００８２】
また、本実施形態では、同期命令を埋め込みながらシナリオをプロセスに割り当てるので、プロセス間において各部分の実行タイミングが、依存関係に基づく先行制約に合致するように制御され、最終的に得られる並行プログラムの信頼性が確保される。
【００８３】
また、本実施形態では、冗長な同期命令を除去することによって、各プロセスが互いにどのようなタイミングで動作するかの自由度が拡張される。これは、無害な非決定性を与えることによって並行プログラムを最適化することを意味し、シナリオという形で一旦逐次化された並行プログラムにおいて、並行性を可能な限り復元することができる。
【００８４】
また、本実施形態では、依存関係を持つ動作の実行順序に影響しない同期命令が除去されるので、並行プログラムの動作の自由度を拡張しながら、依存関係を持つ動作の実行順序は正しく維持される。
【００８５】
〔６．他の実施の形態〕
なお、本発明は上記実施の形態に限定されるものではなく、次に例示するような他の実施形態も含むものである。例えば、上記実施形態を実現するために用いるコンピュータの構成について、図１に示した構成例はマルチＣＰＵであるが、本発明は他の構成のコンピュータシステム上に実現してもよく、例えば、共有メモリを有する並列計算機、共有メモリを有しない並列計算機、分散ネットワーク計算機システム、単一ＣＰＵ計算機をマルチタスクシステムとしたもの、などが考えられる。
【００８６】
また、上記実施形態では、依存関係の抽出は、シナリオを分解する前に行ったが、依存関係の抽出はシナリオを分解した後に行ってもよい。また、上記実施形態では、シナリオの形式としてシナリオグラフを用いたが、シナリオの形式は自由であり、テキストやフローチャート形式など所望の形式のシナリオを用いることができる。また、上記実施形態で示した並行プログラムやシナリオは例示に過ぎず、用いる言語、表現形式、複雑さなどは自由に選択することができる。
【００８７】
また、本発明は、本発明の作用を実現するためのソフトウェアによって実現することが一般的と考えられるが、そのようなソフトウェアを記録した記録媒体も本発明の一態様である。
【００８８】
【発明の効果】
以上説明したように、複雑な構造の並行プログラムについても、優れた信頼性と効率で開発を行うことができるので、プログラミングの生産性と精度が大幅に向上する。
【図面の簡単な説明】
【図１】本発明の実施の形態の実現に用いるコンピュータシステムのハードウェア構成を示す図
【図２】本発明の実施の形態の構成を示す機能ブロック図
【図３】本発明の実施の形態における処理手順を示すフローチャート
【図４】本発明の実施の形態において、データ依存の例を示す図
【図５】本発明の実施の形態におけるシナリオの分解を例示する図
【図６】本発明の実施の形態において、シナリオに同期命令を挿入し、各プロセスに割り当てる例を示す図
【図７】本発明の実施の形態において、シナリオに同期命令を挿入し、各プロセスに割り当てる他の例を示す図
【図８】本発明の実施の形態において、シナリオに挿入した同期命令が冗長なものとして除去される状態を示す図
【図９】本発明の実施の形態において、シナリオグラフにダミー動作を挿入し、違反パスが発生する状態を示す図
【図１０】本発明の実施の形態において、冗長な同期命令を効率的に除去する手順を示すフローチャート
【図１１】本発明の実施の形態における具体例を示す図
【符号の説明】
１：編集手段
２：第１の並行プログラム
３：作成手段
４：シナリオ情報
５：分解手段
６：構造的シナリオ情報
７：並行化手段
８：統合化手段
９：ローカルシナリオ情報
１０：生成手段
１１：第二の並行プログラム
１２：解析手段
１３：解析情報
２１：プロセッサ
２２：Ｉ／Ｏインタフェイス
２３：共有メモリ
２４：入力装置
２５：出力装置
２６：外部記憶装置
【発明の属する技術分野】
本発明は、並行プログラムを開発する技術の改良に関し、より具体的には、複雑な並行プログラムについても優れた信頼性と効率で作成できるようにしたものである。
【０００２】
【従来の技術】
並行プログラムは、複数のプロセスが同時並行的に動作するプログラムであり、別々に動くプロセス間の相互関係によって全体の動作が決まるという複雑さがある。そのため、並行プログラムの作成は、プロセスが単一の流れに従って順次動作をする逐次プログラムに比べて困難である。特に、並行プログラムの挙動は、どのプロセスのどの部分がどのようなタイミングで実行されるかに応じて、実行ごとに非決定的に異なる。この結果、並行プログラムのバグには再現性が乏しく、また、テストするテストケースも極めて多数となるため、テストとデバッグが非常に困難である。
【０００３】
このような並行プログラムの作成を支援し、並行プログラムの信頼性を高める技術として、超逐次プログラミングが知られている（特開平８−１６４２９）。この技術では、並行プログラムを一旦逐次化して超逐次プログラムを作成する。超逐次プログラムとは、もとの並行プログラムをその並行構造に関する情報を保ちながら逐次化したプログラムである。そして、このような超逐次プログラムに対してプログラミング、テスト、デバッグを行い、その結果に基づいて超逐次プログラムを再び並行化することによって信頼性の高い並行プログラムを作成することができる。
【０００４】
例えば、並行プログラムにテストケースを与えるなどしてテストし、このテストの際の実行ログのうち、バグがないと判定された正しい実行ログを、もとの並行プログラムを一旦逐次化した超逐次プログラムの一種とみなす。そして、このような正しい実行ログを複数マージすることによって、超逐次プログラムの正しい振る舞いを表すシナリオグラフを作る。このシナリオグラフを、部分間の実行順序を指定する同期命令と共に、複数のプロセスに部分ごとに割り当てることによって再び並行化し、並行プログラムを作成する。
【０００５】
また、本出願人が出願した他の技術では、並行プログラムを、実行制御の単位となるセクションに分け、セクション間の正しい実行順序をシナリオグラフの経路で表す。この経路に含まれる個々の動作を、動作間の実行順序を指定する同期命令と共に各プロセスに割り当てることによって、正しい振る舞いを示す並行プログラムを作成する。なお、並行プログラムには違った実行順序を表すいくつかの経路が含まれることがあるが、経路ごとの実行結果が同じになる場合のようにシナリオグラフと等価な経路を自動的に復元することによって、生成される並行プログラムの振る舞いに柔軟性が増え、実行効率が向上する。
【０００６】
【発明が解決しようとする課題】
しかしながら、これらの従来技術では、プログラムの正しい振る舞いをシナリオグラフで表す際に、単一の階層のみを持つ平面的な構造のシナリオグラフを用いる。すなわち、このシナリオグラフは、プログラムの各部分をアークで表し、各状態を表すノードの間をアークで接続することによって、プログラムの部分間の実行順序を、平面的な構造の状態遷移グラフで表したものである。そして、ループや階層構造のような複雑な構造を平面的な構造のシナリオグラフで表そうとすると、構造の複雑さに応じてシナリオグラフが複雑で大規模なものとなるので、処理のアルゴリズムが複雑化したり処理効率が悪化するだけでなく、シナリオグラフ自体も理解しづらいものとなる。このため、上記のような従来技術は複雑な並行プログラムに適用することが困難という問題点があった。
【０００７】
本発明は、上記のような従来技術の問題点を解決するために提案されたもので、その目的は、複雑な並行プログラムについても優れた信頼性と効率で作成できる技術を提供することである。
【０００８】
上記の目的を達成するため、本発明は、入力装置及び記憶装置を有するコンピュータに、編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段を構成することによって実現され、前記入力装置が入力した情報に基づいて、前記編集手段が第１の並行プログラムを作成し、前記第１の並行プログラムを前記記憶装置が記憶し、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段が第２の並行プログラムを生成し、前記第２の並行プログラムを前記記憶装置が記憶するプログラム開発支援装置において、前記第１の並行プログラムから実行のシナリオを作成する前記作成手段と、前記第１の並行プログラムを解析することによって、前記第１の並行プログラムの部分間に存在する依存関係を抽出する前記解析手段と、前記シナリオを、ループを含まないブロックに階層的に分解する前記分解手段と、前記依存関係に基づいて、前記分解されたシナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化する前記並行化手段と、各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化する前記統合化手段と、統合化されたプロセスごとのシナリオから第２の並行プログラムを生成する前記生成手段と、を有することを特徴とする。また、本発明は、入力装置及び記憶装置を有するコンピュータに構成された編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段によって実現され、前記入力装置が入力した情報に基づいて、前記編集手段が第１の並行プログラムを作成し、前記第１の並行プログラムを前記記憶装置が記憶し、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段が第２の並行プログラムを生成し、前記第２の並行プログラムを前記記憶装置が記憶するプログラム開発支援方法において、前記作成手段が、前記第１の並行プログラムから実行のシナリオを作成するステップと、前記解析手段が、前記第１の並行プログラムを解析することによって、第１の並行プログラムの部分間に存在する依存関係を抽出するステップと、前記分解手段が、前記シナリオを、ループを含まないブロックに階層的に分解するステップと、前記並行化手段が、前記依存関係に基づいて、分解された前記シナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化するステップと、前記統合化手段が、各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化するステップと、前記生成手段が、統合化されたプロセスごとのシナリオから第２の並行プログラムを生成するステップと、を含むことを特徴とする。また、本発明は、入力装置及び記憶装置を有するコンピュータに、編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段を実現させるソフトウェアであって、前記入力装置から入力された情報に基づいて、前記編集手段に第１の並行プログラムを作成させ、前記第１の並行プログラムを前記記憶装置に記憶させ、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段に第２の並行プログラムを生成させ、前記第２の並行プログラムを前記記憶装置に記憶させるプログラム開発支援用ソフトウェアを記録した記録媒体において、前記プログラム開発支援用ソフトウェアは、前記作成手段に、前記第１の並行プログラムから実行のシナリオを作成させ、前記解析手段に、前記第１の並行プログラムを解析させることによって、前記第１の並行プログラムの部分間に存在する依存関係を抽出させ、前記分解手段に、前記シナリオを、ループを含まないブロックに階層的に分解させ、前記並行化手段に、前記依存関係に基づいて、分解された前記シナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化させ、前記統合化手段に、各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化させ、前記生成手段に、統合化されたプロセスごとのシナリオから第２の並行プログラムを生成させることを特徴とする。
以上の発明では、正しいことが確認されたシナリオという形で、並行プログラムを一旦逐次化し、このシナリオに基づいて並行プログラムを再び生成することによって並行プログラムの信頼性を向上させる。その際、シナリオを一旦、ループを含まないブロックに階層的に分解する。そして、分解されたブロック若しくは前記ブロックに属する命令を各プロセスに割り当てて並行化し、プロセスごとに再び統合化して並行プログラムを生成する。分解された個々のブロックはループや階層構造を含まないので、効率的に並行化処理でき、並行プログラム全体として効率的に開発を行うことができる。
【０００９】
本発明のプログラム開発支援装置は、前記分解手段は、前記作成手段から与えられたシナリオを正規化する手段を有することを特徴とする。
以上の発明では、シナリオを正規化することによって正規表現に変換されたシナリオとし、正規表現に変換されたシナリオは階層的に分解することが容易である。このため、並行プログラムの分解が効率化される。
【００１０】
本発明のプログラム開発支援装置は、前記並行化手段は、シナリオをプロセスに割り当てる際、前記依存関係に対応する同期命令をシナリオに埋め込むように構成されたことを特徴とする。
以上の発明では、同期命令を埋め込みながらシナリオをプロセスに割り当てるので、プロセス間において各部分の実行タイミングが、依存関係に基づく先行制約に合致するように制御され、最終的に得られる並行プログラムの信頼性が確保される。
【００１１】
本発明のプログラム開発支援装置は、前記並行化手段は、シナリオに埋め込んだ前記同期命令のうち、冗長な同期命令を除去するように構成されたことを特徴とする。また、本発明のプログラム開発支援方法は、前記並行化手段が並行化するステップは、シナリオをプロセスに割り当てる際、前記依存関係に対応する同期命令をシナリオに埋め込むサブステップと、シナリオに埋め込んだ前記同期命令のうち、冗長な同期命令を除去するサブステップと、を含むことを特徴とする。
以上の発明では、冗長な同期命令を除去することによって、各プロセスが互いにどのようなタイミングで動作するかの自由度が拡張される。これは、無害な非決定性を与えることによって並行プログラムを最適化することを意味し、シナリオという形で一旦逐次化された並行プログラムにおいて、並行性を可能な限り復元することができる。
【００１２】
本発明のプログラム開発支援装置は、前記並行化手段は、前記冗長な同期命令を除去する際、シナリオに埋め込んだ任意の同期命令の作用を抑制し、前記抑制の前と後の各シナリオの間で、前記依存関係を持つ動作が示し得る実行順序が同じかどうかを判断し、前記実行順序が同じである場合は、作用を抑制した前記同期命令を除去するように構成されたことを特徴とする。また、本発明のプログラム開発支援方法は、前記並行化手段が、冗長な同期命令を除去するサブステップは、シナリオに埋め込んだ任意の同期命令の作用を抑制し、前記抑制の前と後の各シナリオの間で、前記依存関係を持つ動作が示し得る実行順序が同じかどうかを判断し、前記実行順序が同じである場合は、作用を抑制した前記同期命令を除去することを特徴とする。
以上の発明では、依存関係を持つ動作の実行順序に影響しない同期命令が除去されるので、並行プログラムの動作の自由度を拡張しながら、依存関係を持つ動作の実行順序は正しく維持される。
【００１３】
本発明のプログラム開発支援装置は、前記並行化手段は、前記冗長な同期命令を除去する際、シナリオに埋め込んだ任意の同期命令の作用を抑制し、前記抑制の前と後の各シナリオの間で、シナリオが等価かどうかを判定する判定手段を含み、前記判定手段は、相互に依存関係を有する部分を含む２つのシナリオそれぞれについて、前記依存関係を有する部分がいつ実行されたかを表すカウンティングトレースの集合を計算する手段と、計算された前記２つの集合を比較し、２つの集合が等しい場合に２つのシナリオが等価であると判断する手段から構成され、シナリオが等価であると判断された場合は、作用を抑制した前記同期命令を除去するように構成されたことを特徴とする。
並行プログラムの開発において、シナリオが等価かどうかの判定は、シナリオの正規化や冗長な同期命令の除去などで用いることができる。本発明では、この等価性の判定を、依存関係を有する部分がいつ実行されたかを表すカウンティングトレースに基づいて行う。ここで、並行プログラムにおいて、依存関係を有する部分同士は実行順序が変わるとバグの原因になり得るが、それ以外の部分は実行順序を自由にしてもバグの原因とはならず、逆に並行プログラムの柔軟性を高める効果がある。本発明では、等価性の判定において依存関係を有する部分だけを問題とすることによって、バグの発生を防止する一方、バグを生じない部分については実行順序の自由度を増やして並行プログラムの柔軟性を高めることができる。
【００１４】
【発明の実施の形態】
次に、本発明の実施の形態であるプログラム開発支援装置（以下「本装置」という）について、図面を参照して説明する。
【００１５】
〔１．構成〕
〔１−１．本装置を実現するためのコンピュータシステムの構成〕
まず、本装置を実現するためのコンピュータシステムの構成例を図１に示す。このコンピュータシステムは、並行プログラムを構成する各プロセスを同時並行的に実行するためのＮ台のプロセッサ２１１，２１２，…，２１Ｎを有し、これら各プロセッサ２１１，２１２，…，２１Ｎには、Ｉ／Ｏインターフェース２２を介して、共有メモリ２３及び周辺装置が接続されている。周辺装置としては、入力装置２４、出力装置２５及び外部記憶装置２６を用いる。
【００１６】
上記の周辺装置のうち、入力装置４は、各種コマンドやデータの入力をする装置で、キーボードとマウスなどのポインティングデバイスを有する。また、出力装置５は、ＣＲＴディスプレイなどの表示画面に、ソースプログラムやデバッグ状況に関する情報等をテキスト又はグラフィック表示することにより、ユーザに提示する装置である。なお、出力装置としては、他にプリンタなどを適宜用いることができる。ユーザは、これら入力装置４及び出力装置５を用いて、対話的にコンピュータを操作することができる。また、外部記憶装置６は、磁気ディスクや光磁気ディスクなどの記録媒体を用いて、ソースプログラムやデバッグ状況に関する情報などを書き込み及び読み出す装置である。
【００１７】
本装置は、上記のようなコンピュータシステムの各種ハードウェア資源をソフトウェアで制御することによって実現されるが、コンピュータシステムや前記ソフトウェアの具体的な構成は種々考えられるので、以下、本装置の各機能を実現する仮想的回路ブロックを用いて本実施形態を説明する。
【００１８】
〔１−２．機能ブロック図に基づく構成〕
すなわち、図２は本装置の構成を示す機能ブロック図である。この図に示すように、本装置は、編集手段１と、作成手段３と、分解手段５と、を有する。このうち編集手段１は、第１の並行プログラム２を作成及び修正するための手段１である。また、作成手段３は、第１の並行プログラム２に基づいて実行のシナリオを作成し、シナリオを表すシナリオ情報４を提供する手段である。また、分解手段５は、正しいと判定されるシナリオを、ループを含まないブロックに階層的に分解することによって、ブロックに分解されたシナリオをブロック間の構造と共に表す構造的シナリオ情報６を提供する手段である。
【００１９】
また、本装置は、解析手段１２と、並行化手段７と、統合化手段８と、生成手段１０と、を有する。このうち解析手段１２は、第１の並行プログラム２を解析することによって第１の並行プログラム２の各部分間に存在する依存関係を抽出し、この依存関係を表す解析情報１３を提供する手段である。また、並行化手段７は、分解されたシナリオを、抽出された依存関係に対応する部分間の実行順序を維持しながら、ブロックを単位として複数のプロセスに割り当てることによって並行化する手段である。また、統合化手段８は、解析情報１３を参照しながら、各プロセスに割り当てられたシナリオをプロセスごとに統合することによって、統合されたプロセスごとのシナリオを表すローカルシナリオ情報９を提供する手段である。また、生成手段１０は、ローカルシナリオ情報９に基づいて第２の並行プログラム１１を生成する手段である。
【００２０】
〔２．全体的な処理手順〕
上記のような構成を有する本装置における全体的な処理手順を図３のフローチャートに示す。
〔２−１．第１の並行プログラムの作成〕
まず、ユーザは、編集手段１を用いて、第１の並行プログラム２を作成する（ステップ１）。ここで、並行プログラムを作成するプログラミング言語は自由に選択することができ、例えば、Ｊａｖａなどの並行プログラミング言語で記述してもよいし、あるいはＣ言語などの逐次プログラミング言語と、μ−ＩＴＲＯＮのようなオペレーティングシステムのシステムコールとを組み合わせることによって記述してもよい。
【００２１】
〔２−２．シナリオの作成〕
次に、作成手段３によって、第１の並行プログラム２を実行した場合のシナリオを作成する（ステップ２）。ここで、シナリオとは、プログラムの挙動を、実行されるプログラム中の命令からなる逐次的な列として表現したものである。
【００２２】
このようなシナリオを作成するには、例えば、テストケースを与えて第１の並行プログラム２を仮想的に実行し、その実行履歴をシナリオとしたり、第１の並行プログラム２が示し得る各部分間の実行順序を、枝別れするグラフの各経路として表し、許容できない実行順序に対応する経路をグラフから削除し、その結果として得られたグラフをシナリオ情報とするなどが考えられる。ここで、グラフに含まれる各経路が個々のシナリオに対応する。
【００２３】
また、このようなシナリオを表現する具体的な形式としては、例えば、状態遷移図形式のシナリオグラフが考えられる。シナリオグラフは、並行プログラムによって実現されるシステムの全体的な状態、すなわちグローバル状態をノードとし、プログラムの各動作はノードを接続するアークで表した有向グラフである。ここで、複数のプロセスから構成された並行プログラムにおいて、グローバル状態とは、個々のプロセスがどの位置を実行しているかの状態及び各プロセスのメモリの状態を組み合わせたものである。
以上のように作成されたシナリオは、シナリオの内容を表すシナリオ情報４として、後のステップに提供される。すなわち、本出願において、「シナリオ」というときは、プログラムが示し得るある１つの命令の列であり、「シナリオグラフ」というときは１又は２以上のシナリオの集合を一体に表したものである。この場合、シナリオグラフ中の１つの経路（パス）が１つのシナリオを表す。また、「シナリオ情報」は、上記のように１又は２以上のシナリオの集合をシナリオグラフなどの形式で表した情報である。
【００２４】
〔２−３．シナリオの挙動の確認〕
このように作成されたシナリオに対して、ユーザが、シナリオで表された並行プログラム２の挙動が仕様通りであって正しいことを確認する（ステップ３）。この確認は、従来から知られたプログラムのテスト方法を用いればよい。正しくないシナリオがある場合は（ステップ４）、シナリオの元となった第１の並行プログラム２にバグがあるので、編集手段１を用いて第１の並行プログラム２を修正したうえ（ステップ１）、再度シナリオを作成して（ステップ２）、正しいことを確認する。シナリオが正しいことが確認された場合（ステップ４）、さらにシナリオを作成するときはシナリオの作成（ステップ２）に戻り、シナリオの作成を終了するときは次のステップ６に進む。
【００２５】
このようにして、複数のシナリオを順次作成する場合、既に作成したシナリオと新たに作成したシナリオで相違している経路を、既に作成したシナリオに付加することによって、複数のシナリオを一体化して単一のシナリオ情報とすることができる。例えば、シナリオグラフでは、２つのシナリオの後半でプログラムの部分間の実行順序が異なっている場合、シナリオグラフを途中から２つに枝別れさせ、異なっているそれぞれの順序に対応した経路を枝別れの先に続けることによって、前記２つのシナリオを単一のシナリオ情報で表すことができる。また、複数のシナリオを作成する場合は、１つのシナリオを作成するごとにその正しさを確認してもよいが、連続して複数作成した後で、正しさの確認を一括して行ってもよい。
【００２６】
〔２−４．依存関係の抽出〕
上記のようにシナリオ情報で表される各シナリオの正しさが確認され、第１の並行プログラム２にバグがないと考えられる場合は、ステップ６において、解析手段１２が、第１の並行プログラム２を解析することによって、第１の並行プログラム２を構成する各命令間の依存関係を抽出する。
【００２７】
ここで、依存関係とは、プログラムの異なった部分同士が相手を前提とする関係であり、データ依存と制御依存とがある。また、依存関係は、プログラムの部分間に相互に存在する、すなわち対称性を持つ関係である。このような依存関係がある２つの命令については、その実行順序によって計算結果が異なる可能性があるため、一方が他方よりも先行して実行されなければならないという制約が存在する。このような制約を先行制約と呼ぶ。このような依存関係および先行制約を抽出するためのアルゴリズムは既に公知であり、具体的には文献「本多弘樹：自動並列化コンパイラ、情報処理Vol.34.No.9,1993」などに紹介されている。
【００２８】
すなわち、まず、どのプロセスが実行されるかが、プロセス間の条件分岐で決定されず、全てのプロセスが実行される場合、依存関係はプロセス間のデータ依存を求めることによって検出できる。データ依存とは、一方の命令が、他方の命令によって提供されるデータに依存する関係である。例えば、図４（ａ）に示すように、共有変数ＭにＸの値を書き込む命令write(M,X)と、同じ共有変数Ｍからデ−タを読み出す命令Y=read(M) の間には、直接的なデータ依存が存在する。
【００２９】
また、図４（ｂ）に示すように、上記の共有変数Ｍに書き込まれた値が一旦別の変数Ｍ２にコピーされ、読み出す命令はこの変数Ｍ２からデータを読み出す場合、書き込む命令と読み出す命令の間には、間接的なデータ依存が存在する。このような直接的なデータ依存や間接的なデータ依存は、各命令がどの変数についてどのような処理を行っているかを辿ることによって抽出することができる。
【００３０】
また、どのプロセスが実行されるかが、プロセス間の条件分岐で決定される場合は、前記のデータ依存に加えて、制御依存も求める必要がある。制御依存とは、一方のプロセスでの条件の評価が真になるまで、他方のプロセスの実行を開始できないという依存関係である。このような制御依存は、各プロセスに含まれる条件分岐命令と各プロセスとの関係を調べることによって検出する。
【００３１】
前記のような、並行プログラムＣの命令間の依存関係の集合をＤ（Ｃ）と表す。すなわち、（ｔｉ，ｔｊ）∈Ｄ（Ｃ）ということは、命令ｔｉとｔｊの間に依存関係が存在することを意味する。また、与えられた並行プログラムＣが示す動作列θにおいて、動作間の先行制約は次のように定義される。すなわち、先行制約を記号”＜＜”で表し、シナリオθのｉ番目の動作をｃ（θ，ｉ）のように表す場合、
c(θ,i) << c( θ,j)iff (θ[i],θ[j])∈Ｄ（Ｃ）and i<j
である。これは、シナリオθのｉ番目とｊ番目の動作が依存関係を持ち、かつ、ｉがｊより大きければ（先行するなら）ｉ番目の動作はｊ番目の動作に対して先行しなければならないという先行制約が存在することを意味する。なお、本発明で「動作」とは、具体的にはプログラムの命令を意味し、例えば、「ａ＝ｂ−１」のような演算と代入の命令や「ａ＝＝ｂ」のような評価などが命令の単位となる。
以上のように抽出された依存関係は、依存関係を表す解析情報１３として、後のステップに提供される。
【００３２】
〔２−５．シナリオの分解〕
正しいことが確認されたシナリオ情報は、分解手段５によって、ループを含まないブロックに階層的に分解される（ステップ７）。ここで、一般に、並行プログラムは永続的に動き続ける場合が多く、並行プログラムに基づくシナリオはループを持つ場合が多い。このため、シナリオの分解では、ループを含まない部分をブロックとし、ループは、このようなブロックの末尾と先頭をつなぐ経路として、ブロック自体とは区別する。また、ループは多重になっている場合があるので、分解は階層的に行われる。
【００３３】
このように分解されるもとのシナリオが、有向グラフであるシナリオグラフとして表現されている場合、分解でできる個々のブロック内は、下位のブロックをノードとするアサイクリックなグラフとして表現できる。このアサイクリックなグラフとは、ループを含まないグラフである。例えば、図５（ａ）に示すシナリオグラフは、図５（ｂ）に示すように、ループを含まないブロックＢ１とそれ以外の部分に分解され、このブロックＢ１がさらに、ループを含まないブロックＢ２とそれ以外の部分に分解される。このようにループを含まないブロックを、以下、アサイクリックブロックと呼ぶ。
【００３４】
また、分解されたシナリオは、図５（ｂ）のようなグラフで表現する以外に、このグラフと等価な下記のような正規表現で表すことも可能である。
t14 + (t1(t2 t3 t4 +
t7 t8(t12 t13 t14)* t9 t10 t11)t5 t6)*
ここで、ｔ１＋ｔ２は「ｔ１又はｔ２」を表し、ｔ１＊はｔ１の０回以上の繰り返しを表す。なお、シナリオを分解する詳細な手順及び正規表現については後述する。
【００３５】
以上のようにシナリオを分解した結果としては、各ブロックの内容を表す情報と、ブロック以外の例えばループやブロック間の上位下位の関係を表す情報が得られ、これらの情報を構造的シナリオ情報と呼ぶ。すなわち、分解手段５からは構造的シナリオ情報６が、後のステップに提供される。
【００３６】
〔２−６．シナリオの並行化〕
続いて、上記のように分解されたシナリオを各ブロックごとに、複数のプロセスに割り当てる処理、すなわち並行化を行なう（ステップ８）。ここでは、プロセスの構造、例えば用いるプロセスの数などは第一の並行プログラム２と同じだと仮定するが、もちろん、プロセスの構造は任意に設定することもできる。
【００３７】
この並行化の際は、プログラム解析情報１３によって表される命令間の依存関係を用いる。すなわち、並行化とは、シナリオのなかで依存関係のない部分同士を相互に並行に動かせるようにすることを意味する。例えば、あるシナリオでは直列関係（ａｂ）にあるプロセスＰ１の命令ａとプロセスＰ２の命令ｂにおいて、ａとｂの間に依存関係がなければ、ａとｂを異なるプロセスに割り当てることによって並行関係（ａ‖ｂ）にすることができる。一方、依存関係を持つ命令同士については、依存関係から導出される先行制約を満足するために、並行化の際、各命令の前後に同期命令を挿入する。
【００３８】
また、並行化手段７は、このように並行化されたシナリオから冗長な同期命令を除去する。ここで、同期命令が冗長か否かの基準は、シナリオからその同期命令を除去しても、除去されたシナリオを並行プログラムとみなして生成されるシナリオの集合が、除去前のシナリオを並行プログラムとみなして生成されるシナリオの集合と等価であるか否かであり、除去しても等価な同期命令は冗長と判断する。このように等価の概念を用いて冗長な同期命令を除去する詳細な手順は後述する。
【００３９】
〔２−７．シナリオの統合化〕
上記のような並行化の結果、各プロセスには、それぞれ異なったブロックから由来するシナリオの部分が、相互に別個独立のまま割り当てられている状態となる。そこで、統合化手段８が、各ブロックを単位として割り当てられているシナリオを、プロセスごとに統合化する（ステップ９）。この統合化の詳細な手順は後述する。また、統合化の結果としては、統合化されたプロセスごとのシナリオを表すローカルシナリオ情報（９）が、後のステップに提供される。
【００４０】
〔２−８．第２の並行プログラムの生成〕
最後に、上記のように統合化されたプロセスごとのローカルシナリオ情報９から、生成手段１０が、第二の並行プログラム１１を生成する（ステップ１０）。ここで生成される第二の並行プログラム１１は、元となったシナリオ情報４で表されるシナリオおよびそのシナリオと等価な挙動のみを再現するものであるから、ステップ２で与えられたシナリオが正しければ（ステップ４）、この第二の並行プログラムも正しいことが保証される。
【００４１】
〔３．詳細な手順〕
次に、シナリオが有向グラフで与えられた場合を例にとり、上記に説明したステップ１〜１０の手順のうち、シナリオの分解（ステップ７）について詳細な手順を説明し、続いて、シナリオの並行化（ステップ８）及びシナリオの統合（ステップ９）についても詳細な手順を説明する。
【００４２】
ここでは、与えられたシナリオは図５（ａ）に示したようなシナリオグラフであり、このシナリオグラフのノ−ドは第１のプログラム２のグロ−バルな実行状態を表し、ノード間のア−クが第１の並行プログラム２内のｔ１やｔ１４などの命令を表す。また、複数のシナリオが１つのシナリオグラフによって表されていて、１つのシナリオはシナリオグラフ上の１つの経路に対応するものとする。
【００４３】
〔３−１．シナリオの分解の詳細な手順〕
〔３−１−１．シナリオグラフの正規化〕
シナリオグラフを分解するには、まず、ユーザの作成したシナリオグラフＳＧから正規表現(regular expression)に変換されたシナリオグラフＳＧr を作成する。ここで、正規表現とは、例えば、ループ部分が０回以上の繰り返しをするというデータの構造であり、正規表現でないシナリオグラフＳＧから正規表現に変換されたシナリオグラフＳＧr を作成することをシナリオグラフの正規化と呼ぶ。このとき、ＳＧとＳＧr は意味的に等価であることが保証できるようにＳＧr を生成する。このように正規化されたシナリオグラフＳＧr はもとのＳＧと等価であるが、階層的な構造を抽出することによって分解することが容易な構造を有する。
【００４４】
ここで、２つのシナリオが意味的に等価であることをシナリオ等価と呼び、また、２つのシナリオが等価である特徴を等価性と呼び、等価性を記号「＝＝＝」で表す。この場合、等価性は次のように定義できる。すなわち、２つのシナリオθ１とθ２がシナリオ等価である（θ１＝＝＝θ２）とは下記の条件が成り立つことである。
（１）任意のｉに対して、あるｊが存在して、
c(θ1,i) = c( θ2,j)であり、かつ
任意のｊに対して、あるｉが存在して、
c(θ2,j) = c( θ1,i)である。
（２）任意のｉ１，ｉ２に対して、あるｊ１，ｊ２が存在して、
c(θ1,i1) = c(θ2,j1) かつ
c(θ1,i2) = c(θ2,j2) かつ
c(θ1,i1) << c( θ1,i2) → c( θ2,j1) << c( θ2,j2))である。
（３）任意のｊ１，ｊ２に対して、あるｉ１，ｉ２が存在して、
c(θ1,i1) = c(θ2,j1) かつ
c(θ1,i2) = c(θ2,j2) かつ
c(θ2,j1) << c( θ2,j2) → c( θ1,i1) << c( θ1,i2))である。
【００４５】
このようなシナリオ等価を前提として、シナリオをグラフで表したシナリオグラフが等価であることをシナリオグラフ等価と呼ぶ。そして、２つのシナリオグラフＳＧ１＝（Ｓ１，Ｔ１，δ１，ｓ０１）とＳＧ２＝（Ｓ２，Ｔ２，δ２，ｓ０２）に対して、ＳＧ１とＳＧ２がシナリオグラフ等価である（ＳＧ１＝＝＝ＳＧ２) とは下記の条件が成り立つことである。
すなわち、任意のＳＧ１のシナリオθ１に対して、あるＳＧ２のシナリオθ２が存在して、θ１＝＝＝θ２であり、かつ任意のＳＧ２のシナリオθ２に対して、あるＳＧ１のシナリオθ１が存在して、θ1 ＝＝＝θ２である。
【００４６】
次に、与えられたシナリオグラフを、上記のような等価性を維持しながら正規化する手順の一例を示す。まず、与えられたシナリオグラフから、全く実行されない場合があるループを、分岐構造などに基づいて検出する。次に、そのループの中で、そのループが実行されない場合も実行されるパスと共有しているアークを検出する。検出されたアークと同じアークを、当該ループに専属のものと持たせることによって、ループを他の部分から独立させる。
【００４７】
より具体的には、シナリオグラフは有限オ−トマトンであり、シナリオグラフの正規化に関しては、有限オ−トマトンから等価な正規表現を生成する公知のアルゴリズムを用いる（参考文献：福村、稲垣／オ−トマトン・形式言語理論と計算論、岩波書店、1982）。なお、このような等価な正規表現に変換されたシナリオグラフは、ループとそれ以外の部分が明確に区分されているので、階層的な構造の抽出が容易である。
【００４８】
〔３−１−２．ブロックへの階層的分解〕
上記のような正規化に続いて、正規なシナリオグラフＳＧr を図５（ｂ）に示すように、ループを含まないブロックに階層的に分解する。このような分解で得られる階層構造に含まれる各階層では、シナリオは下位のブロックをノ−ドとし、ル−プを含まないサブグラフとして表現できる。
【００４９】
すなわち、上記のように正規化されたシナリオを分解するには、シナリオから最も大きなループを探し出し、そのループを、ループを含まないブロックと、そのブロックの末尾と先頭をつなぐ経路とに分ける。そして、このように作られたブロックから次に大きなループを探し出し、このような手続きを、ループが見つからなくなるまで階層的に繰り返せばよい。例えば、図５（ａ）のシナリオが与えられた場合、最大のループとしてｔ１−ｔ２−ｔ３−ｔ４−ｔ５−ｔ６を含むループ構造が取り出され、図５（ｂ）に示すように、この部分がブロックＢ１となる。さらに、ブロックＢ１の中からループｔ１２−ｔ１３−ｔ１４が取り出され、この部分がブロックＢ２となる。
【００５０】
〔３−２．シナリオの並行化の詳細な手順〕
シナリオの並行化（ステップ８）では、上記のような分解で得られた各階層のアサイクリックブロックごとに、下記の手順で並行化を行なう。これは、ル−プを含む場合とそうでない場合を統一的な手順で並行化することは困難だからである。なお、従来の、ス−パ−コンピュ−タのコンパイラにおける逐次プログラム並列化においても同様のアプロ−チが採用されている（参考文献：M. Girkar and C.D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Trans. on Parallel and Distributed Systems, Vol.3, No.2, 1992）。
【００５１】
〔３−２−１．同期動作の挿入〕
例えば、アサイクリックブロックを構成するプロセスＰ１の命令ｔ１１とプロセスＰ２の命令ｔ２１の間に依存関係がなければ、これら２つの命令ｔ１１とｔ２１は、それぞれプロセスに割り当てることによって並行関係（ｔ１１‖ｔ２１）にすることができる。依存関係のない２つのブロックについても同様である。なお、各命令は、第１の並行プログラム２においてどのプロセスに所属するかが決まっているので、シナリオの並行化では、各命令をそれぞれ所属するプロセスに射影することになる。依存関係のある直列関係の命令やブロックを並行化したり、分岐を含むブロックを並行化する場合は、次のように同期命令を用いる。
【００５２】
まず、依存関係のある直列関係の命令やブロックの間に同期命令ｓi を挿入する。例えば、相互に依存関係を持つ動作ｔ１１とｔ２１が、シナリオのあるブロックで直列しているものとする（図６（ａ））。そして、動作ｔ１１とｔ２１の間の依存関係に基づいて、動作ｔ１１が動作ｔ２１に先行しなければならないという先行制約が存在するものとする。この場合、直列している動作ｔ１１とｔ１２の間に同期命令ｓ１を挿入することによって
t11 t21 → t11 s1 t21
とする（図６（ｂ））。また、例えば、ブロックＢ１とＢ２の間に同様の先行制約がある場合も、同期命令ｓ１を挿入して
B1 B2 → B1 s1 B2
とする。
【００５３】
また、各分岐にも同期命令を挿入する。例えば、図７（ａ）の例では、分岐命令による動作ｔ１１の内容に応じて、動作ｔ１２−ｔ１３を含む左側の経路と、動作ｔ２１−ｔ２２を含む右側の経路とに、動作列が分岐する。この場合、図７（ｂ）に示すように、それぞれの経路へ分岐する部分に同期命令ｓ１及びｓ２を挿入し、
t11 (t12 t13 + t21 t22) →
t11 (s1 t12 t13 + s2 t21 t22)
とする。また、例えば、ブロックＢ１における分岐の動作に基づいてブロックＢ２とＢ３とに分岐するような場合も、それぞれの経路へ分岐する部分に、同様に同期命令ｓ１及びｓ２を挿入し、
B1 (B2 + B3) → B1 (s1 B2 + s2 B3)
とする。
【００５４】
〔３−２−２．プロセスへの射影〕
次に、上記のように同期命令を挿入したシナリオを各プロセスに射影する。ここで、射影(projection)とは、各プロセスにシナリオの一部を割り当てることである。ここで、Ｂ｜ＰはブロックＢのプロセスＰへの射影を意味する。
【００５５】
例えば、図６（ｂ）では、同期命令ｓ１を挿入したシナリオに動作ｔ１１とｔ２１が含まれているが、このうち動作ｔ１１をあるプロセスＰ１に割り当て、動作ｔ２１を別のプロセスＰ２に割り当てる場合、図６（ｃ）に示すように、プロセスＰ１では動作ｔ１１に続けて同期命令ｓ１を割り当て、プロセスＰ２では動作ｔ２１の前に同期命令ｓ１を割り当て、
t11 s1 t21 → t11 s1 ‖s1 t21
とする。この場合、プロセスＰ２の同期命令ｓ１は、プロセスＰ１で同期命令ｓ１が実行されるまで待ち状態となるので、プロセスＰ２の動作ｔ２１は必ずプロセスＰ１の動作ｔ１１の実行終了を待って実行が開始される。このため、動作ｔ１１とｔ２１の実行順序は先行制約に合致するように維持される。
【００５６】
また、ブロックＢ１とＢ２の間に先行制約がある場合も同様に、挿入されている同期命令ｓ１を各ブロックＢ１，Ｂ２と共に各プロセスに割り当てることによって、
B1 s1 B2 → (B1｜P1)s1(B2｜P1) ‖(B1 ｜P2)s1(B2｜P2)
とする。
【００５７】
また、図７（ｂ）では、同期命令ｓ１及びｓ２を挿入したシナリオに、動作ｔ１２−ｔ１３を含む左側の経路と、動作ｔ２１−ｔ２２を含む右側の経路が含まれているが、この２つの経路をそれぞれ別々のプロセスＰ１とＰ２に割り当てるものとする。この場合、図７（ｃ）に示すように、プロセスＰ１では、動作ｔ１１による分岐のうち、プロセスＰ１で実行する左側の経路に同期命令ｓ１を挿入し、右側の経路は同期命令ｓ２を最後に終了するように構成する。プロセスＰ２では、これと反対に、同期命令ｓ１の経路は終了するように構成し、同期命令ｓ２に続けて動作ｔ２１以降の右側の経路を構成することによって、
t11(s1 t12 t13 + s2 t21 t22) →
t11(s1 t12 t13 + s2)‖(s1 + s2 t21 t22)
とする。この場合、プロセスＰ１で同期命令ｓ１に続いて動作ｔ１２以下が実行される場合は、プロセスＰ２は同期命令ｓ１で終了し、また、プロセスＰ２で同期命令ｓ２に続いて動作ｔ２１以下が実行される場合は、プロセスＰ１は同期命令ｓ２で終了する。このため、プロセスＰ１とＰ２を併せて観察しても、図７（ｂ）で示した右側と左側の双方の経路が同時に実行されることはなく、もとのシナリオに含まれていた分岐の構造が保存されている。
【００５８】
また、ブロックＢ１における分岐の動作に基づいてブロックＢ２とＢ３とに分岐するような場合も同様に、挿入されている同期命令ｓ１及びｓ２をブロックと共にそれぞれのプロセスへ割り当て、
B1 (s1 B2 + s2 B3) →
(B1 ｜P1)(s1(B2 ｜P1) + s2(B3 ｜P1))‖
(B1 ｜P2)(s1(B2 ｜P2) + s2(B3 ｜P2))
とする。この場合は、同期命令ｓ１に続いてブロックＢ２が実行される場合、ブロックＢ２の各部分のうちプロセスＰ１ではプロセスＰ１に射影された部分が実行され、プロセスＰ２ではプロセスＰ２に射影された部分が実行される。また、同期命令ｓ２に続いてブロックＢ３が実行される場合、ブロックＢ３の各部分のうちプロセスＰ１ではプロセスＰ１に射影された部分が実行され、プロセスＰ２ではプロセスＰ２に射影された部分が実行される。
【００５９】
上記のような射影を行った時点では、各プロセスには、第１の並行プログラム２において当該プロセスに対応する命令が割り当てられているほか、ブロックに挿入された全ての同期命令が、全てのプロセスに割り当てられている。
【００６０】
〔３−２−３．冗長な同期命令の除去〕
続いて、割り当てられた全ての同期命令の中から、各アサイクリックブロックごとに冗長な同期命令を抽出しそれを除去する。たとえば、図８（ａ）のシナリオをプロセスＰ１，Ｐ２へ射影し、
(s1 a s2 + s3 s4 a) ‖(s1 s2 b + s3 b s4)
とした結果を図８（ｂ）に示す。この例では、命令ａとｂに依存関係があることから同期命令ｓ１，ｓ２，ｓ３，ｓ４が用いられているが、実際には図８（ａ）のシナリオではａ→ｂという順序も、逆のｂ→ａという順序も双方許容されているので、同期命令ｓ１，ｓ２，ｓ３，ｓ４は冗長である。このため、これら同期命令を除去することによって図８（ｃ）の状態とすることができる。
【００６１】
〔３−２−３−１．原始的な手順〕
このような冗長な同期命令をシナリオグラフＳＧから除去する手順は、原始的には次のように表現することができる。すなわち、任意の同期命令ｓを選択し、それを除去する前のグラフＳＧと除去した後のグラフＳＧ’を比較し、両者がシナリオグラフ等価（ＳＧ＝＝＝ＳＧ’）であれば同期命令ｓを削除する、という処理を繰り返し、全ての同期命令についてこの処理を繰り返しても同期命令が１つの除去できなくなった時点で処理を終了する。
【００６２】
〔３−２−３−２．シナリオグラフ等価を判定する手順〕
上記の手順では、選択した同期命令を除去する前後のシナリオグラフが等価かどうかを判定する必要があり、本実施形態では、シナリオグラフの等価性の判定に次のようなカウンティングトレ−スを用いる。カウンティングトレースとは、シナリオにおいてどの動作が何度行われ、依存関係を持つ動作がいつ行われたかを示す情報である。ここで、与えられたシナリオθのカウンティングトレ−スｃｔ（θ）は以下のように定義される。
ct( θ) = (<動作の生起カウンタの組>,< 先行制約条件の集合>)
この定義において、動作の生起カウンタは、そのシナリオ中で当該動作が何回生起したかを表す項目であり、例えば、（ａ，ｋ）のような表現は、シナリオθにおいて動作ａがｋ回生起したことを意味する。また、先行制約条件は、依存関係を持つ動作がいつ生起したかを表す。例えば、並行プログラムＣが動作ａ→ｂ→ｃ→ｂ→ａの順に実行され、この実行順序を表すシナリオθ＝ａｂｃｂａに対して、依存関係の集合Ｄ（Ｃ）が依存関係（ａ，ｃ）を含む場合、θのカウンティングトレ−スは、
【００６３】
このようなカウンティングトレースの集合をカウンティングトレ−ス集合と呼び、アサイクリックなシナリオグラフＳＧにおいて、カウンティングトレ−ス集合ｃｔｓｅｔ（ＳＧ）は以下のように定義される。
ctset(ＳＧ) = {ct(θ) ｜θはＳＧのシナリオ}
この定義は、シナリオグラフＳＧに基づくカウンティングトレース集合ｃｔｓｅｔ（ＳＧ）が、シナリオグラフＳＧの全てのシナリオθのカウンティングトレースｃｔ（θ）からなることを意味している。そして、アサイクリックなシナリオグラフＳＧにおいて、任意のシナリオは有限なので、このシナリオグラフＳＧを並行プログラムＣとみなし、ｃｔｓｅｔ（Ｃ）を計算することが可能である。ここで、アサイクリックなシナリオグラフＳＧ１とＳＧ２に対して、シナリオグラフ等価とカウンティングトレース集合との間には、下記の性質が成り立つ。
ＳＧ1 === ＳＧ2 iff ctset(C1)=ctset(C2)
これは、２つのシナリオグラフＳＧ１とＳＧ２の間でそれぞれに基づくカウンティングトレース集合ｃｔｓｅｔ（Ｃ１）とｃｔｓｅｔ（Ｃ２）が同じであれば、２つのシナリオグラフＳＧ１とＳＧ２は等価であることを意味する。
【００６４】
〔３−２−４．冗長な同期命令の除去を効率的に行う手順〕
シナリオグラフ等価を判定する上記のような手法を応用して、冗長な同期命令の除去を効率的に行う手順を次に示す。なお、ここでは、依存関係を有する動作ｔ１とｔ２の間に同期命令ｓｙｎｃ（ｓ１）の挿入されたアサイクリックブロックＳＧn （図９（ａ））から冗長な同期命令を除去するものとする。まず、ＳＧn をプロセスＰ１とＰ２に射影する。なお、射影されたプロセスは、並行プログラムＣn とみなすことができる。まず、冗長な同期命令の除去を効率的に行う手順を図１０に示す。
〔３−２−４−１．ダミー動作の挿入〕
図１０に示す手順では、まず、各プロセスＰｉに挿入してある各同期命令ｓｙｎｃ（ＩＤ）に１対１に対応させて、ダミー動作ｎｓｙｎｃ（Ｐｉ，ＩＤ）を挿入する（ステップ１０１）。ダミー動作とは、同期する命令である同期命令に対して、同期しない命令であり、言い換えれば、同期命令による同期を解除する動作である。このようなダミー動作は、例えば、同期命令の直前に、当該同期命令の直後へ選択的にジャンプする命令を挿入することによって実現する。例えば、図９（ａ）に示したシナリオグラフについては、各プロセスＰ１及びＰ２に割り当てて並行化する際、同期命令ｓｙｎｃ（ｓ１）の直前に、当該同期命令ｓｙｎｃ（ｓ１）をスキップしてその直後にジャンプするダミー動作ｎｓｙｎｃ（Ｐ１，ｓ１）及びｎｓｙｎｃ（Ｐ２，ｓ１）を各プロセスに挿入する（図９（ｂ））。このようなダミー動作を挿入したシナリオグラフをＳＧe とする。また、このように挿入した全てのダミー動作は、記録用の集合ＡＮＳに記録しておく（ステップ１０２）。
【００６５】
〔３−２−４−２．状態空間の生成〕
次に、上記のようにダミー動作を挿入したシナリオグラフＳＧe を、並行プログラムＣe とみなし、並行プログラムＣe が示し得る動作列の集合を表す状態空間ＳＳ（Ｃｅ）を生成する（ステップ１０３／図９（ｃ））。ここで、並行プログラムＣについて、状態空間ＳＳ（Ｃ）とは、下記に定義する状態遷移グラフＳＳ（Ｃ）＝（Ｓ，Ｔ，δ，ｍ０）である。
ＳはＣのグローバル状態の集合
ＴはＣの命令の集合
δは状態遷移関係。すなわち、この状態遷移関係δの要素（ｍ，ｔ，ｍ’）は、グローバル状態ｍで命令ｔが実行されるとグローバル状態ｍ’になることを意味する。
ｍ０はＣの初期グローバル状態
なお、シナリオグラフＳＧ＝（Ｓ，Ａ，δ’，ｓ０）は並行プログラムＣの状態空間ＳＳ（Ｃ）＝（Ｓ，Ａ，δ，ｓ０）のサブグラフである。すなわち、δ’がδの部分集合である。
【００６６】
〔３−２−４−３．違反パスの検出〕
続いて、生成された状態空間ＳＳ（Ｃｅ）から、カウンティングトレース集合ｃｔｓｅｔ（Ｃｎ）に含まれないカウンティングトレースｃｔ（θ）を生じる違反パスθ、すなわち先行制約に反するまたはデッドロックする違反パスθを検出する（ステップ１０４）。図９（ｃ）では、違反パスθを太線及び×印で示す。なお、ｃｔｓｅｔ（Ｃｎ）はダミー動作挿入前のシナリオグラフに対応するカウンティングトレース集合であり、違反パスθを検出する際に作成するか、それ以前に作成して保存しておく。
【００６７】
違反パスθが検出された場合（ステップ１０５）、この違反パスθをルート側に向かって遡り、遡る経路の最後に登場するダミー動作ｎｓｙｎｃ（Ｐｉ，ＩＤ）を検出する（ステップ１０６／図９（ｃ））。すなわち、違反パスθはダミー動作ｎｓｙｎｃ（Ｐｉ，ＩＤ）の挿入が原因で発生したと考えられることから、同期命令ｓｙｎｃ（ＩＤ）は不可欠であり、冗長でないことが判断できる。図９（ｃ）の例では、動作ｎｓ２１が、正しい動作からの逸脱(deviation) を生じさせたダミー動作として検出されている。
【００６８】
このように検出されたダミー動作は、記録用の集合ＤＮＳに追加する（ステップ１０７）。また、そのダミー動作をシナリオグラフＳＧe から除去（ステップ１０８）したうえで状態空間ＳＳ（Ｃe ）を再度生成するか、状態空間のうちそのダミー動作から始まる部分を枝刈りする。そのうえで再び違反パスθの検出からの手順を繰り返し、違反パスθが検出されなくなった時点で（ステップ１０５）以下の手順へ進む。
【００６９】
〔３−２−４−４．冗長性の判断〕
違反パスθが検出されなくなった時点では、それまでに検出された全てのダミー動作が集合ＤＮＳに含まれている。その結果、挿入した全てのダミー動作の集合ＡＮＳから、検出されたダミー動作の集合ＤＮＳを除いたＡＮＳ−ＤＮＳは、挿入したが違反パスを発生させなかったダミー動作の集合となる。そのようなダミー動作に対応する同期命令は、実際に削除してもシナリオグラフのカウンティングトレース集合には影響を与えない。
【００７０】
したがって、ダミー動作ｎｓｙｎｃ（Ｐｉ，ＩＤ）がＡＮＳ−ＤＮＳに含まれるならば、そのプロセスＰｉに挿入されている同期命令ｓｙｎｃ（ＩＤ）は冗長であるからシナリオグラフから除去する（ステップ１０９）。このように冗長な同期命令をすべて並行プログラムＣｎから除去することによって、並行プログラムＣｏが最終的に得られたとする。このとき、挿入した全ての同期命令を持ったままの並行プログラムＣｎと、冗長な同期命令を除去した並行プログラムＣｏはカウンティングトレース集合が共通することからシナリオグラフ等価であり、ＳＳ（Ｃｏ）＝＝＝ＳＳ（Ｃｎ）が満たされる。
【００７１】
〔３−３．統合化の詳細な手順〕
続いて、分解された各階層のブロックごとに並行化されたシナリオを、各プロセスごとに１つのシナリオに統合する。
【００７２】
〔３−３−１．ブロックの埋め込み〕
統合の際は、まず、下位の階層のブロックの詳細を上位の階層に埋め込む。例えば、
B1 = a1 (B2 ｜P1) a2‖b1 (B2｜P2) b2
B2 = a3 ‖b3
のとき、下位階層のブロックに関する
B2｜P1 = a3 、B2｜P2 = b3
を代入すると、全体として
B1 = a1 a3 a2 ‖b1 b3 b2
になる。
【００７３】
〔３−３−２．ループの展開〕
続いて、ブロックに対するループを、そのブロックの内側の各プロセスのループとする。例えば、
（ａ‖ｂ）＊ → ａ＊‖ｂ＊
とする。
【００７４】
〔４．具体例〕
以下に、本実施形態を並行プログラムを適用する場合の具体例を、図３に示すフローチャートの各ステップにしたがって説明する。ここで対象とするのは共有変数型の並行プログラムＣであり、この並行プログラムＣは少なくとも、２つのプロセスＰ１，Ｐ２から構成され、共有メモリを用いる２つの共有変数ｍ１，ｍ２を読み書きするものとする。
【００７５】
〔４−１．並行プログラムの作成〕
この具体例では、並行プログラムＣ＝Ｐ１‖Ｐ２を作成したとする（ステップ１）。このプログラムの命令間の依存関係の集合Ｄ（Ｃ）には、変数ｍ１を介したデータ依存に基づく依存関係（ａ２，ｂ２）と、変数ｍ２を介したデータ依存に基づく依存関係（ａ３，ｂ３）が含まれる。
【００７６】
m1 = 0 ; m2 = 0 ;
P1:
while(true){
a1: v11 = 1 ;
a2: write(m1,v11) ;
a3: v12 = read(m2) ;
}
P2:
while(true){
b1: v21 = 2 ;
b2: v22 = read(m1) ;
b3: write(m2,v21) ;
}
〔４−２．シナリオの作成〕
上記のような並行プログラムＣから、作成手段３を用いてシナリオを作成する（ステップ２）。ここでは、複数のシナリオをまとめたシナリオグラフ（図１１（ａ））が作成されたものとする。
【００７７】
〔４−３．シナリオの挙動の確認〕
ユーザは、このシナリオグラフ上の各シナリオは正しいことを確認し（ステップ３）、バグがあればステップ１に戻る（ステップ４）。ここでは、シナリオにはバグは発見されず、依存関係の抽出（ステップ６）に続いてシナリオの分解（ステップ７）が行われるものとする。
【００７８】
〔４−４．シナリオの分解〕
シナリオの分解（ステップ６）では、シナリオグラフの正規化と階層構造の抽出が行われる。すなわち、まず、シナリオグラフ（図１１（ａ））を正規化することによって正規表現に変換された次のシナリオを得る。ここで、ａ＊は「ａの０回以上の繰り返し」、ａ＋ｂは「ａまたはｂを実行する」を意味する。
ＳＧr=(b1(a1 a2 a3)* a1(a2 b2 + b2 a2)b3 a3)*
この正規表現に変換されたシナリオを等価なグラフで表したシナリオグラフを図１１（ｂ）に示す。正規表現に変換されたシナリオ
(b1(a1 a2 a3)* a1(a2 b2 + b2 a2)b3 a3)*
は以下のような階層的な構造を有する各ブロックに分解することができる。ここで、Ｂ１＊およびＢ２＊を１つの要素とみなせば、各階層の個々のブロックはル−プ構造を含まない。
ＳＧr = B1*
B1 = b1 B2* a1(a2 b2 + b2 a2)b3 a3
B2 = a1 a2 a3
〔４−５．シナリオの並行化〕
続いて、このように分解されたブロックを単位として、並行化を行なう（ステップ８）。この例では、ブロックＢ２は、
B2 = a1 a2 a3 ‖ε( εは空列の意味）
であり、プロセスＰ１の動作しか含まないので並行化の必要はない。一方、ブロックＢ１は次のように並行化される。まず、ブロックＢ１には同期命令ｓ１，ｓ２，ｓ３，ｓ４，ｓ５，ｓ６を導入する。
B1 = b1 B2* s1 a1(s2 a2 s3 b2 + s4 b2 s5 a2)b3 s6 a3
続いて、このように同期命令ｓ１〜ｓ６を挿入したブロックＢ１をプロセスＰ１，Ｐ２に射影する。
(s2 a2 s3 + s4 s5 a2) ‖(s2 s3 b2 + s4 b2 s5) → a2 ‖b2
と簡約化できる。すなわち、同期命令ｓ２，ｓ３，ｓ４，ｓ５は冗長であるため除去される。この結果、ブロックＢ１の最終的な正規表現は下記のようになる。
B1 =(B2 ｜P1)* s1 a1 a2 s6 a3 ‖b1(B2 ｜P2)* s1 b2 b3 s6
〔４−６．シナリオの統合〕
次に、各ブロックごとに各プロセスに割り当てられているシナリオを統合化する。この統合化では、下位のブロックＢ２の内容を、上位の階層のブロックＢ１に埋め込むことによって、
ＳＧr = ((a1 a2 a3)* s1 a1 a2 s6 a3 ‖b1 s1 b2 b3 s6)*
となる。また、ル−プの展開を行なうことによって、
ＳＧr =
((a1 a2 a3)* s1 a1 a2 s6 a3)* ‖(b1 s1 b2 b3 s6)*
となる。このような統合化によって最終的に生成されたシナリオをシナリオグラフで表すと図１１（ｃ）のようになる。ここで、正規表現をそのままグラフで表したものは多少冗長性があるので、一部最適化されている。
【００７９】
〔４−７．第２の並行プログラムの生成〕
最後に、図１１（ｃ）に示したシナリオグラフから、下記の並行プログラムＣ＝Ｐ１‖Ｐ２を生成する。
【００８０】
以上説明したように、本実施形態では、正しいことが確認されたシナリオという形で、並行プログラムを一旦逐次化し、このシナリオに基づいて並行プログラムを再び生成することによって並行プログラムの信頼性の向上させる。その際、シナリオを一旦、ループを含まないブロックに階層的に分解する。そして、分解されたブロックごとに各プロセスに割り当てて並行化し、プロセスごとに再び統合化して並行プログラムを生成する。このため、構造が複雑な並行プログラムについても、ブロックに分解して処理することによって逐次プログラミングと同程度の容易さで開発することが可能となる。また、分解された個々のブロックはループや階層構造を含まないので、効率的に処理でき、並行プログラム全体として効率的に開発を行うことができる。
【００８１】
特に、本実施形態では、シナリオを正規化することによって正規表現に変換されたシナリオとし、正規表現に変換されたシナリオは階層的に分解することが容易である。このため、並行プログラムの分解が効率化される。
【００８２】
また、本実施形態では、同期命令を埋め込みながらシナリオをプロセスに割り当てるので、プロセス間において各部分の実行タイミングが、依存関係に基づく先行制約に合致するように制御され、最終的に得られる並行プログラムの信頼性が確保される。
【００８３】
また、本実施形態では、冗長な同期命令を除去することによって、各プロセスが互いにどのようなタイミングで動作するかの自由度が拡張される。これは、無害な非決定性を与えることによって並行プログラムを最適化することを意味し、シナリオという形で一旦逐次化された並行プログラムにおいて、並行性を可能な限り復元することができる。
【００８４】
また、本実施形態では、依存関係を持つ動作の実行順序に影響しない同期命令が除去されるので、並行プログラムの動作の自由度を拡張しながら、依存関係を持つ動作の実行順序は正しく維持される。
【００８５】
〔６．他の実施の形態〕
なお、本発明は上記実施の形態に限定されるものではなく、次に例示するような他の実施形態も含むものである。例えば、上記実施形態を実現するために用いるコンピュータの構成について、図１に示した構成例はマルチＣＰＵであるが、本発明は他の構成のコンピュータシステム上に実現してもよく、例えば、共有メモリを有する並列計算機、共有メモリを有しない並列計算機、分散ネットワーク計算機システム、単一ＣＰＵ計算機をマルチタスクシステムとしたもの、などが考えられる。
【００８６】
また、上記実施形態では、依存関係の抽出は、シナリオを分解する前に行ったが、依存関係の抽出はシナリオを分解した後に行ってもよい。また、上記実施形態では、シナリオの形式としてシナリオグラフを用いたが、シナリオの形式は自由であり、テキストやフローチャート形式など所望の形式のシナリオを用いることができる。また、上記実施形態で示した並行プログラムやシナリオは例示に過ぎず、用いる言語、表現形式、複雑さなどは自由に選択することができる。
【００８７】
また、本発明は、本発明の作用を実現するためのソフトウェアによって実現することが一般的と考えられるが、そのようなソフトウェアを記録した記録媒体も本発明の一態様である。
【００８８】
【発明の効果】
以上説明したように、複雑な構造の並行プログラムについても、優れた信頼性と効率で開発を行うことができるので、プログラミングの生産性と精度が大幅に向上する。
【図面の簡単な説明】
【図１】本発明の実施の形態の実現に用いるコンピュータシステムのハードウェア構成を示す図
【図２】本発明の実施の形態の構成を示す機能ブロック図
【図３】本発明の実施の形態における処理手順を示すフローチャート
【図４】本発明の実施の形態において、データ依存の例を示す図
【図５】本発明の実施の形態におけるシナリオの分解を例示する図
【図６】本発明の実施の形態において、シナリオに同期命令を挿入し、各プロセスに割り当てる例を示す図
【図７】本発明の実施の形態において、シナリオに同期命令を挿入し、各プロセスに割り当てる他の例を示す図
【図８】本発明の実施の形態において、シナリオに挿入した同期命令が冗長なものとして除去される状態を示す図
【図９】本発明の実施の形態において、シナリオグラフにダミー動作を挿入し、違反パスが発生する状態を示す図
【図１０】本発明の実施の形態において、冗長な同期命令を効率的に除去する手順を示すフローチャート
【図１１】本発明の実施の形態における具体例を示す図
【符号の説明】
１：編集手段
２：第１の並行プログラム
３：作成手段
４：シナリオ情報
５：分解手段
６：構造的シナリオ情報
７：並行化手段
８：統合化手段
９：ローカルシナリオ情報
１０：生成手段
１１：第二の並行プログラム
１２：解析手段
１３：解析情報
２１：プロセッサ
２２：Ｉ／Ｏインタフェイス
２３：共有メモリ
２４：入力装置
２５：出力装置
２６：外部記憶装置
Claims (10)
- 入力装置及び記憶装置を有するコンピュータに、編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段を構成することによって実現され、前記入力装置が入力した情報に基づいて、前記編集手段が第１の並行プログラムを作成し、前記第１の並行プログラムを前記記憶装置が記憶し、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段が第２の並行プログラムを生成し、前記第２の並行プログラムを前記記憶装置が記憶するプログラム開発支援装置において、
前記第１の並行プログラムから実行のシナリオを作成する前記作成手段と、
前記第１の並行プログラムを解析することによって、前記第１の並行プログラムの部分間に存在する依存関係を抽出する前記解析手段と、
前記シナリオを、ループを含まないブロックに階層的に分解する前記分解手段と、
前記依存関係に基づいて、前記分解されたシナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化する前記並行化手段と、
各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化する前記統合化手段と、
統合化されたプロセスごとのシナリオから第２の並行プログラムを生成する前記生成手段と、
を有することを特徴とするプログラム開発支援装置。 - 前記分解手段は、前記作成手段から与えられたシナリオを正規化する手段を有することを特徴とする請求項１記載のプログラム開発支援装置。
- 前記並行化手段は、シナリオをプロセスに割り当てる際、前記依存関係に対応する同期命令をシナリオに埋め込むように構成されたことを特徴とする請求項１又は２記載のプログラム開発支援装置。
- 前記並行化手段は、シナリオに埋め込んだ前記同期命令のうち、冗長な同期命令を除去するように構成されたことを特徴とする請求項３記載のプログラム開発支援装置。
- 前記並行化手段は、前記冗長な同期命令を除去する際、
シナリオに埋め込んだ任意の同期命令の作用を抑制し、
前記抑制の前と後の各シナリオの間で、前記依存関係を持つ動作が示し得る実行順序が同じかどうかを判断し、
前記実行順序が同じである場合は、作用を抑制した前記同期命令を除去するように構成されたことを特徴とする請求項４記載のプログラム開発支援装置。 - 前記並行化手段は、前記冗長な同期命令を除去する際、
シナリオに埋め込んだ任意の同期命令の作用を抑制し、
前記抑制の前と後の各シナリオの間で、シナリオが等価かどうかを判定する判定手段を含み、
前記判定手段は、相互に依存関係を有する部分を含む２つのシナリオそれぞれについて、前記依存関係を有する部分がいつ実行されたかを表すカウンティングトレースの集合を計算する手段と、
計算された前記２つの集合を比較し、２つの集合が等しい場合に２つのシナリオが等価であると判断する手段から構成され、
シナリオが等価であると判断された場合は、作用を抑制した前記同期命令を除去するように構成されたことを特徴とする請求項４記載のプログラム開発支援装置。 - 入力装置及び記憶装置を有するコンピュータに構成された編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段によって実現され、前記入力装置が入力した情報に基づいて、前記編集手段が第１の並行プログラムを作成し、前記第１の並行プログラムを前記記憶装置が記憶し、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段が第２の並行プログラムを生成し、前記第２の並行プログラムを前記記憶装置が記憶するプログラム開発支援方法において、
前記作成手段が、前記第１の並行プログラムから実行のシナリオを作成するステップと、
前記解析手段が、前記第１の並行プログラムを解析することによって、第１の並行プログラムの部分間に存在する依存関係を抽出するステップと、
前記分解手段が、前記シナリオを、ループを含まないブロックに階層的に分解するステップと、
前記並行化手段が、前記依存関係に基づいて、分解された前記シナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化するステップと、
前記統合化手段が、各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化するステップと、
前記生成手段が、統合化されたプロセスごとのシナリオから第２の並行プログラムを生成するステップと、
を含むことを特徴とするプログラム開発支援方法。 - 前記並行化手段が並行化するステップは、
シナリオをプロセスに割り当てる際、前記依存関係に対応する同期命令をシナリオに埋め込むサブステップと、
シナリオに埋め込んだ前記同期命令のうち、冗長な同期命令を除去するサブステップと、
を含むことを特徴とする請求項７記載のプログラム開発支援方法。 - 前記並行化手段が、冗長な同期命令を除去するサブステップは、
シナリオに埋め込んだ任意の同期命令の作用を抑制し、
前記抑制の前と後の各シナリオの間で、前記依存関係を持つ動作が示し得る実行順序が同じかどうかを判断し、
前記実行順序が同じである場合は、作用を抑制した前記同期命令を除去することを特徴とする請求項８記載のプログラム開発支援方法。 - 入力装置及び記憶装置を有するコンピュータに、編集手段、作成手段、解析手段、分解手段、並行化手段、統合化手段、生成手段を実現させるソフトウェアであって、前記入力装置から入力された情報に基づいて、前記編集手段に第１の並行プログラムを作成させ、前記第１の並行プログラムを前記記憶装置に記憶させ、前記第１の並行プログラムに基づいて、前記作成手段、前記解析手段、前記分解手段、前記並行化手段、前記統合化手段及び前記生成手段に第２の並行プログラムを生成させ、前記第２の並行プログラムを前記記憶装置に記憶させるプログラム開発支援用ソフトウェアを記録した記録媒体において、
前記プログラム開発支援用ソフトウェアは、
前記作成手段に、前記第１の並行プログラムから実行のシナリオを作成させ、
前記解析手段に、前記第１の並行プログラムを解析させることによって、前記第１の並行プログラムの部分間に存在する依存関係を抽出させ、
前記分解手段に、前記シナリオを、ループを含まないブロックに階層的に分解させ、
前記並行化手段に、前記依存関係に基づいて、分解された前記シナリオを前記ブロック若しくは前記ブロックに属する命令を単位として複数のプロセスに割り当てることによって並行化させ、
前記統合化手段に、各プロセスに割り当てられたシナリオを前記プロセスごとのシナリオとして統合化させ、
前記生成手段に、統合化されたプロセスごとのシナリオから第２の並行プログラムを生成させることを特徴とするプログラム開発支援用ソフトウェアを記録した記録媒体。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP29988697A JP3675623B2 (ja) | 1997-10-31 | 1997-10-31 | プログラム開発支援装置及び方法並びにプログラム開発支援用ソフトウェアを記録した記録媒体 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP29988697A JP3675623B2 (ja) | 1997-10-31 | 1997-10-31 | プログラム開発支援装置及び方法並びにプログラム開発支援用ソフトウェアを記録した記録媒体 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH11134307A JPH11134307A (ja) | 1999-05-21 |
| JP3675623B2 true JP3675623B2 (ja) | 2005-07-27 |
Family
ID=17878140
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP29988697A Expired - Fee Related JP3675623B2 (ja) | 1997-10-31 | 1997-10-31 | プログラム開発支援装置及び方法並びにプログラム開発支援用ソフトウェアを記録した記録媒体 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3675623B2 (ja) |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4923288B2 (ja) * | 2000-03-13 | 2012-04-25 | 陽子 友保 | 非同期共有オブジェクトシステムの耐故障合意手法およびその実現機構 |
| US9043194B2 (en) | 2002-09-17 | 2015-05-26 | International Business Machines Corporation | Method and system for efficient emulation of multiprocessor memory consistency |
| US8108843B2 (en) | 2002-09-17 | 2012-01-31 | International Business Machines Corporation | Hybrid mechanism for more efficient emulation and method therefor |
| US7496494B2 (en) | 2002-09-17 | 2009-02-24 | International Business Machines Corporation | Method and system for multiprocessor emulation on a multiprocessor host system |
| JP4754010B2 (ja) * | 2008-09-29 | 2011-08-24 | 富士通株式会社 | メッセージ紐付け処理プログラム、方法及び装置 |
| US8539035B2 (en) * | 2008-09-29 | 2013-09-17 | Fujitsu Limited | Message tying processing method and apparatus |
| JP5017396B2 (ja) * | 2010-03-01 | 2012-09-05 | 株式会社東芝 | 情報処理装置およびプログラムの検証方法 |
| CN111857970A (zh) * | 2020-07-29 | 2020-10-30 | 北京思特奇信息技术股份有限公司 | 一种基于多依赖进程的调度方法和系统 |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3039953B2 (ja) * | 1989-04-28 | 2000-05-08 | 株式会社日立製作所 | 並列化装置 |
| JPH0689188A (ja) * | 1992-09-08 | 1994-03-29 | Nec Software Ltd | 自動並列化処理方式 |
| JPH06250988A (ja) * | 1993-02-26 | 1994-09-09 | Nec Software Ltd | 自動並列化処理方法 |
| JP3641090B2 (ja) * | 1995-12-26 | 2005-04-20 | 株式会社東芝 | プログラミング支援装置とその方法 |
-
1997
- 1997-10-31 JP JP29988697A patent/JP3675623B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH11134307A (ja) | 1999-05-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4629768B2 (ja) | 並列化処理方法、システム、及びプログラム | |
| US8276124B2 (en) | Constructing petri nets from traces for diagnostics | |
| US6275980B1 (en) | Programming method for concurrent programs and program supporting apparatus thereof | |
| JP4042604B2 (ja) | プログラム並列化装置，プログラム並列化方法およびプログラム並列化プログラム | |
| JP2980178B2 (ja) | 並列プロセッサで処理する並列な命令ストリームを同期させる方法 | |
| US9152389B2 (en) | Trace generating unit, system, and program of the same | |
| US10943041B2 (en) | Electronic system level parallel simulation method with detection of conflicts of access to a shared memory | |
| US8201142B2 (en) | Description language for structured graphs | |
| US6067415A (en) | System for assisting a programmer find errors in concurrent programs | |
| JP4050339B2 (ja) | 並行プログラム作成支援装置及び並行プログラム作成方法並びに並行プログラム実行装置 | |
| JP3675623B2 (ja) | プログラム開発支援装置及び方法並びにプログラム開発支援用ソフトウェアを記録した記録媒体 | |
| JP4414373B2 (ja) | プログラムの検証プログラム、プログラムの検証装置、プログラムの検証方法 | |
| JP2012146137A (ja) | 情報処理装置およびプログラム | |
| Hierons et al. | Parallel algorithms for generating harmonised state identifiers and characterising sets | |
| CN111158890A (zh) | 控制任务集中的任务并行的系统及其方法 | |
| Darabi et al. | A verification technique for deterministic parallel programs | |
| JP3641090B2 (ja) | プログラミング支援装置とその方法 | |
| JP3930255B2 (ja) | システム仕様情報処理装置、システム仕様情報処理方法及びプログラム | |
| JP2016146148A (ja) | 設計支援装置、および設計支援方法 | |
| Didier et al. | Sheep in wolf's clothing: Implementation models for dataflow multi-threaded software | |
| CN115033479B (zh) | 一种基于精化约束重用的并行程序增量式回归验证方法 | |
| JP6600888B2 (ja) | 並列化コンパイラ、並列化コンパイル装置、及び並列プログラムの生成方法 | |
| Reichel | Metamorphic testing of version control systems | |
| Ganai et al. | Reduction of verification conditions for concurrent system using mutually atomic transactions | |
| Hwang et al. | A model‐free and state‐cover testing scheme for semaphore‐based and shared‐memory concurrent programs |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20041214 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050214 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20050412 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050426 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090513 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090513 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100513 Year of fee payment: 5 |
|
| LAPS | Cancellation because of no payment of annual fees |