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

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

На чертеже дана блок-схема устройства.

Цифровое устройство для решения систем линейных алгебраических уравнений состоит из m блоков 1 умножени на знак, m сумматоров 2 строк сумматора 3 столбца, коммутатора 4, блока 5 упрааления, блока б памяти, содержащего m узлов 7 памяти коэффициентов, узел 8памяти градиента, узел 9 памяти переменных, блока 10 адресации, m блоков 11 хранения невязок, регистра 12 градиента, дешифратора 13,.счетчика 14, элемента И 15.

Устройство работает следующим образом.

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

п

Set

;)1

где i 1 т т;

- коэффициенты при перемен i

ных;

X- - переменные, можнополучить путем минимизации вспомогательной функции

XJ--Slg, ,

- величина невязок.

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

Перед началом решения значения величин коэффициентов при переменных

начальные значения переменных заносятся в соотв.етствующие узлы памяти, а начальные значения невязок (О)

формулам

вычисляе7.1ые по

Л01 1

(01 , а,.

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

После поступления первого тактового иг отульса на соответствующих выходах блока 5 управления появляются управляющие сигналы, разрешающие выборку из блока б памяти первого столбца коэффициентов и первой переменкой х,- и сигналы, блокирующие поступление на блоки 1 сигналов с выхода коммутатора 4, разрешающие прохождение через блоки 1 сигналов с выхода каждого из блоков 11 на вход соответствующих cyivLMaTopOB 2 строк и блокирующие прохождение сигijaJiOB с выходов каждого блока 11 на вход соответств тощего сумглатора строк.

После прохождения сигналами цепочки сумматоров 2, представляющих собой комбинационные cyм iaтopы, на выходде т-го сумматора 2 появляется значенне первой составляющей вектор градиента минимизируемой функции на данном шаге решения, равное

Ь,- .

1 т; 1 - п;

.(от

Lil, ё sig-r, Cf,-va-)

Сигнал другого из выходов т-го Сумматора 2 (выхода знакового разряда) поступает на вход дешифратора 13. На выходе дешифратора 13 формируется значение компонент вектора переме к н ых Д X - - v /i.,, , где v г &i-g-n(5ign(vx. ). Кроме того дешифратор 13 производит сравнение знака градиента минимизируемой функции на данном v.t)., и предыдущем v/J шагах решении, причем сравнение знаков градиентов производится как для отдельных компонент вектора градиента, так: и для всего вектора градиента в целом (значение v ,t поступает на вход дешифратора 13 с выхода знакового разряда регистра 12).

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

В случае, если знаки компоненты вектора V xjи--; и /Jj совпадают, то на одио1 Г1Ш ходе дешифратора 13 формируется сигнал, блокирующий поступление с выхода узла 8 памяти градиента сигнала v/Jj на второй вход сумматора 3, Таким образом на выходе сумматора 3, представляющего собой комбинационный сумматор, образуется значение текущего значения величины

градиента минимизируемой функции, раное значению градиента минимизируемой функции на данном шаге решения, т.е. ,t, -. v..

В случае, если знаки компоненты вектора v/jjn и ,у /Ci, не совпадают, то на входе сумматора 3 блокирующий сигнал отсутствует, и на входе сумматора 3 образуется значение текущего -значения величины градиента минимизируемой фу 1кции, равное

Л ---ч/ - + ,

Таким образом, на выходе сумматора 3 формируется значение первой составляющей текущего значения v j вектора градиента минимизируемой функци которое после поступления от блока 5 разрешающего сигнала на вход регистра 12 переписывается в регистр 12. Знак первой составляющей вектораградиента минимизируемой функции запоминается в дешифраторе 13, а величина вектора градиента по следующему сигналу с выхода блока 5 заносится в узел 8 памяти градиента.

Далее от блока 5 на вход блока 10 и вход коммутатора 4 поступает следующий сигнал с соответствующего выхода блока 5 и из блока б памяти второго столбца коэффициента и второй переменной, и описанный путь прохождения сигналов повторяется.

Подциклы повторяются до тех пор, пока из памяти не будут последователно выданы все столбцы кохффициентов и все переменные.

После окончания j-ro подцикла в дешифраторе 13 образуются все знаки градиента на данном шаге решения и знаки текущего значения градиента.

В случае неравенства всех знаков обоих векторов градиентов описанные ПОДЦИКЛЫ повторяются до тех пор пока не произойдет полное или частичное совпадение их знаков. В случае совпадения знаков всех или части составляющих векторов градиентов на выходах блока 5 формируется последовательность сигналов, которая дает возможность организовать в устройстве процесс образования вектора невязок и вектора переменных следующим, образом.

С соответствующего выхода блока 5 управляющий сигнал поступает на вход всех блоков 1, блокируя прохождение сигнала с выхода знакового разряда соответствующих блоков 11, разрешая прохождение сигналов с выходов блоков 11 невязок на входы соответствующих сум -1аторов 2 и блокируя передачи между cy /lмaтopaми 2 и т-ным сумматором 2 и сумматором 3.

Далее с выходов блока 5 на вход блока б памяти поступает управляющий сигнал и из блока 6 памяти считываются первый столбец коэффициентов и первая переменная. На другой из входов всех 1 ги;.:;тупают сигналы

с выхода ко.1мутатора 4, представляющие собой приращение первой переменной, этот же сигнал приращения переменной д X . поступает на один нз входов элемента И 15.

На выходах каждого из блоков 1 образуются значения приращений.составляющих вектора невязок, равные

-eV-.-C

которые, поступая на входы соответствующих cyMiviaTopOB 2j суммируются с

0 предыдущими значениями составляющих векторов невязок, накопленными в каждом из блоков 11

5

Да.лее от блока 5 поступает управляющий сигнал на вход блока 11 невязок и на вход элемента И 15, разрешающий перепись значения невязок в блок 11 и величины приращения первой переменной дХ в счетчик 14, где образуется величина первой переменной Х/°+ , которая по сигналу соответствующего выхода блока 5 заносится в узел 9.

Описанный подцикл образования ве5личин слагаег.ых невязок, величин невязок и величин переменных повторяется до тех пор, пока в блоках 11 не образуется новое значение величин невязок на данном шаге решения, а в узел 9 памяти переменных не будут занесены новые значения всех переменных на данном шаге решения. На этом первый шаг вычислений заканчивается.

На выходах блока 5 вновь появляsется описанная выше последовательность импульсов и последовательность операций повторяется.

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

,- г -вектор приращения минимизируемой функции, фор5мируемый в сумматоре 3 столбца;

fW. ).

д,(к.) - вектор переменных, формируемый. в счетчике 14;.

50 (.к) (кн) (к) вектор невязок,

формируемый в сумматорах 2 строк;

,

. iK-fl вектор прира1J

щения Невязок, формируемый на выходах каждого из блоков 1 умножения на знак.

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

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

Формула изобретения

Цифровое устройство для решения систем линейных алгебраических уравнений , содержащее ш блоков умножения на знак/ m сумматоров строк, причем первый вход каждого из них соединен с выходом соответствующего блока умнож аия на знак, cy шaтop столбца, когимутатор, вькод которого соединен с первыми входа1УМ всех блоков умножейия на знак, отличающееся. тем, что,, с цельк повышения точности, а введены блок управления, блок памяти, состоящий из m узлов памяти коэффициентов, узла памяти градиента и узла памяти переменных, блок адресации, га блоков хранения невязок, регистр, градиента, дешифратор, счетчик, элемент И,- причем вторые входы каждого блока умножения на знак соединены с первьши выходами га блоков хранения невязок, вторые выходы которых подключены к вторым входам m сумматоров строк, первые выходы каждого ; i-ro из ю сумматоров строк соединены с третьими входами (i+l) сукматора строк, а также с первыми входами m блоков хранения невязок, первьШ выход ш-го cy вvIaтopa строк подключен к первому входусумматора столбца,второ выход - к первому входу дешифратора; первый выход блока управления соединен с первым входом узла памяти переменных, второй выход - с первым входом коммутатора и через блок адресации со входом блока памяти, третий выход - с первым входом регистра градиента, четвертый выход - с первым входом узла памяти градиента, пятый выход - к четвертому входу т-го сумматора строк, шестой выход - к третьим входам (т-1) сумматоров строк и к пятому входу га-го сумматора стро седьмой и восьмой выходы - соответственно к третьим и четвертым входам m блоков умножения на знак, m выходов блока управления соединены соответственно со вто1Ж ми входами m блоков хранения невязок, причем Первый выход из m выходов блока управления подключен к первому входу элемента И, выход коммутатора подключен ко второму входу элемента И, выход которого соединен с первым входом счетчика, выход которого через узел памяти градиента соединен со вторым входом счетчика/ первый и второй выходы регистра градиента подключены соответственно ко вторым входам узла памяти градиента и додифратора, первый- и второй выходы дешифратора соет динены соответственно с вторыми входами коммутатора и сумматора столбца выход узла памяти градиента соединен с третьим входом сумматора столбца, выход которого подключен к второму входу регистра градиента, выходы m узлов памяти коэффициентов соединены соответственно с пятыми входами га блоков умножения на ,знак, вход блока управления является управляющим.входом устройства.

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

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

2.Заявка 2124267/18-24, 08.04.75, по которой принято положительное решение о выдаче авторского свидетельства.