Устройство для перемножения потока @ - матриц Советский патент 1993 года по МПК G06F15/347 

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

Цель изобретения - сокращение аппаратурных затрат.

На фиг.1 представлена структурная схема устройства для перемножения М пхп- матриц; на фиг2. - структурная схема устройства для случая и п 3, на фиг.З и 4 - функциональные схемы соответственно вычислительных модулей, выполняющие функции, описанные в формуле изобретения, на фиг.5 и 6 - таблицы, поясняющие работу устройства.

Устройство для перемножения потока nxn-матриц (фиг.1) содержит информационные входы первой группы 1| (I 1,2). инфор- мационные входы второй группы 2 (J 1,п), настроечные входы 3i, синхровход 4, вычислительные модули 5j и 6j, информационные выходы первой 7j и второй 8j групп.

Вычислительный модуль 5(фиг.З) содержит первый 9, второй 10 и третий 11 информационные входы, первый 12 и второй 13 разряды настроечного входа, синхровход 14, умножитель 15, сумматор 16, регистры 17,18 и 9j, триггеры 20 и 21, группы элементов И 22,23, 24 и 25, группы элементов ИЛИ 26,27,28, элемент НЕ 29, первый 30, второй 31 и третий 32 информационные выходы, первый 33 и второй 34 настроечные выходы.

Вычислительный, модуль 6 (фиг.4) содержит первый 35 и второй 36 информационные входы, первый 37 и второй 38 настроечные входы, синхровход 39, умножитель 40, сумматор 41, регистры 42, 43 и 44, триггеры 45 и 46,.группу элементов И 47, элемент И 48, первый 49, второй 50 и третий 51 информационные выходы, первый 52 и второй 53 настроечные выходы.

В основу работы устройства положен алгоритм перемножения М nxn-матриц, который задается следующими рекуррентными соотношениями:

т 2,3,...,М:

VJ

ЧУ

VI

ю

00

bur-air- bir jj UT;

bijkjn bijh-r + aikm fbkr 1.k 2.n bi|m bijnm,

В обозначении aij1™ индекс m указывает номер матрицы, а индекс t - номер такта работы устройства.

Устройство (фиг.2) работает следующим образом.

На вход 1i подаются элементы матриц (нечетных) А и А в моменты времени t (i-1)n + j - 1 + (m - 1)/2(n2 + 1) на вход г - элементы матриц (четных) А в моменты времени t I - 1 + jn + (m - 2)/2(n2 + 1), на входы 2i - элементы матрицы в 1 в моменты времени t I + j - 2, на входы 3i и Зг - соответствующие управляющие сигналы

(d,fi. Значения ( d,f$ (,) могут быть произвольными. В таблицах на фиг.5 и 6 приведены состояния регистров и триггеров, значения на входах и выходах вычисли- тельных модулей 5 и б устройства. На выходах 7j устройства формируются элементы bij произведения нечетного числа матриц М в моменты времени t i + j + (M 1)/2(n2 + 1)-2, причем последний элемент bnn формируется на 2п + (М-1)/2(п2 + такте. На выходах 8j устройства формируются элементы Ъ произведения четного числа матриц М в моменты времени t ni + j + (M - 2)/2 (n2 + 1) - 1, последний элемент bnn формируется в момент времени nl + n + (М 2)/2(n2+1)-1.

Формула из обретения Устройство для перемножения потока nxn-матриц, содержащее 2п вычислительных модулей, причем первый и второй информационные входы первой группы входов устройства подключены к первым информационным входам соответственно первого и(п+1)-го вычислительных модулей, первые информационные выходы 1-го и (I + п)-го (i 1, n - 1) вычислительных модулей подключены к первым информационным входам соответственно (i + 1)-го и (i + n + 1)-ro вычислительных модулей, i-й информационный вход второй группы входов устройства подключен к второму информационному входу 1-го вычислительного модуля, второй информационный выход которого подключен к второму информационному входу (i + п)-го вычислительного модуля, второй и третий информационные выходы которого подключены соответственно к i-му информационному выходу первой группы выходов устройства и к третьему информационному входу 1-го вычислительного модуля, третий информационный выход которого подключен к 1-му информационному выходу второй

5

группы выходов устройства, синхровход которого подключен к синхровходам всех вычислительных модулей, первый и второй настроечные входы устройства подключены соответственно к настроечным входам первого и (п + 1)-го вычислительных модулей, настроечные выходы 1-го и (I + п)-го вычислительных модулей подключены к настроечным входам соответственно (I + 1)-го и (i + n + 1)-го вычислительных модулей, отличающееся тем, что, с целью сокращения аппаратурных затрат, вычислительные модули с первого по n-й выполнены с возможностью реализации следующих функций:

vJ +

A + 1 aJ

CJ + 1 аЫ а Ыесли (о,) (1,1)

если (о1. {$, 0м) (0,1,1) d + a bj, если (./З1) (1,0) с1 + а1 Ьн, если (о1,/, ) (0,0,1)

где - значения соответственно на первом и втором настроечных входах вычислительного модуля на j-м такте;

U и г - значения соответственно на первом и втором настроечных, выходах вычислительного модуля на j-м такте;

а и А - значения соответственно на первых информационных входе и выходе вычислительного модуля на j-м такте;

Ы - значения на втором и третьем информационных входах вычислительного модуля на j-м такте;

с - значения на втором и третьем информационных выходах вычислительного модуля на j-м такте;

вычислительные модули с (п + 1)-го по 2п-й выполнены с возможностью реализации следующих функций:

50

55

где dj - значение на втором информационном входе вычислительного модуля на j-м такте.

-J

-J

NJ

со

Изобретение относится к области вычислительной техники и может быть использовано в высокопроизводительных вычислительных машинах и устройствах обработки сигналов для перемножения цепочки матриц. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство для перемножения М(пхп) матриц содержит 2п вычислительных модулей, выполняющих основную арифметическую операцию над числами вида с+а«Ь. В основу работы устройства положена параллельногпоточная организация вычислений. 6 ил.

,6 ,

повторяе/лся „-ч Т г

Фиг.

со

Of

r

CD ГЈ(П)ъ(ОУ$(ОЩи 0)Ј10 0)а(М)б(1ЩО 0)и(ОЩг&Ъ

t« # # Ј «-### #

°Z°Z° ° & S &№##&&&&%&

,(оч) (оч)мшо о) мю (oi) joty) т) т) (Щто окс о) м щ voi )

1 k s S 8 f at и ii с / si Si ц si Bi

фие.Ь

I