Устройство для ll -разложения симметричных матриц

ССМОЗ СОВЕТ СКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 1(57) Изобрлительнойпользованозированных ится к вычистение отно ехнике и м при постро устройств, ения систе т жет быть иснии специали ои предназначенлинейных уравия являетсяьности, Устройнные блокии блок синхроных для ре нений, Цел изобрет возводит повышение ство соде жит операци орой групп ставленная первой инизации.ется за цель дост ного разложеатриц. 4 ил. счет одноврем симметричных 1987. ные бл1,М, г Опе а технике, ири построених устройств, пешения систем пециализирова аэначенных дл йя повысчет одх симметройства,схематорой грункциониза цииоимпульсо 30 и блок онно нал бло = Р бло и ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ П(НТ СССР ПИСАНИЕ ИЗОБ АВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Киевский политехнический инстут им. 50-летия Великой Октябрьссоциалистической революции(56) Авторское свидетельство СССРВ 1292008, кл. С 06 Р 15/347, 198Валях Е. Последовательно-параллельные вычисления, - М.: Мир,1985. с. 260-269.Авторское свидетельство СССРВ 1354206, кл. С 06 Г 15/347 обретение относится к автомати ке и вычислительнои быть использовано п ных уравнении.Целью изобретения являетсение производительности заовременного разложения двуичных матриц.На фиг. 1 дана схема уста Лиг. 2 - функциональнаяР,Р) операционного блока впы (Р = 1,М), на дэиг, 3 - фьная схема (Р,ц)-го операцика первой группы, Р = 1,И,(54) УСТРОЙСТВО ДЛЯ ЬЬ -РАЗЛОЖЕНИЯСИММЕТРИЧННХ МАТРИЦ операцион оку 1.Р.ц второй группы (Р = Р,И), блок 2 синхронизации, р ионный блок первойгруппы содержит регистры 3-5, регистр6 частного, блок 7 умножения-деления,вычитатель 8 коммутаторы 9-12 и управляницие входы 13-19.Операционный блок второй группысодержит регистры 20-22, коммутатор23, блок 24 деления - извлечения квадратного корня, управляющие входы25-27,Блок синхро одержит генератор 28 синхр в, элементИ 29, счетчик 31 памятимикрокоманд.Устройство использует для разложения симметричных положительно определенных матриц А =: а 1 алгоритмХолецкого, в соответствии с которымссьс Иссссссется такая ижняя треуго/сьная1 с стрица 1. = С 1.1, что 1,Ь = А (где1, - транспоссированная матрица 1.):с5а , - Е асс, .25 где 1=1 И;1=1 Р 1)При этом одновременно реализуетсяразложение двух симметричных положи 5тельно определенных матриц А = (ас )и В = (Ь; ) на треугольные матрицы1, = (1; ) и М = (щ, ) соответственно,Устройство работает следующимобразом.Для простоты описания без потери общности положения М = 3. Условимся, что прием инФормации во все регистры осуществляется по заднеМуФронту синхроимпульса, т,е, в концетакта. Поступление исходных данныхорганизовано следующим образом. Напервый вход операционного блока 1.1.поступают элементы 1 строки матрицыВ и затем сс-го стобца матрицы А,Строки подаются со сдвигом на одинтакт, т.е. элементы второй строки подаются, начиная с второго такта,третьей строки - начиная с третьеготакта и т.д. 35В первом такте элемент Ь поступает на первый вход блока 24 операционного блока 1,1.1, который выполсняет операцию Гх , и на его выходеполучаем 1 сЬ, = щ , которое в конце такта записывается в регистры 20и 22 блока 1.1,1. Во втором тактещ, иэ регистра 22 блока 1.1.1 переписывается в регистр 4 блока 1.1.2,пройдя через коммутатор 12 блока 45.1.2. Этот же элемент через коммутатор 9 блока 1.1.2 поступает на второй вход блока 7 операционного блока1.1,2, на первый вход которого черезкоммутатор 10 блока 1.1,2. с первого 50входа операционного блока поступаетЬ,с, блок 7 операционного блока 1.1,2выполняет деление, значение Ь, /щ и"= щ, записывается в регистр 6 блока 1. 1,2. пройдя через коммутатор 5511 блока 1.1.2 в регистр 3 блока1.1.2. В этом же такте а , поступает на первый вход блока 24 операционного блока 1..1, он вьсси 1 ссвссет операцию ,Гх , и на его выходе получаесс а, = 1 с 1, которое в конце такта записывается в регистры 20-22 блока 1.1.1.В третьем такте щ, иэ регистра 4 блока 1. 1.2 переписывается в ресгистр 4 блока 1, 1.3, а также черезкоммутатор 9 блока 1.1.3 поступаетна второй вход блока 7 операционного блока 1.1,3,.на первый вход которого через коммутатор 10 блока 1.1.3 спервого входа операционного блока1,1,3 поступает Ъ блок 7 операционного блока 1.13 выполняет деление,и значение Ъ , /щ,щ , записывается в регистры 6 н 3 блока 1.1.3. В этом же такте щ, из регистра 6 блока 1. 1,2 переписывается в регистр 4 блока 1.1,2, а из регистра 3 блока 1.1.2 щпереписывается (через коммутатор 23 блока 12.2) в регистр 20 блока 1.2.2. Кроме того, из регистра 6 блока 1,1,2 щчерез коммутаторы 9 и 10 блока 1,1.2 поступает на оба входа блока 7 операционного блока 1.1.2, который выполняет умножение, а на второй вход вычитателя 8 блока 1.1.2 поступает Ь и с выхода вычитателя значение Ь- щ, принимается в регистр 3 блока 1.1.2. Кроме того, в третьем такте а поступает на первый вход блока 24 операционного блока 1,1,1, на второй вход которого иэ регистра 21 блока 1,1,2 поступает 1 блок 24 операционного блока 1,1. 1 выполняет деление, и значение а /1, = 1, записывается в регистры 5 блока 1.1,2, 20 и 22 блока 1,1.1, В четвертом такте щиэ регистра 3 блока 1. 1.3 поступает на второй вход вычитателя 8 блока 2.3, который делает пропуск операнда, и щс выхода вычитателя записывается в регистр 3 блока 1,2.3. В этом же такте щ , из регистра 4 блока 1.1.2 через коммутатор 9 блока 1.1.3 поступает на второй вход блока 7 операционного блока 1. 1,3, на первый вход которого. поступает ш, из регистра 6 блока 1.1,3 блок 7 операционного блока 1.1.3 выполняет умножение, полученное выражение поступает на первый вход вычитателя 8 блока 1,1,3., на второй вход которого поступает с первого входа операционного блока 1,1.3 Ь и полученное выражение Ь- щ ,щ ц принипринимает лока 1.3.3. Врегистра 5 блоерез .коммутаторы на оба входа блолока 1,2.3, на ля 8 блока 1,Хазъ - 1 з из ся Эреги Ои 22 б е 1 з из тупает ч а 1.2.3 онного б вычитатеыражение е так .3 по О. бло этом ка 1 операци второй входпоступает в 2.3 ре 5 15205 мается в регистр блока 3 блока 1,1.3 Кроме того, Ьт.т - щ, из регистра 3 блока 1.1.2 поступает на первый вход блока 24 операционного блока 1.2.2, который выполняет операцию ух , и полученное значение е зз = у Ьзз е записывается в регистры 20 и 22 блока1,2.2, в этом же такте из регистра 5 блока 1.1.2 поступает через коммутаторы 9 и 10 блока 1.1.2 на оба входа блока 7 операционного блока 1.1.2, который выполняет умножение, на второй вход вычитателя 8 блока 1.12 поступает ат, и с выхода вычитателя15 8 блока 1, 1.2 выражение ауу - 1, принимается в регистр 3 блока 1.1.2. В этом же такте щ, из регистра 4 блока 1. 1.2 переписывается в регистр 4 блока 1.1.3, а 1, изрегистра 2220 блока 1. 1. 1 переписывается в регистр4 блока 1.1.2Кроме того, а эпоступает на первый вход блока 24 операционного блока 1. 1. 1, на второй вход которого из регистра 21 блока 1.1.1 поступает 1 , блок 24 операционного блока 1.1.1 выполняет деление, и значение а /1 , 1 , записывается в регистры 5 блока 11.3, 20 и 22 блока 1.1. 1, 30В пятом такте щ , из регистра 3 блока 1.2.3 переписывается в регистр 20 блока 1.3,3, пройдя через коммутатор 23 блока 1.3.3. В этом же такте щт из РегистРа 22 блока 1.2.2 постУ пает на второй вход блока 7 операционного блока 1.2.3, на первый вход которого из регистра 3 блока 1,1.3 поступает Ь " щщз блок 7 операцион.ного блока 1.2,3 выполняет деление, и 40 с его выхода выражение (Ь э - щ у кщ,) /щ .т = щпринимается в регистры 6 и 3 блока 1.2.3. В этом же такте из регистра 3 блока 1,1.2 выражение а т - 1 , = 1 т поступает на 45 первый вход блока 24 операционного блока 1.2,2, который выполняет операцию (х , и полученное значениеа тт - 1 = 1 записывается в регистры 20-22 блока 1.2.2В этом же такте иэ регистра 22 блока 1.1,1 1, переписывается в регистр 4 блока 1.1.2, а также постуйает"через коммутатор 9 блока 1.1.2 на второй вход блока 7 операционного блока 1.1.2, на первый вход которого поступает иэ регистра 5 блока 1.1,2 1, а на второй вход вычитателя 8 блока 1.1.2 42 6поступает аз, блок 7 операционного блока 1.1.2 выполняет умножение, и с выхода вычитателя 8 блока 1.1.2 значение а- 1, 1 , записывается в регистр 3 блока 1,1.2. В этом же такте щ , из регистра 6 блока 1.1.3 переписывается в регистр 4 блока 1.1.3, а также поступает через коммутаторы 9 и 10 блока 1.1.3 на оба входа блока 7 операционного блока 1.1,3, а на второй вход вычитателя 8 блока 1. 1.3 поступает Ь и с выхода вычитателяполученное значение Ь- щ , принимается в регистр 3 блока .1.3.В шестом такте щ из регистра 3 блока 1,2.3 переписывается в регистр 20 блока 1.3,3, пройдя через коммутатор 23 блока 1.3,3. В этом же такте из регистра 6 блока 1.2.3 щпоступает на оба входа блока операционного блока 1.2.3, а на второй вход вычитателя 8 блока 1,2.3 из регистра 3 блока 1.1.3 поступает выражение Ьэ - щэ, и с выхода вычи-. тателя полученное значение Ь э - щ - щпринимается в регистр 3 блока 1.2.3. Кроме того, из регистра 3 блока 1, 1.2 выражение а - 1 т 1поступает на первый вход блока 24 операционного блока 1.2.2, на второй вход которого поступает из регистра 21 блока 1,2,2, блок 24 операционного блока 1.2,2 выполняет деление, иполученное выражение а з - 11)/ /1 1 = 1 з принимается в регистры 20 блока 122, 22 блока 1.2,2 и 5 блока 12.3. В этом же такте 1из регистра 5 блока 1.1.3 поступает на оба входа блока 7 операционного блока 1.1.3, на второй вход вычитателя 8 блока 1.1.3 поступает а , и с выхода вычитателя полученное значение а - 1 , принимается в регистр 3 блока 1.1.3.В седьмом такте из регистра 3 блока 1.2.3 выражение Ьэ щз щз 2 .поступает на первый вход блока 24 операционного блока 1.3.3, он выполняет операцию Гх , и полученное значениегистра 3 блока 1. 1.2 и с выхода вычитателя полученное значение аз -1 .22з1 зг принимается в регистр 3 блока 1.2.3, И, наконец, в восьмом такте выражение а, - 1- 1 из регистра 3 блока 1.2,3 поступает на первый вход блока 24 операционного блока 3.1.1,й- . -11 З принимается в регистры 20, 22 и 21 блока 1.1.3,На этом разложение матриц А и В размерности И = 3 заканчивается. Элементы матриц Ъ и М последовательно выдаются из регистров 20.р.р. Формула и обре и 40 г гУстройство для Ы - разложения сим 20 метричных матриц, содержащее блок синхронизации И(К)/2 операционных блоков первой группы и И операционных блоков второй группы, где И - размерность матрицы, причем группы 25 выходов блока синхронизации подключены к группам управляющих входов всех операционных блоков первой и второй групп, первый информационный вход устройства подключен к первому входу 1,1-го операционного блока второй группы, первый вход 1, К-го операционного блока первой. группы подключен к К-му информационному входу устройства (К = 2,М), первый вход и вь.ход К,К-го операционного блока второй группы подключены соответственно к выходу (К,К)-го операционного блока второй группы и к К-му выходу устройства (К = 2,И) выход 1,1-го операционного блока второй группы подключен к первому выходу устройства, первый вход (Р+1,К)-го операционного блока первой групггы подключен к первому выходу Р,К-го операционного блока первой группы (Р = 1,М, К = Р + 2,И), второй выход Р,К-го операционного блока первой группы подключен к второму входу (Р К+1)-го операционного блока первой группы (Р = 1,И, К = Р+1, И), второй выход Р,Р-го операционного блока второй группы подключен к второму входу (Р,Р+1)-го операционного блока первой группы (Р = 1,И),операционный блок первой группы содержит ггервый и второй регистры, регистр частного, блок умножения-деления, вычитатель и первый коммутатор, причем выход блока умноже ни я-деле нияподключен к первому входу вычитате,чзи информационному входу регистрачастного, выход которого соединен спервым информационным входом первогокоммутатора, операционный блок второйгруппы содержит первый регистр, выходкоторого подключен к первому выходуоперационного блока, о т л и ч а ющ е е с я тем, что, с целью повышения производительности за счет одновременного разложения двух симметричных матриц, третий выход Р,Р-го операционного блока второй группы подключен к третьим входам Р,К-х операционных блоков первой группы (Р - 1,И, К = Р+1,И), причем в операционньгй блок первой группы дополнительно введены третий регистр и три коммутатора, первый вход операционного блока подключен к первому информационному входу второго коммутатора и к второму входу вычитателя, выход которого соединен с первым информационным входом третьегокоммутатора, выход которого соединен с информационным входом первого регистра, выход которого является первым выходом операционного блока, второи вход операционного блока соединен с первым ин-,Формационным входом четвертого коммутатора и с вторым информационным входом первого коммутатора, выход которого подключен к второму входу блока умножения-деления, выход второго коммутатора является первым входом блока умножения-деления, вььход которого соединен с вторым информационным входом третьего коммутатора, третий вход операционного блока подключен к информационному входу третьего регистра, выход которого подключен к третьему информационному входу первого коммутатора и второму информационному входу второго коммутатора, а выход регистра частного соединен с третьим входом второго коммутатора и с вторым входом четвертого коммутатора, выход которого подключен к входу второго регистра, вьгход которого является вторым выходом операционного блока, первый управляющий вход группы первого операционного блока подключен к управляющему входу блока умножения- деления, входу разрешения записи регистра частного, управляющему входу третьего коммутатора, управляющиевходы группы первого операционного.блока с второго по пятый подключенысоответственно к управляющему входувычитателя, управляющему входу четвертого коммутатора, входу разрешениязаписи третьего регистра и первомууправляющему входу первого коммутатора, второй управляющий вход которогосоединен с первым управляющим входомвторого коммутатора и подключен кшестому управляющему входу группыпервого операционного блока, седьмойуправляющий вход группы первого операционного блока подключен к второмууправляющему входу второго коммутатора, причем в операционный блок второй группы дополнительно введены коммутатор, второй и третий регистры иблок выполнения операций деления-извлечения квадратного корня, причемпервый вход операционного блока соединен с первым входом блока выполне 102) 562ния операциИ деления-извлеченил корня и с первым информационным входомкоммутатора, выход которого соединнс информационным входом перного р- гистра, выход нторого регистра является вторым входом блока выполненияопераций деления-извлечения корня,выход которого соединен с информацион 10 ными входами второго и третьего регистров, с вторым информационным входом коммутатора и является третьимвыходом операционного блока, выходтретьего регистра является вторым выходом операционного блока, управляю 15щие входы группы с первого по третий,.второго операционного блока подключены соответственно к управляющемувходу коммутатора, входу разрешения.записи второго регистра и нходу ныбора режима блока деления-извлеченияквадратного корня,Подписное аж 66 каз 676051 ри ГКНТ СС ытиям НИИПИ Государственного комитета по изобретениям и о 3035, Москва, Ж, Раушская наб.,н ютзводственно-издательский комбинат Патент , г, Ужгород, ул. Гагарина, О