4. Основы вычислительных конвейеров.

4.1. Введение в архитектурные принципы конвейерных процессоров и эвм.

Повышение скорости обработки информации - самая большая задача вычислительной техники в целом. Главные пути:

-поиск и совершенствование физических элементов, обеспечивающих высокую скорость переключения (в дискретной технике)

-поиск нетрадиционных (недискретных и пр.) методов и технических средств обработки информации (оптических, оптико-магнитных, нейроно-подобных и т.д.)

-совмещение операций на различных уровнях.

Этот последний общий метод включает два подхода: параллелизм и конвейеризация. У них много общего и иногда в конкретных реализациях их бывает трудно разделить. Но в чистом виде эти два термина обозначают два совершенно различных подхода.

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

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

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

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

Аналогия с физическим конвейером-трубопроводом (фильтрация, добавка компонентов, направление и т.д.)

Если некоторая функция при реализации «в лоб» может быть выполнена за Т наносекунд, но может быть разделена на N ступеней, то идеальный конвейер, предусматривающий повторяющиеся выполнения той же функции, может выполнить ее за Т/N наносекунд, т.е. в N раз повысить производительность.

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

4.1.1. Задачи и проблемы конвейеризации.

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

• вычисление базовой функции эквивалентно некоторой последовательности вычисления подфункций;

• величины, являющиеся входными для данной подфункции, являются выходными предшествующей подфункции в цепочке (последовательности) вычисления;

• никаких других связей кроме обмена данными между подфункциями нет;

• каждая подфункция может быть реализована аппаратными блоками;

• времена, необходимые для реализации аппаратными блоками своих действий, считаются равными.

Аппаратные блоки образуют ступени. Поток данных дискретен (аналогия с разливом жидкости в бутылке). Часто удобно полагать, что каждая ступень суть логическая схема без памяти, но на ее входе и выходе есть память – фиксатор. Дискретные данные перемещаются от ступени к ступени по синхросигналам.

Есть близкое к понятию конвейеризации понятие перекрытия.

При перекрытии снимаются некоторые жесткие требования:

• между отдельными вычислениями подфункций могут быть некоторые зависимости;

• каждому вычисления может потребоваться своя цепочка подфункций;

• по назначению подфункции достаточно различны;

• время, необходимое для прохождения одной ступени, необязательно постоянно (зависит от функции ступени и проходящих данных) и не равное (!)

Обработку с перекрытием называют часто (но не вполне корректно) асинхронной или динамической конвейеризацией. Классический пример – вычислительная система с совмещениями вычислений и операций ввода-вывода.

Классический пример обычной (синхронной или статической) конвейеризации показан на следующей странице.

(4.1.1.1) О классификации конвейеров вычислений.

Классифицируются по возможностям и применению.

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

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

В многофункциональных конвейерах выделяют:

1. конвейеры со статической конфигурацией (редко перестраивают)

2. векторные процессоры (конфигурация задается программно)

3. динамическая конфигурация (меняется для различных типов и форматов команд)

Функция сложения с плавающей запятой разбита на следующие подфункции:

• вычитание порядков;

• сдвиг вправо мантиссы числа, имеющего меньший порядок на величину разности порядков;

• сложение другой мантиссы со сдвинутой;

• подсчет числа нулей (единиц) в старших разрядах суммы;

• сдвиг влево суммы мантисс на число нулей (единиц) в старших разрядах и корректировка порядка.

(4.1.1.2) Помехи в конвейерах

Определялась помеха на странице 2.

Существуют две общие категории помех:

1. структурные

2. зависящие от данных

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

Во всех остальных случаях это очень сложная проблема. Решение в каждом случае уникально.

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

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

Такие помехи всегда зависят от режима работы системы и не поддаются аналитическому исследованию.

Разработано множество методов устранения помех.

4.1.2 Сравнение с параллелизмом

Напоминаю: оба метода направлены на увеличение производительности за счет увеличения числа аппаратных модулей, работающих одновременно.

Основные различия показаны на рисунке и в таблице.

4.1.3. Некоторые особенности организации памяти в конвейерных вычислителях.

Роль памяти в базовой структуре конвейерной вычислительной системы (КВС) в простейшем случае выполняют фиксаторы.

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

Основная память КВС содержит большинство данных и команд и наиболее «видима» программисту. В основе основной памяти (ОП) в КВС лежит модуль, который содержит фиксированное число слов, и только к одному из них может быть осуществлен доступ в данный момент времени. Объем памяти и скорость доступа можно увеличить, комбинируя модули.

Объем определяется решаемой задачей и особых проблем не ставит перед разработчиком.

А вот скорость доступа должна соответствовать быстродействию конвейера, иначе КВС теряет смысл.

Запросное отношение – отношение скорости доступа к скорости синхронизации конвейера – имеет минимальное значение 2:1 и растет в зависимости от длины и типа конвейера. В большинстве реальных систем существующая скорость доступа к отдельному базовому модулю памяти редко является достаточной для получения требуемого запросного отношения. Выход – осуществить одновременный доступ к нескольким модулям памяти, а это нам известно – расслоение памяти.

Ниже на рис. 2.20 показана последовательность действий для чтения слов из последовательных ячеек.

Рассмотренная здесь система со сложным расслоением, как и система с более простым расслоением, будет обрабатывать запросы на последовательные слова в N раз быстрее, чем отдельный модуль. Кроме того, она будет с той же высокой скоростью обрабатывать любую серию запросов, в которой ни один модуль в N последовательных запросах не используется более одного раза. Например, 8-кратно расслоенная память, типа показанной на рисунке, будет работать в 8 раз быстрее отдельного модуля, если последовательность адресов распределена равномерно не только с промежутком 1, но и с промежутками 3, 5, 7, 9, 11, … . Для промежутка 3 последовательность адресов имеет вид 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, … , а последовательность используемых модулей 1, 4, 7, 2, 5, 0, 3, 6, 1, 4, 7, … При некоторых других значениях промежутка работа будет происходить не с этой максимальной скоростью, но все же быстрее, чем при работе одного модуля.

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

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

Локальная память.

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

На рисунке: а) классическая кэш-память, помещаемая между конвейерным процессором и основной памятью.

Сложнее и чуть эффективнее структура дуального буфера (см. на рисунке. (б)). Вся сложность заключается в управлении переключением. Используется в векторных процессорах, в частности в легендарной машине CRAY-1.

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

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

Регистровые файлы.

В современных конвейерах вычислителей вместо простых фиксаторов между ступенями применяют более сложные структуры памяти. Годится любая из структур локальной памяти (см. выше), но еще меньшего объема. Цель – обеспечение функциональной гибкости конвейера.

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

Регистровый файл выполняет не менее трех функций, отсутствующих у простых фиксаторов ступени:

1. можно многократно использовать один и тот же набор данных, не прибегая к его повторной генерации (случай использования общего множителя);

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

3. осуществление переменной задержки данных для синхронизации потоков данных в сложных конвейерах и для защиты от «гонок» даже в самых простых конвейерах.

4.1.4 Соединение конвейерных ступеней.

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

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

Первый вариант очевиден и всем известен. Второй же случай используется для ускорения сложения в многоразрядном параллельном сумматоре.

А такое соединение превращает устройство в ступень в последовательном двоичном сумматоре.

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

На следующих двух схемах показано применение подобного устройства для построения конвейерного сумматора и конвейерного умножителя на основе последовательного переноса.

В схемах полно нюансов и их можно долго пояснять, но приходится экономить время.