En bra bok om Fortran-optimering i allmänhet är den av Metcalf, medan optimering främst på superdatorer behandlas av Levesque och Williamson. En nyare bok på samma tema är den av Goedecker och Hoisie.
I sin enklaste form består optimering av att finna gemensamma deluttryck, beräkna dessa samt undvika att upprepa beräkningen, till exempel genom att ta ut beräkningen ur DO-slingor och spara resultatet för användning inuti.
Ett krav på optimering är att det matematiska resultatet ej ändras, däremot kan det numeriska resultatet komma att ändras på grund av att avrundningsfelet hos flyttalsberäkningen blir något annorlunda. I vissa fall skulle till och med allvarliga konsekvenser kunna uppträda genom att spill ("overflow") eller bottning ("underflow") uppkommer som en följd av ändrad beräkningsordning. Ett teoretiskt exempel är de matematiskt ekvivalenta uttrycken (a*b)/c och a*(b/c), men eftersom parenteser skall respekteras, så är dessa båda uttryck inte ekvivalenta i Fortran-mening. Det är dessutom föreskrivet att all beräkning (av samma prioritet) skall ske från vänster, utom i exponenter (efter **, jämför prioritetsreglerna i sektion 3.15).
En annan teknik för optimering är att, eftersom funktions- och subrutinanrop är ganska kostsamma, flytta in respekive kod direkt i den anropande rutinen, så kallad "inlining". Detta rekommenderas endast om respektive subrutin är "liten" i lämplig mening. Man kan således skriva ett strukturerat program med många små funktioner och subrutiner och överlåta åt kompilatorn att framställa en effektiv version genom "inlining".
Mycket arbete läggs ner på att optimera slingor, speciellt då DO-slingor. Speciella problem (och möjligheter) uppstår vid vektormaskiner och/eller parallella maskiner. Att optimera slingor (även multipel-slingor) för vektormaskiner har nu blivit en etablerad teknik.
Jag har testat ett enkelt exempel slinga3.f90 på DEC Alfa utnyttjande Digitals Fortran med de olika optimeringsgraderna O0 till O5.
Resultat blev följande, efter några enkla redigeringar. Här är metod 1 en explict slinga där sista index varierar snabbast, metod 2 en explict slinga där första index varierar snabbast, samt metod 3 en fält-operation.
Script started on Fri Sep 10 13.14.33 1999 [Setting up eno.mai.liu.se (OSF1-V4.0-alpha) done.] eno[~/tana70]> f90 -O0 slinga3.f90 Tid i metod 1 = 0.0566 sekunder Tid i metod 2 = 0.0400 sekunder Tid i metod 3 = 0.0176 sekunder eno[~/tana70]> f90 -O1 slinga3.f90 Tid i metod 1 = 0.0410 sekunder Tid i metod 2 = 0.0137 sekunder Tid i metod 3 = 0.0107 sekunder eno[~/tana70]> f90 -O2 slinga3.f90 Tid i metod 1 = 0.0380 sekunder Tid i metod 2 = 0.0117 sekunder Tid i metod 3 = 0.0117 sekunder eno[~/tana70]> f90 -O3 slinga3.f90 Tid i metod 1 = 0.0341 sekunder Tid i metod 2 = 0.0078 sekunder Tid i metod 3 = 0.0088 sekunder eno[~/tana70]> f90 -O4 slinga3.f90 (default) Tid i metod 1 = 0.0341 sekunder Tid i metod 2 = 0.0078 sekunder Tid i metod 3 = 0.0088 sekunder eno[~/tana70]> f90 -O5 slinga3.f90 Tid i metod 1 = 0.0078 sekunder Tid i metod 2 = 0.0078 sekunder Tid i metod 3 = 0.0079 sekunderVi ser således att i detta fall förefaller det ha stor betydelse om första (metod 2, bäst) eller sista (metod 1, sämst) index varierar snabbast, medan man vid en fältoperation får en betydande ytterligare uppsnabbning vid låg optimering. Utmatningen av summan av alla elementen sker i syfte att lura optimeringen, i annat fall kan en kraftfull optimering undvika att räkna ut något överhuvudtaget.
Utnyttjande NAG:s nya Fortran 95 kompilator på en Sun SPARC station 10 erhölls motsvarande resultat.
Jag har upprepat körningen på en Cray C90 och då använt DIM = 100 i stället för DIM = 50.
Script started on Fri Sep 10 13:33:47 1999 sn4004 1 % f90 -V Cray CF90 Version 2.0.1.0 07/19/99 15:29:15 sn4004 3 % f90 -O0 slinga3.f90 sn4004 4 % a.out Tid i metod 1 = 1.240 sekunder Tid i metod 2 = 1.293 sekunder Tid i metod 3 = 0.019 sekunder sn4004 6 % f90 -O1 slinga3.f90 sn4004 7 % a.out Tid i metod 1 = 0.016 sekunder Tid i metod 2 = 0.004 sekunder Tid i metod 3 = 0.004 sekunder sn4004 8 % f90 -O2 slinga3.f90 (default) sn4004 9 % a.out Tid i metod 1 = 0.002 sekunder Tid i metod 2 = 0.002 sekunder Tid i metod 3 = 0.002 sekunder sn4004 10 % f90 -O3 slinga3.f90 (inkl. autotasking) sn4004 11 % a.out Tid i metod 1 = 0.050 sekunder Tid i metod 2 = 0.002 sekunder Tid i metod 3 = 0.002 sekunder
Vid låg optimering är metod 3 den klart bästa, vid måttlig optimering blir även metod 2 bra. Vid autotasking blir metod 1 extra ineffektiv jämfört med de andra metoderna.
Jag har nu valt ett annat exempel på Cray C90, nämligen där kompilatorn har problem med att vektorisera den slinga som ligger innerst. I exemplet chanel1.f90 sker i den första trippelslingan en initiering och i den andra en beräkning, vilken även tidmätes med Crays funktion SECOND(). I den innersta beräkningsslingan finns ett beroende (elementet i position k beror av det i position k-1), vilket medför att denna ej kan vektoriseras utan vidare.
Jag har valt att göra körningen med optimeringsgrad 1. När jag i stället kör chanel2.f90 med samma optimeringsgrad sker exekveringen mycket snabbare. Detta beror på att den innersta slingan nu är över index j och det finns inte längre något beroende som förhindrar vektorisering. Med högre optimeringsgrad klarar kompilatorn av problemet på egen hand.
Script started on Tue Jul 20 08:44:52 1999 sn4004 3 % f90 -V -O1 chanel1.f90 Cray CF90 Version 2.0.1.0 07/20/99 08:46:02 cf90: COMPILE TIME 1.588000 SECONDS cf90: MAXIMUM FIELD LENGTH 238659 DECIMAL WORDS cf90: 26 SOURCE LINES cf90: 0 ERRORS, 0 WARNINGS, 0 OTHER MESSAGES, 0 ANSI cf90: CODE: 97 WORDS, DATA: 180 WORDS sn4004 4 % a.out Normal beraekningsordning tar 0.147152 sekunder. -2.320756189087945E+323 sn4004 5 % f90 -V -O1 chanel2.f90 Cray CF90 Version 2.0.1.0 07/20/99 08:46:38 sn4004 6 % a.out Optimerad beraekningsordning tar 0.008127 sekunder. -2.320756189087945E+323 sn4004 7 %
Exekveringen av en DO-slinga kan ibland snabbas upp genom att dela upp den ("unrolling") så att systemets parallellism kan utnyttjas maximalt. Detta gäller framför allt på superdatorer. På T3E finns de speciella optimeringsalternativen unroll0, unroll1 och unroll2, samt direktiven !DIR$ UNROLL och !DIR$ NOUNROLL.
Anm. Cray kallar operativsystemet på C90 för UNICOS och det på T3E för unicos/mk.
En utmärkt genomgång av "unrolling" ges på sid 138-142 i boken av Levesque och Williamson.
REAL, DIMENSION (1:10000) :: A
! Metod 1, explicit DO-slinga
DO I = 1, 10000
WRITE(1) A(I)
END DO
! Metod 2, implicit DO-slinga
WRITE(1) (A(I), I = 1, 10000)
! Metod 3, implicit
WRITE(1) A
Det visar sig här att metod 3 är mycket snabbare, även i
ren CPU-tid. Jag har här ett fullständigt körbart exempel
slinga1.f90 på detta.
Här följer utmatningen från programmet samt storleken
på de erhållna resultatfilerna.
Script started on Fri Jul 9 11:25:57 1999 On a Sun SPARCstation 10 with the NAGWare f90 compiler Version 2.2 (261) %./a.out Tid i metod 1 = 0.240 sekunder Tid i metod 2 = 0.040 sekunder Tid i metod 3 = 0.020 sekunder %/bin/ls -slFag 128 -rw-r--r-- 1 boein nsc 120000 Jul 9 11:26 slask1 40 -rw-r--r-- 1 boein nsc 40008 Jul 9 11:26 slask2 40 -rw-r--r-- 1 boein nsc 40008 Jul 9 11:26 slask3Vi ser här att metod 1 (explicit DO-slinga) både är långsammare och genererar en större fil.
Nu följer resultatet från DEC Alpha där jag dock ökat antalet element DIM från 10 000 till 100 000. På Sun blev det problem med en buffer vid för många element.
Script started on fre jul 9 12.24.50 1999 [Setting up eno.mai.liu.se (OSF1-V4.0-alpha) done.] On a DEC Alpha station with the DIGITAL Fortran 90 compiler Version 5.0-492 eno[~/tana70]> a.out Tid i metod 1 = 3.125 sekunder Tid i metod 2 = 0.694 sekunder Tid i metod 3 = 0.695 sekunder eno[~/tana70]> /bin/ls -slFag 1264 -rw-r--r-- 1 boein num 1200000 Jul 9 12:26 slask1 448 -rw-r--r-- 1 boein num 400008 Jul 9 12:26 slask2 448 -rw-r--r-- 1 boein num 400008 Jul 9 12:26 slask3
Nu följer resultatet från CRAY C90 där jag även där har ökat antalet element DIM från 10 000 till 100 000. Filerna blir dessutom större eftersom precisionen på den maskinen är högre.
Script started on Fri Jul 9 12:59:06 1999 On a Cray C90 with Cray CF90 Version 2.0.1.0 sn4004 1 % a.out Tid i metod 1 = 2.457419 sekunder Tid i metod 2 = 0.002330 sekunder Tid i metod 3 = 0.002134 sekunder sn4004 2 % ls -slFag 3136 -rw------- 1 g97900 1605632 Jul 9 12:59 slask1 1568 -rw------- 1 g97900 802816 Jul 9 12:59 slask2 1568 -rw------- 1 g97900 802816 Jul 9 12:59 slask3
Jag har här ett fullständigt körbart exempel slinga2.f90 på detta. Här följer utmatningen från programmet samt storleken på de erhållna resultatfilerna.
Script started on Fri Jul 9 14:40:24 1999 On a Sun SPARCstation 10 with the NAGWare f90 compiler Version 2.2 (261) hugo 3 % a.out Tid i metod 1 = 2.240 sekunder (ett tal per rad) Tid i metod 2 = 1.980 sekunder (tio tal per rad) Tid i metod 3 = 0.020 sekunder (oformatterat) hugo 4 % /bin/ls -slFag 152 -rw-r--r-- 1 boein nsc 140000 Jul 9 14:40 slask1 136 -rw-r--r-- 1 boein nsc 131000 Jul 9 14:40 slask2 40 -rw-r--r-- 1 boein nsc 40008 Jul 9 14:40 slask3