problém validácie výsledkov, homogénna redundancia

[Kiwi]

Masívna lokalizácia v heterogénnych systémoch.

V skratke:

Projekt LHC@home používa počítače dobrovoľníkov, na simuláciu
obehu protónov v LHC (Large Hadron Collider). Pretože
pohyb častíc je chaotický, na dosiahnutie integrity
v distribuovaných výpočtoch v heterogénnych sieťach
je potrebné, aby výpočty s pohyblivou rádovou čiarkou
boli úplne identické, bez ohľadu na použité počítače.
V tejto štúdii popíšeme možné problémy a ich riešenia.


Úvod

V CERN-e boli vždy použité také počítače, ktoré maximálne
vyhovovali požiadavkám experimentov. Tak je to aj teraz,
pri vývoji LCG, celosvetovej siete, LHC Computing Grid.
Avšak v roku 1992, bol postavený klaster PaRC, z pracovných
staníc IBM, podľa požiadaviek technikov a v roku 1997, keď
poradný výbor upozornil na potrebu výrazného zvýšenia
výpočtovej sily, bol zriadený Numerical Acceleration Project
(NAP), aby navrhol potrebnú výpočtovú kapacitu. Prvým bol
desať procesorový systém Digital TurboLaser, s výkonom
800 CU,(CU, CERN Unit, je definovná ako výkon jedného CPU,
IBM 370/168 alebo Digital VAX 8600, na štyroch benchmarkoch)
neskôr rozširený na dvojnásobnú kapacitu desiatimi
pracovnými stanicami Digital. Neskôr, v súlade s požiadavkami
priemyslu a politikou informačných technológií v CERN-e,
bol zavedený nový systém, so šesťdesiatimištyrmi 2,4 GHz
dvojjadrovými PC, poskytujúcimi výkon 50 000 CU, ktorý
fungoval ako zdieľaný systém v rámci linuxového dávkového
systému.

Typická LHC Dynamic Aperture štúdia, analyzuje 5 uhlov
vo fázovom priestore, 60 náhodných zobrazení magnetických
chýb, tzv. seeds; určitý počet amplitúd vo fázovom priestore;
každý prípad obsahuje 30 párov častíc, počas 100 000 obehov.
Každá takáto štúdia vyžaduje tisíce nezávislých úloh,
z ktorých každá trvá 2 hodiny na jednom CPU, takže môže
byť spočítaná rádove v dňoch.

Polovica kapacity NAP-u bola určená na štúdiu Beam Collimation,
ale v rovnakom čase bolo potrebné vykonať podrobný prieskum
interakcie lúč-lúč, pre rádovo milión otáčok. To by ale
vyžadovalo asi šesť miliónov hodín procesorového času,
čo by bolo na danom klastri zjavne nerealizovateľné.

CPSS projekt

CERN Physics ScreenSaver system (CPSS), bol zriadený na využitie
nevyužitého výkonu CPU, na asi 5000 WINDOWS desktopoch v CERN-e,
do ktorých CERN-e vložil niekoľko miliónov dolárov. Pri skromnom
odhade 50 percentného nevyužitého výkonu na 50-tich percentách
počítacov, by výpočtová sila tohto distribuovaného systému bola
rádovo väčšia. Program SixTrack má veľmi malé nároky na vstupno-
výstupné hodnoty, hľadiska pamäťovej kapacity, menej než 1MB/6MB,
vstup/výstup, (50KB/2MB pri kompresii) a má na pracovnú jednotku/
potrebnú alokačnú kapacitu 32/65MB, preto bol takmer ideálnou
aplikáciou na distribúciu cez sieť, je portovateľný a je časťou
SPECFP2000 benchmarku.
A.Wagner of CERN poskytol webovú app obsahujúcu repozitár,
šetrič obrazovky pre WINDOWS a niekoľko PERL-ových rutín,
volateľných z LINUXU, pre vytvorenie skupiny, stiahnutie
úlohy, vrátenie výsledkov a zistenie statusu. Ďalej boli zavedené
kontolné body (checkpoints) a vlastnosti umožnújúce reštartovať
aplikáciu bez straty výsledkov z doterajších výpočtov (Restart
facility), aby neutrpela efektivita pri dlhotrvajúcich úlohách.
Prvé testy boli vykonané použitím kompilátora Compaq Fortran,
jediného kompilátora pre WINDOWS, ktorý bol v CERN-e dostupný.
Po odstranení menej závažných problémov, vynechaním CERN Library
a vynechaním LF (line feed) znakov v text. súboroch pre WINDOWS,
vznikol prvý vážny problém, a to spracovanie NaN, (Not a Number),
t.j. vrátenie nečíselnej hodnoty pri operácii s pohyblivou
rádovou čiarkou, pri ktorom výsledok operácie je nedefinovaný,
napr. druhá odmocnina zo záporného čísla. Podobný závažný
problém bolo spracovanie Inf, t.j. vrátenie nekonečna, pričom
v oboch prípadoch, boli tieto výnimky spracované 1000-krát
pomalšie, ako výpočty, ktoré vrátili platné výsledky.
Kedže testovacie a vetviace inštrukcie sú časovo podstatne
náročnejšie inštrukcie ako aritmetické, testovanie na stratené
častice sa robilo len raz za obeh a kód bol modifikovaný tak,
aby testoval každý prvok počas otáčky. Niekoľko stovák
dobrovoľníkov poskytlo počítače a prvá štúdia s 1500 úlohami,
úspešne prebehla, s výsledkami pre priemernú DA v troch častiach,
v tisícoch Linuxových dávkových súboroch. Podrobný prieskum
výsledkov ukázal, že asi 1000 zo 60 miliónov vstupných parametrov
bolo konvertovaných s rozdielom v ULP na WIN XP a WINDOWS 2000. (ULP
je Unit in the Last Place, t.j. najmenší inkrement pri operáciach
s pohyblivou rádovou čiarkou alebo tiež najmenej významný bit
mantisy pri operáciách s poh.r.č.). Kúpa, inštalácia a použitie
kompilátora Lahey-Fujistu Fortran 95 lf95 pre Linux, tento
problém odstránilo. Dalšie testovanie ukázalo, že výsledky
z Linuxu aj z WINDOWS sú identické. To nie je prekvapivé, lebo
kompilátory môžu generovať ten istý kód, nez ohľadu na rozhranie.
Výrobca deklaruje, že sa snaží o kompatibilitu,lež ju negarantuje.
Toto bol hlavný krok dopredu, až doteraz štúdia bola stále
vykonávaná na úplne kompatibilných procesoroch a systémoch.
Povzbudení výsledkami,bola začatá 300 000 úlohová štúdia, s 1000
uhlami na 100 000 otáčok, aby sme dokázali dlhodobú efektivitu
a spoľahlivosť CPSS, generujúc použiteľné výsledky, s ohľadom
na výslednú DA a východiskový uhol. Paralelne začalo časovo
náročnejšie testovanie prípadov lúč-lúč, v ktorom boli veľmi
náročné operácie s pohyblivou rádovou čiarkou. Znova niekoľko
úloh z tisícov dalo po miliónoch otáčok odlišné výsledky.
Bolo rýchlo zistené, že rozdiel je medzi 32 a 64-bitovými
systémami (Intel IA-32 a Intel IA-64/AMD Athlon 64). Po preskúmaní
identických počiatočných podmienok, po záruke, že bol simulovaný
rovnaký akcelerátor, značne vyčerpávajúca spätná analýza viedla
k detekcii otáčky, v ktorej rozdiel vznikol, potom sa našiel
príslušný krok v otáčke a nakoniec konkrétna inštrukcia
v pohyblivej rádovej čiarke. Analýza vyžadovala porovnanie
skutočnej binárnej reprezentácie čísel v poh.r.č., aby sa zistil
prvý výskyt diferencie menšej ako ULP. Výpočet trajektórie jednej
jedinej častice vyžaduje od desať od rádovo stoviek operácií
s pohyb.r.č., pre každý z 10 000 krokov v jedinej otáčke,
a hoci sa maličký rozdiel rýchlo zväčší, najobtiažnejšie je
nájsť počiatočný rozdiel. V tomto prípade bol spúšťačom rozdielu
výpočet exponenciálnej funkcie,čo bolo veľmi rýchlo dokázané
testovacím programom pozostávajúcim z niekoľkých riadkov, použitím
presného explicitného argumentu. Podobne to bolo aj s logaritmom.
Naozaj, v mnohých systémoch tieto funkcie používajú inštrukčnú
sadu procesorov x86, ako fyl12xp1 a fyl2x, ktorých mikrokód
dáva na rôznych procesoroch rôzne výsledky.

Takže sme sa vzdali požiadavky reprodukovateľnosti výsledkov
obmedzili štúdiu buď na iba 32, či iba 64-bitové systémy.
Ale pri postupnom zavádzaní výkonných 64-bitových systémov,
existoval stále veľký počet 32-bitových a tak sa zdalo, že
by mohlo pár rokov koexistovať. Je stále veľmi potrebné,
aby bola možnosť použiť nezávisle, ktorýkoľvek z nich.

Počítanie s desatinnými číslami

Portabilita počítania s číslami s pohyblivou rádovou čiarkou,
či skôr, neportabilita, bola skúmaná niekoľko rokov.
My budeme definíciu heterogénnosti redukovať na Intel
Pentium a PC s ním kompatibilné. Štandard IEEE 754-1985, ktorý
spĺňajú takmer všetky súčasné procesory, špecifikuje základné
a rozšírené formáty desatinných čísel, sčítanie, odčítanie,
násobenie, delenie, druhá odmocnina, zvyšok a porovnávacie
operácie, konverzia medzi celočíselnými formátmi a formátmi
s pohyblivou rádovou čiarkou, konverzie medzi formátmi
desatinných čísel, konverzie medzi základnými formátmi
čísel s pohyblivou rádovou čiarkou a reťazcami znakov čísel
v desiatkovej sústave a ošetrenie výnimiek. Nás zaujíma iba
aritmetika čísel s dvojnásobnou presnosťou so zaokrúhľovaním
na najbližšie párne číslo.
Avšak tento štandard je nekompletný a otvorený.
Jeho striktné dodržiavanie brzdí výkonnosť aplikácií a tak
sa v záujme konkurencieschopnosti nedodržiava. Tiež treba
vziať v úvahu príslušné štandardy konkrétneho programovacieho
jazyka. Napríklad štandard Fortran-u definuje osobitné poradie
výpočtu iba pre výrazy v zátvorkách, v ktorých každému binárnemu
operátoru prísluší pár zátvoriek, teda portabilita by si vyžaduje
prepis kódu. Tiež je potrebná explicitná kontrola kompilácie.
My používame kompilátor lf95, ktorý má vypnutú rozšírenú presnosť,
a ďalej špecifikujeme voľbu -tp, t.j. generovanie kódu
pre Pentium, takže funkcie špecifické pre určitú architektúru,
ako SSE2 alebo 3DNow, nebudú použité. Nakoniec, súčasný štandard
nepokrýva elementárne funkcie, kao exp, log a trigonometrické
funkcie. Ako príklad použijeme funkciu exp.

Riešením je crlibm

Riešenie problému korektného zaokrúhľovania výsledkov funkcií
je známe ako Table Maker's Dilemma. Ak zoberieme prípad
zaokrúhľovania, problém vzniká vtedy, keď výsledok funkcie
leží veľmi blízko k stredu úsečky, na ktorej by sme zobrazili
susedné desatinné čísla a zaokrúhlenie aproximácie f(x),
nemusí dať rovnaký výsledok ako zaokrúhlenie f(x). Ako
patologický prípad pre dvojnásobnú presnosť zoberme exp
s 53-bitovou mantisou. Binárna notácia je:
x = 1.[52]1 x 2^-53
kde číslo v zátvorkách označuje počet nasledujúcich výskytov
cifry, ktorá nasleduje za pravou zátvorkou. V tejto notácii:
exp (x) = 1.[51]001[104]1010101...
a správne zaokrúhlenie na najbližšie číslo s dvojnásobnou
presnosťou je:
exp (x) = 1.[51]01
V tomto konkrétnom prípade, hoci použijeme aproximáciu
so štvornásobnou presnosťou, (113-bitovú mantisu), vráti
nám jeden z troch výsledkov:
1.[51]010[58]00
1.[51]001[59]11
1.[51]001[58]10
ale zaokrúhlenie posledného výsledku vráti chybnú hodnotu.

Existujú softvérové knižnice, ktoré zväčšujú presnosť,
až kým nedosiahneme korektný výsledok zaokrúhľovania. Ked si
pozriete web, nájdete niekoľko knižníc pracujúcich s dvojnásobnou
presnosťou. Pretože našim cieľom je reproducibilita výsledkov,
tak sa to može zdať ako jedno z extrémnych riešení. Jeho výhoda
je v tom, že všetky tieto knižnice budú dávať výsledy s presnosťou
na posledný bit, takže možeme použiť ktorúkoľvek.
Prvá z nich bola IBM libultim, kto už nie je podporovaná.
MPFR je knižnica s ľubovoľnou presnosťou a teda je extrémne
pomalá, v porovnaní s libm v Linuxe. Knižnica crlibm od ENS-Lyon
je stále podporovaná, je teoreticky dokázané, že zaokrúhľuje
správne, a robí to trochu pomalšie ako libm. Nakoniec, SUN má
svoju libmcr.

| priemer | maximum
libm | 365 | 5528
crlibm | 432 | 41484
mpfr | 23299 | 204736

Tab. 1. Relatívne časy pre exp na Pentiu 4 Xeon, s gcc 3.3


Na ilustráciu portability sme použili náš testovací
program. Jednoduchý test exp (), použijúc g77 a libm, s miliónom
argumentov, od -0,5 do 0,5, našiel 5 rozdielov medzi IA-32
a IA-64, 7 medzi IA-32 a AMD64, 2 medzi IA-64 a AMD64. Všetky
rozdiely sú na 1 ULP. Porovnajúc libm a crlibm sme zistili,
že libm dáva korektné výsledky, ale v 304 prípadach, len
za predpokladu, že je povolená Extended Precision, ak nie,
tak v 134 623 prípadoch zaokrúhľuje nesprávne. Podobne, ale
použijúc lf95 kompilátor a knižnicu sme našli 7 rozdielov
medzi IA-32 a IA-64, 7 medzi IA-32 a AMD64, a 4 medzi IA-64
a AMD64. Rovnaký testovací program použijúc crlibm a kompilujúc
piatimi rôznymi kompilátormi, dával identické výsledky na týchto
troch architektúrach.
Knižnica crlibm poskytovala v roku 2004 exp, log, log10,
sin, cos, tan, atan, sinh a cosh v štyroch štandardných
zaokrúhľovacích módoch. Pár skriptov postačovalo na zmenu
volaní funkcií v SixTrack-u, tak aby volali ekvivalentne
funkcie v crlibm, t.j. exp na exp_rn, sin na sin_rc, atd.
Po modifikovaní SixTrack-u, všetky numerické rozdiely
v našich testoch zmizli, aj v najnáročnejšom lúč-lúč prípade,
v ktorom sú často volané funkcie exp a log. Štúdia s 1000
uhlami bola spustená v novej verzii a všetky úlohy boli spustené
najmenej dvakrát. Všetky vzniknuvšie rozdiely, boli sposobené
krachom procesorov, na dvoch desktopoch a na dávkovom procesore
v počítačovom centre.
Stručne, aby sme dostali dve binárky, ktoré dávajú
identické výsledky pre Linux a pre WINDOWS, musíme:
1. zmeniť všetky volania funkcií na ekvivalent v crlibm
2. stiahnuť a skompilovať crlibm s nastaveniami
zaručújúcimi portabilitu
3. použiť Lahey-Fujitsu Fortran 95 compiler s vypnutou
Extended Precision (rozšírená presnosť)
4. vygenerovať kód pre Pentium s -tp
5. vytvoriť staticky zlinkovanú binárku

Po zbehnutí milióna 100 000 a 1 000 000 otáčkových úloh,
mnoho z nich najmenej 2 alebo 3-krát, sme presvedčení,
(hoci to nemôžeme dokázať), že všetky numerické rozdiely
sú spôsobené zlyhaním hardvéru či pretaktovaním CPU.

LHC@HOME

Počas toho, kolegovia v CERN-e nastavili jednoduchý Berkeley
Open Infrastructure for Network Computing (BOINC) server,
nasledovníka SETI@home, a oporučili použitie SicTrack-u
ako pilotnej aplikácie. SixTrack bol modifikovaný na volanie
rutín z BOINC rozhrania, a na vrátenie sumárneho súboru
s výsledkymi, ktorý bol menší ako 10 KB, aby bola zaručená
skalabilita pri náraste počtu klientov. BOINC bol nastavený
tak, aby spustil každú úlohu najmenej trikrát a zvalidoval
iba výsledky, z ktorých 2 sú identické. Neskoršie verzie
BOINC-u obsahujú novú vlastnosť zvanú Homogénna redundancia,
ktorá poskytuje všeobecné riešenie pre divergentné aplikácie,
ako SixTrack, opakovaním úloh iba na kompitibilnom hardvéri.
Naše riešenie nám umožňuje použiť ktorékoľvek Pentium alebo
kompatibilný hardvér, na získanie identických resultov.
Po úspešnom prebehnutí počiatočných testov, bola
pozvaná verejnosť, na participáciu v LHC@HOME. Zapojilo sa
viac než 30 000 ľudí z celého sveta s viac než 60 000 počítačmi.
Za posledný rok, viac než 2/3 zo 600 000 úloh, pre nastavenie
LHC, bolo ukončených. To znamená asi 300 procesororokov,
alebo 3 roky použitia klastra NAP. Musíme zdôrazniť, že
jeden človek na čiastočný úväzok je zodpovedný za rozdelenie
úloh na rozumné dávky, 10 až 20 tisíc úloh. LHC@HOME klienti,
ktorým sme veľmi povďační, boli motivovaní BOINC kreditmi,
a možu stratiť motiváciu, počas periód, v ktorých sa analyzujú
výsledky a pripravujú sa budúce úlohy.
Hoci nie je dostupná detailná štatistika, menej než 3 %
výsledkov, je odmietnutých BOINC kôrom. To je porovnateľné
s inými BOINC projektmi. Sme presvedčení, že tieto výsledky
prišli v dôsledku zlyhanie počítačov, chýb v sieťovej
komunikácii alebo iného porušenia dát. Iba dáta zvalidované
BOINC-om sa vrátia konečnému užívateľovi.

Záver

Teraz možu časticoví fyzici vykonať štúdie, so SixTrack-om
a dávkovým systémom v CERN-e, v BOINC, v CPSS, jednoducho
nastavením runtajmového parametra: "platform", podla vyssie
uvedeného a vytvorením cron vstupnej tabuľky, štvorriadkovým
skriptom, aby získali platné výsledky. Všetky systémy možu
bežať paralelne, alebo len na určitých podmnožinách úloh,
aby sa zrýchlila kompletizácia štúdie. Toto 10 až 100
násobné zvýšenie výpočtovej kapacity, bolo získané len
s veľmi skromnými investíciami do hardvéru (WWW PC server,
backup pre CPSS a 2 PC servery pre BOINC) a s malým možstvom
pracovníkov, ktorí sa starali o servery. Najväčšie náklady
nevyžaduje mofifikácia aplikácií, ale testovanie a overenie
reprodukovateľnosti výsledkov, čo bolo primárnym cieľom.
Pri distribiovaných výpočtoch je zvlášť dôležité to, že je
možné prispôsobenie aplikácie na akýkoľvek procesor,
na ktorom boli získané overené výsledky.
Veríme, že metodológia može byť použitá aj na IEEE
754 kompatibilné procesory, ako Apple Macintosh, SUN, IBM
Power PC. Zahrnutie potrebnej zátvorkovej notácie, aby sa
zaručilo jedinečné poradie pri vyhodnocovaní aritmetických
výrazov, by malo poskytnúť identické výsledky, bez ohľadu
na stupeň optimalizácie a s akýmkoľvel kompilátorom, zhodným
s Fortran 77/95. Podobný postup môže byť použitý aj pri
aplikáciách vyhovujúcich štandardu C++ C99.

Z originálu:
MASSIVE TRACKING ON HETEROGENEOUS PLATFORMS
E. McIntosh, F. Schmidt, CERN, 1211 Geneva 23, Switzerland
Florent de Dinechin LIP, ENS, 46 allée, d'Italie, 69364 Lyon cedex 07, France
preložil: rottenkiwi

Pretože mám silné dioptrie, skončenú len
základnú školu, nemám na kvalitný textový
editor so spelling checkerom, lahšiu formu
dyslexie, lahšiu formu mentálneho postihu,
ospravedlnte prosím, úmerne zníženú kvalitu
prekladu.
Ďakujem.

[Honza]

Diky, clanek (i jeho preklad) jsou velmi zajimave.

V podstate to NAZORNE popisuje problem, se kterym se musi vyporadavat vice projektu.
U CPDN byly problemy stejneho charakteru - akorat horsi. Aplikace mnohem slozitejsi, mnohem rozsahlejsi, portovana ze 64-bit systemu na Linux a teprve pote na 32-bit Windows. A tak trochu slepou ulickou jsou nove MacOS X, u kterych nektere veci vypnout nejdou (jako ze jedou standardne s SSE ci pod.).
Resenim by mohlo byt u novych aplikaci rovnou prejit na 64-bit a SSE2 (na vsech platformach), ale ani to predem nezarucuje stejny vysledek i za pouziti "stejneho" kompilatoru a jeho parametru/knihoven.

[slavko.sk]

Ale ten vedecky prinos!!!