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

 

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

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

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

РЕСПУБЛИК

„„Я0„„1633422 (5!)5 G 06 F 15 32

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

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

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

ПРИ ГКНТ СССР

К АBTOPCKOMV СВИДЕТЕЛЬСТВУ (21) 4661472/24 (22) 13.03.89 (46) 07. 03.91. Бюл. № 9 (72) В. П. Якуш, Н. А. Лиходед, В. В. Косьянчук, П. И. Соболевский и В. И. Мостовой (53) 681.325 (088.8) (56) Hwang К., Cheng Y. — Н. VLSI Computer . structures for solving Large — Scale

linear system of equations. — Proc. Int. Conf.

Parallel Proc., 1980, N. Y., р. 217 — 227.

Brudary О. Systolic algorithms to solve

linear systems by iteration methods.— «Ап.

sti. Univ. lasi», 1985, sec. 1а, 31, № 3, р. 301—

306, fig. 2. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИ НЕЙ НЫХ АЛ ГЕБРАИЧЕС КИХ

УРАВНЕ НИ Й (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки сигналов для решения систем линейных уравнений.

Цель изобретения — сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство содержит и операционных блоков 5, где n — порядок системы линейных алгебраических уравнений, регистр

6 и блок 7 анализа. 1 з п. ф лы, 3 ил.

1633422

Формули и юбрeтeнuн

При описании работы устройства в обозначении x,"Ф первый индекс в скобках (k) указывает номер итерации, а второй индекс в скобках (i) -номер рекуррентного шага для k-й итерации.

Операционный блок 5 выполняет операцию умножения с накоплением. т.е. на информационные входы 10 — 12 подаются соответственно значения а, с и b, которые записываются соответственно в регистры 14 — 16 и на выходе сумматора 18 формируется значение с+аЬ, которое подается на выход

19.

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

) (ель изобретения — сокращение аппаратурных затрат.

На фиг. 1 представлена схема устройства; на фиг. 2 — схема операционного блока; на фиг. 3 — схема блока анализа.

Устройство для решения систем линейных алгебраических уравнений содержит входы коэффициентов системы линейных алгебраических уравнений устройства, вход 2 свободных членов системы линейных алгебраических уравнений устройства, вход 3 значения точности решения устройства, вход 4 синхронизации устройства, и операционных блоков 5, регистр 6, блок 7 анализа, выходы

8 результата решения устройства и выходы

9 признака окончания решения устройства.

Каждый операционный блок 5 содержит первый информационный вход 10 второй информационный вход 11, третий информационный вход 12, тактовый вход 13, с первого по третий регистры 14 — 16, умножитель

l7, сумматор 18, первый выход 19, второй выход 20.

Блок 7 анализа содержит первый информационный вход 21, второй информационный вход 22, тактовый вход 23, регистры 24 первой группы, регистры 25 второй группы, вычитатели 26, узлы 27 сравнения, первый и второй элементы И 28 и 29, триггер 30, группу выходов 31 и выход 32.

В основу работы устройства положен метод Зейделя нахождения корней х, системы линейных уравнений вида (Е---А)Х=В (Е— единичная матрица) по формуле х,=b„ i=-!.и фк3 ",. И-<)

v",= а„х, +Ха) х,+b„k= 1,2,... г / )а I

В приведенной формуле значения х, определяются рекуррентными соотношениями: и), (o) х, =b„ i= 1,п, k= 1,2,3,... (ЗФ-Ф) еч,(L) щь - ) 6„- fix+I, ) =i,п k=1,2,... а, „-„;.ц х,, „+, J = !, I 1, k = 1, 2,. х,=х,, i=1,п, k=1,2,3, (Kl uI) (в) .

4

Блок 7 анализа предназначен для определения точности вычисления значений

x, (i =1,n) и их выдачи на выходы 3)j блока

7. Точность вычисления определяется величиной е, постоянно подаваемой на вход 22.

При выполнении требуемой точности вычисления х; на выход 32 выдается сигнал окончания вычисления и с выходов 31, считываются все значения х,. Значения х, могут выдаваться последовательно на выход 31I блока 7. Точность вычисления v, определяется следующим образом. Значения х, подаются с выхода регистра 6 на вход 21 блока 7 через такт. Поэтому с целью сокращения числа регистров 24 и 25 блока 7 тактовые импульсы на входы записи-считывания регистров

24 и 25 подаются через такт (такая син хронизация обеспечивается счетным режимом работы триггера 30, который через такт открывает элемент И 29 для прохождения TBKToB6lx HMn) .1ьсов на ВхОды записисчитывания регистров 24 и 25). Записанные значения х, в регистр 25, и значения к,"" в регистр 24, подаются на Входы вычитателя 26„ где Определяется разность Лх, =

=х, " 4 х, ". На входы кзла 27, сравнения подаются разность Лх, и Величина е, задающая точность вычисления х, "" . Если /и,/е, то на выходе узла 27, сравнения будет единичный сигнал. При наличии единичных сигналов на выходе всех узлов 27 сравнения на выходе элемента И 28 сформируется единичный сигнал, который яв IHE. Toÿ признаком окончания вычисления значений к,.

1. Устройство для решения систем линейных алгебраических уравнений, содержащее п операционных блоков, где и — порядок системы линейных алгебраических уравнений, блок анализа и регистр, причем I-й Вход коэффициентов системы линейных алI åáðàèческих уравнений устройства (где =1, ..., и) подключе I к первому информационному Входу 1-го операционного блока, второй информационный вход k-го операционного блока (где k= l, ..., и — -1) подключен к первому выходу (k+! ) -го операционного блока, второй информационный вход и-го операционного блока подключен к входу коэффициентов системы линейных алгебраических уравнений устройства. вход синхронизации которого подключен к тактовым входам всех Операционных блоков, блока анализа и к входу записи-считывания регистра, информационный в.ход которого подключен к первому выходу первого операционного блока, выход регистра подключен к третьему информационному входу первого операционного блока, второй выход k-го операционного блока подключен к третьему информационному входу (k+1) -ro операционного блока, отличаюи ееея тем, что, с целью сокращения

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

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

10 информационным входам узлов сравнения с первого по п-й, вторые информационные входы которых подключены соответственно к выходам вычитателей с первого по Il-й, выходы узлов сравнения подключены соот15 ветственно к входам первого элемента И, выход которого подключен к выходу блока, тактовый вход которого подключен к первому входу второго элемента И и к счетному входу триггера, выход которого подключен к второму входу второго элемента И, выход

20 которого подключен к входам записи-считывания регистров первой и второй групп.

1633422

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

Редактор Е. Папп Техред А. Кравчук Корректор С. Шевкун

Заказ 618 Тираж 410 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР !! 3035, Москва, Ж вЂ” 35, Раушская наб., д. 4/о

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