C-2 OPTIMALIZACE PROGRAMU VE FORTRANU Obsah Predmluva ..................................................... 2 1. Uvod .......................................................... 2 2. Optimalizace monitorovanim casoveho prubehu programu .......... 3 2.1 Utilita prof .................................................. 4 2.2 Podprogramy pro sledovani casu ............................... 4 2.3 Utilita flowtrace ............................................. 5 2.4 Utilita jumptrace ............................................. 5 2.5 Utilita procstat .............................................. 6 2.6 Utilita ja .................................................... 6 3. Fortransky prekladac .......................................... 7 3.1 Volby pro prekladac cf77 ...................................... 7 3.2 Pouziti preprocesoru fpp ...................................... 8 3.3 Direktivy ..................................................... 8 4. Vektorizace ................................................... 8 4.1 Vlastnosti vektoroveho hardware ............................... 9 4.2 Zretezene zpracovani ve funkcni jednotce ...................... 9 4.3 Paralelismus a retezeni funkcnich jednotek ................... 10 4.4 Pozadavky pro vektorizaci .................................... 10 4.5 Fortranske prikazy vhodne pro vektorizaci .................... 10 5. Pouziti preprocesoru fpp pro zlepseni optimalizace ........... 11 5.1 Analyza datovych zavislosti .................................. 12 5.2 Smycka bez datove zavislosti ................................. 13 5.3 Smycka s podminenou datovou zavislosti ....................... 13 5.4 Smycka s datovou zavislosti .................................. 13 5.5 Direktivy pro datovou zavislost .............................. 14 5.6 Rozvoj vnorenych smycek ...................................... 14 5.7 Zmena struktury vnorenych smycek ............................. 15 5.8 Maticove nasobeni ............................................ 15 5.9 Linearni rekurze ............................................. 16 5.10 Odkazy na funkce a volani subrutin ........................... 16 5.11 Rozvoj pro podprogramu ....................................... 16 5.12 Omezeni pro rozvoj podprogramu ............................... 17 5.13 Nevyhody rozvoje podprogramu ................................. 17 5.14 Rozstepeni smycek ............................................ 17 6. Nepouziti dvojnasobne presnosti .............................. 18 7. Optimalizace pouziti pameti .................................. 18 7.1 Pametove odkazy a delka kroku ................................ 18 7.2 Jak se vyhnout pametovym konfliktum .......................... 19 7.3 Zmena poradi smycek .......................................... 20 7.4 Zamena rozmeru poli .......................................... 21 7.5 Rozsireni rozmeru poli ....................................... 21 8. Optimalizovane matematicke knihovny .......................... 21 9. Literatura ................................................... 22 Predmluva Tato prirucka je dalsi z prirucek rady C urcene pro uzivatele po- citace Cray Y-MP EL, vydanych Strediskem automatizace a vypocetni techniky (SAVT) Fyzikalniho ustavu AV CR. Tato rada informuje na uvod- ni urovni o problematice prekladu, vektorizace a optimalizace fortran- skych programu a jejich ladeni. Predkladana prirucka popisuje metody optimalizace fortranskych programu a podrobneji seznamuje s pojmem vektorizace. Navazuje na prirucku C-1: Zpracovani programu ve fortranu [1] a jejim autorem je I. Veltrusky. Prirucky jsou k dispozici u operatorek postupne tak, jak budou vydavany. Obsah techto prirucek je dostupny i v "on-line" tvaru na obrazovce, zatim na pracovnich stanicich Sun jako soucast informacniho systemu info, ktery umoznuje pohodlne listovani pomoci menu a volby kapitol. System se spousti povelem ginfo a jeho soucasti je rovnez na- vod k pouzivani. Prirucky SAVT se volaji volbou fzinfo z hlavniho menu a volbou jmena prirucky z nasledujiciho menu. Aktualni verze prirucky ve forme vystupniho souboru z Chi-Writeru 3 je pristupna vsem uzivatelum site prostrednictvim ftp na pocitaci ftp.fzu.cz po zalogovani jako anonymous (jako heslo napisete vase uzivatelske-oznaceni). Doporucene parametry pro tisk na laserovou tis- karnu z Chi-Writeru 3 jsou Margin Offset: 13, Pitch: Elite, Quality: Firmware. V tistenem textu pouzivame az na drobne vyjimky nasledujici kon- venci pro pro typ pisma: to, co pise uzivatel na klavesnici, je zna- zorneno tucnym pismem (bold), s vyjimkou nazvu formalnich promennych, ktere jsou ve scriptu, odezva pocitace je napsana kurzivou (italics). Nove zavadene pojmy a casto i nazvy jednotlivych souboru v textu jsou psany rovnez kurzivou. Chceme tyto prirucky poskytnout uzivatelum v co nejkratsim case, a tak predpokladame, ze jejich obsah dozna zmen v jejich dalsich vyda- nich na zaklade zkusenosti, ktere se teprve rodi. Uvitame proto vsech- ny vase pripominky jak k obsahu, tak k forme techto informaci. Muzete pouzit e-mail na adresu office@fzu.cz nebo primo na adresu autora pri- slusne prirucky. 1. Uvod Optimalizace je proces usporadani dat a instrukci v programu tak, aby jeho provedeni vyzadovalo minimum naroku na pocitac. Konvertuje- te-li program z jednoho pocitacoveho prostredi do druheho, je vasim cilem ho prelozit, sestavit a uspesne provest. Zridkakdy uvazujete o tom, jak usit program na miru nejakemu konkretnimu pocitaci, protoze rozdily v hardware mezi konvencnimi pocitaci stejneho vykonu obycejne nemaji zadny podstatny vliv na prubeh vypoctu, zvlaste je-li program napsan dobre. Jestlize vsak konvertujete svuj program na pocitac Cray, meli byste si udelat cas a vychozi program optimalizovat, abyste vyuzili vyhod vektoroveho hardware tohoto pocitace. Kratka doba, venovana op- timalizaci, muze vest k vyznamnemu urychleni behu vaseho programu. Tato prirucka se zabyva technikami optimalizace programu pro po- citac Cray Y-MP EL. Tyto techniky jsou uzitecne nejen konvertujete-li program z jineho prostredi, ale i pisete-li novy. Dozvite se z ni, jak . ziskat informaci o pozadavku vaseho programu na cas pocitace . vyuzivat fortranskeho prekladace ke zlepseni optimalizace . implementovat vektorizacni techniky a prekonat pripadne prob- lemy . optimalizovat vyuziti pameti . pouzivat optimalizovanych matematickych knihoven 2. Optimalizace monitorovanim casoveho prubehu programu Vetsina vypocetniho casu se obvykle spotrebuje v urcitych malych castech programu. Nemusite tedy nutne optimalizovat vsechny casti pro- gramu, staci se soustredit pouze prave na tyto casti, ktere vycerpava- ji znacne procento vypocetniho casu. Nasledujici podpurne programy (utilities) vam mohou pomoci iden- tifikovat ty casti programu, ktere jsou narocne na cas CPU (viz tez [2]): . prof . subrutina SECOND . flowtrace . jumptrace . procstat Informace, ktere vam poskytnou, se nekdy castecne prekryvaji. Celkovou informaci o behu programu vcetne udaju o pouzite pameti a o pouzitych vstupnich/vystupnich operacich vam poskytnou prostredky . ja . procstat K identifikaci podprogramu (subrutin a funkci), narocnych na cas CPU, pouzijete utilitu prof nebo flowtrace. Pote muzete soustredit sve optimalizacni usili na smycky, v techto podprogramech se vyskytujici. Abyste urcili prubeh v jednotlivych blocich ci smyckach, muzete pouzit utilit prof, jumptrace nebo subrutiny SECOND. K urceni celkoveho casu spotrebovaneho programem pouzijte for- transkou subrutinu SECOND nebo jeste lepe obecnejsi utilitu ja. Tuto utilitu doporucujeme ke standardnimu pouzivani i pro odladene progra- my, nebot poskytuje souhrnne udaje i o pouziti pameti. Udaje o pouzite pameti a vstupnich/vystupnich operacich, vztazene tez i na jednotlive soubory, se kterymi vas program pracuje, poskytuje utilita procstat. Pote, co jste identifikovali casti programu, narocne na strojovy cas, muzete je vyhodnotit jednu po druhe a zamenit nebo modifikovat algoritmus podle navodu v teto prirucce. K urceni toho, jak nejlepe vektorizovat cast vlastniho programu, je casto uzitecne si vytvorit zvlastni testovaci program. Takovy test by mel odrazet strukturu vlastniho problemu, ale nemel by byt casove prilis narocny. 2.1 Utilita prof Utilitu prof (odvozeno od slova profile) muzete pouzit k casovemu monitorovani (timing) jednotlivych casti programu napsaneho v kterem- koliv jazyce pod UNICOSem. Poskytne vam udaje o relativnim casu spo- trebovanem v subrutinach a smyckach (ve skutecnosti provadi v urcitych casovych intervalech dotazy, ktere casti programu se prave vykonava- ji). Neni tak presna, jako jine casovaci utility, avsak podstatnou ca- sovou informaci poskytuje za cenu pomerne male rezie casu CPU. Jestlize ma vas zdrojovy program jmeno napr. zdroj.f, muzete ho prelozit, sestavit a provest s pouzitim utility prof nasledovne: cf77 -Zv -Wf"-ez" -l prof -o zdroj.x zdroj.f zdroj.x prof -x zdroj.x > zdroj.prof Prvni povel prelozi a sestavi program s tim, ze zachova informaci o symbolicke tabulce (-Wf"-ez"), vyvola volbu pro zesilenou vektoriza- ci preprocesorem fpp (-Zv) a prisestavi knihovnu prof (-l prof). Druhy povel program rozbehne, pricemz je vytvoren pomocny soubor se statis- tickymi daty prof.data. Treti povel rozbehne utilitu prof a specifiku- je volbu -x pro nasledne zpracovani pomoci prohlizeci utility profview. Vystupni soubor se statistickymi daty je pojmenovan zdroj.prof. Povel profview zdroj.prof pak rozbehne interaktivni utilitu profview, ktera vas vyzve k napsani pozadovaneho typu vystupu. Pracujete-li pod grafickym systemem X (X Window System), je radkovy vystup automaticky nahrazen vystupem gra- fickym. 2.2 Podprogramy pro sledovani casu Fortranska knihovna nabizi nekolik casovacich podprogramu (timing routines). Nejcasteji pouzivany podprogram je SECOND, ktery vraci spo- trebovany cas CPU v sekundach v pohyblive carce. Podprogram SECOND muze byt pouzit bud jako funkce nebo subrutina, obe pouziti se vsak v ramci jedne programove jednotky nemohou stridat. Chcete-li ho pouzit jako subrutinu, vlozte do vaseho programu nasledu- jici radku: CALL SECOND (time) Chcete-li ho pouzit jako funkci, vyvolejte ho bez argumentu tak- to: time = SECOND( ) V kazdem pripade promenna time vraci v sekundach souhrnny cas CPU spo- trebovany od zacatku behu vaseho programu do okamziku volani podpro- gramu SECOND. Pro monitorovani casu pro urcitou cast programu muzete umistit podprogram SECOND pred tuto cast a znovu za ni. Rezijni cas pro dve volani podprogramu SECOND je minimalni a vy- znamne neovlivni casovou analyzu, pokud se sledovana cast programu ne- provadi prilis casto. Vice informaci o casovacich podprogramech se do- zvite v manualu UNICOS Fortran Library Reference Manual (SR-2079) [3]. 2.3 Utilita flowtrace Utilita flowtrace shromazduje informace o sledovanych volanich podprogramu behem provadeni programu; dozvime se tak, ktery podprogram je nejcasteji behem vypoctu volan. Sleduje se jak pocet volani, tak celkovy cas CPU, spotrebovany v jednotlivych podprogramech. Skonci-li program normalne, jsou tyto statisticke udaje zapsany do pracovniho souboru flow.data. Zprava (report) muze byt z techto udaju vygenerova- na pouzitim nasledne prohlizeci utility flowview. Abyste mohli pouzit utilitu flowtrace, musite prekladat s volbou -F, tedy preklad a spusteni programu bude vypadat napr. takto: cf77 -F -ZV -o zdroj.x zdroj.f zdroj.x Po prekladu a behu programu si muzete vysledky budto prohlizet interaktivne, nebo je zapsat do souboru. V prvnim pripade vyvolate utilitu flowview bez voleb (muzete pracovat v radkovem modu nebo po- uzivat graficke rozhrani systemu X), v druhem pripade zadate volby pro specificke typy reportu, ktere se ulozi do vami zadaneho souboru; nej- casteji pouzivana je tato kombinace: flowview -Luch > flow.report Dalsi detaily se dozvite pomoci povelu man flowtrace a man flowview. 2.4 Utilita jumptrace Utilita jumptrace umoznuje velmi presne casove monitorovani kaz- deho bloku ve vasem programu (s presnosti jednoho taktu). Je tedy mno- hem detailnejsi a presnejsi nez dosud zminene utility flowtrace (moni- toruje pouze cele podprogramy, a to na zaklade mene presnejsiho mereni casu) nebo prof (monitoruje v jistych casovych intervalech prave vyko- navane adresy). Na rozdil od flowtrace monitoruje tez knihovni podpro- gramy. Je vsak zrejme, ze celkovy cas CPU se znatelne prodlouzi. Pro- behne-li program normalne, jsou vsechna statisticka data zapsana do pracovniho souboru jump.data. Zprava muze byt z techto udaju zpracova- na pouzitim nasledne utility jumpview. Abyste mohli pouzit utilitu jumptrace, volanou povelem jt, musite prekladat s volbou, umoznujici vytvoreni symbolicke tabulky, a prise- stavit knihovnu libtrace.a. Tedy preklad a spusteni programu bude vy- padat napr. takto: cf77 -Wf"-ez" -l trace -o zdroj.x zdroj.f jt zdroj.x Po prekladu a behu programu si muzete vysledky budto prohlizet interaktivne, nebo je zapsat do souboru. V prvnim pripade vyvolate prostredek jumpview bez voleb (muzete pracovat v radkovem modu nebo pouzivat rozhrani grafickeho systemu X), v druhem pripade zadate volby pro specificke typy reportu, ktere se ulozi do vami zadaneho souboru; nejcasteji pouzivana je tato kombinace: jumpview -LuchM > jump.report Dalsi detaily se dozvite pomoci povelu man jt a man jumpview. 2.5 Utilita procstat Utilita procstat monitoruje provadeni kazdeho povelu, tj. shro- mazduje informace o case, o pouziti vstupnich/vystupnich operaci a o pouziti pameti behem procesu, ktery byl danym povelem spusten. Infor- mace se tez tykaji souboru, se kterymi se behem procesu pracuje, tj. napr. fortranskych vstupnich/vystupnich jednotek. Skonci-li beh nor- malne, jsou tyto statistiky zapsany do pracovniho souboru proc.data. Zprava muze byt z techto udaju vygenerovana pouzitim nasledneho pro- stredku procview. Abyste mohli pouzit utilitu procstat, musite krome povelu, ktery ma byt monitorovan, explicitne zadat i jmeno pracovniho souboru, kam se statisticke udaje ukladaji: procstat -R proc.data zdroj.x kde zdroj.x je v tomto pripade povel pro spusteni vykonatelneho soubo- ru tehoz jmena a pracovni soubor je pojmenovan proc.data. Vysledky si muzete budto prohlizet interaktivne, nebo je zapsat do souboru. V prvnim pripade vyvolate prostredek procview bez voleb, avsak s udanim pracovniho souboru se statistickymi udaji (muzete pra- covat v radkovem modu nebo pouzivat rozhrani grafickeho systemu X), v druhem pripade zadate volby pro specificke typy reportu, ktere se ulo- zi do vami zadaneho souboru; nejcasteji pouzivana je tato kombinace: procview -L -Fu -Sn proc.data > proc.report Dalsi detaily se dozvite pomoci povelu man procstat a man procview. 2.6 Utilita ja Utilita ja (job accounting) poskytuje souhrnnou informaci nejen o spotrebovanem case vasi ulohy, ale i o velikosti pouzite pameti, casu spotrebovanem na vstupni/vystupni operace a pouziti jednotlivych pove- lu. Nejprve pouzijete povel ja bez voleb a parametru, a jako posledni povel pouzijete povel ja s volbami pro ruzne typy zprav, jehoz vystup nasmerujete do souboru, tedy napr. ja cf77 -o zdroj.x zdroj.f zdroj.x ja -csft > ja.report V dusledku volby -c se vytvori zprava o pouzitych povelech (command report), volba -f generuje prehled o vzajemnych volanich jednotlivych povelu (command flow report) a volba -s poda celkovou zpravu (summary report) o uloze. Volba -t ukoncuje proces monitorovani. Utilitu ja do- porucujeme pouzivat jako standardni informacni prostredek pro vsechny vase ulohy, zadavane do front NQS, tedy nejen pri optimalizaci a lade- ni. 3. Fortransky prekladac Povelem cf77 vyvolate fortransky prekladacovy system pracujici pod UNICOSem [4]. Timto jednim prikazem lze vhodnymi volbami: . Provest analyzu datove zavislosti (data dependency analysis). Fortransky preprocessor fpp provadi vektorizacni analyzu dato- ve zavislosti, dosadi do programu direktivy pro prekladac, aby se tak prekladaci tyto informace predaly, a zmeni zdrojovy program tak, aby se podporilo a zesililo vektorizacni usili vlastniho prekladace cft77. . Vytvorit cilovy soubor. Vlastni fortransky prekladac cft77 provadi skalarni a vektorovou optimalizaci a vytvori premisti- telny cilovy soubor. . Spustit sestavovaci program segldr. Kazdou vyse uvedenou slozku muzete vyvolat oddelene, doporucujeme vsak pomoci cf77 provest vsechny slozky najednou. Povelova radka pro cf77 je cf77 [volby] soubory kde volby jsou volby pro prekladac cf77 a soubory mohou byt obecne fortranske zdrojove soubory (zdroj.f), vystupni soubory z fpp (zdroj.m) nebo premistitelne binarni soubory (zdroj.o). 3.1 Volby pro prekladac cf77 Problematice prekladu fortranskych programu je venovana samostat- na prirucka C-1: Zpracovani programu ve fortranu [1]. Zde jen konsta- tujme, ze ve vasi povelove radce pro cf77 muzete pouzit nasledujicich voleb, abyste tak vyvolali beh jednotlivych prostredku, spoustenych povelem cf77 (napr. cft77 a fpp): -Wd"fpp-retezec" umoznuje specifikovat volby pro fpp, pricemz fpp-retezec je soubor techto vo- leb (vice informaci se dozvite pouzitim povelu man fpp) -Wf"cft77-retezec" umoznuje specifikovat volby pro cft77, pricemz cft77-retezec je soubor voleb pro cft77 (podrobnejsi informace ziskate povelem man cft77) -Wl"segldr-retezec" umoznuje specifikovat volby pro segldr, pricemz segldr-retezec je soubor voleb pro segldr (podrobnejsi informace ziska- te povelem man segldr). 3.2 Pouziti preprocesoru fpp Preprocesor fpp provadi predbeznou analyzu datovych zavislosti ve vasem programu. Dosazuje do nej prekladacove direktivy a v pripade, je-li to mozne, reorganizuje ho tak, aby pomahal prekladaci cft77 pri optimalizaci. Muze dokonce desifrovat nektere standardni vektorove ci maticove operace a nahradit tyto casti vaseho programu vysoce optima- lizovanymi knihovnimi podprogramy. K vyvolani preprocesoru fpp pouzijte volby -ZV pro cf77 takto: % cf77 -ZV -c zdroj.f kde -ZV indikuje, ze ma byt spusten preprocesor fpp a -c indikuje, ze maji byt produkovany cilove soubory, avsak sestavovaci program segldr nema byt vyvolan. Je vytvoren novy soubor zdroj.m, ktery je vysledkem modifikace vaseho puvodniho zdrojoveho kodu preprocesorem fpp. (Je-li uzita volba -Zv, neni tento soubor zachovan.) Prohlednete-li si tento soubor, zjistite, ze byly dosazeny prekladacove direktivy a ze byly ve vasem puvodnim programu provedeny urcite zmeny (byl-li ovsem vektori- zovatelny). 3.3 Direktivy Direktivy (directives) jsou povely dosazene do vaseho fortranske- ho zdrojoveho programu bud vami nebo preprocesorem fpp. Zacinaji v prvnim sloupci pismenem C. Direktivy jsou ruzneho druhu pro ruzne kom- ponenty fortranskeho prekladacoveho systemu (fpp a cft77) a poskytuji pro tyto komponenty dodatecne instrukce. Formaty pro direktivy jsou: CFPP$ direktiva pro direktivy pro fpp vlozene vami CDIR$ direktiva pro direktivy pro cft77 vlozene vami CDIR@ direktiva pro direktivy pro cft77 vlozene fpp kde direktiva je pripustna volba pro dany typ direktiv CFPP$, CDIR$ nebo CDIR@. Protoze fortranske prekladace obecne definuji prikazy pro poznamky jako prikazy zacinajici pismenem C v 1. sloupci, budou tyto prekladacove direktivy pripadnymi jinymi fortranskymi prekladaci igno- rovany. 4. Vektorizace Architektura pocitace Cray umoznuje, aby nekolik operaci na prv- cich vektoru v ramci jedne smycky bylo provedeno jedinou instrukci, zjednodusene receno, takrka najednou. Tato okolnost muze byt zdrojem vyznamneho urychleni vypoctu v porovnani s klasickou tzv. skalarni ar- chitekturou. Ve skalarnich pocitacich jsou operandy dodavany do funkcni jed- notky vzdy po jednom, a po urcitem poctu period je produkovan vysle- dek. V danem okamziku je zpracovavan pouze jeden soubor operandu, pri- cemz operandem je cislo nebo znakovy retezec urcite maximalni delky. Uvazujme napr. tuto smycku: DO 2 J = 1,N C(J) = S(J) + T(J) 2 CONTINUE V pocitaci se skalarnim procesorem je tato smycka provedena zavedenim operandu S(1), pak T(1), sectenim S(1) a T(1) a ulozenim vysledku do C(1). Tento sled operaci se opakuje pro J = 2,3,...,N. Cas spotrebova- ny ve smycce je tedy N krat suma casu potrebnych pro dve zavedeni ope- randu, jedno scitani, jedno ulozeni, plus jisty rezijni cas pro zvyse- ni indexu smycky a test na ukonceni smycky. 4.1 Vlastnosti vektoroveho hardware Vektorove pocitace (jako je Cray) se od beznejsich skalarnich po- citacu lisi tim, ze v repertoaru instrukci maji navic instrukce vekto- rove, jejichz operandy nejsou jednotliva cisla, ale vektory z nich vy- tvorene. Tyto instrukce se provadeji ve specifickych hardwarovych jed- notkach, a vypocet je tedy podstatne efektivnejsi, nez podle analogic- keho programu slozeneho pouze ze skalarnich instrukci. Mezi specialni hardwarove komponenty patri vektorove registry (vector registers) a segmentovane funkcni jednotky (segmented functional units). Zakladni jednotka (Central Processing Unit, CPU) pocitace Cray ma pritom osm vektorovych registru. Kazdy z nich muze uchovat az 64 ruznych prvku. Jedina vektorova instrukce muze provest aritmetickou nebo logickou operaci mezi dvema vektorovymi registry a vysledek ulozit do tretiho vektoroveho registru. Jina vektorova instrukce zas muze provadet pre- nosy mezi hlavni pameti a vektorovymi registry. Segmentovane funkcni jednotky jsou v procesoru pocitace Cray Y-MP EL ctyri. 4.2 Zretezene zpracovani ve funkcni jednotce V segmentovanych funkcnich jednotkach se aritmeticke operace rozdeluji na oddelene podoperace, z nichz kazda potrebuje na dokonceni jeden takt (clock period) (v pripade pocitace Cray Y-MP EL je to 30 ns). Tyto podoperace jsou provadeny postupne az ke konecnemu vysledku. Tento proces se nazyva zretezene zpracovani (pipelining). Funkcni jednotky pocitace Cray jsou segmentovany do podjednotek (subunits), ktere provadeji vyse zminene podoperace, a nakonec tak vy- tvareji komplexni operaci. Tyto segmenty jsou zretezeny tak, ze si predavaji mezivysledky. Do prvniho segmentu vstupuji v kazdem taktu operandy aritmeticke operace. Na konci kazdeho taktu se vysledek z jednoho segmentu stava vstupem do nasledujiciho segmentu. Operandy tedy prochazeji segmenty jako na montazni lince a po urcite pocatecni startovaci dobe vystupuje pri kazdem taktu na konci segmentovane jed- notky novy vysledek, tj. jeden prvek vysledneho vektoru. Uvazujme napr. opet posledne zminenou smycku. Kdyz pocitac Cray ve vektorovem modu zpracovava smycku, pracuje v blocich se 64 prvky najednou. Jedinou vektorovou instrukci se zavede 64 prvku pole S do vektoroveho registru. Druha vektorova instrukce provede totez s polem T. Treti vektorova instrukce secte 64 prvku z S a T, ktere pritom pro- chazeji funkcni jednotkou. Ctvrta vektorova instrukce ulozi 64 vysled- ku do pole C v pameti. Vektorove zpracovani teto smycky ji tak muze zrychlit i vice nez desetkrat! 4.3 Paralelismus a retezeni funkcnich jednotek Pocitac Cray muze v ramci jednoho procesoru paralelne provadet nekolik po sobe jdoucich instrukci. Napr. vzhledem k tomu, ze jsou tri cesty mezi pameti a procesorem, mohou byt soucasne provadena dve cteni z pameti a jeden zapis do pameti. Protoze procesor naseho pocitace obsahuje 4 oddelene vektorove funkcni jednotky k provadeni ruznych lo- gickych a aritmetickych operaci, mohou byt teoreticky provedeny az 4 instrukce soucasne. Poznamenejme, ze tento paralelismus v ramci jedno- ho procesoru nezustal vysadou vektorovych pocitacu, a podobna metoda je vyuzivana take v tzv. superskalarnich procesorech tridy RISC. Vektorove funkcni jednotky mohou byt tez navzajem zretezeny (tzv. chaining), takze vysledky z jedne jednotky mohou byt nasmerovany jako vstup do jednotky jine pro dalsi vektorove zpracovani, coz tedy umoz- nuje vyhodne prekryvani datove zavislych instrukci. I tuto praci dela za uzivatele prekladac. 4.4 Pozadavky na vektorizaci Fortransky prekladac cft77 analyzuje nejvnitrnejsi smycky for- transkeho programu, aby tak zjistil, zda muze pri prekladu pouzit me- tod vektoroveho zpracovani. Jestlize prekladac zjisti, ze cast progra- mu ve smycce je vhodna pro vektorovy hardware, vygeneruje vektorizova- ny zdrojovy program (vektorovy kod). Prekladac cft77 vektorizuje program pouze uvnitr nejvnitrnejsich smycek. Avsak ne vsechny vnitrni smycky mohou byt vektorizovany. Vek- torovy kod je vytvoren pouze tehdy, jsou-li splneny jiste podminky. Abyste vyuzili vsech vyhod vektorizace, musite vyvolat preproce- sor fpp a uzit direktiv a voleb k vektorizaci smycek. Navic budete pripadne muset zmenit strukturu nekterych smycek nebo napsat zcela no- vy algoritmus, ktery jiz bude vektorizovatelny. Vektorizace muze byt obecne vyuzita pouze tehdy, provadi-li smycka vypocty na jednom nebo vice polich nebo regularnich podmnozinach poli (tj. vyuziva napr. jed- norozmerne pole, radku nebo sloupec vicerozmerneho pole, nebo kazdy n-ty prvek pole). 4.5 Fortranske prikazy vhodne k vektorizaci Ve smycce, ktera bude vektorizovana, se smi objevit pouze typy fortranskych prikazu, popsane nize. Jestlize smycky obsahuji jakekoliv jine prikazy nez tyto nize uvedene, je vhodne je prepsat. . Prirazovaci prikazy, napr. Z(I) = X(I) + Y(I) . Podminene prirazovaci prikazy, napr. IF(Z(I) .LT. 0.0) Z(I) = 0.0 . Prikazy GOTO pro skok dopredu. . Prikazy IF(...) GOTO pro skok dopredu. . Prikazy IF(...) THEN . Prikazy ELSE . Prikazy ENDIF . Prikazy aritmetickeho IF pro skok dopredu, napr. IF(I) 11,22,33 11 ... 22 ... 33 ... . Prikazy CALL pro uzivatelske subrutiny a volani uzivatelskych funkci, avsak pouze se zvlastnimi instrukcemi uzivatele (viz odst.5.10). . Komentare (comment statements) . Prikazy CONTINUE . Prikazy FORMAT . Prikazy DATA Jestlize se ve smycce DO objevi jakykoliv jiny fortransky prikaz, smycka nebude vektorizovana. Jmenovite, nasledujici prikazy a operace ve smycce DO znemoznuji provedeni vektorizace: . Vstupni/vystupni operace . Odkazy na promenne nebo pole typu CHARACTER. 5. Pouziti preprocesoru fpp ke zlepseni optimalizace Jak jsme se jiz zminili, nadavkem k implicitni optimalizaci a vektorizaci provadene samotnym prekladacem cft77 muzete svuj program dale optimalizovat tim, ze v nem nechate preprocesor fpp (nebo ekviva- lentne prekladac cf77 s volbou -ZV) provest analyzu datovych zavislos- ti (viz odst.5.1). Pri teto analyze se preprocesor fpp pokousi vas program modifikovat tak, ze ho prepise do tvaru, ktery prekladac cft77 jiz muze snadno vektorizovat, nebo nahradi jeho casti optimalizovanymi knihovnimi podprogramy. Ke zlepseni analyzy muzete pouzit specialni volby nebo direktivy. Nasledujici odstavce popisuji nektere z techto modifikaci, a tez volby a direktivy, ktere muzete k tomuto zlepseni optimalizace uzit. 5.1 Analyza datovych zavislosti Nejcastejsi prekazkou vektorizace je tzv. datova zavislost (data dependency). Ta nastane, jestlize by vektorizace zpusobila jednu z nasledujicich situaci: . Slovo v pameti ma byt prepsano drive, nez je pouzito. . Slovo v pameti ma byt pouzito drive, nez je do neho ulozena hodnota. Meli byste se tedy snazit psat program bez techto zavislosti. V nekterych pripadech je lze dodatecne odstranit tak, ze vy nebo prepro- cesor fpp zmenite strukturu programu. Abychom porozumeli tomu, co datova zavislost znamena, uvedomme si, jak se skalarni zpracovani smycky lisi od vektoroveho. Ve skalar- nim zpracovani jsou vysledky ulozeny do pameti v kazde iteraci smycky, takze kazda hodnota vypoctena behem jedne iterace je pristupna k po- uziti v iteracich nasledujicich. Vektorove procesory pouzivaji najednou cele skupiny dat (vektory) a operuji s nimi jako s elementarnimi jednotkami (velikosti az do 64 prvku v pripade pocitace Cray). Data zavedena do vektoroveho registru mohou byt poslana do funkcnich jednotek nebo zpet do pameti, a data z funkcnich jednotek mohou byt poslana do vektorovych registru nebo do jine funkcni jednotky. Dokud neni cela vektorova operace dokoncena, nejsou vysledky ulozeny v pameti, a jednotlive vysledky nejsou z vek- toroveho registru dosazitelne. Jestlize smycka neobsahuje zadnou datovou zavislost, dava stejne vysledky, je-li provedena ve vektorovem nebo skalarnim modu. Jestlize v ni vsak datova zavislost existuje, vysledky mohou byt ruzne. Kdyz preprocesor fpp nebo prekladac zavislost najde, predpoklada, ze si prejete skalarni zpracovani, a vygeneruje pro smycku skalarni kod. Uvazujeme nasledujici smycku: DO 2 J = 2,3 T(J) = S(J-1) S(J) = C(J) 2 CONTINUE Predpokladejme, ze S(1) = 10 C(2) = 2 S(2) = 20 C(3) = 3 Skalarni zpracovani da pro J = 2 T(2) = S(1) = 10 S(2) = C(2) = 2 pro J = 3 dostavame T(3) = S(2) = 2 zde je T(3) prirazena nova hodnota S(2) S(3) = C(3) = 3 Vektorove zpracovani dava T(2) = S(1) = 10 T(3) = S(2) = 20 zde je T(3) prirazena nezmenena hodnota S(2) S(2) = C(2) = 2 S(2) je nyni nove definovano S(3) = C(3) = 3 Hodnota T(3) je v druhem pripade odlisna, protoze vektorove zpra- covani v kazdem kroku pusobi na cele pole. Tedy tato smycka obsahuje datovou zavislost. Poznamenejme, ze preprocesor fpp v zasade umi pre- organizovat smycku tak, ze ji lze vektorizovat (viz odst.5.3 - 5.5). 5.2 Smycka bez datove zavislosti Provadi-li preprocesor fpp analyzu datove zavislosti a zjisti-li, ze smycka takovou zavislost neobsahuje, dosadi tesne pred ni direktivu CDIR@IVDEP, coz usetri prekladaci cft77 pri analyze teto smycky praci a vlastni preklad je tudiz rychlejsi. 5.3 Smycka s podminenou datovou zavislosti Zjisti-li preprocesor fpp, ze smycka muze, ale nemusi obsahovat datovou zavislost v zavislosti na hodnote promenne v okamziku vlastni- ho behu programu, vygeneruje podmineny kod. Napr. DO 10 I = 1,N A(IP + 1) = A(I) + B(I) 10 CONTINUE je prelozeno do tvaru IF (ABS(IP) .LE. 0 .OR. ABS(IP) .GE. N) THEN CDIR$ IVDEP DO 10 I = 1,N A(IP + I) = A(I) + B(I) 10 CONTINUE ELSE CDIR$ NOVECTOR DO 77001 I = 1,N A(IP +I) = A(I) + B(I) 77001 CONTINUE CDIR$ VECTOR ENDIF V zavislosti na hodnote IP muze nebo nemusi totiz tato smycka datovou zavislost obsahovat. 5.4 Smycka s datovou zavislosti Jestlize preprocesor fpp zjisti, ze smycka datovou zavislost ob- sahuje, snazi se zmenit poradi prikazu ve smycce tak, aby ji odstra- nil. Jestlize se mu ji takto odstranit nepodari, pokusi se ji odstra- nit pouzitim docasneho pole, zmenou struktury vnorenych smycek (viz odst.5.7) nebo rozdelenim smycky na vektorizovatelnou a nevektorizova- telnou cast. 5.5 Direktivy pro datovou zavislost Preprocesoru fpp muzete pri optimalizaci vaseho programu pomoci tim, ze mu poskytnete dodatecnou informaci pomoci direktiv. Uvedme dve z techto direktiv - NODEPCHK a RELATION: NODEPCHK instruuje preprocesor fpp, aby ignoroval mozne datove zavislosti. Tuto direktivu uzijte pouze tehdy, jste-li si opravdu jis- ti, ze tam nejsou. V nasledujicim prikladu si preprocesor fpp nemuze byt jist, ze N1 se nerovna N2, coz by zpusobilo datovou zavislost, takze vygeneruje podmineny kod (viz odst.5.3): SUBROUTINE MOVE (A,B,N,N1,N2) REAL A(N,*),B(*) DO 10 I = 1,N A(I+1,N1) = A(I,N2) + B(I) 10 CONTINUE Vite-li vsak, ze N1 a N2 si nikdy nejsou rovny, dosadite direktivu CFPP$ NODEPCHK tesne pred smycku, a smycka bude vektorizovana. RELATION poskytuje informaci preprocesoru fpp o mezich indexu po- le, aby mohl urcit, zda lze smycku bezpecne vektorizovat. Format teto direktivy je CFPP$ RELATION (simple1 .rel. simple2) kde simple1 a simple2 jsou jednoduche celociselne promenne a rel je GT, LT, GE, LE, EQ nebo NE se standardnim fortranskym vyznamem. Napr. CFPP$ RELATION (J .GE. N) ... DO 100 I = 1,N A(I+J) = A(I) + B(I) 100 CONTINUE Tato direktiva poskytuje preprocesoru fpp dodatecnou informaci, aniz by vsak absolutne specifikovala, ze se datova zavislost nevyskytuje jako v pripade NODEPCHK. 5.6 Rozvoj vnorenych smycek Plati pravidlo, ze vektorizovany mohou byt pouze nejvnitrnejsi smycky. Vetsi vnejsi smycky by tak mohly zustat vektorizaci nedotceny. Aby program byl optimalne prelozen, mohou se nektere smycky rozvinout. Rozvinuti (unwinding) znamena, ze se smycka nahradi n kopiemi tela smycky (n udava, kolikrat je smycka provadena). Vhodnymi kandidaty pro toto rozvinuti jsou prave nektere male nejvnitrnejsi smycky. Rozvinu- tim se vnitrni smycky odstrani, vnejsi smycka se tak stane vnitrni, a umozni se tak jeji vektorizace. Smycky, ktere prekladac rozvinul, jsou vyznaceny v jeho tiskove sestave. Predpoklady pro rozvinuti smycky jsou nasledujici: . jak vnitrni, tak vnejsi smycka musi byt vektorizovatelna . vnitrni smycka musi mit konstantni pocet kroku, a to nejvyse 5 . vnitrni smycka se nesmi vetvit . vnitrni smycka musi mit mene nez 40 prikazu Rozvinuti smycky vsak nemusi nutne urychlit beh programu, a v pripade, jsou-li vase data citliva na poradi, v kterem jsou vyrazy vy- pocitavany, muze ovlivnit presnost numerickych vysledku. Poradi opera- ci se totiz v obou pripadech muze lisit. Abyste rozvinuti smycek za- branili, uzijte prekladacovou direktivu CDIRS$ NOVECTOR tesne pred vnejsi smyckou a CDIR$ VECTOR tesne pred vnitrni smyckou. 5.7 Zmena struktury vnorenych smycek Jelikoz pouze nejvnitrnejsi smycka muze byt vektorizovana, pre- procesor fpp analyzuje do sebe vnorene smycky (nested loops), aby zjistil, zda vnejsi smycka neni pro vektorizaci a optimalizaci vhod- nejsi. Zjisti-li, ze by bylo vyhodnejsi vektorizovat vnejsi smycku, a ze vysledky vypoctu se po restrukturalizaci smycek nezmeni, zameni vnitrni smycku za vnejsi a naopak. Kriteria, uzita pro tuto analyzu, zahrnuji datovou zavislost, velikost poli a delku vektoru. Obecne, lepsi podminkou jsou delsi vektory, kratsi delky kroku (strides), mene datovych zavislosti a mene podminene vykonavanych prikazu. Vice infor- maci o delce kroku najdete v odst.7.1. Optimalizacni pristup pro urcitou smycku muzete tez nadiktovat, protoze preprocesor si vzdy neni schopen opatrit dostatek informaci o tom, kterou smycku je nejlepe vektorizovat. Jestlize to vite, oznacte ji direktivou CFPP$ SELECT kterou umistete primo pred prikaz DO te smycky, ktera ma byt vektori- zovana. 5.8 Maticove nasobeni Smycky realizujici maticove nasobeni mohou byt zameneny ekviva- lentnimi podprogramy z knihovny LIBSCI, ktere jsou maximalne optimali- zovany. Slouzi k tomu volba -Wd"-ej" pro prekladac cf77 (tato volba je nastavena implicitne). Tyto knihovni podprogramy zahrnuji MXM, MXMA, SGEMM, CGEMM, SGEMV a CGEMV. Vice se dozvite vyuzitim povelu man fpp. 5.9 Linearni rekurze Preprocesor fpp je schopen rozpoznat a prevest nektere linearni rekurze prvniho a druheho radu na volani optimalizovanych podprogramu z knihovny LIBSCI. K temto podprogramum patri FOLR, FOLR2, FOLRP, FOLR2P, FOLRC, SOLR a SOLR3. K tomu je zapotrebi specifikovat volbu cf77 -Wd"-eb". Vice informaci ziskate opet povelem man fpp. 5.10 Odkazy na funkce a volani subrutin Jak odkazy na funkce, tak volani subrutin, ktere se vyskytuji uvnitr smycek, vektorizaci znemoznuji. Neplati to vsak pro prikazove funkce a standardni vnitrni funkce, ktere vektorizaci smycky neznemoz- nuji. Preprocesor fpp lze vsak instruovat, aby funkce a subrutiny roz- vinul nebo aby je ze smycky vydelil (viz odst.5.11). 5.11 Rozvoj podprogramu Podprogramy uvnitr smycek nejsou automaticky rozvijeny. Preproce- sor fpp vsak muzete instruovat, aby tak ucinil, a to pomoci voleb na povelove radce nebo pomoci direktiv CFPP$. Telo podprogramu pak bude dosazeno primo do volajici smycky. Pritom volby na povelove radce pro fpp maji prednost pred direktivami. Muzete nechat rozvinout vsechny nebo pouze vybrane podprogramy. Tyto rozvoje podprogramu (in-line ex- pansions) je vsak treba uzivat uvazlive (viz odst.5.13). Nasledujici volby a direktivy vam umozni rozvinout vsechny nebo pouze specifikova- ne podprogramy: . Volba -Wd"-e8" pro cf77 instruuje preprocesor fpp, aby ve vstupnim souboru nasel podprogramy, ktere by mely byt rozvinu- ty. . Volba -Wd"-I podprogram1,podprogram2" pro cf77 specifikuje podprogramy, ktere maji byt rozvinuty in-line. . Direktiva EXPAND ma tvar CFPP$ EXPAND [(seznam)] a muze byt uzita k rozvinuti specifikovanych podprogramu, uve- denych v seznamu. Neni-li specifikovan zadny podprogram, je rozvinut ten, ktery nasleduje. Rozvoj podprogramu jednak usetri cas potrebny pro volani podpro- gramu, jednak umozni vektorizaci nekterych smycek, ktere by jinak ne- mohly byt optimalizovany. Takto upraveny program se tim vsak stava me- ne prehlednym a srozumitelnym, coz je proti mysli zvlaste tem progra- matorum, kteri si zvykli na zasady "dobreho", strukturovaneho progra- movani. 5.12 Omezeni pro rozvoj podprogramu Podprogramy se rozvijeji, jen jsou-li splneny nektere podminky: . Ma-li podprogram vice nez 50 radek, rozvine se jen tehdy, je- li preprocesor fpp volan s volbou -M. . Podprogramy, ktere maji byt rozvinuty, nemohou volat jine vnejsi podprogramy (plati pro automaticke rozvinuti). . Vsechny bloky COMMON, pouzite ve volajicich a volanych podpro- gramech, se musi presne shodovat. . Podprogramy s argumenty typu CHARACTER nebo typu CHARACTER FUNCTION nemohou byt rozvinuty. . Podprogramy obsahujici prikazy DATA, ASSIGN, SAVE, ENTRY, alternativni prikazy RETURN nebo vnitrni funkce LOC nemohou byt rozvinuty. . Rekurzivni podprogramy nemohou byt rozvinuty. 5.13 Nevyhody rozvoje podprogramu Rozvoj podprogramu ma tyto nevyhody: . V pripade, ze se rozviji prilis mnoho podprogramu, muze se ve- likost programu stat neunosnou. . Stane-li se program prilis dlouhy, cas potrebny pro preklad se potom muze neunosne prodlouzit. . Ladeni pomoci cdbx se muze zkomplikovat, protoze je-li chyba v rozvinutem podprogramu, bude hlasena z jineho podprogramu, nez byste ocekavali. . Je-li rozvinuty podprogram modifikovan, musi byt znova prelo- zen jak volajici, tak rozvinuty podprogram. Tyto typy vzajem- nych zavislosti by mely byt zahrnuty v tzv. makefiles. . Za jistych okolnosti muze rozvinuty podprogram beh celeho pro- gramu zpomalit. Overte si proto, zda vas program po rozvinuti skutecne pracuje rychleji. 5.14 Rozstepeni smycek Preprocesor fpp muzete tez vybidnout k tomu, aby vydelil odkazy na funkce a volani subrutin do separatnich smycek, oddelenych od tech, ktere by byly vektorizovatelne. Presvedcte se vsak nejprve, ze podpro- gramy nemaji vedlejsi rekurzivni efekty. Aby toto rozstepeni (split- out) bylo provedeno, pouzijte direktivu CFPP$ SPLIT 6. Nepouziti dvojnasobne presnosti Promenne ve dvojnasobne presnosti (28 platnych cislic) nejsou ob- vykle na pocitaci Cray zapotrebi. Navic vyraznym zpusobem zpomaluji beh programu. Zmente proto ve svych programech, ktere jste puvodne psali pro jiny pocitac, dvojnasobnou presnost na jednoduchou. Prejete-li si vsak zachovat vas program v jeho puvodnim tvaru s dvojnasobnou presnosti tak, aby zustal prenositelny, pouzijte pro pre- kladac cf77 volbu -dp, ktera zpusobi konverzi vsech deklaraci dvojna- sobne presnosti a vnitrnich funkci na jejich ekvivalenty v jednoduche presnosti, tedy napr. cf77 -dp -o zdroj.x zdroj.f Tuto volbu vsak nepouzivejte, zavisi-li logika vaseho programu na ve- likosti strojoveho slova (napr. spojujete-li prikazem EQUIVALENCE do- hromady promenne v jednoduche a dvojnasobne presnosti). Rovnez pouzi- vate-li specialni podprogramy z matematickych knihoven v dvojnasobne presnosti (tedy nikoliv standardni vnitrni (intrinsic) podprogramy), napr. podprogramy IMSL, nezapomente je soucasne konvertovat na jejich ekvivalenty v jednoduche presnosti. 7. Optimalizace pouziti pameti Centralni pamet (central memory) pocitace Cray Y-MP EL obsahuje 32 milionu slov (32 Mwords) o delce 8 Bytu (64 bitu). Pamet je organi- zovana do ctyr sekci (sections) a kazda sekce je dale rozdelena do 16 tzv. banku (banks). Pocitac Cray ma tedy celkem 64 banku. Zakladni jednotka (CPU) ma ctyri spojeni s pameti, kazde z nich do jedne ze ctyr sekci. 7.1 Pametove odkazy a delka kroku K optimalizaci vaseho programu potrebujete vedet, jak se odkazuje na centralni pamet. Hardwarove instrukce pro odkazy na vektorovou pa- met, cteni a ukladani, se lisi v zavislosti na poctu slov z pameti, ktere se nalezaji mezi jednotlivymi prvky vektoru. Tento pocet slov se nazyva delka kroku (stride). Existuji tri kategorie vektorovych odka- zu, rozlisene podle delky kroku: . Jednotkova delka kroku (unit stride), kdy zakladni jednotka pristupuje postupne k sousednim mistum v pameti. Napr. nasle- dujici dve smycky pouzivaji jednotkovou delku kroku, protoze k prvkum pole se pristupuje postupne: DO 2 J = 1,10 TOTAL = TOTAL + W(J+3) 2 CONTINUE DO 2 J = 1,3 Y(J,2,1) = COS(J*PI) 2 CONTINUE Prvni smycka uziva kroku jednotkove delky ke cteni pole W. Druha smycka pouziva jednotkoveho kroku pri ukladani pole Y. . Nejednotkova delka kroku (non-unit stride) znamena krok vetsi nez jedna. Provadi se pristup k datum, ulozenym v pameti jako kazde n-te slovo pocinaje pocatecnim mistem, kde n je cele cislo vetsi nez jedna. Je-li n liche, je krok nazyvan nejed- notkovym lichym krokem (non-unit odd stride); je-li n sude, jde o nejednotkovy sudy krok (non-unit even stride). Napr. na- sledujici smycky pouzivaji nejednotkovou delku kroku: DO 2 J = 1,20,5 TOTAL = TOTAL + W(J) 2 CONTINUE DIMENSION Z(4,2,3) DO 2 J = 1,3 Z(3,1,J) = SIN(J*PI) 2 CONTINUE Prvni smycka pouziva nejednotkoveho licheho kroku velikosti 5 pro cteni pole W, druha pouziva nejednotkoveho sudeho kroku velikosti 8 pro ulozeni pole Z. . sber/rozptyleni (gather/scatter) oznacuje promenny krok: k mistum v pameti se pristupuje nepravidelne. Nazyva se sber (gather) pro cteni a rozptyleni (scatter) pro ukladani. Tyto hardwarove instrukce vyzaduji dva vektorove registry: jeden pro data a druhy pro relativni adresy v pameti, z kterych se "sbira" (gather) nebo na ktere se "rozhazuje", "rozptyluje" (scatter). Napr. nasledujici smycka "sbira" nepravidelne umis- tene prvky vektoru X za pomoci indexoveho pole K: DO 2 J = 1,N Z(J) = A + X(K(J)) 2 CONTINUE Nasledujici smycka zase "rozhazuje" nepravidelne prvky vekto- ru X pomoci indexoveho pole K DO 2 J = 1,N Z(K(J)) = A + X(J) 2 CONTINUE 7.2 Jak se vyhnout pametovym konfliktum Pametove konflikty (memory conflicts) vzniknou, kdyz vas program ma pametovy pozadavek drive, nez muze byt ve skutecnosti proveden (nez je pristupova cesta k danemu mistu v pameti volna). Tyto konflikty zpusobuji znacne prodlevy, ktere vyznamne prodluzuji spotrebovany cas. Na pocitaci Cray se tyto konflikty mohou objevit na urovni sekce, pod- sekce nebo banku. Prvky pole jsou ulozeny v pameti postupne prostrednictvim sekci a banku. Abyste se vyhnuli pametovym konfliktum, vyhnete se nejednotko- vym delkam kroku v pameti, zvlaste pak sudym krokum vetsi velikosti. Vzhledem k tomu, ze existuje 64 banku, krok 64, jak je ukazano nize, je nejhorsim moznym pripadem z hlediska pametovych konfliktu. BANK 1 2 ... 64 1 ... 64 1 ... ARRAY A(1) A(2) ... A(64) A(65) ... A(128) A(129) ... Nejen ze vas program v kazde iteraci pak odkazuje na stejnou sek- ci,ale zaroven v kazde iteraci odkazuje na stejny bank. Krok 16 zpuso- bi pristup ke stejnemu banku v kazde ctvrte iteraci, ktery je pak rov- nez prilis frekventovany a dochazi tedy k castym pametovym konfliktum. Vysledky pro sber/rozptyleni jsou znacne zhorseny lichymi kroky, protoze rozptyleni/sber vytvareji nahodne pametove pristupy, ktere ma- ji tendenci byt samy se sebou konfliktni. Nicmene tyto konflikty ne- jsou tak vazne jako ty, ktere jsou zpusobeny sudymi kroky znacne del- ky, ktere konflikty v obsazeni banku (bank-busy conflicts) takrka za- rucuji. Velke sude kroky (napr. 32) v pameti mohou byt zpusobeny indexem smycky DO, ktery vzrusta o 32 pri kazdem pruchodu smyckou. Tyto delky kroku vsak mohou byt tez dany zpusobem, kterym je smycka dimenzovana, jako v nasledujicim prikladu: DIMENSION S(8,4,750) DO 2 J = 1,8 DO 2 K = 1,750 S(J,3,K) = T(J) * C(K) 2 CONTINUE Delka kroku 32 v pameti vznikne tak, ze kazdy krok K jde pres 8*4 pa- metovych mist odpovidajicich dvema levym indexum v deklaraci DIMEN- SION. To vede k zavaznym konfliktum v sekcich a v bankach. Existuje vsak nekolik metod, ktere lze uzit, chcete-li se vyhnout problemum to- hoto druhu. Jsou popsany v nasledujicich odstavcich. 7.3 Zmena poradi smycek Program z posledniho prikladu odst.7.2 prepiseme takto: DIMENSION S(8,4,750) DO 2 K = 1,750 DO 2 J = 1,8 S(J,3,K) = T(J) * C(K) 2 CONTINUE Toto usporadani vylouci pametovy konflikt naznaceny v predchozim odstavci. Prehozeni prikazu DO vsak zpusobi, ze bude vektorizovana vnitrni smycka, ktera ma delku pouze 8, coz neni prilis efektivni. 7.4 Prehozeni rozmeru pole Tentyz program zapiseme takto: DIMENSION S(750,4,8) DO 2 J = 1,8 DO 2 K = 1,750 S(K,3,J) = T(J) * C(K) 2 CONTINUE Pametovy konflikt se eliminuje tim, ze ucini z K levy index, a tim se zpusobi, ze krok se stane jednotkovym. 7.5 Rozsireni rozmeru pole Zapis tehoz programu DIMENSION S(9,5,750) DO 2 J = 1,8 DO 2 K = 1,750 S(J,3,K) = T(J) * C(K) 2 CONTINUE vede k eliminaci konfliktu v bankach rozptylenim pristupu na ruzne banky. Tato smycka ma nyni lichou delku kroku (9*5=45). Shrnuti: Abyste se vyhnuli pametovym konfliktum, uzivejte jednot- kovych kroku, kdekoliv je to ve vasem programu mozne, a mejte na zre- teli, ze kratke sude kroky (2,4,6,...) nebo sber/rozptyleni jsou lepsi nez dlouhe sude kroky (32,64,128,...). 8. Optimalizovane matematicke knihovny Nas pocitac Cray ma k dispozici radu matematickych knihoven a umoznuje vam tak pristup k vyzkousenym a spolehlivym podprogramum, ktere provadeji nejcastejsi matematicke operace. Pouziti techto pod- programu vam muze ulehcit praci a pomoci pri optimalizaci vaseho pro- gramu, protoze vetsina techto podprogramu je jiz pro pocitac Cray op- timalizovana. Na pocitaci Cray mate k dispozici balik BLAS (Basic Linear Algeb- ra Subprograms) pro operace z linearni algebry typu vektor-vektor, ma- tice-vektor a matice-matice, balik LAPAC (Linear Algebra Package), starsi baliky LINPACK (Linear Algebra Package) a EISPACK pro vypocty vlastnich hodnot, podprogramy pro ridke matice, pro FFT (Fast Fourier Transform) aj. [5]. Byla tez nainstalovana posledni verze knihovny NAG [6] a CERNska knihovna [7]. Tyto knihovny musite explicitne prisesta- vit parametrem -l nag nebo -l packlib,mathlib,cernlib 9. Literatura [1] C-1: Zpracovani programu ve fortranu (I.Veltrusky, SAVT 1993) [2] UNICOS Performance Utilities (Reference Manual) (SR-2040) [3] UNICOS Fortran Library Reference Manual (SR-2079) [4] cf77 Compiling System, Vol.3: Vectorization Guide (SG-3073) [5] UNICOS Math and Scientific Library Reference Manual (SR-2081) [6] NAG Fortran Library Mark 16 [7] CERN Program Library: CERNLIB (July 1992)