To SPi or not to SPi, question is now! :)

[drfedja]

SPi koristi arhaicne x87 instrukcije, kod nije vektorizovan i tesko da moze da se paralelizuje, jer je Gauss Legendre-ov algoritam zavistan od medjurezultata.
Elem, SPi ima IPC od samo 0.2-0.3 na K10. Na Core i7 mozda ima 0.5. Mahom se izvrsavaju x87 FP instrukcije i to ni manje ni vise nego kvadratni koren!!!
Kvadratni koren ima veliku latenciju i komplikovan je za izvrsavanje.
SPi koristi Gaus-Ležandrov metod za računanje broja Pi. U pitanju je numerička metoda koja se ponavlja iterativno.

Koga zanima objasnicu i ovo. Inicijalne vrednosti su:

a = 1 b = 1 / SqRt(2) t = 1/4 x = 1

Ovo se ponavlja u zavisnosti od toga koliko hocemo iteracija u SPi da napravimo:

y = a

a = (a+b) / 2

b = SqRt(b*y)

t = t - x * (y-a)^2

x = 2 * x

Pi aproksimiramo pomocu sledece formule:

Pi = ((a+b)^2) / (4*t)

Evo i C koda za ovo:

Spojler

#include<stdio.h>
#include<math.h>

int main(void)
{
  double a=1, b, t=0.25, x=1, y;
  int its, i;

  b = 1/sqrt(2);

  printf("\n Unesi broj iteracija: >");
  scanf("%u", &its);

  for(i=0; i<its; i++)
  {
    y = a;
    a = (a + b) / 2;
    b = sqrt(b * y);
    t = t - x*(y - a)*(y-a);
    x = 2*x;
  }
printf("\nPI = %u\n\n", ((a+b)*(a+b)/(4*t)));
return(0);
}

Ovo je u principu jezgro spi programa.

Koriscenje fsqrt x87 instrukcije je daleko sporije nego koriscenje skalarne SSE instrukcije za racunanje kvadratnog korena. Ipak, kompajleri standardno koriste x87 fsqrt pre nego SSE.

Ovo su vremena izvrsavanja i latencija instrukcija:

Compiler sqrt(x) /x87 FPU FSQRT 404.029ms 24ns 0.0000%

SSE intrinsic ssqrts 200.395ms 11.9ns 0.0000%

Carmack’s Magic Number rsqrt * x 72.682ms 4.33ns 0.0990%

SSE rsqrtss * x 20.495ms 1.22ns 0.0094%

SSE rsqrtss * x with one NR step 53.401ms 3.18ns 0.0000%

SSE rsqrtss * x with one NR step,
unrolled by four 48.701ms 2.90ns 0.0000%

Ovde se jasno vidi koliko je ogromna razlika (i do 10x) izmedju kvadratnog korenovanja skalarnim SSE operacijama i x87.
Odredjene operacije se izvrsavaju aproksimativno, pa postoji i odredjena greska u izracunavanju.

 

[animaN]

Sjajan tekst Fedjolino!

Pojasni ljudima boldovane pojmove ispod:

SPi koristi arhaicne x87 instrukcije, kod nije vektorizovan i tesko da moze da se paralelizuje, jer je Gauss Legendre-ov algoritam zavistan od medjurezultata.
Elem, SPi ima IPC od samo 0.2-0.3 na K10. Na Core i7 mozda ima 0.5. Mahom se izvrsavaju x87 FP instrukcije i to ni manje ni vise nego kvadratni koren!!!
Kvadratni koren ima veliku latenciju i komplikovan je za izvrsavanje.
SPi koristi Gaus-Ležandrov metod za računanje broja Pi. U pitanju je numerička metoda koja se ponavlja iterativno.

Da li moze pojashnjeje za ovo:

Ipak, kompajleri standardno koriste x87 fsqrt pre nego SSE.

Zashto?

 

[monteboy]

I pored X87 instrukcija i prednosti IPC'a Intel'a u odnosu na K10 moja procena je da nesto drugo ovdje igra vecu ulogu.

Sobzirom da govorimo o aplikaciji koja treba da izracuna Milion ili 32 Miliona decimala nakon zareza najbitnija stavka u ovoj celoj prici nije implementacija X87 instrukcija i njen IPC nego biblioteka za precizno racunanje koja se koristila kod superpi alatke.

Postoje razne biblioteke koje pomocu float point arithmetike danas omogucuju racunanje sa veoma velikim brojevima kao sto su MPMATH ili BigAL za Javu.
Kljuc performansi je upravu u toj biblioteci. Sobzirom da je neminovna cinjenica da u samom Algorithmu pristupa medjuvrednostima koje su spremljene u samom L2/L3 cachu procesora veoma bitnu ulogu ce imati velicina samog cache'a CPU'a dostupna jednom izvrsnom threadu

 

[BigJoe]

Feđa svaka čast, ovih dana si baš u edukativnom raspoloženju

 

[drfedja]

Sjajan tekst Fedjolino!

Pojasni ljudima boldovane pojmove ispod:



Da li moze pojashnjeje za ovo:



Zashto?

x87 je set instrukcija za rad sa razlomljenim iliti realnim brojevima. U kompjuterskoj
nauci se to strucno naziva Floating Point iliti FP, Float - plutajuca zapeta!
Plivajuci zarez je zato sto FPU - floating point unit radi sa realnim brojevima
tako sto pomera zarez. Npr. 3.14 je 0.314*10^1. Po IEEE754 formatu ovo se zapisuje kao U registru se ovo zapisuje binarno kao:

Eksponent se racuna binarno 1000000 = 128 - 127 = 1. Da bi dobili broj 2 racunamo ga kao
2^1. Dvojka se zapisuje u mantisi kao 0000000000000...00.
Broj 3 je 10000000000000...0000. Racuna se po formuli znak*(mantisa*2^exponent).
Prva cifra je znak. 0 je +, a 1 je -, po konvenciji.
Dalje, mantisa se racuna po stepenu dvojke, dakle 2^n. Svaka jedinica u frakciji predstavlja stepen dvojke uvecan za jedan sa leva na desno.
Tako nas broj Pi=3.14 zapisujemo ovako u fp registrima:

0 10000000 10010001111010111000011 (ovo je 32-bitna FP reprezentacija u IEEE754 formatu)

Ovo je tzv. single precision zapis, 32-bita. Postoje 64-bitni DP - Double Precision, kao i 128-bitni. Sa ovim zapisima moguce je preciznije aproksimirati razlomljen broj.

x87 rade samo sa jednom vrednoscu. Dakle instrukcija moze da izracuna samo jedan broj.
Kod SSE instrukcija u vektor od po 4 broja se smestaju npr. 4 32-bitna broja, nad kojima se vrsi neka operacija, npr. mnozenje, sabiranje, deljenje, mnozenje skalarom, t.j. jednim brojem itd...
Skalarna SSE instrukcija radi isto sto i x87 sa razlikom sto ne koristi stek registar za izracunavanje, nego ima svoje registre. Stek je inace struktura podataka, takva da ono sto je poslednje stavljeno prvo se skida. Za poredjenje, stek je npr. stap na kojem drzite DVD-ove. Da bi dosli do donjeg, morate sve da skinete. Tako je i kod x87 FPU-a. Da bi pristupio podatku koji je na dnu steka, mora da skine sve.
x87 poseduje 8 Stack registara sirine 80-bita maksimalno. Ovo znaci da on moze da operise sa maksimalno sa 64-bitnim IEEE754 vrednostima. Po matorom IEEE754-1985 standardu u 80-bitni registar moze da se smesti 64-bitna mantisa, 15-bitni eksponent i 1-bitni znak.
Ovo se moze koristiti prilikom rada sa 32-bitnim ili 64-bitnim varijablama koje se mogu ucitati u FPU stack registar, nakon cega se one konvertuju u 80-bitne da bi se kalkulacije obavile u 80-bitnoj preciznosti. Posle kalkulacije, vrednosti se "zaokruzuju" na 32 ili 64-bitne. Pogresna izracunavanje se mogu izbeci koriscenjem kompajler switcha kojim se izracunavanja vrse iskljucivo u 80-bitnoj preciznosti.

SSE instrukcije nasuprot x87 koriste 16 registara. SSE je SIMD - single instruction multiple data koji radi po ovom principu:

Zbog mogucnosti smestanja po 4 32-bitne vrednosti sa kojom je moguce vrsiti operacije mnozenja, sabiranja, deljenja, skalarnog mnozenja itd... koriscenje SIMD instrukcija ima visestruke prednosti. Npr, u multimedijalnoj primeni jedan piksel nosi informacije o boji - R, G i B komponente, koje su 3 osmobitne vrednosti. Kao cetvrtu vrednost moguce je cuvati jos neku informaciju o tom pikselu. Npr alfa faktor itd...
SIMD, odnosno SSE je zgodan za matricne proracune. Matrica je skup vektora. Vektor je niz nekih vrednosti. Npr, 4 32-bitna broja poredjana jedna za drugim su vektor. Nad tim vektorom moguce je izvrsiti samo 1 instrukciju. Istu operaciju je moguce uraditi i pomocu x87 FP instrukcija, ali za to ce vam biti potrebne 4 32-bitne x87 FP instrukcije, koje obicno imaju vecu latenciju, t.j. vreme izvrsavanja od SSE SIMD operacija.

Kompajleri najcesce koriste x87 umesto SSE iz razloga kompatibilnosti. Pored toga, x87 se koristi cesto iz razloga jer sami kompajleri nisu optimalno napravljeni za takve stvari.
Cesto nije moguce iskoristiti optimalno SSE instrukcije ukoliko nije sam kod vektorizovan, sto znaci da nisu korisceni nizovi, nego pojedinacne varijable. Npr, u gorepomenutom Gaus Ležendreoovom algoritmu nema vektorizacije, pa je nije moguće upotrebiti vektorske SSE instrukcije. Moguće je koristiti skalarne SSE za izračunavanje kvadratnog korena, ali tu je opet problem kompajlera koji pitanje kako to iskoristi.

 

[drfedja]

I pored X87 instrukcija i prednosti IPC'a Intel'a u odnosu na K10 moja procena je da nesto drugo ovdje igra vecu ulogu.

Ako gledamo implementaciju x87 instrukcija, tu je K10 u prednosti. Latencija SQRT je ista ili manja nego na i7.

Sobzirom da govorimo o aplikaciji koja treba da izracuna Milion ili 32 Miliona decimala nakon zareza najbitnija stavka u ovoj celoj prici nije implementacija X87 instrukcija i njen IPC nego biblioteka za precizno racunanje koja se koristila kod superpi alatke.

IPC je nizak jer postoji ono sto zovemo "stall", odnosno usko grlo.
Biblioteka koja se koristila očigledno nije baš najbolje optimizovana. Probaj sa Mathlabom da izračunaš Pi na milion decimala pa ćeš videti koliko je puta brže.

Postoje razne biblioteke koje pomocu float point arithmetike danas omogucuju racunanje sa veoma velikim brojevima kao sto su MPMATH ili BigAL za Javu.
Kljuc performansi je upravu u toj biblioteci. Sobzirom da je neminovna cinjenica da u samom Algorithmu pristupa medjuvrednostima koje su spremljene u samom L2/L3 cachu procesora veoma bitnu ulogu ce imati velicina samog cache'a CPU'a dostupna jednom izvrsnom threadu

Veličina keša jeste bitna, ali nije presudna. Bitan je hit rate keša i njegova latencija. Za nizak IPC je kriv sam algoritam, kao i veliki dataset koji se nalazi van procesorskih registara.

 

[d0minat0r]

MOj brat Fedja

 

[drfedja]

MOj brat Fedja

Mali, knjigu u sake, pa pitaj sta nije jasno da razvijemo disqsiju!

 

[monteboy]

fedja , zadatak za tebe !
Disassembliraj super_pi_mod.exe i pronadji FSQRT

Jednostavan primer koji si naveo gore sa nekoliko iteracija ogranicen fizickom sirinom registara samog CPU'a nije adekvatan pokazivac zbog cega upravo AMD u SPI1M odnosno Spi32M ima znatno losije rezultate.
Voljan sam da napravimo detaljnu analizu isprobamo neke druge algoritme ili sami odradimo spi proracun na osnovu neke optimizovane biblioteke
Programirati sad preciznu float point arithmetiku je opsiran posao ali nace se neka adekvatna biblioteka.

 

[Luka]

Veoma opsirno i precizno objasnjenje Fedja!

 

[drfedja]

fedja , zadatak za tebe !
Disassembliraj super_pi_mod.exe i pronadji FSQRT

Probacu, pa javljam sta sam nasao.

Jednostavan primer koji si naveo gore sa nekoliko iteracija ogranicen fizickom sirinom registara samog CPU'a nije adekvatan pokazivac zbog cega upravo AMD u SPI1M odnosno Spi32M ima znatno losije rezultate.

Slazem se. Ali ovim gore nisam hteo da objasnim to, nego da pokazem kako radi SPi, odnosno na kom principu radi algoritam za racunanje broja Pi u ovom programu.

Voljan sam da napravimo detaljnu analizu isprobamo neke druge algoritme ili sami odradimo spi proracun na osnovu neke optimizovane biblioteke
Programirati sad preciznu float point arithmetiku je opsiran posao ali nace se neka adekvatna biblioteka.

Daj neki predlog vezan za izbor biblioteke za rad sa velikim brojevima. Ono kako radi SPi je sporo.

 

[monteboy]

Probacu, pa javljam sta sam nasao.

Slazem se. Ali ovim gore nisam hteo da objasnim to, nego da pokazem kako radi SPi, odnosno na kom principu radi algoritam za racunanje broja Pi u ovom programu.


Daj neki predlog vezan za izbor biblioteke za rad sa velikim brojevima. Ono kako radi SPi je sporo.

http://www.apfloat.org/apfloat/
obrati paznju na podeljeni sourcecode po platformi i arhitekturi procesora

Ako stignem za vikend mozemo podici jedan mali test projekat.

Mozda jos efikasnija

http://www.ginac.de/CLN/

 

[drfedja]

Evo jezgra SPi x87 FP komandi:

Ne mogu da tvrdim sta se racuna u registrima, ali sled operacija i ucitavanje u registre lici mnogo na Gaus Lezendrov algoritam.
Izgleda da SPi racuna u delovima i parcice smesta u fajl. Obrati paznju na asm kod.

 

[monteboy]

Evo jezgra SPi x87 FP komandi:

Ne mogu da tvrdim sta se racuna u registrima, ali sled operacija i ucitavanje u registre lici mnogo na Gaus Lezendrov algoritam.
Izgleda da SPi racuna u delovima i parcice smesta u fajl. Obrati paznju na asm kod.

Ne stari kad trazis commandu putem OllyDbg onda ces pronaci prvu kombinaciju Opcode'a za operaciju FSQRT a ta kombinacija moze da bude i neka adresa a ne instruukcija namenjana FPU'u kao sto je i ovdje slucaj.

Zapravo na adresi gdje si pronasao je ustvari JE skok...

Najbolje podji na entry point Exe Modula i trazi forward i backward FSQRT videces da je nema.

asm superpi_mod_1.5.exe

 

[micri]

Bravo Fedja, bravo...

 

[drfedja]

Ne stari kad trazis commandu putem OllyDbg onda ces pronaci prvu kombinaciju Opcode'a za operaciju FSQRT a ta kombinacija moze da bude i neka adresa a ne instruukcija namenjana FPU'u kao sto je i ovdje slucaj.

Zapravo na adresi gdje si pronasao je ustvari JE skok...

Koliko vidim tu nema skoka, nikakvog. Taj deo koda koji sam izvukao iz debuggera je deo koji se izvrsava u toku rada SPi. E sad koliko vidim FSQRT nema nikakvu adresu, pa pretpostavljam da radi sa vrednoscu koja mu je u stek registru u FPU.

Najbolje podji na entry point Exe Modula i trazi forward i backward FSQRT videces da je nema.

asm superpi_mod_1.5.exe

Na Entry Point-u se ne nalazi taj deo koda koji vrti iteracije u SPi vec neke reference na sistemske biblioteke tipa GDI32 itd...

 

[monteboy]

Upravu si tokom debuga kad se malo bolje pogleda sourcecode , FSQRT zaista biva pozvan ali kao sto sam i predpostavio nema direktnu vezu sa izracunavanjem algoritma za sledecu decimalu.

Adresa koja je interesantna i gdje je spremljen OPCODE za FSQRT je 420CB5 ista biva tokom debuginga u superpi'u za bilo koji izbor broja decimala nebitno birao 16 hiljada ili 32 miliona pozvana samo cetiri puta
dovoljno ti je da stavis breakpoint na istu instrukciju i videces tokom inicialnog lupa se ista poziva cetiri puta a ksnije nijedanput vise.

Tokom debuginga dok radi proracun vidno je da su kljucne funkcije na sledecim adresama jel se stalno ponavljaju

- 420020
- 420C60
- 41FF6C
- 420024

 

[drfedja]

I ti si u pravu sto se tice FSQRT. Poziva se vrlo retko. Analizirao sam stack frejm u kome se izvrsava loop sa odredjenim nizom instrukcija.
U pitanju su pozivi funkcija iz kojih se vrse proracuni u svakoj iteraciji. Svaka sledeca iteracija iznova poziva funkcije, koje se nalaze na adresama koje si postovao.
Uglavnom su u pitanju FADD i FMUL x87 instrukcije, kao i operacije sa stack registrom FPU-a. Bilo kako bilo, u pitanju je SPi 1.5 mod, koji bi ako se ne varam trebalo da bude SSE optimizovan, ali statisticki gledano, veci deo vremena se trosi na x87 aritmeticke i stack operacije.

Sibnucu malo kasnije niz instrukcija koje se najcesce ponavljaju, pa mozemo da proanaliziramo kod.

 

[animaN]

Sibnucu malo kasnije niz instrukcija koje se najcesce ponavljaju, pa mozemo da proanaliziramo kod.

A mozda na kraju i uspemo da optimizujemo za bolje vreme

 

[drfedja]

Tesko, osim ako ne izmenimo instrukcije koje se koriste, sto bi prouzrokovalo pucanje programa jer se rad sa stack registrima i SSE flat registrima bitno razlikuje.
Koriscenje stack registra degradira performanse. Ono zbog cega je x87 i dalje veoma zastupljen u velikom broju aplikacija je problem sto je veliki broj biblioteka optimizovan za stari x87 set instrukcija. Optimizacije su vrsene na asemblerskom nivou, pa bi za reoptimizaciju za upotrebu flat registara i SIMD instrukcija trebalo mnogo vremena. Ipak, kako vreme prolazi sve vise aplikacija koristi novije optimizovanije biblioteke koje su pisane za SIMD, t.j. SSE.

Poenta price je da utvrdimo zbog cega tacno na Core arhitekturi SPi radi brze nego na K10 i da probamo da zakljucimo da li ce SPi raditi brze na BD.

Na kraju krajeva, kao nuspojava moze da se desi da sami napravimo svoj AxePi benchmark.

 

[monteboy]

superpi SSE varijanta vec postoji. Cak i SSE2 i SSE3...
Testirao sam SSE3 varijantu u odnosu na ovu obicnu i razlika je u 32M nekih 20 sekundi u korist SSE3...

Nazalost na XS odnosno na hwbot jos uvek je relevantna stara FPU varijanta oznaka mod u imenu se odnosi na modifikaciju koja je svojevremeno odrdjena da bi se izbegla originalna instrukcija (nemogu da se sad setim tacno koja je bila) i koja je usporavala dosta tadasnje Pentium procesore.

 

[CooLa]

Je l' ima negde ceo source SPi-ja da se skine?

 

[drfedja]

A mozda na kraju i uspemo da optimizujemo za bolje vreme

I ako bi to uradili checksum bi nam bio drugaciji, pa nam rezove ne bi priznali.

Jedino da hakujemo checksum....

superpi SSE varijanta vec postoji. Cak i SSE2 i SSE3...
Testirao sam SSE3 varijantu u odnosu na ovu obicnu i razlika je u 32M nekih 20 sekundi u korist SSE3...

Nazalost na XS odnosno na hwbot jos uvek je relevantna stara FPU varijanta oznaka mod u imenu se odnosi na modifikaciju koja je svojevremeno odrdjena da bi se izbegla originalna instrukcija (nemogu da se sad setim tacno koja je bila) i koja je usporavala dosta tadasnje Pentium procesore.

Pa mogli bi da uzmu kao relevantnu SSE verziju. T.j. onda vise ne bi bila relevantna poredjenja sa K7 Athlonima (pre AXP) koji nisu imali SSE.

 

[drfedja]

Je l' ima negde ceo source SPi-ja da se skine?

Koliko znam, nema.