Tento článek navazuje na předchozí příspěvky věnované problematice superpočítačového centra Brno. Obsahem jsou informace o schopnostech a možnostech základního procesoru počítače POWER Challenge a jeho optimalizujících překladačů. Článek je určen především programátorům, ale informace v něm obsažené mohou posloužit i dalším zájemcům o výkonnou výpočetní techniku při úvahách o skutečných možnostech superskalárních počítačů. Je probírána pouze otázka programování jednoho procesoru, optimalizace paralelních programů bude obsahem některého z dalších příspěvků.
Počítač POWER Challenge je základním výpočetním uzlem superpočítačového centra Brno. Je vybaven procesory R8000, bežícími na frekvenci 75MHz (v současné době již firma dodává procesory s frekvencí 90MHz, které mají o předpokládaných 20 % vyšší výkon). Procesory R8000 jsou superskalární RISC procesory, což znamená, že jsou v každém vnitřním cyklu schopny vykonávat více jak jednu instrukci. V případě R8000 jsou to dvě operace v pevné řádové čárce (kam patří i veškeré operace manipulující s adresami) a dvě operace v pohyblivé řádové čárce1. Procesor R8000 je ve skutečnosti tvořen dvěma jednotkami pro práci s pevnou řádovou čárkou a dvěma jednotkami pro práci s pohyblivou řádovou čárkou. Teoretický maximální výkon celého procesoru je pak 300 milionů operací za sekundu (4*75) a je dosažitelný pouze tehdy, je-li skutečně možno v každém ze 75 milionů cyklů za sekundu provést současně všechny čtyři operace2 a současně jsou vždy k dispozici všechny operandy. Tato poslední podmínka však není jednoduše splnitelná. Je třeba si uvědomit, že procesor pracuje podstatně rychleji než operační paměť a ani mimořádně široká sběrnice počítače POWER Challenge (s propustností 1,2GB/s)3 nestačí procesor zásobovat. Tento problém je u počítače POWER Challenge (stejně jako i u jiných počítačů s procesory obdobných parametrů) řešen přítomností velmi rychlé vyrovnávací paměti (cache), která je s procesorem spojena rychlejší sběrnicí a je schopna rychleji předávat (a zapisovat) data (a je ovšem příslušně dražší). U počítače POWER Challenge má sekundární cache velikost 4MB. Cache je schopna poskytovat data s maximálním zdržením jednoho cyklu, zatímco přístup k datům v hlavní paměti způsobí průměrné zdržení kolem 80 cyklů.
Z uvedeného jasně vyplývá, že skutečně efektivně bude procesor R8000 využit jen tehdy, bude-li možné provádět instrukce současně a budou-li včas k dispozici všechny operandy. To však obecně nelze zajistit, jako např. v situaci
| i++; j = i+1; |
kdy druhá operace musí čekat na výsledek první (dokud není operace dokončena, není přirozeně k dispozici příslušný operand)4. V tomto případě, i kdyby hodnota i byla k dispozici, nelze obě operace provést současně - jedna z aritmetických jednotek zůstane nevyužita a dosáhne se jen 50 % teoretického výkonu (ve skutečnosti ještě méně, protože bude třeba další cykly čekat na dokončení operace).
Za běžných podmínek je úkolem překladače (kompilátoru) nalézt příslušné datové závislosti a uspořádat instrukce tak, aby bylo maximalizováno paralelní vykonávání instrukcí v jediném procesoru a současně aby všechna data byla včas k dispozici. Vysoce optimalizující kompilátory, které jsou dodávány jako součást vývojového prostředí operačního systému IRIX 6.x, uvedené vlastnosti mají. Protože otázka generování optimálního kódu je ve své podstatě nerozhodnutelná, nelze očekávat, že by překladač dokázal vygenerovat optimální program bez pomoci programátora. Odhlédneme-li od úplného přeformulování programované úlohy (a tedy snížení algoritmické složitosti), pak nejjednodušší možností je volba vhodné kombinace klíčů, kterou překladači "poradíme", co a jak optimalizovat.
V operačním systému IRIX 6.x (plně 64bitový operační systém) jsou k dispozici optimalizující překladače jazyků Fortran 77 a C. Ve skutečnosti se jedná o jediný překladač se dvěma různými analyzátory vstupního jazyka, tzv. front-endy. Překladače obou jazyků mají proto většinu klíčů společných, vzhledem k jednodušší struktuře jazyka Fortran 77 však kompilátor tohoto jazyka dosahuje obecně lepších výsledků (tj. rychlejšího kódu) než překlad z jazyka C.5
Nativní kód pro procesor R8000 je generován klíči -64 -mips4, které jsou současně defaultním nastavením. Je generován plně 64 bitový kód - hlavní rozdíl oproti 32bitové architektuře je v délce typu long int a pointer (ukazatel), které činí 64 bitů - využívající všechny možnosti procesoru R8000 (typová řada MIPS IV). Toto nastavení je nezbytným předpokladem pro využití všech potenciálních možností překladače6, je to však pouze předpoklad.
Míra úrovně optimalizace je nastavitelná klíčem -Ox, kde x je číslo v rozsahu 0-3, zvané též úroveň optimalizace. Defaultní optimalizace má úroveň 2 (klíč -O). Jednotlivé úrovně je možno stručně charakterizovat následujícím způsobem:
| -O0 | Optimalizace vypnuta (vhodné pro ladění). |
| -O1 | Jednoduché lokální optimalizace (prakticky se neprojevuje na čase překladu). |
| -O2 | Rozsáhlé globální optimalizace (avšak takové, aby nedošlo ke změně přesnosti operací s pohyblivou řádovou čárkou). |
| -O3 | Agresivní optimalizace, které mohou měnit výsledky operací s pohyblivou řádovou čárku (jiné zaokrouhlení). |
Vzhledem ke složitosti problému však zvýšení úrovně optimalizace nemusí být jednoznačně spojeno se zrychlením výpočtu. Zejména přechod z úrovně 2 na úroveň 3 může dokonce přinést zpomalení výpočtu (snad jediná pozorovatelná zákonitost platí o délce překladu - úroveň 0 je vždy nejrychlejší, zatímco úroveň 3 je (skoro) vždy nejdelší, a to mnohdy i řádově oproti úrovni 0, zejména u velmi složitých programů). Každá úroveň optimalizace je ve skutečnosti složena z celé řady dílčích podmínek, z nichž ty nejdůležitejší jsou uvedeny dále.
Pravděpodobně nejdůležitejším pojmem je tzv. software pipelining, programový pipeline. Jeho podstatou je přeskládání operací v cyklu tak, aby bylo možno jednotlivé instrukce provádět paralelně jednotlivými aritmetickými jednotkami procesoru. Jako příklad uvažujme následující jednoduchý kód (ve Fortranu)
| do i = 1,N y(i) = y(i) + a * x(i) enddo |
Tento cyklus se přeloží do tří instrukcí - nahrání (load) hodnoty x(i) a y(i), madd a pak uložení výsledků (store) opět do y(i). Zatímco instrukce load a madd je možno provést paralelně (jsou k dispozici dvě jednotky pro operace load), je po provedení instrukce madd nutno 3 cykly čekat, než je operace ukončena a je možno její výsledek uložit do y(i). To znamená, že na vykonání jedné iterace je zapotřebí 5 cyklů procesoru7. Pokud však přeskládáme jednotlivé iterace cyklu tak, aby v době čekání na dokončení určité iterace byly již připravovány operandy pro následující operaci (a ta případně i provedena), pak můžeme dosáhnout maxima 4 iterací za 6 cyklů, tedy výrazného zlepšení8.
Programový pipeline je k dispozici pouze na nejvyšší úrovni optimalizace. K dispozici jsou i nástroje pro zjistění míry úspěšnosti překladače (což zpětně slouží jako "nápověda" míst, kterým je třeba při optimalizaci věnovat zvýšenou pozornost). Programový pipeline je uplatněn pouze u nejvnitřnějších cyklů (tj. cyklů, které nemají žádné vnořené cykly) a není aktivován, je-li v cyklu volána uživatelská funkce nebo procedura. Míru programového pipeline je možno řídit klíčem -SWP:option, kterým lze nastavit např. úroveň rozvinutí cyklu, jeho velikost, způsob zpracování podmínek v cyklu, způsob přístupu k paměti a další.
Dalším důležitým parametrem optimalizace je globální přesun kódu (global code motion), který je ovlivněn hodnotou klíče -GCM:option. Nastavení tohoto klíče ovlivňuje míru, s jakou překladač přesouvá celé bloky instrukcí s cílem dosáhnout opět jejich paralelního vykonávání (na rozdíl od SWP se zde jedná i o kód mimo cykly). Většina option je standardně vypnuta. Použití maximálních nastavení tohoto klíče může bohužel vést k chybnému kódu (což ostatně platí i pro jiné metody agresivní optimalizace - ta v žádném známém překladači není prostá chyb).
Míru optimalizace je možno dále velmi účinně ovlivnit klíčem -TENV:option, kde nejdůležitějsí hodnoty option jsou uvedeny v následujícím přehledu:
| X=0 : | Vypne veškeré spekulativní přesuny kódu. |
| X=1 : | Provádí jen nejjednodušší (a bezpečné) spekulativní přesuny kódu (předpokládá, že je vypnuto sledování podtečení). |
| X=2 : | Jako X=1, avšak navíc předpokládá, že jsou vypnuta všechna přerušení operacemi s pohyblivou řádovou čárku kromě dělení nulou. |
| X=3 : | Obdobně jako výše, ale ani dělení nulou není zapnuto. |
| X=4 : | Ignoruje všechna přerušení generovaná špatným přístupem k paměti (např. index mimo rozsah pole). |
| X=5 : | Ignoruje všechna přerušení. |
Tyto klíče je vhodné používat při současném použití klíčů -SWP a -GCM. Současně je zřejmé, že nevhodné (příliš vysoké) nastavení může vést k chybné funkci programu.
Všeobecné informace je možno překladači předat prostřednictvím klíče -OPT:option, kde mezi nejdůležitější options patří:
Kromě vlastních překladačů jsou k dispozici i pre-procesory, programy, které provádějí transformace pouze na úrovni zdrojového textu. Jejich hlavním cílem je přeskládat příkazy zdrojového programu dříve, než bude použit vlastní překladač. Pro programy ve Fortranu je k dispozici pre-kompilátor fopt, pro jazyk C pak copt. Kromě již uvedených možností transformace aritmetických výrazů (roundoff, ...) a úpravy cyklů (avšak aplikovaných s trochu jinou strategií a tedy potenciálně s jiným výsledkem než ve vlastním překladači) je tento pre-kompilátor určen k rozvoji procedur a funkcí (tzv. inlining) a k tzv. meziprocedurální analýze. Rozvoj funkcí je určen především pro odstranění overheadu spojeného s jejich voláním (a též umožňuje další optimalizace, především programový pipeline), meziprocedurální analýza se snaží získat informace o skutečných vlastnostech procedur k tomu, aby mohl být generován specializovaný kód (je možno např. detekovat nepřítomnost přiřazení globálních proměnných v těle procedury). Pre-kompilátory jsou též schopny optimalizovat velikost cyklů vzhledem k velikosti vyrovnávací paměti, případně přeskládat pořadí vnořených cyklů tak, aby bylo dosaženo maximálního využití sekundární paměti.
Jak jsme viděli, je každá úroveň optimalizace charakterizována určitými hodnotami konkrétních klíčů ovlivňujících chování překladače. Vhodným nastavením úrovně optimalizace a zpřesněním dalšími klíči je možno dosáhnout velmi podstatného zrychlení výpočtu oproti defaultnímu nastavení překladače. Při překladu náročných programů, u nichž se počítá s intenzivním využitím, se vždy vyplatí vyzkoušet řadu kombinací jednotlivých klíčů. Skutečné "vyladění" programu pro počítač POWER Challenge však vyžaduje mnohem více - je většinou nutno provést více či méně rozsáhlé ruční úpravy zdrojového textu programu tak, aby bylo dosaženo maximálního efektu. K tomu jsou přirozeně v operačním systému IRIX k dispozici další nástroje, jejich popis však již musíme odložit do některého z dalších čísel.
| 1 | A aby to celé bylo ještě složitější, existuje operace
madd, tj. multiply and add, která je rovněž
proveditelná v jediném cyklu procesoru.
... zpět do textu |
| 2 | Teoretický výkon je vlastně ještě větší, představíme-li si, že
pokaždé jsou provedeny dvě operace s celými čísly a dvě
instrukce madd, ovšem to je již zcela hypotetická
záležitost.
... zpět do textu |
| 3 | Uvědomíme-li si, že u procesoru R8000 má operand 64bitů, pak je
tato sběrnice schopna za jednu vteřinu přenést maximálně
150 milionů operandů; na 300 milionů operací však je
zapotřebí cca 600 milionů operandů za vteřinu. A to
ještě nepočítáme se zdržením na úrovni paměti, která není
schopna poskytovat - nebo zapisovat - data touto rychlostí.
... zpět do textu |
| 4 | Faktická situace je poněkud komplikovanější, ale pro základní
ilustraci problému to snad stačí.
... zpět do textu |
| 5 | K dispozici je i překladač objektově orientovaného jazyka
C++, ovšem jeho složitost jej de facto vylučuje
ze soutěže. Obecně nelze očekávat, že by netriviální programy
napsané v jazyce C++ byly do stejné míry optimalizovatelné
jako programy v C nebo Fortranu 77.
... zpět do textu |
| 6 | V nové verzi překladačů pro verzi IRIX 6.1 a vyšší
bude možno za těchto podmínek generovat i 32bitový kód
klíčem -n32.
... zpět do textu |
| 7 | Budeme-li měřit dosažený výkon počtem operací v pohyblivé
řádové čárce, dosáhneme teoretického výkonu 120 milionů operací
- nebo jen 60 milionů operací násobení - za sekundu.
... zpět do textu |
| 8 | Pokud budeme opět měřit dosažený výkon, získáme hodnotu
400 milionů operací (resp. 200 milionů násobení)
za sekundu. To je pochopitelně pouze teoretická hodnota,
protože nepočítáme s vlastními instrukcemi řízení cyklu; přesto
je dosažené zrychlení významné.
... zpět do textu |
předchozí článek
