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

 

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

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

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

РЕСПУБЛИК (si)s G 06 F 15/347

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4751295/24 (22) 17.10.89 (46) 29.02.92. Бюл. ГЬ 8 (71) Киевский политехнический институт им, 50-летия Великой Октябрьской социалистической революции (72) Ю.С. Каневский, М.К. Клименко, С.Э, Котов и С.Г. Оврвменко (53) 681.3(088.8) (56).R.В. Vrguhart and D. Wood. Systolic

malrix and vector multiplication methods for

signal Processing. lEE Proceedings, voj, 131, Pt. F, f4 6, Oct, 1984.

Авторское свидетельство СССР

N. 1494018, кл. G 06 F 15/347, 1987. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ

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

Цель изобретения — сокращение вппаратурных затрат за счет уменьшения числа входов устройства, На фиг. 1 изображена структурная схема устройства; на фиг, 2 — функциональная схема вычислительного модуля; на фиг. 3пример выполнения узла памяти; на фиг. 4 — функциональная схема блока управления; на фиг. 5 — временные диаграммы, поясняющие работу блока управления, Устройство (фиг. 1) содержит вычислительные модули 1.1-.1,К, где К- размерность

2.

Каждый вычислительный модуль (фиг, 2) содержит первый регистр 3, умножитель 4, сумматор 5, второй регистр 6, узел памяти

7, блок регистров 8 и элемент НЕ 9.

Узел памяти 7 (фиг.4) содержит адресуемый регистр 10, регистр 11, дешифраторы

12 и 13, регистры 14 и 15.

Блок управления (фиг. 4) содержит регистр 16, элементы ИЛИ 17 и 18, счетчики 19 и 20, дешифраторы 21 и 22, триггер 23.

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

С=А В(а Д jbjnj = (с п}, где ctn= a(j, tjni

I — t

aq — элемент матрицы-множимого А;

1116536

20

25 ройства, в каждом вычислительном модуле первый информационный вход подключен к

35

50

blï — элемент матрицы-множителя 8; с л — элемент матрицы-результата С, l=1,Ì; j=1,К; и 1,R.

Рассмотрим работу устройства при

К=М=Я=З. На первый информационный 5 вход устройства подаются элементы матрицы А, на второй информационны вход- элементы матрицы В; причем во время умножения матриц А и В через второй информационный вход устройства загружаются элементы матрицы 6 с тем, чтобы после окончания подачи элементов матрицы А можно было начинать умножение следующей пары матриц F u G.

Предварительно в узлы памяти 7 долж- 1 ны быть загружены элементы матрицы В по строкам ()-я строка находится в узле памяти

7l) по четным адресам (триггер 23 блока управления в нулевом состоянии). B соответствии с адресами, поступающими на первый и второй адресные входы узла памяти, информация записывается соответственно в регистры 14 и 15, Кроме того, по адресу, выбранному дешифратором 13, в адресуемый регистр 10 записывается информация с выхода регистра 11.

8 первом такте управляющие сигналы с выходов блока управления 2 фиксируются в блоке регистров 8,1. На первый информационны вход устройства поступает элемент а11, который принимается в регистр 3.1, Из узла памяти по адресу 101 выбирается Ь11.

В умножителе 4.1 формируется произведение a11b11, которое поступает в сумматор

5.1 и в конце такта принимается в регистр

6.1. 8 этом же такте на первый информационный вход устройства поступает элемент новой матрицы G 31 по адресу 101 (элементы матрицы G записываются по нечетным адресам, триггер 23 s нулевом состоянии).

Во втором такте управляющие сигналы с выхода блока регистров 8.1 фиксируется в блоке регистров 8.2. На первый информационный вход устройства поступает элемент а12, который принимается в регистр 3.2 и на 4 выходе сумматора 5.2 формируется промежуточный результат а11Ь11+ а12Ь21, который в конце такта принимается в регистр 6.2.

Элемент Ь21 считывается из узла памяти по адресу 010. В этом же такте на выходе сумматора 5.1 формируется результат а11Ь12 который принимается в регистр 6.1.

В третьем такте из узла памяти 7.3 считывается b3> по адресу 000. На первый информационный вход устройства поступает 5 элемента э, который принимается в регистр

3.3 и на выходе сумматора 5.3 формируется первый элемент результирующей матрицы си= aub3t+ аи2Ьв+ ацЬи, который в конце такта принимается в регистр 6.3. 8 этом же такте в вычислительном модуле 1.2 формируется и ром ежуточ н ы и резул ьтат а1>b>2+ а12Ь22, а в вычислительном модуле — 1.1— а11Ь13. 8 этом же такте на первый информационный вход устройства поступает элемент 6i2.

Дальнейшая работа устройства аналогична описанной. Последний элемент матрицы — результата с33 формируется в вычислительной модуле 1.3 на одиннадцатом такте. На десятом такте в вычислительном модуле 1.1 начинает формироваться произведение новой пары матриц F u G.

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

1. Устройство для умножения матриц, содержащее К вычислительных модулей (К— размерность матриц), каждый из которых содержит два регистра, умножитель и сумMsT0p, причем первый информационный вход I-ro вычислительного модуля (l=2,К) подключен к первому информационному выходу (i-1)-го вычислительного модуля. первый информационный выход К-го вычислительного модуля является выходом устпервому входу сумматора, второй вход которого подключен к выходу умножителя, первый вход которого подключен к выходу первого регистра, информационный вход которого подключен к второму информационному входу вычислительного модуля, первый информационный выход которого подключен к выходу второго регистра, информационный вход которого подключен к выходу сумматора, отл ич а ю ще е с я тем. что, с целью сокращения аппаратурных затрат за счет уменьшения числа входов устройства, оно содержит блок управления, а каждый вычислительный модуль содержит блок регистров, элемент Н Е, узел памяти, причем первый и второй входы блока управления являются соответственно синхровходом и входом начальной установки адреса узла памяти устройства, первый информационный вход которого подключен к объединенным вторым информационным входам всех вычислительных модулей, первый и третий информационные входы первого вычислительного модуля подключены соответственно ко входу логического нуля и второму информационному входу устройства, первый, второй и третий выходы блока управления подключены соответственно к разрядам, кроме младшего. входа адреса узла памяти, младшему разряду входа адреса узла памяти и входу синхронизации ввода элементов матрицы первого вычислительного модуля. вход адреса узла памяти и вход синхронизации ввода эле1716536 ментов матрицы i-го вычислительного модуля подключены к одноименным выходам I1-ro вычислительного модуля, в каждом вычислительном модуле разряды входа адреса узла памяти, кроме младшего, млад- 5 ший разряд входа адреса узла памяти и вход синхронизации ввода элементов матрицы подключены к информационным входам соответственно первого, второго и третьего регистров блока, выход первого регистра 10 которого подключен к обьединенным первому и второму входам адреса узла памяти и разрядам, кроме младшего, выхода адреса узла памяти вычислительного модуля, младший разряд которого подключен к 15 младшему разряду первого входа адреса узла памяти, входу элемента HE и выходу второго регистра блока, выход третьего регистра которого подключен к синхровходу первого регистра и выходу синхронизации ввода 20 элементов матрицы вычислительного модуля, выход элемента НЕ подключен к младшему разряду второго входа адреса узла памяти, информационный вход которого является третьим информационным входом вычисли- 25 тельного модуля. второй информационный выход которого подключен к первому информационному выходу узла памяти, второй информационный выход которого подключен ко второму входу умножителя, 2. Устройство по п,1, о т л и ч а ю щ е ес я тем, что блок управления содержит. регистр, два элемента ИЛИ, два счетчика, два дешифратора и триггер;- причем первый вход блока управления подключен к синхровходу регистра и первым входам первого и второго элементов ИЛИ, выходы которых подключены к счетным входам соответственно первого и второго счетчиков, объединенные входы установки которых подключены к выходу регистра, информационный вход которого является вторым входом блока управления, первый выход которого подключен к выходу первого счетчика и входу первого дешифратора, выход которого подключен ко второму входу первого элемента ИЛИ, входу обнуления второго счетчика, второму выходу. блока управления, третий выход которого подключен к выходу триггера, счетный вход которого подключен ко второму входу второго элемента ИЛИ и выходу второго дешифратОра, вход которого подключен к выходу второго счетчика, 1716536

1716536 фиг. Ф

За руыа катрин оперануака

Я " К

СИ

Фиг.1

Редактор Т,Орловская

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

ВНИИПИ Государственного комитета bio.éçîáðåòåíèÿì и открытиям при ГКНТ СССР

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

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

И

Йи. И2

Ъ йи . И1

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

Техред М.Моргентал Корректор1Л.Бескид