Устройство для перемножения матриц

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (g,ic G 06 F 15/347

ГОСУДАРСТВЕ ННЫИ КОМИТЕТ

ПО ИЗОБРЕТЕПИЯМ И ОТКРЫТИЯМ

ПРИ ГКН Г СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

I: /; Ñ

«1 (." (,» ,CG (Д

С (21) 4750967/24 (22) 17.10.89 (46) 15.01.92. Бюл, N. 2 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) P.Âûæèêîâñêèé (PL), Ю.С.Каневский, M.Ê.Êëèìåíêî и С.Г.Овраменко (SU) (53) 681.3(088.8) (56) Авторское свидетельство СССР

¹ 1226484, кл. G 06 F 15/31. 1986.

Джачадиш X.Â., Pao С.С., Кайлат Т. Матричные структуры для реализации итерационных алгоритмов/ ТИИЭР, 1987, т. 75, фиг.б. (54) УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ

МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислиИзобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных систем, функционирующих в реальном масштабе времени.

Цель изобретения — сокращение аппаратурных затрат.

Нг фиг,1 изображена структурная схема устройства; на фиг.2 — функциональная схема вычислительного модуля; на фиг.3 — врегленные диаграммы работы устройства, Устройство содержит N вычислительных модулей 1,1,„.. 1,N (N — размерность матрицы-множил1ого), выход 2, первый 3 и второй 4 кол глутаторы, первый 5 и второй 6 информационные входы, блок синхронизации 7, регистры 8 — 10, коммутаторы 11 и 12, . HJ«1705836 А1 тельных систем. Цель изобретения — сокращение аппаратурных затрат. Цель дост г- ется тем, что устройство содержит линейку из N вычислительных модулей (N — ч. ело строк матрицы-множимого) со связями, блок синхронизации и два коммутатора. На информационные входы устройства поступают элегленты перемножаемых матриц А и

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

Промежуточные результаты опять поступают в блок буферных регистров, а в блок буферных регистров поступают окончательные результаты суммирования, затем поступают на выход устройства 2. 3 ил., 1 табл. регистры 13 и 14, коммутатор 15, первый информационный вход вычислительного модуля 16, умножитель 17, второй информационныи вход вычислительного модуля 18, регистр 19, первый 20 и второй 21 информационные выходы вычислительного модуля. триггеры 22 и 23, первые управляющие выход 24 и вход 25 вычислительного модуля, второй управляющий вход вычислительного модуля 26, триггеры 27 и 28, второй управляющий вход вычислительного модуля 29, сумматор 30, первый 31 и второй 32 блоки буферных регистров, третьи информационные вход 33 и выход 34 вычислительного модуля, триггеры 35 и 36, третьи управляющие выход 37 и вход 38 вычислительного модуля, счетчики 39 и 40, входы синхрони1705836 зации ввода 41 и вывода 42 элементов матриц, дешифраторы 43 и 44.

Первый и второй блоки буферных регистров содержат соответственно N и К-2 регистров. счетчики 39 и 40 имеют коэффициент 5 пересчета соответственно N и К.

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

С = А В = fai j fb)n) = tCtn), (.1 ) 10 где Cln = aljbjn, А — матрица порядка пхК, 1=1 ац — элемент матрицы А,  — матрица порядка KxN, Ь>п — элемент матрицы В, С вЂ” матрица порядка NxK, полученная в результате произведения, i = 1, 2,..., n, J = 1, 2...„К, п =

1,2,..., N.

Рассмотрим работу устройства при К = 3 (для простоты будем рассматривать случай квадратных матриц К = M). Предполагается, что на вход 5 устройства подаются элементы матрицы А, на вход 6 — матрицы В. Условимся, что информация в регистры принимается по переднему перепаду синхроимпульса.

Элементы а матрицы А поступают на первый информационный вход 5 устройства по столбцам, а элементы bjn матрицы  — на второй информационный вход 6 по строчкам, 30

Умножение матрицы А и В заключается в вычислении элементов матрицы С по формуле (1)

С» Сгг Сзз

С1г Сз Сгз

СЗ2 С 13 С21

На первом выходе первого дешифрэтора 43 формируется сигнал (условимся — логическим нулем) и выдается при поступлении нэ вход устройства nepaoro 40 элемента строки Ь1!. На N-м выходе первого дешифратора выдается сигнал (логический нуль) при подаче на вход устройства N-го элемента строки b m. Младший разряд счетчика 43 управления первым 3 и вторым 4 45 коммутаторами. Причем, четное состояние счетчика 43, т.е. О, 2, 4„. „управляет передачей информации со вторых входов коммутаторов 3 и 4 на их выходы, а нечетное состояние счетчика 43 обеспечивает передачу информации на выход коммутаторов 3 и 4 с первых входов этих же коммутаторов.

Счетчик 44 обеспечивает счет обрабатываемых столбцов матрицы А. При этом сигнал

Ha a opoM выходе блока управления 7 выдается только при подаче на вход устройства

5 последнего столбца матрицы А /аь,..., эмку. При подаче на первый управляющий вход коммутатора 15 активного управляющего сигнала, коммутатор 15 производит передачу информации с первого информационного входа 16 на свой выход, э при подаче активного сигнала на второй управляющий вход коммутатор 15 производит передачу со второго информационного входа

18 на свой выход. При подаче активного сигнала на yïðaâëÿþùèé вход коммутаторов 11 и 12 производится передача со вторых информационных входов на свои выходы. При подаче активного сигнала на блок буферных регистров 32 производится запись в его входной регистр с первого информационного входа. При подаче активного сигнала на блок буферных регистров 31 производится разрешение обнуления его входного регистра, которое производится по переднему перепаду синхроимпульса.

Первый такт. В вычислительном модуле

1,1. Во входные регистры умножителя 17.1 поступают данные С» и b», в регистр 8,1 записывается b», а через коммутатор 15 под управляющим сигналом в регистр 14,1 записывается а». Управляющий сигнал с входа 25 записывается в триггер 22,1.

Второй такт. В вычислительном модуле

1.1. В умножителе 17.1 происходит умножение а»Ь» и записывается в его выходной регистр, э во входные регистры записываются новые исходные данные biz и а1ь Данные а» и. Ь!2 с регистров 8,1 и 14.1 перепишутся соответственно в регистры

13.1 и 9.1 В регистр 8.1 записывается azi, а в регистр 19.1 — Ь12. Управляющий сигнал C выхода триггера 22,1 записывается в триггер 23.1.

Третий такт. В вычислительном модуле

1.1. Произведение а»Ь» с выхода умножителя 17.1 в сумматоре 30.1 сложилось с нулем и записывается во входной регистр блока буферных регистров 31.1. В умножителе 17,1 происходит умножение э21Ь12 и записывается в выходной регистр. На входы умножителя 17.1 поступают аз1 и Ь1з. В регистр 10.1 записывается b», в регистр 14,1Ь!з, в регистр 19.1 — аз, а в регистр 9.1 — azt.

В вычислительном модуле 1,2. Во входные регистры умножителя 17.2 записывается Ь12 и а», в регистр 14.2 записывается Ьд, а в регистр 8.1 — а». Управляющий сигнал с выхода триггера 23 обеспечивает передачу операнда с регистра 13,1 на первый информационный вход 16.2 вычислительного модуля 1.2 и фиксируется в триггере 22.2.

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

1705836 ющим входам первого вычислительного модуля. первый, второй и третий управляю- щие входы 1-го вычислительного модуля подключены к одноименным выходам (1-1)- 55

Время вычисления матричного произведения составляет 2N тактов.

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

Устройство для перемножения матриц, содержащее N вычислительных модулей (N размерность перемножаемых матриц) и блок синхронизации, каждый вычислительный модуль содержит умножитель, сумматор, три регистра и первый блок буферных регистров, причем первый и второй информационные входы i-го вычислительного модуля подключены к одноименным выходам (I-1)-го вычислительного модуля (i = 2, N), третий информационный вход которого подключен к третьему информационному выходу I-го вычислительного модуля, третий информационный выход первого вычислительного модуля является выходом устройства, в каждом вычислительном модуле третьи информационные вход и выход являются соответственно первым информационным входом и выходом первого блока буферных регистров, первый и второй информационные входы вычислительного модуля подключены соответственно к первому и второму входам умножителя и к информационным входам первого и третьего регистров; первый вход сумматора подключен к выходу умножителя, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, устройство содержит два коммутатора. а каждый вычислительный модуль содержит шесть триггеров, три коммутатора, четвертый, пятый и шестой регистры и второй блок буферных регистров, причем первый и второй информационные входы устройства подключены к одноименным входам первого коммутатора, выход которого подключен к первому информационному входу первого вычислительного модуля, второй информационный вход которого подключен к выходу второго коммутатора. первый и второй информационные входы которого подключены соответственно ко второму и первому информационным входам вычислительуого модуля„входы синхронизации ввода и вывода элементов матриц подключены к одноименным входам блока синхронизации, первый, второй и третий выходы которого подключены соответственно к первому, второму и третьему управля10

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

170583b

Таблица

1705836

1О.г

Продолнение таблицы

1705836

1705836

1 2 Ю 4 5 8 7 8 У 10 1

251

261

262

2И

Составитель К.Кухаренко

Редактор Л.Пчолинская Техред М.Моргентал Корректор Т. Малец

Заказ 194 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035. Москва, Ж-35. Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101