Принципы конвейеризации

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

a) во времени или конвейеризацией, при которой происходит совмещение разных вычислительных операций над одними и теми же данными;

b) в пространстве или собственно параллелизмом — совмещением во времени однотипных операций, выполняемых над разными блоками данных.

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

Представим программу как некоторую функцию y=F(x). Ее декомпозиция может быть выражена так:

y=F(x)=fn(fn-1(…(f1(x)))).

Для каждой fk аргумент — результат вычислений fk-1. Программа может быть выполнена конвейерной схемой рис. 14. В ней аппаратные блоки (ступени) вычисляют значения функций fk. Фиксаторы служат для согласования времени работы ступеней.

Р и с. 14. Схема конвейера

f ₁... f_n – ступени, Ф₁… Ф _n – регистры-фиксаторы

Условия эффективной работы конвейера:

a) время выполнения каждой подфункции должно быть приблизительно одинаковым,

b) каждая подфункция реализуется своей ступенью,

c) отсутствие обратных связей передачи данных в конвейере.

Определим среднее время выполнения команды в таком конвейере. Пусть общее время выполнения одной исходной команды равно T ₀. Через n тактов конвейер будет заполнен, и в каждом следующем такте будет выдаваться результат с периодом T ₀ /n.

Пусть n — число ступеней конвейера; длительности выполнения микрокоманд в каждой ступени равны t_i, i = 1, 2, …., n; и K – число команд в последовательности. Число тактов для последовательности из K команд равно

где - время выполнения наиболее медленной ступени.

Среднее время выполнения K команд в конвейере

и при K имеем

Следовательно, скорость конвейера определяется самой длинной ступенью, где бы она ни располагалась. Если длительности всех ступеней одинаковы и равны одному такту, то в пределе (при бесконечном количестве команд в программе) конвейер будет выполнять одну команду за такт.

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

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

a) структурные,

b) по данным,

c) по управлению.

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

· недостаточность конвейерных функциональных устройств системы;

· недостаточное дублирование ресурсов системы;

· кэш-промахи, которые будут рассмотрены позднее;

· общий конвейер для команд и данных.

Конфликт по данным возникает при использовании одной командой результата выполнения другой. В этом случае приходится приостанавливать конвейер и ждать, пока не появится результат. Таким образом возникает «пузырь» (buble) в конвейере. Для исключения рассматриваемых конфликтов изменяют последовательность команд с помощью вставки между связанными логически независимой операции. Такой подход в литературе называют спекулятивным выполнением команд программы. Обычно после окончания программы исходный порядок команд восстанавливают в выходном буфере.

Конфликты по управлению связаны с изменением линейной последовательности команд, вызванным командами безусловного и условного перехода. При этом может оказаться, что часть команд в начале конвейера загружена в него напрасно, и конвейер необходимо очистить, что приводит к дополнительным задержкам. Для сокращения этих задержек используется буфер адресов переходов BTB (Branch Target Buffer), представленный на рис. 15. Он представляет собой ассоциативную кэш-память небольшого объема. В строках BTB хранятся исполнительные адреса точек переходов нескольких последних команд, для которых переход имел место.

Р и с. 15. Буфер BTB

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

Наибольший эффект использования BTB достигается при выполнении циклов - при многократном переходе в одну и туже точку.

При выполнении команд условного перехода IF(L) возникает дополнительная сложность. Требуется несколько тактов, чтобы вычислить логическое условие L и целевой адрес перехода при выполнении этого условия. Возникает вопрос: какую ветвь B1 или B2 программы (рис. 16) загружать в конвейер сразу после загрузки команды IF.

Если не угадать с выбором, то конвейер придется перезагружать.

Основные способы сокращения простоев конвейера:

· Использование буферов предвыборки;

· Задержка (задержанные переходы);

· Предсказание (прогноз) переходов.

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

Р и с. 16. Схема алгоритма
выполнения команды условного перехода

Наиболее эффективным является предсказание переходов. Различают статическое и динамическое предсказание.

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

Этот способ использует априорную информацию о программе. Предсказание делается либо на этапе компиляции, либо в процессоре при ее выполнении.

Существует 4 стратегии статического предсказания переходов.

1. Переход происходит всегда.

2. Переход не происходит никогда.

3. Предсказание определяется кодом операции команды перехода.

4. Предсказание определяется направлением перехода (вперед или назад по программе).

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

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

2. Типы архитектур центральных процессоров

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

Существует два основных типа архитектур центральных процессоров:

a) С очень длинным командным словом (VLIW) и

b) Суперскалярная.

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

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

В суперскалярных процессорах используются все рассмотренные ранее способы устранения конфликтов. Они реализуются динамически. С ростом числа конвейеров увеличивается сложность устройства управления (УУ) ими, а также задержки в УУ. Считается, что максимальное количество конвейеров равно 10, а число ступеней в них – 20. Фирма АМД утверждает, что оптимальным является 10 ступеней (при большем числе увеличиваются потери из-за неправильного предсказания переходов). Основным достоинством суперскалярных процессоров является независимость исполняемого кода программы от их структуры и возможность его выполнения на любой модели процессора. Это достоинство определило преимущественное распространение суперскалярных процессоров.

В последнее время много пишут о процессорах с явным параллелизмом команд (EPIC - Explicitly Parallel Instruction Computing), в которых сочетаются достоинства обеих архитектур. Эта идея реализована в процессорах семейства Itanium.

Рассмотрим структуры современных процессоров ведущих фирм.