Матричная вычислительная система Советский патент 1990 года по МПК G06F15/80 

ОУ о

00

Ы

3

Изобретение относится к вычислительной технике, в частности к многпроцессорным вычислительным система

Цель изобретения - увеличение бы родействия системы за счет упрощени межпроцессорного обмена.

На фиг.1 представлена схема матричной вычистательной системы; на фиг.2 - схема вычислительного устройства; на фиг.З - схема узла синхронизации; на фиг.4 - формат адресной команды вычислительного устройства; на фиг.З и 6 - форматы адресной части команд обращения к запоминающим устройствам соответственно с циклом записи и циклом чтения.

Матричная вычислительная система содержит вычислительные устройства 1, запоминающие устройства 2, первый 3 и второй 4 элементы И.

Каждое вычислительное устройство 1 содержит формирователь 5 синхроимпульсов, узел 6 обр аботки, узел 7 синхронизации, узел 8 формирования , маски, дешифратор 9, raiHHbw фopмирователь 10.

Узел 7 синхронизации содержит эле мент НЕ 11, первый 12 и второй 13 триггеры, первый 14 и второй 15 элементы И, третий четвертый 17 триггеры, первый 18 и второй 19 элементы И-НЕ, элемент ИЛИ 20.

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

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

Относительный номер п;- j-ro вы

числительного устройства 1 (j, j) .матрицы в системе нумерации i-ro вычислительного устройства 1 (i, i) матрицы определяется из соотношения

п - i + j

j - i

при при

(1)

0

5

0

5

0

5

0

При записи информации i-м вычислительным устройством системы в запоминающие устройства адресная часть команды записи определяется из соотношения

и

ч

где В

2 (2 1,

п

,

n;j

2 Ъ + ti

(2)

2,

oiесли осуществляется запись операнда в запоминающее устройство 2 (i, j), ,если запись операнда в запоминающее устройство 2 (i, j) не производится номер ячейки запоминающего устройства, в которую производится запись операнда. При чтении информации i-м вычислительным устройством из ячейки с номером об- запоминающего устройства 2 (j, i) адресная часть команды опреде из соотношения

ляется

AIJ

Узел

.

п

- 1) +. (3)

7 синхронизации предназначен для формирования сигналов Блокировка записи и Блокировка чте-;, ния, длительности положительной фазы синхроимпульсов, для фиксации сигналов Готовность обмена и Конец обмена.

Узел 8 формирования маски предназначен для инвертирования и передачи значений р+1,р+2,...,р+ + п + 1 разрядов,адреса выборки соответствующих запоминающих устройств в режиме записи информации.

Работу системы рассмотрим на примере решения на ней методом простых 5 итераций системы линейных уравнений вида

0

где В

b6R

р

X ВХ +. Ь;(4)

- заданная числовая квадратная матрица т-го порядка; - заданный вектор (свободный

член).

Итерационная последовательность векторов имеет вид

k-t ВХ +

Ь.

(5)

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

п

X X

1 t

1 1

; + ь3- - числовая матрица размерносгя; ™ i;xm;

Ъ:СК - заданный вектор (свободньй член)

JV1

Чтение операнда из запоминающего устройства может осуществляться под управлением любой арифметико-логической адресной команды. Например, при выполнении оператора сложения ADD MA (j, i) + A j-e вычислительное устройство складывает содержимое своего аккумулятора с содержимым А-и ячейки запоминающего устройства 2(1, J) и результат помещается в аккумулятор.

С выхода формирователя 5 синхроимпульсов синхроимпульсы поступают на тактовьй вход узла 7 синхронизации. Если в вьшолняемой операции нет обращения к запоминающим устройствам, то синхроимпульс, пройдя по цепям узла синхронизации, подается на вход

синхронизации узла 6 обработки.

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

адресной части команды.

Содержимое аккумулятора с информационного входа-выхода, и адрес с выхода адреса i-r.o вычислительного устройства поступают соответственно на информационные входы и на первые адресные входы всех запоминающих устройств i-й строки матрицы. Каждый из разрядов инвертированного кода маски подается на второй вход записи-чтения соответствующего запоминающего устройства в i-й строке матрицы. В те запоминающие устройства, на вторые входы записи-чтения которых будет подан логический нуль (активный уровень выборки), произойдет запись содержимого аккумулятора. Это позволяет в одном мащИнном цикле всем вычислительным устройствам системы обменяться одним операндом. После загрузки компонент вектора каждое вычислительное устройство выполняет оператор POST1, который является сигна-v лом систем о том, что запись информации данным, .вычислительным устройством в запоминающее устройство за вершена. Параллельно с процессом чтения из запоминающих устройств осуществляется аппаратный анализ состояния запоминаюш;их устройств системы и в случае неготовности запоминающих

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

В цикле выполнения операции POST1 каждое вычислительное устройство системы вьграбатывает сигнал Конец обмена уровня логической единицы, который фиксируется триггером в узле синхронизации и вьдается на выход признака конца обмена вычислительно-т го устройства, с которого он подается на один из входов элемента И 4. За оператором POST1 может сразу последовать оператор с циклом чтения из запоминающих устройств. В общем случае сигнал Конец обмена вырабатывается вычислительными устройствами не одновременно, поэтому все вычислительные устройства, которые начали цикл чтения из запоминающих устройств до выработки последним вычислительным устройством сигнала Конец обмена, перейдут в режим ожидания. С приходом последнего сигнала Конец обмена на выходе элемента И 4 вырабатывается сигнал Разрешение системного чтения который поступает на вход признака Разрешение системного чтения всех вычислительных устройств системы, разблокирует прохождение отрицатель- ной фазы синхроимпульсов, находящихся в режиме ожидания вычислительных устройств, давая тем самым им возможность завершить чтение первой компоненты вектора и продолжить функционирование.

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

LD MA(j, i) + А

Допустим, что на первой итерации выполняется условие |fx - Х /|, тогда вновь вычисленные компоненты вектора X заменяют в локальной памяти вычислительного устройства компоненты вектора Х°. Далее каждое вычислительное устройство выполняет операцию POST2, по завершении которой на выходе признака Готовность обмена устанавливается уровень логической единицы, который поступает на соответствующий вход элемента И 3. После исполнения всеми вычислительными

устройствами операции POST2 на выходе элемента И 3 вырабатывается сигнал, который подается на вход призна- ка разрешения системной записи всех вьиислительных устройств. Далее может вьшолняться оператор ST МА (i, J1,...,je) записи в запоминающие устройства.

QЕсли даже одно из вычислительных

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

сигналы Блокировка записи, Конец обмена, фиксирует сигналы Готовность обмена, Конец обмена, вырабатываемые в узле 6 обработки, и уп- 30 равляет длительностью синхроимпульсов, которые первоначально формируются в формирователе 5 синхроимпульсов,

В процессе начальной установки триггеры 16 и 17 устанавливаются в единичное состояние, а триггеры 12 и -13 - в нулевое состояние.

Триггер 16 предназначен для фиксации сигнала Конец обмена уровня логической единицы, которьш формируется узлом обработки в цикпе исполнения инструкции POST1 и подается на четвертый вход режима узла синхрони- зации и далее на информационный вход триггера 16, устанавливая его в единичное состояние. Эта единица подается на соответствуюший вход элемента И 4. По приходу единичных сигналов со всех процессоров на выходе элемента И 4 вырабатывается сигнал, который поступая на вход признака разрешения системного-чтения вычислительных устройств и далее на информационные входы всех триггеров 13, переводит их в единичное состояние, триггеры 17 .устанавливает в нулевое состояние. 5 Установка даже одного из триггеров 17 в нулевое состояние устанавливает на вых оде элемента И 3 нулевой уровень, который переводит триггеры

35

40

45

0

HOi;

верно щи си

нения

12 всех вычислительных устройств в HyjieBoe состояние.

Триггер 17 предназначен для фик- сарш сигнала Готовность обмена

овня логической единицы, который формируется узлом обработки в цикле олнения инструкции POST2 и пода- я на третий вход режима узла синх- ро|низации и далее устанавливает триг- )о 17 в единичное состояние. По при-, единичных сигналов со всех вычис- ельных устройств на выходе злемен- И 3 вырабатывается сигнал, поступая -на вход признака разрешения15 си;темной записи всех и далее на информационные входы всех триггеров переводит их в единичное (исход- ) состояние, а триггеры 16 уста-;

в нулевое состояние. При. 20 ановке любого-из триггеров 16 €улевое состояние на выходе элемен- И 3 устанавливается нулевой уро- и триггеры 13 всех вычислитель- :: устройств устанавливаются в нуле- 25 состояние. Состояние триггеров 13, 16 и 17, фиксируемое инст- сцией POST2 и начальной установкой, обращение только для запи-. информации в запоминающие устрой- ЗО , и-оБращенне для чтения информа- из них при таком состоянии тригпереводит вычислительное устрой- в режим ожидания. Противополож- их состояние, фиксируемое инст- ру(сцией POST1, разрешает соответст- чтение информации с запоминаю- устройств, и обращение для запи- информации в них переводит вьиис- ельное устройство в режим ожидания В узле 6 обработки в цикле выполлюбой адресной инструкции на адресном выходе устанавливается

п + 1) - разрядное значение ад-, рее ной части исполняемой команды. Ес- при этом происходит обращение, значение старшего разряда адреса + п) принимает значение, равное

Если адресной командой явля- команда записи информации в па- , то на информационном выходеустанавпивается операнд. Единица устанавливается на выпризнака конца обмена в цикле вьи олнения инструкции POST1 и на выпризнака готовности обмена в выполнения инструкции POST2.

значение сигнала, поступаю- на вход синхронизации узла 8 фор

ет

ге

ли

та

13

но

набивает

ус

в

та

вейь

ны

во

12

ру:

допускает

си

CTfea

ции

35

.ГГГ

то c(i

ед1 нице, ется мять вхсде

хор е

Нулевое

щего

45

50

)о 15

20 5 О

5

5

0

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

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

Выполнение каждой микроинструкции начинается с формирования синхроимпульса формирователем 5 синхроимпульсов, с выхода которого синхроимпульс поступает на тактовый вход узла 7 синхронизации. Положительная фаза синхроимпульса поступает на один из входов элемента ИЛИ 20 и далее положительная фаза синхроимпульса поступает на вход узла 6 обработки.

После окончания начальной установки, когда каждое вычислительное устройство приступает к осуществлению первого шага итерации, первой опера-, цией обмена является инструкция ST МА (i, j1,...,je) + А, при выполнении которой во время действия положительной фазы синхроимпульса обеспечивается передача операнда с информационного выхода узла 6 обработки на информационный вход-выход вычислительного устройства. Сигнал с первого выхода узла синхронизации принимает нулевое значение,что обеспечивает за-, пись операнда в соответствии с адресом на выходе адреса вычислительного блока в соответству-.ош1-1е запоминающие устройства.

По завершении операции записи в запоминающие устройства вычислительным блоком исполняется инструкция POST1, в цикле выполнения которой устанавливается единица на выходе признака конца обмена узла обработки которая устанавливает триггер 17 в единичное состояние.

После выполнения вычислительным устройством инструкции POST1 инструкция ST МА (i, J1,,je)+

+А становится запрещенной для него, так как может заблокировать подачу синхроимпульсов на узел обработки без возможности снятия этой блокировки. Зафиксированный триггером 16 сигнал Конец обмена единичного уровня поступает на один из входов элемента И 3, на другие входы которого посту- - пают аналогичные сигналы от других вычислительных устройств. Так как различные вычислительные устройства вырабатывают такие сигналы не одновременно, то процедура исполнения любой инструкции с циклом чтения ийформации из.запоминающего устройства зависит от состояния выходов элементов И 3 и И А.

Рассмотрим выполнение инструкции LD MA(j, i) + А при условии, что на

один из входов элемента И 4 поступает нулевой сигнал, и, следовательно, системный сигнал Разрешение системного чтения имеет нулевое значение. Во время действия положительной фазы синхроимпульса выход старшего разряда адреса и выход признака записи- чтения узла обработки устанавливаются в единичное состояние. Сочетание этих сигналов обеспечивает передачу операнда с информационного входа-выхода вычислительного устройства на информационный вход узла обработки с помощью шинного формирователя 10, Сигнал, формируемый элементом И 14, принимает при этом нулевое значение, а сигнал с выхода элемента И 15 принимает значение, равное единице, которое заблокирует прохождение отрицательной фазы синхроимпульсов на вход синхронизации узла обработки, до тех пор, пока триггер 13 не будет установлен в единичное состояние, Единица на выходе элемента И 4 устанавливается после исполнения последним вычислительным устройством инструкции POST1,;

Сигнал с входа элемента И 4 поступает на информационные входы триггеров 13 всех вычислительных устройств, устанавливает их в единичное состояние и переводит триггеры 17 в нулевое состояние, что влечет за со- бой установку триггеров 12 в нулевое состояние, С этого момента дешифратор 9 выбирает заданное запоминающее устройство из соответствующего столбца матрицы, считанный с него операнд постзшает через шинный формирователь 10 на информационный вход узла обработки. Отрицательная фаза синхроимпульса на входе синхрониза-: ции узла обработки фиксирует операнд, в аккумуляторе узла обработки,.На этом выполнение операции завершается с

После завершения чтения необходимых операндов выполняется инструкция POST2, в цикле выполнения которой устанавливается единица на выходе признака готовности обмена узла обработки, которая устанавливает триггер 17 в единичное состояние. После исполнения вычислительным устройством инструкции POST2 любая инструкция с циклом чтения из запоминающих устройств становится запре- щенной для него , так как может заблокировать подачу синхрошшульсов на узел обработки без возможности снятия этой блокировки. Таким образом, триггер 17 фиксирует сигнал Готов- IQ ность обмена,; который с его выхода пос тупает на один из входов элемента И 3, на другие входы которого поступают аналогичные сигналы от других вычислительных устройств систе1.1ы. 15 Выработка сигналов Готовность обме- на различными вычислительными устройствами может происходить не одновременно, а потому процесс исполнения инструкции ST MA(i, J1,..,,je)+ 20 А, которая может последовать после операции POST2, зависит от состояния выходов элементов И 3 и 4, Рассмотрим ее исполнение при условии, что на один из входов элемента И 3 поступает нулевой сигнал, а сигнал на выходе элемента И 3 имеет еще нулевое значение.

При данном условии вычислительное устройство переводится в режим ожи- 0 Дания и блокируется прохождение маски через узел 8, задерживая запись с информационного входа-выхода вычислительного устройства операнда в запоминающие устройства, с которых к этому моменту может быть не считана информация, записанная на предыдущем шаге итерации. Как только сигнал на выходе элемента И 3 устанавливается в единицу, устанавливаются 0 в единичное состояние триггеры 12 всех вычислительных устройств, триггеры 16 устанавливаются в нулевое состояние, что влечет за собой сброс в нулевое состояние триггеров 13 5 всех вычислительных устройств.

Формула изобретения

1, Матричная вычислительная сис- Q тема, содержащая матрицу вычислительных устройств и запоминающих устройств размером пхп, причем в узлах главной диагонали которой находятся вычислительные устройства, а в остальных узлах матрицы находятся запоминающие устройства, о т л и ч а- ю щ а я с я тем, что, с целью увеличения быстродействия системы за счет упрощения межпроцессорного обмена, она содержит первый и второй элементы И, причем информационный вхоц-вькод i-ro вычислительного устройства (где i 1,...,п) подключен к выходам запоминающих устройств i-ro столбца; матрицы и к информационным входам запоминающих устройств i-й строки матрицы выхода адреса i-ro вычислительного устройства подключен к первым адресным входам за - поминаюр их устройств i-й строки матрицы и к вторым адресным входам запоминающих устройств i-ro столбца матрицы, выход адреса первого вычислительного устройства подключен к первым адресным входам запоминающих устройств первой строки матрицы и к вторым адресным входам запоминающих устройств первого столбца матрицы, выкод адреса п-го вычислительного устройства подключен к первым адрес- HbiN входам запоминающих устройств n-f строки матрицы и к вторым адрес- ньп входам запоминающих устройств п-го столбца матрицы, выход выборки Kai-ала чтения i-ro вычислительного устройства подключен к первым вхо- дa чтения-записи запоминающих устройств i-ro столбца матрицы, выход маски i-ro вычислительного устройства подключен к вторым входам чтения- загиси запоминаюБдих устройств i-и строки матрицы, выходы признака го- TOIности обмена вычислительных уст- pofcTB подключены к входам первого элемента И, выход которого подклю- 4ef к входам признака разрешения .си записи всех вычислительных устройств, выходы признака конца которых подключены к входам втсрого элемента И, выход, которого по;,ключен к входам признака разрешение системного чтения всех вычисли- rej ьных устройств.

2, Система по п.1, о т л и ч а- iu ц а я с я тем, что вычислительно устройство содержит формирователь

5

0

5

0

5

0

5

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

В о

Изобретение относится к вычислительной технике и, в частности, к многопроцессорным вычислительным системам. Цель изобретения - увеличение быстродействия за счет упрощения межпроцессорного обмена. Матричная вычислительная система содержит матрицу вычислительных устройств и запоминающих устройств размеров N^.N. В узлах главной диагонали матрицы находятся вычислительные устройства 1, а в ее остальных узлах - запоминающие устройства 2. 1 з.п. ф-лы, 6 ил.

18

12

Iff

п

15

LP

13

Фиг.2

-о

16

/7

Фиг.З

N-1

ч/

Код операции

P+nP- П 1

Признан оЦращения

к запоминающему

устройству

шиэнак обращения л запоминающим устройствам

МР

7 Q

Не испольэобанш Номер Адрес ячейки

запоминающего .оустройства

P-1P

1 0

Адресная часть Фиг.

Р

1 О

/ V

Адрес ячейми

запоминающего

устройстда

МР

7 Q