8x4分块优化方阵转置代码逻辑问题排查求助

问题描述 #

针对行列数为8的倍数的方阵设计的Cache友好型8x4分块优化转置算法，在转置8x8矩阵时，B矩阵的(5,0)、(6,1)、(7,2)位置（对应原描述的(0,5)、(1,6)、(2,7)转置后的位置）出现错误值，部分位置为未初始化的垃圾值，部分被错误覆盖。

原错误代码 #

void block8x4_opt(int M, int N, int A[N][M], int B[M][N])
{
    register int i, j, i1, j1;
    for (i = 0; i < N; i += 8)
        for (j = 0; j < M; j += 4) {
            if (j == i || j == i + 4) { /* same block */
                for (i1 = i; i1 < i + 8 ; i1++)
                    for (j1 = j; j1 < j + 4 ; j1++) {
                        if (i1 == j1 || i1 == j1 + 4) /* same row */
                            continue;
                        B[j1][i1] = A[i1][j1];
                    }
                for (j1 = j; j1 < j + 4; j1++) {
                    B[j1][j1] = A[j1][j1]; /* i1 == j1 */
                    B[j1][j1+4] = A[j1+4][j1]; /* i1 == j1 + 4 */
                }
                continue;   
            }
            for (i1 = i; i1 < i + 8 ; i1++)
                for (j1 = j; j1 < j + 4 ; j1++)
                    B[j1][i1] = A[i1][j1];
        }
}

错误原因分析 #

1. 错误的特殊处理逻辑：
   原代码错误引入了原地转置的元素跳过/延后处理逻辑，但当前场景是将矩阵A转置到独立的矩阵B，两个矩阵内存完全分离，不存在元素覆盖的风险，完全不需要跳过任何元素。

2. 数组越界访问：
   当j = i + 4时（比如8x8矩阵中i=0、j=4的块），延后处理的代码B[j1][j1+4] = A[j1+4][j1]会出现数组越界：j1的取值范围是4_{7，`j1+4`的结果是8}11，超出了8x8矩阵的列索引范围（0~7）。非法内存访问会破坏其他位置的元素，导致出现异常值（比如B[6][1]被错误覆盖为0）。

3. 错误的块判断条件：
   原代码认为j == i或j == i +4时是“同一块”，但8x4分块的行块（8行）和列块（4列）尺寸不同，转置后的块与原块完全不重叠，根本不存在需要特殊处理的“同一块”。

修正后的代码 #

去掉错误的特殊处理分支，直接执行分块转置即可：

void block8x4_opt(int M, int N, int A[N][M], int B[M][N])
{
    register int i, j, i1, j1;
    for (i = 0; i < N; i += 8)
        for (j = 0; j < M; j += 4) {
            for (i1 = i; i1 < i + 8 ; i1++)
                for (j1 = j; j1 < j + 4 ; j1++)
                    B[j1][i1] = A[i1][j1];
        }
}

验证结果 #

修正后的代码转置8x8矩阵时，所有位置元素均正确对应原矩阵的转置值，比如：

• B[5][0] = A[0][5] =5
• B[6][1] = A[1][6] =14
• B[7][2] = A[2][7] =23

内容的提问来源于stack exchange，提问作者hskimse