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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве процессора для решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродействия. Устройство содержит 2N-1 блоков 1<SB POS="POST">1</SB>-1<SB POS="POST">2N-1</SB> вычислений, где N - порядок системы линейных алгебраических уравнений, сумматор 2, блок 5 анализа, блок 6 синхронизации, элемент 7 задержки. Устройство предназначено для нахождения решения системы линейных алгебраических уравнений методом Гаусса-Зейделя. 3 ил.

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

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

РЕСПУБЛИК (51) 5 G 06 F 15/324

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

H А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4477038/24-24 (22) 23. 08 ° 88 (46) 23.05.90. Бюл. " 19 (71) Физико-механический институт им. Г.В. Карпенко АН УССР (72) В.Я. Мыхальчишин и И.В. Михальчишин (53) 681,325(088.8) (56) Авторское свидетельство СССР

11 813445, кл. С О6 F 15/324, 1981 °

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

1462353, кл. С 06 F 15/324, 1987. (54) УСТРОЙСТВО ДЛЯ РЕИЕНИЯ СИСТЕМ

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

ÄÄSUÄ 1566367 А1

2 (57) Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве процессора для решения систем линейных алгебраических уравнений. 1(ель изобретения — повышение быстродействия. Устройство содержит 2п-1 блоков 1 "1 „, вычислений, где и - порядок системы линейных алгебраических уравнений, сумматор 2, блок 5 анализа, блок б синхронизации, элемент 7 задержки.

Устройство предназначено для нахождения решения системы линейных алгебра" ических уравнений методом Гаусса-Зейделя. 3 ил.

1566367 х = Ах + b, где А хиЬ

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

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

На фиг. 1. представлена схема устройства для решения систем алгебраических уравнений; на фиг. 2 - схема блока вычислений; на Фиг. 3 - диаграмма работы устройства на первых десяти тактах при n=3, Устройство содержит (2п-1) блоков

1, -1 „, вычислений, где n - порядок системы линейных алгебраических уравнений, сумматор 2, (2п-1) входов 3„31„, коэффициентов системы линейных алгебраических уравнений устройства, вход 4 свободных членов системы линейных алгебраических уравнений устройств, блок 5 анализа, блок 6 синхронизации, элемент 7 задержки. Каждый блок 1 вычислений содержит умно- 25 житель 8, сумматор 9, с первого по третий регистры 10-12.

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

- пхп матрица коэффициентов;

- соответственно вектор неизвестных и вектор свободных членов размерности и, в виде — + У у (2)

1 где

1-1

z;-= а;х (3) j у, ?а,. х + Ь.; (4)

1 ) ° i

k — шаг инерции (метод Гаусса-Зей деля) .

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

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

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

В сумматорах 9 в конвейерном режиме осуществляется вычисление значений

z и „ . Суммирование слагаемых z

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

Блок 5 анализа предназначен для компонентной проверки точности решения системы алгебраических уравнений и выработки признака получения решения системы (1) . В нем вычисляется разница (x - х ", ) значений компоI 1 нент вектора неизвестных, полученных на k"é и (k-1)-й итерациях, и сравнивается с заданным порогом точности. / пя одновременного поступления на входы блока 5 анализа значений х, и х . на первом выходе (2п-1) -го

1< k-i блока 2 осуществляется задержка x" на и тактов. При удовлетворении заданной точности на выходе признака останова устройства появляется признак получения решения и с выхода результата устройства снимаются найденные значения вектора неизвестных.Подача входных данных на входы 3 -3

1 2п-1 и вход 4 происходит периодически, где период определяется временем выполнения одной итерации процесса решения систем линейных алгебраических уравнений.

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

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

5 15

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

k-ro блока вычислений подключен к тре тьему выходу(1+1)-ro блока вычислений, первый выход i-го блока вычислений, где i=2, ° .,п-1, подключен к вто рому информационному входу, (1 1)-го блока вычислений, второй и третий выходы j""ro блока вычислений, где

j=1,...,n-2, подключены соответственн к третьему и четвертому информационным входам (j+1)-ro блока вычислений, вторые выходы (n-1)-го и и-го блоков вычислений и третьи выходы (и-1)-го и и-го блоков вычислений подключены соответственно к информационным входам с первого по четвертый сумматора, выход которого подключен к вторым информационным входам (и-1)-l o u n i o блоков вычислений, к второму информа66367

Ь ционному входу блока анализа и к выходу результата устройства, шина нулевого потенциала которого подключена к третьему информационному входу, четвертому информационному входу первого блока вычислений и четвертому информационному входу (2n-1) -ro блока вычислений, первый выход которого подключен к входу элемента задержки, выход которого подключен к третьему информационному входу блока анализа, выход блока синхронизации подключен к тактовому входу сумматора, причем каждый блок вычисления содержит умножитель, сумматор и три регистра, при этом первый информационный вход блока вычисления подключен к первому информационному входу умножителя, второй информа- 20 ционный вход блока вычислений подключен к второму информационному входу умножителя и к информационному входу первого регистра, выход которого под" ключен к первому выходу вычислитель25 ного блока, третий и четвертый информационные входы блока вычислений о подключены к первому и второму инфор" мационным входам сумматора, выходы сумматора и умножителя подключены

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

156Ь 367

Составитель B. Смирнов

Техред И. Дидык

Корректор И. Иаксимишинец

Редактор В. Петраш

Заказ 1223 Тираж 563 Подписное

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

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

Производственно-издательский комбинат "Патент", r, Ужгород, ул. Гагарина, 1 )!