• Курсы Академии Кодебай, стартующие в мае - июне, от команды The Codeby

    1. Цифровая криминалистика и реагирование на инциденты
    2. ОС Linux (DFIR) Старт: 16 мая
    3. Анализ фишинговых атак Старт: 16 мая Устройства для тестирования на проникновение Старт: 16 мая

    Скидки до 10%

    Полный список ближайших курсов ...

Гостевая статья Branch Prediction - основы, которые не должен знать каждый программист

CPU Pipeline Instructions
Почему инструкции процессора передаются по конвейеру?
«Для лучшей пропускной способности, очевидно»
Обсуждать можно долго, почему это так.Но вместо тысячи слов:
RISC_pipeline.png


Обратите внимание, что дизайн предполагал, что инструкции протекают постоянно. В прямом коде считаетса следующая инструкция либо в порядке программы, либо в порядке, определенном компилятором, чтобы воспользоваться преимуществами параллелизма на уровне инструкций (ILP). В случае ветвлений pipeline не знает заранее, какая следующая инструкция выполнитса в текущей запущенной программе. Пример:

Код:
auto flag = get_output_some_fn();

if (flag) {
    do_something();
} else {
    do_another_thing();
}

В приведенном выше случае нет никакой возможности угадать, куда пойдет поток выполнения. Флаг предиката зависит от результата другой функции, выполнение которой в свою очередь может быть решено некоторыми внешними непредвиденными факторами.

В таких случаях pipeline всегда останавливается, пока не будет определена правильная целевая инструкция для выполнения следующей. Это приводит к потере одного цикла во время выборки команд.
no_prediction_timing.png


Можем ли мы избежать "Pipeline Stalls"?
Да, можем, предварительно загрузив следующую инструкцию и выполнив ее, надеясь, что наше решение о предварительной загрузке было правильным. Это называется спекулятивным исполнением ветвей.
with_prediction_timing.png


Динамическое предсказание ветвления
Цель динамического прогнозирования ветвлений состоит в том, чтобы предсказать, будет ли выполняться условный переход на основе поведения программы в текущем исполнении. Один из более простых способов сделать это:
  • поддерживать состояние для каждой условной ветви
  • предсказать, будет ли ветвь принята на основе состояния
  • изменить состояние в зависимости от того, была ли взята ветка или нет
Current StateInput (Branch Exec)Output (Prediction)Next State
0Not TakenNot Taken0
0TakenNot Taken1
1Not TakenTaken0
1TakenTaken1

Буфер предсказания ветвлений
Важный момент из предыдущей секции - сохранение и обновление следующего состояния для каждой инструкции перехода может стать дорогостоящим. Использование отдельного буфера прогнозирования ветвлений для кэширования прогнозируемых состояний, недавно выполненных условных ветвлений может снизить эту стоимость. Таблица истории ветвления доступна/индексируется с использованием адреса инструкций условного ветвления.

Заключение
В простых конструкциях CPU Pipeline задержки конвейера могут существенно повлиять на пропускную способность команд. Реализация даже простых механизмов прогнозирования ветвлений может существенно улучшить производительность. Результаты наиболее выражены в спекулятивных стратегиях исполнения.

Источник:
 
Мы в соцсетях:

Обучение наступательной кибербезопасности в игровой форме. Начать игру!