Betawetenschappen
Promotie

Herordening van data voor snellere berekeningen 

Voor computers maakt het uit in welke volgorde ze gegevens behandelen. Albert-Jan Yzelman heeft in zijn promotieonderzoek bestaande technieken, oorspronkelijk bedoeld voor het verdelen van gegevens, aangepast en uitgebreid zodat het herordenen van data mogelijk wordt. Dit herordenen zorgt ervoor dat de nieuwe volgorde van gegevens de computerberekeningen veel sneller maken. Hiermee heeft de promovendus een tijdswinst van meer dan 300% behaald op grote ongestructureerde gegevens.

Tussen de processor van een computer en het interne geheugen van die computer, zijn meerdere steeds kleinere (maar snellere) stukjes geheugen te vinden. Deze `caches' worden gebruikt om gegevens die het meest recent nodig waren, dichtbij de processor te houden. Voor gestructureerde problemen levert dit een snelheidswinst op: als recente gegevens weer nodig zijn kunnen die uit het snelle geheugen worden gehaald, in plaats van uit het langzamere grotere geheugen. Echter zijn lang niet alle interessante problemen gestructureerd, en als er te vaak gerefereerd wordt aan het langzame geheugen, is de processor vaker bezig met wachten op gegevens in plaats van het daadwerkelijk verwerken van die gegevens.

De door Yzelman gevonden oplossing begint met het analyseren van afhankelijkheid tussen gegevens. Vervolgens worden gegevens in twee groepen ingedeeld, zodanig dat de groepen zo min mogelijk van elkaar afhankelijk zijn. Elk van die twee stukken kan vervolgens op eenzelfde manier verder gesplitst worden. Gebaseerd hierop kunnen gegevens geordend worden, zodanig dat data in kleinere groepen worden behandeld en dus beter in de caches passen.

Datum en tijd: 3/10/2011 16:15
Locatie: Academiegebouw, Domplein 29, Utrecht
 
Promovendus: Albert-Jan Yzelman 
Faculteit: Faculteit Bètawetenschappen
Proefschrift: Fast sparse matrix-vector multiplication by partitioning and reordering 
Promotor 1: Prof. dr. Rob H. Bisseling