Устройство для умножения трех матриц
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов. Цель изобретения - сокращение объема оборудования устройства. Цель достигается тем, что устройство содержит вычислительных модулей (m-фиксированное число 2 m ), причем основу оборудования каждого вычислительного модуля составляют умножитель и сумматор. В основу работы устройства положена параллельно-поточная организация вычислений. 4 ил., 2 табл.
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения трех матриц.
Известно устройство для перемножения трех матриц FIxP x CPxQ x DQxJ, содержащее Р вычислительных модулей первого типа и Р вычислительных модулей второго типа, причем каждый вычислительный модуль первого типа содержит три регистра, два триггера, умножитель, сумматор, две группы элементов И, две группы элементов ИЛИ, элемент И и узел задержки, а каждый вычислительный модуль второго типа содержит три регистра, два триггера, умножитель, сумматор, шесть групп элементов И, три группы элементов ИЛИ и узел задержки. Недостатком этого устройства является большой объем оборудования. К наиболее близким по технической сущности к предлагаемому изобретению относится устройство для перемножения трех матриц FIxP x CPxQ x DQxJ, содержащее I + J + P + Q - 2 вычислительных модулей, причем каждый вычислительный модуль содержит четыре регистра, два узла задержки, три триггера, умножитель, сумматор, восемь групп элементов И, четыре группы элементов ИЛИ, два элемента И и два элемента НЕ. Недостатком такого устройства является большой объем оборудования (содержит I + J + P + Q - 2 вычислительных модулей). Цель изобретения - сокращение объема оборудования устройства. Цель достигается тем, что устройство для перемножения трех матриц AIxP, XPxQ, DQxJ, где I, J, P и Q - размерности матриц (фиг.1), содержит m(2 m J) вычислительных модулей 5, P(Q+I)-2m параллельных n-разрядных регистров 6(n-разрядность чисел), P(Q + I) - 2m параллельных трехразрядных регистров 7, две группы элементов ИЛИ 8 и 9, причем первый информационный вход 1 устройства подключен к первому информационному входу вычислительного модуля 51, второй информационный вход 2 и настроечный вход 3 устройства подключены соответственно к первым входам групп элементов ИЛИ 8 и 9, выходы которых подключены соответственно ко второму информационному входу и настроечному входу вычислительного модуля 51, первый и второй информационные выходы, настроечный выход 5i-го вычислительного модуля (i = ) подключены соответственно к первому и второму информационному входу, настроечному входу 5(i + 1)-го вычислительного модуля, первый информационный выход 5m-го вычислительного модуля является выходом 10 устройства, второй информационный выход 5m-го вычислительного модуля подключен к информационному входу параллельного n-разрядного регистра 61, выход 6i-го регистра (i = ) подключен к информационному входу 6(i+ 1)-го регистра, выход 6(P(Q + I) - 2m-го регистра подключен ко второму входу группы элементов ИЛИ 8, настроечный выход 5m-го вычислительного модуля подключен к информационному входу трехразрядного параллельного регистра 71, выход 7i-го регистра (i = ) подключен к информационному входу 7(i+1)-го регистра, выход 7(P(Q + I) - 2m)-го регистра подключен ко второму входу группы элементов ИЛИ 9, синхровход устройства подключен к синхровходам всех вычислительных модулей 5iрегистров 6i, 7i. На фиг. 1 представлена структурная схема устройства для перемножения трех матриц; на фиг.2 - структурная схема устройства для I = 2, J = 4, P = 3, Q = 3 и m=2; на фиг.3 - схема вычислительного модуля 5; на фиг.4 - временная диаграмма работы вычислительного модуля в пределах одного такта. Устройство для перемножения трех матриц (фиг.1) содержит первый 1 и второй 2 информационные входы, настроечный вход 3, синхровход 4, вычислительные модули 5i, n-разрядные параллельные регистры 6iтрехразрядные параллельные регистры 7i, группы элементов ИЛИ 8, 9 и выход 10. Вычислительный модуль 5 (фиг.3) содержит первый 11 и второй 12 информационные входы, настроечный вход 13, регистры 14-18, умножитель 19, сумматор 20, триггеры 21-33, группы элементов И 34-46, группы элементов ИЛИ 47-51, элементы И 52-59, элементы НЕ 60-62, первый 63 и второй 64 информационные выходы, настроечный выход 65 и синхровход 66. В основу работы устройства для перемножения матриц A = {aip} , X {xpq} , D = {dqj} i= , j = , = , q = положен следующий алгоритм B= {bpj} = XD, bpj= xpq dqj Y= { yij} = AB, yij= aip dpj который представляется рекуррентными соотношениями: P = , j = , q = : b(p,j,0) = xpodoj, b(p,j,q) = b(p,j,q-1) + xpq dqj , bpj= b(p,j,Q-1); i = , j = , p = : y(i,j,0) = aio boj, y(i,j,p) = y(i,j,p-1)+ aipbpj , yij = y(i,j, P-1). Число m выбирается фиксированным, m =Предполагается, что число Jm = J/m - целое. Если Jm не целое, то J выбирается таким, чтобы J/m , где - ближайшее сверху целое. При этом матрица D дополняется нулевыми столбцами. Вычислительный модуль 5 работает в семи режимах (фиг.3), которые задаются значениями управляющих сигналов , и , подаваемыми соответственно на настроечные входы 131, 132 и 133. Во всех режимах работы значение b, подаваемое на вход 12, выдается на выход 64 с задержкой на два такта. Управляющие сигналы , и выдаются соответственно на выходы 651, 652 и 653 с задержкой на два такта. Информация, записанная в регистр 18i-й ((i = )), на очередном такте переписывается в 18i+1-й регистр. Управляющий сигнал itобеспечивает запись информации в регистр на t-м такте, а управляющий сигнал it - на (t + 1)-м такте. В первом режиме работы подаются управляющие сигналы ( , , )= (0, 1, 1). При этом формируются сигналы 1 = 1 и 1 = 1. Сигнал 1открывает группу элементов И 40 и элемент 59. Элемент а, подаваемый на вход 11, через группы элементов И 40 и ИЛИ 49 подается на информационный вход регистра 17. Элемент записывается в регистр 17 по заднему фронту тактового импульса, проходящего через элемент И 59 на синхровход регистра 17. На первом такте сигнал 1 открывает группу элементов И 35, элемент а с выхода регистра 14 через группы элементов И 35 и ИЛИ 48 подается на первый вход умножителя 19, на его второй вход подается элемент b (с выхода регистра 15), на выходе умножителя 19 формируется значение а b. Временная диаграмма работы в пределах одного такта приведена на фиг.4. Во втором режиме работы ( , , ) = =(0,0,1) формируется сигнал 2= 1. Сигнал 2 открывает группы элементов И 34 и 38. Значение а с выхода регистра 14 через группы элементов И 34 и ИЛИ 47 подается на выход 63. Содержимое регистра 17 через группы элементов И 38 и ИЛИ 48 подается на первый вход умножителя 19, на второй вход которого подается значение b с выхода регистра 15. На выходе умножителя 19 формируется значение <Рег.17> х b. В третьем режиме работы ( , , ) = =(0,1,0). Формируются сигналы 3 = 1 и 3= =1. По сигналу 3 в регистр 17 записывается элемент а. Сигнал 3 открывает группы элементов И 35 и 46. На выходе умножителя 19 формируется значение а. b, на выходе сумматора 20 - значение <Рег.18р >+ a .b. В четвертом режиме работы ( , , ) = =(0,0,0). Формируется сигнал 4 = 1. Сигнал 4 открывает группы элементов И 34, 38 и 46. Значение а с выхода регистра 14 через группы элементов И 34 и ИЛИ 47 подается на выход 63. На выходе умножителя 19 формируется значение <Рег.17> x b, на выходе сумматора 20 - значение <Рег.8р> + <Рег.17 > .b. В пятом режиме работы ( , , ) = =(1,0,1). Формируются сигналы 5 = 1 и 5 = =1. Сигнал 5 открывает группу элементов И 45. Содержимое регистра 18р через группы элементов И 45 и ИЛИ 50 записывается в регистр 181. Сигнал 5 открывает группы элементов И 34, 41 и элемент И 59. Значение а с выхода регистра 14 подается на выход 63. На выходе умножителя 19 формируется значение <18>. b, которое подается через группу элементов И 41 и ИЛИ 49 на информационный вход регистра 17 для записи на следующем такте. В шестом режиме работы ( , , ) = =(1,0,0). Формируются сигналы 6 = 1 и 6 =1. Сигнал 6 открывает группу элементов И 45. В регистр 181 записывается содержимое регистра 18р. Сигнал 6 открывает группы элементов И 34, 37, 39, 44 и элемент И 59. На выход 63 подается значение а. На выходе сумматора 20 формируется значение< Рег.17 >+ <Рег.18> . b, которое через группы элементов И 39 и ИЛИ 49 подается на информационный вход регистра 17 для записи на следующем такте. В седьмом режиме ( , , ) = (1,1,0). Формируются сигналы 7=1 и 7 = 1. Сигнал 7 открывает группу элементов И 45 и в регистр 181 записывается содержимое регистра 18р. Сигнал 7 открывает группы элементов И 36, 37, 39, 44 и элемент И 59. Содержимое регистра 17 через группы элементов И 36 и ИЛИ 47 подается на выход 63. На выходе сумматора 20 формируется значение <Рег. 17 >+ <Рег.18> . b, которое подается через группы элементов И 39 и ИЛИ 49 на информационный вход регистра 17 для записи на следующем такте. Рассмотрим работу устройства (фиг.1)
Управляющие сигналы ig = ( , , ) , i = , j= представляются в виде матрицы
и подаются на вход 3 в моменты времени
t= i P +j. На вход 1 подаются элементы dqj в моменты времени
t= (l-1) P (Q+I)+ ++Pq, где j = + (l-1)m, = , l = . На вход 2 подаются элементы xpq, aip в моменты времени
t= p + Pq , t= p+ P(Q+I-i-1). На выходе 10 формируются элементы yi , + (l -1 ) m в моменты времени t = yi,p+(l-1)m = =lP(Q + I) + m + - P. i - 2. На фиг. 2 приведена структура устройства с входным и выходным потоками данных для I = 2, J = 4, P = 3, Q = 3 и m = 2. Значения на входах и выходах состояния регистров вычислительных модулей 51 (табл. 1) и 52 (табл.2), состояния регистров 7 и 8 приведены в таблице, которая является временной диаграммой работы устройства. Таким образом, предлагаемое устройство содержит меньший объем оборудования по сравнению с прототипом, т.е. предлагаемое устройство содержит m вычислительных модулей, а прототип - J вычислительных модулей (m J).
Формула изобретения
u j+2 = j ;
v j+2 = j ;
w j+2 = j ;
Aj+1 =
cj =
dj-1 =
fj-2 =
ej-1 =
B j+2 = b j ;
1j+1 = 1j = (j, j, j) = (0, 1, 1);
2j+1 = 2j = (j, j, j) = (0, 0, 1);
3j+1 = 3j = (j, j, j) = (0, 1, 0);
4j+1 = 4j = (j, j, j) = (0, 0, 0);
5j+1 = 5j = (j, j, j) = (1, 0, 1);
6j+1 = 6j = (j, j, j) = (1, 0, 0);
7j+1 = 7j = (j, j, j) = (1, 1, 0),
где j, j, j - значения соответственно на первом, втором и третьем разрядах настроечного входа вычислительного модуля на j-м такте;
uj, vj, wj - значения соответственно на первом, втором и третьем разрядах настроечного выхода вычислительного модуля на j-м такте;
aj, bj - значения соответственно на первом и втором информационных входах вычислительного модуля на j-м такте;
Aj, Bj - значения соответственно на первом и втором информационных выходах вычислительного модуля на j-м такте.
РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10