Binary Matrix-Multiplikation Bit twiddling hacken

Question

Abstrakt

Hallo, nehme an, Sie haben zwei verschiedene unabhängige 64-Bit-Binärmatrizen A und T (T ist eine transponierte Version von sich selbst, ermöglicht die transponierte Version der Matrix während der Multiplikation zu bedienen auf T 's Zeilen anstelle von Spalten, die für Binärarithmetik super cool ist) und Sie diese Matrizen multiplizieren möchten, ist das einzige Ding, dass Matrixmultiplikation Ergebnis auf 64-Bits abgeschnitten ist und wenn Sie zu einem Wert größer als 1 in einigen bestimmten Matrixzelle enthält die resultierende Matrixzelle 1, ansonsten 0

Beispiel

A  T 
00000001 01111101 
01010100 01100101 
10010111 00010100 
10110000 00011000 <-- This matrix is transposed 
11000100 00111110 
10000011 10101111 
11110101 11000100 
10100000 01100010 

Binary und traditionelle Multiplikationsergebnisse:

Binary Traditional 
11000100 11000100 
11111111 32212121 
11111111 32213421 
11111111 21112211 
11101111 221
11001111 11001311 
11111111 54213432 
11001111 11001211 

Frage

Wie multiplizieren Sie diese Matrizen in einer Art und Weise oben in effizientesten Materie beschrieben?

PS

Ich habe versucht, den Vorteil von binären and (dh & Operator) zu nehmen, anstatt Multiplikation auf separaten Bits durchgeführt wird, in diesem Fall I-Daten für die Multiplikation vorbereiten musste:

ulong u; 

u = T & 0xFF; 
u = (u << 00) + (u << 08) + (u << 16) + (u << 24) 
    + (u << 32) + (u << 40) + (u << 48) + (u << 56); 

jetzt durch Ausführen einer binären and über zwei ganzen Zahlen A und u würde es folgende Ausbeute:

A  u  R  C 
00000001 01111101 00000001 1 
01010100 01111101 01010100 3 
10010111 01111101 00010101 3 
10110000 01111101 00110000 2 
11000100 01111101 01000100 2 
10000011 01111101 00000001 1 
11110101 01111101 01110101 5 
10100000 01111101 00100000 1 

Im obigen Beispiel enthält R das Ergebnis der Multiplikation von A Bits mit u Bits und um den endgültigen Wert zu erhalten, müssen wir sum alle Bits in einer Zeile. Beachten Sie, dass die Spalte C Werte enthält, die denen entsprechen, die in der ersten Spalte der resultierenden Traditional Matrixmultiplikation gefunden wurden.Das Problem ist, dass während dieses Schrittes ich auf einem separaten Bit operieren muss, was ich für suboptimalen Ansatz halte. Ich habe http://graphics.stanford.edu/~seander/bithacks.html gelesen, um einen Weg zu finden, dies parallel zu tun, aber kein Glück, wenn jemand eine Idee hat wie zu „glättet“ und „merge“ die in R Spalt befanden Werte in resultierenden 64-Bit-Matrix, würde ich mich freuen, wenn Sie mir mehrere Linien fallen,

Danke,

bearbeiten

Mit großem Dank Sie zu David Eisenstat, der endgültige Algorithmus würde dann wie folgt aussehen:

var A = ...; 
var T = ...; // T == transpose(t), t is original matrix, algorithm works with transposed matrix 

var D = 0x8040201008040201UL; 

U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56); 
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56); 
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56); 
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56); 
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56); 
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56); 
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); T = (T << 8) | (T >> 56); D = (D << 8) | (D >> 56); 
U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & D); 

Das folgende Stück Code:

public static void Main (string[] args){ 
     ulong U; 
     var Random = new Xor128(); 

     var timer = DateTime.Now; 

     var A = Random.As<IUniformRandom<UInt64>>().Evaluate(); 
     var T = Random.As<IUniformRandom<UInt64>>().Evaluate(); 

     var steps = 10000000; 

     for (var i = 0; i < steps; i++) { 
      ulong r = 0; 

      var d = 0x8040201008040201UL; 

      U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56); 
      U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56); 
      U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56); 
      U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56); 
      U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56); 
      U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56); 
      U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); T = (T << 8) | (T >> 56); d = (d << 8) | (d >> 56); 
      U = A & T; U |= U >> 1; U |= U >> 2; U |= U >> 4; U &= 0x0101010101010101UL; U = (U << 8) - U; r |= (U & d); 
     } 

     Console.WriteLine (DateTime.Now - timer); 


     var m1 = new Int32[8,8]; 
     var m2 = new Int32[8,8]; 
     var m3 = new Int32[8,8]; 

     for (int row = 0; row < 8; row++) { 
      for (int col = 0; col < 8; col++) { 
       m1 [row, col] = Random.As<IUniformRandom<Int32>>().Evaluate(0, 1); 
       m2 [row, col] = Random.As<IUniformRandom<Int32>>().Evaluate(0, 1); 
       m3 [row, col] = Random.As<IUniformRandom<Int32>>().Evaluate(0, 1); 
      } 
     } 

     timer = DateTime.Now; 

     for (int i = 0; i < steps; i++) { 
      for (int row = 0; row < 8; row++) { 
       for (int col = 0; col < 8; col++) { 
        var sum = 0; 

        for (int temp = 0; temp < 8; temp++) { 
         sum += m1 [row, temp] * m2 [temp, row]; 
        } 

        m3 [row, col] = sum; 
       } 
      } 
     } 

     Console.WriteLine (DateTime.Now - timer); 
    } 

mir zeigt folgende Ergebnisse:

00:00:02.4035870 
00:00:57.5147150 

Und das ist eine 23x Leistungssteigerung unter Mac OS X/Mono, dankt allen

Answer 1

Ich bin nicht sicher über meisten effizient, aber hier ist etwas zu versuchen. Die folgende Befehlsfolge berechnet die Hauptdiagonale des Produkts A * T '. Drehen Sie T und D um 8 Bits und wiederholen Sie sie für weitere 7 Iterationen.

// uint64_t A, T; 
uint64_t D = UINT64_C(0x8040201008040201); 
uint64_t P = A & T; 
// test whether each byte is nonzero 
P |= P >> 1; 
P |= P >> 2; 
P |= P >> 4; 
P &= UINT64_C(0x0101010101010101); 
// fill each nonzero byte with ones 
P *= 255; // or P = (P << 8) - P; 
// leave only the current diagonal 
P &= D; 

Answer 2

Wenn Sie suchen nach einer Möglichkeit, eine dichte Matrixmultiplikation parallel durchzuführen, partitionieren Sie Ihre Ergebnismatrix in Blöcke und berechnen Sie jeden Block parallel.

http://en.wikipedia.org/wiki/Block_matrix#Block_matrix_multiplication

Answer 3

Es ist nicht klar, welche Datenstruktur Sie verwenden, die Sprache (ja, ich weiß, Sie sagten ‚jede Sprache‘), und was Sie versuchen, zu optimieren (Geschwindigkeit? Gedächtnis?) Usw. All Diese können einen tiefgreifenden Einfluss auf Ihre Lösung haben.

Einige Beispiele:

• Sagen Sie dieses C/C++ ist, und Ihre Matrizen sind Bits im Speicher fortgesetzt. Jede Zeile/Spalte wird einem UINT8 zugeordnet. In diesem Fall wird das Multiplizieren einer Zeile mit einer Spalte auf ein bitweises 8-Bit-Bit 0-reduziert und überprüft, ob das Ergebnis größer als 0 ist (die Summe der Bits muss nicht addiert werden). Dies erfordert 2 Prozessoranweisungen.
• Wenn Sie Bit-für-Bit-Operationen erzwingen müssen, verwenden Sie die bitweise 'oder' (|) anstelle von +. Einige Sprachen können dies faul bewerten und bei der ersten "1" stoppen, auf die sie stoßen.
• Wenn Sie mehrere Threads verwenden können, können Sie die Berechnungen beschleunigen.

BTW, ich nehme an, Sie viele von Matrizen zu verarbeiten haben, sonst habe ich einen direkten verwenden und lesbaren Code. Meine Vermutung ist, dass selbst bei vielen Matrizen der Leistungsgewinn vernachlässigbar wäre.