Hat jemand irgendwelche Gedanken darüber, wie man den Modus (Statistik) eines Vektors von 8-Bit-Ganzzahlen in SSE4.x berechnet? Um dies zu verdeutlichen, wären dies 16x8-Bit-Werte in einem 128-Bit-Register.
Ich möchte das Ergebnis als eine Vektormaske, die die modalenwertigen Elemente auswählt. h. das Ergebnis von _mm_cmpeq_epi8(v, set1(mode(v))) , sowie der Skalarwert.
Bereitstellen eines zusätzlichen Kontextes; Während das oben genannte Problem ein interessantes Problem ist, habe ich die meisten Algorithmen mit linearer Komplexität durchgespielt. Diese Klasse löscht alle Gewinne, die ich durch die Berechnung dieser Zahl erhalten kann.
Ich hoffe, euch alle auf der Suche nach tiefer Magie zu beschäftigen. Es ist möglich, dass eine Annäherung notwendig sein kann, um diese Grenze zu brechen, wie zum Beispiel "Wählen Sie ein häufig vorkommendes Element" (NB Unterschied gegen das meiste ), das wäre verdienen. Eine probabilistische Antwort wäre ebenfalls brauchbar.
SSE und x86 haben eine sehr interessante Semantik. Es kann sich lohnen, einen Superoptimierungs-Pass zu erkunden.
Wahrscheinlich ist hier ein relativ einfacher Brute-Force-SSEx-Ansatz geeignet, siehe Code unten.
Die Idee besteht darin, den Eingangsvektor v um 1 bis 15 Positionen zu rotieren und den gedrehten Vektor zu vergleichen
mit dem ursprünglichen v für die Gleichheit. Um die Abhängigkeitskette zu verkürzen und die
Parallelität auf Anweisungsebene, zwei Zähler werden verwendet, um diese gleichen Elemente zu zählen (vertikale Summe):
sum1 und sum2 , weil Architekturen davon profitieren könnten.
Gleiche Elemente werden als -1 gezählt. Die Variable sum = sum1 + sum2 enthält die Gesamtzahl mit Werten
zwischen -1 und -16. min_brc enthält das horizontale Minimum von sum , das an alle Elemente gesendet wird.
mask = _mm_cmpeq_epi8(sum,min_brc) ist die Maske für die als a angeforderten modalenwertigen Elemente
Zwischenergebnis vom OP. In den nächsten Zeilen des Codes wird der aktuelle Modus extrahiert.
Diese Lösung ist sicherlich schneller als eine skalare Lösung. Beachten Sie, dass mit AVX2 die oberen 128-Bit-Spuren verwendet werden können, um die Berechnung weiter zu beschleunigen.
Es dauert 20 Zyklen (Durchsatz), um nur die a-Maske für die modalenwertigen Elemente zu berechnen. Mit dem tatsächlichen Modus ausgestrahlt über das SSE-Register dauert es etwa 21,4 Zyklen.
Beachten Sie das Verhalten im nächsten Beispiel:
[1, 1, 3, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] gibt mask=[-1,-1,-1,-1,0,0,...,0] zurück
und der Moduswert ist 1, obwohl 1 so oft wie 3 auftritt.
Der folgende Code ist getestet, aber nicht gründlich getestet
%Vor%Ausgabe:
%Vor%Das horizontale Minimum wird mit Evgeny Kluevs Methode berechnet.
Sortieren Sie die Daten im Register. Die Einfügesortierung kann in 16 (15) Schritten durchgeführt werden, indem das Register auf "Infinity" initialisiert wird, was versucht, ein monoton fallendes Array zu veranschaulichen und das neue Element parallel zu allen möglichen Stellen einzufügen:
%Vor% Berechnen Sie dann die Maske für vec[n+1] == vec[n] , verschieben Sie die Maske in das GPR und verwenden Sie diese, um eine 32768-Eingabe-LUT für die beste Indexposition zu indizieren.
Im echten Fall möchte man wahrscheinlich mehr als nur einen Vektor sortieren; d. h. 16 16-Eintrittsvektoren gleichzeitig sortieren;
%Vor%Die innere Schleife beläuft sich auf amortisierte Kosten von 7-8 Anweisungen pro Ergebnis; Das Sortieren hat typischerweise 2 Anweisungen pro Stufe - d. H. 8 Anweisungen pro Ergebnis, wenn 16 Ergebnisse 60 Stufen oder 120 Anweisungen benötigen. (Dies lässt die Transponierung immer noch als Übung - aber ich denke, es sollte viel schneller als das Sortieren sein?)
Also sollte dies im Ballpark von 24 Anweisungen pro 8-Bit-Ergebnis sein.
Für den Leistungsvergleich mit Skalarkode. Nicht-vektorisiert auf Hauptteil, aber vektorisiert auf Tabellen-clear und tmp-Initialisierung. (168 Zyklen pro f () -Ruf für fx8150 (22M-Aufrufe in 1.0002 Sekunden bei 3,7 GHz abgeschlossen))
%Vor%g ++ 6.3 Ausgabe:
%Vor%