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

 

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения трех матриц. Цель изобретения - повышение быстродействия и сокращение аппаратурных затрат. Цель достигается тем, что устройство для умножения трех матриц размерностью I x p, p x Q и Q x F содержит p однотипных, линейно связанных вычислительных модулей 7, каждый из вычислительных модулей содержит четыре регистра 17 - 20, группу регистров 21, шесть триггеров 22 - 27, умножитель 15, сумматор 16, семь групп элементов И 28 - 34, четыре группы элементов ИЛИ 35 - 38, три элемента И 39 - 41 и элемент НЕ 42. Устройство перемножает три (n x n) матрицы за (2n²+2n) тактов. 3 ил., 1 табл.

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

Цель изобретения - повышение быстродействия и сокращение аппаратурных затрат.

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

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

Вычислительный модуль 7 (фиг.3) содержит первый 9 и второй 10 информационные входы, первый 11, второй 12 и третий 13 настроечные входы, синхровход 14, умножитель 15, сумматор 16, регистры 17-20, группу регистров 21_j(j= 1, ) триггеры 22-27, группы элементов И 28-34 группы элементов ИЛИ 35-38, элементы И 39-41, элемент НЕ 42, первый 43 и второй 44 информационные выходы, первый 45, второй 46 и третий 47 настроечные выходы В основу работы устройства для умножения трех матриц F_ixp x C_pxQ x D_QxT положены следующие рекуррентные соотношения: g^(o_pj⁾= 0, p = , j= 1,J; q = , p = , j= 1,J: g^(q_pj⁾= g^(q_pj^-1)+ C_pqd_qj; g_pj = g^(Q_pj⁾, p = , j = ; h^(o_ij⁾= 0, i = , j= ;P = , i= , j = : h^(p_ij⁾= h^(p_ij^-1)+f_ipgpi; h_ij= h^(p_ij⁾, i= , j = .

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

В первом режиме подаются управляющие сигналы ( α , β , γ ) = (1,1,1). Пpи этом на входы 9 и 10 подаются соответственно элементы d и c, в регистр 17 записывается элемент d, в регистры 18 и 19 записывается элемент с (элемент И 40 открыт с помощью управляющего сигнала γ= 1 и разрешена запись в регистр 19), группы элементов И 28, 29 и 30 и элемент И 39 открыты, на выходе умножителя 15 формируется значение с ^.d, которое через группы элементов И 30 и ИЛИ 37 на следующем такте записывается в регистр 21₁, элемент d с выхода регистра 17 через группы элементов И 28 и ИЛИ 38 подается на вход регистра 20 и затем на выход 43.

Второй режим задается управляющими сигналами ( α , β , γ ) = (1,1,0). На входы 9 и 10 подаются соответственно элементы d и с^I. Группы элементов И 28, 31 и 34 и элемент И 41 открыты, на выходе умножителя 15 формируется значение с˙ d (элемент с записан в регистре 19), на выходе сумматора 16 формируется значение c˙d (на второй вход сумматора подается нулевое значение, так как группа элементов И 33 закрыта нулевым сигналом с выхода элемента НЕ 42), на вход регистра 21₁подается значение с˙ d через группы элементов И 31 и ИЛИ 37, на выход 43 подается элемент d через группы элементов И 28 и ИЛИ 38, на выход 44 подается элемент с^I.

В третьем режиме подаются управляющие сигналы ( α , β , γ ) = (1,0,1). На входы 9 и 10 подаются соответственно элементы d и с^I. Открываются группы элементов 28, 31, 34 и элементы И 40 и 41. В регистры 18 и 19 записывается элемент с, в регистр 17 - элемент d. На выходе умножителя 15 формируется значение c˙d, на выходе сумматора 16 - значение g = c˙ d + c^I˙ d^I (значение c^I˙ d^I подается на вход сумматора 16 с выхода регистра 21_Λ ), значение g с выхода сумматора 16 подается на вход регистра 21₁ через группы элементов И 31 и ИЛИ 37, элемент d подается через группы элементов И 28 и ИЛИ 38 на вход регистра 20.

В четвертом режиме подаются управляющие сигналы ( α , β , γ ) = (1,0,0). На входы 9 и 10 подаются соответственно элементы d и с. Открываются группы элементов 28, 31, 34 и элемент И 41. В регистр 17 записывается элемент d, в регистр 18 - элемент с, в регистре 19 хранится элемент с^II. На выходе умножителя 15 формируется значение с^I ˙d, на выходе сумматора 16 - значение g = c^II˙ d + c^I˙ d^I (значение c^I ˙ d^Iподается на вход сумматора 16 с выхода регистра 21_Λ-го), значение g подается на вход регистра 211, элемент d подается через группы элементов И 28 и ИЛИ 38 на вход регистра 20.

Пятый режим работы задается управляющими сигналами ( α , β , γ ) = (0,0,1). На входы 9 и 10 подаются соответственно элементы h и f. Элемент h записывается в регистр 17, а элемент f - в регистры 18 и 19. Открываются группы элементов И 29, 32, 33 единичным сигналом с выхода элемента НЕ 42. На выходе умножителя 15 формируется значение f˙ g, где g - содержимое регистра 21_Λ , поступающее на второй вход умножителя через группы элементов И 33 и ИЛИ 35, на выходе сумматора 16 - значение h^I = h + +f ˙g, которое подается через группы элементов И 32 и ИЛИ 38 на вход регистра 20.

В шестом режиме работы подаются управляющие сигналы ( α , β , γ ) = (0,0,1). На входы 9 и 10 подаются соответственно элементы h и f, которые записываются соответственно в регистры 17 и 18. В регистре 19 хранится элемент f^I . Открываются группы элементов И 29, 32 и 33. На выходе умножителя 15 формируется значение f ^I˙g, на выходе сумматора 16 - значение h^I = h + f^I˙ g, которое подается на вход регистра 20. Во всех режимах работы управляющие сигналы α , β , γ задерживаются на два такта.

На фиг. 1 на входы устройства 1 и 2 подаются соответственно элементы d_ij(h_ij) и c_ij(f_ij) в моменты времени: t=i+j+2+t_o,
t=i+j+Q+2+t_o,
t= i+j+2+t_o,
t= ·i +j+Q+2+t_o, где t_o = -(2 + Λ ), Λ = max{F, p}.

На входы 3, 4 и 5 подаются соответственно управляющие сигналы α , β и γ в моменты времени:
t_α=1= j+k+2+t_o, j =, k =Q;
t_α=0= j+k+2+t_o, j =, k =I;
t_β=1= j++2+t_o, j =;
t_β=0= j+k+2+t_o, j =, k =I ;
t_γ=1= k+3+t_o, k =I ;
t_γ=0= j+k+2+t_o, j =, k =I.
На выходе устройства 8 элементы h_ij формируются в моменты времени
t= i+j+Q+2P+2+t_o.

Последний элемент h_IF формируется на (Λ (Q + I) + 2P + (F - Λ )-м такте.

Период подачи элементов (c_ij, d_ij, f_ij) для перемножения матриц следующей задачи равен Λ (Q + I) тактов.

Рассмотрим работу устройства для случая I = P = 3 и F = Q = 2. Организация входного и выходного потоков данных приведена на фиг.2. Состояния регистров, триггеров, значения на выходе умножителя и сумматора вычислительных модулей 7₁, 7₂ и 7₃ приведены в таблице. Рассмотрим формирование элемента h₁₁. На первом такте в вычислительном модуле 7₁ формируется значение c₁₁d₁₁, на втором такте - значение c₁₂d₂₁, на четвертом такте - значение g₁₁ = =c₁₁d₁₁ + c₁₂d₂₁, на седьмом такте - значение h₁₁⁽¹⁾ = h₁₁⁽¹⁰⁾ + f₁₁ g₁₁. В вычислительном модуле 7₂на девятом такте формируется значение h₁₁⁽²⁾ = g₁₁⁽¹⁾ + f₁₂g₂₁. В вычислительном модуле 7₃ на одиннадцатом такте формируется значение h₁₁= h₁₁⁽³⁾ = h₁₁⁽²⁾ + +f₁₃g₃₁, которое выдается на выход 8 устройства на тринадцатом такте. Аналогичным образом формируются остальные элементы h_ij.

Устройство перемножает три (n x n)-матрицы за (2_n² + 2n) тактов.

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

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ, каждая размерностью Y · P, P · Q, Q · Y соответственно, содержащее P вычислительных модулей, причем первый и второй информационные входы устройства соединены соответственно с первым и вторым информационными входами первого вычислительного модуля, первый, второй и третий настроечные входы которого соединены соответственно с первым, вторым и третьим настроечными входами устройства, синхровход которого соединен с синхровходами всех вычислительных модулей, первый и второй информационные выходы и первый, второй и третий настроечные выходы i-го вычислительного модуля (i= соединены соответственно с первым и вторым информационными входами и первым, вторым и третьим настроечными входами (i+1)-го вычислительного модуля, первый информационный выход P-го вычислительного модуля является выходом устройства, при этом каждый вычислительный модуль содержит умножитель, сумматор, четыре регистра, группу регистров, первый, второй и третий триггеры, семь групп элементов И, четыре группы элементов ИЛИ, первый и второй элементы И и элемент НЕ, причем в каждом вычислительном модуле первый и второй информационные входы вычислительного модуля соединены соответственно с информационными входами первого и второго регистров, первый, второй и третий настроечные входы вычислительного модуля соединены соответственно с информационными входами первого, второго и третьего триггеров, синхровход вычислительного модуля соединен с синхровходами первого, второго и третьего регистров, группы регистров и первого, второго и третьего триггеров, выход первого регистра соединен с первыми входами элементов И первой и второй групп, выходы которых соединены соответственно с первыми входами элементов ИЛИ первой и второй групп, выходы которых соединены соответственно с первыми входами умножителя и сумматора, второй вход которого соединен с выходом умножителя, а выход - с первыми входами элементов И третьей и четвертой групп, выходы которых соединены соответственно с первыми входами элементов ИЛИ третьей и четвертой групп, выход первого триггера соединен с первым входом первого элемента И, выход которого соединен с вторыми входами элементов И четвертой группы, прямой выход второго триггера соединен с первым входом второго элемента И, выход которого соединен с первыми входами элементов И пятой группы, выходы элементов И шестой группы соединены с вторыми входами соответствующих элементов ИЛИ второй группы, выходы элементов ИЛИ четвертой группы соединены с информационным входом первого регистра группы, выход j-го регистра группы (J=1.. ., Λ-1, Λ=max{Y,P}) соединен с информационным входом (j+1)-го регистра группы, отличающееся тем, что, с целью повышения быстродействия и сокращения аппаратурных затрат, в каждый вычислительный модуль введены четвертый, пятый и шестой триггеры и третий элемент И, причем в каждом вычислительном модуле второй информационный вход вычислительного модуля соединен с информационным входом четвертого регистра, выход которого соединен с вторым входом умножителя, выход которого соединен с вторыми входами элементов И пятой группы, выходы которых соединены с вторыми входами элементов ИЛИ четвертой группы, третьи входы которых соединены с вторыми входами элементов ИЛИ первой группы и выходами элементов И седьмой группы, первые входы которых соединены с выходом Λ -го регистра группы и первыми входами элементов И шестой группы, вторые входы которых соединены с выходом первого триггера, информационным входом четвертого триггера, вторыми входами элементов И первой группы и входом элемента НЕ, выход которого соединен с вторыми входами элементов И второй, третьей и седьмой групп, выходы элементов И первой группы соединены с вторыми входами элементов ИЛИ третьей группы, выходы которых соединены с информационным входом третьего регистра, выход которого соединен с первым информационным выходом вычислительного модуля, второй информационный выход которого соединен с выходом второго регистра, синхровход четвертого регистра соединен с выходом третьего элемента И, первый и второй входы которого соединены соответственно с синхровходом и третьим настроечным входом вычислительного модуля, первый, второй и третий настроечные выходы которого соединены соответственно с выходами четвертого, пятого и шестого триггеров, синхровходы которых соединены с синхровходом вычислительного модуля, второй вход первого элемента И соединен с инверсным выходом второго триггера, прямой выход которого соединен с информационным входом пятого триггера, информационный вход шестого триггера соединен с выходом третьего триггера, при этом каждый вычислительный модуль реализует следующие фукции:
u ^j+2 = α ^j ;
v ^j+2 = β ^j ;
w ^j+2 = γ ^j ;
H^j+2 = с
где

P=, Z=;
F ^j+1 = f ^j,
где q^j - вспомогательная переменная (значение содержимого регистра 21₁ на j-м такте);
α ^j , β ^j, γ ^j - значения соответственно на первом, втором и третьем настроечных входах вычислительного модуля на j-м такте;
u^j, v^j, w^j - значения соответственно на первом, втором и третьем настроечных выходах вычислительного модуля на j-м такте;
h^j, f^j - значения соответственно на первом и втором информационных входах на j-м такте;
H^j, F^j - значения соответственно на первом и втором информационных выходах на j-м такте.

РИСУНКИ

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