Устройство для ll @ -разложения симметричных матриц

 

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

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

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

РЕСПУБЛИК (б1) 4 0 06 F 1 5/347

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

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

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

ПРИ П(НТ СССР

К АВТОРСК0МУ СВИДЕТЕЛЬСТВУ (21) 4338202/24-24 (22) 02.12.87 (46) 07.11.89, Бюл. h" 41 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Роман Выжиковски (РЬ), И.С.Каневский и О.В.Масленников (SU) (53) 681.32(088.8) (56) Авторское свидетельство СССР

В 1292008> кл. 1 06 F 15/347> 1985.

Валях F,. Последовательно-параллельные вычисления, — М.: Мир, 1985. с. 260-269.

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

Ф 1354206, кл. G 06 F 15/347, 1987.

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

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

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

Устройство содержит операционные блоки 1 ° P P первой группы (P = 1,N), „„SU„„1520542 А 1

2 (54). УСТРОЙСТВО ДЛЯ LL -РАЗЛОЖЕНИЯ

СИММЕТРИЧННХ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Целью изобретения является повышение производительности. Устройство содержит операционные блоки первой и второй групп и блок синхронизации. Поставленная цель достигается за счет одновременного разложения двух симметричных матриц. 4 ил. операционные блоки 1.P.q второй группы (Р = 1,N, q = Р,N), блок 2 синхронизации. Операционный блок первой группы содержит регистры 3-5, регистр

6 частного, блок 7 умножения-деления, вычитатель 8>коммутаторы 9-12 и управляницие входы 13-19.

Операционный блок второй группы содержит регистры 20-22, коммутатор

23, блок 24 деления — извлечения квад ратного корня, управляющие входы

25-27.

Блок синхронизации содержит генератор 28 синхроимпульсов, элемент

И 29, счетчик 30 и блок 3 1 памяти микрокоманд.

Устройство ис11 .11 зует для разложения симметричных 110JIoKHTBIIbHo определенных матриц А =: (а;;) алгоритм

Холецкого, в соотвгтс твии с которым

>11 11tE ляется такая нижняя треугольная

1>трица !. = (! „), что 1,L = А (где

1, — транс полированная матрица 1.): -1 — 1, 1 „

1!

) JJ

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

При этом одновременно реализуется разложение двух симметричных положи!

5 тельно определенных матриц А = (а! ) и В = (b; ) на треугольные матрицы

L = (1; ) и М = (гп,.>) соответственно, Устройство работает следующим образом.

Для простоты описания без потери общности положения N = 3. Условимся, что прием информации во все регистры осуществляется по заднеМу фронту синхроимпульса, т,е, в конце такта. Поступление исходных данных организовано следующим образом. На первый вход операционного блока 1. 1.q поступают элементы q строки матрицы

В и затем q-ro стобца матрицы А. 30

Строки подаются со сдвигом на один такт, т.е. элементы второй строки подаются, начиная с второго такта, третьей строки — начиная с третьего такта и т.д. 35

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

m,„ èý регистра 22 блока 1.1.1 переписывается s регистр 4 блока 1.1.2, пройдя через коммутатор 12 блока 45 !.1.2. Этот же элемент через коммутатор 9 блока 1.1.2 поступает на второй вход блока 7 операционного блока

1.1.2, на первый вход которого через коммутатор 10 блока 1.1.2. с первого 50 входа операционного блока поступает

Ь2„, блок ? операционного блока 1.1,2 выполняет деление, значение Ь2, /ш и

"= m 2 записывается в регистр 6 блока 1. 1.2. пройдя через коммутатор 55

11 блока 1.1.2 в регистр 3 блока

1.1.2. В этом же такте а „, поступает на первый вход блока 24 операционного блока 1.1.1, оН вьсполвяет операцию /х, и на его выходе получаем Га,„= 1 1, которое в конце такта записывается в регистры 20-22 блока

1.1.1.

В третьем такте m „ иэ регистра

4 блока 1. 1.2 переписывается в ре-! гистр 4 блока 1,1.3, а также через коммутатор 9 блока 1.1.3 поступает на второй вход блока 7 операционного блока 1.1.3,.на первый вход которого через .коммутатор 10 блока 1.1.3 с первого входа операционного блока

1.1.3 поступает Ъ,, блок 7 операционного блока 1.1 ° 3 выполняет деление, и значение Ъ, /m,„ m записывается в регистры 6 н 3 блока 1.1.3. В этом же такте т2, из регистра 6 блока 1. 1.2 переписывается в регистр

4 блока 1.1,2, а из регистра 3 блока

1.1.2 т „ переписывается (через коммутатор 23 блока 1 ° 2.2) в регистр

20 блока 1.2.2. Кроме того, из регистра 6 блока 1,1,2 ш 21 через коммутаторы 9 и 10 блока 1.1.2 поступает на оба входа блока 7 операционного блока 1.1.2, который выполняет умножение, а на второй вход вычитателя 8 блока 1.1.2 поступает b u с выхода вычитателя значение Ь 22

- m, принимается в регистр 3 блока

1.1.2. Кроме того, в третьем такте а „ поступает на первый вход блока

24 операционного блока 1,1.1, на второй вход которого иэ регистра 2 1 блока 1.1.2 поступает 1,, блок 24 операционного блока 1.1. 1 выполняет деление, и значение а „/1,„ = 1 записывается в регистры 5 блока

1.1 2, 20 и 22 блока 1.1.1. В четвертом такте m „ иэ регистра 3 блока 1. 1.3 поступает на второй вход вычитателя 8 блока 2.3, который делает пропуск операнда, и ш „ с выхода вычитателя записывается в регистр 3 блока 1.2.3. В этом же такте

m из регистра 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 Ь,, и полученное выражение Ь вЂ” m21ш р прини6 поступает аз, блок 7 операционного блока 1.1.2 выполняет умножение, и с выхода вычитателя 8 блока 1.1.2 значение а — 1, 1, записывается в

91 регистр 3 блока t.1.2. В этом же такте m из регистра 6 блока 1.1.3 переписывается в регистр 4 блока 1.1.3, а также поступает через коммутаторы

9 и 10 блока 1.1.3 на оба входа блока

7 операционного блока 1.1.3, а на второй вход вычитателя 8 блока 1.1.3 поступает Ь и с выхода вычитателя полученное значение b » — ш, приI нимается в регистр 3 блока . 1. 3.

В шестом такте m из регистра

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

m поступает на оба входа блока 7 операционного блока t.2.3, а на второй вход вычитателя 8 блока 1.2.3 из регистра 3 блока 1.1.3 поступает выражение b — m>, и с выхода вычи-. тателя полученное значение Ь вЂ” ш — m принимается в регистр 3 блока

1.2.3. Кроме того, из регистра 3 блока 1. t . 2 выражение а — 1 1 >, поступает на первый вход блока 24 операционного блока 1.2.2, на второй вход которого поступает из регистра

21 блока 1.2.2, блок 24 операционного блока 1.2.2 выполняет деление, и полученное выражение (а з — 1 „ 1 „) /

/1 = 1з принимается в регистры 20 блока 1 ° 2 ° 2, 22 блока 1.2.2 и 5 блока

1.2.3. В этом же такте 1 из регистра 5 блока 1.1.3 поступает на оба входа блока 7 операционного блока

1.1.3, на второй вход вычитателя 8 блока 1.1.3 поступает а, и с выхода вычитателя полученное значение а „ — 1",, принимается в регистр 3 блока 1.1.3.

В седьмом такте из регистра 3 бловыражение b» mз ш z .поступает на первый вход блока 24 операционного блока 1.3.3, он выполняет операцию !х, и полученное значение

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

Кроме того, Ьу — m, из регистра 3 блока 1.1.2 поступает на первый вход блока 24 операционного блока 1.2,2, который выполняет операцию х, и полученное значение е зз = З Ьз записывается в регистры 20 и 22 блока

1.2.2, в этом же такте из регистра

5 блока 1.1.2 поступает через комму- 1О таторы 9 и 10 блока 1.1.2 на оба входа блока 7 операционного блока 1.1.2, который выполняет умножение, на второй вход вычитателя 8 блока 1.1..2 поступает а, и с выхода вычитателя

8 блока 1. 1.2 выражение à zz — 1, принимается в регистр 3 блока 1.1.2.

В этом же такте m, из регистра 4 блока 1. 1.2 переписывается в регистр

4 блока 1.1.3, а 1, из регистра 22

20 блока 1.1.1 переписывается в регистр

4 блока 1.1.2 ° Кроме того, а „поступает на первый вход блока 24 операционного блока 1. 1. 1, на второй вход которого из регистра 21 блока 1.1.1

25 поступает 1 „, блок 24 операционного блока 1.1.1 выполняет деление, и значение а /1, 1, записывается в регистры 5 блока 1 ° 1.3, 20 и 22 блока

1.1.1. 30

В пятом такте m из регистра 3 блока 1.2.3 переписывается в регистр

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

m<> из регистра 22 блока 1.2.2 посту- 35 пает на второй вход блока 7 операционного блока 1.2.3, на первый вход которого из регистра 3 блока i.t.3 поступает Ь - т„m>,, блок 7 операцион .ного блока 1 .2.3 выполняет .деление, и 40 с его выхода выражение (Ь вЂ” m кт,) /m qz = m принимается в регистры 6 и 3 блока 1.2.3. В этом же такте из регистра 3 блока 1.1.2 выражение а — 1, = 1 поступает на 45 первый вход блока 24 операционного блока 1.2.2, который выполняет операцию (х, и полученное значение

a< — 1, = 1 записывается в

I регистры 20-22 блока 1.2.2 ° В этом же такте иэ регистра 22 блока 1.1.1

1, переписывается в регистр 4 блока

1.1.2, а также постуйает через коммутатор 9 блока 1.1.2 на второй вход блока 7 операционного блока 1.1.2, 55 на первый вход которого поступает иэ регистра 5 блока 1.1.2 1 „, а на второй вход вычитателя 8 блока 1.1.2 шзз з принимается в регистры 20 и 22 блока 1.3.3. В этом же такте 1 иэ регистра 5 блока 1.2.3 .поступает через .коммутаторы

9 и 10 блока 1.2.3 на оба входа блока 7 операционного блока 1,2.3, на второй вход вычитателя 8 блока 1.2.3 2. поступает выражение а ъ — 1з из ревходы группы первого операционного. блока с второго по пятый подключены соответственно к управляющему входу вычитателя, управляющему входу четвертого коммутатора, входу разрешения записи третьего регистра и первому управляющему входу первого коммутатора, второй управляющий вход которого соединен с первым управляющим входом второго коммутатора и подключен к шестому управляющему входу группы первого операционного блока, седьмой управляющий вход группы первого операционного блока подключен к второму управляющему входу второго коммута тора, причем в операционный блок второй группы дополнительно введены коммутатор, второй и третий регистры и блок выполнения операций деления-извлечения квадратного корня, причем первый вход операционного блока соединен с первым входом блока выполне10

2<) . 2 ния операциИ деления-извлеченил корня и с первым информационным входом коммутатора, выход которого соединен с информационным входом первого р»гистра, выход второго регистра является вторым входом блока выполнения операций деления-извлечения корня, выход которого соединен с информацион10 ными входами второго и третьего регистров, с вторым информационным входом коммутатора и является третьим выходом операционного блока, выход третьего регистра является вторым вы— ходом операционного блока, управляю15 щие входы группы с первого по третий ,.второго операционного блока подклю\ чены соответственно к управляющему входу коммутатора, входу разрешения .записи второго регистра и входу выбора режима блока деления-извлечения квадратного корня, фиг. 7

Составитель М.Силин

Техред Л.Сеодюкова Корректор О,Кравцова

Редактор О.Головач

Заказ 6760!51 Тираж 668 Подписное

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

tt ют

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