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

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

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

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

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

Недостатком такого устройства является большой объем оборудования за счет большого числа вычислительных модулей - 2п-1, а также большого числа выходов - (2п- 1), m-разрядных выходов, где т - разрядность элементов матриц.

Цель изобретения - сокращение объема оборудования устройства.

Цель достигается тем, что-устройство для умножения матриц AIXQ x BQXJ содержит Q вычислительных модулей 7, причем первый 1, второй 2 и третий 3 информационные входы, первый 4 и второй 5 настроечные входы устройства подключены соответственно к первому, второму, третьему информационным входам, к первому и второму настроечным входам первого вычислительного модуля 7i, первый, второй и третий информационные выходы, первый и второй

ю ы

о

настроечные выходы 7i-ro вычислительного модуля (i 1, Q-1 j подключены соответственно к первому, второму и третьему информационным входам, к первому и второму настроечным входам 7(i+i)-ro вычислительного модуля является выходом 8 устройства, синхровход которого подключен к синхров- ходам всех вычислительных модулей 7. Каждый вычислительный модуль 7 выполнен с возможностью реализации функций

авых аьх

. l+d+2 к. i Ьвых- Dbx

- I+2 r I , вых v-bx +

ТУ;2 Т1

Т2в1;2 т2е

аьх1 Ььх1 если (Г1вх,г2вх) (1.1): -Ььх если

(Г1вх,Г2вх(0,1);

аьх Ььх , если

(Т1вх,Т2вх)(1,0);

Ььх . если

(Т1вх,Т2вх) (0,0)

1вх

где аьх bbx1, Сьх1 - соответственно значения на первом, втором, третьем информационных входах вычислительного модуля на 1-м :такте;

тАвх и - соответственно значения на первом и втором настроечных входах вычислительного модуля на i-м такте;

авых , Ьвых1, Свых - соответственно значения на первом, втором, третьем информационных выходах вычислительного модуля на i-м такте;

мвх TZBX соответственно значения на первом и втором настроечных выходах вычислительного модуля на 1-м такте;

Р параметр, определяемый алгоритмом (р б, D-1);

D max {J, Q} - параметр, определяе- мый размерностью матриц.

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

Устройство для умножения матриц (фиг. 1) содержит первый 1, второй 2 и третий 3 информационные входы, первый 4 и второй 5 настроечные входы, синухровход 6, вычислительные модули 7i (i 1, Q) и выход 8.

Вычислительный модуль 7 (фиг, 2) содержит первый 9, второй 10 и третий 11 информационные входы, первый 12 и второй 13 настроечные входы, синхровход 14, умножитель 15, сумматор 16, регист р ы 17, 18, 19. 20, 21i (i Г D) и 22i (I - 1, D+2), триггеры 23, 24, 25 и 26, группы элементов И 27, 28 и 29, группу элементов ИЛИ 30, элемент НЕ 31, первый 32, второй 33 и тре0

5

0

5

0

5

0

5

0

5

тий 34 информационные выходы, первый 35 и второй 36 настроечные выходы.

В основу работы положен алгоритм

Ci/o) 0,1 1, ,J 1, J; Cij ) + aik bkj, l 1,l,J 1,J,k 1,Q:.

Ci/Q)Cij, I 1,I,J 1,J.

Вычислительный модуль 7 работает в четырех режимах, которые задаются значениями управляющих сигналов п и Г2 , подаваемыми на настроечные входы 12 и 13 соответственно. На выходах 35 и 36 управляющие сигналы т и Т2 выдаются с задержкой на два такта.

В первом режиме работы т, Т2 (1,1) на входы 9, 10 и 11 подаются соответственно элементы С, а и Ь. При этом элемент С записывается в регистр 17, элемент а - в- регистры 18 и 19 (группа элементов И 27 открыта при TI 1) и элемент b - в регистры 211 и 22i (группа элементов И 29 открыта при Т2 1). На выходе умножителя 15 формируется значение а-Ь, на выходе сумматора 16 - значение (С + а-Ь), которое выдается на выход 32 с задержкой на один такт. Элемент а выдается на выход 33 с задержкой на один такт, а элемент b - на выход 34 с задержкой на D+2 тактов,

Во втором режиме работы т , Т2 (0,1) аналогичным образом подаются элементы С, а и Ь. При этом элемент С записывается в регистр 17. элемент а - в регистр 18, эле- мент b - в регистры 211 и 221, из регистров 21| и22|( 1, D+1) элементы записываются в регистры 21(ц-1) и 22(1+1) соответственно. На выходе умножителя 15 формируется значение а -Ь, где элемент а был записан в регистр 19 ранее при подаче т 1, на выходе сумматора 16 формируется значение С + а1 -Ь, которое выдается на выход 32 с задержкой на один такт.

В третьем режиме работы т, тг (1,0) аналогично подаются элементы С, а и Ь. При этом элемент С записывается в регистр 17, элемент а - в регистры 18 и 19 (группа элементов И 27 открыта), элемент b - в регистр . 221, элемент Ь1 (записанный в регистре 21 о) переписывается через открытую группу элементов И 28 и группу элементов ИЛИ 30 в регистр 211, элементы из регистров 21| и 22i (, D-.1) переписываются соответственно в регистры 21(1+1) и 22(i+i), на выходе умножителя 15 формируется значение (а -Ь ), на выходе сумматора 16 - значение С + а-Ь1, которое через регистр 20 выдается на выход 32.

В четвертом режиме работы л , Г2 (0,0) элементы С, а и b подаются аналогичным образом. Элемент а1, записанный в регистре 19 при TI 1, подается на вход умножителя 15, на второй вход которого подается через регистр 211 элемент b . На выходе сумматора 16 формируется значение (С + а -Ь1). Из регистров 21) и 22i осуществляется перезапись элементов соответственно в регистры 21(1+1) и 2(|-и).

Организация входного потока элементов aij, bij и Ci/° управляющих сигналов TI и Г2 выходного потока элементов Cij за- дается известными выражениями.

Элементы aik подаются на вход 2 в моменты времени

taik D-l + k + 2 + tp. I-1,1, k 1,Q, где to (Q - 2)-D - 2, D max {J, Q}.

Элементы bkj подаются на вход 3 в моменты времени

tbkj J - Р -k + 2 -D + 2 + to, | 1 ,J, k Ш Элементы Ci/o) D -i + J + 2 + to, I П. J 1,J.

Управляющий сигнал г 1 подается на вход А в моменты времени

tn D-l + 3 + t0, I-2:QJ, в остальные моменты подаются п 0.

Управляющий сигнал тг 1 подается на вход 5 в моменты времени

tra j + D + 2 + to. j Го, в остальные моменты подаются Г2 0.

На выходе 8 устройства формируются элементы Cij в моменты времени

tcij D -1 + j + 2Q + 1 + to.

Рассмотрим работу устройства для случая l J 2nQ 3. Состояния триггеров 23

0

5

и 25. регистров 17, 18, 29, 20, 211, 21з. 22i и 22s, значения на выходе сумматора 16 вычислительных модулей 7i, 72 и 7з и значения на выходе 8 устройства приведены в таблице. В данном случае элементы аш, bik и Ci/° подаются в моменты времени

tai k 31 + k + 3,1 1JJ, k - П;

+ 9, ,3, J Q;

+ j + 3, I f2,j 0.

Значения результирующей матрицы формируются в моменты времени

tC|j 3i + j + 8.

Время вычисления последнего элемента Спп равно (I + Q-2)-D + 2Q +J- 1 тактам. В данном случае элемент С22 формируется на 16-м такте (см, таблицу).

Период ввода элементов для умножения последующих матриц А и В равен (I + Q - 1)-D - 1 тактам.

Таким образом, предлагаемое устройство содержит меньший объем оборудования по сравнению с прототипом, т.е. содержит п вычислительных модулей (для I J n), a прототип - 2п-1 вычислительных модулей (основу оборудования вычислительных модулей составляют умножитель и сумматор). Кроме того, предлагаемое устройство содержит меньшее число выводов (один т- разрядный выход, т - разрядность элементов матриц), а прототип - (2n-1) m- разрядных выходов, что существенно при проектировании устройства на основе сверхбольших интегральных схем.

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

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

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