Форвардинг, остановки и предсказание переходов

Урок показывает приёмы, которыми процессор сглаживает конфликты конвейера и держит высокую производительность.

Форвардинг (data forwarding) — проброс результата прямо со ступени, где он вычислен, на вход следующей команды, не дожидаясь записи в регистр. Предсказание переходов — догадка процессора о том, куда пойдёт ветвление.

Форвардинг: не ждать записи

Конфликт данных возникал потому, что результат ADD доступен только после ступени WB. Но физически он уже посчитан на ступени EX! Идея форвардинга: пробросить значение прямо с выхода АЛУ на вход следующей команды по специальному «короткому» проводу, минуя регистровый файл. Тогда зависимая команда не ждёт. Смоделируем выигрыш:

# без форвардинга зависимая команда ждёт записи (WB)
# с форвардингом результат доступен сразу после EX
def stalls_needed(forwarding):
    # i1 пишет R1 на такте 5 (WB), i2 хочет R1 на такте 3 (EX)
    if forwarding:
        return 0           # пробрасываем с EX на EX, ждать не нужно
    return 2               # иначе 2 такта простоя

print("без форвардинга: остановок =", stalls_needed(False))
print("с форвардингом:  остановок =", stalls_needed(True))

Вывод:

без форвардинга: остановок = 2
с форвардингом:  остановок = 0

Остановки (stalls / пузыри)

Форвардинг помогает не всегда. Классический случай — load-use: команда LOAD достаёт данные из памяти только на ступени MEM, а следующая команда хочет их раньше. Тут даже форвардинг не успевает, и нужен пузырь (bubble) — один такт простоя, NOP в конвейере. Компиляторы переставляют команды, чтобы заполнить такой пузырь полезной работой.

LOAD  R1, [addr]   IF ID EX MEM WB
ADD   R2, R1, R3      IF ID -- EX MEM WB   <- '--' пузырь (ждём данные)
                              ^ форвардинг из MEM в EX после паузы

Как работает под капотом: предсказание переходов

Чтобы не терять такты на каждом if, процессор предсказывает, куда пойдёт переход, и спекулятивно выполняет команды этой ветки. Если угадал — выигрыш; если нет — сброс. Простейший предсказатель: «переход поведёт себя как в прошлый раз». Реализуем 1-битный и 2-битный предсказатели и сравним точность на типичном цикле:

# Переход цикла: 9 раз "взят" (продолжаем цикл), затем 1 раз "не взят".
pattern = [1,1,1,1,1,1,1,1,1,0] * 3   # три прохода цикла по 10 итераций

def predict_1bit(seq):
    state, correct = 1, 0
    for actual in seq:
        if state == actual:
            correct += 1
        state = actual            # запоминаем последний исход
    return correct / len(seq)

def predict_2bit(seq):
    # счётчик 0..3; >=2 -> предсказываем "взят"
    counter, correct = 3, 0
    for actual in seq:
        pred = 1 if counter >= 2 else 0
        if pred == actual:
            correct += 1
        counter = min(3, counter+1) if actual else max(0, counter-1)
    return correct / len(seq)

print(f"1-битный предсказатель: точность {predict_1bit(pattern)*100:.1f}%")
print(f"2-битный предсказатель: точность {predict_2bit(pattern)*100:.1f}%")

Вывод:

1-битный предсказатель: точность 83.3%
2-битный предсказатель: точность 90.0%

2-битный предсказатель точнее: он не «передумывает» после одного промаха, поэтому выход из цикла стоит ему лишь одной ошибки, а не двух. Реальные процессоры используют куда более сложные предсказатели (с историей переходов) и достигают точности больше 95%.

Глубже в тему

Форвардинг — прекрасный пример того, как внимательный взгляд на тайминг устраняет кажущуюся неизбежной задержку. Наивно кажется, что зависимая команда обязана ждать, пока предыдущая запишет результат в регистровый файл (ступень WB). Но ведь результат физически уже посчитан на выходе АЛУ, на ступени EX, — за два такта до записи! Значит, незачем гонять его «туда-обратно» через регистры: достаточно проложить короткий провод (bypass) прямо с выхода исполнительного блока на его же вход на следующем такте. Аппаратура сравнивает номера регистров: если команде на входе EX нужен регистр, который команда впереди вот-вот запишет, мультиплексор подставляет свежее значение с обходного провода вместо устаревшего из регистрового файла. Это устраняет большинство остановок по данным почти бесплатно — ценой нескольких проводов и компараторов.

Но форвардинг не всесилен, и понять его границу так же важно, как и его силу. Камень преткновения — конфликт load-use: команда LOAD получает данные из памяти лишь на ступени MEM, а это на такт позже, чем АЛУ выдаёт свой результат на EX. Поэтому если сразу за LOAD идёт команда, использующая загруженное значение, даже самый быстрый обходной провод не успевает: данных ещё просто нет в нужный момент. Приходится вставлять пузырь (bubble) — один такт, на котором конвейер «топчется на месте», пропуская NOP. Здесь в игру вступает компилятор: умный планировщик команд старается переставить инструкции так, чтобы между LOAD и использованием его результата стояла какая-нибудь независимая полезная команда, заполняющая пузырь работой. Это яркий пример совместной оптимизации аппаратуры и компилятора — каждый по отдельности слабее, чем оба вместе.

Предсказание переходов превратилось в одну из самых изощрённых частей современного процессора, и неспроста: на ветвистом коде каждая ошибка предсказания стоит десятков потерянных тактов. Эволюция предсказателей поучительна. Однобитный предсказатель просто помнит, как переход повёл себя в прошлый раз, — но он дважды ошибается на каждом цикле: один раз при выходе из цикла и ещё раз на первой итерации следующего захода. Двухбитный счётчик с насыщением добавляет «инерцию»: чтобы сменить мнение, ему нужно ошибиться дважды подряд, поэтому единичный выход из цикла его не сбивает, и точность на циклах подскакивает. Расчёт из урока показывает скачок с 83% до 90% буквально от одного дополнительного бита состояния — отличная иллюстрация того, как крошечное усложнение даёт заметный выигрыш.

Реальные процессоры идут намного дальше двухбитных счётчиков. Современные предсказатели учитывают историю предыдущих переходов (global history), потому что ветвления часто коррелируют: исход одного if предсказывает исход другого. Двухуровневые адаптивные предсказатели и алгоритмы вроде TAGE достигают точности выше 95–99% даже на сложном коде. Отдельно стоит механизм предсказания адреса косвенных переходов (BTB, branch target buffer) и предсказания возврата из функций (return address stack). Цена ошибки настолько высока, что архитекторы готовы тратить на предсказатели десятки тысяч транзисторов. И именно спекулятивное исполнение по предсказанию, как мы увидим дальше, открыло дорогу атакам класса Spectre: процессор, спекулятивно выполнив команды по неверно предсказанной ветке, оставляет в кэше следы, по которым можно восстановить секреты, — наглядное напоминание, что оптимизация производительности и безопасность порой вступают в конфликт.

Частые ошибки

Считать, что форвардинг устраняет все остановки. Load-use конфликт всё равно требует пузыря.
Думать, что предсказание «угадывает наугад». Оно опирается на историю; для циклов точность очень высока.
Недооценивать цену промаха. Неверное предсказание в глубоком конвейере сбрасывает много команд — отсюда важность хороших предсказателей.

Итог

Форвардинг пробрасывает результат с EX/MEM, минуя ожидание записи, и убирает многие остановки.
Load-use конфликт требует пузыря; компилятор старается его заполнить.
Предсказание переходов с историей (2-битное и сложнее) даёт высокую точность на циклах.