Masterproef T802 : Data-distributie op parallelle computers

Begeleiding:

Informatie:	Dirk Roose	Albert-Jan Yzelman
Promotoren:	Dirk Roose	Karl Meerbergen
Begeleider:	Albert-Jan Yzelman

Onderzoeksgroep:

Technisch Wetenschappelijk Rekenen en Numerieke Approximatie en Lineaire Algebra Groep

Context:

Wanneer de uitvoering van een programma teveel tijd kost of wanneer de data niet in het geheugen van de computer past, kan de uitvoering verspreid worden over meerdere computers, die tegelijkertijd aan het probleem werken, en dit zoveel mogelijk onafhankelijk van elkaar. Hierbij moet ook de corresponderende data over de computers verspreid worden. Deze stap, de data-distributie, gaat aan het eigenlijke parallelle werk vooraf, maar vaak is herdistributie nodig terwijl het parallelle rekenen aan de gang is.

Parallellisme speelt tegenwoordig ook een belangrijke rol binnen één enkele processor, waarin steeds meer kernen (cores) gebundeld worden. Hoewel deze kernen data kunnen lezen en schrijven in het hele geheugen van de processor, is data-distributie vaak nuttig omwille van de hiërarchische structuur van het geheugen.

Met hulp vanuit het Flanders ExaScience Life Lab zul je in dit project het probleem van datadistributie toepassen op generieke problemen, eerst op multicore architecturen, en later op een HPC cluster of supercomputer.

Doel:

Deze masterproef heeft tot doel parallelle data-distributies voor hypergrafen te ontwikkelen. Deze zullen worden toegepast in verscheidene toepassingsgebieden. De ontwikkelde distributiemethoden zullen worden geëvalueerd op verschillende architecturen en vergeleken met bestaande methodes.

Uitwerking:

Parallelle algoritmen en programma's en de data-afhankelijkheden tussen deeltaken worden vaak gemodelleerd als een hypergrafe. Een hypergrafe bevat, net als een normale grafe, vertices; maar in plaats van verbindingen, die telkens twee vertices bevinden, bevat een hypergraaf netten, die elk meerdere vertices kunnen bevatten. Om de data-distributiemethoden die je zal onderzoeken zo generiek mogelijk te houden, gaan we ervan uit dat we een hypergrafe distribueren.

Het doel van de data-distributie is om de vertices van de hypergrafe over de parallelle programma's te verdelen, zodanig dat de data toegewezen aan elke deeltaak zo veel mogelijk onafhankelijk is van de andere deeltaken. Immers, gedeelde afhankelijkheden vereist communicatie en synchronisatie. Deze communicatie- en synchronisatie-overhead moet geminimaliseerd worden. Tegelijkertijd willen we dat er maximaal gebruik gemaakt wordt van alle beschikbare cores, dus moet de data ook zodanig verdeeld worden dat elke deeltaak ongeveer evenveel werk heeft.

Het is ook de bedoeling om rekening houden met de verschillende eisen van communicatie over een netwerk ten opzichte van de veel snellere communicatie tussen cores binnen een processor. Voor experimenten zal gebruik worden gemaakt van HPC clusters van het Flanders ExaScience Life Lab en van het Vlaams Supercomputer Centrum.

Relevante literatuur:

Karen D. Devine et al., Parallel Hypergraph Partitioning for Scientific Computing, Parallel and Distributed Processing Symposium, 2006, IEEE, http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=10917

Profiel:

Gemengd theoretisch en praktisch werk.
Noodzakelijke voorkennis:
- asymptotische analyse van programmacodes;
- kennis van Java, C, of C++.
Het is nuttig om kennis te hebben van parallel programmeren (met bv. OpenMP, Cilk, BSP, of MPI) of het vak Parallel Computing gevolgd te hebben of te zullen volgen.

Deze masterproef is voor 1 student.