Организация кэш-памяти современных процессоров

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

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

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

11. ОБЩАЯ ОРГАНИЗАЦИЯ И СПОСОБ ХРАНЕНИЯ ТРАСС В КЭШЕ

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

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

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

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

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

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

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

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

Использование нескольких «внутренних» разрядов адреса x86-инструкции для указания номера набора позволяет достаточно равномерно распределить заголовки трасс по наборам. Только в случае, когда имеется множество трасс, программные адреса первых инструкций в которых отстоят друг от друга на расстоянии, кратном 16 байтам, появится опасность, что только половина наборов сможет использоваться для размещения заголовков трасс. Однако и в этом случае не произойдёт потерь места, так как трассы состоят в общем случае из нескольких блоков.

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

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

Длина трассы ограничена 64 блоками, или 384 ячейками для МОПов. При таком ограничении в кэше может уместиться не менее 32 трасс. Максимальное число трасс равно  числу блоков в Т-кэше – 2048.

12. СРАВНЕНИЕ С АЛЬТЕРНАТИВНОЙ ОРГАНИЗАЦИЕЙ КЭША ИНСТРУКЦИЙ

Рассмотрим для сравнения  организацию кэша инструкций и все  связанные с этим вопросы в  процессорах 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 элементов), недостаточно совершенный алгоритм предсказания направления переходов.