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

(51) М, КлС; 06 32 присоединением заявкиасудврственный камитеСовета Министров СССРпо делам изобретенийн открытий 23) Приоритет43) Опубликовано 25.05.77.Бюллетень145) Дата опубликования описания 22.07.7 53) УДК 681 82.Д. Самойлов, А,А, Бальва и Н.Л. Никонов нститут электродинамики АН Украинской ССР аявите 4) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ Изобретение относится к вычислительной технике и может быть использовано в аналого-цифровых вычислительных системах.Известны устройства для решения систем алгебраических уравнений 11, 21, в которых система алгебраических уравнений решается путем сведения ее к системе дифференциальных уравнений, для чего составляются замкнутые цепочки из цифровых интеграторов.Решение системы сводится к понижению по рядка старшей производной, поступающей на вход первого интегратора. Недостатком известных устройств является сложность конструкции.Известно также устройство для решения 15 систем алгебраических уравнений, которое содержит набор тп т 1 блоков формирования коэффициентов, сумматоры, регистры, цифровые интеграторы 31.В связи с параллельным способом обра ботки информации операции суммирования произведений приращений переменных на коэффициенты решаемой системы, выполняемые на многовходовых комбинационных сумматорах в комбинационных схемах умножения, 25 требуют больших затрат оборудования даже для систем уравнений невысокого порядка и сложность устройства увеличивается по мере увеличения порядка решаемой системы,Цепь изобретения - сокращение оборудования устройства.Это достигается введением в устройство коммутатора и элемента И, причем каждый блок формирования коэффициентов содержит регистр коэффициентов, два узла умножения коэффициентов на знак и два элемента И, выход регистра коэффициентов соедийен с первыми входами узлов умножения коэффициентов на знак, ко вторым входам которых подключены выходы соответствующих элементов И, входы которых являются входами блока формирования коэффициентов, а выходы узлов умножения коэффициентов на знак являются выходами блока формирования коэффициентов, причем одиьвыход блоке ,юрмирования коэффициентов соединен со входом соответствующего сумматора строк, а другой выход - со входом соответствующего сумматора столбцов, выходы всех сумматоров столбцов подключены к одному входу559241 первого элемента И другой вход которогосоединен с первым выходом коммутатора,а выход - со входами цифровых интегратсьров и со входом регистра знака приращений,выход которого подключен к первому входувторого элемента И, второй вход которогосоединен со вторым выходом коммутатора,а выход - с первыми входами блоков формирования коэффициентов, вторые входы которых подключены к выходу третьего эле Омента И, соединенного первым входом стретьим выходом коммутатора, а вторымвходом - с выходом регистра невязок, ковходу которого подключен выход четвертого элемента И, первый вход которого соединен с четвертым выходом коммутатора авторой - с выходами сумматоров строк, третьи и четвертые входы блоков формирования соединены с соответствующими выходами коммутатора,20Блок-схема предлагаемого устройстваизображена на чертеже.Устройство состоит из 1 п и блоков 1формирования коэффициентов, в состав каждого из которых входит регистр 2 коэффициентов, два узла 3 умножения коэффициентов на знак и два элемента 4 И, 111 сумматоров 5 строк, н сумматоров 6 стопбцов.четырех элементов И 7 - 10, регистра1 1 знака приращений, регистра 12 нэвяэок,коммутатора 13, цифровых интеграторов 14,Предлагаемое устройство работает следующим образом.Систему линейных алге знаки начальных значений переменных - врегистр 11 знака приращений, а начальныезначения невязок Е, вычисляемые поформулам5 браических уравнений вида; Х.;о, х.:1 ГДЕ1 +11 переменных свивалентно истемы урав имизации вс 51 Я"И (=Е 1 Е 11 а- коэффициенты прих - переменные;3ожно представить в видеистемы уравнений ШеннонРешение эквивалентнойий Шеннона сводится к миогательной функции: где 8, - величина невяаокЗначения переменных, обеспечивающие минимум этой функции, будут являться решением системы.пред на сапом решения вепичипы коэффици оптов при переменных заносятся в соответствую щие регистры 2 переменных, начальные значении переменных - в соответствующие цифровые интеграторы 14, знаки начальных значений невязок - в регистр 12 невязок,где индекс в круглых скобках указывает номер шага вычислений, заносятся в каждый из сумматоров 5 строк,После поступления первого тактового импульса коммутатор 13 через элементы 4 И соединяет со входами узлов 3 те регистры 2 коэффициентов, которые в приведенной ниже таблице пронумерованы цифрами 1.Таблица очередности коммутациирегистров коэффициент ов Количество элементов в таблице равно количеству регистров 2 коэффициентов в устройстве, Каждая ячейка таблицы соответствует регистру, в котором запоминается значение коэффициента аДалее на выходе 15 коммутатора 13 появляется управляющий сигнал, по которому выходные сигналы элемента 9, представляющие собой значения знаков невязок поступают на входы 1 о соответствующих элементов 4, которые скоммутированы коммутатором 13.ооВ сумматорах 6 столбцов, представляющих собой накапливающие сумматоры, формируется величина перв.го из 1-тых слагаемых вектора градиента минимизируемой функции, равная д,О =а Е(тле 1=1-;тп; 1= 1 - : и; где 00индекс в нижних круглых скобках указывает номер слагаемого, а в верхних - номер шага вычислений,Далее на выходе 17 коммутатора форми руется управляющий сигнал, по которому значения знаков начальных значений приращений переменных, занесенные в регисто 11 знака приращений, поступают на входы соответствующих скоммутированных узлов 3 умножения коэффициентов на знак. На вы ходах скоммутированных узлов 3 умноженияформируются произведения величин коэффиципиентов на знак приращений переменных, представляющие собой первое из -тых слагаемых вектора приращений невязок и оввноеЬЕ =0 . дХКаждая из составляющих вектора приращений невязок поступает на входы соответ 10ствуюших сумматоров 5 строк, где происходит накопление величин невязок. Сумматоры 5 строк представляют собой накапливающие сумматоры,Далее на коммутатор 13 поступает следующий импульс от генератора импульсов.Коммутатор коммутирует следующую группу регистров 2 коэффициентов ко входамузлов 3 умножения, которые в таблице очередности коммутации регистров коэффициентов пронумерованы цифрами 2, (предыдущаягруппа регистров отключается). Далее навыходе 15 коммутатора формируется управляющий сигнал и описанный выше цикл работы повторяется, причем в сумматорах 6 25столбцов будет сформирована сумма двухпервых 1-тых слагаемых вектора градиента минимизируемой функции, а в сумматорвх 5 строк будет сформирована, сумма двухпервых -тых слагаемых вектора невязок.После поступления т) -го тактового импульса нв вход коммутатора 13 в сумматорах 6 столбцов образуется новое значениевектора градиента минимизируемой функции,в в сумматорах 5 строк - новое значениевектора невязок. Эти вновь полученные значения векторов аналогичны значениям векторов нв первом шаге вычислений при параллельной работе модели,После поступления :и+1 тактового им40пульса нв вход коммутвтс)а 13, то естьнв первом такте второго шага (шаг состоит из т) тактов), на выходе 18 коммутатора формиоуется управляющий сигнал, покоторому в регистр 12 невязок заносится 45новый вектор знаков невязок. Далее формируется управляющий сигнал нв выходе 19коммутатора 13, по которому в регистр 11знаков приращений поступает новый векторприращений переменных, формируемый на 50выходе элемента 7 И и равный:(П, .55 УДЕ Яа:в 1 ( 1 д(др +с 4,Вектор приращений переменных иоступвет нв входы цифровых интеграторов 14. Затем нв выходвх 15 и 17 коммутатора 13 форо 0 мируютс я очередные упрдвляюшие сигналы. Таким образом, упрввляющие сигналына выходе 18 и 19 коммутатора 13 будут сформированы на каждом тп(а+1) такте, где е-целое число, что обеспечивает занесение новых значений вектора знаков нвяэок и вектора приращений переменных в сьответствуюшие регистры 12 и 11 только в начале каждого иэ новых шагов, состоящего иэ и тактои,Таким образом, на К-том шаге вычисления работа основных блоков может быть описана следующими математическими зависимостями:(к) Ос-Оья . =а, ьх -вектор приращений невязок,формируемый на выходах каждого узла 3умножения коэффициентов,Использование в предлагаемом устройствесумматоров строк и набора т сумматоровстолбцов, представляющих собой накапливающие сумматоры, вместо применяемых ранеемноговходовых комбинационных сумматороврезко сокращает количество требуемогооборудования и упрощает устройство, чтодает значительную экономию при его технической реализации и повышает его надежность; это особенно важно при использовании данного устройства в качестве спецпроцессорв в составе гибридной вычислительнойсистемы,Ф о р м у л а и з о бр е т е н и яцифровое устройство для решения систем линейных алгебраических уравнений, содержащее та п блоков формирования коэффициентов, сумматоры, регистры, цифровые интеграторы, о т л и ч а ю щ е е с я тем, что, с целью сокрашения оборудования, оно сочержит колмутатор и элементы И, причем каждый блок формирования коэффициентов содержит регистр коэффициентов, двв узла умножения коэффиц.ентов нв знак и двв элемента И, выход регистра коэффициентов соединен с первыми входами узлов умножения коэффициентов на знак, ко вторым входам которых подключены выходы соответствуюших элементов И, охслл 1 которых являются входами блока Формирования коэффициентов,. Проектная, 4 в выходы узлов умножения коэффициетов на знак являются выходами блока формирования коэффициентов, причем одн выход блока формирования коэффициентов соединен со входом соответствуюшего сумматора строК, в другой выход - со входом соответствующего сумматора столбцов, выходы всех сумматоров столбцов подключены к одному входу первого элемента И, другой вход коюрого соединен с первым выходом комму татора, в выход - со входами цифровых интеграторов и со входом регистра знака приращений, выход, которого подключен к первому входу второго элемента И, второй вход которого соединен со вторым выходом ком мутатора, а выход - с первыми входами блоков формироования коэффициентов, вторые4входы которых подключены к выходу третьего элемента И, соединенного первым входом с третьим выходом коммутаторв, а вто. 20 ргим входом - с выходом регистра повязок, ко входу которого подключен выход четвертого элемента И, первый вход которого соединен с четвертым выходом коммутатора, а второй - с выходами сумматоров строк, третьи и четвертые входы блоков формирования соединены с соответствующими выходами коммутатора. Источники информации, принятые во внимание при экспертизе изобретения;1. Неслуховский Н,С, 11 ифровые дифференциальные анализаторы, Иэд-во "Машиностроение", М 1968.2. Пвпернов А.А. Логические основы цифровых машин и программирования, Издво "Наука", М., 1968.3. Пухов Г.Е. Избранные вопросы теории математических машин, Иэд-во АН УССР, Киев, 1969,