Устройство для разбиения матриц Советский патент 1987 года по МПК G06F17/16 

в регистр 3.1.2, элемент а

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

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

На фиг. 1 представле.на функциональная схема устройства; на фиг. 2 и 3 - примеры функциональных схем вычислительных блоков; на фиг. 4 - функциональная схема блока управле- ния; на фиг. 5 блок-схема алгорит- 15 в регистр 13.1.1. ма функционирования устройства.

Устройство содержит вычислительный блок 1 и блок 2 синхронизации. Вычислительный блок 1, представленный на фиг. 2, содержит первый 3 и второй 4 регистры, арифметическое устройство 5, коммутатор 6, сумматор 7, третий регистр 8 и группу с первого по четвертый входов 9-12 синхронизации. Вычислительный блок 1, представленный на.фиг. 3, содержит регистр 13 и вход 1.4 синхронизации.

Блок 2 синхронизации, представленный на фиг. 4, содержит генератор 15 импульсов, элемент И 16, счетчик 17, блок 18 постоянной памяти и входы 19-23 синхронизации.

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

ка 1 первой строки поступает М-й столбец разбиваемой матрицы А. .

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

В первом такте элемент aj° прини- 10 мается в регистр 13.1.1, причем

„Со1 1

(0)

Во втором такте элемент а„ принимается в регистр 4.1.2, элемент а, (1

21

1.1 со)

В третьем такте элемент а,, принимается в регистр 4,1.3, элемент а,° - в регистр 3.1.3. Арифметическое устройство 5.1.2 выполняет деление и на 20 его выходе получают частное а /а„ и, , которое в конце такта записывается в регистр 8.1.2. В конце такта

в регистр 4.1.2 принимается элемент (о) -,,-, ()

в регистр 3.1.2 - элемент а

гг

21 1п

25 а В регистр 13.1.1 - элемент а,, 1,. В четвертом такте на выходе сумматора 7.1.2 получают величину а - а Г/-а;: a j; , которая в конце такта будет принята в регистр

30 13.2.2. Элемент а , будет записан в регистр 4.1.4, элемент а,,, - в ре- : гистр 3.1.4, элемент а, в регистр 4.1.3, элемент a°j - в регистр 3, 1.3.

Арифметическое устройство 5.1.3 вы- Устройство предназначено для раз- 35 полняет деление и с его выхода част- биения квадратной матрицы А размер- ное /а°, U,,, принимается в ре,гистр 8.1.3. Б регистры 4.1.2 и и 3.1.2 будут приняты элементы а.

ности Р на две треугольные: нижнюю левую L и верхнюю правую U такие, что LU а, причем на главной ди,аго- нали матрицы U стоят единицы. Преобразование матрицы А а,.: Т выполняется по алгоритму исключения Гаусса, в процессе которого получаются элементы 1- и Uj.

5(

И Язг. соответственно, а в регистр 40 13.1..1 - элемент а, l,.

В пятом такте элемент а принимается в регистр 4,2.3, элемент а,

(о) (о) / (о (оЧгэ

. а, - а, /а „ а с выхода сумматора 3.1.3 - в регистр 3.2.3. На выхо- 45 де сумматора 7.1.2 получают величи- я .° -

а : М

(К-1)

а Ч

а;

где ,2,...,Р, i,,K+2,...,P;

и

1. iK iK

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

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

в регистр 13.1.1.

начиная с третьего такта, и т.д.

В первом такте элемент aj° прини- мается в регистр 13.1.1, причем

„Со1 1

(0)

Во втором такте элемент а„ принимается в регистр 4.1.2, элемент а, (1

21

1.1 в регистр 13.1.1.

со)

В третьем такте элемент а,, принимается в регистр 4,1.3, элемент а,° - в регистр 3.1.3. Арифметическое устройство 5.1.2 выполняет деление и на его выходе получают частное а /а„ и, , которое в конце такта записывается в регистр 8.1.2. В конце такта

в регистр 4.1.2 принимается элемент (о) -,,-, ()

в регистр 3.1.2 - элемент а

гг

21 1п

а В регистр 13.1.1 - элемент а,, 1,. В четвертом такте на выходе сумматора 7.1.2 получают величину а - а Г/-а;: a j; , которая в конце такта будет принята в регистр

13.2.2. Элемент а , будет записан в регистр 4.1.4, элемент а,,, - в ре- : гистр 3.1.4, элемент а, в регистр 4.1.3, элемент a°j - в регистр 3, 1.3.

Арифметическое устройство 5.1.3 вы- полняет деление и с его выхода част- ное /а°, U,,, принимается в ре,гистр 8.1.3. Б регистры 4.1.2 и и 3.1.2 будут приняты элементы а.

5(

И Язг. соответственно, а в регистр 0 13.1..1 - элемент а, l,.

В пятом такте элемент а принимается в регистр 4,2.3, элемент а,

(о) (о) / (о (оЧгэ ,

. а, - а, /а „ а с выхода сумматора 3.1.3 - в регистр 3.2.3. На выхо- 5 де сумматора 7.1.2 получают величи- я .° -

ну а.

я

1г

,(о1 . 1 ъ .2

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

(01 I (о) ,.

Q частное а, /а„ , которое записывается в регистр 8.1.4. Элемент

принимается в регистр 4.1.4, элемент ал. - в регистр 3.1.4, элемент

col / 1 о(01

а , - в регистр 4.1.3, элемент а,, g в регистр 3 . 1.3, элементы и в регистры 4.1.2 и 3.1.2 соответственно.

В шестом такте, элемент а

О)

22; принимается в регистр 4.2.4, в регистр

3.2.4 принимается элемент а

.t°

Д

(О

14

(О) / lU

а - а,/а„ а у с выхода сумматора 7.1.4. Арифметическое устройство 5.2.3 выполняет деление и частное

ау, /a V U-j записывается

гъ

ijj

- li

,(

в регистр

8.2.3. Элемент а принимается в регистр 4;2.3, а в регистр 3.2.3 с выхода сумматора 7.1.3 принимается элемент а , а, - ,1 а,, . На выходе сумматора 7.1.2 получают эле,( - .w .w /яto) / а „

мент а

41

41

41

а 1

а 4, J.42

который принимается в регистр 13.2.2. ,Со ,.

Ь

И а , записываются в

13,p.q., а элементы матрицы U хранятся в регистрах S.p.q.

Поскольку каждый элемент входной J- матрицы А используется в каждом данном процессорном элементе только один раз, можно выполнять HJ-разло- жение потока матриц. Каждую следующую матрицу можно начинать подавать с 10 N+1-го такта после начала подачи предыдущей матрицы.

Блок 2 синхронизации работает следующим образом. По сигналу пуска счетчик 17 устанавливается в Нулевое

но,

и - в регистрегистры 4.1.4 и 3.1.4 соответствен- 15 состояние и открывается элемент 16,

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

ры 4.1.3 и З.КЗ соответственно.

В седьмом такте на. выходе сумматора 7.2.3 получают элемент а Л

.( 1г

м

гг

.) г 1,, «оторый 20

будет принят в регистр 13.3.3. Арифметическое устройство 5.2.4 выполняет

деление и частное U,

124

J24 записывается в регистр 8.2.4, элемент

, I

а,,2 - в регистр 4.2.4. В регистр

25

3.2.4 с выхода сумматора 7.1.4 при-,

а

нимается элемент а Л (01

иа,, , в регистр 4.2.3 - элемент а

чо

м

(1)

а в регистр 3.2.3 - элемент ai,

(01 (01 / (О)tOl (О)

- - а,„/а„ а, . Элементы а, и

(0

ч

Мг

п

30

принимаются в регистры 4.1.4 и

3.1.4.

В восьмом такте элемент а мается в регистр 4.3.4

(2)

, прини- а элемент

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

1. Устройство для разбиения матриц, содержащее матрицу из Р строк по (Р+1-К) вычислительных блоков в Каждой строке (где Р - порядок разбиваемой матрицы, К 1,. . ., Р - порядковый номер строки матрицы)и блок синхронизации, выходы синхронизации К-й группы которого подключены к группе входов синхронизации всех выi t-b - Ji- t;irt i -T..- jei jic:i c;ni

дС2 дС1) (О / (О W „.rsfnrra числительных блоков К-Й строки 3+ 24 32 ВЫХОДа СуМ- gg

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

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

3.3.4. На выходе сумматора 7.2.3 получают элемент а;, в. 1 - а а

Чз г 41 -Ъ который записывается в регистр 13.3.3. Элемент

принима-

ется в регистр 4.2.4, а элемент а

(о) 10)

М4

74

/4°i

а

f 1

44

С выхода сумматора 7.1.4 - в регистр 3.2.4.

В девятом такте арифметическое устройство 5.3.4 выполняет деление и частное U, принимается в регистр 8.3.4. Элемент при

нимается в регистр 4.3.4, а элемент

Д) f

,о

44

- а

CD 24

(О

с выхода сумматора 7.2.4 - в регистр 3.3.4 В десятом такте с выхода сумматора 7.3.4 элемент

44

„К)

/а,, X

- принимается в регистр 13.4.4.

На этом разложение квадратной матрицы А Га, размерности N 4 заканчивается. Элементы матрицы L последовательно принимались в регистры

542064

13,p.q., а элементы матрицы U хранятся в регистрах S.p.q.

Поскольку каждый элемент входной J- матрицы А используется в каждом данном процессорном элементе только один раз, можно выполнять HJ-разло- жение потока матриц. Каждую следующую матрицу можно начинать подавать с 10 N+1-го такта после начала подачи предыдущей матрицы.

Блок 2 синхронизации работает следующим образом. По сигналу пуска счетчик 17 устанавливается в Нулевое

25

30

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

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

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

2. Устройство по П.1, отличающееся тем, что Ы-й вычислйтельный блок (М } К-й строки матрицы содержит три регистра, арифметическое устройство, коммутатор и сумматор , причем первый вход синхронизации группы вычислительного блока подключен к входам признака записи первого и второго |1егистров, первый информационный вход вычислительного блока подключен к информационному входу первого регистра, выход которого подключен к первому информационному .входу коммутатора и к входу первого слагаемого сумматора, выход которого является первым информационным выходом вычислительного блока, второй информационный вход вычислительного блока подключен к информационному входу второго регистра, выход которого подключен к входу первого операнда арифметического устройства и является вторым информационным выходом вычислительного блока,.второй вход синхронизации группы вычислительного блока подключен к входу признака запуси ре- тистра, Третий вход синхронизации

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

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

9u2.2

Фиг. Ч

/t

QOi/e.J

3.fl. 2Q,p.(i

21.Р.Ч 22.

23.p.il

.-. t -I

rTflTij I r , rr I

Д- //. . ,. r/

7д-«.rJ.-T iA-J .e;j ; tfrt.f.tr.-.,,; Prtf. i.t а г ,: Л- f tfr .. li

Л 1,1л, гУ, - a - aj;V,r --

frit,,., j, .(ff3.r.

« .лJ. - a ii; a/l /

fl-.J. ag /4 «/

Л-«.r;. fr3.

:Л-«г. о-« ,

I

Рг.г. - off; i-r i - ffris-rt :--a ;i a ;{.4 i/a ; -a , iit: tfrl.i.t-t: . a ,f/ai u,.; Pr. J. и; /v.r.J fr3. ag ; Pr r.l --a t ,.f.

5

««.. Pre.j. -ui

fr}.}. aJif аи -

frl..i, aiJ; oiy-ai . eij /e -ef/;

«- W.Z7.- aj . СЙ -аЙ /а;; .а|. „; frf.l.« :-aff; Pr}.i.: tfrtt. гаУ,; /v...- a

/W

Рл W. J.. aJJ aW- aff/йй . a,7.. „ ; fr S.H :- a L/a K t, Я/-. . ffS. аи - ajj ; Яг.;.- л/-./.: .J. ей - аи - aSVa/; . aJ7; ./..-

Т

«Ч.- a ,t йЯ /а/Г a,7; Дг w... аи -- ag- .-t«;

РгЗ. г.4. аД С W - «VfJ. Д-Чг.

I

.4. /V,Jt.«.- s

/ л/ J.4.- r . a

Pr ts.0.4.::flf аЛ - « У г0 -г у. i+

ВИНИЛИ Заказ 5695/44

fui.S

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4

|.

/W

Тираж 671 Подписное

Изобретение относится к вычислительной технике, и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Целью изобретения является сокращение аппаратурных затрат. Устройство содержит вычислительный блок 1 и блок 2 синхронизации и позволяет разбить квадратную матрицу А на две треугольные: нижнюю левую L и верхнюю правую и, такие, что L U А, причем на главной диагонали матрицы и стоят единицы. Преобразование осуществляется по алгоритму исключения Гаусса. Устройство может быть использовано и для разложения потока матриц. 2 з.п. ф-лы, 5 ил. (Л 00 сд 4 ю о а: