(57)【要約】【課題】高位合成におけるハードウェアリソース共有化において、共有化によって発生する通常は活性化しないパス（フォールスパス）のうちフォールスループやロングフォールスパスを発生させないで高い共有化率を実現する。【解決手段】スケジューリング結果に基づいてリソースの接続情報からデータパスグラフを生成し、リソースのライフタイムを計算し、同一のリソースで実行可能なデータパスグラフ内のリソース組に共有化エッジを張り、共有化グラフを生成し、共有化することで発生する活性化しないデータパスグラフ内の経路が閉路にならないように共有化エッジを削除し、共有化エッジを評価式で評価し、共有化対象となるリソース組を１つ選択するか否かを決定し、決定されたリソース組を共有化し、データパスグラフを変形し、各リソースのライフタイムを更新し、ライフタイムがオーバーラップしているリソース組間の共有化エッジを削除した上でリソース組決定へ戻る。【選択図】図１
2008186126.tif 000002
【特許請求の範囲】
【請求項１】
動作レベル記述からレジスタ転送レベル記述を生成する高位合成方法において、同一のハードウェアリソースで実行可能な動作レベル回路内の処理を共有化するハードウェアリソース共有化方法であって、
動作レベルにおける処理をハードウェアリソースに割り付けてスケジューリングされた結果に基づいて、前記ハードウェアリソースの接続情報からデータパスグラフを生成するデータパスグラフ生成ステップと、
前記スケジューリング結果から得られる前記ハードウェアリソースのライフタイムを計算し、同一のハードウェアリソースで実行可能な前記データパスグラフ内のハードウェアリソース組に共有化エッジを張り、共有化グラフを生成する共有化グラフ生成ステップと、
共有化することで発生する活性化しないデータパスグラフ内の経路が閉路にならないように共有化エッジを削除する閉路防止用の共有化エッジ削除ステップと、
前記共有化エッジを評価式で評価し、同評価値に基づいて、共有化対象となるハードウェアリソース組を１つ選択するか、共有化対象がないとしてハードウェアリソース共有化を終了するかを決定するハードウェアリソース組決定ステップと、
決定された前記ハードウェアリソース組を共有化し、前記データパスグラフを変形する共有化ステップと、
変形された前記データパスグラフの各ハードウェアリソースのライフタイムを更新し、前記ライフタイムがオーバーラップしているハードウェアリソース組間の共有化エッジを削除した上で、前記ハードウェアリソース組決定ステップへ戻るライフタイムオーバーラップ防止用の共有化エッジ削除ステップとを含む高位合成におけるハードウェアリソース共有化方法。
【請求項２】
前記閉路防止用の共有化エッジ削除ステップは、
前記データパスグラフ内のレジスタリソースから信号伝播方向へたどった場合の段数を計算する深さ探索ステップと、
両端が異なる段数のノードでかつ、両端のいずれかの出力が前記レジスタリソースに繋がっているリソースでない共有化エッジを削除する異深さ共有化エッジ削除ステップとを含む請求項１に記載のハードウェアリソース共有化方法。
【請求項３】
前記閉路防止用の共有化エッジ削除ステップは、
前記データパスグラフ内のレジスタリソースから信号伝播方向から逆にたどった場合の段数を計算する高さ探索ステップと、
両端が異なる段数のノードでかつ、両端のいずれかの入力が前記レジスタリソースに繋がっているリソースでない共有化エッジを削除する異高さ共有化エッジ削除ステップとを含む請求項１に記載のハードウェアリソース共有化方法。
【請求項４】
前記ハードウェアリソース組決定ステップは、
前記共有化することで発生する活性化しないデータパスグラフ内経路の遅延時間があらかじめ定義された時間を超える場合は、その原因となった共有化エッジを削除する長経路防止用共有化エッジ削除ステップと、
残されたすべての共有化エッジに対し、共有化で挿入される選択リソースを含んだ共有化前後の面積変化量を求め、共有化後の面積が増加する場合は、無効な共有化エッジとして選択対象から除外する共有化前後面積評価ステップと、
選択対象がない場合はハードウェアリソース共有化を終了し、選択対象がある場合は面積減少量が最大の共有化エッジを選択し、その両端のハードウェアリソースを共有化するハードウェアリソース組とする面積指向の共有化エッジ選択ステップとを含む請求項１に記載のハードウェアリソース共有化方法。
【請求項５】
前記面積指向の共有化エッジ選択ステップは、面積減少量が最大値となる共有化エッジが複数ある場合に、共有化後にハードウェアリソースのライフタイムのオーバーラップにより共有化不可となる共有化エッジの発生率が複数の共有化エッジで最も低い共有化エッジの両端を共有化するハードウェアリソース組とする請求項４に記載のハードウェアリソース共有化方法。
【請求項６】
前記面積指向の共有化エッジ選択ステップは、面積減少量が最大値となる共有化エッジが複数ある場合に、共有化後にフォールスパスを含んだレジスタリソース間パス遅延の増加率が複数の共有化エッジで最も低い共有化エッジの両端を共有化するハードウェアリソース組とする請求項４に記載のハードウェアリソース共有化方法。
【請求項７】
前記面積指向の共有化エッジ選択ステップは、面積減少量が最大値となる共有化エッジが複数ある場合に、共有化後にハードウェアリソースのライフタイムのオーバーラップにより共有化不可となる共有化エッジの発生しない率と、共有化後にフォールスパスを含んだレジスタリソース間パス遅延の増加率を１から減じた値との線形和で表現された値が複数の共有化エッジで最も大きい共有化エッジの両端を共有化するハードウェアリソース組とする請求項４に記載のハードウェアリソース共有化方法。
【請求項８】
前記ハードウェアリソース組決定ステップは、
残されたすべての共有化エッジに対し、共有化前ハードウェアリソース面積から、共有化で挿入された選択リソースを含んだ共有化後ハードウェアリソース面積を減じた値と、あらかじめ定義された時間から共有化後のフォールスパスを減じた値を計算し、いずれかの値が負の値になる共有化エッジは無効な共有化エッジとして選択対象から除外する共有化前後面積遅延評価ステップと、
選択対象がない場合はハードウェアリソース共有化を終了し、選択対象がある場合は前記２つの値の線形和が最大の共有化エッジを選択することで、共有化するハードウェアリソース組を決定する面積・遅延指向の共有化エッジ選択ステップとを含む請求項１に記載のハードウェアリソース共有化方法。
【請求項９】
前記面積・遅延指向の共有化エッジ選択ステップは、評価値が最大値となる共有化エッジが複数ある場合に、共有化後にハードウェアリソースのライフタイムのオーバーラップにより共有化不可となる共有化エッジの発生率が複数の共有化エッジで最も低い共有化エッジの両端を共有化するハードウェアリソース組とする請求項８に記載のハードウェアリソース共有化方法。
【請求項１０】
前記面積・遅延指向の共有化エッジ選択ステップは、評価値が最大値となる共有化エッジが複数ある場合に、共有化後にフォールスパスを含んだレジスタリソース間パス遅延の増加率が複数の共有化エッジで最も低い共有化エッジの両端を共有化するハードウェアリソース組とする請求項８に記載のハードウェアリソース共有化方法。
【請求項１１】
前記面積・遅延指向の共有化エッジ選択ステップは、評価値が最大値となる共有化エッジが複数ある場合に、共有化後にハードウェアリソースのライフタイムのオーバーラップにより共有化不可となる共有化エッジの発生しない率と、共有化後にフォールスパスを含んだレジスタリソース間パス遅延の増加率を１から減じた値との線形和で表現された値が複数の共有化エッジで最も大きい共有化エッジの両端を共有化するハードウェアリソース組とする請求項８に記載のハードウェアリソース共有化方法。
【請求項１２】
前記ハードウェアリソース組決定ステップは、
終了条件に合致した場合に処理を終了し、合致しない場合は、すべての共有化エッジからランダムに１つ共有化エッジを選択するランダム選択ステップと、
選択された共有化エッジの共有化で挿入される選択リソースを含んだ共有化前後のリソース面積を目的関数として、組合せ最適化手法で共有化可否を決定し、共有化は否と決定した場合は、終了条件を判定するステップに戻り、共有化は可と決定した場合は、その両端のハードウェアリソースを共有化するハードウェアリソースとする共有化可否決定ステップとを含む請求項１に記載のハードウェアリソース共有化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回路の動作レベル記述を入力としてレジスタ転送レベル記述を出力する高位合成におけるハードウェアリソース共有化方法に関する。
【背景技術】
【０００２】
社会の高度情報化とそれを支える情報技術の進展に伴い、電子機器における情報処理機能は飛躍的に増大しており、そこでは、大規模集積回路が中心的な役割を果たしている。大規模集積回路をより少ない作業で短期間に設計するための設計技術として、より抽象性を高めた高位レベルの設計情報から、ソフトウェア支援による回路合成を行う技術の研究開発が進められている。回路合成技術の１つとして、動作レベルからレジスタ転送レベルを生成する高位合成技術が非特許文献１等で提案されている。動作レベルでは、回路の入力から出力までの処理内容だけが定義され、処理にかかる時間（サイクル数）までは定義されていない。一方、レジスタ転送レベルでは、回路のレジスタが確定しているため、処理にかかる時間（サイクル数）までが定義されている。
【０００３】
図１２は従来の高位合成技術の処理フローを示す。この処理フローは、
Ｃ／Ｃ＋＋等の高級言語で記述された動作レベル記述からデータと制御を解析して、ＣＤＦＧ（Control Data Flow Graph）を生成するＣＤＦＧ生成ステップＮ１と、
あらかじめ用意された、処理を実際に行うハードウェア回路（以降、演算リソース）をＣＤＦＧの各処理ノードに割り付けるリソース割付ステップＮ２と、
設定された生成したいレジスタ転送レベル回路の動作クロック周期と、ＣＤＦＧの処理ノードに割り付けられた演算リソースの遅延値とを用いて処理順序を決定することにより、ＣＤＦＧの各処理ノードが実行される制御サイクルを決定するスケジューリングステップＮ３と、
制御サイクルをまたぐ信号に対して、データ保持用のレジスタリソースを挿入するレジスタ割付ステップＮ４と、
スケジューリング結果から解析できるライフタイム（リソースが処理を行っている制御サイクル）がオーバーラップしない同一演算リソースで処理可能なリソース（演算リソースまたはレジスタリソース）同士を共有化するリソース共有化ステップＮ５と、
ＣＤＦＧの各ノードに割り付けられたリソース情報から、ＨＤＬ（Hardware Description Language）で記述されたレジスタ転送レベル（ＲＴＬ）記述を生成するレジスタ転送レベル記述生成ステップＮ６から構成されている。
【０００４】
次に、従来技術の処理フローである図１２に沿って、Ｃ言語を用いて記述した動作レベル回路（図１３）からレジスタ転送レベル回路を生成する流れを説明する。
【０００５】
まず、ステップＮ１で、図１３の動作モデルから図１４に示したＣＤＦＧ（コントロールデータフローグラフ）を生成する。
【０００６】
次に、ステップＮ２で、ＣＤＦＧの各ノードに演算リソースを割り付け、割付マップ情報を生成する。
【０００７】
次に、ステップＮ３で、割付マップ情報からＣＤＦＧの各ノードの遅延値を計算し、あらかじめ設定されたクロック周期に基づいて、実行する制御サイクルを決定する。
【０００８】
次に、ステップＮ４で、制御サイクルをまたぐ信号に対して、データ保持用のレジスタリソースを挿入する。
【０００９】
図１５は、ステップＮ３、ステップＮ４により図１４のＣＤＦＧ内の各ノードを制御サイクルに割り付け、データ保持用レジスタリソースｒ１〜ｒ７を挿入した状態を示した図である。図１５では、図１４のｖｏ１〜ｖｏ９がそれぞれａ１〜ａ９に割り付き、ｖｓ１，ｖｓ３，ｖｓ５，ｖｓ７，ｖｓ８，ｖｓ９，ｖｓ１０がそれぞれｒ１〜ｒ７に割り付いている。なお、図１４のｖｓ２，ｖｓ４，ｖｓ６は、図１５ではぞれぞれ、ａ１，ａ２間、ａ３，ａ４間、ａ５，ａ６間の配線となっており、さらにｖｃ１〜ｖｃ９までの定数ノードは省略している。
【００１０】
ステップＮ５で、ライフタイムがオーバーラップしない同一演算リソースで処理可能なリソース組を共有化する。リソース組を共有化したことで、リソースへの入力信号を制御サイクルに応じて選択する必要が出た場合には、自動的に、選択リソースＭＵＸが挿入される。図１６は共有化後のリソース接続（データパス）に入力データ選択用の選択リソースＭＵＸが挿入される場合の一例を示した図である。
【００１１】
ステップＮ６で、リソース接続情報と各リソースが実行される制御サイクルの情報から、選択リソースＭＵＸへの制御信号を供給する制御回路を生成し、その制御回路とリソース間を接続したデータパス回路とを、ＨＤＬを用いたレジスタ転送レベル記述として生成する。
【００１２】
ステップＮ５のリソース共有化により、
１）実動作では活性化しないリソース（演算リソースまたは選択リソース）間の接続経路（フォールスパス）の生成
２）共有化されたリソースの入力に挿入される選択リソースの挿入
が引き起こされる。
【００１３】
図１６においては、レジスタＩｒ１，Ｉｒ６間に存在する、Ｉｒ１→Ｉｍ２→Ｉａ１→Ｉｍ４→Ｉａ２→Ｉｍ７→Ｉａ３→Ｉｍ９→Ｉａ４→Ｉｒ６という経路等のフォールスパスが生成され、２信号から１つを選択する選択リソースＭＵＸが６つ、３信号から１つを選択する選択リソースＭＵＸが３つ挿入されている。
【００１４】
以上の２点により、高位合成で生成されたレジスタ転送レベル回路は、次のような問題を引き起こす。
【００１５】
１）共有化されることで削減されたリソース面積より、挿入された選択リソースＭＵＸの面積の方が大きくなり、共有化により面積が増加してしまう場合がある。
【００１６】
２）組合せ回路（演算リソースまたは選択リソース）のみで構成されたループ（この経路はフォールスパスであり、以降、フォールスループと呼ぶ）が発生する。組合せ回路のみのループは信号の発振を引き起こすおそれがあり、回路動作を不安定にさせる可能性がある.
図１６においては、Ｉａ２→Ｉｍ７→Ｉａ３→Ｉｍ４→Ｉａ２がフォールスループに当たる。
【００１７】
３）組合せ回路のみで構成されたフォールスパスの遅延がクロック周期を超えてしまう（以降、このパスをロングフォールスパスと呼ぶ）。
【００１８】
以上で述べた問題を解決する方法として、特許文献１に開示の技術がある。これは、１回のリソース共有化を行う毎に、選択リソースＭＵＸを考慮して、面積が減少しているか、あるいは、フォールスループ／ロングフォールスパスが発生するかを事前に確認し、発生しない場合のみリソース共有化（同じリソースへの割り付け）を行う方法である。
【非特許文献１】High-Level Synthesis: Introduction toChip and System Design, Daniel D. Gajski ,Kluwer Academic Pub (1992/04)
【特許文献１】特開２００３−７６７２８号公報（第７−１４頁、第１６−４０図）
【発明の開示】
【発明が解決しようとする課題】
【００１９】
特許文献１の方法では、選択リソースＭＵＸが挿入されることで逆に面積が増加したり、フォールスループ／ロングフォールスパスが発生したりすることは抑制される。しかし、共有化対象となるリソースの選択方法が、リソース面積の大きいものから順に行うといった単純なものであるため、リソース共有化自体がそれほど進まずに、最終的に生成されるレジスタ転送レベル回路の面積が大きなものになってしまう可能性がある。
【００２０】
本発明は、このような事情に鑑みて創作したものであり、共有化で問題となる活性しないパス（フォールスループ／ロングフォールスパス）の発生を抑制しつつ、共有化率の増大を促進し、最終的に得られるレジスタ転送レベル回路の選択リソースを含んだ面積を小さくすることができるハードウェアリソース共有化方法を提供することを目的としている。
【課題を解決するための手段】
【００２１】
（１）本発明のハードウェアリソース共有化方法は、
動作レベル記述からレジスタ転送レベル記述を生成する高位合成方法において、同一のハードウェアリソースで実行可能な動作レベル回路内の処理を共有化するハードウェアリソース共有化方法であって、
動作レベルにおける処理をハードウェアリソースに割り付けてスケジューリングされた結果に基づいて、前記ハードウェアリソースの接続情報からデータパスグラフを生成するデータパスグラフ生成ステップと、
前記スケジューリング結果から得られる前記ハードウェアリソースのライフタイムを計算し、同一のハードウェアリソースで実行可能な前記データパスグラフ内のハードウェアリソース組に共有化エッジを張り、共有化グラフを生成する共有化グラフ生成ステップと、
共有化することで発生する活性化しないデータパスグラフ内の経路が閉路にならないように共有化エッジを削除する閉路防止用の共有化エッジ削除ステップと、
前記共有化エッジを評価式で評価し、同評価値に基づいて、共有化対象となるハードウェアリソース組を１つ選択するか、共有化対象がないとしてハードウェアリソース共有化を終了するかを決定するハードウェアリソース組決定ステップと、
決定された前記ハードウェアリソース組を共有化し、前記データパスグラフを変形する共有化ステップと、
変形された前記データパスグラフの各ハードウェアリソースのライフタイムを更新し、前記ライフタイムがオーバーラップしているハードウェアリソース組間の共有化エッジを削除した上で、前記ハードウェアリソース組決定ステップへ戻るライフタイムオーバーラップ防止用の共有化エッジ削除ステップとを含むものである。
【００２２】
上記の構成においては、すべての共有化可能なハードウェアリース間に共有化エッジを張った後、フォールスパスで問題になるものが発生しないように共有化エッジを削除する。残った共有化エッジに対して共有化効率を考慮した評価式を用いて評価し、評価値が高い共有化エッジにつながったハードウェアリソースから順番に共有化を行う。
【００２３】
すなわち、共有化対象のハードウェアリソース組の選択を行う前に、共有化すれば発振要因の閉路となってしまうような共有化エッジをあらかじめ除去するので、ハードウェアリソース組の共有化の処理の過程でフォールスループが生じることを未然に回避することが可能となる。そして、ハードウェアリソース組の共有化の過程では、共有化エッジの評価値を用いながら、逐一、ハードウェアリソース組の選択を行い、共有化してデータパスグラフを変形し、ライフタイムがオーバーラップした共有化エッジを削除するという一連の処理を繰り返すので、ロングフォールスパスの発生も確実に抑制することが可能となる。すなわち、フォールスループおよびロングフォールスパスの発生を抑制しながら、リソース共有化率を高め、少ないリソース数の面積の小さいレジスタ転送レベル回路を生成することが可能となる。
【００２４】
（２）上記のハードウェアリソース共有化方法において、前記閉路防止用の共有化エッジ削除ステップは、前記データパスグラフ内のレジスタリソースから信号伝播方向へたどった場合の段数を計算する深さ探索ステップと、両端が異なる段数のノードでかつ、両端のいずれかの出力が前記レジスタリソースに繋がっているリソースでない共有化エッジを削除する異深さ共有化エッジ削除ステップとを含むという態様がある。このように構成すれば、残されたどの共有化エッジに基づいてリソース共有化しても、フォールスループは発生しないようになる。しかも、少ない計算量で、かつ、一度だけ計算することでフォールスループの発生を抑制することが可能となる。
【００２５】
（３）また上記のハードウェアリソース共有化方法において、前記閉路防止用の共有化エッジ削除ステップは、前記データパスグラフ内のレジスタリソースから信号伝播方向から逆にたどった場合の段数を計算する高さ探索ステップと、両端が異なる段数のノードでかつ、両端のいずれかの入力が前記レジスタリソースに繋がっているリソースでない共有化エッジを削除する異高さ共有化エッジ削除ステップとを含むという態様がある。この場合も、上記（２）と同様に、残されたどの共有化エッジに基づいてリソース共有化しても、フォールスループは発生しないようになる。しかも、少ない計算量で、かつ、一度だけ計算することでフォールスループの発生を抑制することが可能となる。
【００２６】
（４）また上記のハードウェアリソース共有化方法において、前記ハードウェアリソース組決定ステップは、前記共有化することで発生する活性化しないデータパスグラフ内経路の遅延時間があらかじめ定義された時間を超える場合は、その原因となった共有化エッジを削除する長経路防止用共有化エッジ削除ステップと、
残されたすべての共有化エッジに対し、共有化で挿入される選択リソースを含んだ共有化前後の面積変化量を求め、共有化後の面積が増加する場合は、無効な共有化エッジとして選択対象から除外する共有化前後面積評価ステップと、
選択対象がない場合はハードウェアリソース共有化を終了し、選択対象がある場合は面積減少量が最大の共有化エッジを選択し、その両端のハードウェアリソースを共有化するハードウェアリソース組とする面積指向の共有化エッジ選択ステップとを含むという態様がある。
【００２７】
このように構成すれば、ハードウェアリソース組の選択が合理的に行われる。
【００２８】
以下の（５）〜（７）は、上記（４）における面積指向の共有化エッジ選択ステップについての具体的態様である。
【００２９】
（５）上記のハードウェアリソース共有化方法において、前記面積指向の共有化エッジ選択ステップは、面積減少量が最大値となる共有化エッジが複数ある場合に、共有化後にハードウェアリソースのライフタイムのオーバーラップにより共有化不可となる共有化エッジの発生率が複数の共有化エッジで最も低い共有化エッジの両端を共有化するハードウェアリソース組とするという態様がある。このように構成すれば、ライフタイムのオーバーラップにより削除される共有化エッジ数をできるだけ少なくして、共有化エッジ数をより多く残すので、より多くのリソース組が共有化され、最終的に得られるレジスタ転送レベル回路の面積を、（４）の場合に比べて、より小さなものにすることが可能となる。
【００３０】
（６）また上記のハードウェアリソース共有化方法において、前記面積指向の共有化エッジ選択ステップは、面積減少量が最大値となる共有化エッジが複数ある場合に、共有化後にフォールスパスを含んだレジスタリソース間パス遅延の増加率が複数の共有化エッジで最も低い共有化エッジの両端を共有化するハードウェアリソース組とするという態様がある。このように構成すれば、ロングフォールスパスが原因で削除される共有化エッジ数をできるだけ少なくして、共有化エッジ数をより多く残すので、より多くのリソース組が共有化され、最終的に得られるレジスタ転送レベル回路の面積を、（４）の場合に比べて、より小さなものにすることが可能となる。
【００３１】
（７）また上記のハードウェアリソース共有化方法において、前記面積指向の共有化エッジ選択ステップは、面積減少量が最大値となる共有化エッジが複数ある場合に、共有化後にハードウェアリソースのライフタイムのオーバーラップにより共有化不可となる共有化エッジの発生しない率と、共有化後にフォールスパスを含んだレジスタリソース間パス遅延の増加率を１から減じた値との線形和で表現された値が複数の共有化エッジで最も大きい共有化エッジの両端を共有化するハードウェアリソース組とするという態様がある。このように構成すれば、上記の（５）と（６）の組み合わせであり、ハードウェアリソース組の選択をより高精度に行うことが可能となる。
【００３２】
（８）また上記のハードウェアリソース共有化方法において、前記ハードウェアリソース組決定ステップは、残されたすべての共有化エッジに対し、共有化前ハードウェアリソース面積から、共有化で挿入された選択リソースを含んだ共有化後ハードウェアリソース面積を減じた値と、あらかじめ定義された時間から共有化後のフォールスパスを減じた値を計算し、いずれかの値が負の値になる共有化エッジは無効な共有化エッジとして選択対象から除外する共有化前後面積遅延評価ステップと、選択対象がない場合はハードウェアリソース共有化を終了し、選択対象がある場合は前記２つの値の線形和が最大の共有化エッジを選択することで、共有化するハードウェアリソース組を決定する面積・遅延指向の共有化エッジ選択ステップとを含むという態様がある。
【００３３】
このように構成すれば、面積関係と遅延関係の双方でハードウェアリソース組を選択することになるので、ハードウェアリソース組の選択をさらに高精度に行うことが可能となる。すなわち、ハードウェアリソース組の共有化が進む過程で選択リソースの数は増減するため、ある状態でロングフォールスパスになる共有化エッジが、選択リソース数が減少したときにロングフォールスパスでなくなる場合がある。このような場合おいても、ロングフォールスパスになる共有化エッジを削除するのではなく、評価値として表現しているため、共有化が可能となり、より多くのリソース組が共有化され、最終的に得られるレジスタ転送レベル回路の面積がより小さくなる。
【００３４】
以下の（９）〜（１１）は、上記（８）における面積・遅延指向の共有化エッジ選択ステップについての具体的態様である。
【００３５】
（９）上記のハードウェアリソース共有化方法において、前記面積・遅延指向の共有化エッジ選択ステップは、評価値が最大値となる共有化エッジが複数ある場合に、共有化後にハードウェアリソースのライフタイムのオーバーラップにより共有化不可となる共有化エッジの発生率が複数の共有化エッジで最も低い共有化エッジの両端を共有化するハードウェアリソース組とするという態様がある。“面積指向”を除けは、上記（５）と同じ内容である。このように構成すれば、ライフタイムのオーバーラップにより削除される共有化エッジ数をできるだけ少なくして、共有化エッジ数をより多く残すので、より多くのリソース組が共有化され、最終的に得られるレジスタ転送レベル回路の面積を、（８）の場合に比べて、より小さなものにすることが可能となる。
【００３６】
（１０）また上記のハードウェアリソース共有化方法において、前記面積・遅延指向の共有化エッジ選択ステップは、評価値が最大値となる共有化エッジが複数ある場合に、共有化後にフォールスパスを含んだレジスタリソース間パス遅延の増加率が複数の共有化エッジで最も低い共有化エッジの両端を共有化するハードウェアリソース組とするという態様がある。“面積指向”を除けは、上記（６）と同じ内容である。このように構成すれば、ロングフォールスパスが原因で削除される共有化エッジ数をできるだけ少なくして、共有化エッジ数をより多く残すので、より多くのリソース組が共有化され、最終的に得られるレジスタ転送レベル回路の面積を、（８）の場合に比べて、より小さなものにすることが可能となる。
【００３７】
（１１）また上記のハードウェアリソース共有化方法において、前記面積・遅延指向の共有化エッジ選択ステップは、評価値が最大値となる共有化エッジが複数ある場合に、共有化後にハードウェアリソースのライフタイムのオーバーラップにより共有化不可となる共有化エッジの発生しない率と、共有化後にフォールスパスを含んだレジスタリソース間パス遅延の増加率を１から減じた値との線形和で表現された値が複数の共有化エッジで最も大きい共有化エッジの両端を共有化するハードウェアリソース組とするという態様がある。“面積指向”を除けは、上記（７）と同じ内容である。このように構成すれば、上記の（９）と（１０）の組み合わせであり、ハードウェアリソース組の選択をより高精度に行うことが可能となる。
【００３８】
（１２）また上記のハードウェアリソース共有化方法において、前記ハードウェアリソース組決定ステップは、
終了条件に合致した場合に処理を終了し、合致しない場合は、すべての共有化エッジからランダムに１つ共有化エッジを選択するランダム選択ステップと、
選択された共有化エッジの共有化で挿入される選択リソースを含んだ共有化前後のリソース面積を目的関数として、組合せ最適化手法で共有化可否を決定し、共有化は否と決定した場合は、終了条件を判定するステップに戻り、共有化は可と決定した場合は、その両端のハードウェアリソースを共有化するハードウェアリソースとする共有化可否決定ステップとを含むという態様がある。このように構成すれば、目的関数を用いた組合せ最適化手法を用いることで、一時的に目的関数が増加するような共有化エッジによる共有化も実施されることになり、解の探索範囲が広がることで、ローカル解での共有化処理終了が回避される。目的関数をリソース面積の総和とすることで、最終的に得られるレジスタ転送レベル回路の面積がより小さなものになる。
【発明の効果】
【００３９】
本発明によれば、高位合成におけるハードウェアリソース共有化方法において、共有化時に発生する活性化しないパスのうち、組合せ回路のみでループを構成するパス（フォールスループ）とクロック周期等のあらかじめ設定された時間よりパス遅延が長くなるパス（ロングフォールスパス）の発生を抑制し、かつ、高い共有化率を実現することができるため、共有化時に挿入される選択リソースを含んだリソース面積が小さなレジスタ転送レベル回路を簡単に生成することができる。
【発明を実施するための最良の形態】
【００４０】
以下、本発明にかかわる高位合成におけるハードウェアリソース共有化方法の実施の形態を図面を用いて詳細に説明する。
【００４１】
（実施の形態１）
図１は本発明の実施の形態１におけるハードウェアリソース共有化方法を含んだ高位合成の処理順序を示すフローチャートであり、従来技術で説明したステップであるステップＮ１〜Ｎ４，Ｎ６に加えて、
割り付けられたリソース間でやり取りが必要なデータ信号の情報から、リソース接続情報であるデータパスグラフ（ＤＰＧ）を生成するステップＳ１０と、
ライフタイムがオーバーラップしない同種リソース間に共有化エッジをデータパスグラフに追加したリソース共有化グラフを生成するステップＳ２０と、
フォールスループを発生させる可能性がある共有化エッジをリソース共有化グラフから削除するステップＳ３０と、
ロングフォールスパスを発生させる共有化エッジをリソース共有化グラフから削除するステップＳ４０と、
定義された計算式に基づいて、リソース共有化グラフ内の共有化エッジの評価値を計算するステップＳ５０と、
リソース共有化グラフ内に有効な共有化エッジがあるかを判定し、ある場合はステップＳ７０へ処理を進め、ない場合はステップＮ６へ処理を進めるステップＳ６０と、
共有化エッジの評価値に基づいて、共有化するリソースを決定する選択ステップＳ７０と、
選択されたリソース組を共有化し、データパスグラフを更新するステップＳ８０と、
更新されたデータパスグラフに基づいて、共有化グラフを更新し、ステップＳ４０へ戻るステップＳ９０とを有している。
【００４２】
まとめると、
Ｎ１：ＣＤＦＧ生成ステップ
Ｎ２：リソース割付ステップ
Ｎ３：スケジューリングステップ
Ｎ４：レジスタ割付ステップ
Ｓ１０：データパスグラフ生成ステップ
Ｓ２０：共有化グラフ生成ステップ
Ｓ３０：閉路防止用の共有化エッジ削除ステップ（フォールスループ抑制）
Ｓ４０：ライフタイムオーバーラップ防止用の共有化エッジ削除ステップ（ロングフォールスパス抑制）
Ｓ５０：ハードウェアリソース組決定ステップ（共有化エッジの評価値計算）
Ｓ６０：ハードウェアリソース組決定ステップ（有効共有化エッジの判定）
Ｓ７０：ハードウェアリソース組決定ステップ（評価値に基づいた共有化エッジ選択）
Ｓ８０：ハードウェアリソース組の共有化ステップ
Ｓ９０：閉路防止用の共有化エッジ削除ステップ（共有化エッジ更新）
Ｎ６：レジスタ転送レベル記述生成ステップ
次に、本実施の形態の高位合成におけるハードウェアリソース共有化方法について、従来技術の説明で用いた動作モデル（図１３）を用いて、図１のフローチャートに即して説明する。
【００４３】
ステップＮ１からステップＮ４までは、従来技術と同様に実行し、図１５に示したリソース接続情報を得る。
【００４４】
ステップＳ１０で、リソース接続情報からデータパスグラフ（ＤＰＧ）を生成する。初期のデータパスグラフは、図１５に示したグラフと同一のものとなる。
【００４５】
ステップＳ２０で、リソース共有化グラフを生成する。図２は図１５から生成した共有化グラフの共有化エッジのみを示した図であり、図２中において、丸印がある箇所はリソース間に共有化エッジがあり、バツ印がある箇所はリソース間に共有化エッジがないことを示している。
【００４６】
ステップＳ３０では、レジスタリソースから信号伝播方向にたどって、レジスタリソースまでのリソースの深さ（段数）を調査する。その後、異なる深さをもったリソース同士の共有化エッジは削除する。だたし、レジスタリソースの直前となるリソース同士の共有化エッジは、削除対象から省く。この削除により、残されたどの共有化エッジに基づいてリソース共有化しても、フォールスループは発生しない。しかも、少ない計算量で、かつ、一度だけ計算することでフォールスループの発生を抑制することができる（フォールスループ抑制）。
【００４７】
なお、ここでは、レジスタからの深さを基点に行う説明をしたが、信号伝播方向の逆にたどって、リソースの高さを基点に削除を行ってもよい。図３は図２に対してフォールスループ用の削除を行った状態を示している。
【００４８】
ステップＳ４０では、共有化エッジの両端のリソースを共有化した場合に必要となる選択リソースＭＵＸの遅延を推定し、選択リソースの遅延を含んだ共有化後のレジスタリソース間パス遅延がクロック周期を超えている場合、その共有化エッジを共有化グラフから削除する。この削除により、残された共有化エッジでリソース共有化しても、ロングフォールスパスは発生しない（ロングフォールスパス抑制）。
【００４９】
ｎ個の信号線から１つの信号線を選択する選択リソースＭＵＸの遅延を推定する場合、２つの信号線から１つの信号線を選択する選択リソースＭＵＸを直列に（ｎ−１）段連結した構成で遅延を推定したり、ツリー状にｌｏｇ（ｎ−１）段を連結した構成で遅延を推定したりすることで、容易に遅延を推定することができる。
【００５０】
ステップＳ５０で、式（１）を用いて、各共有化エッジの面積削減率評価値Ｐａを計算する。
【００５１】
Ｐａ（Ａ，Ｂ）＝Ａrea（Ａ）＋Ａrea（Ｂ）−Ａrea（Ａ，Ｂ）  ………………（１）
ここで、Ａrea（Ａ）はリソースＡの面積とその前後につながる選択リソースＭＵＸの面積の和を示し、Ａrea（Ｂ）はリソースＢの面積とその前後につながる選択リソースＭＵＸの面積の和を示し、Ａrea（Ａ，Ｂ）はリソースＡとリソースＢを共有化した場合の選択リソースＭＵＸを含んだ面積を示している。
【００５２】
面積削減率評価値Ｐａは、共有化前後での面積削減率が大きい程に大きな値になり、共有化で面積が増加する場合は負となる。選択リソースＭＵＸの面積推定方法は、ステップＳ４０で用いた選択リソースの遅延推定方法を用いて、必要となる選択リソースＭＵＸの数から容易に計算することができる。
【００５３】
ステップＳ６０で、ステップ５０での面積削減率評価値Ｐａがゼロ以上の場合は有効な共有化エッジとし、有効な共有化エッジの有無を調査し、ここでは、有効な共有化エッジがあるとし、ステップＳ７０へ進む。
【００５４】
ステップＳ７０で、最大の面積削減率評価値Ｐａをもつ共有化エッジを選択し、その両端のリソースを共有化対象リソース組とする。
【００５５】
ステップＳ８０で、共有化対象リソース組を共有化し、データパスグラフを更新する。図４は図１５のリソース組（ａ８，ａ９）を共有化対象とした場合の共有化後のデータパスグラフを示したものである。
【００５６】
ステップＳ９０で、ステップＳ８０で更新したデータパスグラフに対して、再度、ライフタイム解析を行い、ライフタイムが重なっている共有化エッジを削除することで共有化グラフを更新する。
【００５７】
再び、ステップＳ４０へ戻り、ステップＳ６０で終了が判定されるまで、ステップＳ４０〜ステップＳ９０を繰り返す。
【００５８】
図５はステップＳ６０で終了判定されたときのデータパスグラフの一例を示したもので、（ａ１，ａ３，ａ５），（ａ２，ａ４，ａ６），（ａ７，ａ８，ａ９），（ｒ２，ｒ３），（ｒ４，ｒ５，ｒ６）のリソース組が共有化されている。図５では、ループにはいずれもレジスタが介在していてフォールスループ、ロングフォールスパスが発生せず、少ないリソース数でレジスタ転送レベル回路が生成できている。
【００５９】
以上、説明したように、面積削減率評価値Ｐａが大きい共有化エッジから順次選択されるため、面積削減率が高い共有化が優先され、最終的に得られるレジスタ転送レベル回路の面積は小さいものとなる。
【００６０】
次に、ステップＳ５０で用いた面積削減率評価値Ｐａの最大値が同値の場合の処理について説明する。このような場合は、式（２）に示した共有化エッジ数残存率評価値Ｐｓが大きい共有化エッジを優先的に選択する。
【００６１】
Ｐｓ＝ＮＳｅ（Ａ，Ｂ）／（Ｎｅ（Ａ）＋Ｎｅ（Ｂ））  …………………………（２）
ここで、Ｎｅ（Ａ），Ｎｅ（Ｂ）は、それぞれリソースＡ、リソースＢがもつ有効共有化エッジ数である。また、ＮＳｅ（Ａ，Ｂ）は、リソースＡとリソースＢがもつ有効共有化エッジ数のうち同じリソースへ繋がっている共有化エッジの数である。
【００６２】
図６は共有化エッジ数残存率評価値Ｐｓを用いた場合の共有化エッジの選択方法を説明するための図であり、Ａ，Ｂ，Ｂ’，Ｃ，Ｄ，Ｅ，Ｆ，ＡＢ，ＡＢ’はリソースを示し、破線は共有化エッジを示している。
【００６３】
図６（ａ）の状態からリソースＡ，Ｂ組を共有化する場合は、図６（ｂ）のように、共有化後リソースＡＢは、リソースＤの共有化エッジが残る。一方、リソースＡ，Ｂ’組を共有化する場合は、図６（ｃ）のように、共有化後リソースＡＢ’には共有化エッジが１つも残らない。残った共有化エッジ数が多いほど共有化の可能性が高く、最終的に生成されるレジスタ転送レベル回路の面積が小さくなる。これは、リソースＡとリソースＢを共有化する場合は、リソースＡとリソースＢのライフタイムの論理和が共有化後リソースＡＢのライフタイムになるため、共有化後リソースは、共有化前のどちらか一方のリソースが共有化エッジをもたないリソースとライフタイムがオーバーラップするためである。
【００６４】
もし共有化エッジ数残存率評価値Ｐｓがなければ、リソースＡ，Ｂ間、リソースＡ，Ｂ’間の共有化エッジの面積削減率評価値Ｐａが同値の場合に、共有化後の共有化エッジ数が少ない方のリソースＡ，Ｂ’が共有化対象として選択される可能性がある。しかし、ここでは、共有化エッジ数残存率評価値Ｐｓを用いるので、リソースＡ，Ｂ間の共有化エッジと、リソースＡ，Ｂ’間の共有化エッジとでは、共有化エッジ数残存率評価値Ｐｓは異なる値をもつ。図６の場合の共有化エッジ数残存率評価値Ｐｓは、リソースＡ，Ｂ間共有化エッジが４分の１、リソースＡ，Ｂ’間共有化エッジが３分の０となるので、共有化後に残る共有化エッジ数が多いリソースＡ，Ｂが大きな評価値をもつことになる。その大きい方を選択することで、共有化後の共有化エッジ数が多いリソースＡ，Ｂ組の選択が行われることになる。
【００６５】
以上説明したように、共有化エッジ数残存率評価値Ｐｓを用いると、ライフタイムのオーバーラップにより削除される共有化エッジ数をできるだけ少なくすることから、共有化エッジ数をより多く残しながら、ステップＳ４０〜ステップＳ９０が繰り返されることになる。その結果、より多くのリソース組が共有化され、最終的に得られるレジスタ転送レベル回路の面積がより小さくなる。
【００６６】
あるいは、共有化エッジ数残存率評価値Ｐｓの代わりに、式（３）に示すパス遅延増加率評価値Ｐｐを用いてもよい。
【００６７】
Ｐｐ＝１−｛τ（Ａ，Ｂ）−ＭＡＸ（τ（Ａ），τ（Ｂ））｝／Ｃｐ  …………（３）
ここで、τ（Ａ），τ（Ｂ）は、それぞれリソースＡ、リソースＢを通過するレジスタリソース間パス遅延の最大値、τ（Ａ，Ｂ）はリソースＡ，Ｂ組の共有化後リソースを通過する、フォールスパスを含むレジスタリソース間パス遅延の最大値、Ｃｐはあらかじめ設定したクロック周期である。このパス遅延増加率評価値Ｐｐは、パス遅延の増加率を１から減じた値に相当している。
【００６８】
パス遅延増加率評価値Ｐｐは、フォールスパスを含むレジスタリソース間経路のパス遅延の共有化前後で増加率が小さい場合に大きな値になるため、共有化前後でレジスタリソース間パス遅延の増加率が低いものを優先させる効果がある。ステップＳ８０において、共有化によりクロック周期を超えるフォールスパスをもつ場合は、その共有化を行うための共有化エッジが削除される。そのため、共有化においては、フォールスパスを含んだレジスタリソース間パス遅延は、クロック周期に対してできるだけ小さい方がステップＳ８０で削除される共有化エッジ数が少なくてすむ。
【００６９】
図７（ａ）はパス遅延増加率評価値Ｐｐを用いた場合の共有化エッジの選択方法を説明するための図である。いま、Ａ，Ｂ，Ｃ，Ｄは共有化で着目しているリソース、Ｒ０〜Ｒ７はレジスタ、実線の有向エッジはデータパスの信号パス経路、破線の無向エッジは共有化エッジを表し、その横の数字はパス遅延値である。Ａ，Ｂ，Ｃ，Ｄ，Ｒ０〜Ｒ７、実線でデータパスグラフを表現している。ここで、クロック周期Ｃｐは１００とする。
【００７０】
図７（ａ）において、リソースＡとリソースＣが共有化された場合のフォールスパスを含むレジスタ間パス遅延は、４０（４０と２０のうちの大きい方）と５０（２０と５０のうちの大きい方）の和で９０となる（図７（ｂ））。一方、リソースＡとリソースＤが共有化される場合のフォールスパスを含むレジスタリソース間パス遅延は、２０（２０と１０のうちの大きい方）と５０（５０と３０ののうちの大きい方）の和で７０となる（図７（ｃ））。図７（ｂ）の場合は、リソースＢ、リソースＡＣ組を共有化すると、フォールスパス（を含むレジスタリソース間パス遅延）がクロック周期を超えるため、ステップＳ８０で削除される。図７（ｃ）の場合は削除される共有化エッジが発生しない。
【００７１】
図７（ａ）の場合のパス遅延増加率評価値Ｐｐは、リソースＡ，Ｂ間で１．０、リソースＡ，Ｃ間で０．８、リソースＡ，Ｄ間で１．０となり、リソースＡ、Ｃ間が一番小さな評価値をもつようになる。
【００７２】
ちなみに、リソースＡ，Ｃ間の場合は、式（３）に当てはめて、
Ｐｐ＝１−（９０−７０）／１００＝０．８
また、リソースＡ，Ｄ間の場合は、
Ｐｐ＝１−（７０−７０）／１００＝１．０
である。
【００７３】
以上説明したように、パス遅延増加率評価値Ｐｐを用いると、ロングフォールスパスが原因で削除される共有化エッジ数をできるだけ少なくするために、共有化エッジ数をより多く残しながら、ステップＳ４０〜ステップＳ９０が繰り返される。その結果、より多くのリソース組が共有化され、最終的に得られるレジスタ転送レベル回路の面積がより小さくなる。
【００７４】
あるいは、共有化エッジ数残存率評価値Ｐｓやパス遅延増加率評価値Ｐｐを単独で用いる代わりに、式（４）に示すように、共有化エッジ数残存率評価値Ｐｓとパス遅延増加率評価値Ｐｐを組み合わせて用いてもよい。
【００７５】
Ｐｓｐ＝α×｛ＮＳｅ（Ａ，Ｂ）／（Ｎｅ（Ａ）＋Ｎｅ（Ｂ））｝
＋β×［１−｛τ（Ａ，Ｂ）−ＭＡＸ（τ（Ａ），τ（Ｂ））｝／Ｃｐ］
＝α×Ｐｓ＋β×Ｐｐ  ………………………………………………………（４）
ここで、α，βは実験等で決定したり、入力された動作モデル毎に設定したりする定数である。α，βの値を調整することで、式（２）、式（３）の効果をバランス良く用いたり、どちらか一方のみを用いたりと、使い分けが可能で、入力された動作モデルに応じて最適化の方法を調整することが可能となる。その結果、入力された動作モデルに調整されたリソース共有化方法を実現でき、最終的に得られるレジスタ転送レベル回路の面積がより小さくなる。
【００７６】
（実施の形態２）
本発明の実施の形態２は、ロングフォールスパスを評価式にした場合のものである。図８は本発明の実施の形態２における、ハードウェアリソース共有化方法を含んだ高位合成の処理順序を示すフローチャートであり、実施の形態１で説明したステップであるステップＮ１〜Ｎ４，Ｎ６，Ｓ１０〜Ｓ３０，Ｓ６０〜Ｓ９０と、ロングフォールスパスの評価を含んだ計算式に基づいて、リソース共有化グラフ内の共有化エッジの評価値を計算するステップＳ４１とから構成さている。
【００７７】
実施の形態２が実施の形態１と異なる点は、実施の形態１では共有化によってロングフォールスパスになる共有化エッジを、あらかじめ、ライフタイムオーバーラップ防止用の共有化エッジ削除のステップＳ４０で削除しているのに対して、本実施の形態では、ロングフォールスパス発生の抑制は、ステップＳ４１で用いる共有化エッジの評価式（５）に組み込んでいる点である。
【００７８】
Ｐａｆ（Ａ，Ｂ）
＝ｆ（Ｓｉｇ（Ｐａｂ（Ａ，Ｂ），Ｐａｐ（Ａ，Ｂ））×（（λ×ＡＢＳ（Ｐａｂ（Ａ，Ｂ））＋ω×ＡＢＳ（Ｐａｐ（Ａ，Ｂ））））  ……………………………（５）
Ｐａｂ（Ａ，Ｂ）＝Ａrea（Ａ）＋Ａrea（Ｂ）−Ａrea（Ａ，Ｂ）  ……………（６）
Ｐａｐ（Ａ，Ｂ）＝Ｃｐ−τ（Ａ，Ｂ）  ……………………………………………（７）
式（６）のＡrea（Ａ），Ａrea（Ｂ），Ａrea（Ａ，Ｂ）は式（１）と同様であり、式（７）のＣｐ，τ（Ａ，Ｂ）は式（３）と同様である。式（５）のｆ（Ｘ）は、Ｘが負のときはゼロ、それ以外の場合はＸを返す関数である。Ｓｉｇ（Ｘ，Ｙ）は、ＸまたはＹがマイナスの場合は−１を返し、ＸおよびＹがゼロ以上の場合は１を返す関数である。ＡＢＳ（Ｘ）は、Ｘの絶対値を取る関数である。λ、ωは実験等で決定する定数である。
【００７９】
面積・遅延指向評価値Ｐａｆは、面積削減率評価値Ｐａｂあるいはパス遅延評価値Ｐａｐが正の値をもつ場合にのみ、正の値をもつ。評価値Ｐａｐは、リソースＡ，Ｂが共有化された場合のフォールスパスを含むレジスタリソース間パス遅延がクロック周期を超える場合（ロングフォールスパス）に負の値になる。評価値Ｐａｐが負の値をもつと、面積・遅延指向評価値Ｐａｆはゼロになるので、ロングフォールスパスを生成する共有化エッジは、ステップＳ７０で選択されない。
【００８０】
共有化が進む過程で選択リソースＭＵＸの数は増減するため、ある状態でロングフォールスパスになる共有化エッジが、選択リソースＭＵＸ数が減少したときにロングフォールスパスでなくなる場合がある。本実施の形態では、ロングフォールスパスになる共有化エッジを削除するのではなく、評価値として表現しているため、このような場合おいても共有化が可能となり、より多くのリソース組が共有化され、最終的に得られるレジスタ転送レベル回路の面積がより小さくなる。
【００８１】
（実施の形態３）
図９は本発明の実施の形態３における、ハードウェアリソース共有化方法を含んだ高位合成の処理順序を示すフローチャートであり、実施の形態１で説明したステップである、ステップＮ１〜Ｎ４，Ｎ６，Ｓ１０，Ｓ２０に加えて、目的関数を用いた組み合わせ最適化手法により共有化を進めるステップＳ５５を備えている。
【００８２】
図１０はステップＳ５５の組み合わせ最適化手法にシミュレーティッドアニーニングを用いた場合で説明した図であり、実施の形態１で説明したステップである、Ｓ３０，Ｓ４０，Ｓ８０，Ｓ９０と、
あらかじめ設定された共有化終了条件に合致したかどうかを判定し、合致した場合に処理を終了するステップＳ６１と、
ランダムに共有化エッジを選択するステップＳ６２と、
目的関数を用いたシミュレーティッドアニーニング法により、選択した共有化エッジの両端のリソース組を共有化するかしないかを決定し、共有化しない場合はステップＳ６１へ進み、共有化する場合はステップＳ８０へ進むステップＳ６３
とを備えている。以降、実施の形態１と異なる点のみを、図１０を用いて説明する。
【００８３】
ステップＳ６１では、ステップＳ５５で用いられる組合せ最適化手法に準じて、あらかじめ設定された処理の終了条件に合致しているかを判定して、合致している場合は処理を終了する。終了条件としては、ステップＳ３０〜ステップＳ９０の繰返し回数で決定したり、シミュレーティッドアニーニングのパラメータである温度で決定したりする。
【００８４】
ステップＳ６２では、リソース共有化エッジをランダムに選択する。
【００８５】
ステップＳ６３では、ステップＳ６２で選択された共有化エッジをシミュレーティッドアニーニングによる評価方法を用いて、共有化するかしないかを決定する。シミュレーティッドアニーニングの評価で用いる目的関数は、データパスグラフ（ＤＰＧ）内にあるリソース面積の総和とする。
【００８６】
ステップＳ６３で共有化すると決定した場合は、実施の形態２と同様に、ステップＳ８０とステップＳ９０により、データパスグラフおよび共有化グラフを更新し、ステップＳ６１へ戻る。
【００８７】
ステップＳ６１で処理終了と判定されるまで処理を繰り返すことで、目的関数が小さくなる、すなわちリソース面積の総和が小さくなる共有化が可能となる。
【００８８】
シミュレーティッドアニーニングに代表される組合せ最適化手法では、ローカル解に陥るのを避けるために、一時的に目的関数が増加するような状態を発生させながらグローバル解を求める。図１１は一時的に目的関数を増加させることで、最終的に得られるレジスタ転送レベル回路が小さくなる一例を説明するための図であり、Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈはリソース、実線の有向エッジはデータパスの信号経路、破線の無向エッジは共有化エッジを表している。Ａ〜Ｈと実線でデータパスグラフを表現している。
【００８９】
図１１（ａ）の例では、いずれの共有化エッジでリソースを共有化しても、選択リソースＭＵＸが挿入される。図１１（ｂ）は（Ｂ，Ｆ）を共有化した場合を示し、リソースＢＦの前にデータを選択する選択リソースＭＵＸが挿入されている。しかし、図１１（ｃ）に示すように、（Ａ，Ｅ），（Ｂ，Ｆ），（Ｃ，Ｇ），（Ｄ，Ｈ）のすべてのリソース組を共有化すると、選択リソースＭＵＸは１つも必要でない。
【００９０】
いずれのリソース共有によっても、挿入される選択リソースＭＵＸの面積が共有化によって削減される面積より大きい場合、実施の形態１では、式（１）の面積削減率評価値Ｐａ（式（２）、式（３）もＰａの項があるために同様）によって有効な共有化エッジとならないために、共有化が完了してしまう。しかし、本実施の形態によると、一時的な面積増加（目的関数値の増加）が起こってもリソース共有化を実施するために、図１１（ｂ）の結果を得ることができる。
【００９１】
以上説明したように、目的関数を用いた組合せ最適化手法を用いることで、一時的に目的関数が増加するような共有化エッジによる共有化も実施され、解の探索範囲が広がることで、ローカル解での共有化処理終了が回避される。目的関数をリソース面積の総和とした場合、最終的に得られるレジスタ転送レベル回路の面積がより小さくなる。
【産業上の利用可能性】
【００９２】
本発明の高位合成におけるハードウェアリソース共有化方法は、共有化で問題となる活性しないパス（フォールスループ／ロングフォールスパス）の発生を抑制しつつ、共有化率の増大を促進することができるので、最終的に得られるレジスタ転送レベル回路の選択リソースを含んだ面積を小さくすることができる特徴を有し、大規模集積回路の設計に広く利用することができる。
【図面の簡単な説明】
【００９３】
【図１】本発明の実施の形態１におけるハードウェアリソース共有化方法を含んだ高位合成の処理順序を示すフローチャート
【図２】本発明の実施の形態１における共有化エッジの一例を示した図
【図３】図２からフォールスループを削除した一例を示した図
【図４】本発明の実施の形態１において共有化後のデータパスグラフの一例を示した図
【図５】本発明の実施の形態１によって得られた最終的なデータパスグラフの一例を示した図
【図６】本発明の実施の形態１において共有化エッジ数残存率評価値の効果を説明するための図
【図７】本発明の実施の形態１においてパス遅延増加率評価値の効果を説明するための図
【図８】本発明の実施の形態２におけるハードウェアリソース共有化方法を含んだ高位合成の処理順序を示すフローチャート
【図９】本発明の実施の形態３におけるハードウェアリソース共有化方法を含んだ高位合成の処理順序を示すフローチャート
【図１０】本発明の実施の形態３においてシミュレーティッドアニーニングを用いてステップＳ５５を実現した場合の処理順序を示すフローチャート
【図１１】本発明の実施の形態３において組合せ最適化手法を用いた効果を説明するための図
【図１２】従来の技術における高位合成の処理順序を示すフローチャート
【図１３】動作レベル記述の一例を示した図
【図１４】ＣＤＦＧの一例を示した図
【図１５】ＣＤＦＧスケジューリング後の一例を示した図
【図１６】従来の技術においてリソース共有化した場合の一例を示した図
【符号の説明】
【００９４】
Ｎ１  ＣＤＦＧ生成ステップ
Ｎ２  リソース割付ステップ
Ｎ３  スケジューリングステップ
Ｎ４  レジスタ割付ステップ
Ｎ５  従来技術のリソース共有化ステップ
Ｎ６  レジスタ転送レベル記述生成ステップ
Ｓ１０：データパスグラフ生成ステップ
Ｓ２０：共有化グラフ生成ステップ
Ｓ３０：閉路防止用の共有化エッジ削除ステップ（フォールスループ抑制）
Ｓ４０：ライフタイムオーバーラップ防止用の共有化エッジ削除ステップ（ロングフォールスパス抑制）
Ｓ５０：ハードウェアリソース組決定ステップ（共有化エッジの評価値計算）
Ｓ６０：ハードウェアリソース組決定ステップ（有効共有化エッジの判定）
Ｓ７０：ハードウェアリソース組決定ステップ（評価値に基づいた共有化エッジ選択）
Ｓ８０：ハードウェアリソース組の共有化ステップ
Ｓ９０：閉路防止用の共有化エッジ削除ステップ（共有化エッジ更新）
【図１】
2008186126.tif 000003
【図２】
2008186126.tif 000004
【図３】
2008186126.tif 000005
【図４】
2008186126.tif 000006
【図５】
2008186126.tif 000007
【図６】
2008186126.tif 000008
【図７】
2008186126.tif 000009
【図８】
2008186126.tif 000010
【図９】
2008186126.tif 000011
【図１０】
2008186126.tif 000012
【図１１】
2008186126.tif 000013
【図１２】
2008186126.tif 000014
【図１３】
2008186126.tif 000015
【図１４】
2008186126.tif 000016
【図１５】
2008186126.tif 000017
【図１６】
2008186126.tif 000018