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

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

множественные потоки; Ш задержанный переход; Ш предсказание перехода.

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-07