Sorterings algoritme ved bruk av GPU

[DeadMeat]

Hei

 

Jeg driver aa tester en del forskjellige sorteringsalgoritmer i forbindelse med en skoleoppgave. Har programmert noen grunleggende men jeg er ikke helt fornoyd siden den ikke bruker alle resursene pcen min har.

 

For det forste har jeg 2 kjerner paa CPUen og dermed vil en sorteringsalgoritme som kun kjorer som en prosess max faa 50% av CPUen. Det jeg tenkte var aa modifisere en Qsort eller en merge sort til aa kjore som to prosesser, dette er ikke en stor utfordring.

 

Det jeg ogsaa vil prove er aa faa den til aa kjore paa GPUen idielt slik at den faktisk kjore som 3 prosesser, en paa hver kjerne og en til gpuen (beste metode her er muligens shaer sort uten at jeg har sett saa mye paa det.)

 

Vel til sporsmaalet mitt, hvordan kan jeg faa java til aa kjore kode paa GPUen? Den maa da kunne kjore en vanlig sorteringsalgoritme. Forste jeg tenkte paa vaar aa bruke Java 3d men siden jeg ikke har mye erfaring her saa har jeg ikke peiling paa hvor jeg skal begynne aa lete.

 

Takk for all hjelp!

Endret 6. desember 2006 av DeadMeat

[Harkonnen]

Jeg ser ikke noe poeng i å bruke GPUen i all fall i tilfellet med mergesort.

 

Mergesort vil vel faktisk gå tregere hvis du bruker GPUen. Siden CPUene vil gå tom for arbeid og må hele tida vente på at GPUen skal bli ferdig med sin deloppgave.

[krigun]

Det er nok fullt mulig å gjøre, selv om det antageligvis vil være mest effektivt å bruke data uavhengige sorterings algoritmer (Bitonic sort o.l.), da som Harkonnen sier at mergesort er avhengig av de forskjellige data segmentene for å fungere optimalt. (kanskje jeg tar helt feil her, men dette er bare noe jeg tror).

 

PS: Sikkert nyttig lesing for deg: http://www.cis.upenn.edu/~suvenkat/700/lec...rting-kider.pdf

Endret 6. desember 2006 av krigun

[DeadMeat]

Hei

 

Takk for svarene!

 

Jeg ser tror heller ikke det er et stort poeng aa bruke gpuen i forbindelse med merge sort, men jeg har lyst til aa gjore det selv om det ikke nodvendigvis er raskere.

 

Jeg har sett eksempler paa sorteringsagoritmer som kjorer mye raskere paa en GPU en feks en qsort gjor paa en typisk CPU.

 

Problemet mitt er vel egentlig aa finne ut hvordan man kan faa det til i Java.

[krigun]

Problemet mitt er vel egentlig aa finne ut hvordan man kan faa det til i Java.

7439306[/snapback]

 

JOGL? (https://jogl.dev.java.net/) Ren OpenGL binding for java, eller mener du hvordan man skal restrukturere algoritmen til å fungere på en GPU?

[DeadMeat]

Tenkte paa hvordan jeg kunne faa algorithmen til aa faktisk kjore paa gpuen. Ved aa utnytte en av pipelinene paa gpue feks. Jeg har programmert en del OpenGL(i c og C++) saa jeg vet hvordan jeg setter det opp osv. men jeg har ingen ide om hvordan jeg faktisk skal faa den til aa kjore en sorteringsalgoritme paa GPUen.

 

Takk for linken til jogle har ikke brukt OpenGL i java for.

[krigun]

men jeg har ingen ide om hvordan jeg faktisk skal faa den til aa kjore en sorteringsalgoritme paa GPUen.

7439522[/snapback]

 

Har ikke gjort noe slikt selv, men tror dette er nøyaktig hva du leter etter (Må bare porte koden til java, burde være plankekjøring for deg): http://www.mathematik.uni-dortmund.de/~goe...u/tutorial.html

 

Evt. ta en titt på http://www.gpgpu.org og spesielt forumet der. Sikkert mange der som kan hjelpe deg bedre enn her.

 

PS: Tutorialen viser ingen sorteringsalgoritmer, men konseptene burde være de samme. Hadde vært veldig morsomt hvis du hadde posta noe enkel JOGL kode her for dette, siden du skal knote med dette allikevel

Endret 7. desember 2006 av krigun

[DeadMeat]

Hei

 

 

Takker for hjelpen, det ser ut som om jeg kan bruke dette til aa finne ut av hvordan jeg kan lage en enkel sorteringsalgoritme og faa den til aa kjore paa GPUen.

 

Jeg har tid over helgen til aa jobbe med deg og jeg kan poste koden her hvis jeg finner ut av det.

[blackbrrd]

Quicksort er relativ enkel å kjøre fler-trådet. Etter første "sortering" deles jo jobben effektivt i to. Hvis du har mer enn 2 prosessorer tilgjengelig så må du kjøre det en gang til, da har du delt jobben i 4. ... og sånn fortsetter det.

 

GPU-en er nok ikke veldig godt egnet til jobber med masse if setninger, slik som dette...

 

Quicksort er jo egentlig rimelig enkel, selve koden blir jo ikke på mer enn ca 10 linjer...

[krigun]

GPU-en er nok ikke veldig godt egnet til jobber med masse if setninger, slik som dette...

 

Quicksort er jo egentlig rimelig enkel, selve koden blir jo ikke på mer enn ca 10 linjer...

7677937[/snapback]

 

Nja, tror problemet ligger i å vri hodet sitt rundt grafikkprosessor tankegangen. Hadde jeg gjort noe slikt, så ville jeg kanskje sett på vertex/pixel shadere for evt. kandidater, men kan ikke helt se for meg hvordan det konkret kan løses. (F.eks GLSL: http://www.davidcornette.com/glsl/glsl.html)

Endret 9. januar 2007 av krigun

[Simen1]

Nå er ikke akkurat dette for java, men jeg tenkte det kunne være interessant likevel:

 

Nvidia Releases CUDA SDK

"Nvidia released a public beta of its CUDA software development kit Friday morning, offering developers the chance to use the GeForce 8800 as a general-purpose CPU."