C中的填充矩阵

Question

我尝试使用 SSE 转置我的矩阵。但它只能适合N可以被4整除的矩阵。所以我想填充矩阵来重新格式化它。

比如3*3的矩阵，应该填充成4*4的矩阵：

1 2 3    1 2 3 0 
4 5 6 => 4 5 6 0
7 8 9    7 8 9 0
         0 0 0 0

有什么有效的方法吗？而且我不确定是否需要花费时间来填充它，SSE 转置是否会比循环每个索引更慢...

Answer 1

增加数组或矩阵的大小是一个有趣的问题。我们可以创建一个新的数组或矩阵来填充并将所有内容复制到新的。

#include <stdio.h>
#include <stdlib.h>
#include <histedit.h>
#define MATRIX_SIZE 3 /* use some size */

/* returns an array of arrays of int*, all of which NULL */
int ***alloc_matrix(unsigned rows, unsigned columns) {
    int ***matrix = malloc(rows * sizeof(int **));
    if (!matrix) abort();
    for (unsigned row = 0; row < rows; row++) {
        matrix[row] = malloc(columns * sizeof(int *));
        if (!matrix[row]) abort();
        for (unsigned column = 0; column < columns; column++) {
            matrix[row][column] = NULL;
        }
    }
    return matrix;
}

/* deallocates an array of arrays of int*, calling free() on each */
void free_matrix(int ***matrix, unsigned rows, unsigned columns) {
    for (unsigned row = 0; row < rows; row++) {
        for (unsigned column = 0; column < columns; column++) {
            //    printf("column %d row %d\n", column, row);
            free(matrix[row][column]);
        }
        free(matrix[row]);
    }
    free(matrix);
}

int *** padding_matrix(int ***matrix, unsigned size, unsigned padding) {
    int ***padded_matrix = alloc_matrix(padding, padding);
    for (unsigned row = 0 ; row < size; row++) {
        for (unsigned column = 0 ; column < size; column++) {
            printf("copying column %d row %d %d\n", column, row,  * matrix[row][column]);
            padded_matrix[row][column] =  matrix[row][column];
            printf("copied column %d row %d %d\n", column, row,  * padded_matrix[row][column]);
        }
    }

    for (unsigned row = size ; row < padding; row++) {
        for (unsigned column = 0 ; column < padding; column++) {
            int i = 0;
            padded_matrix[row][column] = &i;
            printf("padded column %d row %d\n", column, row);
        }
    }

    for (unsigned row = 0 ; row < padding; row++) {
            int i = 0;
            padded_matrix[row][3] = &i;
            printf("padded column %d row %d\n", 3, row);
        }
    return padded_matrix;
}

int main(int argc, char *argv[]) {
    int ***matrix = alloc_matrix(MATRIX_SIZE, MATRIX_SIZE);
    int x = 1;
    int y = 2;
    int z = 3;
    int u = 4;
    int w = 5;
    int a = 6;
    int b = 7;
    int c = 8;
    int d = 9;

    matrix[0][0] = &x;
    matrix[0][1] = &y;
    matrix[0][2] = &z;
    matrix[1][0] = &u;
    matrix[1][1] = &a;
    matrix[1][2] = &w;
    matrix[2][0] = &b;
    matrix[2][1] = &c;
    matrix[2][2] = &d;
    for (unsigned row = 0 ; row < MATRIX_SIZE; row++) {
        for (unsigned column = 0 ; column < MATRIX_SIZE; column++) {
            printf("matrix column %d row %d=%d\n", column, row , * matrix[row][column]);
        }
    }


    int ***matrix2  = padding_matrix(matrix, MATRIX_SIZE, MATRIX_SIZE + 1);
    for (unsigned row = 0 ; row < MATRIX_SIZE+1; row++) {
        for (unsigned column = 0 ; column < MATRIX_SIZE+1; column++) {
            printf("padded matrix column %d row %d=%d\n", column, row , * matrix2[row][column]);
        }
    }
}

测试

padmatrix
matrix column 0 row 0=1
matrix column 1 row 0=2
matrix column 2 row 0=3
matrix column 0 row 1=4
matrix column 1 row 1=6
matrix column 2 row 1=5
matrix column 0 row 2=7
matrix column 1 row 2=8
matrix column 2 row 2=9
copying column 0 row 0 1
copied column 0 row 0 1
copying column 1 row 0 2
copied column 1 row 0 2
copying column 2 row 0 3
copied column 2 row 0 3
copying column 0 row 1 4
copied column 0 row 1 4
copying column 1 row 1 6
copied column 1 row 1 6
copying column 2 row 1 5
copied column 2 row 1 5
copying column 0 row 2 7
copied column 0 row 2 7
copying column 1 row 2 8
copied column 1 row 2 8
copying column 2 row 2 9
copied column 2 row 2 9
padded column 0 row 3
padded column 1 row 3
padded column 2 row 3
padded column 3 row 3
padded column 3 row 0
padded column 3 row 1
padded column 3 row 2
padded column 3 row 3
padded matrix column 0 row 0=1
padded matrix column 1 row 0=2
padded matrix column 2 row 0=3
padded matrix column 3 row 0=0
padded matrix column 0 row 1=4
padded matrix column 1 row 1=6
padded matrix column 2 row 1=5
padded matrix column 3 row 1=0
padded matrix column 0 row 2=7
padded matrix column 1 row 2=8
padded matrix column 2 row 2=9
padded matrix column 3 row 2=0
padded matrix column 0 row 3=0
padded matrix column 1 row 3=0
padded matrix column 2 row 3=0
padded matrix column 3 row 3=0

Process finished with exit code 0

您在上面的输出中看到填充后的矩阵更大，我们插入了填充。

Answer 2

你实际上不需要垫，是吗？您只是建议将其作为一种使用您已有的 4x4 SSE 转置例程的方法，对吗？

矩阵转置不移动对角线元素（包括第一个和最后一个）。 3x3 转置的数据移动要少得多：只需要 7 个元素 loaded/stored.

1 2 3    1 4 7
4 5 6 => 2 5 8
7 8 9    3 6 9

AVX2:

如果您的元素是 4B（int 或 float，而不是 double），则前 8 个元素适合单个 AVX 向量。 AVX2 有一个完整的交叉车道洗牌，vpermps。所以整个转置可以通过一次加载/_mm256_permutevar8x32_ps/存储来完成。它在 Intel Haswell 上具有每时钟一个吞吐量和三个周期延迟。

由于最后一个元素不需要移动，所以您根本不需要触摸它，除非您没有就地移调，只需复制它即可。

仅使用 SSE，您可以加载两个包含前八个元素的向量，并使用 shufps 或其他方法将它们相互打乱，以组合每个向量中的元素。

或者可以随机创建一个 { 1 4 3 2 } 向量和一个 { 5 8 7 6 } 向量，然后将元素 7 混合到第一个，将元素 3 混合到第二个。

无论如何，3x3 比 4x4 更容易转置，所以如果以后不需要在整行上使用 SSE，请不要填充到 4x4。

Answer 3

不，您不能有效地填充矩阵。假设平面数组，您需要创建另一个内存区域，然后将值复制到左上角，然后将其余值设置为零。所以本质上是对每个值的操作。

您可以做的是从填充矩阵开始并对它们执行所有操作，或者使用稀疏矩阵表示。但由于目标是快速移调，您很可能会在摇摆上获胜而在环形交叉路口上失败。

C中的填充矩阵

Padding matrix in C

c

transpose

sse

matrix

AVX2: