(57)【要約】  発展的最適化手法に基づいて、アナログおよび混合信号（ＡＭＳ）回路を含む電子回路を設計する方法および装置。実施形態の一例では、１つ以上のコンピュータ上で実行するコンピュータ・プログラムを用いて、最適化手法を実施する。この最適化プログラムは、（ｉ）設計プロセスに対する最適化目的、および（ｉｉ）適応すべき制約機構に関する入力を設計者から受け取る。プログラムによって、制約付きまたは非制約最適化の定式化に対処することができる。種々の目的関数評価機構を実施する。また、プログラムは、連続的にエンコードする変数も考慮し、ＡＭＳ設計問題を解明するためには特に有用である。
2008507038.tif 000002
【特許請求の範囲】
【請求項１】
ＡＭＳ回路の設計を生成する方法であって、
最適化プログラムを定式化することから成り、前記定式化の行為（ａｃｔ）は、
少なくとも１つの設計目的を定義し、
少なくとも１つの制約を定義し、
少なくとも１つの制約処理機構を定義し、
少なくとも部分的に発展的最適化方法論に基づいて、前記最適化問題を最適化することから成り、前記方法論は、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的および／または制約に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの部分集合を選択し、
前記少なくとも１つの部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成る、方法。
【請求項２】
請求項１記載の方法であって、更に、少なくとも部分的に前記部分集合に基づいて、少なくとも１つの統計モデルを構築することを含む、方法。
【請求項３】
請求項２記載の方法であって、更に、少なくとも部分的に前記統計モデルからの情報に基づいて、候補解の新たな集合を構築することを含む、方法。
【請求項４】
請求項１記載の方法であって、更に、コンピュータ・ネットワークに結合されている複数の処理実体を用いて、前記少なくとも１つの目的を評価することを含む、方法。
【請求項５】
請求項２記載の方法であって、更に、コンピュータ・ネットワークに結合されている複数の処理実体を用いて、前記統計モデルを構築することを含む、方法。
【請求項６】
請求項１記載の方法であって、更に、前記最適化する行為に伴う複数の変数の少なくとも一部を、連続変数としてエンコードすることを含む、方法。
【請求項７】
請求項１記載の方法であって、更に、前記最適化する行為に伴う複数の変数の第１部分を連続変数としてエンコードし、前記複数の第２部分を実質的に離散変数としてエンコードすることを含む、方法。
【請求項８】
請求項１記載の方法であって、更に、前記最適化する行為の少なくとも一部の間に、少なくとも１つの変異演算子を適用することを含む、方法。
【請求項９】
請求項１記載の方法において、前記最適化する行為は、更に、候補解のより分散されている集合を選択的に、適正な収束を遂行するための中間または最終ステップとして優先的に用いることを含む、方法。
【請求項１０】
設計プロセスを用いて電子回路を設計する方法であって、
最適化問題を定式化し、
発展的プロセスを用いて前記問題を最適化して、解を得る、
ことから成る、方法。
【請求項１１】
請求項１０記載の方法において、前記定式化する行為は、少なくとも１つの設計目的を定義することを含む、方法。
【請求項１２】
請求項１１記載の方法において、前記定式化する行為は、更に、
少なくとも１つの制約を定義し、
少なくとも１つの制約処理機構を定義する、
ことを含む、方法。
【請求項１３】
請求項１１記載の方法において、前記最適化する行為は、
候補解の少なくとも１つの集合を与え、
前記少なくとも１つの集合に対して、前記少なくとも１つの目的を評価し、
少なくとも部分的に前記評価する行為に基づいて、前記少なくとも１つの集合から、少なくとも１つの部分集合を選択する、
ことを含む、方法。
【請求項１４】
請求項１３記載の方法において、前記最適化する行為は、更に、少なくとも部分的に前記少なくとも１つの選択した部分集合に基づいて、少なくとも１つのモデルを構築することを含む、方法。
【請求項１５】
請求項１４記載の方法において、前記最適化する行為は、更に、少なくとも部分的に前記少なくとも１つのモデルに基づいて、候補解の少なくとも１つの新たな集合を構築することを含む、方法。
【請求項１６】
請求項１４記載の方法において、少なくとも１つのモデルを構築する前記行為は、少なくとも１つの統計モデルを構築することを含む、方法。
【請求項１７】
請求項１５記載の方法において、少なくとも１つのモデルを構築する前記行為は、設計プロセスの間に前記モデルを徐々に構築することを含む、方法。
【請求項１８】
請求項１０記載の方法において、前記電子回路はＡＭＳ回路を備えている、方法。
【請求項１９】
請求項１８記載の方法において、前記最適化する行為は、少なくとも部分的に、データ通信している複数のコンピュータを有するコンピュータ・ネットワーク上で実行する、方法。
【請求項２０】
請求項１３記載の方法において、前記評価する行為は、少なくとも部分的に、データ通信している複数のコンピュータを有するコンピュータ・ネットワーク上で実行する、方法。
【請求項２１】
請求項１４記載の方法において、前記構築する行為は、少なくとも部分的に、データ通信している複数のコンピュータを有するコンピュータ・ネットワーク上で実行する、方法。
【請求項２２】
請求項１０記載の方法において、前記最適化する行為は、連続最適化変数をエンコードすることを含む、方法。
【請求項２３】
請求項２２記載の方法において、前記最適化する行為は、更に、前記連続変数と共に、離散最適化変数をエンコードすることを含む、方法。
【請求項２４】
請求項１０記載の方法であって、更に、前記最適化する行為の少なくとも一部において、少なくとも１つの変異演算子を提供することを含む、方法。
【請求項２５】
請求項１０記載の方法において、前記最適化する行為は、更に、候補解のより分散されている集合を選択的に、適正な収束を遂行するための中間または最終ステップとして優先的に用いることを含む、方法。
【請求項２６】
複数のデータを格納するように適合化したコンピュータ読み取り可能媒体であって、前記複数のデータは少なくとも１つのコンピュータ・プログラムを含み、前記少なくとも１つのプログラムは、少なくとも、
最適化問題を定式化し、
少なくとも部分的に発展的最適化方法論に基づいて前記最適化する、ことによって、電子回路の設計を生成するように適合されており、
前記方法論は、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的および／または制約に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの部分集合を選択し、
前記少なくとも１つの部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成る、コンピュータ読み取り可能媒体。
【請求項２７】
請求項２６記載のコンピュータ読み取り可能媒体において、前記媒体は、コンピュータ・システムのハード・ディスク・ドライブ（ＨＤＤ）を備えている、コンピュータ読み取り可能媒体。
【請求項２８】
請求項２６記載のコンピュータ読み取り可能媒体において、前記少なくとも１つのプログラムは、コンピュータ・ネットワークの多数の処理実体に跨って分散されている他のプログラムと通信するように適合化されている、コンピュータ読み取り可能媒体。
【請求項２９】
請求項２８記載のコンピュータ読み取り可能媒体において、前記少なくとも１つのプログラムは、少なくとも１つのクライアント部を有する分散アプリケーションのサーバ部を備えている、コンピュータ読み取り可能媒体。
【請求項３０】
請求項２８記載のコンピュータ読み取り可能媒体において、前記ネットワークは、ピア・ツー・ピア・ネットワークを備えている、コンピュータ読み取り可能媒体。
【請求項３１】
電子回路の設計に有用なコンピュータ・システムであって、
プロセッサと、
前記プロセッサとデータ通信するデータ記憶デバイスと、
少なくとも部分的に前記記憶デバイス内に常駐するコンピュータ・プログラムであって、少なくとも、
最適化問題を定式化し、
少なくとも部分的に発展的最適化方法論に基づいて、前記最適化問題を最適化する、ことによって電子回路の設計を生成するように適合化されており、
前記定式化は少なくとも１つの設計目的を定義し、
前記方法論は、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的および／または制約に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの部分集合を選択し、
前記少なくとも１つの部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成る、コンピュータ・システム。
【請求項３２】
請求項３１記載のコンピュータ・システムにおいて、前記１つのプログラムは、前記最適化する行為の少なくとも一部を実行するために、コンピュータ・ネットワークの多数の処理実体にまたがって分散されている他のプログラムと通信するように適合化されている、コンピュータ・システム。
【請求項３３】
請求項３１記載のコンピュータ・システムにおいて、前記１つのプログラムは、少なくとも部分的に前記部分集合に基づいて、少なくとも１つの統計モデルを構築するように適合化されており、前記構築する行為は、コンピュータ・ネットワークの多数の処理実体にまたがって分散されている他のプログラムと通信することを含む、コンピュータ・システム。
【請求項３４】
回路設計プロセスに伴う最適化を実行する方法であって、
最適化問題を構成し、
解集合の初期の１つを含む最適化アルゴリズムを設け、
前記アルゴリズムを用いて、少なくとも１つの基準に対して前記最適化問題を評価し、
前記基準が満たされない場合、前記基準が満たされるまで、前記解集合を発展させる、
ことから成る方法。
【請求項３５】
請求項３４記載の方法において、前記構成する行為は、最適化変数Ｘと、目的Ｙ（Ｘ）と、制約Ｃ（Ｘ）および関数Ｔ（Ｘ）とを指定することを含む、方法。
【請求項３６】
請求項３４記載の方法であって、更に、前記解集合の前記初期の１つを母集団とすることにより、前記最適化アルゴリズムを初期化することを含む、方法。
【請求項３７】
請求項３６記載の方法において、前記評価する行為は、前記初期解集合のメンバ毎に、少なくとも１つの目的および少なくとも１つの制約を評価することを含む、方法。
【請求項３８】
請求項３７記載の方法において、前記発展させる行為は、少なくとも部分的に前記評価する行為に基づいて、前記初期解集合を更新することを含む、方法。
【請求項３９】
請求項３４記載の方法において、前記発展させる行為は、少なくとも１つの変異演算子を、前記解集合の少なくとも一部に適用することを含む、方法。
【請求項４０】
請求項３８記載の方法において、前記発展させる行為は、少なくとも１つの変異演算子を、前記解集合の少なくとも一部に適用することを含む、方法。
【請求項４１】
請求項３４記載の方法において、前記少なくとも１つの基準は、前記解集合の発展する反復において、最良の解を得ることを含む、方法。
【請求項４２】
請求項３４記載の方法において、前記少なくとも１つの基準は、前記解集合の発展する反復において、パレート・サンプルの集合を得ることを含む、方法。
【請求項４３】
請求項３４記載の方法において、前記回路は、ＡＭＳ回路を備えており、前記プロセスは、更に、前記最適化問題に伴う複数の変数の少なくとも一部を、連続変数としてエンコードすることを含む、方法。
【請求項４４】
回路であって、
最適化問題を定式化し
少なくとも部分的に発展的最適化方法論に基づいて、前記最適化問題を最適化する、ことから成るプロセスによって設計され、
前記定式化は少なくとも１つの設計目的を定義し、
前記方法論が、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的および／または制約に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの部分集合を選択し、
前記少なくとも１つの部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成る、回路
【請求項４５】
請求項４４記載の回路において、前記回路はＡＭＳ回路を備えており、前記プロセスは、更に、前記最適化問題に伴う複数の変数の少なくとも一部を、連続変数としてエンコードすることを含む、回路。
【請求項４６】
回路設計プロセスにおいて、新たな候補解を作成する方法であって、
第１候補ｃを与え、
最適化変数ｘｉを特定し、
前記最適化変数に対してモデルｍｉを選択し、
前記候補ｃのｘｉの選択値を得て、
前記モデルに伴う分岐値を得て、
前記変数ｘｉを前記分岐値と比較し、
前記比較する行為に基づいて、前記モデルｍｉを下降し、
前記モデルｍｉのリーフ・セルに伴うデータに基づいて、ｘｉに対して新たな値を生成する、
ことから成る、方法。
【請求項４７】
請求項４６記載の方法において、前記特定する行為は、トポロジ順序にしたがって、少なくとも１つの変数を特定することを含む、方法。
【請求項４８】
請求項４６記載の方法において、前記最適化変数を連続変数としてエンコードする、方法。
【請求項４９】
請求項４８記載の方法において、前記回路はＡＭＳ回路を備えている、方法。
【請求項５０】
ＡＭＳ回路を設計する方法であって、
連続変数としてエンコードした少なくとも１つの変数を用いて、少なくとも１つの最適化問題を定義し、
少なくとも１つの制約機構を定義し、前記少なくとも１つの機構を、（ｉ）候補解の制約に基づく評価、および（ｉｉ）非制約目的関数評価から成る群から選択し、
前記定義する行為に少なくとも部分的に基づいて、発展的最適化プロセスを実行し、該最適化プロセスが、前記発展を促進するために、少なくとも１つの変異演算子を適用することを含む、
設計プロセスを実行することを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（優先権および関連出願）
本願は、２００４年７月１３日に出願した、同一名称の同時係属中の米国特許出願第１０／８９０，３４９号に対する優先権を主張する。その内容は、ここで引用したことにより、その全体が本願にも含まれるものとする。また、本発明は、２００４年５月１４日に出願し“Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｄｅｓｉｇｎｉｎｇ  Ｅｌｅｃｔｒｏｎｉｃ  Ｃｉｒｃｕｉｔｓ”（電子回路を設計する方法および装置）と題する、所有者が同一で同時係属中の米国特許出願第１０／８４６，７２７号にも関連があり、その内容も、ここで引用したことにより、その全体が本願にも含まれるものとする。
【０００２】
（著作権）
本特許文書の開示には、著作権保護の対象となる資料を含む部分がある。著作権所有者は、この特許文書または特許開示が、特許商標庁の特許ファイルおよび記録において見られるのと同じであれば、これをいかなる者がファクシミリで複製しても異議を唱えないが、それ以外ではあらゆる著作権を保有する。
【０００３】
（発明の分野）
本発明は、一般的には、電子回路設計の分野に関する。態様の一例では、本発明は、アナログ、混合信号およびＲＦ電子回路の設計に関する。
【背景技術】
【０００４】
（従来技術の説明）
特定用と集積回路（ＡＳＩＣ）、システム・オン・チップ（ＳＯＣ）デバイス、またはその他の種類の集積回路（ＩＣ）のような、電子回路を製造するための設計プロセスは、従来技術では周知である。実装するロジックまたは機能の種類に基づいて、これらの回路は、その特質をディジタル、アナログ、または混合信号（部分的にディジタルであり、部分的にアナログである回路）のいずれかに分類することができる。ディジタル電子回路の例には、非常に基本的なレベルではフリップ・フロップ（ＦＦ）、または非常に高レベルではマイクロプロセッサのパイプラインＣＰＵが含まれる。アナログ回路の例には、周知の位相ロック・ループ（ＰＬＬ）または演算増幅器（オペ・アンプ）が含まれる。混合信号設計の例には、部分的にディジタル機能と部分的にアナログ機能とを組み合わせたモデムＡＳＩＣのＳＯＣ実施態様が含まれる。
【０００５】
競争が激しい今日の市場では、設計者は製作に成功するために厳しく検査され、素早いターンアラウンド時間を有し、異なる製作プロセスに素早く移行する（例えば、もっと小さいサイズの機構または異なる幾何学的形状）ことができ、更に、他の設計と一体化し同じ半導体ダイ上に納めることができる設計を生成する圧力下にいる。ディジタル設計は、電子設計自動化（ＥＤＡ）ツールにより、この作業の多くを自動化できることによる恩恵を受けている。
【０００６】
対照的に、アナログまたは混成信号（ＡＭＳ）回路の設計は、回路の部分を設計するためには手作業の熟練を一層必要とする傾向がある。ディジタルおよびアナログ・ドメイン間を交差信号経路、ならびに幾何学的形状への非線形依存性に関するその他の現象を伴う複雑なフィードバック・ループにより、ブロックを構築するアナログ回路のレイアウトまたは幾何学的形状の変更には、通例、性能要件および設計制約を満たすことを確認するために、費用のかかるシミュレーションを必要とする。このために、長大な設計サイクルとなる場合が多く、専門の（人の）設計者による仲介が必要となる。ＡＭＳ回路設計は、したがって、電子回路を設計する際の隘路となっていると認識されている。
【０００７】
ＡＭＳ回路を設計する場合、デバイスの一致、寄生結合、ならびに熱および基板効果というような回路の物理的特性も、設計の成功を確保するためには、考慮にいれなければならない。性能の名目値は、一般に、多数の寄生結合によって劣化に晒されており、実際のデバイス・レイアウトを試す前に予測することは困難である。これらの劣化効果を過大評価すると、電力および面積の浪費となり、一方過小評価すると、回路がそれらの性能要件を満たさない結果となる。
【０００８】
電子回路設計および最適化には、種々の従来技術の技法が存在する。例えば、“ＤＡＲＷＩＮ：ＣＭＯＳ  ｏｐａｍｐ  Ｓｙｎｔｈｅｓｉｓ  ｂｙ  ｍｅａｎｓ  ｏｆ  ａ  Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ”（ＤＡＲＷＩＮ：遺伝アルゴリズムによるＣＭＯＳオペアンプ合成）  Ｋｒｕｉｓｋａｍｐ  ｅｔ  ａｌ．，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３２ｎｄ  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ，ｐｐ．４３３−４３８，１９９５では、演算増幅器（オペアンプ）を合成する方法が記載されている。その内容は、ここで引用したことにより、その全体が本願にも含まれるものとする。トポロジのばらつき、および原始デバイス（ｐｒｉｍｉｔｉｖｅ  ｄｅｖｉｃｅ）の寸法変化双方を、最適化装置によって検討し、全体的な費用関数（ｃｏｓｔ  ｆｕｎｃｔｉｏｎ）を最小にする。この方法は、手作業で導出する方程式を用いて、最適化変数を性能尺度と関係付けることによって、非常に高速な性能評価方法を得ている。この方程式集合を組み立てることは、通例、限定的な仮定の下でしか有効ではなく、検索空間に厳しい制限が強いられている。更に、この評価機構は、技術的現状のデバイス方程式（例えば、ＢＳＩＭデバイス・モデル）と比較すると、非常に精度が低い結果が得られるに過ぎない。この合成方法は、従前からの遺伝的アルゴリズムを採用しており、手近な例に対してはそれなりの結果を出すものの、最新の最適化手法よりは性能が劣っている。
【０００９】
２００２年１月１８日に公開され、“Ｍｅｔｈｏｄ  ｆｏｒ  Ａｕｔｏｍａｔｉｃａｌｌｙ  Ｓｉｚｉｎｇ  ａｎｄ  Ｂｉａｓｉｎｇ  Ｃｉｒｃｕｉｔ”（自動的に回路をサイジングしバイアスする方法）と題するＲｏｄｎｅｙ  Ｐｈｅｌｐｓ  ｅｔ  ａｌ．，の米国特許出願公開第２００３／０００９７２９号、および、同様に、“ＡＳＦ：Ａ  Ｐｒａｃｔｉｃａｌ  Ｓｉｍｕｌａｔｉｏｎ−Ｂａｓｅｄ  Ｍｅｔｈｏｄｏｌｏｇｙ  ｆｏｒ  ｔｈｅ  Ｓｙｎｔｈｅｓｉｓ  ｏｆ  Ｃｕｓｔｏｍ  Ａｎａｌｏｇ  Ｃｉｒｃｕｉｔｓ”（ＡＳＦ：カスタム・アナログ回路合成のための実践的なシミュレーションに基づく方法論）、Ｍ．Ｋｒａｎｎｉｃｋｉ  ｅｔ  ａｌ．，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ，ｐｐ．３５０−３５７，Ｎｏｖｅｍｂｅｒ  ２００１は、所与の性能仕様集合に向けて回路トポロジのサイズを決定するために用いられる枠組みについて記載している。これら双方の内容は、ここで引用したことにより、その全体が本願にも含まれるものとする。回路のシミュレーションに基づいて、性能を評価する。以前の最適化セッションからの解をデータベースに格納する。このデータベースに格納した情報が、設計問題に対する解を少ない時間量で求めるように、最適化エンジンを誘導する。以前の解または中間解をこのデータベースに格納するという方法は、しかしながら、この候補解の集合が、関連する性能空間の部分をカバーするという保証はない。先進の「シミュレーション・アニーリング」（ｓｉｍｕｌａｔｅｄ  ａｎｎｅａｌｉｎｇ）技法を「ヒル・クライミング」（ｈｉｌｌ  ｃｌｉｍｂｉｎｇ）技法と組み合わせた、混成最適化技法を適用する。最適化アルゴリズム自体は、その経験に基づいて検索空間の知識を構築することができない。
【００１０】
他にも種々の最適化技法が、文献において見つけることができる。これらの技法は、大まかに、決定論的手法（即ち、（局在）極小値に素早く収束する勾配系技法（ｇｒａｄｉｅｎｔ−ｂａｓｅｄ  ｔｅｃｈｎｉｑｕｅ）、またはある機能について大域的な最適条件を求める方向には確実性が高い統計的手法に分類することができる。アナログおよび混合信号回路設計問題における目的関数の複雑度を考えると、開いた標準化されたフレームワークにおいて適用できる十分なロバスト性を備えているのは、統計的最適化手法だけである。決定論的最適化アルゴリズムの高速収束特性を、統計的手法のロバスト性と組み合わせた混成手法も、同様に提供することができる。
【００１１】
統計的最適化アルゴリズムの例は多数ある。以下にあげるのは、選択した手法の短い参照リストの一例に過ぎない。（ｉ）シミュレーション・アニーリング：例えば、Ｋｉｒｋｐａｔｒｉｃｋ，Ｓ，Ｇｅｌａｔｔ，Ｃ．Ｄ．，およびＶｅｃｃｈｉ，Ｍ．Ｐ．“Ｏｐｔｉｍｉｚａｔｉｏｎ  ｂｙ  Ｓｉｍｕｌａｔｅｄ  Ａｎｎｅａｌｉｎｇ”（シミュレーション・アニーリングによる最適化）、Ｓｃｉｅｎｃｅ  ２２０，６７１−６８０，１９８３を参照のこと。（ｉｉ）微分算法。例えば、Ｓｔｏｒｎ，Ｒ．ａｎｄ  Ｐｒｉｃｅ，Ｋ．，“Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｅｖｏｌｕｔｉｏｎ  −  ａ  Ｓｉｍｐｌｅ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ａｄａｐｔｉｖｅ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｇｌｏｂａｌ  Ｏｐｔｉｍｉｚａｔｉｏｎ  ｏｖｅｒ  Ｃｏｎｔｉｎｕｏｕｓ  Ｓｐａｃｅｓ”（微分評価−連続空間に跨る大域的最適化のための単純で効率的な適応方式）  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＴＲ−９５−０１２，ＩＣＳＩ，Ｍａｒｃｈ  １９９５。そして（ｉｉｉ）遺伝的アルゴリズム。例えば、Ｋａｌｙａｎｍｏｙ  Ｄｅｂによる“Ｍｕｌｔｉ−ｏｂｊｅｃｔｉｖｅ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｕｓｉｎｇ  ｅｖｏｌｕｔｉｏｎａｒｙ  ａｌｇｏｒｉｔｈｍｓ”（発展的アルゴリズムを用いた多目的最適化）（１ｓｔ  ｅｄ．，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ  ｓｅｒｉｅｓ  ｉｎ  ｓｙｓｔｅｍｓ  ａｎｄ  ｏｐｔｉｍｉｚａｔｉｏｎ，ＩＢＳＮ−４７１−８７３３９−Ｘの第４章を参照のこと。以上の参考文献の各々は、その内容全体が、ここで引用したことにより、本願にも含まれるものとする。
【００１２】
最近では、以前の実験から得られた情報に基づいて統計的モデルを構築する技法が開発されている。この統計的モデルは、最適化問題に対する新たな候補解を示唆するために用いられる。この部類の最適化技法の特定的な実施形態が、２００２年１月１８日に出願され、“Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｐｔｉｍｉｚｉｎｇ  ａ  Ｓｏｌｕｔｉｏｎ  Ｓｅｔ”（解集合の最適化方法）と題するＭ．ＰｅｌｉｋａｎおよびＤ．Ｇｏｌｄｂｅｒｇの米国特許出願公開第２００３／００５５６１４号において紹介されている。その内容は、ここで引用したことにより、その全体が本願にも含まれるものとする。このモデルの欠陥には、（ｉ）連続最適化変数を直接操作（ａｄｄｒｅｓｓ）できないこと（連続最適化変数は、離散変数との間で両方向に転換される）。（ｉｉ）ネットワーク化したコンピュータ上で統計モデルの構築を並列処理できないこと（副母集団のモデルであれば、並列に構築することができるが）。また、開示した技法をアナログおよび混合信号回路設計問題に適用することは、記載されておらず、実施も容易ではない。
【００１３】
２００１年７月３１日にＤｅｌ  Ｍａｒ  Ｈｅｒｓｈｅｎｓｏｎに発行され、“Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｄｅｓｉｇｎｉｎｇ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔｓ”（集積回路の設計システムおよび方法）と題する米国特許第６，２６９，２７７号は、回路性能を、いわゆる多項式関数を用いて定式化する最適化デバイスを開示する。この数学的媒介を用いて、定式化設計問題の大域的最適を求めるために、高速最適化技法を応用する。多項式定式化で回路性能を表現することは、トポロジおよび技術に依存する作業であり、手が込みすぎる携行がある。
【００１４】
１９９８年７月１４日にＴｓａｉに発行され、“Ｏｐｔｉｍｉｚａｔｉｏｎ  ｍｅｔｈｏｄ  ａｎｄ  ｓｙｓｔｅｍ  ｈａｖｉｎｇ  ｍｕｌｔｉｐｌｅ  ｉｎｐｕｔｓ  ａｎｄ  ｍｕｌｔｉｐｌｅ  ｏｕｔｐｕｔ−ｒｅｓｐｏｎｓｅｓ”（多数の入力および多数の出力応答を有する最適化方法およびシステム）と題する米国特許第５，７８１，４３０号は、多数の入力および多数の出力応答を有するプロセスの定常状態性能を最適化する方法およびシステムを開示する。この方法およびシステムは、応答表面モデル（ＲＳＭ）モジュールを利用し、プロセスの名目的、統計的、そして多基準性能を最適化する、一元化した系統的な方法を提供する。このプロセスは、とりわけ、半導体製造プロセスまたはビジネス・プロセスとすることができる。
【００１５】
２００１年６月１９日にＦｉｓｈｅｒ−Ｂｉｎｄｅｒに発行され、“Ｐｒｏｃｅｓｓ  ｆｏｒ  ｓｉｚｉｎｇ  ｏｆ  ｃｏｍｐｏｎｅｎｔｓ”（コンポーネントのサイジング・プロセス）と題する米国特許第６，２４９，８９７号は、所与の部品（ｃｏｍｐｏｎｅｎｔｒｙ）、特に電子回路における構成要素のサイジングのためのプロセスを開示しており、特に周辺条件において規定される所定の機能性を実現する。個々の構成要素が有する特性は、本質的に予め決定されており、数式で記述され、これらの構成要素は、所与の部品または電子回路におけるそれらの利用に基づいて相互作用を生成する。数式によって記述される特性および／または相互作用は、コンピュータによって解明され、これによって、要求される構成要素に関する最初に解明した解から得られる結果を、追加の式の解明において用いる。解明、およびこれらの範囲の解明可能性の更なる処置は、所与の電子回路における構成要素のサイジングには実用上の関連がなく、用いられない。
【００１６】
２００３年８月１２日にＲａｉ，ｅｔ  ａｌ．に発行され、“Ｍｅｔｈｏｄ  ｆｏｒ  ｃｏｎｓｔｒｕｃｔｉｎｇ  ｃｏｍｐｏｓｉｔｅ  ｒｅｓｐｏｎｓｅ  ｓｕｒｆａｃｅｓ  ｂｙ  ｃｏｍｂｉｎｉｎｇ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋｓ  ｗｉｔｈ  ｏｔｈｅｒ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｏｒ  ｅｓｔｉｍａｔｉｏｎ  ｔｅｃｈｎｉｑｕｅｓ”（ニューラル・ネットワークを他の補間または推定技法と組み合わせることによって複合応答表面を構築する方法）と題する米国特許第６，６０６，６１２号は、従来の応答表面方法論（ＲＳＭ）およびニューラル・ネットワーク双方の利点を組み込んだ設計最適化方法およびシステムを開示する。この発明は、所与の設計空間のパラメータに基づく区分と呼ばれる方策を採用している。設計手順において、ニューラル・ネットワークおよび多項式はめ込み双方に基づく一連の複合応答表面を用いて、設計空間を横断し、最適解を特定する。複合応答表面は、紛れもなく、ニューラル・ネットワークの力と、低次多項式の経済性（必要なシミュレーション回数、およびネットワーク訓練要件に関して）とを有する。この発明は、多数のパラメータによって設計問題を処理し、設計者に、最終設計に到達する前に、種々のトレードオフの研究を行わせる。
【００１７】
２００３年５月１５日に公開され、“Ｍｅｔｈｏｄ  ｏｆ  ｉｎｔｅｒａｃｔｉｖｅ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｉｎ  ｃｉｒｃｕｉｔ  ｄｅｓｉｇｎ”（回路設計における双方向最適化方法）と題するＭｃＣｏｎａｇｈｙの米国特許出願公開第２００３００９３７６３号は、最適化部を用いて、少なくとも１つの最適化設計候補を双方向処理で決定する方法を開示し、最適化部は、生成アルゴリズムと対象関数とを有し、最適化設計候補は、設計問題定義を満足する。この方法は、生成アルゴリズムに基づいて設計候補を生成することから成る。生成された設計候補は、現在の設計候補集合に追加され、新しい設計候補集合を形成する。好ましい設計候補集合に含ませるために、設計候補を選択することができるように、対象関数に基づいて設計候補を評価する。最適化部の現在の状態を、反復検査のために設計者に提示し、最適化部の現在の状態を更新するために、設計者から入力を受け取る。これらのステップは、停止基準を満たすまで繰り返される。
【００１８】
２００３年４月２４日に公開され、“Ｍｅｔｈｏｄ  ｏｆ  ｍｕｌｔｉ−ｔｏｐｏｌｏｇｙ  ｏｐｔｉｍｉｚａｔｉｏｎ”（多重トポロジ最適化方法）と題するＭｃＣｏｎａｇｈｙ  ｅｔ  ａｌ，の米国特許出願公開第２００３００７９１８８号は、トポロジのサイズを決定しつつトポロジを選択する問題に取り組むためにＡＭＳ回路設計において用いられる多重トポロジ最適化の方法を開示する。最初に、設計構成を、既知のトポロジのデータベースから手作業でまたは自動的に選択する。追加のトポロジも同様に設計することができる。候補設計毎に、トポロジ、およびそのトポロジのための１組のパラメータが付随する。単一のトポロジに対する自動サイジングのステップと同様、多重トポロジ最適化は、設計の母集団全体にわたって最適化することを含むが、全てのトポロジを完全に最適化する必要はない。多重トポロジ最適化ステップは、１つ以上の停止基準を満たすまで繰り返される。次いで、サイズが決定した構成を、配置、ルーティング、抽出、および検証に渡す。
【００１９】
２００４年４月１日に公開され、“Ｍｅｔｈｏｄ  ｆｏｒ  ｏｐｔｉｍｉｚｉｎｇ  ｔｈｅ  ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ  ｏｆ  ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔｓ  ｃｏｍｐｏｎｅｎｔｓ  ｆｒｏｍ  ｃｉｒｃｕｉｔ  ｓｐｅｃｉｆｉｃａｔｉｏｎｓ”（回路仕様から集積回路コンポーネントの特性を最適化する方法）と題するＳａｘｅｎａ，ｅｔ  ａｌ．の米国特許出願公開第２００４００６４２９６号は、デバイスを形成するプロセスを選択する方法を開示し、応答表面方法論モデルを用いて、複数の式を生成することを含む。各式は、それぞれのデバイス・シミュレータ入力パラメータを、デバイスを形成するために用いることができる処理パラメータのそれぞれの組み合わせ、またはデバイス特性のそれぞれの組み合わせに関連付ける。性能係数回路のモデルを形成する。これは、デバイスを組み込もうとする集積回路を表す。複数の式およびデバイス・シミュレータを用いて、処理パラメータの組み合わせまたはデバイス特性の組み合わせの１つを特定し、その結果、性能係数回路に対する１組の性能仕様を満たすデバイスが得られる。
【００２０】
ＭｃＣｏｎａｇｈｙの“Ｔｏｐ−ｄｏｗｎ  ｍｕｌｔｉ−ｏｂｊｅｃｔｉｖｅ  ｄｅｓｉｇｎ  ｍｅｔｈｏｄｏｌｏｇｙ”（トップ−ダウン多目的設計方法論）と題するＰＣＴ出願公開ＷＯ０２／１０３５８１は、回路Ｘをその構成要素｛Ｙｉ｝に分解する階層的サイジング技法を開示する。これらの構成要素Ｙｉの各々について、最適化技法を用いて、実現可能な設計空間（いわゆるパレート・フロント（Ｐａｒｅｔｏ−ｆｒｏｎｔ）の境界において、サンプルを生成する。回路Ｘの合成は、ここでも最適化技法に基づく。この後者の最適化問題では、構成要素Ｙｉに対して生成されたサンプルを候補解として用いる。この技法には重大な欠陥があり、構成要素Ｙに対してサンプルを生成し回路Ｘを合成することが、２つの完全に別個のステップから成るという事実を含む。構成要素Ｙの検索空間において制限された１組の離散サンプルのみを候補解として示唆するので、この方法は、最適に近づく回路Ｘの合成問題に対して解を求めるその能力において厳しく制限される。更に、この技法は、前述の離散サンプルの使用により、効率的な歩留まり推定技法と組み合わせることができない。
【００２１】
以上のことに基づいて、従来技術は一般に最適化手法の有用性を認識してはいるが、特にＡＭＳ回路設計に関して、この手法の使用に伴う問題やしがらみの多くにしかるべく対処し損ねていることは明白である。具体的には、従来技術の設計および最適化方法は、後者に伴う複雑度や個々の設計問題のために、ＡＭＳ設計プロセスにおいて用いるアルゴリズムが比較的限られている。更に、従来技術は、主に、（ｉ）連続最適化変数を直接操作（ａｄｄｒｅｓｓ）できず（連続最適化変数は、離散変数との間で両方向に転換される）、更に（ｉｉ）ネットワーク化したコンピュータ上で統計モデルの構築を並列処理できない。以上の制約が主に原因となって、従来技術の最適化技法には、有用な解に迅速に収束するような十分な「進展」もない。
【００２２】
例えば、ＡＭＳ関連における最適化に適合した柔軟性のなる方法および装置が求められている。このような改良した方法および装置は、ＡＭＳ関連において用いるために特に適合化した強力なアルゴリズムを含み、連続最適化変数や、２つ以上の計算実体に跨る最適化プロセスの少なくとも一部の並列処理を扱うことができれば理想的である。更に、このような改良した方法および装置は、階層的サイズ決定方法と互換性があり、できるだけ効率的かつ容易に設計プロセスを行うように使い易いであろう。
【発明の開示】
【発明が解決しようとする課題】
【００２３】
本発明は、電子回路を設計するために改良した方法および装置を提供することによって、前述の要望に取り組む。
【課題を解決するための手段】
【００２４】
本発明の第１の態様において、電子回路を設計する方法の改良を開示する。この方法は、概略的に、最適化プログラムを定式化し、発展的プロセスを用いて前記問題を最適化して解を生成することから成る。実施形態の一例では、回路はＡＭＳ回路を備えており、問題の定式化は、少なくとも１つの設計目的を定義し、少なくとも１つの制約を定義し、少なくとも１つの制約処理機構を定義することを含む。最適化プロセスは、候補解の少なくとも１つの集合を与え、前記少なくとも１つの集合に対して前記少なくとも１つの目的を評価し、少なくとも部分的に前記評価する行為に基づいて、前記少なくとも１つの集合から少なくとも１つの部分集合を選択することを含む。選択した部分集合（複数の部分集合）に少なくとも部分的に基づいて、統計モデルも構築し、任意に、変異演算子を適用し、「発展的」最適化プロセスを更に促進する。最適化プロセスは、変数の離散および連続エンコード双方を利用できるという利点がある。また、モデル構築または最適化処理タスクをネットワーク上にある数個の異なる処理実体に分散する場合のように、プロセスは、コンピュータ・ネットワークを通じて分散状で利用することもできる。  
【００２５】
本発明の第２の態様において、前述の方法論は、コンピュータ読み取り可能媒体上に格納され、単体またはネットワーク状のコンピュータ・システムのいずれかにおいて実行するように適合化されたコンピュータ・プログラムを用いて実施する。ネットワーク・アーキテクチャは、クライアント／サーバ、ピア・ツー・ピア、または適したトポロジであれば他のいずれでも備えることができる。
【００２６】
本発明の第３の態様では、回路設計プロセスに伴う最適化を実行する方法を開示する。一実施形態では、この方法は、最適化問題を構成し、解集合の初期の１つを含む最適化アルゴリズムを設け、前記アルゴリズムを用いて、少なくとも１つの基準に対して前記最適化問題を評価し、前記基準が満たされない場合、前記基準が満たされるまで、前記解集合を発展させることから成る。最適化問題を構成することは、最適化変数Ｘと、目的Ｙ（Ｘ）と、制約Ｃ（Ｘ）および関数Ｔ（Ｘ）とを指定することを含み、初期の解集合を母集団とすることにより、最適化アルゴリズムを初期化する。少なくとも１つの目的および少なくとも１つの制約に基づいて、初期解集合の各メンバを評価し、１つ以上の変数を変異させ、前述の評価に基づいて解集合を更新することにより、解を「発展させる」。変異は、前述の統計モデルにも適用することができる。
【００２７】
本発明の第４の態様では、前述のプロセス（複数のプロセス）によって設計した改良回路を開示する。一実施形態では、回路は、単一の半導体ダイ上に配された複数の関連コンポーネントを有するアナログ混合信号（ＡＭＳ）回路（即ち、ＳｏＣデバイス）を備えている。デバイスの一例は、シリコン・ゲルマニウム（ＳｉＧｅ）サブミクロン・プロセスを用いて形成する。
【００２８】
本発明の第５の態様では、回路設計プロセスの一部として、新たな候補解を作成する方法を開示する。一実施形態では、この方法は、第１候補ｃを与え、最適化変数ｘｉを特定し、前記最適化変数に対してモデルｍｊを選択し、前記候補ｃのｘｉの選択値を得て、前記モデルに伴う分岐値を得て、前記変数ｘｉを前記分岐値と比較し、前記比較する行為に基づいて、前記モデルｍｉを移行し、前記モデルｍｉのリーフ・セルに伴うデータに基づいて、ｘｉに対して新たな値を生成することから成る。変数（複数の変数）は、トポロジ順序にしたがって特定され、任意に、連続変数としてエンコードする。
【００２９】
本発明の前述のおよびその他の特徴ならびに利点について、添付図面および図と共に読む代表的実施形態の以下の詳細な説明において、以下に説明する。図面においては、同様の参照番号を用いて同様のシステム部分および／または方法ステップの同一物を識別する。
【実施例】
【００３０】
これより、図面を参照するが、同様の番号は全体を通じて同様の部分を示すものとする。
ここで用いる場合、「アナログ−混合回路設計」または「ＡＭＳ設計」とは、電子回路の設計、検査、検証、または評価に関する、手作業または自動化されたあらゆる活動を含むことを意図する。このような設計は、例えば、集積回路を構成するものに関係する場合がある。
【００３１】
ここで用いる場合、「集積回路（ＩＣ）」という用語は、あらゆる集積レベルを有するあらゆる種類のデバイス（限定ではなく、ＵＬＳＩ、ＶＬＳＩ、およびＬＳＩを含む）を示し、プロセスや基本材料（限定ではなく、Ｓｉ、ＳｉＧｅ、ＣＭＯＳおよびＧＡｓを含む）には無関係である。ＩＣは、例えば、メモリ・デバイス（例えば、ＤＲＡＭ、ＳＲＡＭ、ＤＤＲＡＭ、ＥＥＰＲＯＭ／Ｆｌａｓｈ、ＲＯＭ）、ディジタル・プロセッサ、ＳｏＣデバイス、ＦＰＧＡ、ＡＳＩＣ、ＡＤＣ、ＤＡＣ、送受信機、増幅器、共振器、変調器、およびその他のデバイス、ならびにそのあらゆる組み合わせを含むことができる。
【００３２】
ここで用いる場合、「ディジタル・プロセッサ」という用語は、総じて、全ての種類のディジタル処理デバイスを含むことを意図しており、限定ではなく、ディジタル信号プロセッサ（ＤＳＰ）、少数命令セット・コンピュータ（ＲＩＳＣ）、汎用（ＣＩＳＣ）プロセッサ、マイクロプロセッサ、ゲート・アレイ（例えば、ＦＰＧＡ）、特定用途集積回路（ＡＳＩＣ）を含む。このようなディジタル・プロセッサは、１つの一元ＩＣダイに内蔵することができ、または多数のコンポーネントにまたがって分散することができる。
【００３３】
ここで用いる場合、「コンピュータ・プログラム」、「ルーチン」、および「サブルーチン」という用語は、実質的に同義語であり、「コンピュータ・プログラム」は通例、後者の２つの要素の集合即ちグループを記述するために用いられる（がそれだけではない）。このようなプログラムおよびルーチン／サブルーチンは、限定ではなく、Ｃ／Ｃ＋＋、Ｆｏｒｔｒａｎ、ＣＯＢＯＬ、ＰＡＳＣＡＬ、アセンブリ言語、マークアップ言語（例えば、ＨＴＭＬ、ＳＧＭＬ、ＸＭＬ、ＶｏＸＭＬ）等、ならびに共通オブジェクト要求ブローカ・アーキテクチャ（ＣＯＲＢＡ）、Ｊａｖａ（登録商標）（Ｊ２ＭＥ、Ｊａｖａ（登録商標）Ｂｅａｎｓ等を含む）等のようなオブジェクト指向環境を含むいずれの言語でも表すことができる。しかしながら、一般に、前述の用語の全ては、ここでは、所与の目的を遂行するために順次実行されるいずれの一連の論理ステップをも包含することを意図している。
【００３４】
ここで用いる場合、「エンジン」という用語は、限定ではなく、設計特徴化または統計的モデル生成のような、１つ以上の分析、計算、または生成機能を実行するように適合化されたいずれのコンピュータ・プログラム、ファームウェア、および／またはハードウェアにも言及するものとする。
【００３５】
ここで用いる場合、「設計フロー」という用語は、総じて、順次、並行して、および／または繰り返し実行し、１つ以上の設計目標を満たす回路設計を達成するための機能的に区別可能な回路設計活動の集合体に言及することを意図している。
【００３６】
この中に含まれるハードウェア記述言語（ＨＤＬ）またはＶＨＳＩＣ  ＨＤＬ（ＶＨＤＬ）に対して参照する場合はいつでも、限定ではなく、Ｖｅｒｉｌｏｇ（登録商標）、ＶＨＤＬ、Ｓｙｓｍｔｅｓ  Ｃ、Ｊａｖａ（登録商標）、またはその他のあらゆるプログラミング言語に基づく設計の表現というような全てのハードウェア記述言語および関連する言語を含むことも意図している。
【００３７】
ここで用いる場合、「ユーザ・インターフェース」という用語またはＵＩは、一人以上のユーザとシステムとの間の一方向または多方向双方向処理を可能にするように適合化されたあらゆるヒューマン／システム・インターフェースを示すものとする。ユーザ・インターフェースは、限定ではなく、グラフィカルＵＩ、音声またはオーディオＵＩ、有形ＵＩ、および仮想ＵＩ（例えば、仮想現実）をも含む。
【００３８】
（全体像）
本発明は、最適化に基づく手法を用いて、ＡＭＳ回路を含む電子回路を高精度にかつ効率的に設計するための、改良した方法および装置を備えている。具体的には、本発明の実施形態例は、単体で動作可能な（または多重プロセッサ／多重実体環境において）コンピュータ・プログラムから成る。本発明の装置は、前述のコンピュータ・プログラムを実行するように適合化されているコンピュータ・システム、およびこのプログラム（複数のプログラム）を用いて設計したＡＭＳ集積回路を含む。これらのツールは、最低レベルの抽象度（即ち、トランジスタ・レベル）において電子回路を設計するためだけではなく、構築ブロックに関して回路を記述する、それよりも高いレベルの抽象度で電子回路を設計するために適合化されている。
【００３９】
本発明の機能的な目標は２つあり、（ｉ）電子回路の特徴化、および（ｉｉ）個々の性能仕様の集合に向けた回路のサイジングの双方を含む。アナログおよび混合信号回路を設計し特徴化する問題は、最初に設計問題を数学的関数の集合に転換させることによって、系統的に処理する。この関数の集合を１つ以上の最適化エンジンによって解き明かす。
【００４０】
実施形態例では、最適化問題を定式化する際に、少なくとも１つの目的（単一および多重目的最適化の双方）を定義し、任意に、制約を定義すること、および制約処理機構を定義することを含む。この定式化した最適化問題を、次に、「発展的」最適化アルゴリズムに基づいて最適化する。「発展的」最適化アルゴリズムは、（ｉ）候補解（少なくとも１つの解を含む）の集合を示唆すること、（ｉｉ）目的を評価すること、（ｉｉｉ）この候補解の集合から、１つ以上の興味深い部分集合（サブセット）を選択すること、（ｉｖ）部分集合の候補解の評価に基づいて、統計モデルを構築する（徐々に、または繰り返し毎に新たなモデル）こと、および（ｖ）統計モデルからの情報に基づいて新たな候補解の集合を構築することができる。
【００４１】
本発明の更に別の特徴は、利用可能なコンピュータ・ネットワーク上における並列処理による解集合の目的の評価、および利用可能なコンピュータ・ネットワーク上における並列処理における統計モデルの構築を含む。
また、本発明の最適化変数は、従来技術の離散変数に対して、連続変数として符号化することができるという利点がある。
【００４２】
（集積回路設計問題）
回路設計問題は、一般に、設計者が所望の機能性および所与の性能（複数の性能）に対する仕様の集合を処理することから開始する。これらの仕様は、例えば、等号制約、不等号制約、または最適化目標として定式化することができる。加えて、（０．１３ミクロンまたは０．１０ミクロン・プロセスのような）半導体プロセス技術を指定する。
【００４３】
回路設計者は、通例、所与のプロセス技術において望ましい機能性を実施するのに潜在的に適している、利用可能な回路トポロジの集合を有する。複雑なシステムの設計は、例えば、２００４年５月１４日に出願し“Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｄｅｓｉｇｎｉｎｇ  Ｅｌｅｃｔｒｏｎｉｃ  Ｃｉｒｃｕｉｔｓ”（電子回路を設計する方法および装置）と題し、ここで引用したことによりその内容全体が本願にも含まれるものとする、所有者が同一で同時係属中の米国特許出願第１０／８４６，７２７号に記載されているように、階層的に取り組む。例えば、大域的トポロジを最初に多数の構築ブロックに分割する（例えば、増幅器、クロック復元回路、電圧レギュレータ等）。後続の段階において、これらの構築ブロックを更に原始コンポーネント（例えば、トランジスタ、コイル、ダイオード等）に分解する。小さいシステムでは、１回の設計段階で設計問題を解明することができる。図１は、前述のプロセスを図で示す。
【００４４】
原始コンポーネントおよび構築ブロックの挙動について、数式の集合（例えば、ＢＳＩＭ  ｖ４．４トランジスタ・モデル方程式）に関して説明する。設計問題の設計変数は、挙動モデル・パラメータの部分集合であり、設計者によって制御することができる（例えば、デバイスの幅または長さのような、寸法量の一部）。
【００４５】
精度が異なる、異なる種類の評価機構が存在し、設計変数値を回路性能に関連付ける。一次数式が、通例、設計の第１段階において回路設計者によって採用される。しかしながら、数値シミュレーション技法は、利用できる最も精度が高い方法であり、このような精度が要求されるときに用いるとよい。
【００４６】
設計プロセスにおいて、設計者は、通例、性能の値を監視するだけでなく、種々のその他の尺度も監視する。彼／彼女の経験に基づいて、設計者は、最終製品または設計解に更に収束させるために、設計にある制約を適用する。
【００４７】
（最適化手法）
本発明の構成に応じて、２つの別個の種類の解を得ることができる。この以下の論出は、各種類の解について説明し、双方の手法における相違点を強調する。
第１の手法では、ユーザは（とりわけ）１つ以上の回路性能属性に対して制約の集合を強制する。本発明のこの手法を採用して成功すると、これらの性能制約全てを持たす設計変数の集合が得られる。この設定は、優れた性能に対する要求と、実現可能性に対する要求は互いに排他的ではないという仮定に基づいている。設計者がこの動作モードで本発明を用いるのは直感的である。何故なら、個々の回路設計作業を解明することと全体的に対応するからである。
【００４８】
第２の手法では、ユーザは多数の関連性能属性を指定する。次いで、本発明は、候補解の集合を生成する。その各々が、「ある意味では最適」な解を表す（ここでは、「ある」という用語は１つ以上を含む）。これらの解は、実際、競合する性能目標間におけるトレードオフフロント（ｔｒａｄｅ−ｏｆｆ  ｆｒｏｎｔ）上に位置する。更に、第２の設定では、同様に性能尺度に制約を用いることができるが、解の空間全体に追加の品質比較関係を定義して、最適化装置を、制約違反がない検索空間の部分に向けてずらす（ｂｉａｓ）ようにしている。したがって、この手法の下における最適化アルゴリズムの目標は、解のトレードオフフロントを生成することであり、各解は、少なくとも１つの性能尺度については最適である。
【００４９】
更に、上で論じた両手法において、性能尺度と同様に制約を処理することができるが、追加の品質比較関係は、制約違反がない検索空間の１つ以上の部分に向かって最適化装置を「ずらす（ｂｉａｓ）」ために、解空間全体に定義することができるという利点がある。この動作モードにおける本発明の使用が、“Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｄｅｓｉｇｎｉｎｇ  Ｅｌｅｃｔｒｏｎｉｃ  Ｃｉｒｃｕｉｔｓ”（電子回路を設計する方法および装置）と題する、所有者が同一で同時係属中の米国特許出願第１０／８４６，７２７号に例示されている。この内容は、以前に本願にも含まれるものとしており、特徴化エンジンの一部として採用されている。
【００５０】
これより図２から図６を参照して、本発明の種々の態様の実施形態例について詳細に説明する。尚、本発明の装置および方法論を、例えば、マイクロコンピュータまたはマイクロコンピュータ・システム上で実行するコンピュータ・プログラムに関して主に説明するが、本発明の種々の態様は、分散型計算システム、クライアント−サーバ・システム、メインフレーム、スーパーコンピュータ、アレイ・プロセッサ、ハンドヘルド・コンピュータまたは計算器というようなその他の環境、あるいは望ましければ手作業でも実施することもできることは認められよう。
【００５１】
本発明の総合的な設計最適化方法論について、これより図２を参照しながら説明する。具体的には、前述の一般化した回路設計問題（図１）を系統的かつ効率的に解くために、本発明の方法論は、この問題を最適化問題２０２に転換させ、数学的手法またはその他の手法を用いてこれを解く。このプロセスにおいて、得られる結果に対して影響がある２つの重要な選択肢が、ユーザに利用可能である。即ち、（ｉ）最適化目的の数の選択（ステップ２０４）、および（ｉｉ）制約機構（複数の機構）の選択（ステップ２０６）である。尚、図２では１組の連続ステップとして示すが、これらの選択の各々は並列に行うことができ、また分離して行ったり、他方の選択に基づいて交互に行ってもよいことを注記しておく。
【００５２】
（ｉ）最適化目的の数の選択  −  ステップ２０２の下において、回路トポロジに対する全ての関連性能を、データベースのような、情報源から読み出す。加えて、ユーザは、望ましければ、設定中に入力を受け取るのに適合化した、プログラム内にあるルーチンまたはインターフェースを介してというようにして、彼ら自体の（ユーザ定義の）性能尺度を追加することができる。
【００５３】
先に論じたように、本発明は、とりわけ、２つの主な設計目的、即ち、回路設計および回路の特徴化に取り組む。第１の手法では、関連する回路尺度の全てを１つの関数（「費用関数」）に組み込み、次いで単一目的最適化装置によってこれを最小化する。通例、費用関数は最小化されるようになっているので、この実施形態例の説明の残りの部分では、関数の最小化を最適化の基礎として採用することにする。しかしながら、最大化への拡張も同様に最小できることは認められよう。
【００５４】
費用関数では、性能寄与（ｐｅｒｆｏｒｍａｎｃｅ  ｃｏｎｔｒｉｂｕｔｉｏｎ）に関して３つの状況が起こり得る。第１の状況では、性能を最適化する必要がある。費用関数をスケーリング（ｓｃａｌｉｎｇ）し正規化した後、これ（性能メトリック）を費用関数に加算する。第２の状況では、当技術分野では周知の形式の制約を、仕様の形態の下で、性能尺度に強制する。第３の状況では、性能は個々の設計では関連がなく、したがって費用関数には含まれない。
【００５５】
続いて、費用関数に制約を導入する機構について、ここで更に詳細に説明する。式（１）の回路設計変数のベクトル
【数１】
2008507038.tif 000003
式（２）毎の非制約回路性能のベクトル
【数２】
2008507038.tif 000004
ならびにスケーリングおよび正規化関数（ｆｕｎｃｔｉｏｎａｌ）Ｔ（ｚ）を仮定する。単一目標最適化の定式化の一例は、次のようになる。
【数３】
2008507038.tif 000005
ここで、ｙｕ，ｉ（ｘ）は、非制約性能ベクトルのｉ番目の成分である。
【００５６】
特徴化手法では、種々の最適化目標を同時に考慮する（ここでは、「同時に」という用語は、限定ではなく、反復分析プロセスも含む）。問題を解くために、本発明の最適化プログラムは、種々の候補解を示唆するように構成されている。これについては、この中では以下で更に詳しく説明する。この手法は、ユーザがリアルタイムで異なる競合する目的間で動的にトレードオフを探求すること、およびそれに基づいて判断（続いて入力）を行うことを可能にするという利点がある。一般的な多目的最適化の定式化の一例を式（４）に示す。
【数４】
2008507038.tif 000006
【００５７】
本発明の最適化プログラムは、設計問題に対して１つの解を求めるように構成されている。しかしながら、代わりに、設計空間内にある１つ以上のパラメータの変動に基づいて多数の解を求めるように構成することもできる。
【００５８】
（ｉｉ）制約機構の選択  −  応答に対する不等式または等式制約を、最適化問題に異なるやり方で組み入れる（図２ａ）。
非制約最適化の定式化２４０では、各（不）等式制約を制約関数による「ペナルティ（ｐｅｎａｌｔｙ）」尺度で変換する。次いで、この寄与（ｃｏｎｔｒｉｂｕｔｉｏｎ）を変換し（正規化およびスケーリングを遂行するため）、次いで費用関数に加算する。図２ｂは、制約関数の一例を示す。この例では、有効な性能を制限するために、上限２５２および下限２５４が指定されている。有効領域内にある性能にはペナルティがない。この領域の外側にある性能には、差に対して線形に比例するペナルティがある。しかしながら、差または他の計量に基づいた他のペナルティ関係も利用可能である。例えば、一実施形態では、ペナルティ関数は二進である（即ち、限度内ではペナルティがなく、これらの限度の外側ではあらゆるものに対して所定のペナルティがある）。別の実施形態では、枠の外側に適用するペナルティは非線形である（例えば、指数的または対数的）。更に別の実施形態では、第２組の上限／下限を適用し、これらの間隔におけるペナルティは一定値または線形関数から成り、第２組の外側では第３組の上限／下限を適用し、これらの間隔の中では第２の一定値または線形関数を適用する等というように、段階状のペナルティを適用する。更に、ペナルティの適用は、離散的な限度や間隔に基づく必要はなく、代わりに、本質的にファジーやベーズとすることもできる（「離れすぎていない」、「かなり離れている」、「非常に離れている」等）。多数のその他の手法も、当業者には認められよう。
【００５９】
更に、式（５）によって制約付き回路尺度のベクトル、
【数５】
2008507038.tif 000007
そして、制約関数Ｃ（ｚ，ｚｃ）を仮定すると、費用関数の一例は次のようになる。
【数６】
2008507038.tif 000008
【００６０】
尚、前述のペナルティ機構または制約処理技法の例は、性能仕様には制限されないことを注記しておく。この原理の一例として、１つ以上の原始デバイスの動作領域を同様に操作するために、ペナルティを加算することができる。
図２ａの制約付き最適化定式化２４２では、各（不）等式制約は、制約を満たさない場合潜在的な解の集合から候補解を拒絶させる別個の方程式として扱われる。したがって、各不等式制約は解集合に対して「厳しい（ｈａｒｄ）」限度として作用する。
【００６１】
別の構成（図示せず）では、制約は、多目的最適化定式化において別個の目的として扱われる。例えば、このような多目的最適化に対する手法の一例については、既に本願にも含まれるものとしたＫａｌｙａｎｍｏｙ  Ｄｅｂの“Ｍｕｌｔｉ−ｏｂｊｅｃｔｉｖｅ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｕｓｉｎｇ  ｅｖｏｌｕｔｉｏｎａｒｙ  ａｌｇｏｒｉｔｈｍｓ”（発展アルゴリズムを用いた多目的最適化）（１ｓｔ  ｅｄ．，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ  ｓｅｒｉｅｓ  ｉｎ  ｓｙｓｔｅｍｓ  ａｎｄ  ｏｐｔｉｍｉｚａｔｉｏｎ，ＩＳＢＮ  ０−４７１−８７３３９−Ｘ）の第７章を参照のこと。制約の各々が多目的定式化において別個の目的として扱われるか、あるいは制約の組合せを既存の目的の集合に加算する。
【００６２】
また、設計者は、両異体、即ち、制約付きおよび非制約（その副異体（ｓｕｂ−ｖａｒｉａｎｔ）を含む）を順次または組合せ手法のいずれかで実行し、全ての制約を満たす解を求める際に最適化プログラムを加速させることができることも認められよう。
【００６３】
このような手法の１つでは、最適化プログラムは、非制約定式化（図２ａのステップ２４０）から開始して、その結果を制約付き定式化に転換し、全ての制約を満たし続けることを確保する。このような「転換」は、漸進的、反復的（例えば、非制約分析の１つ以上の所定の段階における出力を、制約付き分析の下で評価する場合）とすることができ、あるいは単純に非制約分析の完了時に実行してもよい。別の実施形態例では、非制約および「多目的」制約付き技法の組合せを用いて、解の収束を加速してもよい。他の組合せも同様に可能である。
【００６４】
最適化プログラムの本実施形態は、先に参照したように、スケーリングおよび正規化関数も利用する。これらの関数は、ある種のパラメータ（例えば、図２ｂにおける制約関数の傾き、適用する指数的または段階的関数等）を含み、ユーザには任意にアクセス可能である。しかるべき制約関数を選択することにより、そしてこれらの関数のパラメータを適合化することにより、ユーザは制約の違反を選択的に制御することができるという利点が得られる。しかしながら、これらの関数の選択は、１つ以上の「インテリジェント」選択アルゴリズムにしたがって実行し、それにより実際にプログラムに自動的に最良の（または優れた候補の）関数およびその属性を選択させ、それを行うことから設計者を軽減するようにするとよいことは認められよう。例えば、一実施形態では、アルゴリズムは、設定時または設計プロセス中にユーザによって与えられる他の入力を評価し、これらの値を、他の過去の設計セッションまたは解に伴う値のデータベースと比較し、それに基づいて比肩し得る関数を選択（または示唆）するように適合化される。したがって、比肩し得るＡＭＳ設計に関係する以前の設計セッションが、ある特定の関数の集合または構成を最適または有用であることを見出していた場合、アルゴリズムは、現設計セッションにおいて用いるために、これらの値を示唆または呼び出すことができ、これによって少なくとも現プロジェクトに対する有用な関数の「広場」（ｂａｌｌｐａｒｋ）に設計者を据えるという希望を持つことができる。
【００６５】
あるいは、関数集合を選択し、設計プロセスの少なくとも一部を続いてこの関数集合に基づいて実行し、結果を評価し、以前の反復と比較して、何らかの改良（または劣化）があったか否か判定するというように、設計アルゴリズムの本質を反復的とすることもできる。また、この手法を、前述の「インテリジェント」な先験的手法と組み合わせることにより、最適な関数の収束を一層迅速化させることも可能である。
【００６６】
別の代案として、望ましければ、候補関数選択空間の１つの「コーナー（ｃｏｒｎｅｒ）」において開始し、その空間における別の座標に向かって徐々に移動するというように、選択した関数集合に対する開始点を機械的に決定する、即ち、別のアルゴリズムによって駆動することも可能である。単純な例として、前述の線形ペナルティ関数に、最初の反復には無限の傾きを設定し、後続の反復ではこの傾斜を徐々に減少させてもよく、次いでその効果を評価することができる。別の代案として、所与の傾きを有する線形関数を第１の反復に選択することができ、そのプロセスの結果を、非線形または段階的関数の選択によって得られた結果と比較することもできる。
【００６７】
尚、以上のことから、関数およびそれらに伴うパラメータの「インテリジェント」な選択には、本発明にしたがって、多数の異なる変種も採用可能であり、このような変種の各々は、本開示を前提にすれば、当業者には実施が容易であることは認められよう。
本発明は、「発展的」最適化技法を用いることにより、以上の最適化問題を解明する。具体的には、このアルゴリズムは、最適解に向かって徐々に発展する候補解の集合を示唆する。これより図３を参照して、このプロセスの実施形態例について更に詳細に説明する。
【００６８】
最初に（ステップ３０２）、最適化問題を構成する。この構成は、最適化変数ＸＸ、目的Ｙ（Ｘ）、ならびに制約Ｃ（Ｘ）および制約関数Ｔ（Ｘ）の指定を含むことができる。
次に、選択した最適化アルゴリズムを初期化する（ステップ３０４）。これは、初期解集合Ｓ０を母集団とし、Ｓ０における要素（複数の要素）毎に、Ｙ（ｓ）およびＣ（ｓ）を評価することを含む。初期解集合Ｓ０に等しくオフスプリング集合Ｓ０，ｏｆｆｓｐｒｉｎｇを設定し、インデックス（ｉ）を初期値（例えば、ｉ＝１）に等しく設定する。
【００６９】
次に、ステップ３０６のように、関連する停止判断基準を評価する。停止判断基準の定式化については、例えば、Ｚｉｔｚｌｅｒ，Ｔｈｉｅｌｅ，Ｌａｕｍａｎｎｓ，Ｆｏｎｓｅｃａ，ｄａ  Ｆｏｎｓｅｃａ，“Ｐｅｒｆｏｒｍａｎｃｅ  ａｓｓｅｓｓｍｅｎｔ  ｏｆ  ｍｕｌｔｉ−ｏｂｊｅｃｔｉｖｅ  ｏｐｔｉｍｉｚｅｒｓ：ａｎ  ａｎａｌｙｓｉｓ  ａｎｄ  ｒｅｖｉｅｗ”（多目的最適化器の性能評価：分析および検討）、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｍｐｕｔａｔｉｏｎ，Ｖｏｌ．７，Ｉｓｓｕｅ  ２，ｐｐ．１１７−１３２，Ａｐｒｉｌ  ２００３を参照のこと。その内容は、ここで引用したことにより本願にもその全てが含まれるものとする。しかし、他にも本発明にしたがって用いることができるもの（単体または組み合わせのいずれでも）もあることは認められよう。判断基準を満たさない場合、集合Ｓｉを更新し（ステップ３０８）、候補解を均等に分散したまま保持しつつ、必要であればそのサイズを切除する（ステップ３１０）。Ｓｉから部分集合Ｓｉ，ｐａｒｅｎｔｓを選択し、Ｓｉ，ｐａｒｅｎｔｓに基づいて集合Ｓｉ，ｏｆｆｓｐｒｉｎｇを生成する（ステップ３１４）。次いで、変化演算子（ｍｕｔａｔｉｏｎ  ｏｐｅｒａｔｏｒ）をＳｉ，ｏｆｆｓｐｒｉｎｇに適用する（ステップ３１６）。
【００７０】
Ｓｉ，ｏｆｆｓｐｒｉｎｇにおける要素（複数の要素）毎に、Ｙ（Ｓ）およびＣ（ｓ）を評価し（ステップ３１８）、ステップ３２０のようにインデックスＳｉを増分する（ｉ＝ｉ＋１）。
次に、ステップ３２２のように、Ｓｉ−１およびＳｉ−１，ｏｆｆｓｐｒｉｎｇに基づいて集合Ｓｉを更新し、候補解を均等に分散したまま保持しつつ、必要であればＳｉのサイズを切り詰める。
最後に、ステップ３２４のように、解が得られる。単一目的定式化（ステップ３２６）では、これは集合Ｓｉにおいて最良の解を得ることから成る。多目的定式化（ステップ３２８）では、これはＳｉにおけるパレート・サンプル（ｐａｒｅｔｏ−ｓａｍｐｌｅ）の集合を得ることから成る。
【００７１】
下記の表１は、疑似コードで、このような発展的最適化技法のフローの一例を概略的に示す。
【表１】
2008507038.tif 000009
【００７２】
この発展的挙動を設けるために、最適化プログラム内に種々の特徴や機能性を設ける。例えば、前述の最適化プログラムの一例は、最適化変数を離散または連続符号化方式によって表すことができ、これによって「離散のみの」変数およびその転換に関する従来技術の限界を克服するように構成されている。更に、離散および連続符号化方式の組み合わせも支援するという利点がある。連続的にエンコードされた最適化変数を許容することにより、検索空間の解が前もって制限されないという利点が得られる。尚、一部の変数は広い範囲（数十を超える範囲）を有する可能性があっても、粒度は最低レベルが望ましい場合もあることを注記しておく。連続符号化方式は、周知のアルゴリズム演算子の一部が、これらに対処するように適合化されることを暗示する。例えば、モデル生成の間、最適化変数値を、種々の連続判断値と比較して、どの範囲にこれらが当てはまるか判定する（離散的な対応物では、「０」または「１」値に基づいてモデル構造を分岐するのとは対照的である）。更に、最適化値の新たな値は、確率密度関数をサンプリングすることによって生成され、その特性は、モデル構築フェーズにおける最終ステップとして判定される。
【００７３】
図示の実施形態において得られる連続符号化方式に対する支援は、設計フローにおける異なる段階において必要とされる一部の演算子の実装に影響を及ぼす。これについては、以下で論ずる。
また、所与の母集団における個々の変数の初期化は、多数の異なる方法で実行することができ、例えば、（ｉ）ランダムに（即ち、ランダムまたは疑似ランダム関数に基づいて母集団変数または集合を選択する）、（ｉｉ）ユーザが指定する（即ち、ユーザ入力に基づく。これはユーザの生得的な経験または知識を反映することができる）、または（ｉｉｉ）以前の最適化セッションから（関数の選択に関して先に論じたように、１つ以上のパラメータに基づいた検索ルーチンによる等により、ユーザが特定するか、あるいは最適化プログラムが選択することができる）を含む。
【００７４】
また、母集団における個々の変数毎に目的値を評価する際、様々な方法で求められることも認められよう。例えば、以下を含む。
１）ユーザが提供する１つ以上の数式または数式の集合の適用に基づく。一例として、演算増幅器の周波数挙動を考える。この種の構造では、利得−帯域幅積（ＧＢＷ）は、入力デバイスのトランスコンダクタンス（ｇｍｉｎｐｕｔ）および負荷容量（Ｃｌｏａｄ）の関数として近似的に示される。
【数７】
2008507038.tif 000010
【００７５】
２）自動的に生成した１つ以上の数式または数式の集合の適用に基づく。例えば、中間ステップにおいて、先に引用したことによりその内容全体が本願にも含まれるものとした、所有者が同一で同時係属中の米国特許出願第１０／８４６，７２７号に記載されている方法論を用いてもよい。具体的には、最適化変数を回路性能と関連付ける性能モデルを自動的に生成する。一例として、二次多項式を用いてＧＢＷをモデル化する。
【数８】
2008507038.tif 000011
ここで、０≦βｉｊ＋γｉｊ≦２である。
【００７６】
３）１回以上のシミュレーションの適用に基づく。この開示の日付時点では、種々の市販のおよびフリーウェアのシミュレータが現在入手可能であり、回路の尺度および性能を種々の抽象度で評価することができる。図３ａは、回路性能のシミュレーションに基づく評価に有用な方法論の実施形態例を示す。本発明の一実施形態では、シミュレータ・カプセル化レイヤ、または、「ラッパ」（ｗｒａｐｐｅｒ）が、最適化装置から、個々のシミュレータに特有の詳細を隠しており、ソフトウェア内部で実施される。このレイヤまたはラッパは、とりわけ、プリ・プロセッサおよびポスト・プロセッサ、ならびに集中データベースまたはその他の情報／データ源に対するインターフェースを内蔵する。ソフトウェア技術における当業者によってよく理解されているように、他のインターフェースまたは転換機構を設けてもよい。
【００７７】
４）前述の方法１）〜３）の混合を用いる。「混合」という用語は、ここでは、前述の同時および直列（または反復）適用の双方を含む。
前述の評価方法のいずれを実行するためにでも、種々のツールを用いることができ、限定ではなく、既存のまたはカスタムの数学ソフトウェア・パッケージ（例えば、ＭＳ  Ｅｘｃｅｌ、Ｍａｔｌａｂ、Ｌａｂｖｉｅｗ等）、プログラミング言語（例えば、Ｃ／Ｃ＋＋、Ｆｏｒｔｒａｎ、Ｊａｖａ（登録商標）等）、回路シミュレータ（例えば、ＨＳｐｉｃｅ、Ｅｌｄｏ等）、あるいは究極的には手計算即ち「紙と鉛筆」技法でさえも、含まれる。したがって、本発明は、それの具体化する即ち行うことができるソフトウェア・アプリケーションや言語には捕らわれないという利点がある。
【００７８】
注記しておかなければならないのは、目的関数の評価の間、任意に、個々の設計のレイアウト実施の知識を考慮に入れることができるということである。この知識は、種々の様式で得ることができ、その中には、データベースに格納されている以前の設計から得られるデータ、数式に取り込まれた設計者からの経験、レイアウト寄生抽出（ｌａｙｏｕｔ  ｐａｒａｓｉｔｉｃｓ  ｅｘｔｒａｃｔｉｏｎ）から得られる電気的モデルの評価等がある。
【００７９】
また、図示した最適プログラムの実施形態も、利用可能な処理資産（例えば、アレイ・プロセッサまたはコンピュータ・ネットワーク）全体に、母集団における個々の全ての評価を分散する任意の機構を設ける。これについて、以下に説明する。
【００８０】
また、最適化プログラムの実施形態例は、例えば、いわゆる「トーナメント（ｔｏｕｒｎａｍｅｎｔ）」選択および／または制約付きトーナメント選択等のような、種々の選択機構の実施態様も設ける。この目的のために有用なその他の選択機構を認識し実施することは、当業者には容易であろう。例えば、先に引用して本願にもその内容が含まれるものとした、Ｋａｌｙａｎｍｏｙ  Ｄｅｂによる“Ｍｕｌｔｉ−ｏｂｊｅｃｔｉｖｅ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｕｓｉｎｇ  ｅｖｏｌｕｔｉｏｎａｒｙ  ａｌｇｏｒｉｔｈｍｓ”（発展アルゴリズムを用いた多目的最適化）の第４章（１ｓｔ  ｅｄ．，Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ  ｓｅｒｉｅｓ  ｉｎ  ｓｙｓｔｅｍｓ  ａｎｄ  ｏｐｔｉｍｉｚａｔｉｏｎ，ＩＳＢＮ  ０−４７１−８７３３９−Ｘ）を参照のこと。これらの選択機構を用いて、図３を参照しながら既に論じたように、Ｓｉから集合Ｓｉ，ｐａｒｅｎｔを構築する。同様に、Ｓｉ−１およびＳｉ−１，ｏｆｆｓｐｒｉｎｇからＳｉを構築する。親集合Ｓｉ，ｐａｒｅｎｔからのデータを用いて、最適化変数の分散を推定するモデル｛ｍｉ｝の集合を構築および／または徐々に改良する（具体的には、表１の疑似コード例におけるステップ３．４を参照のこと）。変数の分布を推定するために有用なアルゴリズムは、当業者には周知である。一例として、Ｏｃｅｎａｓｅｋ，Ｊ．，Ｓｃｈｗａｒｚ，Ｊ．の“Ｔｈｅ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｂａｙｅｓｉａｎ  Ｏｐｔｉｍｉｚａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｃｏｍｂｉｎａｔｏｒｉａｌ  ｏｐｔｉｍｉｚａｔｉｏｎ”（ＥＵＲＯＧＥＮ  ２００１  −  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｄｅｓｉｇｎ，Ｏｐｔｉｍｉｚａｔｉｏｎ  ａｎｄ  Ｃｏｎｔｒｏｌ，ＣＩＭＮＥ，Ａｔｈｅｎｓ，Ｇｒｅｅｃｅ，２００１，ｐｐ．１１５−１２０，ＩＳＢＮ  ８４−８９９２５−９７−６における）、および２００２年１月１８日に出願され、“Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｐｔｉｍｉｚｉｎｇ  ａ  Ｓｏｌｕｔｉｏｎ  Ｓｅｔ”（解集合の最適化方法）と題するＭ．ＰｅｌｉｋａｎおよびＤ．Ｇｏｌｄｂｅｒｇの米国特許出願公開第２００３／００５５６１４号を引用しておく。これら双方の内容は、ここで引用したことにより、その全体が本願にも含まれるものとする。
【００８１】
これより、前述の本発明の方法論の適用例について説明する。この特定的な例では、最初に、最適化変数毎に別個のモデルを構築する。これらのモデルの各々は、階層的に、一連の判断基準を格納する。これらの判断基準は、とりわけ、特定の最適化変数に対するポインタを、分岐値のリストと共に含む。分岐値は、モデル構造を考察するときに、どの判断基準を選択すべきか判断するために用いられる。実際の変数値を、判断基準における分岐値のリストに格納されている値によって決定される範囲と比較することにより、どの分岐に従うかを判定する。最後に、モデルのリーフ・セル（ｌｅａｆ  ｃｅｌｌ）は、例えば、古い解集合から得られる情報に基づいた統計的特性を含むが、他の種類の情報がリーフ・セル内に常駐していてもよい。実施形態例では、前述した分散モデルの推定をサンプリングすることにより、新たな候補解Ｓｉ，ｏｆｆｓｐｒｉｎｇが最適化プログラムによって示唆される。このようにして、オフスプリング母集団を構成する。
【００８２】
図４の方法例に示すように、反復構造を用いる。具体的には、ステップ４０２において、新たな候補ｃを特定する。次に、最適化変数ｘｉ毎に、モデルｍｉをその特定の最適化変数のために選択する（ステップ４０４）。次に、ｍｉが選択基準を含む間に、候補ｃのｘｉの選択値を取り出す（ステップ４０６）。次いで、選択したモデルｍｉに対して分岐値｛ｖｂｒａｎｃｈ｝のモデルのリストを取り出し（ステップ４０８）、ｘｉと｛ｖｂｒａｎｃｈ｝との比較に基づいてｍｉを下降し（ステップ４１０）、次の選択基準を取り出す（ステップ４１２）。最後に、ステップ４１４のように、ｍｉの選択したリーフ・セルに格納されている統計データに基づいて、ｘｉの新たな値を生成する。表２は、以上のプロセス例を疑似コードで例示する。
【表２】
2008507038.tif 000012
【００８３】
オフスプリング生成の間、先に生成したｃの変数の値に基づいて、モデル構造を考察する。この特定的な例では、最適化変数に対して、連続符号化方式を考慮する。確率密度関数（例えば、正規分布または正規カーネル分布）をサンプリングすることにより、候補解変数に対して新たな値を生成する。これらの統計的関数のパラメータは、表２に示したモデルから読み出す。
【００８４】
図４ａに示すように、トップ−ダウン式に親母集団から確率モデルを構築する。選択基準を得て（ステップ４５２）、検索空間を区分域に分割するために用いる（ステップ４５６）。ここで、ｘｉは他のパラメータからの相関が希薄されたように見える（ステップ４５４）。このような分割は、許容モデル複雑度（またはその他の制限）に達するまで続き（ステップ４５８）、次いで基礎確立密度関数をあてはめ、得られた各区分域において値の密度を近似する（ステップ４６０）。
【００８５】
モデル構築の間、種々の計量を用いて代替モデル構造を互いに比較することができる。一例として、Ｂａｙｅｓ−Ｄｉｒｉｃｈｌｅｔ計量（先に引用した参考資料を参照のこと）を引用しておく。これらの計量に基づいて、最適化変数の間で相関の希薄が進んでいるモデル候補を、他のモデル候補よりも優先させる。
【００８６】
本発明にしたがって、モデルおよび構造の種々の実施態様を利用することができる。実施形態の一例では、二進判断ツリーを用い、分割値に対して必要な全ての情報を、判断基準のプレースホルダ（ｐｌａｃｅｈｏｌｄｅｒ）として格納する。あるいは、他の実施態様は、１つよりも多い分岐値を用いることを含む。更に別の実施態様は、Ｐ．Ｂｏｓｍａｎ  ｅｔ  ａｌ．による“Ｍｉｘｅｄ  Ｉｄｅａｓ”（Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＵＵ−ＣＳ−２０００−４５，Ｕｎｉｖｅｒｓｉｔｙ  Ｕｔｒｅｃｈｔ，Ｔｈｅ  Ｎｅｔｈｅｒｌａｎｄｓ，ｐｐ．１−７１）において紹介されているように、クラスタリングおよび区分の概念を含む。その内容は、ここで引用したことにより、その全体が本願にも含まれるものとする。このような変形および代替実施態様の全ては、本開示が与えられれば、当業者には実施が容易であり、したがってここではこれ以上説明しない。
【００８７】
また、本発明の実施形態例は、任意に、変異演算子（ｍｕｔａｔｉｏｎ  ｏｐｅｒａｔｏｒ）も与える。これは、母集団多様性を保持し、局所捕獲（ｌｏｃａｌ  ｔｒａｐｐｉｎｇ）を低減するために適用することができる。具体的には、性質という観点からと同様、最適化プログラムの変異演算子は、母集団の特定のメンバの変異または変形を生成し、母集団のメンバが類似し過ぎるのを回避し、したがってそれに伴う欠点または障害が発生し易くなり過ぎるのを回避する。言い方を代えると、このような母集団の多様性は、母集団の少なくとも一部が、最適化問題が実行する発展的選択プロセス（複数のプロセス）を乗り切る可能性、そして最適化プロセスが、設計空間の局在化領域内に取り込まれることのない可能性を高める。一方では適切な変異演算子の選択、他方では演算子を呼び出すモードの間で区別することができる。当業者には、変異演算子の多数の実施態様が認められよう。前述したことは、広い原理の一例に過ぎない。例えば、先に引用して本願にもその内容が含まれるものとした、Ｋａｌｙａｎｍｏｙ  Ｄｅｂによる“Ｍｕｌｔｉ−ｏｂｊｅｃｔｉｖｅ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｕｓｉｎｇ  ｅｖｏｌｕｔｉｏｎａｒｙ  ａｌｇｏｒｉｔｈｍｓ”（発展アルゴリズムを用いた多目的最適化）の第４章を参照のこと。適切な変異演算子の選択は、とりわけ、最適化変数符号化方式に左右される。一例として、連続符号化方式を用いる場合、正規分布を変異演算子として適用することができる。名目値および標準偏差は、近隣の候補解の近接度に基づいて、適応することができる。離散符号化方式の場合、構成可能な確率でビットを反転することもできる。
【００８８】
変異演算子をどのように呼び出すかについて、これらの変異は、いずれの数の異なる方法でも得ることができ、例えば、（ｉ）設計者または最適化装置自体が決定する所与の時間的頻度のように、周期的、（ｉｉ）所与のイベントの発生時（例えば、評価プロセスが失敗した場合、または候補解を拒絶した場合）、（ｉｉｉ）先験的または後験的情報に基づいて、（ｉｖ）「遺伝的多様性」について母集団を周期的に評価し、それに応じて、例えば、好みまたは変異の階層の順序で１つ以上の変異を示唆する別個のルーチンによるというように、母集団または関連するパラメータの分析に基づいて、または（ｖ）ランダム、といった方法が含まれる。本発明の最適化技法に合わせたランダム変異演算子の実施態様例は、ブロック構築的変異（ｂｕｉｌｄｉｎｇ−ｂｌｏｃｋ−ｗｉｓｅ  ｍｕｔａｔｉｏｎ）を含む。例えば、Ｓ．Ｋｕｍａｒａ  の“Ｄｅｓｉｇｎｉｎｇ  Ｃｏｍｐｅｔｅｎｔ  Ｍｕｔａｔｉｏｎ  Ｏｐｅｒａｔｏｒｓ  Ｖｉａ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｍｏｄｅｌ  Ｂｕｉｌｄｉｎｇ  ｏｆ  Ｎｅｉｇｈｂｏｒｈｏｏｄｓ”（近傍の確率モデル構築による競合変異演算子の設計）（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｇｅｎｅｔｉｃ  ａｎｄ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ｃｏｍｐｕｔａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ（ＧＥＣＣＯ），ｐｐ．１１４−１２５，２００４）を参照のこと。その内容は、ここで引用したことにより、その全体が本願にも含まれるものとする。
【００８９】
更に個々の間で多様性を保存するために、任意に、分散した固体を優先する技法を本発明において適用するが、クラスター化が進んだ固体程、生成プロセスにおいて考慮すべき最適化プログラムには、魅力が少なくなる。固体間の近接度は、例えば、ジェノタイプ空間（ｇｅｎｏｔｙｐｅ  ｓｐａｃｅ）、フェノタイプ空間（ｐｈｅｎｏｔｙｐｅ  ｓｐａｃｅ）において、または双方の組み合わせとして計算することができるが、他の近接度の尺度も、望ましければ、用いてもよい。
【００９０】
図４および表２に記載したフローに対して相補的な最適化技法を認識し実施することは、当業者には容易であろう。本発明の実施形態例は、混成（ハイブリッド）最適化フローを含み、記載したフローが、局在的最適化アルゴリズムによって補われている。（下降に基づくアルゴリズム。例えば、先に引用して本願にもその内容が含まれるものとした、Ｍ．Ｋｒａｎｎｉｃｋｉ  ｅｔ  ａｌ．の“ＡＳＦ：Ａ  Ｐｒａｃｔｉｃａｌ  Ｓｉｍｕｌａｔｉｏｎ−Ｂａｓｅｄ  Ｍｅｔｈｏｄｏｌｏｇｙ  ｆｏｒ  ｔｈｅ  Ｓｙｎｔｈｅｓｉｓ  ｏｆ  Ｃｕｓｔｏｍ  Ａｎａｌｏｇ  Ｃｉｒｃｕｉｔｓ”（ＡＳＦ：カスタム・アナログ回路の合成のための実践的なシミュレーションに基づく方法論を参照のこと）。
【００９１】
集積回路（ＩＣ）デバイス
ここに記載する実施形態例のＩＣデバイスの基準としては、いずれの数の異なるデバイス構成でも用いることができ、例えば、プロセッサ・コア７０２、メモリ７０４、およびインターフェース７０６というような種々の構成要素を有する、ＡＭＳ構成要素（図５参照）を有するシステム・オン・チップ（ＳｏＣ）デバイスを含む。このようなデバイスは、前述の設計方法論の出力を用いて製作される。出力は、論理レベル表現に合成され、半導体技術において周知のコンパイル、レイアウトおよび製作技法を用いて、物理的デバイスに還元される。例えば、本発明は、０．３５、０．１８、０．１３、および０．１ミクロン・プロセスと互換性があり、究極的には、更に小さいまたはその他の分解能のプロセスにも適用することができる。デバイスの製作のためのプロセス例は、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎ（インターナショナル・ビジネス・マシン社）によって提供された０．０９ミクロンＣｕ−０８または０．１３ミクロンＣｕ−１１「ブルー・ロジック」プロセスであるが、他のものも用いることができる。
【００９２】
尚、本発明のＩＣデバイスは、限定ではなく、シリアル通信デバイス、パラレル・ポート、タイマ、カウンタ、高電流ドライバ、アナログ／ディジタル（Ａ／Ｄ）変換器、ディジタル／アナログ（Ｄ／Ａ）変換器、割り込みプロセッサ、ＬＣＤドライバ、メモリ、発振器、ＰＬＬ増幅器、およびその他の同様のデバイスというような通常に入手可能な周辺機器または構成要素のいずれでも内蔵できることは、当業者には認められよう。更に、プロセッサは、この中で既に参照したように単一パッケージ内に多数の異なる機能性を設けるために有用なシステム・オン・チップ（ＳｏＣ）デバイスを形成するためというように、他のカスタムまたは特定用と回路も含むことができる。本発明は、構成要素や周辺機器および本方法および装置を用いて組み合わせることができるその他の回路の形式、数、または複雑性には限定されることはない。むしろ、時と共に改良する、現存する半導体プロセスの物理的容量によって、いずれの制限も主に強いられている。したがって、本発明を採用することにより、半導体プロセスが改良するに連れて、可能な複雑度や集積度は一層向上することが予期される。
【００９３】
コンピュータ・システム
これより図６を参照して、図２から図４ａに関して先に説明した方法を実行し、とりわけ、図５の集積回路を合成することができる計算装置の一実施形態について説明する。計算デバイス６００は、一般に、中央演算装置（ＣＰＵ）６０２、ランダム・アクセス・メモリ（ＲＡＭ）６０４、およびメモリ・コントローラ６０５を有するマザーボード６０１を備えている。記憶デバイス６０６（ハード・ディスク・ドライブまたはＣＤ−ＲＯＭ）、入力デバイス６０７（キーボード、マウス、および／またはコンピュータ上で実行するソフトウェアの形態の音声認識ユニット）、および表示デバイス６０８（ＣＲＴ、プラズマ、ＬＣＤ、またはＴＦＴディスプレイのような）、ならびにホストおよび周辺構成要素の動作を支援するために必要なバスも設けられている。先に述べた本発明のアルゴリズムは、コンピュータ技術の当業者には周知のように、設計サイジングおよび合成の間ＣＰＵ６０２が用いるために、コンピュータ・プログラムの形態でＲＡＭ６０４および／または記憶デバイス６０６に格納されている。ユーザ（図示せず）は、設計仕様、モデル記述等をシステム動作の間に入力デバイス６０７（またはその他のソフトウェア・プロセス）を通じて、コンピュータ・プログラムのＧＵＩまたはその他の入力構造に入力する。プログラムによって生成された設計は、後に読み出すために記憶デバイス６０６に記憶され、グラフィック表示デバイス６０８上に表示され、および／または、望ましければ、プリンタ、データ記憶ユニット、その他の周辺構成要素にシリアルまたはパラレル・ポート６１２（例えば、ＵＳＢ、ＲＳ−２３２、ＩＥＥＥ−１３９４等）を通じて出力される。
【００９４】
更に、本発明の方法を具体化するコンピュータ・ソフトウェアは、同質であれ異質であれ、データの記憶および／または読み出し、並列処理、あるいは分散処理を含む種々の機能のために、他のコンピュータ・プログラムと共同またはインターフェースすることもできることは認められよう。本装置の一実施形態では、複数の個々の処理デバイスに跨って、または利用可能なコンピュータのネットワークに跨ってモデル構築を分散する機構が実施される。例えば、分散処理環境は、コンピュータ技術においてユビキタス型の複数の単体マイクロコンピュータまたはミニコンピュータが互いに（そして各マシン上で実行するソフトウェアと）データ通信を行って、多数のデバイスに跨ってモデル生成タスクを分散することにより、プロセスを同様に利用するというような場合に用いることができる。このような環境では、最適化プログラムは、ソフトウェア技術においては一般的に周知の形式の「サーバ」モジュールおよび１つ以上の分散「クライアント・モジュール」を用いて前述の分散処理（図７参照）を実行するというような、分散アプリケーション（ＤＡ）を備えることができる。
【００９５】
このような分散処理は、（ｉ）専用（即ち、１つ以上の分散プロセッサがサーバ専用となっている場合）、（ｉｉ）多重化（異なるサーバまたはその他の実体からの複数の異なるタスクを、多重化スケジュールまたはラウンド・ロビン、ＴＤＭＡ等のような方式にしたがって実行するような場合）、（ｉｉｉ）マルチ・タスク（即ち、当該処理エンティティ内において処理中の他のタスクと並列に実行する）、または（ｉｖ）「利用状況次第」とすることができる。この目的のために有用なその他のコンピュータ・アーキテクチャおよびアクセス／分散方式を認識し実施することは、コンピュータ技術における当業者には容易であろう。
【００９６】
あるいは、別の実施形態では、プログラムは、処理アレイにおいて互いに論理的に通信する複数の個別処理エレメント（ディスクリート・マイクロプロセッサ、ＲＩＳＣプロセッサまたはＤＳＰのような）を利用する。このような「アレイ」プロセッサの市販されている例の１つに、Ｍｏｔｏｒｏｌａ  ＭＲＣ６０１１再構成可能コンピュータ・ファブリック（ＲＣＦ：Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｃｏｍｐｕｔｅ  Ｆａｂｒｉｃ）がある。ＭＲＣ６０１１は、多重コア・プロセッサ・アレイの処理最中における再構成を可能とし、モデル生成または分析のような計算集約的な用途や、処理要求が時間またはその他の変数の関数として著しく変動する可能性がある場合において非常に有用である。
【００９７】
本発明のアーキテクチャの別の例では、最適化プログラムは、実際には、ピア・ツー・ピア（Ｐ２Ｐ）環境における無サーバ・クライアント即ちピア・コンポーネントであり、データ取得、分析、他の処理ノードまたは実体への通知、およびその他の支援機能（メッセージ生成や送信の催促または警告のような）を実行する。Ｐ２Ｐネットワークの実施および環境は、当技術分野では周知である。Ｐ２Ｐアーキテクチャの一例および付随するコンポーネントについては、とりわけ、２００１年４月１７日にＧｒａｙ，ｅｔ  ａｌ．に発行され、“Ｍｅｔｈｏｄ  ａｎｄ  ａｐｐａｒａｔｕｓ  ｆｏｒ  ｐｅｅｒ−ｔｏ−ｐｅｅｒ  ｃｏｍｍｕｎｉｃａｔｉｏｎ”（ピア・ツー・ピア通信方法および装置）と題する米国特許第６，２１９，７１０号、２００年１２月２６日にＪｉａｎｇに発行され、“Ｍｅｔｈｏｄ  ｆｏｒ  ｃｒｅａｔｉｎｇ  ｐｅｅｒ−ｔｏ−ｐｅｅｒ  ｃｏｎｎｅｃｔｉｏｎｓ  ｏｖｅｒ  ａｎ  ｉｎｔｅｒｃｏｎｎｅｃｔｅｄ  ｎｅｔｗｏｒｋ  ｔｏ  ｆａｃｉｌｉｔａｔｅ  ｃｏｎｆｅｒｅｎｃｉｎｇ  ａｍｏｎｇ  ｕｓｅｒｓ”（ユーザ間における会議をし易くするために相互接続ネットワークを通じてピア・ツー・ピア接続を作成する方法）と題する米国特許第６，１６７，４３２号、２００２年１０月３１日に公開され、“Ｄｉｓｔｒｉｂｕｔｅｄ  ｓｔｏｒａｇｅ  ｏｎ  ａ  Ｐ２Ｐ  ｎｅｔｗｏｒｋ  ａｒｃｈｉｔｅｃｔｕｒｅ”（Ｐ２Ｐネットワーク・アーキテクチャ上における分散記憶）と題するＳｈｔｅｙｎの米国特許出願第２００２０１６２１０９Ａ１号、２００２年１０月１７日に公開され、“Ｒｅｌｉａｂｌｅ  ｐｅｅｒ−ｔｏ−ｐｅｅｒ  ｃｏｎｎｅｃｔｉｏｎｓ”（信頼性の高いピア・ツー・ピア接続）と題するＴｒａｖｅｒｓａｔ，ｅｔ  ａｌ．の米国特許出願第２００２０１５２２９９Ａ１号、および２００２年１０月１０日に公開され、“Ｐｅｅｒ−ｔｏ−ｐｅｅｒ  ｃｏｍｐｕｔｉｎｇ  ａｒｃｈｉｔｅｃｔｕｒｅ”（ピア・ツー・ピア計算アーキテクチャ）と題するＴａｖｅｒｓａｔ，ｅｔ  ａｌ．の米国特許出願第２００２０１４７７７１Ａ１号に詳細に記載されており、これらの各々は、ここで引用したことにより、その内容全体が本願にも含まれるものとする。Ｐ２Ｐ最適化装置の応用は、例えば、ＩＥＴＦによって標準化されている、Ｂｌｏｃｋｓ  Ｅｘｔｅｎｓｉｂｌｅ  Ｅｘｃｈａｎｇｅ  Ｐｒｏｔｏｃｏｌ（ＢＥＥＰまたはＢＸＸＰ）フレームワークを用いて行うことができ、ピア・ツー・ピア応用の構築を迅速に行うことを可能にする。同様に、メッセージング能力も、いずれの数の異なる環境を用いても実施することができ、ＩＭＸＰ（インスタント・メッセージング交換プロトコル）フレームワーク、前述のＢＥＥＰフレームワークを用いて実施するピア・ツー・ピア応用メッセージング・プラットフォームが含まれる。
【００９８】
本発明のある態様について、具体的な設計例に関して説明したが、これらの説明は本発明のより広い方法を例示するに過ぎず、個々の設計によって必要に応じて修正してもよいことは認められよう。あるステップは、ある状況下では、不必要としたり、選択肢としてもよい。加えて、開示した実施形態にあるステップまたは機能性を追加することができ、２つ以上のステップの実行順序を変えることもできる。このような変形は全て、ここに開示し特許請求する発明の範囲内に含まれるものと見なす。
【００９９】
前述の詳細な説明は、種々の実施形態に適用した本発明の新規な特徴を示し、記載し、指摘したが、図示したデバイスまたはプロセスの形態および詳細における省略、交換、および変更も、本発明から逸脱することなく、当業者によって可能であることは言うまでもない。前述の説明は、現時点において考えられる、本発明を実行する最良の態様である。この説明は、限定の意図は全くなく、逆に本発明の全体的な原理を例示すると見なしてしかるべきである。本発明の範囲は、特許請求の範囲を参照して決定すべきである。
【図面の簡単な説明】
【０１００】
【図１】典型的な従来技術のＡＭＳ回路設計フローを示す論理フロー・チャート。
【図２】本発明による最適化プロセスの一例の目的および制約定義部分の概略的なフローを示す論理フロー・チャート。
【図２ａ】図２の方法論にしたがって制約機構を指定する方法の一実施形態を示す論理フロー・チャート。
【図２ｂ】制約付き最適化問題を無制約最適化問題に転換するために用いられる制約変換機能の一例を示すグラフ。
【図３】本発明による最適化プロセスの実施形態の一例の論理フロー図。
【図３ａ】回路シミュレーションに基づいて回路性能を計算する際に用いられる評価機構の一例を示す図。
【図４】本発明にしたがって候補解（連続変数）を作成する方法の実施形態の一例の論理フロー図。
【図４ａ】本発明にしたがって親母集団から確率モデルを構築する方法の実施形態の一例の論理フロー図。
【図５】本発明の方法にしたがって製造した集積回路デバイスの一例の上平面図。
【図６】本発明の最適化コンピュータ・プログラムの「単体（スタンドアローン）」異体を実行するように適合化したコンピュータ・システムの一例の機能ブロック図。
【図７】本発明の最適化コンピュータ・プログラムの分散アプリケーション（ＤＡ）異体を実行するように適合化したコンピュータ・システムの一例の機能ブロック図。
【図１】
2008507038.tif 000013
【図２】
2008507038.tif 000014
【図２ａ】
2008507038.tif 000015
【図２ｂ】
2008507038.tif 000016
【図３−１】
2008507038.tif 000017
【図３−２】
2008507038.tif 000018
【図３ａ】
2008507038.tif 000019
【図４】
2008507038.tif 000020
【図４ａ】
2008507038.tif 000021
【図５】
2008507038.tif 000022
【図６】
2008507038.tif 000023
【図７】
2008507038.tif 000024
【手続補正書】
【提出日】平成19年3月9日(2007.3.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＡＭＳ回路の設計を生成する方法であって、
最適化プログラムを定式化することから成り、前記定式化の行為（ａｃｔ）は、
少なくとも１つの設計目的を定義し、
少なくとも１つの制約を定義し、
少なくとも１つの制約処理機構を定義し、
少なくとも部分的に発展的最適化方法論に基づいて、前記最適化問題を最適化することから成り、前記方法論は、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的および／または制約に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの部分集合を選択し、
前記少なくとも１つの部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成り、
前記方法は、更に、少なくとも１つの相関分析を利用して、前記最適化方法論に伴う２つ以上の設計変数間における１つ以上の相関の存在を評価する、方法。
【請求項２】
請求項１記載の方法であって、更に、少なくとも部分的に前記部分集合に基づいて、少なくとも１つの統計モデルを構築することを含む、方法。
【請求項３】
請求項２記載の方法であって、更に、少なくとも部分的に前記統計モデルからの情報に基づいて、候補解の新たな集合を構築することを含む、方法。
【請求項４】
請求項１記載の方法であって、更に、コンピュータ・ネットワークに結合されている複数の処理実体を用いて、前記少なくとも１つの目的を評価することを含む、方法。
【請求項５】
請求項２記載の方法であって、更に、コンピュータ・ネットワークに結合されている複数の処理実体を用いて、前記統計モデルを構築することを含む、方法。
【請求項６】
請求項１記載の方法であって、更に、前記最適化する行為に伴う複数の変数の少なくとも一部を、連続変数としてエンコードすることを含む、方法。
【請求項７】
請求項１記載の方法であって、更に、前記最適化する行為に伴う複数の変数の第１部分を連続変数としてエンコードし、前記複数の第２部分を実質的に離散変数としてエンコードすることを含む、方法。
【請求項８】
請求項１記載の方法であって、更に、前記最適化する行為の少なくとも一部の間に、少なくとも１つの変異演算子を適用することを含む、方法。
【請求項９】
請求項１記載の方法において、前記最適化する行為は、更に、候補解のより分散されている集合を選択的に、適正な収束を遂行するための中間または最終ステップとして優先的に用いることを含む、方法。
【請求項１０】
設計プロセスを用いて電子回路を設計する方法であって、
最適化問題を定式化し、前記最適化問題が、前記電子回路に関連し、少なくとも１つの設計目的を定義する複数の設計変数を備えており、
コンピュータ化したシステムを用い、発展的プロセスを用いて前記問題に対する最適解を生成し、
前記解を用いて、前記回路に付随するハードウェアまたはロジックの少なくとも一部を実装することから成り、
前記方法は、更に、前記設計変数の２つ以上の間で、１つ以上の相関希薄を特定する、方法。
【請求項１１】
請求項１０記載の方法において、前記定式化する行為は、少なくとも１つの設計目的を定義することを含む、方法。
【請求項１２】
請求項１１記載の方法において、前記定式化する行為は、更に、
少なくとも１つの制約を定義し、
少なくとも１つの制約処理機構を定義する、
ことを含む、方法。
【請求項１３】
請求項１１記載の方法において、前記最適化する行為は、
候補解の少なくとも１つの集合を与え、
前記少なくとも１つの集合に対して、前記少なくとも１つの目的を評価し、
少なくとも部分的に前記評価する行為に基づいて、前記少なくとも１つの集合から、少なくとも１つの部分集合を選択する、
ことを含む、方法。
【請求項１４】
請求項１３記載の方法において、前記最適化する行為は、更に、少なくとも部分的に前記少なくとも１つの選択した部分集合に基づいて、少なくとも１つのモデルを構築することを含む、方法。
【請求項１５】
請求項１４記載の方法において、前記最適化する行為は、更に、少なくとも部分的に前記少なくとも１つのモデルに基づいて、候補解の少なくとも１つの新たな集合を構築することを含む、方法。
【請求項１６】
請求項１４記載の方法において、少なくとも１つのモデルを構築する前記行為は、少なくとも１つの統計モデルを構築することを含む、方法。
【請求項１７】
請求項１５記載の方法において、少なくとも１つのモデルを構築する前記行為は、設計プロセスの間に前記モデルを徐々に構築することを含む、方法。
【請求項１８】
請求項１０記載の方法において、前記電子回路はＡＭＳ回路を備えている、方法。
【請求項１９】
請求項１８記載の方法において、前記最適化する行為は、少なくとも部分的に、データ通信している複数のコンピュータを有するコンピュータ・ネットワーク上で実行する、方法。
【請求項２０】
請求項１３記載の方法において、前記評価する行為は、少なくとも部分的に、データ通信している複数のコンピュータを有するコンピュータ・ネットワーク上で実行する、方法。
【請求項２１】
請求項１４記載の方法において、前記構築する行為は、少なくとも部分的に、データ通信している複数のコンピュータを有するコンピュータ・ネットワーク上で実行する、方法。
【請求項２２】
請求項１０記載の方法において、前記最適化する行為は、連続最適化変数をエンコードすることを含む、方法。
【請求項２３】
請求項２２記載の方法において、前記最適化する行為は、更に、前記連続変数と共に、離散最適化変数をエンコードすることを含む、方法。
【請求項２４】
請求項１０記載の方法であって、更に、前記最適化する行為の少なくとも一部において、少なくとも１つの変異演算子を提供することを含む、方法。
【請求項２５】
請求項１０記載の方法において、前記最適化する行為は、更に、候補解のより分散されている集合を選択的に、適正な収束を遂行するための中間または最終ステップとして優先的に用いることを含む、方法。
【請求項２６】
複数のデータを格納するように適合化したコンピュータ読み取り可能媒体であって、前記複数のデータは少なくとも１つのコンピュータ・プログラムを含み、前記少なくとも１つのプログラムは、少なくとも、
最適化問題を定式化し、
少なくとも部分的に発展的最適化方法論に基づいて、前記最適化問題を最適化する、ことによって、電子回路の設計を生成するように適合されており、
前記定式化は、少なくとも１つの設計目的を定義し、
前記方法論は、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的および／または制約に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの部分集合を選択し、
前記少なくとも１つの部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成り、
前記少なくとも１つのプログラムは、更に、前記最適化問題に伴う２つ以上の設計変数の間において１つ以上の相関希薄を特定するように適合化されている、コンピュータ読み取り可能媒体。
【請求項２７】
請求項２６記載のコンピュータ読み取り可能媒体において、前記媒体は、コンピュータ・システムのハード・ディスク・ドライブ（ＨＤＤ）を備えている、コンピュータ読み取り可能媒体。
【請求項２８】
請求項２６記載のコンピュータ読み取り可能媒体において、前記少なくとも１つのプログラムは、コンピュータ・ネットワークの多数の処理実体に跨って分散されている他のプログラムと通信するように適合化されている、コンピュータ読み取り可能媒体。
【請求項２９】
請求項２８記載のコンピュータ読み取り可能媒体において、前記少なくとも１つのプログラムは、少なくとも１つのクライアント部を有する分散アプリケーションのサーバ部を備えている、コンピュータ読み取り可能媒体。
【請求項３０】
請求項２８記載のコンピュータ読み取り可能媒体において、前記ネットワークは、ピア・ツー・ピア・ネットワークを備えている、コンピュータ読み取り可能媒体。
【請求項３１】
電子回路の設計に有用なコンピュータ・システムであって、
プロセッサと、
前記プロセッサとデータ通信するデータ記憶デバイスと、
少なくとも部分的に前記記憶デバイス内に常駐するコンピュータ・プログラムであって、少なくとも、
最適化問題を定式化し、
少なくとも部分的に発展的最適化方法論に基づいて、前記最適化問題を最適化する、ことによって電子回路の設計を生成するように適合化されており、
前記定式化は少なくとも１つの設計目的を定義し、
前記方法論は、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的および／または制約に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの部分集合を選択し、
前記少なくとも１つの部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成る、コンピュータ・システム。
【請求項３２】
請求項３１記載のコンピュータ・システムにおいて、前記１つのプログラムは、前記最適化する行為の少なくとも一部を実行するために、コンピュータ・ネットワークの多数の処理実体にまたがって分散されている他のプログラムと通信するように適合化されている、コンピュータ・システム。
【請求項３３】
請求項３１記載のコンピュータ・システムにおいて、前記１つのプログラムは、少なくとも部分的に前記部分集合に基づいて、少なくとも１つの統計モデルを構築するように適合化されており、前記構築する行為は、コンピュータ・ネットワークの多数の処理実体にまたがって分散されている他のプログラムと通信することを含む、コンピュータ・システム。
【請求項３４】
回路設計プロセスに伴う最適化を実行する方法であって、
最適化問題を構成し、
解集合の初期の１つを含む最適化アルゴリズムを設け、
前記アルゴリズムを用いて、少なくとも１つの基準に対して前記最適化問題を評価し、
前記基準が満たされない場合、前記基準が満たされるまで、前記解集合を発展させる、
ことから成る方法。
【請求項３５】
請求項３４記載の方法において、前記構成する行為は、最適化変数Ｘと、目的Ｙ（Ｘ）と、制約Ｃ（Ｘ）および関数Ｔ（Ｘ）とを指定することを含む、方法。
【請求項３６】
請求項３４記載の方法であって、更に、前記解集合の前記初期の１つを母集団とすることにより、前記最適化アルゴリズムを初期化することを含み、
前記評価する行為は、前記初期解集合のメンバ毎に、少なくとも１つの目的および少なくとも１つの制約を評価することを含む、方法。
【請求項３７】
請求項３６記載の方法において、前記発展させる行為は、少なくとも部分的に前記評価する行為に基づいて、前記初期解集合を更新することを含む、方法。
【請求項３８】
請求項３４記載の方法において、前記発展させる行為は、少なくとも１つの変異演算子を、前記解集合の少なくとも一部に適用することを含む、方法。
【請求項３９】
請求項３４記載の方法において、前記少なくとも１つの基準は、前記解集合の発展する反復において、最良の解を得ることを含む、方法。
【請求項４０】
請求項３４記載の方法において、前記回路は、ＡＭＳ回路を備えており、前記プロセスは、更に、前記最適化問題に伴う複数の変数の少なくとも一部を、連続変数としてエンコードすることを含む、方法。
【請求項４１】
回路であって、
最適化問題を定式化し、
少なくとも部分的に発展的最適化方法論に基づいて、前記最適化問題を最適化する、ことから成るプロセスによって設計され、
前記定式化は少なくとも１つの設計目的を定義し、
少なくとも１つの制約を定義し、
少なくとも１つの制約処理機構を定義し、
前記方法論が、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的および／または制約に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの部分集合を選択し、
前記少なくとも１つの部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成り、
前記最適化は、更に、前記最適化方法論に伴う２つ以上の設計変数間における１つ以上の相関の存在を評価する、回路。
【請求項４２】
請求項４１記載の回路において、前記回路はＡＭＳ回路を備えており、前記プロセスは、更に、前記最適化問題に伴う複数の変数の少なくとも一部を、連続変数としてエンコードすることを含む、回路。
【請求項４３】
回路設計プロセスにおいて、新たな候補解を作成する方法であって、
第１候補ｃを与え、
最適化変数ｘｉを特定し、
前記最適化変数に対してモデルｍｉを選択し、
前記候補ｃのｘｉの選択値を得て、
前記モデルに伴う分岐値を得て、
前記変数ｘｉを前記分岐値と比較し、
前記比較する行為に基づいて、前記モデルｍｉを下降し、
前記モデルｍｉのリーフ・セルに伴うデータに基づいて、ｘｉに対して新たな値を生成する、
ことから成る、方法。
【請求項４４】
請求項４６記載の方法において、前記特定する行為は、トポロジ順序にしたがって、少なくとも１つの変数を特定することを含み、
前記最適化変数を連続変数としてエンコードする、方法。
【請求項４５】
請求項４３記載の方法において、前記回路はＡＭＳ回路を備えている、方法。
【請求項４６】
ＡＭＳ回路を設計する方法であって、
連続変数としてエンコードした少なくとも１つの変数を用いて、少なくとも１つの最適化問題を定義し、
少なくとも１つの制約機構を定義し、前記少なくとも１つの機構を、（ｉ）候補解の制約に基づく評価、および（ｉｉ）非制約目的関数評価から成る群から選択し、
前記定義する行為に少なくとも部分的に基づいて、発展的最適化プロセスを実行し、該最適化プロセスが、前記発展を促進するために、少なくとも１つの変異演算子を適用することを含む、
設計プロセスを実行することを含む、方法。
【請求項４７】
複数のデータを格納するように適合化したコンピュータ読み取り可能媒体であって、前記複数のデータは少なくとも１つのコンピュータ・プログラムを含み、前記少なくとも１つのプログラムは、少なくとも、
最適化プログラムを定式化し、前記定式化が少なくとも１つの設計目的を定義することを含み、
少なくとも部分的に発展的最適化方法論に基づいて、前記最適化問題を最適化することによって、電子回路の設計を生成するように適合化されており、前記方法論は、
候補解の集合を与え、
少なくとも部分的に前記少なくとも１つの目的に基づいて、前記解の少なくとも一部を評価し、
前記集合から少なくとも１つの候補解の部分集合を選択し、
前記少なくとも１つの候補解の部分集合の少なくとも一部を利用して、前記回路の前記設計を生成することから成り、
前記少なくとも１つのプログラムは、更に、最適化空間において設計変数間に存在する相関に関する情報を備えている統計モデルを生成し、前記モデルを、前記与え選択する行為の少なくとも１つの一部として用いるように適合化されている、コンピュータ読み取り可能媒体。
【国際調査報告】
2008507038.tif 000025