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

) ЛЬСТ 9- 1 х ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ АВТОРСКОМУ СВИ(46) 23,11,87, Бюл. У 43 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Р. Выжиковски (РЬ), Ю.С. Каневский и С.Э, Котов (БП)(56) Сатпея Тачсе 1 г, Рагг 1 г 1 оп 1 п 8 апй геаг 1 пд арр 11 ей го се 11 ц 1 аг аггау ргосеяяпя. ТЬе 5 г 1 т Бутпровдцш оп Кеа 1 Тдтпе 81 па 1 Ргосеяв 1 пя. 1982.Кцпе Н.Т. апй Ье 1 вегвоп С.Е. Яу о 1 с аггаув Гог 7 Ь 31. Брагяе Магг Ргосеей 1 пдв, 1978, рр. 256-282, Босегу аког 1 пйцвгг 1 а 1 аптек Арр 11 ед Маг 1 тетагхся, 1979.(54) УСТРОЙСТВО ДЛЯ РАЗБИЕНИЯ МАТРИЦ(57) Изобретение относится к вычислительной технике, и может быть использовано при построении специализированных устройств, предназначенныхдля решения систем линейных уравнений, Целью изобретения является сок-ращение аппаратурных затрат. Устройство содержит вычислительный блок 1и блок 2 синхронизации и позволяетразбить квадратную матрицу А на дветреугольные: нижнюю левую Ь и верхнюю правую П, такие, что Ь П = А,причем на главной диагонали матрицыН стоят единицы. Преобразование осуществляется по алгоритму исключенияГаусса. Устройство может быть исполь;зовано и для разложения потока матриц. 2 з.п, ф-лы, 5 ил,Изобретение относится к вычислительной технике и может быть испольгде К=1,2Р,)., ) =К+1, К+2 Р; 1 =а. к (к Для простоты описания работы без потери общности положим Р = 4. Условимся, что прием информации во все регистры осуществляется по заднему фронту синхроимпульса, т,е. в конце такта. Поступление исходных данных организовано следующим образом. На первый вход М-го вычислительного блозовано при построении специализированных устройств, предназначенныхдля решения систем линейных уравнений,Цель изобретения - сокращение аппаратурных затрат.На фиг, 1 представлена функциональная схема устройства; на фиг. 2и 3 примеры функциональных схемвычислительных блоков; на фиг. 4функциональная схема блока управле-ния; на фиг, 5 - блок-схема алгоритма функционирования устройства.Устройство содержит вычислительный блок 1 и блок 2 синхронизации.Вычислительный блок 1, представленный на фиг, 2, содержит первый 3 ивторой 4 регистры, арифметическоеустройство 5, коммутатор 6, сумматор7, третий регистр 8 и группу с первого по четвертый входов 9-12 синхронизации. Вычислительный блок 1,представленный на фиг. 3, содержитрегистр 13 и вход 1.4 синхронизации.Блок 2 синхронизации, представленный на фиг, 4, содержит генератор15 импульсов, элемент И 1 б, счетчик17, блок 18 постоянной памяти и входы 19-23 синхронизации,Устройство работает следующим образом,Устройство предназначено для разбиения квадратной матрицы А размерности Р на две треугольные: нижнююлевую Е и верхнюю правую П такие,что 1 Л = а, причем на главной диагонали матрицы Ц стоят единицы, Преобразование матрицы А = Га 1 выполняет (,ся по алгоритму исключения Гаусса,в процессе которого получаются элементы 1; и П;1)) а .(ккк ка 1 первой строки поступает М-йстолбец разбиваемой матрицы А.Столбцы подаются со сдвигом наодин такт, т.е. элементы второго столбца подаются, начиная свторого такта, третьего столбца,начиная с третьего такта, и т.д.В первом такте элемент а(, прини-(оВо втором такте элемент а при ни(о)мается в регистр 4 . 1 . 2, элемент ав регистр 3 . 1, 2 , элемент а , = 1 г, -5 в регистр 1 3 . 1 . 1 .(а)В третьем такте элемент а и прини(о)мается в регистр 4,1,3, элемент а,в регистр 3.1.3Арифметическое устройство 5.1.2 выполняет деление и на(о) (о)20 е го выходе получают частное а, / а ,П, которое в конце такта з апи сыв ает ся в регистр 8 , 1, 2 , В конце тактав регистр 4 , 1 . 2 принимается элемента , в регистр 3 , 1 . 2 - элемент а(о)а в регистр 1 3 . 1 . 1 - элемент а= 1, 1 .В четвертом такте на выходе сумматора 7 , 1 , 2 получают величину аа г я 12 / а 11 а , которая в(о (о)(о) (о)ггконце такта будет принята в регистр30 13,2,2, Элемент абудет записан в(о)Арифметическое устройство 5,1,3 выполняет деление и с его выхода частное я) /а = П принимается в ре(о 1 агистр 8.1.3. В регистры 4.1.2 ии 3.1.2 будут приняты элементь аяои а, соответственно, а в регистр40 13.1.,1 - элемент а,= 1.В пятом такте элемент а приниИмается в регистр 4.2,3, элемент а= аг, - я /я ас выхода сумматора 3. 1. 3 - в регистр 3. 2. 3. На выхо 5 де сумматора 7.1.2 получают величиИ)(о) (о) у о (о)ну а = а - а, /ан Я 1 = 14 гкоторая в конце такта принимается врегистр 13. 2. 2. На выходе арифметического устройства 5,1.4 получаютВ шестом такте элемент а , принимается в регистр 4 . 2 . 4 , в регистр(2)44 44 24 ЗЗ ха 4 = 1 4 принимается в регистр 13.4.4.На этом разложение квадратной матрицы А = а;Д размерности М = 4 заканчивается. Элементы матрицы Ь последовательно принимались в регистры 3.2.4 принимается элемент а("(о 1 (оЭлементы а, и а, записываются врегистры 41,4 и 3,1.4 соответственно, а элементы а 4, и а, - в регист(о) (а 1ры 4,1.3 и"3.1,3 соответственно,В седьмом такте на выходе сумматора 7.2.3 получают элемент а(о3.1.4,В восьмом такте элемент а прини(2)мается в регистр 43,4 а элемент(2) (1) И(1)а 4 = а )4 - а / а а с выхода сумматора 7.2,4 принимается в регистр3.3,4. На выходе сумматора 7.2.3 получают элемент а 4 = а 4) - а/ад ха= 14, который записывается врегистр 13.3.3. Элемент а принимя42ется в регистр 4.2.4, а элемент а(о) (а) г (о) (о 1Я 44 Я 24 ( 22 42тора 7,14 - в регистр 3,2,4,В девятом такте арифметическоеустройство 5.3.4 выполняет делениеи частное а /а = Н 4 принимается в регистр 8,3.4. Элемент а, при-,30 35 40 45 50 55 13.р, а элементы матрицы Н хранятся в регистрах 8.р,.Поскольку каждый элемент входной матрицы А используется в каждом данном процессорном элементе только один раз, можно выполнять 1 Л-разложение потока матриц. Каждую следующую матрицу можно начинать подавать с И+1-го такта после начала подачи предыдущей матрицы.Блок 2 синхронизации работает следующим образом. По сигналу пуска счетчик 17 устанавливается в нулевоесостояние и открывается элемент 16,.пропуская импульсы с выхода генератора 15 на счетный вход счетчика 17, содержимое счетчика 17 поступает на адресный вход блока 18, с информационных выходов которого сигналы синхронизации подаются на входы синхронизации всех блоков 1Формула изобретения1. Устройство для разбиения матриц, содержащее матрицу йз Р строк по (Р+1-К) вычислительных блоков в каждой строке (где Р - порядок разбиваемой матрицы, К = 1 Р - порядковый номер строки матрицы)и блок синхронизации, выходы синхронизации К-й группы которого подключены к группе входов синхронизации всех вычислительных блоков К-й строки матрицы, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, первый информационный вход (М+1)-го вычислительного блока (К+1)-й строки матрицы (КР) подключен к первому информационному выходу М-го вычислительного блока К-й строки матрицы, второй информационный выход М-го вычислительного блока (М Ф Р + 1 - К) К-й строки матрицы подключен к второму информационному входу (М + 1)-го вычислительного блока К-й строки матрицы, причем первый информационный вход М-го вычислительного блока первой строки является М-м информационным входом устройства, а первый информационный выход первого вычислительного блока К-й строки является К-м информационным выходом устройства, вход блока синхронизации является входом пуска устройства.2, Устрог(ство по п.1, о т л и -ч а ю щ е е с я тем, что М-й вычи5 13542 слительный блок (М Ф 1) К-й строки матрицы содержит три регистра, арифметическое устройство, коммутатор и сумматор, причем первый вход синхронизации группы вычислительного блока подключен к входам признака записи первогЬ и второго регистров, первый информационный вход вычислительного блока подключен к информационному входу первого регистра, выход которого подключен к первому информационному, входу коммутатора и к входу первого слагаемого сумматора, выход которого является первым информационным 15 выходом вычислительного блока, второй информационный вход вычислительного блока подключен к информационному входу второго регистра, выход которого подключен к входу первого операнда арифметического устройства и является вторым информационным выходом вычислительного блока,.второй вход синхронизации группы вычислительного блока подключен к входу признака записи ре гистра, третий вход синхронизации 06группы вычислительного блокаподключен к управляющему входу коммутатора, четвертый вход синхронизации группы вычислительного блока подключен к входу управления режимом (умножение- деление) арифметического устройства, выход которого подключен к входу второго слагаемого сумматора и к информационному входу третьего регистра, выход которого подключен к второму информационному входу коммутатора, выход которого подключен к входу второго операнда арифметического устройства.3, Устройство по п.1, о т л и - ч а ю щ е е с я тем, что первый вычислительный блок К-й строки матрицы содержит регистр, причем вход синхронизации вычислительного блока подключен к входу признака записи регистра, первый информационный вход вычислительного блока подключен к информационному входу регистра, выход которого подключен к первому и второму выходам вычислительного блока1354206Рг 4 /РР: з й ; с Фг.е е е. в а , швее даге еее