Evalモナドを使って無限リストの並列評価

http://partake.in/events/9f226986-2812-441d-98b7-1f5cca9be432 にオンライン参加してきたので、Evalモナドを使った並列評価を行なってみた。

コード

ナイーブな素数探索アルゴリズムです。指定された数以上の一定個数の素数を抽出します。

import Control.Parallel.Strategies

-- rseq first n elements in parallel, then next n..
parListWithN :: Int -> [a] -> Eval ()
parListWithN n l = do
    parSeqListPar $ take n l
    case drop n l of
      [] -> return ()
      _  -> parListWithN n $ drop n l

-- rseq in parallel for finite length list
parSeqListPar :: [a] -> Eval ()
parSeqListPar [] = return ()
parSeqListPar (hd:tl) = do
    rpar hd
    parSeqListPar tl
    rseq hd
    return ()

-- filter f l with parallel precalcuration for l
filterEval :: (a -> Bool) -> [a] -> [a]
filterEval f l = runEval $ do
    rpar $ runEval $ parListWithN 100 l
    return $ filter f l

-- prime testing
isPrime :: Integral b => b -> Bool
isPrime n = not $ or $ map ((==0).(n `mod`)) [2..(n-1)]

-- find 100 successive primes after 435300
main = print $ take 100 $ filterEvalN isPrime [435300..]

このコードの挙動のポイントはいくつかあります。

• filterEval関数：並列処理のトリガーを引くコードを処理キューに積んで、全体評価を始めます。
• parListWithN関数：最初のn個の処理を並列処理にかけ、完了したら次のn個、というようにEvalモナドの挙動を指示する関数です。

並列処理がしたければ、rparを使ってタスクを積んでいくだけの簡単なお仕事です。

でも、次のような問題点があります。

• 全体評価の関数と並列処理が完全に分離していて、コントロールされていない。スケジューリング状況によっては、並列処理だけが進行して、全体評価側にフィードバックされずに進む可能性がある。

Evalモナドはこの辺りのコントロールが難しい感触があります。この後の並列計算ではこの辺りが解消されるか、気になるところです。

実行方法

使用時はthreadedオプションを付けてコンパイルします。

ghc -threaded FindPrime.hs

実行時は並列コアを指定します。

./FinePrime +RTS -N -RTS

threadscopeの実行結果とか見たかったけど、メモってる時点で時間切れなのでまた手が開けばやります。。。