quicksort auf einer GPU?

was weder zu YaCy noch zum Thema Suchmaschinen gehört

quicksort auf einer GPU?

Beitragvon liebel-lab » Fr Dez 19, 2008 9:42 pm

Quicksort auf einer GPU...hm waere das was ?
weil etliche threads (gerade bei der schwarmdiskussion) auf sorting verweisen...

siehe...
http://www.nvidia.com/object/cuda_home.html#
liebel-lab
 
Beiträge: 175
Registriert: Sa Jan 26, 2008 7:00 pm

Re: quicksort auf einer GPU?

Beitragvon PCA42 » Sa Dez 20, 2008 8:51 am

Vielleicht sollten wir auf Java für GPU's warten. ;)
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: quicksort auf einer GPU?

Beitragvon lisema » So Dez 21, 2008 11:48 pm

Moin,

vorhin habe ich mit einem Kumpel gesprochen. Das eine ist, das es eine neue Sache gibt, OpenCl. Dieses soll von CUDA auch unterstützt werden.


Des Weiteren haben wir kurz darüber gequatscht, was GPUs können und was nicht. Das schöne ist, es sind spezielle PUs optimiert auf viele Daten und Streamverarbeitung. Random Access ist dort ein bisserl schlecht. Was kann man nun damit machen? Im Prinzip viel Arithmetik. Thats it.

Datenbank Optimierung dachte ich erst, aber da wurde ich fix von abgebracht. Zu wenig RAM auf der GPU, nicht dafür ausgelegt, nicht wirklich performant, das war eine erste Einschätzung vom Kumpel. Er schaut es sich ein bisserl an, hat mich aber vorgewarnt.

Eine zweite Idee sind regexen. Warum nicht die Filter bei Bedarf durch die Graka jagen, sie ist schnell am am RAM angebunden? Diese Brachial Methode.Patternmatching, die man vermutlich an einigen Stellen hat. Wir lesen die ganze Datenbank nahezu sequenziell ein, und spucken dann die Ergebnisse aus, die Recrawled werden müssen whatever. Also "nur" ein Filter. Die CPU macht den IO Mist, die Graka die anderen Sachen.

Das ist so was nach 30 Min via ICQ rauskam. Das Ganze wird nochmal verfolgt werden. Vielleicht hat er ja Lust sowas mal zu machen, CG ist jedenfalls sein Ding. Er wäre, wenn er mitmacht auch sicher hier der beste Software Archtikt, den ich bisher kenne.

Also wir greifen es mal auf, es ist eine Spielerei. Java darauf wird nicht performant, wir müssten vermutlich spezielle Bibliotheken schreiben. C++ Coder mit Shaderprogrammierung Erfahrung können sicher noch mehr dazu sagen.Mein Fachgebiet ist es jedenfalls nicht

Und nun die Quellen:
http://en.wikipedia.org/wiki/OpenCL

Sodenn einen schönen 4.Advent und schöne Weihnachten.
lisema
 
Beiträge: 110
Registriert: So Dez 14, 2008 8:06 pm

Re: quicksort auf einer GPU?

Beitragvon Orbiter » Mo Dez 22, 2008 1:25 am

Quicksort ist in kelondro relevant, weil die Indizes damit nach dem Einlesen der primary keys gebildet werden, indem eine sortierte Liste gebildet wird. Die kann man kompakt ablegen, und Suche geht darin optimal.

Soweit wäre ein performantes Quicksort also für YaCy sehr hilfreich.

Ich habe, um das zu optimieren, ein concurrent Quicksort implementiert. Das geht bei Quicksort ganz gut, ein kleines Problem ist nur der erste Durchlauf mit Switchen über die gesamte Liste, weil man das nicht parallelisieren kann. Hat man den ersten Durchlauf (also noch kein Rekusionsschritt) durch, kann man mit 2 Threads weitermachen, dann mit 4 u.s.w. In YaCy wird das bei 2 und 4 Cores optimal genutzt, wobei es so ist, das eben der erste Durchlauf auch eben die Masse der Rechenzeit ausmacht, und die nachfolgenden Parallelisierungen nicht so stark was bringen. Hier die Rechnung:

sei T1 die Zeit für einen Quicksort-Test. Sie setzt sich zusammen aus dem Scan S1 und den rekursiven Sorts T2L und T2R. Ich gehe davon aus, das:
S1 = T2L + T2R
weil dabei eben bei S1 genau so viele Speicherstellen angefasst werden, wie bei T2L + T2R, also
T1 = 2 * S1
oder
S1 = 1/2 * T1

Sei nun T1(1) die Zeit für den Quicksort mit einem Prozessor, T1(2) die Zeit mit zwei, T1(4) die Zeit mit vier Prozessoren:
Parallelisiert man das nun, so kann man an S1(1) nichts ändern, es läßt sich nicht parallelisieren. Wohl aber T2L(2) + T2L(2), denn
T2L(2) + T2L(2) = 1/2 * (T2L(1) + T2L(1))
da das ja auf mehreren Prozessoren läuft.

Nun hat man also:
T1(2) = S(1) + 1/2 * (T2L(1) + T2L(1)) = S(1) + 1/2 * S(1) = 3/4 * T1(1)
d.h. durch einen 2. Prozessor spart man bei Quicksort nur 25% ein.
Das geht dann so weiter, die nächsten 2 Prozessoren bringen nur noch weitere 12.5% (ohne Beweis: kleine Rechenübung für jeden)
Vier Prozessoren bringen also einen Speed-Up von 37.5%

Das bedeutet: je mehr Cores an Quicksort beteiligt werden, desto weniger bringen die zusätzlichen Cores. Aus meiner Sicht ist damit die GPU zwar eine nette Idee, aber nach meiner Herleitung nach bringt das nicht viel. Immer vorrausgesetzt, dass meine Sicht auf die Möglichkeiten eines Concurrent Quicksort so richtig ist.
Orbiter
 
Beiträge: 5792
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: quicksort auf einer GPU?

Beitragvon liebel-lab » Fr Jan 09, 2009 10:23 pm

nochwas zum thema...

was haelst du von http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html

..hm...shear sort ....auch nett....naja noch nicht fuer "java fuer GPUs" .-)
liebel-lab
 
Beiträge: 175
Registriert: Sa Jan 26, 2008 7:00 pm

Re: quicksort auf einer GPU?

Beitragvon PCA42 » Sa Jan 10, 2009 12:35 am

Fand das Thema interessant und bin auf folgendes gestoßen: http://www.javaworld.com/javaworld/jw-09-2007/jw-09-multicoreprocessing.html?page=1. Hier wird ein Mergesort verwendet. Soll laut dem Artikel theoretisch 50%, im Anwendungsfall 35% auf einem Dualcore bringen. Codebeispiel in Java ist als Link mit bei.
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: quicksort auf einer GPU?

Beitragvon Orbiter » So Jan 11, 2009 1:20 am

das sind zwei sehr interessante Anregungen. Hab ich mir alles angesehen. Zunächst mal zu Mergesort:
das lässt sich schön parallelisieren, aber es hat 3 Nachteile:
- der Speicheraufwand: man braucht ein back-up array für den Merge, das könnte bei manchen Rechnern knapp werden, erst recht die Leute mit >10 Mio Einträgen in der DB schaffen das nicht so leicht.
- der Durchsatz auf dem Bus: die vielen Kopiervorgänge in den Speicher belegen den Bus, und der skaliert nicht mit den Prozessoren
- der Merge am Ende des Sortierens ist genau so schlecht zu parallelisieren wie das Splitten bei Quicksort am Anfang

Shear Sort:
ist ein in-place sorting, d.h. keine neuen Arrays, nicht mehr Speicher. sieht geeignet aus. Das zeilen- und spaltenweise Vorgehen läßt sich sehr starkt parallelisieren, d.h. wenn ich 1 Mio Einträge habe, kann ich ein 1000x1000 Array machen, und die Operationen dort quasi 1000-fach parallel machen. Und für die Einzelsortierungen in Reihen und Spalten kann ich wiederum das Quicksort nehmen, das ja schon gut funktioniert.
Ein Problem ist, das die Daten in eine Matrix passen müssen, d.h. eine Primzahl von Einträgen kann ich damit nicht sortieren. Eine Anzahl von Einträgen mit ungünstigen Faktoren ist dann auch schlecht. Oder man fügt an die Liste so lange künslich maxvalue-Einträge hinzu, bis die Matrix optimal ist. Darüber muss ich nochmal nachdenken. Ansonsten würde ich das spannen finden, das mal auszuprobieren.
Orbiter
 
Beiträge: 5792
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: quicksort auf einer GPU?

Beitragvon dulcedo » So Jan 11, 2009 5:24 am

Orbiter hat geschrieben:- der Durchsatz auf dem Bus: die vielen Kopiervorgänge in den Speicher belegen den Bus, und der skaliert nicht mit den Prozessoren

Tut er im Prinzip schon, bis zu einem gewissen Grad, und natürlich wieder ein Süppchen das AMD und Intel getrennt kochen.

Eher zu den Grundlagen, denke nicht dass sich dieses Wissen praktisch einsetzen lässt, woher weiss Java z.b. welche Architektur als Unterbau verwendet wird, solche Details betreffed.

http://www.techspot.com/vb/showpost.php ... ostcount=2
(grade für solche Texte hat Gutenberg das CR erfunden, grauenhaft, aber interessant!)
dulcedo
 
Beiträge: 1006
Registriert: Do Okt 16, 2008 6:36 pm
Wohnort: Bei Karlsruhe

Re: quicksort auf einer GPU?

Beitragvon Orbiter » So Jan 11, 2009 12:51 pm

erst dachte ich, "shear sort" wäre was ganz neues, ist es aber nicht, denn auch in Knuths 'The Art of Computer Programming' wird es beschrieben, so jedenfalls sagen viele Referenzen die ich gefunden habe. Das habe ich jetzt mal zum Anlass genommen, mir das Werk zu bestellen.
http://www.amazon.de/Art-Computer-Progr ... 201485419/
Orbiter
 
Beiträge: 5792
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main


Zurück zu Off-Topic

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron