7

我现在正在学习计算机体系结构课程，我们正在学习基本的 R 型和 I 型指令（另外，这是一个RISC体系结构）等。我似乎无法弄清楚如何优化它代码。

说明：此代码将单词添加到数字数组（由 $s1 指向）中，直到达到零。结果存储在 $t1 中。$t0 保存当前单词。

        add   $t1, $zero, $zero      # Initialize result to zero
again:  
        lw    $t0, 0($s1)            # Load the word from the array
        beq   $t0, $zero, done       # Terminate if current word is a zero
        add   $t1, $t1, $t0          # Add current word to result
        addi  $s1, $s1, 4            # Point to the next word in the array
        beq   $t1, $t1, again        # Loop again
done:
        nop                          # Do nothing

我很难优化代码。我觉得beq $t1, $t1, again（因为它总是正确的）是不必要的，但我不知道如何删除它。这是我的尝试，但我现在意识到我的代码不会终止。

        add   $t1, $zero, $zero      # Initialize result to zero
again:  
        lw    $t0, 0($s1)            # Load the word from the array
        add   $t1, $t1, $t0          # Add current word to result
        addi  $s1, $s1, 4            # Point to the next word in the array
        bne   $t1, $zero, again      # If result is not zero, loop
done:
        nop                          # Do nothing

我从不检查终止零并跳到完成。但是如果我再添加一个检查，那么代码不会和以前一样吗？

4

2 回答 2

2

通常，您希望将顶部循环中的测试转换为底部循环中的测试。为此，您经常必须在第一次迭代时（或多或少）跳到循环体的中间。在伪代码中，您现在拥有的基本上是：

    initialize sum
beginning:
    load a word
    if (done) goto end
    add to sum
    increment pointer
    goto beginning
end:

为了优化它，我们希望将结构更改为如下所示：

    initialize sum
    goto start_loop

beginning:
    add to sum
    increment pointer
start_loop:
    load a word
    if (!done) goto beginning

这样每个循环只有一次跳转而不是两次（这是一个短的向后跳转，所以目标几乎总是在缓存中）。

也就是说，我应该补充一点，这种优化实际上已经过时了——通过不错的分支预测，无条件跳转通常基本上是免费的。

编辑：既然提到了循环展开，我会加两分钱。分支预测通常会使循环展开过时，除非您可以使用它来并行执行更多指令。这在这里不是问题，但在现实生活中通常很有用。例如，如果我们假设 CPU 有两个单独的加法器可用，我们可以展开循环的两次迭代，并将这些迭代的结果添加到两个单独的目标寄存器中，因此我们通过同时添加两个值来利用两个加法器时间。然后，当循环终止时，我们将这两个寄存器相加得到最终值。在类 C 的伪代码中，会出现这样的结果：

odds = 0
evens = 0

do {   
    evens += pointer[0];
    odds += pointer[1];
    pointer += 2;
while (pointer[0] && pointer[1]);
total = odds + evens;

正如所写的，这增加了两个连续的零来终止序列的额外要求，而不仅仅是一个，并且数组中至少要添加两个项目。但是请注意，在这里提供主要优势的并不是真正的循环展开，而是并行执行。

如果没有这一点，我们真的只能在未采用的分支比采用的分支便宜时（即使两者都被正确预测）看到循环展开的好处。在较旧的处理器（例如，较旧的 Intel）上，相对于未采用的分支，采用分支确实会带来惩罚。同时，展开的循环会使用更多的缓存空间。因此，在现代处理器上，这通常是整体损失（除非，正如我之前所说，我们可以使用展开来获得并行性）。

于 2012-01-26T20:43:21.993 回答
1

展开你的循环：


        add   $t1, $zero, $zero      # Initialize result to zero
again:  
        lw    $t0, 0($s1)            # Load the word from the array
        beq   $t0, $zero, done       # Terminate if current word is a zero
        add   $t1, $t1, $t0          # Add current word to result
        addi  $s1, $s1, 4            # Point to the next word in the array

        lw    $t0, 0($s1)            # Load the word from the array
        beq   $t0, $zero, done       # Terminate if current word is a zero
        add   $t1, $t1, $t0          # Add current word to result
        addi  $s1, $s1, 4            # Point to the next word in the array

        lw    $t0, 0($s1)            # Load the word from the array
        beq   $t0, $zero, done       # Terminate if current word is a zero
        add   $t1, $t1, $t0          # Add current word to result
        addi  $s1, $s1, 4            # Point to the next word in the array

        lw    $t0, 0($s1)            # Load the word from the array
        beq   $t0, $zero, done       # Terminate if current word is a zero
        add   $t1, $t1, $t0          # Add current word to result
        addi  $s1, $s1, 4            # Point to the next word in the array

        # and so on to a reasonable amount, 4-8 times are common.

        b     again        # Loop again
done:
        nop
于 2012-01-26T20:38:21.553 回答