Устройство для умножения трех матриц
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения трех матриц. Цель изобретения - повышение быстродействия и сокращение аппаратурных затрат. Цель достигается тем, что устройство для умножения трех матриц размерностью 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) матрицы за (2n2+2n) тактов. 3 ил., 1 табл.
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных вычислительных системах и устройствах обработки сигналов при перемножении трех матриц.
Цель изобретения - повышение быстродействия и сокращение аппаратурных затрат. На фиг. 1 представлена структурная схема устройства для умножения трех матриц; на фиг.2 - структурная схема устройства для умножения трех матриц для I = Р = 3 и T = Q = 2; на фиг.3 - схема вычислительного модуля. Устройство для умножения трех матриц (фиг.1) содержит первый 1 и второй 2 информационные входы, первый 3, второй 4 и третий 5 настроечные входы, синхровход 6, вычислительные модули 7i(i= ) и выход 8. Вычислительный модуль 7 (фиг.3) содержит первый 9 и второй 10 информационные входы, первый 11, второй 12 и третий 13 настроечные входы, синхровход 14, умножитель 15, сумматор 16, регистры 17-20, группу регистров 21j(j= 1, ) триггеры 22-27, группы элементов И 28-34 группы элементов ИЛИ 35-38, элементы И 39-41, элемент НЕ 42, первый 43 и второй 44 информационные выходы, первый 45, второй 46 и третий 47 настроечные выходы В основу работы устройства для умножения трех матриц Fixp x CpxQ x DQxT положены следующие рекуррентные соотношения: g(opj)= 0, p = , j= 1,J; q = , p = , j= 1,J: g(qpj)= g(qpj-1)+ Cpqdqj; gpj = g(Qpj), p = , j = ; h(oij)= 0, i = , j= ;P = , i= , j = : h(pij)= h(pij-1)+fipgpi; hij= h(pij), 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 на следующем такте записывается в регистр 211, элемент d с выхода регистра 17 через группы элементов И 28 и ИЛИ 38 подается на вход регистра 20 и затем на выход 43. Второй режим задается управляющими сигналами ( , , ) = (1,1,0). На входы 9 и 10 подаются соответственно элементы d и сI. Группы элементов И 28, 31 и 34 и элемент И 41 открыты, на выходе умножителя 15 формируется значение с d (элемент с записан в регистре 19), на выходе сумматора 16 формируется значение cd (на второй вход сумматора подается нулевое значение, так как группа элементов И 33 закрыта нулевым сигналом с выхода элемента НЕ 42), на вход регистра 211подается значение с 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 формируется значение cd, на выходе сумматора 16 - значение g = c d + cI dI (значение cI dI подается на вход сумматора 16 с выхода регистра 21 ), значение g с выхода сумматора 16 подается на вход регистра 211 через группы элементов И 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 = cII d + cI dI (значение cI dIподается на вход сумматора 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 - значение hI = h + +f g, которое подается через группы элементов И 32 и ИЛИ 38 на вход регистра 20. В шестом режиме работы подаются управляющие сигналы ( , , ) = (0,0,1). На входы 9 и 10 подаются соответственно элементы h и f, которые записываются соответственно в регистры 17 и 18. В регистре 19 хранится элемент fI . Открываются группы элементов И 29, 32 и 33. На выходе умножителя 15 формируется значение f Ig, на выходе сумматора 16 - значение hI = h + fI g, которое подается на вход регистра 20. Во всех режимах работы управляющие сигналы , , задерживаются на два такта. На фиг. 1 на входы устройства 1 и 2 подаются соответственно элементы dij(hij) и cij(fij) в моменты времени: t=i+j+2+to,t=i+j+Q+2+to,
t= i+j+2+to,
t= i +j+Q+2+to, где to = -(2 + ), = max{F, p}. На входы 3, 4 и 5 подаются соответственно управляющие сигналы , и в моменты времени:
t=1= j+k+2+to, j =, k =Q;
t=0= j+k+2+to, j =, k =I;
t=1= j++2+to, j =;
t=0= j+k+2+to, j =, k =I ;
t=1= k+3+to, k =I ;
t=0= j+k+2+to, j =, k =I.
На выходе устройства 8 элементы hij формируются в моменты времени
t= i+j+Q+2P+2+to. Последний элемент hIF формируется на ( (Q + I) + 2P + (F - )-м такте. Период подачи элементов (cij, dij, fij) для перемножения матриц следующей задачи равен (Q + I) тактов. Рассмотрим работу устройства для случая I = P = 3 и F = Q = 2. Организация входного и выходного потоков данных приведена на фиг.2. Состояния регистров, триггеров, значения на выходе умножителя и сумматора вычислительных модулей 71, 72 и 73 приведены в таблице. Рассмотрим формирование элемента h11. На первом такте в вычислительном модуле 71 формируется значение c11d11, на втором такте - значение c12d21, на четвертом такте - значение g11 = =c11d11 + c12d21, на седьмом такте - значение h11(1) = h11(10) + f11 g11. В вычислительном модуле 72на девятом такте формируется значение h11(2) = g11(1) + f12g21. В вычислительном модуле 73 на одиннадцатом такте формируется значение h11= h11(3) = h11(2) + +f13g31, которое выдается на выход 8 устройства на тринадцатом такте. Аналогичным образом формируются остальные элементы hij. Устройство перемножает три (n x n)-матрицы за (2n2 + 2n) тактов.
Формула изобретения
u j+2 = j ;
v j+2 = j ;
w j+2 = j ;
Hj+2 = с
где
P=, Z=;
F j+1 = f j,
где qj - вспомогательная переменная (значение содержимого регистра 211 на j-м такте);
j , j, j - значения соответственно на первом, втором и третьем настроечных входах вычислительного модуля на j-м такте;
uj, vj, wj - значения соответственно на первом, втором и третьем настроечных выходах вычислительного модуля на j-м такте;
hj, fj - значения соответственно на первом и втором информационных входах на j-м такте;
Hj, Fj - значения соответственно на первом и втором информационных выходах на j-м такте.
РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7