Probleemstelling

Metalen plaat

Processorverdeling over het roosterTijdens dit practicum hebben we een vierkante metalen plaat bestudeerd, waarvan de temperatuursverdeling plaats- en tijdsafhankelijk is. Zoals in de inleiding werd vermeld, gaan we ook hier weer het domein in deelintervallen opsplitsen. We discretiseren de metalen plaat tot een k x k-rooster. Iedere ingesloten cel heeft een bepaalde temperatuur. De temperatuur van iedere cel is bij één van de p processoren bekend. Wanneer we iedere processor door een bepaalde kleur voorstellen, kunnen we iedere cel zijn eigen kleur geven. Een voorbeeld hiervan bij k=10 en p=7, is hiernaast te zien.

Communicatie

Om de temperatuursverdeling te kunnen simuleren, is het belangrijk te weten volgens welk proces dit gebeurt. Wanneer er in een klein gebied temperatuursverschillen bestaan, zullen deze verschillen elkaar 'middelen', zodat de temperatuur steeds meer een gemiddelde waarde aanneemt. In deze situatie stellen we dat een cel alleen door zijn noord-, zuid-, oost- en westbuur-cellen beïnvloed wordt. De temperatuur van een cel op tijdstip tj is dus het gemiddelde van de temperatuur van zichzelf en zijn vier directe buren op tijdstip tj-1. Een verdeling over de processoren vinden we goed, wanneer de kosten minimaal zijn. Het berekenen van een nieuwe temperatuursverdeling gebeurt in twee stappen: Schema voor communicatieregels Om de kosten te bepalen moeten we eerst beschouwen wat er gecommuniceerd wordt tussen de verschillende processoren.
Hiernaast is een schematische voorstelling van een cel met zijn buurcellen te zien, met de kleuren voor de processoren. De processor die cel A 'beheert' moet de temperatuur van de buurcellen B, C, D en E weten. We beschouwen het probleem echter van de ander kant: de processoren die de buurcellen 'beheren' moeten allemaal de temperatuur van A (TA) weten en daarom stuurt de processor die A 'beheert' (PA) dit gegeven naar de betreffende processoren. (Wanneer de buurcellen dit ook doen, ontvangt de 'beheerder' van cel A vanzelf alle informatie over de vier buurcellen.) Wanneer de processor van een buurtcel echter dezelfde is als PA - zoals PB - hoeft TA niet naar PB verstuurd worden, omdat deze TA reeds weet. Wanneer een processor, zoals PC reeds TAheeft ontvangen, maar ook een andere buurcel van A - zoals E - 'beheert', hoeft deze niet nogmaals TA te ontvangen. Kort gezegd moet PA dus eenmalig verzenden naar cellen met een andere kleur dan zijn eigen kleur.

Kosten

Om de kostenfunctie voor één 'slag' in het simulatieproces op te stellen, moeten we met twee dingen rekening houden:

  1. De communicatiekosten: Aangezien alle processoren hun werk tegelijk doen, worden de kosten alleen bepaald door de processor die het langst bezig is. We moeten dus het maximum van de verzend- (hs) en ontvangstkosten (hr) van alle processoren nemen. Dit maximum geeft enkel aan, hoe vaak er is gecommuniceerd. Dit aantal moet dus nog met een platformafhankelijke constante worden vermenigvuldigd. Deze maat voor de communicatiekosten noemen we g.
  2. De berekeningskosten: Voor het berekenen van een nieuwe temperatuur voor één cel, moeten vier optellingen worden gedaan en vervolgens één deling. Ook hier bepaalt de processor die het langst bezig is (= die de meeste cellen 'beheert') de kosten. De kosten zijn dus vijf maal het maximum aantal cellen per processor.
De totale kosten worden nu dus gegeven door:

, waarin en is vijf maal het maximum aantal cellen per processor.

Met bovenstaande kennis willen we de verdeling met de laagste kosten vinden. Hiervoor gebruiken we Simulated Annealing.