為什么下面的回圈展開會導致錯誤的結果？

我目前正在嘗試優化我為對 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.

...

uj5u.com熱心網友回復：

展開的 C 回圈條件有問題。

j < N; j =2可以用 開始回圈體j = N-1，在(fine) 和(not fine)
訪問陣列。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）不是無限的，因為這被明確定義為環繞，因此 N = UINT_MAX 可能導致條件始終為真，具體取決于起點。（例如 j = UINT_MAX-2 makeUINT_MAX-1 < UINT_MAX和make 也是如此。）所以j =2它與用于無符號計數器0 < UINT_MAX的問題類似。j <= limit編譯器真的很想知道回圈何時可能是無限的。對于某些人來說，如果在第一次迭代之前無法計算行程計數，它會禁用自動矢量化。

如果j從 開始0，如果保證 N 是展開因子的倍數，您可以擺脫一個草率的條件。但正如 Nate 指出的那樣，這里有所不同。

MIPS asm 的效率

通常，回圈展開的重點是性能。對回圈內的輔助函式的非行內呼叫有點違背目的。

jal getelem我假設做一堆乘法和東西來用一個指標和兩個整數重做索引？請注意，您正在掃描一行中的連續記憶體，因此您可以只增加一個指標。

計算一個要比較的端點，所以你的 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.

MIPSbltu只是一個偽指令（sltu/bnez）；這就是為什么最好計算一個精確的終點指標，這樣您就可以使用一條機器指令作為回圈分支。

是的，這可能意味著將迭代計數向下舍入為 2 的倍數以確保正確性。或者進行標量迭代并四舍五入為2 的倍數。例如x /x&=-2;

使用軟體流水線，例如進行加載和除法但還沒有存盤，如果奇怪，您可以讓四舍五入讓回圈重做該元素。（如果分支錯誤預測的可能性比 FP 乘法和冗余存盤的成本更高。）還沒有完全考慮到這一點，但這與 SIMD 執行第一個未對齊向量的想法相似，然后是可能部分重疊的對齊向量. （SIMD 向量化就像展開，但隨后您回滾到執行 4 個元素的單個指令，例如。）

標籤：C 部件 矩阵 mips 循环展开

上一篇：如何實作數字河流？

下一篇：libcurl放置資料流而不是檔案