Mineure CalHau1
Cours de 3ème année à CentraleSupélec
BE d'optimisations sérielles et de vectorisation
(Utilisation optimale d'un coeur de calcul)
Stéphane
Vialle
Exercice 1 : optimisations sérielles manuelles et progressives d'un produit de
matrices en C sous Linux/gcc
Certaines
optimisation sont réalisées par les
compilateurs, d’autres nécessitent une
modification du code source par le
programmeur. Chaque optimisation explicite est liée
à un concept
d’architecture, et équivaut à prendre
en compte l’architecture de la machine
depuis le code source. Cependant, la plupart de ces optimisations sont
« standard » et sont valables sur
la majorité des systèmes.
Dans
cet exercice :
- Le produit de
matrices carrées denses servira de problème
support, et sera implanté
« naïvement » puis de
plus en plus efficacement.
- Les performances de chaque
étape seront mesurées et rassemblées
dans des tables et des graphes de performances. ON VEILLERA A REALISER
LES DEVELOPPEMENTS ET LES TESTS DANS L’ORDRE !!
Rappel :
1.1 - Prenez connaissance du code
- Calculez le nombre d’opérations de
calcul flottant nécessaire à un produit de
matrices carrées denses (de taille n×n). Vérifiez le calcul automatique des performances
à la fin de la fonction main.
- Etudiez le « Makefile ».
Que fait l’option de compilation
« -O0 » ? (regardez le
man de
gcc).
1.2 - Réalisez une première mesure de
performances sur le kernel 0
- Compilez votre programme pour des matrices de 2048x2048 éléments (de type double).
- Exécutez votre programme avec votre
calcul naïf (kernel 0) en ayant pris soin de n’activer
aucune optimisation du
compilateur (sous Linux : option "-O0" dans le Makefile).
- Relevez cette première mesure de performances dans le fichier Excel.
1.3 - Optimisation du kernel 0
Conservez vos versions intermédaires !!
- Activation des optimisations automatiques
normalisées du compilateur
Utilisation de l'option -Ox (avec x variant de 0 à 3) en modifiant le Makefile.
Compilez encore votre programme avec des matrices de 2048x2048.
- Diminution la
fréquence des accès au tableau C
Modifiez
votre code source pour utiliser un "accumulateur local" et accéder
moins souvent au tableau C.
Vérifiez l'exactitude des résultats.
Puis mesurez les performances obtenues en -O0 et en -O3
Ensuite restez en -O3
- Diminution des défauts de cache / meilleure exploitation du cache :
Identifiez où se situent (théoriquement) des défauts de cache
fréquents dans ce
programme (si le temps le permettait on utiliserait un profiler de code, comme Valgrind).
Evitez
les
défauts de cache en réorganisant les structures de données
(et sans changer l’ordre naturel des instructions).
Vérifiez l'exactitude des résultats, puis mesurez les performances obtenues
- Diminution de la fréquence des ruptures de pipeline et début de vectorisation par "loop unrolling" :
Quelles
sont les options de compilation agissant sur
le « loop unrolling »
(étudiez le « man » de
gcc) ?
Compilez
et testez avec chaque option de compilation de "loop unrolling", sans
modifier votre code source.
Déroulez explicitement la
(bonne) boucle d'un facteur 4, puis 8 (puis 16), compilez sans option de "loop unrolling"
et testez.
Modifiez votre code (comme précédemment) ET compilez avec l'option de "loop unrolling" adaptée à votre programme, et testez.
- Meilleur usage des unités vectorielles d'un coeur. Deux stratégies sont possibles :
- Parallélisme inter-instructions : avec un "vecteur d'accumulateurs" rendez les
instructions complètement indépendantes, afin que le compilateur puisse
ré-agencer au mieux ces instructions.
- Parallélisme intra-instruction : regrouper un maximum d'opérations en une
seule instruction, afin que le compilateur puisse
ré-agencer au mieux ces opérations.
Rmq
: On peut aussi "guider le compilateur" pour
qu'il l'enclenche plus facilement (mais l'utilisation du compilateur icc d'Intel n'est pas prévue dans ces BEs).
- Autre stratégie de meilleur usage du cache ET des untiés vectorielles par interversion des boucles :
Revenez
au code initial, et changez l'ordre des boucles de calcul pour diminuer
les défauts de cache et favoriser la vectorisation (compilez toujours
en -O3)
1.4
- Bilan des optimisations :
- Tracez les temps d'exécution et les Gigaflops obtenus avec la succession des optimisations expérimentées, indiquez clairement la taille du problème associé à chaque mesure.
- Tracez les accélérations calculées vis à vis du code naif compilé en -O0, et du code naif compilé en -O3.
- En considérant la version la plus performante : quelle accélération avez-vous obtenue avec les optimisations automatiques
seules ? puis avec les optimisations manuelles ? et en cumulant les
deux ?
- Finalement quelles sont les étapes
primordiales à ne pas oublier lors d’une
implantation d'un noyau de calcul intensif ?