スパースな正値対象行列の連立１次方程式の演算処理方法、装置、プログラム
【課題】スパースな正値対象行列の連立１次方程式の解を求める並列計算時にメモリアクセスが同じメモリ格納領域に集中しないようにする。
【解決手段】分岐ノード集合検出部１０１は、エリミネーションツリーをルートノードからサーチし、並列レベル毎の分岐ノード集合を検出する。メモリ割付チェイン生成部１０２は、同じ並列レベルのサブツリーと、サブツリーを構成せずかつレベルが近接し並列計算される可能性の高いノード群に、それぞれ異なるメモリ格納領域を割り付ける。タスクチェイン生成部１０３は、複数のスレッドがサブツリー単位で構成するノード群を選択して演算処理を実行し、サブツリーを構成しないノードをリーフ側から順次選択して演算処理を実行タスクチェインを生成する。LDL^T分解実行部１０４は、タスクチェインに基づいて複数のスレッドに各ノードの演算処理の実行時に、前述のノード毎に割り付けられたメモリ格納領域を使用する。
【解決手段】分岐ノード集合検出部１０１は、エリミネーションツリーをルートノードからサーチし、並列レベル毎の分岐ノード集合を検出する。メモリ割付チェイン生成部１０２は、同じ並列レベルのサブツリーと、サブツリーを構成せずかつレベルが近接し並列計算される可能性の高いノード群に、それぞれ異なるメモリ格納領域を割り付ける。タスクチェイン生成部１０３は、複数のスレッドがサブツリー単位で構成するノード群を選択して演算処理を実行し、サブツリーを構成しないノードをリーフ側から順次選択して演算処理を実行タスクチェインを生成する。LDL^T分解実行部１０４は、タスクチェインに基づいて複数のスレッドに各ノードの演算処理の実行時に、前述のノード毎に割り付けられたメモリ格納領域を使用する。
【発明の詳細な説明】
【技術分野】
【０００１】
開示する技術は、シミュレーションや数理モデルから生じるスパースな正値対象行列の連立１次方程式の解を求めることにより数理モデルの分析を行う技術に関する。
【背景技術】
【０００２】
最近のスカラー計算機は、ＣＰＵの性能は高速化されているが、メモリのアクセスが局所的に集中するときに処理性能が低下する傾向にある。特に、スパースな正値対象行列の連立１次方程式をコレスキー分解（LDL^T分解）を行いながら解く場合、データの参照更新が局所的なメモリ格納領域に集中することが多く、これが原因で並列効率をうまく引き出せないことがある。
【０００３】
以下にその実例を示す。
今、図１３に示されるようなスパースな正値対象行列Ｌを考える。対角要素にノード番号、●は非ゼロ要素、○はLDL^T（又はLL^T）分解で発生したフィルイン（fill-in）を表す。
【０００４】
left-looking法に基づくLDL^T分解は、次のようにして求めることができる。
行列Lのi行目のiを除いた非ゼロ要素を持つノードの集合が算出される。これをrowstruct(i) とする。例えば、rowstruct(4)={1,2,3}, rowstruct(8)={5,7}である。
【０００５】
rowstruct(i) は、エリミネーションツリー（elimination tree）のノードi をルートノードとするpuruned row subtree を構成し、それから算出することができる。実際、{4} + {1,2,3}、{8}+{5,7}はsubtree（サブツリー、部分木）になっている。なお、この処理の詳細については、下記非特許文献１に記載されている。
【０００６】
ノードi のLの列ベクトルをliとして、LDL^T分解の対角行列の対角要素をdiiとする。また、LDL^T分解を行う行列をAとし、この下三角行列のi 番目の列ベクトルをaiとする。
li ← ai − Σdjj ×lij ×lj ・・・（１）
j ∈ rowstruct(i)
li ← li ／dii ，ここで dii＝lii ・・・（２）
上記（１）式及び（２）式で示される処理がi=1 からn まで繰り返されることにより、li が算出される。
【０００７】
li の計算は、rowstruct(i)の要素のノードjでlj が計算できていれば、それらを使ってそのjに関する計算をliに対して行うことができる。つまり、li=aiと初期化され、その時点で計算が終わっているljを使ってliに対する更新の計算が実行される。
【０００８】
liの格納に必要なメモリ格納領域の大きさも、エリミネーションツリーのpuruned row subtreeを用いて計算することができる。つまり、ノードiを含むpuruned row subtreeの数を数えることにより、上記メモリ格納領域の大きさを算出することができる。
【０００９】
また、liの非ゼロ要素のインデクス（行番号）の集合は、ノードi及びrowstruct(i)のインデクスの和を求めることで計算することができる。これらの計算処理は、入力配列Aを解析して求めることができ、symbolic decompositionと呼ばれている。この詳細については、下記非特許文献１に記載されている。
【００１０】
これらの情報から、各column（列）のliは、非ゼロ要素を圧縮してcompressed column storage（圧縮列格納方式）でメモリに格納することができる。
また、ノードiの更新で、エリミネーションツリーのdescendantとなるノードのインデクスでiよりも大きなものは、ノードiのインデクスの部分集合になることが、上記（１）式からわかる。
【００１１】
このことから、各liの更新の計算を、圧縮した状態で一時域で計算してインデクスサーチしてliの対応位置に加えることで実行できる。
liの並列計算に関して、ノードiの更新をスレッドに割り付けて並列に、参照可能なljを使ってliを計算できる。ノードiの更新が終わればこれが参照可能となるため、このノードを待っていたスレッドの計算が可能になる。更新の終わったスレッドには、タスクチェイン（タスクキュー）にある次に更新されるべきノードの計算が新たに割り当てられる。参照可能なノードjに関しての更新が実行され、まだ計算が完了していないノードは後回しにして処理される。利用可能なノードの計算が終わり、計算に必要なノードjが残っていれば、ノードjの計算が終わるのが待たれる。このようににして、パイプライン方式で、LDL^T分解計算の並列化を実現することができる。
【００１２】
ここで、エリミネーションツリーは、次式で示される親子関係から算出することができる。
parent(i)=min { j | lji ≠ 0 , j > i } ・・・（３）
： Lのi番目の列で最初にゼロでない行番号
例えば、図１３に示される行例において、ノード１の親はノード２、ノード２の親はノード４、ノード３の親はノード４などである。実際のエリミネーションツリーは、LDL^T分解される配列Aの下三角（{aij | i ≧ j , j=1,…,n}）をサーチすることで算出することができる。この処理の詳細は、下記非特許文献１に記載されている。
【００１３】
図１４は、上記（３）式に基づいて図１３の行列に対して算出されるエリミネーションツリーの例を示す図である。このエリミネーションツリーの例から、例えば以下のような並列計算のための知見を得ることができる。
【００１４】
まず、ノード４とノード７の間では参照される共通のノードはないため、ノード４及びノード７は独立に計算することができる。
一般には、前述の（１）式から、{ i } + rowstruct(i) と { j } +rowstruct(j) が共通部分を持たない場合、各々に属するliの計算は、独立に実行することができる。エリミネーションツリーにおいては、共通部分のないsubtree同士は、独立に計算可能である。subtreeの各ノードのliの計算に必要なノードは、ノードiをルートとするpuruned subtree なので、subtree内に含まれている。従って、共通部分のないsubtree同士は、相互に依存関係がないことになるので、独立な計算が可能である。
【００１５】
図１３及び図１４において、LDL^T分解の結果におけるフィルインを含めた非ゼロ要素の数や各列の非ゼロ要素のインデクス（行番号）は、前述したように、分解の前にsymbolic decompositionによって求めることができる。
【００１６】
eliminationツリーが、depth firstに従って、ルートノード（図１４ではノード２１）からサーチされることにより、各ノードに対してポストオーダで番号付けがなされる。なお、depth firstやポストオーダの意味については、実施形態の説明において詳細に説明する。図１３及び図１４の例では、ポストオーダと元の番号は一致している。
【００１７】
subtree{1,2,3,4}とsubtree{5,6,7}が、前述の（１）式及び（２）式に従って分解される。このときの依存関係から、ポストオーダ順に計算が実行される。つまり、ノード１→２→３→４、及びノード５→６→７の順に計算が実行される。これら２系列の計算は、並列に計算可能である。
【００１８】
上記計算が終わったら、ノード８→９→．．．→２１という順で計算が実行される。ノード８，９は、共に７の列を参照するため、列７を用いて更新する箇所は並列に計算でき、ノード７の計算が終わっていれば計算可能である。８，９，１０と空いたスレッドが発生するたびに、タスクチェインからノードが割り当てられ列の更新が受け持たされる。ノード１１〜ノード２０までの計算も、上記の場合と同様の依存関係がある。例えば、列１３が計算でき、ノード１４，１５を並列に更新できる。ノード１４の更新が終われば、このスレッドにノード１６が割り当てられる。そして、ノード１５の更新と１６の更新が並列に実施される。
【００１９】
このようにして、パイプライン方式で更新を実行することができる。
本出願が開示する技術に関連する従来技術として、下記先行技術文献が開示されている。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】T.DAVIS, Direct Methods for Sparse Linear Systems, SIAM 2006
【発明の概要】
【発明が解決しようとする課題】
【００２１】
ここで、上述した従来の並列計算方式において、計算結果のメモリ格納領域としては、1からnまでのcolumn（列）の大きさ（column count）を加算した大きさのメモリ格納領域が割り当てられる。この場合に、compressed column storage方式で行列Lが格納されてゆく。liが、１からnまでつなげた領域に格納される。
【００２２】
例えば、メモリが３個の部分に分かれていて、メモリ格納領域もほぼ３つ程度に均等にわたって存在するとする。そして、メモリ格納領域が単純に、各liのインデックスｉの大きさに応じて３等分されるとする。そのとき、subtree{1,2,3,4}とsubtree{5,6,7}が並列に計算されると、図１３より、１番目のメモリ格納領域（ｉ＝１〜７に対応）ばかりがアクセスされることになる。またその後、ポストオーダ順にノード１１〜２０までがパイプライン的に並列に処理される。このとき２番目（ｉ＝８〜１４に対応）、３番目（ｉ＝１５〜２１に対応）のエリアばかりが局所的にアクセスされることになる。つまり、アクセスが局所的なメモリ格納領域に集中する。
【００２３】
並列度が２から３に上げられるとき、図１３及び図１４の例では、並列に実行されるsubtreeは３個はない。このため、並列処理の粒度を下げてバランスをとるために、subtreeの計算を並列の対象からはずすことが望ましい。この場合、計算処理がポストオーダ順に実行され、パイプライン処理での並列性が引き出される。このとき、ポストオーダ順にタスクチェインが作成され、ノードのliの更新処理が、各スレッドにパイプライン処理として割り当てられる。しかし、このような方式が採用された場合、メモリに対するアクセスが局所的に集中していってしまうという問題点を有していた。
【００２４】
つまり従来は、並列度を上げてゆけば、並列実行をパイプラインで行える範囲で理論的には性能が向上するはずである。しかし、メモリのアクセスの局所化が増すため、かえって計算効率が低下してしまう可能性が高いという問題点を有していた。
【００２５】
開示する技術が解決しようとする課題は、並列計算時にメモリアクセスが同じメモリ格納領域に集中しないようにすることにある。
【課題を解決するための手段】
【００２６】
上記課題を解決するために、開示する技術は、スパースな正値対象行列の連立１次方程式を解く演算処理を、該正値対象行列のコレスキー分解に先立ち入力行列の非零要素の構造を解析してえられるエリミネーションツリーを構成するスーパーノードを単位として実行する演算処理方法、装置、又はプログラムとして実現され、以下の構成を有する。
【００２７】
分岐ノード集合検出処理ステップ又は分岐ノード集合検出処理部は、エリミネーションツリーをそのルートノードからサーチすることにより、並列レベル毎の分岐ノードの集合を検出する。
【００２８】
サブツリーメモリ格納領域割付けステップ又はサブツリーメモリ格納領域割付け部は、分岐ノードの集合のうち、その集合の要素数が連続にメモリデータが割り当てられる記憶単位である複数のメモリ格納領域の数以上となる集合をサーチし、そのサーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリー毎に、そのサブツリーを構成するノード群に対する列ベクトルの演算結果を複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付ける。
【００２９】
ノードメモリ格納領域割付けステップ又はノードメモリ格納領域割付け部は、エリミネーションツリーを構成するノード群のうち、前述のサーチで得られる分岐ノードの集合に対応する各サブツリーを構成するノード群を含まないノード群に対する列ベクトルの演算結果を、並列レベルが近接しているノード群の演算結果はそれぞれ異なるメモリ格納領域に割り付けられるようにして、複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付ける。
【００３０】
上述の構成に加えて、以下の構成を有する。
サブツリーチェイン生成ステップ又はサブツリーチェイン生成部は、分岐ノードの集合のうち、その集合の要素数が並列実行される複数のスレッドの数以上となる集合をサーチし、そのサーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリーに関する情報をその各サブツリー単位で第１のタスクチェインであるサブツリーチェインに接続する。
【００３１】
ノードチェイン生成ステップ又はノードチェイン生成部は、エリミネーションツリーを構成するノード群のうち、スレッドに関するサーチで得られる分岐ノードの集合に対応する各サブツリーを構成するノード群を含まないノード群を、エリミネーションツリーのリーフノードからルートノードに向かう順でかつ並列レベル毎にまとまるようにして、第２のタスクチェインであるノードチェインに接続する。
【００３２】
そして、各スレッドは、サブツリーチェインに接続されている各サブツリーに関する情報を登録順に選択してその情報に対応するサブツリーを構成するノード群に対する列ベクトルの演算を実行し、サブツリーチェインで選択すべきエントリがなくなったら、ノードチェインに接続されている各ノードに対する列ベクトルの演算を登録順に実行する。
【発明の効果】
【００３３】
開示する技術によれば、同じ並列レベルのサブツリーの並列計算時に各サブツリーを構成するノード同士が集中して同じメモリ格納領域にアクセスするという状況を回避することが可能となる。
【００３４】
また開示する技術によれば、ノードの並列計算時にそれらのノード同士が集中して同じメモリ格納領域にアクセスするという状況を回避することが可能となる。
そして開示する技術によれば、各スレッドは概ね独立したメモリ格納領域をアクセスする。この結果、アクセスが集中することがないため、メモリアクセスのボトルネックが発生せず、並列度が上げたときに処理性能が著しく劣化することを回避することが可能となる。
【図面の簡単な説明】
【００３５】
【図１】実施形態の構成図である。
【図２】分岐ノード集合検出処理を示す動作フローチャートである。
【図３】メモリ割付チェイン生成処理を示す動作フローチャートである。
【図４】タスクチェイン生成処理を示す動作フローチャートである。
【図５】LDL^T分解実行処理を示す動作フローチャートである。
【図６】エリミネーションツリーの例を示す図である。
【図７】実施形態のデータ構成図（その１）である。
【図８】実施形態のデータ構成図（その２）である。
【図９】実施形態の動作説明図である。
【図１０】実施形態のデータ構成図（その３）である。
【図１１】実施形態が適用されるハードウェアシステム構成の例を示す図（その１）である。
【図１２】実施形態が適用されるハードウェアシステム構成の例を示す図（その２）である。
【図１３】LDL^T分解処理を行う正値対象行例の例を示す図である。
【図１４】図１２の正値対象行列の例に対応するエリミネーションツリーを示す図である。
【発明を実施するための形態】
【００３６】
以下、実施形態について詳細に説明する。
スパースな正値対象行列のLDL^T分解は、以下に示される方法で行われる。まず、スパース行列データが、compressed column storage（圧縮列格納方式）などの圧縮格納方式によってメモリに格納される。これにより、対角要素を含む下三角行列部分の非ゼロ要素が圧縮してメモリに格納される。列同士の依存関係や分解で新たに発生する非ゼロ要素が考慮されて、非ゼロパターンが同じか似ている列が並べ替えられて、１つのpanel（ブロック）にまとめられる。ブロックはスーパーノードと呼ばれ、複数のノードからなる。分解過程で生じるスーパーノード間のデータ依存関係が木構造で表現されて処理が実行される。この木のことをエリミネーションツリー（elimination tree）と呼ぶ。
【００３７】
これらの木を構成するノードはスーパーノードであり、親子関係で表現できる。
ノードがleft-looking法で更新されてゆくとき、そのノードに関するpruned row subtreeの情報に基づいて、更新により参照されるrow structure（行構造）が決まる。pruned row subtreeは、エリミネーションツリーのsubtree（サブツリー、部分木）である。
【００３８】
このため、エリミネーションツリーのリーフを持つsubtreeで、お互いに共通部分を持たないものは独立に分解の計算を行うことができる。この処理の詳細については、例えば前述の非特許文献１に詳細に記載されている。
【００３９】
並列計算を行う上では、各々のsubtreeを構成するスーパーノードに対するブロックを格納するメモリ格納領域は、互いに近くに割り付けられるのがよい。
更に処理が進むと、木のルート（root）の方向に処理が進みながら、更新されるべきノードが順次選択されてゆく。処理がルートに近づくほど、一般に独立なsubtreeは減ってゆく。各ノードの依存関係が考慮されながらノードに対するブロックの更新が並列処理されてゆく。スパース行列のために、参照・更新されるノードは限られる。このため、単純に木の構造を構成するノードで近いものがメモリ上でも近くのメモリ格納領域に割り当てられると、メモリへの参照・更新が局所的な部分に集中してしまう。
【００４０】
これを避けるために、並列処理の対象が、subtreeで分けられない部分と分けられる部分に分割される。そして、分解結果を格納する領域が複数の連続する部分に分割されることにより、subtreeを構成するノードに対応するブロック列ベクトルの格納領域が異なる部分連続領域に割り当てられるように制御が行われる。
【００４１】
subtreeが取り除かれた部分の要素となるノードに関しては、木のルートからsubtreeのルート又は木のリーフに届くまで、同じ並列レベルのノードがまとめられながら、木が辿られてゆく。そして、辿られたルートと逆ルートが辿られながら、各ノードが異なる部分連続領域にサイクリックに割り付けられてゆく。
【００４２】
並列処理に関しては、上述の割付けと同様の方式でタスクチェインが生成される。並列処理を実行するスレッド数を#Pとして、#P個以上のsubtreeがあれば、これらのsubtreeのルートとなるノードがタスクチェイン（subtree chain：サブツリーチェイン）に接続される。subtreeが取り除かれたノードに関しても部分連続領域の割付けと同様にして、木のルートからsubtreeのルート又は木のリーフに届くまで、同じ並列レベルのノードがまとめられながら、木が辿られてゆく。そして、辿られたルートと逆ルートを辿る順番のノードのチェインが生成され、ノードのタスクチェイン（node chain：ノードチェイン）とされる。
【００４３】
以上の制御処理により、並列計算を行えるスレッド数が変わっても、同じメモリ格納領域へのメモリアクセスが集中することを避けることができる。
【００４４】
エリミネーションツリーについて、以下に説明する。
本実施形態では、エリミネーションツリーは、全ノード数を#nodeとする１次元配列parentを用いて表現される。例えば、j=parent(i)は、「ノードiの親（parent）はノードjである」という意味を表現している。
【００４５】
エリミネーションツリー上のノードの子及び兄弟の関係は、１次元配列child及びbrotherを用いて表現される。ノードj がノードi の子であれば、child(i)=jである。ノードi に子がなければ、child(i)=0である。
【００４６】
子が複数存在する場合には、１つの子が親のchildとされ、その他の子はそのchildのbrotherとして表現される（親の子とはされない）。ノードj のbrotherとしてj1,j2があれば、brother(j)=j1, brother(j1)=j2, brother(j2)=0 と表現される。
【００４７】
或るノードに対するfirstdescendant（ファーストディッセンダント：第１子孫）とは、そのノードから子（兄弟ではない）を辿って到達する、子がないノード即ちリーフノードのことをいう。例えば図６では、ノード７のfirstdescendantはノード１、ノード６のfirstdescendantはノード４などである。
【００４８】
ここで、ポストオーダを、depth firstで、エリミネーションツリーがルートノード１５からサーチされ、サーチ順に各ノードに番号が付与されるときの順番と定義する。図６においては、ポストオーダは、１，２，３，．．．，１４となる。
【００４９】
depth firstとは、以下のようなサーチ手順をいう。まず、ルートノードから子が辿られて、最も深いノード例えばノード１がサーチされる。１ノード分だけ親＝ノード３に戻って、その親の子のうちノード１の兄弟例えばノード３が辿られる。再び、１ノード分だけ親＝ノード３に戻って、その親の子にはノード１の兄弟はもうないため、更に親＝ノード７に戻って、そこから子が辿られて、最も深いノード例えばノード４がサーチれる。以下同様にエリミネーションツリーがで辿られて、ポストオーダが決定される。このように、常に深いノードが優先されるサーチ手順をdepth firstと呼ぶ。
【００５０】
subtreeは、ノード１〜７によって構成される部分集合や、ノード８〜１４によって構成される部分集合などをいう。また、３つのノードからなるノード１〜３、ノード４〜６、ノード８〜１０、ノード１１〜１２の各部分集合も、subtreeである。
【００５１】
リーフとは、子を持たないノードをいう。図６では、１，２，４，５，６，９，１１，１２がリーフである。
上述のエリミネーションツリーを用いることにより、スパース行列で、ノードに対応する列ベクトルを束ねたスーパーノードが検出される。スーパーノードを構成するノードの非ゼロ要素の存在する行のみが圧縮され、２次元のpanel（パネル）に分解結果が格納される。
【００５２】
各スーパーノードに対応するpanelの大きさは、分解結果の非ゼロパターンに対してsymbolic decompositionが実行されることにより決定され、実際の分解を行う前に知ることができる。
全panelを格納する１次元配列が用意され、この１次元配列のどの要素位置に各スーパーノードに対応するpanelが配置されるかが決定される。
【００５３】
図１は、上述の基本的な考え方に基づく実施形態の構成図である。
この実施形態は、分岐ノード集合検出部１０１、メモリ割付チェイン生成部１０２、タスクチェイン生成部１０３、LDL^T分解実行部１０４を含む。
【００５４】
分岐ノード集合検出部１０１：
ステップ１．エリミネーションツリーデータ（parent配列、child配列、brother配列）が入力される。そして、それによって表現されるエリミネーションツリーにおいて、ルートノードからサーチが行われ、兄弟が複数ノードある、同じ並列レベルの分岐ノードの集合が、レベル毎に検出される。
【００５５】
メモリ割付チェイン生成部１０２：
ステップ２．ステップ１．で検出されたレベル毎の分岐ノードの集合のうち、集合の要素数が連続にメモリデータを割り当てるセクション（メモリ格納領域）の数以上となるものが、レベルが低いものから順にサーチされる。
【００５６】
ステップ３．見つかった場合、この集合から分岐ノードが取り出され、このノードがルートノードとされるsubtreeがポストオーダー順に取り出され、各メモリ格納領域のための割付チェインに接続される。このとき、１つのsubtreeの構成ノードは、同じ割付チェインに接続される。subtree毎に、それが割り付けられるべきメモリ格納領域を指定する割付チェインが、サイクリックな順番で決められる。この結果、同じ並列レベルのsubtreeには、並列計算の実行時に、それぞれ異なる割付チェインを介して異なるメモリ格納領域が割り付けられることになる。即ち、同じ並列レベルのsubtreeの並列計算時に各subtreeを構成するノード同士が集中して同じメモリ格納領域にアクセスするという状況を回避することができる。
【００５７】
ステップ４．ステップ３．で割付けが行われたsubtreeを除いたノードが、ルートノードから同じ並列レベルのノードが集まるようにしてリーフ方向にサーチされる。このサーチがステップ３．で割り付けられた分岐ノードかリーフノードに到達すれば、そのサーチは終了する。サーチされたノードは、サーチの順にstack（後述するwork配列）に積まれる。サーチが終わったら、stackが順にpopされながらサーチの逆順でノードが取り出され、その各ノードに対して、サイクリックな順番で割付チェインが決定される。この結果、レベルが近接し並列計算される可能性の高いノード群には、それぞれ異なる割付チェインを介して異なるメモリ格納領域がサイクリックに割り付けられることになる。これにより、ノードの並列計算時にそれらのノード同士が集中して同じメモリ格納領域にアクセスするという状況を回避することができる。
【００５８】
タスクチェイン生成部１０３：
ステップ５．ステップ１．で検出されたレベル毎の分岐ノードの集合のうち、集合の要素数が並列実行されるスレッドの数以上となる集合が、レベルの低いものから順にサーチされる。
【００５９】
ステップ６．ステップ５．で検出された分岐ノードの集合に含まれる分岐ノードが順次、subtree chainに接続される。
【００６０】
ステップ７．ステップ６．で処理された各分岐ノードがルートノードとされる各subtreeを除いたノードが、ルートノードから同じ並列レベルのノードが集まるようにしてリーフ方向にサーチされる。このサーチがステップ６．でsubtree chainに接続された分岐ノードかリーフに到達すれば、そのサーチは終了する。サーチされたノードは、サーチの順にstack（後述するwork配列）に積まれる。サーチが終わったら、stackが順にpopされながらサーチの逆順でノードが取り出され、その各ノードがnode chainに接続される。
【００６１】
LDL^T分解実行部１０４：
ステップ８．ステップ６．にて生成されたsubtree chainにエントリがあるうちは、subtree chainの先頭から順次各分岐ノードがスレッドの並列数ずつ取り出され、各スレッドに割り当てられる。各スレッドでは、割り当てられた分岐ノードに対応するsubtreeを構成する各ノードに対して、left-lookingなLDL^T分解が実行される。subtree chainのエントリがなくなったら、ステップ７．にて生成されたnode chainの先頭から順次各ノードがスレッドの並列数ずつ取り出され、各スレッドに割り当てられる。各スレッドでは、割り当てられたノードに対して、left-lookingなLDL^T分解が実行される。
【００６２】
ここで、分岐ノード集合検出部１０１が実行するステップ１は、特許請求の範囲における分岐ノード集合検出処理ステップに対応する。メモリ割付チェイン生成部１０２が実行するステップ２．及び３．は、特許請求の範囲におけるサブツリーメモリ格納領域割付けステップ又はサブツリーメモリ格納領域割付け部に対応する。メモリ割付チェイン生成部１０２が実行するステップ４．は、特許請求の範囲におけるノードメモリ格納領域割付けステップ又はノードメモリ格納領域割付け部に対応する。タスクチェイン生成部１０３が実行するステップ５．及び６．は、特許請求の範囲におけるサブツリーチェイン生成ステップ又はサブツリーチェイン生成部に対応する。タスクチェイン生成部１０３が実行するステップ７．は、特許請求の範囲におけるノードチェイン生成ステップ又はノードチェイン生成部に対応する。
【００６３】
以上の各部の処理を実現するための本実施形態の詳細な処理について、従来技術の説明において用いた図１３に示される行列と図１４に示されるエリミネーションツリーの例と、図２から図５の動作フローチャート、及びを用いて、以下に説明する。
【００６４】
図２は、分岐ノード集合検出部１０１が実行する前述のステップ１．の分岐ノード集合検出処理の詳細を示す動作フローチャートである。
図７は、エリミネーションツリーのルートノードをレベル１として、レベル１から順次増加するレベル毎に、各レベルに属する分岐ノードの集合を管理するための配列データの構成例を示した図である。
【００６５】
図７（ｂ）は、分岐ノードを、エリミネーションツリーのルートノードからリーフノードに向かって検出された順に登録する１次元配列branchのデータ構成例である。ここで、branch配列の配列位置０（図７（ｂ）の７０４）の配列要素値＝２１は、図１４に示されるエリミネーションツリーのルートノードに対応し、レベル１の分岐ノードのノード番号を示している。配列位置１（図７（ｂ）の７０５）の配列要素値＝１０は、図１４に示されるエリミネーションツリーのノード１０に対応し、レベル２の分岐ノードのノード番号を示している。配列位置２及び３（図７（ｂ）の７０６及び７０７）の配列要素値＝４及び７は、図１４に示されるエリミネーションツリーのノード４及びノード７に対応し、レベル３の分岐ノード群の各ノード番号を示している。
【００６６】
図７（ａ）は、先頭からレベル１、２、３、・・・の順に、branch配列上における各レベルの分岐ノード群が格納されている先頭の配列位置を配列要素値として格納する１次元配列branchlvlのデータ構成例である。ここで、branchlvl配列の配列位置０（図７（ａ）の７０１）の配列要素値＝０は、図７（ｂ）のbranch配列上のレベル１の分岐ノード群（図７（ｂ）ではノード２１の１つのみ）が格納されている先頭の配列位置を示している。配列位置１の配列要素値＝１（図７（ａ）の７０２）は、図７（ｂ）のbranch配列上のレベル２の分岐ノード群（図７（ｂ）ではノード１０の１つのみ）が格納されている先頭の配列位置を示している。配列位置２の配列要素値＝２（図７（ａ）の７０３）は、図７（ｂ）のbranch配列上のレベル３の分岐ノード群（図７（ｂ）ではノード４及び７の２つ）が格納されている先頭の配列位置を示している。
【００６７】
分岐ノード集合検出部１０１によって実行される図２の動作フローチャートは、図７（ａ）に例示されるbranchlvl配列及び図７（ｂ）に例示されるbranch配列を生成する処理である。
【００６８】
以下の説明において、図１４等に示されるエリミネーションツリーの各ノードは、エリミネーションツリーデータとして入力される前述したparent配列から取得でき、１つのノードに対する子ノードは前述したchild配列から取得でき、兄弟ノードは前述したbrother配列から取得できるものとする。
【００６９】
図２において、まず、levelstart、levelend、ptrnext、ptrsearch、levelの各変数が初期化される（ステップＳ２０１）。levelstartは、レベル毎にそのレベルに属する各分岐ノードの下に更に分岐ノードがあるか否かが探索される際に、そのレベルに属する分岐ノード群のbranch配列上での先頭の配列位置を示す。levelstartの初期値は、０（branch配列の先頭（図７（ｂ）の７０４））にセットされる。levelendは、レベル毎にそのレベルに属する各分岐ノードの下に更に分岐ノードがあるか否かが探索される際に、そのレベルに属する分岐ノード群のbranch配列上での末尾の配列位置を示す。levelendの初期値も、０にセットされる。ptrnextは、branch配列上で分岐ノードが格納されている末尾の配列位置を示す。ptrnextの初期値も、０にセットされる。ptrsearchは、レベル毎にそのレベルに属する各分岐ノードの下に更に分岐ノードがあるか否かが探索される際に、現在探索が行われている分岐ノードの配列位置を示す。ptrnextは、levelstartからlevelendまでの間の値をとり、初期は０にセットされる。levelは、現在処理が行われているレベルを示す。levelの初期値は、１（＝エリミネーションツリーのルートノードのレベル）にセットされる。
【００７０】
次に、ステップＳ２０２で、図７（ａ）の７０１として示されるように、branchlvl配列の先頭の配列位置０に、branch配列の先頭の配列番号０が、レベル１（level=1）のインデックスとして格納される。
【００７１】
次に、ステップＳ２０３で、ptrsearch≦levelendが成立するか否かが判定される。始めは、ptrsearch=0≦levelend=0となるので、この判定はＹＥＳとなる。この結果、ステップＳ２０４へ移行する。
【００７２】
ステップＳ２０４では、branch配列内の配列位置=ptrsearchのノードに子（child）があるか否かが判定される。図１４に示されるように、branch配列内の配列位置０のノード２１にはノード１０のchildがあるので、この判定はＹＥＳとなる。この結果、ステップＳ２０５へ移行する。
【００７３】
ステップＳ２０５では、childstart変数にchildの値が設定される。childstart=10となる。ここで、childstart変数は、現在探索を行っている分岐ノードを示す。
続いて、ステップＳ２０６では、childのノードに、更にchildとそのbrotherがあるか否かが判定される。今、図１４に示されるように、child=10には、更にchild=4と、そのbrother=9があるので、この判定はＹＥＳとなる。この結果、ステップＳ２０７へ移行する。
【００７４】
ステップＳ２０７では、ptrnext変数の値が＋１される。即ち、ptrnext=0+1=1とされる。
続いて、ステップＳ２０８では、branchlvl配列のlevel変数の値に対応する配列位置に、レベル（level+1）のインデックスとして、ptrnext変数の値が格納される。上記配列位置に既に値が格納されている場合には、この処理は実行されない。今、図７（ａ）の７０２として示されるように、branchlvl配列の配列位置１（level=1）に、レベル２（=level+1）のインデックスとして、ptrnext=1が格納される。
【００７５】
続いて、ステップＳ２０９では、childのノード番号がbranch配列のptrnextの値に対応する配列位置に格納される。ここでは、図７（ｂ）の７０５に示されるように、child=10がbranchの配列位置1に格納される。
【００７６】
続いて、ステップＳ２１２では、childstart変数で示されるノードにbrotherがあるか否かが判定される。今、図１４に示されるように、childstart=10にbrother=20があるので、この判定はＹＥＳとなる。この結果、ステップＳ２１３へ移行する。
【００７７】
ステップＳ２１３では、childstart変数の値とchildの値がchildstart変数で示されるノードのbrotherのノード値で置き換えられる。今、childstart=20、child=20とされる。続いて、ステップＳ２０６へ移行する。
【００７８】
図１４に示されるように、child=20には、更にその子としてchild=19があるが、そのbrotherはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
【００７９】
上述のようにchild=20には更にchild=19があるので、ステップＳ２１０の判定はＹＥＳとなる。この結果、ステップＳ２１１に移行する。
ステップＳ２１１では、childのchildでchildが置き換えられる。即ち、child=19となる。続いて、ステップＳ２０６に移行する。
【００８０】
以下、ステップＳ２０６→Ｓ２１０→Ｓ２１１→Ｓ２０６の処理が繰り返されることにより、childのノードが、図１４に示されるように、19→18→17→16→15→14→13→12→11という順で移行してゆく。
【００８１】
child=11になってステップＳ２０６が実行されたときに、図１４に示されるように、child=11の下にchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
【００８２】
上述のようにchild=11の下にはchildはないので、ステップＳ２１０の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
図１４に示されるように、childstart=20にはbrotherがないので、ステップＳ２１２の判定はＮＯとなる。この結果、ステップＳ２１４へ移行する。
【００８３】
ステップＳ２１４では、ptrsearch変数の値が＋１される。即ち、ptrsearch=0+1=1とされる。続いて、ステップＳ２０３に移行する。
図７（ｂ）の７０４として示されるようにレベル１の分岐ノードは１つ（＝ノード２１）のみであり、ptrsearch=1＞levelend=0となるので、ステップＳ２０３の判定はＮＯとなる。この結果、ステップＳ２１５へ移行する。
【００８４】
ステップＳ２１５では、レベル２のための更新処理が実行される。即ち、レベル２の先頭配列位置levelstartが、レベル１の末尾配列位置levelendの次の（＋１した）配列位置とされる。また、レベル２の末尾配列位置levelendは、branch配列の現在の末尾配列位置ptrnextとされる。そして、変数lenの値として、len=levelend-levelstart+1が計算される。また、現在のレベルを示す変数level値がインクリメントされる。
【００８５】
ステップＳ２１６では、変数lenの値が０よりも大きいか否かが判定される。直前のレベルにて分岐ノード群が検出されていれば、ptrnext値がインクリメントされておりそれに従ってlevelend値もインクリメントされて変数lenの値は０より大きくなる。この結果、ステップＳ２１６の判定がＹＥＳとなって、ステップＳ２０３に移行し、直前のレベルにて検出された分岐ノード群に対して更に探索が続行される。直前のレベルにて分岐ノード群が検出されていなければステップＳ２１６の判定はＮＯとなって、全ての処理を終了する。
【００８６】
今、ステップＳ２１５にて、levelstart=0+1=1、levelend=ptrnext=1、len=1-1+1=1、level=1+1=2となる。この結果、len=1＞０となってステップＳ２１６の判定はＹＥＳとなる。続いて、ステップＳ２０３に移行する。
【００８７】
ptrsearch=1≦levelend=1となるので、ステップＳ２０３の判定はＹＥＳとなる。この結果、ステップＳ２０４へ移行する。
branch内の配列位置=ptrsearch=1のノード１０（図７（ｂ）の７０５）には、図１４に示されるように、child=4があるので、ステップＳ２０４の判定はＹＥＳとなる。この結果、ステップＳ２０５へ移行する。
【００８８】
ステップＳ２０５では、childstart=4とされる。
続いて、図１４に示されるように、child=4には、更にchild=2と、そのbrother=3があるので、ステップＳ２０６の判定はＹＥＳとなる。この結果、ステップＳ２０７へ移行する。
【００８９】
ステップＳ２０７では、ptrnext=1+1=2とされる。
続いて、ステップＳ２０８では、図７（ａ）の７０３に示されるように、branchlvl配列の配列位置level=2に、レベル３（=level+1）のインデックスとして、branch配列の末尾の配列位置ptrnext=2が格納される。
【００９０】
続いて、ステップＳ２０９では、child=4がbranch配列の末尾のｐ配列位置ptrnext=2に格納される。続いて、ステップＳ２１２へ移行する。
図１４に示されるように、childstart=4にはbrother=9があるので、ステップＳ２１２の判定はＹＥＳとなる。この結果、ステップＳ２１３へ移行する。
【００９１】
ステップＳ２１３では、childstart=9、child=9とされる。続いて、ステップＳ２０６へ移行する。
図１４に示されるように、child=9には、child=8があるが、そのbrotherはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
【００９２】
上述のようにchild=9にはchild=8があるので、ステップＳ２１０の判定はＹＥＳとなる。この結果、ステップＳ２１１に移行する。
ステップＳ２１１では、child=8となる。続いて、ステップＳ２０６に移行する。
【００９３】
図１４に示されるように、child=8には、child=7があるが、そのbrotherはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
上述のようにchild=8にはchild=7があるので、ステップＳ２１０の判定はＹＥＳとなる。この結果、ステップＳ２１１に移行する。
【００９４】
ステップＳ２１１では、child=7となる。続いて、ステップＳ２０６に移行する。
図１４に示されるように、child=7には、更にchild=5と、そのbrother=6があるので、ステップＳ２０６の判定はＹＥＳとなる。この結果、ステップＳ２０７へ移行する。
【００９５】
ステップＳ２０７では、branch配列の末尾の配列位置がptrnext=2+1=3とされる。
続いて、branchlvl配列の配列位置２（＝level）に、レベル３（=level+1）のインデックス＝２が既にあるから、ステップＳ２０８の処理は実行されない。
【００９６】
続いて、ステップＳ２０９では、child=7がbranch配列の末尾の配列位置ptrnext=3に格納される。続いて、ステップＳ２１２へ移行する。
図１４に示されるように、childstart=9にはbrotherがないので、ステップＳ２１２の判定はＮＯとなる。この結果、ステップＳ２１４へ移行する。
【００９７】
ステップＳ２１４では、ptrsearch=1+1=2とされる。続いて、ステップＳ２０３に移行する。
図７（ｂ）の７０５として示されるようにレベル２の分岐ノードは１つ（＝ノード１０）のみであり、ptrsearch=2＞levelend=1となるので、ステップＳ２０３の判定はＮＯとなる。この結果、ステップＳ２１５へ移行する。
【００９８】
今、ステップＳ２１５にて、levelstart=1+1=2、levelend=ptrnext=3、len=3-2+1=2、level=2+1=3となる。この結果、len=2＞０となってステップＳ２１６の判定はＹＥＳとなる。続いて、ステップＳ２０３に移行する。
【００９９】
ptrsearch=2≦levelend=3となるので、ステップＳ２０３の判定はＹＥＳとなる。この結果、ステップＳ２０４へ移行する。
図１４に示されるように、branch配列内の配列位置ptrsearch=2のノード４にはchild=2があるので、ステップＳ２０４の判定はＹＥＳとなる。この結果、ステップＳ２０５へ移行する。
【０１００】
ステップＳ２０５では、childstart=2とされる。
図１４に示されるように、child=2には、child=1があるが、そのbrotherはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
【０１０１】
上述のように、child=2にはchild=1があるので、ステップＳ２１０の判定はＹＥＳとなる。この結果、ステップＳ２１１に移行する。
ステップＳ２１１では、child=1となる。続いて、ステップＳ２０６に移行する。
【０１０２】
図１４に示されるように、child=1はリーフノードであってchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
上述のようにchild=1にはchildはないので、ステップＳ２１０の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
【０１０３】
図１４に示されるように、childstart=2にbrother=3があるので、ステップＳ２１２の判定はＹＥＳとなる。この結果、ステップＳ２１３へ移行する。
ステップＳ２１３では、childstart=3、child=3とされる。続いて、ステップＳ２０６へ移行する。
【０１０４】
図１４に示されるように、child=3はリーフノードであってchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
図１４に示されるように、childstart=3にはbrotherがないので、ステップＳ２１２の判定はＮＯとなる。この結果、ステップＳ２１４へ移行する。
【０１０５】
ステップＳ２１４では、ptrsearch=2+1=3とされる。続いて、ステップＳ２０３に移行する。
図７（ｂ）の７０６及び７０７として示されるようにレベル３の分岐ノードは２つ（＝ノード４及び７）であり、現在ノード４の処理が終わってノード７の処理に移っており、ptrsearch=3≦levelend=3となるので、ステップＳ２０３の判定はＹＥＳとなる。この結果、ステップＳ２０４へ移行する。
【０１０６】
branch内の配列位置ptrsearch=3のノード７には、図１４に示されるように、child=5があるので、ステップＳ２０４の判定はＹＥＳとなる。この結果、ステップＳ２０５へ移行する。
【０１０７】
ステップＳ２０５では、childstart=5とされる。
続いて、図１４に示されるように、child=5はリーフノードでありchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
【０１０８】
図１４に示されるように、childstart=5にbrother=6があるので、ステップＳ２１２の判定はＹＥＳとなる。この結果、ステップＳ２１３へ移行する。
ステップＳ２１３では、childstart=6、child=6とされる。続いて、ステップＳ２０６へ移行する。
【０１０９】
図１４に示されるように、child=6はリーフノードでありchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
図１４に示されるように、childstart=6にはbrotherがないので、ステップＳ２１２の判定はＮＯとなる。この結果、ステップＳ２１４へ移行する。
【０１１０】
ステップＳ２１４では、ptrsearch=3+1=4とされる。続いて、ステップＳ２０３に移行する。
図７（ｂ）の７０６及び７０７として示されるようにレベル３の分岐ノードは２つ（＝ノード４及び７）であり、ノード４とノード７の処理が共に終了しており、ptrsearch=4＞levelend=3となるので、ステップＳ２０３の判定はＮＯとなる。この結果、ステップＳ２１５へ移行する。
【０１１１】
ステップＳ２１５では、levelstart=3+1=4、levelend=ptrnext=3、len=3-4+1=0、level=3+1=4となる。この結果、len=0=0となってステップＳ２１６の判定はＮＯとなって、全ての処理を終了する。
【０１１２】
以上のようにして、エリミネーションツリーが解析され、図７（ａ）に例示されるbranchlvl配列及び図７（ｂ）に例示されるbranch配列が生成される。
次に、図３は、図１のメモリ割付チェイン生成部１０２が実行する前述のステップ２．から４．のメモリ割付チェイン生成処理の詳細を示す動作フローチャートである。ここでは、エリミネーションツリー上の各ノードに対して、メモリ格納領域が割付けられる。
【０１１３】
まず、例として、並列計算の処理結果を保存する領域が、２つのメモリ格納領域に分割されていると仮定する。今、例えば２つのメモリ格納領域に図１４に示されるようなエリミネーションツリーを構成するノードが割り付けられる場合、例えば図８に示されるようなデータ構成を採用することができる。
【０１１４】
まず、図８（ａ）に例示されるように、エリミネーションツリーを構成する各ノードに配列位置が一意に対応する１次元ノード配列８００が用意される。例えば、配列位置０は図１４のノード２１に対応し、配列位置１は図１４のノード１０に対応し、配列位置２は図１４のノード４に対応するといった如くである。そして、メモリ格納領域１において実行されるノード群はその実行順に、割付チェインchain1に割り付けられる。この場合まず、図８（ａ）に示されるように、割付チェインchain1の先頭を示すレジスタ８０１が用意され、このレジスタ８０１に、メモリ格納領域１にて実行される最初のノードに対応する１次元ノード配列８００上の配列位置が格納される。次に、このレジスタ８０１から参照される１次元ノード配列８００上の配列位置には、２番目に実行されるノードに対応する１次元ノード配列８００の配列位置が格納される。以下同様にして、１次元ノード配列８００上の各配列位置に、その配列位置に対応するノードの次に実行されるノードに対応する配列位置が格納されてゆく。最後に実行されるノードの配列位置には、nullデータが格納される。このようにして、割付チェインchain1として、レジスタ８０１から順次１次元ノード配列８００上の配列位置が辿られることにより、メモリ格納領域１において実行されるノードとその実行順を設定することができる。割付チェインchain1の場合と同様にして、メモリ格納領域２において実行されるノード群もその実行順に、割付チェインchain2に割り付けられる。この場合まず、図８（ａ）に示されるように、割付チェインchain2の先頭を示すレジスタ８０２が用意され、このレジスタ８０２に、メモリ格納領域２にて実行される最初のノードに対応する１次元ノード配列８００の配列位置が格納される。次に、このレジスタ８０２から参照される１次元ノード配列８００上の配列位置には、２番目に実行されるノードに対応する１次元ノード配列８００の配列位置が格納される。以下同様にして、１次元ノード配列８００上の各配列位置に、その配列位置に対応するノードの次に実行されるノードに対応する配列位置が格納されてゆく。最後に実行されるノードの配列位置には、nullデータが格納される。
【０１１５】
以下の説明において、連続にメモリデータを割り当てるセクション（メモリ格納領域）のことをpool（プール）と呼び、その数を#poolと表記する。即ち、ここの仮定では、#pool=2である。
【０１１６】
図３の動作フローチャートにおいて、まず、図７（ａ）に示されるbranchlvl配列と図７（ｂ）に示されるbranch配列がアクセスされることにより、#pool以上の要素数を有する分岐ノード集合が見つけられる（ステップＳ３０１）。ここで、branchlvl配列とbranch配列は、図２の動作フローチャートで示される分岐ノード集合検出処理によって得られている。図７に示される配列構造の例から、レベル１（level 1）の分岐ノード集合は｛21｝（ノード２１を要素とする集合）となる。次に、レベル２（level 2）の分岐ノード集合は{10}（ノード１０を要素とする集合）となる。更に、レベル３（level 3）の分岐ノード集合は{4,7}（ノード４とノード７の集合）となる。そして、#pool=2とすると、２以上の要素数を有する分岐ノード集合は、level 3の分岐ノード集合{4,7}である。この結果、ステップＳ３０２の判定がＹＥＳとなる。
【０１１７】
以上のステップＳ３０１とＳ３０２の処理により、メモリ割付チェイン生成部１０２による前述のステップ２．の処理が実現される。
次に、ステップＳ３０１で見つかったlevel集合から、１つのノード＝分岐ノードが取り出され、nodelvlとされる（ステップＳ３０３）。ここでは例えば、level 3の集合{4,7}からノード４がnodelvlとして取り出される。
【０１１８】
次に、図８（ｂ）に例示されるような分岐ノード指示用１次元配列nmarkが用意される。図８（ｂ）の１次元配列nmarkは、配列要素数が図８（ａ）の１次元ノード配列８００と同じであり、図８（ａ）と同じ配列位置は同じノードに対応している。そして、各配列位置のノードが分岐ノードである場合には、その分岐ノードに対応する分岐ノード指示用１次元配列nmark上の配列位置にon（オン）を示す値が設定される。ここで、分岐ノード指示用１次元配列nmarkにおいて、ステップＳ３０３にて取り出されたノードnodelvl=4に対応する配列位置の配列要素が、onを示す値に設定される（ステップＳ３０４）。なお、nmark配列の各配列要素は、初期状態において全てクリアされている。
【０１１９】
次に、ノードnodelvlに対応するfirstdescendantのノードがfstdecs変数に設定される（ステップＳ３０５）。図１４の例では、ノード４に対するfirstdescendantのノードはノード１であり、fstdecs=1である。
【０１２０】
続いて、現在選択されているpoolの割付チェイン（chain1又はchain2）に、fstdecsノードからnodelvlノードまでポストオーダで、順番に現在のsubtreeの構成要素ノードが接続される（ステップＳ３０６）。今例えば、pool１が選択されており、割付チェイン＝chain1とする。そして、fstdecs=1からnodelvl=4までのポストオーダは、図１４に示されるように、ノード１→ノード２→ノード３→ノード４である。従って、割付チェインchain1は、次のようになる。
chain1={1→2→3→4} ・・・（４）
この割付チェインchain1が、例えば図８（ａ）に示されるデータ構造を使って形成される。
【０１２１】
次に、現在選択されているpoolが、次式によりサイクリックに変更される（ステップＳ３０７）。なお、poolは、現在選択されているpool番号を示す変数である。また、mod(A,B)は、AをBで割った剰余を求める演算を示す。
pool＝mod(pool,#pool)+1 ・・・（５）
今、#pool=2であり、現在のpool番号pool=1とすれば、上記計算の結果、新たなpool番号はpool=2となる。なお逆に、現在のpool番号pool=2とすれば、上記計算の結果、新たなpool番号はpool=1となる。
ここで、現在のpoolが1から2に変化した後、ステップＳ３０１で見つかったlevel集合に残りがあるか否かが判定される（ステップＳ３０８）。
【０１２２】
前述のlevel 3の集合{4,7}の場合、まだノード７が残っている。従って、ステップＳ３０８の判定がＹＥＳとなり、ステップＳ３０３の処理に戻る。この結果、level 3の集合{4,7}からノード７が取り出される（ステップＳ３０３）。次に、１次元配列nmark上の上記ノードnodelvl=7に対応する配列位置の配列要素が、onを示す値に設定される（ステップＳ３０４）。更に、nodelvlノード=4に対するfirstdescendantのノードとして、fstdecs=5が設定される（ステップＳ３０５）（図１４参照）。続いて、現在選択されているpool=2の割付チェイン＝chain2に、fstdecs=5からnodelvl=7までポストオーダで、順番に現在のsubtreeの構成要素ノードノード５→ノード６→ノード７が接続される（ステップＳ３０６）。従って、割付チェインchain2は、次のようになる。
chain2={5→6→7} ・・・（６）
以上のステップＳ３０３からＳ３０８の処理により、メモリ割付チェイン生成部１０２による前述のステップ３．の処理が実現される。
【０１２３】
次に、分岐ノード指示用１次元配列nmarkの配列要素がonとなっている分岐ノード又はリーフノードの何れかに辿り着くまで、エリミネーションツリーのルートノードから順に各ノードが辿られる。ここでは、図８（ｃ）に示される１次元のwork配列が用意され、ルートから同じ並列レベルのノードが辿られ、辿られたノードがwork配列に順次格納されてゆく。この処理は、図３のステップＳ３０９からＳ３１３までの処理によって実現される。これらの処理について、図９の動作説明図を用いながら説明する。
【０１２４】
まず、ステップＳ３０９で、ルートノードが、分岐ノード指示用１次元配列nmark上でonされていなければwork配列に格納される。格納されればnodeend=1、格納されなければnodeend=0とされる。通常は、ルートノードはnmark上でonされていないため、nodeend=1となる（図９の行１）。nodeend=0となる場合は特殊な場合である。nodeendは、work配列の末尾の格納位置を示す。nodestartは、対象ノードのサーチ位置を示す。
【０１２５】
次に、ステップＳ３１０で、nodestart=1とされる（図９の行２）。なお、work配列の先頭の配列位置は１とする。
次に、ステップＳ３１１では、nodestart≦nodeendが成立するか否かが判定される。図９の行３の状態では、ステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１２６】
ステップＳ３１２では、nodestartで示されるノードがwork配列から取り出され、そのノード（以下「対象ノード」と呼ぶ）のchild,brotherのノードが調べられる。そして、調べられたノードがnmark配列上でonされていないなら、nodeend=nodeend+1とされて、nodeendで示されるwork配列上の配列位置に、その調べられたノードが格納される。図９の行４の状態では、nodestart=1で示される配列位置のノード２１がwork配列から取り出され、そのノード２１のchild,brotherのノードが調べられる。ノード２１は、図９の行１でwork配列の配列位置１にセットされている。図１４の例では、ノード２１のchildノードであるノード１０、そのbrotherノードであるノード２０の各ノードが調べられる。まず、ノード１０は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされてはいない。このため、nodeend=1+1=2で示されるwork配列上の配列位置２に、ノード１０が格納される（図９の行４）。続いて、ノード２０も、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされてはいない。このため、nodeend=2+1=3で示されるwork配列上の配列位置３に、ノード２０が格納される（図９の行５）。
【０１２７】
対象ノードの全てのchild,brotherのノードのサーチが終了すると、ステップＳ３１３にて、nodestart=nodestart+1とされる。図９の行６の状態では、nodestart=1+1=2とされる。続いて、ステップＳ３１１に移行する。
【０１２８】
図９の行７の状態では、nodestart=2≦nodeend=3でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
ステップＳ３１２において、図９の行８の状態では、nodestart=2で示される配列位置の対象ノード１０がwork配列から取り出され、その対象ノード１０のchild,brotherのノードが調べられる。対象ノード１０は、図９の行４でwork配列の配列位置２にセットされている。図１４の例では、対象ノード１０のchildノードであるノード４、そのbrotherノードであるノード９の各ノードが調べられる。まず、ノード４は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象となっており、nmark配列上でonされている。このため、ノード４はwork配列には格納されない。続いて、ノード９は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされてはいない。このため、nodeend=3+1=4で示されるwork配列上の配列位置４に、ノード９が格納される（図９の行８）。
【０１２９】
図９の行９の状態では、ステップS３１３において、nodestart=2+1=3とされる。続いて、ステップＳ３１１に移行する。
図９の行１０の状態では、nodestart=3≦nodeend=4でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３０】
ステップＳ３１２において、図９の行１１の状態では、nodestart=3で示される配列位置の対象ノード２０がwork配列から取り出され、その対象ノード２０のchild,brotherのノードが調べられる。対象ノード２０は、図９の行５でwork配列の配列位置３にセットされている。図１４の例では、対象ノード２０のchildノードであるノード１９が調べられる。即ち、ノード１９は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされていない。このため、nodeend=4+1=5で示されるwork配列上の配列位置５に、ノード１９が格納される（図９の行１１）。
【０１３１】
図９の行１２の状態では、ステップＳ３１３において、nodestart=3+1=4とされる。続いて、ステップＳ３１１に移行する。
図９の行１３の状態では、nodestart=4≦nodeend=5でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３２】
ステップＳ３１２において、図９の行１４の状態では、nodestart=4で示される配列位置の対象ノード９がwork配列から取り出され、その対象ノード９のchild,brotherのノードが調べられる。対象ノード９は、図９の行８でwork配列の配列位置４にセットされている。図１４の例では、対象ノード９のchildノードであるノード８が調べられる。即ち、ノード８は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされていない。このため、nodeend=5+1=6で示されるwork配列上の配列位置６に、ノード８が格納される（図９の行１４）。
【０１３３】
図９の行１５の状態では、ステップＳ３１３において、nodestart=4+1=5とされる。続いて、ステップＳ３１１に移行する。
図９の行１６の状態では、nodestart=5≦nodeend=6でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３４】
ステップＳ３１２において、図９の行１７の状態では、nodestart=5で示される配列位置の対象ノード１９がwork配列から取り出され、その対象ノード１９のchild,brotherのノードが調べられる。対象ノード１９は、図９の行１１でwork配列の配列位置５にセットされている。図１４の例では、対象ノード１９のchildノードであるノード１８が調べられる。即ち、ノード１８は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされていない。このため、nodeend=6+1=7で示されるwork配列上の配列位置７に、ノード１８が格納される（図９の行１７）。
【０１３５】
図９の行１８の状態では、ステップＳ３１３において、nodestart=5+1=6とされる。続いて、ステップＳ３１１に移行する。
図９の行１９の状態では、nodestart=6≦nodeend=7でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３６】
ステップＳ３１２において、図９の行２０の状態では、nodestart=6で示される配列位置の対象ノード８がwork配列から取り出され、その対象ノード８のchild,brotherのノードが調べられる。対象ノード８は、図９の行１４でwork配列の配列位置６にセットされている。図１４の例では、対象ノード８のchildノードであるノード７が調べられる。即ち、ノード７は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっており、nmark配列上でonされている。このため、ノード７はwork配列には格納されない（図９の行２０）。
【０１３７】
図９の行２１の状態では、ステップＳ３１３において、nodestart=6+1=7とされる。続いて、ステップＳ３１１に移行する。
図９の行２２の状態では、nodestart=7＝nodeend=7でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３８】
ステップＳ３１２において、図９の行２３の状態では、nodestart=7で示される配列位置の対象ノード１８がwork配列から取り出され、その対象ノード１８のchild,brotherのノードが調べられる。対象ノード１８は、図９の行１７でwork配列の配列位置７にセットされている。図１４の例では、対象ノード１８のchildノードであるノード１７が調べられる。即ち、ノード１７は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされていない。このため、nodeend=7+1=8で示されるwork配列上の配列位置８に、ノード１７が格納される（図９の行２３）。
【０１３９】
以下同様の処理が実行され、work配列上の配列位置９〜１４に、ノード１６〜ノード１１が順次格納される（図９の行２４〜行４１）。
図９の行４２の状態では、ステップＳ３１３において、nodestart=13+1=14とされる。続いて、ステップＳ３１１に移行する。
【０１４０】
図９の行４３の状態では、nodestart=14＝nodeend=14でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
ステップＳ３１２において、図９の行４４の状態では、nodestart=14で示される配列位置の対象ノード１１がwork配列から取り出されるが、図１４に示されるように、対象ノード１１にはchild,brotherのノードがない。このため、work配列へのノード格納は行われない（図９の行４４）。なお、対象ノード１１は、図９の行４１でwork配列の配列位置１４にセットされている。
【０１４１】
図９の行４５の状態では、ステップＳ３１３において、nodestart=14+1=15とされる。続いて、ステップＳ３１１に移行する。
図９の行４６の状態では、nodestart=15＝nodeend=14でステップＳ３１１の判定がＮＯとなり、ステップＳ３１１の判定がＮＯとなって、ステップＳ３１４に移行する。
【０１４２】
以上説明した図３のステップＳ３０９からＳ３１３までの処理によって、nmark配列でonとなっている分岐ノード又はリーフノードの何れかに辿り着くまで、エリミネーションツリーのルートノードから順に各ノードを辿った結果が、work配列に得られる。図１４に対応する図８の例では、work配列に得られた結果は次のようになる。
work＝｛21|10,20|9,19|8,18|17|16|15|14|13|12|11｝ ・・・（７）
ここで、区切り記号「｜」は、レベルの境界を示している。
【０１４３】
以上のようにしてwork配列が確定したら、ステップＳ３１４にて、n=nodeendから１まで１ずつ減じられながら辿られた順の逆順で各work配列要素work(n)のノードが順次取り出される。そして、work配列から順次取り出されたノードが、前述の（４）式及び（６）式として得られている割付チェインchain1及びchain2の末尾に、交互にサイクリックに追加されてゆく。この結果、割付チェインchain1及びchain2は、次のようになる。
chain1＝{1→2→3→4→11→13→15→17→8→9→10} ・・・（８）
chain2＝{5→6→7→12→14→16→18→19→20→21} ・・・（９）
【０１４４】
以上の処理により、ノードのメモリ割付け及び処理順が確定する。最後に、ステップＳ３１５にて、プール毎の割付チェインchain1又はchain2がプール番号順に取り出され、各割付チェインが辿られてノードが取り出され、各ノードに対して順番にメモリ格納領域が割り付けられる。
【０１４５】
前述したように、スパースな正値対象行列Lにおけるノードi の列ベクトルliの大きささは、symbolic decompositionと呼ばれる解析で求めることができる。各ノードに対するLDL^T分解計算結果は、各ノードが登録されている割付チェインに対応するメモリ格納領域に格納されることになる。即ち、chain1に接続される各ノードの処理結果が、この割付チェインでの各ノードの接続順で、メモリ格納領域の前半部分に割り当てられて格納される。同様に、chain2に接続される各ノードの処理結果が、この割付チェインでの各ノードの接続順で、メモリ格納領域の後半部分に割り当てられて格納される。
【０１４６】
今、上述の割付チェインchain1及びchain2に基づく各メモリ格納領域へのノード割当ての順番の対応表は、例えば図１０（ａ）に示されるデータ構成例を有するアサインテーブル（assign table）に保持される。
【０１４７】
また、compressed column storage（圧縮列格納方式）の場合と同様に、相対的な割付順番がmであるノードに対応するpanel（columnを格納する領域）の先頭がメモリ格納領域のどの位置に存在するかが計算されて、その先頭位置を示す値が例えば図１０（ｂ）に示される１次元配列に格納される。
【０１４８】
また実際には、ノードに対するLDL^T分解結果は、非ゼロ要素を含む行のみが圧縮されて２次元配列のpanelに格納される。このため、panel毎にその１次元目の大きささと２次元目の大きさを対で記憶する例えば図１０（ｃ）に示される１次元配列も用意される。
【０１４９】
更には、非ゼロ要素を含む行を指示するためのインデクスの先頭位置を示す値が格納される例えば図１０（ｄ）に示される１次元配列も用意される（図１０（ｅ）参照）。
ステップＳ３１５では、図１０に示されるようなメモリ割当て制御用のデータ群に対して、割付チェインchain1及びchain2に基づいてデータ設定が行われる。後述するLDL^T分解処理の実行時には、これらのデータ群が随時参照されて各ノードの計算結果をメモリ格納領域に割り当てるための制御が実行されることになる。
【０１５０】
次に、図４は、図１のタスクチェイン生成部１０３が実行する前述のステップ５．から７．の動作の詳細を示す動作フローチャートである。ここでは、エリミネーションツリー上の各ノードが、スレッドでの並列計算を制御するためのタスクチェインに登録される。
【０１５１】
タスクチェインは、subtree chainとnode chainを含む。タスクチェインのデータ構造の例としては、メモリ割付チェイン生成処理における割付チェインの場合と同様に、図８（ａ）に示されるようなデータ構造を採用することができる。また、以下の処理において使用される分岐ノード指示用１次元配列nmarkとwork配列のデータ構造例としても、メモリ割付チェイン生成処理の場合と同様の、図８（ｂ）と（ｃ）に示されるようなデータ構造を採用することができる。
【０１５２】
以下の説明では、並列実行されるスレッド数が２である場合の例について説明する。ここで、スレッド数を#threadと表現する。
図４の動作フローチャートにおいて、まず、図７（ａ）に示されるbranchlvl配列と図７（ｂ）に示されるbranch配列がアクセスされることにより、#thread以上の要素数を有する分岐ノード集合が見つけられる（ステップＳ４０１）。ここで、branchlvl配列とbranch配列は、図２の動作フローチャートで示される分岐ノード集合検出処理によって得られている。図７に示される配列構造の例から、レベル１（level 1）の分岐ノード集合は｛21｝（ノード２１を要素とする集合）となる。次に、レベル２（level 2）の分岐ノード集合は{10}（ノード１０を要素とする集合）となる。更に、レベル３（level 3）の分岐ノード集合は{4,7}（ノード４とノード７の集合）となる。そして、#thread=2とすると、２以上の要素数を有する分岐ノード集合は、level 3の分岐ノード集合{4,7}である。この結果、ステップＳ４０２の判定がＹＥＳとなる。
【０１５３】
以上のステップＳ４０１とＳ４０２の処理により、タスクチェイン生成部１０３による前述のステップ５．の処理が実現される。
【０１５４】
次に、ステップＳ４０１で見つかったlevel集合から、１つのノード＝分岐ノードが取り出され、nodelvlとされる（ステップＳ４０３）。ここでは例えば、level 3の集合{4,7}からノード４がnodelvlとして取り出される。
【０１５５】
次に、図８（ｂ）に例示されるような分岐ノード指示用１次元配列nmarkが用意される。図８（ｂ）の１次元配列nmarkは、配列要素数が図８（ａ）の１次元ノード配列８００と同じであり、図８（ａ）と同じ配列位置は同じノードに対応している。そして、各配列位置のノードが分岐ノードである場合には、その分岐ノードに対応する分岐ノード指示用１次元配列nmark上の配列位置にon（オン）を示す値が設定される。ここで、分岐ノード指示用１次元配列nmarkにおいて、ステップＳ４０３にて取り出されたノードnodelvl=4に対応する配列位置の配列要素が、onを示す値に設定される（ステップＳ４０４）。なお、nmark配列の各配列要素は、初期状態において全てクリアされている。
【０１５６】
次に、ノードnodelvlに対応するfirstdescendantのノードがfstdecs変数に設定される（ステップＳ４０５）。図１４の例では、ノード４に対するfirstdescendantのノードはノード１であり、fstdecs=1である。
【０１５７】
続いて、subtree chainと呼ばれる第１のタスクチェインに、ノードnodelvlが加えられる（ステップＳ４０６）。即ち、subtree chainは、次のようになる。
subtree chain={4} ・・・（１０）
このsubtree chainが、例えば図８（ａ）に示されるデータ構造を使って形成される。
【０１５８】
次に、ステップＳ４０１で見つかったlevel集合に残りがあるか否かが判定される（ステップＳ４０７）。
前述のlevel 3の集合{4,7}の場合、まだノード７が残っている。従って、ステップＳ４０７の判定がＹＥＳとなり、ステップＳ４０３の処理に戻る。この結果、level 3の集合{4,7}からノード７が取り出される（ステップＳ４０３）。次に、１次元配列nmark上の上記ノードnodelvl=7に対応する配列位置の配列要素が、onを示す値に設定される（ステップＳ４０４）。更に、nodelvlノード=4に対するfirstdescendantのノードとして、fstdecs=5が設定される（ステップＳ４０５）（図１４参照）。続いて、subtree chainに、ノードnodelvlが加えられる（ステップＳ４０６）。従って、subtree chainは、次のようになる。
subtree chain={4→7} ・・・（１１）
【０１５９】
以上のステップＳ４０３からＳ４０７の処理により、タスクチェイン生成部１０３による前述のステップ６．の処理が実現される。
【０１６０】
次に、分岐ノード指示用１次元配列nmarkの配列要素がonとなっている分岐ノード又はリーフノードの何れかに辿り着くまで、エリミネーションツリーのルートノードから順に各ノードが辿られる。ここでは、図３の動作フローチャートで示したメモリ割付チェイン生成処理の場合と全く同様に、図８（ｃ）に示される１次元のwork配列が用意され、ルートから同じ並列レベルのノードが辿られ、辿られたノードがwork配列に順次格納されてゆく。この処理は、図４のステップＳ３０９からＳ３１３までの処理によって実現される。これらの処理は、前述のメモリ割付チェイン生成処理における図３のステップＳ３０９からＳ３１３までの処理と同じ処理である。これらの処理の結果、図１４に対応する図８の例においてwork配列に得られる結果は、前述した（７）式で示されるものとなる。
【０１６１】
以上のようにしてwork配列が確定したら、ステップＳ４０８にて、n=nodeendから１まで１ずつ減じられながら辿られた順の逆順で各work配列要素work(n)のノードが順次取り出される。そして、work配列から順次取り出されたノードが、第２のタスクチェインであるnode chainに加えられてゆく。この結果、node chainは、次のようになる。
node chain＝{11→12→13→14→15→16→17→18→19→20→10→21}
・・・（１２）
【０１６２】
以上の処理により、第１のタスクチェインであるsubtree chainと、第２のタスクチェインであるnode chainによって、タスクの実行におけるノードの実行順が確定する。
【０１６３】
図５は、図１のLDL^T分解実行部１０４が実行する前述のステップ８．のLDL^T分解実行処理の詳細を示す動作フローチャートである。ここでは、subtree chain、node chainの順番で、各タスクチェインに接続されている各ノードがスレッドの並列数ずつ取り出され、各スレッドのタスクに割り当てられる。
【０１６４】
図５において、まず、ステップＳ５０１において、#thread 数だけタスクが生成される。以下、ステップＳ５０２からＳ５１２は、各スレッド毎に独立して実行される。
各スレッドでは、ステップＳ５０２において、変数snodeと変数nnodeの各値が０に初期設定される。
【０１６５】
次に、例えば第１のスレッドでは、ステップＳ５０３において、図１のタスクチェイン生成部１０３によって生成されたsubtree chainとnode chainがlock（ロック）される。これ以後、第１のスレッドがsubtree chainとnode chainがunlockするまでの間、第２のスレッドは、subtree chainとnode chainへのアクセスを待たされることになる。
【０１６６】
第１のスレッドでは、ステップＳ５０４にて、subtree chainにノードがあるか否かが判定される。
subtree chainにノードがあってステップＳ５０４の判定がＹＥＳの場合、第１のスレッドでは、ステップＳ５０５において、subtree chain の先頭ノードが取り出され、そのノード番号が変数snode に設定され、その後、subtree chainの次のノードが先頭に設定される。今、図８（ａ）に示されるデータ構造において、chain1がsubtree chainであったとした場合において、subtree chainが例えば前述の（１１）式で示されるように得られている場合を考える。この場合、図８（ａ）のレジスタ８０１には、１次元配列８００上のノード４に対応する配列位置が格納されている。また、１次元配列８００上のノード４に対応する配列位置には、１次元配列８００上のノード７に対応する配列位置が格納されている。１次元配列８００上のノード７に対応する配列位置には、nullデータが格納されている。このような例において、第１のスレッドでは、ステップＳ５０５において、レジスタ８０１に格納されている配列位置が、ノード４のノード番号として変数snodeに設定される。その後、レジスタ８０１からアクセスできる１次元配列８００上のノード４に対応する配列位置に格納されているノード７の配列位置が、新たにレジスタ８０１に設定し直される。
【０１６７】
第１のスレッドでは、ステップＳ５０５の処理の後、ステップＳ５０８において、subtree chainとnode chainに対するlockが解除（unlock）される。この結果、第１のスレッドと並列に実行されている第２のスレッドでは、subtree chainとnode chainへのアクセスが可能となる。
【０１６８】
続いて、第１のスレッドでは、ステップS５０９において、変数snodeの値が０であるか否かが判定される。
今、ステップS５０５にてsnodeにノード４のノード番号が設定されたため、ステップS５０９の判定はNOとなる。
【０１６９】
この結果、第１のスレッドでは、ステップＳ５１０にて、変数snodeに設定されているノード番号のノードをルートノードとするsubtreeの各構成ノードに対応する各panelの更新処理が実行される。即ち、前述した（１）式及び（２）式に基づくLDL^T分解処理が、順次実行される。上述の例で、変数snodeに設定されているノード番号に対応するノードがノード４である場合、このノード４をルートノードとするsubtreeの各構成ノードは、図１４より、ノード１、２、３、及び４である。これらのノードに対するpanelの更新処理が、第１のスレッドにおいて順次実行される。このとき、前述したメモリ割付チェイン生成処理における図３のステップＳ３１５にて設定された図１０に示されるようなメモリ割当て制御用のデータ群がアクセスされて、各ノードのメモリ割当てが制御される。
【０１７０】
以上の第１のスレッドによる制御処理と並列に、第２のスレッドにおいても同様の制御処理が実行される。
即ち、第２のスレッドで、ステップＳ５０３にて、subtree chainとnode chainがlockされる。これ以後、第２のスレッドがsubtree chainとnode chainがunlockするまでの間、第１のスレッドは、subtree chainとnode chainへのアクセスを待たされることになる。
【０１７１】
次に、第２のスレッドで、ステップＳ５０４にて、subtree chainにノードがあるか否かが判定される。
subtree chainにノードがあってステップＳ５０４の判定がＹＥＳの場合、第２のスレッドでは、ステップＳ５０５において、subtree chain の先頭ノードが取り出され、そのノード番号が変数snode に設定され、その後、subtree chainの次のノードが先頭に設定される。今、前述の第１のスレッドによるステップＳ５０５の処理によって、図８（ａ）のsubtree chainを示すレジスタ８０１に格納されている配列位置は、ノード４の次のノード７のノード番号を指している。この結果、第２のスレッドによりステップＳ５０５の処理では、ノード７のノード番号が変数snodeに設定される。その後、レジスタ８０１からアクセスできる１次元配列８００上のノード７に対応する配列位置に格納されているnull値が、新たにレジスタ８０１に設定し直される。このnull値は、subtree chainにはこれ以上ノードが無いことを示している。
【０１７２】
第２のスレッドでは、ステップＳ５０５の処理の後、ステップＳ５０８において、subtree chainとnode chainに対するlockが解除（unlock）される。この結果、第２のスレッドと並列に実行されている第１のスレッドでは、subtree chainとnode chainへのアクセスが可能となる。
【０１７３】
続いて、第２のスレッドでは、ステップS５０９において、変数snodeの値が０であるか否かが判定される。
今、ステップS５０５にてsnodeにノード７のノード番号が設定されたため、ステップS５０９の判定はNOとなる。
【０１７４】
この結果、第２のスレッドでは、ステップＳ５１０にて、変数snodeに設定されているノード番号のノードをルートノードとするsubtreeの各構成ノードに対応する各panelの更新処理、即ちLDL^T分解処理が順次実行される。上述の例で、変数snodeに設定されているノード番号に対応するノードがノード７である場合、このノード７をルートノードとするsubtreeの各構成ノードは、図１４より、ノード５、６、及び７である。これらのノードに対するpanelの更新処理が、第２のスレッドにおいて順次実行される。
【０１７５】
以上のようにして、第１のスレッドと第２のスレッドによって、subtree chainに登録されているノード４をルートノードとするsubtreeの構成ノード群に対するpanel更新処理と、ノード７をルートノードとするsubtreeの構成ノード群に対するpanel更新処理が並列に実行されることになる。このとき、前述のメモリ割付チェイン生成処理によって、ノード４をルートノードとするsubtreeの構成ノード群と、ノード７をルートノードとするsubtreeの構成ノード群は、それぞれ異なるメモリ格納領域（プール）に割り付けられている。従って、各subtreeの並列実行において同じメモリ格納領域にアクセスが集中してしまうという事態を回避することが可能となる。
【０１７６】
第１のスレッドでは、前述のステップＳ５１０の処理によってノード４をルートノードとするsubtreeの構成ノード群に対するpanel更新処理が終了すると、再びステップＳ５０２に移行し、変数snodeと変数nnodeがクリアされる。更に、第１のスレッドでは、ステップS５０３にて、subtree chainとnode chainがlockされる。
【０１７７】
続いて、第１のスレッドでは、ステップＳ５０４にて、subtree chainにノードがあるか否かが判定される。今、前述の第２のスレッドによるステップＳ５０５の処理によって、図８（ａ）のsubtree chainを示すレジスタ８０１には、subtree chainにはこれ以上ノードが無いことを示すnull値が設定されている。この結果、ステップＳ５０４の判定はＮＯとなって、第１のスレッドでは、ステップＳ５０６が実行される。
【０１７８】
ステップＳ５０６では、node chainにノードがあるか否かが判定される。
node chainにノードがあってステップＳ５０６の判定がＹＥＳの場合、第１のスレッドでは、ステップＳ５０７において、node chain の先頭ノードが取り出され、そのノード番号が変数ｎnode に設定され、その後、node chainの次のノードが先頭に設定される。今、図８（ａ）に示されるデータ構造において、chain2がnode chainであったとした場合において、node chainが例えば前述の（１２）式で示されるように得られている場合を考える。この場合、図８（ａ）のレジスタ８０２には、１次元配列８００上のノード１１に対応する配列位置が格納されている。また、１次元配列８００上のノード１１に対応する配列位置には、１次元配列８００上のノード１２に対応する配列位置が格納されている。以下、node chainでの各ノードの接続順に従って、各ノードの配列位置にはその次に接続されるノードの配列位置が格納される。そして、最後のノードに対応する配列位置には、nullデータが格納されている。このような例において、第１のスレッドでは、ステップＳ５０７において、レジスタ８０２に格納されている配列位置が、ノード１１のノード番号として変数nnodeに設定される。その後、レジスタ８０２からアクセスできる１次元配列８００上のノード１１に対応する配列位置に格納されているノード１２の配列位置が、新たにレジスタ８０２に設定し直される。
【０１７９】
第１のスレッドでは、ステップＳ５０７の処理の後、ステップＳ５０８において、subtree chainとnode chainに対するlockが解除（unlock）される。
続いて、第１のスレッドでは、ステップS５０９において、変数snodeの値が０であるか否かが判定される。ここで、ステップＳ５０２にて変数snodeが０クリアされた後、ステップＳ５０４の判定はＮＯとなっているため、変数snodeの値は０のままであり、ステップＳ５０９の判定はＹＥＳとなる。
【０１８０】
この結果、第１のスレッドでは、ステップＳ５１１にて更に、変数nnodeの値が０であるか否かが判定される。今、変数nnodeには、ステップＳ５０７にてノード１１のノード番号が格納されているため、ステップＳ５１１の判定はＮＯとなる。
【０１８１】
これにより、第１のスレッドでは、ステップＳ５１２において、変数nnodeに設定されているノード番号に対応するノード１１に対応するpanelの更新処理、即ちLDL^T分解処理が実行される。このとき、前述したメモリ割付チェイン生成処理における図３のステップＳ３１５にて設定された図１０に示されるようなメモリ割当て制御用のデータ群がアクセスされて、各ノードのメモリ割当てが制御される。
【０１８２】
以上の第１のスレッドによる制御処理と並列に、第２のスレッドにおいても更に並列処理が実行される。
即ち、第２のスレッドで、ステップＳ５０３にて、subtree chainとnode chainがlockされる。
【０１８３】
次に、第２のスレッドで、ステップＳ５０４にて、subtree chainにノードがあるか否かが判定される。今、図８（ａ）のsubtree chainを示すレジスタ８０１には、subtree chainにはこれ以上ノードが無いことを示すnull値が設定されている。この結果、ステップＳ５０４の判定はＮＯとなって、第２のスレッドで、ステップＳ５０６が実行される。
【０１８４】
ステップＳ５０６では、node chainにノードがあるか否かが判定される。
node chainにノードがあってステップＳ５０６の判定がＹＥＳの場合、第２のスレッドでは、ステップＳ５０７において、node chain の先頭ノードが取り出され、そのノード番号が変数ｎnode に設定され、その後、node chainの次のノードが先頭に設定される。今、前述の第１のスレッドによるステップＳ５０７の処理によって、図８（ａ）のnode chainを示すレジスタ８０２に格納されている配列位置は、ノード１１の次のノード１２のノード番号を指している。この結果、第２のスレッドによりステップＳ５０７の処理では、ノード１２のノード番号が変数nnodeに設定される。その後、レジスタ８０２からアクセスできる１次元配列８００上のノード１２に対応する配列位置に格納されているノード１３に対応する配列位置が、新たにレジスタ８０２に設定し直される。
【０１８５】
第２のスレッドでは、ステップＳ５０７の処理の後、ステップＳ５０８において、subtree chainとnode chainに対するlockが解除（unlock）される。
続いて、第２のスレッドでは、ステップS５０９において、変数snodeの値が０であるか否かが判定される。ここで、ステップＳ５０２にて変数snodeが０クリアされた後、ステップＳ５０４の判定はＮＯとなっているため、変数snodeの値は０のままであり、ステップＳ５０９の判定はＹＥＳとなる。
【０１８６】
この結果、第２のスレッドでは、ステップＳ５１１にて更に、変数nnodeの値が０であるか否かが判定される。今、変数nnodeには、ステップＳ５０７にてノード１２のノード番号が格納されているため、ステップＳ５１１の判定はＮＯとなる。
【０１８７】
これにより、第２のスレッドでは、ステップＳ５１２において、変数nnodeに設定されているノード番号に対応するノード１２に対応するpanelの更新処理、即ちLDL^T分解処理が実行される。
【０１８８】
以上のようにして、第１のスレッドと第２のスレッドによって、subtree chainに対する処理が終了した後に、node chainに登録されているノード１１に対するpanel更新処理と、ノード１２に対するpanel更新処理が並列に実行されることになる。これ以後も、node chainに登録されている２つずつのノードに対する各panel更新処理が第１及び第２のスレッドによって並列に実行される。このとき、前述のメモリ割付チェイン生成処理によって、node chainに順次登録されているノードは、サイクリックにそれぞれ異なるメモリ格納領域（プール）に割り付けられている。従って、各ノードの並列実行において同じメモリ格納領域にアクセスが集中してしまうという事態を回避することが可能となる。
【０１８９】
各スレッドでは、ステップＳ５１２の処理によって各ノードに対するpanel更新処理が終了すると、再びステップＳ５０２に移行する。そして、各スレッドでは、ステップＳ５０３からＳ５１２の一連の処理によって、node chainに登録されているノードが１つずつ取り出されながら、並列計算が実行される。
【０１９０】
ここで、図１４の例では、例えばノード１５のpanel更新時にはノード１１、１２、１３、１４が参照され、ノード１６のpanel更新時にはノード１２、１３、１４、１５が参照される。この場合、番号が連続する各ノードは、それぞれ異なるメモリ格納領域（プール）に交互に割り付けられているため、１つのスレッドによる１つのノードに対するpanel更新処理においても、１つのメモリ格納領域にアクセスが集中してしまう事態を回避することが可能となる。
【０１９１】
以上の処理の結果、node chainに登録されているノードがなくなる、即ち図８（ａ）のレジスタ８０２からnull値が検出されると、ステップＳ５０６の判定がＮＯ、ステップＳ５０９の判定がＹＥＳ、ステップＳ５１１の判定もＹＥＳとなって、全てのLDL^T分解処理を終了する。
【０１９２】
以上の図５の動作フローチャートの処理により、LDL^T分解実行部１０４による前述のステップ８．の処理が実現される。
次に、並列に実行されるスレッド数が２から３に増やされた場合について説明する。
【０１９３】
メモリ割付けが行われるメモリ格納領域の数は前述の説明の場合と同様に２とする。即ち、前述の図３によるメモリ割付チェイン生成処理では、前述した事例の場合と同じ結果が出力される。
【０１９４】
スレッド数が３になると、図１４のエリミネーションツリーの例において、レベル毎の分岐ノードの集合を探しても要素数が３以上のものはない。この結果、前述の図４によるタスクチェイン生成処理では、subtree chainは生成されず、node chainのみが生成される。この場合、work配列としては、次のようなものが生成される。
work＝{21|10,20|4,9,19|2,3,8,18|1,7,17|1,5,6,16|15|14|13|12|11}
・・・（１３）
これより、node chainとしては、次のようなものが生成される。
node chain＝{11→12→13→14→15→16→6→5→1→17→7→1→18→8
→3→2→19→9→4→20→10→21} ・・・（１４）
【０１９５】
前述の図５によるLDL^T分解実行処理における並列処理では、３個のスレッドに同じようにnode chainから各ノードが取り出されてそれぞれ独立して実行される。
最初、ノード１１、１２、１３が３つのスレッドに割り当てられてpanel更新処理が実行され、空いたスレッドに次のノード１４が割り当てられる。
【０１９６】
例えば、ノード１１の更新処理では、ノード１１のみがアクセスされる。ノード１２の更新処理では、ノード１１と１２がアクセスされる。ノード１３の更新処理では、ノード１２と１３がアクセスされる。これらのノードは、前述のメモリ割付チェイン生成処理によって割付チェインchain1と割付チェインchain2に交互に現れる。つまり、各ノードに対応するメモリ格納領域のliは、メモリ格納領域の前半と後半に分散して割り付けられている。このため、３個のスレッド全てが局所的なメモリ格納領域に集中することを回避することが可能となる。
【０１９７】
処理が進み、ノード１８、８、３が並列実行されているときは、ノード１８の更新処理ではノード１４、１５、１６、１７、１８がアクセスされ、ノード８の更新処理ではノード５、７、８がアクセスされ、ノード３の更新処理ではノード３のみがアクセスされる。このとき、割付チェインchain1にノード３、１５、１７、８、割付チェインchain2にノード５、７、１４、１６、１８というように、ほぼ均等に２つのメモリ格納領域に分散してノード割付けが行われている。このため、アクセスの集中を回避することが可能となる。
【０１９８】
上述の実施形態では、図１のメモリ割付チェイン生成部１０２によって実行される図３のメモリ割付チェイン生成処理では、レベル毎の分岐ノードの集合の要素数が連続にメモリデータを割り当てるセクション（メモリ格納領域）の数以上となるものがサーチされる。これに対して、連続にメモリデータを割り当てるセクションの数を超え、実行スレッド数に近い数をsubtree数とし、このsubtree数以上となるような分岐ノードの集合の要素数がサーチされるように構成されてもよい。このようなサーチにより、メモリ割付チェイン生成部１０２でのメモリ割付けの分散状態をタスクチェイン生成部１０３でのスレッド数の並列状態に合わせることができ、より効果的なメモリアクセス分散が可能となる。
【０１９９】
図１１は、実施形態が適用されるハードウェアシステム構成の例を示す図（その１）である。
マルチコアＣＰＵ１１００が、相互結合網（バス）１１０４を介して、複数のメモリモジュール１１０３と接続される。
【０２００】
マルチコアＣＰＵ１１００は、１つのＣＰＵパッケージ内に、ＣＰＵコア＋Ｌ１キャッシュ１１０１を複数封入したもので、Ｌ２キャッシュ・バスインタフェース１１０２は、各ＣＰＵコア＋Ｌ１キャッシュ１１０１から共通に使用される。
【０２０１】
前述した各ノードが割り付けられるメモリ格納領域は、複数のメモリモジュール１１０３に分散して設定され、或いは、１つのメモリモジュール１１０３内の複数のバンクに分散して設定される。
【０２０２】
前述した並列計算を行うスレッドは、１つのマルチコアＣＰＵ１１００内の各ＣＰＵコア＋Ｌ１キャッシュ１１０１によってそれぞれ実行されるように構成することもできるし、１つのＣＰＵコア＋Ｌ１キャッシュ１１０１がマルチスレッド処理として実行するように構成することもできる。
【０２０３】
図１２は、実施形態が適用されるハードウェアシステム構成の例を示す図（その２）である。
図１２に示されるコンピュータシステムは、ＣＰＵ１２０１、メモリ１２０２、入力装置１２０３、出力装置１２０４、外部記憶装置１２０５、可搬記録媒体１２０９が挿入される可搬記録媒体駆動装置１２０６、及びネットワーク接続装置１２０７を有し、これらがバス１２０８によって相互に接続された構成を有する。同図に示される構成は上記システムを実現できるコンピュータの一例であり、そのようなコンピュータはこの構成に限定されるものではない。
【０２０４】
ＣＰＵ１２０１は、当該コンピュータ全体の制御を行う。メモリ１２０２は、プログラムの実行、データ更新等の際に、外部記憶装置１２０５（或いは可搬記録媒体１２０９）に記憶されているプログラム又はデータを一時的に格納するＲＡＭ等のメモリである。ＣＵＰ１２０１は、プログラムをメモリ１２０２に読み出して実行することにより、全体の制御を行う。
【０２０５】
ＣＰＵ１２０１は、図１１に示されるように、マルチコアタイプのものであってもよい。また、メモリ１２０２は、図１１に示されるように、複数のメモリモジュールから構成されてもよい。
【０２０６】
入力装置１２０３は、例えば、キーボード、マウス等及びそれらのインタフェース制御装置とからなる。入力装置１２０３は、ユーザによるキーボードやマウス等による入力操作を検出し、その検出結果をＣＰＵ１２０１に通知する。
【０２０７】
出力装置１２０４は、表示装置、印刷装置等及びそれらのインタフェース制御装置とからなる。出力装置１２０４は、ＣＰＵ１２０１の制御によって送られてくるデータを表示装置や印刷装置に出力する。
【０２０８】
外部記憶装置１２０５は、例えばハードディスク記憶装置である。主に各種データやプログラムの保存に用いられる。
可搬記録媒体駆動装置１２０６は、光ディスクやＳＤＲＡＭ、コンパクトフラッシュ（登録商標）等の可搬記録媒体１２０９を収容するもので、外部記憶装置１２０５の補助の役割を有する。
【０２０９】
ネットワーク接続装置１２０７は、例えばＬＡＮ（ローカルエリアネットワーク）又はＷＡＮ（ワイドエリアネットワーク）の通信回線を接続するための装置である。
本実施形態によるシステムは、図１の各部に必要な機能を搭載したプログラムをＣＰＵ１２０１が実行することで実現される。そのプログラムは、例えば外部記憶装置１２０５や可搬記録媒体１２０９に記録して配布してもよく、或いはネットワーク接続装置１２０７によりネットワークから取得できるようにしてもよい。
【産業上の利用可能性】
【０２１０】
開示する技術は、有限要素法、偏微分方程式などの解析を行いシミュレーションを行う技術に利用することができる。
【符号の説明】
【０２１１】
１０１ 分岐ノード集合検出部
１０２ メモリ割付チェイン生成部
１０３ タスクチェイン生成部
１０４ LDL^T分解実行部
１１００ マルチコアＣＰＵ
１１０１ ＣＰＵコア＋Ｌ１キャッシュ
１１０２ Ｌ２キャッシュ・バスインタフェース
１１０３ メモリモジュール
１１０４ 相互結合網（バス）
１２０１ ＣＰＵ
１２０２ メモリ
１２０３ 入力装置
１２０４ 出力装置
１２０５ 外部記憶装置
１２０６ 可搬記録媒体駆動装置
１２０７ ネットワーク接続装置
１２０８ バス
１２０９ 可搬記録媒体
【技術分野】
【０００１】
開示する技術は、シミュレーションや数理モデルから生じるスパースな正値対象行列の連立１次方程式の解を求めることにより数理モデルの分析を行う技術に関する。
【背景技術】
【０００２】
最近のスカラー計算機は、ＣＰＵの性能は高速化されているが、メモリのアクセスが局所的に集中するときに処理性能が低下する傾向にある。特に、スパースな正値対象行列の連立１次方程式をコレスキー分解（LDL^T分解）を行いながら解く場合、データの参照更新が局所的なメモリ格納領域に集中することが多く、これが原因で並列効率をうまく引き出せないことがある。
【０００３】
以下にその実例を示す。
今、図１３に示されるようなスパースな正値対象行列Ｌを考える。対角要素にノード番号、●は非ゼロ要素、○はLDL^T（又はLL^T）分解で発生したフィルイン（fill-in）を表す。
【０００４】
left-looking法に基づくLDL^T分解は、次のようにして求めることができる。
行列Lのi行目のiを除いた非ゼロ要素を持つノードの集合が算出される。これをrowstruct(i) とする。例えば、rowstruct(4)={1,2,3}, rowstruct(8)={5,7}である。
【０００５】
rowstruct(i) は、エリミネーションツリー（elimination tree）のノードi をルートノードとするpuruned row subtree を構成し、それから算出することができる。実際、{4} + {1,2,3}、{8}+{5,7}はsubtree（サブツリー、部分木）になっている。なお、この処理の詳細については、下記非特許文献１に記載されている。
【０００６】
ノードi のLの列ベクトルをliとして、LDL^T分解の対角行列の対角要素をdiiとする。また、LDL^T分解を行う行列をAとし、この下三角行列のi 番目の列ベクトルをaiとする。
li ← ai − Σdjj ×lij ×lj ・・・（１）
j ∈ rowstruct(i)
li ← li ／dii ，ここで dii＝lii ・・・（２）
上記（１）式及び（２）式で示される処理がi=1 からn まで繰り返されることにより、li が算出される。
【０００７】
li の計算は、rowstruct(i)の要素のノードjでlj が計算できていれば、それらを使ってそのjに関する計算をliに対して行うことができる。つまり、li=aiと初期化され、その時点で計算が終わっているljを使ってliに対する更新の計算が実行される。
【０００８】
liの格納に必要なメモリ格納領域の大きさも、エリミネーションツリーのpuruned row subtreeを用いて計算することができる。つまり、ノードiを含むpuruned row subtreeの数を数えることにより、上記メモリ格納領域の大きさを算出することができる。
【０００９】
また、liの非ゼロ要素のインデクス（行番号）の集合は、ノードi及びrowstruct(i)のインデクスの和を求めることで計算することができる。これらの計算処理は、入力配列Aを解析して求めることができ、symbolic decompositionと呼ばれている。この詳細については、下記非特許文献１に記載されている。
【００１０】
これらの情報から、各column（列）のliは、非ゼロ要素を圧縮してcompressed column storage（圧縮列格納方式）でメモリに格納することができる。
また、ノードiの更新で、エリミネーションツリーのdescendantとなるノードのインデクスでiよりも大きなものは、ノードiのインデクスの部分集合になることが、上記（１）式からわかる。
【００１１】
このことから、各liの更新の計算を、圧縮した状態で一時域で計算してインデクスサーチしてliの対応位置に加えることで実行できる。
liの並列計算に関して、ノードiの更新をスレッドに割り付けて並列に、参照可能なljを使ってliを計算できる。ノードiの更新が終わればこれが参照可能となるため、このノードを待っていたスレッドの計算が可能になる。更新の終わったスレッドには、タスクチェイン（タスクキュー）にある次に更新されるべきノードの計算が新たに割り当てられる。参照可能なノードjに関しての更新が実行され、まだ計算が完了していないノードは後回しにして処理される。利用可能なノードの計算が終わり、計算に必要なノードjが残っていれば、ノードjの計算が終わるのが待たれる。このようににして、パイプライン方式で、LDL^T分解計算の並列化を実現することができる。
【００１２】
ここで、エリミネーションツリーは、次式で示される親子関係から算出することができる。
parent(i)=min { j | lji ≠ 0 , j > i } ・・・（３）
： Lのi番目の列で最初にゼロでない行番号
例えば、図１３に示される行例において、ノード１の親はノード２、ノード２の親はノード４、ノード３の親はノード４などである。実際のエリミネーションツリーは、LDL^T分解される配列Aの下三角（{aij | i ≧ j , j=1,…,n}）をサーチすることで算出することができる。この処理の詳細は、下記非特許文献１に記載されている。
【００１３】
図１４は、上記（３）式に基づいて図１３の行列に対して算出されるエリミネーションツリーの例を示す図である。このエリミネーションツリーの例から、例えば以下のような並列計算のための知見を得ることができる。
【００１４】
まず、ノード４とノード７の間では参照される共通のノードはないため、ノード４及びノード７は独立に計算することができる。
一般には、前述の（１）式から、{ i } + rowstruct(i) と { j } +rowstruct(j) が共通部分を持たない場合、各々に属するliの計算は、独立に実行することができる。エリミネーションツリーにおいては、共通部分のないsubtree同士は、独立に計算可能である。subtreeの各ノードのliの計算に必要なノードは、ノードiをルートとするpuruned subtree なので、subtree内に含まれている。従って、共通部分のないsubtree同士は、相互に依存関係がないことになるので、独立な計算が可能である。
【００１５】
図１３及び図１４において、LDL^T分解の結果におけるフィルインを含めた非ゼロ要素の数や各列の非ゼロ要素のインデクス（行番号）は、前述したように、分解の前にsymbolic decompositionによって求めることができる。
【００１６】
eliminationツリーが、depth firstに従って、ルートノード（図１４ではノード２１）からサーチされることにより、各ノードに対してポストオーダで番号付けがなされる。なお、depth firstやポストオーダの意味については、実施形態の説明において詳細に説明する。図１３及び図１４の例では、ポストオーダと元の番号は一致している。
【００１７】
subtree{1,2,3,4}とsubtree{5,6,7}が、前述の（１）式及び（２）式に従って分解される。このときの依存関係から、ポストオーダ順に計算が実行される。つまり、ノード１→２→３→４、及びノード５→６→７の順に計算が実行される。これら２系列の計算は、並列に計算可能である。
【００１８】
上記計算が終わったら、ノード８→９→．．．→２１という順で計算が実行される。ノード８，９は、共に７の列を参照するため、列７を用いて更新する箇所は並列に計算でき、ノード７の計算が終わっていれば計算可能である。８，９，１０と空いたスレッドが発生するたびに、タスクチェインからノードが割り当てられ列の更新が受け持たされる。ノード１１〜ノード２０までの計算も、上記の場合と同様の依存関係がある。例えば、列１３が計算でき、ノード１４，１５を並列に更新できる。ノード１４の更新が終われば、このスレッドにノード１６が割り当てられる。そして、ノード１５の更新と１６の更新が並列に実施される。
【００１９】
このようにして、パイプライン方式で更新を実行することができる。
本出願が開示する技術に関連する従来技術として、下記先行技術文献が開示されている。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】T.DAVIS, Direct Methods for Sparse Linear Systems, SIAM 2006
【発明の概要】
【発明が解決しようとする課題】
【００２１】
ここで、上述した従来の並列計算方式において、計算結果のメモリ格納領域としては、1からnまでのcolumn（列）の大きさ（column count）を加算した大きさのメモリ格納領域が割り当てられる。この場合に、compressed column storage方式で行列Lが格納されてゆく。liが、１からnまでつなげた領域に格納される。
【００２２】
例えば、メモリが３個の部分に分かれていて、メモリ格納領域もほぼ３つ程度に均等にわたって存在するとする。そして、メモリ格納領域が単純に、各liのインデックスｉの大きさに応じて３等分されるとする。そのとき、subtree{1,2,3,4}とsubtree{5,6,7}が並列に計算されると、図１３より、１番目のメモリ格納領域（ｉ＝１〜７に対応）ばかりがアクセスされることになる。またその後、ポストオーダ順にノード１１〜２０までがパイプライン的に並列に処理される。このとき２番目（ｉ＝８〜１４に対応）、３番目（ｉ＝１５〜２１に対応）のエリアばかりが局所的にアクセスされることになる。つまり、アクセスが局所的なメモリ格納領域に集中する。
【００２３】
並列度が２から３に上げられるとき、図１３及び図１４の例では、並列に実行されるsubtreeは３個はない。このため、並列処理の粒度を下げてバランスをとるために、subtreeの計算を並列の対象からはずすことが望ましい。この場合、計算処理がポストオーダ順に実行され、パイプライン処理での並列性が引き出される。このとき、ポストオーダ順にタスクチェインが作成され、ノードのliの更新処理が、各スレッドにパイプライン処理として割り当てられる。しかし、このような方式が採用された場合、メモリに対するアクセスが局所的に集中していってしまうという問題点を有していた。
【００２４】
つまり従来は、並列度を上げてゆけば、並列実行をパイプラインで行える範囲で理論的には性能が向上するはずである。しかし、メモリのアクセスの局所化が増すため、かえって計算効率が低下してしまう可能性が高いという問題点を有していた。
【００２５】
開示する技術が解決しようとする課題は、並列計算時にメモリアクセスが同じメモリ格納領域に集中しないようにすることにある。
【課題を解決するための手段】
【００２６】
上記課題を解決するために、開示する技術は、スパースな正値対象行列の連立１次方程式を解く演算処理を、該正値対象行列のコレスキー分解に先立ち入力行列の非零要素の構造を解析してえられるエリミネーションツリーを構成するスーパーノードを単位として実行する演算処理方法、装置、又はプログラムとして実現され、以下の構成を有する。
【００２７】
分岐ノード集合検出処理ステップ又は分岐ノード集合検出処理部は、エリミネーションツリーをそのルートノードからサーチすることにより、並列レベル毎の分岐ノードの集合を検出する。
【００２８】
サブツリーメモリ格納領域割付けステップ又はサブツリーメモリ格納領域割付け部は、分岐ノードの集合のうち、その集合の要素数が連続にメモリデータが割り当てられる記憶単位である複数のメモリ格納領域の数以上となる集合をサーチし、そのサーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリー毎に、そのサブツリーを構成するノード群に対する列ベクトルの演算結果を複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付ける。
【００２９】
ノードメモリ格納領域割付けステップ又はノードメモリ格納領域割付け部は、エリミネーションツリーを構成するノード群のうち、前述のサーチで得られる分岐ノードの集合に対応する各サブツリーを構成するノード群を含まないノード群に対する列ベクトルの演算結果を、並列レベルが近接しているノード群の演算結果はそれぞれ異なるメモリ格納領域に割り付けられるようにして、複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付ける。
【００３０】
上述の構成に加えて、以下の構成を有する。
サブツリーチェイン生成ステップ又はサブツリーチェイン生成部は、分岐ノードの集合のうち、その集合の要素数が並列実行される複数のスレッドの数以上となる集合をサーチし、そのサーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリーに関する情報をその各サブツリー単位で第１のタスクチェインであるサブツリーチェインに接続する。
【００３１】
ノードチェイン生成ステップ又はノードチェイン生成部は、エリミネーションツリーを構成するノード群のうち、スレッドに関するサーチで得られる分岐ノードの集合に対応する各サブツリーを構成するノード群を含まないノード群を、エリミネーションツリーのリーフノードからルートノードに向かう順でかつ並列レベル毎にまとまるようにして、第２のタスクチェインであるノードチェインに接続する。
【００３２】
そして、各スレッドは、サブツリーチェインに接続されている各サブツリーに関する情報を登録順に選択してその情報に対応するサブツリーを構成するノード群に対する列ベクトルの演算を実行し、サブツリーチェインで選択すべきエントリがなくなったら、ノードチェインに接続されている各ノードに対する列ベクトルの演算を登録順に実行する。
【発明の効果】
【００３３】
開示する技術によれば、同じ並列レベルのサブツリーの並列計算時に各サブツリーを構成するノード同士が集中して同じメモリ格納領域にアクセスするという状況を回避することが可能となる。
【００３４】
また開示する技術によれば、ノードの並列計算時にそれらのノード同士が集中して同じメモリ格納領域にアクセスするという状況を回避することが可能となる。
そして開示する技術によれば、各スレッドは概ね独立したメモリ格納領域をアクセスする。この結果、アクセスが集中することがないため、メモリアクセスのボトルネックが発生せず、並列度が上げたときに処理性能が著しく劣化することを回避することが可能となる。
【図面の簡単な説明】
【００３５】
【図１】実施形態の構成図である。
【図２】分岐ノード集合検出処理を示す動作フローチャートである。
【図３】メモリ割付チェイン生成処理を示す動作フローチャートである。
【図４】タスクチェイン生成処理を示す動作フローチャートである。
【図５】LDL^T分解実行処理を示す動作フローチャートである。
【図６】エリミネーションツリーの例を示す図である。
【図７】実施形態のデータ構成図（その１）である。
【図８】実施形態のデータ構成図（その２）である。
【図９】実施形態の動作説明図である。
【図１０】実施形態のデータ構成図（その３）である。
【図１１】実施形態が適用されるハードウェアシステム構成の例を示す図（その１）である。
【図１２】実施形態が適用されるハードウェアシステム構成の例を示す図（その２）である。
【図１３】LDL^T分解処理を行う正値対象行例の例を示す図である。
【図１４】図１２の正値対象行列の例に対応するエリミネーションツリーを示す図である。
【発明を実施するための形態】
【００３６】
以下、実施形態について詳細に説明する。
スパースな正値対象行列のLDL^T分解は、以下に示される方法で行われる。まず、スパース行列データが、compressed column storage（圧縮列格納方式）などの圧縮格納方式によってメモリに格納される。これにより、対角要素を含む下三角行列部分の非ゼロ要素が圧縮してメモリに格納される。列同士の依存関係や分解で新たに発生する非ゼロ要素が考慮されて、非ゼロパターンが同じか似ている列が並べ替えられて、１つのpanel（ブロック）にまとめられる。ブロックはスーパーノードと呼ばれ、複数のノードからなる。分解過程で生じるスーパーノード間のデータ依存関係が木構造で表現されて処理が実行される。この木のことをエリミネーションツリー（elimination tree）と呼ぶ。
【００３７】
これらの木を構成するノードはスーパーノードであり、親子関係で表現できる。
ノードがleft-looking法で更新されてゆくとき、そのノードに関するpruned row subtreeの情報に基づいて、更新により参照されるrow structure（行構造）が決まる。pruned row subtreeは、エリミネーションツリーのsubtree（サブツリー、部分木）である。
【００３８】
このため、エリミネーションツリーのリーフを持つsubtreeで、お互いに共通部分を持たないものは独立に分解の計算を行うことができる。この処理の詳細については、例えば前述の非特許文献１に詳細に記載されている。
【００３９】
並列計算を行う上では、各々のsubtreeを構成するスーパーノードに対するブロックを格納するメモリ格納領域は、互いに近くに割り付けられるのがよい。
更に処理が進むと、木のルート（root）の方向に処理が進みながら、更新されるべきノードが順次選択されてゆく。処理がルートに近づくほど、一般に独立なsubtreeは減ってゆく。各ノードの依存関係が考慮されながらノードに対するブロックの更新が並列処理されてゆく。スパース行列のために、参照・更新されるノードは限られる。このため、単純に木の構造を構成するノードで近いものがメモリ上でも近くのメモリ格納領域に割り当てられると、メモリへの参照・更新が局所的な部分に集中してしまう。
【００４０】
これを避けるために、並列処理の対象が、subtreeで分けられない部分と分けられる部分に分割される。そして、分解結果を格納する領域が複数の連続する部分に分割されることにより、subtreeを構成するノードに対応するブロック列ベクトルの格納領域が異なる部分連続領域に割り当てられるように制御が行われる。
【００４１】
subtreeが取り除かれた部分の要素となるノードに関しては、木のルートからsubtreeのルート又は木のリーフに届くまで、同じ並列レベルのノードがまとめられながら、木が辿られてゆく。そして、辿られたルートと逆ルートが辿られながら、各ノードが異なる部分連続領域にサイクリックに割り付けられてゆく。
【００４２】
並列処理に関しては、上述の割付けと同様の方式でタスクチェインが生成される。並列処理を実行するスレッド数を#Pとして、#P個以上のsubtreeがあれば、これらのsubtreeのルートとなるノードがタスクチェイン（subtree chain：サブツリーチェイン）に接続される。subtreeが取り除かれたノードに関しても部分連続領域の割付けと同様にして、木のルートからsubtreeのルート又は木のリーフに届くまで、同じ並列レベルのノードがまとめられながら、木が辿られてゆく。そして、辿られたルートと逆ルートを辿る順番のノードのチェインが生成され、ノードのタスクチェイン（node chain：ノードチェイン）とされる。
【００４３】
以上の制御処理により、並列計算を行えるスレッド数が変わっても、同じメモリ格納領域へのメモリアクセスが集中することを避けることができる。
【００４４】
エリミネーションツリーについて、以下に説明する。
本実施形態では、エリミネーションツリーは、全ノード数を#nodeとする１次元配列parentを用いて表現される。例えば、j=parent(i)は、「ノードiの親（parent）はノードjである」という意味を表現している。
【００４５】
エリミネーションツリー上のノードの子及び兄弟の関係は、１次元配列child及びbrotherを用いて表現される。ノードj がノードi の子であれば、child(i)=jである。ノードi に子がなければ、child(i)=0である。
【００４６】
子が複数存在する場合には、１つの子が親のchildとされ、その他の子はそのchildのbrotherとして表現される（親の子とはされない）。ノードj のbrotherとしてj1,j2があれば、brother(j)=j1, brother(j1)=j2, brother(j2)=0 と表現される。
【００４７】
或るノードに対するfirstdescendant（ファーストディッセンダント：第１子孫）とは、そのノードから子（兄弟ではない）を辿って到達する、子がないノード即ちリーフノードのことをいう。例えば図６では、ノード７のfirstdescendantはノード１、ノード６のfirstdescendantはノード４などである。
【００４８】
ここで、ポストオーダを、depth firstで、エリミネーションツリーがルートノード１５からサーチされ、サーチ順に各ノードに番号が付与されるときの順番と定義する。図６においては、ポストオーダは、１，２，３，．．．，１４となる。
【００４９】
depth firstとは、以下のようなサーチ手順をいう。まず、ルートノードから子が辿られて、最も深いノード例えばノード１がサーチされる。１ノード分だけ親＝ノード３に戻って、その親の子のうちノード１の兄弟例えばノード３が辿られる。再び、１ノード分だけ親＝ノード３に戻って、その親の子にはノード１の兄弟はもうないため、更に親＝ノード７に戻って、そこから子が辿られて、最も深いノード例えばノード４がサーチれる。以下同様にエリミネーションツリーがで辿られて、ポストオーダが決定される。このように、常に深いノードが優先されるサーチ手順をdepth firstと呼ぶ。
【００５０】
subtreeは、ノード１〜７によって構成される部分集合や、ノード８〜１４によって構成される部分集合などをいう。また、３つのノードからなるノード１〜３、ノード４〜６、ノード８〜１０、ノード１１〜１２の各部分集合も、subtreeである。
【００５１】
リーフとは、子を持たないノードをいう。図６では、１，２，４，５，６，９，１１，１２がリーフである。
上述のエリミネーションツリーを用いることにより、スパース行列で、ノードに対応する列ベクトルを束ねたスーパーノードが検出される。スーパーノードを構成するノードの非ゼロ要素の存在する行のみが圧縮され、２次元のpanel（パネル）に分解結果が格納される。
【００５２】
各スーパーノードに対応するpanelの大きさは、分解結果の非ゼロパターンに対してsymbolic decompositionが実行されることにより決定され、実際の分解を行う前に知ることができる。
全panelを格納する１次元配列が用意され、この１次元配列のどの要素位置に各スーパーノードに対応するpanelが配置されるかが決定される。
【００５３】
図１は、上述の基本的な考え方に基づく実施形態の構成図である。
この実施形態は、分岐ノード集合検出部１０１、メモリ割付チェイン生成部１０２、タスクチェイン生成部１０３、LDL^T分解実行部１０４を含む。
【００５４】
分岐ノード集合検出部１０１：
ステップ１．エリミネーションツリーデータ（parent配列、child配列、brother配列）が入力される。そして、それによって表現されるエリミネーションツリーにおいて、ルートノードからサーチが行われ、兄弟が複数ノードある、同じ並列レベルの分岐ノードの集合が、レベル毎に検出される。
【００５５】
メモリ割付チェイン生成部１０２：
ステップ２．ステップ１．で検出されたレベル毎の分岐ノードの集合のうち、集合の要素数が連続にメモリデータを割り当てるセクション（メモリ格納領域）の数以上となるものが、レベルが低いものから順にサーチされる。
【００５６】
ステップ３．見つかった場合、この集合から分岐ノードが取り出され、このノードがルートノードとされるsubtreeがポストオーダー順に取り出され、各メモリ格納領域のための割付チェインに接続される。このとき、１つのsubtreeの構成ノードは、同じ割付チェインに接続される。subtree毎に、それが割り付けられるべきメモリ格納領域を指定する割付チェインが、サイクリックな順番で決められる。この結果、同じ並列レベルのsubtreeには、並列計算の実行時に、それぞれ異なる割付チェインを介して異なるメモリ格納領域が割り付けられることになる。即ち、同じ並列レベルのsubtreeの並列計算時に各subtreeを構成するノード同士が集中して同じメモリ格納領域にアクセスするという状況を回避することができる。
【００５７】
ステップ４．ステップ３．で割付けが行われたsubtreeを除いたノードが、ルートノードから同じ並列レベルのノードが集まるようにしてリーフ方向にサーチされる。このサーチがステップ３．で割り付けられた分岐ノードかリーフノードに到達すれば、そのサーチは終了する。サーチされたノードは、サーチの順にstack（後述するwork配列）に積まれる。サーチが終わったら、stackが順にpopされながらサーチの逆順でノードが取り出され、その各ノードに対して、サイクリックな順番で割付チェインが決定される。この結果、レベルが近接し並列計算される可能性の高いノード群には、それぞれ異なる割付チェインを介して異なるメモリ格納領域がサイクリックに割り付けられることになる。これにより、ノードの並列計算時にそれらのノード同士が集中して同じメモリ格納領域にアクセスするという状況を回避することができる。
【００５８】
タスクチェイン生成部１０３：
ステップ５．ステップ１．で検出されたレベル毎の分岐ノードの集合のうち、集合の要素数が並列実行されるスレッドの数以上となる集合が、レベルの低いものから順にサーチされる。
【００５９】
ステップ６．ステップ５．で検出された分岐ノードの集合に含まれる分岐ノードが順次、subtree chainに接続される。
【００６０】
ステップ７．ステップ６．で処理された各分岐ノードがルートノードとされる各subtreeを除いたノードが、ルートノードから同じ並列レベルのノードが集まるようにしてリーフ方向にサーチされる。このサーチがステップ６．でsubtree chainに接続された分岐ノードかリーフに到達すれば、そのサーチは終了する。サーチされたノードは、サーチの順にstack（後述するwork配列）に積まれる。サーチが終わったら、stackが順にpopされながらサーチの逆順でノードが取り出され、その各ノードがnode chainに接続される。
【００６１】
LDL^T分解実行部１０４：
ステップ８．ステップ６．にて生成されたsubtree chainにエントリがあるうちは、subtree chainの先頭から順次各分岐ノードがスレッドの並列数ずつ取り出され、各スレッドに割り当てられる。各スレッドでは、割り当てられた分岐ノードに対応するsubtreeを構成する各ノードに対して、left-lookingなLDL^T分解が実行される。subtree chainのエントリがなくなったら、ステップ７．にて生成されたnode chainの先頭から順次各ノードがスレッドの並列数ずつ取り出され、各スレッドに割り当てられる。各スレッドでは、割り当てられたノードに対して、left-lookingなLDL^T分解が実行される。
【００６２】
ここで、分岐ノード集合検出部１０１が実行するステップ１は、特許請求の範囲における分岐ノード集合検出処理ステップに対応する。メモリ割付チェイン生成部１０２が実行するステップ２．及び３．は、特許請求の範囲におけるサブツリーメモリ格納領域割付けステップ又はサブツリーメモリ格納領域割付け部に対応する。メモリ割付チェイン生成部１０２が実行するステップ４．は、特許請求の範囲におけるノードメモリ格納領域割付けステップ又はノードメモリ格納領域割付け部に対応する。タスクチェイン生成部１０３が実行するステップ５．及び６．は、特許請求の範囲におけるサブツリーチェイン生成ステップ又はサブツリーチェイン生成部に対応する。タスクチェイン生成部１０３が実行するステップ７．は、特許請求の範囲におけるノードチェイン生成ステップ又はノードチェイン生成部に対応する。
【００６３】
以上の各部の処理を実現するための本実施形態の詳細な処理について、従来技術の説明において用いた図１３に示される行列と図１４に示されるエリミネーションツリーの例と、図２から図５の動作フローチャート、及びを用いて、以下に説明する。
【００６４】
図２は、分岐ノード集合検出部１０１が実行する前述のステップ１．の分岐ノード集合検出処理の詳細を示す動作フローチャートである。
図７は、エリミネーションツリーのルートノードをレベル１として、レベル１から順次増加するレベル毎に、各レベルに属する分岐ノードの集合を管理するための配列データの構成例を示した図である。
【００６５】
図７（ｂ）は、分岐ノードを、エリミネーションツリーのルートノードからリーフノードに向かって検出された順に登録する１次元配列branchのデータ構成例である。ここで、branch配列の配列位置０（図７（ｂ）の７０４）の配列要素値＝２１は、図１４に示されるエリミネーションツリーのルートノードに対応し、レベル１の分岐ノードのノード番号を示している。配列位置１（図７（ｂ）の７０５）の配列要素値＝１０は、図１４に示されるエリミネーションツリーのノード１０に対応し、レベル２の分岐ノードのノード番号を示している。配列位置２及び３（図７（ｂ）の７０６及び７０７）の配列要素値＝４及び７は、図１４に示されるエリミネーションツリーのノード４及びノード７に対応し、レベル３の分岐ノード群の各ノード番号を示している。
【００６６】
図７（ａ）は、先頭からレベル１、２、３、・・・の順に、branch配列上における各レベルの分岐ノード群が格納されている先頭の配列位置を配列要素値として格納する１次元配列branchlvlのデータ構成例である。ここで、branchlvl配列の配列位置０（図７（ａ）の７０１）の配列要素値＝０は、図７（ｂ）のbranch配列上のレベル１の分岐ノード群（図７（ｂ）ではノード２１の１つのみ）が格納されている先頭の配列位置を示している。配列位置１の配列要素値＝１（図７（ａ）の７０２）は、図７（ｂ）のbranch配列上のレベル２の分岐ノード群（図７（ｂ）ではノード１０の１つのみ）が格納されている先頭の配列位置を示している。配列位置２の配列要素値＝２（図７（ａ）の７０３）は、図７（ｂ）のbranch配列上のレベル３の分岐ノード群（図７（ｂ）ではノード４及び７の２つ）が格納されている先頭の配列位置を示している。
【００６７】
分岐ノード集合検出部１０１によって実行される図２の動作フローチャートは、図７（ａ）に例示されるbranchlvl配列及び図７（ｂ）に例示されるbranch配列を生成する処理である。
【００６８】
以下の説明において、図１４等に示されるエリミネーションツリーの各ノードは、エリミネーションツリーデータとして入力される前述したparent配列から取得でき、１つのノードに対する子ノードは前述したchild配列から取得でき、兄弟ノードは前述したbrother配列から取得できるものとする。
【００６９】
図２において、まず、levelstart、levelend、ptrnext、ptrsearch、levelの各変数が初期化される（ステップＳ２０１）。levelstartは、レベル毎にそのレベルに属する各分岐ノードの下に更に分岐ノードがあるか否かが探索される際に、そのレベルに属する分岐ノード群のbranch配列上での先頭の配列位置を示す。levelstartの初期値は、０（branch配列の先頭（図７（ｂ）の７０４））にセットされる。levelendは、レベル毎にそのレベルに属する各分岐ノードの下に更に分岐ノードがあるか否かが探索される際に、そのレベルに属する分岐ノード群のbranch配列上での末尾の配列位置を示す。levelendの初期値も、０にセットされる。ptrnextは、branch配列上で分岐ノードが格納されている末尾の配列位置を示す。ptrnextの初期値も、０にセットされる。ptrsearchは、レベル毎にそのレベルに属する各分岐ノードの下に更に分岐ノードがあるか否かが探索される際に、現在探索が行われている分岐ノードの配列位置を示す。ptrnextは、levelstartからlevelendまでの間の値をとり、初期は０にセットされる。levelは、現在処理が行われているレベルを示す。levelの初期値は、１（＝エリミネーションツリーのルートノードのレベル）にセットされる。
【００７０】
次に、ステップＳ２０２で、図７（ａ）の７０１として示されるように、branchlvl配列の先頭の配列位置０に、branch配列の先頭の配列番号０が、レベル１（level=1）のインデックスとして格納される。
【００７１】
次に、ステップＳ２０３で、ptrsearch≦levelendが成立するか否かが判定される。始めは、ptrsearch=0≦levelend=0となるので、この判定はＹＥＳとなる。この結果、ステップＳ２０４へ移行する。
【００７２】
ステップＳ２０４では、branch配列内の配列位置=ptrsearchのノードに子（child）があるか否かが判定される。図１４に示されるように、branch配列内の配列位置０のノード２１にはノード１０のchildがあるので、この判定はＹＥＳとなる。この結果、ステップＳ２０５へ移行する。
【００７３】
ステップＳ２０５では、childstart変数にchildの値が設定される。childstart=10となる。ここで、childstart変数は、現在探索を行っている分岐ノードを示す。
続いて、ステップＳ２０６では、childのノードに、更にchildとそのbrotherがあるか否かが判定される。今、図１４に示されるように、child=10には、更にchild=4と、そのbrother=9があるので、この判定はＹＥＳとなる。この結果、ステップＳ２０７へ移行する。
【００７４】
ステップＳ２０７では、ptrnext変数の値が＋１される。即ち、ptrnext=0+1=1とされる。
続いて、ステップＳ２０８では、branchlvl配列のlevel変数の値に対応する配列位置に、レベル（level+1）のインデックスとして、ptrnext変数の値が格納される。上記配列位置に既に値が格納されている場合には、この処理は実行されない。今、図７（ａ）の７０２として示されるように、branchlvl配列の配列位置１（level=1）に、レベル２（=level+1）のインデックスとして、ptrnext=1が格納される。
【００７５】
続いて、ステップＳ２０９では、childのノード番号がbranch配列のptrnextの値に対応する配列位置に格納される。ここでは、図７（ｂ）の７０５に示されるように、child=10がbranchの配列位置1に格納される。
【００７６】
続いて、ステップＳ２１２では、childstart変数で示されるノードにbrotherがあるか否かが判定される。今、図１４に示されるように、childstart=10にbrother=20があるので、この判定はＹＥＳとなる。この結果、ステップＳ２１３へ移行する。
【００７７】
ステップＳ２１３では、childstart変数の値とchildの値がchildstart変数で示されるノードのbrotherのノード値で置き換えられる。今、childstart=20、child=20とされる。続いて、ステップＳ２０６へ移行する。
【００７８】
図１４に示されるように、child=20には、更にその子としてchild=19があるが、そのbrotherはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
【００７９】
上述のようにchild=20には更にchild=19があるので、ステップＳ２１０の判定はＹＥＳとなる。この結果、ステップＳ２１１に移行する。
ステップＳ２１１では、childのchildでchildが置き換えられる。即ち、child=19となる。続いて、ステップＳ２０６に移行する。
【００８０】
以下、ステップＳ２０６→Ｓ２１０→Ｓ２１１→Ｓ２０６の処理が繰り返されることにより、childのノードが、図１４に示されるように、19→18→17→16→15→14→13→12→11という順で移行してゆく。
【００８１】
child=11になってステップＳ２０６が実行されたときに、図１４に示されるように、child=11の下にchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
【００８２】
上述のようにchild=11の下にはchildはないので、ステップＳ２１０の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
図１４に示されるように、childstart=20にはbrotherがないので、ステップＳ２１２の判定はＮＯとなる。この結果、ステップＳ２１４へ移行する。
【００８３】
ステップＳ２１４では、ptrsearch変数の値が＋１される。即ち、ptrsearch=0+1=1とされる。続いて、ステップＳ２０３に移行する。
図７（ｂ）の７０４として示されるようにレベル１の分岐ノードは１つ（＝ノード２１）のみであり、ptrsearch=1＞levelend=0となるので、ステップＳ２０３の判定はＮＯとなる。この結果、ステップＳ２１５へ移行する。
【００８４】
ステップＳ２１５では、レベル２のための更新処理が実行される。即ち、レベル２の先頭配列位置levelstartが、レベル１の末尾配列位置levelendの次の（＋１した）配列位置とされる。また、レベル２の末尾配列位置levelendは、branch配列の現在の末尾配列位置ptrnextとされる。そして、変数lenの値として、len=levelend-levelstart+1が計算される。また、現在のレベルを示す変数level値がインクリメントされる。
【００８５】
ステップＳ２１６では、変数lenの値が０よりも大きいか否かが判定される。直前のレベルにて分岐ノード群が検出されていれば、ptrnext値がインクリメントされておりそれに従ってlevelend値もインクリメントされて変数lenの値は０より大きくなる。この結果、ステップＳ２１６の判定がＹＥＳとなって、ステップＳ２０３に移行し、直前のレベルにて検出された分岐ノード群に対して更に探索が続行される。直前のレベルにて分岐ノード群が検出されていなければステップＳ２１６の判定はＮＯとなって、全ての処理を終了する。
【００８６】
今、ステップＳ２１５にて、levelstart=0+1=1、levelend=ptrnext=1、len=1-1+1=1、level=1+1=2となる。この結果、len=1＞０となってステップＳ２１６の判定はＹＥＳとなる。続いて、ステップＳ２０３に移行する。
【００８７】
ptrsearch=1≦levelend=1となるので、ステップＳ２０３の判定はＹＥＳとなる。この結果、ステップＳ２０４へ移行する。
branch内の配列位置=ptrsearch=1のノード１０（図７（ｂ）の７０５）には、図１４に示されるように、child=4があるので、ステップＳ２０４の判定はＹＥＳとなる。この結果、ステップＳ２０５へ移行する。
【００８８】
ステップＳ２０５では、childstart=4とされる。
続いて、図１４に示されるように、child=4には、更にchild=2と、そのbrother=3があるので、ステップＳ２０６の判定はＹＥＳとなる。この結果、ステップＳ２０７へ移行する。
【００８９】
ステップＳ２０７では、ptrnext=1+1=2とされる。
続いて、ステップＳ２０８では、図７（ａ）の７０３に示されるように、branchlvl配列の配列位置level=2に、レベル３（=level+1）のインデックスとして、branch配列の末尾の配列位置ptrnext=2が格納される。
【００９０】
続いて、ステップＳ２０９では、child=4がbranch配列の末尾のｐ配列位置ptrnext=2に格納される。続いて、ステップＳ２１２へ移行する。
図１４に示されるように、childstart=4にはbrother=9があるので、ステップＳ２１２の判定はＹＥＳとなる。この結果、ステップＳ２１３へ移行する。
【００９１】
ステップＳ２１３では、childstart=9、child=9とされる。続いて、ステップＳ２０６へ移行する。
図１４に示されるように、child=9には、child=8があるが、そのbrotherはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
【００９２】
上述のようにchild=9にはchild=8があるので、ステップＳ２１０の判定はＹＥＳとなる。この結果、ステップＳ２１１に移行する。
ステップＳ２１１では、child=8となる。続いて、ステップＳ２０６に移行する。
【００９３】
図１４に示されるように、child=8には、child=7があるが、そのbrotherはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
上述のようにchild=8にはchild=7があるので、ステップＳ２１０の判定はＹＥＳとなる。この結果、ステップＳ２１１に移行する。
【００９４】
ステップＳ２１１では、child=7となる。続いて、ステップＳ２０６に移行する。
図１４に示されるように、child=7には、更にchild=5と、そのbrother=6があるので、ステップＳ２０６の判定はＹＥＳとなる。この結果、ステップＳ２０７へ移行する。
【００９５】
ステップＳ２０７では、branch配列の末尾の配列位置がptrnext=2+1=3とされる。
続いて、branchlvl配列の配列位置２（＝level）に、レベル３（=level+1）のインデックス＝２が既にあるから、ステップＳ２０８の処理は実行されない。
【００９６】
続いて、ステップＳ２０９では、child=7がbranch配列の末尾の配列位置ptrnext=3に格納される。続いて、ステップＳ２１２へ移行する。
図１４に示されるように、childstart=9にはbrotherがないので、ステップＳ２１２の判定はＮＯとなる。この結果、ステップＳ２１４へ移行する。
【００９７】
ステップＳ２１４では、ptrsearch=1+1=2とされる。続いて、ステップＳ２０３に移行する。
図７（ｂ）の７０５として示されるようにレベル２の分岐ノードは１つ（＝ノード１０）のみであり、ptrsearch=2＞levelend=1となるので、ステップＳ２０３の判定はＮＯとなる。この結果、ステップＳ２１５へ移行する。
【００９８】
今、ステップＳ２１５にて、levelstart=1+1=2、levelend=ptrnext=3、len=3-2+1=2、level=2+1=3となる。この結果、len=2＞０となってステップＳ２１６の判定はＹＥＳとなる。続いて、ステップＳ２０３に移行する。
【００９９】
ptrsearch=2≦levelend=3となるので、ステップＳ２０３の判定はＹＥＳとなる。この結果、ステップＳ２０４へ移行する。
図１４に示されるように、branch配列内の配列位置ptrsearch=2のノード４にはchild=2があるので、ステップＳ２０４の判定はＹＥＳとなる。この結果、ステップＳ２０５へ移行する。
【０１００】
ステップＳ２０５では、childstart=2とされる。
図１４に示されるように、child=2には、child=1があるが、そのbrotherはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
【０１０１】
上述のように、child=2にはchild=1があるので、ステップＳ２１０の判定はＹＥＳとなる。この結果、ステップＳ２１１に移行する。
ステップＳ２１１では、child=1となる。続いて、ステップＳ２０６に移行する。
【０１０２】
図１４に示されるように、child=1はリーフノードであってchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１０へ移行する。
上述のようにchild=1にはchildはないので、ステップＳ２１０の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
【０１０３】
図１４に示されるように、childstart=2にbrother=3があるので、ステップＳ２１２の判定はＹＥＳとなる。この結果、ステップＳ２１３へ移行する。
ステップＳ２１３では、childstart=3、child=3とされる。続いて、ステップＳ２０６へ移行する。
【０１０４】
図１４に示されるように、child=3はリーフノードであってchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
図１４に示されるように、childstart=3にはbrotherがないので、ステップＳ２１２の判定はＮＯとなる。この結果、ステップＳ２１４へ移行する。
【０１０５】
ステップＳ２１４では、ptrsearch=2+1=3とされる。続いて、ステップＳ２０３に移行する。
図７（ｂ）の７０６及び７０７として示されるようにレベル３の分岐ノードは２つ（＝ノード４及び７）であり、現在ノード４の処理が終わってノード７の処理に移っており、ptrsearch=3≦levelend=3となるので、ステップＳ２０３の判定はＹＥＳとなる。この結果、ステップＳ２０４へ移行する。
【０１０６】
branch内の配列位置ptrsearch=3のノード７には、図１４に示されるように、child=5があるので、ステップＳ２０４の判定はＹＥＳとなる。この結果、ステップＳ２０５へ移行する。
【０１０７】
ステップＳ２０５では、childstart=5とされる。
続いて、図１４に示されるように、child=5はリーフノードでありchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
【０１０８】
図１４に示されるように、childstart=5にbrother=6があるので、ステップＳ２１２の判定はＹＥＳとなる。この結果、ステップＳ２１３へ移行する。
ステップＳ２１３では、childstart=6、child=6とされる。続いて、ステップＳ２０６へ移行する。
【０１０９】
図１４に示されるように、child=6はリーフノードでありchildはないので、ステップＳ２０６の判定はＮＯとなる。この結果、ステップＳ２１２に移行する。
図１４に示されるように、childstart=6にはbrotherがないので、ステップＳ２１２の判定はＮＯとなる。この結果、ステップＳ２１４へ移行する。
【０１１０】
ステップＳ２１４では、ptrsearch=3+1=4とされる。続いて、ステップＳ２０３に移行する。
図７（ｂ）の７０６及び７０７として示されるようにレベル３の分岐ノードは２つ（＝ノード４及び７）であり、ノード４とノード７の処理が共に終了しており、ptrsearch=4＞levelend=3となるので、ステップＳ２０３の判定はＮＯとなる。この結果、ステップＳ２１５へ移行する。
【０１１１】
ステップＳ２１５では、levelstart=3+1=4、levelend=ptrnext=3、len=3-4+1=0、level=3+1=4となる。この結果、len=0=0となってステップＳ２１６の判定はＮＯとなって、全ての処理を終了する。
【０１１２】
以上のようにして、エリミネーションツリーが解析され、図７（ａ）に例示されるbranchlvl配列及び図７（ｂ）に例示されるbranch配列が生成される。
次に、図３は、図１のメモリ割付チェイン生成部１０２が実行する前述のステップ２．から４．のメモリ割付チェイン生成処理の詳細を示す動作フローチャートである。ここでは、エリミネーションツリー上の各ノードに対して、メモリ格納領域が割付けられる。
【０１１３】
まず、例として、並列計算の処理結果を保存する領域が、２つのメモリ格納領域に分割されていると仮定する。今、例えば２つのメモリ格納領域に図１４に示されるようなエリミネーションツリーを構成するノードが割り付けられる場合、例えば図８に示されるようなデータ構成を採用することができる。
【０１１４】
まず、図８（ａ）に例示されるように、エリミネーションツリーを構成する各ノードに配列位置が一意に対応する１次元ノード配列８００が用意される。例えば、配列位置０は図１４のノード２１に対応し、配列位置１は図１４のノード１０に対応し、配列位置２は図１４のノード４に対応するといった如くである。そして、メモリ格納領域１において実行されるノード群はその実行順に、割付チェインchain1に割り付けられる。この場合まず、図８（ａ）に示されるように、割付チェインchain1の先頭を示すレジスタ８０１が用意され、このレジスタ８０１に、メモリ格納領域１にて実行される最初のノードに対応する１次元ノード配列８００上の配列位置が格納される。次に、このレジスタ８０１から参照される１次元ノード配列８００上の配列位置には、２番目に実行されるノードに対応する１次元ノード配列８００の配列位置が格納される。以下同様にして、１次元ノード配列８００上の各配列位置に、その配列位置に対応するノードの次に実行されるノードに対応する配列位置が格納されてゆく。最後に実行されるノードの配列位置には、nullデータが格納される。このようにして、割付チェインchain1として、レジスタ８０１から順次１次元ノード配列８００上の配列位置が辿られることにより、メモリ格納領域１において実行されるノードとその実行順を設定することができる。割付チェインchain1の場合と同様にして、メモリ格納領域２において実行されるノード群もその実行順に、割付チェインchain2に割り付けられる。この場合まず、図８（ａ）に示されるように、割付チェインchain2の先頭を示すレジスタ８０２が用意され、このレジスタ８０２に、メモリ格納領域２にて実行される最初のノードに対応する１次元ノード配列８００の配列位置が格納される。次に、このレジスタ８０２から参照される１次元ノード配列８００上の配列位置には、２番目に実行されるノードに対応する１次元ノード配列８００の配列位置が格納される。以下同様にして、１次元ノード配列８００上の各配列位置に、その配列位置に対応するノードの次に実行されるノードに対応する配列位置が格納されてゆく。最後に実行されるノードの配列位置には、nullデータが格納される。
【０１１５】
以下の説明において、連続にメモリデータを割り当てるセクション（メモリ格納領域）のことをpool（プール）と呼び、その数を#poolと表記する。即ち、ここの仮定では、#pool=2である。
【０１１６】
図３の動作フローチャートにおいて、まず、図７（ａ）に示されるbranchlvl配列と図７（ｂ）に示されるbranch配列がアクセスされることにより、#pool以上の要素数を有する分岐ノード集合が見つけられる（ステップＳ３０１）。ここで、branchlvl配列とbranch配列は、図２の動作フローチャートで示される分岐ノード集合検出処理によって得られている。図７に示される配列構造の例から、レベル１（level 1）の分岐ノード集合は｛21｝（ノード２１を要素とする集合）となる。次に、レベル２（level 2）の分岐ノード集合は{10}（ノード１０を要素とする集合）となる。更に、レベル３（level 3）の分岐ノード集合は{4,7}（ノード４とノード７の集合）となる。そして、#pool=2とすると、２以上の要素数を有する分岐ノード集合は、level 3の分岐ノード集合{4,7}である。この結果、ステップＳ３０２の判定がＹＥＳとなる。
【０１１７】
以上のステップＳ３０１とＳ３０２の処理により、メモリ割付チェイン生成部１０２による前述のステップ２．の処理が実現される。
次に、ステップＳ３０１で見つかったlevel集合から、１つのノード＝分岐ノードが取り出され、nodelvlとされる（ステップＳ３０３）。ここでは例えば、level 3の集合{4,7}からノード４がnodelvlとして取り出される。
【０１１８】
次に、図８（ｂ）に例示されるような分岐ノード指示用１次元配列nmarkが用意される。図８（ｂ）の１次元配列nmarkは、配列要素数が図８（ａ）の１次元ノード配列８００と同じであり、図８（ａ）と同じ配列位置は同じノードに対応している。そして、各配列位置のノードが分岐ノードである場合には、その分岐ノードに対応する分岐ノード指示用１次元配列nmark上の配列位置にon（オン）を示す値が設定される。ここで、分岐ノード指示用１次元配列nmarkにおいて、ステップＳ３０３にて取り出されたノードnodelvl=4に対応する配列位置の配列要素が、onを示す値に設定される（ステップＳ３０４）。なお、nmark配列の各配列要素は、初期状態において全てクリアされている。
【０１１９】
次に、ノードnodelvlに対応するfirstdescendantのノードがfstdecs変数に設定される（ステップＳ３０５）。図１４の例では、ノード４に対するfirstdescendantのノードはノード１であり、fstdecs=1である。
【０１２０】
続いて、現在選択されているpoolの割付チェイン（chain1又はchain2）に、fstdecsノードからnodelvlノードまでポストオーダで、順番に現在のsubtreeの構成要素ノードが接続される（ステップＳ３０６）。今例えば、pool１が選択されており、割付チェイン＝chain1とする。そして、fstdecs=1からnodelvl=4までのポストオーダは、図１４に示されるように、ノード１→ノード２→ノード３→ノード４である。従って、割付チェインchain1は、次のようになる。
chain1={1→2→3→4} ・・・（４）
この割付チェインchain1が、例えば図８（ａ）に示されるデータ構造を使って形成される。
【０１２１】
次に、現在選択されているpoolが、次式によりサイクリックに変更される（ステップＳ３０７）。なお、poolは、現在選択されているpool番号を示す変数である。また、mod(A,B)は、AをBで割った剰余を求める演算を示す。
pool＝mod(pool,#pool)+1 ・・・（５）
今、#pool=2であり、現在のpool番号pool=1とすれば、上記計算の結果、新たなpool番号はpool=2となる。なお逆に、現在のpool番号pool=2とすれば、上記計算の結果、新たなpool番号はpool=1となる。
ここで、現在のpoolが1から2に変化した後、ステップＳ３０１で見つかったlevel集合に残りがあるか否かが判定される（ステップＳ３０８）。
【０１２２】
前述のlevel 3の集合{4,7}の場合、まだノード７が残っている。従って、ステップＳ３０８の判定がＹＥＳとなり、ステップＳ３０３の処理に戻る。この結果、level 3の集合{4,7}からノード７が取り出される（ステップＳ３０３）。次に、１次元配列nmark上の上記ノードnodelvl=7に対応する配列位置の配列要素が、onを示す値に設定される（ステップＳ３０４）。更に、nodelvlノード=4に対するfirstdescendantのノードとして、fstdecs=5が設定される（ステップＳ３０５）（図１４参照）。続いて、現在選択されているpool=2の割付チェイン＝chain2に、fstdecs=5からnodelvl=7までポストオーダで、順番に現在のsubtreeの構成要素ノードノード５→ノード６→ノード７が接続される（ステップＳ３０６）。従って、割付チェインchain2は、次のようになる。
chain2={5→6→7} ・・・（６）
以上のステップＳ３０３からＳ３０８の処理により、メモリ割付チェイン生成部１０２による前述のステップ３．の処理が実現される。
【０１２３】
次に、分岐ノード指示用１次元配列nmarkの配列要素がonとなっている分岐ノード又はリーフノードの何れかに辿り着くまで、エリミネーションツリーのルートノードから順に各ノードが辿られる。ここでは、図８（ｃ）に示される１次元のwork配列が用意され、ルートから同じ並列レベルのノードが辿られ、辿られたノードがwork配列に順次格納されてゆく。この処理は、図３のステップＳ３０９からＳ３１３までの処理によって実現される。これらの処理について、図９の動作説明図を用いながら説明する。
【０１２４】
まず、ステップＳ３０９で、ルートノードが、分岐ノード指示用１次元配列nmark上でonされていなければwork配列に格納される。格納されればnodeend=1、格納されなければnodeend=0とされる。通常は、ルートノードはnmark上でonされていないため、nodeend=1となる（図９の行１）。nodeend=0となる場合は特殊な場合である。nodeendは、work配列の末尾の格納位置を示す。nodestartは、対象ノードのサーチ位置を示す。
【０１２５】
次に、ステップＳ３１０で、nodestart=1とされる（図９の行２）。なお、work配列の先頭の配列位置は１とする。
次に、ステップＳ３１１では、nodestart≦nodeendが成立するか否かが判定される。図９の行３の状態では、ステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１２６】
ステップＳ３１２では、nodestartで示されるノードがwork配列から取り出され、そのノード（以下「対象ノード」と呼ぶ）のchild,brotherのノードが調べられる。そして、調べられたノードがnmark配列上でonされていないなら、nodeend=nodeend+1とされて、nodeendで示されるwork配列上の配列位置に、その調べられたノードが格納される。図９の行４の状態では、nodestart=1で示される配列位置のノード２１がwork配列から取り出され、そのノード２１のchild,brotherのノードが調べられる。ノード２１は、図９の行１でwork配列の配列位置１にセットされている。図１４の例では、ノード２１のchildノードであるノード１０、そのbrotherノードであるノード２０の各ノードが調べられる。まず、ノード１０は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされてはいない。このため、nodeend=1+1=2で示されるwork配列上の配列位置２に、ノード１０が格納される（図９の行４）。続いて、ノード２０も、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされてはいない。このため、nodeend=2+1=3で示されるwork配列上の配列位置３に、ノード２０が格納される（図９の行５）。
【０１２７】
対象ノードの全てのchild,brotherのノードのサーチが終了すると、ステップＳ３１３にて、nodestart=nodestart+1とされる。図９の行６の状態では、nodestart=1+1=2とされる。続いて、ステップＳ３１１に移行する。
【０１２８】
図９の行７の状態では、nodestart=2≦nodeend=3でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
ステップＳ３１２において、図９の行８の状態では、nodestart=2で示される配列位置の対象ノード１０がwork配列から取り出され、その対象ノード１０のchild,brotherのノードが調べられる。対象ノード１０は、図９の行４でwork配列の配列位置２にセットされている。図１４の例では、対象ノード１０のchildノードであるノード４、そのbrotherノードであるノード９の各ノードが調べられる。まず、ノード４は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象となっており、nmark配列上でonされている。このため、ノード４はwork配列には格納されない。続いて、ノード９は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされてはいない。このため、nodeend=3+1=4で示されるwork配列上の配列位置４に、ノード９が格納される（図９の行８）。
【０１２９】
図９の行９の状態では、ステップS３１３において、nodestart=2+1=3とされる。続いて、ステップＳ３１１に移行する。
図９の行１０の状態では、nodestart=3≦nodeend=4でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３０】
ステップＳ３１２において、図９の行１１の状態では、nodestart=3で示される配列位置の対象ノード２０がwork配列から取り出され、その対象ノード２０のchild,brotherのノードが調べられる。対象ノード２０は、図９の行５でwork配列の配列位置３にセットされている。図１４の例では、対象ノード２０のchildノードであるノード１９が調べられる。即ち、ノード１９は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされていない。このため、nodeend=4+1=5で示されるwork配列上の配列位置５に、ノード１９が格納される（図９の行１１）。
【０１３１】
図９の行１２の状態では、ステップＳ３１３において、nodestart=3+1=4とされる。続いて、ステップＳ３１１に移行する。
図９の行１３の状態では、nodestart=4≦nodeend=5でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３２】
ステップＳ３１２において、図９の行１４の状態では、nodestart=4で示される配列位置の対象ノード９がwork配列から取り出され、その対象ノード９のchild,brotherのノードが調べられる。対象ノード９は、図９の行８でwork配列の配列位置４にセットされている。図１４の例では、対象ノード９のchildノードであるノード８が調べられる。即ち、ノード８は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされていない。このため、nodeend=5+1=6で示されるwork配列上の配列位置６に、ノード８が格納される（図９の行１４）。
【０１３３】
図９の行１５の状態では、ステップＳ３１３において、nodestart=4+1=5とされる。続いて、ステップＳ３１１に移行する。
図９の行１６の状態では、nodestart=5≦nodeend=6でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３４】
ステップＳ３１２において、図９の行１７の状態では、nodestart=5で示される配列位置の対象ノード１９がwork配列から取り出され、その対象ノード１９のchild,brotherのノードが調べられる。対象ノード１９は、図９の行１１でwork配列の配列位置５にセットされている。図１４の例では、対象ノード１９のchildノードであるノード１８が調べられる。即ち、ノード１８は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされていない。このため、nodeend=6+1=7で示されるwork配列上の配列位置７に、ノード１８が格納される（図９の行１７）。
【０１３５】
図９の行１８の状態では、ステップＳ３１３において、nodestart=5+1=6とされる。続いて、ステップＳ３１１に移行する。
図９の行１９の状態では、nodestart=6≦nodeend=7でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３６】
ステップＳ３１２において、図９の行２０の状態では、nodestart=6で示される配列位置の対象ノード８がwork配列から取り出され、その対象ノード８のchild,brotherのノードが調べられる。対象ノード８は、図９の行１４でwork配列の配列位置６にセットされている。図１４の例では、対象ノード８のchildノードであるノード７が調べられる。即ち、ノード７は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっており、nmark配列上でonされている。このため、ノード７はwork配列には格納されない（図９の行２０）。
【０１３７】
図９の行２１の状態では、ステップＳ３１３において、nodestart=6+1=7とされる。続いて、ステップＳ３１１に移行する。
図９の行２２の状態では、nodestart=7＝nodeend=7でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
【０１３８】
ステップＳ３１２において、図９の行２３の状態では、nodestart=7で示される配列位置の対象ノード１８がwork配列から取り出され、その対象ノード１８のchild,brotherのノードが調べられる。対象ノード１８は、図９の行１７でwork配列の配列位置７にセットされている。図１４の例では、対象ノード１８のchildノードであるノード１７が調べられる。即ち、ノード１７は、前述のステップＳ３０１からＳ３０８の処理におけるメモリ割付対象とはなっておらず、nmark配列上でonされていない。このため、nodeend=7+1=8で示されるwork配列上の配列位置８に、ノード１７が格納される（図９の行２３）。
【０１３９】
以下同様の処理が実行され、work配列上の配列位置９〜１４に、ノード１６〜ノード１１が順次格納される（図９の行２４〜行４１）。
図９の行４２の状態では、ステップＳ３１３において、nodestart=13+1=14とされる。続いて、ステップＳ３１１に移行する。
【０１４０】
図９の行４３の状態では、nodestart=14＝nodeend=14でステップＳ３１１の判定がＹＥＳとなり、ステップＳ３１２に移行する。
ステップＳ３１２において、図９の行４４の状態では、nodestart=14で示される配列位置の対象ノード１１がwork配列から取り出されるが、図１４に示されるように、対象ノード１１にはchild,brotherのノードがない。このため、work配列へのノード格納は行われない（図９の行４４）。なお、対象ノード１１は、図９の行４１でwork配列の配列位置１４にセットされている。
【０１４１】
図９の行４５の状態では、ステップＳ３１３において、nodestart=14+1=15とされる。続いて、ステップＳ３１１に移行する。
図９の行４６の状態では、nodestart=15＝nodeend=14でステップＳ３１１の判定がＮＯとなり、ステップＳ３１１の判定がＮＯとなって、ステップＳ３１４に移行する。
【０１４２】
以上説明した図３のステップＳ３０９からＳ３１３までの処理によって、nmark配列でonとなっている分岐ノード又はリーフノードの何れかに辿り着くまで、エリミネーションツリーのルートノードから順に各ノードを辿った結果が、work配列に得られる。図１４に対応する図８の例では、work配列に得られた結果は次のようになる。
work＝｛21|10,20|9,19|8,18|17|16|15|14|13|12|11｝ ・・・（７）
ここで、区切り記号「｜」は、レベルの境界を示している。
【０１４３】
以上のようにしてwork配列が確定したら、ステップＳ３１４にて、n=nodeendから１まで１ずつ減じられながら辿られた順の逆順で各work配列要素work(n)のノードが順次取り出される。そして、work配列から順次取り出されたノードが、前述の（４）式及び（６）式として得られている割付チェインchain1及びchain2の末尾に、交互にサイクリックに追加されてゆく。この結果、割付チェインchain1及びchain2は、次のようになる。
chain1＝{1→2→3→4→11→13→15→17→8→9→10} ・・・（８）
chain2＝{5→6→7→12→14→16→18→19→20→21} ・・・（９）
【０１４４】
以上の処理により、ノードのメモリ割付け及び処理順が確定する。最後に、ステップＳ３１５にて、プール毎の割付チェインchain1又はchain2がプール番号順に取り出され、各割付チェインが辿られてノードが取り出され、各ノードに対して順番にメモリ格納領域が割り付けられる。
【０１４５】
前述したように、スパースな正値対象行列Lにおけるノードi の列ベクトルliの大きささは、symbolic decompositionと呼ばれる解析で求めることができる。各ノードに対するLDL^T分解計算結果は、各ノードが登録されている割付チェインに対応するメモリ格納領域に格納されることになる。即ち、chain1に接続される各ノードの処理結果が、この割付チェインでの各ノードの接続順で、メモリ格納領域の前半部分に割り当てられて格納される。同様に、chain2に接続される各ノードの処理結果が、この割付チェインでの各ノードの接続順で、メモリ格納領域の後半部分に割り当てられて格納される。
【０１４６】
今、上述の割付チェインchain1及びchain2に基づく各メモリ格納領域へのノード割当ての順番の対応表は、例えば図１０（ａ）に示されるデータ構成例を有するアサインテーブル（assign table）に保持される。
【０１４７】
また、compressed column storage（圧縮列格納方式）の場合と同様に、相対的な割付順番がmであるノードに対応するpanel（columnを格納する領域）の先頭がメモリ格納領域のどの位置に存在するかが計算されて、その先頭位置を示す値が例えば図１０（ｂ）に示される１次元配列に格納される。
【０１４８】
また実際には、ノードに対するLDL^T分解結果は、非ゼロ要素を含む行のみが圧縮されて２次元配列のpanelに格納される。このため、panel毎にその１次元目の大きささと２次元目の大きさを対で記憶する例えば図１０（ｃ）に示される１次元配列も用意される。
【０１４９】
更には、非ゼロ要素を含む行を指示するためのインデクスの先頭位置を示す値が格納される例えば図１０（ｄ）に示される１次元配列も用意される（図１０（ｅ）参照）。
ステップＳ３１５では、図１０に示されるようなメモリ割当て制御用のデータ群に対して、割付チェインchain1及びchain2に基づいてデータ設定が行われる。後述するLDL^T分解処理の実行時には、これらのデータ群が随時参照されて各ノードの計算結果をメモリ格納領域に割り当てるための制御が実行されることになる。
【０１５０】
次に、図４は、図１のタスクチェイン生成部１０３が実行する前述のステップ５．から７．の動作の詳細を示す動作フローチャートである。ここでは、エリミネーションツリー上の各ノードが、スレッドでの並列計算を制御するためのタスクチェインに登録される。
【０１５１】
タスクチェインは、subtree chainとnode chainを含む。タスクチェインのデータ構造の例としては、メモリ割付チェイン生成処理における割付チェインの場合と同様に、図８（ａ）に示されるようなデータ構造を採用することができる。また、以下の処理において使用される分岐ノード指示用１次元配列nmarkとwork配列のデータ構造例としても、メモリ割付チェイン生成処理の場合と同様の、図８（ｂ）と（ｃ）に示されるようなデータ構造を採用することができる。
【０１５２】
以下の説明では、並列実行されるスレッド数が２である場合の例について説明する。ここで、スレッド数を#threadと表現する。
図４の動作フローチャートにおいて、まず、図７（ａ）に示されるbranchlvl配列と図７（ｂ）に示されるbranch配列がアクセスされることにより、#thread以上の要素数を有する分岐ノード集合が見つけられる（ステップＳ４０１）。ここで、branchlvl配列とbranch配列は、図２の動作フローチャートで示される分岐ノード集合検出処理によって得られている。図７に示される配列構造の例から、レベル１（level 1）の分岐ノード集合は｛21｝（ノード２１を要素とする集合）となる。次に、レベル２（level 2）の分岐ノード集合は{10}（ノード１０を要素とする集合）となる。更に、レベル３（level 3）の分岐ノード集合は{4,7}（ノード４とノード７の集合）となる。そして、#thread=2とすると、２以上の要素数を有する分岐ノード集合は、level 3の分岐ノード集合{4,7}である。この結果、ステップＳ４０２の判定がＹＥＳとなる。
【０１５３】
以上のステップＳ４０１とＳ４０２の処理により、タスクチェイン生成部１０３による前述のステップ５．の処理が実現される。
【０１５４】
次に、ステップＳ４０１で見つかったlevel集合から、１つのノード＝分岐ノードが取り出され、nodelvlとされる（ステップＳ４０３）。ここでは例えば、level 3の集合{4,7}からノード４がnodelvlとして取り出される。
【０１５５】
次に、図８（ｂ）に例示されるような分岐ノード指示用１次元配列nmarkが用意される。図８（ｂ）の１次元配列nmarkは、配列要素数が図８（ａ）の１次元ノード配列８００と同じであり、図８（ａ）と同じ配列位置は同じノードに対応している。そして、各配列位置のノードが分岐ノードである場合には、その分岐ノードに対応する分岐ノード指示用１次元配列nmark上の配列位置にon（オン）を示す値が設定される。ここで、分岐ノード指示用１次元配列nmarkにおいて、ステップＳ４０３にて取り出されたノードnodelvl=4に対応する配列位置の配列要素が、onを示す値に設定される（ステップＳ４０４）。なお、nmark配列の各配列要素は、初期状態において全てクリアされている。
【０１５６】
次に、ノードnodelvlに対応するfirstdescendantのノードがfstdecs変数に設定される（ステップＳ４０５）。図１４の例では、ノード４に対するfirstdescendantのノードはノード１であり、fstdecs=1である。
【０１５７】
続いて、subtree chainと呼ばれる第１のタスクチェインに、ノードnodelvlが加えられる（ステップＳ４０６）。即ち、subtree chainは、次のようになる。
subtree chain={4} ・・・（１０）
このsubtree chainが、例えば図８（ａ）に示されるデータ構造を使って形成される。
【０１５８】
次に、ステップＳ４０１で見つかったlevel集合に残りがあるか否かが判定される（ステップＳ４０７）。
前述のlevel 3の集合{4,7}の場合、まだノード７が残っている。従って、ステップＳ４０７の判定がＹＥＳとなり、ステップＳ４０３の処理に戻る。この結果、level 3の集合{4,7}からノード７が取り出される（ステップＳ４０３）。次に、１次元配列nmark上の上記ノードnodelvl=7に対応する配列位置の配列要素が、onを示す値に設定される（ステップＳ４０４）。更に、nodelvlノード=4に対するfirstdescendantのノードとして、fstdecs=5が設定される（ステップＳ４０５）（図１４参照）。続いて、subtree chainに、ノードnodelvlが加えられる（ステップＳ４０６）。従って、subtree chainは、次のようになる。
subtree chain={4→7} ・・・（１１）
【０１５９】
以上のステップＳ４０３からＳ４０７の処理により、タスクチェイン生成部１０３による前述のステップ６．の処理が実現される。
【０１６０】
次に、分岐ノード指示用１次元配列nmarkの配列要素がonとなっている分岐ノード又はリーフノードの何れかに辿り着くまで、エリミネーションツリーのルートノードから順に各ノードが辿られる。ここでは、図３の動作フローチャートで示したメモリ割付チェイン生成処理の場合と全く同様に、図８（ｃ）に示される１次元のwork配列が用意され、ルートから同じ並列レベルのノードが辿られ、辿られたノードがwork配列に順次格納されてゆく。この処理は、図４のステップＳ３０９からＳ３１３までの処理によって実現される。これらの処理は、前述のメモリ割付チェイン生成処理における図３のステップＳ３０９からＳ３１３までの処理と同じ処理である。これらの処理の結果、図１４に対応する図８の例においてwork配列に得られる結果は、前述した（７）式で示されるものとなる。
【０１６１】
以上のようにしてwork配列が確定したら、ステップＳ４０８にて、n=nodeendから１まで１ずつ減じられながら辿られた順の逆順で各work配列要素work(n)のノードが順次取り出される。そして、work配列から順次取り出されたノードが、第２のタスクチェインであるnode chainに加えられてゆく。この結果、node chainは、次のようになる。
node chain＝{11→12→13→14→15→16→17→18→19→20→10→21}
・・・（１２）
【０１６２】
以上の処理により、第１のタスクチェインであるsubtree chainと、第２のタスクチェインであるnode chainによって、タスクの実行におけるノードの実行順が確定する。
【０１６３】
図５は、図１のLDL^T分解実行部１０４が実行する前述のステップ８．のLDL^T分解実行処理の詳細を示す動作フローチャートである。ここでは、subtree chain、node chainの順番で、各タスクチェインに接続されている各ノードがスレッドの並列数ずつ取り出され、各スレッドのタスクに割り当てられる。
【０１６４】
図５において、まず、ステップＳ５０１において、#thread 数だけタスクが生成される。以下、ステップＳ５０２からＳ５１２は、各スレッド毎に独立して実行される。
各スレッドでは、ステップＳ５０２において、変数snodeと変数nnodeの各値が０に初期設定される。
【０１６５】
次に、例えば第１のスレッドでは、ステップＳ５０３において、図１のタスクチェイン生成部１０３によって生成されたsubtree chainとnode chainがlock（ロック）される。これ以後、第１のスレッドがsubtree chainとnode chainがunlockするまでの間、第２のスレッドは、subtree chainとnode chainへのアクセスを待たされることになる。
【０１６６】
第１のスレッドでは、ステップＳ５０４にて、subtree chainにノードがあるか否かが判定される。
subtree chainにノードがあってステップＳ５０４の判定がＹＥＳの場合、第１のスレッドでは、ステップＳ５０５において、subtree chain の先頭ノードが取り出され、そのノード番号が変数snode に設定され、その後、subtree chainの次のノードが先頭に設定される。今、図８（ａ）に示されるデータ構造において、chain1がsubtree chainであったとした場合において、subtree chainが例えば前述の（１１）式で示されるように得られている場合を考える。この場合、図８（ａ）のレジスタ８０１には、１次元配列８００上のノード４に対応する配列位置が格納されている。また、１次元配列８００上のノード４に対応する配列位置には、１次元配列８００上のノード７に対応する配列位置が格納されている。１次元配列８００上のノード７に対応する配列位置には、nullデータが格納されている。このような例において、第１のスレッドでは、ステップＳ５０５において、レジスタ８０１に格納されている配列位置が、ノード４のノード番号として変数snodeに設定される。その後、レジスタ８０１からアクセスできる１次元配列８００上のノード４に対応する配列位置に格納されているノード７の配列位置が、新たにレジスタ８０１に設定し直される。
【０１６７】
第１のスレッドでは、ステップＳ５０５の処理の後、ステップＳ５０８において、subtree chainとnode chainに対するlockが解除（unlock）される。この結果、第１のスレッドと並列に実行されている第２のスレッドでは、subtree chainとnode chainへのアクセスが可能となる。
【０１６８】
続いて、第１のスレッドでは、ステップS５０９において、変数snodeの値が０であるか否かが判定される。
今、ステップS５０５にてsnodeにノード４のノード番号が設定されたため、ステップS５０９の判定はNOとなる。
【０１６９】
この結果、第１のスレッドでは、ステップＳ５１０にて、変数snodeに設定されているノード番号のノードをルートノードとするsubtreeの各構成ノードに対応する各panelの更新処理が実行される。即ち、前述した（１）式及び（２）式に基づくLDL^T分解処理が、順次実行される。上述の例で、変数snodeに設定されているノード番号に対応するノードがノード４である場合、このノード４をルートノードとするsubtreeの各構成ノードは、図１４より、ノード１、２、３、及び４である。これらのノードに対するpanelの更新処理が、第１のスレッドにおいて順次実行される。このとき、前述したメモリ割付チェイン生成処理における図３のステップＳ３１５にて設定された図１０に示されるようなメモリ割当て制御用のデータ群がアクセスされて、各ノードのメモリ割当てが制御される。
【０１７０】
以上の第１のスレッドによる制御処理と並列に、第２のスレッドにおいても同様の制御処理が実行される。
即ち、第２のスレッドで、ステップＳ５０３にて、subtree chainとnode chainがlockされる。これ以後、第２のスレッドがsubtree chainとnode chainがunlockするまでの間、第１のスレッドは、subtree chainとnode chainへのアクセスを待たされることになる。
【０１７１】
次に、第２のスレッドで、ステップＳ５０４にて、subtree chainにノードがあるか否かが判定される。
subtree chainにノードがあってステップＳ５０４の判定がＹＥＳの場合、第２のスレッドでは、ステップＳ５０５において、subtree chain の先頭ノードが取り出され、そのノード番号が変数snode に設定され、その後、subtree chainの次のノードが先頭に設定される。今、前述の第１のスレッドによるステップＳ５０５の処理によって、図８（ａ）のsubtree chainを示すレジスタ８０１に格納されている配列位置は、ノード４の次のノード７のノード番号を指している。この結果、第２のスレッドによりステップＳ５０５の処理では、ノード７のノード番号が変数snodeに設定される。その後、レジスタ８０１からアクセスできる１次元配列８００上のノード７に対応する配列位置に格納されているnull値が、新たにレジスタ８０１に設定し直される。このnull値は、subtree chainにはこれ以上ノードが無いことを示している。
【０１７２】
第２のスレッドでは、ステップＳ５０５の処理の後、ステップＳ５０８において、subtree chainとnode chainに対するlockが解除（unlock）される。この結果、第２のスレッドと並列に実行されている第１のスレッドでは、subtree chainとnode chainへのアクセスが可能となる。
【０１７３】
続いて、第２のスレッドでは、ステップS５０９において、変数snodeの値が０であるか否かが判定される。
今、ステップS５０５にてsnodeにノード７のノード番号が設定されたため、ステップS５０９の判定はNOとなる。
【０１７４】
この結果、第２のスレッドでは、ステップＳ５１０にて、変数snodeに設定されているノード番号のノードをルートノードとするsubtreeの各構成ノードに対応する各panelの更新処理、即ちLDL^T分解処理が順次実行される。上述の例で、変数snodeに設定されているノード番号に対応するノードがノード７である場合、このノード７をルートノードとするsubtreeの各構成ノードは、図１４より、ノード５、６、及び７である。これらのノードに対するpanelの更新処理が、第２のスレッドにおいて順次実行される。
【０１７５】
以上のようにして、第１のスレッドと第２のスレッドによって、subtree chainに登録されているノード４をルートノードとするsubtreeの構成ノード群に対するpanel更新処理と、ノード７をルートノードとするsubtreeの構成ノード群に対するpanel更新処理が並列に実行されることになる。このとき、前述のメモリ割付チェイン生成処理によって、ノード４をルートノードとするsubtreeの構成ノード群と、ノード７をルートノードとするsubtreeの構成ノード群は、それぞれ異なるメモリ格納領域（プール）に割り付けられている。従って、各subtreeの並列実行において同じメモリ格納領域にアクセスが集中してしまうという事態を回避することが可能となる。
【０１７６】
第１のスレッドでは、前述のステップＳ５１０の処理によってノード４をルートノードとするsubtreeの構成ノード群に対するpanel更新処理が終了すると、再びステップＳ５０２に移行し、変数snodeと変数nnodeがクリアされる。更に、第１のスレッドでは、ステップS５０３にて、subtree chainとnode chainがlockされる。
【０１７７】
続いて、第１のスレッドでは、ステップＳ５０４にて、subtree chainにノードがあるか否かが判定される。今、前述の第２のスレッドによるステップＳ５０５の処理によって、図８（ａ）のsubtree chainを示すレジスタ８０１には、subtree chainにはこれ以上ノードが無いことを示すnull値が設定されている。この結果、ステップＳ５０４の判定はＮＯとなって、第１のスレッドでは、ステップＳ５０６が実行される。
【０１７８】
ステップＳ５０６では、node chainにノードがあるか否かが判定される。
node chainにノードがあってステップＳ５０６の判定がＹＥＳの場合、第１のスレッドでは、ステップＳ５０７において、node chain の先頭ノードが取り出され、そのノード番号が変数ｎnode に設定され、その後、node chainの次のノードが先頭に設定される。今、図８（ａ）に示されるデータ構造において、chain2がnode chainであったとした場合において、node chainが例えば前述の（１２）式で示されるように得られている場合を考える。この場合、図８（ａ）のレジスタ８０２には、１次元配列８００上のノード１１に対応する配列位置が格納されている。また、１次元配列８００上のノード１１に対応する配列位置には、１次元配列８００上のノード１２に対応する配列位置が格納されている。以下、node chainでの各ノードの接続順に従って、各ノードの配列位置にはその次に接続されるノードの配列位置が格納される。そして、最後のノードに対応する配列位置には、nullデータが格納されている。このような例において、第１のスレッドでは、ステップＳ５０７において、レジスタ８０２に格納されている配列位置が、ノード１１のノード番号として変数nnodeに設定される。その後、レジスタ８０２からアクセスできる１次元配列８００上のノード１１に対応する配列位置に格納されているノード１２の配列位置が、新たにレジスタ８０２に設定し直される。
【０１７９】
第１のスレッドでは、ステップＳ５０７の処理の後、ステップＳ５０８において、subtree chainとnode chainに対するlockが解除（unlock）される。
続いて、第１のスレッドでは、ステップS５０９において、変数snodeの値が０であるか否かが判定される。ここで、ステップＳ５０２にて変数snodeが０クリアされた後、ステップＳ５０４の判定はＮＯとなっているため、変数snodeの値は０のままであり、ステップＳ５０９の判定はＹＥＳとなる。
【０１８０】
この結果、第１のスレッドでは、ステップＳ５１１にて更に、変数nnodeの値が０であるか否かが判定される。今、変数nnodeには、ステップＳ５０７にてノード１１のノード番号が格納されているため、ステップＳ５１１の判定はＮＯとなる。
【０１８１】
これにより、第１のスレッドでは、ステップＳ５１２において、変数nnodeに設定されているノード番号に対応するノード１１に対応するpanelの更新処理、即ちLDL^T分解処理が実行される。このとき、前述したメモリ割付チェイン生成処理における図３のステップＳ３１５にて設定された図１０に示されるようなメモリ割当て制御用のデータ群がアクセスされて、各ノードのメモリ割当てが制御される。
【０１８２】
以上の第１のスレッドによる制御処理と並列に、第２のスレッドにおいても更に並列処理が実行される。
即ち、第２のスレッドで、ステップＳ５０３にて、subtree chainとnode chainがlockされる。
【０１８３】
次に、第２のスレッドで、ステップＳ５０４にて、subtree chainにノードがあるか否かが判定される。今、図８（ａ）のsubtree chainを示すレジスタ８０１には、subtree chainにはこれ以上ノードが無いことを示すnull値が設定されている。この結果、ステップＳ５０４の判定はＮＯとなって、第２のスレッドで、ステップＳ５０６が実行される。
【０１８４】
ステップＳ５０６では、node chainにノードがあるか否かが判定される。
node chainにノードがあってステップＳ５０６の判定がＹＥＳの場合、第２のスレッドでは、ステップＳ５０７において、node chain の先頭ノードが取り出され、そのノード番号が変数ｎnode に設定され、その後、node chainの次のノードが先頭に設定される。今、前述の第１のスレッドによるステップＳ５０７の処理によって、図８（ａ）のnode chainを示すレジスタ８０２に格納されている配列位置は、ノード１１の次のノード１２のノード番号を指している。この結果、第２のスレッドによりステップＳ５０７の処理では、ノード１２のノード番号が変数nnodeに設定される。その後、レジスタ８０２からアクセスできる１次元配列８００上のノード１２に対応する配列位置に格納されているノード１３に対応する配列位置が、新たにレジスタ８０２に設定し直される。
【０１８５】
第２のスレッドでは、ステップＳ５０７の処理の後、ステップＳ５０８において、subtree chainとnode chainに対するlockが解除（unlock）される。
続いて、第２のスレッドでは、ステップS５０９において、変数snodeの値が０であるか否かが判定される。ここで、ステップＳ５０２にて変数snodeが０クリアされた後、ステップＳ５０４の判定はＮＯとなっているため、変数snodeの値は０のままであり、ステップＳ５０９の判定はＹＥＳとなる。
【０１８６】
この結果、第２のスレッドでは、ステップＳ５１１にて更に、変数nnodeの値が０であるか否かが判定される。今、変数nnodeには、ステップＳ５０７にてノード１２のノード番号が格納されているため、ステップＳ５１１の判定はＮＯとなる。
【０１８７】
これにより、第２のスレッドでは、ステップＳ５１２において、変数nnodeに設定されているノード番号に対応するノード１２に対応するpanelの更新処理、即ちLDL^T分解処理が実行される。
【０１８８】
以上のようにして、第１のスレッドと第２のスレッドによって、subtree chainに対する処理が終了した後に、node chainに登録されているノード１１に対するpanel更新処理と、ノード１２に対するpanel更新処理が並列に実行されることになる。これ以後も、node chainに登録されている２つずつのノードに対する各panel更新処理が第１及び第２のスレッドによって並列に実行される。このとき、前述のメモリ割付チェイン生成処理によって、node chainに順次登録されているノードは、サイクリックにそれぞれ異なるメモリ格納領域（プール）に割り付けられている。従って、各ノードの並列実行において同じメモリ格納領域にアクセスが集中してしまうという事態を回避することが可能となる。
【０１８９】
各スレッドでは、ステップＳ５１２の処理によって各ノードに対するpanel更新処理が終了すると、再びステップＳ５０２に移行する。そして、各スレッドでは、ステップＳ５０３からＳ５１２の一連の処理によって、node chainに登録されているノードが１つずつ取り出されながら、並列計算が実行される。
【０１９０】
ここで、図１４の例では、例えばノード１５のpanel更新時にはノード１１、１２、１３、１４が参照され、ノード１６のpanel更新時にはノード１２、１３、１４、１５が参照される。この場合、番号が連続する各ノードは、それぞれ異なるメモリ格納領域（プール）に交互に割り付けられているため、１つのスレッドによる１つのノードに対するpanel更新処理においても、１つのメモリ格納領域にアクセスが集中してしまう事態を回避することが可能となる。
【０１９１】
以上の処理の結果、node chainに登録されているノードがなくなる、即ち図８（ａ）のレジスタ８０２からnull値が検出されると、ステップＳ５０６の判定がＮＯ、ステップＳ５０９の判定がＹＥＳ、ステップＳ５１１の判定もＹＥＳとなって、全てのLDL^T分解処理を終了する。
【０１９２】
以上の図５の動作フローチャートの処理により、LDL^T分解実行部１０４による前述のステップ８．の処理が実現される。
次に、並列に実行されるスレッド数が２から３に増やされた場合について説明する。
【０１９３】
メモリ割付けが行われるメモリ格納領域の数は前述の説明の場合と同様に２とする。即ち、前述の図３によるメモリ割付チェイン生成処理では、前述した事例の場合と同じ結果が出力される。
【０１９４】
スレッド数が３になると、図１４のエリミネーションツリーの例において、レベル毎の分岐ノードの集合を探しても要素数が３以上のものはない。この結果、前述の図４によるタスクチェイン生成処理では、subtree chainは生成されず、node chainのみが生成される。この場合、work配列としては、次のようなものが生成される。
work＝{21|10,20|4,9,19|2,3,8,18|1,7,17|1,5,6,16|15|14|13|12|11}
・・・（１３）
これより、node chainとしては、次のようなものが生成される。
node chain＝{11→12→13→14→15→16→6→5→1→17→7→1→18→8
→3→2→19→9→4→20→10→21} ・・・（１４）
【０１９５】
前述の図５によるLDL^T分解実行処理における並列処理では、３個のスレッドに同じようにnode chainから各ノードが取り出されてそれぞれ独立して実行される。
最初、ノード１１、１２、１３が３つのスレッドに割り当てられてpanel更新処理が実行され、空いたスレッドに次のノード１４が割り当てられる。
【０１９６】
例えば、ノード１１の更新処理では、ノード１１のみがアクセスされる。ノード１２の更新処理では、ノード１１と１２がアクセスされる。ノード１３の更新処理では、ノード１２と１３がアクセスされる。これらのノードは、前述のメモリ割付チェイン生成処理によって割付チェインchain1と割付チェインchain2に交互に現れる。つまり、各ノードに対応するメモリ格納領域のliは、メモリ格納領域の前半と後半に分散して割り付けられている。このため、３個のスレッド全てが局所的なメモリ格納領域に集中することを回避することが可能となる。
【０１９７】
処理が進み、ノード１８、８、３が並列実行されているときは、ノード１８の更新処理ではノード１４、１５、１６、１７、１８がアクセスされ、ノード８の更新処理ではノード５、７、８がアクセスされ、ノード３の更新処理ではノード３のみがアクセスされる。このとき、割付チェインchain1にノード３、１５、１７、８、割付チェインchain2にノード５、７、１４、１６、１８というように、ほぼ均等に２つのメモリ格納領域に分散してノード割付けが行われている。このため、アクセスの集中を回避することが可能となる。
【０１９８】
上述の実施形態では、図１のメモリ割付チェイン生成部１０２によって実行される図３のメモリ割付チェイン生成処理では、レベル毎の分岐ノードの集合の要素数が連続にメモリデータを割り当てるセクション（メモリ格納領域）の数以上となるものがサーチされる。これに対して、連続にメモリデータを割り当てるセクションの数を超え、実行スレッド数に近い数をsubtree数とし、このsubtree数以上となるような分岐ノードの集合の要素数がサーチされるように構成されてもよい。このようなサーチにより、メモリ割付チェイン生成部１０２でのメモリ割付けの分散状態をタスクチェイン生成部１０３でのスレッド数の並列状態に合わせることができ、より効果的なメモリアクセス分散が可能となる。
【０１９９】
図１１は、実施形態が適用されるハードウェアシステム構成の例を示す図（その１）である。
マルチコアＣＰＵ１１００が、相互結合網（バス）１１０４を介して、複数のメモリモジュール１１０３と接続される。
【０２００】
マルチコアＣＰＵ１１００は、１つのＣＰＵパッケージ内に、ＣＰＵコア＋Ｌ１キャッシュ１１０１を複数封入したもので、Ｌ２キャッシュ・バスインタフェース１１０２は、各ＣＰＵコア＋Ｌ１キャッシュ１１０１から共通に使用される。
【０２０１】
前述した各ノードが割り付けられるメモリ格納領域は、複数のメモリモジュール１１０３に分散して設定され、或いは、１つのメモリモジュール１１０３内の複数のバンクに分散して設定される。
【０２０２】
前述した並列計算を行うスレッドは、１つのマルチコアＣＰＵ１１００内の各ＣＰＵコア＋Ｌ１キャッシュ１１０１によってそれぞれ実行されるように構成することもできるし、１つのＣＰＵコア＋Ｌ１キャッシュ１１０１がマルチスレッド処理として実行するように構成することもできる。
【０２０３】
図１２は、実施形態が適用されるハードウェアシステム構成の例を示す図（その２）である。
図１２に示されるコンピュータシステムは、ＣＰＵ１２０１、メモリ１２０２、入力装置１２０３、出力装置１２０４、外部記憶装置１２０５、可搬記録媒体１２０９が挿入される可搬記録媒体駆動装置１２０６、及びネットワーク接続装置１２０７を有し、これらがバス１２０８によって相互に接続された構成を有する。同図に示される構成は上記システムを実現できるコンピュータの一例であり、そのようなコンピュータはこの構成に限定されるものではない。
【０２０４】
ＣＰＵ１２０１は、当該コンピュータ全体の制御を行う。メモリ１２０２は、プログラムの実行、データ更新等の際に、外部記憶装置１２０５（或いは可搬記録媒体１２０９）に記憶されているプログラム又はデータを一時的に格納するＲＡＭ等のメモリである。ＣＵＰ１２０１は、プログラムをメモリ１２０２に読み出して実行することにより、全体の制御を行う。
【０２０５】
ＣＰＵ１２０１は、図１１に示されるように、マルチコアタイプのものであってもよい。また、メモリ１２０２は、図１１に示されるように、複数のメモリモジュールから構成されてもよい。
【０２０６】
入力装置１２０３は、例えば、キーボード、マウス等及びそれらのインタフェース制御装置とからなる。入力装置１２０３は、ユーザによるキーボードやマウス等による入力操作を検出し、その検出結果をＣＰＵ１２０１に通知する。
【０２０７】
出力装置１２０４は、表示装置、印刷装置等及びそれらのインタフェース制御装置とからなる。出力装置１２０４は、ＣＰＵ１２０１の制御によって送られてくるデータを表示装置や印刷装置に出力する。
【０２０８】
外部記憶装置１２０５は、例えばハードディスク記憶装置である。主に各種データやプログラムの保存に用いられる。
可搬記録媒体駆動装置１２０６は、光ディスクやＳＤＲＡＭ、コンパクトフラッシュ（登録商標）等の可搬記録媒体１２０９を収容するもので、外部記憶装置１２０５の補助の役割を有する。
【０２０９】
ネットワーク接続装置１２０７は、例えばＬＡＮ（ローカルエリアネットワーク）又はＷＡＮ（ワイドエリアネットワーク）の通信回線を接続するための装置である。
本実施形態によるシステムは、図１の各部に必要な機能を搭載したプログラムをＣＰＵ１２０１が実行することで実現される。そのプログラムは、例えば外部記憶装置１２０５や可搬記録媒体１２０９に記録して配布してもよく、或いはネットワーク接続装置１２０７によりネットワークから取得できるようにしてもよい。
【産業上の利用可能性】
【０２１０】
開示する技術は、有限要素法、偏微分方程式などの解析を行いシミュレーションを行う技術に利用することができる。
【符号の説明】
【０２１１】
１０１ 分岐ノード集合検出部
１０２ メモリ割付チェイン生成部
１０３ タスクチェイン生成部
１０４ LDL^T分解実行部
１１００ マルチコアＣＰＵ
１１０１ ＣＰＵコア＋Ｌ１キャッシュ
１１０２ Ｌ２キャッシュ・バスインタフェース
１１０３ メモリモジュール
１１０４ 相互結合網（バス）
１２０１ ＣＰＵ
１２０２ メモリ
１２０３ 入力装置
１２０４ 出力装置
１２０５ 外部記憶装置
１２０６ 可搬記録媒体駆動装置
１２０７ ネットワーク接続装置
１２０８ バス
１２０９ 可搬記録媒体
【特許請求の範囲】
【請求項１】
スパースな正値対象行列の連立１次方程式を解く演算処理を、該正値対象行列のコレスキー分解に先立ち入力行列の非零要素の構造を解析して得られるエリミネーションツリーを構成するスーパーノードを単位として実行する演算処理方法において、
前記エリミネーションツリーをそのルートノードからサーチすることにより、並列レベル毎の分岐ノードの集合を検出する分岐ノード集合検出処理ステップと、
前記分岐ノードの集合のうち、該集合の要素数が連続にメモリデータが割り当てられる記憶単位である複数のメモリ格納領域の数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリー毎に、該サブツリーを構成するノード群に対する列ベクトルの演算結果を前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるサブツリーメモリ格納領域割付けステップと
前記エリミネーションツリーを構成するノード群のうち、前記サーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群に対する前記列ベクトルの演算結果を、並列レベルが近接しているノード群の演算結果はそれぞれ異なるメモリ格納領域に割り付けられるように、前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるノードメモリ格納領域割付けステップと、
を含むことを特徴とするスパースな正値対象行列の連立１次方程式の演算処理方法。
【請求項２】
前記分岐ノードの集合のうち、該集合の要素数が並列実行される複数のスレッドの数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリーに関する情報を該各サブツリー単位で第１のタスクチェインであるサブツリーチェインに接続するサブツリーチェイン生成ステップと、
前記エリミネーションツリーを構成するノード群のうち、前記スレッドに関するサーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群を、前記エリミネーションツリーのリーフノードからルートノードに向かう順でかつ並列レベル毎にまとまるようにして、第２のタスクチェインであるノードチェインに接続するノードチェイン生成ステップと、
を更に含み、
前記各スレッドは、前記サブツリーチェインに接続されている各サブツリーに関する情報を登録順に選択して該情報に対応するサブツリーを構成するノード群に対する前記列ベクトルの演算を実行し、前記サブツリーチェインで選択すべきエントリがなくなったら、前記ノードチェインに接続されている各ノードに対する前記列ベクトルの演算を登録順に実行する、
ことを特徴とする請求項１に記載のスパースな正値対象行列の連立１次方程式の演算処理方法。
【請求項３】
スパースな正値対象行列の連立１次方程式を解く演算処理を、該正値対象行列のコレスキー分解に先立ち入力行列の非零要素の構造を解析して得られるエリミネーションツリーを構成するスーパーノードを単位として実行する演算処理装置において、
前記エリミネーションツリーをそのルートノードからサーチすることにより、並列レベル毎の分岐ノードの集合を検出する分岐ノード集合検出処理部と、
前記分岐ノードの集合のうち、該集合の要素数が連続にメモリデータが割り当てられる記憶単位である複数のメモリ格納領域の数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリー毎に、該サブツリーを構成するノード群に対する列ベクトルの演算結果を前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるサブツリーメモリ格納領域割付け部と
前記エリミネーションツリーを構成するノード群のうち、前記サーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群に対する前記列ベクトルの演算結果を、並列レベルが近接しているノード群の演算結果はそれぞれ異なるメモリ格納領域に割り付けられるように、前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるノードメモリ格納領域割付け部と、
を含むことを特徴とするスパースな正値対象行列の連立１次方程式の演算処理装置。
【請求項４】
前記分岐ノードの集合のうち、該集合の要素数が並列実行される複数のスレッドの数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリーに関する情報を該各サブツリー単位で第１のタスクチェインであるサブツリーチェインに接続するサブツリーチェイン生成部と、
前記エリミネーションツリーを構成するノード群のうち、前記スレッドに関するサーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群を、前記エリミネーションツリーのリーフノードからルートノードに向かう順でかつ並列レベル毎にまとまるようにして、第２のタスクチェインであるノードチェインに接続するノードチェイン生成部と、
を更に含み、
前記各スレッドは、前記サブツリーチェインに接続されている各サブツリーに関する情報を登録順に選択して該情報に対応するサブツリーを構成するノード群に対する前記列ベクトルの演算を実行し、前記サブツリーチェインで選択すべきエントリがなくなったら、前記ノードチェインに接続されている各ノードに対する前記列ベクトルの演算を登録順に実行する、
ことを特徴とする請求項３に記載のスパースな正値対象行列の連立１次方程式の演算処理装置。
【請求項５】
スパースな正値対象行列の連立１次方程式を解く演算処理を、該正値対象行列のコレスキー分解に先立ち入力行列の非零要素の構造を解析して得られるエリミネーションツリーを構成するスーパーノードを単位として実行するコンピュータに、
前記エリミネーションツリーをそのルートノードからサーチすることにより、並列レベル毎の分岐ノードの集合を検出する分岐ノード集合検出処理ステップと、
前記分岐ノードの集合のうち、該集合の要素数が連続にメモリデータが割り当てられる記憶単位である複数のメモリ格納領域の数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリー毎に、該サブツリーを構成するノード群に対する列ベクトルの演算結果を前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるサブツリーメモリ格納領域割付けステップと
前記エリミネーションツリーを構成するノード群のうち、前記サーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群に対する前記列ベクトルの演算結果を、並列レベルが近接しているノード群の演算結果はそれぞれ異なるメモリ格納領域に割り付けられるように、前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるノードメモリ格納領域割付けステップと、
を実行させるためのプログラム。
【請求項６】
前記分岐ノードの集合のうち、該集合の要素数が並列実行される複数のスレッドの数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリーに関する情報を該各サブツリー単位で第１のタスクチェインであるサブツリーチェインに接続するサブツリーチェイン生成ステップと、
前記エリミネーションツリーを構成するノード群のうち、前記スレッドに関するサーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群を、前記エリミネーションツリーのリーフノードからルートノードに向かう順でかつ並列レベル毎にまとまるようにして、第２のタスクチェインであるノードチェインに接続するノードチェイン生成ステップと、
を更に含み、
前記各スレッドは、前記サブツリーチェインに接続されている各サブツリーに関する情報を登録順に選択して該情報に対応するサブツリーを構成するノード群に対する前記列ベクトルの演算を実行し、前記サブツリーチェインで選択すべきエントリがなくなったら、前記ノードチェインに接続されている各ノードに対する前記列ベクトルの演算を登録順に実行する、
ことを特徴とする請求項５に記載のプログラム。
【請求項１】
スパースな正値対象行列の連立１次方程式を解く演算処理を、該正値対象行列のコレスキー分解に先立ち入力行列の非零要素の構造を解析して得られるエリミネーションツリーを構成するスーパーノードを単位として実行する演算処理方法において、
前記エリミネーションツリーをそのルートノードからサーチすることにより、並列レベル毎の分岐ノードの集合を検出する分岐ノード集合検出処理ステップと、
前記分岐ノードの集合のうち、該集合の要素数が連続にメモリデータが割り当てられる記憶単位である複数のメモリ格納領域の数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリー毎に、該サブツリーを構成するノード群に対する列ベクトルの演算結果を前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるサブツリーメモリ格納領域割付けステップと
前記エリミネーションツリーを構成するノード群のうち、前記サーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群に対する前記列ベクトルの演算結果を、並列レベルが近接しているノード群の演算結果はそれぞれ異なるメモリ格納領域に割り付けられるように、前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるノードメモリ格納領域割付けステップと、
を含むことを特徴とするスパースな正値対象行列の連立１次方程式の演算処理方法。
【請求項２】
前記分岐ノードの集合のうち、該集合の要素数が並列実行される複数のスレッドの数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリーに関する情報を該各サブツリー単位で第１のタスクチェインであるサブツリーチェインに接続するサブツリーチェイン生成ステップと、
前記エリミネーションツリーを構成するノード群のうち、前記スレッドに関するサーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群を、前記エリミネーションツリーのリーフノードからルートノードに向かう順でかつ並列レベル毎にまとまるようにして、第２のタスクチェインであるノードチェインに接続するノードチェイン生成ステップと、
を更に含み、
前記各スレッドは、前記サブツリーチェインに接続されている各サブツリーに関する情報を登録順に選択して該情報に対応するサブツリーを構成するノード群に対する前記列ベクトルの演算を実行し、前記サブツリーチェインで選択すべきエントリがなくなったら、前記ノードチェインに接続されている各ノードに対する前記列ベクトルの演算を登録順に実行する、
ことを特徴とする請求項１に記載のスパースな正値対象行列の連立１次方程式の演算処理方法。
【請求項３】
スパースな正値対象行列の連立１次方程式を解く演算処理を、該正値対象行列のコレスキー分解に先立ち入力行列の非零要素の構造を解析して得られるエリミネーションツリーを構成するスーパーノードを単位として実行する演算処理装置において、
前記エリミネーションツリーをそのルートノードからサーチすることにより、並列レベル毎の分岐ノードの集合を検出する分岐ノード集合検出処理部と、
前記分岐ノードの集合のうち、該集合の要素数が連続にメモリデータが割り当てられる記憶単位である複数のメモリ格納領域の数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリー毎に、該サブツリーを構成するノード群に対する列ベクトルの演算結果を前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるサブツリーメモリ格納領域割付け部と
前記エリミネーションツリーを構成するノード群のうち、前記サーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群に対する前記列ベクトルの演算結果を、並列レベルが近接しているノード群の演算結果はそれぞれ異なるメモリ格納領域に割り付けられるように、前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるノードメモリ格納領域割付け部と、
を含むことを特徴とするスパースな正値対象行列の連立１次方程式の演算処理装置。
【請求項４】
前記分岐ノードの集合のうち、該集合の要素数が並列実行される複数のスレッドの数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリーに関する情報を該各サブツリー単位で第１のタスクチェインであるサブツリーチェインに接続するサブツリーチェイン生成部と、
前記エリミネーションツリーを構成するノード群のうち、前記スレッドに関するサーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群を、前記エリミネーションツリーのリーフノードからルートノードに向かう順でかつ並列レベル毎にまとまるようにして、第２のタスクチェインであるノードチェインに接続するノードチェイン生成部と、
を更に含み、
前記各スレッドは、前記サブツリーチェインに接続されている各サブツリーに関する情報を登録順に選択して該情報に対応するサブツリーを構成するノード群に対する前記列ベクトルの演算を実行し、前記サブツリーチェインで選択すべきエントリがなくなったら、前記ノードチェインに接続されている各ノードに対する前記列ベクトルの演算を登録順に実行する、
ことを特徴とする請求項３に記載のスパースな正値対象行列の連立１次方程式の演算処理装置。
【請求項５】
スパースな正値対象行列の連立１次方程式を解く演算処理を、該正値対象行列のコレスキー分解に先立ち入力行列の非零要素の構造を解析して得られるエリミネーションツリーを構成するスーパーノードを単位として実行するコンピュータに、
前記エリミネーションツリーをそのルートノードからサーチすることにより、並列レベル毎の分岐ノードの集合を検出する分岐ノード集合検出処理ステップと、
前記分岐ノードの集合のうち、該集合の要素数が連続にメモリデータが割り当てられる記憶単位である複数のメモリ格納領域の数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリー毎に、該サブツリーを構成するノード群に対する列ベクトルの演算結果を前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるサブツリーメモリ格納領域割付けステップと
前記エリミネーションツリーを構成するノード群のうち、前記サーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群に対する前記列ベクトルの演算結果を、並列レベルが近接しているノード群の演算結果はそれぞれ異なるメモリ格納領域に割り付けられるように、前記複数のメモリ格納領域から所定の選択規則によって選択したメモリ格納領域に割り付けるノードメモリ格納領域割付けステップと、
を実行させるためのプログラム。
【請求項６】
前記分岐ノードの集合のうち、該集合の要素数が並列実行される複数のスレッドの数以上となる集合をサーチし、該サーチで得られる分岐ノードの集合に含まれる各分岐ノードをルートノードとする各サブツリーに関する情報を該各サブツリー単位で第１のタスクチェインであるサブツリーチェインに接続するサブツリーチェイン生成ステップと、
前記エリミネーションツリーを構成するノード群のうち、前記スレッドに関するサーチで得られる分岐ノードの集合に対応する前記各サブツリーを構成するノード群を含まないノード群を、前記エリミネーションツリーのリーフノードからルートノードに向かう順でかつ並列レベル毎にまとまるようにして、第２のタスクチェインであるノードチェインに接続するノードチェイン生成ステップと、
を更に含み、
前記各スレッドは、前記サブツリーチェインに接続されている各サブツリーに関する情報を登録順に選択して該情報に対応するサブツリーを構成するノード群に対する前記列ベクトルの演算を実行し、前記サブツリーチェインで選択すべきエントリがなくなったら、前記ノードチェインに接続されている各ノードに対する前記列ベクトルの演算を登録順に実行する、
ことを特徴とする請求項５に記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１０−２２４６８２（Ｐ２０１０−２２４６８２Ａ）
【公開日】平成２２年１０月７日（２０１０．１０．７）
【国際特許分類】
【出願番号】特願２００９−６８９５７（Ｐ２００９−６８９５７）
【出願日】平成２１年３月１９日（２００９．３．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２２年１０月７日（２０１０．１０．７）
【国際特許分類】
【出願日】平成２１年３月１９日（２００９．３．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]