(57)【要約】【課題】本発明は、並列に動作する複数の回路モジュールのモジュール間インタフェース回路を自動的に合成することができる技術を提供することを課題とする。【解決手段】モジュール間インタフェース回路の書き込み系列と読み出し系列を解析し、書き込み遅延を求め、モジュール間インタフェースが持つ変数配列の変数のライフタイムを解析する。そして各変数配列の集合から、縮退させた変数集合を求める。そして、変数共有問題を解き、各変数をメモリに割り当てる。そしてこの変数の割り当てを元に回路を合成する。【選択図】　　　図１
2004054641.tif 000002
【特許請求の範囲】
【請求項１】
並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成する合成装置であって、
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求める変数算出手段と、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求めるライフタイム算出手段と、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探す縮退集合算出手段と、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する回路合成手段と、
を備えることを特徴とするモジュール間インタフェースの自動合成装置。
【請求項２】
前記縮退された変数集合の要素である変数の前記ライフタイムが重ならないようにメモリに共有させ、前記縮退された変数集合の要素である変数の前記メモリへの割り当てを求める変数割り当て手段を更に備え、前記回路合成手段は前記割り当てに基いて前記モジュール間インタフェースを合成することを特徴とする請求項１に記載のモジュール間インタフェースの自動合成装置。
【請求項３】
回路記述言語による記載を解析し、回路の仕様を出力するコンパイラ手段と、
前記コンパイラ手段から、並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成を依頼されると、該モジュール間インタフェースを合成するインタフェースモジュール生成手段とを備え、前記インタフェースモジュール生成手段は、
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求める変数算出手段と、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求めるライフタイム算出手段と、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探す縮退集合算出手段と、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する回路合成手段と、
を有することを特徴とするＣＡＤシステム。
【請求項４】
並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成する合成方法であって、
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求め、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求め、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探し、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する
ことを特徴とする合成方法。
【請求項５】
並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成するコンピュータによって実行されるプログラムであって
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求め、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求め、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探し、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する
ことを前記コンピュータに実行させるプログラム。
【請求項６】
前記縮退された変数集合の要素である変数の前記ライフタイムが重ならないようにメモリに共有させ、前記縮退された変数集合の要素である変数の前記メモリへの割り当てを求め、前記割り当てに基いて前記モジュール間インタフェースを合成することを前記コンピュータに実行させる請求項５に記載のプログラム。
【請求項７】
Ｌｅｆｔ　Ｅｄｇｅ　法に基いて、前記縮退された変数集合の要素である変数の前記ライフタイムが重ならないようにメモリに共有させ、前記縮退された変数集合の要素である変数の前記メモリへの割り当てを求めることを特徴とする請求項６に記載のプログラム。
【請求項８】
前記モジュール間インタフェースがデータを読み込んでから書き込むまでの最小の時間である最小遅延時間を求め、該最小遅延時間を考慮して、前記モジュール間インタフェースを合成することを前記コンピュータに実行させる請求項５乃至７の何れか１つに記載のプログラム。
【請求項９】
前記モジュール間インタフェースへのデータの書き込みを行う前記回路モジュール、前記モジュール間インタフェースへのデータの読み出しを行う前記回路モジュール及び前記モジュール間インタフェースに対してそれぞれの同期信号に基いた時刻を設定し、前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析する際、前記書き込みを行う回路モジュール及び読み出しを行う前記回路モジュールの時刻を前記モジュール間インタフェースの時刻に変換することを前記コンピュータに実行させることを特徴とする請求項５乃至８の何れか１つに記載のプログラム。
【請求項１０】
並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成するコンピュータによって使用された時、
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求め、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求め、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探し、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する
ことを前記コンピュータに実行させるプログラムを記憶した前記コンピュータが読み出し可能な可搬記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高位合成（Ｈｉｇｈ　Ｌｅｖｅｌ　Ｓｙｎｔｈｅｓｉｓ）による回路設計の技術に関し、更に詳しくは並列動作する複数の回路モジュール間のインタフェースとなるモジュール間インタフェースの合成に関する。
【０００２】
【従来の技術】
近年ハードウエアは、ＶＬＳＩに代表されるように大規模化されており、これに対処する為ハードウエア設計をコンピュータを使って自動化するという研究が進められている。ハードウエア設計の手法の一つとして、ＶＨＤＬやＳＦＬなどのような回路記述言語を用いてハードウエアを意識しないで動作仕様を記述し、これをコンピュータに入力すると、コンピュータが各モジュールの入力論理の合成や論理圧縮などを行い、更に配置・配線などが行われて実際の回路を合成するものがある。このような回路記述言語からの合成手法のうち、特に抽象度の高い回路記述から合成する手法を高位合成と呼ぶ。
【０００３】
図３２に、高位合成による回路設計で用いられる回路記述言語による動作記述例を示す。同図の例では、（Ａ）部分には、配列変数にデータを出力する処理が記述されており、（Ｂ）部分には、配列変数からデータを読み出す処理が記述されている。
【０００４】
高位合成による回路設計において、図３２に示すように記述された、もともと逐次的に処理される部分（Ａ）、（Ｂ）を、並列実行させる構成としたい場合がある。
【０００５】
このような場合、並列実行される回路モジュール間でのデータ転送を担いインタフェースとなる部分をハードウエアとして作成するが、たいていこのインタフェースとなる部分の回路には、タイミング調整用のバッファメモリを設けなければならない。そしてデータを出力する回路モジュールはこのバッファにデータを書き込み、データを受け取る回路モジュールはこのバッファからデータを読み出す。
【０００６】
図３２の（Ａ）部分で記述された処理を実現する回路モジュールＡ、及び（Ｂ）部分で記述された処理を実現する回路モジュールＢを実装し、両者を並列実行させる場合、回路モジュールＡと回路モジュールＢとでバッファ上の同じ配列変数に対するアクセスが行われる。
【０００７】
この時この２つの回路モジュールが正しく並列処理を行う為には、配列変数に対する書き込みと読み出しの順序が正しく行われなければならない。つまり、回路モジュールＡが書き込んだ後に回路モジュールＢが読み出す、回路モジュールＢが読み出す前に回路モジュールＡが書き込んではいけない、といった順序関係が保証される必要がある。
【０００８】
これを実現する方法の１つとして、配列変数ａｒｒａｙ　を２重化し、ａｒｒａｙ　Ａとａｒｒａｙ　Ｂの２つの配列変数に対するメモリ領域を備える構成としてハードウエア化することが考えられる。この場合、回路モジュールＡがａｒｒａｙ　Ａに書き込み、その間回路モジュールＢはａｒｒａｙ　Ｂから読み出す。回路モジュールＡ、Ｂが最後まで書き込み／読み出し終わったら、今度は、回路モジュールＡがａｒｒａｙ　Ｂに書き込み、回路モジュールＢはａｒｒａｙ　Ａから読み出す。以降、この動作を繰り返す。
【０００９】
この方法を用いると、回路モジュールＡで書き込み終わった後に回路モジュールＢが読み出し、回路モジュールＢが読み出す前に回路モジュールＡは書き込まない、という条件は満たすことが出来る。
【００１０】
この方法を用いた場合、配列変数ａｒｒａｙとして使用するメモリ量は、必ずしも元の配列変数のサイズの２倍は必要ないケースが多い。しかし回路を半導体チップ内に構成する場合、メモリサイズはできるだけ小さい方が回路の配置／配線、消費電力、製造コストなど多くの点でメリットがある。
【００１１】
メモリを２重化する方法以外としては、回路設計者が、動作記述を十分に解析し、上記の配列変数を領域を２重化する方法よりもメモリ量を削減した実現方法を、回路毎に検討して手作業で設計する方法が考えられる。
【００１２】
また高位合成一般において、本発明で対象としているモジュール間インタフェース回路とは別に、変数をメモリ（レジスタ）に割り当てるスケジューリング処理がある。そこでは、変数共有と呼ばれる最適化処理が行われる。これは、ライフタイムが重複しない変数は、おなじメモリに割り当てることで、高位合成によって生成されるハードウエア量を減らす技術である。この技術は、本発明で対象としている高位レベル記述のモデルの構造と配列変数に対しては、そのままでは適用できない。
【００１３】
【発明が解決しようとする課題】
本発明は、上述したような、並列実行される複数の回路のインタフェースとなる回路を自動合成することが出来る仕組みを提供することを課題とする。
【００１４】
またこの時、インタフェースとなる回路を構成するバッファメモリのサイズ決定と、バッファメモリに関係する制御回路を自動合成することが出来る仕組みを提供することを課題とする。
【００１５】
配列変数のアクセスを数学的にモデル化し、従来より少ないメモリ量でレイテンシ（処理すべきデータが投入されてから処理結果がでてくるまでの時間）も小さくなったインタフェースとなる回路を、自動合成する仕組みを提供することを課題とする。
【００１６】
【課題を解決するための手段】
上記問題点を解決する本発明による合成装置は、並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成することを前提として、変数算出手段、ライフタイム算出手段、縮退集合算出手段及び回路合成手段を備える。
【００１７】
変数算出手段は、前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求める。
【００１８】
ライフタイム算出手段は、前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求める。
【００１９】
縮退集合算出手段は、前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探す。
【００２０】
回路合成手段は、前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する。
また本発明は、回路記述言語による記載を解析し、回路の仕様を出力するコンパイラ手段及び上記合成装置を手段として備えるＣＡＤシステムとして実現することもできる。
【００２１】
また本発明は、前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求め、前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求め、前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探し、前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成することを特徴とする合成方法も適用範囲内である。
【００２２】
更に本発明は、コンピュータプログラムや可搬記憶媒体も適用範囲内である。本発明によれば、モジュール間インタフェースを自動的に合成することができる。
【００２３】
また使用するメモリ量を少なくしたモジュール間インタフェースを合成することができる。
発明の他の特徴を図２４，図２５を参照して説明する。Ｖ［０］からＶ［ｎ−１］までのｎ個の変数の全体集合（図２４ではＶ［０］からＶ［６３］）の各変数Ｖ［ｉ］が時刻Ｂｅｇｉｎ［ｉ］（図２４で＃の始まる時刻）において、メモリのあるアドレスに書き込まれ、ライフタイムＴ（図２４では＃の数）だけ保持され、時刻Ｅｎｄ［ｉ］（図２４で＃が終わった次の時刻）で読み出されるメモリの書き込み読み出し動作を前提に説明する。変数Ｖ［ｉ］（図２４で例えばＶ［０］の書き込みが始まるＢｅｇｉｎ［ｉ］からライフタイムＴ後に変数Ｖ［ｊ］（図２４で例えばＶ［４］）の書き込み時刻Ｂｅｇｉｎ［ｊ］となること、及び変数Ｖ［ｉ］の読み出し時刻Ｅｎｄ［ｉ］以降に変数Ｖ［ｊ］のＢｅｇｉｎ［ｊ］が始まらなければいけないという条件を満足するｉとｊの組み合わせからなる書き込み系列と読み出し系列が、互いに合同すなわち時間差Ｔｒで同じライフタイムをもつ変数の集合になる部分集合（図２４のＰ０，Ｐ１，Ｐ２，Ｐ３）を求める。各部分集合の中では変数の書き込み時刻は異なる。その条件を満足する部分集合がいくつかできた場合にはその部分集合を全体集合に対して縮退された部分集合と呼ぶ。
【００２４】
この縮退された部分集合は変数の順序関係において、合同となっているので縮退された部分集合の変数に対応するアドレス空間で（図２４では部分集合Ｐ０に対応するアドレス空間１６）メモリの読み書きが可能となる。すなわち、アドレス空間が図２４では６４から１６に縮退されたことになる。
【００２５】
さらに、各縮退された変数集合をさらなる部分集合に分割しても、変数の共有化すなわち１つのアドレスに複数の変数を入れることによって前述の縮退されたアドレス空間よりも少ないアドレス空間で上の条件を満たすことができる。たとえば、図２４のＶ［０］，Ｖ［４］，Ｖ［６］をＡ，＋，Ｂとすれば、図２５のメモリのアドレスＭ［０］に割り当てることができる。これを変数の共有化と呼ぶ。図２５では、もともとのアドレス空間６４が１０まで縮退されたことになる。
【００２６】
【発明の実施の形態】
図１は、本発明におけるインタフェースとなるモジュール間インタフェースのを自動生成する技術をＣＡＤシステムに応用した場合のＣＡＤシステムの構成を示すブロック図である。
【００２７】
同図のＣＡＤシステム１は、入力編集部１１、コンパイラ部１２、ライブラリ格納部１３、インタフェースモジュール生成部１４及び出力部１５を備えている。尚同図は、ＣＡＤシステムのうち本発明に関連する部分のみが示してある。
【００２８】
入力編集部１１は、回路を設計する際、ユーザによる処理内容を回路記述言語で記述入力・編集を処理する部分である。コンパイラ部１２は、入力編集部１１からユーザが入力した記述内容やファイルとして読み込んだファイル内の回路記述言語による記述内容を実現する回路の仕様を生成する。ライブラリ格納部１３は、複数の回路ライブラリを格納する部分で、コンパイラ部１２が回路を生成する際に参照し、必要なライブラリを引き出す。インタフェースモジュール生成部１４は、上記した並列実行される複数の回路モジュール間のインタフェースとなるモジュール間インタフェースを生成するもので、コンパイラ部１２が回路を生成する際、回路記述言語による記述内容を解析し、モジュール間インタフェースが必要と判断すると、その生成を依頼する。尚このインタフェースモジュール生成部１４は、ライブラリ格納部１３の一部機能として構成しても良い。入出力部１５は、コンパイラ部１２が生成した回路をファイルとして、あるいはディスプレイ等の表示装置上に出力するものである。
【００２９】
このＣＡＤシステムは専用ハード上によって実現しても良いし、汎用のコンピュータを用いてソフトウエアによって実現することも可能である。
尚インタフェースモジュール生成部１４は、ＣＡＤシステム１やＣＡＤシステムを実現するソフトウエア一部としてではなく、他の装置やソフトエア、例えば高位合成ツール等の開発ツールやコンパイラの一部として、あるいは単独の装置やソフトウエアとして構成しても良い。
【００３０】
図２は、インタフェースモジュール生成部１４が行う処理を示す図である。
インタフェースモジュール生成部１４は、コンパイラ部１２からのインタフェースモジュールの生成依頼に対して、以下の処理を行う。
１．書き込み系列と読み出し系列を解析する。
２．書き込み系列と読み出し系列から、出力遅延を求める。
３．変数のライフタイムを解析する。
４．縮退させた変数集合を求める。
５．変数共有問題を解き、変数をメモリに割り当てる。
６．モジュール間インタフェースを合成する。
【００３１】
尚上記各処理については、後述する。
インタフェースモジュール生成部１４は、並列に動作する回路モジュールＡ、Ｂ及び回路モジュールＡ、Ｂのモジュール間インタフェースＣをプロセスとして表現して処理する。
【００３２】
ここでのプロセスとは、通信ポートに書き込みもしくは読み出しを行うことで、他のプロセスと通信しながら動作するものをいう。プロセス内部には、記憶（メモリ）が存在してもよい。プロセスは、互いに影響を与えることなく自由に通信操作を実行できる（複数のプロセスが並列動作する）。
【００３３】
またモジュール間インタフェースＣを生成する際には、以下の点を考慮して行う。
・複数のプロセスが並列に動作する。
・通信路に記憶は存在しない。
・相手が読み出す前に書き込みを行った場合には、いわゆる上書きを行ってしまい、前回書き込んだデータを壊してしまう。
・新しいデータを書き込む前に読み出しを行うと、前回書き込んだデータが読み出されるだけで新しいデータを読み出すことは出来ない。
【００３４】
プロセスは、それぞれ固有の時計を持つ。ただし、各プロセスの時計が示す時刻は、互いに線形関数で表現できるものとする。プロセス毎に時計が別々なのは、各回路モジュールが同一のクロック信号を用いて動作しているとは限らず、回路モジュール毎にクロック周波数やその位相が異なった場合において、簡潔に表現するためのものにすぎない。またそれぞれ固有の時計を持っても、各時刻は線形関数で変換できるので、複数の時計があることで、モデルがそれほど複雑になることはない。また、各回路モジュールが全て同一のクロック信号で動作することが予め判っているときは、全ての回路モジュールの時刻を１つの時計で表現してもよい。
【００３５】
図３は、インタフェースモジュール生成部１４で扱われるプロセスの例を示す図である。
同図において、プロセスＣが並列動作するプロセスＡ及びプロセスＢのモジュール間インタフェースとなる。プロセスＡは、データを出力する際、プロセスＣのメモリへの書き込み操作に相当する通信を行い、プロセスＢは、データを入力する際、プロセスＣのメモリからの読み出し操作に相当する通信を行う。そしてインタフェースモジュール生成部１４は、回路モジュールＡが書き込身が完了した後に回路モジュールＢが読み出し、回路モジュールＢが読み出す前に回路モジュールＡが書き込まないよう、順序関係が保証されるように制御するモジュールＣを生成する。
【００３６】
図４及び図５は、インタフェースモジュール生成部１４によって生成されるモジュール間インタフェースの実現例を示す図である。
図４は、配列変数をＲＡＭ上に割り当てた場合の構成で、回路モジュールＡからのデータの書き込みやモジュールＢからのデータの読み出しに対して、制御回路が各配列変数に割り当てたアドレスを発行して、順序関係が保証されるように制御する。
【００３７】
また図５は、配列変数をレジスタ上に割り当てた場合の構成で、回路モジュールＡからのデータの書き込みに対して、制御回路は割り当てられたレジスタに対してロード信号を送信して書き込ませ、モジュールＢからのデータの読み出しに対しては、セレクタを制御信号によって制御して対応するレジスタからのデータを出力させることによって順序関係が保証されるように制御する。
【００３８】
次に図２に示した、インタフェースモジュール生成部１４による処理を詳細に説明する。
（１）書き込み系列／読み出し系列の解析
この処理では、回路モジュールＡの出力及び回路モジュールＢの入力をプロセスＣの入力／出力として書き換え、以降の処理をプロセスＣに対する記述のみで議論できるようにする。
【００３９】
以下の説明では、プロセスＡ及びプロセスＢの時計が示す時刻をｔＡ　、ｔＢ　と表記する。またプロセスＡが時刻ｔＡ　のときに書き込む配列変数の添字の集合をω（Ａ，ｔＡ）、プロセスＢが時刻ｔＢ　のときに読み出す配列変数の添字の集合をγ（Ｂ，ｔＢ　）と表記する。尚本実施例では一度に複数の配列変数要素に対してアクセスするケースも想定して集合としている。また
プロセスＡの書き込み系列Ｗ（Ａ）：
Ｗ（Ａ）＝｛（ｔＡ　，ω（Ａ，ｔＡ　））｜ｔＡ　はプロセスＡの時刻｝
プロセスＢの読み出し系列Ｒ（Ｂ）：
Ｒ（Ｂ）＝｛ｔＢ　，γ（Ｂ，ｔＢ　））｜ｔＢ　はプロセスＢの時刻｝
と定義する。たとえば、
Ｗ（Ａ）＝｛（０，｛０，３２｝），（１，｛１，３３｝），・・・，｛ｊ，（３２＋ｊ）｝｝，ｊ＝ｃ　ｍｏｄ３２
は、時刻０で配列変数の０番目と３２番目に書き込みを行い、時刻１で１番目と３３番目に書き込みを行い、・・・というプロセスを表現しており、また
Ｒ（Ｂ）＝｛（０，｛０，１｝），（１，｛２，３｝），・・・，（ｄ，｛（２ｊ），（２ｊ＋１）｝），・・・｝，ｊ＝ｄ　ｍｏｄ　３２
は、時刻０で配列変数の０番目と１番目を読み出し、時刻１で２番目と３番目を読み出し、・・・というプロセスを表現している。
【００４０】
図６は、読み出し系列／書き込み系列のデータ構造例を示す図である。
プロセスの読み出し系列は書き込み系列は、図６のような１次元配列とリスト構造の組み合わせで実現できる。同図は、配列の要素がリスト構造データの先頭を示しており、またリスト構造部分の各データはその時刻でアクセスする変数の添え字の集合を表している。同図の例では系列｛（０，｛０，１、２｝），（１，｛３，４｝），（３，｛５，６｝），・・・，（ｎ−１，｛３０，３１｝）｝を格納した場合を示している。
【００４１】
またプロセスＡの時刻ｔＡｂからｔＡｅまでの書き込み系列Ｗ（Ａ，ｔＡｂ，ｔＡｅ）：
Ｗ（Ａ，ｔＡｂ，ｔＡｅ）＝｛（ｔＡｂ，ω（Ａ，ｔＡ　））｜ｔＡｂ≦ｔＡ　＜ｔＡｅ｝
プロセスＡの時刻ｔｂＡからｔＡｅまでの書き込み位置集合ω（Ａ，ｔＡｂ，ｔＡｅ）：
【００４２】
【数１】
2004054641.tif 000003
【００４３】
と定義する。
同様に、プロセスＢの読み出しについても、以下のように定義する。
プロセスＢの時刻ｔＢｂからｔＢｅまでの読み出し系列Ｒ（Ｂ，ｔＢｂ，ｔＢｅ）：
Ｒ（Ｂ，ｔＢｂ，ｔＢｅ）＝｛（ｔＢ，γ（Ｂ，ｔＢ））｜ｔＢｂ＜ｔＢ　＜ｔＢｅ｝
プロセスＢの時刻ｔＢｂからｔＢｅまでの読み出し位置集合γ（Ｂ，ｔＢｂ，ｔＢｅ）：
【００４４】
【数２】
2004054641.tif 000004
【００４５】
図３の場合、プロセスＡからプロセスＣへの通信路があるため、Ａの書き込み系列は、Ｃの読み出し系列でもある。ここでは取りこぼしがなく、確実に通信が行えるケースのみを扱うので、それが実現できるように、各プロセスでの時計を設定する。
【００４６】
プロセスＡの時刻ｔＡ　をプロセスＣの時刻ｔＣ　によって
ｔＡ　＝αＣａｔＣ＋βＣａ：αＣａ，βＣａは定数（αＣａはクロック信号の周波数の比、βＣａは位相の差に対応）
と表現すると、プロセスＣの読み出し系列γ（Ｃ，ｔＣ　，ｔＣ　＋１）は、プロセスＡの書き込み系列から容易に求められる。
γ（Ｃ，ｔＣ　，ｔＣ　＋１）＝ω（Ａ，αＣａｔＣ　＋βＣａ，αＣａ（ｔＣ＋１）＋βＣａ）
同様にして、プロセスＢの時刻ｔＢ　をプロセスＣの時刻ｔＣ　によって
ｔＢ　＝αＣｂｔＣ＋βＣｂ：αＣｂ，βＣｂは定数（αＣｂはクロック信号の周波数の比、βＣｂは位相の差に対応）
と表現すると、プロセスＢの書き込み系列ω（Ｃ，ｔＣ　，ｔＣ　＋１）は、プロセスＣの書き込み系列から求めることが可能である。
ω（Ｃ，ｔＣ　，ｔＣ　＋１）＝γ（Ｂ，αＣｂｔＣ　＋βＣｂ，αＣｂ（ｔＣ＋１）＋βＣｂ）
ただし実際の処理としては、プロセスＡの書き込み系列とプロセスＢの読み出し系列が与えられる情報となり、本処理では、逆にプロセスＢの読み出し系列から、プロセスＣの書き込み系列を求めることとなる。
【００４７】
実際には、各プロセスが同じクロック信号で動くケース、つまり、αＣａ＝１，βＣａ＝０のようなケースが大部分であるが、本処理では必ずしもクロック信号が同じ（周波数が同じ）でない場合にも対処する為に、一般化してこのような表現を用いる。
【００４８】
このようにして、モジュールＡの出力、モジュールＢの入力の２つを、プロセスＣの入力と出力だけで表現し、今後、回路モジュールＣの合成方法をプロセスＣだけで議論できるようになる。
【００４９】
一方のプロセスが１回の読み出し処理を行う間に、他方のプロセスが２回以上の書き込み処理を行う場合、複数のポートを用いて通信する等の工夫が必要になる。逆に、一方のプロセスが１回の書き込み処理を行う間に、他方のプロセスが２回以上の読み出し処理を行う場合、読み出しを休む回を設ける等の工夫が必要になる。
【００５０】
図７（ａ）は、プロセスＡの書き込み系列をプロセスＣの読み出し系列に変換する処理を示すフローチャートである。同図の処理によってｔＡ　＝０からプロセスＡの書き込み系列において、最後に書き込みを行う時刻ｔＡＥまでのプロセスＡの書き込み系列をプロセスＣの読み出し系列に変換する。
【００５１】
同図において、処理が開始されるとまずステップＳ１として、ｔａ　＝０、プロセスＣにより読み出し系列を保存する図６に示したリスト構造のデータＲＣ　を全てクリアする。
【００５２】
次にステップＳ２としてｔＣ　にαａＣｔＡ　＋βａＣ（αａＣ，βａＣは時間の関係式における定数）の計算値を小数点以下切り上げた値を代入し、プロセスＡでの時刻をプロセスＣの時刻に変換する。そしてステップＳ３として時刻ｔＣのプロセスＣの読み出し系列を保存している図６に示したようなリスト構造のデータＲＣ　［ｔＣ　］の末尾に時刻ｔａのプロセスＡの書き込み系列を保存している図６に示したようなリスト構造のデータＷＡ　［ｔａ　］を付加する。
【００５３】
次にステップＳ４としてｔＡ　の値を１つ加算し、ステップＳ５としてｔａ　の値が最後に書き込みを行う時刻ｔＡＥを超えていなければ（ステップＳ５、ＹＥＳ）、ステップＳ２に処理を戻し、ステップＳ２〜Ｓ５の処理を繰り返す。そしてステップＳ５で、ステップＳ５としてｔＡの値が最後に書き込みを行う時刻ｔＡＥを超えたならば（ステップＳ５、ＮＯ）、処理を終了する。
【００５４】
図７（ｂ）は、図７（ａ）の処理によってプロセスＡの書き込み系列のプロセスＣの読み出し系列への変換を示したもので、同図上段はプロセスＡの方がプロセスＣより速度が遅い場合、同図下段はプロセスＡの方がプロセスＣより速度が速い場合を示している。
【００５５】
同図上段では、プロセスＡの方が速度が遅いので、時刻ｔＡ　の書き込み処理がプロセスＣの時刻ｔＣ　の読み出し処理に、また時刻ｔＡ　＋１の書き込み処理がプロセスＣの時刻ｔＣ＋２の読み出し処理に対応する。また同図下段では、プロセスＡの方が速度が速いので、時刻ｔＡ　の書き込み処理がプロセスＣの時刻ｔＣ読み出し処理に、また時刻ｔＡ　＋１とｔＡ　＋２の書き込み処理がプロセスＣの時刻ｔｃ　＋１の読み出し処理に対応する。
【００５６】
図８（ａ）は、プロセスＢの読み出し系列をプロセスＣの書き込み系列に変換する処理を示すフローチャートである。同図の処理によってｔＢ　＝０からプロセスＢの書き込み系列において、最後に読み出しを行う時刻ｔＢＥまでのプロセスＢの読み出し系列をプロセスＣの書き込む系列に変換する。
【００５７】
同図において処理が開始されると、まずステップＳ１１として、ｔＢ　＝０、プロセス系列を保存する図６に示したリスト構造のデータＷＣを全てクリアする。次にステップＳ１２としてｔｃ　にαｂＣｔＢ＋βｂＣ（αｂＣ，βｂＣは時間の関係式における定数）の計算値を小数点以下切り下げた値を代入し、プロセスＢでの時刻をプロセスＣの時刻に変換する。そしてステップＳ１３として時刻ｔＣのプロセスＣの読み出し系列を保存している図６に示したようなリスト構造のデータＷＣ　［ｔＣ　］の末尾に時刻ｔＢのプロセスＢによる読み出し系列を保存している図６に示したようなリスト構造のデータＲＢ　［ｔＢ　］を付加する。
【００５８】
次にステップＳ１４としてｔＢ　の値をインクリメントし、ステップＳ１５としてｔＢ　の値が最後に読み出しを行う時刻ｔＢＥを超えていなければ（ステップＳ１５、ＹＥＳ）、ステップＳ１２に処理を戻し、ステップＳ１２〜Ｓ１５の処理を繰り返す。そしてステップＳ１５で、ステップＳ１５としてｔＢの値が最後に読み出しを行う時刻ｔＢＥを超えたならば（ステップＳ１５、ＮＯ）、処理を終了する。
【００５９】
図８（ｂ）は、図８（ａ）の処理によってプロセスＢの読み出し系列のプロセスＣの書き込み系列への変換を示したもので、同図上段はプロセスＢの方がプロセスＣより速度が速い場合、同図下段はプロセスＢの方がプロセスＣより速度が遅い場合を示している。
【００６０】
同図上段では、プロセスＢの方が速度が速いので、プロセスＣの時刻ｔＣ　の書き込み処理がプロセスＢの時刻ｔｂ　またはｔｂ　＋１のいずれかの読み出し処理に、またプロセスＣの時刻ｔＣ＋１の書き込み処理がプロセスＢの時刻ｔＣ　＋２またはｔＣ　＋３のいずれかでの読み出し処理に対応する。また同図下段では、プロセスＢの方が速度が遅いので一般的には複数の通信ポートが必要になり、プロセスＣの時刻ｔＣの書き込み処理がプロセスＢの時刻ｔｂ　読み出し処理に、またプロセスＣの時刻ｔＣ　＋１とｔＣ　＋２の２回分の書き込み処理がプロセスＢの時刻ｔｂ＋１の読み出し処理に対応する。この場合、複数個のデータがプロセス間で受け渡されるならば、複数の通信ポートが必要になる
（２）出力遅延を求める
出力遅延は、プロセスＣプロセスＣが、プロセスＡからデータを読み出してから、そのデータをプロセスＢに書き出すまでの時間で最小出力遅延ｔＣｏｄｅｌａｙ　は、その最小時間を示す値である。本実施形態では、モジュールＣで使用するメモリ量を削減するために、プロセスＣの出力遅延として、この最小出力遅延ｔＣｏｄｅｌａｙ　を選択する。
【００６１】
最小出力遅延ｔＣｏｄｅｌａｙは、以下の関係を満足する整数値となる。
∀ｔＣ　γ（Ｃ，０，ｔＣ　）⊇ω（Ｃ，０，ｔＣ−ｔＣｏｄｅｌａｙ）
プロセスＡが書き込みを開始してから、最小出力遅延ｔＣｏｄｅｌａｙ時間経過後にプロセスＢの読み出しを開始すれば、
・プロセスＡが配列変数に書き込んだあとに、プロセスＢが配列変数を読み出す
・プロセスＡが配列変数を書き込まないうちに、プロセスＢが配列変数を読み出すことはない
という処理の順序関係を満たす。
【００６２】
最小出力遅延ｔＣｏｄｅｌａｙを求めるアルゴリズムの一例を以下に示す。尚配列変数の添字の集合γ及びωは時刻ｔＣ　に対して要素数が単調増加し、上限は配列変数のサイズに等しい。よってこのアルゴリズムは、最大でも、プロセスＢが全ての要素を読み出すのに要するサイクル数だけループすれば停止する。
１．ｔ＝０
２．γ（Ｃ，０，ｔＣ　）⊇ω（Ｃ，０，ｔＣ−ｔ）ならば、ｔＣｏｄｅｌａｙ　＝ｔとして終了
３．ｔ＝ｔ＋１
４．２へ戻る
図９は、最小出力遅延ｔＣｏｄｅｌａｙを求める処理を示すフローチャートである。
【００６３】
同図において処理が開始されると、まずステップＳ２１として、初期値としてｄ、ｔ１、ｔ２に０、Ｒに時刻ｔ１のプロセスＣの読み出し系列を保存している図６に示したようなリスト構造のデータＲｃ［ｔ１］が設定される。
【００６４】
次にステップＳ２２としてｔ２がプロセスＣが最後に書き込みを行う時間ｔＣＥ以下であるかどうかを判断する。その結果ｔＣＥ以下であるならば（ステップＳ２２、ＹＥＳ）、ステップＳ２３としてリスト構造のデータのＷｃ　［ｔ２］の要素が全てリスト構造のデータＲに含まれているかどうかを判断し、含まれていなければ（ステップＳ２３、ＮＯ）ｄを１つ加算させ（ステップＳ２４）、含まれていれば（ステップＳ２３、ＹＥＳ）、ｔ２を１つ加算する（ステップＳ２５）。
【００６５】
そしてステップＳ２６として、ｔ１の値を１つ加算すると共に、リスト構造の変数Ｒの末尾にリスト構造の変数Ｒｃ　［ｔ１］を付加して、ステップＳ２２に処理を戻し、ｔ２がｔＣＥを超えるまで、ステップＳ２２〜Ｓ２６の処理を繰り返す。
【００６６】
ステップＳ２２において、ｔ２がｔＣＥより大きければ（ステップＳ２２、ＮＯ）、ステップＳ２７としてｔＣｏｄｅｌａｙとしてｄの値を設定して処理を終了する。
（３）変数のライフタイムの解析
変数ｖのライフタイムＬ（ｖ）＝（ｂｅｇｉｎ（ｖ），ｅｎｄ（ｖ））とは、時刻ｂｅｇｉｎ（ｖ）に最初に変数ｖに値の代入が発生し、時刻ｅｎｄ（ｖ）に最後の変数ｖの値参照が発生したことを示す。本処理では、モジュールＣに含まれる配列変数のライフタイムを解析する。
【００６７】
配列変数の要素ｖ［ｉ］（ｉは添え字）について、値の代入時刻は、モジュールＡより通信ポートを介して読み出した時刻となり、最後の参照時刻とは、通信ポートよりモジュールＢに向けて書き出した時刻となる。
【００６８】
変数ｖ［ｉ］について、ライフタイムＬ（ｖ［ｉ］）＝（ｂｅｇｉｎ（ｖ［ｉ］），ｅｎｄ（ｖ［ｉ］）
は以下のように求められる。
ｉ∈γ（Ｃ，ｔ）ならばｂｅｇｉｎ（ｖ［ｉ］）＝ｔ
ｉ∈ω（Ｃ，ｔ’）ならばｅｎｄ（ｖ［ｉ］）＝ｔ’
図１０は、変数のライフタイムｂｅｇｉｎ（ｖ［ｉ］），ｅｎｄ（ｖ［ｉ］）のデータ構造を示す図である。
【００６９】
変数ｖ［０］〜ｖ［ｉ］のライフタイムを示すｂｅｇｉｎ（ｖ［０］）〜ｂｅｇｉｎ（ｖ［ｉ］）及びｅｎｄ（ｖ［０］）〜ｅｎｄ（ｖ［ｉ］）は、それぞれ同図に示すような一次元配列Ｂｅｇｉｎ［０］〜Ｂｅｇｉｎ［ｎ−１］及び一次元配列Ｅｎｄ［０］〜［ｎ−１］によって実現することが出来る。
【００７０】
図１１は、ライフタイム∀　ｖｉ，Ｌ（ｖｉ）＝（ｂｅｇｉｎ（ｖ［ｉ］，ｅｎｄ（ｖ［ｉ］）を求める処理を示すフローチャートである。
同図の処理は、図１０に示した１次元配列を用いて行われるものとする。
【００７１】
同図において処理が開始されると、ステップＳ３１として初期値としてｔ＝０が設定される。
次にステップＳ３２として、時刻ｔのプロセスＣの読み出し系列を格納する図６のようなリスト構造をもつ変数Ｒｃ［ｔ］の全要素に対して、図１０に示した一次配列変数Ｂｅｇｉｎ［ｉ］（ｉは変数Ｒｃ［ｔ］の要素）にｔを代入してゆく（ステップＳ３３）。
【００７２】
次にステップＳ３４として、時刻ｔのプロセスＣの書き込み系列を格納する図６のようなリスト構造をもつ変数Ｗｃ［ｔ］の全要素に対して、図１０に示した一次配列変数Ｅｎｄ［ｉ］（ｉは変数Ｗｃ［ｔ］の要素）にｔを代入してゆく（ステップＳ３５）。
【００７３】
ステップＳ３６としてｔの値を１つ加算し、この値がプロセスＣが最後に書き込みを行う時間ｔＣＥより小さいかどうかを判断する（ステップＳ３７）。その結果ｔがｔＣＥより小さければ、ステップＳ３２に処理を戻しステップＳ３２〜Ｓ３６の処理を繰り返す。そして、ステップＳ３７でｔがｔＣＥより小さくなくなったら（ステップＳ３７、ＮＯ）、処理を終了する。
（４）縮退させた変数集合を求める
変数集合Ｖと、Ｖの部分集合ＰとＱ、Ｐ⊆Ｖ、Ｑ⊆Ｖ、｜Ｐ｜＝｜Ｑ｜（本明細書の説明で｜集合Ｘ｜は集合Ｘの要素数を示す）と、ある整数Ｔｒについて、∀ｐ∈Ｐ　∃ｑ∈Ｑ　ｓｕｃｈ　ｔｈａｔ　ｂｅｇｉｎ（ｐ）＋Ｔｒ＝ｂｅｇｉｎ（ｑ）且つｅｎｄ（ｐ）＋Ｔｒ＝ｅｎｄ（ｑ）且つｅｎｄ（ｐ）≦ｂｅｇｉｎ（ｑ）が成り立つ場合を、　外１　と表記する。この時ＰとＱは時間差Ｔｒで同
【００７４】
【外１】
2004054641.tif 000005
【００７５】
じライフタイムを持つと呼ぶ。
このような部分集合Ｐが存在すれば、変数集合Ｖ全体を考慮せずに、より小さい集合Ｐを考慮するだけでよくなる。Ｐのことをここでは縮退させた変数集合と呼ぶ。
【００７６】
本処理では、モジュールＣに含まれる配列変数を縮退した変数集合を求める。
縮退させた変数集合Ｖｒを求める処理を以下に示す。
Ｈｅａｄ（ｎ，Ｌ）を、順序つきリスト構造のデータＬの先頭からｎ個の要素を集合として返す関数とする。
１．変数集合Ｖから、各変数ｖｉ∈Ｖについてｂｅｇｉｎ（ｖｉ）の昇順で並んだ順序つきリストＶｏｒｄ　を求める。
２．変数集合Ｖの要素数｜Ｖ｜の全公約数（≠１）の中で、以下を満足するような最小の公約数ｍを求める。
【００７７】
【数３】
2004054641.tif 000006
【００７８】
３．ｍが求まったなら、Ｖｒ　＝Ｐ０＝Ｈｅａｄ（ｍ，Ｖｏｒｄ　）を、縮退された変数集合とする。
４．もしこのようなｍが存在しなければ、Ｖｒ＝Ｖとする（縮退できない）。
【００７９】
図１２は、縮退された変数集合を示す図である。
同図の例は、１／４に縮退された場合（集合Ｖｏｒｄ　の要素数／ｍ＝４）を示す。各変数集合Ｐ０〜Ｐ３は、　外２　の関係が成り立っており、Ｐ０〜Ｐ３は
【００８０】
【外２】
2004054641.tif 000007
【００８１】
それぞれｍ個の要素を持つ。
このような縮退させた変数集合Ｐ０が求まると、変数集合Ｖ全体でなくこの変数集合Ｐ０を縮退させた変数集合Ｖｒとして考慮すればよい。
【００８２】
図１３は、縮退させた変数集合Ｖｒを求める処理を示すフローチャートである。
同図の処理を行うに当たって、プロセスＣの変数の集合を一次元配列Ｖに、一次元配列Ｖの要素ｖｉ∈ＶをＢｅｇｉｎ［ｉ］の昇順にソートしたリストデータを一次元配列Ｖｏｒｄ　に、一次元配列Ｖの要素数｜Ｖ｜の約数の集合を降順に並べたリストを一次元配列Ｍに事前に設定しておく。
【００８３】
図１３の処理が開始されると、まずステップＳ４１として配列Ｍが空かどうかが判断される。その結果空でなければ（ステップＳ４１、ＮＯ）、ｎに一次元配列Ｍの最初の要素、即ち要素のうち最も小さい値を設定し、配列Ｍからこの最初の要素を取り除く。
【００８４】
次にステップＳ４３として一次元配列Ｖｏｒｄ　内の要素を先頭から順番にｎ等分し、これらをＰ０，Ｐ１，・・・，Ｐｎ−１とする。そして以下のステップＳ４４〜Ｓ４８によって、このＰ０，Ｐ１，・・・，Ｐｎ−１に対して　外３　が
【００８５】
【外３】
2004054641.tif 000008
【００８６】
成り立つかどうかを判断する。
まずステップＳ４４として変数ｉに初期値０を設定し、次にステップＳ４５としてｉ＜ｎ−１かどうか、即ち全てのＰ０，Ｐ１，・・・，Ｐｎ−１に対して処理を行ったかどうかを判断し、その結果ｉ＜ｎ−１ならば（ステップＳ４５、ＹＥＳ）、ステップＳ４６として　外４　かどうかを判断し、その結果ＹＥＳなら
【００８７】
【外４】
2004054641.tif 000009
【００８８】
ば（ステップＳ４６、ＹＥＳ）、ステップＳ４７として変数ｉの値を１つ加算すると共にステップＳ４５の処理に戻り、ステップＳ４５〜Ｓ４７の処理を繰り返す。そしてステップＳ４５で、ｉ＜ｎ−１でないと判断されたなら（ステップＳ４５、ＮＯ）、Ｐ０，Ｐ１，・・・，Ｐｎ−１の全てに対してステップＳ４６の判断において、　外５　が成立すると判断されたので、ステップＳ４８としてＶ
【００８９】
【外５】
2004054641.tif 000010
【００９０】
ｒ＝Ｐ０として処理を終了する。
また途中で、ステップＳ４６の判断の結果がＮＯとなったならば（ステップＳ４６、ＮＯ）、ステップＳ４１に処理を戻し、一次配列Ｍ内の１番目の要素をｎとして、上記した処理と同様の処理を繰り返す。尚ステップＳ４６の判断処理についての詳細は、後述する。
【００９１】
一次配列Ｍ内の全ての要素に対して処理が完了し、ステップＳ４１で一次配列Ｍが空と判断されたなら（ステップＳ４１、ＹＥＳ）、変数の集合Ｖは縮退できないので、ステップＳ４９としてＶｒ＝Ｖｏｒｄ　として処理を終了する。
【００９２】
図１４は、図１３のステップＳ４６の判断処理の詳細を示すフローチャートである。
ステップＳ４６の判断処理では、まず初期値として、変数ｍにＰｉの要素数｜Ｐ｜、変数ｊにｍ＊ｉ、変数ＴｒにＢｅｇｉｎ［ｍ］−Ｂｇｅｇｉｎ［０］が設定される（ステップＳ４６１）。
【００９３】
次に、ステップＳ４６２でｊ＜ｎ−１かどうかが判断され，その結果ｊ＜ｎ−１ならば（ステップＳ４６２、ＹＥＳ）、ステップＳ４６２としてＢｅｇｉｎ［ｊ］＋Ｔｒ＝Ｂｅｇｉｎ［ｊ＋ｍ］且つＥｎｄ［ｊ］＋Ｔｒ＝Ｅｎｄ［ｊ＋ｍ］且つＥｎｄ「ｊ」≦Ｂｅｇｉｎ［ｊ＋ｍ］かどうかが判断される。その結果これら条件を満たしていれば（ステップＳ４６３、ＹＥＳ）、ステップＳ４６４として変数ｊの値を１つ加算した後、ステップＳ４６３の処理を戻し、ステップＳ４６３の判断で上記条件を満たしていないと判断されるか（ステップＳ４６３、ＮＯ）、ステップＳ４６３でｊ＜ｎ−１を満たしていないと判断される（ステップＳ４６３、ＮＯ）までステップＳ４６２〜Ｓ４６４の処理を繰り返す。そして、テップＳ４６２でＮＯとなった時は、　外６　が成立している
【００９４】
【外６】
2004054641.tif 000011
【００９５】
と判断され、ステップＳ４６はＹＥＳとなり、ステップＳ４６３でＮＯとなったときは、　外７　は成立しないと判断され、ステップＳ４６はＮＯとなる。
【００９６】
【外７】
2004054641.tif 000012
【００９７】
（５）変数共有問題を解き、変数をメモリに割り当てる
本処理では、（４）の処理によって縮退された変数集合Ｖｒの各要素に対して、メモリを割り当ててゆく。変数集合Ｖｒは縮退が行われているので、このＶｒの要素となっている変数にそれぞれメモリを割り当て、他の変数はＶｒの要素となっている変数とメモリを共有することによって、メモリの規模を縮小化させた、モジュール間インタフェースを生成することができる。
【００９８】
またこの変数集合Ｖｒについて、変数共有問題を解き、この結果に基いて変数にメモリを割り当てることにより、更にモジュール間インタフェースのメモリ量を更に小さくできる。
【００９９】
この変数共有問題を解くのには、以下の文献に記載されているＬｅｆｔ　Ｅｄｇｅ　法を修正したアルゴリズムで解くことが可能である。
書名　Ｈｉｇｈｔ−Ｌｅｖｅｌ　Ｓｙｎｔｈｅｓｙｓ
著者　Ｄ．　Ｇａｊｓｋｉ，　Ｎ．　Ｄｕｔｔ，　Ａ．　Ｗｕ　ａｎｄ　Ｓ．　Ｌｉｎ
発行　Ｋｌｕｗｅｒ　Ａｃａｄｅｍｉｃ　Ｐｕｂｌｉｓｈｅｒｓ　発行年　１９９２
Ｌｅｆｔ　Ｅｄｇｅ　法を修正したアルゴリズムでは、処理対象の変数群Ｓ内の変数ｖをｂｅｇｉｎの昇順に並べ替え、最初の変数とから他の変数とライフタイムが重なりあうかを調べ、重なり合わなければ同じメモリに割り当ててゆく。
【０１００】
変数集合Ｖについて、Ｖ’を以下のような集合とする。
Ｖ’＝｛ｖ’｜ｖ’∈Ｖ，Ｌ（ｖ’）＝（ｂｅｇｉｎ（ｖ）＋Ｔ，ｅｎｄ（ｖ）＋Ｔ）｝
上式においてＴはプロセスの周期であり、プロセスＣが配列変数の要素に初めて書き込んだ時刻をｔ１　とし、プロセスＣが配列変数のすべての要素に書き込み終わった後、初めて書き込みを行ったときの時刻をｔ２とするとＴ＝ｔ２−ｔ１となる。この変数集合Ｖを縮退できなかった際、このＶ’を用いて変数共有問題を解く。
【０１０１】
図１５は、変数共有問題を解く処理を示すフローチャートである。
本処理では、最初に変数集合Ｖを縮退できた場合と出来なかった場合とで場合分けをし、縮退できなかった場合には、変数集合Ｓに上記Ｖ’を加えて、本来の２倍の量の要素を考慮している。これは、モジュール間インタフェースを設計する際にメモリを２倍にして、読み込み側と書き込み側とで交互にメモリを使って、アクセス競合を防ぐのと同じアイディアである。
【０１０２】
図１５の処理が開始されると、まずステップＳ５１として、縮退した変数集合Ｖｒが変数集合Ｖの変数を最初に値の代入が発生した順序で並べた順序つきリストＶｏｒｄ　と同じかどうかが判断される。その結果異なれば（ステップＳ５１、ＮＯ）、ステップＳ５２としてＳ＝Ｖｒ、Ｔｒ＝Ｂｅｇｉｎ［｜Ｖｒ｜］−Ｂｅｇｉｎ［０］を設定する。またステップＳ５１で同じであれば（ステップＳ５１、ＹＥＳ）、Ｓ＝Ｖ∪Ｖ’、Ｔｒ＝Ｔ＊２とする。
【０１０３】
次にステップＳ５４として集合Ｓに対して、Ｂｅｇｉｎ［ｉ］，ｉ∈Ｓの昇順でソートをかけこれを順序付きリストＳｏｒｄ　とする。
そしてステップＳ５５として、変数ｍｅｍ、ｌａｓｔ及びｉに０を、また変数ｎｅｘｔに∞を設定する。
【０１０４】
次にステップＳ５６としてＳｏｒｄ　が空かどうか判断され、空でなければ（ステップＳ５６、ＮＯ）、Ｓｏｒｄ　の要素数｜Ｓｏｒｄ　｜≦ｉかどうかが判断される。その結果｜Ｓｏｒｄ｜≦ｉならば（ステップＳ５７、ＹＥＳ）、ステップＳ５８として、変数ｍｅｍの値を１つ加算し、変数ｌａｓｔ及びｉに０を、ｎｅｘｔに∞を設定した後、またステップＳ５７で｜Ｓｏｒｄ｜≦ｉでないならば（ステップＳ５７、ＮＯ），そのまま処理をステップＳ５９に移す。
【０１０５】
ステップＳ５９では、Ｓｏｒｄ　の先頭からｉ番目の要素をｖに代入し、ステップＳ６０としてｌａｓｔ≦Ｂｅｇｉｎ［ｖ］且つＥｎｄ［ｖ］≦ｎｅｘｔを満たしているかどうかを判断する。
【０１０６】
その結果、満たしていると判断した場合（ステップＳ６０、ＹＥＳ）、ステップＳ６２として順序付きリストＳｏｒｄ　から要素ｖを除き、
ステップＳ６３としてＢｅｇｉｎ［ｖ］＜Ｅｎｄ［ｖ］かどうかを判断し、その結果Ｂｅｇｉｎ［ｖ］＜Ｅｎｄ［ｖ］でなければ（ステップＳ６３、ＮＯ）、処理をステップＳ５６に処理を戻す。
【０１０７】
またステップＳ６３の判断において、Ｂｅｇｉｎ［ｖ］＜Ｅｎｄ［ｖ］ならば）（ステップＳ６３、ＹＥＳ）、ステップＳ６４として変数のメモリへの割り振りを示す配列ａｓｓｉｇｎ［ｖ］にｍｅｍを代入し、またｌａｓｔ＝ｅｎｄ（ｖ）とした後処理をステップＳ５６に戻す。そしてｎｅｘｔには、ｎｅｘｔの値とＢｅｇｉｎ（ｖ）＋Ｔｒの値の小さいほうを代入する。またステップＳ６０で上記条件を満たしていなかった場合（ステップＳ６０、ＮＯ）、ステップＳ６１としてｉに対して１つ加算した後処理をステップＳ５６に戻す。
【０１０８】
このステップＳ５６からＳ６４までの処理を順序付きリストＳｏｒｄ　の要素が無くなるまで繰り返し、Ｓｏｒｄ　が空になったら（ステップＳ５６、ＹＥＳ）、処理を終了する。そしてこの配列変数ａｓｓｉｇｎに格納された結果に基いて変数にメモリを割り当てる。
（６）インタフェース回路を合成する
これまでの手続きによって、変数がメモリに割り当てられ、どのタイミングでどの変数にアクセスするか（＝どのタイミングでどのメモリにアクセスするか）が決まったので、プロセスＣをＲＴＬ（レジスタ・トランスファ・レベル）での回路として実現するのに十分な情報がそろったことになる。あとは、これらの情報に基づいたＦＳＭ（Ｆｉｎｉｔｅ　Ｓｔａｔｅ　Ｍａｃｈｉｎｅ）を構築し、ＦＳＭに従って、回路を作ればよい。
【０１０９】
以下、ＲＴＬを記述するときの文法として、ＳｙｓｔｅｍＣにならった書式を採用する。
プロセスＣのＲＴＬは、次の２つのサブプロセスから構成される。サブプロセスは同時に実行開始され、並列実行される。動作のタイミングは「ｗａｉｔ（数字）」（後述）で同期するようになっている。
・入力ポートから読み込んで、メモリに書き込むサブプロセス
・メモリもしくは入力ポートからデータを読み込んで、出力ポートに書き込むサブプロセス
変数集合を縮退できた場合の、ＲＴＬ生成を行うアルゴリズムを、図１６に示す。尚変数集合を縮退できなかった場合は、図１５の処理と同様に、２倍の量の変数を考慮する。このとき、γ（Ｃ，ｔＣ　）とω（Ｃ，ｔＣ　）とを、２倍の量の変数を扱えるように拡張する。拡張するとは、以下のような置き換えをすることを示す。
【０１１０】
もともとは、γ（Ｃ，ｔＣ　）＝γ（Ｃ，ｔＣ　＋Ｔ）であるが、次のように定義される、拡張したγ＋　（Ｃ，ｔＣ）にγ（Ｃ，ｔＣ　）を置き換える。
・γ＋　（Ｃ，ｔＣ）＝γ（Ｃ，ｔＣ　）　０≦ｔｃ　＜Ｔ
・γ＋　（Ｃ，ｔＣ）＝γ（Ｃ，ｔＣ　）のインデックスだけを｜Ｖ｜だけ増加させたもの。Ｔ≦ｔｃ　＜２Ｔとする。ω（Ｃ，ｔｃ　）についても同様にω＋（Ｃ，ｔｃ）に置き換える。
【０１１１】
尚図１６中のｏｕｔｐｕｔは、ＲＴＬコードをファイルやコンパイラなどに出力するという意味を示し、Ｐｊは入力ポートｊを示し、Ｐｊ．ｒｅａｄ（）は入力ポートから読み出したデータ、Ｑｋは出力ポートｋ、Ｑｋ．ｗｒｉｔｅ（ｄ）は出力ポートｋにデータｄを書き込むことを意味する。
【０１１２】
またγ（Ｃ，ｔＣ　）は集合であるので、１サイクル中に複数のデータを取り込む場合がある。これを実現するために、プロセスＣは入力ポート及び出力ポートは複数存在する。またどのポートからどのデータが入ってくるかはあらかじめ与えられるとする。
【０１１３】
またＡｓｓｉｇｎ［］は変数共有問題で得られた値であり、Ａｓｓｉｇｎ［ｖ］は変数ｖがどのメモリに割り当てられたかを出力する。このＡｓｓｉｇｎ［］はＲＴＬコード生成時には、定数値となる。Ｍｅｍ［ａ］＝ｂは、メモリのａ番目に値ｂを書き込むことを意味する。ｗａｉｔ（ｎ）は、ｎクロック待つことを意味する。
【０１１４】
図１６において上段のサブプロセスはデータの読み込みのＲＴＬ記述を出力するアルゴリズムで、γ（Ｃ，ｔ１）（ｔ１＝０〜Ｔ−１）の各要素に対してＭｅｍ［Ａｓｓｉｇｎ［ｊ］］＝Ｐｊ．ｒｅａｄ（）（ｊはγ（Ｃ，ｔ１）の各要素）を出力する。
【０１１５】
図１７は、このデータの読み込みを行うサブプロセスによるＲＴＬ記述の出力例を示す図である。尚同図及び後述する図１８、１９においては、サブプロセスによって出力される注釈分については略してある。
【０１１６】
同図の記述ではこれまでの処理によって得られた各変数とメモリの割り当て関係から、入力ポートからの入力データが、メモリの０，１，２，３，４，５，６，７，０，４，２，６，８番目に格納されてゆくことを示している。図４若しくは図５に示した制御部は、ｗｒｉｔｅ　ａｄｄｒｅｓｓやロード信号によってこの記述に基いた制御を行いデータをメモリやレジスタに格納してゆく。
【０１１７】
図１６において下段のサブプロセスはデータの書き込みのＲＴＬ記述を出力するアルゴリズムで、ω（Ｃ，ｔ２）（ｔ２＝０〜Ｔ−１）の各要素に対してＱｋ．ｗｒｉｔｅ（Ｍｅｍ［Ａｓｓｉｇｎ［ｋ］］）（ｋはω（Ｃ，ｔ２）の各要素）を出力する。
【０１１８】
図１８は、このデータの出力ポートへの書き込みを行うサブプロセスによるＲＴＬ記述の出力例を示す図である。
同図の記述ではこれまでの処理によって得られた各変数とメモリの割り当て関係から、出力ポートに対して、メモリの０，２，４，６，０，２，０に格納されているデータ、入力ポートのデータ、メモリの１，３，５，７，４，６，８，９に格納されているデータが、出力されてゆくことを示している。図４若しくは図５に示した制御部は、ｒｅａｄ　ａｄｄｒｅｓｓやロード選択信号によってこの記述に基いた制御を行いデータをメモリやレジスタからデータを出力ポートに出力してゆく。
【０１１９】
図１９は、データの読み込みを行うサブプロセスとデータの出力ポートへの書き込みを行うサブプロセスの２つのサブプロセスをまとめたＲＴＬコードの模擬的な例を示す図である。
【０１２０】
２つのサブプロセスを１つにまとめて記述すると同図のようになり、２つの順序回路を１つにまとめて記述したものとなっている。
次に本実施形態による、具体的な設計例を示す。
【０１２１】
例１として、以下のようなω（Ａ，ｔＡ　）とγ（Ｂ，ｔＢ　）と規定されるプロセスＡ、Ｂが与えられたとする。これはサイズ６４の配列変数をＡからＢへ受け渡すことに相当しており、Ｔ＝６４である。
【０１２２】
【数４】
2004054641.tif 000013
【０１２３】
ここで、ｚｉ　はｚを２進表現した場合のｉ桁目の値（０若しくは１）を表しており、［ｚｉ，ｚｊ　，・・・］は、０か１の値をこの順序で並べた２進数表現の値のことを指す。つまりｚ＝［ｚ５　，ｚ４，ｚ３　，ｚ２　，ｚ１　，ｚ０　］であり、ｙはｚのビット５〜３を並べ替えて得られる値となる。
【０１２４】
ここでは、時間の関係式における定数αＣａ＝１、αＣｂ＝１、βＣａ＝０、βＣｂ＝０として、プロセスＣの読み出し系列Ｒ（Ｃ）、書き込み系列Ｗ（Ｃ）を求めると、以下のようになる。
【０１２５】
Ｒ（Ｃ）＝｛（０，｛０｝），（１，｛３２｝），（２，｛１｝），（３，｛３３｝），・・・，（６３，｛６３｝）｝
Ｗ（Ｃ）＝｛（０，｛０｝），（１，｛１｝），（２，｛２｝），（３，｛３｝），・・・，（７，｛７｝），
（８，｛３２｝），（９，｛３３｝），（１０，｛３４｝），（１１，｛３５｝），・・・，（１５｛３９｝），
（１６，｛８｝），・・・，（２３，｛１５｝），（２４，｛４０｝），・・・，（３１，｛４７｝），
（３２，｛１６｝），・・・，（３９，｛２３｝）（４０，｛４８｝），・・・，（４７，｛５５｝），
（４８，｛２４｝），・・・，（５５，｛３１｝）（５６，｛５６｝），・・・，（６３，｛６３｝）｝
また最小出力遅延を求めるとｔＣｏｄｅｌａｙ＝７となる。
【０１２６】
本実施形態の前提条件として、プロセスＣは一度データの出力をはじめたら、決められた順序で常に出力しつづけ、まだ入力データが到着していないので、出力を一時停止させる、といった措置はいっさい行わないものとしている（いったん流れ始めたら、出力は滞ることなく、常に流れつづけなければならない）。そのため、あまり早いうちから出力を出しはじめてしまうと、まだ到着していないデータを出力する状況に追い込まれてしまう。そのため、ある程度待ってデータがたまってから出力を始める。この時間が最小遅延時間ｔｃｏｄｅｌａｙである。
【０１２７】
たとえば、上の例で、２単位時間だけ待って出力を開始するケースを考えるとする。そのときの様子を図２０に示す。
同図では、各時刻において、
・どのデータが入力として到着し、
・どのデータを出力し
・バッファメモリ内には、どのデータが保持されているか
を表している。
【０１２８】
同図中矢印はデータの移動を、バツ印はバッファメモリからデータが取り出されることを表している。バッファメモリの内容は集合で表現しており、順序は関係ない（この順番で、メモリに格納されていることを意味しているのではない）。尚、時刻ｔＣ　におけるバッファメモリの内容は、次のように集合の差で表現できる。
（バッファメモリの内容）＝γ（Ｃ，０，ｔＣ　）−ω（Ｃ，０，ｔＣ−２）
同図では、時刻５のとき、３番目のデータを出力しなければならないが、まだ３番は到着していないので、行き詰まってしまう（出力が滞る）。
【０１２９】
次に、７単位時間だけ待って出力するケースを考える。その様子は、図２１のようになる。
図２１では時刻２８までしか描かれていないが、それ以降も、出力が滞ることなくデータの入力と出力を連続して実行することが可能である。
【０１３０】
７単位時間よりも長く待ってから出力するケースは、（１）必要なバッファメモリ量が増加する、（２）入力が入ってから出力がでるまでの時間（レイテンシ）が増加する、といったデメリットしかないため、本実施形態ではそのようなケースは対象外とする。ただし、対象外というのは、そのようなケースを扱えないという意味ではない。このようなケースを扱うのには単にｔｃｏｄｅｌａｙ　の値に最小出力遅延の値よりも大きい値を採用すればよいだけである。
【０１３１】
プロセスＣの配列変数ｖのライフタイムの解析結果を図２２に示す。
同図においてＢｅｇｉｎ及びＥｎｄは、図１０に示した１次元配列に対応し、Ｂｅｇｉｎはその変数に最初に値の代入が発生した時間、Ｅｎｄは最後に参照が発生時間、添え字は変数の添え字を示している。
【０１３２】
図２３は、図２２を元に、各変数のライフタイムを図形的に表したものである。
同図は縦軸方向にプロセスＣの配列変数の添え字（インデックス）とり、横方向にその変数のライフタイムを“＃”で表している。同図ではｉ行目が配列変数の要素ｖ［ｉ］に対応しており、Ｂｅｇｉｎ［ｉ］からＥｎｄ［ｉ］−１までの範囲で記号＃をプロットしている。
【０１３３】
普通、配列変数の各要素は、それぞれ専用のメモリに割り当てられる。例えば、変数ｖ［０］はＭｅｍ［０］、変数ｖ［１］はＭｅｍ［１］という具合である。
【０１３４】
しかし、もしも変数ｖ［０］と変数Ｖ［１］のライフタイムに重なりが無いならば専用のメモリを割り当てることなく、メモリ１つだけで、２つの変数の値を確保させることが可能になる。例えば、変数ｖ［０］のライフタイムがＬ（Ｖ［０］）＝（３，５）であり、変数ｖ［１］のライフタイムがＬ（ｖ［１］）＝（１０，１５）であるとき、メモリＭｅｍ［０］は、時刻３〜５のときは変数ｖ［０］の値を保持し（厳密にいうと、時刻５の時に最後の値読み出しが行われ、時刻５から新しい値を保持させられるようになる）、時刻１０〜１５の時は変数ｖ［０］の値を保持する。Ｌ（Ｖ［１］）＝（１０，１５）とは、時刻１５を過ぎたら、もう変数ｖ［１］の値は使わないので値が書き換えられてしまってもかまわない、という意味である。
【０１３５】
変数共有問題とは、いくつかの変数を同じメモリに割り当てるやり方を決めることである。変数集合を縮退させることは、先に変数の共有問題を大雑把に解くことに相当するとも言える。
【０１３６】
縮退させた変数集合Ｖｒを求めると、｜Ｖ｜＝６４、ｍ＝１６であり、変数集合Ｖを４等分した、Ｖｒ＝｛ｖ０　，ｖ３２，ｖ１　，ｖ３３，ｖ２　，ｖ３４，ｖ３　，ｖ３５，ｖ４　，ｖ３６，ｖ５　，ｖ３７，ｖ６　，ｖ３８，ｖ７　，ｖ３９｝が求まる。
【０１３７】
図２４は、図２３に示した変数集合から求めた縮退させた変数集合の例を示す図である。
同図では、変数集合Ｖを４つの部分集合に分けることが出来、各部分集合は時間差Ｔｒで同じライフタイムを持っている。尚ここでは、ここではＴｒ＝１６となっている。
【０１３８】
縮退させた変数集合Ｖｒは、変数集合Ｖの１／４のとなり、モジュールＣが必要とするメモリは、変数集合Ｖ内の各要素にそれぞれメモリを割り当てた場合の１／４の大きさですむ。
【０１３９】
次に第２の例として、図２３、２４のように縮退させた変数集合Ｖｒに対して、図１５に示したようなＬｅｆｔ　Ｅｄｇｅ　法を修正したアルゴリズムによる処理を施して変数共有問題を解き、更にモジュールＣが必要とするメモリを小さくした例を示す。
【０１４０】
図２４に示した縮退させた変数集合Ｖｒ内の各変数においても、ライフタイムが重ならなければ、１つのメモリを複数の変数で共有することができる。
図２４に示した、縮退させた変数集合Ｖｒに対して図１５に示した処理を施し、変数の共有問題を解くと以下のように変数がメモリに割り当てられる。
【０１４１】
Ｍｅｍ［０］へは変数ｖ０、ｖ４、ｖ６
Ｍｅｍ［１］へは変数ｖ３２
Ｍｅｍ［２］へは変数ｖ１、ｖ５
Ｍｅｍ［３］へは変数ｖ３３
Ｍｅｍ［４］へは変数ｖ２、ｖ３６
Ｍｅｍ［５］へは変数ｖ３４
Ｍｅｍ［６］へは変数ｖ３、ｖ３７
Ｍｅｍ［７］へは変数ｖ３５
Ｍｅｍ［８］へは変数ｖ３８
Ｍｅｍ［９］へは変数ｖ３９
ここで変数集合Ｖが縮退されている為、メモリＭｅｍ［ｋ］に変数ｖｉ∈Ｐ０が割り当てられているなら、Ｐ１、Ｐ２、Ｐ３中の変数も対応するＰ０中の変数と同じメモリに割り当てられる。
【０１４２】
図２５は、図２４の縮退した変数の集合に対して変数共有問題を解いた後、変数をメモリに割り当てた場合を示す図である。
図２３にあるように元々はサイズ６４の配列変数があり、読み出しと書き込みの順序保証を行う為、モジュールＣは、最大でサイズ１２８のメモリが必要となるところであったのが、図２５に示すように、本実施形態に示した処理を施すことによって、サイズ１０のメモリを持つ構成として合成することができる。
【０１４３】
次に第３の例として変数集合Ｖが縮退できない場合を示す。
以下のようなω（Ａ，ｔＡ　）とγ（Ｂ，ｔＢ　）とで規定されるプロセスＡ，Ｂが与えられた場合を示す。この例はサイズ６４の配列変数をプロセスＡからプロセスＢへ受け渡すことに相当し、Ｔ＝６４である。
【０１４４】
Ｗ（Ａ）＝｛（０，｛０｝），（１，｛１｝），（２，｛２｝），（３，｛３｝），・・・（６３，｛６３｝）｝＝｛ｉ，｛ｉ｝｝｜０≦ｉ≦６３｝
Ｒ（Ｂ）＝｛（０，｛０｝），（１，｛８｝），（２，｛１６｝），（３，｛２４｝），・・・（６３，｛６３｝）｝＝｛ｉ，｛ｉ｝｝｜０≦ｉ≦６３，ｊ＝（ｉ　ｍｏｄ　８）×８＋［ｉ／８］｝（ここでは、［ｉ／８］は、ｉを８で割って小数を切り捨てて整数にした値を表す。）
ここでは、時間の関係式における定数αＣａ＝１、αＣｂ＝１、βＣａ＝０、βＣｂ＝０として、プロセスＣの読み出し系列Ｒ（Ｃ）、書き込み系列Ｗ（Ｃ）を求めると、Ｒ（Ｃ）＝ｗ（Ａ），Ｗ（Ｃ）＝Ｒ（Ｂ）となる。
【０１４５】
プロセスＣの配列変数ｖのライフタイムの解析結果を図２６に示す。
同図においてＢｅｇｉｎ及びＥｎｄは、図１０に示した１次元配列に対応し、Ｂｅｇｉｎはその変数に最初に値の代入が発生した時間、Ｅｎｄは最後に参照が発生時間、添え字は変数の添え字を示している。
【０１４６】
図２７は、図２６を元に、各変数のライフタイムを図形的に表したものである。
本例の場合は、変数集合Ｖに　外８　となるＶの部分集合Ｐ、Ｑが見つけられ
【０１４７】
【外８】
2004054641.tif 000014
【０１４８】
ず、変数集合ｖは縮退することが出来ない。また、変数をＢｅｇｉｎ［ｖ］の昇順に並べ替えても図２３と変わらない。
このような変数集合Ｖに対して、図１５に示したようなＬｅｆｔ　Ｅｄｇｅ　法を修正したアルゴリズムによる処理を施して変数共有問題を解くと、図２４に示すように各変数がメモリへ割り当てられる。
【０１４９】
図２８は、例３における変数のメモリの割り当て状況を示す図である。
同図より変数ｖ０，ｖ４９，ｖ６３，ｖ１１２，ｖ１２１は、メモリの０番目に割り当てる。表現を変えれば、Ａｓｓｉｎ［０］＝０，Ａｓｓｉｎ［４９］＝０，Ａｓｓｉｇｎ［６３］＝０，Ａｓｓｉｇｎ［１１２］＝０，Ａｓｓｉｇｎ［１２１］＝０である、とも言える。
【０１５０】
例３では、変数集合を縮退できなかったため、２倍のサイズの変数集合を扱っている。そのため、もともとあった変数ｖ０〜ｖ６３と、追加の変数ｖ６４〜ｖ１２７の、合計１２８個の変数を同時に扱っている。
【０１５１】
この図２８より、プロセスＣが必要とするメモリサイズがわかる。もともとはサイズ６４の配列変数があり、読み書き競合を防ぐためにはメモリを２倍にして、最大でサイズ１２８のメモリが必要になるところであったが、本発明を適用することにより、サイズ５６のメモリで済ませることができる。
【０１５２】
なお、図２６をみると、変数ｖ５６のライフタイムはＬ（ｖ５６）＝（５６，５６）であり、ｂｅｇｉｎの値とｅｎｄの値が等しい。そのような変数は、メモリに格納することなく、入力ポートから出力ポートへ素通しで出力する。これは、（１）レイテンシを短くするため、（２）バッファとして必要なメモリ量を減らす、という２つの目的がある。これと同様なことが、例１での変数ｖ７にて見られる。
【０１５３】
図２９に第３の例における変数のメモリの割り当て状況を示す。同図は、図２４に示した変数のメモリへの割り当て状況を縦軸にメモリ、横軸に時間を取って示した図である。
【０１５４】
図３０は、図１のＣＡＤシステムを汎用のコンピュータとして実現した場合のコンピュータのシステム環境図である。
同図のコンピュータは、ＣＰＵ２１、各プログラムのワークエリアとなる主記憶装置２２、各プログラムやデータベースが記録されるハードディスク等の補助記憶装置２３、ディスプレイ、キーボード等の入出力装置（Ｉ／Ｏ）２４、モデム等のネットワーク接続装置２５及びディスク、磁気テープなどの可搬記憶媒体から記憶内容を読み出す媒体読取り装置２６を有し、これらが互いにバス２８により接続される構成を備えている。
【０１５５】
ＣＡＤシステムとしての機能や上記したモジュール間インタフェースの自動生成の機能をソフトウエアによって実現した場合、ＣＰＵ２１がプログラムに基いて、主記憶装置２２をワークエリアとして、主記憶装置２２若しくは補助記憶装置２３上の領域に実現されたライブラリ格納部２１からデータを読み出して実現する。
【０１５６】
図３０のコンピュータでは、媒体読取り装置２６により磁気テープ、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ等の記憶媒体２７に記憶されているプログラム、データを読み出し、これを主記憶装置２２または補助記憶装置２３にダウンロードする。そして本実施形態による各処理は、ＣＰＵ２１がこのプログラムやデータを実行することにより、ソフトウエア的に実現させることが出来る。
【０１５７】
また、図３０のコンピュータでは、フレキシブルディスク等の記憶媒体２７を用いてアプリケーションソフトの交換が行われる場合がある。よって、本発明は、モジュール間インタフェースの自動合成装置、合成方法に限らず、コンピュータにより使用されたときに、上述した本発明の実施形態の機能をコンピュータに行わせるためのプログラムやコンピュータ読み出し可能な記憶媒体２７として構成することもできる。
【０１５８】
この場合、「記憶媒体」には、例えば図３１に示されるように、ＣＤ−ＲＯＭ、フレキシブルディスク（あるいはＭＯ、ＤＶＤ、リムーバブルハードディスク等であってもよい）等の媒体駆動装置３７に脱着可能な可搬記憶媒体３６や、ネットワーク回線３３経由で送信される外部の装置（サーバ等）内の記憶手段（データベース等）３２、あるいはコンピュータ３１の本体３４内のメモリ（ＲＡＭ又はハードディスク等）３５等が含まれる。可搬記憶媒体３６や記憶手段（データベース等）３２に記憶されているプログラムは、本体３４内のメモリ（ＲＡＭ又はハードディスク等）３５にロードされて、実行される。
【０１５９】
尚２つの回路モジュール間でデータの受け渡しを行うモジュール間インタフェースは、回路でなくても良い。例えば２つの回路モジュールが、並列実行される計算機で、共有メモリへのアクセスによってデータのやり取りを行う際、図１７，１８に対応するデータメモリへの読み込み／書き込みの情報を２つの計算機に与えることによって、これら計算機はこの情報に基いて共有メモリにアクセスすることによって、共有メモリのデータの受け渡しに用いる領域を小さくすることができる。
【０１６０】
（付記１）　並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成する合成装置であって、
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求める変数算出手段と、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求めるライフタイム算出手段と、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探す縮退集合算出手段と、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する回路合成手段と、
を備えることを特徴とするモジュール間インタフェースの自動合成装置。
【０１６１】
（付記２）　前記縮退された変数集合の要素である変数の前記ライフタイムが重ならないようにメモリに共有させ、前記縮退された変数集合の要素である変数の前記メモリへの割り当てを求める変数割り当て手段を更に備え、前記回路合成手段は前記割り当てに基いて前記モジュール間インタフェースを合成することを特徴とする付記１に記載のモジュール間インタフェースの自動合成装置。
【０１６２】
（付記３）　前記モジュール間インタフェースがデータを読み込んでから書き込むまでの最小の時間である最小遅延時間を求める最小遅延時間算出手段を更に備え、前記回路合成手段は、前記最小遅延時間を考慮して、前記モジュール間インタフェースを合成することを特徴とする付記１又は２に記載のモジュール間インタフェースの自動合成装置。
【０１６３】
（付記４）　前記回路合成手段は、前記縮退させた変数集合から求まる値に基づいて、前記モジュール間インタフェースが有するメモリの大きさを決定することを特徴とする付記１乃至３の何れか１つに記載のモジュール間インタフェースの自動合成装置。
【０１６４】
（付記５）　回路記述言語による記載を解析し、回路の仕様を出力するコンパイラ手段と、
前記コンパイラ手段から、並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成を依頼されると、該モジュール間インタフェースを合成するインタフェースモジュール生成手段とを備え、
前記インタフェースモジュール生成手段は、
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求める変数算出手段と、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求めるライフタイム算出手段と、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探す縮退集合算出手段と、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する回路合成手段と、
を有することを特徴とするＣＡＤシステム。
【０１６５】
（付記６）　並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成する合成方法であって、
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求め、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求め、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探し、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する
ことを特徴とする合成方法。
【０１６６】
（付記７）　並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成するコンピュータによって実行されるプログラムであって
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求め、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求め、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探し、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する
ことを前記コンピュータに実行させるプログラム。
【０１６７】
（付記８）　前記縮退された変数集合の要素である変数の前記ライフタイムが重ならないようにメモリに共有させ、前記縮退された変数集合の要素である変数の前記メモリへの割り当てを求め、前記割り当てに基いて前記モジュール間インタフェースを合成することを前記コンピュータに実行させる付記７に記載のプログラム。
【０１６８】
（付記９）　Ｌｅｆｔ　Ｅｄｇｅ　法に基いて、前記縮退された変数集合の要素である変数の前記ライフタイムが重ならないようにメモリに共有させ、前記縮退された変数集合の要素である変数の前記メモリへの割り当てを求めることを特徴とする付記８に記載のプログラム。
【０１６９】
（付記１０）　前記メモリへの割り当てに基づいて、前記モジュール間インタフェースが有するメモリの大きさを決定することを前記コンピュータに実行させる付記８又は９に記載のプログラム。
【０１７０】
（付記１１）　前記モジュール間インタフェースがデータを読み込んでから書き込むまでの最小の時間である最小遅延時間を求め、該最小遅延時間を考慮して、前記モジュール間インタフェースを合成することを前記コンピュータに実行させる付記７乃至１０の何れか１つに記載のプログラム。
【０１７１】
（付記１２）　前記最小遅延時間を考慮して、前記モジュール間インタフェースが有するメモリの大きさを決定することを前記コンピュータに実行させる付記１０に記載のプログラム。
【０１７２】
（付記１３）　前記縮退させた変数集合から求まる値に基づいて、前記モジュール間インタフェースが有するメモリの大きさを決定することを前記コンピュータに実行させる付記７乃至１２の何れか１つに記載のモジュール間インタフェースの自動合成装置。
【０１７３】
（付記１４）　前記モジュール間インタフェースへのデータの書き込みを行う前記回路モジュール、前記モジュール間インタフェースへのデータの読み出しを行う前記回路モジュール及び前記モジュール間インタフェースに対してそれぞれの同期信号に基いた時刻を設定し、前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析する際、前記書き込みを行う回路モジュール及び読み出しを行う前記回路モジュールの時刻を前記モジュール間インタフェースの時刻に変換することを前記コンピュータに実行させることを特徴とする付記７乃至１３の何れか１つに記載のプログラム。
【０１７４】
（付記１５）　並列に動作する複数の回路モジュールの間のデータの受け渡しを行うモジュール間インタフェースを合成するコンピュータによって使用された時、
前記回路モジュールによる前記モジュール間インタフェースへのデータの書き込み及び読み出しを解析し、該解析の結果に基いて前記モジュール間インタフェースが持つ変数を求め、
前記モジュール間インタフェースが持つ変数に対して、最初にデータが書き込まれてから最後に読み出されるまでの期間を示すライフタイムを求め、
前記変数を要素として持つ集合を整数分割して得られる部分集合で、要素となる変数の全てに対し、当該要素となる変数の前記ライフタイムと特定の時間ずれた前記ライフタイムを持つ変数が、前記分割して得られる他の部分集合に存在する縮退させた変数集合を探し、
前記縮退させた変数集合を用いて、変数の割り当てを元に前記モジュール間インタフェースを合成する
ことを前記コンピュータに実行させるプログラムを記憶した前記コンピュータが読み出し可能な可搬記憶媒体。
【０１７５】
【発明の効果】
本発明によれば、従来手法よりも使用するメモリ量を少なくしたモジュール間インタフェースを自動的に合成することができる。
【０１７６】
またこのモジュール間インタフェースを自動的に合成することができるので、手作業で設計することによるミスを防げる。
【図面の簡単な説明】
【図１】本実施形態におけるＣＡＤシステムの構成を示す図である。
【図２】インタフェースモジュール生成部が行う処理を示す図である。
【図３】インタフェースモジュール生成部で扱われるプロセスの例を示す図である。
【図４】インタフェース回路モジュールの実現例を示す図（その１）である。
【図５】インタフェース回路モジュールの実現例を示す図（その２）である。
【図６】読み出し系列／書き込み系列のデータ構造例を示す図である。
【図７】（ａ）はプロセスＡの書き込み系列をプロセスＣの読み出し系列に変換する処理を示すフローチャート、（ｂ）はその変換例を示す図である。
【図８】（ａ）はプロセスＢの読み出し系列をプロセスＣの書き込み系列に変換する処理を示すフローチャート（ｂ）はその変換例を示す図である。
【図９】最小出力遅延ｔｃｏｄｅｌａｙを求める処理を示すフローチャートである。
【図１０】変数のライフタイムｂｅｇｉｎ（ｖ［ｉ］），ｅｎｄ（ｖ［ｉ］）のデータ構造を示す図である。
【図１１】ライフタイムを求める処理を示すフローチャートである。
【図１２】縮退された変数集合を示す図である。
【図１３】縮退させた変数集合Ｖｒを求める処理を示すフローチャートである。
【図１４】ステップＳ４６の判断処理の詳細を示すフローチャートである。
【図１５】変数共有問題を解く処理を示すフローチャートである。
【図１６】ＲＴＬ生成を行うアルゴリズムを示す図である。
【図１７】入力ポートの読み出しを行うサブプロセスのＲＴＬコードの例を示す図である。
【図１８】出力ポートの書き込みを行うサブプロセスのＲＴＬコードの例を示す図である。
【図１９】２つのサブプロセスをまとめたＲＴＬコードの模擬的な例を示す図である。
【図２０】出力遅延の説明図（その１）である。
【図２１】出力遅延の説明図（その２）である。
【図２２】例１における配列変数のライフタイムの解析結果を示す図である。
【図２３】例１における配列変数のライフタイムを示す図である。
【図２４】例１における変数集合から求めた縮退させた変数集合の例を示す図である。
【図２５】例２における変数のメモリへの割り当てを示す状況を示す図である。
【図２６】例３における配列変数のライフタイムの解析結果を示す図である。
【図２７】例３における配列変数のライフタイムを示す図である。
【図２８】第３の例における変数のメモリの割り当て結果を示す図である。
【図２９】第３の例における変数のメモリの割り当て状況を示す図である
【図３０】本実施形態におけるコンピュータのシステム環境図である。
【図３１】媒体例を示す図である。
【図３２】高位合成による回路設計で用いられる回路記述言語による動作記述例を示す図である。
【符号の説明】
１　ＣＡＤシステム
１１　入力編集部
１２　コンパイラ部
１３　ライブラリ格納部
１４　インタフェースモジュール生成部
１５　出力部
２１　ＣＰＵ
２２　主記憶装置
２３　補助記憶装置
２３　入出力装置
２５　ネットワーク接続装置
２６　媒体読取装置
２７　記憶媒体
２８　バス
３１　情報処理装置
３２　記憶手段
３３　ネットワーク回線
３４　本体
３５　メモリ
３６　可搬記憶媒体
【図１】
2004054641.tif 000015
【図２】
2004054641.tif 000016
【図３】
2004054641.tif 000017
【図４】
2004054641.tif 000018
【図５】
2004054641.tif 000019
【図６】
2004054641.tif 000020
【図７】
2004054641.tif 000021
【図８】
2004054641.tif 000022
【図９】
2004054641.tif 000023
【図１０】
2004054641.tif 000024
【図１１】
2004054641.tif 000025
【図１２】
2004054641.tif 000026
【図１３】
2004054641.tif 000027
【図１４】
2004054641.tif 000028
【図１５】
2004054641.tif 000029
【図１６】
2004054641.tif 000030
【図１７】
2004054641.tif 000031
【図１８】
2004054641.tif 000032
【図１９】
2004054641.tif 000033
【図２０】
2004054641.tif 000034
【図２１】
2004054641.tif 000035
【図２２】
2004054641.tif 000036
【図２３】
2004054641.tif 000037
【図２４】
2004054641.tif 000038
【図２５】
2004054641.tif 000039
【図２６】
2004054641.tif 000040
【図２７】
2004054641.tif 000041
【図２８】
2004054641.tif 000042
【図２９】
2004054641.tif 000043
【図３０】
2004054641.tif 000044
【図３１】
2004054641.tif 000045
【図３２】
2004054641.tif 000046