Het BSP-model

Arthur van Dam

[Homepage]

Oktober 1997

Bibliotheek-opdracht 1e jaar Computational Science


Over parallelle computer-systemen

In de huidige wetenschap is de computer een onmisbaar hulpmiddel voor het uitvoeren van uitgebreide berekeningen. Aangezien de berekeningen echter steeds complexer worden, zijn de huidige, op zichzelf staande computers niet altijd toereikend meer. Een andere methode is het systeem van parallelle computers. Wetenschappers zijn al jaren met deze vorm van berekenen aan het experimenteren. Er werd echter met slechte communicatie-netwerken gewerkt en om alsnog een redelijk snel systeem te krijgen, moest de software volledig op de architectuur van dat ene systeem afgestemd worden. Hierdoor was de software volledig incompatibel met andere systemen.

Door de vooruitgang in de technologie is men tegenwoordig echter in staat om gestandaardiseerde systemen te ontwerpen. Deze systemen bestaan uit ‘processor-memory pairs’, onderling verbonden door een communicatie-netwerk. Door het ‘direct remote access’-principe heeft elke processor toegang tot het geheugen van een ander pair, zodat onafhankelijke uitwisseling van data tussen de processoren onderling mogelijk is. Om deze systemen voor verschillende toepasingen te gebruiken, is software nodig die rekening houdt met en gebruik maakt van de bovengenoemde eigenschappen van de huidige parallelle systemen. Het veelbelovendste model met deze eigenschappen is het BSP-model.

Het BSP-model

Het BSP-model is een veralgemenisering van het PRAM-model, door Prof. L. G. Valiant van Harvard. Het is echter grondig uitgebreid door speciale werkgroepen aan de universiteit van Oxford. In een machine met p = M·N processoren verdeelt het BSP-model de elementen van een m x n matrix volgens de volgende formule:

waar , een twee-dimensionaal processor-nummer is.

Hoe werkt zo’n parallel systeem nu ongeveer? Ten eerste wordt er een parallel programma gemaakt, dat op alle processoren geïnitialiseerd wordt. Vervolgens worden alle processoren onderling gesynchroniseerd en alle verschillende geheugenlocaties geregistreerd. Alle individuele processoren moeten hun positie in het systeem kennen. Ook moet bekend zijn hoeveel en welke processoren in het systeem zitten. Hierna kan de verwerking en onderlinge uitwisseling van data beginnen. De uitwisseling geschiedt met zogenaamde ‘supersteps’ Deze bestaan uit kleinere stappen van datatransport tussen de processoren onderling. Aan het eind van de ‘superstep’ worden de processoren weer gesynchroniseerd (in gelijke staat gezet) zodat de verschillende stappen toch parallel zijn verlopen. Dit synchroniseren wordt ‘barrier synchronisation’ genoemd.

Uit voorgaande uitleg van het BSP-model wordt meteen de afkorting BSP duidelijk.
BSP staat voor Bulk Synchronous Parallel. Er wordt namelijk een parallel systeem beschreven, waarin ‘bulk-hoeveelheden’ gegevens worden verwerkt door de verschillende processoren na iedere ‘superstep’ te synchroniseren.

De volledige verwerking van gegevens in een parallelle computer met behulp van matrix-operaties voert voor dit korte verslag te ver. Wel is het verstandig nog naar een ander punt te kijken: de kostenfunctie bij een parallel systeem.

Het communicatie-netwerk heeft slechts een bepaalde capaciteit voor data-transport. De processoren kunnen dus niet onbeperkt data verzenden en ontvangen. Om deze reden moeten de verschillende stappen in het BSP-model bekeken worden en moet een goede, voordelige balans gevonden worden. Zo ontstaat een evenwichtig systeem dat maximaal presteert.

Om dit evenwicht te kunnen vinden, is een schematische voorstelling van het systeem nodig. Het BSP-model doet dit op de volgende manier. De snelheid van het systeem hangt af van de tijd die nodig is voor één operatie, een ‘tijdsstap’. Als we deze ‘tijdsstap’ als de tijdseenheid nemen, komen we op de volgende variabelen:

De processor-snelheid heeft alleen een normaliserende invloed, dus blijven er drie variabelen over: p, l en g.

Voor een snel systeem moet l een lage waarde hebben, want dan is er minder tijd nodig voor ‘barrier synchronisation’. Het systeem moet echter ook evenwichtig zijn, dus moet de capaciteit van de processoren ongeveer aansluiten bij die van het communicatie-netwerk. Dit houdt in dat het aantal stappen dat gedaan had kunnen worden tijdens het transporteren van één woord, ongeveer gelijk aan 1 moet zijn. Dan worden er in één seconde ongeveer net zo veel waarden berekend als er in één seconde door het netwerk getransporteerd kunnen worden. Het lijkt vanzelfsprekend dat bij een hogere waarde van p (meer processoren) het systeem sneller werkt. Als de capaciteit van het communicatie-netwerk hier echter niet op aangepast wordt, zal geen verbetering optreden. De ‘in- en uitgangen’ van het communicatie treden namelijk op als soort ‘flessenhalzen’.

Als met bovenstaande variabelen rekening wordt gehouden, lijken parallelle computers mij een duidelijke vooruitgang. De ontwikkelingen in de wetenschap blijven doorgaan en het gebruikte materiaal moet de berekeningen uit die nieuwe ontwikkelingen aankunnen. Natuurlijk moet dit in combinatie gaan met ontwikkeling van goede software voor parallelle systemen. Na een eerste kennismaking met het BSP-model, lijkt dit model mij goed geschikt voor verdere ontwikkeling en toepassing in parallelle systemen.

Het BSP-model is echter niet het enige model voor parallelle systemen. Twee andere modellen zijn PVM en MPI. PVM was het eerste model voor parallel programmeren. Het was niet systematisch opgezet, maar bestond slechts uit een verzameling van bijeengeraapte functies, die de nieuwe vorm van programmeren mogelijk maakten. PVM wordt steeds minder gebruikt. MPI is een systematische uitbreiding van PVM, maar is erg uitgebreid en dus niet zo snel te leren. Toch wordt MPI op dit moment het meest gebruikt. BSP heeft dezelfde mogelijkheden als MPI, met dit verschil dat bij BSP een kostenmodel is opgesteld, zodat het model veel efficienter werkt. Waren er in MPI 10 commando’s om 1 doel te bereiken, in BSP is er 1 algemeen commando. BSP is dus veel algemener en systematischer van opzet. Op dit moment wordt MPI nog het meest gebruikt, maar BSP is sterk in opkomst. Dit lijkt me een goede ontwikkeling, want het is natuurlijk belangrijk dat programma’s naast doeltreffend, ook rendabel zijn. Het BSP voldoet volgens mij aan deze eisen.