| Témaindító hozzászólás: |
| Sziasztok! Sokat gondolkodtam, hogy nyissak-e egyáltalán emiatt egy új topikot, mivel a témával kapcsolatosan már van egy halom topik itt a Prog.Hu-n, de úgy döntöttem, hogy elméletem indoklásához új topik kell, mert igazából egyik korábbi topikba sem való. Ha mégis azok valamelyikében lett volna a helye, akkor előre is bocs érte... Szóval a topikom témája a párhuzamos végrehajtásra alkalmas programok készítése. Erről ugye tudjuk, hogy ma már egy halom módszer létezik, amivel.. |
| videotunes válasza real_het (15:12) hozzászólására | előzmény | privát | 2012.10.09. 23:43 | válasz |
| ma kiosztották a Nobelcsontot, fogadnom kellett volna rájuk bazz!!! kvantumbit=qubit értékét egy atom, kvantumállapota őrzi. A qubit értéke lehet igen vagy nem, de felvehet szuperpozíciót is, amelyben egyszerre van az igen és nem állapotban. (így a bemenet az összes lehetséges állapot szuperpozíciója, akkor a kvantumprocesszor párhuzamosan, egy lépésben képes kiszámolni az összes lehetséges kimenetet) Két bit hosszú bemenet például négy állást vehet fel, ezek a következők: 00, 01, 10, 11. A variációk száma minden további bit hozzáadásával megduplázódik: tehát n darab bit esetében 2 az n-ediken féle bemenet lehetséges. arányok: a hagyományos bitekből 300bit csupán arra alkalmas, hogy pár sornyi szöveget tároljatok benne, de 300qubit be annyi adat fér el körülbelül mint ahány atom van a világegyetemben. ha egy 300 kvantumbites kvantumregisztert a ma szimulálnál, akkor annak memóriaigénye kettő a háromszázadikonnal lenne arányos, ami több, mint az atomok száma az Univerzumban.... szemléletváltás itt: http://www.nobelprize.org/nobel_prizes/physics/laureates/2012/  | |
| videotunes | privát | 2012.08.15. 14:59 | válasz |
| http://graphics.pixar.com/opensubdiv OpenSubdiv is a set of open source libraries that implement high performance subdivision surface (subdiv) evaluation on massively parallel CPU and GPU architectures. bővebben: http://fabricengine.com/2012/07/subdivision-surfaces-using-map-reduce-and-the-gpu-with-the-fabric-engine-creation-platform/ (eredeti modell poligonszámát drasztikusan nem növelő eljárás) Subdivision level 1 (50k triangles): - Softimage: 10 fps - Maya SmoothProxy: 28 fps - Fabric Engine on CPU: 60 fps - Fabric Engine + GPU: 273 fps Subdivision level 2 (200k triangles): - Softimage: 5 fps - Maya SmoothProxy: 9 fps - Fabric Engine on CPU: 23 fps - Fabric Engine + GPU: 95 fps Subdivision level 3 (800k triangles): - Softimage: 2 fps - Maya SmoothProxy: 2.5 fps - Fabric Engine on CPU: 6 fps - Fabric Engine + GPU: 29 fps | |
| videotunes | privát | 2012.05.25. 00:42 | válasz |
| http://www.cs.rice.edu/~sc40/pubs/oopsla09.pdf | |
| kpocza válasza nagya73 (01:50) hozzászólására | előzmény | privát | 2012.05.24. 23:23 | válasz |
| Az oprendszer ugyanis saját maga dönti el, hogy az n szálat elindító alkalmazás terhelését hogyan is osztja el a processzorok között, az alkalmazásnak erre nincs befolyása. Van. Thread affinity mask a neve. Ha low level megyünk. Különben valóban nincs. Ez természetesen nem feltétlenül és minden gépre igaz, de van ilyen és ezt a viselkedést szoftverből, előre megmondani lehetetlen. Mi volt a platform, a feladat valamint a megoldás ami azokat a mutatókat produkálta, amit írtál (és nem idéztem be szó szerint)? | |
| Madamm | privát | 2012.05.23. 20:29 | válasz |
| Egy érdekes nyelv érdekes lehetőségekkel: Oxygene http://wiki.oxygenelanguage.com/en/Asynchronous_Statements http://wiki.oxygenelanguage.com/en/Parallel_Loops http://wiki.oxygenelanguage.com/en/Futures  | |
| nagya73 válasza Banderasz (08:06) hozzászólására | előzmény | privát | 2012.04.26. 01:50 | válasz |
| "Ha ezt a felhasználónak kell eldöntenie, akkor már régen rossz az egész" - sőt, még rosszabbat mondok. Az oprendszer ugyanis saját maga dönti el, hogy az n szálat elindító alkalmazás terhelését hogyan is osztja el a processzorok között, az alkalmazásnak erre nincs befolyása. Tehát ha n processzor van a gépben, és az akármilyen program n szálat is indít (gondolván, hogy így mindent kihasznál), az még egyátalán nem biztos, hogy azok mind fizikailag is külön fognak futni. Ez csak egy kérés az alkalmazástól, amit majd valahogy teljesítenek. És akkor nem beszéltünk a konkrét hardverfelépítésről, ahol pl. a memória egyértelműen szűk keresztmetszet, és ezen keresztül az egyébként külön processzoron futtatott szálak simán akadályozzák egymást. Konkrét (=adott) gépi eredmények: teljesen szétosztott (független memóriaterületeket használó) szálak dolgoznak, a legjobb eredményt mégis az egyszálú beállítás hozza, a szálak növelésével (és a feldolgozandó adatok ennek megfelelő felosztásával) a teljes futás ideje nő! (~arányosan, azaz minél több szál, annál rosszabb idő) A processzorterheléseken látszik is, hogy nem futnak 50% fölé, és ez még nem is mind a felhasználói (feldolgozói) terhelés. Ez természetesen nem feltétlenül és minden gépre igaz, de van ilyen és ezt a viselkedést szoftverből, előre megmondani lehetetlen. | |
| real_het válasza Banderasz (08:06) hozzászólására | előzmény | privát | 2012.04.13. 15:12 | válasz |
| Nade amellett, hogy mindannyiotok a klasszikus SISD-ben gondolkodik, csak nem megyek el szo nelkul :D En mostanaban az uj radeonra akarom feltuningolni a pas scriptemet, de nemhogy arra torekednek, hogy intelligens legyen a pas->asm atalakitas, hanem a 'nyelvet' csak arra hasznalom, hogy egyszerubben meg tudjam adni vele explicit modon a muveleteket és NE GONDOLKOZZON helyettem (ugysem tudna lol). Ilyesmi extra dolgok vannak, amire automata compiler legyen a talpán, ami leforditja a high level kodot optimálisra: - SIMD kőkeményen: 1 thread ugyanolyan lassu, mint 64 thread. (sőt az uj NVidianal asszem 192 az alap:D) - kétféle processzor/instruction set: Van egy int/int64/float/double a vektor ALU-knak es van egy kisebb utasitaskeszlet a vezerlo/konstans_olvasó feladatot ellátó int/int64 (64bit cimzes miatt) skalár ALU-nak. (64 vektorosra jut 1 skalár alu) - 4 darab ALU(simd16)/MemoryRead/MemoryWrite/ConstantRead/InstructionD - olyan szintu parhuzamossag van, hogy 8192 (32bites)thread kell egy idoben, hogy maximalisan ki legyen hasznalva minden ALU a GPU-n. - Egy rakás extra utasitas, amelyeknek a kitalalasakor kizarolag bizonyos feladatok maximalis tamogatasa volt a szempont es legutoljara az, hogy azokat az utasitasokat egy 'emberi' nyelvrol egy automata compiler le tudja forditani. peldaul: abszolut kulonbsegek osszege akkumulálva azaz: v_sadaccum_u8 dest,src0,src1,src2 //mind 32bites reg dst=src2;for i in[0..3] d+=abs(src0.byte[másik kedvenc: a carry-s osszeadas: v_addc_i32 dst, sdst, src0, src1, ssrc ahol dst, src0, src1 int[64] arrayok sdst, ssrc pedig 64bites skalar regiszterek (1 bit jut egy int-re) mukodese: sdst=0;Ebbe gondolj bele, hogy milyen jol lehet ezzel bigint osszeadasokat darálni, viszont magas szintu nyelven még ráutaló magatartassal sem nagyon lehet jelezni a forditonak, hogy ezt a nyakatekert utasitast kerjuk szepen felhasznalni :D En amondója vagyok, hogy minel nagyobb teljesitmenyu a hardver, annal inkabb nyakatekertebb is lesz a mukodese. A memoria iras olvasas az kimaradt :D - Arra van egyreszt egy utasitas, hogy 'olvass 1,2,4,8 vagy 16 dwordot innen es onnan'. Na ez nem azonnal olvas, hanem csak beirja a feladatot egy queue-ba. - Es van egy wait utasitas, ami mindaddig várni fog, amig a fenti memIO parancsokbol mar csak megadott számú van egy queue-ban. Ezek olyan bonyolult dolgok, hogy az idealis kihasznaltsaghoz minel inkabb explicit modon kell programozni, mert mar eleve az input adatok sorrendjere, egymashoz kozelisegere es alignoltsagara is gondolni kell, kulonben jon mindenfele stall :D Az a tobb teraflops szamitasi kapacitas, ami befér egy PC slot-ba a nem olyan, mint egy nagy zsák x86 processzor, amik mind kulon dolgoznak egy végtelen nagy sávszélességű közös memóriából  "Például egy olyan játékprogramban, amely a felhasználó elé tárt virtuális teret menet közben tölti be annak függvényében, hogy a felhasználó éppen merre jár a virtuális térben." Egy ilyen ujdonsagot lattam (image), hogy terabyte méretű virtualis textura elérés. Azaz definialva van egy hatalmas meretu virtualis textura, amibol csak X darab blokk van tarolva a GPU-ram-ban, (mintha egy google map tile cache lenne), es amint ebbol a texturabol olyan teruletre van szukseg, ami nincs feltoltve a GPU-ram-ba, már megy is az interrupt a CPU-nak, ami az adott blokkot aztan beolvashatja winyorol, vagy akarmilyen modon le is generalhatja. Sztem 15 ev alatt ket nagy ugras volt a teljesitmenynovekedes szempontjabol: 1. elfogyott a maximum GHz -> emiatt legyen tobb fuggetlen processzormag! 1b. Bizonyos reszeket osszunk meg 2 mag kozott es akkor nem kell annyi tranzisztor (hyperthreading) 2. tul sok a tranzisztor es keves a teljesitmeny -> jusson aránylag több muveletvegzo (TFlops) kevesebb vezérlőre/memoria savszelre! A 2.-es pont az nagyon megneheziti a magas szintu "paralell foreach()" hatekony megvalosithatosagat. Szoval minel tovabb halogatjuk ennek a paralell nyelvnek a kifejleszteset, annal nehezebb lesz azt megirni az aktualis hardverre  end of novella  | |
| Banderasz válasza nagya73 (01:09) hozzászólására | előzmény | privát | 2012.04.03. 08:06 | válasz |
| "- szálak száma (azért én nem feltétlenül terhelnék le mindig mindenkit egy gépen)" Ha ezt a felhasználónak kell eldöntenie, akkor már régen rossz az egész. De az a poén, hogy még csak nem is a programozó dolga, hogy eldöntse. Hiszen az, hogy éppen egy adott pillanatban hány szálon fut a feldolgozás, az egy sor olyan körülménytől is függ, amit nem lehet előre leprogramozni. Például ha egy hordozható eszköz éppen energiatakarékos módban van, akkor ott nem a sebesség, hanem a hosszú akkumulátor-élettartam a fontosabb, így célszerű azt alig néhány szálon futtatni, a kisebb energiafelhasználás érdekében. Egy másik példa még erre az, hogy mi van akkor, ha a user csak sakkozik a gép ellen, de eközben vagy 90%-on terheli az összes CPU(mago)-t egy háttérben futó videokonvertálással. Ilyenkor a sakkprogram MI logikája hány szálon fusson? Na látod, nem tudod előre, programozás során ezt meghatározni. Mindezekből egyértelműen következik, hogy az, hogy egy program egy adott időpillanatban hány szálon dolgozik, azt nem maga a program kell, hogy eldöntse (a programozó előzetes tervezése és implementálása alapján), hanem a futtató környezet kell, hogy eldöntse, hiszen pont az az a háttérszoftver, ami tisztában van az aktuális beállítások szerinti erőforrások ideális kihasználhatóságával. A program max annyit tehet meg, hogy meghatározza, minimum hány szálon kell futnia, de a futtató környezet által ez is virtualizálható a program részére még akkor is, ha valójában csak egyetlen végrehajtó egység áll rendelkezésre (az ütemező ettől még működik). "- a részfeladatok mérete (jobb híján task-granularity). Éppen az a lényeg, hogy bizonyos "felbontás" alatt nagyon megnő a hasznos számításokhoz viszonyított koordinációs overhead (sőt, probléma lehet egy rossz szervezésnél az is, ha a részfeladatok túl gyorsan befejeződnek - könnyen maradhatnak kihasználatlan erőforrások)" Nyilván a "task-granuality" információ a futtató környezet számára, mely infót a fordító elhelyezhet minden rutinról a tárgykódú programba. Így a futtató környezet tudja, hogy egy adott, sok adaton dolgozó rutint a GPU-n futtasson le sok 100 szálon, vagy a CPU-n egyetlen szálon. Ráadásul a fordító által adott granuality nem biztos, hogy egyenesen arányos a rutin futási idejével, így a futtató környezet egyszerű statisztikai alapon módosíthatja a natív futtató hardver környezetet (CPU/GPU/number of threads), valamint az adott taszkra (melyben a rutin fut) dinamikusan szabályozhat prioritást a CPU időből. Ebből is látszik, hogy az aktuális környezet még ilyen esetben is erősen befolyásolhatja a futtatás mikéntjét annak ellenére, hogy a programozás során ez lehet, hogy nagyon eltérő jövőképet mutat egy adott rutin futtatására. A másik meg hogy az esetlegesen keletkező holt időket is ki tudja használni a futtató környezet mondjuk arra, hogy a programban egy nagy valószínűséggel a közeljövőben futtatásra kerülő rutint a háttérben lefuttassa (csökkentett prioritással), amennyiben ahhoz a szükséges adatok (paraméterek) is rendelkezésre állnak, és nem függ annak futtatása egy még be nem következett eseménytől. Az így előre lefuttatott rutin által módosított összes változást a futtató környezet virtualizálja a rutnin számára, amely eredményeket már csak a valódi célhelyükre kell másolni, ha a futtatás valóban bekövetkezik. És hogy miben hasznos ez? Például egy olyan játékprogramban, amely a felhasználó elé tárt virtuális teret menet közben tölti be annak függvényében, hogy a felhasználó éppen merre jár a virtuális térben. Ilyenkor nagyon zavaró tud lenni, hogy közepesen gyenge vason érezhetően megakad a játék, mialatt dinamikusan betölti az új adatokat. Ám ha egy a fentebb írt előbecslő módszerrel működő futtató környezet már előre lefuttatja az adatok betöltéséért felelős rutint, akkor mire a játékos a helyszínre ér, már nem kell azokat betölteni, hanem csak max. a VRAM-ba másolni. És vedd észre, hogy ilyen előbecslő logika ma már minden CPU-ban adott, de az csak utasításszinten igyekszik a becsléssel hatékonyabban kihasználni a CPU végrehajtó egységeinek képességeit, míg a futtatókörnyezetbe helyezett előbecslő sokkal magasabbról tekint a programra, azaz a program üzleti logikájához sokkal közelebb álló relevanciával tud megbecslést végezni, hisz nem utasításszinten veszik el a részletekben, hanem programlogika követésével sokkal messzebbre előre láthat. A lényeg tehát az, hogy a párhozamos futtatást lehetővé tévő hardver már rég rendelkezésre áll, már csak egy olyan futtatókörnyezet illetve ehhez passzoló programozási nyelv kell, amely már eleve ezzel a párhozamos felfogással áll elő. A programozó látszólag csak a tiszta üzleti logikát programozza le, ráadásul látszólag azt is sorosan, de a programja a lehetőségekhez mérten (hardver, futtatókörnyezet-ütemező, szabad memória, redszerbeállítások) a lehető legtöbb szálon, párhuzamosan fut. Valahogy úgy kell ezt elképzelni, mintha csak egyetlen progresszor(mag)ra készülő szekvenciális programot írnánk, mivel a valóban rendelkezésre álló fizikai párhuzamosság teljesen el van virtualizálva. A programozáskor viszont már tisztában kell lenni vele, hogy a programunk valahány szálon, de párhuzamosítva fut, így eleve a programozási nyelvnek is erre a párhuzamos hozzáállásra kell alapoznia. Hát nem tudom, mennyire magyaráztam félre a dolgot, de bizony eléggé nehéz megmagyarázni olyasmit, ami még nem létezik... | |
| nagya73 válasza Banderasz (10:05) hozzászólására | előzmény | privát | 2012.04.03. 01:09 | válasz |
| "eleve a párhuzamos feldolgozás legyen az adott" - gratula, feltaláltad az analóg számítógépet. A digitálisakat nagyrészt éppen azok hibái miatt találták ki okos emberek. Amúgy két alapvető paraméter minden párhuzamos (alkalmazás)architektúrához szükséges: - szálak száma (azért én nem feltétlenül terhelnék le mindig mindenkit egy gépen) - a részfeladatok mérete (jobb híján task-granularity). Éppen az a lényeg, hogy bizonyos "felbontás" alatt nagyon megnő a hasznos számításokhoz viszonyított koordinációs overhead (sőt, probléma lehet egy rossz szervezésnél az is, ha a részfeladatok túl gyorsan befejeződnek - könnyen maradhatnak kihasználatlan erőforrások) Ezeket egy rendszer belülről soha nem fogja tudni megmondani (az első is csak triviális, de nem biztos, hogy "jó") és még kívülről sem mindig mondható meg pontosan ("optimálisan") - ezért minden ilyen megoldás előzetes tervezést igényel (legalább lesz munkánk...) | |
| simi.2 válasza Banderasz (10:05) hozzászólására | előzmény | privát | 2012.03.19. 09:12 | válasz |
| a probléma a "legyen a párhuzamos feldolgozás az alap"-pal az, hogy nagyon nehéz átlátni egy párhuzamos futást, ha abban mellékhatások is vannak. még egy egyszerű, egyszálú futásnál is vannak olyan fejlesztők, akiknek feladat átlátni a kód hatásait (tudományosan: elő- és utófeltételeket, invariánsokat, gyakorlatban: jó unit teszteket csinálni). pedig itt a bonyolultság csak a sima ciklusokból, elágazásokból meg a függvényhívásokból adódik össze, semmi extra nincs benne. párhuzamos feldolgozásnál viszont bejön az ütemezés és a különféle erőforráselérési stratégiák is. az ütemezésre semmilyen behatásunk nincs, azt majd az oprendszer eldönti hogy melyik szálak milyen ütemben hajtják végre az utasításaikat, emiatt aztán az összes lehetséges variációra fel kell készülni (tesztelni pedig gyakorlatilag lehetetlen). ez nem megléphetetlen dolog, csak épp nem olyan egyszerű, hogy minden programozó csak úgy csuklóból meg tudja lépni. | |
| Stampi válasza Banderasz (10:05) hozzászólására | előzmény | privát | 2012.03.12. 13:39 | válasz |
| Én is nagyon soros gondolkodású vagyok. Azok a feladatok, amikkel foglalkoztam, azok nem voltak nagyon párhuzamosíthatóak, és amíg csak egy végrehajtó egység volt, addig nem volt nagyon értelme a párhuzamos munkának. A való életben a tevékenységek párhozamosan folynak. Az emberek egymással párhuzamosan végzik a munkájukat, ami azt is jelenti, hogy sokszor egymásra kell várni (ami kieső kapacitást jelent), sőt az is lehet, hogy az egyik gátolja a másik tevékenységét.  | |
| Banderasz válasza Stampi (23:08) hozzászólására | előzmény | privát | 2012.03.12. 10:05 | válasz |
| Az emberi (programozói) gondolkodást nem váltja ki a pure paralell computing. Nem is válthatja ki, hiszen akkor már nem is lenne szükség programozóra; a fordító maga találná ki a feladat megoldását. A normalizálós példát csak azért hoztam fel, mert az tipikusan pont egy olyan gyakorlatias példa, amely adja magát, hogy párhuzamosítsunk. De lehetne képfeldolgozás is, vagy adatbázisban keresés is, stb.. Ezek közös tulajdonsága, hogy rendszerint pontosan ugyan azt a feladatot kell elvégezni sok-sok adaton, ahol a részműveletek nem-, vagy nem számottevő mértékben függenek egymás eredményeitől. Véleményem szerint az ilyen feladatok elvégzésére nyelvi szinten kellene hogy biztosítva legyen a párhuzamos feldolgozás, azaz a programozónak ne kelljen gondoskodnia a többszálúságról, hanem csak tisztán az üzleti logika leprogramozásával (vagy max. a többszálúság inicializálásával ha szükséges) kelljen foglalkoznia. Erre már legalább egy tucat különböző próbálkozás van osztálykönyvtárakkal vagy itt-ott már nyelvbe épített fícsőrökkel, de szerintem ezt igazán hatékonyan csak úgy lehetne véghez vinni, ha már eleve párhuzamos feldolgozás az adott alap környezet, ami alól a jelenlegi módszerekkel ellentétben csak akkor kell eltérni (szekvenciálissá alakítani), ha azt az üzleti logika megköveteli. Vagyis: Jelenleg úgy programozunk, hogy alapból a soros működés az adott, és ilyen-olyan módszerekkel külön párhuzamosítunk, ha az kihasználható. Ez nem jó, ezt kell megfordítani, azaz eleve a párhuzamos feldolgozás legyen az adott, és külön programozni csak a soros működést kelljen, de azt is csak akkor, ha a fordító- vagy/és futtató környezet által nem lehet egyértelműen eldönteni egy adott műveletről, hogy az függ-e más műveletek eredményeitől és esetleges explicit szinkronizálásoktól. Na erre értem én azt, hogy a párhuzamos programozás szemléletváltással jár. | |
| Stampi válasza Banderasz (18:00) hozzászólására | előzmény | privát | 2012.03.11. 23:08 | válasz |
| WAVE normalizáláshoz. Valamikor írtam egy programot, ami normalizálni akart. Mikor futtattam, azt láttam, hogy a fájlban vannak a maximális értékhez közeli értékek, így azután nem volt mit normalizálni. Ebbe azért nem nyugodtam bele. Készítettem egy hisztogramot a fájlban található értékekből, és azt találtam, hogy a kiugró értékekből nincs sok. Így a hisztogram alapján húztam meg a határt, ami feletti értékeket egyszerűen zavarnak tekintettem, és ezután normalizáltam. Miért írtam ezt. Azért, mert én úgy gondolom, hogy az emberi gondolkodásra szükség van. | |
| axon01 válasza Banderasz (17:39) hozzászólására | előzmény | privát | 2012.02.29. 19:35 | válasz |
| Értem amit mondasz egyébként. Csak mint láthatod a programozók (többsége) nem képesek a szemléletváltásra. Maradnak inkább a régi jól bevált módszereknél. | |
| Banderasz válasza axon01 (16:25) hozzászólására | előzmény | privát | 2012.02.29. 17:39 | válasz |
| Egyelőre csak írásban (itt a fórumon) halt meg, de én ettől még sokat agyalok a dolgon. Valahogy ezt a témát nem tudom kiverni a fejemből, pedig naponta millió más dolgom is van, mégis nap mint nap elmélázok rajta... | |
| videotunes válasza real_het (00:00) hozzászólására | előzmény | privát | 2012.01.15. 21:48 | válasz |
| http://www.youtube.com/watch?v=rUWfod_8JsM&feature=relmfu | |
| videotunes válasza real_het (00:00) hozzászólására | előzmény | privát | 2012.01.15. 21:45 | válasz |
| http://www.youtube.com/watch?v=rUWfod_8JsM&feature=related http://www.youtube.com/watch?v=YgFVzOksm4o&feature=related http://www.youtube.com/watch?v=VyX8E4KUkWw http://www.youtube.com/watch?v=DNatzhe4BoQ&feature=related http://en.wikipedia.org/wiki/Quantum_computer | |
| nadamhu válasza tisn (10:42) hozzászólására | előzmény | privát | 2011.12.07. 10:52 | válasz |
| Fénykorában már működgetett, volt egy-két tucat ügyfél is, aki megvette a desktop applikációt, de amikor jött a google fordítóprogramja, akkor feladtam a projektet. Túl sok munka volt ez egy embernek nagyon lassú látványos eredménnyel. | |
| tisn válasza nadamhu (11:23) hozzászólására | előzmény | privát | 2011.12.07. 10:42 | válasz |
| Off a gepi ferditoprogram prodzsektel mi lett? | |
| Doi válasza Banderasz (18:00) hozzászólására | előzmény | privát | 2011.11.16. 16:12 | válasz |
| Eredményesnek tűnik az adatokból kiindulni. Mármint sok esetben elég lehet az, ha van néhány alap függvény-típus: Unary = fucntion( X ): Xés egy "párhuzamos tömb" típus különféle műveletekkel: ParVector = (Így a legnagyobb abszolútértékű elem egy Assoc művelettel, a skálázás egy ForEach művelettel elvégezhető. És akkor a ParVector okosítható fel úgy, hogy mondjuk processzor-szám alapján eleve darabokra vágja a teljes készletet, egyszerű (byte, word) alaptípus esetén pedig mondjuk vektorműveleteket (is) használ. Kérdés, hogy ez mekkora tészét fedi le a párhuzamosításra érdemes feladatoknak. | |
| real_het válasza Banderasz (18:00) hozzászólására | előzmény | privát | 2011.11.14. 20:11 | válasz |
| Pillanatnyilag nem tudom megmagyarazni, de ugy erzem ez egy kicsit santit: A feladat az memoriapakolas szempontjabol 2 reszre bonthato: 1. gather jellegu resz, amikor x darab clusterre kell particionalni a feladatot, azokat paralell modon elvegeztetni, vegul a keletkezett reszeredmenyekre is alkalmazni ezt a spec. max keresest. 2. full paralell rész, amikor egy array-t megszorzunk egy konstanssal, na ehhez nem kell sok ész, de az 1. az sántít. var UInt16[1] MaxValue = 0;Ebbol az remlik, hogy Buffer.Left az egy array (en inkabb igy hivom, mert en is belehulyulok :D vagy lehetne vektor is). Az tiszta sor, hogy |Buffer.Left| az adodik az array osszes elemere vegrehajtott abs muveletbol. (amugy jo otlet! :D A compilerbe konnyen beepitheto a zarojelezes specialis eseteként) Viszont az a felteteles ertekadás, na az necc :D A array>skalar oreratort te hogy ertelmezed? Es miert pont ugy? :D Mert ugye mi van akkor, ha azt szeretned megallapitani, hogy van-e 1 olyan elem az arrayban, ami nagyobb a skalarnal? Arra probalok itt utalni, hogy az AND meg az OR egyenranguak, mikor melyikre lehet szukseg. Aztan tegyuk fel, hogy el lett vegezve az (|Buffer.Left| > MaxValue)feltetel es igazat adott, mert |Buffer.Left| barmelyik eleme nagyobb, mint MaxValue. Ekkor a THEN utani MaxValue = |Buffer.Left|; ertekadas honnan fogja tudni, hogy az skalar MaxValue-be a |Buffer.Left| array legnagyobb erteket irja? Ertekadas muvelet, bal oldalon skalar, jobbra array -> necc :p Tehat ez a gather muvelet ez nem kerek :D Ezt GPU-n pl bin fa vagy piramis szeru alakban (2d inputtal) ossze lehet hozni, de oda irni is kell :D Ha pedig a maxvalue valoban az egez program alatt 1 peldanyban letezik, akkor a szinkronizalni kell azt a thread-ek kozott -> qrvanagy penalty. Szoval a ketseges, nemtrivialis: - if - scalar [ertekadas] array - array > scalar {nalam ez egy boolean array-t produkal, az trivialisnak tunik, de nem gather-ezik} Ami állat: - scalar x array, array x scalar, array x array(ugyanakkora arrayok) alapmuveletek megvalositasa. //pelda array x array-ra es array x scalar-raHa az IF-en agyalunk: A fenti logikaval (1,2,3,4,5)>3 az visszaad (false,false,false,true,true)-t. Az uj vektoros IF-et fel kéne erre készíteni, de hogy a then utan kovetkezo reszleges ertekadassal mi lenne o.O Persze az is lehet, hogy nem ertem az altalad elkepzelt IF-et. Tovabbi jo agyalgatást :p Majd vmikor kiprobalom, hogy ez a wavnormalizalo mennyivel gyorsabb akkor, ha parhuzamos multimedia utasitasokat hasznalunk. Sztem minimum 10x, de ki tudja, lehet, hogy memory bottleneck van (foleg a szorzasnal). A kod viszont tuti, hogy 10x gusztustalanabb lesz, még a hagyomanyos, nem parhuzamos alaknál is | |
| Banderasz válasza Benjy (18:36) hozzászólására | előzmény | privát | 2011.11.14. 18:48 | válasz |
| Ebben igazad van, csak megmondom őszintén, hogy a halmazt, mint objektum-struktúrát azért emlegettem, mert nem találtam megfelelőbbet helyette. Persze a halmaz megnevezés nem jó, mivel egy halmazban nincsenek definiálva az elemeinek sorrendje, amire nagyon is szükség lehet, szóval a halmaz nem jó elnevezés. A lista jobb, de ennek hallatán a programozók hajlamosak egy TList() osztály belső működésére asszociálni, ami csak megzavarna, hiszen egy szóval sem mondtam, hogy egy objektum minden eleme ne lenne tömören egyben kezelve (azaz nincs mutató az előző/következő elemre, mivel azok szorosan egymást követik, ideális aligment-tel). De amúgy jogos... | |
| Benjy válasza Banderasz (18:00) hozzászólására | előzmény | privát | 2011.11.14. 18:36 | válasz |
| Első gondolatom, hogy halmazok helyett listákat kéne használni, de jobban még nem gondoltam át Hisz akkor halmaz + halmaz nem valami értelmes művelet (a halmazok összevonásán kívül) de a lista+lista (minden azonos indexen lévő tagot a másik list indexen lévő tagjával) szerintem jobban ki lehet használni a párhuzamosságot. | |
| Banderasz | privát | 2011.11.14. 18:00 | válasz |
| Na végre van egy kis időm leírni, mit is akartam... A lényeg bemutatására vegyünk egy gyakorlatias példát, méghozzá azt, hogy adott egy 44.1kHz-es mintavételezésű, 16 bites, előjeles egészeket tartalmazó, sztereó hang, MS-WAVE formátumban, melyet mondjuk le kéne normalizálnunk 95%-ra. Aki nem értené mi is az a normalizálás: Biztos tapasztaltad már azt a kellemetlen jelenséget, hogy ha összeválogatsz egy audio CD-nyi zenét, kiírod, majd meghallgatod, akkor elég bosszantó tud lenni, hogy szinte ahány zene, annyiféle hangerővel szólalnak meg azok. A normalizálással azt érjük el, hogy minden egyes CD-re írandó zenének a hangerejét egyformára állítjuk, így kiírva azt, élvezetes lesz visszahallgatni. Természetesen minden valamire való CD-író program már automatikusan megcsinálja a normalizálást, de most tételezzük fel, hogy a mi programunk mégsem csinálja ezt meg, így nekünk kell előre gondoskodni a hanganyag hangerőinek kiegyensúlyozottságáról... Legyen az egyszerűség kedvéért a munkafájlunk előre meghatározva, "proba.wav" fájlként, valamint szintén az egyszerűség kedvéért feltételezzük, hogy az egész fájl egyben belefér a memóriába. Először nézzük, hogy ezt szekvenciális programvégrehajtás esetén (1 szálon) hogyan végeznénk el: // Egy adott sztereó hangminta definíciójaTermészetesen bőven volna még mit optimalizálni a kódon, és persze nem ártana bele kivételkezelés is, de itt most az egyszerűség jegyében szándékosan kihagytam ezeket, illetve nem próbáltam ki, ez csak amolyan elméleti kód, és nem lehetetlen, hogy még hibás is. Ha igen, bocs. Mindenesetre a lényeget jól mutatja: A kód nagyon messze áll attól, hogy csak az üzleti logikát tartalmazza, főleg, ha még az egyszálú végrehajtást le is párhuzamosítanánk. A kivételkezelés még tovább bonyolítana, a többszálúságban a szinkronizáció meg főleg (bár itt nem nagyon van szükség adatok megvárására). És most akkor először kommentár nélkül, én így képzelem el ezt a feladatot elegánsabban, szebben, egyszerűbben sőt, alapozva arra, hogy eleve párhuzamosan fut a programom: sokkal hatékonyabban(!): // Egy adott sztereó hangminta definíciójaMagyarázat: Talán két dolog van, ami szembetűnő, és talán elsőre érthetetlen. Az egyik az, hogy a System.Abs() hívást lecseréltem a matematikában is használatos abszolútértékes párra (pl.: "a = System.Abs(a);" helyett "a = |a|;"). Ez egty egyszerű egyoperandusos operátorként van definiálva, ami ugyebár nem más, mint egy egyoperandusos függvény. Szerintem ez nem szorul részletesebb magyarázatra. A másik meg az, hogy a "Buffer" létrehozásakor meg van adva, hogy a "Buffer" nevű objektum kezdőérékei a "proba.wav" fájlban találhatók, 44 bájtos offszettől kezdve. Ez elsőre csak formai egyszerűsítésnek tűnik, de valójában nem csak az. Ugyanis mint azt korábban mondtam, egy azonosítóval ellátott objektum (ez esetben "Buffer") nem csak egyetlen adatra hivatkozik, hanem egy halmazra. Mivel a deklarációkor kezdőértéket meg lehet adni, így én megadtam neki, hogy a kezdőérték a fájlban van. Ezzel tulajdonképpen azt adtam meg, hogy a "Buffer" forrása hol van. Mivel nyelvi szinten meg kell adni az objektumok forrását, így talán érthető, hogy miért nincs fájlkezelés a kódban. Ugyanis mivel a "Buffer" forrása a "proba.wav"-ban van, így természetesen az adatok visszaírása automatikusan megtörténik a fájlba, hiszen logikusan azoknak ott van a helye. Ez egyben lehetőséget ad a fordítónak arra, hogy belső bufferkezelést végezzen, amely által így nincs szükség ponter-ezére sem (azaz sokkal nehezebb elrontani). A futtató környezet meg a pillanatnyi erőforrásokhoz mérten a lehető legoptimálisabban választhatja meg a buffer méretét (kevés szabad memória esetén lapozással). Ami nagyon fontos az az, hogy a "Buffer" egy halmaz, így mivel párhuzamos szemlélet szerint működik a program, érthető, hogy egyetlen feltétel (illetve egyetlen értékadás is) valójában az egész halmazra (pontosabban a halmaz aktuális értékkészletére) vonatkozik. Ezért nincs szükség még ciklusra sem, hiszen tudjuk, hogy a halmaz minden elemén végrehajtódik amit szeretnénk, ráadásul az aktuális lehetőségekhez mérten a legjobban párhuzamosítva. Ezért a forráskódban tényleg csak az üzleti logika van, minden más "sallang" kikerült belőle. Hát kell ennél hatékonyabb eszköz? Fel lehetne tenni a kérdést, hogy a "MaxValue" halmaz miért van kötelezően 1 eleműnek deklarálva? A válasz pedig az, hogy azért, mert így tényleg csak egyetlen elem kerül mindig bele felülírásal, nem másolódik át a teljes "|Buffer.Left/Right|". Ebből pedig következik, hogy ha egy objektumnak nem adjuk meg fixen az elemszámát, akkor az dinamikusan kezelődik, ha meg megadjuk, akkor meg az kötelezően annyi elemű halmazt jelent, amennyit megadtunk. Az érthetőség kedvéért: Ha a "MaxValue"-t mondjuk 3 eleműnek adtuk volna meg, akkor a ">" operátorral megadott feltételvizsgálat mindig 3 elemre vonatkozna, ahol a feltétel csak akkor teljesül, ha mind a 3 elem nagyobb. És persze az értékadásnál is a feltételben éppen vizsgált 3 elem másolódna át. Nos, valahogy így képzelem én azt el, hogy szemléletváltás. A párhuzamosság tudatában eleve halmazokkal kell gondolkodni, nem csak egyetlen objektumokkal. Maga a nyelv is már eleme halmazfelfogásban lenne leírva, így például az operátorok meghatározásánál is így kell gondolkodni (és meg kell tudni adni azt is, hogy az adott operátor kommutatív-e, asszociatív-e, stb...). Na, elég meredek a dolog? | |
| NevemTeve válasza nadamhu (10:50) hozzászólására | előzmény | privát | 2011.11.14. 13:36 | válasz |
| Nagyon igaz. Szerencsére mindnyájan tudjuk miről van szó, de azért leírom precízen is, a jegyzőkönyv kedvéért: a matematikában véges sok szám összeadása tetszés szerint átrendezhető, az eredmény ugyanaz -- de a véges pontosságú lebegőpontos számok körében ez nem igaz. | |
| nadamhu válasza real_het (11:10) hozzászólására | előzmény | privát | 2011.11.14. 11:23 | válasz |
| "'egymasba agyazott'kommutativsag" jó, csak azért veszélyes (lehet) olyan fogalmakat használni, amelyeket nem definiálunk pontosan. Én amúgy a bináris operációkat egy gyurmából/drótból készült bináris faként szemléltetem magamnak. Ha egy művelet kommutatív, az azt jelenti, hogy a csomópontoknál vízszintesen tudok 180 fokos csavarást csinálni. Ebből: /\ezt: /\Ha asszociatív, akkor ugye azt a bonyolultabb átrendezést is meg tudom csinálni a fában, ami tetszőleges csomópontnál ebből: /\ezt csinálja: namost ha mind kommutatív, mind asszociatív, az a kánanán, akkor a fenti transzformációk sorozatával gyakorlatilag tetszőlegesen átrendezhető a fa, vagyis a résztvevő elemeket elég úgy felfogni, hogy bedobáltuk őket egy halmazba, oszt' jön majd az eredmény. Végülis igazad van, hogy ha mind az asszociativitás, mind a kommutativitás teljesül, azt hívhatnánk 'egymasba áagyazott kommutativitásnak' vagy esetleg szerintem találóbb 'n-operandusú kommutativitás'-nak (vagy 'operandus permutáció- függetlenségnek'). De a matekosok egyszerűen kommutativitásnak és asszociativitásnak hívják. | |
| real_het válasza nadamhu (10:50) hozzászólására | előzmény | privát | 2011.11.14. 11:10 | válasz |
| Legalább átismételjuk a matek szakzsargont, mielőtt szemléletváltunk Asszociativitaskent felfogva, a zarojelen belul legyen a sokezer 1e-10 kicsi ertek, es az adodjon a nagy 1e10 ertekhez. De 'egymasba agyazott'kommutativsagkent is, ok, mert csak a vegrehajtasi sorrendrol van szo, lenyeg, hogy a hasonlot a hasonloval muveleteket vegezzunk. (Ha már szemleletet valtunk :p akarok csinalni egy 2 szintu hierarhikus TObjectList-et az elozo exponencialisan novelt lista helyett. Kicsit lassabb lesz a select, de gyorsabb lesz az insert/delete a kevesebb mozgatas miatt. Remelem nem zsákutca, ez igy általános célra :D) | |
| lkedves válasza nadamhu (10:50) hozzászólására | előzmény | privát | 2011.11.14. 11:07 | válasz |
Bocs, igaz, ez az asszociativitás feliratú mellékvágány  | |
| nadamhu válasza real_het (10:56) hozzászólására | előzmény | privát | 2011.11.14. 11:06 | válasz |
| Te hajszálpontosan arról beszéltél, hogy miért kommutatív a cucc (a+b = b+a), ők meg hajszálpontosan arról, hogy miért nem asszociatív (vagyis 2-nél több elem esetén az eredmény függ a bináris operátorok végrehajtási sorrendjétől). Ugyan teljesen biztos vagyok ebben, hiszen ez fekete-fehéren jön a kommutativitás és asszociativitás definíciójából, de azért kerestem referenciát is: http://www.cs.uiuc.edu/class/fa07/cs498mjg/notes/floating-point.pdf Floating point operations lack several math properties. - Floating point operations are commutative - They are not associative or distributive: Floating point addition is not associative Floating point multiplication is not associative The distributive law between multiplication and addition does not necessarily hold. - If a + b = a, then b is 0, may not true with floating point operations | |