3

私はサブセット積を行うコードを書いています: それは要素のリストと (同じ長さの) 標識変数のリストを取ります。積はツリーで計算されます。これは、アプリケーションにとって重要です。各製品は高価であるため、私の目標は、ツリーの各レベルを並行して計算し、連続するレベルを順番に評価することでした。したがって、ネストされた並列処理は行われません。

コード全体のトップレベル近くにある 1 つの関数に repa コードしかありません。subsetProd はモナドではないことに注意してください。

手順:

  1. リストをペアにまとめます (並列処理なし)
  2. チャンクされたリストを圧縮します (並列処理なし)
  3. このリストに製品関数をマップし (Repa マップを使用)、遅延配列を作成します。
  4. computeP を呼び出してマップを並行して評価する
  5. Repa の結果をリストに戻す
  6. 再帰呼び出しを行います (入力の半分のサイズのリストで)

コード：

{-# LANGUAGE TypeOperators, FlexibleContexts, BangPatterns #-}

import System.Random
import System.Environment (getArgs)
import Control.Monad.State
import Control.Monad.Identity (runIdentity)

import Data.Array.Repa as Repa
import Data.Array.Repa.Eval as Eval
import Data.Array.Repa.Repr.Vector

force :: (Shape sh) => Array D sh e -> Array V sh e
force = runIdentity . computeP

chunk :: [a] -> [(a,a)]
chunk [] = []
chunk (x1:x2:xs) = (x1,x2):(chunk xs)

slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1) 

testSubsetProd :: Int -> Int -> IO ()
testSubsetProd size seed = do
    let work = do
            !flags <- replicateM size (state random)
            !values <- replicateM size (state $ randomR (1,10))
            return $ subsetProd values flags
        value = evalState work (mkStdGen seed)
    print value

subsetProd :: [Int] -> [Bool] -> Int
subsetProd [!x] _ = x
subsetProd !vals !flags = 
    let len = (length vals) `div` 2
        !valpairs = Eval.fromList (Z :. len) $ chunk vals :: (Array V (Z :. Int) (Int, Int))
        !flagpairs = Eval.fromList (Z :. len) $ chunk flags :: (Array V (Z :. Int) (Bool, Bool))
        !prods = force $ Repa.zipWith mul valpairs flagpairs
        mul (!v0,!v1) (!f0,!f1)
            | (not f0) && (not f1) = 1
            | (not f0) = v0+1
            | (not f1) = v1+1
            | otherwise = fromInteger $ slow_fib ((v0*v1) `mod` 35)
    in subsetProd (toList prods) (Prelude.map (uncurry (||)) (toList flagpairs))

main :: IO ()
main = do
  args <- getArgs
  let [numleaves, seed] = Prelude.map read args :: [Int]
  testSubsetProd numleaves seed

プログラム全体は、

ghc -Odph -rtsopts -threaded -fno-liberate-case -funfolding-use-threshold1000 -funfolding-keeness-factor1000 -fllvm -optlo-O3

これらの指示に従って、GHC 7.6.2 x64で。

を使用してプログラム（サブセット）を実行しました

$> time ./Test 4096 4 +RTS -sstderr -N4

8秒後：

672,725,819,784 bytes allocated in the heap
 11,312,267,200 bytes copied during GC
   866,787,872 bytes maximum residency (49 sample(s))
   433,225,376 bytes maximum slop
        2360 MB total memory in use (0 MB lost due to fragmentation)

                                Tot time (elapsed)  Avg pause  Max pause


  Gen  0     1284212 colls, 1284212 par   174.17s   53.20s     0.0000s    0.0116s
  Gen  1        49 colls,    48 par   13.76s    4.63s     0.0946s    0.6412s

  Parallel GC work balance: 16.88% (serial 0%, perfect 100%)

  TASKS: 6 (1 bound, 5 peak workers (5 total), using -N4)

  SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time  497.80s  (448.38s elapsed)
  GC      time  187.93s  ( 57.84s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time  685.73s  (506.21s elapsed)

  Alloc rate    1,351,400,138 bytes per MUT second

  Productivity  72.6% of total user, 98.3% of total elapsed

gc_alloc_block_sync: 8670031
whitehole_spin: 0
gen[0].sync: 0
gen[1].sync: 571398

-N パラメータを増やすとコードが遅くなります (-N1 の場合は 7.628 秒、-N2 の場合は 7.891 秒、-N4 の場合は 8.659 秒)。並列性が得られません。また、多数の最適化を行ってコンパイルすると、ランタイムには役立ちますが、並列処理には役立ちません。

Threadscope は、3 つの HEC で重大な作業が行われていないことを確認していますが、ガベージ コレクターは 4 つの HEC をすべて使用しているようです。

上記の -sstderr ブロックのスレッドスコープ

では、なぜ Repa は火花を散らさないのでしょうか? 私のプロダクト ツリーには 64 枚の葉があるので、Repa が内部ノードごとにスパークを作成したとしても、最大63 個のスパークが存在するはずです。並列処理をカプセル化する ST モナドの使用と関係があるように感じますが、これが問題を引き起こす理由はよくわかりません。おそらく、火花は IO モナドでのみ作成できますか?

この場合、各レベルが並行して行われるこのツリー製品をどのように実行できるかについてのアイデアはありますか (ネストされた並列処理が発生することなく、これは私のタスクには不要と思われます)。一般に、ツリー プロダクトを並列化するか、Repa をより有効に活用するためのより良い方法があると思われます。

スパークが作成されていない場合でも、-N パラメーターを増やすとランタイムが増加する理由を説明するためのボーナス ポイント。

編集 上記のコード例を、私の問題のコンパイル例に変更しました。プログラム フローは、実際のコードとほぼ完全に一致しています。いくつかの入力をランダムに選択し、それらに対してサブセット積を実行します。私は今アイデンティティモナドを使っています。私は自分のコードに多くの小さな変更を試みました: インライン化するかどうか、bang パターンかどうか、2 つの Repa リストと Repa zipWith を使用するバリエーションと、リストを順番に圧縮して Repa マップを使用する方法など、どれもまったく役に立ちませんでした。

サンプル コードでこの問題に遭遇したとしても、実際のプログラムははるかに大きくなります。

4

1 に答える 1

6

並列性がないのはなぜですか？

並列処理がない主な理由 (少なくとも現在は単純化されて機能しているプログラム) は、表現computePの配列を使用しておりV、法線ベクトルの要素の型が厳密ではないためです。したがって、実際には実際の作業を並行して行っているわけではありません。最も簡単な修正は、次の定義Uに変更して、ボックス化されていない配列を結果として使用することです。force

force :: (Shape sh, Unbox e) => Array D sh e -> Array U sh e
force a = runIdentity (computeP a)

元のコードで、ボックス化されていない複雑なデータ型を扱っていると主張したことを思い出します。しかし、そうするのは本当に不可能ですか？おそらく、実際に必要なデータをボックス化できない表現に抽出できますか? Unboxまたは、型をクラスのインスタンスにしますか? そうでない場合は、-arrayforceで機能する次のバリアントを使用することもできます。V

import Control.DeepSeq (NFData(..))

...

force :: (Shape sh, NFData e) => Array D sh e -> Array V sh e
force a = runIdentity $ do
  r  <- computeP a
  !b <- computeUnboxedP (Repa.map rnf r)
  return r

ここでの考え方は、最初にV-array 構造を計算し、次に配列をマッピングすることによって、そこから型のU-arrayを計算するというものです。結果の配列は面白くありませんが、-array の各要素はプロセス1で強制されます。()rnfV

これらの変更のいずれかにより、私のマシンでは、問題のサイズが40969 秒から 3 秒に短縮さ-N4れます。

また、すべてのステップでリストと配列を変換するのは奇妙だと思います。subsetProd2 つの配列を取らないのはなぜですか? また、少なくとも値Vについては、ペアに中間配列を使用する必要はないようですD。配列を使用することもできます。しかし、私の実験では、これらの変更はランタイムに大きな有益な効果をもたらしませんでした。

なぜ火花が出ないのですか？

Repa は火花を発生させません。Haskell には、並列処理に対するさまざまなアプローチがあり、スパークは、ランタイム システムで特別にサポートされている特定のメカニズムの 1 つです。ただし、parallelパッケージやパッケージの特定のスケジューラなど、一部のライブラリのみmonad-parが実際にこのメカニズムを利用します。しかし、Repa はそうではありません。forkIO内部ではスレッド、つまりスレッドを使用しますが、外部への純粋なインターフェースを提供します。したがって、火花がないこと自体は心配する必要はありません。

1. 私はもともとそれを行う方法がわからなかったので、Repa の作者である Ben Lippmeier に尋ねました。rnf別の配列を生成するためのマッピングのオプションと、 のUnboxインスタンスがあるという事実を指摘してくれた Ben に感謝し()ます。

于 2013-04-19T06:31:35.360 に答える