TP - Optimization of the energy consumption of a Matrix Multiplication

Pour représenter les matrices en Rust nous allons utiliser la structure suivante:

• Element est le type des valeurs à l’intérieur de la matrice, ici des nombres à virgule flottante stockés sur 64 bits (l’équivalent des double en C).

• n représente la taille d’un côté de la matrice

• values est un vecteur qui contient les éléments de la matrice

  1. Implémentez pour la structure Matrix un constructeur fn new(n: usize, values: Vec<Element>) → Self. Attention à bien vérifier grace à une assertion que le vecteur values contient bien \(n^2\) valeurs.

Une matrice est une structure à deux dimensions, mais nous allons la stocker sur le vecteur values à une seule dimension. Il y a plusieurs ordres de stockage possibles. Ici, nous allons stocker les matrices dans l’ordre des lignes (row-major order).

Nous souhaitons cependant pouvoir accéder aux éléments en utilisant les indices ligne i et colonne j.

1. Implémentez les traits std::ops::Index<(usize, usize)> et std::ops::IndexMut<(usize, usize)> pour la structure Matrix de manière à ce que l’on puisse accéder aux éléments de la matrice avec la syntaxe suivante,

1. Implémentez un deuxième constructeur fn id(n:usize) → Self qui retourne la matrice identité de dimension \(n\).

2. Implémentez un troisième constructeur fn random(n:usize) → Self qui retourne une matrice de dimension \(n\) dont les éléments sont tirés aléatoirement d’une distribution uniforme sur \([-1.0, 1.0\)].

Dans la suite du TP nous allons utiliser l’outil perf pour faire diverses mesurer de performance. Pour installer l’outil perf sous Ubuntu ou Debian vous pouvez exécuter les commandes suivantes:

1. Implémentez une méthode fn multiply(a: &Matrix, b: &Matrix) → Matrix qui retourne le résultat de la multiplication matricielle de a par b. Écrivez un code simple sans essayer à ce stade d’optimiser la fonction. Rajoutez un ou plusieurs tests pour tester que le résultat est correct.

2. Modifiez le fichier src/main.rs de manière à pouvoir réaliser le produit de deux matrices aléatoires dont la taille est passée en ligne de commande.

3. Utilisez l’outil perf pour estimer grâce aux compteurs RAPL la consommation énérgétique en Joules de votre programme pour une matrice de dimension 256x256.

4. Compilez maintenant le programme en utilisant les optimisations du compilateur et mesurez l’énergie consommée à nouveau.

Qu’observez vous ? Comment l’expliquez vous ?

5. Testez la version optimisée avec des dimensions plus grandes: 512, 768, 1024, 1280, 1536, 1792 ? Tracez la courbe de temps d’exécution et de consommation en fonction de n.

Comparez les avec les courbes ci-dessous obtenues sur un processeur à six coeurs i7-9850H CPU @ 2.60GHz, avec 12Mb de cache L3.

6. Quelles sont les caractéristiques de votre machine ? Vous pouvez utiliser les outils suivants:

   • lstopo pour examiner la hiérarchie mémoire

   • cat /proc/cpuinfo pour avoir les caractéristiques du processeur

Comme nous avons vu en cours, la multiplication de matrices peut présenter des problèmes d’accès au cache et à la mémoire. En effet, l’accès à la deuxième matrice n’est pas dans l’ordre des lignes mais dans l’ordre des colonnes. Les éléments d’une colonne ne sont donc pas contigus en mémoire.

Pour vérifier si notre implémentation souffre de problèmes de localité mémoire nous allons à nouveau utiliser l’outil perf.

1. Mesurons tout d’abord le nombre d’accès mémoire au dernier niveau de cache pour la version naïve avec la commande suivante:

• LLC-loads mesure le nombre de lectures depuis le dernier niveau de cache

• LLC-stores mesure le nombre d’écritures sur le dernier niveau de cache

2. Implementez maintenant une version bloquée de la multiplication matricielle, fn multiply_blocked(a: &Matrix, b: &Matrix) → Matrix. Définissez une constante BLOCK dans la classe Matrix pour stocker la taille du block que vous pouvez fixer à 64.

3. Mesurez maintenant le nombre d’accès mémoires au dernier niveau de cache pour la version bloquée ?

4. Mesurez la consommation énergétique et le temps d’exécution pour la version bloquée et comparez les aux mesures de la version naïve ?

5. Que concluez vous ? Pourquoi la version bloquée se révèle plus efficace ?

Si notre processeur possède plusieurs cœurs de calcul, nous pouvons paralléliser l’algorithme de manière à le rendre encore plus efficace. Pour cela nous allons nous appuyer sur la bibliothèque Rayon.

1. Implémentez une version parallèle du produit de matrices, fn multiply_rayon(a: &Matrix, b: &Matrix) → Matrix.

   • Nous vous conseillons de paralléliser en découpant selon les lignes de a et c (la matrice résultat).

   • Rayon ajoute les méthodes par_chunks(&self, chunk_size: usize) et par_chunks_mut(&mut self, chunk_size: usize) aux itérateurs. Ces deux méthodes retournent des itérateurs parallèles. Les opérations sur les itérateurs seront distribuées sur différents threads. Vous pouvez donc utiliser ces deux méthodes pour répartir un calcul sur les lignes de c et les lignes de a.

   • Pour itérer de manière synchronisé sur les lignes des deux itérateurs vous pouvez utiliser la méthode zip.

2. Mesurez l’énergie consommée par l’implémentation parallèle. Comparez les mesures aux expériences précédentes. Que concluez vous ?

3. Rajoutez du cache-blocking dans l’implémentation parallèle et mesurez l’effet sur la consommation.

Pour aller plus loin…​

Crédits