Haskell による並列・並行プログラミング #4 担当: waddlawさん
4章 データフロー並列:Parモナド
p.61 4.1 例:グラフの最短路
Floyd-Warshall アルゴリズム: O(n^3)
復習
return :: a -> Par a
spawn :: NFData a => Par a -> Par (IVar a)
p.65 fwsparse 直列版と並列版の比較
1コア -N1 を明示的に指定しても直列版が11秒, 並列版が4秒程度と、大きく差が出ている、なんで?
p.65 4.2 パイプライン並列
N段の並列化可能な処理を段毎にプロセッサに割り当てる
パイプラインの段毎に処理速度が異なるという課題がある
threadscope rsa-pipeline.eventlog
詰まってるので 0.01s 単位に拡大しよう
消費者が早い分には問題ないが、生産者が早いと、未処理のデータ構造がヒープ上に蓄積し、GCのオーバーヘッドを招く
TOC理論風にいえば、仕掛品が積み上がっている≒ボトルネックがある状態
p.69 4.2.1 生産者の流量制限
ストリームの構築子の1つにForkを作ることを明示化するFork構築子を加えることで流量を制限できる
生産者: ユーザーの指定に従ってストリーム構築中に定期的にFork構築子を挿入する
消費者: 消費中にFork構築子を見つけたら、残りの計算をForkする
宿題:Forkに対応した流量制限の実装。
p.69 4.2.2 パイプライン並列の制限
データ並列に比べ、パイプライン数に並列性が制限されやすい
runParから別のrunParへ処理を移すことができない(IVarを取り出せない)
ParIOモナドを用いるとIOで並列計算が可能になるが、決定性の保証が失われる
次回担当 wado さん