[Leni]

Ja es kotozkodni sem akarok mar, meg ertelme sincs, a radix az egy fuggveny. Nem hiszem, hogy ismerned, mi van mogotte...

Szoval ugy erzem akkor tudink majd esetleg eszmecseret (vitat) folytatni, ha majd el tudsz vonatkoztatni a programozasi kornyezettol es a matematikai/algoritmikai reszere tudsz koncentralni.

[vers]

@Leni: matekot regen tanultam, meg az utobbi 5 evben a muveszetet nyomtam, kicsit megkopott a tudasom

[Nyulpapa]

@bogdan: Mi volt pontosan a gond a párhuzamos gyorsrendezésnél? Azért kérdezem, mert a párhuzamos gyorsrendezés elõnye a többi párhuzamos algóval szemben pont az, hogy nem kell a threadek között kommunikálni. Kész egy lista és már indulhat rajta a new thread.

[bogdan]

Idézet: vers - Dátum: 2010. 07. 02. 00:15

@bogdan: fordul a fenet


for(i=0;i for(i=200;i<300;i++)cout< }


ez a sor kicsit problemas

nincs is benne ilyen sor! mit olvasol Te?

[bogdan]

Idézet: Leni - Dátum: 2010. 07. 02. 01:38

Ja es kotozkodni sem akarok mar, meg ertelme sincs, a radix az egy fuggveny.

meg egy rendezes neve is..! gondolod nem hasznalnak hasonlo neveket kulonbozo helyeken?
es vers ezt azert ugy hiszem ismeri.

Szerkesztette: bogdan 2010. 07. 02. 07:40 -kor

[bogdan]

Idézet: Nyulpapa - Dátum: 2010. 07. 02. 07:19

@bogdan: Mi volt pontosan a gond a párhuzamos gyorsrendezésnél? Azért kérdezem, mert a párhuzamos gyorsrendezés elõnye a többi párhuzamos algóval szemben pont az, hogy nem kell a threadek között kommunikálni. Kész egy lista és már indulhat rajta a new thread.

kell kommunikalni: at kell adni a kezdeti adatokat, es vissza kell adni az eredmenyt!

gond nem volt vele, mukodott jol, csak amig 1-2GByte-nyi adatot atviszel ket gep kozott, meg vissza az eredmenyt, addig egy gep is lerendezi neked! ha egy gepen belul parhuzamosit az ember (azaz a szalak kozotti kommunikacio memoriaban tortenik), akkor 8 szalon talan a duplajara is gyorsult.. de halozati kommunikacioval 2-4x lassabb volt.

nagyobb adatmeretnel persze kijonne a kulonbseg (ugye a kommunikacio linearisan, a rendezes meg lin szor logaritmikusan lassul), de az mar nem fer bele a memoriaba..

[Nyulpapa]

@bogdan: Bazz... Bocs, tényleg a hálózat a(z igen) szûk keresztmetszet, úgy látszik az értõ olvasás nekem sem megy reggel...

[bogdan]

Idézet: Leni - Dátum: 2010. 07. 02. 01:21

"eloszor a..... utana meg" - ez meg mindig soros

hadd vedjem meg: en csak kerdeztem, hogy a radixot hogy hasznalja valosak rendezesere, itt nem volt szo parhuzamositasrol!

abban a programom parhuzamositasat varom.. (amivel elkepzelni sem tudom, mit benazik vers: most ki copy-pasteltem a teljes kodot, es fordul, es nincsenek benne olyen marhasagok, mint amit vers irt..)

[bogdan]

Idézet: Nyulpapa - Dátum: 2010. 07. 02. 07:19

a párhuzamos gyorsrendezés ... Kész egy lista és már indulhat rajta a new thread.

egyebkent igy is lehet, de ebben az esetben szamolni kell, hogy milyen hosszu listat ad oda az ember egy uj thread-nek, mert kulonben a thread-ek szama ertelmetlenul sok lesz, vagy a masik esetben lesznek kihasznalatlan eroforrasok. bonyolult, nehez, problemas.. ezert jobb a samplesort, ami a gyorsrendezes olyan tovabbfejlesztese, ami jol parhuzamosithato, es az altalad leirtaknal joval kevesebb kommunikaciot is igenyel.

[Nyulpapa]

@bogdan: Értelem szerint. Nyilván csak arról tudok beszélni, amit ismerek, programozás ügyileg már elszaladt kicsit mellettem az idõ...

[vers]

@bogdan: szerintem az internet explorer nem szereti a c kodot

ha a rendezendo tomb tul van a 1-2 szaz ezren, akkor 16 bites radixtombel, 1 milliard adat rendezese , 2 milliard ciklus , mig mas elavult lgn-es algonal minimum 30 milliard
de a valosagban van az 100 is mivel a radix ciklusa 5 sor asm-ban ,
az olyan processzoroknal ahol a veletlen adat olvasasa miatt borulna az algoritmus , eloszamlalast vegezve totalisan stream adatfolyam olvasast lehet megvalositani, igaz ugyan hogy igy 3*milliard ciklusunk lesz , de megis gyorsabb vegrehajtast kapunk a memoria sebesseg miatt , pl ibm Cell

http://www.gbadev.org/demos.php?showinfo=356

ebben a jatekban radixot hasznaltam, es ugy kb lealaztam a scenet

[bogdan]

Idézet: vers - Dátum: 2010. 07. 02. 12:08

@bogdan: szerintem az internet explorer nem szereti a c kodot

hat akkor nyisd meg massal a forumot! ennyire azert ne benazz!

es varom akkor a parhuzamositasi javaslatodat!

Idézet

ha a rendezendo tomb tul van a 1-2 szaz ezren, akkor 16 bites radixtombel, 1 milliard adat rendezese , 2 milliard ciklus , mig mas elavult lgn-es algonal minimum 30 milliard

en tudom, mi az a radix, miert magyarazod ezt nekem?

[bogdan]

ja BAZZ, ne a fooldalon keresztul nezzetek a kodot, mert ez a pocsek hwsw meg csak azt sem tudja ugy latszik megoldani, hogy amit a szerkeszto sajat "code" tagjaval beilleszt az ember, az latszodjon is valahogy a cikk alatti hozzaszolasokban!

ekkora ganysagot mar!

[vers]

@bogdan:

"en tudom, mi az a radix, miert magyarazod ezt nekem?"

szerintem nem, mert akkor meg csak nem is gondalnal masra, fel sem merulne holmi logn-es algoritmus, torolni kell felesleges informacio

[bogdan]

nyugi, tudom. a masik informacio sem felesleges, nekem legalabbis.

de hagyjuk, ez mellekszal: remelem most mar sikerult a forumban megnezned a programot, amit kuldtem, es minden bizonnyal kapjuk a parhuzamositasi javaslatodat is. ugye?

[vers]

@bogdan: johogy

" for(i=1;i
X1=x0^2-x1
X2=X1^2-x2= (x0^2-x1)^2-x2=x0^4 + x1^2 - 2*x0^2*x1 - x2

tehat minden kiszamitando adat felirhato polynom alakba, amikor a processzorok vegeznek a sajat ertekuk kiszamitasaval besegitenek egy masik adat kiszamitasaba , igy kb N/2 ciklusido alatt vegezhetnek
tehat a szamitast felgyorsitottam dupla gyorsra , kezdetnek ez nem rossz egyelore ennyire jutottam, tobb idom nem nagyon van ra ,de erzesem szerint van egy logn algoritmus is

[vers]

ja a masodik dupla ugras az a double szamok , 2 lepeses szamolasabol adodik, tehat mantisszat , karakterisztikat szamolunk kulon processzoron singlevel
igy mar 4-szer gyorsabb a cucc gpu-n(ati-n 10 -szer)

[bogdan]

Idézet: vers - Dátum: 2010. 07. 02. 14:40

tehat minden kiszamitando adat felirhato polynom alakba,

ez persze igaz.. de vigyazz, jon a pofozobozotos!

Idézet

amikor a processzorok vegeznek a sajat ertekuk kiszamitasaval besegitenek egy masik adat kiszamitasaba , igy kb N/2 ciklusido alatt vegezhetnek

igy erted N^2/2 alatt..? mond, hany negyzetreemelest vegzel igy el az eredeti N-hez kepest? (no meg azert ne N processzort hasznaljunk, hanem kevesebbet.. legyen pn<<N -- tipikusan ugye pn tizes-ezres nagysagrendu, N meg millios-milliardos.)

Idézet

tehat a szamitast felgyorsitottam dupla gyorsra , kezdetnek ez nem rossz

vagy negyzetesen lelassitottad az egeszet?

a "nem rossz" helyett nem inkabb a pocsek jelzo illik inkabb ra?
(a pelda nem veletlen, es a Te megkozelitesed a "szabvanyos" rossz ut, amit a tankonyvek is kiemelnek..)

Szerkesztette: bogdan 2010. 07. 02. 17:07 -kor

[vers]

@bogdan: attol fugg mennyire lehet egyszerusiteni a polynomokat, nem kell mindent ujra kiszamolni, lehetseges hogy direkt olyan peldat adtal meg hogy szivjak mint tokosborz

[vers]

@vers: a processzorokban az osszeado aramkoroknel is igy csinaljak , hogy oprajel alatt vegezzen, es ne kelljen az atvitel bitet megvarni mig vegigporog