Tanulj meg párhuzamosan programozni - vagy halj ki!
2010-11-06T19:48:05+01:00
2010-11-22T05:23:59+01:00
2022-07-24T21:32:24+02:00
  • Ez igazán szép összefoglaló, köszönöm. Egészen más megvilágításba helyez dolgokat. Például hogy kis feladatoknál nem nagyon érdemes szálakat gyártani, mert annyi idő alatt lehet, hogy már egy szál is végez. És hogy első lépésben érdemes a vektoros műveleteket erőltetni, legalábbis a két maggal szemben. Illetve hogy nagyon adatintenzív feladatoknál az összes trükköt hagyni lehet, mert a memóriaelérési sebesség dönt.

    Én is erre jutottam, hogy ahhoz, hogy szép párhuzamos algoritmuoskat lehessen leírni, igen erős fordítóra van szükség, ami az ilyeneket tudja. És/vagy már a legelején legyártani 2 (4) szálat, és közöttük útközben szétosztani a feladatokat. Vagyis egy ideig maradnak még a lib-ek, illetve a feladatok modelljétől idegen megfogalmazások (szál, SSE2, Altivec, stb.).

    Mutasd a teljes hozzászólást!
  • Kiserletezgettem ma ezzel a linSearch-al egy csoppet es vegeredmenyben ez a fakta kereses annyira memoriaintenziv, hogy gyakorlatilag irtam egy cache/ram sebessegmerot.

    Tehat a teszt: linearis kereses int32-re, es ugy, hogy direkt olyan szamot adok neki, ami nincs benne a tombben. Ez lenyegeben a legrosszabb eset (csupa olyan szavakat keresunk, amelyek nincsenek a tombben). A tesztet egyreszt elvegeztem 8KB, 16KB... 256MB kulonbozo adatméretekre, masreszt pedig kétféle párhuzamositassal (2thread, sse(uroll+simd)) meg ezek kombinaciojaval.

    (Minden egyes tesztet 10x hajtottam vegre, es ebbol vettem a leggyorsabbat. A 2thread teszteknel pedig annyiszor hajtottam vegre a keresest ugyanazon az array-on, hogy vegeredmenyben 16MB atnezese jojjon ki, ezzel a win32 pár millisec (borzalmasan) hosszu threadkezelési overhead-jét kikuszobolve.)

    Az kulonbozo modszerek konnyebb osszehasonlithatosaga miatt nem idoket raktam grafikonra, hanem atviteli sebesseget MByte/Sec -ben.

    Ezek lettek az eredmenyek.

    Magyarazat:
    - Barmilyen optimizalasnak csak akkor hatasos, ha hosszu tavon beleférünk az valamelyik cache szintbe(jelen esetben ez kozos L2 6MB illetve core-onkent egy-egy L1 32KB)
    - 8KB es 16KB adatmeretnel folyamatosan ugyanazt a teruletet olvasom (amig vegul ki nem jon 64MB), emiatt a proci cache-ja kissé meghülyül, emiatt ivel felfele a grafikon elejen a 2 sse gorbe. Az x86-os valtozat annyira 'lassan' nyul a cache-hoz, hogy ott még nem is kapcsol be ez az automata cache-ba elore olvaso mehanizmus.
    - 32KB-nal az 1 thread SSE kodnal az a csúcs, az 1 darab mukodo processzormag 32KB meretu L1 cache-jat jelzi.
    - 64KB-nal szinten van egy csúcs: itt 2 processzormag osszesen 2*32KB byte adat-on belul keres, mindket mag maximalisan kihasznalja az L1 cache-okat.
    - 128KB-tol felfele az L1 cache-ok mar 'haszontalanok', innentol az L2 cache fog dolgozni. Parhuzamos uzemnel a 2 processzormag konkurens modon fogja hasznalni az L2 cache-t, emiatt itt mar nem 2x, hanem csak 1.5x (***) gyorsulas van 2threadnel.
    - 6MB felett pedig elfogy az L2 cache, itt mar akarmilyen modszernel a RAM lesz a bottleneck.

    (***) ez az sse programbol adodik -> most kb. 3-4 utasitas jut 1 darab 128bit memoria olvasasra. Két ilyen programszálat párhuzamosan futtatva még szépen össze tudja fésülni a proci a memoria olvasasokat, innen jott ez a 1.5x gyorsulas. Ha pl. 2-3 utasitas jutna egy read-ra, az már az L2 cache-nak is sok lenne es akkor már nem lenne olyan hatasos a 2szálon futás.


    "Szerintem előfordulhat olyan eset, amikor szigorúan az első találatot keressük. Például összefüggő szövegben egy szó első előfordulása."

    Ez a tobbszintes cache hierarhia is pont erre van kitalalva: a 'szoveg' elején, 32KB-nal nagyon gyors (ott 1 orajel/read), az elso 6MB-nel eleg gyors (sztem olyan 3 clock/read lehet), aztan efelett meg nem gyors, de legalabb megy (saccra minimum 10 clock/read) es megtalalja az 'iszonyat ritka szavakat'.

    Na es ez 1fajta proci, az 'i' sorozatnal ha jol sejtem, 33%-al tobb utasitas tud bent lenni feldolgozas alatt (kevesebb uresjarat bénább kód mellett is (a fenti sse sem 100-as, i3-on jobban futna)) es triple channel ramok vannak, oda lehet, hogy kicsit mas strategia lenne a nyero. Erre a strategiara persze az új paralell nyelvi elemunknek automatikusan figyelnie kéne (JIT compiler) :p

    src
    Mutasd a teljes hozzászólást!
  • Azért erőltettem én ezt, mert azon gondolkodtam, hogy a lineáris keresés javítható-e párhuzamosítással. Szerintem előfordulhat olyan eset, amikor szigorúan az első találatot keressük. Például összefüggő szövegben egy szó első előfordulása. Tudom, hogy ez nem pont ugyanaz, de más esetben is lehet, hogy az első indexre vagyunk kíváncsiak.

    Nekem ilyesmi jutott eszembe párhuzamos algoritmusként:

    function parlinsearch( needle, haystack, n, out i ) { if 0 = haystack.count then return false; result = true; if linsearch( needle, haystack[0 .. n-1], i1 ) then i := i1; parelse if parlinsearch( needle, haystack[n .. haystack.count-1], 2*n, i2 ) then i := i2; else result = false; return result; }

    Kissé pongyolán egy (még) nem létező párhuzamos nyelven. A parelse ág elkezdhet futni az első then ággal párhuzamosan, vagyis mire az befejeződik, már meglehet a második részből az eredmény. Kérdés persze, hogy lehet-e ilyesmiből hatékony gépi kódot csinálni, hogy hogyan használhatók ki az egyes operációs rendszerekben a több mag által nyújtott lehetőségek, meghaladja-e a szálnyitogatások költsége az esetleges hasznot. Tudnak-e dolgozni egyszerre a processzorok a tömb egyes szeletein. Tudtok erre mondani valamit? Hogy ne kelljen kihalnom.
    Mutasd a teljes hozzászólást!
  • Igen, utólag én is rájöttem, hogy ez nem rossz, sőt...
    Bár ebben a témában, jobban érdekelnek azok a feladatok, amiket több maggal nagyságrendekkel jobban meg lehet oldani, pl MI, és genetikus algoritmusok. Több ezer, vagy netán több százezer lebutított maggal, biztosan érdekes dolgokat lehet művelni, amiket mezei x86-ossal olyan lenne mint szorobánon számolni.
    Mutasd a teljes hozzászólást!
  • "... nagyobb feladatok párhuzamosításának szükségtelenségét éritek el."
    Ez szerintem nem rossz dolog, ui. ebben az esetben a meglévő 'szekvenciális' programok telejesítményén is lehet javítani.

    Mutasd a teljes hozzászólást!
  • Ha valahova lineáris keresés kell, akkor ott már valami eleve nem jó.

    Lehet rosszul gondolom, de szerintem az alap algoritmusok párhuzamosításával, csak a nagyobb feladatok párhuzamosításának szükségtelenségét éritek el. Tehát ugyanúgy marad soros minden, csak ami alatta ül az párhuzamosan van megoldva.
    Mutasd a teljes hozzászólást!
  • Elméletileg persze, hogy lehet! Miaz hogy! :D
    Itt az az eljaras fog leginkabb vegrehajtodni, ami a stringeket hasonlitja ossze, ha azt Cha-r onként csinálja, akkor nagyrész cachebol tud mukodni, szoval van esely, hogy gyakorlatilag is megéri a pchar tombben keresést parhuzamositani.

    Aztan itt jon az, hogy mi van akkor, ha 'csalunk' és egy rendezett hash tömb-ben keresunk binarisan (amit a pchar arraybol generaltunk). Itt is jol johet a parhuzamositas.
    Mutasd a teljes hozzászólást!
  • Én elméleti síkon gondolkodtam, hogy két maggal lehet-e jobb lineáris keresést csinálni. De jó, ha mindenáron konkretizálni akarunk, akkor a kérdés legyen mondjuk egy 10000 szavas PChar szótár, amiben az első olyan szót keressük, ami nincs benne az értelmező szótárban.
    Mutasd a teljes hozzászólást!
  • Ez nagyban fugg attól, hogy mik a tömbelemek, milyen muvelettel lehet megmondani egy elemrôl, hogy stimmel vagy nem (pl egy case insensitive string compare az eleg nagy muvelet).

    Sima int32[] array? Vagy classptr[] array, amelyen belul ott egy int32 field, amire keresunk?

    A fenti 2 peldanal inkabb a ram lesz a bottleneck, szoval itt nem segit a tobb core, mert csak egymassal tolakodnának memoria olvasásért. (Ha meg benne vannak az adatok a chache-ban, akkor viszont megint mas a helyzet :D) Nade ezekrol nemigen van konyv, ki kell probalgatni.
    Mutasd a teljes hozzászólást!
  • Közben meg abba a hibába estem, hogy a saját hozzászólásom elgondolkodtatott. Mármint hogy létező algoritmusok párhuzamosítása. Optimális párhuzamos algoritmusok adása ismertebb problémákra. Mondjuk néhány processzoron. Vagy sok processzoron. Létezik ilyesmiből jól összeszedett anyag? Mondjuk lineáris keresés 2 processzorral. Vagy 4 magos maximum kiválasztás. Segít, ha több processzor van? Mi lehet az optimális algoritmus? Milyen nyelvi elemek kellenek ahhoz, hogy az algoritmust szépen le lehessen írni? Lehet-e olyan algoritmust találni ami többé-kevésbé optimális 1, 2, 4, vagy 8 processzor esetén is? Van erre valakinek ötlete?
    Mutasd a teljes hozzászólást!
  • Hát én erre azt gondolom, hogy attól függ, honnan indul az ember. Ha a nyelvtől indulsz, akkor tényleg sok mai OO nyelvnél azt láthatod, hogy jó bonyolult (főleg az OO miatt) és ha hozzátenél, még bonyolultabb lenne. Viszont ha onnan indítasz, hogy van egy feladatod, vagy feladatköröd, amit jellemzően párhuzamos eszközökkel lehet jól kezelni, és elgondolkozol, hogy akkor vajon milyen nyelvi elemek kellenek neked hozzá, lehet, hogy ki tudsz találni valami olyat, amiben a megoldást pikk-pakk frappánsan, jól éthetően le tudod írni.
    Mutasd a teljes hozzászólást!
  • Go-ban megvan ez a csere amire gondolsz:

    package main import ."fmt" func main() { a := 563 b := 327 a , b = b , a Println(a,b) }
    Mutasd a teljes hozzászólást!
  • A funkcionális nyelvek tényleg jól hangzanak párhuzamossági téren...

    Amúgy HZ mindig meséli is, hogy a függvényalkalmazás asszociatív, a funkcionális program egy nagy függvénykompozíció és hogy van az asszoc tétel, lehet párhuzamosítani, ennyi
    Jó, persze azért semmi se ilyen egyszerű. De tényleg van lehetőség a funkcprogban, mert nincs pointer, referencia, nincs mellékhatás és egy csomó más olyan dolog sincs, ami egyébként egy sima program fordítását már akkor is megzavarja, ha nem hogy taszkokra, csak pipeline-ra optimalizálnak.
    De ez olyan kétélű dolog, na mind1...

    Viszont, lehetne pár jó dolog a nyelvekben:
    -Végülis nem kell parallel for-each, a simát észre lehet venni ha párhuzamos, de esetleg hintelni lehetne.
    -Miért nincsenek szimultán értékadások? Olyanra gondolok, hogy ha az ember leírja, hogy:
    a, b <- b, a;
    Akkor az a szemantika, hogy megcseréli az változókat(értsd: olyan szemantika, mintha az értékadások valós párhuzamosok lennének és megbonthatatlanul pillanatszerű lenne ez a sor)
    Ez tök hasznos lehetne, mert segítene a fordítónak pipeline-osítani, SSE-re optimalizálni(gondolj bele, hogy mindenféle pragma nélkül leírsz egy csomó ilyet egymás alá és szépen bepakolja az sse regekbe meg ott számol), sőt ha elég hosszú ilyen szakaszok vannak, akkor indíthatsz is annyi thread-et(jó ez azért ritkán érné meg, beismerem)

    De akár olyat is lehetne, hogy nyitsz egy PP{} blokkot, melybe nem írhatsz elágazást, ciklust és hasonlókat, hanem csak utasításokat, amik valami külső feltételig tetszőleges összefésüléses szemantikával futhatnak, sorrendtől függetlenül.
    Mármint a PP blokk-hoz tartozna valami kilépési feltétel mondjuk, a blokk magja pedig egy utasításhalmaz, melyekről a programozó nem feltételezheti, hogy milyen sorrendben hajtódik végre, csak hogy időnként legalább minden utasítás kiválasztódik.

    Néha jó lennének ilyenek, mert az, hogy kódokat elemzünk és keresünk párhuzamosságot benne az nem biztos hogy jó, lehet hogy ki kéne találni inkább újfajta vezérlési szerkezeteket és hasonlókat.

    ui.: Én személy szerint jobban szeretem, ha a nyelv támogat ilyen cuccokat és nem a library, de azért az se olyan rossz
    Mutasd a teljes hozzászólást!
  • Na mondjuk ebben van valami. Párhuzamosítani egy algoritmust néha igen csak nehéz de sokszor szép feladat!

    Pl. az nyilvánvaló, hogy a ray-tracing párhuzamosítható. De pl. azon meglepődtem, hogy milyen szépen párhuzamosítható egyetlen háromszög fillezése is mondjuk 16 felé:

    Parallel software rasterization
    Mutasd a teljes hozzászólást!
  • En azt gondolom, hogy a jo parhuzamos program, nem a fejleszto eszkozon bukik el.
    Szervezesileg, gondolkodas, szemlelet.
    Ha rosz a program strukturaja(oo) akkor nem lehet jol parhuzamositani.
    De lehet, hogy a feladat zarja ki a parhuzamositast.

    Mutasd a teljes hozzászólást!
  • Itt két dolog van.
    Az egyik, hogy jobbnak tartjátok, hogy nem 3rd party megoldás legyen erre, hanem legyen egy megoldás a nyelv szállítójától. Ezeket az érveket elfogadom.

    Viszont a nyelv szállítója még mindig kétféleképpen járhat el:

    - A: telepakolja a nyelvet mindenféle konstrukciókkal
    - B: lehetőség szerint a lehető legkevesebb de nagyon produktív jól kombinálható featuröket tesz a nyelvbe. Ezekből összepakol cuccokat, és azokat a standard könytárába teszi.

    A mai fejlett nyelvek már így is elég bonyolultak, tehát ha csak lehet a 'B' stratégiát érdemes használni. Vagyis az egy jó design döntés, hogy ha valami a standard lib-be tehető, azt oda kell tenni és nem a nyelv specifikációjába. Ezáltal a nyelv specifikációját és a fordítót józan bonyolultságon tartva. Scala-ban a foreach egy (higher order) függvény a standard libraryben. A parallelforeach is lehetne ilyen függvény, nem feltétlenül van szükség arra, hogy nyelvi kulcsszó legyen belőle, ezáltal bonyolítva a nyelv specifikációját, a nyelv szabályait, a nyelvi fordítókat.

    Röviden: Nyelv design alapelv, hogy egy feature-höz csak akkor legyen külön nyelvi szabály, kulcsszó, stb... ha az feltétlenül szükséges és nem oldható meg 'szépre' a standard lib továbbfejlesztésével.
    Mutasd a teljes hozzászólást!
  • Nem nagyon értem a nagy különbséget aközött, hogy a nyelv alapból, 'beépítetten' képes az ilyen konstrukciókra, vagy egy lib segítségével képes rá. Utóbbinak az az előnye, hogy nem mindent a nyelv kitalálóinak kell beleépíteni a nyelvbe, hanem a lib írók is kitalálhatnak új dolgokat.

    Éppen ez a baj vele. Hogy ti. 100 fejlesztő kitalál 150-féle megoldást rá, amik ráadásul ha elég alapszintű dolgok, akkor lesz még másik 2000 magasabb szintű könyvtár ami ezekre épül. És így egyik megoldásra épülő program nem lesz kompatibilis és/vagy összeköthető a másikkal.

    De ha még esetleg szeparálhatók is az egyik ill. másik (harmadik, negyedik, ötödik, stb.) megoldást használó részei az alkalmazásnak, akkor is redundánsan lesz benne ugyanaz a funkcionalitás. Ezen kívül mivel így egy-egy alternatívára, megoldásra arányaiban kevesebb ember jut (annál mintha egyetlen közös, a nyelvbe eleve beépített megoldás lenne rá), ezért azt kevesebben tesztelik is majd, és nyílt forrás esetén kevesebben is javítják, mert az erőforrások szétforgcsolódnak, ami megint csak nem tesz jót az így előálló kódhalmaz összminőségének.

    Persze ennek igazából semmi köze a párhuzamos programozáshoz - pontosabban szólva minden másra ugyanúgy igaz, mint a párhuzamos programozással összefüggésbe hozható nyelvi megoldásokra, rutinokra, stb. (ha úgy tetszik ez egy teljesen általános alaptétel ill. -igazság). Csak ha már felvetetted...
    Mutasd a teljes hozzászólást!
  • Nincs nekem a Scalaval bajom semmi, biztos kiváló eszköz. Lényeges különbség akkor lenne, ha volna olyan programnyelv, ami tudná azt, amit írni próbáltam. A parallelforeach attól lenne parallelforeach, hogy a nyelv specifikációjában annyi volna megadva, hogy ez valami olyasmi, ami kötetlen sorrendben egy tömb minden elemére hattat egy függvényt. Ha a függvény olyan, hogy az architektúrán hatékonyan SSE utasításokkal lehet futtatni, akor a fordító SSE-t fordítana belőle. Ha az adott gépen 4 mag lenne, akkor az első az elsőre, ötödikre, stb. hattatná a függvényt, a második a másodikra, hatodikra, és így tovább. Ha a futtató gépen egy mag lenne, lehet, hogy a szimpla ciklus futna az elemekre. Az volna a lényeg, hogy programozóként ezen ne kelljen gondolkodni, ezt a részt, hogy mit hogyan párhuzamosítok, párhuzamosítok-e egyáltalán, ezt elvégezné a fordító, vagy esetleg a futtató gépen a virtuális gép. Hogy programíráskor ne azon kelljen gondolkodnom, hogy én hogyan párhuzamosítom a feladatot, ezt a terhet levenné a fordító a vállamról. A Cleanes példa ebből a szempontból igen jó.

    Na, még arra, hogy miért nem ugyanaz egy funkció libben, mint nyelvi elemként. Ha parallelforeach nyelvi elemként van, akkor az azt jelenti, hogy azt a funkcionalitást kell tudni a fordítónak, mindegy, hogy hogyan. Új hardvereken ugyanaz a kód esetleg lényegesen jobb megvalósítással fordulhat, amíg a funkcionalitásnak megfelel. Könyvtárként egy konkrét megvalósításod van, ami vagy horodzható, vagy nem, vagy változik később, vagy nem, vagy csatolnod kell a programodhoz, vagy nem. Illetve még egyszer. Ha könyvtári függvényt használsz, tele lesz a kódod könyvtári függvény hívásokkal, jellemzően olyan helyeken, ahová a programlogika szerint egyáltalán nem való. Nyelvi elemeken viszont senki sem ütközik meg, aki a nyelvet ismeri.

    De tudom én, hogy hol végződik a valóság, és én is azt mondom, hogy manapság jó párhuzamos könyvtárakkal, vagy komponensekkel lehet jó párhuzamos programokat készíteni.

    Mutasd a teljes hozzászólást!
  • hogy a parallelforeach beépített függvény, vagy lib-ként megírt?


    Általában nem. Törekedni kell arra, hogy minél kevesebb third party komponenst használj, vagy ha használsz is, azok megbízható, nagyobb cégek termékei legyenek, ne csak egy zseni egyéjszakás fellángolása, amit utána cseszik fejleszteni, te meg ott vagy egy itt-ott bugzó libbel és egy fél éves projecttel, ami erre épült...
    Mutasd a teljes hozzászólást!
  • Nana, én épp azt mondom, hogy akkor lesz továbblépés, ha az ilyeneket nem "meg lehet csinálni", hanem a nyelv képes rá. Előbbi esetben csak oda fogsz ilyet írni, ahol azt gondolod, hogy szükség van rá, utóbbi esetben meg mindenhova ilyen kifejezést fogsz írni, ahová csak lehet.


    Nem nagyon értem a nagy különbséget aközött, hogy a nyelv alapból, 'beépítetten' képes az ilyen konstrukciókra, vagy egy lib segítségével képes rá. Utóbbinak az az előnye, hogy nem mindent a nyelv kitalálóinak kell beleépíteni a nyelvbe, hanem a lib írók is kitalálhatnak új dolgokat. a parallelforeach függvényt használó programozónak nem teljesen mindegy, hogy a parallelforeach beépített függvény, vagy lib-ként megírt? A lényeg, hogy használja. Pl. Scala-ban senki nem használ hagyományos threadeket, hanem mindenki az actor lib-et használja. Pedig az actor lib nem a nyelvbe van építve, akár te is írhattad volna.
    foreach-re sem képes a Scala 'alapból', 'beépítetten' de van ilyen függvénye a Seq-nak (mindennek, ami szekvenciaként fogható fel ebből öröklődik), ezért mindenki használja.
    Mutasd a teljes hozzászólást!
  • Nana, én épp azt mondom, hogy akkor lesz továbblépés, ha az ilyeneket nem "meg lehet csinálni", hanem a nyelv képes rá. Előbbi esetben csak oda fogsz ilyet írni, ahol azt gondolod, hogy szükség van rá, utóbbi esetben meg mindenhova ilyen kifejezést fogsz írni, ahová csak lehet. Én azt gondolom, hogy a jelenleg elterjedt szálazós megoldás kissé technikás és körülményes. A programozó kell figyeljen arra, mikor indít szálat, mikor állítja le, és ő kell végiggondolja, lesz-e, lehet-e ütközés a közös memóriában. A szál többnyire operációs rendszer elem, programírás közben nem tudod, hogy hány magon fog futni a programod, vagyis lehet, hogy az egész csak lassít. Ha ezzel szemben például a nyelved modellje olyan, hogy eleve annyi szálad van, ahány magon futtatni akarod, és a fordító olyan kódot csinál, ami mondjuk minden egyes hívást (lehetőleg) más szálra pakol, plusz esetleg valami nyelvi leleménnyel hatékonyan megoldja a közös objektumok elérését, akkor nincs szálgyártási/leállítási/szinkronizálási költség, vagy alig.

    Azt nem tudom, hogy a clean használ-e több szálat/több magot. Emlékeim szerint számolásoknál igen szépen ment, de bizonyos feladatoknál (hálózat, grafikus felület) igencsak természetellenesnek tűnő dolgokat kellett írni.

    Go-ról nem tudok sokat. Amit olvastam, az a goroutine meg a channel. Ezek jópofák.
    Mutasd a teljes hozzászólást!
  • Ezt én értem, de konkrétan hogyan csinálnád meg ezt gyorsra? A funkcionális nyelveknek a gráf újraírás elméleti modellje csak: a gyors funkcionális nyelvek interpreterei szvsz ugyanúgy stacken lévő paraméterátadással dolgoznak mint az imperatív nyelvek, sőt a gyorsabbak nem interpretáltak, hanem gépi kódra fordítottak.

    Azt írtad, hogy ha elágazáshoz érkezik a program, akkor a két ágat futtathatja külön szálban. De pont az a kérdés, hogy mikor döntsön így? Minden egyes elágazás esetén ez óriási overhead, mint írtam. Pl. egy szorzás gyakorlatilag semmi egy procinak, egy művelet egy másik threadbe való kidelegálása jóval időigényesebb dolog. Erre írtam, hogy esetleg az egy jó heurisztika, hogy megtippeljük, hogy mennyi ideig fog tartani egy kifejezés kiértékelése. Tehát valamiféle JIT-et el tudok képzelni, ha egy függvény várható kiértékelési ideje elég nagy, akkor veszem a fáradságot és mondjuk úgy JIT-telem le a kódot, hogy a két ágat külön threadbe schedulálja.

    (Amúgy funkcionális programozás esetén is kell gondolkodni a performanciáról. Pl. a fibonaccinak az a megoldása amit írtál az ú.n. tree-recursive megoldás, ami döglassú és redundáns. A Fibonaccinak létezik tail recursive megoldása is. A Tail rekurzió az, amikor a rekurzió a függvény kiértékelésének utolsó eleme. A Tail rekurziót minden komolyabb nyelv gépikódban egyszerű ciklusra fordítja. Pont erről a fibonacci példáról, a tree rekurzióról itt lehet olvasni:

    SICP - Tree recursion
    )
    Mutasd a teljes hozzászólást!
  • " Belátható, hogy a fenti példa esetén 2 proceszormaggal 2x olyan gyorsan lehet kiszámolni ugyanazt."


    Szerintem te nem értetted meg, amit nadamhu felvetett:
    "Gondolom az a nehézség benne, hogy valahogy a runtime-nak ki kellene találni, hogy melyik függvényeket érdemes külön threadbe schedulálni."


    Ha ugyanis a Clean a futtatáskor nem méri azt fel, hogy megéri-e egyáltalán több szálon futtatni a példában szereplő Fibonacci rekurziót, akkor például fib(5) esetén két szálon lassabban funa le az, mint egy szálon. 4 szálon meg még ennél is lassabban. Ennek az az oka, hogy egy új szál nyitása iszonyúan sok időt vesz igénybe, így ténylegesen csak akkor éri meg párhuzamosítani, ha a rekurzió várható körbefordulásai időben meghaladja az új szál(ak) nyitásának idejét. Ezt pedig nem hiszem, hogy a Clean figyelembe venné, az szerintem ha érdemes-, ha nem, mindig párhuzamosít, ha teheti.

    Mivel a Fibonacci fa mérete (csomópontjainak száma) a rekurzív függvény bemenő paraméterével szemre is legalább négyzetének felével arányos, így tippem szerint legalább fib(12)-nél kb. 60 lépés kell ahhoz, hogy megtérüljön a szálnyitás(ok) ráfordított ideje. Ennél kisebb számnál a párhuzamosításkori szálak adminisztrációja nemhogy gyorsítana, de egyenesen lassít is a működésen.

    Összefoglalva tehát nadamhu-nak nem a funkcionális nyelvek adta lehetőségekre akart utalni, hanem arra, hogy egy ilyen nyelvvel elkészített kód a futtatáskor milyen módon dönti el, hogy egyáltalán érdemes-e párhuzamosítani, vagy sem. Na ez itt a tényleg jó kérdés...
    Mutasd a teljes hozzászólást!
  • Gondolom az a nehézség benne, hogy valahogy a runtime-nak ki kellene találni, hogy melyik függvényeket érdemes külön threadbe schedulálni.


    Ez így nem jelenthető ki ilyen egyértelműen. Egy funkcionális nyelvben írt program teljesen másképpen fut, mint egy imperatív nyelvben. Míg egy imperatív nyelv kötelez az utasítások egymásutáni futtatására, a funckionális nyelvekben az imperatív nyelveknek megfelelő utasítások igazából nem is léteznek, csak függvénykiértékelések sorozatából áll az egész program.

    Fibonacci rekurzív változata C kódban:

    int fib(int n) { if (n == 0 || n == 1) return 1; else return fib(n-2) + fib(n-1); }

    Fibonacci rekurzív változata Clean kódban:
    fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1)

    Ugye a rekurzív formulát használva - függetlenül attól, hogy melyik nyelvről van szó - a következő módon értékelődik ki például a fib(5):
    fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(1) | | | | | | | -> fib(0) | | -> fib(1) | | | -> fib(2) -> fib(1) | | | -> fib(0) | -> fib(3) -> fib(2) -> fib(1) | | | -> fib(0) -> fib(1)


    A C fordítónak ugye nincs sok beleszólása a dolgok sorrendjébe, szóval a fenti fának szépen sorban kell kiértékelje a csomópontjait (vagyis kiszámolja a függvényértékeket). A fenti alprogrammal a kövektező a függvényhívási sorrend:
    fib(5), fib(4), fib(3), fib(2), fib(1), fib(0), fib(1), fib(2), fib(1), fib(0), fib(3), fib(2), fib(1), fib(0), fib(1)


    A Clean értelmezőnek ellenben szabad keze van: tetszőleges sorrendben értékelheti ki a csomópontokat, mert - függetlenül attól, hogy mit tartalmaz a függvény - a hívások nincsenek hatással egymásra. Megteheti azt, hogy annyi szálon értékeli ki őket, amennyin az aktuális rendszerarchitektúra mellett optimális. Nem nehéz elképzelni, hogy a fenti kiértékelési fán először elindul 1 szálon, aztán, ha elágazáshoz jut (fib5) és éppen van szabad feldolgozási szál, átadja neki a munkát (vagyis párhuzamosan számítja fib4-et és fib3-at), és ezután már 2 szálon futhatnak tovább a kiértékelés, egészen a kövektező elágazásig. Belátható, hogy a fenti példa esetén 2 proceszormaggal 2x olyan gyorsan lehet kiszámolni ugyanazt.

    Persze ez csak akkor lehetséges, ha a kiértékelési fa elágazó. Amennyiben egy lánc, nincs semmilyen lehetőség párhuzamosításra.

    Amúgy, egy ilyen értelmező használata nagyon nagy overhead-nek tűnhet azzal szemben, hogy az imperatív nyelveket egyenesen bináris kóddá lehet fordítani. A wiki a következőt írja:
    How clean works: Computation is based on graph rewriting and reduction. Constants such as numbers are graphs and functions are graph rewriting formulas. This, combined with compilation to native code, makes Clean programs relatively fast, even with high abstraction
    Mutasd a teljes hozzászólást!
  • Ha nem értem félre amit a runtime statisztikáról írtál: futtass modjuk egy 5-10 másodperces, tisztán CPU-t használó python programot profilerrel (ami kb. azt a statisztikát készíti, amit említettél) és nézd meg, meddig fut úgy!

    ---
    Egyébként automatikus parallel végrehajtásra tudok élő példát: PL/SQL...
    (legalábbis tanfolyamon valami ilyesmit emlegettek anno... sajnos már kidobáltam a tananyagaimat )
    Mutasd a teljes hozzászólást!
  • Nem lenne egyszerűbb processort használni és ROM-ban tárolni a programot? Vagy processort tervezel?
    Mutasd a teljes hozzászólást!
  • Amiket példákat írtál (backslash operátor, select és parallelforeach függvények) azok jó ötletek, és biztos az igazi a nyelvi támogatás lenne, de felxibilisebb nyelvekben ezt elég szépre meg lehet csinálni egyszerű lib-ként. (Nem akarok mindig a Scala-val dobálózni de ha jól látom mind a hármat meg lehet benne csinálni. (Csinálni egy Job osztályt, annak backslash operátort definiálni, aztán implicit konverzióval bámely kifejezést 'név szerint átvéve' Job-á konvertálni, majd a backslash kiértékelésekor ténylegesen párhuzamosan végrehajtani a Job-ok által hivatkozott 'név szerint' átvett kifejezéseket.))
    Mutasd a teljes hozzászólást!
  • Igen. A funkcionális nyelvek régóta velünk vannak, és sokan jósolták az elterjedésüket, de nem terjedtek el. Most sokan mondják, hogy most tényleg szélesebb körben elterjedhetnek a párhuzamosságra való igény miatt.
    Az Erlang úgy tudom tisztán funkcionális, párhuzamosságra kitalált nyelv, de sajnos nem ismerem.

    Amit a teljesen transzparens (VM által kitalált) párhuzamosításról írsz, az nagyon érdekes. Gondolom az a nehézség benne, hogy valahogy a runtime-nak ki kellene találni, hogy melyik függvényeket érdemes külön threadbe schedulálni. Nyilván egy szorzást végrehajtó függvényt nem érdemes: az overhead túl nagy lenne a elvégzett feladathoz képest. Erre most lett egy ötletem: runtime statisztikákat vezethetne a VM a függvények végrehajtási idejéről, és a várhatóan nem túl rövid ideig futókat (mondjuk várhatóan legalább egy millisec-ig futókat) schedulálná másik threadbe/magra. Nagyon érdekes téma, mostanában amúgyis érdeklődök mindenféle automatikus kódfordítás, kódelemzés, automatikus refactoring iránt. Igazából ezt sem feltétlenül kellene VM szinten megvalósítani: pl. elképzelhető, hogy mind a statisztika csináló, mind az auto párhuzamosító kódot forrás -> forrás transzlációval bele lehetne injektálni egy tisztán funkcionális kódba.
    Mutasd a teljes hozzászólást!
  • Akkor meg pláne nem értem mi tarthat 4 napig egy pár kilobájtos ROM fordításában.


    Az én sem értem.
    Nem is csináltam olyat.

    Viszont 120000000 logikai kapu szintetizalasahoz nagyon sok ido kell.
    Optimalizalshoz le sem tudom irni, hogy a forditonak hany kapcsolatot kell ellenorizni.

    Ha meg hozza vesszuk, hogy ezeket a kapukat kb 1000000000 tranzisztorra kell implementalni, az még jó pár nap.
    Mutasd a teljes hozzászólást!
  • Amúgy, ha már a párhuzamosítás és a számtalan magra történő fejlesztés témája került előtérbe, nekem is van egy a témába vágó ötletem.

    A lényeg szerintem a funkcionális nyelvek alaklmazása. A tiszta funkcionális nyelvekben minden függvény mellékhatás nélküli, ami azt jelenti, hogy a függvény eredménye (visszatérési értéke) nem függ semmi mástól, mint a paramétereitől, és az adatok (pl. argumentumként kapott objektumok) módosítása semmilyen formában sem lehetséges. Ez a gyakorlatban azt jelenti, hogy nincsenek sem értékadások, sem globális változók.

    Mivel nincsenek globális változók és egy függvény számára elérhető memóriaterület csak olvasható, ezért teljesen mindegy milyen sorrendben hajtuk őket végre, sőt, még akár párhuzamosan is futtathatóak, és ehhez nem szükséges semmilyen plusz információ vagy tevékenység (pl. szálak létrehozása) a program írójának részéről. A párhuzamosítás teljesen transzparens módon megoldható a fordító (értelmező) számára.

    A funkcionális nyelvekben írt kódok futtatásához tipikusan virtuális gépek szükségesek, és ezek a virtuális gépek már (elméletileg) megírhatóak úgy, hogy a kód futtatása során az aktuálisan elérhető összes processzormagot használják. Ezáltal egy ilyen funkcionális nyelven írt kód teljesen transzparens módon párhuzamosítható, ami egy hatalmas előny az imperatív programozási nyelveken írt programokkal szemben.
    Mutasd a teljes hozzászólást!
abcd