Till innehåll på sidan

Batch-bearbetning för att utnyttja parallelism

Kandidate Examensarbete presentation

Tid: Må 2020-05-18 kl 16.00

Föreläsare: Emma Lind och Mattias Stahre

Plats: Zoom Meeting

Genom analysering av radarsignaler i en miljö kan nivån av hot bestämmas. Detta är en kritisk uppgift som måste lösas snabbt och med hög noggrannhet. För att kunna klassificera en specifik radar måste de elektromagnetiska pulserna identifieras. Vanligtvis sänder flera emittrar ut radarpulser samtidigt i en miljö. Dessa pulser måste sorteras i grupper, där varje grupp innehåller pulser från en och samma emitter. Målet med denna avhandling är att ta fram ett sätt att snabbt och korrekt sortera dessa pulser parallellt. Under det senaste decenniet har det skett en enorm utveckling inom GPU prestanda jämfört med CPU. Prestandafördelarna för en GPU kan dock endast utnyttjas genom att använda implementeringar som kan göra många beräkningar parallellt.

Denna avhandling utvärder hur en klusteringsalgoritm, när man skapar grupper av data, kan användas i ett realtidssystem. Den valda metoden använder grupper av data som analyserades parallellt för att nyttja fördelar med en GPU. Först behövde en klusteringsalgoritm väljas och därefter en optimal gruppstorlek för den valda algoritmen. Gruppstorleken baserades på att grupperna kunde behandlas parallellt och snabbt samt uppnå en hög tillförlitlighet av klusteringen.

En kvantitativ metod användes som baserades på experiment genom att mäta prestanda, noggrannhet och parallellitet som en funktion av gruppstorlek med avseende på den valda klusteralgoritmen. DBSCAN valdes som algoritm på grund av dess förmåga att hitta kluster av olika former och storlekar utan att på förhand ange antalet kluster för en mängd datapunkter samt dess låga tidskomplexitet.

Resultaten från utvärderingen visade att det är möjligt att implementera ett system med grupper av pulser och uppnå en god tillförlitlighet jämfört med en implementation av maximum likelihood-metoden. En optimal gruppstorlek i antal datapunkter är svårt att definera eftersom storleken är väldigt beroende på hur indata. En lösning skulle kunna vara att justera gruppstoleken efter indata.

Det uppstår en fördröjning i systemet som är beroende av skillnaden mellan gruppstorleken och exekveringstiden för att klustra gruppen. Denna fördröjning innebär att en gruppimplementation aldrig kommer kunna vara lika snabb på att producera sin utdata som en sekventiell implementation. Detta betyder att det i ett tidskritiskt system inte är optimalt med hög nivå av parallelitet.

Nyckelord:Parallellisering, GPU, Oövervakat lärande, Commodity GPU, Klustering, Signal Separation, DBSCAN