OpenMP pour les boucles imbriquées?

Question

J'essaie d'utiliser OpenMP dans mon projet qui contient N agents dans une simulation. Chaque agent a un vecteur de position. A l'intérieur de mon programme, je fais quelque chose comme ce qui suit:

for(int i=0;i<agents.size();i++){ 
for(int j=0;j<agents.size();j++){ 
    if(i==j) continue; 
    if(distance_between(i,j)<10){ 
    //do a lot of calculations for interaction between i and j, 
    //and a bunch of changes to variables of the Agents stored in the list 
    } 
} 
} 

Suis-je capable de simplement préfixer « #pragma omp parallèle » en face de la première boucle pour distribuer le travail? Si je le fais, mon programme s'exécute beaucoup plus rapidement, mais je crains que les calculs qu'il effectue ne soient pas exacts. L'ordre de ces calculs n'a pas d'importance, tant que chaque paire i, j est traitée, et aucune variable en dehors des variables définies à l'intérieur de la boucle la plus interne, et les variables de ma classe Agents sont toujours modifiées (seulement lues).

N'étant pas un type de système J'ai du mal à comprendre les rouages ​​internes d'OpenMP, et je m'en mets un peu en doute. Merci pour toute aide concernant ceci!

Answer 1

Oui, l'ajout du pragma serait correct. La mémoire est considérée implicitement partagée par tous les threads. Cela ne veut pas dire que cela fonctionnera plus vite. Il y a plusieurs problèmes à prendre en compte:

• combien de processeurs votre système a-t-il?
• utilisez-vous un nombre entier ou un nombre à virgule flottante? Pour l'entier, l'ordre n'aura pas d'importance, mais ce n'est pas le cas pour les virgules flottantes
• quelles sont les variables accessibles uniquement par la boucle la plus interne? Vous pouvez les déclarer privés pour obtenir de meilleures performances.

Answer 2

Suis-je capable de simplement préfixer « #pragma omp parallèle » en face de la première boucle pour distribuer le travail?

Cela dépend de ce que vous feriez en section parallèle. Pour obtenir de meilleures performances, vous pouvez modifier l'algorithme de votre code parallèle plutôt que de simplement ajouter le #pragma omp parallel à votre code de séquence. Rappelez-vous que la clé de la programmation parallèle sont les variables partagées. Dans certains cas, il serait préférable d'utiliser un code de séquence plutôt qu'un code parallèle. Si je le fais, mon programme s'exécute beaucoup plus rapidement, mais je crains que les calculs qu'il effectue ne soient pas exacts. En effet, vous devez vous assurer qu'il n'y a aucune condition de concurrence dans votre code pour obtenir le résultat de calcul correct.

Answer 3

Assurez-vous que les interactions i,j et j,i qui affectent les mêmes données ne provoquent pas de courses de données. Vous pouvez le faire en ajustant soigneusement la distribution de l'œuvre ou en utilisant des constructions omp critical ou omp atomic si nécessaire. En dehors de cela, il n'y a aucun problème à accélérer votre code en utilisant simplement des constructions omp parallel for sur la boucle externe. Gardez à l'esprit que si le nombre d'unités de traitement (cœurs, hwthreads, etc.) de votre processeur, ou si vous utilisez une machine ccNUMA, ce pourrait être une bonne idée de faire des choses supplémentaires, car l'évolutivité de votre code sera ne pas être aussi bon que possible.

L'amélioration la plus simple consiste à ajouter collapse(2) à votre clause omp for.Cela indiquera à OpenMP que vous voulez distribuer les itérations de ces deux boucles complètement.

#pragma omp parallel for collapse(2) 
for(int i=0;i<agents.size();i++){ 
for(int j=0;j<agents.size();j++){ 
    if(i==j) continue; 
    if(distance_between(i,j)<10){ 
    //do a lot of calculations for interaction between i and j, 
    //and a bunch of changes to variables of the Agents stored in the list 
    } 
    } 
} 

Une fois que vous atteignez d'énormes quantités de particules (ou des agents comme vous les appelez), il pourrait être sage de trier tous selon leur position. Cela entraînera un comportement beaucoup plus stable de votre condition if à l'intérieur de la boucle la plus interne, permettant ainsi une meilleure prédiction des branches (voir why is it faster to process a sorted array).

En outre, vous pouvez supprimer complètement la branche si vous divisez l'espace géométrique dans les emplacements. C'est parce que vous savez exactement que les seaux non adjacents sont trop loin pour que la condition réussisse.

Ce type de problème est très connu et, comme vous le savez peut-être déjà, il s'appelle n-body problems. La version d'optimisation de seau est appelée Barnes-Hut simulation, bien que vous puissiez trouver d'autres approches fonctionnant beaucoup plus vite (bien que plus difficiles à paralléliser, toujours plus efficaces la plupart du temps) comme le Fast Multipole Method, qui consiste plus ou moins à réduire le nombre de calculs par résoudre les deux interactions i,j et j,i dans la même étape.