(57)【要約】【課題】  高位合成以降の工程、特に、レイアウト工程において、実現性の高いＲＴＬ回路を生成する高位合成方法を提供する。【解決手段】  高位合成方法は、入力ファイルと制約ファイルとに基づいてＣＤＦＧを生成するＣＤＦＧ生成工程と、ＣＤＦＧとデジタル回路の制約条件とに基づいてＦＳＭを生成し、ＣＤＦＧの各ノードをＦＳＭの各状態に割り当ててスケジューリングするスケジューリング工程と、ＣＤＦＧの各ノードに対して、デジタル回路を構成するための資源のレイアウトを示す資源レベルレイアウト情報に基づいて資源を割り当ててアロケーション情報と資源間の接続関係を表す回路情報を生成するアロケーションおよび回路情報生成工程と、回路情報を出力する出力工程とを包含する。【選択図】  図１
2004164627.tif 000002
【特許請求の範囲】
【請求項１】
デジタル回路の機能的な動作を記述した入力ファイルに基づいてＣＤＦＧ（Ｃｏｎｔｒｏｌ  Ｄａｔａ  Ｆｌｏｗ  Ｇｒａｐｈ）を生成するＣＤＦＧ生成工程と、
前記ＣＤＦＧ生成工程によって生成された前記ＣＤＦＧと制約ファイルに記述された前記デジタル回路の制約条件とに基づいて、処理内容を表現する前記ＣＤＦＧの各ノードをステップと呼ばれるクロックに同期した時間に割り当ててスケジューリングするスケジューリング工程と、
前記スケジューリング工程によってスケジューリングされた前記ＣＤＦＧの各ノードに対して、前記デジタル回路を構成するための資源のレイアウトを示す資源レベルレイアウト情報に基づいて前記資源を割り当てたアロケーション情報と資源間の接続関係を表す回路情報を生成するアロケーションおよび回路情報生成工程と、
前記アロケーションおよび回路情報生成工程によって生成された前記回路情報を出力する出力工程とを包含することを特徴とする高位合成方法。
【請求項２】
前記アロケーションおよび回路情報生成工程は、前記スケジューリング工程によってスケジューリングされた前記ＣＤＦＧの各ノードに対して前記資源を割り当てた初期アロケーション情報と資源間の接続関係を表す初期回路情報を生成する初期アロケーションおよび初期回路情報生成工程と、
前記初期アロケーションおよび初期回路情報生成工程によって生成された前記初期回路情報に基づいて前記資源レベルレイアウト情報を生成する資源レベルレイアウト工程と、
前記初期アロケーションおよび初期回路情報生成工程によって生成された前記初期アロケーション情報、または後述すると前記資源レベルレイアウト情報とに基づいて、前記ＣＤＦＧの各ノードに対する前記資源の割り当てを変更した修正アロケーション情報と資源間の接続関係を変更した修正回路情報を生成する再アロケーションおよび回路情報生成工程と、
前記再アロケーションおよび回路情報生成工程によって生成された前記修正回路情報に基づいて前記資源レベルレイアウト情報を微修正する資源レベルレイアウト微修正工程とを含んでおり、
所定の基準を満足するまで前記再アロケーションおよび回路情報生成工程と前記資源レベルレイアウト微修正工程とを繰り返して実行し、
前記再アロケーションおよび回路情報生成工程は、前記資源レベルレイアウト情報と前回に生成した修正アロケーション情報とに基づいて、前記ＣＤＦＧの各ノードに対する前記資源の割り当てを変更した修正アロケーション情報と資源間の接続関係を変更した修正回路情報を生成する、請求項１記載の高位合成方法。
【請求項３】
前記アロケーション情報は、ハードウエア資源割り当て情報とハードウエア資源のライフタイム情報とである、請求項２記載の高位合成方法。
【請求項４】
前記資源レベルレイアウト情報は、資源間結線距離情報である、請求項１記載の高位合成方法。
【請求項５】
前記資源レベルレイアウト情報は、資源間結線のレイアウト領域内混雑度情報である、請求項１記載の高位合成方法。
【請求項６】
前記資源レベルレイアウト情報は、資源間結線距離情報と資源間結線のレイアウト領域内混雑度情報とからなる任意の関数で表現された、マクロ間結線情報である、請求項１記載の高位合成方法。
【請求項７】
前記資源レベルレイアウト情報は、レイアウト影響度を係数として含んでいる、請求項１記載の高位合成方法。
【請求項８】
前記初期アロケーション工程は、可能な限りハードウエア資源を共有化しないように、前記ＣＤＦＧの各ノードに対して前記資源を割り当て、
前記再アロケーション工程は、別々に実現されたハードウエア資源を共有化するように、前記ＣＤＦＧの各ノードに対する前記資源の割り当てを変更する、請求項２記載の高位合成方法。
【請求項９】
前記初期アロケーション工程は、可能な限りハードウエア資源を共有化するように、前記ＣＤＦＧの各ノードに対して前記資源を割り当て、
前記再アロケーション工程は、共有化されたハードウエア資源を別々にアロケーションする、請求項２記載の高位合成方法。
【請求項１０】
前記再アロケーション工程は、記憶資源のレイアウト領域内配置分布ばらつきを計算し、前記レイアウト領域内配置分布ばらつきに基づいて、同期クロック回路の合成容易性を推定し、記憶資源共有化時には、合成容易性が高い共有化を選択する、請求項２記載の高位合成方法。
【請求項１１】
前記記憶資源のレイアウト領域内配置分布ばらつきは、レイアウト領域を複数の領域に分割した各領域内に属する記憶資源の数のばらつきである、請求項１０記載の高位合成方法。
【請求項１２】
前記記憶資源のレイアウト領域内配置分布ばらつきは、レイアウト領域内を階層的に分割した各階層ごとに計算したばらつきの合計である、請求項１０記載の高位合成方法。
【請求項１３】
前記初期アロケーション工程は、可能な限りハードウエア資源を共有化するように、前記ＣＤＦＧの各ノードに対して前記資源を割り当て、
前記再アロケーション工程は、共有化されたハードウエア資源を別々にアロケーションし、
前記アロケーション工程は、前記再アロケーション工程において分割されたハードウェア資源を、前記初期アロケーション工程において共有されなかったハードウェア資源と共有するアロケーション変更工程をさらに含んでいる、請求項２記載の高位合成方法。
【請求項１４】
前記資源レベルレイアウト情報は、レイアウト影響度をレイアウト影響係数として含んでおり、
前記レイアウト影響係数を段階的に修正しながら前記再アロケーション工程と前記アロケーション変更工程とを繰り返して実行する、請求項１３記載の高位合成方法。
【請求項１５】
前記出力工程は、前記資源レベルレイアウト微修正工程によって微修正された前記資源レベルレイアウト情報をさらに出力する、請求項２記載の高位合成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル回路の機能的な動作記述に基づいて、ディジタル回路の回路記述を生成する高位合成方法に関し、特に、動作記述中の各処理に対して、その処理を実行するための資源を割り当てるアロケーション方法に関する。
【背景技術】
【０００２】
ＬＳＩを微細化するための技術が発展したことによって、１個のチップに集積することが可能なゲート数が格段に向上した。こうした大規模ＬＳＩを短期間に、かつ効率的に設計するために、近年、ハードウェアの機能的な動作記述に基づいて回路情報を生成するための高位合成技術が利用されるようになってきた。高位合成技術の詳細を記した文献としては、Ｄａｎｉｅｌ  Ｇａｊｓｋｉ、Ｎｉｋｉｌ  Ｄｕｔｔ、Ａｌｌｅｎ  Ｗｕ、Ｓｔｅｖｅ  Ｌｉｎ、”ＨＩＧＨ−ＬＥＶＥＬ  ＳＹＮＴＨＥＳＩＳ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｈｉｐ  ａｎｄ  Ｓｙｓｔｅｍ  Ｄｅｓｉｇｎ”、Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ、１９９２等がある。
【０００３】
図２８は、従来の高位合成方法を示すフローチャートである。まず、ＣＤＦＧ生成工程において、デジタル回路の機能的な動作を記述した入力ファイルに基づいてＣＤＦＧ（Ｃｏｎｔｒｏｌ  Ｄａｔａ  Ｆｌｏｗ  Ｇｒａｐｈ）を生成する（ステップＳ２０１）。そして、スケジューリング工程において、ＣＤＦＧ生成工程によって生成されたＣＤＦＧと制約ファイルに記述されたデジタル回路の制約条件とに基づいて、処理内容を表現するＣＤＦＧの各ノードをステップと呼ばれるクロックに同期した時間に割り当ててスケジューリングする（ステップＳ２０２）。次に、アロケーション工程において、スケジューリング工程によってスケジューリングされたＣＤＦＧの各ノードに対して、デジタル回路を構成するための資源を割り当てたアロケーション情報と回路情報とを生成する（ステップＳ９１）。その後、出力工程において回路情報を出力する（ステップＳ２０８）。
【０００４】
その後、アロケーションおよび回路情報生成工程によって生成された回路情報が、デジタル回路の制約条件を示す所定の基準を満たしているか否かを判断する（ステップＳ９２）。回路情報が所定の基準を満たしていないと判断したときは（ステップＳ９２においてＮＯ）、ステップＳ２０１へ戻る。
【０００５】
回路情報が所定の基準を満たしていると判断したときは（ステップＳ９２においてＹＥＳ）、論理合成工程において、アロケーションおよび回路情報生成工程によって生成された回路情報に論理合成処理を施す（ステップＳ９３）。そして、論理合成工程によって論理合成処理を施された回路情報が、デジタル回路の制約条件を示す所定の基準を満たしているか否かを判断する（ステップＳ９４）。回路情報が所定の基準を満たしていないと判断したときは（ステップＳ９４においてＮＯ）、ステップＳ２０１へ戻る。
【０００６】
回路情報が所定の基準を満たしていると判断したときは（ステップＳ９４においてＹＥＳ）、レイアウト工程において、論理合成工程によって論理合成処理を施された回路情報にレイアウト処理を施す（ステップＳ９５）。次に、レイアウト工程によってレイアウト処理を施された回路情報が、デジタル回路の制約条件を示す所定の基準を満たしているか否かを判断する（ステップＳ９６）。回路情報が所定の基準を満たしていないと判断したときは（ステップＳ９６においてＮＯ）、ステップＳ２０１へ戻る。回路情報が所定の基準を満たしていると判断したときは（ステップＳ９６においてＹＥＳ）、処理を終了する。
【０００７】
このように、高位合成から始まるＬＳＩの設計フローにおいては、ハードウェアの動作記述を入力として、高位合成、論理合成、レイアウトと設計工程を進める。各工程において、設計制約を満たさなければ、最悪の場合は高位合成工程からやり直すことになる。
【０００８】
従来は、高位合成工程以降の下流工程からの手戻りロスを最小限に抑えるために、高位合成工程においては、レイアウト時に配線が混み合わないように、演算器資源および記憶資源を共有する最大数に制限を与えたり、演算器資源と記憶資源との間の接続数に制限を与えたりしていた（西尾、金子、田湯、“配線資源を考慮した高位合成”、Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ｏｆ  ＩＥＩＣＥ、ＶＬＤ９８−１４７、ｐｐ．４９−５６、１９９９−０３）。
【０００９】
また、レイアウト工程においても、回路性能に影響がある資源の間の結線については、その結線の長さが長くなり過ぎないように、あるいは、レイアウト領域内における混雑度が高くならないように、配置するなど、各工程において別々に対策を講じて、手戻りの最小化を図ってきた。
【非特許文献１】Ｄａｎｉｅｌ  Ｇａｊｓｋｉ、Ｎｉｋｉｌ  Ｄｕｔｔ、Ａｌｌｅｎ  Ｗｕ、Ｓｔｅｖｅ  Ｌｉｎ、”ＨＩＧＨ−ＬＥＶＥＬ  ＳＹＮＴＨＥＳＩＳ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｈｉｐ  ａｎｄ  Ｓｙｓｔｅｍ  Ｄｅｓｉｇｎ”、Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ、１９９２
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、これはあくまでも経験的な観点から人間によって行われてきた対策であるため、高位合成工程とレイアウト工程との間の連携がなされていない。また、大規模ＬＳＩの開発においては、高位合成工程からレイアウト工程を完了するまでに数ヶ月を要するため、下流工程から上流工程へ後戻りする手戻りロスが発生すると、ＬＳＩを市場へ早期に投入することができない。
【００１１】
従来の高位合成方法は、下流工程において発生する問題、特に、レイアウト工程において発生する問題を詳細に解析することなく、人間の経験的な判断によって作成された設計制約のみに基づいて回路を生成していた。そのため、性能や面積等に関する設計制約が厳しくない回路、開発期間に余裕がある回路、または、回路規模が小さく下流工程において人間で手修正が可能な回路など、高位合成系を適用する回路に使用制限を設ける必要があるという問題があった。
【００１２】
また、高位合成工程以降の下流工程において設計制約を満たさなかった場合に、下流工程からのフィードバック情報を高位合成方法に反映するためには、高位合成系の入力となるプログラムファイルおよび設計制約ファイルを修正しなければならないという問題があった。
【００１３】
本発明は係る問題を解決するためになされたものであり、その目的は、高位合成以降の下流の工程、特に、レイアウト工程において、実現性の高いＲＴＬ回路を生成する高位合成方法を提供することにある。
【課題を解決するための手段】
【００１４】
係る目的を達成するために本発明に係る高位合成方法は、デジタル回路の機能的な動作を記述した入力ファイルに基づいてＣＤＦＧ（Ｃｏｎｔｒｏｌ  Ｄａｔａ  Ｆｌｏｗ  Ｇｒａｐｈ）を生成するＣＤＦＧ生成工程と、前記ＣＤＦＧ生成工程によって生成された前記ＣＤＦＧと制約ファイルに記述された前記デジタル回路の制約条件とに基づいて、処理内容を表現する前記ＣＤＦＧの各ノードをステップと呼ばれるクロックに同期した時間に割り当ててスケジューリングするスケジューリング工程と、前記スケジューリング工程によってスケジューリングされた前記ＣＤＦＧの各ノードに対して、前記デジタル回路を構成するための資源のレイアウトを示す資源レベルレイアウト情報に基づいて前記資源を割り当てたアロケーション情報と資源間の接続関係を表す回路情報を生成するアロケーションおよび回路情報生成工程と、前記アロケーションおよび回路情報生成工程によって生成された前記回路情報を出力する出力工程とを包含することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、高位合成以降の下流の工程、特に、レイアウト工程において、実現性の高いＲＴＬ回路を生成する高位合成方法を提供することができる。
【発明を実施するための最良の形態】
【００１６】
本実施の形態に係る高位合成方法においては、スケジューリング工程によってスケジューリングされたＣＤＦＧの各ノードに対して、デジタル回路を構成するための資源のレイアウトを示す資源レベルレイアウト情報に基づいて資源を割り当ててたアロケーション情報と資源間の接続関係を表す回路情報を生成する。このため、レイアウト工程によって得られた資源レベルレイアウト情報を高位合成工程のアロケーションフェーズへフィードバックすることができる。従って、高位合成工程以降の下流工程において設計制約を満たさなかった場合に、高位合成工程における入力ファイルまたは制約ファイルを修正することなく、高位合成工程からレイアウト工程までを自動的に実行することができる。その結果、レイアウト工程において、実現性の高いＲＴＬ回路を生成することができる。
【００１７】
前記アロケーションおよび回路情報生成工程は、前記スケジューリング工程によってスケジューリングされた前記ＣＤＦＧの各ノードに対して前記資源を割り当てた初期アロケーション情報と資源間の接続関係を表す初期回路情報を生成する初期アロケーションおよび初期回路情報生成工程と、前記初期アロケーションおよび初期回路情報生成工程によって生成された前記初期回路情報に基づいて前記資源レベルレイアウト情報を生成する資源レベルレイアウト工程と、前記初期アロケーションおよび初期回路情報生成工程によって生成された前記初期アロケーション情報と前記資源レベルレイアウト情報とに基づいて、前記ＣＤＦＧの各ノードに対する前記資源の割り当てを変更した修正アロケーション情報と資源間の接続関係を変更した修正回路情報を生成する再アロケーションおよび回路情報生成工程と、前記再アロケーションおよび回路情報生成工程によって生成された前記修正回路情報に基づいて前記資源レベルレイアウト情報を微修正する資源レベルレイアウト微修正工程とを含んでおり、所定の基準を満足するまで前記再アロケーションおよび回路情報生成工程と前記資源レベルレイアウト微修正工程とを繰り返して実行することが好ましい。
【００１８】
前記アロケーション情報は、ハードウエア資源割り当て情報とハードウエア資源のライフタイム情報とであることが好ましい。
【００１９】
前記資源レベルレイアウト情報は、資源間結線距離情報であることが好ましい。
【００２０】
前記資源レベルレイアウト情報は、資源間結線のレイアウト領域内混雑度情報であることが好ましい。
【００２１】
前記資源レベルレイアウト情報は、資源間結線距離情報と資源間結線のレイアウト領域内混雑度情報とからなる任意の関数で表現された、マクロ間結線情報であることが好ましい。
【００２２】
前記資源レベルレイアウト情報は、レイアウト影響度を係数として含んでいることが好ましい。
【００２３】
前記初期アロケーション工程は、可能な限りハードウエア資源を共有化しないように、前記ＣＤＦＧの各ノードに対して前記資源を割り当て、前記再アロケーション工程は、別々に実現されたハードウエア資源を共有化するように、前記ＣＤＦＧの各ノードに対する前記資源の割り当てを変更することが好ましい。
【００２４】
前記初期アロケーション工程は、可能な限りハードウエア資源を共有化するように、前記ＣＤＦＧの各ノードに対して前記資源を割り当て、前記再アロケーション工程は、共有化されたハードウエア資源を別々にアロケーションすることが好ましい。
【００２５】
前記再アロケーション工程は、記憶資源のレイアウト領域内配置分布ばらつきを計算し、前記レイアウト領域内配置分布ばらつきに基づいて、同期クロック回路の合成容易性を推定し、記憶資源共有化時には、合成容易性が高い共有化を選択することが好ましい。
【００２６】
前記記憶資源のレイアウト領域内配置分布ばらつきは、レイアウト領域を複数の領域に分割した各領域内に属する記憶資源の数のばらつきであることが好ましい。
【００２７】
前記記憶資源のレイアウト領域内配置分布ばらつきは、レイアウト領域内を階層的に分割した各階層ごとに計算したばらつきの合計であることが好ましい。
【００２８】
前記初期アロケーション工程は、可能な限りハードウエア資源を共有化するように、前記ＣＤＦＧの各ノードに対して前記資源を割り当て、前記再アロケーション工程は、共有化されたハードウエア資源を別々にアロケーションし、前記アロケーション工程は、前記再アロケーション工程において分割されたハードウェア資源を、前記初期アロケーション工程において共有されなかったハードウェア資源と共有するアロケーション変更工程をさらに含んでいることが好ましい。
【００２９】
前記資源レベルレイアウト情報は、レイアウト影響度をレイアウト影響係数として含んでおり、前記レイアウト影響係数を段階的に修正しながら前記再アロケーション工程と前記アロケーション変更工程とを繰り返して実行することが好ましい。
【００３０】
前記出力工程は、前記資源レベルレイアウト微修正工程によって微修正された前記資源レベルレイアウト情報をさらに出力することが好ましい。
【００３１】
以下、図面を参照して本発明の実施の形態を説明する。
【００３２】
（実施の形態１）
図１は、実施の形態１に係る高位合成方法を示すフローチャートである。まず、ＣＤＦＧ生成工程において、デジタル回路の機能的な動作を記述した入力ファイルに基づいてＣＤＦＧ（Ｃｏｎｔｒｏｌ  Ｄａｔａ  Ｆｌｏｗ  Ｇｒａｐｈ）を生成する（ステップＳ２０１）。
【００３３】
図２は、デジタル回路の機能的な動作を記述した入力ファイルの一例を示す図である。図２に示す入力ファイルの一例においては、デジタル回路の機能的な動作がＣ言語に従って記述されている。制約ファイルには、動作速度、消費電力、回路面積に対する回路制約条件が記述されている。
【００３４】
図３は、実施の形態１に係る高位合成方法におけるＣＤＦＧ生成工程によって生成されるＣＤＦＧを示す図である。実線の矢印はデータの流れを示しており、破線の矢印は制御の流れを示している。ＣＤＦＧ生成工程においては、入力ファイルの字句解析、構文解析、意味解析をこの順番に実行し、図３に示すＣＤＦＧを生成する。
【００３５】
そして、スケジューリング工程において、ＣＤＦＧ生成工程によって生成されたＣＤＦＧと制約ファイルに記述されたデジタル回路の制約条件とに基づいて処理内容を表現するＣＤＦＧの各ノードをステップと呼ばれるクロックに同期した時間に割り当ててスケジューリングする（ステップＳ２０２）。
【００３６】
図４は、スケジューリング工程によってステップが割り当てられたＣＤＦＧの各ノードを示す図である。図４に示す例では、ＣＤＦＧのノード＋１、ノードｍ１、ノード＋２、ノード＋３およびノードｍ２がステップＳ１に割り当てられている。ＣＤＦＧのノード＋４およびノードｍ３は、ＦＳＭの状態Ｓ２に割り当てられている。ＣＤＦＧのノード＊１およびノードｍ４は、ステップＳ３に割り当てられている。
【００３７】
次に、初期共有化アロケーションおよび回路情報生成工程において、スケジューリング工程によってスケジューリングされたＣＤＦＧの各ノードに対して、デジタル回路を構成するための演算器資源または記憶資源を可能な限り共有するように、演算器資源または記憶資源を割り当てた初期アロケーション情報と資源間の接続関係を表す初期回路情報を生成する（ステップＳ２０３）。
【００３８】
図５Ａは初期共有化アロケーションおよび回路情報生成工程によってＣＤＦＧの各ノードに資源が割り当てられた初期共有化アロケーション情報を示す図であり、図５Ｂは初期共有化アロケーションおよび回路情報生成工程によって生成された回路情報を示す図であり、図６は初期共有化アロケーションおよび回路情報生成工程によって生成された各資源のライフタイム情報を示す図である。デジタル回路を構成するための資源７０１は、記憶資源レジスタｒｅｇ１およびｒｅｇ２と加算器ａｄｄ１、ａｄｄ２およびａｄｄ３と乗算器ｍｕｌｔ１と２入力１出力のマルチプレクサ２−１ＭＵＸ１、２−１ＭＵＸ２、２−１ＭＵＸ３、２−１ＭＵＸ４および２−１ＭＵＸ５とを含んでいる。
【００３９】
図５および図６に示す例では、ステップＳ１に割り当てられたノードｍ１とステップＳ２に割り当てられたノードｍ３とステップＳ３に割り当てられたノードｍ４とに、レジスタｒｅｇ１が共通に割り当てられている。ステップＳ１に割り当てられたノードｍ２には、レジスタｒｅｇ２が割り当てられている。ステップＳ１に割り当てられたノード＋１とステップＳ２に割り当てられたノード＋４とには、加算器ａｄｄ１が共通に割り当てられている。
【００４０】
ステップＳ１に割り当てられたノード＋２には加算器ａｄｄ２が割り当てられており、ステップＳ１に割り当てられたノード＋３には加算器ａｄｄ３が割り当てられており、ステップＳ３に割り当てられたノード＊１には乗算器ｍｕｌｔ１が割り当てられている。
【００４１】
ステップＳ１に割り当てられたエッジａｄｄ２＿ｒｅｇ２およびエッジａｄｄ３＿ｒｅｇ２はともに資源ｒｅｇ２への同一ポートへの入力となるため、マルチプレクサ２−１ＭＵＸ１を挿入して資源ｒｅｇ２への入力が制御されている。ステップＳ１に割り当てられた入力エッジｉｎ１とステップＳ２に割り当てられたエッジｒｅｇ１＿ａｄｄ１とには、同様にマルチプレクサ２−１ＭＵＸ２が共通に挿入されている。
【００４２】
ステップＳ３に割り当てられたエッジｒｅｇ２＿ｍｕｘ４およびノードｉｎ６には、同様にマルチプレクサ２−１ＭＵＸ４が共通に挿入されている。ステップＳ１に割り当てられたエッジａｄｄ１＿ｒｅｇ１とステップＳ２に割り当てられたエッジｍｕｌｔ１＿ｒｅｇ１とには、同様にマルチプレクサ２−１ＭＵＸ５が共通に挿入されている。
【００４３】
その後、資源レベルレイアウト工程において、初期共有化アロケーションおよび回路情報生成工程によって生成された初期回路情報に基づいて資源レベルレイアウト情報を生成する（ステップＳ２０４）。
【００４４】
図７は、初期共有化アロケーションおよび回路情報生成工程によって生成された初期回路情報に基づいて資源レベルにおいてレイアウトされたデジタル回路を示す図である。破線によって囲まれた領域Ｒ１〜領域Ｒ６は、配線混雑度を推定する際に用いるレイアウト部分領域である。図７に示す例では、デジタル回路を６分割した例を示している。
【００４５】
図８は、資源レベルレイアウト工程によって生成された資源レベルレイアウト情報を示す図である。各欄にそれぞれ記載された数値は、各資源の間の結線の長さを示す資源間結線距離情報を示している。例えば、記憶資源レジスタｒｅｇ１とマルチプレクサ２−１ＭＵＸ２との間の資源間結線距離情報は「８」となっており、記憶資源レジスタｒｅｇ１とマルチプレクサ２−１ＭＵＸ５との間の資源間結線距離情報は「１」となっている。
【００４６】
図９は、資源レベルレイアウト工程によって生成された他の資源レベルレイアウト情報を示す図である。図９には、レイアウト部分領域Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５およびＲ６における配線の混雑の度合いを示す配線混雑度情報が示されている。配線混雑度情報は、各レイアウト部分領域Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５およびＲ６内に存在する配線の本数によって表されている。図９に示す例では、レイアウト部分領域Ｒ１においては配線混雑度情報が「９」になっており、レイアウト部分領域Ｒ２においては配線混雑度情報が「６」になっており、レイアウト部分領域Ｒ３においては配線混雑度情報が「６」になっている。レイアウト部分領域Ｒ４においては配線混雑度情報が「４」になっており、レイアウト部分領域Ｒ５においては配線混雑度情報が「６」になっており、レイアウト部分領域Ｒ６においては配線混雑度情報が「２」になっている。なお、配線混雑度情報は、配線可能な配線層数を考慮したり、水平垂直成分で別々に評価したりすることで、より実際のレイアウトを反映した複雑な表現方法を用いることもできる。
【００４７】
そして、資源レベルレイアウト工程によって生成された資源レベルレイアウト情報が、制約ファイルに記述されたデジタル回路の制約条件を示す所定の基準を満たしているか否かを判断する（ステップＳ２０５）。資源レベルレイアウト情報が所定の基準を満たしていると判断したときは（ステップＳ２０５においてＹＥＳ）、出力工程において回路情報を出力して（ステップＳ２０８）、処理を終了する。
【００４８】
資源レベルレイアウト情報が所定の基準を満たしていないと判断したときは（ステップＳ２０５においてＮＯ）、資源分割化アロケーションおよび回路情報生成工程において、初期共有化アロケーションおよび回路情報生成工程によって生成された初期アロケーション情報と資源レベルレイアウト工程によって生成された資源レベルレイアウト情報とに基づいて、ＣＤＦＧの各ノードに対する資源の割り当てを変更した修正アロケーション情報と資源間の接続関係を表す修正回路情報を生成する（ステップＳ２０６）。
【００４９】
資源分割化アロケーション工程（ステップＳ２０６）においては、初期アロケーション情報と資源レベルレイアウト情報とに基づいて、資源を共有することにより資源間結線距離が長くなり、あるいは、レイアウト領域内配線混雑度が高くなるために設計制約を満たさない原因となっている共有化された資源を抽出し、ＣＤＦＧの各ノードを別々の資源に割り当てるように資源割り当てを変更した修正アロケーション情報と資源間の接続関係を変更した修正回路情報を生成する。
【００５０】
図７に示す例では、記憶資源レジスタｒｅｇ１から出力されたデータが、マルチプレクサＭＵＸ２を経由して加算器ａｄｄ１によって演算され、マルチプレクサＭＵＸ５を経由して再び記憶資源レジスタｒｅｇ１に格納される。資源間結線情報から得られたマルチプレクサＭＵＸ２と記憶資源レジスタｒｅｇ１との間の結線距離８０１が長いために、動作速度あるいは消費電力などの回路性能が満たすことができない。
【００５１】
記憶資源レジスタｒｅｇ１は、ＣＤＦＧのノードｍ１、ノードｍ３およびノードｍ４によって共有されている。このように資源を共有化すると、接続先の資源からの距離が遠くなったり、また、各資源の間を接続する結線が集中して配置されるために、レイアウト領域内混雑度が高くなってしまうおそれがある。
【００５２】
図１０Ａは資源分割化アロケーションおよび回路情報生成工程によって資源の割り当てを変更された修正アロケーション情報を示す図であり、図１０Ｂは資源分割化アロケーションおよび回路情報生成工程によって生成された修正回路情報を示す図であり、図１１は資源分割化アロケーション工程によって生成された各資源の修正ライフタイム情報を示す図である。図５および図６をそれぞれ参照して前述した構成要素と同一の構成要素には同一の参照符号を付している。従って、これらの構成要素の詳細な説明は省略する。
【００５３】
前述した図５および図６と異なる点は、ステップＳ１に割り当てられたノードｍ１とステップＳ２に割り当てられたノードｍ３とがレジスタｒｅｇ１に共通に割り当てられており、ステップＳ３に割り当てられたノードｍ４はレジスタｒｅｇ３に割り当てられている点である。このように、ステップＳ１に割り当てられたノードｍ１とステップＳ２に割り当てられたノードｍ３とステップＳ３に割り当てられたノードｍ４との３個のノードに共通に割り当てられていたレジスタｒｅｇ１は、ステップＳ１のノードｍ１とステップＳ２のノードｍ３との２個のノードに共通に割り当てられたレジスタｒｅｇ１とステップＳ３のノードｍ４に割り当てられたレジスタｒｅｇ３とに分割されている。
【００５４】
次に、資源レベルレイアウト微修正工程において、資源分割化アロケーションおよび回路情報生成工程（ステップＳ２０６）によって生成された修正回路情報に基づいて資源レベルレイアウト情報を微修正する（ステップＳ２０７）。
【００５５】
図１２は、資源レベルレイアウト微修正工程によってレイアウトを微修正されたデジタル回路を示す図である。修正回路情報に基づいて記憶資源レジスタｒｅｇ１のレイアウトを微修正した結果、マルチプレクサＭＵＸ２と記憶資源レジスタｒｅｇ１との間の結線距離１２０１は、レイアウトを微修正する前のマルチプレクサＭＵＸ２と記憶資源レジスタｒｅｇ１との間の結線距離８０１よりも短くなっている。
【００５６】
その後、ステップＳ２０５へ戻る。このようにして、所定の基準を満足するまで資源分割化アロケーションおよび回路情報生成工程と資源レベルレイアウト微修正工程とを繰り返して実行する。
【００５７】
以上のように実施の形態１によれば、スケジューリング工程（ステップＳ２０１）によってスケジューリングされたＣＤＦＧの各ノードに対して、デジタル回路を構成するための資源のレイアウトを示す資源レベルレイアウト情報に基づいて資源割り当てを変更した修正アロケーション情報と資源間の接続関係を変更した修正回路情報を生成する。このため、資源レベルレイアウト工程（ステップＳ２０４）によって得られた資源レベルレイアウト情報を高位合成工程のアロケーションフェーズへフィードバックすることができる。従って、高位合成工程以降の下流工程において設計制約を満たさなかった場合に、高位合成工程における入力ファイルまたは制約ファイルを修正することなく、高位合成工程からレイアウト工程までを自動的に実行することができる。その結果、レイアウト工程において実現性の高い回路を生成することができる。
【００５８】
図１３Ａは実施の形態１に係る高位合成方法における資源分割化アロケーションおよび回路情報生成工程によって生成された他の修正アロケーション情報を示す図であり、図１３Ｂは資源分割化アロケーションおよび回路情報生成工程によって生成された他の修正回路情報を示す図であり、図１４は資源レベルレイアウト微修正工程によってレイアウトを微修正された他のデジタル回路を示す図である。前述した図１０Ａ、図１０Ｂ、図１１および図１２に示す例では、設計制約として回路性能を取り上げて説明したが、本発明はこれに限定されない。混雑度情報を用いて回路面積を評価することもできる。その場合、図７に示すように、マルチプレクサＭＵＸ２とレジスタｒｅｇ１との間の配線が長いために、領域Ｒ１内における配線混雑度が高くなる結果、回路面積が増大することになる。
【００５９】
そこで、資源分割化アロケーション工程（ステップＳ２０６）において、ノード＋１とノード＋４とで共有化されている演算器ａｄｄ１を分割するようにし、先の説明と同様にして、図１３Ａおよび図１３Ｂに示すようにアロケーション情報と回路情報とを再生成し、そして、図１４に示すようにレイアウトを微修正すればよい。
【００６０】
また、回路性能と回路面積を同時に評価して、両方の処理、あるいは、優先度を設けてどちらか一方の処理を行うと、回路性能と回路面積の両方を最適にすることができる。あるいは、トレードオフによる最適化を実施することが可能となる。
【００６１】
さらに、資源レベルレイアウト情報にマージンを付加することによって資源レベルレイアウト情報の値を大きくしたり、逆に値を小さくしたりして資源レベルレイアウト情報の値を変更できるようにすると、実際のレイアウト設計における制約を満たしたレイアウトの実現性の容易性を変更することもできる。具体的には、レイアウト影響度を表すレイアウト影響係数を設定し、設定したレイアウト影響係数の値を資源レベルレイアウト情報の値に乗算すればよい。
【００６２】
以上説明したように、実施形態１によれば、まず、可能な限り資源を共有するように高位合成されたＣＤＦＧをレイアウトする。そして、それを初期解として、資源レベルレイアウト情報の資源間結線距離が長く、あるいは、マクロ領域内配線混雑度が高く設計制約を満たさない原因となっている共有された資源を別々の資源に再アロケーションして、レイアウト微修正を行う。設計制約を満たすまでこれを繰り返すことにより、資源レベルのレイアウト結果に基づいて、高位レベルにおいて回路を生成することができるので、レイアウト後に設計制約に違反しない範囲において最適な資源共有化を図ることができる。
【００６３】
（実施の形態２）
図１５は、実施の形態２に係る高位合成方法を示すフローチャートである。ＣＤＦＧ生成工程（ステップＳ１５０１）およびスケジューリング工程（ステップＳ１５０２）は、実施の形態１において図１を参照して前述したＣＤＦＧ生成工程（ステップＳ２０１）およびスケジューリング工程（ステップＳ２０２）とそれぞれ同一である。従って、これらの工程の説明は省略する。
【００６４】
初期非共有化アロケーションおよび回路情報生成工程（ステップＳ１５０３）においては、可能な限りハードウエア資源を共有化しないように、ＣＤＦＧの各ノードに対して演算器資源または記憶資源を割り当てた初期アロケーション情報と資源間の接続関係を表す初期回路情報を生成する。
【００６５】
図１６Ａは初期非共有化アロケーションおよび回路情報生成工程によってＣＤＦＧの各ノードに資源が割り当てられた初期アロケーション情報を示す図であり、図１６Ｂは初期非共有化アロケーションおよび回路情報生成工程によって生成された初期回路情報を示す図であり、図１７は初期非共有化アロケーションおよび回路情報生成工程によって生成された各資源のライフタイム情報を示す図である。
【００６６】
図１６Ａ、図１６Ｂおよび図１７に示す例では、ステップＳ１に割り当てられたノードｍ１に、レジスタｒｅｇ１が割り当てられている。ステップＳ１に割り当てられたノードｍ２には、レジスタｒｅｇ２が割り当てられている。ステップＳ２に割り当てられたノードｍ３には、レジスタｒｅｇ３が割り当てられている。ステップＳ３に割り当てられたノードｍ４には、レジスタｒｅｇ４が割り当てられている。
【００６７】
ステップＳ１に割り当てられたノード＋１には、加算器ａｄｄ１が割り当てられている。ステップＳ１に割り当てられたノード＋２には加算器ａｄｄ２が割り当てられており、ステップＳ１に割り当てられたノード＋３には加算器ａｄｄ３が割り当てられている。ステップＳ２に割り当てられたノード＋４には、加算器ａｄｄ４が割り当てられている。ステップＳ３に割り当てられたノード＊１には、乗算器ｍｕｌｔ１が割り当てられている。
【００６８】
ステップＳ１に割り当てられたエッジａｄｄ２＿ｒｅｇ２およびエッジａｄｄ３＿ｒｅｇ２には、マルチプレクサ２−１ＭＵＸ１が共通に割り当てられている。ステップＳ３に割り当てられたエッジｒｅｇ２＿ｍｕｘ４とステップＳ３に割り当てられたノードｉｎ６とには、マルチプレクサ２−１ＭＵＸ２が共通に割り当てられている。
【００６９】
このように、初期非共有化アロケーションおよび回路情報生成工程においては、可能な限りハードウエア資源を共有化しないようにＣＤＦＧの各ノードに対して演算器資源または記憶資源を割り当てている。
【００７０】
そして、資源レベルレイアウト工程において、初期非共有化アロケーションおよび回路情報生成工程によって生成された初期回路情報に基づいて資源レベルレイアウト情報を生成する（ステップＳ１５０４）。
【００７１】
図１８は、初期非共有化アロケーションおよび回路情報生成工程によって生成された初期回路情報に基づいてレイアウトされたデジタル回路を示す図である。破線によって囲まれた領域Ｒ１〜領域Ｒ６は、配線混雑度を推定する際に用いるレイアウト部分領域である。図１８に示す例では、デジタル回路を６分割した例を示している。
【００７２】
図１９は、資源レベルレイアウト工程によって生成された資源レベルレイアウト情報を示す図である。各欄にそれぞれ記載された数値は、各資源の間の結線の長さを示す資源間結線距離情報を示している。例えば、記憶資源レジスタｒｅｇ１と記憶資源レジスタｒｅｇ２との間の資源間結線距離情報は「４」となっており、記憶資源レジスタｒｅｇ２と記憶資源レジスタｒｅｇ３との間の資源間結線距離情報は「１」となっている。
【００７３】
図２０は、資源レベルレイアウト工程によって生成された他の資源レベルレイアウト情報を示す図である。図２０には、レイアウト部分領域Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５およびＲ６における配線の混雑の度合いを示す配線混雑度情報が示されている。配線混雑度情報は、各レイアウト部分領域Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５およびＲ６内に存在する配線の本数によって表されている。図２０に示す例では、レイアウト部分領域Ｒ１においては配線混雑度情報が「７」になっており、レイアウト部分領域Ｒ２においては配線混雑度情報が「７」になっており、レイアウト部分領域Ｒ３においては配線混雑度情報が「６」になっている。レイアウト部分領域Ｒ４においては配線混雑度情報が「１」になっており、レイアウト部分領域Ｒ５においては配線混雑度情報が「３」になっており、レイアウト部分領域Ｒ６においては配線混雑度情報が「２」になっている。
【００７４】
そして、資源レベルレイアウト工程によって生成された資源レベルレイアウト情報が、制約ファイルに記述されたデジタル回路の制約条件を示す所定の基準を満たしているか否かを判断する（ステップＳ１５０５）。資源レベルレイアウト情報が所定の基準を満たしていると判断したときは（ステップＳ１５０５においてＹＥＳ）、出力工程において回路情報を出力して（ステップＳ２０８）、処理を終了する。
【００７５】
資源レベルレイアウト情報が所定の基準を満たしていないと判断したときは（ステップＳ１５０５においてＮＯ）、資源共有化アロケーションおよび回路情報生成工程において、初期非共有化アロケーションおよび回路情報生成工程によって生成された初期回路情報と資源レベルレイアウト工程によって生成された資源レベルレイアウト情報とに基づいて、ＣＤＦＧの各ノードに対する資源の割り当てを変更した修正回路情報を生成する（ステップＳ１５０６）。
【００７６】
資源共有化アロケーションおよび回路情報生成工程（ステップＳ１５０６）では、初期非共有化アロケーションおよび回路情報生成工程（ステップＳ１５０３）によって生成された初期アロケーション情報と資源レベルレイアウト工程（ステップＳ１５０４）によって生成された資源レベルレイアウト情報とに基づいて資源を共有化することによって資源割り当てを変更した修正アロケーション情報と資源間の接続関係を変更した修正回路情報を生成する。資源を共有化することにより資源間結線距離が長くなったりレイアウト領域内混雑度が高くなったりするため、ここでは、設計制約を満たす範囲において共有化することができる資源を抽出し、抽出した資源を共有化するように資源割り当てを変更する。
【００７７】
図１８に示す例では、図１７に示す初期アロケーション情報から、記憶資源ｒｅｇ１または記憶資源ｒｅｇ２はｒｅｇ３と共有化することができる。また、図１９に示す資源間結線距離情報から、共有化候補の記憶資源ｒｅｇ２と記憶資源ｒｅｇ３との間の結線距離１８０１の方が記憶資源ｒｅｇ１と記憶資源ｒｅｇ２との間の結線距離１８０２よりも短い。記憶資源ｒｅｇ２が記憶するデータが出力されるマルチプレクサ２−１ＭＵＸ１と記憶資源ｒｅｇ３が記憶するデータが出力される加算器ａｄｄ４との間の結線距離１８０３と、記憶資源ｒｅｇ１が記憶するデータが出力される加算器ａｄｄ１とマルチプレクサ２−１ＭＵＸ１との間の結線距離１８０４とは同じである。図２０に示すレイアウト領域内混雑度情報から、記憶資源ｒｅｇ１が属するレイアウト部分領域Ｒ１の混雑度と記憶資源ｒｅｇ２および記憶資源ｒｅｇ３が属するレイアウト部分領域Ｒ２の混雑度も同じである。距離が遠い資源を共有すると、結線距離が長くなってしまうため、資源共有化アロケーション工程においては記憶資源ｒｅｇ２と記憶資源ｒｅｇ３とを共有化するようにする。
【００７８】
図２１Ａは資源共有化アロケーションおよび回路情報生成工程によってＣＤＦＧのノードへの資源の割り当てを変更された修正アロケーション情報を示す図であり、図２１Ｂは資源共有化アロケーションおよび回路情報生成工程によって生成された修正回路情報を示す図であり、図２２は資源共有化アロケーションおよび回路情報生成工程によって生成された各資源のライフタイム情報を示す図である。
【００７９】
記憶資源ｒｅｇ２に割り当てられていたＣＤＦＧのノードｍ２と記憶資源ｒｅｇ３に割り当てられていたＣＤＦＧのノードｍ３とは、１個の記憶資源ｒｅｇ３に共通に割り当てられている。
【００８０】
次に、資源レベルレイアウト微修正工程（ステップＳ１５０７）に進み、資源共有化アロケーションを実施した後のＣＤＦＧを解析して、レイアウトを微修正する。
【００８１】
図２３は、資源レベルレイアウト微修正工程によってレイアウトを微修正されたデジタル回路を示す図である。この資源共有化アロケーション工程（ステップＳ１５０６）と資源レベルレイアウト微修正工程（ステップＳ１５０７）との一連の処理を、設計制約を満たす限り繰り返す。
【００８２】
以上のように実施の形態２によれば、まず、可能な限り資源を共有しないように高位合成されたＣＤＦＧをレイアウトする。そして、それを初期解として、資源間結線距離とレイアウト領域内配線混雑度とが悪化しても設計制約を満たす範囲に収まる程度に共有化することが可能な資源を抽出し、抽出した資源を共有化するように再アロケーションして、レイアウトを微修正する。設計制約を満たす範囲においてこれを繰り返すことにより、資源レベルのレイアウト結果に基づき、高位レベルで回路生成することができるので、レイアウト後に設計制約に違反しない範囲において最適な資源共有化を図ることができる。
【００８３】
なお、前述した実施の形態２においては、説明を簡単にするために、２個の共有化可能な資源に着目して共有化する例を説明したが、本発明はこれに限定されない。３個以上の資源を同時に評価して、共有化することもできる。
【００８４】
次に、実施の形態２の変形例を説明する。図２４は、実施の形態２に係る高位合成方法における同期方式クロック回路の合成容易性の推定方法を説明するための図である。実施の形態２の変形例が前述した実施の形態２と異なる点は、資源共有化アロケーション工程（ステップＳ１５０６）が、設計制約を満たすように資源を共有化する際に、全記憶資源の配置に基づいて同期方式クロック回路の合成容易性を推定する推定工程を含んでいる点である。
【００８５】
高位合成工程の後に実行されるレイアウト合成工程においては、各記憶資源に供給されるクロック信号がすべて同時刻に記憶資源へ到達するようにクロック回路が合成される。合成される同期方式クロック回路の規模は、記憶資源が配置される位置の分布状況に依存している。このため、記憶資源を共有化する際には記憶資源が配置される全体の分布を考慮することが重要である。
【００８６】
本明細書において「合成容易性」とは、回路を合成する容易性を意味し、合成される回路の規模が小さければ小さいほど回路の合成は容易になる。
【００８７】
実施の形態２の変形例においては、記憶資源の配置に粗密があればあるほど、合成される回路の規模が増大することを利用して、同期資源の配置分布を可能な限り均一にする。
【００８８】
図２４は、実施の形態２の変形例に係る高位合成方法における同期方式クロック回路の合成容易性の推定方法を説明するための図である。図２４に示す例では、レイアウト領域は４行×４列の１６個の領域に分割されている。図２４において黒丸は、記憶資源を示している。記憶資源Ｒ１は、前述した実施の形態２の条件下において、記憶資源Ｒ２および記憶資源Ｒ３のいずれとも共有することができるものとする。
【００８９】
各分割領域内にそれぞれ配置された記憶資源の数に基づいて、分割領域内の記憶資源の数の分散を計算する。初期状態においては分散値は０．３３となり、記憶資源Ｒ１と記憶資源Ｒ２とを共有すると分散値は０．２７となり、記憶資源Ｒ１と記憶資源Ｒ３とを共有すると分散値は０．５３となる。この場合、分散値がより小さく、配置位置のばらつきがより少なくなるように、記憶資源Ｒ１と記憶資源Ｒ２とを共有する。
【００９０】
レイアウト領域が広いときは、段階的に分散を計算することによって、推定精度を高めることができる。図２４に示す例では、まず、実線によって区切られた領域（第１階層）ごとに分散を計算する。次に、破線によって区切られた領域（第２階層）に関して第１階層ごとに分散を計算する。その後、前述した総計５個の分散値の和に基づいて合成容易性を推定する。この場合、初期状態においては分散値は１．８３となり、記憶資源Ｒ１と記憶資源Ｒ２とを共有すると分散値は１．８３となり、記憶資源Ｒ１と記憶資源Ｒ３とを共有すると分散値は３．１６となる。
【００９１】
以上のように実施の形態２の変形例によれば、記憶資源の配置分布を可能な限り均一にすることができる。このため、合成される同期方式クロック回路の規模が増大することを抑制することができる。その結果、クロック回路が消費する電力量を低減することができる。
【００９２】
（実施の形態３）
図２５は、実施の形態３に係る高位合成方法を示すフローチャートである。図１および図１５を参照して前述した高位合成方法を示すフローチャートの構成要素と同一の構成要素には同一の参照符号を付している。従って、これらの構成要素の詳細な説明は省略する。
【００９３】
ＣＤＦＧ生成工程（ステップＳ２０１）〜資源レベルレイアウト微修正工程（ステップＳ２０７）は、図１を参照して前述した実施の形態１における同工程と同一である。資源共有化アロケーションおよび回路情報生成工程（ステップＳ１５０６）および資源レベルレイアウト微修正工程（ステップＳ１５０７）は、図１５を参照して前述した実施の形態２における同工程と同一である。
【００９４】
資源レベルレイアウト情報が所定の基準を満たしていると判断したときは（ステップＳ２０５においてＹＥＳ）、アロケーション情報に基づいて共有することができる資源であって、かつ、未だ共有されていないハードウェア資源間の組み合わせが存在しないか否かを判断する（ステップＳ２３０１）。
【００９５】
アロケーション情報に基づいて共有することができる資源であって、かつ、未だ共有されていないハードウェア資源間の組み合わせが存在すると判断されたときは（ステップＳ２３０１においてＮＯ）、その資源を共有化することによって、資源間結線距離が長くなり、またはレイアウト領域内混雑度が高くなっても設計制約を満たす範囲において共有化することができる資源の組み合わせを抽出し、資源を共有化することができるように資源割り当てを変更する。
【００９６】
実施の形態３においては、図１１に示すアロケーション情報から、共有することができる資源であって、かつ未だ共有されていないハードウェア資源間の組み合わせである、記憶資源ｒｅｇ２に割り当てられたノードｍ２と、資源分割化アロケーションおよび回路情報生成工程（ステップＳ２０６）によって資源分割され記憶資源ｒｅｇ３に割り当てられたノードｍ４とを共有の候補として選択する。また、資源レベルレイアウト情報に基づいて、記憶資源ｒｅｇ２と記憶資源ｒｅｇ３とが近距離にあるので、共有化しても資源間結線距離とレイアウト領域内混雑度とに関して設計制約に違反することがないと判断することができる。次に、前述した資源共有化アロケーションおよび回路情報生成工程（ステップＳ１５０６）へ進む。
【００９７】
図２６は、実施の形態３に係る高位合成方法における資源レベルレイアウト微修正工程によってレイアウトを微修正されたデジタル回路を示す図である。図２６には、図１２に示すデジタル回路に対して、資源共有化アロケーション工程（ステップＳ１５０６）において、ノードｍ２とノードｍ４とを記憶資源ｒｅｇ３に割り当てるように資源の割り当てを変更し、資源レベルレイアウト微修正工程（ステップＳ１５０７）によってレイアウトを微修正した結果が示されている。このような資源共有化アロケーションおよび回路情報生成工程の処理を設計制約を満たす限り繰り返す。
【００９８】
以上のように実施の形態３によれば、まず、実施の形態１を実施した後に、別々の資源に再アロケーションされた資源に関して、初期解には存在しなかった組み合わせの資源を可能な限り共有することによって、資源レベルのレイアウト結果に基づいて高位レベルにおいて回路生成をすることができる。このため、レイアウトした後において設計制約に違反しない範囲において最適な資源の共有化を図ることができる。
【００９９】
（実施の形態４）
図２７は、実施の形態４に係る高位合成方法を示すフローチャートである。図１、図１５および図２５を参照して前述した高位合成方法を示すフローチャートの構成要素と同一の構成要素には同一の参照符号を付している。従って、これらの構成要素の詳細な説明は省略する。
【０１００】
ＣＤＦＧ生成工程（ステップＳ２０１）〜資源レベルレイアウト微修正工程（ステップＳ２０７）は、図１を参照して前述した実施の形態１における同工程と同一である。資源共有化アロケーションおよび回路情報生成工程（ステップＳ１５０６）および資源レベルレイアウト微修正工程（ステップＳ１５０７）は、図１５を参照して前述した実施の形態２における同工程と同一である。アロケーション情報に基づいて共有することができる資源であって、かつ、未だ共有されていないハードウェア資源間の組み合わせが存在しないか否かを判断する工程（ステップＳ２３０１）は、図２５を参照して前述した実施の形態３における同工程と同一である。
【０１０１】
初期レイアウト影響係数設定工程（ステップＳ２５０１）において、資源レベルレイアウト情報の影響度を表す初期レイアウト影響係数として、本来設定したい目標レイアウト影響係数よりも小さい値を設定する。例えば、判定工程（ステップＳ２０５）において資源間結線距離情報の値をそのまま使用する場合は、目標レイアウト影響係数が１．０となり、初期レイアウト影響係数は１．０よりも小さい値が設定される。資源レベルレイアウト情報は、１．０よりも小さい値を乗じた値に更新される。
【０１０２】
次に、初期レイアウト影響係数が考慮された資源レベルレイアウト情報に基づいて、判定工程（ステップＳ２０５）によって基準が満たされていると判断されるまで資源分割化アロケーションおよび回路情報生成工程（ステップＳ２０６）と資源レベルレイアウト微修正工程（ステップＳ２０７）とを繰り返す。判定工程（ステップＳ２０５）によって基準が満たされていると判断されたときの資源レベルレイアウト情報の結果は、初期レイアウト影響係数を満たした場合の結果であるため、未だ本来のレイアウト影響度を考慮した制約を満たしていないけれども、制約に大きく違反した重大なエラーを取り除くことができる。
【０１０３】
その後、前述した実施の形態３と同様に、判定工程（ステップＳ２３０１）において、アロケーション情報に基づいて、共有可能な資源であって、且つ未だ共有化されていないハードウェア資源間の組み合わせが存在するか否かを判断する。ハードウェア資源間の組み合わせが存在すると判断したときは、その資源を共有化することによって、資源間結線距離が長くなり、またはレイアウト領域内混雑度が高くなっても設計制約を満たす範囲において共有化することのできる資源の組み合わせを抽出する（ステップＳ２３０１においてＮＯ）。
【０１０４】
そして、資源共有化アロケーションおよび回路情報生成工程（ステップＳ１５０６）において、資源を共有化するように資源割り当てを変更する。次に、資源レベルレイアウト微修正工程（ステップＳ１５０７）においてレイアウトを微修正する。
【０１０５】
共有可能な資源であって、且つ未だ共有化されていないハードウェア資源間の組み合わせが存在しないと判断したときは（ステップＳ２３０１においてＹＥＳ）、レイアウト影響係数判定工程（ステップＳ２５０２）において、現在のレイアウト影響係数が、最終的に与えるべき目標レイアウト影響係数であるか否かを判断する。現在のレイアウト影響係数が、最終的に与えるべき目標レイアウト影響係数であると判断したときは（ステップＳ２５０２においてＹＥＳ）、高位合成処理を終了する。
【０１０６】
現在のレイアウト影響係数が、最終的に与えるべき目標レイアウト影響係数でないと判断したときは（ステップＳ２５０２においてＮＯ）、レイアウト影響係数修正工程（ステップＳ２５０３）において、現在のレイアウト影響係数が目標レイアウト影響係数に近づくように現在のレイアウト影響係数を修正する。そして、ステップＳ２０５へ戻る。
【０１０７】
このように、ステップＳ２０５からステップＳ２５０３までの処理をレイアウト影響係数が目標レイアウト影響係数になるまで繰り返す。緩和されたレイアウト情報から順番に処理を進めることによって、１回の処理において制約に違反する資源割り当てを探索する空間を削減することができる。このため、高位合成処理を効率化することができる。また、レイアウト影響係数を変更しながら資源の割り当て処理を繰り返すため、初期解に対する依存の影響が前述した実施の形態３よりも小さい解空間の検索が可能になる。
【産業上の利用可能性】
【０１０８】
本発明は、ディジタル回路を構成するためのＲＴＬ回路記述を生成する高位合成方法に適用することができる。
【図面の簡単な説明】
【０１０９】
【図１】実施の形態１に係る高位合成方法を示すフローチャート
【図２】デジタル回路の機能的な動作を記述した入力ファイルの一例を示す図
【図３】実施の形態１に係る高位合成方法におけるＣＤＦＧ生成工程によって生成されるＣＤＦＧを示す図
【図４】実施の形態１に係る高位合成方法におけるスケジューリング工程によってスケジューリングされたＣＤＦＧを示す図
【図５Ａ】実施の形態１に係る高位合成方法における初期共有化アロケーションおよび回路情報生成工程によってＣＤＦＧの各ノードに資源が割り当てられた初期共有化アロケーション情報を示す図
【図５Ｂ】初期共有化アロケーションおよび回路情報生成工程によって生成された回路情報を示す図
【図６】実施の形態１に係る高位合成方法における初期共有化アロケーションおよび回路情報生成工程によって生成された各資源のライフタイム情報を示す図
【図７】実施の形態１に係る高位合成方法における初期共有化アロケーション工程によって生成された初期高位合成情報に基づいてレイアウトされたデジタル回路を示す図
【図８】実施の形態１に係る高位合成方法における資源レベルレイアウト工程によって生成された資源レベルレイアウト情報を示す図
【図９】実施の形態１に係る高位合成方法における資源レベルレイアウト工程によって生成された他の資源レベルレイアウト情報を示す図
【図１０Ａ】実施の形態１に係る高位合成方法における資源分割化アロケーションおよび回路情報生成工程によってＣＤＦＧのノードに対する資源割り当てを変更された修正アロケーション情報を示す図
【図１０Ｂ】資源分割化アロケーションおよび回路情報生成工程によって生成された修正回路情報を示す図
【図１１】実施の形態１に係る高位合成方法における資源分割化アロケーションおよび回路情報生成工程によって生成された各資源の修正ライフタイム情報を示す図
【図１２】実施の形態１に係る高位合成方法における資源レベルレイアウト微修正工程によってレイアウトを微修正されたデジタル回路を示す図
【図１３Ａ】実施の形態１に係る高位合成方法における資源分割化アロケーションおよび回路情報生成工程によって生成された他の修正アロケーション情報を示す図
【図１３Ｂ】資源分割化アロケーションおよび回路情報生成工程によって生成された他の修正回路情報を示す図
【図１４】実施の形態１に係る高位合成方法における資源レベルレイアウト微修正工程によってレイアウトを微修正された他のデジタル回路を示す図
【図１５】実施の形態２に係る高位合成方法を示すフローチャート
【図１６Ａ】実施の形態２に係る高位合成方法における初期非共有化アロケーションおよび回路情報生成工程によってＣＤＦＧの各ノードに資源が割り当てられた初期非共有化アロケーション情報を示す図
【図１６Ｂ】初期非共有化アロケーションおよび回路情報生成工程によって生成された初期回路情報を示す図
【図１７】実施の形態２に係る高位合成方法における初期非共有化アロケーションおよび回路情報生成工程によって生成された各資源のライフタイム情報を示す図
【図１８】実施の形態２に係る高位合成方法における初期非共有化アロケーション工程によって生成された初期高位合成情報に基づいてレイアウトされたデジタル回路を示す図
【図１９】実施の形態２に係る高位合成方法における資源レベルレイアウト工程によって生成された資源レベルレイアウト情報を示す図
【図２０】実施の形態２に係る高位合成方法における資源レベルレイアウト工程によって生成された他の資源レベルレイアウト情報を示す図
【図２１Ａ】実施の形態２に係る高位合成方法における資源共有化アロケーションおよび回路情報生成工程によって資源の割り当てを変更された修正アロケーション情報を示す図
【図２１Ｂ】資源共有化アロケーションおよび回路情報生成工程によって生成された修正回路情報を示す図
【図２２】実施の形態２に係る高位合成方法における資源共有化アロケーションおよび回路情報生成工程によって生成された各資源の修正ライフタイム情報を示す図
【図２３】実施の形態２に係る高位合成方法における資源レベルレイアウト微修正工程によってレイアウトを微修正されたデジタル回路を示す図
【図２４】実施の形態２に係る高位合成方法における同期方式クロック回路の合成容易性の推定方法を説明するための図
【図２５】実施の形態３に係る高位合成方法を示すフローチャート
【図２６】実施の形態３に係る高位合成方法における資源レベルレイアウト微修正工程によってレイアウトを微修正されたデジタル回路を示す図
【図２７】実施の形態４に係る高位合成方法を示すフローチャート
【図２８】従来の高位合成方法を示すフローチャート
【符号の説明】
【０１１０】
Ｓ２０１  ＣＤＦＧ生成工程
Ｓ２０２  スケジューリング工程
Ｓ２０３  初期共有化アロケーション工程
Ｓ２０４  資源レベルレイアウト工程
Ｓ２０６  資源分割化アロケーション工程
Ｓ２０７  資源レベルレイアウト微修正工程
Ｓ１５０１  ＣＤＦＧ生成工程
Ｓ１５０２  スケジューリング工程
Ｓ１５０６  資源共有化アロケーション工程
Ｓ１５０７  資源レベルレイアウト微修正工程
Ｓ２５０１  初期レイアウト影響係数設定工程
【図１】
2004164627.tif 000003
【図２】
2004164627.tif 000004
【図３】
2004164627.tif 000005
【図４】
2004164627.tif 000006
【図５Ａ】
2004164627.tif 000007
【図５Ｂ】
2004164627.tif 000008
【図６】
2004164627.tif 000009
【図７】
2004164627.tif 000010
【図８】
2004164627.tif 000011
【図９】
2004164627.tif 000012
【図１０Ａ】
2004164627.tif 000013
【図１０Ｂ】
2004164627.tif 000014
【図１１】
2004164627.tif 000015
【図１２】
2004164627.tif 000016
【図１３Ａ】
2004164627.tif 000017
【図１３Ｂ】
2004164627.tif 000018
【図１４】
2004164627.tif 000019
【図１５】
2004164627.tif 000020
【図１６Ａ】
2004164627.tif 000021
【図１６Ｂ】
2004164627.tif 000022
【図１７】
2004164627.tif 000023
【図１８】
2004164627.tif 000024
【図１９】
2004164627.tif 000025
【図２０】
2004164627.tif 000026
【図２１Ａ】
2004164627.tif 000027
【図２１Ｂ】
2004164627.tif 000028
【図２２】
2004164627.tif 000029
【図２３】
2004164627.tif 000030
【図２４】
2004164627.tif 000031
【図２５】
2004164627.tif 000032
【図２６】
2004164627.tif 000033
【図２７】
2004164627.tif 000034
【図２８】
2004164627.tif 000035