[bogdan]

nem "lehetseges", hanem pontosan tudom, hogy olyan peldat adtam!

ez ugyanis hatrafele fuggoseg, es nem linearis. amit, ahogy mar megirtam, jelenleg nem tudnak parhuzamositani!

mas esetben lehetne trukkozni, de itt nem. es kepzeld, ebbol a szempontbol ez ekvivalens az iteracioval, hiszen ott is az elozo lepesbol kell kiszamolni a kovetkezot, ahogy itt is gyakorlatilag. ha ez nem linearis, akkor nem lehet parhuzamositani. ha linearis, akkor van ra trukk.

de akkor megegyezhetunk abban, hogy a fenti alitasod, miszerint barmely algoritmust lehet parhuzamositani, vagy legalabb trukkot talalni ra nem allja meg a helyet?

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

[vers]

@bogdan: nade ha tobb processzorod van mint az N akkor mukodik az algoritmus, mert lehet hogy tobbet kell osszesegeben szamolni , de van mivel

viszont ugy hogy meg a processzorok szamat is lekorlatozod P

[vers]

@vers: mert pl vegyunk N=16-ot, ha n^2 a polinomok elemszama , akkor 256 processzorral 1 ciklus alatt kesz az eredmeny

az meg hogy most csak 384 processzorunk van , az nem jelent semmit , lesznek itt meg milliok

tehat az olgoritmusom mukodik, bizonyos helyzetekben

[bogdan]

n^2 processzor eseten??
(es persze szepen elhanyagolod a kommunikacio sebesseget..? szep csusztatas!)

nezd, ertelmes feladatot kertel, es en olyat adtam. millios, milliardos meretu tomben szamolas. elvben olyan feladat, amit lehetne ertelmes korulmenyek kozott is parhuzamositani. de nem lehet. az n^2 processzor nem ertelmes korulmeny, ugy hiszem..

[bogdan]

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

mert pl vegyunk N=16-ot,

mi a busnak akarnak ilyen kis meretu feladatot parhuzamositani..??

meg kulonben is, ha jol emlekszem Te voltal az, aki kerted a feladatot, es en voltam az, aki adta. es nem, nem N=16 meretu feladatra gondoltam (mar a programomban is N=1000 szerepelt, ha megnezed..)

[vers]

@bogdan: jo , de a processzorok szama eloszor nem volt kikotes, csak utolag lett az , mert eszrevetted hogy ugy megoldhato a problema

de elismerem hogy vannak idoben folytonos folyamatok amiket nem lehet parhuzamositani ,csak keves

[vers]

@vers: ha N= 1000, ami ezer ciklus ugye, akkor 1 millio processzorral 1 ciklusra redukalodik a vegrehajtasi ido
tehat ezerszeres a gyorsulas

ja hogy meg nincs 1 millio processzor, majd lesz

[bogdan]

ugy sem biztos, hogy megoldhato, mert mint irtam nem szamoltal a kommunikacioval.

van peldaul egy linearis osszehasonlito parhuzamos rendezes, "csak" n^2 processzor kell hozza (megszamlalo rendezes). amig nem torodik az ember a kommunikacioval, addig nincs gond, de ha valoban meg kell epiteni a chipet, ami megcsinalja, akkor ezres nagysagrendu processzor utan (max millios) nem fog mukodni az egesz.

a Te otleted is csak addig jo, amig a kommunikaciot nem szamolod bele. az ilyen extrem megoldasoknak az a rakfeneje.

az meg, hogy keves vagy nem keves az ilyen feladat nem konnyu kerdes. raadasul van egy csomo feladat, amit nem is erdemes parhuzamositani, mert egy mai gep szekvencialisan is gyorsan megoldja. a "maradek" az erdekes: a gepzabalo felhasznaloi programok, illetve a tudomanyos szamitasok.

ja, es persze vannak olyan problemak, ahol majdnemhogy mindegy, hogy lehet-e parhuzamositani (tipikus exponencialis algoritmusok), mert ha igen, akkor mondjuk nem 400 hanem egy 1000 csucsu grafra is meg tudod oldani a vilag legerosebb szuperszamitogepevel, de a tobbtizezer csucs lenne az erdekes..

[bogdan]

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

@vers: ha N= 1000, ami ezer ciklus ugye, akkor 1 millio processzorral 1 ciklusra redukalodik a vegrehajtasi ido

hiszed mindaddig, amig utana nem szamoltal a programozasi es kommunikacios koltsegeknek!

[vers]

@bogdan: ezt a problemat mindensetre eleg jol kiveseztuk , tovabb nem feszegetem
biztos lenne meg otletem ,csak van amikor egy het is keves egy jo a parhuzamos algoritmushoz, erre most nem futja

[bogdan]

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

biztos lenne meg otletem

ami meg biztos, hogy hasonloan rossz lenne!

(ha meg nem, akkor gazdag ember leszel!)

Szerkesztette: bogdan 2010. 07. 02. 19:12 -kor

[vers]

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

ami meg biztos, hogy hasonloan rossz lenne!

(ha meg nem, akkor gazdag ember leszel!)

ketlem hogy egy algoritmusbol barki gazdag lenne valaha is

amugy van egy uj elkepzelesem

ha egyszerre 2 thread szamol , parosaval szamolja az ertekeket , pl X(n) meg az X(n+1)

egyik thread : X(n)= X(n-1)^2-x(n)
masik thread : X(n+1)= ( X(n-1)^2-x(n) )^2 -x(n+1) , ezt kifejtve polinomma akar tobb processzorra is eloszthato

tehat ha parosaval szamolunk akkor a ciklusunk szama felezodik , a vegrehajtasi ido felere csokken, de akar lehet 3-asaval, 4-esevel stb is szamolni az ertekeket ,attol fuggoen hany fizikai processzorral rendelkezunk, talan egy mai gpu-n 16,32 egymas utani adat kiszamitasa is lehetseges parhuzamosan , igy a futasi sebesseg 16-32 szeresere nol

na ebbe koss bele , mondtam hogy csak idore van szuksegem

Szerkesztette: vers 2010. 07. 03. 12:07 -kor

[vers]

a ciklusok szama parhuzamos processzorokon 2* log2(N^2) - hez konvergal

pl N=1000 eseten 2*log2(1000^2) = 40 ciklus

uhogy jo volt a megerzesem ugy 50 hozzaszolassal ezelott:)

Szerkesztette: vers 2010. 07. 03. 13:04 -kor

[bogdan]

Idézet: vers - Dátum: 2010. 07. 03. 13:04

na ebbe koss bele

itt vagyok, itt vagyok! este valaszolok ra, jo?

(persze, hogy nem jo egyebkent.. addig is megszamolhatnad a negyzetreemelesek szamat, mint "elemi" muveletek..)

[bogdan]

Idézet: vers - Dátum: 2010. 07. 03. 13:04

ketlem hogy egy algoritmusbol barki gazdag lenne valaha is

azert egy primfelbonto algoritmus, ami az RSA-t, es minden raepulot azonnal feltor nem kis ertek lenne!

de vannak kevesbe kriminalisztikus lehetosegek is..

Idézet

amugy van egy uj elkepzelesem

lassuk, lassuk!

de elobb terjunk vissza egy pillanatra a regire! ugye az utolso sor, valahogy igy fog kinezni:
xN=x0^(2^N).....

tovabb nem is mennek, eleg idaig. mennyi ideig is tart ezt az egy tagot kiszamolni? hat N hatvanyosas lessz benne. magyaran az utolso processzorod legalabb annyit szamol, mint ami az eredeti feladat egy szem processzora onmagaban.. meg akkor is, ha N^2 processzort vetsz be. azaz egy kanyit nem gyorsult az algoritmusod, akarhany processzort is vettel.

hogy miert vettem elo ismet? hat mert ugy latom a mostani sem lesz jobb:

Idézet

ha egyszerre 2 thread szamol , parosaval szamolja az ertekeket , pl X(n) meg az X(n+1)

egyik thread : X(n)= X(n-1)^2-x(n)
masik thread : X(n+1)= ( X(n-1)^2-x(n) )^2 -x(n+1)

ugye kene egy szamitasi komplexitast szamolnunk. a szorzas tart a legtovabb, tehat vegyuk a szorzasok szamat, hanyagoljunk el minden mast: osszeadast, kommunikaciot..
az elso thread 1 szorzas, tehat egy lepes. a masodik thread 2 szorzas, tehjat 2 lepes ideig tart. a ketto parhuzamos, tehat az ossz lepesido 2 lepes. (az eredeti egy szem cpu-val szamolo algoritmusunk mennyi is? hat az is 2!)

es hiaba vegzett az elso cpu az elso szallal, meg kell varnia a masodik vegeredmenyet, hiszen a kovetkezo lepes a:
x(n+2)=x(n+1)^2-x(n+2), amihez szukseg van az uj x(n+1) ertekere, ami meg nincs kiszamolva..

Idézet

tehat ha parosaval szamolunk akkor a ciklusunk szama felezodik

mikozben a szamitasi lepesek szama megduplazodott, tehat pont ugyanannyi ideig tartott a dolog!

Idézet

mondtam hogy csak idore van szuksegem

valoban, latom sok idore van szukseged, hogy belasd egy tanykonyvi peldarol, hogy a tankonyv igazat allit, miszerint nem ismert hozza hatekony parhuzamositas...

de probalkozz nyugodtan, en raerek!

[bogdan]

nu, mire jutottal?

[bogdan]

na?

[sir ny3]

@bogdan: hagyd, ne zrikáld. Fõleg, ha ugyanazt állítjátok mindketten, vagyis, hogy majdnem minden párhuzamosítható, még ha akad kis számú kivétel is.

[h143570]

@vers: Barmilyen rekurziv algoritmus. Mivel a GPGPU programozasban hasznalatos C leszarmazottak nem tamogatjak a rekurziot.