Блог

В настоящее время я пытаюсь написать алгоритм для оптимизации умножения матриц над GF (2) с использованием упаковки битов. Обе матрицы A и B представлены в основном порядке столбцов, поэтому я начинаю с копирования A в основной порядок строк, а затем упаковываю значения в 8-разрядные целые числа и использую проверку на четность для ускорения операций. Мне нужно иметь возможность тестировать квадратные матрицы размером до 2048×2048, однако моя текущая реализация выдает правильный ответ размером до 24×24, а затем не может вычислить правильный результат. Любая помощь была бы оценена.

 //Method which packs an array of integers into 8 bits
uint8_t pack(int *toPack) {
    int i;
    uint8_t A;
    A = 0;
    for (i = 0; i < 8; i  ) {
        A = (A << 1) | (uint8_t)toPack[i];
    }
    return A;
}

//Method for doing matrix multiplication over GF(2)
void matmul_optimized(int n, int *A, int *B, int *C) {
    int i, j, k;
    //Copying values of A into a row major order matrix.
    int *A_COPY = malloc(n * n * sizeof(int));
    int copy_index = 0;
    for (i = 0; i < n; i  ) {
        for (j = 0; j < n; j  ) {
            A_COPY[copy_index] = A[i   j * n];
            copy_index  ;
        }
    }
    //Size of the data data type integers will be packed into
    const int portion_size = 8;
    int portions = n / portion_size;

    //Pointer space reserved to store packed integers in row major order
    uint8_t *compressedA = malloc(n * portions * sizeof(uint8_t));
    uint8_t *compressedB = malloc(n * portions * sizeof(uint8_t));

    int a[portion_size];
    int b[portion_size];
    for (i = 0; i < n; i  ) {
        for (j = 0; j < portions; j  ) {
            for (k = 0; k < portion_size; k  ) {
                a[k] = A_COPY[i * n   j * portion_size   k];
                b[k] = B[i * n   j * portion_size   k];
            }
            compressedA[i * n   j] = pack(a);
            compressedB[i * n   j] = pack(b);
        }
    }

    //Calculating final matrix using parity checking and XOR on A and B
    int cij;
    for (i = 0; i < n;   i) {
        for (j = 0; j < n;   j) {
            int cIndex = i   j * n;
            cij = C[cIndex];
            for (k = 0; k < portions;   k) {
                uint8_t temp = compressedA[k   i * n] amp; compressedB[k   j * n];
                temp ^= temp >> 4;
                temp ^= temp >> 2;
                temp ^= temp >> 1;
                uint8_t parity = temp amp; (uint8_t)1;
                cij = cij ^ parity;
            }
            C[cIndex] = cij;
        }
    }
    free(compressedA);
    free(compressedB);
    free(A_COPY);
}
  

У меня есть два замечания:

• вероятно, вам следует инициализировать cij на 0 вместо cij = C[cIndex]; . Кажется неправильным обновлять целевую матрицу вместо сохранения результата A * B . Ваш код может работать для небольших матриц по совпадению, потому что целевая матрица C состоит из нулей для этого размера.

• рискованно вычислять размер выделения как, malloc(n * n * sizeof(int)); потому что n * n может произойти переполнение на int n if int меньше, чем size_t . Учитывая размеры, с которыми вы работаете, здесь, вероятно, это не проблема, но рекомендуется всегда использовать sizeof в качестве первого операнда для принудительного преобразования в size_t из следующих:

   int *A_COPY = malloc(sizeof(*A_COPY) * n * n);