Файл: 551-668.pdf

Ассоциативные вычислительные системы  5 7 1

Объединение реализуется за счет операций арифметического и логического сло-

жения, наложения записей, нахождения меньшего и большего из двух значений.

В некоторых SIMD-системах, например МР-1, имеется возможность записать од-
новременно пришедшие сообщения в разные ячейки локальной памяти.

Хотя пересылки данных по сети инициируются только активными ПЭ, пассив-

ные процессорные элементы также вносят вклад в эти операции. Если активный
ПЭ инициирует чтение из другого ПЭ, операция выполняется вне зависимости от

статуса ПЭ, из которого считывается информация. То же самое происходит и при
записи.

Наиболее распространенными топологиями в матричных системах являются

решетчатые и гиперкубические. Так, в ILLIAC IV, МРР и СМ-2 каждый ПЭ со-
единен с четырьмя соседними. В МР-1 и МР-2 каждый ПЭ связан с восьмью смеж-

ными ПЭ. В ряде систем реализуются многоступенчатые динамические сети со-

единений (МР-1, МР-2, GF11).

Ввод/вывод

Хотя программа вычислений хранится в памяти интерфейсной ВМ или иногда

в КМП, входные и выходные данные процессорных элементов и КМП могут хра-

ниться также на внешних ЗУ. Такие ЗУ могут подключаться к массиву про-
цессоров и/или КМП посредством каналов ввода/вывода или процессоров
ввода/вывода.

Ассоциативные вычислительные системы

К классу SIMD относятся и так называемые ассоциативные вычислительные сис-

темы. В основе подобной ВС лежит ассоциативное запоминающее устройство

(см. главу 5), а точнее —

 ассоциативный процессор,

 построенный на базе такого ЗУ.

Напомним, что ассоциативная память (или ассоциативная матрица) представляет

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

Ассоциативный процессор

 (АП) можно определить как ассоциативную память,

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

 мулътизаписи,

 является первым отличием ассоциативного процессора от

традиционной ассоциативной памяти. Считывание и запись информации могут

производиться по двум срезам запоминающего массива — либо это все разряды
одного слова, либо один и тот же разряд всех слов. При необходимости выделения

отдельных разрядов среза лишние позиции допустимо маскировать. Каждый раз-

ряд среза в АП снабжен собственным процессорным элементом, что позволяет
между считыванием информации и ее записью производить необходимую обра-

ботку, то есть параллельно выполнять операции арифметического сложения, по-

иска, а также эмулировать многие черты матричных ВС, таких, например, как

ILLIAC IV.

Таким образом,

 ассоциативные ВС

 или

 ВС с ассоциативным процессором

 есть

не что иное, как одна из разновидностей параллельных ВС, в которых

 п

 процес-

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

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

При этом каждое слово (ячейка) ассоциативной памяти имеет свое собственное

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

но всеми

 п

 ПЭ. Все или часть элементарных последовательных ПЭ могут синхрон-

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

Время обработки

 N

 m-разрядных слов в ассоциативной ВС определяется выра-

жением:

где

 t —

 время цикла ассоциативной памяти;

 п

 — число ячеек ассоциативной систе-

мы;

 К —

 коэффициент сложности выполнения элементарной операции (количе-

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

Вычислительные системы

с систолической структурой

В фон-неймановских машинах данные, считанные из памяти, однократно обраба-

тываются в процессорном элементе, после чего снова возвращаются в память (рис.

13.14

 а).

 Авторы идеи систолической матрицы Кунг и Лейзерсон предложили орга-

низовать вычисления так, чтобы данные на своем пути от считывания из памяти

до возвращения обратно пропускались через как можно большее число ПЭ (рис.

13.14,6).

а

 6

Рис. 13.14. Обработка данных в ВС: а — фон-неймановского типа;

б

 — систолической структуры

Если сравнить положение памяти в ВС со структурой живого организма, то по

аналогии ей можно отвести роль сердца, множеству ПЭ — роль тканей, а поток

данных рассматривать как циркулирующую кровь. Отсюда и происходит назва-

ние

 систолическая матрица

 (систола — сокращение предсердий и желудочков сер-

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

данных и т. д. В качестве примера авторами идеи был предложен линейный мас-

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

В основе схемы лежит ритмическое прохождение двух потоков данных

 x

i

 и у

i

,

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

i

 никогда

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

Рис. 13.15. Процесс векторного умножения матриц (n = 4)

бы не встретился с элементамиy y

i+l

, y

i+3

...

 Вычисления выполняются параллельно

в процессорных элементах, каждый из которых реализует один шаг в операции

вычисления скалярного произведения (IPS, Inner Product Step) и носит название

IPS-элемента

 (рис. 13.16).

Рис. 13.16. Функциональная схема IPS-элемента

Значение

 у

 нх

, поступающее на вход ПЭ, суммируется с произведением входных

значений

 х

вх

 и

 a

вх

.

 Результат выходит из ПЭ как

 у

ВЪ1Х

.

 Значение

 х

вх

,

 кроме того, для

возможного последующего использования остальной частью массива транслиру-
ется через ПЭ без изменений и покидает его в виде

 х

вых

.

Таким образом,

 систолическая структура —

 это однородная вычислительная

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

и матричной обработки и обладающая следующими особенностями:
- вычислительный процесс в систолических структурах представляет собой не-

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

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

-

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

зуется столько раз, сколько необходимо по алгоритму, ввод данных осуществ-
ляется в крайние ПЭ матрицы;

-

 образующие систолическую структуру ПЭ однотипны и каждый из них может

быть менее универсальным,чем процессоры обычных многопроцессорных си-
стем;

-

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

ляет объединять ПЭ локальными связями минимальной длины;

- алгоритмы функционирования позволяют совместить параллелизм с конвей-

ерной обработкой данных;

-

 производительность матрицы можно улучшить за счет добавления в нее опре-

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

В настоящее время достигнута производительность систолических процессо-

ров порядка 1000 млрд операций/с.

Классификация систолических структур

Анализ различных типов систолических структур и тенденций их развития позво-

ляет классифицировать эти структуры по нескольким признакам.

По

 степени гибкости

 систолические структуры могут быть сгруппированы на:

-

 специализированные;

-

 алгоритмически ориентированные;

-

 программируемые.

Специализированные структуры ориентированы на выполнение определенного

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

Алгоритмически ориентированные структуры обладают возможностью про-

граммирования либо конфигурации связей в систолической матрице, либо самих

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

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

рами, матрицами и другими числовыми множествами.

В программируемых систолических структурах имеется возможность програм-

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

По разрядности процессорных элементов

 систолические структуры делятся на:

-

 одноразрядные;

- многоразрядные.

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

В одноразрядных матрицах ПЭ в каждый момент времени выполняет опера-

цию над одним двоичным разрядом; а в многоразрядных — над словами фиксиро-

ванной длины.

По

 характеру локально-пространственных связей

 систолические структуры

бывают:

- одномерные;
- двухмерные;
- трехмерные.

Выбор структуры зависит от вида обрабатываемой информации. Одномерные

схемы применяются при обработке векторов, двухмерные — матриц, трехмерные —
множеств иного типа.

Топология систолических структур

В настоящее время разработаны систолические матрицы с различной геометрией

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

Рис. 13.17. Конфигурация систолических матриц: а — линейная; б— прямоугольная;

в

 — гексагональная; г — трехмерная

Каждая конфигурация матрицы наиболее приспособлена для выполнения оп-

ределенных функций, например линейная матрица оптимальна для реализации
фильтров в реальном масштабе времени; гексагональная — для выполнения опе-
раций обращения матриц, а также действий над матрицами специального вида
(Теплица- Генкеля); трехмерная — для нахождения значений нелинейных диффе-
ренциальных уравнений в частных производных или для обработки сигналов ан-

тенной решетки. Наиболее универсальными и наиболее распространенными, тем

не менее, можно считать матрицы с линейной структурой.

Для решения сложных задач конфигурация систолической структуры может

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