JP3722351B2 - 高位合成方法およびその実施に使用される記録媒体 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明はＬＳＩの動作記述からディジタル回路を自動合成する高位合成方法およびその実施に使用される記録媒体に関する。
【０００２】
【従来の技術】
従来から、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔｓ：特定用途向けＩＣ）の設計等、短期間の設計を要求される場合に、高位合成方法が特に有効な技術として知られている。
【０００３】
高位合成とは、ハードウェアの構造に関する情報を含まずに、処理のアルゴリズムのみを記述した動作記述から、回路を自動的に合成する技術である。なお、高位合成技術の詳細を記した文献としては、「Ｋｌｕｗｅｒ ＡｃａｄｅｍｉｃＰｕｂｌｉｓｈｅｒｓ」による「Ｈｉｇｈ Ｌｅｖｅｌ Ｓｙｎｔｈｅｓｉｓ」等がある。
【０００４】
以下、例えば、次の（１）式に示す動作記述から回路を自動的に高位合成する方法について説明する。
【０００５】
ｘ＝（ａ＋ｂ）＊（ｂ＋ｃ） …（１）
高位合成方法は、通常、図１に示すフローチャートの手順に従って実施され、まず、動作記述の実行の制御の流れと、データの流れとを解析し、ＣＤＦＧ（Ｃｏｎｔｒｏｌ Ｄａｔａ Ｆｌｏｗ Ｇｒａｐｈ）と呼ばれるモデルに変換する（図１のステップＳ１参照）。ＣＤＦＧとは、プログラムのフローチャートに類似したグラフである。ＣＤＦＧは、節点と入出力枝とによって構成される。入出力枝は、データまたはコントロール信号を表し、節点は演算を表わす。演算の入出力は、節点の入出力枝に対応する。
【０００６】
例えば、（１）式に示す動作記述は、図２に示すＣＤＦＧで表わされる。図２のＣＤＦＧは、加算を表わす２つの第１および第２の加算節点１１および１２と、乗算を表わす１つの乗算節点１３を含み、入力「ａ」および「ｂ」を加算した結果と、入力「ｂ」および「ｃ」を加算した結果とを乗算し、その結果が出力「ｘ」であることを表している。
【０００７】
（１）式に示す動作記述が図２に示すＣＤＦＧに変換されると、スケジューリングが実施される（図１のステップＳ２参照）。スケジューリングとは、ＣＤＦＧの節点に対応する演算をいつ実行するか、すなわち、どのクロックステップで実行するかを決定することである。この場合に、各演算の遅延時間を考慮して、全ての節点がクロック周期内に収まるようにする必要がある。
【０００８】
図２のＣＤＦＧをスケジューリングした一例を図３に示す。図３のスケジューリング結果では、２つの加算と１つの乗算を、１つのクロックステップ（ｓｔｅｐ１）で実行するようスケジューリングされている。この場合、データ依存関係にある演算の遅延時間の合計は、１つのクロックステップのステップ周期を超えないようにスケジューリングされる。例えば、加算器の遅延時間が５（ｎｓｅｃ）、乗算器の遅延時間が６０（ｎｓｅｃ）の場合、クロック周期が６５（ｎｓｅｃ）以上の場合には、図３に示すように、１つのクロックステップ（ｓｔｅｐ１）に全ての演算をスケジューリングすることができる。
【０００９】
また、異なるクロックステップにそれぞれスケジューリングされた同一の演算は、1つの演算器によって実行することができる。このために、図５に示すように、第１の加算を示す第１の加算節点１１と、第２の加算を示す第２の加算節点１２とを、異なるクロスステップｓｔｅｐ１およびにｓｔｅｐ２にてスケジューリングして、1つの加算器を生成することもできる。この場合、前述したように、クロック周期が６５（ｎｓｅｃ）以上であれば、遅延時間が５（ｎｓｅｃ）の第２の加算と、遅延時間が６０（ｎｓｅｃ）の乗算とを、第２のクロスステップｓｔｅｐ２にスケジューリングしても問題はない。
【００１０】
動作記述がスケジューリングされると、アロケーションが実行される（図１のステップＳ３参照）。アロケーションとは、スケジューリングされたＣＤＦＧの実行に必要な演算器およびレジスタをそれぞれ生成して、ＣＤＦＧの演算に演算器を割り当て、また、隣接するクロックステップの境界を横切る入出力枝に、レジスタ、セレクタ等を割り当てる処理である。そして、アロケーション処理することによって、（１）式に示す動作記述を実行する回路が生成される（図１のステップＳ４参照）。
【００１１】
図３のスケジューリング結果は、図４に示すように、第１および第２の加算に対して、第１の加算器１４および１５がそれぞれ生成されて、第１および第２の加算節点１１および１２に割り当てられるとともに、乗算に対して乗算器１６が生成されて、乗算節点１３に割り当てられる。この場合、隣接するクロックステップの境界を横切る入出力枝が存在しないために、レジスタおよびセレクタは生成されない。
【００１２】
これに対して、図５のスケジューリング結果では、図６に示すように、異なるクロックステップｓｔｅｐ１および２に、第１および第２の加算に対する第１および第２の加算節点１１および１２がそれぞれスケジューリングされているために、これらの加算節点１１および１２に対して、１つの加算器１４のみが生成される。また、クロックステップｓｔｅｐ１およびｓｔｅｐ２の境界を横切る入出力枝２１および２２が存在するために、各入出力枝２１および２２に対して、セレクタ（図において「ｓｅｌ」で示す）２３およびレジスタ（図においては、「ｒｅｇ」で示す）２４がそれぞれ生成される。
【００１３】
図６に示す回路では、入力「ａ」および「ｂ」がセレクタ２３にそれぞれ入力されて、セレクタ２３の出力が加算器１４に与えられている。加算器１４には、入力「ｂ」も与えられており、加算器１４の出力が、レジスタ２４および乗算器１６にそれぞれ与えられている。この場合、生成されたセレクタ２３およびレジスタ２４それぞれに対するコントロール信号を生成するコントローラ（図において「ｃｏｎｔｒｏｌｌｅｒ」で示す）２５が生成される。コントローラ２５は、セレクタ２３に対してセレクタ信号ｋ１を出力し、セレクタ２３は、セレクト信号ｋ１が「１」の場合に入力「ａ」を、セレクト信号ｋ１が「０」の場合に入力「ｂ」をそれぞれ出力する。また、コントローラ２５は、レジスタ２４に対してイネーブル信号ｋ２を出力し、レジスタ２４は、イネーブル信号ｋ２が「１」の場合に、クロックが立ち上がる瞬間の入力の値を記憶し、イネーブル信号ｋ２が「０」の場合には、記憶している値を保持して、その保持された値を出力する。
【００１４】
図６の回路の動作を説明する。クロックステップｓｔｅｐ１では、セレクト信号ｋ１とイネーブル信号ｋ２は、共に「１」とされ、セレクタ２３は、入力「ａ」を選択して加算器１４に出力する。これにより、加算器１４は、各入力「ａ」および「ｂ」の加算値「ａ＋ｂ」をレジスタ２４に出力する。レジスタ２４は、イネーブル信号ｋ２が「１」であるために、レジスタ２４の出力「ａ＋ｂ」が記憶される。
【００１５】
クロックステップｓｔｅｐ２では、セレクト信号ｋ１およびイネーブル信号ｋ２は、共に「０」とされ、セレクタ２３は、入力「ｃ」を選択して加算器１４に出力する。これにより、加算器１４は、各入力「ｃ」および「ｂ」の加算値「ｃ＋ｂ」を乗算器２４に出力する。この場合、レジスタ２４に対するイネーブル信号ｋ２が「０」になっているために、保持されている値「ａ＋ｂ」を乗算器１６に出力する。乗算器１６は、与えられる値「ｃ＋ｂ」および「ａ＋ｂ」を乗算して、その積をｘとして出力する。
【００１６】
図４に示す回路では、１クロックステップ（たとえば１００ｎｓｅｃ内）によって動作記述の処理が終了するが、２つの加算器１４および１５が２つ必要である。これに対して、図６に示す回路では、２クロックステップ（たとえば２００ｎｓｅｃ）が必要であるが、１つの加算器１４を使用するだけでよい。このように、高位合成方法では、高速な回路が必要な場合には、図４に示す回路、小面積な回路が必要な場合には、図６に示す回路がそれぞれ生成される。
【００１７】
図５に示すスケジューリング結果では、２つの加算を１つの加算器で実行できることが理解される。しかしながら、演算が多くなると、どの演算とどの演算を１つの演算器で実行するかを決定する手順が必要になる。この手順がアロケーションである。スケジューリング、アロケーションは、高位合成の分野では周知である（前述の「Ｈｉｇｈ Ｌｅｖｅｌ Ｓｙｎｔｈｅｓｉｓ」参照）。
【００１８】
次に、動作記述が条件分岐を含む場合について説明する。条件分岐を含む動作記述を高位合成する方法は、条件分岐を制御するためのコントロール信号を生成する必要があるが、基本的には、条件分岐を含まない図１の高位合成方法と同様である。この方法としては、例えば、特開平１１−２５０１１２号公報に開示されている。
【００１９】
以下、図７に示す条件分岐を含む動作記述の高位合成方法について説明する。図７に示す動作記述では、条件（ｉｆ）「ｄ＞ｅ」の場合は、ｘ＝ａ−ｂであり、その他の条件の場合（ｅｌｓｅ）は、ｘ＝ａ＊（ｂ−ｃ）である。この場合のＣＤＦＧをスケジューリングすると、図８に示すように、条件分岐としてＩＦ節点３２を含むものとなる。
【００２０】
図８に示すように、クロックステップｓｔｅｐ１には、比較を示す比較節点３１がスケジューリングされており、クロックステップｓｔｅｐ２には、ＩＦ節点３２がスケジューリングされている。比較節点３１には、入力「ｄ」および「ｅ」からの入出力枝が接続されており、また、コントロール信号ｋを与えるコントロール入出力枝３３が接続されている。図８では、コントロール入出力枝３３を点線で表している。
【００２１】
また、クロックステップｓｔｅｐ２にスケジューリングされたＩＦ節点３２は、内部に第１および第２の副ＣＤＦＧ３４および３５を有している。第１の副ＣＤＦＧ３４は、ＩＦ節点を含むことができる。第１の副ＣＤＦＧ３４は、コントロール信号ｋが「１」（真）の時に実行され（「ｔｒｕｅ」で表す）、第２の副ＣＤＦＧ３５は、コントロール信号ｋが「０」（偽）の時に実行される（「ｆａｌｓｅ」で表す）。このように、比較節点３１およびＩＦ節点３２は、コントローラが必要になるために、それぞれ異なるクロックステップにスケジューリングされている。
【００２２】
「ｔｒｕｅ」で表された副ＣＤＦＧ３４は、入力「ａ」および「ｂ」が入力される第１の減算節点３６が設けられており、「ｆａｌｓｅ」で表される副ＣＤＦＧ３５には、第２の減算節点３７および乗算節点３８がそれぞれ設けられている。第２の減算節点３７には、入力「ｂ」および「ｃ」からの入出力枝が接続されており、乗算節点３８には、入力「ａ」および第１の減算節点３７からの入出力枝が接続されいる。各副ＣＤＦＧ３４および３５は、同時に実行されないため、それぞれに設けられた第１および第２の各減算節点３６および３７に対して１つの減算器４５（図９参照）がアロケーションされる。
【００２３】
図８に示すスケジューリング結果を実行する回路は、図９のようになる。図９に示す回路では、比較節点３１として、比較器４１がアロケーションされており、入力「ａ」および「ｂ」に対しては第１のセレクタ４３が、また、入力「ｂ」および「ｃ」に対しては、第２のセレクタ４４が割り当てられている。また、第１および第２の減算節点３６および３７に対して、１つの減算器４５が割り当てられており、乗算節点３８に対して乗算器４６が割り当てられている。そして、減算器４５および乗算器４６の出力に対して第３のセレクタ４７が割り当てられている。第１〜第３の各セレクタ４３、４４、４７は、コントローラ４２からのコントロール信号ｋによって、それぞれ制御される。コントロール信号ｋが値「１」の場合には、第１のセレクタ４３は、入力「ａ」、第２のセレクタ４４は、入力「ｂ」、第３のセレクタ４７は、減算器４５の出力を、それぞれ選択する。
【００２４】
このような回路の動作について説明する。クロックステップｓｔｅｐ１において、入力「ｄ」および「ｅ」が、比較器４１により比較され、その結果が、コントローラ４２に入力される。コントローラ４２は、比較器４１から入力される比較結果に基づいて、コントロール信号ｋを生成し、次のクロックステップｓｔｅｐ２において出力する。コントロール信号ｋは、比較器４１の比較結果が、「ｄ＜ｅ」の場合には、値「１」（真）を出力し、それ以外の場合には、値「０」（偽）を出力する。クロックステップｓｔｅｐ２において、コントロール信号ｋが値「１」の場合には、第１および第２のセレクタ４１および４２は、それぞれ、入力「ａ」および「ｂ」を選択するために、減算器４５は、「ａ−ｂ」の減算を実行し、第３のセレクタ４７は、減算器４５の出力を選択して、減算器４５による減算結果「ａ−ｂ」が出力「ｘ」とされる。
【００２５】
これに対して、コントロール信号ｋの値が「０」の場合には、第１および第２のセレクタ４３および４４は、入力「ｂ」および「ｃ」をそれぞれ選択して、減算器４５は、「ｂ−ｃ」の減算を実行する。そして、この減算結果が、乗算器４６に与えられて、乗算器は、減算器４５による減算結果と、入力「ａ」との乗算結果を第３のセレクタ４７に出力する。第３のセレクタ４７は、乗算器４６の出力を選択して、乗算器４６による乗算「ａ＊（ｂ−ｃ）」が出力「ｘ」とされる。
【００２６】
【発明が解決しようとする課題】
高位合成方法におけるスケジューリングおよびアロケーションは、非常に複雑な処理である。このため、１つの動作記述が多数の演算を含む場合、ＣＤＦＧ中の節点数が多数になり、計算機を用いて高位合成を行う場合に、非常に長い処理時間が必要になる。
【００２７】
また、高位合成に際しては、ＣＤＦＧ中の各節点の遅延時間に対応する演算器の遅延時間に基づいて、演算時間が算出される。例えば、図１０に示すように、クロック周期の時間が、例えば１０（ｎｓｅｃ）内に、遅延時間が２（ｎｓｅｃ）の第１および第２の「ＮＯＴ」節点５１および５２と、遅延時間が８（ｎｓｅｃ）の「ＡＮＤ」節点５３がスケジューリングされている場合に、このスケジューリング結果に対応する回路は、図１１（ａ）のように、「ＮＯＴ」節点５１および５２に対して「ＮＯＴ」演算器５４および５５がそれぞれ割り当てられるとともに、「ＡＮＤ」節点５３に、「ＡＮＤ」演算器５６が割り当てられる。
【００２８】
この場合、論理合成によって、図１１（ｂ）に示すように、一対の「ＮＯＴ」演算器５１および５２と、１つの「ＡＮＤ」演算器とが、１つの「ＮＯＲ」演算器５７に最適化される可能性がある。その結果、１つの「ＮＯＲ」演算器５７の遅延時間は６（ｎｓｅｃ）になり、高位合成時において見積もられた遅延時間１０（ｎｓｅｃ）とは誤差が生じることになる。すなわち、高位合成時においては、遅延時間を必要以上に大きく見積ることになり、ＣＤＦＧ全体をスケジューリングした際に、必要なステップ数が必要以上に増加することになり、生成される回路の動作が遅くなる可能性がある。
【００２９】
さらに、高位合成では、図６に示すように、演算器である加算器１４の前にセレクタ２３が挿入される可能性があるが、このように、セレクタ２３が加算器１４等の演算器の前に挿入されることにより、遅延時間が増加して、回路が正常に動作しなくなるおそれがある。
【００３０】
また、図７に示すように、条件分岐を含む動作記述を高位合成する場合に、条件分岐節点の入出力枝が多数になっていると、図９に示すように、合成した回路が多数のセレクタを含むことになり、回路規模が大きくなるという問題もある。
【００３１】
さらにまた、図９に示すように、条件分岐のコントロール信号をコントローラ４２で生成する場合は、コントローラ４２は、通常、クロックに同期して動作するため、条件分岐本体を実行する前のクロックステップにおいて、条件を決定しておく必要がある。従って、条件分岐のコントロール信号を生成するクロックステップと、条件分岐本体を実行するクロックステップとを、図８に示すように、別にする必要がある。その結果、回路動作を高速化することができなくなるおそれもある。
【００３２】
本発明は、このような問題を解決するものであり、その目的は、高位合成に必要な処理時間を短くすることができるとともに、高位合成時において、遅延時間の見積り精度を高めることができ、また、高位合成した回路の動作速度を速くすることができるとともに、高位合成した回路の規模を小さくすることができる高位合成方法を提供することにある。
【００３３】
【課題を解決するための手段】
本発明の高位合成方法は、処理の動作のみを記述した動作記述を、演算を示す節点とデータの流れを示す入出力枝とによって構成されるコントロールデータフローグラフ（ＣＤＦＧ）を作成するＣＤＦＧ作成部と、該ＣＤＦＧ作成部にて生成されたＣＤＦＧの一部を論理合成する論理合成部と、該論理合成部の論理合成に基づいて前記ＣＤＦＧ部にて作成されたＣＤＦＧを変更するＣＤＦＧ変更部と、該ＣＤＦＧ変更部にて変更されたＣＤＦＧの前記節点に対応する前記演算をスケジューリングするスケジューリング部と、該スケジューリング部にてスケジューリングされたＣＤＦＧの前記節点に対応する前記演算の実行に必要な演算器、セレクタ等の素子をそれぞれ割り当てるアロケーション部とを有する高位合成装置によって回路を自動合成する高位合成方法であって、前記ＣＤＦＧ作成部によって、前記動作記述に条件分岐が含まれる場合に、該条件分岐において条件が成立する場合の真の処理と該条件が成立しない場合の偽の処理とを有する部分ＣＤＦＧを生成するＣＤＦＧ生成工程と、前記論理合成部によって、前記ＣＤＦＧ生成工程にて生成された部分ＣＤＦＧを論理合成する論理合成工程と、前記ＣＤＦＧ変換部によって、前記論理合成工程にて論理合成して得られる組合せ論理回路を１つの節点として扱って前記ＣＤＦＧ生成工程にて生成されたＣＤＦＧを変更するＣＤＦＧ変更工程と、前記スケジューリング部によって、前記組合せ論理回路に対応する節点を、前記条件分岐に対応した節点と同一のクロックステップにスケジューリングする工程と、を包含することを特徴とする。
【００３４】
また、本発明の高位合成方法は、処理の動作のみを記述した動作記述を、演算を示す節点とデータの流れを示す入出力枝とによって構成されるコントロールデータフローグラフ（ＣＤＦＧ）を作成するＣＤＦＧ作成部と、該ＣＤＦＧ作成部にて生成されたＣＤＦＧの一部を論理合成する論理合成部と、該論理合成部の論理合成に基づいて前記ＣＤＦＧ部にて作成されたＣＤＦＧを変更するＣＤＦＧ変更部と、該ＣＤＦＧ変更部にて変更されたＣＤＦＧの前記節点に対応する前記演算をスケジューリングするスケジューリング部と、該スケジューリング部にてスケジューリングされたＣＤＦＧの前記節点に対応する前記演算の実行に必要な演算器、セレクタ等の素子をそれぞれ割り当てるアロケーション部とを有する高位合成装置によって回路を自動合成する高位合成方法であって、前記ＣＤＦＧ作成部によって、前記動作記述に条件分岐が含まれる場合に、該条件分岐において条件が成立する場合の真の処理と該条件が成立しない場合の偽の処理とを有する部分ＣＤＦＧを生成するＣＤＦＧ生成工程と、前記論理合成部によって、前記ＣＤＦＧ生成工程にて生成された部分ＣＤＦＧを予め論理合成する論理合成工程と、前記ＣＤＦＧ変換部によって、前記論理合成工程にて論理合成して得られる組合せ論理回路を１つの節点として扱って前記ＣＤＦＧ生成工程にて生成されたＣＤＦＧを変更するＣＤＦＧ変更工程と、前記スケジューリング部によって、前記組合せ論理回路における前記真の処理と前記偽の処理とが同一のクロックステップにて終了するように、該組合せ論理回路の節点をスケジューリングする工程と、を包含することを特徴とする。
【００３５】
前記論理合成工程において、部分ＣＤＦＧを、コントローラの制御が必要な節点を除いて論理合成し、前記ＣＤＦＧ変換工程において、前記組合せ論理回路と、前記コントローラの制御が必要な節点とを組み合わせてＣＤＦＧを変更する構成であってもよい。
【００３６】
また、本発明の高位合成方法は、処理の動作のみを記述した動作記述を、演算を示す節点とデータの流れを示す入出力枝とによって構成されるコントロールデータフローグラフ（ＣＤＦＧ）を作成するＣＤＦＧ作成部と、該ＣＤＦＧ作成部にて作成されたＣＤＦＧに含まれる節点を、特定された節点の前記ＣＤＦＧの上流側と下流側とにおいてそれぞれグループ化する節点グループ化部と、該節点グループ化部にてそれぞれグループ化された各グループをそれぞれ１つの節点として分割して、前記特定された節点と組み合わせてＣＤＦＧとする分割部と、該分割部にて生成されたＣＤＦＧの前記各節点に対応する前記演算をスケジューリングするスケジューリング部と、該スケジューリング部にてスケジューリングされたＣＤＦＧの前記各節点に対応する前記演算の実行に必要な演算器、セレクタ等の素子をそれぞれ割り当てるアロケーション部とを有する高位合成装置によって回路を自動合成する高位合成方法であって、前記節点グループ化部によって、前記アロケーション部において割り当てられる演算器の回路面積が、他の節点に対して割り当てられる演算器の回路面積よりも大きい節点を前記特定された節点とすることを特徴とする。
【００３７】
前記回路面積の大きな演算器の節点が複数であって、それぞれの節点に対応する演算が同一の場合に、前記ＣＤＦＧ変換部によって、前記複数の節点が１つの節点に共通化する構成であってもよい。
【００３８】
前記アロケーション部において前記組合せ論理回路に同一の演算器が複数割り当てられる場合に、その１つの演算器の面積がセレクタの面積の定数倍以上の場合に、前記ＣＤＦＧ変換工程において、その演算器に対応する節点を、前記組合せ論理回路と組合せてＣＤＦＧを変更する構成であってもよい。
【００３９】
本発明のコンピュータ読み取り可能な記録媒体は、前記高位合成方法の手順がプログラムされていることを特徴とする。
【００４０】
【発明の実施の形態】
本発明の実施の一形態について図面に基づいて説明する。
【００４１】
＜実施の形態１＞
本実施の形態の高位合成方法は、図１２に示すフローチャートの手順に従って実施される。以下、図７に示す動作記述に基づいて高位合成を行なう場合について説明する。図７に示す動作記述は、条件（ｉｆ）「ｄ＞ｅ」の場合は、ｘ＝ａ−ｂであり、その他の条件の場合（ｅｌｓｅ）は、ｘ＝ａ＊（ｂ−ｃ）である。
【００４２】
本実施の形態の高位合成方法では、まず、このような動作記述の制御の流れと、データの流れとを解析して、動作記述を、ＣＤＦＧ（Ｃｏｎｔｒｏｌ Ｄａｔａ Ｆｌｏｗ Ｇｒａｐｈ）と呼ばれるモデルに変換する（図１２のステップＳ１１参照、以下同様）。そして、ＣＤＦＧの一部を論理合成することによって（ステップＳ１２）、ＣＤＦＧを変更する（ステップＳ１３）。その後は、従来の高位合成方法と同様に、変更されたＣＤＦＧをスケジューリングし（ステップＳ１４）、その後にアロケーションすることによって（ステップＳ１５）、回路を生成する（ステップＳ１６）。
【００４３】
図７に示す動作記述のＣＤＦＧをスケジューリングすると、図８に示すように、条件分岐としてＩＦ節点３２を含むものとなる。図８に示すスケジューリング結果は、従来技術において説明した通りであるので、その説明を省略する。
【００４４】
本実施の形態では、図８に示すスケジューリング結果において、ＣＤＦＧの一部であるＩＦ節点３２内を論理合成して組合せ論理回路を生成する。図１３は、ＩＦ節点３２において、論理合成して生成された組合せ論理回路を示している。
【００４５】
図１３に示す第１の部分回路６１は、ＩＦ節点３２の条件が「真」の場合に実行される副ＣＤＦＧ３４（図８参照）を、組合せ論理回路で実現したものである。この第１の部分回路６１には、第１の減算器６３が設けられており、第１の減算器６３に、入力「ａ」および「ｂ」がそれぞれ入力されている。
【００４６】
また、図１３に示す第２の部分回路６２は、ＩＦ節点３２の条件が「偽」の場合に実行される副ＣＤＦＧ３５（図８参照）を、組合せ論理回路で実現したものである。この第２の部分回路６２には、第２の減算器６４および乗算器６５がそれぞれ設けられており、第２の減算器６４に、入力「ｂ」および「ｃ」が入力されている。乗算器６５には、入力「ａ」と第２減算器６４の出力とが、入力されている。
【００４７】
また、第１の減算器６３の出力は、第１の部分回路６１の出力になっており、乗算器６５の出力は、第２の部分回路６２の出力になっている。そして、第１および第２の部分回路６１および６２の出力が、セレクタ６６に入力されており、セレクタ６６の出力が回路全体の出力とされている。セレクタ６６のセレクト信号ｋは、ＩＦ節点３２のコントロール入力が、コントローラを介することなく直接セレクト６６に入力されている。
【００４８】
次に、ＩＦ節点３２内を論理合成して得られる組合せ論理回路に対応する節点を準備する。図１３に示すＩＦ節点３２は、図１４に示すように、ＣＩＦ（Ｃｏｍｂｉｎａｔｉｏｎａｌ ＩＦ）節点６７とされる。このＣＩＦ節点６７は、ＩＦ節点３２の組合せ論理回路における４つの入力「ｋ」、「ａ」、「ｂ」「ｃ」と１つの出力「ｘ」に対応して、４つの入力枝と１つの出力枝が設けられる。
【００４９】
図１３に示す回路は、組合せ論理回路であるため、ＣＤＦＧにおいては、加算や減算などの演算と同様に扱うことができる。
【００５０】
図８に示すＣＤＦＧのＩＦ節点３２を、図１４に示すＣＩＦ節点６７に置き換えると、図１５に示すＣＤＦＧとなる。図８のＣＤＦＧは、比較の節点３１、２つの減算節点３６および３７、乗算節点３８、および、ＩＦ節点３１の合計５つの節点を含むのに対して、ＩＦ節点３２をＣＩＦ節点６７に置き換えることによって、図１５に示すＣＤＦＧでは、比較節点３１とＣＩＦ節点６７の２つの節点しか含まない。このように、本実施の形態によりＣＤＦＧに含まれる節点数が減少し、高位合成時のスケジューリング、アロケーションなどの処理に必要な時間を短くすることができる。
【００５１】
また、図１５に示すＣＩＦ節点６７に対応する回路は既に論理合成されているため、図１３に示す回路における各入力「ａ」、「ｂ」、「ｃ」、「ｋ」から出力「ｘ」への遅延時間として、セレクタ６６の遅延時間も含めて、論理最適化後の最終的な値が求まる。よって、図１４に示すＣＩＦ節点６７の遅延時間は正確なものであり、図１５において，１クロックステップにスケジューリングされた節点の遅延時間の合計が、クロック周期よりも大きくなって回路が誤作動するおそれがなく、反対に、クロック周期よりも小さくなり過ぎることによって、回路の動作に無駄が生じて、回路の動作が遅くなるおそれもない。
【００５２】
さらに、図８に示すＣＤＦＧのＩＦ節点３２には、コントロール入力枝３３が設けられているために、ＩＦ節点３２のコントロール信号ｋを生成する比較節点３１とＩＦ節点３２とは別のクロックステップにスケジューリングする必要がある。これに対して、図１４に示すＣＩＦ節点６７では、コントロール信号ｋがコントロールを介さない通常の入力枝３３によって与えられるため、加算や乗算などの通常の演算の節点と同じようにスケジューリングすることができる。このため、図１５に示すように、コントロール信号ｋを生成する比較節点３１とＣＩＦ節点６７とを同一のクロックステップにスケジューリングすることができる。これにより、生成される回路の動作が高速化される。
【００５３】
図１５に示すスケジューリング結果から、図１６に示す回路が得られる。図１６において、点線で示す回路６８は、図１４に示すＣＩＦ節点６７に対応する組合せ論理回路（図１３のＩＦ節点３２に対応）である。
【００５４】
本実施の形態の高位合成方法では、ＣＩＦ節点６７に対応する回路を予め論理合成するため、ＣＩＦ節点６７内で使われる演算器を他の演算で用いられる演算器と共通化することはできない。しかし、本実施の形態の高位合成方法では、ＣＩＦ節点６７に対応する組合せ論理回路がセレクタを必要としないため、演算器を共通化できないことによって回路規模が大きくなることよりも、セレクタを減少させることによって回路規模が小さくなることが有利になる場合には、好適である。
【００５５】
例えば、従来の高位合成方法によって得られる図９に示す回路構成では、１つの減算器４５のみが設けられているが、３つのセレクタ４３、４４、４７を必要とする。これに対して、図１６に示す回路構成では、２つの減算器６３および６４が必要であるが、１つのセレクタ６６のみでよいために、２つセレクタの回路規模が、１つの減算器の回路規模よりも小さい場合は、本実施の形態の高位合成方法により、図１６に示す回路構成とすることによって、図９に示す回路構成よりも、全体の回路規模を小さくすることができる。
【００５６】
また、図１６に示す回路構成では、図９に示すコントローラ４２が不要となるために、これによっても、全体の回路規模を小さくすることができる。
【００５７】
＜実施の形態２＞
次に、本発明の高位合成方法の実施の形態の他の例を、図１７の動作記述に基づいて説明する。図１７に示す動作記述は、図７に示す動作記述、すなわち、条件（ｉｆ）「ｄ＞ｅ」の場合、ｘ＝ａ−ｂ、その他の条件の場合（ｅｌｓｅ）、ｘ＝ａ＊（ｂ−ｃ）という動作記述に、条件（ｉｆ）「ｆ＞ｇ」の場合、ｎ＝ｙ−ｘ、その他の条件の場合（ｅｌｓｅ）、ｎ＝ｘ＊ｙ＊ｚという動作記述が加えられている。
【００５８】
図１７に示す動作記述は、ＣＤＦＧに変換されて、図１８に示すようにスケジューリングされる。クロックステップｓｔｅｐ１およびｓｔｅｐ２には、図１７に示す動作記述において、図７に示す動作記述と同様の部分が、図８と同様にスケジューリングされており、その説明については省略する。
【００５９】
クロックステップｓｔｅｐ２には、比較を示す比較節点７１もスケジューリングされており、クロックステップｓｔｅｐ３には、ＩＦ節点７２がスケジューリングされている。比較を示す比較節点７１には、入力「ｆ」および「ｇ」からの入出力枝がそれぞれ接続されている。比較節点７１からの入出力枝は、コントロール信号ｋ２を与える制御入出力枝として、第２のＩＦ節点７２に接続されている。
【００６０】
第２のＩＦ節点７２の内部には、第１および第２の副ＣＤＦＧ７４および７５が設けられている。第１の副ＣＤＦＧ７４は、コントロール信号ｋ２が「１」（真）の場合に実行され（「ｔｒｕｅ」で表す）、第２の副ＣＤＦＧ７５は、コントロール信号ｋ２が「０」（偽）の場合に実行される（「ｆａｌｓｅ」で表す）。
【００６１】
「ｔｒｕｅ」で表された副ＣＤＦＧ７４は、入力「ｙ」および「ｚ」からのそれぞれの入出力枝が接続された減算節点７６が設けられており、「ｆａｌｓｅ」で表される副ＣＤＦＧ７５には、第１の乗算節点７７および第２の乗算節点７８がそれぞれ設けられている。第１の乗算節点７７には、入力「ｚ」および「ｘ」からのそれぞれの入出力枝が接続されており、第２の乗算節点７８には、入力「ｙ」からの入出力枝および第１の乗算節点７７からの入出力枝がそれぞれ接続されている。
【００６２】
このようなスケジューリング結果において、アロケーションされる加算器と減算器と比較器の遅延時間を、それぞれ５（ｎｓｅｃ）、乗算器の遅延時間を６０（ｎｓｅｃ）、クロック周期を１００（ｎｓｅｃ）とすると、第１のＩＦ節点３２において、条件が「ｔｒｕｅ」の場合に実行される副ＣＤＦＧ３４の遅延時間は５（ｎｓｅｃ）、条件が「ｆａｌｓｅ」の場合に実行される副ＣＤＦＧ３５の遅延時間は６５（ｎｓｅｃ）となり、条件の成立如何にかかわらず、１つのクロックステップで終了する。これに対して、第２のＩＦ節点７２は、条件が「ｔｒｕｅ」の場合に実行される副ＣＤＦＧ７４の遅延時間は５（ｎｓｅｃ）であり、１クロックステップで終了するが、条件「ｆａｌｓｅ」の場合に実行される副ＣＤＦＧ７５の遅延時間は１２０（ｎｓｅｃ）となり、クロック周期を超えるために、２つのクロックステップが必要となる。このため、回路全体としては、条件によっては３つのクロックステップ、または４つのクロックステップが必要になる。
【００６３】
図１９は、図１８の第１のＩＦ節点３２と第２のＩＦ節点７２とを、予め論理合成し、それぞれの組合せ論理回路に対応する節点を、第１のＣＩＦ節点３９と第２のＣＩＦ節点７９とによって示したものである。この場合、第１および第２のＣＩＦ節点３９および７９の遅延時間は、第１および第２のＩＦ節点３２および７２それぞれにおける副ＣＤＦＧ３４および３５と、副ＣＤＦＧ７４および７５との長い方の遅延時間となり、第１のＣＩＦ節点３９の遅延時間は、６５（ｎｓｅｃ）、第２のＣＩＦ節点７９の遅延時間は、１２０（ｎｓｅｃ）となる。このため、第２ＣＩＦ節点７９は、２つのクロックステップに跨ることになる。よって、図１９におけるスケジューリング結果では、全体として３クロックステップが必要になる。
【００６４】
しかしながら、この場合に、条件が成立するとき（「ｔｒｕｅ」）と、条件が成立しないとき（「ｆａｓｌｅ」）とにおいて、同一のクロックステップで終了するＩＦ節点のみを予め論理合成すると、図１９に示すＣＤＦＧは、第１のＩＦ節点３２のみが、ＣＩＦ節点３９に変換されて、図２０に示すＣＤＦＧとなる。図２０に示すＣＤＦＧでは、第２のＩＦ節点７２において、条件が成立する場合と条件が成立しない場合とによって、回路全体のクロック数は、それぞれ２つのクロックステップと３つのクロックステップとなる。図１９に示すＣＤＦＧの場合には、条件に関わらず、３つのクロックステップを必要とるすために、図２０に示すＣＤＦＧでは、演算処理をより高速化することができる。
【００６５】
＜実施の形態３＞
次に、本発明の高位合成方法の実施の形態のさらに他の例を、図２１の動作記述に基づいて説明する。図２１に示す動作記述において、関数「ｓｅｎｄ（ｘ）」は、変数ｘを通信路へ送信し、通信が完了するまで待機する動作を表す。すなわち、図２１の動作記述は、条件（ｉｆ）「ｄ＞ｅ」の場合、「ｘ＝ａ−ｂ」を通信路に転送し、その他の条件の場合（ｅｌｓｅ）、「ｘ＝ａ＊（ｂ−ｃ）」を通信路に転送することを表す。
【００６６】
図２１の動作記述に対するＣＤＦＧの一例を図２２に示す。クロックステップｓｔｅｐ１には、比較を示す比較節点８１がスケジューリングされており、クロックステップｓｔｅｐ２には、ＩＦ節点８２がスケジューリングされている。比較を示す比較節点８１には、入力「ｄ」および「ｅ」からの入出力枝がそれぞれ接続されている。比較節点８１からの入出力枝によって、コントロール信号ｋ１がＩＦ節点８２に与えられている。
【００６７】
ＩＦ節点８２の内部には、第１および第２の副ＣＤＦＧ８４および８５が設けられている。第１の副ＣＤＦＧ８４は、コントロール信号ｋ１が「１」（真）の場合に実行され（「ｔｒｕｅ」で表す）、第２の副ＣＤＦＧ８５は、コントロール信号ｋ１が「０」（偽）の場合に実行される（「ｆａｌｓｅ」で表す）。
【００６８】
「ｔｒｕｅ」で表された副ＣＤＦＧ８４は、入力「ａ」および「ｂ」からの入出力枝が接続される減算節点８６が設けられている。
【００６９】
「ｆａｌｓｅ」で表される副ＣＤＦＧ８５には、入力「ｂ」および「ｃ」からの入出力枝がそれぞれ接続された第２の減算節点８７と、第２の減算節点８７からの入出力枝が接続される乗算節点８８がそれぞれ設けられている。乗算節点８７には、入力「ａ」からの入出力枝も接続されている。
【００７０】
クロックステップ３以降のクロスステップには、動作記述中の「ｓｅｎｄ（ｘ）」に対応する第１および第２のｓｅｎｄ節点９１および９２がスケジューリングされている。第１のｓｅｎｄ節点９１には、減算節点８６からの入出力枝が接続されており、第２のｓｅｎｄ節点９２には、乗算節点８８からの入出力枝が接続されている。各ｓｅｎｄ節点９１および９２には、それぞれ、１つのコントロール入出力枝が接続されている。
【００７１】
このように、通信を行うために、コントローラの制御が必要な第１および第２のｓｅｎｄ節点９１および９２を、ＩＦ節点８２の外部に取り出すことにより、ＩＦ節点８２を、組合せ論理回路で実現することができる。従って、前記実施の形態１および２で説明したように、ＩＦ節点８２を、予め論理合成しておくことができる。
【００７２】
ｓｅｎｄ節点には、通常、１つのデータ入出力枝と、１つのコントロール入出力枝がそれぞれ接続されている。データ入出力枝には、通信路に転送するデータが入力される。コントロール入出力枝からは、データ転送が終了したことを示すコントロール信号が出力される。このために、図２１に示される動作記述は、図２３に示すようにスケジューリングされて、第１および第２のｓｅｎｄ節点９１および９２は、ＩＦ節点８２内における第１および第２の副ＣＤＦＧ８４および８５にそれぞれ配置される。各ｓｅｎｄ節点９１および９２は、データ転送が終了するまで待機状態になるために、クロックステップｓｔｅｐ３以降の複数のクロックステップにわたってデータの転送を実行する。
【００７３】
このように、各ｓｅｎｄ節点９１および９２の動作が、コントローラによるコントロール信号によって制御されるために、ｓｅｎｄ節点９１および９２を含むＣＤＦＧ８２は、コントローラとの間にてコントロール信号を送受する必要があり、組合せ論理回路のみでは構成することができず、ｓｅｎｄ節点９１および９２を有するＩＦ節点８２を、予め論理合成することはできない。
【００７４】
しかしながら、図２２に示すように、各ｓｅｎｄ節点９１および９２をＩＦ節点８２の外部に取り出すことにより、ＩＦ節点８２を、組合せ論理回路で実現することができ、ＩＦ節点８２を、予め論理合成しておくことが可能になる。
【００７５】
なお、このように、各ｓｅｎｄ節点９１および９２をＩＦ節点８２の外部に取り出す場合には、図２４に示すように、ＩＦ節点８２の外部に取り出された各ｓｅｎｄ節点９１および９２が同一機能であれば、１つのｓｅｎｄ節点９３のみを設けるようにしてもよい。
【００７６】
図２５は、図２４に示すＩＦ節点８２を、図１３に示すように論理合成して組合せ回路とし、図１５と同様に、対応するＣＩＦ節点９４に入れ換えた場合のスケジューリング結果である。図２５に示すスケジューリング結果では、図２３に示すスケジューリング結果よりも、クロックステップ数が１つ少なくなり、処理速度をより高速化することができる。
【００７７】
なお、組合せ論理回路で表すことができない節点が、ＩＦ節点における副ＣＤＦＧの最上位にある場合には、その節点を、ＩＦ節点の上側に取り出すようにしてもよい。
【００７８】
＜実施の形態４＞
本発明の高位合成方法の実施の形態のさらに他の例を、図２６の動作記述に基づいて説明する。図２６に示す動作記述では、条件（ｉｆ）「ｄ＞ｅ」の場合は、ｘ＝（ａ＋ｂ−ｃ）＊ｃ＋ａであり、その他の条件の場合（ｅｌｓｅ）は、ｘ＝（ｂ＋ｃ）＊ｃ＋（ｂ＋ｃ）＋ａである。
【００７９】
この動作記述をＣＤＦＧ変換してスケジューリングした一例を図２７に示す。図２７に示すように、クロックステップｓｔｅｐ１には、比較を示す比較節点１０１がスケジューリングされており、クロックステップｓｔｅｐ２には、ＩＦ節点１０２がスケジューリングされている。比較節点１０１には、入力「ｄ」および「ｅ」からの入出力枝が接続されるとともに、コントロール信号ｋを与えるコントロール入出力枝１７３が接続されている。
【００８０】
また、クロックステップｓｔｅｐ２にスケジューリングされたＩＦ節点１０２は、内部に第１および第２の副ＣＤＦＧ１０４および１０５が設けられている。第１の副ＣＤＦＧ１０４は、ＩＦ節点を含むことができる。第１の副ＣＤＦＧ１０４は、コントロール信号ｋが「１」（真）の場合に実行され（「ｔｒｕｅ」で表す）、第２の副ＣＤＦＧ１０５は、コントロール信号ｋが「０」（偽）の場合に実行される（「ｆａｌｓｅ」で表す）。
【００８１】
「ｔｒｕｅ」で表された副ＣＤＦＧ１０４には、入力「ａ」および「ｂ」からの入出力枝が接続された第１の加算節点１０６が設けられており、第１の加算節点１０６の入出力枝は、第１の減算節点１０７に接続されている。第１の減算節点１０７には、入力「ｃ」からの入出力枝が接続されている。第１の減算節点１０７の入出力枝は、第１の乗算節点１０８に接続されており、第１の乗算節点１０８に、入力「ｃ」からの入出力枝が接続されている。第１の乗算節点１０８の入出力枝は、第２の加算節点１０９に接続されており、第２の加算節点１０９に、入力「ａ」からの入出力枝が接続されている。そして、第２の加算節点１０９からの入出力枝がＩＦ節点１０２の入出力枝に接続されている。
【００８２】
「ｆａｌｓｅ」で表される副ＣＤＦＧ１０５には、第３の加算節点１１１が設けられており、第３の加算節点１１１には、入力「ｂ」および「ｃ」からの入出力枝が接続されている。第３の加算節点１１１からの入出力枝は、第２の乗算節点１１２および第２の減算節点１１３に接続されている。第２の乗算節点１１２には、入力「ｃ」からの入出力枝が接続されており、第２の乗算節点１１２からの入出力枝は、第２の減算節点１１３に接続されている。第２の減算節点１１３からの入出力枝は、第４の加算節点１１４に接続されている。そして、第４の加算節点１１４からの入出力枝がＩＦ節点１０２の入出力枝に接続されている。
【００８３】
図２７に示すＣＤＦＧも、実施の形態１および２と同様に、条件が成立する場合（「ｔｒｕｅ」）と、条件が成立しない場合（「ｆａｓｌｅ」）とにおいて、同一のクロックステップにおいて終了するＩＦ節点のみを予め論理合成することにより、図２８に示す回路とされる。この回路は、比較節点１０１に対して比較器１２１が割り当てられており、また、ＩＦ節点１０２組合せ回路に対して、ＣＩＦ節点１２０が割り当てられている。
【００８４】
しかしながら、図２７に示す回路構成では、ＩＦ節点の条件が成立した場合に実行される副ＣＤＦＧ１０４と、条件が成立しなかった場合に実行される副ＣＤＦＧ１０５の両方に、乗算節点１０８および１１２を含む場合には、図２８に示すように論理合成すると、２つの乗算器１２２および１２３を含む組合せ論理回路が生成される。通常、乗算器は、加算器および減算器に比べて面積が大きいため、生成される回路全体の面積が増加することになる。
【００８５】
このような回路規模の増大を防止するためには、次の方法が実施される。この方法では、ＩＦ節点を、指定された節点の上側および下側において分割し、指定された節点をＩＦ節点の外部に配置するようになっている。これにより、ＩＦ節点を予め論理合成した場合に、回路全体の面積が増加することが防止される。また、コントローラによる制御が必要なために組合せ論理回路を構成できない演算の節点を指定してＩＦ節点の外部に配置することにより、コントローラによる制御が必要な節点を含むＩＦ節点についても、予め論理合成して組合せ論理回路にすることができる。
【００８６】
この方法を、図２９に示すフローチャートに基づいて説明する。まず、通常の方法によって、動作記述をＣＤＦＧに変換し（図２９のステップＳ２１参照、以下同様）、変換されたＣＤＦＧに含まれる節点を、特定された節点の上側と下側において、それぞれグループに分割する（ステップＳ２２）。
【００８７】
節点をグループ化する方法について、図３０に示すＣＤＦＧに基づいて説明する。図３０に示すＣＤＦＧは、２つの入力枝が接続された第１の加算節点１３１からの出力枝が、第１の減算節点１３２に接続されている。第１の減算節点１３２には、さらに、１つの入力枝が接続されており、出力枝が乗算節点１３３に接続されている。乗算節点１３３からの２つの出力枝が、それぞれ、第２の加算節点１３５および第３の加算節点１３６に接続されている。第１の加算節点１３１からの他の出力枝は、第２の減算節点１３４に接続されており、第２の減算節点１３４からの出力枝が第２の加算節点１３５に接続されている。
【００８８】
このようなＣＤＦＧにおいて、回路面積が大きい乗算節点１３３を、ＩＦ節点の外部に出すことによって、回路規模が増大することを防止できる。この場合、まず、図３０に示すように、ＣＤＦＧに含まれる節点をグループ化する。節点をグループ化する際には、ＩＦ節点の外部に出す乗算節点１３３を指定して、その上側および下側において、各節点をグループ化する。乗算節点１３３の上側のグループＡは、それぞれの出力が乗算節点１３３に直接的または間接的に入力される節点の集合であり、第１加算節点１３１および第１減算節点１３２が含まれている。第１加算節点１３１のように、その出力が、第１減算節点１３２を経て、乗算節点１３３の入力になるものも含む。
【００８９】
乗算節点１３３よりも下側のグループＣに含まれる節点は、乗算節点１３３の出力を入力とする節点の集合であり、第３加算節点１３５および第４加算節点１３６が含まれる。この場合も、乗算節点１３３の出力が他の節点を経て入力される節点があれば、その節点も含まれる。グループＢは、グループＡにもグループＣにも含まれない節点の集合であり、乗算節点１３３の演算と無関係な節点である。グループＢには、第２減算節点１３４が含まれる。このようにして、ＩＦ節点における節点がグループ化される。
【００９０】
このようにして、節点がグループ化されると、各グループに基づいて、ＩＦ節点を分割し、指定された節点をＩＦ節点の外部に配置する（図２９のステップＳ２３）。その後、外部に配置された節点の共通化と、不要な入出力枝を削除することにより、ＣＤＦＧを簡単化する（ステップＳ２４）。その後は、前述した高位合成方法と同様に、変更されたＣＤＦＧをスケジューリングして、アロケーションすることにより、回路を生成する。
【００９１】
このような高位合成方法を、図２７のＣＤＦＧに基づいて説明する。図２７に示すＣＤＦＧにおいても、前述したように、まず、ＩＦ節点１０２に含まれる節点をグループ化する。この場合、ＩＦ節点１０２における「ｔｒｕｅ」で表される副ＣＤＦＧ１０４、および、「ｆａｌｓｅ」で表される副ＣＤＦＧ１０５のそれぞれに関して、回路規模の大きな第１の乗算節点１０８および第２の乗算節点１１２を中心として、それぞれ、節点のグループ化が実施される。
【００９２】
従って、第１の乗算節点１０８に関して、それよりも上側のグループＡには、第１乗算節点１０８にそれぞれの出力が入力される第１加算節点１０６および第１減算節点１０７が含まれ、第１乗算節点１０８よりも下側のグループＣには、第１乗算節点１０８からの出力が入力される第２加算節点１０９が含まれる。
【００９３】
同様に、第２の乗算節点１１２に関して、それよりも上側のグループＡには、第２乗算節点１１２に出力が入力される第３加算節点１１１が含まれ、第２乗算節点１１２よりも下側のグループＣには、第２乗算節点１１２からの出力がそれぞれ入力される第２減算節点１１３および第４減算節点１１４が含まれる。
【００９４】
このように、ＩＦ節点１０２内に含まれる節点がグループ化されると、図３１に示すように、ＩＦ節点１０２を、グループＡに含まれる各節点にて構成される第１のＩＦ節点（図に「ＩＦ１」にて示す）１４１と、グループＣに含まれる各節点にて構成される第２のＩＦ節点（図に「ＩＦ２」にて示す）１４２の２つに分割する。
【００９５】
この場合、第１および第２の乗算節点１０８および１１２とは無関係の節点のグループＢがあれば、グループＡに含まれる節点数がグループＣに含まれる節点数よりも少ない場合は、グループＢに含まれる節点が、グループＡにて構成される第１のＩＦ節点１４１に含められ、そうでない場合は、第２のＩＦ節点１４２に含められる。第１および第２の乗算節点１０８および１１２は、グループＡ，Ｂ，Ｃのいずれにも含まれないため、第１のＩＦ節点１４１と第２のＩＦ節点１４２の間に配置されることになり、図３１に示すように、第１ＩＦ節点１４１および第２ＩＦ節点１４２の外部に配置される。
【００９６】
このようなＣＤＦＧが得られると、得られたＣＤＦＧが簡単化される。ＣＤＦＧの簡単化は、前述したように、ＩＦ節点の外部に配置された複数の節点の演算が同一な場合に、それらの節点を１つの節点にて共通化すること、および、不要な入出力枝の削除で実施される。
【００９７】
図３１に示すＣＤＦＧが得られると、第１および第２のＩＦ節点１４１および１４２の外部に配置された第１および第２の乗算節点１０８および１１２は、図３２に示すように、１つの乗算節点１４３によって共通化する。これにより、２つの乗算節点１０８および１１２に対して、１つの乗算器が割り当てられることになる。この時、当然に、共通化される２つの節点は同一の演算器で行うことができる必要がある。２つの演算が異なる種類の場合には、節点同士の共通化は行われない。
【００９８】
次に、不要な入出力枝を削除する。不要な入出力枝は、各ＩＦ節点１４１および１４２内を、いずれの節点にも接続されることなく、すなわち演算に関係することなく通過する入出力枝であり、図３２においては、第１ＩＦ回路１４１内の入出力枝１４４〜１４７である。これらの入出力枝１４４〜１４７が削除されることにより、図３３に示すように、簡単化されたＣＤＦＧが得られる。
【００９９】
このようにして、分割された第１のＩＦ節点１４１および第２のＩＦ節点１４２が得られると、第１のＩＦ節点１４１および第２のＩＦ節点１４２を、それぞれ、前述したようにして論理合成して、図３４（ａ）に示すように、第２ＩＦ節点１４１に対応する第１のＣＩＦ節点１５１と、図３４（ｂ）に示すように、第２のＩＦ節点１４２に対応する第２のＣＩＦ節点１５２とを、それぞれ生成する。
【０１００】
この場合、第１のＣＩＦ節点１５１には、第１および第２の加算器１５３および１５４と、第１の減算器１５５と、第１のセレクタ１５６とが設けられている。第１の加算器１５３には、入力「ａ」および「ｂ」が入力されており、第２の加算器１５４には、入力「ｂ」および「ｃ」が入力されている。第１の減算器１５５には、第１の加算器１５３の出力と入力「ｃ」とが入力されている。そして、セレクタ１５６には、第１の減算器１５５の出力と第２の加算器１５４の出力が入力されており、コントロール信号ｋによって、第１の減算器１５５の出力、第２の加算器１５４の出力のいずれかが出力される。従って、セレクタ１５３からは、演算「ａ＋ｂ−ｃ」または「ｂ＋ｃ」のいずれかの結果が出力される。
【０１０１】
第２のＣＩＦ１５２には、第３および第４の加算器１５７および１５８と、第２の減算器１５９と、第２のセレクタ１６０とが設けられている。第３の加算器１５３には、入力「ａ」と、セレクタ１５３からの出力である「（ａ＋ｂ−ｃ）＊ｃ」または「（ｂ＋ｃ）＊ｃ」のいずれかとが入力されており、第２の減算器１５９には、乗算器１４３からの出力である「（ａ＋ｂ−ｃ）＊ｃ」または「（ｂ＋ｃ）＊ｃ」のいずれかと、第１ＣＩＦ節点１５１の出力「ｂ＋ｃ」とが入力されている。第２の加算器１５８には、入力「ａ」と、第２減算器の出力とが入力されている。第２のセレクタ１６０には、第３の加算器１５７の出力と第４の加算器１５４の出力が入力されており、コントロール信号ｋによって、第３の加算器１５７の出力、第４の加算器１５８の出力のいずれかが「ｘ」として出力される。
【０１０２】
各ＣＩＦ１５１および１５２において、それぞれの加算器と減算器の遅延時間をそれぞれ５（ｎｓｅｃ）、乗算器の遅延時間を６０（ｎｓｅｃ）とすると、第１ＣＩＦ節点１２１の遅延時間は１０（ｎｓｅｃ）、第２ＣＩＦ節点１５２の遅延時間も１０（ｎｓｅｃ）となる。
【０１０３】
第１のＣＩＦ節点１５１および第２のＣＩＦ節点１５２を用いたＣＤＦＧを、図３５に示す。このＣＤＦＧの最大遅延パスは、比較節点１０１、第１のＣＩＦ節点１５１、乗算節点１４３、第２のＣＩＦ節点１５２を通るパスであり、クロック周期が１００（ｎｓｅｃ）、比較器の遅延時間が５（ｎｓｅｃ）であるとすると、最大遅延時間は８５（ｎｓｅｃ）となり、クロック周期を超えることがなく、１クロックにおいて実行することが可能である。
【０１０４】
図２７に示すＣＤＦＧは、ＩＦ節点も含めると１０個の節点より構成されているのに対して、図３５に示すＣＤＦＧは４つの節点しか含まれず、高位合成を高速で行うことが可能である。
【０１０５】
また、図２７に示すＣＤＦＧの実行には、２クロック周期が必要であるのに対して、図３５に示すＣＤＦＧは、１クロック周期で実行することができ、高速処理が可能になる。最終的には、図３５に示すＣＤＦＧから、図３６に示す回路を得ることができる。図２７に示すＣＤＦＧから生成された図２８に示す回路では、２つの乗算器１２２を含むのに対して、図２７に示すＣＤＦＧから生成された図３６に示す回路では、１つ乗算器１６１しか含まず、回路の面積が小さくなっている。
【０１０６】
＜実施の形態５＞
次に、本発明の高位合成方法の実施形態の他の例について説明する。まず、図３７に示す動作記述を前述した実施の形態１および２と同様にして高位合成した場合について説明する。図３７に示す動作記述では、条件（ｉｆ）「ｄ＞ｅ」の場合は、ｘ＝（ａ＋ｂ）＊ｂ＋ａであり、その他の条件の場合（ｅｌｓｅ）は、ｘ＝（ｂ＋ｃ）＊ａ−（ａ＋ｃ）である。
【０１０７】
この動作記述をＣＤＦＧ変換してスケジューリングした一例を図３８に示す。図３８に示すように、クロックステップｓｔｅｐ１には、比較を示す比較節点１７１がスケジューリングされており、クロックステップｓｔｅｐ２には、ＩＦ節点１７２がスケジューリングされている。比較節点１７１には、入力「ｄ」および「ｅ」からの出力枝が接続されるとともに、コントロール信号ｋを与えるコントロール出力枝１７３が接続されている。
【０１０８】
また、クロックステップｓｔｅｐ２にスケジューリングされたＩＦ節点１７２は、内部に第１および第２の副ＣＤＦＧ１７４および１７５が設けられている。第１の副ＣＤＦＧ１７４は、コントロール信号ｋが「１」（真）の場合に実行され（「ｔｒｕｅ」で表す）、第２の副ＣＤＦＧ１７５は、コントロール信号ｋが「０」（偽）の場合に実行される（「ｆａｌｓｅ」で表す）。
【０１０９】
「ｔｒｕｅ」で表された副ＣＤＦＧ１７４には、入力「ａ」および「ｂ」からの入出力枝が接続された第１の減算節点１７６が設けられており、第１の加算節点１７６からの出力枝は、第１の乗算節点１７７に接続されている。第１の乗算節点１７７には、入力「ｂ」からの出力枝が接続されている。第１の乗算節点１７７の入出力枝は、第１の加算節点１７８に接続されており、第１の加算節点１７８に、入力「ａ」からの出力枝が接続されている。第１の加算節点１７８からの出力枝がＩＦ節点１７２の出力枝に接続されている。
【０１１０】
「ｆａｌｓｅ」で表される副ＣＤＦＧ１７５には、第２の加算節点１８１が設けられており、第２の加算節点１８１には、入力「ｂ」および「ｃ」からの出力枝が接続されている。第２の加算節点１８１からの出力枝は、第２の乗算節点１８２および第２の減算節点１８３に接続されている。第２の乗算節点１８２には、入力「ａ」からの出力枝が接続されており、第２の乗算節点１８２からの出力枝は、第２の減算節点１８３に接続されている。第２の減算節点１８３からの出力枝がＩＦ節点１７２の出力枝に接続されている。
【０１１１】
このようなＣＤＦＧのＩＦ節点１７２は、前述したようにして論理合成することにより、図３９に示すように、ＣＩＦ節点１８４とされる。このようなＣＤＦＧによって、図４０に示す回路が得られる。この回路は、入力「ａ」および「ｂ」が入力される第１減算器１９１を有しており、第１減算器１９１の出力が第１乗算器１９２に入力されている。第１乗算器１９２には、入力「ｂ」も入力されており、第１乗算器１９２の出力が第１加算器１９３に入力されている。第１加算器１９３には、入力「ａ」も入力されている。第１加算器１９３の出力は、セレクタ１９７に与えられている。
【０１１２】
また、この回路には、第２加算器１９４入力「ａ」および「ｂ」が入力される第２加算着１９４が設けられており、第２加算器１９４の出力が第２乗算器１９５に入力されている。第１乗算器１９５の出力は、第２減算器１９６に入力されている。第２減算器１９６には、第２加算器１９４の出力が入力されており、第２減算器１９６の出力がセレクタ１９７に与えられている。セレクタ１９７は、比較器１９８からのコントロール信号ｋに基づいて、第１加算器１９３の出力、第２減算器１９６の出力のいずれかを出力する。
【０１１３】
また、このような回路においては、次の（２）式を満足する演算器があれば、その演算器に関する節点をＩＦ節点の外部に配置することによって、回路面積をさらに低減することができる。。
【０１１４】
（演算器の入力数）×（セレクタの面積）≦（演算器の面積）・・・（２）
すなわち、ＩＦ節点に含まれる副ＣＤＦＧを構成する節点に対応する演算器において、同一の演算器が複数存在する場合には、その演算器の１つの面積が、セレクタの面積に対して、演算器の入力数倍以上であれば、その演算器に対応する節点をＩＦ節点の外部に配置する。
【０１１５】
例えば、図４０に示す回路において、乗算器１９２および１９５に対して、「ｔｒｕｅ」と「ｆａｌｓｅ」の２通りの入力を与えるために、各乗算器１９２および１９５の入力の個数分（２個分）のセレクタが必要になるが、このような個数のセレクタを増加することによって、一方の乗算器を削除することができるために、必要とされるセレクタの全面積に対して、削除される乗算器の面積が大きければ、乗算器を削除することによって、セレクタが増加するにもかかわらず、全体の回路面積を低減させることができる。
【０１１６】
図４０に示す回路において、乗算器の面積が１０、加算器および減算器の面積が２、セレクタの面積が２の割合にそれぞれなっているものとすると、図３８に示すＩＦ節点１７２の副ＣＤＦＧ１７４および１７５に含まれる各節点に対応するそれぞれの演算器において、前記（２）式を満たすものは、図４０に示す乗算器１９２および１９５である。
【０１１７】
このために、各乗算器１９２および１９５に対応する乗算節点１７７および１８２を、実施の形態３で説明したようにして、ＩＦ節点１７２の外部に配置する。
【０１１８】
図４１は、図３８に示すＩＦ節点１７２を分割したＣＤＦＧである。このＣＤＦＧは、第１および第２の乗算節点１７７および１８２を指定して、各乗算節点１７７および１８２の上側の節点のグループと、下側の節点のグループとに分割することによってＩＦ節点１７２を分割して、第１ＩＦ節点２０１および第２ＩＦ節点２０２とする。これにより、各乗算節点１７７および１８２が、第１ＩＦ節点２０１および第２ＩＦ節点２０２の外部に配置される。そして、外部に配置された各乗算節点１７７および１８２を１つの乗算節点２０３によって共通化し、不要な入出力枝を削除することにより、図４１に示すＣＤＦＧが得られる。
【０１１９】
このように、必要とされるセレクタの面積に対して、削除された乗算器の面積が大きいことにより、回路面積を低減させることができる。
【０１２０】
図４２は、図４１に示すＣＤＦＧにおける第１のＩＦ節点２０１と第２のＩＦ節点２０２とを、前述したように、組合せ論理回路である第１ＣＩＦ２０３と、第２ＣＩＦとに置き換えたＣＤＦＧのスケジューリング結果を示す。また、図４３は、図４２に示すスケジューリング結果を回路化したものである。
【０１２１】
図４３に示す回路では、第１のＣＩＦ２０４に対応する第１の組合せ論理回路２２１および第２のＣＩＦに対応する第２の組合せ論理回路２２２と、両組合せ論理回路２２１および２２２の間に配置された乗算器２１２とが設けられている。第１の組合せ論理回路２２１には、入力「ａ」および「ｂ」がそれぞれ入力される第１の減算器２１１および第１の加算器２１４が設けられており、第１減算器２１１および第１の加算器２１４の出力が、それぞれ、第１のセレクタ２１７に入力されるとともに、第２のセレクタ２１８に入力されている。
【０１２２】
第１および第２のセレクタ２１７および２１８は、比較器２２３からのコントロール信号ｋによって、それぞれ、第１減算器２１１および第１の加算器２１４の出力のいずれかを選択して出力する。第１のセレクタ２１７および第２のセレクタ２１８の出力は、それぞれ乗算器２１２に与えられている。
【０１２３】
乗算器２１２の出力は、第２の組合せ論理回路２２２に設けられた第２の加算器２１３および第２の減算器２１６にそれぞれ与えられており、第２の加算器２１３および第２の減算器２１６の出力が第３のセレクタ２１９に与えられている。第３のセレクタ２１９は、比較器２２３からのコントロール信号ｋによって、それぞれ、第２の加算器２１３および第２の減算器２１６の出力のいずれかを選択して出力する。そして、第３セレクタ２１９の出力が、演算結果の出力「ｘ」になる。
【０１２４】
図４３に示す回路を、図４０に示す回路と比較すると、図４０に示す回路は、２つの乗算器１９２および１９５が設けられているが、１つのセレクタ１９７しか設けられていない。これに対して、図４３に示す回路では、１つの乗算器２１２しか設けられていないが３つのセレクタ２１７〜２１９が設けられている。この場合、１つの乗算器の面積は、増加するセレクタの面積よりも大きく、前記（２）式を満たしているため、回路全体では、図４３に示す回路の面積が、図４０に示す回路の面積よりも小さくなる。
【０１２５】
（２）式を満たす節点が「ｔｒｕｅ」または「ｆａｌｓｅ」の副ＣＤＦＧに複数ある場合は、その節点の演算を実行する演算器の面積が最も大きい演算をＩＦ節点が外部に配置されるように、上記方法を適用する。そして、分割して得られる２つのＩＦ節点について、再度上記方法を適用する。
【０１２６】
ＩＦ節点の外部に配置された節点（図４２の場合は乗算節点２０３）と別の節点が、同一の演算器を共通化するような場合には、図４０に示す回路の面積がさらに小さくなる。この場合、演算器の面積が（２）式を満たす程度に大きくなっていなくても、面積削減の効果が現れる。このような可能性を考慮して、条件を、次の（３）式のようにしてもよい。ここで、定数は１より小さい数値で、回路によって実験的に求められる値である。
【０１２７】
（演算器の入力数）×（セレクタの面積）×（定数）≦（演算器の面積）・・・（３）
【０１２８】
【発明の効果】
本発明の高位合成方法では、ＣＤＦＧの一部である複数の節点が、１つの節点として扱われるため、ＣＤＦＧが含む節点が少なくなり、高位合成に必要な処理時間が短くなる。また、節点のＣＤＦＧの一部を予め論理合成して最適化しているため、置き換えられた１つの節点の遅延時間には、最終的な回路における遅延時間を用いることができ、遅延時間の見積り精度が良くなる。
【０１２９】
また、本発明の高位合成方法では、条件分岐に対応するＣＤＦＧの部分は、条件分岐のコントロール信号も含めて予め論理合成されるため、高位合成に必要な処理時間が短くなり、遅延の見積り精度が向上する。また、合成した回路が含むセレクタが減少することによって、回路規模を小さくすることができる。さらに、コントローラによって条件分岐の制御を行う信号を生成する必要がなくなるために、回路規模を小さくすることができる。また、条件分岐の条件判定と、条件分岐自体の動作を同一クロックステップで実行できるために、高位合成によって得られる回路の動作を高速化することもできる。
【０１３０】
また、本発明の高位合成方法では、分岐条件が真でも偽でも無駄なクロックステップが発生するおそれがなく、高位合成によって得られる回路の動作を高速化することができる。
【０１３１】
また、本発明の高位合成方法では、ＣＤＦＧがコントローラとの信号の送受に関する演算を含むため、予め論理合成して組合せ論理回路にできない場合、あるいは、ＣＤＦＧが大規模な演算器を含むために、予め論理合成して組合せ論理回路とすると回路規模が不必要に大きくなるような場合においても、回路規模の縮小および生成される回路動作の高速化が可能になる。
【０１３２】
また、本発明の高位合成方法では、ＣＤＦＧがコントローラとの信号の送受に関する演算を含むため、予め論理合成して組合せ論理回路にできない場合、あるいは、ＣＤＦＧが大規模な演算器を含むために、予め論理合成して組合せ論理回路とすると回路規模が不必要に大きくなるような場合においても、回路規模の縮小および生成される回路動作の高速化が可能になる。
【０１３３】
また、本発明の高位合成方法では、面積が大きい演算器を含む動作記述についても、回路規模の縮小および生成される回路動作の高速化が可能になる。
【０１３４】
本発明の請求項７記載の記録媒体では、このような高位合成方法を容易に実行することができる。
【図面の簡単な説明】
【図１】高位合成の手順を示すフローチャートである。
【図２】（１）式の動作記述のＣＤＦＧの一例を示す模式図である。
【図３】図２のＣＤＦＧのスケジューリング結果の一例を示す模式図である。
【図４】図３に示すスケジューリング結果に対応した回路の構成を示す模式図である。
【図５】（１）式の動作記述のＣＤＦＧをスケジューリングした結果の他の例を示す模式図である。
【図６】図５に示すスケジューリング結果に対応した回路の構成を示す模式図である。
【図７】動作記述の他の例である。
【図８】図７の動作記述のＣＤＦＧをスケジューリングした結果を示す模式図である。
【図９】図８に示すスケジューリング結果に対応した回路の構成を示す模式図である。
【図１０】高位合成における遅延時間の説明図である。
【図１１】（ａ）および（ｂ）は、それぞれ、論理合成において最適化した回路を示す模式図である。
【図１２】本発明の高位合成方法の実施の形態の一例を示すフローチャートである。
【図１３】その高位合成方法において、ＣＤＦＧに含まれるＩＦ節点を、論理合成して生成された組合せ論理回路を示す模式図である。
【図１４】図１３の組合せ論理回路を示す節点である。
【図１５】図１４に示す節点を用いたＣＤＦＧである。
【図１６】図１５に示すＣＤＦＧに対応した回路を示す模式図である。
【図１７】動作記述の一例を示す式である。
【図１８】図１７に示す動作記述のＣＤＦＧの一例を示す模式図である。
【図１９】そのＣＤＦＧをＣＩＦ節点に置き換えたＣＤＦＧの一例を示す模式図である。
【図２０】そのＣＤＦＧのＩＦ節点をＣＩＦ節点に置き換えたＣＤＦＧの他の例を示す模式図である。
【図２１】動作記述の他の例を示す式である。
【図２２】図２１に示す動作記述のＣＤＦＧの一例を示す模式図である。
【図２３】そのＣＤＦＧにおける節点をＩＦ節点の外部に配置したＣＤＦＧの一例を示す模式図である。
【図２４】図２３のＣＤＦＧを最適化したＣＤＦＧを示す模式図である。
【図２５】そのＣＤＦＧのＩＦ節点をＣＩＦ節点に置き換えたＣＤＦＧの一例を示す模式図である。
【図２６】動作記述の他の例を示す式である。
【図２７】図２６に示す動作記述のＣＤＦＧの一例を示す模式図である。
【図２８】図２７に示すＣＤＦＧに対応した回路を示す模式図である。
【図２９】本発明の高位合成方法の実施の形態の他の例を示すフローチャートである。
【図３０】節点をグループ分けする場合を説明するための模式図である。
【図３１】図２６に示すＣＤＦＧを分割したＣＤＦＧを示す模式図である。
【図３２】図３１に示すＣＤＦＧを最適化したＣＤＦＧを示す模式図である。
【図３３】図３２に示すＣＤＦＨを簡単化したＣＤＦＧを示す模式図である。
【図３４】（ａ）および（ｂ）は、それぞれ、図３３に示すＣＩＦ節点に対応した回路を示す模式図である。
【図３５】そのＣＤＦＧをＣＩＦ節点に置き換えたＣＤＦＧの一例を示す模式図である。
【図３６】図２７に示すＣＤＦＧに対応した回路を示す模式図である。
【図３７】動作記述の他の例を示す式である。
【図３８】図３７に示す動作記述のＣＤＦＧの一例を示す模式図である。
【図３９】そのＣＤＦＧをＣＩＦ節点に置き換えたＣＤＦＧの一例を示す模式図である。
【図４０】図３９に示すＣＤＦＧに対応した回路を示す模式図である。
【図４１】図３８に示すＣＤＦＧを分割したＣＤＦＧの一例を示す模式図である。
【図４２】そのＣＤＦＧをＣＩＦ節点に置き換えたＣＤＦＧの一例を示す模式図である。
【図４３】図３９に示すＣＤＦＧに対応した回路を示す模式図である。
【符号の説明】
６１、６２ 部分回路
６３、６４、１５９ 減算器
６５、１６１ 乗算器
６６、１５６ セレクタ
６７、７９、９４、１５１、１５２、１８４ ＣＩＦ節点
７１、８１、１７１、１９８ 比較節点
７２、８２、１０２、１４１、１４２、２０１、２０２ ＩＦ節点
７４、７５、８４、８５、１０４、１０５、１７４、１７５ 副ＣＤＦＧ
７６、８６、８７、１０７、１１３、１３４、１７６、１８３、１９１、１９６ 減算節点
７７、７８、８８、１０８、１１２、１３２、１３３、１７７、１８２、１９２、１９５ 乗算節点
９１、９２、９３ ｓｅｎｄ節点
１０６、１０９、１１１、１１４、１３１、１３５、１３６、１５３、１５４、１５７、１５８、１７８、１８１、１９３、１９４ 加算器

Claims (7)

1. 処理の動作のみを記述した動作記述を、演算を示す節点とデータの流れを示す入出力枝とによって構成されるコントロールデータフローグラフ（ＣＤＦＧ）を作成するＣＤＦＧ作成部と、
   該ＣＤＦＧ作成部にて生成されたＣＤＦＧの一部を論理合成する論理合成部と、
   該論理合成部の論理合成に基づいて前記ＣＤＦＧ部にて作成されたＣＤＦＧを変更するＣＤＦＧ変更部と、
   該ＣＤＦＧ変更部にて変更されたＣＤＦＧの前記節点に対応する前記演算をスケジューリングするスケジューリング部と、
   該スケジューリング部にてスケジューリングされたＣＤＦＧの前記節点に対応する前記演算の実行に必要な演算器、セレクタ等の素子をそれぞれ割り当てるアロケーション部とを有する高位合成装置によって回路を自動合成する高位合成方法であって、
   前記ＣＤＦＧ作成部によって、前記動作記述に条件分岐が含まれる場合に、該条件分岐において条件が成立する場合の真の処理と該条件が成立しない場合の偽の処理とを有する部分ＣＤＦＧを生成するＣＤＦＧ生成工程と、
   前記論理合成部によって、前記ＣＤＦＧ生成工程にて生成された部分ＣＤＦＧを論理合成する論理合成工程と、
   前記ＣＤＦＧ変換部によって、前記論理合成工程にて論理合成して得られる組合せ論理回路を１つの節点として扱って前記ＣＤＦＧ生成工程にて生成されたＣＤＦＧを変更するＣＤＦＧ変更工程と、
   前記スケジューリング部によって、前記組合せ論理回路に対応する節点を、前記条件分岐に対応した節点と同一のクロックステップにスケジューリングする工程と、
   を包含することを特徴とする高位合成方法。
2. 処理の動作のみを記述した動作記述を、演算を示す節点とデータの流れを示す入出力枝とによって構成されるコントロールデータフローグラフ（ＣＤＦＧ）を作成するＣＤＦＧ作成部と、
   該ＣＤＦＧ作成部にて生成されたＣＤＦＧの一部を論理合成する論理合成部と、
   該論理合成部の論理合成に基づいて前記ＣＤＦＧ部にて作成されたＣＤＦＧを変更するＣＤＦＧ変更部と、
   該ＣＤＦＧ変更部にて変更されたＣＤＦＧの前記節点に対応する前記演算をスケジューリングするスケジューリング部と、
   該スケジューリング部にてスケジューリングされたＣＤＦＧの前記節点に対応する前記演算の実行に必要な演算器、セレクタ等の素子をそれぞれ割り当てるアロケーション部とを有する高位合成装置によって回路を自動合成する高位合成方法であって、
   前記ＣＤＦＧ作成部によって、前記動作記述に条件分岐が含まれる場合に、該条件分岐において条件が成立する場合の真の処理と該条件が成立しない場合の偽の処理とを有する部分ＣＤＦＧを生成するＣＤＦＧ生成工程と、
   前記論理合成部によって、前記ＣＤＦＧ生成工程にて生成された部分ＣＤＦＧを予め論理合成する論理合成工程と、
   前記ＣＤＦＧ変換部によって、前記論理合成工程にて論理合成して得られる組合せ論理回路を１つの節点として扱って前記ＣＤＦＧ生成工程にて生成されたＣＤＦＧを変更するＣＤＦＧ変更工程と、
   前記スケジューリング部によって、前記組合せ論理回路における前記真の処理と前記偽の処理とが同一のクロックステップにて終了するように、該組合せ論理回路の節点をスケジューリングする工程と、
   を包含することを特徴とする高位合成方法。
3. 前記論理合成工程において、部分ＣＤＦＧを、コントローラの制御が必要な節点を除いて論理合成し、
   前記ＣＤＦＧ変換工程において、前記組合せ論理回路と、前記コントローラの制御が必要な節点とを組み合わせてＣＤＦＧを変更する、請求項２に記載の高位合成方法。
4. 処理の動作のみを記述した動作記述を、演算を示す節点とデータの流れを示す入出力枝とによって構成されるコントロールデータフローグラフ（ＣＤＦＧ）を作成するＣＤＦＧ作成部と、
   該ＣＤＦＧ作成部にて作成されたＣＤＦＧに含まれる節点を、特定された節点の前記ＣＤＦＧの上流側と下流側とにおいてそれぞれグループ化する節点グループ化部と、
   該節点グループ化部にてそれぞれグループ化された各グループをそれぞれ１つの節点として分割して、前記特定された節点と組み合わせてＣＤＦＧとする分割部と、
   該分割部にて生成されたＣＤＦＧの前記各節点に対応する前記演算をスケジューリングするスケジューリング部と、
   該スケジューリング部にてスケジューリングされたＣＤＦＧの前記各節点に対応する前記演算の実行に必要な演算器、セレクタ等の素子をそれぞれ割り当てるアロケーション部とを有する高位合成装置によって回路を自動合成する高位合成方法であって、
   前記節点グループ化部によって、前記アロケーション部において割り当てられる演算器の回路面積が、他の節点に対して割り当てられる演算器の回路面積よりも大きい節点を前記特定された節点とすることを特徴とする高位合成方法。
5. 前記回路面積の大きな演算器の節点が複数であって、それぞれの節点に対応する演算が同一の場合に、前記ＣＤＦＧ変換部によって、前記複数の節点が１つの節点に共通化する請求項４に記載の高位合成方法。
6. 前記アロケーション部において前記組合せ論理回路に同一の演算器が複数割り当てられる場合に、その１つの演算器の面積がセレクタの面積の定数倍以上の場合に、前記ＣＤＦＧ変換工程において、その演算器に対応する節点を、前記組合せ論理回路と組合せてＣＤＦＧを変更する、請求項２に記載の高位合成方法。
7. 請求項１〜６のいずれかに記載の高位合成方法の手順がプログラムされていることを特徴とするコンピュータ読み取り可能な記録媒体。

Images