Обзор микроархитектур современных десктопных процессоров. Часть 1
Страница 6. Кэш трасс в процессоре Pentium 4 и особенности предсказания переходов

Кэш трасс в процессоре Pentium 4 и особенности предсказания переходов

Кэш инструкций в процессоре P-4 очень сильно отличается от I-кэша в процессоре классической архитектуры. В нём преобразование исходных x86-инструкций в МОПы производится перед кэшем, а в кэш помещаются целые трассы, составленные из этих МОПов. Поэтому такой кэш в процессоре P-4 называется «кэш трасс» (Trace-cache, Т-кэш). Трассы формируются в соответствии с предполагаемым динамическим порядком исполнения инструкций. В момент декодирования производится первичное предсказание перехода, и если предсказывается совершённый переход, то целевая инструкция помещается в трассу вслед за инструкцией перехода. Трасса может содержать множество таких «запаянных» переходов.

Размещение кэша «после декодера» и хранение в нём сформированных МОПов позволяет избежать необходимости параллельно декодировать несколько инструкций в условиях повышенной тактовой частоты, а также сократить затраты (число этапов конвейера) на обработку операции после её выборки из кэша. Кроме того, «запаивание» предсказанных переходов в трассу позволяет существенно снизить потери на их выполнение — теперь в одном такте может быть выполнена операция, предшествующая переходу, сам переход и операция, следующая за ним. В классических процессорах такая последовательность могла бы занять три такта.

Принципиальной особенностью Т-кэша, которая определяет способ хранения МОПов и механизмы работы с ними, является отсутствие прямолинейного соответствия между адресом исходной инструкции и местоположением соответствующего МОПа (МОПов) в кэше в связи с тем, что x86-инструкция переменной длины преобразуется в один или несколько МОПов фиксированной длины. Кроме того, хранение МОПов в виде трасс в предполагаемом порядке исполнения операций нарушает монотонность и непрерывность соответствия между адресами инструкций и положением МОПов в кэше. И, наконец, возможность раскрутки циклов в Т-кэше (то есть размещения в нём нескольких итераций цикла) и построения пересекающихся трасс нарушает взаимную однозначность между x86-инструкциями и МОПами — теперь одной исходной инструкции могут соответствовать несколько МОПов в разных итерациях цикла либо в различных трассах.

На Рис. 4 показан пример подобного кода и соответствие между исходными инструкциями (в их естественном размещении) и МОПами в трассе (в предполагаемом порядке исполнения). В этом примере присутствует предсказанный переход и частичная раскрутка цикла. Буквами I и i обозначены обычные инструкции и МОПы, а буквами J и j — инструкции и МОПы перехода.

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

Т-кэш состоит из блоков размером в 6 ячеек. Обычно МОП занимает одну ячейку, однако в некоторых случаях может потребоваться дополнительное место для размещения недостающей информации. Темп последовательного чтения из Т-кэша составляет 1 блок за 2 такта, или 3 МОПа за такт — что находится в соответствии с темпом обработки и отставки МОПов.

Объём Т-кэша составляет 12K ячеек, или 2048 блоков, организованных в 256 наборов по 8 блоков. Для преобразования программного адреса первой x86-инструкции в каждой трассе (как правило, это инструкция, на которую производится переход) в положение первого блока трассы в кэше используется комбинированный алгоритм, сочетающий прямую адресацию по нескольким разрядам программного адреса инструкции с ассоциативным поиском. Разряды этого адреса b10-3 указывают номер набора, а нахождение требуемого блока в наборе осуществляется сравнением остальных разрядов адреса (ключа) с соответствующими разрядами адреса, хранящимися для каждого блока в наборе (тэгами).

При внешнем сходстве данной схемы адресации блоков в Т-кэше с аналогичной схемой для классических кэшей между ними есть принципиальное отличие. В классических кэшах по этой схеме адресуется каждый блок, в то время как в Т-кэше так отображается только первый блок в трассе. Использование нескольких внутренних разрядов адреса x86-инструкции для указания номера набора позволяет достаточно равномерно распределить заголовки трасс по наборам.

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

Если инструкция, на которую производится переход, отсутствует в Т-кэше (то есть, в нём нет трассы с таким начальным адресом), начинается считывание x86-инструкций непосредственно из L2-кэша с их последующим декодированием и исполнением. Одновременно происходит формирование новой трассы МОПов и её размещение в Т-кэше. Если встречается инструкция условного перехода, то трасса, начиная с этой инструкции, строится в соответствии с результатом работы блока предсказания перехода декодера.

Декодер обрабатывает входной поток со скоростью не более одной x86-инструкции за такт, в зависимости от сложности формата инструкции и наличия префиксов. Если x86-инструкция не может быть преобразована в последовательность, состоящую из небольшого числа МОПов (до четырёх), она заменяется вызовом «микрокодовой подпрограммы», которая при работе будет генерировать МОПы и пересылать их на исполнение.

Имеется ряд ограничений, которые могут не позволить заполнить МОПами все 6 ячеек блока трассы и потребуют перейти к формированию следующего блока. Это требование размещения всех МОПов, составляющих x86-инструкцию, в одном блоке, и ограничение на число МОПов перехода — их может быть не более двух в блоке. Последнее ограничение связано с алгоритмом работы предсказателя переходов и согласовано с темпом, в котором может происходить отставка совершённых переходов — 1 операция за такт. В первом блоке трассы число МОПов перехода ограничено одним, что тоже связано с особенностями работы предсказателя переходов.

При появлении инструкции перехода построение трассы не прерывается, а продолжается в соответствии с предсказанным направлением этого перехода. Если переход будет предсказан как совершённый, непосредственно после МОПа перехода в трассе будет размещён МОП, на который происходит переход — причём оба этих МОПа могут оказаться в одном блоке и даже в одной «тройке», отсылаемой на исполнение. При предсказании перехода как не совершённого формирование трассы продолжится в натуральном порядке. Однако если при первом исполнении операции перехода выяснится, что переход был предсказан неправильно, формирование трассы прекратится, и она будет оборвана после этого МОПа. Также формирование трассы прекращается, если встречается инструкция косвенного перехода, вызова подпрограммы или возврата из подпрограммы. Максимальная длина трассы составляет 64 блока (384 ячейки для МОПов). При достижении этого предела формирование трассы также прекращается.

Может случиться, что правильно предсказанный совершённый переход является переходом по циклу. В таком случае появляется возможность «раскрутить» этот цикл и разместить в трассе несколько его итераций (Рис. 4), чтобы повысить скорость выборки и исполнения инструкций за счёт снижения затрат на переход по циклу. Существует механизм, ограничивающий раскрутку цикла разумными пределами.

При последующем выполнении кода МОПы считываются из Т-кэша последовательно, вплоть до завершения текущей трассы, в темпе 1 блок за 2 такта. Блоки считываются из наборов кэша с возрастающими номерами (после набора 255 следует набор 0). Если при исполнении трассы встречается операция условного перехода, то делается новое предсказание её направления и производятся следующие действия:

• если направление совпадает с тем, которое было предсказано при построении трассы — исполнение текущей трассы продолжается без перерыва и без потери тактов;
• если направление не совпадает с тем, которое было предсказано при построении трассы, и трасса по вновь предсказанному адресу найдена в кэше — начинает исполняться найденная трасса;
• если направление не совпадает с тем, которое было предсказано при построении трассы, и трасса по вновь предсказанному адресу не найдена — начинается формирование новой трассы с одновременным исполнением порождаемых МОПов.

При неправильном предсказании перехода (в тот момент, когда выяснится, что направление предсказано неверно) исполнение всех последующих МОПов прекращается, результаты их работы аннулируются, и производится поиск трассы по другому (правильному) адресу.

Первичное предсказание перехода при формировании трассы производится с помощью механизма, аналогичного такому механизму в классических процессорах, с использованием таблицы адресов переходов BTB размером 4096 элементов. Предсказание переходов при последующем исполнении трассы, считываемой из Т-кэша, производится по позиции МОПа перехода в Т-кэше с использованием вспомогательной таблицы адресов переходов TBTB (Trace-cache Branch Target Buffer), содержащей подмножество основной таблицы BTB и имеющей меньший размер (P-4 — 512 элементов, P-4E — 2048). Предсказание производится с опережением: в момент выборки и исполнения МОПов из текущего блока предсказывается поведение операций перехода, находящихся в следующем блоке. Для одного блока может быть предсказано до двух МОПов перехода (этим и вызвано ограничение на число таких МОПов в блоке).

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

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

Если при исполнении трассы произойдёт правильно предсказанный переход на начало другой трассы, то минимальное время, затрачиваемое на такой переход (в цикле либо в цепочке переходов) составит 4 такта. Благодаря опережающей работе предсказателя, это время может быть скрыто на фоне обработки МОПов и не представлять собой потерю. Однако если трасса (тело цикла) состоит только из одного блока, то время считывания МОПов из кэша в такой трассе составит лишь 2 такта, а время, затрачиваемое на переход - 4 такта (для процессора P-4E — 6 тактов).

Если направление перехода совпадает с тем, которое было предсказано при формировании трассы, то переход происходит без затрат времени. Имеется лишь ограничение на число МОПов перехода, уходящих в отставку — не более одного за такт. Это определяет минимальное время итерации развёрнутого цикла — 1 такт.

С учётом меньшей длины такта в процессоре P-4 время одной итерации цикла, выраженное в «нормализованных» тактах (с соотношением 1:1.4), составит всего 0.75 такта для цикла, «запаянного» в трассу, и 3 такта для цикла с переходом по трассе.

Эффективный размер Т-кэша, выраженный в байтах «эквивалентных x86-инструкций», можно оценить лишь приблизительно. При средней длине x86-инструкции в 3-4 байта и среднем числе МОПов (ячеек Т-кэша) в инструкции, равном 1.5, получаем среднюю «эффективную» длину МОПа на уровне 2-2.7 байта, что соответствовало бы эквивалентному размеру кэша инструкций 24-32 Кбайт. Однако в документации даётся оценка в 8-16 Кбайт, что, вероятно, как-то учитывает фрагментацию и потери на случаи многократного попадания одного и того же МОПа в кэш (при раскрутках циклов и в составе различных трасс).

Скорость работы Т-кэша (с учётом предсказания переходов) может варьироваться в очень широких пределах — от «идеальной» для алгоритмов, в которых все условные переходы были правильно предсказаны в момент формирования трассы, до довольно низкой при большом числе неправильных предсказаний. Вероятно, недостаточно высокая эффективность исполнения процессором P-4 сильно ветвящихся кодов, разработанных без надлежащего следования принципам оптимальной кодогенерации для суперскалярных конвейерных процессоров, связана именно с трудностью построения хорошо предсказанных трасс МОПов в Т-кэше, а также с потерями на работу механизма передачи управления для коротких трасс.