Предсказание переходов

Более эффективными для снижения потерь от конфликтов по управлению являются методы предсказания переходов. Они призваны максимально ускорить определение адреса команды, выполняемой после команды перехода.

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

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

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

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

Ядро процессора начинает выбирать из подсистемы памяти и выполнять команды по предсказанной ветви программы (так называемое выполнение по предположению, или "спекулятивное" выполнение). Однако так как направление перехода может быть предсказано неверно, получаемые результаты с целью обеспечения возможности их аннулирования не записываются в память или регистры (то есть для них не выполняется этап ЗР), а накапливаются в специальном буфере результатов.

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

При этом буфер результатов и конвейер, содержащий команды, которые следуют за командой условного перехода и находятся на разных этапах обработки, - очищаются. Аннулируются результаты всех уже выполненных этапов этих команд. Конвейер начинает загружаться с первой команды другой ветви программы.

Следует отметить, что конфликты по управлению не исчерпываются только проблемами, связанными с командами условных переходов. Они возникают при выполнении всех команд, меняющих значение счетчика команд. Это хорошо видно из табл. 30.1. Если команда i является командой такого типа (например, команда безусловного перехода), то адрес перехода будет вычислен ею в такте 5, в то время как уже в такте 2 необходимо выбирать следующую команду по этому адресу.

Для команд безусловных переходов однажды вычисленный целевой адрес сохраняется в специальной памяти BTB (Branch Target Buffer), откуда он извлекается сразу же при дешифрации данной команды.

Аналогичный подход используется для команд вызова процедуры и - возврата из нее (анализ связок CALL - RETURN).