windows - Parallelering af en algoritme med mange udgangspunkter?

Indlæg af Hanne Mølgaard Plasc

Problem



Jeg står over for at parallelisere en algoritme, som i sin serielle implementering undersøger de seks sider af en terning af array placeringer i et meget større tredimensionelt array. (Dvs. vælg et arrayelement og definer derefter en terning eller cuboid omkring det element 'n' elementer fjernt i x, y og z, afgrænset af grænserne for arrayet.


Hver arbejdsenhed ser noget sådan ud (Fortran pseudokode, den serielle algoritme er i Fortran):


do n1=nlo,nhi
  do o1=olo,ohi          
    if (somecondition(n1,o1) .eq. .TRUE.) then
       retval =.TRUE.
       RETURN
    endif    
  end do 
end do 


Eller C pseudokode:


for (n1=nlo,n1<=nhi,n++) {
  for (o1=olo,o1<=ohi,o++) {
    if(somecondition(n1,o1)!=0) {
      return (bool)true;
    }
  }
}


Der er seks arbejdsenheder som denne i den samlede algoritme, hvor 'lo' og 'hi' -værdierne generelt varierer mellem 10 og 300.


Det, jeg synes, ville være bedst, ville være at planlægge seks eller flere tråde af udførelse, runde robin, hvis der ikke er mange CPU-kerner, ideelt med løkkerne, der udfører parallelt med målet det samme som den serielle algoritme: somecondition() bliver True, skal udførelsen blandt alle trådene straks stoppe, og en værdi på True indstilles på et delt sted.


Hvilke teknikker eksisterer i en Windows compiler for at lette parallelisering af opgaver som dette? Selvfølgelig har jeg brug for en master tråd, der venter på en semafor eller færdiggørelsen af ​​arbejdstrådene, så der er behov for nesting og signalering, men min erfaring med OpenMP er introduktion på dette tidspunkt.


Er der meddelelsesmekanismer i OpenMP?


EDIT: Hvis den højeste forskel mellem 'nlo' og 'nhi' eller 'olo' og 'ohi' er otte til ti, betyder det ikke mere end 64 til 100 iterationer for denne indlejrede sløjfe og ikke mere end 384 til 600 iterationer for de seks arbejdsenheder sammen. Baseret på det, er det værd at parallelisere overhovedet?

Bedste reference


En mulighed er at bruge OpenMP til at parallelisere over de 6 sløjfer - erklære logical :: array(6), tillade, at hver sløjfe løber til afslutning, og derefter retval = any(array). Derefter kan du tjekke denne værdi og vende tilbage uden for den parallelle sløjfe. Tilføj en schedule(dynamic) til den parallelle gør sætning, hvis du gør dette. Eller har en separat !$omp parallel og sæt derefter !$omp do schedule(dynamic) ... !$omp end do nowait omkring hver af de 6 sløjfer.


Eller du kan følge de gode råd fra @ M.S.B. og parallelér den yderste sløjfe over hele rækken. Problemet her er, at du ikke kan have en RETURN inde i en parallel sløjfe - så mærket den anden yderste sløjfe (den største inden for den parallelle del), og EXIT som slår - smth som


retval = .FALSE.
!$omp parallel do default(private) shared(BIGARRAY,retval) schedule(dynamic,1)
do k=1,NN
   if(.not. retval) then
      outer2: do j=1,NN
         do i=1,NN
            ! --- your loop #1
            do n1=nlo,nhi
               do o1=olo,ohi
                  if (somecondition(BIGARRAY(i,j,k),n1,o1)) then
                     retval =.TRUE.
                     exit outer2
                  endif
               end do
            end do
            ! --- your loops #2 ... #6 go here
         end do
      end do outer2
   end if
end do 
!$omp end parallel do


[[rediger: erklæringen if antager, at du skal finde ud af, om der er mindst ét ​​element som det i det store array. Hvis du skal finde betingelsen for hvert element, kan du på samme måde enten tilføje en dummy loop exit eller goto, spring over resten af ​​behandlingen for det element. Igen, brug tidsplan (dynamisk) eller tidsplan (guidet).]]


Som et særskilt punkt vil du måske også gerne tjekke om det kan være en god idé at gå igennem den indvendige sløjfe ved et større trin (afhængigt af flydestørrelsen), beregne en logisk vektor på hver iteration og derefter sammenlægge resultaterne, f.eks. . smth som if(count(somecondition(x(o1:o1+step,n1,k)))>0); i dette tilfælde kan compileren være i stand til at vektorisere somecondition.

Andre referencer 1


Ville det være bedre at parallelisere sløjfen over arrayelementerne og forlade denne algoritme seriel, med flere tråde, der kører algoritmen på forskellige arrayelementer? Jeg tænker på dette fra din kommentar. 'Tidforbruget stammer fra det faktum, at ethvert element i arrayet skal testes som dette. Arraysne har normalt mellem fire millioner og tyve millioner elementer. 'Udformningen af ​​implementering af parallelelementeringen af ​​arrayelementerne er også fleksibel med hensyn til antallet tråde. Medmindre der er en grund til, at arrayelementerne skal kontrolleres i en vis rækkefølge?


Det ser ud til, at den del, du viser os ikke tager så lang tid at udføre, så det tager mindre tid ved at gøre det parallelt, er måske ikke let ... der er altid noget overhead til flere tråde, og hvis der ikke er meget tid at vinde, parallel kode er måske ikke hurtigere.

Andre referencer 2


Jeg tror, ​​at du kan gøre, hvad du vil med opgavekonstruktionen introduceret i OpenMP 3; Intel Fortran understøtter tasking i OpenMP. Jeg bruger ikke opgaver ofte, så jeg vandt ikke giver dig noget wonky pseudokode. [19]

Andre referencer 3


Du har allerede nævnt den indlysende måde at stoppe alle tråde på, så snart en tråd finder den endelige betingelse: Se hver del af en del af en variabel, som giver status for den endelige tilstand, og dermed afgøre, om du vil bryde ud af sløjferne. Det er selvfølgelig en overhead, så hvis du beslutter dig for at tage denne fremgangsmåde, foreslår jeg et par ting:



  1. Brug atom for at kontrollere den endelige tilstand, dette forhindrer dyre hukommelsesspyling, da bare den pågældende variabel spyles. Flyt til OpenMP 3.1, der understøttes nogle nye atomoperationer.

  2. Kontroller sjældent, måske som en gang pr. ydre iteration. Du bør kun parallelisere store sager for at overvinde overhead af multithreading.

  3. Denne er valgfri, men du kan prøve at tilføje kompilatorhints, f.eks. hvis du forventer en bestemt betingelse at være falsk det meste af tiden, vil kompilatoren optimere koden i overensstemmelse hermed.



En anden (noget snavset) tilgang er at bruge delte variabler for loopområderne for hver tråd, måske brug et delt array, hvor indeks n er for tråd n. Når en tråd finder den endelige tilstand, ændrer den sløjfeområdet for alle de andre tråde, så de stopper. Du har brug for den rigtige hukommelsessynkronisering. I grunden er overhead nu flyttet fra at kontrollere en dummy-variabel for at synkronisere/kontrollere sløjfeforhold. Igen er det nok ikke så godt at gøre det ofte, så brug måske delte ydre sløjfevariabler og private indre sløjfevariabler.


På en anden note minder det mig om det klassiske polling versus interrupt problem. Desværre tror jeg ikke, at OpenMP understøtter afbrydelser, hvor du kan sende en slags drabssignal til hver tråd.


Der er hacking work-arounds som at bruge en børneproces for netop dette parallelle arbejde og påberåbe operativsystemet planlæggeren at efterligne afbrydelser, men det er ret vanskelig at få det rigtige og ville gøre din kode ekstremt uportabel.


Opdater som svar på kommentar:


Prøv noget som dette:


char shared\_var = 0;
#pragma omp parallel
{
  //you should have some method for setting loop ranges for each thread
  for (n1=nlo; n1<=nhi; n1++) {
    for (o1=olo; o1<=ohi; o1++) {
      if (somecondition(n1,o1)!=0) {
        #pragma omp atomic write
        shared\_var = 1;  //done marker, this will also trigger the other break below
        break;           //could instead use goto to break out of both loops in 1 go
      }
    }
    #pragma omp atomic read
    private\_var = shared\_var;
    if (private\_var!=0) break;
  }
}

Andre referencer 4


En passende parallel tilgang kan være at lade hver arbejdstager undersøge en del af det samlede problem, præcis som i serienummeret og bruge en lokal (ikke-delt) variabel til resultatet (retval). Endelig gøre en reduktion over alle arbejdere på disse lokale variabler til et fælles samlet resultat.