So schnell wie möglich die zwei größten von fünf kleinen ganzen Zahlen finden

9

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 .215[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?

Fredrik Pihl
quelle
1
Welchen Algorithmus verwenden Sie derzeit? Sieben ganzzahlige Vergleiche reichen aus, ist das zu langsam? Ihr hashführt bereits weitere Operationen aus. Beziehen sich nachfolgende Aufrufe der Methode darauf, z. B. xbewegt sich die Zentrale zeilenweise durch die Matrix?
Raphael
Der Filter wird zeilenweise durch das Bild gefaltet. Dh die 5 Werte erhalten und die Berechnungen durchführen, dann alles einen Schritt nach rechts verschieben und wiederholen. Der Hash war nur ein Beispiel. Ich habe mehrere Schiebefensterlösungen verglichen, um das Lesen von Daten zu minimieren, aber alles läuft darauf hinaus, die höchsten 2 Werte zu finden.
Fredrik Pihl
3
Höchstwahrscheinlich wäre Ihr Algorithmus bei ordnungsgemäßer Implementierung durch Speicherzugriff und nicht durch Berechnung begrenzt. Die Verwendung einer Hashtabelle würde nur die Anzahl der Speicherzugriffe erhöhen und die Geschwindigkeit verringern. Bitte posten Sie Ihren aktuellen Code, damit wir sehen können, wie er verbessert werden kann. Ich glaube, dass nur eine Mikrooptimierung möglich ist. Das Beste, woran ich denken kann, ist: Vielleicht können wir die Tatsache ausnutzen, dass zwei Werte zwischen benachbarten Fenstern gemeinsam sind?
JKFF
@jkff Abhängig von Matrix, Cache-Größe und (Cache-) Zuordnungsfunktion muss jeder Wert möglicherweise nur einmal geladen werden. Die meisten Operationen sollten dann auf Registern oder im L1-Cache ausgeführt werden. Pipelining ist jedoch ein weiteres Problem.
Raphael
1
Tun Sie das übrigens schon parallel? Dies scheint besonders für die Vektorparallelisierung oder SIMD (z. B. auf einer GPU) geeignet zu sein. Diese Route würde viel mehr helfen, als ein paar Prozent pro Zelle zu sparen.
Raphael

Antworten:

11

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.

U.^2(5)=6

Das Netzwerk, das er in den Lösungen angibt (umgeschrieben in Null-basierte Arrays), ist

[0::4]][1::4]][0::3]][1::3]][0::2]][1::2]]

welches implementiert - nach dem Anpassen der Richtung der Vergleiche - in Pseudocode als

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

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 R0durch R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

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.


  1. Sortieren und Suchen von Donald E. Knuth; Die Kunst der Computerprogrammierung Vol. 3 (2. Auflage, 1998)
  2. W.^2(5)=7
Raphael
quelle
Ich akzeptiere das. Ich habe viele neue Ideen erhalten, die ich bewerten muss, bevor ich weitermache. Sich auf Knuth zu beziehen funktioniert immer für mich :-) Vielen Dank für Ihre Mühe und Zeit!
Fredrik Pihl
@FredrikPihl Cool, bitte lass uns wissen, wie es am Ende ausgeht!
Raphael
Ich werde! Lesen Sie jetzt Kapitel 5.3.3. Ich liebe den Start mit Hinweisen auf Lewis Carroll und das Tennisturnier :-)
Fredrik Pihl
2
Abhängig vom Befehlssatz kann die Verwendung von 2 * max (a, b) = a + b + abs (ab) zusammen mit dem Auswahlnetzwerk nützlich sein. Es könnte weniger kostspielig sein als unvorhersehbare bedingte Sprünge (auch ohne eine intrinsische oder bedingte Bewegung für abs: gcc, zumindest für x86, wird eine jumpless-Sequenz generiert, die nicht von x86 abhängig zu sein scheint). Eine übersichtliche Sequenz ist auch in Kombination mit SIMD oder einer GPU nützlich.
AProgrammer
4

Nur damit es auf dem Tisch liegt, hier ein direkter Algorithmus:

// Sort x1, x2
if x1 < x2
  M1 = x2
  m1 = x1
else
  M1 = x1
  m1 = x2
end

// Sort x3, x4
if x3 < x4
  M2 = x4
  m2 = x3
else
  M2 = x3
  m2 = x4
end

// Pick largest two
if M1 > M2
  M3 = M1
  if m1 > M2
    m3 = m1
  else
    m3 = M2
  end
else
  M3 = M2
  if m2 > M1
    m3 = m2
  else
    m3 = M1
  end
end

// Insert x4
if x4 > M3
  m3 = M3
  M3 = x4
else if x4 > m3
  m3 = x4
end

Durch geschickte Implementierung von if ... elsekann man einige bedingungslose Sprünge beseitigen, die eine direkte Übersetzung haben würde.

Das ist hässlich, dauert aber nur

  • fünf oder sechs Vergleiche (dh bedingte Sprünge),
  • neun bis zehn Zuordnungen (mit 11 Variablen, alle in Registern) und
  • Kein zusätzlicher Speicherzugriff.

W.2(5)

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 x1und x2anschließ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.


  1. Sortieren und Suchen von Donald E. Knuth; Die Kunst der Computerprogrammierung Vol. 3 (2. Auflage, 1998)
Raphael
quelle
Ich frage mich, was ein optimierender Compiler damit anfangen kann.
Raphael
Ich werde dies implementieren und es mit der aktuellen CLZ-basierten Lösung vergleichen. Vielen Dank für Ihre Zeit!
Fredrik Pihl
1
@FredrikPihl Was war das Ergebnis Ihrer Benchmarks?
Raphael
1
SWAP-basierter Ansatz schlägt CLZ! Jetzt mobil. Kann ein weiteres Mal mehr Daten posten, jetzt auf dem Handy
Fredrik Pihl
@FredrikPihl Cool! Ich bin froh, dass der gute Ansatz der alten Theorie (noch) von praktischem Nutzen sein kann. :)
Raphael
4

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.

DW
quelle
Mich würde interessieren, was dies für die Programme tun kann, die das OP versucht hat.
Raphael
3

213

T[T[T[441*a+21*b+c]*21+d]*21+e]

214

212

212

Yuval Filmus
quelle