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

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

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

На фиг. 1 дана схема устройства; на фиг. 2 - функциональная схема (Р,Р) операционного блока второй группы (Р 1,N)j на фиг. 3 - функциональная схема (P,q)-ro операционного блока первой группы, Р 1,N, q P,N; на фиг. 4 - пример реализации блока синхронизации.

Устройство содержит операционные блоки 1.Р.Р первой группы (Р 1,N),

операционные блоки 1.P.q второй группы (Р 1,N, q P,N), блок 2 синхронизации. Операционный блок первой группы содержит регистры 3-5, регистр 6 частного, блок 7 у гаожения-деления, вычитатель 8jKOMMyTaTopu 9-12 и уп- . равлякнцие входы 13-19.

Операционный блок второй группы содержит регистры 20-22, коммутатор 23, блок 24 деления - извлечения квадратного корня, управляющие входы 25-27.

Блок синхронизации содержит генератор 28 синхроимпульсов, элемент И 29, счетчик 30 и блок 31 памяти микрокоманд.

Устройство исттп.чьзует для разложения симметричных иолоткительно определенных матриц А - a;jl алгоритм Холецкого, в соотве гс:твии с которым

ел to

о ел

4

to

П л1 п1сг яется такля нижняя треугольная мтгриця L - 1 ;; что LL А (где I, - трянгпониронаннай матрица L): J-1

°ч- 1. iV

i-1

- 1 V--1

К,

где i - 1 , . . . , N; j . 1 , . , . , (N- 1) .

При этом одновременно реализуется разложение двух симметричных полотки- тельно определенных матриц А (а ) и В (h;j) на треугольные матрицы L ( ) и М (.) соответственно.

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

образом.

Для простоты описания без потери общности положения N 3. Условимся, что прием информации во все регистры осуществляется по заднему Фронту синхроимпульса, т.е. в конце такта. Поступление исходных данных организовано следующим образом. На первый вход операционного блока 1.1. поступают элементы q строки матрицы В и затем q-ro стобца матрицы А. Строки подаются со сдвигом на один такт, т.е. элементы второй строки подаются, начиная с второго такта, третьей строки - начиная с третьего такта и т.д.

В первом такте элемент b поступает на первый вход блока 24 операционного блока 1,1.19 который выполз няет операцию /х j и на его выходе получаем m ,, , которое в кон- це такта записывается в регистры 20 и 22 блока 1.1.1. Во втором такте

m

11

из регистра 22 блока 1.1.1 переписывается в регистр 4 блока 1.1.2, пройдя через коммутатор 12 блока 1.1.2. Этот же элемент через коммутатор 9 блока 1.1а2 поступает на второй вход блока 7 операционного блока 1.1.2, на первый вход которого через коммутатор 10 блока 1.1.2. с первого входа операщюнного блока поступает Ь , блок 7 операционного блока 1.1.2 выполняет деление, значение bj,/т ,, т, записывается в регистр 6 блока 1.1.2, пройдя через коммутатор 11 блока 1.1.2 в регистр 3 блока 1.1.2. В этом же такте а ,, поступает на первый вход блока 24 операцион

ного 6jTOKa 1.1.1, он выполняе рацию /X , и на его выходе получае т 1р , которое в конце такта записывается в регистры 20-22 блока 1.1.1.

В третьем такте из регистра 4 блока 1.1.2 переписывается в ре- 1гистр 4 блока 1.1.3, а также через кoм yтaтop 9 блока 1.1.3 поступает на второй вход блока 7 операгщонного блока 1 .1 .3, на первый вход которого через -коммутатор 10 блока 1.1.3 с первого входа операдаонного блока 1.1.3 поступает Ь, , блок 7 операцион ного блока 1.1.3 выполняет деление, и значение Ъ /т э записывается в регистры 6 и 3 блока 1.1.3. В

0

5

5

0

5 0 5

этом же такте m

1

из регистра 6

блока 1.1.2 переписывается в регистр 4 блока 1.1.2, а из регистра 3 блока 1.1.2 переписывается (через коммутатор 23 блока 1.2.2) в регистр 20 блока 1.2.2. Кроме того, из регистра 6 блока 1.1.2 через коммутаторы 9 и 10 блока 1-.1.2 поступает на оба входа блока 7 операционного блока 1.1.2, который выполняет умножение, а на второй вход вычита- теля 8 блока 1.1.2 поступает b и с выхода вычитателя значение bjj - Год, принимается в регистр 3 блока 1.1.2. Кроме того, в третьем такте поступает на первый вход блока 24 операционного блока 1.1.1, на второй вход которого из регистра 21 блока 1.1,2 поступает 1 , блок 24 операционного блока 1.1.1 выполняет деление, и значение а,/

zi ti

-21

записывается в регистры 5 блока 1.1.2, 20 и 22 блока 1.1.1. В четвертом такте rij, из регистра 3 блока 1.1.3 поступает на второй вход вычитателя 8 блока 2.3, который делает пропуск операнда, и т,, с выхода вычитателя записьгоается в регистр 3 блока 1.2.3. В этом же такте т, из регистра 4 блока 1.1.2 через коммутатор 9 блока 1.1.3 поступает на второй вход блока 7 операционного блока 1.1.3, на первый вход которого поступает т, из регистра 6 блока 1.1.3, блок 7 операционного блока 1.1.3 вьшол- няет умножение,полученное выражение поступает на первый вход вычитателя 8 блока 1.1,3, на второй вход которого поступает с первого входа операгщонного блока 1,1.3 bj,, и полученное выражение Ь - , принимается в регистр

блока 3 блока

2

152054 1.1.3

Кроме того, bj 71 регистра 3 блока 1.1,2 поступает на первый вход

J6noKa 24 операционного блока 1.2,2, « который выполняет операцию Ух , и полученное значение m V Ь mfi записывается в регистры 20 и 22 блока 1.2.2, в этом же такте из регистра 5 блока 1,1,2 поступает через комму- О

таторы 9 и 10 блока 1.1,2 на оба вко- да блока 7 операционного блока 1.1.2, который выполняет умножение, на второй вход вмчитателя 8 блока 1.1,2 поступает , и с выхода вычитателя 8 блока 1.1,2 выражение г принимается в регистр 3 блока 1.1.2. В этом же такте т, из регистра 4 блока 1.1.2 переписывается в регистр 4 блока 1.1.3, а 1, из регистра 22 блока 1.1.1 переписывается в регистр 4 блока 1.1,2. Кроме того, а 31 поступает на первый вход блока 24 операционного блока 1.1.1J на второй вход которого из регистра 21 блока 1.1.1 поступает 1,, , блок 24 операционного блока 1.1,1 выполняет деление, и знапоступает азг, блок 7 операционного блока 1.1.2 выполняет умножение, И с выхода вычитателя 8 блока 1.1.2 значение а - In 1 э 1 записывается в регистр 3 блока Т, 1.2. В этом же так те т, из регистра 6 блока 1.1.3 пе реписывается в регистр 4 блока 1.1.3 а также поступает через коммутаторы 9 и 10 блока 1.1.3 на оба входа блок 7 операционного блока 1.1,3, а на второй вход вычитателя 8 блока 1.1,3 поступает b

33

и

с выхода вычитателя полученное значение b э ai При15

20

31

I

нимается в регистр 3 блока 1.1.3.

В шестом такте т, из регистра 3 блока 1,2.3 переписьгоается в регистр 20 блока 1.3,3, пройдя через коммутатор 23 блока 1.3,3, В этом же такте из регистра 6 блока 1.2.3 m J2 поступает на оба входа блока 7 операционного блока 1.2,3, а на второй вход вычитателя 8 блока 1.2.3 из регистра 3 блока 1.1.3 поступает выражение b,-m , ис выхода вычи-.

чение а

3

/1

-if

Э1

записывается в

регистры 5 блока 1.1,3, 20 и 22 блока 1.1.1.30

В пятом такте т, из регистра 3

33 э

тателя полученное значение b ,, - iTij-j принимается в регистр 3 блока 1.2.3, Кроме того, из регистра 3 блока 1.1.2 выражение а .j - , поступает на первый вход блока 24 операционного блока 1,2.2, на второй вход которого поступает из регистра 21 блока 1.2.2, блок 24 операционного блока 1.2.2 выполняет деление, и

j из регистра

блока 1.2.3 переписывается в регистр 20 блока 1.3.3, пройдя через коммутатор 23 блока 1.3.3. В этом же такте

т из регистра 22 блока 1,2.2 посту- 35 полученное выражение (а пает -на второй вход блока 7 операцион- з принимается в регистры 20 ного блока 1.2.3, на первый вход которого из регистра 3 блока 1.1.3 постуЗг -и 3v /

блока 1,2.2, 22 блока 1.2.2 и 5 блок 1.2.3. В этом же такте 1 j из регист

2054

« О

6

поступает азг, блок 7 операционного блока 1.1.2 выполняет умножение, И с выхода вычитателя 8 блока 1.1.2 значение а - In 1 э 1 записывается в регистр 3 блока Т, 1.2. В этом же такте т, из регистра 6 блока 1.1.3 переписывается в регистр 4 блока 1.1.3, а также поступает через коммутаторы 9 и 10 блока 1.1.3 на оба входа блока 7 операционного блока 1.1,3, а на второй вход вычитателя 8 блока 1.1,3 поступает b

33

и

с выхода вычитателя полученное значение b э ai При15

20

31

I

нимается в регистр 3 блока 1.1.3.

В шестом такте т, из регистра 3 блока 1,2.3 переписьгоается в регистр 20 блока 1.3,3, пройдя через коммутатор 23 блока 1.3,3, В этом же такте из регистра 6 блока 1.2.3 m J2 поступает на оба входа блока 7 операционного блока 1.2,3, а на второй вход вычитателя 8 блока 1.2.3 из регистра 3 блока 1.1.3 поступает выражение b,-m , ис выхода вычи-.

30

33 э

тателя полученное значение b ,, - iTij-j принимается в регистр 3 блока 1.2.3, Кроме того, из регистра 3 блока 1.1.2 выражение а .j - , поступает на первый вход блока 24 операционного блока 1,2.2, на второй вход которого поступает из регистра 21 блока 1.2.2, блок 24 операционного блока 1.2.2 выполняет деление, и

регистры 20

Зг -и 3v /

полученное выражение (а з принимается в регистры 20

блока 1,2.2, 22 блока 1.2.2 и 5 блока 1.2.3. В этом же такте 1 j из регист

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

пает b

31

- m.

блок 7 операцион- ра 5 блока 1.1.3 поступает на оба

ного блока Т.2.3 выполняет деление, и 40 входа блока 7 операционного блока

1-1

с его выхода выражение ( -т хт j,) m л принимается в регистры 6 и 3 блока 1.2.3, В этом же такте из регистра 3 блока 1.1.2 выражение 1, Ij поступает на первый вход блока 24 операционного блока 1.2.2, который выполняет операцию УзГ , и полученное значение

. -1

-II

1-г

записывается в

регистры 20-22 блока 1.2.2. В этом же такте из регистра 22 блока 1.1.1 Ij переписывается в регистр 4 блока 1.1.2,-а также поступает через коммутатор 9 блока 1,1.2 на второй вход блока 7 операционного блока 1.1.2, на первый вход которого поступает из регистра 5 блока 1,1.2 , а на второй вход вычитателя 8 блока 1.1.2

- 1

31

принимается в регистр 3

5 блока 1.1.3.

В седьмом такте из регистра 3 блока 1.2.3 выражение bj, - m, - . поступает на первый вход блока 24 операционного блока 1.3.3, он вьтолняет

0 операцию , и полученное значение

-/Т

m

3

зэ

2

- тз1

i Шэг

принимается

5

в регистры 20 и 22 блока 1.3.3. В этом же такте 1 из регистра 5 блока 1.2.3 поступает через .коммутаторы 9 и to блока 1.2.3 на оба входа блока 7 операционного блока 1.2.3, на второй вход вычитателя 8 блока 1.2,3 поступает выражение агъ Iji из регистра 3 блока 1,1.2 и с выхода вычи тателя полученное значение а33 д4 - 1з1 принимается в регистр 3 блока 1.2сЗ, И, наконец, в восьмом такте выражение я- 1 - 1 из регистра 3 блока 1.2.3 поступает на первый вход блока 24 onepajjT oHHoro. блока 1.3.3jOH выполняет операцию /x , И

полученное значение Г 33 1

-1

J-3t

1зг принимается в регистры 20, 22 и 21 блока 1.1.3.

На этом разложение матриц А и В размерности N 3 заканчивается. Элементы матриц L и М последовательно выдаются из регистров 20.р.р.

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

Устройство для LL -разложения CVM метричных матриц;, содержащее блок синхронизациИуН(Ы-1)У2 операционных блоков первой группы и N операционных блоков второй группы, где N - размерность матрицы, причем группы выходов блока синхронизации подключены к группам управляющих входов всех операционных блоков первой и второй групп, первый информационный вход устройства подключен к первому входу 1,1-го операционного блока вто рой группы, первый вход 1, К-го опе- ращ онного блока первой, группы под- к К-му информационному входу устройства (К 2.N), первый, вход и к,К-го операционного блока второй группы подключены соответственно к вькоду (К-1,К)-Го операционного блока второй группы и к К-му выходу устройства (К 2,N) выход 1,1-го операционного блока второй группы подключен к первому выходу устройства, первый вход (Р+1,К)-го операционного блока первой группы подключен к первому выходу Р,К-го операционного блока первой группы (Р 1,N-2, К Р + 2,Ю, второй выход Р,К-го операционного блока перво группы подключен к второму входу (Р,К+1)-го операционного блока перво группы (Р r,lF2, К Р+1, N-1), второй выход Р,Р-го операционного блока второй группы подключен к второму входу (Р,Р+1)-го операционного блока первой группы (Р 1,М-1),операционный блок первой группы содержит первый и второй регистры,-регистр частного, блок умножения-деления, вычитатель и первый коммутатор, при

5

0

5

0

5

0

5

0

5

чем выход блока умножения-деления подключен к первому входу вычитатг-л г и информационному входу регистра частного, выход которого соединен с первым информационным входом первого коммутатора, операционный блок второй группы содержит первый регистр, выход которого лодкяючен к первому выходу операгщонного блока, отличающееся тем, что, с целью повышения производительности за счет одновременного разложения двух симметричных матриц, третий выход Р,Р-го операционного блока второй группы подключен к третьим входам Р,К-х опера- ционных блоков первой группы (Р 1,N-1, К P+1,N), причем в операционный блок первой группы дополни- тельно введены третий регистр и три коммутатора, первый вход операционного блока подключен к первому информационному входу второго коммутатора и к второму входу вычитателя, выход которого соединен.с первым информационным входом третьего коммутатора, выход которого соединен с информационным входом первого ре.гистра, выход которого является первым выходом операционного блока, второй вход операционного блока соединен с первым ни-; формационн ым входом четвертого коммутатора и с вторым информационным входом первого коммутатора, выход которого подключен к второму входу блока умножения-деления, выход второго коммутатора является первым входом блока умножения-деления, выход которого соединен с вторым информационным входом третьего коммутатора, третий вход операционного блока подключен к информационному входу третьего регистра, выход которого подключен к третьему информационному входу первого коммутатора и второму информационному входу второго комму-татора, а выход регистра частного соединен с третьим входом второго коммутатора и с вторым входом четвертого коммутатора, выход которого подключен к входу второго регистра, выход которого является вторьш выходом операционного блока, первый управляю1ЕЩй вход группы первого операционного блока подключен к управляющему входу блока умножения- деления, входу разрешения записи регистра частного, управляющему входу третьего коммутатора, управляющие

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

5

0

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

фуг. /

Фа.

Составитель М.Силин Редактор О.Голорач Техред Л.Сеодюкова Корректор О.Кравцова

Заказ 6760/51

Тираж 668

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

Г

гз

io

зг

Фat.V

Подписное