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

 

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

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

Известно устройство для перемножения трех матриц F_IxP x C_PxQ x D_QxJ, содержащее Р вычислительных модулей первого типа и Р вычислительных модулей второго типа, причем каждый вычислительный модуль первого типа содержит три регистра, два триггера, умножитель, сумматор, две группы элементов И, две группы элементов ИЛИ, элемент И и узел задержки, а каждый вычислительный модуль второго типа содержит три регистра, два триггера, умножитель, сумматор, шесть групп элементов И, три группы элементов ИЛИ и узел задержки.

Недостатком этого устройства является большой объем оборудования.

К наиболее близким по технической сущности к предлагаемому изобретению относится устройство для перемножения трех матриц F_IxP x C_PxQ x D_QxJ, содержащее I + J + P + Q - 2 вычислительных модулей, причем каждый вычислительный модуль содержит четыре регистра, два узла задержки, три триггера, умножитель, сумматор, восемь групп элементов И, четыре группы элементов ИЛИ, два элемента И и два элемента НЕ.

Недостатком такого устройства является большой объем оборудования (содержит I + J + P + Q - 2 вычислительных модулей).

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

Цель достигается тем, что устройство для перемножения трех матриц A_IxP, X_PxQ, D_QxJ, где 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 устройства подключен к первому информационному входу вычислительного модуля 5₁, второй информационный вход 2 и настроечный вход 3 устройства подключены соответственно к первым входам групп элементов ИЛИ 8 и 9, выходы которых подключены соответственно ко второму информационному входу и настроечному входу вычислительного модуля 5₁, первый и второй информационные выходы, настроечный выход 5_i-го вычислительного модуля (i = ) подключены соответственно к первому и второму информационному входу, настроечному входу 5(_{i + 1})-го вычислительного модуля, первый информационный выход 5_m-го вычислительного модуля является выходом 10 устройства, второй информационный выход 5_m-го вычислительного модуля подключен к информационному входу параллельного n-разрядного регистра 6₁, выход 6_i-го регистра (i = ) подключен к информационному входу 6_{(i+ 1)}-го регистра, выход 6_{(P(Q + I) - 2m}-го регистра подключен ко второму входу группы элементов ИЛИ 8, настроечный выход 5_m-го вычислительного модуля подключен к информационному входу трехразрядного параллельного регистра 7₁, выход 7_i-го регистра (i = ) подключен к информационному входу 7_(i+1)-го регистра, выход 7_{(P(Q + I) - 2m)}-го регистра подключен ко второму входу группы элементов ИЛИ 9, синхровход устройства подключен к синхровходам всех вычислительных модулей 5_iрегистров 6_i, 7_i. На фиг. 1 представлена структурная схема устройства для перемножения трех матриц; на фиг.2 - структурная схема устройства для I = 2, J = 4, P = 3, Q = 3 и m=2; на фиг.3 - схема вычислительного модуля 5; на фиг.4 - временная диаграмма работы вычислительного модуля в пределах одного такта.

Устройство для перемножения трех матриц (фиг.1) содержит первый 1 и второй 2 информационные входы, настроечный вход 3, синхровход 4, вычислительные модули 5_i, n-разрядные параллельные регистры 6_iтрехразрядные параллельные регистры 7_i, группы элементов ИЛИ 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 = {a_ip} , X {x_pq} , D = {d_qj} i= , j = , = , q = положен следующий алгоритм B= {b_pj} = X·D, b_pj= x_pq· d_qj Y= { y_ij} = A·B, y_ij= a_ip· d_pj который представляется рекуррентными соотношениями: P = , j = , q = : b(p,j,0) = x_pod_oj, b(p,j,q) = b(p,j,q-1) + x_pq· d_qj , b_pj= b(p,j,Q-1); i = , j = , p = : y(i,j,0) = a_io· b_oj, y(i,j,p) = y(i,j,p-1)+ a_ip·b_pj , y_ij = y(i,j, P-1).

Число m выбирается фиксированным, m =
Предполагается, что число J_m = J/m - целое. Если J_m не целое, то J выбирается таким, чтобы J/m , где - ближайшее сверху целое. При этом матрица D дополняется нулевыми столбцами.

Вычислительный модуль 5 работает в семи режимах (фиг.3), которые задаются значениями управляющих сигналов α , β и γ , подаваемыми соответственно на настроечные входы 13₁, 13₂ и 13₃.

Во всех режимах работы значение b, подаваемое на вход 12, выдается на выход 64 с задержкой на два такта. Управляющие сигналы α , β и γ выдаются соответственно на выходы 65₁, 65₂ и 65₃ с задержкой на два такта. Информация, записанная в регистр 18_i-й ((i = )), на очередном такте переписывается в 18_i+1-й регистр. Управляющий сигнал δ_i^tобеспечивает запись информации в регистр на t-м такте, а управляющий сигнал μ_i^t - на (t + 1)-м такте.

В первом режиме работы подаются управляющие сигналы (α , β , γ )= (0, 1, 1). При этом формируются сигналы δ₁ = 1 и μ₁ = 1. Сигнал δ₁открывает группу элементов И 40 и элемент 59. Элемент а, подаваемый на вход 11, через группы элементов И 40 и ИЛИ 49 подается на информационный вход регистра 17. Элемент записывается в регистр 17 по заднему фронту тактового импульса, проходящего через элемент И 59 на синхровход регистра 17. На первом такте сигнал μ₁ открывает группу элементов И 35, элемент а с выхода регистра 14 через группы элементов И 35 и ИЛИ 48 подается на первый вход умножителя 19, на его второй вход подается элемент b (с выхода регистра 15), на выходе умножителя 19 формируется значение а˙ b. Временная диаграмма работы в пределах одного такта приведена на фиг.4.

Во втором режиме работы (α , β , γ ) = =(0,0,1) формируется сигнал μ₂= 1. Сигнал δ₂ открывает группы элементов И 34 и 38. Значение а с выхода регистра 14 через группы элементов И 34 и ИЛИ 47 подается на выход 63. Содержимое регистра 17 через группы элементов И 38 и ИЛИ 48 подается на первый вход умножителя 19, на второй вход которого подается значение b с выхода регистра 15. На выходе умножителя 19 формируется значение <Рег.17> х b.

В третьем режиме работы (α , β , γ ) = =(0,1,0). Формируются сигналы δ₃ = 1 и μ₃= =1. По сигналу δ₃ в регистр 17 записывается элемент а. Сигнал μ₃ открывает группы элементов И 35 и 46. На выходе умножителя 19 формируется значение а^. b, на выходе сумматора 20 - значение <Рег.18р >+ a ^.b.

В четвертом режиме работы (α , β , γ ) = =(0,0,0). Формируется сигнал μ₄ = 1. Сигнал μ₄ открывает группы элементов И 34, 38 и 46. Значение а с выхода регистра 14 через группы элементов И 34 и ИЛИ 47 подается на выход 63. На выходе умножителя 19 формируется значение <Рег.17> x b, на выходе сумматора 20 - значение <Рег.8р> + <Рег.17 > ^.b.

В пятом режиме работы (α , β , γ ) = =(1,0,1). Формируются сигналы δ₅ = 1 и μ₅ = =1. Сигнал δ₅ открывает группу элементов И 45. Содержимое регистра 18р через группы элементов И 45 и ИЛИ 50 записывается в регистр 18₁. Сигнал μ₅ открывает группы элементов И 34, 41 и элемент И 59. Значение а с выхода регистра 14 подается на выход 63. На выходе умножителя 19 формируется значение <18>^. b, которое подается через группу элементов И 41 и ИЛИ 49 на информационный вход регистра 17 для записи на следующем такте.

В шестом режиме работы (α , β , γ) = =(1,0,0). Формируются сигналы δ₆ = 1 и μ₆ =1. Сигнал δ₆ открывает группу элементов И 45. В регистр 18₁ записывается содержимое регистра 18р. Сигнал μ₆ открывает группы элементов И 34, 37, 39, 44 и элемент И 59. На выход 63 подается значение а. На выходе сумматора 20 формируется значение< Рег.17 >+ <Рег.18> ^. b, которое через группы элементов И 39 и ИЛИ 49 подается на информационный вход регистра 17 для записи на следующем такте.

В седьмом режиме (α , β , γ) = (1,1,0). Формируются сигналы δ₇=1 и μ₇ = 1. Сигнал δ₇ открывает группу элементов И 45 и в регистр 18₁ записывается содержимое регистра 18р. Сигнал μ₇ открывает группы элементов И 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 подаются элементы d_qj в моменты времени
t= (l-1) P (Q+I)+ ρ ++Pq, где j = ρ + (l-1)m, ρ = , l = .

На вход 2 подаются элементы x_pq, a_ip в моменты времени
t= p + Pq , t= p+ P(Q+I-i-1).

На выходе 10 формируются элементы y_{i , ρ + (l -1 ) m} в моменты времени t = y_i,p+(l-1)m = =lP(Q + I) + m + ρ - P^. i - 2.

На фиг. 2 приведена структура устройства с входным и выходным потоками данных для I = 2, J = 4, P = 3, Q = 3 и m = 2. Значения на входах и выходах состояния регистров вычислительных модулей 5₁ (табл. 1) и 5₂ (табл.2), состояния регистров 7 и 8 приведены в таблице, которая является временной диаграммой работы устройства.

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

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

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ, каждая размерностью 1 ·P, P · Q, Q × τ соответственно, содержащее m(2 ≅ m ≅ τ) вычислительных модулей, причем первый информационный вход устройства подключен к первому информационному входу первого вычислительного модуля, первый и второй информационные выходы и настроечный выход i-го вычислительного модуля (i = ) подключены соответственно к первому и второму информационным входам и настроечному входу (i+1)-го вычислительного модуля, первый информационный выход m-го вычислительного модуля является выходом устройства, синхровход которого подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью сокращения объема оборудования, в него введены две группы элементов ИЛИ, [P(Q+I)-2m] параллельных n-разрядных регистров и [P(Q+I)-2m] параллельных трехразрядных регистров (n - разрядность чисел), причем второй информационный вход устройства подключен к первым входам элементов ИЛИ первой группы, выходы которых подключены к второму информационному входу первого вычислительного модуля, второй информационный выход m-го вычислительного модуля подключен к информационному входу первого параллельного n-разрядного регистра, выход j-го параллельного n-разрядного регистра (j = 1 подключен к информационному входу (j+1)-го параллельного n-разрядного регистра, выходы разрядов [P(Q+I)-2m]-го параллельного n-рязрядного регистра подключены к вторым входам элементов ИЛИ первой группы, настроечный вход устройства подключен к первым входам элементов ИЛИ второй группы, выходы которых подключены к настроечному входу первого вычислительного модуля, настроечный выход m-го вычислительного модуля подключен к информационному входу первого параллельного трехразрядного регистра, выход j-го параллельного трехразрядного регистра подключен к информационному входу (j+1)-го параллельного трехразрядного регистра, выход [P(Q+I)-2m]-го параллельного трехразрядного регистра подключен к вторым входам элементов ИЛИ второй группы, синхровход устройства подключен к синхровходам всех регистров, причем каждый вычислительный модуль обладает возможностью реализации функций
u ^j+2 = α ^j ;
v ^j+2 = β ^j ;
w ^j+2 = γ ^j ;
A^j+1 =
c^j =
d^j-1 =
f^j-2 =
e^j-1 =
B ^j+2 = b ^j ;
μ₁^j+1 = δ₁^j = (α^j, β^j, γ^j) = (0, 1, 1);
μ₂^j+1 = δ₂^j = (α^j, β^j, γ^j) = (0, 0, 1);
μ₃^j+1 = δ₃^j = (α^j, β^j, γ^j) = (0, 1, 0);
μ₄^j+1 = δ₄^j = (α^j, β^j, γ^j) = (0, 0, 0);
μ₅^j+1 = δ₅^j = (α^j, β^j, γ^j) = (1, 0, 1);
μ₆^j+1 = δ₆^j = (α^j, β^j, γ^j) = (1, 0, 0);
μ₇^j+1 = δ₇^j = (α^j, β^j, γ^j) = (1, 1, 0),
где α ^j, β ^j, γ ^j - значения соответственно на первом, втором и третьем разрядах настроечного входа вычислительного модуля на j-м такте;
u^j, v^j, w^j - значения соответственно на первом, втором и третьем разрядах настроечного выхода вычислительного модуля на j-м такте;
a^j, b^j - значения соответственно на первом и втором информационных входах вычислительного модуля на j-м такте;
A^j, B^j - значения соответственно на первом и втором информационных выходах вычислительного модуля на j-м такте.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10