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

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