Новосибирский государственный университет

Факультет информационных технологий

Словарь терминов в коллекции "Вычислительные системы"

Матричные вычислительные системы

Синонимы: Матричные вычислительные системы; Матричный процессор;

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

Назначение матричных вычислительных систем - обработка больших массивов данных. В основе матричных систем лежит матричный процессор (array processor), состоящий из массива процессорных элементов (ПЭ). Такие системы имеют общее управляющее устройство, генерирующее поток команд, и большое число ПЭ, работающих параллельно и обрабатывающих каждый свой поток данных. Однако на практике, чтобы обеспечить достаточную эффективность системы при решении широкого круга задач, необходимо организовать связи между процессорными элементами так, чтобы наиболее полно загрузить процессоры работой. Именно характер связей между ПЭ и определяет разные свойства системы. Подобная схема применима и для векторных вычислений.
Между матричными и векторными системами есть существенная разница. Матричный процессор интегрирует множество идентичных функциональных блоков (ФБ), логически объединенных в матрицу и работающих в SIMD-стиле. Не столь существенно, как конструктивно реализована матрица процессорных элементов - на едином кристалле или на нескольких. Важен сам принцип - ФБ логически скомпонованы в матрицу и работают синхронно, то есть присутствует только один поток команд для всех. Векторный процессор имеет встроенные команды для обработки векторов данных, что позволяет эффективно загрузить конвейер из функциональных блоков. В свою очередь, векторные процессоры проще использовать, потому что команды для обработки векторов - это более удобная для человека модель программирования, чем SIMD.

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

Для обеспечения пользователя удобным интерфейсом при создании и отладке программ в состав подобных ВС обычно включают фронтальную ВМ (front-end computer). В роли такой ВМ выступает универсальная вычислительная машина, на которую дополнительно возлагается задача загрузки программ и данных в КМП. Кроме того, такая загрузка может производиться и напрямую с устройств ввода/вывода, например с магнитных дисков. После загрузки КМП приступает к выполнению программы, транслируя в МПЭ по широковещательной шине соответствующие SIMD-команды.

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

Фронтальная ВМ

Фронтальная ВМ (ФВМ) соединяет матричную SIMD-систему с внешним миром, используя для этого какой-либо из сетевых интерфейсов, например Ethernet, как это имеет место в системе MasPar МР-1. Фронтальная ВМ работает под управлением операционной системы, чаще всего UNIX-подобной. На ФВМ пользователи подготавливают, компилируют и отлаживают свои программы. Перед выполнением программы сначала загружаются из фронтальной ВМ в контроллер массива процессорных элементов, который исполняет последовательную часть программы и распределяет распараллеленные команды и данные по процессорным элементам массива. В некоторых ВС при создании, компиляции и отладке программ КМП и фронтальная ВМ используются совместно.
На роль ФВМ подходят различные вычислительные машины. Так, в системе СМ-2 в этом качестве выступает рабочая станция SUN-4, а в системе MasPar - DECstation 3000.

Контроллер массива процессорных элементов

Контроллер массива процессорных элементов выполняет последовательный программный код, реализует команды ветвления программы, транслирует команды и сигналы управления в процессорные элементы.
При загрузке из ФВМ программа через интерфейс ввода/вывода заносится в оперативное запоминающее устройство контроллера массива процессорных элементов (ОЗУ КМП). Команды для процессорных элементов и глобальная маска, формируемая на этапе компиляции, также через интерфейс ввода/вывода загружаются в ОЗУ команд и глобальной маски (ОЗУ КГМ). Затем контроллер начинает выполнять программу, извлекая либо одну скалярную команду из ОЗУ КМП, либо множественные команды из ОЗУ КГМ. Скалярные команды - команды, осуществляющие операции над хранящимися в КМП скалярными данными, выполняются центральным процессором (ЦП) контроллера. В свою очередь, команды, оперирующие параллельными переменными, хранящимися в каждом ПЭ, преобразуются в блоке выборки команд в более простые единицы выполнения - нанокоманды. Нанокоманды совместно с маской пересылаются через шину команд для ПЭ на исполнение в массив процессорных элементов. Например, команда сложения 32-разрядных слов в КМП системы МРР преобразуется в 32 нанокоманды одноразрядного сложения, которые каждым ПЭ обрабатываются последовательно.
В большинстве алгоритмов дальнейший порядок вычислений зависит от результатов и/или флагов предшествующих операций. Для обеспечения такого режима в матричных системах статусная информация, хранящаяся в процессорных элементах, должна быть собрана в единое слово и передана в КМП для выработки решения о ветвлении программы. Например, в предложении IF ALL (условие A) THEN DO В оператор В будет выполнен, если условие А справедливо во всех ПЭ. Для корректного включения/отключения процессорных элементов КМП должен знать результат проверки условия А во всех ПЭ. Такая информация передается в КМП по однонаправленной шине результата. В системе СМ-2 эта шина названа GLOBAL. В системе МРР для той же цели организована структура, называемая деревом SUM-OR. Каждый ПЭ помещает содержимое своего одноразрядного регистра признака на входы дерева, которое с помощью операции логического сложения комбинирует эту информацию и формирует слово результата, используемое в КМП для принятия решения.

Массив процессорных элементов

В матричных SIMD-системах распространение получили два основных типа архитектурной организации массива процессорных элементов.
В первом варианте, известном как архитектура типа «процессорный элемент-процессорный элемент» («ПЭ-ПЭ»), N процессорных элементов (ПЭ) связаны между собой коммуникационной сетью. Каждый ПЭ - это процессор с локальной памятью. Процессорные элементы выполняют команды, получаемые из КМП по шине широковещательной рассылки, и обрабатывают данные, как хранящиеся в их локальной памяти так и поступающие из КМП. Обмен данными между процессорными элементами производится по коммуникационной сети, в то время как шина ввода/вывода служит для обмена информацией между ПЭ и устройствами ввода/вывода. Для трансляции результатов из отдельных ПЭ в контроллер массива процессорных элементов служит шина результата. Благодаря использованию локальной памяти аппаратные средства ВС рассматриваемого типа могут быть построены весьма эффективно. Во многих алгоритмах действия по пересылке информации по большей части локальны, то есть происходят между ближайшими соседями. По этой причине архитектура, где каждый ПЭ связан только с соседними, очень популярна. В качестве примеров вычислительных систем с рассматриваемой архитектурой можно упомянуть MasPar МР-1, Connection Machine СМ-2, GF11, DAP, МРР, STARAN, PEPE, ILLIAC IV.

Второй вид архитектуры - «процессор-память». В такой конфигурации двунаправленная сеть соединений связывает N процессоров с М модулями памяти. Процессоры управляются КМП через широковещательную шину.
Обмен данными между процессорами осуществляется как через сеть, так и через модули памяти. Пересылка данных между модулями памяти и устройствами ввода/вывода обеспечивается шиной ввода/вывода. Для передачи данных из конкретного модуля памяти в КМП служит шина результата. Примерами ВС с такой архитектурой могут служить Burroughs Scientific Processor (BSP), Texas Reconfigurable Array Computer TRAC.

Структура процессорного элемента

В большинстве матричных SIMD-систем в качестве процессорных элементов применяются простые RISC-процессоры с локальной памятью ограниченной емкости. Например, каждый ПЭ системы MasPar МР-1 состоит из четырехразрядного процессора с памятью емкостью 64 Кбайт. В системе МРР используются одноразрядные процессоры с памятью 1 Кбит каждый, а в СМ-2 процессорный элемент представляет собой одноразрядный процессор с 64 Кбит локальной памяти. Благодаря простоте ПЭ массив может быть реализован в виде одной сверхбольшой интегральной микросхемы (СБИС). Это позволяет сократить число связей между микросхемами и, следовательно, габариты ВС. Так, одна СБИС в системе СМ-2 содержит 16 процессоров (без блоков памяти), а в системе MasPar МР-1 СБИС состоит из 32 процессоров (также без блоков памяти). В системе МР-2 просматривается тенденция к применению более сложных микросхем, в частности 32-разрядных процессоров с 256 Кбайт памяти в каждом.

Неотъемлемыми компонентами ПЭ в большинстве вычислительных систем являются:

арифметико-логическое устройство (АЛУ);
регистры данных;
сетевой интерфейс (СИ), который может включать в свой состав регистры пересылки данных;
номер процессора;
регистр флага разрешения маскирования (F);
локальная память.

Процессорные элементы, управляемые командами, поступающими по широковещательной шине из КМП, могут выбирать данные из своей локальной памяти и регистров, обрабатывать их в АЛУ и сохранять результаты в регистрах и локальной памяти. ПЭ могут также обрабатывать те данные, которые поступают по шине широковещательной рассылки из КМП. Кроме того, каждый процессорный элемент вправе получать данные из других ПЭ и отправлять их в другие ПЭ по коммуникационной сети, используя для этого свой сетевой интерфейс. В некоторых матричных системах, в частности в MasPar МР-1, элемент данных из ПЭ-источника можно передавать в ПЭ-приемник непосредственно, в то время как в других, например в МРР, - данные предварительно должны быть помещены в специальный регистр пересылки данных, входящий в состав сетевого интерфейса. Пересылка данных между ПЭ и устройствами ввода/вывода осуществляется через шину ввода/вывода ВС. В ряде систем (MasPar МР-1) ПЭ подключены к шине ввода/вывода посредством сети соединений и канала ввода/вывода системы. Результаты вычислений любое ПЭ выдает в КМП через шину результата.

Каждому из N ПЭ в массиве процессоров присваивается уникальный номер, называемый также адресом ПЭ, который представляет собой целое число от 0 до N-1. Чтобы указать, должен ли данный ПЭ участвовать в общей операции, в процессорном элементе имеется регистр флага разрешения F. Состояние этого регистра может быть изменено сигналами управления из КМП либо по результатам операций в самом ПЭ.
Еще одной существенной характеристикой матричной системы является способ синхронизации работы ПЭ. Так как все ПЭ получают и выполняют команды одновременно, их работа жестко синхронизируется. Это особенно важно в операциях пересылки информации между ПЭ. В системах, где обмен производится с четырьмя соседними ПЭ, передача информации осуществляется в режиме «регистр-регистр».

Подключение и отключение процессорных элементов

В процессе вычислений в ряде операций должны участвовать только определенные ПЭ, в то время как остальные ПЭ остаются бездействующими. Разрешение и запрет работы ПЭ могут исходить от контроллера массива процессорных элементов (глобальное маскирование) и реализуются с помощью схем маскирования ПЭ. В этом случае решение о необходимости маскирования принимается на этапе компиляции кода. Решение о маскировании может также приниматься во время выполнения программы (маскирование, определяемое данными), при этом опираются на хранящийся в ПЭ флаг разрешения маскирования F.
При маскировании, определяемом данными, каждый ПЭ самостоятельно объявляет свой статус «подключен/не подключен». В составе системы команд имеются наборы маскируемых и немаскируемых команд. Маскируемые команды выполняются в зависимости от состояния флага F, в то время как немаскируемые команды этот флаг просто игнорируют.
При использовании схемы глобального маскирования контроллер массива процессорных элементов вместе с командами посылает во все ПЭ глобальную маску. Каждый ПЭ декодирует эту маску и выясняет, должен ли он выполнять данную команду или нет.
В зависимости от способа кодирования маски существует несколько различных схем глобального маскирования. В схеме, примененной в вычислительной системе ILLIAC IV с 64 64-разрядными ПЭ, маска представляет собой N-разрядный вектор. Каждый бит вектора отражает состояние одного ПЭ. Если бит содержит единицу, соответствующий ПЭ будет активным, в противном случае - пассивным. Несмотря на свою универсальность, при больших значениях N схема становится неудобной. В варианте маскирования с адресом ПЭ используется 2m-разрядная маска (m = log₂N), в которой каждая позиция соответствует одному разряду в двоичном представлении адреса ПЭ. Каждая позиция может содержать 0, 1 или X. Таким образом, маска состоит из 2m битов. Если для всех i (0 ≤ i < m) i-я позиция в маске и i-я позиция в адресе ПЭ совпадают или в i-й позиции маски стоит X, ПЭ будет активным. Например, маска 000X1 представляет процессорные элементы с номерами 1 и 3, в то время как маска ХХХХ0 представляет все ПЭ с четными номерами (все это для массива из 32 ПЭ). Здесь можно активизировать только подмножество из всех возможных комбинаций процессорных элементов массива, что на практике не является ограничением, так как в реальных алгоритмах обычно участвуют не произвольные ПЭ, а лишь расположенные регулярным образом.
Глобальные и локальные схемы маскирования могут комбинироваться. В таком случае активность ПЭ в равной мере определяется как флагом F, так и глобальной маской.

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

Эффективность сетей взаимосвязей процессорных элементов во многом определяет возможную производительность всей матричной системы. Применение находят самые разнообразные топологии сетей.
Поскольку процессорные элементы в матричных системах функционируют синхронно, обмениваться информацией они также должны по согласованной схеме, причем необходимо обеспечить возможность синхронной передачи от нескольких ПЭ-источников к одному ПЭ-приемнику. Когда для передачи информации в сетевом интерфейсе задействуется только один регистр пересылки данных, это может привести к потере данных, поэтому в ряде ВС для предотвращения подобной ситуации предусмотрены специальные механизмы. Так, в системе СМ-2 используется оборудование, объединяющее сообщения, поступившие к одному ПЭ. Объединение реализуется за счет операций арифметического и логического сложения, наложения записей, нахождения меньшего и большего из двух значений. В некоторых SIMD-системах, например МР-1, имеется возможность записать одновременно пришедшие сообщения в разные ячейки локальной памяти.
Хотя пересылки данных по сети инициируются только активными ПЭ, пассивные процессорные элементы также вносят вклад в эти операции. Если активный ПЭ инициирует чтение из другого ПЭ, операция выполняется вне зависимости от статуса ПЭ, из которого считывается информация. То же самое происходит и при записи.

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

Ввод/вывод

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

Литература

Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов / С.А. Орлов, Б.Я. Цилькер. - СПб.: Питер, 2011. - 688 с.

Ключевые термины, связанные с термином "Матричные вычислительные системы":

Литература

Основная:

Цилькер Б.Я. Организация ЭВМ и систем : Учебник для вузов / Б.Я. Цилькер, С.А. Орлов. - 2-е изд. - СПб.: Питер, 2011. - 688 с. - ISBN 978-5-49807-862-5.

Ключевые термины (головные): Архитектура вычислительной машины; Классификация Флинна; SIMD-архитектура; Векторные вычислительные системы;

Федотов Анатолий Михайлович

НГУ
ФИТ НГУ
ИВТ СО РАН

© 1998-2024, Новосибирский государственный университет, Новосибирск
© 1998-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2024, Федотов А.М.
Дата последней модификации: 18.11.2013