(57)【要約】【課題】【解決手段】電子回路を最適化するシステムは、二つの部分又は段階を有し、トレーニング段階１０では、進化的アルゴリズムを使用して、選択された電子回路用の最適化シナリオが導出され、運用段階１１では、導出された最適化シナリオを使用して、設計対象の新たな電子回路を最適化する。トレーニング段階１０では、進化的アルゴリズムを使用して、複数の入力回路又は回路グループのそれぞれに対して、専門化した相対的に高速の最適化シナリオを生成する（ステップ１３）。次に、一つ以上の進化済み専門最適化シナリオを選択し、一組の最適化シナリオを形成し（ステップ１５）、設計対象の新たな回路を最適化するために使用する。運用段階１１では、ステップ１８において、最適化対象の新たな回路を入力し、一組の最適化シナリオ１５からの複数の最適化シナリオを使用して、新たな回路の最適化を試みる（ステップ１９）。最善の最適化結果を、その回路のための最適化として取り出す（ステップ２０）。【選択図】図３
2009505198.tif 000002
【特許請求の範囲】
【請求項１】
電子回路の自動設計において使用する一組の最適化シナリオを作成する方法であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
前記異なる回路のために進化させた一つ以上の前記最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、を備える方法。
【請求項２】
請求項１記載の方法であって、
既知のベンチマーク回路セットから取り出した一個以上の回路向けに最適化シナリオを進化させる、方法。
【請求項３】
請求項１又は２記載の方法であって、
複数の個別回路からなる組に対して単一の最適化シナリオを進化させる、方法。
【請求項４】
請求項１〜３のいずれかに記載の方法であって、
同じ回路又は回路のグループに対して複数の最適化シナリオを進化させる、方法。
【請求項５】
請求項１〜４のいずれかに記載の方法であって、
前記進化的アルゴリズムの進化基準の一つとして、前記シナリオの最適化の速度を設定する、方法。
【請求項６】
請求項１〜５のいずれかに記載の方法であって、
前記進化的アルゴリズムの進化基準の一つとして、前記シナリオのメモリ使用要件を設定する、方法。
【請求項７】
請求項１〜６のいずれかに記載の方法であって、
前記進化済み最適化シナリオを評価し、それらの一つ以上を、その評価に基づいて、使用すべき前記一組の最適化シナリオに含める、方法。
【請求項８】
請求項１〜７のいずれかに記載の方法であって、
進化させた対象である前記回路以外の電子回路又は回路群を最適化するために、進化済み最適化シナリオを使用可能か評価し、
その評価に基づいて、前記最適化シナリオを、使用する前記一組の最適化シナリオに含める又は含めないこととする、方法。
【請求項９】
電子回路の設計において使用すべき一組の最適化シナリオに含めるために、最適化シナリオを選択する方法であって、
選択された対象電子回路向けに最適化シナリオを導出するステップと、
前記導出した最適化シナリオを使用して、その対象回路以外の電子回路を最適化可能か評価するステップと、
この評価に基づいて、電子回路の設計において使用する一組の最適化シナリオに、前記最適化シナリオを含めるか否かを選択するステップと、
を備える方法。
【請求項１０】
請求項１〜９のいずれかに記載の方法であって、
前記一組の最適化シナリオに含めるために、進化動作の途中で分かれた最適化シナリオ又はシナリオ群を選択する、方法。
【請求項１１】
請求項１〜１０のいずれかに記載の方法であって、
前記一組の最適化シナリオ内の前記最適化シナリオを、一個以上の回路又は回路の種類に関連付ける、方法。
【請求項１２】
請求項１〜１１のいずれかに記載の方法であって、更に、
前記一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の設計の態様の最適化を実行するステップと、
前記複数の最適化により決定された最適化結果の一つを、前記回路設計の態様に対して使用する最適化として選択するステップと、
を備える方法。
【請求項１３】
電子回路の設計を最適化する方法であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
前記異なる回路のために進化させた二つ以上の前記最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、
前記一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の設計の態様の最適化を実行するステップと、
前記複数の最適化により決定された最適化結果の一つを、前記回路設計の態様に対して使用する最適化として選択するステップと、
を備える方法。
【請求項１４】
請求項１２又は１３記載の方法であって、
各最適化シナリオが最適化を実行する制限時間を設定し、
前記制限時間に達した時と、前記最適化が終了した時と、のうちの何れか早い時点での最適化結果を、シナリオの最適化結果として取り出す、方法。
【請求項１５】
請求項１２〜１４のいずれかに記載の方法であって、
シナリオの各最適化ステップ後に前記最適化の品質を決定し、決定された最善の結果を、前記最適化シナリオの結果として取り出す、方法。
【請求項１６】
請求項１２〜１５のいずれかに記載の方法であって、
特定の対象回路向けに導出された最適化シナリオを、前記対象回路とは異なる回路向けの最適化を実行するために使用する、方法。
【請求項１７】
設計対象の電子回路を最適化する方法であって、
特定の対象回路向けに導出された最適化シナリオを、前記対象回路とは異なる回路を最適化するために使用するステップを備える方法。
【請求項１８】
請求項１６又は１７記載の方法であって、
前記対象回路ではない前記回路を最適化する時に、導出の目的となった前記対象回路に対する前記最適化シナリオの実行の形とは異なる形で、前記最適化シナリオを実行する、方法。
【請求項１９】
電子回路の設計において使用する最適化シナリオを導出する方法であって、
電気回路の態様の設計において使用する最適化シナリオを導出するために進化的アルゴリズムを使用するステップを備え、
前記進化的アルゴリズムの基準は、使用されている前記回路設計の態様を最適化するのに前記最適化シナリオが要する速度である、方法。
【請求項２０】
電子回路の設計において使用する最適化シナリオを導出する方法であって、
電気回路の態様の設計において使用する最適化シナリオを導出するために進化的アルゴリズムを使用するステップを備え、
前記進化的アルゴリズムの基準は、使用されている前記回路設計の態様を最適化する時に前記最適化シナリオが使用するメモリ資源である、方法。
【請求項２１】
電子回路の自動設計において使用する一組の最適化シナリオを作成する装置であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用する手段と、
前記異なる回路のために進化させた一つ以上の前記最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオとして提供する手段と、
を備える装置。
【請求項２２】
請求項２１記載の装置であって、
複数の個別回路からなる組に対して単一の最適化シナリオを進化させる手段を備える、装置。
【請求項２３】
請求項２１又は２２記載の装置であって、
同じ回路又は回路のグループに対して複数の最適化シナリオを進化させる手段を備える、装置。
【請求項２４】
請求項２１〜２３のいずれかに記載の装置であって、
前記進化的アルゴリズムの進化基準の一つとして、前記シナリオの最適化の速度を設定する手段を備える、装置。
【請求項２５】
請求項２１〜２４のいずれかに記載の装置であって、
前記進化的アルゴリズムの進化基準の一つとして、前記シナリオのメモリ使用要件を設定する手段を備える、装置。
【請求項２６】
請求項２１〜２５のいずれかに記載の装置であって、
前記進化済み最適化シナリオを評価し、それらの一つ以上を、その評価に基づいて、使用すべき前記一組の最適化シナリオに含める手段を備える、装置。
【請求項２７】
請求項２１〜２６のいずれかに記載の装置であって、
進化させた対象である前記回路以外の電子回路又は回路群を最適化するために、進化済み最適化シナリオを使用可能か評価し、
その評価に基づいて、前記最適化シナリオを、使用する前記一組の最適化シナリオに含める又は含めないこととする、装置。
【請求項２８】
電子回路の設計において使用すべき一組の最適化シナリオに含めるために、最適化シナリオを選択する装置であって、
選択された対象電子回路向けに最適化シナリオを導出する手段と、
前記導出した最適化シナリオを使用して、その対象回路以外の電子回路を最適化可能か評価する手段と、
この評価に基づいて、電子回路の設計において使用する一組の最適化シナリオに、前記最適化シナリオを含めるか否かを選択する手段と、
を備える装置。
【請求項２９】
請求項２１〜２８のいずれかに記載の装置であって、
前記一組の最適化シナリオに含めるために、進化動作の途中で分かれた最適化シナリオ又はシナリオ群を選択する手段を備える、装置。
【請求項３０】
請求項２１〜２９のいずれかに記載の装置であって、
前記一組の最適化シナリオ内の前記最適化シナリオを、一個以上の回路又は回路の種類に関連付ける手段を備える、装置。
【請求項３１】
請求項２１〜３０のいずれかに記載の装置であって、更に、
前記一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の設計の態様の最適化を実行する手段と、
前記複数の最適化により決定された最適化結果の一つを、前記回路設計の態様に対して使用する最適化として選択する手段と、
を備える、装置。
【請求項３２】
電子回路の設計を最適化する装置であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用する手段と、
前記異なる回路のために進化させた二つ以上の前記最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオとして提供する手段と、
前記一組の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の設計の態様の最適化を実行する手段と、
前記複数の最適化により決定された最適化結果の一つを、前記回路に対して使用する最適化として選択する手段と、
を備える装置。
【請求項３３】
請求項３１又は３２記載の装置であって、
各最適化シナリオが最適化を実行する制限時間を設定する手段と、
前記制限時間に達した時と、前記最適化が終了した時と、のうちの何れか早い時点での最適化結果を、シナリオの最適化結果として取り出す手段とを備える、装置。
【請求項３４】
請求項３１〜３３のいずれかに記載の装置であって、
シナリオの各最適化ステップ後に前記最適化の品質を決定し、決定された最善の結果を、前記最適化シナリオの結果として取り出す手段を備える、装置。
【請求項３５】
請求項３１〜３４のいずれかに記載の装置であって、
特定の対象回路向けに導出された最適化シナリオを、前記対象回路とは異なる回路向けの最適化を実行するために使用する手段を備える、装置。
【請求項３６】
設計対象の電子回路を最適化する装置であって、
特定の対象回路向けに導出された最適化シナリオを、前記対象回路とは異なる回路を最適化するために使用する手段を備える装置。
【請求項３７】
請求項３５又は３６記載の装置であって、
前記対象回路ではない前記回路を最適化する時に、導出の目的となった前記対象回路に対する前記最適化シナリオの実行の形とは異なる形で、前記最適化シナリオを実行する手段を備える、装置。
【請求項３８】
電子回路の設計において使用する最適化シナリオを導出する装置であって、
電気回路の態様の設計において使用する最適化シナリオを導出するために進化的アルゴリズムを使用する手段を備え、
前記進化的アルゴリズムの基準は、使用されている前記回路設計の態様を最適化するのに前記最適化シナリオが要する速度である、装置。
【請求項３９】
電子回路の設計において使用する最適化シナリオを導出する装置であって、
電気回路の態様の設計において使用する最適化シナリオを導出するために進化的アルゴリズムを使用する手段を備え、
前記進化的アルゴリズムの基準は、使用されている前記回路設計の態様を最適化する時に前記最適化シナリオが使用するメモリ資源である、装置。
【請求項４０】
設計中に電子回路を最適化するために使用する一組の最適化シナリオであって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用することで導出された複数の最適化シナリオを備える、一組の最適化シナリオ。
【請求項４１】
電子回路であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
前記異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、
前記一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行するステップと、
前記複数の最適化により決定された最適化結果の一つを、前記回路に対して使用する最適化として選択するステップと、により最適化された電子回路。
【請求項４２】
請求項１〜２０のいずれかに記載の方法、及び／又は、請求項２１〜３９のいずれかの装置を使用して設計された電子回路。
【請求項４３】
電子回路を構築する時に請求項１〜２０の何れかに記載の方法を使用するステップを備える、電子回路を構築する方法。
【請求項４４】
請求項２１〜３９の何れかの装置と、電子回路を構築する手段と、を備える、電子回路を構築する装置。
【請求項４５】
電子回路を構築する方法であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
前記異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、
前記一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行するステップと、
前記複数の最適化により決定された最適化結果の一つを、前記回路に対して使用する最適化として選択するステップと、
前記選択された回路の最適化を使用して、電子回路を設計及び構築するステップと、
を備える方法
【請求項４６】
電子回路を構築する装置であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用する手段と、
前記異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオとして提供する手段と、
前記一組の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行する手段と、
前記複数の最適化により決定された最適化結果の一つを、前記回路に対して使用する最適化として選択する手段と、
前記選択された回路の最適化を使用して、電子回路を設計及び構築する手段と、
を備える装置。
【請求項４７】
電子回路であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
前記異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、
前記一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行するステップと、
前記複数の最適化により決定された最適化結果の一つを、前記回路に対して使用する最適化として選択するステップと、
前記選択された回路の最適化を使用して、電子回路を設計及び構築するステップと、
により構築された電子回路。
【請求項４８】
データ処理手段において動作させた時に請求項１〜２０、４３、４５のいずれかに記載の方法を実行するためのコンピュータソフトウェアコード部分を備えるコンピュータプログラム要素。
【請求項４９】
添付図面の何れかを参照して実質的に上記で説明した、電子回路の自動設計において使用する一組の最適化シナリオを生成する方法又は装置。
【請求項５０】
添付図面の何れかを参照して実質的に上記で説明した、電子回路の設計において使用すべき一組の最適化シナリオに含める最適化シナリオを選択する方法又は装置。
【請求項５１】
添付図面の何れかを参照して実質的に上記で説明した、電子回路の設計又は設計対象の電子回路を最適化する方法又は装置。
【請求項５２】
添付図面の何れかを参照して実質的に上記で説明した、電子回路の設計において使用する最適化シナリオを導出する方法又は装置。
【請求項５３】
添付図面の何れかを参照して実質的に上記で説明した、設計中に電子回路を最適化するために使用する一組の最適化シナリオ。
【請求項５４】
添付図面の何れかを参照して実質的に上記で説明した電子回路。
【請求項５５】
添付図面の何れかを参照して実質的に上記で説明した、電子回路を構築する方法又は装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子回路の設計に関し、限定的ではないが特に、デジタル電子回路の最適化に関する。
【背景技術】
【０００２】
電子回路の設計は、例えば、設計プロセスの一部又は全てを自動化及び支援するソフトウェア、ツールの使用により支援する場合が多い。図１は、こうした「電子設計自動化」（ＥＤＡ）プロセスの一例におけるステップの概略を示す。図１に示した各ステップのために、例えば、ソフトウェアツールは、設計プロセスを支援又は実行するために使用される。
【０００３】
図１に示したような設計プロセスにおいて、ユーザからの主要な最初の入力は、所望の回路の高レベル仕様である（ステップ１）。この仕様は、図式（回路図）として設定してよく、或いは、より一般的には、ハードウェア記述言語を使用して記述される。高レベル仕様は、例えば、事前に設計された回路又はサブシステムを参照してもよい。
【０００４】
設計プロセスの次の段階は、いわゆる高レベル合成である（ステップ２）。これにより、入力された高レベル仕様を、電子部品のネットワーク上にマッピングする準備がほぼ整った形態に変換する。この高レベル合成は、例えば、特定の回路モジュールにタスクを割り当てることと、これらがどのように使用されるかをスケジューリングすることとを含む。
【０００５】
次に、まとめて「低レベル」合成８と呼ばれる一連のプロセスが存在する。この低レベル合成では、高レベル合成の結果を、選択された製造技術を使用して構築可能な形態に変換する（通常は、何らかの集積回路の形態）。
【０００６】
第一のこうした低レベル合成プロセスは、技術非依存の最適化である（ステップ３）。このプロセスは、技術の物理的構成要素のネットワークではなく、抽象論理レベルにおいて、設計を可能な限り簡略化することを目的としている。技術非依存の最適化では、通常、ノードがブール方程式である有向非循環グラフ（ＤＡＧ）を操作する。こうした論理のネットワークへの簡略化により、更に小さな物理回路が生じる。
【０００７】
次の段階は、選択された製造技術において利用可能な構成要素に設計をマッピングするテクノロジマッピングである（ステップ４）。その後、更なる最適化の実行を試みる技術依存最適化が存在する（ステップ５）。こうした両方のステップでは、構成要素のライブラリ６を使用する。
【０００８】
次に、最終段階は、構成要素の自動配置及びルーティングのステップ（ステップ７）であり、構成要素の良好な物理的位置と、構成要素間の接続の経路との発見を試みる。
【０００９】
当業者に理解されるように、上記は、電子回路設計フローの簡略化した説明であるため、説明したプロセスに対する変更及び修正が可能であり、実行されている。更に、例えば、図１に示したステップ間に、これほど明確な区分が存在しない場合もあり、高次のレベルで以前に行われた決定を再考慮するために、プロセスを後戻り可能であり、実行されることがある。更に、設計の検証と、最終的な回路を製造及び利用中に十分に試験可能とする容易さ（その「テスト容易性」）とのように、図示したもの以外の考慮事項も存在し得る（実際、通常は存在する）。
【００１０】
この種の電子回路設計プロセスの重要な態様は、設計フローの多数の段階で行われる自動最適化プロセスである。こうした最適化は、通常、例えば、結果的に生じる回路のサイズを最小化すること（これにより回路のコスト及びシリコン面積を低減されるため）に関係するが、同時に又は代わりに、回路動作の速度、回路の電力消費量、回路のテスト容易性等に関係することも場合もある。
【００１１】
技術非依存最適化に使用される最適化基準の例には、回路を表すブール関数の有向非循環グラフにおける因数分解形でのリテラルの合計を最小にすることである。この基準は、回路を表すブール関数の有向非循環グラフにおける論理の全体的な複雑性の尺度をもたらし、これを最小化することは、許容可能な遅延特性を有する、より小さな物理的回路につながる。この基準の最適化は、後で他の用途特異性の強い最適化が実行される場合でも有用となる場合が多い。この基準を最適化するための最適化プロセスでは、通常、回路を表すブール関数の有向非循環グラフにおける因数分解形でのリテラルの合計を最小化するためにプロセスを指定する。
【００１２】
電子設計自動化ツールにおいて使用される最適化プロセスは、多数のステップを含むことが可能であり、こうしたステップを配列すること、及びそのパラメータを設定することは、困難な問題となり得る。実施対象の最適化の仕様は、通常、最適化シナリオ又はスクリプトと呼ばれる。最適化シナリオは、所望の最適化基準に従って電子回路設計の品質を共に改善する、多数の変換プロセスを指定するものと考えられる。最適化スクリプトは、最適化シナリオの一例（形態）である。最適化シナリオ（例えば、スクリプト）は、その後、ソフトウェア設計ツールに組み込み、回路設計プロセス中に最適化プロセスとして使用できる。
【００１３】
一般的に使用され周知である電子設計自動化ツールは、カリフォルニア大学バークリー校で開発されたBerkeley SISシステムである。SISシステムにおいて、最適化シナリオは、最適化プロセスのステップを設定し、SISソフトウェアに対してテキストファイルで供給されるスクリプトとして構成される
【００１４】
回路設計において使用する最適化シナリオを導出する既知の一方法は、様々な最適化シナリオを手動で分析及び評価することである。これにより、ほぼ全ての回路を十分に最適化することが分かっている多数の既知の標準的な最適化シナリオ（スクリプト）の開発につながった。こうした最適化シナリオは、「汎用」シナリオ又はスクリプトと呼ばれる場合がある。こうした多数の汎用最適化シナリオは、例えば、SISシステム用に開発されてきた。
【００１５】
更に、例えば、ある特定の回路を（汎用性の高いシナリオより良好に）最適化するために調整された、より特化した最適化シナリオを導出する試みも知られている。これは、一般には、既知の汎用シナリオから開始される手動実験により行われる。
【００１６】
最適化シナリオを試験及び最適化するために、例えば、図２に示した種類の、いわゆる進化的（又は遺伝的）探索アルゴリズムを使用することも提案されている。こうした進化的アルゴリズムは、人間の専門家が設計した汎用性の高い最適化シナリオよりも、一定の対象に対して良好な性能を示す最適化シナリオを導出するために使用できる。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
一定の回路に対して最適化シナリオを作成するのに進化的アルゴリズムが使用される仕組みにおいては、当業者が理解するように、問題の回路を最適化するツールとして使用可能となる前に、最適化シナリオを「進化」させる必要がある。したがって、全体的な最適化プロセスは、二つの部分を有するものとして捉えることが可能であり、第一の「トレーニング」段階では、進化的アルゴリズムを使用して、問題の回路用の最適化シナリオを作成し、第二の「最適化」段階では、トレーニング段階で作成した進化済みの最適化シナリオを、最適化対象の回路に利用して、その回路を最適化する。言い換えると、まず、進化的アルゴリズムを使用して最適化シナリオを作成し、次に、進化済みシナリオをツールとして使用し、最適化対象の回路を最適化する。
【００１８】
より特化した最適化シナリオの進化的導出に伴う欠点は、こうした進化的導出が時間及びコンピューティング資源集約的プロセスとなることである（多数の種類の異なる最適化シナリオ候補がプロセスに関与するため）。この努力は、最適化対象の回路が特に重要又は効果的である場合には正当化し得るが、遭遇する可能性のある全ての回路それぞれのために、特化した最適化シナリオを進化させる試みには、それほど実用性がないことを意味する。
【００１９】
一定範囲の回路を最適化する汎用シナリオを生成する進化的アルゴリズムの使用についても、これには遥かに多くの計算作業及び時間が必要であり、一般的なケースでは手動で導出したシナリオを上回ることが困難であることから、通常は行われない。
【００２０】
こうした全ては、実際には、回路設計システムでは、より汎用性の高い、手動で導出されたシナリオを、その最適化シナリオとして使用する傾向にあることを意味している。
【００２１】
出願人は、電子回路の設計において使用する自動化ツール及びプロセスには改良の余地が残されていると考えている。
【課題を解決するための手段】
【００２２】
本発明の第一の態様によれば、電子回路の自動設計において使用する一組の最適化シナリオを作成する方法であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
異なる回路のために進化させた一つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、を備える方法が提供される。
【００２３】
本発明の第二の態様によれば、電子回路の自動設計において使用する一組の最適化シナリオを作成する装置であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化されるために進化的アルゴリズム又はアルゴリズム群を使用する手段と、
異なる回路のために進化させた一つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオとして提供する手段と、を備える装置が提供される。
【００２４】
本発明の第三の態様によれば、設計中に電子回路を最適化するために使用する一組の最適化シナリオであって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用することで導出された複数の最適化シナリオを備える一組の最適化シナリオが提供される。
【００２５】
本発明において、進化的アルゴリズムは、多数の異なる回路に対して最適化シナリオを導出するために使用される。このように進化させた最適化シナリオは、その後、設計対象の新たな回路を最適化するのに使用する最適化シナリオの組（セット）として提供される。
【００２６】
出願人は、このように一組の進化させた最適化シナリオを導出することで、例えば、遭遇するであろう、或いは遭遇し得る全ての回路それぞれに対して進化的アルゴリズムを使用して最適化シナリオを導出する必要なく、既知の汎用性の高い最適化シナリオ等に比べ、回路設計中の新たな設計において、更に良好な最適化等をもたらす一組の最適化シナリオを提供可能であることを発見した。
【００２７】
特に、出願人は、一定の回路用に特異的に進化させた最適化シナリオ（専門シナリオ）がその対象回路に対して良好な性能を示すだけでなく、他の何らかの回路にも同様に良好な性能を示す傾向があることを発見した。こうした他の回路は、最適化シナリオの「補助」回路と考えることができる。出願人は、更に、それぞれが独自に一組の補助回路を有する、複数の専門最適化シナリオからなる組を開発することで、遭遇し得る全ての個別回路それぞれに対して専門最適化シナリオを進化させる必要なく、専門シナリオの組み合わせが、その補助回路のセットと併せて、遭遇し得る回路の全てではなくとも、多数を網羅可能であると共に網羅するであろう一組の最適化シナリオを提供できることを認識した。実際に、出願人は、一組のほんの僅かな専門最適化シナリオを使用して、多数の回路において優れた性能を達成可能であることを発見した。
【００２８】
最適化シナリオを進化させる対象となる回路は、必要に応じて選択できる。例えば、シナリオは、電子設計自動化ツールにおいて一般的に使用される回路の既知の基準又はベンチマークセットから取り出した一つ以上の（選択された）回路にすることができる。しかしながら、これは必須ではなく、他のベンチマークではない回路も、同様に又は代わりに、使用可能であり、使用することが好ましい。例えば、最適化シナリオは、新たな未知の、例えば特に関心が高い、回路又は回路群に対して進化させることができる。
【００２９】
最適化シナリオを進化させる対象となる回路は、例えば、ランダムに選択可能である。しかしながら、好適な実施形態において、シナリオは、既知の標準的シナリオでは最適化が困難であると認識される回路のために進化させる。好ましくは、シナリオは、より最適化が困難である回路のために優先して進化させる。更に、例えば、最適化シナリオの既存の組（及び、例えば、その組において特定された弱点）に基づいて、回路を選択することも可能である（更に、実際に、好ましい）。
【００３０】
好適な実施形態では、評価対象となる（即ち、最適化シナリオを進化させる対象となる）複数の異なる電子回路の組が選択される。好適な一実施形態において、最適化シナリオは、５〜１５個、最も好ましくは１０個の回路に対して進化させる。
【００３１】
好適な実施形態において、一組の複数の個別回路を共にグループ化し、その回路グループのために進化させた単一の最適化シナリオとしてよい。これにより、例えば、特定の回路クラス向けに特化させた最適化シナリオの作成が可能となる。これは、例えば、特定の回路タイプ又は回路クラスを、最適化シナリオの進化中に全て試験可能な個別回路の（少数の）グループにより表現できる場合に有用となり得る。
【００３２】
更に、例えば、同じ回路又は回路グループ向けに、複数の最適化シナリオを進化させること（及び、例えば、こうした最適化シナリオの全てを、使用すべき最適化シナリオの組に含めること）も可能である。更に以下に説明するように、出願人は、同じ回路向けに進化させた異なる最適化シナリオが補助回路の異なるセットを有し、使用すべき最適化シナリオの組（セット）内の両方又は全ての最適化シナリオを含むことが有用となり得ることを発見した。
【００３３】
各回路（又は回路グループ）向けの最適化シナリオは、この技術で既知である進化手法等、任意の適切な進化的アルゴリズム又はプロセスを使用して進化させることができる。したがって、例えば、ランダムに生成したシナリオの集団から進化を開始可能であり、或いは、例えば、既に手動で進化又は設計したシナリオを種とすることが可能である。同じ進化的アルゴリズムを各回路に使用してよく、或いは、異なるアルゴリズムも使用できる。
【００３４】
当業者が理解するように、進化プロセスは、因数分解形でのリテラル数の合計等、最適化シナリオによる最適化が意図された最適化基準を対象とするべきである（即ち、選択（適応度）基準として有するべきである）。このため、各候補シナリオに対する最適化基準の結果の決定等を行い、その後、この技術で既知であるように、それに応じて、候補シナリオを選択して更に進化又は拒絶できる。
【００３５】
特に好適な実施形態では、上記のような最適化「結果」に従って、進化プロセス中に候補最適化シナリオを評価することに加え、シナリオを終了するのに要する時間（即ち、その実行速度）も考慮され、迅速なシナリオが好適となる（例えば、継続的な進化のために優先的に選択されるか、及び／又は使用する最適化シナリオとして選択される）。最も好ましくは、二つ以上の候補シナリオの最適化基準の測定が等しい場合、より素早く終了するシナリオを優先的に選択する。
【００３６】
したがって、特に好適な実施形態において、進化的アルゴリズムに対して設定されると共に、進化的アルゴリズムにおいて奨励される進化基準の一つは、シナリオの最適化の速度である（即ち、そのシナリオがどれほど迅速に最適化結果を形成するか（即ち、対象回路を最適化するか））。これにより、回路に対して相対的に高品質の結果を生み出すが、相対的に迅速である最適化シナリオを優先的に進化させる。これは、以下に更に説明するように、一組の最適化シナリオを使用する際に有利である。
【００３７】
好適な仕組みでは、最適化シナリオが最適化の結果を形成する（即ち、終了する）のに要する時間に制限時間を設定し、例えば、この制限時間を超えるシナリオは、例えば、制限時間に全てを終了させる（その時点で達成された最適化結果をシナリオの結果として取り出す）か、或いは、例えば、更なる考慮から排除する。この制限時間は、好ましくは、上記の終了時間の早いシナリオの優先的選択に追加される。これは、好ましくは、少なくとも最適化シナリオの進化の初期段階中に実行される。制限時間は、進化プロセスの後期段階では、例えば、完全に取り去るのではなく、増やすこともできる。この制限時間は、例えば、既知の汎用スクリプトが問題の回路に対する結果を得るのにどのくらいの長さが必要かを基準にすることができる。こうした制限時間の適切なものは、例えば、６００秒以下である。
【００３８】
最適化シナリオの実行に要する時間を制限することは、進化プロセス中に妥当な時間内で進化及び評価されるべき妥当な数のシナリオについて、最適化シナリオを十分に素早く進化させることが可能な状態を確保するのに役立つことから、進化プロセス自体も促進する。
【００３９】
最適化の速度を、電子回路設計用の最適化シナリオの進化的導出の基準に含めることは、それ自体が新しく、利点になり得ると考えられる。
【００４０】
したがって、本発明の第四の態様によれば、電子回路の設計において使用する最適化シナリオを導出する方法であって、
電気回路の態様の設計において使用する最適化シナリオを導出するために進化的アルゴリズムを使用するステップを備え、進化的アルゴリズムの基準は、使用されている回路設計の態様を最適化するのに最適化シナリオが要する速度である方法が提供される。
【００４１】
本発明の第五の態様によれば、電子回路の設計において使用する最適化シナリオを導出する装置であって、
電気回路の態様の設計において使用する最適化シナリオを導出するために進化的アルゴリズムを使用する手段を備え、進化的アルゴリズムの基準は、使用されている回路設計の態様を最適化するのに最適化シナリオが要する速度である装置が提供される。
【００４２】
特に好適な実施形態では、上記のように、最適化「結果」と、例えば、それが終了するのに要する時間とに従って、進化プロセス中に候補最適化シナリオを評価することに加え、シナリオの実行中のメモリの使用量についても考慮され、メモリの使用量（「消費量」）が少ないシナリオが好適となる（例えば、継続的な進化のために優先的に選択されるか、及び／又は使用する最適化シナリオとして選択される）。最も好ましくは、二つ以上の候補シナリオの最適化基準の測定が等しい場合、よりメモリ使用量の少ないシナリオを優先的に選択する。
【００４３】
したがって、特に好適な実施形態において、進化的アルゴリズムに対して設定されると共に、進化的アルゴリズムにおいて奨励される進化基準の一つは、シナリオのメモリ使用量要件である（例えば、そのシナリオが最適化結果を形成する（即ち、対象回路を最適化する）のにどのくらいの量のメモリ資源を使用するか又は必要とするか）。これにより、回路に対して相対的に高品質の結果を生み出すが、相対的にメモリ使用量が少ない最適化シナリオを優先的に進化させる。これも、一組の最適化シナリオを使用する際に有利である。
【００４４】
メモリ使用量を、電子回路設計用の最適化シナリオの進化的導出の基準に含めることは、それ自体が新しく、利点になり得ると考えられる。
【００４５】
したがって、本発明の第六の態様によれば、電子回路の設計において使用する最適化シナリオを導出する方法であって、
電気回路の態様の設計において使用する最適化シナリオを導出するために進化的アルゴリズムを使用するステップを備え、進化的アルゴリズムの基準は、使用されている回路設計の態様を最適化する時に最適化シナリオが使用するメモリ資源である方法が提供される。
【００４６】
本発明の第七の態様によれば、電子回路の設計において使用する最適化シナリオを導出する装置であって、
電気回路の態様の設計において使用する最適化シナリオを導出するために進化的アルゴリズムを使用する手段を備え、進化的アルゴリズムの基準は、使用されている回路設計の態様を最適化する時に最適化シナリオが使用するメモリ資源である方法が提供される。
【００４７】
更に、進化的アルゴリズムにとっては、（例えば、最適化品質と、シナリオの実行時間とが等しい場合において）より短いシナリオを（更なる評価のために、或いは使用する最適化シナリオとして）優先的に選択することも好適である。
【００４８】
好適な実施形態では、（例えば、通常は、別個のものと考えられる）複数の最適化条件又はプロセスに渡る、或いはこれらを含む、最適化シナリオの進化が可能であり、実行される。例えば、技術依存最適化を単独で実行する代わりに、最適化シナリオを進化させる時に後続のテクノロジマッピングも考慮に入れることができる。こうした「拡張」最適化評価は、必要な時間が長すぎて進化プロセス及び評価が完了しない状態を生じない場合のみ実行することが好適である。
【００４９】
好適な実施形態において、進化的アルゴリズム又はアルゴリズム群は、許容可能な短い期間に特定の回路向けに最適化シナリオを進化させるように準備及び選択される。これにより、許容可能な短い時間スケール内に、進化プロセスを数回反復できる。
【００５０】
好適な実施形態において、進化的アルゴリズムは、反復区間を含み得る長いシナリオの進化が可能だが、それを行うことを強制されない。更に、例えば、どのコマンドが実際に必要かを確認するために、自動化された体系的な一組のテストを使用することで、任意の冗長コマンドを進化済み最適化シナリオ（進化後）から除去（削除）することも好適である。特に好適な実施形態では、例えば、異なる補助回路セットを有する場合があるため、シナリオの「削除」及び「非削除」バージョンの両方を一組の最適化シナリオに含めてよい。
【００５１】
好適な実施形態では、回路又は回路群のための最適化シナリオは、例えば、並行して作動する別個のマイクロプロセッサ上で多数の進化を実行することで、並行して進化させる。
【００５２】
使用すべき一組の最適化シナリオに含まれる進化済み最適化シナリオは、必要に応じて選択可能である。全ての進化済み最適化シナリオそれぞれを、使用すべき一組の最適化シナリオに含めることが可能であり、或いは、全てよりも少なくすることが可能である。好適な実施形態では、選択された数の進化済み最適化シナリオ、好ましくは２つ以上のシナリオであり、好ましくは１０シナリオが、一組の最適化シナリオに含まれる。
【００５３】
好適な実施形態において、進化済み最適化シナリオは、使用すべき一組の最適化シナリオに含められるべきか否かを評価され、その評価に基づいて、その組に含められるか又は含められないこととなる。こうした評価は、任意の適切な又は所望の形で実行できる。例えば、その包含により一組の最適化シナリオが強化されるか、及び／又はその性能が標準の手動設計シナリオと比較可能かを確認するために、進化済みシナリオを使用して、選択サンプル回路群を最適化できる。好適な実施形態では、選択されたシナリオのテストセット内の各シナリオの性能を評価及び使用して、所望の最適化性能を提供する最小数のシナリオをテストセットから選択し、一組の最適化シナリオとして使用する。
【００５４】
特に好適な実施形態において、進化済み最適化シナリオは、それらを有効に使用して最適化可能な補助回路（即ち、それらを有効に使用して最適化可能な対象回路以外の回路）に基づいて、使用すべき一組の最適化シナリオに含められるべきか否かを評価される。そのため、例えば、シナリオの補助回路の全ての範囲を定めることを試みるのではなく、（好ましくは事前に定められた）選択サンプル回路群に対してシナリオを試験することで、シナリオの補助回路の量及び／又は種類を、この目的で評価及び推定することが好適である。
【００５５】
例えば、最適化シナリオを使用可能な補助回路数を考慮可能であり、及び／又は、特定のシナリオの補助回路を、別の最適化シナリオ又はシナリオ群（例えば、使用すべき最適化シナリオの組に既に含まれたシナリオ群）の補助回路と比較できる（例えば、新たな最適化シナリオが、一組の最適化シナリオに対する有効な追加となるか否か）。
【００５６】
したがって、好適な実施形態において、進化済み最適化シナリオに対する補助回路のセットを評価（例えば、推定）し、その評価に基づいて、最適化シナリオを、使用する一組の最適化シナリオに含めるか又は含めないこととなる。
【００５７】
こうした仕組みは、それ自体が新しく、利点になり得ると考えられる。したがって、本発明の第八の態様によれば、電子回路の設計において使用すべき一組の最適化シナリオに含めるために、最適化シナリオを選択する方法であって、
選択された対象電子回路向けに最適化シナリオを導出するステップと、
導出した最適化シナリオを使用して、その対象回路以外の電子回路を最適化可能か評価するステップと、
この評価に基づいて、電子回路の設計において使用する一組の最適化シナリオに、最適化シナリオを含めるか否かを選択するステップと、を備える方法が提供される。
【００５８】
本発明の第九の態様によれば、電子回路の設計において使用すべき一組の最適化シナリオに含めるために、最適化シナリオを選択する装置であって、
選択された対象電子回路向けに最適化シナリオを導出する手段と、
導出した最適化シナリオを使用して、その対象回路以外の電子回路を最適化可能か評価する手段と、
この評価に基づいて、電子回路の設計において使用する一組の最適化シナリオに、最適化シナリオを含めるか否かを選択する手段と、を備える装置が提供される。
【００５９】
当業者に理解されるように、本発明の上記態様は、本明細書で説明した本発明の好適な任意の特徴の全てを何れか一つ以上含むことが可能である。したがって、例えば、最適化シナリオは、好ましくは、進化的アルゴリズムを使用して導出される。
【００６０】
本発明のこうした態様及び仕組みにおいて、特定の対象回路向けに導出した最適化シナリオが同様に有効に最適化する「補助」回路は、任意の望ましい形で決定及び評価できる。例えば、選択されたベンチマーク又は基準回路セット内の各回路等、特定の、例えば選択された、一組の回路に対する最適化シナリオの最適化性能を評価可能であり、回路に対する最適化シナリオの最適化性能が、その回路に対する既知の汎用最適化シナリオの最適化性能よりも良好である場合には、問題の回路を最適化シナリオの補助回路とみなすことができる（その回路の最適化性能を改善するため）。
【００６１】
最適化シナリオに含めるべきか否かを決定する時に、最適化シナリオの「補助」回路を評価することと共に、一組の最適化シナリオに最適化シナリオを含めるか（又は含めないか）を、追加として或いは代わりに、（上述のように）最適化シナリオの実行速度に基づくものとすることが好適であり、例えば、より高速なシナリオ、及び／又は選択された、好ましくは事前に定められた制限時間より早く終了するシナリオのみを、使用する一組の最適化シナリオに含める。
【００６２】
したがって、上述したことから理解されるように、本発明は、好ましくは、例えば、各最適化シナリオにより同様に最適化される「補助」回路に基づいて、使用すべき一組の最適化シナリオに包含する一つ以上の進化済み最適化シナリオを選択するステップ又は手段を含む。こうした選択は、例えば、全ての進化済み最適化シナリオが、使用すべき一組の最適化シナリオに含まれる訳ではないことを一般的に意味するが、こうした選択により、全ての進化済み最適化シナリオが使用される結果となる可能性も等しく存在する。
【００６３】
好適な実施形態では、一組の最適化シナリオに含めるために、進化動作の最終的な進化済み最適化シナリオと同様に、或いはその代わりに、進化動作の途中で分かれた最適化シナリオ又はシナリオ群を選択することが可能である。出願人は、進化動作の途中で分かれた最適化シナリオは、例えば、対象回路のために完全に仕上げた最終結果と比較して、異なる、実際には更に有効な、補助回路の組を有する場合があることを発見した。
【００６４】
好適な実施形態において、一組の最適化シナリオは、選択された指定の対象回路向けに進化させたシナリオに加えて、他の最適化シナリオを含むことが可能であり、好ましくは実際に含んでいる。こうした追加の最適化シナリオは、例えば、標準的な、以前に決定された、及び／又は、手動で導出された、汎用最適化シナリオ、及び／又は（可能な場合）進化済みの汎用最適化シナリオであっても含むことができる。既知である既存の標準的手動設計汎用シナリオを、一組の最適化シナリオに含めることで、例えば、一組の最適化シナリオにより達成される最適化の品質は、標準の汎用シナリオを単独で使用した時に達成可能なものに劣らない状態が確保される。
【００６５】
このように追加の最適化シナリオが一組の最適化シナリオに含まれる場合、追加シナリオは、或る回路を最適化するために使用される時に十分に素早く動作できる場合（即ち、その最適化速度が十分に高速であり、例えば、選択された制限時間を下回る場合）にのみ含まれることが好適である。
【００６６】
好適な実施形態において、使用する最適化シナリオの組内の最適化シナリオは、最適化に特に有効であると考えられる一つ以上の回路又は回路タイプに関連する。これにより、新たな回路を最適化する時に使用する最適化シナリオ又はシナリオ群の選択を更に良好なものにし得る。
【００６７】
当業者に理解されるように、上記では主に、使用すべき一組の最適化シナリオの導出、即ち、上述の「トレーニング段階」を扱っている。
【００６８】
一組の最適化シナリオが作成された後は、電子回路を最適化するために、その設計中に（即ち、回路設計プロセスの「運用段階」において）、必要に応じて、例えば、この技術で既知である任意の形で使用できる。したがって、例えば、組内の最適化シナリオを導出する対象となった態様（群）又は基準との何らかの関係を有する、或いは、対応等のある、新たな回路設計の態様又は基準を最適化するべき時、その最適化プロセスに一組の最適化シナリオを使用できる。
【００６９】
特に好適な実施形態において、最適化シナリオの組内の複数の最適化シナリオのそれぞれを使用して、新たな回路設計を最適化し、試験した全ての最適化シナリオの結果の一つ（選択された一つ）を、新たな回路に使用する最適化結果（即ち、最適化された回路設計）として取り出す。言い換えると、複数の最適化シナリオを回路に対して順番に試し、例えば、最善の結果を選択する。
【００７０】
出願人は、例えば、標準の汎用最適化シナリオを単純に使用することに比較して、この仕組みが、遭遇し得る全ての回路それぞれに対して特化した最適化シナリオを導出する必要無く、新たな未知の回路に対して優れた最適化結果をもたらす傾向にあることを発見した。更に、本発明のように導出した一組の最適化シナリオにより、特に相対的に高速な最適化速度を提供するために進化させた場合には、多数の最適化シナリオをこのように試験し、最適化の結果を改善することが期待できる。
【００７１】
したがって、好適な実施形態において、本発明は、一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の設計の態様の最適化を実行するステップ又は手段と、複数の最適化により決定された最適化結果の一つを、回路設計の態様に対して使用する最適化として選択するステップ又は手段とを含む。
【００７２】
こうした仕組みでは、例えば、最適化プロセスのために、単純に最適化シナリオの組内の全最適化シナリオを使用することが可能であり、更に例えば、最善の一つを選択することが可能である。また、例えば、問題の回路の性質又は種類に基づいて、より限定された、又は選択された一組の最適化シナリオを試すことも可能である。この後者のアプローチは、例えば、最適化シナリオが有効となる可能性が高い回路又は回路群の種類に従って分類されている場合に、特に有効となり得る。
【００７３】
複数の最適化シナリオを試した後で使用又は選択される最適化結果は、任意の適切且つ望ましい形で選択できる。例えば、問題の回路の不具合又は態様を最適化する観点において、良好な結果（及び最も好ましくは最善の結果）をもたらしたシナリオを選択することが好ましい。更に、例えば、可能な全ての最適化シナリオを未だ試していないとしても、例えば、特定の、好ましくは事前に定められた期間において達成された最善の結果を取り出すことも可能である。
【００７４】
例えば、多数の最適化基準（サイズ、速度、電力使用量等）を考慮すべき場合、最適化結果は、選択された、例えば事前に定められた、異なる要件間等でのトレードオフ又はランキングに基づくなどして選択できる。さらに、例えば、一組の最適化シナリオが複数の許容可能な最適化結果又は選択肢を提供する場合には、こうした異なるトレードオフ間での選択等も可能である。これにより、或る回路又は回路群での更なる設計の探求及び最適化が促進できる。
【００７５】
したがって、選択された最適化結果は、好ましくは、その最適化シナリオを使用して達成される最適化品質の尺度に基づいたものとなる。最も好ましくは、最高品質の最適化結果をもたらす最適化が選択される。この最適化品質は、任意の適切且つ望ましい形で測定できる。
【００７６】
特定の好適な実施形態では、好ましくは事前に定められた制限時間により、最適化シナリオ毎に回路に対する最適化を実行可能であり、例えば、制限時間に達した時又は最適化が終了した時の何れか早い方の最適化結果を、そのシナリオの最適化結果として取り出す（その後、システムは、試すべき次の最適化シナリオへ移行する）。これは、多数の最適化シナリオを試行中であっても、プロセスが十分に高速である状態を確保するのに役立つ。
【００７７】
設定された制限時間は（存在する場合）、例えば、要する時間と、最適化性能との間のトレードオフに基づくもの、及び／又は、問題の回路及び最適化基準に対して既知の標準的汎用スクリプト等が最善の最適化結果を達成するのに要する時間に基づくものにすることができる。
【００７８】
最適化シナリオは、進化させた時と厳密に同じ形で、新たな回路に対して使用及び適用可能である。しかしながら、好適な実施形態において、最適化シナリオは、進化させる時に（即ち、トレーニング段階中に）使用又は実行した方法とは異なる方法で、利益が得られるように使用及び／又は実行してよく、そうすることが好ましい。
【００７９】
例えば、特定の対象回路向けに進化させた専門最適化シナリオは、通常、最適化シナリオの実行の終了時に、最も高度に最適化された対象回路のバージョンを生み出す。しかしながら、特定の対象回路ではない回路に対して、最適化シナリオは、最適化シナリオの実行中の何らかの中間点において最善の結果を発生させ得る。
【００８０】
したがって、特に好適な実施形態では、最適化の品質をシナリオの各最適化ステップ後に測定し、最善の測定結果を最適化シナリオの結果として取り出し、適切である場合には、使用する（単純に最適化シナリオの最終結果を取り出す等はしない）。
【００８１】
同様に、最適化シナリオを使用して新たな回路を最適化する時には、最適化シナリオの反復（繰り返し）を発生可能にすることが好適である（この技術で既知であるように、最適化シナリオの反復は有益となり得るが、トレーニング段階中（即ち、シナリオを最初に導出している時）には不要となる場合があり、これは、その段階中には、単一のシナリオにより、最適化シナリオの単一の反復内で一連の最適化ステップの反復を受け入れることが可能となるためである）。
【００８２】
こうした仕組みは、それ自体が新しく、利点になり得ると考えられる。したがって、本発明の第十の態様によれば、電子回路の設計を最適化する方法であって、
選択された対象電子回路向けに最適化シナリオを導出するステップと、
選択された対象回路ではない回路を最適化するために、導出した最適化シナリオを使用するステップと、
選択された対象回路ではない回路を最適化する時に、導出の目的となった選択対象回路に対する最適化シナリオの実行の形とは異なる形で、最適化シナリオを実行するステップと、を備える方法が提供される。
【００８３】
本発明の第十一の態様によれば、電子回路の設計を最適化する装置であって、
選択された対象電子回路向けに最適化シナリオを導出する手段と、
選択された対象回路ではない回路を最適化するために、導出した最適化シナリオを使用する手段と、
選択された対象回路ではない回路を最適化する時に、導出の目的となった選択対象回路に対する最適化シナリオの実行の形とは異なる形で、最適化シナリオを実行する手段と、を備える装置が提供される。
【００８４】
或る回路に対して多数の最適化シナリオを試して評価するプロセスは、必要に応じて準備できる。例えば、各最適化シナリオを順番に、例えばランダムな順序で試すことができる。
【００８５】
好適な一実施形態において、各最適化シナリオは、最適化対象の回路の同じ初期記述に対して動作する。この場合、各最適化シナリオは、事実上、他のシナリオから独立して実行されるため、例えば、並行して動作する複数のプロセッサ上での、全最適化シナリオの並行した実行が可能であると共に、実際に好ましい。
【００８６】
別の好適な実施形態において、最適化シナリオは、連続して（次々に）実行され、最も好ましくは、連続する各シナリオは、以前のシナリオの何れかで発見された最善の結果を開始点として使用する。この場合、最適化シナリオを実行（試行）する順序は、必要に応じて選択することもできる。
【００８７】
更に、（時間等が許す場合）上記に従った最適化シナリオの並列実行と連続実行との両方を試すこともできる。
【００８８】
回路設計の態様を最適化するために最適化シナリオを使用している時、通常は、その最適化シナリオを特に進化させた対象回路に対して使用されているのではなく、特に意図されなかった回路を最適化するために使用されているであろうことは理解されよう。
【００８９】
これは、それ自体が新しく、利点になり得ると考えられる。したがって、本発明の第十二の態様によれば、設計対象の電子回路を最適化する方法であって、
対象回路向けに導出された最適化シナリオを、対象回路とは異なる回路を最適化するために使用するステップを備える方法が提供される。
【００９０】
本発明の第十三の態様によれば、設計対象の電子回路を最適化する装置であって、
特定の対象回路向けに導出された最適化シナリオを、対象回路とは異なる回路を最適化するために使用する手段を備える装置が提供される。
【００９１】
回路設計プロセスの「トレーニング」及び「運用」段階を上記で別々に説明してきたが、当業者が理解するように、本発明は、こうした個別のプロセスに関係し、これらを対象にするだけでなく、最適化シナリオを導出し、その後、使用して電子回路設計を最適化する組み合わせ済みの動作にも関係すると共に、これを範囲に含める。
【００９２】
したがって、本発明の第十四の態様によれば、電子回路の設計を最適化する方法であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、
一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行するステップと、
複数の最適化により決定された最適化結果の一つを、回路に対して使用する最適化として選択するステップと、を備える方法が提供される。
【００９３】
本発明の第十五の態様によれば、電子回路の設計を最適化する装置であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用する手段と、
異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオとして提供する手段と、
一組の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行する手段と、
複数の最適化により決定された最適化結果の一つを、回路に対して使用する最適化として選択する手段と、を備える装置が提供される。
【００９４】
本発明の第十六の態様によれば、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、
一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行するステップと、
複数の最適化により決定された最適化結果の一つを、回路に対して使用する最適化として選択するステップと、により最適化された電子回路が提供される。
【００９５】
当業者に理解されるように、こうした本発明の態様及び実施形態は、必要に応じて、本明細書で説明した本発明の好適な任意の特徴の何れか一つ以上又は全てを含み得ると共に、実際に含むことが好ましい。
【００９６】
本発明は、したがって、電子回路を構築するための本発明の手法の使用と、本発明の手法を使用して構築した電子回路とにも関係する。回路自体は、例えば、既知の回路設計及び構築手法を使用する等、任意の適切な形で構築できる。
【００９７】
したがって、本発明の第十七の態様によれば、電子回路を構築する方法であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、
一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行するステップと、
複数の最適化により決定された最適化結果の一つを、回路に対して使用する最適化として選択するステップと、
選択された回路の最適化を使用して、電子回路を設計及び構築するステップと、を備える方法が提供される。
【００９８】
本発明の第十八の態様によれば、電子回路を構築する装置であって、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用する手段と、
異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオとして提供する手段と、
一組の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行する手段と、
複数の最適化により決定された最適化結果の一つを、回路に対して使用する最適化として選択する手段と、
選択された回路の最適化を使用して、電子回路を設計及び構築する手段と、を備える装置が提供される。
【００９９】
本発明の第十九の態様によれば、
複数の異なる電子回路のそれぞれに対して最適化シナリオを進化させるために進化的アルゴリズム又はアルゴリズム群を使用するステップと、
異なる回路のために進化させた二つ以上の最適化シナリオを、設計中に電子回路を最適化するために使用する一組の最適化シナリオに含めるステップと、
一組の複数の最適化シナリオから二つ以上の最適化シナリオを使用して、最適化対象である電子回路の最適化を実行するステップと、
複数の最適化により決定された最適化結果の一つを、回路に対して使用する最適化として選択するステップと、
選択された回路の最適化を使用して、電子回路を設計及び構築するステップと、により構築された電子回路が提供される。
【０１００】
当業者に理解されるように、こうした本発明の態様及び実施形態は、必要に応じて、本明細書で説明した本発明の好適な任意の特徴の何れか一つ以上又は全てを含み得ると共に、実際に含むことが好ましい。
【０１０１】
当業者に理解されるように、トレーニング及び運用段階は、同じハードウェア及び／又はソフトウェア等を使用して、連続して実行してよく、或いは、個別に、異なる場所で及び／又は異なる個人及び／又は組織により、同様に実行可能である。例えば、最適化シナリオは、電子設計自動化ツール業者が導出し、回路の最適化（運用段階）は、その後、ＥＤＡツールの顧客又はエンドユーザが実行できる。同様に、個人又は組織は、独自の最適化シナリオの組、及び／又は最適化シナリオのプール用の組を導出し、その後、それらを利用して回路設計を最適化できる。
【０１０２】
更に、最適化シナリオの進化と、使用する一組の最適化シナリオへの包含とのプロセスは、継続することが可能であると共に好ましいと理解されよう。したがって、トレーニング段階は、運用段階が利用され始めた際に停止する必要はない。例えば、継続的なトレーニング段階により特定及び導出された追加の有益な最適化シナリオは、使用すべき一組の最適化シナリオに追加できる。同様に、回路設計を最適化するために一組の最適化シナリオを使用している際に（即ち、運用段階中に）確認された弱点又は最適化性能の低さから、最適化シナリオの進化の対象となる新たな回路を特定し、使用すべき一組の最適化シナリオに含めることができる。
【０１０３】
本発明は、この技術において既知であるツール及び手法等、任意の適切な電子設計自動化ツール向けに最適化シナリオを導出及び使用するために使用し得る。本発明は、限定はされないものの、特にBerkeley SISシステムにより、その最適化シナリオ（スクリプト）に対して使用するのに適している。本発明のBerkeley SISシステムへの応用において、SISソフトウェア自体を修正する必要はない。
【０１０４】
本発明は、汎用プロセッサ、デジタル信号プロセッサ、特定用途向け信号プロセッサ、フィールドプログラマブルデバイス、特定用途向け集積回路、物理的に最適化された集積回路、及びシステムオンチップ集積回路等、あらゆる種類の回路設計の最適化に適用できる。特にデジタル電子機器に応用可能だが、必要に応じてアナログ回路にも使用できる。本発明は、したがって、本発明の方法及び／又は装置の何れかを使用して設計された電子回路と、本発明の方法及び／又は装置の何れかを使用して、回路自体を構築するステップ又は手段を含む、電子回路を構築する装置又は方法とにも拡張される。
【０１０５】
当業者に理解されるように、本明細書で説明した本発明の全ての態様は、必要に応じて、本明細書で説明した本発明の任意の好適な特徴の何れか一つ以上又は全てを含むことが可能である共に、実際に含むことが好ましい。したがって、例えば、回路に対して最適化シナリオを導出するべきである場合、好ましくは、進化プロセスを使用して導出する。
【０１０６】
本発明による方法は、ソフトウェア、例えば、コンピュータプログラムを少なくとも部分的に使用して実現し得る。したがって、更なる態様から見る時、本発明は、データ処理手段にインストールされた時に本明細書で説明した方法又は複数の方法を実行するように特に構成されたコンピュータソフトウェアと、データ処理手段において動作させた時に本明細書で説明した方法又は複数の方法を実行するためのコンピュータソフトウェアコード部分を備えるコンピュータプログラム要素と、データ処理システムにおいて実行した時に本明細書で説明した方法又は複数の方法のステップの全てを実行するように構成されたコード手段を備えるコンピュータプログラムとを提供する。本発明は、データ処理手段を備える電子設計又は構築システムを運用するために使用される時、データ処理手段と連動して、前記システムに本発明の方法のステップを実行させるようなソフトウェアを備えるコンピュータソフトウェアキャリアにも拡張される。こうしたコンピュータソフトウェアキャリアは、ＲＯＭチップ、ＣＤ−ＲＯＭ、又はディスク等の物理格納媒体を含むことが可能であり、或いは、配線を通る電子信号、衛星等へ向かう光信号又は無線信号のような信号にすることもできる。
【０１０７】
更に、本発明の方法の全てのステップをコンピュータソフトウェアによって実行する必要はなく、したがって、更に幅広い態様から見て、本発明が、本明細書で述べた本発明のステップの少なくとも一つを実行するためのコンピュータソフトウェアと、コンピュータソフトウェアキャリアにインストールされたこうしたソフトウェアとを提供することは理解されよう。
【０１０８】
本発明は、したがって、コンピュータシステムにより使用するコンピュータプログラム製品として適切に実現し得る。こうした実施形態は、コンピュータ読み取り可能な媒体、例えば、ディスケット、ＣＤ−ＲＯＭ、ＲＯＭ、又はハードディスク等の有形媒体上に固定されるか、或いは、モデム又は他のインタフェース機器を介して、光学又はアナログ通信線を一部として含む有形媒体を通して、若しくはマイクロ波、赤外線、又は他の伝送手法を一部として含むワイヤレス手法を使用した無形状態で、コンピュータシステムへ伝送可能な、一連のコンピュータ読み取り可能な命令を含み得る。一連のコンピュータ読み取り可能な命令は、本明細書で以前に説明した機能の全部又は一部を実現する。
【０１０９】
当業者には、こうしたコンピュータ読み取り可能な命令を、多くのコンピュータアーキテクチャ又はオペレーティングシステムで使用する多数のプログラミング言語で記述可能であることは理解されよう。更に、こうした命令は、半導体、磁気式、又は光学式を一部として含む、現在又は将来の任意のメモリ技術を使用して格納し得るか、或いは、光、赤外線、又は無線を一部として含む、現在又は将来の任意の通信技術を使用して伝送し得る。こうしたコンピュータプログラム製品は、添付の印刷又は電子文書と共に、着脱式媒体、例えば、パッケージソフトウェアとして配布すること、コンピュータシステム、例えば、システムＲＯＭ又は固定ディスク上に事前にロードすること、或いは、ネットワーク、例えばインターネット又はワールドワイドウェブ上のサーバ又は電子掲示板から配信することが考えられる。
【発明を実施するための最良の形態】
【０１１０】
次に、本発明の多数の好適な実施形態を、単なる一例として、以下の添付図面を参照して説明する。
【０１１１】
次に、Berkeley SIS電子機器設計自動化システムを参照して、本発明の好適な実施形態を説明する。SISシステムは、例えば、E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli, SIS: A system for sequential circuit synthesis. Technical Report UCB/ERL M92/41, University of California, Berkeley, 1992、及び、E. M. Sentovich, Sequential Circuit Synthesis at the Gate Level, PhD thesis, Dept. Electrical Engineering and Computer Science, University of California, Berkeley, 1992において説明されている（しかしながら、SISシステムを参照して本発明を説明するが、本発明は、当業者に理解されるように、SISシステムに限定されず、電子設計自動化用の他の手法においても応用及び使用することが可能であることに留意されたい）。
【０１１２】
この技術において既知であるように、SISソフトウェアは、自由に利用可能であり、実地及び文献の両方で広範に使用されている。したがって、周知されていると共に、十分に理解された電子設計自動化ツールである。SISは、技術非依存最適化、テクノロジマッピング、及び技術依存最適化を実行できる。
【０１１３】
SIS最適化シナリオは、SISソフトウェアにテキストファイルで供給される「スクリプト」として与えられる。SISシステム用の優れた汎用スクリプトを導出することに対する多大な努力が、理論及び手動実験によりなされており、選定されたスクリプトがSISソフトウェアの配布に含まれている。SISは、最適化スクリプトに出現し得る多数の異なる最適化コマンドを提供し、こうしたコマンドの多くは、挙動を微調整する数値パラメータ及びオプションフラグの形を取る。
【０１１４】
最も広範に使用される三種類のSISスクリプトは、script.rugged、script.algebraic、及びscript.booleanである。これらのスクリプトを以下に記載する。
【０１１５】
script.rugged:
＃初期の前処理：このコマンド有り及び無しの両方を試行：
full_simplify
更なる改善の可能性がなくなるまで反復し、最善の結果を維持：
{
sweep
eliminate -1
simplify -m nocomp
eliminate -1
sweep
eliminate 5
simplify -m nocomp
resub -a
fx
resub -a
sweep
eliminate -1
sweep
full_simplify -m nocomp
}
【０１１６】
script.algebraic:
＃初期の前処理：このコマンド有り及び無しの両方を試行：
full_simplify
更なる改善の可能性がなくなるまで反復し、最善の結果を維持：
{
sweep
eliminate 5
simplify -m nocomp -d
resub -a
gkx -abt 30
resub -a
sweep
gcx -bt 30
resub -a
sweep
gkx -abt 10
resub -a
sweep
gcx -bt 10
resub -a
sweep
gkx -ab
resub -a
sweep
gcx -b
resub -a
sweep
eliminate 0
decomp -g*
}
【０１１７】
script.boolean:
＃初期の前処理：このコマンド有り及び無しの両方を試行：
full_simplify
更なる改善の可能性がなくなるまで反復し、最善の結果を維持：
{
sweep
eliminate -1
simplify
eliminate -1
sweep
eliminate 5
simplify
resub -a
gkx -abt 30
resub -a
sweep
gcx -bt 30
resub -a
sweep
gkx -abt 10
resub -a
sweep
gcx -bt 10
resub -a
sweep
gkx -ab
resub -a
sweep
gcx -b
resub -a
sweep
eliminate 0
decomp -g*
eliminate -1
sweep
}
【０１１８】
SISを使用した一般的な最適化戦略では、script．ruggedを試し、利用可能な時間内に結果を生成できなかった場合、script.algebraicを使用する。
【０１１９】
本発明では、より正確に実行タイミングを測定可能にすると共に、進化的アルゴリズムソフトウェア（完全に分離されている）によるアクセスを容易にするために最適化結果のログを取れるようにする非常に僅かな追加を除き、標準のSIS1.3ソフトウェアを変更の無い状態で使用した。
【０１２０】
図３は、電子回路設計向けの最適化シナリオ導出用のシステムと、本発明に従った、設計対象の電子回路を最適化するためのこうしたシナリオの使用とを概略的に示している。
【０１２１】
図３に図示し、更に上述したように、本発明のシステムは、二つの別個の部分又は段階に分かれると考えられ、第一のトレーニング段階１０では、進化的アルゴリズムを使用して、選択された電子回路用の最適化シナリオが導出され、第二の運用段階１１では、導出された最適化シナリオを使用して、設計対象の新たな電子回路を最適化する。
【０１２２】
図３に示したように、最適化シナリオが導出されるトレーニング段階１０は、多数のステップを含む。
【０１２３】
第一に、選択された個々の回路又は対象となる回路の小グループを、最適化シナリオ導出プロセスへの入力として提供する（ステップ１２）。
【０１２４】
次に、進化的アルゴリズムを使用して、入力回路及び回路グループのそれぞれに対して、専門化した相対的に高速の最適化シナリオを生成する（ステップ１３）。これにより、入力された個々の回路又は回路のグループのために特に導出された、一組の進化済み高速最適化シナリオが提供される（ステップ１４）。
【０１２５】
次に、一つ以上の進化済み専門最適化シナリオを選択し、最適化シナリオの組（セット）を形成し（ステップ１５）、その後、設計対象の新たな回路を最適化するために使用する。
【０１２６】
どの最適化シナリオを、使用すべき一組の最適化シナリオ１５に含めるかの選択は、必要に応じて実行できる。例えば、最適化シナリオが最適化性能を改善するであろう対象回路以外の回路（即ち、補助回路）の推定数、及び／又は、最適化シナリオとそれが最適化性能を改善する回路とが、一組の最適化シナリオ内に存在する他の最適化シナリオをいかに良好に補完するか、を基準にすることができる。
【０１２７】
図３に示したように、例えば、標準汎用シナリオを含む手動設計シナリオ１６又は進化させた汎用性の高いシナリオ１７等の、他の方法によって生成した最適化シナリオにより、一組の進化済み最適化シナリオ１５を増大させることも可能である。
【０１２８】
各回路（又は回路のグループ）用に最適化シナリオを進化させるためにステップ１３において使用する進化的アルゴリズムは、任意の適切な形態をとることができる。図２は、進化的（遺伝的）アルゴリズムの基本動作を概略的に示す。こうした形で動作する進化的アルゴリズムは、本発明での使用に適している。
【０１２９】
図２に示したように、進化的アルゴリズムは、解候補（即ち、この場合の最適化シナリオ）の初期セットを取り出し（ステップ２１）、その後、所望のタスクにおける解候補の性能の評価（一般的には、解候補の「適応度」の測定と呼ばれる）を行うこと（ステップ２２）で基本的に動作する。この評価において性能が最も低いことが分かった解候補は、廃棄され（ステップ２３）、性能が良好であることが分かった候補は、新たな、できれば改良された解候補を進化させるのに使用する「親」として機能させるために選択される（ステップ２４）。
【０１３０】
選択された「親」解候補は、何らかの方法（ランダム等）で結合及び／又は変更を行い、何らかの新しい解候補（一般的には、「子孫」候補と呼ばれる）を形成し（ステップ２５）、その後、新たに進化させた解候補をそれ自体で進化させ、定められた何らかの終点に達するまでプロセスを反復する（ステップ２６）。
【０１３１】
本発明において、使用された進化的アルゴリズムは、通常と異なる特徴を有していない遺伝的アルゴリズムである。こうした遺伝的アルゴリズムは、例えば、J. H. Holland, Adaption in Natural Artificial Systems, Ann Arbor, Unicersity of Michifan Press, 1975、及びD. E. Goldberg, Genetic Algorithms in Search, Optimisation and Machine Learning, Addison Wesley, 1989において説明されている。
【０１３２】
使用した遺伝的アルゴリズムでは、３０個の母集団に対して、切り捨て及びエリート主義による線形ランク選択を使用した。各進化動作は、最適化シナリオの異なる初期集団により開始され、各最適化シナリオは、ランダムに生成され、厳密に三コマンドの長さである（当然ながら、必要に応じて、既存の結果（手動設計又は以前に進化させたもの等であっても）から進化動作を開始することも可能である）。
【０１３３】
最適化シナリオの適応度を評価し、順序付けするため、最初に、各最適化シナリオがもたらした最適化結果（即ち、最適化品質測定基準）により、最適化シナリオを比較した。シナリオの最適化品質が等しかった場合、候補シナリオは、最適化シナリオ（スクリプト）が終了するのに要した時間によりランク付けした（より高速のシナリオを優先）。それでも同点になる場合、最も短い候補シナリオを最高位とした（この技術において既知であるように、こうした固定された優先度を有する多数の適応度基準を扱う方法は、辞書編集用又は辞書式の配列と呼ばれる場合が多い）。
【０１３４】
最適化シナリオ候補は、通常、数百世代に渡って進化させ、最終出力の進化済み最適化シナリオとした。この実施形態において、最適化シナリオ候補の進化（図２のステップ２５）を行う際に可能とした「遺伝的」変動は、次の通りとした。
【０１３５】
Mutation-New Command（突然変異−新しいコマンド）：
シナリオのコマンドを新たなランダムコマンドと置き換え、パラメータも全てランダムに選択する。
【０１３６】
Mutation-New Command Variant（突然変異−新しいコマンド変異形）：
コマンドの特定のバージョンを定義する記号フラグをランダム化する。コマンドに関連する数値パラメータの数が、これにより変化せず、こうしたパラメータの有効範囲も不変である場合、数値パラメータは変化させない。そうでない場合、新しいコマンド変異形に関連する任意の数値パラメータをランダムに生成する。
【０１３７】
Mutation-Parameters（突然変異−パラメータ）：
コマンドの数値パラメータの一つを、増殖型遺伝的アルゴリズム（ＢＧＡ）突然変異法により調整する（H. Muhlenbein and D. Schierkamp-Voosen, The Science of Breeding and its Application to the Breeder Genetic Algorithm BGA, Evolutionary Computation, 1(4):335-360, 1994を参照）。
【０１３８】
Homologous crossover（相同交叉）：
標準の二点交叉で、関連するコマンドからパラメータが分離されない状態を常に維持する。
【０１３９】
Nonhomologous crossover（非相同交叉）：
上記と同様だが、交叉点間のセグメントは、ランダムに転位させる。
【０１４０】
Insert（挿入）：
新しいランダムコマンド一個をランダムな位置に挿入し、任意のパラメータをランダムに生成する。
【０１４１】
Delete（削除）：
ランダムに選択したコマンド一個を取り除く。
【０１４２】
Block insert（ブロック挿入）：
一つの親シナリオにおいて、ランダムな位置にあるランダムな長さのコマンドの連続配列を選択し、第二の親のランダムな位置に挿入し（シナリオ長を増加させ）、子孫を生成する。
【０１４３】
Block delete（ブロック削除）：
ランダムな位置にあるランダムな長さのコマンドの連続配列を選択し、取り除く。
【０１４４】
こうした「遺伝的」変化演算子は、整数のみを使用する最適化シナリオの直接型数値表現に作用するように構成した。様々な遺伝変化演算子に対して選択した確率は、実験により導いた。他の手法も、当然ながら可能である。最適化シナリオの長さを変更する演算子の使用確率は、選択しない状態で最適化シナリオに増大又は縮小の傾向が備わらないようにバランスを取った。使用した数値表現は、各SISコマンドが有効なパラメータセットを有する状態が保証されるように、即ち、進化中に無効な最適化シナリオが生じ得ないように、選択した。
【０１４５】
上記の遺伝的アルゴリズムを使用して、対象となる選択回路（対象回路）向けに、上述の選択（適応度）基準を用いて最適化シナリオを進化させた。進化動作中には、最適化品質の改善が停止した後でも、通常は、最適化の速度が改善する最終段階が存在することが分かった。
【０１４６】
次に、図３に示した運用段階１１、即ち、新たな回路を最適化する一組の選択された最適化シナリオの使用を参照すると、図３に示したように、このプロセスは三つのステップを有する。最初に、ステップ１８において、最適化対象の新たな回路を入力する。次に、一組の最適化シナリオ１５からの複数の最適化シナリオを（例えば、連続又は並行して）使用し、新たな回路の最適化を試み（ステップ１９）、最善の最適化結果を、その回路のための最適化として取り出す（ステップ２０）。言い換えると、良好な最適化結果が達成されるまで、その組に含まれる複数の選択済み専門最適化シナリオを試す。
【０１４７】
この実施形態において、一組の最適化シナリオ１５内の全ての最適化シナリオを、最適化対象である全ての新しい回路それぞれに対して試行する。または、試行する最適化シナリオを何らかの形態で選択すること、例えば、回路の特定の種類又は複数の種類に対する最適化シナリオの既知の性能に基づいて選択することも可能である。
【０１４８】
図３に示したように、試行する各最適化シナリオに制限時間を設定し、制限時間に達した時に、最善の結果を取り出す。これは、プロセスの全体的な効率を確保するのに役立つ（但し、必須ではない）。
【０１４９】
本発明において、運用段階で新たな回路を最適化するために最適化シナリオを使用している時、シナリオは、トレーニング段階で実行されたものとは異なる形で実行される。これは、トレーニング段階中、進化的プロセスが専門の対象回路を最適化する目的のみを有する最適化シナリオを開発することに向けられるという事実を考慮するためである。しかしながら、運用段階において、最適化シナリオは、対象回路とは異なる回路を最適化するために使用され、即ち、意図されていない目的で使用される。したがって、動作段階において僅かに異なる形で最適化シナリオを使用することは有益となり得る。
【０１５０】
これを考慮に入れるため、単にシナリオの実行の最も終わりに最適化シナリオの結果を評価するのではなく、運用段階では、最適化シナリオの各ステップ後に、（例えば、各ステップ後に適切な品質測定基準を出力するコマンド（下記のSIS print_stats-fコマンド等）を含めることで）最適化の品質を測定し、最善の結果を取り出す。単純に終了時ではなく、シナリオの単一ステップ毎に最適化シナリオの結果を評価するため、この仕組みは、「シングルステッピング」と呼ぶことができる。
【０１５１】
更に、例えば、運用段階中に最適化シナリオの反復（即ち、繰り返し実行）を可能にし、例えば、毎回、それまでの最善の結果から開始することも望ましい。トレーニング段階では、単一最適化シナリオの長さを増加させ、単一の反復内で繰り返しに対応できるため、これを行う必要はない。しかしながら、一定の対象回路向けに特異的に進化させた最適化シナリオを、運用段階中に他の回路に応用する時には、反復は有利となり得る。
【０１５２】
運用段階１１のステップ１９において、多数の最適化シナリオを最適化対象の新たな各回路に試す方法は、必要に応じて選択できる。図４及び５は、こうした仕組みの二種類の可能な選択肢を示している。
【０１５３】
図４に示した仕組みにおいて、各最適化シナリオ３０は、最適化対象の新たな回路１８に並行して適用され、各シナリオ３０は、最適化対象の回路の同じ初期記述に対して動作する。その後、最善の結果２０を取り出す。この仕組みは、例えば、実行を高速化するために、並行して動作する複数のプロセッサ上で実行できる。
【０１５４】
図５は、最適化シナリオ１５を最適化対象の新たな回路１８に連続して適用する別の仕組みを示しており、新たな各最適化シナリオは、以前に試行された最適化シナリオの何れかが発見した最善の結果に対して動作する。したがって、回路１８に対して試行する最適化シナリオを選択し（ステップ３１）、それまでに発見された最善の結果に適用し（ステップ３２）、その後、最終結果２０が選択されるまで、新たな最適化シナリオの選択及び使用等を行う。この仕組みでは、例えば、最適化プロセスを再び更に強化し得るように、最適化シナリオを試す順序を選択することが可能である。
【０１５５】
SISシステムに付属の標準最適化シナリオ（スクリプト）を使用して、本発明の回路最適化システムの性能をSISシステムの性能と比較した。この性能評価では、
広く使用されているMCNC’91ベンチマーク回路セットから７４個のテスト回路を選び出した（S. Yang, Logic synthesis and optimization benchmarks user guide version 3.0, Technical report, Microelectronics Center of North Carolina, P. O. Box 12889, Research Triangle Park, NC 27709, 1991、及びN. Whitaker, Status report on EDA benchmarks, Technical report STEED/T1/01/4, MINT Group, Dept. Computer Science, Univ. Manchester, UK.参照）。これらの回路を以下の表１Ａ〜表１Ｃに記載する。
【０１５６】
【表１Ａ】
2009505198.tif 000003
【表１Ｂ】
2009505198.tif 000004
【表１Ｃ】
2009505198.tif 000005
【０１５７】
標準SISシナリオの性能を測定するために、script.rugged、script.algebraic、script.boolean、及びfull_simplifyのそれぞれを単独で各回路に対して実行した。コンピュータは、Linuxで動作するメモリ５１２Ｍバイトの２．２ＧＨｚインテルペンティアム（登録商標）ＰＣを使用した。
【０１５８】
各スクリプトは、最初のfull_simplifyコマンドが有る状態と無い状態との両方で別個に試した。各組み合わせには、各回路に対する２４時間のプロセッサ時間と、３６時間の実（時計）時間との何れか短い方を与えた。最初の回路で改善が得られない場合、常にスクリプトの結果がその最初の回路となるようにした。回路は、SISソフトウェアの配布に含まれている形態でSISに入力した。「更なる改善の可能性がなくなるまで反復」のスクリプト基準は、改善をもたらさなかった最初の反復後にスクリプトが終了されると解釈した。
【０１５９】
各回路ｃについて、本発明の方法により打破すべき対象を、こうした汎用SIS標準スクリプトから見た最善の結果として取り出し、これをgpscと呼ぶこととした。
【０１６０】
ここで、一部のスクリプトは確率論的であり、コンピュータの乱数発生器以外は同一の条件下で繰り返した時に、僅かに異なる結果を発生させる可能性があるが、本評価の結果は、これを考慮しなくとも十分に際限可能であることが分かった。
【０１６１】
シナリオは、技術非依存最適化に使用した。選択した最適化基準は、SISコマンドprint_stats -fにより報告されるような因数分解形でのリテラル数の最小化とした。上記のように、この最適化基準は、回路を表すブール関数の有向非循環グラフにおける論理の全体的な複雑性の尺度を提供する。回路の入力から出力までの遅延（最長経路）等、他の最適化基準は、要で有れば考慮可能であるが、この評価では考慮していない。
【０１６２】
同様に、これらの例において、新たな専門最適化シナリオ（スクリプト）の進化中、即ち、トレーニング段階１０中に使用した品質測定基準は、最適化シナリオ終了時の因数分解形でのリテラルの計数である。言い換えると、SISコマンドprint_stats -f（因数分解形でのリテラル数を計測させる）を、問題のシナリオが提供する最適化品質の尺度として使用した。運用段階において最適化対象の新たな回路に適用した時の、進化済み最適化シナリオに関するこの数字を、上記のような任意の汎用標準SISスクリプトの実行により生じた、最小の対応する数字と比較した。
【０１６３】
進化的プロセスにおいて、進化済み最適化シナリオ及び進化動作は、メモリ２５６Ｍバイトの１．６ＧＨｚラップトップＰＣ上で実行した。進化中に最適化シナリオを終了するために与えた最大時間量は、どの対象回路が最適化されているかに応じて変化させたが、６００秒を超えないようにした。上記の進化的アルゴリズムを使用したため、この制限時間内で、品質を犠牲にすることなく可能な限り高速となる最適シナリオの選択も行われた。以下の例において、進化済み最適化シナリオが一部の「補助」（即ち、非対象）回路において汎用性の高い標準スクリプトよりも優れた性能を示す場合、１．６ＧＨｚのＰＣで５５０秒を超えることはなく、通常は、これより遥かに短い時間となることに留意されたい。
【０１６４】
トレーニング段階の一例において評価比較を行った第一の対象回路は、回路Ｃ６２８８である（上記表１の回路５８）。この回路を例に選んだのは、SISシステムと、二分決定図に基づく別の最適化手法との両方において問題になると既に言われていたためである。
【０１６５】
本発明の方法は、回路Ｃ６２８８を最適化するために、以下の高速専門最適化スクリプトＡを進化させた。
Script A:
eliminate -1 10000 -1
eliminate -1 2989 47
fx
eliminate -1 841 -1
fx
eliminate -1 3631 47
fx
eliminate -1 1077 75
sweep
fx
simplify -m dcsimp
decomp -g
decomp -g
resub*
eliminate -1 9995 0
simplify -m nocomp -f disj_sup
simplify -i 3 -m dcsimp
eliminate -1 9990 -1
simplify -i 3 -m dcsimp
eliminate -1 9366 0
【０１６６】
スクリプトＡは、更に、テストセット内の他の７３個の回路うち１２個に対して良好な性能を示すこと（即ち、良好な最適化を行うこと）が分かった。したがって、こうした回路は、スクリプトＡの「補助回路」に含まれる。
【０１６７】
次の表２は、進化させたスクリプトＡが三種類の標準ＳＩＳスクリプトの何れよりも良好な性能を示した回路を示している。表２において、gpscは、三種類の汎用標準SISスクリプトの何れかによる因数分解形での最小のリテラル数であり、t(gpsc)は、そのスクリプトが要したプロセッサ時間を秒で表している。evoAc及びt(evoAc)は、スクリプトＡでの対応する性能を表す。標準のSISで最も遅いものが要した時間も記載している。
【０１６８】
この分析において、スクリプトＡは、直接的なタイミング比較を可能にするため、標準スクリプトと同じ２．２ＧＨｚの基準ＰＣ上で実行した。
【表２】
2009505198.tif 000006
【０１６９】
本実施形態は、更に、表１の回路７３であるtoo_large用の高速専門最適化シナリオを進化させるために使用した。以下のスクリプトＢは、この回路を最適化するために進化させた。
Script B:
collapse
full_simplify -o 1 -m snocomp -1
fx-oz
full_simplify -d -o 0 -m dscimp
x1_partition -n 18 -M 1 -t
full_simplify -o  0 -m dcsimp
eliminate -1 9395 0
full_simplify -d -o 0 -m dcsimp
full_simplify -o 0 -m dcsimp -1
fx -ol
fx -lz
full_simplify -o 0 -m dcsimp -1
decomp -g
eliminate -1 951 3
eliminate -1 789 19
full_simplify -o 1 -m dscimp
fx -1
full_simplify -d -o 0 -m dcsimp
full_simplify -o 1 -m dcsimp
eliminate -1 9365 8
full_simplify -o 0 -m snocomp
eliminate -1 4988 -1
eliminate -1 1934 10
full_simplify -o 0 -m dcsimp
fx -1
full_simplify -o 0 -m snocomp
eliminate -1 9371 7
fx -olz
fx
eliminate -1 9688 8
full_simplify -d -o 1 -m snocomp
fx -z
eliminate -1 9963 -1
full_simplify -o 0 -m dcsimp
decomp -q
eliminate -1 2032 6
simplify -i 20:1 -m nocomp
fx -olz
fx -ol
phase -g
eliminate -1 9838 -1
【０１７０】
ここで、スクリプトＢでは、冗長コマンドが全て削除されていることに留意されたい。言い換えると、回路too_largeを最適化する時にスクリプトの性能を低下させることなく、一つのコマンドも除去できない。
【０１７１】
以下の表３は、対象回路７３と、補助回路セット（試験を行った表１の７４個の回路からのもの）とを最適化するスクリプトＢの性能を示している。
【表３】
2009505198.tif 000007
【０１７２】
表３は、（改善がプラスである）各ケースにおいて、三種類の汎用標準ＳＩＳスクリプトの最善のものに対する改善のパーセントを示している。表３の右側の列は、問題の回路を最適化するためのスクリプトＢによるシングルステップ評価での性能改善を示している（即ち、上記のように、単にシナリオ終了時に結果を取り出すのではなく、最適化シナリオの各ステップ終了後に最適化の品質を測定する場合、最善の結果を取り出す場合）。
【０１７３】
スクリプトＢは、多数の回路に対して、特に運用段階において「シングルステップ」の場合に、最適化性能の改善をもたらすことが確認できる。
【０１７４】
１０個の進化済み専門最適化シナリオからなる組を使用して、更なる性能評価を実行した。この一組の最適化シナリオによる性能の分析結果を図６に示す。図６のアスタリスクは、回路と、組に含まれる１０個の最適化シナリオを実際に進化させた条件とを示す。これらの進化済み最適化シナリオは、上記のスクリプトＡ及びＢを含む。
【０１７５】
図６は、表１Ａ〜Ｃの７４個のサンプル回路全体に渡って、この一組の最適化シナリオの性能を、各回路に対する最善の汎用ＳＩＳ標準スクリプトと相対的に示している。図６では、各回路において試験された各スクリプトに対してバーが引かれている（一部は完全に重複）。図６では、相対サイズ「１」は、問題の回路に対する最善の汎用標準SISスクリプトの性能を表す。したがって、例えば、進化済み最適化シナリオの相対サイズ０．９は、進化済み最適化シナリオの性能が、その回路に対する最善の標準スクリプトより、１０％優れていることを意味する（最悪の結果は、図６の最上部の目盛りから外れる）。
【０１７６】
図６から、１０個のみの進化済み最適化シナリオによる組であっても、そのSISスクリプトの組を使用して達成可能な最適化性能は、既に半分を超える回路で、最善の汎用標準SISスクリプトより優れており、格段に優れている場合もあることが確認できる
【０１７７】
図６に示した結果は、上記のように、運用段階における最適化シナリオに対するシングルステップ評価プロセスを使用して導出した。シナリオの反復及び連続適用は使用していないが、必要に応じて可能であり、結果の改善につながり得る。
【０１７８】
更に、図６から、一組の進化済み最適化シナリオのみを使用した性能が一部の回路について劣っていることが確認できる。しかしながら、これは、例えば、標準の汎用ＳＩＳスクリプトを（例えば、動作に関する適切な許容時間と共に）一組の最適化シナリオに追加することで回避できる。これにより、一組の最適化シナリオの性能の上限は、（図６の相対サイズ＝１の水平実線で示す）相対サイズ「１」に定められる。性能は、更なる又は代わりの進化済み最適化シナリオを組に追加することでも改善できる。
【０１７９】
上記の例は単一の技術依存最適化基準のみを参照して説明してきたが、本発明による進化済み最適化シナリオは、通常は別個のものと考えられる複数の最適化活動に渡ることも可能である。
【０１８０】
例えば、技術依存最適化を単独で実行する代わりに、後続のテクノロジマッピングを実行するか或いは考慮に入れ、最適化の品質測定基準を、例えば、マッピング前のネットワークの因数分解形でのリテラルではなく、合計マッピング面積とすることも可能である。これにより、最適化シナリオでは、マッピングアルゴリズムの特性と、テクノロジライブラリとが、技術依存最適化と共に考慮される。
【０１８１】
製造技術の例は、SISソフトウェアと共に配布されるＣＭＯＳ標準セルライブラリstdcell2_2.genlibマッピングアルゴリズムにより説明される。例えば、テクノロジライブラリに記載の負荷限界を尊重する最小面積回路用に推奨されるSISコマンドmap -m 0 AF;phase -gによりマッピングを実行できる。これは、最適化シナリオの進化において、こうしたコマンドを全ての進化中の最適化シナリオに負荷し、結果的なマッピング面積を最適化の品質として取り出すことで可能となる。
【０１８２】
ライブラリstdcell2_2へのマッピングにより、回路my_adderを最適化するために、このように進化させた最適化シナリオを以下に示す。
simplify -m dscimp
map -f3 -B 0 -1
decomp -q
tech_decomp -a 2 -o 2
xl_partition -t
simplify
simplify -m dscimp
fx -z
＃所定の最終マッピング：
map -m 0 -AF;phase -g
【０１８３】
このスクリプトにおいて、進化させたスクリプトの第二のコマンドは、テクノロジライブラリに対する予備マッピングを実行する。後続のコマンドは、テクノロジライブラリ内の構成要素と、回路を表す有向非循環グラフ内のノードとの完全な対応を壊す。しかしながら、これにもかかわらず、予備マッピングコマンドが除去された場合、所定の最終マッピング後の面積が増加していることが分かった。したがって、スクリプトは、単純に最終マッピング前の因数分解形でのリテラルを最適化するか場合よりも、マッピングプロセスを考慮する度合いが高いと思われる。
【０１８４】
このシナリオのように、追加又は後期の最適化基準を考慮する最適化シナリオは、必要な場合、使用する一組の最適化シナリオに含めることが可能であり、これにより、「テクノロジへの認知性」が潜在的に高められる。
【０１８５】
回路の最適化後には、例えば、この技術で知られているような既知の手法を使用して、回路を構築できる。
【０１８６】
本発明が、少なくともその好適な実施形態において、既知の既存最適化手法に対する改善をもたらす、設計対象の電子回路を最適化するシステムを提供することは、上記から確認できる。電子回路の設計及び構築において使用する、改善されたツール及び手法が提供される。
【０１８７】
これは特に、一組の専門最適化シナリオを進化させることで達成され、シナリオは、次に、最適化対象の新たな回路を最適化するために使用され、最善の結果を最終的な最適化として取り出す。
【０１８８】
出願人は、特に、十分な進化を可能にする動作を十分に素早く行うスクリプトを進化させれば、通常は、既知の標準汎用スクリプトの何れよりも対象回路に良好に作用する専門最適化シナリオを生成することは比較的容易であると認識している。更に、優れた進化済み最適化シナリオは、実際に、最適化を完了するのに要するプロセッサ時間が一般的な既知の汎用標準スクリプトよりも短い。
【０１８９】
更に、特定の一回路を最適化するために進化させた最適化シナリオは、特に、最初の対象回路が十分に困難なものである場合、他の何らかの回路に適用した時に優れた結果を生む場合が多い。例えば、比較的小さな一回路を最適化するために進化させた最適化シナリオは、一部の大きな回路に対しても優れた結果を発生させる場合があり、逆も同様となり得る。
【０１９０】
これらは全て、比較的少数の最適化シナリオを含む組を進化により策定し、その後、こうした最適化シナリオのそれぞれを順番に最適化対象の新たな回路に試すのを容易にすることが可能であり、実際に、例えば、既に存在する既知の標準汎用最適化シナリオよりも改善された最適化性能を与える傾向があることを意味する。
【０１９１】
出願人は、更に、同じ対象回路に対して独立して進化させた最適化シナリオが、異なる補助回路の組を有する可能性があり、同様に、異なる対象回路を最適化するためにそれぞれ進化させた二種類の最適化回路も、全く異なる補助回路の組を有する可能性があることを発見した。これは、ごく僅かな進化済み専門最適化シナリオの補助回路を結合することで、実際には、多数の回路に対する性能の改善を網羅及び提供できることを意味する。
【０１９２】
更に、進化済み最適化シナリオの修正、例えば、冗長コマンドの除去により、最適化シナリオに対する回路の補助セットを変更できる。同様に、進化動作の途中で得られた最適化シナリオは、専門対象回路向けに完全に調整された進化動作の最終結果と比較して、改善された最適化性能を提供する補助回路セットの組が異なる場合がある。
【図面の簡単な説明】
【０１９３】
【図１】デジタル電子機器の設計用のプロセスを概略的に示す図である。
【図２】進化的アルゴリズムプロセスの例を概略的に示す図である。
【図３】本発明の実施形態を概略的に示す図である。
【図４】本発明の実施形態において回路を最適化する最適化シナリオの使用を概略的に示す図である。
【図５】本発明の実施形態において回路を最適化する最適化シナリオの使用を概略的に示す図である。
【図６】本発明の実施形態の最適化性能を概略的に示す図である。
【図１】
2009505198.tif 000008
【図２】
2009505198.tif 000009
【図３】
2009505198.tif 000010
【図４】
2009505198.tif 000011
【図５】
2009505198.tif 000012
【図６】
2009505198.tif 000013
【国際調査報告】
2009505198.tif 000014
2009505198.tif 000015
2009505198.tif 000016
2009505198.tif 000017
2009505198.tif 000018