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

(19) ( 1)5 6 06 Р 15/34 ЕТЕ ИДЕТЕЛ ЬСТ АВТОРСКОМ СССР 1986, СССР18,08.88 ОЖЕН вычислительдля Ы-разло- использовано ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ(54) УСТРОЙСТВО ДЛЯ ШМАТРИЦ(57) Изобретение относитсяной технике, предназначеножения матриц и может быт Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем уравнений, обращения матриц,Цель изобретения - повышение быстродействия,На фиг. 1 приведена структурная схема устройства для Щ-разложения матриц; на фиг. 2 - схема (1, 1)-го вычислительного модуля(1=1, й - 1; й - размерность обрабатываемых матриц); на фиг. 3 - схема 1, -го вычислительного модуля =2, й; на фиг. 4 - схема (К -го вычислительного модуля ге=2, Й - 1); на фиг, 5 - схема гся, 1).го вычислительного модуля; на фиг. 6 - схема (1, й)-го вычислительного модуля; на фиг. 7 - схема (п,в)-го вычислительного модуля (п=2,й при т=й; в=2, й - 1 при п=й).Устройство содержит матрицу (Мхй) вычислительных модулей 1, блок 2 синхронизации, синхровход 3, вход 4 управления, группу информационных входов 5, группу 661793 А 1 при построении специализированных устройств, предназначенных для решения различных матричных задач. Целью изобретения является повышение быстродействия эа счет реорганизации структуры устройства. Устройство содержит матрицу Мхй (й - размерность обрабатываемых матриц) вычислительных модулей и блок синхронизации, синхровход, вход управления, группу информационных входов и группу выходов,В основу работы устройства положен алгоритм исключения Гаусса, Особенность функционирования устройства является параллельно-поточная организация вычислений. 7 ил. выходов 6, мультиплексоры 7, регистры 8, делитель 9, умножитель 10 и сумматор 11.О, 1)-й вычислительный модуль (фиг. 2) и (Й, 1)-й вычислительный модуль (фиг, 5) имеют вторые входы (не обозначены), подключенные к выходам регистров 8.(1, -й (фиг. 3) и (1, й)-й (фиг. 6) вычислительные модули имеют третьи информационные входы и вторые выходы (не обозначены), подключенные соответственно к входам знаменателя и выходам соответствующих делителей 9.(К Д-й вычислительный модуль (фиг. 4) имеет третий и четвертый информационные входы (не обозначены), подключенные соответственно к первому и второму входам умножителя 10.(и, в)-й вычислительный модуль имеет второй и третий информационные входы (не показаны), подключенные соответственно к первому и второму входам сумматора 11,.Блок 2 синхронизации может быть выполнен, например, в виде й-разрядного)О= счетчика, работающего в режиме счета синхроимпульсов, На выход блока синхронизации выдается и 1", когда содержимое счетчика равно 1, во всех остальных случаях на выходе блока синхронизации н 0",Устройство предназначено для разбиения квадратной матрицы А порядка й на две треугольные: нижнюю левуюи верхнюю правую И, такие, что Ш=А, причем на главной диагонали матрицы Ц стоят единицы, Преобразование матрицы А=(а выполняется по алгоритму исключения Гаусса, в процессе которого получаются элементы ) и О) матрици 0 на основе рекуррентных фор- мул- 1)пи а) - , )в Ов;( );в =1- 1Ш = - (а) - р )в цв ): () ) .в=1Рассмотрим работу устройства на примере разбиения произвольной матрицы четвертого порядка Искомые матрицыи У, удовлетворяющие1,)=А, будут: На первом такте работы устройства в вычислительные модули 1)1, где )=1,4, с входов 5) в регистры 8 принимаются элементы аЦ матрицы А, В вычислительных модулях 11,2, 11,3, 11,4 происходит деление содержимого регистров 8) на содержимое регистра 811. На выходах делителей 9 вычислительных модулей 11,2, 11,3, 11,4 получаются числа 1/2, 2,1. В вычислительных модулях 1), где Ц=2,4, происходит перемножение чисел, поступивших из вычислительных модулей 1)1 и 111, затем это произведение в сумматоре 11 отнимается от содержимого регистра 8 данного вычислительного модуля 1)1, Таким образом, на выходах сумматоров 11 вы.числительных модулей 12,2, 12,з, 12,4, 13,2, 13,3, 13,4, 14,2, 14,3, 14,4 получаются числа 1/2, -5, -2, 5/2, 1,1, 3/2, -1,2, с выходов 61,1, 62,1, бз,1, 64,1 считываются элементы 11, 21, 31, 41 первого столбца матрицы2, 3, 1, 1, с выходов 61.2, 61,з, 61,4 считываются элементы О 12, О 13, О 14 первой строки матрицы У 1/2, 2, 1. На втором такте с выходов 6), где Ц=2,4,в регистры 8 вычислительных модулей1)-1,1-1 принимаются элементы 1/2, -5, - 2,5/2, 1,1, 3/2, - 1,2. После аналогичных дей 5 ствий, как на первом такте, на выходахделителей 9 вычислительных модулей 11,2,11,3 получаются числа -10, - 4, на выходахсумматоров 11 в вычислительных модулях12,2, 12,з, 1 з,2, 1 з,з - числа 26, 11, 14, 8. С10 выходов 61,1, 62,1, 63,1 считываются элементы 22, 32, 42 второго столбца матрицы1/2,5/2, 3/2, с выходов 61,2, 61,з считываются элементы О 2 з, О 24 второй матрицы- 10, - 4,15 На третьем такте с выходов 62,2, 62,з,бз,2, бз,з, в регистры 8 вычислительных модулей 11,1, 11,2, 12,1, 12,2 принимаются элементы 26, 11, 14 и 8. Затем на выходе делителя9 вычислительного модуля получается чис 20 ло 11/26, на выходе сумматора 11 вычислительного модуля 12,2 получается число27/13. С выходов 61,1, 62,1 считываются элементы зз и 4 з третьего столбца матрицы26 и 14, с выхода 61,2 считывается элемент25 034 третьей строки матрицы У 11/26,На четвертом такте с выхода 62.2 в регистр8 вычислительного модуля 11,1 записывается элемент 27/13 и затем с выхода 61,1считывается последний искомый элемент30 44=27/13,Таким образом, после четырех тактов получены все элементы искомых матрициЦ, удовлетворяющих Я=А,Формула изобретения5 Устройство для ПГ-разложения матриц,содержащее матрицу Йхй вычислительныхмодулей (М - размерность обрабатываемых матриц) и блок синхронизации, вход которого является синхровходом устройства, 40 группу выходов которого образуют первыевыходы (п,а)-х вычислительных модулей (п=1,8 при а=1; а=2,й при п=1), входы управления и синхровходы которых подключены соответственно к выходу и входу блока 45 синхронизации, о т л и ч а ю щ е е с я тем,что, с целью повышения быстродействия, синхровходы, (Ц)-х вычислительных модулей (Ц=2,М) подключены к входу блока синхронизации, выход которого соединен с 50 входами управления (,М)-х вычислительныхмодулей р,1=2,М), первые информеционные входы всех вычислительных модулей образуют группу информационных входов устройства, первый выход (,-го вычис лительного модуля подключен к второму информационному входу (-1,) - 1)-го вычислительного модуля, второй выход (р, 1)-го вычислительного модуля подключен к третьему информационном входу (р, )-го вычислительного модуля (р" 1, М - 1) и к второ1661793 Составитель К, КухаренТехред М,Моргентал Редакто оэори ПодписнОЕбретениям и открытиям при Гаушская наб 4/5 осуда ент" ЕННО-иадатвльСкий камбинат " ОИЗ каз 2 ВН