RIDISTRIBUZIONE IN BLOCCHI

Nella ridistribuzione in blocchi, le iterazioni di un ciclo vengono assegnate ai vari processi suddividendole in n parti o sottogruppi, essendo n il numero di processi che devono essere eseguiti in parallelo. Le iterazioni appartenenti a ciascun sottogruppo sono consecutive in termini della variabile indice del ciclo. Per esempio se il codice deve eseguire un ciclo di 100 iterazioni, il processo 0 eseguirà le iterazioni 1-25, il processo 2 le iterazioni 26-50, il processo 3 le iterazioni 51-75 ed infine il processo 4 le iterazioni 76-100. Se il numero di iterazioni non è divisibile per il numero di processi, ci sono vari accorgimenti per distribuire in modo il più possibile bilanciato il lavoro tra i processi attivi.
E' chiaro che questo procedimento di parallelizzazione dei cicli è idealmente scalabile fino a che il numero di processi non supera il numero di iterazioni del ciclo.
Nel parallelizzare un codice, è conveninte per chiarezza e sinteticità o compattezza generare una subroutine che automaticamente calcola il range delle iterazioni da assegnare ad un particolare processo. Chiaramente questa non è una funzione MPI. Vedimo nel seguente esempio una subroutine per gestire la ridistribuzione in blocchi:

subroutine blocchi(nstart,nend,nprocs,mype,istart,iend)
integer nstart, nend, nprocs, mype, istart, iend
integer i1, i2, i3
i1     = nend - nstart + 1
i2     = i1/nprocs
i3     = mod(i1,nprocs)
istart = mype*i2 + nstart + min(mype,i3)
iend   = istart + i2 - 1
if(i3.gt.mype) iend = iend + 1
return
end

dove:

nstart ed nend rappresentano i valori estremi della variabile che indicizza il ciclo
nprocs si riferisce al numero di processi attivi
mype è l'intero identificativo del processo
istart ed iend sono in uscita dalle subroutine gli estermi delle iterazioni assegnate al processo che chiama la subroutine

Supponiamo a questo punto di associare 14 iterazioni di un ciclo (nstart=1, nend=14) a 4 processi (nprocs=4). Dividendo 14(=i1=nstart-nend+1) per il numero di processi (nprocs=4), otteniamo 3(=i2) con resto 2(=i3). A questo punto con la subroutine precedente ai primi 0...(i3-1) processi sono assegnate (i2+1) iterazioni, mentre algi altri processi vengono assegnate solo i2 iterazioni:

ITERAZIONE	1	2	3	4	5	6	7	8	9	10	11	12	13	14
PROCESSO	0	0	0	0	1	1	1	1	2	2	2	3	3	3

Questa ridistribuzione corrisponde ad esprimere il numero di iterazioni i1 come i1=i3*(i2+1)+(nprocs-i3)*i2.

Ovviamente sono possibili anche altri modi di realizzare una ridistribuzione a blocchi. Un altro esempio, meno efficiente, è dato dalla seguente subroutine in cui può accadere che qualche processo rimanga senza lavoro:

subroutine blocchi2(nstart,nend,nprocs,mype,istart,iend)
integer nstart, nend, nprocs, mype, istart, iend
integer i1
i1 = 1 + (nend - nstart)/nprocs
istart = min(mype*i1 + nstart, nend + 1)
iend = min(istart + i1 - 1, nend)
return
end

Con questa subroutine la ridistribuzione dell'esempio precedente diviene:

ITERAZIONE	1	2	3	4	5	6	7	8	9	10	11	12	13	14
PROCESSO	0	0	0	0	1	1	1	1	2	2	2	2	3	3

Prendiamo in cosiderazione ora il seguente esempio di codice seriale da parallelizzare:

      program esempio7seriale
      parameter (n=100)
      integer i, a, sum
      dimension a(n)

      do i=1,n
        a(i) = i
      enddo
      sum = 0
      do i=1,n
        sum = sum + a(i)
      enddo
      write(6,*) 'somma = ', sum
      end

La versione parallelizzata con le iterazioni ridistribuite a blocchi è la seguente:

      program esempio7
      include 'mpif.h'
      parameter (n=100)
      integer nprocs, mype, ierr
      integer istart, iend
      integer i, a, sum, ssum
      dimension a(n)

      call MPI_INIT(ierr)
      call MPI_COMM_SIZE(MPI_COMM_WORLD, nprocs, ierr)
      call MPI_COMM_RANK(MPI_COMM_WORLD, mype, ierr)
      call blocchi(1,n,nprocs,mype,istart,iend)

      do i=istart,iend
        a(i) = i
      enddo
      sum = 0
      do i=istart,iend
        sum = sum + a(i)
      enddo

call MPI_REDUCE(sum,ssum,1,MPI_INTEGER,MPI_SUM,
+ 0,MPI_COMM_WORLD,ierr)

      if(mype.eq.0) then
      write(6,*) 'somma = ', ssum
      endif
      call MPI_FINALIZE(ierr)
      end

      subroutine blocchi(nstart,nend,nprocs,mype,istart,iend)
      integer nstart, nend, nprocs, mype, istart, iend
      integer i1, i2, i3
      i1     = nend - nstart + 1
      i2     = i1/nprocs
      i3     = mod(i1,nprocs)
      istart = mype*i2 + nstart + min(mype,i3)
      iend   = istart + i2 - 1
      if(i3.gt.mype) iend = iend + 1
      return
      end