ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 20.06.2021
Просмотров: 388
Скачиваний: 1
Тема 7. Понятие о многомашинных и многопроцессорных вычислительных системах (ВС)
Лекция 16. Параллельные системы
1. Векторные и матричные ВС.
2. ВС с командами сверхбольшой длины.
3. ВС с явным параллелизмом команд.
4. Системы с массовой параллельной обработкой.
1. Векторные и матричные ВС
SIMD-системы были первыми вычислительными системами, состоящими из большого числа процессоров, и среди первых систем, где была достигнута производительность порядка GFLOPS.
В настоящее время принято считать, что класс SIMD составляют векторные (векторно-конвейерные), матричные, ассоциативные, систолические и VLIW-вычислительные системы.
Массивы данных представляются матрицами и векторами, а алгоритмы их обработки описываются в терминах матричных операций. Как известно, основные матричные операции сводятся к однотипным действиям над парами элементов исходных матриц, которые, чаще всего, можно производить параллельно. В универсальных ВС, ориентированных на скалярные операции, обработка матриц выполняется поэлементно и последовательно. При большой размерности массивов последовательная обработка элементов матриц занимает слишком много времени, что и приводит к неэффективности универсальных ВС для рассматриваемого класса задач. Для обработки массивов требуются вычислительные средства, позволяющие с помощью единой команды производить действие сразу над всеми элементами массивов – средства векторной обработки.
Понятие вектора и размещение данных в памяти
В средствах векторной обработки под вектором понимается одномерный массив однотипных данных (обычно в форме с плавающей запятой), регулярным образом размещенных в памяти ВС. Если обработке подвергаются многомерные массивы, их также рассматривают как векторы. Такой подход допустим, если учесть, каким образом многомерные массивы хранятся в памяти ВМ. Пусть имеется массив данных А, представляющий собой прямоугольную матрицу размерности 45 (рис. 1).
При размещении матрицы в памяти все ее элементы заносятся в ячейки с последовательными адресами, причем данные могут быть записаны строка за строкой или столбец за столбцом (рис. 2). С учетом такого размещения многомерных массивов в памяти вполне допустимо рассматривать их как векторы и ориентировать соответствующие вычислительные средства на обработку одномерных массивов данных (векторов).
Рис. 1. Прямоугольная матрица данных
Рис. 2. Способы размещения в памяти матрицы 45
Действия над многомерными массивами имеют свою специфику. Например, в двумерном массиве обработка может вестись как по строкам, так и по столбцам. Это выражается в том, с каким шагом должен меняться адрес очередного выбираемого из памяти элемента. Так, если рассмотренная в примере матрица расположена в памяти построчно, адреса последовательных элементов строки различаются на единицу, а для элементов столбца шаг равен пяти. При размещении матрицы по столбцам единице будет равен шаг по столбцу, а шаг по строке – четырем.
Еще одной характеристикой вектора является число составляющих его элементов – длина вектора.
Векторный процессор – это процессор, в котором операндами некоторых команд могут выступать упорядоченные массивы данных – векторы. Векторный процессор может быть реализован в двух вариантах. В первом он представляет собой дополнительный блок к универсальной вычислительной машине (системе). Во втором – векторный процессор – это основа самостоятельной ВС.
Рассмотрим возможные подходы к архитектуре средств векторной обработки. Наиболее распространенные из них сводятся к трем группам:
конвейерное АЛУ;
массив АЛУ;
массив процессорных элементов.
Последний вариант – один из случаев многопроцессорной системы, известной как матричная ВС. Понятие векторного процессора имеет отношение к двум первым группам (рис. 3).
Рис. 3. Варианты векторных вычислений
В варианте, с конвейерным АЛУ (рис. 4, а) обработка элементов векторов производится конвейерным АЛУ для чисел с плавающей запятой (ПЗ).
Рис. 4. Модели обработки векторов
Операции с числами в форме с ПЗ могут быть сведены к четырем этапам (рис. 4, а):
сравнению порядков;
сдвигу мантиссы меньшего из чисел;
сложению мантисс;
нормализации результата.
Каждый этап может быть реализован с помощью отдельной ступени конвейерного АЛУ (рис. 4, б). Очередной элемент вектора подается на вход конвейера, как только освобождается первая ступень (рис. 4, в). Ясно, что такой вариант вполне годится для обработки векторов.
Одновременные операции над элементами векторов можно проводить и с помощью нескольких параллельно используемых АЛУ, каждое из которых отвечает за одну пару элементов (рис. 3, б). Такого рода обработка, когда каждое из АЛУ является конвейерным, показана на рис. 4, г.
Если параллельно используются конвейерные АЛУ, то возможен еще один уровень конвейеризации, что иллюстрирует рис. 4, д. Вычислительные системы, где реализована эта идея, называют векторно-конвейерными. Коммерческие векторно-конвейерные ВС, в состав которых для обеспечения универсальности включен также скалярный процессор, известны как суперЭВМ.
Обобщенная структура векторного процессора приведена на рис. 5. На схеме показаны основные узлы процессора, без детализации некоторых связей между ними.
Рис. 5. Упрощенная структура векторного процессра
Обработка всех п компонентов векторов-операндов задается одной векторной командой. Общепринято, что элементы векторов представляются числами в форме с плавающей запятой (ПЗ). АЛУ векторного процессора может быть реализовано в виде единого конвейерного устройства, способного выполнять все предусмотренные операции над числами с ПЗ. Более распространена, однако, иная структура, – в ней АЛУ состоит из отдельных блоков сложения и умножения, а иногда и блока для вычисления обратной величины, когда операция деления Х/У реализуется в виде Х(1/У). Каждый из таких блоков также конвейеризирован.
Кроме того, в состав векторной вычислительной системы обычно включают и скалярный процессор, что позволяет параллельно выполнять векторные и скалярные команды.
Для хранения векторов-операндов вместо множества скалярных регистров используют так называемые векторные регистры, которые представляют собой совокупность скалярных регистров, объединенных в очередь типа FIFO, способную хранить 50-100 чисел с плавающей запятой. Набор векторных регистров (Va, Vb, Vc,...) имеется в любом векторным процессоре. Система команд векторного процессора поддерживает работу с векторными регистрами и обязательно включает в себя команды:
загрузки векторного регистра содержимым последовательных ячеек памяти, указанных адресом первой ячейки этой последовательности;
выполнения операций над всеми элементами векторов, находящихся в векторных регистрах;
сохранения содержимого векторного регистра в последовательности ячеек памяти, указанных адресом первой ячейки этой последовательности.
Примером одной из наиболее распространенных операций, возлагаемых на векторный процессор, может служить операция перемножения матриц.
Векторный процессор с конвейеризированными блоками обработки для вычисления скалярного произведения показан на рис. 6.
Рис. 6. Векторный процессор для вычисления скалярного произведения
Векторы А и В, хранящиеся в памяти начиная с адресов adrA и adrB, загружаются в векторные регистры VA и VB соответственно. Предполагается, что конвейерные умножитель и сумматор состоят из четырех сегментов, которые вначале инициализируются нулем, поэтому в течение первых восьми циклов, пока оба конвейера не заполнятся, на выходе сумматора будет 0. Пары (Аi, Вi) подаются на вход умножителя и перемножаются в темпе одна пара за цикл. После первых четырех циклов произведения начинают суммироваться с данными, поступающими с выхода сумматора. В течение следующих четырех циклов на вход сумматора поступают суммы произведений из умножителя с нулем. К концу восьмого цикла в сегментах сумматора находятся четыре первых произведения A1B1, ..., А4В4, а в сегментах умножителя – следующие четыре произведения: А5В5,..., А8В8. К началу девятого цикла на выходе сумматора будет A1, B1, а на выходе умножителя – А5В5. Таким образом, девятый цикл начнется со сложения в сумматоре А1, В1 и А5В5. Десятый цикл начнется со сложения А2В2 + А6В6 и т. д. Процесс суммирования в четырех секциях выглядит так:
Когда больше не остается членов для сложения, система заносит в умножитель четыре нуля. Конвейер сумматора в своих четырех сегментах при этом будет содержать четыре скалярных произведения, соответствующие четырем суммам, приведенным в четырех строках показанного выше уравнения. Далее четыре частичных суммы складываются для получения окончательного результата.
Программа для вычисления скалярного произведения векторов А и В, хранящихся в двух областях памяти с начальными адресами adrA и adrB, соответственно может выглядеть так:
V_Load VA, adrA
V_Load VB, adrB
V_muLtiplyVc,VA,VB.
Первые две векторные команды загружают векторы из памяти в векторные регистры VA и Ув. Векторная команда умножения V_multiply вычисляет произведение для всех пар одноименных элементов векторов и записывает полученный вектор в векторный регистр Vс.
Важным элементом любого векторного процессора (ВП) является регистр длины вектора. Этот регистр определяет, сколько элементов фактически содержит обрабатываемый в данный момент вектор, то есть сколько индивидуальных операций с элементами нужно сделать. В некоторых ВП присутствует также регистр максимальной длины вектора, определяющий максимальное число элементов вектора, которое может быть одновременно обработано аппаратурой процессора. Этот регистр используется при разделении очень длинных векторов на сегменты, длина которых соответствует максимальному числу элементов, обрабатываемых аппаратурой за один прием.
Использование векторных команд окупается благодаря двум качествам. Во-первых, вместо многократной выборки одних и тех же команд достаточно произвести выборку только одной векторной команды, что позволяет сократить издержки за счет устройства управления и уменьшить требования к пропускной способности памяти. Во-вторых, векторная команда обеспечивает процессор упорядоченными данными. Когда инициируется векторная команда, ВС знает, что ей нужно извлечь n пар операндов, расположенных в памяти регулярным образом. Таким образом, процессор может указать памяти на необходимость начать извлечение таких пар. Если используется память с чередованием адресов, эти пары могут быть получены со скоростью одной пары за цикл процессора и направлены для обработки в конвейеризированный функциональный блок. При отсутствии чередования адресов или других средств извлечения операндов с высокой скоростью преимущества обработки векторов существенно снижаются.
Структуры типа «память-память» и «регистр-регистр»
Принципиальное различие архитектур векторных процессоров проявляется в том, каким образом осуществляется доступ к операндам. При организации «память-память» элементы векторов поочередно извлекаются из памяти и сразу же направляются в функциональный блок. По мере обработки получающиеся элементы вектора результата сразу же заносятся в память. В архитектуре типа «регистр-регистр» операнды сначала загружаются в векторные регистры, каждый из которых может хранить сегмент вектора, например 64 элемента. Векторная операция реализуется путем извлечения операндов из векторных регистров и занесения результата в векторные регистры.
Обработка длинных векторов и матриц
Аппаратура векторных процессоров типа «регистр-регистр» ориентирована на обработку векторов, длина которых совпадает с длиной векторных регистров (ВР), поэтому обработка коротких векторов не вызывает проблем – достаточно записать фактическую длину вектора в регистр длины вектора.
Если размер векторов превышает емкость ВР, используется техника разбиения исходного вектора на сегменты одинаковой длины, совпадающей с емкостью векторных регистров (последний сегмент может быть короче), и последовательной обработки полученных сегментов.
Ускорение вычислений
Для повышения скорости обработки векторов все функциональные блоки векторных процессоров строятся по конвейерной схеме, причем так, чтобы каждая ступень любого из конвейеров справлялась со своей операцией за один такт (число ступеней в разных функциональных блоках может быть различным).
Матричные вычислительные системы
Назначение матричных вычислительных систем во многом схоже с назначением векторных ВС – обработка больших массивов данных. В основе матричных систем лежит матричный процессор (array processor), состоящий из регулярного массива процессорных элементов (ПЭ). Организация систем подобного типа включает в себя общее управляющее устройство, генерирующее поток команд, и большое число ПЭ, работающих параллельно каждый своим потоком данных. Однако на практике, чтобы обеспечить достаточную эффективность системы при решении широкого круга задач, необходимо организовать связи между процессорными элементами так, чтобы наиболее полно загрузить процессоры работой. Именно характер связей между ПЭ и определяет разные свойства системы.
Между матричными и векторными системами есть существенная разница. Матричный процессор интегрирует множество идентичных функциональных блоков (ФБ), логически объединенных в матрицу и работающих в SIMD-стиле. Не столь существенно, как конструктивно реализована матрица процессорных элементов – на едином кристалле или на нескольких. Важен сам принцип – ФБ логически, скомпонованы в матрицу и работают синхронно, то есть присутствует только один поток команд для всех. Векторный процессор имеет встроенные команды для обработки векторов данных, что позволяет эффективно загрузить конвейер из функциональных блоков.
Структуру матричной вычислительной системы можно представить в виде, показанном на рис. 7.
Рис. 7. Обобщенная модель SIMD-системы
Собственно параллельная обработка множественных элементов данных осуществляется массивом процессоров (МПр). Единый поток команд, управляющий обработкой данных в массиве процессоров, генерируется контроллером массива процессоров (КМП). КМП выполняет последовательный программный код, реализует операции условного и безусловного переходов, транслирует в МПр команды, данные и сигналы управления. Команды обрабатываются процессорами в режиме жесткой синхронизации.