Устройство для операций над матрицами Советский патент 1987 года по МПК G06F17/16 

1

Изобретение относится к ;ычислп- тельной технике и может быть исиол..зовано для вычисления Г1рои:п елспия цепочки матриц ripoH;jiso. ib)io)i лчины, возведения матрицы п степр; ;..

Цель изобретения - увеличение быстродействия устгюнства.

На фиг. 1 представлена структурная схема устройст1:1а; на фи::-. 1 -- схема вь числительно|-о блока першего столбца матрицы вычислительных блоков; на фиг. 3 - схема вычислитель - ного блока 1-го столбца i-й (1 2, . . т, , ... in) матрицы вычислител):,- ных блоков.

Устройство содержит тактовый вход 1,, распределитель 2 импульсов. блок 3 ввода, вычислительные блоки 4j. (j 1, m) матрицы, выхстды 5j. устройства.

Вычислительный блок А ; содержит информационные входы 6; первой группы, информационные входы 7;. второй группы, управляющий вход 8, коммутатор 9, элементы ИЛИ 10 , умножите- , ли 11;. , регистры 12,-j , сумматор 15 выходы 14 jj группы и выход 15 - .

Вычислительный блок 4,р содержи-;: информационные входы 6 ... первой группы, информационные 14 .- второй группы, умножители 1 I ... , матор 13 и выход 5.

Работу устройства можно пояснить на примере вычисления произведения

N 2

fi + i

матриц

А,А . . .А

t 5 п-3

„ . .А. А,

2h

п., А„А„.,.,А

Применяя формулу

d

где 1, J 1, m,

произведение D может быть получено на основании рекуррентной процедуры перемещения матриц,, По формуле (2) вначале вычисляют элемент d ,, матрицы D3 А, ,.,

V i

П г 1 -- n-vf f ,

а ., , а , ( J

г X . i; t M

J полагая d р - а i

:f

1с. примошя ф.-5рмулу (2) Р г 1чис;гя1от элементы -,1 ., матрицы D - А,.„ )л„,,.

1онторяя рекуррентную процедуру на п-м таге находят э.чемент, d искомого произ} еденпя П , т.е.

51

f.Tl

kf

2n- П

(4)

,2 n-1 t(

папден, на предыдущем

шаге.

Плоки 4 (р 2 , In) содержат только умножители 11 и сумматор 13. ) : о 1 1оясняетс;я тем, что при вычисле- Н;1 элементов результирующей матрицы по формуле (4) н соответствующих с.гмгаемых элементов первые два сом1.ожителя совпадают. Например, , элементы d , и d имею вид

IZ

а

. 3 г

1

Первые два сомножителя в соответствующих слагаемых cl;;-х элементов вычислян тся в блоках 4 . и передаются в блоки 4;р ;1,ля вычислеЕшя элементов результмрующеи матрицы.

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

Распреде, итель 2 импульсов и регистры 12 устанавливаются в начальное состояние. В блок 3 вводятся элементы перемножаемрлх мат риц. На вход 1 подается первый тактовый сигнал, по которому с. перБо: О выхода распреелителя импульсов поступает импульс на входы синхронизации блоков 3 и 4.

- блока 3 на и ;формационные входы 7

поступают на элементы а

Pi

а , . , ,, S и .:формационные

входы 6 - элеме1ггы d , d , . . . ,

i

d., . На выходах умножителей 11 формируются сомножит сли а

(1

al d . которые записываются в m inm

31

соответствуюп1;ие регистры 12 блоков 4j, и передаются в блоки 4 -р .

По второму тактовому сигналу с блока 3 поступают на информационные

входы 6 блока 4 элементы а ,

11

, ... , 5 которые через ком 7 {с1 V

мутатор 9 подаются на первые входы соответствующих умножителей 11, на вторые входы которых через соответствующие элементы ИЛИ 10 подаются сформированные по первому тактовому импульсу сомножители, В результате на выходах умножителей 11 формируют-

ся сомножители а , d J, а , . . .,

И-1 .1 uti

См которые суммируются н

сумматоре 13, на выходе которого формируются значения d . , записываемые

в блок 3.

)

На следующем шаге устройство работает аналогично. В блоках 4 формиИ-2 , 1 ht- J

руются сомножители а р а а , ,..,

Яр d rnt вычисляются значения d ., , На последнем шаге получают искомое произведение ,

т.е. на выходах устройства 5;; форМ

мируются значения элементов d .,

iiK-i

Ч

результирующей матрицы.

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

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

5

С

0

5

0

5

0

5

ветственно к информационным входам с первого по первых групп всех вычислительных блоков матрицы вычислительных блоков, выходы с первого по га-й второй группы блока ввода подключены соответственно к информационным входам с первого по т-й вторых вычислительных блоков первого столбца матрицы вычислительных блоков, выходы с первого по группы вычислительного блока i-й строки ( , ,.., т) первого столбца матрицы вычислительных блоков подключены к информационным входам соответственно с первого по второй группы вычислительных блоков i-й строки с второго по т-й столбцов матрицы вычислительных блоков, выходы вычислительных блоков матрицы подключены соответственно к информационным выходам с первого по устройства и соответственно к инфор-i мационным входам с второго по блока ввода, при этом каждый- вычислительный блок первого столбца матрицы вычислительных блоков содержит коммутатор, т элементов ИЛИ, т умножителей, ш регистров и сумматор, причем в каждом вычислительном блоке первого столбца матрицы вычислительных блоков j-й информационный вход (j 1, ..., m) первой группы вычислительного блока первого столбца матрицы вычислительных блоков подключен к первому входу j-ro элемента ИЛИ, выход которого подключен к первому информационному входу j-ro умножителя, выход которого подключен к информационному входу j-ro регистра, выход которого подключен к второму входу j-ro элемента ИЛИ, к -j-My информационному входу сумматора и к j-му выходу вычислительного блока первого столбца матрицы вычислительных блоков, i-й информационный вход второй группы вычислительного блока первого столбца матрицы вычислительных блоков подключен к i-му информационному входу коммутатора, j-й выход которого подключен к второму информационному входу j-ro умножителя, вход синхронизации вычислительного блока первого столбца матрицы вычислительных блоков подключен к управляющему входу коммутатора и по входам чтения-записи регистров с первого по выход вьшислительного блока первого

столбца матрицы вычнслителы ых txiio-- ков подключен к информационному Hx-(i, сумматора, лри этом каждый вычисли-- тельньш блок i-й строки 1-го столбца (, .,, , га) матрицы вычислительных блоков содержит га умножителей и сумматор, при этом в каждом вычиг;- лительном блоке i-й строки 1.-го столбца матрицы вычислительных блоков j-тые информационные входы первой

II второй грукп 1 11числ телы1ого блока i-й с;троки 1-го столГм а матрии,ы вычислительных блоков подключены соот- BeTCTHOiiHcj к первому и второму ин- формац - онным входам j-ro умножителя, выход которого 1одкл;очен к j-му информациочному входу сумматора, выход которого подключен квыходу вычислительного блока г -и строки1-го столбца матрии з вычислительных блоков.

Изобретение относится к области вычислительной техники и может быть использовано для вычисления произведения цепочки матриц, произвольной длины, возведения матрицы в степень. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что устройство содержит тактовый вход 1, распределитель 2 импульсов, блок 3 ввода, матрицу размером m X m вычислительных блоков 4, где m - линейный размер обрабатываемых матриц, выходы 5 устройства. Увеличение быстродействия обеспечивается за счет того, что для одного рекуррентного шага требуются два тактовых импульса. Число рекуррентных шагов определяется длиной цепочки перемножаемых матриц. Зил. 00 4 СЛ

7rr тг 7rf

И

фиеЗ

74fmm

Составитель В. Смирнов Редактор И. Касарда Техред Л.Сердюкова Корректор И.Муска

4922/48

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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