Устройство для решения систем линейных алгебраических уравнений
Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве процессора для решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродействия. Устройство содержит 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 )!
