Файл: 551-668.pdf

5 7 6 Глава 13. Вычислительные системы класса SIMD

риц либо обрабатывающую поверхность. Под

 обрабатывающей поверхностью

 по-

нимается бесконечная прямоугольная сетка ПЭ, где каждый ПЭ соединяется со

своими четырьмя соседями (или большим числом ПЭ). Одним из наиболее подхо-
дящих элементов для реализации обрабатывающей поверхности является матри-

ца простых ПЭ или транспьютеров.

Учитывая то, что матрицы ПЭ обычно реализуются на основе сверхбольших

интегральных схем, возникающие при этом ограничения привели к тому, что наи-

более распространены матрицы с одним, двумя и тремя трактами данных и с оди-

наковым либо противоположным направлением передачи, обозначаемые как ULA,
BLA и TLA соответственно.

ULA

 (Unidirectional Linear Array) — это однонаправленный линейный процес-

сорный массив, где потоки данных перемещаются в одном направлении. ПЭ в мас-

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

Рис. 13.18. Поток данных при векторном перемножении матрице ULA (n = 4)

При реализации алгоритма векторного произведения матриц один из потоков

данных перемещается вправо, в то время как второй резидентно расположен в мас-

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

хранятся в ПЭ массива.

BLA

 (Bidirectional Linear Array) — это двунаправленный линейный процессор-

ный массив, в котором два потока данных движутся навстречу друг другу. BLA,
где один из потоков является выходным, называется

 регулярным.

Рис. 13.19. Поток данных при векторном перемножении матриц в BLA (n = 4)

Реализация рассмотренной ранее операции с применением BLA показана на

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

TLA

 (Three-path communication Linear Array) — линейный процессорный мас-

сив с тремя коммуникационными трактами, в котором по разным направлениям
перемещаются три потока данных. На рис. 13.20 показан пример фильтра ARMA,
предложенного Кунгом и построенного по схеме TLA. Возможны несколько вари-
антов такого фильтра, в зависимости от числа выходных потоков данных и от зна-

Вычислительные системы с систолической структурой  5 7 7

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

 сдвоен-

ными1РS-элементами,

 Две версии таких ПЭ представлены на рис, 13.21. ПЭ могут

использовать как хранимые в памяти значения (рис. 13.21,

 а, б),

 так и внешние

данные (рис. 13.21,

 в, г).

в г

Рис. 13.21. Сдвоенные IPS-элементы:

 a-б

 — с хранимыми в памяти двумя значениями;

в-г

 — с внешними данными

TLA часто называют сдвоенным конвейером, поскольку он может быть разде-

лен на два линейных конвейера типа BLA. Соответственно, TLA можно получить
объединением двух BLA с одним общим потоком данных.

Представленные реализации алгоритма векторного произведения матриц вы-

полняют эту операцию за одно и то же время, но в случае ULA в вычислениях

участвуют вдвое меньше процессорных элементов. С другой стороны, ULA исполь-
зует хранимые в памяти данные, на чтение и запись которых нужно какое-то время.

В свою очередь, в схеме BLA требуется дополнительное время на операции ввода/
вывода.

Структура процессорных элементов

Тип ПЭ выбирается в соответствии с назначением систолической матрицы и струк-
турой пространственных связей. Наиболее распространены процессорные элемен-
ты, ориентированные на умножение с накоплением.

На рис. 13.22 показаны ПЭ для двух типов матриц: прямоугольной (см.

рис, 13.22,

 а)

 и гексагональной (см. рис. 13.22,

6).

5 7 8 Глава 13. Вычислительные системы класса SIMD

а

 6

Рис. 13.22. Структура ПЭ: a

 —

 для прямоугольной систолической матрицы;

б

 — для гексагональной систолической матрицы

В обоих случаях на вход ПЭ подаются два операнда

 А

вх

, В

вх

,

 а выходят операн-

ды

 А

вых

,

 В

вых

, и частичная сумма С

вых

,. На n-м шаге работы систолической системы

ПЭ выполняет операцию

на основе операндов, полученных на (n - 1)-м шаге, при этом операнды на входе
и выходе ПЭ одинаковы:

Частичная сумма поступает на вход ПЭ либо с данного процессорного элемен-

та (штриховая линия), либо с соседнего ПЭ матрицы.

Пример вычислений с помощью

систолического процессора

Организацию вычислительного процесса в систолических массивах различной

конфигурации с использованием ПЭ, функциональная схема которого показана
на рис. 13.23. удобнее всего пояснить на примере умножения матрицы А -(a

y

)на

вектор

Рис. 13.23. Функциональная схема процессорного Элемента систолической матрицы

Вычислительные системы с систолической структурой  5 7 9

Элементы вектора произведения Y =

 {у

1

 , у

2

,

...,

 у

п

)

 могут быть получены перио-

дически повторяющимися операциями

где

 k

 - номер шага вычислений.

Пусть имеется матрица А размером

 пхп с

 шириной полосы ненулевых элемен-

тов

 р + q -

 1 = 4. Схема умножения вектора на матрицу в этом случае представле-

на на рис. 13.24.

Рис. 13.24. Схема умножения вектора на матрицу

Определенная выше последовательность операций для вычисления компонен-

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

 х

i

 и

 у

i

 через

р + q

 - 1 последовательно соединенных ПЭ (рис. 13.25)

Рис. 13.25. Организация вычислений в линейной систолической структуре

Компоненты

 y

i

 (i - 1,...,n) вектора Y; имеющие в начальный момент нулевое

значение, поступают на вход массива и продвигаются через ПЭ справа налево, в то
время как компоненты вектора X движутся слева направо. Элементы матрицы А = {a

ij

}

в порядке, указанном на рисунке, вводятся в ПЭ сверху вниз. Промежуточные ре-
зультаты у

i

(k) накапливаются по мере продвижения от одного ПЭ к другому.

5 8 0

 Глава 13. Вычислительные системы класса SIMD

В табл. 13.1 показаны первые 6 шаГов алгоритма умножения для рассматривае-

мой структуры.

Таблица  1 3 . 1 .

 Последовательность умножения матрицы на вектор в систолической ВС

Заметим, что при такой организации вычислительного процесса для каждого

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

в каждый момент времени активны только (p+q-1)/2 процессорных элементов, сле-

довательно, каждый выходной результат формируется за два такта. Для вычисле-

ния всех и элементов выходного вектора Y необходимо 2n +

 р + q -

 1 тактов.

Вычислительные системы с командными

словами сверхбольшой длины (VLIW)

Архитектура с командными словами сверхбольшой длины

 или

 со сверхдлинными

командами

 (VLIW, Very Long Instruction Word) известна с начала 80-х из ряда

университетских проектов, но только сейчас, с развитием технологии производ-
ства микросхем она нашла свое достойное воплощение. VLIW — это набор команд,
организованных наподобие горизонтальной микрокоманды в микропрограммном
устройстве управления.

Идея VLIW базируется на том, что задача эффективного планирования парал-

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