PR

やみくもな並列化を避ける

 では,betterQuicksort関数を並列Haskellを使って並列化してみましょう。単純に並列化を行うと,以下のような定義になります。

module QSortPar where
import Control.DeepSeq (NFData(..))
import Control.Parallel (par, pseq)
import Control.Parallel.Strategies

qsortPar :: (Ord a, NFData a) => [a] -> [a]
qsortPar = qsortParWithPivot selectMiddle

qsortParWithPivot :: (Ord a, NFData a) => ([a] -> a) -> [a] -> [a]
qsortParWithPivot _ []  = []
qsortParWithPivot _ [x] = [x]
qsortParWithPivot f xs  = losort ++ hisort `using` strategy
     where
         x      = f xs
         losort = qsortParWithPivot f [y | y <- xs, y < x]
         hisort = qsortParWithPivot f [y | y <- xs, y >= x]
         strategy result = rdeepseq losort `par`
                           rdeepseq hisort `pseq`
                           rdeepseq result

 この定義には,処理の並列化を試みる回数が多過ぎるという問題点があります。qsortPar関数のすべての再帰呼び出しで,par関数を使った処理の並列化を試みています。このため,「1要素または0要素を持つリストに対するqsortPar関数の適用」といった処理までpar関数を使った並列化の対象になってしまっています。

 このように小さい処理まで並列化の対象にするのは望ましくありません。小さい処理では,処理を行うのに必要なコストが小さい分,処理の並列化を行うために必要な負荷の割合が大きくなります。その結果,並列化しても性能が上がらなかったり,むしろ性能が悪化したりすることもあります。プログラムを並列化する場合には,並列化の対象になる処理の粒度を調整する必要があります。

 以下のように,処理を並列化すべきかどうかを判断するコードをqsortPar関数内に追加することで,並列化の対象になる処理の粒度を調整できます。

{-# LANGUAGE BangPatterns #-}
module QSortPar where
import Control.DeepSeq (NFData(..))
import Control.Parallel (par, pseq)
import Control.Parallel.Strategies

sampleDepth :: Int
sampleDepth = 8

qsortPar :: (Ord a, NFData a) => Int -> [a] -> [a]
qsortPar = qsortParWithPivot' selectMiddle 0

qsortParWithPivot' :: (Ord a, NFData a) => ([a] -> a) -> Int -> Int -> [a] -> [a]
qsortParWithPivot' _ _ _ []  = []
qsortParWithPivot' _ _ _ [x] = [x]
qsortParWithPivot' f !currentDepth !limit xs
    | currentDepth >= limit = quickSortWithPivot f xs
    | otherwise             = losort ++ hisort `using` strategy
  where
      x      = f xs
      losort = qsortParWithPivot' f (currentDepth+1) limit [y | y <- xs, y < x]
      hisort = qsortParWithPivot' f (currentDepth+1) limit [y | y <- xs, y >= x]
      strategy result = rdeepseq losort `par`
                        rdeepseq hisort `pseq`
                        rdeepseq result

 この新しい定義では,再帰の深さの閾値を第1引数で指定し,処理の並列化の基準に利用しています。再帰の深さが閾値を超えない間は,qsortPar関数を再帰的に呼び出して処理の並列化を行います。再帰の深さが閾値以上になった場合には,前に定義したquickSortWithPivot関数を使って逐次的に処理を行います。

 ここでは並列化の判断基準として再帰の深さを使っていますが,実際には再帰の深さだけで処理の規模を正確に知ることはできません。データ構造の大きさも目安にはなりますが,実際の処理の規模はデータ構造に格納されるデータ型などにも依存します。並列化の効果を最大限に生かしたければ,criterionやprogressionなどで性能を測定し,適切な処理や閾値を決める必要があります。