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

)5 6 06 ТЕНИ ЕЛЬСТВ ГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССРГОСПАТЕНТ СССР) ОПИСАНИ К АВТОРСКОМУ СВ(71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции(56) й, Мейегп, Рагае . Оаизз-,)огбап еапаТ)оп аког Йе зо)ц 1 оп о 1 бепзе Пеаг зузсеаз, - Рагае Согпр. М 4 1987, с.339,М ногофун кциональн ые систолические структуры./Под ред.Дуброва Я.А, Препринт М 20-89, Львов, 1989, ин-т прикладных проблем механики и математики АН УССР, с.38. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для решения задач линейной алгебры,Цель изобретения - снижение аппаратурных затрат и повышение точности вычислений за счет применения алгоритма Жордана-Гаусса с частичным выбором ведущего элемента по столбцу.На фиг. 1 представлена структурная схема устройства для решения СЛАУ; на фиг, 2 - структурная схема первого процессорного элемента; на фиг. 2 - структурная схема возможного варианта построения блока синхронизации; на фиг, 4 - структурная схема -го процессорного элемента(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных в том числе и систолических устройств, предназначенных для решения задач линейной алгебры. Предложенное устройство позволяет вдвое сократить объем оборудования и повысить точность вычислений по сравнению с прототипом. Устройство содержит (и/2+1) процессорных элементов (где и - четное, порядок матрицы коэффициентов системы) и блок синхронизации. Принцип работы устройства основан на решении системы линейных алгебраических уравнений вида Ах = Ь методом Жордана - Гаусса с частичным выбором ведущего элемента по столбцу, 5 ил., 1 табл,( = 2, и/2+1); на фиг, 5 - диаграмма работы блока синхронизации для случая п = 4.В тексте приведена таблица, иллюстрирующая работу устройства для случая и = 4,Устройство для решения СЛАУ содержит процессорные элементы 1,1 - 1,(п/2+1), где и - четное, причем выходы процессорного элемента 1, с первого по пятый ( = 1,п/2) подключены ко входам, соответственно, с первого по пятый процессорного элемента 1,(+1), входы процессорного элемента 1,1 с первого по пятый, подключены, соответственно к выходам с первого по пятый блока 2 синхронизации, вход которого является входом запуска устройства, выходы процессорного элемента 1.(п/2+1), с четвертого по шестой подключены, соответственно, к его входам с девятого по одиннадцатый, шестой выход процессорного элемента 1, ( = 2,п 72)3 с 556 1 Дищщ Дс сэ . 351829043 Составитель О. МасленниковРедактор Т, Иванова Техред М.Моргентал Корректор Л. Филь нт", г. Ужгород, ул,Гагарина,каз 2476 Тираж ВНИИПИ Государственного комитета по изоб 113035, Москва, Ж, Рауроизводственно-издательский комбинат "Па Подписноеениям и открытиям при ГКкая наб 4/5подключен к шестому входу процессорного элемента 1,(1+1), выходы процессорного элемента 1, с седьмого по одиннадцатый= З,п 72 ч 1), подключены соответственно, ко входам с седьмого по одиннадцатый процессорного элемента 1,(1-1), одиннадцатый выход процессорного элемента 1,2 подключен к шестому входу процессорного элемента 1.1, шестой выход которого является выходом устройства, вход которого подключен к седьмому входу процессорного эле- ".ента 1.1 и к двенадцатым входам остальных процессорных элементов, первый и Второй ВыхОды процессорного элемента 1,(п/2+1) подключены к седьмому и восьмомуодам процессорного элемента 1.(п/2+1) соответственно,Процессорный элемент 1,1, содержит блок 3 деления, выход которого подключен ко входу первого блока элементов задержки 4, а первый вход его связан с выходом первого регистра 5, вход которого связан с выходом первого коммутатора 6 и со входом второго регистра 7, выход которого подключен к первым входам схемы 8 сравнения, и первого 6 и второго 9 коммутаторов, вторые входы которых также обьединены и подключены к выходу третьего коммутатора 10, первый и второй входы которого являются, соответственно, шестым и седьмым входами первого процессорного элемента, выходы которого, с первого по третий, подключены, соответственно, выходам с первого по третий второго блока элементов задержки 11, входы которого с первого по третий, являются соответственно первым, вторым и пятым входами первого процессорного элемента, пятый и четвертый выходы которого подключены соответственно, к выходам первого 4 и третьего 12 блока элементов задержки, вход которого связан с управляющими входами коммутаторов 6, 9 и с выходом элемента И 13, первый вход которого подключен к третьему входу первого процессорного элемента, четвертый вход которого подключен к первому входу элемента ИЛИ 14, второй вход которого является выходом схемы 8 сравнения, выход коммутатора 9 подключен ко входу четвертого блока элементов задержки 15, выход которого является шестым выходом первого процессорного элемента и подключен ко второму входу блока 3 деления, вход выбора режима которого (деление с обратным знаком или нахождение обратной величины) связан с управляющим входом регистра 5 и является пятым входом первого процессорного элемента, управляющий вход коммутатора 10 подключен ко второму входу первого процессорного элемента, выход 5 10 15 20 25 30 35 40 45 50 55 элемента ИЛИ 14 связан со вторым входом элемента И 13. Процессорный элемент 1, ( = 2, и/2+1) содержит умножитель 16, первый вход которого подключен к выходу первого регистра 17, вход которого подключен к выходу первого коммутатора 18 и ко входу второго регистра 19, выход которого подключен к первым входам первого 18 и второго 20 коммутаторов, вторые входы которых объединены и связаны с выходом третьего коммутатора 21, первый вход которого подключен к выходу четвертого коммутатора 22, первый и второй входы которого являются, соответственно, шестым и одиннадцатым входами процессорного элемента 1 входы и выходы которого с первого по третий, подключены, соответственно, ко входам и выходам с первого по третий, первого блока элементов задержки 23, второй вход умножителя 16 подключен к выходу пятого коммутатора 24, первый и второй входы которого являются, соответственно, пятым и десятым входами процессорного элемента 1,и подключены, соответственно, ко входам второго - 25 и третьего 26, блоков элементов задержки, выходы которых являются соответственно пятым и десятым выходами процессорного элемента 1., четвертый и девятый выходы которого подключены к выходам соответственно четвертого 27 и пятого 28 блоков элементов задержки, вход которого является входом процессорного элемента 1. и подключен к первому входу шестого коммутатора 29, первый выход которого подключен к управляющим входам коммутаторов 18 и 20, выход коммутатора 20 подключен ко входу шестого блока элементов задержки 30, выход которого связан с первым входом сумматора 31, выход которого является шестым и одиннадцатым выходами процессорного элемента 1,1, седьмой и восьмой выходы которого подключены, соответственно, к первому и второму выходам седьмого блока элементов задержки 32, первый и второй входы которого являются соответственно седьмым и восьмым входами процессорного элемента 1., четвертый вход которого подключен ко входу блока элементов задержки 27, и к третьему входу коммутатора 28, второй и четвертый входы которого подключены соответственно к восьмому и второму входам процессорного элемента 1., второй выход коммутатора 29 является управляющим входом коммутатора 21, второй вход которого подключен к двенадцатому входу процессорного элемента 1 л, управляющий вход коммутатора 22 подключен к седьмому входу процессорного элемента и ко входу инвертора 33, выход которого связан с пер 1829043вым входом элемента ИЛИ 34, второй вход которого подключен к первому входу процессорного элемента, третий вход процессорного элемента связан с управляющими входами сумматора 31 (сложение или пропуск операнда) и регистра 17, управляющий вход коммутатора 29 подключен к выходу элемента ИЛИ 34, и ко входу восьмого блока элементов задержки 35, выход которого подключен к управляющему входу коммутатора 24, выход умножителя 16 подключен ко второму входу сумматора 31.Блок 2 синхронизации может содержать (см. фиг. 3) счетчик 52, выход отрицательного переноса которого является пятым выходом блока 2 и связан со входом элемента ИЛИ 53, выход которого подключен к)-и к - выходам )-к триггеров 36, и ко входу О-триггера 37, выход которого является четвертым выходом блока 2 и подключен ко входу выбора режима (параллельное занесение значения (и) или счет в режиме вычитания) счетчика 52 и к й-входу асинхронного Я- триггера 38, прямой выход которого является вторым выходом блока 2, вход запуска которого связан со входом элемента ИЛИ 53 и со входом О-триггера 39, выход которого связан со входами элементов И 40, 42 и с Я-входами триггера 362 и 38, инверсный выход которого подключен ко входам элементов И 41 и 43, выходы которых подключены, соответственно к синхровходам О-триггеров 44, 46 и 45, 47, а также к синхровходам блоков элементов задержки 54 и 55, выходы которых являются входами коммутатора 48 и подключены ко входам элементов И 49, 56 и 50, 57, входы установки в нуль О-триггеров 44, 45, связаны со входами установки в единицу О-триггеров 46, 47 и триггеров блоков элементов задержки, и подключены к выходам элементов И 40 и 42 соответственно, третий выход блока 2 подключен к выходу коммутатора 48, управляющий вход которого подключен ко входам элементов И 42, 43 и к прямому выходу)-к-триггера 361, инверсный выход которого подключен ко входам элементов И 40, 41, выходы О-триггеров 45 и 44 подключены ко входам элементов И 50 и 49, выходы которых связаны со входами О-триггеров 47 и 46, выходы которых подключены ко входам элементов И 57 и 56 соответственно, на входы О-триггеров 44, 45 постоянно заводится значение логической единицы, Кроме того, в состав блока синхронизации входит генератор тактовых импульсов 51, выход которого подключен ко входам элементов И 41 и 43, к синхровходам счетчика 52, триггеров 36, 37, 39, а также к синхровходам всех регистров и блоков элементов задержки всех процессорных эле ментов (на чертежах для простоты эти связи не показаны).Блоки элементов задержки представляют собой цепочку из и(блок 15, 54, 55, 30) 5 или п (все остальные блоки) регистров (блоки 4, 15, 25, 26, 30) или О-триггеров (блоки 12, 27, 28, 54, 55, 35, 11, 23 и 32), вход первого из которых является входом соответствующего блока, а выход последнего - 10 выходом блока. Таким образом они формируют задержку сигнала или операнда на п или итактов, Необходимо отметить, что блоки 11, 23 и 32 содержат три независимых цепочки из и О-триггеров и осуществляют 15 задержку на и тактов сразу трех блок 32 двух) управляющих сигналов, поступающих на их входы,Устройство для решения СЛАУ предназначено для решения СЛАУ вида20 а 11 х 1+ а 12 х 2+ . + а 1 п хп = а 1(п 1); а 21 Х 1+ а 22 Х 2+ + д 2 п Хп = д 2(п) дп 1 Х 1+ дп 2 Х 2++ дпп Хп = дп(п+1),25методом Гаусса-Жордана, который можно записать в рекуррентном виде следующимобразом: а; = а= 1,п; ) = 1, п;+1,д(п+1) = П 1(п+) аак = +1, и+1. 30 35 В результате выполнения этого алгоритма определяются искомые элементы х 40х = а (и+)(и+1),= 1,п,С целью повышения численной устойчивости вычислений заявляемое устройство реализует алгоритмы Гаусса-Жордана с час тичным выбором ведущего элемента постолбцу. Это означает, что на -м шаге алгоритма= 1,п исключению элементов а(К = +1, и+1-1) принадлежащих исходной расширенной матрице А = А (при= 1) или 50 уже частично преобразованной матрице А(при1) предшествует последовательное сравнение элементов а ) =+1 кп) с элементом а и если очередной элемента)аосуществляется перестановка )- и -й 55 строк. Только после окончания всех (на данном шаге) операций сравнения и перестановок (т,е. процесса выбора ведущего элемента), начи нается и роцесс и рео 6 разования строк с (+1)-й по (и+1)-ю, выполняемый в соответствии с указанным выше10 15 20 25 30 40 45 50 55 алгоритмом. Таким образом, процесс выбора ведущего элемента распространяется только на первых и строк матрицы А,Вычислительный процесс в устройстве организован таким образом, что одна матрица СЛАУ обрабатывается 2 п(п+1) тактов, однако одновременно происходит обработка двух различных матриц, моменты начала поступления на вход устройства которых разнесены на п(п+1) тактов, Т.е., если элементы матрицы А первой СЛАУ начинают поступать на вход устройства с первого такта его работы, то элементы матрицы В следующей СЛАУ начинают поступать с п(п+1)+1-го такта, и период работы устройства в реж ме поточной обработки, т.о., составляет п(п+1) тактов (см. фиг, 5, где С 1 элементы матрицы С той СЛАУ, которая начала обрабатываться за п(п+1) такт до начала обработки матрицы А. Вследствие этого в блок синхронизации устройства входит два одинаковых блока триггеров, элементов И и блоков элементов задержки, вырабатывающих управляющие сигналы (каждый для своей матрицы) для параллельной обработки двух матриц (см, фиг, 3 и 6).Поступление исходных данных организовано следующим образом (см. фиг, 5). На вход устройства начиная с первого такта каждый такт последовательно поступают элементы матрицы А исходной системы по столбцам, начиная с элемента а 1 и заканчивая аьч( =1, и+1), т.е. первые п тактов поступают элементы первого столбца матрицы А,вторые п тактов - элементы второго столбца и т,д,Кратко рассмотрим алгоритм работы процессорных элементов. Как уже отмечалось выше, на вход устройства начиная с первого такта последовательно поступают элементы первого столбца матрицы А, При этом коммутатор 10 пропускает их на входы коммутаторов 6, 9 и схемы сравнения 8. Управление коммутаторами 6, 9 организовано таким образом, что элемент а в первом такте принимается в регистр 7, Во втором такте а 21 с выхода коммутатора 10 поступает на вторые входы коммутаторов 6, 9 и схемы 8, на первые входы которых поступает а 11 и, еслиа 21а 111, на выходе схемы 8 появляется единица (признак перестановки строк О 21 = 1 см, алгоритм), который через элементы 13 и 14 поступает на управляющие входы коммутаторов 6, 9, в результате чего а 21 записывается в регистр 7, а 11 - в регистр 1 (Рг 1) блока 15, а О 21 - в триггер 1 (Тр 1) блока 12. Если условие не выполняется, нуль с выхода схемы 8 записывается в Тр 1 блока 12, ать - в Рг 1 блока 15, а - перезаписывается в регистр 7. В последующих тактах каждый поступающий элемент а 1 сравнивается с= З,п) максимальным (из регистра 7) аналогично второму такту, заполняя блок 15, а вырабатываемые признаки О;1 записываются в блок 12, (т.е, осуществляется выбор ведущего элемента). В и-м такте максимальный элемент переписывается в регистр 5. Начиная с (и+1)-го такта на вход устройства поступают элементы второго столбца матрицы А, которые поступают в процессорный элемент 1.2 через коммутатор 21.2. Элементы второго столбца заполняют блок 30,2 и регистр 19,2 под управлением признаков 01= 2,п) поступающих с блока 12 через коммутатор 29.2 на управляющие входы коммутаторов 18.2 и 20,2, т.е. осуществляется перестановка строк с ведущей строкой, В то же время процессорный элемент 1.1 производит вычисление коэффициентов в, заполняя блок 4, Начиная с (2 п+1)-го такта на вход устройства поступают элементы третьего столбца матрицы А, которые поступают в процессорный элемент 1.3 и заполняют блок 30.3 и регистр 19.3 под управлением признаков О 1, поступающими с блока 27,2 через коммутатор 29,3, В это время процессорный элемент 1,2 производит перевычисление элементов второго столбца матрицы а 2 (см, алгоритм), которые с выхода сум, 2матора 31,2 поступают на процессорный элемент 1.1, где происходит выявление максимального (по абсолютной величине) из них аналогично первым и тактам работы, и вновь заполняются блоки 15 и 12, Таким образом начинается второй шаг алгоритма, Далее действия выполняются аналогично (см, фиг, 5).Рассмотрим работу устройства. Для простоты описания и без потери общности положим и = 4, Условимся, что прием информации в триггеры 44 - 47, блоки 11, 23, 32, 35, 54, 55 и счетчик 52 осуществляется по переднему фронту тактового импульса, т,е. в начале такта, а во все регистры, блоки 4, 15, 12, 25 - 28, 30, триггеры 36, 37 и 39 - по заднему фронту тактового импульса. Пусть перед началом вычислений триггер 36 и триггеры блоков 11, 23, 32, 35 установлены в нулевое состоя н ие.Импульс пуска, поступающий на вход запуска устройства (см. фиг. 2 и 6) по заднему фронту тактового импульса устанавливает в единицу триггеры 37, 39, 36. Также устанавливаются в единицу Я-триггер 38, триггер 47, блок 55, а в нуль - триггер 45, Коммутатор 48 пропускает единицу с выхода блока 55 на третий выход блока 2, В следующем, первом такте в счетчик 52 по переднему фронту тактового импульса за 1829043 10писывается значение (и) = 3 в двоичном коде, на выходе отрицательного переноса счетчика находится нуль, по заднему фронту тактового импульса триггеры 37 и 39 сбрасываются в нуль, а 11 = а 11 поступает со1входа на седьмой вход процессорного элемента 1.1, и пройдя через коммутаторы 10 и 6 (на их управляющих входах единицы), записывается по заднему фронту тактового импульса в регистр 7, а единица с четвертого входа процессорного элемента 1.1 - в Тр 1 блока 12, Во втором такте аг 1 = аг 1 со1 входа устройства поступает через коммутатор 10 на второй вход схемы сравнения 8, на первый вход которой подается а 11, Пустьаг 1"а 11 , Тогда нуль с выхода схемы 8 записывается в Тр 1 блока 12 (Ог 1 = О), единица переписывается в Тр 2 блока 11, аг 1 записывается в Рг 1 блока 15, а 11 пере 1записывается в регистр 7, содержимое счетчика 52 уменьшается на единицу. В третьем такте аз 1= аз 1 поступает со входа устройст 1ва в процессорный элемент 1.1, где аналогично второму такту сравнивается с а 11. Пустьаз 1а 11 . Тогда нуль с выхо 1да схемы 8 записывается в Тр 1 блока 12 (Оз 1 = О), аз 1 записывается в Рг 1 блока 15, аг 1 - в Р, 2 блока 15, содержимое счетчика 52 уменьшается на единицу, Ог 1 переписывается в Тр 2 блока 12, В четвертом такте содержимое счетчика 52 становится равным нулю, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в нуль триггер 36, в единицу триггер 37, а он, в свою очередь, сбрасывает в нуль триггер 38, а 41 = а 41 поступает на вход процессорного элемента 1.1 и сравнивается с а 11 аналогично второму и третьему такту, Пусть а 11"а 41. Тогда единица с выхода схемы 8 (О 41 = 1) записывается в Тр 1 блока 12, а 11 записывается в Рг 1 блока 15, а а 41 - в регистр 5 (а 41 ведущий элемент, следовательно, ведущей строкой на первом шаге алгоритма стала четвертая строка матрицы А). На инверсном выходе триггера 38 появляется единица, которая разрешает прохождение тактовых импульсов через элемент И 14, Кроме того, нуль с выхода этого триггера поступает на управляющий вход коммутатора 10, и он передает на свой выход значения с первого своего входа, Параллельно с этим, в первых четырех тактах в процессорном элементе 1,2 идет вычисление 1 з матрицы С. В пятом такте на вход устройства поступает а 1 г = а 1 г, которое пройдя через комму 1татары 21.2 и 18,2 записывается в регистр 5 10 15 20 25 30 35 40 45 50 55 19.2, поскольку коммутатор 29,2 пропускает на свои выходы информацию со своего четвертого и третьего входов, В этом же такте в счетчик 52 вновь записывается значение (и) = 3 в двоичном коде, аг 1 с выхода блока 15 поступает на вход блока 3, на другой вход котоого подается а 41, и ре 1 зультат гпг 1= -аг 1 /а 41 по заднему фронту тактового импульса записывается в Рг 1 блока 4.В шестом такте на вход устройства поступает агг = агг, которое пройдя через коммутаторы 21,2 и 20.2 записывается в Рг 1 блока 30.2, поскольку на управляющие входы коммутаторов 20.2 и 18,2 поступает Ог 1 = 0 с первого выхода (и третьего входа) коммутатора 29.2, а перезаписывается в регистр 19.2. В этом же такте аз 1 с выхода блока 15 поступает на вход блока 3, и результат щз 1 =-аз 1 /а 41 записывается в Рг 11блока 4, а щг 1 переписывается в Рг 2 блока 4, Ог 1 записывается в Тр 1 блока 27, а единица перезаписывается в Тр 2 блока 27, счетчик 52 уменьшает свое значение на единицу.В седьмом такте азг = азг со входа устройства поступает в процессорный элемент 1,2, и записывается в Рг 1 блока 30.2, Оз 1 = 0 переписывается в Тр 1 блока 27,2, Ог 1 - в Тр 2 блока 27.2, единица - в Тр 3 блока 27.2, а 1 г переписывается в регистр 19,2, а 11 с выхода блока 15 поступает на вход блока 3, с выхода которого результат п 141 = а 11 /а 41 записывается в Рг 11 1блока 4, счетчик 52 уменьшает свое значение на единицу.В восьмом такте содержимое счетчика 52 становится равным нулю, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в единицу триггеры 37 и 36, и таким образом разрешается прохождение тактовых импульсов через элемент И 43. В этом же такте а 4 г = а 4 г со входа устройства поступает и записывается в регистры 19.2 и 17,2, а а 1 г" из регистра 19.2 переписывается в Рг 1 блока 30.2, 041 = 1 переписывается в Тр 1 блока 27,2, на вход выбора режима блока 3 поступает единица, и значение 1/а 41 = п 151 записывается в Р 1 блока 4. Параллельно с этим, во вторых четырех тактах идет выбор ведущего элемента матрицы С(1 = 4) в прОцЕССОрнсм ЭлЕмЕнтЕ 1.1, и перевычисление в процессорных элемЕнтах 1,2 и 1,3 С 14 и С 15 (См. фиг.5), КрсмЕ того, на управляющем входе коммутатора 21.2 появляется нуль, и он начинает передавать на свой выход информацию с выхода коммутатора 22.2.40 45 50 55 В девятом такте нуль с выхода триггера 45 записывается в триггер 47, единица записывается в триггер 45, (и= 3 записывается в счетчик 52, а 1 з = а 1 з поступает со входа устройства в процессорный элемент 1.3, и пройдя через коммутатор 21.3 и 18.3 записывается в регистр 19.3, поскольку коммутатор 29.3 пропускает на свои выходы информацию со своего третьего и четвертого входов. В этом же такте из блока 4 через коммутатор 24,2 (на его управляющем входе появляется единица, которая будет присутствовать и = 4 такта) на вход умножителя 16.2 поступает п 121, на другой вход его поступает а 4; из регистра 17.2, и результат гпг 1 а 42 потупает на вход сумматора 31.2, на другой вход которого подается агг с выхода блока 30.2. С выхо 1 да сумматора 31,2 результат аг 21 + п 121 а 42 = агг поступает2через коммутатор 10 в процессорный элемент 1,1, и записывается в регистр 7(аналогично первому такту). В десятом такте счетчик 52 уменьшает свое состояние на единицу, нуль из триггера 47 переписывается в Тр 1 блока 55, а 2 З = агз поступает со входа устройства в процессорный элемент 1,3, и пройдя через коммутаторы 21.3 и 20,3 записывается в Рг 1 блока 30.3, О 21 = 0 переписывается в Тр 1 блока 27,3, а а, переписывается в регистр 19,3. В этом же такте из блока 4 на вход умножителя 16,2 поступает гпз 1, с выхода которого аз 1/а 42 поступает на вход сумматора 31.2, на другой вход которого подается азг с выхода блока 30.2. С выхода сумматора 31.2 результат аз 21+ п 1 з 1 а 42 = аз 2 поступает через коммутатор 10 в процессорный элемент 1.1, где сравнивается с а 22 аналогич 2но второму такту, Пусть 1 дзг 1д 22 1.2 2 Тогда единица с выхода схемы 8 сравнения (Озг = 1) записывается в Тр 1 блока 12, а также поступает на управляющие входы коммутаторов 6 и 9, в результате чего азгг появляется в регистре 7, а агг записывается2в Рг 1 блока 15. В одиннадцатом такте счетчик 52 уменьшает свое состояние на единицу, нуль переписывается в Тр 2 блока 55, азз = азз поступает со входа устройства в процессорный блок 1.3 и записывается в Р, 1 блока 30.3, Оз 1 = 0 переписывается в Тр 1 блока 27.3, а 1 з перезаписывается в регистр 19.3. В этом же такте из блока 4 на вход умножителя 16,2 поступает п 141, с его выхода п 141 а 42 поступает на сумматор, с выхода которого результат а 12 + а 42 - а 41 = а 421,1 2 поступает в процессорный элемент 1,1, где 5 10 15 20 25 30 35 сравнивается с аз 2, Пусть ) а 42азг2 2Тогда нуль с выхода схемы 8 (О 42 = 0) записывается в Тр 1 блока 12, а также управляет работой коммутаторов б и 9 так что а 42 записывается в Рг 1 блока 15, а аз 2 остается в регистре 7,В двенадцатом такте счетчик 52 уменьшает свое значение до нуля, и на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в нуль триггер 36, а в единицу - 37, нуль переписывается в Тр 3 блока 55 и появляется на его выходе и на выходе коммутатора 48 (в течение интервала от начала такта до заднего фронта тактового импульса), а 4 з = а 4 з поступает со входа устройства в процессорный элемент 1.3 и записывается в регистры 19.3 и 17,3, О 41 = 1 переписывается в Тр 1 блока 27,3, а 1 з записывается в Рг 1 блока 30,3, В этом же такте из блока 4 нэ вход умножителя 16,2 поступает в 51, с его выхода п 151 а 42 поступает на сумматор 31.2, который осуществляет пропуск операнда (на его управляющем входе единица) и результат гп 51 а 42 = аБ 2 с выхода сумматора поступает в процессорный элемент 1.1, где без операции сравнения (на выходе элемента 13 нуль) записывается в Рг 1 блока 15, а в Тр 1 блока 12 записывается в нуль, Параллельно с этим, с девятого по двенадцатый такт в процессорном элементе 1.1 идет вычисление коэффициентов 114 матрицы С, в процессорных элементах 1.2 и 1.3 - перестановка элементов С;5, и вычисление элементов С 5, 4 , 4 соответственно. В тринадцатом такте в счетчик 52 записывается значение (и) = 3, на вход устройства поступает а 14 = а 14, которое пройдя через коммутатор 21.3 (на его управляющем входе остается единица, хотя коммутатор 29,3 уже передает на свои выходы информацию с первого и второго своих входов) и коммутатор 18.3, записывается в регистр 19,3. В этом же такте гп 21 через коммутатор 24.3 поступает на вход умножителя 16.3, на другой его вход поступает а 4 з из регистра 17,3, и результат гп 21 а 4 з поступает на вход сумматора 31,3, на другой вход которого подается агз с выхода блока 30,3. С выхода сумматора результат агз+ + а 21 а 4 з = а 2 з поступает через коммутаторы 22,2 и 21.2 в процессорный элемент 1,2, где записывается в регистр 19,2. В этом же такте а 22 с выхода блока 15 посту 2пает на блок 3, который выполняет деление, и результат взг = -аг 2 /азг принимается в2 2Рг 1 блока 4.В четырнадцатом такте счетчик 52 уменьшает свое значение на единицу, на вход устройства поступает а 24 = а 24, которое записывается в Рг 1 блока 30,3, О 21 = 0 переписывается в Тр 1 блока 28.3, вз 1 через коммутатор 24,3 поступает на вход умножителя 16.3, с выхода которого вз 1 а 4 з поступает на сумматор 31,3, с выхода которого результат азз + вз 1 а 4 з = азз поступает в1 . 1 2процессорный элемент 1.2, где записывается в регистр 19,2 (Оз 2 = 1), а а 2 з записыва 2ется в Рг 1 блока 30.2, В этом же такте а 422 с выхода блока 15 поступает на блок 3, с выхода которого п 14 г =-а 422/азг принимает 2ся в Рг 1 блока 4, вз 1 записывается в Рг 1 блока 25.3, а в 21 переписывается в Рг 2 блока 25.3.В пятнадцатом такте счетчик 52 уменьшает свое значение на единицу на вход устройства поступает аз 4 = аз 4, которое записывается в Рг 1 блока 30.3, Оз 1 = 0 переписывается в Тр 1 блока 28.3, в 41 поступает на вход умножителя 16.3, с выхода которого в 41 а 4 з поступает на сумматор 31,3, с выхода которого результат а 1 з + в 41 а 4 Э = а 4 з поступает в процессорный элемент 1,2, где записывается в Рг 1 блока 30.2 (О 42 = О), а азз остается2в регистре 19.2, О 42 переписывается в Тр 1 блока 27,2, Оз 2 - в Тр 2 блока 27.2, В этом же такте а 52 с выхода блока 15 поступает на блок 3, с выхода которого в 52 = -а 52 /аз 22 2 принимается в Рг 1 блока 4.В шестнадцатом такте содержимое счетчика 52 становится равным нулю, на его выходе отрицательного переноса появляется единица, которая по заднему фронту тактового импульса устанавливает в единицу триггеры 37 и 36, нэ вход устройства поступает а 44 = а 44, которое записывается в ре 1гистры 17,3 и 19,3, а 14 записывается в Рг 11блока 30,3, О 41 = 1 переписывается в Тр 1 блока 28.3, в 51 поступает на вход умножителя 16.3 с выхода которого в 51 а 4 з посту 1 пает на сумматор 31.3, который осуществляет пропуск операнда, и результат в 51 а 4 з =а 5 з с выхода сумматора посту 1пает в процессорный элемент 1.2, где записывается в Рг 1 блока 30.2. В этом же такте значение 1/азг = вбг записывается вгРг 1 блока 4 (на входе выбора режима блока 3 - единица),В семнадцатом такте в счетчик 52 записывается значение (и) = 3, вг 1 поступает с выхода блока 25,3 через коммутатор 24,3 нэ умножитель 16.3 (на управляющем входе коммутатора 24.3 нуль), на другой вход которого поступает а 44, с вы 1 хода умножителя 16,3 в 21 а 44 поступает на сумматор 31,3, с выхода которого ре 5 10 15 20 25 30 35 40 45 50 55 зультат а 24 + в 21 а 44 = а 24 поступает на1 . 1 2коммутатор 22,3, с выхода которого проходит через коммутаторы 21.3 и 18.3, и принимается в регистр 19.3. Кроме того, в этомтакте на вход устройства поступает а 15, которое поступает в процессорный элемент1,2 и пройдя через коммутаторы 21.2 и 18.2записывается в регистр 19.2. В этом же такте вз 2 с выхода блока 4 поступает на вхоумножителя 16.2, с выхода которого взгаззпоступает на вход сумматора 31.2, на другой вход которого поступает агз с выходаблока 30,2 и результат агз + взгазз = азз2 . 2 3с выхода сумматора поступает в процессорный элемент 1,1, где принимается в регистр 7.В восемнадцатом такте счетчик 52уменьшает свое значение на единицу, вз 1поступает на умножитель 16.3, с выхода которого вз 1 а 44 поступает на сумматор 31,3,с выхода которого результат аз 4 + вз 1 а 44 == аз 4 проходит через коммутаторы 22.3 и21.3 и записывается в регистр 19.3, а а 24записывается в Рг 1 блока 30,3, Кроме того,в этом же такте на вход устройства поступает аг 5, которое пройдя через коммутаторы 21.2 и 20.2 записывается в регистрРг 1 блока 30,2 (О 21 = 0), в 42 с выходаблока 4 поступает на умножитель 16.2, свыхода которого в 42 азз поступает навход сумматора 31,2, с выхода которого результат а 4 з + в 42 азз = а 4 з поступает вгпроцессорный элемент 1.1, где сравнивается с азз из регистра 7. Пусть азза 4 з(О 4 з = 1) записывается в Тр 1 блока 12, азззаписывается в Рг 1 блока 15, а ааз - взрегистр 7,В девятнадцатом такте счетчик 52уменьшает свое значение на единицу, в 41поступает на умножитель 16.3, с выходакоторого в 41 а 44 поступает на сумматор 31.3, с выхогда которого результата 14 + в 41 а 44 = а 44 проходит через комму 1татары 22,3 и 21.3 и записывается в Рг 1блока 30,3. Кроме того, в этом такте на входустройства поступает аз 5, которое пройдячерез коммутаторы 21.2 и 20.2 записываетсяв Рг 1 блока 30,2 (Оз 1= 0), в 52 с выхода блока4 поступает на умножитель 16,2, с выходакоторого в 52 азз поступает на вход сум 2матора 31.2, с выхода которого результата 5 з + вгазз = а 5 з поступает в процессор 2 . 2 3ный элемент 1,1, где без сзоавнения записывается в Рг 1 блока 15, азз переписываетсяв Рг 2 блока 15.В двадцатом такте счетчик 52 уменьшает свое значение до нуля, и на его выходеотрицательного переноса появляется единица, в 51 поступает на умножитель 16,3, с15 20 а 44, 36 - в нуль. 25 30 35 40 45 50 55 выхода которого т 51 а 44 поступает на сум 1матор 31,1, который пропускает это значение нд выход, и результат П 151 д 44 = а 541 2. поступает в Рг 1 блока 30,3, Кроме того, в этом такте на вход устройства поступает 5 а 45 = а 45, которое пройдя через коммутаторы 21.2 и 18,2, записывается в регистры 19,2 и 17,2 (041 = 1), а а 15 переписывается в1Рг 1 бЛОКа 30.2, П 152 С ВЫХОда бЛОКа 4 ПОСтупает на умножитель 16.2, с выхода которого 10 гп 52 азз поступает на сумматор 31.2 с выхогда которого результат азз гп 52 = а 5 з (на упг,равляющем входе сумматора единица) принимается в Рг 1 блока 15, пройдя через коммутаторы 10 и 9, Кроме того, в этом такте на вход запуска устройства поступает импульс пуска, который по заднему фронту тактового сигнала устанавливает триггеры 39, 37, 38, 46 и триггеры блока 54 в единицу,В двадцать первом такте аналогично первому такту, в счетчик 52 записывается значение (и) = 3, первый элемент Ь 11= Ь 111 очередной обрабатываемой матрицы В поступает на вход устройства, и пройдя через коммутаторы 10 и 6 записывается в регистр 7, а единица - в Тр 1 блока 12, Параллельно с этим продолжается обработка матрицы А аналогично тому, как это было с матрицей С (см. фиг. 5),Далее работа устройства продолжается аналогично. Как видно из таблицы, вывод результатов х обработки матрицы А происходит с 37 по 40-й такт работы устройства, а вывод результатов у обработки матрицы С - с 17 по 20-й такт работы устройства. формула изобретенияУстройство для решения систем линейных алгебраических уравнений, содержащее и/2+1 процессорных элементов (и - четное число), блок синхронизации, о т л и ч а ю щ е е с я тем, что, с целью повышения точности и снижения аппаратурных затрат, выходы -го процессорного элемента с первого по пятый ( = 1, п/2) подключены к входам соответственно с первого по пятый (1+1)-го процессорного элемента, входы первого процессорного элемента с первого по пятый подключены соответственно к выходам с первого по пятый блока синхронизации, вход которого является входом запуска устройства, шестой выход 1-го процессорного элемента ( = 2, и/2) подключен к шестому входу(+1)-го процессорного; элемента, выходы -го процессорного элемента с седьмого по одиннадцатый ( = 3, п/2+1) подключены соответственно к входам с седьмого по одиннадцатый (-1)-го процессорного элемента, первый и второй выходы (и/2+1) процессорного элемента подключены к седьмому и восьмому входам (и/2.1)-го процессорного элемента соответственно, выходы (и/2+1)-го процессорного элемента с четвертого по шестой подключены соответственно к его входам с девятого по одиннадцатый, одиннадцатый выход второго процессорного элемента подключен к шестому входу первого процессорного элемента, шестой выход которого является выходом устройства, вход которого подключен к седьмому входу первого процессорного элемента и к двенадцатым входам остальных процессорных элементов, причем первый процессорный элемент содержит блок деления, выход которого подключен к входу первого блока элементов задержки первого процессорного элемента, а первый вход его соединен с выходом первого регистра первого процессорного элемента, вход которого связан с выходом первого коммутатора первого процессорного элемента и с входом второго регистра первого процессорного элемента, выход которого подключен к первым входам схемы сравнения, первого и второго коммутаторов первого процессорного элемента, вторые входы которых также обьединены и подключены к выходу третьего коммутатора первого процессорного элемента, первый и второй входы которого являются соответст- ВЕННО ШЕСТЫМ И СЕДЬМЫМ ВХОДаМи ПЕРВОГО процессорного элемента, выходы процессорного элемента с первого по третий подключены соответственно к выходам с первого по третий второго блока элементов задержки, входы которого с первого по третий являются соответственно первым, вторым и пятым входами первого процессорного элемента, пятый и четвертый выходы которого подключены соответственно к выходам первого и третьего блока элементов задержки, вход которого связан с управляющими входами первого и второго коммутаторов и с выходом элемента И первого процессорного элемента, первый вход которого подключен к третьему входу первого процессорного элемента, четвертый вход которого подключен к первому входу элемента ИЛИ, второй вход которого соединен с выходом схемы сравнения, выход второго коммутатора подключен к входу четвертого блока элементов задержки, выход которого является шестым выходом первого процессорного элемента и подключен к второму входу блока деления, выход выбора режима которого соединен с управляющим входом первого регистра и является пятым входом первого процессорного эле1829043 17 45 50 55 мента, управляющий вход третьего коммутатора подключен к второму входу первого процессорного элемента, выход элемента ИЛИ соединен с вторым входом элемента И первого процессорного элемента, причем -й процессорный элемент ( = 2, и/2-1) содержит умножитель, первый вход которого подключен к выходу первого регистра 1-го процессорного элемента, вход которого соединен с выходом первого коммутатора и входом второго регистра 1-го процессорного элемента, выход которого подключен к первым информационным входам первого и второго коммутаторов -го процессорного элемента, вторые входы которых объединены и связаны с выходом третьего коммутатора, первый информационный вход которого подключен к выходу четвертого коммутатора, первый и второй информационный входы которого являются соответственно шестым и одиннадцатым входами -го процессорного элемента, входы и выходы которого с первого по третий подключены соответственно к входам и выходам с первого по третий первого блока элементов задержки. второй вход умножителя подключен к выходу пятого коммутатора, первый и второй входы которого являются соответственно пятым и десятым входами -го процессорного элемента и подключены соответственно к входам второго и третьего блоков элементов задержки, выходы которых являются соответственно пятым и десятым выходами -го процессорного элемента, четвертый и девятый выходы -го процессорного элемента подключены к выходам соответственно четвертого и пятого блоков элементов задержки, вход которого является девятым входом 1-го процессорного элемента и подключен к первому информационному входу шестого коммутатора, первый выход которого подключен к управляющим входам первого и второго коммутатора 1-го процессорного элемента, выход которого подключен к вхо ду шестого блока элементов задержки, выход которого соединен с первым входом сумматора, выход которого соединен с шестым и одиннадцатым выходами -го процессорного элемента, седьмой и восьмой 10 выходы 1-го процессорного элемента подключены соответственно к первому и второму выходам седьмого блока элементов задержки, первый и второй входы которого являются соответственно седьмыми и вось мыми входами -го процессорного элемента,четвертый вход которого подключен к входу четвертого блока элементов задержки и к третьему входу шестого коммутатора, второй и четвертый входы которого подключе ны соответственно к восьмому и второмувходам -го процессорного элемента, второй выход шестого коммутатора является управляющим входом третьего коммутатора, второй вход которого подключен к 25 двенадцатому входу 1-го процессорного элемента, управляющий вход четвертого коммутатора подключен к седьмому входу 1-го процессорного элемента и к входу элемента НЕ, выход которого соединен с первым вхо дом элемента ИЛИ, второй вход которогоподключен к первому входу -го процессорного элемента, третий вход -го процессорного элемента соединен с управляющими входами первого регистра и сумматора, уп равляющий вход шестого коммутатораподключен к выходу элемента ИЛИ и к входу восьмого блока элементов задержки, выход которого подключен к управляющему входу пятого коммутатора, выход 40 умножителя подключен к второму входусумматора.