Est-ce que cela peut être optimisé?

Question

J'ai un programme qui tourne plus lentement que je le voudrais.

J'ai fait quelques profilage, et je l'ai trouvé la section qui prend la grande majorité du temps de traitement

 DO K = 0, K_MAX 
      WRITE(EIGENVALUES_IO, *) K * 0.001 * PI, (W_UP(J), J=1, ATOM_COUNT) 
      DCMPLXW_UP(:) = DCMPLX(W_UP(:)) 
      DO E = 1, ENERGY_STEPS 
       ENERGY = MIN_ENERGY + ENERGY_STEP * REAL(E, DP) 
       ZV = DCMPLX(ENERGY, DELTA) 
       ON_SITE_SINGLE = DCMPLX(0.0_DP) 
       DO Q = 1, ATOM_COUNT 
        DO J = 1, ATOM_COUNT 
         ON_SITE_SINGLE(J) = ON_SITE_SINGLE(J) + (MATRIX_UP(J, Q) * MATRIX_UP_CONJG(J, Q))/(ZV - DCMPLXW_UP(Q)) 
        END DO 
       END DO 
       DOS_DOWN(E) = DOS_DOWN(E) - WEIGHTS(K) * SUM(IMAG(ON_SITE_SINGLE)) 
      END DO 
     END DO 

La ligne

ON_SITE_SINGLE(J) = ON_SITE_SINGLE(J) + (MATRIX_UP(J, Q) * MATRIX_UP_CONJG(J, Q))/(ZV - DCMPLXW_UP(Q)) 

est celui qui fait les dégâts. Je suis assez novice en la matière, y a-t-il un moyen d'accélérer ce processus? AFAIK, les mêmes principes s'appliquent avec C, donc toute aide de votre part serait bien.

Les tableaux sont tous COMPLEXE

K_MAX est 1000

ENERGY_STEPS est 1000

ATOM_COUNT est faible (< 50)

Answer 1

Tous mes programmes tournent plus lentement que je le voudrais. Dans tous (OK, pas tous, mais beaucoup de) mes programmes scientifiques il y a un nid de boucle profonde dans lequel les instructions les plus internes prennent la majeure partie du temps de calcul. Typiquement, je m'attends à ce que 90% + de mes calculs soient repris par ces déclarations. Votre déclaration la plus secrète est en cours d'exécution 2.5x10^9 fois, alors vous devriez vous attendre à ce qu'elle prenne une fraction significative du temps total.

Dans cet esprit, je suggère que vous:

a) Prendre @ conseils d'Alexandre à utiliser BLAS plutôt que votre multiplication matrice-vecteur-brassée maison. B) ignorer les conseils de Yuval sur les opérations de levage hors de la boucle - un bon compilateur Fortran le fera pour vous si vous mettez l'optimisation à un niveau élevé (ATTENTION: ceci est une prophétie auto-réalisatrice dans la mesure où le compilateur n'est-ce pas un bon). Il y a beaucoup d'autres optimisations que j'attends d'un bon Fortran ces jours-ci, voir (d). (Je ne m'attends pas à une optimisation de l'accès mémoire par le compilateur, je m'attends à ce que BLAS.)

c) Formule une attente réaliste de la performance que vous devriez pouvoir obtenir de votre programme. Si vous obtenez un taux de FLOP soutenu supérieur à 10% de la performance nominale des processeurs, vous vous débrouillez très bien et vous devriez passer votre temps à faire autre chose qu'à optimiser.

d) Lisez attentivement la documentation de votre compilateur. Assurez-vous de bien comprendre ce que les indicateurs d'optimisation font réellement. Assurez-vous que vous générez du code pour les processeurs que vous utilisez, pas une variante plus ancienne. Commutez dans les opérations vectorielles rapides si elles sont disponibles. Tout ce genre de chose.

e) Démarrer la parallélisation. OpenMP est un bon point de départ et, comme l'indique @Nicolas, la courbe d'apprentissage est plutôt douce au début. Oh, et le conseil 0, que vous semblez avoir suivi, est de mesurer la performance du code et de mesurer l'impact de tout changement que vous effectuez.

Answer 2

Les facteurs vous divisez par, à savoir

(ZV - DCMPLXW_UP(Q)) 

ne dépend pas de J, seulement sur Q. Par conséquent, je déplacerais ce calcul jusqu'à la boucle Q. Mieux encore, calculer:

1/(ZV - DCMPLXW_UP(Q)) 

dans la boucle externe, et multiplier par elle au lieu de diviser l'intérieur de la boucle (AFAIR, multiplications sont plus rapides que les divisions). Vérifiez également que vos structures de données matricielles correspondent aux boucles (que les boucles parcourent le plus possible les parties contiguës de la mémoire). En règle générale, si vous pouvez améliorer l'algorithme, ce sera la plus grande amélioration du temps d'exécution.

Programming Pearls a une excellente description des optimisations similaires.

Answer 3

Si l'optimisation du code normal vous bloque, vous pouvez essayer OpenMP, qui est une API pour la programmation parallèle faite pour C et Fortran. Il y a quelques instructions que vous insérez dans votre code avant les boucles, style "pré-compilateur", et il va fractionner les boucles lourdes à travers différents processus.

Vous avez plusieurs instructions à essayer. Par exemple:

#pragma omp parallel for 
/* Loop here */ 

C'est une API très complète, et vous pouvez diviser tout selon un grand nombre de paramètres, variables partagées et différentes techniques de fractionnement parallèles. Vous pouvez également spécifier le nombre de processus que vous souhaitez créer, nombre de cœurs, etc.

Avec un peu de réglage, vous finirez par trouver une solution augmentant votre vitesse de calcul.

Answer 4

Veuillez utiliser BLAS pour 'multiplicateur matriciel-vecteur de vactor'. Vous effectuez cela essentiellement dans la ligne

ON_SITE_SINGLE(J) = ON_SITE_SINGLE(J) + (MATRIX_UP(J, Q) * MATRIX_UP_CONJG(J, Q))/(ZV - DCMPLXW_UP(Q)) 

Avec des bibliothèques BLAS bien accordées, vous pouvez obtenir une amélioration significative.