1. No category

大規模回路シミュレーションの高速化技術に関する研究

SURE: Shizuoka University REpository
http://ir.lib.shizuoka.ac.jp/
Title
Author(s)
大規模回路シミュレーションの高速化技術に関する研究
田中, 伸幸
Citation
Issue Date
URL
Version
1999-03-24
http://doi.org/10.11501/3162141
ETD
Rights
This document is downloaded at: 2016-03-01T10:47:20Z
電子科学研究科
0002515799 R
静岡大学 博士論文
大規模回路シミュレーションの高速化技術に関する研究
絆周大学国書
1999年1月
田中 伸幸
論文要旨
マルチメディア社会を支える高速なコンピュータや大容量通信システムなどの高速
情報処理システムを構成するために，LSIの大規模・高密度化ならびに高速化は著しく
進んでおり，また，回路の小規模化・低消費電力化に有効なA／D混載LSIも開発されて
いる・このようなLSIの設計および動作検証には，回路のアナログ的な挙動を詳細に解
析することが不可欠となり，極めて大規模な回路の詳細解析を実用的な時間で実行で
きる大規模アナログ回路シミュレータが必要となってきた．
本論文では，数百万トランジスタ規模の大規模回路シミュレーションに適した次世
代回路シミュレーションシステムを構成する要素技術である，専用並列計算機とこれ
を中核とする直接法ベースの大規模回路シミュレーションシステム，ならびに，高速
な緩和アルゴリズムを提案する．
本研究の目的とする回路シミュレータにおいては，解析精度は従来の回路シミュレー
タと同様で，高速化の代償として解析精度を低下させることはないものとし，数値計
算の収束性についても従来の回路シミュレータと同様のレベルを確保するものとした．
この目標を達成するために，収束性に優れた直接法を本研究の回路解析手法のベース
として用いる．直接法を適用できない規模の回路については，各部分回路を直接法の
適用限界まで大きく分割して緩和法を適用することとし，最上位レベルの回路分割と
対応して波形緩和法を適用することにより回路のマルチレート性を利用するとともに，
次のレベルの回路分割と対応して反復タイミング解析を適用し，このレベルでの回路
分割によって生じる部分回路の解析には直接法を用いることで，直接法と同等の収束
性を確保するものとした．
直接法で問題となる大規模回路への適用性を改善するため，本論文では，専用並列
計算機SMASHならびにスイッチを含む区分線形ダイオードモデルを提案する．SMASH
は大規模回路シミュレーションにおいて計算時間の多くを占める回路行列の三角化分
解に特化した専用ハードウエアを有し，節点分割に基づく回路分割を適用し，ホスト
計算機と負荷分散を行うことにより，行列計算時間を大幅に短縮することができるこ
とを示す．さらに，スイッチと抵抗のみで構成される簡易区分線形ダイオードモデル
を提案し，これを用いることによって素子モデル計算時間を削減できることを示した．
これらの高速化手法を通用することによって，従来の直接法では非現実的であった大
規模回路を解析できることを示す．
さらに，直接法が適用できない規模の回路に対して適用するオーバーラップ分割に
よる高速反復タイミング解析手法を提案し，直接法の収束性を保ったまま解析可能な
ii
回路規模を飛躍的に増大させると同時に高速化を達成できることを示す．本論文で提
案するオーバーラップブロック緩和ニュートン法は，部分回路の境界付近にある素子
や節点を隣接する部分回路に重複して含むよう冗長分割して解析する手法であり，各
部分回路には直接法を適用して解析する．オーバーラップ分割の適用によって1回の
緩和反復で求まる近似解の精度が向上し，緩和反復回数が減少するため，従来法と比
較して10∼1000倍の高速化を達成できることを示す．また，オーバーラップブロック
緩和ニュートン法は，適用する回路規模が2000節点以上と大きいときに回路全体に直
接法を適用するより高速になり，両者の差は回路規模が大きくなるにしたがって急速
に拡大することを示し，各部分回路を直接法の適用限界まで大きく分割する本論文の
分割手法に対して，オーバーラップブロック緩和ニュートン法が有効であることを示
す．
さらに，大規模回路の有するマルチレート性を利用した高速化を達成するために，
本論文では最上位の回路分割で動作速度の異なる機能ブロックレベルの極めて大きな
分割を適用し，波形緩和法による解析を行うことを提案する．従来の波形緩和法では，
部分回路間で局所的帰還ループを構成する場合に収束性が劣化し，無駄な計算を行っ
てしまう問題があった．本論文では，このような局所的帰還ループに対して，帰還ルー
プに沿った部分反復とウインドウ分割アルゴリズムを提案し，部分反復によって，収
束性の悪い局所帰還ループ部分のみを集中して緩和反復することによって全体の緩和
反復を減少させられることを示す．部分反復に全体の解析時間ウインドウより小さな
時間ウインドウを適用することで，時間ウインドウ後半部分の収束性を向上させ，そ
の結果として解析時間が短縮される．この波形緩和アルゴリズムにより，解析時間の
増大をともなうことなく，回路のマルチレート性を有効に利用できることを示す．
以上の要素技術を適用することにより本研究の目標である数百万トランジスタ規模
の大規模回路シミュレータを構築できる見通しが得られた．
iii
目次
1．2 回路シミュレーションの概要……．
1．3 直接法による回路シミュレーション……．……．……．
3
1．4大規模回路シミュレーションのための回路分割
1．5 緩和法による回路シミュレーション
6
1．6 潜在性とマルチレート性の利用による高速化
1．7 従来技術の大規模回路シミュレーションへの適用性．．…．……
1．8 本研究の目的
11
2 回路シミュレータ開発用支援ツールASSIST 17
2．1概要
2．2 回路方程式の導出
18
2．3 回路シミュレータ開発支援システムASSIST．．．．．．．．．．…．．．．．．
2．3．1ASSISTの構成…．．
2．3．2回路入力および構造記述言語HAL
19
2．3．3オーダリング及び基本モジュール定義ファイル
20
2．3．4回路情報生成
2．3．5行列情報生成……．…．．
2・3．6ライブラリの構成…………………． 28
2．4 ASSISTを用いたプログラム開発手順．…．．．．
29
2・5 ASSIST2およびASSISTを用いた回路シミュレータ開発例 30
2．6 まとめ
3 大規模回路行列のLU分解専用並列計算機……………
3．1概要
．． 32
3．2 回路行列の特徴とLU分解の並列処理性
3．2．1回路行列の特徴
lV
33
3．2．2LU分解の並列性
…………33
3．3 LU分解専用並列計算機SMASH
3．3．1アーキテクチャの概要．……．．…．
………．34
3．3．2メモリユニット及びデータ構造
35
3．3．3シフトレジスタユニットの構成
35
3．3．4除算クラスタの構成と動作
37
3．3．5更新クラスタの構成と動作
38
3．3．6回路分割手法導入による高速化 40
3．4 性能評価
3．5 まとめ………．．
4 LU分解専用並列計算機SMASHを用いた大規模回路シミュレーションの高速化…．46
4．1概要……．．…．．……
4．2 大規模回路の分割
………‥46
4．3 非線形回路網解析における計算量の評価
4．4 SMASHの構成
……‥51
4．5 メモリユニットの構成
●■●●●●●●●●●●●●●●●●●●●●●●●●●●
4．6 システムの動作概要．．．
4．7 シミュレーション結果…．．．．…．．．．．
4．8 素子モデル計算の高速化
4．9 まとめ
5 区分線形ダイオードモデルを用いた回路解析
5．1概要……………………………………‥ 59
5・2 スイッチを含む区分線形ダイオードモデルの提案とその定式化 60
5．3 バイポーラ回路網の動作状態解析……．．…‥．．…．．
5．4 解析例
5．5 まとめ‥．．…．．…．…．…．．．…
Ⅴ
6 オーバーラップ分割を用いた反復タイミング解析の高速化
6．1概要
6．2 オーバーラップ分割の有効性
6．3 0BRN法の評価
． 78
6．3．1解析プログラムの構成と解析回路例
6．3．2冗長度と計算時間の関係の評価
6．3．3冗長度決定アルゴリズム
6．4 回路規模と解析時間．…．．
6．5 まとめ
7 波形緩和法の高速化手法
7．1概要
…‥90
7．2 部分反復による高速化手法
7．3 ウインドウ分割による高速化手法
…‥94
7．4 評価結果．．…．
7．5 まとめ
…………‥101
8．2 将来の展望
参考文献
Vl
1序論
1．1背景
マルチメディア社会の到来にともない，高速なコンピュータや大容量通信システム
などの高速情報処理システムへの需要が急増している．
LSIプロセスの微細化によるLSIの大規模・高密度化ならびに高速化は著しく進んで
いる・VLSIの典型である汎用CPUでは，クロック周波数が500MHzに到達するものが製
品化され，さらに，クロック周波数が1GHzに達するLSIも試作されている．また，従来
は個別のICチップによって構成していたアナログ回路とディジタル回路を同一チップ
上に集積することで動作速度を向上させたAの混載LSIも開発されている【1】．
LSIの設計および動作検証は，多くの場合，回路設計用シミュレータを用いて行われ
ている・このうち，アナログ回路の設計に用いる回路シミュレータは，キルヒホッフ
の電流則・電圧別にもとづく非線形連立微分方程式（回路方程式）の数値解析を行う
機能を持っており，もっとも詳細に回路の挙動を解析できるシミュレータである【2］．
しかし，回路シミュレータは，回路の節点電圧と素子電流の一部を状態変数とする回
路方程式を直接数値解析するため，回路の大規模化にともなう状態変数の増加により，
解析時間が膨大になってしまう．したがって，従来，回路シミュレータは，小規模な
アナログICならびに，A／D混載LSIのアナログ部分に限って使用され，ディジタル回路
だけで構成するVLSIの設計においては，回路の入出力関係に注目して論理検証のみを
行う論理シミュレーションが用いられてきた【3】．
しかしながら，高速アナログ回路と高速ディジタル回路を同一チップ上に集積した
A／D混載LSIの設計においては，アナログ部とディジタル部の相互干渉を解析し，設計
にフィードバックすることが重要となる［1】．また，LSIプロセスの速度限界に迫る高速
LSIの設計においては，LSIを構成する論理ゲートの過渡的挙動を無視できなくなり，
論理ゲートを構成するトランジスタレベルの詳細な解析を行う回路シミュレーション
を適用することが必要となる．さらに，近年，アナログ回路においてもディジタル回
路と同様にハードウエア記述言語の利用による上位レベル設計の研究が行われており
【4】【5】，このようなアナログハードウエア記述言語を用いて設計した回路の検証のため
に大規模回路シミュレータが必要となる．すなわち，今日のLSI設計においては，大規
模回路を現実的な時間で高精度に解析できる次世代回路シミュレータへの需要が非常
に高い【3】【61【7】．
さらに，LSIの実際のシステム内での動作検証においては，ICパッケージや配線板上
に搭載した状態でシミュレーションを行うことが重要である．信号速度の高速化にと
1
もない，信号配線を分布定数回路として扱うことが必要となっている【8】【9】【10】［11】．配
線を伝搬する信号波形を厳密に解析するためには，配線の特性インピーダンス等の物
理定数の周波数依存性を考慮に入れる必要がある．しかし，一般的に配線板上の信号
速度は，特性インピーダンス等をほぼ一定とみなせる周波数領域であることが多く，
この領域では，分布定数線路を微小区間に分割し，各々の区間をインダクタ，抵抗，
容量からなる等価回路で近似する方法で十分であることが多い．このような方法によっ
て近似した配線板とLSIとを一括してシミュレーションし，動作検証を行うためには，
さらに大規模な回路を扱う回路シミュレータが必要となる．
回路シミュレーションの高速化に対し，スパース処理【12】【13】，回路分割
【14】【15】【16】【17日18】【19】【20】【211，緩和法に基づく解析アルゴリズム【22】［23】【24】【25】【26】など
の研究が進められている．しかし，いずれの方法を用いても，解析対象回路の大規模
化に十分に対応できていないのが現状である．
本論文は，LSI単体の回路設計からボードレベルの動作検証まで適用可能な，高速回
路シミュレーション技術を構築することを目的とし，主に高入力インピーダンス／低
出力インピーダンスの基本回路を組み合わせて構成する大規模回路の過渡解析の高速
化を検討する・論理LSIでは，論理ゲートが基本回路であり，論理ゲートは，通常，高
入力インピーダンス／低出力インピーダンスとなるよう設計されているため，本研究
の大規模回路シミュレータを適用可能である．また，アナログLSIならびにAの混載LSI
のアナログ回路部分については，基本回路となる増幅回路，発振回路なども高入力イ
ンピーダンス／低出力インピーダンスとなるよう設計することが普通であることから，
本研究の大規模回路シミュレータを適用できる回路が多いと考えられる．
本論文で検討する回路シミュレータにおいては，解析精度は従来の回路シミュレー
タと同様とし，タイミングシミュレータ等のように，高速化の代償として解析精度を
低下させることはないものとする．また，数値計算の収束性についても従来の回路シ
ミュレータと同様のレベルを確保するものとする．すなわち，従来の回路シミュレー
タを用いたとき，数値計算が収束する回路であれば，本論文の大規模回路シミュレー
タを用いても収束することを条件とする．さらに，本論文では，収束性を，収束まで
に要する反復計算の反復回数で定義するものとする．本定義に従えば，収束性が良い
場合はより少ない反復回数で収束することを示し，逆に，収束性の悪い場合は，収束
までに要する反復回数が多いことを示す．
1．2 回路シミュレーションの概要
回路シミュレーションは，キルヒホッフの電流則・電圧別にもとづく非線形連立常
2
微分方程式
r（す，Ⅴ）＝0
（1．1）
に対して数値解析を行う【2】．ここで，Yは，節点電圧，枝電流等の状態変数ベクトルで
あり，はその時間微分である．一般的に用いられるSPICE【27】等の回路シミュレータ
においては，節点電圧を状態変数とし，電圧源のように枝電流を端子電圧の関数とし
て記述できない素子，ならびに，インダクタのように，枝電流の関数が端子電圧の積
分項を含む素子について，素子電流を状態変数に追加する修正節点解析法【28】が用いら
れる．本論文においても，修正節点解析法に基づく回路方程式を採用するものとする．
回路シミュレータは，通常，動作点解析（DCトランスフア解析），AC解析，過渡解
析などの機能を持っている．動作点解析は，式（1．1）の時間微分項をすべて取り除いた非
線形代数方程式について解析を行う．AC解析は，回路中の非線形素子について，直流
動作点付近の線形等価回路に変換した線形回路網の解析を行う．さらに，過渡解析は，
式（1・1）を直接数値解析するものである．本論文では，このうち，すべての解析アルゴリ
ズムを内包し，もっとも膨大な解析時間を要する過渡解析の高速化を検討する．以降，
特に断らないかぎり，回路シミュレーションとは過渡解析を示すものとする．
式（1・1）の数値解析アルゴリズムは，以下に述べるように，直接法【2】に基づくアルゴリ
ズムと，緩和法【25】に基づくアルゴリズムの2種類に大別される．以下に従来用いられ
てきた直接法による回路シミュレーション手法と，大規模回路を対象として研究され
ている回路分割手法，ならびに，緩和法による回路シミュレーション手法について概
説する．
1．3 直接法による回路シミュレーション
直接法では，図1．1に示すように，式（1．1）に対して，グローバルタイムステップ数値
積分を適用して
ヤ→
vr−ⅤトAJ
（1．2）
AJ
とし，時刻tにおける状態変数のみの非線形連立代数方程式
F（中（
vJ−ⅤトAr
（1．3）
3
を得る・ここで，AJは数値積分の時間刻み，Yrは時刻tにおける状態変数ベクトルで
ある・さらに，式（1．3）にニュートン法を適用し，線形連立代数方程式
J（Ⅴ当・Ⅹ＝−中当
Ⅹ＝VJ，た＋1−VJ，た
を繰り返し解くことによって解Yrを求める．ここで，Ⅴ竹は，時刻tのk回目の
ニュートン反復における状態変数ベクトルであり，行列Jはヤコピアン行列（回路行列）
項Ⅴ当＝
（1．6）
Ⅴ＝VJ，た
である．
数値積分法
非線形連立常微分方程式
（回路方程式）
r（す，Ⅴ）＝0
′一一■−■−■
「∵∴∴∴配
非線形連立代数方程式
ニュートン法
r■■−■
l
I
l
：線形連立方程式
J（Ⅴ当・Ⅹ＝−F（Ⅴ当
l
l
− − − − − ■■
Ⅹ＝VJ＋1−VJ，た
項Ⅴ当＝
Ⅴ＝VJ，た
解析解
（過渡応答波形）
図1．1直接法による過渡解析
4
回路解析では，式（1．4）はLU分解等の三角化分解と前進・後退代入によって解く．通
常の回路には局所結合性があるため，回路行列Jは要素の大部分がゼロ要素であるスパー
ス行列である．全要素に対するゼロ要素の比率（スパース率）は，回路が大規模であ
るほど大きくなり，LSIでは95％以上となる．
密行列の三角化分解には行列の次元Nの3乗オーダの計算量が必要であり，状態変数
の数と同じ次元の大規模行列の三角化分解を必要とする回路シミュレーションに密行
列と同じ手法を適用することは現実的でない．そこで，回路行列のスパース性を利用
して，計算量を削減するスパース処理手法【12】【13】が検討された．スパース行列の三角
化分解に際しては，ゼロ要素が三角化分解の過程で非ゼロ要素となるフィル・インの
問題が発生する．スパース処理手法においては，ゼロ要素に村する計算を省略するこ
とを基本として，フィル・イン抑制のためのピボット順序の最適化を組み合わせ，三
角化分解の計算量をNl・2∼Nl・5オーダまで減少させることができる．
しかし，従来のスパース処理手法における計算量の削減効果は，フィル・イン要素
の数に極めて強く依存するが，ピボット順序の完全な最適化にはN！オーダの処理時間
が必要であるため，大規模回路のシミュレーションに直接通用することは困難である．
さらに，従来のスパース処理手法を適用すると，回路行列の非ゼロ要素がランダムに
出現するランダムスパース行列となるため大規模回路行列をその大きさのままで処理
する必要が生じると同時に回路行列が本来持っていた並列処理性を失ってしまう問題
がある．したがって，従来のスパース処理手法だけで大規模回路シミュレーションの
三角化分解を高速化することは極めて困難である．
1．4 大規模回路シミュレーションのための回路分割
回路の大規模化に対応し，解析対象回路を部分回路に分割して解析するアルゴリズ
ムが注目されている・分割した部分回路は，独立してシミュレーションできるため，
回路規模が縮小され，取り扱いが容易になるとともに，並列処理性が向上する．すな
わち，大規模回路シミュレーションにおいては，回路分割が必須となる．
直接法に基づく回路シミュレーションに適用する回路分割手法として，回路行列の
分割を対象とした節点分割手法【16】【17】［20】【26】ならびに枝分割手法【29］が用いられる．前
述のように，修正節点解析法では，状態変数は節点電圧と考えることができるため，
直接法における回路分割手法として，節点分割を考えればよい．節点分割は，回路内
の複数の部分節点を局所基準節点として選択することにより回路を分割するものであ
る・局所基準節点に対応する行と列を行列の縁部分に集めることにより，回路行列は，
図1・2に示す縁付きブロック対角（borderedblockdiagonal：BBD）構造となる．BBD行列で
5
は，各対角ブロックが部分回路内部の情報に対応し，縁の部分が部分回路相互の接続
に対応する．BBD行列の三角化分解に際しては，フィル・インの発生場所が対角ブロッ
ク内部と縁部分に限定されるため，複雑なピボット順序の最適化をすることなく，フィ
ル・イン発生率を効率よく抑制することができる．同時に，各対角ブロックごとに三
角化分解を独立に実行できる特徴もある．しかし，最後に各ブロックの情報を基に，
局所基準節点に対応する縁部分の三角化分解の計算が必要であり，完全に回路を分割
しているとはいえない・したがって，直接法によって取り扱える回路規模には，シミュ
レーションの所要時間や計算機のメモリ量などの制約に起因する上限が存在すること
になる．
M
l
P l
0
P 2
M 2
M
3
P 3
ヽヽ
ヽヽ
ヽヽ
ヽ
QTl
l
l
l
l
l
l
l
ヽ ヽ ヽヽ
Q T2
QT3
R
図1．2 縁付きブロック対角行列
1．5 緩和法による回路シミュレーション
節点分割法が部分回路間の接続情報を保ったまま回路分割する方法であるのに対し，
緩和法【22】【23】【24】［25】【26】は，回路シミュレーションで扱う連立方程式のレベルで回路分
割を行うアルゴリズムであり，大規模回路を相互に接続のないより小規模な回路へ分
割して取り扱う手法と考えることができる．すなわち，各部分回路の外にある節点を
定数（独立電源）と考えて部分回路の数値計算を独立に行い，その結果を用いて独立
電源の値を更新する処理を，全ての状態変数の値が動かなくなるまで反復するアルゴ
リズムである．以下，緩和法における反復計算処理を緩和反復と呼ぶ．各部分回路の
解析は完全に独立して実行できることから，並列処理性が高く，また，一度に取り扱
う回路を縮小できるため，大規模回路解析には適していると考えられている．
6
回路方程式（1・1）のレベルに適用する緩和法が図1．3に示す波形緩和法【23】であり，各部
分回路方程式の組に対して，異なる時間刻みによる数値積分を適用できるマルチレー
ト性を利用できる特徴がある・これは，高速動作する部分と，比較的低速で動作する
部分を含む大規模回路を別個の時間刻みで効率よく解析できる可能性を持ったアルゴ
リズムであるといえる・しかしながら，波形緩和法においては，部分回路外部の節点
の応答波形を独立電源の電源波形として取り扱うことから，その初期値を最適に決定
することは事実上不可能である．したがって，各緩和反復において回路シミュレーショ
ンの開始時刻に近い方から順に正しい解が確定していく現象が起こる［30】．このことは，
初期の緩和反復においては，解析の時間ウインドウの後半に近くなるほど無駄な計算
を実行することを意味し，逆に，緩和反復末期においては，時間ウインドウの前半で
無駄な計算を実行することを意味している．この現象は，大規模回路内に局所的な帰
還ループが存在する場合に最も顕著に現れる．
図1．3 波形緩和法による過渡解析
7
回路方程式にグローバルタイムステップ数値積分を適用した後の非線形連立代数方
程式（1・3）に対して回路分割を行う緩和法は反復タイミング解析［22］と呼ばれる．図1．4に
示すように，反復タイミング解析においては，各部分回路ごとにニュートン法を適用
するため，ニュートン法の収束性が良い部分回路については，少ないニュートン反復
で解が求まる特徴がある・また，各時刻の解析において，節点電圧ベクトルの初期値
は，前の時刻の収束解を用いることができるため，無駄な緩和反復を行う可能性は波
形緩和法より低くなる・一方で，大規模回路全体を同じ時間刻みで解析する必要が生
じる．
過渡応答波形
図1・4 反復タイミング解析による過渡解析
8
線形緩和法は各ニュートン反復における式（1．4）の三角化分解に緩和法を適用するもの
である・したがって，大規模行列の三角化分解を行う必要はないが，大規模回路全体
に一括してニュートン法を適用するため，ニュートン法の収束性が悪い部分回路に対
するニュートン反復回数が全体のニュートン反復回数を決定してしまい，大規模回路
に対して効率的な手法であるとは言いがたい．
緩和法に基づく回路シミュレーションにおいては，部分回路外部の回路の影響を完
全に無視してしまうことになるため，部分回路間の相互作用が小さい分割点を適切に
決定しないと，緩和反復回数が膨大になってしまうことが知られている【311［32］【33】．特
に，回路を節点1個単位で扱う節点緩和アルゴリズムにおいては，非常に多くの反復
回数が必要で，結果として，直接法を用いた場合より解析時間が膨大に増加すること
が知られている・節点緩和アルゴリズムの収束性は，回路行列の対角優位性に依存す
し【25】，MOS回路網など，一般に対角優位性が保証される回路も存在するが，バイポー
ラトランジスタ回路を含めた回路網全てについて回路行列の対角優位性を常に保証す
ることはできない．一方，複数の節点を含む部分回路に分割するブロック緩和アルゴ
リズムでは，部分回路行列の三角化分解が必要となる反面，緩和反復の収束性が節点
緩和アルゴリズムより向上し，緩和反復回数を削減することが可能となるが，節点緩
和アルゴリズムと同様に適用可能な回路が限定されることが知られている．したがっ
て，本研究の目的とする大規模回路シミュレータには，従来の緩和法を直接適用する
ことはできない．
1．6 潜在性とマルチレート性の利用による高速化
実用的な時間で大規模回路の解析を行う回路シミュレーション技術の構築に対し，
近年の研究で特に回路の持つ潜在性【14】【15】【17］とマルチレート性【231【26】を生かした高速
化手法が注目されている．
大規模回路においては，ある時刻に状態が変化している部分回路または素子は少な
く，ほかの部分回路は単に前時刻と同じ状態を保持する不活性（潜在的）状態にある
場合が多い・この時間領域潜在性を利用することで潜在的状態にある部分回路の計算
を省略し，回路シミュレーションを高速化することが可能となる．一般に，大規模回
路の潜在率は90％を越えるといわれており，時間領域潜在性を利用することで大幅な高
速化が期待できる．時間領域潜在性をもっとも効率よく利用できるのは，部分回路ご
とに異なる時間刻みで数値積分できる波形緩和法である．
また，各時間ステップのニュートン反復ならびに媛和反復において，前反復と現反
復で状態の変化しない部分が発生する反復領域潜在性も利用可能である．
9
直接法による回路シミュレーションでは，回路全体を一括して取り扱うため，回路
内の一部分でも活性状態にあれば，その時間ステップに対する解析を行う必要があり，
また，ニュートン反復中においても，一部分でも変化すれば，三角化分解を再度実行
することが必要となる・したがって，直接法による回路シミュレーションにおいて時
間領域あるいは反復領域の潜在性を効率的に利用することは難しい．
1・7従来技術の大規模回路シミュレーションへの適用性
以上述べてきた各手法の長所および短所をまとめると表1．1のようになる．また，本
研究の回路シミュレータへの要求とそれを実現するために適した解析手法をまとめて
図1・5に示す・表1．1，図1．5のように，従来から提唱されてきた回路シミュレーションア
ルゴリズムを用いて，本研究の目指す大規模回路シミュレータを構築することは非常
に困難である・すなわち，直接法では，各時刻の解析が最も収束しやすい回路シミュ
レータを構築でき，多くの回路で収束性が良好である反面，回路の大規模化にともなっ
て，回路行列の三角化分解に必要な時間が急激に増大する欠点があり，従来のピボッ
ト順序の決走法と逐次計算アルゴリズムを直接使用することができなくなる．また，
完全な回路分割が不可能であるため，並列処理による高速化が困難であると同時に，
取り扱える回路の大きさが，計算機のメインメモリ構成等によって制限を受けてしま
う・さらに回路全体を一括して取り扱うため，潜在性の効率的な利用が難しい．一方，
緩和法は・回路を完全に分割して計算可能であり，補助記憶装置の利用等によって取
り扱い可能な回路規模の上限を実用上十分なレベルまで引き上げることが容易になる
と同時に，潜在性を効率的に利用でき，並列計算の適用も容易である．しかし，緩和
反復の収束性が直接法に比べて低く，収束しない，すなわち，解析不能なケースが多
く発生し，かつ，収束する場合においても反復回数の増加に伴う計算時間増大の問題
がある・そこで，直接法と緩和法の長所を融合した直接法・緩和法混合モード解析手
法【34】【26】や・回路分割箇所を動的に決定する混合モード解析アルゴリズムが注目を集
めている［34】【35】【361【37】・さらに，直接法をベースとし，階層分割を適用した混合モー
ド大規模回路シミュレータ【38】【39】【40】【41】【42】【43］【44】【45】【46】【471【48】も研究レベルではあ
るが，構築されてきている．しかし，従来検討されてきた混合モードシミュレータの
シミュレーション効率は，回路の分割点を決定するアルゴリズムに強く依存し，一般
的な回路への適用例もまだ十分とはいえないなど，研究途上にあるものである．
10
表1．
1 直接法 ・緩和法の長所 と短所
緩和法
（
波形緩和法，反復 タイミング解析）
直接法
収束性が良好
長 収束する回路が多い
所 適用回路を選ばない
大規模回路 を分割 して解析する
部分回路ごとに異なる時間刻みを適用
可能 （
波形緩和法）
潜在性の利用が容易
並列処理性が高い
大規模回路 を一括 して解析
収束性が悪い
短 回路全体を同一時間刻みで解析 部分回路数が増えるほど収束性が劣化
所 潜在性の利用が困難
収束 しない回路が多い
並列処理性が低い
適用可能な回路が限られる
図1・5 大規模回路シミュレータへの要求条件と解析手法の対応
1．8 本研究の目的
本研究においては，直接法と緩和法の長所を生かしつつ，それぞれのアルゴリズム
が持つ問題点を解決し，大規模回路シミュレータを構築する手法を提案する．本論文
では，大規模回路シミュレータを構築するための要素技術として，直接法による大規
模回路シミュレーションの高速化に有効な専用並列計算機と，過渡解析に先立って行
われる直流動作点解析の高速化に有効な，簡易な区分線形素子モデルを提案する．さ
らに，直接法では取り扱えない規模の大規模回路を高速に解析できる波形緩和アルゴ
リズムならびに反復タイミング解析アルゴリズムを提案する．
図1．6に本研究の回路シミュレータ構成を示す．
11
低速部分回路
l
反復タイミング解析
非線形
抵抗回路網
非線形 非線形
抵抗回路網 抵抗回路網
非線形
抵抗回路網
I
I
直接法
直接法
図1．6 本研究の大規模回路シミュレータ構成イメージ
本論文で提案する回路シミュレータは，解析対象の大規模回路を機能ブロックレベ
ルの極めて大きな部分回路に分割して波形緩和法を適用し，回路のマルチレート性を
利用した高速化を行う・さらに，各機能ブロックの解析においては，直接法の適用限
界のサイズに再度回路分割し，得られた部分回路間で反復タイミング解析を通用する
とともに，各部分回路の解析に大規模回路への適用性を向上させた直接法を適用する
ことで，回路全体に直接法を適用した場合と同等の収束性を確保すると同時に高速化
を達成することをめざす．すなわち，緩和法を適用する部分回路の規模を決定するた
めには，直接法の適用限界となる回路規模をどの程度改善できるかを見積もる必要が
あり，さらに・波形緩和法を適用する機能ブロックの大きさを決定するためには，反
復タイミング解析の特性を明らかにすることが必要となる．したがって，本論文では，
12
シミュレーション実行手順とは逆に，直接法，反復タイミング解析，波形緩和法の順
にそれぞれの高速化手法を提案する．
実用的な回路シミュレータにおいては，適用する回路の種類に依存しないで各時刻
の反復計算を良好に収束させることが必要となり，そのためには，直接法の適用が有
効であることから，大規模回路に通用できる直接法ベースの高速回路シミュレーショ
ンシステムを構築することが必要であると考えられる．この高速回路シミュレーショ
ンシステムにおいては，大規模な回路行列の構造を評価することなく効率的にフィル・
インを抑制できると同時に，一度に取り扱う回路行列の大きさを縮小できる節点分割
法を回路分割手法として用いることが有効である．さらに，スパース行列の三角化分
解を高速に実行するための専用ハードウエアを持つLU分解専用並列計算機【491【50］【51】
により従来の逐次計算を大幅に上回る分解計算速度を達成することが重要と考えられ
る・また，過渡解析に先立って行う動作点解析においては，素子モデルの計算時間が
長いダイオードやバイポーラトランジスタについて，ダイオード特性を順バイアス領
域と逆バイアス領域の2区間を理想スイッチを含む簡易等価回路で区分線形近似する
とともに，この理想スイッチの状態を求める区分線形解析手法を適用することにより
真の動作点に近い粗い解を効率的に求めることができる【52］．この区分線形等価回路を
適用して求めた租解をニュートン反復の初期値として用いることで，ニュートン法の
2次収束性を効率的に利用でき，解の精度を落とすことなく動作点解析を高速化でき
る・これら2つの要素技術を適用することにより，従来の直接法ベースの回路シミュ
レータでは膨大な時間が必要であった数十万節点から100万節点クラスの大規模回路シ
ミュレーションを実用的な時間で実行できる高速回路シミュレーションシステムの構
築をめざす．
さらに，上述の直接法ベース高速回路シミュレーションシステムで取り扱えない大
きさの大規模回路については，部分回路単位の反復タイミング解析の適用が有効であ
ると考えられる・しかし，反復タイミング解析では収束しない回路が多くあり，収束
する回路の場合においても緩和反復回数が非常に多く必要となる問題を解決すること
が必須となる・近年，線形緩和法において，各部分回路の境界付近に位置する節点を
隣接する部分回路に重複して含ませるように回路分割するオーバーラップ分割を適用
することで，従来法では収束しない回路についても収束させることができ，収束する
場合においては緩和反復回数が大幅に削減できることが報告されている．本研究では，
このオーバーラップ分割を反復タイミング解析に通用すると同時に，解析実行中にオー
バーラップ分割の分割点を動的に変化させることによりさらに収束性のよい反復タイ
ミング解析を行うアルゴリズムを構築する【531．この新しい反復タイミング解析手法を，
部分回路のサイズが各々数十万節点から100万節点となるように適用し，各部分回路に
13
対するニュートン反復ついて，上述の直接法ベース高速回路シミュレーションシステ
ムを適用すれば，直接法のメリットである広範な回路への適用性と良好な収束性を保っ
たまま，数百万節点クラスの大規模回路シミュレーションが可能になると考えられる．
また・大規模回路内におけるマルチレート性を有効に用いるためには，波形緩和法
の適用が有効である・波形緩和法は，1・5節に述べたように，特に回路内に局所的な帰
還ループが存在する場合に解析効率が劣化する．これは，波形緩和法を適用する部分
回路の数が多くなるほど発生しやすくなると考えられる．そこで，本研究においては，
解析対象の大規模回路を多くとも数十個程度の部分回路に分割して波形緩和法を適用
することを考える・すなわち，リセット回路や制御回路など，直流に近い動作速度を
もつ部分回路をまず分割し，次いで，主信号系の中でも，動作速度の大きく異なる部
分回路に大きく分割することにより，波形緩和法を適用する部分回路の規模を数百万
節点程度までとする・各部分回路は，前述の改良反復タイミング解析により，さらに
回路分割して解析することができる・さらに，本研究では，局所的帰還ループの存在
による解析効率の劣化を積極的に補償することを目的として，局所帰還ループを構成
する部分回路の緩和反復を集中して行う新しい波形緩和アルゴリズムを構築し，マル
チレート性をさらに効果的に利用できる大規模回路シミュレータを構築する【30】．
本論文においていくつかの回路シミュレーション手法を提案し，その計算速度評価
を行っている・これらの評価用シミュレーションプログラムにおいては，特に断らな
いかぎり，数値積分法として後退オイラー法【54】を用いる．また，修正ニュートン法の
ようなニュートン反復における近似値修正量の操作【54］【55］は行わないものとする．
テユートン反復・ならびに，緩和反復の収束判定条件は，回路方程式に近似値を代入
して得られるベクトルの2乗ノルム【56］が規定の値以下となることとしている．さらに，
三角化分解法としては，ガウス消去あるいは外積型ガウス法によるLU分解［57】【581を用
いている．
以下，第2章で，回路シミュレータ開発用支援ツールASSI叩59】を提案する．
ASSISTは，研究用回路シミュレータ開発のための共通環境を実現することを目的とし
て，ハードウエア記述言語HAL【60】をベースに構築されており，回路図入力から回路シ
ミュレーションに必要な回路方程式，行列構造といった情報を出力するツール群を備
えている・さらに，回路シミュレーションの実行時に必要となる素子モデル計算サブ
ルーチンや回路行列の三角化分解サブルーチン等をライブラリの形で提供し，シミュ
レーションアルゴリズム本体を記述するだけで容易に回路シミュレーションプログラ
ムを作製することができる．ASSISTを用いて従来法に基づく回路シミュレータと新し
く提案するアルゴリズムに基づく回路シミュレータの両方を作製すれば，シミュレー
ションアルゴリズムを除く周辺ルーチンを共通化できる．したがって，それらの実行
14
結果を比較することにより，アルゴリズムの違いによる解析解の精度や実行時間の差
異を明らかにできる．
第3章では，大規模スパース行列のLU分解を高速に実行できるLU分解専用並列計算
機SMASHl49］を提案する．sMASHは四則演算のみを行う簡易なプロセッサをクラスタ
分割することによって高度の並列計算を行う．各プロセッサは単純な計算に特化され
ているため，ソフトウエアによる煩雑な制御を必要としない．また，スパース行列を
メモリに格納する際，ゼロ要素を無視して，非ゼロ要素とフィル・イン要素のみを各
行ごとに，列番号情報とともに格納する方法がとられろため，LU分解実行時に列番号
整合操作を行う必要が生じるが，SMASHは，巡回シフトを用いて列番号整合操作を高
速に実行する専用回路を備えており，列番号整合に伴う計算効率の劣化を最小限に抑
えることができる．
次いで，第4章において，SMASHを制御し，回路行列データや計算結果の転送，取
り出しを行うホスト計算機と組み合わせて動作させる，実際の利用形態に近い状態で
の評価結果を示す［50】．
さらに，第5章において，ダイオードの非線形特性をスイッチと電圧源および抵抗
を用いた2区間で区分線形近似し，スイッチのON／OFF，すなわち，ダイオードの順バ
イアス，逆バイアス状態をシミュレーションすることで，非線形関数の数値代入計算
を行うことなく効率的に直流動作点の租解をもとめることができる区分線形シミュレー
ション手法【52】を提案する・第3章で提案するスイッチを含むダイオードモデルは，従
来，スイッチレベルシミュレーションで用いられていたダイオードモデルに改良を施
し，区分線形モデルとすることによって，スイッチレベルシミュレーションで生じて
いた非正則問題を回避できLU分解専用並列計算機の利用が可能になるとともに，従来
モデルで問題となっていたリミットサイクルへの縮退問題の発生が緩和される．以上，
第3章から第5章までは，直接法に基づく回路シミュレーションの高速化手法を提案
するものである．
第6章では，直接法で取り扱えない大きさの大規模回路網に対して適用可能な反復
タイミング解析の収束性改善手法【53】を提案する．これは，回路分割の際に，各部分回
路の境界付近に存在する節点と素子を，隣接する部分回路に重複して含ませるように
オーバーラップ分割し，このオーバーラップ部分によって，部分回路に含まれない外
部回路の影響を近似するものである．オーバーラップ分割の適用により，緩和反復の
収束性が向上し，緩和反復回数が減少する．すなわち，本手法によって，直接法を適
用できない規模の大規模回路についても直接法と同等の良好な収束性・高速性を維持
したまま大規模回路シミュレーションが可能となる．
15
第7章では，マルチレート性を利用できる波形緩和法の計算効率改善が可能な局所
反復波形緩和アルゴリズム【30】を提案する・これは，部分回路間で局所的帰還ループを
構成する場合に，全体の解析時間ウインドウより短いウインドウ幅を設定して，局所
的帰還ループを構成する部分回路間でのみ緩和反復を実行するアルゴリズムである．
本アルゴリズムの適用によって，特に解析時間ウインドウの後半で収束性が劣化する
問題を回避でき，波形緩和法の計算速度を改善できることを示す．
最後に第8章において将来的展望を述べ，本論文のまとめとする．
16
2 回路シミュレータ開発用支援ツールASSIST
2．1概要
近年の集積回路技術の進歩にともない，高度な回路シミュレータの需要が高まって
いる・これに対して，最近の研究ではいくつかのアルゴリズムが提案され，その評価
が行われている・一般的に，回路シミュレーションプログラムは，回路を構成する素
子モデルの特性を記述する関数のモジュールと回路方程式，即ち，非線形常微分方程
式を解くアルゴリズムを記述するモジュールから構成されると考えられる．これらを
細分化すると解析アルゴリズムの中には複数の手法で共通して用いられる処理が存在
する．
従来・アルゴリズム評価用の比較的小規模な回路シミュレータは個別に素子モデル
を記述するモジュール群やアルゴリズム本体を記述するモジュールを用意して開発さ
れるかあるいはSPICE【27樺の既存のシミュレータに組み込む形で開発されていた．こ
の方法では，プログラミングに要する労力が大きく，プログラムの巧拙によってシミュ
レータの性能が大きく左右されるばかりでなく，プログラムの信頼性を確保すること
が難しくなる・また，新しいアルゴリズムを評価する場合，既存のアルゴリズムを用
いたシミュレータとアルゴリズム本体を除くモジュールを同一とする必要があるが，
従来の方法では全てのモジュールが専用化されている場合が多く，また，その内部仕
様が公開されていないため，不可能であることが多い．したがって，回路シミュレー
タを開発するための標準ツールの構築が必要である【6】．本章では，回路シミュレータ
開発支援ツールASSISTを提案する【59］．ASSISTはC言語を用いて記述されたライブラ
リとツール群から構成され，回路のネットリストを入力としてツール群によって生成
された回路情報ファイルを基にライブラリ内の関数を用いてシミュレーションプログ
ラムを構築する・ASSISTは回路に対応する回路方程式を求め，節点電圧等の情報をパ
ラメータとして回路方程式を構成する関数の示す値を求める機能を基本として構成さ
れている・したがって，関数値を基にした数値微分によりヤコピアン値の導出も容易
に行うことができる．
ツール群はテキスト形式のファイルを入力としてテキスト形式の出力ファイルを生
成する・ファイルの形式に矛盾しない限り内部処理は自由に実行することができる．
ライブラリは主に素子モデルの特性を記述するモデルライブラリと解析アルゴリズ
ムのプログラム化のためのプログラミングライブラリから構成される．ライブラリ中
においてハードウエアに依存するモジュールは別個に記述されているため，異なるハー
ドウエアへの移植が容易である．モデルライブラリ内のモジュールは全て同一の引数
17
を用いて参照され，その追加も容易にできるように考慮されている．また，不要な素
子モデルに対してはシステムテーブル中からそのモデル名を削除すればユーザプログ
ラムにリンクされなくなる・モデルライブラリ中のモデル関数は引数として与えられ
たモデルの端子に流れる電流値を求めて返す・ツール群によって生成された回路情報
ファイルの各節点毎のモデル接続情報にしたがってモデル関数を呼び出し，その返値
の和を計算することで回路方程式に含まれる関数の値を求めることができる．プログ
ラミングライブラリは基本的に直接法によるシミュレーションプログラムを構築する
ことを想定して各処理をモジュール化して組み込んでいる．各モジュールの構成やデー
タ形式に従えば，ユーザの作成したモジュールを組み込むことが容易にでき，拡張性
が高い．
ASSISTには，原形の発淘59］以来，いくつかの拡張・改良【61］［46］［62］が加えられてい
る・しかし，本研究で用いているのは，原形をベースに必要なツール・モジュールを
追加したものである・したがって，本章では，原形のASSISTについて述べることとし，
章末で原形からの改良点および，ASSISTを用いて開発された研究用シミュレータにつ
いて述べる．
2．2 回路方程式の導出
回路シミュレーションの目的は
r（す，Ⅴ）＝0
（2．1）
を満たす節点電圧Ⅴ（t）を求めることであり通常数値積分法を用いて差分化した式
F畔r〔
vr−ⅤトAJ
ヰ0 （2・2）
を各々の時刻tについて解いて解を得る．回路中に非線形特性を持つ素子が存在する
場合，式（2・2）を解くためにニュートン法が用いられ，ニュートン反復の各ステップで現
時刻の節点電圧Ⅴ悠前時刻の節点電圧ⅤトAJを引数として式（2．2）を評価する必要がある．
すなわち，各々の節点について接続されている素子枝に流れる電流の和を求めること
が必要となる・例えば図2．1に示すように，節点②について素子a，b，。に流れる電流
扉占亮を節点電圧作り，巧をパラメータとして求め，その和を計算する必要がある．
ASSISTは鞄2・2）を評価するために素子に流れる電流を求める関数のライブラリと，各
節点毎に素子の結合情報を生成するツール群により構成する．
18
図2．1回路方程式の導出
2．3 回路シミュレータ開発支援システムASSIST
2．3．1ASSISTの構成
ASSISTは図2・2に示すように回路情報生成ツール群とライブラリから構成される．ツー
ル群は・構造記述言語HAL【60】を入力としてオーダリングを行い，最終的に回路情報ファ
イルを生成する・ライブラリ中のプログラミングライブラリは，この回路情報ファイ
ルと行列構造ファイルを参照して動作する．また，ツール群はライブラリ内のモ
ジュールを用いてプログラムされている．ASSISTのツール群は全て入力ファイルとし
てテキスト形式のファイルを用い，出力もテキスト形式のファイルである．したがっ
て・ツールの内部処理を変更することが容易であり，標準以外のツールを作成するこ
とができる・ASSISTは有限数の基本モジュールで構成される回路を扱うことを想定し
ている・デジタル回路では基本モジュールがゲートに相当し，アナログ回路では基本
モジュールが回路素子に相当する．
2．3．2回路入力および構造記述言語HAL
回路入力は回路図エディタGRACEl60］，または，OrCADl63］を用いて行う．入力され
た回路は階層構造を記述できる構造記述言語HALに変換される．図2．3に示す回路に対
するHALリストの例を図2・4に示す・GRACEを用いた入力では，HALの文法にしたがっ
た出力ファイルが直接得られるが，OrCADを用いた入力では標準出力形式であるEDIF
ネットリストから変換ツールを用いてHALリストを得る．ASSISTでは，HALリスト中
19
にある回路モジュールを基本モジュールの組合せとして認識する．HALリスト中にお
ける基本モジュールは，図2・4のLEVELlブロックに記述されたモジュールである．
LEVEL2・LEVEL3のモジュールは別のHALリストで定義されるマクロモジュールであ
り・リンクツールHALLINKによって1階層HAL（LNK）ファイルに変換される．図2．3の
回路のLNKファイルを図2・5に示す・LNKファイルでは元のHALリスト中にあったコメ
ントなどの不要部分が削除される．
2・3・3オーダリング及び基本モジュール定義ファイル
リンクツールによって出力されたLNKファイルは，標準オーダリングツールMCMTX
によってオーダリングされ，節点情報（MTX）ファイルが出力される．図2．3の回路に対
するmxファイルを図2・6に示す・MTXファイルは各々の基本モジュール内部の節点に
オーダリングを行った結果の情報を持つ．MCMTXは単純なオーダリングを行うツール
でありJl階層HALリスト中の基本モジュールに対し，出現順にオーダリングを行う．
また・基本モジュールの構成についてはユーザが基本モジュール定義（腫T）ファイル中
で行う・MCMTXの他，特殊なオーダリングを行うツールとして自動階層節点分割ツー
ルMRBBD【38】【39】【40】が完成している．
NETファイルはユーザがテキストエディタを使用して作成するファイルであり基本
モジュル内部の構造を記述する．NETファイルを参照することで基本モジュールレベ
ルの回路記述を素子レベルに変換することができる．バイポーラトランジスタを用い
たゲートのNETファイルを図2．7に示す．
20
AS SI STの構成
一・・1苫警A。E
回路図エディタ
●EDI F2HAL
ヽ
ヽ
ヽ
ネットリスト変換ツール
ヽ
ヽ
ヽ
・、、 ●DOCGEN
＼ ドキュメント生成ツール
、●HALLINK
．．・・・・・・・●MCMTX
オーダリングツール
．●FGEN
．．・／回路情報生成ツール
．．・．’JMKMTS
．′’行列情報生成ツール
′
■
■
′プログラムライブラリ
●機種別関数ライブラリ
●モデル作成支援ライブラリ
●モデルライブラリ
●レベル1ユーザプログラム
ライブラリ
●レベル2ユーザプログラム
ライブラリ
●入力信号ライブラリ
図2．2 ASSISTの構成
21
芸P官
図2．3 回路例
ファイル：sr且hal
NAME：SR−FF
LEⅥ乱O
DATA：
begin
end
USER＿NAME：
PURPOSE：
LEⅦ：Ll
ELEMENT NUMBER
begin
LEⅥミL O
OOllINPUT［1］
LO＿MOD
0021INPUT［2］
nunber＝000
LEVELl
00引INPUT［3］
INPUT
number＝003
001（OUTPUT［4］
number＝002
00210UTPUT［5］
0UTPUT
LlJMOD nu血ber＝002
LINE
0011NAm［1，2；6］
0021M［1，3；7］
end
number＝000
CONNECT
number＝000
LEⅥ王L2
L2⊥MOD
LEVEL2
begin
number＝000
LEⅥ王L3
L3＿MOD
end
LEⅦ：L3
nuhber＝001
h仏IN［］
ROOT：h仏IN
begin
OOl圧f［6，7；4，5］
ELEMENT STRUCTURE
end
NUMBER NAME［NODE］
図2．4 HALリストの例
22
ファイル：srff．lnk
NA肥：h仏IN［］
ROOT：MAIN
M肥：0011ff［6，7；4，5］
ROOT：001lff＜MAIN
LEⅥ王LO
LEⅥ王LO
begin
end
begin
end
LEVELl
LEⅥ王Ll
begin
begin
OOIIINPUT［1］
OO引NAm［6，5；4］
002ⅧⅣUT［2］
003ⅧⅣUT［3］
00引NAm［7，4；5］
end
001JOUTPUT［4］
LEⅥ王L2
002rOUTPUT［5］
begin
0011N皿D［1，2；6］
end
0021MND［1，3；7］
LEⅥミL3
end
begin
LEⅦ：L2
end
begin
end
LEVEL3
begin
OOlはf［6，7；4，5］＊
end
図2．5 LNKファイルの例
23
ファイル：srff．mtx
Output＿nOde
EXT＿OUTPUT（1）＝4
EXT＿OUTPUT（2）＝5
＞NA肥：NAm［1，3；7］1002
＞S¶収T：8
＞NODE：7
● ● ● ● ● ● ● ● ● ● ● ● ● ●
EXTJNPUT（3）＝3
︶ ︶ ︶ ︶ ︶ ︶ ︶
5 6 7 8 9 0 1
1 1 1 1 1 2 2
︵
︵
︵
︵
︵
︵
︵
EXTJNPUT（2）＝2
＞ⅠⅣUT（1）：6；7
＞INPUT（2）：5；28
︶ ︶ ︶ ︶ ︶ ︶ ︶
1 2 3 4 5 6 7
︵
︵
︵
︵
︵
︵
︵
＞ ＞ ＞ ＞ ＞ ＞ ＞
EXLIⅣm（1）＝1
● ● ● ● ● ● ● ● ● ■ ● ●
InpuLnode
︶
︶
︶
︶
︶
︶
2 3 4 5 6 7
︵
︵
︵
︵
︵
︵
Dimension＝28
︶
︶
︶
︶
︶
︶
2 3 4 5 6 7
︵ ︵ ︵ ︵ ︵ ︵
＞ ＞ ＞ ＞ ＞ ＞
−Node＿information
＞OUTPUT（1）＝7：7；14
＞NA肥：NAm［7，4；5］用04
＞INPUT（1）：1；INPUT［1］
＞START：22
＞NODE：7
胤［7］＝舶TRIX（14）
＞ⅠⅣUT（2）：3；ⅠⅣm［3］
＞（1）：（8）
mL［4］＝舶TRIX（21）
＞（2）：（9）
鮎L［5］＝鮎TRIX（28）
＞（3）：（10）
＞（4）：（11）
＞ⅠⅣUT（1）：7；14
＞ⅠⅣUT（2）：4；21
Reration＿MATRIX＿＆＿胤
mL［6］＝舶ⅧⅠⅩ（7）
−Node＿information＿end
＞NA肥：NAm［1，2；6］1001
＞START：1
＞（1）：（22）
＞（5）：（12）
＞（2）：（23）
＞（6）：（13）
＞（3）：（24）
＞（7）：（14）
＞（4）：（25）
＞NODE：7
＞（5）：（26）
＞INPUT（2）：2；INPUTl2］
＞NAME：N心の［6，5；4］1003
＞S¶収T：15
＞NODE：7
＞（1）：（1）
＞OUTPUT（1）＝7：4；21
＞OUTPUT（1）＝7：6；7
＞INPUT（1）：1；INPUT［1］
＞OUTPUT（1）＝7：5；28
＞（6）：（27）
＞（7）：（28）
′ヽ
図2．6 MTXファイルの例
ファイル：bipolar．net
CONSTANTIEVERS＿NPN：NPN＝11．Oe−15，100．0，￥
NAME：N瓜田
1．0，1．Oe−12，0．8，0．5，￥
NODE［7］
0．5e−12，0．7，0．5，1．Oe−10，￥
OUT（1）＝［N7］
1．Oe−8，0．02引
IN［2］
CONSTANTlPOWER：VCC＝制
くMODEL：MCAP＞
CONSTANTIPOWER：GND＝iot
＋EⅧRS」WN2［Nl；N2；Il；Ⅰ2］＝ⅣN
CONSTANTILINER＿R：4K＝140001
＋LINER＿R［VCC；Nl］＝4K
CONSTANTJLINER＿R：2K＝12000t
＋LINER＿R［VCC；N3］＝1．6K
CONSTANTILINER＿R：1．6k＝u600t
＋EⅧRS」肝N［N2；N3；N4］＝ⅣN
CONSTANTrLINER＿R：lK＝uOOOt
＋LINER＿R［N4；GND］＝1k
CONSTANTILINER＿R：130＝1130t
＋LI肥R＿R［VCC；N5］＝130
CONSTANTfLINER＿R：800：は00i
＋EⅧRS＿ⅣN［N3；N5；N6］＝WN
CONSTANTIEVERS」）＿OLD：IS1400＝10．6，￥
＋EVERS＿D＿OLD［N6；N7］＝IS1400
3．022e−25，0．026，3．5E−12，￥
0．330，0．750i
＋EVERS」ⅣNlN4；N7；GND］＝NPN
END
図2．7 NETファイルの例
24
2．3．4回路情報生成
MTXファイルのオーダリング情報を入力として回路方程式情報生成ツールFGENを使
用すると回路情報（CDT）ファイルが得られる．図2．3の回路のCDTファイルを図2．8に示
す・CDTファイルは・各節点毎に素子モデルの接続情報，節点に流れこむ電流値を得
るための素子モデル関数の呼び出し手順の情報，モデルライブラリ中のモデル記述モ
ジュールに与えるパラメータ，電源電圧の値の情報を含んでいる．cDTファイルは他
のファイルと異なり，テキストエディタによる編集を想定してないため可読性の低い
文法になっている・プログラミングライブラリ中にはCDTファイルの情報を読み込ん
で各節点の電流値を返すモジュールが用意れている．ユーザはこれを用いてプログラ
ムを作成すればよく，CDTファイル内の情報を直接扱う必要はない．
25
ファイル：srff．cdt
DIMENSION：28
INPUT：3
＊569＆3＠4＃15＃16＃7＃28？O
NODE：8
CONSTANTS：
＊0＆1＠4＃81柑！1！370
1．OE−15100．01．01．OE−120．80．5
＊629＆2＠2：12＃8？14
NODE：9
＊0＆3＠3＃17＃19＃2070
＊0＆2＠4＃8＃9！1！370
＊682＆1＠3＃9＃10＃11？O
NODE：10
＊0＆2＠14＃20＃21？20
0．5E−120．70．51．OE−101．OE＿8
0．026
5
0
4000
＊0＆2＠2：12＃19？18
＊1385＆2＠3＃17＃19＃20？O
NODE：20
＊1441＆1＠14＃20＃21？20
NODE：21
＊1498＆2＠3＃18＃21：13？0
＊0＆2＠2：12＃10？16
＊739＆2＠3＃9＃10＃11？0
＊1520＆4＠4＃22＃23＃14＃21？O
NODE：22
10（X）
＊760＆1＠3＃10＃12＃13？O
NODE：11
＊0＆1＠4＃22＃23＃14＃21？0
＊1586＆2＠2：12＃22714
NODE：23
2000
1600
130
＊0＆3＠3＃9＃10＃11？0
800
＊819＆1＠2＃11：13？17
0．63．022E−250．0263．5E−120．330
＊842＆1＠3＃11＃14：13？O
NODE：12
0．750
PARAMATER：26
NODE：1
＊0＆1＠4＃1＃2！1！2？0
＊195＆2＠2：12＃1714
NODE：2
＊0＆2＠2：12＃12？18
＊899＆2＠3＃10＃12＃13？O
NODE：13
＊0＆2＠4＃22＃23＃14＃21？0
＊1646＆1＠3＃23＃24＃25？O
NODE：24
＊0＆2＠2：12＃24？16
＊1709＆2＠3＃23＃24＃25？0
＊1730＆1＠3＃24＃26＃27？O
NODE：25
＊0＆2＠4＃1＃2！l！2？0
＊0＆3＠3＃10＃12＃13？0
＊954＆1＠14＃13＃14？20
NODE：14
＊248＆1＠3＃2＃3＃4？O
NODE：3
＊0＆2＠14＃13＃14？20
＊1010＆2＠3＃11＃14：13？0
＊0＆2＠2：12＃3？16
＊1032＆3＠4＃22＃23＃14＃21？O ＊0＆2＠2：12＃26？18
NODE：15
＊1875＆2＠3＃24＃26＃27？O
＊0＆1＠4＃15＃16＃7＃28？0
NODE：27
＊302＆2＠3＃2＃3＃4？0
＊322＆1＠3＃3＃5＃6？O
NODE：4
＊0＆3＠3＃2＃3＃4？0
＊375＆1＠2＃4：13？17
＊1098＆2＠2：12＃15？14
NODE：16
＊0＆2＠4＃15＃16＃7＃28？0
＊396＆1＠3＃4＃7：137O
NODE：5
＊1157＆1＠3＃16＃17＃18？O
NODE：17
＊0＆2＠2：12＃5？18
＊0＆2＠2：12＃17？16
＊1219＆2＠3＃16＃17＃18？0
＊449＆2＠3＃3＃5＃6？O
NODE：6
＊0＆3＠3＃3＃5＃6？0
＊499＆1＠14＃6＃7？20
NODE：7
＊0＆2＠14＃6＃7？20
＊549＆2＠3＃4＃7：13？0
＊1240＆1＠3＃17＃19＃20？O
NODE：18
＊0＆3＠3＃16＃17＃18？0
＊1302＆1＠2＃18：13？17
＊1326＆1＠3＃18＃21：13？O
NODE：19
＊0＆3＠3＃23＃24＃25？0
＊1792＆1＠2＃25：13？17
＊1816＆1＠3＃25＃28：13？O
NODE：26
＊0＆3＠3＃24＃26＃27？0
＊1931＆1＠14＃27＃28？20
NODE：28
＊0＆4＠4＃15＃16＃7＃28？0
＊1988＆2＠14＃27＃28？20
＊2015＆2＠3＃25＃28：13？O
SIZE：464
ENTRY：
219272345418469520593
653
70678586592097810591125
1184
126713501406146515471614
16741757
1840189619552040
図2．8 CDTファイルの例
26
2．3．5行列情報生成
CDTファイルを入力として回路行列構造生成ツールMKMTSを使用すると行列構造
（MTS）ファイルが得られる・MKMTSはCDTファイルの情報にしたがってモデル関数を
呼び出し・非ゼロ要素の位置を求めた後，LU分解のシミュレートを行ってフィル・イ
ンの位置を求める・MTSファイルは行列中の非ゼロ要素の位置及び数，フィル・イン
の位置及び数，行列の次元の情報を持つファイルである．図2．3の回路のMTSファイル
を図2・9に示す・ユーザプログラム中で行列のスパース処理を行う場合はMTSファイル
が必要となる．
ファイル：s r f f．mts
DI肥NSION：28
＊＊
● ● ● ● ● ● ● ● ● ● ● ● ■ ●
＊＊＊＊
● ● ● ● ● ■ ● ● ● ● ● ●
＊＊＊＊＊
■ ● ● ● ● ● ● ● ■ ●
＊＊＊ff＊．‥‥‥‥
‥＊f＊＊f‥‥‥‥．
‥＊f＊＊f‥‥‥．‥
‥．＊ff＊……．＊＊
＊＊
● ● ● ● ● ● ● ■ ● ● ● ● ● ■
＊＊＊＊
● ● ■ ● ■ ● ● ● ● ● ● ●
＊＊＊＊＊
＊＊＊ff＊‥．‥‥‥
‥．＊f＊＊f．‥．‥．‥
．‥＊f＊＊f‥‥．‥‥
…．＊ff＊……．＊＊
＊ ＊＊
● ■ ● ● ● ● ● ● ● ● ● ● ● ●
＊ ＊＊＊＊
＊＊＊＊＊……．f
＊＊＊ff＊……f
．＊f＊＊f……f
．＊f＊＊f……f
＊＊＊
f
＊＊＊＊＊
f
＊ ＊
‥＊ff＊＊＊…．f
……‥＊＊＊＊＊f
……‥＊＊＊ff＊
………＊f＊＊f
………＊f＊＊f
＊＊ffffffff＊ff＊
NON＿ZERO：108
FILLIN：48
図2．9 MTSファイルの例
27
2．3．6ライブラリの構成
ASSISTのライブラリは以下の6個のライブラリを含んでいる．
①機種別ライブラリ
グラフィックモジュール，メモリ管理モジュール等のハードウエア依存のモジュー
ルを含むライブラリ・これをハードウエア毎に用意すれば他のモジュールを書き換え
ることなく移植することができる．
②モデル作成支援ライブラリ
モデルライブラリを構成する素子モデル関数のプログラミング用のライブラリであ
り，指数関数型非線形抵抗，キャパシタ等の基本的な素子の特性を記述する関数，ヤ
コピアンの存在を得る関数，エラー処理用関数等で構成される．
③モデルライブラリ
素子モデルの電流値を返すモジュールのライブラリであり，
A．線形抵抗
B．線形キャパシタ
C．インダクタ
D．動作点解析用ダイオードモデル
E．過渡解析用ダイオードモデル
F．エバース・モル動作点解析用モデル
G．エバース・モル過渡解析モデル
H・Shichman−Hodgesモデル
を含んでいる．
④レベル1ユーザプログラム支援ライブラリ
ユーザプログラムの作成を支援するモジュールのうち基本的なモジュールから構成
される・回路情報ハンドリング関数，行列構造情報ハンドリング関数，スパース行列
処理関数等を含む・ASSISTの提供する環境を低レベルインタフェースで使用するライ
ブラリである．
⑤レベル2ユーザプログラム支援ライブラリ
直接法に基づく回路シミュレータの構築を想定して作成されたライブラリであり，
ニュートン法を実行する関数，LU分解実行関数等からなる．本ライブラリはレベル1
ライブラリを使用してプログラムされており，標準的な回路シミュレータを作成する
場合は本ライブラリの提供する環境のみでプログラミングすることが可能であるが，
28
特殊な解析アルゴリズムを使用するときはレベル1ライブラリを直接使用する必要が
ある．
⑥入力波形ライブラリ
シミュレーションを行う際の入力波形を計算するモジュールを含むライブラリであ
り，現在ステップ，パルス波形を発生する関数を含む．
2．4 ASSISTを用いたプログラム開発手順
ASSISTを用いたプログラム開発手順を図2．10に示す．ユーザプログラムはCコンパイ
ラによってオブジェクトファイルに変換され，さらにASSISTのライブラリと結合され
て実行ファイルが生成される．シミュレーションの実行時にはCDTファイルとMTSファ
イルが参照される．
図2．10 ASSISTを用いたプログラム開発手順
29
2・5 ASSIST2およびASSISTを用いた回路シミュレータ開発例
以上述べてきたように，ASSISTは研究用回路シミュレータ開発用共通環境として必
要な機能を有すると同時に，比較的小規模な関数をライブラリとして準備し，改造お
よびツールの入れ換え・新設が容易な構造としている．原形の発表以来，実際の回路
シミュレーションの研究に用いられ，階層節点分割システムHIDE［38】【39］【40】【41］や，
HIDEをベースとするシミュレータ【42】，ならびに混合モードシミュレータ
SPL叩43】【叫【45】【47】【48】など短期間に多くの研究用シミュレータが実現されており，
ASSISTがシミュレータ開発用共通環境として有用であることがわかる．さらに，
ASSISTそのものに対する拡鞄46］［61］も続けられており，HALの扱いに変更を加え，ア
ナログ回路を扱いやすくするとともに，モデルのスタンプ化により計算速度を改善し
たASSIST2が実現されている．
30
2．6 まとめ
本章では回路シミュレータ開発支援システムASSISTを提案し，その構成及び使用例
を示した．
ASSISTはC言語を用いて記述されたライブラリとツール群から構成され，回路のネッ
トリストを入力としてツール群によって生成された回路情報ファイルを基にライブラ
リ内の関数を用いてシミュレーションプログラムを構築する．ASSISTを用いることで
回路方程式の導出部をプログラム中に置く必要がなくなり，シミュレーションプログ
ラムの構築が容易になると同時に，既存のアルゴリズムを用いたシミュレータとアル
ゴリズム本体を除くモジュールを同一とする新しいシミュレータを容易に構築するこ
とができ・回路シミュレーションアルゴリズム研究用ツールとして有用である．また，
ASSISTに含まれるツール群は・テキストファイルを入出力とする単機能かつ小規模な
構成をとっているため，回路シミュレーションにおける行列構造評価等に用いること
ができると同時に，特定のツールの入れ換えも容易となっている．これにより，回路
分割などの前処理アルゴリズムの研究に供することもできる・このような特徴から，
ASSISTは，回路シミュレーションの研究用ツールとして非常に有効である．
31
3 大規模回路行列のLU分解専用並列計算機
3．1概要
近年のVLSI技術の進歩に伴って，大規模集積回路の解析を高速に実行できる回路シ
ミュレータの開発が望まれている．線形回路網解析，あるいは非線形回路網解析で用
いられるニュートン反復の各ステップにおいては，線形連立方程式を解くことが必要
となり，線形緩和法や三角化分解による解法が用いられる．前者では，解の収束性に
問題があるため，三角化分解による解法が一般的であるが，フィル・イン発生による
計算効率の劣化等の問題［12】があり，与えられた回路行列の三角化分解の高速化が重要
となる・近年，大規模スパース行列の三角化分解における処理の並列化やパイプライ
ン化についての手法が提案されるとともに，シストリックアレイ【64】，SMP【65】，
ASWiCl66］，RAMPl67］などのLU分解専用並列計算機が考えられている．
シストリックアーキテクチャはソフトウエアに依存する部分がほとんどなく制御は
容易であるが，N次元の行列を扱うのにN2個，あるいは，N個のプロセッサが必要であ
り，バンド構造以外の大型の行列を扱うには現実的ではない．さらに，スパース行列
を扱うことを考えると行列のスパース性を利用できず，プロセッサの稼働率が低下す
る．
SMPは1行についての処理を並列に行うことを基本とするアーキテクチャであるが，
プロセッサ数が1行の非ゼロ要素数より少ない場合に処理効率が低下する．
ASWiCはプロセッサをクラスタに分割して管理することにより処理効率の向上を行っ
ており，プロセッサとメモリバンクとの結合を連想スイッチで制御することでプロセッ
サ効率の向上を目指す．しかし，ASWiCではプロセッサを効率的に動作させるために
ソフトウエアで最適な制御を行う必要がある．
本章では行列のスパース性を利用でさ，かつ，プロセッサをクラスタ分割すること
によって高度の並列処理を行うLU分解専用計算機SMASH（Simulati。nMAchinewith
SpecialHardware）を提案する．SMASHはLU分解の除算，更新演算処理をそれぞれ専用
のクラスタで行い，ガウス消去演算における列番号整合操作をシフト回路を用いた巡
回シフトによって行う事で高速処理を実現する．sMASHのプロセッサは除算，更新演
算専用演算器であり，ソフトウエアによる煩雑な制御を必要としない．
本章では計算機シミュレーションによるSMASHの性能評価を行った結果として，実
用的なプロセッサ数で高い処理効率を実現できることを示す．さらに，節点分割法に
基づく回路分割処理【161【68】を行う事で処理効率が飛躍的に向上することを示す．
32
3．2 回路行列の特徴とLU分解の並列処理性
3．2．1回路行列の特徴
回路行列は以下の特徴を持つ．
①アドミタンス行列あるいは，ヤコピアン行列は回路内の節点数nにほぼ等しい次元N
の正方行列である．
②全要素の95％以上がゼロ要素のスパース行列であり，次元Nが大きいほどスパース率
も大きくなる傾向がある．
③1行の非ゼロ要素数は平均5∼10程度であり，回路構造によらずほぼ同程度の数
である．
④ピボット順序を適当に選ばないと，フィル・インが大量に発生し，スパース行列で
なくなる．
⑤フィル・インの発生によって，1行の非ゼロ要素数が非常に多い行ができる可能性
がある．
3．2．2LU分解の並列性
LU分解実行中の行列の概要を図3．1に示す．LU分解は以下の2ステップで行われる．
①ピボット要素（P）によるピボット行の各要素の除算を実行する．この商をUとする．
②要素Lを先頭とする各行についてA＝A−エ×Uで要素Aを更新する．
（主）②より明らかなようにLU分解では以下の処理が並列に実行可能である．
Ⅰ・ピボット要卯＝折よるピボット行の要素id誹＞中除算
Ⅱ・要素上＝舶こよるA＝‡郁＞中更新
Ⅲ・複数の要素‡上＝鮎）による各行の更新
以上のほか，大規模スパース行列では，複数のピボット要素による消去処理も並列
に実行可能となる場合がある．
図3．1LU分解実行時の行列構造の例
33
3．3 LU分解専用並列計算機SMASH
3．3．1アーキテクチャの概要
多数のプロセッサを用いる並列処理計算機では，プロセッサのメモリアクセス時の
バス競合が増大し，処理効率が低下する．このバス競合を緩和するため，SMASHでは
いくつかのプロセッサを1単位にまとめるクラスタ方式【69］【70】を採用する．また，前
述のようにLU分解処理の並列性は行列の1行に村する処理を基本として考えることが
できる・したがって，SMASHでは1個のクラスタが1番に対する処理を行う．図3．2に
全体のブロック図を示す・すなわち，1個の除算クラスタ，K個の更新クラスタ，さら
に，メモリユニット及びコントロールユニットで構成され，1クラスタにはP個のプロ
セッサが含まれる．
除算クラスタはピボット要素によるピボット行のデータの除算を行い，更新クラス
タはピボット行のデータによる更新行の更新演算を行う．
メモリユニットは図3・3に示すバンク構造を持ち，そのバンク数は各クラスタ内のプ
ロセッサ数に等しい．コントロールユニットは各クラスタの‘クラスタコントローラと
通信し，処理に必要なデータの送信，演算制御を行い，メモリバスの競合調停を行う．
また・ホストコンピュータとのデータの送受信制御もコントロールユニットが行う．
図3．2 SMASHの構成
34
3．3．2メモリユニット及びデータ構造
回路網解析では大規模スパース行列を扱うことが多く，これをゼロ要素を含めて主
記憶装置上に展開することは多くの場合不可能である．そこで，図3．3（a）に示す行列を
図3・3（b）のようにフィル・インを含む各行のゼロ要素を無視し，非ゼロ要素のみを列番
号とともに記憶させ，更に，メモリのバンド幅を大きくするために複数のメモリバン
クfMBi；i＝1，2，・・・，P）に分けて格納する．図3．3のメモリユニットは1行の非ゼロ要素を1
つのアドレスに対応して記憶させることを基本とするが，非ゼロ要素がバンク数より
多い場合はアドレス2，3のように1行を何回か折り畳んで記憶させる方法をとる．
図3・3のように行列を圧縮した場合には，主記憶内での格納場所が行列上での要素の
位置と一致しなくなる・そのためLU分解実行時に列番号を参照して非ゼロ要素の行列
上での位置に関する整合操作が必要となる．スパース行列のLU分解を行う場合にはこ
の様なデータの整合操作が非常に多くなり，したがってLU分解を高速に行う計算機で
は効率的にデータの整合をとる機能が必要である．
1234567891011121314 MB1 MB2 MB3 MB4
0 1 2 3 4 5
SS巴ppく
＊ ＊ ・ ・ ・ ・ ・ ・ ・ ・ ・ ● ● ●
．．．．・・・・・・＊f＊＊
．．．・・・・・・＊f＊＊＊
．．．・・・・・・＊f＊＊f
．．．・・・・・＊＊＊ff＊
．．．・・・・・＊＊＊＊＊・
．・・・・・＊＊＊＊＊・・・
・・・・・・＊＊＊・・・・・
・・・＊f＊＊＊＊・・・・・
・・＊f＊＊＊・・・・・・・
・・＊f＊＊f・・・・・・，
・＊＊＊ff＊・・・・・・・
・＊＊＊＊＊・・・・・・・・
＊＊＊＊・・・・・・・・・・
1234567891 0日123
114
（a）行列構造の例
（b）データ構造
図3．3 メモリ内のデータ構造
3．3．3 シフトレジスタユニットの構成
演算実行時の列番号整合操作は計算機の動作効率に大きな影響を及ぼす．そこで
SMASHでは図3．4に示すデータのシフト操作の機能を持つ回路をクラスタのローカルメ
モリとして使用し，データの巡回シフトを利用した整合操作により効率化を図る．
図3・4に示すシフトレジスタは列番号を記憶するINDEX，データを記憶するDATAとい
う2つのレジスタがあり，各々が専用のバスに結合される．制御論理回路の論理関数
および，シフトレジスタの動作モードは以下のようになる．
35
論理関数‥（m：コンパレ一夕の一致出力）
∫1＝椚・1和十g
ち＝かぶ＋∫ゐ・五・Wだ
ち＝かぶ＋∫かg・Ⅵ甥
Gl＝瓦百・両・（肝∫ゐ十g）
G2＝かぶ・g
①書き込みモード（DS＝1，E＝1，WR＝1，Sh＝1）
INDEX、DATAバス上のデータを各々のレジスタへロードする．
②読み出しモード（DS＝0，E＝1，WR＝0，Sh＝0）
レジスタの内容を各々のバスへ出力する．
③強制出力モード（DS＝0，E＝1，WR＝0，Sh＝1）
レジスタの内容を各々のバスへ出力したままデータのシフトを行う．
④整合読み出しモード（DS＝0，E＝0，WR＝0，Sh＝1）
NDEXバスをネカとして，INDEXレジスタの内容と比較し，一致した場合には，
DATAレジスタの内容をDATAバスへ出力する．
⑤整合書き込みモード（DS＝0，E＝0，WR＝1，Sh＝1）
INDEXバスを入力として，INDEXレジスタの内容と比較し，一致した場合には
DATAバスの内容をDATAレジスタへ書き込む．
⑥強制書き込みモード（DS＝0，E＝1，WR＝1，Sh＝1）
INDEXバスにINDEXレジスタの内容を出力し，DATAバスの内容をDATAレジスタへ
読み込む．このモードではシフト操作は行われない．
⑦アイドルモード（DS＝0，E＝0，WR＝0，Sh＝0）
シフトを含む一切の動作を行わない．
シフトレジスタユニット（SRU）は図3．5に示すようにシフトレジスタ回路をP個接続し
たものであり，クラスタのローカルメモリとして使用する．
36
図3．4 シフトレジスタ回路
Index
Data
画。h
図3．5 SRUの構成
3．3．4除算クラスタの構成と動作
除算クラスタは図3・6に示すように2個のSRU，P個の除算専用プロセッサ，さらに，
クラスタコントローラ，ピボット要素抽出のためのレジスタ（R，Rd）とコンパレ一夕で構
成される．動作の概要は以下のようである．
Dl：孟Fリユニットからデ￣夕をSRUlに読み込み，SRU2をクリアする・（SRUlモード
D2：Riとクラスタコントローラ内のピボット行番号を記憶しているレジスタの内容を比
較し，一致していなければシフト操作と同時にレジスタRiへ列番号，レジスタRdへ
データをロードする・これを繰り返すことによってレジスタRdにピボット要素Pが
ストアされ，SRUl内には除算対象のデータが残る．（SRUlモード③）
D3‥R。の内容を各除算器へ放送し，SRUl内のそれぞれのデータを除算する．同時に更新
クラスタへ整合開始信号を出力する．
37
D4‥全ての除算器における除算終了後，SRUlをモード⑥とし，除算器の除算結果をデー
タバス上へ出力して，SRUlへ書き込む．同時に更新クラスタへ除算データのラッチ
要求信号を出力し，更新クラスタからラッチ完了信号が出力されるまで待つ．
D5：SRUl内の内容をシフト操作によってすべてSRU2へ送る．
D6：SRU2内の内容をメモリユニットへ書き込む．
D7：除算対象のデータがメモリ内に残っている場合にはDlから繰り返す．
l −
Ⅵミ
．．．．．．．．．．．． ．．．．．．．．．．．．．．．．．．．．
＿．
E
2 I r l
√ ■▲
m
R d ta r t
▲
iJ
q ）
▼
てコ
i■
省
●l・
・
■l
＞
●一■
＞
ト．
I
qJ
「コ
●l l
＞
●−
⊂〕
■
●■
▼
＞
■
■
・
．
■
lS
l
▲
l、
qゝ■
）
「コ
h
U
l疇
l
▼
・
．
・
．
■
OL1
LU．
l・
ト
J
＋
J
⊂
コ
∽
く
つ
END ′「
コU
▼
・
．
■
U
轟
nS
●l l
．⊂⊃
●■｛l
⊂〕
⊂〕
、
河
図3．6 除算クラスタの構成
3．3．5更新クラスタの構成と動作
各更新クラスタは図3・7に示すように，除算クラスタからINDEX，DATAの内容を受
け取るラッチ，P個の更新演算専用プロセッサ，更に，図3．1の要素Lを抽出するための
レジスタとコンパレ一夕，M個のSRU，および，クラスタコントローラで構成される．
動作の概要は以下のようである．
Ul：メモリユニットからSRUへデータを読み込む．
U2‥除算クラスタの整合開始信号が出力されるまで待ち，データをラッチする．このと
き，DATAラッチの内容は除算される前の数値のままである．
U3‥SRUをモード④として巡回シフトを行う．これによって，SRU内に更新されるべき
データが存在すれば，SRU内のコンパレ一夕から一致信号が出力される．プロセッ
38
サは一致信号が出力されたらDATAバス上のデータを取り込む．更に，要素Lがレジ
スタRへ取り込まれる．
U4：除算クラスタのラッチ要求信号が出力されるまで待ち，データをラッチする．この
とき，INDEXラッチの内容は以前と同じはずであり，DATAラッチの内容は，除算
実行後の商Uである．この時点で更新演算に必要なデータはすべて揃う．
U5：更新演算を行う．
U6：SRUをモード⑤とし，プロセッサから更新済みのデータを出力して巡回シフトを行
う・これによって，更新したデータはSRU内の元のレジスタへ戻されることになる．
U7：SRUの内容をメモリユニットへ書き込む．
U8‥メモリユニット内に更新されるべきデータが残っている場合，即ち，ローカルメモ
リに更新行の非ゼロ要素がすべて入りきらなかった場合には，
Ul，U3，U5，U6，U7の順で更新処理を続ける．更新を完了している場合にはコン
トロールユニットへ更新終了信号を出力し，新しい更新行の割当を受ける．
U9‥新しく割り当てられた更新行の更新処理を行う．このとき，ラッチにはすでにピボッ
ト行のデータが存在しているから，U2とU4の動作は行わない．
図3．7 更新クラスタの構成
39
更新処理は1行の更新を1クラスタを1回だけ使って実行することが望ましい．更
新行の非ゼロ要素数がプロセッサ数Pより多い場合でもなるべく1回で更新できるよ
うにローカルメモリとしてのSRUをM個用意する・この場合，更新行の非ゼロ要素数q
が
曾≦Px〟■
（3．1）
であれば更新クラスタを1回だけ使って更新することができる．さらに前述のように
SRUは列番号の整合操作を行う機能を持つ．したがっそ，更新クラスタ内に複数のSRU
を持たせることにより整合操作を並列に行い処理速度を向上させることができる．
3．3．6回路分割手法導入による高速化
SMASHを効率的に動作させるには，以下の条件が必要となる．
1・ピボット行の非ゼロ要素数qとプロセッサ数Pがなるべくq≦Pの関係を満たすこと．
2・更新クラスタのアイドルタイムを減らすために，更新クラスタの負荷が同じであ
ること．
1，2の条件を満たすためにはフィル・インの発生によって，非ゼロ要素数の非常
に多い行ができることは望ましくなく，フィル・インの抑制が必要になる．
フィル・イン抑制のアルゴリズムには行列の行または列の入れ替えを基本とするい
くつかの方法が提案されている・しかし，並列処理性の向上に対する限界があること，
また，大型の行列を扱わねばならないことから，ここでは，節点分割法（以下，m法）
に基づく効率化を考える【16】【68】．これは，回路の部分的な集合内に存在する節点を局
所基準節点として選び，元の大規模回路をいくつかの部分回路に分割する手法である．
局所基準節点に対応する回路行列の行と列を行列の縁に移すことにより，図3．8の縁付
きブロック対角行列に変換することができる．この構造に対してLU分解を行う場合，
ブロック毎の並列処理が可能となるだけでなく，フィル・イン発生率およびその発生
場所が制限され，結果として専用計算機の利用が有利になる．TTLを用いた回路につい
てゲートの出力節点を局所基準節点とするゲートレベル節点分割【68］を適用した場合，
Mを行った場合と行わない場合のフィル・インの数を表3．1に示す．
40
M l
P l
0
P2
M 2
M 3
P3
ヽ
ヽ
ヽ
ヽヽ
ヽ
ヽ
l
l
l
l
l
l
l
ヽ
ヽ
ヽ
ヽ
Q Tl
q T2
Q T3
R
図3．8 縁付きブロック対角行列の構造
表3．1m回路に対するNT法適用例
N T を行 わ な い 場 合
例（
N ） NZ
f
1 （
2 1）
90
48
2（
166 ） 7 72
m aX A v ．
21
h
D iv
M
U d
f
を行 っ た 場 合
m aX A v ． h
D iv
Ud
3．
4
57
177
48
12
6．
4
2．
8
57
179
1164
7 7 1 1．
4
10 ．
0
86 8
5 3 16
702
45
8．
7
7．
2
6 37
290 1
3（
294 ） 140 6
657 2
22 8 2 6．
9
34 ．
5 380 8
662 02
17 74
8 1 10 ．
5 1 1．
8 140 9 104 87
4（
3 17 ） 14 84
260 0
229 12 ．
7
20 ．
8 185 1
129 19
17 56
80 10 ．
0 1 1．
0 142 9 10067
5（
554 ） 26 16
7 86 2
257 18 ．
7
26 ．
0 4 90 1 5 70 99
2 808
57
6（
620 ） 2 90 3
7 72 2
26 8 16 ．
9
23 ．
3 4 940
44 20
9 7 11．
6 16．
0 32 89 40 26 1
回路例
1：3段インバータリング
2：2bit同期式カウンタ
3：3bit同期式カウンタ＋インバータリング
4：3bitジョンソンカウンタ
5：2相クロックパルス発生回路
6：2bit直列加算器
号
5 65 38
記N
6．
4
9．
6
9．
5 2374 134 16
：行列の次元
f ：フィル・インの数
max：1行の非ゼロ要素数の最大
Av．：1行の非ゼロ要素数の平均
h ：非ゼロ要素数の標準偏差
Div：LU分解時の除算数
Ud：LU分解時の更新演算数
表3．1からMを行うことによりフィル・インの発生が著しく抑制されることがわかる．
ここで，図3．8の行列をLU分解すると以下のようになる．
41
［芸拙ふ描こ］
（3．2）
4
5
′
0
LrUr＝R−WTv
WT＝QTU￣l
3
V＝rlp
︶ ︶ ︶ ︶
3 3 3 3
︵ ︵ ︵ ︵
M＝LU
式（3・3），式（3・4），式（3．5）は各ブロック毎に並列に処理でき，最後に
R′＝R−∑wJv
R′→LrUr
とすることでLU分解が完了する・回路例2について，Mを行った場合と行わない場合
の各行のフィル・インを含む非ゼロ要素数を図3．9に示す．図3．9から，mを行うことに
より，各行における非ゼロ要素数の最大値が小さくなり，かつ，各行の非ゼロ要素数
のばらつきが小さくなっていることがわかる・したがって，NT法はSMASHを効率的に
動作させるための前処理として有効である．
図3．9 NT法による各行の非ゼロ要素数の変化
42
3．4 性能評価
SMASHにおけるメモリアクセス時のバス競合は，回路構造に依存する．そこで，本
章においては，SMASHの性能を正確に見積るために，具体的な回路例に対する性能評
価シミュレーションについて述べる．シミュレーションの条件は以下のようである．
システムのクロック周波数
メモリ素子のアクセスタイム
SRUのシフト操作所要時間
：50MHz
：100ns
：20ns／シフト
除算実行時間
：3720ns
更新演算実行時間
：1080ns
1クラスタ内のプロセッサ数
：P
更新クラスタ数
：K
更新クラスタ内のSRUの数
：M
また，更新クラスタの負荷をなるべく同じにするために更新行は更新の対象となる
非ゼロ要素数の多い順に更新クラスタへ割当を行うものとする．これによって，更新
行の数より更新クラスタ数が少ない場合に更新クラスタ間での負荷分散効果が期待で
きる．
図3・10に表3・1の例2の回路の回路行列のLU分解シミュレーション結果を示す．図3．10
からMを行うことによって計算時間が著しく減少していることがわかる．
また・P＝1、K＝1、M＝1の構成のSMASHの計算時間をTL，各々の構成の場合の計算時間
をTsとして，計算速度Sを式（3．9）で定義する．
∫＝五
（3．9）
㌔
例2の回路行列にMを行った行列を処理した場合の計算速度Sを図3．11に示す．プロセッ
サ数Pが行列の1行の非ゼロ要素数の平均を越えるまでは速度の改善が著しい．また，
SRUの数Mを増やすとプロセッサ数が少ない場合ほど速度向上効果が大きいことがわか
る．
43
0 5
15 20 25
Processor／Cluster
30
図3．10 シミュレーション結果1
Sample：2
M＝1−−−M＝6
∽30
5 10 15
20 25
Processor／Cluster
図3．11シミュレーション結果2
44
30
3．5 まとめ
本章ではLSIシミュレーションにおいて重要となる大規模スパース行列のLU分解専用
並列計算機SMASHを提案し，その性能評価を行った．
大規模回路シミュレーションを通常の汎用逐次計算機で行う場合，回路規模の増大
にともなって，行列情報を格納するメモリ領域も大きくなっていき，キャッシュメモ
リの容量を越えてしまう．したがって，列番号整合のためにCPUが行列メモリ領域に
アクセスする時間が非常に長くかかるようになり，大規模回路シミュレーションにお
いては，非現実的な処理時間がかかることになってしまう．
SMASHは列番号整合を専用ハードウエアSRUによる巡回シフトで高速化することで，
プロセッサのアイドル時間を削減し，稼働率を高めることができるため大規模行列の
三角化分解を効率的に行うことができる・さらに，SMASHはプロセッサをクラスタ分
割して管理することによりバス競合を回避し，プロセッサの動作効率を高めている．
その結果，従来から提案されているLU分解専用並列計算機に比べてプロセッサ数が比
較的少数の場合に特に並列処理性が高いことをシミュレーションによって示した．ま
た，SMASHを効率的に動作させるためにm法による前処理が有効であることを示した．
これらの結果から，SMASHを用いることで，逐次計算では非現実的であった大規模
回路シミュレーションを高速に行えると考えられる．
45
4 LU分解専用並列計算機SMASHを用いた大規模回
路シミュレーションの高速化
4．1概要
高速・大規模VLSIの設計では大規模回路シミュレータの高速化が重要である．収束
性に優れた直接法を用いた回路シミュレーションの高速化を目的として，スパース行
列を取り扱うための特別なアーキテクチャを持ついくつかのLU分解専用並列計算機
【711【651【66】【67】【69】の利用が検討されている．第3章において，従来のLU分解専用並列計
算機において問題となっていたプロセッサ稼働効率の低下やソフトウエア制御の煩雑
化を解消できる大規模スパース行列のLU分解専用並列計算機SMASHを提案し，その性
能評価を行った【49】．
SMASHはクラスタ方式を採用した並列計算機であり，LU分解時に必要な列番号整合
操作を，データの巡回シフト操作を行う専用回路SRUを使って実行することにより実
用的なプロセッサ数で高度の並列処理を行う・更に，節点分割（NT）法【161［681に基づく
前処理を行うことで，より一層の高速処理が実行できる．
本章ではSMASHをLU分解用コプロセッサとして使用する回路シミュレーションシス
テムを想定し，その結合方式の検討および，実際の回路データを用いて計算機シミュ
レーションによる性能評価を行った結果を示す【50】．ホスト計算機とSMASHを，行列
データおよび，三角化分解の手順を示す制御コードを格納するメモリバンクを介して
共有メモリ接続し，さらに，共有メモリを3バンク構成とすることで，ホスト計算機
とSMASHを独立して動作させることができる．
計算機シミュレーションを用いて，本回路シミュレーションシステムの動作シミュ
レーションを行った結果として，LU分解および前進代入の計算時間をホスト計算機上
の他の計算時間とオーバーラップさせることが可能であることを示す．その結果，従
来の回路シミュレータにおける行列計算の所要時間を，SMASHへのデータ転送時間で
置き換えることが可能となり，シミュレーションの所要時間を素子モデルの計算時間
とほぼ同一となるまで短縮できる．さらに，ホスト計算機として，汎用並列計算機を
適用するか，簡易な素子モデルの適用により素子モデル計算時間を短縮した場合でも
同様に高速化することが可能であり，解析時間全体に対する行列計算の割合が多い場
合ほど，SMASHの利用効果が高いことを示す．
4．2 大規模回路の分割
大規模回路のシミュレーションでは回路全体を1度に取り扱うことは多くの場合不
46
可能であり・いくつかの部分回路に分割する必要がある．そこで本研究では節点分割
法を用いる・これは，回路の部分的な節点集合内に存在する節点を局所基準節点とし
て選び・元の大規模回路をいくつかの部分回路に分割する手法である．局所基準節点
に対応する回路行列の行と列を行列の縁に移すことにより，図4．1（a）の縁付きブロック
対角（BBD）行列に変換することができる．この構造に対してガウス法に基づくLU分解
を行う場合，対角ブロックMi内の各行によるガウス消去処理過程で参照及び更新され
る要素は部分行列Mi，R，Ql，R内の要素に限られる．したがって，SMASHのメ
モリ上に展開する行列は図4．1（b）に示す小行列でよい．
SMASHを効率的に動作させるためには，LU分解処理を行う行列に対して，各行に含
まれる非ゼロ要素数を均一化することが必要であり，そのための前処理としてNT法が
有効である【491・本章では，SMASHを効率的に動作させるために，m法によって得ら
れた対角ブロック行列Mfに対して，Mを再帰的に行うことによる階層分割
【18】【19】【20］【38】を前処理として使用した．階層節点分割によって得られる行列は，図4．2
に示す再帰的縁付きブロック対角（RBBD）構造となる．本研究で用いた階層節点分割
システムは構造記述言語HAL【60］を入力とする自動分割アルゴリズム【38】を使用してお
り，他のスパース処理技法と比較して，
1：回路構造を反映した行列構造が得られる．
2：行列の取り扱いが容易である．
3：煩雑な消去シミュレーションを行う必要がなく，高速である．
4：潜在性の利用が容易である．
等の特徴がある・また，1階層節点分割と比較するとフィル・インの抑制効果が向
上することが確認されている【381【39］［40］．従って，SMASHを含むシミュレーション・
システムの前処理として有効である．
47
（a）縁付き対角ブロック（BBD）行列
（b）BBD行列のLU分解
図4．1節点分割後の行列構造
0
拙 宅な≧
宏な
0
醐
ヽヽ
ヽヽ
ヽ
坊謡
＃＃岩浅頴＃絃
坊呈H 巧
≧
朋
図4．2 再帰的縁付きブロック対角（RBBD）行列
4．3 非線形回路網解析における計算量の評価
直接法による非線形回路網解析では解析時間のほとんどがニュートン反復に要する
時間である．ニュートン反復は以下の3ステップで実行される．
1：素子モデルの計算及び行列化
48
2：行列計算
3：近似解の更新及び，収束判定
このうちステップ3に要する時間はステップ1，2に比べて無視できるほど少ない
【20】・したがって，ここではステップ1及びステップ2の所要時間を評価する．
本研究ではSMASHを制御するホスト計算機として一般的なワークステーションを仮
定しているが，ホスト計算機上での演算，処理に必要な時間を正確に見積ることは困
難である・そこで，ホスト計算機の計算時間を，浮動小数点演算にかかる時間および，
メモリ上の数値データのアクセス時間のみで評価した．四則演算および関数計算の所
要時間は浮動小数点コプロセッサMC68881を20MHzのクロックで動作させた場合を想
定して以下のように定めた．
加，減算：2600ns
乗算：3600ns
除算：5200ns
平方根：5400ns
expO：24900ns
べき乗：61000ns
メモリⅣ0：100ns
表4・1にmを用いた回路を解析した場合の各々のステップの計算時間評価を，また，
表4・2に本評価法と実際に数値解析を行った場合の所要時間の比較を示す．表4．1の回路
例はJKフリップ・フロップを用いた非同期式カウンタであり，表4．2の回路例はインバー
タチェインである．トランジスタのモデルは図4．3に示す非線形容量を含むEbe，S＿M。11モ
デルを使用した・回路行列は節点分割法によって図4．2のRBBD構造に変換され，行列
演算は全てコード生成されているものとして評価した．
表4・2から，素子モデル計算では計算時間評価の結果は実際の数値解析における所要
時間とほぼ一致しているが，行列計算では本評価法は計算時間を過小評価しているこ
とが分かる・また，表4・1では回路規模の増大に伴って解析時間に対する行列計算時間
の割合が増加傾向を示す．行列計算の計算量は次元の1．1乗∼1．5乗に比例して
増大することが知られており，解析する回路規模が大きくなるほど行列計算の高速化
が重要となる．
トランジスタモデルとして図4．3のモデルを使用した場合，回路網中の素子枝のほと
んどが非線形特性を持つことになる．実際の回路解析で線形素子の割合が多くなった
場合にも行列計算時間の割合が増大する．表4．1の回路例lRおよび2Rは回路例1，2と
同じ回路について図4・3のトランジスタモデルにエミッタ抵抗，コレクタ抵抗，ベース
抵抗を付加したモデルを用いて計算時間評価を行った結果である．各々を比較すると
49
線形素子の増加にともなって行列計算時間の割合が増大していることがわかる．
表4．1ニュートン反復1回の計算時間評価
M odel
N o ．N o d e
1
M a tri x co m p u tatio n tim e （
n s）
CO m p u tatio n
tim e （
ns）
L U decom p ．
F o rw ard
T o tal
（
ns）
B a ck w o rd
83
58 ，
390 ，
000
（
82．
1 3 ％）
8，
5 2 1，
700
（1 1 ．
9 9 ％）
2，
3 1 1，
100
（
3．
2 5 ％）
1，
8 7 1，
2 00
（
2．
6 3 ％）
7 1，
094 ，
00 0
（10 0 ％）
lR
2 37
62，
04 9，
20 0
（
68 ．
67％）
18 ，
0 98，
3 00
（
20 ．
0 3 ％）
5，
7 32 ，
10 0
（
6．
34 ％）
4，
4 76 ，
00 0
（
4．
95 ％）
9 0，
35 5 ，
600
（10 0 ％ ）
2
4 15
293 ，
4 64 ，
000
（
80．
5 3 ％）
4 8，
50 0，
10 0
（13 ．
3 1％ ）
12 ，
3 2 1，
100
（
3．
3 8 ％）
10 ，12 1，
6 00
（
2．
7 8 ％）
3 64 ，
4 0 6，
8 00
（10 0 ％）
1 18 5
3 10 ，
40 8，
0 00
（
67 ．
12 ％）
98 ，
807 ，
500
（
2 1．
3 7 ％）
29 ，
7 69 ，
30 0
（
6．
44 ％）
23 ，
48 8，
80 0
（
5．
0 8％）
46 2 ，
4 73 ，
60 0
（10 0 ％ ）
3
74 7
52 8，
53 8，
000
（
80 ．
3 6 ％）
88，
47 8，
50 0
（1 3 ．
4 5 ％）
2 2，
3 3 1，
10 0
（
3．
4 0 ％）
18 ，
37 2 ，
0 00
（2 ．
7 9 ％）
657 ，
7 19 ，
6 00
（10 0 ％）
4
996
7 04 ，
843，
5 00
1 18 ，
4 62 ，
300
（
8 0．
3 0 ％）
（13 ．
5 0 ％）
29 ，
83 8，
60 0
（
3．
4 0 ％）
24 ，
559 ，
80 0
（
2．
80 ％ ）
87 7 ，
704 ，
20 0
（10 0 ％ ）
2R
表4．
2 計 算 時 間 評 価 と シ ミ ュ レ ー シ ョ ン 時 間 の 差
Odel
R eal
LU
F o rw ard
O m P u tatio n D ec o m p ．
70 ．
4 1m s
2．
569m s
1．
55 8m s
E stim ate
67 ．
3 9m s
0．
9 92m s
0．
45 5m s
0．
3 2 1m s
69 ．
16 m s
R atio
1．
04
2．
59
3．
49
2．
75
1．
09
R ea l
84 ．
80m s
7．
74 5m s
3．
550 m s
2．
7 17 m s
98．
8 1m s
E stim ate
77 ．
94m s
2．
5 18 m s
1．
2 3 1m s
0．
869m s
82．
5 6m s
1．
09
3．
08
2．
88
3．
13
1．
19
N o．
A
B
R atio
50
B a c k w o rd
S um
0．
8 83m s
75 ．
4 2m s
CsUB
図4．3 Ebers一mOllモデル
4．4 SMASHの構成
SMASHは図4・4に示すようにコントロールユニット，メモリユニット，除算クラスタ
および，K個の更新クラスタで構成され，メモリユニットを介してホスト計算機と結合
される・コントロールユニットはクラスタへの処理行の割当を行い，各クラスタは行
列の1行単位の処理を行う．また各クラスタ内にはデータの巡回シフト操作の機能を
持つ回路SRUが複数あり，これによって列番号整合操作を並列に実行することで
SMASHの動作速度を向上させる．特に1クラスタ内のプロセッサ数が比較的少ない場
合ほど・複数のSRUを使用することによる速度改善効果が高い【49】．
SMASHは図4・5に示すようにガウスの外積アルゴリズムにしたがってLU分解を実行
する・除算クラスタはSRU，コントローラ，およびP個の除算専用プロセッサで構成
され，図4・5のsteplの除算処理を行う．更新クラスタはコントローラ，ラッチ，P個の
更新演算専用プロセッサ・M個のSRUで構成され，図4・5のstep2の更新処理を行う．さ
らに，各々の更新クラスタは別々の行の更新処理を行う．各クラスタの詳細は第3章で
述べた通りであるので，ここでは省略する．
SMASHはメモリユニット中の行列データを，コードメモリに格納される制御コード
にしたがって処理し，結果を元の位置へ格納する．ホスト計算機はSMASHのメモリユ
ニットへ行列データおよび，制御コードを転送し，処理開始信号を送るだけでよく，
SMASHの動作を制御する必要はない【49］．したがって，ホスト計算機とSMASHは独立
して動作することが可能であり，各々の処理時間をオーバーラップさせることが出来
る．
51
図4．4 SMASHの構成
1：U＝A／D
2：A＝A−LXU
図4．5 LU分解
4．5 メモリユニットの構成
BBD構造の回路行列を取り扱う場合，前述のようにブロック毎に独立して処理する
ことが可能である・この時・各ブロックのLU分解処理には図4．1の部分行列Rの更新演
52
算が毎回含まれる・システムの動作効率を向上させるためにはホスト計算機とSMASH
間のデータ転送時間を短縮することが必要となるため，各ブロックの処理に共通して
必要な部分行列Rを処理の開始から終了までSMASHのメモリ上に置くことが望ましい．
さらに，SMASHの動作中にホスト計算機とのデータ転送を可能にするために図4．6に示
すようなメモリ構造を採用する・即ち，図4．6（a）に示すように，メモリユニットは
PageO，Pagel・Page2の3ページで構成され，各々のページは図4．6（b）のようにデータ部
とコード部に分かれている．
データ部は各クラスタ中のプロセッサ数Pと同数のバンクに分かれており，行列要素
の数値及び列番号がゼロ要素を無視して行ごとに格納される・例えば，図4．7（a）の行列
を格納する場合，P＝4とすると図4．7（b）のようになる．
コード部はコントロールユニットにバススイッチDを介して接続され，SMASHを動
作させる制御コードを格納する．
Pagel及びPage2は同一のアドレス上に配置され，バススイッチA，Bを介してSMASH
およびホスト計算機に接続される・バススイッチA，Bは排他的に制御され，これによっ
てSMASHとホスト計算機はそれぞれ別々のページを独立してアクセスできる．pageoは
Pagel及びPage2と連続するアドレス上に配置されバススイッチCによって切り替えを行
う・PageOはSMASHの動作中にホストからアクセスできない領域であり，前述の部分行
列Rおよび‡Qr拉1，2，…）を格納する・
53
（a）メモリユニットの構成
Data
Bus
Code
Bus
（b）メモリページ
図4．6 メモリユニット
1234567891011121314 MB1 MB2 MB3 MB4
0 1 2 3 4 5
SS巴ppく
＊ ＊ ・ ・ ・ ・ ・ ・ ・ ・ ● ● ● ●
．．．．・・・・・・＊f＊＊
．．．・・・・・・＊f＊＊＊
．．．．・・・・・＊f＊＊f
．．．．・・・・＊＊＊ff＊
・・・・・・・・＊＊＊＊＊・
・・・・・・＊＊＊＊＊・・・
・・・・・・＊＊＊・・・・・
・・・＊f＊＊＊＊・・・・・
・・＊f＊＊＊・・・・・・・
・・＊f＊＊f・・・・・・・
・＊＊＊ff＊・・・・・・・
・＊＊＊＊＊・・・・・・● ●
＊＊＊＊・・・・・・・・● ●
12345678910日121314
（b）データ構造
（a）行列構造の例
図4．7 メモリユニット内のデータ構造
54
4．6 システムの動作概要
本システムは回路を図4．1のBBD構造にして，ブロック単位でのガウス消去をSMASH
上で行い，ホスト計算機は素子モデル計算及び後退代入のみを行う．
SMASHとホスト計算機間のデータ転送は各々のページに対して処理要求フラグ，処
理終了フラグ，状態フラグを用意して行う．処理要求フラグは該当するページ中のデー
タをLU分解処理する必要があることを表し，処理終了フラグはLU分解済みのデータが
あることを表す・さらに，状態フラグは該当するページに新しいデータを書き込むこ
とが出来ない状態であることを表す．
ホスト計算機上ではSMASHの処理終了信号によって例外処理が起動され，処理終了
フラグのセットおよび処理要求フラグのクリアを行う．更に別のページの処理要求フ
ラグがセットされていればバススイッチA，B，Dを切り替えてSMASHに処理開始信号
を送る．
ニュートン反復を1回実行するときのシミュレーションシステムの動作は以下のよ
うになる．
①回路行列上のQ告Rの部分に相当する素子のモデル計算を行い，行列データ及び部
分行列RのLU分解コードをPageOのメモリ上に転送しバススイッチCをSMASH側に
切り替える．
②未処理のブロックMい戦について素子モデル計算を行う．
③pagelあるいはPage2の処理終了フラグがセットされていればホスト計算機のメモリ上
に逆転送し，該当するページの状態フラグおよび処理終了フラグをクリアする．
④page1，2の状態フラグをサーチし，クリアされているページがあれば行列データを
転送し処理要求フラグ及び状態フラグをセットする．
⑤全てのブロックについてガウス消去が終了していなければ，②から繰り返す．
⑥バススイッチDをPageOに切り替えてSMASHに処理開始信号を送る．
⑦sMASHから処理終了信号が出力されるのを待って，PageOのデータを逆転送する．
⑧後退代入を行う．
⑨近似解の更新及び収束判定を行う．
4．7 シミュレーション結果
表4・1の回路例を解析した場合のニュートン反復1回の所要時間を表4．3に示す．シミュ
レーションの条件は以下の通りである．
SMASH：
クロック周波数：50MHz
メモリアクセスタイム：100ns
55
SRUのシフト操作所要時間
除算実行時間
更新演算実行時間
1クラスタ内のプロセッサ数
更新クラスタ数
更新クラスタ内のSRUの数
：20ns／シフト
：3720ns
：1080ns
：P＝4
：K＝3
：M＝5
ホスト計算機：
データバス幅：32bit
浮動小数点コプロセッサ：MC68881
使用した回路はいずれもm法によって均等の大きさのブロックに分割されており，
1ブロック中の節点数，及び，ブロック数は表4．3に示す通りである．
表4・3と表4・1を比較するとSMASHを使用することで，回路規模に関係なくLU分解と
前進代入の所要時間分の高速化が出来ることがわかる．
表4．3 SMASH使用時の計算時間
N o ．N o de
1
N um b er of
d iago nal
block
D im en sio n o f
C om p utation tim e （
n s）
diago n al
W ith ou t S M A S H
W ith SM A S H
block
83
1
83
7 1，
0 94 ，
0 00
62 ，
68 1，
9 00
（
1 1．
83 ％up ）
lR
237
1
237
90 ，
3 55 ，
600
69 ，
89 1，
60 0
（
22．
6 5％up ）
2
4 15
5
82，
83
364 ，
4 0 6，
800
3 07 ，
4 38，
3 00
（15 ・
6 3％u p）
2R
1185
5
2 36 ，
23 7
4 62 ，
4 7 3，
60 0
34 0 ，
638 ，
20 0
（
26．
34 ％up ）
3
7 47
9
82 ，
83
6 57 ，
7 19 ，
600
5 5 2，
169 ，
900
（
16．
0 5％up ）
4
99 6
12
82，
83
87 7 ，
7 04 ，
2 00
7 35 ，
7 38，
2 00
（16 ．
17 ％u p）
56
4．8 素子モデル計算の高速化
素子モデルの計算は，
1：MIMD型並列計算機の利用【72】
2：潜在性の利用による計算の省略【20］
3：簡易素子モデルによる近似計算
によって高速化することが可能である・また，分布定数線路を含む回路網の解析など
線形回路素子の多い回路の解析では解析時間全体に対して素子モデル計算に要する時
間の割合が減少することが予想される・以上のように，解析時間全体に対する行列計
算時間の割合が高い場合の評価として，ここではホスト計算機としてMIMD型の並列計
算機を用いたシミュレーションシステムの評価を行う．素子モデル計算がS倍の速度で
行われるとした場合の計算時間を表4・4に示す・表4．4からSMASHを用いれば素子モデ
ル計算の高速化にほぼ比例してシミュレーション時間が高速化できることがわかる．
一方，LU分解用コプロセッサとしてホスト計算機と同等の計算速度をもつSISD型計算
機を使用した場合，表4・4から，行列計算時間の割合が大きくなった場合に処理速度の
向上に限界が見られる．
表 4・
4 M IM D 型 ホ ス ト計 算 機 を 使 用 し た 場 合 の 計 算 時 間
C o m p u ta tio n T im e （
n s ） ／ rS p e e d u p ra tio l
H o s t c o m p u te r ： 0
S I S D （S ＝ 1 ）
L U D e c o m p ・P rO C eS SO r
S M A SH
1
62 ，
68 1，
90
【1．
0 】
lR
69 ，
89 1，
60
【1 ．
0 】
30 7，
4 38，
30
2
【1．
0 ］
R
S IS D
M IM D （S ＝2 ）
L U D ec o m p ・P rO Ce SSO r
SM A SH
S IS D
H o st c o m p u te r： M M
D （S ＝3 ）
L U D e co m p ・p rO C e SSO r
SM A SH
S IS D
H o s t c o m p u te r ：
M M
L U D e c o m p ・p rO C eS SO r
SM A SH
7 1，
4 17 ，
10 0 3 3 ，
4 86 ，
900 4 2，
22 2，
10 0 2 3 ，
755，
300 32 ，
490 ，
500
【1 ．
0 0】
【1 ．
87】
【1．
69］
【
2．
64】
【
2 ．19 1
18，
8 89，
4 00
9 1 ，14 5 ，
700
23 ，
354 ，
700
【1．
00 1
38，
86 7，
∝旧
【1．
7 9 ］・
6 0 ，12 1 ，
10 0
【1 ．
6 1】
28，
525 ，
500
【
2．
4 5】
49 ，
7 79 ，
㈱
【1 ．
831
D （S ＝4 ）
【
3．
3 1】
【2 ．
9 9】
S IS D
27，
6 24 ，
60
【
2．
5 8】
44 ，
60 8，
800
【
2．
糾】
3 17 ，
34 7 ，
4（
犯 16 0 ，
706 ，
40
17 0 ，
6 15，
50 0 1 1 1 ，
796，
（旧0 12 1，
7 0 5 ，10 0 8 7 ，
3 40，
4 00
97 ，
24 9 ，
50 0
【1 ．
00 】
【
1．
9 11
【1 ．
86】
【
2．
75 】
【
2．
6 1】
【
3．
52 】
【
3．
26】
34 0 ，
638 ，
2（
氾 36 3，
45 3，
70 185 ，
4 34 ，
4 00 20 8，
249 ，
900 133，
699 ，
7 0 0 17 3 ，
4 59 ，
9 0 0 10 7 ，
8 32，
4（
M 16 8 ，
25 5，
800
【1．
（
氾】
【1 ．
0 】
［1．
8 3】
【1．
74 】
【
2．
54】
［
2 ．10 】
【
3 ．15 1
r2 ．
16 1
5 5 2 ，16 9 ，
90
3
H o s t c o m p u te r ： 【1．
0 】
7 35 ，
738 ，
20
【1．
0 】
5 63 ，
627 ，
800 28 7，
90 1，
∝氾 2 9 9 ，
3 58，
9 0 0 19 9 ，
8 1 1，
8 0 0 2 1 1，
26 9，
70 155 ，
766 ，
5 0 0 16 7 ，
224 ，
40
【
1．
0 0］
【1 ．
9 2】
【1 ．
8 81
［
2．
76 】
【
2．
6 6】
【
3．
54 1
【3 ．
37】
74 8，
3 3 8 ，100 3 8 3 ，
3 16，
5 0 0 39 5 ，
9 16 ，
400 ■
265 ，
84 3 ，
300
27 8，
44 3 ，
2 0 2 0 7 ，10 5 ，
7 0 2 19，
70 5，
600
【1 ．
00 】
【1 ．
92 】
【1．
891
【
2．
77】
【2 ．
69】
【
3．
55 】
【
3．
4 1］
57
4．9 まとめ
本章では，LU分解専用並列計算機SMASHを含む回路シミュレーションシステムの性
能評価を行った．
SMASHは，LU分解実行時の列番号整合操作をおこなう専用回路SRUを持ち，メモリ
に対する複雑な制御を行うことなく効率的に列番号整合を実行できる．また，SMASH
を構成するプロセッサは・除算あるいは更新演算専用の単純なものであるため，プロ
セッサに対する制御も簡略化できる・したがって，SMASHは，内蔵するコントロール
ユニットの制御信号のみで動作でき，外部から複雑な制御を行う必要がないため，直
接法による回路シミュレーションに必要な素子モデル計算と行列計算の負荷をホスト
計算機とSMASHに分けて実行できる・実際の回路を用いてSMASHを含む回路シミュレー
ションシステムの動作シミュレーションの結果，SMASHを使用することで回路シミュ
レ￣ションの所要時間を素子モデル計算の時間とほぼ同一にできることが示された．
さらにホスト計算機としてMMD型の並列計算機を用いる，潜在性を利用するなどの方
法により素子モデル計算時間の割合が減少した場合にも同様にシミュレーション時間
をほぼ素子モデルの計算のみの時間にまで短縮できることを確認した．
以上の結果から，SMASHを含む回路シミュレーションシステムが，大規模回路シミュ
レーションに特に有効であるといえる．
58
5 区分線形ダイオードモデルを用いた回路解析
5．1概要
大規模回路の過渡解析において，過渡解析の実行前に，回路の動作点を求める動作
点解析が必要となる．一般的な回路シミュレータでは，回路内に存在するコンデンサ
を除去し，インダクタを短絡して得られる非線形抵抗回路網について，ニュートン法
を適用して動作点を求めている・動作点解析を行う際のニュートン法の初期値は，ネッ
トリストなどの回路構造の情報から決定する事が困難であるため，すべての状態変数
を0とした初期値を用いるなどの方法を採ることが多い．したがって，ニュートン反復
が収束しない例が多くなり，収束する場合においても，膨大な反復回数が必要となる
場合が多く発生することが知られている．動作点解析のためのニュートン反復の所要
時間は，素子モデルの計算時間が60％∼90％を占めており，特にバイポーラ回路網の動
作点解析においては，バイポーラトランジスタの素子モデル計算に多くの指数関数計
算を含み，計算時間が増大するため，モデル計算の高速化が極めて重要である．本章
では，大規模回路の動作点解析におけるニュートン反復の初期値決走法として，非線
形関数計算を含まない簡易素子モデルを用いる手法を提案する．簡易素子モデルを用
いることにより，素子モデル計算時間が大幅に短縮できる反面，解析解の精度は低下
してしまう・そこで，本手法をニュートン反復の初期値決定法としてのみ用いる方法
をとる・第1章に述べたように，ニュートン法は各反復で近似解の修正量を計算し，近
似解を更新していくことによって真の解を得る方法である．ニュートン法は，近似解
が真の解に近くなると，2次収束性を示すことが知られている．すなわち，真の解に
十分近い初期値を与えることによって，少ない反復回数でニュートン法を収束させる
ことができ，高速化が達成される．
簡易な素子モデルを用いる非線形回路解析には，区分線形法による回路解析法があ
る・これは非線形素子の特性をいくつかの区間に分け，それぞれの区間を線形関数で
近似することで非線形方程式を線形方程式の集合と考え，隣接する各領域を順次決定
しながら解曲線を追跡する方法である．この種の方法は非線形方程式の解を大局的に
追跡するために有力であり，Katzenelson法【73】をはじめとし，一般化手法【74］も提案さ
れている・また，区分線形法による解析は，ヤコピアン導出の必要性がないことから，
解析の高速化という点に対しても大きく寄与する．しかしながら，隣接する領域を順
次決定しながら解曲線を追跡するため，解析に時間がかかる．
さらに，バイポーラトランジスタ回路におけるスイッチレベルシミュレーション
（SLS）技法が提案された【75】【76】．文献【76］では，ダイオードをスイッチと電圧源によっ
59
てモデル化し，得られたスイッチト回路網に含まれる複数のスイッチの状態を同時に
変化させながら反復解析を行なう方法が述べられている．これはダイオード特性をス
イッチがONである順バイアス領域と，OFFである逆バイアス領域の2区間で線形近似
した区分線形法であると考えられる［76】【77】【78】．ダイオードモデルを電圧源とスイッチ
のみで構成した区分線形解析法においては回路トポロジは動的に変化する．従って，
スイッチの状態によっては回路網中に電流源のみのカットセットや電圧源のみのルー
プが生じる場合がある・また，ある部分回路が他の回路網と分離され，基準節点への
パスを持たない節点集合が生じることがあり，これらの場合には係数行列が非正則に
なる・さらに，初期スイッチパターンの与え方によっては，解析の反復過程において，
誤ったリミットサイクルに縮退するリミットサイクル問題がある．
本論文では非正則問題を回避するためのダイオードのスイッチを含む区分線形モデ
ルを提案するとともにその修正節点方程式化について述べる．本モデルは，電圧源と
スイッチの他に，逆バイアス領域の特性を近似する線形並列抵抗（R）と順バイアス領域
の特性を近似する線形直列抵抗（r）を付加することでダイオード特性を2区間で近似す
る区分線形モデルである・区間の切り替えはモデル内のスイッチで行ない，複数のス
イッチの状態を同時に変えることにより解析を高速に実行する．並列抵抗（R）の挿入に
よって，電流源のみのカットセットの発生及び部分回路網の分離がなくなり，直列抵
抗（r）の挿入によって電圧源のみのループが生じなくなる．その結果，修正節点方程式
の係数行列は常に正則であることが保証され，行列構造が変化しないため，LU分解専
用並列計算機【491の利用も可能となる．
本モデルを使用した解析の評価として，本論文では，電圧源と理想スイッチのみで
構成されるダイオードモデル【76］【771を用い，非正則問題が発生した場合には拡張LU分
解【771を行なって反復を続行する方法との比較を行なった．m回路について本区分線
形モデルを使用して解析を行なった結果，ピボット選択等の処理をしなくても非正則
問題を回避することが可能となり，更にリミットサイクル問題を大幅に緩和できるこ
とが確認できた・これは，スイッチを含む区分線形ダイオードモデルによる近似精度
の向上と本モデルを使用した修正節点方程式化に基づくスイッチ状態の切り替え制御
により反復計算が収束しやすくなったことに起因するものと考えられる．
5・2 スイッチを含む区分線形ダイオードモデルの提案とその定式化
図5・1に示されるような理想スイッチと順バイアス時の順方向電圧降下を表わす走電
圧源Ⅵのみで構成されるダイオードモデルでは，逆バイアス状態，即ち，スイッチが
OFFとなる状態でアノードとカソードが完全に遮断される．このとき，部分回路網が分
60
離され，基準節点へのパスを持たない節点集合を生じることがある．また，ダイオー
ドのみのループを有する回路ではスイッチがONの時に電圧源だけのループを生じる．
さらに，バイポーラトランジスタを図5・2のエバース・モルモデルで置き換えた場合，
電流源のみのカットセットを生じる可能性がある．以上のように図5．1のダイオードモ
デルによる区分線形解析では係数行列が非正則になる場合がある．
そこで，図5・3に示されるようなスイッチを含む区分線形ダイオードモデルを使用す
ることを提起する・このモデルは電圧源と理想スイッチの他に線形並列抵抗（R）と線形
直列抵抗（r）を付加している．スイッチを含む枝（S枝）を流れる電流は修正節点解析
【281における電流変数となる．
並列抵抗（R）はスイッチ状態と無関係に節点Naと節点Ncの間に結合され，主に，逆
バイアス領域のダイオード特性を近似する．一般にダイオードの漏れ電流は非常に小
さな値であるので，抵抗値Rは大きな値をとる．Rの挿入によって，回路網は分離され
なくなり，さらに，電流源のみのカットセットも生じなくなる．
岩尾蓋
や
扁
Vd
図5．1ダイオードモデル
0・99・IDE
0・01・IDC
図5．2 エバース・モルモデル
61
図5．3 スイッチを含む区分線形ダイオードモデル
逆バイアス領域におけるダイオード電動dは，
佐一隼
（5．1）
となり，S枝の素子特性式【281は，
佐一隼一隼＝鴨
（5．2）
となる．
直列抵抗（r）は順バイアス領域のダイオード特性を近似する．順バイアス時のダイオー
ドのⅤⅠ特性は，非常に大きな傾きを持つ直線で近似できる．従って，抵抗値rは小さな
値をとる．
順バイアス領域におけるダイオード電流idは，
佐一隼
Zd＝
十㌔
（5．3）
となり，S枝の素子特性式【28】は，
62
叱一隼−r・∼∫＝鴨
（5．4）
となる．
スイッチ変数（S変数）Xを，スイッチOFFのときZ＝0，ONのときZ＝1となる変数Zを
用いて，
ズ＝Z・f∫＋（1−Z）隼
（5．5）
とすると，式（5．1）∼（5．4）から，
佐一隼−（1−Z＋柁）ズ＝鴨
となる．式（5．6），式（5．7）が本モデルの修正節点方程式である．
式（5・2）において，スイッチの両端の電圧町ま，スイッチがOFFの時のみ値を持ち，
隼≦0である・また，S枝の電流変数は，スイッチがONの時のみ値を持ち，f∫≧0で
ある・従って，S変数ズは正のとき電流を表わし，負のとき電圧を表わす．本論文では
ズ＝0のときも電流を表わしていると解釈している．
S変数を用いた解析では，式（5・6），（5．7）を用いて得られた修正節点方程式について，
現反復でのスイッチ状態から係数行列を決定し，節点電圧変数，電流変数，S変数を
求める・得られたS変数の値から，次反復におけるスイッチ状態を求める操作をスイッ
チ状態が変化しなくなるまで行なう・このとき・求めたS変数ズが，f≧0であれば，
式（5・5）から，項まS枝を流れる電流を表わす．従って，次の反復でのスイッチ状態は，
ONである・Ji＜0であれば，式（5・5）から，項まスイッチの端子間電圧を表わしている．
従って，次の反復でのスイッチ状態はOFFである．
以上のようにスイッチ状態をS変数の値によって決定するアルゴリズムにおいては，
複数のスイッチ状態を同時に変えることができる．従って，隣接する領域を順次決定
しながら解曲線を追跡する従来の区分線形法と比較して高速に解を求めることができ
ると考えられる．
5．3 バイポーラ回路網の動作状態解析
本章では，スイッチを含む区分線形ダイオードモデルを用いたバイポーラ回路網の
動作状態解析について述べる・本論文では，バイポーラトランジスタのモデルとして，
63
図5・2のエバース・モルモデルを用いる・図5・3のダイオードモデルを用いたときの反復
式は以下のように導出される・まず，文献【76］と同様に，トランジスタを図5．2のモデル
に置き換えて得られた回路網に含まれるダイオード及びダイオードを流れる電流によっ
て制御される電流制御電流源を全て取り除いた回路網Naに関する修正節点方程式を立
てる．これを，
Mh＝b
（5．8）
とする・ここで，Mは修正節点方程式の係数行列で，nXn次元であり，hは節点電圧
変数及び電流変数からなるn次元の未知変数ベクトル，bは走電圧源，定電流源の値を
要素とするn次元のベクトルである．
次にダイオードを回路網Naに1個加え，さらに，このダイオードの電流で制御され
る電流制御電流源を加える・ダイオード1個の既約接続行列を，nXl次元の行列Dと
し・さらに・電流制御電流源の利得行列をnxl次元の行列αで表わすと，
B＝D＋α
（5．9）
として，式（5．6）∼（5．8）から，
［M憲DTz烏に皿］
（5．10）
を得る．ここでG＝1／尺とする．
さらに，式（5・10）をm個のダイオードについて拡張すると，次式が得られる．
［MT諾DT
ただし，
芝逓Hニ］
Z−E−rZ
B＝D＋α，
G＝diag
r＝diag（17），
Z＝diag（zf）
64
（5．11）
ここで，
D：ダイオードの既約接続行列（乃×m次元）
α：電流制御電流源の利得行列（月×m次元）
E：m次元単位行列
G：ダイオードモデルのコンダクタンス行列
r 弓Z Z．Ⅹ
旦：f番目のダイオードモデル中の並列抵抗の値
ダイオードモデルの直列抵抗行列
■f番目のダイオードモデル中の直列抵抗の値
：スイッチング行列
f番目のスイッチ状態変数
m次元スイッチ変数ベクトル
である．
式（5・11）の係数行列をM∫と記述する．線形抵抗Rとrの挿入によるダイオードモデル
の修正により，行列M∫のブロック対角部分行列内にG及びrを含むことになる．それ
故，行列M∫は正則となり，反復式
［三悪M∫（Z嬬］
（5．12）
が成立する．
式（5・12）を用いた解析アルゴリズムは，以下の5ステップで実行される．
1：初期スイッチパターンZ。を決定する．
2：現在のスイッチ状態Zたを用いて・係数行列M∫を求める・
3：三角化分解を用いて，式（5．12）を解く．
4：Ⅹた＋1からZた＋1を求める．
5：Zた≠Zた＋1ならた＝た＋1としてステップ2に戻る・Zた＝Z…なら収束・
解析のフローチャートを図5．4に示す．
65
図5．4 区分線形解析のフローチャート
66
5．4 解析例
本章では，［L回路に対し，本論文で述べられたスイッチを含む区分線形モデルを使
用したシミュレーション結果を示し，図5．1の従来モデルを使用した場合と比較するこ
とにより，その有効性を確認する・図5・1のモデルを使用した解析においては，非正則
問題が発生した場合の対策が必要であるので，ここでは以下に示す手法1を用いてい
る・さらに，スイッチを含む区分線形モデルを使用した解析法として，手法2を用い
る．
［手法1］式（5・11）の係数行列に対し，r＝G＝0として得られた行列に拡張LU分解
［77】を行なう・即ち，未処理の部分行列中から絶対値が最も大きい要素を捜し，その要
素がピボット要素となるように行，列の入れ替えを行なう．未処理の部分行列がゼロ
行列となった時点で分解を打ち切る・手法1では，ピボット要素の探索が必要であり，
その分，解析時間は増加する．また，ランクが落ちた場合に，スイッチ変数Ⅹの値が求
まらない事がある・このときは，現反復でのスイッチ状態を反転して次反復のスイッ
チ状態とする．
［手法2］ダイオードモデルとして図5・3のモデルを用い，式（5．11）をLU分解によって解
く・式（5・11）の係数行列は常に正則であるから，ピボット選択は行なわない．
以上の両手法で図5．5のTTLインバータを解析した結果を表5．1に示す．mインバー
タ中にはトランジスタ4個とダイオード1個があり，スイッチ9個を含む．表5．1は
29＝512通りの全てのスイッチパターンを初期パターンとして解析を行なった結果を
示している・表5・1から，TTLインバータの解析では手法1，手法2共に初期パターン
に依存しないで収束することが分かるが，手法1では，平均反復回数が6．2回となるの
に対し，手法2では，4．1回であり，少ない反復で収束する．また収束時の各節点の電
圧は表5・2に示す通りであり，ダイオードの非線形特性として指数関数を用いてニュー
トン法を利用した解析結果とほぼ一致する・また，手法2について，並列抵抗Rおよび，
直列抵抗rの値を変えた場合の平均反復回数を表5．3に示す．表5．3から，R，r共に広い範
囲に対していずれの場合にも良好に収束していることが分かる．
これは，スイッチを含む区分線形ダイオードモデルを用いた修正節点方程式化に基づ
くスイッチの状態制御手法の適用によるものと考えられる．
67
図5．5 mインバータ
表5・
l TT L インバータの解析 における反復回数
最大反復回数
平均反復回数
9
6 ．2
6
4 ．1
従来モデル
【
手法 1 】
提案モデル
【
手法 2 】
R ＝10 10
F l0−
6
表5 ．
2 m
Vl
V2
V3
V4
V5
V6
V7
イ ンバ ー タ の 解 析 結 果
従来モデル
提案モデル
【
手法 1 】
【
手法 2 】
0．
70 v
0．
10V
5．
Ov
0．
0 0V
5．
0v
4．
3v
3．
7V
0．
70 v
0．
10v
5．
0v
0．
0 0v
5．
Ov
4．
3v
3．
7v
68
ニ ュ ー トン法
0．
66 V
0．
12 V
5．
0v
0．
00V
5．
Ov
4．
9v
4．
lv
表5．3 平均反復回数
1 0 −3
1 0 −6
10 −9
10 6
4 ．0
4 ．0
4．
0
1 0 10
4 ．0
4 ．1
4．
2
1 0 14
4 ．2
4 ．4
4 ．
4
R r
次に，図5．6の3ステートバッファに対し，無作為に選んだ24通りの初期パターン
について解析を行なった．その結果を表5．4に示す．表5．4には，24パターンに対する縮
退パターン数と収束パターン数及び収束パターンのみに対する平均反復回数が示され
ている・表より，図5．1のモデルを用いた解析は，ハイインピーダンス状態に村する解
析に対してはリミットサイクルに陥る場合が多いことがわかる．また，本モデルの利
用により，いずれの場合においてもリミットサイクルの発生が少なくなっており，収
束する場合が多くなることを確認した．
図5．6 3ステートバッファ
69
表 5．
4 3 ス テ ー トバ ッ フ ァの 解 析 結 果
V cs＝0v
従来モデル
【手 法 1 】
V in＝Ov
V in ＝5V
V in ＝O v
V in ＝5V
リ ミ ッ トサ イ ク ル発 生 ’
’
’
19
15
24
24
収束 個数
5
9
0
0
5．
2
11
−
−
0
12
0
17
収束 個数
24
12
24
7
平均 反復 回数
6．
6
8．
0
9．
3
9．1
平 均 反復 回 数
提 案 モ デル
【手 法 2 】
R ＝10 10
V csl＝5 V
リ ミ ッ トサ イ ク ル発 生 糞
堅 10−6
70
5．5 まとめ
本章では・スイッチを含む区分線形ダイオードモデルを用いた修正節点方程式を構
成し，非正則問題を回避しながら動作状態解析を行う手法について述べ，TTL回路の解
析に適用することでその有効性を示した．
本モデルを使用した解析の結果，電圧源と理想スイッチのみで構成されるモデルを
用いた解析に比べてリミットサイクル問題を相当緩和することが確認された．さらに，
収束する初期パターンを与えたときの平均反復回数もより少なくなることが確認され
た・本モデルを用いた解析においては，非正則問題は生じず，また，ピボット選択を
行なわなくても解析することが可能であるため，LU分解を専用並列計算機を用いて高
速化することが容易である．
区分線形ダイオードモデルを用いた解析の収束解は，真の解に比べて十分な精度持っ
ているとは言い難く，これを過渡解析開始時における動作点として直接用いることは
できない・しかし，動作点解析におけるニュートン反復の初期値を得る手法として用
いれば・ニュートン法に適切な初期値を与えることができるため，本手法を適用した
後・通常のニュートン反復を行えば，ニュートン法の2次収束性を効果的に利用でき，
少ない反復回数で収束させることが可能となる．これにより，大規模回路の動作点解
析の高速化が達成できると考えられる．
71
6 オーバーラップ分割を用いた反復タイミング解析
の高速化
6．1概要
LSIやマルチチップモジュールの設計においては，大規模回路の解析を高速に実行で
きる回路シミュレータの実現が重要であり，回路解析には直接法に基づく手法と緩和
法に基づく手法が使われている．
直接法は，SPICE【27樺の代表的な回路シミュレータで用いられているが，ニュート
ン・ラフソン（NR）法による解析の実行時に回路の節点数Nにほぼ等しい次元の線形連立
方程式を解く必要があり，大規模回路解析に適用すると，押オーダの膨大なメモリが
必要となる・また，回路全体を一括して解析するため，計算処理の並列化効率も悪い．
したがって，大規模回路を直接法のみを用いて解析することは困難である．
一万・緩和法に基づく解析においては，回路を複数の部分回路に分割し，部分回路
毎に解析を行うため，解析実行時に必要なメモリは節点数Nのオーダであり，さらに，
各部分回路の計算を独立して行うため，並列化効率が高い．しかし，緩和法では，解
の収束性が悪く，計算時間が増大する傾向があり，収束しない場合も多い．さらに，
収束性を向上させるために・は，回路毎に適切な分割点を決定する必要がある．
緩和法における収束性改善のために，近年，回路分割時に各部分回路の境界付近の
節点が隣接する部分回路に重複して含まれるように分割を行うオーバーラップ分割【79】
が提案され，線形回路網解析への適用例【79】・および，非線形回路網の波形緩和（WR）法
による解析への適用例が報告されている【80］【81］．
MOKARI−BOLHASSANらは，MOS回路について，ブロック境界の1節点が隣接する
ブロックに共通して含まれるようにオーバーラップ分割を行い，WR法を通用した結果，
従来のWR法と比較して緩和反復回数が約1′6程度に減少したことを報告している【80］．
また・島らは・部分回路毎に異なるレベルのオーバーラップ分割を適用したWR解析に
よるMOS回路の解析でSPICEと比較して約2倍の解析速度が得られたことを報告してい
る【811．
しかしこれらのWR法では，解析の実行時に各部分回路の応答波形を記憶する必要が
あり，大規模回路に適用した場合，膨大な波形記憶用メモリが必要である．また，WR
法の収束性は解析ウインドウに強く依存するため，適切なウインドウを決定する必要
がある・従来の解析例は緩和法の収束性が比較的よいMOS回路に適用したものであり，
収束性の悪いバイポーラ回路の解析を行った例はない．
そこで・本研究では，解析実行時のメモリ容量が小さい反復タイミング解析（ITA）法
72
に基づくブロック緩和ニュートン（BRN）法にオーバーラップ分割を適用したオーバーラッ
プブロック緩和ニュートン（OBRN）法を提案する・OBRN法ではオーバーラップ分割を
適用して，1回の緩和反復で求まる近似解の精度を向上させ，緩和反復回数の減少に
伴う高速化を達成する・解析対象の大規模回路網に対してOBRN法を適用することで，
ニュートン法，すなわち・直接法を適用する回路規模を小さくすることが可能となり，
直接法の良好な収束性を生かした大規模回路シミュレータが構築できる．
本章では・実際のバイポーラディジタル回路を例としてOBRN法の評価を行い，2000
節点以上の大規模回路に対して特に有効であることを示す．評価に用いた回路は，高
入力インピーダンス／低出力インピーダンスの基本ゲート回路によって構成されるも
のであり・本研究の大規模回路シミュレータが対象とする回路と同じ構成を持つ．ま
た，伝送線路の等価回路を含む例についても評価を行い，低出力インピーダンスの基
本回路に対して・低入力インピーダンスの基本回路を接続した場合においても，収束
性が改善されることを示す．
6．2 オーバーラップ分割の有効性
BRN法における回路分割の1例を図6・1に示す．このように回路中の各節点がいずれ
かの部分回路に重複なく含まれるように分割する・BRN法では，緩和反復の各回で，
ブロックに含まれる節点を変数とするNR法を適用して近似解を求める．これは，図6．1
に示すように，各緩和反復でブロック外部の節点に定電圧源が接続されているとして
解析することに相当し・ブロック外部の回路の影響を全て無視している．したがって，
服法を適用して得られた近似解の精度が低下し，特に，走電圧源付近の節点，すなわ
ち，ブロック境界付近の節点の近似解の精度が低下すると考えられる．さらに，W＋1回
目の反復における定電圧源の値としてW回目の反復で求めたブロック境界付近の節点の
精度の悪い解を用いると，W＋1回目の計算で得られる近似解の精度がさらに悪化する場
合がある・即ち，BRN法では，反復計算が収束しない場合が多く，収束する場合にお
いても緩和反復回数が多く・計算時間が増大する原因は回路分割方法に起因すると考
えられる．
ブロック外部の回路の影響を厳密に考慮した解析を行うためには，テブナンの定理
にしたがって，ブロック外部回路の接続点の開放電圧および，外部回路の等価インピー
ダンスを求めることが必要である・しかし，外部回路は非線形抵抗回路網であるため，
テブナンの定理を適用するためには，解析対象となるブロックとこれに接続するすべ
ての外部ブロックからなる回路全体にニュートン法を適用し，ニュートン反復の各ス
テップにおいて，外部ブロック各々の開放電圧と等価インピーダンスを求める操作を
73
行うことが必要になる・したがって，各ブロックと外部回路の接続点を平均m個とする
と・テブナンの定理を適用するためには，大規模回路全体にニュートン法を適用した
場合のm倍以上の計算量が各緩和反復で必要となるため，膨大な計算時間を必要とする．
（b）ブロック分割
図6．1ブロック分割の例
これに対し，本報告のOBRN法におけるオーバーラップ分割では，図6．2に示すよう
に・ブロック分割した各ブロックに含まれる節点を核節点とし，核節点に接続する節
点を冗長節点として付加した冗長ブロックに対してNR法を適用し，核節点に対する解
のみを用いて近似値を更新する・ここでは，オーバーラップのレベルを冗長度dで定義
する・冗長度dのオーバーラップ分割では核節点から距離d以下の位置にある節点を冗
長節点とする・例えば，図6・2（b）の冗長度1の例では冗長ブロック1，について，核節
点④から距離1の節点⑤が冗長節点であり，図6．2（C）の冗長度2の例では核節点④から
距離2以下の節点⑤，⑥が冗長節点である．
74
⑦
（b）オーバーラップ分割（冗長度＝1）
（C）オーバーラップ分割（冗長度＝2）
図6．2 オーバーラップ分割の例
75
冗長節点はブロック外部の回路の影響を代表し・さらに，走電圧源から離れた位置
に核節点が配置されるため，緩和反復の各回で求まる近似解の精度が向上することが
期待できる・以下に図6・3のモデル回路について，数式を用いて説明する．
図6・3（b）のように・従来のブロック分割を適用した場合，節点②についてキルヒホッ
フの電流別に基づく方程式
Gl（均一巧）＋G2（均一場
（Gl＋G2）鴨＝GlⅥ＋q彗
より，
Gl＋G2
G2
Ⅵ＋ハ〒∠（q
（6．3）
Gl＋G2
となる・図6・3（b）のブロック分割の場合では巧が走電圧源であるから，走電圧源の値に
対する節点電圧鴨の変動率は
旦旦＿
（6．4）
∂q Gl＋G2
一方，図6・3（C）に示すように・オーバーラップ分割を適用すると，節点③について
G2（均一場＋G3（均一場＝0
巧＝
生＿，′．q
巧＋
q十q‘▼G2＋q
である・式（6．6）を式（6．2）に代入すると
〔Gl＋q−岩石〕鴨＝Gl町
G2G3
（6．7）
であり・定電圧源均の値に対する節点電圧鴨の変動率は
些＿ G2G3
（6．8）
∂q GIG2＋Glq十qq
76
となる・式（6・4）と式（6・8）から，ブロック分割とオーバーラップ分割の場合で走電圧源の
値に対する節点電圧鴨の変動率を比較すると
GIG2
（Gl ＋G2）（GIG2＋GIG3十G2G3）
（6．9）
であるから，
q≧0
（6．10）
のとき，
旦里，卓旦
（6．11）
∂巧￣∂均
となる．
”＿．…王G二三G2言G3壬G；
Vl V2 V3 V4
Gj：コンダクタンス
（a）モデル回路
Vl
V2
（b）ブロック1（ブロック分割）
Vl V2 V3
核節点：①、②
冗長節点：③
（C）冗長ブロック1，
（オーバーラップ分割：冗長度＝1）
図6・3 オーバーラップ分割の効果
77
式（6・11）から分かるようにOBRN法では，核節点の解に対して定電圧源の値の影響が
BRN法より小さくなると考えられる・これによって緩和反復1回で求まる近似解の精
度が向上し，緩和反復回数の減少による高速化が図れる．同時に，緩和反復が収束す
る場合が多くなることが期待できる．
上記の議論から，OBRN法においては・冗長度を大きくするほど緩和反復が減少し，
収束する場合が多くなると考えられるが，冗長度が大きくなるにしたがって，計算量
は増大する・したがって・OBRN法による解析を行う際には，回路毎に最適な冗長度を
決定する必要がある．
本章ではOBRN法の有効性を確認するため・回路シミュレータ開発用支援ツール【59】
を用いて・OBRN法による解析プログラムと，従来法であるBRN法および直接法による
解析プログラムを構築し・簡単なECL回路を例として，計算時間，解析解の比較を行っ
た結果を示す・上記ツールでは，キルヒホッフの電流別に基づく回路方程式が用いら
れ，数値積分法は後退オイラー法である．
6．3 0BRN法の評価
6・3・1解析プログラムの構成と解析回路例
解析プログラムは，オーバーラップ分割部と解析実行部から成る．oBRN法による解
析実行部のフローチャートを図6・4に示し，ニュートン法の計算処理フローチャートを
図6．5に示す．
オーバーラップ分割部では以下のようにオーバーラップ分割を実現している．
①：回路をネットリストにしたがって，ブロック分割する．ブロック分割には，ゲー
トレベル分割法［68】を用いる．
②：ブロック分割した各ブロックに含まれる節点を核節点とし，冗長ブロックの初期
値とする．
③：冗長ブロックに含まれる節点と距離1の節点を接続行列から求め，冗長節点とし
て冗長ブロックに付加する．本操作によって冗長度が1増える．
④：既定の冗長度に到達するまで③を繰り返す．
オーバーラップ分割における冗長度の決定方法については，後述する．
解析実行部は・BRN法と同様に各冗長ブロックについて独立に服法を適用して解を
求め核節点に対する解のみを用いて近似解を更新する・緩和反復は，冗長ブロック外
部の節点に接続する走電圧源の値として，前回の緩和反復で得られた近似解を用いる
Jacobi型の反復を用いている．
78
図6・4 0BRN法による解析実行部のフローチャート
79
図6．5 ニュートン法のフローチャート
解析回路例は図6・6のECLリング発振器と図6・7のECL非同期カウンタを用い，ECLゲー
トは，図6・8に示す回路とした．また，図6．6中の伝送線路は図6．9に示す等価回路を用い
て伝送線路1本を1ゲートとして定義し，図6・7のD一汗は図6．10に示すように2入力，
3入力のECL−NORゲートで記述した．トランジスタモデルはEbe，S＿M。11モデルとした．
図6・6の回路は，低出力インピーダンスの回路に低入力インピーダンスの回路を接続し
た例であり，図6・7の回路は高入力インピーダンス／低出力インピーダンスの回路を接
続して構成しており，本研究の解析対象回路の典型的な例である．
80
二二一、∴二∴
図6．6 解析回路例1
、二・、∴、、
図6．7 解析回路例2
図6．8 ECLゲートの内部回路
△L△L
△L△L
△R △R
△G △C
①一任＝h
図6．9 分布定数線路の等価回路
81
図6．10 D−FF回路
6・3．2冗長度と計算時間の関係の評価
はじめに・OBRN法の有効性を確認するため，1時刻の解析に要する計算時間と冗長
度の関係を求めた・前述のように，OBRN法では，冗長度を上げると緩和反復回数が減
少することが期待できるが，緩和反復1回の計算量は増大するため，計算時間が最小
となる冗長度が存在することが予想できる．
解析回路例1・2について・時刻0の解析を行い，各緩和反復で得られた近似解の
誤差をそれぞれ図6・11，図6・12に示す．ここで，誤差は，
巧拙，ⅤトAりl
（6．12）
F：数値積分法適用後の回路方程式
Yと：k回目の緩和反復で求めた近似解
と定義した．また，緩和反復の打ち切り条件は，
ど＜10￣5
（6．13）
とし，BRN法，OBRN法とも共通とした．
図6・11，図6・12からわかるように，冗長度が増大すると，緩和反復1回で求まる解の
精度が向上し・それに伴って，緩和反復回数が減少する．この傾向は，解析した2例
について同じであるが，回路例1における収束性改善効果の方が際立って大きくなっ
ており・OBRN法が低出力インピーダンスの回路に低入力インピーダンスの回路を接続
した場合のような・緩和法にとって条件の悪い場合に特に有効に機能する可能性を示
唆している．
82
△t＝10−12
→ト￣BRN法
le￣oBRN法（冗長度：1）
＋oBRN法（冗長度：2）
￣十汁￣OBRN法（冗長度こ3．1
＋oBRN法r冗長度：4）
→トOBRN法（冗長度‥7）
＋oBRN法（冗長度：10）
0 510遠点反羞0（回デ5303540
図6．11近似解の誤差（解析回路例1）
△t＝10−12
一一el BRN法
♯￣OBRN法（冗長度：1）
＋oBRN法（冗長度：2）
￣￣う←oBRN法（冗長度：3）
￣1トoBRN法（冗長度：4）
￣￣各l OBRN法（冗長度：7）
OBRN法（冗長度：10）
10
−7
0 5 10 15 20 25 30 35 40
緩和反復（回）
図6・12 近似解の誤差（解析回路例2）
また，計算時間については，図6．13，図6．14に示すように，最初は冗長度の増大に伴
う緩和反復回数の減少にしたがって減少していくが，ある冗長度を越えると，冗長節
点の増加に伴う計算量増大の影響が顕著になり，計算時間は逆に増大する．
図6・13，図6・14より，最適な冗長度は回路によって異なっている．また，冗長度が増大
83
した場合の計算量の増大率は，各冗長ブロックの核節点数と冗長節点数の比率で決定
されるため，最適冗長度はブロック分割時のブロックサイズによっても変動する．
過渡解析においては，時間刻み△tは動的に変化し，これによっても，OBRN法の収
束性が変わると考えられる．時間刻み△tを変えた場合の計算時間を図6．15，図6．16に示
す・△tが大きい場合，即ち，収束性が悪い場合には，最適な冗長度は大きくなる傾向
があることがわかる．以上の結果から，OBRN法による解析を行う際には，回路毎に適
切な冗長度を決定する必要がある．
4
冗長度
6 8 10
図6．13 冗長度と計算時間（解析回路例1）
6
冗長度
8 10
20
図6．14 冗長度と計算時間（解析回路例2）
84
︵S︶ 匝皆琳缶
皿 80 60
0 2 4
0 2 4 6
冗長度
8 10
図6．15 最適冗長度の変化（解析回路例1）
0 2
4
冗長度
6 8 10
図6．16 最適冗長度の変化（解析回路例2）
85
6．3．3冗長度決定アルゴリズム
前述のように，最適冗長度は，
①回路構造，
②ブロック分割時のブロックサイズ，
③数値積分の時間刻み，
によって変化するため，ネットリスト等の回路解析の入力情報から適切な冗長度を決
定することは困難である．
そこで，本OBRN法では，解析の先頭で，適切と予想される冗長度を決定して解析を
開始する静的冗長度決定アルゴリズムと，解析実行中に適切な冗長度に調整する動的
冗長度決定アルゴリズムを用いて冗長度を決定することとした．
静的冗長度決定アルゴリズムでは，冗長度0から既定の最大冗長度まで冗長度を増
加させながら時刻0の解析を行い，その計算時間が最小となる冗長度を解析開始時の
適切な冗長度とする・ここで，3・2節で示したように，△tが小さい場合の適切な冗
長度を用いるより△tが大きい場合に対応する適切冗長度を用いたほうが，計算時間が
短縮されるため，△tを既定の最大時間刻みとして冗長度を求めている．
本解析では，1時刻の解析毎にLTEを求めて△tを決定している．解析の効率化のた
めには，過渡解析の実行中に△tの変化に伴って冗長度を変化させることが望ましいが，
オーバーラップ分割を行う際に，各冗長ブロック中の節点と他のすべての節点の接続
を調べる必要があるため，特に大規模回路に対しては，分割処理の所要時間が長く，
計算時間が増大する・そこで，動的冗長度決定アルゴリズムでは，過渡解析中に緩和
反復が発散した場合に限ってオーバーラップ分割を再度実行し，冗長度を上げて解析
を試みる方法を採用することとした・以上の冗長度決定アルゴリズムを用いて，
図6・6，図6・7の回路について，電源投入直後から直流動作点に到達するまでの過渡解析
を行った結果，直接法と一致する解析解が得られることを確認した．
また，動的冗長度決定アルゴリズムに関しては，ある時刻に対する解析の実行中に
緩和反復が発散した場合に，
①冗長度を上げる，
（∋△tを下げる
方法がある・冗長度を変えず，△tを下げて解析を再度実行する方法では，本報告の解
析例については全て収束させることができた・これに対し，発散した場合に，△tを変
えず・冗長度を上げて再度解析する方法では，冗長度を2倍以上に上げても収束しな
い場合があることを確認した．さらに，解析実行中に緩和反復回数が既定値を越えた
86
場合に冗長度を上げるアルゴリズムについても検討したが，前述したように，再度オー
バーラップ分割を実行するために計算時間が増大することも確認した．
以上の検討から，冗長度の決定は，本論文の静的冗長度決定アルゴリズムのように，
解析開始時に最悪条件下での最適冗長度を決定し，解析実行中は常に同一の冗長度を
用いるほうが計算時間を短縮できるといえる・冗長度を動的に変化させる場合には，
効率的なオーバーラップ分割アルゴリズムが必須である．
6．4 回路規模と解析時間
大規模回路に対するOBRN法の適用性の評価では，回路規模に対する過渡解析の解析
時間を評価する必要がある・緩和法では，回路構造によって収束性が異なるため，回
路構造が同一で回路規模だけが異なる回路を用いて評価することが重要である．そこ
で・図6・7の非同期カウンタ回路を2段，4段，16段，32段に従属接続した回路を
例として，回路規模に対する解析時間，緩和反復回数を評価した．
図6・17に回路規模に対する解析時間を直接法を用いた場合と比較して示す．
図6・17からわかるように，直接法を用いた解析では，解析時間が回路規模の増大にと
もない，節点数の多項式オーダで急激に増大する．これに対し，OBRN法を用いた場合
では，解析時間は回路規模にほぼ比例しているが，表6．1のように回路規模の増大にと
もなって平均反復回数が若干増大するため，OBRN法の解析時間は回路規模に完全には
比例しない．
本評価に用いた回路例は，回路規模と解析時の計算量がほぼ比例する．直接法の解
析時間が図6・17のように増大する原因は，解析実行時に回路行列を格納するために必要
なメモリ量が増大し，行列計算時に大容量のメモリ領域を扱うため，キャッシュメモ
リのヒット率が低下し，メモリアクセス時間が増大することが原因であると考えられ
る・これに対して，OBRN法では，解析実行時に扱う行列のサイズは，各冗長ブロック
のサイズによって決定されるため，回路規模によらずほぼ一定の値となる．したがっ
て，キャッシュメモリのヒット率も回路規模に依存しないため，解析時間は計算量に
ほぼ比例して増大すると考えられる．
87
4
0・
3・ 53・ 02・ 52・ 01・ 51・ 00・ 5
︵Sの〇二匝皆毎駐
やか寸N
∞寸N−
N
くつ＼
○ヽ
寸
節点数
図6．17 回路規模に対する解析時間
表6 ．
1
段数
0 B R N 法 に よる解 析 結 果
反復 回数
ポ イ ン ト数
平均 反復 回数
1
2 3 5 9
4 5 0
5 ．2 4
2
2 7 4 3
4 6 3
5 ．9 2
4
2 9 4 5
4 7 1
6 ．2 5
8
3 0 7 5
4 7 1
6 ．5 2
1 6
3 1 6 4
4 6 5
6 ． 7 7
3 2
3 3 6 3
4 7 0
7．
． 1 5
88
6．5 まとめ
本章では，大規模回路の高速解析アルゴリズムとして，回路分割法にオーバーラッ
プ分割を用いて反復タイミング解析を行うOBRN法を提案し，実際のバイポーラ回路を
例として評価した．
OBRN法は，解析の実行時に大規模行列の計算を行わないために節点数の1乗オーダー
のメモリ量で解析できるとともに，オーバーラップ分割の導入によって緩和反復回数
を従来の緩和法より減少させ，その結果として，従来法より高速に解析できることを
示した・実際のECL回路を解析対象として評価した結果，OBRN法は従来法であるBRN
法の4倍以上高速であることを確認した・さらに，2000節点程度以上の大規模回路に
対しては，直接法より高速であり，大規模回路解析への適用性に特に優れていること
を確認した．
OBRN法は，冗長分割の適用によって，緩和反復1回あたりの計算量が増大するが，
求まる近似解の精度が飛躍的に向上するため，反復回数を劇的に減少させることがで
き，その結果として，回路シミュレーションの高速化を達成するものといえる．この
効果は，各部分回路の大きさには依存せず，単に冗長度のみに依存するものであるこ
とから，各部分回路を大きくすることによって，計算量の増大を抑制することができ，
さらに有効性を増す・通常の逐次計算機を用いる場合は，部分回路のサイズを小さく
することが求められるため，OBRN法を有効に活用することが難しいが，．本研究で提案
するように，ニュートン反復をLU分解専用並列計算機で高速化することにより，部分
回路のサイズを大きくとることができるようになる．したがって，OBRN法は，本研究
の大規模回路シミュレータに非常に適した手法であるといえる．
89
7 波形緩和法の高速化手法
7．1概要
大規模回路では，部分回路によって動作速度が大きく異なるマルチレート性を有す
る場合が多く，これを同一の時間刻みで回路シミュレーションすると，高速動作する
部分に合わせて全体の時間刻みを設定する必要があるため，低速動作する部分回路に
ついては不要な計算を行うことになる．たとえば，リセット信号系や，DC的な制御信
号を生成する制御回路などは，ほぼ直流に近い動作速度であることから，主信号系の
時間刻みより大きな時間刻みを適用して解析できる．さまざまな機能ブロックから構
成され，機能ブロックごとに動作速度の大きく異なる大規模回路シミュレーションで
は，マルチレート性を利用した高速化が重要となる．
回路のマルチレート性を有効に利用するためには，波形緩和法［23】の通用が有効であ
る・波形緩和法は，もとの大規模回路をいくつかの部分回路に分割し，それぞれの部
分回路について，解析時間ウインドウ内の過渡解析をそれぞれ個別に実行する．した
がって，各部分回路の解析に異なる時間刻みを適用でき，大規模回路のマルチレート
性を利用できる・しかし，帰還ループを含む回路では，係数行列の対角優位性が成り
立たない場合が発生し，収束性が劣化する問題があった【821【83】．また，波形緩和法で
は，部分回路外部にある節点については初期波形を仮定して，部分回路の解析を行い，
その結果を用いて次の媛和反復における波形を決定する．したがって，初期値を最適
に決定することは事実上不可能であり，各緩和反復において回路シミュレーションの
開始時刻に近い方から順に正しい解が確定していく現象が起こる［30】．これは，緩和反
復初期においては，解析の時間ウインドウの後半に近くなるほど無駄な計算を実行す
ることになり，逆に，緩和反復末期においては，時間ウインドウの前半で無駄な計算
を実行することになる．さらに，部分回路の解析順序を信号の伝搬方向と一致させて
解析することが重要となるが，部分回路間で帰還ループを構成する場合に，まだ解析
を行っていない部分の影響を受けてしまうため，帰還部分での収束性がもっとも劣化
し，全体の緩和反復回数を増加させてしまう．そこで，従来は，帰還ループを切り離
す方法や，帰還ループ回路全体を1つの部分回路として解析する手法がとられていた．
しかし，ループを切り離すことで収束性が劣化してしまう場合が多く，この方法は一
般的でない・また，本研究のように大きな部分回路に分割して波形緩和法を適用する
ような場合は，帰還ループ全体を1つの部分回路とすることは困難である．
そこで，本研究では，部分回路間で局所的な帰還ループを構成する場合の波形緩和
法の収束性を改善するため，帰還回路間でのみ局所反復【841を行うとともに，この局所
90
反復に，全体の解析時間ウインドウより短い時間ウインドウを通用するウインドウ分
割を適用する高速波形緩和アルゴリズムを提案する．局所的帰還ループを構成する部
分回路間で局所反復を適用することによって，すでに収束した部分回路や，帰還ルー
プ部分の影響を受けない部分回路に対する緩和反復を繰り返すことが避けられ，その
結果として，全体の緩和反復回数を減少させることができる．
さらに，帰還を構成する部分回路間の解析に限定して，回路全体の解析時間ウイン
ドウより短い時間ウインドウを用いるウインドウ分割を適用する．部分回路間で帰還
ループを構成する回路のシミュレーションでは，緩和反復の初期に時間ウインドウの
後半部分で，まだ収束していない解析解を入力としたシミュレーションを行っている
ことになり，この部分の収束性が劣化することによって計算時間が増大する．逆に，
緩和反復の末期では，すでに収束した時間ウインドウ前半部分に対しての解析を繰り
返すことになり，これによっても計算時間の増大を招く．したがって，時間ウインド
ウを小さくして解析することが求められるが，大規模回路全体の時間ウインドウを小
さくしてしまうと，マルチレート性を有効に利用することができず，効率が悪い．本
研究で提案するウインドウ分割は，帰還ループを構成する部分回路間のみに，ウイン
ドウ分割を適用するものであるため，全体の時間ウインドウとは独立に，収束性の悪
い部分の時間ウインドウを決定することができ，マルチレート性を有効に利用しなが
ら収束性を改善し，高速化が達成できる．
本章では，提案するアルゴリズム有効性を示すため，MOSディジタル回路に部分反
復とウインドウ分割を適用した例を示す．
7．2 部分反復による高速化手法
波形緩和法において帰還ループのある回路を解析する上での問題点に，まだ解析を
行っていない部分の影響を受けることが挙げられる．波形緩和法では，回路の解析を
行う際に回路をいくつかの部分回路に分割する．部分回路間に帰還ループがないとき
は，信号の流れにしたがい，それぞれの部分回路の解析を順に行う．しかし，帰還ルー
プを構成する場合は，まだ解析を行っていない部分回路からの信号が必要になるといっ
た問題が生じる．
例として図7・1に示すようなA，B，C，Dの4つの部分回路から構成され，部分回路
B，Cが局所帰還ループを構成する回路について考える．ここで，図の矢印が信号の伝
搬方向を表す．
この回路については，まず部分回路Aについての解析を行い，次に部分回路Aの出力
を入力として部分回路Bを解析するのであるが，入力として部分回路Cの出力を必要と
91
する・この時点では・部分回路Cはまだ解析していないため，前回の緩和反復で求めた
出力か・適当な初期値を与えることになる・その結果，部分回路Bの出力は，部分回路
Cの出力を正確に反映したものではなくなるため，正しい出力波形にならない．さらに，
部分回路Cの解析では，もともと正しくない部分回路Bの出力を入力として与えること
になるため，ここでも誤った波形を得ることになる．このように，帰還ループがある
回路の解析では，帰還の影響により，解析順が後の部分回路に誤った波形を次々と与
えることになり・正しい結果を得ることができないため，収束性が劣化し，回路全体．
の大域的反復（GlobalIteration）回数と解析時間が増加する．この現象は，ループ1周の
信号伝搬遅延時間が短い帰還ループの場合に特に顕著に現れる．
従来，部分回路間に帰還ループを含む回路を解析するときは，図7．2に示すように帰
還ループの枝を切り離す方法がとられていた・しかし，この方法では，帰還の影響を
完全に無視するため，帰還の影響が小さい場合に限ってのみ有効であり，一般的とい
えない・そこで，図7・3に示すように，帰還ループを構成する部分回路B，Cを1つの部
分回路として解析を行う手法が考えられている・しかし，図7．3の方法では，帰還ルー
プ全体を覆う部分回路が非常に大きくなることが予想され，特に，本研究のように，
部分回路を大きく分割する用途では現実的でない．
そこで・図7・4に示すように，局所帰還ループを構成する部分回路間に部分反復（Local
Iteration）を適用する・すなわち，一連の部分回路の解析に関しては，信号の伝搬順序に
したがって波形緩和反復を実行するのであるが，帰還ループを構成する部分回路B，C
については，この部分が収束するまで緩和反復を行い，収束した後に次の部分回路Dの
解析を行う・この方法では，帰還ループの影響を考慮して解析した結果を部分回路Dの
入力としているので収束性の向上が期待できる．
図7．1帰還ループを含む回路
92
l‥一一…一一一一一一一一一一‥−‥一一一一‥−t‥■日日■■■■■■日
globaliteration
図7．2 従来の解析手順
lH■一日‥‥一一一一一一一一‥一一一一‥−‥一一一‥＝■■●■●一日■＿＿
globalIteration
図7・3 従来の帰還ループに対する解析手順
」−‥一一日……一一一‥一一一‥＝−‥一一日−一一日HHH一日＝
globalIteration
図7．4 部分反復を用いた解析手順
93
7．3 ウインドウ分割による高速化手法
帰還ループを含む回路では，解析時間ウインドウを大きくとると，帰還の影響によ
り，ウインドウの後半部分での収束性が悪化する．さらに，収束性の悪い後半部分を
解析するために・すでに収束した前半部分の解析を繰り返し実行することになるため，
計算時間が増大する．すなわち，帰還ループを含む回路については，解析時間ウイン
ドウを短くすることが必要となる・しかし，大規模回路全体に対して小さなウイン、ド
ゥを適用すると，マルチレート性を有効に利用することができなくなる問題がある．
このような問題を解決するため，本研究では，局所帰還ループを含む部分回路のみ
に小さな解析時間ウインドウを適用することを提案する・たとえば，図7．1の回路では，
部分反復を行う部分回路B，Cに対して，回路全体に対する時間ウインドウを分割した
小さな時間ウインドウで解析を行う．このときの解析手順を図7．5に示す．部分回路
B，Cを解析するときは，まず，解析時間ウインドウをいくつかのサブ・ウインドウに
分割し・最初のサブ・ウインドウの部分反復を行って収束させる．その後，2番目，
3番目のサブ・ウインドウについて解析を行って，全体のウインドウに対する解を求
める・帰還ループを構成しない部分回路A，Dについては，従来どおりに解析時間ウイ
ンドウ全体で連続的に解析を行う．
このように帰還ループを含む部分回路に部分反復とウインドウ分割を用いた波形緩
和法を適用すると・収束に多くの反復を要する区間だけの解析を行うことができ，ま
た，すでに収束した部分の解析を繰り返さないことから，収束性を改善するとともに，
解析時間を短縮することができると考えられる．
A
− − −
B
■■ ■■
■■ − ■■
一 一 一 ■■
− →− ■■
■■ − −
一一一一一一
−
＿上で￣
−
C
D
■■ ■■
−
V￣
一一￣ −
一 一 一 一
■■ − ■■
図7．5 ウインドウ分割を適用した場合の解析手順
94
7．4 評価結果
ここでは，部分反復とウインドウ分割手法の有効性を確認するため，局所帰還ルー
プを含む実際の回路について，波形緩和法による解析を行った結果を示す．wR法では
部分回路の過渡解析を各緩和反復で行うが，本評価に用いたプログラムは，第6章に示
したニュートン法のアルゴリズムに従った直接法の解析プログラムを各部分回路の過
渡解析に用い，時間刻みについては固定値としている．
評価に使用した回路は，図7・6（a）に示すMaster−SlaveTflip−nOpであり，各論理ゲート
はMOSトランジスタで構成されるものとした・また，部分回路は，ゲート単位で分割
することとした・2入力および3入力NAND回路のトランジスタレベルの回路図を
図7．6（b）に示す．
図7・6の評価用回路は，部分回路4，5，ならびに，部分回路8，9の間に局所帰還
ループが存在する・この部分に部分反復とウインドウ分割を適用する．このときの解
析手順を図7・7と図7・8に示す・また，入力波形とシミュレーション結果の出力波形を
図7．9に示す．
表7・1および表7・2は各々の部分反復における反復回数を示している．部分反復回数に
ついては・上から大域的反復1回目，2回目，3回目，4回目の順で示す．また，解
析時間の比較を表7・3に示す・表7・3における解析時間の比は部分反復を適用し，ウイン
ドウ分割数を1とした場合を基準として示している．
部分反復を適用した場合と適用しない場合とを比較すると，適用しない場合は大域
的反復回数が12回であり，適用した場合は4回に減少している．さらに，部分反復
回数は・部分反復Aで16回・部分反復Bで11回となっており，その約半数の反復が，
大域的反復の1回目で行われていることがわかる・これは，緩和反復の初期において，
各部分回路の入力として仮定した波形と，実際の波形の差異が大きい場合に，部分反
復回数が多くなることを示している・部分反復を適用することによって，緩和反復を，
収束性の悪い部分回路間に集中させることができ，その結果，大域的反復回数が減少
することがわかる・この傾向は，ウインドウ分割を適用した場合にも見られるが，大
域的反復の1回目における部分反復の回数と2回目以降の大域的反復における部分反
復の回数がともに減少する傾向があることがわかる．この結果から，ウインドウ分割
によって，収束性の悪かったウインドウ後半部分の収束性が改善され，部分反復回数
が減少していることがわかる．
計算時間についても，表7・3に示したように，部分反復の適用にともなう大域的反復
回数の減少によって，約2倍の高速化が達成される．さらに，ウインドウ分割を通用
することで，ウインドウ分割数の増加にともなって計算時間が減少していくことがわ
95
かる．
以上の評価結果から，局所帰還ループを有する回路の波形緩和解析の高速化のため
に部分反復ならびにウインドウ分割アルゴリズムが有効であることが確認された．
（a）Master−SlaveTflip−nOp
Vdd
Vdd
OUT
OUT
2入力NAND回路
3入力NAm回路
（b）NAND回路
図7．6 シミュレーション回路例
96
globalIteration
図7．7 部分反復を適用した解析手順
1
2
3
二二二：二二：：：三：＝
ヽ■L
tL
一 一 一 一 一 一
一 一 一 一 一■ −
4
■■
■■
こユーご二
■■
一 一 ■ 1■■ ■■
■■
ここbf二二
5
■ 一 一 一 ■
ニュー∫二二
■■ r
l ■■
一 一 一 一 一 一
6・一一一一一一一一一一一￣￣￣￣￣￣
7止一一一一三一一一一一一￣￣￣；￣二二二
一一一一一一一一一一一一一一一一一−■
一 一 一 一 一 一 一
こユーご二
一 一 一 1■■ ■■
■■ ■■
ここ、′二二
二二、どこ
■■ r
Wi n d ow
図7・8 ウインドウ分割を適用した解析手順
97
l ■■
︵A︶ト
0 5
︵
A
︶
U
0 5
l l l l l l I
l l I l l l l ︵
A
︶
ご
l 10 0 −
20 0 30 0 4 0 0 TIME（ns）
図7．9 入力および出力波形
98
5
表 7．
1
反復 回数 （
L bcalIteration A ）
N um ber
Of sub−
W in do w s
1
2
4
8
1 6
N um bero f Iteration
g lob al 0 loca1 8
5
2
1
4
6
4
1
1
4
6
5
2
1
5
4
1
1
4
6
3
1
■
1
2
1
1
1
4
4
50 0 【
n s】
2
1
1
1
5
4
1
1 、
2
1
1
1
3
2
1
1
5
4
1
1
4
3
1
1
3
3
1
1
5
3
1
1
5
2
1
1
4
2
1
1
99
4
2
1
1
6
5
2
1
5
2
1
1
4
2
1
1
4
2
1
1
4
3
1
1
4
2
1
1
4
2
1
1
4
3
1
1
4
3
1
1
4
3
1
1
5
5
2
1
4
3
1
1
4
4
2
1
4
4
2
1
表7 ．
2 反復 回数 （
L ocalIteration B ）
N um ber
O f sub一
W in do w s
N um ber of Iteration
glo bal 0 1
loc a1 7
2
1
1
4
2
5
1
1
1
4
4
5
1
1
1
2
1
1
1
4
1 6
7
2
1
1
2
1
1
1
4
8
50 0 【
n s】
2
1
1
1
4
2
1
1
1
2
1
1
1
2
1
1
1
5
1
1
1
2
1
1
1
2
1
1
1
2
1
1
1
5
1
1
1
2
1
1
1
4
1
1
1
5
2
1
1
4
1
1
1
4
1
1
1
3
1
1
1
4
1
1
1
3
1
1
1
4
1
1
1
5
2
1
1
4
1
1
1
4
1
1
1
4
2
1
1
4
2
1
1
4
2
1
1
表7 ．
3 解析 時 間
L ocal
Iteratio n
W itho ut
N um ber
Of
Sub W in dow s
N um b er of
g lob al
iteration s
1
1 2
1
4
2
4
4
4
8
4
1 6
4
W ith
A：localiterationA B：localiterationB
100
C P U tim e lsec］
（
R atio ）
T otal
B
・A
7 17 1
84 6
839
（
1．
995）
（
0．
797 ） （
1．
12 3）
3 600
106 1
・74 7
（
1．
00 0）
（
1．
0 00 ） （1．
000 ）
32 92
858
63 9
（
0．
9 14 ）
（
0．
809） （
0．
855 ）
306 9
7 64
509
（
0．
85 3）
（
0．
72 0） （
0．
6 8 1）
290 2
6 50
4 57
（
0．
806 ）
（
0．
6 13） （
0．
6 12）
2 775
55 9
4 22
（
0．
7 7 1）
（
0．
527 ） （
0．
56 5）
4
2
1
1
7．5 まとめ
本章では，大規模回路のマルチレート性を有効に利用できる波形緩和法の収束性を
改善し・高速化を達成する部分反復・ウインドウ分割アルゴリズムを提案し，実際の
回路を用いて評価した結果を示した．
部分反復アルゴリズムは，部分回路間に局所的な帰還ループが存在する場合に，大
域的緩和反復中で，局所帰還ループ間だけに部分反復を適用することによって，収束
性の悪い局所帰還ループ部分のみに集中的に緩和反復を行い，求まる近似解の精度を
向上させるものである・その結果，収束性が比較的良好な部分の無駄な計算を省くこ
とが可能となり，大域的緩和反復の回数を飛躍的に削減することができることを示し
た・これにともなって，計算時間も減少することを，実際の回路例を用いて検証した．
ウインドウ分割アルゴリズムは，解析時間ウインドウの後半部分の収束性を改善す
るために，時間ウインドウをいくつかのサブ・ウインドウに分割し波形緩和解析する
ものである・これは，緩和反復初期における時間ウインドウ後半部分の収束性を向上
させるとともに，緩和反復末期の時間ウインドウ前半部分の無駄な計算を省くことに
より高速化を達成する．波形緩和法では，マルチレート性を有効に利用するためには
ウインドウサイズを大きくして，可能なかぎり大きな時間ステップで解析することが
望ましく，ウインドウ分割手法とは矛盾してしまうため，本研究では，部分反復アル
ゴリズムと融合し，特に収束性の悪い局所帰還ループ部分についてのみウインドウ分
割するものとした・本アルゴリズムを通用することにより局所帰還ループ部分の部分
反復回数を削減し，その結果として高速化が達成されることを実際の回路例により確
認した．
部分反復アルゴリズムは，回路構造を反映して計算資源を収束性の悪い部分回路に
集中させるアルゴリズムであると言える・・また，ウインドウ分割アルゴリズムは，回
路の時間応答を反映し，回路の状態が急峻に変化する収束性の悪い時刻の解析に計算
資源を集中させるものと言える．
本アルゴリズムを，大規模回路シミュレーションの最上位の大きな部分回路への回
路分割と対応づけることにより，回路のもつマルチレート性を有効に利用できるよう
に設計者が分割位置を指定することが容易であると同時に，帰還ループが発生するよ
うな分割になった場合においても，波形緩和法のもつ有効性を維持することが可能と
なると言える．
101
8 結論
8．1総括
マルチメディア社会を支える高速なコンピュータや大容量通信システムなどの高速
情報処理システムを構成するために，LSIの大規模・高密度化ならびに高速化は著しく
進んでおり，また，回路の小規模化・低消費電力化に有効なAの混載LSIも開発されて
いる・このようなLSIの設計および動作検証には，回路のアナログ的な挙動を詳細に解
析することが不可欠となり，極めて大規模な回路の詳細解析を実用的な時間で実行で
きる大規模アナログ回路シミュレータが必要となってきた．
本論文では，主に，論理LSIなど高入力インピーダンス／低出力インピーダンスの基
本回路を組み合わせて実現される大規模回路の過渡解析を高速化することを目的とし
て，その要素技術となる専用並列計算機と動作点解析用区分線形モデルおよび，高速
な緩和アルゴリズムを提案した．
本研究の目的とする回路シミュレータにおいては，解析精度は従来の回路シミュレー
タと同等で，高速化の代償として解析精度を低下させることはないものとし，数値計
算の収束性と収束しやすさについても従来の回路シミュレータと同様のレベルを確保
するものとした・したがって，収束性に優れた直接法を本研究の回路解析手法のベー
スとして用い，直接法による回路シミュレーションを高速化するLU分解専用並列計算
機と簡易な区分線形ダイオードモデルを提案し，直接法を適用できる回路規模を大幅
に増大できる見通しを得た．さらに，直接法が通用できない規模の回路に対して適用
するオーバーラップ分割による高速反復タイミング解析手法を提案し，直接法の良好
な収束性を保ったまま解析可能な回路規模を飛躍的に増大させると同時に高速化を達
成できることを示した．さらに，大規模回路のマルチレート性を生かして回路シミュ
レーションを高速化するために，波形緩和法の収束性改善アルゴリズムを提案し，最
上位レベルの回路分割としてこれを用いることでマルチレート性を有効に利用して高
速化できる見通しが得られた．
本論文では，最初に，最も小さな部分回路レベルに適用する直接法の高速化手法を
示した・始めに，直接法において，計算時間の多くを占める回路行列の三角化分解に
特化したLU分解専用並列計算機SMASHを提案した．sMASHでは，複数個のプロセッ
サを1群として管理するクラスタ方式を採用して，プロセッサ間のバス競合を回避す
るとともに，LU分解実行時の列番号整合操作を専用回路SRUで並列化することにより，
プロセッサ稼働率を高めることができることを示した．また，節点分割法にもとづく
前処理を行うことによりSMASHの動作効率をより高めることができるとともに，複数
102
のメモリバンクを有するメモリユニットを介してホスト計算機と接続することによっ
て，ホスト計算機上での処理とSMASHの動作を独立させることが可能となり，回路シ
ミュレーションシステムとしても高い効率で動作することを示した．実際の回路例で
評価した結果，回路シミュレーションシステムの計算時間は，素子モデルの計算時間
とほぼ同一であることを確認している．この結果から，SMASHを含む回路シミュレー
ションシステムにおいては，素子モデルの計算時間の短縮によりさらに高速化できる
ことが示された・次に，過渡解析に先立って行う動作点解析の高速化を目的として，
スイッチと抵抗のみで構成される簡易区分線形ダイオードモデルを提案した．これは，
スイッチレベルシミュレーション手法で用いられていたダイオードモデルを区分線形
ダイオードモデルへ拡張するものであり，本モデルによって，回路トポロジの動的変
化を解消し，従来の直接法と同じアルゴリズムを用いて回路解析が可能となると同時
に，SMASHを含む回路シミュレーションシステムの通用も可能となる．本研究では，
提案した区分線形ダイオードモデルによる回路解析をニュートン法の初期値を求める
計算として利用する．これにより，ニュートン法の2次収束性を有効に利用すること
が可能となり，ニュートン反復回数を削減できる．これらの直接法の高速化手法を用
いることによって，従来は，膨大な計算時間が必要であり，それゆえ非現実的とされ
ていた数十万節点クラスの大規模回路に対する直接法適用の見通しが得られた．
次に，直接法で取り扱えない大規模回路に対しては，直接法の限界の大きさに分割
した部分回路ごとの反復タイミング解析を用いることとし，その高速化手法を提案し
た・従来の反復タイミング解析では，直接法に比較して収束性が悪く，また，回路の
分割点を最適に選ばないと収束しない場合も多くあった．そこで，本論文では反復タ
イミング解析における収束性を劇的に改善できるオーバーラップブロック緩和ニュー
トン（OBRN）法を提案した．oBRN法は，部分回路の境界付近にある素子や節点を隣接
する部分回路に重複して含むよう冗長分割して解析する手法であり，1回の緩和反復
で求まる近似解の精度を向上させ，緩和反復回数を減少させることによって従来の反
復タイミング解析法（BRN法）と比較して10∼1000倍の高速化を達成できることを示
した・また，OBRN法は，適用する回路規模が2000節点以上と大きい場合に，回路全体
に直接法を適用するより高速になり，両者の差は回路規模が大きくなるにしたがって
急速に拡大することを示した．この結果から，本研究のように，直接法の適用限界を
数十万節点クラスに拡大し，各部分回路の大きさを直接法の通用限界まで大きくする
ことによって，冗長分割による計算量増大幅を無視できるレベルに抑えることができ，
直接法の良好な収束性と収束しやすさを保ったまま数百万節点クラスの大規模回路を
高速に解析できる見通しを得た．
さらに，大規模回路の有するマルチレート性を利用した高速化を達成するために，
103
最上位の回路分割で動作速度の異なる機能ブロックレベルの極めて大きな分割を適用
し，波形媛和法による解析を行うことを提案した．従来の波形緩和法では，部分回路
間で局所的帰還ループを構成する場合に収束性が劣化し，無駄な計算を行ってしまう
問題があった．本論文では，このような局所的帰還ループに対して，帰還ループに沿っ
た部分反復とウインドウ分割アルゴリズムを提案した．部分反復によって，収束性の
悪い局所帰還ループ部分のみを集中して緩和反復することによって全体の緩和反復を
減少させられることを確認した．部分反復に全体の解析時間ウインドウより小さな時
間ウインドウを通用することで，時間ウインドウ後半部分の収束性を向上させ，その
結果として解析時間が短縮されることを確認した．この波形緩和アルゴリズムにより，
解析時間の増大をともなうことなく，回路のマルチレート性を有効に利用できる見通
しを得た．
8．2 将来の展望
本論文では，数百万トランジスタクラスの大規模回路シミュレータを実現するため
の要素技術であるLU分解専用並列計算機，簡易素子モデルによる高速回路解析手法，
収束性に優れた反復タイミング解析アルゴリズム，ならびに，波形緩和法の収束性改
善アルゴリズムを提案し，その評価を行った．これらの要素技術を組み合わせること
により，現在広く用いられているSPICE等の回蕗シミュレータと同等の解析精度と収束
性ならびに多くの回路で収束するという特徴を保持したまま，従来の回路シミュレー
タの適用限界を超える大規模回路シミュレータを実現する見通しが得られた．しかし，
それぞれの要素技術において，今後検討を要する課題が残されており，また，これら
を組み合わせた回路シミュレーションシステムの検討も必要である．ここでは，それ
ぞれの要素技術に関する今後の検討課題と，本研究の目的とする大規模回路シミュレー
ションシステムの構築に必要なその他の技術をまとめて示し，本研究の将来展望とす
る．
まず，LU分解専用並列計算機SMASHに関する検討課題を述べる．SMASHは，プロ
セッサをクラスタ管理するとともに，列番号整合操作を行う専用回路SRUによりスパー
ス行列のLU分解を高速化する．SMASHを実現するうえで，問題となるのは，SRUなら
びにクラスタ内部のバス配線量であると考えられる．すなわち，SRUを構成するシフ
トレジスタ回路間を結ぶ配線の量と，SRU−PE間を結ぶ配線の量をいかに削減するかが
重要なポイントである．LU分解時における丸め誤差の累積を防ぐためには，数値デー
タを倍精度以上の多ビットで表現することが必要になるが，これにより，バス配線量
が増大して，ボード面積あるいはチップ面積のほとんどをバス配線が占める結果になっ
てしまう．この間題の解決に対しては，1クラスタを1チップに集積し，チップ内部
104
配線の高速性を利用して，バス配線を時分割多重で共用する方法が有効と考えられる．
SMASHを構成するプロセッサは，除算あるいは更新演算専用の簡易な構成でよいこと
と，SRUもレジスタとセレクタで構成する簡単な回路であることから，今日のLSIプロ
セスで実現可能な500万トランジスタクラスの回路によって，SMASHを構成するクラ
スタを1チップで実現できると考えられる．今後，SMASHの実現に向けて，具体的な
回路構成の検討が必要である．
次に，SMASHを含むシミュレーションシステムに関する検討課題を述べる．第4章
に述べたように，SMASHを用いることにより，比較的小規模な，モデル計算時間の占
める割合が大きい回路シミュレーションに関しては，その所要時間を，素子モデル計
算とほぼ同等となるまで削減できる．しかし，数十万節点クラスの大規模回路では，
逆に，LU分解の時間が支配的となることが予想でき，その場合には，SMASHの計算時
間によって回路シミュレーションの所要時間が決定されることになる．したがって，
たとえば，SMASHを複数台使用するなどの方法によって，LU分解の所要時間を削減す
るとともに，ホスト計算機とSMASH間のデータ転送方法を最適化し，SMASHのアイド
ルタイムを削減していくことが必要と考えられる．そのため，本論文では考慮しなかっ
たホスト計算機上でのLU分解コード生成時間などを正確に見積もり，ホスト計算機と
SMASHの処理時間を均衡させる適当なサイズに回路を節点分割するアルゴリズムの検
討が必要である．
区分線形ダイオードモデルを用いた動作点解析手法については，第5章に述べたよう
に，本モデルを適用することで，従来のスイッチレベルシミュレーションで問題となっ
ていた回路構造が変化する問題を回避でき，リミットサイクルへ縮退する問題も緩和
できる．しかし，リミットサイクルの問題については，本モデルを適用した場合にお
いても，完全に回避できておらず，特に大規模な回路に適用した際には，リミットサ
イクルの検出そのものが難しくなることから，リミットサイクルの発生メカニズムの
解明とその回避手段の研究が必要である．また，完全にリミットサイクルを回避する
ことができない場合は，解析の反復回数に制限を設け，制限値に達した場合に解析を
打ち切るなどのアルゴリズムを用いることが必要である．本研究では，区分線形モデ
ルを用いた解析により，ニュートン反復の初期値を得ることを考えているため，たと
え，区分線形解析が収束しなくてもシミュレーションを継続でき，反復回数に制限を
設ける方法も適用可能である．
OBRN法の検討課題としては，まず，回路分割の分割点決走法にある．OBRN法は，
部分回路の境界付近にある節点と素子を，隣接する部分回路に重複して含むように冗
長分割するため，従来法に比べると分割点の決走法が，実際の数値解析に与える影響
は小さくなることが予想できる．しかし，完全ではないまでも，ある程度適切な分割
105
点を適用するほうが，冗長度を小さくすることができ，さらに有効性を増すため，回
路構造を反映した分割手法を構築することが望ましい．また，冗長度の決定について
は，現状では，解析が収束しない場合に冗長度を大きくする発見的手法を用いている
が，この方法では，不要な場合でも大きな冗長度を適用してしまうため適切な冗長度
を決定できているとは言えない．また，収束しない計算を行うまで冗長度の妥当性が
わからない問題がある．したがって，今後，冗長度の決走法を研究する必要がある．
実際の数値解析に先立って冗長度を決定する必要があることから，回路構造を反映し
た冗長度の決走法や，実際の数値解析を行いながら，緩和反復の収束性が良くなった
場合に冗長度を下げるなどのアルゴリズムの検討が必要と考える．
最後に，部分反復とウインドウ分割を用いる波形緩和法についての検討課題を述べ
る・本手法は，回路内にある局所的帰還ループに沿って部分反復を行うとともに，ウ
インドウ分割を適用して波形緩和法の収束性を向上させるものである．検討を要する
課題としては，まず，部分反復を適用する局所帰還ループの検出アルゴリズムがある．
すなわち，収束性に大きな影響を与えない大域的帰還ループと，局所帰還ループを回
路構造から切り分けるか，あるいは，解析を実行しながら部分反復の適用先を決定す
るアルゴリズムの検討が必要である．
本論文で提案した大規模回路シミュレーションの要素技術についても細部について
今後検討を要する課題が残されているが，その他にも，本論文で述べなかった高速化
手法の導入が有効と思われる．そのうち，最も効果的と思われるものが潜在性の利用
による高速化である．潜在性は，時間領域の潜在性と，反復領域の潜在性に分けられ
る・このうち，時間領域の潜在性は，波形緩和法の適用によってある程度利用できる．
しかし，本研究のように，最上位のレベルの大きな回路分割に対応して波形緩和法を
通用する際には十分有効に利用できるとは言い難い．また，反復領域の潜在性につい
ては，現状では全く利用していない．そこで，今後は，時間領域・反復領域の潜在性
を，OBRN法による緩和反復と，各部分回路に適用するニュートン反復において利用で
きるよう，反復アんゴリズムを拡張していくことが必要と思われる．
以上述べた検討課題を解決することにより，将来の大規模な高速LSIならびに，これ
を搭載するボードレベルまでの詳細な回路シミュレーションを，現実的な時間で実行
できる大規模回路シミュレーションシステムの構築をめざす．
106
謝辞
本研究をご指導いただくとともに，終始適切なご助言を賜りました静岡大学工学部
浅井秀樹教授に深謝します．また，本論文を審査して頂くとともに，貴重なご助言
を賜りました静岡大学 窪野隆能教授，八巻直一教授，ならびに，渡辺健蔵教授に深
謝します・さらに，同分野の研究者として情報を御提供いただくとともに貴重な御討
論をして頂きました静岡大学 西垣正勝助手に感謝します．
本研究の創始期からご指導・ご支援を賜りましたNTTアドバンステクノロジ株式会
社ファイバオプティクス事業部 大崎孝明部長（前NTT光エレクトロニクス研究所
光応用装置研究部部長），mT生活環境研究所 昆太一担当部長，mネットワークサー
ビスシステム研究所 佐々木伸一主任研究員ならびにNTTエレクトロニクス株式会社
冨室久技術部長に感謝します．
日ごろご指導頂き，本論文執筆に際しご支援を頂きましたm通信エネルギー研究
所ネットワーク装置インテグレーション研究部 大平文和部長，光インタコネクショ
ン研究グループ 安東泰博グループリーダならびに，NTTアドバンステクノロジ株式
会社 石塚文則担当部長に感謝します．また，研究を直接ご指導頂き，有益な御討論
をしていただきましたm通信エネルギー研究所 新井芳光主幹研究員，ならびに，
mフォトニクス研究所 石原昇主幹研究員に感謝します．
本研究の遂行にあたり，浅井研究室において共同研究者として御尽力をいただきま
したシャープ株式会社 鈴木成次氏，セイコーエプソン株式会社 日吉泰徳氏ならび
に日本電気株式会社 遠藤一夫氏に感謝します．また，貴重な御討論をしていただき
ました松下電器株式会社 古門健氏ならびにヤマハ株式会社 川嶋隆宏氏をはじめ，
浅井研究室OBの皆様に御支援をいただきましたことを感謝します．
浅井研究室の皆様には，現在もASSISTの改良・保守・を継続して頂いておりますこと
に敬意を表するとともに，御礼申し上げます．
最後に，多忙な研究生活を支えてくれる妻をはじめ，支援してくれた家族に感謝す
る．
107
参考文献
［1］N．Ishihara，S．Fttjita，M．Togashi，S．Hino，Y．Arai，N．Tanaka，Y．Kobayashiand
Y．Akazawa：’13．5−Gb／sx4−ChSibipolarLSrsR）rOpticalInterconnectionsH，IEEETrans・Of
Solid−StateCircuits，Vol．30，12，PP．1493−1501（Dec．1995）．
［2］W．J．McCalla，‖Fundamentalsofcomputer−aidedcircuitsimulation”，KluwerAcademic
Publishers，1988．
［3］R．A．SalehandA．R．Newton，HMixed−mOdesimulation”，ⅢuwerAcademicPublishers，1990．
［4】R．Lipsett，C．SchaeftrandC．Ussery，HVHDL：Hardwaredescriptionanddesign’’，Ⅲuwer
AcademicPublishers，1989．
［5］C．M．Kurker，J．J．Paulos，B．S．CohenandE．S．Cooley，一’Developmentofananaloghardware
descrlPt10nlanguageH，Proc．19901EEECustomIntegratedCircuitsConftrence，1990・
【61大谷純一，今野大介，足立武彦，一一新世代回路シミュレーション技法の共同開発のための
一提案日，信学論，J74−A，8，PP．1197−1207，1991年8月．
［7］T．Murayama，一一Mixed−SignalsimulationofapulsewidthmodulationcircuitH，信学技報，
NLP，3・85，pp．9−16，1994年3月．
［8］H．HasegawaandS．Seki，．lAnalysisofinterconnectiondelayonveryhighspeedLSINLSI
ChipsuslnganMISmicrostriplinemodel’’，IEEETrans．ElectronDevices，ED・31，
PP．1954−1960，Dec．1984．
［9］R．SainatiandT．Moravee，l’Estimatinghighspeedcircuitinterconnectperformance’一，正EE
TranS．CircuitsandSystems，36，4，PP．533−541，Apri11984．
［10］N．Tanaka，Y．Arai，Y．0lmoandH．Takahara：‖AlNceramicpackageforahigh−SPeedparallel
OPticallinkmodulel’，Technicaldigestofthe3rdVLSIpackagingworkshopofJq）an，
PP．123−124（Dec．1996）
lll］N．Tanaka，Y．Arai，H．Takahara，Y．Ando，N．IshiharaandS．Hino：’■3．5Gb／sx4choptical
interconnectionmodulefbrATMswitchingsystem’．，Proc．IEEE1997ECTC，PP・210−
216（May1997）
［12］R．D．Berry，一■Anoptimalorderingofelectroniccircuitequationsforasparsematrixsolution
’．，正EETranS．CircuitsTheory，CT・18，1，PP．40−50，Jan・1971・
［13］Ⅰ・S・Duff，”AsurveyOfsparSematrixresearch一一，ProceedingsoftheIEEE，VOl・65，4，
PP．500−535，April1971．
108
［14】N．B．RabbatandH．Y．Hsieh，一一AlatentmacromodularaPPrOaChtolarge−SCalesparSe
networks日，IEEETrans・Circuits＆Systems，CAS・23，12，PP・745−752，Dec・1976・
［15］RabbatN．B．，Sangiovanni−VincentelliA・L・andHsiehH・Y・，”Amultilevelnewton
algorithmwithmacromodelingandlatencyfbrtheanalysisoflarge−SCalenonlinearCircuits
inthetimedomain一．，IEEETrans．Circuits＆Syst・，CAS・26，9，PP・733−741，Sep・1979・
［16］Ⅰ．N．H頑，1．SparSityconsiderationinnetworksolutionbytearing’’，正EETrans・Circuits＆
Systems，CAS・27，5，PP・357−366，May1980・
［17］P．Yang，I．N．H年ijandT．N．Trick，HSlate：aCircuitsimulationprogramwithlatency
exploitationandnodetearlng”，Proc・ICCC−80，Pp・353−355，Oct・1980・
［18］M．Vlach，‖LUdecompositionandforward−backwardsubsutitionofrecursivebordered
blockdiagonalmatrixt一，Proc・1983ⅢEEIntemationalSymposiumonCircuitsAnd
Systems，PP・427−430，May1983・
［19］M．Vlach，MLUdecompositionandfbrward−backwardsubstitutionofrecursivebordered
blockdiagonalmatricesH，IEEProc・，132，Pt・G，1，PP・24−31，Feb・1985・
［20］S．Moriyama，HLargeSCalecircuitsimulationbasedonthedirectmethod■一，Trans・正ICE，
E72，12，PP・1326−1335，Dec・1989・
［21］鹿毛，新妻，寺前，下郡，泉田，憧列回路シミュレータPARACSの開発●一，第5回回路とシ
ステム軽井沢ワークショップ論文集，pp．213−218，1992年4月・
［22］A．R．Newton，HTeclmiquesforthesimulationoflarge−SCaleintegratedcircuits．1，正EE
TranS・Circuits＆Syst・，CAS・26，9，PP・741−749，Sep・1979・
［23］E．LelaraSmee，A．E．RuehliandA．LSangiovanni−Vincentelli，”Thewavefbmrelaxation
methodfbrtime−domainanalysisoflargescaleintegratedcircuits一一，IEEETrans・Computer−
AidedDesign，CAD・1，PP・131−145，July1982・
［241浦浜喜一，‖波形緩和法の局所収束性・・，信学論（A），J69・A，10，pP・1219−1225，1986年
10月．
［25］J．K．WhiteandA．Sangiovanni−Vincentelli，”Relaxationtechniquesfbrthesimulationof
VLSIcircuits一一，ⅢuwerAcademicPublishers，1987・
［26］R．A．SalehandR．A．Newton，一一Theexploitationoflatencyandmultiratebehaviorusing
nonlinearrelaxationforcircuitsimulationH，IEEETrans・Computer−AidedDesign，CAD・8，
12，PP・1286−1298，Dec・1989・
109
［27］LNagel，’tSPICE2，AcomputerprogramtOSimulatesemiconductorforcircuits’’，ERL
MemoERL−M520，UniversltyOfCalifbmia，Berkeley，May．1975．
［28］C．W．Ho，A．E．RuehliandP．A．Brennan：●lThemodinednodalapproachtonetwork
analysis’’，IEEETrans・Circuits＆Syst．，CAS・22，6，PP・504−509（June1975）・
［291浅井秀樹，田中衛，森真作，＝階層分割法による回路網解析−■，信学論，J‘＄・D，2，pp．83−
90，1985年2月．
［30］K．Endoh，N．TanakaandH．Asai：”AvailabilityofWaveformRelaxationMethodwithLocal
IterationandWindowPartitionTechniques”，TranS．OfIEICE，E74，5，PP．1003−1005（May
1991）．
［31］KoichHayashi，MitsuruKomatsu，MasakatsuNishigakiandHidekiAsai，HWaveform
relaxationmethodwiththedynamicpartitionlngteClmiqueforbipolartranSistorcircuitsH，
Proc．35thMidwestSymposiumonCircuitsAndSystems，PP・400−403，Aug．1992．
［32］MasakiIshida，KoichHayashi，MasakatsuNishigakiandHidekiAsai，‖Relaxation−based
algorithmsforbipolarcircuitanalysis■■，Proc・1993JointTeclmicalConftrenceon
Circuits／Systems，ComputersandCommunications，PP．566−569，July1993・
［33］MasakiIshida，KoichHayashi，MasakatsuNishigakiandHidekiAsai，一’Relaxation−based
algorithmswithdynamicpartitionlngteChniqueforbipolarCircuitanalysis．一，Proc・1993Int・
SymposiumonNonlinearTheoryanditsApplications，PP・659−662，Dec・1993・
［34］B．Chen，M．Onodaand M．Kaneko，”MMAPC：anefftctivemixed−mOdecircuitsimulator
uslngdynamiccircultPartitionprocessH，TranS・IEICE，E71，4，PP・388−393，Apri11988・
［35］K．Hayashi，M・Komatsu，M・Nishigakiand H・Asai，”Bipolartransistorcircuitanalysisby
WaVebrmrelaxationmethodwithconsiderationoftheoperationpolnt一一，IEICETrans・
Fundamentals，E75−A，7，PP．914−916，July1992・
［36］MasakiIshida，KoichHayashi，MasakatsuNishigakiandHidekiAsai，’lIteratedtiming
analysISWithdynamicpartitionlngteChniquefbrbipolartranSistorcircuitsH，Proc・1994
正EEIntemationalSymposiumonCircuitsAndSystems，PP．41ト414，May1994．
［37］MasakiIshida，KoichHayashi，MasakatsuNishigakiandHidekiAsai，一一Relaxation−based
algorithmsfbrbipolarcircuitanalysis一▼，IEICETrans・FundamentalS，E77・A，6，PP・1023−
1027，June1994．
［38］M．Nishigaki，N・TanakaandH．Asai，’一Hierarchicaldecompositionfbrcircuitsimulationby
directmethod一一，TranC．IEICE，E73，12，PP．1948−1956，Dec．1990．
110
［39］MasakatsuNishigaki，NobuyukiTanakaandHidekiAsai，．一HIDE：HierarChical
decompositionsystemforpreprocesslngOfcircuitsimulationbydirectmethodH，Proc・1990
JointTechnicalConftrenceonCircuits／Systems，ComputersandCommunications，PP・518−
523，Dec．1990．
［40】M・Nishigaki，N・TanakaandH・Asai，”Hierarchicaldecompositionsystemanditsavailability
fornetworksolutionH，Proc・1991IEEEIntemationalSymposiumonCircuitsAndSystems，
PP・884−887，June1991．
【41］西垣正勝，田中伸幸，浅井秀樹，一一MOS回路網に対する階層節点分割の有効性一一，信学論，
J74・A，8，PP．1176−1179，1991年8月．
［42］M・Nishigaki，N・TanakaandH・Asai，‖Hierarchicaldecompositionandlatencyforcircuit
SimulationbydirectmethodH，IEICETranS・Fundamentals，E75・A，3，PP・347−351，March
1992．
［43］MasakatsuNishigaki，NobuyukiTanakaandHidekiAsai，HMixedmodecircuitsimulator
SPLIT2uslngdynamicnetworkseparationandlatencyll，Proc・35thMidwestSymposium
OnCircuitsAndSystems，PP・1369−1372，Aug・1992・
［44］M・Nishigaki，N・TanakaandH・Asai，’．Mixedmodecircuitsimulationusingdynamic
Partitionlng．一，IEICETranS・Fundamentals，E76・A，3，PP・292−298，MarCh1993・
［45］西垣正勝，浅井秀樹，‖回路の動的分離に基づく大規模回路解析用混合モードシミュレー
ションとシミュレータの構築日，静岡大学大学院電子科学研究科研究報告第15号，
pp．7ト76，1994年3月．
【46】入井 久，林宏一，河野健人，西垣正勝，浅井秀樹，−■SPL汀2．2：混合モード回路シミュレー
タ’−，信学技報，NLP，3−8‘，pp．9−16，1994年3月．
［47］MasakatsuNishigaki，NobuyukiTanakaandHidekiAsai，HMixedmodecircuitsimulation
uslngdynamicnetworkseparationandselectivetrace一一，IEICETrans．Fundamentals，
E77・A，3，PP．454−460，MarCh1994．
［48］MasakatsuNishigaki，NobuyukiTanakaandHidekiAsai，’’Mixedmodecircuitsimulator
SPLIT2・luslngdynamicnetworkseparationandselectivetraceH，Proc．1994IEEE
htemationalSymposiumonCircuitsAndSystems，PP・9−12，May1994・
［49］N・TanakaandH・Asai，‖SpecialparallelmachinefbrLUdecompositionofalargescale
CircuitmatrixanditsperformanCel一，TranS・IEICE，E72，12，PP・1336−1343，Dec・1989・
［50］N・TanakaandH・Asai：HLargeScaleCircuitSimulationSystemwithDedicatedParallel
ProcessorSMASH”，TranS．OfIEICE，E73，12，PP．1957−1963（Dec．1990）．
111
［51］N．TanakaandH．Asai：HArchitecturefbrSimulationSystemwithConsiderationofCircuit
PartitionTl，Proc．正EE1991Intl．Symp．OnCircuits＆Syst・（Singapore），PP・2689−
2692（June1991）．
【521田中伸幸，日吉泰徳，鈴木成次，浅井秀樹：−▼スイッチを含む区分線形ダイオードモ
デルを用いたバイポーラ回路網の動作状態解析とその評価日，電子情報通信学会論文
誌，J74，A，8，PP．1160−1166（Aug・1991）・
［53］N．Tanaka，Y．Arai，S．YamaguChiandH．Tomimuro：．’AvailabilityoftheOverlappedBlock
RelaxationNewtonMethodfbrNonlinearLargeScaleCircuitSimulation．一，TranS・Of
IEICE，E78・A，2，PP．152−159（Feb・1995）
［54］宇都宮他：一一電子回路のCAD．一，電子情報通信学会，（1968）・
【55］広中他：‖現代数理科学辞典−t，丸善株式会社，（1991）・
【56】牧之内，鳥居：‖数値解析−t，オーム社，（1975）・
【571戸川隼人：一一マトリクスの数値計算”，オーム社，（1971）
【581村田，小国，唐木田：・・スーパーコンピュータ科学技術計算への通用一一，丸善株式会社，
（1991）．
［59］田中伸幸，浅井秀樹，個路シミュレータ開発用支援ツールASSIST”，信学技報，
NLP，0・鴫pp．9−16，1991年3月．
［60】H．Asai，H．UsamiandY・Matsunomoto，1−HierarChicallanguagefbrstruCturaldescription
withfacilityofleveltransfomationanditsapplicationtoLSIsimulatorsH，Proc・ICCAS．89，
PP・345−348，July1989・
［61］都築正明，西垣正勝，浅井秀樹，咽路シミュレータ開発用支援ツールーASSISTの改良−．一，
信学技報，NLP91・，3，pp．1−7，1992年3月・
［62］HiroshiSagesaka，HisashiIriiandHidekiAsai‥一一SPADE：Analog／DigitalMixedSignal
simulatorwithAnalogHardwareDescnptlOnLanguage・・，Proc・OfIEEEICECS．98，pP・517−
520（Sep．1998）・
［63］HSchematicdesignTooIsOrCAD／SDTIIIH，OrCADSystemsCorporation・
［64］C．A．Mead，L・A・Conway：MIntroductiontoVLSIsystems．一，Addison−Wesley（1980）・
［651浅井秀樹，浅井光男，田中衛‥‖大規模スパース行列のLU分解専用並列計算機日，信学
論（D），J69・D，7，PP．1044−1052（昭61−07）・
112
【66】田辺昇，土肥康孝：‖連想スイッチによる疎行列用計算機の構成日，信学論（D），J70・
D，12，pp．2393−2401（昭62−12）・
［67］田辺，石坂，村越，泉谷，土肥：＝並列パイプライン式疎行列専用計算機RAMPの
構成●一，信学論（D），J71・D，10，PP．1939−1948，（1988−10）
［68］H．AsaiandA．Kumita，HAvailal）ilityofgatelevelnodetearinginbipolarcircuitsimulation
by directmethodM，Trans・IEICE，E71，10，PP・962−964，Oct・1988・
［69］R．M．Kickhaftr，C．Pottle：HAclusteredprocessorarrayforthesolutionofunstruCturedsparSe
matrixequationsH，Proc．ISCAS−83，PP・214−217，（1983）・
【701中田，堀口，高木，川添，重井：‖クラスタ方式マルチプロセッサシステム一一，信学論（D），
J70・D，8，PP．1469−1477，（Aug・1987）・
［71］清水尚彦，田中衛，”ビットシリアル系LU分解プロセッサ日，信学論（D），J66・D，12，
pp．1416−1423，1983年12月．
【72】園原，田中，浅井：−ヤコピアン計算専用並列計算機一一，1990倍学春季仝大，A−9
［73］J．Katzenelson：HAnalgorithmfbrsoIvingnonlinearreSistornetworksl’，BellSyst・Tech・
J．，PP．1605−1620（Oct・1965）・
［74］L．0．ChuaandR．L．P．Ying：”CanOnicalpiecewise−linearanalysis■’，IEEETrans・Circuits＆
Syst．，CAS・30，3，（MarCh1983）・
［75］I．N．H年ijandD．Saal）：”Switch−LevellogicsimulationofdigitalbipolarCircuitsH，IEEE
TranS．Computer−AidedDesign，CAD・6，2，PP・251−258（MarCh1987）・
【76】水谷光，田中衛：一・修正節点方程式によるトランジスタ回路網の動作状態解析−，信学
論（A），J70・A，5，PP．775−784（昭62−05）．
［77】水谷光，田中衛：‖トランジスタ回路網の動作状態探索過程における非正則回路方程
式の解法日，信学論（A），J72・A，8，PP．1268−1276（平1−08）．
【78］水谷光‥・・非正則問題を避けるために仮想状態方程式を使ったスイッチト回路網の
解析法・一，信学論（A），J73・A，10，PP．1632−1640（平2−10）．
［79］MOKARI−BOLHASSANM．E．，TRICKT．N．：一一ANEWITERATIVEALGORITHMFOR
THESOLUTIONOFLARGESCALESYSTEMS一・，Proc．ofthe28thMidwestSymposium
OnCircuitandSystems，PP・75−77（Aug・1985）・
113
［80］MOKARI−BOLHASSANM．E．，SmartD．andTRICKT・N・：”ANewRobustRelaxation
TechniquefbrVLSICircuitSimulationH，IEEEInt・Conf・OnCAD，ICCAD−85，PP・26−
28（Nov．1985）．
［81】ShimaT．：一一Acircuitsimulationbasedonthewavefbrmrelaxationmethodusingselective
overlappedpartitionandclassinedlatenciesH，IEEESymp・OnCAS，ISCAS．88，PP・1651−
1654．
［82］浦浜喜一：”波形緩和法の一加速法”，信学論（A）J68・A，10，PP・1121−1122（昭60−10）・
［83］H．AsaiandS．Isobe：”WavefbrmRelaxationAlgorithmbasedonVirtualState
FormulationandItsNumericalStability一．，33rdMidwestSymp・OnCircuitsandSyst・
（Aug．1990）．
［84】Y．H．Jun，C．W．Lee，K．J．LeeandS．B．Park：’’TimingSimulatorbyWaveform
RelaxationConsideringtheFeedbackEfftct1．，IEEEProc・，136・Pt・G，1，pP・38−
42（Feb．1989）．
114

 Download  Report
Document 7470988

Document 7470988

119. Node.jsによるWebサーバサイド開発実践

119. Node.jsによるWebサーバサイド開発実践

ロビーサーバーとネットワークに使われるデータ構造の

ロビーサーバーとネットワークに使われるデータ構造の

Nginx で日本語入力を遊んでみよう！

Nginx で日本語入力を遊んでみよう！

データストア基盤 GridStore

データストア基盤 GridStore

複合施設node uehara（ノード ウエハラ） オープン

複合施設node uehara（ノード ウエハラ） オープン

Document

Document

プログラミング演習I

プログラミング演習I

Click - NICT

Click - NICT

expydoc.com

Your ExpyDoc

© Copyright 2024 ExpyDoc