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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных системах. Целью изобретения является повышение быстродействия. Устройство содержит операционные блоки 1<SB POS="POST">1</SB> - 1<SB POS="POST">М</SB> (М - размерность матрицы), блок 2 управления, элементы 3,4 задержки, вход 5 режима работы, синхровход 6, вход начальной установки, информационный вход 8 устройства, группы информационных входов 9<SB POS="POST">1</SB> - 9<SB POS="POST">М</SB> и выходов 10<SB POS="POST">1</SB> - 10<SB POS="POST">М</SB> устройства. Поставленная цель достигается за счет введенных элементов и рациональной организации вычислений. 3 ил.

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

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

РЕСПУБЛИК

СМ1 4 G 06 F 15/347

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4298298/24-24 (22) 19.08,87 (46) 07.04.89. Вюл. Vi 13 (72) В.А.Грищенков, А.Д.Калалб и А.П.Царев (53) 681.32 (088.8) (56) Авторское свидетельство СССР

У 647687, кл. G 06 F 15/347, 1976.

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

М - 1226484, кл. G 06 F 15/31, 1986. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть исÄÄSUÄÄ 1471201 А1 пользовано в специализированных вычислительных системах. Целью изобретения является повышение быстродействия. Устройство содержит операционные блоки t, — 1„ (М вЂ” размерность матрицы), блок 2 управления, элементы 3, 4 задержки, вход 5 режима работы, синхровход 6, вход начальной установки, информационный вход 8 устройства, группы информационных входов 9 -9 „ и выходов 10,—

10 устройства. Поставленная цель достигается за счет введенных элементов и рациональной организации вычислений. 3 ил.

1471201

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

Цель изобретения — повышение быстродействия.

На фиг. 1 представлена функциональная схема устройства на фиг.2— функциональная схема операционного блока, на фиг.3 — функциональная схема блока управления.

Устройство содержит операционные блоки 1 -1„, где М " размерность матрицы, блок 2 управления, элементы 3 и 4 задержки, вход 5 режима работы устройства, синхровход 6 устройства, вход 7 начальной установки 20 устройства, информационный вход 8 устройства, группу информационных входов 9,-9 „ устройства, группу информационных выходов 10„-10„ устройства, входы 11 управления прие- 25 мом операндов, 12 управления порядком обработки операндов,13 синхронизации накапливающего сумматора, 14 установки в "0" регистра накапливающего сумматора, 15 синхронизации 30 регистра результата операционного блока, мультиплексор 16, группу регистров 17, мультиплексор 18, умножитель 19, накапливающий сумматор

20, регистр 2 1 результата, элемент

ИЛИ 22, элемент НЕ 23, элементы

ИЛИ 24 и 25, элемент И 26, триггеры 27 и 28, счетчик 29.

Устройство работает следующим образом. 40

При включении питания сигнал

"Сброс" с входа 7 устройства проходит через элементы ИЛИ 22, 24 и 25, сбрасывает счетчик 29, триггер 27 и устанавливает триггер 28. 45

При этом триггеры 27 и 28 включают мультиплексоры 16 и 18 таким образом, что информация, поступающая в операционный блок 1.К с входа 9.К проходит через мультиплексор 16 в 50 группу регистров 17 и одновременно через мультиплексор 18 поступает на умножитель 19. При умножении вектора на матрицу на вход 5 устройства подается сигнал "Вектор", имеющий уровень логической единицы. В отличие от сигнала "Сброс", который nott Il дается импульсом, сигнал Вектор подается потенциалом и присутствует на входе 5 в течение всего процесса векторно- матричных вычислений. Вектор Х поступает на вход 8 устройства поэлементно (в каждом такте по одному элементу). Матрица Y подается в устройство по столбцам — в каждом такте работы устройства в k-й операционный блок подается очередной элемент k-й строки матрицы У °

Каждый элемент вектора Х поступает на первые входы умножителей всех операционных блоков одновременно. На второй вход умножителя поступает соответствующий . элемент матрицы Y.

Произведение этих элементов подается на вход накапливающего сумматора

20 и складывается с его содержимым.

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

Элемент результирующего вектора с номером P представляет собой скалярное произведение P-й строки матрицы на исходный вектор, Р=О, М-1.

Элемент 3 необходим для задержки сигнала синхронизации накапливающего сумматора на время, необходимое для умножения элементов вектора и матрицы. Через M тактов после начала работы устройства каждый элемент . вектора Х перемножается и суммируется в k-м операционном блоке с соответствующими элементами -й строки матрицы Y. В накапливающем сумматоре

k-ro операционного блока оказывается

k-й элемент вычисляемого вектора произведения: в первом операционном блоке — первый элемент вычисляемого вектора, во втором - второй и т.д.

В это время на первом выходе счетчика

29 появляется сигнал, который стробирует запись результата, находящегося к этому моменту времени в накапливающем сумматоре 20, в регистр

2 1 результата, Этот сигнал, пройдя через элемент 4 задержки, сбрасывает накапливающий сумматор в "0", подготовив его тем самым к вычислению элементов следующего вектора. Элемент 4 необходим для задержки сигнала сброса накапливающего сумматора на время, необходимое для записи результата в регистр 21.

Таким образом, через M тактов после начала работы на выходе устройства появляется весь вычисляемый вектор, а начиная с (И+1)-ro такта

1471201 начинается вычисление следующего векторно-матричного произведения.

Кроме вычисления векторно-матричного произведения предлагаемого уст5 ройства позволяет вычислять произведение матриц. В этом случае матрица

Х подается на вход 8 устройства в следующей последовательности: за элементами первого столбца подаются элементы второго столбца, затем третьего и т.д. Матрица Y подается в устройство так же, как и в предыдущем случае. Одновременно с прохождением через мультиплексор 18 на вход умножителя 19 элементы матрицы Y проходят через мультиплексор 16 на вход группы регистров 17 и записываются в регистры. Группа регистров

17 устроена таким образом, что эле- 20 мент, записываемый в нее на очередном такте, попадает на место элемента, записанного в предыдущем такте, а сам этот элемент сдвигается на одну позицию к выходу (запись мат- 25 рицы Y в ОЗУ необходима потому, что каждый элемент этой матрицы участвует в вычислениях M раз).

Таким образом, через M тактов после начала работы устройства вся матрица Y записана в группу регистров

17. В это время в регистры 21 результата операционных блоков с первого по M-й записаны элементы первого столбца вычисляемой матрицы (как и в случае векторно-матричйого произведения), Сигнал, появившийся на первом выходе счетчика 29, кроме фиксации результата в регистре 2 1 и сброса накапливающего сумматора 20, уста- 4 навливает триггер 27 для переключения мультиплексора 18 в режим передачи на вход умножителя 19 информа-ции из группы регистров 17. Одновременно через элемент И 26 этот сигнал сбрасывает триггер 28 для переключения мультиплексора 16 в режим перезаписи матрицы Y с выхода группы регистров 17 на ее вход.

Через М(М-1) тактов после на50, чала работы устройства на втором 1 выходе счетчика появляется сигнал, который, пройдя через элемент 23, запрещает прохождение сигнала с первого выхода счетчика через элемент И 26 на вход установки в "0", триггера 28 и, пройдя через элемент ИЛИ 24, устанавливает триггер

28 для ввода в группу регистров 17 через мультиплексор 16 новой матрицы Y . .В течение следующих M тактов в группу регистров вводится новая матрица, затем на первом выходе

1 двоичного счетчика 29 появляется сигнал, который записывает в регистры 2 1 результата последний столбец вычисляемой матрицы, обнуляет накапливающие сумматоры 20 операционных блоков и переключает триггер

128 и мультиплексор 16 в режим пере записи введенной матрицы Y ° Одновременно на третьем выходе счетчика

29 появляется сигнал, который через элемент 25 сбрасывает счетчик, и в дальнейшем весь процесс повторяется с новой матрицей. Триггер 27 ис.пользуется только для вычисления первой после начала работы устройства матрицы и в дальнейшем не переключается. Сигнал Вектор" на входе

5 устройства при перемножении матриц должен отсутствовать.

В описанном случае результирующая матрица Z вычисляется по столбцам.

Если матрицу Z необходимо вычислять по строкам, то исходные матрицы Х и Y необходимо подавать в устройство по строкам.

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

Устройство для умножения матриц, содержащее блок управления и M операционных блоков, где М вЂ” размерность матрицы, причем операционный блок содержит умножитель, первый мультиплексор и регистр результата, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены два элемента задержки, ! а в операционный блок — второй мультиплексор, группа регистров и накапливающий сумматор, причем первый информационный вход блока подключен к первым информационным входам первого и второго мультиплексоров, выходы которых подключены соответственно к информационному входу первого регистра группы и к первому входу умножителя, второй вход и выход которого подключены соответственно к второму информационному входу блока и к информационному входу накапливающего сумматора, синхровход, вход установки результата в "0" и выход которого подключены соответственно к входу синхронизации накапливающего сумма1471201

Составитель M.ÑHëèí

Редактор А.Мотыль Техред Л.Олийнык

Корректор Л.Патай

Заказ 1610/51 Тираж 667 Подписное

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

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

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

P-ro регистра группы подключен к ннформаднонаоиу входу Р+1-го регистра группы, .(Р = 1, М вЂ” 1), выход

М-ro регистра группы подключен к вторым информационным входам первого и второго мультиплексоров, вход синхронизации регистра результата блока подключен к синхровходу регистра результата, вход режима работы устройства подключен к входу задания режима блока управления, вход начальной установки устройства подключен к входу начальной установки блока управления, синхровход устройства подключен к спнхровходу k-го опе рационного блока, (k = 1, М) и через первый элемент задержки — к синхровходу блока управления и входу синхронизации накапливающего сумматора k-ro операционного блока, k-й информационный вход группы устройства подключен к первому информацион10 ному входу k-го операционного блока, информационный вход устройства подключен к второму информационному входу k-го операционного блока, выход которого подключен к k-му ин15 формационному выходу группы устройства, первый и второй выходы блока управления подключены соответственно к входам управления приемом операндов и управления порядком о6ра2Q ботки операндов k-го операционного блока, третий выход блока управления подключен к входу синхронизации регистра результата k-го операционного блока и через второй элемент за25 держки — к входу установки в "0" регистра накапливающего сумматора

k-ro операционного блока.