nederlandse organisatie voor wetenschappelijk onderzoek


nieuw algoritme minimaliseert datauitwisseling

wiskundigen aan de katholieke universiteit nijmegen hebben een indelingsalgoritme ontworpen, waarmee rekentaken sneller evenredig onder processoren kunnen worden verdeeld. de processoren hoeven in het algoritme tijdens de indeling vijf keer minder data uit te wisselen. data-uitwisseling is een van de meest tijdrovende zaken bij computerberekeningen waarin processoren gelijktijdig deelproblemen oplossen (parallelle systemen). het project werd gefinancierd door het nwo-gebied exacte wetenschappen.

in het nieuwe algoritme worden de berekeningen voor de verdeling van rekentaken goeddeels gedelegeerd naar de processoren en niet op centraal niveau uitgevoerd. uit simulaties blijkt dat de werkverdelingen die het nieuwe algoritme produceert even goed in balans zijn als de oudere.

de wiskundigen ontwikkelden hun algoritme voor een computerbenadering om bijvoorbeeld de concentratie en druk van toegevoegde deeltjes in een complexe tweedimensionale stroming te benaderen. de computer berekent deze grootheden door een ruimtelijk rooster, bijvoorbeeld van driehoekjes, over de stroming te leggen. de concentratie of druk in een driehoek is te bepalen uit de concentratie of druk in de aangrenzende driehoekjes met de zogeheten behoudsvergelijking.

met een foutschatter wordt vervolgens geschat hoe veel de berekende concentratie binnen een driehoek afwijkt van de werkelijke. de computer deelt hierna alle driehoeken met een grote geschatte fout verder op, en begint een nieuwe berekening. door deze locale verfijning neemt het aantal driehoekjes in een deel van het rooster gedurende het rekenproces niet evenredig toe.

in het programma is nu een bewerking ingebouwd die het rekenwerk zo verdeelt dat de andere processoren niet op de processor met de grootste rekentaak hoeven te wachten. elke processor houdt zich hierbij bezig met een deel van het rooster en zijn rekentijd hangt af van het aantal driehoekjes in hun deel. bij de herverdeling moeten er zo weinig mogelijk driehoekzijden op de grens van twee deelroosters liggen, omdat de processoren hiervoor data moeten uitwisselen (externe koppelingen).

in het nieuwe algoritme laten de wiskundigen de computer een klasse werkverdelingen doorlopen die in balans zijn en kiest de computer die verdeling waarbij het aantal externe koppelingen minimaal is. de processoren berekenen hierbij zelf hoeveel minder externe koppelingen zij zouden hebben bij kleine verleggingen van de grens tussen twee deelroosters. daarna laten de wiskundigen de processoren paarsgewijs kleine stukjes van het rooster onderling uitwisselen.

nadere informatie bij:

* drs. leendert vijfvinkel (kun)

* tel. (024) 3652489, fax (024) 3652140

* e-mail vijfvink@sci.kun.nl

Deel: ' Nieuw algoritme minimaliseert datauitwisseling '




Lees ook