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

 

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕ- , НИИ, содержащее матрицу размером ПП регистров коэффициентов, м сдвиговых регистров неизвестных, ц сдвиговых регистров свободных членов, П сумматоров (п - порядок системы линейных алгебраических уравнений) и генератор, тактовых импульсов, отличающееся тем, что, с целью увеличения быстродействия, в него введены первая и вторая матрицы размером И- И групп элементов И и счетчик , причем первые входы элементов И и счетчик, причем первые входы элементов И (А ,р-ых групп первой и второй матриц соединены соответственно , с прямыми и инверсными выходами (.1,)-го регистра коэффициентов матрицы , 4 tj-i t информационный вход -го сдвигового регистра свободных членов соединен с выходом 1-го сумматора , i 1,п , входы -го сумматора соединены с информационным входом i-ro сдвигового регистра свободных членов и с соответствующими выходами элементов И групп t-ых строк первой и второй матриц, выход старшего разряда -го сдвигового регистра свободных членов соединен с входом первого младшего разряда i -го сдвигового регистра неизвестных и с вторыми входами элементов И групп t -ых столбцов первой и второй матриц, прямой выход знакового разряда п-го сдвигового регистра свободных членов соединен с третьими входами элементов И групп 1 -ых столбцов первой (Л матрицы, инверсный выход знакового С разряда -ГС сдвигового регистра свободных членов соединен с входом второго младшего разряда i -го сдвигового регистра неизвестных и третьими входами элементов И групп -ых столбцов второй матрицы, прямой выг ход генератора тактовых импульсов . соединен с входами записи сдвиговых М регистров свободных членов и с входами сдвига сдвиговых регистров неизвестных , инверсный выход генератора тактовых импульсов соединен с входами сдвига сдвиговых регистров свободных членов и со счетным входом счетчика , выход переполнения которого соединен с входом останова генератора тактовых импульсов.

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

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

РЕСПУБЛИК

„„SU,, 117936 (5Ц4 G 06 F 15/324

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3618055/24-24 (22) 03.05.83 (46) 15.09.85. Бюл. Р 34 (72) В.Д.Байков и М.Б.Сергеев (53) 681.3(088.8) (56} Авторское свидетельство СССР

В 824217, кл. С 06 F. 15/324, 1981

Евреинов Э.В., Прангишвили И.В.

Цифровые автоматы с настраиваемой структурой (однородные среды). М.;

Энергия, 19749 с. 193-196. (54)(57) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее матрицу размером

tl l3 регистров коэффициентов, tl сдвиговых регистров неизвестных, и сдвиговых регистров свободных членов, н сумматоров (и — порядок системы линейных алгебраических уравнений) и генератор тактовых импульсов, о тл и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, в него введены первая и вторая матрицы раз» мером Ф И групп элементов И и счетчик, причем первые входы элементов И и счетчик, причем первые входы элементов И (i, )-ых групп первой и второй матриц соединены соответственно с прямыми и инверсными выходами (.1,1)-го регистра коэффициентов матрицы, ю,1 =1, ll, информационный вход

q -го сдвигового регистра свободных членов соединен с выходом e-ro сумматора, i =1, и входы 1 -го сумматора соединены с информационным входом

i-го сдвигового регистра свободных членов и с соотвегствующими выходами

1 элементов И групп 1-ых строк первой и второй матриц, выход старшего разряда 1 -го сдвигового регистра свободных членов соединен с входом первого младшего разряда -го сдвигового регистра неизвестных и с вторыми входами элементов И групп 1 --ых столбцов первой и второй матриц прямой выход знакового разряда z-ro сдвигового регистра свободных членов соединен с третьими входами элементов И групп -ых столбцов первой матрицы, инверсный выход знакового разряда t -гс сдвигового регистра свободных членов соединен с входом

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

1179367.

)($ Sign Q, ; (-Sign(б ;" )) ж o, lg ;" I г"

1, ; .г11

1Ф1 (5) при з.-j, p-! а; *K а(к).2 к к*о iS

4 .К Ь(2 к к о х It . (-sign(f;)) (6) E =0

О, если ст.разр.

1если ст.разр.

Р-1

),,,((к1 -к к=о

Е =1

1 при i j (3) (1,« i (к1 (к) < 1= Ъ.. =1,n, k° - о,р-< . а - в ц

Ь !

7 ры свободных членов

В регис н щ юг к(0 (1) знак х °

Изобретение относится к вычисли тельной технике и может быть приме, нено нри построении специализированных и .проблемно-ориентированных процессоров для решения систем линейных 5 алгебраических уравнений (СЛАУ) в двоичной системе счисления.

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

Алгоритм для решения СЛАУ вида и .й:а", =Ъ,i=(,п (1)

1- Ч представляется по методу "цифра эа цифрой" следующим образом: (м«) Е (к) - (к) (2)

Е. =- О 1 1, (ol

1т > (0, -(., йли для непосредственной структурной реализации в предлагаемом устройстве З в виде

На чертеже представлена структурная схема устройства. 55

Устройство содержит матрицу размером п п регистров 1 коэффициентов,. и сдвиговых регистров 2 неизвестных, Условием перехода на (1+1)-й шаг является выполнение соотношения

j < I <0в5 <, э 1=1,п. (4) Таким образом, переход на следующий шаг осуществляется, если на данном шаге значение каждой невязки уменьшается как минимум в два раза, т.е. обнуляется старший разряд в регистрах свободных членов.

Гарантией поразрядного уменьшения невяэок СЛАУ является соблюдение условия сходимости, которое для итера ционных процессов оценивается следующим соотношением

Верность получаемых на каждом шаге цифр в значениях корней гарантируется условием (5). Все коэффици.енты, свободные члены и искомые корни для СЛАУ вида (1) представляются правильными дробями и задаются в позиционной системе счисления с основанием 2 р-разрядными симметричными ,кодами в виде и записываются до начала вычислений числений х записаны в виде и сдвиговых регистров 3 свободных членов, и сумматоров 4, генератор 5 тактовых импульсов, шины 6 записи коэффициентов, шины 7 записи свободных членов, выходные шины 8, первую

3 11793 и вторую матрицу размером п.п групп элементов И соответственно 9 и 10, счетчик 11, шину 12 начальной установки

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

Сумматор 4 конструктивно выполнен по комбинационной схеме и имеет (n+ 1

+1) р-разрядных входов.

Вычисление значений корней СЛАУ с необходимой точностью (р разрядов) в устройстве производится до появления сигнала переноса счетчика 11. 2б

Этот сигнал при достижении счетчиком значения р блокирует работу генератора тактовых импульсов 5. Емкость счетчика таким образом однозначно определяет точность (количество вычисляемых разрядов в значениях корней).

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

После записи в регистры 1 по ши нам 6 коэффициентов решаемой СЛАУ и установки на шинах 7 ее свободных членов сигналом по шине 12 обнуляется счетчик 11, т.е. переходит в состояние "0" выход переноса. Это позволяет запуститься генератору тактовых.импульсов 5.

3S

Первым положительным фронтом им.пульса с прямого выхода генератора синхроиизируется запись с шин 7 B регистры 3 свободных членов и произво.дится пустой сдвиг в регистрах 2, поскольку до начала работы регистры

3 были пусты, т.е. старший значащий

67 4 разряд находился в состоянии "0". Это нулевое состояние обеспечивается и беэ предварительного обнуления, так как после окончания решения в устройстве любой предыдущей СЛАУ по условию (4) старший разряд обнулен. Первым noJIQRHTeJIbHbM фронтом импульса с инверсного выхода генератора 5 осуществляется сдвиг значений свободных членов на один разряд влево, тем самым в старшие значащие разряды регистров поступают первые разряды свободных членов для анализа, установки на входах регистров 2, управления соответствующими группами элементов И 9 и 10.

НЛ протяжении всего процесса вычислений эа время которое проходит ь между появлением положительных фронтов с прямого выхода генератора 5, происходит запись в регистры 3, сдвиг в регистрах 2, а через равные длительности положительного импульса с прямого выхода генератора тактовых импульсов — сдвиг в регистрах 3. 3а время между положительными фронтами с инверсного и прямого выходов гарантированно появляется результат на выходах сумматоров 4.

Кроме того, положительньм фронтом с инверсного выхода генератора 5, подключенного к счетному входу суммирующего счетчика 11, прибавляется

"1" к его содержимому.

После появления "1" иа выходе переноса счетчика 11 работа генератора тактовых импульсов блокируется.

Время вычисления корней СЛАУ и-го порядка с р значащими двоичными цифрами определяется следующим образом:

1179367

6

Составитель И.Пчелинцев

Редактор И.Ковальчук Техред Т. акта Корректор М. СамбоРскаЯ

Заказ 5678/52 Тираж 710 Подписное

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

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

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4