LU分解の並列化について

斉藤宏樹，廣安知之，三木光範

ISDL Report No. 20020612018

2002年 10月 9日

Abstract

本報告では，HPL(High-Performance Linpack Benchmark)のメインアルゴリズムであるLU分解について説明する．HPLは並列計算機用のベンチマークソフトウェアであり，LU分解を並列化させることで演算性能を測定している．LU分解の並列化について，その方法を示す．

1 はじめに

HPL(High-Performance Linpack Benchmark)は，分散メモリ型並列計算機用のベンチマークソフトウェアであり，並列計算機の演算性能を測定するものである．そのメインアルゴリズムは，密行列の連立１次方程式をLU分解の並列化により解くというものである．LU分解についてのアルゴリズムと，LU分解の並列化の仕組みについて説明する．　　　　　　　

2 LU分解

LU分解は，連立１次方程式の解法である．その原理を，式 1の連立一次方程式を例に示す．

(1)

2.1 LU分解による解法

式 1の係数行列，解の行列，右辺の行列はそれぞれ次のようになる．

Fig.1 各行列

ここで係数行列Aを，下三角行列L(lower triangular matrix)と上三角行列U(upper triangular matrix)Uの積に分解する(分解のアルゴリズムの詳細は後述)．

Fig.2 三角行列LとU

Fig.2 にのようにAをLとUに分解できれば，後はFig.3 に示す手順で解xを求めることができる．

Fig.3 LとUからxを求める手順

このとき，LとUは三角行列のため，Ly=bからyを求める計算量や，Ux=yから解xを求める計算量は小さくなる．

例として，下三角行列Lから解yを得る手順を説明する(Fig.4 参照)．

Fig.4 下三角行列Lと行列y

下三角行列Lから解yを得るためには，Fig.5 に示す前進代入法で解く．

Fig.5 前進代入法

同様に上三角行列Ux=yから解xを得るには，Fig.5 の前進代入法の逆の処理を行う後退代入法で解く．これらの解法の演算量は $O(n$ ²)である．そのためLU分解は，同一の係数行列を用いて複数の連立一次方程式を解く場合に，最初にLU分解をしておくことで，後の計算量が $O(n$ ²)となり，少なくなる利点がある(通常は $O(n$ ³))．

2.2 LU分解のアルゴリズム

LU分解のアルゴリズムには大きく分けて三つの方法，Right-looking algorithm，Left-looking algorithm，Crout algorithmがある．HPLにおいても，ユーザはこれら三つの方法から選択できる．今回は，分散メモリ計算機上で実装することが容易であるright lookingアルゴリズムについて説明する．

Fig.2 に示した，係数行列Aの下三角行列Lと上三角行列Uを求めるアルゴリズムは，以下のようになる．

上三角行列Uを求めるため，枢軸要素(対角線上の要素)より下の要素を0にしていく(Fig.6 参照)．

Fig.6 LU分解のアルゴリズム

Fig.6 より，Uを求める演算の履歴が，Lの要素になることがわかり，Uの1列目の要素とLの1列目の要素が同時に求まっていることがわかる．同様の手順をFig.7 のように行う．

Fig.7 LU分解のアルゴリズム

Fig.7 より，上三角行列Uが求まったため演算は終了である．下三角行列Lも，これまでの演算結果からFig.8 のように同時に求まる．

Fig.8 下三角行列Lの生成

right lookingアルゴリズムにおける係数行列のアクセスパターンを Fig.9 に示す．

Fig.9 right lookingアルゴリズムにおけるアクセスパターン

3 LU分解の並列化

LU分解の並列化とは，係数行列Aを下三角行列Lと上三角行列Uに並列で分解していくことである．行列演算を並列で処理する場合，まず行列をどのように各プロセスに割り当てるかが問題になる．また各プロセスで行列演算を行うには，どのような情報をどのような方法で各プロセスと通信するのかといったことも考慮しなければならない．これらについて説明する．

3.1 行列の分配方法

行列の分配方法には以下に示す三つがある．ただし，ここの例では行列M(12×12)の列方向の分割しかしておらず，実際には行方向への分割を行う場合もある．

１．ブロック分割

Fig.9 ブロック分割

Fig.9 に示すように，プロセス数が3の場合，各プロセスに1/3ずつの連続した領域を割り当てる方法である．

２．サイクリック分割

Fig.10 サイクリック分割

Fig.10 に示すように，1列ずつ各プロセスに循環して割り当てる方法である．各プロセスは，連続していない領域を割り当てられることになる．

３．ブロック・サイクリック分割

Fig.11 ブロック・サイクリック分割

Fig.11 に示すように，何列かをまとめて１つのブロックとして，ブロック単位でサイクリック分割を行う方法．１列のみをブロックにした場合はサイクリック分割になる．この方法においても，各プロセスは連続していない領域を割り当てられることになる．

HPLでは，行，列二方向にブロック・サイクリック分割を適用している(Fig.12 参照)．

Fig.12 HPLにおけるブロック・サイクリック分割

3.2 各プロセスとの通信

各プロセスとの通信には，行方向と列方向の通信があり，行列の分配の仕方で通信の方向は異なってくる．LU分解の並列化においては，枢軸要素の交換による通信と，行列の更新情報による通信が発生する可能性がある．それぞれについて以下に説明する．

１．枢軸要素の交換

Fig.13 枢軸要素の交換

Fig.13 に示すように，枢軸要素には各行の要素のうち，絶対値が最大であるものがくるようにする．これは，計算途中の丸め誤差の影響を減らすという趣旨と，計算途中で枢軸要素が0になることを防ぐ趣旨がある．Fig.13 のように行方向へのブロック分割の場合は，行方向への通信が発生する．

２．行列の更新情報

Fig.14 更新情報の送信

Fig.14 に示すように，1列目の枢軸要素以下を0にする演算は，全行の要素を更新する必要があるため，プロセス1が他のプロセスに各行への更新情報を送信しなければならない．Fig.14 では，列方向へブロック・サイクリック分割しており列方向への通信が発生する．

4 考察

HPLなどのLU分解の並列化については，行方向と列方向にブロック・サイクリック分割しており，行方向と列方向に通信が発生する．その通信の方法はいくつかあり，それらによってロードバランスや，通信量が変化する．今後は，プロセス間の通信方法についても調べる必要がある．

Reference

[1]: 森口繁一，伊理正夫，武市正人 Cによる算法通論東京大学出版会 1992年
[2]: 笹生健卒業論文：ヘテロな環境における並列Linpackの最適化 2001年
[3]: Hisashi Yokota 行列の分解
http://next1.cc.it-hiroshima.ac.jp/numeanal1/node30.html
[4]: Kozo Sato LU分解法 http://www.fuka.info.waseda.ac.jp/~kozo/suuchi/simple_equation/simple_equation_3.html

[5]

西出隆二大学院輪講資料：非対称疎行列連立一次方程式の直接解法 2001年

[6]

青山幸也並列プログラミング虎の巻 MPI版日本IBM株式会社 2001年

Copyright

Copyright (C) 2002 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2002 Mitsunori Miki, All rights reserved.
Copyright (C) 2002 Hiroki Saito, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.
In no event shall the authors be liable for any damages caused in any way
out of the use of this document．