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

 

хн че:;: ",3 иеевкк Ml, „

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

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

Республик

ПИСАНИЕ

ЗОБРЕТЕНИЯ

<11>798863

ВТОРСКОМУ СВИ ЕТИЗЬСТВУ

Дополнительное к авт. саид-вуЗаявлено 21. 02. 79 (21) 2753317/18-24 соединением заявки М—

ПриоритетОпубликовано 23.01.81. Бюллетень М 3

Дата опубликования описания 230181

<51)м. кл.

G Об F 15/324

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

СССР но делам изобретени и открытий (53) Юк в81.3 (088. 8) (72) Авторы изобретения

В.Д.Самойлов, В.Д.Бакуменко, A.Â.Çàðàíoâñêèé, A.À.Hàëüâà и В.A.Ìàì÷åíêo (71) Заявитель Институт электродинамики АН Украинской ССР (54) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ РЕЧЕНИЯ СИСТЕМ

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

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

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

Недостатком известного устройства является низкая надежность и техно- 15 логичность.

Наиболее близким по технической сущности к предлагаемому является цифровое устройство для решения систем алгебраических уравнений, 20 которое содержит блоки уравновешивания и синхронизации.

В блоках формирования коэффициенттов происходит умножение кодов коэффициентов на з;;ахи приращений пере- 25 менных. Результаты умножения построчно алгебраически суммируются в накапливающих сумматорах и регистрах и образуют. вектор невязок. Алгоритм минимизации реализуется блоком урав- 30 новешивания, на выходе которого формируются приращения вектора переменных. Полное значение вектора переменных накапливается в цифровых интеграторах. Вычислительный процесс заканчивается, когда все величины невязок становятся равными нулю (2).

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

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

798863

О

20

Цель изобретения — повышение надежности устройства.

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

На фиг.1 представлена блок-схема устройства, Устройство содержит блок вводавывода 1, блок индикации 2, блок синхронизации 3, m+2 вычислительных блока 4, в каждый из которых входят арифметико-логический узел 5, группа регистров б и формирователь 7 адресов, а также блок 8 уравновешивания.

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

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

АХ = В, где A — матрица коэффициентов a„.

 — вектор правых частей Ь„, X — вектор переменных х

i = 1. 2,...m;j=l, 2...n, m — число уравнений (строк А), n — число переменных (столбцов

А), решается итерационно модифицированным методом минимизации.

Перед началом решения посредством блока ввода-вывода 1 в регистры 6 (1-m)-x вычислительных блоков 4 построчно вводятся в дополнительном коде коэффициенты в; и правые части

Ь„, в регистры 6 (а+1) и (m+2)-ro блоков 4 вводятся соответственно начальные значения векторов,ц и Х,. где д = A Sign (AX-В), A — грансцонированная матрица, и постоянная ве30

d0

65 личина h — шаг поиска, а в блок синхронизации 3 заносится код числа, ограничивающего число итераций.

Вычислительный процесс осуществляется следующим образом.

В 1-m-x вычислительных блоках 4 параллельно и независимо построчно рассчитывается вектор невязок

Е = AX — В по программе, одинаковой для всех строк и составленной из команд, не требующих для их выполнения информации с входных машин.

На первом такте коэффициенты а„-„ из регистров б передаются в арифметико-логические узлы 5 своих t-x блоков 4, где происходит их умножение на переменную X " . Результат алгебраически суммируется с величиной Ь„, т.е. Е„„ = а„, Х вЂ” Ь„, и к . к заносится в регистры б. На втором такте коэффициенты а„ передаются в узлы 5 своих блоков 4 и умножаются на переменную Х . Затем в узлах 5

k формируются величины Е„ — — Е + а Х и заносятся в регистры б. На остальных и-2-х тактах вычисления аналогичны.

После выполнения программы расчета E в тех же 1-m-x вычислительк ных блоках 4 с использованием (m+1)-ro блока 4 начинается выполнение программы расчета вектора,Ок.

Программа за и тактов формирует вектор,И"= А S gn E". Hа первом такте на формирователи (1+в)-х блоковз

4 из блока 8 уравновешивания выдается одинаковая команда, предполагающая одновременное извлечение из регистров 6 коэффициента а„.„ со знаком, соответствующим его умножению на знак невязки Е„, его суммирование к в арифметико-логическом узле 5 с величиной на входе этого узла и выдачу результата на выход узлов 5 и 4.

В результате последовательного соединения комбинационных схем арифметика-логических узлов 5 в вычислительных блоках 4 на выходе m-го блока 4 по истечении времени окончания переходных процессов в (1-m)-x узлах

5 формируется величинаХ " Xiik -hsi

Остальные и-1 компоненты вектора,о определяются аналогично. Только на каждом такте вычисления в коде команды, выдаваемой в формирователи

7, изменяется адрес регистра в группе регистров б, равный j

Сформированные величины фк ...,,о„к заносятся и хранятся в

2 регистрах б (m+1)-ro вычислительногс блока. Одновременно с выполнением программы расчета вектора,О" рассчитывается вектор Х " ".

На первом такте по знаку величины,бл в m+2-м вычислительном волоке

4 в АЛУ рассчитывается величина

Х, = .

798863 тры 6. На остальных и-1 тактах по знакам соответствующих компонентов вектора,0 рассчитываются остальные компоненты вектора Х "+"

После определения вектора Х в

К+4 блоке 8 уравновешивания проверяют условия окончания итерационного вычислительного процесса по заданном числу итераций или зацикливанию процесса поиска вблизи точки искомого решения. При невыполнении этих условий итерационный процесс продолжается и повторяется вычислительный процесс.

При вводе и выводе информации в какой-либо i-й вычислительный блок 4 в формирователи 7 всех остальных вычислительных блоков 4 выдается команда, по которой информация с входа блока 4 проходит без изменений на его выход.

На формирователь 7 i-ro блока 4 поступает команда ввода-вывода, обеспечивающая запись информации с входа блока 4 в регистры 6 или считывание информации из регистров 6 на выход блока 4. Выводимая информация по цепочке последовательно соединенных

АЛУ 5 поступает на блок 1 и через него на блок 2 индикации. Управление вводом и Выводом информации, а также решением задачи осуществляется блоком

8 уравновешивания по сигналам с блоков ввода-вывода 1 и синхронизации

Блок ввода-вывода представляет собой интерфейс ввода-вывода, состоящий из подканалов ручного и автоматического ввода-вывода информации, и необходим для ввода исходной ин-. формации и команд, а также для организации обмена информацией и командами при неавтономном (системном) использовании предлагаемого устройства. Пример вв1полнения блока вводавывода приведен и" пг.2. Он содержит клавиатуру 9, преобразователь 10 десятичного кода в двоичный, мультиплексоры 11 и 12, узел управления 13, генератор 14 синхроимпульсов, входной регистр 15, память 16, узел 17 регистров, выходной регистр 18, коммутатор 19 и преобразователь 20 двоичного года в двоично-десятичный.

Блок ввода-вывода работает следующим образом.

Шины 21-25 составляют внешний интерфейс для связи с каналом вводавывода. Прямая информационнаяшина 21, обратная — 25, адресная шина 22, шины управления 23 и 24 °

По шине 26 информация с блока вводвывода поступает на информационную шину первого вычислительного блока.

Шина 27 используется для передачи синхроимпульсов с генератора 14 и управляющего слова из регистров 17 в блок синхронизации и далее не блок уравновешйвания. По шине 28 информация с выходной шины m+2-ro вычислительного блока поступает на выходной регистр 18. Шины 26-29 образуют внутренний интерфейс устройства.

При ручном вводе посредством клавиатуры 9 набирается вводимое число, выдается сигнал переключения мультиплексоров 1 1 и 12 на ручной подканаЛ ввода, в регистрах 17 через мультиплексор 12 и память 16 вводится адресная информация. Вводимое число с клавиатуры 9 через преобразователь

10, блоки 11, 15 поступают на вход 6.

При автоматическом .вводе мультиплексоры 11,12 переключаются на шины 21, 22. Информация с шины 21 через мультиплексор 11 и входной регистр 15

15 поступает на шину 26. Адресная информация с шины 22 под управлением узла

13 и генератора 14 синхроимпульсов побайтно заносится через мультиплексор 12 и память 16 в узел 17 регист2О ров. Сформированное управляющее слово передается в шину 21.

Ручной и автоматический вывод информации осуществляется аналогично вводу с той лишь разницей, что мульт типлексор 11 блокируется для прохождения информации и с узла 13 управления на коммутатор 19 поступает сигнал разрешения выдачи информации с выходного регистра 18 на шину 8. Через преобразователь 20 код с выходного регистра 18 выдается на блок индикации.

Блок уравновешивания представляет собой управляющий автомат для задания порядка выполнения всех подпрограмм вычислительными блоками. Он состоит из m+2-х микроавтоматов, схема одного из которых показана на фиг.3. Каждый вычислительный блок управляется своим микроавтоматом.

40 Такой микроавтомат состоит из узла логических условий:(УЛУ) 30, элемента И 32, дешифратора 33, счетчика 34, элемента ИЛИ 35, коммутатора 36, 37, схемы 38 сравне45 ния и элемента И 39.

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

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

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

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

„наДежности, в него введены блок ввода-вывода, блок индикации и (m+2) вычислительных блока, каждый иэ которых, содержит арифметико-логический узел, группу регистров и формирователь адресов, причем первый, второй и третий выходы блока вводавывода соединены соответственно со входами блока индикации, блока синхронизации и первым входом арифметико-логического узла первого вычислительного блока, арифметико-логические узлы всех вычислительных блоков соединены между собой последовательно, выход арифметико-логического узла (m+2)-ro вычислительного блока соединен со входом блока ввода-вывода, выход блока синхройизации соединен с входом блока уравновешиваний, группа входов которого подключейа: к выходам регистров группы всех вычислительных блоков, а группа выходов соединена с входами формирователей адресов всех вычислительных блоков, а в каждом вычислительном блоке выход формирователя адреса соединен с вторым входом арифметико-логического узла и входами регистров группы, вхо-, ды-выходы которых соединены с выходами-входами арифметико-логического узла.

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

15 1. Авторское свидетельство СССР

9 559241, кл.G 06 F 15/32, 1977.

2. Авторское свидетельство СССР

9 529468, кл.G 06 F 15/32, 1976 (прототип).!

98863

Составитель Н.Палеева

Редактор Т.Кугрышева Техред Н. Ковалева КорректорМ.Шароши

Закаэ 10057/68 Тираж 756 Подписное

BHHHIIH Государственного комитета СССР по делам иэобретений и,открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП "Патент", r.Óærîðîä, ул.Проектная,4