(57)【要約】【課題】線形連立方程式をガウス・ヤコビ法で求解する際に、専用ハードウェアによる並列化効果を大幅に向上させる。【解決手段】セル３０１は、隣接セルとの複数の接続関係を記憶する手段３０４と、反復演算の回数を記憶する手段３０５と、線形連立方程式の係数行列の値を記憶する手段３０６と、乗算及び加算を行う手段３０８と、反復演算の演算結果を記憶する手段３０７と、隣接セルとの間で演算結果の受渡し及び演算順を制御する手段３０３とを有し、反復演算の一回分の演算結果を係数行列の対角部分に割り当てられた対角セルに係数行列の行ごとに集積する第一工程と、対角セルに得られた一回分の演算結果を対角セル以外のセルに係数行列の列ごとに伝播させる第二工程とを反復演算の回数だけ繰り返す。【選択図】  図３
2007086919.tif 000002
【特許請求の範囲】
【請求項１】
ガウス・ヤコビ法による反復演算で線形連立方程式を求解する装置であって、
それぞれ隣接セルとの複数の接続関係を記憶する手段と、前記反復演算の回数を記憶する手段と、線形連立方程式の係数行列の値を記憶する手段と、乗算及び加算を行う手段と、前記反復演算の演算結果を記憶する手段と、隣接セルとの間で演算結果の受渡しを行う手段と、演算順を制御する手段とを有し、それぞれに線形連立方程式の係数行列の要素値が割り当てられ、前記接続関係に従い接続される複数のセルを備え、
前記演算順を制御する手段は、前記反復演算の一回分の演算結果を前記係数行列の対角部分に割り当てられた対角セルに前記係数行列の行ごとに集積する第一工程と、前記対角セルに得られた一回分の演算結果を前記対角セル以外のセルに前記係数行列の列ごとに伝播させる第二工程とを前記反復演算の回数だけ繰り返す線形連立方程式の求解装置。
【請求項２】
前記隣接セルとの複数の接続関係を記憶する手段は、前記第一工程に対応する接続関係と前記第二工程に対応する接続関係とを記憶する請求項１記載の線形連立方程式の求解装置。
【請求項３】
前記隣接セルとの複数の接続関係を記憶する手段は、前記第一及び第二工程に対応する接続関係を前記第一工程又は前記第二工程の実行に応じて選択可能に記憶する請求項１記載の線形連立方程式の求解装置。
【請求項４】
請求項１から３の何れか一項記載の線形連立方程式の求解装置に必要なセルを決定する方法であって、
前記係数行列の要素数より少ないセル数の縮小枠を決定し、
前記第一及び第二工程の接続関係を維持しながら前記縮小枠に移動可能なセルを前記縮小枠内へ移動させる方法。
【請求項５】
前記縮小枠内のセルを前記第一及び第二工程の接続関係を維持しながら移動又は入替えを行う請求項４記載の方法。
【請求項６】
請求項１から３の何れか一項記載の線形連立方程式の求解装置を備えた回路シミュレーション装置。
【請求項７】
線形連立方程式の規模に応じて並列動作可能に分割した各求解装置のそれぞれに線形連立方程式を割り当てる手段を備える請求項６記載の回路シミュレーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は半導体装置の回路シミュレーション等に用いる線形連立方程式を求解する装置に関する。
【背景技術】
【０００２】
従来、半導体装置の回路動作の検証にはＳＰＩＣＥなどの回路シミュレータを用いるのが主流である。半導体装置の回路シミュレーションにおいては、通常、非線形微分方程式を求解する必要がある。このために、非線形微分方程式は数値積分法で差分化されて非線形代数方程式に変換され、その後ニュートン法などで線形連立方程式に変換される。この線形方程式は通常は大規模なスパース行列で表現され、ガウス消去などの直接法で求解される。
【０００３】
近年における半導体装置の設計規模の大型化や回路動作の高速化に伴い、計算コストが増大しシミュレーション時間が増すことが大きな問題となっている。回路シミュレーションの原理、課題などについては非特許文献１が詳しい。
【０００４】
回路シミュレーションの高速化のためには、特許文献１のように回路分割するものや、特許文献３のように計算を簡略化し収束性を向上させる方法、特許文献２のように大域収束性を保証し大規模化に対応する方法など、計算のアルゴリズム自体を改変するものがある。
【０００５】
一方、特許文献４のように解法自体は維持し、回路シミュレーションを行うハードウェア自体を回路シミュレーションに適したものに改変して高速化する手法も考えられる。また、後述する乗算器の構成については非特許文献２が詳しい。
【特許文献１】特許第３１６１１４０号公報
【特許文献２】特許第２９８３１１６号公報
【特許文献３】特許第３０２２１０３号公報
【特許文献４】特開２００３−２４２１３３号公報
【非特許文献１】浅井秀樹、渡邉貴之、「電子回路シミュレーション技法」、科学技術出版、２００２年１２月２５日
【非特許文献２】富田眞治、「コンピュータアーキテクチャ」、第２版、丸善株式会社、２０００年９月１５日
【０００６】
半導体装置の回路シミュレーションにおいて、一般に小規模な回路ではニュートン法などのヤコビアン行列の計算が、数千方程式を超える大規模な回路方程式の解析ではガウス消去などの線形連立方程式を解く行列演算過程が支配的となると言われている（例えば、非特許文献１第１２５頁参照）。
【０００７】
現在の標準的な回路シミュレータにおいては、行列演算過程でガウス消去法、ＬＵ分解法などの直接法が利用される。ここでの課題は大規模回路の線形連立方程式をいかに高速に求解するかである。以下に、直接法の代表例として数１に示す３元の連立方程式でのガウス消去法を説明する。
【数１】
2007086919.tif 000003
【０００８】
数１は初期システムでピボット操作により各要素の値が更新される。ピボット操作が進む度に各要素に「'」「''」を付加して更新過程を示す。１行目、２行目、３行目をそれぞれe1、e2、e3と定義する。このとき、数２の操作により数１は数３に変形される。
【数２】
2007086919.tif 000004
【数３】
2007086919.tif 000005
【０００９】
ここで、さらに数４の操作により数３は数５へと変形され、上三角化が終了する。そして、数６の後退代入操作で解が求められる。
【数４】
2007086919.tif 000006
【数５】
2007086919.tif 000007
【数６】
2007086919.tif 000008
【００１０】
ここで、ガウス消去法を演算する計算機の構成を説明する。通常の電子計算機のハードウェア構成を図１に示す。一般の回路シミュレータにおいては、線形連立方程式は電子計算機上のソフトウェアにより、メインメモリ１０２などに蓄積された値をＣＰＵ１０１内のＡＬＵ（算術論理演算装置）１０３で演算することで求解される。
【００１１】
近年の計算機は複数のＡＬＵを有し、ハードウェア若しくはソフトウェアにて並列に計算できる命令を選択し、同時並列に演算する機構を有するものも多い。いかに並列数を多くするかはプロセッサの高速化などにおいても重要な命題である。
【００１２】
次に、線形連立方程式を解く専用ハードウェアを用いる場合を考える。専用ハードウェアは動画像処理などの演算量の多い信号処理で使用されており、計算機の負荷軽減や処理時間の短縮に有効である。専用ハードウェアにおける高速演算は複数の演算器の搭載による演算の並列化で実現されている場合が多い。
【００１３】
ガウス消去法を専用のハードウェアで並列演算する場合は、その性質上直列的に演算する必要がある。例えば、数４におけるe3"を演算するにはe2'及びe3'の演算後でなければならない。また、後退代入は上三角化の後でなければできない。行の値に係数を掛ける場合（例えば、数２で(a21/a11)にe1を乗算するなど）に関しては並列化により高速化は可能であるが、ハードウェアを無限に増やしても高速化には一定の限界がある。
【００１４】
演算器を高速化することも考えられるが、メインメモリは一般に演算器より低速であり、いわゆるノイマンボトルネックの限界がある。また除算も必要で四則演算全てを行う必要があり、ハードウェア規模も増大する。
【００１５】
一方、高速化の手法として直接法に代わり緩和法を用いる方法がある。緩和法では直接法で発生するフィル・インの発生を避けることができ、計算量の観点からは反復回数が少なければ直接法よりも優位となる利点がある。一方、一定の条件を満足しないと収束しない欠点がある。
【００１６】
緩和法にはガウス・ヤコビ法やガウス・サイデル法などがある。これらの方法は前述した直接法と比較するとハードウェア化に向いている。しかし、効率の良いハードウェアを作成するには一定の工夫を要する。まず、以下にガウス・ヤコビ法について説明する。
【００１７】
解を求める線形方程式を数７のように表す。
【数７】
2007086919.tif 000009
【００１８】
ここで、AはN×Nの係数行列、bはN×1の列ベクトル、xはN×1の未知の列ベクトルである。この未知ベクトルを数８のように変形する。
【数８】
2007086919.tif 000010
【００１９】
ここで、行列Dは行列Aの対角行列であり、行列D'は行列Aから対角部分を除いた行列である。すなわちD'=A-Dである。また、kは緩和反復回数である。数２でi番目の変数xiについて変形すると数９を得る。aは行列Aの各要素である。
【数９】
2007086919.tif 000011
【００２０】
この反復を繰り返し、数１０を満足（εは十分小さな正の値）したら終了し、この際のxを解とする。
【数１０】
2007086919.tif 000012
【００２１】
ガウス・ヤコビ法は前述のごとく収束しない場合があるという欠点を持つ。行列Aが対角優位で、少なくとも一行が強く対角優位であるときに収束することが知られている。回路内の全ての節点に接地容量が存在するような回路では、数値積分法での差分化において積分刻み幅を小さく選べば必ず対角優位になることが知られており、緩和法での収束性が保証される。従って、このような回路網では緩和法は有効となる。（非特許文献１第１４０頁参照）
【発明の開示】
【発明が解決しようとする課題】
【００２２】
前述したように、線形連立方程式を求解する際に専用ハードウェアを用いる場合は、複数の演算器を用いて並列に演算することができ、高速化できる利点がある。しかし、計算方法によっては並列化しにくい場合もある。ガウス・ヤコビ法は後述するようにガウス消去法などの直接法と比べて並列化しやすい方法である。
【００２３】
しかし、ハードウェア資源を有効に活用するには、単にハードウェア化するだけでなく、各値をどのようにハードウェアに割当てるかのアルゴリズムが重要となる。
【００２４】
本発明は、半導体装置の回路シミュレーション等に用いる線形連立方程式をガウス・ヤコビ法で求解する際に、専用ハードウェアによる並列化効果を大幅に向上させることが可能な線形連立方程式の求解装置を提供することを目的とする。
【課題を解決するための手段】
【００２５】
上記課題を達成するために、線形連立方程式をガウス・ヤコビ法で求解するための新たな専用ハードウェアと割当てアルゴリズムを考案した。
【００２６】
具体的には、ガウス・ヤコビ法による反復演算で線形連立方程式を求解する装置であって、それぞれ隣接セルとの複数の接続関係を記憶する手段と、前記反復演算の回数を記憶する手段と、線形連立方程式の係数行列の値を記憶する手段と、乗算及び加算を行う手段と、前記反復演算の演算結果を記憶する手段と、隣接セルとの間で演算結果の受渡しを行う手段と、演算順を制御する手段とを有し、それぞれに線形連立方程式の係数行列の要素値が割り当てられ、前記接続関係に従い接続される複数のセルを備え、前記演算順を制御する手段は、前記反復演算の一回分の演算結果を前記係数行列の対角部分に割り当てられた対角セルに前記係数行列の行ごとに集積する第一工程と、前記対角セルに得られた一回分の演算結果を前記対角セル以外のセルに前記係数行列の列ごとに伝播させる第二工程とを前記反復演算の回数だけ繰り返す。
【００２７】
上記構成によれば、線形連立方程式の係数行列に対応してセルを配列し、係数行列の行ごとの演算を行う第一工程と演算結果を係数行列の列ごとに伝播させる第二工程とに合わせて隣接セルとの接続関係を設定することで、各セルに演算を平均的に分配することができ、また、構成単位となる各セルが演算器としてだけでなくメモリとしての役割も果たしていることで、メモリとのボトルネックが無くセルの実装数に比例して性能を向上させることができるため、並列化効果を大幅に向上させることができ、第一工程と第二工程の繰り返す方法で効率よく高速にガウス・ヤコビ法による解が得られる。
【００２８】
前記隣接セルとの複数の接続関係を記憶する手段は、前記第一工程に対応する接続関係と前記第二工程に対応する接続関係とを記憶する。この構成によれば、隣接セルとの接続が第一工程用の接続か第二工程用の接続かが一意に決定されるため、各セルにおいては隣接セルからは値のみを受渡しすればよく、その値が第一工程用か第二工程用かを区別する情報を受取る必要がないため、構造及び制御を単純化できる。
【００２９】
又は、前記隣接セルとの複数の接続関係を記憶する手段は、前記第一及び第二工程に対応する接続関係を前記第一工程又は前記第二工程の実行に応じて選択可能に記憶する。隣接セルとの接続が第一工程用の接続か第二工程用の接続かが一意に決定されると接続関係に制約を発生させ、必要なセル数が多くなる欠点があるが、この構成によれば、隣接セル間で渡す値が行接続か列接続かの情報を受渡す必要があるものの、この二者択一情報を受け渡すのみでセルの使用効率を大きく向上させる利点がある。
【００３０】
線形連立方程式の求解装置に必要なセルを決定する場合、前記係数行列の要素数より少ないセル数の縮小枠を決定し、前記第一及び第二工程の接続関係を維持しながら前記縮小枠に移動可能なセルを前記縮小枠内へ移動させる。また、前記縮小枠内のセルを前記第一及び第二工程の接続関係を維持しながら移動又は入替えを行う。
【００３１】
線形連立方程式の係数行列は一般にスパース行列であり、全てのセルに演算器を割り当てた場合は演算器を使用しないセルが多数存在することになるが、上記構成によれば、第一工程用及び第二工程用の接続関係を維持しながら縮小枠内のセルの移動又は入替えを所定回数繰り返すことにより、演算器を使用するセルをセル数の少ない縮小枠に収めることができるため、効率良くセルに値を割り振ることが可能となり、ハードウェアの小規模化を実現することが可能となる。
【００３２】
また、求解装置を複数備える回路シミュレーション装置においては、線形連立方程式の規模に応じて並列動作可能に分割した各求解装置のそれぞれに線形連立方程式を割り当てる手段を備える。
【発明の効果】
【００３３】
本発明によれば、線形連立方程式の係数行列に対応してセルを配列し、係数行列の行ごとの演算を行う第一工程と演算結果を係数行列の列ごとに伝播させる第二工程とに合わせて隣接セルとの接続関係を設定することで、各セルに演算を平均的に分配することができ、また、構成単位となる各セルが演算器としてだけでなくメモリとしての役割も果たしていることでメモリとのボトルネックが無くセルの実装数に比例して性能を向上させることができるため、並列化効果を大幅に向上させることができ、第一工程と第二工程の繰り返しにより効率よく高速にガウス・ヤコビ法による解が得られる。
【発明を実施するための最良の形態】
【００３４】
（実施の形態１）
数１１の線形連立方程式を例に、ガウス・ヤコビ法で線形連立方程式を求解するための本発明の実施の形態に係る専用ハードウェアの構成法を説明する。
【数１１】
2007086919.tif 000013
【００３５】
まず、線形連立方程式の右辺を全て「1」にするように右辺の値で左辺の値を除算する。このようにすることで、後述するハードウェア化が簡略化できる。次に、数１２の各値を新たに数１３のように定義しなおす。
【数１２】
2007086919.tif 000014
【数１３】
2007086919.tif 000015
【００３６】
数１３に基づき数９を変形させると線形連立方程式は数１４のようになる。
【数１４】
2007086919.tif 000016
【００３７】
図３は本発明の専用ハードウェアを構成する単位回路（以下「セル」という）である。図３において、セル３０１は制御回路３０３、接続情報蓄積部３０４、反復回数蓄積部３０５、係数蓄積部Ａ３０６、係数蓄積部Ｂ３０７、演算器３０８で構成され、隣接セルと接続線３０２を介して接続される。
【００３８】
数１４を求解するために、このセル１６個を図２（１）に示すように４行×４列の構成に接続する。各セルには数１３で非零の係数を割当てる。図２（１）の網がけをしたセルがこれに該当する。
【００３９】
各セルは図４に示す手順で演算される。まず、係数行列の対角部分に相当するセルを選択する（４０１）。対角部分とは数１３におけるc11、c22、c33、c44であり、数１４の右辺の項(1/aii)に該当する。図２（１）においては点線で囲われたセルがこれに該当する。
【００４０】
次に各セルに接続情報を設定する（４０１）。接続情報は接続情報蓄積部３０４に蓄積される。ここでいう接続情報とは、行方向の接続（以下「行接続」という）と列方向の接続（以下「列接続」という）とに分けられる。
【００４１】
行接続については、例えば図２（１）のS11とS13は同じ行で非零の関係があり、零のセルであるS12を介して接続される。同様にS21とS22、S31とS33とS34、S42とS44も行接続される。
【００４２】
列接続は非零のセルで同一の列に存在するものを関連付けるものである。図２（１）においてS11とS21とS31、S22とS42、S13とS33、S34とS44の組合せで接続される。この接続情報はガウス・ヤコビ法の反復演算（４０４）において演算結果の授受に使用される。
【００４３】
次に反復回数を設定する（４０２）。これは数１３のkに該当する値で反復回数蓄積部３０５に蓄積される。ガウス・ヤコビ法においては数１０を満足した時点で解とするが、本発明の構成では対角部分の各セル全てが数１０を満足しているかの確認が困難であるため、数１０の比較は行わず、反復回数を設定し、この回数分反復したら終了とする。
【００４４】
数１０を満足しているかの確認が困難な理由は、本構成では隣接セルでのデータの授受を原則としているためである。また、数１０を確認するには比較器及び１回前の結果の蓄積が必要となり、面積増加及び制御の複雑化を招くためである。そこで、反復回数分で終了とすることでハードウェアを縮小することができる。
【００４５】
続いて係数の設定を行う（４０３）。係数Aは係数蓄積部Ａ３０６に蓄積される。ここには対角部分は(1/aii)に相当する係数を、非対角部分にはaijの値を設定する。係数Bは反復演算により計算される解が逐次蓄積される。この係数Bは数１４のxjk-1に該当する。この値は反復計算で解に近づいていくため、設定する初期値は零以外の適当な値でよい。
【００４６】
以上で初期設定が完了しガウス・ヤコビ法の反復演算（４０４）に入る。この過程は以下の手順でなされる。まず、非対角要素につき係数Aと係数Bの乗算（数１４のcijxjk-1に該当）を行う。続いて行接続の情報に従い、演算結果を加算しながら対角部分に集める演算（数１４のΣcijxjk-1に該当）を行う（図２（２））。対角部分に値の合計が集まったら対角部分のセルの内部で数１４の残りの演算を行い、結果を係数蓄積部Ｂ３０７に格納する。
【００４７】
以上で反復演算が１回終了する。そして初期で設定された反復回数に満たない場合は次の反復演算を行う（４０５）。この際に、まず対角部分の係数蓄積部Ｂ３０７に蓄積された値を列接続に従って値をシフトさせる（図２（３））。これにより次の反復演算が開始できる。
【００４８】
初期設定された反復回数に至ったら計算を終了し結果を読み出す（４０６）。演算結果は対角部分のセルから読み出せばよい。
【００４９】
図３に示す１セルの隣接セルとの接続は４本としているが増加させることは理論上可能である。現実のハードウェアの設計では接続本数を増やすとセル内の信号先の調停や、セルの配置が困難になる可能性があるため、これらのトレードオフで決定すべきである。
【００５０】
次に、本実施の形態１における各セルの接続情報の設定方法について具体例により説明する。図５は図２（２）、（３）に示される演算順をセル間の接続関係として書き換えたものである。
【００５１】
図２（２）における行接続の演算は図５においては破線の接続として示され、図２（３）おける列接続の演算は図５においては実線での接続として示されている。以後の図においても同様の意味で実線と破線を用いる。セルは値を有するセル（例えば、図５のA-i。以下「数値セル」と呼ぶ。）と、値を有しないセル、すなわち線形連立方程式において係数がゼロにあたるセル（例えば、図５のA-ii。以下「ゼロセル」と呼ぶ。）とに分けられる。
【００５２】
セルは上下左右に４本の接続関係を有し、隣接のセルと結合され値の受渡しを行う。以後、各接続を「腕」と呼ぶ。各腕の方向を図６（１）のごとくＵ側、Ｄ側、Ｌ側、Ｒ側と呼ぶ。）ただし、腕は４本以外の数でも可能であり、あくまで例示である。
【００５３】
ゼロセルは図６（１）〜（３）に示すような動作を行う。例えば、図６（１）ではＬ側とＲ側が行接続とし決定されおり、Ｌ側はＲ側以外の腕とは接続されず、また接続関係を有するＲ側と列接続としての値の受渡しを行うことはない。すなわち、本実施例におけるゼロセルは一定の接続関係を有し、行接続と列接続は競合しない。
【００５４】
数値セルにおいても同様である。図７（１）〜（３）に示すように、数値セルにおいても、各腕は他の腕と一意の接続関係を有し、行接続と列接続は競合しない。なお、接続関係は図３の制御回路３０３及び接続情報蓄積部３０４において決定される。
【００５５】
これにより、隣接セルからは値のみを受渡しすればよく、その値が行接続なのか列接続なのか情報を受取る必要がないため、構造及び制御を単純化できるメリットがある。一方、接続関係に制約を発生させるため、必要なセル数が多くなる欠点がある。この対策については実施の形態２で説明する。
【００５６】
以上のように、本発明の専用ハードウェアの構成法によると、第一にハードウェアが並列化しやすい点が挙げられる。直接法では演算器の速度を上げてもメモリとの速度差により一定以上性能が上がらなくなる。しかし、本構成では各セルが演算器としてだけでなくメモリとしての役割も果たしており、メモリとのボトルネックが無いためセルの実装数に比例し性能を向上できる。これは直接法のごとく並列度を上げても性能が上がらない構成と比べて有利な効果である。
【００５７】
また、半導体の微細化に伴い搭載できるトランジスタ数は増大しているが動作速度は上げにくくなっている。本発明のように低速だが面積に比例し性能を向上できる構成はこの点でも有利である。
【００５８】
さらに本構成において、数９をソフトウェアなどで計算して設定することや、数１１の右辺で左辺の係数を割った値を設定することによりハードウェアを簡略化することができる。この部分は初期設定で一度計算すればよいため、計算負荷は軽くハードウェア化するメリットは少ないからである。
【００５９】
一方、配列の要素数だけセルを実装すると回路規模が莫大になるという問題がある。前述のごとく除算回路は不要であるが、加算器（減算も可能なもの）と乗算器は必要である。高速演算可能な配列型等の並列型乗算器は通常回路規模が大きく、これらを大量に並べることは半導体の微細化が進んだとはいえ困難である。
【００６０】
Booth法などによる逐次型乗算器を用いると回路規模は大幅に低減できる。一方、並列演算器は演算時間が原則計算するビット数分かかり低速である（乗算器の構成は非特許文献２第１２４〜１２８頁に詳しい）。これにより演算速度は低下するが大量のセルの実装が可能となる。セル数の増加により処理量は増大できる。
【００６１】
本発明の専用ハードウェアの構成法においては、セル内での演算とセル間の値の受け渡しで解が求められる。セル間の受け渡しは隣接セルからの情報によりなされるため、各セルは非同期に動作することができる。
【００６２】
通常の半導体装置における演算装置は同期設計がなされており、多数の演算装置を実装する場合は、演算装置間での同期をとるために大量のバッファを用いてクロック信号の位相を合わせるため、面積や電力面で不利となる。本発明では各セルが非同期に動作できるため、大量のセルを実装しても同期をとるための大量のバッファは不要で低面積、低電力化が可能である点で有利である。
【００６３】
図１６は本発明の専用ハードウェアを用いた回路シミュレータの構成例を示すブロック図である。上述した演算はＣＰＵ１０１及びメインメモリ１０２に接続された専用装置１１０にて実行される。この専用装置１１０はセルを複数実装した装置１１２と、これらを１つあるいは複数結合した装置１１３と、演算する値及び演算結果の入出力を制御するコントローラ１１１からなる。
【００６４】
このようにして専用ハードウェアを用いて回路シミュレータを構成することで、ＣＰＵ１０１の負荷を最小限に抑え、低面積、低消費電力で高速に線形連立方程式を求解する装置を提供することができる。線形連立方程式の規模が小さい場合は、コントローラによりセルを複数実装した装置１１２をそれぞれ独立に使用することが可能で、並列に複数の線形連立方程式を求解することができる。
【００６５】
（実施の形態２）
前述した通り、実施の形態１においては接続関係が単純化されるため、必要なセル数が多くなり回路規模が大きくなる問題がある。一方、演算すべき線形連立方程式の係数行列は一般にスパース行列であり、全てのセルに演算器を割り当てた場合は演算器を使用しないゼロセルが多数存在することになる。例えば、図２（１）では１６個のセルを使用しているが、数値セルは９つのみである。そこで、実施の形態２においては、効率良くセルに値を割り振ることでハードウェアの小規模化を可能にする。
【００６６】
図５における接続関係は、直感的には図８に示す接続関係としても全く同一の機能を有することは明らかである。行接続及び列接続が等価であるからである。図９に図８の接続におけるガウス・ヤコビ法の演算手順を示す。
【００６７】
図９（２）は行接続における演算順を、図９（３）は列接続における演算順を示している。これらを図５の接続における演算順を示す図２と比較しても全く等価であることが分かる。図８では数値セルが９個であるのに対して使用するセルも９個であり、最も最適化された割当てとなっている。
【００６８】
線形連立方程式が大きくなると完全に最適化することは困難であるが、原始の線形連立方程式での接続関係から大幅に小さい接続を求めることは可能であり、少ないセルで構成される装置で求解することに大きく寄与する。
【００６９】
ここでは、図５の接続から、接続関係の等価性を維持しながら、いかに図８における接続に至るかが問題となる。この問題を数学的に一意に求めることは困難である。また総当りで求めることも、対象の線形連立方程式の規模が大きくなると現実的でなくなる。なぜなら、組合せが天文学的値となるからである。また、この割当ての過程に大量の計算量が必要になると、求解が高速となっても結果として従来の方法と何ら変わりがないこととなる。
【００７０】
そこで、本実施の形態においては、簡便な操作を繰り返し行うことでセルの割当ての最適化を行う。図１０にセルの割当ての手順を、図１１に図５の接続から図８の接続に至る過程を例示する。
【００７１】
まず、原始の線形連立方程式からセルを収める枠を決める（４１０）。図５においては数値セルの個数が９個であり、完全に最適化された場合は３行×３列の枠に収まる。そこで、ここでは図１１（１）の太枠で示す範囲を縮小枠とし、この中に全セルを収めることを目標とする。
【００７２】
線形連立方程式が大きくなった場合は完全に最適化することができる可能性は低くなるため、縮小枠を完全に最適化された場合よりも大きくとり、次第に小さくしていく手法が有効である。
【００７３】
次に、終了回数を決定し終了カウントをゼロにする（４１１）。本発明の割当て方法は後述するように一定の手順を繰り返して最適化する。しかし、数学的に一意の割当てを求める方法ではないため、繰り返しに限度を設ける必要がある。これを決定するのが終了回数であり、繰り返し数をカウントする手順を終了カウントと呼ぶ。
【００７４】
次に枠内に入るセルがあるかを検索する（４１２）。図１１（１）においてはD-iiの”４”を枠内に入れることができ図１１（２）に至る（４１５）。枠内にセルを入れることができた場合は終了カウントをゼロに戻す（４１６）。
【００７５】
図１１（２）においては枠内に入れることができるセルが存在しないため、枠内でセルの移動又は置換を行う。この際、行接続及び列接続の関係を破壊しないことを条件とし移動する（４１３）。ここでは図１１（２）のA-iiiの”１”をA-ii移動させ、図１１（３）に至る。この際、終了カウントに１を加える（４１７）。
【００７６】
図１１（３）においても枠内に入れることのできるセルが存在しないため、枠内でセルの移動を行う。枠内では移動だけでなく、行接続及び列接続の関係を破壊しないことを条件としてセルの置換も行う（４１３）。例えば、図１１（６）から（７）に至るような場合である。
【００７７】
枠内での移動又は置換を終了回数分行っても（４１３、４１４、４１７）、枠内に入れることができるセルが存在しない場合は、最適化がそれ以上できないものとして、その時点の接続関係で演算を行う。この時点の接続関係が装置の規模を超えている場合は、図１に示す従来の手法で演算することとなる。
【００７８】
以上の手順により、行接続及び列接続の関係を維持しつつ、必要なセル数を減らすことが可能となる。この方法は各セルがゼロセルか数値セルかの区別を基準に行い、数値セルの値は問題ではない。したがって値の演算が行われてはおらず、最適化の過程は高速に行われる。ソフトウェアによる最適化が機能的には適当である。なお、本実施の形態の方法は次の実施の形態３における回路構成においても適用が可能である。
【００７９】
（実施の形態３）
実施の形態１のセルにおいては、セルの各腕の隣接するセルとの接続は行接続か列接続かいずれか一方のみであるものとした。それにより、前述したごとく接続関係に制約を発生させ、必要なセル数が多くなる欠点がある。
【００８０】
本実施の形態では、一定の条件下で行接続と列接続の競合を許可する構成を採る。例えば、図１２においてゼロセルのＬ側に着目すると、図１２（１）の列接続の場合はＵ側と、図１２（２）の行接続の場合はＤ側と２種類の接続関係を有する。そのために行接続か列接続かの情報を隣接セルから受け取り、これにより接続先を決定する構成を採る。図１３に示す数値セルの場合も同様である。
【００８１】
前述したように、行接続の演算と列接続の演算は別過程（例えば、図９の（２）と（３））であるため、二者択一の制御は可能である。なお、接続の関係は図３の制御回路３０３及び接続関係蓄積部３０４において決定される。
【００８２】
次に本実施の形態における最適化の具体例として、数１５の線形連立方程式を求解する場合を考える。
【数１５】
2007086919.tif 000017
【００８３】
数１５をそのままセルの接続に置き換えると図１４となる。この構成を本実施の形態の方法で最適化すると図１５のようになる。図１５（１）はセル間の列接続のみを図１５（２）はセル間の行接続のみを記載したものである。
【００８４】
例えば、図１５のセルA-iiiのＲ側の腕はセルA-ivのＬ側の腕と図１５（１）においては列接続され、図１５（２）においては行接続されており、セルA-iii内の接続先も行接続か列接続かで異なる。
【００８５】
隣接セル間で渡す値が行接続か列接続かの情報も受渡す必要があるが、二者択一のための情報を受け渡すのみであり、これだけでセルの使用効率を大きく向上させることができる点で大きな利点がある。
【００８６】
なお、異なる列接続間や行接続間も競合させることも理論上は可能であるが、前述したように行接続か列接続の二者択一の情報だけでなく、何番目の列接続の値かなどの情報を受渡ししなければならず、構造や制御が複雑になり現実的ではない。
【００８７】
本実施の形態におけるセルの腕の本数は実施の形態１と同じであるが、実施の形態１に比べて使用するセル数を減ずることが可能である点で有利である。
【産業上の利用可能性】
【００８８】
本発明の線形連立方程式の求解装置は、効率よく高速にガウス・ヤコビ法による解が得られるという効果を有し、半導体装置の回路シミュレーション等への適用に有用である。同様に大規模な線形連立方程式を解く必要のある分野は多数あり、流体計算、熱伝導解析のシミュレーションなどにも応用可能である。
【図面の簡単な説明】
【００８９】
【図１】通常の電子計算機のハードウェア構成を示す図。
【図２】本発明の線形連立方程式の求解装置における求解原理を説明する図。
【図３】本発明の線形連立方程式の求解装置を構成するセルの回路構成を示す図。
【図４】本発明の線形連立方程式の求解装置における演算手順を示すフロー図。
【図５】本発明の実施の形態１に係る線形連立方程式の求解装置におけるセルの結合を示す図。
【図６】本発明の実施の形態１に係る線形連立方程式の求解装置におけるゼロセルの接続を例示する図。
【図７】本発明の実施の形態１に係る線形連立方程式の求解装置における数値セルの接続を例示する図。
【図８】本発明の実施の形態２に係る線形連立方程式の求解装置におけるセルの結合を示す図。
【図９】本発明の実施の形態２に係る線形連立方程式の求解装置におけるセル割当てが最適化された後の各セルの挙動を示す図。
【図１０】本発明の実施の形態２に係る線形連立方程式の求解装置におけるセル割当て最適化の手順を示すフロー図。
【図１１】本発明の実施の形態２に係る線形連立方程式の求解装置におけるセル割当て最適化の過程を例示する図。
【図１２】本発明の実施の形態３に係る線形連立方程式の求解装置におけるゼロセルの接続を例示する図。
【図１３】本発明の実施の形態３に係る線形連立方程式の求解装置における数値セルの接続を例示する図。
【図１４】本発明の実施の形態３に係る線形連立方程式の求解装置におけるセルの結合を示す図。
【図１５】本発明の実施の形態３に係る線形連立方程式の求解装置におけるセル割当て最適化後の接続関係を示す図。
【図１６】本発明の線形連立方程式の求解装置を用いた回路シミュレータの構成例を示すブロック図。
【符号の説明】
【００９０】
１０１  ＣＰＵ
１０２  メインメモリ
１０３  ＡＬＵ（算術論理演算装置）
１１０  線形連立方程式を解く専用装置
１１１  コントローラ
１１２  本発明の線形連立方程式の求解装置
１１３  本発明の線形連立方程式の求解装置を複数結合した装置
３０１  １つのセル
３０２  隣接セルとの接続線
３０３  セルの入出力及び演算の制御回路
３０４  接続情報蓄積部
３０５  反復回数蓄積部
３０６  係数蓄積部Ａ
３０７  係数蓄積部Ｂ
３０８  演算器
【図１】
2007086919.tif 000018
【図２】
2007086919.tif 000019
【図３】
2007086919.tif 000020
【図４】
2007086919.tif 000021
【図５】
2007086919.tif 000022
【図６】
2007086919.tif 000023
【図７】
2007086919.tif 000024
【図８】
2007086919.tif 000025
【図９】
2007086919.tif 000026
【図１０】
2007086919.tif 000027
【図１１】
2007086919.tif 000028
【図１２】
2007086919.tif 000029
【図１３】
2007086919.tif 000030
【図１４】
2007086919.tif 000031
【図１５】
2007086919.tif 000032
【図１６】
2007086919.tif 000033