Устройство для lu - разложения матриц

 

Изобретение относится к вычислительной технике, предназначено для LV-разложения матриц и может быть использовано при построении специализированных устройств, предназначенных для решения различных матричных задач. Целью изобретения является повышение быстродействия за счет реорганизации структуры устройства. Устройство содержит матрицу N<SP POS="POST">.</SP>N (N - размерность обрабатываемых матриц) вычислительных модулей и блок синхронизации, синхровход, вход управления, группу информационных входов и группу выходов. В основу работы устройства положен алгоритм исключения Гаусса. Особенностью функционирования устройства является параллельно-поточная организация вычислений. 7 ил.

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

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

РЕСПУБЛИК (я)л G 06 F 15/347

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4487470/24 (22) 28.09.88 (46) 07.07.91, Бюл. № 25 (72) А.п. Царев и И,И. Чебан (53) 681,32(088.8) (56) Авторское свидетельство СССР № 1354206, кл. G 06 F 15/347, 1986, Авторское свидетельство СССР

¹ 1575205, кл. G 06 F 15/347, 18.08.88. (54) УСТРОЙСТВО ДЛЯ LU-РАЗЛОЖЕНИЯ

МАТРИЦ (57) Изобретение относится к вычислительной технике, предназначено для LU-разложения матриц и может быть использовано

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем уравнений, обращения матриц, Цель изобретения — повышение быстродействия, На фиг. 1 приведена структурная схема устройства для LU-разложения матриц; на фиг. 2 — схема (i, 1)-ro вычислительного модуля О=1, N — 1; N — размерность обрабатываемых матриц); на фиг. 3 — схема 1, J)-ro вычислительного модуля (J=2, N-1; на фиг. 4 — схема (k, ))-ro вычислительного модуля (k=2, N — 1); на фиг. 5 — схема (N, 1)-го вычислительного модуля; на фиг. 6 — схема (1, N)-го вычислительного модуля; на фиг. 7 — схема (n,m)-ro вычислительного модуля (n=2,N при m=N; m=2, N — 1 при n=N). Устройство содержит матрицу (NxN) вычислительных модулей 1, блок 2 синхронизации. синхровход 3, вход 4 управления, группу информационных входов 5, группу

„„ЯЯ„„1661793 А1 при построении специализированных устройств, предназначенных для решения различных матричных задач. Целью изобретения является повышение быстродействия эа счет реорганизации структуры устройства. Устройство содержит матрицу NxN (N— размерность обрабатываемых матриц) вычислительных модулей и блок синхронизации, синхровход, вход управления, группу информационных входов и группу выходов.

В основу работы устройства положен алгоритм исключения Гаусса, Особенность функционирования устройства является параллельно-поточная организация вычислений. 7 ил. выходов 6, мультиплексоры 7, регистры 8, делитель 9, умножитель 10 и сумматор 11. (i, 1)-й вычислительный модуль (фиг. 2) и (N, 1)-й вычислительный модуль (фиг, 5) име- ф ют вторые входы (не обозначены), подключенные к выходам регистров 8. (1, J)-й (фиг. 3) и (1, N)-й (фиг. 6) вычислительные модули имеют третьи инфор- О .мационные входы и вторые выходы (не обозначены), подключенные соответствен- в но к входам знаменателя и выходам соответствующих делителей 9. О (К ) -й вычислительный модуль (фиг. 4) имеет третий и четвертый (информационные входы (не обозначены), подключенные соответственно к первому и второму входам умножителя 10.

° Э (n, m)-й вычислительный модуль имеет второй и третий информационные входы (не показаны), подключенные соответственно к первому и второму входам сумматора 11, .Блок 2 синхронизации может быть выполнен, например, в виде N-разрядного

1661793

2142

3211

1332

1213

Il 2

0 1 -1о -40 0 I и!2

0 0 0 1 а o o 0

ЪЦ2 О O

5/г 26 0

3/д 14 27/ц счетчика, работающего в режиме счета синхроимпульсов. На выход блока синхронизации выдается и1", когда содержимое счетчика равно 1, во всех остальных случаях на выходе блока синхронизации н0", Устройство предназначено для разбиения квадратной матрицы А порядка N на две треугольные: нижнюю левую L и верхнюю правую lA, такие, что LU--A, причем на главной диагонали матрицы U стоят единицы, Преобразование матрицы А=(а!!) выполняется по алгоритму исключения Гаусса, в процессе которого получаются элементы lil u Uii матриц L u U на основе рекуррентных формул! вЂ

1!! = а —, » 1ь щ; (1 J );

s =1

1 ) — 1 оц = — (ац — » 1! щ ); (I < J ) .

s =1

Рассмотрим работу устройства на примере разбиения произвольной матрицы четвертого порядка

Искомые матрицы L и U, удовлетворяющие LU=A, будут:

На первом такте работы устройства в вычислительные модули 1!1, где!!=1,4, с входов 5!! в регистры 8 принимаются элементы

aij матрицы А, В вычислительных модулях

11,г, 11,3, 11,4 происходит деление содержимого регистров 8!! на содержимое регистра

811. На выходах делителей 9 вычислительных модулей 1>,г, 1>,з, 11,4 получаются числа

1/2, 2,1. В вычислительных модулях 1ii, где

iJ=2,4, происходит перемножение чисел, поступивших из вычислительных модулей 1п и

111, затем это произведение в сумматоре

11 отнимается от содержимого регистра 8 данного вычислительного модуля 1 !. Таким образом, на выходах сумматоров 11 вы.числительных модулей 1г,г, 1г,3, 1г,4, 1з,г, 13,3 13,4 14,г 14,3, 14,4 получаются числа 1/2, -5, -2, 5/2, 1,1, 3/2, -1,2, с выходов 61,1, бг,1, 6з,1, 64,1 считываются элементы 1м, 1г1, 1з1, 14! первого столбца матрицы L2, 3, 1, 1, с выходов 6>,г, 6i,з, 61;4 считываются элементы 0!г, 013, 014 первой строки матрицы U 1/2, 2, 1.

На втором такте с выходов 6ii, где J=2,4, в регистры 8 вычислительных модулей

1!-ц-1 принимаются элементы 1/2, — 5, — 2, 5/2, 1,1, 3/2, — 1,2. После аналогичных дей5 ствий, как на первом такте, на выходах делителей 9 вычислительных модулей 11,г, 1i,3 получаются числа -10, — 4, на выходах сумматоров 11 в вычислительных модулях

1г,г, 1г,з, 1з,г, 1з,з — числа 26, 11, 14, 8. С

10 выходов 61,1, бг,1, 63,1 считываются элементы 122, 1зг, 142 второго столбца матрицы L

1/2,5/2, 3/2, с выходов 6> г, 61,з считываются элементы Огз, 0га второй матрицы

u — - 10, -4.

15 На третьем такте с выходов 6г,г, 6г,3, 6з,г, 6з,з, в регистры 8 вычислительных модулей 11,1 11,г 1г,1 1г,г принимаются элементы 26, 11, 14 и 8. Затем на выходе делителя

9 вычислительного модуля получается чис20 ло 11/26, на выходе сумматора 11 вычислительного модуля 1г,г получается число

27/13. С выходов 61,1, бг,1 считываются элементы Iзз и 14з третьего столбца матрицы L

26 и 14, с выхода 61,г считывается элемент

25 034 третьей строки матрицы U 11/26, На четвертом такте с выхода 6г,г в регистр

8вычислительного модуля 11,1 записывается элемент 27/13 и затем с выхода 61.i считывается последний искомый элемент

30 144=27/13, Таким образом, после четырех тактов получены все элементы искомых матриц L u

Ц, удовлетворяющих LU=A.

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

5 Устройство для LU-разложения матриц, содержащее матрицу NxN вычислительных модулей (N — размерность обрабатываемых матриц) и блок синхронизации, вход которого является синхровходом устройства, 40 группу выходов которого образуют первые выходы (п,m)-х вычислительных модулей (п=1,N при m=1; m=2,N при n=1), входы управления и синхровходы которых подключены соответственно к выходу и входу блока

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

50 входами управления (I,k)-x вычислительных модулей (I.k=2,N-1), первые информеиионные входы всех вычислительных модулей образуют группу информационных входов устройства, первый выход (i,j)-ro вычис55 лительного модуля подключен к второму информационному входу (1-1,J — 1)-ro вычислительного модуля, второй выход (р, 1)-ro вычислительного модуля подключен к третьему информационном входу (р, !)-го вычислительного модуля (р-1, N 1) и к второ1661793 му информационному входу (р,N)-го вычислительного модуля, второй выход (N,1)-го вычислительного модуля подключен к второму информационному входу (N,l)-ro вычислительного модуля, третий информационный вход которого соединен с четвертыми информационными входами (k,l) x вычислительных модулей и с вторым выходом (1,l)-го вычислительного модуля, второй выход (N, 1)-ro вычислительного модуля соединен так же с вторым информационным входом (N,N)-го вычислительного модуля, 5 третий информационный вход которого соединен с третьими информационными входами (k,N)-õ и вторым выходом (1,й)-го вычислительных модулей, 1661793 < 1 Jff

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

Редактор А, Козориз Техред М,Моргентал Корректор Н. Король

Заказ 2126 Тираж 411 Подписное

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

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

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