Ich verwende eine Variation eines 5-Kreuz-Medianfilters für Bilddaten auf einem kleinen eingebetteten System, d. H.
x
x x x
x
Der Algorithmus ist wirklich einfach: Lesen Sie 5 vorzeichenlose Ganzzahlwerte, erhalten Sie die höchsten 2, führen Sie einige Berechnungen durch und schreiben Sie das vorzeichenlose Ganzzahlergebnis zurück.
Das Schöne ist, dass die 5 ganzzahligen Eingabewerte alle im Bereich von 0 bis 20 liegen. Der berechnete ganzzahlige Wert liegt ebenfalls im Bereich von 0 bis 20!
Durch die Profilerstellung habe ich herausgefunden, dass das Erhalten der zwei größten Zahlen der Engpass ist, daher möchte ich diesen Teil beschleunigen. Was ist der schnellste Weg, um diese Auswahl durchzuführen?
Der aktuelle Algorithmus verwendet eine 32-Bit-Maske mit 1 an der durch die 5 Zahlen angegebenen Position und eine HW-unterstützte CLZ-Funktion.
Ich sollte sagen, dass es sich bei der CPU um eine proprietäre CPU handelt, die außerhalb meines Unternehmens nicht verfügbar ist. Mein Compiler ist GCC, aber maßgeschneidert für diese CPU.
Ich habe versucht herauszufinden, ob ich eine Nachschlagetabelle verwenden kann, aber ich konnte keinen Schlüssel generieren, den ich verwenden kann.
Ich habe Kombinationen für die Eingabe, aber die Reihenfolge ist nicht wichtig, dh ist die gleiche wie .[5,0,0,0,5]
[5,5,0,0,0]
Es kommt vor, dass die unten stehende Hash-Funktion einen perfekten Hash ohne Kollisionen erzeugt!
def hash(x):
h = 0
for i in x:
h = 33*h+i
return h
Aber der Hash ist riesig und es gibt einfach nicht genug Speicher, um das zu nutzen.
Gibt es einen besseren Algorithmus, den ich verwenden kann? Ist es möglich, mein Problem mithilfe einer Nachschlagetabelle zu lösen und einen Schlüssel zu generieren?
quelle
hash
führt bereits weitere Operationen aus. Beziehen sich nachfolgende Aufrufe der Methode darauf, z. B.x
bewegt sich die Zentrale zeilenweise durch die Matrix?Antworten:
In meiner anderen Antwort schlage ich vor, dass bedingte Sprünge das Haupthindernis für die Effizienz sein könnten. Infolgedessen kommen Sortiernetzwerke in den Sinn: Sie sind datenunabhängig, dh die gleiche Folge von Vergleichen wird unabhängig von der Eingabe ausgeführt, wobei nur die Swaps bedingt sind.
Das Netzwerk, das er in den Lösungen angibt (umgeschrieben in Null-basierte Arrays), ist
welches implementiert - nach dem Anpassen der Richtung der Vergleiche - in Pseudocode als
Jetzt haben naive Implementierungen immer noch bedingte Sprünge (über den Swap-Code). Abhängig von Ihrer Maschine können Sie sie jedoch mit bedingten Anweisungen umgehen. x86 scheint sein übliches Mudpit-Selbst zu sein; ARM sieht vielversprechender aus, da anscheinend die meisten Operationen an sich bedingt sind. Wenn ich die Anweisungen richtig verstehe , wird der erste Austausch in diese übersetzt, vorausgesetzt, unsere Array-Werte wurden in Register geladen
R0
durchR4
:Ja, ja, natürlich können Sie den XOR-Austausch mit EOR verwenden .
Ich hoffe nur, dass Ihr Prozessor dies oder ähnliches hat. Natürlich, wenn Sie bauen die Sache zu diesem Zweck, vielleicht können Sie das Netzwerk fest verdrahtet bekommen dort?
Dies ist wahrscheinlich (nachweislich?) Das Beste, was Sie im klassischen Bereich tun können, dh ohne die begrenzte Domäne zu nutzen und böse Intra-Word-Magie auszuführen.
quelle
Nur damit es auf dem Tisch liegt, hier ein direkter Algorithmus:
Durch geschickte Implementierung von
if ... else
kann man einige bedingungslose Sprünge beseitigen, die eine direkte Übersetzung haben würde.Das ist hässlich, dauert aber nur
Es ist jedoch nicht zu erwarten, dass dies bei Maschinen mit Pipelining schnell ist. Angesichts des hohen Prozentsatzes an bedingten Sprüngen würde die meiste Zeit wahrscheinlich im Stall verbracht werden.
Beachten Sie, dass eine einfachere Variante - sortieren
x1
undx2
anschließend die anderen Werte einfügen - vier bis sieben Vergleiche und nur fünf bis sechs Zuweisungen erfordert. Da ich davon ausgehe, dass Sprünge hier teurer sind, habe ich mich an diesen gehalten.quelle
Dies könnte eine großartige Anwendung und ein Testfall für das Souper-Projekt sein . Souper ist ein Superoptimierer - ein Tool, das eine kurze Codesequenz als Eingabe verwendet und versucht, diese so weit wie möglich zu optimieren (versucht, eine äquivalente Codesequenz zu finden, die schneller ist).
Souper ist Open Source. Sie können versuchen, Souper auf Ihrem Code-Snippet auszuführen, um zu sehen, ob es besser funktioniert.
Siehe auch John Regehrs Wettbewerb zum Schreiben von schnellem Code zum Sortieren von 16 4-Bit-Werten . Es ist möglich, dass einige der dortigen Techniken nützlich sind.
quelle
T[T[T[441*a+21*b+c]*21+d]*21+e]
quelle