c - C语言中的二进制 vector 和矩阵运算

Question

我正在尝试在C中实现一个数据结构，该数据结构将允许我有效地处理二进制矩阵(仅包含1或0)。我将说明我必须对该矩阵执行哪些操作，并想知道什么是最好的数据结构？

这些操作在字段F_2中完成(这意味着1 + 1 = 0，其他操作保持不变)。我有一个称为k的n * k矩阵(n <H)。最多k = 2325和n = 3009。

我将要在此矩阵上执行的操作是:

我将仅使用行交换和行添加将它对角线化。完成后，我将不再使用行操作，并且将在此矩阵上对列表添加进行很多(!)操作(我的意思是“很多”是关于((n-k)/2)³列的添加操作)

我正在考虑用于矩阵的数据结构:

对于矩阵系数，我正在考虑一次将多个位的序列存储在一个无符号int中。例如，我可以将序列(11001011)存储到uint8_t 203(从二进制转换为十进制)

这是个好主意吗？

如果这样做，我有两个选择:

我可以使用uint16_t或uint64_t系数将矩阵H拆分为许多4 * 4或8 * 8子矩阵。

这是一个不错的选择(就时间效率而言)，如果是，那么使用uint16_t或uint64_t会更好吗？

另外，我正在考虑将每一行存储在多个uint32_t或uint64_t中，然后对我的部分对角线进行操作。接下来切换到将矩阵编码为 n列 vector 的结构，以处理其余操作。

您认为这样更有效吗？

无论使用哪种方法，我都必须有效地访问unsigned int(n，uint16或32)的第64个位。我怎么做 ？

Answer 1

为了获得最佳性能，请为行交换和行添加使用行指针数组。使用<stdint.h>和最小受支持字大小的快速无符号整数类型-我建议使用uint_fast32_t，除非您打算在16位或8位处理器上运行它。

完成所有的行交换和行加法后，转置数组。尽管此操作“慢”，但随后的列操作将如此快以抵消转置成本。

考虑以下:

#include <stdint.h>
#include <limits.h>

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

typedef struct {
    int    rows;  /* Number of row vectors */
    int    cols;  /* Number of defined bits in each row */
    int    words; /* Number of words per row vector */
    word **row;   /* Array of pointers */
} row_matrix;

typedef struct {
    int    rows;  /* Number of defined bits in each column */
    int    cols;  /* Number of col vectors */
    int    words; /* Number of words per col vector */
    word **col;
} col_matrix;

尽管您可以使用单个类型来描述这两种矩阵形式，但是使用单独的类型可以使代码和函数更易于维护。您最终将获得一些重复的代码，但是与拥有清晰，直观的类型相比，这是一个小问题。

在32位系统上， uint_fast32_t通常是32位类型。在64位系统上，通常为64位。 WORD_BITS宏扩展为 word中的位数-并不总是32!

对位进行编号的最简单方法是将矩阵中最左边的位指定为位0，并将这些位存储在每个字的最低有效位中。如果您有 row_matrix *rm，那么 row列 col行的位是

!!(rm->row[row][col / WORD_BITS] & ((word)1U << (col % WORD_BITS)))

!!是非运算符:如果参数为非零，则产生1，否则产生0。因为我们从单词中屏蔽了一位，所以“位已设置”值将是2的幂(1 ，2、4、8、16、32、64等)。

要设置位，请使用

rm->row[row][col / WORD_BITS] |= (word)1U << (col % WORD_BITS);

要清除一点，您需要对除目标位1以外的所有掩码进行二进制与运算。使用not运算符 ~可以轻松实现:

rm->row[row][col / WORD_BITS] &= ~((word)1U << (col % WORD_BITS));

col_matrix *cm的相应操作是

!!(cm->col[col][row / WORD_BITS] & ((word)1U << (row % WORD_BITS)))
cm->col[col][row / WORD_BITS] |= (word)1U << (row % WORD_BITS);
cm->col[col][row / WORD_BITS] &= ~((word)1U << (row % WORD_BITS));

尽管 /和模数(或余数) %的划分通常较慢(与加法，减法，甚至是乘法相比)，但 WORD_BITS在所有广泛使用的体系结构上都是两个编译时常数的幂。我所知道的所有编译器都可以将上述内容转换为快速的移位和二进制与运算符。

要将 srcrow行添加到 dstrow行，您只需对所有单词执行二进制异或运算:

{
    const word *const src = rm->row[srcrow];
    word *const       dst = rm->row[dstrow];
    int               w = rm->words;
    while (w-->0)
        dst[w] ^= src[w];
}

类似地，对于列矩阵，

{
    const word *const src = cm->col[srccol];
    word *const       dst = cm->col[dstcol];
    int               w = cm->words;
    while (w-->0)
        dst[w] ^= src[w];
}

请注意，如果合并多于两行，则可以非常高效地完成；比连续进行添加要快得多。 Intel和AMD CPU非常擅长预测上述模式，因此您可以使用多个源行/列。同样，目的地也不必参与结果，尽管如果我正确地猜到您要实现的算法，我想您也希望它参与。

如果您知道目标体系结构具有SSE2或更高版本，甚至是AVX，则可以分别将 emmintrin.h或 immintrin.h头文件用于编译器内置类型和运算符，从而允许您分别对128位和256位进行XOR。 ;有时会给您很大的帮助。

由于 vector 类型需要C标准所说的“过度对齐”，因此您还需要包括 mm_malloc.h，并使用 _mm_malloc()和 _mm_free()为 word数据分配行/列 vector -显然将 words向上舍入，这样您可以将行/列作为合适的整数字类型(对于SSE *为 __m128i，对于AVX为 __m256i)访问行/列。

就个人而言，我总是先实现未矢量化的版本，然后再实现一些“讨厌的”测试用例进行单元测试，然后再实现矢量化。这样做的好处是，您可以将非向量化版本作为使用它的用户的初步版本，并且可以比较向量化和非向量化案例之间的测试用例结果，以查看其中一个是否存在错误。 。

移调操作非常简单，尽管我确实建议使用三重循环:在单个字中的位的最内层循环。另外，您可能想要检查哪种顺序(行或列主音)对外部循环效果最好；根据矩阵大小，您可能会看到巨大的差异。 (这是由于缓存行为所致:您希望CPU能够预测访问模式，而不必重新加载相同的缓存行。在最好的情况下，使用年限最短的AMD和Intel x86- 64个处理器，如果两个矩阵都适合高速缓存，则可以获得接近高速缓存的速度。)

上面所有这些都可以在单个头文件中实现-如果目标体系结构支持SSE2/AVX，甚至可以包括矢量化版本，因此实现起来应该不会太困难。

问题？