Служебные данные предсказания ветвления идеально предсказанной ветви
Я прочитал, что идеально предсказанная ветвь имеет нулевые / почти нулевые издержки. (Вот например: https://stackoverflow.com/a/289860/8038490Я не совсем понимаю, что люди имеют в виду. По крайней мере, должно быть оценено условие ветвления, которое может быть простым bool или вызовом функции, что занимает много времени.
Решение
Резюме
Оценка состояния ветки всегда занимает некоторое Работа, даже если идеально предсказуемо, но из-за внутреннего параллелизма в современных процессорах Работа не обязательно добавлять в Стоимость определенной последовательности команд.
подробности
Я думаю, что часть путаницы заключается в модели умственной производительности, которую многие люди используют для выполнения инструкций процессора. Да, каждая инструкция требует Работа, так что это должно подразумевать, что каждая инструкция имеет Стоимость, как бы мало оно ни было при измерении во время исполнения, верно?
Ну, это было бы верно, если бы общая стоимость выполнения была просто аддитивной в работе для каждой инструкции — вы просто складываете все Работа и получить финал Стоимость. Из-за большого параллелизма в современных процессорах это не работает так.
Думайте об этом как об организации вечеринки по случаю дня рождения. Возможно, вам придется купить муку, которая занимает 10 минут, а затем испечь торт, который занимает 60 минут, и пойти и забрать специальный подарок, который находится в 30 минутах езды. Эти сроки — все «работа», необходимая для деятельности. Тем не менее, кто-то может пойти и забрать подарок во время сбора муки и выпечки торта. Вы не можете испечь пирог без муки, однако. Итак, у вас есть две цепочки зависимостей: 70-минутная цепочка покупки муки -> выпечка и 30-минутная цепочка подарков. С неограниченным параллелизмом только 70-минутная цепочка, связанная с тортом, вносит свой вклад в то время, когда все готово. Подбирая подарок 30 минут Работа но это заканчивается стоимость нет времени (не задерживая выполнение всех задач), из-за другой работы, которая занимает больше времени (или критический путь) и происходит параллельно.
Другие дополнительные задачи могут выполняться параллельно, пока у вас не закончатся люди, которые могут их назначить. (В этот момент ограничения пропускной способности выполнения начинают увеличиваться задержки, и это называется конфликтом ресурсов. Если конфликт ресурсов задерживает критический путь, а не одну из более коротких цепочек зависимостей. Процессоры не знают, какая цепочка зависимостей является / будет быть критическим путем, поэтому их планирование не расставляет приоритеты так, как умные люди в этой аналогии планирования.)
Для менее абстрактного и более практического взгляда на то, как этот материал применяется непосредственно к процессорам, см. Вихрь Введение в графы потоков данных.
Как только мы получим эту новую ментальную модель, в которой стоимость последовательности инструкций часто доминирует некоторый критический путь, хотя последовательность, мы можем начать понимать, почему хорошо предсказанные ветви часто очень низки или равны нулю:
- Отраслевые инструкции имеют нет выходного регистра а также нет вывода памяти1. Это означает, что они не могут участвовать в типичных цепочках зависимостей, кроме как в качестве конечного узла — они всегда конец цепочка зависимостей. Таким образом, ответвления не участвуют в формировании длинных цепочек зависимостей и, таким образом, в некотором смысле находятся «вне линии» и могут быть рассчитаны параллельно с другими результатами.
- Фактическое выполнение команд ветвления обычно требует очень мало Работа: на современном x86 они могут выполняться на двух портах с задержкой в 1 цикл. Кроме того, ветвь инструкции могут быть плавленый с предыдущей операцией ALU, и результирующая операция все еще выполняется за 1 цикл — так что в некотором смысле ветвь иногда может быть свернута в предыдущую операцию без дополнительной работы при исполнении2. Это очевидно помогает аргументу «почти нулевой стоимости», но также помогает аргументу «действительно нулевой стоимости», поскольку потребность в меньших ресурсах означает, что с меньшей вероятностью возникает узкое место пропускной способности, которое может нарушить график выполнения с нулевой стоимостью.
Эти факторы в совокупности делают большинство прогнозируемых инструкций перехода нулевой или почти нулевой стоимостью.
Вы не должны поверить мне на слово, давайте посмотрим на реальный пример:
int mul1(int count, int x) {
do {
x *= 111;
} while (--count);
return x;
}
Учитывая count и начальное значение xумножается x на 111 count раз и возвращает результат. Петля монтирует до 3 инструкций, один для умножения, один для --count и ветка, чтобы проверить count значение:
.L2:
imul eax, eax, 111
sub edi, 1
jne .L2
Теперь вот тот же цикл, но с дополнительной веткой:
int mul2(int count, int x) {
do {
x *= 111;
if (x == 0) {
abort();
}
} while (--count);
return x;
}
это монтирует до 5 инструкций. Два дополнительных для теста x и ветка тест показывает, что x ноль:
.L7:
imul eax, eax, 111
test eax, eax
je .L12 ; ends up calling abort
sub edi, 1
jne .L7
Так какова стоимость добавления на 60% больше инструкций, включая ветку? Ноль, по крайней мере, до 4 значащих цифр3:
Running benchmarks groups using timer libpfc
** Running benchmark group stackoverflow tests **
Benchmark Cycles
No branch 3.000
Added test-branch 3.000
Просмотр занимает 3 цикла за итерацию, потому что он ограничен цепочкой зависимостей, включающей 3-х кратное умножение. Дополнительные инструкции и ветвление ничего не стоили, потому что они не добавляли в эту цепочку зависимостей и могли выполнять «вне линии», скрываясь за задержкой критического пути.
1 Концептуально, инструкции ветвления записывают регистр «rip», но это совсем не рассматривается как другие регистры: его прогрессирование прогнозируется заранее, поэтому предиктор нарушает зависимость.
2 Конечно, еще есть дополнительная работа по декодированию и слиянию инструкции в первую очередь, но это часто не является узким местом, поэтому может быть «бесплатным» с точки зрения стоимости, и такие вещи, как кэши UOP, означают, что это может даже не выполняться часто , Кроме того, в x86, хотя команда с объединенной ветвью имеет ту же задержку, что и операция ALU, она менее гибкая с точки зрения того, какие порты она может выполнять, поэтому в зависимости от давления порта может случиться, что слитая команда будет стоить по сравнению с голым ALU op.
3 Фактически, если вы перейдете к «бесконечным» значащим цифрам и посмотрите на число необработанных циклов, вы увидите, что дополнительные итерации этого цикла стоят именно так 3 цикла в обоих случаях. Случай без ветвления обычно заканчивается на 1 цикл короче (разница, которая возрастает до 0 в относительном смысле по мере увеличения итераций), возможно, потому, что начальная итерация в нестационарном состоянии занимает дополнительный цикл, или восстановление при неверном прогнозировании требует дополнительный цикл на заключительной итерации.
Другие решения
Предсказание ветвлений — это предсказание ИТОГА вашего состояния на уровне инструкций, которое является фактическим результатом условия C или C ++ — если это результат сравнения строк из миллиона символов, это, вероятно, не особенно полезно, потому что это сравнение займет много времени. Если это конечное условие цикла for, который перебирает две строки по миллиону символов в каждой, то это очень полезно, потому что это происходит много раз в этом цикле (при условии, что строки равны).
НЕЛЬЗЯ проводить сравнение двух длинных строк. Можно свободно угадать, что сравнение строк будет продолжаться (пока мы не найдем конец строки или разницу, и в этот момент предсказание ветвления будет неверным).
«Непредсказуемая» ветвь приведет к тому, что процессор не будет знать, где продолжается код. Современные процессоры имеют довольно длинные конвейеры (15-30 шагов), поэтому, если конвейер не заполнен «правильным» кодом, процессору придется ждать, пока «правильный» код протекает по конвейеру.
Итак, чтобы ответить на фактический квестон:
Когда сама ветвь хорошо спрогнозирована, процессор уже получил инструкции RIGTH в конвейере, и нет «пузыря конвейера», чтобы пройти по конвейеру, прежде чем мы сможем выполнить правильные инструкции для продолжения программы. Смотрите ниже для аналогии. Если прогноз неверен, в конвейере будет что-то отличное от правильных инструкций, и процессор должен прожевать их, выбрасывая их.
Думайте об этом как о автомобильном заводе, производящем автомобили моделей A и B на производственной линии, которая сначала монтирует кузов на шасси, красит его (волшебной краской, почти мгновенно высыхает), затем устанавливает двигатель и коробку передач, а затем ставит колеса на него, устанавливает свет, и, наконец, стекло устанавливается, и это полная машина. Каждый шаг занимает 20 минут, и конвейер для автомобилей будет перемещаться вперед на следующую позицию каждые 20 минут [в этом упражнении мы игнорируем тот факт, что само движение требует времени].
Вы отвечаете за производственную линию, и у вас есть несколько машин А на производственной линии. Внезапно, главный босс говорит: «Мы только что получили заказ на автомобили B, немедленно перейдем к созданию модели B». Итак, вы начинаете подавать детали автомобиля B на производственную линию. Но пройдет еще некоторое время, прежде чем следующая машина B выйдет на другом конце.
Предсказание ветвлений работает так, что он «угадывает», изменит ли код направление или перейдет к следующей инструкции. Если он угадает правильно, это все равно, что гадать, когда «большой босс» скажет вам переключаться между моделями автомобилей A и B, так что вы можете иметь правильный автомобиль, готовый сойти с конвейера, когда босс захочет, а не приходится ждать всю производственную линию, чтобы
Когда это работает, это здорово, потому что ожидаемый материал готов к выполнению. Если вы угадаете неправильно, вам все равно придется подождать, пока остальная часть производственной линии пройдет через текущий набор, и спрятать их в угол «у нас нет клиентов» (или с точки зрения инструкций процессора). «откажитесь от инструкции»).
Большинство современных процессоров также допускают «умозрительное выполнение». Это означает, что процессор начнет выполнять инструкции ДО того, как условие действительно будет определено. Таким образом, процессор переключится с автомобилей А на работу на автомобилях В, прежде чем начальник скажет об этом. Если в этот момент начальник скажет: «Нет, вы должны продолжать работать над автомобилями А», у вас есть куча машин, от которых вы можете отказаться, и над которыми вы уже начали работать. Вам не обязательно собирать все машины, но вы должны перемещать их по производственной линии, один шаг каждые 20 минут.