CUDA grep - hardveresen gyorsított regex illesztő

Szerszám

Manish Burman és Brandon Kase a CUDA-t hívta segítségül arra, hogy egy hardveresen (GPU) gyorsított, párhuzamosított regex illesztőt hozzon létre. Az implementációjuk a méréseik szerint - a feladattól függően - körülbelül 2x-10x gyorsabb a grep-nél, illetve 68x gyorsabb a perl regex engine-nél.

Részletek, kód stb. itt.

( Salcay v | 2013. 06. 04., k – 11:24 )

Ha az egész shell-t meg tudnák csinálni hardware gyorsítottra, az lenne csak szép... Perverz állatnak számítok, ha szeretek shell scripteket írni?

Nem vagyok informatikus, de nekem eddig erről a jelenségről az a kép alakult ki, hogy nem a fejlesztők akarnak ilyen számítási módokra áttérni, elvégre mindenkinek kényelmesebb jól megszokott módszereknél maradni.

Ami miatt mégis kénytelenek erre az útra lépni az az, hogy a hardverek teljesítménye véges és az esetleges gyártástechnológiai váltások lassulásával / nehezebbé válásával kénytelenek lesznek minden erőforrást kihasználni és amiben tudják, tehermentesíteni a CPU-t.

Valószínűleg ezért lépett az Intel és az AMD is az APU fejlesztés útjára, és ez volt talán a lényege anno a Larrabee projektnek is.

Az APU koncepció szerintem nem erről szól, hanem arról, hogy ne kelljen az alaplapra integrálni valamilyen egyéb VGA -t, hanem majd az AMD/Intel jól beletesz egyet a CPU-jába (persze olyat amit ő gyárt), így nem fordul elő hogy pl. AMD procis gépekbe rivális, integrált GPU kerül (pl. Intel).

--
http://developersideas.blogspot.hu/
http://neurogadget.com/

Ez csak mellekhatas. Az APU koncepciot gyakorlatilag ugyanazert hivtak eletre, amiert a memoria vezerlo belekerult a CPU-va egy tokba, novelni a leadott teljesitmenyt. Ha nem teljesen vilagos ez, akkor nezd meg a Sony PS4 felepiteset, rogton erthetove valik.

---
pontscho / fresh!mindworkz

akkor miért tett az AMD hatalmas erőfeszítéseket azért, hogy közös virtuális címtérrel közös memóriavezérlő mögé tegye a GPU-t és a CPU-t? Ha csak az lett volna a cél, hogy egy tokon belül legyenek és ezért a konkurencia termékét ne integrálják az alaplapra, akkor ez nem lett volna szempont.

( tr3w v | 2013. 06. 04., k – 11:43 )

A részletek alapján a teszt elég mesterséges volt, és így is csak ennyi eredményt értek el...

Persze játéknak jó.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

( fabian-bros | 2013. 06. 04., k – 11:58 )

Hanyszor nagyobb infrastrukturan (1 mag helyett X) ertek el 10-szeres gyorsulast?
mikor jon a cat(1) implementacioja quantum processzorokra felhos megvalositasban html5 kimenettel?

Szerk: Megneztem, mit lehet parhuzamositani egy ilyen fajoan linearis probleman.
Ha tobb regexet matchelnek, akkor mindegyiket egyenkent parhuzamosan.
Raadasul egy teljesen buta matcher-t hasznalnak (vannak sokkal jobbak/gyorsabbak mar evezredek ota)
Erre en nem adnek diplomat, mert anyam megcsinalja egy CUDA manual-lal. De itt tart most az informatika oktatas.
System programming-ot meg kiveszik a curriculum-bol, mert sokan buknak....

szerk2: Ha irok egy multithread echo(1)-t, lehetek hir a hup-on?

--------------------------------------
Unix isn't dead. It just smells funny.

Igen, hozzá kellett volna tennem, hogy nem láttam még regexp értelmezőt közelről, ezért elég naivan közelítettem meg a problémát.

Amikor faluhelyen a haverokkal leülök télen a fonóban regexpet illeszteni, felosztjuk egymás között a stringet, és mindenki elkezdi rá matcholni a regexp elejét. Ha valakinek a saját stringje előbb elfogy, mint a regexp, átszól a komájának, hogy a saját stringjére illeszkedik-ë a regexp maradéka. Így tökjó párhuzamos.

Persze el tudom képzelni, hogy akit komolyabban programozni tanítottak, ennél hatékonyabb parsolási módot is ismer. 

int getRandomNumber() { return 4; }  // ← aláírás
//szabályos kockadobással választva. garantáltan véletlenszerű.  xkcd

Ha jól emlékszem (de nem biztos!), a grep regex-ei max 1 sorral nyúlhatnak előre.

Akkor a párhuzamosítás úgy zajlódhatna, hogy egy soros átlapolásokkal szednénk darabjaira a fájlt. Tehát pl. az első node-ra jutna az, 1,2,3,...,10. sor, a másodikra a 10,11,12,...,20., a harmadikra a 20,21,22,..., 30. stb.

És a cikkhez: lehet, hogy ez még nem egy praktikus dolog, de jó, hogy valaki dolgozik ezen. Hátha kijön belőle valami. Szerintem nagyon nem használjuk még ki a GPU-k kapacitását, pedig lehetne jobban.

Ez ugyanugy nem oldja meg azt a problemat, hogy a 10-ik es 11-ik sorra matchel a regex.

Masreszt akarhany newline is lehet a regexben (a perl szintakszisuban) a /s modositoval matchel az ujsorra is.

"Szerintem nagyon nem használjuk még ki a GPU-k kapacitását, pedig lehetne jobban."
A GPU arra jo, hogy adatparhuzamos dolgokat csinalj rajta. Soros feldolgozasra hasznalhatatlanok.

A regex adva van, meg lehet nézni, hogy max hány sorra illeszkedhet, és annyi sornyi átfedéssel particionálni az óriás szövegfile-t.

Egyébként nem tudom, hogy mások hogy vannak vele, de én elenyészően ritkán használok többsoros regexet, szóval részemről már az is teljesen jó lenne, ha az elején megnézné, hogy egy vagy többsoros-e a regex, és ha egysoros, akkor adatparticionál, ha több, akkor meg nem.
Másrészt amikor annyi szöveget kell átnézni, hogy a teljesítmény számítana, akkor ott esetemben legtöbbször sok (forrás)file-ról van szó (git grep, grep -r), ekkor meg adja magát, hogy file-onként lehet particionálni.

A problemam ezzel az egesszel, hogy ez egy beadando (ne adj isten diplomamunka)
Ami annyit innoval, hogy lefordul nekik egy CUDA helloworld jellegu alkalmazas.
Meg hogy ez hir erteku minden uberhozzaerto szamara.

--------------------------------------
Unix isn't dead. It just smells funny.

Szerintem nem azert lett hirerteke mert diplomamunkaban oda csapott egy helloworldot CUDA-ban, hanem az otlet miatt lett felkapott a hir, ami igazabol nem hulyeseg, csak meg az itt leledzo "szakemberek" tobbsege is 1bites es eszebe sem jutott volna a GPU-t felhasznalni egy ilyen triviahoz.

---
pontscho / fresh!mindworkz

( uid_1062 | 2013. 06. 04., k – 12:10 )

SIEM rendszereknél ez egy valós szűk keresztmetszet.
Ha Javában lenne megírva valószínűleg többen izgulnának rá.
Mindenképpen nagyon jó móka ez.

( vargad | 2013. 06. 04., k – 23:58 )

Vajon benne van az is hogy át kell másolni a fájlt a GPU memóriájába? A legtöbb nagy mennyiségű adatot igénylő feladatnál az önmagában szokott olyan sokáig tartani, hogy nincs értelme az egésznek. Nem hiszem, hogy a kernel forrás greppeléséban is megveri a GNU grep-et.

Benne van, mert olyan mély dolgokról elmélkednek, hogy érdemesebb több sort átmásolni egy hívással ahelyett, hogy soronként küldözgetnék, sőt még oda is eljutnak, hogy elég a gpu-n megkeresni a sorhatárokat...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

( lazyone | 2013. 06. 05., sze – 00:03 )

Bocs, nincsenek pontos ismereteim. Ez a CUDA nem arra való jórészt, hogy a GPU-kat általános számítási feladatokra használjuk?

Mert ha igen, akkor ezt nem tartom jó ötletnek. A GPU shaderek tudomásom szerint buta számdarálók. Vmi VLIW vagy SIMD cucc, ami arra jó, hogy "sok" arithmetikai műveletet tudjon elvégezni párhuzamosan.

Viszont nem jó pl. branch prediction-ben és karakteres adat kezelésben. Biztos meg tudja csinálni, de nem hatékony és sok energiát fogyaszt.

Erre akár több, egyszerűbb, de általánosabb célú proci jobb lehet.

A CUDA valóban számdarálásra ideális, pl. float számolásban piszok gyors. Arra optimális.

Viszont... annyi processzor van egy mai GPU kártyán, hogy sok lúd disznót győz. Ha 256-szoros párhuzamossággal csinálsz valamit, abba belefér az is, hogy amúgy per core 10*rosszabb a hatékonysága. (ezek példa számok, of course)

Ez persze tekinthető olyan perverziónak is, mint ha pl. fényképezőgéppel vernél be szöget, na de ha ládaszám vannak fényképezőid, akkor nem zavar a dolog annyira :)))))))))

( zoli78 | 2013. 06. 06., cs – 13:25 )

hardveres gyorsító kártyát szövegekben való mintakeresésre már a 90-es években is gyártottak. Ma is el tudom képzelni, hogy FPGA-val lefejlesszenek speciális feladatokra ilyet. Ami sajnos elviszi a nyers teljesítménybeli előnyt az az, hogy oda kell másolnod a szöveget a GPU memóriájába, szervezned kell az eredmények kinyerését és a részfeladatok kiosztását. Ha hozza a teljesítményt, akkor is eljuthatsz könnyen arra a pontra, ahonnan már hagyományosan CPU-ra írt programnak kell átvennie az eredményeket és további feladatokat végezni vele, és ez utóbbi is lehet szűk keresztmetszet.
Az meg, hogy mi értelme van egy ilyennek? Hát ne csak egy desktop gépben vagy egy SOHO webszerverben tessék gondolkodni, hanem mondjuk egy google szerverfarmban ahol sokmillió kérést kell másodpercenként kiszolgálni és bőven van mit párhuzamosítani, van mivel tömni a feldolgozóegységeket.

FPGA-át értelmesebbnek látom erre a feladatra. Adatok mozgatását meg talán meg lehet DMA-val oldani, addig a proci szabadon csinálhat más feladatokat, vagy éppen ő is regexpezhet egy másik adathalmazon.
Még talán DMA-zni sem kell. A célhardver bus master módban olvashatja a fizikai memóriát (MMU-t és proci cache-t kikerülve).
Pl. FPGA-ba lehetne beletenni annyi párhuzamos regexp engine-t amennyit csak sikerül. Jelezni neki, hogy a feladatokat melyik memória címen találja meg, meg hogy hova tegye le az eredményeket, meg hogy mikor adjon interruptot (pl. ha már 3000 regexpet feldolgozott, vagy ha már a regexp motorok 20% felszabadult).
Persze az FPGA - CPU memória busz sebessége szűk keresztmetszet lehet.
Meg az is lehet, hogy a 100-200MHz-en tötyögő FPGA nagyon megfogja a GHz feletti sebességre képes memória buszt (nem ismerem a mostani hardvereket, bocs) és többet rontana a rendszer teljes hatékonyságán, mint amennyit javítana.
Sok buktató van szerintem is.