Haskell による並列・並行プログラミング #3 担当: maton
3章 評価戦略
前回までのあらすじ
type Stragegy a = a -> Eval a という型シノニムを導入
ユーザーがストラテジーを合成することで並列化戦略を書きやすくする
Control.Parallel.Strategies にStrategyのコンビネータAPIが提供されている
3.1 戦略の並列化
rparWith :: Strategy a -> Strategy a : 受け取った戦略をrparで包む
3.2 リストを並列に評価する戦略
evalList :: Strategy a -> Strategy [a] : 受け取った戦略をリストの各要素に適用する戦略にする、全部 rpar で包む parList もある
3.3 例: K平均法
頂点集合とクラスタ数 K を受け取って、 K 個のクラスタの重心を求めるアルゴリズム
チャンクの粒度のトレードオフ
チャンクが少なすぎる→チャンク毎の計算時間のばらつきが大きく、最も遅いチャンクがボトルネックになる
チャンクが多すぎる→チャンク作成と計算結果の合成のオーバーヘッドが大きくなる
p.48 3.4 GCされるスパークと投機的並列性
parList/evalList の問題点： 渡されたリストからrparを適用したリストを再生成しており、末尾再帰でない
引数にアキュムレータを取って末尾再帰っぽく書くこともできるが、作成した並列性はGCに破棄されてしまう
Why: GHCが実行時システムが、スパークプール以外から参照されていないスパークを見つけて破棄しているため
ここで作られた余分な並列性を投機的であると言う。
+RTS -s やThreadScopeで破棄されたスパークを確認できる（GC'dと書かれる）
悪い例 -> sudoku5 (末尾再帰版parList使用)
cabal build --ghc-options="-O2 -threaded -rtsopts -eventlog" sudoku5
cabal exec -- sudoku5 sudoku17.1000.txt +RTS -N2 -l
threadscope sudoku5.eventlog
runEval ではなく using を使って書くのがオススメ
Eval モナドを直接使うときは
rpar を適用したものが束縛するか、
並列計算の外のスコープで変数を束縛すること
p.51 3.5 parBufferを使った遅延ストリームの並列化
題材：RSA暗号 rsa.hs
1 チャンクに分ける→2 各チャンクを暗号化→3 暗号化したチャンクを連結
遅延ストリーム（Data.ByteString.Lazy.ByteString) を使うことで1MBのファイルを処理しても最大レジデンシは200kB程度に抑えられる
2 各チャンクを暗号化 は
rsa1.hs: withStrategy (parList rdeeepseq) を用いた並列化
2.2倍速度向上するけど最大レジデンシが2.3MBに増えている（スペースリーク）
rsa2.hs: withStrategy (parBuffer 100 rdeepseq) を用いた並列化
3.5倍速度向上して、最大レイテンシを300kB程度に抑えられる
TreadScopeを見るとスパークの供給を一定に保っていることがわかる（Overflow 0）
p.55 3.6 チャンク分け戦略
K平均法の実装で使われたチャンク分け技法は parListChink で達成できる
リストの要素をすべてスパーク化するとスパークプールからあふれる時にチャンクにすると良い
rsa1.hs ではスパークプールがOverflowしている
rsa2.hs ではOverflowが起きていない
チャンク分けにもオーバーヘッドがある
kmeans/kmeans.hs ではチャンク分けを初めに1回だけやって、チャンクのリストをparList rseq で並列化している
p.55 3.7 同一性特性
式 x と x \`using\` s のプログラムの意味は同一であってほしい
戦略 s が同一性特性に従う必要がある
ユーザー定義の戦略では同一性特性をコンパイラが保証することはできない（モナド則みたいなもん）
x \`using\` s は x よりも定義が狭い
x \`using\` s の計算が失敗するとき、 x の計算が成功する場合がある。
例えば、遅延評価では正しく動くけど正格評価では失敗する、という例がある。
code:haskell
print $ snd (1div0, "Hello!") -- 成功
print $ snd (1div0, "Hello!") using rdeepseq -- 失敗 (ゼロ除算)
4章 データフロー並列:Parモナド
Eval モナド振り返り
Pros
アルゴリズムを並列性から分離できる
並列評価を組織的に構築できる（モジュラリティ）
Cons
遅延データ構造を並列に評価するスタイルなので、遅延データ構造を作りたくない場合に困る
遅延評価には、挙動の理解や性能調査をややこしくする側面がある
Par モナド
明示的に粒度とデータの依存関係を記述するプログラミングモデルを持つ
monad-par ライブラリの Control.Monad.Par
newtype Par a: Appicative と Monad のインスタンス
runPar:: Par a -> a Parモナドの計算
fork :: Par () -> Par () 渡された「子」Par計算を親と並列に実行する
IVar を用いた通信
Par計算の間で値をやり取りするために用いる
new で IVar a 型の値をつくり、
put で a 型の値を書き込み、
get で a 型の値を読み出す。
7.2 節の MVar と異なり、 put による書き込みは一度だけしかできない。
注意：IVarをrunParから返したりしないこと!
lvish のPar モナドの実装ではSTトリックを用いてこれを防いでいる
fork や IVar を用いたデータフローグラフの構築
see: parmonad.hs
データフローグラフが見れると嬉しいですね
VisPar: visualising dataflow graphs from the Par Monad
Par 計算のコンビネータ
spawn :: NFData a => Par a -> Par (IVar a) : 計算を fork して結果を待つＩＶａｒを返す
parMapM :: NFData b => (a -> Par b) -> [a] -> Par [b] : Parモナドの計算をリストにmapする
現在はControl.Monad.Par.Combinatorにある模様
parMap :: NFData b => (a -> b) -> [a] -> Par [b] : 上記のPure版
put の正格性
タスクが期待された場所で実行されるようにNFDataの制約を与えている
（データが巨大である場合など）NFDataにしたくない場合にはWHNF版のput_も用意されている
p.61 4.1 例：グラフの最短路
次回 5/10
担当: waddlawさん