Désolé pour le long post, mais je voulais inclure tout ce que je pensais pertinent au premier coup.

Ce que je veux

J'implémente une version parallèle des méthodes de sous-espace de Krylov pour les matrices denses. Principalement GMRES, QMR et CG. J'ai réalisé (après profilage) que ma routine DGEMV était pathétique. J'ai donc décidé de me concentrer sur cela en l'isolant. J'ai essayé de l'exécuter sur une machine à 12 cœurs, mais les résultats ci-dessous concernent un ordinateur portable Intel i3 à 4 cœurs. Il n'y a pas beaucoup de différence dans la tendance.

Ma KMP_AFFINITY=VERBOSEsortie est disponible ici .

J'ai écrit un petit code:

size_N = 15000
A = randomly_generated_dense_matrix(size_N,size_N); %Condition Number is not bad
b = randomly_generated_dense_vector(size_N);
for it=1:n_times %n_times I kept at 50 
 x = Matrix_Vector_Multi(A,b);
end

Je crois que cela simule le comportement de CG pour 50 itérations.

Ce que j'ai essayé:

Traduction

J'avais à l'origine écrit le code en Fortran. Je l'ai traduit en C, MATLAB et Python (Numpy). Inutile de dire que MATLAB et Python étaient horribles. Étonnamment, C était meilleur que FORTRAN d'une seconde ou deux pour les valeurs ci-dessus. Régulièrement.

Profilage

J'ai profilé mon code à exécuter et il a fonctionné pendant 46.075quelques secondes. C'est à ce moment que MKL_DYNAMIC a été défini surFALSE et que tous les cœurs ont été utilisés. Si j'ai utilisé MKL_DYNAMIC comme vrai, seulement (environ) la moitié du nombre de cœurs étaient en cours d'utilisation à un moment donné. Voici quelques détails:

Address Line    Assembly                CPU Time

0x5cb51c        mulpd %xmm9, %xmm14     36.591s

Le processus le plus long semble être:

Call Stack                          LAX16_N4_Loop_M16gas_1
CPU Time by Utilization             157.926s
CPU Time:Total by Utilization       94.1%
Overhead Time                       0us
Overhead Time:Total                 0.0%    
Module                              libmkl_mc3.so   

Voici quelques photographies:

Conclusions:

Je suis un vrai débutant en profilage mais je me rends compte que l'accélération n'est toujours pas bonne. Le code séquentiel (1 cœur) se termine en 53 secondes. C'est une vitesse inférieure à 1,1!

Vraie question: que dois-je faire pour améliorer mon accélération?

Des trucs qui je pense pourraient aider mais je ne suis pas sûr:

• Implémentation de Pthreads
• Implémentation MPI (ScaLapack)
• Réglage manuel (je ne sais pas comment. Veuillez recommander une ressource si vous le suggérez)

Si quelqu'un a besoin de plus de détails (en particulier en ce qui concerne la mémoire), faites-moi savoir ce que je dois exécuter et comment. Je n'ai jamais profilé de mémoire auparavant.

Votre matrice a une taille de 15 000 x 15 000, vous avez donc 225 millions d'éléments dans la matrice. Cela représente environ 2 Go de mémoire. C'est bien plus que la taille du cache de votre processeur, il doit donc être chargé complètement à partir de la mémoire principale dans chaque multiplication de matrice, ce qui représente environ 100 Go de transferts de données, plus ce dont vous avez besoin pour les vecteurs source et de destination.

La bande passante mémoire maximale de l'i3 est d'environ 21 Go / s selon les spécifications d'Intel, mais si vous regardez sur le Web, vous constaterez qu'au plus la moitié de cela est vraiment disponible en réalité. Ainsi, à tout le moins, vous vous attendez à ce que votre référence dure 10 secondes, et votre mesure réelle de 45 secondes n'est pas si loin de cette marque.

Dans le même temps, vous effectuez également quelque 10 milliards de multiplications et d'ajouts à virgule flottante. En considérant, disons, 10 cycles d'horloge pour la combinaison et une fréquence d'horloge de 3 GHz, vous sortirez à environ 30 secondes. Bien sûr, ils peuvent s'exécuter simultanément avec des charges de mémoire spéculatives si le cache est intelligent.

Dans l'ensemble, je dirais que vous n'êtes pas trop loin de la réalité. À quoi vous attendiez-vous?

Comment faites-vous la multiplication matrice-vecteur? Une double boucle à la main? Ou des appels à BLAS? Si vous utilisez MKL, je vous recommande fortement d'utiliser les routines BLAS de la version filetée.

Par curiosité, vous souhaiterez peut-être également compiler votre propre version optimisée d' ATLAS et voir comment cela résout votre problème.

Mise à jour

Suite à la discussion dans les commentaires ci-dessous, il s'avère que votre Intel Core i3-330M ne possède que deux "vrais" cœurs. Les deux cœurs manquants sont émulés avec l' hyperthreading . Étant donné que dans les cœurs hyperthreadés, le bus mémoire et les unités à virgule flottante sont partagés, vous n'obtiendrez aucune accélération si l'un des deux est un facteur limitant. En fait, l'utilisation de quatre cœurs ralentira probablement même les choses.

Quel genre de résultats obtenez-vous sur "seulement" deux cœurs?

J'ai l'impression que l'ordre des lignes principales est optimal pour ce problème en ce qui concerne les temps d'accès à la mémoire, l'utilisation des lignes de cache et les échecs TLB. Je suppose que votre version FORTRAN a plutôt utilisé un classement par colonnes, ce qui pourrait expliquer pourquoi elle est toujours plus lente que la version C.

$b$ n'est pas conservé dans le cache. Vous pouvez tester si vous observez la même bande passante mémoire (effective) pour size_N = 15000 que pour size_N = 5000. Si vous le faites, il y a de fortes chances que le code soit déjà optimal et que la bande passante mémoire de votre système soit simplement pas terrible.

Vous pouvez également tester la vitesse si vous résumez tous les éléments de la matrice en une seule boucle au lieu de la multiplication vectorielle matricielle. (Vous voudrez peut-être dérouler la boucle d'un facteur 4, car la non-associativité de l'addition pourrait empêcher le compilateur de faire cette optimisation pour vous.)