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

О П И С А Н И Е966702ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик(22)Закалено 12.01,81 (2) 3272882/18-2 Цс присоелинением заявки М(51)М. Кл. 6 06 Г 15/32 Ьеударстмииый комитет СССР ао делам иаабретеиий и атирытийДщтнд ,Институт электродинамики АН Ук конструкторское бюро ИнститутаАН Украинской ССР инской ССеталлофизиИЗ(5 Й) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЫ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙяИзобретение относится к вычислительной технике, в частности к специализированным цифровым вычислительнымустройствам для решения систем алгебраических уравнений и задач линейно 5го программирования . Оно может бытьиспользовано как автономно, так и всоставе цифровых и аналого-цифровыхвычислительных комплексов.Известно цифровое устройство длярешения систем алгебраических уравнений,Известное устройство характеризуется тем, что содержит блоки формирования коэффициентов, сумматоры, регистры, цифровые интеграторы, коммутатори элементы И 1 1.Недостатками этого устройства явлются низкие скорости обработки информации, большое количество оборудова ония и низкая технологичность,Наиболее близким к предлагаемомуявляется цифровое устройство для решенин систем алгебраических уравнений,Это устройство характеризуется течто содержит блок уравновешивания,блок синхронизации, блок ввода-выво"да, блок индикации и (и+2 ) вычислительных блоков, каждый из которых состоит из арифметико-логического узла,группы регистров и формирователя адресов ( где м - число уравнений решаемой системы алгебраических уравнений).ЮВ устройстве формирование вектора,(1("1 производится суммированием арифметико-логическими узлами коэффициентов исходной матрицы, умноженных назнаки невязок и извлеченных из группрегистров, а результаты суммированиявыдаются на выход вычислительных блоков за один такт. Выбор коэффициентовиз групп регистров осушествляется формирователем адресов, В устройстветакже осуцествляется покомпонентноевычисление вектора переменных2.1ь А. ЧеканРейвес рректор С. ИекмардписноеР о комитета СС й и открытий шская наб,П ктная,ул Составител Редактор Л, Авраменко Техре 8 И. Заказ 7816/67 Тираж 731 ВНИИПИ Государственног по делам изобретени 113035 Москва Ж-Я Ра Филиал ППП "Патент", г. УжгНедостатком устройства является ограниценный класс задач, решаемых. устройством, в частности отсутствует возможность решения задач линейного программирования. 5Цель изобретения - расширение Функциональных возможностей данного устройства путем решения задач линейного программирования.Поставленная цель достигается тем, 10 что устройство для решения системы алгебраицеских уравнений, содержащее блок ввода-вывода, блок синхронизации, блок уравновешивания и(1 ъ+2) вычислительных блоков (где и - число 15 уравнений),причем управляющий вход блока ввода-вывода соединен си 1-4)-м входом блока уравновешивания, выход синхронизации блока ввода-вывода соединен с входом блока синхронизации, выход которого соединен со входом синхронизации блока уравновешивания, информационный выход блока ввода-.вывода соединен с инФормационным входом первого вычислительного блока, первый 25 выход - го (где= 1,2и +3) вычислительного блока соединен с информационным входом (+1)-го вычислительного блока, второй выход 1-го вычислительного блока соединен с 1-м инФормационным входом блока уравновешиванил, 1-й выход которого соединен с управляющим входом 1-го вычислительного блока, дополнительно введен (щ+3) вычислительный блок, причем ин 35 формационный вход этого блока подключен к первому выходу (я+2)-го вычисли. о тельного блока, управляющий вход данного блока соединен с (в+3)-м выходом блока уравновешиванил, первый выход40 (п+3) - го вычислительного блока соединен с информационным входом блока вво" да-вывода, второй выход которого соединен,с (в+3)-м входом блока уравновешивания,Кроме того, (и+3) вычислительныйблок содержит ариФметико-логическийузел, группу регистров данных, регистр адресов и счетчик адреса, при"чем первый информационный вход арифметико-логического узла является информационным входом блока, второй информационный вход этого узла соединен с выходом группы регистров данных,который является также вторым выходом 55блока, выход сцетчика адресов соеди"нен с входом регистра адресов, выходкоторого соединен с инФормационным входом группы регистров данных, выход арифметико-логического узла является первым выходом блока, вход счетчика адресов, управляющие входы арифметико-логического узла и группы регистров данных подключены к управляющему входу блока.На фиг. 1 представлена блок-схема цифрового вычислительного устройства; на фиг. 2 - блок-схема блока вво да-вывода; на Фиг. 3 - блок-схема одного из микроавтоматов блока уравновешивания; на Фиг. 4 - блок-схема арифметико-логического узла.Устройство, предназначенное для решения систем алгебраических уравнений и задач линейного программирова" ния, содер 1 нит блок ввода-вывода 1, блок индикации 2, блок синхронизации 3, блок уравновешивания 4, (пн.3) вычис-. лительных блоков 5, причем кандый из (в+3)-х вычислительных блоков 5 содержит арийметико-логический узел 6, группу регистров 7 и Формирователь адресов 8, а (и 1+3)-ый вычислительный блок 5, кроме арифметико-логического узла 6 и группы регистров 7 данных, содержит счетчик 9 и регистр адресов 10 (везде на чертежах цифрами в скобках обозначены порядковые номера одинаковых по техническому выполнению блоков) . Вычислительные блоки 5 соединены последовательно, причем первый вход первого вычислительного бло" ка 5 соединен с первым выходом блока ввода-вывода 1, а первый выход(и+3) вычислительного блока 5 с вторым входом блока ввода-вывода 1. Второй выход блока ввода-вывода 1 соединен с входами блока индикации 2, а третий выход - с входом блока синхронизации 3, выход которого соединен с соответствующим входом блока уравновешивания 4, а(В+4 ) выход блока уравновешивания 4 соединен с первым входом блока ввода-вывода 1. Группы (в+3 ) вторых выходов блока ура вно вешивания 4 соединены с вторыми входами (управления) вычислительных блоков 5, а группа (ю+3 ) входов - с вторыми выходами (условий) вычислительных блоков 5. Первые входы и выходы вь 1 числительных блоков 5 являются входами и выходами арифметико-логических узлов 6 соответственно, выходы условий - вторыми выходами групп регистров 7, первые входы-выходы которых соединены с первыми входами-выходами узла арифметико-логических ус02 5 9667 ловий 6. В вычислительных блоках 5 с номерами от 1-го до(+)-го вторые входы (управления)являются входами регистров адресов 8, первые выходы которых соединены с входами управления 5 арифметико-логических узлов 6 и вхо.дами адресов групп регистров 7. В вычислительном блоке 5 с номером (р+3 ) .счетчик 9 и регистр адресов 10 соедине ны последовательно, выход регистра ад 10 ресов 10 соединен с входом адреса группы регистров 7, а вход управле.ния (,и+3)-го вычислительного блока 5 является входом управления арифметико-.логического узла 6, входом сцетци ка 9 и входом управления группы регистров 7.Блок ввода-вывода 1 представляет собой интерфейс ввода-вывода, состоящий из подканалов ручного и автоматического ввода-вывода информации, и предназначен для ввода информации и команд, вывода информации, а также для организации обмена информацией и командами при неавтономном системном использовании предлагаемого устройства. Пример одного из возможных вариантов выполнения блока ввода-вывода 1 приведен на фиг, 2, Он содержит клавиатуру 11, преобразователь 30 десятицного кода в двоичный 12 мультиплексоры 13 и 14,. узел управления 15, генератор синхро-импульсов 16, входной регистр 17, память 18, узел регистров 19, выходной регистр 20, ком- З 5 мутатор 21, преобразователь двоичного кода в двоично-десятичный 22 и мультиплексор 23. Блок индикации 2 представляет собой устройство отображения алфавитно" цифровой информации и может быть выФполнен в виде экранного пульта с кла" виатурой 13 по любой из известных схем.Блок синхронизации 3 представляет собой устройство организации серий адресных и управляющих синхро-импульсов и может быть выполнен в виде Формирователя импульсных сигналов по любой из известных схем.Арифметика"логические узлы 6 предназначены для выполнения арифметических и логических операций и могут быть выполнены по любой из известных схем. Пример выполнения арифметико-логического узла 6 приведен на Фиг, 4. Он содержит сумматор 34, регистры 35-38, мультиплексоры 39 и 40. Сумматор 34 выполняет арифметицеские операции, Регистр 38 служит буфером для совмещения выборки из группы регистров 7 нового операнда с выполнением в арифметико-логицеском узле текущей операции. В регистрах 36 и 37 хранятся операнды текущей операции, а в регистре 35 хра-, нятся операнды результатов, Мультиплексор 39 служит для подключения на вход сумматора 34 или выходную шину 41 регистров 35 36 и 37. Мультиплек сор 40 служит для.подключения регистров 35 и 36 к входам группы регистров 7. Входы регистров 35, 36 и 37. соединены с входной шиной 42. К шине 42 подключен также выход сумматора 34. Связь арифметико-логического узла 6 с группой регист Блок уравновешивания представляет собой управляющий автомат для задания порядка выполнения всех подпрограмм вычислительными блоками 5. Он состоит из Онмикроавтоматов, Каждый вычислительный блок 5 управляется своим микроавтоматом. Пример-схема одного из микроавтоматов " показан на фиг. 3. Такой микроавтомат состоит из узла логических условий 24, элемента И 25, памяти 26, дешифратора 27, счетчика 28, элемента ИЛИ 29, коммутато 50 ров 30 и 31, схемы сравнения 32 и элемента И 33. В память 26 в определенном порядке записаны подпрограммы операций, выполняемые вычислительными блоками 5. Узел логических условий 24 55 осуществляет анализ результатов операций, выполняемых вычислительными блоками 5. ров 7 осуществляется по шинам 43 и44. Узел управления 15 представляет собой управляющий автомат и может бытьвыполнен по любой из известных схем.Узел логических.условий 24 и схе"ма сравнения 32 представляют собойсхемы сравнения значений двух слов наравенство.Заявляемое цифровое вычислительноеустройство решает системы алгебраического уравненияА Х = В 1где А - матрица коэффициентов а";В - вектор правых частей Ь,М - вектоу переменных )(, 1 = 1,щ,1= 1 п;и - число уравнений (строк А);и - число переменных (столбцовА),702 10тельных блоках 5 из групп регистров 7 в арифметико-логические узлы бпередается коэффициенты а., где выполняется процедура умножения а на1 Х(к, которая осуществляется путеммногократного суммирования коэйфици"ентов . Величины приращении Ь Х(к)равные шагу приращения Ь , и знакиприращений Ь Х 1, противоположныезнакам элементов вектора градиента ; Чр", устанавливаются в блоке уравновешивания 4, Полуценное произведениепо команде блока уравновешивания 4переводится в группы регистров 7. Затем передается следующие коэффициентыа из гругп регистров 7 в арифметикологические узлы 6, в которых выполняется умнонение этих коэффициентов наприращения Ь Хи полученные произедения а ф Х (1 суммируются с предыщими а 6 ХЮ . Завершение вычисленияприращения вектора невязки ь 1(к анализируется блоком уравновешивания 4,который переводит устройство для решения новых значений вектора переменных Х ( и невязки(к-) предыдущих значений векторов Х ис приращениями Ь Х(" и ьбф т.е. 20 9. 966по команде блока уравновешивания 4значения переменных Х(переводятся из-тых в (1+1)-ые выцислительные блоки 5, а из групп регистров 7 в арифметико-логические узль 1 6 значения сле дующих коэффициентов а и процедура2умножения повторяется, Результатыумножения суммируются с величиной Ь,и заносятся в группы регистров 7. Вычисление вектора ( завершается за- Онесением в группы регистров 7 значений 6(, а значения Функций Боп 6(1 в блок уравновешивания 4. Затем блокуравновешивания 4 переводит устройство для вычисления начал ьных значений5вектора градиента, элемент котороговычисляется по Формуле(о)чф = а Бпп( 1 =-1 игде уп (7 =-1 приО,0 приОВычисление элементов нацальногозначения вектора градиента осуществляется в ю-х вычислительных блоках 5По команде блока уравновешивания 425значения коэффициентов асо знаком,соот ветст вующим е го знаку, умноженному на знак Функции Бпп Ф,поступаютиз группы регистров 7 в арифметикологические узлы 6, где происходитсуммирование со значениями коэффициентов а, поступающими на их входы.Данная процедура завершается по ко"манде блока уравновешивания 4 занесением значений элементов нацального 35вектора градиента в группу регистров 7 (и+1)-го вычислительного блока 5 и значений Функций Ьу Ч,О вблок уравновешивания 4, где функцияИ Ч,О =ЧЦО - ЮОир дБлок уравновешивания 4 фиксирует завершение вычисления начальных значений ЧОФ и переводит устройство вподре 4 м итерационного решения.Итерационный процесс решения начинается с вычисления приращения невязки по формуле(с)ХОс) ( иде дХ = "В" БуЧР,=1,п " рращения -того элемента вектора переменных на к-том шаге итерационногопроцесса; Ф- шаг приращения 1-тогоэлемента вектора переменных. 55По команде блока ввода-вывода 1,блока синхронизации 3 и блока уравно,вешивания 4 в1+и)-том вычисли",;+ 1- 1,еВычисление новых значений векторов выполняется в (1+и) -их вычислительных блоках 5, а вектора - в (в+2)-м выцислительном блоке 5 параллельно. После выполнения данных вычислений, значения элементов 1 1 заносятся вКгруппы регистров 7 (1 +г)-го вычислительных блоков 5 значения Х 1 - в3 группу регистров 7 (гн 2) - го вычислительного. блока 5, а значения йункций Бдпв блок уравновеши вания 4, ко(к .торый переводит устройство даня вычис-ф ления вектора градиента Ч,О . Процедура вычисления вектора градиента выполняется аналогично процедуре вычисления начального вектора градиен" таму". Блок уравновешивания 4 анализирует завершение вычисления вектора градиента Ч,, значение которого заносится в группу регистров 7 (и+1)- -го вычислительного блока 5, Фиксирует значения Функций 5(1 пЧО"и перевоыдит устроиство для выполнения следующего шага итерационного процесса, ко966702 13гистра 37 непосредственно, а с регистра 36 через мультиплексор 39, поступает на входы сумматора 34, который выполняет операцию над операндами. Результаты операций хранятся в регистре 35.В регистрах 35 и 36 осуществляется необходимый сдвиг. Вывод результатов вычисления на группу регистров 7 осуществляется через мультиплексор 40. Вход арифметико-логи О ческого узла 6 совмещен с выходом сумматора 34, а выход - с входом сумматора 34, Управляющие сигналы по ступают с блока уравновешивания 4 и на все эпементы арифметико-логическо го узла 6 по шине 45,Блок ввода-вывода 1 работает следующим образом. Шины 47-49 составляют внешний интерфейс для свяЗи с каналом ввода- вывода. Это прямая информационная шина 47, адресная шина 48, управление 49, По шине 50 информация с блока ввода-вывода 1 через мультиплексор ввода 13,и выходного регистра 17 поступает на входы вычислительных блоков 5. Шина 51 используется для передачи синхроимпульсов с генератора 16 и управляющего слова из регистра 19 в блок синхронизации 3 и блок уравновешивания 4. По шине 52 информация с выхода последнего вычислительного блока 5 поступает на выходной регистр 20, а по шине 53 информация поступает на блок индикации 3, По нине 54 сигналы с блока уравновешивания 4 поступают на узел управления 15, Шины 49-54 образуют внутренний интерфейс устройств, При ручном вводе посредством клавиатуры 11 набирается вводимое число и его адрес и выдается сигнал переключения мультиплексоров 13 и 14 на ручной режим ввода. В узел регистров 19 через мультиплексор 14 и память 18 вводится адресная инфор мация. Вводимое число с клавиатуры 11 через.преобразователь 12, мультиплексор 13 и .входной регистр 17 поступают на шину 50. При автоматическом режиме ввода мультиплексоры 13 и 14 пере ключаются на шины 47 и 48 соответст" венно, Информация данных с шины 47 через мультиплексор 14 и память 18 поступает в узел регистров 19, а с узла регистров 19 передается на ши ну 51, Управление работой блока ввода- вывода 1 осуществляет узел управления 15 и генератор синхро-импуль 14сов 16, Выводимая информация по сигналам узла управления 15 и генератора синхро-импульса 16 с шины 52 через выходной регистр 20 поступает либо на преобразователь 22 и далее на шину 53, либо через коммутатор 21 на шину 46. Остановка итерационного процесса и вывод результатов решения осуществляются по команде узла управления 15. При автономном использовании предлагаемого устройства сигналы остановок итерационного процесса поступают со всех микроавтоматов блока уравновешивания 4 по шине 54 на узел управле- ния 15, который через мультиплексор 14, память 18 и узел регистров 19 выдает команду вывода результатов на блок уравновешивания 4 через шину 51, При системном использовании устройства сигнал остановки итерационного процесса поступает на шину 49. Остановка итерационного процесса может осуществляться также клавиатурой 11. Мультиплексор 23 по команде блока управления 15 осуществляет передачу инФормации с последнего на первый вычислительные блоки 5 по шине 50.Все микроавтоматы блока уравновешивания 4 имеют одинаковую структуру и работают следующим образом.Сигнал с выхода блока ввода-вывода 1 по шине 55 через коммутатор 31 и элемент ИЛИ 29 запускает счетчик 28, который устанавливает номер команды. Сигнал номера команды с выхода счетчика .28 через дешиФратор 27 поступает на вход памяти 26. Память 26 выдает на вычислительный блок 5 по шине 56 сигнал кода операции, выполняемой вычислительным блоком 5, а на коммутатор 30 номер выполняемой операции. Узел логических условий 24 по шине 57 принимает с вычислительного блока 5 сигнал результатов выполнения операции и анализирует их.выхода узла логических условий 24 сигналы поступают на вход элемента И 26 и через коммутатор 30 и элемент ИЛИ 29 на второй вход счетчика 28. Счетчик 28 по команде элемента ИЛИ 29 и элемента И 25 устанавливает следующий номер подпрограммы. Сигнал с выхода счетчика 28 через дешифратор 27 поступает на вход памяти 26, которая выдает на шину 54 сигнал кода следующей операции и адрес памяти, При подаче с памяти 26 на шину 56 сигнала кода операции схема сравнения 32 сравнивает данный с сиг9667 налом подаваемым на вход схемы сравнения 33 с шины 55, Если код операции является последним в подпрограмме, то схема сравнения 33 выдает на узел логических условий 24 команду перехода анализа следующих условий. После выполнения каждого шага итерационного процесса узел логических условий 24 анализирует выполнение критериев остановки итерационного процесса. Если 10 критерии не выполняются, то узел логических условий 24 выдает на элемент И 25 и элемент ИЛИ 30 сигнал о переходе к следующей операции и итерационный процесс повторяется. Если 15 критерии выполняются, то узел логических условий 24 выдает сигнал на блок ввода-вывода 1 по шине 58. Блок ввода-вывода 1 выдает по шине 55 на элемент и 33 сигнал остановки итера ционного процесса. Элемент И 33 переключает счетчик 28, который через дешийратор 27 выдает сигнал на память 26. Память 26 по шине 56 выдаетна вычислительный блок 5 команды 25 подпрограммы вывода информацИи.В память 26 последнего микроавто-мата записаны только команды кода операции, выполняемой арифметико-ло гическим узлом 6 и группой регистров 7 З 0 (в+3)-го вычислительного блока 5. Адрес ячейки памяти в группе регистров 7 (и+3)-го вычислительного блока 5 определяется счетчиком 9 и регистром 10 при подаче с (я+3)-го микроавтомата блока уравновешивания 4 по шине 59 с элемента 33 счетчика импульсов.Преимущества предлагаемого устройства в сравнении с известными ранее40 обусловлены тем, что введение в устройство (в+3) - го вычислительного блока, в состав которого входят счетчик и регистр адресов, соединенных последовательно, позволяет расширить функциональные возможности предлагаемого устройства в части решения задач линейного программирования .Предполагаемый экономический эффект от использования вычислительных комплексов, частью которых является предлагаемое устройство, составляет 83,0 тыс.руб. в год, а срок окупаемости 0,4 года.. Формула изобретения1. Устройство для решения системы 55 алгебраических уравнений, содержащее блок ввода-вывода, блок синхронизации, блок уравновешивания и (в+2) 02 16 вычислительных блоков, (где щ - числоуравнений), причем управляющий входблока ввода-вывода соединен с (М+4)-мвыходом блока уравновешивания, выходсинхронизации блока ввода-вывода соединен с входом блока синхронизациивыход которого соединен с входом синхронизации блока уравновешивания, информационный выход блока ввода-вывода .соединен с инйормационным входомпервого вычислительного блока, первыйвыход 1-го (где 1= 1,2вч.3)вычислительного блока соединен с ин"формационным входом 4 +1)-го вычислительного блока, второй выход 1-го вычислительного блока соединен с 1-минформационным входом блока уравновешивания, 1-й выход которого соединенс управляющим входом 1-го вычислительного блока, о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных возможностей устройства засчет обеспечения решения задач линейного программирования, в устройствовведен (я+3) вычислительный блок,причем информационный вход этого бло"ка подключен к первому выходу (в+2)-говычислительного блока, управляющийвход которого соединен с (п+3)"м выходом блока уравновешивания, первыйвыход (в+3 )-го вычислительного блокасоеди нен с и нформационным входом блока ввода- вывода, второй выход которогосоединен с(В+3)-м входом блока уравновешивания,2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что (и+3)-й вы" числительный блок содержит арифметико-логический узел, группу регистров данных, регистр адресов и счетчик адреса, причем первый информационныйвход арийметико-логического узла явллется информационным входом блока, вто" рой инйормационный вход этого узласоединен с выходом группы регистров данных, который является также вторым выходом блока, выход счетчика адресов соединен с входом регистра адресов, выход которого соединен с информационным входом группы регистров данных, выход арийметико-:логического, узла яв- ляется первым выходом, вычислительного блока, вход счетчика адресов, управля. ющие входы арифметико-логического узла и группы регистров данных подкдючены к управляющему входу блока.966702 17 Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР М 55921, кл, 0 06 Р 15/32, 1977.182. Авторское свидетельство СССР по заявке 1 2753317/18-24,кл. 6 06 Г 15/32. 21.02,79 (прототип 3.