Granularitet (parallell beräkning)

Vid parallell beräkning är granularitet (eller kornstorlek ) för en uppgift ett mått på mängden arbete (eller beräkning ) som utförs av den uppgiften.

En annan definition av granularitet tar hänsyn till kommunikationsoverhead mellan flera processorer eller bearbetningselement. Den definierar granularitet som förhållandet mellan beräkningstid och kommunikationstid, där beräkningstid är den tid som krävs för att utföra beräkningen av en uppgift och kommunikationstid är den tid som krävs för att utbyta data mellan processorer.

Om T _comp är beräkningstiden och T _comm anger kommunikationstiden, kan granulariteten G för en uppgift beräknas som:

$G={\frac {T_{\mathrm {comp} }}{T_{\mathrm {comm} }}}$

Granularitet mäts vanligtvis i termer av antalet instruktioner som exekveras i en viss uppgift. Alternativt kan granularitet också specificeras i termer av exekveringstiden för ett program, genom att kombinera beräkningstiden och kommunikationstiden.

Typer av parallellism

Beroende på hur mycket arbete som utförs av en parallell uppgift kan parallellitet delas in i tre kategorier: finkornig, medelkornig och grovkornig parallellitet.

Finkornig parallellism

För mer, se Mikroparallelism .

I finkornig parallellism bryts ett program ner till ett stort antal små uppgifter. Dessa uppgifter tilldelas individuellt till många processorer. Mängden arbete i samband med en parallell uppgift är låg och arbetet är jämnt fördelat mellan processorerna. Därför underlättar finkornig parallellitet lastbalansering .

Eftersom varje uppgift behandlar mindre data, är antalet processorer som krävs för att utföra hela bearbetningen högt. Detta i sin tur ökar kommunikations- och synkroniseringskostnaderna.

Finkornig parallellism utnyttjas bäst i arkitekturer som stöder snabb kommunikation. Delad minnesarkitektur som har låg kommunikationsoverhead är mest lämplig för finkornig parallellism.

Det är svårt för programmerare att upptäcka parallellism i ett program, därför är det vanligtvis kompilatorernas ansvar att upptäcka finkornig parallellism.

Ett exempel på ett finkornigt system (från utanför den parallella beräkningsdomänen) är nervsystemet i vår hjärna .

Connection Machine (CM-2) och J-Machine är exempel på finkorniga parallella datorer som har en kornstorlek i intervallet 4-5 μs.

Grovkornig parallellism

I grovkornig parallellism delas ett program upp i stora uppgifter. På grund av detta sker en stor mängd beräkningar i processorer. Detta kan resultera i belastningsobalans, där vissa uppgifter bearbetar huvuddelen av datan medan andra kan vara inaktiva. Vidare misslyckas grovkornig parallellism att utnyttja parallelliteten i programmet eftersom det mesta av beräkningen utförs sekventiellt på en processor. Fördelen med denna typ av parallellitet är låg kommunikation och synkroniseringsoverhead.

Meddelandeöverförande arkitektur tar lång tid att kommunicera data mellan processer vilket gör den lämplig för grovkornig parallellism.

Cray Y-MP är ett exempel på grovkornig parallelldator som har en kornstorlek på cirka 20s.

Medelkornig parallellism

Mellankornig parallellism används relativt till finkornig och grovkornig parallellism. Mellankornig parallellism är en kompromiss mellan finkornig och grovkornig parallellism, där vi har uppgiftsstorlek och kommunikationstid större än finkornig parallellism och lägre än grovkornig parallellism. De flesta parallella datorer för allmänt bruk faller i denna kategori.

Intel iPSC är ett exempel på medelkornig parallelldator som har en kornstorlek på cirka 10ms.

Exempel

Tänk på en 10*10 bild som behöver bearbetas, med tanke på att bearbetningen av de 100 pixlarna är oberoende av varandra.

Finkornig parallellism: Antag att det finns 100 processorer som är ansvariga för att bearbeta 10*10-bilden. Om man ignorerar kommunikationsoverheaden kan de 100 processorerna bearbeta bilden på 10*10 i en klockcykel. Varje processor arbetar på 1 pixel av bilden och kommunicerar sedan utdata till andra processorer. Detta är ett exempel på finkornig parallellism.

Mediumkornig parallellism: Tänk på att det finns 25 processorer som bearbetar 10*10-bilden. Bearbetningen av bilden kommer nu att ta 4 klockcykler. Detta är ett exempel på medelkornig parallellism.

Grovkornig parallellism: Vidare, om vi minskar processorerna till 2, kommer behandlingen att ta 50 klockcykler. Varje processor behöver bearbeta 50 element vilket ökar beräkningstiden, men kommunikationskostnaderna minskar när antalet processorer som delar data minskar. Detta fall illustrerar grovkornig parallellism.

Finkornig: Pseudokod för 100 processorer	Medelkornig : Pseudokod för 25 processorer	Grovkornig : Pseudokod för 2 processorer
void main () { switch ( Processor_ID ) { fall 1 : Beräkna element 1 ; bryta ; fall 2 : Beräkna element 2 ; bryta ; fall 3 : Beräkna element 3 ; bryta ; . . . . fall 100 : Beräkna element 100 ; bryta ; } }	void main () { switch ( Processor_ID ) { fall 1 : Beräkna element 1-4 ; bryta ; fall 2 : Beräkna element 5-8 ; bryta ; fall 3 : Beräkna element 9-12 ; bryta ; . . fall 25 : Beräkna element 97-100 ; bryta ; } }	void main () { switch ( Processor_ID ) { fall 1 : Beräkna element 1-50 ; bryta ; fall 2 : Beräkna element 51-100 ; bryta ; } }
Beräkningstid - 1 klockcykel	Beräkningstid - 4 klockcykler	Beräkningstid - 50 klockcykler

Nivåer av parallellism

Granularitet är nära kopplat till bearbetningsnivån. Ett program kan delas upp i fyra nivåer av parallellitet -

1. Instruktionsnivå.
2. Slingnivå
3. Sub-rutin nivå och
4. Programnivå

Den högsta graden av parallellitet uppnås på instruktionsnivå , följt av loop-nivå parallellism. På instruktions- och loopnivå uppnås finkornig parallellitet. Typisk kornstorlek på instruktionsnivå är 20 instruktioner, medan kornstorleken på loopnivå är 500 instruktioner.

På subrutinnivån (eller procedurnivån) är kornstorleken vanligtvis några tusen instruktioner. Medelkornig parallellism uppnås på subrutinnivå.

På programnivå sker parallell exekvering av program. Granulariteten kan ligga inom tiotusentals instruktioner. Grovkornig parallellism används på denna nivå.

Tabellen nedan visar sambandet mellan nivåer av parallellitet, kornstorlek och grad av parallellitet

Nivåer	Kornstorlek	Parallellism
Instruktionsnivå	Bra	Högsta
Slingnivå	Bra	Måttlig
Underrutinnivå	Medium	Måttlig
Programnivå	Grov	Minst

Inverkan av granularitet på prestanda

Granularitet påverkar prestandan hos parallella datorer. Att använda fina korn eller små uppgifter resulterar i mer parallellitet och ökar därmed hastigheten . Synkroniseringskostnader, schemaläggningsstrategier etc. kan dock påverka utförandet av finkorniga uppgifter negativt. Enbart ökad parallellitet kan inte ge det bästa resultatet.

För att minska kommunikationsoverheaden kan granulariteten ökas. Grovkorniga uppgifter har mindre kommunikationskostnader men de orsakar ofta lastobalans. Således uppnås optimal prestanda mellan de två ytterligheterna av finkornig och grovkornig parallellism.

Olika studier har föreslagit deras lösning för att bestämma den bästa granulariteten för att underlätta parallell bearbetning. Att hitta den bästa kornstorleken beror på ett antal faktorer och varierar mycket från problem till problem.

Se även

• Parallellism på instruktionsnivå
• Dataparallellism