Устройство для треугольного разложения ленточных матриц Советский патент 1990 года по МПК G06F17/16 

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

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

На фиг.1 представлена структурная схема устройства для треугольного разложения ласточных матриц;на фиг.2 - структурная схема (p,k)-ro вычислительно го модуля (р 1,f, k 2,uj, о f + h + 1, f и h - соответственно число под- и наддиаго- .нальных элементов матрицы);на фиг.3-.

структурная схема (р,1)-го вычислительного модуля; на фиг.4 - порядок ввода и вьшода элементов матрицы для случая f 2, h , 1 .

Устроство для треугольного разложения ленточных матриц содержит (фиг.1) матрицу (p,q) (где q 1,w) вычислительных модулей 1-p-q и генератор синхроимпульсов (не показан), выход которого подключен к синхро- входам всех вычислительных модулей.

Вычислительньй модуль l-p-k (фиг.2) содержит умножитель 2, второй регистр 3, первый мультиплексор 4, первый регистр 5, второй мультиплексор

СЛ

00

1

СЛ

6, D-триггер 7, третий регистр 8 и сумматор 9.

Вычислительный модуль 1 р 1 (фиг.З) содержит первый регистр 10, схему 11 сравнения, первьй 12 и второй 13 мультиплексоры, D-триггер 14, второй регистр 15, инвертор 16 и де- лчтель 17.

Устройство для треугольного раз- лсжения ленточных матриц предназначено для выполнения первой фазы решени системы линейных алгебраических уравнений Ах Ь (где X и b - N - мерные векторы столбцы, а А - ленточная ма- трица N-ro порядка) методом исключения Гаусса - прямого исключения, которое состоит в нахождении такой нижней треугольной матрицы L, котора преобразует матрицу А в верхнюю тре- угольную матрицу и, т.е. U . Преобразование ленточной Гатрицы А . Сэ if с шириной ленты Ш f+h+1 , где f и h - число соответственно под- и надциагональных элементов ма- триды А, выполняется по алгоритму исключения Гаусса с локальным выбором главного (ведущего) элемента.

Локальный выбор ведущего элемента предполагает, что исключение эле- мента aji на i-м шаге алгоритма Гаусса (i 1,h-1), j i+1, j+f) предшествует сравнение элементов а .. и a(j-;);, причем, если I а.; / (а jf то осуществялется перестановка j-й и (з-1)-й строк. Затем производится пр образование j-й строки путем поэлементного вычитания из нее (з-1)-й строки, умноженной на коэффициент

a. j/afj.ijj Ijt- противном случа перестановка строк не производится. Таким образом в качестве ведущего при исключении элемента а . используется теперь максимальньи по абсо-- лютней величине элемент i-ro столбца, расположенньй в .строках от (j - 1)-й до j-й включительно. При этом все происходящие перестановки строк запоминаются и выдаются (в качестве нижней треугольной матрицы перестановок V Ujj) дпя дальнейшего использования.

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

Положим , u)4, , условимся, что прием информации во все регистры и триггеры осуществляются по заднему фронту синхроимпульса, , в конце такта все триггеры и

to }5 20 5

о

0

5

0

5

регистры перед началом вычисления устанавливаются в нулевое состояние. Обозначим aj элемент а . на i-м шаге вычислений.

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

В первом такте на первые входы вычислительных модулей 1.1.1-1.1.4 поступают (фиг.4) соответственно 0,0, а, , 0. Мультиплексор 6.1.3 пропускает а,, на вход сумматора 9.1.3, а с выхода мультиплексора 4.1.3 на вход умножителя 2.1.3 выдается нуль из регистра 8.1.4, ив конце первого такта а записывается в регистр 8.1.3.

Во втором такте а, и пают на первые входы вычислительных модулей - соответственно 1.1.2 и 1.1.4 и в конце такта записьшаются в регистры 8.1.2 и 8.1.4 соответственно. В регистр 5.1.2 через мультиплексор 4.1.2 переписьюается а из регистра 8.1 .3.

В третьем такте на первые входы вычислительных модулей 1.1.1 и 1.1.3 поступают соответственно элементы а, и а2. а J, сравнивается в схеме сравнения 11.1.1 с а, . Пусть в нашем случае (а,, ,J. Тогда нуль с выхода схемы сравнения записывается в триггер 14.1.2 и поступает на управляющие входы мультиплексоров 12.1.1 и 13.1.1, которые пропускают на свои выходы соответственно а, и а-, В делителе 17.1.1 вычисляется частное (,) и записьгаается в регистр 15.1.1. В регистр 10.1.2 записывается aj,j в регистр 8.2.2 через мультиплексор 6.2.2 и сумматор 9.2.2 из регистра 5.1.2 переписывается а,, . В регистр 8.1.3 записьтается а -j.

В четвертом такте на первые входы вычислительных модулей 1.1.2 и 1.1.4 поступают .соответственно а « и а... На первый и второй входы схемы 11.2.1 сравнения поступают соответственно а 2, и а, . Пусть |а , , | . Тогда единица с выхода схемы 11.2.1 сравнения переключает D-триггер 14.2.1 и мультиплексоры 12.2.1 и 13.2.1, которые пропускают на свои выходы соответственно а, и а,. В делителе 17.2.1 вычисляется (-а,,/а,) и запи- сьшается в регистр 15.2.1. В регистр 10.21 записывается а,г U,, и поступает Hd первый пыход первой группы выходов устройства.

В этом же такте (-a3f/a2,) перепиэлемент матрицы перестановок Vj, О, На первьй выход третьей группы выхо,. . . дов устройства поступает L, , /

сывается из регистра 15.1.1 в регистр /а. С первого входа вычислительно- 3.1.2 и поступает на второй вход ум-...

ножителя, на первый вход которого из регистра 8.1.3 через мультиплексор 4.1.2 поступает а 2г записывает ,-. .

го модуля 1.1.4 элемента а., через

3t- ся также в регистр 5.1.2. Результат умножения (-а21-аэ,/а J,) суммируется с а

и а

(

32

21

32 - 3

21

-аэ,/а

записьшается в регистр 8.1.2, в регистр 8.1.4 - а,23, в 5.1.3 - a,i.

В пятом также в умножителе 2.2.2 вычисляется (-а. а „/а ) , в сумматоре 9.2.2

а 11 11

а,,/а.

которое записывается в регистр 8.2.2 D-триггер 7.2.2, переключается единичным сигналом с выхода D- триггера 14.2.1, а,записывается в регистр 5.2.2 и и, а поступает на второй выход первой группы выходов устройства. В схеме 11.1.1 сравнения сравниваются si- Пусть 25 |а I 7(а J2 I тогда единица с выхода схемы сравнения записывается в D-триггер 14.1.1, а также поступает на управляющие входы мультиплексоров Т2.1.1 и 13.1.1, которые пропускают на свои выходы соответственно а, . В делителе 17.i. 1 вычисляется (-а /а, ). В регистры

А f -4лл Г-лл

сумматор 9.1.4 и мультиплексор 6.1.4 записывается в регистр 8.1.4.

В этом же такте в вычислительном to модуле 1.2.3 вычисления

(-а

21ВОЙ группы выходов устройства через

регистр 5.2.3 поступает U j ajj. В вычислительном модуле 1.1.2 формируется элемент а и записьгоается в регистр 8.1.2. В ре- 21,гистры 5.1.2 и 5.1.4 записываются

соответственно а, и нуль.

Далее элементы матриц U, L и V 20 формируются аналогичным образом.

«

) на третий выход пер15

Ф о р м у л

изобретени

30

10.1.1 и 15.1.1 записьшается соот1. Устройство для треугольного разложения ленточных матриц, содержащее f СО вычислительных модулей ( о; f+h+1,fHh- соответственно число под- и наддиагольных элементов матрицы), отличающееся тем, что, с целью сокращения аппаратурных затрат, i-й вход первой группы информационных входов устройства подключен к первому информационному входу (1,i)-го вычислительного моду- 35 ля (i 1,w), i-й выход первой группы выходов устройства подключен к первому выходу (f,i)-ro вычислительного модуля, первый информационный вход (J,i)-ro вычислительного модуля, 40 (J 2,f) подключен к первому выходу (J 1 i)-ro вычислительного модуля, второй и третий информационные входы ()гр вычислительного модуля (р 1,f, q 2,ui подключены соответ- 45 ственно к второму и третьему выходам (p,q-1)-го вычислительного модуля, а второй и третий выходы (р, (х))-го вычислительного модуля являются р-ми выходами соответственно 50 второй и третьей групп выходов устройства, второй информационный вход (р,1)го вычислительного модуля подключен к четвертому выходу (р,2)-го вычислительного модуля, четвертый 55 информационный вход (р,со)-го вычислительного модуля является р-м входом второй группы информационных входов устройства, а четвертый информационный вход (р, t)-ro вычисливетственно а

и -а

/а

В этом

, 42

же такте нуль из П-триггера 7.1.2 переписьюается в D-триггер 7.1.3 .поступает на первый вход вычислтельного модуля 1.1.3 ив этом вычислительном модуле вычисляется элемент а зэ а 33- а .,,. ..,,, которы записьюается в регистр 8.1.3. Элемент а,, записывается в регистр 5.1.3.

В шестом такте схеме 11.2.1 сравнения сравниваются а и . Пусть ( f. Тогда нуль с выхода схемы 11.2.1 сравнения записьшается в триггер 14.2.1, а мультиплексоры 12.2.1 и 13.2.1 пропускают на выходы соответственно а .а. В делителе вычисляется (), а на пер- вьй выход первой группы устройства из регистра 10.2.1 поступает Ujj

гг

в этом же такте нуль из D-триг- гера 7,1.3 переписьшается в D-триггер 7.1,4, и на первьй выход второй группы выходов устройства поступает

элемент матрицы перестановок Vj, О, На первьй выход третьей группы выхор /а. С первого входа вычислительно- ...

,-. .

го модуля 1.1.4 элемента а., через

3t-

25

сумматор 9.1.4 и мультиплексор 6.1.4 записывается в регистр 8.1.4.

В этом же такте в вычислительном to модуле 1.2.3 вычисления

(-а

ВОЙ группы выходов устройства через

регистр 5.2.3 поступает U j ajj. В вычислительном модуле 1.1.2 формируется элемент а и записьгоается в регистр 8.1.2. В ре- ,гистры 5.1.2 и 5.1.4 записываются

соответственно а, и нуль.

Далее элементы матриц U, L и V 20 формируются аналогичным образом.

«

) на третий выход пер15

Ф о р м у л

изобретени

25

30

1. Устройство для треугольного разложения ленточных матриц, содержащее f СО вычислительных модулей ( о; f+h+1,fHh- соответственно число под- и наддиагольных элементов матрицы), отличающееся тем, что, с целью сокращения аппаратурных затрат, i-й вход первой группы информационных входов устройства подключен к первому информационному входу (1,i)-го вычислительного моду- 5 ля (i 1,w), i-й выход первой группы выходов устройства подключен к первому выходу (f,i)-ro вычислительного модуля, первый информационный вход (J,i)-ro вычислительного модуля, 0 (J 2,f) подключен к первому выходу (J 1 i)-ro вычислительного модуля, второй и третий информационные входы ()гр вычислительного модуля (р 1,f, q 2,ui подключены соответ- 5 ственно к второму и третьему выходам (p,q-1)-го вычислительного модуля, а второй и третий выходы (р, (х))-го вычислительного модуля являются р-ми выходами соответственно 0 второй и третьей групп выходов устройства, второй информационный вход (р,1)го вычислительного модуля подключен к четвертому выходу (р,2)-го вычислительного модуля, четвертый 5 информационный вход (р,со)-го вычислительного модуля является р-м входом второй группы информационных входов устройства, а четвертый информационный вход (р, t)-ro вычисли

тельного модуля (f. 2, ) подключен к четвертому выходу (р, 1+1)-го вычислительного модуля, синхровход, устройства подключен к синхровходам всех вычислительных модулей.

2. Устройство по П.1. о т л и - ч а .ю щ е е с я тем, что (p,q)-й вычислительный модуль содержит умножитель, сумматор, два мультиплексора, три регистра и D-триггер, причем первьй информационный вход вычислительного модуля подключен к первым информационным входам первого и второго мультиплексоров, выходы которых подключены к первым входам соответственно умножителя и сумматора,первы выход вычислительного модуля подклю- чен к выходу первого регистра, информационный вход которого подключе к выходу первого мультиплексора, управляющий вход которого соединен с управляющим входом второго мультиплексора и информационным входом D-триг гера, второй и третий информационные входы вычислительного модуля подключены к информационным входам D-триггера и второго регистра, выходы которых являются соответственно вторым и третьим выходами вычислительного модуля,четвертый информационный вход которого подключен к вторым информационным входам первого и второго мультиплексоров, информационный вход второго регистра подключен к второму входу умножителя, выход которого подключен к второму входу сумматора, выход которого подключен к информационному входу третьего регистра, выход которого явля-

0

5

о о

5

0

5

ется четвертым выходом вычислительного модуля, синхровход которого подключен к синхровходам всех регистров и D-триггера.

3. Устройство по П.1, отличающееся тем, что (р,1)-й вычислительный модуль содержит два регистра, два мультиплексора, схему сравнения, делитель, инвертор и D- триггер, причем первые информационные входы первого и второго мультиплексоров соединены с первым входом схемы сравнения и с первым информационным входом вычислительного модуля, первый выход которого соединен с выходом первого регистра, информационный вход которого подключен к вьпсоду первого мультиплексора, первому входу делителя и -входу инвертора, выход которого соединен с входом обну рения второго регистра, информационный вход которого соединен с выходом делителя, второй вход которого соединен с выходом второго мультиплексора, второй информационный вход которого соединен с вторым информационным входом второго мультиплексора, вторым входом схемы сравнения и вторым информационным входом вычислительного модуля, второй и третий выходы которого соединен с выходами соответственно D-триггера и второго регистра, выход схемы сравнения подключен к управляющим входам мультиплексоров и входу В-триггера, синхровход вычислительного модуля подключен к синхровходам всех регистров и D-триггера.

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Цель изобретения - сокращение аппаратурных затрат. Устройство выполняет первую фазу решения системы алгебраических уравнений AX = B (где X и B N - мерные векторы

A - ленточная матрица порядка N), которая состоит в отыскании нижне-и верхнетреугольных матриц L и V, таких, что V = L . A. Преобразование выполняется методом исключения Гаусса - прямого исключения с локальным выбором ведущего элемента. Перестановки строк запоминаются и выдаются в виде матрицы перестановок V. Особенностью работы устройства является параллельно-поточная организация вычислений в матрице вычислительных модулей двух типов. 2 з.п. ф-лы, 4 ил.

l.f.c

0

Ю

t г

Фиг. 2

l.p.1

;4

75

/3

77

HF

uaJ

w г;

(7

(7

tr,2 (5;

г. 7,

li. «2 j; n Ю9 8 f 6