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

 

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

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

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву (22) Заявлено, 281178 (21) 2688965/18-24 (51)М. НЛ.

G 06 F 15/324 с присоединением заявки ¹â€”

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

СССР по делам изобретений и открытий (23) ПриоритетОпубликовано 23,02.81.Бюллетень №7

Дата опубликования описания 230281 (53) УДК 681. 325 . 5 (088. 8) .к (72) Автор изобретения

Л.Г. Козлов

- <> ГРф: „-,, ИЯ нУГ,.-, Ордена Ленина .институт кибернетики AH УкраиМЖЙй9Щ (71) Заявитель (54) МНОГОКАНАЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

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

Изобретение относится к вычислительной технике и может быть применено при построении специализированных и проблемно ориентированных процессов лля решения систем линейных алгебраических уравнений (СЛАУ) .

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

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

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

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

807318

40 сдвигового регистра, выход знакового разряда (n+1) -го сдвигового peri «тра связан с первым входом блока анализа, выход которого еоединен с входом соответствующего реверсивного счет чика, выход (и+1)-го сдвигового регистра соединен с вторым входом блока анализа и через первый элемент И вЂ” с вторым входом элемента .ИЛИ и с вторым входом первого одноразрядного сумматора соответствующего столбца, вторые входы элементон

И всех столбцов и управляющие входы реверсивных счетчиков соединены с управляющей шиной (3) .

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

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

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

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

В i-ые блоки 1 памяти заносятся коды коэффициентов решаемой СЛОУ,. в сумматоры 2 заносятся коды свободных членов, а сумматоры 3 и реверсивные счетчики 4 устанавливаются в нулевое состояние. Триггеры 5 устанавливаются н состояние,соответствующее знаку невязки, вычисляе мой н сумматорах 2 (на первой итерации это знак свободного члена

Ц = Ь1 ). Из блоков 1 памяти через ц) шйфраторы 8, управляемые сигналами от триггеров 5, на входы сумматоров

3 поступают коды коэффициентов соответствующих, столбцов матрицы СЛОУ со сдвигом на (разрядов влево д (Ю = 1 - P, P - разрядность), т.е, в сумматорах 3 вычисляются значения невязок Е „„ в соответствии со

К+1 следующей Формулой (к+1) (к)+ " „„(к) н к+4 где Е„„ - значение неняэок в сумматоре 3 на предыдущей итераgHHi

U. — сигналы состояния триггеj ров 5, соответствующие знакам невязок P . в суммато(к) рах 2; ((К) ч. (,ЕСли Е(" >О

1 1- (,если Е(9 <о

I — основная система счисления; (к)- значения невяэок в сумматорах

2.

Из блоков 1 памяти через шифраторы,7, управляемые. сигналами от триггеров б, на входы вычисления сумматоров 2 поступают коды коэффициентов соответствующих строк матрицы СЛАУ со сдвигом на (разрядов влево ((= — 1 — Р), а на другие входы вычитания сумматоров 2 поступают единицы 6 †.ro разряда в соответствии со знаками невязок, зафиксированных в триггерах

5, т.е. в сумматорах 2 вычисляются значения невязок в соответствии со следующей формулой (к 1) (к) (к) -6 (к) «к

;.„ 1 ()1 % (1% где с - значения невязон в суммато(к)

1 рах 2 на к-ой итерации; (о) =(, 1 1 ()(к)- сигналы состояния триггеров

11 б, соответствующие знакам невязок ((")в сумматорах 3;

U(K +(,ЕСли 5 >O;

-1,Если 6 ". (О, 1)

Одновременно с этим в реверсивных счетчиках 4 происходит формирование кодон искомых неизвестных Х * (К+1)

1 по следующим зависимостям

Х " " = Х(">+ П(к. Е ю т. е. в -ые разряды реверсивных счетчиков 4 прибавляется или вычитается единица, в зависимости от состояний триггеров б. Коды коэффициентов строк а„.. (1 = 1,2„...,п) решаемой системы уравнений ) а„.

= b„. (i = 1,2,...,n) хранятся в соответствующих блоках памяти, Перед решением задачи в сумматоры заносятся коды свободных членов b. реверсивные счетчики устананливаются в нулевое состояние. На первой итера- ции в триггерах фиксируются знаки свободных членов, затем к кодам, содержащимся в сумматорах и являющихся невязками для первой итера807318 ции Ж = b прибавляются и вычитаются в зависимости от состояния триггеров коды коэффициентов соответствующих строк, сдвинутые на 6 разрядов (= 1 — P где P — разрядность представления чисел в устройстве) в сторону младших разрядов, Одновременно в f --ый разряд реверсивных счетчиков прибавляется или вычитается единица в зависимости от состояния триггеров, т.е. в соответствии со знаками невяэок.

На каждой (к + 1)-ой итерации вычисления невязок в сумматорах производят в соответствии с формулами (К+1) К, -6,"„ ),(К)

1 1 ).11) j) где q — основание системы счисления;

U — состояние триггеров 5 на К к-ой итерации,.причем к -1,если Е к (о, +,Если K.". ЬО, Вычисление искомых неизвестных на (к+1) -ой итераций производится по формуле

Х-К+ = Х®+ Ы(".С

1 1

Метод простой итерации для решения СЛАУ, одной из модификаций которого является реализуемый в устройстве алгоритм сходится.в том случае, если коэффициенты решаемой СЛАУ довлетворяют следующим условиям

0„4 > .Й Io (, т,е. диагональные коэффицйенты решаемой СЛАУ больше по абсолютной величине суммы всех остальных коэффициентов в строке или столбце матрицы коэффициентов а Я=

=4,h I, Однако широкий класс СЛАу, к которому сводятся задачи, возникающие в прикладной механике, при обработке экспериментальной информации, определении коэффициентов корреляции, в задачах теории поля и математической физики и ряде других научно-технических задач, не удовлетворяют приведенным выше ограничениям и имеют коэффициенты в диагонали матрицы меньше по абсолютной величине других коэффициентов в строке или столбце. Такие задачи не могут быть решены в известном устройстве.

Предлагаемое устройство реализует такой алгоритм, который не зависит. от коэффициентов матрицы СЛАУ,поэто» му устройство по своим воэможностям приближается к универсальной ЭВМ.в рамках решения СЛАУ, но обладает более высокой производительностью и эффективностью обработки информации, что позволяет реализовать быстродействующие и дешевые вычислительные устройства и испольэовать ах в системах обработки информации реальном масштабе времени.

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

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

1. Майоров Ф.В. Электронные циф- о ровые интегрирующие машины М., Машгиз, 19б2, с. 86-88.

2. Евреинов Э.В. и Прангишвилм И.В. Цифровые автоматы с перестраиваемой структурой (однородные среды).М;, Энергия ™, 1972,с.195 °

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

У 543943 кл. G 06 F 15/32, 1975 (прототип).

I .Многоканальное устройство для ре15 шения систем линейных алгебраиЧеских уравнений, содержащее в каждом канале блок памяти, первая группа выходов которого .через шифраторы первой группы соединена соответстЩ венно с входами первого триггера,и реверсивный счетчик, о т л и ч а ю— щ е е с я тем, что, с целью расшире-. ния функциональных возможностей эа счет реализации алгоритма, который не зависит от коэффициентов матрицы системы уравнений, в каждый канал введены второй триггер и сумматор, и вторая группа шифраторов, выходы которых соединены с входами второго сумматора, выход которого через второй триггер соединен с входом реверсивного счетчика и с входами

807318

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

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

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

Заказ 294/75

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

Составитель A.Æåðåíîâ

Редактор Л. Кеви Техред С. Беца Корректор 0 Билак