Исполнение процессорами инструкций x86 и x64 (Лекция 4)

Кэш инструкций

Во всех современных микроархитектурах, за исключением процессора P-4, кэш инструкций (I-кэш) организован классическим образом.

Кэш 1-го уровня (L1-кэш) имеет размер 32 Кбайт и состоит из блоков по 64 байта, организованных в виде 64 наборов по 8 блоков. Для поиска требуемого элемента данных в кэше используется комбинированный алгоритм, сочетающий прямую адресацию по нескольким разрядам адреса с ассоциативным поиском. Младшие 6 разрядов адреса b5-0 указывают положение байта в 64-байтовом блоке и для поиска блока не используются. Следующие 6 разрядов адреса b11-6 указывают номер набора, а нахождение требуемого блока в наборе осуществляется сравнением самых старших разрядов адреса (ключа) с соответствующими разрядами адреса, хранящимися для каждого блока в наборе (тэгами). Таким образом, элемент данных по какому-либо адресу может располагаться в рассматриваемом кэше в одном из 8 блоков конкретного набора.

Если нужный блок данных не найден в L1-кэше, он ищется в кэше второго уровня (L2-кэше), и далее, если не найден и там, в оперативной памяти. Затем этот блок записывается в L1-кэш. Если все блоки в наборе уже заняты, то один из блоков удаляется (вытесняется). Как правило, для вытеснения используется алгоритм LRU (Least Recently Used — «наименее используемый в последнее время»).

Описанная организация кэша называется «наборно-ассоциативной» (set-associative). Число блоков в наборе (в данном случае 8) называется уровнем ассоциативности кэша. Оно определяет, сколько блоков данных, отстоящих друг от друга на расстоянии с определённой кратностью (в данном случае – кратном 4 Кбайт), может одновременно находиться в кэше. Данное ограничение называют проблемой алиасинга. Чем выше уровень ассоциативности, тем меньше вероятность, что различные блоки данных столкнутся с алиасингом. Например, у L1-кэшей процессора K8 уровень ассоциативности равен 2 при размере 64 Кбайт, а I-кэш процессора PPC970 имеет уровень ассоциативности, равный 1 при том же размере 64 Кбайт (такая организация называется прямым отображением), и состоит из блоков по 128 байт.

Обычно поиск в кэшах осуществляется по физическому адресу элемента данных. Однако преобразование адреса из программного (логического) в физический требует определённого времени – для этого используется вспомогательная структура, похожая на небольшой кэш и называемая буфером преобразования адреса (TLB, Translation Lookaside Buffer). Поэтому для адресации набора L1-кэша, чтобы ускорить поиск, используют необходимые разряды программного адреса. В тех случаях, когда эти разряды адресуют не больше одной страницы памяти (размер которой, как правило, равен 4 Кбайт), они совпадают с соответствующими разрядами физического адреса. Например, в процессорах P-M и P8 для этого используются разряды b11-6, и данное условие соблюдается. Арифметически это условие можно выразить так: частное от деления размера кэша на уровень ассоциативности не должно превышать размера страницы. Легко видеть, что в процессорах K8 и PPC970 данное условие не соблюдается (64K/2=32K, 64K/1=64K).

В I-кэше процессора K8, помимо байтов инструкций, хранятся также так называемые биты предекодирования — по 3 разряда на байт. Их назначение будет описано в разделе про декодирование.

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

Предсказание переходов

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

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

В современных процессорах для предсказания адреса перехода обычно используют специальную таблицу адресов переходов BTB (Branch Target Buffer). Эта таблица устроена подобно кэшу и содержит адреса инструкций, на которые ранее производились переходы. Например, в процессоре P-III таблица BTB имеет размер 512 элементов и организована в виде 128 наборов с ассоциативностью 4. Для адресации набора используются младшие разряды адреса 16-байтового блока инструкций (b10-4). Если в этом блоке есть инструкции перехода, и если эти инструкции отрабатывали ранее, то алгоритм предсказания может очень быстро найти адрес целевой инструкции в таблице BTB и начать считывание блока, содержащего эту инструкцию. Адреса целевых инструкций помещаются в BTB в момент отставки соответствующих инструкций перехода.

В более новых процессорах размер таблицы BTB достигает 2048 элементов (K8) и 4096 элементов (P-4). Организация данной подсистемы в процессоре K8 несколько отличается от классической и основывается на предварительной разметке блоков инструкций в так называемых массивах селекторов перед помещением их в I-кэш. Эти селекторы привязаны к положению инструкций в I-кэше и при их вытеснении оттуда сохраняются в L2-кэше (в так называемых ECC-битах, предназначающихся для коррекции ошибок). Элементы таблицы BTB также привязаны к положению инструкций в I-кэше и теряются при их вытеснении. Это несколько снижает эффективность предсказания адресов переходов в процессоре K8.

Для предсказания направления условного перехода используется другой механизм, основанный на изучении поведения переходов в программе в процессе её выполнения (своего рода «сбор статистики»). Этот механизм учитывает как локальное поведение конкретной инструкции перехода (например, «как правило, переходит», «как правило, не переходит»), так и глобальные закономерности («чередуется по определённому закону» и т.п.). История поведения инструкций условного перехода записывается в специальных структурах, обычно называемых «таблицами истории переходов» (Branch History Table, BHT). Современные механизмы предсказания переходов обеспечивают правильное предсказание более чем в 90 процентах случаев.

Механизм предсказания переходов работает одновременно с декодером инструкций и независимо от него. Благодаря эффективной реализации предсказания адреса перехода в процессорах P-III, P-M, P-M2, P8 и K8 при правильном предсказании теряется всего 1 такт. Это означает, что минимальное время, затрачиваемое на итерацию цикла (либо на один переход в цепочке переходов), составляет 2 такта. По существу, предсказатель переходов в таком цикле (или цепочке) работает в своём независимом цикле, состоящем из двух стадий – предсказания и считывания нового блока кэша – а декодер и прочие подсистемы процессора обрабатывают инструкции из вновь считываемых блоков. Поскольку предсказатель переходов «просматривает» целый блок, который может содержать большое число инструкций, то он может «опережать» декодер в своём просмотре. Благодаря этому переход может быть совершён раньше, чем исчерпаются инструкции в текущем блоке, и указанной потери такта не произойдёт – этот такт будет скрыт на фоне бесперебойной работы декодера.

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

Длина конвейера непредсказанного перехода не всегда указывается в документации и известна весьма приблизительно. Её довольно трудно замерить, так как современные предсказатели переходов работают достаточно эффективно и не позволяют добиться гарантированной доли неправильных предсказаний в тестах. Можно дать следующие примерные оценки длины конвейера: P-III – 11, P-M – 12, P-4 – 20, P-4E – 30, P8 – 14, K8 – 11, PPC970 – 13.

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

Исполнение инструкций

Большинство процессоров обрабатывают и исполняют инструкции архитектуры x86 (называемой также IA-32) и расширенной архитектуры x86-64 (называемой также AMD64 либо EM64T). Принципиальных различий по структуре машинной инструкции между архитектурами x86 и x86-64 нет, поэтому по тексту будем везде использовать общее наименование «x86-инструкции». Эти инструкции имеют очень сложный и нерегулярный формат и могут состоять из нескольких составных частей: одного или нескольких однобайтных префиксов, кода операции длиной от 1 до 3 байтов, описателя типа адресации операндов (ModR/M), указателя регистров базы, индекса и масштаба индексирования (SIB), поля смещения адреса и непосредственного операнда. Длина x86-инструкции может варьироваться от 1 до 15 байтов.

Для суперскалярной обработки необходимо в каждом такте извлекать из входного потока несколько инструкций переменной длины и отправлять каждую из них в отдельный блок декодирования для преобразования в микрооперации (МОПы). Эта задача представляется очень трудоёмкой, поэтому необходимо применение специальных средств, которые позволили бы её облегчить. В разных процессорах x86 используются различные приёмы и механизмы, обеспечивающие бесперебойную обработку инструкций. Лишь для процессора PPC970 не требуется никаких ухищрений, так как в RISC-архитектуре IBM Power машинные инструкции имеют фиксированную длину (4 байта) и регулярный формат. По типу используемых механизмов рассматриваемые процессоры можно разбить на четыре класса:

PPC970: Не используется никакой механизм, так как инструкции имеют фиксированную длину и формат.

P-III, P8: После выборки из I-кэша производится разметка инструкций (определение их границ и положения кода операции) в устройстве, называемом определителем длины инструкций (Instruction Length Decoder, ILD).

K8: Перед помещением блоков инструкций в I-кэш производится предварительное декодирование (предекодирование) с аналогичной разметкой, информация о разметке записывается в дополнительные биты при каждом байте в I-кэше.

P-4: Перед помещением в кэш производится полное декодирование инструкций, сформированные МОПы записываются в этот кэш (Т-кэш) в виде трасс.

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