Ich habe binäre Matrizen in C ++, die ich mit einem Vektor von 8-Bit-Werten wiederhole.
Zum Beispiel die folgende Matrix:
%Vor%wird wie folgt dargestellt:
%Vor%Der Grund, warum ich es so mache, ist, weil dann das Berechnen des Produkts einer solchen Matrix und eines 8-Bit-Vektors wirklich einfach und effizient wird (nur eine bitweise UND- und eine Paritätsberechnung pro Zeile) viel besser als jedes Bit einzeln zu berechnen.
Ich suche jetzt nach einer effizienten Möglichkeit, eine solche Matrix zu transponieren, aber ich war nicht in der Lage, herauszufinden, wie es geht, ohne jedes Bit manuell berechnen zu müssen.
Nur um zu verdeutlichen, für das obige Beispiel möchte ich das folgende Ergebnis aus der Umsetzung erhalten:
%Vor%HINWEIS : Ich würde einen Algorithmus bevorzugen, der dies mit beliebig großen Matrizen berechnen kann, aber auch an Algorithmen interessiert bin, die nur bestimmte Größen bewältigen können.
Ich habe mehr Zeit damit verbracht, nach einer Lösung zu suchen, und ich habe einige gute gefunden.
Auf einer modernen x86-CPU kann die Umsetzung einer binären Matrix sehr effizient mit SSE2-Anweisungen durchgeführt werden. Mit solchen Anweisungen ist es möglich, eine 16 × 8-Matrix zu verarbeiten.
Diese Lösung wurde von diesem Blogpost von mischasan inspiriert und ist jedem Vorschlag, den ich bisher zu dieser Frage bekommen habe, weit überlegen.
Die Idee ist einfach:
#include <emmintrin.h> uint8_t Variablen in ein __m128i
_mm_movemask_epi8 , um die MSBs jedes Bytes zu erhalten, was zu einem uint16_t führt.
_mm_slli_epi64 , um das 128-Bit-Register um eins uint16_t s Leider muss ich dies auch mit ARM machen. Nach der Implementierung der SSE2-Version wäre es einfach, nur die NEON-Entsprechungen zu finden, aber die Cortex-M CPU hat (im Gegensatz zu Cortex-A ) keine SIMD-Fähigkeiten, daher ist NEON im Moment für mich nicht sehr nützlich.
HINWEIS : Da das Cortex-M keine native 64-Bit-Arithmetik hat , konnte ich die Ideen in keiner Antwort verwenden das schlägt vor, einen 8x8 Block als uint64_t zu behandeln. Die meisten Mikrocontroller, die eine Cortex-M CPU haben, haben auch nicht so viel Speicher, also bevorzuge ich all dies ohne eine Nachschlagetabelle.
Nach einigem Nachdenken kann derselbe Algorithmus unter Verwendung einfacher 32-Bit-Arithmetik und einiger cleverer Codierung implementiert werden. Auf diese Weise kann ich mit 4 × 8 Blöcken gleichzeitig arbeiten. Es wurde von einem Kollegen vorgeschlagen und die Magie liegt in der Art und Weise, wie die 32-Bit-Multiplikation funktioniert: Sie können eine 32-Bit-Zahl finden, mit der Sie multiplizieren können und dann das MSB jedes Bytes in den oberen 32 Bits von das Ergebnis.
uint8_t s in einer 32-Bit-Variablen 0x80808080 ) 0x02040810
Wenn Sie dies mit zwei 4 × 8 Blöcken machen, dann können Sie einen 8x8 Block erstellen und die resultierenden Bits so arrangieren, dass alles an den richtigen Platz kommt.
Mein Vorschlag ist, dass Sie die Transposition nicht machen, sondern Sie fügen Ihren Matrixdaten ein Bit-Information hinzu, die angibt, ob die Matrix transponiert ist oder nicht.
Wenn Sie nun eine transposierte Matrix mit einem Vektor multiplizieren wollen, ist es dasselbe wie die Matrix links mit dem Vektor zu multiplizieren (und dann zu transponieren). Das ist einfach: nur einige xor Operationen Ihrer 8-Bit-Zahlen.
Dies macht jedoch einige andere Operationen kompliziert (z. B. Hinzufügen von zwei Matrizen). Aber im Kommentar sagen Sie, dass Multiplikation genau das ist, was Sie optimieren möchten.
Mein Vorschlag wäre, eine Nachschlagetabelle zu verwenden, um die Verarbeitung zu beschleunigen.
Es ist noch eine Sache zu beachten, dass bei der aktuellen Definition Ihrer Matrix die maximale Größe 8x8 Bit beträgt. Dies passt in einen uint64_t, so dass wir dies besonders bei einer 64-Bit-Plattform zu unserem Vorteil nutzen können.
Ich habe ein einfaches Beispiel mit einer Nachschlagetabelle ausgearbeitet, die Sie unten finden und verwenden Sie: Ссылка Online-Compiler .
Beispielcode
%Vor%Wie es funktioniert
Ihre 3x8-Matrix wird in eine 8x3-Matrix transponiert, die in einem 8x8-Array dargestellt wird. Das Problem ist, dass Sie Bits, Ihre "horizontale" Darstellung in eine vertikale, über mehrere Bytes verteilt, konvertieren möchten.
Wie bereits erwähnt, können wir die Tatsache nutzen, dass die Ausgabe (8x8) immer in ein uint64_t passt. Wir werden dies zu unserem Vorteil verwenden, da wir jetzt ein uint64_t verwenden können, um das 8-Byte-Array zu schreiben, aber wir können es auch verwenden, um xor usw. hinzuzufügen, weil wir grundlegende arithmetische Operationen an einer 64-Bit-Ganzzahl ausführen können. p>
Jeder Eintrag in Ihrer 3x8-Matrix (Eingabe) ist 8 Bit breit. Um die Verarbeitung zu optimieren, erzeugen wir zunächst eine 256-Eintrag-Nachschlagetabelle (für jeden Byte-Wert). Der Eintrag selbst ist ein uint64_t und wird eine gedrehte Version der Bits enthalten.
Beispiel:
byte = 0b01001111 = 0x4F
lut [0x4F] = 0x0001000001010101 = (uint8_t []) {0, 1, 0, 0, 1, 1, 1, 1}
Nun zur Berechnung:
Für die Berechnungen verwenden wir den uint64_t, aber bedenken Sie, dass es unter Wasser ein Array von uint8_t [8] darstellt. Wir verschieben einfach den aktuellen Wert (beginnend mit 0), suchen unser erstes Byte und fügen es dem aktuellen Wert hinzu.
Die "Magie" hier ist, dass jedes Byte des uint64_t in der Nachschlagetabelle entweder 1 oder 0 ist, so dass es nur das niedrigstwertige Bit (jedes Bytes) setzt. Das Verschieben von uint64_t verschiebt jedes Byte, solange wir sicherstellen, dass dies nicht mehr als acht Mal macht! Wir können Operationen für jedes einzelne Byte ausführen.
Probleme
Wie jemand in den Kommentaren bemerkt hat: Übersetzen (Übersetzen (M))! = M also, wenn Sie das brauchen, brauchen Sie etwas zusätzliche Arbeit.
Perfomance kann verbessert werden, indem man uint64_t anstelle von uint8_t [8] Arrays direkt abbildet, da es eine "sichere Kopie" auslässt, um Ausrichtungsprobleme zu vermeiden.
Ich habe einen neuen Markierer hinzugefügt, anstatt meinen ursprünglichen zu bearbeiten, um diesen besser sichtbar zu machen (leider keine Kommentarrechte).
In Ihrem eigenen Gruss fügen Sie eine zusätzliche Anforderung hinzu, die in der ersten nicht enthalten ist: Es muss auf ARM Cortex-M funktionieren
Ich habe eine alternative Lösung für ARM in meinem ursprünglichen Awnser gefunden, aber weggelassen, da es nicht Teil der Frage war und off Topic erschien (hauptsächlich wegen des C ++ - Tags).
ARM Spezifische Lösung Cortex-M:
Einige oder die meisten Cortex-M 3/4 haben eine Bit-Banding-Region, die für genau das verwendet werden kann, was sie brauchen, sie erweitert Bits in 32-Bit-Felder, diese Region kann für atomare Bitoperationen verwendet werden.
>Wenn Sie Ihr Array in eine bitbanded Region setzen, wird es eine "explodierte" Spiegelung in der Bittband-Region haben, wo Sie einfach die Verschiebungsoperationen für die Bits selbst verwenden können. Wenn Sie eine Schleife erstellen, kann der Compiler sicher entrollen und optimieren, um Operationen einfach zu verschieben.
Wenn Sie wirklich wollen, können Sie sogar einen DMA-Controller einrichten, um einen ganzen Stapel von Transponierungsoperationen mit ein wenig Aufwand zu verarbeiten und vollständig von der CPU zu entfernen:)
Vielleicht hilft Ihnen das noch.
Hier ist der Text von Jay Foads E-Mail an mich bezüglich der schnellen Booleschen Matrix transponieren:
Das Herz des Booleschen Transponieralgorithmus ist eine Funktion, die ich transpose8x8 nennen werde, die eine boolesche 8x8-Matrix in einem 64-Bit-Wort (in der Reihenfolge der Hauptreihenfolge von MSB zu LSB) umsetzt. Um eine rechteckige Matrix zu transponieren, deren Breite und Höhe ein Vielfaches von 8 sind, zerlegen Sie sie in 8x8 Blöcke, transponieren Sie jede einzeln und speichern Sie sie an der entsprechenden Stelle in der Ausgabe. Um einen 8x8-Block zu laden, müssen Sie 8 einzelne Bytes laden und verschieben und ODER in ein 64-Bit-Wort umwandeln. Das Gleiche zum Speichern.
Eine einfache C-Implementierung von transpose8x8 beruht auf der Tatsache, dass alle Bits auf jeder diagonalen Linie parallel zur führenden Diagonalen die gleiche Entfernung nach oben / unten und links / rechts bewegen. Zum Beispiel müssen sich alle Bits gerade oberhalb der führenden Diagonalen um eine Stelle nach links und eine Stelle nach unten bewegen, d. H. Um 7 Bits nach rechts in dem gepackten 64-Bit-Wort. Dies führt zu einem Algorithmus wie folgt:
Dies läuft ungefähr 10x schneller als die vorherige Implementierung, die jedes Bit einzeln aus dem Quellbyte im Speicher kopierte und es in das Zielbyte im Speicher zusammenfügte.
Alternativ können Sie, wenn Sie PDEP- und PEXT-Anweisungen haben, ein perfektes Shuffle implementieren, und das verwenden, um die Transponierung durchzuführen, wie in Hacker's Delight erwähnt. Dies ist wesentlich schneller (aber ich habe keine Zeitpläne zur Hand):
%Vor% POWER vgbbd Instruktion implementiert effektiv die Gesamtheit von transpose8x8 in einem einzelnen Befehl (und da es ein 128-Bit Vektorbefehl ist, macht es dies zweimal unabhängig auf den niedrigen 64 Bits und den hohen 64 Bits). Dies ergab etwa 15% Beschleunigung gegenüber der Plain-C-Implementierung. (Nur 15%, denn obwohl das Bit-Twiddling viel schneller ist, wird die gesamte Laufzeit jetzt durch die Zeit bestimmt, die benötigt wird, um 8 Bytes zu laden und sie in das Argument von transpose8x8 zu assemblieren und das Ergebnis zu speichern und zu speichern 8 separate Bytes.)
Folgendes habe ich auf gitub gepostet (mischasan / sse2 / ssebmx.src) Wenn INP () und OUT () geändert werden, um Induktionsvariablen zu verwenden, wird jeweils ein IMUL gespeichert. AVX256 macht es doppelt so schnell. AVX512 ist keine Option, da es kein _mm512_movemask_epi8 () gibt.
%Vor%HTH.
Das ist ein bisschen spät, aber ich bin gerade über diesen Austausch heute gestolpert. Wenn Sie Hacker's Delight, 2nd Edition betrachten, gibt es mehrere Algorithmen zum effizienten Transponieren von Booleschen Arrays, beginnend auf Seite 141.
Sie sind ziemlich effizient: Ein Kollege von mir hat einen Faktor von etwa 10X erhalten Beschleunigung im Vergleich zu naiven Codierung, auf einem X86.