Предсказание переходов (ветвлений) призвано свести к минимуму холостую работу конвейера и обеспечить его непрерывным потоком команд. Вообще, в среднем до 10 процентов кода программы составляют безусловные переходы, передающие управление по новому указанному адресу, и от 10 до 20 процентов - условные переходы, которые меняют или не меняют ход выполнения программы в зависимости от результата сравнения или выполнения какого-либо другого условия. В случае, если условный переход не выполняется, программа просто продолжает выполнение следующей по порядку команды.

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

Для предсказания переходов процессор использует расширенный алгоритм Yeh'а, позволяющий с большой достоверностью спрогнозировать, будет ли выполняться переход. Если предсказание окажется верным, то исполнение продолжится с малой задержкой или совсем без задержки. Если же предположение ошибочно, то частично выполненные команды придется удалять из конвейера, а новые команды выбирать из области памяти с правильным адресом, декодировать и выполнять их. Это повлечет за собой существенное снижение производительности, напрямую зависящее от глубины конвейера - для архитектуры P6 в случае ошибочного предсказания перехода потери составят от 4 до 15 тактов.

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

Итак, выровненные 16-байтовые команды передаются в дешифратор команд (Instruction Decoder) , состоящий из трех параллельных дешифраторов, два из которых - простые (Simple), и один - сложный (Complex). Задача каждого дешифратора - преобразование IA инструкции в одну или несколько микрокоманд (micro-ops).

Простые дешифраторы обрабатывают команды x86, транслируемые в единственную микрокоманду. Сложный дешифратор работает с командами, которым соответствуют от одной до четырех микрокоманд. Некоторые особенно сложные команды невозможно непосредственно декодировать даже сложным дешифратором, поэтому они передаются в планировщик последовательности микрокоманд (MIS - microcode instruction sequencer), генерирующий необходимое число микрокоманд. Если простой дешифратор встречает команду, которая не поддается трансляции, то она передается в сложный дешифратор, либо в планировщик последовательности микрокоманд. Такая пересылка слегка замедляет дешифрацию, но за счет буферизации с помощью станции-резервуара (Reservation Station), работу которой мы еще рассмотрим, не очень значительно сказывается на производительности.

В случае, если сложные и простые команды безупречно выровнены их соответственными дешифраторами, то дешифраторы способны генерировать в общей сложности шесть микрокоманд за такт, но, как правило, из всех трех дешифраторов за один такт выдаются три микрокоманды, соответствующие, в среднем, двум - трем IA командам, которые передаются в буфер восстановления последовательности (ROB - Reorder Buffer). ROB содержит 40 элементов, размером 254 байт каждый, и может хранить микрокоманду, два связанных с ней операнда, результат и несколько битов состояния.

Последним этапом перед выполнением команд является отображение регистров, осуществляемое в таблице псевдонимов регистров (RAT - register alias table). Архитектура x86 предусматривает только восемь 32-разрядных регистров общего назначения, а с таким малым числом регистров вероятность того, что две соседние команды будут использовать один регистр, относительно велика. Отображение регистров помогает ослабить влияние таких регистровых взаимозависимостей (register dependencies) - в случае необходимости записи в один и тот же регистр для двух команд их невозможно будет исполнить вне очереди без отображения регистров, так как более поздняя команда не может быть обработана до завершения более ранней команды.

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

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

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

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

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

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

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

Для операций с плавающей точкой предусмотрены два блока вычислений, причем второй предназначен для обработки SIMD инструкций.

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

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

Такие команды признаются завершенными, и блок вывода выстраивает их в первоначальную последовательность, учитывая прерывания, исключения, точки останова и неверные предсказания переходов.

Блок вывода способен выводить три микрокоманды за такт. При выводе микрокоманды результаты записываются в выводящий регистровый файл (RRF - retire register file) и/или память. Выводящий регистровый файл содержит 8 регистров общего назначения и 8 регистров для данных с плавающей точкой. После того, как микрокоманда выведена, она удаляется из буфера восстановления последовательности.

Операции записи в память откладываются до той поры, пока вызвавшая их микрокоманда не будет выведена. Для этого в P6 предусмотрен буфер упорядочения обращений к памяти (MOB - memory order buffer), в котором по командам, выдаваемым блоком записи в память, сохраняется информация о данных и адресах. Буфер упорядочения обращений к памяти пересылает данные в память только после того, как буфер восстановления последовательности уведомит его о том, что микрокоманда, произведшая запись в память, удаляется.

Для практической оценки эффективности нового механизма предсказания ветвлений попробуем воспользоваться простеньким тестом Queens_CW4.exe - маленькой программкой, рассчитывающей знаменитую <задачу ферзей> (необходимо разместить N ферзей на поле размером NxN клеток так, чтобы ни один из них не атаковал другого, см., например, тут). Чтобы время вычислений было разумным (не очень долгим, но и достаточным для получения точности порядка нескольких десятых процента) мы ограничились N=32 (см. также www.terralab.ru/system/29375). Заметим, что эта программа выдает всегда одно и то же расположение ферзей, то есть время не зависит от произвола в решении задачи ферзей (в принципе, у этой задачи много равноценных решений). Результаты представлены на диаграмме (в трех нижних строчках на этой и последующих диаграммах мы в чистом виде для лучшей наглядности сравниваем три Pentium 4 на частоте 3,2 ГГц, тогда как в верхней части диаграмм результаты для всех процессоров проранжированы в порядке от худшего к лучшему).
[Тут диаграмма]
Предполагается, что программа настолько компактна, что полностью помещается в кэш-память первого уровня для всех современных процессоров, то есть мы исследуем почти в чистом виде производительность и масштабируемость целочисленного <вычислителя> с кэшом L1 (это, кстати, видно и по равенству в пределах погрешности результатов для Northwood и Extreme Edition). Оказывается, что Prescott катастрофически проигрывает в этом тесте не только прежней микроархитектуре Pentium 4, он и Athlon 64. Отставание от Northwood составляет 31,5%!!! Если же перевести это во время расчета, приходящееся на один такт работы конвейера, то у Northwood (20 ступеней) оно составит 0,236 нс, а у Prescott (31 ступень) - лишь 0,200 нс. То есть, на первый взгляд, по этой программе, которая использует возможности блока предсказания переходов заметно активнее, чем большинство реальных программ, можно сделать вывод, что блок предсказаний ветвлений в Prescott может работать лучше, чем у Northwood (на 15% меньше затрат времени в расчете на одну стадию конвейера), однако на самом деле это не совсем так - ведь частота сброса конвейера зависит не только от его полной длины J, но и от множества других факторов.

Я конечно в некотором роде глуп