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

- {. J/ / j/

(Л

с:

Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве процессора для решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродействия. Поставленная цель достиается тем, что устройство содержит N вычислительных блоков 1, где N - порядок решаемой системы линейных алгебраических уравнений, блок 4 анализа, блок 5 синхронизации и борк 6 формирования импульсов. 3 ил.

ел

оэ

05 00 О5

оэ

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

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

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

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

Число в регистр 10 1-го блока 1

10

15

25

ных членов системы линейных алгебраи-,Q записывается через четвертый инфор- ческих уравнений устройства,- блок h мационный вход. Запись осуществляет- анализа, блок 5 синхронизации и блок 6 формирования импульсов.

Блок 1 вычислений содержит первый регистр 7, умножитель 8, сумматор 9, второй регистр 10, триггер 11 и третий регистр 12. Блок 6 формирования импульсов содержит счетчик 13, триггер 1, первый 15 и второй 16 элементы И.

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

30

ся пбд воздействием импульса, поступающего с управляющего входа блока 1 вычислений на вход записи/считывания соответствующего регистра 10. Данный импульс появляется на выходе блока 6 формирования импульсов через каждые п тактов в промежутке между n-м и (п + 1)-м тактами.Под воздействием тактовых импульсов этот импульс передвигается от одного триггера 11 к другому, записывая при этом информацию в регистры 10 соответствующих блоков 1 вычислений. В каждом триггере 11 данный импульс задерживается на один такт. Таким образом считывание информации с первого выхода 1-го блока вычислений, где i 1,n, осуществляется в каждом такте, а -изменение информации в регистре 10 (i + 1)-го блока 1 вычислений осуществляется в каждом (i + n) (k - 1}-м . такте, где k 1,m; m - число циклов решения задачи.

d,

невырожденная матрица размерности ;

заданный вектор размерности п, инерционным методом Якоби;

X k + (СХ - d)

-- АХ -с Б,

(D

гд2 k - HdMep итерации;

О - итерационный параметр; А Е -f t С - матрицы перехода (Е - единичная матрица).

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

Перед началом решения системы линейных алгебраических уравнений в блок k анализа записывается код порога,1 задающий точность решения системы линейных алгебраических уравнений. В блок 6 формирования импульсов записывается число п. Блок 6 формирования импульсов генерирует управляющие импульсы для блоков 1 вычис63664

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

Число в регистр 10 1-го блока 1

10

15

5

Q записывается через четвертый инфор- мационный вход. Запись осуществляет-

0

5

5

0

5

ся пбд воздействием импульса, поступающего с управляющего входа блока 1 вычислений на вход записи/считывания соответствующего регистра 10. Данный импульс появляется на выходе блока 6 формирования импульсов через каждые п тактов в промежутке между n-м и (п + 1)-м тактами.Под воздействием тактовых импульсов этот импульс передвигается от одного триггера 11 к другому, записывая при этом информацию в регистры 10 соответствующих блоков 1 вычислений. В каждом триггере 11 данный импульс задерживается на один такт. Таким образом считывание информации с первого выхода 1-го блока вычислений, где i 1,n, осуществляется в каждом такте, а -изменение информации в регистре 10 (i + 1)-го блока 1 вычислений осуществляется в каждом (i + n) (k - 1}-м . такте, где k 1,m; m - число циклов решения задачи.

Блок k анализа предназначен д 1я покомпонентной проверки точности решения системы линейных алгебраических уравнений, и в нем осуществляется покомпонентное сравнение текущего вектора решения с предыдущим. Компоненты текущего вектора решения поступают на блок 4 анализа с первого выхода n-го блока 1 вычисления, а компоненты предыдущего вектора решения - с второго выхода n-го блока 1 .вычислений. В каждом такте работы устройства в блоке Ц анализа вычисляется значение X - X + г и происходит сравнение этого значения с

порогом, задающим точность решения системы уравнений.

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

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

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

формационным входам первого блока

0

5

0

5

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

0

0

5

0

5