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

(71) Киевский птут им. 50-летисоциалистическ Б-РАЗЛОЖЕН Бюл. У 21олитехнический инстия Великой Октябрьскойй революции С.Э.Кот вскиова88,8 атент У 0144123, опублик. 12.06.85. Був 1 о 1 с аггаувМаг.гх Ргосеейдпвв. кии/347 и др агве 282,ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенныхдля решения системы линейных урав-.нений. Целью настоящего изобретения является упрощение, Поставленнаяцель достигается тем, что благодаряизменению организации вычислений ичисла межпроцессорных связей устройство содержит 1/2 И(И+1) операционных блоков, Н входов и И выходов. 2 з.п. ф-лы, 4 ил,.ным правилам.Выходы распределителя 2 подключены к соответствующим синхровходам требуемых ОБ, Временная диаграмма синхроимпульсов на выходах распределителя 2 определяется заданной последовательностью записи операндов и ре 35 зультата.Устройство для Ь-разложения матриц предназначено для разложенияданной квадратной матрицы А размерности о 1 на две треугольные: нижнююлевую Ь и верхнюю правую П,такие,какЫА, причем на главной диагоналиодной из треугольных матриц соят единицы, Преобразование матрицы А = а; 145выполняется по алгоритму исключенияГаусса, в процессе которого получаются элементы 1; и П;)+1,, ),Цк а /а, 1;= а,551( 1,2, ,.) = )ф 50 Устройство работает следующимобразом. Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений.Целью изобретения является упрощение устройства.На фиг. 1 представлена функцио нальная схема устройства; на фиг,2 функциональная схема Ь,Е)-го операционного блока Ь = 1,М), на фиг. 3 - функциональная схема (К,Р)- го операционного блока (Р = 1,2, 15 Е); на фиг. 4 - блок-схема алгоритма работы устройства.Устройство содержит 0,5 И (о)+1) операционных блоков 1 (ОБ) и распределитель 2 импульсов, (1,Е)-й ОБ со держит входной регистр 3, блок 4 деления и вход 5 синхронизации, Ь,Р)-й ОБ содержит регистр 6 первого сомно-. жителя, умножитель 7, вычитатель 8, выходной регистр 9, регистр 10 вто рого сомножителя, первый 11, второй 12 и третий 13 входы синхронизации.Распределитель 2 импульсов реализован на базе ПЗУ согласно известДля краткости описания без потери общности положим И = 3, Условимся, что прием информации во все регистры осуществляется по заднемуфронту синхроимпульса, т.е. в концетакта.Исходные данные поступают на входы устройства для ЬП-разложения матриц построчно со сдвигом на одинтакт, т.е. первая строка исходнойматрицы А, а,; подается на вход операционного блока 1.1.1, вторая строка, а;) - с задержкой на такт навход ПЭ 1,2,1, третья строка, ана вход ОБ 1.3.1 и т.д.В первом такте элемент а о подается на вход ПЭ 1.1.1 и в конце такта принимается в регистр 3,1,1, причем а(1= 1,11(оВо втором такте элемент а пос 11тупает на вход ПЭ 1.1.1, на выходекоторого получаем частное а(,/а о,(оВ тРЕтЬеМ тахтЕ ЭЛЕМеит а 1 о ПОдается на вход ОБ 1.1. 1, на выходекоторого получим частное а а= Ц . Элемент а подается на первый вход ОБ 1.2.1, на выходе умножителя 7.2.1 получаем произведениеа(1/а ( а(1, которое поступает навход вычитателя 8.2.1 и на его выходе получаем выражение а= а о -1- а /а .а , = 1 оо. В конце такта(оВ четвертом такте элемент аподается на первый вход ПЭ 1.2.1.На выходе умножителя 7.2.1 получаемпроизведение а(о 1/а(1 а " котороепоступает на вход вычитателя 8,2.1,и на его выходе получаем выражениеа 1 = а- а/а , а,. Элемент(1) (О 1 (1 (О 1 (о 1а(о поступает на первый вход ПЭ311,3.1. На выходе умножителя 7.3.1появляется произведение а,1/а ф акоторое подается на вход вычитателя8,3,1 и на его выходе получаем вы(1 (о (о(о), (оражение а = а - а,1/аа о,. Вконце такта частное а ("/а(о принимается в регистр 10,3,1, а Д - из регистра 9.2.1 принимается в регистр3.2.2, а о принимается в регистр(19. 2; 1, а (1 - в регистр 9. 3. 1, В пятом такте отсчет а(0) подается33на первый вход ПЭ 1.3.1, на гыходеумножителя 7.3.1 получается произведение а,)/а(, а (" которое подается(о)на вход вычитателя 8.3.1 и на еговыходе получаем выражение а = азз зз- аз /а(" а(0). На первый вход ОБ1,2.2 поступает а(з из регистра9.2.1, и на выходе ОБ 1.2.2 получаемчастное а з/а= з, В конце так(1) ( )та а з = 1 з записывается из регист)ра 9.3. 1 в регистр 6,3.2, а записывается в регистр 9.3,1, частноеа(,)/а - в регистр 10,3.215В шестом такте а поступает напервый вход ОБ 1.3,2, на выходе умножителя 7.3.2 получаем произведениеа /а а , которое подается на(юВ седьмом такте а зз = 1 зз принимается в регистр 3.3.3.На этом процесс ЕП-разложения матрицы А завершается. Элементы верхнейтреугольной матрицы П : ПпПззвыдаются с выходов ПЭ 11.1 и 1,2,2,Элементы нижней треугольной матрицьЬ к концу вычислений находятся врегистрах процессорных элементов:11 12 1 зз - в регистрах 3,1.1,3.2,2, 3.3.3 соответственно, 1 г,1 з, 1 з - в регистрах 6.2.1,6.3.1,356.3,2 соответственно.Поскольку каждый элемент исходнойматрицы А используется в каждом данном процессорном элементе только одинраз, можно выполнять 1 Л-разложениепотока матриц, Каждую следующую матрицу можно начинать подавать с И+1такта после начала подачи предыдущейматрицы,45Формула изобретения 1, Устройство для 1 Л)-разложения матриц, содержащее 0,5 И (И+1) операционных блоков и распределитель импульсов, где М - размерность матрицы, выходы которого подключены к синхровходам операционных блоков, о т л и ч а ю щ е е с я тем, что,с целью упрощения, первьп вход(К,1)-го операционного блока подключен к К-му информационному входуустройства, где К = 1,), первый выход (К,1)-го операционного блока подключен к К-му вьходу устройства, второй выход щр-го операционного блокаподключен к второму входу (щ+1,ц)-гооперационного блока (щ = 1,)-1,- 1,щ) (первый выход ).)-го операционного блока подключен к первомувходу (1)+1)-го операционного блока(1 = 2,И, ) = 1,1-1).2. Устройство по п, 1, о т л и -ч а ю щ е е с я тем, что (К,К)-йоперационный блок содержит входнойрегистр и блок деления, причем первый вход операционного блока подключен к входу делимого блока деленияи информационному входу входного регистра, синхровход которого подключен к синхровходу операционного блока, а выход - к входу делителя блокаделения, выход которого подключен кпервому и второму выходам операционного блока.3. Устройство по п. 1, о т л ич а ю щ е е с я тем, что (К,Р)-й(Р = 1, К) операционньп блок содержит регистры первого и второгосомножителя, выходной регистр, умножитель и вычитатель, причем первьпвход операционного блока подключенк информационному входу регистра первого сомножителя и выходу уменьшаемого вычитателя, выход которого подключен к информационному входу выходного регистра, выход которого подключен к первому выходу операционногоблока, второй вход операционного блока подключен к информационному. входурегистра второго сомножителя, выходырегистров первого и второго сомножителей подключены соответственно кпервому и второму входам умножителя,выход которого подключен к входу вычитаемого вычитателя, выход регистравторого сомножителя подключен к выходу операционного блока, первый, третий и второй входы синхронизации операционного блока подключены соответственно к синхровходам регистровпервого и второго сомножителей и выходного регистра, 140 4781401478 Г. Составитель М,Сил Техред М.Ходанич тор М,Шароши актор Н.Лазаренко Тираж 7 Заказ 2786/48 одписно итета СССР 1 роизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 ВНИИ по 113035, И Государственногоделам изобретений иМосква, Ж, Раушс ткрытиия наб., д.