Fil parallèle OpenMP

Je dois paralléliser cette boucle, je pensais que l’utiliser était une bonne idée, mais je ne l’avais jamais étudiée auparavant

#pragma omp parallel for for(std::set::const_iterator it=mesh->NEList[vid].begin(); it!=mesh->NEList[vid].end(); ++it){ worst_q = std::min(worst_q, mesh->element_quality(*it)); } 

Dans ce cas, la boucle n’est pas parallélisée car elle utilise un iterator et le compilateur ne peut pas comprendre comment la couper.

Pouvez-vous m’aider?

OpenMP requirejs que le prédicat de contrôle en parallèle for boucles comporte l’un des opérateurs relationnels suivants: < , <= , > ou >= . Seuls les iterators à access aléatoire fournissent ces opérateurs et, par conséquent, les boucles parallèles OpenMP fonctionnent uniquement avec des conteneurs fournissant des iterators à access aléatoire. std::set ne fournit que des iterators bidirectionnels. Vous pouvez surmonter cette limitation en utilisant des tâches explicites. La réduction peut être effectuée en réduisant d'abord partiellement les variables privées sur chaque thread, puis en réduisant globalement les valeurs partielles.

 double *t_worst_q; // Cache size on x86/x64 in number of t_worst_q[] elements const int cb = 64 / sizeof(*t_worst_q); #pragma omp parallel { #pragma omp single { t_worst_q = new double[omp_get_num_threads() * cb]; for (int i = 0; i < omp_get_num_threads(); i++) t_worst_q[i * cb] = worst_q; } // Perform partial min reduction using tasks #pragma omp single { for(std::set::const_iterator it=mesh->NEList[vid].begin(); it!=mesh->NEList[vid].end(); ++it) { size_t elem = *it; #pragma omp task { int tid = omp_get_thread_num(); t_worst_q[tid * cb] = std::min(t_worst_q[tid * cb], mesh->element_quality(elem)); } } } // Perform global reduction #pragma omp critical { int tid = omp_get_thread_num(); worst_q = std::min(worst_q, t_worst_q[tid * cb]); } } delete [] t_worst_q; 

(Je suppose que mesh->element_quality() retourne double )

Quelques points clés:

  • La boucle est exécutée en série par un seul thread, mais chaque itération crée une nouvelle tâche. Ceux-ci sont probablement mis en queue pour être exécutés par les threads inactifs.
  • Les threads inactifs qui attendent à la barrière implicite de la construction single commencent à consumr des tâches dès leur création.
  • La valeur indiquée par it - it est déréférencée devant le corps de la tâche. En cas de déréférence dans le groupe de tâches, it s'agirait du premier firstprivate et une copie de l'iterator serait créée pour chaque tâche (c'est-à-dire à chaque itération). Ce n'est pas ce que tu veux.
  • Chaque thread effectue une réduction partielle dans sa partie privée du t_worst_q[] .
  • Afin d'éviter toute dégradation des performances due à un faux partage, les éléments de t_worst_q[] auxquels chaque access accède sont espacés de manière à se retrouver dans des lignes de cache distinctes. Sur x86 / x64, la ligne de cache est de 64 octets. Par conséquent, le nombre de threads est multiplié par cb = 64 / sizeof(double) .
  • La réduction worst_q globale est effectuée à l'intérieur d'une construction critical afin d'empêcher worst_q plusieurs threads worst_q à worst_q . Ceci est uniquement à des fins d'illustration car la réduction pourrait également être effectuée par une boucle dans le fil principal après la région parallèle.

Notez que les tâches explicites nécessitent un compilateur prenant en charge OpenMP 3.0 ou 3.1. Cela exclut toutes les versions du compilateur Microsoft C / C ++ (il ne prend en charge que OpenMP 2.0).

Conteneur à access aléatoire

La solution la plus simple consiste à tout jeter dans un conteneur à access aléatoire (comme std::vector ) et à utiliser les boucles basées sur un index privilégiées par OpenMP:

 // Copy elements std::vector neListVector(mesh->NEList[vid].begin(), mesh->NEList[vid].end()); // Process in a standard OpenMP index-based for loop #pragma omp parallel for reduction(min : worst_q) for (int i = 0; i < neListVector.size(); i++) { worst_q = std::min(worst_q, complexCalc(neListVector[i])); } 

En plus d'être incroyablement simple, selon votre situation (minuscules éléments de type size_t pouvant être facilement copiés), c'est également la solution offrant les meilleures performances et la meilleure évolutivité.

Éviter les copies

Cependant, dans une situation différente de la vôtre, il se peut que des éléments ne soient pas copiés aussi facilement (éléments plus grands) ou ne puissent pas être copiés du tout. Dans ce cas, vous pouvez simplement placer les pointeurs correspondants dans un conteneur à access aléatoire:

 // Collect pointers std::vector neListVector; for (const auto &entry : mesh->NEList[vid]) { neListVector.push_back(&entry); } // Process in a standard OpenMP index-based for loop #pragma omp parallel for reduction(min : worst_q) for (int i = 0; i < neListVector.size(); i++) { worst_q = std::min(worst_q, mesh->element_quality(*neListVector[i])); } 

Ceci est légèrement plus complexe que la première solution, a toujours les mêmes bonnes performances pour les petits éléments et des performances accrues pour les plus gros éléments.

Tâches et ordonnancement dynamic

Étant donné que quelqu'un d'autre a évoqué les tâches OpenMP dans sa réponse, je souhaite faire un commentaire à ce sujet. Les tâches sont une construction très puissante, mais elles ont une charge énorme (qui augmente même avec le nombre de threads) et dans ce cas, rendent les choses plus complexes.

Pour la réduction min l'utilisation de Tasks n'est jamais justifiée car la création d'une Task dans le thread principal coûte beaucoup plus cher que de simplement faire std::min lui-même!

Pour l'opération plus complexe mesh->element_quality vous pouvez penser que la nature dynamic de Tasks peut vous aider à résoudre les problèmes d'équilibrage de charge, dans le cas où le temps d'exécution de mesh->element_quality varie considérablement entre les itérations et si vous n'en avez pas assez pour l'égaliser. Mais même dans ce cas, il existe une solution plus simple: utilisez simplement la planification dynamic en ajoutant la directive schedule(dynamic) à votre ligne parallel for ligne dans l’une de mes solutions précédentes. Il obtient le même comportement, mais beaucoup moins de frais généraux.