PARCEL SYCL v1.2 / 利用者ガイド 利用者ガイド API リファレンス 検索 ダウンロード English

10 前処理

 一般に反復解法では, K≈AK \approx Aとなるように前処理行列を選ぶと, 収束に必要な反復回数が減少する. アルゴリズムに見られる「solvezfromKz=r\mathrm{solve}\ z\ \mathrm{from}\ Kz = r」型の計算は「Az=rAz = rをzzについて近似的に解く」ことに相当する. この近似の精度を上げれば反復回数が減少するが, 逆にこの部分の計算のオーバーヘッドが増加する. 並列計算でない場合には, この近似計算に不完全LU分解を用いることが多いが, 並列計算の場合には, 前処理計算の並列処理手法が必要となる. 本ライブラリルーチンでは並列前処理法としてポイント Jacobi 法, ブロック Jacobi 法, Jacobi 法を採用している. 記号の約束は線形ソルバの章の冒頭に示したとおりである.

 前処理はソルバのset_precon_algo()に次の値を与えて選ぶ. サンプルプログラムではコンパイル時に-Dparcel_solver_precon_algo=<値>で, 実行時に環境変数PARCEL_PRECON=<値>で指定できる.

値 定数 前処理 付随する設定
0 parcel::PRECON_NONE 前処理なし (z=rz = r) なし
1 parcel::PRECON_POINTJACOBI ポイント Jacobi 前処理 なし
2 parcel::PRECON_BLOCKJACOBI ブロック Jacobi 前処理 (ブロック内 ILU(0)) set_blockjacobi(nb), set_scaling_matrix(), set_scaling_vector()
4 parcel::PRECON_JACOBI Jacobi 前処理 set_jacobi(ITER), set_scaling_matrix(), set_scaling_vector()

 以下では係数行列をA=LA+DA+UAA = L_A + D_A + U_A (DAD_Aは対角部分, LAL_A・UAU_Aは狭義下三角・狭義上三角部分) と分解し, R=LA+UAR = L_A + U_Aと書く. 各アルゴリズムは前処理の 1 回の適用「solvezfromKz=r\mathrm{solve}\ z\ \mathrm{from}\ Kz = r」の中身を示す.


10.1 スケーリング

 ブロック Jacobi 前処理と Jacobi 前処理には, 行列スケーリングとベクトルスケーリングを併用できる. いずれも値の範囲を低精度 (半精度) の表現範囲に収めるための処理である. set_scaling_matrix()・set_scaling_vector()で明示的に指定でき, 指定しない場合は次のように自動で決まる.

 行列スケーリングがどの前処理の作用を変えるかは各節で述べる.


10.2 ポイント Jacobi 前処理 [1]

 前処理行列KKとして係数行列AAの対角成分のみを用いる (K=DAK = D_A). 不完全LU分解など他の前処理法と比べると効果は小さいが, 各行が独立に処理でき, プロセッサ間通信も不要である. 対角成分が 0 の行はKKの対角要素を 1 に置き換える. スケーリングは行わない.

 aiia_{ii}はAAの対角要素, did_{i}はK−1K^{-1}の対角要素, nlocaln_{local}は各 MPI プロセスが担当する行数である.

  1. fori=1,…,nlocalinparallel\mathrm{for}\ i = 1,\ldots,n_{local}\ \mathrm{in}\ \mathrm{parallel}
  2.   ifaii=0then\mathrm{if}\ a_{ii} = 0\ \mathrm{then}
  3.     di=1d_{i} = 1
  4.   else\mathrm{else}
  5.     di=1/aiid_{i} = 1\ /\ a_{ii}
  6.   endif\mathrm{endif}
  7. end\mathrm{end}

 1〜7 行目は前処理行列の作成時に 1 回だけ行う. 前処理の適用は次のとおりである.

  1. fori=1,…,nlocalinparallel\mathrm{for}\ i = 1,\ldots,n_{local}\ \mathrm{in}\ \mathrm{parallel}
  2.   zi=diriz_{i} = d_{i}r_{i}
  3. end\mathrm{end}


10.3 Jacobi 前処理 [1]

 Jacobi 前処理は, Az=rAz = rを Jacobi 反復で近似的に解く PARCEL 独自の前処理である. 1 反復内の各行に依存性がないため GPU 向けの前処理である. 反復回数ITERITERはset_jacobi(ITER)で指定する (既定 1. サンプルプログラムではコンパイル時に-DJACOBI_ITER=<値>).

 前処理行列の作成時にDA−1D_A^{-1}を求めて保持する (aii=0a_{ii} = 0の行はDA−1D_A^{-1}の要素を 1 とする). B=DA−1RB = D_A^{-1}Rの値は既定では (A64FX 向けのビルドを除き) 保持せず, 5 行目でAAの値とDA−1D_A^{-1}からbij=di−1aijb_{ij} = d_i^{-1}a_{ij}をその場で計算する (前処理行列の精度への丸めは保持する場合と同じなので値は同じ. メモリを使って速くする場合の-DPARCEL_JACOBI_ONTHEFLY=0は「メモリと速さの選択」). 全ての行に対角要素が格納されている必要がある. PARCEL はこれを検査しないので, 対角要素が格納されていない行があると前処理の結果は不正になる. 前処理の適用は次のとおりである. ψ\psiはベクトルスケーリング無効時は 1 である.

  1. ψ=max⁡i|ηiri|\psi = \max_{i}|\eta_{i}r_{i}|
  2. c=DA−1r/ψc = D_{A}^{-1}r\ /\ \psi
  3. z(0)=cz^{(0)} = c
  4. fork=1,…,ITER\mathrm{for}\ k = 1,\ldots,ITER
  5.   z(k)=c−Bz(k−1)z^{(k)} = c - Bz^{(k - 1)}
  6. end\mathrm{end}
  7. z=ψz(ITER)z = \psi z^{(ITER)}

 5 行目はz(k)=z(k−1)+DA−1(r/ψ−Az(k−1))z^{(k)} = z^{(k-1)} + D_A^{-1}(r/\psi - Az^{(k-1)})と同じであり, 反復は初期値z(0)=DA−1r/ψz^{(0)} = D_A^{-1}r/\psiから始まる. したがって作用は K−1=∑l=0ITER(−DA−1R)lDA−1K^{-1} = \sum_{l=0}^{ITER}\left( -D_A^{-1}R \right)^{l}D_A^{-1} で, ゼロ初期値からの Jacobi 反復 (減衰係数 1) をITER+1ITER + 1回行ったものに等しい. ITER=1ITER = 1でもK−1=DA−1−DA−1RDA−1K^{-1} = D_A^{-1} - D_A^{-1}RD_A^{-1}であり, ポイント Jacobi 前処理 (K−1=DA−1K^{-1} = D_A^{-1}) とは異なる.

 BBは係数行列AAの行ポインタと列番号を複製せずに共有する. 値を保持する場合 (-DPARCEL_JACOBI_ONTHEFLY=0, または下の対象外の場合) は, 値だけをAAと同じ並び (対角の位置は 0) で持つ. 5 行目では行ごとに控えた対角の位置で対角を飛ばす. 既定では前処理を適用するたびにAAの値も読む. 各ソルバは前処理をsolver()の中で作り, solver()の中だけで使う (固有値ソルバの内部線形ソルバも同じ) ので, 通常の使い方ではsolver()の実行中にAAを破棄・変更しなければよい (solver()を呼ぶたびに作り直すので, 呼び出しの間にAAの値を変えるのは構わない). 前処理行列parcel::precon_matrixを直接作って使う場合 (pgmresのexternal_preconなど. 通常は使わない) は, 使い終えるまでAAを破棄・変更してはならない. ITER=1ITER = 1 (既定) では反復用の作業ベクトルを確保しない.

 BBの値をその場で計算する対象は, CRS 形式の行列で, 行列スケーリングが無効で, 係数行列・前処理行列・前処理の演算精度のいずれも double-double でない場合である. 半精度 (FP16) の前処理は行列スケーリングが既定で有効になるので, 値を保持する. 対象外の場合は-DPARCEL_JACOBI_ONTHEFLY=0と同じく値を保持する.

 MPI 並列時は 5 行目の前にz(k−1)z^{(k-1)} (1 回目はcc) の袖領域を通信する. BBは通信込みの大域行列として定まるため, 前処理の作用は MPI の分割数によらない.

 行列スケーリング有効時は, ηiaij\eta_i a_{ij}からDA−1D_A^{-1}とBBを作り, 2 行目でrrにηi\eta_iを掛ける. DAD_AとRRが同じ係数で割られるためBBとccは変わらず, 前処理の作用は変わらない (丸め誤差を除く).


10.4 ブロック Jacobi 前処理 [1]

 前処理行列KKとして係数行列AAのブロック対角成分をとり, 各ブロック内でフィルイン無し不完全LU分解 (ILU(0)) を用いる. ブロックの外にある要素は無視する. 各 MPI プロセスが担当するnlocaln_{local}行を連続するnbnb個のブロック (行数は⌊nlocal/nb⌋\lfloor n_{local}/nb \rfloorまたは⌊nlocal/nb⌋+1\lfloor n_{local}/nb \rfloor + 1) に分割するため, ブロックがプロセスをまたぐことはなく, 通信は不要で, 各ブロックは完全に並列に処理できる. 一方で前処理の作用は MPI の分割数とnbnbに依存する.

 ILU(0) は, 正方行列AAを下三角行列LLと上三角行列UUの積に近似分解する際に, AAの非零要素の位置 (非零パターン) 以外に値が入ること (フィルイン) を許さない不完全LU分解である. フィルインを考慮しないことで, 分解後の行列のメモリ使用量を元の行列と同じに抑えられる.

 𝑓𝑖𝑟𝑠𝑡b\mathit{first}_{b}・𝑙𝑎𝑠𝑡b\mathit{last}_{b}はブロックbbの先頭行と最終行, PPはAAの非零パターンである. aija_{ij}はAAの要素の複製を上書きしていく.

  1. forb=1,…,nbinparallel\mathrm{for}\ b = 1,\ldots,nb\ \mathrm{in}\ \mathrm{parallel}
  2.   fori=𝑓𝑖𝑟𝑠𝑡b+1,…,𝑙𝑎𝑠𝑡b\mathrm{for}\ i = \mathit{first}_{b} + 1,\ldots,\mathit{last}_{b}
  3.     fork=𝑓𝑖𝑟𝑠𝑡b,…,i−1with(i,k)∈P\mathrm{for}\ k = \mathit{first}_{b},\ldots,i - 1\ \mathrm{with}\ (i,k) \in P
  4.       aik=aik/akka_{ik} = a_{ik}\ /\ a_{kk}
  5.       forj=k+1,…,𝑙𝑎𝑠𝑡bwith(i,j)∈Pand(k,j)∈P\mathrm{for}\ j = k + 1,\ldots,\mathit{last}_{b}\ \mathrm{with}\ (i,j) \in P\ \mathrm{and}\ (k,j) \in P
  6.         aij=aij−aikakja_{ij} = a_{ij} - a_{ik}a_{kj}
  7.       end\mathrm{end}
  8.     end\mathrm{end}
  9.   end\mathrm{end}
  10. end\mathrm{end}

 分解後, ブロック内の狭義下三角部分と対角要素 1 からLL (単位下三角行列) を, 対角を含む上三角部分からUUを作る.

 lijl_{ij}・uiju_{ij}はLL・UUの要素, ηi\eta_{i}は行列スケーリングの係数 (無効時は 1), ψ\psiはベクトルスケーリングの係数 (無効時は 1) である.

  1. ψ=max⁡i|ηiri|\psi = \max_{i}|\eta_{i}r_{i}|
  2. forb=1,…,nbinparallel\mathrm{for}\ b = 1,\ldots,nb\ \mathrm{in}\ \mathrm{parallel}
  3.   fori=𝑓𝑖𝑟𝑠𝑡b,…,𝑙𝑎𝑠𝑡b\mathrm{for}\ i = \mathit{first}_{b},\ldots,\mathit{last}_{b}
  4.     yi=ηiri/ψ−∑j=𝑓𝑖𝑟𝑠𝑡bi−1lijyjy_{i} = \eta_{i}r_{i}\ /\ \psi - \sum_{j = \mathit{first}_{b}}^{i - 1} l_{ij}y_{j}
  5.   end\mathrm{end}
  6.   fori=𝑙𝑎𝑠𝑡b,…,𝑓𝑖𝑟𝑠𝑡b\mathrm{for}\ i = \mathit{last}_{b},\ldots,\mathit{first}_{b}
  7.     zi=(yi−∑j=i+1𝑙𝑎𝑠𝑡buijzj)/uiiz_{i} = (y_{i} - \sum_{j = i + 1}^{\mathit{last}_{b}} u_{ij}z_{j})\ /\ u_{ii}
  8.   end\mathrm{end}
  9. end\mathrm{end}
  10. z=ψzz = \psi z

 行列スケーリング有効時も ILU(0) 分解はスケーリング前のAAに対して行い, 4 行目で入力にηi\eta_iを掛ける. したがって作用はK−1=U−1L−1SK^{-1} = U^{-1}L^{-1}S (K=S−1LUK = S^{-1}LU) となり, Jacobi 前処理と異なり行列スケーリングの有無で前処理の作用が変わる. 全行でmax⁡j|aij|\max_j |a_{ij}|が等しい行列 (例えば中心 -6 の 7 点差分行列) ではSSはスカラー倍であり, 線形ソルバの反復には影響しないが, AK−1AK^{-1}の固有値はその倍率だけ変わる.

 ブロックを細かくするほど並列度は上がるが, 無視する要素が増えるため前処理の効果は弱まる. GPU での選び方は「ソルバの選び方」の「前処理」に示す.