Inleiding

Capaciteitsvergroting

In het vakgebied van de Computational Science, wordt veelvuldig gesimuleerd. Dit wordt vaak gedaan door een (continu) proces te bekijken op een tijdsinterval, dat wordt opgesplitst in veel deelintervallen. Aan het eind van ieder deelinterval, wordt een voorspelling over (een grootheid in) het proces gedaan. Voor nauwkeurige simulaties, moeten de deelintervallen zeer klein zijn, zodat onnauwkeurigheden uit de voorspelling slechts beperkt doorwerken in het uiteindelijke antwoord. Natuurlijk vergt dit steeds meer van de gebruikte hardware. Wanneer je reeds over goede apparatuur beschikt, kun je nog een andere methode gebruiken, voor capaciteitsverhoging.

Paralelle systemen

Om een probleem op te lossen, dat veel hardware-capaciteit vergt, kun je meerdere workstations tegelijk op hetzelfde probleem loslaten. In het vervolg praten we over workstations met elk één processor, die via een netwerk met elkaar verbonden zijn. Iedere processor voert bepaalde bewerkingen uit en rapporteert de resultaten aan de processoren die daar om 'vragen'.
De eerste vraag is nu, hoe alle bewerkingen over de processoren te verdelen. Bewerkingen die veel uitkomsten van elkaar nodig hebben, kunnen het beste door één processor worden uitgevoerd, zodat deze nauwelijks met andere processoren hoeft te communiceren over benodigde gegevens.
Vervolgens moet het communiceren geordend verlopen, zodat een processor pi niet lang moet wachten voordat pj de benodigde resultaten heeft berekend en kan versturen. pi moet dus niet pas beginnen met rekenen wanneer pj erom 'vraagt'. Bovendien moeten niet allerlei processoren tegelijk aan één processor data 'vragen' of sturen, om opstoppingen te voorkomen.

BSP-model

Het BSP-model voldoet aan de hiervoor genoemde eisen. Het BSP-model (Bulk Synchroon Parallel) van Prof.L.G. Valiant (Zie:[5]) laat de processoren in een superstap met elkaar communiceren volgens een bepaald matrix-schema, zodat nooit meerdere processoren tegelijk met eenzelfde processor willen communiceren. Iedere superstap wordt afgesloten door een globale synchronisatie. In deze slotfase worden de processoren onderling weer 'gelijkgezet', zodat het proces parallel blijft verlopen. In de volgende superstap hoeven de processoren nu nauwelijks op elkaar te wachten, omdat ze gelijk met elkaar gestart zijn.(Uit:[2] en [3])

Het kostenmodel voor BSP is van de vorm a+bg+cl, waarin a, b en c scalaire waarden zijn, die in het ideale geval respectievelijk de volgende waarden hebben: 1, 0 en 0. Hierin wordt a beïnvloed door het algoritme, b door de communicatie en c door de synchronisatie. Vooral b blijkt af te hangen van de verdeling van de deelproblemen over de processoren. De synchronisatie laten we in dit practicum buiten beschouwing. Wij houden ons slechts bezig met het optimaliseren van de verdeling over de processoren en hebben dus voornamelijk te maken met b. Wanneer b=0 is de communicatie gratis (ideaal). In de praktijk blijkt b vaak groter dan 1 te zijn.

CS-practicum

Tijdens dit practicum werken we aan de hand van een practicumopdracht (Zie:[4]) en maken wij gebruik van een concreet voorbeeld, dat in de probleemstelling besproken zal worden. De verdeling over de processoren zal eerst random of gebalanceerd worden aangebracht, waarna deze geoptimaliseerd wordt door middel van Simulated Annealing. Alle technieken worden uitgevoerd door zelfgeschreven JAVA-programma's, waarvan ook de listings te zien zijn.