CICLI CONCATENATI

In questa sezione affronteremo solo la parallelizzazione di due cicli concatenati, anche se gli argomenti qui riportati possono essere generalizzati ad un numero maggiore di concatenazioni. Inoltre la tecnica a cui si fa riferimento è solo quella della ridistribuzione a blocchi.

Quando si parallelizzano dei cicli concatenati ci sono due cose da tenere bene in considerazione:

Focalizziamo l'attenzione sul primo punto.
In Fortran, l'ordine di occupazione delle componenti di un vettore multidimensionale occupano la memoria procedendo per colonne; ad esempio per la seguente matrice 3x3 ho esplicitato l'ordine di occupazione delle locazioni di memoria per le componenti A(i,j) con il numero rosso:
 
A(1,1)
1°		 A(1,2)
4°		 A(1,3)
7°
A(2,1)
2°		 A(2,2)
5°		 A(2,3)
8°
A(3,1)
3°		 A(3,2)
6°		 A(3,3)
9°

(in C invece la situazione è opposta).
E' chiaro che è più efficiente accedere alle componenti di questi vettori nell'ordine in cui sono stati memorizzati, in modo da poter leggere il più possibile quello che è già scritto in cache, senza dover richiedere al sistema di rileggere continuamente la memoria e quindi di dover reimportare un dato in cache che non è più presente avendo dovuto fare spazio ad altre componenti non prossime.

Consideriamo quindi questi due cicli doppi concatenati (equivalenti dal punto di vista del risultato):

CICLO 1:
do j=1,n
  do i=1,n
    a(i,j) = b(i,j) + c(i,j)
  enddo
enddo

CICLO 2:
do i=1,n
  do j=1,n
    a(i,j) = b(i,j) + c(i,j)
  enddo
enddo

il ciclo 2, operando successivamente su dati appartenenti a colonne distinte, genera cache misses ed è quindi (in Fortran) meno efficiente.
Nel parallelizzare il ciclo 1, si applicano gli stessi ragionamenti:

CICLO 1A:
do j=istart,iend
  do i=1,n
    a(i,j) = b(i,j) + c(i,j)
  enddo
enddo

CICLO 1B:
do j=1,n
  do i=istart,iend
    a(i,j) = b(i,j) + c(i,j)
  enddo
enddo

Parallelizzando il ciclo più esterno si assegnano intere colonne dei vettori ai vari processi invece di alcune parti come nella parallelizzazione del ciclo più interno; la parallelizzazione 1A è quindi più efficiente perchè genera meno cache misses.

Prendiamo in considerazione ora anche il problema delle comunicazioni tra i vari processi. Ad esempio consideriamo il seguente ciclo doppio concatenato:

CICLO 3:
do j=1,n
  do i=1,n
    a(i,j) = b(i,j-1) + b(i,j+1)
  enddo
enddo

in questo ciclo vi è una dipendenza con gli elementi appartenenti alla stessa riga, ma a colonne adiacenti. In questo caso se si parallelizza il ciclo più esterno, si costringe i vari processi a dover comunicarei dati presenti nelle zone di confine dei blocchi così creati (2n dati da comunicare e 2n dati da ricevere). Se invece si parallelizza (sempre a blocchi) il ciclo più interno, la comunicazione tra i processi non è più necessaria poichè ogni processo possiede già tutti i dati di cui ha bisogno per operare il calcolo; così facendo si andrà incontro a numerosi cache misses, ma poichè i tempi di accesso alla memoria sono molto più rapidi di quelli di comunicazione, la parallelizzazione del ciclo più interno è in questo caso più efficiente.
Se invece la dipendenza esiste sia tra i dati appartenenti a colonne ma anche a righe adiacenti...

CICLO 4:
do j=1,n
  do i=1,m
    a(i,j) = b(i-1,j) + b(i,j-1) + b(i+1,j) + b(i,j+1)
  enddo
enddo

allora la scelta più efficiente della parallelizzazione dipende in modo esplicito dalla lunghezza reciproca dei cicli concatenati. E' sempre possibile comunque parallelizzare entrambi i cicli; ci si muove comunque per minimizzare la comunicazione che è il fattore principale di calo di prestazioni e questo lo si ottiene cercando di minimizzare il perimetro dei blocchi.