[es] - Hyper-Threading Vulnerability i alternativna vidjenja

Ivan Dimkovic

Administrator
Član broj: 13
Poruke: 16752
*.dip.t-dialin.net.

+7204 Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 17:31 - pre 242 meseci}

Citat:

Stvari koje sam slusao i polozio na postdiplomskim studijama (koje nijesam zavrsio) jos 90-e, a ti se vidi koja je danas godina. Teorija za takve stvari poodavno postoji, prakticne implementacije nema, a da je ja znam. Ovaj "autovectorizer" iz GCC je prvi iskorak u prakticne implementacije iz tih domena, ja sam pricao o teoretskom maksimumu ne cipova sa vise procesorskih jezgara, vec Altivec kao jedinice za vektorsku aritmetiku.

Ispravi me ako gresim, Apatrid - ali moderni Intel kompajleri (> 6, danas 8.1) imaju i vektorizaciju preko SSE registara, i loop unrolling i optimizaciju pipeline izvrsavanja, kao i baznu hyperthreading optimizaciju - i jos podosta prilicno modernih tehnologija optimizacije.

Tako da GCC nije izmislio nikakvu toplu vodu, a sve to postoji u komercijalnim kompajlerima za takve sisteme i arhitekture (tipa Alpha) jos ohoho odavno.

Ono o cemu je ovde rec, je da kompajler ne moze (i to uz pomoc bilo kakve teorije) da bude uporediv sa dizajnom (ne pricamo o implementaciji, pa je asemblersko poredjenje neprimereno) aplikacije gde se vodilo racuna o ciljnoj arhitekturi a u pogledu optimizacije programskih modula i niti.

To ni jedan kompajler ne moze da uradi bez asistencije coveka, i to veceg dela posla na covekovoj strani - iz prostog razloga sto kompajler ne moze da nasluti izvrsnu logiku ili redosled racunanja nekih parametara u vise niti - to ne ide, niti je iko normalan radio na tako necemu (mozda za neki bogus Ph.D)

Evo ti prost primer - imas dupli DSP / dual corei, recimo, video enkoder - zavisnost frejmova jedan od drugog (predikcije), problem zavisnosti jednog algoritamskog bloka od drugog i sl... jednostavno cine kompajler nemocnim u optimizaciji osim povrsnih optimizacija.

Ako dobar projektant onda preuredi algoritam tako da a-priori bude poznato da ima vise jezgara i podele se zadaci i sinhronizuje posao izmedju jezgara - takav proizvod ce trcati mnogo brze nego puki pokusaj kompajlera da grubo nesto opimizuje.

Naravno, ima softverskih aplikacija koje pukim forkovanjem mogu da budu brze, tipa HTTP serveri, ali i tu moze da se ucini dosta boljim dizajnom koji kompajler ne moze da nasluti... e sad, pitanje je da li tebi treba takav boost u performansama, ili ces se samo osloniti na "kupi jaci hardver" ... to zavisi od tvoje poslovne politike.

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey

Odgovor na temu

Apatrid
Ottawa, ON

Član broj: 34944
Poruke: 471
*.freescale.com.

Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 17:52 - pre 242 meseci}

Citat:

Ivan Dimkovic: Ispravi me ako gresim, Apatrid - ali moderni Intel kompajleri (> 6, danas 8.1) imaju i vektorizaciju preko SSE registara, i loop unrolling i optimizaciju pipeline izvrsavanja, kao i baznu hyperthreading optimizaciju - i jos podosta prilicno modernih tehnologija optimizacije.

"loop unrolling" je i tehnika za optimizaciju, ali i tehnika za elementarnu paralelizaciju.

Ne znam za vektorizaciju u Intel kompajlerima, nijesam pratio razvoj njihovog kompajlera. Za nase procesore nema, Ivane. Postoji ekipa koja je zaduzena za Altivec i prati te domene non-stop, ljudi decidirano rekli da je samo jedan pokusaj implementacije vectorizer-a bio i da nije doslo do "market traction".

Inace, ova primjedba da kompajler ne moze da prepozna paralelizam na visem nivou je OK, ja nijesam rekao da ce upotreba "fork" (ili ekvivalenata) nestati, niti da ce nestati potreba za dobrim programerom :).

Realnost je da, sto se "dobro napisanih aplikacija" tice, broj onih koje nijesu "dobro" sa tog aspekta napisane, (ali jos uvijek rade koristan posao) veci od onih drugih, koje generisu dovoljno threads da iskoriste sistem maltene bilo kog stepena paralelnosti.

Odgovor na temu

Apatrid
Ottawa, ON

Član broj: 34944
Poruke: 471
*.freescale.com.

Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 18:06 - pre 242 meseci}

Citat:

caboom: ovo nema veze sa asemblerskim kodom Apatrid, ovo ima veze sa >> arhitekturom << aplikacije - kompajler ne moze da ti optimizuje losu arhitekturu.

Ja sam primjer sa asemblerom naveo zbog razlike u utrosenom trudu, te prakticnosti primjene tehnologije. Slusaj, "dobro napisana aplikacija" ce postici jedan nivo paralelizma, recimo, grubog primjera radi, 13 paralelnih threads u bilo kom trenutku. Ako kompajler izgenerise jos 4-5, ukupni efekt je jos bolji, zar ne?

Kompajler ne moze da mi optimizuje arhitekturu cijelog sistema i odradi bolji posao od vjestog covjeka (otud analogija sa asemblerom, nema kompajlera koji moze da se nosi sa rucno optimizovanim kodom), ne moze da zamijeni vjestog programera, ali kompajler moze da "iscijedi suvu drenovinu" i da bilo kojoj lose napisanoj aplikaciji da "boost", ma kako malen bio.

Odgovor na temu

caboom
Igor Bogicevic
bgd

Član broj: 255
Poruke: 1503
*.montgomery.com.

ICQ: 60630914

+1 Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 18:33 - pre 242 meseci}

Citat:

Apatrid: Ja sam primjer sa asemblerom naveo zbog razlike u utrosenom trudu, te prakticnosti primjene tehnologije. Slusaj, "dobro napisana aplikacija" ce postici jedan nivo paralelizma, recimo, grubog primjera radi, 13 paralelnih threads u bilo kom trenutku. Ako kompajler izgenerise jos 4-5, ukupni efekt je jos bolji, zar ne?

apsolutno ne, ovo je veoma opasna i manipulativna implikacija. naime, suvo razbacivanje samim thread-ovima moze rezultovati time da ti aplikacija trosi previse resursa na sam context switching. stvar kao sto je balans u sinhronizaciji je u ne-trivijalnim slucajevima cesto veoma zeznuta i kompajler moze da ti iscedi samo trivijalno malo performansi u slucaju dobro napisanih aplikacija. sto se tice lose napisanih aplikacija, one su naprosto to - lose napisane aplikacije.
stvar je u tome da ti naprosto gcc sa threading optimizacijama nece genrisati SMP ready aplikaciju iz mnogo razloga.

OV SM
LA PK

Odgovor na temu

Apatrid
Ottawa, ON

Član broj: 34944
Poruke: 471
*.freescale.com.

Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 18:56 - pre 242 meseci}

To sto ti pricas, caboom, ja ne osporavam. Da, sve je to tacno kad dizajniras sistem gdje ti mozes/moras stvari da drzis pod kontrolom.

Stvarnost je da procesori ne rade samo u embeded svijetu, gdje je, ama do zadnje, svaka linija koda pod tvojom kontrolom, vec i u workstation svijetu, "procesorima opste namjene".

Kolicina niti koja ce bit aktivna u jednom trenutku, zavisi od dinamike koju definise korisnik. Ti jednostavno ne mozes da izbacis iz igre mogucnost da ce doci do overloading-a paralelizma, jer covjek moze da pokrene N aplikacija koje ce taj, pazljivo optimizovani sistem za maksimalno iskoriscenje paralelizma da razbiju.

Problemi su ovakve prirode: imas procesor sa 64 procesorska jezgra. Kako dizajniras svoju aplikaciju, da ima paralelizam 16 (16 niti koje otprilike isto rade), 32, ili 64? Sve je veoma jednostavno ako je tvoja aplikacija jedina koja se izvrsava. Na masini opste namjene, sa dovoljnim brojem procesorskih jezgara, "pokreni niti koliko mozes (nema smisla ic' preko 64 u ovom mom primjeru) da pronadjes i staraj se da rad medju nitima podijelis da bude otprilike isti, pusti scheduler da ispegla ukupne performanse sistema dijeleci procesor izmedju niti" i nije tako hrdjava logika.

Nakarikati 64 paralelne niti u algoritmima koji su "flat" je mozda moguce, ali nije bas toliko trivijalno da kazes "svaki programer to moze da oposli". Kompajler ce pronaci paralelizam u svakoj petlji (petlji se vala odreci neces, ipak), iskoristiti ga AKO TO IMA SMISLA, i time pomoci cak i losoj aplikaciji.

Kompajler moze da prepozna kad nema smisla vijati paralelizam (e je skuplja dara nego maslo), jer se takve situacije daju precizno matematicki opisati.

Odgovor na temu

Sundance

Član broj: 7510
Poruke: 2559
*.sava.sczg.hr.

Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 19:07 - pre 242 meseci}

Apatrid mislim da si vrlo u krivu :)

Kompajler ne zna ništa o sinkronizacijskim primitivima koje OS na odredišnoj platformi implementira. Šta kompajler zna, što je semafor, mutex, spinlock, šta on zna koji točno API uzrokuje context-switch, koji uzrokuje wait operaciju (i na koliko dugo?) -> to je sve uloga OS-a. Recimo na win Sleep(0) je interno implementiran kao SwitchToThread() -> kako će to kompajler znati? :)

A što se kompajlera tiče, recimo na NT, CRITICAL_SECTION je struktura kao i svaka druga, nema u njoj ništa magično :) Nadalje svaki objekt (proces, job, nit, semafor, datoteka, timer, događaj...na NT je to svaki objekt koji ima embeddan tzv. dispatcher objekt sa DISPATCHER_HEADER strukturom, a nove tipove objekata može stvarati i korisnički program, tako da nema nikakve šanse da kompajler "pogodi" koja varijabla može, a koja ne može biti korištena za sinkronizaciju, te i na koji način, svaki od gore navedenih objekata se "okida" na drugi način, proces kad mu se terminiraju sve niti, timer kad mu istekne vrijeme...) nad kojim se može implementirati sinkronizacijski ili notifikacijski događaj, nad njom može biti imlementirana wait operacija u raznim kompleksnim scenarijima. Ako poziva neki API koji radi I/O + neka completion rutina, stvari postaju još zabavnije :)

Ako pretpostavimo da nekim čudo sve to zna, recimo da kompajler može u stadiju semantičke analize nad svaki objekt attachati odgovarajući dependecy tree, da može algoritamski extrahirati najbolji mogući scenarij (u smislu paralelizacije) odnosa sa svim drugim objektima, da poznaje sve detalje odredišne arhitekture, opet u igru dolaze neke lude pikanterije OS-a kao što su quantum pojedine niti, broj pojedinih niti u odnosu na broj logičkih procesora, predikcija overheada poziva sistemskih fja, lag između niti koji se sinkroniziraju (proporcionalan broj logičkih CPU-ova), potencijalni runtime priority boost koji je programski implementiran od strane programera ili heuristikama OS-a, komunikacija samog thread primitiva sa OS-om i interakcija sa njim (recimo APC-ovi se izvršavaju u kontekstu pojedine niti, pošto su oni po definiciji asinkroni (jerbo se tako i zovu - Asynchrounous Procedure Calls :) nema te logike po kojoj bi kompajler mogao napraviti njihovu predikciju), te ne daj bože da niti korise neki oblik IPC-a jerbo je za kompajler sve izvan trenutne aplikacije jedna velika crna kutija....

Uglavnom, mislim da je extrahiranje thread-level paralelizma iz koda SF, i da je moguć (ako je uopće moguć), samo u scenarijima typesefe jezika koje se izvode pod virtualnom mašinom, tj. kad JIT-er zna i broj logičkih CPU-ova i detalje OS-a).

Uspoređivati instruction-level paralelizam kroz multistage pipeline sa ovakvim nečim jest totalno nerealno IMHO. To su dvije totalno različite klase problema. Nit po konceptu i jest primarna apstrakcija CPU-a sa stajališta programa, ali ovaki scenariji kad bi kompajler generirao nove niti kako mu šune bi bili mogući tek kad CPU bude imao 100 jezgara, pa krivi pogodak baš i neće puno značit....

Mislim da teka kad 90% programera bude imalo multithreaded programiranje u malom prstu (dakle nikad), kompajleri će kroz neke odgovarajuće metodologije programiranja omogućiti da im se da hint koji dio koda na koji način ovisi o kojem dijelu koda.

Sve do tada, VTune u ruke i deri :)

Odgovor na temu

caboom
Igor Bogicevic
bgd

Član broj: 255
Poruke: 1503
*.montgomery.com.

ICQ: 60630914

+1 Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 19:11 - pre 242 meseci}

apatrid, nalazenje paralelizma u svakoj petlji moze da uzrokuje takodje i ozbiljne probleme sa bas onim sto sam naveo - context switching-om i opet... takva optimizacija ce ti doneti znacajnije performanse u samo nekim slucajevima. nemoguce je napraviti potpuno flat aplikaciju, ali je moguce napraviti aplikaciju koja se dobro ili lose skalira na takvim arhitekturama.
ono sto mi se ne dopada u ovom rezonu je bas taj klasicni Linux "nabudzi i pomoli se" pristup gde ocekujes da ti kompajler magicno resi problem sa lose napisanim aplikacijama. generalno, osecam veliki antagonizam prema takvim resenjima i mislim da su primenjiva samo do odr. granice i da na kraju uvek vode do mnogo veceg man/effort troska, osim u veoma trivijalnim slucajevima.

OV SM
LA PK

Odgovor na temu

caboom
Igor Bogicevic
bgd

Član broj: 255
Poruke: 1503
*.montgomery.com.

ICQ: 60630914

+1 Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 19:16 - pre 242 meseci}

Citat:

Sundance:
Ako pretpostavimo da nekim čudo sve to zna, recimo da kompajler može u stadiju semantičke analize nad svaki objekt attachati odgovarajući dependecy tree, da može algoritamski extrahirati najbolji mogući scenarij (u smislu paralelizacije) odnosa sa svim drugim objektima, da poznaje sve detalje odredišne arhitekture...

onog dana kada se to bude desilo, verovatno cemo ostati bez posla :)

OV SM
LA PK

Odgovor na temu

Sundance

Član broj: 7510
Poruke: 2559
*.sava.sczg.hr.

Profil

Re: Hyper-Threading Vulnerability i alternativna vidjenja

^{01.06.2005. u 19:41 - pre 242 meseci}

Citat:

Apatrid:Kompajler ce pronaci paralelizam u svakoj petlji (petlji se vala odreci neces, ipak), iskoristiti ga AKO TO IMA SMISLA, i time pomoci cak i losoj aplikaciji.

To je ILP (Instruction Level Paralelism), kad sve te instrukcije izvršavaju pod _istim_ kontekstom (istim thread-om). To _nije_ multithreaded paradigma. Jedan CPU ima u _jednom_ trenutku _jedan_ execution flow.

Citat:

Kompajler moze da prepozna kad nema smisla vijati paralelizam (e je skuplja dara nego maslo), jer se takve situacije daju precizno matematicki opisati.

Može za 1 execution flow te extrahirati međusobno neovisne instrukcije koje može unutar pipeline-a izvesti. Koliko ja vidim ti si spominjao da kompjaler _generira_ nove niti, kako bi ih optimizirao za multicore scenarije.

Sjećam se negdje sam pročitao da su kompajleri ograničeni na maximalno 4-way ILP (barem za Intel). Tako da ni tu nije baš najbolje :) Najbliže nekom ludom iznuđivanju kontekstualno-neovisnog paralelizma iz koda bi bilo spekulativno izvođenje niti kao npr. na MAJC, kad se stvara nova spekulativna nit izvođenja koja izvodi buduće instrukcije u sadašnjosti, te koje se spajaju kad prva nit završi čekanje. Ali opet takvo nešto je na razini CPU-a, a ne kompajlera...

Što se tiče samog ILP, na IA-32 arhitekturama sa jako _ograničenim_ skupom registara, ne možeš baš puno širiti code stream. Intelovi procesori su uglavnom bazirani na uskoj jezgri, serijski posloženim funkcionalnim jedinicama koje jako brzo izvršavaju kod. To suxa sa bilo kojeg stanovišta paralelizacije.

PS: Vjerojatno sam u svemu ovome rekao neke gluposti pa se unaprijed ispričavam :)

Odgovor na temu