为什么下面的循环展开会导致错误的结果？
Why does the following loop unrolling lead to a wrong result?
我目前正在尝试优化我为三角剖分 24x24 矩阵的程序编写的一些 MIPS 汇编程序。我目前的目标是利用延迟分支和手动循环展开来尝试减少循环。 注意：我对所有矩阵运算都使用 32 位单精度。
算法的一部分涉及我试图展开的以下循环（N 将始终为 24）
...
float inv = 1/A[k][k]
for (j = k + 1; j < N; j++) {
/* divide by pivot element */
A[k][j] = A[k][j] * inv;
}
...
我要
...
float inv = 1/A[k][k]
for (j = k + 1; j < N; j +=2) {
/* divide by pivot element */
A[k][j] = A[k][j] * inv;
A[k][j + 1] = A[k][j + 1] * inv;
}
...
但它生成的结果不正确，我不知道为什么。有趣的是，带循环展开的版本正确生成矩阵的第一行，但其余行不正确。没有循环展开的版本正确地对矩阵进行了三角剖分。
这是我的尝试。
...
# No loop unrolling
loop_2:
move $a3, $t2 # column number b = j (getelem A[k][j])
jal getelem # Addr of A[k][j] in $v0 and val in $f0
addiu $t2, $t2, 1 ## j += 2
mul.s $f0, $f0, $f2 # Perform A[k][j] * inv
bltu $t2, 24, loop_2 # if j < N, jump to loop_2
swc1 $f0, 0($v0) ## Perform A[k][j] := A[k][j] * inv
# The matrix triangulates without problem with this original code.
...
...
# One loop unrolling
loop_2:
move $a3, $t2 # column number b = j (getelem A[k][j])
jal getelem # Addr of A[k][j] in $v0 and val in $f0
addiu $t2, $t2, 2 ## j += 2
lwc1 $f1, 4($v0) # $f1 <- A[k][j + 1]
mul.s $f0, $f0, $f2 # Perform A[k][j] * inv
mul.s $f1, $f1, $f2 # Perform A[k][j+1] * inv
swc1 $f0, 0($v0) # Perform A[k][j] := A[k][j] * inv
bltu $t2, 24, loop_2 # if j < N, jump to loop_2
swc1 $f1, 4($v0) ## Perform A[k][j + 1] := A[k][j + 1] * inv
# The first row in the resulting matrix is correct, but the remaining ones not when using this once unrolled loop code.
...
展开的 C 循环条件有问题。
j < N; j +=2可以用j = N-1,
开始循环体
在 A[k][N-1]（正常）和 A[k][N]（不正常）处访问数组。
一种常见的方法是j < N-1，或者一般来说j < N-(unroll-1)。但是对于无符号 N，你还必须在开始循环之前单独检查 N >= unroll，因为 N-1 可能会换成一个巨大的无符号值。
保持 j < limit 通常对 C 编译器有利，而 j + 1 < N 是他们必须计算的另一件事。并且还可以阻止编译器证明循环对于无符号计数（如 size_t）不是无限的，因为这是 well-defined 环绕，所以 N = UINT_MAX 可能导致根据起点，条件始终为真。 （例如 j = UINT_MAX-2 使 UINT_MAX-1 < UINT_MAX，j+=2 使 0 < UINT_MAX 也为真。）所以这与对无符号计数器使用 j <= limit 类似的问题.编译器真的很想知道循环何时可能是无限的。对于某些人来说，如果 trip-count 在第一次迭代之前无法计算，它会禁用 auto-vectorization。
如果 j 从 0 开始，如果 N 保证是展开因子的倍数，您可以使用草率条件。但正如 Nate 指出的那样，这里有所不同。
MIPS asm 的效率
通常循环展开的重点是性能。 non-inline 调用循环内的辅助函数有点违背了目的。
jal getelem 我假设做一堆乘法和东西来用一个指针和两个整数重做索引？请注意，您正在一行中扫描连续的内存，因此您可以只增加一个指针。
计算一个 end-pointer 进行比较，因此您的 MIPS 循环看起来像
# some checking outside the loop, maybe with a bxx to the end of it.
looptop: # do{
lwc1 $f2, 0($t0)
lwc1 $f3, 4($t0)
addiu $t0, $t0, 4*2 # p+=2 advance by 8 bytes, 2 floats
...
swc1 something, 0($t0)
swc1 something, 4($t0)
bne $t0, $t1 # }while(p!=endp)
# maybe another condition to check if you should run one last iteration.
MIPS bltu只是一个pseudo-instruction(sltu/bnez);这就是为什么最好计算一个精确的 end-pointer 以便您可以使用单个机器指令作为循环分支。
是的，这可能意味着将迭代计数向下舍入为 2 的倍数以确保正确性。或者进行标量迭代并将 up 舍入为 2 的倍数。例如x++ / x&=-2;
使用软件流水线，例如进行加载和划分但不进行存储，您可以让 rounding-up 让循环重做该元素（如果奇数）。 （如果分支错误预测的机会比 FP 乘法和冗余存储成本更高。）还没有完全考虑清楚，但这与 SIMD 做第一个未对齐向量，然后 potentially-partially-overlapping 对齐向量的想法类似. （SIMD 向量化就像展开，但随后您会回滚到执行 4 个元素的单个指令，例如。）
我目前正在尝试优化我为三角剖分 24x24 矩阵的程序编写的一些 MIPS 汇编程序。我目前的目标是利用延迟分支和手动循环展开来尝试减少循环。 注意：我对所有矩阵运算都使用 32 位单精度。
算法的一部分涉及我试图展开的以下循环（N 将始终为 24）
...
float inv = 1/A[k][k]
for (j = k + 1; j < N; j++) {
/* divide by pivot element */
A[k][j] = A[k][j] * inv;
}
...
我要
...
float inv = 1/A[k][k]
for (j = k + 1; j < N; j +=2) {
/* divide by pivot element */
A[k][j] = A[k][j] * inv;
A[k][j + 1] = A[k][j + 1] * inv;
}
...
但它生成的结果不正确，我不知道为什么。有趣的是，带循环展开的版本正确生成矩阵的第一行，但其余行不正确。没有循环展开的版本正确地对矩阵进行了三角剖分。
这是我的尝试。
...
# No loop unrolling
loop_2:
move $a3, $t2 # column number b = j (getelem A[k][j])
jal getelem # Addr of A[k][j] in $v0 and val in $f0
addiu $t2, $t2, 1 ## j += 2
mul.s $f0, $f0, $f2 # Perform A[k][j] * inv
bltu $t2, 24, loop_2 # if j < N, jump to loop_2
swc1 $f0, 0($v0) ## Perform A[k][j] := A[k][j] * inv
# The matrix triangulates without problem with this original code.
...
...
# One loop unrolling
loop_2:
move $a3, $t2 # column number b = j (getelem A[k][j])
jal getelem # Addr of A[k][j] in $v0 and val in $f0
addiu $t2, $t2, 2 ## j += 2
lwc1 $f1, 4($v0) # $f1 <- A[k][j + 1]
mul.s $f0, $f0, $f2 # Perform A[k][j] * inv
mul.s $f1, $f1, $f2 # Perform A[k][j+1] * inv
swc1 $f0, 0($v0) # Perform A[k][j] := A[k][j] * inv
bltu $t2, 24, loop_2 # if j < N, jump to loop_2
swc1 $f1, 4($v0) ## Perform A[k][j + 1] := A[k][j + 1] * inv
# The first row in the resulting matrix is correct, but the remaining ones not when using this once unrolled loop code.
...
展开的 C 循环条件有问题。
j < N; j +=2可以用j = N-1,
开始循环体
在 A[k][N-1]（正常）和 A[k][N]（不正常）处访问数组。
一种常见的方法是j < N-1，或者一般来说j < N-(unroll-1)。但是对于无符号 N，你还必须在开始循环之前单独检查 N >= unroll，因为 N-1 可能会换成一个巨大的无符号值。
保持 j < limit 通常对 C 编译器有利，而 j + 1 < N 是他们必须计算的另一件事。并且还可以阻止编译器证明循环对于无符号计数（如 size_t）不是无限的，因为这是 well-defined 环绕，所以 N = UINT_MAX 可能导致根据起点，条件始终为真。 （例如 j = UINT_MAX-2 使 UINT_MAX-1 < UINT_MAX，j+=2 使 0 < UINT_MAX 也为真。）所以这与对无符号计数器使用 j <= limit 类似的问题.编译器真的很想知道循环何时可能是无限的。对于某些人来说，如果 trip-count 在第一次迭代之前无法计算，它会禁用 auto-vectorization。
如果 j 从 0 开始，如果 N 保证是展开因子的倍数，您可以使用草率条件。但正如 Nate 指出的那样，这里有所不同。
MIPS asm 的效率
通常循环展开的重点是性能。 non-inline 调用循环内的辅助函数有点违背了目的。
jal getelem 我假设做一堆乘法和东西来用一个指针和两个整数重做索引？请注意，您正在一行中扫描连续的内存，因此您可以只增加一个指针。
计算一个 end-pointer 进行比较，因此您的 MIPS 循环看起来像
# some checking outside the loop, maybe with a bxx to the end of it.
looptop: # do{
lwc1 $f2, 0($t0)
lwc1 $f3, 4($t0)
addiu $t0, $t0, 4*2 # p+=2 advance by 8 bytes, 2 floats
...
swc1 something, 0($t0)
swc1 something, 4($t0)
bne $t0, $t1 # }while(p!=endp)
# maybe another condition to check if you should run one last iteration.
MIPS bltu只是一个pseudo-instruction(sltu/bnez);这就是为什么最好计算一个精确的 end-pointer 以便您可以使用单个机器指令作为循环分支。
是的，这可能意味着将迭代计数向下舍入为 2 的倍数以确保正确性。或者进行标量迭代并将 up 舍入为 2 的倍数。例如x++ / x&=-2;
使用软件流水线，例如进行加载和划分但不进行存储，您可以让 rounding-up 让循环重做该元素（如果奇数）。 （如果分支错误预测的机会比 FP 乘法和冗余存储成本更高。）还没有完全考虑清楚，但这与 SIMD 做第一个未对齐向量，然后 potentially-partially-overlapping 对齐向量的想法类似. （SIMD 向量化就像展开，但随后您会回滚到执行 4 个元素的单个指令，例如。）