Discussion :

[lyxthe]

Bonjour, j'ai une question à propos d'optimisation de code en vue d'améliorer des performances. (je reprend ce que j'ai déjà expliqué ici : http://www.developpez.net/forums/d96...bleau-tableau/ en changeant un peu ma question).

Je développe un programme dont le but est de calculer une suite d'entiers jusqu'à un certain rang non connu à l'avance. Chacun des entiers correspond (plus ou moins) à l'élément minimum d'une matrice particulière. Au départ j'ai une matrice M grande (selon les cas entre 200Mo et plusieurs giga), le nième entier de ma suite est l'entier minimum que contient la matrice M à la puissance n (selon une algèbre particulière où, pour le calcul de M*M, on remplace l'addition usuelle par l'opération min, et la multiplication usuel par l'addition).

Bref je dois calculer une suite d'entier, pour chaque entier, prenons le nieme j'ai besoin de connaitre trois grandes matrices, M, M^(n-1) et M^n.

Après toutes ces explications fastidieuses, voici ma question.

En vue de diminuer le temps d'exécution du programme, j'aimerai savoir quel serait les meilleurs options. Le programme est prévu pour tourner exclusivement sur un quad core 64bits (pour l'instant il utilise uniquement les ressource d'un seul coeur) sous windows 7.

Après avoir lu cette discution :
http://www.developpez.net/forums/d92...eur-appli-cpp/ j'ai cru comprendre qu'il était possible d'explorer plusieurs pistes principales :
multithreadings pour utiliser tous les coeurs (mais je sais pas trop ce que je vais pouvoir paraléliser)
SIMD mais je sais pas trop si c'est applicable à mon cas
exécuter le programme sur mon GPU

Vers quoi devrais-je me tourner ?

Merci

[bruno_pages]

Bonjour,

mais je sais pas trop ce que je vais pouvoir paraléliser

des opérations telle que l'addition de matrice sont trivialement parallélisable, découpez par exemple vos boucles de 1 à n en 4 boucles : de 0 .. n/4-1 et n/4 .. n/2-1 et n/2-1 .. 3n/4-1 et 3n/4 .. n en exécutant chacune dans un thread différent

[jblecanard]

Salut

tu n'es pas obligé de te taper ce travail à la mano, OpenMP est ton ami pour cette tâche.

Attention : il se peut que même parallélisé, le calcul ne soit pas beaucoup plus rapide. Tu n'es pas limité que par le processeur, tu l'es aussi par le bus de données. Cela dit, ça vaut le coup d'essayer.

Une discussion qui peut t'intéresser : http://old.nabble.com/uBLAS-parallel...d22842406.html

Si tu as vraiment besoin de grosses perfos et que tu as une carte graphique tu peux aussi paralléliser les calculs sur la carte avec OpenCL. Bien utilisé, ça peut faire exploser tes perfos.

[Aleph69]

Bonjour,

à mon avis tu as beaucoup à gagner en réfléchissant à un algorithme efficace.
Pour deux matrice A et B, le terme cij de C=A*B s'écrit (si j'ai bien compris)

cij = min_k (a_ik+b_kj)

Etant donné que tu manipules des minima, tu dois pouvoir exploiter les signes de tes coefficients dans un premier temps : la somme de deux entiers positifs est supérieure à chacun des deux entiers.

Il y a aussi peut-être des choses à faire du côté des symétries/anti-symétries,

cij = min_k (a_ik+b_kj),
cji = min_k (a_jk+b_ki) (coefficient de la transposée),

pour les puissances paires en particulier.

Dans le même ordre d'idée, il n'est pas forcément malin de calculer la suite dans l'ordre d'apparition des termes M,M^2,M^3,...
Une fois que tu as calculé M^2, il est peut-être judicieux de calculer M^4.
(J'ai supposé M^4=M^2*M^2 mais je n'ai pas vérifié).
Bonne chance avec les puissances de nombres premiers...

Autre chose : a priori tu vas avoir trois boucles imbriquées (indices i,j,k). Essaye de voir toutes les permutations possibles d'imbrications de boucles : i-j-k,i-k-j,j-i-k,j-k-i,k-i-j,k-j-i (au mieux). Tu peux améliorer la localité de tes données, la réutilisation de la mémoire cache en faisant le meilleur choix.