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