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

 

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

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

На фиг. 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; c_ij^(k) = c_ij^(k-1) + a_ik b_kj, k, i, j = 1, n; c_ij = c_ij⁽ⁿ⁾, i, j = 1, n Вычислительный модуль 8 (фиг. 3) обладает возможностью реализации следующих функций: V^j+1 = α^j W^j+1 = β^j A^j+2 = a^j B^j+l = b^j
c^j+1 = c^j+ d^j l^j,
d^j=
e^j= где α^j и β^j - значения управляющих сигналов соответственно на первом и втором входах задания режима вычислительного модуля на j-м такте;
V^j+1 и W^j+1 - значения управляющих сигналов соответственно на первом и втором выходах задания режима вычислительного модуля на (j + 1)-м такте;
a^j, b^j и c^j - значения чисел соответственно на втором, первом и третьем информационных входах вычислительного модуля на j-м такте;
A^j, B^j и c^j - значения чисел соответственно на первом, втором и третьем информационных выходах вычислительного модуля на j-м такте;
p = 0, n-1 - параметр, определяемый алгоритмом.

Вычислительный модуль 8 работает в четырех режимах, которые задаются комбинацией управляющих сигналов α и β , подаваемых соответственно на входы 13 и 14.

Во всех режимах элемент b^j подается на вход 10, задерживается регистрами 18 на l тактов и выдается на выход 31 на (j + l + 1)-м такте; элемент a^j подается на вход 11, задерживается регистрами 20 и 22 и выдается на выход (j + 2)-м такте; управляющие сигналы α, β задерживаются соответственно триггерами 24 и 25 на один такт и выдаются на выходы 34 и 35; на выходе сумматора 17 формируется значение с + a b (элемент c подается на вход 12).

В первом режиме (α, β ) = (1,1). При этом элемент b^j через группы элементов И 26 и ИЛИ 28 записывается в регистр 19₁; элемент a^jзаписывается в регистр 21, т. к. элемент И 29 открыт и по заднему фронту тактового импульса осуществляется запись в регистр 21; на выходе сумматора 17 формируется значение c^j + a^j-b^j, которое подается на выход 33.

Во втором режиме (α, β ) = (1,0). Элемент b^j записывается в регистр 19₁. В регистре 21 хранится элемент a^j-p (p = 0, n-1), записанный ранее на (j-p)-м такте. На выходе сумматора 17 формируется значение c^j + a^j-pb^j.

В третьем режиме (α, β ) = (0, 1). На выходе элемента НЕ 30 формируется единичный сигнал, который открывает группу элементов И 27, элемент b^j-n с выхода регистра 19_n-го через группы элементов И 27 и ИЛИ 28 записывается в регистр 19₁. На выходе сумматора формируется значение c^j + a^j b^j-n.

В четвертом режиме (α, β ) = (0, 0). В регистр 19₁-й записывается элемент b^j-n из регистра 19_n-го. В регистре 21 хранится элемент a^j-p. На выходе сумматора 17 формируется значение c^j₊⁺ a^j-p b^j-n.

Рассмотрим работу устройства.

В исходном состоянии все регистры и триггеры вычислительных модулей 8 устанавливаются в нулевое состояние. На выходы 1, 2 и 3 подаются соответственно элементы bj= , k= , a_ik(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-n²-2, j= 1, n, k= , n
На вход 4 постоянно подается нулевое значение.

На входы 5 и 6 подаются управляющие сигналы τ_ij = (α, β) в виде матрицы

Элементы τ_ij подаются в моменты времени
t= ni+j+nn/2-2n-1
На выходе 9 элементы c_ij формируются в моменты времени
t= ni≠j+nn/2-n-2.

Последний элемент c_nn для n-нечетного формируется на (3/2·n²-n/2-1)-м такте, для n-четного - (3/2·n²-2)-м такте.

На фиг. 2 приведена организация подачи входных и выходных потоков для n = 4. В таблице приведены состояния регистров, триггеров, значения на выходе сумматоров 17 и выходных 33 вычислительных модулей 8₁, 8₂, 8₃и 8₄ при вычислении элементов c_ij для 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)-го регистра второй группы, выходы элементов ИЛИ группы соединены с информационными входами первого регистра второй группы, второй вход задания режима модуля соединен с информационным входом второго триггера и первым входом элемента И, выход которого соединен с синхровходом третьего регистра, выход второго триггера соединен с вторым входом задания режима модуля, выход элемента НЕ соединен с вторыми входами элементов И группы, синхровход модуля соединен с синхровходами регистров второй группы, четвертого регистра, второго триггера и вторым входом элемента И.

РИСУНКИ

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