JPH0752748B2 - 三次元デバイスのシミュレーション装置 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明は、例えば半導体素子の特性解析を、実際の素
子を製作することなく、コンピュータ上で行なう三次元
デバイスのシミュレーション装置に関する。

［従来の技術］ 半導体素子の特性解析を、実際の素子を用いないでコン
ピュータ上で行なうデバイスシミュレーションにおいて
は、大規模疎行列計算を高速で実行する必要がある。

現象を定量的に解明しようとする数値シミュレーション
技術は、コンピュータの進歩によってその重要性が増し
ている。半導体集積回路の設計に際しても、プロセスシ
ミュレーション、デバイスシミュレーション、回路シミ
ュレーション等の技術が既に実用化されており、設計期
間を短縮するために、シミュレーションの短縮化がさら
に強く望まれている。

デバイスシミュレーションは、最終的に大規模行列方程
式の求解問題に帰着されるもので、各シミュレーション
時間の大半が、この求解部分に費やされる。このこと
は、素子構造が複雑化し、三次元シミュレーションが不
可欠なものとなるにつれて、より強まる傾向にあり、求
解部分の高速化が求められている。

［発明が解決しようとする課題］ この発明においては、シストリックアレーを用いて高速
化が実現できる三次元デバイスのシミュレーション装置
を提供することを目的としている。シストリックアレー
は、H.T.Kungによって提案されたVLSI向きのアーキテク
チャの１つで論理的且つ実践的側面からの研究もされて
きた。しかし、これまで提案された密行列に対する処理
をシストリックアレー上で、デバイスシミュレーション
のような大規模疎行列計算を行なう場合、数百万個の演
算セルを必要とする。

したがってこの発明においては、小数個の演算セルによ
って大規模行列を効果的に扱うことのできるシストリッ
クアレーを提供しようとするものである。

［課題を解決するための手段］ この発明に係る三次元デバイスのシミュレーション装置
は、基本セル、下三角要素出力セル、対角要素出力セ
ル、上三角要素出力セル、および時間調整セルからなる
５種類の演算セルを六角形に配置して構成され、その行
列の各要素はそれぞれ上方から入力され、分解された行
列の各要素はそれぞれ下方から出力されるように構成さ
れている、疎帯行列の不完全LU分解用のシストリックア
レーと、複数の積和演算セルが一次元的に並べて配置さ
れ、この複数の演算セルの一次元配列の一方の端からベ
クトルの要素が特定される時間間隔で入力され、前記各
演算セルにはそれぞれ各行列の各要素が特定される時間
間隔で入力されて、その各行列要素と各ベクトル要素と
の積を順次累積して出力ベクトルの要素として出力する
ようにした疎帯行列ベクトル積用シストリックアレー
と、複数の積和演算セルが一次元的に並べて配置され、
この複数の演算セルの一次元配列の一方の端からベクト
ルの要素が特定される時間間隔で入力され、前記各演算
セルにはそれぞれ各行列の各要素が特定される時間間隔
で入力されて、その各行列要素と各ベクトル要素との積
を順次減算して出力ベクトルの要素として出力するよう
にした前進後退代入用シストリックアレーとを備えるも
ので、前記疎帯行列の不完全LU分解用シスリックアレ
ー、疎帯ベクトル積用シストリックアレー、および前進
後退代入用シストリックアレーは、それぞれデータバス
およびコントールバスによって結合され、主計算部から
の指令に基づき演算動作を実行させられるようにしてい
る。

［作用］ このシミュレーション装置によれば、デバイスシミュレ
ーション問題の特徴から問題を分割できるもので、それ
らを並列的に解くことができる。特に疎行列ベクトル
積、前進・後退代入、ベクトルの和、内積は、ループ内
にあって繰り返し計算されるものであるため、この部分
の高速化の可否によって計算時間に大きな差が生ずる。
このシミュレーション装置においては、デバイスシミュ
レーションの高速化のために少数個のセルにより大規模
問題を効率的に扱うことができるシストリックアレーを
提供できる。

［発明の実施例］ 以下、図面を参照しながら、この発明の一実施例を説明
する。第１図はデバイスシミュレーション装置の構成を
示しているもので、疎帯行列の不完全行列分解（Imd＝I
ncomplete Matrix Decomposition）モジュール11、行列
ベクトル積（Mvm＝Matrix−Vector Multiplication）モ
ジュール12、および前進・後退（Fbs＝Foward−Backwar
d Substitution）モジュール13を備え、これらモジュー
ル11〜13はグローバルデータバス14を介して、ホストコ
ンピュータ15に接続されるようにする。ここで、Imdモ
ジュール11、Mvmモジュール12、およびFbsモジュール13
には、それぞれImdコントローラ16、Mvmコントローラ1
7、およびFbsコントローラ18が設けられ、これらコント
ローラ16〜18はグローバルコントロールバス19を介し
て、ホストコンピュータ15によって制御されるようにな
っている。

ここで、半導体デバイスシミュレーションについて考え
てみると、このシミュレーションは半導体素子の不純物
分布、接合面の軽上等の情報を基にして素子の電気的な
特性を求めるものであり、素子の内部電位Φ、電子密度
ｎ、正孔密度ｐは、ボアソン方程式、電子および正孔に
対する電流連続式等によって適宜表現できる。

デバイスシミュレーションにおいては、これらの３つの
式を線形化、離散化した後、適当な境界条件を与えて数
値的に解く。ここで、離散化の手法としては、有限差分
法、有限要素法等があるが、シストリックアルゴリズム
との整合性を考慮して有限差分法を採用すると効果的で
ある。

三次元シミュレーションにおいては、第２図で示す注目
点Ｄと、その前後、左右、上下の格子点（A,G,C,E,B,
F）の合計７点に関して前記３つの式を離散化する（７
点差分近似）。

格子座標（k,m,n）の格子点に対しては、次の式にした
がって通し番号を付ける。

ｉ＝ｋ＋ｘ（ｍ−１）＋xy（ｎ−１） ……（１） （１≦ｋ≦ｘ、１≦ｍ≦ｙ、１≦ｎ≦ｚ） 但し、ｘ、ｙ、ｚはそれぞれ離散化格子におけるＸ軸、
Ｙ軸、Ｚ軸の格子点数である。

このとき、ｉ番目の点における電位等の物理量Ψ_ｉは次
の式で表現される。

a_iΨ_i-xy＋b_iΨ_i-x＋c_iΨ_i-1 ＋d_iΨ_ｉ＋e_iΨ_i+1＋f_iΨ_i+x ＋g_iΨ_i+xy＝h_i ……（２） ここで、a_i〜g_iは係数であり、h_iは定数項である。

これを行列方程式（ＡΨ＝ｈ）で表現すると、第３図で
示すようになり、係数行列Ａ（次元数Ｎ＝xyz）は規則
的且つ大規模で疎な帯行列となる。例えば、各軸を40個
の格子点に分割したとき、６万４千次元の連立一次方程
式である。

素子の微細化が進み、素子構造が複雑化するにつれて、
三次元ではシミュレーションにおける係数行列の次元数
も数十万次元から数百万次元になるものであり、この求
解部分の高速化が不可欠となる。

その解法は主に共役勾配法（CG法）系統の反復法が用い
られているもので、基本となる演算は、疎帯行列の不完
全分解、疎帯行列ベクトル積、前進・後退代入、ベクト
ルの内積、そしてベクトルの和である。第４図はこの解
法の全体像を示すフローチャートである。

疎帯行列用のシストリックアレーについて、まず疎帯行
列の不完全分解について説明すると以下のようになる。

デバイスシミュレーションで得られる係数行列Ａが、対
称行列となる場合と、非対称行列となる場合がある。こ
のいずれの場合においても不完全分解を行えるシストリ
ックアレーが必要となる。いま、係数行列Ａを次のよう
に不完全分解すると次のようになる。

Ａ＝LDU＋Ｒ ここで、Ｌは下三角行列、Ｄは対角行列、Ｕは上三角行
列であり、Ｒは不完全分解によって生ずる誤差行列であ
る。

この式のＡ、Ｌ、Ｄ、Ｕの非零要素の行番号ｉ、列番号
ｊの組（i,j）は、それぞれ集合Ｓ、S^L、S^D、S^Uに含ま
れる（１≦ｉ、ｊ≦Ｎ）。

Ｓ＝｛（i,j）|j＝ｉ−xy,i-x, ｉ−1,i,i＋1,i＋x,i＋xy｝ S^L＝｛（i,j）|j＝ｉ−xy,i−xy＋1,i−xy＋x,i−x, ｉ−ｘ＋1,i−1,i｝ S^D＝｛（i,j）|j＝ｉ｝ S^U＝｛（i,j）|j＝i,i＋1, ｉ＋ｘ−1,i＋1,i＋xy −x,i＋xy−1,i＋xy｝ 以下の説明では、行列ＡのＳで指定される非零要素を含
む斜めの列を７本のＮ次元ベクトルとして、それぞれ
（a,b,c,d,e.f.g）と表し、行列Ａの行番号をそれぞれ
の添字とする。また、Ｌ、Ｄ、Ｕについても非零要素を
含む斜めの列をベクトルとして、それぞれ（a^L,a^L′,
a^L″,b^L,b^L′,c^L,d^L）,d^D,（d^U,e^U,f^U,f^U,g^U″,g^U′,
g^U）と名前を付け、同じく行番号を添字とする。

以下に、不完全LU分解（d^D _i＝d^U _i＝１）を計算式を示す
（１≦ｉ≦Ｎ）。

a^L _i＝a_i a^L′_ｉ＝−a^L _ie^U _i-xy a^L″_ｉ＝−a^L _if^U _i-xy−a^L′f^U′_i-xy+1 b^L _i＝b_i−a^L _ig^U″_i-xy b^L′_ｉ＝−a^L′_ig^U″_i-xy+1 −b^Lie^U _i-x c^L _i＝c_i−a^L _ig^U′_i-xy −b^L _if^U′_i-x d^L _i＝d_i−a^L′_ig^u _i-xy −a^L′_ig^U′_i-xy+1 −a^L″g^U″_i-xy+x−b^L _if^U _i-x −b^L'_if^U′_i-x+1−C^L _ie^U _i-1 e^U _i＝（e_i−a^L′_ig^U _i-xy+1 −b^L′_if^U _i-xy+1）/d^L _i f^U′_ｉ＝（−a^L″_ig^U′_i-xy+x −c^L _if^U _i-1）/d^L _i f^U _i＝（f_i−a^L″_ig^U _i-xy+x）／ d^L _i g^U″_ｉ＝（−b^L _ig^U _i-x −b^L′_ig^U′_i-x+1）/d^L _i g^U′_ｉ＝−c^L _ig^U _i-1/d^L _i g^U _i＝g_i/d^L _i （３） この式（３）のデータの依存関係をまとめ、各データ間
における参照関係の規則性に着目すると、疎行列の不完
全分解を実行するシストリックアレーが得られるもの
で、第５図で示すようになる。この図において、矢印に
丸を付した印は、隣接セル間で遅延を必要とする部分を
表し、その遅延時間はそれぞれδ１、δ２、δ３であ
る。

このシストリックアレーは、第６図の（ａ）で示す基本
セル、同図の（ｂ）で示す下三角要素出力セル、同図の
（ｃ）で示す対角要素出力セル、同図の（ｄ）で示す上
三角要素出力セル、同図の（ｅ）で示す時間調整セルを
六角形に配置して構成したものである。そして、第５図
で示されるようにＡの各要素がアレーの上方から入力さ
れ、Ｌ、Ｄ、Ｕの各要素は下方から出力される。

ここで、各入力データのタイミングは次の通りである。
行列Ａの７本のベクトルの各第１要素、a1、b1、c1、d
1、e1、f1、g1は、それぞれ時刻Ｔ＝1,5,7,8,10,14,22
の各アレーに入力し、それ以降の入力の時間間隔は、３
である。

このとき出力d^L _Nは、時刻 Ｔ＝８＋３（Ｎ−１）＋７＋１ に出力される。

アレーを構成する５種類のセルの中で、（ｅ）図で示さ
れる時間調整セルは、実際の演算を行わず、データを遅
延させるためのセルであるが、アレー内のデータ流を規
則的にして、式（３）を正しく計算させるために必要で
ある。また、このシストリックアレーでは、セル機能を
若干変更することによって、次の３種類の分解が可能で
ある。

I.不完全LU分解（d^D _i＝d^U _i＝１） II.不完全LDL^T分解（d^D _id^U _i＝1,d^L _i＝d^U _i） III.不完全LDL^T分解（d^L _i＝d^U _i＝１） 不完全LDL^T分解（II,III）の計算式は、式（３）の一部
を次のように変更すればよい。

II.式（３）の右辺のa^L _i〜c^L _iを、下記の゜a^L _i〜゜c^L _i
に、さらにd^L _iによる除算を無くした式。

III.式（３）の両辺のa^L _i〜c^L _iを下記の゜a^L _i〜゜c
^L _iに、さらにd^L _iをd^D _iに置き換えた式。

但し、 ゜a^L _i＝a^L _id^D _i-xy ゜a^L′_ｉ＝a^L′_id^D _i-xy+1 ゜a^L″_ｉ＝a^L″_id^D _i-xy+x ゜b^L _i＝b^L _id^D _i-x ゜b^L′_ｉ＝b^L′_id^D _i-x+1 ゜c^L _i＝c^L _id^D _i-1 ところで、この不完全分解は後述する前進・後退代入に
おいての使用が本来の目的であり、その計算は反復法に
おけるループ内で行われる。このため、このシストリッ
アレーでは下三角要素出力セル、および対角要素出力セ
ルの機能を工夫して前進・後退代入で、そのまま使用で
きるデータ（例えばd^L-1 _iや゜a^L _i〜゜c^L _i等）にして出
力する。

第７図はこのように不完全行列分解を行うImdモジュー
ル11の具体的な構成例を示している。すなわち、、被分
解行列（Ａ）バッファメモリ111から不完全行列分解ア
レー112に入力が与えられ、この分解アレー112からの出
力は分解行列（Ｌ、Ｄ、Ｕ）用バッファメモリ113に与
えられるようになる。

次ぎに、疎帯行列ベクトル積について考える。疎帯行列
ベクトル積（ｑ＝Ap）の各成分q_iは、次ぎの式で表現さ
れる。

q_i＝Σ^N _{j ＝ 1}A_ijP_ij,（i,j）∈Ｓ ……（４） アレーは第８図で示す積和演算セル７個からなる一次元
アレーとし、これを第９図で示すように構成する。そし
て、ベクトルｑの各要素q_iは、初期値を０として左端の
セルから、ベクトルｐの各要素p_iは右端のセルから、そ
れぞれ時間間隔２で入力し、計算結果q_iは式（４）の処
理を受けながら、アレー内を右方向に進む。ここで、δ
_１〜δ₁₂は、各セル間に設定すべき遅延時間であり、式
（４）とアレー内のデータ移動の時間関係とによって、
次ぎの条件式で表される。

Σ⁶ _{i ＝ １}δ_ｉ＝Σ_{ｉ ＝ ７}δ_ｉ＝2xy−6, Σ⁵ _{i ＝ １}δ_ｉ＝2x−４＋δ₇, Σ¹⁰ _{i ＝ ７}δ_ｉ＝δ_１＋δ₂, Σ⁶ _{i ＝ １}δ_ｉ＝δ_７δ₈, Σ¹¹ _{i ＝ ７}δ_ｉ＝2x−４＋δ₁, Σ³ _{i ＝ １}δ_ｉ＝Σ⁹ _{1 ＝ ７}δ_i, （５） この式（５）とδ_ｉ≧０とによって、次ぎの結果が導か
れる。

δ_１＋δ₁₂＝δ_６＋δ_７＝2xy−2x−2, δ_２＋δ₁₁＝δ_５＋δ_８＝2x−4, δ_３＝δ_４＝δ_９＝δ₁₀＝0, δ_１＋δ_２＋δ_５＋δ_６＝2xy−６ ……（６） また、a₁〜g₁がq₁に対して使われる時刻をTa₁〜Tg₁とす
ると、 Ta₁＝1,Tb₁＝２＋δ₁, Tc₁＝３＋δ_１＋δ₂, Te₁＝５＋Σ⁴ _{i ＝ １}δ_ｉ Tf₁＝６＋Σ⁵ _{i ＝ １}δ_ｉ Tg₁＝１＋2xy ……（７） となり、各入力データのタイミングが遅延時間との関数
として表される。しかし、p₁,q₁が時刻Ｔ＝１にそれぞ
れ右端、左端のセルに入力されたとき、p_N、q_Nが出力さ
れる時刻は、 Ｔ＝１＋2xy＋２（Ｎ−１）＋１ となり、遅延時間の選択の仕方が、全計算期間に影響を
及ぼさないことがわかる。したがって、遅延時間、入力
データのタイミングは一意には決まらず、それぞれ式
（６）（７）を満足する範囲内で任意に選択できるよう
になる。このことは、この疎帯行列・ベクトル積の場合
には、直接的な効果ではないが、次ぎの前進・後退代入
において、重要な役割を果たすようになる。

前進・後退代入について説明する。この部分は、ループ
内で最も計算時間を必要とするもので、（LU）^-1r＝ｔ
の計算は、２段階に分けて実行される。

前進代入L^-1r＝ｓでは、ｒを入力してｓを求める。さら
に後退代入U^-1s＝ｔでは、ｓを入力してｔを求める。

まず、前進代入においては、ｓの各成分s_iは次式で計算
される。

s_i＝（r_i−a^L _is_i-xy −a^L′_is_i-xy+1−a^L″_is_i-xy+x−b^L _is_i-x−b^L′_is_i-x+1 −c^L _is_i-1）/d^Li （８） この式（８）には、d^L _iによる除算が含まれているが、
不完全分解の段階で既に逆数を計算しているので、実際
には乗算を行う。また、不完全LDL^T分解ではa^L _i〜c^L _iで
はなく、゜a^L _i〜゜c^L _iとd^L-1 _i、あるいはd^D-1 _iが必要で
あるが、やはり不完全分解の段階でデータを加工してお
いて乗算のみ行うようにする。

前進・後退代入アレーは疎帯行列ベクトル積アレーと同
じ一次元アレーでセル数は同じで構成できる。このアレ
ーは右端以外のセルの機能は、第８図で示した積和演算
セルにおいて、 α_out＝α_in＋β_inγ_in の加算を減算に置き換えたものである。また、右端のセ
ルは前進・後退代入の結果を出力するセルであり、その
機能は、 α_out＝α_inγ_in β_out＝α_out とする。ここで、入力データの時間間隔は２とし、疎帯
行列・ベクトル積のときと同様にして、δ_１〜δ₁₂の条
件式から、各セル間の遅延時間として次ぎの結果が得ら
れる。

δ_１＝δ₁₂＝δ_４＝δ_９＝δ_６＝δ_７＝０ δ_２＋δ₁₁＝2x−4,δ_５＋δ_８＝2x−６ δ_３＋δ₁₀＝2xy−4x−２ ……（８） 入力データのタイミングは、 Ta^L ₁＝1,Ta^L′_１＝２＋δ₁, Ta^L″_１＝３＋δ_１＋δ₂, Tb^L ₁＝４＋Σ³ _{i ＝ １}δ_i, Tb^L′_１＝５＋Σ⁴ _{i ＝ １}δ_i, Tc^L ₁＝６＋Σ⁵ _{i ＝ １}δ_i, TdL^L-1＝７＋Σ⁶ _{i ＝ １}δ_ｉ （10） となり、r₁が時刻Ｔ＝１に左端のセルに入力されたと
き、 Ｔ＝７＋Σ⁶ _{i ＝ １}δ_ｉ＋２（Ｎ−１）＋１ にS_Nが出力される すなわち、疎帯行列ベクトル積の場合とは違い、各セル
間の遅延時間の設定の仕方が計算時間に影響を及ぼすよ
うになる。したがって、Ｔを最小限にするには、δ_２＝
δ_３＝δ_５＝０とする。このときの計算時間は最も短
く、時刻Ｔ＝2M＋６に終了する。ちなみに、計算時間の
最も長いのは、δ_８＝δ₁₀＝δ₁₁＝０のときで、Ｔ＝2N
＋2xy−６に処理が終わる。

デバイスシミュレーションでは、xyが大きく、数万にも
及ぶ場合があり、また反復法による計算であるため、遅
延時間の選び方が重要となる。

一方後退代入の計算式は次ぎのようになる（ｉ＝Ｎ〜
１）。

t_i＝s_i−g^U _it_i+xy−g^U′t_i+xy-1 −g^U″_it_i+xy-x−f^U _it_i+x −f^U′t_i+x-1−e^U _it_i+1 ……（11） したがって、前進代入における入力データの組（r_i,…,
c^L _i,d^L-1 _i）を（s_i,…,e^U _i,1）と置き換えることによっ
て、同じアレーを用いて、同じ遅延時間の設定の下で実
行することができる。これは不完全LDL^T分解に基づく場
合も同様である。

ここで、第10図は行列ベクトル積を実行するMvmモジュ
ール12の具体的な構成を示し、また第11図は前進・後退
代入を実行するFbsモジュール13の構成列を示す。

さらに、第12図は第５図で示した不完全行列分解アレー
を構成する各セル構成例を示しているもので、（Ａ）図
は基本セル、（Ｂ）図は下三角要素出力セル、（Ｃ）図
は対角要素出力セル、（Ｄ）図は上三角要素出力セル、
（Ｅ）図は時間調整セルをそれぞれ示している。

また、第13図の（Ａ）は第８図で示した積和演算セルを
構成する内積演算セルの具体的な構成例を示し、また同
図の（Ｂ）は和演算セルを示している。

デバイスシミュレーションにおいて、これを高速化する
手段について考えると、デバイスシミュレーションの問
題の特徴から、問題を分割することができ、これらを並
列に解くことができる。特に、疎帯行列・ベクトル積、
前進・後退代入、ベクトルの和、内積はループ内にあ
り、繰り返し計算されるものであるため、この部分の高
速化の可否によって、計算時間に大きな差が生ずる。以
下の説明では、疎帯行列ベクトル積、前進・後退代入の
高速化手段を示す。しかし、前進・後退代入を高速化す
る手段は、疎帯行列ベクトル積の高速化手段と同じであ
るので、これについてのみ説明する。

前述した方法で離散化を行った場合、シミュレーション
対象領域の境界上に位置する点では、近傍の格子点の
内、いくつかが存在しない。このことに注目して係数行
列Ａをxy次元で正方行列に分割し、それぞれをブロック
行列とする。前述の性質からこのブロック行列は対角行
列、５重対角行列、零行列のいずれかになる。

各点（i,j）、（１≦i,j≦ｚ），について゜A^ijをxy次
元のブロック行列、゜p^j、゜qⁱを対応するxy次元のベク
トルとする。このとき、疎帯行列・ベクトル積（ｑ＝A
p）は、ブロック行列毎に分割して次の式で表現され
る。

゜q_i＝Σ^Z _{i ＝ １}゜Ai_j゜p_j （12） 但し、s^A＝｛（i,j）|j＝ｉ−1,i＋１｝とおくと、（i,
j）s^Aについて゜A^ij＝０である。したがって、前記式
（12）の各゜qⁱは、具体的には次のように表現される。

゜q¹＝A¹¹゜p¹＋゜A¹²゜p² ゜q²＝゜A²¹゜p¹＋゜A²²゜P²＋゜A²³゜p³ ゜q³＝゜A³²゜p²＋゜A³³゜p³＋゜A³⁴゜p⁴ １ ゜q^Z＝゜A^ZZ-1゜p^z-1＋゜A^ZZ゜p^Z ……（13） ここで、゜A^ij-1,゜A^ij+1は、対角行列であり、゜A^ijは
５重対角行列である。

この式（13）の各゜q_iの計算を１つのアレーで計算さ
せ、ｚ個のアレーを並列に動作させることで、高速化を
達成できる。さらに各データの出力時刻に同期させて、
ベクトルの内積（q,p）をパイプライン的に計算させる
ことによって、全体としてさらに高速化するようにな
る。これをブロック並列計算と呼び、゜q_iに対する処理
をするアレーを［Array_i］と呼ぶ。

この［Array_i］は第14図で示すように、疎帯行列ベク
トル積アレーに第15図で示す内積演算セルを付加したも
のとして実現する。また、和のパイプライン処理のた
め、第７図で示した積和演算セルの機能に若干の変更を
加えたセルが必要となる。

これは、入力データが時間間隔２で入力されることに着
目し、データ流のデータが存在しない時間を利用するも
のである。γ_inに対する入力データ流は、゜A^ijの各要
素が時間間隔２で流れてくるものであるが、その時刻の
状態を（Red）とし、間の時刻の状態を（White）とす
る。第13図において、機能の変更が必要なセルは＋印で
区別し、その機能を次のようにする。

if（White） Register←β_in＋γ_in else if（Red） α_out＝α_in＋register×γ_in まず、内積演算セルのアキュムレータ、カウンタの初期
値を、それぞれ0,1に設定し、カウンタがxyより小さい
ときには、そのブロックで内積の部分和がアキュムレー
タに順次累算され、カウンタの値がxyになったとき、す
なわちxy次元ベクトル゜qⁱ最後の要素゜qⁱ _xyに対する処
理が行われた後、内積の部分和が次の［Array_i＋１］
のγ_inに送られる。

この［Array_i］の動作は、例えば次のように行われ
る。式（13）において、゜q_iの計算で最初に使われる゜
p^(i-1)はベクトル゜p^(i-1)aと゜p^(i-1)bとの和であり、
゜p^(i-1)a、 ゜p^(i-1)bの第１要素゜p^(i-1)a ₁、 ゜p^(i-1)b ₁は、それぞれＴ＝T_iに積和演算セルのβ_in、
γ_inへWhite列として入力される。加算の結果はセル内
のレジスタに格納され、Ｔ＝T_i＋１で゜qⁱ ₁の計算に使
用される。゜qⁱ ₁はＴ＝T_i＋２からＴ＝T_i＋２＋2xまで
は゜A^ij゜pⁱの結果を受取りながら右方に進み、Ｔ＝Tⁱ
＋５＋2xに゜qⁱ ₁゜pⁱ ₁がアキュムレータに加えられ、同
時に゜qⁱ ₁が出力される。

全体の動作は、まず［Array_1］でＴ＝１に゜q¹の処理
を開始し、以後一単位時間づつ遅らせて［Array_2］［A
rray_3］と順次処理を開始させる。前述したように［Ar
ray_i］内での処理が進行し、゜q^Z _xyはＴ＝2xy＋2x＋ｚ
＋３に［Array_z］から出力され、同時に内積（q,p）の
結果も出力される。

この様に複数個の［Array］を用いたブロック並列計算
（T_bp＝2xy＋2x＋ｚ＋３）では、8z個のセルを用いる
が、そうでない場合（To＝2xyz＋2xy）に比べてT₀/T_bp
＝ｚとなり、約ｚ倍速くなる。

セル間の遅延処理について考えてみると、このセル間の
遅延処理をどの様に行うかについては、シフトレジスタ
を用いる手段、メモリを用いる手段が考えられる。高速
化のためにはシフトレジスタを用いる方がよいが、ハー
ドウエアとして大きくなる。既存のメモリ素子を用いて
FIFOを実現する手段の方が現実的である。

セル間の遅延時間は、最大で約2xy（≧2¹¹）であり、デ
バイスシミュレーションの数値データは64ビットである
から、少なくとも16キロバイト程度のメモリが必要であ
る。一方ブロック並列計算では約2xの遅延であり、遅延
用のメモリとしては２キロバイト程度であれば、数十万
次元のシミュレーションにも対応できる。

［発明の効果］ 以上のようにこの発明に係る三次元デバイスのシミュレ
ーションによれば、その高速化のために小数個のセル
（例えば行列分解に64個、行列ベクトル積に７個、前進
・後退代入に７個）によって、大規模問題を効率的に扱
うことができるシストリックアレーを得ることができ
る。したがってＮを三次元シミュレーションの対象領域
の全格子点数とするとき、計算時間はＮに比例するもの
となり、非常に高速化できる。また離散化により得られ
る係数行列の特徴を活かした高速化手段が得られた。こ
の場合必要セル数は、Ｎ^1/3倍になるが、計算時間はＮ
^2/3に比例するようになる。

ここで、各アレーで必要なセルは、数種類になるもので
あるが、必要な演算処理は類似している。したがって、
これを実現する場合には、全ての機能を取り込み使用時
にその機能を切り替える機構を導入して、１つのセルと
して実現させることができる。第12図および第13図はそ
の概略を示している。

【図面の簡単な説明】

第１図はこの発明の一実施例に係るデバイスシミュレー
ション装置を説明するための構成図、第２図はシミュレ
ーションにおける７点差分近似を説明する図、第３図は
行列方程式の態様を説明する図、第４図は基本演算の解
法を説明するフローチャート、第５図は不完全行列分解
アレーの構成を示す図、第６図の（ａ）〜（ｅ）はそれ
ぞれ上記アレーを構成するセルを説明する図、第７図は
不完全行列分解モジュールを説明する図、第８頭は積和
演算セルの機能を説明する図、第９図は疎帯行列・ベク
トル積アレーを示す図、第10図は行列ベクトル積モジュ
ールの構成を説明する図、第11図は前進・後退代入モジ
ュールの構成を説明する図、第12図の（Ａ）〜（Ｅ）は
それぞれ前記不完全行列分解アレーを構成する演算セル
の具体的な構成例を示す図、第13図の（Ａ）および
（Ｂ）はそれぞれ積和演算セルの構成例を示す図、第14
図はブロック並列計算アレーを説明する図、第15図はこ
の並列計算アレーに付加された内積演算セルを示す図で
ある。 11……不完全行列分解モジュール、12……行列ベクトル
積モジュール、13……前進・後退代入モジュール、14…
…グローバルデータバス、15……ホストコンピュータ、
16〜18……コントローラ、19……グローバルコントロー
ルバス。

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｈ０１Ｌ 29/00 (56)参考文献 特開 平１−129434（ＪＰ，Ａ)

Claims (1)

【特許請求の範囲】
1. 【請求項１】基本セル、下三角要素出力セル、対角要素
   出力セル、下三角要素出力セル、および時間調整セルか
   らなる５種類の演算セルを六角形に配置して構成され、
   行列の各要素はそれぞれ上方から入力され、分解された
   行列の各要素はそれぞれ下方から出力されるように構成
   されている、疎帯行列の不完全LU分解用のシストリック
   アレーと、 複数の積和演算セルが一次元的に並べて配置され、この
   複数の演算セルの一次元配列の一方の端からベクトルの
   要素が特定される時間間隔で入力され、前記各演算セル
   にはそれぞれ各行列の各要素が特定される時間間隔で入
   力されて、その各行列要素と各ベクトル要素との積を順
   次累積して出力ベクトルの要素として出力するようにし
   た疎帯行列ベクトル積用シストリックアレーと、 複数の積和演算セルが一次元的に並べて配置され、この
   複数の演算セルの一次元配列の一方の端からベクトルの
   要素が特定される時間間隔で入力され、前記各演算セル
   にはそれぞれ各行列の各要素が特定される時間間隔で入
   力されて、その各行列要素と各ベクトル要素との積を順
   次減算して出力ベクトルの要素として出力するようにし
   た前進後退代入用シストリックアレーとを具備し、 前記疎帯行列の不完全LU分解用シスリックアレー、疎帯
   行列ベクトル積用シストリックアレー、および前進後退
   代入用シストリックアレーは、それぞれデータバスおよ
   びコントロールバスによって結合され、主計算部からの
   指令に基づき演算動作を実行させられるようにしたこと
   を特徴とする三次元デバイスのシミュレーション装置。