7.24. Concurrent HaskellおよびParallel Haskell

GHCは、並行プログラミングおよび並列プログラミングに対応するための、Haskellへの大規模な拡張をいくつか実装している。まず用語をはっきりさせておこう。

並列性(parallelism)とは、実行性能の向上を目的として、Haskellプログラムを複数のプロセッサ上で走らせることである。理想的には、これは不可視に、意味を変更することなく為されるべきである。
並行性(concurrency)とは、それぞれIOを行う複数のスレッドを使ってプログラムを実装することである。確かに並行Haskellプログラムは並列な機械上で走らせることができるが、並行性を使うのは、第一目的として実行性能を得るためではなく、それが当該プログラムを書くための最も単純で最も直接的な方法だからである。スレッドは入出力を行うので、プログラムの意味は必然的に非決定的なものになる。

GHCは並行性と並列性の両方に対応している。

7.24.1. Concurrent Haskell

Concurrent HaskellとはGHCの並行性拡張に付けられた名前である。これはデフォルトで有効になっており、特別なフラグは必要ない。Concurrent Haskellの論文は今でも素晴らしいリソースであるし、Tackling the awkward squadもそうである。

プログラマに対しては、Concurrent Haskellでは新しい言語要素は導入されず、単なるライブラリ(Control.Concurrent)の形を取る。このライブラリからは例えば次のような関数がエクスポートされている。

スレッドのforkやkill。
スリープ。
MVarと呼ばれる、同期化された変更可能変数
bound threadの補助関数。Extending the FFI with concurrencyを見よ。

7.24.2. Software Transactional Memory

GHCは、Concurrent Haskellのスレッドの動作を統括するための新しい方法をサポートするようになった。これはSoftware Transactional Memory(STM)と呼ばれる。STMの論文は、STMとは何か、どう使うのか、についての素晴らしい入門文書である。

使うのに必要な主要ライブラリはstmライブラリである。サポートされる主な機能は以下の通り。

分割不能ブロック。
トランザクション変数
トランザクションを組み合わせるための演算(retryとorElse)。
データの不変条件。

これらの機能は全て先に述べた論文に記述されている。

7.24.3. Parallel Haskell

GHCには、対称的・メモリ共有型のマルチプロセッサ(SMP)上でHaskellプログラムを並列実行することのサポートが含まれている。デフォルトでは、プログラムはひとつのプロセッサ上で走る。並列実行されてほしい場合、プログラムを-threaded付きでリンクし、RTSの-Nオプション付きで実行せねばならない。(4.15. SMP並列計算を使うを見よ)。OSスレッドはRTSオプション-Nで指定された数だけ並列に実行され、ランタイムはこれらに対して実行中のHaskellスレッドをスケジュールする。

GHCが並列実行に対応しているのはメモリ共有型のマルチプロセッサだけである。Glasgow Parallel Haskellは、Parallel Haskellのプログラムを、複数の機械からなるクラスタ、および単一のマルチプロセッサの両方で動かす。GPHはGHCとは別に開発・配布されている。(The GPH Pageを見よ)。ただしGPHの現在の版はかなり古いGHC(4.06)を元にしている。

7.24.4. 純粋なコードに並列計算用の注釈を加える

通常の単一スレッドのHaskellプログラムは、SMP並列性を有効にしただけではその恩恵を被ることができない。並列性をコンパイラから見えるようにしてやる必要があるのだ。これには、Concurrent Haskell(7.24.1. Concurrent Haskell)を使ってスレッドをforkするという方法もあるが、純粋なコードから並列性を取り出す場合、最も単純な方法はparコンビネータを使うことである。これは、seqと強く関連している(また、良く一緒に使われる)。これらはどちらもparallelライブラリにある。

infixr 0 `par`
infixr 1 `pseq`

par  :: a -> b -> b
pseq :: a -> b -> b

式(x `par` y)は、xの(弱頭部正規形までの)評価をスパークにし、yを返す。スパークはFIFO順に実行待ちに入るが、すぐには実行されない。ランタイムが待機状態のCPUを見つけると、スパークはスレッドにされ、その新しいスレッドが待機状態のCPUで走らされる。この方法で、利用可能な並列性が実CPU間で分散されることになる。

例として、我々の宿敵であるnfibの並列版を考えよう。

import Control.Parallel

nfib :: Int -> Int
nfib n | n <= 1 = 1
       | otherwise = par n1 (pseq n2 (n1 + n2 + 1))
                     where n1 = nfib (n-1)
                           n2 = nfib (n-2)

nの値が1より大きいときは、parを使って、nfib (n-1)を評価するスレッドをスパークさせる。次に、pseqを使って、親スレッドでnfib (n-2)を評価し、その後でこれらの二つの部分式を加算するようにする。この分割統治法において、計算の枝の一方だけに新しいスレッドをスパークさせている。(一方の枝は親が評価する)。また、親が式(n1 + n2 + 1)中のn1を評価する前にn2を評価することを保証するためにpseqを使わなければならない。式を(n2 + n1 + 1)と並べ替えるだけでは不十分である。コンパイラが加数を左から順に評価するコードを生成するとは限らないからである。

seqでなくpseqを使っていることに注意。この二つはほとんど同等だが、実行時の振る舞いが微妙に異なる。seqはどちらの引数を先に評価することもあるが、pseqは最初の引数を二番目の引数より先に評価することが決まっているので、parと組み合わせて評価順を制御するにはこちらの方が適している。

parを使うとき、一般的な経験則としては、スパークするのは後で必要とされるものであるべきだが、一方、あまりすぐ必要とされるものであるべきではない。また、あまり小さい計算をスパークさせるべきではない。得られる並列性に比べてそれをforkするコストが比較的高いからである。実際には、これらの比率を正しく把握するのは難しい。

実行時の統計情報から、parがどの程度うまく働いているかについての情報を少々集めることができる。4.17.3. ガベッジコレクタを制御するためのRTSオプションを見よ。

並列性を表現するためのより洗練されたコンビネータがparallelパッケージのControl.Parallel.Strategiesモジュールにある。このモジュールはparを基に機能を構築しており、例えば並列mapのような、並列計算の複雑なパターンを表現できる。

7.24.5. Data Parallel Haskell

GHCにはData Parallel Haskell(DPH)への試験的対応が含まれている。このコードは非常に不安定であり、もっぱら技術の下見のために供給されている。対応するDPHのwikiページにはより多くの情報がある。