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

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

Цель изобретения - сокращение объема оборудования устройства.

На фиг.1 представлена структурная схема устройства; на фиг.2 - структурная схема устройства для п 3 (п - порядок системы); на фиг.З - функциональная схема первого вычислительного модуля; на фиг.4 - функциональная схема 1-го вычислительного модуля (, п+1).

Организация входного потока дан- ных приведена в табл.1.

Устройство (фиг.1) содержит информационный вход 1, настроечный вход 2, синхровход 3, первый вычислительный модуль 4, второй - (п+1)-й вычи- слительные модули , информационные выходы 6; устройства.

Первый вычислительный модуль (фиг.З) содержит информационный вход 7, настроечный вход 8, синхровход 9, регистры 10 и 11, узел 12 вычисления обратной величины числа, умножитель 13, триггер 14, группу элементов , элементы И 16 и 17, элемент

ОЭ 4Ь 4

в

О

НЕ 18, информационный выход 19 и настроечный выход 20.

i-й вычислительный модуль (i 2, п + 1) (фиг.4) содержит первый инфор- мационный вход 21, второй информационный вход 22, синхровход 23, настроечный вход 24, регистры 25-27, узел 28 задержки, умножитель 29, вычита- тель 30, триггер 31, группу элементов И 32, элемент НЕ 33, элементы И 34 и 35, регистры 36 (i 1,2n-2), первый информационный выход 37, второй информационный выход 38, третий инфор-. мационный выход 39 и настроечный выход 40.

При описании работы устройства в обозначении а индекс К в скобках указывает номер рекуррентного шага, а в обозначении индекса а без скобок - номер такта работы устройства.

На информационный вход 1 устройства подаются последовательно данные по строкам в соответствии с табл.1. Первый элемент первой строки подается на (п-Н)-м такте, затем последовательно подаются остальные элементы первой строки, затем подаются последовательно элементы второй строки и т.д. На настроечный вход 3 на первом такте подается разряд 1, затем 2п раз подаются разряды 0, затем последовательно единичный разряд и 2п нулевых разрядов, и т.д.

Значение Х ( п+) ) формируется в 5J-M вычислительном модуле (j 1,п) на (Vn + j + 1)-м такте.

В основу работы устройства положен метод Гаусса-Жордана, который задается рекуррентными соотношениями:

0-й таг:

a.Y a;j ; i 1 ,n, j 1,n+1;

1-й шаг:

0) 1 , to) a t / a «

°4l - «;; . i-..

.,-{-..

j 2.П-И;

nli.i -a ,. J -2. „+1; 2-й шаг:

a ll 1/ a22

J ) j

i n+1, 2n-1, j n+1;

W ,

a

{«) nni-i

X - я (n

,П4,

i 1, n.

5 о

с

о

5

0

5

Первый вычислительный модуль (фиг.З) работает в двух режимах, которые задаются единичным и нулевым разрядами на настроечном входе 8.

В первом режиме на i-м такте на вход 8 подается единичный разряд, а на информационный вход 7 - элемент а. При этом элемент И 16 открывается и по заднему фронту тактового импульса в регистр 10 записывается элемент а. Триггер 14 устанавливается в единичное состояние. Во втором режиме на (i+D-м такте на вход 8 подается нулевой разряд, на вход 7 - элемент Ь. На выходе элемента НЕ 18 формируется единичный сигнал, который открывает элемент И 17 и в регистр 11 записывается элемент Ь.Триггер 14 устанавливается в нулевое состояние, с инверсного выхода которого единичный сигнал открывает группу элементов И 15. На выходе узла вычисления обратной величины числа 12 формируется значение 1/а, на выходе умножителя 13 - значение b/а, которое через группу элементов И 15 подается на выход 19.

i-й вычислительный модуль (фиг.4) работает также в двух режимах.

В первом режиме на настроечный вход 24 подается единичный разряд, а на информационный вход 21 - элемент а. При этом элемент И 34 открывается и в регистр 25 записывается элемент а,триггер - 31 устанавливается в едиичное состояние, закрывая группу лементов И 32. Во втором режиме на ход 24 подается нулевой разряд, а вход 21 - элемент и .на вход 22 - лемент с. На выходе элемента НЕ 33 ормируется единичный сигнал, котоый открывает элемент И 35, в регистр 26 записывается элемент Ь, а в регистр 27 - элемент с. Триггер 31 устанавливается в нулевое состояние,на нверсном выходе которого единичный сигнал открывает группу элементов И 32. На выходе умножителя 29 формируется значение а«с, а на выходе вы- читателя 30 - значение b - а.с, которое через открытую группу элементов И 32 подается на выход 38, а на выход 39 значение b - ас подается через узел 28 задержки1 с задержкой на 2п - 2 тактов.

Рассмотрим работу устройства для случая п 3 (фиг.2).

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

В соответствии с табл.1 для п 3 элементы первой строки последовательно подаются на вход 1 с 7-го по 10-й такты, элементы второй строки - с 13-го по 16-й такты, элементы третьей строки с 19-го по 21-й такты. Элемент а записывается в регистр 10 первого вычислительного модуля на 22-м такте. На 22-м такте в первом вычислительном модуле формируется значение а а(. С этого такта начинается вычислительный процесс в соответствии с приведенными рекуррентными соотношениями. ормируемые значения на последующих тактах работы устройства приведены в табл.2. На 38-м такте в вычислительном модуле 5 Лорнируется значе & - я(. „V

ние X „W

а

4

14

44

144

45

4

которое подается на выход 61 устройства, на 39-м такте в вычислительном модуле 5 формируется значение Хл

т

о

94

«)

54

« - ™

У4

1«

аЙ

г4

которое подается на выход 6,

10

15

20

25

30

35

устройства, и на 40-м такте в вычислительном модуле 5, формируется значе- -г

/1 . , . Ml, l, JJ

ние

X, а« - 0 - (-1 -а) , которое подается на выход 6 устройства. Последнее значение Х формируется на (Y п + п + 1)-м такте.

дд

45

50

о

р м у л а

и

6

я о

бретения

Устройство для решения систем линейных алгебраических уравнений, содержащее п+1 вычислительных модулей (п - порядок системы), причем первый вычиелительный модуль содержит два регистра, триггер, группу элементов И, два элемента И и элемент НЕ, i-й вычислительный модуль (, п+1) содержит три регистра, умножитель, вычитатель, триггер, группу элементов И, два элемента И, элемент НЕ, синхровход устройства подключен

р

20

25

30

35

JJ

к синхровходам всех вычислительных модулей, при этом информационный вход первого вычислительного модуля подключен к информационным входам первого и второго регистров, выход первого элемента И подключен к син- хровходу первого регистра, а выход второго элемента И - к .синхровходу второго регистра, настроечный вход первого вычислительного модуля подключен к информационному входу триггера, к первому входу первого элемента И и к входу элемента НЕ, выход которого подключен к первому входу второго элемента И, информационный выход первого вычислительного модуля подключен к выходу группы элементов И, первый вход которой подключен к инверсному выходу триггера, прямой выход которого подключен к настроечному выходу первого вычислительного модуля, синхровход которого подключен к синхровходу триггера и к вторым входам первого и второго элементов

дд И, первый информационный вход 1-го вычислительного модуля подключен к информационным входам первого и второго регистров, настроечный вход 1-го вычислительного модуля подклю45 чен к информационному входу триггера, к первому входу первого элемента И и к входу элемента НЕ, выход которого подключен к первому входу второго элемента И, выход которого

50 подключен к синхровходу второго регистра, а выход первого элемента И подключен к синхровходу первого регистра, выход которого подключен к первому входу умножителя, второй вход которого подключен к выходу третьего регистра, а выход - к первому входу вычитателя, второй вход которого подключен к выходу второго регистра, а выход - к первому входу

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

o

S

0

5

0

5

узел задержки 1-го вычислительного модуля содержит 2п-2 регистров, информационный вход узла задержки подключен к информационному входу первого регистра, выход 1-го регистра (, 2п-3) подключен к информационному входу (l-H)-ro регистра, выход (2п-2)-го регистра подключен к информационному выходу узла задержки, синхровход которого подключен к синхровходам всех регистров, информационный вход устройства подключен к первому информационному входу (п-И)-го вычислительного модуля, настроечный вход устройства подключен к настроечному входу первого вычислительного модуля, информационный вход которого подключен к третьему информационному выходу второго вычислительного модуля, первый информационный вход j-ro вычислительного модуля (j 2,п) подключен к третьему информационному выхо- ДУ (j+O-го вычислительного модуля, информационный выход первого вычислительного модуля подключен к второму информационному входу второго вычисли тельного модуля, настроечный выход первого вычислительного модуля подключен к настроечному входу второго вычислительного модуля, первый информационный выход j-ro вычислительного модуля подключен к второму информационному входу (j+1)-ro вычислительного модуля, второй информационный выходk-ro вычислительного модуля (k 2,n+1) подключен к k-му выходу устройства.

Таблица 1

О -1 -1

аг О

О

ап,н-э а п.и-г ап,п ап,гн( 00000

00000

О

о о

о

J V U

V3«уЗЗ„40

/

v« AJ

Ж.

Z5

. . it

23

30 Й

22

1

27

Входной nomok элементов O(J

kb

U

уЗЗ„40

/

v« AJ

Фиг. 2

Si

26

f%h-H-J

т 28

«Л

J7