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

Ё

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

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

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

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

Устройство для Ш-разложения матриц (фиг. 1) содержит вход 1 элементов матриц, первый 2, второй 3 и третий 4 входы режима, синхровход 5, вычислительные блоки 6i (i 1, п-1) первого типа и выход 8 результата.

Вычислительный блок 6 первого типа (фиг. 3) содержит первый 9, второй 10 и третий 11 информационные входы, синхровход 12, первый 13, второй 14 и третий 15 входы режима, умножитель 16. сумматор 17, регистры 18,19.20и21|(1 1. п-1),триггеры 22, 23 и 24i (i 1, п-1), блоки элементов И 25-32, блоки элементов ИЛИ 33 - 35, элементы И 36 - 39, первый - шестой выходы 40-45.

Вычислительный блок 7 второго типа (фиг. 4) содержит первый 46 и второй 47 информационные входы, первый 48, второй 49 и третий 50 входы режима, синхровход 51, узел 52 вычисления обратной величины числа, регистры 53, 54. 55| (1 1, п-2), триггеры 56, 57 и 58| (1 1, п-1), блоки элементов И 59 - 63, блоки элементов ИЛИ 64 и 65, элементы И 66 и 67, первый 68, второй 69, третий 70, четвертый 71 и пятый 72 выходы.

В основу работы устройства для разложения матрицы А {ay}, i,j 1, п на нижнюю треугольную с единицами по главной диагонали матрицу L {lij} и верхнюю треугольVI

СО

Ј

о

СЛ

ную матрицу U {Uij} положены следующие рекурентные соотношения:

aij(1) aij, l,j f, n;

,n;

Ukj akjM j k;n;

lik - aik(. Ukk 1.k i n;

a4(k+1) aij(k) + hk (-Ukj), k i n, k j n.

Вычислительный блок 6 первого типа выполнен с возможностью реализации слеующих функций:

Uj+n «i, п, Wj+n Я

где о,/ и У - значения соответственно на первом, втором и третьем входах режима вычислительного блока первого типа на j-м такте;

UJ, V и W - значения соответственно на четвертом, пятом и шестом выходах вычислительного блока первого типа на j-м такте;

AJ+1 aj;

aj + lhp. cj, если (а1 0. у1) (0, 1, 0), bj + .cj, если (с//, у1) (О, О, О), aj.cj, если (, у) (0, 1, 1), bj-cj, если(, уО (0, 0, 1), Ы, если (о1 /, у) (1,0, 0),

ЈJ+fl ЈJ

где IJ+1 raj.cj, если (а1 /9, у1 ) (0,1, 1),

|bj,cj, если (o/ /Sl. у) (0, О, 1), р 0, п-1 - параметр, определяемый алго

ритмом;

Ь и с - значения на первом, втором

и третьем информационных входах вычислительного блока первого типа на j-м такте;

А , в и С - значения на первом, втором и третьем выходах вычислительного блока первого типа на j-м такте.

Вычислительный блок 7 второго типа обладает возможностью реализации следующих функций:

uJ+rW,

Vj4n.

wj+n yJ,

где d,$ и у - значения на первом, втором и третьем входах режима вычислительного блока второго типа на j-м такте;

lA V и W - значения на четвертом, пятом и шестом выходах вычислительного блока второго типа на j-м такте;

А

Ъ

i+t a

, если (/,#, у1) (0, 1, 1)v(0, 1,0),

bj, если (о1 j$, У) (0,0, 1)v(0, 0, ОУ(1, 0, 0} i+fl.,f 1/А,если(о -/б1.)-(0. 1, 1МО,0, 1) -AJ, если (о1- fl, у) (0, 1, 0)v(0, О, О),

где а, Ы и с - значения на первом, втором и третьем информационных входах вычислительного блока второго типа на j-м такте; А и В - значения на первом и втором

5 выходах вычислительного блока второго типа на j-м такте.

Рассмотрим работу вычислительных блоков.

Вычислительный блок 6 первого типа

10 работает в пяти режимах.

В первом режиме на входы 13, 14 и 15 подаются сигналы (а, /, у) (0,1,1). При этом триггер 221 устанавливается в нулевое состояние, а триггеры 23i, 24i - в единичное

15 состояние. Элемент а записывается в регистр 18 и выдается на выход 40. Элементе записывается в регистр 211. Открываются блоки элементов I/I 25, 30 и элементы И 36, 39. Элемент а через блок элементов И 35

0 подается на первый вход умножителя 16, на второй вход которого подается элемент cj. На выходе умножителя 16 формируется значение I aj.cj, которое на следующем такте запишется в регистр 20 (регистр 20 постро5 ен на однотактных триггерах, запись в который осуществляется по переднему фронту тактового импульса). Кроме того, значение I а. cj через блок элементов И 30 и блок элементов ИЛИ 34 подается на выход 41.

0 Во всех режимах элемент с , подаваемый на вход 11, выдается на выход 42 с задержкой на (п-1) тактов. Также задерживаются и управляющие сигналы (а,/, у). Во втором режиме на входы 13, 14 и 15

5 подаются управляющие сигналы (а,Д у) (0, 1, 0). Открываются блоки элементов И 26, 28 и 31 и элемент И 37. Элемент aj с выхода регистра 18 через блок элементов И 28 и блок элементов ИЛИ 35 подается на первый

0 вход суматора 17.Содержимое I регистра 20 через блок элементов И 26 и блок элементов ИЛИ 33 подается на вход умножителя 16, на второй вход которого с выхода регистра 211 подается элемент d. На выходе

5 умножителя 16 формируется значение l-c, которое подается на второй вход сумматора 17 и на выходе которого формируется значение а + id, которое через блок элементов И 31 и блок элементов ИЛИ 34 подается на выход

0 41.

В третьем режиме работы подаются управляющие сигналы (а,/, у) (0,0, 1). Открываются блоки элементов И 27,30 и элементы

5 И 36, 38. Аналогично, как и во втором режиме, на выходе умножителя 16 формируется

значение b-cj, которое подается на выход 41 и записывается на следующем такте в регистр 20.

В четвертом режиме работы подаются управляющие сигналы (а,/, у) (О, О, 0). Открываются блоки элементов И 26, 29, 31 и элемент И 37. При этом, как и в третьем режиме, на выходе умножителя 16 формируется значение. 1-е1, а на выходе сумматора 17 - значение Ы + l-cj, которое подается на выход 41.

В пятом режиме работы подаются управляющие сигналы (а,/,у) (1, 0, 0). При этом открывается блок элементов И 32, через который элемент Ы с выхода регистра 19 подается на выход 41.

Вычислительный блок 7 второго типа работает также в пяти режимах.

В первом режиме на входы 48, 49 и 50 подаются управляющие сигналы (а,/, у) (О, 1, 1). При этом триггер 56i устанавливается в нулевое состояние, а триггеры 57i и 58i - в единичное состояние. Блоки элементов И 59 и 63 открываются. Элемент а записывается в регистр 53 и через блок элементов И 59 и блок элементов ИЛИ 64 подается на выход 68 и на узел вычисления обратной величины числа 52. Значение 1/а с выхода узла 52 вычисления обратной величины числа через блок элементов И 63 и блок элементов ИЛИ 65 подается на вход регистра 55i, в который записывается на следующем такте. Управляющие сигналы (а,/3, у) выдаются соответственно на выходы 70, 71 и 72 с задержкой на (п-1) тактов.

Во втором режиме на входы 48, 49 и 50 подаются управляющие сигналы (а, /3, у) (О, 1, 0). Открывается блок элементов И 59, через который элемент а (с выхода регистра 53) подается на выход 68. На выходе элемента И 66 формируется единичный сигнал, который открывает блок элементов И 61, через который с инверсного выхода регистра 53 элемент - а записывается на следующем такте в регистр 55i.

В третьем режиме на входы 48, 49 и 50 подаются управляющие сигналы (a, J3, у) (О, О, 1). Открываются блоки элементов И 60 и 63. Элемент Ы с выхода регистра 54 подается на выход 68 и узел 52 вычисления обратной величины числа. Значение подается через блок элементов И 63 и блок элементов ИЛИ 65 на вход регистра 55i, в который записывается на следующем такте.

В четвертом режиме на входы 48, 49 и 50 подаются управляющие сигналы (2,Ду) (О, О, 0). Открывается блок элементов 60, 62 и элемент И 67. С инверсного выхода регистра 54 значение - Ы через блок элементов И 62 и блок элементов ИЛИ 65 подается на вход регистра 55i и записывается на следующем такте. Элемент b с прямого вы

хода регистра 54 подается через блок элементов И 60 на выход 68,

В пятом режиме на входы 48, 49 и 50 подаются управляющие сигналы (а, /, у) (1, 0, 0). Элемент Ы с выхода регистра 54 через открытый блок элементов И 60 подается на выход 68.

Во всех режимах значения, записанные в регистр55i, выдаются на выход 69 с задер- жкой на (п-2) тактов.

Рассмотрим работу устройства (фиг. 1).

Элементы ац подаются на вход 1 в моменты времени

taij (M)n + j-1.

На входы 2, 3 и 4 подаются соответственно управляющие сигналы а,/, иу. Управляющиесигналыт j (а, Д y)(-j образуют матрицу вида

,, «

ча

г.1

л

сгп

25

п

«12

л ь пп

0

5

0

5

0

5

гдеП1(0, 1, 1); Г1.Г(0, 1,0), j

2, п;

И г (О, О, 1), J-2, п;

тп

т j (1, 0, 0), i 2. п. j 1, n-1, i-j2:1 ;

Ч j-(0, 0,0), 1 2, n-1,j 3, n,J-fe1.

На входы 2, 3 и 4 управляющие сигналы

подаются в моменты времени

tTij (i-1) n + n+j-2.

На выходе 8 формируются Uij(lij) элементы в моменты времени

tUij(lij) (i-1)n + n + j-2.

На фиг. 2 приведена для п 3 организация входных и выходных потоков данных. В таблице для п 3 приведены состояния регистров, триггеров и значения на выходах вычислительных блоков 6i, 62 и 7 устройства. Загрузка элементов aij осуществляется с 0-го по 8-й такты. На втором такте в вычислительном блоке 7 формируется элементен аи, на третьем такте - элемент 1ИГ1 Van и на четвертом такте - элемент 1Из aj3., которые подаются на выход 68. На третьем такте в вычислительном блоке 7 формируется значение Ui2 atz, которое подается в вычислительный блок 6i, в котором на четвертом такте формируется элемент 121 32/ 1 -Uif1 На пятом такте в вычислительном блоке 7 в регистр 17 записывается элемент 121 и выдается на выход 68, в вычислительном блоке 6i формируется элемент 322 322 + 121 ), который выдается на выход 41. На шестом такте в вычислительном блоке 7 на выход подается элемент U22 322 , в вычислительном блоке

6 формируется элемент 323 + 121 -Uia), B вычислительном блоке 62 элемент 1з1 asi-Un 1. На седьмом такте в вычислиельном блоке 7 на выход 68 подается элемент U23 323 , в вычислительном блоке 6i 5 на выход 41 подается элемент 1з1, в вычислительном блоке 62 формируется элемент аз2 аз2 + l3i (Ui2). На восьмом такте в вычислительном блоке 7 на выход 31 подается элемент Ы, в вычислительном блоке 6i ю формируется элемент 1з2 аз2 U22 в вычислительном блоке 62 формируется элемент a3311J + lsi-(-Ui3). На девятом акте в вычислительном блоке 7 на выход 68 подается элемент 1з2, в вычислительном бло- 15 ке 6i формируется элемент азз + 1з2 (-U23). На десятом такте в вычислительном блоке 7 на выход 68 подается элемент Узз- азз 2).

С 2-го по 10-й такты соответствующие 20 элементы lij - е и Uij - е подаются на выход 8 устройства.

Формула изобретения Устройство для LU-разложения матриц, 25 содержащее с первого по (п-1)-й вычислительные блоки, где nxn-размерность разлагаемой матрицы, причем вход элементов матрицы устройства подключен к первому информационному входу первого вычисли- 30 тельного блока, первый выход, первый и второй входы режима i-ro вычислительного блока (где i 1,..., п-2) подключены соответственно к первому информационному вхоу, к второму и третьему выходам (i+1)-ro 35 вычислительного блока, вход синхронизации устройства подключен к входам синхронизации всех вычислительных блоков, отичающееся тем, что, с целью сокращения аппаратурных затрат, первый выход 40 п-1)-го вычислительного блока подключен к первому информационному входу n-го вычислительного блока, первый выход которого подключен к выходу результата устройства, первый и второй входы режима 45 п-1)-го вычислительного блока подключены соответственно к второму и третьему выхоам n-го вычислительного блока, первый, второй и третий входы режима которого подключены соответственно к первому, вто- 50 рому и третьему входам режима устройства, ретий вход режима и второй информационный вход j-ro вычислительного блока (где j 1п-1) подключены соответственно к четвертому выходу и к пятому выходу 0+1)-го 55 вычислительного блока, шестой выход 1-го вычислительного блока подключен к третьему информационному входу (i+1)-ro вычисительного блока, шестой выход (п-1)-го вычислительного блока подключен к второму информационному входу n-го вычислительного блока, причем каждый вычислительный блок с первого по (п-1)-й содержит три регистра, четыре сдвигающих регистра, сумматор, умножитель, три триггера, восемь блоков элементов И, три блока элементов ИЛИ и четыре элемента И, при этом в каждом вычислительном блоке с первого по (п-1)-й первый, второй и третий информационные входы, первый, второй и третий входы режима каждого вычислительного блока с первого по (п-1)-й подключены соответственно к информационному входу первого регистра, информационному входу первого сдвигающего регистра, информационному входу второго регистра и информационным входам первого, второго и третьего триггеров, выход первого регистра подключен к первым входам первого и второго блоков элементов И и к первому выходу вычислительного блока с первого по n-й, выходы которых подключены соответственно к первым входам первого и второго блоков элементов ИЛИ, выходы которых подключены соответственно к первым информационным входам умножителя и сумматора, выход которого подключен к первому входу третьего блока элементов И, выход которого подключен к первому входу третьего блока элементов ИЛИ, первый и второй входы которого подключены соответственно к выходам четвертого и пятого блоков элементов И, выход второго регистра подключен к второму входу пятого блока элементов И, к первому входу шестого блока элементов И и первому входу седьмого блока элементов И, выход которого подключен к второму входу первого блока элементов ИЛИ, третий вход которого подключен к выходу восьмого блока элементов И, первый вход которого подключен к выходу третьего регистра, вход записи-считывания подключен к выходу первого элемента И, прямой выход первого триггера подключен к информационному входу второго сдвигающего регистра, к второму входу второго блока элементов И и к первому входу второго элемента И, выход которого подключен к второму входу первого блока элементов И, инверсный выход первого триггера подключен к первому входу третьего элемента И и к второму входу шестого блока элементов И, выход которого подключен к второму входу второго блока элементов ИЛИ, прямой выход второго триггера подключен к информационному входу третьего сдвигающего регистра, к первому входу первого элемента И, к первому входу четвертого блока элементов И, ко второму входу второго элемента И и ко второму входу третьего элемента И, выход которого подключей к второму входу седьмого блока элементов И, инверсный выход второго триггера подключен к первому входу четвертого элемента И, выход которого подключен к второму входу третьего блока элементов И и к второму входу восьмого блока элементов И, прямой выход третьего триггера подключен к информационному входу четвертого сдивигающего регистра и к второму вхо- того блока элементов И, инверсный выход третьего триггера подключен к второму входу четвертого элемента И, информационный выход первого сдвигающего регистра подключен к второму информационному входу умножителя, выход которого подключен к второму информационному входу сумматора, второму входу четвертого блока элементов И и к информационному входу третьего регистра, выходы переноса второго, третьего, четвертого и первого сдвигающих регистров и выход третьего блока элементов ИЛИ подключены соответственно к выходам с второго по шестой вычислительного блока с первого по (п-1)-й, вход синхронизации которого подключен к входам записи считывания первого и второго регистров, второму входу первого элемента И, к входам синхронизации сдвигающих регистров с первого по четвертый и триггеров с первого по третий, причем n-й вычислительный блок содержит первый и второй регистры, узел вычисления обратной величины, с первого по четвертый сдвигающие регистры, с первого по третий триггеры, с первого по пятый блоки элементов И, первый и второй блоки элементов ИЛИ, первый и второй элементы И, при этом первый и второй информационные входы, первый, второй и третий входы режима n-го вычислительного блока подключены соответственно к информационным входам первого и второго регистров, первого, второго и третьего триггеров, прямые выходы первого и второго регистров подключены соответственно к первым входам первого и второго блоков элементов И, выходы которых подключены соответственно к первому и второму входам первого блока ИЛИ, выход которого подключен к первому выходу n-го вычислительного блока и к информационному входу узла вычисления обратной величины,

выход которого подключен к первому входу третьего блока элементов И, выход которого подключен к первому входу второго блока элементов ИЛИ, выход которого подключен к информационному входу первого сдвигающего регистра, инверсные выходы первого и второго регистров подключены соответственно к первым входам четвертого и пятого блоков элементов И, выходы которых подключены соответственно к второму

и третьему входам второго блока элементов ИЛИ, прямой выход первого триггера подключен к информационному входу второго сдвигающего регистра, второму входу первого блока элементов И и к первому входу

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

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

ю о

чг со гТИ

ft/ 41

S

ЈA-I

ас;

Фиг. i

.ггр °« Q/г % Чгг °гг «гз%/05г&лз

f

J5

л

ти УТИ

aj

45

Чти

Фиг.З