Comment dire à OpenMP de ne paralléliser qu'une fonction dans une boucle for?

Question

Je viens de m'enseigner un peu OpenMP et cela pourrait être stupide. Fondamentalement, j'essaie de paralléliser un premier programme de recherche de grande envergure en C++, chaque nœud prenant beaucoup de temps à traiter. Voici un exemple de code:

queue<node*> q; 
q.push(head); 
while (!q.empty()) { 
    qSize = q.size(); 
    for (int i = 0; i < qSize; i++) { 
    node* currNode = q.front(); 
    q.pop(); 
    doStuff(currNode); 
    q.push(currNode); 
    } 
} 

La fonction de traitement doStuff() est assez cher et je veux paralléliser. Cependant, si je parallélise la boucle for en mettant #pragma omp parallel for juste avant la ligne for, toutes sortes d'erreurs bizarres apparaissent à l'exécution. Je suppose que la raison est que de cette façon q.front() et q.push() sera également parallélisé, et plusieurs threads auront probablement le même nœud par q.front() (parce qu'ils ont tous été traités avant que tout q.push a été traité).

Comment puis-je contourner le problème?

Answer 1

La solution consiste à protéger l'accès à la file d'attente avec une section critique.

queue<node*> q; 
q.push(head); 
while (!q.empty()) { 
    qSize = q.size(); 
    #pragma omp parallel for 
    for (int i = 0; i < qSize; i++) { 
    node* currNode; 
    #pragma omp critical 
    { 
     currNode = q.front(); 
     q.pop(); 
    } 
    doStuff(currNode); 
    #pragma omp critical 
    q.push(currNode); 
    } 
} 

Ceci est similaire au fait d'avoir un mutex commun et de le verrouiller.

Cette version présente certaines limites d'efficacité: À la fin de la boucle for, certains threads peuvent être inactifs, même si le travail est dans la file d'attente. Faire une version où les threads fonctionnent en permanence quand il y a quelque chose dans la file d'attente est un peu compliqué en termes de gestion des situations où la file d'attente est vide mais certains threads sont toujours calculés.

En fonction de la taille des données impliquées dans un noeud, vous pouvez également avoir un impact significatif sur les performances des effets de cache et du partage erroné. Mais cela ne peut pas être discuté avec un exemple spécifique. La version simple sera probablement suffisamment efficace dans de nombreux cas, mais obtenir des performances optimales peut devenir arbitrairement complexe.

Dans tous les cas, vous devez vous assurer que doStuff ne modifie aucun état global ou partagé.