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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах для решения систем алгебраических уравнений вида . Целью изобретения является повышение быстродействия устройства. С этой целью устройство содержит матрицу вычислительных элементов, структурно подобную матрице коэффициентов А(а-; . Каждьш вычислительный элемент ведет обработку одного из неизвестных системы с применением табличного метода вычислений с помощью двух блоков постоянной памяти. Вычисления ведутся в избыточной четверичной системе счисления. 1 з.п. ф-лы, 4 ил. с б со N3 N О оо о:

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (дц 4 (, 06 F 15/32

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К A BTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4037357/24-24 (22) 17.03,86 (46) 15.07.87. Бюл. № 26 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.Е.Золотовский, Р.В.Коробков и В.Е.Горюнов (53) 681.325(088.8), (56) Авторское свидетельство СССР

¹ 710044, кл. G 06 F 15/32, 1980, Авторское свидетельство СССР № 1088087, кл. С 06 F 15/32, 1984. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к вычислительной технике и может быть исSU» 1324036 А 1 пользовано в специализированных вычислительных устройствах для решения систем алгебраических уравнений вида

АХ+В=О. Целью изобретения является повышение быстродействия устройства.

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

Вычисления ведутся в избыточной четверичной системе счисления. 1 s.n. ф-лы, 4 ил.

1 1 3240

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

АХ+В=-О.

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

На фиг. 1 показана блок-схема устройства; на фиг. 2 — функциональная 10 схема вычислительного элемента; на фиг. 3 — временная диаграмма работы устройства; на фиг. 4 — функциональная схема блока синхронизации.

Устройство содержит группу реги- 15 стров 1 неизвестного, группу регистров 2 невязки, группу регистров 3 приращений, элемент ИЛИ-НЕ 4, триггер 5, элемент 2И-ИЛИ 6, N групп по

N вычислительных элементов 7 и блок 20

8 синхронизации, Устройство имеет

N групп no N входов 9 записи коэффициента, вход 10 запуска, выходы 11 и входы 12 начальных условий.

Вычислительный элемент 7 содержит 25 регистр 13, два блока !4 и 15 памяти, шесть элементов 16-21 задержки и сумматор 22 в избыточной четвертичной системе счисления, Вычислительный 7 элемент имеет управляющий вход. 30

23, вход 24 записи коэффициента, два информационных входа 25 и 26 и выход 27.

Блок 8 синхронизации содержит генератор 28 импульсов, счетчик 29 разрядов, счетчик 30, дешифратор 31, триггеры 32, элементы И 33 и три элемента ИЛИ 34-36.

Блок 8 имеет вход 37 запуска, вход

38 задания цикла, три выхода 39-41 0 и группу из N выходов 42.

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

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

АХ+В=О (1) 36 2 о гд P „ — символ, указывающий, что в качестве приращения берется первый старший разряд невязКИ Е д+„

Как следует из выражения (2), в качестве начального приближения берутся свободные члены, которые заносятся в регистры 2 невязки по входам

12 начальных условий ° Коэффициенты матрицы А заносятся в регистры 13 вычислительных элементов 7, причем а,. записывается в 1-й вычислительный эле1 мент 7, i-й группы. В регистрах 3 приращений первоначально записаны нули. Триггер 5 находится в нулевом состоянии (это взято для определенности, в первом шаге безразлично, в каком состоянии триггер 5), тогда по серии управляющих сигналов с выхода

40 содержимое регистров 3 приращений разряд за разрядом, начиная со старших разрядов, поступает на первые информационные входы 25 вычислительных элементов. Нулевые значения приращений поступают из регистров 3 приращений на вторые информационные входы 26 вычислительных элементов, В вычислительном элементе выполняется операция умножения коэффициента матрицы А, хранимого в данном элементе, на приращение и сложение произведения с поступающей на вход элемента невязкой.

Для произвольного элемента а," можно записать

s((+a)=(„.с .,„дх„а;,д х,...,+а... дх „)+

+а,"дх, .

1.() 1!

Так как в первом шаге все дх равны нулю, то 1;„=Ь;, т.е. невязка сохраняет значейие свободного члена, 1

Рассмотрим процедуру вычисления невязки несколько подробнее, Для определенности выберем невяэку с номером 1, Таким образом старший разряд из первого регистра 3 поступает на первый вычислительный элемент (ВЭ) первой группы, Сюда же поступает приВ=-1Ь„,Ь,,...,Ь„) где A= а,„а, ...а,„ а,„а, а а ...а, Я,„=tp Адх о д + p+a Р- q (p+ a ) Х=о,l,..., К,=В, дх,=О, (2) Для реализации в предлагаемом устройстве система представляется в виде ращение дх„ =-О. Происходит умножение приращения дх„ на старший разряд ко5Q эффициента а„„, хранимого в регистре рассматриваемого ВЭ, Осуществляется это следующим образом. Старший разряд коэффициента а, который представлен в четвертичной избыточной системе счисления, поступает на первый адресный вход первого блока 14 памяти из регистра 13. На второй адресный вход поступает приращение дх . В блоке ю

14 памяти записана таблица умножения

6 4 тов строк окончательно формируются в виде множества новых невязок — (Е(р+„1,,(д+,1,... Д(,+,1 . Происходит это через 2п тактов. Здесь возможны два случая 2п m и 2n > m, где m— число разрядов обрабатываемых данных.

В каждом случае будет своя диаграмма работы, На фиг. 3 изображена диаграмма работы для случая 2п з m. В этом случае считывание из регистров невязки заканчивается раньше, чем произойдет обработка невязки в матрице. В связи с этим в синхросерии с выходов 40 и 41 блока 8 управления имеется момент, когда импульсы отсутствуют (пауза). Длина первой паузы определяется величиной (2п-ш). Первая пауза образуется в случае, когда считывание из регистра невязки завершено, — а запись еще невозможна. Вторая пауза возникает в том случае, когда запись в регистр закончена, а считывание из регистра невязки недопустимо, так как с выходов вычислительных элементов считывается хвост невязки. После окончания умножения необходимо три дополнительных такта для обнуления схемы умножения — такт на первую группу линий задержек, такт на вторую группу и такт на обнуление сумматора 22. Таким образом, минимальная длительность паузы равна такту. Для того, чтобы переходные процессы завершились полностью, вторую паузу расширим до двух тактов. Тогда общее время вычисления невязки будет равным

Рассмотрим как формируются приращения неизвестных, Из алгоритма (2) следует, что в качестве приращення берется старший разряд невязки. Старший разряд невязок образуется по второму такту синхросерии на выходах сумматоров 22, последних БЭ групп, Для выделения этого такта подается сигнал с: выхода 39 блока 8 управления. Он совпадает по времени со вторым импульсом со второго выхода группы 42.

По этому импульсу происходит запись старших разрядов невязки в регистры приращений и происходит сложение содержимого регистров 1 неизвестного со старшими разрядами невязок.

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

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

42. Эта серия подобна серии с перво" го выхода группы 42 и сдвинута на два разряда. Во втором ВЭ первой группы формируется новое значение частичной невязки. Работает ВЭ аналогично описанному. Проходя последовательно через вычислительные элементы строк, частичные невяэки на выходах последних вычислительных элемен3 132403 цифр избыточной четверичной системы счисления. Здесь использованы два вида кодирования: вспомогательное, содержащее следующие цифры (0,1,2, -11 H ocHoBHoe кодирование, содержащее шесть цифр (0,1,2,3,-1,-2 1

В качестве примера покажем значение на выходе блока памяти при поступлении максимальных цифр:

Первый Второй Старший Младший

10 вход вход разряд разряд

011 011 010 001

110 011 ill 110

110 110 001 000 15

010 010 00 1 000

Здесь использовано двоичное кодирование четверичных- цифр (Π— О ° 00, 1 — 0.01, 2 — 0.10, 3 — 0.11, -1

1.11, -2 — 1.1()). Таким образом, после перемножения старший разряд поступает на первый адресный вход второго блока 15 памяти, на второй адресный вход которого поступает младший разряд результата предыду25 щего перемножения. В нашем случае на оба входа поступают нули. На третий вход поступает разряд невязки: В блоке 15 памяти записана таблица сложения 3-х цифр, поступающих на его входы, Результат фбрмируется в виде двух цифр, старшая поступает на сумматор 22 непосредственно, а младшая-с задержкой на один такт. После поступления второго разряда в суммато- 35 ре 22 окончательно сформируется первый разряд результата. Таким образом, через два такта старший разряд первой частичной невязки E » оказыва1(P 1) ется сформированным, и он поступает 40 на второй ВЭ первой группы.

N=2m+ (2п-m)+2=2 (n+1)+m.

5 !324036 да существует 1 хотя бы на одном проводе, и на выходе элемента ИЛИНЕ 4 будет нуль, Это говорит о том, что итерационный процесс отыскания текущего разряда неизвестных не закончен и должен быть продолжен. B том случае,, если все старшие разряды невязок равны нулю, на выходе элемента ИЛИ-НЕ 4 будет сигнал, равный

1. Содержимое регистров 1 неизвест- !ð ного сдвигается в сторону старших разрядов. В результате сдвига младший разряд неизвестного и поступающее новое приращение будут иметь один вес. Одновременно триггер 5 устанавливается в единичное состояние и на вход сдвига регистров 2 невязки потупает не ш, а (тп+1) импульс. В реультате в регистры 2 невяэки запнется не m разрядов, а (ш+1) разряд.

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

Таким образом, увеличением веса содержимого регистров неизвестного и невязки достигается сохранение без изменения временной диаграммы, хотя и совершился переход на отыскание следующего младшего разряда. Этот процесс повторяется до тех пор, пока не будут определены все m разрядов, Это определяется подсчетом в устройстве управления числа 1, образующихся на выходе элемента ИЛИ-HE 4.

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

1. Устройство для решения систем алгебраических уравнений, содержащее группу регистров неизвестного, gg группу регистров невяэки, группу регистров приращений и элемент ИЛ!-НЕ, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит триггер, элемент 2И-ИЛИ, N групп rro N вычислительных элементов (где N — число неизвестных, равное числу уравнений в системе) и блок синхронизации, вход задания цикла которого подключен к выходу элемента

ИП!1-НЕ, к информационному входу триггера и к входам сдвига регистров неизвестного группы, информационный вход i-ro (i=!,N) регистра неизвестного группы подключен к выходу 11-го вычислительного элемента i-й группы, к |.-му входу элемента ИЛИ-HE и к информационным входам i-го регистра приращений группы и i-го регистра невязки группы, выход последнего подключен к первому информационному .входу первого вычислительного элемента

i-й группы, вторые информационные входы i-x вычислительных элементов всех групп подключены к выходу i-ro регистра приращений группы, синхровходы регистров приращений группы и регистров неизвестного группы подключены к синхровходу триггера и первому выходу блока синхронизации, входы элемента 2И-ИЛИ подключены соответственно к прямому выходу триггера, второму и третьему выходам блока синхронизации, и инверсному выходу триггера, выход элемента 2И-ИЛИ подключен к входам сдвига регистров невязки группы, выход j-ro вычислительного элемента (1=!,N-1) каждой группы подключен к первому входу (3+1)-го вычислительного элемента той же группы, управляющие входы i-х (i=l,N) вычислительных элементов всех групп подключены к (i+3) ìó выходу группы блока синхронизации, вход записи коэффициента i-го вычислительного элемента

i-й r.ýóïïû (i=1,N, j =1,N) является -м входом записи коэффициента j --й группы устройства, вход запуска блока синхронизации является входом запуска устройства„ выходы регистров неизвестного группы являются соответствующими выходами устройства, установочные входы регистров невязки являются входами начальных условий устройства, 2, Устройство по и. 1, о т л и ч а ю щ е е с я тем, что вычислительный элемент содержит регистр, два блока памяти, шесть элементов задержки и сумматор в избыточной четверичной системе счисления, причем синхровход регистра является управляющим входом вычислительного элемента, первый информационный вход регистра является входом записи коэффициента вычислительного элемента, второй информационный вход регистра подключен к его выходу и к первому адресному вхо132403б ду первого блока памяти, второй адресный вход которого является вторым информационным входом вычислительноro элемента, первый информационный вхОд которого подключен к первому адресно- 5 му входу второго блока памяти, второй адресный вход которого подключен к первому выходу первого блока памяти, разряды третьего адресного входа которого подключены к выходам со- )p ответственно первого, второго и третьего элементов задержки, входы которых.подключены к соответствующим разрядам второго выхода первого блока памяти, первый выход второго блока памяти подключен к входу первого слагаемого сумматора в избыточной четверичной. системе счисления, разряды входа второго слагаемого которого подключены к выходам соответственно четвертого, пятого и шестого элементов задержки, входы которых подключены соответственно к разрядам с первого по третий второго выхода второго блока памяти, выход суммы сумматора в избыточной двоичной системе счисления является выходом вычислительного элемента.

1324036 л р

ДД )ДФ4 ° шз" лз :" a

Е/ил

1324036 иР

Составитель Н.Захаревич

Редактор Т.Парфенова Техред И.Попович Корректор И.Муска

Заказ 2967/53

Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4