Arbete med att stjäla

Vid parallell beräkning är arbetsstöld en schemaläggningsstrategi för flertrådade datorprogram . Det löser problemet med att exekvera en dynamisk flertrådad beräkning, en som kan "skapa" nya exekveringstrådar, på en statiskt flertrådad dator, med ett fast antal processorer (eller kärnor ). Det gör det effektivt när det gäller exekveringstid, minnesanvändning och kommunikation mellan processorer.

I en schemaläggare för arbetsstöld har varje processor i ett datorsystem en kö av arbetsobjekt (beräkningsuppgifter, trådar) att utföra. Varje arbetsobjekt består av en serie instruktioner som ska utföras sekventiellt, men under dess utförande kan ett arbetsobjekt också skapa nya arbetsobjekt som möjligen kan utföras parallellt med dess övriga arbete. Dessa nya objekt placeras initialt i kön hos processorn som exekverar arbetsobjektet. När en processor får slut på arbete, tittar den på de andra processorernas köer och "stjäl" deras arbetsobjekt. I själva verket fördelar arbetsstöld schemaläggningsarbetet över lediga processorer, och så länge som alla processorer har arbete att göra, uppstår ingen schemaläggningsoverhead.

Arbetet stjäl står i kontrast till arbetsdelning , ett annat populärt schemaläggningssätt för dynamisk multithreading, där varje arbetsobjekt schemaläggs på en processor när det skapas. Jämfört med detta tillvägagångssätt minskar arbetsstöld mängden processmigrering mellan processorer, eftersom ingen sådan migrering sker när alla processorer har arbete att göra.

Idén med arbetsstöld går tillbaka till implementeringen av programmeringsspråket Multilisp och arbetet med parallella funktionella programmeringsspråk på 1980-talet. Den används i schemaläggaren för programmeringsspråket Cilk , Java fork/join-ramverket, .NET Task Parallel Library och Rust Tokio runtime .

Utförandemodell

Work stealing är designad för en "strikt" gaffel-join-modell av parallell beräkning, vilket innebär att en beräkning kan ses som en riktad acyklisk graf med en enda källa (start av beräkning) och en enda sänkning (slut på beräkning). Varje nod i denna graf representerar antingen en gaffel eller en sammanfogning . Gafflar producerar flera logiskt parallella beräkningar, olika kallade "trådar" eller "strängar". Kanter representerar seriell beräkning.

Som ett exempel, överväg följande triviala gaffel-join-program i Cilk- liknande syntax:

 funktion  f(a, b): c ←  gaffel  g(a) d ← h(b)  sammanfoga  retur c + d  funktion  g(a): returnera a × 2  funktion  h(a): b ←  gaffel  g(a) c ← a + 1  gå med  retur b + c

Funktionsanropet f(1, 2) ger upphov till följande beräkningsgraf:

I grafen, när två kanter lämnar en nod, är beräkningarna som representeras av kantetiketterna logiskt parallella: de kan utföras antingen parallellt eller sekventiellt. Beräkningen kan bara fortsätta förbi en kopplingsnod när beräkningarna som representeras av dess inkommande kanter är klara. Arbetet med en schemaläggare är nu att tilldela beräkningarna (kanterna) till processorer på ett sätt som gör att hela beräkningen körs till slut i rätt ordning (som begränsat av kopplingsnoderna), helst så snabbt som möjligt.

Algoritm

Den randomiserade versionen av arbetsstöldalgoritmen som presenteras av Blumofe och Leiserson upprätthåller flera exekveringstrådar och schemalägger dessa på $P$ -processorer. Var och en av processorerna har en dubbeländad kö (deque) av trådar. Kalla ändarna av dequen "top" och "bottom".

Varje processor som har en aktuell tråd att exekvera, exekverar instruktionerna i tråden en efter en, tills den stöter på en instruktion som orsakar ett av fyra "speciella" beteenden:

En spawn -instruktion gör att en ny tråd skapas. Den aktuella tråden placeras längst ner i dequen och processorn börjar köra den nya tråden.
En stallinstruktion är en som tillfälligt stoppar exekveringen av dess tråd. Processorn släpper en tråd från botten av sin deque och börjar köra den tråden. Om dess deque är tom, börjar den arbeta med att stjäla, förklarat nedan.
En instruktion kan få en tråd att dö . Beteendet i det här fallet är detsamma som för en instruktion som stannar.
En instruktion kan aktivera en annan tråd. Den andra tråden trycks på botten av dequen, men processorn fortsätter att köra sin nuvarande tråd.

Inledningsvis består en beräkning av en enda tråd och tilldelas någon processor, medan de andra processorerna börjar inaktiva. Varje processor som blir inaktiv startar den faktiska processen med arbetsstöld, vilket betyder följande:

den väljer en annan processor likformigt slumpmässigt;
om den andra processorns deque inte är tom, skjuter den upp den översta tråden från dequen och börjar utföra den;
annars, upprepa.

Barnstöld kontra fortsättningsstöld

Observera att i regeln för spawn föreslår Blumofe och Leiserson att "förälder"-tråden kör sin nya tråd, som om den utförde ett funktionsanrop (i det C-liknande programmet f(x); g(y); , funktionen anrop till f avslutas innan anropet till g utförs). Detta kallas "fortsättningsstöld", eftersom fortsättningen av funktionen kan stjälas medan den skapade tråden exekveras, och är schemaläggningsalgoritmen som används i Cilk Plus . Det är inte det enda sättet att genomföra arbetsstöld; den alternativa strategin kallas "barnstöld" och är lättare att implementera som ett bibliotek utan kompilatorstöd . Barnstöld används av Threading Building Blocks , Microsofts Task Parallel Library och OpenMP , även om det senare ger programmeraren kontroll över vilken strategi som används.

Effektivitet

Flera varianter av arbetsstöld har föreslagits. Den randomiserade varianten på grund av Blumofe och Leiserson utför en parallell beräkning på förväntad tid $T_{1}/P+O(T_{\infty })$ på $P$ processorer; här är $T_{1}$ arbetet , eller den tid som krävs för att köra beräkningen på en seriell dator, och $T_{\infty }$ är spann , mängden av tid som krävs på en oändligt parallell maskin. Detta innebär att i förväntan är högst en konstant faktor gånger det teoretiska minimum. Däremot kan körtiden (särskilt antalet exekverade steals) vara exponentiell i $T_{\infty }$ i värsta fall. En lokaliserad variant, där en processor försöker stjäla sitt eget arbete när det är gratis, har också analyserats teoretiskt och praktiskt.

Utrymmesanvändning

En beräkning schemalagd av Blumofe–Leiserson-versionen av arbetsstöld använder $O(S_{1}P)$ stackutrymme , om $S_{1}$ var stackanvändningen av samma beräkning på en enda processor, som passar författarnas egen tidigare definition av utrymmeseffektivitet. Denna gräns kräver fortsatt stjäl; i en schemaläggare för att stjäla barn håller det inte, vilket kan ses av följande exempel:

 för  i = 0  till  n:  gaffel  f(i)  sammanfoga

I en barnstöld-implementation läggs alla "klumpade" anrop till f i en arbetskö som därmed växer till storlek n , som kan göras godtyckligt stor.

Multiprogrammeringsvariant

Algoritmen för att stjäla arbete som beskrivits tidigare, och dess analys, förutsätter en datormiljö där en beräkning schemaläggs på en uppsättning dedikerade processorer. I en med flera programmeringar (multi-tasking) måste algoritmen modifieras för att istället schemalägga beräkningsuppgifter på en pool av arbetartrådar , som i sin tur schemaläggs på de faktiska processorerna av en schemaläggare av operativsystemet . Vid varje given tidpunkt kommer OS-schemaläggaren att tilldela arbetsstöldprocessen ett antal $P A \leq P$ av $P$ -processorerna i datorn, eftersom andra processer kan använda de återstående processorerna. I den här inställningen har arbete som stjäl med en pool av $P$ arbetartrådar problemet att arbetare som agerar som tjuvar kan orsaka livelock : de kan blockera avrättningen av arbetare som faktiskt skulle skapa användbara uppgifter.

En variant av arbetsstöld har utarbetats för denna situation, som utför en beräkning inom förväntad tid

O\left({\frac {T_{1}}{P_{\mathrm {avg} }}}+{\frac { T_{\infty }P}{P_{\mathrm {avg} }}}\right),

där $P avg$ är det genomsnittliga antalet processorer som allokerats till beräkningen av OS-schemaläggaren över beräkningens körtid. Den flerprogrammerade arbetsschemaläggaren skiljer sig från den traditionella versionen i två avseenden:

Dess köer är icke-blockerande . Medan på dedikerade processorer kan åtkomst till köerna synkroniseras med lås , detta är inte tillrådligt i en multiprogrammeringsmiljö eftersom operativsystemet kan föregripa arbetartråden som håller låset, vilket blockerar förloppet för alla andra arbetare som försöker komma åt samma kö .
Före varje försök att stjäla arbete anropar en arbetartråd ett " yield "-systemanrop som ger processorn på vilken den är schemalagd till OS, för att förhindra svält .

Försök att förbättra multiprogrammeringsarbetet har fokuserat på problem med cachelokalitet och förbättrade ködatastrukturer.

Alternativ

Flera schemaläggningsalgoritmer för dynamiskt flertrådade beräkningar konkurrerar med arbetsstöld. Förutom den traditionella arbetsdelningsmetoden finns det en schemaläggare som kallas parallell djup-först (PDF) som förbättrar utrymmesgränserna för arbetsstöld, samt ger bättre prestanda i vissa situationer där kärnorna i en chip-multiprocessor delar en cache.

Anteckningar