(57)【特許請求の範囲】
【請求項１】
有限要素法を使用した構造解析で得られるスカイライン行列を係数とする連立一次方程式の解を計算する装置であり、一次元配列で与えられる係数行列Ａ、該Ａの各列の該Ａにおける非ゼロ要素の上端の位置情報が格納された先頭アドレステーブルＮＰ及び右辺ベクトルＢを記憶する手段と、前記ＮＰの値により判定されるスカイライン行列の列の先頭が揃っていない場合に対して、Ｌ列（Ｌ＝２，３，４，５，６，７のいずれか）づつをまとめて計算処理する際に発生する無駄なゼロ要素による計算を減少させるように、スカイライン行列をブロックした範囲内でゼロ要素のみの列を削除するパッキング処理を行い、該パッキング処理が行われたブロックについてスカイライン解法演算処理を行う手段とを備えたことを特徴とする連立一次方程式に関する計算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、連立一次方程式の数値解を計算する装置に関わり、特に有限要素法を使用した構造解析で得られるスカイライン行列を係数とする行列の三角分解をする装置であり、数値シミュレーションを行う記憶階層システムを持つＲＩＳＣプロセッサを使用したワークステーション、超並列計算機の計算機などに関する。
【０００２】
【従来の技術】
従来の技術としては、小国  力編「行列計算ソフトウエア、ＷＳ、スーパーコン、並列計算機」（丸善）で論じられているスカイライン行列の改訂コレスキー分解を用いた方法がある。この方法は１行１列の内積計算処理を基本としている。
【０００３】
また、スカイライン行列をＬ＊Ｌ（Ｌ＝２，３，・・・）のセルに分割して、分解を行うパラレルスカイライン法、スカイライン行列をいくつかの列ごとにブロック化して、外部記憶装置に記憶しておき、必要なブロックのみを適宜主記憶装置に読み込んで分解を行うブロックスカイライン法がある。
【０００４】
一方、特願平０４−３１９７５６に記述されている連立一次方程式に関する計算装置では、スカイライン列の先頭がＬ個（Ｌ＝２．３．・・・，６）づつ揃ったスカイライン行列とそれ以外の一般的なスカイライン行列の場合に分けて処理することを特長としている。
【０００５】
【発明が解決しようとする課題】
記憶階層を持つシステムでは、記憶階層間のデータの入出力を少なくしてより高速な記憶装置（演算装置）での計算の比率を高めることが、計算の高速化に効果的であるので、前記のパラレルスカイライン法が有効である。パラレルスカイライン法を適用すると、たとえば、ワークステーションではもっとも高速な記憶装置であり計算装置であるレジスタに対する入出力の計算量に対する比率が減少するため、計算時間を短縮できる。パラレルスカイライン法を適用する場合、スカイライン行列のスカイライン列の先頭が揃っている場合にはゼロ要素による無駄な計算は必要ないが、一般的なスカイライン行列に対しては無駄なゼロ要素による計算が発生する。図６に例で示す。図６はスカイライン列の先頭が揃っていない一般的なスカイライン行列である。６０１の網掛け部分が無駄なゼロ要素計算となる。本例では、一度に消去する列幅Ｌが４の場合である。
【０００６】
本発明の目的は、スカイライン列の先頭が揃っていない一般的なスカイライン行列に対するパラレルスカイライン法において、無駄なゼロ要素による計算を減少する処理を装備した連立一次方程式に関する計算装置を提供することにある。
【０００７】
【課題を解決するための手段】
上記目的は、スカイライン行列において、なるべくスカイライン行列の要素を使用するように計算時にスカイライン行列の形状をブロック化した範囲で変更する装置を具備することにより達成される。
【０００８】
列幅は計算を通して計算機でのもっとも高い性能がでる列幅の使用が可能であり、また、同時にゼロ要素による無駄な計算の減少が可能である。記憶階層を持つ計算装置においては、無駄なゼロ要素の格納、及び記憶階層間の入出力を減少させて、計算の比率を高めることが可能となる。
【０００９】
【発明の実施の形態】
以下、本発明の一実施例について図面により説明する。
【００１０】
図１は、レジスタ（１０４）、キャッシュメモリ（１０３）、及び主記憶装置（１０２）からなる記憶階層を持つ記憶装置（１０５）に対して、主記憶装置（１０２）からキャッシュメモリ（１０３）に、キャッシュメモリ（１０３）の記憶容量に収まる容量にブロック化されたデータを転送する過程に、本発明の一実施例である、スカイライン係数行列（２０２）をＬ列づつまとめて計算する際に発生して無駄計算を引き起こすゼロ要素（６０１）を減少させるように形状をブロック化した範囲で変更する処理（以下パッキング処理と呼ぶ）を具現したパッキング処理部（１０９）とブロック制御部（１０８）、スカイライン解法演算処理部（１０７）及び、算術演算処理部（１０６）からなるパラレルスカイライン法解法装置（１１０）と、キーボード（１０１）からなる入力装置と、表示装置であるディスプレイ（１１１）を具備するパラレルスカイライン連立一次方程式解法装置の装置図を示す。
【００１１】
図２掲載の様式でキーボード（１０１）から入力した、一次元配列に格納された次元数Ｎのスカイライン係数行列（２０２）のデータは主記憶装置（１０２）上に記憶される。計算時に必要なデータは、図３掲載のようなキャッシュメモリの容量を超えない大きさに分割したブロック単位で、ブロック制御部（１０８）の制御に従い、主記憶装置（１０２）からキャッシュメモリ（１０３）に転送される。その際、ブロック内のスカイライン行列のデータはパッキング処理部（１０９）の制御に従い、第５図に示されるように列単位に圧縮される。そしてキャッシュメモリ（１０３）のデータはスカイライン解法演算処理部（１０７）の制御に従い、レジスタ（１０４）上で算術演算処理部（１０６）により必要なパラレルスカイライン法解法装置（１１０）の処理が施される。必要な処理が完了した時点で更新したデータはキャッシュメモリ（１０３）及び主記憶装置（１０２）に戻される。すべての計算が完了した後、ディスプレイ（１１１）に結果を出力する。
【００１２】
図２は、入力される連立一次方程式問題の一例である。次元数３３の連立一次方程式のスカイライン係数行列（２０２）は、一次元配列Ａに、Ａ（１）から順に矢印の向きにスカイライン列（２０３）の係数データを格納する。スカイライン列（２０３）は対角要素（２０１）から始まっているが、行列の途中で終わっているものがある。これは、スカイライン列（２０３）の定義されていない部分は０であるため、その部分の格納を省略しているためである。このように一般的にスカイライン列（２０３）の高さは不規則になるので、ｋ列目のスカイライン係数行列（２０２）の対角要素（２０１）が一次元配列Ａのどこにあるかという位置を示すポインタテーブルとして、配列ＮＰ（２０５）を定める。すなわち、入力される連立一次方程式問題は、Ａ（ＮＰ（Ｋ））がｋ列目の対角要素（２０１）を示すように、一次元配列Ａに連続して格納されている。また、（２０４）は入力される連立一次方程式問題の右辺ベクトルである。
【００１３】
図３は、スカイライン係数行列（２０２）をブロック１（３０１）、ブロック２（３０２）、ブロック３（３０３）、ブロック４（３０４）、ブロック５（３０５）、ブロック６（３０６）に６分割したブロック分割の例である。これらのブロックは、パラレルスカイライン法の処理で、実装されているキャッシュメモリ（１０３）の容量に収まるようにスカイライン係数行列（２０２）を分割したものである。これらのブロックは、ブロック制御部（１０８）の制御のもと、表３０７で示される順序で制御し、パラレルスカイライン法の処理を適用する。
【００１４】
図４は、図１で示したパッキング装置を具現する連立方程式解法装置におけるＰＡＤを示す。
【００１５】
連立一次方程式問題は、キーボード（１０１）から入力する（ステップ４０１）。連立方程式問題の入力データを図３で示した様にブロック１（３０１）からブロック６（３０６）まで６分割して制御する（ステップ４０２）。その際、図５で示すように、更新が完了し、参照されるブロック（５０１）にはデータを列単位に圧縮して格納し（ステップ４０３）、更新途中の値で参照されるブロック（５０２）でもデータを列単位に圧縮して格納する（ステップ４０４）。そして、スカイライン解法の制御に従い（ステップ４０５）、スカイライン解法演算処理部（１０７）が、更新が完了し、参照されるブロック（５０１）及び、更新途中の値で参照されるブロック（５０２）を使用して、更新するブロック（５０３）を処理する（ステップ４０６）。計算処理終了後、ディスプレイ（１１１）に結果を表示する（ステップ４０７）。
【００１６】
図５は、更新されるブロック（５０３）、更新が完了し、参照されるブロック（５０１）、更新途中の値で参照されるブロック（５０２）、にパッキング処理部（１０９）の制御のもと、算術演算処理部（１０６）でのパラレルスカイライン法の内積計算処理を施した場合の状況を表したものである。５０４が主記憶装置上のデータ格納のイメージである。この状態で、Ｌ列（Ｌ＝２，３，４，５，６，７）づつまとめて行う内積計算を適応すると、更新途中の値で参照されるブロック（５０２）、更新が完了し、参照されるブロック（５０１）内の、スカイライン列（２０３）が１列分定義されていない部分（５１０）には、内積計算をＬ列（Ｌ＝２，３，４，５，６，７）づつまとめて行う都合上、ゼロ要素を格納する。しかし、１列で内積計算する場合、スカイライン列（２０３）が１列分定義されていない部分（５１０）の内積は計算する必要がないため、この５１０のゼロ要素による内積計算および、５１０にゼロ要素を格納するのは、無駄な作業である。
【００１７】
そこで、この無駄を取り除くために、更新途中の値で参照されるブロック（５０２）、更新が完了し、参照されるブロック（５０１）内において、スカイライン列（２０３）が１列分定義されていない部分（５１０）を取り除いて、すなわち列単位に詰めてキャッシュメモリ（１０３）上の連続領域（５０９）に格納する。これにより、キャッシュメモリ（１０３）上の連続領域（５０９）では、列単位に詰めて格納されたスカイライン係数行列部分（５０７）以外の部分（５０８）だけにゼロ要素を格納すればよくなり、格納の無駄が削減される。また、Ｌ列（Ｌ＝２，３，４，５，６，７）づつまとめて行う内積計算でも、更新途中の値で参照されるブロック（５０２）、更新が完了し、参照されるブロック（５０１）内での、内積計算に必要な列だけが使用されることになり、ゼロ要素による無駄な計算が列単位で削減されることになる。さらに、ブロック内部の必要なスカイライン列（２０３）のみを使用することで、更新されるブロック（５０３）内で、内積計算結果により更新をする必要のあるデータ（５０５）と、更新の必要のない部分（５０６）とに分離することができ、更新されるブロック内（５０３）のすべての要素を更新する必要もなくなる。
【００１８】
そのうえ、キャッシュメモリ（１０３）上の連続領域（５０９）に詰めて格納する事で、主記憶装置（１０２）からキャッシュメモリ（１０３）間の、５１０部分の無駄なゼロ要素のデータ転送量を削減することも可能となる。
【００１９】
図６は、スカイライン係数行列（２０２）に対して４列づつまとめて計算処理する際に発生する、無駄計算を引き起こすゼロ要素（６０１）の一例である。
【００２０】
【発明の効果】
以上の説明から明らかなように、本発明によれば、スカイライン列の高さが揃っていないスカイライン行列に対してパラレルスカイライン法を適用したとき、無駄なゼロ要素計算を減少させる効果がある。また、記憶階層を具備する計算機では、ある記憶階層に記憶する無駄なデータ量を削減し、記憶階層間のデータの入出力を削減することを可能とする。
【００２１】
これらにより、従来の一行一列内積型計算と比較して求解ＣＰＵ時間が大幅に短縮するという性能上の効果がある。
【図面の簡単な説明】
【図１】本発明の一実施例である、スカイライン行列を部分的に変更して、無駄なゼロ要素計算を削減する処理装置を具備する連立一次方程式に関する装置図。
【図２】スカイライン係数行列ＡとそのＡの各スカイライン列の先頭アドレステーブルＮＰ、及び右辺ベクトルの例。
【図３】スカイライン行列のブロック分割例。
【図４】計算時に無駄なゼロ要素を削減を施した三角分解のＰＡＤ。
【図５】ブロック分割に対して、列単位でゼロ要素を削減して計算を行う三角分解の例。
【図６】無駄なゼロ要素計算が発生するスカイライン行列の例。
【図１】
0003694947.tif 000002
【図２】
0003694947.tif 000003
【図３】
0003694947.tif 000004
【図４】
0003694947.tif 000005
【図５】
0003694947.tif 000006
【図６】
0003694947.tif 000007