Parallellisatie van lineair algebraïsche operaties

Parallellisatie van lineair algebraïsche operaties
Promotoren: Yvan Saeys, Bart Goossens
Begeleiders: Jonas De Vylder, Joris Roels, Jan Aelterman
Probleemstelling
Lineaire algebra vormt de basis voor vele combinatorische en algebraïsche algoritmen in
dagdagelijkse toepassingen: beeld- en videoverwerking, computationele financiële analyse,
statistische data-analyse, enz. Deze algebraïsche operaties, b.v. het oplossen van een lineair stelsel,
worden typisch numeriek opgelost. Er bestaan al enkele decennia nauwkeurige en efficiënte
algoritmen voor het oplossen van verschillende numerieke problemen in de lineaire algebra (b.v.
Conjugate Gradient, LU-factorisatie, …) die goed werken op conventionele (seriële) machines. Dit
heeft geleid tot de ontwikkeling van een aantal efficiënte software-bibliotheken (JAMA, BLAS en
LAPACK)
Recent is de interesse voor het gebruik van parallelle systemen sterk toegenomen. Deze kunnen de
computationele werklast in complexe algoritmen significant verbeteren. Spijtig genoeg is het
parallelliseren van algoritmen en het aanspreken van parallelle hardware niet triviaal. Hedendaagse
(co-)processoren bestaan al uit een aantal processoren die parallel kunnen werken, maar het aantal
processoren en de specifieke karakteristieken van deze processoren hangt sterk af van de specifieke
hardware. Van een klein aantal processoren die complexe operaties kunnen uitvoeren voor een multicore CPU tot honderden processoren die gericht zijn naar de simpele taken op een GPU: deze
diversiteit heeft voor een groot aantal toepassingen het gebruik van parallelle algoritmen belemmerd.
Voor de applicaties waarvoor wel parallelle algoritmen ontwikkeld werden, resulteerde dit vaak in
een hardware-specifieke implementatie die moeilijk kan overgedragen worden naar andere hardware.
Doelstelling
Binnen deze thesis zullen we onderzoeken welke algoritmen voor het oplossen van lineaire stelsels
(bv LU-factorisatie of Successive Over-Relaxation) geparallelliseerd kunnen worden. Gebaseerd op
deze analyse zullen we bestaande algoritmen aanpassen en een nieuw parallel optimalisatie schema
voorstellen voor het numeriek oplossen van lineaire stelsels. Het nieuwe algoritme zal ontwikkeld
worden in functie van zowel de computationele snelheid als de numeriek stabiliteit. De ontwikkelde
technieken zullen getest worden op verschillende types van parallelle hardware (een multi-core
processor, een GPU of een combinatie van beiden) en er zal bestudeerd worden hoe de snelheid
schaalt met het aantal gebruikte cores.
De algoritmen zullen geïmplementeerd en getest worden in de programmeertaal Quasar. Deze
programmeertaal werd ontwikkeld binnen de universiteit Gent en laat geoptimaliseerde uitvoering op
heterogene hardware toe. Quasar is een eenvoudig te leren, high-level programmeertaal die hardware
onafhankelijk is. Quasar automatiseert multi-core en GPU programmering, wat het mogelijk maakt
om snel en eenvoudig GPUs en multi-cores te gebruiken voor parallelle berekeningen. Er is geen
voorkennis vereist over parallel programmeren, maar enige ervaring met high-level scripting talen
(bv. Matlab of Python) zal de overstap naar Quasar vergemakkelijken.

Download Report