Цифровое устройство для решения систем линейных алгебраических уравнений Советский патент 1977 года по МПК G06F17/12 

1

Изобретение относится к вычислительной технике и может быть использовано в аналого-цифровых вычислительных системах.

Известны устройства для решения систем алгебраических уравнений fl, 2, в которых система алгебраических уравнений решается путем сведения ее к системе дифференциальных уравнений, для чего составляются замкнутые цепочки из цифровых интеграторов. Решение системы сводится к понижению порядка старшей производной, поступаюшей на вход первого интегратора. Недостатком известных устройств является сложность конструкции.

Известно также устройство для решения систем алгебраических уравнений, которое содержит набор ТП тп блоков формирования коэффициентов, сумматор(.1, регистры, цифровые интеграторы З,

В связи с параллельным способом обработки информации операции суммирования произведений приращений переменных на коэффициенты решаемой системы, выполняемые на многовходовых комбинационных сумматорах в комбинационных схемах умножения,

требуют больших затрат оборудования даже для систем уравнений невысокого порядка и сложность устройства увеличивается по мере увеличения порядка решаемой системы

Цель изобретения - сокращение оборудования устройства.

Это достигается введением в устройство коммутатора и элемента И, причем каждый блок формирования коэффициентов содержит регистр коэффициентов, два узла умножения коэффициентов на знак и два элемента И, выход регистра коэффициентов соединен с первыми входами узлов умножения коэффициентов на знак, ко вторым входам которых подключены выходы соотвегсгвуюших элементов И, входы которых являются входами блока формирования коэ4)фициентов, а выходы узлов умножения коэффициентов на знак. являются выходами блока формирювания коэффициентов, причем одинвыход блока формирования коэффициентов соединен со входом соответствующего сумматора строк, а другой выход - со входом соответствующего сумматора столбцов, выходы всех сумматоров столбцов подключены к одному входу первого элемента И, другой вход которого соединен с первым выходом коммутатора, а выход - со входами цифровых ин.теграто- ров и со входом регистра знака приращений Выход которого подключен к первому входу второго элемента И, второй вход которого соединен со вторым выходом коммутатора, а выход - с первыми входами блоков фор. мирования коэффициентов, вторые входы которых подключены к выходу третьего элемента И, соединенного первым входом с третьим выходом коммутатора, а вторым входом - с выходом регистра невязок, ко входу которого подключен выход четвертого элемента И, первый вход которого соеди йен с четвертым выходом коммутаторе а второй - с выходами сумматоров строк, тр тьи и четвертые входы блоков формирования соединены с соответствующими выходами коммутатора. Блок-схема предлагаемого устройства изображена на чертеже. Устройство состоит из тл- тг блоков 1 формирования коэффициентов, в состав каждого из которых входит регистр 2 коэффициентов, два узла 3 умножения коэффициентов на знак и два элемента 4 И, 1И сумматоров 5 строк, м сумматоров 6 столбцов четырех элементов И 7 - 1О, регистра И знака гфиращений, регистра 12 нэвяаок коммутатора 13, цифровых интеграторов 1 Предлагаемое устройство работает следующим образом. Систему линейных алгебраических уравнений вида: п S«,j.где 1 1 -т- тп а - коэффициенты при переменных; X - переменные; можно представить в виде эквивалентной системы уравнений Шеннона. Решение эквивалентной системы уравне ний Шеннона сводится к минимизации вспо могательной функции: .. где i величина невязок. Значения переменных, обеспечивающие минимум этой функции, будут являться решением системы. Пред начапом решения вепичипы коэффициентов при 11еременнь хзаносятсявсоответств шие регистры 2 переменных, начальные зн чения переменных - в соответствующие ци ровые интеграторы 14, знаки начальных значений невязок - в регистр 12 невязок, наки начальных значений переменных - в егистр 11 знака приращений, а начальные начения невязок f |° , вычисляемые по ормулам де индекс в круглых скобках указывает ноер шага вычислений, заносятся в каждый а сумматоров 5 строк. После поступления первого тактового импульса коммутатор 13 через элементы 4 И соединяет со входами узлов 3 те регистры 2 коэффициентов, которые в приведенной ниже таблице пронумерованы цифрами 1. Таблица очередности коммутации регистров коэффициен ов Количество элементов в таблице равно количеству регистров 2 коэффициентов в устройстве. Каждая ячейка таблицы соответствует регистру, в котором запоминается значение коэффициента . Далее на выходе 15 коммутатора 13 появляется управляющий сигнал, по которому выходные сигналы элемента 9, представляющие собой значения знаков неЬязок,поступают на входы le соответствующих элементов 4, которые скоммутированы коммутатором 13. , В сумматорах 6 столбцов, представляющих собой накапливающие сумматоры, формируется величина перво1Х из i -тых слагаемых вектора градиента минимизируемой функции, равная -°п j-л- -пг е 1 1 -гтп е - «.ig-TiCstg-Ti (егде О 0( 4 1 , индекс в нижних круглых скобках указывает номер слагаемого, а в верхних - номер шага вьиислений. Далее на выходе 17 коммутатора формируется управляющий сигнал, по которому значения знаков начальных значений приращений переменных, занесенные в регистр 11 знака приращений, поступают на входы соответствующих скоммутировакных узлов 3 умножения коэффициентов на знак. На выходах скоммутированных узлов 3 умножения формируются произведения величин коэффиц циентов на знак прирашений переменных, представляющие собой первое из -тых слагаемых вектора приращений невязок и оавное , Каждая из составляющих вектора приращений невязок поступает на входы соответствующих сумматоров 5 строк, где происходит накопление величин невязок. Суммато ры 5 строк представляют собой накапливающие сумматоры. Далее на коммутатор 13 поступает следующий импульс от генератора импульсов. Коммутатор коммутирует следующую гру пу регистров 2 коэффициентов ко входам узлов 3 умножения, которые в таблице очередности коммутации регистров коэффициентов пронумерованы цифрами 2 (предьщущая группа регистров отключается). Далее на выходе 15 коммутатора формируется управляющий сигнал и описанный выше цикл работы повторяется, причем в сумматорах 6 столбцов будет сформирована сумма двух первых i -тых слагаемых вектора градиента минимизируемой функции, а в сумматорах 5 строк будет сформирована; сумма дву первых j-тых слагаемых вектора невязок, После поступления Л -го тактового имдульса на вход коммутатора 13 в суммато- рах 6 столбцов образуется новое значение вектора градиента минимизируемой функции, а в сумматорах 5 строк - новое значение вектора невязок. Эти вновь полученные значения векторов аналогичны значениям векторов на первом шаге вычислений при параллельной работе модели. После поступления тактового им- пульса на вход коммутатора 13, то есть на первом такте второго щага (шаг состоит из т1 тактов), на выходе 18 коммутатора формиоуется управляющий сигнал, по которому в регистр 12 невязок заносится новый вектор знаков невязок. Далее формируется управляющий сигнал на выходе 19 коммутатора 13, по которому в регистр 11 знаков приращений поступает новый вектор приращений переменных, формируемый на выходе элемента 7 И и равный: (f)(О Д - , где (ig-Ti(7/4 ($. Вектор приращений переменных поступает на входы Ц11фровых интеграторов 14. Затем ка выходах 15 и 17 коммутатора 13 формируются очередные управляющие сигналы. Таким образом, управляющие сигналы на выходе 18 и 19 коммутатора 13 будут сформированы на каждом тп(-п ) такте, где тп-целое число, что обеспечивает занесение новых значений вектора знаков невязок и вектора приращений переменных в сйответствующие регистры 12 и 11 только в начале каждого из новых шагов, состоящего из Л тактов. Таким образом , на К-том щаге вычисления работа основных блоков может быть описана следующими математическими зависимостями: (к) Д.. (к-1 Я -- .Т где п-вектор приращений миникшаируемой функции, формируемый в сумматорах в столбцов; х tux вектор переменных, формируемый в цифровых интеграторах 14 накоппения переменных; g(Kl.g,(K-i)gCK) вектор не-зязок, формируемый в сумматорах 5 строк; -вектор приращений невязок. формируемый на выходах каждого узла 3 умножения коэффициентов. Использование в предлагаемом устройстве fn сумматоров строк и набора vt сумматоров столбцов, представляющих собой накапливалощие сумматоры, вместо применяемых ранее многовходовых комбинационных сумматоров резко сокращает количество требуемого оборудования и упрощает устройство, что дает значительную экономию при его-технической реализации н повыщает его надежность; это особенно важно при использовании данного устройства в качестве спецпроцессора в составе г 1бр1шной вычислительной системы. Формула изо бр е т е н и я Цифровое устройство для решения систем линейных алгебраических уравнений, содержащее тп- п блоков формирования коэффициентов, сумматоры, регистры, цифровые интеграторы, о т л и ч а ю щ е е с я тем, что, с целью сокращения оборудования, оно содержиткоммутатор и элементы И, причем каждый блок формирования коэффициентов содержит регистр коэффипнентов, два узла умножения коэффиц.ентов на знак и два элемента И, выход регистра коэффициентов соед1шен с первыми входами узлов умножения коэффициентов на знак, ко вторым входам которых подключены выходы соответствующих элементов II, входы которых являются входами блока формирования коэффициентов.

7

a выходы узлов умножения коэ;)фиииентоа на знак являются выходами блока формирования коэффициентов, причем одни выход блока формирования коэффициентов соединен со входом соответ :;твующл1Х) сумматора строк, а другой пыхоа - со входом cooTEseTствующего сумматора столбцов, выходы всех сумматоров столбцов подключены к одному входу первого элемента И, дру1Х1Й вход когорого соединен с первым выходом коммутатора, а выход - со входами, цифровых интеграторов и со входом регистра знака приращений, ВЫХОД которого подключен к первому входу BTOpoiX) элемента И, второй вход которого соединен со вторым выходом коммутатора, а выход с первыми входами блоков фор.мироования коэффициентов, вторые входы которых подключены к выходу третьего элемента И, соединенного первым входом с третьим выходом коммутатора, а вто8

рым входом - с выходом регистра повязок, ко входу которого подключен выход четвертого элемента И, первый вход которогхэ соединен с четвертым выходом коммутатора, а второй - с выходами сумматоров строк, третьи и четвертые входы блоков формирования соединены с соответствующими выходами коммутатора.

Источники информации, принятые во внимание при экспертизе изобретения:

1.Неслуховский Н.С. Цифровые дифференциальные анализаторы , Изд-во Машиностроение, М., 1968.

2.Папернов А.А. Логические основы цифровых машин и программирования , Издво Наука, М., 1968.

3.Пухов Г.Е. Избранные вопросы теории математических машин , Изд-во АН УССР, Киев, 1969.