İkili matris çarpım bit twiddling

Question

Özeti

kesmek

Merhaba, iki farklı bağımsız 64 bit ikili matrisler A ve T (T kendisinin bir aktarılmamıştır versiyonu matris aktarılmış sürümünü kullanarak çalışmasına çarpma esnasında olanak tanır olduğunu varsayalım T 'ın satırları, ikili aritmetik için süper serin olan sütunlar yerine) ve bu matrisleri çoğaltmak istediğinizde, matris çarpma sonucunun, 64 bit'e kesilmesi ve bazı özel değerlerde 1 değerini daha büyük bir değere getirmenizdir. matris hücresi elde edilen matris hücresi, 1, aksi takdirde 0

içerecektir.

Örnek

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

İkili ve geleneksel çarpma sonuçları:

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

Soru

nasıl en verimli konuda yukarıda açıklanan şekilde bu matrisi çarpmak mı?

PS

ben çoğalması için verileri hazırlamak zorunda olduğu durumda, bunun yerine ayrı bit üzerinde çarpma performans ikili and (yani & operatör) yararlanmak çalışıyordu: şimdi

ulong u; 

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

ikili and iki yılı Tamsayılardaki A ve u gerçekleştirerek aşağıdaki boyun olacaktır:

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 

Yukarıdaki örnekte, R, A bitlerinin u bitt çarpımının sonucunu içerir ve son değeri elde etmek için, bir satırdaki tüm bitleri sum olmalıdır. Sütun C'un, yukarıdaki ilk sütunda bulunan değerlere eşit değerler içerdiğine dikkat edin. Yukarıdaki Traditional matris çarpımı.Sorun şu ki, bu adımda alt-optimal yaklaşım olduğunu düşündüğüm ayrı bir bit üzerinde çalışmam gerektiğidir, http://graphics.stanford.edu/~seander/bithacks.html'u okudum, bunun paralel olarak yapılabileceğine dair bir yol arıyorum ama şansınız yok, ,

teşekkür ederim, bana birkaç satır damla eğer 64 bit matrisi çıkan içine R sütunda bulunan değerler, ben takdir ediyorum "birleştirme"

Edit

büyük teşekkür ile "düzleştirmek" ve David Eisenstat'a, son algoritma şöyle görünecektir:

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); 

kod

aşağıdaki parça:

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); 
    } 

beni takip sonuçları gösterir:

00:00:02.4035870 
00:00:57.5147150 

Ve bu Mac OS X/Mono altında bir 23x performans iyileştirme, teşekkürler herkes

Answer 1

Ben en çok verimli konusunda emin değilim, ama burada denemek için bir şey. Aşağıdaki talimat dizisi, A * T 'ürününün ana köşegenini hesaplar. T ve D'yi 8 bitle döndürün ve 7 daha fazla yineleme için tekrarlayın.

// 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

Eğer Yoğun matris çarpmasını paralel olarak yapmak, sonuç matrisini bloklara ayırmak ve her bloğu paralel olarak hesaplamak için bir yol arıyorlar.

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

Answer 3

Size (siz 'herhangi bir dil' dedi evet, biliyorum) hangi dilde kullanıyorsanız ve ne duruma getirmek için çalışıyoruz hangi veri yapısı belli değil (? Belleği hızını?) Vs. hepsi Bunların çözümünüz üzerinde büyük etkisi olabilir.

Bazı örnekler:

• bu C/C++ oldu varsayalım ve matrisler bellekte bitlerini devam bulunmaktadır. Her satır/sütun UINT8 ile eşleşir. Bu durumda, bir satırın bir sütunla çarpılması 8 bitlik bir bit - & yapmakta ve sonucun 0'dan büyük olup olmadığını kontrol etmektedir (bitleri toplamamaya gerek yoktur). Bu 2 işlemci talimatı alır.
• Bit-by-bit işlemleri yapmak zorunda kalıyorsanız, + yerine bitwise 'veya' (|) kullanın. Bazı diller bu durumu değerlendirebilir, karşılaştıkları ilk '1' de dururlar.
• Çok iş parçacığı yapabiliyorsanız, hesaplamaları hızlandırabilirsiniz.

BTW, yoksa ben direk ve okunabilir kodu kullanabilirsiniz olur, sen çok işlemek için matrislerin var varsayıyorum. Tahminimce, birçok matrisle bile, performanstaki kazanım göz ardı edilebilir.