(57)【要約】検証言語を合成するための方法であって、それにより検証言語を目的言語にコンパイルすることを可能にする方法。この方法は、検証言語の基礎を成す制御構造を決定し、次いで検証言語の動的挙動を静的枠組の一部として目的言語にマップすることを可能にするために使用される。何らかの型の検証言語を合成するプロセスは、ソフトウェアプログラムの暗黙の制御構造の少なくとも一部分をコンパイル済み出力コードに構築させるので、追加スケジューラまたは他の型の実行時システムを必要としない。したがって、コンパイル済み出力コードは、検証言語自体で書かれたソフトウェアプログラムより高い実行速度を持つはずであり、かつ、より効率的に動作するはずである。【特許請求の範囲】
【請求項１】
第１言語で書かれたコードを第２目的言語に少なくとも半自動的に翻訳する方法であって、第１言語は構造制約条件を特徴としかつ動的挙動を特徴とし、第１言語はオブジェクトの階層を特徴とし、かくしてオブジェクト間の関係は制約によって決定される方法において、
第１言語のコードの基礎を成す制御構造を検出するステップと、
第１言語で書かれたコードの動的挙動をサポートするために資源の静的枠組を形成するステップと、
前記資源の静的枠組および前記基礎を成す制御構造に従って動的挙動を第２目的言語にマップするステップと
を含む方法。
【請求項２】
前記基礎を成す制御構造は、制御フロー解析によってアクションについて検出され、前記アクションを実行させるために条件およびトリガのうちの少なくとも１つを決定する請求項１記載の方法。
【請求項３】
前記条件およびトリガのうちの少なくとも１つは、前記アクションの実行を支配するためのガードであり、かくして制御フロー解析は各アクションに対して少なくとも１つのガードを少なくとも決定することを含む請求項２記載の方法。
【請求項４】
前記制御フロー解析は、逐次制御フローグラフを作成するために複数のガードを決定することをさらに含む請求項３記載の方法。
【請求項５】
第１言語のコードの基礎を成す制御構造は、
コードを構文解析すること、
抽象構文ツリーを作成すること
によって検出される請求項４記載の方法であって、
前記逐次制御グラフの少なくとも１つのノードは、前記抽象構文ツリーのノードへの参照を保持している方法。
【請求項６】
前記制御フロー解析は、
各プロセスのトリガ構造を計算すること、
前記プロセスの各アクションに対して前記少なくとも１つのガードを決定すること、
前記プロセスの複数のセグメントへのセグメント化を決定すること
を含む請求項４記載の方法。
【請求項７】
前記制御フロー解析は、少なくとも１つのループを展開することをさらに含む請求項６記載の方法。
【請求項８】
少なくとも１つのアクションをリタイミングすることをさらに含む請求項６記載の方法。
【請求項９】
各ノードは、時間がかからないアクションのリストを表わす基本ノード、分岐点を表すガードノード、および時相式を含む待機ノードからなる群から選択される請求項６記載の方法。
【請求項１０】
前記制御フロー解析は、ユーザによる手動変更のために少なくとも１つの異常制御構造を検出する請求項２記載の方法。
【請求項１１】
前記資源の静的枠組は推敲することによって作成され、推敲することは第１言語で書かれたコードの動的挙動を表現するのに充分な数の状態保持要素を割り当てることによって実行される請求項１記載の方法。
【請求項１２】
前記状態保持要素は、
第１言語で書かれたコードの構造を再帰的に解析すること、
構造制約条件を決定すること、
前記コードの構造と前記構造制約条件から推敲グラフを作成すること
によって割り当てられる請求項１１記載の方法。
【請求項１３】
前記推敲グラフは、スカラノード、ストラクトノードおよびリストノードからなる群から選択される複数のノードを特徴とする請求項１２記載の方法。
【請求項１４】
前記推敲グラフは、第１言語の複数の構造を完全に表わすために展開される請求項１２記載の方法。
【請求項１５】
検証言語は対称性を特徴とし、前記推敲グラフは展開されてコードの非対称な特徴を克服する請求項１４記載の方法。
【請求項１６】
前記非対称な特徴は、時相式および時間のかかるメソッドからなる群から選択される請求項１５記載の方法。
【請求項１７】
前記基礎を成す制御構造は、アクションについての制御フロー解析によって検出され、前記アクションを実行させるために条件およびトリガのうちの少なくとも１つを決定し、前記条件およびトリガのうちの少なくとも１つは、前記アクションの実行を支配するためのガードであり、複数のガードは逐次制御グラフを作成するために決定される請求項１２記載の方法であって、
前記推敲グラフと前記逐次制御グラフとの間の相互関係を決定することをさらに含む方法。
【請求項１８】
前記相互関係は、競合を検出するために使用される請求項１７記載の方法。
【請求項１９】
前記相互関係は、実行スケジュールを計算するために使用される請求項１７記載の方法。
【請求項２０】
第１言語は少なくとも１つの型の対称性を特徴とし、前記少なくとも１つの型の対称性は前記資源の静的枠組を作成するときに維持される請求項１記載の方法。
【請求項２１】
第１言語は検証言語である請求項１記載の方法。
【請求項２２】
第２言語の翻訳後、コードは設計の検証を実行する請求項１記載の方法。
【発明の詳細な説明】
【０００１】
発明の分野
本発明は、検証言語の合成に関し、特に、そのような言語で書かれたプログラムを目的言語、好適な例ではＨＤＬ（ハードウェア記述言語）にコンパイルするための方法に関する。
【０００２】
発明の背景
設計検証は、集積回路、基板、またはシステムレベルのアーキテクチャがそのデバイスのアーキテクチャの仕様によって規定された要求事項を厳格に実現するかどうかを決定するプロセスである。試験対象デバイス（ＤＵＴ）の設計検証は、実際のデバイスで、またはデバイスのシミュレーションモデルで実行することができる。説明のみを目的として、かついかようにも限定する意図無く、以下の記載はデバイスのシミュレーションモデルに実行する試験を中心にしている。
【０００３】
様々な種類のデバイスおよびデバイスアーキテクチャの設計が複雑になるにつれて、設計ミスの可能性が増加する。しかし、デバイスの設計のシミュレーションモデルも作成しかつ試験することが複雑になるので、設計検証もまた困難になり、時間がかかる。
【０００４】
設計検証の問題は、多種多様なデバイスおよびデバイスアーキテクチャの検証および試験に役立つ、幅広く一般化可能なツールの欠如によって悪化する。典型的な背景技術の検証方法はしばしば特定の設計を有する特定のデバイスに限定されてきたので、シミュレーションモデルのためのそのような検証方法を準備しかつ実現するステップを、各々の新しいデバイス毎に実行しなければならない。
【０００５】
デバイスのシミュレーションモデルを通して設計を検証するプロセスは、ＶｅｒｉｌｏｇおよびＶＨＤＬなどのハードウェア記述言語すなわちＨＤＬの利用可能性によって助長される。これらの言語は、ゲートまたはトランジスタより高い抽象化レベルでハードウェアを記述するように設計されている。結果的に得られるデバイスのシミュレーションモデルは、回路の入力に加えられる２進数の文字列であるテストベクトルの形の入力刺激を受け付けることができる。次いでシミュレーションモデルは結果を生成し、それは特定の設計のデバイスの期待結果に照らして検査される。しかし、これらの言語は一般的に実際の検証用に設計されていない。したがって、検証エンジニアは、デバイスの設計検証を実行するため、これらのハードウェア記述言語によって記述されたモデルとインタフェースするために、追加プログラミングコードを書かなければならない。特に、ｅ検証特定的言語は設計検証に非常に有用である。
【０００６】
有用な検証言語の一例として、ＳｐｅｃｍａｎＴＭ関数型プログラミング言語（米国カリフォルニア州マウンテンビュー、Ｖｅｒｉｓｉｔｙ  Ｄｅｓｉｇｎ社）によって提供され、かつ１９９８年２月６日に出願された米国特許出願第６１８２２５８号に開示されたｅ言語がある。該米国特許出願を、あたかも全文がここに記載されているかのごとく、参照によってここに組み込む。ｅ言語は設計検証用のプログラムを作成するのに非常に有用であるが、依然として特定の欠点を持つ。例えば、ほとんどのソフトウェア言語と同様に、ｅコードは明瞭な静的構造を持たず、モデルの動的機能性は、タイミングに関して最も顕著に、実行時の解釈を受け入れやすい。対照的に、ハードウェア記述言語はより明瞭な静的構造を持ち、タイミングなどの問題に関してさほど曖昧ではない。しかし、この後者の型の言語は本質的に、ｅ言語などの検証言語の動的側面を備えていない。
【０００７】
発明の概要
背景技術の参考文献はいずれも、ｅ言語をハードウェア記述言語に自動的に翻訳するための方法を教示せず、示唆してもいない。
【０００８】
本発明は、ｅ言語を合成するための方法を提供し、それにより該言語を目的言語にコンパイルすることを可能にすることによって、背景技術の欠点を克服する。この方法は、言語の基礎を成す制御構造を決定し、次いでそれを使用して言語の動的挙動を静的枠組の一部として目的言語にマップすることを可能にする。何らかの型の言語を合成するプロセスは、ソフトウェアプログラムの暗黙の制御構造の少なくとも一部分をコンパイル済み出力コードに構築させるので、追加スケジューラまたは他の型の実行時システムを必要としない。したがって、コンパイル済み出力コードは、原始言語自体で書かれたソフトウェアプログラムより高い実行速度を持つはずであり、かつ、より効率的に動作するはずである。
【０００９】
本発明では、第１言語で書かれたコードを第２目的言語に自動的に翻訳する方法を提供する。第１言語は動的挙動を特徴とし、第２目的言語はオブジェクトの階層を特徴とするので、オブジェクト間の関係は第１言語の制約によって決定される。該方法は、第１言語のコードの基礎を成す制御構造を検出するステップと、第１言語で書かれたコードの動的挙動をサポートするために資源の静的枠組を形成するステップと、前記資源の静的枠組および前記基礎を成す制御構造に従って前記動的挙動を第２目的言語にマップするステップとを含む。
【００１０】
本発明の方法はまた、データプロセッサによって実行される複数の命令として記述することもできるので、本発明の方法はハードウェア、ソフトウェア、ファームウェア、またはそれらの組合せとして実現することができる。本発明のために、適切であれば実質的にどんなプログラミング言語でもソフトウェアアプリケーションを書くことができ、それは通常の当業熟練者が容易に選択することができる。選択されるプログラミング言語は、ソフトウェアアプリケーションを実行するコンピューティングプラットフォームと互換可能でなければならない。適切なプログラミング言語の例としてＣ、Ｃ＋＋、およびＪａｖａ（登録商標）があるが、それらに限定されない。
【００１１】
図面の簡単な説明
本発明をここで、単に例として、添付の図面に関連して説明する。
図１は、本発明に係る例示的方法のフローチャートである。
図２は、本発明に係る幅優先推敲を実行するための「擬似コード」の一例を示す。
図３は、本発明に係るｅ言語による実現に関する推敲プロセスの一例を示す。
図４は、図２のコードの実行の結果得られる本発明に係る例示的グラフを示す。
図５は、展開後の図４の例示的グラフを示す。
図６は、本発明に係る逐次制御フローグラフを作成するためのｅ言語コード入力の一例を示す。
図７は、本発明に係る図６から結果的に得られる逐次制御フローグラフを示す。
図８は、本発明に係る図７の逐次制御フローグラフに対して展開プロセスを実行した後の例示的展開グラフを示す。
図９は、本発明に係る逐次制御フローグラフのためのクライアントプロセスのセグメント化の一例を示す。
図１０は、本発明に係るタグ付けに関する例示的注釈プロセスのための例示的擬似コードを示す。
図１１は、ｅ言語で書かれた単純な２プロセス例を示す。
図１２は、本発明の方法に従って作成された推敲グラフ結果を示す。
図１３は、例示的セグメント化スケジューリング制約グラフを示す。
図１４は、導出されたセグメント化スケジューリング制約グラフを示す。
【００１２】
好ましい実施態様の説明
本発明は、検証言語を合成し、それにより検証言語を例えばハードウェア記述言語（ＨＤＬ）などの目的言語にコンパイルすることを可能にする方法を提供する。そのような検証言語の好適な例であって、本発明の好適な実施形態を説明するために使用する言語は、ｅ言語である。言うまでも無く、本発明は他の型の検証言語および多種多様な目的言語に使用することができる。
【００１３】
いずれかの型の検証言語を合成するプロセスは、ソフトウェアプログラムの暗黙の制御構造の少なくとも一部分をコンパイル済み出力コードに構築させるので、追加スケジューラまたは他の型の実行時システムを必要としない。したがって、コンパイル済み出力コードは、検証言語自体で書かれたソフトウェアプログラムより高い実行速度を持つはずであり、かつ、より効率的に動作するはずである。しかし、合成のプロセスは２つの問題を持つことが予想される。第一に、時相コードの動的挙動をサポートするのに充分な静的枠組を作成しなければならない。第二に、コンパイル済みコードの実行が検証言語自体の動的挙動を正確に表わすように、動的挙動を目的言語にマップしなければならない。
【００１４】
ｅ時相言語は合成用に設計されてはいないが、Ｊａｖａ（登録商標）およびＣ＋＋などの「純粋」なソフトウェア言語よりずっと大幅に、ハードウェアデバイスの挙動に関連付けることのできる一般構造を持つ。したがって、ｅ言語は本発明に好適な検証言語であるが、前述の通り、それは合成プロセスに有用な唯一のそのような検証言語ではない。
【００１５】
今、図面を参照すると、図１は、本発明に係る合成の例示的方法のフローチャートである。図示する通り、該方法は最初に、ここで「推敲」と呼ぶプロセスで検証言語を「推敲する」ことを含む。推敲のプロセスは、ｅ言語プログラムによって呼び出される全ての可能な挙動を表現するのに充分な状態保持要素の割当を含む。特に、実行前に存在する構造は静的であるが、実行中に「大急ぎで」割り当てられるオブジェクトは一時的とみなされる。全ての必要な構造は実行前にコンパイル済み言語で表現されているはずなので、後者のオブジェクトは実行時にデータ転送によって処理される。
【００１６】
これらの構造を表現するために、検証言語の静的構造を予め定められた意味構文に従って拡張し、それにより予測可能な構成のコンパイル済みコードを生成することが好ましい。代替的に、言語の動的側面が文字通りに動作するように、検証言語を実行することによって検証言語の動的特性を捕捉することができるが、そのような代替的手法には多数の不都合がある。例えば、スカラおよびオブジェクトの役割に関するより高レベルの情報は、代替的手法では失われるので、動的構造のさらなる解析は不可能である。したがって、本発明の好適な実施形態では、予め定められた意味構文に従って静的構造を決定する。
【００１７】
これらの予め定められた意味構文は任意選択的に、かつ好ましくは、型のネスティングおよび構造制約条件の決定を含む。型のネスティングによる構文のプロセスとは、推敲が必ずトップユニットから始まり、次いでそのユニットの派生を再帰的に含むことを意味する。構造制約条件は型宣言内に埋め込まれ、構造の部分間の関係を課すため、およびフィールドに初期値および定数値を課すために使用される。タイミング依存構文またはｗｈｅｎ  ｉｎｈｅｒｉｔａｎｃｅ構文は、正確な構文を決定することができない場合に可能性のサブツリー全体の決定が必要になるので、このプロセスをさらに複雑にする。
【００１８】
図１に関連して示す通り、本発明の方法は、当技術分野で公知であるように原始言語で書かれた入力プログラムの構文解析および抽象構文ツリーの作成から開始することが好ましい。該プロセスは、推敲プロセスの始まりである推敲グラフの作成に続く。好適なグラフの実施形態において、オブジェクトまたはスカラの各インスタンスはノードによって表現される。全てのグラフノードはそれらの型情報を含む。３つの主要な型のノード、すなわち初期値または定数値を含むことができるスカラノード、ネストされたインスタンスを参照するストラクトノード（ｓｔｒｕｃｔ  ｎｏｄｅ）、ならびにリスト項目、リストサイズ、およびインデックスロールを参照するリストノードがあることが好ましい。全てのノードは、（以下でさらに詳述する通り）作成順序に従って決定される親参照を含む。有向エッジが参照を示す。エッジには、ソースに配置されたときにターゲットにアクセスするために使用される名前がタグ付けされる。
【００１９】
推敲プロセスは、図１に関連して示す通り、幅優先走査により実行することが好ましい。そのような幅優先走査を実行するための「擬似コード」の一例を、図２に関連して示す。幅優先走査は、構造制約条件の収集、およびそのような制約条件を各レベルの走査プロセスに適用することを含む。制約条件は値を割り当て、インスタンスを統一することが好ましい。後者の作業において、無限再帰を回避するために、ルートに近いインスタンスだけを維持することがより好ましい。
【００２０】
例えば制約条件がまだ呼び出されていない引数を含むために、制約条件をそのレベルで適用できない場合には、それを「満たされない制約条件リスト」に集めることが好ましい。また、幅優先探索は、探索の各レベルで１つまたはそれ以上の制約条件を適用しようとして、このリストを繰返し検査するプロセスを含むことも好ましい。
【００２１】
次に、各インスタンスの一意の親が識別される。それはインスタンスを参照した最初の、あるいは最上位のエンティティである。探索の同一レベルから複数の参照が行われる場合、親関係は任意選択的に、自由裁量と考えることができることに注意されたい。
【００２２】
本発明の好適な実施形態では、プログラムコードも合成しながら、検証言語に特有の何らかの型の対称性を少なくとも可能な程度に維持することに特別な考慮が払われる。ｅ言語の特定の特徴は対称性の検出および維持に役立つので、したがってｅ言語による本発明の好適な実現は対称性の維持に役立つ。例えば、ｅ言語ではリストが、しばしば対称性を持続するような仕方で幅広く使用される。リスト自体が本質的に対称型であり、代表的項目が全ての項目を表わすことができ、したがって解析が簡素化される。本発明の方法はさらに、より好ましくは、全ての項目を表わす対称リスト項目代表および対称リスト項目から区別される全ての未決項目のリストの二重表現を有するリストノードを提供することによって、そのような対称性を維持する。本発明では、以下でさらに詳しく述べる通り、対称表現から対称性を破る特定の条件下で明示的表現に切り替える合成のプロセスにより、全てのリストを最初に対称と想定することがより好ましい。
【００２３】
対称性を維持する別の例は、スカラに関して実現される。例えば、スカラは対称配列のインデックスとして使用される。そのようなスカラは、スカラが特定の値を割り当てられない限り、インデックスとして使用される間に対称性を破ることはない。
【００２４】
グラフを作成するためにこれらのプロセスを繰り返し、それにより推敲プロセスを形成することが好ましい。そのようなプロセスのための例示的擬似コードを図２に関連して示す。図示する通り、Ｌは現行探索レベルのノードのセットであり、Ｃは満たされない制約条件セットである。関数ａｐｐｌｙ（）は満たされない制約条件のセットを受け取り、制約条件に適合するように構造を変更し、満たされないままの制約条件のセットを返す。関数ｔｙｐｅｏｆ（）はインスタンス参照を受け取り、型記述子を返す一方、関数ｒｅｆｔｏ（）は型記述子を受け取り、グラフ参照エッジを返す。関数ｍａｋｅｎｏｄｅ（）は参照を受け取り、インスタンスに対応するグラフノードを返す。
【００２５】
図２に示す通り、例示的擬似コードアルゴリズムはトップユニットへの参照から始まる。ノードのセットＬ内の各参照ｒに対し、型記述が最初に決定される。次に、参照に対応するノードが関数ｍａｋｅｎｏｄｅ（）によって返される。この型記述の制約条件が、未解決制約条件のリストＣに追加される。次いで、制約条件のいずれかを適用できるかどうかを決定するために、型記述の各フィールドが未解決制約条件のリストに対して検査される。加えて、新しいグラフノードをグラフの残部に接続するために、新しい参照エッジも返される。次いで、好ましくはこのプロセスは繰り返され、さらに好ましくは、全ての制約条件が適用されるかまたは解決不能であるとみなされるかのどちらかになるまで、繰り返される。
【００２６】
図３は、ｅ言語による実現に関する推敲プロセスの一例を示す。この例示的プロセスはネストされたストラクトおよびストラクトのリストを含むが、簡潔にするために方法は省かれている。このコードを実行した結果得られる、本発明に係る例示的グラフを図４に示す。四角はｅストラクトを表し、楕円はスカラを表し、八角形はリストを表わす。破線リンクは、インデックスなどの特殊ロールを表わす。
【００２７】
例示的プログラムはｓｙｓと呼ばれるトップレベルオブジェクトを含み、これはｃｌ ｌｉｓｔと呼ばれるネストされたオブジェクトのリストを含み、オブジェクトはｃｌ型である。ｓｙｓ内の制約条件は、ｃｌ ｌｉｓｔが４個の要素を含むことを決定し、各要素のｉｄフィールドはリスト内の要素のインデックスに設定される。Ｓｙｓはまたａｒｂ型のａｒｂと呼ばれるオブジェクトをも含む。このオブジェクトのｃｌｓフィールドは、上述したｃｌ ｌｉｓｔリストの参照に制約される。ａｒｂ型は、ｃｌｓと呼ばれるｃｌ型のリストおよびｄａｔａと呼ばれる整数フィールドを含むことが図示されている。ｃｌ型は複数のスカラフィールドおよびａｒｂ型のａｒｂフィールドを含むことが図示されている。ａｒｂフィールドは、ｓｙｓ下のａｒｂフィールドと同一であるように制約される。
【００２８】
図４は、推敲プロセスによって抽出される静的構造を示す。ｓｙｓ下およびｃｌ下の制約条件を使用して、プロセスは結果的にｃｌ型要素の単一リスト、および無限再帰構造のように見えるものにもかかわらず単一のａｒｂオブジェクトを生じた。
【００２９】
再び図１に戻ると、推敲のプロセスは、全ての制約条件が適用されたかまたは解決不能であるとみなされる場合に完了することが好ましい。しかし、任意選択的に、かつ、より好ましくは、図示するように、検証言語構造をより完全に表わすために、完成したグラフを展開する。例えば、リストの対称性が破られたときに、完成したグラフを展開することがより好ましい。リストの対称性が破られる状況の一例は、リスト内のオブジェクトが、埋め込まれた時間のかかるメソッド（Ｔｉｍｅ  Ｃｏｎｓｕｍｉｎｇ  Ｍｅｔｈｏｄ）（これはここで「ＴＣＭ」と呼ぶ制御またはプロセスの独立スレッドである）または時相式を持つときに発生する。これらのプロセスは内部状態を持ち、かつ、これらのプロセスはインスタンス毎に異なる状態にある可能性が高いので、リストはもはや対称ではなくなる。
【００３０】
図５は、この例ではｃｌストラクトがその中にＴＣＭを持つので必要になる、展開後の図４の例示的グラフを示す。推敲プロセス中にストラクトの状態を事前決定することはできないので、展開されたグラフはこのストラクトの全ての可能性を含む。
【００３１】
再び図１に戻ると、例示的方法は、制御構造の解析または制御フロー解析を示す。この解析は推敲ステージの後に続く別個の逐次ステージとして示されているが、実際には、制御構造の解析は任意選択的に、推敲のプロセスと並行して実行することができる。制御構造の解析は、該方法およびｅ型宣言の一部である時相式に関して実行することが好ましい。加えて、ＴＣＭおよびイベントの様々なインスタンス化を解析に含めることが好ましい。
【００３２】
制御フロー解析の最終結果は、各データ処理アクションについて、どの条件およびトリガがそのアクションを実行させるかを決定することである。目的言語としてハードウェア設計言語にコンパイルする本発明の好適な実現では、意味論が同期的であり、サイクルを基礎にすると想定することができるので、ブール条件および時相トリガは相似であるとみなすことができる。しかし、ｅ言語の意味論を正確に複製する本発明の好適な実現の場合、時相トリガはブール式に対して計算優先性を有することが好ましい。唯一の同期トリガはシステムクロックを維持し、全ての非クロック、時相トリガ、およびブール条件はここでは「ガード」と呼ばれる。したがって、制御フロー解析は、各アクションの実行を支配し、それにより結果的に逐次制御フローグラフを作成するために、ガードのリストを決定することが可能でなければならない。
【００３３】
再び図１に戻って、制御フロー解析は、最初に各プロセスのトリガ構造を計算することによって始動することが好ましい。この計算は任意選択的に、かつ、好ましくは、ストラクトレベルからＴＣＭへの制御の流れまたは時相式を捕捉することによって実行される。制御の流れは、ｓｔａｒｔアクションが無いかｒｕｎ（）メソッドを走査し、ＴＣＭ内部の発生を処理し、ｏｎメソッド（特定の時相式が成功したときに実行される手順）を処理することによって捕捉される。
【００３４】
次に、非クロック、時相トリガ、およびブール条件を決定するために、各メソッドのアクションシーケンスを解析することによって、各プロセスの各アクションに対してガードが計算される。任意選択的に、かつ、より好ましくは、メソッド呼出しは、呼び出されたメソッドの制御フローを呼出し自体の代わりにインスタンス化させる。
【００３５】
ひとたびガードが決定されると、逐次制御フローグラフが作成される。このグラフはアクションを基本ブロックに分類する。基本ブロックは任意選択的にガード内にネストすることができる一方、ガードは任意選択的にネストすると共に連鎖させることもできる。ある期間にわたって発生するアクション、あるいはｗａｉｔおよびｓｙｎｃなど、他の方法で時間のかかるアクションは、基本ブロックを分割する特殊待機ノードによって表現することが好ましい（前述の通り、これらのブロックは任意選択的に、ｗａｉｔなどプロセスを遮断するアクションによってセグメント化することができる）。
【００３６】
逐次制御フローグラフは、少なくとも３つの型のノード、すなわち基本ノード、ガードノード、および待機ノードから作成することがより好ましい。基本ノードは、いずれも時間がかからないアクション、あるいは制御フローアクションではないアクションのリストを表わす。ガードノードは分岐点を表し、ガードであるブール式と、式が真であると評価された場合に選ばれる正分岐と、そうでない場合に実行される負分岐とを有する。ガードのラベルは、ループまたはｉｆ  ｔｈｅｎ  ｅｌｓｅアクションとして示すことができる。待機ノードは、それが単一時相式、またはポートを介する通信など他の時間のかかるアクションを含む（他のアクションは含まない）ことを除いては、基本ノードと同様である。
【００３７】
本発明の好適な実施形態では、このグラフのノードは抽象構文ツリーノードへの参照を保持しているので、コード生成は追加情報を抽出することができる。グラフ全体が抽象構文ツリーの特定の型のノードに関連付けられる。
【００３８】
逐次制御フローグラフを作成するためのｅ言語コード入力の一例を図６に示す。
【００３９】
該コード例は、ｓｙｓと呼ばれるトップオブジェクトの下でネストされるｃｌ型のクライアントのリストを含む。ａｒｂ型のアービタオブジェクトも、ｓｙｓの下でネストされる。クライアントは、アービタ内にネストされた共用データフィールドにデータを転送しようとする。クライアントが同時に操作する場合、共通フィールドへのアクセスは、データの破損を防止するために、順次に実行しなければならない。順次アクセスは、アービタと各クライアントとの間で実行されるプロトコルによって達成することが好ましい。クライアントのデータが転送可能な状態になり、外部エージェント（サンプルコードには含まれない）によってセットされたｄｒｄｙによって合図されると、クライアントはｘｒｅｑを表明する。次いでそれはアービタが要求を通知し、ｘｇｒｔをセットすることによって肯定応答するのを待つ。この時点でデータは転送され、クライアントは要求の表明を解除し、これによりアービタはｘｇｒｔの表明を解除する。ひとたび転送が完了すると、クライアントはｄｒｄｙの表明を解除し、外部エージェントの停止を合図する。
【００４０】
結果的に得られる逐次制御フローグラフを図７に示す。四角は基本ブロックを表し、菱形はガードを表し、八角形は時間のかかるアクションを示す。
【００４１】
逐次制御フローグラフを作成するときに、少なくとも１つのアクションに対して文脈を設定することがより好ましい。繰返し子またはメソッド呼出しなど、特定のアクションは局所的文脈を形成する。式を解釈し、かつ推敲グラフ上の参照を位置決めするために、この局所的文脈が必要である。各アクションの文脈は、名前参照対のリストを制御フロー抽出プロセスに渡すことによって設定することが好ましい。アクションが局所変数を生成するたびにリストに追加することが好ましい。次いで、プロセスがこれらの変数の範囲から外れるたびに、リストは「ポップ」され、あるいは非関連変数が除去される。任意選択的に、かつ、より好ましくは、文脈は各待機ノードに保存される。実行はこれらのノードでのみ開始されるので、文脈情報はこれらのノードからより効率的に検索される。
【００４２】
本発明の任意の、しかし好適な実施形態では、制御フロー抽出プロセスは、少なくとも１つの異常制御構造を明らかにすることができ、次いでユーザはこれを手動で変更することが好ましい。そのような異常制御構造の一例として、条件付き待機アクションのみを含むサイクルがある。サイクルを解きほぐす方法は無数にあるので、そのようなコードは、コード生成段階の必須要件である、セグメントの有限リストとして表わすことができない。したがって、ユーザにそのような構造の存在を通知し、ループに待機が無くなるか、あるいは少なくとも１つの無条件待機を含むように、コードを修正するように要求することが好ましい。
【００４３】
次いで、必要な場合、ループを展開することが好ましい。ループ構造が前述の通り異常であるため、またはループが参照する構造の展開のため、ループによっては展開する必要があるかもしれない。異常制御構造の場合、ユーザはループを展開する前にコードを手動で変更することが好ましい。ループが参照する制御構造の展開に関して、そのような展開が行われる状況の一例として、対称性がくずれたためにリストを展開する場合がある。特定のプロセスは、リストにアクセスするために繰返し子を使用することができる。しかし、ひとたびリストが展開されると、リスト構造が変化するので、繰返しアクセスは一般的にもはやサポートされなくなる。したがって、リストに適切にアクセスするためには、繰返し子自体を展開しなければならない。
【００４４】
展開のプロセスは、文脈値割当に関して多少のサポートを必要とする。例えば、ｆｏｒ  ｅａｃｈアクションは、ｉｔおよびｉｎｄｅｘのような変数を文脈に追加する。展開したときに、これらの変数は、その範囲が１回の繰返しである定数になる。このプロセスは、文脈ノードと呼ばれる第４の逐次制御フローグラフノードによってサポートされる。文脈ノードは、文脈に変数または定数のいずれかの範囲を追加する。文脈ノードは、展開される構造の各繰返しのトップに追加される。
【００４５】
展開されるループの一例を、図６の例に関連して説明する。その例では、クライアントオブジェクトｃｌにネストされたＴＣＭがリストを展開させる。アービタプロセスｓｗｉｔｃｈ（）はリストオブジェクトにアクセスするので、リスト繰返し子を展開しなければならない。展開のプロセスは逐次制御フローグラフ上で実行され、その結果得られた展開アービタプロセスのための新しいグラフが図８に示されている。図８における破線の四角は文脈ノードを表わす。
【００４６】
次に、各セグメントがアトミック実行を表わすように、各プロセスのセグメント化を計算することがより好ましい。一部のプロセスは待機アクションなど一部のアクションを妨げるので、そのようなセグメント化は非常に好ましい。したがって、サイクルフリーである（または、実現のための特定の目的言語によっては、少なくとも零時間サイクルのみを含む）こと、およびシーケンスの最後の最後を除いて時間のかかるアクションが無いことをも特徴とする、実行のアトミックシーケンスにプロセスを分類する必要がある。
【００４７】
セグメント化プロセスは、循環有向グラフであることが好ましい（しかし必ずしもその必要はない）逐次制御フローグラフを取り、待機ノードで始まりかつ終わる全ての可能な経路をグラフから抽出する。単純化として、グラフ全体への入口点および出口点も待機ノードとみなすことが好ましい。経路は分岐したり交わるが、それでもなお、待機ノードなど時間のかかるアクションによって中断されない限り、同一セグメント内にあるとみなすことができる。
【００４８】
図９は、逐次制御フローグラフのクライアントプロセスのセグメント化の一例を示す。セグメントは基本ブロックの番号として示される。各ブロックは任意選択的に複数のセグメントによってカバーすることができることに注意されたい（トップノードのように）。また、セグメントは、この例では分岐するセグメント４に関して示すように、任意選択的に分岐したり交わることもできる。
【００４９】
本発明の任意であるが好ましい実施形態では、ネストされたｉｆ−ｔｈｅｎ−ｅｌｓｅ節を含むセグメントの急増を排除することによって、逐次制御フローグラフ自体を最適化することがより好ましい。そのような急増は、セグメント化段階後の逐次制御フローグラフノードを併合して、併合されたノードが同一ソースを参照し、したがって同一アクションを表わし、かつ同一セグメントの部分となるようにすることによって排除される。適切な最適化プロセスの一例は、ソース参照およびそのノードのセグメントに基づいて各ノードのハッシュ数を最初に算出し、次いで各セグメントを横切り、ノードへの参照を参照されたノードのハッシュ値と合致するノードリスト内の最初のノードと置換することによって実行される。
【００５０】
一例として、簡単なプログラムは次の構造を持つことができる。
2004530236.tif 000002
非最適化制御フローグラフはガードノードで始まり、その正の子がＡ１を含む基本ブロックノードとなり、その後にＡ３を含む基本ブロックノードが続く。負の子はＡ２を含む基本ブロックであり、その後にＡ３を含む基本ブロックの第２インスタンスが続く。
【００５１】
該最適化プロセスは、同一ハッシュ値を持つＡ３を含む２つの基本ブロックを格納する。制御フローグラフを再構成するときに、基本ブロックノードの同一インスタンスが、正および負の両方の分岐下のＡ３を表わすように使用される。これにより制御フローグラフのサイズが低減される。
【００５２】
図１に関連して示した通り、次の段階では、推敲グラフと逐次制御フローグラフとの間の相互関係が作成される。そのような相互関係は推敲構造に対する各プロセスインスタンスの影響を考慮し、それにより広域変数を介する連絡、副作用、および競合状態を明らかにする。
【００５３】
そのような相互関係を作成するために、ネストされたプロセスを持つ全てのインスタンスを識別することによって、構造全体に対して制御フローを最初に計画することが好ましい。これらのインスタンスはそれらのプロセスのｍｅ（または自己参照）文脈として役立つ。事前実行時構造に存在するプロセスは「ルートプロセス」と呼ばれ、ｒｕｎ（）メソッドにより始動する。そのようなプロセスは一般的にそのトップレベルに無限ループを有する。ルートプロセスは次にメソッドを呼び出し、あるいは新しいプロセスを始動することができる。メソッド呼出しに関連する問題を、以下でさらに詳しく述べる。
【００５４】
リスト項目内の各々のネストされたプロセスはリストの対称性を破るので、ネストされたプロセスは任意選択的に、かつより好ましくは幾つかのクラスに分類され、次いでそれらの各々が別個に処理される。第１クラスは独立プロセスであり、それはリストオブジェクト内のデータにアクセスするだけであり、他のリストオブジェクトまたは大域文脈にはアクセスしない。このプロセスは実際には対称性を破らず、そのようなプロセスの１つのインスタンスは推敲グラフに対する全てのそのようなプロセスの影響を実証するのに充分である。次のクラスは近傍従属プロセスであり、それはそのインデックスを使用して他のリストにアクセスし、リスト内の先行オブジェクトおよび後続オブジェクトを覗き込む。推敲グラフに対する完全な影響を見るためには、多数のそのようなプロセスが存在する必要がある。
【００５５】
例えば、リスト項目がオブジェクト内のフィールドのみならず、リスト内の先行オブジェクト内のフィールドにもアクセスできると仮定する。先行点を持たない項目０を除いて、全てのリスト要素は対称である。プログラムにおけるそのようなオブジェクトの影響を完全に評価するために、２つの場合を考慮しなければならない。すなわち項目０の場合と、インデックスが０より大きい項目の場合である。一般的に、近傍従属プロセスは、２つ以上のリスト項目であるが、全リスト項目には満たない数のリスト項目を考慮することによって解析することができる。そのようなプロセスは方法によっては対称性を破るが、別の方法ではそれを保全することができるので、推敲グラフに対する完全な影響を識別するために、小セットの代表的プロセスを考慮する必要があるかもしれない。
【００５６】
第３クラスは、アクセスが全く制限されず、したがって常に対称性を破る任意従属プロセスである。これらのプロセスの影響は、小セットのそのようなプロセスの挙動を調べることによって決定することはできないので、この型のプロセスの存在は対称性を破ると想定しなければならず、したがって独立して調べなければならない。
【００５７】
次に、注釈のプロセスは任意選択的に、かつより好ましくは、エイリアシングを処理する。これはデリファレンシングによって生じる問題である。パラメータまたはフィールドなどの変数に推敲グラフのノードへの参照が割り当てられると、そのような変数に実行される演算が推敲グラフノードに適用されることが好ましい。したがって、変数は今やノードのエイリアスとして機能する。しかし、制御構造の処理中にそのようなデリファレンシングが、一部は条件付きで複数の異なる割当を通過すると、最終結果として、静的解析中に決定することのできない曖昧な不確定エイリアシング関係が生じ得る。この問題を解決するために、可能なエイリアスのリストを各変数に対して維持することが好ましい。実行中に特定のエイリアスを選択する決定を行わなければならない場合には、インスタンス化されたセレクタ論理で正しいノードを指定することが好ましい。
【００５８】
一例として、次のような簡単なプログラムを考慮されたい。
2004530236.tif 000003
プログラムｐｒｏｇ（）は、Ｂの値に応じてｆ．ｌｅｆｔまたはｆ．ｒｉｇｈｔを返すことができる。ｒｅｓｕｌｔ変数は両方のためのエイリアスである。ｒｅｓｕｌｔが実行時に正しいフィールドの値を反映するように、一部の論理は目的言語で作成しなければならない。
【００５９】
そのような解決策は曖昧なエイリアシングを防止するのでが好ましいが、多数の潜在的エイリアスを格納する必要があるという不利益を持つことがある。
【００６０】
前述の通り、例えばルートプロセスが別のメソッドを呼び出したときにメソッド呼出しが行われる。各メソッド呼出しの結果、形式パラメータが実パラメータに置換されて、呼び出されたメソッドのアクションが逐次制御フローグラフに追加されることが好ましい。この解決策の問題点は、前述したエイリアシング、および多形性から生じることがある。
【００６１】
多形メソッドは、事実上特定の実現が選択されるまで厳密なメソッドが決定されないので、どの実現を呼び出すかを決定するために型を決定する必要がある。特定の実現のそのような選択、およびしたがって多形性の解決は、多くの理由から静的解析中にはできないかもしれない。例えば、静的型はツリー型のリーフではないので、実際の型はサブタイプであるかもしれない。代替的に、静的型は未決定のｗｈｅｎサブタイプであるかもしれないので、決定因子は実行中にその値を変えるかもしれない。この問題を解決するために、実行中に適切な実現を選択することができるように充分な論理を追加して、全ての可能なケースをサポートすることがより好ましい。複雑さの範囲はエイリアシングの場合のそれと同様であるが、これらの２つの効果は相互に増幅して、目的言語で作成される構造のサイズを潜在的に膨張させるかもしれない。
【００６２】
これらの異なる型の曖昧さが解消し、あるいは少なくとも実行時の解決が可能となるように充分にサポートされると、次に注釈プロセスは、推敲グラフの全てのインスタンスにデータアクセスを識別するラベルをタグ付けすることに続く。タグは、アクセスインスタンス、プロセスインスタンス内のアクセスセグメント、およびアクセスモード（書込みまたは読出し）を特徴とすることがより好ましい。タグ付けプロセスは任意選択的に、かつより好ましくは、次のように実行される。最初に、推敲グラフを通過し、見つかった全てのプロセスインスタンスを始点として役立てることが好ましい。各始点で、全てのセグメントについて、全てのアクションをステップ処理することが好ましい。各アクションの全てのデータアクセス式を、より好ましくはアクション文脈にも従って、推敲グラフ上にマップする。次いで各目的インスタンスを識別し、データアクセス式の意味論に従ってタグ付けすることができる。タグ付けのプロセスを実行するときに、可能な場合、かつ任意選択的にユーザへの表示用の診断メッセージを生成するために、情報を使用して出力モデルの静的スケジュールを算出するので、大域データフローパターンが明らかになる。
【００６３】
図１０は、タグ付けに関する例示的注釈プロセスのための例示的擬似コードを示す。この擬似コードは、注釈が各ノードから始まり、次いで各ノードの構造内により深く、各アクション内の各式が見つかりタグ付けされるまで、再帰的に浸透することを強調している。
【００６４】
再び図１に戻ると、次の段階は任意選択的に、かつより好ましくは、目的言語の出力翻訳コードの実行のためのスケジューリングである。そのようなスケジューリングは、異なるスケジューリング規則を使用することができるかあるいは真の同時環境で実際に実行することのできる目的言語での実行中に、ｅ言語などの原始言語のスケジューリング規則を維持するために、非常に好ましい。そのような同時環境では、イベントは潜在的に人工的な順序またはスケジュールに従って発生せず、代わりに、プログラムによって規定された通りに発生する。対照的に、目的言語が異なるスケジューリング規則に従って実行される場合、イベントは任意順序に従って発生することがある。
【００６５】
本発明の任意であるが好ましい実施形態では、そのような任意順序付けを防止するために、スケジューリング上の考慮事項を、翻訳されるコードの構造にガードの形でコンパイルすることが好ましい。したがって、これらの考慮事項を即座にガードとして認識できるようにするために、そのような考慮事項は本質的に静的であることを要求することがより好ましい。
【００６６】
したがって、本発明の方法のスケジューリング段階は、図１に関連して述べた通り、全てのセグメントの静的優先順位を見つけようとすることが好ましく、それをここではスケジュールと呼ぶ。全ての制御変数に関連付けられる値のリストである実行状態を前提として、スケジュールは、全ての明らかになったアクションが実行される順序を決定する。明らかになったアクションはここでは、真であるガード付きのアクションと定義される。
【００６７】
スケジューリング段階の特に好適な側面は競合の排除である。競合状態は回路設計における非常に一般的で深刻な問題である。競合状態の一例を、Ｖｅｒｉｌｏｇプログラムによって下の表１に示す。
表１．競合状態
2004530236.tif 000004
この例において、クロック「ｃｌｋ」が「０」からｃｌｋの正のエッジである「１」に変化すると、最初にａ＝ｂとなるか、あるいは最初にａ＝ｃとなるかのいずれかである。すなわち、それらは相互に競合する。その結果、信号「ａ」が「ｂ」または「ｃ」の値を取ることがある。回路設計では、最終値「ａ」が１つに定まらないので、これは望ましくない効果である。
【００６８】
競合状態は、変数を読み出すと結果的に幾つかの値のうちの１つが非決定的に生じる状況と定義される。競合を回避するために、回路は通常、競合状態を防止する幾つかの特定の方法で設計される。別の手法は、設計段階で回路に競合があるかどうかを検知するものである。幾つかの回路シミュレーションツールは、同一シミュレーションサイクル中に信号（ワイヤ、レジスタ、または変数とも称される）が２回またはそれ以上書き込まれるか、あるいは書込みだけでなく読出しも行われることをシミュレータが見つけた場合に、競合状態を検知することができる（例えば米国特許第５３８３１６７号、第５８１８２６３号、第５９０１０６１号、および第６００９２５６号を参照されたい）。
【００６９】
設計に競合が無い場合、スケジュールに対する唯一の制約条件は、式の計算を、その計算の結果を使用する前に配置することである。さらに好ましくは、特別な場合、ＴＣＭを評価する前に時相式の評価が必要である。ｅ時相言語を使用する本発明の好適な実現では、イベントをＴＣＭによって任意選択的に発行することができ、次いでイベントは同一クロックサイクル内のコードの実行に影響を及ぼすことができなければならない。ＴＣＭによって発行されるイベントの従属性がネストされた少なくとも特定のケースでは、例えば１つのＴＣＭ内の発行動作により別のＴＣＭが実行される場合、従属性の連鎖を処理することができる。そのような従属性を正しく処理するために、発行動作の実行は、ここで「アクションリタイミング」と呼ぶプロセスである各サイクルの始めに移動することがより好ましい。アクションリタイミング自体はスケジューリングの問題を生じることがあるが、この問題は各々の個別セグメント内で解決可能である。
【００７０】
任意選択的に、かつより好ましくは、サイクル同期モデルだけがそのようなリタイミングプロセスおよび他のスケジューリング合理化によって処理される。サイクル同期モデルとは、１サイクルの計算結果が次のサイクルに影響するモデルであり、例えばｅ言語用のモデルである。サイクル同期イベントが発生した場合、これらのイベントを手動で解決するために、ユーザに警報を出すことがより好ましい。
【００７１】
また任意選択的に、かつより好ましくは、潜在的な競合が、翻訳されているコードの解析の一部として識別される。一般的に、競合は曖昧なプログラムの結果である。プログラムの曖昧さは、イベントのタイミングおよび順序を決定する実行時スケジューラに、これらのイベントの実行順序に関して任意の決定をさせる。その場合この順序は実際の被試験デバイス（ＤＵＴ）によって再現されないかもしれない。したがって、ユーザに全ての疑わしい競合を通知することが好ましい。
【００７２】
競合についてさらに詳しく述べると、競合は、適切なアクセスプロトコル無しに共用変数を介して連絡するプロセスによって生み出されるということである。注釈段階で、推敲グラフの各インスタンスに全てのアクセスがタグ付けされる。複数のアクセスタグを持ち、少なくとも１つのそのようなアクセスが「書込み」アクセスである各インスタンスは、潜在的に競合が疑わしいターゲットである。しかし、同一セグメントインスタンスに属するアクセスタグは、それらが制御の単一スレッドに属しており、したがって順次に実行されるので、競合とはみなされないことが好ましい。
【００７３】
疑わしい各競合ターゲットは、そのターゲットにアクセスしようとする複数のアクションに関して調べることがより好ましい。各アクションを調整するためのガードの階層を調べて、これらのアクションが明らかになる少なくとも１つの条件が存在する場合に、疑わしい競合ターゲットを競合とみなすようにすることが、最も好ましい。例えば、任意選択的に、かつ最も好ましくは、２つのブール条件が同時に真となるかどうかの決定を使用して、潜在的競合を判別することができる。また、任意選択的に、かつ最も好ましくは、２つのセグメントを同時に実行することができるかどうかを決定するために、時相式を解く。
【００７４】
そのような競合によって生じる問題を少なくとも軽減するために、本発明の好適な実施形態では、時相式にＴＣＭより高い実行の優先順位を与える。また、読出し−書込み競合が存在する場合、値が使用前に計算されるようにするために、読出しアクションの前に書込みアクションをスケジュールすることがより好ましい。所与のアクションの結果を、この結果が次のアクションによって要求される前に決定することができるようにするために、他のアクションも任意選択的にスケジュールすることができる。
【００７５】
実行のスケジュールに対するこれらの制約条件は任意選択的に、かつより好ましくは、スケジューリング制約条件グラフに具現される。セグメントインスタンスはアクションのアトミックな零時間シーケンスであるので、グラフのノードは各々、セグメントインスタンスであることが好ましい。セグメントを別のセグメントの前に実行することを、前者のセグメントの何らかのアクションのために、要求する各制約条件は、したがって、従属セグメントから独立セグメントへの直接エッジとして表わすことが好ましい。
【００７６】
図１１は、ｅ言語で書かれた単純な２プロセスの例を示す。この例は、ｓｙｓの下でネストされたａｇｅｎｔ型の２つのオブジェクトを含む。これらのエージェントは同時に実行して、ｓｙｓの下のｗフィールドである共通変数に値を書き込もうとする。エージェントは、データ破損を引き起こすことのあるｗへの同時アクセスを防止する、相互排除アルゴリズムを実現する。該アルゴリズムは、各エージェントが要求を表明し、共用の非保護変数（ｓｙｓの下のＫフィールド）に何らかの型の識別子を保存することを要求する。値が無傷のままであり、他のエージェントがその要求を取り下げた場合には、共用変数ｗに再び書き込むことができる。
【００７７】
結果的に得られた推敲グラフを図１２に示す。セグメント化制御フローグラフを図１３に示し、導出されたセグメント化スケジューリング制約条件グラフを図１４に示す。
【００７８】
推敲グラフは、ｓｙｓの下の２つの共用変数ｗおよびＫのみならず、２つのエージェントを表わすエージェントオブジェクトの２つのインスタンスをも示す。各エージェントはＩＤフィールドｉｄ、要求フィールドｒｅｑ、および他のエージェントｏａへの参照を有する。
【００７９】
制御フローグラフは、各エージェントが３つの実行状態の１つを取ることができることを示す。すなわち、セグメント０は初期要求である。セグメント１は、他のエージェントが共用変数にアクセスしている場合に入ることのできる待機サイクルを表わし、セグメント２は、エージェントが共用変数にアクセスできる状態である。
【００８０】
スケジューリング制約条件グラフは、２つのエージェントのセグメント間の矛盾を示す。各楕円形はエージェントの１つのセグメントを表わし、各エッジはセグメント間の従属性を表わす。共依存セグメントはスケジュールの矛盾を表わす。例示のスケジューリング制約条件グラフの破線ノードは、Ｋおよびｗに関して書込み／書込み競合の疑いの顕現である２つのサイクルを形成している。Ｋに関する競合は真の競合であり、ｗに関する競合は真の競合ではない。第２サイクルを検知して除去するために、関係するプロセスの時相性に関してフィルタリングが必要になる。
【００８１】
ひとたびスケジューリング制約条件グラフが作成されると、スケジューリングプロセスがこのグラフ上に位相的順序を形成することが好ましい。該プロセスによりスケジュールする非制約ノードを選択し、その後、そのノードにつながる全ての制約条件を除去する。全てのノードがスケジュールされるまで、このプロセスを繰り返すことがより好ましい。スケジューリング制約条件グラフ自体がサイクルフリーである場合には、該プロセスは中断無く任意選択的に繰り返すことができる。
【００８２】
しかし、グラフに１つまたはそれ以上のサイクルがある場合には、追加の独立ノードが利用可能でなければ、該プロセスは停止するかもしれない。その場合、該プロセスは、幾つかの制約条件を無視するように、任意の決定を実行することがより好ましい。この任意の決定は結果的に出力モデルのタイミングを狂わせるかもしれないので、そのような決定が行われる場合は、ユーザに通知することが最も好ましい。スケジューリング制約条件グラフにおけるそのようなサイクルの存在は、前述の通り解決されなかった対応するタイミングの曖昧さを暗示すると考えることができる。他方、対応する制約条件は偽の競合の結果生じることがあるので、サイクルの存在だけでは、競合の原因として充分ではない。
【００８３】
さらに、ノードをスケジュールした後、１つまたはそれ以上のサイクルを中断させるかもしれないこのノードにつながる全ての制約条件を除去することがより好ましい。次いで原プロセスを任意選択的に続けることができる。サイクル中断は原モデルと合成モデルとの間のタイミング差を導入する結果になるかもしれないので、そのようなサイクル中断を最小化するために、１つまたはそれ以上の発見的規則を加えることができる。
【００８４】
前述の通り、本発明の好適な実施形態では、ＴＣＭ内に発行されたイベントをサポートし、したがって実行されるコードの挙動を合理化するために、アクションリタイミングを実行する。ＴＣＭによって発行されるイベントは、同一クロックサイクル内の制御フローに影響を及ぼすことが予想されるので、リタイミングされた動作を注釈段階で制御フローから抽出することが好ましく、それらの実行を支配するガード付きで抽出することがより好ましい。抽出プロセスは、セグメント開始点からリタイミングされたアクションまでの零時間経路に、ガード状態を変更するアクションが含まれるかどうかを決定することが好ましく、ガード状態を変更するそのようなアクションの存在をユーザに通知する。
【００８５】
より好ましくは、リタイミングされたアクションを次いで静的スケジュールに最初に配置して、アクションが特定のサイクルで実行されるときに、そのガードの値に応じて、セグメントが実行される前に、その特定のアクションが最初に実行されるように配置することがより好ましい。次いでこの実行の結果を、必要に応じてセグメントで使用することができる。
【００８６】
これまでの説明は、１対の原始言語コードと目的言語に関連し、原始言語のコードが目的言語に翻訳される本発明の方法の一例を中心にした。原始言語／目的言語対の特に好適な例は、原始言語についてｅ言語で書かれたコードおよび目的言語としてのＶｅｒｉｌｏｇ  ＨＤＬである。
【００８７】
本発明を限定された数の実施形態に関連して説明したが、本発明の多くの変形、変化、および応用が可能であることは理解されるであろう。
【図面の簡単な説明】
【００８８】
【図１ａ】本発明に係る例示的方法のフローチャートである。
【図１ｂ】本発明に係る例示的方法のフローチャートである。
【図１ｃ】本発明に係る例示的方法のフローチャートである。
【図２】本発明に係る幅優先推敲を実行するための「擬似コード」の一例を示す。
【図３】本発明に係るｅ言語による実現に関する推敲プロセスの一例を示す。
【図４】図２のコードの実行の結果得られる本発明に係る例示的グラフを示す。
【図５ａ】展開後の図４の例示的グラフを示す。
【図５ｂ】展開後の図４の例示的グラフを示す。
【図６】本発明に係る逐次制御フローグラフを作成するためのｅ言語コード入力の一例を示す。
【図７】本発明に係る図６から結果的に得られる逐次制御フローグラフを示す。
【図８ａ】本発明に係る図７の逐次制御フローグラフに対して展開プロセスを実行した後の例示的展開グラフを示す。
【図８ｂ】本発明に係る図７の逐次制御フローグラフに対して展開プロセスを実行した後の例示的展開グラフを示す。。
【図９】本発明に係る逐次制御フローグラフのためのクライアントプロセスのセグメント化の一例を示す。
【図１０】本発明に係るタグ付けに関する例示的注釈プロセスのための例示的擬似コードを示す。
【図１１】ｅ言語で書かれた単純な２プロセス例を示す。
【図１２】本発明の方法に従って作成された推敲グラフ結果を示す。
【図１３】例示的セグメント化スケジューリング制約グラフを示す。
【図１４】導出されたセグメント化スケジューリング制約グラフを示す。
【図１ａ】
2004530236.tif 000005
【図１ｂ】
2004530236.tif 000006
【図１ｃ】
2004530236.tif 000007
【図２】
2004530236.tif 000008
【図３】
2004530236.tif 000009
【図４】
2004530236.tif 000010
【図５ａ】
2004530236.tif 000011
【図５ｂ】
2004530236.tif 000012
【図６】
2004530236.tif 000013
【図７】
2004530236.tif 000014
【図８ａ】
2004530236.tif 000015
【図８ｂ】
2004530236.tif 000016
【図９】
2004530236.tif 000017
【図１０】
2004530236.tif 000018
【図１１】
2004530236.tif 000019
【図１２】
2004530236.tif 000020
【図１３】
2004530236.tif 000021
【図１４】
2004530236.tif 000022
【国際公開パンフレット】
2004530236.tif 000023
2004530236.tif 000024
2004530236.tif 000025
2004530236.tif 000026
2004530236.tif 000027
2004530236.tif 000028
2004530236.tif 000029
2004530236.tif 000030
2004530236.tif 000031
2004530236.tif 000032
2004530236.tif 000033
2004530236.tif 000034
2004530236.tif 000035
2004530236.tif 000036
2004530236.tif 000037
2004530236.tif 000038
2004530236.tif 000039
2004530236.tif 000040
2004530236.tif 000041
2004530236.tif 000042
2004530236.tif 000043
2004530236.tif 000044
2004530236.tif 000045
2004530236.tif 000046
2004530236.tif 000047
2004530236.tif 000048
2004530236.tif 000049
2004530236.tif 000050
2004530236.tif 000051
2004530236.tif 000052
2004530236.tif 000053
2004530236.tif 000054
2004530236.tif 000055
2004530236.tif 000056
2004530236.tif 000057
2004530236.tif 000058
2004530236.tif 000059
2004530236.tif 000060
2004530236.tif 000061
2004530236.tif 000062
2004530236.tif 000063
【国際調査報告】
2004530236.tif 000064
2004530236.tif 000065