Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для перемножения трех матриц. Цель изобретения - повышение быстродействия и сокращение аппаратурных затрат. Цель достигается тем, что устройство для умножения трех матриц размерностью 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. С помощью поисковых систем

   С помощью Google:    

   С помощью Яндекс:  

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2024932
Класс(ы) патента: G06F15/347
Номер заявки: 4855128/24
Дата подачи заявки: 30.07.1990
Дата публикации: 15.12.1994
Заявитель(и): Якуш Виктор Павлович[RU]; Косьянчук Виктор Васильевич[BY]; Лиходед Николай Александрович[BY]; Соболевский Павел Иосифович[BY]
Автор(ы): Якуш Виктор Павлович[RU]; Косьянчук Виктор Васильевич[BY]; Лиходед Николай Александрович[BY]; Соболевский Павел Иосифович[BY]
Патентообладатель(и): Якуш Виктор Павлович (RU)
Описание изобретения: Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных вычислительных системах и устройствах обработки сигналов при перемножении трех матриц.
Цель изобретения - повышение быстродействия и сокращение аппаратурных затрат.
На фиг. 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 формируется значение c˙d (на второй вход сумматора подается нулевое значение, так как группа элементов И 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 формируется значение c˙d, на выходе сумматора 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 I˙g, на выходе сумматора 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) тактов.
Формула изобретения: УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ, каждая размерностью 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 ;
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-м такте.