Устройство для решения систем линейных алгебраических уравнений с треугольной матрицей

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКРЕСПУБЛИК 1803 9) -ъЫ 5)5 0 06 Р 15/34 ОПИС РЕТЕН ие относится к вычислитель- может быть использовано в ванных системах цифровой формации, Целью изобретеповышение быстродействия. цель достигается тем, что усжит матрицу НХН зэпоминапервую вычислительную у вычислительных ячеек, втольную ячейку. 4 ил. ательЯ СИС- ЕСКИХ Операционный блок 6 с номером) = 2.п содержит (фиг,2) первый вход 6.1, первый выход 6,2, второй вход 6.3, третий выход 6.4, четвертый вход 6.5, третий вход б,б, второй выход 6,7, пятый вход 6.8, четвертый выход 6,9, умножитель 8, сумматор 9, мультиплексоры 10 и 11, регистры 12 - 15, причем входы умножителя 8 соединены с входом 6.1 ячейки и выходом мультиплексора 10, один вход которого объединен с входом регистра 12 и является входом 7,6 ячейки, другой вход первого мультиплексора 10 объединен с входом регистра 13 и является входом ячейки, выход умножителя 8 соединен с первым входом сумматора 9, выход которого подключен к входам регистров 14 и 15, а второй вход к выходу мультиплексора 11, входы которого подключены к входам 6.3 и 6.8 ячейки. Выходы регистров 12 - 15 подключены к выходам 6,2, 6.9, 6,7 и 6.4 ячейки соответственно.Устройство работает следую льзовдно цифрово щим обра нятся зле , причем в онныи выход 8, информационветственно. перационных блоках х матрицы 1 а по диагона ент ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(2) В.А,Грачевфб) Авторское свидетельство СССМ 1324036, кл. 0 06 Р 15/347, 198Патент США В 4493048,Кл. 0 06 Р 7/38, опублик, 1989,(В 4) УСТРОЙСТВО ДЛЯ РЕШЕН1 ЕМ ЛИНЕЙНЫХ АЛГЕБРАИ Изобретение относится к вычислительной технике и может быть испо в специализированных системах й обработки информации.Целью предложения является повышение быстродействия,На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг, 2 - функциональная схема )-й вычислительной ячейки О = 2, и); на фиг, 3 - временная диаграмма работы вычислительных ячеек; на фиг. 4 - функциональная схема эпоминающих ячеек.Устройство для решения СЛАУ с треугОльной матрицей содержит информационнй вход 1, матрицу 2 запоминающих ячеек ЗЗЯД, операционный блок 4, выполняющую1базовую операцию у = (Ь-х) - , группу 5 иза(Н - 1) операционных блоков 6, операционный блок 7, выполняющий базовую операцию у = (Ь - х) - информаци1а информационный выход ньй выход 10 и вход 11 с УРАВНЕНИЙ ЦЕЙ(57) Изобретен ной технике и специализиро обработки ин ния является Поставленная тройство содер ющих ячеек, ячейку матриц рую вычислите ТРЕУГОЛЬНОИ МАТРИ 1803921ячейке ЗЯ хранятся элементы главной 1 диаГОНаЛИ МатРИЦ 1 И .2 т,Е. 11(пп ) И111 )пп ). В общем случае в ячейкегЗЯ у = 1,п. хранятся элементы (а,=),и, М = Тчп.+, п 1 = 1,2, причем епемеиты мет.риц )1 и .2 в ячейках памяти каждой ЗЯ) расположены следующим образом0)1( ): 1( ); )+,2( ) +1,2( );(1)Элементы матрицз и4 расположены в ячейках ЗЯ), ) = и+1,2, аналогично элементам матриц (1 и .2 отличие заключается в том, что элементы диагоналей матриц загружаются, начиная с правого конца линейки ЗЯ); т,к, в ячейку 3 ЗЯп+1 загружаются элементы главной диагонали, в ячейку 3 ЗЯп элементы и, Н,= 2,п; К = 1, пи т.д.Каждая ячейка 3 ЗЯ), ) = 1, и+1 представляет собой дуальный буфер, что позволяет загружать элементы матриц1 -4 в ячейки 3 матрицы 2 на фоне решения СЛАУ для четырех матриц, загруженных ранее,Рассмотрим организацию вычислительного процесса на примере решения СЛАУ (, х = Ь 1. В устройстве для решения СЛАУ с треугольной матрицей элементы вектора решений формируются в соответствии с формулой;х; = (Ь - у ) - ,= 1,п, у = О, (2)(н) 1, (о) к где у - вычисляется по рекур рентн омусоотношениюПроцесс вычисления элементов вектора решений начинается с формирования элемента х 1 в микротакте то, по формулет.к. у 1( ) = О,В этом микротакте на один из входов блока 4 с информационного выхода 9 передаются координаты Ь 1 вектора свободных членов, а на другой вход блока 41 с выхо(д 1 а ячейки 3 поступает элемент матрицы (11 ). Вычисленная в миротакте , координата х 1 записывается в конвейерный регистр ячей и 4 и в микротакте с 1 передается на вход 6,6 блока 6; в этом же микротакте на в)ход 6.1 из ячейки ЗЯ поступает элемент 21 матриц. В микротакте т 1 с помощью мультиплексора 10, умножителя 8 и сумматора 9 блока 6 ВЯ формируется промежуточный параметр у 2( )(1)14 блока 6 ВЯ и выход 6.7 передается в блок4, в котором по формуле (2) формируетсякоордината х 2 вектора решений, а координата х 1 в этом микротакте записывается в10 регистр 12 и передается через выход 6.3блока 6 на вход 6.6 блока 6, в котором формируется по формуле (3) промежуточный параметр уз )1).В дальнейшем элементы х вектора решений, распространяясь слева направовдоль линейки блока 6 (по шине, образованной входом 6.6 регистром 12 и выходом 6.2блока), ) = 2,п), участвуют в формированиипромежуточных параметров у), причем в20 ячейке 6 ВЯ формируется параметр у;("), вблоке 6 - у; ) и т.д. Параметр у; форми у(х- )ется по формуле (3), причем параметр уг"поступает на вход 6,3 блока 6.Я+1. В блоке6 а+1 с помощью мультиплексоров 10 и 11,25 умножителя 8 и сумматора 9 формируетсяпараметр у, который через регистр 14,.0-1)выход 6,7 блока 6 передается на вход 6,3.блока 6 ь+1.Аналогичным образом в микротактах30 т 2, ци 2 а формируется решение СЛАу2 х = Ь 2. Решение СЛАУ Ы = Ьз и4 х =14производится аналогично СЛАУ Ох = Ь 1 и2 х = Ь 2, отличие заключается в следующем;1. Потоки элементов векторов решений35 х, х и промежуточных параметров ураспространяются по шинам, образованным входом 6,5, регистром 13, выходом 6,9и входом 6.,8, регистром 5, выходом 6.4 каждой ячейки 6 ВЯ),= п.2 в направлении,40 противоположном направлению распространения соответствующих потоков дляСЛАУ ( х = Ь 1 и2 х = Ь 2.2, Ввод элементов матрицыз произво- дится с задержкой на и микротактов по от 45 ношению к началу ввода элементовматрицы1.3. Ввод элементов матрицз и .4 производится, начиная с ячейки 7 ВЯп+1, т.е. в этуячейку передаются элементы главной диаго 50 нали, в ячейку 6 ВЯп элементы диагоналит+1 "), Ц, 1 = 1, ии т,д,Временная диаграмма, поясняющаяфункционирование устройства приведенана фиг. 3 и в таблице,55Формула изобретенияУстройство для решения систем линейных алгебраических уравнений с треугольной матрицей, содержащее Н+1 узловбуферной памяти, где Н х Н - размерность треугольной матрицы, группу из (Н - 1)-го операционного блока и первого операционного блока, причем первый и второй входы коэффициентов треугольной матрицы устройства подключены соответственно к информационному входу первого узла буферной памяти и к первому информационному входу первого операционного блока, первый и второй выходы которого подключены соответственно к первому информационному и первому управляющему входам первого операционного блока группы, первый и второй выходы а-го операционного блока группы, где а = 1 Н, подключены соответственно к первому информационному и первому управляющему входам(а+1)-го операционного блока группы, первый и второй выходы (Н)-го операционного блока группы подключены соответственно к выходам результата первой группы устройства, первый выход первого узла буферной памяти подключен к второму информационному входу первого операционного блока, третий информационный вход которого подключен к третьему выходу первого операционного блока группы, второй информационный вход а-го операционного блока группы подключен к третьему выходу (а+1)-го операционного блока группы, первые выходы узлов буферной памяти с второго по Н-й подключены соответственно к третьему информационному входу операционных блоков с первого по (Н)-й группы, с первого по (Н+1)-й управляющий входы устройства подключены соответственно к входам чтения- записи узлов буферной памяти с первого по (Н+1) й, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит второй операционный блок, причем третий и четвертый входы коэффициентов треугольной матрицы устройства подключены соответственно к первому информационному входу второго операционного блокавторому информационному входу (Н)-го рперационного блока группы, четвертый Вход коэффициентов треугольной матрицы и (Н+2)-й управляющий вход устройства подключены соответственно к четвертому Информационному и к второму управляющему входам первого операционного блока группы, четвертый и пятый выходы а-го операционного блока группы подключены соотВетственно к четвертому информационномувторому управляющему входам (а+1)-го Операционного блока группы, шестой выходпервого операционного блока группы подключен к второму выходу результата устройства, первый выход (Н+1)-го узла буферной памяти подключен к второму информацион 5 10 15 20 25 30 35 40 45 50 55 ному входу второго операционного блока, четвертый выход (Н)-го операционного блока группы подключен к третьему информационному входу второго операционного блока, выход которого подключен к пятому информационному входу (Н)-го операционного блока группы, пятый информационный вход а-го операционного блока группы подключен к шестому выходу (а+1)-го операционного блока группы, второй выход К-го узла буферной памяти (где К = 1,.,Н) подключен к информационному входу (К+1)-го узла буферной памяти, вход синхронизации устройства подключен к входам синхронизации операционных блоков группы, первого и второго операционных блоков, причем каждый операционный блок группы содержит умножитель, сумматор, два мультиплексора и четыре регистра в каждом операционном блоке группы первый информационный вход операционного блока группы подключен к информационному входу первого регистра и к первому информационному входу первого мультиплексора, первый управляющий вход операционного блока группы подключен к управляющему входу первого мультиплексора, второй и третий информационные входы операционного блока группы подключены соответственно к первым информационным входа. второго мультиплексора и умножителя, четвертый информационный и второй управляющий входы операционного блока группы подключены соответственно к второму информационному и управляющему входам второго мультиплексора, выход которого подключен к первому информационному входу сумматора, выход которого подключен к информационным входам второго и третьего регистров, пятый информационный входоперационного блока группы подключен к информационному входу четвертого регистра и второму информационному входу первого мультиплексора, выход которого подключен к второму информационному входу умножителя, выход которого подключен к второму информационному входу сумматора, первый и второй выходы первого регистра подключены соответственно к первому и второму выходам операционного блока группы, выход второго регистра подключен к третьему выходу операционного блока группы, первый и второй выходы третьего регистра подключены соответственно к четвертому и пятому выходам операционного блока группы, выход четвертого регистра подключен к шестому выходу операционного блока группы, вход синхронизации которого подключен к входам записи-считывания регистров с первого по четвертый, 18039211803921 Синхротактц Бит управлениямультиплексорами д 6,6 Составитель Г. СмирноТехред М,Моргентал Фил Корре Редакто ванова аказ 1058 ВНИИПИ Госуда Производственно-издательский комбинат "Патент". г, Ужгород, ул.Гагарина. 101 ФТир ННОГО 3035,ЯфЪ( Выход 6.97 1ЯеДЯ,у Я,д 1 Выкод 6. Подписноеитета по изобретениям и открытиям при ГКНва, Ж, Раушская наб., 4/5