Устройство для треугольного разложения матриц

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных , в том числе и систолических устройств, предназначенных для решения систем линейных алгебраических уравнений . Целью изобретения является снижение аппаратурных затрат. Устройство для треугольного разложения матриц содержит вычислительные блоки 1.1-1.(п-1) и блоки 2.1-2.(п-1) управления. Причем информационные выходы с первого по четвертый вычислительного блока 1.1 (i 1, п-2) подключены соответственно к информационным входам с первого по четвертый блока 1.(i+1), первый и четвертый информационные выходы вычислительного бл.ока 1.(п-1) являются соответственно первым и третьим выходами устройства, третий информационный выход вычислительного блока 1 .(п-Т) является вторым выходом устройства и подключен к второму информационному входу вычислительного блока 1.1, третий и информационный вход которого связан с выходом регистра 3, вход которого является первым входом устройства, пятый информационный вход вычислительного блока 1.J , п-1) является (i+1)-M информационным входом устройства, вход запуска которого подключен к входу D-триггера 4, выходы блока 2.j управления с первого по, пятый подключены соответственно к входам с первого по пятый блокам 2.(j+1) управления, второй и пятый выходы блока 2.(п-1) управления подключены соответственно к третьему и пятому входам блока 2.1 управления, первый, второй, третий и пятый выходы блока 2.j управления подключены соответственно к первому, второму, третьему и пятому управляющим входам вычислительного блока 1J, четвертый выход блока 2.J управления подключен к четвертому управляющему входу блока 2.0+1) управления, четвертый управляющий вход блока 2.1 управления подключен к четвертому управляющему входу вычислительного блока 1.1 и к выходу триггера 4. При этом п означает размерность обрабатываемой матрицы. 4 ил: ел С 00 о о Os со

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

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

РЕСПУБЛИК

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОВРЕТЕНИ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ОО

С)

C) (3 (Ы (21) 4774437/24 (22) 26.12.89 (46) 07.03;93. Бюл. N- 9 (71) Киевский политехнический институт им, 50-летия Великой Октябрьской социалистической революции (72) P.Âûæèêîâñêèé (PL), Ю.С.Каневский и

О.В.Масленников (SU) (56) Авторское свидетельство СССР

N 1587540, кл. G 06 Е 15/347, 1989, Н. Barada А, E I-А-mawy systolic

architecture for matrix triengularization with

partial piloting ll lEEE Proc. WoL 135 Pt.E

¹ 4, lyly 1988, рр, 209. (54) УСТРОЙСТВО ДЛЯ ТРЕУГОЛЬНОГО

РАЗЛОЖЕНИЯ МАТРИЦ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для решения систем линейных алгебраических уравнений. Целью изобретения является снижение аппаратурных затрат. Устройство для треугольного разложения матриц содержит вычислительные блоки 1.1-1.(n-1) и блоки

2.1-2,(n-1) управления. Причем информационные выходы с первого по четвертый вычислительного блока 1. (i=1, и-2) подключены соответственно к информационным входам с первого по четвертый блока

1.(i+1), первый и четвертый информацион„„Я „„1800463 А1 ные выходы вычислительного блока 1,(n-1) являются соответственно первым и третьим выходами устройства, третий информационный выход вычислительного блока 1.(п-1) является вторым выходом устройства и подключен к второму информационному входу вычислительного блока 1.1, третий и информационный вход которого связан с выходом регистра 3, вход которого является первым входом устройства, пятый информационный вход вычислительного блока 1. (j=1, и-1) является (j+1)-м информационным входом устройства, вход запуска которого подключен к входу D òðèããåðà 4, выходи блока 2,j управления с первого по, пятый подключены соответственно к входам с первого по пятый блокам 2.(j+1) управления. второй и пятый выходы блока 2.(n-1) управления подключены соответственно к третьему и пятому входам блока 2,1 управления, первый, второй, третий и пятый выходы блока 2.j управления подключены соответственно к первому, второму, третьему и пятому управляющим входам вычислительного блока 1.j, четвертый выход блока 2.j управления подключен к четвертому управляющему входу блока 2.(j+1) управления. четвертый управляющий вход блока 2.1 управления подключен к четвертому управляющему входу вычислительного блока 1.1 и к выходу триггера 4. При этом и означает размерность обрабатываемой матрицы. 4 ил .

1800463

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

i-ro вычислительного модуля (i=1, и-1); на фиг. 3 — структурная схема возможного варианта реализации первого блока управления; на фиг. 4 — структурная схема возможного варианта реализации k-го (k=2, и-1) блока управления.

Устройство для треугольного разложения матриц содержит вычислительные модул и 1. 1-1. (п-1) и блоки 2. 1-2. (и-1) управления. Причем информационные выходы с первого по четвертый модуля 1,i (i=1, и-2) подключены соответственно к информационнь м входам с первого по четвертый, модуля 1.(+1), первый и четвертый информационные выходы вычислительного модуля 1.(n-1) являются соответственно первым и третьим выходами устройства, третий информационный выход модуля 1,(n-1) является вторым выходом устройства и подключены к второму информационному входу вычислительного модуля 1.1, четвертый информационный вход которого связан с выходом регистра 3, вход которого является первым входом устройства, пятый информационный вход модуля 1л (i=1, и-1) является (i+1)-м входом устройства, вход запуска которого подключен к входу D-триггера 4. Выходы блока 2,i управления с первого по пятый (i=1, и-2) подключены соответственно к входам с первого bio пятый блока 2. (i+1), второй и пятый выходы блока 2. (п-1) подключены соответственно к третьему и пятому входам блока 2.1, первый, третий и пятый выходы блока 2,i (i=1, и-1) управления подключены соответственно к первому, второму, третьему и пятомууправляющим входам вычислительного модуля 1л, четвертый выход блока 2 i (i=1, и-2) подключен к четвертому управляющему входу блока 2,(i+1), четвертый управляющий вход блока 2.1 подключен к четвертому управляющему входу модуля 1,1 и к выходу D-триггера 4.

Вычислительный модуль 1,i (i=-1, и-1) содержит блок 5 умножения-деления, выход которого связан с входом первого регистра

6 и с первым входом сумматора 7, Выход сумматора 7 подключен к входу второго регистра 8, выход которого связан с входом

55 третьего регистра 9 и с первым входом первого коммутатора 10, выход которого связан с первыми входами второго 11 и третьего 12 коммутаторов и схемы 13 сравнения, Вторые входы коммутаторов 11, 12 и схемы сравнения 13 объединены и подключены к выходу четвертого коммутатора 14, первый и второй входы которого являются соответственно третьим и четвертым информационными входами вычислительного модуля.

Второй информационный вход последнего связан с входом четвертого регистра 15, выход которого подключен к первому входу блока 5 и является вторым информационным выходом модуля. Четвертый, третий и первый информационные выходы модуля подключены к выходам соответственно регистра 9, пятого 16 и шестого 17 регистров, пятый информационный вход вычислительного модуля подключен к второму входу коммутатора 10, управляющий вход которого является пятым управляющим входом модуля. Четвертый и первый управляющие входы модуля подключены соответственно к управляющим входам коммутаторов 14 и

18, выход которого подключен к входу седьмого регистра 19, выход которого подключен к входу регистра 17. Выход схемы 13 сравнения связан с входом D-триггера 20, выход которого подключен к управляющим входам коммутаторов 11 и 12 и к первому входу коммутатора 18. Второй вход коммутатора 18 связан с выходом регистра 6 и с первым входом шестого коммутатора 21, второй вход которого подключен к второму входу сумматора 7 и к выходу блока 22 элементов задержки, вход которого является выходом коммутатора 11, Выход коммутатора 21 подключен к второму входу блока 5, вход выбора режима которого (умножение или деление с обратным знаком) подключен к входу разрешения приема информации регистра 6, к управляющему входу коммутатора 21 и является третьим управляющим входом вычислительного модуля, второй управляющий вход которого подключен к синхровходу D-триггера 20. Выход коммутатора

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

Блок 2л (i=2, и-1) управления может содержать три последовательно включенных

D-триггера 23-25, счетчик 26, синхронный

RS-триггер 27, 0-триггеры 28, 29 и 30. Причем входы 0-триггеров 23, 28, 30 и 29 являются соответственно первым, вторым, пятым и третьим входами блока 2., выходы

1800463

D-триггеров 25, 28,30 и 29 являются соответственно первым, вторым, пятым и третьим выходами блока 2л. При этом четвертый вход блока 2л подключен к S-входу RS-триггера 27 и к входу выбора режима(параллель- 5 ное занесение (n+2) или счет в режиме вычитания) счетчика 26, выход отрицательного переноса которого подключен к R-входу триггера 27, выход которого является четвертым выходом блока 2л. Блок 2.1 мо- 10 жет содержать D-триггеры 31-35, счетчик

36, синхронные RS-триггеры 37, 38, счетчики 39, 40, элементы ИЛИ 41, 42 и D-триггер

43. Причем выходы блока 2.1 с первого по пятый являются выходами соответственно 15 элементов ИЛИ 42, 41, D-триггера 35 и RSтриггеров 38 и 37. При этом выходы элементов ИЛИ 42 и 41 подключены соответственно к входам выбора режима счетчиков 39 и 36, S-вход триггера 38 связан 20 с входом 0-триггера 31 и с выходом 0-триггера 32, вход которого является четвертым входом блока 2,1 и подключен к входу выбора режима счетчика 40, к S-входу триггера

37 и к входу D-триггера 34, Выходы отрица- 25 тельного переноса счетчиков 36, 39 и 40 подключены соответственно к входам элементов ИЛИ 41, 42 и к R-входу триггера 39.

Третий и пятый входы блока 2,1 связаны соответственно с входами 0-триггеров 33 и 30

43, а выход 0-триггера 43 подключен к Rвходу триггера 37.

Все узлы и элементы устройства (кроме триггеров) имеют разрядность, равную разрядности входных данных и результатов, 35 однако регистры 17, 19 и коммутатор 18— (m+1)-разрядные, Это вызвано тем, что через коммутатор 18 проходит и в регистры

17, 19 записывается кроме m-разрядного результата еще и одноразрядный признак 40 перестановки строк (более подробно см.описание работы устройства), Таким образом, в зависимости от значения сигнала на своем управляющем входе коммутатор

18 передает на выход либо (m+1) разряд с 45 третьего своего входа, либо m разрядов с второго входа и один разряд с первого входа. Блоки 22 элементов задержки представляют собой цепочку из и последовательно соединенных регистров. 50

Устройство для треугольного разложения матриц предназначено для выполнения первой фазы решения системы линейных алгебраических уравнений Ax=b (х и b-пмерные векторы столбцы, А — матрица коэф- 55 фициентов) методом исключения Гаусса— прямого исключения, которое состоит в нахождении такой нижней треугольной матрицы L = (I;;), которая преобразует матрицу А в верхнюю треугольную матрицу U = (Щ, т.е.

U = L А. При этом преобразование матрицы

А выполняется по алгоритму исключения Гаусса с частичным выбором ведущего элемента по столбцу, который предполагает, что исключению элемента а íà i-м шаге алгоритма Гаусса (i=1, п-1, j=i+1,n) предшествует его сравнение с элементом aii, причем если la>< I < !а11, то осуществляется перестановка j-й и i-й строк. После проведения операций сравнения (и перестановок) ай со всеми элементами а1, а становится максимальным по модулю среди остальных

aji. Затем производится преобразование j-й (j=i+1,n) строки путем поэлементного суммирования с ней -й строки, умноженной на коэффициент Iji = -ajar/а",. При этом все происходящие перестановки строк запоминаются и выдаются (в качестве элементов нижней треугольной матрицы перестановок

V = (0р) для дальнейшего использования.

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

Поступление исходных данных организовано следующим образом, На i-й вход устройства (i=1,n) в каждый такт поступает элемент

i-й строки матрицы А, начиная с элемента а, и заканчивая ann В свою очередь, элементы каждой строки матрицы поступают на соответствующие входы устройства со сдвигом на один такт, т.е. элемент аи (i=1,n) поступает на -й вход устройства в i-м такте работы устройства.

Считаем, что перед началом вычислений все триггеры всех блоков управления установлены в нулевое состояние, В первом такте на вход запуска устройства поступает единичный импульс, который устанавливает в единицу 0-триггер 4.

Эта единица поступает на S-вход триггера

37, на входы D-триггеров 32 и 34, и на вход выбора режима счетчика 40 (параллельное занесение информации или счет в режиме вычитания), Кроме того, элемент а матрицы А поступает на первый вход устройства и записывается в конце такте в регистр 3.

На втором такте D-триггер 4 устанавливается в нуль, à D-триггеры 32, 34 и RS-триггер 37 — в единицу, в счетчик 40 заносится значение(п+2)=5, ay< с второго входа устройства через коммутатор 10.1 поступает на первые входы коммутаторов 11,1, 12.1 и схемы 13.1 сравнения, на вторые входы которых поступает à > с выхода коммутатора

1800463

14,1, и если а11 < а21 !, на выходе схемы

13.1 сравнения появляется единица, которая записывается в D-триггер 20.1 (признак перестановки строк Чг1). В противном случае на выходе схемы 13.1 сравнения остается ноль. Пусть в нашем случае la21 l < !811!.

Тогда ноль с выхода схемы 13.1 (V21 = О) записывается в 0-триггер 20,1 и поступает на управляющие входы коммутаторов 11.1 и

12,1, и они пропускают на свои выходы соответственно 821 и 811 после чего 821 записывается в первый регистр блока 22,1 элементов задержки, а а11 в регистр 16.1, и появляется на третьем информационном выходе модуля 1.1. Кроме того, в регистр 3 записывается а12.

В третьем такте триггеры 31, 28, 30 и 38 устанавливаются в единицу, а 32 и 34 — в ноль, в счетчик 36 записывается значение (и+1)=4, а31 с третьего входа устройства через коммутатор 10.2 поступает на входы коммутаторов 11,2, 12.2 и схемы 13.2 сравнения, на вторые входы которых поступает а11 из регистра 16.1 (через коммутатор 14,2), и пРоисхоДит сРавнение элементов а.н и аз1 аналогично второму такту. Пусть а11 < аз1!. Тогда единица с выхода схемы 13.2 сравнения (Чз1 = 1) записывается в D-триггер 20.2 и поступает на управляющие входы коммутаторов 11,2 и 12.2, в результате чего а11 записывается в первый регистр блока

22.2, а a31 — в регистр 16.2, и появляется на втором выходе устройства„причем аз1= 011, В этом же такте V21 из D-триггера 20.1 проходит через первый вход коммутатора 18,1 на его выхбд и записывается в регистр 19,1, а22 с второго входа устройства проходит через коммутаторы 10.1 и 11.1 и записывается в первый регистр блока 22.1, а 21 из первого регистра блока 22.1 переписывается в его второй регистр. Кроме того, 812 из третьего регистра проходит через коммутаторы 14.1 и 12.1 и записывается в регистр 16.1, в третий регистр записывается а 13, счетчик 40 уменьшает свое значение на единицу.

В четвертом такте триггеры 23, 27, 43 и

33 устанавливаются в единицу, а триггеры

31 и 28 — в ноль, в счетчики 39 и 26 записываются соответственно значения (n-1)=2 и (n+2)=5, счетчики 40 и 36 уменьшает свое состояние на единицу, азг поступает с третьего входа устройства, записывается в регистр 16.2 и появляется на втором выходе устройства, причем 832 = U12, 811 из первого регистра блока 22.2 переписывается во второй регистр блока 22,2, а в первый регистр блока 22.2 записывается а12 из регистра

16 1, а21 и а22 из второго и первого регистров блока 22.1 переписываются соответственно в третий и второй регистры блока 22,1, а в

55 ется из триггера 20.2 в регистр 19.2.

В седьмом такте триггер 23 устанавливается в единицу, а триггеры 42, 25 и 36 — в ноль, в счетчик 39 записывается значение (п-1)=2 в двоичном коде, счетчики 40 и 36 уменьшают свои значения на единицу, и на их выходах отрицательного переноса появляется единица, азг из регистра 15.2 постуего первый регистр записывается а23, поступающее с второго входа устройства, Ч21 из регистра 19.1 переписывается в регистр

17.1, а31 из регистра 16,2 переписывается в

5 регистр 15.1, а в регистр 16.1 записывается а1з.

В пятом такте триггеры 24 и 35 устанавливаются в единицу, а триггеры 37, 33, 23— в ноль, счетчики 40, 39 и 36 уменьшают свои

10 значения на единицу, а счетчик 26 не меняет своего состояния (на его управляющем входе остается единица), аз1 из регистра 15.1 поступает на первый вход блока 5.1, на второй вход которого поступает а21 (с выхода

15 блока 22.1 через коммутатор 21.1), и результат деления (-821/831) = l21 принимается в регистр 6,1. В этом же такте а31 переписывается в регистр 15.2, в регистр 15.1 записывается а32, а в регистр 16.2 — азз, причем азз20 = U13, Кроме того, в третий и второй регистры блока 22.1 записываются соответственно агг и агз, V21 из регистра 17 1 переписывается в регистр 19.2, в регистры

3, 2 и первый блок 22,2 записываются соот25 ветственно а11, 812 и а1з.

B шестом такте триггеры 29 и 25 устанавливаются в единицу, а триггеры 35, 30 и

24 — в ноль, счетчики 36, 40 и 39 вновь уменьшают свои значения на единицу, и их

30 содержимое становится равным соответственно 1,1 и О, на выходе отрицательного переноса счетчика 39 появляется единица, аз1 из регистра 15,2 поступает на первый вход блока 5.1, на второй вход которого по35 ступает а11(с выхода блока 22.2), и результат деления (-811/831) = !31 принимается в регистр 6,2. В этом же такте а32 из регистра

15,1 поступает на первый вход блока 5.1, на второй вход которого поступает (-аг1/a31) из

40 регистра 6.1, результат умножения поступает на первый вход сумматора 7.1, на второй вход которого поступает агг(с выхода блока

22.1), и окончательный результат a22 - 832x ха21/аз1= 822 принимается в регистр 8.1, !21

45 из регистра 6.1 переписывается в регистр

19.1, а32 переписывается в регистр 15.2, а азз — в регистр 15.1, Кроме того, третий и второй регистры блока 22,2 записываются соответственно а1г и а13, а в третий регистр

50 блока 22,1 — 823, V21 переписывается из регистра 19.2 в регистр 17,2 и появляется на первом выходе устройства, V31 переписыва1800463

10 пает на блок 5.2, туда же поступает (-а11/а31) из регистра 6.2, результат умножения поступает на сумматор 7.2 и с его выхода значение a12 - а32.а11/а31 =

=а12 принимается в регистр 8.2. В этом же такте а33 из регистра 15.1 переписывается в регистр 15.2, а также поступает на блок 5,1, туда же подается содержимое регистра 6.1, а на сумматор 7.1 — значение а23 из третьего регистра блока 22.1, и с выхода сумматора

7.1 значение а23-аззa21/а31= а23 принима1 ется в регистр 8.1, а а22 переписывается в

1 регистр 9.1. Кроме того, в третий регистр блока 22.2 записывается а13, Ч31 переписывается из регистра 19.2 в регистр 17,2 и появляется на первом выходе устройства, I21 из регистра 19,1 переписывается в регистр 17,1.

В восьмом такте триггеры 24 и 28 устанавливаются в единицу, а триггеры 23, 38, 24 — в ноль, счетчики 39 и 40 уменьшают свои значения на единицу, в счетчик 36 записывается значение (и+1)=4, а33 из регистра 15.2 поступает на блок 5.2, туда же подается (-а11/а31), результат умножения поступает на сумматор 7.2 с выхода которого значение а13 - а33 а11/а31 = а13 и ринимается в регистр 8.2, а а12 переписывается в

1 регистр 9.2, а также поступает на первый вход коммутатора 10,2, с его выхода — на первые входы коммутаторов 11.2, 12.2 и схемы 13.2 сравнения, на вторые входы которых поступает а22 из регистра 9.1 (через

1 коммутатор 14.2) и происходит их сравнение. Пусть I à22 1< Iа12 1. Тогда единица с 1 1 выхода схемы 13,2 сравнения (Ч23 = 1) записывается в D-триггер 20.2, а22 записывается в первый регистр блока 22.2, а а12 — в регистр 16,2 и появляется на втором выходе устройства, причем а12 = U22. В этом же такте 121 переписывается из регистра 17.1 в регистр 19.2, а а23 — регистра 8,1 в регистр

9.1. В этом же такте возможно начало обработки следующей входной матрицы. Для этого на вход запуска устройства необходимо вновь подать единичный импульс, который устанавливает в единицу D-триггер 4, Кроме того, элемент а11 следующей матрицы необходимо подать на первый вход устройства, и тогда он запишется в регистр 3 (в этом же такте).

В девятом такте триггеры 25, 32, 37, 34 и 33 устанавливаются в единицу, а триггеры

28, 24 и 4 — в ноль, счетчики 39, 26, 36 уменьшают свои значения на единицу, причем на выходе отрицательного переноса счетчика 39 появляется единица, в счетчик

40 записывается значение (n+2)=5, 131 из регистра 6.2 переписывается в регистр 19,2, Ч23 из D-триггера 20.2 переписывается в

27, 29, 43, 33 устанавливаются в единицу, триггеры 35, 28 и 31 — в ноль, счетчики 40, 36 уменьшают свои значения на единицу, в счетчики 39 и 26 записываются соответст45 венно значения 2 и 5, U22 из регистра 15,2 поступает на блок 5.2, туда же выдается а221 из третьего регистра блока 22,2, и результат деления 132 = (-а22 /U22) записывается в регистр 6,2, а23 переписывается в третий ре1

50 гистр блока 22.2, U23 переписывается в регистр 15.1. Действия над элементами очередной матрицы производятся аналогично четвертому такту.

В двенадцатом такте триггеры 24, 25, 35

55 устанавливаются в единицу, триггеры 23, 29, 43, 37, 33 — в ноль, счетчики 40, 36 и.39 уменьшают свои значения на единицу, U23 из регистра 15.2 поступает на блок 5.2, туда же выдается 132 из регистра 6.2, а23 из третьего регистра блока 22.2 поступает на

40 регистр 19,2. В этом же такте а13 из регист1 ра 8.2, пройдя через коммутаторы 10.2 и

12.2, переписывается в регистр 16.2 и появляется на выходе устройства, причем а13 =

=023, а23 из регистра 9.1 переписывается в первый регистр блока 22.2 (пройдя через коммутаторы 14.2 и 11.2), а а22 переписыва1 ется во второй регистр этого блока, U22 из регистра 16,2 переписывается в регистр

15.1, 121 появляется на выходе устройства, Кроме того, в этом такте продолжается обработка следующей входной матрицы аналогично второму такту, т.е, элемент следующей матрицы а21 с второго входа устройства поступает на первые входы коммутаторов 11.1, 12.1 и схемы 13,1 сравнения, на вторые входы которых поступает из регистра 3, и происходит их сравнение, в результате которого один из элементов записывается в регистр 16.1, а другой. — в первый регистр блока 22.1. Кроме того, в регистр 3 записывается а12, а в D-триггер

20,1 — признак V21.

Вдесятом такте триггеры 23,,38,,35, 30, 28 и 31 устанавливаются в единицу, триггеры 32, 34, 33, 25 — в ноль, счетчики 40 и 26 уменьшают свои значения на единицу, и их содержимое становится равным соответственноо 4 и 4, в счетчики 39 и 36 записываются соответственно значения 2 и 4, Ч23 и 31 из регистра 19,2 переписываются в регистр

17.2 и появляются на выходе устройства, а12 = U22 и а13 = 023 записываются соответ1 ственно в регистры 15.2 и 15.1, а22 и а23 записываются соответственно в третий и второй регистры блока 22.2.

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

В одиннадцатом такте триггеры 23, 24, 1800463

12 сумматор 7.2, с выхода которого результат а23 — U23 а22/U22 = 0зз принимается в ре1 гистр 8.2, з2 из регистра 6,2 переписывается в регистр 19.2. Действия над элементами очередной матрицы производятся аналогично пятому такту.

В тринадцатом такте!з2 переписывается в регистр 17.2 и появляется на первом выходе устройства, а 0зз переписывается в регистр 9.2 и появляется на третьем выходе устройства. Действия над элементами очередной матрицы производятся аналогично шестому такту, На этом разложение матрицы А заканчивается. Далее работа устройства продолжается аналогично с периодом (n-2) такта, т.е. каждую следующую матрицу (вместе с импульсом запуска) можно начинать подавать с (n-Д)-го такта после начала подачи предыдущей матрицы, Формула изобретения

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

1-го вычислительного модуля соединены соответственно с первым, вторым, третьим и четвертым информационными входами (i+1)-ro вычислительного модуля (i = 1, п-2), первый, третий и четвертый выходы (n-1)-го вычислительного модуля являются соответственно первым, вторым и третьим выходами устройства, второй выход которого соединен с вторым информационным входом первого вычислительного модуля, четвертый информационный вход которого соединен с выходом регистра, вход которого является первым информационным входом устройства, входом запуска которого является вход D-три ге а, пятый информационный вход)-ro(j:1, и-1) вычислительного модуля является (j+1)-м информационным входом устройства, с первого, второй, третий, четвертый и пятый выходы I-го блока управления соединены соответственно с первым, вторым, третьим, четвертым и пятым входами (i+1)-го блока управления, второй и пятый выходы (п-1)-го блока управления соединены соответственно с третьим и пятым входами первого блока управления, первый, второй и третий выходы

j-го блока управления соединены соответст5

55 венно с первым, вторым и третьим управляющими входами)-ro вычислительного модуля, четвертый вход и пятый выход/-ro блока управления соединены соответственно с четвертым и пятым управляющими входами

j-ro вычислительного модуля, выход D-триггера соединен с четвертым управляющим входом первого вычислительного модуля, причем в каждом вычислительном модуле выход блока умножения-деления соединен с информационным входом первого регистра и первым входом сумматора, выход которого соединен с информационным входом второго регистра, выход которого соединен с информационным входом третьего регистра и первым информационным входом первого коммутатора, выход которого соединен с первыми информационными входами второго и третьего коммутаторов и первым входом схемы сравнения, второй вход которой объединен с вторыми информационными входами второго и третьего коммутаторов и соединены с выходом четвертого коммутатора, первый и второй информационные входы которого являются соответственно третьим и четвертым информационными входами вычислительного модуля, второй информационный вход которого соединен с информационным входом четвертого регистра, выход которого соединен с первым входом блока умножения-деления и вторым выходом вычислительного модуля, четвертый, третий и первый выходы которого соединены соответственно с выходами третьего, пятого и шестого регистров, пятый информационный вход вычислительного модуля соединен с вторым информационным входом первого коммутатора, управляющий вход которого является пятым управляющим входом вычислительного модуля, четвертый и первый управляющие входы которого соединены соответственно с управляющими входами четвертого и пятого коммутаторов, выход пятого коммутатора соединен с информационным входом седьмого регистра, выход которого соединен с информационным входом шестого регистра, выход схемы сравнения соединен с входом D-триггера, выход которого соединен с управляющими входами второго и третьего коммутаторов и с первым информационным входом пятого коммутатора, второй информационный вход кЬторого соединен с выходом первого регистра и первым информационным входом шестого коммутатора, второй информационный вход которосо соединен с вторым входом сумматора и выходом блока элементов задержки, вход которого соединен с выходом второго коммутатора, выход шестого коммутатора сое14

1800463

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

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

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

1800463

Г

9 uz. з

40

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

Техред М.Моргентал Корректор С.Шекмар

Редактор С,Кулакова

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

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

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

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