arrays - ingles - qué significa en español

La fijación de precios y el riesgo de las opciones idiomáticas utilizando arreglos paralelos Repa

Question

Supongamos que quiero asignarle un precio a una opción de llamada utilizando un método de diferencia finita y repagar, entonces lo siguiente hace el trabajo:

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 

Pero ahora supongamos que quiero ponerle precio a las opciones en paralelo (por ejemplo, para hacer una escalera), entonces puedo hacer esto:

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

Preguntas:

1. ¿Hay una forma más idiomática de hacer esto en Repa?
2. ¿El método anterior realmente precio en paralelo?
3. ¿Cómo puedo determinar si mi código realmente está generando algo que se ejecutará en paralelo?

Intenté esto por 3 pero lamentablemente encontré un error en 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

Su error no está relacionado con su código; es su uso de -fext-core para imprimir el resultado de la compilación en el formato External Core. Simplemente no hagas eso (para ver el núcleo, yo uso ghc-core ).

Compila con -O2 y -threaded :

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

Luego ejecute con +RTS -N4 , por ejemplo, para usar 4 hilos:

$ 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

Por lo tanto, se completa demasiado rápido para ver un resultado. Aumentaré tus parámetros myp a 1k y 3k

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

Entonces sí, funciona en paralelo. 1.6x en una máquina de 2 núcleos, en un primer intento. Si es o no eficiente es otra pregunta. Utilice + RTS -s para ver las estadísticas de tiempo de ejecución:

TAREAS: 4 (1 obligado, 3 trabajadores punta (3 en total), utilizando -N2)

Así que teníamos 3 hilos ejecutándose en paralelo (2 presumiblemente para el algo, uno para el administrador de IO).

Puede reducir el tiempo de ejecución ajustando la configuración del GC . Por ejemplo, mediante el uso de -A podemos reducir la sobrecarga del GC y producir aceleraciones paralelas genuinas.

$ 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

Puede mejorar el rendimiento numérico a veces utilizando el servidor de LLVM. Este parece ser el caso aquí también:

$ 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

Nada espectacular, pero está mejorando el tiempo de ejecución de su versión de un solo subproceso, y no he modificado su código original de ninguna manera. Para mejorar realmente las cosas, necesitarás perfilar y optimizar.

Revisando las banderas -A, podemos reducir aún más el tiempo usando un límite en el área de asignación de hilos inicial.

$ 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

De modo que lo redujimos a 1.8 desde 2.7 (mejora del 30%) al usar el tiempo de ejecución paralelo, el backend de LLVM y tener cuidado con los indicadores de GC. Puede mirar la superficie de la bandera de GC para encontrar el óptimo:

Con la depresión alrededor de -A64 -N2 es ideal para el tamaño del conjunto de datos.

También consideraría seriamente el uso de la eliminación manual de subexpresiones comunes en su kernel interno, para evitar el recalibrado excesivo de las cosas.

Como sugiere Alp, para ver el comportamiento en tiempo de ejecución del programa, compile threadscope (de Hackage) y ejecútelo de la siguiente manera:

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

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

Y obtienes un rastro de evento para tus dos núcleos así:

Entonces, ¿qué está pasando aquí? Tiene un período inicial (0,8 segundos) de tiempo de configuración, asignando su lista grande y codificándola en una matriz Repa, como puede ver por el intercalado de rosca única de GC y la ejecución. Luego hay otros 0,8 s de algo en un solo núcleo, antes de que su trabajo paralelo real ocurra durante los últimos 300 ms.

Entonces, aunque su algoritmo real se puede paralelizar muy bien, toda la configuración de prueba circundante básicamente inunda el resultado. Si serializamos su conjunto de datos , y luego solo lo cargamos desde el disco, podemos obtener un mejor comportamiento:

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

y ahora tu perfil se ve más saludable:

¡Esto se ve genial! Muy poco GC (98,9% de productividad), y mis dos núcleos corriendo en paralelo felizmente.

Entonces, finalmente, podemos ver que obtienes un buen paralelismo:

Con 1 núcleo, 1.855s

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

y con 2 núcleos, 1.014s

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

Ahora, responda específicamente sus preguntas:

1. ¿Hay una forma más idiomática de hacer esto en Repa?

En general, el código de reparación debe consistir en viajes paralelos, consumidores y produce, y funciones de kernel inelicables. Entonces, mientras lo hagas, entonces el código probablemente sea idiomático. En caso de duda, mira el tutorial . En general, marcaría sus núcleos de trabajadores (como f ) como en línea.

1. ¿El método anterior realmente precio en paralelo?

El código se ejecutará en paralelo si usa combinadores paralelos como computeP o los diversos mapas y pliegues. Así que sí, debería y se ejecuta en paralelo.

1. ¿Cómo puedo determinar si mi código realmente está generando algo que se ejecutará en paralelo?

En general, sabrá a priori porque usa operaciones paralelas. En caso de duda, ejecute el código y observe la aceleración. Es posible que deba optimizar el código.