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

со ОЭ J

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

Фиг 1

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

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

На фиг. 1 представлена схема устройства для решения систем алгебраи- ческих уравнений; на фиг. 2 - схема блока вычислений; на фиг. 3 диаграмма работы устройства на первых десяти тактах при .

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

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

х Ах + Ь, (1)

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

х и b - соответственно вектор неизвестных и вектор свободных членов размерности п, в виде .

(2)

х zk

У,

k

Z ;

a JXj; V-

(3) (4)

,; - шаг инерции (метод Гаусса-Зей

деля).

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

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

5 0 5

0

5

0

5

0

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

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

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

Блок 5 анализа предназначен для компонентной проверки точности решения системы алгебраических уравнений и выработки признака получения решения системы (1). В нем вычисляется разница (х. - х k;1 ) значений компонент вектора неизвестных, полученных на k-й и (k-1)-n итерациях, и сравнивается с заданным порогом точности. Для одновременного поступления на входы блока 5 анализа значений х и х k ( на первом выходе (2п-1)-го блока 2 осуществляется задержка х на п тактов. При удовлетворении заданной точности на выходе признака останова устройства появляется признак полумения решения и с выхода результата устройства снимаются найденные значения вектора неизвестных.Подача входных данных на входы 3,37п , и вход происходит периодически, где период определяется временем выполнения одной итерации процесса решения систем линейных алгебраических уравнений.

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

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

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

k-ro блока вычислений подключен к тре- 20 ционный вход блока вычислений подклю- тьему выходу(k-t-1) -го блока вычисле- чен к второму информационному входу

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

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

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

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

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

Фиг. 2

ю о

а

е