Оптимизируйте этот код сборки

Question

Сейчас я прохожу курс по компьютерной архитектуре, и мы переходим к базовым инструкциям 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

Я никогда не проверяю завершающий ноль и не прыгаю на готово. Но если я добавлю еще одну проверку, то код не будет таким же, как раньше?

Answer 1

Обычно вы хотите преобразовать тест в верхнем цикле в тест в нижнем цикле. Чтобы сделать это, вам часто приходится переходить (более или менее) к середине тела цикла для первой итерации. В псевдокоде то, что у вас есть сейчас, в основном:

    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

Таким образом, вместо одного прыжка в цикле будет только один прыжок (и это короткий обратный переход, поэтому цель почти всегда будет в кеше).

Тем не менее, я должен добавить, что эта оптимизация на самом деле в основном устарела - при достойном прогнозировании ветвлений безусловный переход обычно является по существу бесплатным.

Изменить: так как было упомянуто развертывание цикла, я добавлю два своих цента об этом. Предсказание ветвления обычно делает развертывание цикла устаревшим, если вы не можете использовать его для параллельного выполнения большего количества инструкций. Это не проблема здесь, но часто полезно в реальной жизни. Например, если мы предположим, что ЦП имеет два отдельных сумматора, мы можем развернуть две итерации цикла и добавить результаты этих итераций в два отдельных целевых регистра, поэтому мы используем преимущества обоих сумматоров, добавляя два значения одновременно время. Затем, когда цикл завершается, мы складываем эти два регистра, чтобы получить окончательное значение. В C-подобном псевдо-коде это будет выглядеть примерно так:

odds = 0
evens = 0

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

Как написано, это добавляет незначительные дополнительные требования к двум последовательным нулям для завершения последовательности вместо одного, и минимум двух элементов в массиве, который будет добавлен. Заметьте, однако, что здесь главное не развертывание цикла, а параллельное выполнение.

В отсутствие этого, мы действительно видим выгоду от развертывания цикла только в том случае, если ветвь, которая не взята, дешевле, чем ветвь, которая занята (даже если оба предсказания предсказаны правильно). На более старых процессорах (например, более старых Intel) взятие ветки действительно несло штраф относительно не взявшейся ветки. В то же время развернутый цикл будет использовать больше места в кеше. Таким образом, на современном процессоре это часто общая потеря (если, как я уже говорил, мы не можем использовать развертывание для получения параллелизма).

Answer 2

Разверните свой цикл:

        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