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

(50.4 С 06 Р 15 ИСАНИЕ ИЗОБРЕТЕЙИ У СВИДЕТЕЛЬСТ АВТОР В 26 иотехнический мыкова Р,В,Коробк СССР 1980. ССР 1984. СИСТЕМ ельст ельствР 1 ЯРЕШЕНИЯЕНИЙ осит выч жет быть ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРОЙСТВО ДЛЯАЛГЕБРАИЧЕСКИХ УРАВН(57) Изобретение отнлительной технике и пользовано в специализированных вычислительных устройствах для решениясистем алгебраических уравнений видаАХ+В=О, Целью изобретения являетсяповышение быстродействия устройства.С этой целью устройство содержитматрицу вычислительных элементов,структурно подобную матрице коэффициентов А=1 а . Каждый вычислительный элемент ведет обработку одногоиз неизвестных системы с применениемтабличного метода вычислений с помощью двух блоков постоянной памяти.Вычисления ведутся в избыточной четверичной системе счисления. 1 з.п.ф-лы, 4 ил,1 13240Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах, предназначенных для решения систем алгебраических уравнений вида АХ+В=-О.Целью изобретения является повышение быстродействия устройства.На фиг, 1 показана блок-схема устройства; на Фиг. 2 - функциональная Ю схема вычислительного элемента; на фиг. 3 - временная диаграмма работы устройства; на фиг. 4 - Функциональная схема блока синхронизации.Устройство содержит группу реги стров 1 неизвестного, группу регистров 2 невязки, группу регистров 3 приращений, элемент ИЛИ-НЕ 4, триггер 5, элемент 2 И-ИЛИ 6, Х групп по И вычислительных элементов 7 и блок 20 8 синхронизации, Устройство имеет Ы групп по И входов 9 записи коэффициента, вход 10 запуска, выходы 11 и входы 12 начальных условий.Вычислительный элемент 7 содержит 25 регистр 13, два блока 14 и 15 памяти, шесть элементов 16-21 задержки и сумматор 22 в избыточной четвертичной системе счисления, Вычислительный 7 элемент имеет управляющий вход 30 23, вход 24 записи коэфФициента, два информационных входа 25 и 26 и выход 27. Блок 8 синхронизации содержитгенератор 28 импульсов, счетчик 29разрядов, счетчик 30, дешифратор 31,триггеры 32, элементы И 33 и три элемента ИЛИ 34-36.Блок 8 имеет вход 37 запуска, вход38 задания цикла, три выхода 39-410и группу из Н выходов 42,Устройство работает следующим образом.Пусть необходимо найти решение алгебраической системы уравненийАХ+В=О (1) 36 2огде Р- символ, указывающий, что вкачестве приращения беретсяпервый старший разряд невязки Е е+Как следует из выражения (2), в качестве начального приближения берутся свободные члены, которые заносятся в регистры 2 невязки по входам 12 начальных условийКоэфФициенты матрицы А заносятся в регистры 13 вычислительных элементов 7, причем а,. записывается в 1-й вычислительный эле 1 е мент 7, -й группы. В регистрах 3 приращений первоначально записаны нули. Триггер 5 находится в нулевом состоянии (это взято для определенности, в первом шаге безразлично, в каком состоянии триггер 5), тогда по серии управляющих сигналов с выхода 40 содержимое регистров 3 приращений разряд за разрядом, начиная со старших разрядов, поступает на первые информационные входы 25 вычислительных элементов. Нулевые значения приращений поступают из регистров 3 приращений на вторые информационные входы 26 вычислительных элементов, В вычислительном элементе выполняется операция умножения коэфФициента матрицы А, хранимого в данном элементе, на приращение и сложение произведения с поступающей на вход элемента невязкой, Для произвольного элемента а," можно записать(1-1Так как в первом шаге все лх равны нулю, то 1;=Ь;, т,е, невязка сохраняетзначейие свободного члена,1Рассмотрим процедуру вычисления невязки несколько подробнее, Для определенности выберем невяэку с номером 1, Таким образом старший разряд из первого регистра 3 поступает на первый вычислительный элемент (ВЭ) первой группы, Сюда же поступает при(2) Для реализации в предлагаемом устройстве система представляется в виде ращение дх =-О. Происходит умножениеприращения хо на старший разряд ко эффициента а, хранимого в регистрерассматриваемого ВЭ, Осуществляетсяэто следующим образом. Старший разрядкоэффициента а, который представленв четвертичной избыточной системе 55 счисления, поступает на первый адресный вход первого блока 14 памяти изрегистра 13, На второй адресный входпоступает приращение йх . В блокею14 памяти записана таблица умножения6 , 4тов строк окончательно формируются в виде множества новых невязок 1(Рф 11 ф 7(0+11фв зп(+111Происходит это через 2 п тактов. Здесь возможны два случая 2 п 6 ш и 2 пш, где ш - число разрядов обрабатываемых данных, В каждом случае будет своя диаграмма работы, На фиг. 3 изображена диаграмма работы для случая 2 п уш. В этом случае считывание из регистров невязки заканчивается раньше, чем произойдет обработка невязки в матрице. В связи с этим в синхросерии с выходов 40 и 41 блока 8 управления имеется момент, когда импульсы отсутствуют (пауза), Длина первой паузы определяется величиной (2 п-ш). Первая пауза образуется в случае, когда считывание из регистра невязки завершено, - а запись еще невозможна. Вторая пауза возникает в том случае, когда запись в регистр закончена, а считывание из регистра невязки недопустимо, так как с выходов вычислительных элементов считывается хвост невязки. После окончания умножения необходимо три дополнительных такта для обнуления схемы умножения - такт на первую группу линий задержек, такт на вторую группу и такт на обнуление сумматора 22. Таким образом, минимальная длительность паузы равна такту. Для того, чтобы переходные процессы завершились полностью, вторую паузу расширим до двух тактов. Тогда общее время вычисления невязки будет равным Рассмотрим как формируются приращения неизвестных, Из алгоритма (2) следует, что в качестве приращення берется старший разряд невязки, Старший разряд невязок образуется по второму такту синхросерии на выходах сумматоров 22, последних БЭ групп. Для выделения этого такта подается сигнал с: выхода 39 блока 8 управления. Он совпадает по времени со вторым импульсом со второго выхода группы 42.По этому импульсу происходит запись старших разрядов невязки в регистры приращений и происходит сложение содержимого регистров 1 неизвестного со старшими разрядами невязок. Одновременно результат анализа старших разрядов невяэок на нуль фиксируется в триггере 5, Предположим, что хотя бы один разряд не нуль, тогПоступление старшего разряда частичной невязки на информационный вход указанного ВЭ позволяет начать фор мирование новой частичной невязкн. Разрешение работы второй ячейки осуществляется подачей на управляющий вход вычислительных элементов серии импульсов со второго выхода группы 42. Эта серия подобна серии с перво" го выхода группы 42 и сдвинута на два разряда. Во втором ВЭ первой группы формируется новое значение частичной невязки. Работает ВЭ аналогично описанному. Проходя последовательно через вычислительные элементы строк, частичные невяэки на выходах последних вычислительных элемен 3 132403цифр избыточной четверичной системы счисления. Здесь использованы два вида кодирования: вспомогательное, содержащее следующие цифры 0,1,2, -1,(, и основне кодрани, содержащее шесть цифр 0,1,2,3,-12В качестве примера покажем значение на выходе блока памяти при поступлении максимальных цифр:Первый Второй Старший Младший1 Овход вход разряд разряд О 011 010 001 110 011 111 110 110 110 001 000 010 010 001 000 Здесь использовано двоичное кодирование четверичных- цифр (0-000, 1 - 0.01, 2 - 0,10, 3 - 0.11, -1 1,11, -2 - 1,1(. Таким образом, после перемножения старший разряд поступает на первый адресный вход второго блока 15 памяти, на второй адресный вход которого поступает младший разряд результата предыду 25 щего перемножения, В нашем случае на оба входа поступают нули. На третий вход поступает разряд невязки: В блоке 15 памяти записана таблица сложения 3-х цифр, поступающих на его входы, Результат фбрмируется в виде двух цифр, старшая поступает на сумматор 22 непосредственно, а младшаяс задержкой на один такт. После поступления второго разряда в суммато ре 22 окончательно сформируется первый разряд результата. Таким образом, через два такта старший разряд первой частичной невязки Г ф оказыва 1( 011 ется сформированным, и он поступает 40 на второй ВЭ первой группы. И=2 ш+ (2 п-ш)+2=2 (и+1)+ш.324035 да существует 1 хотя бы на одном проводе, и на выходе элемента ИЛИНЕ 4 будет нуль, Это говорит о том, что итерационный процесс отыскания текущего разряда неизвестных не закончен и должен быть продолжен. В том случае если все старшие разряды невязок равны нулю, на выходе элемента ИЛИ-НЕ 4 будет сигнал, равный 1, Содержимое регистров 1 неизвестного сдвигается в сторону старших раз. рядов, В результате сдвига младший разряд неизвестного и поступающее новое приращение будут иметь один вес. Одновременно триггер 5 устанавливается в единичное состояние и на вход сдвига регистров 2 невязки потупает не ш, а (ш+1) импульс. В реультате в регистры 2 невяэки запнется не ш разрядов, а (ш+1) разряд. 2 О Так как запись ведется, начиная со старших разрядов, то первый старший разряд невязки будет потерян, а второй старший разряд станет первым. В результате этой операции достигается следующее. Все старшие разряды, а они были, как это было показано, нулевыми, будут исключены из анализа. Анализироваться будут теперь разряды невязки, имеющие вес на 1 меньше, но номер такта, в котором они будут анализироваться, сохраняется, анализируемый разряд остается первым, Таким образом, увеличением веса содержимого регистров неизвестного и невязки достигается сохранение без изменения временной диаграммы, хотя и совершился переход на отыскание следующего младшего разряда. Этот процесс повторяется до тех пор, пока не будут определены все ш разрядов, Это определяется подсчетом в устройстве управления числа 1, образующихся на выходе элемента ИЛИ-НЕ 4. т е н и яо р м уо рого подключен к выходу элементаИП 1-НЕ, к информационному входутриггера и к входам сдвига регистровнеизвестного группы, информационныйвход х-го (1=1,11) регистра неизвестного группы подключен к выходу 11-говычислительного элемента 1-й группы,к 1-му входу элемента ИЛИ-НЕ и к информационным входам х-го регистраприращений группы и 1-го регистра невязки группы, выход последнего подключен к первому информационному входу первого вычислительного элемента2.-й группы, вторые информационныевходы ь-х вычислительных элементоввсех групп подключены к выходу -горегистра приращений группы, синхровходы регистров приращений группы ирегистров неизвестного группы подключены к синхровходу триггера и первому выходу блока синхронизации, входыэлемента 2 И-ИЛИ подключены соответственно к прямому выходу триггера,второму и третьему выходам блока синхронизации, и инверсному выходу триггера, выход элемента 2 И-ИЛИ подключен к входам сдвига регистров невязки группы, выход 3-го вычислительногоэлемента Ц=,И) каждой группы подключен к первому входу Я+1)-го вычислительного элемента той же группы,управляющие входы 1-х (=1,И) вычислительных элементов всех групп подключены к (1+3)-му выходу группы блока синхронизации, вход записи коэффициента 1-го вычислительного элемента-м входом записи коэффициента 3 -йгруппы устройства, вход запуска блока синхронизации является входом запуска устройства выходы регистровнеизвестного группы являются соответствующими выходами устройства, установочные входы регистров невязки являются входами начальных условий устройства,авн со ржао 5 ре-НЕ,оонотов си то 1, Устройство алгебраических у щее группу регист группу регистров гистров приращени о т л и ч а ю щ е с целью повышения содержит триггер,групп по Ы вычисл(где Ы - число не числу уравнений в хронизации, входя решения систеь ов неизвестно евяэки, группу и элемент ИЛИ е с я тем, чт быстродействия элемент 2 И-ИЛИ тельных элемен известных, рав системе) и блзадания цикла 2, Устройство по и. 1, о т л и ч а ю щ е е с я тем, что вычислительный элемент содержит регистр, два блока памяти, шесть элементов задержки и сумматор в избыточной четверичной системе счисления, причем синхровход регистра является управляющим входом вычислительного элемента, первый информационный вход регистра является входом записи коэффициента вычислительного элемента, второй информационный вход регистра подключен к его выходу и к первому адресному вхо 132403 бду первого блока памяти, второй адресный вход которого является вторыминформационным входом вычислительногоэлемента, первый информационный вхОдкоторого подключен к первому адресному входу второго блока памяти, второйадресный вход которого подключен кпервому выходу первого блока памяти, разряды третьего адресного входа которого подключены к выходам со Оответственно первого, второго и третьего элементов задержки, входы которых подключены к соответствующимразрядам второго выхода первого бло" ка памяти, первый выход второго блока памяти подключен к входу первогослагаемого сумматора в избыточнойчетверичной. системе счисления, разряды входа второго слагаемого которого подключены к выходам соответственно четвертого, пятого и шестогоэлементов задержки, входы которыхподключены соответственно к разрядамс первого по третий второго выходавторого блока памяти, выход суммысумматора в избыточной двоичной системе счисления является выходом вычислительного элемента.1324036л р ЕХ Дф вСЕ Е/ил ш з1324036 Составитель Н,ЗахаревиТехред И,Попович Парфено Редак орректор ИЛуска 2967/53 Тираж 672 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, Раа Подкомитета ССн открытийушская наб сно4/ Произ твенно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4