Fusion d’une boucle sortingangular pour la parallélisation, calcul de sous-indices

Une technique courante en parallélisation consiste à fusionner des boucles nestedes comme celle-ci.

for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { 

à

 for(int x=0; x<n*n; x++) { int i = x/n; int j = x%n; 

Je me demande comment je peux faire cela pour fondre une boucle en sortingangle comme celle-ci

 for(int i=0; i<n; i++) { for(int j=0; j<i+1; j++) { 

Cela a n*(n+1)/2 itérations. Appelons l’itération fusionnée x . En utilisant la formule quadratique, j’ai trouvé ceci:

 for(int x=0; x<(n*(n+1)/2); x++) { int i = (-1 + sqrt(1.0+8.0*x))/2; int j = x - i*(i+1)/2; 

Contrairement à la fusion de la boucle carrée, cela nécessite l’utilisation de la fonction sqrt et des conversions d’intol en float et de float en int.

Je me demande s’il existe un moyen plus simple ou plus efficace de procéder. Par exemple, une solution ne nécessitant pas la fonction sqrt ou les conversions de int en float ou de float en int.

Edit: Je ne veux pas de solution qui dépend des itérations précédentes ou suivantes. Je veux seulement des solutions comme int i = funci(x) and int j = funcj(x,i)

Voici un code montrant que cela fonctionne:

 #include  #include  int main() { int n = 5; int cnt = 0; for(int i=0; i<n; i++) { for(int j=0; j<i+1; j++) { printf("%d: %d %d\n", cnt++, i,j); } } printf("\n"); int nmax = n*(n+1)/2; for(int x=0; x<nmax; x++) { int i = (-1 + sqrt(1.0+8.0*x))/2; int j = x - i*(i+1)/2; printf("%d: %d %d\n", x,i,j); } } 

Étant donné que vous essayez de fusionner un sortingangle dans le but de paralléliser, la solution non évidente consiste à choisir un mappage non sortingvial de x vers (i, j):

 j |\ i -> | \ ____ | | \ => |\\ | V |___\ |_\\__| 

Après tout, vous ne les traitez pas dans un ordre spécial, le mappage exact est donc sans importance.

Calculez donc x->i,j comme vous le feriez pour un rectangle, mais si i > j alors { i=Ni, j = Nj } (axe Y du miroir, puis axe X du miroir).

  ____ |\\ | |\ |\ |_\\__| ==> |_\ __ => | \ / | | \ /__| |___\ 

La forme la plus saine est bien sûr la première forme.

Cela dit, la forme fusionnée est mieux faite avec les conditionnels:

 int i = 0; int j = 0; for(int x=0; x<(n*(n+1)/2); x++) { // ... ++j; if (j>i) { j = 0; ++i; } } 

Je me demande s’il existe un moyen plus simple ou plus efficace de procéder.

Oui, le code par lequel vous deviez commencer. Veuillez garder ceci à l’esprit:

  • Il n’existe aucun cas où l’arithmétique en virgule flottante est jamais plus rapide que des entiers simples.
  • Il existe cependant de nombreux cas où la virgule flottante est beaucoup plus lente que les entiers ordinaires. FPU ou pas de FPU.
  • Les variables float sont généralement plus grandes que les entiers ordinaires sur la plupart des systèmes et sont donc plus lentes pour cette seule raison.
  • La première version du code est probablement la plus conviviale pour la mémoire cache. Comme pour tout cas d’optimisation manuelle, cela dépend entièrement de la CPU que vous utilisez.
  • La division est généralement lente sur la plupart des systèmes, peu importe qu’il s’agisse de simples entiers ou de flottants.
  • Toute forme d’arithmétique complexe sera plus lente que le simple comptage.

Ainsi, votre deuxième exemple est quasiment garanti d’être beaucoup plus lent que le premier exemple, quel que soit le processeur utilisé dans le monde. En outre, il est également complètement illisible.