Глава 9
Основные направления в архитектуре процессоров
Ранее уже были рассмотрены основные составляющие центрального процессора. В данном разделе основное внимание уделено вопросам общей архитектуры про­цессоров как единого устройства и способам- повышения их производительности.
Конвейеризация вычислений
Совершенствование элементной базы уже не приводит к кардинальному росту производительности ВМ. Более перспективными в этом плане представляются архитектурные приемы, среди которых один из наиболее значимых — конвейери­зация.
Для пояснения идеи конвейера сначала обратимся к рис. 9.1, а, где показан от­дельный функциональный блок (ФБ). Исходные данные помещаются во входной регистр Ргвх, обрабатываются в функциональном блоке, а результат обработки фик­сируется в выходном регистре Ргвых. Если максимальное время обработки в ФБ равно Ттш,, то новые данные могут быть занесены во входной регистр Ргвх не ранее, чем спустя Ттш,.
Рис. 9.1. Обработка информации: а — в одиночном блоке; б —в конвейере с регистрами; в — в конвейере с буферной памятью
4 1 4 Глава 9. Основные направления в архитектуре процессоров
Теперь распределим функции, выполняемые в функциональном блоке ФБ (см. рис. 9.1, а), между тремя последовательными независимыми блоками: ФБ,, ФБг и ФБ3, причем так, чтобы максимальное время обработки в каждом ФЦ было одина­ковым и равнялось ТШЛ1/3.. Между блоками разместим буферные регистры Ргр (рис. 9.1, 6), предназначенные для хранения результата обработки в ФБ^ на слу­чай, если следующий за ним функциональный блок еще не готов использовать этот результат. В рассмотренной схеме данные на вход конвейера могут подаваться с интервалом Тшах/3(втрое чаще), и хотя задержка от момента поступления первой единицы данных в Ргвх до момента появления результата ее обработки на выходе Ргвьш по-прежнему составляет Tmax, последующие результаты появляются на выхо­де Ргвьжуже с интервалом Т^/3.
На практике редко удается добиться того, чтобы задержки в каждом ФБ, были одинаковыми. Как следствие, производительность конвейера снижается, посколь­ку период поступления входных данных определяется максимальным временем их обработки в каждом функциональном блоке. Для устранения этого недостатка или, по крайней мере, частичной его компенсации каждый буферный регистр Ргр сле­дует заменить буферной памятью БЦ способной хранить множество данных и орга­низованной по принципу FIFO — "первым вошел — первым вышел" (рис. 9.1, в). Обработав элемент данных, ФБР заносит результат в БЦ извлекает из БПЫ новый элемент данных и приступает к очередному циклу обработки, причем эта последо­вательность осуществляется каждым функциональным блоком независимо от дру­гих блоков. Обработка в каждом блоке может продолжаться до тех пор, пока не ликвидируется предыдущая очередь или пока не переполнится следующая оче­редь. Если емкость буферной памяти достаточно велика, различия во времени об­работки не сказываются на производительности, тем не менее желательно, чтобы средняя длительность обработки во всех ФБ, была одинаковой.
В архитектуре вычислительных машин можно найти множество объектов, где конвейеризация обеспечивает ощутимый прирост производительности ВМ. Ранее уже рассматривались два таких объекта — операционные устройства и память, од­нако наиболее ощутимый эффект достигается при конвейеризации этапов машин­ного цикла.
По способу синхронизации работы ступеней конвейеры могут быть синхрон-нымииасинхронными.ДлятрадиционныхВМхарактерны синхронные конвейеры. Связано это, прежде всего, с синхронным характером работы процессоров. Ступе­ни конвейеров в процессоре обычно располагаются близко друг от друга, благода­ря чему тракты распространения сигналов синхронизации получаются достаточ­но короткими и фактор «перекоса» сигналов становится не столь существенным. Асинхронные конвейеры оказываются полезными, если связь между ступенями не столь сильна, а длина сигнальных трактов между разными ступенями сильно роз­нится. Примером асинхронных конвейеров могут служить систолические масси­вы (систолическая обработка будет рассмотрена в последующих разделах).
Синхронные линейные конвейеры
Эффективность синхронного конвейера во многом зависит от правильного выбо­ра длительности тактового периода Тк. Минимально допустимую Тк можно опре­делить как сумму наибольшего из времен обработки на отдельной ступени кон-
Конвейеризация вычислений 4 15
вейера ТСМАХ и времени записи результатов обработки в буферные регистры меж­ду ступенями конвейераТБР:
Из-за вероятного «перекоса» в поступлении тактирующего сигнала в разные ступени конвейера предыдущую формулу следует дополнить еще одним элемен­том — максимальной величиной «перекоса»Тпк:
*к *" ^смах + ?бр + ^пк-Каждая ступень может содержать множество логических трактов обработки. Тк определяется наиболее длинными трактами во всех ступенях конвейера. При разработке конвейера необходимо учитывать, что для двух последовательных эле­ментов, обрабатываемых одной и той же ступенью, обработка первого элемента может проходить по тракту максимальной длины, а второго элемента — по мини­мальному тракту. В итоге результат обработки второго элемента может появиться на выходе ступени прежде, чем в выходном регистре ступени будет запомнен пре­дыдущий результат. Чтобы избежать подобной ситуации, сумма TbV + Tm должна быть меньше минимального времени обработки в ступени! Гсыш, откуда
Выбор длительности тактового периодадля конвейера должен осуществляться с соблюдением соотношения
Несмотря на очевидные преимущества выбора Тк равным нижнему пределу, проектировщики ВМ обычно ориентируются на среднее значение между нижним и верхним пределами.
Метрики эффективности конвейеров
Чтобы охарактеризовать эффект, достигаемый за счет конвейеризации вычисл­или, обычно используюттри метрики: ускорение, эффективность и производитель­ность.
Полускорением понимается отношение времени обработки без конвейераи при его наличии. Теоретически наилучшее время обработки входного потока из N зна­чений Тш на конвейере с ^ступенями и тактовым периодом Тк можно определить выражением
Формула отражает тот факт, что до появления на выходе конвейера результата обработки первого элемента должно пройти ^тактов, а последующие результаты будут следовать в каждом такте.
В процессоре без конвейера общее время выполнения составляет NKTK. Таким образом, ускорение вычислений S за счет конвейеризации вычислений можно опи­сать формулой
ПриN—* « ускорение стремится к величине, равной количеству ступеней в кон­вейере.
4 1 6 Глава 9. Основные направления в архитектуре процессоров
Еще одной метрикой, характеризующей конвейерный процессор, является эф­фективность Е — доля ускорения, приходящаяся на одну ступень конвейера:
В качестве третьей метрики часто выступает пропускная способностыши произ­водительность Р — эффективность, деленная на длительность тактового периода:
При N —► «* эффективность стремится к единице, а производительность — к ча­стоте тактирования конвейера:
Нелинейные конвейеры
Конвейер не всегда представляет собой линейную цепочку этапов. В ряде ситуа­ций оказывается выгодным, когда функциональные блоки соединены между со­бой не последовательно, а в соответствии с логикой обработки, при этом одни бло­ки в цепочке могут пропускаться, а другие — образовывать циклические структуры. Это позволяет с помощью одного и того же конвейера одновременно вычислять более одной функции, однако если эти функции конфликтуют между собой, то такой конвейер трудно загрузить полностью! Структура нелинейного конвейера, одновременно вычисляющего две функции Хи Ύ, приведена на рис. 9.2. Там же показана последовательность, в которой функциями X и У востребуются те или иные функциональные блоки.
Чтобы определить, когда пора приступать к повторному вычислению той или иной функции, необходимо построить диаграмму однократной реализации этой функции и отследить по ней моменты, когда такой запуск не приведет к конфлик­ту, связанному с одновременным обращением к одному и тому же функциональ­ному блоку.
Так, в ходе реализации функции Хзапуск очередного ее вычисления возможен после 1,3 и 6 тактов. Запуск параллельного вычисления функции Увозможен после
Конвейеризация вычислений 4 17
2 и 4 тактов. При запуске функции Уочередной ее запуск позволен после тактов 1,
3 и 5, а параллельный запуск функцииХдопустим после 2 и 4 тактов.
Конвейер команд
Идея конвейера команд была предложена в 1956 году академиком С. А.Лебеде-вым. Как известно, цикл команды представляет собой последовательность этапов. Возложив реализацию каждого из них на самостоятельное устройство и последо­вательно соединив такие устройства, мы получим классическую схему конвейера команд. Для иллюстрации воспользуемся примером, приведенным в [200]. Выде­лим в цикле команды шесть этапов:
1.  Выборка команды (ВК). Чтение очередной команды из памяти и занесение ее в регистр команды.
2.  Декодирование команды (ДК). Определение кода операции и способов адреса­ции операндов.
!3. Вычисление адресов операндов (ВА). Вычисление исполнительных адресов каждого из операндов в соответствии с указанным в команде способом их адре­саций.
4.  Выборка операндов (ВО). Извлечение операндов из памяти. Эта операция не нужна для операндов, находящихся в регистрах.
5.  Исполнение команды (ИК). Исполнение указанной операции.
6.  Запись результата (ЗР), Занесение результата в память.
На рис. 9.3 показан конвейер с шестью ступенями, соответствующими шести этапам цикла команды. В диаграмме предполагается, что каждая команда обяза­тельно проходит все шесть ступеней, хотя этот случай не совсем типичен. Так, ко­манда загрузки регистра не требует этапа ЗР. Кроме того, здесь принято, что все этапы могут выполняться одновременно. Без конвейеризации выполнение девяти команд заняло бы 9 х 6 = 54 единицы времени. Использование конвейера позво­ляет сократить время обработки до 14 единиц.
14 За*. 470
418 Глава 9. Основные направления в архитектуре процессоров
Конфликты в конвейере команд
Полученное в примере число 14 характеризует лишь потенциальную производи­тельность конвейера команд. На практике в силу возникающих в конвейере конф­ликтных ситуаций достичь такой производительности не удается. Конфликтные ситуации в конвейере принято обозначать термином риск (hazard), а обусловлены они могут быть тремя причинами:
-  попыткой нескольких команд одновременно обратиться к одному и тому же
ресурсу ВМ (структурный риск);
-  взаимосвязью команд по данным (риск по данным);
-  неоднозначностью при выборке следующей команды в случае команд перехода
(риск по управлению).
Структурный риск (конфликт по ресурсам) имеет место, когда несколько ко­манд, находящихся на разных ступенях конвейера, пытаются одновременно ис­пользовать один и тот же ресурс, чаще всего — память. Так, в типовом цикле ко­манды сразу три этапа (ВК, 80 и ЗР) связаны с обращением к памяти. Диаграмма (см. рис. 9.3) показывает, что все три обращения могут производиться одновре­менно, однако на практике это не всегда возможно. Подобных конфликтов частич­но удается избежать за счет модульного Построения памяти и использования кэш­памяти — имеется вероятность того, что команды будут обращаться либо к разным модулям ОП, либо одна из них станет обращаться к основной памяти, а другая -к кэш-памяти. С этих позиций выгоднее разделять кэш-память команд и кэш-па­мять данных. Конфликты из-за одновременного обращения к памяти могут и не возникать, поскольку для многих команд ступени выборки операнда и записи ре­зультата часто не требуются. В целом, влияние структурного риска на производи­тельность конвейера по сравнению с другими видами рисков сравнительно неве­лико.
Риск по данным, в противоположность структурному риску — типичная и регу-данным положим, что две команды в конвейере (i и j) предусматривают обраще­ние к одной и той же переменной х, причем команда i предшествует команде). В общем случае между i и j ожидаемы три типа конфликтов по данным (рис. 9.4):
-Чтение после записи» (ЧПЗ): команда/читает*до того, как команда i успела записать новое значение х, то есть j ошибочно получит старое значение* вмес­то нового. '
- «Запись после чтения» (ЗПЧ): команда; j записывает новое значение х до того,
как команда i успела прочитатьх:, то есть команда i ошибочно получит новое значение х вместо старого.
-  «Запись после записи» (ЗПЗ): командау записывает новое значение* прежде,
чем команда i успела записать в качестве * свое значение, то есть * ошибочно содержит i-e значение * вместоу- го.
Возможен и четвертый случай, когда команда] читает х прежде команды L Этот случай не вызывает никаких конфликтов, поскольку как i, так у получат верное значение *.
Конвейеризация вычислений 419
Наиболее частый вид конфликтов по данным — ЧП 3, поскольку операция чте­ния в цикле команды (этап Ю) предшествует операции записи (этап ЗР). По той же причине конфликты типа ЗПЧ большой проблемы не представляют. Сложнос­ти появляются, только если структура конвейера допускает запись прежде чтения или если команды в конвейере обрабатываются в последовательности, отличной от предписанной программой. Такое возможно, если командам в конвейере разре­шается «догонять» предшествующие им команды, приостановленные из-за како­го-то конфликта. Конфликт типа ЗПЗ также не вызывает особых проблем в кон­вейерах, где команды следуют в порядке, определенном программой, и могут производить запись только на этапе ЗР. В худшем случае, когда одна команда дого­няет другую из-за приостановки последней, имеет место конфликт по ресурсу — попытка одновременного доступа к одной и той же ячейке.
В борьбе с конфликтами по данным выделяют два аспекта: своевременное об­наружение потенциального конфликта и его устранение. Признаком возникнове­ния конфликта по данным между двумя командами Ϊ и у служит невыполнение хотя бы одного из трех условий Бернстейна (Bernstein's Conditions):
а дляЧПЗ:0(п/(Л= 0: ■ для ЗПЧ: 7(0 n 0(f) -0; ■■ для ЗПЗ: ft п 00)- 0-
Где 0(к) — множество ячеек, изменяемых командой к; 1(1) — множество ячеек, читаемых командой 1; 0 — пустое множество; п — операция пересечения множеств.
Критерий может быть распространен и на большее число команд: для трех ко­манд подобных уравнений будет 9, для четырех команд — 18 (по три на каждую пару). Соблюдение соотношений является достаточным, но не необходимым ус­ловием, поскольку в ряде случаев коллизий может и не быть.
Для борьбы с конфликтами поданным применяются как программные, так и ап­паратные методы.
Программные методы ориентированы на устранение самой возможности кон­фликтов еще на стадии компиляции программы. Оптимизирующий компилятор пытается создать такой объектный код, чтобы между командами, склонными к
42 0 Глава 9. Основные направления в архитектуре процессоров
конфликтам, находилась достаточное количество нейтральных в этом плане ко­манд. Если такое не удается, то между конфликтующими командами компилятор вставляет необходимое количество команд типа «Нет операции»,
Фактическое разрешение конфликтов возлагается на аппаратные методы. Наи­более очевидным решением является остановка команды;"на несколько тактов с тем, чтобы команда i успела завершиться или, по крайней мере, миновать ступень конвейера, вызвавшую конфликт. Соответственно задерживаются и команды, сле­дующие в конвейере 3aj-n командой. Данную ситуацию назьшают «пузырьком» в конвейере. Иногда приостанавливают только команду/, не задерживая следую­щие за ней команды. Это более эффективный прием, но его реализация усложняет конвейер.
Понятно, что остановки конвейера снижают его эффективность и разработчи­ки ВМ всячески стремятся сократить общее число остановок или хотя бы их дли­тельность. Поскольку наиболее частые конфликты по данным — это ЧПЗ, основ­ные усилия тратятся на противодействие именно этому типу конфликтов. Среди известных методов борьбы с ЧПЗ наибольшее распространение получил прием ускоренного продвижения информации (forwarding). Обычно между двумя сосед­ними ступенями конвейера располагается буферный регистр, через который пред­шествующая ступень передает результат своей работы на последующую ступень, то есть передача информации возможна лишь между соседними ступенями кон­вейера. При ускоренном продвижении, когда для выполнения команды требуется операнд, уже вычисленный предыдущей командой, этот операнд может бьпь по­лучен непосредственно из соответствующего буферного регистра, минуя все про­межуточные ступени конвейера. С данной целью в конвейере предусматриваются дополнительные тракты пересылки информации (тракты опережения, тракты об­хода), снабженные средствами мультиплексирования.
Наибольшие проблемы при создании эффективного конвейера обусловлены командами, изменяющими естественный порядок вычислений1. Простейший кон­вейер ориентирован на линейные программы. В нем ступень выборки извлекает команды из последовательных ячеек памяти, используя для этого счетчик команд (СК). Адрес очередной команды в линейной программе формируется автомати­чески, за счет прибавления к содержимому СК числа, равного длине текущей ко-В них обязательно присутствуют команды управления, изменяющие последова-возврат из процедуры и т. п. Доля подобных команд в программе оценивается как 10-20% (по некоторым источникам она существенно больше). Выполнение команд, изменяющих последовательность вычислений (в дальнейшем будем их называть командами перехода), может приводить к приостановке конвейе­ра на несколько тактов, из-за чего производительность процессора снижается. Приостановки конвейера при выполнении команд перехода обусловлены дву­мя факторами.
В фон-неймановской ВМ команды размещаются в ячейках памяти и извлекаются для выполнения в том же порядке, в каком они следуют в программе. Такую последовательность выполнения команд программы называют естественной.
Конвейеризация вычислений 4 2 1
Первый фактор характерен для любой команды перехода и связан с выборкой команды из точки перехода (по адресу, указанному в команде перехода). То, что текущая команда относится к командам перехода, становится ясным только после декодирования (после прохождения ступени декодирования), то есть спустя два такта от момента поступления Команды на конвейер. За это время на первые сту­пени конвейера уже поступят новые команды, извлеченные в предположении, что естественный порядок вычислений не будет нарушен. В случае перехода эти сту­пени нужно очистить и загрузить в конвейер команду, расположенную по адресу перехода, для чего нужен исполнительный адрес последней. Поскольку в коман­дах перехода обычно указаны лишь способ адресации и адресный код, исполни-ступени конвейера. Таким образом, реализация перехода в конвейере требует оп­ределенных дополнительных операций, выполнение которых равносильно оста­новке конвейера как минимум на два такта.
Вторая причина нарушения ритмичности работы конвейера имеет отношение только к командам условного перехода Для пояснения сути проблемы воспользу­емся ранее приведенной условной программой рис. 9.3), несколько изменив по­становку задачи (рис. 9.5).
Пусть команда 3 — это условный переход к команде 15. До завершения коман­ды 3 невозможно определить, какая из команд (4-я или 15-я) должна выполняться следующей, поэтому конвейер просто загружает следующую команду в последо­вательности (команду 4) и продолжает свою работу. В варианте, показанном на рис. 9.3, переход не произошел и получена максимально возможная производи­тельность. На рис. 9.5 переход имеет место, о чем неизвестно до 7-го шага. В этой точке конвейер должен бьпь очищен от ненужных команд, выполнявшихся до дан­ного момента. Лишь на шаге 8 на конвейер поступает нужная команда 15, из-за чего в течение тактов от 9 до 12 не будет завершена ни одна другая команда. Это и есть издержки из-за невозможности предвидения исхода команды условного
4 2 2 Глава 9. Основные направления в архитектуре процессоров
перехода. Как видно, они либо существенно больше, чем для прочих команд перехода (если переход происходит), либо отсутствуют вовсе (если переход не происходит).
Для сокращений задержек, обусловленных выборкой команды из точки пере­хода, применяются несколько подходов:
» вычисление исполнительного адреса перехода на ступени декодирования ко­манды;
-   использование буфера адресов перехода;
-  использование кэш-памяти для хранения команд, расположенных в точке пе-. рехода;
-   использование буфера цикла.
В результате декодирования команды выясняется не только ее принадлежность к командам перехода, но также способ адресации и адресный код точки перехода. Это позволяет сразу же приступить к вычислению исполнительного адреса пере­хода, не дожидаясь передачи команды на третью ступень конвейера, и тем самым сократить время остановки конвейера с двух тактов до одного. Для реализации этой идеи в состав ступени декодирования вводятся дополнительные сумматоры, с помощью которых и вычисляется исполнительный адрес точки перехода.
Буфер адресов перехода (ВТВ, Branch Target Buffer) представляет собой кэш­память небольшой емкости, в которой хранятся исполнительные адреса точек пе­рехода нескольких последних команд, для которых переход имел место. В роли тегов выступают адреса соответствующих команд. Перед выборкой очередной ко­манды ее адрес (содержимое счетчика команд) сравнивается с адресами команд, представленных в ВТВ. Для команды, найденной в буфере адресов перехода, ис­полнительный адрес точки перехода не вычисляется, а берется из ВТВ, благодаря чему выборка команды из точки перехода может быть начата на один такт раньше. Команда, ссылка на которую в ВТВ отсутствует, обрабатывается стандартным образом. Если это команда перехода, то полученный при ее выполнении исполни­тельный адрес точки перехода заносится в ВТВ, при условии, что команда завер­шилась переходом. При замещении информации в ВТВ обычно применяется ал­горитм LRU.
Применение ВТВ дает наибольший эффект, когда отдельные команды перехо­да в программе выполняются многократно, что типично для циклов. Обычно ВТВ используется не самостоятельно, а в составе других, более сложных схем компен­сации конфликтов по управлению.
Кэш-память команд, расположенных в точке перехода (BTIC, Branch Target Instruction Cache), — это усовершенствованный вариант ВТВ, где в кэш-память помимо исполнительного адреса команды в точке перехода записывается также и код этой команды. За счет увеличения емкости кэш-памяти BTIC позволяет при повторном выполнении команды перехода исключить не только этап вычисления исполнительного адреса точки перехода, но и этап выборки расположенной там команды. Преимуществаданного подхода в наибольшей степени проявляются при многократном исполнении одних и тех же команд перехода, главным образом при реализации программных циклов.
Конвейеризация вычислений 4 2 3
Буфер цикла представляет собой маленькую быстродействующую память, вхо­дящую в состав первой ступени конвейера, где производится выборка команд. В буфере сохраняются коды « последних команд в той последовательности, в ко­торой они выбирались. Когда имеет место переход, аппаратура сначала проверяет, нет ли нужной команды в буфере, и если это так, то команда извлекается из буфера. Стратегия наиболее эффективна при реализации циклов и итераций, чем и объяс­няется название буфера Если буфер достаточно велик, чтобы охватить все тело цикла, выборку команд из памяти достаточно выполнить только один раз в первой итерации, поскольку необходимые для последующих итераций команды уже на­ходятся в буфере.
По принципу использования буфер цикла похож на BTIC, с той разницей, что в нем сохраняется последовательность выполнения команд, а сам буфер меньше по емкости и дешевле.
Среди ВМ, где реализован буфер цикла, можно упомянуть некоторые вычис­лительные машины фирмы CDC (Star 100,6600,7600) и суперЭВМ CRAY-1. Спе­циализированная версия буфера цикла имеется и в микропроцессоре Motoro­la 68010, где он используется для особых циклов, включающих в себя команду «Уменьшение и переход по условию».
Методы решения проблемы условного перехода
Несмотря на важность аспекта вычисления исполнительного адреса точки пере­хода, основные усилия проектировщиков ВМ направлены на решение проблемы условных переходов, поскольку именно последние приводят к наибольшим издерж­кам в работе конвейера. Для устранения или частичного сокращения этих издер­жек были предложены различные способы, которые условно можно разделить на четыре группы:
-   буферы предвыборки;
-   множественные потоки;
-   задержанный переход;
-   предсказание перехода
Равномерность поступления команд на вход конвейера часто нарушается, на­пример из-за занятости памяти или при выборке команд, состоящих из несколь­ких слов. Чтобы добиться ритмичности подачи команд на вход конвейера, между ступенью выборки команды и остальной частью конвейера часто размещают бу­ферную память, организованную по принципу очереди (FIFO) и называемую бу­фером предвыборки. Буфер предвыборки можно рассматривать как несколько до­полнительных ступеней конвейера. Подобное удлинение конвейера не сказывается на его производительности (при заданной тактовой частоте); оно лишь приводит к увеличению времени прохождения команды через конвейер. Типичные буферы предвыборки в известных процессорах рассчитаны на 2-8 команд.
Чтобы одновременно с обеспечением ритмичной работы конвейера решить и проблему условных переходов, в конвейер включают два таких буфера (рис. 9.6).
Каждая извлеченная из памяти и помещенная в основной буфер команда ана­лизируется блоком перехода При обнаружении команды условного перехода (УП)
4 2 4 Глава 9. Основные направления в архитектуре процессоров
блок перехода вычисляет исполнительный адрес точки перехода и параллельно с продолжением последовательной выборки в основной буфер организует выбор­ку в дополнительный буфер команд, начиная с точки УП. Далее блок перехода определяет исход команды УП, в зависимости от которого подключает к остатку конвейера нужный буфер, при этом содержимое другого буфера сбрасывается. Уп­рощенный вариант подобного подхода применен в IBM 360/91, где дополнитель­ный буфер рассчитан на одну команду, то есть выигрыш достигается за счет ис­ключения времени' на выборку команды из точки перехода.
Помимо необходимости дублирования части оборудования, у метода имеется еще один недостаток. Так, если в потоке команд несколько команд УП следуют одна задругой или находятся достаточно близко, количество возможных ветвле­ний увеличивается и, соответственно, должно быть увеличено и число буферов предвыборки.
Другим решением проблемы переходов служит дублирование начальных ступеней конвейера и создание тем самым двух параллельных потоков команд (рис. 9.7).
В одной из ветвей такого «раздвоенного» конвейера последовательность вы­борки и выполнения команд соответствует случаю, когда условие перехода не вы­полнилось, во второй ветви — случаю выполнения этого условия. Для ранее рас­смотренного примера (см. рис. 9,5) в одном из потоков может обрабатываться последовательность команд 4-6, а в другом— 15-17. Оба потока сходятся в точке,
Конвейеризация вычислений 42 5
где итог проверки условия перехода становится очевидным. Дальнейшее продви­жение по конвейеру продолжает только «правильный» поток. Основной недоста­ток метода состоит в том, что на конвейер или в поток может поступить новая ко­манда У П до того, как будет принято окончательное решение по текущей команде перехода. Каждая такая команда требует дополнительного потока. Несмотря на это, стратегия позволяет улучшить производительность конвейера. При­мерами ВМ, где используются два или более конвейерных потоков, служат ШМ 370/168 и IBM 3033.
Стратегия задержанного перехода предполагает продолжение выполнения ко­манд, следующих за командой УП, вне зависимости от ее исхода. Естественно, что это имеет смысл, лишь когда последующие команды являются «полезными», то есть такими, которые все равно должны быть когда-то выполнены, независимо от того, происходит переход или нет, и если команда перехода никак не влияет на результат их выполнения.
Для реализации этой идеи на этапе компиляции программы после каждой ко­манды перехода вставляется команда «Нет операции». Затем на стадии оптимиза­ции программы производятся попытки «перемешать» команды таким образом, чтобы по возможности большее количество команд «Нет операции»- заменить «по­лезными» командами программы. Разумеется, замещать команду «Нет операции» можно лишь на такую, которая не влияет на условие выполняемого перехода, ина­че полученная последовательность команд не будет функционально эквивалент­ной исходной. В оптимизированной программе удается заменить более 20% ко­манд «Нет операции» [120].
Предсказание переходов
Предсказание переходов на сегодняшний день рассматривается как один из наибо­лее эффективных способов борьбы с конфликтами по управлению. Идея заключа­ется в том, что еще до момента выполнения команды условного перехода или сразу же после ее поступления на конвейер делается предположение о наиболее вероят­ном исходе такой команды (переход произойдет или не произойдет). Последую­щие команды подаются на конвейер в соответствии с предсказанием. Для иллюст­рации вернемся к примеру (см. рис. 9.5), где команда 3 является командой УП. Пусть для команды 3 предсказано, что переход не произойдет. Тогда вслед за ко­мандой 3 на конвейер будут поданы команды 4-6 и т. д. Если предсказан переход, то после команды 3 на конвейер подаются команды 15-17,... При ошибочном пред­сказании конвейер необходимо вернуть к состоянию, с которого началась выборка «ненужных» команд (очистить начальные ступени конвейера), и приступить к заг­рузке, начиная с «правильной» точки, что по эффекту эквивалентно приостановке конвейера Цена ошибки может оказаться достаточно высокой, но при правиль­ных предсказаниях крупен и выигрыш — конвейер функционирует ритмично без остановок и задержек, причем выигрыш тем больше, чем выше точность предска­зания. Термин «точность предсказаниям »в дальнейшем будем трактовать как про­центное отношение числа правильных предсказаний к их общему количеству. В работе [70] дается следующая оценка: чтобы снижение производительности кон­вейера из-за его остановок по причине конфликтов по управлению не превысило 10%, точность предсказания переходов должна быть выше 97,7%.
42 6 Глава9. Основные направления в архитектуре процессоров
К настоящему моменту известно более двух десятков различных способов реа­лизации идеи предсказания переходов [165,230-232], отличающихся друг от дру­га исходной информацией, на основании которой делается прогноз, сложностью реализации и, главное, точностью предсказания. При классификации схем пред­сказания переходов обычно вьщеляют два подхода: статический и динамический, в зависимости от того, когда и на базе какой информации делается предсказание.
Эффективность большинства из приводимых в учебнике методов предсказа­ния переходов иллюстрируется результатами исследований, опубликованными в [68,95,107,197,207,228]. Все эксперименты проводились по примерно одинако­вой методике: численные показатели получены путем имитации методов предска­зания переходов при выполнении наборов стандартных тестовых программ. Глав­ное различие заключалось в выборе тестовых программ, что и нашло отражение в существенном расхождении полученных оценок.
Так, в работе Смита [197] использовались шесть тестовых программ, написан­ных на языке Фортран:
-  ADVAN: решение системы из трех дифференциальных уравнений в частных
производных;
-  GIBSON: искусственная программа компиляции набора команд, примерно удов-
летворяющего так называемой смеси Гибсона № 5;
-   SCI2: обращение матрицы;
-  SINCOS: преобразование массива координат из полярной системы отсчета
в прямоугольную;
-  SORTST: сортировка массива из 10 000 целых чисел;
-  TBLINK: работа со связанным списком.
В прочих исследованиях участвовали программы, входящие в различные вер­сии тестовых пакетов SPEC, в частности пакетов SPEC92, SPEC95 и CPU2000.
Последующий материал раздела посвящен рассмотрению различных механиз­мов предсказания переходов.
Статическое предсказание переходов
Статическое предсказание переходов осуществляется на основе некоторой апри­орной информации о подлежащей выполнению программе. Предсказание делает­ся на этапе компиляции программы и в процессе вычислений уже не меняется. Главное различие между известными механизмами статического прогнозирования заключается в виде информации, используемой для предсказания, и ее трактовке. Исходная информация может быть получена двумя путями: на основе анализа кода программы или в результате ее профилирования (термин «профилирование» по­ясняется ниже).
Известные стратегии статического предсказания для команд УП можно клас­сифицировать следующим образом:
-   переход происходит всегда (ПВ);
-  переход не происходит никогда (ПН);
-  предсказание определяется по результатам профилирования;
Конвейеризация вычислений 4 2 7
-  предсказание определяется кодом операции команды перехода;
-  предсказание зависит от направления перехода;
Я при первом выполнении команды переход имеет место всегда,
В первом иэ перечисленных вариантов предполагается, что каждая команда условного перекодавпрограммеобязателънозавершитсяпереходом, и, сучетом такого предсказания, дальнейшая выборка команд производится, начиная с адре­са перехода В основе второй стратегии лежит прямо противоположный подход: ниоднаизкомандусловногопереходавпрограмменикогданезавершаетсяперехо-дом, поэтому выборка команд продолжается в естественной последовательности.
Интуитивное представление, что обе стратегии должны приводить к верному предсказанию в среднем в 50% случаев, на практике не подтверждается. Так, по результатам тестирования (рис. 9.8), приведенным в [ 197], предсказание об обяза­тельном переходе оказалось правильным в среднем для 76% команд УП.
Рис. в. 8. Точность предсказания переходов при стратегии «переход происходит всегда-Аналогичный показатель, полученный на ином наборе тестовых программ [ 150], составил 68%. В работе [228] приводятся результаты проверки стратегии ПВ на тестах CPU2000 отдельно для программ с интенсивными целочисленными вычис­лениями и программ с преимущественной обработкой чисел в форме с плавающей запятой. Для первых средняя точность предсказаний составила 55,2%, а для вто­рых — 59,9%. В других источниках встречаются и иные численные оценки точнос­ти прогноза при стратегии ПВ, в частности 60% и 71,9%. В то же время в работе ■ [233] отмечается, что для ряда программ, связанных с целочисленной обработкой, процент правильных предсказаний может опускаться ниже 50%.
Цифры свидетельствуют, что успешность стратегии ПВ существенно зависит от характера программы и методов программирования, что, естественно, можно рассматривать как недостаток. Тем не менее стратегия все же используется в ряде ВМ, в частности MIPS-X, SuperSPARC, микропроцессорах i486 фирмы Intel. Свя­зано это, скорее всего, с простотой реализации и с тем, что для определенного класса программ стратегию можно считать достаточно эффективной.
Схожая ситуация характерна и для стратегии ПН, где предполагается, что ни одна из команд УП в программе никогда не завершается переходом. Несмотря на схожесть с ПВ, процент правильных исходов здесь обычно ниже, особенно в про­граммах с большим количеством циклов.
Стратегия ПН реализована в конвейерах микропроцессоров М68020 и МС88000, вычислительной машине \АХ 11/780. Сравнительная оценка стратегий ПВ и ПН, полученная при выполнении тестов CPU2000 для целочисленных и веществен­ных; вычислений [228], показана на рис. 9.9.
4 2 8 Глава 9. Основные направления в архитектуре процессоров
Из диаграммы видно, что ни одна из двух стратегий не обладает явным преиму­ществом над другой. Тем не менее анализ большого количества программ [154] показывает, что условные переходы имеют место более чем в 50% случаев, поэто­му если стоимость реализации двух рассмотренных вариантов одинакова, то пред­почтение следует отдать стратегии ПВ.
В третьем из перечисленных способов статического предсказания назначение командам УП наиболее вероятного исхода производится по результатам профи-лированияподлежащихвыполнениюпрограмм.Полпрофилированиемиодразуме-вается выполнение программы при некотором эталонном наборе исходных данных, сопровождающееся сбором информации об исходах каждой команды условного перехода. Тем командам, которые чаще завершались переходом, назначается стра­тегия ПВ, а всем остальным — ПН. Выбор фиксируется в специальном бите кода операции. Некоторые компиляторы самостоятельно проводят профилирование программы и по его результатам устанавливают этот бит в формируемом объект­ном коде. При выполнении программы поведение конвейера команд определяется после выборки команды по состоянию упомянутого бита в коде операции. Основ­ной недостаток этого образа действий связан с тем, что изменение набора исход-ныхданных для профилирования может существенно менять поведение одних и тех же команд условного перехода.
Средняя вероятность правильного предсказания, полученная на программах тестового набора SPEC_92, составила75%. Стратегия используется в процессорах MIPS 4x00 и PowerPC 603.
Прм^пред,сказаниинаосновекодаоперациикомандыпереходаддяо}щихкамянд предполагается, что переход произойдет, для других — его не случится. Например, для команды перехода по переполнению логично предположить, что перехода не будет. На практике назначение разным видам команд УП наиболее вероятного исхода чаще производится по результатам профилирования программ. В исследо­ваниях Е. Смита [197] стратегия ПВ была назначена командам перехода по усло­виям: «меньше нуля», «равно», «больше или равно», а ПН — всем прочим коман­дам условного перехода. Результаты показаны на рис. 9.10.
Эффективность предсказания зависит от характера программы. Этим, в част­ности, объясняется различие в выводах, полученных на основе разных исследова­ний. Так, согласно [154] стратегия приводит к успеху в среднем более чем в 75% случаев, а исследования Е. Смита дают цифру 86,7%,
Достаточно логичным представляется предсказание исходя из направления пе­рехода. Если указанный в команде адрес перехода меньше содержимого счетчика
Конвейеризация вычислений 4 2 9
комавд, говорят о переходе «назад»-, и для такой команды назначается стратегия ПВ. Переход к адресу, превышающему адрес команды перехода, считается перехо­дом «вперед», и такой команде назначается стратегия ПН. В основе рассматривае­мого подхода лежит статистика по множеству программ, согласно которой боль­шинство команд УП в программах используются для организации циклов, причем, как правило, переходы происходят к началу цикла (переходы «назад»). Согласно [120], для команд, выполняющих переход -«назад», фактический переход имеет место в 85% случаев. Для переходов «вперед» эта цифра составляет 65%. Таким образом, для команд условного перехода «назад»- логично принять, что переход происходит всегда. Рассматриваемую стратегию иногда называют «Переход назад происходит всегда». Результаты ее оценки [197] приведены на рис. 9.11.
Здесь при тестировании на пакете SPEC_89 средняя точность предсказания со­ставила 65%. Среди ВМ, где описанная стратегия является основной, можно упомя­нуть MicroSPARC-2 и РА-7хОО. Чаще, однако, стратегия используется в качестве вто­ричного механизма в схемах динамического прогнозирования переходов.
В последней из рассматриваемых статических стратегий при первом выполне-шшлюбойкомандыусловногопереходаделаетсяпредсказание,чтопереходобязательно будет. Предсказания на последующее выполнение команды зависят от правильнос­ти начального предсказания. Стратегию можно считать статической только частич­но, поскольку она однозначно определяет исход команды лишь при первом ее выпол­нении. Точность прогноза в соответствии с данной стратегией выше, чем у всех предшествующих, что подтверждают результаты, приведенные на рис. 9.12 [197].
К сожалению, при больших объемах программ вариант практически нереа­лизуем из-за того, что нужно отслеживать слишком много команд условного перехода.
4 3 0 Глава 9. Основные направления в архитектуре процессоров
Динамическое предсказание переходов
В динамических стратегиях решение о наиболее вероятном исходе команды УП принимается в ходе вычислений, исходя из информации о предшествующих пере­ходах (истории переходов), собираемой в процессе выполнения программы. В це­лом, динамические стратегии по сравнению со статическими обеспечивают более высокую точность предсказания. Прежде чем приступить к рассмотрению конк­ретных динамических механизмов предсказания переходов, остановимся на неко­торых положениях, общих для всех динамических подходов.
Идея динамического предсказания переходов предполагает накопление инфор­мации об исходе предшествующих команд УП. История переходов фиксируется в форме таблицы, каждый элемент которой состоит из т битов. Нужный элемент таблицы указывается с помощью к-разрядной двоичной комбинации — шаблона (pattern). Этим объясняется общепринятое название таблицы предыстории пере­ходов— таблица истории для шаблонов (PHT, Pattern History Table).
При описании динамических схем предсказания переходов их часто расцени­вают как один из видов автоматов Мура, при этом содержимое элементов РНТ трактуется как информация, отображающая текущее состояние автомата. В рабо­те [230] рассмотрены различные варианты подобных автоматов, однако реально осмысленно говорить лишь о трех вариантах, которые условно обозначим Al, А2 иАЗ.
Автомат А1 имеет только два состояния, поэтому каждый элемент РНТ состоит из одного бита (т= 1), значение которого отражает исход последнего выполнения команды условного перехода. Диаграмма состояний автомата А1 приведена па рис. 9.13.
Конвейеризация вычислений 4 3 1
Если команда завершилась переходом, то в соответствующий элемент РНТ за­носится единица, иначе — ноль. Очередное предсказание совпадает с итогом пре­дыдущего выполнения команды. После обработки очередной команды содержи­мое элемента корректируется.
Два других автомата предполагают большее число состояний, поэтому в них используются РНТ с многоразрядными элементами. Чаще всего ограничиваются двумя разрядами (т =2) и, соответственно, автоматами с четырьмя состояниями.
В двухразрядном автомате А2 элементы РНТ отражают исходы двух последних выполненных команд условного перехода и заполняются по схеме регистра сдвига. После обработки очередной команды УП содержимое выделенного этой команде элемента РНТ сдвигается влево на один разряд, а в освободившуюся позицию за­носится единица (если переход был) или ноль (если перехода не было). Если в эле­менте РНТ присутствует хотя бы одна единица, то при очередном выполнении команды делается предсказание, что переход будет. При нулевом значении эле­мента РНТ считается, что перехода не будет. Диаграмма состояний для такого ав­томата показана на рис. 9.14.
Двухразрядная схема автомата А2 используется относительно редко. Большую известность получила трехразрядная модель. Она, в частности, реализована в про­цессоре HP РА 8000.
Элементы РНТ в автомате A3 можно рассматривать как реверсивные счетчики, работающие в режиме с насыщением. При поступлении на конвейер команды ус­ловного перехода происходит обращение к соответствующему счетчику РНТ, и в зависимости от текущего состояния счетчика делается прогноз, определяющий дальнейший порядок извлечения команд программы. После прохождения ступе­ни исполнения, когда фактический исход команды становится ясным, содержи­мое счетчика увеличивается на единицу (если команда завершилась переходом) или уменьшается на единицу (если перехода не было). Счетчики работают в режи­ме насыщения. Это означает, что добавление единиц сверх максимального числа в счетчике, а также вычитание единиц при нулевом содержимом счетчика уже не
4 3 2 Глава 9. Основные направления в архитектуре процессоров
производятся. Основанием для предсказания служит состояние старшего разряда счетчика. Если он содержит единицу, то принимается, что переход произойдет, в противном случае предполагается, что перехода не будет.
Интуитивное представление о том, что с увеличением глубины предыстории (увеличением т) точность предсказания должна возрастать, на практике не под­тверждается. На рис. 9.15 показаны результаты одного из многочисленных иссле­дований, свидетельствующие, что при т > 3 точность предсказания начинает сни­жаться.
Рис. 9.15. Зависимость точности предсказания от разрядности элементов РНТ
График показывает также, что различие в точности предсказания при т = 3 и т - 2 незначительно, что удостоверяют также результаты, приведенные в [197] (рис. 9.16).
Как следствие, в большинстве известных процессоров используются двухраз­рядные счетчики (ш= 2). Логика предсказания переходов применительно к двух­разрядным счетчикам известна как алгоритм Смита [193]. Алгоритм предполага­ет четыре состояния счетчика:
-   00 — перехода не будет (сильное предсказание);
-   01 — перехода не будет (слабое предсказание);
-   10 — переход будет (слабое предсказание);
-   11 — переход будет (сильное предсказание).
Конвейеризация вычислений 4 3 3
Логику предсказания можно описать диаграммой состояний двухразрядного автомата A3 (рис. 9.17).
Поскольку вариант РНТ со счетчиками получил наиболее широкое распрост­ранение, в дальнейшем будем ссылаться именно на него.
После определения способов учета истории переходов и логики предсказания необходимо остановиться на особенностях использования таблицы, в частности на том, какая информация выступает в качестве шаблона для доступа к РНТ и ка­кого рода история фиксируется в элементах таблицы. Именно различия в спосо­бах использования РНТ определяют ту или иную стратегию предсказания.
В качестве шаблонов для доступа к РНТ могут быть взяты:
-   адрес команды условного перехода;
-   регистр глобальной истории;
-  регистр локальной истории;
-   комбинация предшествующих вариантов.
Схема, где для доступа к РНТ выбран адрес команды условного перехода (со­держимое счетчика команд), позволяет учитывать поведение каждой конкретной команды УП. При многократном выполнении большинства команд условного пе­рехода наблюдается повторяемость исхода: переход либо, как правило, происхо­дит, либо, как правило, не происходит (имеет место бимодальное распределение исходов). Индексация РНТ с помощью адреса команды УП дает возможность от­делить первые от вторых и, соответственно, повысить точность предсказания. Каж­дой команде условного перехода в РНТ соответствует свой счетчик. Когда коман­да завершается переходом, содержимое счетчика увеличивается на единицу, а в противном случае — уменьшается на единицу (естественно, с соблюдением логи­ки счета с насыщением). В качестве шаблонадля поиска в РНТ служат младшие к разрядов содержимого счетчика команд (рис. 9.18).
При к-разрядном индексе таблица может содержать 2к элементов.
Схема обеспечивает достаточно высокий процент правильных предсказаний для тех команд У П, которые в ходе вьгаислений выполняются многократно, например
4 3 4 Глава 9, Основные направления в архитектуре процессоров
предназначены для управления циклом. В то же время в любой программе имеет­ся достаточно много команд перехода, выполняемых лишь однократно или малое число раз. Как показали исследования, исход для таких команд в значительной мере зависит от поведения предшествующих им команд УП, связь которых с рас­сматриваемой командой не столь очевидна. Иными словами, между исходами ко­манд условного перехода в программе существует известная взаимосвязь, учет которой, дает возможность повысить долю правильных предсказаний. Эта идея реализуется схемой с регистром глобальной истории.
Регистр глобальной истории (GHR, Global History Register) представляет со­бой 1-разрядный сдвиговый регистр (рис. 9.19). После выполнения очередной ко­манды условного перехода содержимое регистра сдвигается на один разряд, а в освободившуюся позицию заносится единица (если исходом команды был пере­ход) или ноль (если перехода не было). Следовательно, кодовая комбинация в GHR отражает историю выполнения последних 1 команд условного перехода. Под ин­дексирование массива предикторов (элементов механизма предсказания) выделя­ются £ младших разряда GHR (чаще всего 1 - к). Каждой к-разрядной комбинации исходов последовательно выполнявшихся команд УП в массиве дескрипторов со­ответствует свой счетчик. Таким образом, счетчик РНТ определяется тем, какая комбинация исходов имела место в к предшествовавших командах перехода. Со­держимое счетчика используется для предсказания исхода текущей команды пе­рехода и впоследствии модифицируется по результату фактического выполнения команды.
.Регистрлокальной ucmopuu(LHR, Local History Register) по логике работы ана­логичен регистру глобальной истории, но предназначен для фиксации последова­тельных исходов одной и той же команды УП. В схемах предсказания с LHR при­сутствует так называемая таблица локальной истории, представляющая собой массив регистров локальной истории (рис. 9.20).
Конвейеризация вычислений 4 3 5
Рис. 9.20. Индексирование РНТ с помощью регистров локальной истории
Как и в схеме с адресом команды перехода, каждый счетчик в РНТ фиксирует историю исхода только одной команды УП, но базируясь на более детальных зна­ниях, отражающих к тому же и последовательность исходов.
Ранее уже отмечалось, что действие команды условного перехода зависит не только от результатов предшествующих выполнений данной команды, но и от ис­хода других команд перехода. Учет обоих факторов позволяет повысить точность предсказаний. С этой целью в ряде динамических методов предсказания шаблон для доступа к РНТ формируется путем объединения адреса команды перехода и со­держимого GHR (либо LHR), при этом используется одна из двух операций: кон­катенация (сцепление) и сложение по модулю 2 («исключающее ИЛИ»),
При конкатенации к-разрядный шаблон для обращения к РНТ образуется по­средством взятия q младших битов из одного источника, к которым пристыковы­ваются k-q младших разрядов, взятых из второго источника (рис, 9.21).
Регистр глобальной
Счетчик команд
{повальной) истории
РНТ
■
•
г '
кбит
!
;
Биты для предсказан!
Рис. 9.21'. Формирование шаблона для доступа к РНТ путем конкатенации
Эффективность предсказания на основе подобного шаблоназависит от соотно­шения количества разрядов (q и k-q), выбранных от каждого из двух источников. Здесь многое определяется и характером программы. В качестве иллюстрации на рис. 9.22 приведена зависимость точности предсказания от соотношения числа битов, взятых от счетчика команд (СК) и регистра глобальной истории (GHR). Данные получены на тестовой программе xlisp (интерпретатор языка LISP) при объеме РНТ, равном 1024 входам.
43 6 Глава 9. Основные направления в архитектуре процессоров
|к%
|те%
* 4+6 U3+7
75%                         80%
Точность предсказания Рис. 9.22. Зависимостьточности предсказания от соотношения разрядов в шаблоне
при конкатенации [ 197]
Вариант со сложением по модулю 2 предполагает побитовое применение опе­рации «Исключающее ИЛИ» к обоим источникам (рис. 9,23). В качестве шаблона используются к младших разрядов результата. Сформированный шаблон содер­жит больше полезной информации для предсказания, чем каждый из источников по отдельности.
Регистр глобальной (локальной) истории
шштшшш
биты для предсказания
Счетчик юманд Рис. 9.23. Формирование шаблона для доступа к РНТ путем сложения по модулю 2
Для сравнительной оценки рассмотренных вариантов доступа к РНТ обратим­ся к результатам экспериментов, приведенным в [64]. Исследовались четыре тес­товых программы:
-   compress— сжатиефайлов(ЮмлнУП);
-  eqntott — преобразование логических функций, заданных таблицей истиннос-
ти(178млнУП);
-  espresso — минимизация логических функций (73 млн УП);
-  xlisp — интерпретатор LISP (772 млн УП).
Результаты, усредненные по всем четырем программам для различных по объему таблиц РНТ, показаны на рис. 9.24.
Первый вывод, вытекающий из представленных данных, очевиден — с увели­чением размера РНТ точность предсказания возрастает. Среди четырех рассмот­ренных схем наилучшую точность обеспечивает схема со сложением по модулю два. Схема со счетчиком команд относится к наименее эффективным. Объясняет­ся это тем, что каждый отдельный счетчик РНТ в схеме со счетчикок команд за-действуется значительно реже, а некоторые счетчики вообще остаются без внима-
Конвейеризация вычислений 4 3 7
s*,j% Щ ск
*5.i% OGHR ■ mod 2 Ш Конкатенации
80%
8$%                         90%
Точность предсказания
95%
Рис. 9.24. Зависимость точности предсказания от способа доступа к РНТ и размера таблицы
ния. Результаты для схемы с конкатенацией получены для случая, когда в шабло­не используется одинаковое число разрядов из СК и GHR. При малых объемах РНТ вариант с конкатенацией дает наихудшие результаты, но при больших РНТ эта схема превосходит модель со счетчиком команд.
В реальных схемах предсказания переходов размер таблицы РНТ ограничен. Типичное количество элементов РНТ (элементарных счетчиков) в разных про­цессорах варьируется от 256 до 4096. Для выбора определенного входа в РНТ (нуж­ного счетчика) применяется 6-разрядный шаблон, где к определяется размером массива. Для упомянутых выше размеров РНТ значение Улежит в диапазоне от 8 до 12. Если обращение к РНТ определяется счетчиком команд, разрядность кото­рого обычно больше, чем к, в качестве шаблона выступают к младших битов СК. Как следствие, две команды условного перехода, адреса которых в младших к раз­рядах совпадают, будут обращаться к одному и тому же элементу РНТ, и история выполнения одной команды будет накладываться на историю выполнения дру­гой, что, естественно, будет влиять на точность предсказания. Ситуация известна кжэффект наложения (aliasing). ТажепроблемасуществуетипридоступекРНТна основании содержимого регистра глобальной истории или регистралокальной исто­рии. В зависимости от типа программы и других факторов наложение может при­водить к повышению точности предсказания, ее ухудшению либо вообще не сказы­ваться на точности предсказания. Соответственно, эффекты наложения класси­фицируют какконструктивный, деструктивныйжнейтральный.
Рассмотрим, насколько часто предсказания производятся на основании тех счетчиков РНТ, при обращении к которым имел место эффект наложения (рис. 9.25) [64].
■ СК
□ OHR Ш mod 2
Щ- Конкатенация
0%
. 10%                  20%                  30%                  40%                  50%
Процент предсказаний по счетчикам, где было наложение
Рис. 9.25. Интенсивность наложения при различныхспособахдоступакРНТ
4 3 8 Глава 9. Основные направления в архитектуре процессоров
В больших РНТ частота перекрытия снижается по причине большего числа счетчиков. Схема со счетчиком команд в наименьшей степени подвержена эффек­ту наложения. С другой стороны, в схемах, где шаблон для доступа к РНТ форми­руется на основе содержимого регистра глобальной истории, причем использует­ся операция конкатенации, эффект наложения сказывается в значительной мере и обычно отрицательно влияет на точность предсказания переходов.
При классификации динамических стратегий обычно выделяют следующие их виды:
-   одноуровневые или бимодальные;
-   двухуровневые или коррелированные;
-    гибридные;
-    асимметричные.
Одноуровневые схемы предсказания переходов. В многочисленныхисследо-ваниях, проводившихся на самых разнообразных программах, была отмечена ин­тересная закономерность. В поведении многих команд условного перехода явно прослеживается тенденция повторяемости исхода: одни команды программы, как правило, завершаются переходом, в то время как другие — остаются без оного, то есть имеет место бимодальное распределение исходов. Идея одноуровневых схем предсказания, известных также под вторым названием — бимодальные схемы [165], сводится к отделению команд, имеющих склонность завершаться переходом, от команд, при выполнении которых переход обычно не происходит. Такая диффе­ренциация позволяет для каждой команды выбрать наиболее подходящее пред­сказание. Для реализации идеи в составе схемы предсказания достаточно иметь лишь одну таблицу, каждый элемент которой отображает историю исходов одной команды УП. Для обращения к элементу, ассоциированному с определенной ко­мандой УП, используется адрес этой команды (или его младшие биты). Таким об­разом, одноуровневые схемы предсказания переходов можно определить как схе­мы, содержащие один уровень таблиц истории переходов (обычно единственную таблицу), адресуемых с помощью адреса команды условного перехода.
В первом из возможных вариантов одноуровневых схем строится сравнитель­но небольшая таблица, куда заносятся адреса п последних команд У П, при выпол­нении которых переход не случился. В сущности, это ранее упоминавшийся буфер адресов перехода (ВТВ), но с противоположным правилом занесения информа­ции (фиксируются адреса команд, завершившихся без перехода). Таблица обычно реализуется на базе ассоциативной кэш-памяти. При поступлении на конвейер очередной команды УП ее адрес сравнивается с адресами, хранящимися в таблице. При совпадении делается предположение о том, что перехода не будет, в против­ном случае предсказывается переход. С этих позиций для каждой ноёой команды УП по умолчанию принимается, что переход произойдет. После того как факти­ческий исход становится очевидным, содержимое таблицы корректируется. Если команда завершилась переходом, соответствующая запись из таблицы удаляется. Если же перехода не было, то адрес команды заносится в таблицу при условии, что до этого он там отсутствовал. При заполнении таблицы опираются на алгоритмы LRU или FIFO. По точности предсказания стратегия превосходит большинство стратегий статического предсказания.
Конвейеризация вычислений 43 9
Вторая схема ориентирована на то, что команды программы извлекаются из кэш-памяти команд. Каждая ячейка кэш-памяти содержит дополнительный раз­ряд, который используется только применительно к командам условного перехода. Состояние разряда отражает исход предыдущего выполнения команды (1 — пере­ход был, 0 — перехода не было). Новое предсказание совпадает с результатом пред­шествующего выполнения данной команды. При занесении такой команды в кэш-память рассматриваемый разряд устанавливается в единицу. Это напоми­нает стратегию «при первом выполнении переход обязательно происходит» с той лишь разницей, что первое предсказание, хотя и носит статический характер, про­исходит в ходе заполнения кэш-памяти, то есть динамически. После выполнения команды состояние дополнительного бита корректируется: если переход имел ме­сто, в него заносится единица, а в противном случае — ноль. Эффективность стра­тегии характеризуют данные, полученные в [ 197] (рис. 9.26).
advan щшт^^ш^т
GIBSON
SC12
98.9% 97,9% 96,0%
SINCOS
. SORTST
TBLINK
щттвшштштшжш 76,2% рмшшт^ф^шдзддз^м 81,7%
40% 50% 60% 70% 80% 90% 100%
Точность предсказания Рис. 9.26, Точность предсказания схемы с дополнительным битом в кэш-памяти команд
Главный ее недостаток заключается в дополнительных затратах времени на обновление состояния контрольного разряда в кэш-памяти команд.
В третьей схеме (рис. 9.27) РНТ состоит из одноразрядных элементов и носит название таблицы истории переходов (ВНТ, Branch History Table).
Счетчик команд                  ВНТ
кбит
__. Бит для
—Г"*" предсказания
Рис. 9.27. Однобитовая бимодальнаясхемапредсказания
Состояние элемента ВНТ определяет, произошел ли переход в ходе последнего выполнения команды условного перехода (1) или нет (0). Каждой команде УП в ВНТ соответствует свой элемент, для обращения к которому используются к младших разрядов адреса команды. Предсказание совпадает с исходом предыду­щего выполнения команды. Если команда условного перехода участвует в органи­зации цикла, то стратегия всегда приводит к неправильному предсказанию пере­хода в первой и последней итерациях цикла.
Схема была реализована в процессорах Alpha 21064 и AMD К5. Согласно результатам большинства исследовании, средняя точность успешного прогно­за с помощью однобитовой бимодальной схемы не превышает 78%. В то же время в работе [197] получено значение 90,4%.
44 0 Глава 9. Основные направления в архитектуре процессоров
Точность предсказания перехода существенно повышается с увеличением раз­рядности элементов ВНТ. В четвертой из рассматриваемых одноуровневых схем каждый элемент ВНТ состоит из двух битов, выполняющих функцию двухразряд­ного счетчика, работающего в режиме с насыщением. Иными словами, реализует­ся алгоритм Смита. Каждый-счетчик отображает историю выполнения одной ко­манды УП, то есть адресуется младшими разрядами счетчика команд (рис. 9.28).
Для обозначения таблицы истории переходов в данной схеме используют абб­ревиатуру DHT (Decode History Table). Слово «decoder»декодирование) в назва­нии отражает особенность работы с таблицей. Если к обычной ВНТ обращение происходит при выборке любой команды, вне зависимости от того, на самом ли деле она команда условного перехода, поискв БНТначинается только после деко­дирования команды, то есть когда выяснилось, что данная команда является ко­мандой условного перехода. Реализуется DHT на базе обычного ЗУ с произволь­ным доступом.
Последняя из обсуждаемых одноуровневых схем предсказания известна как схемаСмитамлибимодальныйпредиктор. Отличиеотпред^^щущетовариантавы-ражается лишь в способе реализации ВНТ (в схеме Смита сохранено именно это название таблицы). Таблица истории переходов организуется на базе кэш-памяти с ассоциативным отображением (рис. 9.29).
В качестве ассоциативного признака (тега) при поиске нужного счетчика вы­ступает адрес команды условного перехода. Такой подход позволяет ускорить по-
Конвейеризация вычислений 4 41
иск нужного счетчика и устраняет эффект наложения, но связан со значительны­ми аппаратными затратами.
Результаты моделирования бимодальной схемы с двухразрядными счетчика­ми показаны нарис. 9.30. По этим данным среднюю точность предсказания можно оценить как 92,6%.
В экспериментах, где данная идея проверялась на программах тестового пакета SPEC_95, средняя точность предсказания по всем программам пакета составила 53,9%. Несмотря на это, бимодальная схема с двухразрядными счетчиками довольно распространена На ее основе построены схемы предсказания переходов в процес­сорах Alpha 21164, R10000, PowerPC 620, UltraSPARC и др.
В заключение отметим, что во многих одноуровневых решениях таблица исто­рии переходов (DHT или ВНТ) совмещена с буфером адреса перехода (ВТВ), что позволяет сэкономить на вычислении исполнительных адресов точек перехода.
Двухуровневые схемы предсказания переходов. Одноуровневые схемы пред­сказания ориентированы нате команды УП, очередной исход которых существен­но зависит от их собственных предыдущих исходов. В то же время для многих команд программы наблюдается сильная зависимость не от собственных исходов, а от результатов выполнения других предшествующих им команд УП. Это обсто­ятельство призваны учесть двухуровневые адаптивные схемы предсказания переходов, впервые предложенные в [229]. Такие схемы часто называют коррели-условного перехода.
В коррелированных схемах предсказания переходов выделяются два уровня таблиц. В роли таблицы первого уровня может выступать регистр глобальной ис­тории (GHR), и тогда двухуровневую схему предсказания называют глобальной. В качестве таблицы первого уровня может также быть взят массив регистров ло­кальной истории (LHR), где отдельный регистр отражает последовательность по­следних исходов одной команды УП. Такая схема предсказания носит название локальной. Каждый элемент таблицы второго уровня служит для хранения исто­рии переходов отдельной команды УП. Таблица второго уровня обычно состоит из двухразрядных счетчиков и организована в виде матрицы (рис. 9.31). Содержи­мое счетчика команд (адрес команды УП) определяет один из регистров в таблице первого и одну строку в таблице второго уровня. В свою очередь, кодовая комби­нация (шаблон), хранящаяся в выбранном регистре таблицы первого уровня, оп­ределяет нужный счетчик в указанном ряду таблицы второго уровня. Выбранный счетчик используется для формирования предсказания. После выполнения коман­ды содержимое регистра и счетчика обновляется.
4 42 Глава 9. Основные направления в архитектуре процессоров
Из описания логики двухуровневого предсказания следует, что выбор нужного счетчика обусловливается двумя источниками — адресом команды, для которой делается предсказание, и шаблоном, отражающим историю предшествующих пе­реходов. Того же эффекта можно добиться при помощи схемы двухразрядного бимодального предиктора, если для доступа к ВНТ использовать шаблон, сфор­мированный путем сложения по модулю 2, как это показано на рис. 9.23. Такая схема известна под названием^ж/гаге.
Гибридные схемы предсказания переходов. Для всех ранее рассмотренных стратегий характерна сильная зависимость точности предсказания от особеннос­тей программ, в рамках которых эти стратегии реализуются. Та же самая схема, прекрасно проявляя себя с одними программными продуктами, с другими может давать совершенно неудовлетворительные результаты. Кроме того, необходимо учитывать еще один фактор. Прежде уже отмечалось, что точность предсказания повышается с увеличением глубины предыстории переходов, но происходит это лишь после накопления соответствующей информации, на что требуется опреде­ленное время: Период накопления предыстории принято называть временем «ра­зогрева». Пока идет «разогрев», точность предсказания весьма низка. Иными сло­вами, ни одна из элементарных стратегий предсказания переходов не является универсальной — со всех сторон лучшей в любых ситуациях. Гибридные или со­ревновательные схемы объединяют в себе несколько различных механизмов пред­сказания — элементарных предикторов. Идея состоит в том, чтобы в каждой конк­ретной ситуации задействовать тот элементарный предиктор, от которого в данном случае можно ожидать наибольшей точности предсказания.
Гибридная схема предсказания переходов, предложенная Макфарлингом [ 165], содержит два элементарных предиктора, отличающихся по своим характеристи­кам (размером таблиц предыстории и временем «разогрева») и работающих неза­висимо друг от друга. Выбор предиктора, наиболее подходящего в данной ситуа­ции, обеспечивается селектором, представляющим собой таблицу двухразрядных счетчиков, которые часто называют счетчиками выбора предиктора (рис. 9.32),
Адресация конкретного счетчика в таблице (индексирование) осуществляется к младшими разрядами адреса команды условного перехода, для которой осуще­ствляется предсказание. Обновление таблиц истории в каждом из предикторов производится обычным образом, как это происходит при их автономном исполь-
Конвейеризация вычислений 4 4 3
зовании. В свою очередь, изменение состояния счетчиков селектора выполняется по следующим правилам. Если оба предиктора одновременно дали одинаковое предсказание (верное или неверное), содержимое счетчика не изменяется. При правильном предсказании от первого предиктора и неверном от второго содержи­мое счетчика увеличивается, а в противоположном случае — уменьшается на еди­ницу. Выбор предиктора, на основании которого делается результирующая оцен­ка, реализуется с помощью мультиплексора, управляемого старшим разрядом соответствующего счетчика селектора.
В работе [95] идея гибридного механизма была обобщена на случай п предик­торов. Общая структура такой схемы предсказания переходов показана нарис. 9.33. При выполнении команды УП предсказания формируются одновременно всеми предикторами, однако реальные действия осуществляются на основании только одного из них.
Выбор подходящего предиктора обеспечивает механизм селекции (рис. 9.34). В схеме имеется буфер предыстории переходов (ВТВ), в котором каждая запись дополнена п двухразрядными счетчиками выбора предиктора, по числу исполь­зуемых элементарных предикторов. Счетчики позволяют отследить самый предпоч­тительный элементарный предиктор для каждой командыУП, представленной в ВТВ.
4 44 Глава 9. Основные направления в архитектуре процессоров
При записи в ВТВ нового элемента во все ассоциированные с ним счетчики заносится число 3. Для каждой команды условного перехода предсказание генери­руется всеми п предикторами, но во внимание принимаются только те из них, для которых соответствующий счетчик выбора предиктора содержит число 3. Если это число встретилось более чем в одном счетчике, выбор единственного предиктора, на основании которого и делается окончательное предсказание, обеспечивает шиф­ратор приоритета. После выполнения команды условного перехода содержимое соответствующих ей счетчиков выбора обновляется, при этом действует следую­щий алгоритм. Если среди предикторов, счетчики которых равнялись 3, хотя бы один дал верное предсказание, то содержимое всех счетчиков, связанных с невер­но сработавшими предикторами, уменьшается на единицу. В противном случае содержимое всех счетчиков, связанных с предикторами, проноз которых подтвер­дился, увеличивается на единицу. Такая политика гарантирует, что по крайней мере в одном из счетчиков будет число 3. Еще одно преимущество рассматривае­мой схемы выбора состоит в том, что она позволяет, например, отличить предик-тор-<юракул», давший правильное предсказание последние пять раз, от предикто­ра, верно определившего исход последние четыре раза. Стандартные счетчики с насыщением такую дифференциацию не обеспечивают.
По имеющимся оценкам, точность предсказания переходов с помощью гибрид­ных стратегий в среднем составляет 97,13%, что существенно выше по сравнению с прочими вариантами.
Асимметричная схема предсказания переходов. Асимметричная схема соче­тает в себе черты гибридных и коррелированных схем предсказания. От гибрид­ных схем она переняла одновременное срабатывание нескольких различных эле­ментарных предикторов, В асимметричной схеме таких предикторов три, и каждый из них использует собственную таблицу РНТ. Для доступа к таблицам, аналогич­но коррелированным схемам, используется как адрес команды условного перехо­да, так и содержимое регистра глобальной истории (рис. 9.35).
Шаблон для обращения к каждой из трех РНТ формируется по-разному (при­менены различные функции хэширования). При выполнении команды условного перехода каждый из трех предикторов выдвигает свое предположение, но оконча­тельное решение принимается по мажоритарной схеме. После завершения коман­ды условного перехода содержимое всех трех таблиц обновляется.
Конвейеризация вычислений 445
Правильный подбор алгоритмов хэширования позволяет практически исклю­чить влияние на точность предсказания эффекта наложения. Средняя точность предсказания с помощью асимметричной схемы, полученная на тестовом пакете SPEC_95, составила 72,6%.
Суперконвейерные процессоры
Эффективность конвейера находится в прямой зависимости от того, с какой час­тотой на его вход подаются объекты обработки. Добиться η-кратного увеличения темпа работы конвейера можно двумя путями:
-  разбиением каждой ступени конвейера на п «подступеней» при одновремен-
ном повышении тактовой частоты внутри конвейера также в п раз;
-  включением в состав процессора п конвейеров, работающих с перекрытием.
В данном разделе рассматривается первый из этих подходов, известный как с&перконвейеризация (термин впервые был применен в 1988 году). Иллюстрацией эффекта суперконвейеризации может служить диаграмма, приведенная на рис. 9.36, где рассмотрен ранее обсуждавшийся пример (см. рис. 9.3). Каждая из шести сту­пеней стандартного конвейера разбита на две более простые подступени, обозна­ченные индексами 1 и 2. Выполнение операции в подступенях занимает половину тактового периода. Тактирование операций внутри конвейера производится с час­тотой, вдвое превышающей частоту «внешнего» тактирования конвейера, благо­дарящему на каждой ступени конвейера можно в пределах одного «внешнего» так­тового периода выполнить две команды. '
В сущности, суперконвейеризация сводится к увеличению количества сту­пеней конвейера как за счет добавления новых ступеней, так и путем дробле­ния имеющихся ступеней на несколько простых подступеней. Главное требо­вание — возможность реализации операции в каждой подступени наиболее простыми техническими средствами, а значит, с минимальными затратами вре­мени. Вторым, не менее важным, условием является одинаковость задержки во всех подступенях.
Критерием для причисления процессора к суперконвейерным служит число ступеней в конвейере команд. К суперконвейерным относят процессоры, где та­ких ступеней больше шести. Первым серийным суперконвейерным процессором считается MIPS R4000, конвейер команд которого включает в себя восемь ступе-
44 6 Глава9. Основные направления в архитектуре процессоров ·
ней. Супер конвейеризация здесь стала следствием разбиения этапов выборки ко­манды и выборки операнда, а также введения в конвейер дополнительного этапа проверки тега, появление которой обусловлено архитектурой системы команд ма­шины.
Таблица 9,1 · Длина конвейера команд в популярных микропроцессорах
1ип микропроцессор·
Количеств ступеней в коимйере команд
MIPS R4400
8
UltraSPARC!
9
Pentium III
10
Itanium
10
UltraSPARC III
и
Pentium 4
20
К сожалению, выигрыш, достигаемый за счет суперконвейеризации, на прак­тике может оказаться лишь умозрительным. Удлинение конвейера ведет не толь­ко к усугублению проблем, характерных для любого конвейера, но и возникнове­нию дополнительных сложностей. В длинном конвейере возрастает вероятность конфликтов. Дороже встает ошибка предсказания перехода — приходится очищать большее число ступеней конвейера, на что требуется больше времени. Усложняет­ся логика взаимодействия ступеней конвейера. Тем не менее создателям ВМ уда­ется успешно справляться с большинством из перечисленных проблем, свидетель­ством чего служит неуклонное возрастание числа ступеней в конвейерах команд современных процессоров (табл. 9.1).
Hosted by uCoz