УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ Российский патент 1994 года по МПК G06F15/347 

Описание патента на изобретение RU2024933C1

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

Известно устройство для перемножения трех матриц 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} = X·D, bpj= xpq· dqj
Y= { yij} = A·B, 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)+ aip·bpj ,
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 формируется значение <181>. b, которое подается через группу элементов И 41 и ИЛИ 49 на информационный вход регистра 17 для записи на следующем такте.

В шестом режиме работы (α , β , γ) = =(1,0,0). Формируются сигналы δ6 = 1 и μ6 =1. Сигнал δ6 открывает группу элементов И 45. В регистр 181 записывается содержимое регистра 18р. Сигнал μ6 открывает группы элементов И 34, 37, 39, 44 и элемент И 59. На выход 63 подается значение а. На выходе сумматора 20 формируется значение< Рег.17 >+ <Рег.181> . 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 >+ <Рег.181> . 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).

Похожие патенты RU2024933C1

название год авторы номер документа
УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ 1989
  • Якуш В.П.
  • Косьянчук В.В.
  • Лиходед Н.А.
  • Соболевский П.И.
SU1819020A1
УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ N X N МАТРИЦ 1990
  • Якуш В.П.
  • Косьянчук В.В.
  • Лиходед Н.А.
  • Соболевский П.И.
RU2037199C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ (N X N)-МАТРИЦЫ 1992
  • Якуш В.П.
  • Лиходед Н.А.
  • Соболевский П.И.
  • Тиунчик А.А.
RU2012050C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ 1991
  • Якуш В.П.
  • Лиходед Н.А.
  • Соболевский П.И.
  • Косьянчук В.В.
RU2011221C1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1989
  • Якуш В.П.
  • Косьянчук В.В.
  • Лиходед Н.А.
  • Соболевский П.И.
  • Чернега П.П.
SU1819019A1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1991
  • Якуш В.П.
  • Лиходед Н.А.
  • Косьянчук В.В.
  • Соболевский П.И.
RU2012049C1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1990
  • Якуш В.П.
  • Косьянчук В.В.
  • Лиходед Н.А.
  • Соболевский П.И.
RU2037197C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ 1990
  • Якуш В.П.
  • Лиходед Н.А.
  • Косьянчук В.В.
  • Тиунчик А.А.
SU1779180A1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 1991
  • Якуш В.П.
  • Лиходед Н.А.
  • Косьянчук В.В.
  • Соболевский П.И.
RU2012048C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 1994
  • Якуш Виктор Павлович[Ru]
  • Драницин Олег Николаевич[Ru]
  • Лиходед Николай Александрович[By]
  • Соболевский Павел Иосифович[By]
RU2049351C1

Иллюстрации к изобретению RU 2 024 933 C1

Реферат патента 1994 года УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ

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

Формула изобретения RU 2 024 933 C1

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ТРЕХ МАТРИЦ, каждая размерностью 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 ;
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-м такте.

Документы, цитированные в отчете о поиске Патент 1994 года RU2024933C1

Авторское свидетельство СССР N 1832990, кл
Приспособление для точного наложения листов бумаги при снятии оттисков 1922
  • Асафов Н.И.
SU6A1

RU 2 024 933 C1

Авторы

Якуш В.П.

Лиходед Н.А.

Косьянчук В.В.

Соболевский П.И.

Даты

1994-12-15Публикация

1990-12-04Подача