Микропроцессорные системы

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

    К каждой очереди планировщика подсоединено одно или несколько специализированных функциональных устройств. Число операций, которые могут быть запущены на исполнение в каждом такте, обычно заметно превышает  ширину остальных трактов процессора и варьируется от 5 (P-III) до 10 (PPC970), что позволяет сглаживать пиковую  нагрузку и обеспечить высокую пропускную способность при неоднородной загрузке устройств.

    Помимо  арифметико-логических и адресных функциональных устройств, в каждом процессоре имеются  также устройства загрузки и выгрузки (Load/Store), которые производят доступ к кэшам данных и к оперативной памяти. Эти устройства работают асинхронно от других, и их обычно не изображают на блок-схемах. Логически эти устройства связаны с устройствами вычисления адресов чтения/записи (AGU). Устройства загрузки и выгрузки конвейеризованы и могут одновременно обслуживать большое количество запросов. Эти устройства также осуществляют предварительную выборку из оперативной памяти (копирование в кэши тех данных, использование которых ожидается в ближайшее время). На Рис. 1 группа блоков процессора, образующих подсистему внеочередного исполнения, обведена пунктирной линией.

                                        Рис.2

    На  Рис. 2 показан фрагмент кода с глубоким внеочередным исполнением. Этот фрагмент представляет собой итерацию алгоритма  перемножения матриц для процессора AMD Athlon [1]. Он состоит из 12 машинных инструкций и исполняется за 4 такта. Как видно из приведённой блок-схемы, алгоритм содержит 4 ветви, представляющие собой последовательности Load-Mul-Add (загрузка — умножение — сложение). Старт-стопное время исполнения каждой ветви составляет примерно 12 тактов, но благодаря внеочередному исполнению и переименованию регистров они обрабатываются параллельно, с глубоким перекрытием, обеспечивая темп выполнения 64-битных операций арифметики с плавающей точкой x87, близкий к предельному (две операции за такт).

                                        Рис.3

    На  Рис. 3 показаны различные состояния, в которых могут находиться МОПы, помещённые в буфер переупорядочения. В хронологическом порядке, каждый МОП может проходить через следующие стадии:

1. находится в очереди планировщика, но ещё не готов к исполнению;
2. готов к исполнению (все аргументы операции вычислены);
3. запущен на исполнение (диспетчеризован);
4. исполнен и ждёт отставки либо отмены спекулятивной ветви;
5. находится в процессе отставки.

2. Кэш инструкций в традиционных процессорах

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

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

    Если  нужный блок данных не найден в L1-кэше, он ищется в кэше 2-го уровня (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 байтам.

3. Предсказание  адреса и направления  переходов

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

    Необходимость предсказания адреса «целевой» инструкции вызвана тем, что этот адрес может  быть извлечён из 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 процентах случаев.

    В данной статье не будут рассматриваться  конкретные алгоритмы предсказания переходов, тем более что информация о них в настоящее время  обычно не разглашается разработчиками (см. статьи [2], [3]). Перечислим лишь некоторые  механизмы, используемые в новом  процессоре P8, имеющем наиболее совершенную  систему предсказания переходов:

    сочетание локального и глобального механизмов для предсказания «обычных» инструкций перехода с учётом истории их поведения;

    статический предсказатель для инструкций, совершающих  переход в первый раз, основанный на эмпирических закономерностях (например, «переход назад» обычно предсказывается  как совершённый, так как может  означать переход по циклу, а «переход вперёд» — как несовершённый);

    предсказатель коротких циклов, распознающий такие  переходы и определяющий число итераций цикла (позволяет правильно предсказать  момент выхода из цикла);

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

    предсказатель целевых адресов для инструкций выхода из подпрограммы, использующий небольшой аппаратный стек для запоминания  адресов возврата (Return Address Stack) для эффективной отработки инструкций Call — Return.

    В других процессорах компании Intel используется только часть перечисленных механизмов. Эти механизмы совершенствуются с каждым новым поколением процессоров.

    В процессорах AMD K8 и IBM PPC970 используются более простые механизмы предсказания обычных переходов, и отсутствуют  механизмы предсказания циклов и  чередующихся косвенных переходов.

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

    В процессоре PPC970 предсказатель переходов  работает менее эффективно — при  правильном предсказании теряется 2 такта, а минимальное время итерации цикла составляет 3 такта. Хотя предсказатель  просматривает инструкции с некоторым  опережением, это может лишь частично скрыть потерю указанных двух тактов, и в результате эффективность  исполнения перехода окажется ниже, чем  в других процессорах.