Hello!
Eloszor is erdekelne, hogy a tobbszalas programozassal megoldhato-e, hogy egy adott c++ programban levo ket folyamat a ket processzormagon egymassal parhuzamosan fusson, ne egymas utan?
Egy QuickSort algoritmust szeretnek ugy megirni, hogy az az elso partitioning utan a ket tombot ket szalon rendezze, parhuzamosan, gondolom ettol majdnem felere csokkenne a futasi ido.
Egy beadandohoz kellene, csak ugy erdekessegkepp a vegere iram, ha mar egyszer ugyis core duos a cucc...
- 1869 megtekintés
Hozzászólások
Megoldható, pont ilyesmire találták ki a szálazást. Azt viszont, hogy melyik szál melyik processzoron fut, az ütemező dönti el. Van valami módja ezt befojásolni, de nem tudom c++ alatt hogy működik.
- A hozzászóláshoz be kell jelentkezni
Ne nevessetek, csak javitsatok ki, ha oruletes blodseget mondanek, de az utemezo nem ugy fogja pont eldonteni, hogy a ket kulonbozo magon fusson? Tenyleg nem tudom... :\
- A hozzászóláshoz be kell jelentkezni
-QuickSort egy konkret algoritmus. ha mast csinalsz az nem QuickSort.
-2x gyorsitas? Es a ket reszeredmenyt osszefesulni ki fogja?
-amugy tfh az input "jo" es a quicksort nem n^2 hanem n*log(n) -es.
(legrosszabb esetben n^2-es mint a buborekrendezes...)
n<=n/2 azt adja hogy n/2*log(n/2) de ossze kell fesulni az +n + a szalas overhead
szoval nagysagrendben kb. ott vagy ahol voltal
persze egy probat meger, ha megvan - es van kedved mericskelni - erdekelne milyen futasi ido kulonbseg van a szekvencialis meg a parhuzamos kozt..
====================
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.
- A hozzászóláshoz be kell jelentkezni
QuickSort egy konkret algoritmus. ha mast csinalsz az nem QuickSort.
ha ugyanarra a bemenetre ugyanaz a kimenet es minden elemi lepest ugyanugy csinal, akkor az ugyanaz az algoritmus, szerintem. az ma'r inkabb implementacio kerdese, hogy most 1, 2, sok cpu-t hasznal.
2x gyorsitas? Es a ket reszeredmenyt osszefesulni ki fogja?
nem kell osszefesulni: a qsort valahogy igy mukodik:
static int index_qsort_local(int *index,int l,int r,
int (*compare)(int,int,void *),void *param)
{
int i,j,tmp,ch;
ch=index[(l+r)/2];
i=l-1,j=r+1;
while ( 1 )
{ do { i++; } while ( index[i] != ch && compare(index[i],ch,param)<0 ) ;
do { j--; } while ( index[j] != ch && compare(index[j],ch,param)>0 ) ;
if ( i<j )
tmp=index[j],index[j]=index[i],index[i]=tmp;
else if ( i==j )
{ i++;
break;
}
else break;
};
/***/
if ( l<j ) index_qsort_local(index,l,j,compare,param);
if ( i<r ) index_qsort_local(index,i,r,compare,param);
return(0);
}
szoval az elso" hivas utan ke't szalra bomlik, az egyik csinalja az l<j esetet, a masik az i<r esetet. utana ma'r nem tortenik semmi (return(0)).
persze biztos lehet trukkozni, pl. valahogy globalis modon tarolod, hogy e'pp hany szal fut, es hogyha a /***/ re'szen csak egy sza'l fut, akkor kettot indit el. Persze mindezt okosan, mert nagyon-nagyon sok overhead jon abbol, hogy uj sza'l letrehoz es/vagy lebomlik.
A.
- A hozzászóláshoz be kell jelentkezni
Kezdem ugy latni, ez igencsak meghaladja a kepessegeimet... Mindenesetre mar most is merem ugyebar az idoket - ez a beadando feladat celja -, es egymillio szamra is 3 tizd mp. alatt csinalja.
- A hozzászóláshoz be kell jelentkezni
ez a fenti ize elegge altalanos es raadasul az index-tombot rendezi, nem is a valodit (mint pl maga a qsort()). ugy, eredeti felallasban ez joval egyszerubb...
de a sza'laza'shoz me'g valoban meg kellene nezni ezt-azt, legfokeppen azt, hogy a ke't egymas utani rekurziv hivas nem kavar-e be egymasnak (azaz az l, i, j, es r valtozok kozott a megf. kenyszerek megvannak-e', azaz nem fed a't a ke't memoriaterulet). Ha nem, akkor szerintem relative egyszeru, legalabbis c-ben. c++-hoz nem ertek annyira...
A.
- A hozzászóláshoz be kell jelentkezni
Amugy az en kodom nemileg egyszerubb es atlathatobb:
void QuickSort(int* nums, int r, int l=0){
int i, j, pivot;
if(r > l) {
pivot = nums[r]; i = l-1; j = r;
while (1) {
while(nums[++i] < pivot); comparisons++;
while(nums[--j] > pivot); comparisons++;
if(i >= j) break;
std::swap(nums[i], nums[j]);
}
std::swap(nums[i],nums[r]);
QuickSort(nums,i-1,l);
QuickSort(nums,r,i+1);
}
}
Igy hivom a foprogrambol:
N 1000, 2000, 5000, 10000, 50000, 1000000 valamelyike (nyilvan a tesztelesnel mindegyikre lefut magatol.... hmmm... majd opensource felteszem az egeszet ide, ha kesz :))
...
int A[N];
QuickSort(A, N);
- A hozzászóláshoz be kell jelentkezni
"QuickSort egy konkret algoritmus. ha mast csinalsz az nem QuickSort."
Akkor fogalmazzunk ugy, hogy egy adott elemnel szetvalasztott tomb ket reszet quicksorttal rendezem, parhuzamosan.
"2x gyorsitas? Es a ket reszeredmenyt osszefesulni ki fogja?"
Tudom, hogy nem pont ketszer gyorsabb. hanem annal egy kicsit tobb ido, mert a cache megoszlik a ket processzormag kozt, stb.stb. Az osszefesulni reszt nem ertem. Lesz ket rendezett tombom, egyik ~0 es n kozt, a masik m es ~vegtelen kozt, ahol (n < m) v (n = m). {ez logikai jeloles volt. tudom, hogy C-ben az '=' operator ertekadas}
Utana egybefuzni... hat igen. mondjuk lancolt listas megoldas a leggyorsabb valszeg.
"...ha megvan - es van kedved mericskelni - erdekelne milyen futasi ido kulonbseg van a szekvencialis meg a parhuzamos kozt.""
Na igen. sajnos kedvem nincs, de beadandokent meg kell csinalni, es gondoltam miert ne lehetne valamivel megfuszerezni a dolgot.
Szoval, valaki valamit is konyit hozza, hogy lehet ilyet?
- A hozzászóláshoz be kell jelentkezni
Visszaszivom igazad van, ez igy QuickSort. Azt hittem a particionalas allat masra gondolsz.
Hogyha elsore sikerulne jo medians elemet valasztanod akkor 2 threaddel
ertelmesen meg lehetne csinalni. Az elso szinten inditasz 2 threadet, aztan a tovabbi tomb felosztasoknal mar nem mivel csak 2 magod van. Pech : medianst valasztani nehez. Tehat inkabb vmi olyasmi kene, hogy amikor egy elemet a helyere
mozgatott az egyik thread megnezi fut e meg a masik. Ha mar nem akkor a 2 reszfeladat
egyiket megoldja maga, a masikra indit uj threadet.
PS. Az egesz optimalizacionak semmi ertelme ha nem iterativan hanem rekurzivan
csinalod.
====================
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.
- A hozzászóláshoz be kell jelentkezni
"Hogyha elsore sikerulne jo medians elemet valasztanod"
Ahogy tanultuk, empirikus tapasztalatok alapjan erdemes az elso, utolso, kozepso elemek medianjat valasztani, ha tudjuk, hogy fair veletlenszeruen generalt szamok. En meg gondoltam arra is, hogy mondjuk egymillio szam rendezese eseten, ha fair random szamok vannak, erdemes ugy megvalasztani a pivotot, hogy mittomen az elso 100 szam medianja, amennyit ott vesztunk, talan nyerunk a tobbi reszen annyit.
Gondolkodtunk mar ezen a dolgon szobatarsaimmal - namarmint a parhuzamos coreokon valo futtatason. Az a gond, hogy mvel holnap utanra kell leadni, szerintem nem fogok ezzel szarakodni tobbet, majd ha egyszer nagyn raerek.
- A hozzászóláshoz be kell jelentkezni
Szerintem úgy kellene, hogy létre kell hozni egy queue-t, amibe majd belekerülnek a partícionálandó részek indexei. Indítani kell n threadet, amelyek a queue-ra várnak. Ha belekerül valami a queue-ba, akkor a theradek felébrednek, vesznek maguknak egy feladatot a queue-ból (ha van), végrehajtják a partícionálást. Keletkezik két rész, az egyik indexeit beleteszi a feladat-queue-ba, a másikon fut tovább az aktuális thread.
Ezáltal mindig dolgoznak a thread-ek, ha van mit csinálni, és ez nem csak két threadre működik, hanem akárhányra.
- A hozzászóláshoz be kell jelentkezni
Igen jo otlet. Nemi mutexeket kellene meg hozza dobni, meg amikor mar nagyon kicsi particok vannak, akkor nem kene, visszatenni a sorba (pl. 64 alatti elemszam), mert tobb idot vesz el a manageles, mint a rendezes...
- A hozzászóláshoz be kell jelentkezni