Идиоматическая цена опциона и риск с использованием параллельных массивов Repa

Предположим, что я хочу оценить опцион колл с использованием метода конечных разностей и repa, то выполняется следующее задание:

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

Вопросы:

  • Есть ли более идиоматический способ сделать это в repa?
  • Будет ли вышеупомянутый метод фактически продаваться параллельно?
  • Как я могу определить, действительно ли мой код генерирует что-то которые будут выполняться параллельно?

Я попробовал это для 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

Ответы

Ответ 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

Так что да, он работает параллельно. 1.6x на двухъядерной машине, с первой попытки. Независимо от того, эффективен он или нет, это еще один вопрос. Используйте + RTS -s, вы можете увидеть статистику времени выполнения:

ЗАДАЧИ: 4 (1 связанный, 3 пиковых рабочих (всего 3), используя -N2)

Итак, у нас было 3 потока, работающих параллельно (2 предположительно для algo, один для менеджера 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

Таким образом, он снизил до 1,8 с 2,7 (улучшение на 30%) за счет использования параллельной среды выполнения, бэкэнд LLVM и осторожности с флагами GC. Вы можете посмотреть на поверхность флага GC, чтобы найти оптимальный:

enter image description here

Если лоток вокруг -A64 -N2 идеален для размера набора данных.

Я также настоятельно рекомендую использовать ручное устранение общего подвыражения в вашем внутреннем ядре, чтобы избежать чрезмерного перерасчета вещей.

Как говорит Альп, чтобы увидеть поведение во время выполнения программы, скомпилируйте потокомер (из Hackage) и выполните следующее:

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

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

И вы получите трассировку событий для ваших двух ядер следующим образом:

enter image description here

Итак, что здесь происходит? У вас есть начальный период (0,8 с) времени установки - выделение большого списка и его кодирование в массив repa - как вы можете видеть при однопоточном чередовании GC и выполнении. Затем еще один 0.8s что-то на одном ядре, прежде чем ваша фактическая параллельная работа произойдет за последние 300 мс.

Таким образом, в то время как ваш фактический алгоритм может хорошо распараллеливаться, все окружающая тестовая установка в основном увеличивает результат. Если мы сериализуем ваш набор данных, а затем просто загружаем его с диска, мы можем улучшить поведение:

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

и теперь ваш профиль выглядит более здоровым:

enter image description here

Это выглядит великолепно! Очень мало GC (производительность 98,9%), и мои два ядра работают параллельно.

Итак, наконец, мы видим, что вы получаете хороший parallelism:

С 1 ядром, 1,855 с

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

и с 2 ядрами, 1,014 с

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

Теперь, конкретно, ответьте на ваши вопросы:

  • Есть ли более идиоматический способ сделать это в repa?

В общем случае код repa должен состоять из параллельных траверсов, потребителей и выпусков и встроенных функций ядра. Поэтому, пока вы это делаете, код, вероятно, идиоматичен. Если есть сомнения, посмотрите учебник. Я бы вообще отметил ваши рабочие ядра (например, f) как inlined.

  • Будет ли вышеупомянутый метод фактически продаваться параллельно?

Код будет выполняться параллельно, если вы используете параллельные комбинаторы типа computeP или различные карты и складки. Так что да, он должен и должен работать параллельно.

  • Как я могу определить, код действительно генерирует что-то, что будет выполнено в параллельно?

Как правило, вы будете знать априори, потому что вы используете параллельные операции. Если есть сомнения, запустите код и наблюдайте за ускорением. Затем вам может понадобиться оптимизировать код.