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

 

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

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

РЕС1ТУБЛИН

-SU 1644 > 60 А1 (51)5 Г 06 F 15/347, 15/324

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

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

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

IlO ИЗОБРЕТЕНИЯМ И OTHPbITHRM

ПРИ ГКНТ СССР (21) 4676095/24 (22) 11.04.89 (46) 23.04.91. Бвл. Р 15 (72) В.II.ßêóø, В.В.Косьянчук, Н.А.Лиходед, П.И.Соболевский и В.И.Мостовой (53) 681.3(088,8) (56) Авторское свидетельство СССР

Р 1509932, кл . С 06 F 15/347, 28.01.87.

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

Р 1444820, кл. С 06 F 15/347, 13.01 87. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ,ЛИНЕЙННХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специаличированных вычислительных машиИчобретение относится. к области вычислительной техники и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для решения систем линейных алгебраических уравнений.

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

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

2 нах и устройствах обработки сигналов. Цель изобретения — сокрашение объема оборудования . Устройство содержит n+1 вычислительных модулеи, где п — порядок системы линейных алгебраических уравнений. Первый вычислительный модуль содержит два регистра, узел вычисления обратной величины числа, умножитель, триггер, группу элементов И, два элемента И и элемент HF.. i-й вычислительный модуль (i = 2,п+1) содержит три регистра, узел задержки, умножитель, вычитатель, триггер, группу элементов И, два элемента И и элемент НЕ.

В основу работы устройства положена параллельно-поточная органиэация вычислений. 4 ил., 2 табл .

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

Устройство (фиг.1) содержит информационный вход 1, настроечный вход

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

Первый вычислительный модуль (фиг.3) содержит информационный вход

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

1644160

a„= а, ; i = 1,n, j = 1,n+1; (о)

<) 1-й шаг:

45 (I) (o) a« = 1/a«, (1

1) „(<1

II

50 — 2, и+1; а = a, j =2, и+1; (

2-й шаг: (01 (

< д 1/агг<

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

i-й вичислительный модуль (i = 2, n + 1) (фиг.4) содержит первый информационный вход 21, второй информационный нход 22, синхровход 23, настроечный вход 24, регистры 25-27, узел

28 задержки, умножитель 29, нычитатель 30, триггер 31, группу элементов 10

И 32, элемент HE 33, элементы И 34 и

35, регистры 36 (i = 1,2п-2), первый информационный внход 37, второй информационный выход 38, третий инфор-. мационный выход 39 и настроечный 15 выход 40.

При описании работы устройства н обозначении а. индекс К в скобках (к) указывает номер рекуррентного шага, а н обозначении ищiекса а без скобок — Zp номер такта работы устройства.

На информационный вход 1 устройства подавтся последовательно данные по строкам в соответствии с табл.1.

Первый элемент первой строки подается 25 на (и+1)-м такте, затем последовательно подавтся остальные элементы первой строки, затем подавтся последовательно элементы второй строки и т.д. На настроечный вход 3 на первом 30 такте подается разряд 1, затем 2п раз подавтся разряды О, затем последовательно единичный разряд и 2п нулевых разрядов и т.д. ."-<начение Х (а 3 n»I формируется 35

ni

I в 5j-м вычислйтельном модуле (j

1,n) íà (Yn + < + 1)-м такте.

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

О-й шаг:

"l (« ° = 3 +1, гг 2 ) (<) () (г) а ° — a . .° а °, i = 3, п+1, << г г1 а(г) г) (г) а.; «

= 3, и+1; (g) (г) а)< г аг ) = 3, и+1;

ЫЧ- 7) и-й шаг: («- <1

1/ (nl (n- <1 а - а

«и )«<»< (n- <) (n-<) (nl

an

<) <н «j а пп (nl

<<<и < а

<) 1 = и+1, 2п-19 j = и+1; (ll) (nl г«,n»< nn<.I (ni

Х=a,,<=1,п.

«<, >li+< <

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

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

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

В первом режиме на !»астроечный вход 24 подается единичный разряд, а на информационный вход 21 — элемент а. При этом элемент И 34 открывается и н регистр 25 записывается элемент

1 а,триггер 31 устанавливается в еди1644160

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

1О

25

45 ничное состояние, закрывая группу элементов И 3?. Ro втором режиме на вход 24 подается нулевой разряд, на вход 21 — элемент и,на вход 22— элемент с. На выходе элемента HF. 33 формируется единичный сигнал, который открывает элемент И 35, в регистр

26 записывается элемент Ъ, а в регистр 27 — элемент с. Триггер 3 1 устанавливается в нулевое состояние,на инверсном выходе которого единичный сигнал открывает группу элементов

И 32. На выходе умножителя 29 формируется значение а ° с, а на выходе вычитателя 30 — значение Ь вЂ” асс, которое через открытую группу элементов И 32 подается на выход 38, а на выход 39 значение b — ас подается . через узел 28 задержки с задержкой на 2п — 2 тактов.

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

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

В соответствии с табл.1 для п = 3 элементы первой строки последовательно подаются на вход 1 с 7-ro по 10-й такты, элементы второй строки — с

13-ro по 16-й такты, элементы третьей строки с 19-ro по 21-й такты.

Элемент а „записывается в регистр (o)

10 первого вычислительного модуля на 22-м такте. На 22-м такте в первом вычислительном модуле (ормируется значение R )g R 12 1/B 11 . С это 40

О (о) (o го такта начинается вычислительный процесс в соответствии с приведенными рекуррентными соотношениями. формируемые значения на последуюших тактах работы устройства приведены в табл.?. На 38-м такте в вычислительном модуле 5< *ормируется,значе(ъ) (21 (2) ние Х! = а44 = а44 — а4ъ ° а 4

= а, которое подае(ся на выход 6 () устройства, на 39-м такте в вычислительном модуле 5 формируется значение Х = à" = а ()) = а — а()" а (3) 64 4 %4 %з ЪФ . = a+4, которое подается на выход 6 устройства, и на 40-м такте в вычислительном модуле 5 > формируется значениеХ =a =0- (-1-а ) =а () (1! (М

3 64 )4 Ъ которое подается на выход 6> устройства. Последнее значение Х ) формируется Hà (Y п + п + 1) -м такте.

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

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

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

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

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

1644160

Таблица 1

Позиция s строке и+2 и+1 и и+1

Стро

1i2 и+ 2 ... 2п 2п+1

1 О О а«, аI.„+I

a«aIq

2 О 0

3 0 О а я, О

О О аи ааз °

Л 34 а < а12 а4! и О и+1 -1 и+2 -1

О О

О О

О, О

aII,п а а,п«

О О

О О а h1n-i

О

aII,II-з an,II-а

0 О

О О а III

О

О О

О О

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

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

И, о т л и ч а ю щ е е с я тем, что, с целью сокращения объема оборудования, в первый вычислительный модуль введены узел вычисления обратной величины числа и умножитель, в i-й вычислительный модуль введен узел задержки, причем в первом вычислительном модуле выход первого регистра подключен к входу узла вычисления обратной величины числа, выход которого .подключен к первому входу умножителя,второй вход которого подключен к выходу второго регистра, а выходк второму входу группы элементов И, в i-м вычислительном модуле выход группы элементов И подключен к информационному входу узла задержки, информационный выход которого подключен к третьему информационному выходу -ro вычислительного модуля, синхровход которого подключен к синхровходу узла задержки, при этом узел задержки i-ro вычислительного модуля содержит 7п-2 регистров, информационный вход узла задержки подключен к информационному входу пер5 ного регистра, выход 1-rn регистра (1 = 1, 2п-3) подключен к информационному входу (1+1)-го регистра, выход (2n-2)-го регистра подключен к информационному выходу узла задержки, синхровход которого подключен к синхровходам всех регистров, информационный вход устройства подключен к первому информационному входу (n+1}-ro вычислительного мо15 дуля, настроечный вход устройства подключен к настроечному входу первого вычислительного модуля, информационный вход которого подключен к третьему информационному выходу второго вычислительного модуля, первый информационный вход j-го вычислительного модуля (j = 2,n) подключен к третьему информационному выхо25 ду (j+1)-ro вычислительного модуля, информационный выход первого вычислительного модуля подключен к второму информационному входу второго вычислительного модуля, настроечный выход первого вычислительного модуля подключен к настроечному входу второго вычислительного модуля, первый информационный выход 1-ro вычислительного модуля подключен к второму ин35 формационному входу (j+1)-го вычислительного модуля, второй информационный выход k-ro вычислительного модуля (k = 2,n+1) подключен к k-му выходу устройства.

164ч16(> д и ца 2

Т а б

Ь<уЗО г 7

Pr278ыуаО г2

Рг 2

Рг2 выуЗ г2 г о (о

0 о а«

«а а<г

9о а, (< o а«

Qz<

<З О а

< ай а

ОД по агг о а„ а,„о а ., а„

О О до

+

<г

g

gf> p

Azz аф. о а" а го о г(о а"

О 0

0 О а„ аз«

О О а«

0 0 о о о о

Q з<0, 2<О

О О ргг а<г

О >5 0 а«а,< а а«

27 0 а,>r

0 4< "<

0 о о а<з а" г.o а«0

<- гг - 0 о о о 0

a„o

0 аз<"

0 0 а аг<

Юг " г1 зоо

0 о-я" о 0 агг а.зз © гз

З20 а,„а,„

<<) О азг< агг О а < а ьга о

О 0

- о О

0 ага<

0 айаг

0 0

0 аза

0 азг о о с б

0 0

О 0

0 0

0 О

0 а, аз

) азу«<;0

0 а.«ь

0 О

О -1 а аз азз 1 .0 о а,<з о 0 о. 0 або

0 Q

vo а» О

TA 2

49а л у

Фь

Pr (О .Рс ((<2<<<о< р «о а«< о агг:аz

aä « . 0 аи<; 0 а зз .бг з<

ИН З Рггу а<а аг< а<з«> а

a<<< <> o rr абаз Q аг аа<<г< <гзг<

< з а«з и 2ь Pr27

a„"; О а.„о аг< а<Р а" <7э"

О 0 O

О О 0 а а» о о а, о о о О О

О о 0 0 а„-о а,, о

О a." о о о о

О О О 0 аз г а.<г а„

Мз а<з< а, -/ аз

0 О 0

О 0 О о o G ачба G. <газ -(о с а о о 0

Gs йз«аиду о о о диой лдаае< yeeOg /

1644160 дхадмю щи)( элененвоб Ц) 2 аиа3

Фиг.4

Составитель К.Кухаренко

ТехРед Л,Сердюкова Корректор Н.Ревская

Редактор Г.Бельская

Заказ 1462 Тираж 422 Подписное

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

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

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