La parallélisation OpenMP la matrice de multiplication par un triple boucle for (problème de performance)
Je suis en train d'écrire un programme de multiplication de matrice avec OpenMP, qui, pour le cache de commodité, met en œuvre la multiplication de A x B(transpose) rangées X lignes au lieu de la classique de A x B lignes x colonnes, pour une meilleure efficacité de la mémoire cache. Faisant cela, j'ai fait face à un fait intéressant que pour moi, c'est illogic: si, dans ce code, je l'ai paralléliser le extern boucle le programme est plus lent que si je mets les directives OpenMP dans la plus à l'intérieur de la boucle, dans mon ordinateur les temps sont de 10,9 vs 8,1 secondes.
//A and B are double* allocated with malloc, Nu is the lenght of the matrixes
//which are square
//#pragma omp parallel for
for (i=0; i<Nu; i++){
for (j=0; j<Nu; j++){
*(C+(i*Nu+j)) = 0.;
#pragma omp parallel for
for(k=0;k<Nu ;k++){
*(C+(i*Nu+j))+=*(A+(i*Nu+k)) * *(B+(j*Nu+k));//C(i,j)=sum(over k) A(i,k)*B(k,j)
}
}
}
En jouant sur omp paramètres j'ai 200% de la vitesse sur ma machine. original: llcomp.googlecode.com/hg/examples/mxm.c: codepad.org/nSfZHp03
Solution sympa. Ouais, OpenMP est un peu délicat
Le Code qui utilise
Avez-vous évalué votre Gflops/s? Il devrait être de 2,0*n^3/heure. Comparez cela avec le max pour votre PROCESSEUR: fréquence * (SIMD_width)* (2 ILP) * (nombre de cœurs). e.g sur mon 2600k c'est (4GHz) * 4(AVX) * 2 (ILP) * 4 carottes = 128 DP Gflops/s. Probablement, votre efficacité est inférieure à 10%.
Solution sympa. Ouais, OpenMP est un peu délicat
Le Code qui utilise
'fortran'
disposition de la mémoire pour le B
matrice fonctionne 4-8 plus rapide (le plus grand bénéfice) pour 1000x1000 matrices (version filetée prend 0.5
secondes). gist.github.com/790865Avez-vous évalué votre Gflops/s? Il devrait être de 2,0*n^3/heure. Comparez cela avec le max pour votre PROCESSEUR: fréquence * (SIMD_width)* (2 ILP) * (nombre de cœurs). e.g sur mon 2600k c'est (4GHz) * 4(AVX) * 2 (ILP) * 4 carottes = 128 DP Gflops/s. Probablement, votre efficacité est inférieure à 10%.
OriginalL'auteur sdffadsf | 2011-01-18
Vous devez vous connecter pour publier un commentaire.
Essayer de frapper le résultat de moins en moins souvent. Ceci induit cacheline de partage et empêche le fonctionnement à partir de l'exécution en parallèle. À l'aide d'une variable locale au lieu de cela va permettre à la plupart de l'écrit à prendre place dans chaque cœur du cache L1.
Aussi, l'utilisation de
restrict
peut aider. Sinon le compilateur ne peut pas garantir que écrit àC
ne changent pasA
etB
.Essayer:
Aussi, je pense que Elalfer est à droite sur la nécessité de réduction si vous paralléliser les recoins les plus profonds de la boucle.
Incredibile, le temps est devenu seulement 4,2 s avec le plus à l'intérieur de la boucle et 4.4 avec la plus externe (!), alors que le code avec #pragma comme dans le code que vous avez posté, le temps est >le 17, je ne sais pas pourquoi. merci vraiment à tous, même si c'est ne pas comprendre pourquoi avec la plus externe est légèrement plus lente que la plupart des intérieurs
Vérifier les résultats, vous ne pouvez pas avoir le droit de sortie lors de la parallélisation de l'intime boucle sans spécification d'une réduction de fonctionnement.
oui, vous avez raison, même sur ce. J'ai commis plusieurs erreurs pendant le programme, et votre proposition est correcte, avec la réduction de l'intérieure de travaux (4,2 s), mais la plus externe est la plus efficace (3,9 s!), alors que la centrale est très lente, d'environ 20 ans, je pense que c'est dû à la cacheline (l'adresse varie avec j'ai très vite), alors le paradoxe apparent est révélé, demain matin, j'ai l'examen scientifique de la programmation...merci encore à vous et Elalfer
il y a une faute de frappe dans
Bcol = B + i*Nu
il devrait êtrej
.OriginalL'auteur Ben Voigt
Vous pourriez probablement avoir des dépendances dans les données lorsque vous paralléliser la boucle externe et le compilateur n'est pas capable de le comprendre, et ajoute des serrures supplémentaires.
Très probablement, il décide qu'externes différentes itérations de boucle pourrait écrire dans le même
(C+(i*Nu+j))
et il ajoute accès serrures pour les protéger.Compilateur pourrait probablement trouver qu'il n'y a pas de dépendances si vous allez paralléliser la 2ème boucle. Mais à comprendre qu'il n'y a pas de dépendances de la parallélisation de la boucle externe n'est pas si anodin pour un compilateur.
Mise à JOUR
Certaines mesures de rendement.
Salut à nouveau. Il ressemble à 1000 double
*
et+
n'est pas suffisant pour couvrir le coût de threads synchronisation.J'ai fait quelques petits tests et simple vecteur scalaire de la multiplication n'est pas efficace avec openmp, sauf si le nombre d'éléments est inférieur à ~10'000. En gros, plus votre tableau, plus le rendement que vous obtenez de l'aide d'openmp.
Afin de paralléliser le plus à l'intérieur de la boucle, vous aurez pour séparer les tâches entre les différents threads et de recueillir des données 1'000'000 de fois.
PS. Essayez Intel de la CPI, c'est un peu gratuit pour les étudiants et les projets open source. Je me souviens avoir été en utilisant openmp pour les petits que 10'000 éléments des tableaux.
Mise à JOUR 2: exemple de Réduction des
Vous pouvez le voir, mais le compilateur n'est pas une IA et pourrait passer à côté 😉 j'ai eu beaucoup de batailles avec OpenMP & icc relatives à ce genre de choses.
désolé pour mon arrogance, vous êtes sûrement plus expert que moi, je vais vérifier. Si je paralléliser la deuxième boucle, le résultat est plus que de 15 secondes.
Un avis: Avez-vous essayé d'utiliser
reduction
clause pour la plupart à l'intérieur de la boucle? Je vais essayer ce code plus tard. Il ressemble à du plaisir à se rappeler comment travailler avec OpenMP. Le compilateur que vous utilisez? gcc ou de la cpi? Et quelle est la taille de votre matrice?si vous voulez je peux vous envoyer mon code.La matrice est grande (1000x1000). Je ne vois pas d'espace pour l'utilisation de la réduction (C est un pointeur), dans la boucle externe, vous ne pouvez pas l'utiliser dans tous les cas (ce que vous reduc?). Le problème est que je suis ne suis pas un ingénieur en informatique, je ne sais pas comment la mémoire de l'ordinateur "travaille" dans un sens physique, je sais comment utiliser la ligne de mémoire cache, et comme vous pouvez le voir, j'ai utilisé cette information pour la multiplication des lignes de x lignes, mais mes connaissances s'arrête ici. Pour moi le problème est dans l'utilisation de la mémoire cache, seulement cette fonction permet d'ajouter tout ce temps à s'exécuter. Merci pour la réponse, je suis impatient de vos idées
OriginalL'auteur Elalfer