Процессор Intel

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

Методы  ускорения выборки  команд при условном переходе

    Для ускорения процесса выборки команд применяются следующие методы:

1. вычисление исполнительного адреса перехода на этапе декодирования команды;
2. использование буфера адресов перехода;
3. использование кэш-памяти для хранения команд, расположенных в точке перехода;
4. использование буфера циклов.

  На этапе  декодирования команды выясняются ее принадлежность к команде перехода, а также способ адресации и адресный код точки перехода. Это позволяет сразу на втором этапе приступить к вычислению исполнительного адреса, не дожидаясь передачи команды на третью ступень, где обычно происходит вычисление адресов. Для этого в состав ступени декодирования вводят дополнительные сумматоры, с помощью которых и вычисляется исполнительный адрес точки перехода, т.е. адрес j-ой команды на правой ветке. Этот метод позволяет незначительно сократить потери времени всего на один такт.

   Более  существенно сократить потери времени на вычисление исполнительного адреса команды перехода можно за счет использования буфера адресов перехода ВТВ. ВТВ от слов Branch Target Buffer.

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

     Усовершенствованным  вариантом ВТВ является BTIC (Branch Target Instruction Cache). В BTIC помимо исполнительного адреса команды в точке перехода записывается также и код самой команды. Это позволяет при повторном исполнении этой команды выбирать команду не из памяти, а непосредственно из BTIC, что дает наилучший эффект для циклических программ.

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

Методы  решения проблемы условного перехода

  Рассмотренные методы ускорения выборки команд не позволяют в целом решить все проблемы условного перехода, из-за которых происходит снижение производительности процессора. Поэтому были предложены различные методы сокращения потерь времени при условных переходах, которые можно разделить на четыре группы:

1. буферы предвыборки;
2. множественные потоки;
3. задержанный переход;
4. предсказание перехода.

  Равномерность  поступления команд на вход  конвейера часто нарушается из-за  занятости памяти или при выборке  команд, состоящих из нескольких  слов. Чтобы добиться ритмичности  подачи команд на вход конвейера,  между первой ступенью выборки команд и остальной частью конвейера часто размещают буферную память, организованную по принципу очереди (FIFO – первый пришел, первый ушел), которая называется буфером предвыборки (БП). Буфер предвыборки – это фактически очередь команд, которые дожидаются своего времени поступления на конвейер. Использование буфера предвыборки не сказывается на производительности конвейера, а лишь приводит к увеличению времени прохождения команд через конвейер. Чтобы одновременно с обеспечением ритмичной работы конвейера решить и проблему условных переходов, в конвейер включают два таких буфера. На рисунке приведена модель конвейера с двумя буферами:

      Каждая извлеченная из памяти  и помещенная в основной буфер  команда анализируется блоком  перехода. При обнаружении команды  условного перехода блок перехода вычисляет исполнительный адрес точки перехода и одновременно с продолжением выборки команд в основной буфер организует выборку команд в дополнительный буфер, начиная с точки перехода. Далее блок перехода определяет исход команды условного перехода, в зависимости от которого подключает к конвейеру нужный буфер, при этом содержимое другого буфера сбрасывается. Таким образом, при любом исходе команды перехода задержек в работе конвейера не будет, поскольку происходит плавное переключение программы на нужную ветку. Это достоинство метода.

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

   Другим  решением проблемы переходов  служит дублирование начальных  ступеней конвейера и создание двух параллельных потоков команд (множественные потоки). На рисунке приведена модель конвейера с множественными потоками:

   В одной  из ветвей такого множественного  конвейера последовательность выборки и выполнения команд соответствует случаю, когда условие перехода не выполнилось, а во второй ветви – в случае выполнения этого условия. Оба потока сходятся в точке, где итог проверки условия перехода становится очевидным. Дальнейшее продвижение по конвейеру продолжает только тот поток, который соответствует условию перехода. Основной недостаток метода состоит в том, что на конвейер или в поток может поступить новая команда условного перехода, которая требует дополнительного потока. Примером ЭВМ, где используются два или более конвейерных потоков, служат IBM 370/168 и IBM 3033.

      Стратегия задержанного перехода предполагает продолжение выполнения команд, следующих за командой условного перехода, независимо от проверки условия. Естественно, что выполнению подлежат те команды, которые все равно должны быть когда-то выполнены независимо от того, происходит переход или нет. Кроме того, команда перехода не должна влиять на результат выполнения таких команд. Для реализации задержанного перехода на этапе компиляции программы после каждой команды перехода вставляется пустая команда “Нет операции”. На стадии оптимизации программы производится попытка заменить пустые команды полезными командами программы. Разумеется, замещать команду “Нет операции” можно лишь на такую, которая не влияет на условие выполняемого перехода, иначе замена не будет корректной. При оптимизации программы удается заменить более 20% пустых команд “Нет операции”. 
 
 

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

     Предсказание переходов в настоящее время рассматривается как один из более эффективных способов борьбы с конфликтами по управлению. Для устранения таких конфликтов еще до момента выполнения команды условного перехода или сразу же после ее поступления на конвейер делается предположение о наиболее вероятном исходе такой команды, т.е. делается предсказание о том, произойдет или не произойдет переход. Все последующие команды подаются на конвейер в соответствии со сделанным предсказанием. При ошибочном предсказании конвейер необходимо вернуть в состояние, с которого началась загрузка ненужных команд. Для этого необходимо очистить начальные ступени конвейера и приступить к загрузке, начиная с команды, которой передается управление. Подобная перезагрузка конвейера по эффекту эквивалентна приостановке конвейера, что ведет к снижению производительности процессора. Поэтому цена ошибки предсказания перехода может оказаться достаточно высокой, но при правильных предсказаниях крупен и выигрыш, поскольку конвейер в этом случае работает ритмично без остановок и задержек. При правильном предсказании выигрыш в производительности будет тем больше, чем выше точность предсказания. Точность предсказания обычно оценивают как процентное отношение числа правильных предсказаний к их общему количеству. Для того чтобы снижение производительности конвейера по причине конфликтов по управлению не превысило 10%, точность предсказания переходов должна быть выше 97,7%.

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

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

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

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

1. Переход происходит всегда (ПВ);
2. Переход никогда не происходит (ПН);
3. Предсказание определяется по результатам профилирования;
4. Предсказание определяется кодом операции команды перехода;
5. Предсказание зависит от направления перехода;
6. При первом выполнении команды переход имеет место всегда.

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

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

    Проведенные  исследования путем имитационного  моделирования с помощью тестовых программ показали, что точность предсказания первого способа ПВ лежит в диапазоне от 55% до 76%, а второго – менее 50%. Поэтому при прочих равных условий предпочтение следует отдать стратегии ПВ.

   Несмотря  на невысокую точность предсказаний  обе стратегии нашли применение в реальных микропроцессорах. Например, способ ПВ использовался в микропроцессорах i 486 фирмы Intel, а способ ПН был реализован в микропроцессорах М68020 и МС88000 ЭВМ VAX 11/780 фирмы DEC.

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

     Четвертый  способ предсказания на основе кода операции команды перехода предполагает, что для одних команд переход произойдет всегда, а для других команд – никогда. Поэтому все команды условного перехода делят на две группы, командам одной группы назначается стратегия ПВ, а другой – ПН. Распределение команд на группы можно проводить либо по результатам профилирования, либо по кодам команд. Например, стратегию ПВ можно назначить командам перехода по условиям: меньше нуля, равно, больше или равно, а всем остальным командам – стратегию ПН. Этот способ имеет примерно такую же точность предсказания, что и третий, т.е. примерно 75%.

    Пятый  способ предполагает, что предсказание зависит от направления перехода. Если указанный в команде адрес перехода меньше содержимого счетчика команд, то переход происходит назад, т.е. в сторону начала программы. Для таких команд назначается стратегия ПВ, поскольку по статистике именно такие команды используются для организации циклов. Согласно статистике переход назад выполняется в 85% случаев. Переход по адресу, превышающему адрес команды перехода, называется переходом вперед. Для таких команд назначается стратегия ПН. Этот способ еще называют: переход назад происходит всегда, а его точность примерно равна точности третьего и четвертого способов предсказания.

    Шестой  способ предсказания, когда при первом выполнении команды переход происходит всегда, статическим является только частично, поскольку предсказания на последующее выполнение команды зависят от правильности начального предсказания, т.е. стратегия однозначно определяет исход команды только при первом ее выполнении, а все последующие переходы определяются уже при выполнении программы. Точность прогноза данного способа несколько выше, чем у всех предшествующих, но этот способ трудно реализовать на практике для больших программ из-за того, что нужно отслеживать слишком много команд условного перехода.