Статическое предсказание переходов

 

Статическое предсказание переходов осуществляется на основе некоторой апри­орной информации о подлежащей выполнению программе. Предсказание делает­ся на этапе компиляции программы и в процессе вычислений уже не меняется. Главное различие между известными механизмами статического прогнозирования заключается в виде информации, используемой для предсказания, и ее трактовке. Исходная информация может быть получена двумя путями: на основе анализа кода программы или в результате ее профилирования (термин «профилирование» по­ясняется ниже).

Известные стратегии статического предсказания для команд УП можно клас­сифицировать следующим образом:

· переход происходит всегда (ПВ);

· переход не происходит никогда (ПН);

· предсказание определяется по результатам профилирования;

· предсказание определяется кодом операции команды перехода;

· предсказание зависит от направления перехода;

· при первом выполнении команды переход имеет место всегда.

В первом из перечисленных вариантов предполагается, что каждая команда условного перехода в программе обязательно завершится переходом, и, с учетом такого предсказания, дальнейшая выборка команд производится, начиная с адре­са перехода. В основе второй стратегии лежит прямо противоположный подход: ни одна из команд условного перехода в программе никогда не завершается перехо­дом,поэтому выборка команд продолжается в естественной последовательности.

Интуитивное представление, что обе стратегии должны приводить к верному предсказанию в среднем в 50% случаев, на практике не подтверждается. Так, по результатам тестирования, предсказание об обяза­тельном переходе оказалось правильным в среднем для 76% команд УП.

Аналогичный показатель, полученный на ином наборе тестовых программ, составил 68%.

Тесты свидетельствуют, что успешность стратегии ПВ существенно зависит от характера программы и методов программирования, что, естественно, можно рассматривать как недостаток. Тем не менее, стратегия все же используется в ряде ВМ, в частности MIPS-X, SuperSPARC, микропроцессорах i486 фирмы Intel. Свя­зано это, скорее всего, с простотой реализации и с тем, что для определенного класса программ стратегию можно считать достаточно эффективной.

Схожая ситуация характерна и для стратегии ПН, где предполагается, что ни одна из команд УП в программе никогда не завершается переходом. Несмотря на схожесть с ПВ, процент правильных исходов здесь обычно ниже, особенно в про­граммах с большим количеством циклов.

Стратегия ПН реализована в конвейерах микропроцессоров М68020 и МС88000, вычислительной машине VAX 11/780.

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

Средняя вероятность правильного предсказания, полученная на программах тестового набора SPEC_92, составила 75%. Стратегия используется в процессорах MIPS 4x00 и PowerPC 603.

При предсказании на основе кода операции команды переходадля одних команд предполагается, что переход произойдет, для других — его не случится. Например, для команды перехода по переполнению логично предположить, что перехода не будет. На практике назначение разным видам команд УП наиболее вероятного исхода чаще производится по результатам профилирования программ.

Достаточно логичным представляется предсказание исходя из направления пе­рехода.Если указанный в команде адрес перехода меньше содержимого счетчика команд, говорят о переходе «назад», и для такой команды назначается стратегия ПВ. Переход к адресу, превышающему адрес команды перехода, считается перехо­дом «вперед», и такой команде назначается стратегия ПН. В основе рассматривае­мого подхода лежит статистика по множеству программ, согласно которой боль­шинство команд УП в программах используются для организации циклов, причем, как правило, переходы происходят к началу цикла (переходы «назад»). Таким образом, для команд условного перехода «назад» логично принять, что переход происходит всегда. Рассматриваемую стратегию иногда называют «Переход назад происходит всегда».

Динамическое предсказание переходов

 

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

Идея динамического предсказания переходов предполагает накопление инфор­мации об исходе предшествующих команд УП. История переходов фиксируется в форме таблицы, каждый элемент которой состоит из mбитов. Нужный элемент таблицы указывается с помощью k-разрядной двоичной комбинации – шаблона (pattern). Этим объясняется общепринятое название таблицы предыстории пере­ходов – таблица истории для шаблонов(РНТ, Pattern History Table).

При описании динамических схем предсказания переходов их часто расцени­вают как один из видов автоматов Мура, при этом содержимое элементов РНТ трактуется как информация, отображающая текущее состояние автомата.

Суперконвейерные процессоры

 

Эффективность конвейера находится в прямой зависимости от того, с какой час­тотой на его вход подаются объекты обработки. Добиться n-кратного увеличения темпа работы конвейера можно двумя путями:

· разбиением каждой ступени конвейера на п «подступеней» при одновремен­ном повышении тактовой частоты внутри конвейера также в п раз;

· включением в состав процессора п конвейеров, работающих с перекрытием.

В данном разделе рассматривается первый из этих подходов, известный как суперконвейеризация(термин впервые был применен в 1988 году). Иллюстрацией эффекта суперконвейеризации может служить диаграмма, приведенная на рис. 54, где рассмотрен ранее обсуждавшийся пример (см. рис. 50). Каждая из шести сту­пеней стандартного конвейера разбита на две более простые подступени, обозна­ченные индексами 1 и 2. Выполнение операции в подступенях занимает половину тактового периода. Тактирование операций внутри конвейера производится с час­тотой, вдвое превышающей частоту «внешнего» тактирования конвейера, благо­даря чему на каждой ступени конвейера можно в пределах одного «внешнего» так­тового периода выполнить две команды.

В сущности, суперконвейеризация сводится к увеличению количества сту­пеней конвейера как за счет добавления новых ступеней, так и путем дробле­ния имеющихся ступеней на несколько простых подступеней. Главное требо­вание — возможность реализации операции в каждой подступени наиболее простыми техническими средствами, а значит, с минимальными затратами вре­мени. Вторым, не менее важным, условием является одинаковость задержки во всех подступенях.

Критерием для причисления процессора к суперконвейерным служит число ступеней в конвейере команд. К суперконвейерным относят процессоры, где та­ких ступеней больше шести. Первым серийным суперконвейерным процессором считается MIPS R4000, конвейер команд которого включает в себя восемь ступе ней. Суперконвейеризация здесь стала следствием разбиения этапов выборки ко­манды и выборки операнда, а также введения в конвейер дополнительного этапа проверки тега, появление которой обусловлено архитектурой системы команд ма­шины.

 

Рис. 54. Традиционная и суперконвейерная обработка команд.

 

К сожалению, выигрыш, достигаемый за счет суперконвейеризации, на прак­тике может оказаться лишь умозрительным. Удлинение конвейера ведет не толь­ко к усугублению проблем, характерных для любого конвейера, но и возникнове­нию дополнительных сложностей. В длинном конвейере возрастает вероятность конфликтов. Дороже встает ошибка предсказания перехода — приходится очищать большее число ступеней конвейера, на что требуется больше времени. Усложняет­ся логика взаимодействия ступеней конвейера. Тем не менее, создателям ВМ уда­ется успешно справляться с большинством из перечисленных проблем, свидетель­ством чего служит неуклонное возрастание числа ступеней в конвейерах команд современных процессоров.