Характеристика умножения двоичных матриц на вектор - PullRequest
Новая
       54

Характеристика умножения двоичных матриц на вектор

0 голосов
/ 03 января 2019

Я пытаюсь реализовать матричное векторное умножение над двоичным полем.Вектор x имеет размерность 1xa, а матрица M имеет размерность axb, а результат y = a * M имеет размер 1xb.Прямо сейчас я реализовал это так, что x и M имеют тип uint8_t *, т.е. я объединяю столбцы M, поскольку к ним также осуществляется последовательный доступ.Функция выглядит следующим образом: 

void mul(uint8_t M, size_t a, size_t b, uint8_t* x, uint8_t* y) {
    uint8_t val;
    uint8_t *ptr;
    for(size_t i = 0; i < b; i++) {
        val = 0;
        ptr = M + i * a;
        for(size_t j = 0; j < a; j++) {
            val ^= (x[j] & *ptr++);
        }
        y[i] = bit;
    }
}

M и x были выделены вызывающей стороной как 

M = malloc(sizeof(uint8_t) * a * b);
x = malloc(sizeof(uint8_t) * a);
y = malloc(sizeof(uint8_t) * b);

Поскольку эта процедура вызывается миллиард раз, мне нужно оптимизировать дерьмо изэто;) Чтобы сделать это, я думал о

  • вместо того, чтобы представлять каждый 0/1 как отдельный uint8_t (то есть, 8 бит), я мог бы упаковать все биты в "x" и "M"в массивы uint64_t гораздо меньшего размера, например, ap и Mp, где

ap = (size_t) ceil ((double) a / 64);Mp = (size_t) ceil ((double) (a * b) / 64);

  • с использованием векторных встроенных функций.

До сих пор я выполнил (выровненный по левому краю)) упаковка (при правильном выравнивании) M и умножение на 

typedef uint64_t word;
#define WORD_BITS      (CHAR_BIT * sizeof (word))

void mul_fast(word *M, size_t Mlen, word *x, size_t xlen, size_t b, word *y) {

    for(size_t i = 0; i < Mlen; i++) {
        y[i/xlen] ^= (M[i] & x[i % xlen]);
    }
    for(size_t i = 0; i < b; i++) {
        y[i] = __builtin_popcountll(y[i]) & 1;
    }
}

Однако оказывается, что вышеупомянутое намного медленнее, чем прямая реализация функции mul ().

Doу вас есть идеи или рекомендации?Я не эксперт по ассемблеру, поэтому сравнение вывода gcc -S мне мало что говорит: /

Спасибо, с наилучшими пожеланиями, Том.

1 Ответ

0 голосов
/ 04 января 2019

Соответствующее различие в выводе ассемблера:

.L26: - movq %r10, %rax - xorl %edx, %edx - divq %rcx - movq (%r11,%rdx,8), %rdx - andq (%rdi,%r10,8), %rdx - addq $1, %r10 - xorq %rdx, (%r9,%rax,8) - cmpq %r10, %rsi + movq %rax, %rcx + movq %rax, %r10 + andl $1, %ecx + shrq %r10 + movq (%rdx,%rcx,8), %rcx + andq (%rdi,%rax,8), %rcx + addq $1, %rax + xorq %rcx, (%r9,%r10,8) + cmpq %rax, %rsi Вы видите, кто был виновником?

...