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

 

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

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

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

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

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

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

Чтобы одновременно с обеспечением ритмичной работы конвейера решить и проблему условных переходов, в конвейер включают два таких буфера (рис. 52).

Рис. 52. Конвейер с буферами предвыборки команд.

 

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

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

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

 

Рис. 53. Конвейер с множественными потоками.

 

В одной из ветвей такого «раздвоенного» конвейера последовательность вы­борки и выполнения команд соответствует случаю, когда условие перехода не вы­полнилось, во второй ветви – случаю выполнения этого условия. Для ранее рас­смотренного примера (см. рис. 53) в одном из потоков может обрабатываться последовательность команд 4-6, а в другом – 15-17. Оба потока сходятся в точке, где итог проверки условия перехода становится очевидным. Дальнейшее продви­жение по конвейеру продолжает только «правильный» поток. Основной недоста­ток метода состоит в том, что на конвейер или в поток может поступить новая ко­манда УП до того, как будет принято окончательное решение по текущей команде перехода. Каждая такая команда требует дополнительного потока. Несмотря на это, стратегия позволяет улучшить производительность конвейера. При­мерами ВМ, где используются два или более конвейерных потоков, служат IBM 370/168 и IBM 3033.

Стратегия задержанного переходапредполагает продолжение выполнения ко­манд, следующих за командой УП, вне зависимости от ее исхода. Естественно, что это имеет смысл, лишь когда последующие команды являются «полезными», то есть такими, которые все равно должны быть когда-то выполнены, независимо от того, происходит переход или нет, и если команда перехода никак не влияет на результат их выполнения.

Для реализации этой идеи на этапе компиляции программы после каждой ко­манды перехода вставляется команда «Нет операции». Затем на стадии оптимиза­ции программы производятся попытки «перемешать» команды таким образом, чтобы по возможности большее количество команд «Нет операции» заменить «по­лезными» командами программы. Разумеется, замещать команду «Нет операции» можно лишь на такую, которая не влияет на условие выполняемого перехода, ина­че полученная последовательность команд не будет функционально эквивалент­ной исходной. В оптимизированной программе удается заменить более 20% ко­манд «Нет операции».

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

 

Предсказание переходов на сегодняшний день рассматривается как один из наибо­лее эффективных способов борьбы с конфликтами по управлению. Идея заключа­ется в том, что еще до момента выполнения команды условного перехода или сразу же после ее поступления на конвейер делается предположение о наиболее вероят­ном исходе такой команды (переход произойдет или не произойдет). Последую­щие команды подаются на конвейер в соответствии с предсказанием. Для иллюст­рации вернемся к примеру (см. рис. 51), где команда 3 является командой УП. Пусть для команды 3 предсказано, что переход не произойдет. Тогда вслед за ко­мандой 3 на конвейер будут поданы команды 4-6 и т. д. Если предсказан переход, то после команды 3 на конвейер подаются команды 15-17,... При ошибочном пред­сказании конвейер необходимо вернуть к состоянию, с которого началась выборка «ненужных» команд (очистить начальные ступени конвейера), и приступить к заг­рузке, начиная с «правильной» точки, что по эффекту эквивалентно приостановке конвейера. Цена ошибки может оказаться достаточно высокой, но при правиль­ных предсказаниях крупен и выигрыш — конвейер функционирует ритмично без остановок и задержек, причем выигрыш тем больше, чем выше точность предска­зания. Термин «точность предсказания»в дальнейшем будем трактовать как про­центное отношение числа правильных предсказаний к их общему количеству. Чтобы снижение производительности кон­вейера из-за его остановок по причине конфликтов по управлению не превысило 10%, точность предсказания переходов должна быть выше 97,7%.

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