Hallo Forum,
Ich suche einen Algorithmus der mir in einem Array, Elemente die eine
Bedingung erfüllen an den Anfang des Arrays bringt. Soweit wäre das ja
noch ganz einfach, allerdings soll der Algorithmus auf einer SIMD
Architekture (genauer GPU via OpenCL) effizient laufen.
Die Struktur des Arrays schaut beispielhaft so aus:
1 | [XXXOOOOO|XOOOOOOO|OOOOOOOO|XXXXXXX]
|
und es soll folgendermaßen aus dem Algorithmus herauskommen:
1 | [XXXXXXXX|XXXXOOOO|OOOOOOOO|OOOOOOOO]
|
Folgende Randbedingungen gibt es:
Die Elemente mit X sollen also an den Anfang, was mit den O Elementen
passiert ist nicht wichtig, sie können auch verworfen werden.
Die Reihenfolge der X Elemente ist nicht wichtig.
Die X Elemente starten immer am Anfang eines mit "|" begrenzten Blocks,
diese Blöcke sind in der Realität 16 Elemente lang.
Die Anzahl der X Elemente in einem mit "|" begrenztem Block ist bekannt
und kann von 0 bis 16 Schwanken.
Der Algorithmus muss nicht unbedingt in place sein, zuviel zusätlicher
Speicher steht allerdings nicht zur Verfügung.
Über Google bin ich auf den
Bitonic-Sort(https://en.wikipedia.org/wiki/Bitonic_sorter) Algorithmus
gestoßen, dieser scheint für parallele Verarbeitung gut geeignet zu
sein, aber er sortiert halt komplett, was ich nicht benötige. Geht das
mit meinen zusätzlichen Randbedingungen schneller als mit dem Bitonic
Sort? Ist mein Problem 100% Äquivalent zum kompletten sortieren wo es
bei jedem Element auf die Reihenfolge ankommt?
lg
derMosphet
