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

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

Иллюстрации

Показать все

Реферат

 

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

ГОСУ APC

ПО И БРЕТЕ

ПРИ Т тельн вано ных у реше

Из тельн вано ных у реше являе ва по

Ц функц однов ходно

На схема ональ ного на фи тельн функ з ации ритма перво (61) (21) 22) 46)

А.Н.Б

В. Г. (53) (56 ) № 135 (54 ) (57) СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ вЂ” РЕСПУБЛИК

ТНЕНКЫЙ КОМИТЕТ

НИЯМ И ОТКРЫТИЯМ

СССР

354206

496698/24-24

1 ° 10.88

3.1!.90. Бюл. ¹ 43 .В.Демидов, А.В.Моисеев, идар ь, А. Н. Семашко, иневич и С. Г, Седухин

81. 35 (088. 8) торское свидетельство СССР

206, кл. G 06 F 15/347, 1986.

СТРОАСТ8О ДЛЯ РАЗБИЕНИЯ МАТРИЦ зобретение относится к вычис-,ий технике и может быть использори построении специализирован-. тройств, предназначенных для я систем линейных уравнений. бр ет ение относится к вычислий технике, может быть использори построении специализировантройств, предназначенных для я систем линейных уравненич, и ся усовершенствованием устройставт,св, ¹ 1354206. ь изобретения — расширение ональных возможностей за счет еменного транспонирования исматрицы. фиг. 1 показана функциональная устройства; на фчг. 2 — функциая схема M-го выччслительблока (11-1)К-й строки;

3 — схема первого вычислиго блока K-й строки; на фиг,4 ональная схема блока синхрониФа фиг, 5 — блок-схема алгофункционирования устройства в. режиме. (51)5 0 06 Е !5/347

Цель изобретения — расширение функциональных возможностей устройства за счет одновременно ro транспортиров ания исходной матрицы, Устройство содержит матрицу вычислительных блоков, причем первый вычислительный блок К-й строки матрицы содержит два регистра, арифметическое устройство и коммутатор. Устройство работает в двух режимах. В первом режиме ввод элементов матрицы осуществляется по строкам и так.-.м образом и ходная матри=!а транспонируется. Во втором режиме ввод исходной матрицы осуществляется го столбцам и устройство функционирует аналогично прототипу, 5 ил, У строй ство содержит вы числит ел ьный блок 1 и блок 2 синхронизации, Вычислительный блок (фиг. 2) содержит регистры 3 и 4, .арифметическое устройство 5, коммутатор 6, сумматор 7, регистр 8, первый 9, второй

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

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

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

1608б90 аа" а .. =а, ° 10

iê > tj ц 9 где k I 2...,, р) левую L и верхнюю правую V такие, что L 7=А, причем на главной диагонали матрицы 7 стоят единицы. Преобразование матрицы А= )„а Д выполняется )) по алгоритму исключения Гаусса, в процесс".. которого получаются элементы

1, иы, : ().) (K-<) а „ =а,, А

11 ) (к- i\ а кк () .11 . (- 1 15

Х,) с 1, k+2 в ° ° э 1 kj (z )) 5 1$

Р u = э 1 а ° акк

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

Устройство имеет два режима функционирования: в первом режиме ввод и 25 обработка элементов разбиваемой матрицы А осуществляется по строкам; во втором режиме функционирования - по столбцам.

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

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

В первом такте регистр 13. 1. 1 ус- . танавливается в положение "1", .причем 1=и((, элемент а«принимается в регистр 14, 1, 1, причем а« =1< (ь)

Во втором такте элемент и „, =1 принимается в регистр 4. 1.2, элемент с.(ь) принимается в регистр 3. 1. 2, арифметическое устройство 15. 1. l выполняет операцию деления a, /a 1„и 50 (ь) (o) на его выходе формируется частное, равное и которое в конце такта принимается в регистр 13. I.,1.

В третьем такте элемент и равный единице, принимается в регистр

4 ° 1.3Ф элемент а31 — в регистр 3 1.3 ° (о) арифметическое устройство 5. 1.3 выполняет операп ю умножения и íà его выходе формируется произведение 1У (ь)

I(а, равное 1с которое в конце так2! 4) та при.".имается в регистр 8. 1.2 част (о) (о)

° ° ф ное a /а„, равное и<<, принимается в регистр 3, 1.2, арифметическое устройство 15, 1.1 выполняет деление и на его выходе формируется частное (о) у (о) а, /а,, равное и <, которое в кон,це такта прин:)мается н регистр 13.1. 1 °

В четвертом. такте регистр 13.2.2 устанавливается в единичное состояние, причем 1=по, на выходе сумматора

7, 1, 2 получается величина а -а а„ / (о)

2т=1 22 которая в конце прйж мается в регистр 14. 2. 2, величи- на и< =1 принимается в регистр 4.1.4, элемент a4, - в регистр 3. 1,4, вели(о) чина 1 a ) =1,, полученная на выходе арифметического устройства 5. 1.3 в конце такта, принимается в регистр (о) (о)

8. 1.3, величина а2 /а „„и элемент (о)

2) а принимаются соответственно в регистры 4, 1.3 и 3.1.3, частное а< /

/a „) =u 4 с выхода арифметического устройства 15.1. 1 принимается в регистр 13. 1. 1, величина а /а, и эле" (î1 (о) (ь)

19 мент а принимаются соответственно в регистры 4. 1. 2 и 3. l, 2.

В пятом такте величина u =-1 принимается в регистр 4.2. 3, арифметическое устройство 5. !. 3 выполняетс@ (ь) (о) (о) умножение и величина а =а -а, а, /

/а(ь), которая формируется на выходе сумматора 7.1,3 в конце такта, записывается в регистр 3.2. 3, арифме- тическое устройство 15.2.2 выполняет деление и частное а /a =u в (j)/ (л) конце такта принимается в ре;истр

13.2.2, значение произведения

1 а4, = 14, принимается в ре<о) гистр 8, l 4 с выхода арифметического устройства 5 . 1 . 4 величина а /а и (о) (0)

<о)

М 1 элемент: а4. принимаются соответственно в регистры 4 .4 и 3.1.4, а /а,ц и а („- соответственно в регистры

4.1.3 и 3.1,3, а, /a)4 и à 2+ — соот(ь) (о) Ф) ветственно в регистры 4, 1.2 и 3.1.2, частное О/аф =0 записывается в регистр 13. 1.! .

В щестом-десятом тактах устройство работает аналогичным образом.

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

23,, рат дер все вхо адр п 111 тор щее ма ных рой вес что

К-й с б при во ся

15. мен

) дов фор

13,.

5 160 ожение потока матриц, Каждую слеую матрицу можно подавать с И+1акта после начала подачи предыдуматрицы. лок 2 синхронизации работает слем образом. По с:.иналу пуска чик 24 устанавливается в нулевое ояние и открывается элемент И опуская импульсы с выхода генера 22 на вход счетчика 24. Соимое счетчика 24 поступает на кроме одного, разряды адресного а блока 26. На оставшийся разряд ского входа блока 26 поступает или "0" с выхода триггера 25, кой устанавливается в соответствуюсостояние сигналом выбора режиункционирования. С информационвыходов блока 26 сигналы синхроции подаются на входы синхронизавсех блоков 1. о втором режиме предлагаемое усттво функционирует аналогично изному. Отличие заключается в том, в первых вычислительных блоках строки по сигналам синхронизации ока 2 синхронизации блокируется м зл ементо в р аз бив ае мой матрицы торые регчстры 14. р, q, блокчруетабота арифметических устройств .q и разрешаетс:- прохождение элеов с первых информационных выхочерез коммутаторы 16.р,с; на инационные входы,пе", вых регистров

aqэ

8690 6

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

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

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

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

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

-„0 чнфэ .;,.«;,-:очномy =хо„-,,i комм,- атора ч. ..1ерть: .. и iiRTb! 1 . хо:,ы с. 1-= ронжа ац ".4

Быч 1с ительного элОк и":"кл:0 :с- ьь) оот " в, тственно к у:.:равля .. г1.; в> оду ко: -- . мутатора н к входу у. раьления режимом

"Умно. кение-деление" арифме тичес:;.ого

35 ус:"ройства, 20

2f!

608690 ф у 11

27

И

39

1e0S690

<Ра.4.1.2»:=1; <Р„3.1. 2»: =а г), (о) а Ь.)3.1.! )(= а)г/а = (г)г д

<Рг.4.П :1; <Рг.3.1.3 :-аД;

<Ргй И»=.1-(2 „-4); <Рг412М=а)г /а)г, <Рг 3.127:=агг; (о) .. (о) (о) (о) (2)3 /а)! <)1,3 (о) о) (о) (2) ()) ф

<Ра!3221)=!=иге; <%)4221.=агам=а, аг,/а(„=агг -1

<Рг.4.1.41--1; < г.Л).4) (=а„; (о)

<РгВ13>:=) аз) =Ъ; <Рг.413):=а:о/)а((о); <Рг, 3 j3)(=<2г()

<Рг. 1321) =а (о)/а(;) = ()„, .

<Рг.91.2p:=(г)3/а)), <Рг 312 ):=аг3 (о) (о). . (О) <Рг((23):=1; <Рг32Ъ)=азг аз)-а)г,са), =а (o)„(o) (о);о) () )

<Р )322»(аф< ф o) „() а(() ° (cA8 g 4) t ((pj =)о()<М(4). а)Яа Д(Рг 314»= йФи - б)) -, <Рг.Ъ|З:= ао ;

<Рг).3,ry : =(о(а(о)((о) (о)) (о) ())

6 г3»:=аг(гl/а()| <)М23):=аД

) (о) (») ()) (())

)(а(т М 17 а г@(агг

314». а<о) . г3 13»:=аго,2):= У.г !

"33 33 <) )43» - =()оз (("г"-„ 2 g:=(1ð3= 151:

2(():=Ра го(Ог;<Е2(/У":= ЗГС1, (&324):=-аФ)-аО,.6)3/& =а„., Хг»: g4/агг, <ФЛ23),":,, — ы -) о а, = а

21):= ф; (о) ((о)... (о)

)М:=а /Iа о ° <Рг 3 )4» =. Q, 13»:= У; <Рал13>)=Ф,9 ге — — а,„. (г) s» (о ) ))

59/ абаз го), „(о) гай) а (i). оо |

34» =a4 () (t)344), 1 ((< Р 1444> а (г) а(г) (г/ (г) а Р

<Рг4.3)((=2 ; <Рг,3З.41-=-Ф

Составитель Кухаре2-.ко

Техред 1. .4оргентал ор Н. Тупица

КорректоР С. 2Чекмар ч 378

Тираж 571

Подписное

Государственного комитета по изобретениям и открытиям при ГКНТ СССР

1130."»5, Москва, Ж-35, Раушская наб., д. (2/5 одственно-издательс кий комбинат "Патент" „г, Ужгород, ул. Гагарина, 101