Матричный вычислитель Советский патент 1988 года по МПК G06F17/16 

со о | и

Изобретение относится к вычислительной технике и может быть использовано для вычисления произведения цепочки матриц произвольной длины, произведения строки на матрицу, столбУУ . Ф ца на матрицу, возведения матрицы в степень. Матричный вычислитель содержит блок 1 ввода, умножитель 2, блок 3 синхронизации и матрицу Р вычислительных блоков 4. Найденные закономерности при вычислении произведения цепочки матриц, представляемого как произведение ядра результирующей матрицы, вычисляемого в умножителе 2 и общего для всех элементов результирующей матрицы, на соответствующую строку первой матрицы справа и столбец последней матрицы слева позволили осуществить вычисление всех элементов результирующей матрицы за три такта работы блока 3 синхронизации. 1 з.п.ф-лы, 7 ил. с 9 (Л с:

Фиг.1

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

Цель изобретения - повышение быстродействия з стройства при вычислении произведения нескольких матриц,

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

Устройство содержит блок 1 ввода, умножитель 2, блок 3 снгосронизации и матрицу из вычислительных бло- ков 4,

Умножитель 2 имеет группу блоков умножения, каждый из которых содержи соединенные последовательно узлы 5 умножения и группу блоков 6 элементов И.

Вьршслительный блок 4 образуют KOMi iyTaTop 7, группа блоков 8 элементов ИЛИ, группа узлов 9 умножения и группа регистров 10, сумматор 11.

Коммутатор 7 состоит из групп элементов И 12 и 13 .и группы элементов ИЛИ 14.

Блок 3 синхронизации содержит счетчик 15, деишфратор 16, элемент 17 задержки и элемент 18 ИЛИ,

Устройство работает следующим образом.

В блок 1 вводятся элементы перемножаемых матриц. С выхода блока 1 элементы перемножаемых матриц подаются в умножитель 2.и вычислительные блоки 4 матрицы. В умножителе 2 формируются соответствующие сомножители (. .. ), ,..,,P, j 1,..., P, где P - порядок перемножаемых матриц, N - количество перемножаемых матриц. ГГосле формирования сомножителей в умножителе 2 на вход пуска блока 3 подается сигнал, по которому с первого выхода блока 3 поступает импульс на вход синхронизации умножите ля 2 и на первый вход синхронизации блоков 4, На первые группы информационных входов блоков./ ч коммутатора 7 поступают элементы i-й строки

o

0

5

5

5 о

i-2

1р

первой матрицы а

На вькодах блоков 12 формируются соответствующие элементы, согласно алгоритму представления любого элемента результирующей матрицы С ,-j , которые поступают через элементы ИЛИ 14-, на первые входы соответствующих узлов 9, на вторые входы которых поступают соответствующие сомножители (а., к а jj .. .а Г ) . На выходах узлов 9 формируются соответствующие сомножители (alj X а я а . X... а ) , которые записываются в регистры 10;. Запись в регистры lOj осздцествляется по заднему фронту импульса, который подается на вход разрешения записи регистра 10; через элемент ИЛИ 20, По окончании первого тактового импульса, второй тактовый импульс подается на вход элемента РШИ 20 с задержкой t, где t т - время переключения триггера. Задержка t- осуществляется элементом 17 задержки распределения 5 импульсов. По второму тактовому сигналу элементы j-ro столбца N-й матрицы поступают на- входы второй группы блока 4 jj и коммутатора 7, при этом элементы И 6 и 12 блокируются, так как на вход синхронизации умножителя 2 и на первьй уп- равляющий вход коммутатора 7 импульс не подается. При этом с выходов регистров 10: через элементы ИЛИ В/ подаются соответствующие сомножители ,х а ) на вторые вхо(alix: аТ. ха.

ч

ды узлов 9; умножения, на первые входы которых с выходов коммутатора 7 поступает соответствующие элементы j-ro столбца N-й матрицы. На выходах 0 узлов 9 j формируются соответствующие

сомножители (.- а к . .. .а , ) , ко- 1} ) J 1J

торые записываются в регистры 10 и с выходов которых поступают на.j-e входы сумматора 11 соответствунщего ,вычислительного блока 4 jj . На выходе сумматора 24 блока формируются значе шя элементов С-- результирующей матрицы.

Таким образом, в основу работы предлагаемого устройства положен метод точного определения любого из элементов результирующей матрицы, не требующий использования известной процедуры перемножения матриц.

Определение С ;; -го элемента результирующей матрицы, где N - число перемножения матриц, эквивалентно умножению матрицы Д,, являющейся произведением с второй по предпослед

Анализ выявленных закономерностей расположения элементов перемножаемых матриц позволяет указать следующий алгоритм представления любого элемен- та С .

2,В каждом последующем Р-м столбце сомножителей, кроме последнего, т.е. , 3, ,.., N-1, располагаются последовательно элементы столбцов матрицы Ар, т.е, элементы а, , .- ( i 11 11 ) , -

4f

Vr«

повторяется г группа из г «- раз.

р-1

MS

причем каждый элемент

раз, затем вся эта

элементов повторяется

ТЫ а ; , . а

, м

Г) M-i

a fj, каждый из ко

,,- - 2J

торых повторяется г раз

В качестве примера представлен элемент С t перемножаемых четырех матриц ,-А ,.А , А, Для наглядности проведены горизонтальные яинии, определяющие границы повторяемости по вертикали сомножителей, обведены повторяющиеся по вертикали группы сомножителей. Кроме того, пунктирной линией обведена группа элементов (яд ро) , являющаяся общей для. всех элементов соответствующей результирующей матрицы С.

0

5

0

5

0

5

необходимо сформировать N столбцов элементов, которые подвержены в каждом столбце указанным выше двум процессам повторения элементов и групп элементов, а затем осуществить последовательное перемножение соответствующих элементов каждого сформированного столбца. Поскольку часть сомножителей (обведенная пунктирной линией) одна и та же для всех элементов ре- . зультирующей матрицы С, а меняются . только элементы в крайних столбцах, в зависимости от ij-ro номера элемента результирующей матрицы, то необходимо осуществить соответствующий

.выбор элементов при формировании этих

iдвух столбцов.

Метод точного определения любого элемента матрицы С позволяет, кроме перемножения N матриц, осуществлять перемножение матриц на матрицу столбец или на матрицу строку, возведение матрицы в произвольнук степень от второй до N-й. Например, для перемножения двух матриц, необходимо результирующую матрицу представить как . ,. i , где 1 - единичная матрица, для возведения матрицы А в N-ю степень - .. ., а в ( - А

степень

,д N- 1«

h . Х )

Временные диаграммы работы устройства.

На временных диаграммах показано: в момент времени tg с выходов блока ввода, на которых сформированы соответственно элементы матригЬи а,.,

1 9-11} ч

и , a|j, ..., а ,j-, сигналы подаются соответственно на входы конмутато- ру 7 в вьршслительном блоке 4 и на

.входы умножителя 2J в момент времени t на вход 11 умножителя 2 к на вход блока 2 подается единичный сигнал, на выходах 14 формируются значения а , X а .. X. . .к а t , , которые подаются на входы элементов ИЛИ 8 и соответственно на первые входы узлов 9s значения а (. формируются на выходах комкутато ра 7, которые подаются на вторые входы узлов 9, по заднему фронту единичного произведения а. «... записываются в регистры 10 в момент t на вход блока А подается единичный сигнал, на вькодах формируются значения , которые подаются на вторые входы узлов 9 умножения, на первые входы которых с выходов регистров 10 через элементы РИГИ 8 подаются значения а ;-ка .х. . a jj , в момент, времени t3 по заднему фронту единичного сигнала в регистры 10 записываются произведения 5 с выходов регистров 10 эти произведения подаются на соответствующие входы сумматора 11, На выхо°- дах сумматора 24 в блоке , формируется ijj-й элемент результирующей матрицы.

Формула изобретения

1, Матричный вычислитель, содержа- пщй матрицу из Р ср вычислительных блоков, где Р - порядок результирующей матрицы, отличающий- с я тем, 4TOj с-целью повышения быстродействия вычислителя при вычислении произведения Е матриц, в него введены группа из блоков умножения, где Е - количество перемножаемых матриц, блок синхронизации и группа блоков элементов И, принем первая группа информатдионных входов всех вычислительных блоков стро- ки матрицы является входом для задания К-й строки первой матрицы устройства, вторая группа информационных входов всех вычислительных блоков является входом для задания М-го столбца Е-й матрицы, Т-й информационный вход Н-го блока умножения группы (, .,., Е-2, ,

E-f

)

является входом задания Т-го элемен

та Н-й строки ядра результирующей матрицы, выход Н-го блока умножения подключен к первому входу Н-го блока элементов И группы, выход которого подключен к Н-му информационному входу третьей группы всех вычислительных блоков матрицы, тактовый вход устройства подключен к тактовому

IQ входу блока синхронизации, с первого по третий выходы синхронизации которого подключены соответственно к вто- рым входам всех блоков элементов И группы, первому входу синхронизации

.- всех вычислительных блоков матрицы и второму входу синхронизации всех вычислительных блоков матрицы, выход М-го вычислительного блока К-й строки матрицы является выходом М-го элемен-j та К-й строки результирующей матри- цьи

25 каждый вычислительный блок содержит коммутатор, группу из р элементов ИЛИ, группу умножителей, группу регистров и сумматор, причем первая и вторая группы информационных вхо2Q дов сумматора подключены к первой и второй группам информационньпс входов коммутатора соответственно, первый и второй входы синхронизации вычислительного блока подключены к первому и второму управляющим входам ком35 1утатора, Н-й информационньш выход которого подключен к входу первого сомножителя Н-го умножителя группы, Н-й информагщонный вход третьей группы выч;ислительного блока подключен к первому входу Н-го элемента ИЛИ группы, выход которого подключен к входу второго сомножителя Н-го умножителя группы, выход которого подключен к информационному входу Н-го ре45 гистра группы, выход которого подключен к второму входу Н-го элемента ИЛИ группы и входу Н-го слагаемого сумматора, выход которого является выходом вычислительного блока, тре50 тий вход синхронизации вычислительного блока подключен к входам признаков записи всех регистров группы.

40

oft a/, ,r

°IT

.J...

L..

oil

23 If V Г

0mm Ofnfjjuujmf mm

фиг. 2

y . Йу

I. о I

rS

% I 0 I

П-5

IIMl J

.

4 о/С

Ж

±

2

п

-Sf.

:г

3

гз

Г2

12

4

f % f ч

fJ

1

;4

«

L-i-.Фф

Фи. 5

7

Ж

/2

fZ

:5L.

Т

iLjkf2

.Г2

2

( Ч# f f л Л Ч 4f

/4

f«

Ч

f

ffв

Фиг. б

,32 t/rt

Й7,У2Г %,

Wrai

i/23

Уза, УЗЗ

W3, УЗ i/39