Parallélisme : cours

Liste des travaux pratiques / dirigés

1. Produit de Matrices

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 :

  1. template<class T>
  2. class Matrix {
  3. public:
  4.     int rows, cols, size;
  5.     T *data;
  6.    
  7.     Matrix() {
  8.         rows = cols = size = 0;
  9.         data = nullptr;
  10.     }
  11.    
  12.     Matrix(int _rows, int _cols) {
  13.         rows = _rows;
  14.         cols = _cols;
  15.         size = _rows * _cols;
  16.         data = new T [ size ];
  17.     }
  18.    
  19.     ...
  20.    
  21.     T& operator()(int i, int j) {
  22.         return data[ i * cols + j ];
  23.     }
  24.    
  25. };
  26.  
  27. template<class T>
  28. void product( Matrix<T>& a, Matrix<T>& b, Matrix<T>& c) {
  29.     c.resize( a.rows, b.cols );
  30.     for (int i = 0; i < a.rows; ++i) {
  31.         for (int j = 0; j < b.cols; ++j) {
  32.             T sum = (T) 0;
  33.             for (int k = 0; k < a.cols; ++k) {
  34.                 sum += a(i,k) * b(k,j);
  35.             }
  36.             c(i,j) = sum;
  37.         }
  38.     }
  39. }
  40.  

Produit classique et dérivés en parallèle

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.

Validité et performance

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.

Graphiques

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

BLAS

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 $$

$α$ et $β$ sont des réels et $op$ est soit l'identité, la transposée ou la transposée conjuguée.

  1. #include <iostream>
  2. #include <numeric>
  3. using namespace std;
  4. #include <cblas.h>
  5. #include <xmmintrin.h>
  6.  
  7. /*
  8. extern "C" void cblas_dgemm(const enum CBLAS_ORDER Order, const enum CBLAS_TRANSPOSE TransA,
  9.                  const enum CBLAS_TRANSPOSE TransB, const int M, const int N,
  10.                  const int K, const double alpha, const double *A,
  11.                  const int lda, const double *B, const int ldb,
  12.                  const double beta, double *C, const int ldc);
  13.  */
  14. int DIM = 1000;
  15. double *A;
  16. double *B;
  17. double *C;
  18.                  
  19. int main(int argc, char *argv[]) {
  20.     char TRANS = 'N';
  21.     double alpha = 1.0;
  22.     double beta = 0.0;
  23.  
  24.     srand(19702013);
  25.    
  26.     if (argc > 1) {
  27.         DIM = atoi(argv[1]);
  28.     }
  29.    
  30.     int size = DIM*DIM;
  31.    
  32.     // allocate
  33.     A = static_cast<double *>(_mm_malloc(size * sizeof(double), 16));
  34.     B = static_cast<double *>(_mm_malloc(size * sizeof(double), 16));
  35.     C = static_cast<double *>(_mm_malloc(size * sizeof(double), 16));
  36.    
  37.     // fill
  38.     for (int i=0; i<size; ++i) {
  39.         A[i] = (rand() % 131) * 0.01;
  40.         B[i] = (rand() % 131) * 0.01;
  41.     }
  42.    
  43.     cblas_dgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans, DIM, DIM, DIM,
  44.         alpha, A, DIM, B, DIM, beta, C, DIM);
  45.  
  46.     // check result
  47.     double sum = accumulate(&C[0], &C[size], 0.0);
  48.    
  49.     cout << "sum = " << sum << endl;
  50.    
  51.     _mm_free(A);
  52.     _mm_free(B);
  53.     _mm_free(C);
  54.     return 0;
  55. }
  56.