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

1

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

Цель изобретения - расширение класса решаемых задач.

На чертеже изображена структурна схема предлагаемого устройства.

Устройство содержит матрицу п хп регистров 1, первую группу из п сдвговых регистров 2, вторую группу из п сдвиговых регистров 3, первую групу из п сумматоров 4 генератор 5 тактовых импульсов, входы 6 коэффицентов системы уравнений устройства, входы 7 свободных членов устройства выходы 8 результата устройства, первую и вторую матри1ды. размером п хп каждая групп элементов И соответственно 9 и 10, счетчик 1, вход 12 задания режима работы устройства, первый элемент И 13, второй элемент И 14, вторую группу из п сумматоров 15.

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

м( k)

РИ-Я.

р-1

,. Z

1-, 4-,

. P l

р-1

L а

Р--Г

, у . (К) Ь- Z b

р-1

v (it) p-l-v

X;- Z X ; 2,

kro

где i, j l,n;

. 0,;

x. e {0,,

k - цифры.

Вычисление цифр неизвестных систем уравнений осуществляется по следующим соотношениям:

г„ wV(К) P- -t

- ; f - ,Т - 2

ье

(k

;,Е

(t)

г Н

.f-(-sign(i, ));

0,если старший разряд f. , 0

1

1,если старший разряд „ 1;

2

К О, I . , , р- 1 ; i Г.п при условии, что на каждой итерации во всех невязках обнуляется старший разряд, т,е.

0,ЗЕ(,- ,, ,(2)

а новая нормализованная невязка вычисляется как

I

2.

i, fii ;, f+i

(kl.

Здесь X ; f - k-я цифра 1-го неиз Н

вестного на 1-й итерации; j нормализовая ная i-я невязка на 1-й итерации.

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

п

|«-.и 7

п -

1 е 1, N

И

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

S 0

X, X;

P-1-k

35

;

40

45

50

Количество итераций при этом возрастает (), но гарантируется уменьшение невязок до нуля с точностью р,

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

Коэффициенты и свободные члены решаемой системы уравнений перед началом вычислений заносятся,соответственно в регистры 1 через входы 6 и в регистры 2 через входы 7, Переход в состояние О выхода переполнения счетчика 11 может быть осуществлен следующим образом: обнулением счетчика II через вход 12, при этом вычисляются р-разряднь1е неизвестные; записью в счетчик II значения S, если необходимо вычислить лишь (p-S)цифр результатов.

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

При ходе решения по первому варианту каждым положительным фpoнтo f импульса с прямого выхода генератора 5 тактовых импульсов синхронизируется запись в регистры 2 и осуществля- ется сдвиг в регистрах 3, а каждым положительным фронтом импульса с инверсного выхода генератора 5 тактовых импульсов осуществляется сдвиг значений в регистрах 2 на один раз- ряд влево и увеличение значения счетчика 11 на единицу. При этом информация, поступившая в старший значащий разряд, и в знаковом разряде передается для управления соответствующими группами элементов И и первым и вторым элементами И.

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

После появления 1 на выходе переполнения счетчика 11 работа генератора тактовых иг-иульсов блокируется и результат с выхода регистров 3 поступает на выходы 8 устройства.

При ходе решения по второму варианту на итерациях, не приведших к обнулению старших значащих разрядов хотя бы в одном сдвиговом регистре 2 блокируется сдвиг как в этих регист- рак, так и в регистрах 3, а также не увеличивается значение счетчика 11, Это позволяет определить по вычисленным невязкам (1) корректирующие цифры, скорректировать значения не- известных и перейти к следующей итерации. Блокировка счетного входа счетчика 1I ка корректирующих шагах позволяет вычислять необходимое ко- личество цифр в значениях неизвест- ных (заданное при начальной установке счетчика 11 по шине 12).

Время вычисления неизвестных системы алгебраических уравнений в пер- вом варианте равно

t t -Р, во втором равно

1

где и определяются выбранной элементной базой.

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано при построении цифровых специализированных процессоров для решения систем линейных алгебраических уравнений. Цель изобретения - расширение класса решаемых задач. Поставленная цель достигается тем, что устройство содержит матрицы размером пхп гдеп- порядок системы линейных алгебраических уравнений, регистров 1., первую группу из п сдвиговых регистров 2, вторую группу из п сдвиговых регистров 3, первую группу из п сумматоров 4, генератор 5 тактовых импульсов, входы 6 коэффициентов матрицы системы уравнений, входы 7 свободных членов, выходы 8 результата, первую матрицу размером п хп групп элементов И9,1 вторую матрицу размером пхп групп элементов И 10, счетчик 11, вход 12 задания режима работы устройства, первый и второй элементы И 13 и 14, вторую группу из п сумматоров 15. Расширение функциональных возможностей обеспечивается тем, что при уменьшении не- зязок на заданную величину необходимо переходить к вычислению следующих цифр результатов, в противном случае - вычислять корректируюшие цифры неизвестных. 1 ил. с (С (f 00 го 4 О сд