(57)【要約】  この発明の実施形態に従うと、シミュレーションを実施するためのシステムおよび方法が提供される。この方法は、システム並列性を用いることにより、大きな問題をいくつかの小さなパーティションに分解する。これらのパーティション間で交換される波形が収束するまで、一連の反復が実施される。強結合されたパーティションのプレビュー近似解が導入されて、収束に必要な反復の数が減少する。これらのプレビュー近似解は、シミュレーションが生じる前に導入される。波形が一旦収束すると、シミュレーションは解を得る。
2009512910.tif 000002
【特許請求の範囲】
【請求項１】
システムをシミュレートするための方法であって、
前記システムをシミュレートすることに関する１つ以上の見積りコストに基づき、前記システムを第１の組のパーティションに自動的に分解するステップと、
前記システムのシミュレーションを実施するステップとを含み、前記第１の組のパーティションに対応する前記システムの部分は、相対的に精度の低いシミュレーションメカニズムを用いてシミュレートされ、前記方法はさらに、
第２の組のシミュレーションを実施するステップを含み、前記第２の組のシミュレーションを実施する前記ステップの間に、前記第１の組のパーティション内の各パーティションは、相対的に精度の高いシミュレーションメカニズムを用いてシミュレートされる、方法。
【請求項２】
前記第２の組のシミュレーションの性能を監視するステップと、
前記第２の組のシミュレーションの１つ以上の性能が、予め定められた量を上回る量だけ、前記１つ以上の見積りコストから外れることを検出することに応答して、以下のステップを実施するステップとをさらに含み、前記以下のステップは、
第２の組のパーティションを生じるように前記システムをさらに分解するステップと、
前記システムのシミュレーションを実施するステップとを含み、前記第２の組のパーティションに対応する前記システムの部分は、相対的に精度の低いシミュレーションメカニズムを用いてシミュレートされ、前記以下のステップはさらに、
第３の組のシミュレーションを実施するステップを含み、前記第３の組のシミュレーションを実施する前記ステップの間に、前記第２の組のパーティション内の各パーティションは、相対的に精度の高いシミュレーションメカニズムを用いてシミュレートされる、請求項１に記載の方法。
【請求項３】
自動的に分解する前記ステップは、前記システムをシミュレートするために使用されるべきシミュレータに関連するライセンス供与情報に少なくとも部分的に基づいて実施される、請求項１に記載の方法。
【請求項４】
システムをシミュレートするための方法であって、
前記システムを複数のパーティションに分解するステップを含み、
第１の組の前記パーティションは、第１の種類のシミュレータでシミュレータされ得るが第２の種類のシミュレータではシミュレートされ得ない第１の種類の技術に対応し、
第２の組の前記パーティションは、前記第２の種類のシミュレータでシミュレートされ得るが前記第１の種類のシミュレータではシミュレートされ得ない第２の種類の技術に対応し、前記方法はさらに、
以下のステップを実施することにより前記システムをシミュレートするステップを含み、前記以下のステップは、
前記第１の種類のシミュレータを用いて前記第１の組のパーティション内の各パーティションをシミュレートするステップと、
前記第２の種類のシミュレータを用いて前記第２の組のパーティション内の各パーティションをシミュレートするステップとを含む、方法。
【請求項５】
前記システムをシミュレートする前記ステップは、
前記システムのシミュレーションを実施するステップを含み、前記複数のパーティションに対応する前記システムの部分は、相対的に精度の低いシミュレーションメカニズムを用いてシミュレートされ、前記システムをシミュレートする前記ステップはさらに、
第２の組のシミュレーションを実施するステップを含み、前記第２の組のシミュレーシ
ョンを実施する前記ステップの間に、前記複数のパーティション内の各パーティションは、相対的に精度の高いシミュレーションメカニズムを用いてシミュレートされ、
前記第２の組のシミュレーションを実施する前記ステップは、
前記第１の種類のシミュレータを用いて前記第１の組のパーティション内の各パーティションをシミュレートするステップと、
前記第２の種類のシミュレータを用いて前記第２の組のパーティション内の各パーティションをシミュレートするステップとを含む、請求項４に記載の方法。
【請求項６】
システムをシミュレートするための方法であって、
前記システムをシミュレートするために使用されるべきシミュレータに関連するライセンス供与情報を自動的に検出するステップと、
前記ライセンス供与情報に少なくとも部分的に基づいて前記システムをシミュレートするステップとを含む、方法。
【請求項７】
前記ライセンス供与情報に少なくとも部分的に基づき、前記システムをシミュレートする前記ステップは、
前記システムをシミュレートするために使用されるべきシミュレータに関連するライセンス供与情報に少なくとも部分的に基づき、前記システムをパーティションに自動的に分解するステップと、
前記パーティションを用いて前記システムをシミュレートするステップとを含む、請求項６に記載の方法。
【請求項８】
シミュレートされるべきシステムのパーティションを識別するステップと、
シミュレーションジョブを作成するステップとを含み、
前記シミュレーションジョブは、他のシミュレーションジョブからの信号を刺激ファイルとして含み、
前記刺激ファイルは、
既に遂行されたシミュレーションジョブの出力を収集し、
前記刺激を計算し、
前記刺激を書出すことにより作成される、方法。
【請求項９】
前記刺激は、区分的線形信号として書出される、請求項８に記載の方法。
【請求項１０】
遂行されるべきシミュレーションジョブの明細と、１つのシミュレーションジョブの、他のシミュレーションジョブからの出力に対する依存度とを含む実行プランを生成するステップをさらに含む、請求項８に記載の方法。
【請求項１１】
前記実行プランは、シミュレーションジョブ間のデータ従属性を示すための有向非巡回グラフを含む、請求項１０に記載の方法。
【請求項１２】
実行プランを生成する前記ステップは、多数の処理ユニットで併行して実行されるタスクに分割される、請求項１０に記載の方法。
【請求項１３】
シミュレーションのランタイムスケジューリングを実施するための方法であって、
必要とされる入力の利用可能性に基づき、遂行される準備が整ったすべてのシミュレーションジョブを、所定のいずれの時間においても識別するステップと、
実行プランにおいて遂行される準備が整ったシミュレーションジョブを、実行キューに追加するステップと、
その時に、シミュレーションライセンスを用いて稼動されるように利用可能なすべてのプロセッサを識別するステップと、
前記実行キュー内の次のシミュレーションジョブを、利用可能ないずれかのプロセッサに配布するステップとを含む、方法。
【請求項１４】
シミュレートされるべきシステムを分解する方法であって、
前記システムの要素間の階層関係に基づき、前記システムをパーティションにどのように分解するかを決定するステップと、
前記パーティションを用いて前記システムをシミュレートするステップとを含む、方法。
【請求項１５】
どのように分解するかを決定する前記ステップは、既存のパーティションをさらに分解するコストを見積もる際に、前記既存のパーティション内の要素間の階層関係を考慮するステップを含む、請求項１４に記載の方法。
【請求項１６】
システムをシミュレートする方法であって、
実行プランを生成するステップを含み、前記実行プランを生成する前記ステップは、前記実行プラン内の特定のレベルにあるタスクをスケジューリングするステップを含み、前記方法はさらに、
前記実行プランを解析して、現在スケジューリングされるべきタスクがどのように互いに関連しているか、および、それらのタスクが、今後スケジューリングが必要とされるタスクにどのように関連しているかを判断するステップと、
今後のタスクに関連する前記実行プランの部分を先読みするステップと、
前記現在スケジューリングされるべきタスクと、今後スケジューリングが必要とされるタスクとの間の関係に基づき、前記現在スケジューリングされるべきタスクをどのようにスケジューリングするかを決定するステップと、
前記実行プランに基づき、前記システムをシミュレートするステップとを含む、方法。
【請求項１７】
特定の現在スケジューリングされるべきタスクに多くの今後のタスクが従属していることを検出すると、他の現在スケジューリングされるべきタスクよりも先に、前記特定のタスクをスケジューリングするステップをさらに含む、請求項１６に記載の方法。
【請求項１８】
１つ以上のプロセッサにより実行されると、前記１つ以上のプロセッサにクレーム１−１７のいずれか１つに記載の方法を実施させる命令の１つ以上のシーケンスを有する、コンピュータ読取可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
この発明は一般に、シミュレーションに関し、特定的には、大きな複雑系の正確な波形レベルのコンピュータシミュレーションに関する。
【背景技術】
【０００２】
背景
シミュレーションは、設計者または開発者が生産前に設計の試験を行なえるように、コンピュータシステムを用いて実施され得る。たとえば、設計者は、コンピュータアプリケーションを用いる複雑な回路を設計することができる。すると、そのアプリケーションは、或る入力を受けた場合の或る時間における当該回路の出力をシミュレートすることができる。設計者は、このシミュレーションを用いて、いくつかの回路を実際に構築する必要なく、当該回路の試作品の形成および試験を容易に行なうことができる。
【０００３】
シミュレーションは、高価な計算リソースを必要とすることが多い。これらのリソースを安価に提供する１つの方法が、並列に作動する機械のクラスタの使用である。たとえば、いくつかのコンピュータシステムを共にネットワーク接続して、１つの問題の解に一団となって取組むことが可能である。これらのシミュレーションを並列に実施する１つの難題が、機械間での作業の分割および連係である。
【０００４】
回路のシミュレーションは、集積回路に重点を置いたシミュレーションプログラム（Simulation Program With Integrated Circuit Emphasis）（ＳＰＩＣＥ）シミュレータまたはその派生物を用いて実施されることが多い。これらのシミュレータは、「ダイレクトスパース（Direct Sparse）」解法として公知の数値積分法を使用する。回路が大きくなること、および、信号品位の影響が重大になることに伴い、これらのシミュレーションの遂行に要する時間が極めて長くなる。これらのシミュレーションは一般に、回路の過渡挙動を要し、初期値問題（Initial Value Problem）を解くことを必要とする。
【０００５】
図１は、初期値問題を用いるシミュレーションに対する解を求めるためのプロセスを示すフローチャートである。ダイレクトスパース法を用いてより大きなシミュレーションの所定の部分についての解を求めるために、プロセス１００を用いることができる。たとえば、回路のシミュレーションをいくつかのブロックに分割することができ、いくつかのブロックの各々は、微分代数方程式（ＤＡＥ）により表わされ得る。一実施形態によると、修正節点解析法（ＭＮＡ）を用いてＤＡＥが提供される。次に、これらの方程式を簡約して解き、シミュレーションについての解に到達することができる。
【０００６】
【数１】
2009512910.tif 000003
【０００７】
ブロック１０８および１１０はＮＲループを形成し、このループは、ブロック１１０の線形システムソルバの解が収束するまで繰返され得る。ブロック１１２では、ＮＲ解が収束したか否かが判断される。収束している場合、プロセスはブロック１１４に進む。解が収束していない場合、ＮＲループが繰返され、プロセスはブロック１０８に戻る。
【０００８】
ブロック１１４において、処理されるべき時間ステップがまだ存在する場合、プロセス１００はブロック１０６に戻り、新規の時点についての解を求めることができる。時間ステップがそれ以上存在しない場合、このプロセスはブロック１１６で終了する。その時点で、この問題についての解が得られる。
【０００９】
シミュレーションの並列化
チップ設計の検証は、異なる入力波形または動的ベクトルを用いた多くの過渡シミュレーションの遂行を要する。シミュレーションの並列実施はシミュレーションの速度を高め得る。通信のオーバーヘッドと、通信中における計算の同期化の必要性とにより、並列実施にボトルネックが生じ得る。ダイレクトスパース法は、通信および同期化のオーバーヘッドにより、並列実施の性能ゲインが限られていた。
【００１０】
システムのシミュレーションを並列化するための手法は、２つの大きなカテゴリに分けられ、これらのカテゴリを、本明細書では、方法並列性（parallelism-in-the method）およびシステム並列性（parallelism-in-systems）と称する。方法並列性の手法を用いて、プロセス１００のＮＲ反復を並列化させることができる。しかしながら、ＮＲ反復の並列化は、回路全体のどこにおいても、活動（すなわち、変数値の急速な変化）により規定される時間的尺度において、回路全体における通信の同期化を必要とする。
【００１１】
回路のシミュレーションという状況において、システム並列性の手法は、回路のシミュレーションの文献において「波形緩和」とも呼ばれる。このシステム並列性の手法は、サブ回路への回路の分割を要し、当該サブ回路間ですべての波形を交換することにより、初期値問題の並列シミュレーション（時間過渡シミュレーション）を可能にする。しかしながら、実際のほとんどの回路では、フィードバックにより、結果的に得られる収束が遅くなる。
【００１２】
システム並列性のシミュレーションで使用されるサブ回路が、強結合されたシステムの一部であるときに、遅い収束により生じる問題が悪化する。システム内の２つの異なるサブ回路における２つ以上の節点が、（Ｊ．ホワイト（J. White）およびＡ．Ｉ．サンジョバンニ−ヴァンサンテリ（A. I. Sangiovanni-Vincentelli）、回路のシミュレーションのための分割アルゴリズムおよび波形緩和の並列実施（Partitioning Algorithms and Parallel Implementation of Waveform Relaxation for Circuit Simulations）、ＩＣＡＳ−８５紀要、２２１−２２４頁）に記載されるように「密結合」している場合、２つ以上のサブ回路からなるシステムまたはシステムの一部は、「強結合」していると考えられる（ケビン・ブラージ（Kevin Burrage）、常微分方程式のシステムのための並列方法（Parallel Methods for Systems of Ordinary Differential Equations）、アドバンシス・イン・コンピュテーショナル・マスマティックス（Advances In Computational Mathematics）、１９９７年、１−３１頁を参照）。
【００１３】
システム並列性の実施の利点は、遅い収束の結果、減少する。この遅い収束は、多くの緩和反復を生じる。この問題に対処するために、局所結合という状況における強結合により生じる遅い収束に対処するための手法が提案されてきた。「局所結合」という用語は、２つのエンティティ間の特定の接続部におけるローディングを指す。回路という状況において、局所結合は、或る回路の１つのポートを別の回路の別のポートに接続するワイヤに対するローディングに対応し得る。たとえば、図１８において、Ｓ１とＳ２との間の結合Ｖ１は、局所結合を構成する。
【００１４】
強い局所結合により生じる遅い収束の問題に対処するいくつかの試みは、たとえば、Ｊ．ホワイトおよびＡ．Ｉ．サンジョバンニ−ヴァンサンテリ、回路のシミュレーションのための分割アルゴリズムおよび波形緩和の並列実施、ＩＣＡＳ−８５紀要、２２１−２２４頁、Ｖに開示されている。いくつかのシミュレーションツールを用いた混合システム解析のための改善された緩和手法は、（ドミトリエフ−ズドロフ，Ｖ．Ｂ．（Dmitriev-Zdorov, V. B.）、クラーセン，Ｂ．（Klaassen, B.）、デザイン・オートメーション・カンファレンス（Design Automation Conference）、１９９５、ＥＵＲＯ−ＶＨＤＬ共催、ＥＵＲＯ−ＤＡＣ’９５紀要、欧州（European）、巻、号、１８−２２、１９９５年９月、２７４−２７９頁）に記載されている。
【００１５】
「局所結合」とは対照的に、「大域結合」とは、周期を生じる態様で多数のエンティティを接続することにより形成される結合を指す。たとえば、大域結合は、回路Ａを回路Ｂに接続し、この回路Ｂが回路Ｃに接続され、この回路Ｃが回路Ａに再び接続されることにより生じ得る。したがって、図１８において、Ｓ１、Ｓ２、およびＳ３の間で環状接続を生じるＶ１、Ｖ２、Ｖ３を含む結合は、大域結合である。「大域結合」に対処するためのいくつかの試みが、（緩和ベースのソルバにおいて収束を改善するための方法としての汎用化結合（Generalized coupling as a way to improve the convergence in relaxation-based solvers）、ドミトリエフ−ズドロフ，Ｖ．Ｂ．、デザイン・オートメーション・カンファレンス、１９９６、ＥＵＲＯ−ＶＨＤＬ’９６および展示会共催、ＥＵＲＯ−ＤＡＣ’９６紀要、欧州（European）、巻、号、１６−２０、１９９６年９月、１５−２０頁）、ならびに（大域フィードバックループを有する回路の並列波形緩和（Parallel Waveform Relaxation of Circuits with Global Feedback Loops）、デザイン・オートメーション・カンファレンス、１９９２、１２−１５頁）に記載されているが、効率が悪い。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
実際に、システムのシミュレーションを並列化するためにシステム並列性の手法が使用される場合、パーティションが大きくなり過ぎて計算負荷の効果的な並列化が達成されな
いか、または、通信および同期化のオーバーヘッドにより、この方法が非効果的になってしまう。必要とされているのは、並列化されたシミュレーションを実施するのに必要な時間を短縮し、かつ、局所強結合および大域強結合の両方を考慮する方法である。
【課題を解決するための手段】
【００１７】
発明の概要
本明細書では、さまざまな新規の技術およびシステムを記載する。それらの中には、システムをシミュレートすることに関する１つ以上の見積りコストに基づき、システムを第１の組のパーティションに自動的に分解することにより、当該システムをシミュレーションするための方法が含まれる。システムのシミュレーションが実施され、第１の組のパーティションに対応するシステムの部分は、相対的に精度の低いシミュレーションメカニズムを用いてシミュレートされる。第２の組のシミュレーションが実施され、この間に、第１の組のパーティション内の各パーティションは、相対的に精度の高いシミュレーションメカニズムを用いてシミュレートされる。
【００１８】
以下に記載する別の新規の技術は、システムを複数のパーティションに分解することにより、当該システムをシミュレートすることを含む。分解は、階層を意識した態様で実施され得る。第１の組のパーティションは、第１の種類のシミュレータでシミュレートされ得るが第２の種類のシミュレータではシミュレートされ得ない第１の種類の技術に対応する。第２の種類のパーティションは、第２の種類のシミュレータでシミュレートされ得るが第１の種類のシミュレータではシミュレートされ得ない第２の種類の技術に対応する。システムはその後、第１の種類のシミュレータを用いて第１の組のパーティション内の各パーティションをシミュレートすること、および、第２の種類のシミュレータを用いて第２の組のパーティション内の各パーティションをシミュレートすることを含むステップを実施することにより、シミュレートされる。
【００１９】
以下に記載する別の新規の技術は、システムをシミュレートするために使用されるべきシミュレータに関連するライセンス供与情報を自動的に検出すること、および、当該ライセンス供与情報に少なくとも部分的に基づいてシステムをシミュレートすることにより、当該システムをシミュレートすることを含む。
【００２０】
以下に記載するシミュレーション技術は、（容量限界により）より精度の高いシミュレータでは実行され得ない、強結合された大きな回路のシミュレーションの遂行を可能にする。さらに、このシミュレーション技術は、レイアウト後の抽出から生じる、強結合された大きな回路のシミュレーションの遂行を可能にする。
【００２１】
本明細書に記載される技術を用いて、電力／接地／基板グリッドのネットワークを含み、かつ、信号品位の解析および検証に高精度を必要とする、強結合された大きな回路のシミュレーションを実施することができる。
【００２２】
１つのシミュレーション演算は、多数のＣＰＵおよび／または多数のコアにおいて併行して遂行されるタスクに分割され得る。たとえば一実施形態において、実行プランの生成およびスケジューリングの実行は、多数のｃｐｕにおいて実施される。一実施形態において、スケジューリングは、スケジューラの先読みを伴う。
【００２３】
シミュレーションの進捗報告および中間結果報告を実施するための技術も記載される。このような報告技術は、シミュレーションを実施する者に対し、極めて有用なフィードバックを提供し得る。
【発明を実施するための最良の形態】
【００２４】
この発明の１つ以上の実施形態は、添付の図面において、限定ではなく例示として示され、添付の図面では、同じ参照符号が同様の要素を指す。
【００２５】
詳細な説明
以下の説明では、説明のために、多数の具体的な詳細を明示して、この発明の完全な理解を図る。しかしながら、これらの具体的な詳細を用いなくてもこの発明の実施が可能であることが明らかであろう。また、場合によっては、この発明を必要以上に不明瞭にすることを回避するため、公知の特徴および装置をブロック図の形態で示すこともある。
【００２６】
用語
この説明において、「一実施形態」または「実施形態」への言及は、参照されている特徴が、この発明の少なくとも一実施形態に含まれていることを意味する。さらに、この説明における「一実施形態」または「実施形態」への別個の言及は、必ずしも同一の実施形態を指さない。しかしながら、このような実施形態は、明記されていない限り、また、説明から当業者にとって容易に明らかになるであろう場合を除き、やはり互いを排除しない。たとえば、一実施形態に記載された特徴、構造、動作等は、他の実施形態にも含まれ得る。したがって、この発明は、本明細書に記載する実施形態のさまざまな組合せおよび／または統合を含み得る。
【００２７】
概観
上記のように、システム並列性は、システムをいくつかのパーティションに分解することを要する。小さなパーティションほど容易に並列化され得、それにより、シミュレーションに必要な時間が、場合によっては短縮される。加えて、パーティションが小さいほど、必要とされる計算の総数が少なくなる。一般に、シミュレーションは、パーティション間で波形を交換することにより並列化される。波形は、特定のパーティションの出力および入力を表わす。交換されている波形が共通の値に一旦近づくと、波形は収束して解を生じる。２つのパーティション間の強結合は、収束に必要な反復（または２つのパーティション間の波形の交換）の数を増大させ得る。
【００２８】
システムシミュレーションの手法における先行の実施例は、局所強結合しか効果的に扱うことができなかった。本明細書では、強結合されたパーティションの「プレビュー」近似解を実施することにより、収束に必要な反復の数を減らすための技術を記載する。これらのプレビュー解は、シミュレーションが始まる前に導入され、局所結合および大域結合の両方の影響を低減する。波形が一旦収束すると、シミュレーションは解を求める。以下に説明するように、近似の導入は、波形が収束するのに必要とする計算時間量を短縮し、局所強結合および大域強結合の両方に対応する。
【００２９】
シミュレーション反復の概観
一連のシミュレーション反復を用いてシステムを並列にシミュレートするための技術が提供される。一実施形態によると、システムはパーティションに分割される。システムがパーティションに分割された後に、これらのパーティションの１つ以上が選択されて近似され、別個にシミュレートされる。本明細書では、選択されて近似され、別個にシミュレートされるパーティションを「選択されたパーティション」と呼ぶ。本明細書では、選択されたパーティションのいずれにも属さないシステムの部分を、そのシステムの「残余」と一括して呼ぶ。
【００３０】
選択されたパーティションの組が確立した後に、シミュレーション反復が実行される。各シミュレーション反復は、２つのシミュレーション段階、すなわち、プレビューアのシミュレーション段階および選択されたパーティションのシミュレーション段階を要する。プレビューアのシミュレーション段階では、システムのシミュレーションが遂行され、こ
の間に、システムの選択されたパーティションは、相対的に精度の低いシミュレーションメカニズムを用いてシミュレートされる。選択されたパーティションのシミュレーション段階では、１組のシミュレーションが遂行され、その間に、選択されたパーティションの各々は、相対的により精度の高いシミュレーションメカニズムを用いてシミュレートされる。
【００３１】
プレビューアのシミュレーション段階からの結果は、選択されたパーティションのシミュレーション段階からの結果と比較され、さらに別のシミュレーション反復が必要であるか否かが判断される。さらに別のシミュレーション反復が必要な場合は、さらに別のシミュレーション反復が実施され、以降のシミュレーション反復の各々が、以前のシミュレーション反復の結果を考慮に入れる。
【００３２】
一実施形態によると、プレビューアのシミュレーション段階では、選択されたパーティションの、相対的に精度の低い数学的モデルが使用され、選択されたパーティションのシミュレーション段階では、選択されたパーティションの、相対的に精度の高い数学的モデルが使用される。このような一実施形態では、シミュレーション反復の両方の段階において同一のシミュレータを使用して、選択されたパーティションをシミュレートすることができる。
【００３３】
別の実施形態によると、プレビューアのシミュレーション段階では、選択されたパーティションをシミュレートするために、相対的に精度の低いシミュレータが使用され、選択されたパーティションのシミュレーション段階では、選択されたパーティションをシミュレートするために、相対的に精度の高いシミュレータが使用される。このような実施形態では、シミュレーション反復の両方の段階において、選択されたパーティションの同一の数学的モデルを使用することができる。
【００３４】
シミュレーションシステムの概観
図２７は、この発明の一実施形態に従った、システムをシミュレートするためのシステム２７００のブロック図である。システム２７００は一般に、システム定義パーサ２７０２、パーティショナ２７０４、およびスケジューラ２７０６を含む。
【００３５】
システム定義パーサ２７０２は、シミュレートされるべきシステムの定義を受取り、そのシステムの基準形式の記述をパーティショナ２７０４のＡＰＩ２７０６に提示する。システム２７００は、いくつかの異なるシステム定義パーサを含み得、それらの各々は、異なる種類のシステム定義を構文解析するように設計される。たとえば、シミュレートされるべきシステムが回路である場合、その回路を記述するネットリストを構文解析することのできるシステム定義パーサ２７０２が使用され得る。システム定義パーサ２７０２は、ネットリストを構文解析した後に、その回路の基準形式の記述をパーティショナ２７０４に提示する。
【００３６】
異なるシステム定義パーサの使用を通じ、パーティショナ２７０４は、さまざまな種類のシステムと併用され得る。これらのシステム定義パーサが、パーティショナ２７０４に対してシステムの基準形式の記述を提示することから、シミュレートされるべきシステムの固有の本質は、パーティショナ２７０４にとってほぼ透過的となり得る。
【００３７】
パーティショナ２７０４は、シミュレートされるべきシステムをパーティションに分割する。以下により詳細に説明するように、シミュレートされるべきシステムを分割するプロセスは、いくつかの段階を要し得る。シミュレートされるべきシステムが一旦分割されると、パーティショナは、そのシステムがいかにシミュレートされるかを示すプランを生成する。本明細書において、シミュレーションの「実行プラン」と称されるこのプランは
その後、スケジューラ２７０６に提供される。
【００３８】
スケジューラ２７０６は、パーティショナ２７０４からシミュレーションについての実行プランを受取り、そのプランを実行する。一般に、プランの実行は、刺激およびシミュレーション問題をシミュレータに供給すること、シミュレータ２７０８を呼出すこと、ならびに、シミュレータ２７０８からシミュレーション結果を受取ることを要する。回路のシミュレーションという状況において、シミュレータ２７０８は、ＳＰＩＣＥシミュレータおよび／またはＦＡＳＴ  ＳＰＩＣＥシミュレータを含み得る。以下により詳細に説明するように、シミュレーションの或る段階において、スケジューラ２７０６は、多数のシミュレータ２７０８にシミュレーションを並列に実施させ、この並列動作は、シミュレートされるべきシステムが分割されたパーティションに対応する。
【００３９】
Ｎポートシステムのシミュレーション
回路のシミュレーションについて広範囲にわたって論じる予定だが、これ以外のシミュレーションが、本明細書に記載する技術から恩恵を受け得ることを理解されたい。ネットワーク接続されたｎポートの観点から、たとえば生物学的、化学的、および自動車のシミュレーションを説明することができる。
【００４０】
ｎポートは、他のシステムとネットワーク接続され得る一層大きなシステムのパーティションとして考えられ得る。ｎポートの観点で説明され得るいずれの種類のシステムも、開示される技術から恩恵を受け得る。たとえば、ｎポートは、温度、速度、力、電力等の値を記述することができる。いくつかのシミュレーション規格、たとえばＶｅｒｉｌｏｇＡＭＳは、現在、ｎポートの観点でさまざまなシステムを記述することができる。
【００４１】
Ｎポートシステムの分割
図４は、この発明の一実施形態に従った、ｎポートまたは回路を備えてシミュレーションを実施するシステムを分割するためのプロセスを説明するフローチャートである。プロセス４００は、シミュレートされるべき一層大きなシステムを、システム並列の方法と共に使用されるべき一層小さなパーティションに分割することを記述する。以下に論じるように、システム全体を一層小さなブロックに分割することにより、各パーティションについてのノード数Ｎが減少し、その結果、必要な計算の総数が減少する。計算は、収束に必要な波形反復の数だけ、各パーティションの波形シミュレーションを遂行することを含む。
【００４２】
大きなパーティション、または、多くの未知の節点変数を有するパーティションは一般に、波形シミュレーション中に、より小さなパーティションよりも多くの計算を必要とする。信号品位の影響を受けない純粋なデジタル回路のほとんどにおいて、時点当たりの計算コストは、節点の数Ｎ、大まかにはＮαに比例し、式中、αは１．４から１．６である。しかしながら、電力グリッドのメッシュ等の信号品位の影響が含まれる場合、αは１．８から２．４の間であり得る。加えて、より大きな回路において、シミュレーションにおける時点の数は、全体使用率が高くなることによって増大する。共に、これらの影響は、収束速度およびオーバーヘッドが悪影響を受けないという前提で、より小さなパーティションの稼働を極めて有利にする。
【００４３】
一般に、回路が有する節点または変数Ｎが少なくなるほど、時点当たりに必要とされる計算の数が少なくなる。たとえば、α＝２のシステムにおいて、１０００個の節点を有するパーティションは、１つの波形において、時点当たり〜１，０００，０００回の浮動小数点演算を必要とする。その一方で、１０００個の節点の回路が、各々が１００個の節点を有する１０個のより小さな回路に分割された場合、これら１０個のより小さな回路の各々は、時点当たり全部で〜１００，０００回の演算に対し、時点当たり〜１０，０００回
の浮動小数点演算しか必要としない。加えて、より大きな回路において、シミュレーションにおける時点の数は、全体使用率が高くなることによって増大する。
【００４４】
強結合の影響は、システムをより一層小さなパーティションに分割する利点に照らして平均化される。たとえば、パーティションは、その挙動が回路の他の素子の挙動に強く依存する素子を含む回路を含み得る。この分割化により、これらの強結合されたパーティションが分割される場合、結果的に得られるシミュレーションは一般に、収束に多くの波形反復を必要とする。その結果、収束に必要とされる反復の数の増大が、より小さなパーティションのおかげで各波形反復をシミュレートするのに必要な時間が短縮されることよりも強い影響を有することがある。以下に説明するように、プレビューアを用いた近似の導入により、大域結合および局所結合の両方の影響が低減され、収束に必要な反復の数が減少する。
【００４５】
プロセス４００は、開始ブロック４０２において開始される。ブロック４０４では、全システムの、サブシステムへの初期の分割化が行なわれる。この分割化は、システムの本来の特性から生じる弱い結合に基づき完了される。効果的にも全システムが走査され、初期のパーティションの数およびそれらのシミュレーションの次数が求められる。これらのパーティションは、本来の結合の次数でシミュレートされると相対的に少ない数の反復で収束するように選択される。大きな初期のパーティションは、内部における強結合の結果である。上で述べたように、パーティションが大きいほど、波形のシミュレーションの各々に対し、より著しく長い計算時間が必要となる。時間が長くなるほど、コンピュータのローディングに不均衡を生じ、このことが並列化を制限する。ブロック４０６では、さらに並列化を必要とする、順序付けられたパーティションが識別される。これらのパーティションは、ブロック４０４で生成されたパーティションを吟味することにより、さらに分割可能であると識別される。これらの識別されたパーティションは、所望されるものよりも大きな、強結合されたパーティションである。ブロック４０８では、さらに並列化を可能にし、かつ、改良された分割化および次数を得るために、プレビューアシミュレーションが導入される。プレビューアおよびその動作については以下にさらに説明するが、一般にプレビューアや、プレビュー近似解を提供するために強結合されたシステムに導入される近似を含む。プレビューアは、シミュレータに対する解を「プレビュー」する。パーティションのシミュレーションが始まる前に、プレビューアが近似を生成するため、システムは、局所結合および大域結合の影響を低減する。このことについては、以下に説明する。
【００４６】
プレビューアは、さらに分割を行なうための最良の候補を決定する。ブロック４１０では、コンピュータプラットフォーム上における新たな次数のプレビューアシミュレーションを含む、改良されたパーティションのシミュレーションが遂行される。この演算は、シミュレーション自体の実施である。このシミュレーションは、ＳＰＩＣＥ、ＶｅｒｉｌｏｇＡＭＳ、または他のシミュレーションアプリケーションを用いて実施され得る。
【００４７】
ブロック４１２では、シミュレーションの進捗状況が監視され、提案された分割の収束についての試験が実施される。必要であれば、ブロックの最良の組、したがって最良のシミュレーションを生じるために、これらの分割がさらに改良される。
【００４８】
回路のシミュレーション等の分野で生じる力学系のシミュレーションは一般に、ｎポートの相互接続を用いて記述される。ＶｅｒｉｌｏｇＡＭＳ等のシミュレーション言語により、設計者は、大規模のシステムを、ｎポートの観点で階層的に記述することが可能になる。ＳＰＩＣＥ等の回路のシミュレーションにより、ｎポートのサブ回路に関する階層的記述が可能になる。ｎ＋１端末装置はいずれも、ｎポートのサブ回路として記述され得る。各ｎポートは、内部において、１組の微分および代数方程式として記述される。ポート
における相互接続は、キルヒホフの電流則（Kirchoff's Current Law）（ＫＣＬ）またはキルヒホフの電圧則（Kirchoff's Voltage Law）（ＫＶＬ）等のさらに別の制約を生じる。
【００４９】
回路の分割の例
図５は、強結合されたマルチポート非線形回路を示す。回路５００は、回路５０２および５０４を含み、これらの回路は、個々のｎポートとして記述され得る。回路５００は、上記の分割化４０４の結果である。回路５００は、大き過ぎるパーティションであり得、したがって、シミュレーションに必要な時間を増大させる。しかしながら、回路５００は強結合もされているため、分割されると収束が遅くなり過ぎる。大きな回路５００は事前に２つの回路５０２および５０４に分割され得、回路５０２が近似され得、回路５０４は、元の回路５００の残余である。
【００５０】
具体的に、回路５００は、２つのパーティション、すなわち回路５０２および回路５０４に分割される。例示のため、回路５０２が、選択されて近似され、別個にシミュレートされる唯一のパーティションであるものと仮定されたい。したがって、回路５０２は、回路５００の「選択されたパーティション」であり、回路５０４は「残余」である。
【００５１】
回路５０２がｎポートインピーダンスＨ1として表わされ、回路５０４が、より大きなパーティション５００の残余であると仮定されたい。回路５０２はｎ＋１端子回路であり、ｎは、この回路で見られるポートの数であり、回路５０２は、回路の残余５０４と共通の接地４０６を共有する。
【００５２】
【数２】
2009512910.tif 000004
【００５３】
並列実行
パーティショナ２７０４は、シミュレートされるべきシステムを分割した後、シミュレーションについての並列実行プランを構築する。パーティショナ２７０４は、並列実行プランをスケジューラ２７０６に渡し、スケジューラ２７０６は、このプランに基づいてシミュレータ２７０８を呼出す。たとえば、スケジューラ２７０６は、シミュレーション反復の、プレビューアのシミュレーション段階において、シミュレータを呼出し、シミュレートされるべきシステムのプレビューアをシミュレートすることができる。スケジューラ２７０６は、シミュレーション反復の、選択されたパーティションのシミュレーション段階において、シミュレートされるべきシステムの選択されたパーティションの各々に対し、別個のシミュレータを呼出すことができる。各シミュレーション反復の結果を用いて、
さらに別のシミュレーション反復が実施されるべきか否かが判断される。
【００５４】
一実施形態によると、シミュレートされるべきシステムがこのようにしてシミュレートされている間、シミュレーション性能が監視される。シミュレーションに、コストの見積もりが示した時間よりも著しく長い時間がかかっている場合、このシミュレーションは停止され得る。パーティショナ２７０４は、シミュレーションが停止された後に、このシミュレーションで用いられた分割化を改訂することができる。たとえば、パーティショナ２７０４は、そのパーティションのシミュレーションに、元々見積もった時間よりも著しく長い時間がかかっていることを検出すると、システムのパーティションをさらに分解することができる。この分割化が変更された後に、新規の分割化方式に基づき、新規の実行プランが生成され得る。この新規の実行プランはスケジューラ２７０６に渡され、スケジューラ２７０６は、この新規の実行プランに基づいてシミュレーションを再開する。
【００５５】
たとえば、パーティショナ２７０４は、システムのすべてのパーティションが、Ｘ以下のシミュレーション見積りコストを有するようになるまで、特定のシステムを分割することができる。システム２７００は、実際のシミュレーション中において、パーティションのうちの１つのシミュレーションに、Ｘを著しく上回る費用がかかっていることを検出することができる。その時点で、システム２７００はシミュレーションを停止し、その特定のパーティションをより小さなパーティションにさらに分解することができる。システム２７００はその後、より小さなパーティションに基づいた実行プランを用いて、シミュレーションのプロセスを再開することができる。
【００５６】
「大き過ぎる」と判断されたパーティションは、シミュレーションプロセスの全体を再開する代わりに、実行中にさらに分解され得る。したがって、１回のシミュレーション反復中に、特定のパーティションがシミュレートされ得る。その特定のパーティションは、シミュレーション反復とシミュレーション反復との間に、いくつかの一層小さなパーティションに分割され得る。したがって、以降のシミュレーション反復において、より小さなこれらのパーティションの各々は、別個にシミュレートされる。
【００５７】
一実施形態では、「最終的な」実行プランが選択される前に、システム２７００により、１つ以上の「特徴付けラン」が実施される。この特徴付けランの間に、パーティションに試験シミュレーションが実施され、分解すべきパーティションがあれば、どのパーティションをさらに分解すべきであるかが判断される。
【００５８】
並列シミュレーションの例
回路５００が分割されてプレビューア回路６００が一旦作成されると、回路５００のプレビューアのシミュレーション段階において、プレビューア回路６００を用いて回路５００をシミュレートすることができる。
【００５９】
プレビューア回路６００のシミュレーションが、パーティション５０２の、一層精度の低いシミュレーションの実施を要することから、プレビューア回路６００のシミュレーションは、回路５００のシミュレーションよりも一段と高速で実施され得る。
【００６０】
回路６００をシミュレートすることにより生じる結果は、回路５００を直接シミュレートすることによって生じる結果ほど正確ではないことが考えられる。しかしながら、多数のシミュレーション反復を実施することにより、正確なシミュレーション結果が生成され得る。
【００６１】
【数３】
2009512910.tif 000005
【００６２】
第３の演算３）は、選択されたパーティションのシミュレーション段階を構成し、この段階では、電流波形について求められた値が、回路５０２（選択されたパーティション）に入力されて、この反復についての電圧波形の値が求められる。
【００６３】
【数４】
2009512910.tif 000006
【００６４】
多数の選択されたパーティションを用いたシミュレーションの例
【００６５】
【数５】
2009512910.tif 000007
【００６６】
このプロセスは、図６に関して上で説明したプロセスと同様である。しかしながら、この場合、シミュレーションが実施されなければならないいくつかの異なるパーティションが存在する。値ｉは、各パーティションに対してインクリメントされる。
【００６７】
選択されたパーティションのシミュレーション段階の並列化
【００６８】
【数６】
2009512910.tif 000008
【００６９】
図１０は、上記のシミュレーションプロセスを並列化した状態における、いくつかのプロセッサ１００２、１００４、および１００６の、時間線１００８に沿ったアクションを示す。時間ｔsimは、シミュレーションの各反復に対する時間である。１回の反復中におけるシミュレーション期間は、時間セグメントに分割される。図１０は、各々が等しい計算時間ｔsim／２を必要とする２つの時間セグメントを有する例を示す。第１のプロセッサ１００２には一般に、プレビューアの算出が割当てられる。第２のプロセッサ１００４および第３のプロセッサ１００６には、個々のパーティションが割当てられ、これらのパーティションをシミュレートする。この例において、第１のプロセッサ１００２は、複合近似（プレビューア）を遂行し、第２のプロセッサ１００４は、第１のパーティション９０２ａを遂行し、第３のプロセッサ１００６は、第２のパーティション９０２ｂを遂行する。たとえば、第１のプロセッサ１００２は、反復１０１０ａの前半において複合近似１０１２を遂行する。近似１０１２が完了すると、この近似１０１２は、プロセッサ１００４および１００６に転送され、各プロセッサ１００４および１００６は、この反復の後半において個々のパーティションをシミュレートする。換言すると、ｔ0とｔ0＋ｔsim／２との間の時間期間において、第１のプロセッサ１００２はプレビューア１０１２を算出し、このプレビューア１０１２は、プロセッサ１００４および１００６により使用されて、それぞれシミュレーション１０１４および１０１６が遂行される。ｔ0＋ｔsim／２とｔ0＋ｔsimとの間の時間期間において、第１のプロセッサ１００２は、第１の反復の後半のプレビューアシミュレーションを算出する。この時間中に、プロセッサ１００４および１００６は、時間ｔ0およびｔ0＋ｔsim／２の時間中にプロセッサ１００２により生成されたプレビューアを用いて、反復の前半についてのシミュレーションを遂行する。時間ｔ0＋ｔsimとｔ0＋１．５＊ｔsimとの間において、プロセッサ１００４および１００６は、時間ｔ0＋ｔsim／２とｔ0＋ｔsimの間にプロセッサ１００２により生成されたプレビューアの解１０２２を用いて、シミュレーション１０１８および１０２０を遂行する。このプロセスは、シミュレーションが収束するまで続く。
【００７０】
【数７】
2009512910.tif 000009
【００７１】
【数８】
2009512910.tif 000010
【００７２】
シミュレーションの利点
この手法にはいくつかの利点がある。ほぼ強結合された非線形マルチポートシステムが考察されているため、大域フィードバック状況および局所フィードバック状況がいずれも、共に対処される。これまでの方法は、大域フィードバックとは別個に、１つの端子におけるローディングから生じる局所フィードバックへの対処を試みていた。これらの先行の方法は、ＭＯＳ回路の固有の単一方向構造を利用していた。強力な局所双方向結合が存在すると、このことにより収束が難しくなる。また、先行の方法は、強力な大域結合が存在すると、収束が遅くなるという欠点を有した。
【００７３】
この方法は、バナッハ（Banach）空間において非線形波形を非線形波形にマッピングするあらゆるシミュレーションに適用される。反復中の収束試験において、また、以下の近似のためのインクリメンタルな作用素ゲインを計算するために、対応するバナッハ空間ノルムが使用される。したがって、この発明は、マルチポートシステムの固有の構造を使用してその利益を得ない。根底に存在するドメインの構造を利用するシミュレータであればいずれも、この方法から得られる利点だけでなく、この構造をも利用することができる。たとえば、ＳＰＩＣＥ等の回路シミュレータにおいて、根底に存在する回路方程式の疎構造は、シミュレータ自体により利用される。個々の構成要素のシミュレートにＳＰＩＣＥ
を使用することにより、回路方程式の疎構造の利用が可能になる。
【００７４】
複合近似は、さまざまな手法を用いてシミュレートされ得る。たとえば、ＭＯＳ回路のシミュレータにおいて、複合近似は、事象駆動型シミュレーションにおける、テーブル駆動型区分的近似モデルを用いて構築され得る。このようなシミュレータは、高速タイミングシミュレータとも呼ばれ、ＳＰＩＣＥよりも１０−１０００倍の速度で近似波形を提供する。しかしながら、近似波形は、５−１０％内でのみ正確である。近似シミュレーションの別の例は、モデル次数低減（Model Order Reduction）（ＭＯＲ）の使用である。大きなＲＬＣネットワークに関し、ＭＯＲは、１０％までの誤差を持ち込むことと引換えに、数桁分も高速の計算を提供する。
【００７５】
近似が収束条件に見合う限り、どのようなドメイン特化シミュレータおよびドメイン特化近似をも使用することができる。驚くべき点とは、粗い近似が迅速な収束につながる点である。
【００７６】
近似の選択
【００７７】
【数９】
2009512910.tif 000011
【００７８】
【数１０】
2009512910.tif 000012
【００７９】
【数１１】
2009512910.tif 000013
【００８０】
残りの説明は、本明細書に記載する技術のいくつかの例について記載する。これらの説明は、例として理解され、さらに、記載された発明の他のいくつかの考え得る実施例および実施形態が存在することがさらに理解される。
【００８１】
【数１２】
2009512910.tif 000014
【００８２】
【数１３】
2009512910.tif 000015
【００８３】
結合コンデンサＣ３  １３１０が、他のコンデンサＣ１  １３０８およびＣ２  １３１０よりも大きなキャパシタンスを有するときに、収束の速度が下がる。図１４は、標準的なガウス−ザイデル分解を用いた遅い収束を示す。グラフ１４００は、ｘ軸１４０２に沿ってプロットされた時間と、ｙ軸１４０４に沿った電圧とを有する。プロット線１４０６の各々は、回路１３００についての実際の値と比較した、先行のガウス−ザイデル分解を用いたシミュレーションの進行中の反復の各々の誤差を示す。グラフ１４００は、１０回の反復を経てゆっくりと収束するシミュレーションを示す。プロット線１４０６ａは、１回目の反復についての誤差を示し、プロット線１４０６ｊは、１０回目の反復についての誤差を示す。このシミュレーションは正しい解に向けてゆっくりと収束しているが、１０回目の反復の後も、誤差はいくつかの時点において０．６Ｖを上回る。このように低い収束速度が実際に容認不可能であることは明らかである。先行の方法を用いた発見的分割アルゴリズムは、回路１３００を分割しない。しかしながら、より大きな回路で分割を行なうと、並列計算に対して不十分な粒度を生じる。
【００８４】
図１５は、非線形素子Ｇ２  １３０２についての近似を示す。グラフ１５００は、ｘ軸１５０２の電圧対ｙ軸１５０４の電流のプロットを示す。完全な、シミュレートされたプロット１５０６が、グラフ１５００に示される。近似値は、プロット１５０８を用いて示される。この近似値は、本明細書に記載する技術、たとえば、粗い区分的線形テーブルルックアップを用いて得られる。
【００８５】
図１６は、非線形素子Ｇ２の区分的線形近似１５０８を含む回路１３００を示す。プレビューア回路１６００は、元の非線形素子１３０２の代わりに近似１６０２を含む回路１３００である。パーティション１６０４は、図５および図６で示したように、パーティション１３０４に取って代わる。
【００８６】
図１７は、プレビューア回路１６００を用いた、加速された収束を示すプロットである。プロット１７００は、プロット１５００と同様に、ｘ軸１７０２に沿って時間を、また、ｙ軸１７０４に沿って電圧を示す。プロットの電圧は、回路１３００により生じた実際の出力からの誤差である。ｙ軸１７０４の尺度が、上記のｙ軸１５０４の尺度よりもはるかに小さく、１回目の反復１７０６ａについても、誤差が１０回目の反復１５０６ｊについての誤差よりもはるかに小さいことを示す点に注目されたい。３回目の反復１７０６ｃまでに誤差はほとんどなくなっており、シミュレーションは、回路１３００について実際に計算された値に極めて接近する。その結果、本明細書に記載する発明の実施形態を用いることにより、反復は、近似を用いないときよりもはるかに迅速に収束する。
【００８７】
図１８−図２２は、この発明の一実施形態に従った、単方向大域結合および局所双方向
結合と、それらのシミュレーションとを示す。図１８は、双二次フィルタ回路１８００を示す。回路１８００は、３つの演算増幅器の段１８０２、１８０４、および１８０６を含む。入力電圧から出力電圧への理想的なフィルタ伝達関数は、振動応答を有する二次である。実際の応答は、演算増幅器におけるスリューレートおよびクランピング等の非線形の影響を受ける。加えて、線形化された伝達関数には、高次の寄生極および零が存在する。演算増幅器の段１８０２、１８０４、または１８０６の各々をサブ回路と考えると、機能ブロックの単方向入力−出力信号のフローをトラバースするのに伴って振動応答を生じる強力な大域結合が存在することは明らかである。各接続節点においては、この大域結合に加え、局所的な双方向ローディングの影響が存在する。大域結合は、高速で作動し、かつ強力である。
【００８８】
図１９は、ガウス−ザイデル分解を用いて分割された回路１８００を示す。分解１９００は、いくつかの順序付けられたパーティション１９０２、１９０４、および１９０６に分割された回路１８００を示す。これらのパーティションは、公知のガウス−ザイデル分解を用いて形成される。
【００８９】
図２０は、ガウス−ザイデル分解を用いた回路１８００のシミュレーションの収束を示すプロットである。グラフ２０００は、ｘ軸２００２に沿って時間を、また、ｙ軸２００４に沿って電圧を示す。プロット２００６は、回路１８００の実際の応答を示す。プロット２００８は、ガウス−ザイデル分解１９００を用いた５回の反復後の出力を示す。プロット２０１０は、ガウス−ザイデル分解１９００を用いた１０回の反復後の出力を示す。認識できるように、波形は極めてゆっくりと収束する。
【００９０】
この発明の実施形態によると、回路１８００は、図７、図８、および図９の回路７００が分解されたのと同じ態様で分解され得る。図２１は、この発明の実施形態に従った、回路１８００の分解からのプレビューアを示す。各サブ回路の段Ｈ1  １８０２、Ｈ2  １８０４、およびＨ3  １８０６は、非線形２ポートインピーダンス作用素として視認される。残余回路Ｈ0  ２１０８は、相互接続ワイヤを有する節点のみを含む。段２１０２、２１０４、および２１０６の各々の近似は、全非線形演算増幅器を等価の理想的な電圧制御電圧源で置換することにより得られる。
【００９１】
図２２は、この発明の実施形態に従って分解された回路１８００の収束を示すグラフである。グラフ２２００は、ｘ軸２２０２に時間を示し、ｙ軸２２０４に出力電圧を示す。プロット２２０６は、フルシミュレーションである。プロット２２０８は、１回目の反復後の出力であり、プロット２２１０は、２回目の反復後の出力である。認識できるように、図７、図８、および図９で示す分解を用いると、シミュレーションは極めて迅速に収束する。
【００９２】
図２３−図２６は、この発明の実施形態に従った、双方向局所結合および双方向大域結合の非線形メッシュの例を示す。図２３Ａは、非線形二次元メッシュ２３００を示す。図２３Ｂおよび図２３Ｃは、メッシュ２３００の分解図を示す。メッシュ２３００は、集積回路（ＩＣ）における電力グリッドであり得る。メッシュ２３００は、近接する４つの節点に接続する各内部節点２３０４における４つの抵抗器２３０２を含む。各節点２３０４において、コンデンサ２３０６およびダイオード２３０８は、接地２３１０に接続される。ダイオード２３０８には逆バイアスがかけられている。メッシュの角部は、４つの接続抵抗器２３０２を介して供給節点に接続される。メッシュの節点は、タイル２３１２に分割される。図２３Ａに示すように、メッシュ２３００は、３×２個のタイルのグリッドを含む。各タイル２３１２は、中央節点２３０４を含み、この中央節点２３０４に対し、高インピーダンス電流源２３１４が取付けられる。
【００９３】
図２３Ｃに示すように、タイル２３１２は、接続抵抗器２３１６を介して接続される。これらの接続抵抗器２３１６は、残余回路Ｈ0を構成することが考えられ、各タイル２３１２は、図７、図８および図９と同様に、パーティションＨiを含み得る。メッシュ２３００は、この発明の実施形態に従った態様で分解され得る。
【００９４】
【数１４】
2009512910.tif 000016
【００９５】
図２４は、回路２３００の完全参照シミュレーションおよびフルオーダ線形近似からの、タイル２３１２についての中央節点電圧を示すグラフ２４００を示す。ｘ軸２４０２は時間を示し、ｙ軸２４０４は出力の電圧を示す。プロット２４０６は、完全参照シミュレーションを示し、プロット２４０８は、フルオーダ線形近似を示す。２つのプロット２４０６と２４０８との差は、ダイオード２３０８の非線形性により生じる。
【００９６】
図２５は、タイル２３１２の中央節点電圧についての近似低次プレビューア応答と、完全参照系との差を示す。ここでも同様に、ｘ軸２５０２は時間を示し、ｙ軸２５０４は電圧を示す。プロット２５０６は、近似と完全参照との差がかなり大きいことを示す。
【００９７】
図２６は、プレビューアベースの近似の実施形態を用いた３回の反復後のシミュレーションの電圧出力の誤差を示すグラフである。グラフ２６００は、時間を示すｘ軸２６０２と、電圧を示すｙ軸２６０４とを含む。プロット２６０６は、誤差が、わずか３回の反復の後に、容認される許容差内に十分に入っていることを示す。それとは対照的に、標準的なガウス−ザイデル分解を用いると、収束は５０回を上回る反復を要する。
【００９８】
シミュレートされるべきシステムの分解
以下により詳細に説明するように、パーティショナ２７０４により生じるパーティションの各々は、選択されたパーティションのシミュレーション段階において、別個にシミュレートされる。一実施形態によると、選択されたパーティションのシミュレーションは、並列に実施される。その結果、選択されたパーティションのシミュレーション段階の持続時間は、パーティショナ２７０４によって生じる、シミュレートするのに最も費用のかかるパーティションにより規定される。
【００９９】
パーティションが小さいほど／複雑ではないほど、そのパーティションのシミュレーションが高速で行なわれる。しかしながら、シミュレートされるべきシステムのパーティションが小さくなるにつれ、パーティションの数が増える。パーティションの数が増えるにつれ、シミュレーションの並列実行の連係および実行にまつわるオーバーヘッドも増える。
【０１００】
パーティショナ２７０４は、パーティションが大き過ぎるか否かを判断するために、パーティションの「サイズ」を求めるためのメカニズムを含む。パーティションのサイズを求めるためのメカニズムは、シミュレートされるべきシステムの本質を含むさまざまな因子に基づき、実現例ごとに異なり得る。
【０１０１】
たとえば回路という状況において、パーティショナ２７０４は、パーティションの記述内の節点の数、パーティション内で表わされる素子の数、パーティションをシミュレートするのに使用されるシミュレータの能力、各プロセッサにとって利用可能な揮発性メモリ
の量等に少なくとも部分的に基づき、回路のパーティションのサイズを求めるように構成され得る。
【０１０２】
パーティションをさらに分割すべきか否かを判断するために使用されるしきいサイズは、プレビューア回路をシミュレートするのにかかる推定時間量、および、シミュレートされるべきシステムの分解の所望の程度を含む、さまざまな因子に基づき選択され得る。分解の所望の程度は、次いで、シミュレーションを実施するのに利用可能なコンピュータリソースの数、シミュレータを始動するコスト、システムを極めて多くのパーティションに分解し過ぎることにより生じるであろう通信オーバーヘッドの量を含む、さまざまな因子に基づき、変化し得る。
【０１０３】
一実施形態によると、パーティショナ２７０４は、利用可能な計算リソース、システムが分割されるパーティションの数およびサイズ、使用されているシミュレータ等に基づき、シミュレートされるべきシステムをシミュレートする総コストを見積もるためのメカニズムを含む。パーティションを細分化することによってシミュレーションの総コストが削減される限り、パーティショナ２７０４は、パーティションを細分化し続ける。パーティションを細分化することによってもシミュレーションの総コストが削減されない場合、分解はそれ以上行なわれない。
【０１０４】
多数の段階への分解
この発明の実施形態によると、パーティショナ２７０４は、システムを多数の段階に分割するように構成される。一般に、パーティショナ２７０４は、相対的に迅速な収束（すなわち、相対的に数の少ないシミュレーション反復）と、利用可能な計算リソースの効率のよい使用と、シミュレーションの総計算コストの削減とを可能にする態様でシステムを分解することにより、シミュレートされるべきシステムを分割する。
【０１０５】
段階を説明するために、シミュレートされるべきシステムが回路である例を提示する。しかしながら、パーティショナ２７０４により使用される分割化技術は、シミュレートされるべきあらゆる種類のシステムに適用され得る。分割化のさまざまな段階を、以下により詳細に説明する。
【０１０６】
Ｙ／Ｚ分解
一実施形態によると、パーティショナ２７０４により実施される分割化の第１の段階が、Ｙ／Ｚ分解である。パーティショナ２７０４は、Ｙ／Ｚ分解の段階中に、シミュレートされるべきシステム内において、或る分離基準を満たす構成要素を探す。一実施形態によると、この分離基準は、（１）構成要素が１つ以上のワイヤにより接続されていることと、（２）当該１つ以上のワイヤ上の波形が別個にシミュレートされる場合に当該波形が収束することとを含む。
【０１０７】
図２８Ａは、１つ以上のワイヤにより互いに接続される２つの構成要素（ＹおよびＺ）のブロック図である。Ｙ／Ｚ分解の段階において、以下のこと、すなわち、（１）Ｙのシミュレーション中に、Ｚの以前のシミュレーションにより生じた電圧を、それらのワイヤ上の入力電圧として用いること、および、（２）Ｚのシミュレーション中に、Ｙの以前のシミュレーションにより生じた電流を、それらのワイヤ上の入力電流として使用すること、を繰返し実施することにより収束が生じる場合、ＹおよびＺは、異なるパーティションに分離される。図２８Ｂにおいて、構成要素ＹおよびＺを含むシステムは、ＺからＹを分離することにより分割されている。
【０１０８】
Ｙ／Ｚ分解は、インターフェイス節点において対接地インピーダンスが低いことを表わすサブ回路を識別することにより、開始される。たとえば、マイクロチップ回路における
電力および接地の供給ネットワークは、それらを能動構成要素に接続するポートにおいて、対接地インピーダンスが低いことを表わす。電力および接地のネットワークにより供給を受ける能動構成要素は一般に、それらを電力および接地のネットワークに接続するポートにおいて、低い対接地アドミッタンスを提供する。接地節点から始まり、低抵抗経路を介して到達され得るすべての節点は、他方の側が、Ｚサブ回路により提供される対接地インピーダンスよりも著しく高い対接地インピーダンス（または低いアドミッタンスＹ）を提供する場合、Ｚサブ回路に属するものと識別される。
【０１０９】
Ｙ／Ｚ分解の段階の後、図２９に示すように、元のシステムは多くのパーティションに分割され得る。図２９において、Ｙ／Ｚの分割化の段階は、３つの別個の「Ｙ」パーティションおよび３つの別個「Ｚ」パーティションへのシステムの分割化を生じる。しかしながら、この結果は単に例示である。Ｙ／Ｚ分解の段階から生じる特定の組のパーティションおよびそれらのパーティションの種類は、分割されるべきシステムの本質および特徴に基づいて変化する。
【０１１０】
ＲＬＣＭ分解
この発明の一実施形態によると、２段階分割動作の第２段階を、本明細書ではＲＬＣＭ分解と呼ぶ。ＲＬＣＭは、抵抗器（Ｒ）、インダクタ（Ｌ）、コンデンサ（Ｃ）、およびＭＯＳトランジスタ（Ｍ）を表わす。ＲＬＣＭ分解中に、Ｙ／Ｚ分解の段階で生じたパーティションに試験を行ない、これらのパーティションがさらに分割され得るかを判断する。
【０１１１】
パーティション内の各回路素子は、当該回路素子によって生じる結合がどの程度強いかに基づき、パーティションをより多くのパーティションへとさらに分解するための候補であるかどうかを判断するために試験される。試験は、すべての候補素子の中でも、抵抗器、インダクタ、コンデンサ、およびＭＯＳトランジスタに限定される。さらに、素子の結合の強度は、ｓ＝０（コンダクタンス試験）およびｓ＝無限大（キャパシタンス試験）において接続節点におけるノートンの等価（Norton Equivalents）を用いて計算される（Ｊ．ホワイトおよびＡ．Ｉ．サンジョバンニ−ヴァンサンテリ、…ＩＣＡＳ、１９８５年、およびＶＬＩＳ回路のシミュレーションのための緩和技術（Relaxation Techniques for the Simulation of VLIS Circuits）１９８７年を参照）。分解におけるこの段階は、回路の本質的な特性を利用する。ＭＯＳトランジスタは一般に、ゲート端子からドレインおよびソース端子への単方向の強力な結合を提供する。パーティション間の強力な単方向フローからの大域フィードバックにより、周期が形成され得る。周期内で長いループ遅延が生じたときに、時間ウインドウイング（Ｊ．ホワイトおよびＡ．Ｉ．サンジョバンニ、ＩＣＡＳ  １９８５、Ｔ．Ａ．ジョンソン（T. A. Jhonson）およびＡ．Ｅ．ルーリ（A. E.
Ruehli）、ＤＡＣ  １９９２年を参照）は、効率のよいパーティションのためのメカニズムを提供する。周期内で短い時間遅延が生じた場合、周期内のパーティションはマージバックされ、このマージの後に、潜在的に大きなパーティションが生じる。
【０１１２】
回路という状況において、自動化されたＹ／Ｚの分割化の間に生じた「Ｚ」パーティションは一般に、電力グリッドまたは接地グリッドに対応する。対照的に、「Ｙ」パーティションは一般に、能動的な非電力グリッド構造である。一実施形態によると、パーティショナ２７０４は、Ｚパーティションが電力グリッドであるか否かを判断し、ＲＬＣＭ段階の間には、このようにして識別されたどのような電力グリッドにも試験を行なわない。なぜなら、ＲＬＣＭの試験が、電力グリッドに対するさらに別のパーティションを生じにくいためである。
【０１１３】
プレビューアベースの分割化
一実施形態では、Ｙ／Ｚ分解およびＲＬＣＭ分解の後に、或るしきいサイズを引続き上
回っているパーティションのいずれかは、大きすぎると考えられ、プレビューアベースの分解というさらに別の段階が、これらのパーティションに対して実施される。
【０１１４】
一般に、プレビューアベースの分割化は、図５から図１２に記載した手法の、大きなパーティションの各々への適用を要する。このようなパーティションの各々に関しては、図７、図１２、および図２１と同様にプレビューアパーティションが存在し、図９と同様に、対応するサブパーティションが存在する。
【０１１５】
実行プランの生成
最終のパーティションおよびサブパーティションが一旦識別されると、シミュレーションジョブがネットリストファイルとして作成される。一実施形態において、ネットリストファイルは、他のシミュレーションジョブからの信号を刺激ファイルとして含む。刺激ファイルは、既に遂行されたシミュレーションジョブの出力を収集し、刺激を計算し、その刺激を書出すことによって作成される。一実施形態において、刺激は、区分的線形信号として書出される。実行プランは、遂行されるべきシミュレーションジョブの明細と、１つのシミュレーションジョブの、他のシミュレーションジョブからの出力に対する依存度とを含む。一実施形態において、実行プランは、シミュレーションジョブ間のデータ従属性を示すための有向非巡回グラフを含む。
【０１１６】
シミュレーションのスケジューリングおよび実行
一実施形態において、シミュレーションのランタイムのスケジューリングは、１）ジョブを遂行するのに必要とされる入力の利用可能性に基づき、遂行される準備が整ったすべてのシミュレーションジョブを、所定のいずれの時間においても識別し、２）実行プランにおいて遂行される準備が整ったシミュレーションジョブを、実行キューに追加し、３）その時に、シミュレーションライセンスを用いて稼動されるように利用可能なすべてのプロセッサを識別し、４）実行キュー内の次のシミュレーションジョブを、ステップ３）において利用可能ないずれかのプロセッサに配布することにより、実施される。ステップ１）から４）を含むランタイムのスケジューリングループは、実行プラン内のすべてのシミュレーションジョブが完了するまで繰返される。
【０１１７】
ライセンスを意識した分解およびシミュレーション
設備によっては、シミュレーションを実施するために使用されるシミュレータの数に対して制限が課されることが考えられる。たとえば、シミュレータは、許可されたソフトウェアにより実施され得、このシミュレータソフトウェアに適用されるライセンスは、特定の団体が使用し得るシミュレータの数に対して制限を課す。したがって、一実施形態によると、このような制限は、シミュレートされるべきシステムの分解中に、パーティショナ２７０４により考慮される因子である。たとえば、パーティショナ２７０４は、１０個の許可されたシミュレータのみが利用可能であることを示す入力に応答して、パーティションの数を１０に制限することが考えられる。
【０１１８】
一実施形態によると、シミュレーションシステム２７００は、シミュレーションを実施する前に、シミュレータライセンスの表示を探すように構成される。システム２７００は、たとえば、ライセンスの表示が発見されたシミュレータのみを用いてシミュレーションを実施するように構成され得る。システム２７００はまた、上記のとおり、シミュレートされるべきシステムをどの程度細かく分解するかを判断するために使用される因子の１つとして、発見したライセンス情報を用いることができる。
【０１１９】
階層を意識した分解およびシミュレーション
多くのシステムにおいて、システムの要素は、互いに階層関係を有する。一実施形態によると、パーティショナ２７０４は、システムをどのように分解すべきかを判断する際に
、システムの要素間の階層関係を考慮する。たとえば、パーティショナ２７０４は、既存のパーティションをさらに分解するコストを見積もるときに、そのパーティション内の要素間の階層関係を考慮する。極めて関連性の高い要素を別個のパーティションに分ける態様でパーティションを細分化することは、関連性のより少ない要素を別個のパーティションに分ける態様でパーティションを細分化するよりも高いコストがかかる。
【０１２０】
誤ったシミュレーション結果の補償
残念ながら、シミュレータが正確な結果を常に生じるとは限らない。たとえば、或る状況下において、一連の点についてデータを生成する際に、シミュレータによっては、その一連の点の最後の点について、誤った情報を生じることがある。一実施形態によると、スケジューラ２７０６がシミュレータを呼出すときに、スケジューラ２７０６は、シミュレータに、実際の所望の一連の点を上回る一連の点についてシミュレートさせる。スケジューラ２７０６は、要求された一連の点についてのシミュレーション結果を受取ると、その要求された一連の点のうちの最後の点にまつわる、不必要であり、かつ、潜在的に誤ったシミュレーション結果を廃棄する。
【０１２１】
スケジューラの先読み
一実施形態によると、スケジューラ２７０６は、先読み機能を有して設計される。たとえば、スケジューリングのタスクが実行プラン内の特定のレベルにある場合、スケジューラ２７０６は、実行プランを解析して、現在スケジューリングされるべきタスクがどの程度互いに関連しているか、および、それらのタスクが、今後スケジューリングが必要とされるタスクにどの程度関連しているかを判断する。スケジューラ２７０６は、今後のタスクに関連する実行プランの部分を先読みすることにより、現在スケジューリングされるべきタスクをどのようにスケジューリングすべきかについて、インテリジェントな決定を行なうことができる。たとえば、スケジューラ２７０６は、多くの今後のタスクが、現在スケジューリングされるべき特定のタスクに従属していることを検出すると、他の現在スケジューリングされるべきタスクよりも先に、その特定のタスクをスケジューリングすることができる。
【０１２２】
シミュレーションの進捗状況の報告
一実施形態によると、スケジューラ２７０６は、シミュレーション演算の進捗状況を報告するためのメカニズムを有して構成される。スケジューラ２７０６は、たとえば、シミュレートされるべきシステム全体のシミュレーションの進捗状況、および／または、選択された各パーティションのシミュレーションの進捗状況の表示を、或る態様で発行するように構成され得る。進捗状況の表示が発行される態様は、実施例ごとに異なり得る。たとえば、スケジューラ２７０６は、呼出され得るＡＰＩを公開して進捗状況の表示を検索することができる。代替的に、スケジューラ２７０６は、プログレスバーの視覚表示を生成することができる。さらに別の実施形態において、進捗状況は、表示された素子の色を変更することにより、視覚的に表わされ得る。
【０１２３】
中間結果報告
一実施形態によると、スケジューラ２７０６は、シミュレーション演算の全体が完了する前に、事前のシミュレーション結果を報告するためのメカニズムを有して構成される。たとえば、スケジューラ２７０６は、呼出され得るＡＰＩを公開して、最も最近のシミュレーション反復により生じたシミュレーション結果を検索することができる。これらの結果は、まとめて、またはパーティションごとに、システムに提供され得る。
【０１２４】
一実施形態によると、スケジューラ２７０６は、（１）選択されたパーティションにより表わされるシステムの一部を識別する情報と、（２）その選択されたパーティションをシミュレートすることにより生じる最も最近のシミュレーション結果とを生成する。シス
テム全体のシミュレーションが進行中であり得る場合でも、特定のパーティションについてのシミュレーション結果が「最終」であることが考えられる。なぜなら、そのパーティションをシミュレートする結果が、プレビューア回路のシミュレーションの結果により収束するためである。
【０１２５】
シミュレートされるべきシステム
本明細書に記載する技術は、プレビューア段階のシミュレーションおよび選択されたパーティション段階のシミュレーションの結果が収束する限り、どのようなシステムにも使用され得る。したがって、本明細書に提示する例の多くが回路のシミュレーションという状況にあるものの、これらの同じ技術を用いて、以下のものに限定されないが、航空機／機体のシミュレーション、油田のシミュレーション、精製／化学的シミュレーション、ビジネス／株式市場のシミュレーション、医療用撮像、コンピュータ動画、気象学、生物工学のシミュレーション、機械のシミュレーション、建築学のシミュレーション、マイクロメカニカルシミュレーション（ＭＥＭＳ）、光学系シミュレーション、映像符号化および／または暗号化、ならびに配電シミュレーションを含む、あらゆる数の状況におけるシミュレーションを並列化することができる。
【０１２６】
マルチモードシステム
上に提示した例において、シミュレートされるべきシステムは主に、１種類の技術を要する。たとえば、シミュレートされるべきシステムは、アナログ回路またはＲＦ回路であり得る。しかしながら、本明細書に記載する技術を同様に適用して、異なる種類のサブシステムを含むシステムをシミュレートすることができる。たとえば、これらの技術を用いて、異なる技術を用いていることにより異なるシミュレータを必要とする２つ以上のサブシステムを含むシステムをシミュレートすることができる。たとえば、これらの技術を用いて、たとえば、アナログ回路素子とのインターフェイスとなるか、またはデジタル回路素子とのインターフェイスとなるＲＦ回路素子を含むシステムをシミュレートすることができる。このようなシステムは、本明細書において「マルチモード」システムと呼ばれる。
【０１２７】
分割化の第１のラウンドが、マルチモードシステムをシミュレートするために使用される場合、この第１のラウンドは、システムの異なるサブシステムをシミュレートするために用いられなければならないシミュレータに基づき、システムを分割することを要し得る。このサブシステムが緊密に結合されている場合、このレベルでプレビューアベースの分割化が用いられる。この態様で作成されたパーティションは、所望の分解の程度を得るために、さらに細分化され得る。パーティションのシミュレーション間でのデータ交換は、単にシミュレーション波形を用いることにより行なわれ得る。したがって、完全に異なるシミュレーションメカニズムを有するシミュレータの使用が可能となる。特定のクラスの回路素子に特化されたシミュレータは、一般的なシミュレータよりも著しく高い速度を提供し得る。
【０１２８】
マルチコアＣＰＵ
マルチコアＣＰＵは、１つのダイ上に多数の処理ユニットを有する。同一のダイの上のコア間の通信にまつわるオーバーヘッドは、異なるダイ上のプロセッサ間の通信にまつわるオーバーヘッドよりもはるかに少ない。実施形態によると、この差は、シミュレートされるべきシステムの分解中、および、シミュレーションのスケジューリング中に考慮される因子の１つである。
【０１２９】
たとえば、回路は、マルチコアＣＰＵの存在を検出したことに応答して、グループ内のパーティション間で相対的に多くの通信を必要とするパーティションの別個のグループを作成するように分解され得る。シミュレーション中に、グループ内のパーティションは、
同一のマルチコアＣＰＵに割当てられる。一実施形態において、分割化で使用されるコストメトリックは、シミュレーションのパーティション間の相対的通信負荷を含む。
【０１３０】
統合されるシミュレータ
一実施形態において、シミュレータ２７０８は、新規のシミュレーション演算が実施されなければならなくなる度に、スケジューラ２７０６により呼出される。残念ながら、シミュレータを頻繁に起動させると、特に相対的に小さなパーティションをシミュレートする際に、多大な量のオーバーヘッドを生じ得る。このオーバーヘッドは、シミュレートされるべきパーティションを規定する情報の読出および構文解析を含む。
【０１３１】
一実施形態によると、シミュレータ２７０８は、システム２７００に統合され、シミュレーション演算間で割振られた状態になるように設計される。したがって、シミュレータは、パーティションの１回目のシミュレーション反復中に、そのパーティションを規定するネットリストの読出および構文解析を行なうことができる。１回目の反復の後に、そのネットリストについて構文解析された情報が保持される。結果的には、シミュレータが同一のパーティションの以降のシミュレーション反復を実施する際に、そのネットリストを再度構文解析する必要がなくなる。
【０１３２】
一実施形態において、プレビューアの近似は、シミュレータにより構文解析されたネットリストから計算される。統合されたシミュレータは、１回目のランから計算された近似を格納し、プレビューアの以降のシミュレーション反復においてそれを使用することができる。
【０１３３】
補助的情報の作成および伝搬
シミュレータの入力の必要性は、シミュレータごとに異なる。シミュレータによっては、シミュレートされるべきシステムの定義を上回る情報を与えられると、より効率よく作動し得るものもある。このような情報を、本明細書では「補助的」情報と呼ぶ。
【０１３４】
補助的情報の一例は、回路内の素子間の階層についての情報である。回路シミュレータによっては、回路をより効率よくシミュレートするために、このような回路情報を使用し得るものもある。一実施形態によると、このような階層情報は、システム２７００に対し、入力として提供される。シミュレートされるべきシステムが、システム２７００によって分解されると、各パーティションに関連する階層情報が識別され、その階層情報は、そのパーティションをシミュレートする責任を負うシミュレータに提供される。
【０１３５】
別の実施形態によると、階層情報は、シミュレートされるべきシステムの定義に基づき、システム２７００により導出される。したがって、階層情報がシステム２７００に提供されない場合でも、階層情報は、シミュレーションの効率を高めるためにシミュレータに提供され得る。
【０１３６】
一実施形態において、システム２７００は、シミュレートされるべきシステムの分解を容易にするために、このシミュレートされるべきシステムを記述する階層を「均す」。しかしながら、システム２７００は、この階層についての情報を保持しており、それにより、このような情報は、当該このような情報を利用するシミュレータに提供され得る。
【０１３７】
階層情報は、シミュレータがシミュレーションをより効率よく実施するために使用し得ることが考えられる補助情報の一例に過ぎない。一実施形態によると、システム２７００は、各パーティションに適用される補助情報の一部が、そのパーティションのシミュレーションを実施するタスクを割当てられたシミュレータに提供されるようにする。
【０１３８】
他の状況における並列化
本明細書に記載する並列化技術を、シミュレーション演算という状況で説明してきたが、これらの技術は、他の状況において同様の態様で適用され得る。たとえば、本明細書で説明した逆構造解釈／並列化技術は、マイクロチップ設計の演算に適合され得る。
【０１３９】
単一ＣＰＵプラットフォーム
図２は、この発明の実施形態が実施され得るコンピュータシステムを示す。コンピュータシステム２００は、図３に記載する、より大きなクラスタの一部であり得る。コンピュータシステム２００は、バス２０２を含み、このバス２０２は、コンピュータシステム２００の全体にわたり、情報用配信チャネルとして働く。プロセッサ２０４はバス２０２に結合される。プロセッサ２０４は、以下のものに限定されないが、インテル（Intel）およびモトローラ（Motorola）により製造されたものを含む、あらゆる適切なプロセッサであり得る。プロセッサ２０４はまた、多数のプロセッサも含み得る。メモリ２０６もまた、バス２０２に結合される。メモリ２０６は、ランダムアクセスメモリ（ＲＡＭ）、読出専用メモリ（ＲＯＭ）、フラッシュメモリ等を含み得る。基本入力／出力ユニット２０８は、キーボード、マウス等のいくつかのソースから入力を受取り、ディスプレイ、スピーカ等の出力装置に出力する。記憶装置２１０は、ハードドライブまたはコンパクトディスク読出専用メモリ（ＣＤ−ＲＯＭ）等の磁気または光学記憶装置を含む、あらゆる種類の永久記憶装置または一時記憶装置を含み得る。オペレーティングシステム（ＯＳ）２１２のコピーが記憶装置２１０に格納され得る。ＯＳ２１２は、コンピュータシステム２００を作動させるのに必要なソフトウェアを含み、Ｌｉｎｕｘ（登録商標）等のＵｎｉｘ（登録商標）派生物であり得る。ＯＳ２１２が他の利用可能なＯＳのいずれか、たとえばマイクロソフト（Microsoft）のＷｉｎｄｏｗｓ（登録商標）またはＭａｃｉｎｔｏｓｈ（登録商標）ＯＳであってもよい理解されたい。ネットワークアダプタ２１４は、コンピュータシステム２００を、クラスタ内の他のシステム、およびインターネット（Internet）等の他のネットワークに、接続部２１６を介して接続する。コンピュータシステム２００がこの発明を実施するのに使用され得るコンピュータシステムの単なる一例であり、他の適切ないずれの構成を用いてもよいことを理解されたい。
【０１４０】
クラスタプラットフォーム環境
図３は、この発明の一実施形態に従ったコンピュータシステム３００のクラスタを示す。いくつかのコンピュータシステム２００は、中央スイッチまたはルータ３０２を備えたピア・トゥー・ピア構成を用いて共にネットワーク接続され得る。代替的に、ネットワーク接続されたシステム３００内のコンピュータシステム２００の１つが、セントラルサーバであり得る。この実施例を用いて、いくつかの安価なコンピュータシステム２００をネットワーク接続してクラスタ３００にし、並列化された問題を解くことのできる強力なシステムを提供することができる。
【０１４１】
この発明の実施形態が回路のシミュレーションに限定されないことを理解されたい。たとえば、いくつかの他の種類のシミュレーション、たとえば化学的シミュレーション、生物学的シミュレーション、自動車のシミュレーション等を、本明細書に記載したシステムおよび技術を用いて実施することができる。これらの技術は、特定のアプリケーションに対して適合され得る。
【０１４２】
特定の例示的な実施形態を参照してさまざまな技術を説明してきた。しかしながら、この発明のより広い精神および範囲から逸脱することなく、さまざまな変形および変更がこれらの実施形態に対して行なわれ得ることが、この開示の恩恵を受ける者にとっては明らかであろう。したがって、明細書および図面は、限定的な意味ではなく、例示的な意味で捉えられるべきである。
【図面の簡単な説明】
【０１４３】
【図１】初期値問題を用いてシミュレーションに対する解を求めるためのプロセスを示すフローチャートである。
【図２】この発明の実施形態が実施され得るコンピュータシステムを示す図である。
【図３】この発明の実施形態に従ったコンピュータシステムのクラスタを示す図である。
【図４】この発明の一実施形態に従った、システムを分割してシミュレーションを実施するためのプロセスを説明するフローチャートである。
【図５】強結合されたマルチポート非線形回路を示す図である。
【図６】この発明の一実施形態に従った、近似を含む強結合された回路を示す図である。
【図７】いくつかの一層小さなパーティションに分解された１つの大きなパーティションを示す図である。
【図８】ｍ個の近似されたパーティションを有する回路７００についてのプレビューア回路を示す図である。
【図９】いくつかの異なるパーティションに対してシミュレーションを実施するいくつかのプロセッサを示す図である。
【図１０】この発明の実施形態に従った、並列に稼働するいくつかのプロセッサを示す図である。
【図１１】プレビューア回路６００と同様の、強結合された回路についてのプレビューアを示す図である。
【図１２】回路８００と同様の、多くの別個のパーティションを含む回路を示す図である。
【図１３】双方向局所結合を呈する回路を示す図である。
【図１４】標準的なガウス−ザイデル分解を用いた遅い収束を示す図である。
【図１５】非線形素子Ｇ２についての近似を示す図である。
【図１６】非線形素子Ｇ２の区分的線形近似を含む回路を示す図である。
【図１７】回路の加速された収束を示すプロットである。
【図１８】双二次フィルタ回路を示す図である。
【図１９】ガウス−ザイデル分解を用いて分割された回路を示す図である。
【図２０】ガウス−ザイデル分解を用いた回路のシミュレーションの収束を示すプロットである。
【図２１】この発明の実施形態に従った、回路の分解からのプレビューアを示す図である。
【図２２】この発明の実施形態に従って分解された回路の収束を示すグラフである。
【図２３Ａ】非線形二次元メッシュを示す図である。
【図２３Ｂ】メッシュの分解図を示す図である。
【図２３Ｃ】メッシュの分解図を示す図である。
【図２４】回路の完全参照シミュレーションから、および、フルオーダ線形近似から、タイルについての中央節点電圧を示すグラフを示す図である。
【図２５】タイルの中央節点電圧についての、近似低次プレビューア応答と、完全参照系との差を示す図である。
【図２６】プレビューアベースの近似の実施形態を用いた３回の反復後のシミュレーションの電圧出力の誤差を示すグラフである。
【図２７】この発明の実施形態に従った、システムをシミュレートするためのシステムのブロック図である。
【図２８Ａ】１つ以上のワイヤにより互いに接続された２つの構成要素（ＹおよびＺ）のブロック図である。
【図２８Ｂ】構成要素ＹおよびＺが分離された、図２８Ａのシステムのブロック図である。
【図２９】システムが３つの別個の「Ｙ」パーティションおよび３つの別個の「Ｚ」パーティションに分割されたブロック図である。
【図１】
2009512910.tif 000017
【図２】
2009512910.tif 000018
【図３】
2009512910.tif 000019
【図４】
2009512910.tif 000020
【図５】
2009512910.tif 000021
【図６】
2009512910.tif 000022
【図７】
2009512910.tif 000023
【図８】
2009512910.tif 000024
【図９】
2009512910.tif 000025
【図１０】
2009512910.tif 000026
【図１１】
2009512910.tif 000027
【図１２】
2009512910.tif 000028
【図１３】
2009512910.tif 000029
【図１４】
2009512910.tif 000030
【図１５】
2009512910.tif 000031
【図１６】
2009512910.tif 000032
【図１７】
2009512910.tif 000033
【図１８】
2009512910.tif 000034
【図１９】
2009512910.tif 000035
【図２０】
2009512910.tif 000036
【図２１】
2009512910.tif 000037
【図２２】
2009512910.tif 000038
【図２３Ａ】
2009512910.tif 000039
【図２３Ｂ】
2009512910.tif 000040
【図２３Ｃ】
2009512910.tif 000041
【図２４】
2009512910.tif 000042
【図２５】
2009512910.tif 000043
【図２６】
2009512910.tif 000044
【図２７】
2009512910.tif 000045
【図２８Ａ】
2009512910.tif 000046
【図２８Ｂ】
2009512910.tif 000047
【図２９】
2009512910.tif 000048
【手続補正書】
【提出日】平成19年6月15日(2007.6.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
システムをシミュレートするための方法であって、
前記システムを第１の組のパーティションに自動的に分解するステップを含み、前記システムを第１の組のパーティションに自動的に分解する前記ステップは、
特定のパーティションを含む一組のパーティションを生じるように前記システムを分割するステップと、
前記システムをシミュレートすることに関する１つ以上の見積りコストに基づき、前記特定のパーティションを分割すべきか否かを判断するステップとを含み、前記方法はさらに、
前記システムのシミュレーションを実施するステップを含み、前記第１の組のパーティションに対応する前記システムの部分は、相対的に精度の低いシミュレーションメカニズムを用いてシミュレートされ、前記方法はさらに、
第２の組のシミュレーションを実施するステップを含み、前記第２の組のシミュレーションを実施する前記ステップの間に、前記第１の組のパーティション内の各パーティションは、相対的に精度の高いシミュレーションメカニズムを用いてシミュレートされる、方法。
【請求項２】
前記第２の組のシミュレーションの性能を監視するステップと、
前記第２の組のシミュレーションの１つ以上の性能が、予め定められた量を上回る量だけ、前記１つ以上の見積りコストから外れることを検出することに応答して、以下のステップを実施するステップとをさらに含み、前記以下のステップは、
第２の組のパーティションを生じるように前記システムをさらに分解するステップと、
前記システムのシミュレーションを実施するステップとを含み、前記第２の組のパーティションに対応する前記システムの部分は、相対的に精度の低いシミュレーションメカニズムを用いてシミュレートされ、前記以下のステップはさらに、
第３の組のシミュレーションを実施するステップを含み、前記第３の組のシミュレーションを実施する前記ステップの間に、前記第２の組のパーティション内の各パーティシ
ョンは、相対的に精度の高いシミュレーションメカニズムを用いてシミュレートされる、請求項１に記載の方法。
【請求項３】
自動的に分解する前記ステップは、前記システムをシミュレートするために使用されるべきシミュレータに関連するライセンス供与情報に少なくとも部分的に基づいて実施される、請求項１に記載の方法。
【請求項４】
システムをシミュレートするための方法であって、
前記システムを複数のパーティションに分解するステップを含み、
第１の組の前記パーティションは、第１の種類のシミュレータでシミュレータされ得るが第２の種類のシミュレータではシミュレートされ得ない第１の種類の技術に対応し、
第２の組の前記パーティションは、前記第２の種類のシミュレータでシミュレートされ得るが前記第１の種類のシミュレータではシミュレートされ得ない第２の種類の技術に対応し、前記方法はさらに、
以下のステップを実施することにより前記システムをシミュレートするステップを含み、前記以下のステップは、
前記第１の種類のシミュレータを用いて前記第１の組のパーティション内の各パーティションをシミュレートするステップと、
前記第２の種類のシミュレータを用いて前記第２の組のパーティション内の各パーティションをシミュレートするステップとを含む、方法。
【請求項５】
前記システムをシミュレートする前記ステップは、
前記システムのシミュレーションを実施するステップを含み、前記複数のパーティションに対応する前記システムの部分は、相対的に精度の低いシミュレーションメカニズムを用いてシミュレートされ、前記システムをシミュレートする前記ステップはさらに、
第２の組のシミュレーションを実施するステップを含み、前記第２の組のシミュレーションを実施する前記ステップの間に、前記複数のパーティション内の各パーティションは、相対的に精度の高いシミュレーションメカニズムを用いてシミュレートされ、
前記第２の組のシミュレーションを実施する前記ステップは、
前記第１の種類のシミュレータを用いて前記第１の組のパーティション内の各パーティションをシミュレートするステップと、
前記第２の種類のシミュレータを用いて前記第２の組のパーティション内の各パーティションをシミュレートするステップとを含む、請求項４に記載の方法。
【請求項６】
システムをシミュレートするための方法であって、
前記システムをシミュレートするために使用されるべきシミュレータに関連するライセンス供与情報を自動的に検出するステップと、
前記ライセンス供与情報に少なくとも部分的に基づいて前記システムをシミュレートするステップとを含む、方法。
【請求項７】
前記ライセンス供与情報に少なくとも部分的に基づき、前記システムをシミュレートする前記ステップは、
前記システムをシミュレートするために使用されるべきシミュレータに関連するライセンス供与情報に少なくとも部分的に基づき、前記システムをパーティションに自動的に分解するステップと、
前記パーティションを用いて前記システムをシミュレートするステップとを含む、請求項６に記載の方法。
【請求項８】
シミュレートされるべきシステムのパーティションを識別するステップと、
シミュレーションジョブを作成するステップとを含み、
前記シミュレーションジョブは、他のシミュレーションジョブからの信号を刺激ファイルとして含み、
前記刺激ファイルは、
既に遂行されたシミュレーションジョブの出力を収集し、
前記刺激を計算し、
前記刺激を書出すことにより作成される、方法。
【請求項９】
前記刺激は、区分的線形信号として書出される、請求項８に記載の方法。
【請求項１０】
遂行されるべきシミュレーションジョブの明細と、１つのシミュレーションジョブの、他のシミュレーションジョブからの出力に対する依存度とを含む実行プランを生成するステップをさらに含む、請求項８に記載の方法。
【請求項１１】
前記実行プランは、シミュレーションジョブ間のデータ従属性を示すための有向非巡回グラフを含む、請求項１０に記載の方法。
【請求項１２】
実行プランを生成する前記ステップは、多数の処理ユニットで併行して実行されるタスクに分割される、請求項１０に記載の方法。
【請求項１３】
シミュレーションのランタイムスケジューリングを実施するための方法であって、
必要とされる入力の利用可能性に基づき、遂行される準備が整ったすべてのシミュレーションジョブを、所定のいずれの時間においても識別するステップと、
実行プランにおいて遂行される準備が整ったシミュレーションジョブを、実行キューに追加するステップと、
その時に、シミュレーションライセンスを用いて稼動されるように利用可能なすべてのプロセッサを識別するステップと、
前記実行キュー内の次のシミュレーションジョブを、利用可能ないずれかのプロセッサに配布するステップとを含む、方法。
【請求項１４】
シミュレートされるべきシステムを分解する方法であって、
前記システムの要素間の階層関係に基づき、前記システムをパーティションにどのように分解するかを決定するステップと、
前記パーティションを用いて前記システムをシミュレートするステップとを含む、方法。
【請求項１５】
どのように分解するかを決定する前記ステップは、既存のパーティションをさらに分解するコストを見積もる際に、前記既存のパーティション内の要素間の階層関係を考慮するステップを含む、請求項１４に記載の方法。
【請求項１６】
システムをシミュレートする方法であって、
実行プランを生成するステップを含み、前記実行プランを生成する前記ステップは、前記実行プラン内の特定のレベルにあるタスクをスケジューリングするステップを含み、前記方法はさらに、
前記実行プランを解析して、現在スケジューリングされるべきタスクがどのように互いに関連しているか、および、それらのタスクが、今後スケジューリングが必要とされるタスクにどのように関連しているかを判断するステップと、
今後のタスクに関連する前記実行プランの部分を先読みするステップと、
前記現在スケジューリングされるべきタスクと、今後スケジューリングが必要とされるタスクとの間の関係に基づき、前記現在スケジューリングされるべきタスクをどのようにスケジューリングするかを決定するステップと、
前記実行プランに基づき、前記システムをシミュレートするステップとを含む、方法。
【請求項１７】
特定の現在スケジューリングされるべきタスクに多くの今後のタスクが従属していることを検出すると、他の現在スケジューリングされるべきタスクよりも先に、前記特定のタスクをスケジューリングするステップをさらに含む、請求項１６に記載の方法。
【請求項１８】
１つ以上のプロセッサにより実行されると、前記１つ以上のプロセッサにクレーム１−１７のいずれか１つに記載の方法を実施させる命令の１つ以上のシーケンスを有する、コンピュータ読取可能な媒体。
【国際調査報告】
2009512910.tif 000049
2009512910.tif 000050
2009512910.tif 000051