Gäng schemaläggning

Inom datavetenskap är gruppschemaläggning en schemaläggningsalgoritm för parallella system som schemalägger relaterade trådar eller processer att köras samtidigt på olika processorer . Vanligtvis kommer dessa att vara trådar som alla tillhör samma process, men de kan också vara från olika processer, där processerna kan ha en producent-konsument relation eller komma från samma MPI- program .

Gruppschemaläggning används för att säkerställa att om två eller flera trådar eller processer kommunicerar med varandra, kommer de alla att vara redo att kommunicera samtidigt. Om de inte var gängschemalagda skulle man kunna vänta med att skicka eller ta emot ett meddelande till en annan medan den sover, och vice versa. När processorer är övertecknade och gruppschemaläggning inte används inom en grupp av processer eller trådar som kommunicerar med varandra, kan varje kommunikationshändelse drabbas av en kontextväxling .

Gängschemaläggning baseras på en datastruktur som kallas Ousterhout-matrisen. I denna matris representerar varje rad en tidsdel och varje kolumn en processor. Trådarna eller processerna för varje jobb packas i en enda rad i matrisen. Under exekvering utförs koordinerad kontextväxling över alla noder för att växla från processerna i en rad till de i nästa rad.

Gängschemaläggning är strängare än coscheduling . Det kräver att alla trådar i samma process körs samtidigt, medan coscheduling tillåter fragment , som är uppsättningar av trådar som inte körs samtidigt med resten av gänget.

Gruppschemaläggning implementerades och användes i produktionsläge på flera parallella maskiner, framför allt Connection Machine CM-5.

Typer

Bag of Gangs (BoG)

I gruppschemaläggning sker en till en mappning, vilket innebär att varje uppgift kommer att mappas till en processor. Vanligtvis betraktas jobb som oberoende gäng, men med en påse med gäng kan alla gäng kombineras och skickas tillsammans till systemet. När jobb utförs i systemet kan avrättningen aldrig slutföras förrän och om inte alla gäng som tillhör samma BoG slutför sina avrättningar. Således, om ett gäng som tillhör något jobb slutför sin avrättning, kommer det att behöva vänta tills alla gängen har slutfört sina avrättningar. Detta leder till ökad synkroniseringsfördröjning.

Svarstid $R_{j}$ av $j^{th}$ Bag of Gangs definieras som tidsintervallet från ankomsten av BoG till grid-expeditören till slutförandet av jobb för alla undergäng som tillhör BoG. Den genomsnittliga svarstiden definieras enligt följande:

Svarstid (RT)= ${\frac {1}{N}}\textstyle \sum _{j-1}^{N}R_{j}\displaystyle$ .

Svarstiden påverkas ytterligare när ett prioriterat jobb kommer. Närhelst ett prioriterat jobb anländer till systemet kommer det jobbet att ges prioritet med avseende på alla andra jobb, även över de som för närvarande körs på processorerna. I det här fallet, när ett prioriterat jobb anländer, kommer undergruppen som för närvarande körs på systemet att stoppas och alla framsteg som har gjorts kommer att gå förlorade och måste göras om. Detta avbrott i jobbet kommer att försena den totala svarstiden för BoG ytterligare.

Anpassad först till kvarn (AFCFS)

Anpassat först till kvarn-system (AFCFS) är den anpassade versionen av först till kvarn-systemet. Enligt först till kvarn-först till kvarn-schemat kommer det jobb som kommer först att skickas vidare för utförande. Men i AFCFS-schemat, när ett jobb väl anländer till systemet, kommer jobbet inte att schemaläggas om inte och tills tillräckligt många processorer finns tillgängliga för att utföra respektive jobb. När ett stort jobb anländer till systemet och är närvarande i början av den färdiga kön men inte tillräckligt många processorer är tillgängliga, kommer en AFCFS-policy att schemalägga det mindre jobbet för vilket tillräckligt många processorer är tillgängliga, även om det jobbet finns längst bak i kön. Med andra ord, detta schema gynnar mindre jobb jämfört med större jobb baserat på tillgången på processor, vilket kommer att leda till ökad fragmentering i systemet.

Största gänget först till kvarn (LGFS)

I ovanstående exekveringsschema placeras uppgifterna som motsvarar ökande jobbstorlek i en kö, med uppgifterna som tillhör det största gänget schemalagda först, men denna metod för utförande tenderar att leda till att mindre jobb svälter ut resurser och är därför olämplig att köras i system där antalet processorer är jämförelsevis lågt.

AFCFS och LGFS måste också hantera eventuella processorfel. I ett sådant fall skickas uppgifter som utförs på den processorn till andra processorer för exekvering. Uppgifterna väntar i huvudet på kön på dessa processorer medan den aktuella processorn repareras.

Det finns två scenarier som framgår av ovanstående fråga:

• Blockeringsfall: Processorerna som tilldelats de avbrutna jobben är blockerade och kan inte utföra andra jobb i deras kö förrän jobben från de skadade processorerna har raderats.
• Icke-blockerande fall: Detta fall uppstår när de jobb som redan körs i processorerna bearbetas tidigt istället för att vänta på att de blockerade jobben ska återupptas.

schemaläggning för gäng

Gruppschemaläggning medan de I/O-bundna processerna körs håller processorerna inaktiva medan de väntar på svar från de andra processorerna, medan de lediga processorerna kan användas för att utföra uppgifter. Om gänget består av en blandning av CPU- och I/O-processer, eftersom dessa processer inte stör lite i varandras drift, algoritmer definieras för att hålla både CPU och I/O sysselsatta samtidigt och utnyttja parallellitet. Denna metod skulle presentera idén om att matcha par av gäng, en I/O-baserad och en CPU-bunden. Varje gäng skulle anta att det arbetar isolerat eftersom de använder olika enheter.

Schemaläggningsalgoritm

• Allmänt fall: I det allmänna fallet är en central nod utsedd i nätverket för att hantera uppgiftstilldelning och resursallokering. Den upprätthåller informationen i en Ousterhout-matris. I strikt gruppschemaläggning väljs en rad åt gången, varefter en nodschemaläggare schemalägger en process i respektive cell i den raden.
• Parat gäng: I schemaläggning av parade gäng väljs två rader istället för en, en vardera av det I/O-bundna gänget och CPU-gänget. Det är upp till den lokala schemaläggaren att tilldela jobb till lämpliga processorer för att framkalla maximal tillåten parallellitet.

Synkroniseringsmetoder

Concurrent Gang Scheduling (CGS)

Samtidigt gäng schemalägger en mycket skalbar och mångsidig algoritm och antar att det finns en synkroniserare som använder den interna klockan för varje nod. CGS består huvudsakligen av följande tre komponenter.

• Processor/minnesmodul (även kallad Processing Element).
• 2-vägs nätverk som tillåter 1-1 kommunikation.
• En synkroniserare som utför synkronisering av alla PE efter ett konstant intervall.

Synkroniseringsalgoritmen utförs i två steg.

• När belastningen ändras skapas en dedikerad tidtabell av frontend-schemaläggaren.
• Lokal schemaläggare följer sedan tidtabellen genom att växla mellan jobben som har distribuerats till dem av gränssnittsschemaläggaren.

Vi antar att det finns en synkroniserare som skickar signalen till alla noder i ett kluster med ett konstant intervall. CGS använder det faktum att de vanligaste händelserna som inträffar i en PC är timeravbrott och de använder samma parameter för att vara den interna klockan.

• En gemensam räknare initieras som inkrementeras varje gång ett avbrott påträffas och betecknas OS:s interna klocka.
• Alla noder synkroniseras efter ett kontrollintervall 't' och använder de individuella nodernas interna klockor.
• Om det efter tid t inte finns någon diskrepans mellan nodernas individuella klocka och den globala klockan, förlängs tidsintervallet t. Annars förkortas den.
• Kontrollera och uppdatera ständigt kontrollintervall t.

DELA schemaläggningssystem

SHARE-schemaläggningssystemet använder det interna klocksystemet för varje nod och synkroniseras med hjälp av NTP-protokollet . Smaken av schemaläggning implementeras genom att samla in jobb med samma resurskrav i en grupp och utföra desamma under en fördefinierad tidsperiod. Ofullständiga jobb föregrips efter att tidsdelen är slut.

Nodens lokala minne används som växlingsutrymme för förinställda jobb. De främsta fördelarna med det schemalagda SHARE-systemet är att det garanterar servicetiden för accepterade jobb och stödjer både batch- och interaktiva jobb.

Synkronisering:

Varje grupp av processer som använder samma resurser mappas till en annan processor. SHARE-systemet består i första hand av tre samverkande moduler.

• En global schemaläggare: Denna schemaläggare styr den lokala schemaläggaren i vilken ordning de ska utföra sina processer (lokala gängmedlemmar).
• En lokal schemaläggare: Efter att den lokala schemaläggaren har tillhandahållit jobben att exekvera av den globala schemaläggaren, säkerställer den att endast en av de parallella processerna exekveras vid någon av processorerna i en given tidslucka. Den lokala schemaläggaren kräver en kontextväxling för att föregripa ett jobb när dess tidssegment har löpt ut och byta ut ett nytt i dess ställe.
• Gränssnitt till kommunikationssystemet: Kommunikationsdelsystemet måste uppfylla flera krav som kraftigt ökar schemaläggarens overheadkrav. De består främst av:
  • Effektivitet: Måste exponera hårdvaruprestanda för sammankopplingen till klientnivå.
  • Åtkomstkontroll: Måste hantera åtkomst till kommunikationsundersystemet
  • Skydd och säkerhet: Sammankopplingen måste upprätthålla separation av processorerna genom att inte tillåta en att påverka prestanda hos en annan.
  • Multi-Protocol: sammankopplingen måste kunna kartlägga olika protokoll samtidigt för att tillgodose olika klientbehov.

Förpackningskriterier

En ny lucka skapas när vi inte kan packa jobbet i den tillgängliga luckan. Om en ny lucka öppnas även om jobbet kan packas i den tillgängliga luckan, kommer kördelen som är lika med en över antalet använda luckor att öka. Därför har vissa algoritmer utarbetats på packningskriterier och nämns nedan:

Kapacitetsbaserad algoritm

Denna algoritm övervakar slotskapaciteten och avgör om det finns något behov av att öppna en ny slot. Det finns två varianter av denna algoritm:

1. Första passningen. Här kontrolleras de använda luckorna för kapacitet i en sekventiell ordning, sedan väljs den första som har tillräcklig kapacitet. Om ingen av de tillgängliga luckorna har tillräcklig kapacitet, öppnas en ny lucka och bearbetningselementen (PE) allokeras i luckan i sekventiell ordning.

2. Bäst passform. Till skillnad från första passningen sorteras de använda platserna baserat på kapacitet, men inte i sekventiell ordning. Slitsen med den minsta tillräckliga kapaciteten väljs. Om ingen av de använda platserna har tillräcklig kapacitet, öppnas endast en ny lucka. När den nya luckan väl har öppnats allokeras bearbetningselementen (PE) i luckan i sekventiell ordning enligt den tidigare algoritmen.

Vänster-högerbaserade algoritmer

Denna algoritm är en modifierad version av algoritmen som passar bäst. I den bästa anpassningsalgoritmen tilldelas PEs i en sekventiell ordning, men i denna algoritm kan PE:erna infogas från båda riktningarna för att minska överlappningen mellan olika uppsättningar av PE som tilldelats olika jobb.

1. Vänster-höger efter storlek. Här kan PE:erna infogas i sekventiell ordning och i omvänd sekventiell ordning baserat på jobbets storlek. Om storleken på jobbet är liten infogas PE från vänster till höger och om jobbet är stort infogas PE från höger till vänster.

2. Vänster-höger vid spår. Till skillnad från den tidigare algoritmen, där valet baserades på jobbets storlek, är valet här beroende av slot. Nu indikeras luckor som fyllda, dvs fyllda från vänster eller från höger. PE:erna tilldelas jobbet i samma ordning. Antalet luckor på båda sidor är ungefär lika, så när en ny lucka öppnas indikeras riktningen baserat på antalet luckor i båda riktningarna.

Belastningsbaserade algoritmer

Både de kapacitetsbaserade och vänster-högerbaserade algoritmerna klarar inte belastningen på enskilda PE:er. Belastningsbaserade algoritmer tar hänsyn till belastningen på den individuella PE medan de spårar överlappningen mellan uppsättningar av PE som tilldelats olika jobb.

1. Minimal maxbelastning. I detta schema sorteras PE baserat på belastningen på dem som varje jobb kommer att ha på PE. Tillgängligheten av de fria PE i luckan bestämmer luckans kapacitet. Antag att PE:er tilldelas ett jobb som har $x$ trådar, $x^{th}$ PE i belastningsordningen (sista) kommer att bestämma den maximala belastningen som alla PE kan ha som finns i facket. Den slits som har minimal maximal belastning på någon PE väljs och ett antal minst belastade lediga PE används i spåret.

2. Minimal medelbelastning. Till skillnad från det tidigare schemat, där slots valdes baserat på den minimala maximala belastningen på $x^{th}$ PE, väljs här slots baserat på genomsnittet av belastningen på $x$ minst belastade PE.

Kompisbaserad algoritm

I denna algoritm tilldelas PE:erna i kluster, inte individuellt. PE:erna delas först upp i grupper som har två potens. Varje medlem i gruppen kommer att tilldelas en styrenhet och när ett jobb av storlek n anländer tilldelas det en kontrollenhet av storlek 2 [lg 2] ( ^den minsta styrkan till 2 som är större än eller lika med n). Styrenheten tilldelas genom att först sortera alla använda luckor och sedan identifiera grupper om 2 [ ^{lg 2]} sammanhängande fria processorer. Om en styrenhet har alla PEs lediga i några av luckorna, kommer endast ett nyligen ankommet jobb att tilldelas den styrenheten. Annars öppnas en ny lucka.

Migrationsbaserad algoritm

I alla ovan nämnda algoritmer är den initiala placeringspolicyn fast och jobb tilldelas PEs baserat på det. Detta schema migrerar dock jobb från en uppsättning PE till en annan uppsättning av PE, vilket i sin tur förbättrar kördelen av systemet.

Se även

• Samschemaläggning
• Parallell beräkning

• Gruppschemaläggning, tidsdelning på parallella datorer, SC98, november 1998 (en sammanfattning)
• Prestandaegenskaper för gruppschemaläggning i multiprogrammerade miljöer, SC97, november 1997