Pentium 4: Мистический и загадочный Trace-кэш

Введение

Важнейшим элементом процессора Intel Pentium 4 является так называемый кэш трасс (Trace cache, Т-кэш), который выполняет ту же функцию, что и кэш инструкций в классических микропроцессорах. Необходимость создания такого устройства была связана с тем, что разработчики процессора столкнулись с трудностями реализации обычного кэша инструкций, эффективно работающего на повышенных тактовых частотах. Эти трудности обусловлены сложностью декодирования и обработки машинных инструкций процессоров архитектуры x86 (x86-инструкций), имеющих переменную длину и неудобный формат. Уже в процессорах предыдущего поколения (Pentium Pro, Pentium II, Pentium III) было реализовано преобразование "нерегулярных" x86-инструкций в "регулярные" микрооперации (uOP's, МОПы), удобные для последующей обработки. Однако в кэше инструкции по-прежнему хранились в исходном виде. Сложность декодирования x86-инструкций усугублялась тем, что эти процессоры имеют суперскалярную архитектуру и способны исполнять до трёх инструкций за такт, и декодирование этих трёх инструкций должно производиться параллельно. В процессоре Pentium 4 был сделан следующий шаг - кэш разместили после блока декодирования инструкций, и теперь в нём хранятся микрооперации с регулярной структурой. Таким образом, критически важный этап выборки и окончательного декодирования инструкций может производиться в высоком темпе и с минимальными временными затратами. Новый кэш получил название "Trace-cache" (Т-кэш).
К сожалению, Т-кэш очень скупо описан в документации по процессору Pentium 4. Несмотря на то, что с момента выхода первого процессора в семействе прошло уже более четырёх лет, ни один из ведущих компьютерных ресурсов (сайтов или журналов) не провёл собственного исследования и не уделил этому вопросу должного внимания. Автор рассчитывает на то, что данная статья позволит приоткрыть завесу тумана над Т-кэшем и показать, что это уникальное, сложное и интересное устройство было незаслуженно обойдено вниманием общественности. В связи с недавним выходом цикла статей по микроархитектуре процессора Pentium 4 автор надеется, что настоящая работа явится естественным продолжением и развитием этого цикла.
Для начала нужно отметить, что рассматриваемый кэш является "кэшем трасс" (Trace-cache), а не "кэшем микроопераций" (uOP-cache). Этим определяется принципиальное отличие Т-кэша от классического кэша инструкций - элементом хранения в кэше является не отдельная (микро)инструкция или выровненный блок из группы инструкций, а "трасса", т.е. непрерывная последовательность (микро)инструкций в соответствии с предполагаемым динамическим порядком их исполнения. Вследствие этого организация Т-кэша и алгоритмы его функционирования принципиально отличаются от организации обычного кэша инструкций (который, в свою очередь, не отличается существенно от обычного кэша данных).
Настоящая статья основана на изучении документации корпорации Intel, другой доступной литературы и патентов по тематике Т-кэша и смежным вопросам, а также на экспериментальном исследовании функционирования двух вариантов процессора Pentium 4: Northwood и Prescott. Для тестирования использовались модели процессоров Pentium 4 2.4 GHz и Celeron-D 2.8 GHz. В дальнейшем по тексту там, где это будет необходимо, эти два варианта процессора будут обозначаться соответственно P4 (Northwood) и P4E (Prescott).
Выводы о структуре элементов Т-кэша, их количественных характеристиках, алгоритмах работы и временах исполнения являются предположениями автора, основанными на результатах данного исследования. Эти предположения могут оказаться не всегда верными, но в целом они удовлетворительно описывают большинство наблюдаемых эффектов и не противоречат доступным описаниям и патентам.

Предпосылки и общая идея

Первичной предпосылкой создания Т-кэша была не только необходимость хранения x86-инструкций переменной длины в виде предекодированных микроопераций (МОПов), но и (главным образом) желание снизить потери на выполнение условных переходов в суперскалярной архитектуре с "широкой выборкой инструкций". Эти потери обусловлены в первую очередь тем, что инструкция перехода может располагаться в начале блока выбираемых инструкций, а инструкция, на которую производится переход - в конце соответствующего блока, что приведёт к снижению темпа выборки полезных инструкций даже при отсутствии затрат на предсказание и организацию перехода. Например, при ширине выборки, равной трём, инструкция перехода может оказаться в любой из трёх позиций, и в среднем темп выборки полезных инструкций в таких блоках окажется равным двум (варьируясь от одного до трёх). То же самое относится и к инструкции, на которую производится переход. Хранение инструкций в виде трасс в соответствии с предполагаемым динамическим порядком исполнения исключает оба упомянутых типа потерь, а также потери на выборку нового блока инструкций.
Размещение Т-кэша в процессоре P4 "после предекодера" и хранение в нём предекодированных микроопераций (МОПов) обеспечивает дополнительное удобство, позволяя использовать чисто последовательный предекодер, обрабатывающий не более одной x86-инструкции за такт, и сократить затраты (число этапов конвейера), необходимые для финального декодирования и обработки операции после её выборки из кэша для исполнения (см. схему процессора Pentium 4 на Рис. 1).

Первоначально идея "кэша трасс инструкций" разрабатывалась для RISC-процессоров с фиксированной длиной инструкций в расчёте на очень широкую выборку (до 4-6 инструкций за такт). Процессор Pentium 4 явился первой и единственной (на данный момент) реализацией такой идеи.

Ниже будут рассмотрены следующие вопросы организации и функционирования Т-кэша:

общая организация и способ хранения трасс в кэше;
декодирование инструкций и формирование трасс;
исполнение трасс, предсказание и организация переходов;
вытеснение блоков и реорганизация трасс;
эффективность работы и использования пространства кэша;
сравнение с альтернативной организацией кэша инструкций (на примере процессоров AMD K7/K8).

Общая организация и способ хранения трасс в кэше

Прежде чем приступить к обсуждению структуры Т-кэша, рассмотрим строение классического кэша. Возьмём для примера кэши данных процессоров P4 (8 Кбайт) и P4E (16 Кбайт). Эти кэши состоят из блоков размером 64 байта и организованы в виде 32 наборов по 4 (P4) либо по 8 (P4E) блоков. Поиск блока в кэше производится по физическому адресу элемента данных (без учёта младших 6 разрядов b5-0, которые адресуют требуемый байт внутри блока) и происходит таким образом: следующие 5 разрядов адреса (b10-6) указывают номер набора, а нахождение требуемого блока в наборе осуществляется сравнением самых старших разрядов адреса (ключа) с соответствующими разрядами адреса (тэгами), хранящимися для каждого блока в наборе. Для ускорения поиска сначала происходит сравнение нескольких младших разрядов ключа с соответствующими разрядами тэга - так называемый поиск по мини-тэгу. Мини-тэг состоит из 5 разрядов (b15-b11) у процессора P4 и из 10 разрядов (b20-b11) у процессора P4E. При нахождении блока с требуемым мини-тэгом происходит выборка данных с одновременной проверкой оставшейся части тэга.
На Рис. 2 показана организация кэша данных и структура физического адреса при доступе к кэшу для процессоров P4 и P4E. Буквами B обозначены разряды номера байта в блоке, буквами S - разряды номера набора, буквами M - разряды мини-тэга, и буквами T - разряды оставшейся части тэга.

Как видим, элемент данных по какому-либо адресу может располагаться в кэше в одном из 4 (P4) либо 8 (P4E) блоков конкретного набора. Это порождает так называемую проблему алиасинга, когда данные, отстоящие друг от друга на расстоянии, кратном 2 Кбайтам (без учёта 6 младших разрядов адреса), претендуют на блоки одного набора, и число таких различных элементов данных (точнее, объемлющих 64-байтовых блоков) в кэше ограничено числом этих блоков (4 либо 8). Помимо "алиасинга по набору", существует также "алиасинг по мини-тэгу": в наборе не может быть двух блоков данных с совпадающими мини-тэгами. Попытка записи в какой-либо набор нового блока с совпадающим мини-тэгом приведёт к вытеснению старого набора из кэша. Это означает, что в кэше не могут одновременно находиться два элемента данных (вместе с объемлющими блоками), отстоящие друг от друга на расстоянии, кратном 64 Кбайтам (P4) либо 2 Мбайтам (P4E).
Аналогичным образом устроен и классический кэш инструкций (I-кэш).
К сожалению, кэш трасс не может быть организован подобным образом как в способе размещения инструкций, так и в алгоритме поиска МОПа по адресу при переходе.
Принципиальной особенностью Т-кэша, которая определяет способ хранения микроинструкций и механизмы работы с ними, является отсутствие однозначного и прямолинейного соответствия между адресом исходной инструкции и местоположением соответствующего МОПа (МОПов) в кэше. Это связано в первую очередь с тем, что x86-инструкция переменной длины перекодируется в МОП (либо в несколько МОПов) фиксированной длины. Кроме того, хранение МОПов в виде трасс в предполагаемом порядке их исполнения (когда непосредственно после микроинструкции перехода может располагаться МОП, на который происходит переход) нарушает монотонность и непрерывность соответствия между адресами инструкций и "адресами МОПов" в кэше. И, наконец, возможность раскрутки циклов в Т-кэше (т.е. размещения в нём нескольких итераций цикла) и построения пересекающихся трасс нарушает взаимную однозначность между x86-инструкциями и МОПами - теперь одной исходной инструкции могут соответствовать несколько МОПов в разных итерациях цикла либо в различных трассах.
На Рис. 3 показан пример подобного кода и соответствие между исходными инструкциями (в их естественном размещении) и МОПами в трассе (в предполагаемом порядке исполнения). В этом примере присутствует предсказанный переход и частичная раскрутка цикла.

Можно сказать, что существует "пространство адресов МОПов" в Т-кэше. Адреса (или позиции) МОПов в этом пространстве могли бы прямолинейно отображаться на адреса блоков в кэше аналогично тому, как это делается в классических кэшах. Но, с другой стороны, преобразование адресов x86-инструкций в адреса МОПов (и обратно) должно было бы производиться специальным нетривиальным образом.
На самом деле механизм отображения адресов x86-инструкций в адреса МОПов необходим не для каждой инструкции, а только для тех, на которые производится переход - то есть для первой (микро)инструкции в каждой трассе. Все последующие МОПы располагаются в цепочке блоков кэша, непрерывно следующих друг за другом - до конца текущей трассы. Трассы должны размещаться в Т-кэше таким образом, чтобы по возможности не выталкивать друг друга и не вызывать потерь места из-за излишней фрагментации.
Итак, перейдём к описанию структуры Т-кэша процессора Pentium 4.
Т-кэш состоит из блоков размером в 6 "ячеек" для размещения микроинструкций. Обычно МОП занимает одну ячейку Т-кэша. Однако в случаях, когда МОП соответствует x86-инструкции, содержащей литеральную константу либо непосредственный адрес (смещение), и длина значимой части этой константы превышает 16 разрядов, требуется дополнительное место для размещения недостающей информации. В ряде случаев место может быть выделено в соседних ячейках при условии, что поле литеральной константы в этих ячейках не занято. При отсутствии такой возможности выделяется дополнительная ячейка. В этом случае обе ячейки, составляющие МОП, должны размещаться в одном блоке кэша. Кроме того, если x86-инструкция состоит из нескольких МОПов (до 4-х), то все эти МОПы должны также размещаться в одном блоке. Существуют и некоторые другие ограничения на размещение МОПов.
Темп последовательного чтения из Т-кэша составляет 1 блок за 2 такта, или 3 МОПа за такт - что находится в соответствии с темпом декодирования и отставки микроинструкций, а также их обработки на некоторых промежуточных стадиях.
Объём Т-кэша составляет 12K ячеек, или 2048 блоков, организованных в 256 наборов по 8 блоков. Для преобразования программного адреса первой x86-инструкции в каждой трассе (как правило, это инструкция, на которую производится переход) в положение первого блока трассы (заголовка трассы) в кэше используется комбинированный алгоритм, сочетающий прямую адресацию по нескольким разрядам программного адреса инструкции с ассоциативным поиском. Разряды этого адреса b10-3 указывают номер набора, а нахождение требуемого блока в наборе осуществляется сравнением остальных разрядов адреса (ключа) с соответствующими разрядами адреса (тэгами), хранящимися для каждого блока в наборе. Для ускорения поиска сначала происходит сравнение нескольких разрядов ключа с соответствующими разрядами тэга - мини-тэгом. Мини-тэг включает в себя 6 разрядов - b13-11 и b2-0. При нахождении блока с требуемым мини-тэгом происходит выборка инструкций с одновременной проверкой оставшейся части тэга.
На Рис. 4 приведён пример отображения последовательных блоков инструкций на наборы классического I-кэша, а на Рис. 5 показана организация хранения трасс в Т-кэше. Также показана структура программного адреса первой инструкции в трассе при доступе к первому блоку трассы в Т-кэше. Буквами S обозначены разряды номера набора, буквами M - разряды мини-тэга, и буквами T - разряды оставшейся части тэга.

При такой организации доступа существует проблема "алиасинга по мини-тэгу": в Т-кэше не могут одновременно находиться две трассы, отстоящие друг от друга (по адресу начальной x86-инструкции) на расстоянии, в точности кратном 16 Кбайтам. Очевидно, что данное требование может быть легко соблюдено путём добавления дополнительной инструкции "nop" в случае необходимости. Проблема "алиасинга по набору" тоже существует, но она относится не только к тем блокам, которые адресуются с помощью указанного механизма (т.е. к первым блокам в трассах), но и ко всем остальным блокам, которые располагаются последовательно друг за другом.
Описанная выше схема относится к процессору P4. Адресация Т-кэша в процессоре P4E производится в целом аналогично, однако алиасинг наступает при кратности 32 Кбайта. По всей видимости, в этом процессоре реализовано другое распределение разрядов адреса между полями мини-тэга и номера набора.
При внешнем сходстве данной схемы адресации блоков в Т-кэше с аналогичной схемой для классических кэшей между ними есть принципиальное отличие. В классических кэшах по данной схеме адресуется каждый элемент данных (вместе с объемлющим блоком достаточно большого размера) (Рис. 4), в то время как в Т-кэше так отображается только первый блок в трассе (Рис. 5). В принципе стартовая позиция каждой трассы могла бы быть выбрана достаточно произвольно и зависеть не от адреса первой x86-инструкции в трассе, а (например) от возможностей выделения блоков в кэше. Однако для упрощения и ускорения алгоритма отображения была использована такая комбинированная схема.
Использование нескольких "внутренних" разрядов адреса x86-инструкции для указания номера набора позволяет достаточно равномерно распределить заголовки трасс по наборам. Только в случае, когда имеется множество трасс, программные адреса первых инструкций в которых отстоят друг от друга на расстоянии, кратном 16 байтам, появится опасность, что только половина наборов сможет использоваться для размещения заголовков трасс. Однако и в этом случае не произойдёт потерь места, так как трассы состоят в общем случае из нескольких блоков.
Последующие блоки в трассе располагаются в наборах с возрастающими номерами (после набора 255 следует набор 0). Номер (позиция) блока трассы в каждом наборе может быть любым и определяется алгоритмом вытеснения и выделения блоков. Так как блоки в трассе считываются последовательно (начиная со следующего блока после заголовка), то для их поиска не нужен никакой механизм отображения адресов. Для убыстрения выборки все блоки в трассе связаны в двунаправленный список - в служебной информации каждого блока указаны номера (позиции) следующего и предыдущего блоков в соответствующих наборах (Рис. 5).
Каждая трасса должна размещаться в кэше целиком, поскольку блоки МОПов в случае вытеснения не могут быть в дальнейшем восстановлены отдельно от трассы. В случае, если какой-то блок вытесняется из кэша, трасса "укорачивается" - т.е. предыдущий блок трассы помечается как "последний".
Длина трассы ограничена 64 блоками, или 384 ячейками для МОПов. При таком ограничении в кэше может уместиться не менее 32 трасс. Максимальное число трасс равно числу блоков в Т-кэше - 2048.

Декодирование инструкций и формирование трасс

В том случае, когда микроинструкция, на которую происходит переход, отсутствует в Т-кэше, начинается считывание x86-инструкций непосредственно из кэша 2-го уровня (L2-кэша) с их последующим декодированием и исполнением. Одновременно происходит формирование новой трассы микроинструкций и её размещение в Т-кэше. Если встречается инструкция условного перехода, то трасса, начиная с этой инструкции, строится в соответствии с результатом работы блока предсказания перехода предекодера. Так как инструкции и данные хранятся в L2-кэше по физическим адресам, перед считыванием каждого блока из него происходит преобразование программного адреса в физический с помощью соответствующей таблицы трансляции адресов (Instruction Translation Look-aside Buffer, ITLB).
Предекодер обрабатывает входной поток со скоростью не более одной x86-инструкции за такт, в зависимости от сложности формата инструкции и наличия префиксов. Если x86-инструкция не может быть преобразована в последовательность, состоящую из небольшого числа МОПов (до четырёх), она заменяется на вызов "микрокодовой" подпрограммы, которая при работе будет генерировать МОПы и пересылать их на исполнение.
В случаях, когда темп выполнения инструкций заметно отстаёт от темпа формирования трассы, трасса может не записываться в Т-кэш. На практике наблюдается ситуация, когда исполняется очень большой участок кода, и вновь заполняемые блоки Т-кэша вытесняют старые блоки, которые могли бы понадобиться в дальнейшем. В результате выполнение этого участка происходит без участия Т-кэша - все инструкции считываются прямо из L2-кэша. Скорость работы в таком случае ограничивается возможностями x86-декодера.
Имеется ряд ограничений, которые могут не позволить заполнить МОПами все 6 ячеек блока трассы и потребуют перейти к формированию следующего блока. Это требование размещения всех МОПов (и частей МОПа), составляющих x86-инструкцию, в одном блоке. Кроме того, имеется ограничение на число инструкций перехода - их может быть не более двух в блоке. Это ограничение связано в первую очередь с алгоритмом работы предсказателя переходов и согласовано с темпом, в котором может происходить отставка (retirement) совершённых переходов (taken branch) - 1 инструкция за такт. В первом блоке трассы число инструкций перехода ограничено одной, что тоже связано с особенностями работы предсказателя переходов.
Как уже отмечалось выше, при появлении инструкции перехода построение трассы не прерывается, а продолжается в соответствии с предсказанным направлением этого перехода (механизм предсказания переходов будет рассмотрен в следующем разделе). Таким образом, в случае, если переход будет предсказан как "совершённый" (taken), непосредственно после инструкции (МОПа) перехода в трассе будет размещена инструкция (МОП), на которую происходит переход (Рис. 3) - причём оба этих МОПа могут оказаться в одном блоке и даже в одной "тройке", отсылаемой на исполнение. При предсказании перехода как "не совершённый" (not taken) формирование трассы продолжится в натуральном порядке. Однако в случае, если при первом исполнении инструкции перехода (после отсылки её на исполнение параллельно с формированием трассы) выяснится, что переход был предсказан неправильно, формирование трассы прекратится, и она будет оборвана после этого МОПа.
Также формирование трассы прекращается, если встречается инструкция безусловного косвенного перехода (indirect jump), вызова подпрограммы (call) или возврата из подпрограммы (return).
Может случиться, что правильно предсказанный "совершённый" переход является переходом по циклу. В таком случае появляется возможность "раскрутить" этот цикл и разместить в трассе несколько его итераций (Рис. 3) и, соответственно, повысить скорость выборки и исполнения инструкций за счёт снижения затрат на переход по циклу. С другой стороны, должен существовать механизм, ограничивающий раскрутку цикла разумными пределами. Согласно патентам, в этом механизме имеются ограничения по длине тела цикла и по числу оборотов раскрутки. Измерения показывают, что для коротких циклов число оборотов раскрутки равно по меньшей мере четырём.
Максимальная длина трассы составляет 64 блока. При достижении этого предела формирование трассы также прекращается.
По завершении формирования трассы происходит поиск в кэше другой трассы с требуемым стартовым программным адресом (обычно это случается, если текущая трасса была оборвана из-за неправильно предсказанного либо иного перехода). Если трасса с нужным адресом не найдена, снова начинается считывание x86-инструкций из L2-кэша и формирование следующей трассы.
В нынешних вариантах процессора Pentium 4 не реализован механизм "точек входа в трассу", хотя имеются патенты, описывающие несложные способы нахождения таких точек входа при построении трассы. Вероятно, трудности реализации такого механизма вызваны необходимостью создания вспомогательной ассоциативной структуры - таблицы точек входа (Entry Candidate Table, ECT), которая предназначалась бы для быстрого нахождения точки входа по программному адресу перехода. Поиск в этой структуре должен был бы производиться одновременно с поиском заголовка трассы в кэше по этому же программному адресу.
Таким образом, при любом нарушении порядка исполнения инструкций в трассе, а также при завершении трассы переход может быть произведён только на начало какой-либо трассы - существующей или вновь формируемой.
К сожалению, также не существует механизма, который при построении трассы отслеживал бы стартовые программные адреса всех трасс в Т-кэше на совпадение с адресом текущей декодируемой инструкции. Наличие такого механизма позволило бы избегать во многих случаях построения частично совпадающих и пересекающихся трасс. С другой стороны, такие пересекающиеся трассы могут соответствовать различным ветвям (сценариям) исполнения алгоритма и позволяют избегать неправильного предсказания переходов - так как одним и тем же (по программному адресу) инструкциям перехода в разных трассах соответствуют разные экземпляры МОПов с различающимися направлениями наиболее вероятного перехода. Кроме того, при соблюдении простых принципов структурного программирования, когда инструкции переходов могут располагаться только в конце линейных участков кода и передавать управление только на начало линейных участков, границы формируемых трасс будут совпадать с границами этих линейных участков. В результате совпадение и пересечение трасс не окажется слишком большим.

Исполнение трасс, предсказание и организация переходов

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

При правильном предсказании перехода:

1 - направление перехода совпадает с тем, которое было предсказано при построении трассы - в этом случае продолжается исполнение текущей трассы без перерыва и без потери тактов;

2 - направление перехода не совпадает с тем, которое было предсказано при построении трассы, и трасса по предсказанному адресу перехода найдена в кэше - в этом случае начинает исполняться найденная трасса;

3 - направление перехода не совпадает с тем, которое было предсказано при построении трассы, и трасса по предсказанному адресу не найдена - в этом случае начинается формирование новой трассы с одновременным исполнением записываемых в неё МОПов.

При неправильном предсказании перехода: сначала выполняются действия 1, 2 или 3 - в соответствии с предсказанным направлением. В тот момент, когда выяснится, что направление предсказано неверно, исполнение всех стартовавших инструкций (начиная с инструкции перехода) прекращается, результаты их работы аннулируются, и производится поиск трассы по другому (правильному) адресу. Далее начинается исполнение найденной трассы либо формирование новой. Неправильно предсказанный переход при нахождении адресата в Т-кэше занимает около 20 тактов для процессора P4 и около 30 тактов для процессора P4E. Если адресата нет в Т-кэше, то требуется ещё около 20 тактов (по грубым оценкам).
Для инструкций безусловного косвенного перехода (indirect jump), вызова подпрограммы (call) и возврата из подпрограммы (return) возможны только случаи, подобные описанным в пунктах 2 и 3, так как такие инструкции "обрывают" трассу.
Перейдём теперь к рассмотрению работы механизма предсказания переходов. Этот механизм выполняет две основные функции - предсказание программного адреса инструкции, на которую производится переход, и предсказание направления ветвления (для инструкций условного перехода). Оба предсказания должны быть выполнены заблаговременно - по возможности даже раньше, чем начнётся обработка инструкции перехода - для того, чтобы поиск (при необходимости) новой трассы и считывание нового блока МОПов были произведены без потерь лишних тактов либо с минимальными потерями.
Предсказание адреса перехода производится по адресу исходной x86-инструкции перехода либо по позиции соответствующего МОПа с использованием таблиц адресов перехода (Branch Target Table, BTB). Необходимость такого предсказания вызвана тем, что этот адрес может быть извлечён из инструкции (МОПа) и вычислен только на финальной стадии декодирования, а для инструкций косвенного перехода - только на стадии выполнения. Для инструкций "прямого" перехода этот адрес (при условии его нахождения в BTB) является правильным и окончательным, а для инструкций косвенного перехода - гипотетическим, так как содержимое элемента данных с целевым адресом может меняться. Отдельным случаем является предсказание инструкций возврата из подпрограммы (return): так как подпрограмма может вызываться из различных мест с разными адресами возврата, для таких инструкций предусмотрен специальный аппаратный стек глубиной в 16 элементов.
Предсказание направления необходимо только для инструкций условного перехода. Это предсказание производится специальным механизмом, который отслеживает историю всех условных переходов и вычисляет наиболее вероятный результат. При отсутствии необходимой информации производится статическое предсказание с учётом направления перехода (вперёд или назад), его расстояния, типа инструкции и наличия специальных префиксов-хинтов. Конкретные алгоритмы отслеживания истории и предсказания направления переходов в данной статье не рассматриваются (см. ссылки [Fog], [Milenkovic]).
Рассмотрим по отдельности предсказание переходов при формировании новой трассы и при исполнении существующей трассы.
При формировании трассы предсказание целевого адреса и направления перехода необходимо для того, чтобы размещать МОПы в трассе в соответствии с предполагаемым динамическим порядком их последующего исполнения. Предсказание производится по адресу исходной x86-инструкции перехода. Этой цели служит так называемая динамическая таблица адресов переходов (Dynamic Branch Target Buffer, DBTB) и связанная с ней таблица истории переходов (Branch History Table, BHT). Таблица DBTB по своей структуре напоминает кэш-память и состоит из 4096 элементов, организованных в виде 1024 наборов по 4 элемента. Номер набора при поиске определяется разрядами адреса инструкции перехода b13-4, а нахождение нужного элемента в наборе осуществляется сравнением остальных разрядов адреса (ключа) с соответствующими разрядами адреса (тэгами), хранящимися для каждого блока в наборе. Найденный элемент содержит предполагаемый программный адрес инструкции, на которую производится переход.
При такой организации доступа существует проблема алиасинга, когда инструкции перехода, отстоящие друг от друга на расстоянии, кратном 16 Кбайтам (без учёта младших 4 разрядов адреса), включая также инструкции, находящиеся внутри объемлющих 16-байтовых блоков, претендуют на блоки одного набора, и число таких инструкций, представленных в DBTB, ограничено четырьмя. С учётом того, что 16-байтовый блок x86-инструкций приблизительно соответствует одному-двум блокам МОПов в Т-кэше, а число МОПов перехода в одном блоке Т-кэша ограничено двумя, это означает, что алиасинг не должен накладывать серьёзных ограничений для инструкций, запоминаемых в кэше. Однако роль DBTB является более широкой - в нём сохраняется информация и о тех инструкциях перехода, которые были вытеснены из T-кэша либо не были в него записаны. Накопленная информация об адресах и истории переходов может использоваться в дальнейшем при повторном формировании трасс, содержащих эти инструкции.
Запись элемента таблицы DBTB и соответствующих полей таблицы истории переходов производится в момент отставки инструкции перехода, когда адрес и направление перехода становятся доподлинно известны.
Таблицу DBTB иногда в документации называют "Front-end Branch Target Buffer", но такое определение не совсем верно, так как она также может использоваться для предсказания переходов и при исполнении трасс.
Несколько иначе производится предсказание переходов при исполнении трассы, считываемой из Т-кэша. В этом случае повышается роль скорости работы алгоритма предсказания, поэтому предсказание производится не по адресу x86-инструкции перехода, а по позиции соответствующего МОПа в Т-кэше. Так как минимальное время обработки каждого блока кэша составляет всего 2 такта, то предсказание адреса и направления перехода должно производиться с опережением: в момент обработки текущего блока (выборки и запуска МОПов на исполнение) проводится предсказание для МОПов перехода, находящихся в следующем блоке.
Для предсказания адреса перехода в первую очередь используется вспомогательная таблица адресов переходов Т-кэша (Trace-cache Branch Target Buffer, TBTB). Эта таблица содержит подмножество основной таблицы DBTB и имеет меньший размер (512 элементов у процессора P4 и 2048 элементов у процессора P4E). Структуру TBTB детально расшифровать не удалось. Предположительно, индексирование (выбор набора) производится по позиции, занимаемой заголовком трассы (которая, в свою очередь, определяется несколькими разрядами программного адреса начальной инструкции в трассе), а для поиска нужного элемента используется позиция блока в трассе и положение МОПов перехода в блоке. Для одного блока может быть предсказано до двух МОПов перехода (этим и вызвано ограничение на число таких МОПов в блоке). Направление перехода определяется с помощью той же таблицы истории переходов, которая используется для предсказания переходов при формировании трасс.
В предсказании переходов при исполнении трассы есть своя специфика. Строго говоря, необходимо предсказывать не направление перехода и его адрес (в случае, когда переход предсказан как "совершённый"), а "выход" (или "невыход") из текущей трассы и адрес, по которому должно быть передано управление (в случае, когда предсказан выход из трассы). Это связано с тем, что трасса построена в соответствии с динамическим порядком выполнения инструкции при первом прохождении алгоритма, и те переходы, которые были предсказаны в тот момент как "совершённые", уже "запаяны" в трассу (Рис. 3). Поэтому для таких переходов, которые при очередном исполнении трассы снова предсказываются как "совершённые", выход из трассы производиться не должен, а для переходов, которые предсказываются уже как "не совершённые", должен быть произведён выход из трассы и передача управления по адресу x86-инструкции, следующей за инструкцией перехода. Для переходов, которые при построении трассы были предсказаны как "не совершённые", сохраняется натуральный порядок следования инструкций и привычное поведение при исполнении трассы.
Таким образом, назначение предсказателя переходов при исполнении трассы - принять решение "покинуть трассу" (Trace leave) или "не покидать трассу" (Not trace leave) и, для решения "покинуть трассу", выработать адрес перехода. Если инструкция перехода является последней в трассе, нужно только вычислить адрес, на который должно быть передано управление.
К числу ситуаций, требующих раннего определения направления и/или адреса перехода, помимо привычных инструкций условного перехода, безусловного косвенного перехода, вызова подпрограммы и возврата из подпрограммы, относится также и естественное завершение трассы. В свою очередь, для инструкции прямого безусловного перехода никакого предсказания не требуется, так как эта инструкция не может вызвать выхода из трассы.
Напомним, что предсказатель переходов вычисляет лишь программный адрес следующей инструкции, а поиск трассы в Т-кэше по этому адресу осуществляется с помощью частично-ассоциативного алгоритма, описанного в разделе про общую организацию кэша. Поскольку предсказатель обрабатывает текущий блок с опережением, пока запускаются МОПы из предыдущего блока, в случае принятия решения "покинуть трассу" имеется достаточно времени, чтобы выбрать из кэша первый блок новой трассы и начать запускать МОПы из него без потери тактов (либо с минимальной потерей). Фактически для этого есть 4 такта - 2 такта, пока запускаются МОПы из предыдущего блока, и ещё 2 такта - пока запускаются МОПы из текущего блока (где находится рассматриваемая инструкция перехода).
Может оказаться, что в первом блоке новой трассы также содержится инструкция перехода, результат исполнения которой необходимо предсказать. Поскольку в момент запуска МОПов из этого первого блока предсказатель переходов уже будет занят опережающей обработкой второго блока трассы, необходим какой-то дополнительный (либо дублирующий) механизм для обработки первого блока. В патентах предложено ввести ещё одну таблицу адресов переходов для заголовков трасс (Head Trace Branch Target Buffer) уменьшенного размера. Однако в процессоре Pentium 4 реализована другая схема. В качестве этого дублирующего механизма используется та же подсистема, что и для предсказания переходов при формировании трасс, с использованием основной таблицы адресов переходов DBTB. Этот механизм производит предсказание адреса и направления перехода по программному адресу x86-инструкции перехода. Данная процедура более сложна и трудоёмка, чем поиск в таблице TBTB, и обрабатывает одну инструкцию перехода за раз. Поэтому число МОПов перехода в первом блоке каждой трассы также ограничено одним.
Рассмотрим на примерах время выполнения коротких трасс. Замеры проводились следующим образом: была построена программа, состоящая из одинаковых кодовых последовательностей, завершающихся инструкцией косвенного перехода на следующую последовательность. Поскольку такая инструкция перехода обрывает трассу, мы получаем цепочку трасс, которую можем замкнуть в цикл и исполнить требуемое число раз.
Если трасса состоит из двух блоков, время её выполнения составляет 4 такта, как и должно быть (при условии, что время выполнения ограничивается темпом считывания инструкций - 2 такта на блок). Таким образом, механизмы предсказания переходов и поиска новой трассы работают "бесплатно" - за счёт опережающей обработки не происходит потери тактов. То же самое верно и для более длинных трасс. Трасса, состоящая из одного блока, уже не может быть выполнена за 2 такта, так как опережающей обработки для неё нет. Время выполнения такой трассы в составе зацикленной цепочки составляет 4 такта для процессора P4 и около 6 тактов для процессора P4E. Следует отметить, что на процессоре P4E трасса, состоящая из одного блока, исполняется дольше, чем трасса, состоящая из двух блоков! Этого можно избежать, удлинив трассу с помощью инструкций "nop" либо вставив в её начало фиктивную инструкцию условного перехода. Однако на практике трассы, состоящие из единственного блока, должны встречаться нечасто, поэтому данный пример является скорее курьёзом, нежели реальной проблемой.
Если при попытке предсказания перехода при исполнении трассы не удалось найти элемента в таблице TBTB с адресом перехода, то происходит обращение к основной таблице адресов переходов DBTB. Такое обращение увеличивает время выполнения приблизительно на 2 (P4) либо 4 (P4E) такта. Однако это увеличение имеет место только в том случае, когда время выполнения программы ограничивается темпом считывания инструкций из Т-кэша - в противном случае эта потеря может быть скрыта на фоне выполнения других инструкций.
Возможна и обратная ситуация, когда при исполнении первого (или единственного) блока трассы может понадобиться обращение к таблице адресов переходов TBTB. Это происходит, например, в случае, когда существует несколько экземпляров трассы, состоящих из одного блока и содержащих МОПы, соответствующие одной и той же x86-инструкции перехода. Эти экземпляры трассы относятся к разным ветвям алгоритма, и разные экземпляры МОПов перехода (для одной x86-инструкции) могут иметь различные целевые адреса или направления перехода. В таком случае предсказание производится с помощью TBTB по позиции соответствующего МОПа перехода - в каждом случае своего.
Таким образом, при предсказании переходов во время исполнения трасс из кэша имеет место тесная кооперация механизмов доступа к динамической и кэшевой таблицам адресов переходов DBTB и TBTB совместно с использованием таблицы истории переходов BHT для определения направления переходов.

Вытеснение блоков и реорганизация трасс

Ещё более сложным представляется вопрос организации вытеснения блоков и целых трасс из Т-кэша при затребовании блоков для новых трасс. Так как блок МОПов не может быть реконструирован отдельно от всей трассы, то и вытеснение по идее должно было бы производиться лишь целыми трассами - в противном случае повышается вероятность "разрушения" трасс в результате спонтанного вытеснения отдельных блоков.
Однако в нынешней реализации блоки вытесняются из Т-кэша всё же по отдельности, без какой-либо увязки со своим положением в трассе. При вытеснении блока, принадлежащего трассе, эта трасса "укорачивается" - предыдущий блок трассы помечается как "последний". Остальные блоки трассы становятся при этом недоступными. Однако особой беды в этом нет: так как вытеснение блоков происходит по механизму LRU (Least Recently Used, т.е. наименее используемый в последнее время), то "омертвевшие" блоки в хвосте трассы станут вскоре наиболее вероятными кандидатами на вытеснение, поскольку обращений к ним больше производиться не будет. Если же нужен кандидат на вытеснение в связи с заведением начального блока новой трассы, то в первую очередь будет вытеснен блок, являющийся также начальным блоком трассы и имеющий тот же мини-тэг, что и вновь заводимый (если такой блок обнаружится в данном наборе).
Замеры показывают, что существующий механизм вытеснения и замещения достаточно эффективно работает с трассами фиксированной длины. При построении трасс длиной в 1, 2, 4, 8, 16, 32 или 64 блока механизм позволяет полностью заполнить кэш трассами без фрагментации. Для трасс переменной длины уровень заполнения достигает 85-90 %, что соответствует занятости приблизительно 7 блоков в каждом наборе. Однако оставшиеся 10-15 % нельзя считать чистой потерей на фрагментацию, поскольку они могут использоваться (и, вероятно, используются) для хранения прочих участков кода программы и операционной системы.
На Рис. 6 показаны примеры заполнения Т-кэша трассами фиксированной и переменной длины. На рисунке с трассами переменной длины (снизу) хорошо видно, как образуются "складки", не позволяющие разместить дополнительные трассы (несмотря на наличие свободных блоков в некоторых наборах). Попытка добавить новую трассу приведёт к тому, что из кэша будут вытеснены отдельные блоки каких-либо "старых" трасс, и произойдёт "укорачивание" этих трасс.

Аналогичный эффект наблюдается при попытке исполнения очень длинных кодовых последовательностей без условных переходов. Такие последовательности "нарезаются" в трассы по достижении предельной длины в 64 блока. Поскольку стартовые программные адреса таких трасс (и определяемые этими адресами позиции начальных блоков в кэше) распределены определённым образом, не оптимальным с точки зрения "рационального" укладывания трасс в Т-кэш, трассы в одних местах могут отстоять друг от друга, а в других - наползать друг на друга с образованием "складок", подобных тем, что изображены на Рис. 6 (снизу).
Если среднее число занятых блоков в каждом наборе равно 7, в местах образования "складок" происходит заполнение оставшегося 8-го блока, и конфликтов между трассами, как правило, не возникает. Однако при попытке добавить новые длинные трассы в таких наборах со "складками" начнутся вытеснения блоков старых трасс, и возникнет эффект "переполнения кэша" с резким увеличением среднего времени доступа. Этим эффектом объясняются результаты тестов на определение "эффективной" длины Т-кэша - они как раз показывают длину в 10.5K ячеек, то есть 7/8 от полного размера кэша. Разумеется, слабо заполненный "8-й слой" вполне годится для размещения (или сохранения) каких-то других участков кода - мелких и случайно распределённых. Таким образом, в примере с "бесконечной цепочкой инструкций" имеет место определённый вид "мягкой аномалии", вводящей в заблуждение тестовую программу.
Также интересным является вопрос перестройки и динамической адаптации трасс. По мере накопления информации о поведении условных переходов в таблице истории переходов появляется возможность строить трассы более рационально. Возможность такой перестройки предоставляется мультизадачностью вычислительной системы: при полной смене контекста задачи вместе со сменой адресного пространства содержимое Т-кэша становится неактуальным, поскольку работа с кэшем ведётся в программных адресах. Таким образом, при обратной смене контекста содержимое рабочего множества программы в Т-кэше должно быть восстановлено "с нуля".
Это не относится к переключению двух потоков, исполняемых в рамках технологии Hyper-Threading, так как имеется механизм поддержки сосуществования таких потоков: у каждой трассы есть признак (тэг) номера потока, к которому она принадлежит.
Проведём грубую оценку потерь на полную смену содержимого Т-кэша. Предположим, что частота смены контекста составляет 100 раз в секунду, а время, необходимое для заполнения Т-кэша, равно 20-30 тысячам тактов при частоте процессора 2-3 GHz. В таком случае заполнение кэша займёт примерно 10 микросекунд из полного времени работы задачи между сменами контекста 10 миллисекунд. Таким образом, данная (предположительно завышенная) оценка показывает потери на уровне 0.1 % от общего времени выполнения.
Наличие такого неявного механизма реорганизации трасс чрезвычайно затрудняет проведение точных измерений функционирования Т-кэша. Несмотря на достаточно понятные правила формирования трасс (в зависимости от правильности предсказания условных переходов на момент их построения и т.п.), нельзя гарантированно получить ту или иную структуру исследуемой трассы - за короткое время механизм предсказания переходов изучит поведение программы и перестроит кэш в соответствии с более "правильными" предсказаниями. Поэтому приходится прибегать к искусственным приёмам типа использования инструкций, принудительно обрывающих трассу в нужном месте (косвенных переходов, вызовов подпрограмм и т.п.). В результате удаётся исследовать поведение Т-кэша лишь в неестественных и аномальных режимах, что позволяет выявить его структуру и особенности, но затрудняет проведение количественных оценок для более реалистичных ситуаций.

Эффективность работы и использования пространства кэша

Достаточно реалистичные оценки эффективности работы Т-кэша сделать довольно трудно. Противоречия возникают даже при оценке его "эквивалентного размера". При средней длине x86-инструкции в 2.5-3.5 байта и среднем числе МОПов (ячеек Т-кэша) в инструкции, равном 1.5, получаем среднюю "эффективную" длину ячейки МОПа на уровне 1.7-2.3 байта, что соответствовало бы эквивалентному размеру кэша инструкций 20-28 Кбайт. Однако в документации даётся оценка в 8-16 Кбайт, что, вероятно, как-то учитывает фрагментацию и потери на случаи многократного попадания одного и того же МОПа в кэш (при раскрутках циклов и в составе различных трасс).
Не претендуя на рассмотрение всех возможных вариантов многократного попадания МОПа в кэш, приведём простой пример. Предположим, что A, B, C, D ... - цепочка линейных участков кода, начинающихся с метки и заканчивающихся условным переходом на другую метку. При последовательном проходе всех участков без переходов получилась бы трасса A-B-C-D. Но если при первом проходе алгоритма будет выполнен обход участка B, а при одном из последующих - обход участка C, то в результате получатся две трассы: A-C-D и B-D. Таким образом, участок кода D в данном примере окажется сдублированным.
С другой стороны, блок в Т-кэше имеет достаточно малый размер - 6 МОПов, что эквивалентно (согласно приведённой выше оценке) 10-14 байтам обычного кэша инструкций. Даже если мы примем чуть более высокую оценку - 16 байт - то всё равно при сравнении с типичным размером блока у классического кэша в 64 байта (процессоры AMD K7/K8) потери на фрагментацию внутри блока окажутся намного ниже. В дополнение к этому, высокий уровень ассоциативности Т-кэша (число блоков в наборе), равный 8, снижает вероятность конфликтов из-за алиасинга в сравнении с другими процессорами (у K7/K8 он равен 2). Разумеется, при размещении очень больших связных участков кода эквивалентный размер Т-кэша процессора Pentium 4 (85-90 % от 20-28 Кбайт, т.е. 17-25 Кбайт) окажется всё же ниже, чем эффективный размер кэша у процессоров K7/K8 (который с учётом алиасинга можно было бы грубо оценить в 75 % от 64 Кбайт, т.е. в 48 Кбайт). Но для очень коротких трасс потенциал Т-кэша весьма велик - в идеале до 2048 трасс (по числу блоков), в то время как кэш процессоров K7/K8 состоит всего из 1024 блоков.
По занимаемому месту на кристалле процессора Т-кэш в несколько раз превосходит классический кэш инструкций. Например, размер ячейки для хранения МОПа оценивается приблизительно в 50 бит, что в 2.7-3.7 больше её "эффективного" размера в байтах. Таким образом, с учётом тэгов соотношение физических размеров Т-кэша и эквивалентного ему по объёму классического кэша формально (без учёта эффектов, рассмотренных выше) составит примерно 2.5-3.5 : 1. Однако следует отметить, что при создании кэшей 1-го уровня главным ограничивающим фактором обычно является не наличие свободного места, а возможность быстрого доступа. По этой причине для такого высокочастотного процессора, как Pentium 4, в качестве размера кэша инструкций с альтернативной (классической) организацией следовало бы принять 16 Кбайт (максимум 32 Кбайта).
Что касается скорости работы Т-кэша (с учётом предсказания переходов), то, как было показано в предыдущих разделах, она может варьироваться в очень широких пределах - от "идеальной" для алгоритмов, в которых все условные переходы были правильно предсказаны в момент формирования или перестройки трассы, до очень низкой при большом числе неправильных предсказаний.
Вполне возможно, что недостаточно высокая эффективность исполнения процессором Pentium 4 некоторых сильно ветвящихся кодов, разработанных без надлежащего следования принципам оптимальной кодогенерации для суперскалярных конвейерных процессоров, связана именно с трудностью построения хорошо предсказанных трасс МОПов в Т-кэше, а также с потерями на работу механизма передачи управления для коротких трасс.

Сравнение с альтернативной организацией кэша инструкций

Рассмотрим для сравнения организацию кэша инструкций и все связанные с этим вопросы в процессорах AMD Athlon (K7) и Athlon 64 (K8). Так как ключевыми вопросами являются возможность эффективной выборки инструкций и предсказания переходов без ущерба для темпа выборки полезных инструкций в суперскалярном процессоре, а также реализация декодирования сложных x86-инструкций в максимальном темпе, то сведём рассмотрение к этим двум пунктам.

1. В процессорах K7/K8 применён новаторский подход к реализации предсказания переходов. Вместо того, чтобы привязывать работу предиктора к каждой конкретной инструкции перехода (что особенно затруднительно в случае инструкций переменной длины в архитектуре x86), она привязывается к 16-байтовым блокам инструкций. Этим схема напоминает подход, реализованный в процессоре Pentium 4 (где предиктор привязывается к блокам Т-кэша через таблицу TBTB), но, в отличие от последнего, работает с x86-инструкциями в их исходном невыровненном размещении. Для каждого 16-байтового блока накапливается информация об истории трёх инструкций перехода (учитываются только "потенциально совершаемые" переходы, включая безусловные; для процессора K7 это может быть одна инструкция возврата из подпрограммы и два прочих перехода, для K8 - три перехода любого вида). Данная схема обеспечивает сразу несколько преимуществ:

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

Появляется возможность сделать "окно для предсказания переходов" более широким, чем "окно суперскалярной выборки инструкций". В частности, в процессорах K7/K8 считывание и обработка такого 16-байтового окна эквивалентны выборке и проверке (на предсказание перехода) приблизительно шести инструкций - что вдвое больше, чем окно выборки и декодирования (три инструкции). Благодаря этому обеспечивается некоторое опережения работы предсказателя переходов даже для кода, исполняемого в предельном темпе 3 инструкции за такт - и за счёт этого опережения удаётся сгладить исполнение и избежать потери одного такта (см. предыдущий пункт). В результате не теряются такты на инструкцию перехода по циклу и в случае предельного темпа выполнения инструкций;

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

2. Для обеспечения декодирования в максимальном темпе сложных x86-инструкций производится предекодирование инструкций перед помещением их в кэш. Формально инструкции помещаются в кэш в неизменённом виде, однако для каждого байта инструкции записывается ещё 3 бита дополнительной информации. По существу предекодирование представляет из себя разметку сложных x86-инструкций: помечаются начальный и конечный байты инструкции и байты префиксов, а также указывается тип инструкции - DirectPath либо VectorPath. Такая разметка позволяет основному декодеру работать с полной частотой процессора и при этом обрабатывать три равноценных потока инструкций, затрачивая на это небольшое число этапов конвейера.
Предекодирование ведётся также в небольшом темпе - около 4 байтов за такт для процессора K7, и несколько быстрее - для K8. При этом не производится предсказания переходов. Однако благодаря большому размеру кэша инструкций (64 Кбайт) операция предекодирования является редкой.
Одновременно с процессом предекодирования производится разметка инструкций перехода в специальной структуре - массиве селекторов переходов. Эта разметка нужна для подготовки работы блока предсказания переходов. В процессоре K8 этот массив сохраняется в ECC-битах кэша второго уровня (при вытеснении соответствующего блока из кэша инструкций), что позволяет использовать накопленную ранее информацию об истории переходов для их последующего предсказания.
Таким образом, операции предекодирования и разметки в процессорах K7/K8 можно рассматривать как некоторое подобие перекодирования x86-операций в МОПы в процессоре Pentium 4. Однако здесь такое преобразование не приводит к нарушению однозначного и линейного соответствия между программным адресом инструкции и её положением в кэше. Соответственно, не возникает необходимости в создании способа отображения одного адресного пространства в другое.
Разумеется, организация кэша инструкций в процессорах K7/K8 также имеет определённые ограничения и недостатки. Некоторые из них (большой размер блока и низкий уровень ассоциативности) были рассмотрены в предыдущем разделе, к числу других относятся ограничение на количество инструкций перехода в 16-байтном блоке, не очень большой размер таблицы адресов переходов (2048 элементов), недостаточно совершенный алгоритм предсказания направления переходов.
Тем не менее, организация кэша инструкций с использованием идеи предсказания переходов по 16-байтным блокам и предекодированием/разметкой инструкций явилась большим шагом вперёд в сравнении с близкими по идеологии процессорами Intel Pentium Pro, Pentium II и Pentium III. Реализация этих прогрессивных идей позволила увеличить производительность процессоров одновременно с некоторым упрощением их структуры. Однако данная схема, вероятно, не позволит достичь уровня тактовой частоты, характерного для процессора Pentium 4 (примерно в 1.4 раза более высокого при прочих равных условиях). Следовательно, для создания новых высокочастотных процессоров потребуется реализация новых идей с учётом опыта разработки микроархитектур Pentium 4 и K7/K8.

Заключение

Итак, мы убедились в том, организация Т-кэша в процессоре Pentium 4 очень сложна и запутанна. Несмотря на проведённое исследование и тщательное изучение всей доступной документации, Т-кэш по-прежнему содержит для нас немало загадок и оставляет открытыми множество вопросов. Так что не исключено, что многие загадки Т-кэша процессора Pentium 4 так никогда и не будут разгаданы.
Тем не менее, автор надеется, что выявленные характеристики и обнаруженные особенности поведения Т-кэша, а также полученные оценки скорости и эффективности выполнения различных операций не только удовлетворят академический интерес и техническое любопытство читателей, но и помогут в разрешении некоторых проблем с оптимизацией программ.
Автор выражает благодарность Виктору Картунову (артистический псевдоним "matik") за его интерес, своевременно проявленный к работе по исследованию Т-кэша и по существу спровоцировавший появление этой статьи, а также за неоценимую помощь в её критическом обсуждении.

Список литературы

IA-32 Intel Architecture Optimization Reference Manual. Intel, 2004.

IA-32 Intel Architecture Software Developer's Manual. Intel, 2004.

G. Hinton et al. The Microarchitecture of the Pentium 4 Processor. Intel Technology Journal, V.5, Q1, 2001.

G. Hinton et al. A 0.18-um CMOS IA-32 Processor With a 4-GHz Integer Execution Unit. IEEE Journal of Solid-State Circuits, V.36, N.11, 2001.

D. Boggs et al. The Microarchitecture of the Intel Pentium 4 Processor on 90nm Technology. Intel Technology Journal, V.8, Issue 1, 2004.

D. Carmean. The Intel Pentium 4 Processor. 2002.
http://www-cse.ucsd.edu/classes/wi02/cse240/carmean.pdf

P. DeMone. What's Up With Willamette? (Part 2). Real World Technologies, 2000.
http://www.realworldtech.com/page.cfm?ArticleID=RWT040400000000

A. Fog. How to optimize for the Pentium family of microprocessors. 2004.
http://www.agner.org/assem/pentopt.pdf

M. Milenkovic, A. Milenkovic, J. Kulick. Demystifying Intel Branch Predictors. Proceedings of the Workshop on Duplicating, Deconstructing and Debunking, 2002.

E. Rotenberg, S. Bennett, J.E. Smith. Trace Cache: a low latency approach to high bandwidth instruction fetching. Proceedings of the 29th International Symposium on Computer Architecture, 1996.

E. Rotenberg, S. Bennett, J.E. Smith. A Trace Cache Microarchitecture and Evaluation. IEEE Transactions on Computers, V.48, Issue 2, 1999.

Trace branch prediction unit.
United State Patent 6,014,742. 2000.

Method and apparatus for caching trace segments with multiple entry points.
United State Patent 6,073,213. 2000.

Method and apparatus for identifying potential entry points into trace segments.
United State Patent 6,076,144. 2000.

Trace based instruction caching.
United State Patent 6,170,038. 2001.

Branch prediction architecture.
United State Patent 6,332,189. 2001.

Multi-tag system and method for cache read/write.
United State Patent 6,493,797. 2002.

System and method for unrolling loops in a trace cache.
United State Patent 6,578,138. 2003.