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

 

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

СОЮЗ COBETCHHX

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

РЕСПУБЛИК

„„SU 1345211 (51)4 С 06 F 15/347

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4083852/24-24 (22) 15,04,86 (46) 15.10.87. Бюл. N 38 (72) В.П.Якуш, В.А.Мищенко, П.И.Соболевский, Л.Б.Авгуль и Э.Г.Лазаревич (53) 681.325(088.8) (56) Авторское свидетельство СССР

Ф 264797, кл. С Об G 7/16, 1968.

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

Ô 647687, кл. G 06 F 15/347, 1976. (54) УСТРОИСТВО ДЛЯ ОПЕРАЦИЙ НАД

МАТРИЦАМИ (57) Изобретение относится к области вычислительной техники и может быть использовано для вычисления произведения цепочки матриц произвольной длины, возведения матрицы в степень.

Цель изобретения — повышение быстродействия. Поставленная цель достигается тем, что устройство содержит тактовый вход 1, распределитель 2 импульсов, блок 3 ввода, матрицу размером m x m вычислительных блоков 4, где m — линейный размер обрабатываемых матриц, выходы 5 устройства. Увеличение быстродействия обеспечивается за счет того, что для одного рекуррентного шага требуются два тактовых импульса. Число рекуррентных шагов определяется длиной цепочки перемножаемых матриц. 3ил. т I "11 > ст .— 2 и.» т>» тт,2 >1-1 г;т сl

1с{

d, <2 а

11 ст Л 1 1» аз, 1 а

» с! с>

> а2 аЗ

f2. а с

1 а !

+ а l1

g » а а

>, 2<

1 3 а,„„ а, >.

3 с!

> сl а

12

,! )

>() .А А, Применяя формулу

Я-2 >< { «т с2 с) с, где i, I = 1, m, быть г<олуче то ой гроссе,турьi

Г ">, форму»!е . » ент <» ма-.—

l1- а .„ и

Й,, а"! полагая d f,f

Ч а I,Ã

{{aoI)»e гение отнс>с.итс я к i!m÷Hñ.;Iii-тельной технике и можс -. бьггi, ис т«,)л),-зовано для вычисле))ия прои 31!-;Io)!Iffy< цепочки матриц прои )во. »ьной 1.111)п), ВОЗВЕДЕНИЯ MBTPI»IIE I 13 С иЕIIЕ :)Ь.

Пел! изобрете)1;»я — увели;енис быстродействия устройства, На фиг. 1 представ. пена стp"ук.гур-ная схема устройства; ня фи: . схема вычислительно) о блока первого столбца матрит„ы вы итслительных бтп»ков; на фиг. 3 — схема вычи<.:лиfe:Iь-ного блока 1-го столбца E-",f (1=2> и., i=1, ..., m) матрицы тты»тттслитет)),— ных блоков.

Устройство содержит тактовый вход 1 „распределитель 2 им.,тупьсов > бЛОК 3 ВВОда, ВЬ)с)ИСЛИтЕЛЬН))С! б:)ОКИ

4 (j = 1 m) матрицы, вь)х< ды 5,. ! 1 устройства.

Вычислительный блок 4, со„ тс)р>):1»т информационные входы б .Iåp loй гру)т пы, информационные входы 71, второй ! группы,, у-правляющий вход Я, комму;атор 9, элементы {{{{И 10 „у).псожито-, ли 11, регистры I 7;, су..»1»с-;ор 1 3, 1 т выходы 14;; группы и вь:ход 15

Вычислительный блок 4; (c OJ),c p>) H информационные входы б;. первой т группы, информацтlo)IHE>lo входь< 14 второй группы, умножители I! . „ : умматор 13 и выход 5.

Работу устройства можно:ioяснить

На ПРИМЕРЕ ВЫЧИСЛЕНИЯ ПРОИЭ)кЕПЕ))ИЯ

N = 2 матриц

il f1

2)) <»

> произведение D может

ff на основании рекуррентн перемещения матриц„ По вначале вычисляют элем

Рицы Э Ач» АчА. { < ) 11 т 1) p ) l < > ) p и м с ) l EI л,> > {»и у и у (2 ) с

l: - )ч И с."»я)0 г )л и"..е)»ты . M<3 Tp HITE )

Г> А „. {31.

Понт<>ряя рекурре!»тпую процедуру

2 п .I а и M и)я Гс> H сэхо.!>я . иь 1<. . "Iе нть) d

H< Комого iipnff 3)IOJEe!«»EI D Т, e ..

)тайдены тта предыдущем

<)3;т т е .

1 поки 4 (р = 2, то) содержат

1 т> го:тько умножители 11 H ñóMìàòoð 13.

"о 1!оясняется тем, что при вычислен!»;! -элемен-.ов результирующей матрицы

L по формуле (4) в соответствующих

ofI ) ãëoMf)õ с{ -х элементов первые

1 1 ,E)3,I сом)!ожт»те

{ервые дв» с омно>кителя в соо гвет—

". зу)ощих: =Hàl аемых <1; -х элементов нычисляк>тся в блоках 4 H передаются

11 з блоки <; д:IEI вычисления элементов

Рс> I >т) ЬтИР К>)О)ДС) )й Ма TPI»IIbf

Устрсйство рабо:ает следующим эf)ЭаЗОМ.

Расс!рецепт»тел)> 2 имттульсов и регH=трь1 2 устанавэи)заются в начальное состояние. В <>)ток 3:вводятся элеменгь: перемножаемых матриц. На вход 1 по.„ается ттервьттй» тактовый сигнал, по которому с .->ерво о вьгхода распределителя импу тьсов )тоступает импульс

Hа входы синхрониза)тии бHoKoB 3 и 4.

: пока 3 на и):.формат!)»о нные входы 7 б. KB с) пос:т IIP î-. на:3лементы ст, ! 11

». i - l а .., .а, ".я и>!формационные

EI

-: х .ды б — )л мин ть: <{

I- ;I выходах уMH,о:-к).ттелей 11 фор)» и»

"1-1 . 1 миэуются сомножите:ти а

1 ,-{ >СО От»„1< i>1ò<» . )жа)О«И;Я с )и f>»>134з211

15

30 соответствующие регистры 12 блоков

4, и передаются в блоки 4;

По второму тактовому сигналу с блока 3 поступают на информационные входы 6 блока 4 элементы а "

11 1 !! n+ а, ..., а, которые через ком2 мутатор 9 подаются на первые входы соответствующих умножителей 11, на вторые входы которых через соответствующие элементы ИЛИ 10 подаются сформированные по первому тактовому импульсу сомножители. В результате на выходах умножителей 11 формируются сомножители а „ с1„„ а,„, 1! - 1 !14! а „„d à „которые суммируются на сумматоре 13, на выходе которого формируются значения d, записываемые

3 20 в блок 3..

На следующем шаге устройство работает аналогично. В блоках 4 формируются сомножители а с1 а

1!-2

21 11, П-2 3 !12 а Й „„ а и вычисляются зна1 !11 чения d,,. .На последнем шаге полу1) чают искомое произведение D т.е. на выходах устройства 5; Аор211 1 мируются значения элементов d ..,, 1! результирующей матрицы.

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

Устройство для операций над матрицами, содержащее блок ввода, вход элементов исходных матриц устройства подключен к первому информационному входу блока ввода, о т л и ч аю щ е е с я тем, что, с целью увеличения быстродействия, оно содержит матрицу размером ш х ш вычисли45 тельных блоков, где m — порядок обрабатываемой матрицы, и распределитель импульсов, причем тактовый вход устройства подключен к синхровходу распределителя импульсов, вы50 ходы с первого по ш-й распределителя импульсов подключены соответственно к входам синхронизации вычислительных блоков с первой по ш-ную строк первого столбца матрицы, m+ 1-й вы55 ход распределителя импульсов подключен к входу синхронизации блока ввода, выходы с первого по m2-й первой группы блока ввода подключены соответственно к информационным входам с первого по ш -й первых групп всех вычислительных блоков матрицы вычислительных блоков, выходы с первого по ш-й второй группы блока ввода подключены соответственно к информационным входам с первого по ш-й вторых вычислительных блоков первого столбца матрицы вычислительных блоков, выходы с первого по шР -й группы вычислительного блока i-й строки (i=1, ..., m) первого столбца матрицы вычислительных блоков подключены к информационным входам соответственно с первого по ш -й второй группы вычислительных блоков

i-й строки с второго по m-й столбцов матрицы вычислительных блоков, выходы вычислительных блоков матрицы подключены соответственно к информационным выходам с первого по ш -й устройства и соответственно к информационным входам с второго по пР +1-й блока ввода, при этом каждый- вычислительный блок первого столбца матрицы вычислительных блоков содержит коммутатор, m элементов ИЛИ, mÐ умножителей, m регистров и сумматор, причем в каждом вычислительном блоке первого столбца матрицы вычислительных блоков j é информационный вход (j=1, ..., mР ) первой группы вычислительного блока первого столбца матрицы вычислительных блоков подключен к первому входу

j-го элемента ИЛИ, выход которого подключен к первому информационному входу j-го умножителя, выход которого подключен к информационному входу j-го регистра, выход которого подключен к второму входу j-го элемента ИЛИ, к j ìó информационному входу сумматора и к j ìó выходу вычислительного блока первого столбца матрицы вычислительных блоков, i-й информационный вход второй группы вычислительного блока первого столбца матрицы вычислительных блоков подключен к i-му информационному входу коммутатора, j-й выход которого подключен к второму информационному входу j-го умножителя, вход синхронизации вычислительного блока первого столбца матрицы вычислительных блоков подключен к управляющему входу коммутатора и по входам чтения-записи регистров с первого по ш -й выход вьгчислительного блока первого г, 1 1, ) ) ) столбца матрицы Вы !ислитель..ых 1лгков подключен к информ11ционному 1!ход сумматора, при этом каждый I!f.!числи-тельный блок i-й строки 1-г<) с-.олбца (1 = 2, ..., m) матрицы в1В1ислите:!нных блоков содержит пР умножителей и сумматор, при этом в каждом вычис— лительном блоке i-и строки 1-го столбца матрицы вычислительных бло-ков 1-тые информационные входы ifep.)ой,! в Г;)1)()!! I р уl.Ï 1:.I I Р Г. !11 -е)if>lf:) I O блоКа

1 и I тр1)ки ) Гo I топбц мат>рицы I)fl чн< .!ите)11 н! !х б 1()f(()f) подключены соот—

f3 I.> т с т в е ) I II f) к ". е 1) в о и "" и В т 0 р о му и и !

) формационным Б хо ам ) Го умножите )чя >

Выход которогс !!>)цкл:очен к 1-му и)1формационно! !у входу сумматора, В.)ход которого подключен к выходу вычис— чительного блока I -й строки 1 — го столб— ца матр)3вы Вычислительных блоков.

1345211

Составитель В. Смирнов

Редактор И. Касарда Техред Л.Сердюкова Корректор И.Муска

Заказ 4922/48

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

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

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

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