2015-12-27 12 views
6

In questo link, l'autore fornisce un esempio comeCome evitare Condizionali in Loops

subroutine threshold(a, thresh, ic) 
    real, dimension(:), intent(in) :: a 
    real, intent(in) :: thresh 
    integer, intent(out) :: ic 
    real :: tt 
    integer :: n 

    ic = 0 
    tt = 0.d0 
    n = size(a) 
    do j = 1, n 
    tt = tt + a(j) * a(j) 
    if (sqrt(tt) >= thresh) then 
     ic = j 
     return 
    end if 
    end do 
end subroutine threshold 

e l'autore ha commentato questo codice come

Un approccio alternativo, che consentirebbe molte ottimizzazioni (srotolamento del loop, pipelining della CPU, meno tempo impiegato per valutare il condizionale ) implicherebbe l'aggiunta di tt in blocchi (ad esempio, blocchi di dimensioni 128) e controllare il condizionale dopo ogni blocco. Quando viene soddisfatta la condizione , è possibile ripetere l'ultimo blocco per determinare il valore di ic.

Che cosa significa? ciclo di svolgimento? Pipelining della CPU? aggiungendo tt in blocchi?

Come ottimizzare il codice come dice l'autore?

+2

Bene, penso che la prima cosa da fare sia sostituire "sqrt (tt)> = thresh" in "tt> = thresh_sq" (dove thresh_sq = thresh ** 2 viene preparato prima di entrare nel ciclo) ... – roygvib

+0

@roygvib questo è intelligente! +1 – user15964

+0

Mi sono preso la libertà di correggere il codice in modo che possa effettivamente compilare ;-) –

risposta

11

Se il ciclo viene eseguito in blocchi/blocchi che si adattano alla cache della CPU, si riduce il numero di errori di cache e, di conseguenza, il numero di righe della cache recuperate dalla memoria. Ciò aumenta le prestazioni su tutti i loop che sono limitati dalle operazioni di memoria. Se la dimensione del blocco corrispondente è BLOCKSIZE, questo si ottiene

do j = 1, n, BLOCKSIZE 
    do jj = j, j+BLOCKSIZE-1 
     tt = tt + a(jj) * a(jj) 
    end do 
end do 

Questo, tuttavia, lascia un residuo che non viene trattato nel ciclo principale. Per illustrare questo, considerare una serie di lunghezza 1000. I primi sette blocchi (1--896) sono coperti nel ciclo, ma l'ottavo (897--1024) non lo è. Pertanto, è necessario un altro circuito per la restante:

do j=(n/BLOCKSIZE)*BLOCKSIZE,n 
    ! ... 
enddo 

Mentre poco senso rimuovere il condizionale dal loop resto, essa può essere eseguita nel circuito esterno del ciclo principale bloccata. Poiché ora non si verificano succursali nel loop interno, potrebbero essere applicabili ottimizzazioni aggressive.
Tuttavia, ciò limita la "precisione" della posizione determinata ai blocchi. Per ottenere una precisione in base agli elementi, è necessario ripetere il calcolo.

Ecco il codice completo:

subroutine threshold_block(a, thresh, ic) 
    implicit none 
    real, dimension(:), intent(in) :: a 
    real, intent(in) :: thresh 
    integer, intent(out) :: ic 
    real :: tt, tt_bak, thresh_sqr 
    integer :: n, j, jj 
    integer,parameter :: BLOCKSIZE = 128 

    ic = 0 
    tt = 0.d0 
    thresh_sqr = thresh**2 
    n = size(a) 
    ! Perform the loop in chunks of BLOCKSIZE 
    do j = 1, n, BLOCKSIZE 
    tt_bak = tt 
    do jj = j, j+BLOCKSIZE-1 
     tt = tt + a(jj) * a(jj) 
    end do 
    ! Perform the check on the block level 
    if (tt >= thresh_sqr) then 
     ! If the threshold is reached, repeat the last block 
     ! to determine the last position 
     tt = tt_bak 
     do jj = j, j+BLOCKSIZE-1 
      tt = tt + a(jj) * a(jj) 
      if (tt >= thresh_sqr) then 
       ic = jj 
       return 
      end if 
     end do 
    end if 
    end do 

    ! Remainder is treated element-wise 
    do j=(n/BLOCKSIZE)*BLOCKSIZE,n 
    tt = tt + a(j) * a(j) 
    if (tt >= thresh_sqr) then 
     ic = j 
     return 
    end if 
    end do 
end subroutine threshold_block 

prega di notare che i compilatori sono oggi molto buoni nella creazione bloccati loop in combinazione con altre ottimizzazioni. Nella mia esperienza è abbastanza difficile ottenere prestazioni migliori da tali semplici loop modificandoli manualmente.
Il blocco del ciclo è abilitato in gfortran con l'opzione del compilatore -floop-block.


Loop svolgimento può essere effettuata manualmente, ma dovrebbe essere lasciato al compilatore. L'idea è di eseguire manualmente un ciclo in blocchi e invece di un secondo ciclo come mostrato sopra, eseguire le operazioni duplicando il codice.Ecco un esempio per il ciclo interno come indicato sopra, per un ciclo di srotolamento fattore quattro:

do jj = j, j+BLOCKSIZE-1,4 
    tt = tt + a(jj) * a(jj) 
    tt = tt + a(jj+1) * a(jj+1) 
    tt = tt + a(jj+2) * a(jj+2) 
    tt = tt + a(jj+3) * a(jj+3) 
end do 

qui, senza resto si può verificare se BLOCKSIZE è un multiplo di 4. Probabilmente si può radersi poche operazioni qui ;-) L'opzione gfortran compilatore per abilitare questa è -funroll-loops


Per quanto ne so, pipelining CPU (Instruction Pipelining) non può essere applicate manualmente in Fortran. Questo compito spetta al compilatore.

Il pipelining crea una pipa di istruzioni. Si alimenta l'array completo in quella pipe e, dopo la fase di wind-up, si otterrà un risultato ad ogni ciclo di clock. Ciò aumenta drasticamente il rendimento. Tuttavia, i rami sono difficili (impossibili?) Da trattare nelle tubazioni e l'array dovrebbe essere abbastanza lungo da compensare il tempo necessario per impostare la tubazione, la fase di avvolgimento e la fase di wind-down.

+3

bella spiegazione. Va sottolineato che dovresti fare questo sforzo solo se hai profilato il codice e stabilito che quel particolare loop è un collo di bottiglia critico. C'è un chiaro svantaggio in termini di leggibilità/manutenzione e possibilità di introdurre errori se si scrive codice di routine in quel modo. – agentp

+0

@agentp Sono d'accordo, e anche in questo caso la dimensione del blocco, il fattore di srotolamento e in particolare il pipelining dipende in gran parte dalla macchina su cui viene eseguito il codice. A meno che tu non sappia esattamente cosa stai facendo, probabilmente il compilatore farà un lavoro migliore di te. –

+0

@AlexanderVogt Spiegazione molto chiara! Ho imparato molto. Ma come ho provato, la versione modificata è solo leggermente più veloce della versione originale. – user15964