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

 

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

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

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

РЕСПУБЛИН (5g 4 G 06 F 15/324 вс соп":нц 1 рта@;.;,,. „, н,Н43

Ь ЬЛ;О.

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

К ASTOPCHOMV СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4282428/24-24 (22) 08. 07. 87 (46) 28.02.89. Бюл. Ф 8 (71) Физико-механический институт им. Г.В.Карпенко (72) В.В.Грицык, И.Н.Калиняк, В.Я.Мыхальчишин и P.M.Ïàëåíè÷êà. (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 813445, кл. G 06 F 15/324, 1981.

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

У 1198535, кл. G 06 F 15/324, 1985.

„„SU„,, 1462353 А1 (54) УСТРОЙСТВО ДЛЯ РЕШЕНКЯ СИСТЕМ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано для решения систем линейных алгебраических уравнений. Цель изобретения — повышение быстродействия. Поставленная цель достигается тем, что устройство содержит 2п-1 процессорных элементов 1, где и— порядок системы линейных алгебраических уравнений, 2п-1 блоков 2 памяти, 2п-й блок 3 памяти, блок 4 анализа и синхронизатор 5. 6 ил.

1462353

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

Цель изобретения — увеличение быстродействия.

На фиг. 1 представлена схема уст- 1Р ройства для решения систем алгебраических уравнений; на фиг. 2 — функциональная схема процессорного элемента; на фиг. 3 — схема блока анализа; на фиг. 4 — схема размещения 15 в блоках памяти элементов матрицы коэффициентов и вектора свободных членов размерности 3; на фиг, 5 схема процесса начальной загрузки процессорных элементов; на фиг. 6 — 20 схема пяти первых тактов работы устройства при п=3.

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

2 памяти; 2п-й блок 3 памяти, блок 4 анализа и синхронизатор 5. При этом блок 4 анализа состоит иэ вычитателя

6, регистра 7, схемы 8 сравнения, а также первого 9 и второго 10 счет- 30 чиков.

Устройство реализует итерационный процесс Х =АХ +В, где А " матрица перехода оазмевности и х и; В— вектор правой части системы уравнений; к — номер итерации, Перед процессом решения системы алгребраических уравнений в блоки 2 памяти устройства вводятся коэффициенты матрицы перехода А, а в блок 3 40 памяти записывается заданный вектор

В размерности и. Блоки 2 и 3 памяти

;состоят из 2п-1 ячеек памяти каждый и снабжены схемой циклической пере записи информации, При этом коэффи- 45 циенты заданного вектора В записываются в соответствующие ячейки с нечетными номерами блока 3 памяти, а во все ячейки с четными номерами записывается "0", Аналогично происхо- 5р дит запись коэффициентов матрицы перехода А в блок 2 памяти. В регистр 7 с информационного входа устройства записывается код числа, задающего точность решения системы алгебраических уравнений. Затем происходит начальная загрузка процессорных элементов 1. При поступлении тактовых импульсов от синхронизатора 5 йа вход считывания блока 3 памяти выполняется считывание информации, записанной в 2п-1 ячейках памяти, и ее запись в регистры-фиксаторы соответствующих процессорных элементов 1. 3а начальные значения компонент вектора неизвестных прини" мают значения компонент вектора В.

В сост ав блоков 2 памяти входят также схемы блокирования считывания, т.е; схемы установки в "0" считываемых данных при поступлении первых

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

При поступлении тактовых импульсов от синхронизатора 5 происходит считывание данных из блоков 2 памяти и блока 3 памяти. При этом числа на выходе первой ячейки памяти i-го блока 2 памяти, где i=1, 2п-1, поступают на информационный вход i-го процессорного элемента 1, а число на выходе первой ячейки блока 3 памяти поступает на вход (2п-1)-ro процессор ного элемента 1. В каждом такте работы устройства в процессорном элементе 1 реализуются операции умноже.ния и сложения согласно схеме на фиг. 2. Каждый процессорный элемент 1 состоит из умножителя и сумматора, кроме того, он содержит соответст-. вующие регистры-фиксаторы на выходах процессорного элемента.

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

>ний, и в нем осуществляется покомпо.нентное сравнение текущего вектора решения с предыдущим вектором. В каждом такте работы устройства на выходе вычитателя 6 появляется абсолютное значение разности i-й компоненты вектора решения на k-й итерации

Х, и i-й компоненты вектора решения

1 К11 на {k+1)-й итерации Х;, т.е., вычисляется значение /Х "" -Х .I. Далее осуществляется сравнение этого значения с порогом, задающим точность решения системы уравнения.

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

Устройство для решения систем линейных алгебраических уравнений, содержащее 2п-1 блоков памяти и 2п-1 процессорных элементов, где n — порядок системы линейных алгребраических уравнений, причем первый выход i-ro )5 процессорного элемента (1=1,...,2п-2) подключен к первому информационному входу (i+1)-ro процессорного элемента, второй информационный вход j-ro процессорного элемента ()=1,...,2п-2) 2О подключен к второму выходу (j+1)-ro процессорного элемента, третий информационный вход k-ro процессорного элемента (k=1,...,2n) подключен K mrxopy k-ro блока ти, о т л и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, в него введены 2п-й блок памяти, блок анализа и синхронизатор, причем вход задания точности устройства подключен к первому информационному входу блока анализа, выход которого подключен к выходу признака завершения вычислений устройства, выход 2n-ro блока памяти подключен к первому ин.формационному входу первого процессорного элемента, второй вход которого подключен к выходу результата устройства и к второму информационному входу блока анализа, первый выход (2n-1)-4 го процессорного элемента пддключен к третьему информационному входу блока анализа н к второму информационному входу (2n-1)-го процессорного элемента, вход запуска устройства под-: ключен к входу запуска синхронизатора, первый и второй выходы которого подключены соответственно к синхровходу блока анализа и к входу записи-чтения

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

1 31

I—

l—

1а !

ig -g -g

Х, **br а„ ; к Ц rrt„xr+rtrtxt к Ю ах к

S Ф ° °

М4 анх rrtitxt а, х, 4 ta аю

l ° О к, = ахх; аокх

+s b+ tr кв х кх =l >rttrxi юхххфадхs хт- а

У O Ф х> f +atrxt арх,,йем

ык, -к»

° в f к к» ° °

gt х- Х / аХ Х Iattxt rrtt tt х br

Arab ,4йЬФИ

rg< -к /

t t

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

Редактор А" .Огар Техред Л.Олийнык Корректор Г.Джула

Заказ 715/49 Тираж 667 Подписное

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

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

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

Г а

) И

lu

1 !

1462353 1 Г I 33

1 а, ><@pl

1а, 1 J