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

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 4 (л) ф (й

iC) (у

1 (21) 4857628/24 (22) 11.06.90 (46) 15.05.92. Бюл. М 18 (72) В.П,Якуш, Н.А.Лиходед, B.Â.Êocüÿí÷óê и П.И.Соболевский (53) 681.325(088.8) (56) Авторское свидетельство СССР

Q 1534470, кл. G 06 F 15/347, 1987.

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

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

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

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

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

7 второго типа.

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

1, и — 1) первого типа и выход 8 результата.

Вычислительный блок 6 первого типа (фиг, 3) содержит первый 9, второй 10 и третий 11 информационные входы, синхров„„. Ж,„, 1734105 А1 высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для

LU-разложения матриц. Цель изобретения— сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство содержит (n — 1) вычислительных блоков первого типа (п — размерность разлагаемой матрицы) и вычислительный блок второго типа.

Вычислительный блок первого типа реализует арифметические операции умножения и вычитания, а вычислительный блок второго типа — обратную величину числа, 1 табл, 4 ил. ход 12, первый 13, второй 14 и третий 15 входы режима, умножитель 16, сумматор 17, регистры 18, 19, 20 и 21 (! =1, п — 1), триггеры

22, 23 и 24 (i = 1, и — 1), блоки элементов И

25 — 32, блоки элементов ИЛИ 33 — 35, элементы И 36 — 39, первый — шестой выходы

40-45.

Вычислительный блок 7 второго типа (фиг. 4) содержит первый 46 и второй 47 информационные входы, первый 48, второй

49 и третий 50 входы режима, синхровход

51, узел 52 вычисления обратной величины числа, регистры 53, 54, 55j(i = 1, n — 2), триггеры 56, 57 и 58 (i = 1, n — 1), блоки элементов

И 59 — 63, блоки элементов ИЛИ 64 и 65, элементы И 66 и 67, первый 68. второй 69, третий 70, четвертый 71 и пятый 72 выходы.

B основу работы устройства для разложения матрицы А = {ал), Ц = 1, и на нижнюю треугольную с единицами по главной диагонали матрицу 1 = (1л} и верхнюю треуголь1734105

U, V W значения на четвертом, пятом и шестом выходах вычислительного третьем режиме работы подаются упблока второго типа на )-м такте; равляющие сигналы (а, Р, у) = (О, О, 1). Открываются блоки элементов И 27, 30 и элементы

55 И 36, 38, Аналогично, как и во втором режиj t а, если (а Фy ) =(О 1 1)" (О "° О) ме, на выходе умножителя 16 формируется

bj, если (а! ф p) =(0, О, 1) (0, О, 0) (1, О, О), значение Ь с, которое подается на выход 41

1 А! (.p, !) (О 1, 1) (O О, 1) и записывается на следующем такте в ре— А1, если (а! lj, y ) = (О. 1, О) v(0. О, О), ную матрицу U = (Uijj положены следующие рекурентные соотношения: а !..=aij, i,j=1, и; (11

k=1, и; !

la= àà . Usk . k < I и; а iI"+ j = aij(") + !и (— Оц), k < I ï, k< j п.

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

Uj+n

Vi n =р

Wj+n где а1,P и y — значения соответственно на первом, втором и третьем входах режима вычислительного блока первого типа на j-м такте;

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

А =aj; а + lj р с, если (а p, y ) = (О, 1, О), Ь! + Ij Р с, если (а ф y) = (О, О, О), а! с, если (а ф yl) = (О, 1, 1), Ь с, если (а! ф у ) = (О, О, 1), bi, если (а! ф P) = (1, О, О), С1 "=C, где = а!.с1, если (а! Р, y ) =(О, 1, 1), Ь, с, если (а ф ) ) = (О, О, 1), р = О, и — 1 — параметр, определяемый алгоритмом; а, Ь и с — значения на первом, втором и третьем информационных входах вычислительного блока первого типа на J-м такте;

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

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

Uj+n )

Vj+n р!

Wj+n где aj,p и) — значения на первом, втором и третьем входах режима вычислительного блока второго типа иа j-м такте; и

50 где а1, Ь! и с — значения на первом, втором и третьем информационных входах вычислительного блока второго типа на J-м такте;

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

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

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

В первом режиме на входы 13, 14 и 15 подаются сигналы (а, P, y) = (О, 1, 1). При этом триггер 221 устанавливается в нулевое состояние, а триггеры 231, 241 — в единичное состояние, Элемент а записывается в pej гистр 18 и выдается на выход 40. Элемент с записывается в регистр 211. Открываются блоки элементов И 25, 30 и элементы И 36, 39. Элемент а! через блок элементов И 35 подается на первый вход умножителя 16, на второй вход которого подается элемент с .

Ка выходе умножителя 16 формируется значение I = а,с, которое на следующем такте. запишется в регистр 20 (регистр 20 построен на однотактных триггерах, запись в который осуществляется по переднему фронту тактового импульса), Кроме того, значение

= а1. с через блок элементов И 30 и блок элементов ИЛИ 34 подается на выход 41.

Во всех режимах элемент с, подаваемый на вход 11, выдается на выход 42 с задержкой на (n — 1) тактов. Также задерживаются и управляющие сигналы (а,/3, y), Во втором режиме на входы 13, 14 и 15 подаются управляющие сигналы (а, Р, у) = (О, 1, О). Открываются блоки элементов И 26, 28 и 31 и элемент И 37. Элемент а с выхода регистра 18 через блок элементов И 28 и блок элементов ИЛИ 35 подается на первый вход суматора 17.Содержимое регистра

20 через блок элементов И 26 и блок элементов ИЛИ 33 подается на вход умножителя

16, на второй вход которого с выхода регистра 21> подается элемент с . Ка выходе умножителя 16 формируется значение !-cj, которое подается на второй вход сумматора i7 и на выходе которого формируется значение а + Id, которое через блок элементов И 31 и блок элементов ИЛИ 34 подается на выход

41, 1734105 л л л

"(а л n„, и, "ь "ы ° - "z„

Л л д и "n2 "nn

В четвертом режиме работы подаются управляющие сигналы (а,P r) = (О, О, О). Открываются блоки элементов И 26, 29, 31 и элемент И 37. При этом, как и в третьем режиме, на выходе умножителя 16 формиру- 5 ется значение 1с, а на выходе сумматора 17 — значение Ь + I с, которое подается на выход 41, В пятом режиме работы подаются управляющие сигналы (а,P, у) = (1, О, О). При 10 этом открывается блок элементов И 32, через который элемент Ь с выхода регистра

19 подается на выход 41.

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

В первом режиме на входы 48, 49 и 50 подаются управляющие сигналы (a,p, y) =(О, 1, 1). При этом триггер 56 устанавливается в нулевое состояние, а триггеры 571 и 581— в единичное состояние. Блоки элементов И 20

59 и 63 открываются. Элемент а записывается в регистр 53 и через блок элементов И

59 и блок элементов ИЛИ 64 подается на выход 68 и на узел вычисления обратной величины числа 52.. Значение 1/а с выхо- 25 да узла 52 вычисления обратной величины числа через блок элементов И 63 и блок элементов ИЛИ 65 подается на вход регистра 551, в который записывается на следующем такте. Управляющие сигналы (а,P,ó) 30 выдаются соответственно на выходы 70, 71 и 72 с задержкой на (n-1) тактов, Во втором режиме на входы 48, 49 и 50 подаются управляющие сигналы (а, Р, y) = (О, 1, О), Открывается блок элементов И 59, че- 35 рез который элемент а (с выхода регистра

53) подается на выход 68. На выходе элемента И 66 формируется единичный сигнал, который открывает блок элементов И 61, через который с инверсного выхода регистра 53 40 элемент — а1 записывается на следующем такте в регистр 55>.

В третьем режиме на входы 48, 49 и 50 подаются управляющие сигналы (а, Р, у) =(О, О, 1). Открываются блоки элементов И 60 и 45

63.Элемент Ь с выхода регистра 54 подается на выход 68 и узел 52 вычисления обратной величины числа. Значение подается через блок элементов И 63 и блок элементов

ИЛИ 65 на вход регистра 55, в который 50 записывается на следующем такте.

В четвертом режиме на входы 48, 49 и

50 подаются управляющие сигналы (а,P,y)

= (О, О; О). Открывается блок элементов 60, 62 и элемент И 67, С инверсного выхода 55 регистра 54 значение — b через блок элементов И 62 и блок элементов ИЛИ 65 подается на вход регистра 55 и записывается на следующем такте, Элемент Ь с прямого выхода регистра 54 подается через блок элементов И 60 на выход 68.

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

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

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

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

С. ; = (-1)n+ ) — 1, На входы 2, 3 и 4 подаются соответственно управляющие сигналы а,Р, йу. Управляющие сигналы A! = (а, Р, y); образуют матрицу вида

Ф где т = (О, 1, 1);

Тц=(0, 1, О), j -2, п; г = (О, О, 1), j = 2, и;

% 1= (1, О, О); i = 2, и, j = 1, n— - 1, i — j>1; и )= (О, О, О), i = 2, п-1, j = 3, n, j-Ь1.

На входы 2, 3 и 4 управляющие сигналы г 1 подаются вмоменты времени т т = (i — 1) n + n + j — 2.

На выходе 8 формируются U>q(l<>) элементы в моменты времени

tU j(lii) = (i-1)n + n + j - 2.

На фиг. 2 приведена для n = 3 организация входных и выходных потоков данных. В таблице для и = 3 приведены состояния регистров, триггеров и значения на выходах вычислительных блоков 6>, 6 и 7устройства. Загрузка элементов ail осуществляется с

О-ro по 8-й такты. На втором такте в вычислительном блоке 7 формируется элемент 0

= а«, на третьем такте — элемент О« " =

1/а«и на четвергом такте —.элемент Uia = ад, которые подаются на выход 68. На третьем такте в вычислительном блоке 7 формируется значение U, в котором на четвертом такте формируется элемент lz> = а ° U« На пятом такте в вычислительном блоке 7 в регистр 17 записывается элемент le< и выдается на выход

68, в вычислительном блоке 6> формируется элемент а22 = агР + i21 (— U12) который выдается на выход 41. На шестом такте в вычислительном блоке 7 на выход подается элемент U22 = айаг, в вычислительном блоке

1734105

6.! формируется элемент а23 = а23(+ 121» (г) (1) (— U13), в вычислительном блоке 62 элемент

Iз1 = аз1 !.)11 . На седьмом такте в вычисли-1 тельном блоке(7 на выход 68 подается элемент U23 = а23 ), в вычислительном блоке 61 5 на выход 41 подается элемент 131, в вычислительноь блоке 62 формируется элемент азг(= азг ) + 131 (— U12). На восьмом такте в (г) 1) вычислительном блоке 7 на выход 31 подается элемент (з1, в вычислительном бл е 61 10 формируется элемент 1зг = а32(, U22 ", в вычислительном блоке 62 формируется элемент а33() = азз + 131.(— U13). На девятом такте в вычислительном блоке 7 на выход 68 подается элемент 1зг, в вычислительном бло- 15 ке 61 формируется элемент азз = азз )+ 1з2. к(-0гз). На десятом такте в вычислительном блоке 7 на выход 68 подается элемент U33=

= азз ).

С 2-го по 10-й такты соответствующие 20 элементы I!) — е и О!! — е подаются на выход

8 устройства.

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

Устройство для LU-разложения матриц, содержащее с первого по (n — 1)-й вычислительные блоки, где пхп-размерность разлагаемой матрицы, причем вход элементов матрицы устройства подключен к первому информационнОму входу первого вычислительного блока, первый выход, первый и второй входы режима i-го вычислительного блока (где i = 1,..., n — 2) подключены соответственно к первому информационному входу, к второму и третьему выходам (1+1)-го вычислительного блока, вход синхронизации устройства подключен к входам синхронизации всех вычислительных блоков, отл и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, первый выход (и — 1)-го вычислительного блока подключен к первому информационному входу и-го вычислительного блока, первый выход которого подключен к выходу результата устройства, первый и второй входы режима (и — 1)-го вычислительного блока подключены соответственно к второму и третьему выходам и-го вычислительного блока, первый, второй и третий входы режима которого подключены соответственно к первому, второму и третьему входам режима устройства, третий вход режима и второй информационный вход j-го вычислительного блока (где j =

1,...,n — 1) подключены соответственно к четвертому выходу и к пятому выходу (j+1)-ãî вычислительного блока, шестой выход i-го вычислительного блока подключен к третьему информационному входу (!+1)-го вычислительного блока, шестой выход (n — 1)-го вычислительного блока подключен к второ25

55 му информационному входу и-го вычислительного блока, причем каждый вычислительный блок с первого по (п — 1)-й содержит три регистра, четыре сдвигающих регистра, сумматор, умножитель, три триггера, восемь блоков элементов И, три блока элементов ИЛИ и четыре элемента И, при этом в каждом вычислительном блоке с первого по (и — 1)-й первый, второй и третий информационные входы, первый, второй и третий входы режима каждого вычислительного блока с первого по (n — 1)-й подключены соответственно к информационному входу первого регистра, информационному входу первого сдвигающего регистра, информационному входу второго регистра и информационным входам первого, второго и третьего триггеров, выход первого регистра подключен к первым входам первого и второго блоков элементов И и к первому выходу вычислительного блока с первого по п-й, выходы которых подключены соответственно к первым входам первого и второго блоков элементов ИЛИ, выходы которых подключены соответственно к первым информационным входам умножителя и сумматора, выход которого подключен к первому входу третьего блока элементов И, выход которого подключен к первому входу третьего блока элементов ИЛИ, первый и второй входы которого подключены соответственно к выходам четвертого и пятого блоков элементов И, выход второго регистра подключен к второму входу пятого блока элементов И, к первому входу шестого блока элементов И и первому входу седьмого блока элементов И, выход которого подключен к второму входу первого блока элементов ИЛИ, третий вход которого подключен к выходу восьмого блока элементов И, первый вход которого подключен к выходу третьего регистра, вход записи-считывания подключен к выходу первого элемента И, прямой выход первого триггера подключен к информационному входу второго сдвигающего регистра, к второму входу второго блока элементов И и к первому входу второго элемента И, выход которого подключен к второму входу первого блока элементов И, инверсный выход первого триггера подключен к первому входу третьего элемента И и к второму входу шестого блока элементов И, выход которого подключен к второму входу второго блока элементов ИЛИ, прямой выход второго триггера подключен к информационному входу третьего сдвигающего регистра, к первому входу первого элемента И, к первому входу четвертого блока элементов И, ко второму входу второго элемента И и ко второму входу третьего элемента И, выход которого под10

1734105

55 ключен к второму входу седьмого блока элементов И, инверсный выход второго триггера подключен к первому входу четвертого элемента И, .выход которого подключен к второму входу третьего блока элементов И 5 и к второму входу восьмого блока элементов

И, прямой выходтретьего триггера подключен к информационному входу четвертого сдивигающего регистра и к второму вхотого блока элементов И, инверсный выход 10 третьего триггера подключен к второму входу четвертого элемента И, информационный выход первого сдвигающего регистра подключен к второму информационному входу умножителя, выход которого подклю- 15 чен к второму информационному входу сумматора, второму входу четвертого блока элементов И и к информационному входу третьего регистра, выходы переноса второго, третьего, четвертого и первого сдвигаю- 20 щих регистров и выход третьего блока элементов ИЛИ подключены соответственно к выходам с второго по шестой вычислительного блока с первого по (и — 1)-й, вход синхронизации которого подключен к вхо- 25 дам записи считывания первого и второго регистров, второму входу первого элемента

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

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

1734105

2 3, V 5 6 Р. S 8 <о 4 КгНАРггИ ъ ЬАФзз 0 о о 6 р о" о 1

МГ. 2

1734105

1734105 и-1,/ФП

Фиг.4

Составитель И.Якуш

Техред M.Ìoðãåíòàë Корректор Н. Король

Редактор М,Циткина

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

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

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

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