Haskellにおける並列実行

Haskell Parallel

Haskellはデフォルトではシングルスレッドで走ります。 並列で動かしたい場合は、プログラムを-threaded付きでコンパイルし、RTSの-Nオプションを付けて実行します。 -Nオプションで指定された数だけ、OSのスレッドが立ち上がり実行されます。

$ ghc -O2 par.hs -threaded
$ ./par +RTS -N2

もちろんこれだけでは、並列に動きません。 並列に実行できるようにプログラムを書く必要があります。

遅延評価

Haskellでは、必要となるまで式の評価が遅延されます。 普段は気にする必要はありませんが、並列実行ではどのように評価されるのか意識する必要があります。 GHCiを使って確認していきます。

Prelude> let x = 1 + 2 :: Int
Prelude> let y = x + 1
Prelude> :sprint x
x = _
Prelude> :sprint y
y = _

_は式が未評価であることを示しています。 Haskellではこの未評価部分をthunkと呼びます。

xとyは評価されていません。 yの値はxに依存しており、yの値を求めるとxの式も評価されます。

Prelude> seq y ()
()
Prelude> :sprint x
x = 3
Prelude> :sprint y
y = 4

WHNF

関数を評価しても完全に値まで評価されるわけではありません。 Haskellは、部分式をなるべく評価せずに済ませます。 seq関数は、一番最初のコンストラクタまで評価し、それ以上は評価を行いません。 これは専門用語で弱頭部正規形(Weak Head Normal Form; WHNF)まで評価すると言います。

Prelude> let xs = map (+1) [1..10] :: [Int]
Prelude> :sprint xs
xs = _
Prelude> seq xs ()
()
Prelude> :sprint xs
xs = _ : _
Prelude> length xs
10
Prelude> :sprint xs
xs = [_,_,_,_,_,_,_,_,_,_]
Prelude> sum xs
65
Prelude> :sprint xs
xs = [2,3,4,5,6,7,8,9,10,11]

完全に評価された式をNormal Formと言います。 Control.DeepSeqを使用することでNormal Formまで評価できます。

Prelude> import Control.DeepSeq
Prelude Control.DeepSeq> let xs = map (+1) [1..10] :: [Int]
Prelude Control.DeepSeq> :sprint xs
xs = _
Prelude Control.DeepSeq> deepseq xs ()
()
Prelude Control.DeepSeq> :sprint xs
xs = [2,3,4,5,6,7,8,9,10,11]

並列処理を実装する際には、Haskellの評価方法に注意を払う必要があります。 並列に動くように処理を分割したとしても値が必要になるまで評価されません。

Eval Monad

Control.Parallel.Strategies モジュールにある、rparおよびrseqを用いて並列処理を記述したいと思います。

data Eval a
instance Monad Eval

runEval :: Eval a -> a

rpar :: a -> Eval a
rseq :: a -> Eval a

rparは、引数が並列処理が可能であることを示します。 rseqは、引数を評価し、結果を待つように示します。

rparも、rseqも評価が行われるのはWHNFまでです。

Eval monadは、評価を実行し、結果を返すrunEval操作を提供しています。

実際に利用方法として2つのパターンを紹介します。

rpar/rpar

単純に並列で動かしたい時に利用します。 即座にreturnされます。

runEval $ do
   a <- rpar (f x)
   b <- rpar (f y)
   return (a,b)
rpar/rseq/rseq

f xおよびf yの結果を待ってからreturnします。 他の処理が結果を必要な時利用します。

runEval $ do
    a <- rpar (f x)
    b <- rseq (f y)
    rseq a
    return (a,b)

Sudoku

数独の例題を実行してみたいと思います。 ソースコードはこちらにあります。 simonmar/parconc-examples

sudoku3.hsを利用します。

import Sudoku
import Control.Exception
import System.Environment
import Control.Parallel.Strategies hiding (parMap)
import Data.Maybe

-- <<main
main :: IO ()
main = do
  [f] <- getArgs
  file <- readFile f

  let puzzles   = lines file
      solutions = runEval (parMap solve puzzles)

  print (length (filter isJust solutions))
-- >>

-- <<parMap
parMap :: (a -> b) -> [a] -> Eval [b]
parMap f [] = return []
parMap f (a:as) = do
   b <- rpar (f a)
   bs <- parMap f as
   return (b:bs)
-- >>

受け取ったファイルを、parMapで並列に実行します。

$ghc -O2 sudoku3.hs -rtsopts -threaded
$ ./sudoku3 sudoku17.1000.txt +RTS -N8 -s

プログラムを-rtsopts付きでコンパイルし、RTSの-sオプションを付けて実行することで統計情報を見ることができます。

実際に実行結果を測定してみます。 Fedora 16, Intel Xeon X5650 * 2で実行しました。

スレッド数 実行時間
-N1 2.11s
-N2 1.16s
-N4 0.60s
-N8 0.36s

2スレッドで1.81倍、4スレッドで3.51倍、8スレッドで5.86倍程度の速度向上が見られます。 大体95%程度の並列化率でしょうか。

rparを利用するだけで、ある程度の並列化率が出ていることが分かります。

今回紹介した、Eval monad以外にも、Haskellの並列化手法にはいくつかあります。 今後紹介していきたいと思います。

参考文献

Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming

Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming