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

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

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для умножения матриц. Цель изобретения - сокращение аппаратурных затрат и повышение быстродействия устройства. Устройство содержит n вычислительных модулей, где n - порядок перемножаемых матриц, причем каждый вычислительный модуль содержит две группы регистров, четыре регистра, умножитель, сумматор, два триггера, две группы элементов И, группу элементов ИЛИ, элемент И и элемент НЕ. 3 ил. 1 табл.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

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


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

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

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

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2011221
Класс(ы) патента: G06F15/347
Номер заявки: 5013894/24
Дата подачи заявки: 03.07.1991
Дата публикации: 15.04.1994
Заявитель(и): Якуш В.П.; Лиходед Н.А.; Соболевский П.И.; Косьянчук В.В.
Автор(ы): Якуш В.П.; Лиходед Н.А.; Соболевский П.И.; Косьянчук В.В.
Патентообладатель(и): Якуш Виктор Павлович
Описание изобретения: Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для умножения матриц.
На фиг. 1 представлена структурная схема устройства для умножения матриц; на фиг. 2 - структурная схема устройства для умножения матриц для n = 4; на фиг. 3 - функциональная схема вычислительного модуля.
Устройство для умножения матриц содержит первый 1, второй 2 и третий 3 информационные входы, вход логического нуля 4, первый 5 и второй 6 входы задания режима, синхровход 7, вычислительные модули 8i (i = 1, n) и выход 9.
Вычислительный модуль 8 (фиг. 3) содержит первый 10, второй 11 и третий 12 информационные входы, первый 13 и второй 14 входы задания режима, синхровход 15, умножитель 16, сумматор 17, первую группу 18 регистров 8, вторую группу регистров 19, первый 20, второй 21, третий 22 и четвертый 23 регистры, первый 24 и второй 25 триггеры, первую 26 и вторую 27 группы элементов И, группу элементов ИЛИ 28, элемент И 29, элемент НЕ 30, первый 31, второй 32 и третий 33 информационные выходы, первый 34 и второй 35 выходы задания режима.
В основу работы устройства положен алгоритм умножения двух (n x n)-матриц, основанный на рекурентных соотношениях
сij(o) = 0, i, j = 1, n;
cij(k) = cij(k-1) + aik bkj, k, i, j = 1, n;
cij = cij(n), i, j = 1, n
Вычислительный модуль 8 (фиг. 3) обладает возможностью реализации следующих функций:
Vj+1 = αj
Wj+1 = βj
Aj+2 = aj
Bj+l = bj

cj+1 = cj+ dj lj,
dj=
ej= где αj и βj - значения управляющих сигналов соответственно на первом и втором входах задания режима вычислительного модуля на j-м такте;
Vj+1 и Wj+1 - значения управляющих сигналов соответственно на первом и втором выходах задания режима вычислительного модуля на (j + 1)-м такте;
aj, bj и cj - значения чисел соответственно на втором, первом и третьем информационных входах вычислительного модуля на j-м такте;
Aj, Bj и cj - значения чисел соответственно на первом, втором и третьем информационных выходах вычислительного модуля на j-м такте;
p = 0, n-1 - параметр, определяемый алгоритмом.
Вычислительный модуль 8 работает в четырех режимах, которые задаются комбинацией управляющих сигналов α и β , подаваемых соответственно на входы 13 и 14.
Во всех режимах элемент bj подается на вход 10, задерживается регистрами 18 на l тактов и выдается на выход 31 на (j + l + 1)-м такте; элемент aj подается на вход 11, задерживается регистрами 20 и 22 и выдается на выход (j + 2)-м такте; управляющие сигналы α, β задерживаются соответственно триггерами 24 и 25 на один такт и выдаются на выходы 34 и 35; на выходе сумматора 17 формируется значение с + a b (элемент c подается на вход 12).
В первом режиме (α, β ) = (1,1). При этом элемент bj через группы элементов И 26 и ИЛИ 28 записывается в регистр 191; элемент ajзаписывается в регистр 21, т. к. элемент И 29 открыт и по заднему фронту тактового импульса осуществляется запись в регистр 21; на выходе сумматора 17 формируется значение cj + aj-bj, которое подается на выход 33.
Во втором режиме (α, β ) = (1,0). Элемент bj записывается в регистр 191. В регистре 21 хранится элемент aj-p (p = 0, n-1), записанный ранее на (j-p)-м такте. На выходе сумматора 17 формируется значение cj + aj-pbj.
В третьем режиме (α, β ) = (0, 1). На выходе элемента НЕ 30 формируется единичный сигнал, который открывает группу элементов И 27, элемент bj-n с выхода регистра 19n-го через группы элементов И 27 и ИЛИ 28 записывается в регистр 191. На выходе сумматора формируется значение cj + aj bj-n.
В четвертом режиме (α, β ) = (0, 0). В регистр 191-й записывается элемент bj-n из регистра 19n-го. В регистре 21 хранится элемент aj-p. На выходе сумматора 17 формируется значение cj++ aj-p bj-n.
Рассмотрим работу устройства.
В исходном состоянии все регистры и триггеры вычислительных модулей 8 устанавливаются в нулевое состояние. На выходы 1, 2 и 3 подаются соответственно элементы bj= , k= , aik(i= , k= ) и bj= , k= в соответствующие моменты времени: t= -ni-k+nn/2-2n+1, i, k= ; t= nk+j+nn/2-1, j= , k= ; t= nk+j+nn/2-n2-2, j= 1, n, k= , n
На вход 4 постоянно подается нулевое значение.
На входы 5 и 6 подаются управляющие сигналы τij = (α, β) в виде матрицы

Элементы τij подаются в моменты времени
t= ni+j+nn/2-2n-1
На выходе 9 элементы cij формируются в моменты времени
t= ni≠j+nn/2-n-2.
Последний элемент cnn для n-нечетного формируется на (3/2·n2-n/2-1)-м такте, для n-четного - (3/2·n2-2)-м такте.
На фиг. 2 приведена организация подачи входных и выходных потоков для n = 4. В таблице приведены состояния регистров, триггеров, значения на выходе сумматоров 17 и выходных 33 вычислительных модулей 81, 82, 83и 84 при вычислении элементов cij для n = 4. (56) Kung H. T. Leiserson C. E. Systolic Arrayt (for VLSI)-Sparse Matrix Proc. 1976, Society for Industrial and Applied Mathematicf, 1979, p. 262, fig 3-2.
Авторское свидетельство СССР N 1619305, кл. G 06 F 15/347, 1991.
Формула изобретения: УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ МАТРИЦ, содержащее n вычислительных модулей (n - разрядность перемножаемых матриц), каждый из которых содержит первую группу регистров, первый, второй и третий регистры, умножитель, сумматор, первый триггер и первую группу элементов И, причем первый и второй информационные входы и первый вход задания режима первого вычислительного модуля соединены соответственно с первым и вторым информационными входами и первым входом задания режима устройства, первый информационный выход i-го вычислительного модуля (i = , где - число, округленное в сторону большего целого) соединен с первым информационным входом (i + 1)-го вычислительного модуля, второй информационный выход и первый выход задания режима j-го вычислительного модуля (j = 1, . . . , n - 1) соединен соответственно с вторым информационным входом и первым входом задания режима (j + 1)-го вычислительного модуля, третий информационный выход n-го вычислительного модуля соединен с выходом устройства, синхровход которого соединен с синхровходами всех вычислительных модулей, при этом в каждом из вычислительных модулей второй информационный вход модуля соединен с информационным входом первого регистра, выход которого соединен с информационным входом второго регистра, выход которого соединен с вторым информационным выходом модуля, первый вход задания режима которого соединен с информационным входом первого триггера, выход которого соединен с первым выходом задания режима модуля, выход умножителя соединен с входом первого слагаемого сумматора, синхровход модуля соединен с синхровходами первого и второго регистров, первого триггера и регистрами первой группы, отличающееся тем, что, с целью сокращения аппаратурных затрат и повышения быстродействия, в каждый из вычислительных модулей введены вторая группа регистров, четвертый регистр, второй триггер, вторая группа элементов И, элемент И и элемент НЕ, причем третий информационный вход и второй вход задания режима первого вычислительного модуля соединены соответственно с входом логического нуля и вторым входом задания режима устройства, третий информационный выход и второй выход задания режима j-го вычислительного модуля соединены соответственно с третьим информационным входом и вторым входом задания режима (j + 1)-го вычислительного модуля, первый информационный вход n-го вычислительного модуля соединен с третьим информационным входом устройства, первый информационный вход m-го вычислительного модуля m = соединен с первым информационным выходом (m + 1)-го вычислительного модуля, при этом в каждом вычислительном модуле первый информационный вход модуля соединен с первыми входами элементов И первой группы и информационным входом первого регистра первой группы, выход K-го регистра первой группы K = l = n+1 для вычислительных модулей с первого по -й; l = n - 1) для вычислительных модулей с -го по n-й) соединен с информационным входом (K + 1)-го регистра первой группы, выход l-го регистра первой группы соединен с первым информационным выходом модуля, второй информационный вход которого соединен с информационным входом третьего регистра, выход которого соединен с первым входом умножителя, второй вход которого соединен с выходом первого регистра второй группы, третий информационный вход модуля соединен с информационным входом четвертого регистра, выход которого соединен с входом второго слагаемого сумматора, выход которого соединен с третьим информационным выходом модуля, первый вход задания режима соединен с входом элемента НЕ и вторыми входами элементов И первой группы, выходы которых соединены с первыми входами элементов ИЛИ группы, вторые входы которых соединены с выходами элементов И второй группы, первые входы которых соединены с выходом n-го регистра второй группы, выход j-го регистра второй группы соединен с информационным входом (j + 1)-го регистра второй группы, выходы элементов ИЛИ группы соединены с информационными входами первого регистра второй группы, второй вход задания режима модуля соединен с информационным входом второго триггера и первым входом элемента И, выход которого соединен с синхровходом третьего регистра, выход второго триггера соединен с вторым входом задания режима модуля, выход элемента НЕ соединен с вторыми входами элементов И группы, синхровход модуля соединен с синхровходами регистров второй группы, четвертого регистра, второго триггера и вторым входом элемента И.