13

この一見些細な並列クイックソートの実装を取得しました。コードは次のとおりです。

import System.Random
import Control.Parallel
import Data.List

quicksort :: Ord a => [a] -> [a]
quicksort xs = pQuicksort 16 xs -- 16 is the number of sparks used to sort

-- pQuicksort, parallelQuicksort  
-- As long as n > 0 evaluates the lower and upper part of the list in parallel,
-- when we have recursed deep enough, n==0, this turns into a serial quicksort.
pQuicksort :: Ord a => Int -> [a] -> [a]
pQuicksort _ [] = []
pQuicksort 0 (x:xs) =
  let (lower, upper) = partition (< x) xs
  in pQuicksort 0 lower ++ [x] ++ pQuicksort 0 upper
pQuicksort n (x:xs) =
  let (lower, upper) = partition (< x) xs
      l = pQuicksort (n `div` 2) lower
      u = [x] ++ pQuicksort (n `div` 2) upper
  in (par u l) ++ u

main :: IO ()
main = do
  gen <- getStdGen
  let randints = (take 5000000) $ randoms gen :: [Int]
  putStrLn . show . sum $ (quicksort randints)

私はコンパイルします

ghc --make -threaded -O2 quicksort.hs

そして一緒に走る

./quicksort +RTS -N16 -RTS

私が何をしても、これを 1 つの CPU で実行する単純な順次実装よりも高速に実行することはできません。

  1. 1 つよりも複数の CPU でこれが非常に遅くなる理由を説明することは可能ですか?
  2. 何らかのトリックを行うことで、CPU の数に応じて、少なくともサブリニアにこのスケーリングを行うことは可能ですか?

EDIT：@tempestadeptは、クイックソート自体が問題であることをほのめかしました。これを確認するために、上記の例と同じ精神で単純なマージソートを実装しました。動作は同じですが、追加する機能が増えるほどパフォーマンスが低下します。

import System.Random
import Control.Parallel

splitList :: [a] -> ([a], [a])
splitList = helper True [] []
  where helper _ left right [] = (left, right)
        helper True  left right (x:xs) = helper False (x:left) right xs
        helper False left right (x:xs) = helper True  left (x:right) xs

merge :: (Ord a) => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = case x<y of
  True  -> x : merge xs (y:ys)
  False -> y : merge (x:xs) ys

mergeSort :: (Ord a) => [a] -> [a]
mergeSort xs = pMergeSort 16 xs -- we use 16 sparks

-- pMergeSort, parallel merge sort. Takes an extra argument
-- telling how many sparks to create. In our simple test it is
-- set to 16
pMergeSort :: (Ord a) => Int -> [a] -> [a]
pMergeSort _ [] = []
pMergeSort _ [a] = [a]
pMergeSort 0 xs =
  let (left, right) = splitList xs
  in  merge (pMergeSort 0 left) (pMergeSort 0 right)
pMergeSort n xs =
  let (left, right) = splitList xs
      l = pMergeSort (n `div` 2) left
      r = pMergeSort (n `div` 2) right
  in  (r `par` l) `pseq` (merge l r)

ris :: Int -> IO [Int]
ris n = do
  gen <- getStdGen
  return . (take n) $ randoms gen

main = do
  r <- ris 100000
  putStrLn . show . sum $ mergeSort r
4

5 に答える 5

4

慣用的なクイックソートでどれだけうまく機能するかはわかりませんが、Sparking Imperativesの Roman で示されているように、真の命令型クイックソートでは (やや弱い範囲で) 機能します。

しかし、彼は良いスピードアップを得たことはありませんでした。これには、適切に最適化するために、spark キューのようにオーバーフローしない実際の作業を盗む両端キューが本当に必要です。

于 2013-11-04T05:05:52.837 に答える
3

疑似クイックソートにはリスト連結が含まれているため、目立った改善は得られません。これは並列化できず、二次時間 (すべての連結の合計時間) が必要です。O(n log n)リンクされたリストにあるマージソートを試してみることをお勧めします。

また、多数のスレッドでプログラムを実行するには、 でコンパイルする必要があります-rtsopts。

于 2013-11-04T06:41:08.317 に答える
3

parは、最初の引数のみを弱頭正規形に評価します。つまり、最初の引数の型が の場合Maybe Int、par結果がNothingorかどうかをチェックJust somethingして停止します。まったく評価されませんsomething。同様に、リストの場合、リストが[]またはであるかどうかを確認するのに十分なだけ評価されますsomething:something_else。リスト全体を並行して評価するには、リストを に直接渡すのではなく、リスト全体parに渡すときに必要になるように、リストに依存する式を作成しparます。例えば：

evalList :: [a] -> ()
evalList [] = ()
evalList (a:r) = a `pseq` evalList r

pMergeSort :: (Ord a) => Int -> [a] -> [a]
pMergeSort _ [] = []
pMergeSort _ [a] = [a]
pMergeSort 0 xs =
  let (left, right) = splitList xs
  in  merge (pMergeSort 0 left) (pMergeSort 0 right)
pMergeSort n xs =
  let (left, right) = splitList xs
      l = pMergeSort (n `div` 2) left
      r = pMergeSort (n `div` 2) right
  in  (evalList r `par` l) `pseq` (merge l r)

別の注意: Haskell で新しいスレッドを起動するためのオーバーヘッドは非常に低いため、for のケースpMergeSort 0 ...はおそらく役に立ちません。

于 2015-07-08T03:42:39.860 に答える