Устройство для перемножения матриц Советский патент 1992 года по МПК G06F15/347 

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

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

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

Устройство содержит N вычислительных модулей 1.1,..., 1.N (N - размерность матрицы-множимого), выход 2, первый 3 и второй 4 коммутаторы, первый 5 и второй 6 информационные входы, блок синхронизации 7, регистры 8-10, коммутаторы 11 и 12,

регистры 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, входы синхрони J

Р О.

со со о

зации ввода 41 и вывода 42 элементов матриц, дешифраторы 43 и 44.

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

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

С bjn Cm.H)

где Cin Л aiibjn, А-матрица порядка пхК,

1 1

aij - элемент матрицы А, В - матрица порядка KxN, bjn - элемент матрицы В, С - матрица порядка NxK, полученная в результате произведения, i 1, 2,..., п. j 1, 2,..,, К, п 1,2,..., N.

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

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

С п С22 Сзз

С12 С31 С23 С32 Cl3 C21

На первом выходе первого дешифратора 43 формируется сигнал (условимся - логическим нулем) и выдается при поступлении на вход устройства первого элемента строки bji. На N-м выходе первого дешифратора выдается сигнал (логический нуль) при подаче на вход устройства М-го элемента строки bjm. Младший разряд счетчика 43 управления первым 3 и вторым 4 коммутаторами. Причем, четное состояние счетчика 43, т.е. 0. 2, 4,.,., управляет передачей информации со вторых входов коммутаторов 3 и 4 на их выходы, а нечетное состояние счетчика 43 обеспечивает передачу информации на выход коммутаторов 3 и 4 с первых входов этих же коммутаторов. Счетчик 44 обеспечивает счет обрабатываемых столбцов матрицы А. При этом сигнал на втором выходе блока управления 7 выдается только при подаче на вход устройства 5 последнего столбца матрицы A /aik..... auk/. При подаче на первый управляющий вход коммутатора 15 активного управляющего сигнала, коммутатор 15 производит

передачу информации с первого информационного входа 16 на свой выход, а при подаче активного сигнала на второй управляющий вход коммутатор 15 производит передачу со второго информационного входа 18 на свой выход. При подаче активного сигнала на Управляющий вход коммутаторов 11 и 12 производится передача со вторых информационных входов на свои

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

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

Первый такт. В вычислительном модуле 1.1. Во входные регистры умножителя 17.1

поступают данные Си и bn, в регистр 8.1 записывается bn, а через коммутатор 15 под управляющим сигналом в регистр 14.1 записывается ап. Управляющий сигнал с входа 25 записывается в триггер 22.1.

Второй такт. В вычислительном модуле 1.1. В умножителе 17.1 происходит умножение anbn и записывается в его выходной регистр, а во входные регистры записываются новые исходные данные bi2 и an. Дэн- ные an и . bi2 с регистров 8.1 и 14.1 перепишутся соответственно в регистры 13.1 и 9.1 В регистр 8.1 записывается a2i, a в регистр 19.1 - bi2- Управляющий сигнал с выхода триггера 22.1 записывается в тригrep 23.1.

Третий такт. В вычислительном модуле 1.1. Произведение ацЬп с выхода умножителя 17.1 в сумматоре 30.1 сложилось с нулем и записывается во входной регистр

блока буферных регистров 31.1. В умножителе 17.1 происходит умножение 32ibi2 и записывается в выходной регистр. На входы умножителя 17.1 поступают аз1 и bis. В регистр 10.1 записывается bn, в регистр 14.1Ьтз, в регистр 19.1 - азт, а в регистр 9.1 - 321. В вычислительном модуле 1.2. Во входные регистры умножителя 17.2 записывается bi2 и an. в регистр 14.2 записывается bi2. а в регистр 8.1 - ац. Управляющий сигнал с

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

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

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

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

Таблица

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

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

tf

16

F

J

L

25

26

LEE

ъо

D 1

---Э

.-

--э

-

-.

№hy

J

11

1Q

-

2i

24

29

31 -i

Я 77

фиг. 2

3&Z 38.3

Фиг.З