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

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

Цехь изобретения - расширение функциональных возможностей за счет однов:)емённого транспонирования исходно i матрицы.

На фиг. 1 показана функциональная схема устройства; на фиг, 2 - функци- ональ ая схема М-го вычислительного блока (М-Г) К-й строки; на фи; , 3 - схема первого вычислительного блока К-й строки; на фиг,4 - функциональная схема блока синхронизации I rfa фиг. 5 блок-схема алгоритма функционирования устройства в. первой режиме.

З стройство содержит вычислительный блок 1 и блок 2 синхронизации.

Вычислитепьный блок (фиг, 2) содержит регистры 3 и 4, .арифметическое устройство 5, коммутатор 6, сумматор 75 регистр 8, первый 9, второй 10, третий 11 и четвертый 12 входы синхронизации.

Вычисли тел ьш1Й блок (фиг. 3) содержит регистры 13 и 14, арифметическое устройство 15, коммутатор 16, входы 17-21 синхронизации.

Блок 2 синхронизации (фиг. 4) содержит генератор 22 импульсов, элемент И 23, счетчик 24, триггер 25, блок 26 постоянной памяти, выходы 27- 30 синхронизации.

Устройство предназначено для р,аз- биения квадратной матрицы А размерности Р на две треугольные: нижнюю

левую L и верхнюю правую V такие, что L , причем на главной диагонали матрИ1Ц)1 V стоят единицы. Преобразование матрицы А выпсшняется по алгоритму исключения Гаусса, в прцесс, которого получаются элементы 1

l /.

М

и u;J :

3

(К-О

а

(К-1)

iK

«к

(о

а.. а, fj J

где К: 1, 2,

Pt i,,

k+2,...,Р;

Г

(k-iV

а KJ

u-0

КК

(tr-c)

- Q .

15

Для простоты описания работы без , потери общности положим . Усповим- ся, что прием информации во все ре- 20 гистры осуществляется по заднему фронту синхроимпульса, т.е. в конце такта.

Устройство имеет два режима функВ четвертом такте регистр 13.2.2 устанавливается в единичное состояние, причем .2, на выходе сумматора 7.1.2 получается величина , a,j, / j;,, которая в конце такта принимается в регистр 54.2.2, величина и, 1 при1шмается в регистр 4.1.А, элемент - в регистр 3.1.4, величина 1 f , , полученная на выходе арифметического устройства 5.1.3 в конце такта, принимается в регистр 8.1.3, величина и элемент

---«- ...) Принимаются соответственно в рецио1шрования: в первом режиме ввод и 3.1.3, частное ag/ обработка элементов разбиваемой мат-/а и л с выхода арифметического рицы А осуществляется по строкам воустройства 15.1.1 принимается в ре- втором режиме функционирования - по 13.1.1, величина .° и эле- столбцам. g) принимаются соответственно в

Поступление исходных данных в пер-30 , 4.1.2 и 3.1.2. вом-режиме функционирования организовано следующим образом. На первый

вход М-го вычислительного блока 1 пер-В пятом такте величина U22. l привой строки поступает М-я строка раз-нимается в регистр 4.2.3, арифме- биваемой матрицы А. Строки подают- 35тическое устройство 5.1.3 вьшол няет ся со сдвигом на один такт, т.е. эле-умнс5жение и величина ,2-aj, а,/ менты второй строки подаются, :шчи-/а , которая формируется на выходе ная с второго такта, третьей строки -сумматора 7.1.3 в конце такта, за начиная с третьего такта и т.д. писывается в ,

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

1 ИЧССЛ - с у „JL V л-rv .-ч- у- няет деление и частное a /a 22.U23 «

разом.

В первом такте регистр 13.1.1 устанавливается в положение 1,.причем ,j , элемент а, принимается в регистр 14. 1.1, причем f, .

Во втором тшсте элемент принимается.в регистр 4.1.2, элемент

е.° принимается в регистр 3.1.2, арифметическое устройство 15.1.1 выполняет операцию деления . и на его выходе формируется частное, равное и,, которое в конце такта принимается в регистр 13.1.1.

g;выходе формируется произведение IX j Jt а , равное Х., которое в конце такта принимается в регистр 8.1.2, частт)

fftl , fOl

(О) , col

frtl , (Ol

ное а i2. равное . принимается в регистр 3.1.2, арифметическое устройство 15.1.1 выполняет далекие и нл его выходе формируется частное aftVa ° равное Ui, которое в конIJ4 . ,,--- .

10 /це такта принимается в регистр 13.1.1

5

20 В четвертом такте регистр 13.2.2 устанавливается в единичное состояние, причем .2, на выходе сумматора 7.1.2 получается величина , a,j, / j;,, которая в конце такта принимается в регистр 54.2.2, величина и, 1 при1шмается в регистр 4.1.А, элемент - в регистр 3.1.4, величина 1 f , , полученная на выходе арифметического устройства 5.1.3 в конце такта, принимается в регистр 8.1.3, величина и элемент

) Принимаются соответственно в ретическое устройство 15.2.

1 ИЧССЛ - с у „JL V л-rv .-ч- у- няет деление и частное a /a 22.U23 «

конце такта nEHHHMaeTjc5 B ge HCTp

13. 2, 2, значение произведения 1 . alfj принимается в ре- гистр 8.1.4 с выхода арифметического устройства 5.1.4 величина а,2/а,° и элемент - af принимаются соответственно в регистры 4 1.4 и 3.1.4,

и а - соответственно в регистры 4.1.3 и 3.1..3, и а f - соот- ветственно в регистры 4.1.2 и 3.1.2, частное записывается в ре- гигтр 13.1.1.

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Цель изобретения - расширение функциональных возможностей устройства за счет одновременного транспонирования исходной матрицы. Устройство содержит матрицу вычислительных блоков, причем первый вычислительный блок К-й строки матрицы содержит два регистра, арифметическое устройство и коммутатор. Устройство работает в двух режимах. В первом режиме ввод элементов матрицы осуществляется по строкам и таким образом исходная матрица транспонируется. Во втором режиме ввод исходной матрицы осуществляется по столбцам и устройство функционирует аналогично прототипу. 5 ил.

В третьем такте элемент и„ , рав-В шестом-десятом тактах устроистный единице, принимается в регистрво работает аналогичным образом.

4 1 3 элемент - в регистр 3. 1.3.Поскольку каждый элемент матрицы А в

арифметическое устройство 5.1.3 вы-каждом процессорном элементе испольполняет операидш умножения и на егозуется один раз, можно выполнять LVрой

вес

что

К-й

с 6J

при

во

ся

южение потока матриц. Каждую слематрицу можно подавать с N+1- гакта после начала подачи предыду- матрицы, 5лок 2 синхронизации работает слеобразом. По сигналу пуска гчик 24 устанавливается в нулевое гояние и открывается элемент И тропуская импульсы с выхода гене- 5ра 22 на вход счетчика 24, Сосчетчика 24 поступает на , кроме одного, разряды адресного блока 26. На оставшийся разряд

входа блока 26 поступает или О с выхода триггера 25, ко- устанавливается в соответствую- состояние сигналом выбора режи- 1)ункционирования. С информацион- выходов блока 26 сигналы синхро- адии подаются на входы синхрониза- всех блоков I, Зо втором режиме предлагаемое уст- :;тво функционирует аналогично из- ному. Отличие заключается в том, в первых вычислительных блоках строки по сигналам синхронизации юка 2 синхронизации блокируется ;м элементов разбиваемой матрицы

раз,

,yЮ

го щей

ДУЮ(1ЩМ

сче сое 23,

рат

дер|симое

все

вхойа

адресного

тормй

щее

ма

ных

низ

ции

10

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

Устройство дпя разбиения матриц по п, 1 авт.ев, № 1354206, отличающееся тем, что, с целью расширения функциональных возможностей за счет одновременного транспо - нирования исходной матрицьг, в первьш вычислительный блок K-I строки матри цы вычислительных блоков введены регистр, арифметическое устройство и коммутатор, причем второй вход синхронизации вычислительного блока подключен к второму входу признака записи первого регистра, третий вход синхронизации вычислительного блока подключен к входу признака записи второго регистра, информационный вхо

20 вычислительного блока подключен к

информационному входу второго регист ра, входу первого операнда арифметического устройства и первому информационному входу коммутатора, выход

25 которого подключен к информационному входу первого регистра, выход второг регистра подключен к входу второго операнда арифметического устройства, выход которого подключен к второму ,

15

:эторые регистры i4.p4q., блокирует- 30 инфо ьч.яту сп.кону нхолз коммл-татора,

;эабота арифметических устройств

;3,q и разрешается прохождение эле- мен гов с первых информационных выходов через коммутаторы 16.p,q на информационные входы ,первых регистров 13,Peg.

ч. 1 jepTb; :. и пятый :.;ходы c; к;poнизaц ; вычислигелькогс 5лок2 по/.чключеьы .оо в.тственно к у::разляи 11,о;.-ь. входу ком мутатора и к входу улраьления режимо , Умножение-деление арифметического yc - ройства.

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

Устройство дпя разбиения матриц по п, 1 авт.ев, № 1354206, отличающееся тем, что, с целью расширения функциональных возможностей за счет одновременного транспо - нирования исходной матрицьг, в первьш вычислительный блок K-I строки матрицы вычислительных блоков введены регистр, арифметическое устройство и коммутатор, причем второй вход синхронизации вычислительного блока подключен к второму входу признака записи первого регистра, третий вход синхронизации вычислительного блока подключен к входу признака записи второго регистра, информационный вход

вычислительного блока подключен к

информационному входу второго регистра, входу первого операнда арифметического устройства и первому информационному входу коммутатора, выход

которого подключен к информационному входу первого регистра, выход второго регистра подключен к входу второго операнда арифметического устройства, выход которого подключен к второму ,

ч. 1 jepTb; :. и пятый :.;ходы c; к;poнизaц ;-: вычислигелькогс 5лок2 по/.чключеьы .оот в.тственно к у::разляи 11,о;.-ь. входу коммутатора и к входу улраьления режимом Умножение-деление арифметического yc - ройства.

Фиг.7

9 Г2

17 20

19

Фиб 2

W

Фиг Л

I iPг.13..Tf. i.pirf.i.

- :

PtM.1.. Р„3.J. аУ; ;

Рг.13.1.(,г

М. ; Pe.3.1.3 :- aYj ;

ft.aгг7: /-а М,.,1Удя; :рг.з...223;

.fii.t3.t., S /a f°, -а,з .

.Pt.ZS.r-(/fe..-

Afe./W.27:-ff 1 ar-4Va f й;; гг; Рг.чл. ; Pг.

Рг.8.}.(,РеА1.3г.а ,7а ° ; Л.3.f.,j Рг.Ш.1г.а 1 /а ,, (/,: fi..r2r.a °3/aff i fe.m az3

.г..5.г.:5;: а | -дЙ -й;ГА/ - « 5г

j /л Ул1../. I/.

flr./3.77:-( ЯУ...3.}.

.3.r.J7: 0

-}-ад 1,г,.:-а г , /а

csr- altya)/a / с А « .ДгЛx Vf 4 /4 г, ,; ,, ,,;

ft.,,.-.., .ftnizj

f.PeAJ., : PiAf.r. a iPy /a ,; . U7 al°Ji Pe i.tZr.0; Ps.-S.l.

r:::v:

i jj,/о./«5: :---й j-y-(7i;-;:--- iVff /jj;

/%гг. /-ff/; «.;..,

., ;./: -a.

Ps.

ffiAi., fe,3J.:

/./.j7. Pf.3.J.

-.T-i; .Л1/. Mj:.yffr. . .

ife.ii. Pt.Z.S7:

л.й1«7: ДчТ - м; «г-. /.г. -сД/ а ; c . Д5. 7--cl yial j a /a t a

.Fs.i 3. 37:(i/

Pi. f.i iy--(S , .t ir- &

T.

T.

PZ-nifA -.-l «/4,4 ; , г./«.4.- 1 г| | - a(f, /W ; fett.3.47:-0 .7.ЪА7:- 1 ... „;

Pe;,актор H.Тупица

Составитель Кухарекко Техред М.Моргентал „

Заг

аз 4378

Тираж 571

ВНИШИ Государственного коьштета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская каб. д. 4/5

Начало

Т

,r-Л«

a.

-.T-i; .Л1/. Mj:.yffr. . .

T.

1 г

( КОНРЦ ) г

Корректор С.Щекмар

Подписное