Huvudmeny

Anpassning och optimering av låsfria datastrukturer

Startdatum

2009-01-01

Slutdatum

2012-12-31

Projektets huvudsakliga mål att förbättra parallelismen och dess uppsättning av verktyg som finns tillgängliga för mjukvaruutvecklarna inom Microsoft.Net.

Sedan den moderna datorns tillkomst har den effektiva delen i maskinen varit en processor som utför instruktioner, en efter en i en bestämd följd, en s.k. tråd. Dock har hastigheten som kan uppnås med denna arkitektur närmat sig den övre gränsen för vad som är möjligt. Detta är beroende av många faktorer, varav en mycket viktig faktor är problemet med strömförbrukningen och den relaterade värmeutvecklingen som ökat till ohanterliga nivåer. Därför har processorutvecklare valt andra sätt att öka datorns prestanda, och en nu vald väg är att erbjuda mer och mer parallellism. De nya processorer som nu lanseras med multi-core-tekniker, erbjuder mer och mer möjligheter att utföra flera instruktioner parallellt.

Dock, för att kunna utnyttja den tillgängliga prestandan måste datorprogrammen konstrueras så att de består av ett antal parallella trådar. Dessa trådar samarbetar för att lösa en större uppgift, och arbetar därmed med samt uppdaterar gemensam information samtidigt, vilket kräver en effektiv koordinering. En vanlig lösning på koordineringsproblemet har varit att använda låsmekanismer, så att endast en tråd åt gången kan arbeta med den gemensamma datamängden. Därmed blockeras övriga trådar från att arbeta med denna datamängd under tiden som en enskild tråd har låst den. Denna blockering medför en mängd problem, inte minst minskas den utnyttjade parallellismen med sänkt prestanda som följd. Om ett lås aldrig släpps av olika orsaker, kan detta få katastrofala följder.

Vi och andra har därför forskat i alternativa metoder, och utvecklat s.k. icke-blockerande protokoll där låsningsmekanismer undviks, och istället utnyttjas de inbyggda mekanismerna för synkronisering som processorerna erbjuder för att utföra samt koordinera uppdateringen av gemensam information mellan trådarna. Vi har under senare tid utvecklat ett antal effektiva och praktiska icke-blockerande protokoll för flera olika vanliga användningsområden för hantering av gemensamma datamängder. Självfallet borde dessa resultat vara mycket användbara inom ramen för att lösa problemet med omställningen till parallell programvara.

Samtidigt under de tiotal år som forskare har tagit fram de nya icke-blockerande teknikerna, har andra forskare självklart vidareutvecklat vanliga metoder för programutveckling. I samarbete med programvaruindustrin har man skapat nya programspråk och verktyg så att man kan arbeta mer effektivt och säkert, för att på så sätt korta ner utvecklingstider och därmed kostnader. Tyvärr har dessa två huvudspår nu problem att mötas, då man under så lång tid utvecklats utan nämnvärd interaktion. De icke-blockerande protokollen är användbara på en basnivå, och de nya väl accepterade verktygen kräver en högre nivå. Vi vill därför forska vidare på att anpassa de mycket lovande icke-blockerande protokollen så att de även passar de högnivåverktyg som används av professionella programmerare ute i arbetslivet idag.

Projektledare

Forskningshandledare

Forskare

Finansiärer