Wie Conditionals in Loops

Question

In diesem link zu vermeiden, gibt der Autor ein Beispiel als

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 

und der Autor diesen Code als

kommentiert

Ein alternativer Ansatz, der für viele Optimierungen erlauben würde, (Schleifen-Abrollung, CPU-Pipeline, weniger Zeitaufwand für die Auswertung der -Bedingung) würde das Hinzufügen von tt in Blöcken (z. B. Blöcke der Größe 128) und das Überprüfen der Bedingungen nach jedem Block beinhalten. Wenn die Bedingung erfüllt ist, kann der letzte Block wiederholt werden, um den Wert von ic zu bestimmen.

Was bedeutet das? Schleife abrollen? CPU-Pipeline? Hinzufügen von tt in Blöcken?

Wie den Code zu optimieren, wie der Autor sagen?

Answer 1

Wenn die Schleife in Chunks/Blöcke ausgeführt wird, die in den CPU-Cache passen, reduzieren Sie die Anzahl der Cache-Misses und folglich die Anzahl der aus dem Speicher abgerufenen Cache-Zeilen. Dies erhöht die Leistung bei allen Schleifen, die durch Speicheroperationen begrenzt sind. Wenn die entsprechende Blockgröße BLOCKSIZE ist, wird dies durch

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

aber dies erreicht wird, wird einen Rest hinterlassen, die nicht in der Hauptschleife behandelt wird. Betrachten Sie zur Veranschaulichung ein Array der Länge 1000. Die ersten sieben Brocken (1-896) sind in der Schleife abgedeckt, aber die achte (897-1024) ist nicht. Daher wird eine weitere Schleife für den Rest benötigt:

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

Während es wenig Sinn macht, die bedingte Schleife von dem Rest zu entfernen, kann es in der äußeren Schleife der blockierten Hauptschleife durchgeführt werden. Da jetzt keine Verzweigungen in der inneren Schleife mehr vorkommen, können dann aggressive Optimierungen anwendbar sein.
Dies begrenzt jedoch die "Genauigkeit" der ermittelten Position auf die Blöcke. Um zu einer elementweisen Genauigkeit zu gelangen, müssen Sie die Berechnung wiederholen. Hier

ist der vollständige Code:

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 

Bitte beachten Sie, dass die Compiler heutzutage sehr gut bei der Schaffung von blockierten Schleifen in Kombination mit anderen Optimierungen. Meiner Erfahrung nach ist es ziemlich schwierig, aus solchen einfachen Loops eine bessere Leistung zu erzielen, indem man sie manuell optimiert.
Loop-Blockierung ist in gfortran mit der Compileroption -floop-block aktiviert.

---

Schleifenentrollen kann manuell durchgeführt werden, sollte aber an den Compiler überlassen werden. Die Idee besteht darin, eine Schleife manuell in Blöcken auszuführen und anstelle einer zweiten Schleife, wie oben gezeigt, die Operationen durch Duplizieren des Codes durchzuführen.Hier ist ein Beispiel für die innere Schleife, wie oben angegeben, für eine Schleife Abrollen von Faktor vier:

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 

Hier kann kein Rest auftreten, wenn ein Vielfaches von BLOCKSIZE4 ist. Sie können sich wahrscheinlich ein paar Operationen hier ;-) Die gfortran Compiler-Option dies zu ermöglichen abrasieren ist -funroll-loops

---

Soweit ich weiß, CPU Pipelining (Instruction Pipelining) können nicht manuell in Fortran erzwungen werden. Diese Aufgabe liegt beim Compiler.

Pipelining richtet eine Reihe von Anweisungen ein. Sie speisen das komplette Array in diese Pipe und nach der Aufwickelphase erhalten Sie mit jedem Taktzyklus ein Ergebnis. Dies erhöht den Durchsatz drastisch. Verzweigungen sind jedoch schwierig (unmöglich?) In Rohren zu behandeln, und die Anordnung sollte lang genug sein, dass die Zeit, die für das Einrichten der Rohr-, Aufwickel- und Abwickelphase erforderlich ist, kompensiert wird.