- Haskellでの式評価は、必要となるまで遅延される。並列実行ではどの段階で評価が実行されるのか意識する必要がある。
- 以下、GHCiで検証する。
> let x = 1 + 2 :: Int- この段階でxは未評価なので、式の内容は1 + 2のままで、3ではない。
> :sprint xx = __は未評価であることを示している。Haskellではこの未評価部分をthunkと呼ぶ。
> let x = 1 + 2 :: Int
> let y = x + 1
> :sprint x
x = _
> :sprint y
y = _
> seq y ()
()
> :sprint x
x = 3
> :sprint y
y = 4
-
上記のように、関数が評価されるとthunk部分が評価される。
-
Weak Head Normal Form
- What is Weak Head Normal Form? - Stack Overflow
- 一番外側のコンストラクタまで評価された式をWHNFと呼ぶ
- 完全に評価された式をnormal formという
> let xs = map (+1) [1..10] :: [Int]
> :sprint xs
xs = _
> seq xs ()
> :sprint xs
xs = _ : _
> length xs
10
> :sprint xs
xs = [_,_,_,_,_,_,_,_,_,_]
> sum xs
65
> :sprint xs
xs = [2,3,4,5,6,7,8,9,10,11]
- lengthでは(:)コンストラクタのみ評価され、リストの各要素まで評価されない。
- sumによって(+1)がリストの各要素に適用され、normal formとなる。
Control.Paralle.Strategiesモジュールの解説
data Eval a
instance Monad Eval
runEval :: Eval a -> a
rpar :: a -> Eval a
rseq :: a -> Eval a- rparは並列で評価する部分を指定
- rseqは逐次で評価する部分を指定
- rparもrseqも、評価はWHNFまで。
- rparへの引数は未評価である必要がある。でないと、並列化によるメリットが全くない。
runEval $ do
a <- rpar (f x)
b <- rpar (f y)
return (a,b)- 上記のコードでは、returnはすぐに応答する。
- 結果が揃った時、(a,b)の内容が表示される。
runEval $ do
a <- rpar (f x)
b <- rseq (f y)
return (a,b)-
上記のコードでは、returnは(f y)の処理が終わるまで応答しない。
-
結果が揃った時、(a,b)の内容が表示される。
-
パターンとしては以下が考えられる
- rpar/rpar
- rpar/rseq
- rpar/rsep/rseq
- rparを最後のrseqで再度包む
- rpar部分が並列で走り、最後に結果が出揃ったところでreturnから返ってくる
- rpar/rpar/rseq/rseqでもいい。
-
rpar/rseqは有用ではない。実装者がどの処理を並列にするかを実装時に把握することはできない
-
とりあえず並列で実行したいなら、rpar/rpar
-
もし複数の処理の一つの結果をもって次の処理へと繋ぎたいのであれば、rpar/rseq/rseqパターンが良い
-
以下で実行できる
$ ghc -O2 rpar.hs -threaded -rtsopts
$ ./rpar 1 +RTS -N2
- 例として、Sudokuを解く
- まずは並列なしで
- sudoku1.hsを+RTS -sオプションをつけて実行。これにより実行時の統計情報が取れる
- Total Time : 1.30s ( 1.31s elapsed)
- Total TimeはCPUの総稼働時間と、開始から終了するまでにかかった時間(elapsed)の２つで表される
- rpar/rpar/rseq/rseqパターンで
- sudoku2.hs
- rparはWHNFしか評価しない。そのため、そのままではreturn (as' + bs')で評価が実行され、rparで包んだ意味がなくなる。
- rparの中でnormal formまで評価しきるために
Control.DeepSeqモジュールにあるforceを使う。force :: NFData a => a -> a
- Total Time : 1.46s ( 0.88s elapsed)
- elapsed timeが短縮されたが、半分になったわけではない。
- 仕事量が均等分割されるわけではない
- 仕事量が均等でも、それぞれの実行にかかる時間にはばらつきがある
- dynamic partitioningで
- static partitioning / dynamic partitioning
- staticは、実行時に走らせる並列数を先に決めてしまう方法？
- dynamicでは、細かい粒度のタスクを積み上げ、利用可能なコアに随時振り分けていく
- ということで、rparを呼びまくっておけばGHCが割り振ってくれる。
- rparに渡される式をsparkと呼ぶ。
- (http://stackoverflow.com/questions/958449/what-is-a-spark-in-haskell)
- rparは式へのポインタを配列に加えていくだけの実装。sparkの生成はとても軽い。
- runtimeはsparkをプールに溜め込み、使用可能なコアに適宜割り振っていく(Work Stealingという)
- sudoku3.hs
- parMapでリスト要素にrparをmap、リスト要素をsparkにする
- 実行すると、1.82倍のスピード
- sparkの処理
- Life cycle of a spark
- converted
- runtimeによって並列実行されたsparkの数
- overflowed
- spark poolのサイズをあふれたsparkの数。
-e<n>オプションで実行時のspark pool sizeを指定できる(デフォルト:4096）- 例えば-e100にしてみると、手元ではconverted : 136, overflowed : 864, Total : 1000になった
- dud
- すでに評価済みの式に対してrparが適用された回数。
- GC'd
- 評価する必要がないと判断されたsparkの数
- fizzled
- spark化された時点では評価されなかったが、convertされるまでに別途評価されたsparkの数
- parMapはリストの最初の要素が評価された段階で最初のsparkを生成するので、ファイル全体の読み込みを待たずに処理を開始することができる
- コア数から、Amdahl則により並行処理効果の上限が計算できる
- 1 / ((1 - P) + P / N)
- P : 並列処理できる部分の割合 / N : プロセッサの数
- 1 / ((1 - P) + P / N)
- static partitioning / dynamic partitioning
- WHNFをNormal Formまで評価したい場合、
Control.DeepSeqモジュールのdeepseqを使う
class NFData a where
rnf :: a -> ()
rnf a = a `seq` ()
deepseq :: NFData a => a -> b -> b
deepseq a b = rnf a `seq` b
force :: NFData a => a -> a
force x = x `deepseq` xrnf(reduce to normal-form)は与えられた引数をNormalFormまで評価し切るseq a bがaをWHNFまで評価しbを返すのに対して、deepseq a bはaをNFまで評価してbを返すforceは与えられた引数をNFまで評価してから、そのNFを返す