パイプライン並列

 ここまでは,コントロール主導での並列化やデータ主導での並列化に焦点を当てて話をしてきましたが,他の手法を使った並列化を行うこともできます。とはいえ,並列Haskellではその手法の多くは意識することなくプログラム中に入り込んでくるので,特にここで取り上げる必要はないと思います。

 意識しないと書けないのは,パイプライン(pipeline)を使った並列化くらいでしょうか? これは,関数をいくつも適用していくような式があったとき,それぞれの関数による処理を逐次的にではなく並列に行わせるという手法です。

f $ g $ h x

 パイプラインは,プロセサの内部構造や工場の流れ作業など,世の中のあらゆるところで使われている手法です。一度,気づいてしまえば,しごく当たり前のやり方のように思えるでしょう。しかし,そうしたものに限って,案外気づかないものです。

 パイプライン並列化では,個々のデータに対する処理にかかる時間そのものは変わりません。むしろ,並列化の負荷などで遅くなります。このため,xがIntのような組み込みの型の場合,この式のそれぞれの関数による処理を並列化したところで意味はありません。しかし,xがリストのような複数の値を持つデータ型だった場合はどうでしょうか? 関数f,g,hは流れ作業的にそれぞれの処理するべき値が来たところで適宜処理を行うことができるため,それぞれの関数の処理を並列化すれば全体的な処理能力(throughput,スループット)を向上させることができます。

 当然ながら,それぞれに処理にかかる時間に偏りがある場合には,処理に一番時間がかかる部分がボトルネック(bottleneck)になってしまいます。パイプライン並列化は,関数プログラミングのスタイルに一番近いため,一見使いやすそうに見えます。が,性能を出すためにはパイプラインのそれぞれの段(stage,ステージ)の処理時間ができるだけ均等になるよう工夫する必要があります。

 さて,パイプライン並列のための演算子の定義を見てみましょう。

infixl 6 $||
($||) :: (a -> b) -> Strategy a -> a -> b
f $|| s = \ x -> f x `sparking` s x

 「関数の適用」と「値に対する戦略の適用」を並列に行う,ただこれだけです。

 通常,このように前の部分からの結果を使って適宜計算を行っていく形の処理を書く場合には,前の部分での処理結果が全く存在しないときに処理を待つ仕組みを入れる必要があります。スレッドを使った並行/並列プログラミングを学んだことのある方なら,そのようなパターンやイディオム(idiom,慣用句)を必須のテクニックとして知っているかもしれません。でもHaskellは非正格の言語なので,(I/O)アクションなどが絡まない純粋な関数間での値のやり取りであれば,そのような仕組みを特に必要としません。それぞれの処理間での同期は,言語の側で勝手に行ってくれます。

 もう一つ説明しておく必要があるのが,$||から派生した,逐次処理のための演算子です。先に説明したように,パイプライン並列で性能を出すには,パイプラインのそれぞれの段で行われる処理の計算時間が均等である必要があります。これを実現するために,ある段ではデータ並列を使ったりといろいろと工夫を凝らしていくわけですが,並列化のための演算子だけでは工夫に限界があります。そこでControl.Parallel.Strategiesモジュールは,逐次処理のための演算子も同時に提供しています。

infixl 6 $|
($|) :: (a -> b) -> Strategy a -> a -> b
f $| s  = \ x -> f x `demanding` s x

 それでは,パイプライン並列の例を見てみましょう。第4回で見た素数列を生成するプログラムは,$||演算子を使うことで以下のように定義できます。

primes = sieve [2..]
sieve (p:ps) = (p :) $|| rnf
             $ sieve $|| rnf
             $ [q | q <- ps, q `mod` p /= 0]

 簡約戦略がrwhnfではなくrnfであることに注意してください。rwhnfを使った場合,並列化して行われる「値に対する評価」がWHNFの時点で終わってしまうため,パイプライン並列化は実現されません。このように書くと,$||演算子では自動的にrnfを適用するよう定義されていればいいと考える人もいるかもしれません。しかし,それではparList rnfのようにデータ並列化戦略と組み合わせることができなくて不便です。このため$||演算子は評価戦略をrnfに固定せず,他の関数や演算子と同様に,評価戦略を与えられる形で定義されているのです。

 なお,このプログラムは最初の2で割る部分に多くの処理時間をさいているので,あまり性能が良い並列プログラムにはなっていません。効率化のためには,条件式などを使ってパイプラインの段を動的に調整する必要があります。

 さて,$|演算子や$||演算子は通常の関数定義における$演算子に対応するものでした。であるならば,(.)演算子に対応する演算子も欲しくなるのではないでしょうか? そうすれば,通常の関数定義でi x = f (g (h x))やi x = f $ g $ h xの代わりにi = f . g . hと書けるように,関数合成を行っているという意図をソースコード上で明確に示せます。

 Control.Parallel.Strategiesモジュールには,そうした目的のための.|演算子や.||演算子も定義されています。また,モナドの>>=演算子と同様に処理の繋がりを命令的な形で記述することを目的とした,逆向きの合成演算子も提供しています。

infixl 9 .|, .||, -|, -||

(.|) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
(.|) f s g = \ x -> let  gx = g x 
                    in   f gx `demanding` s gx

(.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
(.||) f s g = \ x -> let  gx = g x 
                     in   f gx `sparking` s gx

(-|) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
(-|) f s g = \ x -> let  fx = f x 
                    in   g fx `demanding` s fx

(-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
(-||) f s g = \ x -> let  fx = f x 
                     in   g fx `sparking` s fx 

スケルトン並列プログラミング

 前回から今回にかけて説明したコントロール並列やデータ並列などと直交する概念として,スケルトン並列(Skeletal Parallelism)と呼ばれる並列化手法があります。スケルトン並列は,並列計算で使われる処理をあらかじめ抽象化した骨組み(skeleton,並列スケルトン(Parallel Skeleton)やアルゴリズミック・スケルトン(Algorithmic Skeleton)とも呼ばれます)として用意しておき,それらを組み合わせることで並列プログラミングを行おうというものです。

 そうしたスケルトンの例としては,前回説明したndpパッケージのPという接尾辞のついた関数や,今回説明したControl.Parallel.StrategiesモジュールのparMap関数などが挙げられます。また,米GoogleのMapReduceも,GFS(Google File System)の上に乗った一種のスケルトン並列である,という話を聞いたことがある人もいるかもしれません(参考リンク)。

 スケルトン並列を使うメリットはどこにあるのでしょうか? 並列プログラミングの問題点は,並列性を意識してプログラミングをしなければならないところにあります。Haskellの場合には,遅延評価や並列Haskellなどの機能の助けもあってさほど苦労しないかもしれませんが,それでも全く意識しなくていいということにはなりません。また,効率が良い並列プログラムを書こうとすると,プロセサ数の違いやアーキテクチャなどのマシン構成も考慮に入れる必要があります。なぜなら,並列プログラミングを行う際に考慮しなければならない要素は,マシン構成によって違ってくるからです。例えば,プロセサ間のローカルな並列化であるか分散環境であるか,といった違いによって,並列化の負荷に大きな違いが出てきます。また同じローカルな並列化であっても,メイン・メモリーへのアクセス・コストが均一ではないNUMA(Non-Uniform Memory Access)を使っているとか,Cellのように異なるプロセサ・コアを組み合わせたヘテロジニアス・マルチコア(Heterogeneous Multi-Core)を採用しているとか,そうした違いによって最適な並列化は異なってくるでしょう(参考リンク1参考リンク2)。

 一方,スケルトンを使えば,このような並列性の問題をスケルトンの抽象化の下に閉じ込めてしまうことができます。よって,スケルトンのユーザーは,逐次的なプログラムを書いているとほとんど同じ感覚で,そこそこ効率的な並列プログラミングを行うことができるのです。

 言うまでもなく,スケルトン並列の肝は「いかに,うまく抽象化されていて,かつ効率的なスケルトンを提供できるか」というところにあります。MapReduceのmapとreduce(foldなど)を並列化の枠組みとして提供するという仕組みがいかにも直感的でわかりやすいため,ここ最近,MapReduceのこの部分だけをまねる試みが多いようです。しかし.そうした部分をまねることで満たされるのは,あくまで抽象化の面だけに過ぎません。本物のMapReduceでは,GFSの利用などによって,Googleのシステム上で効率よく運用できるものになっていることも重要な要素の一つであるはずです(参考リンク)。このことを忘れ,ただ抽象化の外面をまねて満足するようであれば,まさに「仏作って魂入れず」でしょう。

 スケルトンは,実際に使用しようとする環境で高い効率性を持つことも重要である,ということをゆめゆめ忘れないようにしてください。


著者紹介 shelarcy

 Control.Parallel.Strategiesモジュールの説明を通して,なぜ並列HaskellはOpenMPや並行Clean(Concurrent Clean)の機能とは違い,並列化のインタフェースに関数を採用しているのかが見えてきたのではないでしょうか?

 parやpseqが関数として提供されていることで,今回見てきたように評価戦略を自由に組み替えることが可能になっています。もし,こうした戦略を指示文のような注釈として与えなければならなかったとしたらどうでしょうか。おそらく,Algorithm + Strategy = Parallelismでも指摘しているように,今のような柔軟性を持つことはなかったでしょう。多少近いことはできたとしても,今よりもずっと複雑なものになっていたと思います。

 なお,このような柔軟性はparやpseqが関数として提供されていること,それだけによって実現されたわけではありません。問題を複雑にしないようこれらの関数が今の形で提供されていることや,Control.Parallel.Strategiesモジュール自体の素性の良さもかかわっているということを忘れないでください。もし,これらがあまり合成性を意識して定義されていなかったとしたら,どのみち今のような姿になることは決してなかったと思います。