Gaffel-skarv modell
Vid parallell beräkning är gaffel -join-modellen ett sätt att sätta upp och exekvera parallella program, så att exekveringen avgrenas parallellt vid angivna punkter i programmet, för att "join" (sammanfoga) vid en efterföljande punkt och återuppta sekventiell exekvering. Parallella sektioner kan dela rekursivt tills en viss uppgiftsgranularitet uppnås. Gaffelfog kan betraktas som ett parallellt designmönster . Den formulerades redan 1963.
Genom att kapsla gaffel-join-beräkningar rekursivt får man en parallell version av dela och erövra paradigmet, uttryckt av följande generiska pseudokod :
solve(problem) : om problemet är tillräckligt litet: lös problemet direkt (sekventiell algoritm) annars : för del i subdivide(problem) gaffel deluppgift för att lösa(del) gå med i alla deluppgifter som skapats i tidigare loop returnerar kombinerade resultat
Exempel
Den enkla parallella sammanslagningen av CLRS är en gaffel-join-algoritm.
mergesort(A, lo, hi): if lo < hi: // minst ett element av input mid = ⌊lo + (hi - lo) / 2⌋ gaffel mergesort(A, lo, mid) // process (potentiellt) parallellt med huvuduppgift mergesort(A, mid, hi) // huvuduppgift hanterar andra rekursion join merge(A, lo, mid, hi)
Det första rekursiva anropet är "forked off", vilket betyder att dess exekvering kan köras parallellt (i en separat tråd) med följande del av funktionen, upp till joinen som gör att alla trådar synkroniseras . Även om sammanfogningen kan se ut som en barriär , är den annorlunda eftersom trådarna fortsätter att fungera efter en barriär, medan efter en sammanfogning bara en tråd fortsätter.
Det andra rekursiva anropet är inte en gaffel i pseudokoden ovan; detta är avsiktligt, eftersom fördelningsuppgifter kan kosta en kostnad. Om båda de rekursiva anropen konfigurerades som deluppgifter, skulle huvuduppgiften inte ha något extra arbete att utföra innan den blockerades vid anslutningen .
Genomföranden
Implementeringar av gaffel-join-modellen kommer vanligtvis att gaffeluppgifter , fibrer eller lätta trådar , inte "tungvikts" -trådar eller processer på operativsystemnivå, och använda en trådpool för att utföra dessa uppgifter: gaffelprimitiven tillåter programmeraren att specificera potentiell parallellitet , som implementeringen sedan mappar till faktisk parallell exekvering. Anledningen till denna design är att skapa nya trådar tenderar att resultera i för mycket overhead.
De lätta trådarna som används i fork-join-programmering kommer vanligtvis att ha sin egen schemaläggare (vanligtvis ett arbete som stjäl en) som mappar dem till den underliggande trådpoolen. Den här schemaläggaren kan vara mycket enklare än en fullfjädrad, förebyggande schemaläggare av operativsystem: trådschemaläggare för allmänna ändamål måste hantera blockering för lås , men i gaffel-join-paradigmet, blockerar trådar bara vid kopplingspunkten.
Fork-join är huvudmodellen för parallell exekvering i OpenMP- ramverket, även om OpenMP-implementeringar kan eller kanske inte stöder kapsling av parallella sektioner. Det stöds också av Java concurrency- ramverket, Task Parallel Library för .NET och Intels Threading Building Blocks (TBB). Programmeringsspråket Cilk har stöd för fork and join på språknivå, i form av nyckelorden spawn och sync , eller cilk_spawn och cilk_sync i Cilk Plus .
Se även
externa länkar
- En primer om schemaläggning av gaffel – gå med parallellism med arbetsstöld
- Fork-Join Merge Sort (Java) (på portugisiska)