PR

データ構造に対する並列処理関数を利用する

 qsortPar関数では,並列化処理および並列化の粒度を決める処理を,再帰を使って直接組み込んでいました。しかし,並列化処理や並列化の粒度を決める処理を行う「並列化のための関数」があらかじめ用意されていることもあります。そうした関数の例として,並列Haskellを利用してデータ構造の要素を並列に評価する関数を見ていきましょう。こうした関数は,第11回で紹介したように,parallelパッケージのControl.Parallel.Strategiesモジュールで用意されています。

Prelude Control.Parallel.Strategies> :i parList
parList :: Strategy a -> Strategy [a]
        -- Defined in Control.Parallel.Strategies
Prelude Control.Parallel.Strategies> :i parListChunk
parListChunk :: Int -> Strategy a -> Strategy [a]
        -- Defined in Control.Parallel.Strategies

 parList関数は,リストの各要素を並列に評価するための関数です。parListChunk関数は,リストをN個の要素を持つ固まりに分け,それぞれを並列評価するための関数です。ほかに,N番目の要素を並列評価するparListNth関数,2分割したリストをそれぞれ並列評価するparListSplitAt関数などもあります。

-- | @'evaListSplitAt' n stratPref stratSuff@ evaluates the prefix
-- (of length @n@) of a list according to @stratPref@ and its the suffix
-- according to @stratSuff@.
evalListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a]
evalListSplitAt n stratPref stratSuff xs
  = let (ys,zs) = splitAt n xs in
    stratPref ys >>= \ys' ->
    stratSuff zs >>= \zs' ->
    return (ys' ++ zs')

-- | Like 'evalListSplitAt' but evaluates both sublists in parallel.
parListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a]
parListSplitAt n stratPref stratSuff = evalListSplitAt n (rpar `dot` stratPref) (rpar `dot` stratSuff)

~ 略 ~

-- | Evaluate the nth element of a list (if there is such) according to
-- the given strategy.
-- The spine of the list up to the nth element is evaluated as a side effect.
evalListNth :: Int -> Strategy a -> Strategy [a]
evalListNth n strat = evalListSplitAt n r0 (evalListN 1 strat)

-- | Like 'evalListN' but evaluates the nth element in parallel.
parListNth :: Int -> Strategy a -> Strategy [a]
parListNth n strat = evalListNth n (rpar `dot` strat)

 これらの関数の定義で使われているrparは,parList*関数などと同様に,値を評価するための戦略(方法)を定義する関数です。rparではpar関数を使い,「値の評価を並列化する」という単純な評価戦略を定義しています。

-- | 'rpar' sparks its argument (for evaluation in parallel).
rpar :: Strategy a
rpar x = x `par` return x

 dotは,二つのStrategy型の評価戦略を合成して新たな評価戦略を作成する関数です。

-- | Compose two strategies sequentially. 
-- This is the analogue to function composition on strategies.
--
-- > strat2 `dot` strat1 == strat2 . withStrategy strat1
--
dot :: Strategy a -> Strategy a -> Strategy a
strat2 `dot` strat1 = strat2 . runEval . strat1

 今回の本題から外れるので,これらの関数の詳細には立ち入りません。これらの関数を使うことで,「データ構造に対する評価戦略を定義したeval*という名前の関数」から「並列評価を行うための戦略を定義したpar*という名前の関数」を組み立てられることを理解できれば,今回は十分です。

 ここまで見てきた並列評価関数は,いずれもリストの要素に対する正格評価を伴うものです。例えばparList関数は,リストの各要素を先行評価していくように実装されています。しかし,正格評価を伴う評価戦略は場合によっては有害です。第47回で説明したように,正格評価することでプログラムの効率が悪くなったり,プログラムの挙動が変わってしまうことがあるからです。そこでControl.Parallel.Strategiesモジュールでは,リストの必要な個所だけを並列に正格評価し,残りを遅延評価されるよう残しておくparBufferWHNFという関数が用意されています。

-- Like evalBufferWHNF but sparks the list elements when pushing them
-- into the buffer.
-- Not to be exported; used in parBuffer and for optimisation.
parBufferWHNF :: Int -> Strategy [a]
parBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0))
  where -- ret :: [a] -> [a] -> [a]
           ret (x:xs) (y:ys) = y `par` (x : ret xs ys)
           ret xs     _      = xs

        -- start :: Int -> [a] -> [a]
           start 0   ys     = ys
           start !_n []     = []
           start !n  (y:ys) = y `par` start (n-1) ys


-- | Like 'evalBuffer' but evaluates the list elements in parallel when
-- pushing them into the buffer.
parBuffer :: Int -> Strategy a -> Strategy [a]
parBuffer n strat = parBufferWHNF n . map (withStrategy strat)
-- Alternative definition via evalBuffer (may compromise firing of RULES):
-- parBuffer n strat = evalBuffer n (rpar `dot` strat)

-- Deforest the intermediate list in parBuffer/evalBuffer when it is
-- unnecessary:

{-# RULES 
"evalBuffer/rseq"  forall n . evalBuffer  n rseq = evalBufferWHNF n
"parBuffer/rseq"   forall n . parBuffer   n rseq = parBufferWHNF  n
 #-}

 parBufferWHNF関数では,リストの最初のN個だけを並列評価し,残りを遅延評価するリストとして残します。無駄な評価を極力防ぐため,parBuffer関数はeval*関数を使わずに直接定義されています。

 リスト以外のデータ構造に対して並列評価を行う関数も用意されています。例えば,parTuple*関数を利用することで,タプルの要素を並列評価できます。

parTuple2 :: Strategy a -> Strategy b -> Strategy (a,b)
parTuple2 strat1 strat2 =
  evalTuple2 (rpar `dot` strat1) (rpar `dot` strat2)

parTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
parTuple3 strat1 strat2 strat3 =
  evalTuple3 (rpar `dot` strat1) (rpar `dot` strat2) (rpar `dot` strat3)

~ 以下略 ~

 データ構造や型に関係なく各要素を並列評価したい場合には,parTraversable関数を利用します。

-- | Like 'evalTraversable' but evaluates all elements in parallel.
parTraversable :: Traversable t => Strategy a -> Strategy (t a)
parTraversable strat = evalTraversable (rpar `dot` strat)

{-# SPECIALISE evalTraversable :: Strategy a -> Strategy (Maybe a) #-}
{-# SPECIALISE parTraversable :: Strategy a -> Strategy (Maybe a) #-}
{-# SPECIALISE evalTraversable :: Strategy a -> Strategy [a] #-}
{-# SPECIALISE parTraversable :: Strategy a -> Strategy [a] #-}

 parTraversableの型宣言にあるように,parTraversable関数はTraversableクラスのインスタンスである型が持つ要素を並列評価します。Traversableクラスのインスタンスが定義されている型にはリストやMaybe型などがあります。

 並列評価のための戦略を提供しているのはparallelパッケージだけではありません。例えば,vector-strategiesパッケージData.Vector.Strategiesモジュールは,Vectorに対する処理を並列評価するためのparVectorという関数を提供しています(参考リンク)。

-- |Evaluate the elements of a boxed vector in parallel.
--
-- The vector will be divided up into chunks of length less than or
-- equal to the provided chunk size (first argument) and each chunk
-- of elements will be sparked off for evaluation.
-- 
-- Use this along with the "parallel" package's 'using' function:
--
-- @
--    vec \``using`\` (`parVector` chunkSize)
-- @
--
-- 'parVector' can not provide any benefits (read: no parallelism) for unboxed vectors!
parVector :: NFData a => Int -> Strategy (V.Vector a)
parVector n = liftM V.fromList . parListChunk n rdeepseq . V.toList

instance NFData a => NFData (V.Vector a) where
  rnf = rnf . V.toList

 parVectorは,Vecorをいったんリストに変換してからparListChunk関数を使用することで,N個の要素を持つ固まりに分けてそれぞれを並列評価するように実装されています。既存の「リストに対する並列評価関数」を利用することで,こうした戦略を実現できるのです。リストを作成してから並列処理を行い,元のデータ構造に再度戻すため,その分のコストは必要です。ただ,そのコストが十分に低ければ,こうした戦略も検討してみる価値はあります。

 今のところ,vector-strategiesにはparVector以外の関数はまだ用意されていません。また,非ボックス化Vectorに対する適切な並列評価戦略もまだありません(参考リンク)。将来はこうしたものも提供されるようになるでしょう。

 ここでは並列Haskellを使った例を取り上げましたが,「データ構造に対して定義されている既存の並列処理関数を利用する」という考え方自体は,他の並列処理機能や並列処理ライブラリにも応用できます。ある処理を並列化したい場合には,データ構造に対して並列処理を行う関数などがライブラリとして提供されているかどうか調べるようにしましょう。