Устройство для матричных операций

 

Изобретение относится к вычислительной технике и может быть пользовано в специализированных машинах и устройствах цифровой обработки сигналов для перемножения ленточной (пхп)матрицы с шириной ленты и)а на плотную (пхп)-матрицу. Цель изобретения - упрощение устройства - достигается тем, что устройство содержит ленту однотипных операционных блоков, при этом операционный блок содержит пять регистров, сумматор, умножитель, три триггера, элемент И и элемент НЕ. Устройство также реализует матричные операции С + АЪ и АВ ,, АВ, ABj и т.д. Особенностями работы устройства являются параллельно-поточная организаций вычислений, синхронность исполнения и коммутации различтсых частей Щ алгоритма перемножения матриц. 2 ил. (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„„SU„„1429127

А1 (у 4 С 06 F 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) ..4224609/24-24 (22) 04.03.87 (46) 07.10.88. Бюл. Ф 37 (72) В.П.Якуш, С.Г.Седухин, Л.Б.Авгуль и А.А. Ленев (53):681.32(088.8) (56).Гун Суньюань. Систолические и волновые матричные процессоры для высокопроизводительных вычислений.

ТИИЗР, т.72, 1984, У 7, с.141, рис.9.

Авторское свидетельство СССР В 1388897, кл. G 06 F 15/347, 1986, (54) УСТРОЙСТВО ДЛЯ МАТРИЧНЫХ ОПЕРАЦИЙ (57) Изобретение относится к вычислительной технике и может быть ис пользовано в специализированных машинах и устройствах цифровой обработки сигналов для перемножения ленточной (п п)=матрицы с шириной ленты м)д на плотную (пхп)-матрицу. Цель изобретения — упрощение устройства — достигается тем, что устройство содержит ленту однотипных операционных блоков, при этом операционный блок содержит пять регистров, сумматор, умножитель, три триггера, элемент И и элемент НЕ.

Устройство также реализует матричные операции С + АВ и AB,. AB, AB и т.д.

Особенностями работы устройства являются параллельно-поточная органиэация вычислений, синхронность исполнения и коммутации различных частей g алгоритма перемножения матриц. 2 ил.

1429127

Изобретение относится к вычисли1 тельной технике и может быть использовано в специализированных вычислительных машинах и устройствах цифро5 вой обработки сигналов для перемножения ленточной (nxn)-матрицы на плотную (nm) -матрицу.

Цель изобретения — упрощение устройства, !О

На фиг.l представлена структурная схема устройства для перемножения матриц для случаев и 5, М» = 4, Р»1 = 3 и ц„ = 2; на фиг.2 — функциональная схема операционного блока. !5

Устройство для перемножения матриц (фиг.l) содержит первую группу информационных входов 1;,(i - Т, ц)), вторую группу информационных входов 2 »(1.

1» P ; j 1» q„)» ТРетью ГРУппУ 20 информационных входов 3j (j = 1, и), синхровход 4, операционные блоки

5Ц (i,j 1, и) и выходы 6 (i = 1, и).

Операционный блок 5 (фиг.2) содержит первый 7, второй 8, третий 9 25 входы, регистры 10 — 14, триггеры 1517, умножитель 18, сумматор 19, элемент НЕ 21, синхровход 22, первый вы" ход 23, второй выход 24, третий выход 25. 30

В основу работы устройства положен ! алгоритм умножения (n к n)-ленточной матрицы А = (а „ ).с шириной ленты

»-»4. = Ра + q — 1 на плотную (n x n) матрицу В = (Ьц ), определяющий Pe". 35 эультирующую (n к п)-матрицу С = (c;> ) на основании следующих рекурентных (С(ъ)) соотношений для С!

0: (<) (к- 4)

С =С. +а;„Ь„;

У (К) (1 (3 (К) j K = I,п

f с,)

С Ctj 1) =1 где ((i) = макс(О,i — Рс,); P(K) макс(1, К вЂ” с1<» + 1) p(K) HH(n Рс» + K 1)» Е (i) мин(п»i +

+ q — 1); К = Т,п.

Рассмотрим работу операционного блока 5. Регистры 10 и 14, построенные на двухтактных триггерах, регистры Il — 13, построенные на однотактных -риггерах, и двухтактные триггеры !5 - 17 устанавливаются в начальное состояние. На входы 7 и 9 подаются с дополнительным единичным разрядом соответственно элементы С;, 1 и

bt I, а на вход 8 — элемент atj . По переднему фронту тактового импульса элемент а > записывается в регистры

11 и 12. Запись элемента а в регистр 12 осуществляется с выхода регистра 11 при наличии единичного сигнала на входе разрешения записи регистра 12, который подается с инверсного выхода, триггера 16. По заднему фронту тактового импульса в регистры

10 и 14 записываются соответственно элементы С и be, в регистр 13 записывается элемент а;>, триггеры 1517 устанавливаются в единичное состояние. Триггер 16 устанавливается в единичное состояние единичным сигналом, который подается на его информационный вход, с выхода элемента И 20.

При этом запись в регистр 12 запрещается, так как на инверсном выходе триггера 16 будет нулевой сигнал. На выходе умножителя 18 формируется значение atj Mj, а на выходе сумматора

19 — значение Ctj + at> bt . Для записи в регистр 12 нового значения элемента а необходимо на (тп+1)-е разряды входов 7 и 9 подать нулевые сигналы, по заданному фронту тактового импульса триггер 16 устанавливается в начальное сосТояние и при этом разрешается запись в регистр 12.

Устройство работает следующим образом. На первые информационные входы 1, подаются по тактам начальные значения

С;7, 1,. на вторые 2 и третьи Зт входы подаются соответственно элемен»

С1) СУ ты а, и bt, 1, где .t — номер такта, at„ — элементы ленточной (n кп)— матрицы А, Ы вЂ элементы плотной (и к n)-матрицы. На входы 1 и 3 одновременно с элементами С, и btg подаются дополнительные единичные разряды (фиг,l).

На нулевом такте на входы I!, 2« и 3 подаются соответственно элементы

С„ „, 1; а„„и Ь„„, 1. На выходе сумматора 19 в операционном блоке 5,» . ж (o) формируется значение» « = С,» + а„„Ь«, На первом такте на входы 1 и 1 подаются соответственно значения

С, 1 и С, 1, на входы 2 „, 2 и

»

2„ — соответственно элементы а,д, 9! 27

25

Устройство для матричных ойерацийр содержащее ленточную матрицу из

n -(n-P) (п-Р+l ) /2-(n-q) (n-q+ l )/2 операционных блоков, где n — размерность

З0 квадратных матриц, P u q — количество элементов соответственно первого столбца и первой строки ленточной матрицы, причем ь-й информационный вход первой группы устройства подключен к первому входу (i, i)-го операционно.го блока, (i = Г, P}, второй вход которого подключен к i-му информационному входу второй группы устройства (i = l P) второй вход i j-го операцн40

45 з .142 а и. а, на входы З„и З вЂ” соот"

» 4 ветственно элементы b»,z, 1 и Ь, 1.

В операционном блоке 5»» элемент а, 1 записывается в регистр !3, на выходе. сумматора 19 формируется значение

C<) (o)

C«, = С»» + а„„ Ь» . В операционном блоке 5„в регистр 10 записывается значение С„», в регистр 12 — элемент а„, в регистр 14 — элемент Ь », на выходе сумматора 19 формируется знай) (s) чение C« = С и + а, Ъ „р которое подается на выход 6» . В операционном блоке 5 в,регистр 10 записывается значение С», в регистр 12 - элемент а"», в регистр 14 — элемент b« на выходе сумматора 19 формируется знаЙ) (9) чение С = С » + ае„Ъ+, .

На втором такте на входы 1„, 1 и

1>у подаются соответственно значения

Е

С»ь, С и С> на входы 211 р 2»

2 и 2 — соответственно элементы

2 . 2 и 2 а, а, аз и а>, на входы 3» и с

3 —, соответственно элементы Ь» и

Ь, В операционном блоке 5„» форми"

Й) (o) . руется значение С = С1ь + а„„b»» в регистр 13 записывается элемент а, а

В операционном блоке 5«формируется (а)

С = С + а „ Ь„, в регистр 13 заа писывается элемент аы . В операцион-!

:ном блоке 5>й в регистр 12 эаписываэ. ется элемент а, в регистр 10 — знаты (»)

Л чение Сд», в регистр t4 - элемент Ь,н, 5

15 ет аналогичным Ьбраэом. Особенностью работы устройства является то,что элемент ау,! записывается и хранится в регистре 12 операционного блока 5,, Сформированные значения С " результирующей (n к и)-матрицы С = (С; ) выдаются на выходе 6! устройства, где

t — номер такта (фиг.1 ).

Таким образом, если значения элементов С на входе 1 подаются нулевыми, то устройство реализует матричную операцию АВ, если С 0 — устрой- ство реализует матричную операцию

С + АЗ.

Кроме того, так как элементы а;>. ленточной матрицы А постоянно хранятся в регистрах 12 ПЭ 51>, то устройство дополнительно выполняет перемножение цепочки матриц АВ<, АВ<, АВЗ и теде

Формула изобретения онного блока подключен к j ìó информационному входу второй группы устРойства, (j = 2й с1) р тРетий вход ij-ro операционного блока подключен к j — му информационному входу третьей группы устройства, (j = 1, q), синхровход устройств а подключ ен к с инхр ов ход ам операционйых блоков, о т л и ч а ю—

50 на выходе сумматора 19 формируется

Cz) (») значение С! C«+ az> Ь1 (. В опеРационнам блоке 5й» в регистр 12 записывается элемент а, в регистр 10— значение С,», в регистр 14 - элемент

b, на выходе сумматора 19 формиру(») (о2 . ется значение С .(С » + а „Ь»» . На последующих тактах устройство работащ е е с я тем, что, с целью упрощения, первый вход (i, i — P + !)-го операционного блока подключен к 1-му информационному входу первой группы устройства, (! = 7+1. и), первый выход ij-го операционного блока подключен к первому входу (i,j + 1)-го операционного блока (i=i,n; j = l; n-l;

j - q + 2ф i P + j), третий вход (j — q + 1; j)-ro операционного блока подключен к 1-му информационному входу

5 2 4291 третьей группы устройстве, j йь Г; и), -второй выход ij-го операционного блока подключен к второму входу (i+1, j+I )-го операционного блока, (i., j !, n-I; j — q < i j + p), тРетий выход ij-го операционного блока подключен к третьему входу (i+1 j)-ro

27 6 операционного блока, (i 1, п-1;

j = I, и; j — .q (i (j + Р-2), первый выход (j — q + 1, j)-ro операционного блока подключен к (3 — q + 1)-му выходу устройства, (j = Г, и), первый выход (n, п)-го операционного блока подключен к п-му выходу устройства.

)429 j 27

14291 27

Составитель M.Ñèëèí

Редактор В..Бугренкова Техред Л.Сердюкова Корректор M.Âàñèëüeâà

Заказ 5127/46 Тираж 704 Подписное

ВЯИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4