Процессорные матрицы

Понятие "процессорная матрица" подчеркивает тот факт, что параллельные операции выполняются группой одинаковых ПЭ, объединенных коммутационной сетью и управляемых единым ЦУУ, реализующим единственную программу. Следовательно, ПМ являются представителями класса ОКМД-ЭВМ. Процессорная матрица может быть присоединена в качестве сопроцессора к БМ. В данном случае БМ обеспечивает ввод-вывод данных, управление графиком работы ПМ, трансляцию, редактирование программ и некоторые другие вспомогательные операции. В отдельных случаях все эти функции выполняет ЦУУ. Процессорные матрицы описаны в литературе (см. приложение).

Рис. 2.32 Схема ПМ.

Каждый ПЭ может иметь или не иметь собственную (локальную) память. Известно, что более половины обращений за информацией приходится на долю локальной памяти, поэтому в таких системах к быстродействию коммутатора предъявляются относительно низкие требования. Схема ПМ с локальной памятью приведена на рис. 2.32. Центральное устройство управления является полноценным процессором для выполнения единственной программы, однако в этой программе используются команды двух типов: скалярные и векторные. Скалярные команды начинаются и заканчиваются в ЦУУ, векторные команды начинаются в ЦУУ, а продолжаются в ПП.

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

Центральное устройство управления связано с ПП тремя магистралями:

1. по магистрали данных МД из ЦУУ в ПП передаются общие адреса и данные, а из отдельных ПЭ в ЦУУ проводится выборка необходимых единиц информации;
2. по системной магистрали СМ, которая имеет одну шину на каждый ПЭ, в ПП передается (или из ПП считывается) вектор активности процессорных элементов;
3. по магистрали управления МУ из ЦУУ всем ПЭ передаются одни и те же микрокоманды для одновременного исполнения.

Как в ЦУУ, так и в ПЭ имеются регистры РОН, поэтому форматы и типы скалярных и векторных команд такие же, как и в последовательных ЭВМ: регистр - регистр (RR), регистр - память (RX) и др.

Векторные команды можно разделить на пять основных групп: арифметико-логические команды; команды пересылки между ЦУУ и ПП; команды коммутации; команды групповых условных переходов; команды активации процессорных элементов.

Рассмотрим функционирование ПП при выполнении команд этих групп. Пусть имеется следующий фрагмент программы:

1 S ЧТ 5, A1
2 V ПС 5, 3
3 V ЧТ 2, A2
4 V УМН 2, 3

Здесь S и V - скалярная и векторная команды соответственно.

По команде 1 в ЦУУ из локальной ОП (адрес А1) считывается константа Z1 и записывается в регистр 5. По команде 2 константа Z1 из регистра 5 ЦУУ передается в регистр 3 всех ПЭ по МД. По команде 3 все ПЭ считывают из локальной памяти (адрес A 2) константу Z 2 и помещают в регистр 2. Наконец, по команде 4 все ПЭ умножают содержимое регистров 2 и 3 и результат помещают в регистр 2, т.е. выполняется операция умножения на константу, которую на фортраноподобном векторном языке можно записать так:

Z (*) = Z1 * Z2 (*)

Рассмотрим подробнее выполнение векторной команды 3 на микропрограммном уровне (табл. 2.3).

Таблица 2.3.

Выполнение векторной команды обращения к локальной памяти по тактам

Из таблицы следует, что все микрокоманды генерируются в УУ ЦУУ, однако для команды векторного типа некоторые микрооперации выполняются не в ЦУУ, а в ПП (микрокоманды 4...8). При этом управление производится выборочно различными блоками ПЭi и (как будет далее показано) коммутатором. В ПП все ПЭi выполняют одну и ту же микрооперацию. Рассмотрение этой микропрограммы позволяет оценить разрядность МУ и МД.

Для большинства ЭВМ магистраль МД имеет 32...64 разряда, а магистраль МУ - 30...80 разрядов; разрядность магистрали СМ равна числу ПЭ.

Как и для конвейерных ЭВМ, в ЦУУ для повышения быстродействия обычно применяется совмещение операций. Например, при выполнении микрокоманд 4...8 для команды Kj производится выполнение микрокоманд 1...3 для следующей команды K (j + 1).

Совмещение может быть применено и в процессорных элементах.

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

Первый уровень активации - реконфигурация - позволяет отключать ненужные или неисправные ПЭ на период выполнения нескольких задач и дает возможность проводить вычисления при наличии неисправных ПЭ. Триггер конфигурации имеется в каждом ПЭ. После выполнения тестовых программ процессорного поля в триггеры конфигурации исправных ПЭ из ЦУУ по СМ заносятся единицы, а в триггеры неисправных ПЭ - нули.

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

Кроме триггера конфигурации в каждом ПЭ есть несколько (до 16) триггеров активации. Триггер основной активности A0 управляет активностью ПЭ: если A0 находится в состоянии 1, то данный ПЭ активен, если в состоянии 0 - пассивен. Вспомогательные триггеры A1...A7 запоминают активность ПЭ перед раз-личными внутренними циклами, если эта активность меняется; после выхода из цикла нужно восстановить исходное значение активности. Триггеры A8...A15 отражают результат вычислений, проводимых в ПЭ: A8 - равенство результата нулю; A9 - знак результата; A10 - перенос; A11 - арифметическое переполне-ние; A12 - исчезновение порядка; A13 - переполнение порядка; A14 - некорректное деление; A15 - служебный триггер.

Активация бывает внешней и внутренней. В первом случае состояние триггеров активности каждого ПЭ устанавливается со стороны ЦУУ по СМ с помощью команд вида V ВША Ri, Aj. Здесь код ВША означает, что выполняется команда внешней активации, по которой содержимое 16 разрядов регистра Ri ЦУУ поразрядно записывается во всех ПЭ в регистры активации с номером j. Если j = 0, то это означает, что производится загрузка триг-геров основной активности, которая может привести к выключению некоторых ПЭ, когда в соответствующих разрядах находятся нули.

Команда V ЧТА Ri, Aj выполняет обратную операцию: счи-тывание состояния триггеров активации в разряды регистра Ri ЦУУ.

Коммутатор в ПП (см. рис. 2.32) может управляться командами двух типов:

V КМ1 Ri, Rj, Rk, F
V КМ2 Ri, Пk, F (2.3)

Команда коммутации КМ1 передает содержимое регистров Ri всех ПЭ в регистры Rk других ПЭ в соответствии с вектором адре-сов (номеров ПЭ-приемников), каждый элемент которого распо-ложен в регистре Rj данного ПЭ. При выполнении команды содержимое Ri и Rj передается в коммутатор, прокладывающий по адресу из Rj нужный маршрут и затем передающий информацию из Ri.

Детальный алгоритм выполнения команды коммутации зависит от типа используемого коммутатора.

Функция F в команде КМ1 указывает на разновидность ко-манды: запись или считывание данных. В случае считывания тре-буется обеспечить еще и обратную передачу информации.

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

Команды коммутации с адресным вектором используются там, где заранее не известен вид перестановки, т. е. при обработке сложных структур данных (графов, деревьев, таблиц и т. д.).

Однако не всякий коммутатор пригоден для эффективной реализации команд типа КМ1. Такой коммутатор должен допускать работу в асинхронном режиме, внутренними средствами разрешать конфликты, если они возникают. Время передачи пакета случайных связей должно находиться в допустимых пределах. Назовем подобный коммутатор универсальным (УК). Для небольших размеров ПП (N = 16...32) в качестве УК может использоваться полный координатный переключатель, а для N > 32 должны использоваться, многокаскадные ком-мутаторы.

В УК изменение конфигурации путем разделения ПП на независимые части или по причине неисправностей процессоров не вызывает трудностей, так как для продолжения решения задачи необходимо только переустановить адресные таблицы. Это обеспечивает повышенную живучесть ПП. В машинах с реконфигурацией число ПЭ задается как параметр. Это означает, что в библиотеках стандартных программ число процессоров не определено и конкретизируется в процессе трансляции пользователем или ОС. В синхронных же сдвиговых коммутаторах типа двумерной среды в ILLIAC-IV выход из строя одного узла разрушает всю систему сдвигов.

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

Команда типа КМ2 означает, что на коммутатор из ЦУУ через МД передается код перестановки Пk, в соответствии с которым настраивается коммутатор и производится бесконфликтная передача информации из регистров Ri или считывание через коммутатор в регистры Ri. Команда КМ2 может выполняться как на универсальных, так и на синхронных коммутаторах для всех видов регулярных перестановок.

Рассмотрим вопросы, связанные с эффективностью вычислений и методами программирования для ПМ, на примерах программирования некоторых операций.

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

Рассмотрим два варианта размещения квадратной матрицы в ПП (рис. 2.33). Предположим, что для решения некоторой задачи, например, умножения матриц, требуется параллельная выборка как строк, так и столбцов. Стандартное, принятое для большинства языков и ЭВМ размещение "по столбцам" (см. рис. 2.33, а) позволяет выбирать в АЛУ из ОП параллельно только строки, а эле-менты столбца расположены в одной ОПi и могут выбираться только последовательно. В результате при таком размещении параллелизм процессорного поля не будет использован в полной мере, поэтому для подобных задач характерно специальное размещение информации. При "скошенном" размещении матрицы (см. рис. 2. 33, б) за один такт могут быть выбраны как строка, так и столбец. Но при выборе столбца должна использоваться "фигурная" выборка, когда каждый ПЭi обращается в ОПi по собст-венному адресу, вычисляемому в зависимости от номера ПЭ.

Рис. 2.33. Размещение матрицы в памяти процессорного поля

Размещение информации влияет и на методы программирова-ния. Рассмотрим операцию сложения двух векторов (рис. 2.34) для L = N и L > N, где L - длина вектора; N - число процессоров. Программы будут выглядеть различно:

Рис. 2.34. Многослойное размещение коротких (а) и длинных (б) векторов

а) V ЧТ 1, Я1 (считывание среза ячеек Я памяти в регистры 1)
V СЛ 1, Я2 (сложение содержимого регистров 1 со срезом ячеек Я2 памяти)
V ЗП 1, Я2 (запись содержимого регистров 1 в срез ячеек Я3 памяти)

б) V ЧТ 1, Я1
V СЛ 1, Я3
V ЗП 1, Я5
V ВША 5, А0 (из регистра 5 ЦУУ передан код активации 1100, что запрещает обращение к ОП3, ОП4)
V ЧТ 1, Я2
V СЛ 1, Я4
V ЗП 1, Я6

Таким образом, несоответствие размеров L и N меняет не только длину, но и состав операторов программы. На программах на параллельных ЯВУ это не отражается: обе программы будут представлены в виде одного и того же оператора

C (*) = A (*) + B (*)

Поскольку наиболее эффективные программы могут быть написаны только на ассемблере, то в языках подобного уровня следует предусматривать средства, позволяющие вне зависимости от соотношения L и N получать одинаковые программы. Так как это не всегда возможно, то из-за необходимости учитывать расположение данных программирование на ассемблере для ПМ становится намного сложнее, чем для последовательных ЭВМ.

Некоторые операции в ПМ программируются проще и выполняются быстрее, чем в параллельных ЭВМ других типов. Например, операция сборки

V = V0 (INDEX (i)), i = 1, 2, ..., n

состоит в том, что из вектора V0 выбираются числа в порядке, указанном в целочисленном массиве INDEX(i) и помещаются в вектор V1. В конвейерной ЭВМ данная операция выполняется в скалярной части (и поэтому медленно). В ПМ операция сборки отображается в одну команду коммутации согласно (2.3):

КМ1 Ri, Rj, Rk, F

Здесь в регистре Ri хранится вектор V0, в регистре Rj - массив INDEX(i), в регистр Rk будет записан вектор V1. Поскольку все операции в команде КМ1 выполняются параллельно, то время выполнения этой команды в простейшем случае (L = N) будет соответствовать одному циклу работы коммутатора.

Для многих параллельных ЭВМ принципиальное значение имеет команда SUM V, т. е. операция суммирования элементов некоторого вектора V. В процессорных матрицах с УК она выполняется в течение нескольких микротактов, которые строятся на основе команды КМ1. В каждом микротакте реализуется следующая операция (работают все ПЭi):

V СЛ Ri, Rj

Здесь операция СЛ выполняется в каждом ПЭl и производит сложение двух чисел, одно из которых расположено в регистре Ri данного ПЭk, а другое - в регистре Ri, но в ПЭl. В регистре Rj процессора ПЭk указан номер процессора ПЭl. Если в регистре Rj процессора ПЭk записан нуль, то этот процессор не производит суммирование, а выборка операнда из него через коммутатор не запрещается.

Операция SUM V для N = 8 (рис. 2.35) выполняется за три такта и для каждого такта по вертикали указано содержимое адресного регистра Rj для любого ПЭ.

Рис. 2.35. Выполнение операции SUM V в ПМ

Для ПМ довольно сложным является выполнение циклов с оператором IF внутри цикла. В примере

DO 5 I = 1, L
IF (X (I) - R) 1, 2, 3
1 Y (I) = (X (I))
GO TO 5
2 Y(I) = (X (I))  (2.4)
GO TO 5
3 Y(I) = (X (I))
5 CONTINUE
STOP

как X, так и Y являются векторами, но Y вычисляется по трем различным формулам в зависимости от значений X(I) и R.

Следовательно, если даже длина векторов X и Y равна числу процессоров, т. е. L = N, то и тогда все три части вектора Y нельзя вычислять одновременно в ПП, так как в нем имеется только одно ЦУУ, а для одновременного вычисления всех элементов Y в (2.4) требуется три ЦУУ. Наиболее простой выход из положения за-ключается в том, что участки f1(X(I)), f2(X(I)), f3(X(I)) вычисляются последовательно в единственном ПП.

Этот метод будет эффективным только в том случае, если функция внутри оператора проста и разбивает всю длину вектора L на сплошные, примыкающие друг к другу участки, длина которых l1,l2,l3>>N.

Наиболее известным представителем процессорных матриц является ЭВМ ILLIAC-IV.

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