Матричные и векторно–конвейерные ЭВМ. Принцип действия, назначение, области применения.

Введение

Экспериментальные разработки многопроцессорных вычислительных систем начались в 1960-х годах. Первой такой системой стала система ILLIAC-IV (Illinois Automatic Computer), в состав которой входили 64 процессора, функционировавших под управлением единой программы, применяемой к содержимому собственной оперативной памяти каждого процессора. Осуществление обмена данными между процессорами происходило с помощью специальной матрицы коммуникационных каналов. Первые матричные вычислительные системы имели чрезвычайно высокую стоимость, а их выпуск осуществлялся практически поштучно. Серийные образцы таких систем, появившиеся значительно позже, не получили широкого распространения из-за сложности программирования матричных вычислительных систем с одним потоком управления.
Первыми промышленными многопроцессорными системами стали системы на базе векторно-конвейерных компьютеров, появившиеся в середине 1980-х годов. Наиболее широкое распространение среди систем данного класса получили суперкомпьютеры фирмы Cray. Тем не менее, и они выпускались крайне ограниченными партиями в виды чрезвычайно высокой стоимости. Как правило, в подобных компьютерах были объединены от 2 до 16 процессоров, имевших равноправный или симметричный доступ к общей оперативной памяти. Такие системы стали называть симметричными мультипроцессорными системами (Symmetric Multiprocessing — SMP). [3]
Альтернативу дорогим мультипроцессорным системам на базе векторно-конвейерных процессоров составили эквивалентные по мощности многопроцессорные системы, состоящие из большого количества дешевых серийных микропроцессоров. Но вскоре выяснилось, что SMP-архитектура накладывает весьма значимые ограничения на возможности увеличения количества процессоров, которое связано с пропорциональным увеличением количества конфликтов при обращении к общей шине памяти. Проблема была решена путем снабжения каждого процессора собственной оперативной памятью, таким образом, параллельная система превращалась в объединение независимых вычислительных узлов. Данный подход позволил в значительной мере увеличить степень масштабируемости многопроцессорных систем, но при этом понадобилась разработка собственного способа обмена информацией между вычислительными узлами, который был реализован в виде механизма передачи сообщений (Message Passing). Системы, в основе которых лежала данная архитектура дали толчок для развития отдельного направления параллельных вычислительных систем — MPA (Message Passing Architecture).
МАТРИЧНЫЕ ЭВМ
Отличительная особенность матричных вычислительных систем заключается в жестко синхронизируемой множественной обработке данных. Высокий показатель производительности достигается за счет большого числа простых по структуре процессоров, каждый из которых представляет собой большую интегральную схемы и называется процессорным элементом из-за ограниченного круга выполняемых операций.
Основной проблемой, стоящей перед разработчиками матричных вычислительных систем является организация межпроцессорных связей. Решение данной проблемы значительно упрощается для матрицы процессоров, функционирующих в синхронном режиме. Кроме технических причин такой организации матричных систем, существует также экономическая — построение N процессоров с одним устройством управления стоит дешевле, чем построение N аналогичных вычислительных машин.
Ключевые компоненты матричных вычислительных систем:
блок общего управления;
блоки локального управления;
коммутационная среда;
набор банков памяти;
набор процессорных элементов.
Наиболее общая структура матричных вычислительных систем содержит наборы идентичных процессоров и банков памяти. Каждый процессор может непосредственно соединяться со своей секцией памяти. Связь между процессорами и присвоенным ему банком памяти осуществляется через коммутационную среду, объединяющую все процессоры. Схема такой организации системы приведена на рисунке 1, где коммутационная среда изображена как отдельный компонент, подключаемый к процессорам с помощью входов и выходов.

Рисунок SEQ Рисунок \* ARABIC 1 - Типовая структура процессорной матрицы с одинаковым числом процессоров и банков памяти
Кроме того, существует другая распространенная конфигурация, с использованием более сложной коммутационной среды: коммутатор установлен между процессорами и банками памяти (рисунок 2). Такая конфигурация позволяет устранить ограничения на связь процессора только с одним единственным банком памяти, что позволяет использовать в матрице различное количество процессоров и банков памяти.

Рисунок SEQ Рисунок \* ARABIC 2 - Типовая структура процессорной матрицы, предусматривающая различное число банков памяти и процессоров
Управление работой системы осуществляется устройством управления или управляющим процессором, который характеризуется высоким быстродействием и имеет многомодульную оперативную память большого объема. Высокое быстродействие управляющего процессора обеспечивает непрерывность потока команд, направляемых для выполнения в матрицу процессоров. Повышенные требования к характеристикам оперативной памяти обусловлены спецификой применения матричных систем, рассчитанных на выполнение трудоемких программ, перерабатывающих наборы данных большого объема. Кроме программ, исходных наборов данных, промежуточных и выходных результатов в оперативной памяти размещаются резидентные программы операционной системы, организующей и контролирующей ход вычислительных процессов.
При работе системы управляющий процессор выбирает команды из оперативной памяти, декодирует их с целью выявления команд обработки данных и направляет последние в матрицу процессоров поочередно. Команды переходов выполняются самим процессором управления с учетом состояния процессоров на момент завершения предшествующей команды. Команды ввода/вывода передаются для выполнения в процессор ввода/вывода.
Процессоры однородны по составу и представляют собой относительно простые арифметико-логические устройства, обладающие высокой скоростью обработки данных. Блоки управления процессорами содержат средства дешифрации арифметико-логических операций, управления их реализацией, формирования признаков по результатам операций и обращения к локальной сверхоперативной памяти. Все процессоры, кроме блокируемых, в один и тот же момент времени выполняют одну и ту же операцию, жестко задаваемую управляющим процессором, над различными данными, размещаемыми в локальной сверхоперативной памяти. Процессор может пропустить команду, т. е. блокировать ее, если на его входе нет данных, но выполнять команду, отличную от заданной для всех, не может. Асинхронное выполнение различных команд в различных процессорах в одном такте потребовало бы существенно более сложной организации управляющего процессора и усложнения структуры системы в целом.
Несмотря на то, что идея регулярной матрицы процессоров, выполняющих одну и ту же операцию над различными данными, является основой канонической матричной вычислительной системы, на практике часто требуется некоторая форма автономного управления отдельным процессором для реализации независимых разветвлений данных в пределах потока команд.
В простейшем случае такой подход реализуется с помощью передачи одного одноразрядного флага в каждый процессор для маскирования выполнения команды. Таким образом, процесс управления представляет собой трансляцию команд в матрицу, выполняемую устройством управления, а затем каждый элементарный процессор делает выбор — выполнять или не выполнять команду в зависимости от того, установлен или не установлен флаг. Действия процессора обычно сводятся к тому, разрешить ли на основе состояния данного флага циклы записи в память или регистры. [4]
Известно несколько альтернативных вариантов организации системы управления матрицей процессоров, предусматривающих декодирование некоторых команд в процессорах. В зависимости от объема управления, возлагаемого на элементарный процессор, такие системы можно разбить на два типа: системы с полной процессорной независимостью и системы с микропрограммным управлением.
В системах с полной процессорной независимостью каждый процессор матрицы имеет локальный блок управления, который независимо от других процессоров и устройства управления декодирует собственную программу. Однако при любой управляющей структуре должна существовать некоторая форма глобального управления, которая инициирует, останавливает и синхронизирует элементарные процессоры. Заметим, что согласно используемой нами терминологии такие системы следует рассматривать как матрицу компьютеров.
Достоинство систем с полной независимостью процессоров заключается в том, что каждый процессор следит за своей магистралью и в соответствии с индивидуальной программой выполняет операции над своими данными. Синхронизация требуется только после обновления глобальной базы данных и выполняется с помощью флага, устанавливаемого для каждого элементарного процессора или компьютера матрицы.
Простейшим примером матричной вычислительной системы с микропрограммным управлением является двухуровневая управляющая структура. Первый уровень — общий, на нем производятся декодирование команд и транслирование их в матрицу, на этом уровне матрица синхронизируется. На втором (более низком) уровне элементарный процессор интерпретирует команду и генерирует микрокоманды. Важно отметить, что задаваемая команда может быть интерпретирована в микропроцессоре различными способами. Поскольку последовательности микрокоманд могут быть различной длины, синхронизация достигается с помощью системы флагов или, что предпочтительнее, посредством опережающего просмотра последовательностей более длинных микрокоманд в любой заданной команде. [2]
Одной из характерных особенностей архитектуры матричных вычислительных систем является организация памяти, определяющая способы ее адресации и подключения к элементарным процессорам.
В случае структуры, представленной на рисунке 1, где каждый процессор подключается к своему блоку памяти, остается определить, как происходит адресация памяти. Команды, выдаваемые устройством управления, обычно содержат одинаковый адрес для всех процессоров. Вопрос состоит в том, разрешить ли индивидуальному процессору обрабатывать этот адрес с помощью своего индексного регистра.
В случае структуры, приведенной на рисунке 2, используется более сложная коммутационная среда, обеспечивающая связь каждого процессора с любым блоком памяти

. При этом адресация к каждому банку памяти осуществляется независимо.
Конфликты на уровне банков памяти — один из основных недостатков любой параллельной организации памяти. В качестве примера на рисунке 3а представлена матрица 4x4, хранящаяся в четырех банках памяти. Можно видеть, что обращение к строкам матрицы A можно осуществлять без конфликтов, но все данные столбцов матрицы A располагаются в одном и том же банке памяти, поэтому выборку этих данных нельзя выполнять параллельно.

Рисунок SEQ Рисунок \* ARABIC 3 - Примеры использования схем хранения элементов матрицы, обеспечивающих бесконфликтный доступ к строкам матрицы A (а); к строкам и столбцам матрицы A (б)
При наличии сети коммутации, которая может подключать все банки памяти к одному процессору, желательно иметь структуру памяти или данных, при которой обращение к строкам, столбцам и другим основным подструктурам в виде матриц можно осуществлять без конфликтов. Одним из основных способов достижения этой цели является применение асимметричных схем хранения. На рисунке 3б показан пример такой схемы для матрицы 4x4. Она обеспечивает бесконфликтный доступ к строкам и столбцам, хотя для диагоналей матрицы A конфликты сохраняются.
Фирма Burroughs в проекте BSP предложила структуру памяти на основе асимметричных схем. Уникальной особенностью системы BSP является то, что каждое арифметико-логическое устройство обеспечивается операндами за один цикл обращения к памяти. Это означает, что расстояние в памяти между элементами вектора необязательно должно быть единичным. Поэтому циклы могут выполняться с неединичным шагом, а программы могут получить доступ к строкам, столбцам или диагоналям матриц без возникновения конфликтов. [2]
Следует отметить, что до появления асимметричной схемы BSP память суперкомпьютеров, основанная на относительно дешевых компонентах, не имела такого свойства. Разработчики либо использовали дешевые компоненты и вводили существенные ограничения на доступ к отдельным ячейкам памяти, либо применяли дорогую быстродействующую компонентную базу и пытались сократить количество конфликтов при обращениях к памяти повышением пропускной способности.
В основе предложенного способа организации памяти лежат: простое число портов памяти, полный матричный коммутатор между портами памяти арифметико-логического устройства и специальные формирователи индекса ячеек памяти и тегов портов коммутатора.
Формирователи индексов и тегов вычисляют реальные адреса для конкретного способа адресации элементов массива, который основан на принципе, присущем последовательным системам: каждый последующий адрес ссылается на следующее слово в памяти. Таким образом, была обеспечена совместимость с последовательными языками программирования.
Индекс определяется выражением (1).
i=A/NАЛУ(1);
где 𝐴 — адрес,
𝑁АЛУ — количество арифметико-логических устройств в системе.

Таким образом, индекс остается неизменным для цикла с числом итераций, равным 𝑁АЛУ, после чего он увеличивается на единицу. Тег, или номер банка памяти, в котором хранится значение, связанное с адресом 𝐴, определяется выражением (2)
µ=A mod NБ (2);
где 𝑁Б — количество банков памяти в системе (простое число, большее либо равное 𝑁АЛУ). [1]

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

Рисунок SEQ Рисунок \* ARABIC 4 - Пример использования схемы хранения с числом банков памяти, задаваемым простым числом
При обращении к строкам матрицы шаг приращения адреса равен числу строк, при обращении к столбцам — единице, а при обращении к диагоналям — числу строк плюс один.
Коммутационная среда является основой структуры матричных вычислительных систем и продуманное ее построение важно для эффективного использования системы в целом.
Для обмена промежуточными результатами процессоры могут быть связаны между собой как с применением межпроцессорного коммутатора, так и без него.
В системе без коммутатора наиболее распространенным является размещение процессоров в узлах квадратной решетки, размерность которой 𝑁 = n x n. Пример матрицы из 16 процессоров представлен на рисунке 5. Каждый процессор связан с четырьмя другими по правилу {(i±1) mod 16} или {(i±4) mod 16}. В схемах соединения этого вида передача данных от одного процессора к другому требует не более (log2𝑁 - 1) шагов. Возможны и другие способы соединения процессоров, основанные на использовании решеток в виде шестиугольников, восьмиугольников и многомерных покрытий.

Рисунок SEQ Рисунок \* ARABIC 5 - Матрица процессорных элементов
Традиционным примером матричных вычислительных систем является ILLIAC-IV. Проект этой системы рассчитан на 256 процессоров, разбитых на четыре матрицы размером 8x8 каждая. Система должна была состоять из четырех квадрантов, каждый из которых включал 64 процессора и 64 модуля памяти, объединенных коммутатором на базе сети типа гиперкуба. Все процессоры квадранта обрабатывают векторную инструкцию, которую им направляет процессор команд, причем каждый выполняет одну элементарную операцию вектора, данные для которой сохраняются в связанном с этим процессором модуле памяти. Таким образом, один квадрант ILLIAC-IV способен одновременно обрабатывать 64 элемента вектора, а вся система из четырех квадрантов — 256 элементов.
Результаты эксплуатации системы получились неоднозначными: с одной стороны, использование суперкомпьютера позволило решить ряд сложнейших задач аэродинамики, с которыми не могли справиться другие системы; с другой стороны, на практике разработчики ILLIAC-IV ограничились лишь одним квадрантом. Причинами явились не столько технические сложности в наращивании числа процессоров системы, сколько проблемы, связанные с программированием обмена данными между процессорами через коммутатор модулей памяти. Все попытки решить эту задачу с помощью системного программного обеспечения потерпели неудачу, в результате каждое приложение потребовало ручного программирования передач коммутатора, что и породило неудовлетворительные отзывы пользователей. [1]
Несмотря на то, что матричные вычислительные системы не нашли широкого применения, разработка суперкомпьютеров с матричной архитектурой имела огромное значение для дальнейшего развития параллельных вычислительных систем в целом. Во-первых, удалось доказать возможность практической реализации быстродействующей параллельной обработки информации. Во-вторых, на волне интереса к матричным структурам были сформулированы теоретические основы построения коммутационных сред, объединяющих множество процессоров. В-третьих, в прикладной математике сформировалось самостоятельное направление по параллельным вычислениям.

ВЕКТОРНО-КОНВЕЙЕРНЫЕ ЭВМ
Достижение производительности большинства суперкомпьютеров основано на применении принципов векторно-конвейерной обработки информации. Стоит также отметить, что в настоящее время данные принципы широко применяются также и во встраиваемых процессорах, к примеру, в сигнальном процессоре TigerSharc от Analog Devices реализована поддержка векторных команд, которая существенно повышает его производительность при обработке векторов данных.
Векторами данных называют группы данных, которые расположены в упорядоченных регистрах.
Повышение производительности может достигаться как включением средств векторной обработки данных в состав процессора, так и интеграцией в систему специализированного векторного сопроцессора. Обычно, система, поддерживающая выполнение векторных команд, поддерживает также и выполнение скалярных команд.
Векторные команды имеют ряд особенностей. Код векторной команды не только задает нужную операцию для выполнения, но также определяет необходимую конфигурацию активных элементов конвейера для исполняемой операции - указывает на начало вектора в памяти, определяет длину вектора, размер и тип его элементов вектора, а также расположение результирующего вектора. [5]
Основной потенциал распараллеливания задач на векторноконвейерной системе заключается в распараллеливании вычислительных циклов. Программист Д. Кнут показал [3], что циклы do занимают не 4% кода на языке FORTRAN, но при этом занимают более 50% счетного времени задачи. Аналогичные рассуждения будут справедливы и для прочих языков высокого уровня.
Простейшим примером вычислительного цикла является операция сложения двух одноименных элементов векторов A и B:
for (i = 0; i < N; i++)
C[i] = A[i] + B[i];

В соответствие с классификацией М. Флинна [4] большинство компьютеров — от персональных компьютеров до высокопроизводительных рабочих станций — относятся к SISD-системам, в которых выполнение программы осуществляется последовательно, при этом каждой командой формируется только один числовой результат. Совершенно ясно, что выполнение цикла из примера, приведенного выше, потребует от компьютера класса SISD, по меньшей мере, N операций сложения элементов векторов A и B, а также, 2N команд условного перехода и приращения индекса.
Сама идея векторной обработки подобных циклов заключается в том, что в систему команд компьютера вводится векторная операция сложения A + B , которая осуществляет сложение всех элементов векторов-операндов. Таким образом, появляются сразу две возможности повышения производительности вычислений:
возможность одновременного выполнения всех операций сложения элементов векторов-операндов, за счет параллелизма вычислений;
сокращение количества команд объектного кода, исполняемых процессором, за счет отсутствия необходимости перерасчета индексов и организации переходов.
Действительно, в примере выше, результат любой i-й операции цикла не будет влиять на ход оставшихся (N - 1) операций. Таким образом, если система способна одновременно выполнить N циклических операций, то для выполнения векторной команды потребуется в N раз меньше времени, чем для последовательной циклической обработки