Sziasztok!
Egy kis digital signal processinghez kapcsolodo optimalizacios kerdes. Van egy effele programtoredek, amiben egesz aritmetikaval, mindenfele lookup-tablak hasznalataval es bufferek kezelesevel egy multiply-and-accumulate jellegu belso ciklusmag futkoraszik:
for ( i=0; i<nsample; i++ )
{ [...]
int si,sq;
si=sq=0;
for ( k=0,b_offset=2*i,sip=sip0; k<nnode; k++,b_offset+=2*nsample,sip++ )
{ int ci,cq,rot_cos,rot_sin;
ci=2*(int)sib->sib_buffer[b_offset+0]-255; /* 2*(k*nsample+i)+0 */
cq=2*(int)sib->sib_buffer[b_offset+1]-255; /* 2*(k*nsample+i)+1 */
rot_cos=sif->sif_phase_shift_array[sip->sip_offset].re;
rot_sin=sif->sif_phase_shift_array[sip->sip_offset].im;
si += +rot_cos*ci-rot_sin*cq;
sq += +rot_sin*ci+rot_cos*cq;
sip->sip_offset = (sip->sip_offset+sip->sip_step)%sif->sif_phase_shift_length;
}
sif_out_buffer[0] = (si+255*PHASE_SHIFT_AMPLITUDE)/(2*PHASE_SHIFT_AMPLITUDE);
sif_out_buffer[1] = (sq+255*PHASE_SHIFT_AMPLITUDE)/(2*PHASE_SHIFT_AMPLITUDE);
sif_out_buffer += 2;
[...]
}
Itt a belso ciklusmag az erdekes, az `nnode` erteke a gyakoratban 8 lesz. A kerdes az az hogy vannak-e olyan SIMD utasitasok x86_64 alatt, amivel ez a ciklusmag jol kioptimalizalhato es/vagy a forditot ra tudjuk venni hogy hasznalja? Most nezem a objdump/disasm-ot, gcc-10.2.1 alatt, -O3-as optimalizacioval, es kb olyan mintha en irtam volna minimalis assembly rutinnal (oke, a LEA-s trukkok erdekesek). Ugy latom elsore hogy mar SSE2 alatt vannak pl 4x32 bites integer regiszterek, amikkel mar egy kis unroll felhasznalasaval eleg jol lehetne optimalizalni a fenti ciklust... de meg az is lehet hogy a ket ciklus felcserelesevel (nnode fut kivul, az nsamples pedig belul) megjobban kihasznalhatoak bizonyos SIMD/MAC utasitasok.
Valamelyik internetekben azt olvastam hogy a forditok mar eleg okosak hogy felismerjek hogyha SIMD-del jol kioptimalizalhatoak az effele ciklusok, de ottan a peldak valos arithmetikara vannak kihegyezve. Itt meg integer aritmetika van.... opcionalisan annyi lehet a konnyites hogy a rot_cos, rot_sin ertekek valojaban i16-osak es a ci/cq ertekek pedig i8-asok, szoval akar valami PMADDWD is lehetne.
Alapjaraton a fenti implementacio sem rossz a gyakorlatban, de hamar annyira nagy az arconporges az effele utasitaskeszletek irant, akkor kezdjuk el ertelmesen is hasznalni ;)
Hozzászólások
Clang-ot nézted? https://llvm.org/docs/Vectorizers.html
Nem, egyelore csak gcc-t neztem. De koszi, ezek erdekesek, megnezem!
Kézzel ne optimalizálj ilyet, mert a kódod kötve lesz x86-hoz, annak is egy konkrét utasításkiegészítést támogató variánsához. Lehet ezt nem érzed bajnak, de később visszaüthet. Clang sem muszáj ehhez, persze jó az is, de a gcc-re is rá lehet bízni, de az -O3 önmagában nem elég, kapcsold be az march=native vagy march=konkrét_géparchitektúra kapcsolókat (utóbbi nálam pl. Zen2-es Ryzenen: -march=znver2), akkor használja az extra SIMD utasításkészleteket.
“A computer is like air conditioning – it becomes useless when you open Windows.” (Linus Torvalds)
Ja, nem, fordito es/vagy architektura-specifikus dolgokat nem akarok bennehagyni. Inkabb forditva: jol ismerni kellene az architekturak altal tamogatott dolgokat ahhoz hogy olyan C kodot lehessen irni amit utana a fordito (megfelelo noszogatassal) ki tud optimalizalni jol. Ld amit irtam hogy pl a kulso meg a belso ciklus felcserelese meg ilyesmi, attol fuggoen hogy a SIMD/MAC utasitasok mifele inputra lesznek hatekonyak. Ilyesmik.
Mondjuk az is igaz hogy ez itten kvazi-cel-hardverre meno cel-szoftver, szoval ha kicsit kevesbe hordozhato (es/vagy a hordozhato valtozat nem optimalis) az nem tragedia. A mostani architektura [Intel(R) Core(TM) i3-10105T CPU @ 3.00GHz] ezeket tudja:
Ebbol elsore az SSE4* es AVX2 lehet az erdekes, de talan mas is van itten amit nem ismerek (fel).
A magas szintű nyelvek azért vannak, hogy téged szolgáljon ki a fordító, nem fordítva. Arra törekedj, hogy a kódod normálisan legyen megírva, ne alapuljon elavult szternderden, dialektuson, ne legyen benne felesleges spagettikódos gányolás, a többit a fordító intézi. Ha a gcc vagy clang nem dob túl sok warningot, akkor valószínű elég jó a kód. A procid az -march=icelake-client profilba tartozik (Comet Lake proci, de ahhoz nincs külön profil). Az -march=native kapcsolóval detektálja a profilt (írja is, hogy melyik választotta, ha verbose módban használod), és onnan tudni fogja, hogy SSE4, AVX2 is elérhető, elvileg még az AVX512-őt is használni fogja.
Persze a fordítók trükkös szerkezetek, főleg a gcc, gyakran nem is mindig az -O3-as optimalizóciós szint adja a legjobb eredményt, hanem néha az -O2, vagy akár az -Os is gyorsíthat, ezt le kell mérni konkrétan. De még olyan is előfordul, mikor valami generic profil, pl. -march=x86_64 vagy x86_64-v4 jobb eredményt ad, mint a konkrét procihoz tartozó speciális profil, néhány phoronixos tesztben még ilyet is láttam.
Persze, csinálhatod kézzel is, gondolom az Inteltől letölthető a procid termékoldaláról egy x86-os ASM manual, amiben a modern utasítások is le vannak írva, hogy mi hány órajelciklus, mire való, milyen regiszterekkel, stb. dolgozik, milyen procik tudják, és akár ASM-ben is megírhatod, de nem véletlen, hogy senki nem járja ezt az utat. Ma már csak néhány drivernél, encodernél használnak ASM-et, és ott is csak a sebességkritikus részeknél. Ma már lassan az is luxus optimalizáció, hogy rendes natív binárisra fordított nyelven van írva, és low levelnek számító C-ben, és nem interpretált nyelv (JS, Python, stb.), és 10 kiló hülye extra lib van erőltetve. Tényleg nevetséges, hogy már ezzel a sok soydev elé kerülsz, akik alapból virtualizáltan kontérizált, Electron Shit Frameworkökben gányolnak.
“A computer is like air conditioning – it becomes useless when you open Windows.” (Linus Torvalds)
Szerintem azért nem fog tudni ezen mit optimalizálni, mert nem csak aritmetikát végzel, hanem lookupot is - az, hogy mivel töltse fel a regisztert, az a ciklusban dinamikusan változik. Hiszen a sip->sip_offset, amit lookupra használsz, a ciklus lefutásában számítódik ki. Lehet, hogy ez konstans érték mindig, de semmi nem garantálja. Én unrollolnám ezeket a sip struktúra elemeket lokális változókba. De valószínűleg így sem fogja tudni SIMD-dé alakítani. Te kézzel át tudnád úgy alakítani a dolgot, hogy valóban egy vektoron, valóban azonos műveletet azonos operandussal végezzen minden vektorelemen a CPU? Mert itt láthatólag nem ez történik, mindegyik vektorelemen más-más operandussal kell végezni a műveletet, emiatt nem lehet SIMD-esíteni.
Igen, az adott hogy mely bufferekbol melyikbe kell dolgoznia, szoval a lookup sem elhanyagolhato mennyisegu ido. Mondjuk a phase_shift_array eleresen talan lehet optimalizalni olyanertelemben hogy nem annyira gyakran rendezodik az at (gyakorlatban mondjuk 5-10 masodpercenkent valtozik a sip->sip_step erteke, mikozben ez a sif_out_buffer feltoltese 2.4MSPS-sel kell hogy porogjon kvazi-valos idoben (gyakorlatban masodpercenkent kb 9x fut le, ez a blokk nsamples=262144-es ertek mellett... szoval ahhoz kepest a sip->sip_step "lassan" valtozik, igy a tomb egyszeri atrendezesevel lehet nyerni valamennyi cache-eleresi idot).
Egy pár ötlet:
Ha sip_step lassan változik, akkor nem elképzelhető, hogy fel lehet úgy osztani a ciklus blokkokat, hogy egy blokkban állandó legyen a sip_step értéke? Ha így volna, akkor ki lehetne hagyni teljesen a lookupot.
Általánosságban a RAM elérés mindig lassabb mint a regiszter, tehát RAM elérésre érdemes optimalizálni a kódot.
Ezen kívül a sip_offset értékét nem tárolnám memóriában, hanem számolnám mindig, hogy hol tart (ha lehetséges, de a kódból úgy veszem ki, hogy lehetséges). Ha 1-2-3 helyi változóval meg lehet oldani (regiszter), akkor gyorsabb lesz, mint memóriából olvasgatni és visszaírni.
Indirekciók: nagyon megnézném, hogy a kettős indirekciók között nincsen-e olyan, amit valóban két memória eléréssel csinál a CPU? Remélhetőleg az O3 megoldja, de én ilyesminél ki szoktam emelni a pointert lokális változóba biztos ami biztos.
A sif_phase_shift_length értéke konstans, remélhetőleg nem olvassa minden körben RAM-ból?
A look up nem egy szinusz-koszinusz táblázat valójában (a phase-ből meg a változónevekből tippelném, hogy egy forgóvektorról van szó)? Nem lehetséges, hogy ki lehet számolni trigonometrikus függvényekkel és nem kell hozzá memóriát használni? A CPU-n elérhető gyorsítókat nem ismerem, de például GPU-n ezek a függvények 1 órajelesek volnának, hatékonyabb kiszámolni, mint táblázatból venni. (Sima CPU utasításokkal sajnos nem gyorsabb számolni, ahogy utána olvastam.)
Ez el is vezet oda, hogy ilyen fajta számítást szerintem nagyon jól lehet GPU-ra optimalizálni. Persze több munka, de jó móka lehet kipróbálni és méregetni, hogy mit tud a GPU. OpenCL-lel lehetne fejleszteni például, és talán az Intel GPU-n is lehetne futtatni és azon is gyors volna. Régen csináltam ilyen összegzős programot GPU-ra (OpenCL+NVidia volt) és valóban nagyon gyors volt, köröket vert a CPU-ra.
Még tovább gondolva: valami olyasmit csinálsz, hogy 8-asával végzed el az összegzést úgy, hogy az érték vektorokat forgatod (2D térben). A 8-asok egymást átlapolva vannak felvéve! Meg lehetne talán csinálni azt, hogy egy mintát csak egyszer töltesz be, és mind a 8 műveletet elvégzed rajta, egyszerre számon tartva a nyolc összeget! Elég sok regiszter kellene ehhez, de talán beleférne a CPU-ba, és akkor tényleg villámgyors kódot lehetne csinálni!
Izgalmas, szép feladat, szinte irigyellek! Sok sikert hozzá!
Igenigen, itten komplex szamok komplex egyseggekkel valo szorzasat es felosszegzeset kell megoldani, valojaban ez a megoldando problema: https://latex2png.com/pngs/3ffeb319ad07ff3c84446cd87d102b2a.png. Ahol a memoria-eleres mar eleve a kettos indexu valtozo, z^{(k)}_j miatt nem annyira egyertelmu. Ugye ezek jonnek a bemeneti bufferbol (sib->sib_buffer), es ott ugy vannak sorbarendezve hogy nnode darab, nsample hosszusagu tomb van egymas mogott, linearisan (ezt persze ki lehet valtani kettos indirekcioval, de ahogy mondod, nem biztos hogy jol jarnank ezzel). A p_k, q_k ertekek pedig a sip->sip_offset ill sip->sip_step ertekek, amik lenyegeben barmilyen egesz szamok lehetnek.
A lookup is azert kerulhetett bele mert az \exp() csak N fele erteket vehet fel, az elegge konstans (N az a sif->sif_phase_shift_length a programban). Es az \exp() periodicitasa miatt a lookup-megoldas nagyon termeszetesen adja magat, viszont az ketsegtelen hogy a q_k tetszoleges erteke miatt nagyon kell benne ugralni.
Szoval tkp ezt a formulat barhogy at lehet rendezni hogy az jo legyen ;)
Kicsit hasonlit az egesz a DFT/FFT temakorre az \exp() fuggveny ill a hasaban levo komplex egyseggyok-hatvanyok miatt, de azert nem is teljesen ugyanaz. Es emiatt a hasonlosag miatt gondoltam hogy a SIMD jo lehet, merthat ugye pont ezeket szoktak iskolapeldanak hozni(?). GPU itt sajnos annyira nem jatszik. Egyreszt nem ertek hozza ennyire, es ez most konkretan egy headless, beagyazott gep, sztem olyan combos GPU nincs is benne (ha egyatalan), viszont az meg meginkabb architekturafuggove tenne a dolgot...
pk, qk értéke mi? Ez valami rádiós mintázat, ami egy adott átviteli csatornához tartozik?
N értéke mennyi? Az nem ugyanaz, mint az nnode, ami pedig 8? Félreértem?
Nagyjából megértettem: z-ben, ami a programban a sib_buffer nnode*nsample*2 darab érték van (nnode*nsample komplex szám). Szerintem az első probléma az, hogy nem lineáris így a forrás buffer elérése, a k szerinti címzés miatt ugrálva kell kiolvasni. Jobb lenne, ha a k szerinti értékek egymás mellett lennének, akkor lineárisan olvasná végig a forrást a program. A memória elérés általában szereti, ha sorban olvassuk a memóriát. (És a SIMD utasításoknak is ez előfeltétele, ha jól emlékszem.) (Bár PC-n nem mértem még, de más processzoron így volt, hogy ha sorban olvastuk és írtuk a memóriát, az kb másfélszer gyorsabb volt mintha nem. PC-n szerintem a cache-be egész sorokat tölt be a RAM-ból a PC, és ha nem sorban olvassuk, akkor elérhetjük, hogy kikerül a cache-ből az adott sor mire újra rákerülne az olvasás.)
Lásd: "opcionalisan annyi lehet a konnyites hogy a rot_cos, rot_sin ertekek valojaban i16-osak es a ci/cq ertekek pedig i8-asok" Tehát ezekből 4 illetve 8 közlekedhet egyetlen memória művelettel! Sőt, a rot értékek ha kevés elemű táblázatok, akkor teljes egészében regiszterben is tárolhatók lehetnek.
Hasonlóan a sif_out_buffer kiírását is lehet optimalizálni, ha többet egyszerre írunk ki.
Ha összesen 8 féle együttható van, és ezeket sorban használjuk fel, akkor mindenképpen valahogy "tudatnám ezt a programmal", hogy az index csak lépegessen, de ne memóriából jöjjön, és vagy egy kicsi tömböt indexelve működjön, vagy még jobb, ha ki van hajtogatva a ciklus, ahogy mások is írták. Fontos volna, hogy a kihajtogatást lehetővé tedd a fordítónak: az nnode értéke konstans legyen a fordító számára is!
GPU témája: Ha hinni lehet az Internetnek, akkor 23 execution unit van a GPU-jában:
* Intel® UHD Graphics 630 van benne eszerint: https://ark.intel.com/content/www/us/en/ark/products/201890/intel-core-…
* Aminek 23 exec unitja van eszerint: https://www.techcenturion.com/intel-uhd-graphics-630
Szóval nem lehetetlen, hogy működne. Elképzelhetőnek tartom, hogy ebben a feladatban kisebb energiafelhasználás mellett jobb teljesítményt adna a GPU, mint a CPU. De ne is feszegessük, valóban rengeteg plusz munka ilyet programozni, és kétséges az eredmény.
Igenigen, ez egy radios cucchoz lesz ;) (azert is nem "re" meg "im" a ket komponens neve hanem I meg Q) Az nnode az 8 (de valtoztathato, szoval nem igazan lehet es/vagy erdemes bevasalni a forraskodba #define formaban), az nsample az most epp 262144, az N (sif->sif_phase_shift_length) pedig 240000 jelenleg, de az csak specifikus ertekeket vehet fel. A p_k es q_k ertekek meg tetszoleges egeszek lehetnek (nyilvan 0 es 240000-1 kozott van ertelme, az \exp() fuggveny ciklikus/periodikus visekledese miatt).
Igen, koszi, most ezen agyalok hogy az sib_buffer tombben nem nnode darab nsamples hosszusagu komplex szam (cu8) van, hanem nsamples hosszan, nnode hosszu rekord (ami igy 16 byte lesz a gyakorlatban). Ez downstream oldalon lesz kevesbe hatekony hiszen azokat a buffereket meg akkor szet kell huzni... de lehet hogy osszessegeben tenyleg megeri, foleg hogy akkor egy fokkal kiegyenlitettebb lesz a processzor terhelese.
> de valtoztathato, szoval nem igazan lehet es/vagy erdemes bevasalni a forraskodba #define formaban
Optimalizálásra kitalált kódokban rendszeres trükk, hogy egyes paraméterek lényegében kódgenerátor paraméterek, és mondjuk minden nnode értékhez külön kód tartozik. Vagy annyi függvény van, ahány változatban elképzelhető a paraméter, vagy használatkor fordítják le és töltik be dinamikusan a megfelelő változatot. (Például ilyen rajzoló könyvtárakban pixelműveletek esetén láttam ilyen kódokat.) Ezzel lehet ezt a problémát kikerülni úgy, hogy a dinamizmus is megmaradjon és a kecske is jól lakjon. Persze ez is extra bonyolultság...
Ahhoz is szükséges lesz a paraméterek fixálása, hogy SIMD-et tudjon használni a processzor (legalábbis több esélyed van, hogy sikerül neki), de az alap utasításokra épülő megoldás is gyorsabb lesz tőle várhatóan. Az szerintem legenda, hogy úgy lehet SIMD-et csinálni, hogy bele se gondolsz és majd a fordító alád teszi. Pontosan tudnod kell, hogy mit vársz a fordítótól és ha szerencséd van észreveszi, hogy alkalmazható a megoldás. Tehát az adataid szerkezetét hozzá kell igazítanod azokhoz a SIMD utasításokhoz, amit majd használni akarsz.
Én egyszer próbáltam SIMD megoldást csinálni valamire, és az jött ki, hogy az algoritmus memória sávszélesség limites, ami SIMD esetén is ugyanannyi, és nem lesz valójában gyorsabb tőle. Persze csak azután, hogy az adatok elrendezését úgy optimalizáltam, hogy az elérésük optimális legyen.
Az OpenCL hordozható: több GPU-hoz is van illesztője, és CPU-ra is tud fordítani és ha szerencséd van még arra is viszonylag optimális eredményt tud adni.
Mértél már, hogy hogyan teljesít az algoritmusod, és milyen teljesítményre volna szükséged?
A fordító csak akkor tud vektorizált pl. SSE4, AVX vagy AVX2 utasításokat generálni, ha tudtára adod, hogy generáljon ilyeneket (-msse4 -mavx -mavx2). Lásd https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html. A fent nevezett i3-as procinál ezeket mind egyszerre be lehet kapcsolni az -march=native kapcsolóval.
A Godbolt-tal online ki is lehet ezeket próbálni és meg lehet tekinteni a kiköpött utasításokat, pl.: https://godbolt.org/z/Z7ApPy