haskell - 并行 Repa 代码不会产生 Spark

Question

我正在编写代码来执行子集乘积:它需要一个元素列表和一个指示变量列表(长度相同)。产品是在树中计算的，这对我们的应用程序至关重要。每个产品都很昂贵，所以我的目标是并行计算树的每个级别，按顺序评估连续的级别。因此，不存在任何嵌套并行性。

我只有一个函数中的 repa 代码，靠近我的整体代码的顶层。请注意，subsetProd 不是一元的。

步骤:

1. 将列表分成对(无并行性)
2. 压缩分块列表(无并行性)
3. 将乘积函数映射到此列表上(使用 Repa 映射)，创建一个延迟数组
4. 调用computeP并行评估 map
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

根据these instructions ，在 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 秒)，但我创建了 0 个 Spark ，这似乎是一个主要嫌疑人至于为什么我没有得到任何并行性。此外，使用大量优化进行编译有助于提高运行时速度，但对并行性没有帮助。

Threadscope 确认没有在 3 个 HEC 上进行认真的工作，但垃圾收集器似乎正在使用所有 4 个 HEC。

那么为什么 Repa 没有产生任何 Spark 呢？我的产品树有 64 个叶子，因此即使 Repa 为每个内部节点生成一个 Spark ，也应该有大约 63 个 Spark 。我觉得这可能与我使用封装并行性的 ST monad 有关，尽管我不太确定为什么这会导致问题。也许 Spark 只能在 IO monad 中创建？

如果是这种情况，有谁知道我如何执行这个树产品，其中每个级别都是并行完成的(不会导致嵌套并行性，这对我的任务来说似乎是不必要的)。总的来说，也许有更好的方法来并行化树产品或更好地利用 Repa。

解释为什么运行时间随着我增加 -N 参数而增加的奖励点，即使没有创建 Spark 。

编辑我将上面的代码示例更改为我的问题的编译示例。程序流程几乎完全符合我的真实代码:我随机选择一些输入，然后对它们进行子集乘积。我现在使用identity monad 。我已经尝试对我的代码进行很多小的更改:是否内联、是否有爆炸模式、使用两个 Repa 列表和 Repa zipWith 与按顺序压缩列表并使用 Repa 映射的变化，等等，这些都没有任何帮助。

即使我遇到this我的示例代码中存在问题，我的实际程序要大得多。

Answer 1

为什么没有并行性？

程序没有并行性的主要原因(至少对于您现在的简化和工作而言)是您在 V 表示数组上使用 computeP ，法向量的元素类型并不严格。所以你实际上并没有并行地做任何真正的工作。最简单的修复方法是通过将 force 更改为以下定义，使用未装箱的 U 数组作为结果:

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

我确实记得在您的原始代码中您声称您正在使用未拆箱的复杂数据类型。但真的不可能做到吗？也许您可以将实际需要的数据提取到一些不可装箱的表示形式中？或者使类型成为 Unbox 类的实例？如果没有，您还可以使用以下适用于 V 数组的 force 变体:

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 数组结构，然后计算 () 类型的 U 数组通过将 rnf 映射到数组上来从中得到。生成的数组并不有趣，但是 V 数组的每个元素都将在该过程中被强制¹。

在我的机器上使用 -N4 时，这些更改都可以将 4096 问题的运行时间从约 9 秒缩短到约 3 秒。

此外，我觉得每一步都在列表和数组之间进行转换很奇怪。为什么不让 subsetProd 接受两个数组？另外，至少对于值来说，使用中间的 V 数组似乎没有必要，您也可以使用 D 数组。但在我的实验中，这些更改并没有对运行时产生显着的有益影响。

为什么没有 Spark ？

Repa从不产生 Spark 。 Haskell 有许多不同的并行方法，而 Spark 是一种在运行时系统中得到特殊支持的特殊机制。但是，只有某些库(例如 parallel 包和 monad-par 包的一个特定调度程序)实际上使用了该机制。然而，雷帕却没有。它在内部使用forkIO，即线程，但向外部提供纯接口(interface)。因此，没有 Spark 本身就无需担心。

<小时/>

<子>1. 我本来不知道该怎么做，所以我问了 Repa 的作者 Ben Lippmeier。非常感谢 Ben 指出映射 rnf 来生成不同数组的选项，以及 () 有一个 Unbox 实例>，对我来说。