Bitonisches Sortieren

Hallo Experten,

hier gibts eine Ausführung über bitonisches Sortieren,
http://www.tools-of-computing.com/tc/CS/Sorts/bitoni…
mit Code (s.u.)

Der funktioniert wunderbar, wenn die Zahl der Elmente
2er-Potenzen hat und irgenswie durch 2,4,8 teilbar ist.
Wenn die Anzahl der Elemente zb 15 ist, funktionierts nicht.
Ein Array mit 15 Elementen 14,13,12,11 … 3,2,1,0
sieht nach dem aufsteigenden sort so aus:

0:7.000000
1:8.000000
2:9.000000
3:10.000000
4:11.000000
5:12.000000
6:13.000000
7:14.000000
8:6.000000
9:5.000000
10:4.000000
11:3.000000
12:2.000000
13:1.000000
14:0.000000

Liegt das wohl an der Implementierung unten,
oder liegt das Grundsätzlich am bitonischen Sortieren,
also dass es nicht jede beliebige Anzahl von elementen
richtig sortiert, wohl nicht oder?
Für mich sieht das so aus, als ob der Code nicht ganz fertig ist,
die zweite Hälfte des Arrays muss noch sortiert werden
und mit der ersten Hälfte vertauscht werden.
Steht auch so etwa im Artikel
We sort only sequences a power of two in length, so we can always divide a subsequence of mnore than one element into two halves.
was muss man tun, um ohne Rekursion die Sache fertig zu kriegen?

for (k=2;k>1;j>0;j=j>>1) {
for (i=0;ii) {
if ((i&k)==0 && get(i)>get(ixj)) exchange(i,ixj);
if ((i&k)!=0 && get(i)

Moien

Liegt das wohl an der Implementierung unten,
oder liegt das Grundsätzlich am bitonischen Sortieren,

Es liegt am grundsätzlichen Verfahren. Wobei einige der Implementieren drum rum arbeiten.

I.d.R. macht man bei sowas padding. D.h. man fügt einfach solange Elemente an bis es halt 2^n sind. Die Dummyelemente setzt man auf einen bekannten Wert (den der maximal vorkommen kann) und filtert sie nachher wieder raus.

cu

Danke, sowas hatte ich mir kaum denken können.
Hier gibts aber eine (graphische) Implementierung,
die auch mit 15 funktioniert.
http://www.iti.fh-flensburg.de/lang/algorithmen/sort…
Aber jetzt meine ich, zu verstehen.
Mein Eindruck ist, dass zumindest die erste 2erPotenz der
Elemente richtig sortiert wird, also die ersten 8 von 15 elementen.
Danach muss man die nächsten 4 elemente 9,10,11,12 bitonisch (oder sonstwie) sortieren (sofern 4 in der Elementzahl ist), dann die 2 Elemente 13 und 14. Danach muss man die Teilarrays der 2er Potenzen alle mergen. Ich glaub aber, dass man sich dann den Laufzeitgewinn durch Parallelität u.U. zunichte macht, sodass -wie Du sagts-
eine Ausweitung des Arrays auf eine 2er-Potenz mit Dummy-Werten
sinnvoller ist.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

Moien

Hier gibts aber eine (graphische) Implementierung,
die auch mit 15 funktioniert.

Das ist (streng genommen) nicht bitonisch. Das wird aber bitonisch wenn man 2^n Elemente reinstopft.

Danach muss man die nächsten 4 elemente 9,10,11,12 bitonisch
(oder sonstwie) sortieren (sofern 4 in der Elementzahl ist),
dann die 2 Elemente 13 und 14. Danach muss man die Teilarrays
der 2er Potenzen alle mergen.

Ich glaub aber, dass man sich
dann den Laufzeitgewinn durch Parallelität u.U. zunichte
macht, sodass -wie Du sagts-
eine Ausweitung des Arrays auf eine 2er-Potenz mit
Dummy-Werten sinnvoller ist.

Nihct unbedingt. Wenn es dir heute um die Laufzeit geht ist es besser von der reinen Lehre abzukommen und den nicht 100% bitonsichen Ansatz zu nehmen (Von der Laufzeit her sind andere auf den modernen 2-Kern Systemen eh deutlich schneller).

Solche Algos wurden oft für einen speziellen Typ Hardware entwickelt. Bei denen ist es dann nicht möglich eine etwas flexiblere Auslegung zu machen. Da muss man zu Dummywerten greifen. Beschäftig dich ein bisschen mit den allerersten Crays und deren Grundlagen. Die haben so strikte Vorgehensweisen noch ganz ernsthaft gebraucht.

cu

cu

da, also ich beschäftige mich mit cuda,
diesem SDK für GPU-Programmierung
von Nvidia ab Modell 8800 GTS.
Da ist so ein Beispielprogramm,
das kann aber nur 256 elemente,
und das auch nur in den bekannten
2er Potenzen.
Die 8800 ist aber auch ne tolle Graphikkarte,
für Spiele etc, man soll ja das angenehme mit dem nützlichen verbinden. Ohne CUDA hätt ich die 350 € aber nicht dafür
auf den Ladentisch gelegt. Ich wollt’ das Programm ein wenig aufbohren für beliebig viele Elemnte und ganze Datensätze. Mehrere 1000 Threads sollten möglich sein. Aber es gestaltet sich schwierig.
Ich weis auch gar nicht ob es sich lohnen wird,
die so >100 Millionen Zahlen die in die 640 MB Graphikkartenspeicher passen, sind mit standard qsort in so 2 sekunden sortiert, etwa 0,5 sek braucht der Transfer in die Graphikkarte, und 0,5 zurück, also
ist schon rund eine sekunde verbraucht.

Ich hab so in den frühen 90ern auf Convex und Nec SX3
gerechnet. Da machte das alles der Fortran Compiler,
(also nicht sortieren, aber Matrizen und Vektoren mit ±*/ Operationen), was manchmal auch schwierig war,
aber man hatte nichts mit der Technik zu tun.
Die Kollegen sagten, die Crays seien nicht so schnell wie die Nec,
aber der Compiler der Cray holts wieder raus, die gewonnene Arbeitszeit macht die Cray als ganzes dann doch wieder wesentlich schneller als die Nec, das durfte man aber nicht laut sagen.
Sicherlich meintest du noch ältere Crays.

Moien

da, also ich beschäftige mich mit cuda,
diesem SDK für GPU-Programmierung
von Nvidia ab Modell 8800 GTS.

Ach deshalb das Verfahren. Ich dachte irgendein Uniprof hätte eine der alten SIMD-Architekturen ausgegraben und würde damit Studis quälen.

Die 8800 ist aber auch ne tolle Graphikkarte,
für Spiele etc, man soll ja das angenehme mit dem nützlichen
verbinden. Ohne CUDA hätt ich die 350 € aber nicht dafür
auf den Ladentisch gelegt.

GPU-Programmierung ist nicht mein Gebiet. Von CUDA hab ich gehört, sieht lustig aus. Allerdings scheint ATI den Forschern besser zu gefallen. Folding@Home läuft nur auf ATI X19XX Karten. Angeblich weil die ATI längere Laufzeiten und mehr Code für ihre Shaderprogramme erlauben. OK, der normale Mensch wird mit „normalen“ Aufgaben die Rechnerpower so oder so nicht auslasten können. Und der ATI-Support ist eher bescheiden und Treiber meistens Schrott. Ein CUDA-mässiges Programm hab ich bei ATI noch nicht gesehen.

Ich weis auch gar nicht ob es sich lohnen wird,
die so >100 Millionen Zahlen die in die 640 MB
Graphikkartenspeicher passen, sind mit standard qsort in so 2
sekunden sortiert, etwa 0,5 sek braucht der Transfer in die
Graphikkarte, und 0,5 zurück, also
ist schon rund eine sekunde verbraucht.

Sortieren ist nicht gerade das Ziel von GPUs. Ich glaube mit sortieren alleine wird die Karte nicht glücklich. Da müssen weitere Programmteile drauf wandern.

Ich hab so in den frühen 90ern auf Convex und Nec SX3
gerechnet. Da machte das alles der Fortran Compiler,
(also nicht sortieren, aber Matrizen und Vektoren mit ±*/
Operationen), was manchmal auch schwierig war,
aber man hatte nichts mit der Technik zu tun.
Die Kollegen sagten, die Crays seien nicht so schnell wie die
Nec,
aber der Compiler der Cray holts wieder raus, die gewonnene
Arbeitszeit macht die Cray als ganzes dann doch wieder
wesentlich schneller als die Nec, das durfte man aber nicht
laut sagen.
Sicherlich meintest du noch ältere Crays.

An den Anfängen gab es in Crays Entwürfen separate Einheiten für so ziemlich alles. Diese Einheiten sind superschnell aber unflexibel. So Sachen wie Vektorprodukt, Matrixmultiplikation,… usw waren damals (~1980-85) als reale Hardwareschaltung implementiert. Aber halt nur für bestimmte Grössen. Die Compiler haben die realen Matrixgrössen dann drauf angepast. Padding ist in dem Fall deutlich schneller als das ganze auf den normalen Prozessoren durchzukauen. Auf bestimmte Systeme optimierte Fortrancompiler waren Meister des Umbauen von Vektoren und missbrauchen von Einheiten für die absurdesten Zwecke. Aber ab einem gewissen Punkt war das aber nicht mehr interessant, weil zu teuer. Es kostete zuviel Zeit, Busbandbreite (und Nerven der Compilerbauer) im Vergleich zu inzwischen schnelleren normalen Prozessoren. Ein anderer Quell solcher Algos war die CM-1 (und teilweise die CM-2). Auch der Transputer wurde von einigen Forschern für sowas benutzt.

Die Shader2 fähigen GPUs und Intels brandneuer Teraansatz wird den ganzen Kram wieder auferstehen lassen. Das wird noch sehr lustig …

cu

Sortieren ist nicht gerade das Ziel von GPUs. Ich glaube mit
sortieren alleine wird die Karte nicht glücklich. Da müssen
weitere Programmteile drauf wandern.

Ich hab eine Zahlereihe mit 67.108.864 Zahlen
aufsteigend gefüllt (also 1,2… 67.108.864)
und dann mit VC++ 7 qsort absteigend sortiert. Da dauert 2 Sekunden.
Mit bitonic -so wie gepostet- etwa 1 Min mit reinem C Code
auf einer CPU (3GHZ Intel)

Irgendwie scheint das VC7 qsort das zu merken, dass die Zahlen
umgekehr vorsortiert sind, und es dreht sie einfach um,
oder es liegt in der Natur von qsort.
(heisst das stabil oder natürliches Sortierverhalten?, ich weiss es nicht mehr)
Wenn man die Zahlenreihe mit Zufallszahlen füllt,
braucht das qsort etwa 15 Sekunden.
Die nicht Cuda bitonic 1-CPU Lösung bleibt bei 1 Min.
Wenn man die 67.108.864 Zahlen auf die
GraKa schiebt und in 256er Paketen mit Cuda sortieren lässt,
ist man schon auf 10 Sek runter.
Jetzt muss ich nur noch schauen, wie ich mehr als 256 Threads auf die Zahlenreihe ansetze.
Wenn man ganze Datensätze sortiert, glaube ich auch,
dass die postive Wirkung des CPU-Caches nachlässt,
während die 640 MB der GraKa sozusagen ein einziger Cache sind.

Ich glaub schon, dass man mit Cuda auf einen Faktor von
10-20 kommt gegenüber qsort kommt, mit reiner CUDA C-ähnlicher Hochsprache, nur Rekursionen und Funktionszeiger gehen nicht. Notwendige Verteilungsüberlegungen dürften die von MultiCPU-Systemen
nicht an Komplexität übertreffen.
Es ist auf jeden Fall hochinteressant und jetzt schon da
und billig, im Prinzip nur so 150 Euro zusätzlich zu einer
guten Graphikkarte.
Die Investitionen in die Software sollten gesichert sein,
denn der Spieltrieb treibt die Hardwareleistung der GraKas
weiter zeitnah zu den technischen Möglichkeiten und billig in die Höhe, und die GraKa Hersteller werden wohl nichts machen, dass alte Spiele und indirekt auch alte Cuda Programme nicht mehr funktionieren. Nvidia arbeitet angeblich auch an doppelt genauen
Graphikkarten.

Sortieren ist nicht gerade das Ziel von GPUs. Ich glaube mit
sortieren alleine wird die Karte nicht glücklich. Da müssen
weitere Programmteile drauf wandern.

Hier gibts jemanden von der TU München,
der sich vor 2 Jahren ca
damit beschäftigt hat.
Die TU München ist ja schliesslich
eine unserer Elite Unis.
http://wwwcg.in.tum.de/Download/GPUGems2