Name: Per Nyberg

Titel: En jämförelse av låsstrategier för quadträd med loose-mekanism i en miljö av många frekvent flyttande objekt

Sammanfattning

Att använda ett quadträd för att lagra punkter eller geometriska objekt i tvådimensionella miljöer är en välbeprövad metod som har visat sig kunna tillhandahålla både snabba uppdateringar av den innehållna informationen såväl som snabba områdescheckar för ett specifikt område. Dessa egenskaper kommer väl till användning för en datastruktur om den t ex ska spåra utryckningsfordon åt larmcentraler. Att finjustera denna datastruktur för att uppnå ännu bättre prestanda räcker bara så långt och förr eller senare kommer andra åtgärder att behövas för att nå en högre kapacitet. Det skulle kunna vara fallet att informationsflödet behöver gå snabbare för att operatörerna ska få den information de behöver i tid. En sådan åtgärd som vanligtvis används inom datalogi är att göra datastrukturen parallel. På en maskin med flera trådar kan ett program som har gjorts parallelliserade snabbas upp med upp till antalet kärnor gentemot en sekventiell lösning, vilket innebär att den totala körtiden kan förbättras.

I detta arbete utvärderas quadträd med loose-mekanism och buckets för olika tillämpningar av vanliga parallelliseringsmetoder. Försök att samla in inkommande anrop görs med två olika tillvägagångssätt, att gå igenom kön av operationer rakt av samt att bygga om quadträdet med de ändringar som tillämpas från anropen för att skapa ett nytt träd. Andra tillvägagångssätt bygger på strategin för hand-över-hand-låsning och används för att prova hur trädet fungerar med lås placerade på noderna i trädet. En femte metod som testas är att låsa hela datastrukturen vid varje interaktion. Dessa taktiker jämförs i olika scenarier som matchar hur verkliga scenarier kan se ut och utvärderas både som helhet och för varje enskilt scenario.

Resultaten visar att den bästa metoden av de som jämförs, den med högsta genomsnittliga genomströmning av operationer, är den där det bara finns ett lås som används för åtkomst till datastrukturen, vilket fungerar särskilt bra i jämförelse för när objekten är grupperade. En intressant funktion som visas skapa snabbare exekvering för det parallella arbetet är användningen av något som kallas dummy-lager. Att lägga till dessa i datastrukturen gjorde det möjligt att jobba mer parallellt på bekostnaden av att sätta en begränsning för objektets storlek.

Det huvudsakliga bidraget i detta arbete är den grund som den skapar för ytterligare arbete inom detta specifika område. På grund av bristen på tidigare arbete fanns det lite att gå på förutom att tolka lösningar för andra strukturer och det begränsade därmed mängden arbete som kunde utföras. Så med detta arbete är lösningar relativt enkla och baserade med olika huvudstrategier i åtanke. Detta gör det möjligt för framtida arbete att jämföras med dessa lösningar eller utveckla dem vidare om så önskas. Ett sekundärt bidrag är också resultat på hur prestandan för quadträd med loose-mekanism och buckets blir när den används med fyra skrivtrådar och två läsetrådar.