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

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

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

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

Устройство содержит группу реги- стров 1 неизвестного, группу регистров 2 невязки, группу регистров 3 приращений, элемент ИЛИ-НЕ 4, триггер 5, элемент 2И-ИЛИ 6, N. групп по N вычислительных элементов 7 и блок 8 синхронизации. Устройство имеет N групп по N входов 9 записи коэффициента, вход 10 запуска, выходы 11 и входы 12 начальных условий.

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

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

Блок 8 имеет вход 37 запуска , вхо 38 задания цикла, три выхода 39-41 и группу из N выходов 42.

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

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

, (1) , ,Ь. ,...,b,

где А

, .а.

а,а,,.

Мл

nn

Для реализации в предлагаемом устройстве система представляется в виде

fii Efi- Адхр лхр,,(гр,,) ,1,..., ,В, лх,0.

0

15 0

5 О

0

5

0

5

г.де РД - символ, указывающий, что в качестве приращения берется первый старший разряд невязки EI. ,

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

. (i ) i- +а,.лх. .J

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

Рассмотрим процедуру вычисления невязки несколько подробнее. Для определенности выберем невязку с номером 1, Таким образом старший разряд из первого регистра 3 поступает на первый вычислительный элемент (ВЭ) первой группыf Сюда же поступает приращение , -0. Происходит умножение приращения лх на старший разряд коэффициента а, хранимого в регистре рассматриваемого ВЭ. Осуществляется это следующим образом. Старший разряд коэ||)фициента а, который представлен в четвертичной избыточной системе счисления, поступает на первый адрес- ньй вход первого блока 14 памяти из регистра 13. На второй адресный вход- поступает приращение л х. В блоке 14 памяти записана таблица умножения

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

Здесь использовано двоичное кодирование четверичных- цифр (0-0.00, 1 - 0.01, 2 - 0.10, 3 - 0.11 , -1 - 1.11, -2 - 1.1Q). Таким образом, после перемножения старший разряд поступает на первый адресный вход второго блока 15 памяти, на второй адресный вход которого поступает младший разряд результата предыдущего перемножения, В нашем случае на оба входа поступают нули. На третий вход поступает разряд невязки, В блоке 15 памяти записана таблица сло

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

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

импульсов со второго выхода группы

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

5

0

5

0

35 0

5

гп

5

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

. (2n-m)(n+l)+m.

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

да существует 1 хотя бы на одном проводе, и на выходе элемента ИТШ- ИЕ 4 будет нуль. Это говорит о том, что итерационный процесс отыскания текущего разряда неизвестных не за- кончен и должен быть продолжен, В том епучае,, если все старшие разряд невязок равны нулю, на выходе элемента, Ш1И-НЕ 4 будет сигнал, равный 1„ Содержимое регистров 1 неизвест- кого сдвигается в сторону старших рарядов, В результате сдвига младший разряд неизвестного и поступающее новое приращение будут иметь один вес. Одновременно триггер 5 устанавливается в единичное состояние и на вход сдвига регистров 2 невязки поступает не ш, а (m+l) импульс, В результате в регистры 2 невязки запи- 1шется не m разрядов, а (m+l) разряд Так как запись ведется, начиная со старших разрядов, то первый старший разряд невязки будет потерян, а второй старший разряд станет первым, В результате этой операции достигается следующее. Всё старшие разряды, а они были, как это было показано, нулевыми, будут исключены из анали- за. Анализироваться будут теперь разряды невязки, имеющие вес на 1 меньше, но номер такта, в котором они будут анализироваться, сохраняется, анализируемый разряд остается первым Таким образом, увеличением веса содержимого регистров неизвестного и невязки достигается сохранение без изменения временной диаграммы, хотя и совершился переход на отыскание следующего младщего разряда Этот процесс повторяется до тех пор, пока н е будут определены все m разрядов, Это определяется подсчетом в устройстве управления числа 1, образующихся на выходе элемента ИЛИ-НЕ 4,

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

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

содержит триггер, элемент 2И-ШШ, N вьй информационный вход регистра яв- гругш по N вычислительных элементов ляется входом записи коэффициента вы- (где N - число неизвестньгх, равное числительного элемента, второй инфор числу уравнений в системе)-и блок син мационньй вход регистра подключен к хронизации, вход задания цикла кото- его выходу и к первому адресному вхоf5

20

г fo . 240366

рого подключен к выходу элемента ИЛИ-НЕ, к информацнонному входу триггера и к входам сдвига регистров неизвестного группы, информационный вход i-ro (,N) регистра неизвестного группы подключен к выходу N-ro вычислительного элемента i-й группы, к .-му входу элемента ИЛИ-НЕ и к информационным входам i-ro регистра приращений группы и i-ro регистра невязки группы, выход последнего подключен к первому информационному .входу первого вычислительного элемента группы, вторые информационные входы i-x вычислительных элементов всех групп подключены к выходу i-ro регистра приращений группы, синхро- входы регистров приращений группы и регистров неизвестного группы подключены к синхровходу триггера и первому выходу блока синхронизации, входы элемента 2И-ШТИ подключены соответственно к прямому выходу триггера, второму и третьему выходам блока син- 25 хронизации, и инверсному выходу триггера, выход элемента 2И-ШШ подключен к входам сдвига регистров невязки группы, j-ro вычислительного элемента (,N-l) каждой группы подключен, к первому входу (j+l)-ro вычислительного злемента той же группы, управляющие входы i-x (,N) вычислительных элементов всех групп подключены к (i+3)-My выходу группы блока синхронизации, вход записи коэффициента i-ro вычислительного элемента

30

35

i-й группы (,N, ,N) является i-M входом записи коэффициента j-й группы устройства, вход запуска блока синхронизации является входом запуска устройства, выходы регистров неизвестного группы являются соответствующими выходами устройства, установочные входы .регистров невязки являются входами начальных условий устройства, t

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

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

26 19

75

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

(puff. 2

J

ran

ft Тг...

4/7

4f

-t

42

ГзЛ

ZJi

4

Составитель Н.Захаревич Редактор Т.Парфенова Техред, И.ПоповичКорректор И.Муска

Заказ 2967/53

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

ВНИИГШ Государственного омитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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