Paralléliser un algorithme avec de nombreux points de sortie?

Une possibilité consiste à utiliser OpenMP pour paralléliser les 6 boucles – déclarez logical :: array(6) , laissez chaque boucle s’exécuter complètement, puis retval = any(array) . Ensuite, vous pouvez vérifier cette valeur et retourner en dehors de la boucle parallélisée. Ajoutez une schedule(dynamic) à l’instruction parallèle si vous faites cela. Ou bien, ayez un !$omp parallel et mettez ensuite !$omp do schedule(dynamic) … !$omp end do nowait autour de chacune des 6 boucles.

Ou, vous pouvez suivre les bons conseils de @MSB et paralléliser la boucle la plus externe sur l’ensemble du tableau. Le problème ici est que vous ne pouvez pas avoir un RETURN dans une boucle parallèle – étiquetez donc la deuxième boucle la plus externe (la plus grande dans la partie parallèle), et EXIT cette boucle – tout comme

 retval = .FALSE. !$omp parallel do default(private) shared(BIGARRAY,retval) schedule(dynamic,1) do k=1,NN if(.not. retval) then outer2: do j=1,NN do i=1,NN ! --- your loop #1 do n1=nlo,nhi do o1=olo,ohi if (somecondition(BIGARRAY(i,j,k),n1,o1)) then retval =.TRUE. exit outer2 endif end do end do ! --- your loops #2 ... #6 go here end do end do outer2 end if end do !$omp end parallel do 

[edit: la déclaration if présume que vous devez savoir s’il y a au moins un élément comme celui-ci dans le grand tableau. Si vous devez déterminer la condition de chaque élément, vous pouvez également append une sortie de boucle factice ou un goto, en ignorant le rest du traitement pour cet élément. Encore une fois, utilisez le calendrier (dynamic) ou le programme (guidé).]

En tant que point distinct, vous pouvez également vérifier si cela peut être une bonne idée de passer par la boucle la plus profonde (en fonction de la taille du flottant), calculer un vecteur de logique à chaque itération, puis agréger les résultats, par exemple . smth comme if(count(somecondition(x(o1:o1+step,n1,k)))>0) ; dans ce cas, le compilateur peut être capable de vectoriser somecondition .

Serait-il préférable de paralléliser la boucle sur les éléments du tableau et de laisser cet algorithme en série, avec plusieurs threads exécutant l’algorithme sur différents éléments du tableau? Je pense ceci de votre commentaire “La consommation de temps vient du fait que chaque élément du tableau doit être testé comme ceci. Les tableaux ont généralement entre quatre et vingt millions d’éléments.” La conception de la mise en œuvre de la parallélisation des éléments du tableau est également flexible en termes de nombre de threads. À moins qu’il y ait une raison pour laquelle les éléments du tableau doivent être vérifiés dans un certain ordre?

Il semble que la partie que vous nous montrez ne soit pas trop longue pour être exécutée, donc cela prend moins de temps en le rendant parallèle peut-être pas facile … il y a toujours un peu de temps pour plusieurs threads beaucoup de temps pour gagner, le code parallèle peut ne pas être plus rapide.

Je crois que vous pouvez faire ce que vous voulez avec la structure de tâche introduite dans OpenMP 3; Intel Fortran prend en charge les tâches dans OpenMP. Je n’utilise pas souvent de tâches, donc je ne vais pas vous proposer de pseudo-code.

Vous avez déjà mentionné le moyen évident d’arrêter tous les threads dès qu’un thread trouve la condition de fin: vérifiez chaque variable partagée qui donne l’état de la condition de fin, déterminant ainsi s’il faut sortir des boucles. Évidemment, il s’agit d’un surcoût, alors si vous décidez de suivre cette approche, je suggérerais quelques choses:

1. Utilisez atomics pour vérifier la condition de fin, cela évite le vidage de mémoire coûteux car seule la variable en question est vidée. Déplacer vers OpenMP 3.1, il y a quelques nouvelles opérations atomiques supscopes.

2. Vérifiez rarement, peut-être comme une fois par itération externe. Vous ne devriez paralléliser que des cas importants pour surmonter le surcoût du multithreading.

3. Celui-ci est facultatif, mais vous pouvez essayer d’append des conseils de compilation, par exemple si vous vous attendez à ce que certaines conditions soient fausses la plupart du temps, le compilateur optimisera le code en conséquence.

Une autre approche (quelque peu sale) consiste à utiliser des variables partagées pour les plages de boucles pour chaque thread, peut-être utiliser un tableau partagé où index n est destiné au thread n. Lorsqu’un thread trouve la condition de fin, il modifie les plages de boucle de tous les autres threads pour qu’ils s’arrêtent. Vous aurez besoin de la synchronisation de mémoire appropriée. Fondamentalement, la surcharge est passée de la vérification d’une variable factice à la synchronisation / vérification des conditions de la boucle. Encore une fois, probablement pas si bon de faire cela fréquemment, donc peut-être utiliser des variables de boucles externes partagées et des variables de boucles internes privées.

Sur une autre note, cela me rappelle le problème classique d’interrogation ou d’interruption. Malheureusement, je ne pense pas qu’OpenMP supporte les interruptions où vous pouvez envoyer une sorte de signal de suppression à chaque thread.

Il existe des solutions de contournement telles que l’utilisation d’un processus enfant pour ce travail parallèle et l’appel du planificateur du système d’exploitation pour émuler les interruptions, mais cela est plutôt difficile à corriger et rendrait votre code extrêmement difficile à transporter.

Mise à jour en réponse à un commentaire:

Essayez quelque chose comme ça:

 char shared_var = 0; #pragma omp parallel { //you should have some method for setting loop ranges for each thread for (n1=nlo; n1<=nhi; n1++) { for (o1=olo; o1<=ohi; o1++) { if (somecondition(n1,o1)!=0) { #pragma omp atomic write shared_var = 1; //done marker, this will also trigger the other break below break; //could instead use goto to break out of both loops in 1 go } } #pragma omp atomic read private_var = shared_var; if (private_var!=0) break; } } 

Une approche parallèle appropriée pourrait consister à laisser chaque travailleur examiner une partie du problème global, exactement comme dans le cas de la série et à utiliser une variable locale (non partagée) pour le résultat (retval). Enfin, réduisez tous les travailleurs sur ces variables locales en un résultat global partagé.