Конвейерные процессоры для векторной обработки

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

Для перемножения матриц на последовательных ЭВМ неизменно применяется гнездо из трех циклов:

DО 1 I = 1, L
DО 1 J = 1, L
DО 1 K = 1, L
1 С(I, J) = С(I, J) + А(I, K) * В(K, J)

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

R (*) = A (I, *) * В (*, J) (2.1)
С (I, J) = SUM R (*)

Здесь R(*), A(I, *), D(*, J)- векторы размерности L; первый оператор представляет бинарную операцию над векторами, а второй - унарную операцию SUM суммирования элементов вектора.

Для выполнения операций над векторами также используются арифметические конвейеры. Структура конвейерного процессора для обработки векторов показана на рис. 2.13.

Рис. 2.13 Структура векторного конвейерного процессора

Структура устройства управления этого процессора не рассматривается, так как она аналогична структуре управления скалярного конвейерного процессора (отличие в том, что при выпол-нении векторной команды код операции команды не меняется).

Главная особенность векторного процессора - наличие ряда векторных регистров V (обычно до 8), каждый из которых позволяет хранить вектор длиною до 64 слов. Это своего рода РОН, значительно ускоряющие работу векторного процессора. Назначение остальных узлов такое же, как и узлов, изображенных на рис. 2.11.

Рассмотрим, как будет выполняться программа (2.1) в векторном процессоре. На условном языке ассемблерного уровня программа может быть представлена следующим образом:

1 LD L, Vi, A
2 LD L, Vj, B
3 MP Vk, Vi, Vj (2.2)
4 SUM Sn, Vk

Операторы 1 и 2 соответствуют загрузке слов из памяти с начальными адресами A и B в регистры Vi, Vj; оператор 3 означает поэлементное умножение векторов с размещением результата в регистре Vk; оператор 4 - суммирование вектора из Vk с размещением результата в Sn.

Соответственно этой программе векторные регистры сначала потактно заполняются из ЦМП, а затем слова из векторных регистров потактно (одна пара слов за такт) передаются в конвейерные АЛУ, где за каждый такт получается один результат.

Рассмотрим характеристики быстродействия векторного процессора на примере выполнения команды MP Vi, Vj, Vk. Число тактов, необходимое для выполнения команды, равно: r = m* + L, где m* - длина конвейера умножения. Поскольку на умножение пары операндов затрачивается k = (m* + L)/L тактов, то быстродействие такого процессора

где Δt - время одного такта работы конвейера.

Быстродействие конвейера зависит от величины L (рис. 2.14, кривая 1). При L>m* величина K = 1 и V = 1/Δt. Обычно для векторных процессоров стараются сделать Δt малым, в пределах 10...20 нс, поэтому быстродействие при выполнении векторных операций может достигать 50...10 млн оп/с.

Рис.2.14. Зависимость быстродействия векторного процессора от длины вектора: mЦМП = 4; m* = 7; m+ = 6

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

LD L, Vi, А
ЗЦ Sn, Vi, В

Здесь команда зацепления (ЗЦ) задает одновременное выполнение операций в соответствии со схемой соединений (рис. 2.15).

Рис. 2.15. Выполнение операции зацепления в векторном конвейерном процессоре

Для команды ЗЦ получаем:

где n - число одновременно выполняемых операций. В случае команды ЗЦ n = 3 (рис. 2.14, кривая 2). При L>>mi и Δt = 10...20 нс в зацеплении быстродействие равно 150...300 млн оп/с. Такое быстродействие достигается не на всех векторных операциях. Для векторных ЭВМ существуют "неудобные" операции, в которых ход дальнейших вычислений определяется в зависимости от результата каждой очередной элементарной операции над одним или парой операндов. В подобных случаях L приближается к единице. К таким операциям относятся операции рассылки и сбора, которые можно определить следующими отрезками фортран-программ:

1) рассылка

DO 1 I = 1, L
1 X(INDEX (I)) = Y (I)

2) сбор

DO 1 I = 1, L
1 Y (I) = X (INDEX (I))

Целочисленный массив INDEX содержит адреса операндов, разбросанных произвольным образом в памяти процессоров. Операция рассылки распределяет упорядоченный набор элементов Y(I) по всей памяти в соответствии с комбинацией адресов в массиве INDEX. Операция сбора, наоборот, собирает разбросанные элементы X в упорядоченный массив Y. Названные операции имеются в задачах сортировки, быстрого преобразования Фурье, при обработке графов, представленных в форме списка, и во многих других задачах.

Быстродействие векторного процессора на таких операциях снижается до уровня быстродействия скалярного процессора.

Выше конвейерные ЭВМ были описаны по частям: сначала скалярная часть, затем векторная. Теперь рассмотрим полную структуру векторной ЭВМ на примере машины CRAY (рис. 2.16).

CRAY-1, созданная в 1976 г., была одной из первых ЭВМ, в которой в полной мере проявились все характерные особенности векторно-конвейерных машин. Машина CRAY-1 включает стандартные для любой ЭВМ секции: управления памятью и ввода-вывода, регистровую секцию и группу функциональных устройств. Однако состав оборудования каждой секции существенно отличается от аналогичных устройств последовательных ЭВМ.

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

Структура УУ описана в параграфе 1. Здесь имеются механизмы предварительного просмотра команд, а также резервирования регистров и функциональных устройств.

Рис. 2.16. Структура Векторной ЭВМ. В скобках указана длина конвейеров

Для выполнения адресных операций используются группа адресных регистров A0...A7 и специальные АЛУ для операций целочисленной арифметики. Эти АЛУ, как и все другие функциональные устройства, имеют конвейерную структуру.

Скалярные операции выполняются с помощью группы регистров S0...S7, а векторные - с помощью векторных регистров V0...V7.

Наибольший интерес представляет состав функциональных устройств. В выполнении скалярных операций участвует семь функциональных устройств: четыре для работы с целочисленной арифметикой и три для работы с числами с плавающей запятой. Устройство "Счетчик" используется для подсчета числа единиц в операнде или числа нулей, предшествующих первой единице опе-ранда.

Поскольку деление плохо поддается конвейеризации, в CRAY-1 оно выполняется в устройствах обратной аппроксимации и умножения посредством итерационной процедуры. Такой подход позволяет использовать конвейерную обработку на операции умножения и зацепление операций.

Векторные операции в CRAY-1 можно разделить на четыре типа. Векторная инструкция первого типа получает операнды из одного или двух регистров V и отправляет результат в другой регистр V. Последовательные пары операндов передаются из Vj и Vk в конвейерное АЛУ в каждом такте, и соответствующий результат на выходе АЛУ появляется на m тактов позже, где m - длина конвейера. Результат отправляется в регистр результата Vi. Векторная инструкция второго типа получает по одному операнду из регистров S и V. Инструкции двух других типов передают данные между памятью и регистрами V.

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

Две команды машины CRAY-1 требуют специального объяснения. Установка маски 64-разрядного векторного регистра маски (VM) соответствует 64 элементам векторного регистра. Если элемент удовлетворяет условию, то соответствующий разряд VM устанавливается в 1, в противном случае - в 0. Таким образом команда, VM V5, Z устанавливает разряд VM в 1, когда элементы V5 равны нулю; VM V7, P устанавливает разряд VM в 1, если элементы V7 положительны.

По команде слияния векторов содержимое двух векторных регистров Vi и Vk сливается в один результирующий вектор Vi в соответствии с маской регистра VM. Если l-й разряд VM - единица, то l-й элемент Vj становится l-м элементом регистра результа-тов, в противном случае l-й элемент Vk становится l-м элементом регистра результатов. Значение регистра длины вектора определяет число сливаемых элементов. Таким образом, команда ViVj!Vk&VM сливает Vj и Vk в Vi в соответствии с комбинацией в VM; V7S2!V6&VM сливает S2 и V6 в V7 в соответствии с комбинацией в VM.

Цель команд маски и слияния - обеспечить условные вычисления с векторными командами.

В CRAY-1 соотношение объема памяти хорошо сбалансировано с производительностью системы. По эмпирическому правилу Амдала 1 бит памяти должен приходиться на 1 оп/с. В CRAY-1 при памяти 1 Мслов (64 Мбит) производительность равна 80 Моп/с.

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

Составлено по материалам книги Г.И. Шпаковский. Организация параллельных ЭВМ и суперскалярных процессоров