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

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

1) буферы предвыборки;

2) множественные потоки;

3) задержанный переход;

4) предсказание перехода.

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

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

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

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

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

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