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

4

сх

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

Целью изобретения является упрощение устройства.

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

Устройство содержит 0,5N (N+1) операционных блоков 1 (ОБ) и распределитель 2 импульсов, (k,k)-ft ОБ содержит входной регистр 3, блок 4 деления и вход 5 синхронизации, (k,P)ОБ содержит регистр 6 первого сомножителя, умножитель 7, вычитатель 8, выходной регистр 9, регистр 10 второго сомножителя, первый 11, второй 12 и третий 13 входы синхронизации.

Распределитель 2 импульсов реализован на базе ПЗУ согласно извест- Гным правилам.

Выходы раслределителя 2 подключен к соответствующим синхровходам требуемых ОБ. Временная диаграмма синхроимпульсов на выходах распределителя 2 определяется заданной последовательностью записи операндов и результата .

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

,(:.) - J

-,, a,j , k 1,2,

k+l,...,N,

UKJ a r-;Va r . 1

k

ij „(«I

- , Va

,(-, ki

(it-t)

KK

,(K- )

,

,N, i,j

1,..

KJ Кк К Ч 17 N

Л- f J

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

0

5

0

5

5

5

0

0

5

Для краткости описания без потери общности положим N 3. Условимся, что прием информации во все регистры осуществляется по заднему фронту синхроимпульса, т.е. в конце такта.

Исходные данные поступают на входы устройства для LU-разложения матриц построчно со сдвигом на один такт, т.е. первая строка исходной матрицы А, а,- подается на вход операционного блока 1.1.1, вторая строка, а ,-j - с задержкой на такт на вход ПЭ 1,2,1, третья строка, а. на вход ОБ 1.3.1 и т.д.

Д)

В первом такте элемент подается на вход ПЭ 1.1.1 ив конце такта принимается в регистр 3.1.1, причем а (° 1,, .

Во втором такте элемент а. поступает на вход ПЭ 1.1.1, на выходе которого получаем частное а/ . /а,

и

ft

Это частное в конце такта

а элемент 1,, принимается в

(0)

0

принимается в регистр 10.2.1 ПЭ 1.2.1

(0) 71

регистр 6.2.1.

В третьем такте элемент подается на вход ОБ 1.1.1, на выходе которого получим частное а , . Элемент а подается на первый вход ОБ 1.2.1, на выходе умножителя 7.2.1 получаем произведение а °|/а °, , которое поступает на вход вычитателя 8.2.1 и на его выходе получаем выражение а

() .(«J. гг

22

/- a ij°Va 1°, „ a j, lij. В конце такта частное ,, /а ° принимается в ре- гистр 10.2.1, частное а ( /a J, - в регистр 10.3.1, а - в регистр 9.2.1, элемент а °J 1 i. в регистр 6.3,1.

J1 3 f ti

В четвертом такте элемент а подается на первый вход ПЭ 1.2.1. На выходе умножителя 7.2.1 получаем

произведение 5i , которое поступает на вход вычитателя 8.2.1, и на его выходе получаем вьфажение

an

- а (

л л - я

JJ

,. а //. Элемент

а Д поступает на первый вход ПЭ

1.3.1.На выходе умножителя 7.3.1 появляется произведение а , /а 7/ а j / которое подается на вход вычитателя 8.3.1 и на его выходе получаем выражение а а ,, - aS - /aSV-a ,,. В конце такта частное а j /a y, принимается в регистр 10.3.1, а у| - из регистра 9.2.1 принимается в регистр

3.2.2,а/J} принимается в регистр 9., а У - в регистр 9.3.1.

В пятом такте отсчет ci(° подается на первый вход ПЭ 1.3.1, на г.ыходе умпожителя 7,3,1 получается произведение 3° i oTopoe подается на вход вычитателя 8,3.1 и на его выходе получаем выражение a j j а ° - a /jVa7i - з, - На первый вход ОБ 1.2.2 поступает из регистра 9.2.1, и на выходе ОБ 1.2.2 получаем

V, /.

частное та а 1

11

и

13

в конце так31 31 записывается из регистра 9,3.1 в-регистр 6.3.2, a jj записывается в регистр 9,3.1, частное

оО)/ ()

23

/aVo - в регистр 10.3,2.

В шестом такте а У поступает на первый вход ОБ 1.3,2,на выходе умножителя 7,3.2 получаем произведение Vv JJ а , котороеподается на вход вычитателя 8,3.2и на его выходе получаем выражениеа - - а Ij, ,которое в конце такта записываетсяв регистр

9.3.2.

C i)

В седьмом такте а j принимается в регистр 3,3.3.

На этом процесс LU-разложения матрицы А завершается. Элементы верхней треугольной матрицы U : U , U,, , Uj вьщаются с выходов ПЭ 1.1,1 и 1.2.2. Элементы нижней треугольной матрицы L к концу вычислений находятся в регистрах процессорных элементов: , 1, 1 за в регистрах 3,1,1, 3,2.2, 3.3.3 соответственно, li,, 31 за в регистрах 6,2.1,6,3.1, 6.3.2 соответственно.

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

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

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

0

5

0

5

0

5

0

5

0

с целью упрощения, первьп вход (К,1)-го операционного блока подключен к К-Му информацион рму входу устройства, где К 1,N, первый выход (K,k)-ro операционного блока подключен к К-му выходу устройства, второй выход тр-го операционного блока подключен к второму входу (m-t-1,q)-ro операционного блока (т 1,N-1, q 1,m) (первый выход ij-ro операционного блока подключен к первому входу (i,j-b1 )-го операционного блока (i 27N, j 1,i-1).

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

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

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

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

Л/v-ZA- /kJ J.N-1M-2

t-J

/мл/ /и.

..-2lf-

/.A ..Л -А-

S

Изобретение относится к вычисли- тельной технике и может быть использовано при построении специализированных устройств, предназначенных для решения системы линейных уравнений. Целью настоящего изобретения является упрощение. Поставленная цель достигается тем, что благодаря изменению организации вычислений и числа межпроцессорных связей устройство содержит 1/2N(N+1) операционных блоков, N входов и N выходов. 2 з.п. ф-лы, 4 ил.

0U2j

Фаг.2

«

{jtovaao J I

(W

Рг3.,1„

I

AT /a. 7 ; - r , t,

.- (7„г/

ti tJ

РгЮг1 : a, fa ;-cPr fO.3.

-Л- « л/, : - ,.T-, ;« ,

PrS.J.: a, Ij,

Pr JO.J.,, Рг3.г., Pr 9..a ,.a,r- Pr9. . a ; .a f ГАГ r /,.

X

1s

Ргб.з.г7: ff j; . t,f .З..-af /af f

.J.,,-a

/ /j . j /..-. . 7j;,- ,ГА/;.; - /.

ц-°х- и

fflrJ3j.---a f -fr,

(/fioffeu ) ФигЛ

Редактор Н.Лазаренко

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

Техред М.Ходанич Корректор М Шароши

Заказ 2786/48

Тираж 704

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

/

«

tj

:n

55ггг.З

/;.; - /.

ц-°х- и

Подписное