DOPIPE

DOPIPE- parallellism är en metod för att utföra parallellism på loopnivå genom att pipelinera satserna i en loop. Pipelinerad parallellism kan existera på olika abstraktionsnivåer som loopar, funktioner och algoritmiska stadier. Omfattningen av parallellitet beror på programmerarnas förmåga att utnyttja detta koncept på bästa sätt. Det beror också på faktorer som att identifiera och separera de oberoende uppgifterna och utföra dem parallellt.

Bakgrund

Huvudsyftet med att använda parallellitet på loop-nivå är att söka och dela sekventiella uppgifter i ett program och konvertera dem till parallella uppgifter utan någon tidigare information om algoritmen . Delar av data som är återkommande och förbrukar en betydande mängd exekveringstid är goda kandidater för parallellism på loop-nivå . Vissa vanliga tillämpningar av parallellism på loopnivå finns i matematisk analys som använder flerdimensionella matriser som itereras i kapslade loopar.

Det finns olika typer av parallelliseringstekniker som används på basis av datalagringskostnader, grad av parallellisering och databeroende . Några av de kända teknikerna är: DOALL , DOACROSS och DOPIPE .

DOALL: Denna teknik används där vi kan parallellisera varje iteration av loopen utan någon interaktion mellan iterationerna. Följaktligen reduceras den totala körtiden från N * T (för en seriell processor, där T är exekveringstiden för varje iteration) till endast T (eftersom alla N iterationer exekveras parallellt).

DOACROSS: Denna teknik används överallt där det finns möjlighet för databeroende. Därför parallelliserar vi uppgifter på ett sådant sätt att alla dataoberoende uppgifter exekveras parallellt, men de beroende exekveras sekventiellt. Det finns en grad av synkronisering som används för att synkronisera de beroende uppgifterna över parallella processorer.

Beskrivning

DOPIPE är en pipelined parallelliseringsteknik som används i program där varje element som produceras under varje iteration konsumeras i den senare iterationen. Följande exempel visar hur man implementerar DOPIPE-tekniken för att minska den totala exekveringstiden genom att bryta uppgifterna inuti slingan och exekvera dem på ett pipelinerat sätt. Inbrytningen i uppgifter sker på ett sådant sätt att alla beroenden inom slingan är enkelriktade, dvs följande iteration är inte beroende av föregående iteration.

Exempel

Programmet nedan visar en pseudokod för DOPIPE-parallellisering.

I den här koden ser vi att det finns tre uppgifter (F0, F1 och F2) inuti en loop som itererar över j för 1 till N . Följande är en lista över beroenden i koden:

F1[j] → ^T F1[j+1], innebär att sats F1 i iteration j+1 måste exekveras efter sats F1 i iteration j . Detta är också känt som verkligt beroende.

F1[j] → ^T F2[j], innebär att sats F2 i iteration j måste exekveras efter sats F1 i iteration j .

för (j=1; j<=N; j++) {F0: o[j] = x[j] - a[j]; Fl: z[j] = z[j-1] * 5; F2: y[j] = z[j] * w[j]; }

_konsumeras vara lika med N * (TF0 ₊ T _F1 + T _F2 ), där _TF0 , TF1 och T _F2 anger exekveringstid för funktionerna F0, F1 och F2 per iteration. Om vi ​​nu parallelliserar slingan genom att pipelina uttalandena inuti slingan på följande sätt:

för (j=1; j<=N; j++) {F0: o[j] = x[j] - a[j]; // DOALL parallellism } for (j=1; j<=N; j++) { F1: z[j] = z[j-1] * 5; // DOPIPE parallellism post(j); // Resultatet av F1 är postat och tillgängligt för användning } för (j=1; j<=N; j++) { wait(j); // Den väntar tills F1 är klar och producerar värdet z[j] som ska användas av F2 F2: y[j] = z[j] * w[j]; }

Eftersom F0 är en oberoende funktion, dvs den har inget loopburet beroende (inget beroende av j+1 eller j-1 iterationer). Inte heller det har något beroende mellan andra uttalanden i loopen. Därför kan vi helt separera den här funktionen och köra den parallellt med DOALL parallellism . Å andra sidan är påståenden F1 och F2 beroende (förklarat ovan), därför delar vi upp dem i två olika loopar och exekverar dem på ett rörligt sätt. Vi använder post(j) och wait(j) för att synkronisera mellan F1- och F2-loopar.

Med start från den första iterationen av j , exekveras sats F1 i T _F1 -tid. Samtidigt exekveras inte F2 eftersom den väntar på att värdet z[j] ska produceras av F1. När F1 slutför sin exekvering för iteration j , postar den värdet med post(j) . Efter att ha väntat på F1:s exekvering, med hjälp av wait(j), startar F2 dess exekvering eftersom den har värdet z[j] tillgängligt för användning. Dessutom, eftersom F1:s exekvering inte är begränsad av F2, så exekverar F1 j+1 samtidigt. Figuren nedan visar exekveringstidslinjen för alla uttalanden.

DOPIPE exempel

Från figuren ser vi att den totala tiden för att exekvera F0 är T _F0 , eftersom alla iterationer av F0 exekveras parallellt. Medan för F1 och F2 är den totala exekveringstiden lika med N * T _F1 + T _F2 (med tanke på försumbar synkroniseringstid).

Detta är avsevärt mindre än tiden som erhålls under sekventiell exekvering.

Jämförelse med andra modeller

DOALL parallellism arbetar huvudsakligen på principen om dela och erövra. Här körs alla uppgifter i olika iterationer som använder unik uppsättning data. Så problemet med den här implementeringen är att när stora mängder data fungerar tillsammans, behövs ett stort cacheutrymme för att fungera för olika trådar . Eftersom det inte finns några beroenden i trådarna finns det ingen overhead för kommunikationen mellan trådarna.

I DOPIPE finns det en synkroniseringsoverhead mellan trådarna. Men på grund av sin pipelinestruktur kräver den mindre cacheutrymme eftersom den producerade data omedelbart konsumeras av konsumenten.

Se även

• Parallell beräkning
• Slingnivåparallellism
• Uppgiftsparallellism
• Databeroende
• ÖppnaMP
• Automatisk parallellisering
• Tråd (dator)
• Cache (dator)