Discussion :

[bongo parfait]

boujour
j'ai un algo qui resoud ce exercice mais j'aimerai avoir un programme optimisé qui me permettra d' afficher le produit de deux matrices et de mettre le resultat dans une troisième matrice.merci

[droggo]

Hi,

De quel exercice parles-tu ?

Avant d'optimiser, il faut écrire un programme qui fonctionne, c'est le plus important.

[Loceka]

A vrai dire l'optimisation du produit matriciel dépend essentiellement du langage (et du compilateur) utilisé.

Je ne connais pas du tout la gestion des différents compilateurs Pascal en ce qui concerne la gestion en mémoire des tableaux.

Tu as donc 2 façons de coder ton produit matriciel :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// première méthode (simple réécriture de la formule mathématique)
// soit A et B 2 matrices, on a C_ij = Somme_k(A_ik * B_kj)
 
pour i de 0 a N faire
	pour j de 0 a N faire
		s = 0;
		pour k de 0 a N faire	// on somme sur la colonne de 'a' et la ligne de 'b'
			s = s + a[i][k]*b[k][j];
		fin_pour
		c[i][j] = s;		// resultat dans c_ij
	fin_pour
fin_pour
 
 
// deuxième méthode
pour i de 0 a N faire
	pour k de 0 a N faire
		s = a[i][k];		// on stocke la valeur de la colonne de 'a'
		pour j de 0 a N faire	// on ajoute a c_ij la valeur de la colonne de 'a' et de la ligne de 'b'
			c[i][j] = c[i][j] + s*b[k][j];
		fin_pour
	fin_pour
fin_pour

Tu remarques que le premier code fait des appels successifs de a[.][k] et de b[k][.], donc de la colonne de 'a' et de la ligne de 'b'.

Or ça, typiquement ce n'est pas du tout optimal.
En effet ton compilateur (en C en tout cas ça se passe comme ça) va charger dans le cache des "blocs" de variables. Il conserve ces "blocs" dans le cache tant qu'ils ont toujours une "chance" d'être utilisés (ça, ça dépend de la politique après : Least Recently Used, etc.) ET tant qu'il peut les conserver.
En effet, lorsqu'il charge une ligne/colonne (cf. la suite) dans le cache, il charge toute la ligne/colonne et pas seulement la valeur qui l'intéresse. Ce qui fait qu'il écrase les autres variables stockées.

Là, typiquement, on remarque qu'il va constament réécrire la mémoire et recharger les variables.


Dans le deuxième code, on remarque qu'il ne travaille plus que sur la valeur de la colonne de 'b', pour une ligne fixée. Donc il chargera dans le cache tout le contenu de la ligne 'k' de 'b' et il pourra accéder directement aux variables.

Ce qui fait que c'est si important, c'est que les temps d'accès du cache et de la RAM sont très différents. Le temps d'accès à une variable dans le cache se fait plus vite que celui d'une variable dans la mémoire ET de toute façon ta variable doit passer par le cache pour être utilisée (si je me souviens bien) : on ne peut donc pas accéder directement à la valeur de la variable en mémoire.

Là où ça diffère entre les langages et les compilateurs c'est dans la façon de charger les colonnes ou les lignes d'un tableau.

Dans le deuxième code, on suppose que le cache contient toute la ligne 'k' de la matrice 'b'. Sinon il est aussi mauvais que le premier.
Seulement ce chargement de toute la ligne dans le cache n'est pas standard et il existe des langages/compilateurs qui chargent au contraire toute une colonne dans le cache.

En ce qui concerne le Pascal je n'ai aucune idée de comment ça fonctionne donc je ne peux pas t'en dire plus.
Par contre tu peux le savoir facilement en faisant des tests.
Pour ça il te suffit de réécrire le deuxième code pour qu'il traite les lignes de 'a' au lieu des colonnes de 'b'.

J'espère avoir répondu à ta question.

Edit :
On peut encore optimiser l'algo en découpant la matrice en blocs et en les faisant les opérations sur ces blocs. C'est utile si la matrice est trop grande pour que le cache contienne toutes les valeurs d'une ligne/colonne.