Descomposició recursiva

Quan treballem amb algoritmes divide-and-conquer, també podem paral·lelitzar la generació i execució de tasques de forma recursiva. Hi ha dues estratègies principals: Leaf i Tree.

Leaf Strategy

En l’estratègia Leaf, un únic thread (master) recorre seqüencialment l’arbre de recursió. Quan arriba a un cas base (fulla), crea una tasca explícita perquè sigui executada per qualsevol thread lliure del team. Per tant, les tasques es creen només a les fulles!

▣Arbre de recursió de $n = 1024$ fins a $n = 64$: el master thread el recorre en profunditat (DFS) i crea una tasca a cada fulla. (figura al dossier, p. 24)

Passos per paral·lelitzar:

1. Regió paral·lela i creació de tasques: obrim una regió parallel amb single perquè un sol thread recorri l’arbre.

   #pragma omp parallel
   #pragma omp single
   crida_recursiva(...)

2. Creem tasques en el cas base de la recursió usant #pragma omp task.

   crida_recursiva() {
       if (cond) {
           #pragma omp task
           {
               cas_base();
           }
       }
       else crida_recursiva();
   }

3. Data race conditions: la variable global de resultat és compartida i modificada per totes les tasques ⇒ cal protegir-la.

4. Sincronització: afegim #pragma omp taskwait per assegurar que totes les tasques han acabat abans de consumir el resultat.

   #pragma omp parallel
   #pragma omp single
   crida_recursiva(...)
   #pragma omp taskwait
   // Valor de result correcte

Problemes de l’estratègia Leaf:

• Si baixem fins a molta profunditat podem arribar a tenir moltes tasques (una per cada fulla ⇒ $2^{\text{profunditat}}$ tasques, de mida $N/2^{\text{profunditat}}$ cadascuna).
• Un sol thread s’encarrega de crear totes les tasques ⇒ molt overhead de creació concentrat en un únic thread.
• Si la granularitat de les tasques és molt petita ⇒ s’executen les tasques molt més ràpid del que es creen, provocant que els threads quedin inactius esperant.
• Si recórrer l’arbre és car, es concentrarà molta càrrega de feina en un únic thread mentre els altres estaran esperant que els arribi la feina ⇒ load imbalance.

Leaf amb cut-off

Per reduir l’overhead de creació de tasques i el temps que un únic thread dedica a recórrer l’arbre, introduïm un cut-off per profunditat. A partir d’un cert nivell (CUTOFF), el thread creador deixa de baixar seqüencialment i crea una tasca que assumeix la continuació de la recursió de manera independent. Això reparteix el recorregut (i la creació de tasques) entre múltiples threads.

▣Estratègia Leaf amb cut-off: a partir de la profunditat de tall ($d = 2$), el thread creador deixa de recórrer seqüencialment i genera noves tasques que continuen la recursió de manera independent. (figura al dossier, p. 25)

Quan depth == CUTOFF, es crea una tasca que encapsula la recursió del subarbre a partir d’aquell node. Dins d’aquesta tasca, la recursió continua seqüencialment fins arribar al cas base. A partir d’aquest punt, el cas base s’executa dins la mateixa tasca (no cal crear cap altra tasca «de continuació» perquè ja som dins del subarbre delegat).

Cal tenir en compte que, si s’arriba al cas base amb depth < CUTOFF, encara s’ha de crear la tasca explícita del cas base (tal com fèiem en l’estratègia Leaf original).

Tree Strategy

En l’estratègia Tree, cada crida recursiva crea una nova tasca, que al seu torn generarà més crides i, per tant, més tasques. Hi ha tasques que només creen tasques (nodes interns) i d’altres que només executen el cas base (fulles).

▣Arbre de recursió de $n = 1024$ fins a $n = 64$ amb una tasca a cada node. (figura al dossier, p. 26)

Passos per paral·lelitzar: la funció recursiva ha de retornar el resultat parcial (o bé escriure’l en variables locals del pare) en lloc d’acumular-lo en una variable global. Així, la reducció és natural a cada nivell.

1. Regió paral·lela: es fa la primera crida dins parallel + single.

   #pragma omp parallel
   #pragma omp single
   result = rec(...);

2. Tasques recursives: cada crida als fills es crea amb #pragma omp task i escriu en una variable del pare (shared).

3. Data races: no hi ha conflicte entre tasques germanes perquè cadascuna escriu en una variable diferent (tmp1, tmp2) del pare.

4. Sincronització: taskwait és necessari abans de combinar (tmp1 + tmp2); si no, podríem estar retornant un resultat parcial que encara no sigui vàlid.

   int rec(...) {
       int tmp1 = 0, tmp2 = 0;
   
       if (cond) return cas_base(...);
       else {
           #pragma omp task shared(tmp1)
           tmp1 = rec(... left ...);
   
           #pragma omp task shared(tmp2)
           tmp2 = rec(... right ...);
   
           #pragma omp taskwait
           return tmp1 + tmp2;
       }
   }

Problemes de l’estratègia Tree:

• Es creen tasques a tots els nivells ⇒ el nombre total pot ser enorme: $2^{d+1} - 1$.
• Per tant, el cost dels overheads de creació, gestió i sincronització pot arribar a ser enorme.
• Amb granularitat massa fina, el programa pot dedicar més temps a gestionar tasques que a executar-les.

Tree amb cut-off

A partir d’un cert nivell (CUTOFF), es deixa de crear tasques i la branca restant s’executa seqüencialment (tant casos recursius com base).

▣Estratègia Tree amb cut-off: es creen tasques a cada nivell per sobre del tall. Per sota, cada tasca continua la recursió de manera seqüencial sense generar noves tasques. (figura al dossier, p. 27)

Control de cut-off amb final i omp_in_final

OpenMP proporciona un mecanisme integrat per controlar el cut-off sense necessitat de gestionar manualment la profunditat amb un if-else:

• #pragma omp task final(condició): si la condició és certa, la tasca es marca com a final. Una tasca final s’executa immediatament pel thread que la crea (sense afegir-la a la pool), i totes les tasques filles generades dins d’una tasca final també s’executen immediatament (és a dir, de forma seqüencial).
• omp_in_final(): retorna true si la tasca actual s’està executant en un context final. Permet decidir, en temps d’execució, si cal crear més tasques o continuar seqüencialment.

La clàusula final(depth >= CUTOFF) marca la tasca com a final quan s’assoleix la profunditat de tall. A partir d’aquell punt, la crida a omp_in_final() retorna cert i s’executa la branca seqüencial, evitant la creació de noves tasques.