Ett nytt system utvecklat av MIT-forskare "lär sig" automatiskt hur man schemalägger databearbetningsoperationer över tusentals servrar - en uppgift som traditionellt är reserverad för oprecisa, mänskligt utformade algoritmer. Att göra det kan hjälpa dagens energikrävande datacenter att fungera mycket mer effektivt.

Datacenter kan innehålla tiotusentals servrar, som ständigt kör databearbetningsuppgifter från utvecklare och användare. Klusterschemaläggningsalgoritmer fördelar de inkommande uppgifterna över servrarna, i realtid, för att effektivt använda alla tillgängliga datorresurser och få jobbet gjort snabbt.

Traditionellt, dock, människor finjusterar dessa schemaläggningsalgoritmer, baserat på några grundläggande riktlinjer ("policys") och olika avvägningar. De kan, till exempel, koda algoritmen för att få vissa jobb gjorda snabbt eller dela resurser lika mellan jobb. Men arbetsbelastningar – det vill säga grupper av kombinerade uppgifter – finns i alla storlekar. Därför, det är praktiskt taget omöjligt för människor att optimera sina schemaläggningsalgoritmer för specifika arbetsbelastningar och, som ett resultat, de saknar ofta sin verkliga effektivitetspotential.

MIT-forskarna överförde istället all manuell kodning till maskiner. I en artikel som presenterades på SIGCOMM, de beskriver ett system som utnyttjar "förstärkningsinlärning" (RL), en maskininlärningsteknik, prova och missa, för att skräddarsy schemaläggningsbeslut till specifika arbetsbelastningar i specifika serverkluster.

Att göra så, de byggde nya RL-tekniker som kunde träna på komplexa arbetsbelastningar. I träning, systemet försöker många möjliga sätt att fördela inkommande arbetsbelastningar över servrarna, så småningom hitta en optimal kompromiss med att utnyttja beräkningsresurser och snabba bearbetningshastigheter. Inget mänskligt ingripande krävs utöver en enkel instruktion, Till exempel, "minimera tiderna för slutförande av jobb."

Jämfört med de bästa handskrivna schemaläggningsalgoritmerna, forskarnas system slutför jobb cirka 20 till 30 procent snabbare, och dubbelt så snabbt under tider med hög trafik. Till största del, dock, systemet lär sig hur man komprimerar arbetsbelastningar effektivt för att lämna lite avfall. Resultaten indikerar att systemet kan göra det möjligt för datacenter att hantera samma arbetsbelastning vid högre hastigheter, använda färre resurser.

"Om du har ett sätt att göra trial and error med hjälp av maskiner, de kan prova olika sätt att schemalägga jobb och automatiskt ta reda på vilken strategi som är bättre än andra, säger Hongzi Mao, en Ph.D. student vid institutionen för elektroteknik och datavetenskap (EECS). "Det kan förbättra systemets prestanda automatiskt. Och varje liten förbättring av användningen, till och med 1 procent, kan spara miljontals dollar och mycket energi i datacenter."

"Det finns inget som passar alla för att fatta schemaläggningsbeslut, " tillägger medförfattaren Mohammad Alizadeh, en EECS-professor och forskare vid Computer Science and Artificial Intelligence Laboratory (CSAIL). "I befintliga system, dessa är hårdkodade parametrar som du måste bestämma i förväg. Vårt system lär sig istället att justera dess schemapolicyegenskaper, beroende på datacenter och arbetsbelastning."

Med Mao och Alizadeh på tidningen är:postdoktorerna Malte Schwarzkopf och Shaileshh Bojja Venkatakrishnan, och forskarassistent Zili Meng, hela CSAIL.

RL för schemaläggning

Vanligtvis, databehandlingsjobb kommer in i datacenter representerade som grafer över "noder" och "kanter". Varje nod representerar någon beräkningsuppgift som måste göras, där ju större nod, ju mer beräkningskraft behövs. Kanterna som förbinder noderna länkar samman anslutna uppgifter. Schemaläggningsalgoritmer tilldelar noder till servrar, utifrån olika policyer.

Men traditionella RL-system är inte vana vid att bearbeta sådana dynamiska grafer. Dessa system använder en mjukvaru-"agent" som fattar beslut och tar emot en återkopplingssignal som belöning. Väsentligen, den försöker maximera sina belöningar för varje given handling för att lära sig ett idealiskt beteende i ett visst sammanhang. Dom kan, till exempel, hjälpa robotar att lära sig utföra en uppgift som att plocka upp ett föremål genom att interagera med omgivningen, men det handlar om att bearbeta video eller bilder genom ett enklare rutnät av pixlar.

För att bygga sin RL-baserade schemaläggare, kallas Decima, forskarna var tvungna att utveckla en modell som kunde bearbeta grafstrukturerade jobb, och skala till ett stort antal jobb och servrar. Deras systems "agent" är en schemaläggningsalgoritm som utnyttjar ett grafiskt neuralt nätverk, används ofta för att bearbeta grafstrukturerade data. För att komma på ett grafiskt neuralt nätverk som är lämpligt för schemaläggning, de implementerade en anpassad komponent som aggregerar information över vägarna i grafen – som att snabbt uppskatta hur mycket beräkning som krävs för att slutföra en given del av grafen. Det är viktigt för jobbschemaläggning, eftersom "barn" (nedre) noder inte kan börja köras förrän deras "förälder" (övre) noder slutar, så att förutse framtida arbete längs olika vägar i grafen är centralt för att fatta bra schemaläggningsbeslut.

För att träna sitt RL-system, forskarna simulerade många olika grafsekvenser som efterliknar arbetsbelastningar som kommer in i datacenter. Agenten fattar sedan beslut om hur man allokerar varje nod längs grafen till varje server. För varje beslut, en komponent beräknar en belöning baserat på hur bra den klarade sig vid en specifik uppgift – som att minimera den genomsnittliga tid det tog att bearbeta ett enskilt jobb. Agenten fortsätter, förbättra sina beslut, tills den får högsta möjliga belöning.

Grundläggande arbetsbelastning

Ett bekymmer, dock, är att vissa arbetsbelastningssekvenser är svårare än andra att bearbeta, eftersom de har större uppgifter eller mer komplicerade strukturer. Dessa kommer alltid att ta längre tid att bearbeta — och, därför, belöningssignalen kommer alltid att vara lägre än enklare. Men det betyder inte nödvändigtvis att systemet fungerade dåligt:​​det skulle kunna göra bra tid på en utmanande arbetsbelastning men ändå vara långsammare än en lättare arbetsbelastning. Den variationen i svårighetsgrad gör det utmanande för modellen att avgöra vilka åtgärder som är bra eller inte.

För att ta itu med det, forskarna anpassade en teknik som kallas "baselining" i detta sammanhang. Denna teknik tar medelvärden av scenarier med ett stort antal variabler och använder dessa medelvärden som baslinje för att jämföra framtida resultat. Under träning, de beräknade en baslinje för varje inmatningssekvens. Sedan, de låter schemaläggaren träna på varje arbetsbelastningssekvens flera gånger. Nästa, systemet tog den genomsnittliga prestandan över alla beslut som fattades för samma inmatningsbelastning. Det genomsnittet är den baslinje mot vilken modellen sedan kan jämföra sina framtida beslut för att avgöra om dess beslut är bra eller dåliga. De hänvisar till denna nya teknik som "input-beroende baslinje."

Den innovationen, forskarna säger, är tillämplig på många olika datorsystem. "Det här är ett allmänt sätt att göra förstärkningsinlärning i miljöer där det finns den här inputprocessen som påverkar miljön, och du vill att varje träningsevenemang ska överväga ett exempel på den inmatningsprocessen, " säger han. "Nästan alla datorsystem hanterar miljöer där saker och ting hela tiden förändras."

Aditya Akella, professor i datavetenskap vid University of Wisconsin i Madison, vars grupp har designat flera högpresterande schemaläggare, fann att MIT-systemet kunde bidra till att ytterligare förbättra deras egen policy. "Decima kan gå ett steg längre och hitta möjligheter för [schemaläggning] optimering som helt enkelt är för betungande att realisera via manuella design-/justeringsprocesser, " säger Akella. "De schemaläggare vi designade uppnådde betydande förbättringar jämfört med tekniker som används i produktionen när det gäller applikationsprestanda och klustereffektivitet, men det fanns fortfarande ett gap med de idealiska förbättringar vi möjligen kunde uppnå. Decima visar att ett RL-baserat tillvägagångssätt kan upptäcka [policyer] som hjälper till att överbrygga klyftan ytterligare. Decima förbättrade våra tekniker med [ungefär] 30 procent, vilket kom som en stor överraskning."

Just nu, deras modell är tränad på simuleringar som försöker återskapa inkommande onlinetrafik i realtid. Nästa, forskarna hoppas kunna träna modellen på realtidstrafik, vilket potentiellt kan krascha servrarna. Så, de håller för närvarande på att utveckla ett "skyddsnät" som kommer att stoppa deras system när det är på väg att orsaka en krasch. "Vi ser det som träningshjul, " säger Alizadeh. "Vi vill att det här systemet ska tränas kontinuerligt, men den har vissa träningshjul som om den går för långt kan vi se till att den inte ramlar omkull."

Den här historien återpubliceras med tillstånd av MIT News (web.mit.edu/newsoffice/), en populär webbplats som täcker nyheter om MIT-forskning, innovation och undervisning.