(57)【要約】高レベル合成レジスタ転送レベル設計を行うための方法および装置は、データ経路割り付けにおける電力消散、面積利用間のトレードオフを利用する。電力消散および面積制約条件、ならびにその間の優先順位を入力する。アルゴリズムは、特定した優先順位および制約条件に従って、使用するべきレジスタの数を自動的に判断する。電力管理公式を用いて、レジスタ領域内で同等に保管するためのより少ない電力管理コストをトレードするように割り付け処理を適合させることが可能である。複数判定基準最適化整数線形計画法を、発見的に定められた電力および面積重み付けと共に利用して、予め規定されたチップ設計の異なる必要条件を適合させる。二連重み付け割り当てを用いて、コスト公式およびハンガリアンアルゴリズムによって、あらゆる段階で使用するレジスタの数を決定する。
2008500631.tif 000002
【特許請求の範囲】
【請求項１】
データ経路割り付け方法において：
（ａ）  初期資源割り付けを生成する工程と；
（ｂ）  資源の割り付けが所定の第１の制約条件を満たすかどうかを決定する工程と；
（ｃ）  より少ない面積利用および電力利用の一方と、より多い面積利用および電力利用の他方とのトレードオフに基づいて、改訂された資源の割り付けを生成する工程と；
を備え、前記第１の制約条件が満たされたと決定されるまで（ｂ）および（ｃ）を繰り返すことを特徴とする、データ経路割り付け方法。
【請求項２】
初期資源割り付け生成工程が、より少ない面積および電力利用間の優先順位に基づいて資源を割り付ける工程を備えることを特徴とする請求項１に記載の方法。
【請求項３】
より小さい電力よりも、より小さい面積に優先順位がある場合には、初期資源割り付け生成工程が、大量のレジスタを共用することに基づいて資源を割り付ける工程を備えることを特徴とする請求項２に記載の方法。
【請求項４】
より小さい電力よりも、より小さい面積に優先順位がある場合には、初期資源割り付け生成工程が、できるだけ多くのジスタを共用することに基づいて資源を割り付ける工程を備えることを特徴とする請求項３に記載の方法。
【請求項５】
より小さい電力よりも、より小さい面積に優先順位がある場合には、改訂された資源の割り付けを繰り返し生成する工程が、第１の制約条件を満たすまで面積利用の増大と電力利用の削減を繰り返す工程を備えることを特徴とする請求項２〜４のいずれかに記載の方法。
【請求項６】
より小さい面積よりも、より小さい電力に優先順位がある場合には、初期資源割り付け生成工程が、優れた電力管理に基づいて資源を割り付ける工程を備えることを特徴とする請求項２〜５のいずれかに記載の方法。
【請求項７】
より小さい面積よりも、より小さい電力に優先順位がある場合には、初期資源割り付け生成工程が、完全電力管理に基づいて資源を割り付ける工程を備えることを特徴とする請求項６に記載の方法。
【請求項８】
より小さい面積よりも、より小さい電力に優先順位がある場合には、改訂された資源割り付けを繰り返し生成する工程が、第１の制約条件を満たすまで電力利用の増大と面積利用の削減を繰り返す工程を備えることを特徴とする請求項２〜７のいずれかに記載の方法。
【請求項９】
より小さい面積およびより小さい電力の利用の優先順位を入力する工程をさらに備えることを特徴とする請求項２〜８のいずれかに記載の方法。
【請求項１０】
より小さい面積よりも、より小さい電力に優先順位がある場合には、より小さい電力の利用に対する、より大きい面積の利用においてトレードオフが行われることを特徴とする請求項２〜９のいずれかに記載の方法。
【請求項１１】
より小さい電力よりも、より小さい面積に優先順位がある場合には、より小さい面積の利用に対する、より大きい電力の利用においてトレードオフが行われることを特徴とする請求項２〜１０のいずれかに記載の方法。
【請求項１２】
より少ない面積利用に対する、より多い電力利用を受け付ける工程が、レジスタ間での共用に、より多くの変数を割り付ける工程を備えることを特徴とする請求項１１に記載の方法。
【請求項１３】
あまり頻繁には使用しない変数が、改訂された資源の割り付け生成工程を、より頻繁に使用する変数よりも早めに繰り返す際に、レジスタ間で共用するように割り付けられるものであることを特徴とする請求項１２に記載の方法。
【請求項１４】
電力消費がより少ない演算のための変数は、改訂された資源の割り付け生成工程を、電力消費がより多い演算のための変数よりも早めに繰り返す際に、レジスタ間で共用するように割り付けられることを特徴とする請求項１２または１３に記載の方法。
【請求項１５】
より少ない電力利用に対する、より多い面積利用を受け付ける工程が、レジスタ間で共用する、より多くの変数を別のレジスタに割り付ける工程を備えることを特徴とする、請求項１０または少なくとも請求項１０に従属する場合は請求項１１〜１４のいずれかに記載の方法。
【請求項１６】
より頻繁に使用する変数が、改訂された資源の割り付けを生成する工程を、あまり頻繁には使用しない変数よりも早めに繰り返す際に、別のレジスタに割り付けられるものであることを特徴とする請求項１５に記載の方法。
【請求項１７】
電力消費がより多い演算のための変数は、改訂された資源の割り付けを生成する工程を、電力消費がより少ない演算のための変数よりも早めに繰り返す際に、別のレジスタに割り付けられることを特徴とする請求項１５または１６に記載の方法。
【請求項１８】
改訂された資源の割り付け生成工程が、複数の可能な割り付けに関連するコストを決定し、前記関連のコストに基づいて割り付けを選択する工程を備えることを特徴とする請求項１〜１７のいずれかに記載の方法。
【請求項１９】
前記関連のコストに基づく割り付けを選択する工程が、最低の関連コストでの割り付けを選択する工程を備えることを特徴とする請求項１８に記載の方法。
【請求項２０】
電力利用に電力重み付きを与え、コストは、割り付けおよび電力重み付けに関連する電力利用に基づく資源の割り付けに関連することを特徴とする請求項１〜１９のいずれかに記載の方法。
【請求項２１】
面積利用に面積重み付きを与え、コストは、割り付けおよび面積重み付けに関連する面積利用に基づく資源の割り付けに関連することを特徴とする請求項１〜２０のいずれかに記載の方法。
【請求項２２】
改訂された資源割り付け生成工程が、重み付けのうちの少なくとも１つを変化させる工程をさらに備えることを特徴とする、少なくとも請求項１８に従属する場合は請求項２０または２１に記載の方法。
【請求項２３】
面積および電力利用間のトレードオフを決定する際に変数のためのスイッチングアクティビティを利用する工程をさらに備えることを特徴とする請求項１〜２２のいずれかに記載の方法。
【請求項２４】
変数のためのスイッチングアクティビティに関する情報を入力する工程をさらに備えることを特徴とする請求項２３に記載の方法。
【請求項２５】
スイッチングアクティビティは、コンパイラ指令によってユーザが入力することを特徴とする請求項２４に記載の方法。
【請求項２６】
変数のためのスイッチングアクティビティを自動的に決定する工程をさらに備えることを特徴とする請求項２３または２４に記載の方法。
【請求項２７】
変数が入力されない場合、スイッチングアクティビティのためのデフォルト値を決定することを特徴とする請求項２６に記載の方法。
【請求項２８】
２個の変数の各々に対して、変数を他の変数に連結された機能ユニットの電力量へのスイッチングの割合を乗算して、共用処理に導入されたスプリアス電力消散を示すことにより、２個の変数間の共通レジスタを共用して、相対的電力消散コストを計算する工程をさらに備えることを特徴とする請求項２３〜２７のいずれかに記載の方法。
【請求項２９】
相対的電力消散コストが、以下の公式に従って計算されることを特徴とする請求項２８に記載の方法：
【数１】
2008500631.tif 000023
ここで、
Ｖａｒ１は、レジスタに割り付けられた変数を表す；
Ｖａｒ２は、このレジスタを事前に用いた変数を表す；
ＳＡは、全ての変数に関する変数のスイッチングアクティビティを表す；
ｎは、宛先演算の数を表す；
Ｐｏｗｅｒは、２個の変数では共用されない、割り付けられた機能ユニットの正規化された電力消費を表す。
【請求項３０】
資源割り付け生成工程が、モジュールおよびレジスタへのデータ経路における演算および変数をそれぞれ割り付ける工程を備えることを特徴とする請求項１〜２９のいずれかに記載の方法。
【請求項３１】
同一モジュールを使用することが可能な演算のグループを生成する工程をさらに備えることを特徴とする請求項３０に記載の方法。
【請求項３２】
演算をモジュールに割り付ける際に、生存期間がオーバラップする演算のクラスタを生成する工程をさらに備えることを特徴とする請求項３０または３１に記載の方法。
【請求項３３】
同一モジュールおよびオーバラップする生存期間を利用する能力によって演算をクラスタリングすることを特徴とする請求項３１または３２に記載の方法。
【請求項３４】
レジスタに変数を割り付ける際に、オーバラップする生存期間を有する変数のクラスタを生成する工程をさらに備えることを特徴とする請求項３０〜３３のいずれかに記載の方法。
【請求項３５】
機能ユニットへの演算の異なる割り付けのために相対的な面積コストを決定する工程をさらに備えることを特徴とする請求項１〜３４のいずれかに記載の方法。
【請求項３６】
レジスタへの演算の異なる割り付けのために相対的な面積コストを決定する工程をさらに備えることを特徴とする請求項１〜３５のいずれかに記載の方法。
【請求項３７】
面積コストが、レジスタの面積コストを備えることを特徴とする請求項３６に記載の方法。
【請求項３８】
面積コストが、マルチプレクサの面積コストを備えることを特徴とする請求項３５〜３７のいずれかに記載の方法。
【請求項３９】
面積コストが、特定の割り付けにおいて明示面積コストを備えることを特徴とする請求項３５〜３８のいずれかに記載の方法。
【請求項４０】
面積コストが、特定の割り付けにおいて暗黙面積コストをさらに備えることを特徴とする請求項３９に記載の方法。
【請求項４１】
資源割り付け生成工程が、電力およびコスト利用のための重みと共に、二連重み付け割り当て割り付けを使用する工程をさらに備えることを特徴とする請求項１〜４０のいずれかに記載の方法。
【請求項４２】
改訂された資源の割り付けを生成する際に、電力および面積利用のための相対的重み付けを変化させる工程をさらに備えることを特徴とする請求項４１に記載の方法。
【請求項４３】
資源の割り付け生成工程は、ハンガリアンアルゴリズムを用いて割り付け整合問題を解決する工程をさらに備えることを特徴とする請求項１〜４２のいずれかに記載の方法。
【請求項４４】
より少ない面積利用およびより少ない電力利用のトレードオフが、以下の式を満たすことによって面積および電力の両方を共最適化する工程を備えることを特徴とする請求項１〜４３のいずれかに記載の方法：
【数２】
2008500631.tif 000024
ここで、
ｆpower（ｘ）は電力のコスト公式を表す、
ｆarea（ｘ）は面積のコスト公式を表す、
Ｃ＝｛最大関連密度での最小数のレジスタまたは機能ユニットの制約条件を表す｝、
Ｋpowerはｆpower（ｘ）の重みを表す、
Ｋareaはｆarea（ｘ）の重みを表す。
【請求項４５】
所定の第１の制約条件が、所定の面積制約条件および所定の電力利用制約条件のうちの一方であることを特徴とする請求項１〜４４のいずれかに記載の方法。
【請求項４６】
所定の第２の制約条件が、所定の面積制約条件および所定の電力利用制約条件のうちの他方であり、（ｂ）前記所定の第２の制約条件を満たすかどうかを判断する工程をさらに備えることを特徴とする請求項４５に記載の方法。
【請求項４７】
所定の第２の制約条件が、所定の面積制約条件および所定の電力利用制約条件のうちの
他方であり、前記第１の制約条件が満たされていると判断した後、前記所定の第２の制約条件を満たすかどうかを判断する工程をさらに備えることを特徴とする請求項４５に記載の方法。
【請求項４８】
少なくとも前記所定の第１の制約条件を入力する工程をさらに備えることを特徴とする請求項１〜４７のいずれかに記載の方法。
【請求項４９】
所与のデータフローグラフ（ＤＦＧ）からのデータ経路割り付け方法であることを特徴とする請求項１〜４８のいずれかに記載の方法。
【請求項５０】
回路に対するデータ経路割り付け方法であることを特徴とする請求項１〜４９のいずれかに記載の方法。
【請求項５１】
電子回路に対するデータ経路割り付け方法であることを特徴とする請求項１〜５０のいずれかに記載の方法。
【請求項５２】
実質的に添付図面を参照して上で述べた、また添付図面に例示したデータ経路割り付け方法。
【請求項５３】
データ経路割り付け装置において：
初期資源割り付けを生成する手段と；
資源の割り付けが少なくとも１つの所定制約条件を満たすかどうかを決定する手段とを備え、前記少なくとも１つの所定制約条件は、所定の面積制約条件および所定の電力利用のうちの少なくとも１つを備え、さらに；
より少ない面積利用および電力利用の一方と、より多い面積利用と電力利用の他方とのトレードオフに基づいて改訂された資源の割り付けを生成する手段と；
前記改訂された割り付けが前記少なくとも１つの所定制約条件を満たすかどうかを決定するための手段と；
改訂された割り付けを生成し、前記改訂された割り付けが前記少なくとも１つの制約条件を満たすまでに前記少なくとも１つの所定の制約条件を満たすかどうかを決定するために前記装置を制御するための手段と；
を備えることを特徴とする、データ経路割り付け装置。
【請求項５４】
請求項１〜５２のいずれかに記載の方法により動作可能な装置。
【請求項５５】
請求の範囲１〜５２のいずれかに記載の方法により動作可能な、請求項５３に記載の装置。
【請求項５６】
実質的に添付図面を参照して上で述べたように、また添付図面に例示したように動作するように構成され配置されたデータ経路割り付け装置。
【請求項５７】
データ経路割り付けのためのコンピュータ読み出し可能媒体にコンピュータプログラムが記録されたコンピュータプログラム製品において、前記コンピュータプログラム製品は：
初期資源割り付けを生成するコンピュータプログラムコード手段と；
資源の割り付けが少なくとも１つの所定制約条件を満たすかどうかを決定するコンピュータプログラムコード手段とを備え、前記少なくとも１つの所定制約条件は、所定の面積制約条件および所定の電力利用制約条件のうちの少なくとも１つを備え、さらに；
より少ない面積利用および電力利用の一方と、より多い面積利用および電力利用の他方とのトレードオフに基づいて改訂された資源の割り付けを生成するコンピュータプログラ
ムコード手段と；
前記改訂された割り付けが前記少なくとも１つの所定制約条件を満たすかどうかを決定するためのコンピュータプログラムコード手段と；
改訂された割り付けを生成し、前記改訂された割り付けが前記少なくとも１つの制約条件を満たすまでに前記少なくとも１つの所定の制約条件を満たすかどうかを決定するために前記装置を制御するためのコンピュータプログラムコード手段と；
を備えることを特徴とする、コンピュータプログラム製品。
【請求項５８】
請求項１〜５２のいずれかに記載の方法によりデータ経路割り付けのための動作可能な、コンピュータ読み出し可能媒体にコンピュータプログラムが記録されたコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば回路設計においてデータ経路を割り付けることに関する。
【背景技術】
【０００２】
回路設計において、設計者は回路の機能性のアルゴリズム仕様を含む行動記述から開始することも可能である。高レベル合成によって、超大規模集積（ＶＬＳＩ）回路の行動記述が構造上のレジスタ転送レベル（ＲＴＬ）の実現に変換される。このＲＴＬ実現は、マクロブロック（例えば、機能ユニット、レジスタ、マルチプレクサ、バス、メモリブロック等）およびランダム論理の相互接続について述べている。
【０００３】
順次回路についての行動記述には、回路のサイクル毎の行動についての情報がほとんど含まないか、またはその構造実現を含むことも可能である。高レベル合成（ＨＬＳ）ツールは一般に、行動記述を、制御データフローグラフ（ＣＤＦＧ）等の好適な中間フォーマットにコンパイルする。ＣＤＦＧにおける頂点は、行動記述の様々な動作を表す。データおよび制御エッジを用いて、動作と制御フローとのデータ依存性を表す。
【０００４】
高レベル合成ツールは一般に、以下のタスク、すなわち変換、モジュール選択、クロック選択、スケジューリング、資源割り付けおよび割り当て（資源共用またはハードウェア共用とも呼ぶ）のうち１つ以上を実施する。スケジューリングは、一つ以上のクロックサイクルまたは制御ステップに各動作を割り当てることにより、設計のサイクル毎の行動を決定する。割り付けは、行動記述を実現するために使用する各形式のハードウェア資源の数を決定する。割り当ては、各変数（および対応する動作）の、割り付けられたレジスタの一つ（および対応する機能ユニット）に対する結合に関連する。
【０００５】
ＶＬＳＩ回路において、回路内の信号が論理変換を受ける際には必ず必要となるダイナミックコンポーネントは、電力消散を支配する場合が多い。しかし、各クロックサイクル中に回路の全ての部分が機能する必要があるわけではない。このように、不必要な信号遷移を抑圧するか、または排除することに基づいて、いくつかの低電力設計技術が提案されている。一般に、このような技術に関連して用いる用語として、電力管理が挙げられる。データ経路割り付けの文脈では、以下の技術を用いるデータ経路割り付けに電力管理を適用することが可能である。
ｉ）  オペランド分離
埋め込み組み合わせ論理ブロックの入力における透過ラッチおよび他の制御回路を挿入して、論理ブロックのためのアイドル状態を検出する。制御回路の出力を適度に利用して、論理ブロックの入力におけるラッチが値を変化させないようにする。このように、前のサイクルの入力値が、考慮中の論理ブロックの入力に保持されて、不必要な電力消散を排除する。
【０００６】
オペランド分離技術には、欠点が２つある。様々な分岐回路のためのアイドル状態を検出する信号は一般に、遅れて到着する（例えば、各コントローラの状態に、ネストされた条件が存在することにより、アイドル状態がデータ経路からの比較器の出力に依存する可能性もある）。したがって、課すべきタイミング制約条件には、頻繁に応じるわけではなく（すなわち、透過ラッチに対するイネーブル信号が、そのデータ入力が変化可能となる前に処理しなければならず、それによって抑圧が効果的でなくなる。さらに、機能ユニットの前方に透過ラッチを挿入することにより、回路のクリティカルパスにおけるさらなる遅延を生じることになり、これは、高速でしかも電力効率の良さを必要とする信号および画像処理アプリケーションにおいて受容可能でなくてもよい。
ｉｉ）      低電力ＶＬＳＩ設計のための制約付きレジスタ共用技術
ラグネーサン（Ｒａｇｈｕｎａｔｈａｎ）他に２００１年２月２７日に発行された米国特許第６，１９５，７８６Ｂ１号により、データ経路割り付けにおけるレジスタ共用を拘束することにより、スプリアス動作が回避される。この機構では、レジスタの賢明な共用が割り付けられ、その結果、共通レジスタを共用するいくつかの動作に対する出力変数によって、他の機能ユニットの入力に対して不必要なスイッチングを行わなくなる。
【０００７】
データ経路割り付けは、少なくともスプリアススイッチングアクティビティに関する限り、完全電力管理を利用し、それによって、あらゆる機能ユニットへの入力を、他のいかなる機能ユニットの入力にも接続されないレジスタに接続することが必要となる。この厳密な要求によって、共用可能な資源の量やＣＤＦＧの性質に比例して変化する省電力や面積オーバヘッドを有するアーキテクチャが得られる。制約付きレジスタ共用において、機能ユニットの一方の入力に繰り返し現れる値のシーケンスが、ｖ１_１、ｖ２_１，…  、ｖｉ_１に対応し、機能ユニットの他の入力に繰り返し現れる値のシーケンスが、ｖ１_２、ｖ２_２，…  、ｖｉ_２に対応する場合、いずれかのクロックサイクルでの機能ユニットの入力における値は、対の（ｖｊ_１、ｖｊ_２）、１_ｊ_ｉに対応する。
【０００８】
図１は、２個のレジスタの無制限使用を示す。図２は、レジスタの制約付き共用を示す。図１において、第１のレジスタＲ１は、第１のクロック期間、論理演算装置（ＡＬＵ）に第１の変数ＶａｒＡを与え、マルチプレクサ（ＭＵＬＴ）に第２の変数ＶａｒＢを与え、第１のクロック期間の後の第２のクロック期間に、他の場所からも入力を受ける。レジスタの制約付き共用では、図２に示すように、第２のレジスタＲ２がさらに設けられる。第１のレジスタＲ１は、第１のクロック期間に演算論理装置（ＡＬＵ）に第１の変数ＶａｒＡを与え、第２のレジスタＲ２は、第２のクロック期間にマルチプレクサ（ＭＵＬＴ）に変数ＶａｒＢを与える。制約付き共用により、スプリアススイッチングアクティビティが回避される。しかしながら、これによってレジスタの数が増えることになる。
【０００９】
制約付きレジスタ共用は、８．４％から３３．０％までの省電力ならびに４．０％から６．４％までの面積オーバヘッドを提供するものと報告されている。関連の論文では、上記米国特許公報第６，１９５，７８６Ｂ１号、ジー・ラクシュミナラヤナ（Ｇ．Ｌａｋｓｈｍｉｎａｒａｙａｎａ）、エー・ラグナンサン（Ａ．Ｒａｇｈｕｎａｎｔｈａｎ）、エヌ・ケー・ジャ（Ｎ．Ｋ．Ｊｈａ）およびエス・ディー（Ｓ．Ｄｅｙ）、「高レベル合成における電力管理（Ｐｏｗｅｒ  ｍａｎａｇｅｍｅｎｔ  ｉｎ  ｈｉｇｈ  ｌｅｖｅｌ  ｓｙｎｔｈｅｓｉｓ）」、ＩＥＥＥトランス（Ｔｒａｎｓ．）ＶＬＳＩシステムズ（Ｓｙｓｔｅｍｓ）、第７巻、第１号、７ページから１５ページ、１９９９年３月、に挙げられている発明者によって発表されている。この論文には、０％から１３．８％の面積オーバヘッドでの電力削減（平均２３．０５、標準偏差１３．３％）が、５９，７２および８６サイクルのスループット制約条件の元で試験された帯域例を用いて報告されている。延長したサンプリング期間が、増大したレジスタ共用を容易にするため、サンプリング期間の延長で電力消散および面積オーバヘッドが増大し、それによって、スプリアス動作の実行における増大をもたらすことに注目した。スプリアス動作を排除するために、レジスタ共用は、緊密な性能条件付き設計と比較して、かなりの程度まで抑圧するべきである。
【００１０】
制約付きレジスタ共用管理は、省電力は優れているが、データフローグラフ特性に依存する面積オーバヘッドを有する。多くの共用可能な動作および変数を有するデータフローグラフ（ＤＦＧ）に対して、この割り付け機構において受ける面積オーバヘッドは大きい。大きな面積オーバヘッドは、ＤＦＧに対する制約付きレジスタ共用管理を受け、この場合、多くの動作出力変数は、後の制御段階における２つ以上の動作に及ぶ。すなわち、動作の入力は他の動作に接続される。これによって、特に、このような変数に対するレジスタの共用から生じるスプリアススイッチングアクティビティの機会が多くなる。制約付き
レジスタ共用の厳密な条件によっては、データ経路割り付け段階で必要とされるほどレジスタを使用しないＲＴＬ設計を生成するという柔軟性を開発者は提供していない。
【００１１】
ダイのコストは一般に、その面積の４倍に比例する。従って、生産コストを削減するための最小面積のＲＴＬ設計の実施は、コスト効果がある。しかしながら、ラップトップ、パームトップコンピュータ、携帯電話、ワイヤレスモデム、ハンドヘルドビデオゲーム等の携帯用または移動式計算および通信装置の出現により、電力消散は、あらゆるＲＴＬ設計における他の主要な問題となっている。集積回路内の過度の電力消散は、携帯環境における使用を妨げるだけでなく、過熱を生じ、その結果、性能を劣化させてチップ寿命を短くすることになる。その温度レベルを制御するために、高電力チップは、特殊でしかも高価な包装やヒートシンク構造を必要とする。過度な電力消散は、一個または多数のチップのモジュールに、より多くのトランジスタを集積する際の限定要因となる。
【００１２】
チップ設計の面積および電力の必要条件は、チップが提供するアプリケーションにより規模が異なる。携帯用装置および高密度超小型電子装置に対して、ＶＬＳＩ回路の電力消散は、重大な関心事である。非携帯装置および低密度超小型電子装置に対して、電力消散は、ダイ面積と比較してあまり重大な問題とはならない。
【特許文献１】米国特許第６，１９５，７８６Ｂ１号明細書
【非特許文献１】ジー・ラクシュミナラヤナ（Ｇ．Ｌａｋｓｈｍｉｎａｒａｙａｎａ）、エー・ラグナンサン（Ａ．Ｒａｇｈｕｎａｎｔｈａｎ）、エヌ・ケー・ジャ（Ｎ．Ｋ．Ｊｈａ）およびエス・ディー（Ｓ．Ｄｅｙ）、「高レベル合成における電力管理（Ｐｏｗｅｒ  ｍａｎａｇｅｍｅｎｔ  ｉｎ  ｈｉｇｈ  ｌｅｖｅｌ  ｓｙｎｔｈｅｓｉｓ）」、ＩＥＥＥトランス（Ｔｒａｎｓ．）ＶＬＳＩシステムズ（Ｓｙｓｔｅｍｓ）、第７巻、第１号、７ページから１５ページ、１９９９年３月
【発明の開示】
【００１３】
本発明の一局面では、データ経路割り付け方法が提供される。前記方法は、初期資源割り付けを生成する工程と、資源の割り付けが所定の第１の制約条件を満たすかどうかを決定する工程とを備える。制約条件を満たさない場合には、より小さい面積利用および電力利用とのトレードオフに基づいて、改訂された資源の割り付けを生成する。改訂された割り付けは、第１の制約条件を満たすまで、第１の制約条件に逆らって生成されテストされる。
【００１４】
本発明の他の局面では、データ経路割り付け装置が提供される。前記装置は、初期資源割り付けを生成する手段と、資源の割り付けが少なくとも１つの所定制約条件を満たすかどうかを決定する手段とを備え、前記少なくとも１つの所定制約条件は、所定の面積制約条件および所定の電力利用のうちの少なくとも１つを備える。前記装置はまた、より小さい面積利用および電力利用の一方と、より高い面積利用と電力利用の他方とのトレードオフに基づいて、改訂された資源の割り付けを生成する手段を備える。前記装置は、前記改訂された割り付けが前記少なくとも１つの所定制約条件を満たすかどうかを決定するための手段をさらに備える。前記装置は、前記改訂された割り付けを生成し、前記改訂された割り付けが前記少なくとも１つの制約条件を満たすまでに前記少なくとも１つの所定の制約条件を満たすかどうかを決定するために前記装置を制御するための手段をさらに備える。
【００１５】
本発明のさらに他の局面では、前記第１の局面の方法により動作可能なデータ経路割り付け装置が提供される。
本発明のさらに他の局面では、データ経路割り付けのための、コンピュータ読み出し可能媒体に記録されたコンピュータプログラムを有するコンピュータプログラム製品が提供される。前記コンピュータプログラム製品は、初期資源割り付けを生成するコンピュータ
プログラムコード手段と、資源の割り付けが少なくとも１つの所定制約条件を満たすかどうかを決定するコンピュータプログラムコード手段とを備え、前記少なくとも１つの所定制約条件は、所定の面積制約条件および所定の電力利用のうちの少なくとも１つを備える。前記製品は、より少ない面積利用および電力利用の一方と、より多い面積利用と電力利用の他方とのトレードオフに基づいて、改訂された資源の割り付けを生成するコンピュータプログラムコード手段をさらに備える。前記製品は、前記改訂された割り付けが前記少なくとも１つの所定制約条件を満たすかどうかを決定するためのコンピュータプログラムコード手段をさらに備える。前記製品は、前記改訂された割り付けを生成し、前記改訂された割り付けが、前記少なくとも１つの制約条件を満たすまでに前記少なくとも１つの所定の制約条件を満たすかどうかを決定するために前記装置を制御するためのコンピュータプログラムコード手段をさらに備える。
【００１６】
本発明のさらに他の局面では、前記第１の局面の方法により動作可能なデータ経路割り付けのための、コンピュータ読み出し可能媒体に記録されたコンピュータプログラムを有するコンピュータプログラム製品が提供される。
【００１７】
本発明の実施の形態を用いて、最適化技術の優先順位をアドレスし、チップ開発要求を分類するための、開発者により特定された制約条件にある面積および電力消費特性を有する回路を生成するために、高レベル合成ツールに対して対話式インタフェースを提供することができる。
【発明を実施するための最良の形態】
【００１８】
本発明は、添付図面を参照して非制限的例を用いて説明する。
例示の実施の形態は、不完全電力管理とも呼ばれるものを利用する。実施の形態では、より多くのレジスタ共用から生じる改良された面積使用と、より多くのレジスタ共用にかかる、増大した電力管理コストとのトレードオフが利用される。
【００１９】
本発明の実施の形態は、成就するべき２つのサブタスクとして、モジュール割り付け（演算対機能ユニット結合）とレジスタ割り付け（変数対レジスタ結合）を有する高レベル合成のデータ経路割り付け最適化段階において有用である。改良された電力管理と使用するレジスタの数とのトレードオフコストを、電力管理コスト公式を通じて、好ましくはあらゆる割り付け段階において比較し、最適な割り付けをもたらす。開発者は、電力および面積制約条件、ならびにその関連の最適化優先順位を指示することによって、割り付け形式を決定することができる。さらに、開発者は、ループがコンパイラ指令によって高レベル抽象で反復される回数を知った上で、その割り付けに影響を及ぼすことができる。
【００２０】
電力管理に関し、面積のためのスプリアス電力のトレードオフは、あまり頻繁にはコールされないループ、すなわちあまり深くネストされていないループや滅多にコールされないループに対してはあまり重要ではない。また、面積に対するスプリアス電力のトレードオフは、電力消費が比較的少ない機能ユニットに対してもあまり重要ではない。このように、あまり頻繁にはコールされず、しかもあまり深くはネストされていないループにおける変数は、より頻繁にコールされ、より深くネストされているループと比較して、電力管理コストが少ない。これは、あまり頻繁にはコールされず、しかもあまり深くはネストされていないループにおける変数に向けた面積に対して電力をトレードするレジスタ割り付けを、それらが回路内の電力消散にあまり貢献しないものとして適合させる。
【００２１】
ユーザは、例えば高レベルＣ抽象における特定の基本ブロックのスイッチング率をユーザが特定できるコンパイラ指令を利用して、主たる実施の形態における割り付け処理において介在することができる。このコンパイラ指令によって、ユーザは、電力管理コストの割り当てがユーザが特定するものと比例した状態で、割り付け処理に影響を与えることが
できる。
【００２２】
上記実施の形態はまた、二連重み割り当てアルゴリズムを用いてデータ経路を割り付ける。割り付けられたレジスタの数は、グラフエッジに関連する重みに基づく二連重み割り当てによって自動的に決定される。これらの重みは、面積および電力コストや、特定の設計に対する面積および電力の相対的重要性を反映する重み係数を用いてモデリングされる。
【００２３】
電力管理および面積間のトレードオフは、データ経路割り付け処理において発見的に決定された電力および面積の重み係数と共にモデリングされる。これによって、不完全電力管理コストを公式化し、様々なデータ経路割り付け段階において低電力消散構造をもたらす割り付けを導く。
【００２４】
上記実施の形態を用いて、ＲＴＬ設計を繰り返し生成することが可能である。データ経路割り付け最適化における優先順位としての面積を有する回路に対して、最適なレジスタ共用を有する設計で反復が開始する。推定電力が開発者が特定する範囲内である場合、設計反復は終了する。その優先順位として電力を用いたデータ経路割り付け最適化に対して、ＲＴＬ設計は、最小限の電力消散でＲＴＬ設計を繰り返し生成し、その最初の解法として完全電力管理をもたらす。推定面積が、ユーザインタフェースにおいて開発者が特定する範囲内になると、設計段階が停止する。
【００２５】
図３は、特定された制約条件および最適化優先順位に基づくハードウェア設計を生成するための、本発明の実施の形態による動作に関する概略フローチャートである。
回路の行動記述を設ける（ステップＳ１０）。電力および面積の制約条件を入力する（ステップＳ１２）．これらは、機械、またはキーボードやグラフィックユーザインタフェース等のインタフェースを用いてユーザにより入力することも可能である。電力および面積の制約条件は、設計中の回路の最大許容電力消費および最大許容面積を特定する。最適化優先順位を入力する（ステップＳ１４）。最適化優先順位は、機械、またはキーボードやグラフィックユーザインタフェース等のインタフェースを用いてユーザにより入力することも可能である。最適化優先順位は、面積削減または電力消費低減のいずれがより重要であるかを特定する。
【００２６】
回路設計のための変数のスイッチング回数を設ける（ステップＳ１６）．これは一般に、高レベルアブストラクション入力（例えばＣ源）において、ＨＬＳコンパイラ等の行動合成ツールに回数を提供するコンパイラ指令によって行われる。ユーザによって規定さるか、またはコンパイラの上位段階によって計算可能なスイッチング回数は、不完全電力管理アーキテクチャにおいて生じるレジスタ共用によって導入されるスプリアス電力消散を計算する際に、リソース割り付け段階において使用する。
【００２７】
行動記述は、例えばＨＬＳコンパイラによって、入力制約条件および最適化優先順位を用いてオペランド解析される（ステップＳ１８）．中間表示もまた、周知の方法のうちのいずれかで最適化される（ステップＳ２０）。中間表示を最適化するのに共通の技術は、ソフトウェアパイプライン、ループアンローリング、命令対応スケジューリング、強制スケジューリング等を含む。これらの方法は、通常、中間表示を最適化するために連帯して適用される。データフローグラフ（ＤＦＧ）は、変数のスイッチング回数でスケジューリングされる（ステップＳ２２）。オペランド解析された記述がコンパイルされて、ＤＦＧをスケジューリングする。
【００２８】
最初の電力および面積重みづけを生成する（ステップＳ２４）。目標とする設計の最適化優先順位に基づいて、初期の最大重み係数を。より高い最適化優先順位に関連するコス
トに割り当て、初期の最小重み係数を、より低い最適化優先順位に割り当てる。このように、より高い優先順位の最適化判定基準に対して初期の割り付けを完全に偏倚させる。
【００２９】
現在の重み付けに対して、以下で述べるように、回路設計（ステップＳ２６）においてモジュールおよびレジスタが割り付けられ、提案したアーキテクチャをＲＴＬ設計の形態でもたらす（ステップＳ２８）。規定された入力制約条件に抗してアーキテクチャを評価する。この制約条件内に含まれるか（ステップＳ３０）？  制約条件のうちの一つを満たしていない場合には、その制約条件をより良く考慮して設計するために、重み付け係数を調整する（ステップＳ３２）。このように、アーキテクチャが面積の制約条件を満たさない場合には、面積重み付け係数を増大し、電力重み付け係数を減少させるか、またはそのいずれかである。この処理はステップＳ２６に戻って、評価するための新たなアーキテクチャを生成する。一方、ステップＳ３０で両方の制約条件を満たす場合、最終アーキテクチャとして現在のアーキテクチャで処理を停止する（ステップＳ３４）。このように、特定された制約条件を満たすと、ハードウェア生成および評価処理が停止する。
面積と電力との関係
図４は、回路設計のための面積に対する電力使用を示すグラフである。グラフ上の線と点とは電力使用と面積とが一般に互いに変化する様子を概略的に示す。レジスタ割り付けにおける最大ハードウェア共用と最小面積使用での設計点は、“Ｘ”で示される。電力管理の観点および最大面積使用に基づく最適設計点は“Ｏ”で示される。２つの線４０および４２は、（電力管理の観点からの）電力とレジスタ共用（および面積）の程度との潜在的トレードオフを例示する。
【００３０】
点曲線４０は、少ない方の電力および面積の典型的設計軌跡を例示しており、この場合、面積と電力とのトレードオフが注意深く管理されてはいない。実曲線４２は、現在の最適電力管理およびレジスタ共用が、レジスタを賢明に割り付けすることで達成される場合の典型的最適設計軌跡を例示する。破線４４は、例えば以下のようにループネスト情報のみを用いて、あまり最適ではない電力管理およびレジスタ共用を達成する場合の設計軌跡を例示する。
【００３１】
賢明なレジスタ割り付けでは、完全電力管理設計から偏向するための初期の努力の際には、電力増大に関する面積の削減が大きくなる。
あまり深くネストされていないループに関するアーキテクチャは、内部にネストされたループに関するものと比較して電力消散度を減少させる。最外部のループのためのレジスタ共用から生じるスプリアスアクティビティは、電力消散量を最小にする。このように、省面積のための電力をトレードオフするための試みは、最も使用されないアーキテクチャから始めるべきである。図５は、ネストされたループをいくつか有するループを示す。図５は、回路アルゴリズムを一回繰り返すために変数を使用する回数を例示する。最外部のネストされたループに対しては、ｎ回変数を使用する。第２のレベルのネストされたループに対して、変数をｍ*ｎ回スイッチングする。第３のレベルのネストされたループに対
して、ｎ*ｍ*ｋの割合で変数をスイッチングする、等である。電力使用への寄与は、変数を使用する割合に比例する。このように、レジスタ面積に対する電力をトレードする際に、不完全電力管理により、最もスイッチング回数の少ない変数が電力消散に最も貢献しないように共用するべきである。従って、トレードオフ曲線４２および４４は、完全に管理されたアーキテクチャに接近した設計点に対してはあまり急峻ではない。面積用電力をトレードする際に、あまり頻繁にはスイッチングされないレジスタを使い果すので、電力単位の面積のトレードオフコストが増大し、それによって設計が、完全に電力管理されたアーキテクチャからさらにかけ離れるように、トレードオフ曲線の勾配が増大することになる。
【００３２】
面積および電力管理間のトレードオフを最適化するための更なる管理を、データ経路割
り付けにおける変数のためのレジスタ共用により導入されたスプリアスアクティビティの量に貢献する要因を検査することにより可能となる。どのレジスタを共用して、共用使用により導入されるスプリアスアクティビティの量を削減するか割り付ける際に、より良い判断が行える。
【００３３】
機能ユニットに対するスイッチングが同等量であると仮定すると、入力ベクトルにおける同等の変化に対してあまりスイッチングを使用しない機能ユニット間でレジスタを共用することにより、スプリアスアクティビティを最小限に維持することが可能である。図６は、加算器（ＡＬＵ）とシフタとの間でのレジスタ共用を示す。加算器とシフタとの間の共通入力レジスタを共用することにより導入されたスプリアススイッチングからの電力消散は、シフタおよび乗算器候補間のスプリアススイッチングが同じであると仮定する図１でのように、加算器と乗算器との間で共通入力レジスタを共用することにより導入されるスプリアススイッチングによる電力消散よりもずっと少ない。
【００３４】
全てのレジスタに対して共用することにより導入されるスプリアスアクティビティの累積量をガイドラインとして用いて、異なる変数間のレジスタを共用するための最小電力損を達成する。最も費用効果のある共用により、図４に示すような実曲線４２設計軌跡を生じる。
【００３５】
このように、レジスタを賢明に割り付けて電力管理機構における面積用電力をトレードすることにより、開発者は、最適な電力―面積トレードオフ曲線に沿って、またはそれに対して、より接近して設計を行い、特定された制約条件内で電力および面積最小化の矛盾した目的物のバランスを取る。
コンパイラ指令
コンパイラ指令は、データ経路割り付け処理上で、より繊細な制御を回路開発者に与える。コンパイラ指令は、機能のソースコードの始めに挿入され、それによってユーザが、その特定の機能のスイッチングの割合を特定できる。このコメント（プログマ）機構によりユーザは、あまり頻繁にはコールされないループ内に配置された変数に向かって、面積に対して省電力をトレードオフするようにオプチマイザに指示を与えることができる。
【００３６】
このような指令の使用例が、図７に示されており、Ｃソースコードで書かれており、この場合、ユーザはコメント“＃ｐｒａｇｍａ  ｓｗｉｔｃｈ__ｉｔｅｒａｔｉｏｎ（Ｉｔｅｒａｔｉｏｎ_ｎｕｍｂｅｒ）”に対する反復数を割り当てることができる。コンパイ
ラは、開発者が特定のループ内でコンパイラ指令を挿入しない場合、周知の“Ｉｔｅｒａｔｉｏｎ_ｎｕｍｂｅｒ”でデフォルト値を割り当てる。このデフォルト値は、前に使用
した反復数、例えば全ての既知の反復数の平均（または最後の幾つか、例えば最後の５つの平均）から得られる。図７を参照すると、nが１００の場合、“Ｉｔｅｒａｔｉｏｎ_ｎｕｍｂｅｒ”は、コンパイラによって自動的に１００に割り当てられる。入力プログラム実行フローのより早いステップにおいてｎを割り当て、このnがコンパイラによって確定
できない場合には、コンパイラ指令によってユーザが割り当てた“Ｉｔｅｒａｔｉｏｎ_
ｎｕｍｂｅｒ”を用いて特定のループ内のスイッチングの割合を確立する。
【００３７】
電力管理コストの公式におけるこの情報の利用については、式３を参照して以下で述べる。
データ経路電力および面積最適化
電力および面積最適化は、特定の設定、すなわちｉ）最適化の優先順位（面積/電力）
；  ｉｉ）面積制約条件（例えば、面積単位ｍｍ2）および  ｉｉｉ）電力制約条件（例
えば電力測定単位μＷ）に従って自動的に行われる。
【００３８】
データ経路割り付けでは、スケジューリングが事前に行われると仮定する。割り付けに
対し、クロックおよび電圧は固定される。バス相互接続の様々な欠点のため、相互接続割り付けのためにマルチプレクサのみを使用する。
ｉ）  チップサイズが増大すると、２個の相互接続部が互いに離れて配置される可能性が増し、それらを組み合わせることによって、長距離にわたるバスを生成することも可能となる。頻繁に利用するバスの長さは、チップの寸法と共に線状に増大する傾向があり、それによって性能が損なわれ、さらにコストが増大する[エフ．ブルーワー（Ｆ．Ｂｒｅｗ
ｅｒ）およびディー．ガイスキー（Ｄ．Ｇａｊｓｋｉ）、“Ｃｈｉｐｐｅ：  制約条件付き駆動行動合成システム（Ａ  ｓｙｓｔｅｍ  ｆｏｒ  ｃｏｎｓｔｒａｉｎｔ  ｄｒｉｖｅｎ  ｂｅｈａｖｉｏｕｒａｌ  ｓｙｎｔｈｅｓｉｓ）”、ＩＥＥＥ  Ｔｒａｎｓ．  コンピュータ援助設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ）、第９巻、１９９０年７月]；さらに
ｉｉ）  バスアーキテクチャは、容易にはテストできない。
【００３９】
一般に、数少ない機能ハードウェアユニットと数少ないレジスタとが、配線コストをあまりかけずに設計を行うため、割り付けには平面情報は使用しない。これは、ダブリュ・イー・ドナス（Ｗ．Ｅ．Ｄｏｎａｔｈ）“演算論理の配置および平均相互接続長さ（Ｐｌａｃｅｍｅｎｔ  ａｎｄ  ａｖｅｒａｇｅ  ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ  ｌｅｎｇｔｈｓ  ｏｆ  ｃｏｍｐｕｔｅ  ｌｏｇｉｃ）”、ＩＥＥＥ  Ｔｒａｎｓ．回路およびシステム（Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ）、第２６巻、１９７９年４月；  ダブリュ・アール・ヘラー（Ｗ．Ｒ．Ｈｅｌｌｅｒ）、シー・ジー・ヒズ（Ｃ．Ｇ．Ｈｉｓ）およびダブリュ・エフ・ミクヘイル（Ｗ．Ｆ．Ｍｉｋｈａｉｌ）、“チップおよびチップパッケージ用配線可能性―設計配線スペース（Ｗｉｒｅａｂｉｌｉｔｙ  −  Ｄｅｓｉｇｎｉｎｇ  ｗｉｒｉｎｇ  ｓｐａｃｅ  ｆｏｒ  ｃｈｉｐｓ  ａｎｄ  ｃｈｉｐ  ｐａｃｋａｇｅｓ）”、ＩＥＥＥ  設計およびテスト（Ｄｅｓｉｇｎ  ａｎｄ  Ｔｅｓｔ）、第１巻、１９８４年８月；  “ＶＬＳＩレイアウトの面積推定技術（Ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  ａｒｅａ  ｅｓｔｉｍａｔｉｏｎ  ｏｆ  ＶＬＳＩ  ｌａｙｏｕｔｓ）”、ＩＥＥＥ  Ｔｒａｎｓ．コンピュータ援助設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ−Ｄｅｓｉｇｎ）、第８巻、１９８９年１月；  “結合問題を解決するための最適且つ発見的アルゴリズム（Ｏｐｔｉｍａｌ  ａｎｄ  Ｈｅｕｒｉｓｔｉｃ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｓｏｌｖｉｎｇ  ｔｈｅ  Ｂｉｎｄｉｎｇ  Ｐｒｏｂｌｅｍ）”、ミンジューング・リム（Ｍｉｎｊｏｏｎｇ  Ｒｉｍ）、アシュトシュ・ムジュムダー（Ａｓｈｕｔｏｓｈ
Ｍｕｊｕｍｄａｒ）、ラジブ・ジェイン（Ｒａｊｉｖ  Ｊａｉｎ）およびレナトー・デ・ロエン（Ｒｅｎａｔｏ  Ｄｅ  Ｌｏｅｎｅ）、ＩＥＥＥトランザクションズ・オン・ＶＬＳＩシステム（Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ＶＬＳＩ  Ｓｙｓｔｅｍｓ）、第２巻、第２号、１９９４年６月。
【００４０】
図３のフローチャートのステップＳ２６の一部である、データ経路割り付け問題を解決するための整数線形計画法（ＩＬＰ）公式においては、複数判定基準最適化を用いる。面積および電力を共同最適化するために使用するＩＬＰ公式は、以下の式１で表される。
【００４１】
【数３】
2008500631.tif 000003
【００４２】
ここで、
ｆpower（ｘ）は電力のコスト公式を表す、
ｆarea（ｘ）は面積のコスト公式を表す、
Ｃは｛レジスタ割り付けのための最大変数密度での最小数のレジスタの制約条件またはモ
ジュール割り付けのための最大演算密度における最小数の機能ユニットの制約条件を表す、
Ｋpowerはｆpower（ｘ）の重みを表す、
Ｋareaはｆarea（ｘ）の重みを表す。
【００４３】
各々の可能な割り付けに関連するコストを用いて、マトリックスを生成する。あらゆる演算、変数等が割り付けられる最小総コストである最良の結果は、ハンガリアン法によって見出される。
【００４４】
図８は、データ経路割り付けのための最適化機構の例を示しており、この場合は、面積の優先順位の方が高い。図９は、データ経路割り付けのための最適化機構の例を示しており、この場合は、電力の優先順位の方が高い。
【００４５】
図８に対して、初期の解決法の特徴としては、最大レジスタ共用によって最適面積を達成するデータ経路割り付けが挙げられる。このように、まず最初に、電力重み係数Ｋpowerを１に設定し、面積重み係数ＫareaをＭＡＸ_ＷＥＩＧＨＴに設定する（ステップＳ１０２  −  図３のステップＳ２４の具体例）。現在の重み付けに基づいて、データ経路割り付けを行う（ステップＳ１０４  −  図３のステップＳ２６およびＳ２８の一般化）。その後、ランダムな、または事前に選択された入力ビットパターン４０（ステップＳ１０６）、例えばＲＴＬ電力推定ツールや事前に特徴づけられたセルライブラリからの電力使用情報を用いて、回路の電力消散を推定する。推定された電力が、予め設定された電力制約条件未満であるかどうか判断する（ステップＳ１０８  −  図３のステップＳ３０の一部）。電力消散が電力制約条件を超えている場合、Ｋpowerを第１の発見的に決定されたス
テップ値αだけ増加させ、Ｋareaを第２の発見的に決定されたステップ値βだけ減少させる（ステップＳ１１０  −  図３のステップＳ３２の具体例）。新たな重み付けのために、データ経路割り付け処理（ステップＳ１０４）を繰り返す。推定された電力消散が、ステップＳ１０８による制約量未満である場合、例えばシノプシス（Ｓｙｎｏｐｓｉｓ）ＤＣコンパイラを用いて、現在の経路割り付けのための面積を推定する（ステップＳ１１２）。面積が、予め設定された面積制約条件未満であるかどうか判断する（ステップＳ１１４）。面積が許容面積を超える場合には、入力した制約条件に対する解法は存在せず（Ｓ１１６）、処理は終了する。面積が許容範囲内である場合、現在のデータ経路割り付けを出力し（Ｓ１１８）、処理を終了する。
【００４６】
シミュレーションを各々反復するために使用するステップ値を決定するための発見的方法の例を、以下に示す。
まず第１に、コスト（式１のｆpower（ｘ）およびｆarea（ｘ））との乗算に関して（
３２ビットよりも多い）オーバフローを生じないように、ＫareaおよびＫpowerの両方に
対する最大値を選択する。本実施の形態では、ＫareaおよびＫpowerの最大値は、上限を
１０００に設定する。２つの極限設計、すなわち一方はＫareaが１に設定され、Ｋpower
が最大重み（１０００）に設定され、他方はＫareaが最大重み（１０００）に設定され、Ｋpowerが１に設定される設計に必要なレジスタの数の差を、２つのシミュレーションを
実施することによってまず決定する。これら２つの設計構成（一方は完全電力管理機構に対する設計構成、他方は最も不完全な電力管理機構に対する設計構成）に対するレジスタの数の差は、最大結果範囲を最適化スペース全体におけるシミュレーションによって達成可能なレジスタ数で示す。この範囲は、最適化結果の差を示す。
【００４７】
重み領域（１から最大値、すなわち本実施の形態では１０００）をまずＮ個の領域に分割する。この場合、各々の最適化軌跡領域に使用する制約条件が、各々の特定重み領域に対するシミュレーションを開始する前に決定される。Ｎは、望ましい精度が高くなると、大きくなる。本実施の形態において、Ｎには４が選択されており、重み領域は、ステップ
値αおよびβに対して｛１，２５０，５００，７５０，１０００｝に（ほぼ）均一に分割される。第１の値としては１を使用するため、極端な設計最適化のために、優先順位がより低い目的物（電力または面積）をさらに考慮する。あまり重要ではない目的物に対する重みとして０を割り当てると、コンパイラは、より重要な目的物の候補に対して同じだけのコストがかかる全ての場合に、あまり重要ではない目的物を最適化する割り付けを実施しない。
【００４８】
２個の第１の領域の交差部、すなわち本実施の形態における（Ｋareaは２５０およびＫpowerは７５０）であるという重み設定において必要とされるレジスタの最大数を、最初
に決定する。第１の領域に対する結果範囲は、この交差部で必要とされる最大レジスタ数と初期の重み設定（１，１０００）に対して得られる最大レジスタ数との差から得られる。その後、第１の領域に対する結果範囲は、２個の限界設計軌跡での設計から得られる最大結果範囲（すなわち、（１，１０００）から（１０００，１）までの結果範囲）によって正規化される。この第１の領域に対するシミュレーションを反復するために選択されたステップ値は、正規化された結果範囲を望ましく正規化された変化のステップに均等に分割することにより得られる（すなわち、各ステップは、レジスタの数を結果範囲のある一定の小数部に変化させるべきである）。この場合、重みと結果とは線状の関係があると仮定する。例えば、第１の領域｛（１，１０００），（２５０，７５０）｝に対する結果範囲が１０％、すなわちシミュレーション結果｛（１，１０００），（１０００，１）｝の最大範囲である０．１であり、０．０２が各反復に対して望ましい結果において望ましく正規化された変化である場合（すなわち、レジスタの数は、（１，１０００）から（１０００，１）までの結果範囲におけるレジスタ数の２％だけ変化するべきである）、各反復に対するステップ値は、２５０の５分の１（０．０２/０．１）、すなわちαおよびβに
対して５０に設定される。
【００４９】
好適な経路割り付け解法が第１の領域｛（１，１０００），（２５０，７５０）｝内では決定されない場合、第２の領域｛（２５０，７５０），（５００，５００）｝に対して新たな組のステップ値が決定され、必要に応じて第３および第４の領域に対しても同様である。
【００５０】
上記発見的方法によれば、ステップ値αおよびβは、発見的決定の結果に従ってあらゆる反復（第１の領域に対する最初の５つの後）を変化させる傾向にある。あるいは、ステップ値は、定数、例えばαおよびβの両方を通じて５０に維持することも可能である。ステップ値αおよびβは同じである必要はない。
【００５１】
同量の省電力に対する初期の面積トレードオフは小さく、図４の点“Ｘ”から設計が離れるにつれて徐々に増加する。これは、最も頻繁に使用する変数が初期のトレードオフにおいてレジスタを共用しないように妨げられ、それによって固定面積単位に対して省電力を増加させることによる。予め規定された電力制約条件を満たすと、設計反復が停止する。この機構の効果としては、最大限可能な省電力が、予め規定された電力制約条件を満たすために最小面積がトレードオフされている最適面積を有するアーキテクチャが挙げられる。
【００５２】
図９は、最適化における優先順位としての電力を有する機構を示す。初期の解決法の特徴としては、完全電力管理を有するデータ経路割り付けが挙げられる。Ｋareaを１に設定し、ＫpowerをＭＡＸ_ＷＥＩＧＨＴに設定する（ステップＳ１２２  −  図３のステップＳ２４の具体例）。現在の重み付けに基づいて、第１のデータ経路割り付けを行う（ステップＳ１２４  −  図３のステップＳ２６およびＳ２８の一般化）。例えばシノプシス（Ｓｙｎｏｐｓｉｓ）ＤＣコンパイラを用いて、生成したＲＴＬの面積を推定または分析する（ステップＳ１２６）。面積が、予め設定された面積制約条件未満であるかどうか判断
する（ステップＳ１２８  −  図３のステップＳ３０の一部）。面積が面積制約条件を超えている場合、Ｋpowerを第１の発見的に決定されたステップ値αだけ減少させ、Ｋarea
を第２の発見的に決定されたステップ値βだけ増加させる（ステップＳ１３０  −  図３のステップＳ３２の具体例）。データ経路割り付け処理（ステップＳ１２４）を、新たな重み付けのために繰り返す。面積が、ステップＳ１２８による制約量未満である場合、現在のデータ経路割り付けに関連する電力消散を推定する（ステップＳ１３２）。ランダムな、または事前に選択された入力ビットパターン４０および予め特徴づけられたセルライブラリからの電力使用情報を、例えばＲＴＬ電力推定ツールによって使用する。推定された電力消散が、予め設定された電力制約条件未満であるかどうか判断する（ステップＳ１３４）。推定された電力が許容電力を超えている場合、入力した制約条件に対する解法は存在せず（Ｓ１３６）、処理は終了する。推定した電力が許容電力の範囲内である場合には、現在のデータ経路割り付けを出力し（Ｓ１３８）、処理を終了する。
【００５３】
ステップ値は前記と同じように、または他の方法で計算することも可能であり、また定数に維持することも可能である。
固定した面積単位に対する電力のトレードオフコストは、設計が最適電力を有する図４の点“Ｏ”から離れるにつれて徐々に増加する。これは、最も使用されない変数をレジスタ共用において利用して、最初に面積に対して電力をトレードオフし、それによって不完全管理アーキテクチャに対する最小電力消散を犠牲にすることによる。最も使用されないアーキテクチャを犠牲にして、面積に対して電力をトレードオフするにつれて、同じ面積単位に対する電力のトレードオフコストが増加する。設計機構により、最小電力が最大省面積に対してトレードオフされた最適な電力管理アーキテクチャが生じ、予め規定された面積制約条件を満たす。
データ経路割り付けプログラム
図１０は、例えば、ステップＳ１０４およびＳ１２４において、図８および図９を参照して上で述べた処理においてそれぞれ使用するように、ＩＬＰ公式（式１）によって記述された制約条件を満たすためのデータ経路割り付け処理を示すフローチャートである。データ経路割り付け内で実施するべきサブタスクは、モジュール割り付け（演算対機能ユニット結合）およびレジスタ割り付け（変数対レジスタ結合）である。本実施の形態では、モジュール割り付けを実施した後、レジスタ割り付けを行うが、同時に、または他の行程で行っても良い。
【００５４】
あらゆる変数に対する演算データ、すなわち変数を使用する（Ｏｐ_宛先）演算に対し
て（Ｏｐ_源）変数を得る演算に関する情報を収集する（ステップＳ２０２）。あらゆる
演算に対する変数データ、すなわちあらゆる演算によって使用され導かれる変数に関する情報を収集する（ステップＳ２０４）。あらゆる変数に対する演算データの分析から、あらゆる変数に対して生成時間と消滅時間とが割り当てられる（ステップＳ２０６）。生成時間と消滅時間は、あらゆる演算に割り当てられる（ステップＳ２０８）。
【００５５】
演算は必要な機能に従って、すなわちモジュール形態によりまずグループ分けされる。同一のモジュール形態を必要とする演算、すなわち同一の機能ユニットを共用することが可能な演算は、その生成時間および消滅時間（生成および消滅に基づく）によりクラスタリングされる（ステップＳ２１０）。演算は、その生成時間に従って下から順に、まずソートされる。相互に共用不可能な演算のクラスタを、ソートされた順に従って割り付ける（その生存期間がオーバラップする場合やその場合のみに２つの演算を共用できない）。必要な各形態のモジュールの数を、決定する（ステップＳ２１２）。各々の潜在的なモジュール形態に対して、必要な数は、その形態のモジュールを共用できる演算の最大数であり、この演算は、いずれかの制御ステップにおいて同時に行われる。各形態のモジュールの総数は、そのモジュール形態を利用するいずれかの演算クラスタでの演算の最大数以上であっても良い。その際、異なる演算にモジュールを割り付ける（Ｓ２１４）。
【００５６】
（生成および消滅に基づく）生成時間および消滅時間に従って、変数をクラスタリングする（ステップＳ２１６）。変数はまず、その生成時間に従って下から順にソートされる。同一レジスタを共有するのが不可能な変数のクラスタは、ソートされた順序に従って割り付けられる（２個の変数は、それらの生存期間がオーバラップする場合およびその場合にのみ、同一レジスタを共有することが不可能である）。必要なレジスタの数が決定される（ステップＳ２１８）。必要な数は、いずれかの制御ステップにおいて同時に存在する変数の少なくとも最大数である。レジスタの総数は、いずれかのクラスタにおける変数の最大数以上であっても良い。その際、レジスタは異なる変数に割り付けられる（Ｓ２２０）。
【００５７】
モジュールを割り付けるステップの例（図１０のステップＳ２１４）を、図１１を参照して以下で述べる。
モジュー形態は全て、モジュール形態番号が割り付けられている。共通機能ユニットを共有することが可能なモジュールは、同一モジュール形態に従ってグループ分けされる。同一モジュール形態のモジュールは全て、同一待ち時間（生成から消滅までの時間）を有する。モジュール形態に割り付けられるモジュール形態番号は、待ち時間の長い順から割り付けられる。すなわち、最長待ち時間のモジュール形態はモジュール形態番号が一番小さく（すなわち０）、最短待ち時間のモジュール形態はモジュール形態番号が一番大きい。同一待ち時間のモジュール形態に、異なる連続番号をランダムに割り付ける。同様に、各モジュール形態に対する演算の各クラスタに番号を割り付ける。
【００５８】
割り付ける第１のモジュール形態、すなわちモジュール形態＝０を設定してモジュール割り付け処理を開始する（ステップＳ３０２）。現在のモジュール形態番号が、直前の（最も大きいと思われる）モジュール形態番号よりも大きいかどうかを調べる（ステップＳ３０４）。現在のモジュール形態番号が直前のモジュール番号よりも大きくない場合には、現在のモジュール形態に対して、現在の演算クラスタ番号を０に設定する（ステップＳ３０６）。現在のモジュール形態に対する現在の演算クラスタ番号における演算は全て、現在のモジュール形態の異なる機能ユニットに割り当てられる（ステップＳ３０８）。現在のクラスタにおける演算待ち時間の長い順に、モジュールを割り付ける。その後、現在の演算クラスタ番号を１だけ増加する（ステップＳ３１０）。
【００５９】
現在の演算クラスタ番号が直前の（最も大きい）演算クラスタ番号よりも大きいかどうかを調べる（ステップＳ３１２）。現在の演算クラスタ番号が直前の演算クラスタ番号よりも大きい場合、現在のモジュール形態番号を１だけ増加させ（ステップＳ３１４）、処理をステップＳ３０４に戻す。新たな現在のモジュール形態番号が直前のモジュール形態番号よりも大きくない場合、この次のモジュール形態のモジュールを使用する第１の演算クラスタにおける演算が、この次の形態のモジュールに割り付けられる（ステップＳ３０８）。
【００６０】
現在の演算クラスタ番号が、ステップＳ３１２において直前の演算クラスタ番号よりも大きくない場合には、モジュール割り付けのためにマトリックスまたはグラフを構成する（ステップＳ３１６）。マトリックスまたはグラフは、（第１の演算クラスタおよびこれまでに処理された他のいずれかの演算クラスタに対する）モジュールおよび現在の演算クラスタ番号の既存の割り付けに基づくものである。いかなる割り付け問題も解決され（ステップＳ３１８）、現在のモジュール形態に対してこれまで処理されてきた全てのクラスタに対する割り付けを行う。
【００６１】
その後、現在の演算クラスタ番号を１だけ増加し（ステップＳ３２０）、ステップＳ３１２に処理を戻す。
モジュール割付処理が、全てのモジュール形態を通じて一旦循環すると、ステップＳ３０４によって、モジュール形態番号が直前または最も大きいモジュール形態番号よりも大きく、しかもモジュール割り付け処理が全てのモジュール形態に対してモジュール割り付け（ステップＳ３２２）を出力することがわかる。
【００６２】
モジュール割り付けが、待ち時間の長い順に演算に対して行われる。これは、生存期間がオーバラップしたモジュールの機会が、より短い待ち時間と比較して、より長い待ち時間の演算に対してより多くなる理由による。待ち時間がより短い演算に対しては、より長い待ち時間の演算に対して割り当てられた実際の機能ユニットが、むしろ演算自体よりも分析に用いられる。
【００６３】
共用可能な機能ユニットの演算は、二連重み付き割り当てを用いて機能ユニットにクラスタ毎に割り当てる。突合せ問題を解決するために、重み付き二連グラフＷＢ＝（Ｓ，Ｔ，Ｅ）を構成する。ここでは、グラフの各頂点ｓi∈Ｓ（ｔj∈Ｔ）は演算ｏｐi∈ＯＰ（
機能ユニットｆｕj∈ＦＵ）を表し、ｏｐiがｆｕjに割り当て可能である（すなわち、既
にｆｕjに結合されている演算はいずれも、生存期間がｏｐiとはオーバラップしない）場合またその場合にのみ、ｓiとｔjとの間の重み付きエッジｅijが存在する。エッジｅijに関連する重みｗijを、面積および電力コスト公式やそれぞれの関連する重み係数に従って（式１を用いて、しかも式２および式３を参照して以下で述べるように）計算する。あらゆるモジュールクラスタの割り付けは、例えば表２を参照して以下で述べるように、重み付き二連グラフに関する突合せ問題としてモデリングされ、周知のハンガリアン法によって解決する[シー・エイチ・パダディミトリオウ（Ｃ．Ｈ．Ｐａｄａｄｉｍｉｔｒｉｏｕ
）およびケー・スタイグリッツ（Ｋ．Ｓｔｅｉｇｌｉｔｚ）、組み合わせ最適化（Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ｏｐｔｉｍｉｓａｔｉｏｎ，プレンティス-ホール（Ｐｒｅｎｔ
ｉｃｅ−Ｈａｌｌ）、１９８２）。
【００６４】
グラフエッジの電力および面積コストを、コスト用重み係数として割り当てられた重みと線状に組み合わせる。その後、二連重み付け割り当てを行う。
レジスタを割り付けるステップの例（図１０のステップＳ２２０）について、図１２を参照して以下で述べる。
【００６５】
現在の変数クラスタ番号を０に設定する（ステップＳ３５２）。現在の変数クラスタにおける全ての演算を、異なるレジスタに割り当てる（ステップＳ３５４）。その後、現在の変数クラスタ番号を１だけ増加する（ステップＳ３５６）。
【００６６】
現在の変数クラスタ番号が直前の変数クラスタ番号よりも大きいかどうかを調べる（ステップＳ３５８）。ステップＳ３５８において、現在の変数クラスタ番号が直前の変数クラスタ番号以下である場合、レジスタ割り付けに対してマトリックスまたはグラフを構成する（ステップＳ３６０）。マトリックスまたはグラフは、（第１の変数クラスタおよびこれまでに処理された他のいずれかの変数クラスタに対する）レジスタの既存の割り付けおよび現在の変数クラスタに基づくものである。いずれかの割付問題を解決して（ステップＳ３６２）、これまでに処理された全ての変数クラスタに対する割り付けを行う。
【００６７】
その後、現在の変数クラスタ番号を１だけ増加し（ステップＳ３６４）、処理をステップＳ３５８に戻す。そこから、次の変数クラスタに対するレジスタ割付を実施することが可能となる。その場合、次の変数クラスタ番号は、最も大きい変数クラスタ番号以下である。
【００６８】
一旦レジスタ割り付け処理が全ての変数クラスタを通じて循環すると、ステップＳ３５８により、変数クラスタ番号が直前の（最も大きい）変数クラスタ番号よりも大きく、し
かもレジスタ割り付け処理が、レジスタ割り付けを出力する（ステップＳ３６６）。
【００６９】
また、二連重み付き割り当てを用いてクラスタ毎に変数をレジスタに割り当てる。各レジスタクラスタの割り付けもまた、重み付き二連グラフに関する突合せ問題としてモデリングされ、周知のハンガリアン法によって解決される。二連重み付き割り当てが入力ＤＦＧにおける全ての演算および変数に対して実施された状態で、その後、生成されたＲＴＬ設計をユーザ規定の入力制約条件に抗して評価することが可能となる。
【００７０】
レジスタサブセットにおける新たなノードの数を変数サブセットにおけるノードの数に等しく割り当てることにより、資源割り当てにおいて使用するレジスタの数を自動的に決定することが資源割り付けによって可能となる。特定の割り付けに必要なものよりも多いレジスタ数によって、電力管理がより良く行われることになる。割り付けるレジスタの総数は、特定の対の重み係数やそれに関連する面積および電力エッジコスト公式に対する二連重み付き割り付けの結果により、決定する。
コスト公式
モジュール割付  −  面積コスト計算（図１１のステップＳ３１６）
モジュール割り付けにおいて変化可能な関連の面積コストのみは、マルチプレクサ（ＭＵＸ）の数に影響する。従って、モジュール割り付けにおいては、式１を用いた面積ｆarea（ｘ）のコスト公式を以下のように定める：
ｆarea（ｘ）＝  （マルチプレクサ面積コストの合計）    [２]
これを実現するために、可能な限り常に機能ユニットを共用する。電力管理を完璧に行うために余分のレジスタを設けることもできるレジスタ割り付けとは異なり、余分の機能ユニットは割り付けない。モジュール割り付け段階は、機能ユニットの共用方法を定めるためのものであるため、その入力およびレジスタ入力において、ＭＵＸ電力利用が最も少なく、しかも最良の電力管理構成を生成することになる。
【００７１】
レジスタおよび機能ユニットへの入力におけるマルチプレクサ（ＭＵＸ）の数は、二連重み付き割り当て目標を利用することによって抑える。演算の入力および出力変数に対するＭＵＸ面積の必要条件は、図１１のステップＳ３１６に対して生成するように、以下の式３で示されるモジュール割り付け面積コスト公式ｗijにおいて評価される。機能ユニットに対する演算の割り付け全てに対して、式３を用いて、まずレジスタへの入力において受ける明示ＭＵＸコストを評価する（レジスタ割り付け段階まではレジスタを割り付けないが、モジュール割り付け段階ではレジスタの必要性が認識され、それに応じて総コストの見積もりが可能である）。その後、式３を用いて機能ユニットへの入力において受ける暗黙コストを計算する。
【００７２】
【数４】
2008500631.tif 000004
【００７３】
ここで、ｉおよびｊは、それぞれ比較する際の演算候補およびモジュールの指標を表す；ｖａｒiおよびｖａｒjは、変数（演算への入力または出力）を表す；
ＣMUXは、ＭＵＸの推定コストを表す（例えば、ＭＵＸビット幅に基づく）；
ＭＡＸは、演算が同一機能ユニットを共用することができないため突合せが不可能である場合に割り当てられた最大値を表す（値はあまり大きくするべきではないため、指示されたコストによってオーバフローが生じる）；
Ｏｖｅｒｌａｐ（）は、変数、または変数が入力変数である場合に変数が生じる演算、または変数が、出力変数に対してパスする演算の生存期間がオーバラップする場合は１であ
り、その他の場合には０である；
ｏｐiおよびｏｐjは、それぞれ比較する際の演算候補およびモジュールの過去に割り付けられた演算を表す；
Ｏｐは、変数がモジュールへの入力変数である場合に変数が生じる演算または変数がモジュールからの出力変数に対してパスする演算を表す。
【００７４】
モジュールの入力への入力においては、モジュールにパスする変数が、異なる演算から生じる場合に、明示ＭＵＸコストがかかる。モジュールからの出力においては、他の組み合わせよりも優先的に共通機能ユニットへパスするモジュールの共用を促進するために、共通機能ユニットにパスしない組み合わせに暗黙ＭＵＸコストを割り当てる。これは、共通機能ユニットにパスする演算が異なるモジュールに割り当てられる場合に、ＭＵＸコストがかかるためである。ＭＵＸコストは、必ずしもかかるわけではないので、すなわちいずれの組み合わせも共通機能ユニットにパスする変数から構成されない場合、この時点では単に暗黙的なものである。しかし、実際にコストがかかるかどうかは、特定のモジュール割り付けを選択してレジスタが割り付けられるまで決定されない。従って、暗黙コストが不確定な場合には、他の実施の形態ではそれを無視することもできる。
【００７５】
演算の生存期間がオーバラップする場合、モジュールは共用できない。従って、結果は常に最大となる。
Ｏｖｅｒｌａｐ（ｏｐi，ｏｐj）＝  １  従って
【００７６】
【数５】
2008500631.tif 000005
【００７７】
となる。このように、結果のみが  １  *  ＭＡＸ  ＝  ＭＡＸ  となり得る。
演算にオーバラップ生存期間がない場合には、Ｏｖｅｒｌａｐ（ｏｐi，ｏｐj）＝  ０となる。従って、Ｏｖｅｒｌａｐ（ｏｐi，ｏｐj）  *  ＭＡＸ＝  ０となる。しかし、
ＭＵＸ面積コストがいまだに存在する可能性もある。これは、演算の変数にオーバラップ生存期間があるかどうか、演算にオーバラップ生存期間があるかどうか、また２つの変数に対して同一演算を用いるかどうかによる。
【００７８】
演算の変数にオーバラップ生存期間がある場合、Ｏｖｅｒｌａｐ（ｖａｒi，ｖａｒj）＝  １となる。後続または先行する演算にオーバラップ生存期間がある場合には、
【００７９】
【数６】
2008500631.tif 000006
【００８０】
となる。従って、
【００８１】
【数７】
2008500631.tif 000007
【００８２】
となる。後続の、または先行する演算または変数に、オーバラップ生存期間があり、その時、演算にはオーバラップ生存期間がない場合には、その結果は１*  １  *  ＣMUX  ＝
ＣMUX  となる。
【００８３】
同一演算を使用する場合には、（Ｏｐi＝＝Ｏｐj）＝１となる。演算にオーバラップ生存期間がなく、変数にもオーバラップ生存期間がない場合には、
【００８４】
【数８】
2008500631.tif 000008
【００８５】
となる。従って、
【００８６】
【数９】
2008500631.tif 000009
【００８７】
となる。それ故、ＭＵＸ面積コストはゼロになる。
変数にオーバラップ生存期間がある場合には、共通レジスタを共用できないため、ＭＵＸが必要となる。変数にオーバラップ生存期間がない場合には、変数は共通レジスタを共用することができる。共用されるレジスタへの入力においては、レジスタに割り当てられた変数が共通機能ユニットに続く場合にＭＵＸコストを回避する。これは、変数が機能ユニットを共用することが可能な類似の演算に続き、しかもこれらの演算にオーバラップ生存期間がない場合にのみ可能性がある。機能ユニットへの入力においては、機能ユニットへの入力変数が共通のレジスタに割り当てられた場合、ＭＵＸコストが回避される。
モジュール割り付け電力コスト公式（図１１のステップＳ３１６）
モジュール割り付けにおいて変化可能な関連の電力コストは、マルチプレクサ（ＭＵＸ）および電力管理コストの割付に依存する。このように、モジュール割り付けにおいて、式１で用いる電力のコスト公式ｆpower（ｘ）を以下のように定める。
ｆpower（ｘ）＝（電力管理コストの合計）＋（マルチプレクサ電力コストの合計）  [４]
ＭＵＸによるモジュール割り付けにおける総電力増加は、ＭＵＸ面積増加に比例する。ＭＵＸ面積増加は、上記式３から得られる。
【００８８】
先行の演算クラスタにおける同種の演算に割り当てられた機能ユニットを共用することが可能な同一演算に対して、電力管理コストを計算する。電力管理コスト計算において満たすべき前提条件は、レジスタを共用するための候補である出力変数の生存期間がモジュールの過去の割り付けの出力変数とはオーバラップしないことである。その理由は、意図されたレジスタ割り付けでモジュール割付を行うため、レジスタ割り付けにおける最良の電力管理を許容するように機能ユニットが割り付けられるからである。
【００８９】
電力に関連するコストの公式は、レジスタを共用することによって導入されるスプリアスアクティビティの計算を必要とする。これは、共用する際に必要となる変数のスイッチングアクティビティや、変数が共通レジスタを共用するべき場合に共用されるレジスタに接続される機能ユニットに変数によって導入されるスプリアス電力消散を考慮することによって達成される。スイッチングアクティビティに関する情報は、例えばコンパイラ指令を用いて設計者によって提供することも可能であり、また上記のように自動的に提供することも可能である。第１の変数によって導入されるスプリアスアクティビティは、第１の変数が共にレジスタを共用する他の変数の演算の電力量が乗算されたその第１の変数のスイッチングアクティビティから計算される。モジュール割り付けは、この情報を利用して、レジスタの割り付けに有利となるようにモジュールを共用する。
【００９０】
【数１０】
2008500631.tif 000010
【００９１】
ここで、
Ｖａｒ１は、その宛先演算に対する第１の入力変数を表す；
Ｖａｒ２は、その宛先演算に対する第２の入力変数を表す；
ＳＡは、全ての変数に関する変数のスイッチングアクティビティを表す；
ｎは、宛先演算の数を表す；
Ｐｏｗｅｒは、他の変数の宛先演算（スプリアスアクティビティ）のいずれのものとも共用できない演算の正規化された電力消費を表す。
【００９２】
レジスタは、それに対する入力が変化する時に切り替わる。しかし、機能ユニットの出力が切り替わる場合の電力消費全体に対して、出力が共用されているレジスタにラッチされているか、または共用されていないレジスタにラッチされているかに拘らず、レジスタの電力消費は、今までどおり同じ状態を維持する、すなわち１個のレジスタを切り換えなければならない。一方、存在するマルチプレクサは電力を消費し、これらによって全電力消費に効果的となる。電力管理コストは、不必要な機能ユニットスイッチングにのみ関連するコストである。これらは、レジスタスイッチングまたはマルチプレクサスイッチング電力損には関係ない。
【００９３】
図１および図６を参照すると、この式５の公式は、モジュールの割り当てを電力管理コストを低減するものに適応させる。変数Ａの宛先演算は、ＡＤＤＥＲ（ＡＬＵ）である。変数ＢおよびＣは、ＭＵＬＴＩＰＬＩＥＲおよびＳＨＩＦＴＥＲの宛先演算をそれぞれ有する。変数ＢおよびＣのスイッチングレートは、変数Ａに対するものと同じである。割り付けタスクは、低減した電力管理コストに有利となる。変数Ａが変数Ｂの代わりに変数Ｃと共通レジスタを共用する場合には、ＰｏｗｅｒshifterがＰｏｗｅｒmultiplierより低
いため、電力管理コストが低減する。
【００９４】
さらに式５を参照すると、変数１の宛先演算が変数２の宛先演算と同じであり、２つの演算にはオーバラップ生存期間がない（すなわち、同一の機能ユニットによって２つの演算を実施することが可能である）場合、レジスタ共用によってはスプリアスアクティビティが導入されないため、電力管理コストがかからない（すなわち、式５の右側にある両方の構成要素に対しては、“Ｐｏｗｅｒi”がゼロである）。
【００９５】
前記のように、スイッチングアクティビティは、前記のようなプログラムの内部のネストされたループと比較して、外部のネストされたループに対して低減する。このように、式５の公式は、省面積のための不完全な電力管理のトレードオフをよりアクティブではないループに適合させる。
レジスタの割り付けのための面積および電力に対するコスト公式（図１２のステップＳ３６０）
レジスタ割り付けに対する面積およびコスト公式は、上記の式３および５を参照して述べたものと同じである。コスト公式において使用する演算は、モジュール割り付けによって割り当てられた機能ユニットと置き換えられる。
レジスタ割り付け  −  面積コスト計算
レジスタ割り付けにおいて変化可能な関連の面積コストは、マルチプレクサ（ＭＵＸ）の数とレジスタの数に依存する。このように、レジスタ割り付けにおいては、式１で使用する面積のコスト公式ｆarea（ｘ）を以下のように決定する：
ｆarea（ｘ）＝（マルチプレクサ面積コストの合計）＋（レジスタ面積コストの合計）  [６]
レジスタが、異なる機能ユニットからパスする２個の変数によって共用される場合、ＭＵＸコストがかかる。同様に、２個の変数が共通機能ユニットにパスするが、同一レジスタを共用しない場合、ＭＵＸコストがかかる。割り付けられたレジスタの入力および出力変数に対するＭＵＸ面積の必要条件は、以下の式７ａおよび７ｂに示すレジスタ割り付け面積コスト公式ｘijにおいて査定される。
【００９６】
レジスタが既に割り付けられている場合、式７ａをまず用いて、レジスタへの入力においてかかる明示ＭＵＸコストを査定する。その後、式７ａをさらに用いて、レジスタからの出力および機能ユニットへの入力においてかかる暗黙コストを計算する。
【００９７】
【数１１】
2008500631.tif 000011
【００９８】
ここで、
ｉは、現在の割り付けにおいてレジスタに割り付けられる変数を表す；
ｊは、レジスタを共用する場合、前のレジスタ割り付けにおけるレジスタに既に割り当てられている変数の一つを表す；
ＣMUXは、（例えば、ＭＵＸビット幅に基づく）ＭＵＸの推定コストを表す；
ＭＡＸは、変数が同一レジスタを共用できないため、突合せが不可能である場合に割り当てられた最大値を表す（値はそれほど大きくないため、示されたコストがオーバフローを生じる）；
Ｏｖｅｒｌａｐ（）は、変数または変数がパスする機能ユニットにオーバラップ生存期間がある場合は１であり、他の場合は０である；
ｆｕは、変数がレジスタからパスするか、または変数がレジスタにパスする、割り付けられた機能ユニットを表す。
【００９９】
レジスタへの入力においては、レジスタにパスする変数が異なる機能ユニットから生じる場合、明示ＭＵＸコストがかかる。レジスタからの出力においては、他の組み合わせよりも優先的に共通機能ユニットへパスする変数に対するレジスタの共用を促進するために、共通機能ユニットにパスしない組み合わせに暗黙ＭＵＸコストを割り当てる。これは、共通機能ユニットにパスする変数が異なるレジスタに割り当てられる場合に、ＭＵＸコストがかかるためである。コストは、例えば、いずれの組み合わせも共通機能ユニットにパスする変数から構成されない場合には必ずしもかかるわけではないため、暗黙的である。しかし、コストが実際かかるかどうかは、クラスタ全体に対するレジスタが割り付けられるまで決定されない。従って、暗黙コストが不確定な場合には、他の実施の形態ではそれを無視することもできる。
【０１００】
変数ｉおよびｊにオーバラップ生存期間がない場合、Ｏｖｅｒｌａｐ（ｉ，ｊ）＝１となる。従って、
【０１０１】
【数１２】
2008500631.tif 000012
【０１０２】
となる。このように、結果は常に少なくとも１*ＭＡＸ＝ＭＡＸとなる。
変数ｉおよびｊにオーバラップ生存期間がない場合、Ｏｖｅｒｌａｐ（ｉ，ｊ）＝０となる。従って、Ｏｖｅｒｌａｐ（ｉ，ｊ）*  ＭＡＸ＝０となる。しかし、ＭＵＸ面積コ
ストは今まで通りかかる可能性がある。これは、演算にオーバラップ生存期間があるかどうか、また同一機能ユニットが両方の変数に割り付けられているかどうかによる。
【０１０３】
変数ｉおよびｊに対する機能ユニットにオーバラップ生存期間がある場合には、
【０１０４】
【数１３】
2008500631.tif 000013
【０１０５】
となる。従って、
【０１０６】
【数１４】
2008500631.tif 000014
【０１０７】
となる。その時、変数ｉおよびｊにオーバラップ生存期間がない場合には、結果は１*１*ＣMUX＝ＣMUXとなる。
変数ｉおよびｊに対する２個の機能ユニットが同じである場合には、（ｆｕi＝＝ｆｕj）＝１となる。変数ｉおよびｊに対する機能ユニットにオーバラップ生存期間がない場合には、
【０１０８】
【数１５】
2008500631.tif 000015
【０１０９】
となる。従って、
【０１１０】
【数１６】
2008500631.tif 000016
【０１１１】
となる。それ故、共用レジスタによるＭＵＸ面積コストがゼロである。
かかる暗黙的コストを査定すると、前のレジスタ割り付けにおける異なるレジスタに既に割り付けられている変数ｊと同じ機能ユニットにまたはそこから変数ｉがパスする場合、暗黙的コストは（ｆｕi＝＝ｆｕj）*ＣMUX＝１*ＣMUX＝ＣMUXとなる。
【０１１２】
割り付けられていないレジスタ、すなわち新たに割り付けられたレジスタの入力および出力変数に対するＭＵＸ面積必要条件は、以下の式７ｂに示すレジスタ割り付け面積コスト公式ｘijにおいて査定される。
ｘij  ＝  [（（ｆui＝＝ｆｕj））*  ＣMUX]            [７ｂ] 
同一機能ユニットにパスする変数が共通レジスタを共用しない場合には、ＭＵＸコストがかかる。
レジスタ割り付け  −  電力コスト計算
レジスタ割り付けにおいて変化可能な関連の電力コストは、マルチプレクサ（ＭＵＸ）の割り付けと電力管理コストに依存する。このように、レジスタ割り付けにおいては、式１で使用する面積のコスト公式ｆpower（ｘ）を以下のように決定する：
ｆpower（ｘ）＝  （電力管理コストの合計）＋（マルチプレクサ電力コストの合計）  [８]
ＭＵＸ電力コストによるレジスタ割り付けにおける総電力増加は、ＭＵＸ面積の増加に比例する。ＭＵＸ面積の増加は、上記式７から得られる。
【０１１３】
【数１７】
2008500631.tif 000017
【０１１４】
ここで、
Ｖａｒ１は、レジスタに割り付けられた変数を表す；
Ｖａｒ２は、このレジスタを事前に用いた変数を表す；
ＳＡは、全ての変数に関する変数のスイッチングアクティビティを表す；
ｎは、宛先演算の数を表す；
Ｐｏｗｅｒは、２個の変数では共用されない、割り付けられた機能ユニットの正規化された電力消費を表す。
【０１１５】
電力に関連するコストの公式は、レジスタを共用することによって導入されるスプリアスアクティビティの計算を必要とする。これは、共用する際に必要となる変数のスイッチングアクティビティや、共用されるレジスタに接続される機能ユニットに変数によって導入されるスプリアス電力消散を考慮することによって達成される。スイッチングアクティビティに関する情報は、例えばコンパイラ指令を用いて設計者によって提供することも可能であり、また上記のように自動的に提供すること可能である。第１の変数によって導入されるスプリアスアクティビティは、第１の変数が共にレジスタを共用する他の変数の機能ユニットの電力量が乗算されたその第１の変数のスイッチングアクティビティから計算される。
【０１１６】
必要となるレジスタの最小数は、使用する際には必ずレジスタの最大数となる。これは、２個以上の異なるクラスタが時間的にオーバラップした場合にそこで必要となる変数に対する使用も含まれる。しかし、これによって電力コストは増大することになる。一方、設計される回路は、各変数に対して異なるレジスタを使用することが可能である。これによって電力コストは低減するが、面積コストは増大する。本実施の形態では、（面積および電力管理のいずれがより重要であるかによってコストを割り付けるための重み付けを用いて）異なるレジスタへの変数の割り付けに関連するコストを算出し、その後、どの割り付け組み合わせが最良の結果を生むかを算出する。この処理は、クラスタベースでクラスタ上でこれを行う。このように、クラスタにおいてレジスタに対する変数の可能な割り付けは、事前のクラスタの割り付けによって制限される。いずれかのクラスタに対する潜在的候補は、これまでに割り付けられた全てのレジスタ、すなわちその特定の割り付けまでに用いられたレジスタの累計数および現在のクラスタにおける変数の数に等しいレジスタの数を含む。しかし、ある一定の割り付けは、オーバラップする生存期間により不可能と
なる。その場合、その組み合わせに関連するコストは高く、少なくとも上記式７のＭＡＸ値となる。
重みによる自動レジスタ数決定の例示
図１３は、変数クラスタ（クラスタ０ないしクラスタ３）にクラスタリングされたコントロールステップ（Ｓ1ないしＳ4）の数の生存期間を有する変数を概略的に示す。レジスタを変数クラスタ０に最初に割り付けた後、クラスタ１における変数に対する割り付けは、必ずしも追加のレジスタを必要とするわけではない。その理由は、クラスタ１における変数の総数は、クラスタ０における総数よりも少なく、クラスタ１における変数の生存期間とオーバラップしないクラスタ０における変数の数は、クラスタ１における変数の数以上である。より正確には、この場合、クラスタ１内の3個の変数の生存期間とオーバラッ
プしないクラスタ０内の変数が3個ある。しかし、この機構に対しては、（不完全電力管
理のみに対照的に）完全電力管理を許容するために、割り付け候補として利用可能なレジスタの総数が、５ではなく８である（完全電力管理割り付けを許容するためにクラスタ０から５個とさらに3個のレジスタ）。
【０１１７】
自動化されたレジスタ割り付けの例を以下で示す。この機構は、必要な電力、面積間のトレードオフを考慮して、より良い電力管理のために余分のレジスタを使用するかどうかの判断および使用する余分のレジスタの数を自動化する。
【０１１８】
表1で示すモジュール割り付け結果を考える。図１３におけるクラスタ０のレジスタ割
り付けに対して、変数ａ、ｂ、ｃ、ｄおよびｅを（図１２におけるステップＳ３５４の）判断を行うことなく、Ｒ１，Ｒ２，Ｒ３、Ｒ４およびＲ５にそれぞれ割り当てる。これは、第１のクラスタ割り当ての際にはコストがかからないためである。
【０１１９】
【表１】
2008500631.tif 000018
【０１２０】
【表２】
2008500631.tif 000019
【０１２１】
本実施の形態では、実際に生成したマトリックスは方形マトリックスである。クラスタ内の変数を超えて、コラム内のエントリに対して大きい値の擬似スコアを生成する。これは、マトリックスのバランスを取るためである。問題が釣り合わない場合には、ハンガリアンアルゴリズムが擬似回答を生成することができる。
【０１２２】
クラスタ1内の変数ｆ、ｇおよびｈは、レジスタＲ１またはＲ２のいずれかを使用する
ことができない。その理由は、クラスタ０からの変数ａおよびｂは、変数ｆないしｈを最初に使用する際に、そのレジスタを使用中であるためである。これらの割り付けは、上記式７において生成するように、高いスコアを含むことにより不可能であると示されている。さらに、レジスタＲ３およびＲ４は、変数ｆを最初に使用する際には、変数ｃおよびｄによってそれぞれ今まで通り使用される。しかし、変数ｇおよびｈを最初に使用する際には、もはやこのような場合はあり得ない。このように、レジスタＲ３およびＲ４における変数ｇおよびｈに対して上記表２に値が示されている。
【０１２３】
各組み合わせに対するコストエントリは、Ｋarea（明示面積コスト＋暗黙面積コスト−
Ｅｑ７ａ）  ＋  Ｋpower（電力コスト−Ｅｑ８）である。例えば、変数ｇとレジスタＲ
４の組み合わせに対して、
【０１２４】
【数１８】
2008500631.tif 000020
【０１２５】
共用された変数はオーバラップせず、また機能ユニットもオーバラップしないため、両方の共用変数に対して同一の機能ユニットは割り付けられていない。
＝  １*１*ＣMUX
＝  ＣMUX
【０１２６】
【数１９】
2008500631.tif 000021
【０１２７】
共用された変数はオーバラップせず、また機能ユニットもオーバラップしないため、両方の共用変数に対して同一の機能ユニットは割り付けられていない。
＝  １*１*ＣMUX_implicit
＝  ＣMUX_implicit
レジスタＲ４を用いる変数ｇに関連するさらなるレジスタ面積コストはない。その理由としては、クラスタ０における変数ｄによって使用されるように、いずれにしてもＲ４が存在することが挙げられる。しかし、マルチプレクサが現在必要とされるレジスタ手段の共用として、ＭＵＸ面積コストが存在する。面積コストに対する計算のためにのみ、暗黙ＭＵＸ面積コストを使用する。暗黙ＭＵＸ面積コストは、必ずしもかかるものではないので、電力コスト計算においては除外される。
【０１２８】
【数２０】
2008500631.tif 000022
【０１２９】
レジスタＲ４が、クラスタ０内の変数ｄに既に割り付けられているため、変数ｄのスイッチングアクティビティは、変数ｄが使用する宛先機能ユニット、すなわちシフタ１（表１）に対するスプリアスアクティビティからの電力消費およびレジスタを共用するのに必要となるＭＵＸに対する電力コストであるとして関連するものである。
【０１３０】
レジスタＲ６に割り当てられた変数ｆに対して、レジスタＲ６の割り当てが初めてであ
るため、レジスタ面積コストがかかる。変数ｆに対する宛先がレジスタＲ５に既に割り当てられている変数ｅに対する宛先と同じであるため、ＭＵＸコストも存在することになる。さらに、ＭＵＸに関連する電力コストがかかる。
【０１３１】
レジスタＲ８に割り当てられた変数ｈに対しては、レジスタＲ８の割り当てが初めてであるため、レジスタ面積コストがかかる。しかし、（少なくともこの割り付けからは）電力管理コストはかからない。その理由としては、レジスタＲ８が、異なる宛先モジュールをその時点で有する可能性があるいかなる他の変数とも共用されないことが挙げられる。
【０１３２】
上記処理を用いると、レジスタ割り付けのためのレジスタ面積コストおよび電力管理コストのうち少なくとも1つは常にゼロである。しかし、電力管理コストと同時にＭＵＸ面
積コストが存在する可能性がある。レジスタを2回目に割り付け、それによって余分のレ
ジスタ面積コストがかからないがＭＵＸ面積コストがかかる可能性があるか、またはレジスタを最初に割り当て、その場合レジスタを共用せず、電力管理コストも存在しない、かのいずれかである。
【０１３３】
ＫareaがＫpowerと比較してかなり大きい場合には、変数ｆ、ｇおよびｈは、レジスタ
Ｒ３、Ｒ４およびＲ５に割り当てられ（この順番ではないが）、さらなるレジスタＲ６、Ｒ７およびＲ８は必要なくなり、面積は低減するが不完全電力管理をもたらすことになる。この割り当てにはＣMUXコストのみがかかるため、変数ｆはＲ５に割り付けられること
になる。ハンガリアンアルゴリズムは、２つの異なる可能な割り付け組み合わせに対する電力コスト間の比較に基づいて、この場合の最良の電力管理コストに対するレジスタＲ３およびＲ４間の変数ｇおよびｈの実際の割り付けを自動的に決定する。
ＳＡ（ｇ）．Ｐｏｗｅｒ（ＦＵ４+）＋ＳＡ（ｃ）．Ｐｏｗｅｒ（ＦＵ１*）＋ＳＡ（ｈ）．Ｐｏｗｅｒ（ＦＵ１<<）＋ＳＡ（ｄ）．Ｐｏｗｅｒ（ＦＵ１/）＋Ｐｏｗｅｒ（ＣMUX）および
ＳＡ（ｈ）．Ｐｏｗｅｒ（ＦＵ４+）＋ＳＡ（ｃ）．Ｐｏｗｅｒ（ＦＵ１/）＋ＳＡ（ｇ）．Ｐｏｗｅｒ（ＦＵ１<<）＋ＳＡ（ｄ）．Ｐｏｗｅｒ（ＦＵ１*）＋Ｐｏｗｅｒ（ＣMUX）．
一方、ＫpowerがＫareaよりずっと大きい場合、変数ｆ、ｇおよび変数ｈは、新たな3個のレジスタＲ６、Ｒ７およびＲ８に割り当てられる。実際の割り付けは、面積コストのみを考慮するものとしてランダムであっても良く、各レジスタに対する面積コストは同じである。あるいは、例として、コストが同じ場合に、小さい番号の変数を小さい番号のレジスタに割り当て、使用するレジスタ番号にギャップを残さない。
【０１３４】
ＫpowerおよびＫareaの値によって、ほぼ等しいコストマトリックスを生じる場合を考
える。変数ｆは、レジスタＲ５または新たなレジスタ｛Ｒ６，Ｒ７，Ｒ８｝のいずれかに割り付けられ、変数ｇおよびｈの割り当てに対して生じ得る結果は以下の通りである：
変数ｇはＲ３に割り当てられ、変数ｈは、Ｒ４またはまだ割り当てられていない新たなレジスタ｛Ｒ６，Ｒ７およびＲ８｝のうちの１つに割り当てられる；
変数ｇはＲ４に割り当てられ、変数ｈは、Ｒ３またはまだ割り当てられていない新たなレジスタ｛Ｒ６，Ｒ７およびＲ８｝のうちの１つに割り当てられる；
変数ｇおよび変数ｈは、まだ割り当てられていない新たなレジスタ｛Ｒ６，Ｒ７およびＲ８｝のうちの２つに割り当てられる。
【０１３５】
いかなる場合にも、変数ｇおよびｈのいずれもレジスタＲ５には割り当てられない。その理由として、ＭＵＸに関連するコストがレジスタに関連するものよりも少ない場合、変数がレジスタＲ５にある状態での総スコアは、変数ｇまたはｈがそこに割り付けられている場合よりも常に小さい。
【０１３６】
上記例では、ＭＵＸコストは、ＭＵＸが各々2個の入力を有する場合と同じであり、ビ
ット幅（例えば32ビット）が同じであると仮定する。Ｒｅｇ_ＣｏｓｔｓもまたＲ６ない
しＲ８に対して、レジスタがこのとき1個の変数に対するもののみである場合と同じであ
る。
【０１３７】
ハンガリアンアルゴリズムは、二連重み付き割り当てにおける割り当てを解決し、コスト全体を最小化する。電力および面積の重みを用いて、割り付けを案内する。本実施の形態の機構は、制約条件および優先順位が特定された状態で割り付けられるレジスタの数を自動的に決定する。
【０１３８】
図１４は、クラスタ１の変数が割り付けられた後、図１３のクラスタ２に対して可能性のある、変数のレジスタへの割付を示す二連グラフである。二連グラフでは、ノード設定が、共通要素を持たない２個のサブセットに分割される。あらゆるエッジは、異なるサブセット内の２個のノードを接続する。図１３に示す例の第２のクラスタのレジスタ割り付けの際、グラフにおける２個のサブセットは、図１４に示すように２個のセット、すなわちレジスタＲ＝｛ｒ1，ｒ2，ｒ3，ｒ4，ｒ5，ｒ6，ｒ7，ｒ8｝および変数のセットＶ＝｛ｖf，ｖg，ｖh｝を有する。レジスタが、それらに割り付けられた変数を既に有する場合
には、図１４内の関連のノード内に変数番号が現れる。グラフは一組のエッジを有し、可能性のある突合せＥ＝｛ｅ3,g，ｅ3,h，ｅ4,g，ｅ4,h，ｅ5,f，ｅ5,g，ｅ5,h，ｅ6,f，ｅ6,g，ｅ6,h，ｅ7,f，ｅ7,g，ｅ7,h｝を表す。各変数のレジスタへの突合せの問題は、ク
ラシックなジョブ割り当て問題としてモデリングされる。いずれの共通エンド・ノードも有さない最も大きなエッジのサブセットは、グラフの最大突合せとして規定され、その場合、グラフの最大エッジ・重み突合せは、そのエッジの重みの最大合計との最大突合せである。これによって、これらのエッジが有効エッジではないものとして二連重み割り当てにおける他のエッジとは競合しないことが確実となる。
【０１３９】
例示の実施の形態の装置および方法は、例えば図１５に略図で示すように、コンピュータシステム４００上で実現可能である。本実施の形態は、コンピュータシステム４００内で実施され、実施例の方法を実行するようコンピュータシステム４００に指示するコンピュータプログラムなどのソフトウェアとして実現しても良い。
【０１４０】
コンピュータシステム４００は、コンピュータモジュール４０２と、キーボード４０４およびマウス４０６などの入力モジュールと、ディスプレイ４０８およびプリンタ４１０などの複数個の出力装置とを備える。
【０１４１】
コンピュータモジュール４０２は、好適なトランシーバ装置４１４を介してコンピュータネットワーク４１２に接続され、例えばローカルエリアネットワーク（ＬＡＮ）やワイドエリアネットワーク（ＷＡＮ）などのインターネットや他のネットワークシステムへのアクセスを可能にする。
【０１４２】
本例のコンピュータモジュール４０２はまた、プロセッサ４１８と、ランダムアクセスメモリ（ＲＡＭ）４２０と、リードオンリメモリ（ＲＯＭ）４２２とを備える。コンピュータモジュール４０２は、多数の入力/出力（Ｉ/Ｏ）インタフェース、例えばディスプレイ４０８へのＩ/Ｏインタフェース４２４と、キーボード４０４へのＩ/Ｏインタフェース４２６とを備える。キーボード４０４は、例えば、チップ設計者が利用して、異なる最適化ニーズのチップを適合させるために最適化する際の電力および面積制約条件ならびにその関連の重要性を特定することも可能である。
【０１４３】
コンピュータモジュール４０２の構成部品は一般に、相互接続されたバス４２８を介して当業者に周知の方法で通信する。
アプリケーションプログラムは一般に、ＣＤ−ＲＯＭまたはフレキシブル・ディスクなどのデータ記憶媒体にコード化され、データ記憶装置４３０の対応するデータ記憶媒体駆動装置を用いて読み出されたコンピュータシステム４００のユーザに提供する。アプリケーションプログラムは、プロセッサ４１８によて実行する際に読み出され制御される。プログラムデータの中間記憶は、ＲＡＭ４２０を用いて実施されてもよい。
効果
高レベル合成レジスタ転送レベル設計を行うための方法および装置は、データ経路割り付けにおける電力消散と面積使用とのトレードオフを利用する。電力消散および面積制約条件と、その間の優先順位とを入力する。アルゴリズムは、特定された優先順位および制約条件に従って、使用するレジスタの数を自動的に決定する。電力管理公式を用いて、割り付け処理を適合させてレジスタ領域内で同等に保管するために電力管理コストをより低減することが可能となる。発見的に定めた電力および面積重み付けと共に複数判定基準最適化整数線形計画法を利用して、チップ設計の、事前に規定された異なる必要条件を適合させる。二連重み付き割り当てを利用して、コスト公式およびハンガリアンアルゴリズムによって、あらゆる段階で使用するレジスタの数を決定する。
【０１４４】
現代のチップ設計では、アプリケーションにさまざまな必要条件を提供する。携帯用装置に使用するチップおよび高密度チップは、その開発において主たる最適化優先順位として電力を有する。一方、非携帯アプリケーションに提供するチップを開発する際に、一般に電力よりも面積の方を考慮に入れる。上記実施の形態では、データ経路割り付け最適化の優先順位（面積/電力）および満たすべきそれぞれの制約条件（面積および電力）をユ
ーザが特定できる対話式機能を提供する。これらの対話式特徴部によって、チップが供給するアプリケーションおよびそれに課す制約条件に基づいてデータ経路割り付けをユーザが決定できる。
【０１４５】
上記実施の形態は、最適な電力―面積トレードオフ設計軌跡に沿った面積に対する電力管理コストをトレードすることが可能な機構を提供することによって、従来技術の問題をいくつか解決する。電力管理コストの公式は、割り付けによって、変数が切り替えられる割合を利用して同等面積に対する電力管理コストを最小にし、さらに公式におけるパラメータとしてのモジュールに対する不完全管理により失われる電力を最小にする。最適化する際に面積に優先順位がある場合には、反復データ経路割り付けによって、電力に対する最小面積をトレードしてユーザインタフェースによってユーザが特定する電力制約条件を実現するアーキテクチャを生成することになる。最適化する際に電力に優先順位がある場合には、面積に対する最小電力をトレードするアーキテクチャに反復データ経路割り付けが到達して、ユーザインタフェースによりユーザが特定する面積制約条件を実現する。
【０１４６】
データ経路割り付けは、二連重み付き割り当てを用いて実施され、ハンガリアンアルゴリズムを行ってこれらの割り当てにおける整合問題を解決する。ハンガリアンアルゴリズムは、Ｏ（ｎ3）の複雑さが少ないため、割り当てには時間を浪費しない。
【０１４７】
上記実施の形態は、例えばデコーダまたはエンコーダに対する電子回路へのデータ経路の割り付けを参照して述べた。しかし、上記処理は、当業者に容易に理解できるように、光学/光通信などの他の回路に対するデータ経路を割り付けるために利用できる。
【０１４８】
上記のように、データ経路を割り付けるための方法および装置を開示した。いくつかの実施の形態のみを述べたが、この開示に鑑み、本発明の範囲を逸脱することなく様々な変化および/または修正が可能であることが当業者には明らかになるであろう。
【図面の簡単な説明】
【０１４９】
【図１】図１は、２個の機能ユニットおよび２個のレジスタに対する、周知の制約条件のないレジスタ使用を示す。
【図２】図２は、２個の機能ユニットおよび１個のレジスタに対する、周知の制約条件付きレジスタ使用を示す。
【図３】図３は、本発明の実施の形態による、動作に関連する総括フローチャートである。
【図４】図４は、電力および面積利用のトレードオフを示すグラフである。
【図５】図５は、幾つかのネストされたループを有するループを示す図である。
【図６】図６は、ＡＬＵ、シフタ間の制約条件付きレジスタ使用を示す。
【図７】図７は、ループがスイッチングされる反復回数を特定するためのコンパイラ指令の使用を示す。
【図８】図８は、面積がより高い優先順位であるデータ経路割り付けにおける最適化を示すフローチャートである。
【図９】図９は、電力がより高い優先順位であるデータ経路割り付けにおける最適化を示すフローチャートである。
【図１０】図１０は、データ経路割り付け処理を示すフローチャートである。
【図１１】図１１は、モジュール割り付け処理を示すフローチャートである。
【図１２】図１２は、レジスタ割り付け処理を示すフローチャートである。
【図１３】図１３は、オーバラップした生存期間を有する変数のクラスタリングを示す概略図である。
【図１４】図１４は、レジスタに対する変数の可能な割り付けを示す二連グラフの例を示す。
【図１５】図１５は、実施の形態に関連する装置および方法を実現するためのコンピュータシステムを示す。
【図１】
2008500631.tif 000025
【図２】
2008500631.tif 000026
【図３】
2008500631.tif 000027
【図４】
2008500631.tif 000028
【図５】
2008500631.tif 000029
【図６】
2008500631.tif 000030
【図７】
2008500631.tif 000031
【図８】
2008500631.tif 000032
【図９】
2008500631.tif 000033
【図１０】
2008500631.tif 000034
【図１１】
2008500631.tif 000035
【図１２】
2008500631.tif 000036
【図１３】
2008500631.tif 000037
【図１４】
2008500631.tif 000038
【図１５】
2008500631.tif 000039
【国際調査報告】
2008500631.tif 000040
2008500631.tif 000041
2008500631.tif 000042