Матричный вычислитель

 

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

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

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

РЕСПУВЛИН (51) 4 G 06 F 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ вЂ”;

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР по делдм изоы етений и отнРытий (21) 4033285/24-24 (22) . 07.03.86 (46) 30.07.88. Бюл, N - 28 (72) В.П.Якуш, А.А.Перепелица, В.А.Мищенко и А.Г,Онищук (53) 681.325.5 (088,8) (56) Авторское свидетельство СССР

Р 647687, кл. G 06 F 15/32, 1979.

Авторское свидетельство СССР

Р 478306, кл, С 06 F 15/347, 1975.

{54) МАТРИЧНЫЙ ВЫЧИСЛИТЕЛЬ (57) Изобретение относится к вычислительной технике и может быть использовано для вычисления произведения цепочки матриц произвольной длины, произведения строки на матрицу, столб„„Я0„„1413644 А1 г ца на матрицу, возведения матрицы в степень. Матричный вычислитель содержит блок 1 ввода, умножитель 2, блок 3 синхронизации и матрицу Р Р вычислительных блоков 4. Найденные закономерности при вычислении произведения цепочки матриц, представляемого как произведение ядра результирующей матрицы, вычисляемого в умножителе 2 и общего для всех элементов результирующей матрицы, на соответствующую строку первой матрицы справа и столбец последней матрицы слева позволили осуществить вычисление всех элементов результирующей матрицы за три такта работы блока 3 синхронизации. 1 з.п.ф-лы, 7 ил.

l 413644

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

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

На фиг.1 представлена функциональ ная схема устройства; на фиг.2— функциональная схема блока умножения, на фиг.3 — функциональная схема вы15 числительного блока; на фиг.4 — функциональная схема блока ввода; на фиг.5 — функциональная схема коммутатора; на фиг.6 — функциональная схема блока синхронизации на фиг.? - sp{»

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

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

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

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

ИЛИ 14.

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

17 задержки и элемент 18 ИЛИ.

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

В блок 1 вводятся элементы перемножаемых матриц. С выхода блока 1 элементы перемножаемых матриц подаются в умножитель 2 и вычислительные 45 блоки 4 матрицы. В умножителе 2 формируются соответствующие сомножители

3» х. (а; »а{;» ...а; ), 3,=1,...,Р, 1=1.

Р, где P — порядок перемножаемых матриц, N — количество перемножаемьи матриц. После формирования сомножителей в умножителе 2 на вход пуска блока 3 подается сигнал, по которому с первого выхода блока 3 поступает импульс на вход синхронизации умножите- -5 ля 2 и на первый вход синхронизации блоков 4. На первые группы информационных входов блоков. н коммутатора 7 поступают элементы i-й строки первой матрицы а ",, а,, . а1

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

14, на первые входы соответствующих узлов 9, на вторые входы которых поступают соответствующие сомножители

° х

{{-{ (а.. ° а,; ° ...а, ) . На выходах узлов

) {

9 формируются соответствующие сомножители (а . » а . » а, .... а . ), кото{ 3

{{ {3 {Я Ц ° рые записываются в регистры 10 . 3aпись в регистры 10 осуществляется по заднему фронту импульса, который подается на вход разрешения записи регистра 10> через элемент ИЛИ 20, По окончании первого тактового импульса, второй тактовый импульс rioдается на вход элемента ИЛИ 20 с эа" держкой t„, где t — время переключения триггера. Задержка - осуществляется элементом 17 задержки распределения 5 импульсов. По второму тактовому сигналу элементы j-го столбца N-й матрицы поступают на входы второй группы блока 4;; и коммутатора 7, при этом элементы И б и 12 блокируются, так как на вход синхронизации умножителя 2 и на первый управляющий вход коммутатора 7 импульс не подается. При этом с выходов регистров 10 через элементы ИЛИ 8у подаются соответствующие сомножители (а .. х а,, ха, х...х а ) на вторые вхо-

Ф ° ° ды узлов 9 умножения, на первые входы которых с выходов коммутатора

7 поступают соответствующие элементы

j-ro столбца N-й матрицы. На выходах узлов 9; формируются соответствующие

1 1 3 сомножители (a,; а {» а ", ...а . ), кон торые записываются в регистры 10 и с выходов которых поступают на. j-e входы сумматора 11 соответствующего вычислительного блока 4 ц . На выходе сумматора 24 блока 4; формируются значения элементов С; результирующей матрицы.

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

Определение С;; -го элемента результирующей матрицы, где И - число перемножения матриц, эквивалентно умножению матрицы Д„ являющейся произведением с второй l1o предпослед14 13644 нюю матрицу, слева на i-ю строку матрицы А„, справа íà j-й столбец последней матрицы А9(9 т.е. !1, а12 -... а„а„...

9!

С =)а(, 9 ;2 9" 9а!и!"

° ° ° ° 4 Ю а„а„...

«!а,,а,,,...,а

j T!

Таким образом, все элементы С; матрицы С=А(А ...А,„, имеют общую часть, представленную матрицей Д, а их различие определено выбором i-й строки первой матрицы A u j-,ãî столбца последней матрицы А9(.

3. В последнем столбце сомножите2ей располагаются элементы j-го столбца последней матрицы А» т.е. элементы а",, а ",, ..., а ;9 каждый из ко- 45

9 2 9 ° ° 9

9(-2 торых повторяется r раз.

В качестве примера представлен элемент С 12 перемножаемых четырех

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

20 !

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

1. В первом столбце сомножителей располагаются элементы i-й строки первой матрицы А„, т.е, а °,а

19 Ф, 19;29 ° ° 9 а(„, а затем вся эта группа из r элементов повторяется г " 2 раз. 30

2. В каждом последующем P-м столбце сомножителей, кроме последнего, т е. P=2, 3, ..., N-1, располагаются последовательно элементы столбцов матрицы Ар, т.е. элементы а „, а 2,, . 35 е е р, е

° 9 а!4 9 а119 а 9 9 а92 9 аи9 а, ..., а, причем каждый элемент Г 9 2 повторяется г 2 раз, затем вся эта .руппа из r элементов повторяется . 9(- (Р+П раз. 40

I х I Я 11 ! (I х I а« ! у а(2

2

I ! ! 11

1 ! " n

4 а !

4 х а

1"

I" a%2

l 4 агг ! х а 22

4 ! ! аи !

1 а1

1

12

1

11 .1 а а

21 !

12

22

I !

hf

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

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

С=А,А j ...1, где 1 — единичная матрица, для возведения матрицы А s

Н-ю степень — C=A À ...А"< а в ((1192 степень - С=А А ...:А" ° 1

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

На временных диаграммах показано в момент времени t(I с выходов блока ввода, на которых сформированы соответственно элементы матриц;. а j, a(.

2 1 и а(., а 1, ..., а,, сигналы йодают1 1 ся соответственно на входы кокмутатору 7 в вычислительном блоке 4 и на

1413644

2О, входы умножнтеля 2, в момент времени

I на вход 11 умножителя 2 и на вход блока 2 подается единичный сигнал, на выходах 14 формируются значения

3 И-1 а w a .. x...x а,, которые подаются на

ij входы элементов ИЛИ 8 и соответственно на первые входы узлов 9, значения а формируются на выходах коммутато3 ра 7, которые подаются на вторые входы узлов 9, по заднему фронту единичного сигнала произведения а . «а . х

1 й-1 1 1J ... а, записываются в регистрй 10 ;

1J в момент t < íà вход блока 4 подается единичный сигнал, на выходах формируются значения а;. которые подаются

И на вторые входы узлов 9 умчожения, на первые входы которых с выходов регистров 10 через элементы ИЛИ 8 подаются значения а . х à . <...<а, в момент. вре4 ° °;) Ф мени t по заднему фройту единичного сигнала в регистры 10 записываются произведения, с выходов регистров 10 эти произведения подаются на соответствующие входы сумматора 11, На выхо" дах сумматора 24 в блоке 4 „ формируется i j-й элемент результирующей матрицы.

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

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

ЗО

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

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

2. Матричный вычислитель по п.1, отличающийся тем, что каждый вычислительный блок содержит

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

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

1413644

2 З Я Н 2 3 Ф и

0 О 0 И г Ои Пикап

1 I. 1

2 Л 55 Мт

0 m ипцпавща

ad а4 a55V

I5 У 15

-1413644

4 ю st%6 Ъ ЯЦ 0й 01 о6 Qz> 4 o zeg< oz,ag, 40 г Аа3 40Ь azzoz>

408. Ф

)4)3644 з1

Составитель A.Мишин

Техред Л.Олийнык

Редактор Л.Пчелинская

Корректор М.Помо

Заказ 3787/52

Тираж 704 Подписное:

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

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

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