Forum: Digitale Signalverarbeitung / DSP / Machine Learning Array "sortieren" mit SIMD Architektur


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von derMosphet (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.