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

/34 ГОСУДАРСТВЕННЫЙ КОМПО ИЗОБРЕТЕНИЯМ И ОЩРПРИ ГКНТ СССР ИЯМ ИЯ ОПИСАНИЕ ИЗОБРЕТ А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Киевский политехнический инсти тут им. 50-летия Великой Октябрьско социалистической революции(56) Авторское свидетельство СССР 11 1401778, кл. О 06 Р 15/347, 1986.Ка Нчапд апй реп - Непй СЬеця. Раг 1 Ыопей А 3.дог 111 ппя апй УЬБ 1 Б 1 гцсСцгея Гог Ьагяе - Бса 1 е ша 1 гхх сошрц 1 аЫопя, - РгосееЖпяя оГ 1 Ье 5-1 Ь Бушрояппп оп Сошрц 1 ег АгЫЬшеИс, 1981. Изобретение относится к автоматике и вычислительной техникебыть использовано при построении специализированных устройствначенных для решения систуравнений,Целью изобретения является снижение аппаратурных затрат,На фиг,1 представлена структурнаясхема устройства для 1 Х)-разложенияматриц; на фиг, 2 - структурная схемамножительно-вычитающего блока; нафиг.3 - структурная схема блока.синхронизации; на фиг, 4 - структурнаясхема одного из вариантов построенияформирующего узла; на фиг, 5 - временная диаграмма работы блока синхронизации,Устройство для Ь 11-разложения матриц (фиг,1) содержит первый 1,второй(57) Устройство для Ь 11-разложенияматриц относится к области вычислительной техники и может быть использовано при построении специализированных устройств, предназначенныхдля матричных вычислений, Цель изобретения - снижение аппаратурных затрат, Цель достигается новой организацией связей между элементами устройства, Особенностью работы устройства является распараллеливаниепроцесса вычислений в сочетании с высоким коэффициентом использованияэлементов устройства, Размерность Ораэлагаемых матриц 4 х 4. 5 ил,2,третий 3, четвертый 4, пятый 5 ишестой 6 регистры, первый 7, второй8, третий 9, четвертый 10, пятый 11и шестой 12 коммутаторы, .первый 13,второй 14, третий 15 и четвертый 16множительно-вычитающие блоки, первый17 и второй 18 блоки деления, седьмой19, восьмой 20, девятый 21, десятый22, одиннадцатый 23, двенадцатый 24,тринадцатый 25, четырнадцатый 26,пятнадцатый 27, шестнадцатый 28 и семнадцатый 29 регистры, седьмой 30, восьмой 31, девятый 32, десятый 33,одиннадцатый 34, двенадцатый 35,тринадцатый 36 и четырнадцатый 37 коммутаторы, блок 38 синхронизации,Множительно-вычитающий блок, например, содержит (фиг.2) умножитель39, входы которого являются входами первого и второго сомножителей,и вычитатель 40, первый вход которого соединен с выходом умножителя 39,второй вход является входом слагаемого, а выход - выходом всего множительно-вычитающего блока,5Множительно-вычитающий блок имеетвход слагаемого, вход первого сомножителя и вход второго сомножителяи выполняет вычисления по формулей = а - Ь с, где а - число на входеслагаемого; Ь и с - чис(и на входахпервого и второго сомножителей; Й -число на выходе множительно-вычитающего блока, 15Блок 38 синхронизации 9 например,содержит (Фиг,3) элемент И 41, выход3которого подключен к счетному входутрехразрядного счетчика 42 адреса,выходы которого подключены к входамрегистра 43 адреса, синхровход приема информации которого объединен спервым входом элемента И 41 и является вхоцом 44,1 блока синхронизации,Вход установки нуля счетчика 42 . 25объединен с вторым входом элементаИ 41 и является входом 44.2 запускаблока синхронизации. Выходы регистра 43 адреса подключены к входампостоянного запоминающего устройстваПЗУ) 45 микрокоманд, Выход элементаИ 41 является первым выходом 46 блока 38 синхронизации, Выходы 47-57 за поминающего устройства 45 микрокоманд являются соответственно с второго по двенадцатый выходами блокасинхронизации.Блок деления имеет вход делимогои вход делителя и выполняет вычисления по формуле 1 = Г/ц где Г - чис 9 40ло на входе делимого; о - число навходе делителя; 1 - число на выходеблока деления,При одноканальном потоке исходныхданных для Формирования требуемойпоследовательности исходных данныхи записи получаемых результатов в одноканальную память можно использовать преобразователь последовательного потока данных в параллельный50и параллельного в последовательный.Подобный формирующий узел можно построить множеством различных способовФормирующий узел, представленный нафиг.4, содержит шесть входных блоков58-63 регистров, входы которых объе 55динены и являются входом узла, а выходы подключены к входам устройствадля 1 Л-разложения матриц, Выходы= К 91 С+199 П. Поскольку устройство предназначено для Ю-разложения матриц размерностью 4 х 4, то вся обработка заключается в следующих вычислениях: 11 1 9 12 1 г 9 1 Ъ 13 9(144 - а 4 - -11 14 - -г Ц 4 г Ъ 1 -43 34 9 а за - .(.31 119, Т 1 а 4% 1 41 111114 й9.9а 43 3. 41 Ц 13 . г -113 -43е1.133Рассмотрим подробно работу устройства при выполнении.1 Л-разложения матрицыаа,. а, аа%1 айаг а г 3 а 24аэт а 33 а зааг а 3 аи получении матрицы1111 11 П П 1321 11 гг1723-31 139. 11 ээ1414143 Ц(41134П 4 устройства для ЬП-разложения соединены с входа(3(и шести выходных блоков 64-69 регистров, выходы которых обЪединены и являются выходом формирующего узла,Устройство для 1 Л-разложения матриц выполняет вычисление по формуле1О 5 20 25 30 5 154условимся, что прием в регистры осуществляется эадним фронтом синхроимпульса, т,е, в начале такта, и исходное состояние всех регистров ОпВ момент времени С (начало пер 1вого такта) в регистры 1-6 по сигналу, поступающему с выхода 46 блока 38 синхронизации принимаются а,а, а 15 Ф а 1+ ъ аг 1 аз соответственно По нулевым сигналам, поступающим с выходов 47, 48, 50 и 5 блока 38 синхронизации, коммутаторы 7-12 подключают к множительно-вычитающим блокам и блокам деления выходы входных регистров 1-6, коммутатор 37 по сигналам 10, поступающим с выходов 47 и 49 блока 38 синхронизации подключает к входам делителя блоков 17 и 18 деления выход входного регистра 1, коммутаторы 30-36 могут находиться в произвольном состоянии, так как в качестве сомножителей в любом случае будут подаваться нули. Таким образом, в конце первого такта в момент С по сигналам, поступающим с выходов 54-57 блока 38 синхронизации, в регистры 19-24 приник.аются соответП 1 .П 1ц 111 э 1 1 э -э 1также в регистр 29 - коэффициент 1 э,. 8795 6 эации, принимаются в регистры 19 и24 соответственно,В момент времени С , в началетретьего такта, в регистры 2-4 при 5нимаются соответственно а , а г,а и по нулевому сигналу коммута 1 г торы 8-10 подают их на входы блоков 14-16 соответственно, Коммутатор 31 по нулевому сигналу подает на вход п ервого сомножителя блока4 Б т,е, содержимое регистра 21,коммутаторы 32 и 33 подают на входы первого сомножителя блоков 15 и 16 Цт,е, содержимое регистра 20, выходрегистра 23 (1,) по нулевому сигналу коммутатор 35 подключает к входу второго сомножителя блока 14,выход регистра 29 (1 ,) по единичному сигналу коммутатор 36 соединяет с входом второго сомножителя блока 15, с выхода регистра 24 1,подается на вход второго сомножителя блока 16,К концу третьего такта на выходе блока 1 4 получают Ц , на выходе блоков 15 и 1 6 - числители соответственно 1 и 1 , которые в момент С принимаются соответственно в регистры 20, 27 и 28.В момент Св регистры 1-4 принимаются соответственно аг, азеф абазВ момент времени С г по сигналу, поступающему с выхода 46 блока 38 синхронизации, принимаются также аи ав регистры 1 и 6 соответственно, по нулевым сигналам, поступающим с выходов 47 и 48 блока 38 синхронизации, коммутаторы 7 и 12 подключают к входам блоков 13 и 18 выходы регистров 1 и 6, по сигналам "01"поступающим с выходов 52 и 53 блока 38 синхронизации, коммутатор 30 подключает к входу первого сомножителя блока 13 выход регистра 20, т,е, ц, По единичному сигналу, поступающему с выхода 51 блока 38 синхронизации, коммутатор 34 подает на вход второго сомножителя блока 13 1 т.е. выход регистра 23. По сигналам, "10", поступающим с выходов 47 и 49 блока 38 синхронизации, коммутатор 37 соединяет с входом делителя блока 18 выход. регистра 19, т,е, П, Таким образом, к концу второго такта на выходе блока 13 появляетсяа на выходе блока 18 - 1 котог.1рые в момент Сэ по сигналу, поступающему с выхода 55 блока 38 синхрониа , которые через коммутаторы 7-10подаются на входы слагаемого блоков13-16. Выход регистра 22 (И) через 35коммутаторы 30 и 33 подключается квходам первого сомножителя блоков13 и 16, выход регистра 21 (П, ) через коммутаторы 31 и 32 подключается к входам первого сомножителя бло ков 14 и 15, выход регистра 23 (.,)по единичному сигналу через коммутатор 34 подается на вход второго сомножителя блока 13, выход регистра29 (1 З, ) по единичному сигналу через 5 коммутатор 35 подключается к входувторого сомножителя блока 14, с выхода регистра 24. 1 , подается на входвторого сомножителя блока 15 по нулевому сигналу через коммутатор 36, на 50 вход блока 1 6 - непосредственно, Выход регистра 27 (числитель 1 ) поединичному сигналу через коммутатор11 подключается к входу делимого блока 17, выход регистра 28 (числитель1) по сигналам 10 через коммутатор12 - к входу делимого блока 18,выходрегистра 19 (Б ) по нулевым сигналамчерез коммутатор 37 - к входам делителя блоков 17 и 18.Таким образом, к концу четвертого такта на выходах блоков 13-8 получают соответственно Н первуют 4 фразность з 5, первую разность числителя 1 первую Разность 1 1 54 З ф 44З 2 ф1 , Б момент времени С 14,1 1.,Зз1принимаются в регистры 19, 23 и24 соответственно, а первые разностизз, числителя 14 и Н 44 - в Реги 4 З 44 Остры 26-28 соответственно,В начале пятого такта (С ) в реги"тр 1 принимается а з 4 и через коммугатор 7 подается на вход слагаемого блока 13, Коммутаторы 8 в 1 под 15качают выходы регистров 26-28 квходам слагаемого блоков 4-16 соотвегственно, Выход регистра 22 (114)через коммутатор 30 по сигналам "10"поключается к входу первого сомно 20жиТеля блока 13, выход регистра 20( ) через коммутаторы 31 и 32 - квхОдам первого сомножителя блоков14 и 15, выход регистра 19 (14) через коммутатор 33 - к входу первого 25сомножителя блока 16, С выхода регистра 29 через коммутатор 34 1подается на вход второго сомножителя блока 13, с выхода регистра 23 черезкоммутатор 35 1 з подается на ВХОДвторого сомножителя блока 14, с выхода регистра 24 1 41 подается на входвторого сомножителя блока 15 черезкоммутатор 36, а на вход второго сомносителя блока 16 - непосредственно,К концу пятого такта на выходах35блохов 13-16 получают ьответственноопервую разность П, НЗ, числитель34 ф ЗЗ ф14, вторую разность 1, Я момент44 овремени С 4 первая разность П чисЗ 40литель 145 и вторая разность П при 44нимаются в регистры 25, 27 и 28 Л зпринимается в регистр 20. В шестом такте коммутатор 7 подключает выход регистра 25 (первая разность П 4 ) к входу слагаемого блока 13, С выхода регистра 19 через коммутатор 30 1подается на вход первого сомножителя блока 13, с выхода;регистра 20 через коммутатор 3750 по сигналам "01" П, подается на вход делителя блока 18, с выхода регистра 23 1 з через коммутатор 34 подается на вход второго сомножителя блока 13, с выхода регистра 27 через коммутатор2 по сигналам "01" чис 55 итель 1 подается на вход делимого блока 18,К концу шестого такта на выходахблоков 3 и 18 получают коэффициентыН 4 и 1 соответственно, которыев момент времени С принимаются врегистры 19 и 24 соответственно,В седьмом такте коммутатор 1 0 подает на вход слагаемого блока 16вторую разность П 4 с выхода регистра 28, с выхода регистра 19подаЗ 4ется на вход первого сомножителя блока б через коммутатор 33, с выходарегистра 24 на вход второго сомножителя блока 16 подается 1 К концуседьмого такта на выходе блока 16 получают Ц , которое в момент времениСЗ принимается в регистр 22.На этом разложение исходной матрицы А на коэффициенты 1 и П заканчивается, В момент времени С в реги 6стры 1-6 принимаются исходные данныеновой матрицы. Далее работа устройства аналогична описанной.Блок 38 синхронизации работаетследующим образом, Синхроимпульсы отвнешнего устройства через вход 44,1поступают на синхровход приема информации регистра 43 адреса и на первыйвход элемента И 41, на второй входкоторого через вход 44,2 подаетсясигнал запуска, При единичном значении сигнала запуска снимается сигналустановки в ноль счетчика 42 и синхроимпульсы начинают поступать насчетный вход счетчика 42 адреса.Выходы счетчика 42 адреса подаются навходы регистра 43 адреса, выходы которого поключены к адресным входамПЗУ 45 микрокоманд . Емкость ПЭУ45 микрокоманд - восемь девятиразрядных слов, Количество микрокоманд равно количеству тактов работы количество разрядов микрокоманды равно количеству различных управляющих сигналов, требуемых для элементов устройства,Формирующий Узел (фиг,4) работаетследующим образом, Элементы исходнойматрицы принимаются в соответствующие входные блоки регистров, т.ев регистры 58,1-58,4 принимаютсяэлементы а а, а 4, аз 4, в регистры 59.1 -59,3 - элементы а а11 ф 25 фа, в регистры 60.1-60.3 - а а1 Ъ ф Зйфа 45, в регистры 61,1-61.3 - а а14 ф 45и а 44, в регистр 62 - а в регистры 63.1-63,2 - а з 1 и а 4 Элементыпреобразованной матрицы Ю принимаются в выходные блоки регистров следующим о бр аз ом; в регистры 64, 1-64, 4элементы И, И, И+, Ц 4, в регистры 65.1-65.3 - элементы Й 1,ИИз, в регистр 66 - И в регистры67.1 и 67.2 - И,4 и И 44, в регистры68.1 и 68.2 - 1, и 3, в регистрыча элементов преобразованной матрицы из устройства может быть органи 10эована в любой требуемой последовательности. Управление формирующимузлом осуществляет внешнее устройство управления, которое может быть,например, микропрограммным,15формула и з обретенияУстройство для ЬИ-разложения матриц, содержащее семнадцать регист 20 ров, четырнадцать коммутаторов,два блока деления, четыре множительновычислительных блока, блок синхронизации, причем информационные входы с первого по шестой регистров под ключены соответственно к первому, второму, третьему, четвертому, пятому, и шестому входам устройства, с первого по шестой выходы которого подключены к выходам соответственно седьмого, восьмого, девятого, десятого, одиннадцатого и двенадцатого регистров, о т л и ч а ю щ е е с я тем, ,что, с целью снижения аппаратурных затрат, выходы с первого по шестой регистров соединены с первыми информационными входами с первого по шестой коммутаторов, выходы первого, второго, третьего и четвертого коммутаторов соединены с входами слагае 40 мого соответственно первого, второго, третьего и четвертого множительновычислительных блоков, входы первых сомножителей которых соединены соответственно с выходами. седьмого,весь мого, девятого и десятого коммутаторов, информационные входы седьмого, восьмого, девятого и десятого регистров соединены соответственно с выходами первого, второго, третьего и четвертого множительно-вычислитель 50 ных блоков, входы вторых сомножителей которых соединены с выходами соответственно одиннадцатого, двенадцатого, тринадцатого коммутаторов и двенадцатого регистра, выходы пятого и шестого коммутаторов соединены с входами делимого соответственно первого и второго блоков деления,входы делителей которых соединены междусобой и с выхедом четырнадцатого комгмутатора., первый информационный входкоторого соединен с первыми информационными входами седьмого и десятогокоммутаторов и с выходом седьмого регистра, выход тринадцатого регистрасоединен с вторым входом первого коммутатора, выход первого блока деления соединен с информационным входомодиннадцатого регистра, выход которого соединен с первыми входами одиннадцатого и двенадцатого коммутаторов, вторые входы которых соединенымежду собой и с первым входом тринадцатого коммутатора, выход четырнадцатого регистра. соединен с вторым информационным входом второго коммутатора, выход пятнадцатого регистра соединен с вторыми информационными входами третьего;пятого и шестого коммутаторов, выход шестнадцатогорегистра соединен с вторым информационным входом четвертого коммутатора и третьим информационным входом шестого коммутатора, выход второго блока деления соединен с информационными входами семнадцатого и двенадцатого регистров, выходы которых соединены соответственно с первым и вторым информационным входами тринадцатого коммутатора, выход девятого регистра соединен с первыми информационными входами восьмого и девятого коммутаторов, выход восьмого регистра соединен с вторыми информационными входами седьмого, восьмого, девятого, десятого и четырнадцатого коммутаторов, выход десятого регистра соединен с третьими входами седьмого и десятого коммутаторов, выход первого регистра соединен с третьим входом четырнадцатого коммутатора,первый выход блока синхронизации соединен с .синхровходами первого,второго, третьего, четвертого, пятого, шестого, тринадцатого, четырнадцатого, пятнадцатого и шестнадцатого регистров, второй выход блока синхронизации соединен снастроечным входом первого коммутатора и с первыми настроечными входами шестого, десятого и четырнадцатого коммутаторов, третий выход блока синхронизации соединен с вторыми настроечными входами шестого и десятого коммутаторов, четвертый выход блока синхронизации соединен с вторым настроечным10 входом четырнадцатого коммутатора, пятый выход блока синхронизации соединен с настроечными входами второго, третьего, четвертого и восьмого коммутаторов, шестой выход блока синхронизации соединен с настроечными входами пятого, девятого, одиннадцатого и двенадцатого коммутато ров, седьмой выход блока синх; ронизации соединен с настроечным входом тринадцатого коммутатора и первым настроечным входом седьмого коммутатора, второй настроечный вход которого соединен с восьмым выходом блока синхронизации,девятый выход которого соединен с синхровходами девятого, десятого и семнадцатого регистров, десятый выходблока синхронизации соединен с синхровходами седьмого и двенадцатогорегистров, одиннадцатый и двенадцатый выходы блока синхронизации соединены соответственно с синхровходамивосьмого и одиннадцатого регистров.1548795 Составитель К, Кухаренкоедактор В,Петраш Техред А. Кравчук Корректоруска КНТ СС Производственно-издательский комбинат "11 атент", г, Ужгород, ул, Гагарина, 10 ЗакВНИИП 142Го Тираж 565 арственного комитета по 113035, Москва, Ж