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

 

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

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

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

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

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4819892/24 (22) 28.04.90 (46) 07.02.93. Бюл. N 5 (72) B.Ï.ßêóø, В.B.Koñüÿí÷óê, Н,А,Лиходел и П.И.Соболевский (56) Авторское. свидетельство СССР

N 1619304, кл. G 06 Е 15/347, 1989, Авторское свидетельство СССР

¹ 1619305, кл. G 06 F 15/347, 1989. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТ, РИЦ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных маИзобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки сигналов.

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

Наиболее близким по технической сущности к изобретению является устройство для умножения пхп матриц, содержащее 2п1 вычислительных мо„-улей. причем каждый вычислительный модуль содержит три реги„„. Щ„„1793446 А1 шинах и устройствах обработки сигналов для умножения (nxn)-матрицы на вектор.

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

И.

Недостатком такого устройства является большой объем оборудования за счет большого числа вычислительных модулей—

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

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

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

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

I+1 эво(= аьх

I+a+2

Ьвых = Ььх г аьх Ььх если (1 вх Хгвх) =(1, 1):

I+2 I=p .

CBb x = Cbx + аЬх ЬЬх ЕСЛИ (Ttax, тг)Я» (0,1), аьх Ььх, если (71 вх, Фвх (1,0), аьх " Ььх, если (Г1вх т2вх) = (0 0)

1 1вх = 1ex

+г

Йвх — 6вх

ГДЕ abx bbx, Cbx СООтВЕтСтВЕННО ЗНаЧЕНИЯ

I, 1 I нэ первом, втором, третьем информационных входах вычислительного модуля на l-м такте; т)1в„и т)гв,. — соответственно значения на первом и втором настроечных входах вычислительного модуля на i-м такте;

I eblX bBblX Cebx — соответственно значения на первом, втором, третьем информационных выходах вычислительного модуля на i-м такте; т ) в„= тг„— соответственно значения на первом и втором настроечных выходах вычислительного модуля на l-м такте; р — параметр, определяемый алгоритмом (р = б; D-1);

0 = max (J, О} — параметр, определяе мый размерностью матриц.

Нэ фиг, 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, 21((i = 1, 0) и 22((i = 1, D+2), триггеры 23, 24, 25 и 26, группы элементов

И 27, "8и 29, .группу эле.ме.нтов ИЛИ 30, элемент НЕ 31, первь и 32, второй 33 и третий 34 информационные выходы, первый 35 и второй 36 настроечные выходы.

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

С1) = О, ) = 1, I, J =- 1, S;

Сц(")=CII )+а(((Ьц, i 1, I,J=1, 1,k=

=1, Q;

С()()= CII, =1, I,J=1,J.

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

В первом режиме работы tq, t2 = (1,1) на входы 9, 10 и 11 подаются соответственно элементы С, а и b. При этом элемент С записывается в регистр 17, элемент а — в регистры 18 и 19 (группа элементов И 27

20 открыта при т1 =1) и элемент b — в регистры

211 и 221 (группа элементов И 29 открыта при гг = 1). На выходе умножителя 15 формируется значение а Ь, на выходе сумматора 16 — значение (С+ а b), которое выдается на выход 32 с задержкой на один такт. Элемент а выдается на выход 33 с задержкой на один такт, а элемент Ь вЂ” на выход 34 с задержкой на D+2 тактов, Во втором режиме работы т1, тг = (0,1) аналогичным образом подаются элементы

С, а и Ь. При этом элемент С записывается в регистр 17, элемент а — в регистр 18, элемент b — в регистры 211 и 221, из регистров

21 и 22I (l = 1, D+1) элементы записываются в регистры 21(i+1) и 22(I+1) соответственно. На выхо,()(е умножителя 15 формируется значение а Ь, где элемент а был записан в регистр 19 ранее при подаче т1 = 1, на выходе

40 сумматора 16 формируется значение

С + а Ь, которое выдается на выход 32 с

1. задержкой на один такт, В третьем режиме работы r1, тг = (1,0) аналогично подаются элементы С, а и b. При

45 этом элемент С записывается в регистр 17, элемент а — в регистры 18 и 19 (группа элементов И 27 открыта), элемент Ь вЂ” в регистр . 22, элемент Ь (записанный в регистре 210)

1 переписывается через открытую группу эле50 ментов И 28 и группу элементов ИЛИ 30 в регистр 211, элементы из регистров 21I и 22I (i = 1, 0-.1) переписываются соответственно в регистры 21(I+>) и 22(I+I), на выходе умножителя 15 формируется значение (а.Ь ), на вы55 ходе сумматора 16 — значение С + а b . которое через регистр 20 выдается на выход 32.

В четвертом режиме работы т1, тг =

-(0,0) элементы С, а и b подаются аналогичным образом. Элемент а, записанный в ре1

1793446 гистре 19 при т1 =- 1, подается на вход умножителя 15, на второй вход которого подается через регистр 211 элемент b, На выходе сумматора 16 формируется значение (C + а Ь ), Из регистров 21! и 22! осуществ1. 1 ляется перезапись элементов соответственно в регистры 21(i+ ) и 2(н-!).

Организация входного потока элементов а!), bi! и С!)(управляющих сигналов т! и т выходного потока элементов С!! за- 5 дается известными выражениями.

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

tg)k = D )+ k+2+ lp, )-1,!, k=1,0, где то = (Q - 2) D - 2, D = вам {J, Q). 10

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

gab!,I=j D k+2 О+2+то,/=1,J, k=1 Q, Элементы С!! О = 0 I + j + 2 + tp, I = 1,), j=

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

tr = D - + 3 + то, I 2 Q,l, в остальные моменты подаются т1 = О. 20

Управляющий сигнал тг - 1 подается на . вход 5 в моменты времени (т = ) + 0 + 2 + tp, ) = 1,D, в остальные моменты подаются т =О.

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

t(i!= D !+j+ 2Q+ 1+ tp.

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

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

Устройство для умножения матриц, содержащее Q вычислительных модулей, где

Q — целое число, Q < N, N — линейный размер квадратных матриц, причем первый и второй информационные входы и первый вход задания режима устройства подключены соответственно к первому и второму информационным входам и к первому входу задания режима первого вычислительного модуля, первый, второй и третий входы )-го вычислительного модуля, где I = 1, ..., 0-1, подключены соответственно к первому и второму информационным входам и к первому входу задания режима (!+1)-го вычислительного модуля, четвертый выход Q-ro вычислительного модуля подключен к выходу результата устройства, синхровход которого подключен к синхровходам всех вычислительных модулей, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, и 25, регистров 17, 18, 29, 20, 211, 21з 22! и

225, значения на выходе сумматора 16 вычислительных модулей 7!, 7 и 7з и значения на выходе 8 устройства приведены в таблице. В данном случае элементы ац, Ьц, и С )() подаются в моменты времени та!!<= 3I + k + 3, = 1,2, k = 1,3;

ibgj= j - 3k + 9, k = 1,3, j = 1 2;

tl)= 3I + j + 3, I = 1,2, j = 1,2.

Значения результирующей матрицы формируются в моменты времени тс!)= 3! + j + 8.

Время вычисления последнего элемента Спп равно (I + Q -2) О+ 2Q + J - 1 тактам.

В данном случае элемент Сгг формируется на 16-м такте (см. таблицу).

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

Таким образом, предлагаемое устройство содержит меньший объем оборудования по сравнению с прототипом, т.е. содержит и вычислительных модулей (для = J = n), а прототип — 2n-1 вычислительных модулей (основу оборудования вычислительных моду".ей составляют умножитель и сумматор).

Кроме того, предлагаемое устройство содержит меньшее число выводов (один mразрядный выход, m — разрядность элементов матриц), а прототип — (2n-1) mразрядных выходов, что существенно при проектировании устройства на основе сверхбольших интегральных схем. третий информационный вход и второй вход задания режимаустройства подключены соответственно к третьему информационному и к второму входу задания режима первого вычислительного модуля, четвертый и пятый выходы )-го вычислительного модуля подключены соответственно к третьему информационному входу и к второму входу задания режима (I+1)-ro вычислительного модуля, причем каждый вычислительный модуль содержит четыре регистра, два сдвигающих регистра, умножитель, сумматор, четыре триггера, три блока элементов И, блок элементов ИЛИ и элемент НЕ, при этом в каждом вычислительном модуле первый информационный вход вычислительного модуля подключен к информационному входу rlepeoro регистра, выход которого подключен к первому информационному входу сумматора, выход которого подключен к информационному входу второго регистра, вы1793446

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

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

1793446 а„„

ФигД

Фиг.2

Редактор С. Кулакова

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

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

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

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

Составитель В. Смирнов

Техред М.Моргентал Корректор М, Ткач с