Parallelliseren van Fractalberekeningen met Boost/C++

Spreker: Eric L. Meijer

Abstract

Elmfract is een fractalgenerator met als doel het genereren van mooie plaatjes. Het programma genereert voornamelijk strange attractors van iteratieve functiesystemen. Een iteratief functiesysteem bestaat uit twee of meer geometrische transformaties die op een punt in de ruimte (voor elmfract twee- of drie-dimensionaal) werken. De transformaties zijn combinaties van spiegelingen, rotaties, en schalingen, en bevatten altijd minstens een verkleinende schaling. Het bedenken van nieuwe transformaties leidt steeds weer tot verbazende nieuwe vormen.

Voor het op hoge resolutie uitrekenenen van vooral drie-dimensionale fractals moeten grote aantallen punten worden uitgerekend, tot in de biljoenen (echte biljoenen, geen Amerikaanse), en dergelijke berekeningen kunnen meerdere weken in beslag nemen. Daarom ligt een gecompileerde taal voor de hand. Het domein leent zich voor een objectgeoriënteerde aanpak, wat (in 1999) leidde tot de keus voor C++. Toen multi-core processoren hun intrede deden in het hobby-segment ben ik de berekeningen gaan parallelliseren. De Boost library biedt een goed bruikbare abstractie van threading in C++, waar standaardisatie ontbreekt.

(Klik op de plaatjes voor een vergroting, en zie emweb.nl)

De berekening van een fractalplaatje verloopt in twee fasen. In de eerste fase worden punten gegenereerd via een backtracking algoritme. Deze punten worden door een rendererklasse gebruikt om een intermediaire structuur in het geheugen op te bouwen (je kunt niet alle biljoen punten bewaren). In de tweede fase genereert de renderer het plaatje uit de intermediaire structuur.

Parallellisatie van de eerste fase geschiedt door de backtrack-boom op gepaste hoogte “door te zagen”, en de afgezaagde takken als taak aan meerdere threads uit te delen. Bij de renderer wordt er gesynchroniseerd door een locking strategie. In fase twee kan een veel simpeler parallellisatie plaatsvinden door de scanlines te verdelen over verschillende threads. Gebruik van C++ const methods kan helpen om race-condities te voorkomen.

Biografie

Eric studeerde Scheikundige Technologie aan de TU Eindhoven, gevolgd door een promotieonderzoek in de theoretische chemie (“Quantum Mechanical of Infrared Spectra of Acidic Zeolites”, 2000). Vanaf 2000 is hij werkzaam bij Philips Medical Systems in Best, aanvankelijk als software engineer in de software voor MRI systemen. Na verschillende technische posities nu software architect voor medische applicaties op het Intellispace Portal client server platform.

Zijn affiniteit met unix ontstond tijdens het afstuderen en promotieonderzoek waar grootschalige berekeningen werden gedaan op unix workstations (DEC, SGI) en “supercomputers” zoals de Cray-MP van SARA. Tijdens het promotieonderzoek werd geprogrammeerd in FORTAN, C, C++, en raakte hij verzeild in systeembeheerklussen.

Hobbies zijn fractals genereren met eigen programmatuur (C++, Debian), klassiek gitaar spelen en wandelen.