Practicum

Het doel van dit practicum is niet om het temperatuursverloop in een metalen plaat te simuleren. Wij willen slechts een zo goed mogelijke verdeling van alle cellen over de processoren realiseren. We maken eerst een beginverspreiding en laten deze vervolgens door middel van Simulated Annealing verbeteren.

Beginspreiding

Er zijn verschillende methoden om een beginspreiding aan te brengen.

Om het komende optimaliseringsproces een 'eerlijk' begin te geven, kunnen we de beginspreiding volledig random aanbrengen. In ons programma hebben we dit in de methode randomGrid geïmplementeerd. In een dubbele for-lus wordt het hele grid langs gelopen en voor iedere cel wordt een random geheel getal tussen 0 en p-1 bepaald door (int)Math.random()*proc. De cast naar een int levert een geheel getal, omlaag afgerond op. Hiermee wordt de kleur van die cel bepaald.

Nadeel van bovenstaande methode is dat de hoeveelheid cellen per processor nogal kan variëren. Wanneer één processor veel meer cellen beheert dan de anderen, kunnen de communicatiekosten wel geoptimaliseerd worden, maar de berekeningskosten voor die ene processor zijn zo hoog, dat die in de kostenfunctie domineren. We zouden daarom de processoren weliswaar random moeten verspreiden, maar grenzen stellen aan de aantallen. We hebben dit in de methode balancedGrid() geïmplementeerd. Deze methode geeft iedere processor aanvankelijk een even grote kans om aan een cel toegewezen te worden. Iedere processor mag evenveel cellen beheren en heeft dus aanvankelijk een kans p=#cellen/#processoren. In de array cum_kans[] worden de cumulatieve kansen opgeslagen, dus de som van de kans van de processor zelf en die van de voorgaande processoren. De cellen worden weer langsgelopen in een dubbele for-lus, waarin telkens een nieuw random getal wordt bepaald. Dan wordt bepaald welke processor daarbij hoort, door te kijken tussen welke twee kansen uit de array dit random getal valt. De huidige cel krijgt die bewuste processor toegewezen en vervolgens worden de kansen aangepast. Wanneer een processor een cel krijgt 'toegewezen' wordt het aantal cellen dat hij nog mocht beheren met 1 in mindering gebracht. Het totaal cellen, dat nog 'ongekleurd' was is ook 1 minder geworden en dus veranderen alle kansen. Als bijvoorbeeld bij een bepaalde verdeling processor 3 (nr. 2) van de 7 wordt toegewezen, op het moment dat er nog 22 'ongekleurd' zijn, worden de kansen voor en na de toewijzing gegeven door:

proc.nr: 0 1 2 3 4 5 6  
# over, voor: 2 3 7 1 0 4 5 restvoor: 22
kans voor: 2/22 5/22 12/22 13/22 13/22 17/22 22/22 (cumulatief)
# over, na: 2 3 6 1 0 4 5 restna: 21
kans na 2/21 5/21 11/21 12/21 12/21 17/22 21/21 (cumulatief)

Algemeen geldt: wanneer uit proc processoren, nr. p wordt 'gekozen', dan geldt het volgende voor de nieuwe kansen:

Afhankelijk van hoe vaak een processor reeds is toegewezen, heeft hij nog een bepaalde kans om aan een cel toegewezen te worden. De methode balancedGrid() bepaalt dus met deze kansen, welke processor er aan iedere cel wordt toegewezen. Zo ontstaat een verdeling met (vrijwel) gelijke aantallen van ieder processor, zodat de berekeningskosten sowieso al minimaal zijn.

Kostenbepaling

Dit hele practicum draait om kostenvermindering, dus is het belangrijk om de kosten van een bepaalde configuratie snel en goed te kunnen bepalen.

Wanneer voor een volledig nieuwe situatie de kosten bepaald moeten worden, moet het hele grid in een dubbele lus langsgelopen worden. Dit is geïmplementeerd in de methode compCosts. Om de taken goed te verdelen is een methode addCellComms geschreven. Deze methode bepaalt het aantal verzendingen voor één cel met opgegeven i- en j-coördinaten, en het aantal ontvangsten voor de buurcellen daarvan. Het bepalen van het aantal communicaties, wordt gedaan door de nummers van de processoren van de cellen te vergelijken. De redenering die daarbij gevolgd wordt, staat in de probleemstelling.
Als eerste wordt de gekeken of de noorderbuur geldig is. Zo ja, wordt hij vergeleken met de middencel en worden eventuele communicaties opgeteld. De variabele n krijgt het nummer van de noorderbuur toegewezen. Indien de noorderbuur niet geldig is, worden geen kosten bepaald, maar krijgt n het nummer van de middencel toegewezen. De kleur van de middencel wordt toegekend, zodat er geen communicatiekosten in rekening worden gebracht (buren met de zelfde kleur) voor een niet bestaande cel. De oost-, zuid- en westburen worden ook op hun geldigheid gecontroleerd en eventueel met de middencel en voorgaande buurcellen op kleur vergeleken. De kleur van iedere buurcel (behalve west, want dat is de laatste) wordt - afhankelijk van zijn geldigheid - in een tijdelijke variabele n, o of z opgeslagen, zodat volgende buurcellen zonder problemen met hun (misschien niet bestaande) voorgangers vergeleken kunnen worden. Aangezien verschillende methoden de verzend- en ontvangstkosten van alle processoren willen weten, hebben we hiervoor twee arrays hs[] (send) en hr[] (receive) als klasse-variabelen aangemaakt. Methode addCellComms voegt de bepaalde aantallen communicaties voor een cel toe aan de reeds bepaalde communicaties in deze twee arrays. Het is nu wel zaak, om vòòr de dubbele for-lus in compCosts, de twee arrays op nul te zetten, zodat in het verleden berekende kosten niet meer meetellen.
Wanneer de dubbele lus voor het hele grid is afgerond, wordt het maximum van de getallen uit de hs[] en hr[] bepaald en vermenigvuldigd met g.
Hierna moeten de berekeningskosten nog bepaald worden. In de dubbele lus is reeds een array 'gevuld', waarin het aantal cellen staat dat door iedere processor 'beheert' wordt. Ook hiervan wordt het maximum bepaald en met vijf vermenigvuldigd. De som van de communicatie- en berekeningskosten wordt geretourneerd. De bepaling van het maximum van getallen uit een array wordt uitgevoerd door findMax.

Wanneer slechts enkele cellen veranderd zijn, hoeft natuurlijk niet het hele grid langsgelopen te worden. Het is veel sneller om te bepalen, in welke mate de kosten veranderd zijn door deze verandering van enkele cellen en vervolgens deze kostenverandering op te tellen bij de kosten van vòòr de verandering. De situatie dat er slechts enkele cellen veranderen, treedt alleen op tijdens de optimalisatie. Aldaar wordt uitgelegd hoe het hiervoor beschreven idee geïmplementeerd wordt. De optimalisatiemethode retourneert na zijn optimalisatie het kostenverschil, zodat de totale kosten veel sneller bekend zijn.

Optimalisatie

Zoals beschreven in Simulated Annealing, wordt voor een huidige situatie een willekeurige buursituatie gekozen, en worden de kosten voor en na de verandering vergeleken. Het kostenverschil bepaalt de kans, waarmee de wisseling wordt toegestaan.
In de methode optimize worden de i- en j-coördinaat van een willekeurig punt bepaald. Vervolgens bepaalt een willekeurig gekozen getal uit 0, 1, 2 en 3 of met respectievelijk de noord-, oost-, zuid- of westbuur gewisseld gaat worden. De methode validNode bepaalt of de cellen niet buiten het grid vallen door de volgende eis te stellen:

Indien de bepaalde buurcel niet geldig is, wordt net zo lang een andere gezocht, totdat er één wel geldig is. Een wisseling wordt aangegeven met zijn richting en zijn pivot: dit is de linkse of bovenste cel (rood aangegeven in onderstaande figuur). Er zijn vier mogelijke wisselingen, die op de volgende manieren zijn gedefiniëerd:
  1. Noord met midden, verticaal, pivot = noord.
  2. Oost met midden, horizontaal, pivot = midden.
  3. Zuid met midden, verticaal, pivot = midden.
  4. West met midden, horizontaal, pivot = west.
Deze vier mogelijke situaties worden geëvalueerd door de twee methoden horizontalSwap en verticalSwap, die de coördinaten van het linker respectievelijk bovenste punt als parameter meekrijgen. Bij een wisseling zijn, wat de communicatiekosten betreft, acht cellen betrokken (Zie de twee schema's in de listings). De twee methoden controleren van alle acht betrokken cellen of ze geldig zijn en roepen voor de geldige cellen de methode substractCellComms aan om de oude kosten af te trekken in de arrays hs[] en hr[] die de communicatiekosten over het hele grid bewaren. De methode substractCellComms werkt hetzelfde als addCellComms, met als enig verschil, dat de bepaalde communicaties voor een cel worden afgetrokken van de reeds bepaalde communicaties in de twee communicatie-arrays.
Vervolgens worden de cellen gewisseld en de nieuwe kosten voor de acht betrokken cellen opgeteld door addCellComms. Hierna worden de communicatiekosten voor en na de wisseling bepaald door de maxima van de oude- en nieuwe hs[] en hr[] te bepalen (de rekenkosten zijn gelijk gebleven). Aan de hand hiervan wordt bepaald met welke kans de wisseling blijft, en eventueel wordt de wisseling nog ongedaan gemaakt. De methode retourneert het kostenverschil. De methode optimize doet het wisselen in een for-lus, zodat een groot aantal wisselingen wordt geprobeerd. De lusgrootte wordt als parameter meegegeven, zodat de gebruiker deze zelf kan aanpassen als het programma loopt. Uiteindelijk retourneert deze methode het totale kostenverschil van alle gedane wisselingen, zodat in de applet de nieuwe kosten op het scherm gezet kunnen worden.

Interface

Om bovenstaande methoden gebruikersvriendelijk te maken, hebben we een applet gemaakt, die de mogelijkheid biedt om zelf allerlei parameters in te voeren, die invloed hebben op het verdelings- en optimalisatieproces. Voor de optimalisatie maken we gebruik van een thread, die een oneindige optimalisatie-lus start, maar wel zelf meteen stopt, zodat de gebruiker toch nieuwe commando's in kan geven.

Applet

Hieronder is de applet te zien, waarmee je zelf kunt experimenteren. Eerst nog even een korte uitleg van de verschillende onderdelen:
gridsize k: Het aantal cellen in de breedte (en de hoogte)
Number of procs: Het aantal processoren dat cellen beheert
Communic. costs: De communicatieconstante g, een maat voor de communicatiekosten
Initial T: De begin-koeltemperatuur, waarmee Simulated Annealing rekent
Cooling speed: De koelingsfactor, waarmee T vermenigvuldigd wordt na één koelperiode
Cooling period: Het aantal celwisselingen, dat wordt geprobeerd, voordat T wordt verlaagd (lusgrootte van optimize)
Generated grid: De verdeling over het grid; volledig random, of met gelijke aantallen van processoren (balanced)
Reset: Zet de bovengenoemde parameters op hun standaardwaarde en herverdeelt het grid
Redistribute: Herverdeelt het grid met de opgegeven parameters
Start/Stop: Start of stopt de optimalisatie van de huidige optimalisatie
Pause/Resume: Pauzeert en hervat de op dat moment actieve optimalisatie
Total costs: De totale kosten, voor de huidige configuratie
Difference: Het verschil (in %) van de huidige kosten, t.o.v. de kosten waarmee gestart werd
Minimum costs: De minimale kosten die ooit in de op dat moment actieve optimalisatie zijn gehaald, en het percentage t.o.v. de beginwaarde
In de status-balk onderin je browser, is de status van de applet te zien.
Wat de animatie betreft, wanneer een andere actie plaatsvindt, anders dan 'Pause' of 'Resume', wordt de optimalisatie gestopt, en de nieuwe actie afgehandeld. Het zou ook niet zinnig zijn om tijdens de optimalisatie het grid of andere parameters te veranderen. Hierop is wel één uitzondering: de koelperiode. Het is mogelijk om deze tijdens de optimalisatie te veranderen. Zorg dan wel dat je na het aanpassen van het getal, de nieuwe periode niet met [Enter] bevestigt, want dan wordt alsnog de optimalisatie gestopt. Zorg er ook voor dat tijdens het aanpassen van het getal er altijd een geldig getal in het TextField blijft staan, want de thread kan ieder moment, zonder voorafgaande actie, de inhoud ervan proberen te lezen. Indien het getal ongeldig is, 'throwt' hij een NumberFormatException. De waarden die 'Reset' oplevert, zijn waarden, waarbij een snel resultaat verkregen wordt. De afmetingen het en aantal processoren, kunnen naar eigen smaak worden aangepast. De keuze van de initiële T, is echter minder willekeurig. Het idee van Simulated Annealing schrijft voor dat deze flink wat groter is dan het maximale kostenverschil. Zodoende is de kans op wisseling bij een verhoging van de kosten aanvankelijk toch nog behoorlijk groot. Bij aanpassing van g, moet T dus ook veranderd worden. De maximale kostenverandering bij g=1, is ongeveer 5. In het algemeen is het verstandig om T minstens tien maal zo groot als g te nemen. Bij hoge initiële T, duurt het vaak wel lang voordat er daadwerkelijk optimalisatie te zien is. Voor een snel resultaat, kan het beste een niet te groot grid genomen worden, met niet te veel processoren. Probeer bijvoorbeeld eens een grid van vier bij vier uit met vier processoren en vergelijk het uiteindelijke resultaat met de animatie linksboven (Er zijn twee mogelijke minimum-configuraties). Bij grotere grids is duidelijk te zien, dat de optimalisatie vrijwel alleen naar een diagonale structuur neigt. Reden hiervoor is, dat in een diagonale structuur twee 'kleur-gebieden' het meest contact met elkaar maken, terwijl er weinig gecommuniceerd hoeft te worden. In het ideale geval, zouden er dus perfecte ruiten van iedere kleur ontstaan. Bij grotere grids, wil het echter nogal eens gebeuren, dat er afzonderlijk van elkaar, kleine gebiedjes van dezelfde kleur ontstaan. Deze zitten vaak te ver weg om nog naar elkaar toe te kunnen 'schuiven'.

Opmerking: De applet is getest en werkte in de appletviewer. Netscape Navigator geeft echter soms wat problemen met de juiste afhandeling van threads. Zo functioneert de 'Pause'-knop niet altijd zoals het hoort.

Experimentele resultaten

Om de invloed van de parameters te onderzoeken, hebben we voor verschillende grids optimalisaties uitgevoerd. Als eerste hebben we een grid van 50 bij 50 met 10 processoren genomen. Bij een lange optimalisatie (4 uur op een Pentium 233MMX met 64 MB RAM) waren de parameters: g = 10, T = 100, koelperiode = 50000, koelfactor = 0.98. We stopten de optimalisatie na 2506 periodes van 50000 mogelijke wisselingen. Er waren dus meer dan 125 miljoen wisselingen geprobeerd! Het resultaat was een kostenafname met 69,5 %. Duidelijk de moeite waard dus.
Hetzelfde grid lieten we optimaliseren bij dezelfde g, maar met T = 10, koelperiode = 1000 en koelfactor = 0.8. Deze optimalisatie is natuurlijk veel greedy'er. Door de korte koelperiode en de sterke koelfactor, was de T al na 20 minuten tot 10^-250. De overgangskans bij een verslechtering is dan al vrijwel 0. Toch blijken vooral de eerste periodes nog een redelijke kostenvermindering te veroorzaken. Na zo'n 25 minuten was T = 1E-323, en op dat moment veranderde T niet meer. De kosten waren 5250, wat neerkomt op een afname van nog ruim 42 %.
Configuratie na lange optimalisatie Configuratie na korte optimalisatie
Lang: Kosten = 2780 Kort: Kosten = 5250
Voor een grid van 10 bij 10 experimenteerden we met het aantal processoren. De overige parameters waren g = 10, T = 100, koelperiode = 5000, koelfactor = 0.98. Bij 2 processoren was de optimalisatie al voltrokken na 200 periodes van 5000. De kosten stonden toen op 350, een afname van bijn 51 %. Bij tien processoren, echter, was er na 200 periodes nog geen optimalisatie te zien. Na 800 periodes van 5000 was dit wel het geval. De kosten stonden toen op 170, een afname van bijna 53 %.
Configuratie met 2 processoren Configuratie met 10 processoren
2 processoren: Kosten = 350 10 processoren: Kosten = 170
Tenslotte hebben we nog geëxperimenteerd met verschillende waarden van g. De overige parameters waren hierbij gridsize = 20, 3 processoren, T = 10·g, koelperiode = 5000, koelfactor = 0.98. Bij kleine waarden van g (<1) verwachten we slechts beperkte optimalisatie, omdat de rekenkosten dan veel groter zijn dan de communicatiekosten. Aangezien de rekenkosten niet veranderen, veranderen de totale kosten relatief weinig. Bij grote g, is dit juist andersom. Bij het experimenteren bleek de eerste hypothese juist te zijn. De optimalisatie bij g = 0.5 leverde na 200 periodes van 5000 als kosten 698.5 op, een afnamepercentage van bijna 10 %. Bij g = 1000 kwamen na 100 periode de kosten terecht op 87670, een afname van bijna 59 %. Hierna bleven de kosten hieromheen schommelen. Dit percentage is duidelijk groter, maar het algoritme is ook greedy'er. Wanneer in het begin namelijk nog wel eens verslechteringen optreden zijn die heel groot, omdat g ook zo groot is. De overgangskans, gegeven door p = e(Kvoor-Kna)/T is meteen heel klein door het grote kostenverschil. In het begin is de kostenafname zeer sterk, maar dit zakt al gauw terug naar een niet meer veranderende waarde. De clusters zijn ook een stuk kleiner dan bij de lage g. Wij hebben dan ook met de overige experimenten met een g van 10 gewerkt.
Configuratie met <I>g</I> = 0.5 Configuratie met <I>g</I> = 1000
g = 0.5: Kosten = 698.5 g = 1000: Kosten = 87670