Parallélisme : cours
Liste des travaux pratiques / dirigés
On s'intéresse à la parallélisation du produit matriciel. On rapelle que le produit de deux matrices $A(n × p)$ par $B(p × q)$ est une matrice $C(n × q)$ telle que : $$ C_i^j = ∑↙{k=1}↖{p} A_i^k × B_k^j $$
Ce qui se traduit en informatique par le code C++ suivant :
Ecrire un programme C++ (matrix_product.exe) qui permet de réaliser le produit de deux matrices carrées de double $A$ et $B$. La méthode de calcul choisie ainsi que la dimension des matrices (qui par défaut est de 1024) seront passées en arguments du programme (penser à utiliser getopt).
Les méthodes à implanter sont les suivantes :
Attention, l'une de ces méthodes ne donne pas de résultat correct.
Réaliser un script bash (test_matrix_product_validity.sh) qui permet de vérifier si chaque méthode donne un résultat correct du calcul. On affichera par exemple le coefficient C[0,0] de la matrice qui servira de valeur de référence.
Réaliser un script bash (test_matrix_product_performance.sh) qui permet de calculer les temps de calculs avec les différentes versions valides et de les comparer.
On génèrera des graphiques grâce à gnuplot (ou octave) pour comparer l'efficacité du calcul des méthodes avec différentes dimensions de matrices notamment 512, 1024, 2048, 4096.
On pourra utiliser la commande /usr/bin/time -f "%e;%E;%U" bin/matrix_product.exe paramètres pour obtenir les temps de calcul.
Les fichiers de données seront de la forme matrix_1.gpd, matrix_2.gpd, etc (d'extension .gpd pour GnuPlot Data) et contiendront les temps d'exécution de chaque méthode pour les dimensions 512, 1024 et 2048 :
512 0.34
1024 4.03
2048 49.96
3092 66.66
4096 438.22
Voici un exemple de script gnuplot (matrix.gps) qui utilise le fichier de palette suivant palette.pal pour afficher les graphiques obtenus :
# fichier matrix.gps
set term pdfcairo enhanced size 6in,5in color font 'Helvetica,12'
set output "matrix.pdf"
# use of palette to have different line colors
load 'palette.pal'
# define grid
set style line 102 lc rgb '#808080' lt 0 lw 1
set grid back ls 102
set key below
set title "matrix product"
set xlabel "dimension of matrix"
set ylabel "Time in seconds"
set xtics rotate by -90
plot "matrix_1.gpd" using 1:2 with lines ls 1 title "m1", "matrix_2.gpd" using 1:2 with lines ls 2 title "m2", "matrix_3.gpd" using 1:2 with lines ls 3 title "m3", "matrix_4.gpd" using 1:2 with lines ls 4 title "m4", "matrix_5.gpd" using 1:2 with lines ls 5 title "m5", "matrix_6.gpd" using 1:2 with lines ls 6 title "m6"
Exemple de graphique généré avec GNU Octave
Utiliser la librairie BLAS (Basic Linear Algebra Subprograms) pour faire le produit de matrices notamment le sous-prorgamme DGEMM. BLAS est une librairie de sous-programmes optimisés pour calcul matriciel :
Voir la BLAS Reference Card.
Sous Ubuntu, installer les packages :
Voici à présent un exemple de code pour l'appel afin d'effectuer un produit de matrices avec double DGEMM (Double GEneral Matrix Matrix) :
$$ C ← α . op(A) × op(B) + β . C $$où $α$ et $β$ sont des réels et $op$ est soit l'identité, la transposée ou la transposée conjuguée.