Program többszálúsítása
2014-01-17T20:51:38+01:00
2014-01-19T08:24:09+01:00
2022-07-23T01:12:21+02:00
  • köszönöm a hozzászólásokat

    nekilátok megvalósítani a tervet, ha valahol elakadok, akkor majd konkrétumokkal is jelentkezek
    Mutasd a teljes hozzászólást!
  • Errre volt valami fejtegetésem, hogy hogyan érdemes ezt kultúr módon csinálni egy magasszintű nyelvben manapság (assemblyben helyezgettem cache-re optimalizálva nagyjából utoljára, így bár gondolom meg tudnám oldani, hogy a feltételed teljesüljön, de nem lenne túl szép a kód - c/c++ esetén talán van erre valami pragma, de más nyelvek?)

    Jelenleg nincs kultúr mód rá Java-ban (dolgoznak rajta, de az gyakorlatilag Java9-et jelent). Nem kultúr van, de a JIT próbál kereszbe tenni azzal, hogy kitalálja hogy olyan változókat deklaráltál amiket nem is használsz, ergo nincs is rájuk szükség. C++-ban van, mert ott te mondod meg, hogy hova allokálja amit akarsz, és azt nem mozgatja. 

    Itt ha jól értem arra játszunk, hogy bár a memory barrier hiánya miatt nem rendelkezünk megfelelő láthatósággal és később jut el hozzánk csak a frissülés, az megint csak nem baj, hiszen ekkor addig pörög a fogyasztó node, amíg rá nem futunk egy barrier-re máshol ami miatt láthatóvá válik a változás, vagy valami egyéb dolog miatt láthatóvá nem válik. Gondolom az, hogy nem kell minden írásnál memory barrier, az bőven több gyorsítást tud eredményezni, mint a plussz esetleges üresjárat - főleg ha tényleg kicsik a műveletek amit a node végez.

    Ugyanakkor jut el a változás, a CPU mindig ugyanolyan gyorsan flusholja a buffereit. Kérdés, hogy te ezt az író thread-en meg akarod-e várni, a memory-barrier ugyanis ezt biztosítja: vár amíg a store buffer kiürül.
    Java-ban a lazySet jellegű műveletekkel megteheted, hogy csak compiler barriert használsz, ami biztosítja hogy a JIT nem rendezi át azt, amit nem szabad, tehát a CPU megfelelő sorrendben látja az utasításokat. Ez pedig single-writer esetén elég a helyes működéshez. Multiple writer esetén NEM, ott kell a memory barrier is, de a cél hogy minél kevesebb legyen.

    Más: Anno sokat gondolkoztam rajta, hogy olyan modellben megéri-e programozni, ahol minden thread-közti kommunikáció csak read-only módon zajlik. Arra gondolok, hogy minden thread-hez ugye tartozna egy teljesen lokális rész és tartozik egy megosztott változóhalmaz, amit viszont szintén csak ő maga írhat. Anno nekem az volt a benyomásom, hogy ilyen feltételek mellett könnyebben tudok ügyeskedni, de nem tudtam megfogalmazni, hogy miért, vagy hogy mik az általános előnyök, úgy tetszik tételek. Annyira azért sokat nem foglalkoztam azzal, hogy ezen agyaljak - inkább csak egy ötlet volt anno, de most újra eszembe jutott. Úgy veszem ki a szavaidból, hogy ez a single writer dolog nagyjából ugyanez (vagy valamilyen viszonyban van legalábbis azzal amit most felfestek) és azért ezt a területet kutatják is, aminek örülnék, mert akkor nem teljesen bugyuta ötletem volt

    Algoritmus függő. Lehet adatot (más adatot más thread dolgoz fel), lehet logikát particionálni (pl. pipeline). Feladata válogatja mikor melyiket érdemes.

    Nem vagyok annyira találgatós kedvemben, de érdekelne, mert utoljára jcip alapján, java concurrent-el és hasonlókkal meg a java memory modell alapján (a c++nál úgy érzem lényegében lekoppintották) stb. amikor írtam egy szerintem _NAGYON_JÓL_ párhuzamosítható feladatra egy megoldást a korábbi kétmagos gépemen, akkor úgy 1.5-1.6x lett csak gyorsabb a szekvenciális alapmegoldáshoz képest.

    Az az 1.5-1.6x az egész jó. Ne felejtsd el, a többszálúsítással csak a CPU magok számát dupláztad meg. Minden más maradt ugyanaz: ugyanazon a memóriabuszon kapod az adatokat. Viszont cserébe kaptál várakozást a szinkronizációs pontokon: vársz a QPI buszra. Na az lassú.

    A C++ memória modelljénél is ugyanaz volt a cél: egy olyan modell létrehozása, amivel lehet érvelni. Ugyanazokon a hardvereken kell futnia. Nyilvánvalóan hasonló lesz a végeredmény. A Java-é egy kicsit hamarabb készült, a C++-é kicsit jobb lett. A Java-ét kb. a Java 9 környékén kicsit frissíteni akarják, akkor méginkább hasonlítani fog a C++-éra, ami azért is hasznos, mert könnyebb ha a programozók ugyanazzal a modellel dolgozhatnak mindkét platformon.

    Melóban pedig bár elég sok synchronized-et leírok, inkább konkurens a rendszer, mint párhuzamos és arra kell koncentrálni, hogy precízen és jól működjön mindenképpen, meg karbantartható legyen, így nem akarok volatile-ozni, hogy a jelenlegin felül is agyalni kelljen a kódomon bárkinek is. Épp elég bizonytalannak érzem néha azt is, ami most van....

    Nincsen baj a sok synchronized-al, ha nincsenek nagy teljesítmény igények. Eltekintve attól, hogy nem lehet átlátni, hogy mikor ki mire szinkronizál, kire vár, mikor kerül deadlockba, stb...

    A teljesítmény szempontjából sem jó, ha ezek a bonyolultabb dolgok szanaszét hevernek a kódban. Az azt jelenti, hogy a feldolgozás túl sok ponton szinkronizációt próbálsz elérni, ahelyett hogy a lehető leghamarabb elkülönítenéd egymástól a különböző adatokon dolgozó viselkedéseket, és sorbarendeznéd a versengő feladatokat, hogy utána plusz várakozások nélkül, single-threaded stílusban dolgozhass.
    Mutasd a teljes hozzászólást!
  • Azta szemét szerkesztőjét ennek az új proghunak !! Szép csak bugos és az idézetek kezelése miatt elveszett a HSZ

    No még egyszer nekifutok:

    "Nem feltétlenül lokális, ha végiggondolod ez a finished(i) értéke ha 1-1 megfeleltetés van a fázisok adatai között."
    - Igazad van, ezt benéztem, de itt találtam ki és ennyi belefér

    "Ezenkívül ezek a finished változók legyenek külön cache-line-okon (legalább 64 byte-al arrébb) hogy ne pingpongozzon a cache-line-al a sok core, ha egyszerre akarod írni őket."
    - Errre volt valami fejtegetésem, hogy hogyan érdemes ezt kultúr módon csinálni egy magasszintű nyelvben manapság (assemblyben helyezgettem cache-re optimalizálva nagyjából utoljára, így bár gondolom meg tudnám oldani, hogy a feltételed teljesüljön, de nem lenne túl szép a kód - c/c++ esetén talán van erre valami pragma, de más nyelvek?)

    "Ezentúl még vannak bizonyos optimalizációs lehetőségek, pl. single writer stage esetén nem full memory barrier csak compiler barrier használata (a compile reorderingjét nem engedi, viszont nem csinál hw memory barriert) a pozíciójelző írásakor, de ezt már bonyolultabb elmagyarázni, és CPU architektúra függő (ebből a szempontból az x86 elkényeztet minket). "
    - Itt ha jól értem arra játszunk, hogy bár a memory barrier hiánya miatt nem rendelkezünk megfelelő láthatósággal és később jut el hozzánk csak a frissülés, az megint csak nem baj, hiszen ekkor addig pörög a fogyasztó node, amíg rá nem futunk egy barrier-re máshol ami miatt láthatóvá válik a változás, vagy valami egyéb dolog miatt láthatóvá nem válik. Gondolom az, hogy nem kell minden írásnál memory barrier, az bőven több gyorsítást tud eredményezni, mint a plussz esetleges üresjárat - főleg ha tényleg kicsik a műveletek amit a node végez.

    Más: Anno sokat gondolkoztam rajta, hogy olyan modellben megéri-e programozni, ahol minden thread-közti kommunikáció csak read-only módon zajlik. Arra gondolok, hogy minden thread-hez ugye tartozna egy teljesen lokális rész és tartozik egy megosztott változóhalmaz, amit viszont szintén csak ő maga írhat. Anno nekem az volt a benyomásom, hogy ilyen feltételek mellett könnyebben tudok ügyeskedni, de nem tudtam megfogalmazni, hogy miért, vagy hogy mik az általános előnyök, úgy tetszik tételek. Annyira azért sokat nem foglalkoztam azzal, hogy ezen agyaljak - inkább csak egy ötlet volt anno, de most újra eszembe jutott. Úgy veszem ki a szavaidból, hogy ez a single writer dolog nagyjából ugyanez (vagy valamilyen viszonyban van legalábbis azzal amit most felfestek) és azért ezt a területet kutatják is, aminek örülnék, mert akkor nem teljesen bugyuta ötletem volt

    "Itt akkor vársz, akkor amikor épp nincs mit csinálnod, nem pedig akkor amikor épp történik valami és te versenyzel vele, ahelyett hogy csinálnál valamit. "
    - Viszont elméletben azért nem-busy waiting-nél megoldható, hogy valahogy kevésbé forrjon fel a processzor és egye a wattokat, ha mondjuk nem szépen és kiszámíthatóan jön az adatforgalom, hanem burst-ökben, melyeket nagy kihagyások követnek és hasonlók. De nyilván igazad van, hogy ez nem teljesen az a busy waiting - de végülis akkor is busy waiting, csak szerintem nem kell félni az elnevezéstől.

    "Direkt nem írtam le a technológia nevét, kiváncsi vagyok valaki ismeri-e innen. Válaszokat lehet privátban küldeni, túró rudi sajna nem jár."
    - Nem vagyok annyira találgatós kedvemben, de érdekelne, mert utoljára jcip alapján, java concurrent-el és hasonlókkal meg a java memory modell alapján (a c++nál úgy érzem lényegében lekoppintották) stb. amikor írtam egy szerintem _NAGYON_JÓL_ párhuzamosítható feladatra egy megoldást a korábbi kétmagos gépemen, akkor úgy 1.5-1.6x lett csak gyorsabb a szekvenciális alapmegoldáshoz képest. Ez akkor nekem nem tűnt igazán jónak, pedig ilyen mátrixos műveletek voltak és lényegében csak az egyes iterációk végén volt szinkronizálás + amennyire lehet minden threadindítgatási, meg hasonló macerákat kerültem, meg persze task-thread fogalmak szétválasztása is megvolt stbstb. A lényeg, hogy legalább arra a feladatra olyan 1.8 körüli speedup értéket vártam akkor is, ha kultúrált eszközöket használok, amivel még nagyjából átlátható is volt a cucc és nagyobb volt az overhead, mint gondoltam. Mostanában nemigen méregetek semmi ilyesmit már jó ideje, mert visszatértem egy olyan 7+ éves laptopra, miután a modernebb megadta magát a garancia letelte után. Mostanában inkább csak igyekszem mindenféle lightweight software-t használni linux alól és amíg igazán nincs szükségem rá, addig nem venni új gépet, mert így legalább nem játszok rajta annyit :)))
    Melóban pedig bár elég sok synchronized-et leírok, inkább konkurens a rendszer, mint párhuzamos és arra kell koncentrálni, hogy precízen és jól működjön mindenképpen, meg karbantartható legyen, így nem akarok volatile-ozni, hogy a jelenlegin felül is agyalni kelljen a kódomon bárkinek is. Épp elég bizonytalannak érzem néha azt is, ami most van....

    Privátban ha nem akarod ide írni, akkor megküldheted mire gondolsz
    Mutasd a teljes hozzászólást!
  • Egyébként lehet hasonló algoritmusokról külön olvasni valahol? Mármint ilyenekre gondolok, amelyek nem igényelnek tényleges szinkronizációt, csak volatile-on keresztül. Szívesen olvasnék ilyenekről, mert szerintem érdekes dolog és nem hiszem, hogy nekem kéne ezeket a megoldásokat kitalálni, mert én nem tudom nem-e rontottam most el azt, amit úgy hellyel-közzel felfestettél (próbáltam figyelni arra, hogy ne rontsam el)

    Lehet, de először mindenkinek az alapokat kell megtanulni, hogy megértse hogy a ráépülő dolgok miért működnek korrekten.

    Utána meg már könnyű célzatos google keresésekkel konkrét megoldásokat találni.

    Direkt nem írtam le a technológia nevét, kiváncsi vagyok valaki ismeri-e innen. Válaszokat lehet privátban küldeni, túró rudi sajna nem jár.

    Amúgy itt is van szinkronizáció és várakozás, de csak ami szükséges. A lock overheadje a legtöbb esetben nem szükséges.

    Itt akkor vársz, akkor amikor épp nincs mit csinálnod, nem pedig akkor amikor épp történik valami és te versenyzel vele, ahelyett hogy csinálnál valamit.
    Mutasd a teljes hozzászólást!
  • Ha jól sejtem, akkor azt mondod, hogy ne szinkronizáljunk hagyományos módon, hanem trükközzünk a volatile-al.

    Nem azt mondtam, hogy trükközzünk, hanem hogy használjuk a volatile long-ot és az általa biztosított memory barriert szinkronizációra.

    A pozíció jelzőként pedig arra jó, hogy amit volatile-ból olvastál, azt az adatpozíciót a volatile érték beírását megelőzően írtad, tehát a memory barrier miatt látod ami benne van. Viszont ezután már nem fogod írni, mivel a pozíciójelző túlmutat rajta, tehát nem fog továbbiakban változni (mivel egyetlen szál írhatja a felelősség megosztás miatt, és az pedig már kiírta).

    Egyébként konkrétan akkor most arra gondolsz, hogy:
    - Van n darab feldolgozó külön szállal.
    - van finished1..finishedn volatile long változók, amikkel jelzi a pipeline node, hogy ő mennyit tett le az asztalra.

    Igen, bár a mennyit tett le az asztalra helyett azt mondanám, mennyit dolgozott már fel az inputjából. Az inputja vagy közös, ha azonos input adatsoron kell több egymásra épülő feldolgozási fázist végrehajtani, vagy az előző outputja ha szigorúan vett pipeline-ról beszélünk.

    Azt is nyilvántartom (ezt már belsőleg, csak a saját szál területén), hogy én meddig dolgoztam már fel a dolgokat.

    Nem feltétlenül lokális, ha végiggondolod ez a finished(i) értéke ha 1-1 megfeleltetés van a fázisok adatai között.

    A többi stimmel. Lényeg, hogy csak olyat dolgozz fel amit tudod, hogy már nem írnak, és csak olyan pozíciót írj a te finished változódba, amit már nem fogsz később írni.

    Ezenkívül ezek a finished változók legyenek külön cache-line-okon (legalább 64 byte-al arrébb) hogy ne pingpongozzon a cache-line-al a sok core, ha egyszerre akarod írni őket.

    Valamint az írt adatok is legyenek külön cache line-okon a különböző szálaknál.

    Ezentúl még vannak bizonyos optimalizációs lehetőségek, pl. single writer stage esetén nem full memory barrier csak compiler barrier használata (a compile reorderingjét nem engedi, viszont nem csinál hw memory barriert) a pozíciójelző írásakor, de ezt már bonyolultabb elmagyarázni, és CPU architektúra függő (ebből a szempontból az x86 elkényeztet minket).
    Mutasd a teljes hozzászólást!
  • Ha jól sejtem, akkor azt mondod, hogy ne szinkronizáljunk hagyományos módon, hanem trükközzünk a volatile-al. Ekkor ezt gondolom nem igazán lehet busy waiting nélkül csinálni, ami nem feltétlen baj, de akkor gondolom attól függ az alkalmazhatósága a módszernek, hogy mennyire nyúlnak el a lépések bizonyos esetekben, mert ez inkább akkor jó, ha kiegyensúlyozott és viszonylag kicsi feladatokra bontunk. Nyugodtan tegyél helyre, ha tévedek, de nekem most így jön le.

    Egyébként konkrétan akkor most arra gondolsz, hogy:
    - Van n darab feldolgozó külön szállal.
    - van finished1..finishedn volatile long változók, amikkel jelzi a pipeline node, hogy ő mennyit tett le az asztalra.
    - Azt is nyilvántartom (ezt már belsőleg, csak a saját szál területén), hogy én meddig dolgoztam már fel a dolgokat az engem megelőző nódustól.
    - Ha épp elkészültem egy feladattal és én vagyok az i.-edik feldolgozó node, akkor nézem a finished(i-1) változót, hogy az nagyobb-e mint a lokális változóm, amiben tárolom, hogy meddig olvastam ki a cuccot már az előzőből. Itt nyilván kaphatok fals értéket, ami már elavult - mert a kiolvasás volatile és utána az még változhat még az egész feltétel kiértékelés előtt, de abből sose lesz baj, mert így maximum nem csinálom meg a műveletet, amit meg tudnék csinálni és a következő loop-ban sikerül...
    - Ha érzékelem, hogy van bent új elem, akkor elindul a feldolgozás.

    - Ha feldolgoztam teljesen, akkor én is növelem a saját finishedi volatile változómat

    - stb. stb.

    Elmések az ilyen megoldások


    Egyébként lehet hasonló algoritmusokról külön olvasni valahol? Mármint ilyenekre gondolok, amelyek nem igényelnek tényleges szinkronizációt, csak volatile-on keresztül. Szívesen olvasnék ilyenekről, mert szerintem érdekes dolog és nem hiszem, hogy nekem kéne ezeket a megoldásokat kitalálni, mert én nem tudom nem-e rontottam most el azt, amit úgy hellyel-közzel felfestettél (próbáltam figyelni arra, hogy ne rontsam el)
    Mutasd a teljes hozzászólást!
  • Ennél talán konkrétabb példát kellene látni. Mekkora egy adat (egy szám, vagy akár egy több megás memóriaterület), mekkora/milyen a "lépés".

    Nagy mennyiségű adatot valószínűleg fel lehet osztani, hogy egy részét az egyik szál, a másik részét a másik szál dolgozza fel, legfeljebb bevárják egymást.
    Matematikai képleteknél is biztos ki lehet szedni részeket és előre küldeni azt egy másik szálnak, hogy spóroljon az első szál.
    Mutasd a teljes hozzászólást!
  • Tipikusan ilyen helyzetben nem jatszani akarsz a lockolassal, hanem kihajitani es inkabb a feldolgozast ugy szervezni hogy ne utkozzenek egymasba.

    Ha van egy lokalis adatfeldolgozo muvelethalmazod, ami a legjobban vissza tudja fogni a sebesseget, az a folyamatos lockolas (es a logolas).

    Minden szakasznak van egy dedikalt szala, minden szal mas memoria teruletre ir, es csak az elozo szakaszok memoriateruleteirol valamint az inputbol olvashat (single-writer principle).

    Egy csak folyamatosan novekvo ertekeket felvevo volatile long value-val pedig jelzi a kovetkezo szakaszoknak, hogy o meddig jutott mar el a feldolgozasban (megint single-writer principle).

    Ekkor mar csak annyi a dolgod, hogy az inputot biztonsagosan sorbarakd es a sorban a poziciot egy long-al reprezentalni tudd.
    Mutasd a teljes hozzászólást!
  • Csak általánosságban: a jellemzően olyan felépítésű alkalmazások remekül teljesítményfokozhatóak. Ha gyakorlati konkrétum érdekel, vagy az egész megoldásának szöszölős kérdései (van ám belőlük, mint égen a csillag), akkor írj konkrétumot.
    Mutasd a teljes hozzászólást!
  • lehet (lásd: adatcsatorna tétele)

    ahhoz hogy működjön is, általában fontos feltétel az egyes feldolgozó processzek (szálak) közti gyors kommunikáció, főleg az, hogy minél kevesebbet kelljen várni az adatok berakására és kivételére. lehet játszani a lockolással :)
    Mutasd a teljes hozzászólást!
  • Mik az adatok es a lepesek?
    Mutasd a teljes hozzászólást!
  • Kell egy szálbiztos sor-szerkezet, amibe az egyik oldalon (a feldolgozási sorban előrébb lévő szálból) pumpálod be a kimeneti adatokat, a másik oldalon meg veszed ki belőle őket bemenetként (a feldolgozási sorban később lévő szál számára). Ezen keresztül jól láncba tudsz fűzni feldolgozó szálakat a programon belül, minimális feldolgozási fejrésszel.

    Persze mindez csak akkor működik, ha a kimenet felbontható olyan diszkrét egységekre, blokkokra, amik az egyes feldolgozási lépések szintjén önállóan kezelhetők, vagy legfeljebb csak az előttük jövő adatoktól függenek, később várhatóaktól nem. Egyéb esetben ugyanis nyilvánvalóan meg kell várni amíg az előző feldolgozási fázis az utóbbi adatokhoz is elér, mert addig nem lehet a későbbi lépéseket megkezdeni a már addig elkészült adatokon (sem).

    Ha megadsz nyelvet akkor lehet kapsz tippet arra is, hogy milyen osztályt érdemes használni a szóban forgó sorszerkezet céljára, vagy ha az alap futtatókörnyezet nem biztosít ilyent, akkor hol találsz letölthető komponenst, osztályt erre a célra.
    Mutasd a teljes hozzászólást!
  • sziasztok!

    Az érdekelne, hogy lehet-e egy olyan programot többszálúsítani, ahol a program a megkapott inputon egymás után kell hogy elvégezzen különféle műveleteket, ahol mindig az egyes lépések eredményeit kell tovább feldolgozni.

    tehát input -> lépés1 -> eredmény1 -> lépés2 -> eredmény2 -> stb -> output
    Mutasd a teljes hozzászólást!
abcd