Wenn wir einen Vektor der Größe N haben, der zuvor sortiert wurde, und ersetzen Sie M -Elemente mit beliebigen Werten (wobei M ist) viel kleiner als N ), gibt es eine einfache Möglichkeit, sie zu niedrigeren Kosten (dh ein Sortiernetzwerk mit reduzierter Tiefe) neu zu sortieren als eine vollständige Sortierung?
Wenn zum Beispiel N = 10 und M = 2 ist, könnte die Eingabe
sein %Vor%Hinweis: Die Indizes der modifizierten Elemente sind nicht bekannt (bis wir sie mit den umgebenden Elementen vergleichen).
Hier ist ein Beispiel, wo ich die Lösung kenne, weil die Eingabegröße klein ist und ich sie mit einer Brute-Force-Suche finden konnte:
Wenn N = 5 und M 1 ist, wären dies gültige Eingaben:
%Vor% Zum Beispiel kann die Eingabe 0 1 1 0 1 sein, wenn der vorher sortierte Vektor 0 1 1 1 1 war und das vierte Element wurde modifiziert, aber es gibt keine Möglichkeit, 0 1 0 1 0 als gültige Eingabe zu bilden, weil sie sich in mindestens 2 unterscheidet Elemente aus jedem sortierten Vektor.
Dies wäre ein gültiges Sortiernetzwerk zum Umsortieren dieser Eingaben:
%Vor% Es ist uns egal, dass dieses Netzwerk einige ungültige Eingaben nicht sortiert (z. B. 0 1 0 1 0 .)
Und dieses Netzwerk hat Tiefe 4, eine Einsparung von 1 verglichen mit dem allgemeinen Fall ( eine Tiefe von 5 im Allgemeinen notwendig, um ein 5-Element zu sortieren Vektor .)
Leider ist der Brute-Force-Ansatz für größere Eingabegrößen nicht möglich.
Gibt es eine bekannte Methode zum Erstellen eines Netzwerks, um einen größeren Vektor neu zu sortieren?
Meine N Werte liegen in der Größenordnung von einigen hundert, wobei M nicht viel mehr als √ N ist.
Ok, ich poste dies als Antwort, da die Länge der Kommentarbeschränkung mich verrückt macht:)
Sie sollten das ausprobieren:
clGetDeviceInfo mit CL_DEVICE_LOCAL_MEM_SIZE ) und leiten Sie die maximale Anzahl der Arbeitselemente pro Arbeitsgruppe ab,
weil bei diesem Ansatz die Anzahl der Arbeitselemente höchstwahrscheinlich durch die Menge an lokalem Speicher begrenzt ist. Das wird wahrscheinlich ziemlich gut funktionieren, vermute ich, weil:
Lass es mich wissen, wenn du Probleme mit meinen Ideen hast.
Ich habe gerade festgestellt, dass ich eine Technik benutzt habe, die für andere verwirrend sein könnte: Mein Vorschlag für lokalen Speicher verwenden ist nicht für die Synchronisierung oder die Verwendung mehrerer Arbeitselemente für einen einzelnen Eingabevektor / Array. Ich benutze es einfach, um eine niedrige Lese- / Schreibspeicherlatenz zu erhalten. Da wir ziemlich große Teile des Speichers verwenden, befürchte ich, dass die Verwendung von privatem Speicher dazu führen kann, dass der Austausch des globalen Speichers verlangsamt wird, ohne dass wir es merken. Dies bedeutet auch, dass Sie lokalen Speicher für jedes Arbeitselement zuweisen müssen . Jedes Arbeitselement greift auf seinen eigenen Teil des lokalen Speichers zu und verwendet es zum Sortieren (ausschließlich). Ich bin mir nicht sicher, wie gut diese Idee ist, aber ich habe gelesen, dass zu viel privater Speicher den globalen Speicher wechseln kann und der einzige Weg, dies zu bemerken, ist die Leistung (nicht sicher, ob ich recht habe) ).
Hier ist ein Algorithmus, der sehr gute Sortiernetze ergeben sollte. Wahrscheinlich nicht das absolut beste Netzwerk für alle Eingabegrößen, aber hoffentlich gut genug für praktische Zwecke.
Alle diese Schritte können künstlich ausgeführt werden, und die Vergleiche werden in einem Master-Netzwerk gespeichert, anstatt auf die Daten zu wirken.
Es ist erwähnenswert, dass die (bitonischen) Netzwerke von # 2 parallel betrieben werden können, und die kleineren werden zuerst beendet. Das ist gut, denn wenn sie fertig sind, können die Netzwerke von # 5-6 mit der Ausführung beginnen.
Tags und Links sorting sorting-network