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

 

01) 559241

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено08 04 75 (21) 2124287/24 с присоединением заявки № (23) Приоритет (Я1) Я. Кл.о

С1 06 F 15/32

Государственным комитет

Совете Министров СССР по делам изооретений н открытий (43) Опубликовано25.05.77.Бюллетень № 19 (53) ДК 681,325 (088.8) (45) Дата опубликования описания 22.07.77 (72) Авторы изобретения В.Д. Самойлов, A..А. Бальва и Н.Л. Никонова (71) Заявитель Институт электродинамики AH Украинской ССР (54) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ И1ГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

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

Решение системы сводится к понижению по- 10 рядка старшей производной, поступающей на вход первого интегратора. Недостатком из вестных устройств является сложность конструкции.

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

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

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

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

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

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

Блок-схема предлагаемого устройства изображена на чертеже.

Устройство состоит из tn- и блоков 1 формирования коэффициентов, в состав каждого из которых входит регистр 2 коэффициентов, два узла 3 умножения коэффициентов на знак и два элемента 4 И, тл сумматоров 5 строк, н сумматоров 6 стопбцов. четырех элементов И 7 — 10, регистра

11 знака приращений, регистра 12 нэвяэок, коммутатора 13, цифровых интеграторов 14, Предлагаемое устройство работает следующим образом.

Систему линейных алгебраических уравнений вида;

35 и а, -х.=g i где 1 1 —:тп й; — коэффициенты при переменных;

40 х — переменные;

3 можно представить в виде эквивалентной системы уравнений Шеннона.

Решение эквивалентной системы уравнений Шеннона сводится к минимизапии вспо45 могательной функции:

50 где Е1 — величина невяаок

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

Пред на ампом решения вепичипы коэффици.» оптов при переменных заносятся в соответствую шие регистры 2 переменных, начальные значения переменных — в соответствующие цифровые интеграторы 14, знаки начальных значений невязок — в регистр 12 невязок, знаки начальных значений переменных — в регистр 11 знака приращений, а начальные значения невязок Е;, вычисляемые по формулам где индекс в круглых скобках указывает номер шага вычислений, заносятся в каждый из сумматоров 5 строк.

После поступления первого тактового импульса коммутатор 13 через элементы 4 И соединяет со входами узлов 3 те регистры

2 коэффициентов, которые в приведенной ниже таблице пронумерованы цифрами 1.

Таблица очередности коммутации регистров коэффициентов

Количество элементов в таблице равно количеству регистров 2 коэффициентов в устройстве. Каждая ячейка таблицы соответствует регистру, в котором запоминается значение коэффициента „..

Далее на выходе 15 коммутатора 13 появляется управляющий сигнал, по которому выходные сигналы элемента 9, представляющие собой значения знаков невязок, поступают на входы 16 соответствующих элементов 4, которые скоммутированы коммутатором 13. о о

Б сумматорах 6 столбцов, представляющих собой накапливающие сумматоры, формируется величина первого из 1-тых слагаемых вектора градиента минимизируемой функции, равная () (о) тле 1=1-:тп; ) = —: и; (O)

Е - = ъ тч (з тд и (E,- о ) ), где 0

Далее на выходе 17 коммутатора формируется управляющий сигнал, по которому значения знаков начальных значений приращений переменных, занесенные в регисто

11 знака приращений, поступают на входы соответствующих скоммутированных узлов

3 умножения коэффициентов на знак. На выходах скоммутированны х узлов 3 ум но жения формируются произведения величин коэффиципиентов на знак приращений переменных, представляющие собой первое из (-тых слагаемых вектора приращений невязок и равное дЕ =о(.-дХ

i4) j3

Каждая из составляющих вектора приращений невязок поступает на входы соответ10 ствуюших сумматоров 5 строк, где происходит накопление величин невязок. Сумматоры 5 строк представляют собой накапливающие сумматоры.

Далее На коммутатор 1 3 поступает следующий импульс от генератора импульсов.

Коммутатор коммутирует следующую группу регистров 2 коэффициентов ко входам узлов 3 умножения, которые в таблице очередности коммутации регистров коэффициентов пронумерованы цифрами 2, (предыдущая группа регистров отключается). Далее на выходе 15 коммутатора формируется управляющий сигнал и описанный выше цикл работы повторяется, причем в сумматорах 6 25 столбцов будет сформирована сумма двух первых 1-тых слагаемых вектора градиента минимизируемой функции, а в суммато« рах 5 строк будет сформирована, сумма двух первых g-тых слагаемых вектора невязок. З0

После поступления 7) -го тактового им.пульса на вход коммутатора 13 в сумматорах 6 столбцов образуется новое значение вектора градиента минимизируемой функции, а в сумматорах 5 строк — новое значение вектора невязок. Эти вновь полученные значения векторов аналогичны значениям векторов на первом шаге вычислений при параллельной работе модели.

После поступления:и (тактового им 40 пульса на вход коммутатс)а 13, то есть на первом такте второго шага (шаг состоит из т) тактов), на выходе 18 коммутатора формируется управляющий сигнал, по которому в регистр 12 невязок заносится 45 новый вектор знаков невязок. Далее формируется управляющий сигнал на выходе 19 коммутатора 13, по которому в регистр 11 знаков приращений поступает новый вектор приращений переменных, формируемый на 50 выходе элемента 7 И и равный: (1) (<) )(-- q (П .. () 55 уА q а =э1(гтг (гд.тг(ч,и + х», <с, Вектор приращений переменных иоступает на входы цифровых интеграторов 14. Затем на выходах 15 и 17 коммутатора 13 форо0 мируго гя очередные управляющие сигналы.

Таким образом, управляющие сигналы на выходе 18 и 19 коммутатора 13 будут сформированы на каждом тгг(а+ () такте, где т))-целое число, что обеспечивает занесение новых значений вектора знаков н вяэок и вектора приращений переменных в сьответствуюшие регистры 12 и 11 только в начале каждого иэ новых шагов, состоящего иэ 31 Гактои.

Таким образом, на )(-том шаге вычисления работа основных блоков может быть описана следующими математическими зависимостямии: (К) тгг (к-1) ч >и

1) т где 1 = 4-.т -вектор приращений л1ипил изируемой функции, Формируемый в сулгматорах 6

:толбцов; (к) (к- 3) (к)

=х д)(— вектор переменных, формируемый в цифровых интеграторах 14 накопления переменных;

) д (к) вектор неувязок, формируе(к) (к-г) (к) мый в счмматорах 5 строк; (к) (к-() д =э . дх — вектор приращений невязок. формируемый на выходах каждого узла 3 умножения коэффициентов.

Использование в предлагаемом устройстве )г) сумматоров строк и набора vr сумматоров столбцов, представляющих собой накапливающие сумматоры, вместо применяемых ранее многовходовых комбинапионных сумматоров резко сокращает количество требуемого оборудования и упрощает устройство, что дает значительную экономию при его технической реализации и повышает его надежность; это особенно важно при использовании данного устройства в качестве спецпроцессора в составе гибридной вычислительной системы.

Формула изобретения цифровое устройство для решения систем линейных алгебраических уравнений, содержащее та- и блоков формирования коэффициентов, сумматоры, регистры, цифровые интеграторы, о т л и ч а ю щ е е с я тем, что, с целью сокращения оборудования, оно сочержит колглгутатор и элементы И, причем каждый блок формирования коэффициентов содержит регистр коэффициентов, два узла умножения коэффиш.ентов на знак и два элемента И, выход регистра коэффициентов соединен с первыми входами узлов умножения коэффициентов на знак, ко вторым входам которых подключены выходы соответствующих элементов И, ахсллг которых являются входамн блока формирования коэффициентов, 11НИИ1!И Заказ 137 4/101 Тираж 818

Подписное

Филиал ПП!1 "Г1агеит", г. Ужгород, ул. Проектная 4

Э I а выходы узлов умножения коэффициентов на знак являются Выходами блока формироВания коэффициентОВ, лричем Один Выход блока формирования коэффициентов соединен со BxolloM соответствуюш . го сумматора строК, а другой Выход - co входом соответствующего сумматора столбцов, выходы всех сумматоров столбцов подключены к одному входу первого элемента И, пругой вхоп коюрого соединен с первым выходом коммутатора, а выход - со входами, цифровых интеграторов и со входом регистра знака прирашений, выход, которого подключен к первому входу второго элемента И, второй Вход которого соединен со вторым выходом ком- 15 мутатора, а выход — с первыми входами блоков формироования коэффициентов, вторые

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

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

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

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

3. Пухов Г.E. Избранные вопросы теории. математических машин, Иэд-во AH

УССР, Киев, 1969,