33. Необходимость и общие принципы функционирования блока предсказаний ветвлений:

Блок предсказания ветвлений Sandy Bridge, по сравнению с предшествовавшей ей микроархитектурой Nehalem, существенно улучшен. Например, буфер блока предсказания ветвлений (Branch Target Buffer, BTB) вмещает в два раза больше адресов результатов ветвления и вдвое большую историю комбинаций команд. Кроме того, увеличены размеры области хранения истории ветвлений, в том числе предсказанных и выполненных. Этим удалось существенно снизить количество неудачных предсказаний ветвлений и таким образом как увеличить производительность процессора, за счет уменьшения времени вынужденного простоя для сброса конвейера с обработанными впустую инструкциями, так и уменьшить потребление энергии, затраченной зря на обработку неудачных ветвлений.

Предсказание переходов (ветвлений) – это концепция, которая возникла в связи с появлением конвейерного способа исполнения команд и реализуется довольно давно. В микропроцессорах Intel начиная с процессоров семейства P6 (Pentium Pro+), а также в RISC процессорах и даже в микроархитектуре целого ряда высокопроизводительных процессоров типа mainframe, причем с каждой новой микроархитектурой все более и более совершенствуется. Связано это с тем, что в большинстве пользовательским программ на долю условных переходов приходится от 10 % до 20 % команд и до 10 % команд безусловных переходов. И когда в потоке инструкций встречается инструкция безусловного перехода, выборка следующей инструкции может осуществиться только на той ступени конвейера, когда выбран адрес перехода. Для команд безусловных переходов это, в лучшем случае, на этапе (ступени конвейера) выборки операнда (адреса) из памяти. А когда встречается инструкция условного перехода, то вопрос об адресации передачи управления может быть решен только после исполнения инструкции, вырабатывающей условие перехода, т.е. только тогда, когда она достигнет по конвейеру соответствующего исполнительного блока и будет выполнена. Следовательно, если предварительный адрес передачи управления будет выбран неправильно, то все команды, которые уже находятся на различных ступенях конвейера, придется сбрасывать и на конвейер подавать новую цепочку инструкций, начиная с точки разветвления. Все это приводит к существенному снижению производительности процессора и компьютера в целом.

Поэтому прежде чем подавать инструкции на конвейер, они анализируются в так называемом специальном блоке предсказания переходов (ветвлений) (Branch Prediction Unit - BPU). Цель анализа – определить точки ветвления в исполняемом потоке инструкций и предсказать наиболее вероятные ветви (пути) по которым пойдет обработка инструкций после точек ветвления. После определения ветви, инструкции к ней относящиеся тут же ставятся в очередь на исполнение. Этим минимизируется количество сбросов конвейера, и тем самым повышается производительность процессора. Конечно, такой порядок очередности поступления потока инструкций на конвейер даст выигрыш только в том случае, если алгоритм определения наиболее вероятных ветвей исполнения программы реализуется достаточно эффективно. Если ветвь программы предсказана неверно, то процессору придется исполнять инструкции, принадлежащие как неправильно угаданной, так и истинной ветви, т.е. проделать в данном случае двойную работу. Однако современные алгоритмы предсказания переходов, как показывает практика работы на тестах SPEC, позволяет правильно предсказывать до 98-99 % ветвлений программы.

Обычно разделяют две основных группы методов предсказания ветвлений: статические и динамические.

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

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

Примером статического предсказания переходов может также служить предположение, что любой прямой переход, т.е. переход на более старшие адреса, не выполняется, а переход обратный, т.е. на более младшие адреса – выполняется всегда. Вероятность справедливости такого утверждения довольно высока и основывается на том, что переход на более младшие адреса характерен при организации циклов, которые в программах встречаются довольно часто. Действительно, проведенные исследования показывают, что переходы назад обычно соответствуют циклу и выполняются в 90 % случаев, а переходы вперед большей частью соответствуют ветвлению и выполняются в 50 % случаев.

Следует отметить, что статическое предсказание ветвлений часто реализуется и на ступени компиляции, например, такие приемы как вынос ветвлений за пределы цикла, развертку итераций и т.п.

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

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

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

• Предсказать, является ли только что выбранная команда командой ветвления;

• Предсказать, будет ли переход или нет;

• Предсказать адрес перехода.

Для этого в блоке предсказания ветвлений предусматривается специальная ассоциативная память, называемая буфером адресов ветвлений (BTB – Branch Target Buffer) и таблица хранения истории предсказания ветвлений (BHT – Branch History Table). Например, в процессорах поколения P6, в памяти BTB сохраняется 512 адресов ранее выполненных переходов. (В современных моделях микропроцессоров объём этой памяти достигает до 4086 адресов и больше). BTB процессоров поколения P6 организована в виде 128 наборов, с ассоциативностью 4 (4-х входовая множественно-ассоциативная кэш-память). Для адресации используются младшие разряды адреса 16-байтового блока инструкций.

Структурная схема буфера адресов ветвлений (совместно c BHT), поясняющая принцип его работы, приведена на рис.XI.2.

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