使用Repa并行数组的惯用选项定价和风险

Question

假设我想使用有限差分法对一个看涨期权定价,然后修复以下工作:

import Data.Array.Repa as Repa

r, sigma, k, t, xMax, deltaX, deltaT :: Double
m, n, p :: Int
r = 0.05
sigma = 0.2
k = 50.0
t = 3.0
m = 3
p = 1
xMax = 150
deltaX = xMax / (fromIntegral m)
n = 800
deltaT = t / (fromIntegral n)

singleUpdater a = traverse a id f
  where
    Z :. m = extent a
    f _get (Z :. ix) | ix == 0   = 0.0
    f _get (Z :. ix) | ix == m-1 = xMax - k
    f  get (Z :. ix)             = a * get (Z :. ix-1) +
                                   b * get (Z :. ix) +
                                   c * get (Z :. ix+1)
      where
        a = deltaT * (sigma^2 * (fromIntegral ix)^2 - r * (fromIntegral ix)) / 2
        b = 1 - deltaT * (r  + sigma^2 * (fromIntegral ix)^2)
        c = deltaT * (sigma^2 * (fromIntegral ix)^2 + r * (fromIntegral ix)) / 2

priceAtT :: Array U DIM1 Double
priceAtT = fromListUnboxed (Z :. m+1) [max 0 (deltaX * (fromIntegral j) - k) | j <- [0..m]]

testSingle :: IO (Array U DIM1 Double)
testSingle = computeP $ singleUpdater priceAtT 

但是现在假设我想要并行定价(比如做一个现场阶梯)然后我可以这样做:

multiUpdater a = fromFunction (extent a) f
     where
       f :: DIM2 -> Double
       f (Z :. ix :. jx) = (singleUpdater x)!(Z :. ix)
         where
           x :: Array D DIM1 Double
           x = slice a (Any :. jx)

priceAtTMulti :: Array U DIM2 Double
priceAtTMulti = fromListUnboxed (Z :. m+1 :. p+1)
                [max 0 (deltaX * (fromIntegral j) - k) | j <- [0..m], _l <- [0..p]]

testMulti :: IO (Array U DIM2 Double)
testMulti = computeP $ multiUpdater priceAtTMulti

问题:

1. 在修复中是否有更惯用的方法？
2. 上述方法实际上会并行定价吗？
3. 如何确定我的代码是否真的生成了将要并行执行的内容？

我试过这个3但遗憾地遇到了ghc中的一个错误:

bash-3.2$ ghc -fext-core --make Test.hs
[1 of 1] Compiling Main             ( Test.hs, Test.o )
ghc: panic! (the 'impossible' happened)
 (GHC version 7.4.1 for x86_64-apple-darwin):
    MkExternalCore died: make_lit

Answer 1

您的错误与您的代码无关 - 您可以使用它-fext-core以外部核心格式打印编译输出.只是不要这样做(看到核心,我使用ghc-core).

用-O2和编译-threaded:

$ ghc -O2 -rtsopts --make A.hs -threaded 
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

然后运行+RTS -N4,例如,使用4个线程:

$ time ./A +RTS -N4
[0.0,0.0,8.4375e-3,8.4375e-3,50.009375,50.009375,100.0,100.0]
./A  0.00s user 0.00s system 85% cpu 0.008 total

因此,查看结果的速度太快了.我会增加你m和p参数1K与3K

$ time ./A +RTS -N2
./A +RTS -N2  3.03s user 1.33s system 159% cpu 2.735 total

所以是的,它确实并行运行.首次尝试时,在2核机器上运行1.6倍.它是否有效是另一个问题.使用+ RTS -s可以看到运行时统计信息:

任务:4个(1个绑定,3个峰值工人(共3个),使用-N2)

所以我们有3个并行运行的线程(2个可能用于算法,一个用于IO管理器).

您可以通过调整GC设置来缩短运行时间.例如,通过使用-A我们可以减少GC开销,并产生真正的并行加速.

$ time ./A +RTS -N1 -A100M   
./A +RTS -N1 -A100M  1.99s user 0.29s system 99% cpu 2.287 total

$ time ./A +RTS -N2 -A100M   
./A +RTS -N2 -A100M  2.30s user 0.86s system 147% cpu 2.145 total

您有时可以使用LLVM后端来提高数值性能.这似乎也是这种情况:

$ ghc -O2 -rtsopts --make A.hs -threaded -fforce-recomp -fllvm
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A +RTS -N2 -A100M                                    
./A +RTS -N2 -A100M  2.09s user 0.95s system 147% cpu 2.065 total

没什么了不起的,但是你正在改进单线程版本的运行时间,而且我没有以任何方式修改你的原始代码.要真正改进,您需要进行分析和优化.

重新访问-A标志,我们可以使用初始线程分配区域上的更大的限制来进一步缩短时间.

$ ghc -Odph -rtsopts --make A.hs -threaded -fforce-recomp -fllvm

$ time ./A +RTS -N2 -A60M -s
./A +RTS -N2 -A60M 1.99s user 0.73s system 144% cpu 1.880 total

因此,通过使用并行运行时,LLVM后端,并小心使用GC标志,将其从2.7(降低30%)降低到1.8s.您可以查看GC标志表面以找到最佳值:

由于低谷-A64 -N2是理想的数据集大小.

我还强烈考虑在内核中使用手动公共子表达式消除,以避免过度重新计算事物.

正如Alp建议的那样,要查看程序的运行时行为,请编译threadscope(来自Hackage)并运行如下:

$ ghc -O2 -fllvm -rtsopts -threaded -eventlog --make A.hs

$ ./A +RTS -ls -N2 -A60M

并且您获得了两个内核的事件跟踪,如下所示:

那么这里发生了什么？您有一个初始周期(0.8秒)的设置时间 - 分配您的大列表并将其编码到一个复制数组中 - 正如您可以通过GC和执行的单线程交错看到的那样.然后在你的实际并行工作发生在最后300ms之前,单核上还有0.8s的东西.

因此,虽然您的实际算法可能很好地并行化,但所有周围的测试设置基本上都会淹没结果.如果我们序列化您的数据集,然后只是从磁盘加载它,我们可以获得更好的行为:

$ time ./A +RTS -N2 -A60M
./A +RTS -N2 -A60M  1.76s user 0.25s system 186% cpu 1.073 total

现在你的个人资料看起来更健康了:

这看起来很棒!非常少的GC(98.9%的生产率),我的两个核心并行运行.

所以,最后,我们可以看到你获得良好的并行性:

1核,1.855s

$ time ./A +RTS -N1 -A25M
./A +RTS -N1 -A25M  1.75s user 0.11s system 100% cpu 1.855 total

并有2个核心,1.014s

$ time ./A +RTS -N2 -A25M   
./A +RTS -N2 -A25M  1.78s user 0.13s system 188% cpu 1.014 total

现在,具体回答你的问题:

1. 在修复中是否有更惯用的方法？

通常,修复代码应包含并行的traveral,使用者和产品,以及无限的内核函数.所以只要你这样做,那么代码可能是惯用的.如有疑问,请查看教程.我通常会将您的工作内核(如f)标记为内联.

1. 上述方法实际上会并行定价吗？

如果您使用并行组合器computeP或各种映射和折叠,代码将并行执行.所以是的,它应该并且确实并行运行.

1. 如何确定我的代码是否真的生成了将要并行执行的内容？

通常,您将了解先验因为您使用并行操作.如果有疑问,请运行代码并观察加速.然后,您可能需要优化代码.