(57)【要約】【課題】  処理に必要なクロック周期数を増加させることなく、割付リソースの共有化を効果的に行うレイアウトベース高位合成方法を提供する。【解決手段】  回路の設計仕様に含まれる演算やデータの流れを表すグラフＣＤＦＧを生成し（Ｓ１０１）、処理に必要なクロック周期数を求め、割付リソース接続グラフを生成する（Ｓ１０２）。割付リソース接続グラフに同機能のハードウェアリソースが割り付けられた節点が含まれていれば、当該節点間に、節点の共有化を制御する共有化枝を付加する（Ｓ１０３）。共有化枝付加後の割付リソース接続グラフを仮にレイアウトし（Ｓ１０４）、レイアウト結果に基づき、割付リソース接続グラフの節点を共有化する（Ｓ１０５）。共有化枝には、引力、斥力などの属性や重みが与えられる。これにより、レイアウト結果におけるノード間の距離を制御し、リソースが共有化される程度を制御する。【選択図】  図１
2006011878.tif 000002
【特許請求の範囲】
【請求項１】
レイアウトを考慮した半導体集積回路の高位合成方法であって、
設計対象回路の機能記述に含まれる演算を節点に、前記機能記述に含まれるデータの流れを枝に対応づけたフローグラフを生成するフローグラフ生成工程と、
前記フローグラフの各節点に使用可能なハードウェアリソースを割り付け、前記フローグラフの枝で表現された順序付けを考慮して、前記フローグラフの各節点をクロック周期に相当する状態に割り当てた結果から、前記フローグラフで表現される処理の実行に要する総状態数を求めるとともに、前記フローグラフの、ハードウェアリソース割付後の節点に対応した節点と、前記フローグラフの枝に対応した信号枝とを有する割付リソース接続グラフを生成する初期アロケーションスケジューリング工程と、
前記割付リソース接続グラフに含まれる、共有化可能なハードウェアリソースが割り付けられた節点の組について、当該節点間に、節点の共有化を制御するための共有化枝を付加する共有化枝生成工程と、
共有化枝付加後の割付リソース接続グラフを仮にレイアウトするリソース配置工程と、
前記リソース配置工程で求めたレイアウト結果に基づき、前記割付リソース接続グラフの節点を共有化するリソース共有化工程とを備えた、高位合成方法。
【請求項２】
前記共有化枝生成工程は、前記状態割り当て結果において異なる状態に割り当てられた節点がある場合には、前記割付リソース接続グラフの対応する節点間に共有化を促進する引力共有化枝を付加し、前記状態割り当て結果において同じ状態に割り当てられた節点がある場合には、前記割付リソース接続グラフの対応する節点間に共有化を抑制する斥力共有化枝を付加し、
前記リソース配置工程は、引力共有化枝によって接続された節点同士を近接して、斥力共有化枝によって接続された節点同士を離間して配置することを特徴とする、請求項１に記載の高位合成方法。
【請求項３】
前記共有化枝生成工程は、前記割付リソース接続グラフの枝に対して重み付けを行い、
前記リソース配置工程は、前記共有化枝生成工程で付された重みに基づき、前記レイアウト結果を求めることを特徴とする、請求項２に記載の高位合成方法。
【請求項４】
前記共有化枝生成工程は、総状態数が前記初期アロケーションスケジューリング工程で求めた値を超えない範囲内で前記フローグラフの各節点を状態に割り当て直した際に、異なる状態に割り当てられる可能性が高い節点間ほど、前記割付リソース接続グラフの対応する節点間に付加される引力共有化枝の重みを、より共有化を促進する値に設定することを特徴とする、請求項３に記載の高位合成方法。
【請求項５】
前記共有化枝生成工程は、総状態数が前記初期アロケーションスケジューリング工程で求めた値を超えない範囲内で前記フローグラフの各節点を状態に割り当て直した際に、異なる状態に割り当てられる可能性が低い節点間ほど、前記割付リソース接続グラフの対応する節点間に付加される斥力共有化枝の重みを、より共有化を抑制する値に設定することを特徴とする、請求項３に記載の高位合成方法。
【請求項６】
前記共有化枝生成工程は、前記状態割り当て結果において同じ状態に割り当てられた節点が、当該状態内にある１本以上の信号枝を介して接続されている場合には、前記割付リソース接続グラフの対応する節点間に付加された斥力共有化枝の重みを無効な値に設定することを特徴とする、請求項３に記載の高位合成方法。
【請求項７】
前記共有化枝生成工程は、前記状態割り当て結果において異なる状態に割り当てられた節点がある場合には、前記割付リソース接続グラフの対応する節点間に共有化を促進する重み付けされた引力共有化枝を付加し、
前記リソース配置工程は、前記共有化枝生成工程で付された重みに基づき、引力共有化枝によって接続された節点同士を近接して配置することを特徴とする、請求項１に記載の高位合成方法。
【請求項８】
前記リソース配置工程は、総状態数が前記初期アロケーションスケジューリング工程で求めた値を超えない範囲内で前記フローグラフの各節点を状態に割り当て直し、共有化枝付加後の割付リソース接続グラフを仮にレイアウトするスケジューリング付きリソース配置工程であることを特徴とする、請求項１に記載の高位合成方法。
【請求項９】
前記リソース共有化工程で処理された割付リソース接続グラフに対して、共有化枝を付加し直す共有化枝再生成工程をさらに備え、
所定の条件を満たすまで、前記スケジューリング付きリソース配置工程と前記リソース共有化工程と前記共有化枝再生成工程とを繰り返し実行することを特徴とする、請求項８に記載の高位合成方法。
【請求項１０】
前記リソース共有化工程は、
前記割付リソース接続グラフから共有化すべき節点の組を選択する共有化対象選択工程と、
前記共有化対象選択工程で選択された節点を共有化する被選択リソース共有化工程と、
前記被選択リソース共有化工程で処理された割付リソース接続グラフに対して、共有化枝を付加し直す共有化枝再生成工程と、
前記共有化枝再生成工程で処理された割付リソース接続グラフに基づき、前記リソース配置工程で得られたレイアウト結果を修正するレイアウト結果修正工程とを含み、
所定の条件を満たすまで、前記共有化対象選択工程と前記被選択リソース共有化工程と前記共有化枝再生成工程と前記レイアウト結果修正工程とを繰り返し実行する、逐次改良型リソース共有化工程であることを特徴とする、請求項１に記載の高位合成方法。
【請求項１１】
前記リソース共有化工程は、前記割付リソース接続グラフに含まれる、共有化可能なハードウェアリソースが割り付けられた節点の組について優先度を求め、予め定めた範囲内で、求めた優先度が高い順に、節点を共有化することを特徴とする、請求項１に記載の高位合成方法。
【請求項１２】
前記リソース共有化工程における優先度は、前記リソース配置工程で求めたレイアウト結果における節点間の距離に反比例することを特徴とする、請求項１１に記載の高位合成方法。
【請求項１３】
前記共有化枝生成工程は、前記割付リソース接続グラフの枝に対して重み付けを行い、
前記リソース共有化工程における優先度は、節点間に付加された枝に付された重みを、前記リソース配置工程で求めたレイアウト結果における節点間の距離で割った値に比例することを特徴とする、請求項１１に記載の高位合成方法。
【請求項１４】
前記共有化枝生成工程は、前記割付リソース接続グラフの枝に対して重み付けを行い、
前記リソース共有化工程における優先度は、節点間に付加された枝に付された重みに比例する項と、前記リソース配置工程で求めたレイアウト結果における節点間の距離に反比例する項とを有する計算式を用いて計算されることを特徴とする、請求項１１に記載の高位合成方法。
【請求項１５】
共有化枝付加後の割付リソース接続グラフについて、レイアウトの困難度を評価するレイアウト困難度評価工程と、
前記レイアウト困難度評価工程においてレイアウト困難と判断された場合に、共有化枝付加後の割付リソース接続グラフから、共有化効率の低い引力共有化枝を選択する引力共有化枝選択工程と、
前記引力共有化枝選択工程で選択された引力共有化枝の重みを削減する引力共有化枝重み削減工程とをさらに備えた、請求項３に記載の高位合成方法。
【請求項１６】
共有化枝付加後の割付リソース接続グラフについて、レイアウトの困難度を評価するレイアウト困難度評価工程と、
前記レイアウト困難度評価工程においてレイアウト困難と判断された場合に、共有化枝付加後の割付リソース接続グラフから、共有化効率の低い引力共有化枝を選択する引力共有化枝選択工程と、
前記引力共有化枝選択工程で選択された引力共有化枝を削除する引力共有化枝削除工程とをさらに備えた、請求項７に記載の高位合成方法。
【請求項１７】
前記レイアウト困難度評価工程は、共有化枝付加後の割付リソース接続グラフの信号枝および引力共有化枝に付された重みの総和に基づき、レイアウトの困難度を評価することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項１８】
前記レイアウト困難度評価工程は、共有化枝付加後の割付リソース接続グラフの信号枝に付された重みの総和と引力共有化枝に付された重みの総和との差に基づき、レイアウトの困難度を評価することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項１９】
前記レイアウト困難度評価工程は、共有化枝付加後の割付リソース接続グラフの信号枝および引力共有化枝に付された重みの総和に対する引力共有化枝に付された重みの総和の割合に基づき、レイアウトの困難度を評価することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項２０】
前記レイアウト困難度評価工程は、共有化枝付加後の割付リソース接続グラフに基づき、所定値以下の重みを有する引力共有化枝に対してダミーのハードウェアリソースを割り付けた節点を追加することにより、評価用割付リソース接続グラフを生成し、前記評価用割付リソース接続グラフに含まれるすべての節点のそれぞれと１本の信号枝によって接続された１次隣接節点の総数と、前記評価用割付リソース接続グラフに含まれるすべての節点のそれぞれと２本以内の信号枝を介して接続された２次以内隣接節点の総数とを求め、求めた２つの総数の対数値の差に基づきレイアウトの困難度を評価することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項２１】
前記引力共有化枝選択工程は、両端に接続された節点に割り付けられたハードウェアリソースのビット幅の差が大きい引力共有化枝を、共有化効率の低い引力共有化枝として選択することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項２２】
前記引力共有化枝選択工程は、両端に接続された節点に割り付けられたハードウェアリソースにおける遅延時間の差が大きい共有化枝を、共有化効率の低い引力共有化枝として選択することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項２３】
前記引力共有化枝選択工程は、両端に接続された節点に割り付けられたハードウェアリソースの面積のうち小さい方の値が小さい引力共有化枝を、共有化効率の低い引力共有化枝として選択することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項２４】
前記引力共有化枝選択工程は、より共有化を抑制する重みが付された引力共有化枝を、共有化効率の低い引力共有化枝として選択することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項２５】
前記引力共有化枝選択工程は、両端に接続された節点に割り付けられたハードウェアリソースの出力値のライフタイムが重なる確率が大きい引力共有化枝を、共有化効率の低い引力共有化枝として選択することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項２６】
前記引力共有化枝選択工程が、両端に接続された節点に割り付けられたハードウェアリソースのビット幅の差に比例する項と、前記ハードウェアリソースの遅延時間の差に比例する項と、前記ハードウェアリソースの面積のうち小さい方の値に反比例する項と、前記ハードウェアリソースの出力値のライフタイムが重なる確率に比例する項と、付された重みに反比例する項とを有する計算式による評価値が大きい引力共有化枝を、共有化効率の低い引力共有化枝として選択することを特徴とする、請求項１５または１６に記載の高位合成方法。
【請求項２７】
前記リソース配置工程は、共有化可能なハードウェアリソースが割り付けられた節点を同じ位置に配置できるレイアウトモデルに従い、共有化枝付加後の割付リソース接続グラフを仮にレイアウトすることを特徴とする、請求項１に記載の高位合成方法。
【請求項２８】
前記リソース配置工程におけるレイアウトモデルでは、同じ位置に配置できる節点の個数が予め制限されていることを特徴とする、請求項２７に記載の高位合成方法。
【請求項２９】
前記リソース配置工程は、配置済みの節点と同じ位置に新たな節点を配置したときに、当該節点に割り付けられたハードウェアリソースの入力側に設けられる選択回路の遅延時間を推定した上で、前記選択回路の遅延時間を含んだ、当該節点が割り当てられた状態の処理時間を推定し、推定された処理時間がクロック周期に近い場合には、新たに配置された節点を他の位置に移動し、以降の処理では前記配置済みの節点と同じ位置に節点を配置することを禁止することを特徴とする、請求項２７に記載の高位合成方法。
【請求項３０】
前記リソース配置工程は、共有化枝付加後の割付リソース接続グラフを仮にレイアウトする際に、同じ位置に配置される節点の個数が所定値を超えた場合に評価値が悪化する評価関数を用いることを特徴とする、請求項２７に記載の高位合成方法。
【請求項３１】
前記リソース配置工程は、共有化枝付加後の割付リソース接続グラフの節点を、当該節点に割り付けられたハードウェアリソースに応じて、複数の単位要素と単位要素間を接続する接続要素とに変換し、変換後の割付リソース接続グラフを仮にレイアウトすることを特徴とする、請求項１に記載の高位合成方法。
【請求項３２】
前記リソース配置工程は、共有化枝付加後の割付リソース接続グラフの節点に割り付けられたハードウェアリソースが固定の形状を有する剛リソースである場合には、高い密度で前記接続要素を設け、前記ハードウェアリソースが可変の形状を有する軟リソースである場合には、低い密度で前記接続要素を設けることを特徴とする、請求項３１に記載の高位合成方法。
【請求項３３】
前記リソース配置工程は、前記剛リソースであるハードウェアリソースには、大きな重みを付した接続要素を設け、前記軟リソースであるハードウェアリソースには、小さな重みを付した接続要素を設け、各接続要素に付された重みに基づき、変換後の割付リソース接続グラフを仮にレイアウトすることを特徴とする、請求項３２に記載の高位合成方法。
【請求項３４】
前記剛リソースであるハードウェアリソースには、上下左右４方向に隣接するすべての単位要素間を接続する接続要素が設けられることを特徴とする、請求項３２に記載の高位合成方法。
【請求項３５】
前記軟リソースであるハードウェアリソースには、１本の接続ですべての単位要素を接続する接続要素が設けられることを特徴とする、請求項３２に記載の高位合成方法。
【請求項３６】
前記軟リソースであるハードウェアリソースには、単位要素間を、上下左右４方向に隣接する単位要素のうち１個以上３個以下の単位要素と接続する接続要素が設けられることを特徴とする、請求項３２に記載の高位合成方法。
【請求項３７】
前記軟リソースであるハードウェアリソースには、中心となる単位要素と他の単位要素間とをそれぞれ接続する接続要素が設けられることを特徴とする、請求項３２に記載の高位合成方法。
【請求項３８】
前記軟リソースであるハードウェアリソースには、当該ハードウェアリソースのアーキテクチャに応じた形態の接続要素が設けられることを特徴とする、請求項３２に記載の高位合成方法。
【請求項３９】
前記フローグラフ生成工程は、前記機能記述に含まれる演算とデータの流れを表すデータフローグラフと、前記機能記述に含まれる演算の実行制御を表す制御フローグラフとを含む制御／データフローグラフを生成することを特徴とする、請求項１に記載の高位合成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路の高位合成方法に関し、より特定的には、レイアウトを考慮して高位レベルの合成を行う半導体集積回路の高位合成方法に関する。
【背景技術】
【０００２】
社会の高度情報化とそれを支える情報技術の進展に伴い、電子機器における情報処理機能は飛躍的に増大している。これらの電子機器では、大規模集積回路が、情報処理機能を実現する中心的な役割を果たしている。そこで、より複雑、低電力かつ高性能な大規模集積回路を低コストで製造するためのプロセス技術として、微細化技術の研究開発が進められている。一方、大規模集積回路をより少ない作業で短期間に設計するための設計技術として、より抽象性を高めた高位設計からソフトウェア支援による論理回路合成技術、物理回路合成技術、既存回路の設計流用技術などの研究開発が進められている。
【０００３】
しかし、非特許文献１にも記載されているように、近年のプロセス技術がナノスケールにまで及び、低電圧化が進んだために、従来のプロセス技術を用いた回路設計では十分な精度で見積もれた、あるいは無視できた物理効果が問題となってきている。例えば、微細化が進行した近年の半導体集積回路では、配線間に寄生する電荷容量、配線抵抗、電子回路間の信号の干渉（クロストーク、ノイズなど）、電圧降下問題などの影響が、顕著に現れている。また、上記要因によってどの程度の影響が現れるかは、不確実な状況にある。このため、回路設計の最終工程であるレイアウト設計や物理設計を確実に完了することが困難になっている。
【０００４】
このように大規模集積回路を効率よく設計するために、より抽象度の高い設計技術が求められている一方で、上記の背景により、回路設計を確実に完了することが困難になるという問題が深刻化している。
【０００５】
この問題を解決する１つの方法として、高位設計から物理設計までの工程を何度も繰り返して行う方法が考えられる。しかし、これらの２つの設計工程には膨大な時間がかかるので、この方法は現実的ではない。そこで、近年、必要最小限の物理特性を見積もるために、高位設計工程において、簡単な仮のレイアウト処理を行う方法が考案されている。
【０００６】
例えば、非特許文献２および３では、図４４に示すような、簡易的にレイアウト結果を推定する高位設計方法が提案されている。図４４に示す高位設計方法では、設計対象となる半導体集積回路の動作仕様を記述した動作記述データに対して、ＣＤＦＧ生成工程、初期アロケーションスケジューリング工程、リソース配置工程、および、リソース共有化工程が実行される。
【０００７】
まず、ＣＤＦＧ生成工程（ステップＳ１１）では、入力された動作記述データに基づき、ＣＤＦＧ（Control Data Flow Graph ：制御／データフローグラフ、後述する図２を参照）と呼ばれるグラフが生成される。ＣＤＦＧは、演算とデータの流れを表すＤＦＧ（Data Flow Graph ）と演算の実行制御を表すＣＦＧ（Control Flow Graph：制御フローグラフ）とを含んでいる。
【０００８】
次に、初期アロケーションスケジューリング工程（ステップＳ１２）では、ＣＤＦＧ生成工程で生成されたＣＤＦＧに基づき、ＣＤＦＧに含まれる処理ノードをどのクロック周期に割り当てるかを示すアロケーションスケジュール（後述する図３を参照）と、割付リソース接続グラフ（後述する図４を参照）とが生成される。割付リソース接続グラフは、ＣＤＦＧの処理ノードに割り付けられたハードウェアリソース（以下、割付リソースという）をノードとし、ＣＤＦＧの各信号の流れを枝としたグラフである。なお、ＣＤＦＧ生成工程および初期アロケーションスケジューリング工程については、本発明の第１の実施形態でその詳細を説明する。
【０００９】
次に、リソース配置工程（ステップＳ１３）では、初期アロケーションスケジューリング工程で生成された割付リソース接続グラフに基づき、ノードである割付リソースを配置要素とし、割付リソース接続グラフの枝を配置要素間の接続要素として、仮に設けたレイアウト領域内での各割付リソースの概略配置が求められる。ただし、リソース配置工程では、一般的な物理設計工程で用いられる、確定した形状を有する配置要素を配置する厳密な手法（例えば、スタンダードセルの配置手法）に代えて、簡易的な配置手法が用いられる。具体的には、各割付リソースを大きさを持たない点で表したときの相対的な位置関係が求められ、その後に、仮に設けたレイアウト領域内での各割付リソースの配置位置が決定される。
【００１０】
最後に、リソース共有化工程（ステップＳ１４）では、割付リソース数を削減するために、レイアウト結果において近接して配置された同機能の割付リソースが複数個ある場合に、これらの割付リソースが処理タイミングを考慮して共有化される。このように割付リソースを共有化できる理由は、同機能の割付リソースが複数個あり、それらが互いに異なるクロック周期で動作する場合には、そのうち、いずれか１個の割付リソースを各クロック周期で動作させれば、他の割付リソースを不要とすることができるからである。
【００１１】
共有化によって割付リソース数が減少すれば、回路面積を削減できる。このように、レイアウトした場合の位置関係を考慮して割付リソースを共有化することにより、レイアウト設計後に無理なく割付リソースを共有化でき、結果として物理設計を精度よく見積もった高位設計を行うことができる。
【非特許文献１】ラビ・レブ（Lavi Lev）、他１名、イーイーデザイン（Eedesign）、“ライト・オン・タイム−先端カスタムデザインに対する要求（Right on time -requirements for advanced custom design）”、［平成１６年６月１日検索］、インターネット＜ＵＲＬ：http://www.eedesign.com/story/OEG20030822S0027＞、２００３年８月２２日
【非特許文献２】ウィリアム・Ｅ・ドーハティー（William E. Dougherty）、他１名、“動作合成と物理合成の一体化（Unifying Behavioral Synthesis and Physical Design ）”、第３７回デザインオートメーションカンファレンス（Design Automation Conference）予稿集、２０００年
【非特許文献３】ジュンヒュン・ウン（Junhyung Um ）、他２名、“高位レベル合成におけるレイアウトに基づくリソース共有（Layout-Driven Resource Sharing in High-Level Synthesis）”、コンピュータエイディドデザインに関する国際会議（International Conference on Computer Aided Design ）予稿集、２００２年
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、上記従来の共有化方法には、次のような課題がある。すなわち、従来の共有化方法では、割付リソース接続グラフを用いて割付リソースの仮配置が行われ、複数の同機能の割付リソースがレイアウト結果において偶然に近接して配置された場合に、それらの割付リソースが共有化される。ところが、この方法では、初期アロケーションスケジューリング工程で求めたアロケーションスケジュールが全く考慮されていない。このため、近接して配置された同機能の割付リソースを共有化したときに、アロケーションスケジュールが変化し、与えられた設計仕様を満足できなくなる場合がある。
【００１３】
上記課題を解決する１つの方法として、予め設計仕様より厳しいタイミング条件で（すなわち、より高速な動作条件で）、初期アロケーションスケジューリング工程を行うことが考えられる。しかし、不必要な高性能化を行うと、余分なハードウェアリソースが必要となるために、回路面積や消費電力が増大し、最適な回路を得られなくなる。
【００１４】
それ故に、本発明は、アロケーションスケジューリング工程で求めた、処理に必要なクロック周期数を増加させることなく、割付リソースの共有化を効果的に行うレイアウトベース高位合成方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明の高位合成方法は、レイアウトを考慮した半導体集積回路の高位合成方法であって、設計対象回路の機能記述に含まれる演算を節点に、機能記述に含まれるデータの流れを枝に対応づけたフローグラフを生成するフローグラフ生成工程と、フローグラフの各節点に使用可能なハードウェアリソースを割り付け、フローグラフの枝で表現された順序付けを考慮して、フローグラフの各節点をクロック周期に相当する状態に割り当てた結果から、フローグラフで表現される処理の実行に要する総状態数を求めるとともに、フローグラフの、ハードウェアリソース割付後の節点に対応した節点と、フローグラフの枝に対応した信号枝とを有する割付リソース接続グラフを生成する初期アロケーションスケジューリング工程と、割付リソース接続グラフに含まれる、共有化可能なハードウェアリソースが割り付けられた節点の組について、当該節点間に、節点の共有化を制御するための共有化枝を付加する共有化枝生成工程と、共有化枝付加後の割付リソース接続グラフを仮にレイアウトするリソース配置工程と、リソース配置工程で求めたレイアウト結果に基づき、割付リソース接続グラフの節点を共有化するリソース共有化工程とを備える。
【００１６】
共有化枝生成工程は、状態割り当て結果において異なる状態に割り当てられた節点がある場合には、割付リソース接続グラフの対応する節点間に共有化を促進する引力共有化枝を付加し、状態割り当て結果において同じ状態に割り当てられた節点がある場合には、割付リソース接続グラフの対応する節点間に共有化を抑制する斥力共有化枝を付加し、リソース配置工程は、引力共有化枝によって接続された節点同士を近接して、斥力共有化枝によって接続された節点同士を離間して配置してもよい。より好ましくは、共有化枝生成工程は、割付リソース接続グラフの枝に対して重み付けを行い、リソース配置工程は、共有化枝生成工程で付された重みに基づき、レイアウト結果を求めてもよい。
【００１７】
この場合、共有化枝生成工程は、総状態数が初期アロケーションスケジューリング工程で求めた値を超えない範囲内でフローグラフの各節点を状態に割り当て直した際に、異なる状態に割り当てられる可能性が高い節点間ほど、割付リソース接続グラフの対応する節点間に付加される引力共有化枝の重みを、より共有化を促進する値に設定し、異なる状態に割り当てられる可能性が低い節点間ほど、割付リソース接続グラフの対応する節点間に付加される斥力共有化枝の重みを、より共有化を抑制する値に設定してもよい。あるいは、共有化枝生成工程は、状態割り当て結果において同じ状態に割り当てられた節点が、当該状態内にある１本以上の信号枝を介して接続されている場合には、割付リソース接続グラフの対応する節点間に付加された斥力共有化枝の重みを無効な値に設定してもよい。
【００１８】
また、共有化枝生成工程は、状態割り当て結果において異なる状態に割り当てられた節点がある場合には、割付リソース接続グラフの対応する節点間に共有化を促進する重み付けされた引力共有化枝を付加し、リソース配置工程は、共有化枝生成工程で付された重みに基づき、引力共有化枝によって接続された節点同士を近接して配置してもよい。
【００１９】
また、リソース配置工程は、総状態数が初期アロケーションスケジューリング工程で求めた値を超えない範囲内でフローグラフの各節点を状態に割り当て直し、共有化枝付加後の割付リソース接続グラフを仮にレイアウトするスケジューリング付きリソース配置工程であってもよい。より好ましくは、高位合成方法は、リソース共有化工程で処理された割付リソース接続グラフに対して、共有化枝を付加し直す共有化枝再生成工程をさらに備え、所定の条件を満たすまで、スケジューリング付きリソース配置工程とリソース共有化工程と共有化枝再生成工程とを繰り返し実行してもよい。
【００２０】
また、リソース共有化工程は、割付リソース接続グラフから共有化すべき節点の組を選択する共有化対象選択工程と、共有化対象選択工程で選択された節点を共有化する被選択リソース共有化工程と、被選択リソース共有化工程で処理された割付リソース接続グラフに対して、共有化枝を付加し直す共有化枝再生成工程と、共有化枝再生成工程で処理された割付リソース接続グラフに基づき、リソース配置工程で得られたレイアウト結果を修正するレイアウト結果修正工程とを含み、所定の条件を満たすまで、共有化対象選択工程と被選択リソース共有化工程と共有化枝再生成工程とレイアウト結果修正工程とを繰り返し実行する、逐次改良型リソース共有化工程であってもよい。
【００２１】
また、リソース共有化工程は、割付リソース接続グラフに含まれる、共有化可能なハードウェアリソースが割り付けられた節点の組について優先度を求め、予め定めた範囲内で、求めた優先度が高い順に、節点を共有化してもよい。この場合、リソース共有化工程における優先度は、リソース配置工程で求めたレイアウト結果における節点間の距離に反比例してもよい。あるいは、共有化枝生成工程は、割付リソース接続グラフの枝に対して重み付けを行い、リソース共有化工程における優先度は、節点間に付加された枝に付された重みを、リソース配置工程で求めたレイアウト結果における節点間の距離で割った値に比例してもよく、あるいは、節点間に付加された枝に付された重みに比例する項と、リソース配置工程で求めたレイアウト結果における節点間の距離に反比例する項とを有する計算式を用いて計算されてもよい。
【００２２】
また、重み付けされた引力共有化枝と斥力共有化枝を用いる場合には、高位合成方法は、共有化枝付加後の割付リソース接続グラフについて、レイアウトの困難度を評価するレイアウト困難度評価工程と、レイアウト困難度評価工程においてレイアウト困難と判断された場合に、共有化枝付加後の割付リソース接続グラフから、共有化効率の低い引力共有化枝を選択する引力共有化枝選択工程と、引力共有化枝選択工程で選択された引力共有化枝の重みを削減する引力共有化枝重み削減工程とをさらに備えていてもよい。また、重み付けされた引力共有化枝を用いる場合には、高位合成方法は、引力共有化枝重み削減工程に代えて、引力共有化枝選択工程で選択された引力共有化枝を削除する引力共有化枝削除工程とを備えていてもよい。
【００２３】
これらの場合、レイアウト困難度評価工程は、共有化枝付加後の割付リソース接続グラフの信号枝および引力共有化枝に付された重みの総和や、信号枝に付された重みの総和と引力共有化枝に付された重みの総和との差や、信号枝および引力共有化枝に付された重みの総和に対する引力共有化枝に付された重みの総和の割合に基づき、レイアウトの困難度を評価してもよい。あるいは、レイアウト困難度評価工程は、共有化枝付加後の割付リソース接続グラフに基づき、所定値以下の重みを有する引力共有化枝に対してダミーのハードウェアリソースを割り付けた節点を追加することにより、評価用割付リソース接続グラフを生成し、評価用割付リソース接続グラフに含まれるすべての節点のそれぞれと１本の信号枝によって接続された１次隣接節点の総数と、評価用割付リソース接続グラフに含まれるすべての節点のそれぞれと２本以内の信号枝を介して接続された２次以内隣接節点の総数とを求め、求めた２つの総数の対数値の差に基づきレイアウトの困難度を評価してもよい。
【００２４】
また、引力共有化枝選択工程は、両端に接続された節点に割り付けられたハードウェアリソースのビット幅の差が大きい引力共有化枝や、両端に接続された節点に割り付けられたハードウェアリソースにおける遅延時間の差が大きい共有化枝や、両端に接続された節点に割り付けられたハードウェアリソースの面積のうち小さい方の値が小さい引力共有化枝や、より共有化を抑制する重みが付された引力共有化枝や、両端に接続された節点に割り付けられたハードウェアリソースの出力値のライフタイムが重なる確率が大きい引力共有化枝などを、共有化効率の低い引力共有化枝として選択してもよい。
【００２５】
また、リソース配置工程は、共有化可能なハードウェアリソースが割り付けられた節点を同じ位置に配置できるレイアウトモデルに従い、共有化枝付加後の割付リソース接続グラフを仮にレイアウトしてもよい。この場合、リソース配置工程におけるレイアウトモデルでは、同じ位置に配置できる節点の個数が予め制限されていてもよい。あるいは、リソース配置工程は、配置済みの節点と同じ位置に新たな節点を配置したときに、当該節点に割り付けられたハードウェアリソースの入力側に設けられる選択回路の遅延時間を推定した上で、選択回路の遅延時間を含んだ、当該節点が割り当てられた状態の処理時間を推定し、推定された処理時間がクロック周期に近い場合には、新たに配置された節点を他の位置に移動し、以降の処理では配置済みの節点と同じ位置に節点を配置することを禁止してもよい。あるいは、リソース配置工程は、共有化枝付加後の割付リソース接続グラフを仮にレイアウトする際に、同じ位置に配置される節点の個数が所定値を超えた場合に評価値が悪化する評価関数を用いてもよい。
【００２６】
また、リソース配置工程は、共有化枝付加後の割付リソース接続グラフの節点を、当該節点に割り付けられたハードウェアリソースに応じて、複数の単位要素と単位要素間を接続する接続要素とに変換し、変換後の割付リソース接続グラフを仮にレイアウトしてもよい。より好ましくは、リソース配置工程は、共有化枝付加後の割付リソース接続グラフの節点に割り付けられたハードウェアリソースが固定の形状を有する剛リソースである場合には、高い密度で接続要素を設け、ハードウェアリソースが可変の形状を有する軟リソースである場合には、低い密度で接続要素を設けてもよい。この場合、剛リソースであるハードウェアリソースには、大きな重みを付した接続要素を設け、軟リソースであるハードウェアリソースには、小さな重みを付した接続要素を設けた上で、これらの重みに基づき、変換後の割付リソース接続グラフを仮にレイアウトしてもよい。あるいは、剛リソースであるハードウェアリソースには、上下左右４方向に隣接するすべての単位要素間を接続する接続要素が設けられてもよく、軟リソースであるハードウェアリソースには、１本の接続ですべての単位要素を接続する接続要素や、単位要素間を、上下左右４方向に隣接する単位要素のうち１個以上３個以下の単位要素と接続する接続要素や、中心となる単位要素と他の単位要素間とをそれぞれ接続する接続要素や、当該ハードウェアリソースのアーキテクチャに応じた形態の接続要素などが設けられてもよい。
【００２７】
また、フローグラフ生成工程は、機能記述に含まれる演算とデータの流れを表すデータフローグラフと、機能記述に含まれる演算の実行制御を表す制御フローグラフとを含む制御／データフローグラフを生成してもよい。
【発明の効果】
【００２８】
本発明の高位合成方法では、共有化可能な節点間に節点の共有化を制御するための共有化枝を付加する処理と、共有化枝付加後の割付リソース接続グラフを仮にレイアウトする処理と、レイアウト結果に基づき節点の共有化を行う処理とが実行される。このように共有化枝を用いることにより、共有化可能な節点をレイアウト結果において近接して配置し、近接して配置された割付リソースを共有化することができる。したがって、処理に必要なクロック周期数が最初に求めた値を超えることなく、節点の共有化を効果的に行えるので、回路規模の小さい回路を得ることができる。
【発明を実施するための最良の形態】
【００２９】
（第１の実施形態）
図１は、本発明の第１の実施形態に係るレイアウトベース高位合成方法を示すフローチャートである。図１に示す高位設計方法では、設計対象の半導体集積回路（以下、設計対象回路という）の動作仕様を記述した動作記述データに対して、ＣＤＦＧ生成工程、初期アロケーションスケジューリング工程、共有化枝生成工程、スケジューリング付きリソース配置工程、および、リソース共有化工程が実行される。このうち、ＣＤＦＧ生成工程および初期アロケーションスケジューリング工程は、従来の高位合成方法（図４４）に含まれる工程と同じである。
【００３０】
ＣＤＦＧ生成工程（ステップＳ１０１）では、入力された動作記述データに基づき、ＣＦＧ（Control Flow Graph）とＤＦＧ（Data Flow Graph ）とを含むＣＤＦＧ（Control Data Flow Graph ）が生成される。より詳細には、動作記述データは、例えば、プログラミング言語ＣやＣ＋＋などを用いて記述される。ＣＤＦＧ生成工程では、動作記述データに含まれる各信号（データ信号と制御信号）の流れが解析され、演算とデータの流れを表すＤＦＧと、演算の実行制御を表すＣＦＧとが生成される。このようにして生成されたＤＦＧとＣＦＧとを合わせて、ＣＤＦＧと呼ぶ。ＣＤＦＧの各ノード（以下、処理ノードという）は、１個の演算器で実行可能な演算の内容を表す。また、ＣＦＤＧでは、信号値を一時的に記憶する変数も、処理ノードを用いて表される。
【００３１】
初期アロケーションスケジューリング工程（ステップＳ１０２）では、ＣＤＦＧ生成工程で生成されたＣＤＦＧに基づき、アロケーションスケジュールと割付リソース接続グラフとが生成される。より詳細には、初期アロケーションスケジューリング工程に先立ち、設計対象回路で使用できる演算器（例えば、加算器、乗算器など。以下、ハードウェアリソースという）の特性（例えば、機能や遅延時間など）を含んだハードウェアリソースライブラリが用意される。初期アロケーションスケジューリング工程では、まず、ＣＤＦＧの各処理ノードに対して、ハードウェアリソースライブラリから、各処理ノードで実行される演算を実行でき、かつ、動作周波数等の設計仕様を満たすハードウェアリソースが選択され、各処理ノードに割り付けられる。この各処理ノードに割り付けられたハードウェアリソースを、割付リソースという。
【００３２】
次に、各処理ノードで実行される演算がクロック同期で行われるように、ハードウェアリソース割付後のＣＤＦＧの各処理ノードがクロック周期に相当する状態（以下、ステートという）に割り当てられる。このように処理ノードをステートに割り当てることをスケジューリング、処理ノードに割り当てられたステートを割当ステート、処理ノードがステートに割り当てられた結果をアロケーションスケジュールという。初期アロケーションスケジューリング工程で決定されたアロケーションスケジュール（以下、初期アロケーションスケジュールという）では、各処理ノードの割当ステートが仮に決定されている。
【００３３】
初期アロケーションスケジューリング工程では、初期アロケーションスケジュールから、ＣＤＦＧで表現される処理の実行に要する総ステート数（以下、総実行ステート数という）が求められる。また、ＣＤＦＧの処理ノードに対応した各割付リソースをノードとし、ＣＤＦＧの各枝を枝とした、割付リソース接続グラフが生成される。
【００３４】
共有化枝生成工程（ステップＳ１０３）では、初期アロケーションスケジューリング工程で生成された割付リソース接続グラフに対して、共有化可能な割付リソースの間に、新たな枝（以下、共有化枝という）が付加される。共有化可能な割付リソースとは、同じ演算を実行できる（すなわち、同機能の）割付リソースをいう。例えば、割付リソース接続グラフに、全く同じハードウェアリソースが割り付けられたノードが含まれていれば、これらの割付リソースは共有化可能である。この場合、ハードウェアリソースのビット幅が異なっていても、これらの割付リソースを共有化可能であるとしてもよく、あるいは、ビット幅がある程度異なっていれば、これらの割付リソースを共有化不可能であるとしてもよい。
【００３５】
次に、スケジューリング付きリソース配置工程（ステップＳ１０４）では、初期アロケーションスケジュールを初期解として、各処理ノードの割当ステートが決定されるとともに、共有化枝生成工程で共有化枝を付加された割付リソース接続グラフに含まれる各割付リソースの概略配置が決定される。
【００３６】
最後に、リソース共有化工程（ステップＳ１０５）では、スケジューリング付きリソース配置工程で決定された割付リソースの配置位置に応じて、共有化可能な割付リソースの共有化が行われる。ここでは、レイアウト結果において近接して配置されたと判断された割付リソースが共有化される。これにより、最終的なハードウェアリソースの個数と、各ハードウェアリソースの概略配置とが決定される。
【００３７】
従来の高位合成方法（図４４）では、初期アロケーションスケジューリング工程で生成された、共有化枝が付加されていない割付リソース接続グラフに対して、リソース配置工程とリソース共有化工程とが実行される。このように、従来の高位合成方法では、割付リソースが共有化可能か否かを考慮することなく、割付リソースの仮配置が行われ、得られたレイアウト結果において偶然に近接して配置された割付リソースが共有化される。
【００３８】
これに対して、本実施形態に係る高位合成方法（図１）では、共有化枝生成工程で共有化枝を付加した割付リソース接続グラフに対して、スケジューリング付きリソース配置工程とリソース共有化工程とが実行される。このように、本実施形態に係る高位合成方法では、割付リソースが共有化可能か否かを考慮して、割付リソースの仮配置が行われる。したがって、割付リソースを仮配置する段階で、共有化可能な割付リソースを近接して配置することにより、後に割付リソースを共有化したときに、クロックタイミングエラーの発生などを防止することができる。
【００３９】
以下、例として、次式（１ａ）および（１ｂ）に示す計算式が動作記述データとして入力された場合に、本実施形態に係る高位合成方法において、どのような処理が行われるかを説明する。以下では、次式（１ａ）および（１ｂ）を動作記述ＢＤという。
ｙ＝ｆ＋ｇ                                              …（１ａ）
ｘ＝（（ａ＋（ｂ＋ｃ）＋（ｄ＋ｅ））×ｙ）＋（ｈ＋ｉ）  …（１ｂ）
【００４０】
まず、ＣＤＦＧ生成工程（ステップＳ１０１）では、入力された動作記述ＢＤに対して、字句解析、構文解析および意味解析が順に実行され、図２に示すように、変数および演算をノードとし、データの流れを枝としたＣＦＧおよびＤＦＧを含むＣＤＦＧが生成される。なお、図２では、ＣＦＧの内容は、省略されている。一般に、設計対象回路の動作記述データは、ＣＦＧおよびＤＦＧを含むＣＤＦＧに変換することができる。
【００４１】
次に、初期アロケーションスケジューリング工程（ステップＳ１０２）では、設計対象回路で使用できるハードウェアリソースについて機能や遅延時間などの特性を記述したハードウェアリソースライブラリと、設計対象回路の設計制約条件（例えば、動作周波数など）を記述した設計制約ファイルとを参照して、以下の処理が行われる。
【００４２】
まず、第１段階の処理として、ＣＤＦＧの各処理ノードに対して別々のハードウェアリソースが仮に割り付けられ、ハードウェアリソース割付後の各処理ノードをステートに割り当てた結果（初期アロケーションスケジュール）が求められる。この初期アロケーションスケジュールでは、各処理ノードの実行順序が仮に決定されている。初期アロケーションスケジュールを参照して、入力された動作記述データで表現される処理の実行に要する総実行ステート数が決定される。
【００４３】
図３は、図２に示すＣＤＦＧについての初期アロケーションスケジュールを示す図である。図３では、入力ａ〜ｉがステートＳ０に、ハードウェアリソース割付後の８個の処理ノードがステートＳ０〜Ｓ４に、出力ｘおよびｙがステートＳ４およびＳ１に、それぞれ割り当てられている。この初期アロケーションスケジュールでは、総実行ステート数は５である。なお、図３では、同じ演算を実行する処理ノードには、１、２、３などの番号が添え字として付されている。以下、アロケーションスケジュールにおいて、ラベルＬが付された処理ノードをＮL と表す。
【００４４】
次に、第２段階の処理として、ハードウェアリソース割付後のＣＤＦＧに対応した割付リソース接続グラフが生成される。この割付リソース接続グラフは、ＣＤＦＧの、ハードウェアリソース割付後の各処理ノードに対応したノードと、ＣＤＦＧの各枝に対応した枝とを有する。
【００４５】
図４は、図３に示すハードウェアリソース割付後のＣＤＦＧに対応した割付リソース接続グラフＲＧ１を示す図である。図４にノードとして示す割付リソースＲ+1〜Ｒ+7、Ｒ×は、それぞれ、図３に示す処理ノードＮ+1〜Ｎ+7、Ｎ×に対応している。ただし、割付リソース接続グラフＲＧ１では、変数を記憶する処理ノードは、信号を伝播する信号枝に変換され、プライマリ入出力変数から変換された信号枝は、割付リソースの入出力端子に接続される。動作記述ＢＤでは、すべての変数がプライマリ入出力であるので、これらの変数から変換された信号枝は、すべて、割付リソースの入出力端子に接続される。
【００４６】
初期アロケーションスケジューリング工程が完了した段階では、動作記述データによって表現された処理の実行に要するステート数（総実行ステート数）は決定されているが、ハードウェアリソース割付後のＣＤＦＧの各処理ノードは、ステートに仮に割り当てられているだけである。各処理ノードの割当ステートは、最終的には、後に実行されるスケジューリング付きリソース配置工程で決定される。
【００４７】
共有化枝生成工程（ステップＳ１０３）では、初期アロケーションスケジュールを参照して、割付リソース接続グラフに対して、割付リソースの共有化を制御するための共有化枝をノード間に追加する処理が行われる。本実施形態では、１本の信号枝を介して直接接続されていないすべての共有化可能なノード間に共有化枝が追加され、追加された各共有化枝に以下に示す特性が与えられる。
【００４８】
ＣＤＦＧに２本のクリティカルパスが含まれており、各クリティカルパス上で同じステート内に、同機能のハードウェアリソースが割り付けられた２個の処理ノードが存在する場合には、これらの処理ノードに対応した、割付リソース接続グラフのノード間には、「近接して配置しない」ための特性を有する共有化枝が追加される。これにより、後に割付リソースの仮配置を行うときに、これら２個の割付リソースは離間して配置されるので、その後に割付リソースの共有化を行うときに、「近接して配置された同機能の割付リソース」として共有化されることを防止できる。
【００４９】
逆に、ＣＤＦＧに２本のクリティカルパスが含まれており、各クリティカルパス上で異なるステート内に、同機能のハードウェアリソースが割り付けられた２個の処理ノードが存在する場合には、これらの処理ノードに対応した、割付リソース接続グラフのノード間には、「近接して配置する」ための特性を有する共有化枝が追加される。これにより、後に割付リソースの仮配置を行うときに、これら２個の割付リソースは近接して配置されるので、その後に割付リソースの共有化を行うときに、「近接して配置された同機能の割付リソース」として共有化される。
【００５０】
また、上記以外の場合において同機能の２個の処理ノードが存在する場合には、これらの処理ノードに対応した、割付リソース接続グラフのノード間には、「近接して配置することを許す」ための特性を有する共有化枝が追加される。このように共有化枝の特性を設定することにより、レイアウト結果において割付リソースを近接して配置するか、離間して配置するかを制御し、割付リソースが共有化されるか否かを制御することができる。
【００５１】
図５は、図３に示す初期アロケーションスケジュールを参照して、図４に示す割付リソース接続グラフＲＧ１に対して付加される共有化枝の種類を示す図である。図６は、図４に示す割付リソース接続グラフＲＧ１に対して、図５に示す種類の共有化枝を追加して得られた割付リソース接続グラフＲＧ１０を示す図である。なお、共有化枝生成工程では、共有化枝は、同機能の２個の割付リソース間に付加されるが、１本の信号枝を介して直接接続された割付リソース間には付加されない。
【００５２】
スケジューリング付きリソース配置工程（ステップＳ１０４）では、図３に示す初期アロケーションスケジュールと、図６に示す割付リソース接続グラフＲＧ１０とに基づき、ＣＤＦＧの各処理ノードの割当ステートと、各割付リソースの概略配置とが決定される。次に、リソース共有化工程（ステップＳ１０５）では、スケジューリング付きリソース配置工程で求めたレイアウト結果において、２個の割付リソース間の距離が所定値以下である場合に、これらの割付リソースが共有化される。
【００５３】
このように共有化枝生成工程において好適な特性を有する共有化枝を生成することにより、割付リソースが共有化されるか否かを制御し、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えないように制御することができる。
【００５４】
なお、リソース共有化工程では、２個の割付リソース間の距離が所定値以下であっても、これらの割付リソースが同じステートに割り当てられた２個の処理ノードに対応したものである場合には、これらの割付リソースを共有化しないこととしてもよい。これにより、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えないように、より確実に制御することができる。
【００５５】
本実施形態に係る高位合成方法の効果を、図３に示す初期アロケーションスケジュールを例として説明する。この初期アロケーションスケジュールでは、入力ｂまたはｃから５個のノードＮ+1、Ｎ+5、Ｎ+6、Ｎ×、Ｎ+7を経て出力ｙに到達する経路と、入力ｄまたはｅから５個のノードＮ+2、Ｎ+5、Ｎ+6、Ｎ×、Ｎ+7を経て出力ｙに到達する経路とが、クリティカルパスとなる。
【００５６】
図３に示す初期アロケーションスケジュールに対して共有化枝を使用しない従来の高位合成方法（図４４）を適用した場合、レイアウト結果において、割付リソースＲ+1（Ｎ+1に対応した割付リソース）とＲ+2（Ｎ+2に対応した割付リソース）とが偶然に近接して配置されることがある。ところが、割付リソースＲ+1とＲ+2を共有化すると、処理ノードＮ+1とＮ+2を同じステートで処理するという、初期アロケーションスケジュール（図３）に矛盾する。このため、初期アロケーションスケジュールを、例えば図７に示すように、処理ノードＮ+1を２つのステートＳ０およびＳ１に割り当てた新たなアロケーションスケジュールに変更する必要が生じる。このように、従来の高位合成方法では、総実行ステート数が、初期アロケーションスケジューリング工程で求めた値を超えることがある。
【００５７】
これに対して、本実施形態に係る高位合成方法では、共有化枝を付加した割付リソース接続グラフが使用される。したがって、例えば、ＣＤＦＧのクリティカルパス以外の経路上に処理ノードＮ+2とＮ+3が存在する場合には、引力となる共有化枝が割付リソースＲ+2とＲ+3（Ｎ+3に対応した割付リソース）の間に付加され、ＣＤＦＧのクリティカルパス上に処理ノードＮ+1とＮ+2が存在する場合には、斥力となる共有化枝が割付リソースＲ+1とＲ+2の間に付加される。これにより、割付リソースＲ+2とＲ+3とを近接して配置する一方で、割付リソースＲ+1とＲ+2とを離間して配置することができる。このように、本実施形態に係る高位合成方法では、割付リソースを共有化した結果を好適に制御することにより、総実行ステート数が、初期アロケーションスケジューリング工程で求めた値を超えないようにすることができる。
【００５８】
以下、本実施形態に係る高位合成方法における共有化枝生成工程（ステップＳ１０３）およびスケジューリング付きリソース配置工程（ステップＳ１０４）の詳細を説明する。先に、共有化枝生成工程の詳細を説明する。
【００５９】
共有化枝生成工程で生成される共有化枝は、引力および斥力という２種類の特性を有することに加えて、引力および斥力の強さを表す重みを有してもよい。これにより、割付リソースを共有化した結果をより高い精度で制御することができる。例えば、割付リソースの共有化を強く促進するためには、これらの割付リソースの間に付加された共有化枝に大きな重みを設定し、割付リソースの共有化を弱く促進するためには、これらの割付リソースの間に付加された共有化枝に小さな重みを設定すればよい。
【００６０】
共有化枝生成工程における各共有化枝に対する重みの設定は、人手の作業で行ってもよいが、以下に示すように、一定の処理手順に従って自動的に行ってもよい。以下、共有化枝に設定される重みを自動的に計算する方法の一例として、初期アロケーションスケジュールに基づき、各処理ノードについて、総実行ステート数が最初に求めた値を超えない範囲内でステートを変更できる範囲（以下、スケジュール変更可能範囲という）を求め、その結果に基づき共有化枝の重みを計算する方法を説明する。
【００６１】
図８は、重み付き共有化枝を付加する場合の共有化枝生成工程の詳細を示すフローチャートである。図８に示す共有化枝生成工程では、初期アロケーションスケジュールを参照して、スケジュール変更可能範囲計算工程、重み計算工程、および、重み付き共有化枝生成工程が実行される。
【００６２】
スケジュール変更可能範囲計算工程（ステップＳ１１１）では、初期アロケーションスケジュールに含まれる各処理ノードについて、スケジュール変更可能範囲が計算される。次に、重み計算工程（ステップＳ１１２）では、計算されたスケジュール変更可能範囲に基づき、割付リソース接続グラフの各ノード間に付加される共有化枝に付される重みが計算される。次に、重み付き共有化枝生成工程（ステップＳ１１３）では、計算された重みを有する共有化枝が生成され、割付リソース接続グラフの各ノード間に付加される。
【００６３】
以下、例として、図３に示す初期アロケーションスケジュールを参照して、図４に示す割付リソース接続グラフＲＧ１に付加される共有化枝の重みを計算する場合について説明する。スケジュール変更可能範囲計算工程（ステップＳ１１１）では、総実行ステート数が最初に求めた値を超えない範囲内で、各処理ノードについて、当該処理ノードを最も早いステートに割り当てたときの割当ステートと、当該処理ノードを最も遅いステートに割り当てたときの割当ステートとが求められ、前者の割当ステートから後者の割当ステートまでの範囲が、当該処理ノードについてのスケジュール変更可能範囲とされる。なお、スケジュール変更可能範囲を求める方法の詳細は、例えば、ピエール・Ｇ・パウリン（Pierre G. Paulin）、他１名、“ＡＳＩＣの機能合成のためのフォースダイレクティッドスケジューリング（Force-Directed Scheduling for the Behavioral Synthesis of ASIC's）”、ＩＥＥＥトランザクションズ・オン・コンピュータエイディッドデザイン（IEEE Transactions on Computer-Aided Design）、第８巻、第６号、１９８９年６月などに記載されている。
【００６４】
図９は、図３に示す初期アロケーションスケジュールについて求めたスケジュール変更可能範囲を示す図である。図９に示すように、処理ノードＮ+3は、３個のステート（ステートＳ０〜Ｓ２）を含むスケジュール変更可能範囲を有し、処理ノードＮ+4は、４個のステート（ステートＳ０〜Ｓ３）を含むスケジュール変更可能範囲を有する。それ以外の処理ノードは、いずれも、ＣＤＦＧのクリティカルパス上にあり、１個のステートを含むスケジュール変更可能範囲を有する。
【００６５】
共有化枝重み計算工程（ステップＳ１１２）では、各処理ノードのスケジュール変更可能範囲に基づき、同機能の割付リソース間に付加される引力共有化枝の重みが計算される。例えば、引力共有化枝の重みＷａijは、次式（２）を用いて計算される。
【数１】
2006011878.tif 000003
ただし、式（２）において、δlmはクロネッカーデルタを表す。また、ｉ番目およびｊ番目の処理ノードのスケジュール変更可能範囲をＳＲi 、ＳＲj としたとき、Ｓi 、Ｓj はＳＲi 、ＳＲj の開始ステートを、Ｅi 、Ｅj はＳＲi 、ＳＲj の終了ステートを、Ｍi 、Ｍj はＳＲi 、ＳＲj に含まれるステートの個数を、変数ｌ、ｍはＳＲi 、ＳＲj 内の値を表す。ｉ番目およびｊ番目の処理ノードが共有化可能で、同じステートに割り当てられた場合（すなわち、ｌ＝ｍの場合）、δlm＝１となる。したがって、同じステートに割り当てられる可能性が低い処理ノード間ほど、式（２）による値Ｗａijは大きくなる。
【００６６】
図１０は、図９に示すスケジュール変更可能範囲に基づき、式（２）を用いて、引力共有化枝に付される重みＷａijを計算した結果を示す図である。なお、ノード間に付加される共有化枝が斥力共有化枝である場合には、斥力共有化枝に付される重みＷｒijは、引力共有化枝である場合に付される重みから１を引くことにより、すなわち、次式（３）を用いて算出される。
Ｗｒij＝Ｗａij−１  …（３）
【００６７】
図１１〜図１４を参照して、式（２）を用いて共有化枝の重みを計算する方法の有効性を説明する。図１１は、互いに共有化可能な３つの処理ノードＦａ〜Ｆｃのスケジュール変更可能範囲を示す図である。この例について、式（２）を用いて処理ノードＦａ−Ｆｂ間に付加される共有化枝の重みを計算すると、３／４となる。処理ノードＦａ−Ｆｃ間に付加される共有化枝の重みは３／４で、処理ノードＦｂ−Ｆｃ間に付加される共有化枝の重みは１／２となる。また、処理ノードＦａ〜Ｆｃを共有化しないとした場合、３個の処理ノードをステートに割り当てる方法は、全部で８（２の３乗）通りある。
【００６８】
このうち、処理ノードＦｂとＦｃを共有化できる方法（図１２）は４通りあり、処理ノードＦｂ−Ｆｃ間に付加される共有化枝の重みＷａijは１／２となる。一方、処理ノードＦａとＦｂを共有化できる方法（図１３）と、ＦａとＦｃを共有化できる方法（図１４）は、それぞれ６通りあり、処理ノードＦａ−Ｆｂ間およびＦａ−Ｆｃ間に付加される共有化枝の重みＷａijは３／４となる。このことから、式（２）を用いて計算された重みＷａijは、割付リソースの共有化を行った場合に、総実行ステート数が最初に求めた値を超えない可能性を表すことがわかる。したがって、大きな重みが付された共有化枝によって接続される割付リソースを共有化しても、総実行ステート数が最初に求めた値を超える可能性は低いので、これらの割付リソースは共有化されやすいように近接して配置すればよい。逆に、小さな重みが付された共有化枝によって接続される割付リソースを共有化すると、総処理ステート数が最初に求めた値を超える可能性が高いので、これら割付リソースは積極的に近接した位置に配置する必要はない。
【００６９】
このように、各処理ノードのスケジュール変更可能範囲に基づき、各処理ノード間に付加される共有化枝の重みを計算することにより、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えない範囲内で、割付リソースの共有化を促進する、効果的な共有化枝の重みを求めることができる。
【００７０】
次に、スケジューリング付きリソース配置工程（ステップＳ１０４）の詳細を説明する。上述したように、スケジューリング付きリソース配置工程では、初期アロケーションスケジュールを初期解として、各処理ノードの割当ステートが決定されるとともに、共有化枝生成工程で共有化枝を付加された割付リソース接続グラフに含まれる各割付リソースの概略配置が決定される。
【００７１】
スケジューリング付きリソース配置工程では、共有化枝を付加された割付リソース接続グラフを、あるレイアウトモデルに従って配置したときに、コストが最小となるレイアウト結果が求められる。ここでは、割付リソース接続グラフに含まれる割付リソースが配置要素とされ、割付リソース間に付加された枝（信号枝または共有化枝）の重みや長さに基づきコストが算出される。また、ここでは、共有化可能な割付リソースは、同じ位置にいくつでも配置できるものとする。割付リソース接続グラフを配置したときのコストは、例えば、次式（４）で与えられ、次式（４）によるコストＣＯＳＴが最小となる割付リソースの配置結果が求められる。
【数２】
2006011878.tif 000004
ただし、式（４）において、Ｒn は割付リソースの総数、Ｌijはレイアウト結果におけるｉ番目およびｊ番目の割付リソース間の距離、ＷＭijはｉ番目およびｊ番目の割付リソース間の接続枝の重みを表す。ここで、接続枝の重みＷＭijは、枝の種類（信号枝、引力共有化枝、斥力共有化枝）ごとに定義され、例えば、接続枝が信号枝である場合には１、接続枝が引力共有化枝である場合は式（２）によるＷａij、接続枝が斥力共有化枝である場合には式（３）によるＷｒijに設定される。また、ｉ番目およびｊ番目の割付リソース間に枝が存在しない場合（例えば、異なる機能の割付リソースが信号枝で直接接続されていない場合）には、接続枝の重みＷＭijは０に設定される。
【００７２】
スケジューリング付きリソース配置工程では、式（４）で計算されるコストが最小となる配置を求めるために、各処理ノードの割当ステートが、スケジュール変更可能範囲内で変更される。例えば、図９に示す例では、処理ノードＮ+3は、３つのステートＳ０〜Ｓ２を含むスケジュール変更可能範囲を有し、処理ノードＮ+4は、４つのステートＳ０〜Ｓ３を含むスケジュール変更可能範囲を有している。このように初期アロケーションスケジュールに複数のステートを含むスケジュール変更可能範囲を有する処理ノードが含まれている場合、この処理ノードの割当ステートは所定の頻度で変更され、変更後のアロケーションスケジューリングに基づき配置した場合のコストが算出される。なお、このように処理ノードの割当ステートを変更すると、これまで引力共有化枝が付加されていた割付リソース間に斥力共有化枝が付加される場合や、その逆の場合もありえるが、このような場合には、接続枝の重みＷＭijを変更した後に、式（４）を用いてコストが計算される。
【００７３】
さらに具体的に述べると、スケジューリング付きリソース配置工程では、割付リソースは最初はランダムな位置に配置され、その初期配置について、式（４）を用いてコストが計算される。その後は、Simulated Annealing 法（焼きなまし法）など等の逐次改善手法に従い、割付リソースの配置位置を変更する処理（ＭＯＶＥ処理）と処理ノードの割当ステートを変更する処理（ＲＥＳＣＨ処理）とが繰り返し行われ、これにより、式（４）に示すＣＯＳＴが最小となるレイアウト結果が求められる。なお、Simulated Annealing 法の詳細は、例えば、Ｓ・カークパトリック（S. Kirkpatrik ）、他２名、“シミュレーティッドアニーリングによる最適化（Optimization by Simulated Annealing ）”、サイエンス（Science ）２００、１９８３年、ｐ．６７１−６８０などに記載されている。
【００７４】
このようなスケジューリング付きリソース配置工程を実行することにより、割付リソース接続グラフのレイアウト結果が得られる。このレイアウト結果では、信号枝だけでなく、引力共有化枝も短くなる。これにより、異なるステートに割り当てられた処理ノードに対応した、共有化可能な割付リソース間では共有化が促進される。一方、斥力共有化枝には負の重みが設定されるので、同じステートに割り当てられた処理ノードに対応した、共有化可能な割付リソース間では共有化は抑制される。
【００７５】
なお、以上の説明では、共有化可能な割付リソースは、同じ位置にいくつでも配置できることとしたが、これに代えて、同じ位置に配置できる割付リソースの個数（以下、重複配置可能数という）を設計制約ファイルなどで予め制限しておいてもよい。より詳細には、同じ位置に配置された割付リソースは、後に実行されるリソース共有化工程において共有化される可能性が高い。しかし、割付リソースを共有化し、１個の割付リソースで多くの処理を切り換えて実行すると、割付リソースの入力データを選択する選択回路（マルチプレクサ）の遅延時間が大きくなる。このため、１つのステートに割り当てられたすべての処理をクロック周期内で完了できない現象（以下、クロックタイミングエラーという）が起こる可能性がある。この問題を解決するためには、重複配置可能数に制限を設ければよい。これにより、割付リソースを共有化する際に必要とされる選択回路の遅延時間を考慮して、割付リソースの仮配置を行い、後述するクロックタイミングエラーの発生を防止することができる。
【００７６】
また、以上の説明では、式（４）を用いて、割付リソース接続グラフの配置コストを計算することとしたが、これに代えて、レイアウト領域を矩形状の小領域に分割し、式（５）を用いて、割付リソース接続グラフの配置コストを計算してもよい。
【数３】
2006011878.tif 000005
ただし、式（５）において、Ｘmax およびＹmax はＸ方向およびＹ方向の小領域の個数、ＯvsxyはＸ方向にｘ番目、Ｙ方向にｙ番目の小領域における重複配置可能数、Ｏvxy はＸ方向にｘ番目、Ｙ方向にｙ番目の小領域に実際に配置された割付リソース数、関数Ｈ［ｘ］は、ｘが０未満であるときは０、ｘが０以上であるときは１となるヘビサイドステップ関数、αおよびβは実験などで求めたパラメータである。式（５）の第２項の存在により、式（５）で求めたコストＣＯＳＴ’が最小となるレイアウト結果を求めれば、そのレイアウト結果では、同時に、同じ小領域に配置される割付リソース数が各小領域の重複配置可能数に抑制されている。
【００７７】
このように、同じ位置に配置される節点の個数が所定値を超えた場合に評価値が悪化する評価関数を用いて、レイアウト結果を評価することにより、レイアウト処理を行うだけで、同じ位置に配置する節点の個数を制限することができる。
【００７８】
また、スケジューリング付きリソース配置工程では、選択回路の遅延時間を推定した結果などに基づき、重複配置可能数を動的に変更してもよい。より詳細には、例えば、配置済みの割付リソースと同じ位置に新たな割付リソースを配置したときに、これらの割付リソースを共有化するために必要な選択回路の遅延時間が推定され、当該推定値と割付リソースの遅延時間との和が算出される。この和は、これらの割付リソースが割り当てられたステートの処理時間の推定値となる。この処理時間の推定値が予め定められたクロック周期に一定の基準まで近づいたときに、新たに配置された割付リソースは他の位置に移動される。また、このとき、重複配置可能数は、その時点でその位置に配置されている割付リソースの個数に一致するように変更され、これにより、以降の処理では、新たな割付リソースが同じ位置に重複して配置することが禁止される。
【００７９】
選択回路の遅延時間は、共有化する割付リソースの個数やビット幅などによって決定されるので、共有化される割付リソースが決定された後であれば、高い精度で推定することができる。このように高い精度で遅延時間を推定することにより、クロックタイミングエラーが発生しない最大限の共有化を実行し、クロックタイミングエラーが発生しない最小の回路を得ることができる。
【００８０】
スケジューリング付きリソース配置工程では、現実のレイアウトを反映したレイアウトモデルを採用してもよい。以下、図１５〜図２１を参照して、割付リソースの物理的構造（面積や形状など）を反映したレイアウトモデルの一例を説明する。このレイアウトモデルを用いれば、現実のレイアウト処理により近い処理を行えるので、より規模の小さな回路を得ることができる。
【００８１】
以下に示すレイアウトモデルでは、割付リソースの物理的構造は、所定の２次元形状を有する単位要素と単位要素を接続する接続要素とを用いて表現される。より詳細には、式（５）を用いてコスト計算を行う場合と同様に、レイアウト領域は、矩形状の小領域に分割される。各割付リソースは、この小領域と同じ形状または同じ面積に分割され、その結果として得られた要素が単位要素となる。単位要素は、所定の規定に従って設けられた接続要素によって接続される。
【００８２】
例えば、割付リソースは、図１５に示すように、複数の単位要素に分割される。図１５（ａ）に示す割付リソースＲ+1は、小領域９個分の面積を有し、９個の単位要素に分割される。図１５（ｂ）に示す割付リソースＲ+5は、小領域２５個分の面積を有し、２５個の単位要素に分割される。図１６は、図１５（ｂ）に示す割付リソースＲ+5の２５個の単位要素が接続要素によって接続される様子を示す図である。図１６に示すように、２５個の単位要素は２次元状に配置され、上下左右４方向に隣接する単位要素間に接続要素が設けられる。
【００８３】
割付リソースを単位要素と接続要素とを用いて表現した場合、単位要素の個数は、割付リソースのレイアウト上の面積に対応する。また、接続要素は、割付リソースのレイアウト上の形状を変更できる程度を表す。スケジューリング付きリソース配置工程で割付リソースを配置するときには、上記のように単位要素と接続要素とを用いて表現された割付リソースが、矩形状の小領域に分割されたレイアウト領域に配置される。
【００８４】
割付リソース接続グラフに含まれる割付リソースには、メモリなどのように固定の形状を有するもの（以下、剛リソースという）と、演算器などのように可変の形状を有するもの（以下、軟リソース）とが含まれる。両者の違いは、単位要素間にどのように接続要素を設けるかによって表現される。より詳細には、剛リソースには高い密度で接続要素が設けられ、軟リソースには低い密度で接続要素が設けられる。また、各接続要素に重み付けをした上で、付された重みを考慮して割付リソースをレイアウトする場合には、剛リソースに設けられる接続要素には大きな重みを設定し、軟リソースに設けられる接続要素には小さな重みを設定してもよい。
【００８５】
剛リソースについては、例えば図１６に示すように、上下左右４方向に隣接するすべての単位要素間に、接続要素として接続枝が設けられる。この場合、各接続枝に対して、割付リソース接続グラフに含まれる接続枝（信号枝および共有化枝）に付加された重みよりも十分に大きな重みを設定して、割付リソースの配置を行えば、割付リソースは当初の形状を維持したまま配置される。このように、分割要素間に高い密度で接続要素を設けることにより、たとえ各単位要素の配置位置を個別に最適化した場合でも、配置が完了した時点では、単位要素は、全体として、接続枝の長さの総和が最小となる形状（すなわち、分割前の割付リソースの形状）に配置される。
【００８６】
一方、軟リソースについては、例えば図１７（ａ）に示すように、１本の接続ですべての単位要素を接続する接続要素を設けてもよい。一般に、配置を行ったときに接続長を見積もる方法としては、いわゆるミニマムバウンディングボックス法（１個の接続要素に接続される単位要素がある矩形領域内に配置されたときに、その矩形の半周囲長を最小化する方法）が採用されることが多い。したがって、割付リソースの形状が図１７（ａ）に示すように元は正方形である場合でも、割付リソース接続グラフの接続枝を考慮すると、配置が完了した時点では、単位要素が、全体として、図１７（ｂ）や（ｃ）に示すように長方形状に配置されると予想される。
【００８７】
また、軟リソースについては、例えば図１８（ａ）および（ｂ）に示すように、単位要素間を、上下左右４方向に隣接する単位要素のうち１個以上３個以下の単位要素と接続する接続要素を設けてもよい。図１８（ａ）に示す接続形態は、図１６に示す接続形態から一部の接続枝を削除して、接続要素の密度を下げたものである。この接続形態を用いた場合、図１７（ａ）に示す接続形態よりも、中心となる単位要素から単位要素が離れて配置される可能性が高いので、割付リソースの形状をより柔軟に変形できる。また、図１８（ｂ）に示す接続形態も、図１８（ａ）に示す接続形態と同じ単位要素間の接続距離を有するので、この接続形態を用いた場合も、割付リソースの形状をより柔軟に変形できる。
【００８８】
あるいは、軟リソースについては、例えば図１９（ａ）に示すように、中心となる単位要素と他の単位要素間とをそれぞれ接続する接続要素を設けてもよい。この接続形態を用いた場合、中心に配置される単位要素からのマンハッタン距離が所定値以内に入るように各単位要素が配置されるので、配置が完了した時点では、単位要素は、図１９（ｂ）に示すように、全体としてひし形状に配置される。この場合、各接続枝に対して、割付リソース接続グラフに含まれる接続枝（信号枝および共有化枝）に付加された重みと同等の重みを設定した上で、割付リソースの配置を行えば、割付リソース接続グラフ全体の配置を考慮して、割付リソースの形状が決定される。さらに、図１９（ａ）に示す接続形態は、多くの場合、図１８（ａ）および（ｂ）に示す接続形態よりも、接続枝の本数が少なくなるので、レイアウト時に考慮すべき接続枝の本数を減らし、より短時間でレイアウト処理を行うことができる。
【００８９】
あるいは、形状を変更できるが、演算器アーキテクチャが固定されている割付リソースについては、演算器アーキテクチャに応じた形態の接続要素を設けてもよい。例として、割付リソースがリップルキャリー型加算器である場合の接続形態（図２０（ａ））と、割付リソースがキャリールックアヘッド型加算器である場合の接続形態（図２０（ｂ））とについて説明する。割付リソースがリップルキャリー型加算器であり、レイアウト領域を分割して得られた小領域の面積がｎビット加算器の面積と等しくなる場合、ｎビット加算器が単位要素に対応づけられる。また、キャリー伝搬信号が、単位要素間に設けられる接続要素に対応づけられる。したがって、この場合、割付リソースは、単位要素と接続要素とを用いて、図２０（ａ）に示すように表現される。
【００９０】
これに対して、割付リソースがキャリールックアヘッド型加算器である場合、ｎビット加算器あるいはキャリー生成・伝搬回路が単位要素に対応づけられ、キャリー生成・伝搬信号が単位要素間に設けられる接続要素に対応づけられる。したがって、この場合、割付リソースは、単位要素と接続要素とを用いて、図２０（ｂ）に示すように表現される。このように割付リソースのモデルとして、演算器アーキテクチャに応じた形態の接続要素を設けることにより、割付リソースの面積だけでなく、割付リソース内部の信号線の接続状態を考慮して単位要素を配置し、割付リソースのレイアウトモデルをより正確に表現することができる。なお、ここでは、例として加算器について説明したが、乗算器などのように、複数の演算器アーキテクチャを取り得る他の割付リソースについても、同様の方法を適用できることは言うまでもない。
【００９１】
また、メモリなどのように、入出力端子の位置が固定されている割付リソースについては、例えば図２１に示すように、接続要素を設けてもよい。図２１には、入出力端子の位置が固定されている割付リソース（中央の単位要素にハッチングが施されていない割付リソース）と、入出力端子の位置を変更できる割付リソース（中央の単位要素にハッチングが施された割付リソース）とが記載されている。前者の割付リソースでは、入出力端子と同じ位置にある単位要素に入出力端子が割り当てられ、後者の割付リソースでは、中央に位置する単位要素に入出力端子が割り当てられる。これにより、入出力端子の位置が固定されている割付リソースについては、入出力端子の位置を考慮して単位要素を配置することができる。
【００９２】
このように割付リソースを単位要素と接続要素とを用いて表現した上で、割付リソースを配置することにより、面積は既知であるが、形状が未確定の割付リソースについては、形状を自由に変化させながら、面積と形状が配置結果に与える影響を考慮して、割付リソースを好適に配置することができる。よって、このように精度の高いレイアウトモデルを採用することにより、割付リソースを共有化した際により良い結果を得ることができる。
【００９３】
以上に示すように、本実施形態に係る高位合成方法では、共有化枝生成工程で共有化枝を付加された割付リソース接続グラフに対して、スケジューリング付きリソース配置工程とリソース共有化工程とが実行され、共有化可能か否かを考慮して割付リソースの仮配置が行われる。したがって、割付リソースを仮配置する段階で、共有化可能な割付リソースを近接して配置することにより、後に割付リソースを共有化したときに、クロックタイミングエラーの発生などの問題を防止することができる。また、総実行ステート数が最初に求めた値を超えない範囲内で割付リソースの共有化を実行し、総実行ステート数の少ない合成結果を得ることができる。
【００９４】
また、共有化枝に重み付けを行うことにより、割付リソースの共有化を促進あるいは抑制する程度を制御し、より良い合成結果を得ることができる。また、割付リソースの物理的特徴を考慮したレイアウトモデルを採用することにより、実際のレイアウト結果を考慮した、より良い合成結果を得ることができる。
【００９５】
（第１の実施形態の第１変形例）
図２２は、本発明の第１の実施形態の第１変形例に係るレイアウトベース高位合成方法を示すフローチャートである。図２２に示すフローチャートは、図１に示すフローチャートのリソース共有化工程（ステップＳ１０５）の後に、終了判定工程（ステップＳ１２１）と共有化枝再生成工程（ステップＳ１２２）とを追加したものである。図２２に示す工程のうち、図１と同一の工程については、同一のステップ番号を付して説明を省略する。
【００９６】
本変形例に係る高位合成方法では、図２２に示すように、リソース共有化工程（ステップＳ１０５）の次に、終了判定工程（ステップＳ１２１）が実行される。終了判定工程では、所定の判断基準に従い、処理を終了するか継続するかが判断される。処理継続と判断された場合には、共有化枝再生成工程（ステップＳ１２２）において、割付リソース接続グラフに対して共有化枝を付加し直す処理が行われ、次に、再びスケジューリング付きリソース共有化工程（ステップＳ１０４）が実行される。その後、終了判定工程において処理終了と判定されるまで、ステップＳ１０４〜Ｓ１２２の各工程が繰り返し実行される。
【００９７】
以下、例として、上述した動作記述ＢＤ（すなわち、式（１ａ）および（１ｂ））が動作記述データとして入力された場合に、本変形例に係る高位合成方法において、どのような処理が行われるかを説明する。この場合、本変形例に係る高位合成方法においても、第１の実施形態と同様に、ステップＳ１０１〜Ｓ１０５の各工程が実行される。これにより、リソース共有化工程（ステップＳ１０５）が完了した時点では、割付リソース共有化後の割付リソース接続グラフと各割付リソースの配置位置とが得られる。ここでは、図６に示す割付リソース接続グラフＲＧ１０に対してリソース共有化工程を実行した結果、割付リソースＲ+1とＲ+5、Ｒ+4とＲ+7が共有化され、図２３に示す割付リソース接続グラフＲＧ２が生成されたとする。図２３において、割付リソースＲ+1/5、Ｒ+4/7は、それぞれ、Ｒ+1とＲ+5を共有化した後の割付リソース、Ｒ+4とＲ+7を共有化した後の割付リソースを表し、Ｍ1 〜Ｍ4 は、共有化に伴って追加された選択回路を表す。
【００９８】
終了判定工程（ステップＳ１２１）では、所定の終了条件を満たしているかが判定される。終了判定工程では、例えば、終了判定工程を実施した回数が規定の回数を超えた場合や、前回この工程を実行したときの割付リソース接続グラフから変化がない場合に、処理終了と判断され、それ以外の場合に、処理継続と判断される。
【００９９】
終了判定工程において処理継続と判断された場合には、次に、共有化枝再生成工程（ステップＳ１２２）が実行される。共有化枝再生成工程では、その時点の割付リソース接続グラフに含まれる共有化可能な（同機能の）割付リソース間に、新たな共有化枝が再び生成される。
【０１００】
共有化枝再生成工程では、新たな共有化枝を再生成するときに、処理ノードのスケジュール実現順列数が計算される。ここで、処理ノードのスケジュール実現順列数とは、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えない範囲内で、処理ノードをステートに割り当てる方法の個数をいう。共有化枝再生成工程では、その時点の割付リソース接続グラフに含まれる共有化可能な割付リソース間に新たな共有化枝が生成され、その共有化枝には、次式（６）を用いて計算された重みＷａ’ijが付加される。
Ｗａ’ij＝ＰＧij／（Ｐi ×Ｐj ）  …（６）
ただし、式（６）において、Ｐi 、Ｐj は、それぞれ、ｉ番目およびｊ番目の割付リソースに対応した処理ノードのスケジュール実現順列数であり、ＰＧijは、ｉ番目およびｊ番目の割付リソースを共有化した場合に、これら２個の割付リソースに対応した処理ノードのスケジュール実現順列数である。なお、共有化枝が斥力共有化枝である場合には、共有化枝の重みＷｒ’ijは、式（３）と同様に、次式（７）を用いて計算される。
Ｗｒ’ij＝Ｗａ’ij−１  …（７）
【０１０１】
例えば、図９に示すスケジュール変更可能範囲を参照して、図２３に示す割付リソース接続グラフについて、各処理ノードのスケジュール実現順列数を求めると、次のようになる。図２４〜図２８は、図２３に示す割付リソースＲ+1/5、Ｒ+2、Ｒ+3、Ｒ+4/7、Ｒ+6について、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えない範囲で、処理ノードをステートに割り当てる方法を示す図である。例えば、図９では、処理ノードＮ+1のスケジュール変更可能範囲はステートＳ０だけを含み、処理ノードＮ+5のスケジュール変更可能範囲はステートＳ１だけを含んでいる。したがって、処理ノードＮ+1およびＮ+5における処理を１個の割付リソースＲ+1/5で実行する場合でも、これら２つの処理は、それぞれ、ステートＳ０およびＳ１で実行するしかない（図２４を参照）。これに対して、図９では、処理ノードＮ+4のスケジュール変更可能範囲はステートＳ０〜Ｓ４を含み、処理ノードＮ+7のスケジュール変更可能範囲はステートＳ４だけを含んでいる。したがって、処理ノードＮ+4およびＮ+7における処理を１個の割付リソースＲ+4/7で実行する場合には、これら２つの処理は、４通りの方法で実行できる（図２７を参照）。このようにして割付リソースＲ+1/5、Ｒ+2、Ｒ+3、Ｒ+4/7、Ｒ+6のスケジュール実現順列数は、順に１、１、３、４、１であることが分かる。
【０１０２】
また、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えない範囲で、割付リソースＲ+1/5とＲ+6に対応した処理ノードをステートに割り当てる方法は１通りしかないので（図２９を参照）、ＰＧ+1/5,+6 ＝１となる。上述したように、Ｐ+1/5＝Ｐ+6＝１であるから、式（６）によるＷａ’+1/5,+6 は１となる。同様に、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えない範囲で、割付リソースＲ+4/7とＲ+3に対応した各処理ノードをステートに割り当てる方法は９通りある（図３０を参照）ので、ＰＧ+4/7,+3 ＝９となる。上述したように、Ｐ+4/7 ＝４、Ｐ+3＝３であるから、式（６）によるＷａ’+4/7,+3 は３／４となる。
【０１０３】
図３１は、図３に示すアロケーションスケジューリングに基づき、図２３に示す割付リソース接続グラフＲＧ２に対して付加される引力共有化枝の重みを示す図である。図３２は、図２３に示す割付リソース接続グラフＲＧ２に対して、図３１に示す共有化枝を追加して得られた割付リソース接続グラフＲＧ２０を示す図である。なお、本変形例では、共有化枝は、１本の信号枝を介して直接接続された割付リソース間、および、選択回路と２本の信号枝とを介して間接的に接続された割付リソース間（例えば、選択回路Ｍ2 と２本の信号枝とを介して接続されるＲ+2とＲ+1/5の間）には付加されない。
【０１０４】
共有化枝再生成工程の次には、再びスケジューリング付きリソース配置工程（ステップＳ１０４）が実行され、その後、終了判定工程において処理終了と判定されるまで、ステップＳ１０４〜Ｓ１２２の各工程が繰り返し実行される。このように、本変形例では、最初にリソース共有化工程を実行したときに得られた結果を初期解として、スケジューリング付きリソース配置工程が繰り返し実行される。これにより、割付リソースの共有化がさらに促進され、より良い合成結果を得ることができる。
【０１０５】
なお、上述した第１の実施形態のスケジューリング付きリソース配置工程では、各処理ノードの割当ステートがスケジュール変更可能範囲内で変更されることとした。これに対して、本変形例のスケジューリング付きリソース配置工程では、共有化された割付リソースに対応した処理ノードの割当ステートだけが、当該処理ノード群ごとのスケジュール実現順列の範囲内で、予め規定された頻度で変更される。これにより、共有化された割付リソースに対応した処理ノード群の割当ステートを変更しても、総実行ステート数が最初に求めた値を超えることがない。したがって、総実行ステート数が最初に求めた範囲を超えない範囲内で、割付リソースの共有化に伴い変更された新たなアロケーションスケジュールを考慮して、割付リソースの共有化をさらに促進することができる。
【０１０６】
以上に示すように、本変形例に係る高位合成方法では、割付リソースの共有化に伴い割付リソース接続グラフが変形されるたびに、再び、共有化枝再生成生成工程、スケジューリング付きリソース配置工程、および、リソース共有化工程が実行される。これにより、より多くのハードウェアリソースについて共有化の可能性を発見し、より規模の小さな回路を得ることができる。
【０１０７】
（第１の実施形態の第２変形例）
本発明の第１の実施形態の第２変形例は、上述した第１の実施形態の第１変形例のリソース共有化工程（ステップＳ１０５）において、共有化する割付リソースの個数が制限されていることを特徴とする。
【０１０８】
本変形例に係るレイアウトベース高位合成方法では、共有化する割付リソースの個数の上限値（以下、共有化上限値という）が、予め決定されている。また、リソース共有化工程では、共有化可能な各割付リソース間について、共有化が好ましいほど大きな値となる優先度が計算される。その上で、優先度が所定値以上となる割付リソース間について、優先度が高い順に、共有化上限値を超えない範囲内で、割付リソースの共有化が行われる。
【０１０９】
割付リソース間の優先度を求める方法には、各種の方法が考えられる。例えば、次式（８）に示すように、レイアウト結果における割付リソース間の距離に反比例する優先度を用いてもよい。
ＣＯＳＴ１ij＝Ａ１／Ｌij  …（８）
ただし、式（８）において、Ｌijはレイアウト結果におけるｉ番目およびｊ番目の割付リソース間の距離、Ａ１は実験などで求めたパラメータである。
【０１１０】
このように、式（８）による優先度ＣＯＳＴ１ijが所定値未満となる割付リソース同士を共有化しない理由は、離間して配置された割付リソース同士を共有化したときに、レイアウト結果に弊害が生じることを防止するためである。
【０１１１】
あるいは、次式（９）に示すように、接続枝の重みを、レイアウト結果における割付リソース間の距離で割った値に比例する優先度を用いてもよい。この場合、次式（９）による優先度が、例えば０以上である場合に、割付リソースの共有化が行われる。
ＣＯＳＴ２ij＝Ａ２×ＷＭij／Ｌij  …（９）
ただし、式（９）において、ＷＭijは式（４）で、Ｌijは式（８）で定義された値であり、Ａ２は実験などで求めたパラメータである。
【０１１２】
このように、接続枝の重みＷＭijを考慮して優先度を計算することにより、斥力共有化枝が付加された割付リソース同士は、たとえ両者間の距離が最小であっても、共有化されることはない。斥力共有化枝が付加された割付リソース同士を共有化すると、総実行ステート数が増加する。そこで、式（９）による優先度を用いることにより、斥力共有化枝が付加された割付リソース同士の共有化を防止し、総実行ステート数の増加を確実に防止することができる。
【０１１３】
あるいは、次式（１０）に示すように、接続枝の重みに比例する項と、レイアウト結果における割付リソース間の距離に反比例する項とを有する計算式を用いて優先度を計算してもよい。
ＣＯＳＴ３ij＝Ｂ×ＷＭij＋Ｃ／Ｌij  …（１０）
ただし、式（１０）において、ＷＭijは式（４）で、Ｌijは式（８）で定義された値であり、ＢおよびＣは実験などで求めたパラメータである。
【０１１４】
式（９）を用いた場合、ＷＭijが負であれば、優先度も必ず負になるが、式（１０）を用いた場合には、ＷＭijが負であっても、第２項の値によっては、優先度が正の値になることがある。したがって、式（１０）を用いた場合には、ＷＭijとＬijのどちらを重視するかを、パラメータＢおよびＣを用いて調整することができる。パラメータＢを大きくした場合には、総実行ステート数を重視した共有化が行われ、パラメータＣを大きくした場合には、レイアウト推定精度を重視した共有化が行われる。これにより、レイアウト推定精度（配線長、信号遅延など、論理合成において必要となるレイアウト属性の推定精度）と全体性能とのトレードオフを調整し、物理設計などの後工程における見積もり誤差による再設計を防止することができる。
【０１１５】
あるいは、次式（１１）〜（１３）を単独で用いて、若しくは、次式（１１）〜（１３）を適宜組み合わせて、割付リソース間の優先度を計算してもよい。
ＣＯＳＴ４ij＝Ｄ１／ＢＷij  …（１１）
ＣＯＳＴ５ij＝Ｄ２／ＡＲij  …（１２）
ＣＯＳＴ６ij＝Ｄ３／ＤＬij  …（１３）
ただし、式（１１）〜（１３）において、ＢＷij、ＡＲij、ＤＬijは、それぞれ、ｉ番目およびｊ番目の割付リソースのビット幅の差、面積の差、遅延時間の差、Ｄ１〜Ｄ３は、実験などで求めたパラメータである。この方法で計算された評価値に基づき、割付リソースを共有化することにより、ビット幅や面積や性能などが大きく異なる割付リソース同士の共有化を抑制し、効率の悪い共有化を防止することができる。
【０１１６】
以上に示すように、本変形例に係る高位合成方法では、リソース共有化工程において共有化する割付リソースの個数を制限した上で、共有化枝再生成生成工程、スケジューリング付きリソース配置工程、およびリソース共有化工程が繰り返し実行される。これにより、割付リソースの共有化が徐々に進行し、最終的な解が得られる。したがって、割付リソース接続グラフの変化に伴うレイアウト結果の変化をより詳細に把握し、レイアウトの品質を高めることができる。
【０１１７】
（第１の実施形態の第３変形例）
本発明の第１の実施形態の第３変形例は、上述した第１の実施形態のスケジューリング付きリソース配置工程（ステップＳ１０４）において、同じステートに割り当てられた共有化可能な２つの処理ノードが所定の条件を満たす場合には、これらの処理ノードに対応した割付リソース間に付加される共有化枝の重みが無効な値（共有化を促進も抑制もしない値）に設定されることを特徴とする。ここで、上記所定の条件とは、同じステートに割り当てられた共有化可能な２個の処理ノードが、当該ステート内にある１本以上の信号枝を介して接続されていることである。この条件を満たす２個の処理ノードに対応した割付リソース間には、第１の実施形態では負の重みを有する斥力共有化枝が付加されるが、本変形例では重み０を有する共有化枝が付加される。
【０１１８】
アロケーションスケジューリングにおいて、１本の信号枝を介して直接、あるいは複数の信号枝を介して間接的に接続された２個の処理ノードが、同じステートに割り当てられることがある。以下、このような割り当てをチェイニングという。チェイニングされた複数の処理ノードにおける一連の演算は、１クロック周期以内で実行される。したがって、割付リソース間の接続遅延時間を考慮すると、チェイニングされた複数の処理ノードに対応した割付リソースは、近接して配置されることが好ましい。このような好ましい配置は、上記所定の条件を満たす２個の処理ノードに対応した割付リソース間に、重み０を有する共有化枝を付加することにより実現される。
【０１１９】
以下、例として、次式（１４）に示す計算式が動作記述データとして入力された場合に、本変形例に係る高位合成方法において、どのような処理が行われるかを説明する。
ｘ＝（（（ａ＋ｂ）＜＜２）＋ｃ）×（ｄ＋ｅ）  …（１４）
【０１２０】
式（１４）が入力された場合、本変形例においても、第１の実施形態のステップＳ１０１〜Ｓ１０３が実行される。ここでは、ステップＳ１０３までを実行した時点で、図３３に示すアロケーションスケジュールと、図３４に示す割付リソース接続グラフとが得られたとする。図３４に示す割付リソース接続グラフの割付リソースＲ+1、Ｒ+2、Ｒ+3、Ｒ<<、Ｒ× は、それぞれ、図３３に示すアロケーションスケジュールの処理ノードＮ+1、Ｎ+2、Ｎ+3、Ｎ<<、Ｎ× に対応している。また、図３３に示すように、２本の信号枝で接続された処理ノードＮ+1、Ｎ<<、Ｎ+2は、同じステートに割り当てられている。すなわち、これら３個の処理ノードは、チェイニングされている。また、割付リソースＲ+1とＲ+2は、共有化可能で、かつ、同じステートに割り当てられているので、これら割付リソース間には、斥力共有化枝が付加される。
【０１２１】
第１の実施形態では、ステップＳ１０３までを実行して得られたアロケーションスケジュールと割付リソース接続グラフとに対して、スケジューリング付きリソース配置工程（ステップＳ１０４）が実行される。したがって、第１の実施形態では、割付リソースＲ+1とＲ+2の間に斥力共有化枝が付加された状態で、スケジューリング付きリソース配置工程が実行される。このため、割付リソースＲ+1とＲ+2は、近接して配置されることが好ましいにもかかわらず、離間して配置される。
【０１２２】
これに対して、本変形例では、割付リソースＲ+1とＲ+2は、割付リソースＲ<<および２本の信号枝を介して接続されているので、上記所定の条件を満たす。したがって、割付リソースＲ+1とＲ+2の間には、重みが０の斥力共有化枝が付加され、その状態で、スケジューリング付きリソース配置工程が実行される。よって、割付リソースＲ+1とＲ+2は、近接して配置される。
【０１２３】
以上に示すように、本変形例では、アロケーションスケジュールにおいて複数の処理ノードがチェイニングされている場合でも、これら処理ノードに対応した割付リソースは近接して配置されやすくなる。したがって、この場合でも、予め規定されたクロック周期以内で動作する回路を得ることができる。
【０１２４】
（第１の実施形態の第４変形例）
図３５は、本発明の第１の実施形態の第４変形例に係るレイアウトベース高位合成方法を示すフローチャートである。図３５に示すフローチャートは、図１に示すフローチャートの共有化枝生成工程（ステップＳ１０３）とスケジューリング付きリソース配置工程（ステップＳ１０４）との間に、引力共有化枝重み調整工程（ステップＳ１３１）を追加したものである。図３５に示す工程のうち、図１と同一の工程については、同一のステップ番号を付して説明を省略する。
【０１２５】
本変形例に係る高位合成方法では、共有化枝生成工程（ステップＳ１０３）の次に、引力共有化枝重み調整工程（ステップＳ１３１）が実行される。引力共有化枝重み調整工程では、一定の基準に従って、共有化枝生成工程で生成された引力共有化枝に付された重みが変更される。
【０１２６】
これまでに述べた共有化枝生成工程では、割付リソース接続グラフに含まれる共有化可能な割付リソース間には、割付リソースが１本の信号枝を介して直接接続されている場合を除き、共有化枝（引力共有化枝または斥力共有化枝）が付加される。このため、信号の伝播に無関係な共有化枝が多くなり過ぎて、仮のレイアウト結果と、後に実行される実際のレイアウト工程で得られるレイアウト結果との間に乖離が生じ、レイアウト結果の見積もりが不正確になる。そこで、本変形例に係る高位合成方法は、上記問題を解決するために、引力共有化枝重み調整工程を備えている。なお、本変形例においても、総実行ステート数の増加を抑制するために、斥力共有化枝の重みは調整されない。
【０１２７】
図３６は、引力共有化枝重み調整工程（ステップＳ１３１）の詳細を示すフローチャートである。図３６に示す引力共有化枝重み調整工程では、共有化枝生成工程で共有化枝を付加された割付リソース接続グラフに対して、レイアウト困難度評価工程、引力共有化枝選択工程、および、引力共有化枝重み削減工程が実行される。
【０１２８】
レイアウト困難度評価工程（ステップＳ１４１）では、共有化枝が付加された割付リソース接続グラフについて、レイアウトの困難度を示す評価値（以下、レイアウト困難度評価値という）が計算され、レイアウト困難度評価値に基づき、処理を終了するか継続するかが判断される。処理継続と判断された場合には、引力共有化枝選択工程（ステップＳ１４２）において、所定の基準に基づいて共有化枝が選択される。次に、引力共有化枝重み削減工程（ステップＳ１４３）において、引力共有化枝選択工程で選択された共有化枝の引力共有化枝の重みが、０より大きい所定値までの範囲内で削減され、その次に、再びレイアウト困難度評価工程が実行される。その後、レイアウト困難度評価工程において処理終了と判定されるまで、ステップＳ１４１〜Ｓ１４３が繰り返し実行される。
【０１２９】
以下、レイアウト困難度評価工程（ステップＳ１４１）および引力共有化枝選択工程（ステップＳ１４２）の詳細を説明する。先に、レイアウト困難度評価工程の詳細を説明する。
【０１３０】
レイアウト困難度評価工程では、例えば、次式（１５）に示すように、割付リソース接続グラフの信号枝および引力共有化枝に付された重みの総和を用いて、レイアウト困難度評価値を計算してもよい。
ＣＯＳＴｗ１＝Ｗｓ＋Ｗａ  …（１５）
ただし、式（１５）において、Ｗｓは信号枝の重みの総和、Ｗａは引力共有化枝の重みの総和を表す。式（１５）による値ＣＯＳＴｗ１は、信号枝および引力共有化枝の重みの総和となる。この値が所定値以上であるときは処理継続と判断され、この値が所定値未満であるときは処理終了と判断される。
【０１３１】
あるいは、引力共有化枝の重みの総和Ｗｓと信号枝の重みの総和Ｗａとの差（次式（１６））や、信号枝および引力共有化枝の重みの総和に占める引力共有化枝の重みの総和Ｗｓの割合（次式（１７））などを、レイアウト困難度評価値としてもよい。
ＣＯＳＴｗ２＝Ｗｓ−Ｗａ            …（１６）
ＣＯＳＴｐｗ＝Ｗｓ／（Ｗｓ＋Ｗａ）  …（１７）
これらの値が所定値以上であるときは処理継続と判断され、これらの値が所定値未満であるときは処理終了と判断される。
【０１３２】
式（１５）〜（１７）による値は、引力共有化枝の影響が大きいほど、大きくなる。引力共有化枝は、割付リソースの共有化を促進するために付加された、実際の回路には存在しない冗長な枝である。このような引力共有化枝の本数や重みが全体に占める割合があまりに大きいと、実際に回路を構成する信号枝が配置や遅延時間などに与える影響が過小に評価され、結果的にレイアウトの品質が低下する可能性がある。そこで、式（１５）〜（１７）による値がある程度以下になるように、引力共有化枝の重みを削減することにより、引力共有化枝が過剰な影響を及ぼすことを防止することができる。
【０１３３】
あるいは、割付リソース接続グラフに含まれる、所定値以下の重みを有する引力共有化枝にダミーのハードウェアリソースを割り付けたノード（以下、ダミーノードという）を追加することにより、評価用の割付リソース接続グラフを生成し、そのグラフについて次式（１８）を用いて計算した値を、レイアウト困難度評価値としてもよい。
ＣＯＳＴｄ＝｛ｌｏｇ（Ｎ１）−ｌｏｇ（Ｎ２）｝／ｌｏｇ（２）  …（１８）
ただし、式（１８）におけるＮ１およびＮ２は、以下のように定義される。グラフ中のあるノードに着目したときに、当該ノードと１本の信号枝によって接続されたノード（以下、１次隣接節点という）の個数をｎ１、当該ノードと２本以内の信号枝を介して接続さノード（以下、２次以内隣接節点という）の個数をｎ２とする。例えば、図３７に示すノードＴＧについては、実線で接続された１次隣接節点の個数ｎ１は５、実線および破線で接続された２次以内隣接節点の個数は１３となる。式（１８）におけるＮ１は、割付リソース接続グラフに含まれるすべてのノードについての上記ｎ１の合計（すなわち、１次隣接節点の総数）を表し、式（１８）におけるＮ２は、割付リソース接続グラフに含まれるすべてのノードについての上記ｎ２の合計（すなわち、２次以内隣接節点の総数）を表す。なお、式（１８）におけるＮ１およびＮ２を、それぞれ、ノード１個あたりの１次隣接節点の個数の平均値、および、ノード１個あたりの２次以内隣接節点の個数の平均値としてもよい。
【０１３４】
式（１８）は、特許第２９７７４２２号公報に記載されたものであり、グラフの接続関係に基づきレイアウトの品質を推定するために用いられる。式（１８）による値ＣＯＳＴｄは、与えられた割付リソース接続グラフが何次元の複雑さを有するかを示す。したがって、この値が２より大きい場合には、割付リソースを２次元にレイアウトすることが困難になる。そこで、式（１８）〜（１７）による値が所定値（例えば、２）以下になるように、引力共有化枝の重みを削減することにより、共有化枝を付加した割付リソース接続グラフを無理なく２次元にレイアウトすることができる。
【０１３５】
ただし、特許第２９７７４２２号公報に記載された方法では、重み付きグラフを扱うことができない。そこで、本変形例では、所定値以下の重みを有する引力共有化枝にダミーノードを追加することにより、評価用の割付リソース接続グラフが生成される。例えば、元の割付リソース接続グラフに図３７に示すノードが含まれている場合、評価用の割付リソース接続グラフの対応する部分は、図３８に示すようになる。図３８では、２個のダミーノードが追加されたために、２次以内隣接節点の個数ｎ２が１３から１２に変化している。
【０１３６】
このようにダミーノードを追加することにより、ｎ１およびｎ２の値が小さくなり、結果としてＣＯＳＴｄの値が小さくなる。これにより、スケジューリング付きリソース配置工程で最適なレイアウト結果を求める際に、小さい重みを有する枝はあまり考慮しないことを、式（１８）に反映させることができる。このようにして、特許第２９７７４２２号公報に記載された方法を、重み付きグラフにも適用可能なように拡張することができる。
【０１３７】
次に、引力共有化枝選択工程（ステップＳ１４２）の詳細を説明する。引力共有化枝選択工程では、上述したように、所定の基準に基づいて、次の引力共有化枝重み削減工程で重みを削減されるべき引力共有化枝が選択される。このような引力共有化枝としては、両端に接続された割付リソースを共有化したときの効果が低い引力共有化枝（すなわち、共有化効率の低い引力共有化枝）が選択される。
【０１３８】
引力共有化枝選択工程で引力共有化枝を選択する方法には、各種の方法が考えられる。例えば、第１の選択方法として、引力共有化枝の両端に接続された割付リソース間のビット幅の差を求め、その差が大きい引力共有化枝を選択してもよい。この場合、ビット幅の差が最大のものを選択してもよく、あるいは、ビット幅の差が所定値以上のものを選択してもよい。ビット幅が異なる割付リソースを共有化すると、ビット幅が大きい方の割付リソースでビット幅が小さい方の演算を実行することになるが、これでは割付リソースの性能を十分に発揮できないので、この共有化は非効率的である。そこで、引力共有化枝選択工程で割付リソースのビット幅の差が最大となる引力共有化枝を選択し、その後に引力共有化枝重み削減工程で選択した引力共有化枝の重みを削減することにより、ビット幅が異なる割付リソースの共有化を防止することができる。
【０１３９】
あるいは、第２の選択方法として、引力共有化枝の両端に接続された割付リソース間の遅延時間の差を求め、その差が大きい引力共有化枝を選択してもよい。この場合、遅延時間の差が最大のものを選択してもよく、あるいは、遅延時間の差が所定値以上のものを選択してもよい。遅延時間が異なる割付リソースを共有化した場合にも、上記と同様の理由で、割付リソースの性能を十分に発揮できない。そこで、引力共有化枝選択工程および引力共有化枝重み削減工程で、割付リソースの遅延時間の差が最大となる引力共有化枝を選択し、その重みを削減することにより、遅延時間が異なる割付リソースの共有化を防止することができる。
【０１４０】
あるいは、第３の選択方法として、引力共有化枝の両端に接続された割付リソース間で面積が小さい方の値を求め、求めた値が小さい引力共有化枝を選択してもよい。この場合、求めた値が最小のものを選択してもよく、あるいは、求めた値が所定値以下のものを選択してもよい。面積が小さい割付リソースを共有化しても、回路全体の面積削減にはあまり貢献しない。そこで、共有化枝選択工程および引力共有化枝重み削減工程で、割付リソース間で面積が小さい方の値が最小となる引力共有化枝を選択し、その重みを削減することにより、面積が小さい割付リソースの共有化を防止することができる。
【０１４１】
あるいは、第４の選択方法として、より共有化を抑制する重み（本変形例では、より小さな重み）が付された引力共有化枝を選択してもよい。この場合、重みが最小のものを選択してもよく、あるいは、重みが所定値以下のものを選択してもよい。引力共有化枝に付された重みが小さいほど、その両端に接続された割付リソースを共有化することが好ましくない。そこで、共有化枝選択工程および引力共有化枝重み削減工程で、引力共有化枝の重みが小さい引力共有化枝を選択し、その重みを削減することにより、共有化の効率が低い引力共有化枝の影響を除去し、割付リソースをより効率的に共有化することができる。
【０１４２】
あるいは、第５の選択方法として、引力共有化枝の両端に接続された割付リソースの出力値のライフタイムを求め、求めたライフタイムが重なる確率が高い共有化枝を選択してもよい。この場合、ライフタイムが重なる確率が最大のものを選択してもよく、あるいは、その確率が所定値以上のものを選択してもよい。ライフタイムが重なる割付リソースを共有化した場合、割付リソースの出力値を保持するレジスタを共有化できないので、後に実行されるレジスタの共有化によって、回路の面積を削減できる可能性が少ない。そこで、共有化枝選択工程および引力共有化枝重み削減工程で、求めた確率が高い引力共有化枝を選択し、その重みを削減することにより、共有化による効果が低い引力共有化枝の影響を除去し、割付リソースをより効率的に共有化することができる。
【０１４３】
なお、第５の選択方法で計算される確率とは、ｉ番目およびｊ番目の割付リソースを共有化した場合に、これら割付リソースに対応した２個の処理ノードを、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えないようにステートに割り当てる方法のうち、２個の処理ノードの出力値のライフタイムが重なる方法の割合をいい、次式（１９）を用いて計算される。
Ｐｏij＝Ｏｃij／ＰＧij  …（１９）
ただし、式（１９）において、ＰＧijは式（６）で定義された値であり、Ｏｃijは、ｉ番目およびｊ番目の割付リソースに対応した処理ノードを、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えないようにステートに割り当てる方法のうち、２個の処理ノードの出力値のライフタイムが重なる方法の個数を表す。
【０１４４】
例えば、図９に示すスケジュール変更可能範囲について式（１９）による確率Ｐｏijを計算すると、以下のようになる。割付リソースＲ+3とＲ+5を共有化する場合、これら割付リソースに対応した２個の処理ノードを、総実行ステート数が最初に求めた値を超えないようにステートに割り当てる方法は、２通りある（図３９を参照）。図３９（ａ）に示すように、処理ノードＮ+3（割付リソースＲ+3に対応した処理ノード）をステートＳ０に、処理ノードＮ+5（割付リソースＲ+5に対応した処理ノード）をステートＳ１に割り当てた場合には、処理ノードＮ+3の出力値のライフタイムと処理ノードＮ+5の出力値のライフタイムは重なる。これに対して、図３９（ｂ）に示すように、処理ノードＮ+3をステートＳ２に、処理ノードＮ+5をステートＳ１に割り当てた場合には、処理ノードＮ+3の出力値のライフタイムと処理ノードＮ+5の出力値のライフタイムは、重ならない。よって、ＰＧ+3,+5 ＝２、Ｏｃ+3,+5 ＝１より、Ｐｏ+3,+5 ＝１／２となる。
【０１４５】
同様に、割付リソースＲ+4とＲ+5を共有化する場合、これら割付リソースに対応した２個の処理ノードを、総実行ステート数が最初に求めた値を超えないようにステートに割り当てる方法は、３通りある（図４０を参照）。このうち、処理ノードＮ+4（割付リソースＲ+4に対応した処理ノード）の出力値のライフタイムと処理ノードＮ+5の出力値のライフタイムが重なる方法は、図４０（ａ）に示す１通りである。よって、ＰＧ+4,+5 ＝３、Ｏｃ+4,+5 ＝１より、Ｐｏ+4,+5 ＝１／３となる。
【０１４６】
あるいは、第６の選択方法として、上記第１〜第５の選択方法における評価値を適宜組み合わせた評価値を求め、その評価値が最大（あるいは最小）となる引力共有化枝を選択してもよい。例えば、次式（２０）による評価値Ｓｃが最大となる共有化枝を選択してもよい。
Ｓｃ＝α１×ΔＢ＋α２×ΔＤ＋α３／Ａ＋α４／Ｗ＋α５×Ｐｏ  …（２０）
ただし、式（２０）において、ΔＢは割付リソース間のビット幅の差（第１の選択方法における評価値）、ΔＤは割付リソース間の遅延時間の差（第２の選択方法における評価値）、Ａは小さい方の割付リソースの面積（第３の選択方法における評価値）、Ｗは引力共有化枝の重み（第４の選択方法における評価値）、Ｐｏは割付リソースの出力値のライフタイムが重なる確率（第５の選択方法における評価値）、α１〜α５は、どの選択方法を重視するかを調整するためのパラメータである。α１〜α５を好適な値に調整することにより、各種の選択方法を容易に実現することができる。
【０１４７】
以上に示すように、本変形例に係る高位合成方法では、引力共有化枝重み調整工程において、引力共有化枝に付された重みが適切な値に変更され、引力共有化枝の重みを効果的に削減した割付リソース接続グラフが生成される。したがって、割付リソース接続グラフに共有化枝を付加しても、レイアウトの品質が著しく低下することがない。よって、レイアウトの品質を維持しつつ、従来よりも総実行ステート数の少ない回路を得ることができる。
【０１４８】
（第２の実施形態）
図４１は、本発明の第２の実施形態に係るレイアウトベース高位合成方法を示すフローチャートである。図４１に示す高位設計方法では、設計対象回路の動作仕様を記述した動作記述データに対して、ＣＤＦＧ生成工程、初期アロケーションスケジューリング工程、引力共有化枝生成工程、引力共有化枝間引き工程、リソース配置工程、および、逐次改良型リソース共有化工程が実行される。
【０１４９】
図４１において、ＣＤＦＧ生成工程（ステップＳ２０１）および初期アロケーションスケジューリング工程（ステップＳ２０２）は、第１の実施形態に係る高位合成方法（図１）に含まれる工程と同じである。これらのステップの詳細は、第１の実施形態で説明したので、ここでは説明を省略する。
【０１５０】
引力共有化枝生成工程（ステップＳ２０３）では、初期アロケーションスケジューリング工程で生成された割付リソース接続グラフに対して、共有化可能な割付リソース間に新たな共有化枝が付加される。ただし、本実施形態では、第１の実施形態とは異なり、引力共有化枝生成工程では、引力共有化枝だけが付加され、斥力共有化枝は付加されない。また、本実施形態においても、第１の実施形態と同様に、割付リソースの共有化が行われる程度を調整するために、引力共有化枝に重みを付してもよい。引力共有化枝に付する重みは、例えば、式（２）を用いて計算される。
【０１５１】
引力共有化枝間引き工程（ステップＳ２０４）では、引力共有化枝生成工程で生成された引力共有化枝のうち、一部の引力共有化枝が削除される。したがって、引力共有化枝間引き工程により、一部の割付リソース間には引力共有化枝が付加されているが、残りの割付リソース間には引力共有化枝が付加されていない割付リソース接続グラフが得られる。
【０１５２】
リソース配置工程（ステップＳ２０５）では、引力共有化枝間引き工程で得られた割付リソース接続グラフに基づき、割付リソースを配置要素とし、割付リソース間の枝を配置要素間の接続要素として、仮に設けたレイアウト領域における各割付リソースの概略配置が求められる。リソース配置工程では、各割付リソースを大きさを持たない点で表したときの相対的な位置関係が求められ、その後に、仮に設けたレイアウト領域における各割付リソースの配置位置が決定される。
【０１５３】
逐次改良型リソース共有化工程（ステップＳ２０６）は、従来の高位合成方法におけるリソース共有化工程（図４４のステップＳ１４）と同様に、割付リソース数を削減するために、レイアウト結果において近接して配置された同機能の割付リソースが複数個ある場合に、これらの割付リソースが処理タイミングを考慮して共有化される。ただし、この工程では、従来の方法とは異なり、上記の処理に加えて、割付リソースの共有化に伴い割付リソース接続グラフが変化した場合に、共有化枝を再生成し、レイアウト結果を修正する処理が行われる。
【０１５４】
以下、本実施形態の特徴である引力共有化枝間引き工程（ステップＳ２０４）、リソース配置工程（ステップＳ２０５）、および、逐次改良型リソース共有化工程（ステップＳ２０６）の詳細を説明する。まず、引力共有化枝間引き工程の詳細を説明する。
【０１５５】
図４２は、引力共有化枝間引き工程の詳細を示すフローチャートである。図４２に示す引力共有化枝間引き工程では、引力共有化枝生成工程で引力共有化枝を付加された割付リソース接続グラフに対して、レイアウト困難度評価工程、共有化枝選択工程、および、共有化枝削除工程が実行される。なお、この引力共有化枝間引き工程の詳細は、第１の実施形態の第４変形例で説明した引力共有化枝重み調整工程（ステップＳ１３１）の詳細（図３６）と類似している。
【０１５６】
図４２において、レイアウト困難度評価工程（ステップＳ２１１）および引力共有化枝選択工程（ステップＳ２１２）は、第１の実施形態の第４変形例で説明したレイアウト困難度評価工程（ステップＳ１４１）および引力共有化枝選択工程（ステップＳ１４２）と同じである。引力共有化枝重み削除工程（ステップＳ２１３）では、引力共有化枝選択工程で選択された引力共有化枝が割付リソース接続グラフから削除され、その次に、再びレイアウト困難度評価工程が実行される。その後、レイアウト困難度評価工程において処理終了と判定されるまで、ステップＳ２１１〜Ｓ２１３が繰り返し実行される。
【０１５７】
第１の実施形態の第４変形例では、引力共有化枝重み削減工程（ステップＳ１４３）において、選択された引力共有化枝の重みが削減される。これに対して、本実施形態では、選択された引力共有化枝が、割付リソース接続グラフから完全に削除される。本実施形態では、割付リソース接続グラフの割付リソース間には、引力共有化枝だけが付加され、斥力共有化枝が付加されることはないので、引力共有化枝を削除することは、引力共有化枝の重みを０に設定するのと同じ意味になる。したがって、引力共有化枝を削除することにより、後に実行される逐次改良型リソース共有化工程で処理すべき引力共有化枝の本数を削減し、割付リソースの配置に要する時間を短縮することができる。
【０１５８】
次に、リソース配置工程（ステップＳ２０５）の詳細を説明する。リソース配置工程では、引力共有化枝を追加された割付リソース接続グラフを、あるレイアウトモデルに従って配置した場合に、コストが最小となるレイアウト結果が求められる。割付リソース接続グラフを配置したときのコストは、例えば、次式（２１）で与えられ、次式（２１）によるコストＣＯＳＴが最小となる割付リソースの配置結果が求められる。
【数４】
2006011878.tif 000006
ただし、式（２１）において、Ｒn およびＬijは式（４）で定義された値であり、ＷＭij’はｉ番目およびｊ番目の割付リソース間の接続枝の重みを表す。本実施形態では、接続枝の重みＷＭ’ijは、枝の種類（信号枝、引力共有化枝）ごとに定義され、例えば、接続枝が信号枝である場合には１、接続枝が引力共有化枝である場合は式（２）によるＷａijに設定される。
【０１５９】
上述したように、第１の実施形態のスケジューリング付きリソース配置工程（図１のステップＳ１０４）では、割付リソースの配置位置を変更する処理（ＭＯＶＥ処理）と処理ノードの割当ステートを変更する処理（ＲＥＳＣＨ処理）とが繰り返し行われる。これに対して、本実施形態のリソース配置工程では、ＭＯＶＥ処理だけが繰り返し行われ、ＲＥＳＣＨ処理は行われない。また、第１の実施形態のスケジューリング付きリソース配置工程では、共有化可能な割付リソースは、同じ位置に配置できることとした。これに対して、本実施形態のリソース配置工程では、共有化可能な割付リソースでも、同じ位置に配置することは禁止される。
【０１６０】
式（２１）に示すコストＣＯＳＴが最小となるレイアウト結果は、上記の条件下で求められる。これにより、求めたレイアウト結果では、引力共有化枝で接続された割付リソース同士は、近接して配置される。したがって、引力共有化枝で接続された割付リソース同士の共有化が促進される。
【０１６１】
次に、逐次改良型リソース共有化工程（ステップＳ２０６）の詳細を説明する。図４３は、逐次改良型リソース共有化工程の詳細を示すフローチャートである。図４３に示す逐次改良型リソース共有化工程では、引力共有化枝間引き工程で得られた割付リソース接続グラフとリソース配置工程で得られたレイアウト結果とに対して、終了判定工程、共有化対象選択工程、選択判定工程、被選択リソース共有化工程、共有化枝再生成工程、および、レイアウト結果修正工程が実行される。
【０１６２】
終了判定工程（ステップＳ２２１）では、予め定義された共有化終了条件を満足するか否かが判定され、処理継続と判断された場合には、共有化対象選択工程（ステップＳ２２２）において、レイアウト結果における割付リソース間の距離に基づき、共有化すべき割付リソースが選択される。次に、選択判定工程（ステップＳ２２３）では、共有化対象選択工程で選択が行われた否かが判定され、選択が行われた場合には、被選択リソース共有化工程、共有化枝再生成工程、および、レイアウト結果修正工程が実行される。
【０１６３】
被選択リソース共有化工程（ステップＳ２２４）では、共有化対象選択工程で選択された割付リソースが共有化され、割付リソース接続グラフが変更される。次に、引力共有化枝再生成工程（ステップＳ２２５）では、変更後の割付リソース接続グラフに対して、引力共有化枝を付加し直す処理が行われる。次に、レイアウト結果修正工程（ステップＳ２２６）では、共有化枝を付加し直した後の割付リソース接続グラフに基づき、レイアウト結果が修正される。
【０１６４】
以下、図４３に示す各工程の詳細を説明する。終了判定工程（ステップＳ２２１）では、例えば、使用可能な割付リソース数が所定数以上であるか否かが、共有化終了条件として採用される。終了判定工程では、使用可能な割付リソース数が所定数以上である場合に、処理継続と判定され、それ以外の場合には、処理終了と判定される。
【０１６５】
共有化対象選択工程（ステップＳ２２２）では、共有化可能な割付リソースのペアの集合から、例えば、式（８）による評価値ＣＯＳＴ１ijが所定値以上で、かつ、最大となる割付リソースのペアが選択される。あるいは、式（８）に代えて、次式（２２）による評価値を使用してもよい。
ＣＯＳＴ５ij＝Ａ２×ＷＭ’ij／Ｌij  …（２２）
ただし、式（２２）において、ＬijおよびＷＭ’ijは、それぞれ、式（８）および（２１）で定義された値であり、Ａ２は実験などで求めたパラメータである。
【０１６６】
本実施形態では、ＷＭ’ij（信号枝または引力共有化枝の重み）に基づき、割付リソースの共有化が行われ、信号枝あるいは引力共有化枝のいずれによっても接続されていない割付リソース同士は、たとえ両者間の距離が最短であっても、共有化されない。ＷＭ’ijが０である割付リソース同士を共有化すると、総実行ステート数が初期アロケーションスケジューリング工程で求めた値を超えることがある。したがって、本実施形態に係る高位合成方法によれば、ＷＭ’ijが０である割付リソース同士の共有化を防止し、総実行ステート数の増加をより確実に防止することができる。
【０１６７】
あるいは、式（８）に代えて、次式（２３）による評価値を使用してもよい。
ＣＯＳＴ６ij＝Ｂ×ＷＭ’ij＋Ｃ／Ｌij  …（２３）
ただし、式（２３）において、ＬijおよびＷＭ’ijは、それぞれ、式（８）および（２１）で定義された値であり、ＢおよびＣは実験などで求めたパラメータである。
【０１６８】
式（２２）を用いた場合、ＷＭ’ijが０であれば、評価値は０になるが、式（２３）を用いた場合、ＷＭ’ijが０であっても、第２項の存在により、評価値は０にはならない。したがって、ＷＭijとＬijのどちらを重視するかを、パラメータＢおよびＣを用いて調整することができる。これによる効果は、第１の実施形態の第２変形例で述べた効果と同じである。
【０１６９】
被選択リソース共有化工程（ステップＳ２２４）では、上述したように、共有化対象選択工程で選択された割付リソースが共有化され、割付リソース接続グラフが変更される。この際、割付リソース接続グラフに対して、割付リソースの共有化に伴い必要とされる選択回路が追加される。
【０１７０】
共有化枝再生成工程（ステップＳ２２５）では、被選択リソース共有化工程で処理された割付リソース接続グラフに対して、引力共有化枝を付加し直す処理が行われる。この工程は、第１の実施形態の第１変形例の共有化枝再生成工程（図２２のステップＳ１２２）と同じである。すなわち、その時点の割付リソース接続グラフに含まれる共有化可能な割付リソース間に共有化枝が再び生成され、その共有化枝には、式（６）による重みＷａ’ijが付される。
【０１７１】
レイアウト結果修正工程（ステップＳ２２６）では、上述したように、共有化枝を付加し直した後の割付リソース接続グラフに基づき、レイアウト結果が修正される。より詳細には、共有化枝再生成工程で処理された割付リソース接続グラフに対して、式（２１）で計算されるコストＣＯＳＴが最小となる割付リソースの配置結果が求められる。
【０１７２】
図４３に示す逐次改良型リソース共有化工程では、終了条件が満たされるか（ステップＳ２２１の処理終了）、あるいは、共有化すべき割付リソースが選択されなくなる（ステップＳ２２３の選択なし）までの間、割付リソースが共有化されるたび、その時点の割付リソース接続グラフに対して、引力共有化枝の生成、レイアウト結果修正、割付リソースの共有化が実行される。これらの処理を繰り返すことにより、最終的な割付リソースの個数と、各割付リソースの配置位置が決定される。
【０１７３】
以上に示すように、本実施形態に係る高位合成方法では、レイアウトを考慮して割付リソースを共有化する際に、割付リソース接続グラフに引力共有化枝を付加することにより、総実行ステート数が初期アロケーションスケジュールで求めた値を超えることなく、割付リソースの共有化が促進される。したがって、レイアウトを考慮しながら、従来の高位合成方法よりも、総実行ステート数の少ない回路を得ることができる。
【０１７４】
また、引力共有化枝に重み付けを行うことにより、割付リソースの共有化を促進する程度を制御し、より良い合成結果を得ることができる。また、割付リソース接続グラフから共有化の効果が低い引力共有化枝を削除することにより、処理時間を短縮し、レイアウトの品質を維持しながら、従来の高位合成方法よりも、総実行ステート数の少ない回路を得ることができる。
【０１７５】
なお、本実施形態においても、第１の実施形態の第４変形例で述べたように、引力共有化枝の重みをゼロよりも大きい所定の範囲内で削減してもよい。これにより、第１の実施形態の第４変形例と同様に、レイアウトの品質を維持しながら、総実行ステート数の少ない回路を得ることができる。
【０１７６】
以上、本発明の第１および第２の実施形態、並びに、これらの変形例に係る高位合成方法について説明したが、これらの高位合成方法に含まれる特徴をその性質に反しない限り任意に組み合わせて、新たな高位合成方法を構成できることは言うまでもない。
【産業上の利用可能性】
【０１７７】
本発明の高位合成方法は、処理に必要なクロック周期数を増加させることなく、かつ、割付リソースの共有化を効果的に行うという効果を奏するので、各種のディジタル半導体集積回路の設計に広く利用することができる。
【図面の簡単な説明】
【０１７８】
【図１】本発明の第１の実施形態に係る高位合成方法を示すフローチャート
【図２】ＣＤＦＧの一例を示す図
【図３】図２に示すＣＤＦＧについて、図１に示す初期アロケーションスケジュール工程で得られるアロケーションスケジュールを示す図
【図４】図２に示すＣＤＦＧについて、図１に示す初期アロケーションスケジュール工程で生成される割付リソース接続グラフを示す図
【図５】図４に示す割付リソース接続グラフについて、図１に示す共有化枝生成工程で付加される共有化枝の種類を示す図
【図６】図４に示す割付リソース接続グラフについて、図５に示す種類の共有化枝を付加した割付リソース接続グラフを示す図
【図７】従来の高位合成方法により、リソース共有化によって総実行ステート数が増加した割付リソース接続グラフを示す図
【図８】図１に示す共有化枝生成工程の詳細を示すフローチャート
【図９】図３に示すアロケーションスケジューリングについてのスケジュール変更可能範囲を示す図
【図１０】図４に示す割付リソース接続グラフに付加される共有化枝の重みを示す図
【図１１】３個の処理ノードのスケジュール変更可能範囲を示す図
【図１２】図１１に示す処理ノードＦｂとＦｃを共有化する場合に可能なスケジュールを示す図
【図１３】図１１に示す処理ノードＦａとＦｂを共有化する場合に可能なスケジュールを示す図
【図１４】図１１に示す処理ノードＦａとＦｃを共有化する場合に可能なスケジュールを示す図
【図１５】図１に示すスケジューリング付きリソース配置工程で採用されるレイアウトモデルにおいて、割付リソースが複数の単位要素に分割されることを示す図
【図１６】図１に示すスケジューリング付きリソース配置工程で採用されるレイアウトモデルにおける、剛リソースのモデルを示す図
【図１７】図１に示すスケジューリング付きリソース配置工程で採用されるレイアウトモデルにおける、軟リソースのモデルを示す図
【図１８】図１に示すスケジューリング付きリソース配置工程で採用されるレイアウトモデルにおける、軟リソースのモデルを示す図
【図１９】図１に示すスケジューリング付きリソース配置工程で採用されるレイアウトモデルにおける、軟リソースのモデルの第３例を示す図
【図２０】図１に示すスケジューリング付きリソース配置工程で採用されるレイアウトモデルにおける、２種類の加算器のモデルを示す図
【図２１】図１に示すスケジューリング付きリソース配置工程で採用されるレイアウトモデルにおける、割付リソース間の接続方法を示す図
【図２２】本発明の第１の実施形態の第１変形例に係る高位合成方法を示すフローチャート
【図２３】図２２に示す高位合成方法において、割付リソース共有化後に得られる割付リソース接続グラフを示す図
【図２４】図２３に示す割付リソースＲ+1/5に対応した処理ノードの可能なスケジュールを示す図
【図２５】図２３に示す割付リソースＲ+2に対応した処理ノードの可能なスケジュールを示す図
【図２６】図２３に示す割付リソースＲ+3に対応した処理ノードの可能なスケジュールを示す図
【図２７】図２３に示す割付リソースＲ+4/7に対応した処理ノードの可能なスケジュールを示す図
【図２８】図２３に示す割付リソースＲ+6に対応した処理ノードの可能なスケジュールを示す図
【図２９】図２３に示す割付リソースＲ+1/5とＲ+6を共有化した場合に可能なスケジュールを示す図
【図３０】図２３に示す割付リソースＲ+4/7とＲ+3を共有化した場合に可能なスケジュールを示す図
【図３１】図２３に示す割付リソース接続グラフについて、図２２に示す共有化枝生成工程で付加される共有化枝の重みを示す図
【図３２】図２３に示す割付リソース接続グラフについて、図３１に示す種類の共有化枝を追加した割付リソース接続グラフを示す図
【図３３】あるＣＤＦＧについてのチェイニングされた処理ノードを含むアロケーションスケジュールとスケジュール変更可能範囲を示す図
【図３４】図３４に示すＣＤＦＧに対応した割付リソース接続グラフを示す図
【図３５】本発明の第１の実施形態の第４変形例に係る高位合成方法を示すフローチャート
【図３６】図３５に示す引力共有化枝重み調整工程の詳細を示すフローチャート
【図３７】１次隣接節点および２次以内隣接節点を説明するために、ノードの配置結果を示す図
【図３８】図３７に示すノードの配置結果にダミーノードを追加した結果を示す図
【図３９】図２に示すＣＤＦＧについて、処理ノードＮ+3、Ｎ+5の出力値のライフタイムが重なる様子を示す図
【図４０】図２に示すＣＤＦＧについて、処理ノードＮ+4、Ｎ+5の出力値のライフタイムが重なる様子を示す図
【図４１】本発明の第２の実施形態に係る高位合成方法を示すフローチャート
【図４２】図４１に示す引力共有化枝間引き工程の詳細を示すフローチャート
【図４３】図４１に示す逐次改良型リソース共有化工程の詳細を示すフローチャート
【図４４】従来の高位合成方法を示すフローチャート
【符号の説明】
【０１７９】
Ｓ１０１、Ｓ２０１…ＣＤＦＧ生成工程
Ｓ１０２、Ｓ２０２…初期アロケーションスケジューリング工程
Ｓ１０３…共有化枝生成工程
Ｓ１０４…スケジューリング付きリソース配置工程
Ｓ１０５…リソース共有化工程
Ｓ１１１…スケジュール変更可能範囲計算工程
Ｓ１１２…重み計算工程
Ｓ１１３…重み付き共有化枝生成工程
Ｓ１２１、Ｓ２２１…終了判定工程
Ｓ１２２…共有化枝再生成工程
Ｓ１３１…引力共有化枝重み調整工程
Ｓ１４１、Ｓ２１１…レイアウト困難度評価工程
Ｓ１４２、Ｓ２２２…引力共有化枝選択工程
Ｓ１４３…引力共有化枝重み削減工程
Ｓ２０３、Ｓ２２５…引力共有化枝生成工程
Ｓ２０４…引力共有化枝間引き工程
Ｓ２０５…リソース配置工程
Ｓ２０６…逐次改良型リソース共有化工程
Ｓ２１３…引力共有化枝削除工程
Ｓ２２２…共有化対象選択工程
Ｓ２２３…選択判定工程
Ｓ２２４…被選択リソース共有化工程
Ｓ２２６…レイアウト結果修正工程
【図１】
2006011878.tif 000007
【図２】
2006011878.tif 000008
【図３】
2006011878.tif 000009
【図４】
2006011878.tif 000010
【図５】
2006011878.tif 000011
【図６】
2006011878.tif 000012
【図７】
2006011878.tif 000013
【図８】
2006011878.tif 000014
【図９】
2006011878.tif 000015
【図１０】
2006011878.tif 000016
【図１１】
2006011878.tif 000017
【図１２】
2006011878.tif 000018
【図１３】
2006011878.tif 000019
【図１４】
2006011878.tif 000020
【図１５】
2006011878.tif 000021
【図１６】
2006011878.tif 000022
【図１７】
2006011878.tif 000023
【図１８】
2006011878.tif 000024
【図１９】
2006011878.tif 000025
【図２０】
2006011878.tif 000026
【図２１】
2006011878.tif 000027
【図２２】
2006011878.tif 000028
【図２３】
2006011878.tif 000029
【図２４】
2006011878.tif 000030
【図２５】
2006011878.tif 000031
【図２６】
2006011878.tif 000032
【図２７】
2006011878.tif 000033
【図２８】
2006011878.tif 000034
【図２９】
2006011878.tif 000035
【図３０】
2006011878.tif 000036
【図３１】
2006011878.tif 000037
【図３２】
2006011878.tif 000038
【図３３】
2006011878.tif 000039
【図３４】
2006011878.tif 000040
【図３５】
2006011878.tif 000041
【図３６】
2006011878.tif 000042
【図３７】
2006011878.tif 000043
【図３８】
2006011878.tif 000044
【図３９】
2006011878.tif 000045
【図４０】
2006011878.tif 000046
【図４１】
2006011878.tif 000047
【図４２】
2006011878.tif 000048
【図４３】
2006011878.tif 000049
【図４４】
2006011878.tif 000050