並列スケルトンによる差分法計算の記述とその効率化
数理第七研究室 野村 芳明
指導教員 胡 振江 助教授

2007/02/06

1 はじめにスケルトン並列プログラミングは並列プログラムの構築を容易にする一方で，並列スケルトンに合わせた処理手順を強要するため非効率性を招くことが多い．個々の並列スケルトンは効率的に実装されていても，それらを組み

図 1 並列スケルトンによる差分法計算合わせた計算にはより効率的な実装が存在することがある．そこで，並列スケルトンによる計算を融合し，より効率的な実装を与える研究がなされている．[1, 2]

列スケルトンを用いて本研究では，ある値の計算にその近傍値のみを使うようルトンプログラムの融合変換による効率化手法を提案し

uls 1 = shiftr (boundary n 0) us n ;..
.

た．この計算は微分方程式の数値解法である差分法で中uls l = shiftr (boundary n (−l + 1)) uls l−1 ;な局所的な依存関係を持った計算を対象として，並列スケ心となる計算である．

urs 1 = shiftl (boundary n (N + 1)) us n ;..
.

2 並列スケルトン

urs r = shiftl (boundary n (N + r)) urs r−1 ;本稿で用いる並列スケルトンの定義を示す．

map f [a1 , . . . , an ] = [f a1 , . . . , f an ]zip [a1 , . . . , an ] [b1 , . . . , bn ] = [(a1 , b1 ), . . . , (an , bn )]shiftl e [a1 , . . . , an ] = [a2 , . . . , an , e]shiftr e [a1 , . . . , an ] = [e, a1 , . . . , an−1 ]3 並列スケルトンによる差分法計算の記述
本手法が対象とする計算は，漸化式

 initial iboundary n iuni =n−1f (un−1i−l , . . . , ui+r )n=0i∈/ [1, . . . , N ]otherwisezs = zipl+1+r uls l · · · uls 1 us n urs 1 · · · urs r ;
where
zip2
= zip
zipm as bs = zipm−1 (zip as bs)
us n+1 = map f 0 zs
where
f 0 (· · · ((u−l , u−l+1 ), u−l+2 ), . . . , ur )= f (u−l , u−l+1 , . . . , ur )と記述できる．計算の概要を図 1 に示す．
このプログラムは大量の中間データを介した処理を行っているため，このままでは非常に効率が悪い．この問が与えられたとき題は本効率化手法によって解決される．

uT1 , uT2 , . . . , uTNを求める計算である．この計算は陽解法の差分法スキームを一般化したものである．
時刻 n の状態から時刻 n + 1 の状態を求める計算は並4 融合変換による差分法プログラムの効率化
並列スケルトンの融合は，より一般的な計算を扱う拡張並列スケルトンを導入し，なされる計算を拡張並列スケルトンで表現することで行う．本手法では，拡張並列スケル

(ID-RULE)
as → s-map bound (strip, 0, 0) as(MAP-RULE)
map g (s-map bound (f, j, k) as) → s-map bound (g ◦ f, j, k) as(SHIFTL-RULE)
e = f [bN +1+j , . . . , bN +1+k ], N = length as,
bi = if 1 ≤ i ≤ N then ai else bound i
shiftl e (s-map bound (f, j, k) as) → s-map bound (f, j + 1, k + 1) as(SHIFTR-RULE)
e = f [b0+j , . . . , b0+k ], N = length as,
bi = if 1 ≤ i ≤ N then ai else bound i
shiftr e (s-map bound (f, j, k) as) → s-map bound (f, j − 1, k − 1) as(ZIP-RULE)
zip (s-map bound (f1 , j1 , k1 ) as) (s-map bound (f2 , j2 , k2 ) as)→ s-map bound (f3 , j1 ↓ j2 , k1 ↑ k2 ) as
where
f3 = (f1 ◦ subarr j10 k10 ) 4 (f2 ◦ subarr j20 k20 )j10 = j1 − (j1 ↓ j2 ), k10 = k1 − (j1 ↓ j2 )j20 = j2 − (j1 ↓ j2 ), k20 = k2 − (j1 ↓ j2 )
図2

拡張並列スケルトンの融合規則に対して与える．

5 まとめと今後の課題
本手法により，簡潔に記述された並列スケルトンプログ
図3

拡張並列スケルトン s-map の計算

ラムから複雑な実装を必要とする効率的なプログラムを融合変換によって得られるようになった．また，この変換を与えたことにより差分法計算をスケルトン並列プログ

トンラミングの枠組みで議論することが可能になった．

s-map bound (f, j, k) [a1 , . . . , aN ] = [c1 , . . . , cN ]whereci = f [bi+j , bi+j+1 , . . . , bi+k ]bi = if 1 ≤ i ≤ N then ai else bound iを導入する．なされる計算を図 3 に示す．
拡張並列スケルトン s − map の融合規則を図 2 に示す．
これにより前節の計算は，ひとつの計算

usn+1 = s-map (boundary n) (f, −l, r) usnへと変換することができる．
この s-map の計算は，繰り返して行う場合には，通信今後の課題としてはまず，扱える計算の拡大が挙げられる．多次元空間上の計算や陰解法スキームの計算などがその対象である．また，本手法とは別の抽象化を用いた差分法計算プログラムに対して，本手法が適用可能な形への変換を考えることも今後の課題である．

参考文献[1] C. Grelck and S. B. Scholz. Merging Compositionsof Array Skeletons in SAC. Parallel Computing,Vol. 32, No. 7+8, pp. 507–522, 2006.

をまとめて行いメモリアクセスの局所化をはかることで[2] Z. Hu, H. Iwasaki, and M. Takeichi. An Accu-

より効率的な実装を与えることができる．従って，s-map

mulative Parallel Skeleton for All. In Proceedingsのは実装は，s-map を t 回繰り返す計算of the 11th European Symposium on Programming

diﬀerential 0 boundary (f, j, k) = id
diﬀerential t boundary (f, j, k)= s-map (boundary (t − 1)) (f, j, k)◦ diﬀerential (t − 1) boundary (f, j, k)(ESOP 02), Vol. 2305 of Lecture Notes in Computer Science, pp. 83–97. Springer-Verlag, 2002.