Давно уже был тот момент, когда увидели свет предыдущие части цикла статей, которые рассказывали об устройстве процессора, о том, как он выполняет команды, и о том, что такое конвейер и для чего он нужен. Теперь мы познакомимся еще с одним компонентом процессора: предсказателем переходов.

Многие полагают, что в работе вычислительной техники нет места неопределенности и элементам теории вероятности. А уж угадываниям и «вангованию» - так и подавно. Оказывается, что это далеко не так. И если до сих пор считаете так, то мы в данной статье переубедим вас.

Давайте вспомним: среди команд, выполняемых процессором, есть команды перехода. Они бывают двух типов: условные и безусловные. Команды выполняются последовательно, одна за другой, а когда встречается команда перехода, происходит «прыжок» на другой адрес. Если команда безусловная, то этот «прыжок» происходит в любом случае. А если команда условная, то надо еще решить, нужно ли нам прыгать.

Когда проводятся какие-либо вычисления, следующим шагом мы проверяем, получился ли результат нулевой. И в зависимости от этого выполняем разные действия. В коде это будет выглядеть примерно так:

result = a * b – с / d;

if (result == 0) {

         // набор команд при нулевом результате (ветвь 1)

} else {

         // набор команд при ненулевом результате (ветвь 2)

}

Кажется, что всё хорошо: сначала посчитали результат, а потом проверили, нулевой ли он. Загрузили новый адрес и продолжили выполнение. Так-то оно так, но давайте вспомним, что у нас есть конвейер! Пока будет считаться результат, конвейер уже может успеть запустить на выполнение несколько новых команд. Но как? Ведь он же не знает, по какой ветви двигаться, пока не рассчитает предыдущее значение.

Как выйти из создавшейся ситуации? Подождать, пока результат будет рассчитан, а потом продолжить выполнение? Пожалуй, это простейшее, однако не самое лучшее решение, поскольку это сводит на нет все преимущества конвейера в плане ускорения вычислений.

Ещё один способ. Создать в процессоре возможность выполнять обе ветви одновременно, а в конце выбрать необходимый результат. Но тут свои проблемы: а как быть, если у нас в ветви встретится еще одно условие? А если ещё большей вложенности условий? Вернуться к первому варианту в таком случае? Не выход. К тому же, это существенно удорожает процессор.

Решение было найдено достаточно изящное: установить предсказатель переходов. Такое устройство, которое будет угадывать, по какой ветви нам придется идти. Кажется странным, не правда ли? Но все на самом деле ещё более странно выглядит, когда начинаешь разбираться в том, как же предсказатель угадывает ветвь, по которой пойдет вычисление.

Давайте посмотрим на простейшие предсказатели переходов. Конечно, такие предсказатели не используются в реальной технике, однако некоторые из них (а может и все) когда-то давно применялись.

• Переход происходит всегда. Один из простейших вариантов, который в любом случае осуществляет переход. В процессоре не требуется никаких дополнительных компонентов. Вероятность угадывания таким предсказателем около 50%.
• Переход не происходит никогда. Ещё один простейший вариант. Полностью аналогичен предыдущему, за исключением того, что всегда выбирается иная ветвь. Вероятность угадывания те же 50% (та половина, которая не угадывается первым вариантом).
• Переход происходит всегда, когда назад. Если адрес перехода меньше текущего адреса, то переход будет, а если больше, то не будет. Вероятность угадывания таким предсказателем около 70%. Повышение вероятности связано с тем, что в большинстве случаев переход назад – это переход на очередной шаг цикла. Если цикл должен выполниться 50 раз, то 49 переходов будет назад и лишь один будет вперед.

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

Основная идея динамических переходов – это анализ истории прошлых переходов. Существует история глобальных переходов, куда записываются все переходы, а также история локальных переходов, куда по раздельности записываются переходы каждого типа (ассемблерные команды je, jne, jg, jz и так далее). Алгоритм работы таких предсказателей бывает весьма интересным, и создается впечатление, что предсказатель просто магическим образом угадывает ветвь. Например, выбирается несколько значений из истории локальных переходов, на основе этих значений выбираются некоторые значения из истории глобальных переходов, а затем вновь выбранные значения отправляются в конечный автомат, который по результатам работы выдает на выход информацию о том, будет ли переход или нет. И что самое интересное, что при отсутствии, казалось бы, логики в работе этих предсказателей, вероятность угадывания ими достаточно высокая: 96-98%!

Но все же, что будет, если предсказатель переходов не угадал направление, и произошло выполнение не той ветви? В таком случае осуществляется сброс конвейера, полная его очистка, и загрузка заново. Конечно, теряется время, но все же намного меньше (в целом при выполнении всей программы), чем в случае остановки конвейера до того момента, пока не станет точно известен результат.

И еще небольшой момент: что делать процессору, если у него история переходов пуста? В таком случае динамические предсказатели перехода не могут ничего предположить, да и угадать у них тоже вряд ли получится. В этом случае процессор прибегает к помощи статического предсказателя (как правило, к варианту «Переход происходит всегда, когда назад»). И когда заполнятся истории динамического предсказателя, произойдёт переход к нему.

Как говорится, удивительное рядом. Тяжело было бы предположить вообще, что при работе компьютера находится место реализации теории вероятности и угадываниям. Но, как оказывается, без этого не удается обойтись. И предсказатель переходов – очередное тому подтверждение. Выдавая достаточно высокий процент точности предсказаний, он становится незаменимым ускорителем конвейеризации вычислений.

Пацовский Игорь

Effective Soft, Ltd.