JPH0816429A - 並行プログラム作成支援装置及び並行プログラム作成方法並びに並行プログラム実行装置 - Google Patents

Abstract

(57)【要約】 【目的】 並行プログラムのテスト・デバッグを容易に
実現でき、並行プログラムの開発を効率よく行うことが
できる並行プログラムの作成方法及びその作成支援装置
並びに効果的なテスト・デバッグ及び再現性を保証した
部分並行実行を可能とする並行プログラム実行装置を提
供すること。 【構成】 本発明の並行プログラム作成支援装置は、並
行構造を有する第１並行プログラムを逐次実行可能な逐
次プログラムに変換する逐次化手段１２と、前記逐次プ
ログラムのテスト・デバッグを行い、テスト・デバッグ
情報を作成するテスト・デバッグ手段１６と、テスト・
デバッグ後の前記逐次プログラムを前記テスト・デバッ
グ情報に基づいて並行化することにより第２並行プログ
ラムに変換する並行化手段１８とを備えた。また、前記
テスト・デバッグ手段は、前記逐次プログラムに対して
並行性に関する情報を導入する手段を含む。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、並行プログラムの作成
方法及びその作成支援装置並びに並行プログラム実行装
置に関する。

【０００２】

【従来の技術】近年の半導体集積回路技術の進歩によ
り、複雑なプロセッサ及び大容量のメモリが小型かつ低
価格で実現できるようになり、多数のプロセッサからな
る並行処理システムや分散処理システムが実用化されて
いる。このようなハードウェアに対しては、専用のプロ
グラム、即ち並列プログラムや分散処理プログラム等
（以下「並行プログラム」という）を用いなければなら
ない。従って、並行プログラムをいかに効率よく開発す
るかは、優れたアルゴリズムを検討する場合と同様に重
要な課題となっている。

【０００３】ところで、プログラム開発においては、プ
ログラム中のバグを見つけ修正すること（即ちテスト・
デバッグ）と呼ばれる開発工程がプログラム開発の効率
に大きく影響する。しかし、並行プログラムの開発にお
いては、逐次プログラムの開発においては遭遇すること
のない、並行プログラム特有の問題を考慮する必要があ
る。この並行プログラム特有の問題とは、並行プログラ
ムを構成する各プロセスは、各プロセス間における相互
作用のタイミングにより様々な振る舞いをする可能性が
あるため、並行プログラム全体が正しく動作しないとい
う問題である。この問題は、並行プログラムの性質に基
づく問題であり、一般に「非決定性」と呼ばれる。

【０００４】例えば、図１１６に示す並行プログラムを
考慮する。図１１６（ａ）において、プロセスＰ１は、
共有メモリＭの初期設定（ｉｎｉｔ）を行うプロセス、
プロセスＰ２は、共有メモリＭから読み出し（ｒｅａ
ｄ）を行うプロセス、プロセスＰ３は、共有メモリＭに
書き込み（ｗｒｉｔｅ）を行うプロセスを示す。これら
のプロセスをそれぞれ異なるプロセッサで実行するよう
な並列処理システム等で動作させた場合、全部で６通り
（図１１６（ｂ）参照）の動作の組み合わせがあること
になる。通常、システムは初期設定で処理を開始するか
ら、今、プロセスＰ１（ｉｎｉｔ）→Ｐ２（ｒｅａｄ）
→Ｐ３（ｗｒｉｔｅ）又はＰ１（ｉｎｉｔ）→Ｐ３（ｗ
ｒｉｔｅ）→Ｐ２（ｒｅａｄ）の順番でプログラムが動
作する場合に正しい結果が得られるものとすれば、残り
の４通り（例えばＰ２→Ｐ３→Ｐ１）は、初期化が最初
に行われないため、明らかに正しい結果が得られないこ
とがわかる。

【０００５】上記のようにプロセスの振る舞いに関する
非決定性は、並行プログラムを動作させる毎に、その時
点におけるシステムの状況等によって結果を異なったも
のになる。従って、この非決定性に関する問題を解決し
ない限り、その並行プログラムは、テストにおいてたと
え正常に動作することがあっても、常に正常に動作する
という保証はない。

【０００６】また、非決定性に関するバグは、一般に、
逐次プログラムにおけるバグを見つける場合よりも困難
である。なぜなら、逐次プログラムにおいては、テスト
・デバッグ時にプログラム中の全てのパスを実行するこ
とによって動作を確認することができるのに対し、並行
プログラムにおいては、全ての組合せ的なパス（即ち、
各プロセス中の全てのパスのみならず、プロセス相互間
の振る舞い）を考慮してパスを実行しなければならない
からである。上記の例のようにプロセスの数が少ない場
合にあっては、各プロセス相互間の振る舞いを全て列挙
することは比較的容易であるが、実際のプログラム開発
では、その数は膨大になり、その組み合わせも膨大なも
のとなるため、全ての振る舞いを把握することはもはや
不可能なものとなる。

【０００７】

【発明が解決しようとする課題】上記のように、並行プ
ログラム開発におけるテスト・デバッグは、逐次プログ
ラム開発におけるテスト・デバッグに比較して、非常に
困難である。特に、プログラム自体が巨大化した今日に
おいては、このテスト・デバッグは一層困難になってい
る。

【０００８】更に、並行プログラム特有の問題である非
決定性によって再現性が保証されないことからテスト・
デバッグが困難となり、また予期せぬエラーが出現する
という問題を有する。

【０００９】本発明は、並行プログラムのテスト・デバ
ッグを容易に実現でき、並行プログラムの開発を効率よ
く行うことができる並行プログラムの作成方法及びその
作成支援装置を提供することを目的とする。

【００１０】本発明の他の目的は、並行プログラムを逐
次的に実行することにより再現性を保証し、効果的なテ
スト・デバッグを行なうことを可能とすると共に、テス
ト・デバッグ後に一部分を並行化して実行することによ
り、非決定性による予期せぬエラーを排除した安全な並
行プログラムの実行が可能な並行プログラム実行装置を
提供することである。

【００１１】本発明は並行プログラムを一旦逐次化し、
逐次化したプログラムに対してテスト・デバッグを行
い、テスト・デバッグが完了した時点で、プログラムの
並行性を復元することを骨子とする。

【００１２】

【課題を解決するための手段】本発明は、上記の課題を
解決するために次のような手段を講じた。並行プログラ
ムのプログラミングの困難さは、「人間の思考は本来逐
次的であり、並行に動くものをありのままでは論理的に
認識することは困難である」ことに起因する。そこで、
本発明は並行プログラムをいったん逐次化し、逐次化し
たプログラムに対してプログラミング、テスト・デバッ
グを行う。これは、従来の逐次プログラミングと同じレ
ベルの困難さである。そして、テスト・デバッグが完了
した時点で並行性を、そのテスト・デバッグ情報を用い
て、自動的に復元する。

【００１３】上記のようなプログラミングのスタイルを
「超逐次プログラミング」と呼ぶ。この「超逐次プログ
ラミング」によれば、従来の手法におけるプログラミン
グの困難さを解決できる。本発明の基本コンセプトは、
以下の３つのステップ（或いは手段）から構成される。

【００１４】（１） 並行プログラムを逐次化して超逐
次プログラムを生成するステップ（手段）。

【００１５】（２） 超逐次プログラムに対して、作業
（プログラミング、テスト・デバッグ、並行性の導入）
を行うステップ（手段）。

【００１６】（３） 作業が完了した超逐次プログラム
を並行化して並行プログラムを作成するステップ（手
段）。

【００１７】ここで、「超逐次プログラム」とは、オリ
ジナルの並行プログラムの並行構造に関する情報を保ち
ながら逐次化したプログラムをいう。

【００１８】本発明に係る並行プログラム作成装置は、
並行構造を有する第１並行プログラムを逐次実行可能な
逐次プログラムに変換する逐次化手段と、前記逐次プロ
グラムのテスト・デバッグを行い、テスト・デバッグ情
報を作成するテスト・デバッグ手段と、テスト・デバッ
グ後の前記逐次プログラムを前記テスト・デバッグ情報
に基づいて並行化することにより第２並行プログラムに
変換する並行化手段とを具備することを特徴とする。ま
た、本発明に係る並行プログラムの作成方法は、並行構
造を有する第１並行プログラムを逐次実行可能な逐次プ
ログラムに変換する第１ステップと、前記逐次プログラ
ムのテスト・デバッグを行い、テスト・デバッグ情報を
作成する第２ステップと、テスト・デバッグ後の前記逐
次プログラムを前記テスト・デバッグ情報に基づいて並
行化することにより第２並行プログラムに変換する第３
ステップとを具備することを特徴とする。

【００１９】本発明の好ましい態様を以下に列挙する。 （１） 前記逐次プログラムに対して並行性に関する情
報を導入すること。この並行性に関する情報は、例え
ば、後述する良い非決定性に関する情報を含む。 （２） 第１並行プログラムの並行構造を解析し、この
並行構造と逐次プログラムをテストして得られた実行結
果を用いて逐次プログラムの並行化を行うこと。

【００２０】（３） 第１並行プログラムの逐次プログ
ラムに変換されるセクションの並行構造と、逐次プログ
ラムのセクションの逐次構造をそれぞれ解析し、第１並
行プログラムの並行構造に関する相互関係及び逐次プロ
グラムの逐次構造に関する相互関係をグラフ情報として
表示する。このグラフ情報の表示においては、所定のセ
クション群をノードとし、第１並行プログラムの並行構
造に関する相互関係を第１アークとし、逐次プログラム
の逐次構造に関する相互関係を第２アークとしてグラフ
情報を表示する。そして、逐次プログラムのうち選択さ
れたセクションを並行化して部分的に逐次構造を有する
部分逐次プログラムに変換し、この部分逐次プログラム
を並行化して第２並行プログラムに変換する。

【００２１】ここで、第１並行プログラムを逐次プログ
ラムに変換するステップにおいて、逐次プログラムの所
望の実行結果が得られるまで逐次プログラムのテスト・
デバッグを行うステップを含ませるか、又は逐次プログ
ラムを部分逐次プログラムに変換するステップにおい
て、所望の実行結果が得られるまで部分逐次プログラム
のテスト・デバッグを行うステップを含ませるか、或い
はこれら両方のテスト・デバッグステップを含ませても
よい。

【００２２】更に、逐次プログラムを部分逐次プログラ
ムに変換するステップに、部分逐次プログラムの逐次構
造を解析するステップを含ませた上で、グラフ情報の表
示と並行化セクションの選択及び部分逐次プログラムへ
の変換のステップを所定回数繰り返すようにしてもよ
い。

【００２３】（４） 第１並行プログラムを逐次プログ
ラムに変換する逐次化に際して、この第１並行プログラ
ムを実行してそれによる実行ログを保存するとともに、
この保存された実行ログ及び第１並行プログラムを解析
し、この解析結果に基づいて、保存された実行ログを並
べ替える。実行ログ及び第１並行プログラムの解析にお
いては、例えば保存された実行ログ及び第１並行プログ
ラムからプロセスの先行関係を抽出し、これを先行関係
情報として保存する。

【００２４】（５） 逐次プログラムに対する並行性に
関する情報の導入に際して、逐次プログラムのプロセス
の流れを制約と遷移条件からなるフィールドに変換し、
このフィールドをチューニングすることによって行う。
更に、このフィールドを表すフィールドデータを表示す
る。

【００２５】（６） 逐次プログラムに対して並行化の
候補となるプロセス群を指定し、このプロセス群の実行
順序を入れ換えて逐次プログラムを複数の並行模擬プロ
グラムに変換した後、これら複数の並行模擬プログラム
を部分的に逐次構造を有する１つの部分逐次プログラム
に変換し、この部分逐次プログラムを並行化して第２並
行プログラムに変換する。

【００２６】ここで、第１並行プログラムを逐次プログ
ラムに変換するステップにおいて、逐次プログラムの所
望の実行結果が得られるまで該逐次プログラムのテスト
・デバッグを行うステップを含ませるか、又は複数の並
行模擬プログラム群を１つの部分逐次プログラムに変換
するステップにおいて、並行模擬プログラム群の所望の
実行結果が得られるまで複数の並行模擬プログラムのテ
スト・デバッグを行うか、或いはこれら両方のテスト・
デバッグステップを含ませてもよい。また、逐次プログ
ラムに対して並行化の候補となるプロセス群を指定する
際、第１並行プログラムを解析し、この解析結果から並
行化の候補となるプロセス群を抽出してもよい。また、
逐次プログラムを複数の並行模擬プログラムに変換する
ステップにおいて、複数の並行模擬プログラムの一部の
実行結果から不要と判断される並行模擬プログラムを取
り除くステップを含ませてもよい。更に、複数の並行模
擬プログラムを１つの部分逐次プログラムに変換するス
テップにおいて、部分逐次プログラムに対して並行化の
候補となるプロセス群を指定するステップを含ませ、逐
次プログラムを複数の並行模擬プログラムに変換するス
テップと、複数の並行模擬プログラムを１つの部分逐次
プログラムに変換するステップを所定の回数繰り返して
もよい。

【００２７】（７） 第１並行プログラムの逐次プログ
ラムへの変換を所定の逐次化ルールに従って行う場合、
この逐次化ルールを修正することによって、逐次プログ
ラムに対して並行性に関する情報を導入する。

【００２８】（８） プロセス群がメッセージ情報を交
換しながら並行して動作する実行環境に用いられる並行
プログラムの作成を支援する並行プログラム作成支援装
置において、並行プログラムのプロセス群の実行履歴で
あるログ情報を逐次化ルールとして取得して記憶し、こ
の記憶したログ情報を修正可能とする。記憶されている
ログ情報に基づいてプロセス群を逐次的に起動制御し、
また記憶されたログ情報を並行化して第２並行プログラ
ムに変換する。

【００２９】ここで、ログ情報修正手段は、前記ログ情
報記憶手段に記憶されているログ情報を時系列に表示す
る表示手段と、前記表示手段により時系列に表示された
ログ情報内のデータの順序の入れ換えを指示するための
入れ替え指示手段と、前記入れ替え指示手段による指示
に従って前記ログ情報記憶手段に記憶されているログ情
報を書き換える書換手段とを含むことを特徴とする。ま
た、ログ情報修正手段は、プロセス間の処理タイミング
の非決定性を導入する非決定性導入手段を含むことを特
徴とする。

【００３０】（９） プロセス群がメッセージ情報を交
換しながら並行して動作できる実行環境で前記プロセス
群が実行順序規定情報に従って動作するシステムにおい
て、実行順序規定情報を分割し、この分割された実行順
序情報に基づいてプロセス群を起動制御する。

【００３１】この場合、実行順序規定情報を分割するた
めの基準を与える分割基準指定手段を保持する手段を更
に具備してもよい。また、メッセージ交換の履歴を実行
順序規定情報として用いるとともに、分割基準指定手段
における分割基準としてメッセージ中の宛先プロセス情
報を基準として用いる。また、メッセージ交換の履歴を
実行順序規定情報として用い、分割基準指定手段におけ
る分割基準として前記メッセージ中の宛先プロセス情報
を基準として用いるとともに、プロセス制御手段を各プ
ロセス毎に保持する手段を具備する。更に、メッセージ
交換の履歴を実行順序規定情報として用い、分割基準指
定手段における分割基準として前記メッセージ中の宛先
プロセス情報を基準として用いるとともに、プロセス制
御手段を各プロセス毎に保持する手段と、実行順序情報
分割手段によって分割された実行順序情報をそれぞれ別
々に保存する分割実行順序情報保存手段を具備し、プロ
セス制御手段は該プロセスに対応する分割実行順序情報
保存手段に保存されている分割実行順序情報に基づいて
プロセスを起動制御する。また、プロセス群の実行履歴
情報であるログ情報を実行順序規定情報として用いても
よい。

【００３２】（１０） 第１並行プログラムをテスト実
行して、そのテスト実行の結果バグのない実行ログを蓄
積し、この蓄積されたバグのない実行ログのみを並行化
して第２並行プログラムに変換する。更に、テスト実行
の結果バグのある実行ログを蓄積し、この蓄積されたバ
グのある実行ログに基づいて第１並行プログラムを修正
する。

【００３３】また、本発明の並行プログラム実行装置
は、並行プログラムを解析してセクションを抽出し、そ
れらのセクション間の実行時の同期を制御するための実
行順序に関するルールを抽出するプログラム解析手段
と、実行時のセクション間の同期を調節するために実行
順序に関するルールを編集し、主に実行の効率化のため
に、抽出された当該セクションを融合・分割する編集手
段と、セクションをオブジェクトに変換するコンパイル
手段と、該実行順序に関するルールに従いセクション単
位で逐次又は並行に実行を行なう実行手段を具備する。

【００３４】

【作用】上記手段を講じた結果、次のような作用が生じ
る。本発明では並行プログラムを一旦逐次化し、逐次化
したプログラムに対してテスト・デバッグを行うことに
より、従来の並行プログラムのプログラミングより遥か
に容易な逐次プログラミングと同じレベルの困難さで並
行プログラムのテスト・デバッグが可能となる。

【００３５】また、本発明では、いったん逐次化された
プログラムに対して意図的に並行性に関する情報（良い
非決定性）を導入できるので、意図しない並行性（悪い
非決定性）に基づいて発生するバグを回避でき、高信頼
化が達成できる。

【００３６】上記のグラフ情報によって並行化及び逐次
化の情報をユーザに対して同時に提示することにより、
ユーザは第１並行プログラムの並行構造を考慮しつつ、
良い非決定性部分の指定をすることができるようにな
る。また、並行プログラム記述レベルにおける良い非決
定性部分の指定・解除ではなく、グラフ情報に対して良
い非決定性部分を指定・解除を行うことでができるた
め、高度な並行プログラミング技術を必要とすることな
く、容易に並行プログラムの開発をすることができるよ
うになる。

【００３７】第１並行プログラムを逐次プログラムに変
換する際、第１並行プログラム及びその実行ログを解析
し、この解析結果に基づいて実行ログを並べ替えるよう
にすれば、並べ替え後の実行ログを表示してユーザに提
示することによって、並行プログラムの実行過程の理解
が容易となり、テスト・デバッグの効率が向上する。逐
次プログラムに並行性に関する情報を導入する際、逐次
プログラムのプロセスの流れを制約と遷移条件からなる
フィールドに変換し、更にそのフィールドデータを表示
することによって、フィールドを対話的・視覚的に編集
することで並行性に関する情報を効果的に導入し、バグ
のない並行プログラムが効率的に作成される。

【００３８】第１並行プログラムから逐次化された逐次
プログラムに対して並行化の候補となるプロセス群を指
定し、このプロセス群の実行順序を入れ換えて逐次プロ
グラムを複数の並行模擬プログラムに変換した後、これ
ら複数の並行模擬プログラムを部分的に逐次構造を有す
る１つの部分逐次プログラムに変換し、この部分逐次プ
ログラムを並行化して第２並行プログラムに変換するこ
とにより、部分逐次プログラム上で並行プログラムの動
作を十分に確認することができる。また、部分逐次プロ
グラムに対して並行化の候補となるプロセス群を指定す
ることで、逐次構造プログラムを段階的に並行プログラ
ムへ変換することができる。更に、並行模擬動作系列に
基づく逐次実行で正しく動作することが確認された非決
定性のみを許容する並行性に関する情報を導入すること
で、正しく動作する並行プログラムを得ることができ
る。これらによって、並行プログラムのテスト・デバッ
グが容易となる。

【００３９】プロセス群がメッセージ情報を交換しなが
ら並行して動作する実行環境に用いられる並行プログラ
ムの作成を支援する並行プログラム作成支援装置におい
て、第１並行プログラムのプロセス群の実行履歴である
ログ情報を逐次化ルールとして取得して記憶し、このロ
グ情報を修正可能とするとともに、記憶されているログ
情報に基づいてこれに基づいてプロセス群を逐次的に起
動制御し、記憶されたログ情報を並行化して第２並行プ
ログラムに変換することにより、ソースプログラムとし
ての並行プログラムを修正することなく、ログ情報の修
正で処理タイミングの非決定性に起因する不具合を解決
できる。これにより、処理タイミングの非決定性が内在
する並行／並列／分散プログラムの開発が容易となる。
また、ユーザの意図する良い非決定性のみを容易に導入
することができるため、並行プログラムとしての柔軟
性、再利用性及び拡張性を維持することもできる。

【００４０】プロセス群がメッセージ情報を交換しなが
ら並行して動作できる実行環境でプロセス群が実行順序
規定情報に従って動作するシステムにおいて、実行順序
規定情報を分割し、つまり並行プログラムを逐次化して
得られた全プロセスの集中ログ情報を各プロセス毎に分
割し、この分割された実行順序情報に基づいてプロセス
群を起動制御することにより、無害の非決定性を自然に
導入し、集中ログ情報に基づく逐次プログラムの実行時
と同一結果を高い処理効率で得ることが可能となる。

【００４１】第１並行プログラムをテスト実行してその
テスト実行の結果、その１つであるバグのない実行ログ
を蓄積し、この蓄積されたバグのない実行ログのみを並
行化して第２並行プログラムに変換することにより、テ
ストで通過したタイミングだけを許容するようにプログ
ラムが動くようになるため、テストしなかったことで残
存したバグに陥ることを回避でき、信頼性が向上する。

【００４２】本発明の並行プログラム実行装置によれば
並行プログラムの逐次又は部分並行実行を行なうことが
可能となるので、従来の逐次プログラムと同様に再現性
を保証することができ、効果的かつ安定したテスト・デ
バッグを行なうことができる。また、逐次実行から部分
並行実行に容易に切替えることができるため、逐次化し
てテスト・デバッグをおこなったプログラムを非決定性
に影響されない安全な並行実行を可能とする。他に、セ
クションの実行順序に関するルールを編集して実行時の
セクション間の同期を制御することにより、効果的なテ
スト・デバッグを行なえるとともにプログラムの効率化
の指針とすることもできる。

【００４３】更に、本発明の並行プログラム実行装置
は、本発明の並行プログラム作成支援装置或いは作成方
法と組み合わせて用いることもできる。この場合には、
並行プログラム実行装置は、第１並行プログラム（ソー
スプログラム）の実行手段として、機能する。更に、並
行プログラム実行装置は、本発明の並行プログラム作成
支援装置或いは作成方法により作成された並行プログラ
ムの検証用としても利用できる。

【００４４】

【実施例】以下、図面を参照して本発明の実施例を説明
する。本発明の実施例の説明を行う前に、本発明におい
て使用する用語を以下のように定義する。

【００４５】並行システム：論理的な並行性を持つシス
テム。並行プログラムが動くシステムは並行システムで
ある。並列計算機や分散処理システムは並行システムで
ある。

【００４６】並行プログラム（ＣＰ）：論理的に並行に
動くモデルに基づいて記述されたプログラム。複数のＣ
ＰＵから構成される並列計算機上で、論理的にも物理的
にも並行に動くプログラム（並列プログラム）は、並行
プログラムに含まれる。また、単一のＣＰＵ上で物理的
には逐次的に動く場合でも、マルチタスクシステムのよ
うに論理的に並行であれば、並行プログラムに含まれ
る。

【００４７】逐次プログラム：論理的に逐次に動くモデ
ルに基づいて記述されたプログラム。

【００４８】超逐次プログラム（ＨＳＰ）：並行プログ
ラムにメタレベル（実行管理レベル）の制御を付加する
ことによって、逐次的に動くようにしたプログラム。例
えば、並行プログラムとして記述されたプログラムを、
実行管理レベルのスケジューラを付加することによって
逐次的に動くようにしたプログラムは、超逐次プログラ
ムである。超逐次プログラムは後述する非決定性を持た
ないので、外部からの入力が同じならばその挙動は必ず
再現性を持つ。また、超逐次プログラムにおいて、部分
的に並行性（非決定性）を導入することもできる。部分
的に並行性（非決定性）が導入された超逐次プログラム
を、特に、部分超逐次プログラム（ＰＨＳＰ）、並行性
（非決定性）が全くなく完全に逐次化されたプログラム
を完全超逐次プログラムと呼ぶこともある。

【００４９】非決定性：入力が同じにもかかわらず、処
理のタイミングによってシステムの挙動が変わること。
並行プログラムの実行において、非決定性は本質的側面
である。ある意味で、非決定性のないプログラムは論理
的に逐次プログラムと等価である。

【００５０】良い非決定性：ユーザの意図する非決定性
をいう、即ち、ユーザの仕様、その他実現要求に含まれ
る非決定性。この非決定性により、外部（環境）からの
非決定的な入力に適切に応答できるようになる。

【００５１】悪い非決定性：ユーザが予想しなかった非
決定性。ユーザの思考回路は逐次的であるため、設計時
には意図しなかったケースが実際の並行プログラムの実
行では多々発生する。

【００５２】無害な非決定性：その非決定的な選択肢の
選択が、最終的な結果に影響しないもの。「超逐次プロ
グラミング」の並行化装置において、並行化する対象
は、この「無害な非決定性」を含む。

【００５３】デフォルト逐次化：実行管理レベルで逐次
化制御を行なうこと。

【００５４】並行模擬プログラム：超逐次プログラムに
おいて、並行化の候補となる特定の範囲について生成さ
れた並行模擬動作系列の集合。

【００５５】・並行模擬動作系列：超逐次プログラムに
おいて並行化の候補となる特定の範囲について並行プロ
グラムの動作を逐次プログラム上で模擬することを目的
として、逐次実行の順序を任意又は意図的に入れ替えて
生成される１つの動作列のこと。一般に、１つの並行化
範囲には複数の並行模擬動作系列が生成されるので、そ
の全体を１つの並行模擬プログラムという。超逐次プロ
グラム全体では複数の並行模擬プログラムが生成され
る。

【００５６】図１は、本発明に係る並行プログラム作成
支援装置を実現するためのコンピュータシステムの構成
例を示す図である。図１において、Ｎ台のプロセッサ１
−１、１−２、…、１−Ｎは、並行プログラムを同時に
実行することができ、Ｉ／Ｏインタフェース２を介して
共有メモリ３及び周辺装置とアクセスすることができ
る。周辺装置は、入力装置４と出力装置５及び外部記憶
装置６から構成される。入力装置４は、キーボードとポ
インティングデバイス等とからなり、各種コマンドやデ
ータの入力をするために用いられる。出力装置５は、Ｃ
ＲＴディスプレイ等からなり、ソースプログラムやテス
ト・デバッグ状況に関する情報等をテキスト又はグラフ
ィック表示することにより、ユーザに提示する。ユーザ
は、これら入力装置４及び出力装置５を用いて、対話的
にコンピュータを操作することができる。

【００５７】外部記憶装置６は、磁気ディスクや光磁気
ディスク等からなり、ソースプログラムやテスト・デバ
ッグ状況に関する情報を書き込み又は読み出すことがで
きるようになっている。

【００５８】なお、上記説明したコンピュータシステム
の構成は、これにこだわる必要はなく、例えば、複数の
計算機をネットワークを用いて接続した、いわゆる分散
ネットワークを用いて構成してもよい。

【００５９】上記のように構成されたコンピュータシス
テムにおいて、本発明における並行プログラムの作成
は、以下のようにして実現される。

【００６０】（実施例１）実施例１では、テスト・デバ
ッグは部分超逐次プログラムに対して行い、好ましい実
施例として良い非決定性の導入を超逐次プログラムに対
して行う。なお、以下の実施例において、良い非決定性
を導入した例を説明するが、必ずしも良い非決定性を導
入しなくても良い。

【００６１】図２は、実施例１に係る並行プログラム作
成支援装置の概略構成を示す図である。実施例１に係る
並行プログラム作成支援装置は、逐次化装置１２と、テ
スト実行装置１５と、デバッグ装置１６と、非決定性導
入装置１７と、並行化装置１８とを具備する。

【００６２】逐次化装置１２は、第１ＣＰファイル記憶
部１１に記憶されたソースプログラム（以下、「第１並
行プログラム」と称する）を逐次化ルール記憶部１３に
記憶された逐次化ルールに基づいて超逐次プログラムに
変換して、その結果がＨＳＰファイル記憶部１４に記憶
される。第１ＣＰファイル記憶部１１には、モデル化さ
れ並行プログラミング言語で記述された第１並行プログ
ラムが格納されている。この第１並行プログラムには、
バグが存在する可能性がある。第１並行プログラムを記
述する並行プログラミング言語には、例えば以下のもの
がある。 （ａ）Ｃｏｎｃｕｒｒｅｎｔ ＰＡＳＣＡＬ （ｂ）ＡＤＡ （ｃ）ＧＨＣ （ｄ）Ｍｏｄｕｌａ３ （ｅ）Ｏｃｃａｍ （ｆ）ｃｏｏＣ テスト実行装置１５及びデバッグ装置１６は、それぞ
れ、ＨＳＰファイル記憶部１４に記憶された超逐次プロ
グラムのテスト・デバッグを行う。

【００６３】非決定性導入装置１７は、第１並行プログ
ラムを超逐次プログラムに変換する際に、良い非決定性
を導入する。

【００６４】並行化装置１８は、ＨＳＰファイル記憶部
１４に記憶された超逐次プログラムのテスト・デバッグ
情報に基づいて、超逐次プログラムを並行化して、第２
並行プログラムを生成する。この第２並行プログラム
は、第２ＣＰファイル記憶部１９に記憶される。

【００６５】図３は、実施例１に係る並行プログラム作
成方法の概略手順を示すフローチャートである。

【００６６】（１） ステップＡ１：モデル化 対象の並行システムに対し、並行性を用いた自然なモデ
ル化を行う。また、並行システムの各プロセス構造を決
定する。更に、該各プロセス内を並行プログラム等を用
いたプログラミングにより、並行構造を有する並行プロ
グラムをソースプログラムとして記述する。なお、「並
行構造を有する」としたのは、一般に並行プログラム
は、その全てが並行構造で構成されているわけではな
く、逐次性を用いたモデル化の方がより自然である場合
には、その部分は逐次構造である場合があるからであ
る。なお、このソースプログラムには、バグが潜在的に
存在する可能性がある。

【００６７】（２） ステップＡ２：逐次化 デフォルト逐次化によって、第１並行プログラムを逐次
構造の超逐次プログラムに変換する。本実施例では、メ
タレベルにおいて逐次性を導入する。ここで、メタレベ
ルとはソースプログラム（すなわち、第１並行プログラ
ム）そのもののレベルではなく、ソースプログラムの実
行を管理するレベルをいう。例えば、並行プログラムで
記述されたソースプログラムを、それとは別に管理され
るスケジューラによって逐次的に実行することを保障し
たプログラムのソースプログラムに変換する。

【００６８】（３） ステップＡ３：超逐次プログラム
のテスト・デバッグ 超逐次プログラムのテスト・デバッグを行う。テスト実
行装置により超逐次プログラムをテスト実行した結果に
基づいて、デバッグ装置により超逐次プログラムからバ
グを除去する。ここでのテスト・デバッグは、逐次プロ
グラムにおける通常のテスト・デバッグ方法と同様に行
うことができる。超逐次プログラムが正常に動作するこ
とが保障されるまで、テスト・デバッグを行う。

【００６９】（４） ステップＡ４：超逐次プログラム
に対する良い非決定性の導入 テスト・デバッグが行われた超逐次プログラムに対し
て、良い非決定性に関する情報（並行性に関する情報）
を与える。これにより超逐次プログラムは、非決定性に
関する情報を一部に持つことで、部分超逐次プログラム
となる。良い非決定性に関する情報の導入方法は後述す
る。

【００７０】（５） ステップＡ５：部分超逐次プログ
ラムのテスト・デバッグ ステップＡ４で得られた部分超逐次プログラムに対し
て、テスト・デバッグを行う。すなわち、ステップＡ４
で良い非決定性に関する情報が導入された超逐次プログ
ラムをテスト・デバッグする。

【００７１】（６） ステップＡ６：部分超逐次プログ
ラムに対する良い非決定性の導入・拡大 ステップＡ５でテスト・デバッグが行われた部分超逐次
プログラムに対して、良い非決定性に関する情報を追加
する。ステップＡ５〜ステップＡ６を所定の回数繰り返
し、良い非決定性を徐々に拡大していく。

【００７２】（７） ステップＡ７：並行化コンパイル 良い非決定性に関する情報が導入された部分超逐次プロ
グラムのうち、無害な非決定性部分を抽出し、その部分
を並行化することで、部分超逐次プログラム全体を並行
プログラム（すなわち、第２並行プログラム）に復元す
る。すなわち、並行化に関する情報が導入されなかった
部分に関しては、デフォルト逐次化で与えられた逐次性
を並行プログラム中に反映させて（例えば、ソースプロ
グラム自体に埋め込む）、メタレベルのデフォルト逐次
性は解除する。

【００７３】図４〜図７を参照して、本発明をより具体
的に説明する。

【００７４】図４は、簡単な並行プログラムの一例を示
す図である。

【００７５】図４の並行プログラムは、プロセスＰ１と
プロセスＰ２とから構成されている。これらのプロセス
は、並行プログラムのソースコードがコンパイルされる
ことにより生成された実行モジュールがコンピュータ上
で実行された時に初めて実体化するものであり、プロセ
スＰ１とプロセスＰ２とにそれぞれ対応する並行プログ
ラムが必ずしも物理的に別の記憶媒体に記憶されている
必要はない。また、メモリＭはここでは共有メモリ(sha
red memory) を表し、並行プログラムのアクセス命令に
よって書き込み／読み込み等のアクセスを行うことがで
きる。図４において実線矢印はプロセスＰ１、Ｐ２が実
行された時に共有メモリＭとの間でアクセスが行われる
ことを示す。

【００７６】ＣＰファイル記憶部１１に格納された第１
並行プログラムは、ユーザによる入力装置４からの指示
により引き出され、逐次化装置１２に入力される。逐次
化装置１２に入力された第１並行プログラムは、逐次化
ルール記憶部１３に格納された逐次化ルールに従って、
メタレベルにおいてデフォルト逐次性が導入されること
により、超逐次プログラム（ＨＳＰ）に変換され、ＨＳ
Ｐファイル記憶部１４に記録される。

【００７７】逐次化ルールの代表的なものには以下のも
のがある。 （ａ）プロセスに優先度を導入するルール。 （ｂ）プロセス内の処理単位（オブジェクト指向におけ
るメソッド）に優先度を導入するルール。 （ｃ）具体的な実行ログに基づく逐次化ルール。 （ｄ）メッセージの到着先の実行を優先する逐次化ルー
ル。 （ｅ）メッセージの送信元の実行を優先する逐次化ルー
ル。

【００７８】図４の下方に記載した" Ｐ１＞＞Ｐ２" が
図４の並行プログラムに対する逐次化ルールの一例であ
り、二つのプロセスＰ１、Ｐ２に対してＰ１をＰ２より
優先的に動作させるという優先度を与えることを表して
いる。これは上記（ａ）のルールに相当する。この逐次
化ルールは、例えば第１並行プログラムの先頭で宣言し
ておき、プログラム本体ととともにコンパイルすること
により並行プログラムに導入するようにしても良いし、
並行プログラムとは別にファイルに記述しておき、並行
プログラムが実行時にオペレーティングシステムやスケ
ジューラが解釈することにより導入するようにしても良
い。なお、本実施例では逐次化ルールを" ＞＞" で示し
たが、これに限らず任意の記号を用いることができる。

【００７９】図５は、メタレベルにおいてデフォルト逐
次性が導入された超逐次プログラムＨＳＰの概念図であ
り、プロセスＰ１とプロセスＰ２とはスケジューラＳに
よって管理されていることを示しており、図５におい
て、破線矢印は図４に示した逐次化ルール（" Ｐ１＞＞
Ｐ２" ）に従って、スケジューラＳがプロセスＰ１を実
行後、プロセスＰ２を実行することを示す。なお、この
超逐次プログラムＨＳＰの概念図は、図５の下方に記載
した式、 ＨＳＰ＝Ｐ１｜Ｐ２｜Ｓ のように記述するものとする。これは、超逐次プログラ
ムＨＳＰはプロセスＰ１とプロセスＰ２とスケジューラ
Ｓとから構成されていることを示す。ここで、逐次化ル
ールはスケジューラのスケジューリング規則に対応す
る。

【００８０】ユーザは、この超逐次プログラムＨＳＰを
出力装置５によって見ることができる。この超逐次プロ
グラムＨＳＰは、ユーザによる入力装置４からの指示に
よってテスト実行装置１５に入力され、テスト実行が行
われる。テスト実行装置１５は、テスト実行の結果（実
行ログ）を出力装置５に提示する。ユーザは、このテス
ト実行の結果に基づいて、入力装置４をデバッグ装置１
６として用いて、超逐次プログラムＨＳＰに対し所定の
テスト・デバッグを行うことができる。具体的なテスト
・デバッグ技術には、 （ａ）ソースコードのトレーサ （ｂ）ブレークポイント （ｃ）アニメーション 等がある。

【００８１】図６は、この時のテスト・デバッグのイメ
ージを表す図である。図６において、出力装置５上のデ
バッグ画面６０には、各種ウィンドウ６１〜６５がオー
プンされ、各種情報が表示されており、これらウィンド
ウ６１〜６５は、適宜オープン・クローズすることが可
能である。なお、ここでのテスト・デバッグは、基本的
には公知のデバッグ装置を用いることができ、具体的に
は、ＵＮＩＸワークステーション上のｄｂｘｔｏｏｌ等
が知られている。

【００８２】ユーザは、超逐次プログラムＨＳＰに対し
て所定のテスト・デバッグを行った後、入力装置４から
再度テスト実行の指示を与える。これにより、テスト・
デバッグの行われた超逐次プログラムＨＳＰは、テスト
実行装置１５に入力され、再度テスト実行が行われる。
このテスト・デバッグは、超逐次プログラムＨＳＰが正
常に動作することを確認するまで繰り返し行われる。テ
スト・デバッグにより正常に動作することを確認した時
点で、非決定性導入装置１７により超逐次プログラムに
対して良い非決定性に関する情報を部分的に導入してい
く。非決定性導入装置１７より導入された良い非決定性
に関する情報は、超逐次プログラムＨＳＰに反映され、
ＨＳＰファイル記憶部１４に記録される。なお、非決定
性導入装置１７については後述する。

【００８３】図７は、超逐次プログラムに良い非決定性
に関する情報が導入された状態の一例を示す図である。
ここで、並行プログラムの各プロセスの実行単位を「セ
クション」と呼ぶと、図７はセクションＳ１とセクショ
ンＳ２とに分けられたプロセスＰ１と、セクションＳ３
とセクションＳ４とに分けられたプロセスＰ２につい
て、セクションＳ２とセクションＳ３の優先度を同じも
のとすることにより、非決定性が導入された状態を示
す。

【００８４】より具体的には、実行単位毎に異なる優先
度を与えている逐次化ルールに対し所定の部分に良い非
決定性に関する情報を与える（例えば、優先度を同じに
したいプロセスをマウスで指定する）ことにより、当該
部分については優先度を同じとして、並行に実行可能に
する。図７の例では、Ｓ１〜Ｓ４の４つのセクションの
うち、「Ｓ２である" ｗｒｉｔｅ１" とＳ３である" ｒ
ｅａｄ２" の優先度を同じにする」という情報（Ｓ２＝
Ｓ３）を良い非決定性として導入している。すなわち、
優先度が同じプロセスは、どちらが先に実行されてもか
まわないので、非決定性を持つ。

【００８５】次に、非決定性導入装置１７により良い非
決定性に関する情報が導入された超逐次プログラム（部
分超逐次プログラムＰＨＳＰ）は、ユーザからの指示に
従ってテスト実行装置１５によりテスト実行が行われ、
デバッグ装置１６によりテスト・デバッグが行われる。
この場合、部分超逐次プログラムＰＨＳＰの振る舞い
は、良い非決定性に関する情報の導入された部分につい
ては非決定的な振る舞いをするので、その振る舞い全て
についてテスト・デバッグを行うことが好ましい。この
ようにして、テスト・デバッグ及び良い非決定性に関す
る情報の導入を繰り返し、良い非決定性に関する情報を
徐々に付加していく。

【００８６】良い非決定性に関する情報がインクリメン
タル(incremental) に導入されて得られた部分超逐次プ
ログラムＰＨＳＰは、ユーザからの指示により並行化装
置１８に入力される。並行化装置１８は、部分超逐次プ
ログラムＰＨＳＰのうち無害な非決定性部分を抽出し、
部分超逐次プログラムＰＨＳＰ全体を並行化する。即
ち、並行化装置１８は、導入された良い非決定性と無害
な非決定性に関してデフォルト逐次性を解除し、並行プ
ログラムＣＰ（第２並行プログラム）としてファイルに
記録する。ここで、良い非決定性と無害な非決定性以外
はデフォルト逐次化で与えられた逐次性が並行プログラ
ムＣＰに反映されなければならない。ユーザは、この第
２並行プログラムを出力装置５によって見ることができ
るとともに、最終的なテスト・デバッグを行うことがで
きる。

【００８７】実施例１は、本発明の基本的な実施例を示
したが、以下、更に詳細な実施例を実施例を説明する。
但し、以下の実施例においては、実施例１と共通の部分
や相対応する部分については同一符号を付して説明を簡
略化するか又は省略し、相違点を中心に説明する。

【００８８】（実施例２）実施例２では、実施例１と同
様に、次のような並行プログラムを対象とする。並行プ
ログラムは複数のプロセスから構成される。並行プログ
ラムは、共有メモリ型のマルチプロセッサで実行され
る。各プロセス毎にプロセッサ（ＣＰＵ）が割り当てら
れる。各プロセスの同期は、同期基本命令と共有メモリ
型で実現される。

【００８９】上記の並行プログラムに本発明を適用した
実施例を説明する。図８は、実施例２に係る並行プログ
ラム作成支援装置の概略構成を示すブロック図であり、
図９は、実施例２に係る並行プログラム作成方法の概略
手順を示すフローチャートである。図８が、図２と異な
る点は、セクション設定装置７を更に具備し、テスト実
行装置１５とデバッグ装置１６とを、具体的に、テスト
実行装置１５、修正装置９、及び解析装置１０とし、解
析装置１０で解析された解析情報を記憶する解析情報記
憶部２０を有する点である。解析装置１０では、超逐次
プログラムを解析し、解析情報として後述する先行制約
を抽出する。他の構成部分は実施例１と同様であるの
で、説明を省略する。なお、図８には、並行化装置１８
で、超逐次プログラムの並行化を行う際に参照される並
行化ルールを記憶する並行化ルール記憶部２１を入れて
いる。

【００９０】セクション設定装置７は、第１並行プログ
ラムの各プロセスをいくつかのセクション（プログラム
単位）に分割する。

【００９１】修正装置９は、テスト実行装置１５による
テストの結果バグがあれば、修正を行う。

【００９２】テスト実行装置１５は、実施例１と同様
に、超逐次プログラムのテストを行う。

【００９３】解析情報記憶部２０は、解析装置１０で解
析された情報を記憶する。

【００９４】実施例２の動作を図９のフローチャートを
参照して説明する。なお、図９において、図３のフロー
チャートと同一動作には同一の符号を付す。

【００９５】（１） ステップＡ１：モデル化 対象の並行システムに対し、並行性を用いた自然なモデ
ル化を行う。また、並行システムの各プロセス構造を決
定する。更に、該各プロセス内を並行プログラム等を用
いたプログラミングにより、並行構造を有する並行プロ
グラムをソースプログラムとして記述する。このソース
プログラムには、バグが潜在的に存在する可能性があ
る。

【００９６】（２） ステップＢ１：セクションの設定 セクション設定装置７により、設計者が第１並行プログ
ラムの各プロセスをいくつかのセクション（単位）に分
割する。ここで、第１並行プログラム中の同期命令は自
動的に単独のセクションとする。ここで、セクションは
プロセスの処理の単位であり、以下のステップでは、セ
クションを単位として、逐次化及び並行化を行う。この
場合において、設計者によるセクション設定がなくても
構わない。この場合は、同期命令で区切られる区間が自
動的にセクションになる。

【００９７】セクションの設定は、プロセスのソースコ
ードを分割し、分割された各区間にセクションＩＤを設
定することで実現できる。ソースコード分割の一例とし
ては、図１０に示すように、区切りポイントを挿入し、
区切りポイントから次の区切りポイントまでの処理をセ
クションとする方法がある。ここで、上記のように同期
命令の前後には自動的に区切りポイントが挿入される。

【００９８】（３） ステップＡ２：逐次化 逐次化ルールに基づき、逐次化装置により、第１並行プ
ログラムを逐次化する。逐次化ルールの一例としては、
プロセスに優先度を導入する方式がある。この優先度に
基づいて実行すれば、実行時の非決定性は存在しないの
で、超逐次プログラムとみなすことができる。このよう
にして並行構造に関するプログラム情報を持ちながら逐
次化されたプログラムを超逐次プログラムとする。逐次
化方式の一例としては、「プロセスの優先度」に基づく
方式がある。この方式によれば、プロセスに予め固定の
優先度を設定し、優先度が高いプロセスのセクションの
実行を優先することにより、非決定性のない逐次的な実
行順序が得られる。別の逐次化方式の例としては、図１
１に示すような「同期命令のwait側の実行を優先する方
式（逐次化ルール１）」や「同期命令のsend側の実行を
優先する方式（逐次ルール２）」等がある。ここで、超
逐次プログラムは、３種のプログラム情報、すなわちセ
クション情報と、プログラム構造情報と、逐次化情報と
から構成される。セクション情報は、セクションの識別
子（ＩＤ）とセクションの属するソースコードの情報で
ある。プログラム構造情報は、オリジナルの並行プログ
ラムにおける、プロセス毎のセクションの実行順序情
報、更に、異なるプロセスのセクション間のデータ依存
関係の情報である。逐次化情報は、逐次化によるグロー
バルなセクションの実行順序情報であり、同時によい並
行性の関する情報も持つ。一例としては、並行システム
のモデル化手法であるペトリネットで逐次化情報を表現
する方法がある。

【００９９】（４） ステップＡ３：超逐次プログラム
に対するテスト・デバッグ 超逐次プログラムに対して、テスト実行装置１５でテス
トを行い、バグがある場合は、修正装置９でデバッグ／
修正を行う。また、プログラムの修正が同期命令等の並
行構造の変更にも及ぶ場合は、ステップＡ１に戻り、プ
ログラム作成装置８でモデル化を行い、再度セクション
の設定及び逐次化を行う。ここで、プログラム６は逐次
化されているので、テスト・デバッグは逐次プログラム
なみに容易になる。

【０１００】（５） ステップＡ４：超逐次プログラム
に対する良い非決定性の導入 非決定性導入装置１７により、出力装置５に超逐次プロ
グラムの構造が示される。設計者はこの構造を見ながら
非決定性導入装置１７により良い非決定性による並行性
を明示的に導入できる。この時、解析装置１０により抽
出された超逐次プログラムのプログラム情報により、設
計者による良い非決定性の導入を支援する。良い非決定
性の導入の必要がなければ、ステップＢ２に進む。良い
非決定性の導入方式として、例えば、超逐次プログラム
の逐次化情報がペトリネットで表現されている場合に
は、プログラム構造を保存する範囲でのペトリネットの
書換によって良い非決定性を導入する。

【０１０１】（６） ステップＡ５：テスト・デバッグ 良い非決定性が導入された超逐次プログラムに対して、
ステップＡ３と同様に、テスト実行装置１５でテストを
行い、バグがある場合は、修正装置９でテスト・デバッ
グを行う。また、プログラムの修正が同期命令等の並行
構造の変更にも及ぶ場合は、ステップＡ１に戻り、プロ
グラム作成装置で修正を行い、再度セクションの設定及
び逐次化を行う。ここで、プログラム６で並行化が導入
された部分に関しては、並行に実行を行う。この場合に
おいて、超逐次プログラムの逐次化情報がペトリネット
で表現されている場合には、ペトリネットのシミュレー
タを用いて、トークン(token) のあるプレースに対応す
るセクションを実行することで、超逐次プログラムのテ
スト実行が実現できる。

【０１０２】（７） ステップＡ６：部分超逐次プログ
ラムに対する良い非決定性の導入・拡大 ステップＡ５でテスト・デバッグが行われた超逐次プロ
グラムに対して、良い非決定性に関する情報を追加す
る。ステップＡ５〜ステップＡ６を所定の回数繰り返
し、良い非決定性を徐々に拡大していく。更に良い非決
定性を導入する必要があれば、ステップＡ５と同様に非
決定性導入装置１７で並行性を追加し、ステップＡ６に
戻る。必要がなければ、ステップＢ２に進む。

【０１０３】（８） ステップＢ２：自動並行化 設計者による良い非決定性の導入が終わった超逐次プロ
グラムに対して、解析装置１０により抽出された超逐次
プログラムの解析情報１２により、並行可能な部分を自
動抽出し、並行化装置１８で並行化ルールを用いて超逐
次プログラムの並行性を自動拡大する。並行化ルール
は、例えば、以下のようになっている。プログラム情報
から、解析装置１０によってデータ依存関係及び制御依
存関係に基づく先行制約を抽出し、先行制約のないセク
ションに関しては並行化できる。この並行化処理は、予
め定められた並行化ルールを適用することにより行うこ
とができる。並行化ルールの一例としては、図１２に示
すようなペトリネットによる逐次化情報の書換ルールが
ある。データ依存関係及び制御依存関係に関しては、公
知である。

【０１０４】（９） ステップＢ３：並行プログラムの
作成 並行化装置１８において、自動的に並行性を拡大した超
逐次プログラムに対して、超逐次プログラムのプログラ
ム情報をソースコードに反映させた並行プログラム１５
を生成する。

【０１０５】通常、逐次プログラムに比べて、並行プロ
グラムのテスト・デバッグは非常に困難な作業である。
これは、並行性によるプログラムの非決定により、ある
タイミングによっては、プログラムが設計者の意図しな
い挙動を示すからである。並行プログラムのテスト・デ
バッグでは、設計者の意図しない並行性（悪い非決定
性）によるバグを１つ１つテストで発見して取り除いて
いる。しかし、この方法では、バグを完全に取り除くの
は非常に困難であり、更に労力を要する。

【０１０６】本発明の超逐次プログラミングでは、並行
プログラムをまず逐次化し、それに対して設計者が意図
する並行性を徐々に導入し、最終的に自動的に並行化で
きる部分を並行化し、並行プログラムを復元する。

【０１０７】すなわち、本発明の超逐次プログラミング
は、並行プログラムから悪い非決定性を除くのではな
く、逐次プログラムに良い非決定性を導入する。このよ
うに、超逐次プログラミングでは、逐次プログラムから
ボトムアップ的に並行プログラムを作成するので、予期
せぬタイミングで発生するバグが入る余地がなく、非常
に信頼性の高いプログラムを作成することができる。ま
た、テスト・デバッグがはるかに容易になる。逐次プロ
グラミングでは、逐次化による性能劣化等が懸念される
が、スーパーコンピュータ等の分野におけるＦＯＲＴＲ
ＡＮ等の逐次プログラムの自動並行化技術が利用できる
ので、多くの場合では実用上問題がない。実施例２の基
本的な構成及び動作を説明したが、以下に、実施例２の
具体例を示す。 （ａ） 第１具体例 図１３は、並行プログラムの例を示す。ここで、Ｐ１と
Ｐ２は並行に動くプロセスである。また、Ｐ１とＰ２
は、共有メモリＭをアクセスしている。

【０１０８】（１） ステップＡ１：モデル化 並行プログラムＰを図１４のように記述する。

【０１０９】（２） ステップＢ１：セクションの設定 この場合は、各命令が１つのセクションを形成すると考
える。簡単のため、セクションＩＤを命令そのものとす
る。

【０１１０】（３） ステップＡ２：逐次化 プロセス優先度を導入することによる逐次化を行う。具
体的には、Ｐ１＞＞Ｐ２（Ｐ１はＰ２より優先する）と
する。この時、逐次化されたセクションの実行順序は、
以下のようになる。 ｉｎｉｔ１→ｒｅａｄ１→ｗｒｉｔｅ１→ｒｅａｄ２→
ｗｒｉｔｅ２ 逐次化により生成された超逐次プログラムは、それぞれ
図１５に示すように、セクション情報、プログラム構造
情報、超逐次化情報から構成される。ここで、逐次化情
報は、上記の実行順序をペトリネットで表現したもので
ある。

【０１１１】（４） ステップＡ３：超逐次プログラム
に対するテスト・デバッグ 超逐次プログラムを実行し、バグがあればセクションの
各セクションのソースコード、或いは、オリジナルの並
行プログラムを修正する。ここでは、バグはなかったと
する。

【０１１２】（５） ステップＡ４：超逐次プログラム
に対する良い非決定性の導入 逐次化情報のペトリネットを表示装置で表示し、逐次関
係を切断することにより、並行化を行う。ここでは、ｗ
ｒｉｔｅ１とｒｅａｄ２の逐次関係を切断することにす
る（図１６（ａ））。ｗｒｉｔｅ１とｒｅａｄ２はプロ
グラム構造情報での実行順序関係はないので、切断可能
である。ここで、どの逐次関係を切断すべきかに関する
ガイダンス情報を後述する解析情報２０に基づき提供す
ることもできる。

【０１１３】（６） ステップＡ５：テスト・デバッグ 並行性の導入された超逐次プログラムをテスト実行す
る。ここでは、 ｉｎｉｔ１→ｒｅａｄ１→ｗｒｉｔｅ１→ｒｅａｄ２→
ｗｒｉｔｅ２ ｉｎｉｔ１→ｒｅａｄ１→ｒｅａｄ２→ｗｒｉｔｅ１→
ｗｒｉｔｅ２ のような実行が可能である。実行の結果、バグがあれば
修正する。ここでは、バグはなかったとする。

【０１１４】（７） ステップＢ２：自動並行化 超逐次プログラムの逐次化情報とプログラム情報のデー
タ依存関係から、解析情報２０により、セクション間の
先行制約が得られる。この先行制約が解析情報２０であ
る。先行制約とは、データ依存関係にあるセクション間
の実行順序の制約である。すなわち、データ依存関係に
あるセクション間は、実行順序によって計算結果が変わ
り得るので、逐次化情報で定められた順序を保持する必
要がある。ここでの先行制約は以下の３つである。 ｉｎｉｔ１→ｒｅａｄ２ ｉｎｉｔ１→ｗｒｉｔｅ２ ｒｅａｄ１→ｗｒｉｔｅ２ 例えば、Ｐ１がｒｅａｄ１で読み込む値は、Ｐ２のｗｒ
ｉｔｅ２がｒｅａｄ１の前で起こるか後で起こるかによ
って影響を受ける。逐次情報では、ｒｅａｄ１→ｗｒｉ
ｔｅ２であるので、これが先行制約となる。以上の先行
制約がないセクションに関しては、並行化が可能であ
り、並行化ルールにより自動並行化できる。ここでは、
ｒｅａｄ１とｒｅａｄ２には先行制約がないため、並行
化ルール１（図１２）を適用できた（図１６（ｂ））。

【０１１５】（８） ステップＢ３：並行プログラムの
作成 自動並行化を行った逐次プログラミングから、並行プロ
グラムのソースコードを生成する。この例では、図１０
における逐次化情報１と逐次化情報２を実現する同期命
令（ｓｅｎｄ、ｗａｉｔ）をソースコードに埋め込む。
その他の逐次化情報は、オリジナルの並行プログラムが
持っている逐次化情報（実行順序）である。変換された
プログラムは図１７のようになる。この並行プログラム
は、図１３のような構造の並列計算機上で実行される。 （ｂ） 第２具体例 第２具体例では、並行プログラムが同期命令、ループ構
造、条件分岐を持つ場合の超逐次プログラミングの手順
を示す。

【０１１６】（１） ステップＡ１：モデル化及びステ
ップＢ２：セクションの設定は省略し、図１８のような
セクションの実行順序（プログラム構造情報）を持つ並
行プログラムが与えられたとする。ここで、同期命令
（ｓｅｎｄ、ｗａｉｔ）とデータ依存関係（Ｓ１３とＳ
２２）、ループ構造及び条件分岐があることに注目され
たい。

【０１１７】（２） ステップＡ２：逐次化 プロセスに優先度（Ｐ１がＰ２より優先度が高い；すな
わち、Ｐ１＞＞Ｐ２）を導入することによる逐次化を行
う。逐次化の結果は図１９のようになる。すなわち、超
逐次プログラムは、それぞれ図１８及び図１９のプログ
ラム構造情報と逐次化情報を持つ（セクション情報は省
略）。ここで、同期命令によって実行されるプロセスが
切り替わっていることに注目されたい。例えば、ｗａｉ
ｔ命令によって、Ｐ１のＳ１２の実行の後にＰ２のＳ２
１が実行されている。また、ループ及び分岐構造もペト
リネットで表現されている。

【０１１８】（３） ステップＡ３：超逐次プログラム
に対するテスト・デバッグ 超逐次プログラムを実行し、バグがあればセクションの
各セクションのソースコード、或いは、オリジナルの並
行プログラムを修正する。ここでは、バグはなかったと
する。

【０１１９】（４） ステップＡ４：超逐次プログラム
に対する良い非決定性の導入 逐次化情報のペトリネットを表示装置で表示し、逐次関
係を切断することにより、並行化を行う。この例では、
明示的には、良い非決定性を入れなかったとする。

【０１２０】（５） ステップＢ２：自動並行化 超逐次プログラムの逐次化情報とプログラム情報のデー
タ依存関係から、セクション間の先行制約が得られる。
ここでは、先行制約としては、Ｓ２２→Ｓ１３だけであ
る。ここで、ループにおいては、先行関係にもループが
生じることがある。ここでは、１回のループにおける先
行関係のみに注目する。先行制約がないセクションに関
しては、並行化が可能であり、並行化ルールにより自動
並行化できる。この例では、先行関係はＳ２２→Ｓ１３
だけであり、図１２の並行化ルール１と並行化ルール２
により、最終的に図２０が生成できる。

【０１２１】（６） ステップＢ３：並行プログラムの
変換 第１具体例と同様に、残った逐次化情報に関して同期命
令を埋め込むことによって並行プログラムが生成でき
る。

【０１２２】（実施例３）図２１は実施例３に係る並行
プログラム作成支援装置の概略構成を示す図であり、図
２２は、本実施例に係る並行プログラム作成方法の概略
手順を示すフローチャートである。

【０１２３】本実施例では、テスト実行装置４０１とテ
ストケース記憶部４０２によって逐次化装置１２が構成
される。この逐次化装置１２では、今までの実施例と異
なり特別に逐次化ルールはなく、逐次化はランダムに行
われる。すなわち、ランダムに実行したときのログを超
逐次プログラムとみなす。以下、本実施例を具体的に説
明する。

【０１２４】本実施例における並行プログラムの作成
は、以下のような手順によって実現される。ここで、第
１並行プログラムとして全く独立に動く２つのプロセス
Ｐ１とＰ２から構成される簡単な並行プログラムを考え
る。

【０１２５】（１） ステップＡ１：モデル化 対象の並行システムに対し、並行性を用いた自然なモデ
ル化を行う。また、各プロセス構造を決定する。更に、
該プロセス内を並行プログラム等を用いたプログラミン
グにより、並行構造を有する並行プログラムをソースプ
ログラムとして記述する。このソースプログラムには、
バグが潜在的に存在する可能性がある。ここでは、２つ
のプロセスＰ１とＰ２を図２３に示すようにプログラミ
ングする。

【０１２６】（２） ステップＣ１：テスト テスト実行装置４０１により、テストケース記憶部４０
２からテストケースを引き出し、ＣＰファイル記憶部１
１からの第１並行プログラムを実行し、実行結果を出力
装置５に表示してランダムにテストを行う。ここでは、
実行ログが、 ｌｏｇ１＝ｊｏｂ１１→ｊｏｂ１２→ｊｏｂ２１→ｊｏ
ｂ２２ であったとする。

【０１２７】（３） ステップＣ２：バグ判定 ステップＣ１のテストの結果、バグがなければステップ
Ｃ４に進み、バグがあれば、その実行ログを実行ログ記
憶部４０３に保存してステップＣ３に進む。ここで、も
しバグがあればステップＣ３に進むが、ここではバグが
なかったとしてステップＣ４に進む。

【０１２８】（４） ステップＣ３：テスト・デバッグ デバッグ装置１６により、実行ログ記憶部４０３に保存
された実行ログに基づくバグの発見を出力装置５を用い
て行い、ＣＰファイル記憶部１１に格納されている第１
並行プログラムを修正してバグを除去する。テスト・デ
バッグが完了したら、ステップＣ１に戻る。

【０１２９】（５） ステップＣ４：実行ログの蓄積 ステップＣ１のテストの結果、ステップＣ２でバグがな
いと判定されれば、実行ログｌｏｇ１を実行ログデータ
ベース４０４に蓄積する。実行ログは、超逐次的な実行
系列であり、超逐次プログラムの特殊な形態とみなすこ
とができる。

【０１３０】（６） ステップＣ５：残テストケースの
有無判定 テストケース記憶部４０２にテストケースが残っている
かどうかを判定し、残っていればステップＣ１に戻って
テストを続行し、テストケースが残っていなければステ
ップＡ７に進む。本ステップでは、別のテストケースも
試みるためにステップＣ１に戻ってテストを続行する。
この２回目のテストで、次に示す実行ログｌｏｇ２が実
行ログデータベース４０４に保存されたとする。 ｌｏｇ２＝ｊｏｂ１１→ｊｏｂ２１→ｊｏｂ１２→ｊｏ
ｂ２２ （７） ステップＡ７：並行プログラムの生成 ＣＰファイル記憶部１１に格納されている第１並行プロ
グラムと実行ログデータベース４０４に格納されている
実行ログから、テストで通過したパスだけしか実行しな
いような並行プログラムを並行化装置１８により生成
し、第２ＣＰファイル記憶部１９に格納する。

【０１３１】本ステップでは、実行ログデータベース４
０４に保存された２つの実行ログｌｏｇ１、ｌｏｇ２だ
けを実行するような並行プログラムを以下の手順で生成
する。 （Ａ）全ての実行ログをマージしてグローバル状態遷移
システムＧＴＳ(Global Transition System)を生成する
（図２４（ａ））。 （Ｂ）ＧＴＳを２つのプロセスＰ１、Ｐ２に射影する。
この時、相手のプロセスの挙動を認識し、同期を取るた
めの同期命令（ｊｏｂ１１−ｏｋ、ｊｏｂ２１−ｏｋ、
ｊｏｂ１２−ｏｋ、ｊｏｂ２２−ｏｋ）が埋め込まれ
る。生成されたプログラムをＰ１′、Ｐ２′とする（図
２４（ｂ））。 （Ｃ）Ｐ１′、Ｐ２′の同期命令には冗長性があるた
め、この冗長性を除去する。この冗長性を除去した後の
最終的なプロセスをＰ１″、Ｐ２″とする（図２４
（ｃ））。

【０１３２】上記の手順により、２つのプロセスＰ
１″、Ｐ２″から構成される並行プログラムＣＰ″が生
成できる。この並行プログラムＣＰ″では、テストで正
しく動くことを確認した実行ｌｏｇ１、ｌｏｇ２は可能
だが、テストしてないケース、例えば ｌｏｇ３＝ｊｏｂ２１→ｊｏｂ１１→ｊｏｂ１２→ｊｏ
ｂ２２ は実行されることはない。

【０１３３】上記のように、テストしてないケースは実
行されることはないので、非常に安全なプログラムであ
るといえる。

【０１３４】実施例３によれば、逐次プログラミングと
同程度の困難さで並行プログラムのプログラミングがで
き、ユーザはテストを効率的にできるばかりではなく、
テストしない部分は動かないので、非常に高い信頼性が
達成できる副次的効果も期待できる。

【０１３５】（実施例４）図２５は、実施例４における
並行プログラム作成方法の概略手順を示すフローチャー
トである。

【０１３６】（１） ステップＡ１：モデル化 （２） ステップＡ２：逐次化 （３） ステップＡ３：超逐次プログラムのテスト・デ
バッグ 以上のステップＡ１〜Ａ３は、図３に示したステップＡ
１〜Ａ３と全く同様であるため、説明を省略する。

【０１３７】（４） ステップＡ４：超逐次プログラム
に対する良い非決定性部分の導入 ステップＡ３でテスト・デバッグが行われた超逐次プロ
グラムに対して、ユーザが非決定性導入装置１７によ
り、非決定的に動作する部分（これを「良い非決定性部
分」という）を指定する。非決定性導入装置１７により
指定された良い非決定性部分は、超逐次プログラムに良
い非決定性に関する情報（並行性に関する情報）として
反映される。これにより超逐次プログラムは、良い非決
定性部分を持つ部分超逐次プログラムとなる。良い非決
定性部分の指定方法は後述する。

【０１３８】（５） ステップＡ５：部分超逐次プログ
ラムのテスト・デバッグ ステップＡ４で得られた部分超逐次プログラムに対し
て、テスト・デバッグを行う。すなわち、ステップＡ４
で良い非決定性部分が導入された部分超逐次プログラム
をテスト・デバッグする。ここでは、部分超逐次プログ
ラムを実行形式に変換して実行する際に、ステップＡ４
において導入された良い非決定性部分のみが並行構造の
実行形式に、導入されなかった部分は元の逐次構造のま
ま実行形式に変換され、実行される。そして、この実行
結果に基づいて、超逐次プログラムに対してテスト・デ
バッグする。変換された実行形式のプログラムが正しく
動作しない場合は、変換前の逐次プログラムにおいて導
入した良い非決定性部分は本来、非決定的に動作させる
べき部分ではないとみなして、並行化の解除を行う。 （６） ステップＡ６：超逐次プログラムにおける良い
非決定性部分の拡大 ステップＡ５でテスト・デバッグが行われた部分超逐次
プログラムに対して、良い非決定性に関する情報を追加
する。ステップＡ４〜ステップＡ６を所定の回数繰り返
し、良い非決定性部分を徐々に拡大していく。

【０１３９】（７） ステップＡ７：並行化コンパイル メタレベルのデフォルト逐次性で管理されている部分超
逐次プログラムのデフォルト逐次性を解除する（例え
ば、ソースプログラム自体に逐次情報及び並行情報を直
接埋め込む）。また、この時、部分超逐次プログラムの
うちの良い非決定性に関する情報が導入されなかった部
分について、可能な限り、無害な非決定性部分を抽出
し、その部分を並行化することを試みて、部分超逐次プ
ログラムの並行性を高める。例えば、良い非決定性に関
する情報が導入されなかった部分について各プロセス間
の依存関係を解析し、依存関係がないと解析された部分
に対応するソースプログラムの部分の逐次性を解除す
る。なお、無害な非決定性部分の抽出は、ステップＡ２
で逐次化する際に解析された並行情報を参照することに
より行われる。

【０１４０】次に、本実施例に係る並行プログラム作成
方法及び作成支援装置の詳細について説明する。

【０１４１】本実施例は、出力装置５上に表示された超
逐次グラフを用いることにより、非決定性部分の導入
を、視覚的に行うことができるようにしたことを特徴と
する。超逐次グラフとは、並行構造を有する並行プログ
ラムに対してデフォルト逐次性を導入した超逐次プログ
ラムのプロセス処理順序を表した遷移グラフをいうもの
とする。この超逐次グラフの表示は、逐次化情報に基づ
いて行われる。逐次化情報は、逐次化装置１２により並
行プログラムが超逐次プログラムに変換される際に生成
される。

【０１４２】より具体的には、逐次化情報とは、所定の
フィールドを有するプロセステーブルと呼ばれるデータ
列群である。図２６は、プロセステーブルの構造を示す
図である。

【０１４３】図２６において、名前フィールドＦ１は、
個々のプロセスを識別するための名前を保持する。ポイ
ンタフィールドＦ２は、当該プロセスから呼び出される
プロセス（以下「被呼出プロセス」という）の名前リス
トを格納する被呼出プロセスリストテーブル（図示しな
い）のポインタを保持する。この被呼出プロセスリスト
テーブルは、別に設けられている。優先順位フィールド
Ｆ３は、プロセスの優先順位を保持する。このプロセス
の優先順位は、もとの並行構造を有するプログラムに基
づき、ある処理時点において複数のプロセスが実行可能
な場合に、逐次化装置１２によって決定され、その結果
が当該フィールドに記述される。優先順位バッファフィ
ールドＦ３は、後述するように非決定性導入装置１７に
より、その値が変更される。このため、優先順位バッフ
ァフィールドＦ４は、変更前の優先順位を保持すること
により、変更前の状態に戻すことを可能とする。グルー
プ化情報フィールドＦ５は、特定のノード群がグループ
化された場合に、各グループ間を識別する情報を保持
し、グループ化されたノード群に対応するプロセス群の
うち、最初に実行されるプロセスの名前が書き込まれ
る。

【０１４４】本実施例における逐次化装置１２について
説明する。

【０１４５】図２７に示すような並行プログラムが逐次
化装置１２に読み込まれたとする。逐次化装置１２は、
まず並行プログラムの並行構造を解析する。図２７に示
す並行プログラムは、概念的には図２８のような並行構
造を有するものであると解析される。この解析は、例え
ば、木構造探索アルゴリズム等を用いることにより実現
できる。そして、逐次化装置１２はその解析結果をプロ
セステーブルに書込む。具体的には、逐次化装置１２
は、図２６に示したプロセステーブルの優先順位フィー
ルドＦ３に優先順位を書込むことによってデフォルト逐
次性を導入し、超逐次プログラムに変換する。すなわ
ち、図２８において、プロセスＢの処理の後、プロセス
ＣとプロセスＤとのいずれが処理されるかは、その時点
におけるシステム環境等により異なる。このような場合
に、逐次化装置１２は、所定の規則（逐次化ルール）に
より優先順位を一意に決定する。なお、所定の規則と
は、例えば、プロセスの読み込み順に従うとする規則や
乱数により決定するという規則等があげられるが、種々
の事情に応じてユーザが設定することができるものとす
る。なお、本実施例における超逐次プログラムは、概念
的には、ソースプログラムとそれをメタレベルで管理す
る逐次化情報とにより構成されることになる。

【０１４６】例えば、上記の例において、所定の規則に
よりプロセスＣの方がプロセスＤよりも優先的に処理す
るものと決定されると、プロセステーブルにおけるプロ
セスＣの優先順位フィールドＦ３には「１」が書き込ま
れ、プロセステーブルにおけるプロセスＤの優先順位フ
ィールドＦ３には「２」が書き込まれる。なお、優先順
位を決定する必要がないプロセスについては、優先順位
フィールドＦ３は「０」のままである。この優先順位の
決定は、階層レベルが等しいプロセス間で行われる。例
えば、図２８におけるプロセスＣ、Ｇ、Ｉとプロセス
Ｄ、Ｈ、Ｊとは、同じレベルのプロセスであるが、その
中のプロセスＥとプロセスＦとは一階層下のレベルであ
るとされる。

【０１４７】このようにして逐次化装置１２は、並行プ
ログラムの並行構造を解析して逐次化情報（プロセステ
ーブル）を生成し、これをファイルに記録する。

【０１４８】図２９は、逐次化装置１２によって並行プ
ログラムの構造を解析した結果作成されたプロセステー
ブルの内容を示す図である。すなわち、図２９はプロセ
スＡからプロセスＫまでに対応する各レコードにおける
各フィールドの内容を示す。より具体的には、プロセス
Ａの次に呼び出されるプロセスはプロセスＢであり、プ
ロセスＡの優先順位は０であることを示す。また、例え
ば、プロセスＢでは次に呼び出されるプロセスとしてプ
ロセスＣ又はプロセスＤであることを示しており、プロ
セスＣとプロセスＤとは本来非決定的であるということ
を意味している。そして、このプロセスＣとプロセスＤ
とは逐次化装置１２によりそれぞれ優先順位「１」と
「２」とが割り当てられ、プロセスＣがプロセスＤより
も優先的に呼び出される（実行される）ことを意味して
いる。

【０１４９】良い非決定性に関する情報の導入（つま
り、良い非決定性部分の指定方法）について説明する。
良い非決定性部分の導入は、図２に示した非決定性導入
装置１７を用いたユーザによる対話的操作により行われ
る。すなわち、この非決定性装置１７は、出力装置５上
に超逐次グラフを表示し、ユーザは、この超逐次グラフ
に対して入力装置４を用いて、良い非決定性部分の導入
・解除を行う。

【０１５０】図３０は、超逐次グラフの一例を示す図で
ある。図３０において、各ノードは各プロセスを表し、
破線矢印で示されたアークはもとの並行プログラムの並
行構造を表している。また、実線矢印は逐次化装置１２
によりデフォルト逐次性が導入されることにより決定さ
れたプロセスの逐次構造を表し、その逐次構造に従って
プロセスの実行順序が連番で付されている。つまり、も
との並行プログラムにおいては、プロセスＣ→Ｇ→Ｉと
プロセスＤ→Ｅ→Ｆ→Ｈ→Ｊとは、本来並行処理される
ように記述されていることを表しているが、超逐次プロ
グラムにおいてはプロセスＣ→Ｇ→Ｉを一連に処理した
後、プロセスＤ以降を処理することを表している。

【０１５１】ユーザは、このような超逐次グラフを出力
装置５により視覚的に把握することができる。更に、ユ
ーザは、並行プログラムが逐次化装置１２により逐次化
され、逐次化情報が生成された後は、超逐次グラフを表
示する旨の指示を与えることにより、いつでも出力装置
５により視覚的に把握することができる。本実施例で
は、超逐次グラフの表示は、非決定性導入装置１７の超
逐次グラフ表示制御部によって行われる。この超逐次グ
ラフ表示制御部は、ユーザにより超逐次グラフを表示す
る旨の指示を受けると、所定の内蔵プログラムに従って
超逐次グラフの表示を開始する。

【０１５２】図３１は、超逐次グラフ表示制御部の構成
を示す機能ブロック図である。 超逐次グラフ表示制御
部は、逐次化情報記憶部３１に格納されている逐次化情
報に従って、各プロセスに対応するノードと、ノード間
の呼び出し関係を示す並行構造及び逐次構造に対するア
ークを決定し、これらを画像データ生成部３５により出
力装置５上に表示するために必要な画像データに変換す
る。

【０１５３】逐次化情報読込部３２は、逐次化情報記憶
部３１から逐次化情報を読み込み、並行構造解析部３３
及び逐次構造解析部３４に送出する。

【０１５４】並行構造解析部３３及び逐次構造解析部３
４は、逐次化情報を参照して並行構造を解析する。具体
的には、並行構造解析部３３は、ポインタフィールドＦ
２に指示された被呼出プロセスリストテーブルを参照す
ることにより、名前フィールドＦ１に記述されたプロセ
スによって呼出され得るプロセス名の間の呼出関係を特
定する。逐次構造解析部３４は、これらのフィールドに
加え、更に優先順位フィールドＦ３に記述された優先順
位を参照して逐次構造を特定する。これら並行構造解析
部３３及び逐次構造解析部３４による解析結果は、画像
データ生成部３５に送出される。画像データ生成部３５
は、入力されたこれらの解析結果に基づいて、各プロセ
スに対応するノードを表示するための画像データと、該
プロセス間の呼出関係を接続するための２つのアーク
（つまり、並行構造に対するアーク及び逐次構造に対応
するアーク）を表示するための画像データを生成し、出
力装置５に送出する。出力装置５は、これらの画像デー
タに基づいて遷移グラフ（即ち、超逐次グラフ）を表示
する。

【０１５５】なお、上記超逐次グラフの表示に際し、並
行構造解析部３３により解析された並行構造の各ノード
間の接続関係に、従属的に逐次構造解析部３４により解
析された逐次構造の各ノード間の接続関係を付加するこ
とにより画像データを生成することが望ましい。換言す
れば、超逐次グラフは、もとの並行プログラムの並行構
造を保持した超逐次グラフであることが望ましい。これ
により、ユーザは、もとの並行プログラムが本来持つ並
行構造を意識しつつ、逐次化された処理の流れ（プロセ
ス）に対して、良い非決定性部分を導入することができ
る。

【０１５６】出力装置５に超逐次グラフが表示される
と、図２の非決定性導入装置１７はユーザによる良い非
決定性部分の入力待ちの状態になる。（部分）超逐次プ
ログラムのテスト・デバッグ開始当初は、非決定性部分
が導入されていないので、逐次構造に対するアークは出
力装置５上の全てのノードに対して設けられており、並
行化情報は表示されていない。ここで、並行化情報と
は、良い非決定性部分が導入されたノードに対して与え
られる情報であり、良い非決定性部分が導入されたか否
かにより画面上で視覚的に区別されて（例えば陰影の濃
度、色分け等）表示される。また、この並行化情報は、
階層化された良い非決定性部分についても視覚的に区別
されて表示される。

【０１５７】ユーザによる良い非決定性部分の導入は、
入力装置４を用いて行われる。具体的な良い非決定性の
導入方法については後述するが、略説すれば、入力装置
４を用いてノード間の逐次構造の接続関係（アーク）を
断ち切ったり、接続したりすることにより行われ、その
結果は、逐次化情報変更部３６により逐次化情報記憶部
３１の内容が変更される。変更された内容は、再び逐次
化情報読込み部により読み込まれ、出力装置５上に表示
されることになる。

【０１５８】良い非決定性部分の導入の具体的操作例に
ついて説明する。

【０１５９】図３２は、良い非決定性部分の導入方法を
説明するための図である。

【０１６０】複数のプロセス間に対して良い非決定性を
導入する場合、良い非決定性の導入モードにおいて、該
プロセスに対応する所望のノードを続けて指定すること
により行われる。良い非決定性の導入モードは、例え
ば、指示操作メニュー等により選択され、該モードに移
行する。

【０１６１】図３２において、プロセスＥとＦとの並行
化を許容する場合、入力装置４により操作されるカーソ
ルＰでノードＥ、Ｆを続けて指定する。この指定された
ノードは、指定されていない他のノードと視覚的に区別
できるように、陰影が付される。対象とするノード全て
について指定が完了した場合、ユーザは完了した旨を非
決定性導入装置１７に与える。これにより、逐次化情報
変更部３６は、逐次化情報記憶部３１内のプロセステー
ブルにおける対応するプロセスの優先順位フィールドＦ
３の現在の値を優先順位バッファフィールドＦ４に対比
させるとともに、優先順位フィールドＦ３の値を「０」
に変更する。

【０１６２】つまり、本実施例では、プロセスＥ及びＦ
の優先順位フィールドＦ３の値「１」及び「２」がそれ
ぞれ優先順位バッファフィールドＦ４に対比されるとと
もに、それぞれの優先順位フィールドＦ３の値は「０」
に変更される。逐次化情報変更部３６による逐次化情報
記憶部３１の更新後、再度、出力装置５上に超逐次グラ
フが表示される。この時、プロセスＥとＦとの間の優先
順位はないため、それに対応する逐次構造のアークは表
示されない。つまり、出力装置５上では、プロセスＥと
Ｆとは、並行に動作することが確認される。

【０１６３】図３３は、上記の場合において、良い非決
定部分が導入された超逐次グラフの一例を示す図であ
る。

【０１６４】上記のようにして良い非決定性部分が導入
されたプログラム（部分超逐次プログラム）は、テスト
実行装置１５により実行形式に変換され、テスト実行さ
れる。ユーザは、テスト実行装置１５による実行結果に
基づいて、プログラムが正しく動作するか否かを確認す
る。この動作確認は、並行性に基づく全てのパスについ
て実行する必要がある。テスト実行装置１５が正しく動
作しなかった場合、良い非決定性部分を導入した部分
は、本来並行化を許容する部分ではないとみなすことが
できるため、ユーザは並行化を解除する指定をする。

【０１６５】並行化の解除は、非決定性部分解除モード
において、良い非決定性部分を導入する場合と同様に指
定することにより行われる。これにより、逐次化情報変
更部３６は、逐次化情報記憶部３１内のプロセステーブ
ルにおける優先順位バッファフィールドＦ４に格納され
ている値を優先順位フィールドＦ３に戻す。

【０１６６】本実施例では、良い非決定性部分の導入に
際し、階層レベルごとにグループ化することも可能であ
る。例えば、プロセスＣ、Ｇ、Ｉのグループ（グループ
１という）とプロセスＤ、Ｈ、Ｊのグループ（グループ
２という）とは同一の階層レベルであるので、これらは
互いに並行動作しうる。従って、個々のプロセスについ
て操作したのでは操作性に欠けるため、これらをグルー
プ化することが有効である。このグループ化は、グルー
プ化モードを選択することにより行われる。具体的に
は、グループ化モードにおいて、対象とするノードを順
次選択し、完了した旨を与えることにより、対象となる
ノードがグループ化されて１つの新たなノードとして表
示される。

【０１６７】図３４は、グループ化されたノードを持つ
超逐次グラフの一例を示す図である。

【０１６８】図３４において、グループ１及び２のノー
ドは、グループ化されていない他のノードと視覚的に区
別できるように、例えば、楕円形で表示されている。更
に、グループ２は、更に下位階層（プロセスＥ及びＦ）
を持っているため、例えば、影付きで表示される。この
ような超逐次グラフに対し、ユーザは、良い非決定性部
分を指定することができる。なお、このようなグループ
化された超逐次グラフに対して良い非決定性部分を導入
した場合であっても、先頭のプロセス（プロセスＣ及び
Ｄ）の優先順位フィールドＦ３を変更するだけでよい。

【０１６９】超逐次グラフのノードに対して良い非決定
性部分を導入する場合には、上述したように所望のノー
ドを入力装置４により直接指定することにより行われる
が、このような方法ではなく、特定のノード群を囲い込
むことによって、又は指定領域が特定のノード群に掛か
ることによって指定されたとするようにしてもよい。な
お、プロセスが多数ありそれに対応するノードが多数あ
るため、出力装置５上で確認することが困難な場合も想
定できる。このような場合は、グループ化されたノード
群のみを表示することにより対処することができる。

【０１７０】本実施例では更に、逐次化装置１２により
決定されたプロセス間の優先順位を変更することもでき
る。つまり、優先順位変更モードにおいて、所望のノー
ドを指定することにより、対象とされたノード間の優先
順位を変更する。

【０１７１】図３２の超逐次グラフに対し、優先順位変
更モードにおいて、プロセスＥとＦとの優先順位を変更
するとする。ユーザは、上記のように入力装置４によ
り、ノードＥ及びＦとを指定し、指定完了の旨を非決定
性導入装置１７に与える。これにより、逐次化情報変更
部３６は、逐次化情報記憶部３１内のプロセステーブル
におけるプロセスＥの優先順位フィールドＦ３の値を
「２」、プロセスＦの優先順位フィールドＦ３の値を
「１」と変更する。これにより、出力装置５上には、新
たな超逐次グラフが表示されることとなる。図３５は、
この時の超逐次グラフの一例を示す図である。図３５に
示すように、優先順位変更後は、逐次構造に対するアー
クが変更されることになる。

【０１７２】このようなプロセスの優先順位の変更は、
ユーザの意図したプロセス間の動作が保証されるため、
良い非決定性部分の導入に有効に役立てることができ
る。すなわち、まず、ユーザは図３２の超逐次プログラ
ムについてテスト実行装置１５で実行形式に変換し、テ
スト実行を行う。次に、ユーザは、優先順位変更後の図
３５の超逐次グラフについて同様にテスト実行を行う。
これにより、両方のテスト実行結果がユーザの意図した
ものであることが確認できれば、プロセスＥとプロセス
Ｆは、どちらを先に実行しても良いとみなせるので、良
い非決定性部分の導入を行うことができる。

【０１７３】なお、本実施例では、２プロセス間の非決
定性の導入について説明したが、３プロセス以上の場合
も同様である。

【０１７４】図３６は、３プロセス間の良い非決定性部
分の導入を説明するための図である。並行構造のプロセ
スＢ、Ｃ、Ｄ間において、その全てについて並行化を許
容するようにすることもできるが、図３６においては、
プロセスＢとＣとの間のみ並行化を許容されている場合
を示す。このような良い非決定性部分の導入により、超
逐次グラフは図３７のようになる。つまり、図３７に示
す超逐次グラフは、プロセスＢ及びＣの両方が実行され
た後に、プロセスＤが実行されることを示す。上記のよ
うに本実施例によれば、出力装置５上に表示した超逐次
グラフによって並行化情報及び逐次化情報をユーザに対
して同時に提示するので、ユーザはもとの並行構造を考
慮しつつ、良い非決定性部分の指定をすることができる
ようになる。また、並行プログラム記述レベルにおける
良い非決定性部分の指定・解除ではなく、超逐次グラフ
に対して良い非決定性部分を指定・解除をするので、高
度な並行プログラミング技術を必要とすることなく、容
易に並行プログラムの開発をすることができるようにな
る。

【０１７５】（実施例５）図３８は、本実施例に係る並
行プログラム生成作成支援装置のブロック図であり、特
に図２におけるＨＳＰファイル記憶部１４と非決定性導
入装置１７について詳しく示す。

【０１７６】図３８において、ＣＰファイル記憶部１１
に格納されている第１並行プログラムは、逐次化装置１
２により先の実施例のように逐次化され、得られた超逐
次プログラムはＨＳＰファイル記憶部１４内の逐次化プ
ロセスリスト記憶部５１に格納される。なお、超逐次プ
ログラムは、図３８には図示してないデバッグ装置によ
り、逐次化プロセスリスト記憶部５１に格納される時に
は既に逐次化された状態でのバグが取り去られている。

【０１７７】ここで生成された超逐次プログラム（逐次
化プロセス）は、フィールドデータ生成部５３によりフ
ィールドデータに変換され、フィールドデータ記憶部５
２に保存される。これら逐次化プロセスリスト記憶部５
１とフィールドデータ記憶部５２の情報は、中間ファイ
ルたるＨＳＰファイル記憶部１４に保存される。フィー
ルドデータ記憶部５２からのフィールドデータは、フィ
ールドチューニング部５４を介してフィールドエディタ
５５での編集に供される。

【０１７８】非決定性導入装置１７は、フィールドデー
タ生成部５３、フィールドチューニング部５４及びフィ
ールドエディタ５５で構成される。フィールドエディタ
５５で編集が終了したフィールドデータは、並行化装置
１８（フィールドデータ変換部）で修正された並行プロ
グラムに変換され、第２ＣＰファイル記憶部１９に格納
される。

【０１７９】図３９は、図３８におけるＣＰファイル記
憶部１１に格納されている第１並行プログラムの一例を
示しており、説明の便宜上、意図的にバグを含ませてい
る。ここでは、バグとしてプロセスＰ４とＰ５の並行実
行は誤りであり、逆に、プロセスＰ２とＰ６は並行実行
が可能であるとし、正しい並行プログラムは後述する図
６６であるとする。図４０は図３９の第１並行プログラ
ムで実行されるプロセスの流れをイメージした図であ
り、プロセスＰ４とＰ５、プロセスＰ７とＰ８がそれぞ
れ並行に実行される。図４１は、図３８における逐次化
プロセスリスト記憶部５１に格納されている逐次化プロ
セスの一例であり、逐次化装置１２において図３９の第
１並行プログラムで並行な部分に、ある順番を付けるこ
とで逐次化されている。

【０１８０】また、図４２は図４１で実行されるプロセ
スの流れをイメージした図である。この例では偶然、Ｐ
４、Ｐ５の順で逐次化されているので、この点に関する
バグは取り除かれている。仮に、逐次化がＰ５、Ｐ４の
順で行われていたなら、上記のバグが従来のデバック手
法で検出されるはずであり、逐次化の時点で誤った並行
化（悪い非決定性）を取り除くことができる。

【０１８１】図４３は、図３８におけるフィールドデー
タ生成部５３で実行される処理の流れを示すフローチャ
ートである。ここでは、１つのプロセスからもう１つの
プロセスへ処理が進むことをある制約と遷移条件が存在
する範囲（エリア）ととらえて、超逐次プログラム（逐
次化プロセス）をフィールドデータに変換している。図
４３に示すように、ステップＤ１でスタートエリアを生
成し、最後のプロセスが来るまでステップＤ３〜Ｄ９を
繰り返し実行する。そして、最後のプロセスが来たらス
テップＥ１０〜Ｅ１２の処理を行って終了となる。図４
４は、図４３に示した処理によって生成される一般的な
エリアのデータ構造を示す。このエリアの接続で構成さ
れる全体構造としてフィールドが形成される。

【０１８２】エリアＡ（ｉ）には以下のような情報が記
述されている。 （１） エリアＡ（ｉ）にいる限りは、"constraint"に
記述された制約が存在する。（例えば、Ｐ( ｘ１) はＰ
( ｘ２) より先に実行される） （２） エリアＡ（ｉ）から他のエリアへ移るための遷
移条件は、"transition"に記述されている。（例えば、
Ｐ（ｚ１）が終了してＡ（ｊ）へ遷移できる） （３） エリアＡ（ｉ）から移ることのできるエリア
は、Ａ(j) である。 （４） エリアＡ（ｉ）へ移る以前の状態は、エリアＡ
（ｋ）である。

【０１８３】図４５は、図４３に示した処理により図４
１に記述されたプログラムをエリアの集合で構成された
フィールドに変換した様子を示す。

【０１８４】このフィールドは処理の順序関係の制約が
最も強い。非決定性の導入は、この制約を変更したり、
なくしたりすることで行なうことができる。つまり、フ
ィールドチューニングを行うことで非決定性を導入し、
並行化を図ることができる。なお、一般的には制約によ
るチューニングであるので、ユーザには制約と遷移条件
を表示する。

【０１８５】図４６は、図３８におけるフィールドチュ
ーニング部５４で実行される処理のフローチャートであ
る。

【０１８６】ステップＥ１で選択されたフィールドデー
タは、ステップＥ２においてそのエリア間の連結情報が
解析されて視覚的にフィールドが生成され、フィールド
エディタ５５に表示される。ユーザは、フィールドエデ
ィタ５５の画面を見ながらステップＥ３でコマンドを入
力し、フィールドのチューニングを行うことができる。

【０１８７】ステップＥ５で編集中のフィールド保存で
き、編集終了ならステップＥ１７を経て終了する。な
お、ステップＥ１４〜Ｅ１６にて、編集による制約の矛
盾を検出している。

【０１８８】ステップＥ９は制約の書き換え処理に関す
るサブルーチンである。また、ステップＥ１１は制約の
追加処理に関するサブルーチンである。そして、ステッ
プＥ１３は制約の削除処理に関するサブルーチンであ
る。

【０１８９】図４７は図４６におけるステップＥ９の処
理を行なうサブルーチンである。

【０１９０】ステップＥ９−１で編集された制約に関し
て、ステップＥ９−２で自明な制約の有無を検査し、も
し自明な制約が存在すれば、制約の書き換えにエラーが
あることをユーザにステップＥ９−９で伝え、ステップ
Ｅ９−１０で書き換えを無効にする。もし、自明な制約
が存在しなければ、ステップＥ９−４のようにフィール
ドを書き換える。そして、ステップＥ９−５〜Ｅ９−８
でフィールドチェックする。

【０１９１】図４８は、図４６におけるステップＥ９ー
４の制約の変更操作のアルゴリズムによって起こるフィ
ールドの変化を示した図である。これは"before Pi Pj"
を"before Pl Pj"に変更したときの様子を示しており、
図４８の（ａ）から（ｂ）へとフィールドが変化する。
ここでは、Ａ（ｙ）のエリアがエリアＡ（ａ）の"next"
に接続され、それに伴って各エリアの属性が変化する。

【０１９２】図４９は図４６におけるステップＥ１１の
処理を行なうサブルーチンである。ステップＥ１１−１
で編集された制約に関して、ステップＥ１１−２で自明
な制約の有無を検査し、もし自明な制約が存在すれば、
制約の書き換えにエラーがあることをユーザにステップ
Ｅ１１−９で伝え、ステップＥ１１−１０で追加を無効
にする。もし、自明な制約が存在しなければ、ステップ
Ｅ１１−４のようにフィールドを書き換える。そして、
ステップＥ１１−５〜Ｅ１１−８でフィールドチェック
する。

【０１９３】図５０は図４９におけるステップＥ１１−
４の制約の追加操作のアルゴリズムによっておこるフィ
ールドの変化を示した図である。ここではエリアＡ
（ｙ）に"before Pj Pk"を追加したときの様子を示した
もので、図５０（ａ）から（ｂ）へとフィールドが変化
する。ここでは、Ａ（ｙ）のエリアが新たにエリアＡ
（ｘ２）のnextに追加され、それに伴って各エリアの属
性が変化する。

【０１９４】図５１は図４７におけるステップＥ１３の
処理を行なうサブルーチンである。

【０１９５】エリアには少なくとも１つの制約が必要で
あるので、ステップＥ１３−１で指定したエリアＡ
（ｙ）の制約の個数を調べ、もし１つならステップＥ１
３−８でエラーメッセージを表示して終了する。もし、
複数の制約があれば、ユーザの指定した制約を削除し、
ステップＥ１３−３のようにフィールドを書き換える。
そして、ステップＥ１３−４〜Ｅ１１−７でフィールド
チェックし、自明な制約の発生を防ぐ。

【０１９６】図５２は、図５１におけるステップＥ１３
の制約の削除操作のアルゴリズムによって起こるフィー
ルドの変化を示した図である。

【０１９７】これは"before Pj Pk"を削除したときの様
子を示しており、図５２（ａ）から（ｂ）へとフィール
ドが変化する。ここでは、Ａ（ｘ２）のエリアがエリア
Ａ（ｚ）の"pre" に接続され、それに伴って各エリアの
属性が変化する。

【０１９８】図５３はフィールドに矛盾を発生させる自
明な制約を検出する処理であり、図４７のＥ９−２、Ｅ
９−５、図４９のＥ１１−２、Ｅ１２−５、図５１のＥ
１３−４で共通に実行されるサブルーチンである。ここ
では、例えば"before A B"、"before B C"が存在するに
も関わらず、"before A C"のような自明な制約を検出す
る。

【０１９９】図５３においてＥ９−３〜Ｅ９−２−６の
繰り返しにより、自明制約が生成され、Ｅ９−２−７で
制約集合との間のに共通要素を探すことにより実現され
る。例えば、図５４のような自明制約"before A D"を含
んだフィールドを仮定した場合、この処理によって図５
５のテンポラリ集合（ａ）、テンポラリ集合（ｂ）、テ
ンポラリ集合（ｃ）の順番で処理が実行され、共通要
素"before A D"を検出することができる。

【０２００】図５６は、フィールドエディタ５５の表示
画面を示す。フィールドエディタ５５では、フィールド
の読み込み、保存、制約編集、表示モードの変更等をメ
ニュー７１を指定して行うことができ、四角で表現され
たエリア７２を選択すると、編集画面７３が現れる。図
５７は、表示モードとして「２Ｄ表示モード」を選択し
た場合のフィールドの表示例を示す。このモードでは、
平面的にフィールドが表示される。図５８は、表示モー
ドとして「３Ｄ表示モード」を選択した場合のフィール
ドの表示例を示す。このモードでは、立体的にフィール
ドが表示され、全体が大きくなったり、多くの並行処理
部分がある場合にも、全体を見渡しやすくすることがで
きる。

【０２０１】図５９〜図６６は、図４４に示したフィー
ルドデータが図４６のアルゴリズムでチューニングされ
ていく様子を示す。

【０２０２】図５９では、例えばユーザはＰ５とＰ６に
因果関係がなく、Ｐ６はＰ２の後であれはバグとなる悪
い非決定的な動きはしない判断したとする。この場合、
図５９中に示されるように制約の書き換えるという編集
を行うと、表示は図６０のようになる。図６０では、例
えばＰ６とＰ４に因果関係はなく、Ｐ４はＰ３とのみ正
しい順序が存在すると判断したとする。この場合、図６
０中に示されるようにある制約（"before P6 P4"）を削
除する編集を行うと、表示は図６１のようになる。以下
同様に、ユーザがエリア内の制約を吟味し、徐々に編集
を加えていくと、フィールドデータは図６２→図６３→
…→図６６のように変化する。

【０２０３】図６７は、図３８における並行化装置（フ
ィールドデータ変換部）１８で実行される処理を示すフ
ローチャートである。図６７に示されるように、並行化
装置１８ではフィールドデータ記憶部５２からフィール
ドデータを読み込み（ステップＦ１）、エリア間のグラ
フ構造を解析してプロセスフローを生成し（ステップＦ
２）、更にそのプロセスフローを解析して非決定性のみ
導入された形で並行プログラムのソースを生成し（Ｓス
テップＦ３）、第２ＣＰファイル記憶部１９に保存する
（ステップＦ４）。

【０２０４】図６８は、図６６の状態となったフィール
ドを並行化装置１８で解析して変換して得られた並行プ
ログラムである。図６８に示されるように、図３９の第
１並行プログラムで仮定したバグであるＰ４とＰ５の並
行実行が直され、逆に、良い非決定性であるＰ３とＰ６
の並行化が行われている。

【０２０５】また、図６９は図６８の並行プログラムで
実行されるプロセスの流れをイメージした図である。

【０２０６】本実施例によれば、逐次化された並行プロ
グラムのプロセスの流れを制約と遷移条件からなるフィ
ールド（場）という概念として捉え、このフィールドを
チューニングすることで良い非決定性を導入し、バグの
ない高品質な並行プログラムを効率的に生成することが
できる。また、本実施例では逐次化されたプログラムが
制約を外すことによって並行化が進んでいくと、図形的
に細長いフィールドだったものが縦方向に伸びていくの
で、直観的に理解しやすく、操作が容易となるという利
点がある。

【０２０７】（実施例６）本実施例に係る並行プログラ
ム作成方法及び作成支援装置では、テスト・デバッグ
は、超逐次プログラムに対して行う。また、良い非決定
性に関する情報の導入も、超逐次プログラムに対して行
う。

【０２０８】図７０は、実施例６に係る並行プログラム
作成支援装置の概略構成を示す図である。図７０におい
て、ＣＰファイル記憶部１１に格納された第１並行プロ
グラムは、ユーザによる入力装置４からの指示により引
き出され、逐次化装置１２に入力される。逐次化装置１
２に入力された第１並行プログラムは、逐次化ルール記
憶部１３に格納された逐次化ルールに従って完全超逐次
プログラムＨＳＰに変換され、複数の完全超逐次プログ
ラムを格納可能なＨＳＰファイル記憶部１４に記録され
る。

【０２０９】この完全超逐次プログラムＨＳＰに対し
て、テスト実行装置１５でテストが行われる。ここで、
バグがあればデバッグ装置１６を用いて、ＨＳＰファイ
ル記憶部１４に格納されている完全超逐次プログラムＨ
ＳＰを修正する。テスト・デバッグが完了したならば、
完全超逐次プログラムＨＳＰをＨＳＰファイル記憶部１
４に保存する。

【０２１０】次に、非決定性導入装置１７で変更装置２
５を介して完全超逐次プログラムＨＳＰの実行順序を変
更し、別の完全超逐次プログラムＨＳＰを生成する。こ
の完全超逐次プログラムＨＳＰに対して、同様のテスト
・デバッグを繰り返しながら、完全超逐次プログラムＨ
ＳＰをＨＳＰファイル記憶部１４に蓄積していく。すな
わち、良い非決定性を１つの部分超逐次プログラムとし
て表現する替わりに、複数の完全超逐次プログラムとし
て表現したものである。非決定性導入装置１７による良
い非決定性導入が完了したならば、最終的にＨＳＰファ
イル記憶部１４に蓄積された完全超逐次プログラムＨＳ
Ｐの集合から、並行化装置１８で並行プログラムが生成
され、第２ＣＰファイル記憶部１９に格納される。

【０２１１】（実施例７）本実施例において並行プログ
ラム作成支援装置の構成は、実施例６と同様であり（図
７０）、その並行プログラム作成手順が異なっているの
で、図示は省略する。図７１は、本実施例における並行
プログラム作成方法の概略手順を説明するためのフロー
チャートである。

【０２１２】（１） ステップＡ１：モデル化 対象の並行システムに対し、並行性を用いた自然なモデ
ル化を行う。また、各プロセス構造を決定する。更に、
該プロセス内を並行プログラム等を用いたプログラミン
グにより、並行構造を有する並行プログラムをソースプ
ログラムとして記述する。このソースプログラムには、
バグが潜在的に存在する可能性がある。 （２） ステップＡ２：逐次化 デフォルト逐次性を導入することによって、並行プログ
ラムを逐次構造の超逐次プログラムに変換する。本実施
例では、メタレベルにおいてデフォルト逐次性を導入す
る。ここで、メタレベルとはソースプログラムそのもの
のレベルについていうのではなく、ソースプログラムの
実行を管理するレベルをいう。例えば、並行プログラム
で記述されたソースプログラムを、それとは別に管理さ
れるスケジューラによって逐次的に実行することを保障
したプログラムのソースプログラムに変換する。

【０２１３】（３） ステップＡ３：超逐次プログラム
のテスト・デバッグ ステップＡ２で変換された超逐次プログラムに対して、
テスト・デバッグを行う。すなわち、テスト実行装置に
より逐次プログラムをテスト実行した結果に基づいて、
デバッグ装置により超逐次プログラムからバグを除去す
る。ここでのテスト・デバッグは、逐次プログラムにお
ける通常のテスト・デバッグ方法と同様に行うことがで
きる。超逐次プログラムが正常に動作することが保障さ
れるまで、このテスト・デバッグを行う。

【０２１４】（４） ステップＧ１：並行模擬プログラ
ム化 ステップＡ３でテスト・デバッグが行われた超逐次プロ
グラムに対し、並行化の候補となるプロセス群を導入
し、変更装置２０によって複数の並行模擬動作系列を生
成する。本実施例では、メタレベルにおいて並行模擬動
作系列を導入する。

【０２１５】（５） ステップＧ２：並行模擬動作系列
の実行・確認 ステップＧ１で得られた並行模擬動作系列をステップＡ
３でテスト・デバッグが行われた超逐次プログラムを用
いて実行し、実行結果の確認を行う。この実行は、プロ
グラムが並行に動作する状況を超逐次プログラム上で模
擬的に再現している。ユーザは、各動作結果が正しいか
否かを並行模擬実行装置に記録する。

【０２１６】（６） ステップＧ３：良い非決定性の選
択による部分逐次化 ステップＧ２の実行結果から、正しく実行された並行模
擬動作系列を許容し、かつ実行の正しくない並行模擬動
作系列を排除する非決定性を導入して、良い非決定性と
して登録する。ステップＧ１〜ステップＧ３の処理を所
定の回数繰り返し、良い非決定性の範囲を徐々に拡大し
ていく。

【０２１７】（７） ステップＡ７：並行化コンパイル 良い非決定性の導入された部分超逐次プログラムのう
ち、無害な非決定性部分を抽出し、その部分を並行化す
ることで、部分超逐次プログラム全体を並行プログラム
に変換する。すなわち、並行化に関する情報が導入され
なかった部分に関しては、デフォルト逐次性を並行プロ
グラムに反映させて（例えば、ソースプログラム自体に
埋め込む）、メタレベルのデフォルト逐次性を解除す
る。

【０２１８】図７２は、ユーザが想定していた並行プロ
グラムモデルの例である。ここで、Ｐ１、Ｐ２、Ｐ３等
はプログラムが実行される単位を表しており、これらを
プロセスと呼ぶ。同図の例は、ユーザの意図においてプ
ロセスＰ３、Ｐ４、Ｐ５は並行実行され、プロセスＰ
７、Ｐ８、Ｐ９は逐次実行されることを表している。更
に、プロセスＰ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６からなるプ
ロセス群と、プロセスＰ７、Ｐ８、Ｐ９からなるプロセ
ス群も並行実行可能である。

【０２１９】超逐次プログラムＨＳＰは、逐次化装置１
２により並行モデルにおけるプロセスの前後関係を壊さ
ない範囲で、全てのプロセスを一列に並べて得られる。

【０２２０】図７３は、図７２の並行プログラムから得
られる超逐次プログラムＨＳＰの実行系列をモデル化し
た例である。このように逐次化モデルでは、並行に実行
されるプロセスＰ３、Ｐ４、Ｐ５等は任意の順で、場合
によっては離れた位置に置かれるが、これらより先に実
行されるべきプロセスＰ１、Ｐ２は、プロセスＰ３、Ｐ
４、Ｐ５のいずれよりも前に置かれ、またこれらより後
に実行されるべきプロセスＰ６、Ｐ１０は、プロセスＰ
３、Ｐ４、Ｐ５のいずれよりも後に置かれる。同様に、
プロセスＰ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６からなるプログ
ラム群と、プロセスＰ７、Ｐ８、Ｐ９からなるプログラ
ム群を逐次化した際の群の間の前後関係は任意で、場合
によっては両方の群のプロセスが逐次モデル上に交互に
表れることもある。

【０２２１】超逐次プログラムＨＳＰは、ユーザによる
入力装置４からの指示により、テスト実行装置１５に入
力され、テスト実行が行われる。テスト実行装置１５
は、テスト実行の結果を出力装置に提示する。ユーザ
は、このテスト実行の結果に基づいて超逐次プログラム
ＨＳＰに対し、入力装置４を用いて所定のテスト・デバ
ッグを行うことができる。また、ユーザは超逐次プログ
ラムＨＳＰに対して所定のテスト・デバッグを行った
後、再度入力装置４からテスト実行の指示を与える。こ
れにより、テスト・デバッグの行われた超逐次プログラ
ムＨＳＰは、テスト実行装置１５に入力され、再度テス
ト実行が行われる。このテスト・デバッグは、プログラ
ムＨＳＰが正常に動作することを確認するまで繰り返し
行われる。

【０２２２】テスト・デバッグにより正常に動作するこ
とを確認した時点で、非決定性入力装置１７により超逐
次プログラムを部分逐次プログラムへ変換する。まず、
超逐次プログラムを複数の並行模擬プログラムへ変換
し、並行模擬プログラムの実行結果より、良い非決定性
に関する情報を蓄積する。この手順を図７４に示す。こ
の図７４に示す手順に従い、図７３の逐次モデルを並行
模擬モデルへ変換し、部分逐次モデルを得るまでの過程
の具体例を図７５〜図７８に示す。

【０２２３】以下、この例の手順について説明する。

【０２２４】図７５（ａ）ではポインティングデバイス
等によって、並行模擬範囲としてＰ３、Ｐ４、Ｐ５が選
ばれる（ステップＨ１）。更に、各々のプロセスが単独
で並行化の単位に指定される（ステップＨ２）。図７５
では、並行化単位が色の違いによって区別される。超逐
次プログラムでは、この並行模擬範囲の内部でプロセス
はＰ３、Ｐ４、Ｐ５の順番で実行される。

【０２２５】図７５（ｂ）では、並行化単位の置き換え
としてＰ４、Ｐ５が置き換えられ（ステップＨ３）、一
つの並行模擬動作系列が獲得される。この並行模擬動作
系列では、並行模擬範囲の内部でプロセスはＰ３、Ｐ
５、Ｐ４の順番で実行される。このプログラムを実行し
て実行結果が保証されると（ステップＨ４）、図７５
（ｃ）のようなプログラムが獲得される（ステップＨ
５）。この部分逐次プログラムでは、並行模擬範囲の内
部でプロセスＰ３を実行した後にＰ４とＰ５が並行に実
行される。

【０２２６】更に、同一範囲内での非決定性の拡大がユ
ーザによって指示されると（ステップＨ６）、図７６
（ａ）では単独のプロセスＰ３と２つのプロセスの組Ｐ
４＆Ｐ５が置き換えられ（ステップＨ３）、もう一つの
並行模擬動作系列が獲得される。この並行模擬動作系列
では、並行模擬範囲の内部でプロセスはＰ４とＰ５が並
行に実行された後にＰ３が実行される。このプログラム
を実行して正しさが確認されると（ステップＨ４）、図
７６（ｂ）のような非決定性を持つプログラムが獲得さ
れる（ステップＨ５）。この部分逐次プログラムでは、
並行模擬範囲の内部でプロセスＰ３、Ｐ４、Ｐ５が並行
に実行される。これによって、この並行模擬範囲内での
非決定性は十分となるので、ステップＨ６からステップ
Ｈ７に進み、並行範囲の拡大がユーザによって指示され
ると（ステップＨ７）、図７７〜図７８に示すように、
ステップＨ１に戻って同様の処理を繰り返す。

【０２２７】良い非決定性に関する情報がインクリメン
タルに導入され得られた部分逐次プログラムＰＨＳＰ
は、ユーザからの指示により、並行化装置１８に入力さ
れる。この並行化装置１８では、良い非決定性のみを持
つ部分逐次プログラムＰＨＳＰを並行プログラムＣＰと
して第２ＣＰファイル記憶部１９に記録する。ユーザ
は、このプログラムＣＰを出力装置５によって見ること
ができるとともに、最終的なテスト・デバッグを行うこ
とができる。

【０２２８】本実施例によれば、超逐次プログラム上で
並行プログラムの動作を十分に確認することができる。
また、超逐次プログラムに対して並行化の候補となる範
囲を指定することで、超逐次プログラムを段階的に並行
プログラムへ変換することができる。更に、並行模擬動
作系列に基づく逐次実行で正しく動作することが確認さ
れた非決定性のみを許容する並行性を導入することで、
正しく動作する並行プログラムを得ることができる。こ
れによって、並行プログラムのテスト・デバッグが更に
容易となるという利点がある。

【０２２９】（実施例８）本実施例は、図１のように構
成されたコンピュータシステムにおいて、図７９に示す
ように各プロセッサ１−１〜１−Ｎに少なくとも１個以
上のプロセスＡ〜Ｄが登録され、それぞれのプロセスは
並行／並列に動作しており、互いにメッセージを交換し
ながら情報交換して処理を行うというプロセス実行環境
において、並行プログラムの作成を行う例である。

【０２３０】本実施例では、並行プログラムのテストを
超逐次プログラムに対して行うが、バグのあった場合は
ソースコードたる並行プログラムを修正せずに、逐次化
ルールを修正することでテスト・デバッグを行う。

【０２３１】図８０は、本実施例に係る並行プログラム
作成支援装置の概略構成を示す図である。

【０２３２】図８０において、ＣＰファイル記憶部１１
に格納されている第１並行プログラムは、逐次化装置１
２において逐次化ルール記憶部１３に格納された逐次化
ルールに従って、メタレベルにおいてデフォルト逐次性
が導入されることにより、超逐次プログラム（ＨＳＰ）
に変換され、ＨＳＰファイル記憶部１４に記録される。
ここで、逐次化ルールはソースプログラム（ＣＰファイ
ル）を実行装置２２で実行させた際に得られる実行ログ
情報となり、ＨＳＰファイル記憶部１４はＣＰファイル
と逐次化ルールである実行ログ情報の対からなる。ユー
ザは、この超逐次プログラムＨＳＰを出力装置５によっ
て見ることができる。この超逐次プログラムＨＳＰは、
ユーザによる入力装置４からの指示によってテスト実行
装置１５に入力され、テスト実行が行われる。

【０２３３】テスト実行装置１５は、テスト実行の結果
（実行ログ）を出力装置５に提示する。ユーザは、この
テスト実行の結果に基づいて、逐次化ルール修正装置２
６を用いて逐次化ルール記憶部１３に格納されている逐
次化ルールを修正し、超逐次プログラムＨＳＰに対し所
定のテスト・デバッグを行うことができる。

【０２３４】ユーザは、このように逐次化ルールの修正
により超逐次プログラムＨＳＰに対して所定のテスト・
デバッグを行った後、入力装置４から再度テスト実行の
指示を与える。これにより、テスト・デバッグの行われ
た超逐次プログラムＨＳＰは、テスト実行装置１５に入
力され、再度テスト実行が行われる。このテスト・デバ
ッグは、超逐次プログラムＨＳＰが正常に動作すること
を確認するまで繰り返し行われる。

【０２３５】そして、本実施例ではテスト・デバッグに
より正常に動作することを確認した時点で、逐次化ルー
ル修正装置２６により逐次化ルール記憶部１３に格納さ
れている逐次化ルールが修正され、この修正の後の逐次
化ルールが逐次化ルール記憶部１３に新たに記録され
る。この逐次化ルールの修正によって、超逐次プログラ
ムに対して良い非決定性に関する情報が部分的に導入さ
れる。超逐次プログラムＨＳＰは部分超逐次プログラム
ＰＨＳＰに変換される。

【０２３６】次に、部分超逐次プログラムＰＨＳＰは、
潜在的に存在する無害な並行性を顕在化させるために、
並行化装置１８にて部分超逐次プログラムＰＨＳＰにお
ける逐次化ルールを分割基準指定装置２３からの指示に
基づいて各プロセス毎に分割し、各プロセス毎の起動順
序制御を可能とする第２並行プログラム１９に変換す
る。

【０２３７】図８１は、本実施例に係る並行プログラム
作成方法の概略手順を説明するための図である。

【０２３８】（１） ステップＡ１：モデル化 対象の並行システムに対し、並行性を用いた自然なモデ
ル化を行う。また、各プロセス構造を決定する。更に、
該プロセス内を並行プログラム等を用いたプログラミン
グにより、並行構造を有する第１並行プログラムをソー
スプログラムとして記述する。このソースプログラムに
は、バグが潜在的に存在する可能性がある。

【０２３９】（２） ステップＡ２：逐次化 デフォルト逐次性を導入することによって、第１並行プ
ログラムを逐次構造の超逐次プログラムに変換する。本
実施例では、メタレベルにおいてデフォルト逐次性を導
入する。ここで、メタレベルとはソースプログラムその
もののレベルについていうのではなく、ソースプログラ
ムの実行を管理するレベルをいう。例えば、並行プログ
ラムで記述された第１並行プログラムを、それとは別に
管理されるスケジューラによって逐次的に実行すること
をいう。すなわち、ここでいう逐次化とは、ＣＰファイ
ル記憶部１１と逐次化ルール記憶部１３を対応付けるこ
とである。よって、得られる超逐次プログラムは、第１
並行プログラムと逐次化ルールの対からなるとする。

【０２４０】（３） ステップＡ３：超逐次プログラム
のテスト・デバッグ ステップＡ２で逐次化された超逐次プログラムを実行
し、テストを行う。この際のテスト実行は、第１並行プ
ログラムを逐次化ルールに基づいて動作させることをい
う。機能面のバグがある場合は、第１並行プログラムを
修正し、ステップＡ２へ戻る。タイミング面のバグがあ
る場合は、ステップＪ１に移行する。タイミング面のバ
グがない場合は、その逐次化ルールを保存してステップ
Ａ４に移行する。

【０２４１】（４） ステップＪ１：逐次化ルールの修
正 ステップＡ３でタイミング面のバグがある場合は、逐次
化ルールを修正した後、ステップＡ２に戻る。

【０２４２】（５） ステップＡ４：良い非決定性の導
入 良い非決定性の追加が必要な場合は、逐次化ルールを修
正した後、ステップＡ２に戻る。良い非決定性の追加が
必要ない場合は、ステップＡ７に移行する。

【０２４３】（６） ステップＡ７：並行化コンパイル ステップＡ３で保存された逐次化ルールから無害な非決
定性部分を抽出し、その部分を並行化することで、部分
超逐次プログラム全体を第２並行プログラムに変換す
る。

【０２４４】図８２は、図７９に示したようなプロセス
間通信のある並行プログラムをメタレベルにおいてデフ
ォルト逐次性を導入して実行した結果の実行履歴である
ログ情報の一例を示す図である。

【０２４５】ユーザは、このログ情報を出力装置５によ
って見ることができる。図８２において、縦のスクロー
ルバーは任意の時刻のログ情報を見るために表示情報を
スクロールするために用い、横のスクロールバーは良い
非決定性を導入し複数の実行可能な候補がある時に、そ
れら情報を見るために用いる。このように縦と横のスク
ロールバーを用いることにより、全ログ情報中の任意の
場所を見ることができる。更に、画面上部に示された
「順序修正」と「非決定性導入」は、後述するそれぞれ
の操作を要求する時に、選択して処理を指示するために
用いる。

【０２４６】更に、ユーザは入力装置４を介して指示を
行うことによって、ＨＳＰファイル記憶部１４に保存さ
れている第１並行プログラムと実行ログ情報ファイルを
テスト実行装置１５に入力し、超逐次プログラムＨＳＰ
としてテスト実行を行うことができる。

【０２４７】テスト実行装置１５は、テスト実行の結果
を出力装置５に提示する。ユーザは、このテスト実行の
結果に基づいて、超逐次プログラムＨＳＰに対し入力装
置４を用いて所定のテスト・デバッグを行うことができ
る。テスト・デバッグは、機能面の不具合についてはＣ
Ｐファイル記憶部１１内の第１並行プログラムを修正
し、タイミング面の不具合については逐次化ルール記憶
部１３内の実行ログ情報ファイルを修正し、再度、修正
された第１並行プログラムと実行ログ情報を対応付けし
直し、超逐次プログラムを再作成する。

【０２４８】ユーザは、超逐次プログラムＨＳＰに対し
て前記テスト・デバッグを行った後、再度入力装置４か
らテスト実行の指示を与える。これにより、テスト・デ
バッグの行われた超逐次プログラムＨＳＰは、テスト実
行装置１５に入力され、再度テスト実行が行われる。こ
のテスト・デバッグは、超逐次プログラムＨＳＰが正常
に動作することを確認するまで繰り返し行われる。

【０２４９】テスト・デバッグにより正常に動作するこ
とを確認した時点で、逐次化ルール修正装置２６により
超逐次プログラムに対して良い非決定性に関する情報を
部分的に導入していく。逐次化ルール修正装置２６より
導入された良い非決定性に関する情報は、ログ情報に反
映され、ＨＳＰファイル記憶部１４に記録される。

【０２５０】次に、逐次化ルール修正装置２６により良
い非決定性に関する情報が導入された超逐次プログラム
（部分超逐次プログラムＰＨＳＰ）について、ユーザか
らの指示に従ってテスト実行装置１５によりテスト実行
を行い、テスト・デバッグを行う。この場合、部分超逐
次プログラムＰＨＳＰの振る舞いは、良い非決定性に関
する情報の導入された部分については、非決定的な振る
舞いをするので、その振る舞い全てについてテスト・デ
バッグを行うことが好ましい。このようにして、テスト
・デバッグ及び良い非決定性に関する情報の導入を繰り
返し、良い非決定性に関する情報を徐々に付加してい
く。

【０２５１】良い非決定性に関する情報がインクリメン
タルに導入され得られた部分超逐次プログラムＰＨＳＰ
は、ユーザからの指示により並行化装置１８に入力され
る。この並行化装置１８では、部分超逐次プログラムＰ
ＨＳＰのうち、無害な非決定性部分を抽出し、部分超逐
次プログラムＰＨＳＰ全体を並行化する。即ち、集中ロ
グ情報を各プロセス毎にその起動順序を規定するように
分割し、各プロセス毎に起動制御を行うようにすること
で、デフォルト逐次性を解除し、部分超逐次プログラム
を並行プログラムに変換して第２ＣＰファイル記憶部１
９に記録する。ユーザは、この並行プログラムを出力装
置によって見ることができるとともに、最終的なテスト
・デバッグを行うことができる。

【０２５２】図８３は、まず、ステップＡ２〜ステップ
Ａ４の処理に関する部分超逐次プログラムを構成するま
での部分の構成例を示す。以下に、それぞれの構成部分
の機能実現法について説明する。

【０２５３】図８４に、プロセス間で交換されるメッセ
ージのフォーマットを示す。「宛先情報」には宛先プロ
セス名等の情報伝達先を指定する情報がセットされ、
「送信元情報」には送信元プロセス名等の送信元を規定
する情報がセットされる。「メッセージ本体」には、プ
ロセス間で交換するデータがセットされる。

【０２５４】ログ情報として保存される情報は、図８４
のメッセージフォーマット中の宛先情報と送信元情報を
用いて生成される。以下の説明においては、ログ情報と
して宛先情報として宛先プロセス名を、送信元情報とし
て送信元プロセス名だけを用いるが、同一プロセスが複
数回利用される場合は、何回目の使用かの判別がつかな
くなるので、送信元情報を｛プロセス名とプロセス起動
回数｝からなるように拡張することができる。更に、あ
るプロセスの１回の起動中に複数回のメッセージ送信が
ある場合は、今回の起動後の何回目の送信かを特定する
ため、送信元情報を｛プロセス名、プロセス起動回数、
メッセージ送信回数｝からなるように拡張することがで
きる。更に、各プロセスが複数の処理の単位（メソッド
と以降呼ぶ）を持つ場合には、その情報も付加して送信
元情報は｛プロセス名、メソッド名、メソッド起動回
数、メッセージ送信回数｝とする事もできる。

【０２５５】また、宛先情報も宛先プロセス名だけでな
く、宛先メソッド名を付加して｛宛先プロセス名とメソ
ッド名｝とすることもできる。もちろん、実行形態に応
じて宛先情報と送信元情報を組み合わせることができる
ため、計８通りの組み合わせが存在する。

【０２５６】まず、実行装置２２について詳述する。前
述したように、第１並行プログラムをランダムに実行す
る。その際の実行ログを逐次化ルールとするため、本実
施例では、逐次化ルールとしてプロセス間の全ての通信
を一旦プロセス群制御部２０３に送り、処理待ちメッセ
ージ保存部２０４に蓄える。プロセス群制御部２０３
は、処理待ちメッセージ保存部２０４から順次メッセー
ジを取り出し、本来の宛先に対して再度送る。よってプ
ロセス群制御部２０３によって全プロセスの起動が逐次
的に制御されるため、第１並行プログラムは逐次的に処
理されるようになる。

【０２５７】この時、プロセス群制御部２０３によって
逐次的に処理されたメッセージは、ログ情報取得部２０
２によって時系列にログ情報としてログ情報記憶部２０
１に保存される。このログ情報が逐次化ルール記憶部１
３となり、以降の逐次実行時の実行制約条件となる。

【０２５８】図８５は、プロセス間の通信をプロセス群
制御部２０３を経由して行う様子を示す。この例では、
プロセスＡとＢがプロセスＣにメッセージを送信する
時、プロセスＡとＢのどちらのメッセージが先にプロセ
スＣに届いても良いとする良い非決定性が存在する場合
であるが、実行時にたまたまプロセスＡがプロセスＢよ
り先にメッセージを送信したとすると、プロセス群制御
部２０３において｛プロセスＡ→プロセスＣ｝が先にロ
グ情報に記憶され、続いて｛プロセスＢ→プロセスＣ｝
が記憶される。図８６に、その場合の逐次化ルールであ
るログ情報の一例を示す。

【０２５９】次に、逐次化装置１２において、ＣＰファ
イル記憶部１１に記憶されている第１並行プログラムと
上記のようにして得られた逐次化ルールであるログ情報
を対応付ける。これにより、並行性を持った第１並行プ
ログラムは、逐次化情報が付加された超逐次プログラム
に変換される。

【０２６０】次に、テスト実行装置１５におけるテスト
・デバッグの段階では、プロセス間で交換されるメッセ
ージをプロセス群制御部２０３において一旦受信し、ロ
グ情報記憶部２０１に記憶されたログ情報の順序に従っ
て本来の宛先に対して送信するようにする。このためプ
ロセス群制御部２０３は、処理待ちメッセージ保存部２
０４に保存されたメッセージ中から、ログ情報に従った
順序でメッセージを取り出して送信する機構を有してい
る。

【０２６１】上記のように、プロセス群制御部２０３で
メッセージ送信順序をログ情報に指定された順序で送信
するようにすることにより、並行プログラムの難しさの
一つである処理順序の非決定性を解決することができ、
処理の再現性が実現される。つまり、図８５の例におい
て、あるテスト実行時にはプロセスＢの方がプロセスＡ
より先にメッセージをプロセスＣに送ったとしても、プ
ロセス群制御部２０３でログ情報に図８６に示すように
プロセスＡからのメッセージを先にプロセスＣに送る旨
が記載されている場合は、プロセスＢからのメッセージ
を処理待ちメッセージ保存部２０４に保存しておき、プ
ロセスＡからのメッセージを受信しプロセスＣに対して
送信した後、処理待ちメッセージ保存部２０４に保存し
ておいたプロセスＢからのメッセージをプロセスＣに送
る。

【０２６２】図８７に、プロセス群制御部２０３の処理
の流れを示す。

【０２６３】ログ情報記憶部２０１に保存されたログ情
報に従って実行順番が一意に規定された超逐次プログラ
ムにおけるテスト・デバッグは、機能面に不具合がある
場合はソースプログラムを修正して上記処理ステップの
ステップＡ２から再度行う必要があるが、タイミングの
みに不具合がある場合は、容易にテスト・デバッグをす
る事ができる。つまり逐次化ルールであるログ情報を修
正し意図する順番にログ情報を書き換えれば良い。この
書換は、ログ情報修正部２０５によって行う。逐次化ル
ールであるログ情報の修正は、ユーザからの指示により
逐次化ルール修正装置２６内のログ情報修正部２０５に
おいて行う。ログ情報修正部２０５は、図８２に示すよ
うにその処理した順番（時系列）にログ情報を表示する
ことができる表示部を持つ。そしてタイミングのバグを
修正したいユーザは、ログ情報の順序を入れ換える入替
部を起動し、図８８に示すように処理順序を交換したい
メッセージを指定する。図８８の例では、２メッセージ
間の順序入れ替えを指示したが、複数メッセージの順序
を入れ換えることも可能である。もちろん１メッセージ
以上のメッセージを１つの集合としてとらえ、集合間で
の交換も可能である。そして、ログ情報修正部２０５に
は、ログ情報記憶部２０１のログ情報を入替部によって
指定されたように書き換える書換部があり、図８８の例
の場合は図８９のように変更される。また入れ替えメッ
セージの指定法としては、ポインティングデバイスを使
って該当メッセージを指定する方法や、画面上の行番号
をキーボードから指定する方法等がある。

【０２６４】上記のように、ログ情報を意図する順序に
並べ替えることによって、テスト実行時にプロセス群制
御部２０３が受信メッセージを本来の宛先プロセスに送
信する順番を変えることになるため、タイミングの不具
合を容易に修正することができるようになる。

【０２６５】例えば、図８５において本来プロセスＣは
プロセスＢからのメッセージをプロセスＡからのメッセ
ージより先に処理しなければならない場合に、ログ情報
に図８６に示すようにプロセスＡからのメッセージを先
に処理するようになっていたならば、上記の手順に従っ
てログ情報を図８９に示すように修正すればよい。これ
によって、プロセス群制御部２０３のメッセージ処理順
番が変更されるため、処理のタイミングの不具合を解決
することができる。

【０２６６】このようなタイミングの不具合解決方法を
用いることによって、プロセスの処理順序を変更するた
めにソースプログラムを修正することなく、容易にテス
ト・デバッグをすることが可能となり、プログラム開発
の生産性が向上する。

【０２６７】次に、良い非決定性の導入方法について説
明する。

【０２６８】良い非決定性は、ログ情報修正部２０５内
の非決定性導入部によってログ情報を修正することで行
う。これは、超逐次化されたプログラムにユーザが意図
的に非決定性を導入するものである。例えば図８５に示
す処理において、プロセスＡとプロセスＢのどちらが先
にプロセスＣにメッセージを送っても良い場合には、対
象となるログ情報を図９０に示すように指定することに
よって行う。これによって、非決定性導入部は、指定さ
れたメッセージの順序制約を解除した形で、例えば図９
１（ａ）、図９１（ｂ）に示すようにログ情報記憶部２
０１に記憶されたログ情報を修正する。図９１（ｂ）
は、図９１（ａ）を横スクロールバーで右へシフトする
ように指示することによって得られる。この場合は２つ
のメッセージ順序の非決定性を導入した場合であるが、
更に多数のメッセージ順序の非決定性を導入する場合
は、順次右へシフトすることによってその一覧を見るこ
とができる。

【０２６９】図９１では、プロセスＡないしプロセスＢ
からのメッセージであれば、プロセスＣにメッセージを
送り、続いて次のタイミングでも、プロセスＡないしプ
ロセスＢからのメッセージであれば、プロセスＣにメッ
セージを送るように解釈する。プロセス群制御部２０３
が上記のようにログ情報を解釈するようにすることによ
って良い非決定性を扱うことが可能となる。これは、プ
ロセス群制御部２０３の処理における図８７におけるス
テップＫ３において、メッセージ送信元として一致する
か否かのチェック対象が、一つから複数個に拡張される
ことによって実現できる。

【０２７０】但し、上記例では、プロセスＣがプロセス
ＡないしプロセスＢから続けて２つのメッセージを受信
した場合でも、それらのメッセージを処理してしまう問
題点があるが、これは、先に受信したメッセージを次の
起動候補から削除することによって容易に防止すること
ができる。削除対象となるメッセージは、本実施例では
説明の容易のために、送信先情報をプロセス名のみで示
したが、図８４の送信先情報説明で前述したように唯一
に特定できるので、未処理メッセージの情報を削除する
ことはない。

【０２７１】よって、この良い非決定性の導入によっ
て、外部からの非決定的な刺激に適切に反応でき、プロ
セスの柔軟性、再利用性、拡張性を実現できる。

【０２７２】上記の実施例では、良い非決定性を２つの
メッセージの到着順序に関して示したが、２つ以上の複
数のメッセージの到着順序に良い非決定性を与えること
も可能である。その場合でも、上記処理と同様にプロセ
ス群制御部２０３の処理における図８７のステップＫ３
においてメッセージ送信元として一致するか否かのチェ
ック対象を、一つから複数個に拡張することによって解
決されるので、正しく動作することは明らかである。

【０２７３】次に図８１におけるステップＡ７と図８０
の並行化装置１８に関する並行化コンパイルのフェーズ
について詳述する。図９２に、ステップＡ７の処理に関
する部分の構成例を示す。ここで、集中ログ情報記憶部
３０１はＨＳＰファイル記憶部１４内に保存されている
良い非決定性導入後の実行ログ情報を保存している記憶
部である。例えば図７９におけるプロセス群が図９３に
示すようなメッセージ交換を行った場合、図８２で示し
たような超逐次プログラム用の集中ログ情報から、例え
ば図９４のように良い非決定性が導入された集中ログ情
報に変換されたものが保存されているとする。

【０２７４】以下には、良い非決定性が導入された集中
ログ情報を各プロセス毎に分割する手順を図９２、図９
４、図９５を用いて説明する。集中ログ情報を分割する
基準は、分割基準指定装置２３内の分割基準指定部３０
３から指定する。この基準としては、例えば宛先プロセ
ス名であったり、宛先計算機番号であったりするが、以
下の説明では、宛先プロセス名を用いる。宛先名にメソ
ッド名も付加する場合には、分割基準として、｛宛先プ
ロセス名、メソッド名｝を指定して、宛先メソッド毎に
分割して分割ログを作ることも可能である。分割基準指
定部３０３では、この分割基準を保持している。

【０２７５】ユーザからの指示により集中ログ情報を分
割させようとすると、ログ情報分割部３０２が起動され
る。ログ情報分割部３０２は、図９５に示す手順に従っ
て集中ログ情報を分割基準指定部３０３によって指定さ
れた基準で分割する。

【０２７６】ログ情報分割部３０２が起動されると、分
割基準指定部３０３より分割基準値を読み込み（ステッ
プＬ１）、分割基準を把握する。続いて集中ログ情報記
憶部３０１に保存されているログ情報を１レコード読み
込み（ステップＬ２）、最終レコードか否かチェックす
る（ステップＬ３）。この例では、集中ログ情報の１レ
コード目は、図９４に示すようにプロセスＡからプロセ
スＤへのメッセージなので、最終レコードでないと判断
し、分割基準（宛先プロセス名＝プロセスＤ）に従っ
て、該当する分割ログ情報記憶部（ここでは、分割ログ
情報記憶部Ｄとする）に保存する（ステップＬ４）。こ
の操作を集中ログ情報記憶部３０１に記憶されているロ
グ情報が終了するまで繰り返す。この結果、図９６に示
すようにあて先プロセス毎に分割されたログ情報が分割
ログ情報記憶部Ａ、Ｂ、Ｃ、Ｄのそれぞれに保存され
る。

【０２７７】図９６（ａ）では、例えばプロセスＡはプ
ロセスＣからのメッセージを処理した後に、プロセスＤ
からのメッセージを処理することを規定している。ま
た、図９６（ｃ）のプロセスＣは、いわゆる良い非決定
性を導入した処理であり、プロセスＡないしプロセスＢ
からのメッセージを最初に処理し、次もプロセスＡない
しプロセスＢからのメッセージを処理することを規定し
ている。これは言い替えると、プロセスＡからのメッセ
ージとプロセスＢからのメッセージのどちらが先に来て
も良いという良い非決定性を表現している。ここでは、
２つのメッセージの順序の制約を解除した例を示した
が、より多くのメッセージの順序制約を解除し、良い非
決定性を導入したい場合は、同一行に所望数のメッセー
ジを列挙すれば良い。

【０２７８】また、分割ログ情報は宛先プロセス毎に分
割されるため、分割ログ情報中の送信先プロセス名を省
略することもできる。

【０２７９】次に、このようにプロセス毎に分割された
ログ情報に従って各プロセスが動作する方式の一例を述
べる。各プロセスは、例えば図９７に示すようにメッセ
ージを受信し実際のプロセスの処理を開始する前にプロ
セス制御部３０５を呼出し、図９８に示す処理を行う。
このようなプロセス制御部の呼出は、並行化装置１８の
一部として第１並行プログラムにおける各プロセスの処
理の先頭に呼出処理を挿入するようにソースプログラム
を書き換えることによって行うことができる。即ち、各
プロセスは図９９に示すように、当該プロセス本来の処
理部分に加え、プロセス制御部３０５、分割ログ情報記
憶部３０４、処理待ちメッセージ保存部３０６からな
る。プロセス制御部３０５は、当該プロセスに内在する
分割ログ情報記憶部３０４に保存されているログ情報を
参照してメッセージ処理を行い、処理すべきメッセージ
でない場合は、処理待ちメッセージ保存部３０６に保存
する。

【０２８０】次に、プロセス制御部３０５の処理につい
て図９６と図９８を用いて説明する。

【０２８１】例えばプロセスＡは、図９３に示す処理の
流れの場合、プロセスＣとプロセスＤのどちらから先に
メッセージをもらうかは決定されておらず、ここに処理
タイミングの非決定性が存在している。しかし、ここで
は超逐次で実行したときの実行ログ（図８２相当）よ
り、プロセスＣからのメッセージを先に処理し、その後
にプロセスＤからのメッセージを処理するように規定さ
れる。よって、無害の非決定性を導入したとしても、こ
のメッセージ処理順序の規定は守られなければならな
い。

【０２８２】最初の例として、プロセスＡが最初にプロ
セスＣからのメッセージを受信して起動された場合を示
す。プロセスＡがプロセスＣからのメッセージを受信し
て起動されたならば、プロセス制御部が呼び出され、当
該プロセスを起動させたメッセージの送信元情報を得る
（ステップＭ１）。ここでは、送信元情報Ｉｓ＝｛プロ
セスＣ｝となる。続いて分割ログ情報記憶部よりまず最
初に来るべきメッセージ情報Ｉｒ１を得る（ステップＭ
２）。ここでは、Ｉｒ１＝｛プロセスＣ｝となる。

【０２８３】次に、現在受信したメッセージが分割ログ
情報に記憶された順序に一致しているかを調べるため、
ＩｓがＩｒ１に含まれているかどうかを調べる（ステッ
プＭ３）。この場合は、ともにプロセスＣで一致し含ま
れているため、受信メッセージに基づいた処理を即行う
ことが許される。よって次の起動チェックのために分割
ログ情報記憶部から読み出すレコードを１つ進めておく
（ステップＭ４）。そして、プロセス本体の処理を開始
する前に、処理待ちメッセージ保存部に実行待ちメッセ
ージが存在している場合には、その保存されたメッセー
ジが起動可能となったかどうかを調べる。つまり、分割
ログ情報記憶部に保存されている情報から次に処理すべ
きメッセージ情報Ｉｒ２を取り出し（ステップＭ５）、
それに含まれるメッセージが処理待ちメッセージ保存部
に存在しているか調べる（ステップＭ６）。この場合
は、Ｉｒ２＝｛プロセスＤ｝となるが、処理待ちメッセ
ージ保存部にメッセージが存在しないため処理を終了
し、プロセスＣからのメッセージに基づいた本処理を行
う。

【０２８４】続いて、プロセスＡ宛にプロセスＤからの
メッセージが届いたならば、上記同様に処理を行うと、
Ｉｓ＝｛プロセスＤ｝、Ｉｒ１＝｛プロセスＤ｝とな
り、集合Ｉｓは集合Ｉｒ１と等しいか又はＩｒ１に含ま
れる。Ｉｒ２は存在しないため、処理待ちメッセージ保
存部内のメッセージを調べる必要なく処理を終了し、プ
ロセスＤからのメッセージに基づいた処理を行う。

【０２８５】また、逆にプロセスＡが、プロセスＤから
先にメッセージを受信した場合の処理の流れを示す。つ
まりプロセスＡが、最初にプロセスＤからのメッセージ
を受信して起動されたならば、プロセス制御部が呼び出
され、当該プロセスを起動させたメッセージの送信元情
報を得る（ステップＭ１）。ここでは、送信元情報Ｉｓ
＝｛プロセスＤ｝となる。続いて、分割ログ情報記憶部
よりまず最初に来るべきメッセージ情報Ｉｒ１を得る
（ステップＭ２）。ここではＩｒ１＝｛プロセスＣ｝と
なる。

【０２８６】次に、現在受信したメッセージが分割ログ
情報に記憶された順序に一致しているかどうかを調べる
ため、ＩｓがＩｒ１に含まれているか調べる（ステップ
Ｍ３）。この場合は、含まれないため即プロセスＤから
のメッセージを処理してはいけないと判断し、処理待ち
メッセージ保存部３０６にプロセスＤからのメッセージ
を保存し（ステップＭ８）、プロセスＡの処理を強制的
に終了させる（ステップＭ９）。即ち、プロセスＤから
のメッセージに基づいた処理を行うことなくプロセスＡ
の処理を終了する。

【０２８７】続いて、プロセスＡ宛にプロセスＣからの
メッセージが届いたならば、上記同様に処理を行うと、
Ｉｓ＝｛プロセスＣ｝、Ｉｒ１＝｛プロセスＣ｝となり
ＩｓはＩｒ１に含まれるため、受信メッセージに基づい
た処理を即行うことが許される。よって次の起動チェッ
クのために分割ログ情報記憶部から読み出すレコードを
１つ進る（ステップＭ４）。そして、プロセス本体の処
理を開始する前に、処理待ちメッセージ保存部に起動可
能となった実行待ちメッセージが存在しているかどうか
を調べる。つまり、分割ログ情報記憶部に保存されてい
る情報から次に処理すべきメッセージ情報Ｉｒ２を取り
出し（ステップＭ５）、それに含まれるメッセージが処
理待ちメッセージ保存部に存在しているか調べる（ステ
ップＭ６）。この場合は、Ｉｒ２＝｛プロセスＤ｝とな
り、処理待ちメッセージ保存部に先ほど保存しておいた
該当メッセージが存在するため、その実行可能となった
メッセージを次に処理するために、送信先（ここではプ
ロセスＡ）宛に送信元情報等をそのまま（この例では、
プロセスＤのまま）送信する（ステップＭ７）。そし
て、プロセスＡは受信メッセージとしてプロセスＣから
送られたメッセージに基づく処理を行うべくプロセス制
御部の処理を終了する。

【０２８８】更に、プロセスＡは前記処理待ちメッセー
ジ保存部から取り出し送信したメッセージを受信するの
で、上記同様に処理を行うと、Ｉｓ＝｛プロセスＤ｝、
Ｉｒ１＝｛プロセスＤ｝となりＩｓはＩｒ１となる。Ｉ
ｒ２はもはや存在しないため、処理待ちメッセージ保存
部内のメッセージを調べる必要なく処理を終了し、プロ
セスＤからのメッセージに基づいた処理を行う。

【０２８９】このことより、たとえメッセージの到着順
序が実行ログに記載された順序と異なっていたとして
も、実行ログに記載された順序に処理され、非決定的な
処理の再現性が保証される。

【０２９０】次に良い非決定性を導入した場合の処理例
として、プロセスＣの動作を例に示す。プロセスＣが最
初にプロセスＡからのメッセージを受信して起動された
ならば、プロセス制御部が呼び出され、当該プロセスを
起動させたメッセージの送信元情報を得る（ステップＭ
１）。ここでは、送信元情報Ｉｓ＝｛プロセスＡ｝とな
る。続いて分割ログ情報記憶部よりまず最初に来るべき
メッセージ情報Ｉｒ１を得る（ステップＭ２）。ここで
はＩｒ１＝｛プロセスＡ、プロセスＢ｝となり、プロセ
スＡからのメッセージでもプロセスＢからのメッセージ
でも、どちらからのメッセージでも良いとしている。

【０２９１】次に、現在受信したメッセージが分割ログ
情報に記憶された順序に一致しているかを調べるため、
ＩｓがＩｒ１に含まれているかどうかを調べる（ステッ
プＭ３）。この場合、集合Ｉｓは集合Ｉｒ１と等しいか
又はＩｒ１に含まれるため、受信メッセージに基づいた
処理を即行うことが許される。よって、次の起動チェッ
クのために分割ログ情報記憶部から読み出すレコードを
１つ進めておく（ステップＭ４）。そして、プロセス本
体の処理を開始する前に、処理待ちメッセージ保存部に
実行待ちメッセージが存在している場合には、その保存
されたメッセージが起動可能となったかを調べる。つま
り、分割ログ情報記憶部に保存されている情報から次に
処理すべきメッセージ情報Ｉｒ２を取り出し（ステップ
Ｍ５）、それに含まれるメッセージが処理待ちメッセー
ジ保存部に存在しているか調べる（ステップＭ６）。こ
の場合は、Ｉｒ２＝｛プロセスＡ、プロセスＢ｝となる
が、処理待ちメッセージ保存部にメッセージが存在しな
いため、処理を終了し、プロセスＡからのメッセージに
基づいた本処理を行う。

【０２９２】続いて、プロセスＣ宛にプロセスＢからの
メッセージが届いたならば、上記同様に処理を行うと、
Ｉｓ＝｛プロセスＢ｝、Ｉｒ１＝｛プロセスＡ、プロセ
スＢ｝となり、ＩｓはＩｒ１と等しいか又はＩｒ１に含
まれる。Ｉｒ２は存在しないため、処理待ちメッセージ
保存部内のメッセージを調べる必要なく処理を終了し、
プロセスＢからのメッセージに基づいた処理を行う。

【０２９３】上記の良い非決定性導入の例では、メッセ
ージの到着順序が逆の状態、即ちプロセスＣに、プロセ
スＢからのメッセージが先に到着し、その後にプロセス
Ａからのメッセージが到着した場合も同様に処理できる
ことは明かである。

【０２９４】但し、上記例では、プロセスＣがプロセス
ＡないしプロセスＢから続けて２つのメッセージを受信
した場合でも、それらのメッセージを処理してしまう問
題点があるが、これは、先に受信したメッセージを次の
起動候補から削除することによって容易に防止すること
ができる。削除対象となるメッセージは、本実施例では
説明の容易のために、送信先情報をプロセス名のみで示
したが、図８４の送信先情報説明で前述したように唯一
に特定できるので、、未処理メッセージの情報を削除す
ることはない。

【０２９５】上記のように、オブジェクト毎に実行ログ
情報を分割して動作させることによって、並行プログラ
ムが潜在的に持っている無害な非決定性を実現しなが
ら、超逐次プログラムで抽出した逐次性を維持している
ため、処理の再現性を保持しており、超逐次プログラム
実行時と同一結果を、より高い処理性能で実現すること
が可能となる。

【０２９６】また、上記の例では良い非決定性を２つの
メッセージの到着順序に関して示したが、２つ以上の複
数のメッセージの到着順序に良い非決定性を与えること
も可能である。その場合でも、上記処理はＩｒ１ないし
Ｉｒ２が複数の要素を持つことによって解決されるの
で、正しく動作することは明らかである。

【０２９７】また、上記例では、各プロセスないし各メ
ソッドの処理の始めにプロセス制御部を呼び出して実現
する実施例を示したが、各計算機のオペレーティングシ
ステムが、宛先プロセス毎の処理待ちメッセージ保存部
を保持し、メッセージ処理の都度、該当する分割ログ情
報を参照して、該当プロセスを起動すること又は処理待
ちメッセージ保存部に保存することによって実現するこ
とも可能である。

【０２９８】この場合は、図９８におけるステップＭ７
で次の処理対象メッセージを送信することなく、実行待
ち状態から次に起動可能なプロセスとしてスケジューリ
ング対象に変更すれば良い。

【０２９９】本実施例によれば、ソースプログラムを修
正することなく逐次化ルールであるログ情報を書き換え
ることにより、処理タイミングの非決定性に起因する不
具合を容易に解決することができる。このことによっ
て、処理タイミングの非決定性が内在する並行／並列／
分散プログラムの開発を容易にし、生産性を向上させる
ことができる。

【０３００】また、本実施例では、ユーザの意図する良
い非決定性のみを容易に導入することが可能になるた
め、並行プログラムとしての柔軟性、再利用性、拡張性
を維持することもできる。

【０３０１】更に、並行プログラムを逐次化して得られ
た全プロセスの集中ログ情報を各プロセス毎に分割し、
分割されたログ情報に基づいて各プロセスを制御するこ
とによって、無害の非決定性を自然に導入し、集中ログ
情報に基づく超逐次プログラム実行時と同一結果を高い
処理効率で得ることができる。

【０３０２】尚、本実施例に係るコンピュータシステム
の構成は、図１において、（ａ） 共有メモリ３が存在
しない構成の場合、（ｂ） Ｉ／Ｏインタフェース２が
バスで密にプロセッサ１−１〜１−Ｎが接続している並
列計算機の場合、（ｃ） Ｉ／Ｏインタフェースが通信
路で疎に結合している分散ネットワーク計算機構成の場
合、（ｄ） 単一プロセッサで構成される場合、及びそ
れらの組み合わせの場合、が考えられる。

【０３０３】（実施例９）本実施例で使用される新しい
概念であるセクションについて説明をする。

【０３０４】本実施例におけるセクションとはスレッド
の入口を１個のみ持ち、出口を複数持つプログラム断片
を言う。ここでスレッドとは、コンピュータ言語の分野
で一般的に用いられる用語であり、プログラムをたどり
ながら実行をする作用体をいう。例えばスレッドが同時
に複数走った場合には、それは並行実行を意味してい
る。

【０３０５】下記のようなプログラム断片があったとす
る。 ｃｏｄｅ１ ｃｏｄｅ２ ： ｂｒａｎｃｈ 処理１ 処理２ ここで、簡単のためｃｏｄｅ１からｂｒａｎｃｈ命令ま
での区間で、区間外への分岐命令又は同期命令はないも
のとする。このプログラム断片をスレッドが処理してい
くとき、ｃｏｄｅ１が実行の開始点、すなわち、ｃｏｄ
ｅ１がスレッドの入口となる。次に、処理が進みｂｒａ
ｎｃｈ命令に到達した時、ｂｒａｎｃｈ命令までの処理
内容に応じて処理１に分岐するか処理２に進むかが決ま
るとすれば、スレッドが処理１に進む場合と処理２に進
む場合の２個の出口があることになる。従って、ｃｏｄ
ｅ１からｂｒａｎｃｈ命令までのプログラム断片はスレ
ッドの出口を２個持つセクションとなる。ところで、も
しｃｏｄｅ１からｂｒａｎｃｈまでの間でこのプログラ
ム断片から外部への分岐命令があった場合は、そこもこ
のセクションの出口の一つとなる。

【０３０６】上記の例は、１本のスレッドが複数の出口
から１個の出口を選択して出ていく場合を示したが、次
にプログラム断片の内部でスレッドの生成が行なわれる
場合の例を示す。 ｃｏｄｅ１ ｃｏｄｅ２ ： ｆｏｒｋ 処理１ 上記の例では、ｆｏｒｋ命令でスレッドの分裂、すなわ
ちもう一つのスレッドの生成が行なわれる。この時、処
理１は分裂した２本のスレッドによって並行に処理され
るが、これを２個の出口から各々のスレッドが出て行
き、処理１を実行するものとみなすことができる。従っ
て、ｃｏｄｅ１からｆｏｒｋ命令の間は、この区間に外
部への分岐命令がなければ、出口を２個持つセクション
となる。このように、プログラム断片の内部でスレッド
の生成が行なわれる場所も一種の分岐とみなされ、複数
の出口をもつセクションとなり得る。

【０３０７】図１００は、上記のようなセクションを概
念的に表した図である。図１００に示すように、セクシ
ョンは、スレッドの入口１０１と、セクションの本体部
分１０２と、スレッドの複数の出口１０３とからなる。
以後セクションを概念的に図示する時にはこのような表
現を用いる。

【０３０８】次にセクションの融合と分割を説明する。
図１０１はセクションの融合を表す概念図である。図１
０１は、Ｓ１１とＳ１２の２個のセクションが融合して
Ｓ１３という新たなセクションを生成する例を示してい
る。図１０１中の矢印２０１はＳ１１の出口の一つであ
り、それをＳ１２の入口に接続することで２個のセクシ
ョンの融合を可能としている。この例では２個のセクシ
ョンの融合を示したが、一般に複数のセクションにおい
て出口と入口を接続することにより、新たなセクション
を生成（融合）することができる。

【０３０９】図１０２はセクションの分割を表す概念図
である。図１０２は、セクションＳ２１を２個のセクシ
ョンＳ２２とＳ２３に分割する例を示している。ここ
で、以下のプログラム断片の例を考える。 ｃｏｄｅ１ ： ｃｏｄｅ２ ｃｏｄｅ３ ： ｃｏｄｅ４ ただし、ｃｏｄｅ１〜４には分岐命令を含まないものと
する。これをスレッドが処理する時、ｃｏｄｅ１が入口
でｃｏｄｅ４が出口となることから、このプログラム断
片を出口が１個のセクションとみなすことができる。こ
のプログラム断片をセクションＳ２１に対応させる。次
に、例えば、ｃｏｄｅ２とｃｏｄｅ３の間で分割して、
ｃｏｄｅ１〜ｃｏｄｅ２をセクションＳ２２、ｃｏｄｅ
３〜ｃｏｄｅ４をセクションＳ２３に対応させれば、セ
クションＳ２１はセクションＳ２２とセクションＳ２３
に分割されたことになる。このように１個のセクション
を複数のセクションに分割することが可能である。

【０３１０】次にセクションの分類について説明する。
セクションは基本セクションとグループセクションに分
類される。基本セクションは、内部に分岐命令や同期命
令を含まないセクションをいう。基本セクションを分割
した場合には、基本セクションになる。グループセクシ
ョンは基本セクション以外のセクションをいい、グルー
プセクションは複数の基本セクションに分割することが
できる。

【０３１１】セクションに予測実行時間を付加する場合
を説明する。ここではセクションを構成する個々の命令
の実行時間（又は平均実行時間）がわかっているものと
し、この時間を各命令の予測実行時間と呼ぶことにす
る。

【０３１２】基本セクションは途中で分岐することなく
直列に実行されるので、セクションを構成する各々の命
令の予測実行時間を合計することにより、そのセクショ
ンの入口から出口までの予測実行時間が計算される。基
本セクションの場合は、出口が複数あってもセクション
の出口は必ず命令列の最後の分岐命令又は同期命令であ
るため、一般に入口から各出口までの予測実行時間は等
しくなる。

【０３１３】グループセクションは基本セクションに分
解できるため、グループセクションの入口から各出口ま
でに通過する基本セクションの予測実行時間を加えるこ
とにより、出口までの予測実行時間が計算される。すな
わちグループセクションでは出口によって予測実行時間
は変わってくる。また、グループセクション内部に処理
結果に応じて回数が変わるループや無限ループ、ｊｏｉ
ｎ等の同期命令、入出力命令を含む実行時間の予測は不
可能である。その時は、グループセクションを、上記の
ような実行時間の予測ができないようなループ、同期命
令、入出力命令を内部に含まない複数のセクションに分
割し、分割されたセクションを対象とすれば良い。

【０３１４】上記の方法によりセクションの各出口まで
の予測実行時間が計算された後に、その中で最大のもの
をセクション自身の予測実行時間とする。

【０３１５】セクションの予測実行時間は、セクション
の実行の効率化のためにセクションの融合・分割をする
ときの指針となり、プログラム自身を最適化するときの
指針としても利用できる。

【０３１６】本実施例では同期の容易さ、実行時間の予
測の容易さのため、ｆｏｒｋ等のスレッドを生成する命
令とｊｏｉｎ等の同期命令、入出力命令はセクションの
内部には含まれずセクションの終端に位置し、実行時間
の予測不可能なループは内部に持たないものとする。

【０３１７】実施例９を図面を参照して具体的に説明す
る。図１０３は、本発明の実施例９の概略構成を示す図
である。

【０３１８】プログラム解析部４１１は、図示されない
入力部から入力されたソースプログラムを解析し、基本
セクションへの分割及びセクションの実行順序に関する
ルールの抽出をおこなう。プログラム解析部４１１で解
析された情報（すなわちセクション情報）はセクション
情報記憶部４１２に記憶される。

【０３１９】セクション情報編集部４１３はセクション
情報記憶部４１２に記憶されたセクション情報の編集を
行なう。具体的には、セクションの実行順序に関するル
ールの編集やセクションの融合・分割が、自動的に又は
ユーザによって行なわれる。コンパイル部４１４は各セ
クションをコンパイルしてオブジェクトコードに変換
し、その結果をセクション情報記憶部４１２に登録す
る。

【０３２０】実行部４１５はセクション情報記憶部４１
２に記憶されたセクション情報に基づき、セクションを
単位として逐次又は並行にプログラムを実行していく。
実行方法の逐次と並行の切替えは、逐次実行モードと並
行実行モードの２種類のモード間を切替えることによっ
て行なわれる。逐次実行モードで実行をすれば並行プロ
グラムの再現性の問題を回避することができる。すなわ
ち何度実行しても同じ結果が得られるため、並行プログ
ラムについて有効なテスト・デバッグを行なうことがで
きる。その状態で並行実行モードに切替えて実行すれ
ば、セクション単位の同期をとりながら実行をすること
により、安全な並行実行を行なうことができる。なお、
実行部４１５がインタプリタ的にのみプログラムを実行
する場合は、コンパイル部４１４は省略することができ
る。

【０３２１】実施例９を構成する各部分について詳細に
説明する。

【０３２２】まず、図１０３に示されるセクション情報
記憶部４１２について、特にセクションに関する情報が
どのような構造で記憶されるのかを詳細に説明する。セ
クション情報は、セクション自身に関する情報とセクシ
ョンの実行順序に関する情報（ルール）とに２分され
る。まずセクション自身がどのように記憶されているか
を図１０４を用いて説明する。

【０３２３】図１０４は、出口が３個のグループセクシ
ョン２個と出口が２個の基本セクション１個とから構成
される例を示し、全体として出口が６個のグループセク
ションの記憶方法を示している。セクション情報記憶部
４１２は、図１０４に示すような、セクションの管理テ
ーブル５０１、５０５、５０６、５０９を有する。これ
らの管理テーブルには図１０５に示すように、セクショ
ンのラベルと、セクションがコンパイルされているかを
示すフラグと、コンパイルされているならそのオブジェ
クトを指すポインタと、セクションがプログラムコード
かを示すフラグと、このセクションを構成するセクショ
ンの部品テーブルを指すか又はプログラムコードを指す
ポインタと、各出口を指すポインタとその出口までの予
想実行時間等が記憶される。

【０３２４】セクション情報記憶部４１２は、更に、図
１０４に示すセクションの部品テーブル５０２、５０
３、５０４を有する。部品テーブルとはグループセクシ
ョンを構成する個々の部品としてのセクションについて
記憶するテーブルである。具体的には、部品テーブル
は、図１０６に示すように、部品としてのセクションの
管理テーブルを指すポインタと、各出口がどのセクショ
ンに接続されているかを指すポインタ等が記憶される。
図１０４に示す例では部品テーブル５０２は他のグルー
プセクションの管理テーブル５０５を指すポインタと、
３個のうち２個の出口の接続先のセクションの、部品テ
ーブル５０３、５０４を指すポインタを記憶している。
ここで、例えば部品テーブルにおける出口５０８はどの
部品テーブルにも接続されていない。この時、その出口
を指すポインタは、管理テーブル５０１にセクションの
出口として記憶される。また、管理テーブル５０６がプ
ログラムコード５０７を指しているように、管理テーブ
ルはプログラムコードも同様に管理している。

【０３２５】セクションの実行順序に関するルールを説
明する。この場合において、スレッド１が以下のプログ
ラム断片を実行するとする。 処理１ ｊｏｉｎ スレッド２ 処理２ 上記のセクションは、スレッド１が処理１を終了させた
後、スレッド２の終了を待ち、処理２を行なう、という
ことを意味している。図１０７は上記の例をセクション
の概念図に置き換えて図示したものである。Ｓ３１は上
記の処理１を構成するセクションのうち最後のセクショ
ンである。Ｓ３２は上記の処理２を構成するセクション
のうち最初のセクションである。Ｓ３３はスレッド２が
実行する最後のセクションである。この時、このｊｏｉ
ｎ文によって、 セクションＳ３１の実行後、スレッド２におけるセクシ
ョンＳ３３の実行が終了してからセクションＳ３２の実
行が開始される というセクション実行順序のルールが抽出され、セクシ
ョン情報記憶部４１２に記憶される。このようにセクシ
ョンの実行順序に関するルールは、主に実行時にセクシ
ョン間の同期をとるために利用される。

【０３２６】図１０８は図１０３におけるプログラム解
析部４１１の詳細な構成を示す。図１０８において中間
言語変換部９０１は図示されない入力部から入力された
ソースプログラムを中間言語に変換する。中間言語変換
部９０１で中間言語に変換するのは、セクションの抽出
がしやすくなることと、各命令の実行時間が予測しやす
くなるという理由による。なお、中間言語変換部９０１
での変換に当たっては従来のコンパイラの技術がそのま
ま使用できる。セクション情報抽出部９０２は、中間言
語変換部９０１によって変換された中間言語から基本セ
クションを切り出し、セクションの実行順序に関するル
ール等を抽出する。

【０３２７】プログラム解析部４１１における処理の流
れを図を用いて詳細に説明する。図１０９はプログラム
解析部４１１における処理の流れを示した図である。

【０３２８】入力されたソースコードは、中間言語変換
部９０１において中間言語に変換される（ステップＮ
１）。変換された中間言語はセクション情報抽出部９０
２に引き渡される。

【０３２９】セクション情報抽出部９０２は、中間言語
から基本セクションの切り出しや実行順序のルールを抽
出するために初期化される（ステップＮ２）。この初期
化は新しいセクションの切り出しのたびに行なわれる。
この例では、基本セクションを切り出しながら同時にそ
のセクションの予測実行時間を計算するため、それに関
する初期化も行う。

【０３３０】中間言語を１行ずつ読み込み、処理を繰り
返していく。この繰り返しの中で中間言語の読み込みが
すべて終了した時は（ステップＮ３）、この時点まで読
み込んだ中間言語列を１個の基本セクションとしてセク
ション情報記憶部４１２に記憶し（ステップＮ８）、処
理を終了する（ステップＮ９）。

【０３３１】中間言語の読込みが終了していないのであ
れば、更に中間言語を１行読込み（ステップＮ４）、読
み込んだ中間言語が、例えばｊｏｉｎセクションの実行
順序のルールを決める命令ならば（ステップＮ５）、そ
れによって決定されるルールをセクション情報記憶部４
１２に登録する（ステップＮ１０）。中間言語が分岐又
は同期命令ならば（ステップＮ６）、その命令は基本セ
クションの切れ目となるので、初期化以降に読み込んだ
プログラム断片を１個の基本セクションとしてセクショ
ン情報記憶部４１２に記憶し（ステップＮ１１）、次の
セクションの抽出を行うために、ステップＮ２に戻る。
ステップＮ４において、読み込んだ中間言語の命令が上
記の条件を満たさなければ、その命令の予測実行時間を
切り出し中のセクションの予測実行時間に加え（ステッ
プＮ７）、ステップＮ３に戻る。ここで中間言語の各命
令の予測実行時間は、あらかじめ測定をする等してテー
ブル等に記憶させておけば良い。以上の手続きが終った
時点で、もとのプログラムは、中間言語列として切り出
された基本セクションと、セクション実行順序のルール
とに変換され、セクション情報記憶部４１２に記憶され
たことになる。

【０３３２】セクション情報編集部４１３の詳細な説明
をする。セクション情報編集部４１３は大きく二つの動
作をする。一つはセクションの融合・分割をする動作で
あり、もう一つの動作は、セクションの実行順序のルー
ルを編集する動作である。

【０３３３】セクションの融合・分割の主な目的として
は、セクションの大きさを揃えることによって、実行部
４１５においてより効率的な実行を行なわせることにあ
る。本実施例では、この動作にセクションの予測実行時
間を利用している。セクション情報編集部４１３では、
各セクションの予測実行時間がほぼ均一になるようにセ
クションの融合・分割をすれば良く、これは容易に自動
化できる。

【０３３４】また、セクション情報編集部４１３のセク
ションの実行順序のルールの編集により、実行時におけ
るセクション間の同期や、実行順序等を自由に変更する
ことができ、効果的なテスト・デバッグを可能とする。

【０３３５】図１１０を用いてセクション情報編集部４
１３の詳細な構成を説明する。図１１０においてセクシ
ョン情報変換部１１０１は、図示されない入力装置によ
り入力されたセクションの融合・分割の指示、セクショ
ンの実行順序のルールの編集要求に従い、セクション情
報記憶部４１２に記憶されたセクション情報を変更す
る。この動作は主にユーザによってなされるが、セクシ
ョンの融合・分割に関してはセクションの予測実行時間
を利用することにより容易に自動化をすることができ
る。セクション情報表示部１１０２はセクション情報記
憶部４１２に記憶されたセクション情報を、セクション
情報変更部１１０１からの指示に従い表示する。

【０３３６】図１１１は図１０３におけるコンパイル部
４１４の詳細な構成を示す。図１１１において、セクシ
ョン末端処理部１６０１は、セクションの末端に次に実
行すべきセクションの登録とセクションの終了のための
コードを書き込む。セクションコンパイル部１６０２
は、末端処理を受けたセクションをコンパイルしてオブ
ジェクトに変換し、セクション情報記憶部４１２に登録
する。

【０３３７】ここで、セクションの末端の処理の仕方を
説明する。例えば、あるセクションの末端が以下のよう
なコードであったとする。 処理１ ｂｒａｎｃｈ ｌａｂｅｌ 処理２ ｌａｂｅｌ： 処理３ 上記のコードは、処理１の結果によって、ｌａｂｅｌに
ジャンプして処理３を実行するか、そのまま処理２を実
行する、ということを表したコードである。ここで、処
理２の先頭に位置するセクションをセクション２、処理
３の先頭に位置するセクションをセクション３、とした
とき、上記コードは以下のように処理される。 処理１ ｂｒａｎｃｈ ｌａｂｅｌ ｓｅｃｔｉｏｎ−ｅｎｄ セクション２ ｌａｂｅｌ： 図１１２は図１０３における実行部４１５の詳細な構成
図を示す。図１１２において、実行セクション選択部１
２０１は、セクション情報及び実行セクション候補記憶
部１２０３に記憶される情報に基づき、次に実行すべき
セクションを１個又は複数選択する。実行セクション選
択部１２０１は、図示されない入力部から切替えること
が可能な２つのモード（逐次実行モードと並行実行モー
ド）を有する。逐次実行モードではセクションの選択は
１個である。並行実行モードではセクションの選択は一
般に複数となる。セクション実行部１２０２は、実行セ
クション選択部１２０１によって選択されたセクション
を実行する。特に、選択されたセクションが複数の場合
は並行に実行する。実行セクション候補記憶部１２０３
は、セクション実行部１２０２で実行した結果から決め
られる次の実行の候補となるセクションを記憶する。

【０３３８】図１１３は、実行部４１５における処理の
流れを示す図である。プログラムは、セクション情報記
憶部４１２に記憶されるセクションの情報及び実行順序
のルールに従って、セクション単位に実行される。

【０３３９】全体の初期化が行なわれる（ステップＰ
１）。この時、実行セクション候補記憶部１２０３には
最初に実行すべきセクションが記憶される。

【０３４０】次にセクション毎に実行を行なうループに
入る。このループの最初では、次に実行するセクション
の選択が、モードによって異なる方法で行なわれる（ス
テップＰ２）。逐次実行モードでは、実行セクション候
補記憶部１２０３に記憶される次に実行されるセクショ
ンの候補の中から実行順序のルールに従うものを１個選
択する（ステップＰ３）。一般に候補となるセクション
の中には、ルールに従うものが複数ある。これから１個
を選択する方法としては、例えば記憶された時間が最も
前のものを選択しても良いし、又は、固定された乱数列
に従って選択しても良い。ただし、ここでの選択方法と
しては再現性が保証される方法を用いる必要がある。プ
ログラムの実行のたびに選択される順序が変化しない
（すなわち再現性が保証されている）ことは本発明の重
要な動機の一つだからである。モードが並行実行モード
では、実行候補の中からルールに従うセクションをすべ
て選択する（ステップＰ４）。選択されたセクションは
一般に複数となる。

【０３４１】ステップＰ３又はステップＰ４において、
選択に失敗した場合は（ステップＰ５）、プログラムが
終了したか、実行順序を決めるルールの異常により失敗
した場合が考えられる。そこで、候補のリストを確かめ
（ステップＰ６）、候補が残っていないならば正常終了
（ステップＰ７）、残っているならば異常終了（ステッ
プＰ８）とする。異常終了の場合には、例えばデッドロ
ック状態が考えられ、この旨をユーザに提示することに
よりテスト・デバッグの指針とすることができる。ステ
ップＰ３及びステップＰ４において、選択に成功した時
は、選択されたセクションの実行をする（ステップＰ
９）。

【０３４２】複数のセクションが選択された時には、そ
れらのセクションは並行に実行される。この後セクショ
ン実行部４１５は、並行に実行されたセクションすべて
の実行の終了を待ってから、次のステップに進む。

【０３４３】なお、本実施例で使用しているセクション
の内部には、無限ループ等の実行時間を予測不可能にす
る因子は含まれていないため、セクションの実行終了を
永久に待ち続けるということはない。

【０３４４】実行が終了すると、まず終了したセクショ
ンが実行セクション候補記憶部１２０３から消去され、
次に実行結果に応じて次の実行候補となるセクションが
記憶される（ステップＰ１０）。「実行結果に応じて」
ということは例えばセクションの最後がｉｆ文のとき
は、計算結果によって次に分岐する分岐先、すなわち次
に実行するべきセクションが変わる、ということを意味
する。また、セクションがｅｎｄ文で終了するときは、
それを実行していたスレッドも終了するので、このスレ
ッドが次に実行すべきセクションは無いことになる。こ
の時は、実行セクション候補記憶部１２０３には何も記
憶されない。

【０３４５】実行セクション候補記憶部１２０３での記
憶内容の詳細な変化を説明する。図１１４は、プログラ
ムの一例をセクションの概念図を使って表した図であ
る。１本のスレッドがセクション１を実行し、その中の
ｆｏｒｋ文により２本のスレッドに分裂し、それぞれの
スレッドがセクション２とセクション４を実行し、ｊｏ
ｉｎ命令により同期をとって１本のスレッドに戻り、最
後にセクション３を実行して終了する例を示す。ここで
ｊｏｉｎ文により同期をとるために、セクション３はセ
クション４の後に実行されるというセクションの実行順
序に関するルールが、事前のプログラム解析により抽出
されているとする。

【０３４６】図１１５は上記の例を、逐次実行モードで
実行した時の実行セクション候補記憶部１２０３の変化
を示す図である。

【０３４７】初期状態１４０１では最初に実行されるセ
クション１が記憶されている。そこで、まずセクション
１が実行される。セクション１が実行されるとｆｏｒｋ
文によりスレッドが２本に分裂することから、次の実行
候補としてセクション２とセクション４の２セクション
が記憶される（状態１４０２）。ここで並行実行モード
であればセクション２とセクション４が同時に選択され
実行されるが、ここでは逐次実行モードで実行している
ため、どちらか１個が選択されなければならない。そこ
でセクション２を選択し、実行したとする。セクション
２が終了すると、次の候補としてのセクション３が記憶
される（状態１４０３）。

【０３４８】次に、候補を見る限りではセクション３と
セクション４のどちらを選択しても良さそうだが、先に
示した実行順序のルール「セクション３はセクション４
の後に実行される」により、セクション４しか選択する
ことができないので、セクション４が実行されることに
なる。セクション４の実行が終了すると、それを実行し
たスレッドが終了するため候補記憶部１２０３ではセク
ション４に続くセクションが無くなっている（状態１４
０４）。そして、セクション３を実行し全処理を終了し
たことになる（状態１４０５）。

【０３４９】本発明は、上記実施例に限定されない。

【０３５０】上記実施例は、それぞれ独立の実施例とし
て記載したが、それぞれ適宜組み合わせることにより、
より効果的な並行プログラムを作成することが可能にな
る。特に、実施例１〜実施例８において作成された並行
プログラムを実施例９の並行プログラム実行装置で実行
させてその妥当性を検証することも可能であるし、実施
例９において、ソースプログラムである並行プログラム
を並行プログラム実行装置で実行させて、実施例１〜実
施例８に示すように、実行情報（テスト・デバッグ情報
を含む）に基づいて、逐次プログラムを並行化する、或
いは、ソースプログラムをバグのない並行プログラムに
変換しても良い。

【０３５１】本実施例によれば、実行ログを意味を変え
ない範囲でユーザに理解し易い形に並べ替え、ユーザに
提示することができる。並べ替えても意味が変わらない
ことが保証されているので、オリジナルの実行ログにバ
グがある場合は、並べ替え後の実行ログにおいてもバグ
が存在する。この性質により、テスト・デバッグの効率
が向上するという効果が得られる。

【０３５２】（実施例１０）本実施例では、図２の逐次
化装置１２の具体的な実現法について述べる。図１１７
は逐次化装置１２の実施例を示すブロック図である。こ
の逐次化装置１２は、テスト実行装置１２１、第１実行
ログファイル記憶部１２２、解析装置１２３、先行関係
情報ファイル１２４、並べ替え装置１２５及び第２実行
ログファイル記憶部１２６からなる。

【０３５３】図１１８は図１１７の逐次化装置１２を用
いた場合の並行プログラム作成方法の概略手順を示すフ
ローチャートである。

【０３５４】（１） ステップＡ１：モデル化 対象の並行システムに対し、並行性を用いた自然なモデ
ル化を行う。また、各プロセス構造を決定する。更に、
該プロセス内を並行プログラム等を用いたプログラミン
グにより、ソースプログラムＣＰを記述する。このソー
スプログラムには、バグが潜在的に存在する可能性があ
る。図１１９は、こうして記述されたソースプログラム
ＣＰの具体例であり、２つのプロセスＰ１とＰ２をプロ
グラミングしている。

【０３５５】（２） ステップＱ１：実行 テスト実行装置１２１により、ソースプログラムＣＰを
実行し、実行ログを第１実行ログファイル記憶部１２２
に格納するとともに図２の出力装置５に表示する。この
例の場合、図１１９のソースプログラムＣＰに対する可
能な実行ログは数多く存在するが、ここでは、図１２０
のような実行ログが生成されたとする。しかし、この実
行ログはプロセスＰ１とプロセスＰ２が複雑に絡み合っ
ており、実行過程が把握しにくいものとなっている。

【０３５６】（３） ステップＱ２：バグの判定 テストの結果、バグがなければ終了する。テストの結果
バグがあれば、その実行ログ３を保存しステップＱ３に
進む。この例の場合、図１２０の実行ログが示す実行後
のＭの値は「Ｍ＝−１」であり、バグであると判定した
とする（期待した値は「Ｍ＝０」）。

【０３５７】（４） ステップＱ３：解析 解析装置１２３により、第１ＣＰファイル記憶部１１か
らのソースプログラムＣＰ及び第１実行ログファイル記
憶部１２２に格納された実行ログからプロセス間の先行
関係情報を抽出し、先行関係情報ファイル１２４に格納
する。図１２１に、図１１９の実行ログにおける２つの
プロセスＰ１とＰ２の各命令の先行関係を示す。

【０３５８】（５） ステップＱ４：実行ログの並べ替
え 第１実行ログファイル記憶部１２２と先行関係情報ファ
イル１２４に格納された実行ログ及び先行関係情報か
ら、並べ替え装置１２５によりユーザが理解しやすい順
序に並べ替えた実行ログを生成し、第２実行ログファイ
ル記憶部１２６に格納する。この例の場合、図１２１の
先行関係を満たす範囲で、ユーザが理解しやすい順序に
並べ替えた実行ログを生成する。具体的な並べ替え規則
の一例としては、（ａ）プロセスに優先順位を導入し、
その優先順位を用いて実行ログを並べ替える、（ｂ）待
ち状態が解除されたプロセスを優先して実行ログを並べ
替える （ｃ）ユーザが指定する、などがある。図１２２に、プ
ロセスに優先順位を導入して並べ替えた後の実行ログを
示す。

【０３５９】（６） ステップＱ５：実行ログの表示 第２実行ログファイル記憶部１２６に格納された並べ替
え後の実行ログを逐次プログラムとして出力し、かつ出
力装置５により表示してユーザに提示する。

【０３６０】この例では、図１２２に示す実行ログが出
力装置５で図１２２に示すように表示される。この実行
ログはプロセスＰ１とプロセスＰ２の命令が先行関係を
保つ範囲でまとまっており、ユーザにとって実行過程が
把握し易いものとなっている。

【０３６１】（７） ステップＱ６：並行プログラムの
デバッグ／修正 ユーザは出力装置５で表示された実行ログを見て実行過
程を把握又は実行を再現し、バグの原因を発見すればプ
ログラムを修正する。プログラムを修正したらステップ
Ｑ１に戻る。この例の場合、図１２２の実行ログの表示
から、ユーザは、バグの原因は「Ｐ２：read（Ｍ、
Ｙ);」と「Ｐ１：write(Ｍ、ＸＸ);」の順序が間違って
いることであると認識し、Ｐ２のｓｅｎｄ命令の場所を
修正することができる。修正されたプログラムは図１２
３のようになる。この修正後のプログラムを実行する
と、実行後のＭの値は「Ｍ＝０」となり、バグが削除で
きたことがわかる。

【０３６２】（実施例１１）本実施例では、テスト実行
は部分超逐次プログラムに対して行うが、ソースコード
の修正はオリジナルの並行プログラムに対して行う。ま
た、良い非決定性に関する情報の導入は、逐次化条件に
対して行い、良い非決定性の導入毎にオリジナルの並行
プログラムの逐次化（部分逐次化）を行う。

【０３６３】図１２４は、本実施例に係る並行プログラ
ム作成支援装置の概略構成を示す図である。同図におい
て、第１ＣＰファイル記憶部１１に格納されたソースプ
ログラムＣＰは、ユーザによる入力装置４からの指示に
より引き出され、逐次化装置１２に入力される。逐次化
装置１２に入力されたソースプログラムＣＰは、逐次化
ルール記憶部１３に格納された逐次化ルールに従って超
逐次プログラムＨＳＰ又は部分超逐次プログラムＰＨＳ
Ｐに変換され、ＨＳＰ／ＰＨＳＰファイル記憶部１４１
に記録される。

【０３６４】このプログラムＨＳＰ／ＰＨＳＰに対し
て、テスト実行装置１５でテストが行われる。ここで、
バグがあればデバッグ装置１６を用いて、第１ＣＰファ
イル記憶部１１に格納されているソースプログラムＣＰ
を修正する。修正されたソースプログラムＣＰは再度逐
次化され、超逐次プログラム（ＨＳＰ）又は部分超逐次
プログラム（ＰＨＳＰ）が生成されてＨＳＰ／ＰＨＳＰ
ファイル記憶部１４１に記録される。

【０３６５】この一連のサイクルを繰り返し、テスト・
デバッグが完了したならば、非決定性導入装置１７で、
逐次化ルール記憶部１３に格納されている逐次化ルール
の制約を緩めて、部分超逐次プログラムＰＨＳＰを生成
する。そして、この部分超逐次プログラムＰＨＳＰに対
して、同様のテスト・デバッグを繰り返しながら、非決
定性導入装置１７で、徐々に逐次化ルールの制約を弱め
ていく。このようにして良い非決定性導入が完了したな
らば、最終的に並行化装置１８で並行プログラムが生成
され、第２ＣＰファイル記憶部１９に格納される。

【０３６６】（実施例１２）本実施例では、テスト超逐
次プログラムに対して行うが、バグのあった場合はソー
スコードたる並行プログラムを修正せずに、逐次化ルー
ルを修正することでテスト・デバッグを行う。その他の
部分に関しては、基本的にこれまでの実施例と同じであ
る。

【０３６７】本実施例における並行プログラムの作成
は、以下のような手順によって実現される。図１２５
は、本実施例に係る並行プログラム作成方法の概略手順
を示すフローチャートである。

【０３６８】（１） ステップＡ１：モデル化 対象の並行システムに対し、並行性を用いた自然なモデ
ル化を行う。また、各プロセス構造を決定する。更に、
該プロセス内を並行プログラム等を用いたプログラミン
グにより、並行構造を有する並行プログラムをソースプ
ログラムとして記述する。このソースプログラムには、
バグが潜在的に存在する可能性がある。 （２） ステップＡ２：逐次化 ステップＡ１で得られた並行プログラムを所定の逐次化
ルールに基づいて超逐次プログラムに変換する。

【０３６９】（３） ステップＡ３：テスト・デバッグ ステップＡ２で変換された超逐次プログラムを実行して
テストを行い、機能面のバグがある場合は、超逐次プロ
グラムを修正してテスト・デバッグを行う。

【０３７０】（４） ステップＣ２：バグ判定 ステップＡ３のテストの結果、タイミング面のバグがあ
る場合は、ステップＪ１に移行する。いずれのバグもな
い場合は、その超逐次プログラムを保存しステップＡ４
に移行する。

【０３７１】（５） ステップＪ１：逐次化ルールの修
正 ステップＣ２でタイミング面のバグがあると判定された
場合は、逐次化ルールを修正し、ステップＡ２に戻る。

【０３７２】（６） ステップＡ４：良い非決定性の導
入 良い非決定性の追加が必要な場合は、ステップＪ１によ
り逐次化ルールを修正して新たな逐次化ルールを設定
し、ステップＡ２に戻る。良い非決定性の追加が必要で
ない場合は、ステップＡ７に移行する。

【０３７３】（７） ステップＡ７：並行化コンパイル 保存された超逐次プログラムの集合から、無害な非決定
性部分を抽出し、それを並行プログラムとして生成す
る。

【０３７４】図１２６は、本実施例に係る並行プログラ
ム作成支援装置の概略構成を示す図である。同図におい
て、第１ＣＰファイル記憶部１１に格納されているソー
スプログラムＣＰは、逐次化装置１２において逐次化ル
ール記憶部１３に格納された逐次化ルールに従って、メ
タレベルにおいてデフォルト逐次性が導入されることに
より、超逐次プログラム（ＨＳＰ）に変換され、ＨＳＰ
ファイル記憶部１４に記録される。ユーザは、この超逐
次プログラムＨＳＰを出力装置５によって見ることがで
きる。この超逐次プログラムＨＳＰは、ユーザによる入
力装置４からの指示によってテスト実行装置１５に入力
され、テスト実行が行われる。

【０３７５】テスト実行装置１５は、テスト実行の結果
（実行ログ）を出力装置５に提示する。ユーザは、この
テスト実行の結果に基づいて、逐次化ルール修正装置２
６を用いて逐次化ルール記憶部１３に格納されている逐
次化ルールを修正し、超逐次プログラムＨＳＰに対し所
定のテスト・デバッグを行うことができる。

【０３７６】ユーザは、このように逐次化ルールの修正
により超逐次プログラムＨＳＰに対して所定のテスト・
デバッグを行った後、入力装置４から再度テスト実行の
指示を与える。これにより、テスト・デバッグの行われ
た超逐次プログラムＨＳＰは、テスト実行装置１５に入
力され、再度テスト実行が行われる。このテスト・デバ
ッグは、超逐次プログラムＨＳＰが正常に動作すること
を確認するまで繰り返し行われる。

【０３７７】そして、本実施例ではテスト・デバッグに
より正常に動作することを確認した時点で、逐次化ルー
ル修正装置２６により逐次化ルール記憶部１３に格納さ
れている逐次化ルールが修正され、この修正の後の逐次
化ルールが逐次化ルール記憶部１３に新たに記録され
る。この逐次化ルールの修正によって、超逐次プログラ
ムに対して良い非決定性に関する情報が部分的に導入さ
れる。

【０３７８】その他本発明の要旨を変更しない範囲で種
々変形して実施できるのは勿論である。

【０３７９】

【発明の効果】本発明によれば次のような効果が得られ
る。

【０３８０】本発明では並行プログラムを一旦逐次化
し、逐次化したプログラムに対してテスト・デバッグを
行うことにより、従来の並行プログラムのプログラミン
グより遥かに容易な逐次プログラミングと同じレベルの
困難さで並行プログラムのテスト・デバッグが可能とな
る。

【０３８１】上記のグラフ情報によって並行化及び逐次
化の情報をユーザに対して同時に提示することにより、
ユーザは第１並行プログラムの並行構造を考慮しつつ、
良い非決定性部分の指定をすることができるようにな
る。また、並行プログラム記述レベルにおける良い非決
定性部分の指定・解除ではなく、グラフ情報に対して良
い非決定性部分を指定・解除を行うことでができるた
め、高度な並行プログラミング技術を必要とすることな
く、容易に並行プログラムの開発をすることができるよ
うになる。

【０３８２】第１並行プログラムを逐次プログラムに変
換する際、第１並行プログラム及びその実行ログを解析
し、この解析結果に基づいて実行ログを並べ替えるよう
にすれば、並べ替え後の実行ログを表示してユーザに提
示することによって、並行プログラムの実行過程の理解
が容易となり、テスト・デバッグの効率が向上する。逐
次プログラムに並行性に関する情報を導入する際、逐次
プログラムのプロセスの流れを制約と遷移条件からなる
フィールドに変換し、更にそのフィールドデータを表示
することによって、フィールドを対話的・視覚的に編集
することで並行性に関する情報を効果的に導入し、バグ
のない並行プログラムが効率的に作成される。

【０３８３】第１並行プログラムから逐次化された逐次
プログラムに対して並行化の候補となるプロセス群を指
定し、このプロセス群の実行順序を入れ換えて逐次プロ
グラムを複数の並行模擬プログラムに変換した後、これ
ら複数の並行模擬プログラムを部分的に逐次構造を有す
る１つの部分逐次プログラムに変換し、この部分逐次プ
ログラムを並行化して第２並行プログラムに変換するこ
とにより、部分逐次プログラム上で並行プログラムの動
作を十分に確認することができる。また、部分逐次プロ
グラムに対して並行化の候補となるプロセス群を指定す
ることで、逐次構造プログラムを段階的に並行プログラ
ムへ変換することができる。更に、並行模擬動作系列に
基づく逐次実行で正しく動作することが確認された非決
定性のみを許容する並行性に関する情報を導入すること
で、正しく動作する並行プログラムを得ることができ
る。これらによって、並行プログラムのテスト・デバッ
グが容易となる。

【０３８４】プロセス群がメッセージ情報を交換しなが
ら並行して動作する実行環境に用いられる並行プログラ
ムの作成を支援する並行プログラム作成支援装置におい
て、第１並行プログラムのプロセス群の実行履歴である
ログ情報を逐次化ルールとして取得して記憶し、このロ
グ情報を修正可能とするとともに、記憶されているログ
情報に基づいてこれに基づいてプロセス群を逐次的に起
動制御し、記憶されたログ情報を並行化して第２並行プ
ログラムに変換することにより、ソースプログラムとし
ての並行プログラムを修正することなく、ログ情報の修
正で処理タイミングの非決定性に起因する不具合を解決
できる。これにより、処理タイミングの非決定性が内在
する並行／並列／分散プログラムの開発が容易となる。
また、ユーザの意図する良い非決定性のみを容易に導入
することができるため、並行プログラムとしての柔軟
性、再利用性及び拡張性を維持することもできる。

【０３８５】プロセス群がメッセージ情報を交換しなが
ら並行して動作できる実行環境でプロセス群が実行順序
規定情報に従って動作するシステムにおいて、実行順序
規定情報を分割し、つまり並行プログラムを逐次化して
得られた全プロセスの集中ログ情報を各プロセス毎に分
割し、この分割された実行順序情報に基づいてプロセス
群を起動制御することにより、無害の非決定性を自然に
導入し、集中ログ情報に基づく逐次プログラムの実行時
と同一結果を高い処理効率で得ることが可能となる。

【０３８６】第１並行プログラムをテスト実行してその
テスト実行の結果、その１つであるバグのない実行ログ
を蓄積し、この蓄積されたバグのない実行ログのみを並
行化して第２並行プログラムに変換することにより、テ
ストで通過したタイミングだけを許容するようにプログ
ラムが動くようになるため、テストしなかったことで残
存したバグに陥ることを回避でき、信頼性が向上する。

【０３８７】本発明の並行プログラム実行装置によれば
並行プログラムの逐次又は部分並行実行を行なうことが
可能となるので、従来の逐次プログラムと同様に再現性
を保証することができ、効果的かつ安定したテスト・デ
バッグを行なうことができる。また、逐次実行から部分
並行実行に容易に切替えることができるため、逐次化し
てテスト・デバッグをおこなったプログラムを非決定性
に影響されない安全な並行実行を可能とする。他に、セ
クションの実行順序に関するルールを編集して実行時の
セクション間の同期を制御することにより、効果的なテ
スト・デバッグを行なえるとともにプログラムの効率化
の指針とすることもできる。

【図面の簡単な説明】

【図１】 本発明に係る並行プログラム作成支援装置を
実現するためのコンピュータシステムの構成図。

【図２】 実施例１に係る並行プログラム作成支援装置
の概略構成を示すブロック図。

【図３】 実施例１に係る並行プログラム作成方法の概
略手順を示すフローチャート。

【図４】 実施例１の動作説明のための並行プログラム
の一例と逐次化ルールを示す図。

【図５】 実施例１の動作説明のためのメタレベルのデ
フォルト逐次性が導入された超逐次プログラムの概念
図。

【図６】 実施例１の動作説明のためのデバッグ画面の
一例を示す図。

【図７】 実施例１の動作説明のための非決定性に関す
る情報の導入例を示す図。

【図８】 実施例２に係る並行プログラム作成支援装置
の概略構成を示すブロック図。

【図９】 実施例２に係る並行プログラム作成方法の概
略手順を示すフローチャート。

【図１０】 セクションの設定方法の一例を示す図。

【図１１】 逐次化方式の一例を示す図。

【図１２】 逐次化情報の書換ルール例を示す図。

【図１３】 並行プログラムの例を示す図。

【図１４】 並行プログラムの記載例を示す図。

【図１５】 それぞれ、超逐次プログラムのセクション
情報、プログラム構造情報、超逐次化情報を示す図。

【図１６】 良い並行性の導入を説明するための図。

【図１７】 自動並行化を行った逐次プログラミングか
ら生成された並行プログラムのソースコードを示す図。

【図１８】 超逐次プログラムのプログラム構造情報を
示す図。

【図１９】 超逐次プログラムの逐次化情報を示す図。

【図２０】 自動並行化された超逐次プログラムの処理
の流れを示す図。

【図２１】 実施例３に係る並行プログラム作成支援装
置の概略構成を示すブロック図。

【図２２】 実施例３に係る並行プログラム作成方法の
概略手順を示すフローチャート。

【図２３】 実施例３の動作説明のためのソースプログ
ラムである並行プログラムの一例を示す図。

【図２４】 実施例３における並行プログラム合成例を
示す図。

【図２５】 実施例４に係る並行プログラム作成法の概
略手順を示すフローチャート。

【図２６】 実施例４で用いるプロセステーブルを示す
図。

【図２７】 実施例４の動作説明のための並行プログラ
ムの一例を示す図。

【図２８】 図２７における並行プログラムの並行構造
を示す概念図。

【図２９】 実施例４で用いる並行プログラムの構造解
析の結果作成されるプロセステーブルを示す図。

【図３０】 実施例４で用いる超逐次グラフの一例を示
す図。

【図３１】 実施例４における超逐次グラフ生成装置の
動作処理を説明するための図。

【図３２】 実施例４における並行化部分の指定方法を
説明するための図。

【図３３】 実施例４における並行化部分指定後の超逐
次グラフの一例を示す図。

【図３４】 グループ化されたノードを持つ超逐次グラ
フの一例を示す図。

【図３５】 優先順位変更後の超逐次グラフの一例を示
す図。

【図３６】 ３プロセス間の良い非決定性部分の導入を
説明するための図。

【図３７】 良い非決定性部分の導入後の超逐次グラフ
を示す図。

【図３８】 実施例５に係る並行プログラム作成支援装
置の概略構成を示すブロック図。

【図３９】 実施例５の動作説明のためのソースプログ
ラムである並行プログラムを示す図。

【図４０】 図３９の並行プログラムで実行される処理
の流れを示す図。

【図４１】 実施例５における逐次化プロセスファイル
に格納されている逐次化プロセスの一例を示す図。

【図４２】 図４１の逐次化プロセスで実行される処理
の流れを示す図。

【図４３】 実施例５におけるフィールドデータ生成部
で実行される処理の流れを示すフローチャート。

【図４４】 図４３の処理により生成されるエリアのデ
ータ構造を示す図。

【図４５】 実施例５におけるフィールドデータ生成部
で生成されるフィールドデータの一例を示す図。

【図４６】 実施例５におけるフィールドチューニング
部で実行される処理の流れを示すフローチャート。

【図４７】 図４６の一部（ステップＥ９）を詳細に示
す図。

【図４８】 実施例５における制約変更操作によって起
こるフィールドの変化を示す図。

【図４９】 図４６の他の一部（ステップＥ１１）を詳
細に示す図。

【図５０】 実施例５における制約変更操作によって起
こるフィールドの変化を示す図。

【図５１】 図４６の更に他の一部（ステップＥ１３）
を詳細に示す図。

【図５２】 実施例５における制約変更操作によって起
こるフィールドの変化を示す図。

【図５３】 フィールドに矛盾を発生させる自明な制約
を検出する処理を示す図。

【図５４】 自明制約を含むフィールド例を示す図。

【図５５】 自明制約の検出例を示す図。

【図５６】 フィールドエディタの表示画面の例を示す
図。

【図５７】 フィールドエディタの表示画面の他の例を
示す図。

【図５８】 フィールドエディタの表示画面の更に他の
例を示す図。

【図５９】 実施例５におけるフィールドデータのチュ
ーニング過程の様子示す図。

【図６０】 実施例５におけるフィールドデータのチュ
ーニング過程の様子示す図。

【図６１】 実施例５におけるフィールドデータのチュ
ーニング過程の様子示す図。

【図６２】 実施例５におけるフィールドデータのチュ
ーニング過程の様子示す図。

【図６３】 実施例５におけるフィールドデータのチュ
ーニング過程の様子示す図。

【図６４】 実施例５におけるフィールドデータのチュ
ーニング過程の様子示す図。

【図６５】 実施例５におけるフィールドデータのチュ
ーニング過程の様子示す図。

【図６６】 実施例５におけるフィールドデータのチュ
ーニング過程の様子示す図。

【図６７】 実施例５におけるフィールド変換部で実行
される処理を示すフローチャート。

【図６８】 実施例５における修正後の並行プログラム
の一例を示す図。

【図６９】 図６８の並行プログラムで実行されるプロ
セスの流れをイメージした図。

【図７０】 実施例６に係る並行プログラム作成支援装
置の概略構成を示す図。

【図７１】 実施例７に係る並行プログラム作成方法の
概略手順を示すフローチャート。

【図７２】 実施例７の動作説明のためのユーザが想定
した並行プログラムモデルの一例を示す図。

【図７３】 図７２の並行プログラムから得られる超逐
次プログラムの実行系列をモデル化した例を示す図。

【図７４】 実施例７における超逐次プログラムから部
分並行プログラムへの変換手順を示すフローチャート。

【図７５】 実施例７における超逐次プログラムから部
分並行プログラムへの変換例を示す図。

【図７６】 実施例７における超逐次プログラムから部
分並行プログラムへの変換例を示す図。

【図７７】 実施例７における超逐次プログラムから部
分並行プログラムへの変換例を示す図。

【図７８】 実施例７における超逐次プログラムから部
分並行プログラムへの変換例を示す図。

【図７９】 実施例８に係るプロセス間の情報交換の一
例を示す図。

【図８０】 実施例８に係る並行プログラム作成支援装
置の概略構成を示すブロック図。

【図８１】 実施例８に係る並行プログラム作成方法の
概略手順を示すフローチャート。

【図８２】 実施例８におけるメッセージの実行履歴で
あるログ情報の一例を示す図。

【図８３】 実施例８に係るログ情報に基づく並行プロ
グラムデバッグ装置の概略構成を示すブロック図。

【図８４】 実施例８におけるメッセージフォーマット
の一例を示す図。

【図８５】 実施例８におけるプロセス間情報交換を示
す図。

【図８６】 実施例８におけるログ情報の一例を示す
図。

【図８７】 実施例８におけるプロセス群制御部の処理
手順を示すフローチャート。

【図８８】 実施例８におけるログ情報を修正するため
に入れ替え対象を指示している一例を示す図。

【図８９】 実施例８における修正後のログ情報の一例
を示す図。

【図９０】 実施例８におけるログ情報に良い非決定性
を導入するためにその対象箇所を指定している一例を示
す図。

【図９１】 実施例８における良い非決定性導入後のロ
グ情報の一例を示す図。

【図９２】 実施例８におけるログ情報に基づく並行プ
ログラム実行システムの構成を示す図。

【図９３】 実施例８におけるタスク間情報交換を示す
図。

【図９４】 実施例８における良い非決定性を導入した
場合のログ情報の一例を示す図。

【図９５】 実施例８におけるタスク制御部の処理手順
を示すフローチャート。

【図９６】 実施例８におけるタスク制御部を起動する
ための一手段であるプログラム例を示す図。

【図９７】 実施例８におけるメッセージフォーマット
を示す図。

【図９８】 実施例８におけるタスク制御部の処理手順
を示すフローチャート。

【図９９】 実施例８における各タスクの構成例を示す
図。

【図１００】 セクションの概念を示す図。

【図１０１】 セクションの融合を示す概念図。

【図１０２】 セクションの分割を示す概念図。

【図１０３】 本発明の実施例９の概略構成を示す図。

【図１０４】 セクションを記憶するためのデータ構造
を示す図。

【図１０５】 セクション管理テーブルの構造を示す
図。

【図１０６】 部品テーブルの構造を示す図。

【図１０７】 セクションの実行順序のルールを説明す
るための図。

【図１０８】 プログラム解析部の詳細構成を示す図。

【図１０９】 プログラム解析の流れを示すフローチャ
ート。

【図１１０】 セクション情報編集部の詳細構成を示す
図。

【図１１１】 コンパイル部の詳細構成を示す図。

【図１１２】 実行部の詳細構成を示す図。

【図１１３】 実行部の処理の流れを示すフローチャー
ト。

【図１１４】 実行セクション候補記憶部の変化を説明
するための図。

【図１１５】 実行セクション候補記憶部の変化を示す
図。

【図１１６】 従来技術の問題点を説明するための図。

【図１１７】 実施例１０に係る逐次化装置の構成を示
すブロック図。

【図１１８】 実施例１０に係る並行プログラム作成方
法の概略手順を示すフローチャート。

【図１１９】 実施例１０の動作説明のためのソースプ
ログラムである並行プログラムの一例を示す図。

【図１２０】 実施例１０の動作説明のための図１１９
の並行プログラムの実行ログを示す図。

【図１２１】 実施例１０の動作説明のための並行プロ
グラムの先行関係を示す図。

【図１２２】 実施例１０の動作説明のための並行プロ
グラムの実行ログの並べ替えた後の状態を示す図。

【図１２３】 実施例１０の動作説明のための修正後の
並行プログラムの一例を示す図。

【図１２４】 実施例１１に係る並行プログラム作成支
援装置の概略構成を示す図。

【図１２５】 実施例１２に係る並行プログラム作成方
法の概略手順を示すフローチャート。

【図１２６】 実施例１２に係る並行プログラム作成支
援装置の概略構成を示すブロック図。

【符号の説明】

１〜１〜１−Ｎ…プロセッサ ２…Ｉ／Ｏインタフェ
ース ３…共有メモリ ４…入力装置 ５…出力装置 ６…記憶装置 １１…第１ＣＰファイル記憶部 １２…逐次化装置 １３…逐次化ルール記憶部 １４…ＨＳＰファイル
記憶部 １５…テスト実行装置 １６…デバッグ装置 １７…非決定性導入装置 １８…並行化装置 １９…第２ＣＰファイル記憶部 ２０…解析情報記憶部 ２１…並行化ルール記
憶部 ２２…実行装置 ２３…分割基準指定装
置 ２５…変更装置 ２６…逐次化ルール修
正装置 ３１…逐次化情報記憶部 ３２…逐次化情報読込
部 ３３…並行構造解析部 ３４…逐次構造解析部 ３５…画像データ生成部 ５１…逐次化プロセスリスト記憶部 ５２…フィールドデータ記憶部 ５３…フィールドデー
タ生成部 ５４…フィールドチューニング部 ５５…フィールドエディタ ２０１…ログ情報記憶部 ２０２…ログ情報取得
部 ２０３…プロセス群制御部 ２０４…メッセージ保
存部 ２０５…ログ情報修正部 ３０１…集中ログ情報記憶部 ３０２…ログ情報分割
部 ３０３…分割基準指定部 ３０４…分割ログ情報
記憶部 ３０５…プロセス制御部 ３０６…処理待ちメッ
セージ保存部 ４０１…テスト実行装置 ４０２…テストケース
記憶部 ４０３…実行ログ記憶部 ４０４…実行ログデー
タベース ４１１…プログラム解析部 ４１２…セクション情
報記憶部 ４１３…セクション情報編集部 ４１４…コンパイル部 ４１５…実行部

───────────────────────────────────────────────────── フロントページの続き (72)発明者 關 俊文 神奈川県川崎市幸区柳町70番地 株式会社 東芝柳町工場内 (72)発明者 永井 保夫 神奈川県川崎市幸区柳町70番地 株式会社 東芝柳町工場内 (72)発明者 半田 恵一 神奈川県川崎市幸区柳町70番地 株式会社 東芝柳町工場内 (72)発明者 伊藤 聡 神奈川県川崎市幸区柳町70番地 株式会社 東芝柳町工場内 (72)発明者 澤島 信介 神奈川県川崎市幸区小向東芝町１番地 株 式会社東芝研究開発センター内 (72)発明者 田原 康之 神奈川県川崎市幸区柳町70番地 株式会社 東芝柳町工場内 (72)発明者 塩谷 英明 神奈川県川崎市幸区柳町70番地 株式会社 東芝柳町工場内

Claims (50)

【特許請求の範囲】
1. 【請求項１】並行構造を有する第１並行プログラムを逐
   次実行可能な逐次プログラムに変換する逐次化手段と、 前記逐次プログラムのテスト・デバッグを行い、テスト
   ・デバッグ情報を作成するテスト・デバッグ手段と、 テスト・デバッグ後の前記逐次プログラムを前記テスト
   ・デバッグ情報に基づいて並行化することにより第２並
   行プログラムに変換する並行化手段と、を具備すること
   を特徴とする並行プログラム作成支援装置。
2. 【請求項２】 前記テスト・デバッグ手段は、前記逐次
   プログラムに対して並行性に関する情報を導入する手段
   を含むことを特徴とする請求項１記載の並行プログラム
   作成支援装置。
3. 【請求項３】 前記逐次プログラムは、セクション情報
   と、プログラム構造情報と、逐次化情報とを含むことを
   特徴とする請求項１記載の並行プログラム作成支援装
   置。
4. 【請求項４】 前記第１並行プログラムの並行構造を解
   析する解析手段を更に具備し、前記並行化手段は、前記
   テスト・デバッグ手段によりテスト・デバッグが行われ
   た前記逐次プログラムを前記解析手段の解析結果を用い
   て並行化して、第２並行プログラムに変換する手段を含
   むことを特徴とする請求項１記載の並行プログラム作成
   支援装置。
5. 【請求項５】並行構造を有する第１並行プログラムの所
   定のセクション群を逐次実行可能な逐次プログラムに変
   換する逐次化手段と、 前記第１並行プログラムの所定のセクション群の並行構
   造を解析する並行構造解析手段と、 前記逐次プログラムの所定のセクション群の逐次構造を
   解析する逐次構造解析手段と、 前記並行構造解析手段で解析された並行構造に関する相
   互関係及び前記逐次構造解析手段で解析された逐次構造
   に関する相互関係をグラフ情報として表示するグラフ情
   報表示手段と、 前記逐次プログラムのうち選択された所定のセクション
   群を並行化して部分的に逐次構造を有する部分逐次プロ
   グラムに変換する部分逐次化手段と、 前記部分逐次プログラムを並行化して第２並行プログラ
   ムに変換する並行化手段と、を具備することを特徴とす
   る並行プログラム作成支援装置。
6. 【請求項６】 前記逐次化手段は、 前記第１並行プログラムを実行する実行手段と、 前記実行手段による実行ログを保存する保存手段と、 前記保存手段により保存された実行ログ及び前記第１並
   行プログラムを解析する解析手段と、 前記保存手段により保存された実行ログを前記解析手段
   による解析結果に基づいて並べ替えする並べ替え手段
   と、を含むことを特徴とする請求項１ないし請求項５の
   いずれかに記載の並行プログラム作成支援装置。
7. 【請求項７】 前記実行手段は、 前記第１並行プログラムを解析してセクション情報の抽
   出をおこなうプログラム解析手段と、 前記セクション情報を記憶するセクション情報記憶手段
   と、 前記セクション情報記憶手段に記憶されたセクション情
   報を変更するセクション情報変更手段と、 前記セクション情報記憶手段により記憶されたセクショ
   ン情報に基づいて前記並行プログラムの実行を行なう並
   行プログラム実行手段と、を含むことを特徴とする請求
   項６記載の並行プログラム作成支援装置。
8. 【請求項８】 前記導入手段は、 前記逐次プログラムのプロセスの流れを制約と遷移条件
   からなるフィールドに変換して該フィールドを表すフィ
   ールドデータを生成するフィールドデータ生成手段と、 前記手段により生成されたフィールドデータで表される
   フィールドをチューニングするためのチューニング手段
   と、 前記フィールドデータ生成手段により生成されたフィー
   ルドデータで表されるフィールドを表示する表示手段
   と、含むことを特徴とする請求項１ないし請求項５のい
   ずれかに記載の並行プログラム作成支援装置。
9. 【請求項９】前記逐次化手段は、前記第１並行プログラ
   ムを複数の超逐次プログラムに変換する手段を含み、 前記テスト・デバッグ手段は、前記複数の超逐次プログ
   ラムを独立にテスト・デバッグする手段を含むことを特
   徴とする請求項１ないし請求項４のいずれかに記載の並
   行プログラム作成支援装置。
10. 【請求項１０】並行構造を有する第１並行プログラムの
    所定のプロセス群を所定の実行順序に従って逐次実行可
    能な逐次プログラムに変換する逐次化手段と、 前記逐次構造プログラムに対して並行化の候補となるプ
    ロセス群を指定するプロセス群指定手段と、 前記手段により指定されたプロセス群の実行順序を入れ
    換えて前記逐次プログラムを複数の並行模擬プログラム
    に変換する模擬並行プログラム変換手段と、 前記複数の並行模擬プログラムを部分的に逐次構造を有
    する１つの部分逐次プログラムに変換する部分逐次化手
    段と、 前記部分逐次プログラムを並行化して第２並行プログラ
    ムに変換する並行化手段とを具備することを特徴とする
    並行プログラム作成支援装置。
11. 【請求項１１】逐次化ルールを格納する逐次化ルール格
    納手段と、 前記逐次化ルール格納手段に格納された逐次化ルールに
    従って並行構造を有する第１並行プログラムを逐次実行
    可能な逐次プログラムに変換する逐次化手段と、 前記逐次プログラムに対して並行性に関する情報を導入
    すべく前記逐次化ルール格納手段に格納された逐次化ル
    ールを修正する逐次化ルール修正手段と、 前記逐次プログラムのテスト・デバッグを行うためのテ
    スト・デバッグ手段と、 前記逐次化ルール修正手段により並行性に関する情報が
    導入されかつ前記テスト・デバッグ手段によりテスト・
    デバッグが行われた逐次プログラムを並行化して第２並
    行プログラムに変換する並行化手段と、を具備すること
    を特徴とする並行プログラム作成支援装置。
12. 【請求項１２】 プロセス群がメッセージ情報を交換し
    ながら並行して動作する実行環境に用いられる並行プロ
    グラムの作成を支援する並行プログラム作成支援装置に
    おいて、 第１並行プログラムのプロセス群の実行履歴であるログ
    情報を逐次化ルールとして取得するログ情報取得手段
    と、 前記ログ情報取得手段により取得されたログ情報を記憶
    するログ情報記憶手段と、 前記ログ情報記憶手段に記憶されているログ情報を修正
    するためのログ情報修正手段と、 前記ログ情報記憶手段に記憶されているログ情報に基づ
    いて前記プロセス群を逐次的に起動制御するプロセス群
    制御手段と、 前記ログ情報記憶手段に記憶されたログ情報を並行化し
    て第２並行プログラムに変換する並行化手段と、を具備
    することを特徴とする並行プログラム作成支援装置。
13. 【請求項１３】 前記ログ情報修正手段は、 前記ログ情報記憶手段に記憶されているログ情報を時系
    列に表示する表示手段と、 前記表示手段により時系列に表示されたログ情報内のデ
    ータの順序の入れ換えを指示するための入れ替え指示手
    段と、 前記入れ替え指示手段による指示に従って前記ログ情報
    記憶手段に記憶されているログ情報を書き換える書換手
    段と、を含むことを特徴とする請求項１２記載の並行プ
    ログラム作成支援装置。
14. 【請求項１４】 前記ログ情報修正手段は、プロセス間
    の処理タイミングの非決定性を導入する非決定性導入手
    段を含むことを特徴とする請求項１２記載の並行プログ
    ラム作成支援装置。
15. 【請求項１５】 プロセス群がメッセージ情報を交換し
    ながら並行して動作できる実行環境で前記プロセス群が
    実行順序規定情報に従って動作する並行プログラムを作
    成支援する並行プログラム作成支援装置において、 前記実行順序規定情報を分割する実行順序情報分割手段
    と、 前記実行順序情報分割手段によって分割された実行順序
    情報に基づいて前記プロセスを起動制御するプロセス制
    御手段と、を具備することを特徴とする並行プログラム
    作成支援装置。
16. 【請求項１６】 前記実行順序規定情報を分割するため
    の基準を与える分割基準指定手段を保持する手段を更に
    具備することを特徴とする請求項１５記載の並行プログ
    ラム作成支援装置。
17. 【請求項１７】 前記プロセス制御手段は、前記メッセ
    ージ交換の実行履歴であるログ情報を実行順序規定情報
    として用いるとともに、前記分割基準指定手段における
    分割基準として前記メッセージ中の宛先プロセス情報を
    基準として用いることを特徴とする請求項１５記載の並
    行プログラム作成支援装置。
18. 【請求項１８】 前記プロセス制御手段を各プロセス毎
    に保持する手段を具備することを特徴とする請求項１７
    記載の並行プログラム作成支援装置。
19. 【請求項１９】 前記実行順序情報分割手段によって分
    割された実行順序情報をそれぞれ別々に保存する分割実
    行順序情報保存手段を更に具備し前記プロセス制御手段
    は該プロセスに対応する分割実行順序情報保存手段に保
    存されている分割実行順序情報に基づいてプロセスを起
    動制御する手段を含むことを特徴とする請求項１８記載
    の並行プログラム作成支援装置。
20. 【請求項２０】 前記プロセス制御手段は、前記プロセ
    ス群の実行履歴であるログ情報を前記実行順序規定情報
    として用いることを特徴とする請求項１５記載の並行プ
    ログラム作成支援装置。
21. 【請求項２１】並行構造を有する第１並行プログラムを
    逐次的にテスト実行する逐次的テスト実行手段と、 前記テスト実行手段によるテスト実行の結果、正常に実
    行終了したテスト実行結果のバグのない逐次的実行ログ
    を蓄積する実行ログ蓄積手段と、 前記実行ログ蓄積手段により蓄積された逐次的実行ログ
    を並行化して第２並行プログラムに変換する並行化手段
    と、を具備することを特徴とする並行プログラム作成支
    援装置。
22. 【請求項２２】並行構造を有する第１並行プログラムを
    テスト実行するテスト実行手段と、 前記テスト実行手段によるテスト実行の結果バグのない
    実行ログを蓄積する第１の実行ログ蓄積手段と、 前記テスト実行手段によるテスト実行の結果バグのある
    実行ログを蓄積する第２の実行ログ蓄積手段と、 前記第２の実行ログ蓄積手段により蓄積された実行ログ
    を修正し、修正された実行ログを前記第１の実行ログ蓄
    積手段に蓄積する修正手段と、 前記第１の実行ログ蓄積手段により蓄積された実行ログ
    を並行化して第２並行プログラムに変換する並行化手段
    と、を具備することを特徴とする並行プログラム作成支
    援装置。
23. 【請求項２３】並行構造を有する第１並行プログラムを
    逐次実行可能な逐次プログラムに変換する第１ステップ
    と、 前記逐次プログラムのテスト・デバッグを行い、テスト
    ・デバッグ情報を作成する第２ステップと、 テスト・デバッグ後の前記逐次プログラムを前記テスト
    ・デバッグ情報に基づいて並行化することにより第２並
    行プログラムに変換する第３ステップと、を具備するこ
    とを特徴とする並行プログラム作成方法。
24. 【請求項２４】 前記第２ステップは、前記逐次プログ
    ラムに対して並行性に関する情報を導入するサブステッ
    プを含むことを特徴とする請求項２３記載の並行プログ
    ラム作成方法。
25. 【請求項２５】前記第１ステップは、前記第１並行プロ
    グラムの並行構造を解析するサブステップを含み、 前記第３ステップは、テスト・デバッグ後の前記逐次プ
    ログラムを前記第１並行プログラムの並行構造を用いて
    並行化するサブステップとを含むことを特徴とする請求
    項２３記載の並行プログラム作成方法。
26. 【請求項２６】 前記第２ステップは、前記逐次プログ
    ラムに対して指定された非決定性を前記並行性に関する
    情報として導入するサブステップを含むことを特徴とす
    る請求項２３ないし請求項２５のいずれかに記載の並行
    プログラム作成方法。
27. 【請求項２７】前記第１ステップは、 並行構造を有する前記第１並行プログラムの所定のセク
    ション群を逐次実行可能な逐次プログラムに変換する第
    １サブステップと、 前記第１並行プログラムの所定のセクション群の並行構
    造を解析する第２サブステップと、 前記逐次プログラムの所定のセクション群の逐次構造を
    解析する第３サブステップと、 前記第２サブステップで解析された並行構造に関する相
    互関係及び前記第３サブステップで解析された逐次構造
    に関する相互関係をグラフ情報として表示する第４サブ
    ステップと、 前記逐次プログラムのうち選択された所定のセクション
    群を並行化して部分的に逐次構造を有する部分逐次プロ
    グラムに変換する第５サブステップと、を含み、 前記第３ステップは、前記部分逐次プログラムを並行化
    して第２並行プログラムに変換するサブステップを含む
    ことを特徴とする請求項２３記載の並行プログラム作成
    方法。
28. 【請求項２８】並行構造を有する前記第１並行プログラ
    ムの所定のセクション群を逐次実行可能な逐次プログラ
    ムに変換する第１ステップと、 前記第１並行プログラムの所定のセクション群の並行構
    造を解析する第２ステップと、 前記逐次プログラムの所定のセクション群の逐次構造を
    解析する第３ステップと、 前記第２ステップで解析された並行構造に関する相互関
    係及び前記第３ステップで解析された逐次構造に関する
    相互関係をグラフ情報として表示する第４ステップと、 前記逐次プログラムのうち選択された所定のセクション
    群を並行化して部分的に逐次構造を有する部分逐次プロ
    グラムに変換する第５ステップと、 前記部分逐次プログラムを並行化して第２並行プログラ
    ムに変換する第６ステップと、を具備することを特徴と
    する並行プログラム作成方法。
29. 【請求項２９】前記第１サブステップは、前記逐次プロ
    グラムの所望の実行結果が得られるまで当該逐次プログ
    ラムのテスト・デバッグを行うサブステップを含むこと
    を特徴とする請求項２８記載の並行プログラム作成方
    法。
30. 【請求項３０】 前記第４サブステップは、前記所定の
    セクション群をノードとし、前記並行構造に関する相互
    関係を第１アークとし、前記逐次構造に関する相互関係
    を第２アークとして前記グラフ情報を表示するサブステ
    ップを含むことを特徴とする請求項２８記載の並行プロ
    グラム作成方法。
31. 【請求項３１】 前記第５サブステップは、前記部分逐
    次プログラムの所望の実行結果が得られるまで該部分逐
    次プログラムのテスト・デバッグを行うサブステップを
    含むことを特徴とする請求項２８記載の並行プログラム
    作成方法。
32. 【請求項３２】前記第５サブステップは、前記部分逐次
    プログラムにおける所定のセクション群の逐次構造を解
    析するサブステップを含み、 前記第１ステップは、前記第４サブステップから第５サ
    ブステップを所定の回数繰り返すサブステップを更に含
    むことを特徴とする請求項２８記載の並行プログラム作
    成方法。
33. 【請求項３３】前記第１ステップは、 前記第１並行プログラムを実行する第１サブステップ
    と、 前記第１サブステップによる実行ログを保存する第２サ
    ブステップと、 前記第２サブステップにより保存された実行ログ及び前
    記第１並行プログラムを解析する第３サブステップと、 前記第２サブステップにより保存された実行ログを前記
    第３サブステップによる解析結果に基づいて並べ替える
    第４サブステップと、を含むことを特徴とする請求項２
    ３ないし請求項２５、請求項２８又は請求項２９のいず
    れかに記載の並行プログラム作成方法。
34. 【請求項３４】 前記第３サブステップは、前記第２サ
    ブステップにより保存された実行ログ及び前記第１並行
    プログラムからプロセスの先行関係を抽出し先行関係情
    報として保存するサブステップを含むことを特徴とする
    請求項３３記載の並行プログラム作成方法。
35. 【請求項３５】 前記第２ステップは、前記逐次プログ
    ラムのプロセスの流れを制約と遷移条件からなるフィー
    ルドに変換するサブステップと、前記フィールドをチュ
    ーニングするサブステップと、前記並行性に関する情報
    を導入するサブステップとを含むことを特徴とする請求
    項２３ないし請求項２５のいずれかに記載の並行プログ
    ラム作成方法。
36. 【請求項３６】複数のプロセス群を有し並行構造を有す
    る第１並行プログラムの所定のプロセス群を所定の実行
    順序に従って逐次実行可能な逐次プログラムに変換する
    第１ステップと、 前記逐次プログラムに対して並行化の候補となるプロセ
    ス群を指定する第２ステップと、 前記第２ステップにより指定されたプロセス群の実行順
    序を入れ換えて前記逐次プログラムを複数の並行模擬プ
    ログラムに変換する第３ステップと、 前記複数の並行模擬プログラムを部分的に逐次構造を有
    する１つの部分逐次プログラムに変換する第４ステップ
    と、 前記部分逐次プログラムを並行化して第２並行プログラ
    ムに変換する第５ステップと、を具備することを特徴と
    する並行プログラム作成方法。
37. 【請求項３７】 前記第１ステップは、前記逐次プログ
    ラムの所望の実行結果が得られるまで該逐次プログラム
    のテスト・デバッグを行うサブステップを含むことを特
    徴とする請求項３６記載の並行プログラム作成方法。
38. 【請求項３８】 前記第２ステップは、 前記第１並行プログラムを解析するサブステップと、 前記解析結果から前記並行化の候補となるプロセス群を
    抽出するサブステップと、を含むことを特徴とする請求
    項３６記載の並行プログラム作成方法。
39. 【請求項３９】 前記第３ステップは、前記複数の並行
    模擬プログラムの所望の実行結果が得られるまで前記複
    数の並行模擬プログラムのテスト・デバッグを行うサブ
    ステップを含むことを特徴とする請求項３６記載の並行
    プログラム作成方法。
40. 【請求項４０】 前記第３ステップは、前記複数の並行
    模擬プログラムの一部の実行結果から不要と判断される
    並行模擬プログラムを取り除くサブステップを含むこと
    を特徴とする請求項３６記載の並行プログラム作成方
    法。
41. 【請求項４１】 前記第４ステップは、前記部分逐次プ
    ログラムに対して並行化の候補となるプロセス群を指定
    するサブステップを含み、 前記第３ステップから前記第４ステップを所定の回数繰
    り返すステップを更に具備することを特徴とする請求項
    ３６記載の並行プログラム作成方法。
42. 【請求項４２】 前記第１ステップは、 前記第１並行プログラムを逐次化ルールに従って前記逐
    次プログラムに変換する第１サブステップと、 前記逐次プログラムに対して並行性に関する情報を導入
    するために前記逐次化ルールを修正する第２サブステッ
    プと、を含み、 前記第３ステップは、前記テスト・デバッグ情報と、前
    記並行性に関する情報とに基づいて前記逐次プログラム
    を並行化して第２並行プログラムに変換するサブステッ
    プを含むことを特徴とする請求項２３記載の並行プログ
    ラム作成方法。
43. 【請求項４３】並行構造を有する第１並行プログラムを
    テスト実行する第１ステップと、 前記第１ステップによるテスト実行の結果バグのない実
    行ログを蓄積する第２ステップと、 前記第２ステップにより蓄積された前記実行ログを並行
    化して第２並行プログラムに変換する第３ステップと、
    を具備することを特徴とする並行プログラム作成方法。
44. 【請求項４４】前記第１ステップによるテスト実行の結
    果バグのある実行ログを蓄積する第４ステップと、 前記第４ステップにより蓄積された実行ログに基づいて
    前記第１並行プログラムを修正して、再度実行ログを蓄
    積する第５ステップと、を更に具備することを特徴とす
    る請求項４３記載の並行プログラム作成方法。
45. 【請求項４５】並行プログラムを解析してセクション情
    報の抽出をおこなうプログラム解析手段と、 前記セクション情報を記憶するセクション情報記憶手段
    と、 前記セクション情報記憶手段により記憶されたセクショ
    ン情報に基づいて前記並行プログラムの実行を行なう並
    行プログラム実行手段と、を具備することを特徴とする
    並行プログラム実行装置。
46. 【請求項４６】 前記セクション情報記憶手段によって
    記憶されるセクション情報を編集するセクション情報編
    集手段及び前記セクション情報記憶手段によって記憶さ
    れるセクション情報内の各セクションをオブジェクトに
    変換するコンパイル手段の少なくとも一方を更に具備す
    ることを特徴とする請求項４５記載の並行プログラム実
    行装置。
47. 【請求項４７】 前記プログラム解析手段が、入力され
    たプログラムを中間言語に変換する手段と、前記中間言
    語からセクションを抽出する手段とを更に含むことを特
    徴とする請求項４５記載の並行プログラム実行装置。
48. 【請求項４８】 前記実行手段が、実行するセクション
    の候補を記憶する実行セクション候補記憶手段と、前記
    実行セクション候補記憶手段によって記憶されるセクシ
    ョンから次に実行するセクションを選択する実行セクシ
    ョン選択手段と、前記実行セクション選択手段によって
    選択されたセクションを実行するセクション実行手段と
    を更に含むことを特徴とする請求項４５記載の並行プロ
    グラム実行装置。
49. 【請求項４９】 前記実行セクション選択手段が、実行
    可能なセクションを一つ選択するモードと実行可能なセ
    クションをすべて選択するモードを含むことを特徴とす
    る請求項４８記載の並行プログラム実行装置。
50. 【請求項５０】 前記実行セクション実行手段が、前記
    実行セクション選択手段によって選択されたセクション
    が複数の時はそれらのセクションを並行に実行すること
    を特徴とする請求項４８記載の並行プログラム実行装
    置。