Tarification et risque des options idiomatiques à l'aide de tableaux parallèles Repa

Question

Supposons que je veuille le prix d'une option d'achat à l'aide d'une méthode des différences finies et repa puis le suivant fait le travail:

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 

Mais maintenant, supposons que je veuille prix des options en parallèle (dit de faire une place échelle), alors je peux faire ceci:

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

Questions:

1. Est-il plus idiomatiques façon de le faire dans le repa?
2. Sera la méthode ci-dessus, les cours en parallèle?
3. Comment puis-je déterminer si mon code est vraiment générer quelque chose qui seront exécutées en parallèle?

J'ai essayé ce pour 3 mais malheureusement rencontré un bug dans 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

Votre bug est pas lié à la votre code, il est de votre utilisation de l' -fext-core d'imprimer la sortie de la compilation du Noyau Externe format. Il suffit de ne pas le faire (voir le noyau, j'utilise ghc-core).

Compiler avec -O2 et -threaded:

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

Puis courir avec +RTS -N4, par exemple, pour utiliser 4 threads:

$ 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

De sorte qu'il se termine trop vite pour voir la suite. Je vais augmenter votre m et p paramètres de 1k et 3k

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

Donc, oui, il ne s'exécutent en parallèle. 1,6 x sur un 2 core de la machine, lors d'une première tentative. Si elle est ou non efficace est une autre question. Utilisez +RTS-s, vous pouvez voir l'exécution stats:

TÂCHES: 4 (1 lié, 3 pic de travailleurs (3 au total), aide -N2)

Nous avons donc eu 3 threads s'exécutant en parallèle (2 probablement pour l'algo, l'un pour le gestionnaire d'e / s).

Vous pouvez réduire le temps d'exécution par le réglage de la table de paramètres. E. g. en utilisant -A nous pouvons réduire GC-dessus, et le rendement authentiques parallèle accélérations.

$ 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

Vous pouvez améliorer les performances numérique, parfois à l'aide de la LLVM backend. Cela semble être le cas ici aussi:

$ 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

Rien de spectaculaire, mais vous êtes l'amélioration des temps d'exécution sur votre seule version filetée, et je n'ai pas modifié votre code d'origine en quelque sorte. Pour vraiment améliorer les choses, vous aurez besoin de profil et de les optimiser.

Revisiter l'Un des drapeaux, nous pouvons apporter à la fois vers le bas encore plus loin en utilisant un te sentir plus ajusté lié sur le thread initial de l'allocation de la zone.

$ 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

Ainsi apporté à 1.8 s de 2,7 (30% d'amélioration) à l'aide de la parallèle de l'exécution, le LLVM backend, et en faisant attention GC drapeaux. Vous pouvez regarder l'indicateur GC surface afin de trouver l'optimum:

Avec le creux autour de -A64 -N2 idéal pour le jeu de données de taille.

Je voudrais également fortement envisager d'utiliser le manuel de l'élimination des sous-expressions redondantes dans votre noyau, pour éviter de recalculer les choses à l'excès.

Comme Alp suggère, pour voir le comportement d'exécution du programme, compiler threadscope (à partir de Hackage) et l'exécuter comme suit:

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

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

Et vous obtenez un événement de trace de vos deux cœurs comme suit:

Alors que ce passe ici? Vous avez une première période (0,8 s) de temps d'installation -- l'allocation de votre grande liste et l'encodage dans un repa tableau -- comme vous pouvez le voir par la mono-thread entrelacement de GC et de l'exécution. Ensuite, il y a un autre 0.8 s de quelque chose sur un seul core, avant votre travail parallèle se produit pour la dernière 300ms.

Donc, même si votre algorithme réel peut être la parallélisation de bien, tous les environs de configuration de test de coeur des marais du résultat. Si nous sérialiser vos dataset, puis il suffit de charger l'arrière à partir du disque, nous pouvons obtenir un meilleur comportement:

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

et maintenant votre profil semble plus sain:

Cela ressemble beaucoup! Très peu de GC (98.9% de productivité), et mes deux cœurs qui s'exécutent en parallèle et heureusement.

Donc, finalement, nous pouvons voir que vous obtenez un bon parallélisme:

Avec 1 core, 1.855 s

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

et avec 2 cœurs, 1.014 s

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

---

Maintenant, plus précisément de répondre à vos questions:

1. Est-il plus idiomatiques façon de le faire dans le repa?

En général, repa code devrait consister en parallèle traverals, des consommateurs et de produit, et inlinable fonctions du noyau. Donc, tant que vous faites cela, alors le code est probablement idiomatiques. En cas de doute, regardez le tutoriel. Je préfère en général la marque de votre travailleur d'amandes (comme f) comme inline.

1. Sera la méthode ci-dessus, les cours en parallèle?

Le code s'exécute en parallèle, si vous utilisez parallèle combinators comme computeP ou les différentes cartes et les plis. Donc oui, il faut et ne s'exécutent en parallèle.

1. Comment puis-je déterminer si mon le code est vraiment générer quelque chose qui sera exécuté dans en parallèle?

Généralement, vous le savez a priori parce que vous utilisez les opérations en parallèle. En cas de doute, exécutez le code et d'observer l'accélération. Il peut être nécessaire d'optimiser le code.