電子回路およびNポートシステムのシミュレーション方法
この発明の或る実施例に従うと、シミュレーションを実行するためのシステムおよび方法が提供される(400)。システム内の並列性を用いて、この方法は、大きな問題を複数の小さい区画へと分解する(404)。一連の反復が実行され、(410)、上記各区画間で交換される波形が収束するまで(412)これを行なう。強結合された区画の近似プレビュー解が導入され(408)、収束に必要な反復の数を減少させる。これら近似プレビュー解は、シミュレーションが行なわれる前に導入される。波形が一旦収束すれば、シミュレーションは解を決定している。
【発明の詳細な説明】
【技術分野】
【0001】
関連出願
本願は、2003年5月22日出願の、「電子回路および物理的nポートシステムの高速・正確なシミュレーション方法(Method for fast, accurate simulation of electronics circuits and physical n-port system)」と題された、米国特許仮出願連続番号第60/473,047号の優先権を主張する。
発明の分野
この発明は、一般的にシミュレーションに関し、特定的には、大型の複雑系についての正確な波形レベルコンピュータシミュレーションに関する。
【背景技術】
【0002】
背景
コンピュータシステムを用いてシミュレーションを実行することによって、設計者または開発者が或る設計を製造前にテストできるようにする場合がある。たとえば、設計者はコンピュータアプリケーションを用いて複雑な回路を構築する場合がある。次に、このアプリケーションは、或る入力があった場合にいくつかの時点で回路の出力をシミュレートすることができる。シミュレーションを用いて設計者は容易にいくつかの回路の原型を作り出し、それを実際に構築することなしにテストすることができる。
【0003】
シミュレーションは、しばしば大きな計算リソースを必要とする。このリソースを低価格で提供する1つの方策として、並列動作する複数の機械からなるクラスターを用いるというものがある。たとえば、複数のコンピュータシステムを合せてネットワーク化することによって、単一の問題についての解に対して集団で作業を行なうことができる。このシミュレーションを並列実行する1つの問題は、機械同士の間で作業を分割し連携させることである。
【0004】
回路シミュレーションは、しばしばSPICE(Simulation Program With Integrated
Circuit Emphasis)シミュレータまたはそこから派生したものを用いて実行される。これらシミュレータは、「ダイレクトスパース(Direct Sparse)」解求方法として知られる数値積分を用いる。回路が大型化し信号完全性効果がより重要となるのに伴い、これらシミュレーションを実行するのにかかる時間が極端に長くなっている。これらシミュレーションでは、典型的には、回路の過渡挙動が伴い、初期値問題(Initial Value Problem)を解くことが必要である。
【0005】
図1は、初期値問題を用いてシミュレーションに対する解を決定するためのプロセスを例示するフローチャートである。プロセス100は、ダイレクトスパース法を用いて大規模なシミュレーションの所与の部分についての解を決定するために用いることができる。たとえば、回路シミュレーションを複数のブロックに分割し、その各々を微分代数方程式(differential algebraic equations:DAE)によって表わせるようにすることができる。一実施例に従うと、DAEは、変形ノード分析(modified nodal analysis:MNA)を用いて得られる。次に、これら式を簡略化して解くことによって当該シミュレーションについての解に達することができる。
【0006】
【数1】
【0007】
これらは非線形代数方程式である。
【0008】
非線形の式は解くのが困難で計算コストがかかるため、ブロック108にて、ニュートン・ラフソン(NR)反復を実行して線形代数方程式を得る。NR反復は以下の形である。
【0009】
【数2】
【0010】
結果として得られる、Ax=bの形の線形代数方程式は、次にブロック110にて線系求解部を用いて解くことができる。
【0011】
ブロック108およびブロック110はNRループを形成し、これはブロック110での線系求解部の解が収束するまで繰返され得る。ブロック112にて、NR解が収束したか否かを判断する。もし収束していれば、プロセスはブロック114へと継続する。解が収束していなければ、NRループが繰返され、プロセスはブロック108に戻る。
【0012】
ブロック114にて、さらに処理されるべきタイムステップがある場合、プロセス100はブロック106に戻り、新たな時点について解を求めることができる。タイムステップがもはやない場合、プロセスはブロック116にて終了する。この時点で、当該問題についての解が得られている。
【0013】
チップ設計の検証は、異なる入力波形または動的なベクトルで多数の過渡シミュレーションの実行を必要とする。シミュレーションを並列実現すればシミュレーションを高速化させることができる。通信オーバーヘッドと、通信を介して計算を同期させる必要とによって、並列の実現においてボトルネックが生じる場合がある。並列の実現においてダイレクトスパース法がもたらしてきた性能利得は、通信および同期オーバーヘッドのため限定的である。プロセス100のNR反復は並列化可能である。この「方法内の並列性」は、回路全体におけるあらゆる箇所での活動(すなわち可変値における急速な変化)によって決まるタイムスケールで回路全体にわたる通信同期を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【0014】
回路シミュレーションにおいて、「システム内の並列性」が提案されている。これは回路シミュレーション関連の文献では「波形緩和」とも呼ばれている。この手法によって、複数の副回路にわたって全体の波形を交換することにより初期値問題の並列シミュレーシ
ョン(時間過渡シミュレーション)が可能となる。しかしながら、ほとんどの実際の回路においては、強く結合されたシステムにおけるフィードバックのため、結果としての収束は遅くなる。その結果、並列の実現から得られる利益は遅い収束の結果減少し、こうして多くの弛緩反復が必要となる。この問題に対処するため、ローカル(端子での負荷)およびグローバル(多数の端子および副回路にわたる)強結合を扱ういくつかの手法がそれぞれ提案されている。実際には、各区画が大きくなりすぎて計算負荷の効果的な並列化が達成されなくなるか、または通信および同期オーバーヘッドのため当該方法が効果的でなくなる。よって、並列化されたシミュレーションの実行に必要な時間を減少させるとともに、ローカルおよびグローバル両方の強結合を考慮した方法が必要とされている。
【課題を解決するための手段】
【0015】
発明の概要
この発明の一実施例に従うと、シミュレーションを実行するためのシステムおよび方法が提供される。システム内の並列性を用いて、上記方法は、大きい問題をいくつかのより小さい区画へと分解する。各区画間で交換される波形が収束するまで一連の反復が実行される。強結合された区画の近似プレビュー解が導入されて、収束に必要な反復の数を減少させる。これら近似プレビュー解は、シミュレーションが行なわれる前に導入される。波形が一旦収束すれば、シミュレーションは解を決定している。
【0016】
添付の図面の各図においてこの発明についての1つ以上の実施例を限定でなく例として説明する。図中においては、同様の参照符号は同様の構成要素を示す。
【発明を実施するための最良の形態】
【0017】
詳細な説明
本願明細書においては、電子回路および物理的なNポートシステムのシミュレーションのための方法およびシステムが記載される。なお、この説明においては、「一実施例」または「或る実施例」への言及は、言及されている特徴がこの発明についての少なくとも1つの実施例に含まれることを意味している。さらに、この説明における「一実施例」または「或る実施例」への個々の言及は、必ずしも同じ実施例を指すものではない。しかしながら、このような実施例は、別段の記載がない限り、さらに説明から当業者に容易に明らかであろう場合を除き、相互に排他的でもない。たとえば、一実施例に記載された特徴、構造、行為などは、その他の実施例にも含まれ得る。したがって、この発明は、ここに記載された各実施例の多種多様な組合せおよび/または統合を含み得る。
【0018】
この発明の一実施例に従うと、シミュレーションを実行するためのシステムおよび方法が提供される。システム内の並列性を用いて、上記方法は、大きな問題をいくつかのより小さい区画へと分解する。各区画間で交換される波形が収束するまで、一連の反復が実行される。強結合された区画の近似プレビュー解が導入されて、収束に必要な反復の数を減少させる。これらプレビュー解は、シミュレーションがローカルおよびグローバル両方の結合の効果を減少させ始める前に導入される。波形が一旦収束すれば、シミュレーションは解を決定している。下で説明するように、近似の導入によって、波形が収束するのに必要な計算時間の量が減少し、ローカルおよびグローバル両方の強結合が勘案される。
【0019】
一般的に、大きなシミュレーションをより小さい区画へと分割することが有利である。より小さい区画はより容易に並列化可能であり、その場合シミュレーションに必要な時間が短縮される。加えて、より小さい区画であれば必要な全体の計算も少なくなる。一般的に、シミュレーションは各区画間で波形を交換することによって並列化される。波形は、特定の区画の出力および入力を表わす。波形は、交換されている波形が或る共通の値に一旦近づけば収束し、結果として解が得られる。2つの区画の間での強結合は、収束に必要な反復の数(または2つの区画間の波形の交換)を増加させる場合がある。
【0020】
従来技術の実現では、ローカルな強結合を効果的に扱うことができるのみであった。以下の各例を用いて示すように、区画のシミュレーションが始まる前に複合近似(または「プレビューア」)をシミュレーション反復に導入することによって、ローカルおよびグローバル両方の結合の効果は大幅に減少される。その結果、より小さい区画を用いることができる一方、交換される波形はより速やかに収束する。その結果として、シミュレーション時間は大幅に短縮されるが、それはより多くの区画に伴って並列化が大きくなり、より小さい区画であれば必要な計算が少なくなり、強結合の効果の減少の結果、収束に必要な反復が少なくなるからである。
【0021】
回路シミュレーションについて詳細に述べるが、その他のシミュレーションもここに記載の技術から利益を享受し得ることが理解される。たとえば、生物学的、化学的および自動車工学的シミュレーションが、ネットワーク化されたnポートに関連して記述可能である。nポートは、他のシステムとネットワーク化可能な大型のシステムのうちの1区画と考えることができる。nポートに関連して記述可能なあらゆる種類のシステムが、ここに開示の技術から利益を享受することができる。たとえば、nポートは、温度、速度、力、電力などといった値を記述し得る。現在、ベリログ(Verilog)AMSといったいくつかのシミュレーション規格が、nポートに関連してさまざまなシステムを記述することが可能である。
【0022】
図2は、この発明の或る実施例が実現され得るコンピュータシステムを例示する。コンピュータシステム200は、図3に記載の、より大型のクラスタの一部であり得る。コンピュータシステム200は、コンピュータシステム200全体にわたる情報のための分配チャネルとして働くバス202を含む。バス202にはプロセッサ204が結合される。プロセッサ204は、インテル(Intel)およびモトローラ(Motorola)で製造されたものを含む(ただしこれに限定されず)任意の好適なプロセッサであり得る。プロセッサ204はまた、多数のプロセッサを含み得る。バス202にはさらにメモリ206が結合される。メモリ206は、ランダムアクセスメモリ(RAM)、読出専用メモリ(ROM)、フラッシュメモリなどを含み得る。基本入出力ユニット208は、キーボード、マウスなどといったいくつかの入力源からの入力を受け、ディスプレイ、スピーカなどといった出力装置に対して出力する。記憶装置210は、磁気または光学記憶装置、たとえばハードドライブまたはコンパクトディスク読出専用メモリ(CD−ROM)を含むあらゆる種類の永久または一時記憶装置を含み得る。オペレーティングシステム(OS)212のコピーが記憶装置210に記憶され得る。OS212は、コンピュータシステム200を動作させるために必要なソフトウェアを含み、リナックス(Linux)などといったユニックス(Unix(登録商標))派生品であり得る。OS212は、マイクロソフト・ウィンドウズ(登録商標)(Microsoft Windows(登録商標))またはマッキントッシュ(Macintosh)OSといったその他入手できるどのOSでもよいことが理解される。ネットワークアダプタ214によって、コンピュータシステム200を、接続部216を介してクラスタ内の他のシステムおよびインターネットといった他のネットワークと接続する。コンピュータシステム200は、単にこの発明の実現に用いられ得るコンピュータシステムの一例であり、その他あらゆる適当な構成を用いてもよいことが理解される。
【0023】
図3は、この発明の或る実施例に従うコンピュータシステム300のクラスタを例示する。いくつかのコンピュータシステム200が、中央スイッチまたはルータ302を伴うピア・ツー・ピア構成を用いて一緒にネットワーク化され得る。これに代えて、ネットワーク化されたシステム300内のコンピュータシステム200の1つは中央サーバであり得る。この実現例を用いて、いくつかの安価なコンピュータシステム200をネットワーク化してクラスタ300とすることによって、並列化された問題を解くための強力なシステムを提供することができる。
【0024】
図4は、この発明の一実施例に従う、nポートまたは回路を含むシステムを区画化してシミュレーションを実行するためのプロセスを記述するフローチャートである。プロセス400は、シミュレートされるべき大きなシステムを、システム内並列の方法で用いられるべき小さい区画へと分割することを記載している。下で述べるように、システム全体をより小さなブロックへと分割することによって、各々の区画についてのノードの数Nは減少し、その結果、必要な計算の総数は減少する。この計算は、収束に必要な波形反復の数だけの、各々の区画の波形シミュレーションの実行からなる。
【0025】
大きな区画、または多数の未知のノード変数を有する区画は、典型的に小さな区画よりも波形シミュレーション中により多くの計算を必要とする。信号完全性効果のない最も純粋なデジタル回路の場合、一時点あたりの計算コストは、ノードの数Nと比例して、およそNのα乗となり、ここでαは1.4から1.6の範囲である。しかしながら、電力格子メッシュといった信号完全性効果が含まれる場合、αは1.8から2.4の範囲となり得る。加えて、より大きな回路の場合、シミュレーションにおける時点の数は、より高い全体の活動性のため大きくなる。総合的に、これらの効果は、収束レートおよびオーバーヘッドが悪影響を受けない限り、より小さい区画の実行を極めて有利としている。
【0026】
一般的に、回路が有するノードまたは変数Nが少なくなるのに伴い、1タイムポイントあたりに必要とされる計算は少なくなる。たとえば、α=2のシステムにおいては、1000ノードを有する区画は、波形において1タイムポイントあたり最大100万の浮動小数点演算を必要とする。一方、1000ノード回路が各々100ノードの10個の小さい回路へと分割される場合、これら10個の小さい回路の各々は、1タイムポイントあたり最大わずか1万の浮動小数点演算を必要とし、すなわち1タイムポイントあたり合計で最大10万の演算となる。加えて、より大きな回路の場合、シミュレーション内のタイムポイントの数は、全体の活動性がより高いことから高くなる。
【0027】
強結合の効果は、システムをより小さい区画へと分割する利益に対してバランスが取られる。たとえば、一区画は、回路の要素であって、その挙動が当該回路の他の要素の挙動に大きく依存する要素、を含む回路を含み得る。区画化によってこれら強結合された区画が分割される場合、結果として得られるシミュレーションは、典型的に、収束するために多数の波形反復を必要とすることになる。その結果、収束に必要な反復の数の増大は、区画がより小さくなったことによって各々の波形反復をシミュレートするために必要な時間の減少を上回る場合がある。下に記載のプレビューアを用いた近似の導入によって、グローバルおよびローカル両方の結合の効果が減少し、収束に必要な反復の数が減少する。
【0028】
プロセス400は開始ブロック402で始まる。ブロック404にて、システム全体の、サブシステムへの初期区画化が作成される。この区画化は、システムの内在的な特性から生じる弱結合に基づいて完了される。システム全体をスキャンして、初期区画の数およびそのシミュレーション順序を決定するのが効果的である。これら区画は、内在的結合の順序でシミュレートされたときに比較的少ない反復で収束するように選択される。大きな初期区画が内部の強結合の結果である。上述のように、より大きい区画は、各々の波形シミュレーションにつきはるかに長い計算時間を必要とする。より長い時間に伴い、コンピュータ負荷におけるバランスの崩れが生じて並列化が制約を受ける。ブロック406にて、さらなる並列化を必要とする順序付けられた区画が識別される。これら区画は、ブロック404にて生成された区画を調べることによって、さらに分割可能と識別される。識別された区画は、所望よりも大きい強結合された区画である。ブロック408にて、プレビューアシミュレーションが導入されて、さらなる並列化が可能となり、細かい区画化および順序が得られる。プレビューアおよびその動作については下でさらに説明するが、一般的には、プレビューアは、近似プレビュー解をもたらすために、強結合されたシステム内
に導入されることになる近似を含む。プレビューアは、シミュレータに対する解を「プレビュー」する。プレビューアは、区画のシミュレーションが始まる前に近似を生成することから、システムはローカルおよびグローバル結合の効果を減少させるが、これについては下で説明する。
【0029】
プレビューアは、さらなる分割のための最適な候補を決定する。ブロック410にて、細かい区画シミュレーションが実行され、これにはコンピュータプラットフォーム上の新たな順序におけるプレビューアシミュレーションが含まれる。この動作は、シミュレーション自体の実行である。このシミュレーションは、SPICE、ベリログAMS、または別のシミュレーションアプリケーションを用いて実行され得る。
【0030】
ブロック412にて、シミュレーションの進行が監視され、提案された分割の収束についてのテストが実行される。必要であれば、上記分割をさらに細かくすることによって、最も良いブロック組ひいては最も良いシミュレーションを生成する。
【0031】
回路シミュレーションといった分野で生じる動的なシステムのシミュレーションは、典型的にはnポートの相互接続を用いて記述される。ベリログAMSといったシミュレーション言語によって、設計者は、nポートに関連して階層的に大型のシステムを記述することが可能である。SPICEといった回路シミュレータによれば、nポート副回路に関連して階層記述が可能である。任意のn+1端子装置がnポート副回路として記述され得る。各々のnポートは、一組の微分方程式および代数方程式として内部的に記述される。ポートでの相互接続は、その結果としてキルヒホフ(Kirchoff)の電流則(KCL)またはキルヒホフの電圧則(KVL)といったさらなる制約が生じる。
【0032】
図5は、強結合されたマルチポート非線形回路を例示する。回路500は、個々のnポートとして記述され得る回路502,504を含む。回路500は、上述の区画化404の結果である。回路500は、区画としては大きすぎるものである場合があり、したがって、シミュレーションに必要な時間を増加させることになる。しかしながら、回路500はまた、強結合されているので、分割された場合には収束が遅くなりすぎることになる。大きな回路500は、予備的に2つの回路502,504に分割することができ、ここで回路502は近似可能であり、回路504は、元の回路500の残りである。
【0033】
回路502がnポートインピーダンスH1として表わされ、回路504がより大きな区画500の残りであると仮定する。回路502は、n+1端子回路とすることができ、ここでnは回路内にあるポートの数であり、回路502は、回路の残り504と共通の接地406を共有する。
【0034】
回路502の代わりに計算上コストの低い近似、たとえばH^1(なおH^などは、図6以下のようにHなどの上に^があるものを表わすこととする)を導入することによって回路500が変換される場合、収束は加速可能である。図6は、この発明の或る実施例に従う近似を含む強結合された回路600を例示する。回路600は、回路502の代わりに近似回路602を用いた回路500のプレビューアである。残りの回路504は上述のものと同じである。下に述べるように近似H^1が適当なものである限り、プレビューア回路600は、元の回路区画502H1に弱結合されることになり、プレビューア回路600および回路502の収束は、はるかに速やかに起こることになる。近似H^1は、計算上低コストとなるように選択され、その場合、プレビューア回路600のシミュレーションは、区画H2のシミュレーションおよび区画502H1のシミュレーションとほぼ同じ時間がかかる。
【0035】
シミュレーションについての波形反復を以下に記載する。
【0036】
(1) k=1;波形を初期化ΔV1k-1=0
(2) プレビューア回路600をシミュレートすることによってΔV1k-1├→{I1k,V^1k}
(3) 区画化されたスタンダロンインピーダンス回路502H1をシミュレートすることによってI1k├→V1k、こうして電圧波形ΔV1k=V1k−V^1kを与える。
【0037】
(4) ‖ΔV1k-1−ΔV1k‖>tolであれば、k=k+1、演算(2)へ戻り、他では終了する。
【0038】
値kは各々の反復につき増分される。第1の演算(1)において各変数が初期化される。
【0039】
第2の演算(2)において、ΔV1k-1├→{I1k,V^1k}が決定される。値ΔV1k-1は、実際の電圧波形と、前の反復k−1についての近似電圧波形との差に対応する。この値は回路600に入力され、シミュレーションが実行され、電流波形についての値およびこの反復についての電圧波形の近似がプレビューアを用いて決定される。第3の演算(3)において、電流波形についての決定された値が回路に入力されて、この反復についての電圧波形についての値を決定する。次に、この反復ΔV1kについての実際値および近似値間の差が決定され得る。演算(4)において、波形ΔV1k-1およびΔV1k間の差のノルムが、予め定められた許容値よりも大きい場合、反復は継続してプロセスは演算(2)に戻る。差が許容値よりも小さい場合、波形は収束しており、回路602についてのシミュレートされた値は決定されている。波形のノルムの計算およびプレビューアにおける近似の選択については下でさらに説明する。
【0040】
場合によっては、いくつかの近似を単一の区画内に導入することが必要なこともある。図7は、複数のより小さい区画へと分解された大きい区画を示す。図7に示すように、回路700は、初期の区画化から残っている大きい区画である。回路700は強結合されているため、いくつかの副回路702a〜702xに分割されており、ここでxは、m個の近似区画に等しい任意の区画数である。副回路702a〜702xは、回路700H0の残り704にすべて結合され、これは典型的に抵抗器といった単純な受動素子を含む。図8は、m個の近似区画を有する回路700についてのプレビューア回路800を示す。副回路702a〜702xの各々は、近似H^1802aからH^m802xと交換されている。残りの回路H0804は、残りの回路704と同じである。
【0041】
回路800の収束についての波形反復は以下のように進行する。
【0042】
(1) 初期化k=1。i=1,…mの場合、波形ΔVi0
(2) プレビューア800をシミュレートすることによってΔV1k-1├→{Iik,V^ik}。704−(802a…802x)。
【0043】
(3) 区画化されたスタンダロンインピーダンスマルチポート回路Vik=Hi(Iik)、i=1,…m、の各々をシミュレートすることによってIik├→Vik、こうして波形ΔVik=Vik−V^ikを与える。この演算は並列で行なわれ得る。
【0044】
(4) 任意のi=1,…mについて‖ΔVik-1−ΔVik‖>tolの場合、k=k+1であり、演算(2)に戻り、他では終了する。
【0045】
このプロセスは、図6に関して上述したプロセスと類似である。しかしながら、この場合、シミュレーションが実行されなければならないいくつかの異なる区画が存在する。値
iは各々の区画につき増分される。図9は、いくつかの異なる区画についてのシミュレーションを実行するいくつかのプロセッサを例示する。図9に示すように、第3の演算(3)は並列化可能であり、これのためには、第2の演算(2)においてプレビューアから電流波形Iikが一旦利用可能となれば別個のプロセッサ904a〜904xにおいて各々の元の区画902a〜902xのシミュレーションを実行する。他では、プロセスは図6に関して上述したものと同じである。
【0046】
上述のように、第3の演算(3)は並列化され得るが、第2の演算(2)の後に直列的に続く。複合近似の計算コストが、各々の個々の回路区画Vik=Hi(Iik)の計算コストよりも小さいときには、第2の演算(2)および第3の演算(3)のさらなる並列化が達成可能である。図10は、この発明の或る実施例に従う並列動作する複数のプロセッサを例示する。一実施例では、各々の区画が、シミュレーションのためにおよそ同じ量の計算時間を必要とするように、複数の区画が選択される。
【0047】
図10は、上述のシミュレーションプロセスを並列化する間における時系列1008に沿っての複数のプロセッサ1002,1004,1006の動作を例示する。時間tsimは、シミュレーションにおける各々の反復についての時間である。反復中のシミュレーションインターバルは時間セグメントに分割される。図10は、各々が等しい計算時間tsim/2を必要とする2つの時間セグメントを伴う例を示す。第1のプロセッサ1002は、一般にプレビューアの計算が割当てられる。第2のプロセッサ1004および第3のプロセッサ1006は、個々の区画が割当てられてこれら区画をシミュレートする。この例においては、第1のプロセッサ1002は複合近似(プレビューア)を実行し、第2のプロセッサ1004は第1の区画902aを実行し、第3のプロセッサ1006は第2の区画902bを実行する。たとえば、第1のプロセッサ1002は、反復1010aの前半の間に複合近似1012を実行する。近似1012が完了したとき、これはプロセッサ1004,1006に転送され、各々のプロセッサ1004,1006は、反復の後半の間に個々の区画をシミュレートする。換言すると、t0およびt0+tsim/2間の期間の間中、第1のプロセッサ1002はプレビューア1012を算出し、これはプロセッサ1004およびプロセッサ1006によってそれぞれシミュレーション1014およびシミュレーション1016を実行するために用いられることになる。t0+tsim/2およびt0+tsim間の期間においては、第1のプロセッサ1002は、第1の反復の後半のプレビューアシミュレーションを算出する。この時間の間中、プロセッサ1004,1006は、プロセッサ1002によって時間t0およびt0+tsim/2中に生成されたプレビューアを用いて、反復の前半についてのシミュレーションを実行する。時間t0+tsimおよびt0+1.5*tsim間に、プロセッサ1004,1006は、プロセッサ1002によって時間t0+tsim/2およびt0+tsim中に生成されたプレビューア解1022を用いてシミュレーション1018,1020を実行する。このプロセスは、シミュレーションが収束するまで継続する。
【0048】
より具体的には、シミュレーションインターバル1010の前半の終わりに、反復1010aの前半インターバルについてのポート電流波形Ii1、i=1,2がプロセッサ1002に対して利用可能となる。これら電流波形は、スタンダロン区画を実行するよう割当てられたプロセッサ1004,1006に転送される。スタンダロン区画は、前半インターバルについてのシミュレーションを開始し、一方でプロセッサ1002は、シミュレーションインターバルの後半についてのシミュレーションを実行する。プロセッサ1004,1006が時間t0+tsimでインターバルの前半のシミュレーションを完了させたとき、前半のインターバルについての区画から、プロセッサ1002で次の反復中に用いられるべき複合近似までの電圧波形Vi1、i=1,2をもたらす。これによって、プロセッサ1002は、時間t0+tsimにおいて、第2の反復についての前半のインターバルのシミュレーションを継続することができる。パイプライン化された評価によって、当該方法を
効率的に並列実行することが可能となる。
【0049】
図11および図12は、インピーダンスおよび電圧でなくアドミタンスおよび電流を用いたこの発明の或る実施例を例示する。図11は、プレビューア回路600に類似の強結合された回路のためのプレビューア1100を例示する。回路1100は、近似回路1102および回路の残り1104を含む。図12は、回路800に類似の多数の別個の区画を含む回路1200を例示する。回路1200は、複数の区画1202a〜1202xおよび回路の残り1204を含む。上述のインピーダンスおよび電圧nポートと類似して、波形反復は以下のように進行する。
【0050】
(1) 初期化k=1。i=1,…mの場合、波形ΔIi0
(2) 上述の図11に示すようにプレビューアシステム0−1’…m’をシミュレートすることによってΔIik-1├→{Vik,I^ik}。
【0051】
(3) 区画化されたスタンダロンアドミタンスマルチポート回路Iik=Hi(Vik)、i=1,…mの各々をシミュレートすることによってVik├→Iik、これによって波形ΔIik=Iik−I^ikを与える。この演算は並列で実行可能である。
【0052】
(4) 任意のi=1,…mの場合に‖ΔIik-i−ΔIik‖>tolである場合、k=k+1であり、演算(2)に戻り、他では終了する。
【0053】
ここで用いられる場合、最初の区画1202aについてはi=1であり、最後の区画1202xについてはi=mである。上と同様に、波形ΔIikは、電流の実際の算出値と近似値との差を測定する。第4の演算(4)において、前の繰返しと現在の繰返しとの波形ΔIik間の差のノルムが許容値tol未満であれば、反復は収束しており、この区画につてのシミュレーションは完了している。図8および図12においては、任意の1つのnポートはハイブリッドマルチポートであり得る。対応の入力および出力は、電圧および電流のハイブリッド(組合せ)である。波形反復は、回路についての適当な入力および出力波形のために変更が加えられる。
【0054】
この手法にはいくつかの利点がある。一般に強結合された非線形のマルチポートシステムが考慮されているため、グローバルおよびローカル両方のフィードバック状況がともに対処される。以前の方法では、単一の端子での負荷から生じるローカルフィードバックに対してグローバルフィードバックとは別個に対処を図っていた。これら先行技術の方法では、MOS回路における特定の単方向構造を利用していた。強いローカルな両方向結合が存在する場合、これは収束上の困難さを引起していた。先行技術の方法にはまた、強いグローバル結合が存在する場合に収束が遅いという問題があった。
【0055】
本方法は、非線形波形をバナッハ空間での非線形波形に写像するあらゆるシミュレーションに適用される。対応のバナッハ空間ノルムが、反復中に収束テストにおいてかつ下記の近似のための増分演算子利得を計算するために用いられる。したがって、その利益を引出すためにマルチポートシステムにおける特定の構造は用いない。本方法から引出される利益に加えて、下層ドメインの構造を利用するあらゆるシミュレータが、構造を利用するために使用され得る。たとえば、SPICEといった回路シミュレータにおいては、下層の回路式のスパーシティ構造はシミュレータ自体によって利用される。個々の構成要素のシミュレーションにSPICEを用いることによって、回路式のスパーシティ構造の利用が可能となる。
【0056】
複合近似は、多種多様な手法を用いてシミュレーション可能である。たとえば、MOS回路シミュレータにおいては、イベント駆動シミュレーションにおいてテーブル駆動のピ
ースワイズ近似モデルを用いて複合近似が構成可能である。このようなシミュレータは、高速タイミングシミュレータとも称され、SPICEよりも10〜1000倍の速度で近似波形をもたらす。しかしながら、近似波形はわずか5〜10%の範囲で正確なものである。近似シミュレーションの別の例は、MOR(Model Order Reduction)を用いるというものである。大型のRLCネットワークについては、MORは、最大10%のエラーを導入することと引き換えに数桁速い計算をもたらす。
【0057】
近似が収束のための条件を満たす限りあらゆる特定ドメインのシミュレータおよび特定ドメインの近似を用いることができる。注目すべきことは、比較的粗い近似が速い収束に繋がることである。
【0058】
以下の記載は、上述の各プロセスで用いられることになる近似を選択するプロセスを説明するものである。強結合されたシステムについてのプレビューアは、以下の特性を有する複合近似を含む。
【0059】
(1) プレビューアは、各々の元の構成要素nポートを正確にシミュレートするために必要とされる時間に相当する時間内にそれ自身のシミュレータでシミュレート可能である。これは、図10におけるパイプライン化されたプロセスに関して既に述べられたものである。
【0060】
(2) 残りの回路H0は無視できるほど小さなものであり、典型的に抵抗器またはノードといった受動素子を含む。
【0061】
(3) 各々の近似された構成要素nポートH^iは、Hiに対してエラーテストを満たす。これはHi−H^iの増分演算子利得についてのテストである。
【0062】
近似のための候補には、簡略化テーブルルックアップモデルでのシミュレーション、スイッチレベルシミュレーション、マクロモデル、および低次縮約モデルが含まれる。これら近似は、再利用される構成要素についての前特徴付けを含み得る。これに加えて、近似の品質とその実行時間速度との間の兼ね合いがある。前特徴付け時には、HiとH^iとの間のエラーは以下を用いて計算される。
【0063】
u1,u2,…,ulを、H^iの当てはめに用いられる別個の入力ベクトルとする。
【0064】
y1,y2,…,ylを、入力yj=Hi(uj)でのHiの実行からの出力ベクトルとする。
【0065】
y^1,y^2,…,y^lを、入力y^j=H^i(uj)でのH^iの実行からの出力ベクトルとする。
【0066】
ここでは、ujは入力波形値を表わし、yj=Hi(uj)は、入力ujが与えられた場合の区画Hiの実際の波形出力を表わし、y^j=H^i(uj)は、入力ujが与えられた場合の区画についての近似出力を表わす。近似についてのエラーを決定するためには、増分演算子利得の推定値が計算される。
【0067】
【数3】
【0068】
ここで入力または出力ベクトル波形のノルムは
【0069】
【数4】
【0070】
である。任意の所与の時間tにて、y(t)は電圧または電流変数のベクトルである。|y(t)|は、順序付けられた実際のn個の要素からなる集合の線形空間におけるノルムを表わす。たとえば、y(t)が4つの電圧から構成される場合、y(t)=[V1(t),V2(t),V3(t),V4(t)]であり、その場合
|y(t)|=max[abs(V1(t)),abs(V2(t)),abs(V3(t)),abs(V4(t))]、
または代替的に|y(t)|=(V12(t)+V22(t)+V32(t)+V42(t))1/2である。
【0071】
【数5】
【0072】
後の記載は、ここに記載された技術のいくつかの例を説明する。これら記載は例であると理解され、さらに、記載の発明については他のいくつかの可能な実現例および実施例が存在することが理解される。
【0073】
図13〜17は、この発明の或る実施例に従う両方向ローカル結合を呈する回路のシミュレーションを例示する。図13は、両方向ローカル結合を呈する回路を例示する。回路1300は、非線形要素G2 1302を含む強結合された回路であり、これは2つの並列のダイオード方程式によって記述され得る。
【0074】
【数6】
【0075】
回路1300は、H1と表わす第1の区画1304と回路の残り1306とに区画化されることになる。回路1300はさらに、3つのキャパシタC1 1308、C2 1310およびC3 1312、線形要素G1 1314および電流源J 1316を含む。
【0076】
標準ノード分析(キルヒホフの電流則を用いる)からは、2つの結合された微分方程式が与えられる。
【0077】
【数7】
【0078】
ガウス・ザイデル反復を用いてこの回路を複数の区画へと分解するための先行技術の方法は、結果として以下の式を与える。
【0079】
【数8】
【0080】
【数9】
【0081】
結合キャパシタC3 1310が、他のキャパシタC1 1308およびC2 1310と比較して大きい静電容量を有するとき、収束のレートは遅くなる。図14は、標準的なガウス・ザイデル分解を用いた遅い収束を例示する。グラフ1400は、x軸1402に沿ってプロットされた時間およびy軸1404に沿った電圧を有する。プロット線1406の各々は、回路1300についての実際の値と比較した先行技術のガウス・ザイデル分解を用いたシミュレーションにおける各々の漸進反復についてのエラーを例示する。グラフ1400は、10回の反復を通じて遅く収束するシミュレーションを示す。プロット線1406aは、1回目の反復についてのエラーを示し、プロット線1406jは、10回目の反復についてのエラーを示す。シミュレーションは正しい解へ向けてゆっくりと収束するが、10回目の反復の後でもエラーはいくつかのタイムポイントで0.6Vを超過する。このような低い収束レートは実際の場面は許容不可能であることは明らかである。先行技術の方法を用いた発見的区画化アルゴリズムでは回路1300を区画化しないであ
ろう。しかしながら、大型の回路でこれを行なうことは、並列計算のために不十分な粒度に繋がる。
【0082】
図15は、非線形要素G2 1302についての近似を例示する。グラフ1500は、x軸1502上の電圧対y軸1504上の電流のプロットを示す。完全な、シミュレートされたプロット1506を、グラフ1500に示す。近似値はプロット1508を用いて示される。近似値は、ここに記載の技術を用いて、たとえば粗いピースワイズリニアテーブルルックアップを用いて得られる。
【0083】
図16は、非線形要素G2のピースワイズリニア近似1508を含む回路1300を例示する。プレビューア回路1600は、回路1300であって、元の非線形要素1302の代わりに近似1602を含むものである。図5,6に記載の区画1304の代わりに区画1604が示されている。
【0084】
図17は、プレビューア回路1600を用いた高速収束を例示するプロットである。プロット1500と同様、プロット1700は、x軸1702に沿った時間およびy軸1704に沿った電圧を示す。プロット内の電圧は、回路1300によって生成された実際の出力からのエラーである。なお、y軸1704の目盛は、上述のy軸1504の目盛よりもはるかに小さく、1回目の反復1706aについても10回目の反復1506jについてのエラーよりもエラーがはるかに小さいことを示している。3回目の反復1706cまでに、エラーは極めて小さくなっており、シミュレーションは、回路1300についての実際の算出値に極めて近づいている。その結果、ここに記載のこの発明の各実施例を用いて、反復は近似を用いないよりもはるかに速やかに収束する。
【0085】
図18〜22は、この発明の一実施例に従う単方向グローバルおよびローカル両方向結合ならびにそのシミュレーションを例示する。図18は、四次フィルタ回路1800を例示する。回路1800は、3つの演算増幅器の段1802,1804,1806を含む。入力電圧から出力電圧への理想化されたフィルタ転送機能は、振動応答を伴う二次である。実際の応答は、演算増幅器におけるスルーレート(slew rate)およびクランピングといった非線形の効果を有する。加えて、より高次の寄生極およびゼロは、線形化された転送機能に存在する。各々の演算増幅器段1802,1804または1806を副回路とみなすと、機能ブロックの単方向入出力信号流れを横切るのに伴い振動応答を生じさせる強いグローバル結合が存在することが明らかである。グローバル結合に加えて、各々すべての接続ノードにはローカルな両方向負荷効果が存在する。グローバル結合は、高速で作用しかつ強いものである。
【0086】
図19は、ガウス・ザイデル分解を用いて区画化された回路1800を例示する。分解1900は、複数の順序付けられた区画1902,1904,1906に分割された回路1800を示す。これら区画は、公知のガウス・ザイデル分解を用いて作り出されている。
【0087】
図20は、ガウス・ザイデル分解を用いた回路1800のシミュレーションの収束を示すプロットである。グラフ2000は、x軸2002に沿った時間およびy軸2004に沿った電圧を示す。プロット2006は、回路1800の実際の応答を示す。プロット2008は、ガウス・ザイデル分解1900を用いた5回の反復後の出力を示す。プロット2010は、ガウス・ザイデル分解1900を用いた10回の反復後の出力を示す。波形は極めて遅く収束することが見て取れる。
【0088】
この発明の或る実施例に従うと、回路1800は、図7,8,9の回路700が分解されるのと同じ態様で分解され得る。図21は、この発明の或る実施例に従う回路1800
の分解からのプレビューアを例示する。副回路段H11802、H21804およびH31806の各々は、非線形2ポートインピーダンス演算子として見られる。残りの回路H02108は、相互接続ワイヤを伴うノードのみを含む。各々の段2102,2104,2106の近似は、完全な非線形演算増幅器の代わりに等価の理想電圧制御電圧源を用いることによって達成される。
【0089】
図22は、この発明の或る実施例に従い分解された回路1800の収束を例示するグラフである。グラフ2200は、x軸2202における時間およびy軸2204における出力電圧を示す。プロット2206は完全なシミュレーションである。プロット2208は1回目の反復後の出力であり、プロット2210は2回目の反復後の出力である。図7,8,9に示す分解を用いたときにシミュレーションは極めて速やかに収束することが見て取れる。
【0090】
図23〜26は、この発明の或る実施例に従う両方向ローカルおよびグローバル結合の非線形メッシュ例を示す。図23Aは、非線形二次元メッシュ2300を例示する。図23Bおよび23Cは、メッシュ2300の分解図を示す。メッシュ2300は、集積回路(IC)内の電力格子であり得る。メッシュ2300は、4つの隣接するノードに接続する各々の内部ノード2304について4つの抵抗器2302を含む。各々のノード2304にて、キャパシタ2306およびダイオード2308が接地2310に接続される。ダイオード2308は逆バイアスされる。メッシュコーナは,4つの接続抵抗器2302を介して供給ノードに接続される。メッシュノードは、タイル2312に分割される。図23Aに示すように、メッシュ2300は3×2タイルの格子を含む。各々のタイル2312は、高インピーダンス電流源2314が取付けられる中央ノード2304を含む。
【0091】
図23Cに示すように、タイル2312は、接続抵抗器2316を介して接続される。これら接続抵抗器2316は、残りの回路H0を構成でき、各々のタイル2312は、図7,8,9におけるような区画Hiを含み得る。メッシュ2300は、この発明の或る実施例に従いこの態様で分解され得る。
【0092】
メッシュ2300についての近似H^iは、Hiの線形化されたインピーダンスの低次縮約モデルを用いて作り出されている。その結果得られるプレビューアは、効率的にシミュレート可能な低次の線形システムである。
【0093】
図24は、回路2300のフルレファレンスシミュレーションから、およびそのフルオーダ線形近似からのタイル2312についての中央ノード電圧を示すグラフ2400を例示する。x軸2402は時間を示し、y軸2404は出力の電圧を示す。プロット2406はフルレファレンスシミュレーションを示し、プロット2408はフルオーダ線形近似を示す。2つのプロット2406,2408間の差は、ダイオード2308の非線形性から生じる。
【0094】
図25は、タイル2312の中央ノード電圧についてのフルレファレンスシステムおよび近似の低次プレビューア応答間の差を例示する。ここでもまた、x軸2502は時間を示し、y軸2504は電圧を示す。プロット2506では、近似と完全な参照との差がかなりあることが示される。
【0095】
図26は、プレビューアベースの近似の或る実施例を用いた3回の反復後のシミュレーションの電圧出力のエラーを示すグラフである。グラフ2600は、時間を示すx軸2602および電圧を示すy軸2604を含む。プロット2606では、わずか3回の反復後にエラーは受け入れられる許容値以内に十分にあることが示される。これとは対照的に、標準的なガウス・ザイデル分解を用いた場合、収束は50回超の反復を要する。
【0096】
この発明の各実施例は回路シミュレーションには限定されないことが理解される。たとえば、化学的シミュレーション、生物学的シミュレーション、自動車工学的シミュレーションなどといった他のいくつかの種類のシミュレーションが、ここに記載されたシステムおよび技術を用いて実行され得る。これら技術は、特定の用途に対して適合され得る。
【0097】
この発明は、その特定の例示的な実施例を参照して記述してある。しかしながら、この開示の利益を有する者にとっては、この発明のより広い意味および範囲から逸脱することなしにさまざまな変形や変更が上記各実施例に対して可能であることが明らかであろう。したがって、明細書および図面は、制限的でなく例示的な意味で考えられるべきである。
【図面の簡単な説明】
【0098】
【図1】初期値問題を用いてシミュレーションに対する解を決定するためのプロセスを例示するフローチャートである。
【図2】この発明の或る実施例が実現され得るコンピュータシステムを例示する図である。
【図3】この発明の或る実施例に従うコンピュータシステムのクラスタを例示する図である。
【図4】この発明の一実施例に従いシステムを区画化してシミュレーションを実行するためのプロセスを説明するフローチャートである。
【図5】強結合されたマルチポート非線形回路を例示する図である。
【図6】この発明の或る実施例に従う近似を含む強結合された回路を例示する図である。
【図7】複数の小さな区画へと分解された大きな区画を例示する図である。
【図8】m個の近似区画を伴う回路700についてのプレビューア回路を例示する図である。
【図9】複数の異なる区画についてのシミュレーションを実行する複数のプロセッサを例示する図である。
【図10】この発明の或る実施例に従う並列実行される複数のプロセッサを例示する図である。
【図11】プレビューア回路600に類似の強結合された回路についてのプレビューアを例示する図である。
【図12】回路800に類似の、多数の別個の区画を含む回路を例示する図である。
【図13】両方向ローカル結合を呈する回路を例示する図である。
【図14】標準ガウス・ザイデル分解を用いた遅い収束を例示する図である。
【図15】非線形要素G2についての近似を例示する図である。
【図16】非線形要素G2のピースワイズリニア近似を含む回路を例示する図である。
【図17】回路の高速収束を例示するプロットである。
【図18】四次フィルタ回路を例示する図である。
【図19】ガウス・ザイデル分解を用いて区画化された回路を例示する図である。
【図20】ガウス・ザイデル分解を用いた回路のシミュレーションの収束を示すプロットである。
【図21】この発明の或る実施例に従う回路の分解からのプレビューアを例示する図である。
【図22】この発明の或る実施例に従い分解された回路の収束を例示するグラフである。
【図23A】非線形二次元メッシュを例示する図である。
【図23B】メッシュの一例の分解図である。
【図23C】メッシュの一例の分解図である。
【図24】回路のフルレファレンスシミュレーションから、およびフルオーダ線形近似からのタイルについての中央ノード電圧を示すグラフである。
【図25】タイルの中央ノード電圧についてのフルレファレンスシステムおよび近似の低次プレビューア応答間の差を例示する図である。
【図26】プレビューアベースの近似の或る実施例を用いた3回の反復後のシミュレーションの電圧出力のエラーを示すグラフである。
【技術分野】
【0001】
関連出願
本願は、2003年5月22日出願の、「電子回路および物理的nポートシステムの高速・正確なシミュレーション方法(Method for fast, accurate simulation of electronics circuits and physical n-port system)」と題された、米国特許仮出願連続番号第60/473,047号の優先権を主張する。
発明の分野
この発明は、一般的にシミュレーションに関し、特定的には、大型の複雑系についての正確な波形レベルコンピュータシミュレーションに関する。
【背景技術】
【0002】
背景
コンピュータシステムを用いてシミュレーションを実行することによって、設計者または開発者が或る設計を製造前にテストできるようにする場合がある。たとえば、設計者はコンピュータアプリケーションを用いて複雑な回路を構築する場合がある。次に、このアプリケーションは、或る入力があった場合にいくつかの時点で回路の出力をシミュレートすることができる。シミュレーションを用いて設計者は容易にいくつかの回路の原型を作り出し、それを実際に構築することなしにテストすることができる。
【0003】
シミュレーションは、しばしば大きな計算リソースを必要とする。このリソースを低価格で提供する1つの方策として、並列動作する複数の機械からなるクラスターを用いるというものがある。たとえば、複数のコンピュータシステムを合せてネットワーク化することによって、単一の問題についての解に対して集団で作業を行なうことができる。このシミュレーションを並列実行する1つの問題は、機械同士の間で作業を分割し連携させることである。
【0004】
回路シミュレーションは、しばしばSPICE(Simulation Program With Integrated
Circuit Emphasis)シミュレータまたはそこから派生したものを用いて実行される。これらシミュレータは、「ダイレクトスパース(Direct Sparse)」解求方法として知られる数値積分を用いる。回路が大型化し信号完全性効果がより重要となるのに伴い、これらシミュレーションを実行するのにかかる時間が極端に長くなっている。これらシミュレーションでは、典型的には、回路の過渡挙動が伴い、初期値問題(Initial Value Problem)を解くことが必要である。
【0005】
図1は、初期値問題を用いてシミュレーションに対する解を決定するためのプロセスを例示するフローチャートである。プロセス100は、ダイレクトスパース法を用いて大規模なシミュレーションの所与の部分についての解を決定するために用いることができる。たとえば、回路シミュレーションを複数のブロックに分割し、その各々を微分代数方程式(differential algebraic equations:DAE)によって表わせるようにすることができる。一実施例に従うと、DAEは、変形ノード分析(modified nodal analysis:MNA)を用いて得られる。次に、これら式を簡略化して解くことによって当該シミュレーションについての解に達することができる。
【0006】
【数1】
【0007】
これらは非線形代数方程式である。
【0008】
非線形の式は解くのが困難で計算コストがかかるため、ブロック108にて、ニュートン・ラフソン(NR)反復を実行して線形代数方程式を得る。NR反復は以下の形である。
【0009】
【数2】
【0010】
結果として得られる、Ax=bの形の線形代数方程式は、次にブロック110にて線系求解部を用いて解くことができる。
【0011】
ブロック108およびブロック110はNRループを形成し、これはブロック110での線系求解部の解が収束するまで繰返され得る。ブロック112にて、NR解が収束したか否かを判断する。もし収束していれば、プロセスはブロック114へと継続する。解が収束していなければ、NRループが繰返され、プロセスはブロック108に戻る。
【0012】
ブロック114にて、さらに処理されるべきタイムステップがある場合、プロセス100はブロック106に戻り、新たな時点について解を求めることができる。タイムステップがもはやない場合、プロセスはブロック116にて終了する。この時点で、当該問題についての解が得られている。
【0013】
チップ設計の検証は、異なる入力波形または動的なベクトルで多数の過渡シミュレーションの実行を必要とする。シミュレーションを並列実現すればシミュレーションを高速化させることができる。通信オーバーヘッドと、通信を介して計算を同期させる必要とによって、並列の実現においてボトルネックが生じる場合がある。並列の実現においてダイレクトスパース法がもたらしてきた性能利得は、通信および同期オーバーヘッドのため限定的である。プロセス100のNR反復は並列化可能である。この「方法内の並列性」は、回路全体におけるあらゆる箇所での活動(すなわち可変値における急速な変化)によって決まるタイムスケールで回路全体にわたる通信同期を必要とする。
【発明の開示】
【発明が解決しようとする課題】
【0014】
回路シミュレーションにおいて、「システム内の並列性」が提案されている。これは回路シミュレーション関連の文献では「波形緩和」とも呼ばれている。この手法によって、複数の副回路にわたって全体の波形を交換することにより初期値問題の並列シミュレーシ
ョン(時間過渡シミュレーション)が可能となる。しかしながら、ほとんどの実際の回路においては、強く結合されたシステムにおけるフィードバックのため、結果としての収束は遅くなる。その結果、並列の実現から得られる利益は遅い収束の結果減少し、こうして多くの弛緩反復が必要となる。この問題に対処するため、ローカル(端子での負荷)およびグローバル(多数の端子および副回路にわたる)強結合を扱ういくつかの手法がそれぞれ提案されている。実際には、各区画が大きくなりすぎて計算負荷の効果的な並列化が達成されなくなるか、または通信および同期オーバーヘッドのため当該方法が効果的でなくなる。よって、並列化されたシミュレーションの実行に必要な時間を減少させるとともに、ローカルおよびグローバル両方の強結合を考慮した方法が必要とされている。
【課題を解決するための手段】
【0015】
発明の概要
この発明の一実施例に従うと、シミュレーションを実行するためのシステムおよび方法が提供される。システム内の並列性を用いて、上記方法は、大きい問題をいくつかのより小さい区画へと分解する。各区画間で交換される波形が収束するまで一連の反復が実行される。強結合された区画の近似プレビュー解が導入されて、収束に必要な反復の数を減少させる。これら近似プレビュー解は、シミュレーションが行なわれる前に導入される。波形が一旦収束すれば、シミュレーションは解を決定している。
【0016】
添付の図面の各図においてこの発明についての1つ以上の実施例を限定でなく例として説明する。図中においては、同様の参照符号は同様の構成要素を示す。
【発明を実施するための最良の形態】
【0017】
詳細な説明
本願明細書においては、電子回路および物理的なNポートシステムのシミュレーションのための方法およびシステムが記載される。なお、この説明においては、「一実施例」または「或る実施例」への言及は、言及されている特徴がこの発明についての少なくとも1つの実施例に含まれることを意味している。さらに、この説明における「一実施例」または「或る実施例」への個々の言及は、必ずしも同じ実施例を指すものではない。しかしながら、このような実施例は、別段の記載がない限り、さらに説明から当業者に容易に明らかであろう場合を除き、相互に排他的でもない。たとえば、一実施例に記載された特徴、構造、行為などは、その他の実施例にも含まれ得る。したがって、この発明は、ここに記載された各実施例の多種多様な組合せおよび/または統合を含み得る。
【0018】
この発明の一実施例に従うと、シミュレーションを実行するためのシステムおよび方法が提供される。システム内の並列性を用いて、上記方法は、大きな問題をいくつかのより小さい区画へと分解する。各区画間で交換される波形が収束するまで、一連の反復が実行される。強結合された区画の近似プレビュー解が導入されて、収束に必要な反復の数を減少させる。これらプレビュー解は、シミュレーションがローカルおよびグローバル両方の結合の効果を減少させ始める前に導入される。波形が一旦収束すれば、シミュレーションは解を決定している。下で説明するように、近似の導入によって、波形が収束するのに必要な計算時間の量が減少し、ローカルおよびグローバル両方の強結合が勘案される。
【0019】
一般的に、大きなシミュレーションをより小さい区画へと分割することが有利である。より小さい区画はより容易に並列化可能であり、その場合シミュレーションに必要な時間が短縮される。加えて、より小さい区画であれば必要な全体の計算も少なくなる。一般的に、シミュレーションは各区画間で波形を交換することによって並列化される。波形は、特定の区画の出力および入力を表わす。波形は、交換されている波形が或る共通の値に一旦近づけば収束し、結果として解が得られる。2つの区画の間での強結合は、収束に必要な反復の数(または2つの区画間の波形の交換)を増加させる場合がある。
【0020】
従来技術の実現では、ローカルな強結合を効果的に扱うことができるのみであった。以下の各例を用いて示すように、区画のシミュレーションが始まる前に複合近似(または「プレビューア」)をシミュレーション反復に導入することによって、ローカルおよびグローバル両方の結合の効果は大幅に減少される。その結果、より小さい区画を用いることができる一方、交換される波形はより速やかに収束する。その結果として、シミュレーション時間は大幅に短縮されるが、それはより多くの区画に伴って並列化が大きくなり、より小さい区画であれば必要な計算が少なくなり、強結合の効果の減少の結果、収束に必要な反復が少なくなるからである。
【0021】
回路シミュレーションについて詳細に述べるが、その他のシミュレーションもここに記載の技術から利益を享受し得ることが理解される。たとえば、生物学的、化学的および自動車工学的シミュレーションが、ネットワーク化されたnポートに関連して記述可能である。nポートは、他のシステムとネットワーク化可能な大型のシステムのうちの1区画と考えることができる。nポートに関連して記述可能なあらゆる種類のシステムが、ここに開示の技術から利益を享受することができる。たとえば、nポートは、温度、速度、力、電力などといった値を記述し得る。現在、ベリログ(Verilog)AMSといったいくつかのシミュレーション規格が、nポートに関連してさまざまなシステムを記述することが可能である。
【0022】
図2は、この発明の或る実施例が実現され得るコンピュータシステムを例示する。コンピュータシステム200は、図3に記載の、より大型のクラスタの一部であり得る。コンピュータシステム200は、コンピュータシステム200全体にわたる情報のための分配チャネルとして働くバス202を含む。バス202にはプロセッサ204が結合される。プロセッサ204は、インテル(Intel)およびモトローラ(Motorola)で製造されたものを含む(ただしこれに限定されず)任意の好適なプロセッサであり得る。プロセッサ204はまた、多数のプロセッサを含み得る。バス202にはさらにメモリ206が結合される。メモリ206は、ランダムアクセスメモリ(RAM)、読出専用メモリ(ROM)、フラッシュメモリなどを含み得る。基本入出力ユニット208は、キーボード、マウスなどといったいくつかの入力源からの入力を受け、ディスプレイ、スピーカなどといった出力装置に対して出力する。記憶装置210は、磁気または光学記憶装置、たとえばハードドライブまたはコンパクトディスク読出専用メモリ(CD−ROM)を含むあらゆる種類の永久または一時記憶装置を含み得る。オペレーティングシステム(OS)212のコピーが記憶装置210に記憶され得る。OS212は、コンピュータシステム200を動作させるために必要なソフトウェアを含み、リナックス(Linux)などといったユニックス(Unix(登録商標))派生品であり得る。OS212は、マイクロソフト・ウィンドウズ(登録商標)(Microsoft Windows(登録商標))またはマッキントッシュ(Macintosh)OSといったその他入手できるどのOSでもよいことが理解される。ネットワークアダプタ214によって、コンピュータシステム200を、接続部216を介してクラスタ内の他のシステムおよびインターネットといった他のネットワークと接続する。コンピュータシステム200は、単にこの発明の実現に用いられ得るコンピュータシステムの一例であり、その他あらゆる適当な構成を用いてもよいことが理解される。
【0023】
図3は、この発明の或る実施例に従うコンピュータシステム300のクラスタを例示する。いくつかのコンピュータシステム200が、中央スイッチまたはルータ302を伴うピア・ツー・ピア構成を用いて一緒にネットワーク化され得る。これに代えて、ネットワーク化されたシステム300内のコンピュータシステム200の1つは中央サーバであり得る。この実現例を用いて、いくつかの安価なコンピュータシステム200をネットワーク化してクラスタ300とすることによって、並列化された問題を解くための強力なシステムを提供することができる。
【0024】
図4は、この発明の一実施例に従う、nポートまたは回路を含むシステムを区画化してシミュレーションを実行するためのプロセスを記述するフローチャートである。プロセス400は、シミュレートされるべき大きなシステムを、システム内並列の方法で用いられるべき小さい区画へと分割することを記載している。下で述べるように、システム全体をより小さなブロックへと分割することによって、各々の区画についてのノードの数Nは減少し、その結果、必要な計算の総数は減少する。この計算は、収束に必要な波形反復の数だけの、各々の区画の波形シミュレーションの実行からなる。
【0025】
大きな区画、または多数の未知のノード変数を有する区画は、典型的に小さな区画よりも波形シミュレーション中により多くの計算を必要とする。信号完全性効果のない最も純粋なデジタル回路の場合、一時点あたりの計算コストは、ノードの数Nと比例して、およそNのα乗となり、ここでαは1.4から1.6の範囲である。しかしながら、電力格子メッシュといった信号完全性効果が含まれる場合、αは1.8から2.4の範囲となり得る。加えて、より大きな回路の場合、シミュレーションにおける時点の数は、より高い全体の活動性のため大きくなる。総合的に、これらの効果は、収束レートおよびオーバーヘッドが悪影響を受けない限り、より小さい区画の実行を極めて有利としている。
【0026】
一般的に、回路が有するノードまたは変数Nが少なくなるのに伴い、1タイムポイントあたりに必要とされる計算は少なくなる。たとえば、α=2のシステムにおいては、1000ノードを有する区画は、波形において1タイムポイントあたり最大100万の浮動小数点演算を必要とする。一方、1000ノード回路が各々100ノードの10個の小さい回路へと分割される場合、これら10個の小さい回路の各々は、1タイムポイントあたり最大わずか1万の浮動小数点演算を必要とし、すなわち1タイムポイントあたり合計で最大10万の演算となる。加えて、より大きな回路の場合、シミュレーション内のタイムポイントの数は、全体の活動性がより高いことから高くなる。
【0027】
強結合の効果は、システムをより小さい区画へと分割する利益に対してバランスが取られる。たとえば、一区画は、回路の要素であって、その挙動が当該回路の他の要素の挙動に大きく依存する要素、を含む回路を含み得る。区画化によってこれら強結合された区画が分割される場合、結果として得られるシミュレーションは、典型的に、収束するために多数の波形反復を必要とすることになる。その結果、収束に必要な反復の数の増大は、区画がより小さくなったことによって各々の波形反復をシミュレートするために必要な時間の減少を上回る場合がある。下に記載のプレビューアを用いた近似の導入によって、グローバルおよびローカル両方の結合の効果が減少し、収束に必要な反復の数が減少する。
【0028】
プロセス400は開始ブロック402で始まる。ブロック404にて、システム全体の、サブシステムへの初期区画化が作成される。この区画化は、システムの内在的な特性から生じる弱結合に基づいて完了される。システム全体をスキャンして、初期区画の数およびそのシミュレーション順序を決定するのが効果的である。これら区画は、内在的結合の順序でシミュレートされたときに比較的少ない反復で収束するように選択される。大きな初期区画が内部の強結合の結果である。上述のように、より大きい区画は、各々の波形シミュレーションにつきはるかに長い計算時間を必要とする。より長い時間に伴い、コンピュータ負荷におけるバランスの崩れが生じて並列化が制約を受ける。ブロック406にて、さらなる並列化を必要とする順序付けられた区画が識別される。これら区画は、ブロック404にて生成された区画を調べることによって、さらに分割可能と識別される。識別された区画は、所望よりも大きい強結合された区画である。ブロック408にて、プレビューアシミュレーションが導入されて、さらなる並列化が可能となり、細かい区画化および順序が得られる。プレビューアおよびその動作については下でさらに説明するが、一般的には、プレビューアは、近似プレビュー解をもたらすために、強結合されたシステム内
に導入されることになる近似を含む。プレビューアは、シミュレータに対する解を「プレビュー」する。プレビューアは、区画のシミュレーションが始まる前に近似を生成することから、システムはローカルおよびグローバル結合の効果を減少させるが、これについては下で説明する。
【0029】
プレビューアは、さらなる分割のための最適な候補を決定する。ブロック410にて、細かい区画シミュレーションが実行され、これにはコンピュータプラットフォーム上の新たな順序におけるプレビューアシミュレーションが含まれる。この動作は、シミュレーション自体の実行である。このシミュレーションは、SPICE、ベリログAMS、または別のシミュレーションアプリケーションを用いて実行され得る。
【0030】
ブロック412にて、シミュレーションの進行が監視され、提案された分割の収束についてのテストが実行される。必要であれば、上記分割をさらに細かくすることによって、最も良いブロック組ひいては最も良いシミュレーションを生成する。
【0031】
回路シミュレーションといった分野で生じる動的なシステムのシミュレーションは、典型的にはnポートの相互接続を用いて記述される。ベリログAMSといったシミュレーション言語によって、設計者は、nポートに関連して階層的に大型のシステムを記述することが可能である。SPICEといった回路シミュレータによれば、nポート副回路に関連して階層記述が可能である。任意のn+1端子装置がnポート副回路として記述され得る。各々のnポートは、一組の微分方程式および代数方程式として内部的に記述される。ポートでの相互接続は、その結果としてキルヒホフ(Kirchoff)の電流則(KCL)またはキルヒホフの電圧則(KVL)といったさらなる制約が生じる。
【0032】
図5は、強結合されたマルチポート非線形回路を例示する。回路500は、個々のnポートとして記述され得る回路502,504を含む。回路500は、上述の区画化404の結果である。回路500は、区画としては大きすぎるものである場合があり、したがって、シミュレーションに必要な時間を増加させることになる。しかしながら、回路500はまた、強結合されているので、分割された場合には収束が遅くなりすぎることになる。大きな回路500は、予備的に2つの回路502,504に分割することができ、ここで回路502は近似可能であり、回路504は、元の回路500の残りである。
【0033】
回路502がnポートインピーダンスH1として表わされ、回路504がより大きな区画500の残りであると仮定する。回路502は、n+1端子回路とすることができ、ここでnは回路内にあるポートの数であり、回路502は、回路の残り504と共通の接地406を共有する。
【0034】
回路502の代わりに計算上コストの低い近似、たとえばH^1(なおH^などは、図6以下のようにHなどの上に^があるものを表わすこととする)を導入することによって回路500が変換される場合、収束は加速可能である。図6は、この発明の或る実施例に従う近似を含む強結合された回路600を例示する。回路600は、回路502の代わりに近似回路602を用いた回路500のプレビューアである。残りの回路504は上述のものと同じである。下に述べるように近似H^1が適当なものである限り、プレビューア回路600は、元の回路区画502H1に弱結合されることになり、プレビューア回路600および回路502の収束は、はるかに速やかに起こることになる。近似H^1は、計算上低コストとなるように選択され、その場合、プレビューア回路600のシミュレーションは、区画H2のシミュレーションおよび区画502H1のシミュレーションとほぼ同じ時間がかかる。
【0035】
シミュレーションについての波形反復を以下に記載する。
【0036】
(1) k=1;波形を初期化ΔV1k-1=0
(2) プレビューア回路600をシミュレートすることによってΔV1k-1├→{I1k,V^1k}
(3) 区画化されたスタンダロンインピーダンス回路502H1をシミュレートすることによってI1k├→V1k、こうして電圧波形ΔV1k=V1k−V^1kを与える。
【0037】
(4) ‖ΔV1k-1−ΔV1k‖>tolであれば、k=k+1、演算(2)へ戻り、他では終了する。
【0038】
値kは各々の反復につき増分される。第1の演算(1)において各変数が初期化される。
【0039】
第2の演算(2)において、ΔV1k-1├→{I1k,V^1k}が決定される。値ΔV1k-1は、実際の電圧波形と、前の反復k−1についての近似電圧波形との差に対応する。この値は回路600に入力され、シミュレーションが実行され、電流波形についての値およびこの反復についての電圧波形の近似がプレビューアを用いて決定される。第3の演算(3)において、電流波形についての決定された値が回路に入力されて、この反復についての電圧波形についての値を決定する。次に、この反復ΔV1kについての実際値および近似値間の差が決定され得る。演算(4)において、波形ΔV1k-1およびΔV1k間の差のノルムが、予め定められた許容値よりも大きい場合、反復は継続してプロセスは演算(2)に戻る。差が許容値よりも小さい場合、波形は収束しており、回路602についてのシミュレートされた値は決定されている。波形のノルムの計算およびプレビューアにおける近似の選択については下でさらに説明する。
【0040】
場合によっては、いくつかの近似を単一の区画内に導入することが必要なこともある。図7は、複数のより小さい区画へと分解された大きい区画を示す。図7に示すように、回路700は、初期の区画化から残っている大きい区画である。回路700は強結合されているため、いくつかの副回路702a〜702xに分割されており、ここでxは、m個の近似区画に等しい任意の区画数である。副回路702a〜702xは、回路700H0の残り704にすべて結合され、これは典型的に抵抗器といった単純な受動素子を含む。図8は、m個の近似区画を有する回路700についてのプレビューア回路800を示す。副回路702a〜702xの各々は、近似H^1802aからH^m802xと交換されている。残りの回路H0804は、残りの回路704と同じである。
【0041】
回路800の収束についての波形反復は以下のように進行する。
【0042】
(1) 初期化k=1。i=1,…mの場合、波形ΔVi0
(2) プレビューア800をシミュレートすることによってΔV1k-1├→{Iik,V^ik}。704−(802a…802x)。
【0043】
(3) 区画化されたスタンダロンインピーダンスマルチポート回路Vik=Hi(Iik)、i=1,…m、の各々をシミュレートすることによってIik├→Vik、こうして波形ΔVik=Vik−V^ikを与える。この演算は並列で行なわれ得る。
【0044】
(4) 任意のi=1,…mについて‖ΔVik-1−ΔVik‖>tolの場合、k=k+1であり、演算(2)に戻り、他では終了する。
【0045】
このプロセスは、図6に関して上述したプロセスと類似である。しかしながら、この場合、シミュレーションが実行されなければならないいくつかの異なる区画が存在する。値
iは各々の区画につき増分される。図9は、いくつかの異なる区画についてのシミュレーションを実行するいくつかのプロセッサを例示する。図9に示すように、第3の演算(3)は並列化可能であり、これのためには、第2の演算(2)においてプレビューアから電流波形Iikが一旦利用可能となれば別個のプロセッサ904a〜904xにおいて各々の元の区画902a〜902xのシミュレーションを実行する。他では、プロセスは図6に関して上述したものと同じである。
【0046】
上述のように、第3の演算(3)は並列化され得るが、第2の演算(2)の後に直列的に続く。複合近似の計算コストが、各々の個々の回路区画Vik=Hi(Iik)の計算コストよりも小さいときには、第2の演算(2)および第3の演算(3)のさらなる並列化が達成可能である。図10は、この発明の或る実施例に従う並列動作する複数のプロセッサを例示する。一実施例では、各々の区画が、シミュレーションのためにおよそ同じ量の計算時間を必要とするように、複数の区画が選択される。
【0047】
図10は、上述のシミュレーションプロセスを並列化する間における時系列1008に沿っての複数のプロセッサ1002,1004,1006の動作を例示する。時間tsimは、シミュレーションにおける各々の反復についての時間である。反復中のシミュレーションインターバルは時間セグメントに分割される。図10は、各々が等しい計算時間tsim/2を必要とする2つの時間セグメントを伴う例を示す。第1のプロセッサ1002は、一般にプレビューアの計算が割当てられる。第2のプロセッサ1004および第3のプロセッサ1006は、個々の区画が割当てられてこれら区画をシミュレートする。この例においては、第1のプロセッサ1002は複合近似(プレビューア)を実行し、第2のプロセッサ1004は第1の区画902aを実行し、第3のプロセッサ1006は第2の区画902bを実行する。たとえば、第1のプロセッサ1002は、反復1010aの前半の間に複合近似1012を実行する。近似1012が完了したとき、これはプロセッサ1004,1006に転送され、各々のプロセッサ1004,1006は、反復の後半の間に個々の区画をシミュレートする。換言すると、t0およびt0+tsim/2間の期間の間中、第1のプロセッサ1002はプレビューア1012を算出し、これはプロセッサ1004およびプロセッサ1006によってそれぞれシミュレーション1014およびシミュレーション1016を実行するために用いられることになる。t0+tsim/2およびt0+tsim間の期間においては、第1のプロセッサ1002は、第1の反復の後半のプレビューアシミュレーションを算出する。この時間の間中、プロセッサ1004,1006は、プロセッサ1002によって時間t0およびt0+tsim/2中に生成されたプレビューアを用いて、反復の前半についてのシミュレーションを実行する。時間t0+tsimおよびt0+1.5*tsim間に、プロセッサ1004,1006は、プロセッサ1002によって時間t0+tsim/2およびt0+tsim中に生成されたプレビューア解1022を用いてシミュレーション1018,1020を実行する。このプロセスは、シミュレーションが収束するまで継続する。
【0048】
より具体的には、シミュレーションインターバル1010の前半の終わりに、反復1010aの前半インターバルについてのポート電流波形Ii1、i=1,2がプロセッサ1002に対して利用可能となる。これら電流波形は、スタンダロン区画を実行するよう割当てられたプロセッサ1004,1006に転送される。スタンダロン区画は、前半インターバルについてのシミュレーションを開始し、一方でプロセッサ1002は、シミュレーションインターバルの後半についてのシミュレーションを実行する。プロセッサ1004,1006が時間t0+tsimでインターバルの前半のシミュレーションを完了させたとき、前半のインターバルについての区画から、プロセッサ1002で次の反復中に用いられるべき複合近似までの電圧波形Vi1、i=1,2をもたらす。これによって、プロセッサ1002は、時間t0+tsimにおいて、第2の反復についての前半のインターバルのシミュレーションを継続することができる。パイプライン化された評価によって、当該方法を
効率的に並列実行することが可能となる。
【0049】
図11および図12は、インピーダンスおよび電圧でなくアドミタンスおよび電流を用いたこの発明の或る実施例を例示する。図11は、プレビューア回路600に類似の強結合された回路のためのプレビューア1100を例示する。回路1100は、近似回路1102および回路の残り1104を含む。図12は、回路800に類似の多数の別個の区画を含む回路1200を例示する。回路1200は、複数の区画1202a〜1202xおよび回路の残り1204を含む。上述のインピーダンスおよび電圧nポートと類似して、波形反復は以下のように進行する。
【0050】
(1) 初期化k=1。i=1,…mの場合、波形ΔIi0
(2) 上述の図11に示すようにプレビューアシステム0−1’…m’をシミュレートすることによってΔIik-1├→{Vik,I^ik}。
【0051】
(3) 区画化されたスタンダロンアドミタンスマルチポート回路Iik=Hi(Vik)、i=1,…mの各々をシミュレートすることによってVik├→Iik、これによって波形ΔIik=Iik−I^ikを与える。この演算は並列で実行可能である。
【0052】
(4) 任意のi=1,…mの場合に‖ΔIik-i−ΔIik‖>tolである場合、k=k+1であり、演算(2)に戻り、他では終了する。
【0053】
ここで用いられる場合、最初の区画1202aについてはi=1であり、最後の区画1202xについてはi=mである。上と同様に、波形ΔIikは、電流の実際の算出値と近似値との差を測定する。第4の演算(4)において、前の繰返しと現在の繰返しとの波形ΔIik間の差のノルムが許容値tol未満であれば、反復は収束しており、この区画につてのシミュレーションは完了している。図8および図12においては、任意の1つのnポートはハイブリッドマルチポートであり得る。対応の入力および出力は、電圧および電流のハイブリッド(組合せ)である。波形反復は、回路についての適当な入力および出力波形のために変更が加えられる。
【0054】
この手法にはいくつかの利点がある。一般に強結合された非線形のマルチポートシステムが考慮されているため、グローバルおよびローカル両方のフィードバック状況がともに対処される。以前の方法では、単一の端子での負荷から生じるローカルフィードバックに対してグローバルフィードバックとは別個に対処を図っていた。これら先行技術の方法では、MOS回路における特定の単方向構造を利用していた。強いローカルな両方向結合が存在する場合、これは収束上の困難さを引起していた。先行技術の方法にはまた、強いグローバル結合が存在する場合に収束が遅いという問題があった。
【0055】
本方法は、非線形波形をバナッハ空間での非線形波形に写像するあらゆるシミュレーションに適用される。対応のバナッハ空間ノルムが、反復中に収束テストにおいてかつ下記の近似のための増分演算子利得を計算するために用いられる。したがって、その利益を引出すためにマルチポートシステムにおける特定の構造は用いない。本方法から引出される利益に加えて、下層ドメインの構造を利用するあらゆるシミュレータが、構造を利用するために使用され得る。たとえば、SPICEといった回路シミュレータにおいては、下層の回路式のスパーシティ構造はシミュレータ自体によって利用される。個々の構成要素のシミュレーションにSPICEを用いることによって、回路式のスパーシティ構造の利用が可能となる。
【0056】
複合近似は、多種多様な手法を用いてシミュレーション可能である。たとえば、MOS回路シミュレータにおいては、イベント駆動シミュレーションにおいてテーブル駆動のピ
ースワイズ近似モデルを用いて複合近似が構成可能である。このようなシミュレータは、高速タイミングシミュレータとも称され、SPICEよりも10〜1000倍の速度で近似波形をもたらす。しかしながら、近似波形はわずか5〜10%の範囲で正確なものである。近似シミュレーションの別の例は、MOR(Model Order Reduction)を用いるというものである。大型のRLCネットワークについては、MORは、最大10%のエラーを導入することと引き換えに数桁速い計算をもたらす。
【0057】
近似が収束のための条件を満たす限りあらゆる特定ドメインのシミュレータおよび特定ドメインの近似を用いることができる。注目すべきことは、比較的粗い近似が速い収束に繋がることである。
【0058】
以下の記載は、上述の各プロセスで用いられることになる近似を選択するプロセスを説明するものである。強結合されたシステムについてのプレビューアは、以下の特性を有する複合近似を含む。
【0059】
(1) プレビューアは、各々の元の構成要素nポートを正確にシミュレートするために必要とされる時間に相当する時間内にそれ自身のシミュレータでシミュレート可能である。これは、図10におけるパイプライン化されたプロセスに関して既に述べられたものである。
【0060】
(2) 残りの回路H0は無視できるほど小さなものであり、典型的に抵抗器またはノードといった受動素子を含む。
【0061】
(3) 各々の近似された構成要素nポートH^iは、Hiに対してエラーテストを満たす。これはHi−H^iの増分演算子利得についてのテストである。
【0062】
近似のための候補には、簡略化テーブルルックアップモデルでのシミュレーション、スイッチレベルシミュレーション、マクロモデル、および低次縮約モデルが含まれる。これら近似は、再利用される構成要素についての前特徴付けを含み得る。これに加えて、近似の品質とその実行時間速度との間の兼ね合いがある。前特徴付け時には、HiとH^iとの間のエラーは以下を用いて計算される。
【0063】
u1,u2,…,ulを、H^iの当てはめに用いられる別個の入力ベクトルとする。
【0064】
y1,y2,…,ylを、入力yj=Hi(uj)でのHiの実行からの出力ベクトルとする。
【0065】
y^1,y^2,…,y^lを、入力y^j=H^i(uj)でのH^iの実行からの出力ベクトルとする。
【0066】
ここでは、ujは入力波形値を表わし、yj=Hi(uj)は、入力ujが与えられた場合の区画Hiの実際の波形出力を表わし、y^j=H^i(uj)は、入力ujが与えられた場合の区画についての近似出力を表わす。近似についてのエラーを決定するためには、増分演算子利得の推定値が計算される。
【0067】
【数3】
【0068】
ここで入力または出力ベクトル波形のノルムは
【0069】
【数4】
【0070】
である。任意の所与の時間tにて、y(t)は電圧または電流変数のベクトルである。|y(t)|は、順序付けられた実際のn個の要素からなる集合の線形空間におけるノルムを表わす。たとえば、y(t)が4つの電圧から構成される場合、y(t)=[V1(t),V2(t),V3(t),V4(t)]であり、その場合
|y(t)|=max[abs(V1(t)),abs(V2(t)),abs(V3(t)),abs(V4(t))]、
または代替的に|y(t)|=(V12(t)+V22(t)+V32(t)+V42(t))1/2である。
【0071】
【数5】
【0072】
後の記載は、ここに記載された技術のいくつかの例を説明する。これら記載は例であると理解され、さらに、記載の発明については他のいくつかの可能な実現例および実施例が存在することが理解される。
【0073】
図13〜17は、この発明の或る実施例に従う両方向ローカル結合を呈する回路のシミュレーションを例示する。図13は、両方向ローカル結合を呈する回路を例示する。回路1300は、非線形要素G2 1302を含む強結合された回路であり、これは2つの並列のダイオード方程式によって記述され得る。
【0074】
【数6】
【0075】
回路1300は、H1と表わす第1の区画1304と回路の残り1306とに区画化されることになる。回路1300はさらに、3つのキャパシタC1 1308、C2 1310およびC3 1312、線形要素G1 1314および電流源J 1316を含む。
【0076】
標準ノード分析(キルヒホフの電流則を用いる)からは、2つの結合された微分方程式が与えられる。
【0077】
【数7】
【0078】
ガウス・ザイデル反復を用いてこの回路を複数の区画へと分解するための先行技術の方法は、結果として以下の式を与える。
【0079】
【数8】
【0080】
【数9】
【0081】
結合キャパシタC3 1310が、他のキャパシタC1 1308およびC2 1310と比較して大きい静電容量を有するとき、収束のレートは遅くなる。図14は、標準的なガウス・ザイデル分解を用いた遅い収束を例示する。グラフ1400は、x軸1402に沿ってプロットされた時間およびy軸1404に沿った電圧を有する。プロット線1406の各々は、回路1300についての実際の値と比較した先行技術のガウス・ザイデル分解を用いたシミュレーションにおける各々の漸進反復についてのエラーを例示する。グラフ1400は、10回の反復を通じて遅く収束するシミュレーションを示す。プロット線1406aは、1回目の反復についてのエラーを示し、プロット線1406jは、10回目の反復についてのエラーを示す。シミュレーションは正しい解へ向けてゆっくりと収束するが、10回目の反復の後でもエラーはいくつかのタイムポイントで0.6Vを超過する。このような低い収束レートは実際の場面は許容不可能であることは明らかである。先行技術の方法を用いた発見的区画化アルゴリズムでは回路1300を区画化しないであ
ろう。しかしながら、大型の回路でこれを行なうことは、並列計算のために不十分な粒度に繋がる。
【0082】
図15は、非線形要素G2 1302についての近似を例示する。グラフ1500は、x軸1502上の電圧対y軸1504上の電流のプロットを示す。完全な、シミュレートされたプロット1506を、グラフ1500に示す。近似値はプロット1508を用いて示される。近似値は、ここに記載の技術を用いて、たとえば粗いピースワイズリニアテーブルルックアップを用いて得られる。
【0083】
図16は、非線形要素G2のピースワイズリニア近似1508を含む回路1300を例示する。プレビューア回路1600は、回路1300であって、元の非線形要素1302の代わりに近似1602を含むものである。図5,6に記載の区画1304の代わりに区画1604が示されている。
【0084】
図17は、プレビューア回路1600を用いた高速収束を例示するプロットである。プロット1500と同様、プロット1700は、x軸1702に沿った時間およびy軸1704に沿った電圧を示す。プロット内の電圧は、回路1300によって生成された実際の出力からのエラーである。なお、y軸1704の目盛は、上述のy軸1504の目盛よりもはるかに小さく、1回目の反復1706aについても10回目の反復1506jについてのエラーよりもエラーがはるかに小さいことを示している。3回目の反復1706cまでに、エラーは極めて小さくなっており、シミュレーションは、回路1300についての実際の算出値に極めて近づいている。その結果、ここに記載のこの発明の各実施例を用いて、反復は近似を用いないよりもはるかに速やかに収束する。
【0085】
図18〜22は、この発明の一実施例に従う単方向グローバルおよびローカル両方向結合ならびにそのシミュレーションを例示する。図18は、四次フィルタ回路1800を例示する。回路1800は、3つの演算増幅器の段1802,1804,1806を含む。入力電圧から出力電圧への理想化されたフィルタ転送機能は、振動応答を伴う二次である。実際の応答は、演算増幅器におけるスルーレート(slew rate)およびクランピングといった非線形の効果を有する。加えて、より高次の寄生極およびゼロは、線形化された転送機能に存在する。各々の演算増幅器段1802,1804または1806を副回路とみなすと、機能ブロックの単方向入出力信号流れを横切るのに伴い振動応答を生じさせる強いグローバル結合が存在することが明らかである。グローバル結合に加えて、各々すべての接続ノードにはローカルな両方向負荷効果が存在する。グローバル結合は、高速で作用しかつ強いものである。
【0086】
図19は、ガウス・ザイデル分解を用いて区画化された回路1800を例示する。分解1900は、複数の順序付けられた区画1902,1904,1906に分割された回路1800を示す。これら区画は、公知のガウス・ザイデル分解を用いて作り出されている。
【0087】
図20は、ガウス・ザイデル分解を用いた回路1800のシミュレーションの収束を示すプロットである。グラフ2000は、x軸2002に沿った時間およびy軸2004に沿った電圧を示す。プロット2006は、回路1800の実際の応答を示す。プロット2008は、ガウス・ザイデル分解1900を用いた5回の反復後の出力を示す。プロット2010は、ガウス・ザイデル分解1900を用いた10回の反復後の出力を示す。波形は極めて遅く収束することが見て取れる。
【0088】
この発明の或る実施例に従うと、回路1800は、図7,8,9の回路700が分解されるのと同じ態様で分解され得る。図21は、この発明の或る実施例に従う回路1800
の分解からのプレビューアを例示する。副回路段H11802、H21804およびH31806の各々は、非線形2ポートインピーダンス演算子として見られる。残りの回路H02108は、相互接続ワイヤを伴うノードのみを含む。各々の段2102,2104,2106の近似は、完全な非線形演算増幅器の代わりに等価の理想電圧制御電圧源を用いることによって達成される。
【0089】
図22は、この発明の或る実施例に従い分解された回路1800の収束を例示するグラフである。グラフ2200は、x軸2202における時間およびy軸2204における出力電圧を示す。プロット2206は完全なシミュレーションである。プロット2208は1回目の反復後の出力であり、プロット2210は2回目の反復後の出力である。図7,8,9に示す分解を用いたときにシミュレーションは極めて速やかに収束することが見て取れる。
【0090】
図23〜26は、この発明の或る実施例に従う両方向ローカルおよびグローバル結合の非線形メッシュ例を示す。図23Aは、非線形二次元メッシュ2300を例示する。図23Bおよび23Cは、メッシュ2300の分解図を示す。メッシュ2300は、集積回路(IC)内の電力格子であり得る。メッシュ2300は、4つの隣接するノードに接続する各々の内部ノード2304について4つの抵抗器2302を含む。各々のノード2304にて、キャパシタ2306およびダイオード2308が接地2310に接続される。ダイオード2308は逆バイアスされる。メッシュコーナは,4つの接続抵抗器2302を介して供給ノードに接続される。メッシュノードは、タイル2312に分割される。図23Aに示すように、メッシュ2300は3×2タイルの格子を含む。各々のタイル2312は、高インピーダンス電流源2314が取付けられる中央ノード2304を含む。
【0091】
図23Cに示すように、タイル2312は、接続抵抗器2316を介して接続される。これら接続抵抗器2316は、残りの回路H0を構成でき、各々のタイル2312は、図7,8,9におけるような区画Hiを含み得る。メッシュ2300は、この発明の或る実施例に従いこの態様で分解され得る。
【0092】
メッシュ2300についての近似H^iは、Hiの線形化されたインピーダンスの低次縮約モデルを用いて作り出されている。その結果得られるプレビューアは、効率的にシミュレート可能な低次の線形システムである。
【0093】
図24は、回路2300のフルレファレンスシミュレーションから、およびそのフルオーダ線形近似からのタイル2312についての中央ノード電圧を示すグラフ2400を例示する。x軸2402は時間を示し、y軸2404は出力の電圧を示す。プロット2406はフルレファレンスシミュレーションを示し、プロット2408はフルオーダ線形近似を示す。2つのプロット2406,2408間の差は、ダイオード2308の非線形性から生じる。
【0094】
図25は、タイル2312の中央ノード電圧についてのフルレファレンスシステムおよび近似の低次プレビューア応答間の差を例示する。ここでもまた、x軸2502は時間を示し、y軸2504は電圧を示す。プロット2506では、近似と完全な参照との差がかなりあることが示される。
【0095】
図26は、プレビューアベースの近似の或る実施例を用いた3回の反復後のシミュレーションの電圧出力のエラーを示すグラフである。グラフ2600は、時間を示すx軸2602および電圧を示すy軸2604を含む。プロット2606では、わずか3回の反復後にエラーは受け入れられる許容値以内に十分にあることが示される。これとは対照的に、標準的なガウス・ザイデル分解を用いた場合、収束は50回超の反復を要する。
【0096】
この発明の各実施例は回路シミュレーションには限定されないことが理解される。たとえば、化学的シミュレーション、生物学的シミュレーション、自動車工学的シミュレーションなどといった他のいくつかの種類のシミュレーションが、ここに記載されたシステムおよび技術を用いて実行され得る。これら技術は、特定の用途に対して適合され得る。
【0097】
この発明は、その特定の例示的な実施例を参照して記述してある。しかしながら、この開示の利益を有する者にとっては、この発明のより広い意味および範囲から逸脱することなしにさまざまな変形や変更が上記各実施例に対して可能であることが明らかであろう。したがって、明細書および図面は、制限的でなく例示的な意味で考えられるべきである。
【図面の簡単な説明】
【0098】
【図1】初期値問題を用いてシミュレーションに対する解を決定するためのプロセスを例示するフローチャートである。
【図2】この発明の或る実施例が実現され得るコンピュータシステムを例示する図である。
【図3】この発明の或る実施例に従うコンピュータシステムのクラスタを例示する図である。
【図4】この発明の一実施例に従いシステムを区画化してシミュレーションを実行するためのプロセスを説明するフローチャートである。
【図5】強結合されたマルチポート非線形回路を例示する図である。
【図6】この発明の或る実施例に従う近似を含む強結合された回路を例示する図である。
【図7】複数の小さな区画へと分解された大きな区画を例示する図である。
【図8】m個の近似区画を伴う回路700についてのプレビューア回路を例示する図である。
【図9】複数の異なる区画についてのシミュレーションを実行する複数のプロセッサを例示する図である。
【図10】この発明の或る実施例に従う並列実行される複数のプロセッサを例示する図である。
【図11】プレビューア回路600に類似の強結合された回路についてのプレビューアを例示する図である。
【図12】回路800に類似の、多数の別個の区画を含む回路を例示する図である。
【図13】両方向ローカル結合を呈する回路を例示する図である。
【図14】標準ガウス・ザイデル分解を用いた遅い収束を例示する図である。
【図15】非線形要素G2についての近似を例示する図である。
【図16】非線形要素G2のピースワイズリニア近似を含む回路を例示する図である。
【図17】回路の高速収束を例示するプロットである。
【図18】四次フィルタ回路を例示する図である。
【図19】ガウス・ザイデル分解を用いて区画化された回路を例示する図である。
【図20】ガウス・ザイデル分解を用いた回路のシミュレーションの収束を示すプロットである。
【図21】この発明の或る実施例に従う回路の分解からのプレビューアを例示する図である。
【図22】この発明の或る実施例に従い分解された回路の収束を例示するグラフである。
【図23A】非線形二次元メッシュを例示する図である。
【図23B】メッシュの一例の分解図である。
【図23C】メッシュの一例の分解図である。
【図24】回路のフルレファレンスシミュレーションから、およびフルオーダ線形近似からのタイルについての中央ノード電圧を示すグラフである。
【図25】タイルの中央ノード電圧についてのフルレファレンスシステムおよび近似の低次プレビューア応答間の差を例示する図である。
【図26】プレビューアベースの近似の或る実施例を用いた3回の反復後のシミュレーションの電圧出力のエラーを示すグラフである。
【特許請求の範囲】
【請求項1】
システムを区画化するステップと、
上記システムに、区画の近似シミュレーションを導入するステップと、
上記近似シミュレーションを用いて上記システムをシミュレートするステップとを含む、方法。
【請求項2】
上記近似シミュレーションを含むプレビューアを生成するステップをさらに含む、請求項1に記載の方法。
【請求項3】
上記システムを区画化するステップは、
上記システムの内在的な特性に基づいて弱結合を識別するステップと、
上記弱結合に基づいて上記システムを上記区画へと分割するステップとを含む、請求項1に記載の方法。
【請求項4】
上記シミュレートするステップは、上記導入するステップの後に行なわれる、請求項1に記載の方法。
【請求項5】
上記プレビューアを生成するステップは、ルックアップテーブルからピースワイズリニア近似を生成するステップを含む、請求項2に記載の方法。
【請求項6】
上記シミュレートするステップおよび上記導入するステップは、ネットワーク化された機械において並列実行される、請求項1に記載の方法。
【請求項7】
実行された際に機械が方法を実行することを引起す実行可能なプログラムコードを記憶した機械読取可能媒体であって、上記方法は、
システムを区画化するステップと、
上記システムに、区画の近似シミュレーションを導入するステップと、
上記近似シミュレーションを用いて上記システムをシミュレートするステップとを含む、機械読取可能媒体。
【請求項8】
上記近似シミュレーションを含むプレビューアを生成するステップをさらに含む、請求項7に記載の機械読取可能媒体。
【請求項9】
上記システムを区画化するステップは、
上記システムの内在的な特性に基づいて弱結合を識別するステップと、
上記弱結合に基づいて上記システムを上記区画へと分割するステップとを含む、請求項7に記載の機械読取可能媒体。
【請求項10】
上記シミュレートするステップは、上記導入するステップの後に行なわれる、請求項7に記載の機械読取可能媒体。
【請求項11】
上記プレビューアを生成するステップは、ルックアップテーブルからピースワイズリニア近似を生成するステップを含む、請求項8に記載の機械読取可能媒体。
【請求項12】
上記シミュレートするステップおよび上記導入するステップは、ネットワーク化された機械において並列実行される、請求項7に記載の機械読取可能媒体。
【請求項13】
デジタル処理システムであって、
表示装置に結合されたデジタルプロセッサと、
前記デジタルプロセッサに結合され、シミュレーションのためのシステムを受けるメモリとを備え、前記プロセッサは、
システムを区画化し、
上記システムに、区画の近似シミュレーションを導入し、かつ
上記近似シミュレーションを用いて上記システムをシミュレートする、デジタル処理システム。
【請求項14】
上記近似シミュレーションを含むプレビューアを生成する上記プロセッサをさらに含む、請求項13に記載のデジタル処理システム。
【請求項15】
システムを区画化することは、
上記システムの内在的な特性に基づいて弱結合を識別することと、
上記弱結合に基づいて上記システムを上記区画へと分割することとを含む、請求項13に記載のデジタル処理システム。
【請求項16】
上記シミュレートは、上記導入の後に行なわれる、請求項13に記載のデジタル処理システム。
【請求項17】
プレビューアを生成することは、ルックアップテーブルからピースワイズリニア近似を生成することを含む、請求項14に記載のデジタル処理システム。
【請求項18】
上記シミュレートおよび上記導入は、ネットワーク化された機械において並列実行される、請求項13に記載のデジタル処理システム。
【請求項1】
システムを区画化するステップと、
上記システムに、区画の近似シミュレーションを導入するステップと、
上記近似シミュレーションを用いて上記システムをシミュレートするステップとを含む、方法。
【請求項2】
上記近似シミュレーションを含むプレビューアを生成するステップをさらに含む、請求項1に記載の方法。
【請求項3】
上記システムを区画化するステップは、
上記システムの内在的な特性に基づいて弱結合を識別するステップと、
上記弱結合に基づいて上記システムを上記区画へと分割するステップとを含む、請求項1に記載の方法。
【請求項4】
上記シミュレートするステップは、上記導入するステップの後に行なわれる、請求項1に記載の方法。
【請求項5】
上記プレビューアを生成するステップは、ルックアップテーブルからピースワイズリニア近似を生成するステップを含む、請求項2に記載の方法。
【請求項6】
上記シミュレートするステップおよび上記導入するステップは、ネットワーク化された機械において並列実行される、請求項1に記載の方法。
【請求項7】
実行された際に機械が方法を実行することを引起す実行可能なプログラムコードを記憶した機械読取可能媒体であって、上記方法は、
システムを区画化するステップと、
上記システムに、区画の近似シミュレーションを導入するステップと、
上記近似シミュレーションを用いて上記システムをシミュレートするステップとを含む、機械読取可能媒体。
【請求項8】
上記近似シミュレーションを含むプレビューアを生成するステップをさらに含む、請求項7に記載の機械読取可能媒体。
【請求項9】
上記システムを区画化するステップは、
上記システムの内在的な特性に基づいて弱結合を識別するステップと、
上記弱結合に基づいて上記システムを上記区画へと分割するステップとを含む、請求項7に記載の機械読取可能媒体。
【請求項10】
上記シミュレートするステップは、上記導入するステップの後に行なわれる、請求項7に記載の機械読取可能媒体。
【請求項11】
上記プレビューアを生成するステップは、ルックアップテーブルからピースワイズリニア近似を生成するステップを含む、請求項8に記載の機械読取可能媒体。
【請求項12】
上記シミュレートするステップおよび上記導入するステップは、ネットワーク化された機械において並列実行される、請求項7に記載の機械読取可能媒体。
【請求項13】
デジタル処理システムであって、
表示装置に結合されたデジタルプロセッサと、
前記デジタルプロセッサに結合され、シミュレーションのためのシステムを受けるメモリとを備え、前記プロセッサは、
システムを区画化し、
上記システムに、区画の近似シミュレーションを導入し、かつ
上記近似シミュレーションを用いて上記システムをシミュレートする、デジタル処理システム。
【請求項14】
上記近似シミュレーションを含むプレビューアを生成する上記プロセッサをさらに含む、請求項13に記載のデジタル処理システム。
【請求項15】
システムを区画化することは、
上記システムの内在的な特性に基づいて弱結合を識別することと、
上記弱結合に基づいて上記システムを上記区画へと分割することとを含む、請求項13に記載のデジタル処理システム。
【請求項16】
上記シミュレートは、上記導入の後に行なわれる、請求項13に記載のデジタル処理システム。
【請求項17】
プレビューアを生成することは、ルックアップテーブルからピースワイズリニア近似を生成することを含む、請求項14に記載のデジタル処理システム。
【請求項18】
上記シミュレートおよび上記導入は、ネットワーク化された機械において並列実行される、請求項13に記載のデジタル処理システム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23A】
【図23B】
【図23C】
【図24】
【図25】
【図26】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23A】
【図23B】
【図23C】
【図24】
【図25】
【図26】
【公表番号】特表2007−536602(P2007−536602A)
【公表日】平成19年12月13日(2007.12.13)
【国際特許分類】
【出願番号】特願2006−533391(P2006−533391)
【出願日】平成16年5月24日(2004.5.24)
【国際出願番号】PCT/US2004/016384
【国際公開番号】WO2004/107828
【国際公開日】平成16年12月9日(2004.12.9)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Linux
2.Macintosh
3.リナックス
4.マッキントッシュ
【出願人】(505431282)ズームシス・インコーポレイテッド (2)
【氏名又は名称原語表記】XOOMSYS,INC.
【Fターム(参考)】
【公表日】平成19年12月13日(2007.12.13)
【国際特許分類】
【出願日】平成16年5月24日(2004.5.24)
【国際出願番号】PCT/US2004/016384
【国際公開番号】WO2004/107828
【国際公開日】平成16年12月9日(2004.12.9)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Linux
2.Macintosh
3.リナックス
4.マッキントッシュ
【出願人】(505431282)ズームシス・インコーポレイテッド (2)
【氏名又は名称原語表記】XOOMSYS,INC.
【Fターム(参考)】
[ Back to top ]