boucles nestedes, parallélisation de boucle interne, réutilisation de threads

Clause de non-responsabilité: l’exemple suivant n’est qu’un exemple factice pour comprendre rapidement le problème. Si vous pensez à un problème du monde réel, pensez à toute programmation dynamic.

Le problème: nous avons une masortingce n * m et nous voulons copier les éléments de la ligne précédente comme dans le code suivant:

for (i = 1; i < n; i++) for (j = 0; j < m; j++) x[i][j] = x[i-1][j]; 

Approche: les itérations de la boucle extérieure doivent être exécutées dans l’ordre, elles seraient exécutées de manière séquentielle. La boucle intérieure peut être parallélisée. Nous souhaitons minimiser les frais généraux liés à la création et à la suppression de threads. Nous souhaitons donc créer une seule équipe de threads. Toutefois, cela semble être une tâche impossible dans OpenMP.

 #pragma omp parallel private(j) { for (i = 1; i < n; i++) { #pragma omp for scheduled(dynamic) for (j = 0; j < m; j++) x[i][j] = x[i-1][j]; } } 

Lorsque nous appliquons l’option ordered sur la boucle externe, le code sera exécuté de manière séquentielle, de sorte qu’il n’y aura aucun gain de performance. Je cherche une solution pour le scénario ci-dessus, même si je devais utiliser une solution de contournement.

J’ajoute mon code actuel. C’est en fait plus lent que seq. version. S’il-vous-plaît évaluez:

 /* load input */ for (i = 1; i <= n; i++) scanf ("%d %d", &in[i][W], &in[i][V]); /* init */ for (i = 0; i <= wc; i++) a[0][i] = 0; /* compute */ #pragma omp parallel private(i,w) { for(i = 1; i <= n; ++i) // 1 000 000 { j=i%2; jn = j == 1 ? 0 : 1; #pragma omp for for(w = 0; w <= in[i][W]; w++) // 1000 a[j][w] = a[jn][w]; #pragma omp for for(w = in[i][W]+1; w <= wc; w++) // 350 000 a[j][w] = max(a[jn][w], in[i][V] + a[jn][w-in[i][W]]); } } 

En ce qui concerne la mesure, j’utilise quelque chose comme ceci:

 double t; t = omp_get_wtime(); // ... t = omp_get_wtime() - t; 

Pour résumer la parallélisation dans OpenMP pour ce cas particulier: cela ne vaut pas la peine.

Pourquoi? Les opérations dans les boucles internes sont simples. Le code a été compilé avec -O3 , donc l’appel max() a probablement été remplacé par le code du corps de la fonction. La surcharge de la barrière implicite est probablement suffisamment élevée pour compenser le gain de performances, et la surcharge globale est suffisamment élevée pour rendre le code parallèle encore plus lent que le code séquentiel. J’ai également découvert qu’il n’y a pas de réel gain de performance dans une telle construction:

 #pragma omp parallel private(i,j) { for (i = 1; i < n; i++) { #pragma omp for for (j = 0; j < m; j++) x[i][j] = x[i-1][j]; } } 

parce que sa performance est similaire à celle-ci

 for (i = 1; i < n; i++) { #pragma omp parallel for private(j) for (j = 0; j < m; j++) x[i][j] = x[i-1][j]; } 

grâce au thread intégré réutilisant dans GCC libgomp , selon cet article: http://bisqwit.iki.fi/story/howto/openmp/

Étant donné que la boucle externe ne peut pas être parallélisée (sans option ordered ), il semble impossible d'améliorer de manière significative les performances du programme en question à l'aide d'OpenMP. Si quelqu'un estime que j'ai fait quelque chose de mal et que c'est possible, je serai heureux de voir et de tester la solution.