EvalモナドとParモナドのトレードオフ

 並列処理の流れを記述する仕組みとしては,Parモナドの方がEvalモナドよりも優れています。一方,Parモナドの方が劣っている部分もあります。

 Parモナドでは,プログラムを並列化するために,並列処理の流れをプログラムに直接組み込む必要があります。Evalモナドを使って記述したStrategy型の値のように,「プログラムで行う処理と,並列処理の流れを分けて記述しておいて,後からプログラムに並列処理を組み込む」ということはできません。

 プログラムの並列化を容易にする手段は,Evalモナドのように作成した並列処理をプログラムに後から組み込むことだけではありません。プログラムの記述がmapやfoldなどの高階関数を利用して抽象化されていれば,その高階関数をParモナドを使って定義した並列版の関数に置き換えることもできます。例えばControl.Monad.Parモジュールでは,map関数の並列版にあたるparMap関数や,並列処理のタスクとして一度処理を分配してその結果を集約するparMapReduceRangeThresh関数などが提供されています(参考リンク)。

-- Parallel maps over Traversable data structures

-- | Applies the given function to each element of a data structure
-- in parallel (fully evaluating the results), and returns a new data
-- structure containing the results.
--
-- > parMap f xs = mapM (pval . f) xs >>= mapM get
--
-- @parMap@ is commonly used for lists, where it has this specialised type:
--
-- > parMap :: NFData b => (a -> b) -> [a] -> Par [b]
--
parMap :: (Traversable t, NFData b) => (a -> b) -> t a -> Par (t b)
parMap f xs = mapM (pval . f) xs >>= mapM get

-- | Like 'parMap', but the function is a @Par@ monad operation.
--
-- > parMapM f xs = mapM (spawn . f) xs >>= mapM get
--
parMapM :: (Traversable t, NFData b) => (a -> Par b) -> t a -> Par (t b)
parMapM f xs = mapM (spawn . f) xs >>= mapM get

{-# SPECIALISE parMap  :: (NFData b) => (a -> b)     -> [a] -> Par [b] #-}
{-# SPECIALISE parMapM :: (NFData b) => (a -> Par b) -> [a] -> Par [b] #-}


-- TODO: Perhaps should introduce a class for the "splittable range" concept.
data InclusiveRange = InclusiveRange Int Int

-- | Computes a binary map\/reduce over a finite range.  The range is
-- recursively split into two, the result for each half is computed in
-- parallel, and then the two results are combined.  When the range
-- reaches the threshold size, the remaining elements of the range are
-- computed sequentially.
--
-- For example, the following is a parallel implementation of
--
-- >  foldl (+) 0 (map (^2) [1..10^6])
--
-- > parMapReduceRangeThresh 100 (InclusiveRange 1 (10^6))
-- >        (\x -> return (x^2))
-- >        (\x y -> return (x+y))
-- >        0
--
parMapReduceRangeThresh
   :: NFData a
      => Int                            -- ^ threshold
      -> InclusiveRange                 -- ^ range over which to calculate
      -> (Int -> Par a)                 -- ^ compute one result
      -> (a -> a -> Par a)              -- ^ combine two results (associative)
      -> a                              -- ^ initial result
      -> Par a

parMapReduceRangeThresh threshold (InclusiveRange min max) fn binop init
 = loop min max
 where
  loop min max
    | max - min <= threshold =
        let mapred a b = do x <- fn b;
                            result <- a `binop` x
                            return result
        in foldM mapred init [min..max]

    | otherwise  = do
        let mid = min + ((max - min) `quot` 2)
        rght <- spawn $ loop (mid+1) max
        l  <- loop  min    mid
        r  <- get rght
        l `binop` r

 parMapReduceRangeThresh関数では,並列処理を行うために指定した数のプロセスを作成し,InclusiveRange型で与えられた最小値から最大値までの範囲で並列に処理を行います。

 こうした高階関数を使えば,ある程度簡単にプログラムを並列化できます。しかし,並列処理の流れを高階関数に直接組み込んでしまうと,第48回で説明したような,並列処理の効率化に必要な「不要な同期の除去」を簡単に行えなくなってしまいます。

 第48回でのDPHライブラリの例のように,融合変換を使って同期を除去するようにすれば,このような問題をある程度緩和できます。ですが,現在のmonad-parでは融合変換のための仕組みは特に提供されておらず,融合変換を行うには自分で定義しなければなりません。このように,Parモナドで定義した高階関数を使った並列化では,Evalモナドを使って並列処理をプログラムに後から組み込む場合に比べ,不要な同期を除去するのが面倒になります。

 また,Parモナドには,Evalモナドとは異なり処理系による補助がありません。Evalモナドのrpar関数で作られる並列処理のタスクは,par関数で作られるsparkと同じものです。したがって,ランタイム・システムで実行時に行われる処理の最適化の対象になります。また,第49回で説明したGHCの測定機能や並列プロファイラなどを使って,並列処理のタスクの振る舞いに関する情報を得ることもできます。一方,Parモナドはsparkを使わずに純粋にライブラリとして実装されているため,今のところはそうした機能の恩恵を受けることはできません。

 Parモナドにも欠点があるため,Evalモナドを完全に置き換えられるわけではありません。それぞれに適したプログラムがあります。他の効率化手法や並列化機能と同様に,トレードオフを考えて使い分ける必要があります。

 ParモナドとEvalモナドは別の形で実装されているため,必要であれば,ParモナドとEvalモナドを組み合わせて利用することも可能です。Evalモナドで作成される並列処理タスクであるsparkは,HECで行う処理に空きがあるときだけ実行されます。このため,Parモナドで作成された並列処理タスクがある間はParモナドでの処理が優先され,Evalモナドで作成した並列処理のタスクがParモナドの実行を妨げることはありません。EvalモナドよりもParモナドの並列処理タスクが優先されるという原則さえ覚えておけば,両者を安全に組み合わせて利用できます。