Parallella datorprogram utan lås höjer prestandan
Utvecklingen går mot datorer som erbjuder allt större möjligheter att köra flera program samtidigt. I dag kan exempelvis en vanlig kontorsdator göra det. Ofta är även moderna datorprogram parallella i sig själva, så att ett flertal beräkningstrådar samarbetar till ett kombinerat resultat. Håkan Sundell på Chalmers presenterar i en doktorsavhandling avancerade datastrukturer som kan används av programmerare för att effektivt utbyta information mellan de parallella beräkningstrådarna.
Det kan vara mycket komplext att konstruera protokoll för datastrukturer som kan modifieras från flera håll samtidigt, och samtidigt garantera att informationen är korrekt och ger en gemensam vy som är konsistent. Vanligen använder man sig av låsmekanismer, som begränsar åtkomsten till de delade datastrukturerna till endast en beräkningstråd åt gången. Användningen av lås kan medföra ett antal allvarliga problem. Det allvarligaste är kanske så kallat dödläge, vilket innebär att den tråd som har låset har stannat eller “dött” och inte kan släppa låset. Alla som väntar på låset väntar då förgäves. Dessutom leder användningen av lås till ett ineffektivt utnyttjande av datorns kapacitet eftersom den inbyggda parallellismen inte utnyttjas.
Alternativet är att konstruera protokoll med icke-blockerande tekniker, som förutom att de undviker många av de problem som lås kan medföra, även tillåter en utökad parallellism.
Stora forskningsinsatser har gjorts för att utveckla icke-blockerande datastrukturer, dock har endast enkla datastrukturer visat sig vara praktiska och effektiva.
– Min forskningsgrupp har konstruerat ett flertal nya avancerade datastrukturer som är både praktiska och effektiva. Vissa är också inriktade mot tidskritiska realtidssystem som kan dra speciell nytta av den driftsäkerhet som icke-blockerande protokoll erbjuder. Vi har skapat ett programbibliotek som förutom de nyutvecklade protokollen också innehåller andra effektiva lösningar anpassade för praktisk användning genom ett gemensamt gränssnitt. Detta gränssnitt gör det möjligt för noviser i icke-blockerande protokoll att enkelt och effektivt använda sig av dem när de utvecklar datorprogram. Experiment som vi och andra har utfört visar på stora möjligheter till prestandaökningar, säger Håkan Sundell.
Resultaten har rönt betydande intresse inom såväl den akademiska som den industriella världen.
– En av våra nya datastrukturer som presenteras i avhandlingen har vunnit pris för bästa forskning på en av de främsta internationella konferenserna inom parallell databehandling. Hittills har två amerikanska företag inkorporerat våra datastrukturer i sina system, där de används för bland annat effektiv informationshantering. De två företagen är Essex-Radez LLC som arbetar med verktyg för börsanalyser och aktiehandel, samt Planview som arbetar med affärssystem.
Håkan Sundell försvarar sin doktorsavhandling “Efficient and Practical Non-Blocking Data Structures” den 5 november 2004 kl 10.00 i Gustaf Dalén-salen på Chalmers tekniska högskola. Opponent är Prof. Friedhelm Meyer auf der Heide från Heinz Nixdorf Institute, University of Paderborn, Tyskland. Handledare har varit Philippas Tsigas, Chalmers tekniska högskola.
Håkan Sundell kommer från Skoghall i Värmland.
Kontaktinformation
För mer information kontakta:
Håkan Sundell, Datavetenskap, Chalmers tekniska högskola,
tel 031-772 1053
e-post: phs@cs.chalmers.se
