= Computer systemen voor AI =
== week 3, performance lab ==

* Tjerk Kostelijk          0418889 tkosteli@science.uva.nl
* Andreas van Cranenburch  ?? acranenb@science.uva.nl

=== Wed Sep 21 13:52:45 CEST 2005 ===
De allereerste aanpassing die in het oog sprong was het gebruiken van een macro, in plaats van een hele functie.

De tweede was om de aanroep van maximum in de for loop van de line functie te verplaatsen *uit* de for loop. Deze twee optimalisaties bij elkaar gaven een speedup van 1.7.

We hebben de for loop zo veranderd dat er 5 stappen tegelijk worden genomen. We moeten nog zorgen dat bij een grootte die niet een veelvoud van 5 is ook zal werken (padden, if statement en twee for loops, 1 voor het grootste veelvoud van 5, andere voor de rest)

Verder hebben we zo veel mogelijk onnodige (tijdelijke) variabele declaraties weggehaald, met de gedachte dat dan de essentiele variabelen misschien een vaste plek in het register kunnen krijgen. 

=== Fri Sep 23 14:50:23 CEST 2005 ===

In de conditie van de for loop gebruiken we een variabele in plaats van een expressie. Hierdoor hoeft de expressie niet bij elke iteratie gevalueerd te worden.

We hebben bedacht dat we veel beter pointers kunnen gebruiken in plaats van de array-notatie met [] haken. Als we bij iedere iteratie het juist aantal pixels optellen bij de pointer, dan hoeft er a) geen andere teller meer worden bijgehouden in de for loop, en b) het array-element hoeft niet opgezocht te worden, het adres is meteen beschikbaar.

We hebben de for loop herschreven met pointers maar nu worden er fouten gevonden in het resulterende plaatje, we moeten alles dus nog eens zeer zorgvuldig nalezen.

Ook hebben we bedacht dat we de maximum routine nog kunnen optimaliseren, als we de errors hebben opgelost.

Het blijkt dat een aantal variabelen die we van type int hebben gemaakt, in plaats van double, problemen veroorzaken, door afrondingsfouten. 

=== Sat Sep 24 23:25:19 CEST 2005 ===
De maximum functie is nu zeer geoptimaliseerd.

 for(jj = dim-1; jj >= 0; jj--)
         for(ii = 0; ii <= dim-1; ii++)
             if (INTENSITY(src[RIDX(ii, jj, dim)]) > darkness)
             {
                 darkness = INTENSITY(src[RIDX(ii, jj, dim)]);
                 maxi = &(src[RIDX(ii, jj, dim)]);
             }

Hier wordt een if statement met meerdere regels erin gebruikt, maar toch staat er voor het blok van de for loop geen accolades gebruikt. 

De snelheid is nu:
 Line: Version = unst_line: almost optimised implementation:
 Dim             64      128     256     512     1024    Mean
 Your CPEs       16.6    14.9    14.8    15.4    15.1
 Baseline CPEs   72.0    74.0    78.0    190.0   260.0
 Speedup         4.3     5.0     5.3     12.3    17.2    7.5

De manier waarop deze functie geoptimaliseerd is door het gebruik van pointers. In plaats van een bepaald element drie keer op te vragen per iteratie wordt er in de for loop als index een pointer bijgehouden, en wordt door middel van dereferencing en assignment de maximum waarde gevonden. Dit gaf een zeer aanzienlijke versnelling van het programma.
  
Interessant om te vermelden is dat een loop unrolling, b.v. acht stappen tegelijk doen per iteratie van de loop, totaal niets uithaalde. Deze versie was langzamer dan de versie die met pointers 1 stap per iteratie.

We hebben ons flink moeten verdiepen in pointers. Enkele tutorials die we geraadpleegd hebben zijn:
http://pw1.netcom.com/~tjensen/ptr/pointers.htm
http://www.eskimo.com/~scs/cclass/notes/sx10b.html

De macro INTENSITY wordt met een pointer aangeroepen waar twee haakjes om staan. Dit hebben we gedaan omdat het argument van deze macro een struct is. De * operator voor de dereferencing moet aan onze pointer binden, en niet aan de variabelen in de struct. Toelichting:
als src = *pointer : src.green = *pointer.green = *(pointer.green)
als src = (*pointer) : src.green = (*pointer).green

== Tue Sep 27 CEST 2005 ==
We vingen een tip op dat het gebruik van assignments altijd geheugengebruik betekent, en dus traag  is. We bedachten ons dat de uitkomst van een expressie direct in het register kan worden geschreven en dus veel en veel sneller is. Toen we deze optimalisatie doorvoerden bleek dat de loop unrolling plotseling vertragend werkte! Dit kwam ons goed uit want zo'n uitgerolde loop ziet er niet echt netjes uit in de code.

Echter, toen we deze gedachte verder doorvoerde, en ook op maximum toepastte, bleek dat een unrolling juist wel goed was. Experimenterend zijn we er achter gekomen dat 32 een goede mate van unrolling is. Om niet 32 regels code te hoeven tikken, ieder met een andere waarden voor de offset, hebben we een 2-regelig Python script geschreven om de code te genereren:
        
 for a in range(32):
         print "         if (INTENSITY((*(pix_p +",a, "))) > darkness) { darkness = INTENSITY((*(pix_p +", a, "))); maxi = (pix_p +", a, "); } "

Dit stukje code genereert:
if (INTENSITY((*(pix_p + 0 ))) > darkness) { darkness = INTENSITY((*(pix_p + 0 ))); maxi = (pix_p + 0 ); }
if (INTENSITY((*(pix_p + 1 ))) > darkness) { darkness = INTENSITY((*(pix_p + 1 ))); maxi = (pix_p + 1 ); }
if (INTENSITY((*(pix_p + 2 ))) > darkness) { darkness = INTENSITY((*(pix_p + 2 ))); maxi = (pix_p + 2 ); }
if (INTENSITY((*(pix_p + 3 ))) > darkness) { darkness = INTENSITY((*(pix_p + 3 ))); maxi = (pix_p + 3 ); }
enz.

De snelheid is nu:
Line: Version = unst_line: almost optimised implementation:
Dim             64      128     256     512     1024    Mean
Your CPEs       8.9     8.1     8.6     9.9     9.6
Baseline CPEs   72.0    74.0    78.0    190.0   260.0
Speedup         8.1     9.1     9.1     19.3    27.0    12.9

Wat ons betreft een mooi eindresultaat.