(57)【要約】【課題】ＳＩＭＤ（Single Instruction Multiple Data）命令を利用した効率的な求解を実現する。【解決手段】記憶部１１は、係数行列から値が０の要素を削除し、列数を削減する方向に圧縮した圧縮行列１を記憶する。演算部１２は、圧縮行列１のＵ番目の行（Ｕは１以上の整数）からＶ番目の行（ＶはＵより大きな整数）までの複数の行を含む行群を取得する。次に演算部１２は、行群の各行内での要素の並べ替えにより、係数行列のＵ番目の列からＶ番目の列までの列とは異なる列に属する要素に対応する行群内の第１要素を、圧縮行列１の同じ列に集約し、圧縮行列１を用いた演算において、行群内の列方向に連続する複数の第１要素それぞれに対する演算をＳＩＭＤ命令で実行する。【選択図】図１
2017130036.tif 000002
【特許請求の範囲】
【請求項１】
係数行列から値が０の要素を削除し、列数を削減する方向に圧縮した圧縮行列を記憶する記憶部と、
前記圧縮行列のＵ番目の行（Ｕは１以上の整数）からＶ番目の行（ＶはＵより大きな整数）までの複数の行を含む行群を取得し、前記行群の各行内での要素の並べ替えにより、前記係数行列のＵ番目の列からＶ番目の列までの列とは異なる列に属する要素に対応する前記行群内の第１要素を、前記圧縮行列の同じ列に集約し、前記圧縮行列を用いた演算において、前記行群内の列方向に連続する複数の第１要素それぞれに対する演算をＳＩＭＤ（Single Instruction Multiple Data）命令で実行する演算部と、
を有する情報処理装置。
【請求項２】
前記演算部は、前記並べ替えにおいて、前記係数行列のＵ番目の行からＶ番目の行までの各行において対角要素よりも右側にある要素に対応する、前記行群内の第２要素を、前記圧縮行列内の同じ列に集約し、前記圧縮行列を用いた演算において、前記行群内の列方向に連続する複数の第２要素それぞれに対する演算をＳＩＭＤ命令で実行する、
請求項１記載の情報処理装置。
【請求項３】
前記演算部は、前記圧縮行列を用いた演算において、ＳＩＭＤ命令を用いずに実行する演算より前に、ＳＩＭＤ命令による演算を実行する、
請求項１または２記載の情報処理装置。
【請求項４】
前記演算部は、前記並べ替えにおいて、前記係数行列のＵ番目の列からＶ番目の列までのいずれかの列に属する要素に対応する、前記行群内の第３要素を、前記圧縮行列の左または右の端に寄せて配置する、
請求項１乃至３のいずれかに記載の情報処理装置。
【請求項５】
コンピュータが、
係数行列から値が０の要素を削除し、列数を削減する方向に圧縮した圧縮行列を記憶する記憶部から、
前記圧縮行列のＵ番目の行（Ｕは１以上の整数）からＶ番目の行（ＶはＵより大きな整数）までの複数の行を含む行群を取得し、
前記行群内の各行内での要素の並べ替えにより、前記係数行列のＵ番目の列からＶ番目の列までの列とは異なる列に属する要素に対応する前記行群内の第１要素を、前記圧縮行列の同じ列に集約し、
前記圧縮行列を用いた演算において、前記行群内の列方向に連続する複数の第１要素それぞれに対する演算をＳＩＭＤ命令で実行する、
演算方法。
【請求項６】
コンピュータに、
係数行列から値が０の要素を削除し、列数を削減する方向に圧縮した圧縮行列を記憶する記憶部から、
前記圧縮行列のＵ番目の行（Ｕは１以上の整数）からＶ番目の行（ＶはＵより大きな整数）までの複数の行を含む行群を取得し、
前記行群内の各行内での要素の並べ替えにより、前記係数行列のＵ番目の列からＶ番目の列までの列とは異なる列に属する要素に対応する前記行群内の第１要素を、前記圧縮行列の同じ列に集約し、
前記圧縮行列を用いた演算において、前記行群内の列方向に連続する複数の第１要素それぞれに対する演算をＳＩＭＤ命令で実行する、
処理を実行させる演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、演算方法、および演算プログラムに関する。
【背景技術】
【０００２】
流体解析や構造解析などの数値シミュレーションにおいては、連立１次方程式を解く部分が実行時間の大半を占める場合が多い。よって、連立１次方程式の解を求める計算の高速化は非常に重要である。
【０００３】
連立方程式は、行列の計算式「Ａｘ＝ｂ」で表すことができる。Ａは係数行列であり、ｘ，ｂは列ベクトルである。一般に、数値シミュレーションに含まれる連立１次方程式中の係数行列Ａは、要素の大半は値が「０」である。このような行列は疎行列と呼ばれる。
【０００４】
係数行列が疎行列である連立１次方程式の解法には、疎行列に特化した解法アルゴリズムである反復法が用いられる。反復法による連立１次方程式の解法としては、例えばガウス・ザイデル（Gause-Seidel）法がある。
【０００５】
なお連立１次方程式の近似解の計算では、近似解が発散しにくい反復法を用いると並列演算の効率が低くなり、並列演算の効率が高い反復法を用いると近似解が発散する場合がある。そこで、発散を抑えつつ並列効率の向上を図る演算方法が考えられている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１５−１３５６２１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
近年のＧＰＵ（Graphics Processing Unit）、ＣＰＵ（Central Processing Unit）などのプロセッサは、いわゆるＳＩＭＤ（Single Instruction Multiple Data）命令を持つのが普通である。ＳＩＭＤ命令１個で実行できる演算数であるＳＩＭＤ長も、４〜８と大きくなる傾向にある。ゆえに、疎行列の格納方法も、そのような長ＳＩＭＤ向きのものが用いられることが多くなってきている。
【０００８】
疎行列である係数行列Ａのデータ構造としては、「０」以外の値を持つ非零要素の位置とその値のみを圧縮して格納したデータ構造が用いられる。例えば疎行列である係数行列から、値が「０」の要素が予め取り除かれる。このとき、残った要素は左に詰められる。これにより、係数行列の列数を大幅に削減できる。そして各要素の値は、行列の掛け算における列方向に並んだ複数の要素それぞれを用いた複数の乗算が一回のＳＩＭＤ命令で実行できるようにメモリに格納すれば、ＳＩＭＤ命令を有効に利用した行列の計算が可能となる。
【０００９】
しかし、ガウス・ザイデル法で連立１次方程式を解く場合、ＳＩＭＤ命令を有効に利用するのが難しい。すなわちガウス・ザイデル法では、計算の繰り返し回数をＫ（Ｋは１以上の整数）としたとき、Ｋ回目の計算において、複数の１次方程式が所定の順番で計算される。このとき、各１次方程式に含まれる数値の一部には、先にＫ回目の計算が実施された他の１次方程式の計算結果が代入される。そのため、ある１次方程式の計算は、その計算に用いる数値を求めるための他の１次方程式の計算と並列に実行することはできない。並列に実行することができない計算は、ＳＩＭＤ命令による同時実行もできない。そのため、ガウス・ザイデル法で連立１次方程式を解く計算処理において、ＳＩＭＤ命令が有効に利用されておらず、十分な高速化が図られていない。
【００１０】
１つの側面では、本件は、ＳＩＭＤ命令を利用した効率的な求解を実現することを目的とする。
【課題を解決するための手段】
【００１１】
１つの案では、記憶部と演算部とを有する情報処理装置が提供される。記憶部は、係数行列から値が０の要素を削除し、列数を削減する方向に圧縮した圧縮行列を記憶する。演算部は、圧縮行列のＵ番目の行（Ｕは１以上の整数）からＶ番目の行（ＶはＵより大きな整数）までの複数の行を含む行群を取得する。次に演算部は、行群の各行内での要素の並べ替えにより、係数行列のＵ番目の列からＶ番目の列までの列とは異なる列に属する要素に対応する行群内の第１要素を、圧縮行列の同じ列に集約し、圧縮行列を用いた演算において、行群内の列方向に連続する複数の第１要素それぞれに対する演算をＳＩＭＤ命令で実行する。
【発明の効果】
【００１２】
１態様によれば、ＳＩＭＤ命令を利用した効率的な求解が可能となる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施の形態に係る情報処理装置の機能構成例を示す図である。
【図２】第２の実施の形態のシステム構成例を示す図である。
【図３】管理ノードのハードウェアの一構成例を示す図である。
【図４】連立１次方程式を表す行列の積を示す図である。
【図５】係数行列の圧縮例を示す図である。
【図６】格納された要素のアクセス順の一例を示す図である。
【図７】ＳＩＭＤ命令により計算できる部分の一例を示す図である。
【図８】ガウス・ザイデル法による処理ルーチンの一例を示す図である。
【図９】管理ノードの機能を示すブロック図である。
【図１０】ＳＩＭＤ化処理の手順の一例を示すフローチャートである。
【図１１】圧縮行列作成処理の手順の一例を示すフローチャートである。
【図１２】非零要素数および非零要素数の最大値を求める処理の手順の一例を示すフローチャートである。
【図１３】部分ＳＩＭＤ化処理の手順の一例を示すフローチャートである。
【図１４】ｆｉｎｄ処理の手順の一例を示すフローチャートである。
【図１５】ｓｗａｐ処理の手順の一例を示すフローチャートである。
【図１６】圧縮行列の作成例を示す図である。
【図１７】要素の並べ替えの一例を示す図である。
【図１８】部分ＳＩＭＤ化の一例を示す図である。
【図１９】部分ＳＩＭＤ化後のＡｃｏｌの格納例を示す図である。
【図２０】解析実行時のアクセス例を示す図である。
【図２１】第３の実施の形態における並べ替えの例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
まず第１の実施の形態について説明する。
【００１５】
図１は、第１の実施の形態に係る情報処理装置の機能構成例を示す図である。情報処理装置１０は、連立１次方程式の求解を行う。情報処理装置１０は、例えばプロセッサ、メモリ、ストレージ装置などを備えたコンピュータである。情報処理装置１０は、複数のコンピュータを有するコンピュータシステムであってもよい。連立１次方程式は、計算式「Ａｘ＝ｂ」の行列の式で表される。Ａは係数行列であり、ｘ，ｂは列ベクトルである。係数行列Ａの要素の値と、ベクトルｂの要素の値とは、予め設定されており、情報処理装置１０は、計算式を満たすベクトルｘの各要素の値を算出する。なお係数行列Ａは、大多数の要素の値が「０」の疎行列である。
【００１６】
記憶部１１は、係数行列Ａから値が「０」の要素を削除し、列数を削減する方向（行方向）に圧縮した圧縮行列１を記憶する。また記憶部１１に、係数行列Ａやベクトルｂを記憶させてもよい。
【００１７】
演算部１２は、係数行列Ａを列数を削減する方向に圧縮する。例えば演算部１２は、係数行列Ａ内の値が「０」の要素を削除し、残された要素を行方向の左に寄せる。これにより係数行列Ａから列数を削減した圧縮行列１が生成される。図１の例では、Ｎ行×Ｎ列（Ｎは１以上の整数）の係数行列Ａが、Ｎ行×８列の圧縮行列１に圧縮されている。
【００１８】
圧縮行列１の各要素は、係数行列Ａ内の対応する要素の列位置（何番目の列か）に関連付けられている。図１の例では、圧縮行列の各要素の括弧内に、列位置を示している。圧縮行列１内の各要素と、その要素に対応する圧縮行列１内の要素の列位置との関係は、例えば圧縮行列１と同じサイズの行列（列位置行列）に設定しておくことができる。その場合、演算部１２は、係数行列Ａを圧縮する際に、圧縮行列１と列位置行列とを生成する。演算部１２は、生成した圧縮行列１と列位置行列とを記憶部１１に格納する。
【００１９】
さらに演算部１２は、圧縮行列１を用いて、連立１次方程式の解を求める。演算部１２は、求解を、例えばガウス・ザイデル法により行う。具体的には、演算部１２は、ベクトルｘの各要素に初期値を設定する。初期値は「０」などの所定の値でよい。次に演算部１２は、圧縮行列１を所定数の行（例えば４行）を含む複数の行群に分割する。そして演算部１２は、上位の行群から順に積和演算を行う。図１の例では、演算部１２は、まず１行目〜４行目の行群の積和演算を行い、次に５行目〜８行目の行群の積和演算を行い、次に９行目〜１２行目の行群の積和演算を行う。以後同様に、上位の行群から順に積和演算が行われる。
【００２０】
演算部１２は、反復法で解を求める。その場合、圧縮行列１の各行の積和演算では、ベクトルｘ内の同じ行の要素の値を未知数とし、その未知数を求める計算が行われる。例えば圧縮行列１の９行目の要素を用いた積和演算を行うことで、ベクトルｘの９行目の要素の値が算出される。そして、ベクトルｘの各要素の値は、新たな値が算出されるごとに更新される。このようにして、ベクトルｘの各要素の値を繰り返し求め、要素の値が収束したとき（再計算しても同じ値が求まるとき）、その時点でのベクトルｘの各要素の値が、連立１次方程式の解となる。
【００２１】
なお、ガウス・ザイデル法では、繰り返し実行する演算の各サイクルにおいて、係数行列Ａの１行目から順にベクトルｘとの積和演算を行うこととなる。そして、Ｘ行目（Ｘは１以上の整数）の積和演算を行う場合、列ベクトルであるベクトルｘの１行目からＸ−１行目までの各要素の値として、同じサイクル内で先に計算した値が用いられる。なお、Ｘ行目の積和演算では、ベクトルｘのＸ行目の要素の値は未知数である。またベクトルｘのＸ＋１行目から最後の行までの各要素の値としては、前回のサイクルで計算した値が用いられる。
【００２２】
このようなガウス・ザイデル法による求解を、行群ごとに効率的に行うため、演算部１２は、記憶部１１から圧縮行列１内の行群を取得する。次に演算部１２は、行群の各行内での要素の並べ替えにより、ガウス・ザイデル法の制約の下、並列実行可能な要素を共通の列に集約する。例えば演算部１２が、圧縮行列１のＵ番目の行（Ｕは１以上の整数）からＶ番目の行（ＶはＵより大きな整数）までの複数の行を含む行群を取得したものとする。このとき演算部１２は、取得した行群の各行内での要素の並べ替えにより、係数行列ＡのＵ番目の列からＶ番目の列までの列とは異なる列に属する要素に対応する行群内の要素を、圧縮行列１の同じ列に集約する。
【００２３】
そして演算部１２は、圧縮行列１を用いた演算において、行群内の列方向に連続する複数の第１要素それぞれに対する演算をＳＩＭＤ命令で実行する。例えば図１に示す９行目から１２行目の行群において、右側４列に属する要素は、係数行列Ａにおいて９列目から１２列目以外の列位置の要素に対応する。そのため、右側４列に属する要素に対する、行列の計算の際の列ベクトル内の乗算相手の要素は、既に値が求められている。従って、行群の右側４列内の要素に対する演算は並列実行可能である。そこで、演算部１２は、行群の右側４列の要素について、列ごとに４ＳＩＭＤ命令によって同時に演算処理を実行する。なお、４ＳＩＭＤ命令とは、演算適用対象の要素数（ＳＩＭＤ長）が４つのＳＩＭＤ命令である。以下同様に、ＳＩＭＤ命令の前に付けた数値により、そのＳＩＭＤ命令における演算適用対象の要素数を示すものとする。
【００２４】
これにより、ＳＩＭＤ命令を有効に利用し、求解を効率的に実行することが可能となる。
演算部１２は、要素の並べ替えにおいて、係数行列のＵ番目の行からＶ番目の行までの各行において対角要素よりも右側にある要素に対応する、行群内の要素を、圧縮行列１内の同じ列に集約してもよい。例えば、係数行列Ａの９行目の行であれば、その行内の９列目の要素が対角要素である。そして、９行目の行の１０列目以降の各要素が、対角要素よりも右側にある要素となる。係数行列Ａの各行において対角要素よりも右側にある要素に対する行列演算における、乗算相手のベクトルｘ内の要素の値は、前のサイクルで既に算出された値である。そのため、対角要素よりも右側にある複数の要素の演算は、同時に実行可能である。そこで演算部１２は、係数行列Ａにおいて対角要素よりも右側にある要素に対応する圧縮行列１内の要素が行群内の列方向に連続するとき、圧縮行列１を用いた演算において、それらの連続する要素それぞれに対する演算を、ＳＩＭＤ命令で実行する。
【００２５】
例えば、図１に示す圧縮行列１の９列目から１２列目は、要素の並べ替えの結果、９行目と１０行目の３列目に、係数行列Ａにおいて１１列目に配置されている要素に対応する２つの要素が連続している。この２つの要素は同時実行可能であり、演算部１２は、これらの要素を用いた演算を、２ＳＩＭＤ命令で実行する。また９行目から１１行目の４列目に、係数行列Ａにおいて１２列目に配置されている要素に対応する３つの要素が連続している。この３つの要素は同時実行可能であり、演算部１２は、これらの要素を用いた演算を、３ＳＩＭＤ命令で実行する。例えば２ＳＩＭＤ命令は、４要素のうちの２つの要素に対して例外を起こさない値（例えば１．０）をセットしておいて４ＳＩＭＤとして演算し、その２つの要素の演算結果は使用しないことにより実現できる。
【００２６】
なお演算部１２は、圧縮行列１を用いた演算を行う場合、ＳＩＭＤ命令を用いずに実行する演算より前に、ＳＩＭＤ命令による演算を実行する。その後、演算部１２は、ＳＩＭＤ命令を用いずに実行する演算を、上の行の要素から順に実行する。これにより、ガウス・ザイデル法に従った演算が適切に実行される。
【００２７】
また演算部１２は、要素の並べ替えにおいて、他の要素への演算と並列実行できない要素を、圧縮行列１の行方向の右または左に寄せてもよい。例えば、圧縮行列１のＵ番目の行からＶ番目の行までの複数の行を含む行群を取得したものとする。この場合、演算部１２は、並べ替えにおいて、係数行列のＵ番目の列からＶ番目の列までのいずれかの列に属する要素に対応する、行群内の要素を、圧縮行列１の左または右の端に寄せて配置する。これにより、ＳＩＭＤ命令を実行可能な連続要素を増やすことができる可能性がある。その結果、ＳＩＭＤ命令を用いた処理の効率化を促進させることができる。
【００２８】
なお、演算部１２は、例えば情報処理装置１０が有するプロセッサにより実現することができる。また、記憶部１１は、例えば情報処理装置１０が有するメモリまたはストレージ装置により実現することができる。
【００２９】
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、流体解析や構造解析などの数値シミュレーションにおける連立１次方程式の計算を、ＳＩＭＤ命令を有効に用いて効率的に実施するものである。
【００３０】
図２は、第２の実施の形態のシステム構成例を示す図である。図２の例では、複数の計算ノード３１，３２，・・・、管理ノード１００、および端末装置３０が、ネットワーク２０を介して接続されている。複数の計算ノード３１，３２，・・・は、数値シミュレーションを並列計算するコンピュータ群である。管理ノード１００は、各計算ノード３１，３２，・・・へのジョブの投入などを管理するコンピュータである。端末装置３０は、管理ノード１００に対してユーザの指示を入力するコンピュータである。
【００３１】
図３は、管理ノードのハードウェアの一構成例を示す図である。管理ノード１００は、プロセッサ１０１によって装置全体が制御されている。プロセッサ１０１には、バス１０９を介してメモリ１０２と複数の周辺機器が接続されている。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ、ＭＰＵ（Micro Processing Unit）、またはＤＳＰ（Digital Signal Processor）である。プロセッサ１０１がプログラムを実行することで実現する機能の少なくとも一部を、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現してもよい。
【００３２】
メモリ１０２は、管理ノード１００の主記憶装置として使用される。メモリ１０２には、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０２には、プロセッサ１０１による処理に必要な各種データが格納される。メモリ１０２としては、例えばＲＡＭ（Random Access Memory）などの揮発性の半導体記憶装置が使用される。
【００３３】
バス１０９に接続されている周辺機器としては、ストレージ装置１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、機器接続インタフェース１０７およびネットワークインタフェース１０８がある。
【００３４】
ストレージ装置１０３は、内蔵した記憶媒体に対して、電気的または磁気的にデータの書き込みおよび読み出しを行う。ストレージ装置１０３は、コンピュータの補助記憶装置として使用される。ストレージ装置１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、ストレージ装置１０３としては、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）を使用することができる。
【００３５】
グラフィック処理装置１０４には、モニタ２１が接続されている。グラフィック処理装置１０４は、プロセッサ１０１からの命令に従って、画像をモニタ２１の画面に表示させる。モニタ２１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００３６】
入力インタフェース１０５には、キーボード２２とマウス２３とが接続されている。入力インタフェース１０５は、キーボード２２やマウス２３から送られてくる信号をプロセッサ１０１に送信する。なお、マウス２３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００３７】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク２４に記録されたデータの読み取りを行う。光ディスク２４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００３８】
機器接続インタフェース１０７は、管理ノード１００に周辺機器を接続するための通信インタフェースである。例えば機器接続インタフェース１０７には、メモリ装置２５やメモリリーダライタ２６を接続することができる。メモリ装置２５は、機器接続インタフェース１０７との通信機能を搭載した記録媒体である。メモリリーダライタ２６は、メモリカード２７へのデータの書き込み、またはメモリカード２７からのデータの読み出しを行う装置である。メモリカード２７は、カード型の記録媒体である。
【００３９】
ネットワークインタフェース１０８は、ネットワーク２０に接続されている。ネットワークインタフェース１０８は、ネットワーク２０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００４０】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお端末装置３０、および計算ノード３１，３２，・・・も、管理ノード１００と同様のハードウェアにより実現することができる。また、第１の実施の形態に示した情報処理装置１０も、図３に示した管理ノード１００と同様のハードウェアにより実現することができる。
【００４１】
管理ノード１００は、例えばコンピュータ読み取り可能な記録媒体に記録されたプログラムを実行することにより、第２の実施の形態の処理機能を実現する。管理ノード１００に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、管理ノード１００に実行させるプログラムをストレージ装置１０３に格納しておくことができる。プロセッサ１０１は、ストレージ装置１０３内のプログラムの少なくとも一部をメモリ１０２にロードし、プログラムを実行する。また管理ノード１００に実行させるプログラムを、光ディスク２４、メモリ装置２５、メモリカード２７などの可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えばプロセッサ１０１からの制御により、ストレージ装置１０３にインストールされた後、実行可能となる。またプロセッサ１０１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００４２】
次に連立１次方程式の解法について、詳細に説明する。前述のように連立１次方程式は、「Ａｘ＝ｂ」という行列の積で表すことができる。
図４は、連立１次方程式を表す行列の積を示す図である。図４の例では、８つの１次方程式を行列の積「Ａｘ＝ｂ」で表している。係数行列Ａは、８行×８列の正方行列である。係数行列Ａ内の各要素は、所定の値が設定された係数である。ベクトルｘは、８つの未知数を要素として含む列ベクトルである。ベクトルｂは、所定の値が要素として設定された列ベクトルである。
【００４３】
数値シミュレーションにおいては連立１次方程式の解を求める場合、係数行列Ａは疎行列であることが多い。図４の例では、係数行列Ａの各行の８つの要素のうち、「０」以外の値が設定された非零要素は、１つの行当たり３つである。このような疎行列は、計算を効率的に行うため、値が「０」の要素を除外することで圧縮される。
【００４４】
図５は、係数行列の圧縮例を示す図である。図５において、係数行列Ａの各要素を矩形で表している。矩形内には、各要素の値が設定されている。なお矩形内に数字の書いてない要素は、値が「０」の要素である。
【００４５】
各行から値が「０」の要素が除外され、各要素の位置が左に詰められる。また計算ノード３１，３２，・・・のプロセッサの最大のＳＩＭＤ長が４ＳＩＭＤであれば、係数行列Ａの複数の行が、４行単位でまとめられる。すると、最初の４行と次の４行とが、それぞれ４行×３列の行列に圧縮される。圧縮された各行列が、メモリに格納される。
【００４６】
なお、図３、図４に示した例では、元の係数行列Ａ中の各行の非零要素数がすべて３であるが、一般には、各行の非零要素数の最大値ｍ（ｍは１以上の整数）が求められ、４行×ｍ列の行列に圧縮して格納される。
【００４７】
圧縮後の行列を格納する際には、列方向に連続する要素を続けて読み出せるような配列で、メモリに格納される。
図６は、格納された要素のアクセス順の一例を示す図である。図６では、要素へのアクセスの順番を矢印で示している。すなわち、係数行列Ａにおける値が「０」以外の要素をメモリに格納する際に、図６に示すアクセス順となるように要素を並べてメモリに格納する。
【００４８】
このとき、「Ａｘ＝ｂ」におけるベクトルｘの要素のうち、既に値が求まっている要素を用いた積和演算は、ＳＩＭＤ命令により効率化することができる。
図７は、ＳＩＭＤ命令により計算できる部分の一例を示す図である。図７の例では、疎行列である８×８の係数行列Ａと、ベクトルｘ＝（−１，−２，−３，−４，−５，−６，−７，−８）Tと積の最初の４要素の計算例である。行列の積は、係数行列Ａの非零要素と対応するｘの要素との積和となる。このような積和計算を、ＳＩＭＤ長が４のＣＰＵを用いて実効すれば、破線で囲んだ部分のデータのロードおよび演算がＳＩＭＤ命令で実行できる。すなわち、積和演算を同時に４個ずつ実行できる。すなわち、ＳＩＭＤ命令により、行列とベクトルの積４行分を同時に行うことができる。
【００４９】
なお、疎行列の非零要素を行方向に連続格納する方法も考えられるが、各行の非零要素
数がＳＩＭＤ長の整数倍（この場合は４の倍数）であるとは限らない。整数倍でない場合は、ＳＩＭＤ化できない部分が生じ、ＳＩＭＤ命令を効果的に使えない。
【００５０】
図７に示したようなＳＩＭＤ命令による演算は、係数行列の各行の計算が独立に行える。しかし、反復法アルゴリズムによっては、各行が独立に行えない場合がある。例えばガウス・ザイデル法の場合は各行の計算の実行順が決まっている。
【００５１】
図８は、ガウス・ザイデル法による処理ルーチンの一例を示す図である。図８には、ガウス・ザイデル法による処理ルーチン４０を、疑似コードで表している。処理ルーチン４０には、順方向ループ４１と逆方向ループ４２とが含まれる。処理ルーチン４０において、ループ処理を示すｆｏｒ文の構文はＣ言語と同じである。ｆｏｒ文の括弧内に、セミコロンで区切って、カウンタ変数の初期化処理、ループの継続条件、およびカウンタ変数の更新処理が記載されている。
【００５２】
処理ルーチン４０において、ｎは係数行列の行数である。ｍは１行あたりの非零要素数の最大値である。colind[]は、非零要素の列位置を格納している配列である。「*」は乗算を示す。例えばｋ行目（ｋは１以上の整数）の非零要素の列位置が、「１，３，８，・・・」である場合、
colind[k*m+1]=1
colind[k*m+2]=3
colind[k*m+3]=8
…
である。変数ｉは、圧縮して得られた行列のうちの、計算対象の行番号を表している。ｘ［］は、ベクトルｘの要素を格納している配列である。例えばｘ［１］は、ベクトルｘの１番目の要素の値を表している。ａｖａｌ［］は、圧縮して得られた行列の要素を格納している配列である。復号代入演算子「−＝」は、右辺の変数の値から左辺の計算結果を減算し、右辺の変数に代入することを示している。
【００５３】
このような処理ルーチン４０において「ｉ＝ｋ」のときはｋ行目の処理をしていることに相当し、ベクトルｘのｋ番目の要素ｘ［ｋ］の値が定義される。今、順方向ループ４１において、ｋ〜ｋ＋３行目の４行の計算について考える。
【００５４】
ｋ行目の処理に関しては、ガウス・ザイデル法において、参照するｘ［ｋ＋１］，ｘ［ｋ＋２］，ｘ［ｋ＋３］の値は、繰り返し処理における前回の計算で得られた値でよい。そして、ｋ行目の処理によりｘ［ｋ］が定義される。このｘ［ｋ］は、ｋ＋１〜ｋ＋３行目の処理でｘ［ｋ］が参照される。そのため、ｋ＋１〜ｋ＋３行目の各行のうち、ｋ列目に非零要素がある行の計算は、ｋ行目の計算と並列実行はできない。
【００５５】
同様に、ｋ＋１行目の処理でｘ［ｋ＋１］が定義され、ｋ，ｋ＋２，ｋ＋３行目の処理でｘ［ｋ＋１］が参照される。そのため、ｋ＋２，ｋ＋３行目の各行のうち、ｋ＋１列目に非零要素がある行の計算は、ｋ＋１行目の計算と並列実行はできない。
【００５６】
このように、各行における非零要素がある列の位置により、その行の計算と並列実行できない行が特定される。ここで、係数行列が疎行列の場合、ある程度離れた行同士は、同じ列位置に非零要素を持たず独立に計算を行えることが多い。このような特徴を利用して、処理を効率化することが可能である。例えば、管理ノード１００が、行列全体をスキャンして、独立に処理できる行が連続となるように疎行列の行を並び替え、連続する行が独立に処理できるようにする。これにより、連続する数行（例えば４行）の行列の計算を、並列で実行可能となる。
【００５７】
しかし、行の並べ替えによる処理の効率化には以下の問題がある。
・行列を並び替えるコストが要る。
・元の計算順序を大きく変えてしまうことで生じる演算誤差のために、行を並び替える前に比べて反復回数が増え、解が求まるまでの時間が長くなることが多い。
・データのアクセス順序も変わってしまい、データローカリティが悪くなることが多い。
【００５８】
そこで、第２の実施の形態では、管理ノード１００は、行を並び替える代わりに、各行内の非零要素の順番を変える。そして管理ノード１００は、連続するＮ行をＳＩＭＤ化可能な部分（つまりＮ行を同時に実行できる部分）とそうでない部分とに分離し、前者に対してはＳＩＭＤ命令を用いて同時実行する。このようにＳＩＭＤ命令を有効に利用することで、高速処理が可能となる。なお、非零要素の順番の並び替えは、行の並び替えに比べて処理コストは小さいため、処理の効率化が図れる。
【００５９】
行の並び替えと異なり、行内の非零要素の順番の入れ替えによる計算順序の変更は、局所的である。そのため、反復回数やデータローカリティが悪化する可能性は、行の並び替えに比べて非常に低くなる。実際には、行内の非零要素の順番の入れ替えにより、反復回数やデータローカリティが悪化することはほとんどない。
【００６０】
次に、各行内の非零要素の順番を変えてシミュレーションを実行する場合の管理ノード１００の機能について説明する。
図９は、管理ノードの機能を示すブロック図である。管理ノード１００は、記憶部１１０、ＳＩＭＤ化部１２０、およびシミュレーション指示部１３０を有する。
【００６１】
記憶部１１０は、シミュレーションの条件に関する情報を記憶する。例えば記憶部１１０には、図４に示した係数行列、ベクトルｂなどが記憶される。また記憶部１１０には、図５に示したように、圧縮後の行列も記憶される。
【００６２】
ＳＩＭＤ化部１２０は、シミュレーションにおいて実行する行列計算のＳＩＭＤ化を行う。すなわちＳＩＭＤ化部１２０は、処理の効率化が図れるように、係数行列の圧縮や、行内の非零要素の順番の入れ替えを行う。
【００６３】
シミュレーション指示部１３０は、最適化後の係数行列を用いたシミュレーションを、計算ノード３１，３２，・・・に指示する。
なお、図９に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。また、図９に示した各要素の機能は、例えば、その要素に対応するプログラムモジュールをコンピュータに実行させることで実現することができる。
【００６４】
次に、ＳＩＭＤ化部１２０によるＳＩＭＤ化処理について詳細に説明する。
図１０は、ＳＩＭＤ化処理の手順の一例を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。
【００６５】
［ステップＳ１０１］ＳＩＭＤ化部１２０は、係数行列の行数をＮに設定する。またＳＩＭＤ化部１２０は、Ｎ行Ｎ列の係数行列をＡとする。
［ステップＳ１０２］ＳＩＭＤ化部１２０は、行数ＮとＮ行Ｎ列の係数行列Ａとに基づいて、それを圧縮したＮ行Ｌ列（ＬはＮ以下の整数）の行列を作成する。圧縮とは、図５に示したように、各行の値が「０」の要素を削除し、非零要素を左に寄せる処理である。圧縮処理で生成される行列を、以下「圧縮行列」と呼ぶ。第２の実施の形態では、圧縮行列の作成処理により、行列「Ａｃｏｌ」と行列「Ａｖａｌ」とが生成される。Ａｃｏｌは、係数行列の各行における非零要素の位置（何番目の列か）を示す行列である。Ａｖａｌは、係数行列の各行における非零要素の値を示す行列である。これらの２つの行列（ＡｃｏｌとＡｖａｌ）が、圧縮行列である。圧縮行列の作成処理の詳細は後述する（図１１参照）。
【００６６】
［ステップＳ１０３］ＳＩＭＤ化部１２０は、ＳＩＭＤ化に用いる変数の初期値を設定する。例えばＳＩＭＤ化部１２０は、変数Ｍ（Ｍは１以上の整数）に、一度に部分ＳＩＭＤ化する行数を設定する。例えば４行単位で部分ＳＩＭＤ化を行う場合、Ｍ＝４である。またＳＩＭＤ化部１２０は、ｓｔａｒｔＲｏｗに、非零要素の順番の入れ替えを最初に実施する行の初期値を設定する。図１０の例ではｓｔａｒｔＲｏｗの初期値は「１」である。すなわち、１行目から順に、非零要素の順番の入れ替えが行われる。さらにＳＩＭＤ化部１２０は、ｅｎｄＲｏｗに変数Ｍの値を設定する。
【００６７】
［ステップＳ１０４］ＳＩＭＤ化部１２０は、ｓｔａｒｔＲｏｗで示される行から、ｅｎｄＲｏｗで示される行数分の複数の行をＳＩＭＤ化する。このＳＩＭＤ化では、複数の行の一部の列がＳＩＭＤ化される。このようなＳＩＭＤ化を部分ＳＩＭＤ化と呼ぶ。この部分ＳＩＭＤ化処理の詳細は後述する（図１３参照）。
【００６８】
［ステップＳ１０５］ＳＩＭＤ化部１２０は、ｓｔａｒｔＲｏｗの値にＭを加算し、新たにｓｔａｒｔＲｏｗに設定する。またＳＩＭＤ化部１２０は、ｅｎｄＲｏｗの値にＭを加算し、新たにｅｎｄＲｏｗに設定する。
【００６９】
［ステップＳ１０６］ＳＩＭＤ化部１２０は、ｓｔａｒｔＲｏｗの値が、係数行列の行数Ｎより大きいか否かを判断する。ｓｔａｒｔＲｏｗ値がＮ以下であれば、処理がステップＳ１０４に進められる。ｓｔａｒｔＲｏｗ値がＮより大きければ、ＳＩＭＤ化処理が終了する。
【００７０】
このようにして、Ｎ行Ｎ列の係数行列がＮ行Ｌ列に圧縮され、Ｎ行Ｌ列の圧縮行列がＭ行ずつに分けて、部分ＳＩＭＤ化が施される。
次に、圧縮行列の作成処理について詳細に説明する。
【００７１】
図１１は、圧縮行列作成処理の手順の一例を示すフローチャートである。以下、図１１に示す処理をステップ番号に沿って説明する。なお、圧縮行列作成処理では、Ｒｏｗ（１≦Ｒｏｗ≦Ｎ）は、係数行列Ａ（Ｎ行Ｎ列）、行列Ｎｃ（Ｎ行１列）、行列Ａｃｏｌ（Ｎ行Ｌ列）、行列Ａｖａｌ（Ｎ行Ｌ列）それぞれ内の行を、上から何行目なのかで示す変数である。Ｃｏｌ（１≦Ｃｏｌ≦Ｎ）は、行列Ａ（Ｎ行Ｎ列）中の列を、左から何列目なのかで示す変数である。ｊおよびｋ（１≦ｊ，ｋ≦Ｌ）は、行列Ａｃｏｌ（Ｎ行Ｌ列）、行列Ａｖａｌ（Ｎ行Ｌ列）内の列を、左から何列目なのかで示す変数である。
【００７２】
［ステップＳ１１１］ＳＩＭＤ化部１２０は、Ｎ行１列の行列Ｎｃを生成する。
［ステップＳ１１２］ＳＩＭＤ化部１２０は、係数行列Ａの各行の非零要素数、および非零要素数の最大値Ｌを求める。なおＳＩＭＤ化部１２０は、係数行列Ａの各行の非零要素数を、行列Ｎｃに格納する。この処理の詳細は後述する（図１２参照）。
【００７３】
［ステップＳ１１３］ＳＩＭＤ化部１２０は、非零要素の列位置を格納するためのＮ行Ｌ列の行列Ａｃｏｌを生成し、すべての要素を「０」に初期化する。またＳＩＭＤ化部１２０は、非零要素の値を格納するためのＮ行Ｌ列の行列Ａｖａｌを生成し、すべての要素を「０」に初期化する。
【００７４】
［ステップＳ１１４］ＳＩＭＤ化部１２０は、Ｒｏｗに「１」を設定する。
［ステップＳ１１５］ＳＩＭＤ化部１２０は、ｊに「１」を設定する。
［ステップＳ１１６］ＳＩＭＤ化部１２０は、Ａｃｏｌ（Ｒｏｗ，ｊ）に、係数行列ＡのＲｏｗ行目の左からｊ番目の非零要素の列位置を設定する。またＳＩＭＤ化部１２０は、Ａｖａｌ（Ｒｏｗ，ｊ）に、係数行列ＡのＲｏｗ行目の左からｊ番目の非零要素の値を設定する。
【００７５】
［ステップＳ１１７］ＳＩＭＤ化部１２０は、ｊに「１」を加算する。
［ステップＳ１１８］ＳＩＭＤ化部１２０は、ｊの値がＮｃ（Ｒｏｗ）より大きいか否かを判断する。Ｎｃ（Ｒｏｗ）は、係数行列ＡのＲｏｗ行目の行に含まれる非零要素の数である。ｊの値がＮｃ（Ｒｏｗ）より大きい場合、処理がステップＳ１１９に進められる。ｊの値がＮｃ（Ｒｏｗ）以下であれば、処理がステップＳ１１６に進められる。
【００７６】
［ステップＳ１１９］ＳＩＭＤ化部１２０は、Ｒｏｗの値に「１」を加算する。
［ステップＳ１２０］ＳＩＭＤ化部１２０は、Ｒｏｗの値が係数行列Ａの行数Ｎより大きいか否かを判断する。Ｒｏｗの値が行数Ｎより大きい場合、処理がステップＳ１２１に進められる。Ｒｏｗの値が係数行列Ａの行数Ｎ以下であれば、処理がステップＳ１１５に進められる。
【００７７】
以上のステップＳ１１４〜Ｓ１２０の処理により、係数行列Ａの非零要素の列位置がＡｃｏｌに設定され、非零要素の値がＡｖａｌに設定される。
［ステップＳ１２１］ＳＩＭＤ化部１２０は、行列Ｎｃをメモリに保存する。そして、ＳＩＭＤ化部１２０は、圧縮行列作成処理の呼出元に、各行の非零要素数のうちの最大値Ｌ、Ａｃｏｌ、およびＡｖａｌを、処理の呼出元への戻り値として出力する。
【００７８】
このようにして生成されたＡｃｏｌとＡｖａｌとにより、係数行列Ａを圧縮した圧縮行列が表される。すなわち、Ａｖａｌは、係数行列Ａ内の値が「０」の要素を削除し、その他の非零要素を左に寄せた行列を表している。Ａｃｏｌの各要素は、Ａｖａｌ内の同じ行および同じ列にある要素が、係数行列Ａにおける何列目の要素であったのかを示している。
【００７９】
次に、各行の非零要素数と非零要素数の最大値とを求める処理について詳細に説明する。
図１２は、非零要素数および非零要素数の最大値を求める処理の手順の一例を示すフローチャートである。以下、図１２に示す処理をステップ番号に沿って説明する。
【００８０】
［ステップＳ１２１］ＳＩＭＤ化部１２０は、最大値Ｌに初期値「０」を設定する。またＳＩＭＤ化部１２０は、Ｒｏｗに初期値「１」を設定する。
［ステップＳ１２２］ＳＩＭＤ化部１２０は、係数行列ＡのＲｏｗ行目の非零要素の数を計数し、Ｎｃ（Ｒｏｗ）に設定する。
【００８１】
［ステップＳ１２３］ＳＩＭＤ化部１２０は、ステップＳ１２２の係数結果を示すＮｃ（Ｒｏｗ）が、現在の最大値Ｌよりも大きいか否かを判断する。最大値ＬよりもＮｃ（Ｒｏｗ）が大きければ、処理がステップＳ１２４に進められる。Ｎｃ（Ｒｏｗ）が最大値Ｌ以下であれば、処理がステップＳ１２５に進められる。
【００８２】
［ステップＳ１２４］ＳＩＭＤ化部１２０は、Ｎｃ（Ｒｏｗ）の値を最大値Ｌに設定する。
［ステップＳ１２５］ＳＩＭＤ化部１２０は、Ｒｏｗの値に「１」を加算し、新たにＲｏｗに設定する。
【００８３】
［ステップＳ１２６］ＳＩＭＤ化部１２０は、Ｒｏｗが、係数行列Ａの行数Ｎより大きいか否かを判断する。Ｒｏｗが行数Ｎより大きければ、処理の戻り値として最大値Ｌを出力し、最大値Ｌを求める処理が終了する。Ｒｏｗが行数Ｎ以下であれば、処理がステップＳ１２２に進められる。
【００８４】
このようにして、係数行列Ａの各行の非零要素数と非零要素数の最大値Ｌとが得られる。
次に、部分ＳＩＭＤ化処理について詳細に説明する。
【００８５】
図１３は、部分ＳＩＭＤ化処理の手順の一例を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。
［ステップＳ１３１］ＳＩＭＤ化部１２０は、ｓｔａｒｔＲｏｗの値をＲｏｗに設定する。
【００８６】
［ステップＳ１３２］ＳＩＭＤ化部１２０は、Ｒｏｗの値をＣｏｌに設定し、ｋに「１」を設定する。
［ステップＳ１３３］ＳＩＭＤ化部１２０は、ｆｉｎｄ処理を実行する。ｆｉｎｄ処理は、係数行列におけるＲｏｗ行Ｃｏｌ列の非零要素の列位置が、行列ＡｃｏｌのＲｏｗ行目の行の何番目の要素（列）に示されているかを探索する処理である。すなわち、「Ａｃｏｌ（Ｒｏｗ，ｊ）＝＝Ｃｏｌ」を満たすｊが探索される。ｆｉｎｄ処理の詳細は後述する（図１４参照）。
【００８７】
ステップＳ１３２において、ＲｏｗとＣｏｌとの値を同じにしているため、ステップＳ１３３では見つけ出されるｊは、係数行列Ａにおける対角要素が、行列ＡｃｏｌのＲｏｗ行目のどこにあるのかを示すことになる。なお、「Ａｃｏｌ（Ｒｏｗ，ｊ）＝＝Ｃｏｌ」を満たすｊが存在しない場合、ｊには「−１」が設定される。
【００８８】
［ステップＳ１３４］ＳＩＭＤ化部１２０は、ｆｉｎｄ処理で得られたｊが、０より大きく、かつｋと異なるという条件を満たすか否かを判断する。当該条件が満たされる場合、処理がステップＳ１３５に進められる。当該条件が満たされない場合、処理がステップＳ１３６に進められる。
【００８９】
なお、ステップＳ１３４では、ｊがｋと異なるという条件があり、この条件を満たさなければ次のステップＳ１３５の処理はスキップされる。これは、ｊがｋと等しい場合は、ステップＳ１３５におけるｓｗａｐ処理による値の交換が不要なためである。
【００９０】
［ステップＳ１３５］ＳＩＭＤ化部１２０は、ｓｗａｐ処理を実行する。ｓｗａｐ処理は、Ａｃｏｌ（Ｒｏｗ，ｋ）とＡｃｏｌ（Ｒｏｗ，ｊ）の値を交換し、Ａｖａｌ（Ｒｏｗ，ｋ）とＡｖａｌ（Ｒｏｗ，ｊ）の値を交換する処理である。この段階ではｋ＝１であるため、ステップＳ１３５のｓｗａｐ処理により、係数行列ＡにおけるＲｏｗ行目の行の対角要素が、圧縮行列（Ａｃｏｌ，Ａｃｏｌ）の先頭の列に移動する。ｓｗａｐ処理の詳細は後述する（図１５参照）。
【００９１】
［ステップＳ１３６］ＳＩＭＤ化部１２０は、ｋに「２」を設定し、ｓｔａｒｔＲｏｗの値をＣｏｌに設定する。
［ステップＳ１３７］ＳＩＭＤ化部１２０は、ＣｏｌとＲｏｗとの値が等しいか否かを判断する。ＣｏｌとＲｏｗとの値が等しい場合とは、係数行列ＡのＲｏｗ行Ｃｏｌ列の要素が対角要素の場合である。対角要素に対しては、ステップＳ１３２〜Ｓ１３５により、並び替えの処理が実施済みである。そこで、ＣｏｌとＲｏｗとの値が等しい場合、処理がステップＳ１３８に進められる。ＣｏｌとＲｏｗとの値が異なる場合、処理がステップＳ１３９に進められる。
【００９２】
［ステップＳ１３８］ＳＩＭＤ化部１２０は、Ｃｏｌの値に「１」を加算し、新たにＣｏｌに設定する。
［ステップＳ１３９］ＳＩＭＤ化部１２０は、ｆｉｎｄ処理を実行する。これにより、現在のＲｏｗ行Ｃｏｌ列の非零要素の列位置が、行列ＡｃｏｌのＲｏｗ行目の行の何番目の要素（列）に示されているのかを示すｊが得られる。
【００９３】
［ステップＳ１４０］ＳＩＭＤ化部１２０は、ｆｉｎｄ処理で得られたｊが、０より大きく、かつｋと異なるという条件を満たすか否かを判断する。当該条件が満たされる場合、処理がステップＳ１４１に進められる。当該条件が満たされない場合、処理がステップＳ１４２に進められる。
【００９４】
［ステップＳ１４１］ＳＩＭＤ化部１２０は、ｓｗａｐ処理を実行する。このｓｗａｐ処理により、Ａｃｏｌ（Ｒｏｗ，ｋ）とＡｃｏｌ（Ｒｏｗ，ｊ）の値が交換され、Ａｖａｌ（Ｒｏｗ，ｋ）とＡｖａｌ（Ｒｏｗ，ｊ）の値が交換される。
【００９５】
［ステップＳ１４２］ＳＩＭＤ化部１２０は、ｋの値に「１」を加算し、Ｃｏｌの値に「１」を加算する。
［ステップＳ１４３］ＳＩＭＤ化部１２０は、ｋの値がＭの値より大きいか否かを判断する。ｋの値がＭの値より大きければ、処理がステップＳ１４４に進められる。ｋの値がＭの値以下であれば、処理がステップＳ１３７に進められる。
【００９６】
［ステップＳ１４４］ＳＩＭＤ化部１２０は、Ｒｏｗの値に「１」を加算する。
［ステップＳ１４５］ＳＩＭＤ化部１２０は、Ｒｏｗの値がｅｎｄＲｏｗの値より大きいか否かを判断する。Ｒｏｗの値がｅｎｄＲｏｗの値より大きい場合、部分ＳＩＭＤ化処理が終了する。Ｒｏｗの値がｅｎｄＲｏｗの値以下の場合、処理がステップＳ１３２に進められる。
【００９７】
このようにして、Ｎ行Ｌ列の圧縮行列が、Ｍ行ずつ部分ＳＩＭＤ化される。すなわち、圧縮行列の作成処理（図１１）で生成したＮ行Ｌ列の２つの行列（Ａｃｏｌ，Ａｖａｌ）の要素を並び替えることにより、部分的にＳＩＭＤ命令で演算可能となる。具体的には、図１１に示した処理により、ｓｔａｒｔＲｏｗ〜ｅｎｄＲｏｗのＭ行が部分ＳＩＭＤ化される。すなわち、係数行列ＡにおけるｓｔａｒｔＲｏｗ〜ｅｎｄＲｏｗ行の対角要素の列位置とその値が、Ａｃｏｌ（ｓｔａｒｔＲｏｗ：ｅｎｄＲｏｗ，１）とＡｖａｌ（ｓｔａｒｔＲｏｗ：ｅｎｄＲｏｗ，１）に格納される。またｓｔａｒｔＲｏｗ〜ｅｎｄＲｏｗ行の対角要素と同じ列位置である非零要素の列位置とその値が、Ａｃｏｌ（ｓｔａｒｔＲｏｗ：ｅｎｄＲｏｗ，２：Ｍ）とＡｖａｌ（ｓｔａｒｔＲｏｗ：ｅｎｄＲｏｗ，２：Ｍ）に格納される。
【００９８】
次に、ｆｉｎｄ処理について詳細に説明する。
図１４は、ｆｉｎｄ処理の手順の一例を示すフローチャートである。以下、図１４に示す処理をステップ番号に沿って説明する。
【００９９】
［ステップＳ１５１］ＳＩＭＤ化部１２０は、ｊに「１」を設定する。
［ステップＳ１５２］ＳＩＭＤ化部１２０は、「Ａｃｏｌ（Ｒｏｗ，ｊ）＝＝Ｃｏｌ」の条件が満たされるか否かを判断する。この条件が満たされる場合、ｆｉｎｄ処理が終了する。この条件が満たされない場合、処理がステップＳ１５３に進められる。
【０１００】
［ステップＳ１５３］ＳＩＭＤ化部１２０は、ｊの値に「１」を加算する。
［ステップＳ１５４］ＳＩＭＤ化部１２０は、ｊの値がＬの値より大きいか否かを判断する。ｊの値がＬの値より大きい場合、処理がステップＳ１５５に進められる。ｊの値がＬの値以下の場合、処理がステップＳ１５２に進められる。
【０１０１】
［ステップＳ１５５］ＳＩＭＤ化部１２０は、ｊに「−１」を設定し、ｆｉｎｄ処理を終了する。
このようにして、係数行列ＡのＲｏｗ行Ｃｏｌ列の非零要素の列位置が行列ＡｃｏｌのＲｏｗ行目のどこに格納されているかが探索される。そして、Ａｃｏｌ（Ｒｏｗ，ｊ）＝＝Ｃｏｌを満たすｊが見つかれば、そのｊが戻り値として出力される。なお、Ｒｏｗ行Ｃｏｌ列には非零要素が存在しない場合は、ｊ＝−１の戻り値が出力される。
【０１０２】
次に、ｓｗａｐ処理について説明する。
図１５は、ｓｗａｐ処理の手順の一例を示すフローチャートである。以下、図１５に示す処理をステップ番号に沿って説明する。
【０１０３】
［ステップＳ１６１］ＳＩＭＤ化部１２０は、Ａｃｏｌ（Ｒｏｗ，ｋ）の値をｔｍｐＣｏｌに設定する。またＳＩＭＤ化部１２０は、Ａｖａｌ（Ｒｏｗ，ｋ）の値をｔｍｐＶａｌに設定する。
【０１０４】
［ステップＳ１６２］ＳＩＭＤ化部１２０は、Ａｃｏｌ（Ｒｏｗ，ｊ）の値をＡｃｏｌ（Ｒｏｗ，ｋ）に設定する。またＳＩＭＤ化部１２０は、Ａｖａｌ（Ｒｏｗ，ｊ）の値をＡｖａｌ（Ｒｏｗ，ｋ）に設定する。
【０１０５】
［ステップＳ１６３］ＳＩＭＤ化部１２０は、ｔｍｐＣｏｌの値をＡｃｏｌ（Ｒｏｗ，ｊ）に設定する。またＳＩＭＤ化部１２０は、ｔｍｐＶａｌの値をＡｖａｌ（Ｒｏｗ，ｊ）に設定する。
【０１０６】
このようにして、Ａｃｏｌ（Ｒｏｗ，ｋ）とＡｃｏｌ（Ｒｏｗ，ｊ）の値が交換され、Ａｖａｌ（Ｒｏｗ，ｋ）とＡｖａｌ（Ｒｏｗ，ｊ）の値が交換される。
図１０〜図１５に示した処理により、連立１次方程式の解を求めるための行列計算のＳＩＭＤ化が実現する。以下、具体的なＳＩＭＤ化の例について説明する。
【０１０７】
図１６は、圧縮行列の作成例を示す図である。図１６には、係数行列５０の９行目を圧縮した場合の例を示している。
例えば、係数行列５０（Ｎ行Ｎ列）の９行目には、１，２，３，９，１０，１１，１２，２０列に非零要素が存在する。これらの非零要素それぞれの値は５．０，６．０，７．０，９．０，８．０，４．０，５．０，２．０である。この場合、係数行列５０の９行目において非零要素が存在する行位置が、Ａｃｏｌ（９，１：８）に設定される。また係数行列５０の９行目の非零要素の値が、Ａｖａｌ（９，１：８）に設定される。この例では、１行あたりの非零要素数の最大値Ｌは「８」である。
【０１０８】
同様に、係数行列５０のすべての行について、図１６に示す９行目と同様に圧縮することで、圧縮行列が生成される。
圧縮行列が生成されると、数行ごとに、部分ＳＩＭＤ化が行われる。例えば、４行ずつ（Ｍ＝４）部分ＳＩＭＤ化する場合、１〜４、５〜８、９〜１２行目、・・・というように４行ずつの部分行列ごとに、部分ＳＩＭＤ化が行われる。部分ＳＩＭＤ化では、ＡｃｏｌおよびＡｖａｌの各行について、行内での要素の並べ替えが行われる。
【０１０９】
図１７は、要素の並べ替えの一例を示す図である。図１７には、９行目に対する並べ替えの例が示されている。ＳＩＭＤ化部１２０は、図１３の処理手順に従い、ＡｃｏｌおよびＡｖａｌそれぞれの９行目の要素を並び替える。Ａｃｏｌの９行目は、まず係数行列５０の対角要素の行位置「９」が設定された要素の値と、１列目の要素の値とが交換される。次に、係数行列５０の１０行目の要素の行位置「１０」が設定された要素の値と、２列目の要素の値とが交換される。次に、係数行列５０の１１行目の要素の行位置「１１」が設定された要素の値と、３列目の要素の値とが交換される。最後に、係数行列５０の１２行目の要素の行位置「１２」が設定された要素の値と、４列目の要素の値とが交換される。
【０１１０】
このような並べ替えにより、係数行列５０の９行目〜１２行目の行位置を示すＡｃｏｌ内の要素が、Ａｃｏｌの１列目〜４列目に集約される。Ａｃｏｌと同様にＡｖａｌの要素も、図１７に示すように並べ替えられる。
【０１１１】
図１７には、９行目の並べ替えを示しているが、１０行目〜１２行目に対しても、９行目と同様の並べ替えが行われ、９行目〜１２行目に対する部分ＳＩＭＤ化が完了する。
図１８は、部分ＳＩＭＤ化の一例を示す図である。図１８において、上段に部分ＳＩＭＤ化前のＡｃｏｌの９行目〜１２行目が示されており、下段に部分ＳＩＭＤ化後のＡｃｏｌの９行目〜１２行目が示されている。Ａｖａｌの９行目〜１２行目についても、Ａｃｏｌと同様に並べ替えられる。
【０１１２】
このように、部分ＳＩＭＤ化により要素の並べ替えを行った結果、４ＳＩＭＤ命令で並列実行可能な部分（図１８中、破線で囲われた部分）と、４ＳＩＭＤ命令での並列実行はできないが同時実行可能な部分（図１８中、点線で囲われた部分）が生成される。
【０１１３】
圧縮行列全体に対してＭ行ずつの部分ＳＩＭＤ化を行うことで、シミュレーションにおける連立１次方程式の解を効率的に求めることができる。
以下、部分ＳＩＭＤ化ができるように並べ替えた要素配列を用いた解析処理プログラムの処理手順について説明する。解析処理プログラムは、例えば管理ノード１００のシミュレーション指示部１３０からの指示に基づいて、計算ノード３１，３２，・・・が実行する。
【０１１４】
解析の指示を受け付けた計算ノード３１，３２，・・・は、解析の前処理として、部分ＳＩＭＤ化が施された圧縮行列（Ａｃｏｌ，Ａｖａｌ）を、ＳＩＭＤ命令によって連続して読み出せるような配列で、メモリに格納する。以下、計算ノード３１がシミュレーションを実行する場合を例にとって、解析処理を説明する。
【０１１５】
図１９は、部分ＳＩＭＤ化後のＡｃｏｌの格納例を示す図である。図１９では、メモリ６０の各列は左から右に向かって連続してアクセスされる。メモリ６０内の１つの列のアクセスが完了すると、次にその列の１段上の列がアクセスされる。
【０１１６】
このような順番でメモリアクセスが行われる場合に、計算ノード３１は、Ａｃｏｌ内の要素は、部分ＳＩＭＤ化された行群ごと（図１９の例では４行×８列）に、要素の配置を転置する。そして計算ノード３１は、転置された配置の要素をメモリ６０に格納する。計算ノード３１は、Ａｖａｌについても同様に転置して、メモリ６０に格納する。
【０１１７】
図２０は、解析実行時のアクセス例を示す図である。図２０では、１つの命令で同時にアクセスされる要素を破線で囲んでいる。またプロセッサからのアクセス順「１」〜「１７」を、丸内の数字で表している。
【０１１８】
例えば、計算ノード３１のプロセッサは、非零要素の列位置情報（８行×４列）に対して、まずアクセス順「１」〜「４」の要素について、４回の４ＳＩＭＤ命令により４個ずつロードする。次にプロセッサは、アクセス順「５」の３個の要素をロードする。次にプロセッサは、アクセス順「６」の２個の要素をロードする。その後、プロセッサは、アクセス順「７」〜「１７」の要素を１個ずつロードする。
【０１１９】
なお、図２０に示したアクセス順「１」〜「７」の要素は、任意にアクセス順の入れ替えが可能である。一方、プロセッサは、アクセス順「８」〜「１７」の要素については、アクセス順「１」〜「７」の要素を用いた演算後に順番にロードする。
【０１２０】
なお、プロセッサは、Ａｃｏｌ内の要素のロードと同様の順番で、Ａｖａｌ内の対応する非零要素の値もロードする。そしてプロセッサは、要素をロードするごとに、積和演算を行う。具体的には、プロセッサは、Ａｃｏｌからロードした要素の値に対応するベクトルｘの要素とＡｖａｌからロードした要素の値とを用いた積和演算を行う。例えばプロセッサは、４ＳＩＭＤ命令でＡｖａｌから４つの要素をロードした場合、４つの要素それぞれの値に、ベクトルｘの対応する要素の値を乗算し、乗算結果を係数行列の行ごとの積算値に加算する。
【０１２１】
このように、計算ノード３１のプロセッサは、ＳＩＭＤ命令で演算可能な要素群についてはＳＩＭＤ命令によってロードして演算を行うことで、効率的に解析処理を実行する。また、プロセッサは、並列実行可能な要素についても、ＳＩＭＤ命令でロードして演算することで、効率的な解析処理を実行する。
【０１２２】
以上説明したように、第２の実施の形態では、係数行列を圧縮した圧縮行列の各行における行内での要素の入れ替えにより、ＳＩＭＤ命令で並列実行可能な要素配列を実現している。そして、ＳＩＭＤ命令による演算が可能となることで、解析処理の高速化が図れる。
【０１２３】
なお、第２の実施の形態では、ＳＩＭＤ化処理を管理ノード１００が行い、解析処理を計算ノード３１，３２，・・・が行っているが、ＳＩＭＤ化処理についても計算ノード３１，３２，・・・に実行させてもよい。
【０１２４】
〔第３の実施の形態〕
次に第３の実施の形態について説明する。第３の実施の形態は、要素の並べ替えにおいて、ＳＩＭＤ化できない要素を左に寄せるような配置にするものである。これにより、例えば４ＳＩＭＤ化の場合、４ＳＩＭＤ化できない部分が左の３列以下とすることができる場合がある。
【０１２５】
すなわち第２の実施の形態では、圧縮行列を以下の３つの部分に分けている（図１８参照）。
１．４ＳＩＭＤ化できる部分
２．４ＳＩＭＤ化はできないが同時実行できる部分
３．逐次に実行する部分
それに対して、第３の実施の形態では、「１．４ＳＩＭＤ化できる部分」と「３．逐次に実行する部分」とに分ける。
【０１２６】
図２１は、第３の実施の形態における並べ替えの例を示す図である。例えばＳＩＭＤ化部１２０は、まず、行ごとに、４ＳＩＭＤ化できない要素数を求める。図２１の例では、９行目から１２行目の各行の部分ＳＩＭＤ化を行う場合を想定している。この場合、ＳＩＭＤ化部１２０は、Ａｃｏｌに示される非零要素の列位置のうち、９〜１２のいずれかの値を持つ要素の個数を、行ごとに求める。そしてＳＩＭＤ化部１２０は、行ごとの４ＳＩＭＤ化できない要素数の最大値ｎｚを求める。その最大値ｎｚが４であれば、左寄せしても４ＳＩＭＤ化できる部分のサイズは広がらないので、左寄せの処理は終了する。
【０１２７】
最大値ｎｚが４未満であれば、４ＳＩＭＤ命令で演算可能な列が、「４−ｎｚ」列だけ増えることになる。そこで、最大値ｎｚが４未満の場合、ＳＩＭＤ化部１２０は、Ａｃｏｌの９〜１２行の各行において、左側のｎｚ列内だけに、非零要素の列位置が９〜１２の要素が配置されるように並び替える。図２１の例では、最大値ｎｚが３であるため、第２の実施の形態の場合よりも１列だけ、４ＳＩＭＤ命令で演算可能な列（図２１中の破線で囲まれた列）が増えている。なお、４ＳＩＭＤ化できない要素数がｍｚ（＜ｎｚ）個である行のｍｚ＋１〜ｎｚ列には任意の列位置の要素を配置してよい。
【０１２８】
ＳＩＭＤ化部１２０は、Ａｖａｌの要素についても、Ａｃｏｌ内の対応する要素と同様の配置となるように並べ替える。その結果、４ＳＩＭＤ命令で実行可能な部分が拡大し、さらに解析処理が効率化される。
【０１２９】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【符号の説明】
【０１３０】
１  圧縮行列
１０  情報処理装置
１１  記憶部
１２  演算部
【図１】
2017130036.tif 000003
【図２】
2017130036.tif 000004
【図３】
2017130036.tif 000005
【図４】
2017130036.tif 000006
【図５】
2017130036.tif 000007
【図６】
2017130036.tif 000008
【図７】
2017130036.tif 000009
【図８】
2017130036.tif 000010
【図９】
2017130036.tif 000011
【図１０】
2017130036.tif 000012
【図１１】
2017130036.tif 000013
【図１２】
2017130036.tif 000014
【図１３】
2017130036.tif 000015
【図１４】
2017130036.tif 000016
【図１５】
2017130036.tif 000017
【図１６】
2017130036.tif 000018
【図１７】
2017130036.tif 000019
【図１８】
2017130036.tif 000020
【図１９】
2017130036.tif 000021
【図２０】
2017130036.tif 000022
【図２１】
2017130036.tif 000023