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

г

tPvzi

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

Целью изобретения является снижение аппаратурных затрат.

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

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

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

третьего регистра 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 связан с выходом регистра бис первым входом шестого коммутатора 21,

второй вход которого подключен к второму входу сумматора 7 и к выходу блока 22 эле- . ментов задержки, вход которого является выходом коммутатора 11. Выход коммутатора 21 подключен к второму входу блока 5,

вход выбора режима которого (умножение или деление с обратным знаком) подключен

к входу разрешения приема информации регистра 6, к управляющему входу коммутатора 21 и является третьим управляющим

входом вычислительного модуля, второй управляющий вход которого подключен к син- хровходу D-триггера 20. Выход коммутатора 12 подключен к входу регистра 16, первый информационный вход вычислительного

модуля подключен к третьему входу коммутатора 18,- на управляющий вход блока элементов задержки постоянно подается значение п в двоичном коде.

Блок 2.i (, n-1) управления может содержать три последовательно включенных D-триггера 23-25, счетчик 26, синхронный RS-триггер 27, D-триггеры 28, 29 и 30. Причем входы D-триггеров 23, 28, 30 и 29 являются соответственно первым, вторым, пятым и третьим входами блока 2.i, выходы

D-триггеров 25,28,30 и 29 являются соответственно первым, вторым, пятым и третьим выходами блока 2.i. При этом четвертый вход блока 2.i подключен к S-входу RS-триг- гера 27 и к входу выбора режима (параллельное занесение (п+2) или счет в режиме вычитания) счетчика 26, выход отрицательного переноса которого подключен к R-вхо- ду триггера 27, выход которого является четвертым выходом блока 2.I. Блок 2.1 может содержать D-триггеры 31-35, счетчик 36, синхронные RS-триггеры 37, 38, счетчики 39, 40, элементы ИЛИ 41, 42 и D-триггер 43. Причем выходы блока 2.1 с первого по пятый являются выходами соответственно элементов ИЛИ 42, 41, D-триггера 35 и RS- триггеров 38 и 37. При этом выходы элементов ИЛИ 42 и 41 подключены соответственно к входам выбора режима счетчиковЗЭ и 36, S-вход триггера 38 связан с входом D-триггера 31 и с выходом D-триггера 32, вход которого является четвертым входом блока 2,1 и подключен к входу выбора режима счетчика 40, к S-входу триггера 37 и к входуD-триггера 34, Выходы отрицательного переноса счетчиков 36, 39 и 40 подключены соответственно к входам элементов ИЛИ 41, 42 и к R-входу триггера 35. Третий и пятый входы блока 2.1 связаны соответственно с входами D-триггеров 33 и 43, а выход D-триггера 43 подключен к R- входу триггера 37.

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

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

U L А. При этом преобразование матрицы А выполняется по алгоритму исключения Гаусса с частичным выбором ведущего элемента по столбцу, который предполагает,

что исключению элемента aji на i-м шаге алгоритма Гаусса (, n-1, ,n) предшествует его сравнение с элементом aii, причем если laji I lajjl , то осуществляется перестановка j-й и i-й строк. После проведе0 ния операций сравнения (и перестановок) aii со всеми элементами aji, an становится максимальным по модулю среди остальных aji. Затем производится преобразование j-й ( ,п) строки путем поэлементного сумми5 рования с ней i-й строки, умноженной на коэффициент Iji -ajj/an. При этом все происходящие перестановки строк запоминаются и выдаются (в качестве элементов нижней треугольной матрицы перестановок

0 V Uji для дальнейшего использования.

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

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

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

5 каждой строки матрицы поступают на соответствующие входы устройства со сдвигом на один такт, т.е. элемент аи ( ,п) поступает на i-й вход устройства в i-м такте работы устройства.

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

В первом такте на вход запуска устройства поступает единичный импульс, кото5 рый устанавливает в единицу D-триггер 4. Эта единица поступает на S-вход триггера 37, на входы D-триггеров 32 и 34, и на вход выбора режима счетчика 40 (параллельное занесение информации или счет в режиме

0 вычитания). Кроме того, элемент a-i н матрицы А поступает на первый вход устройства и записывается в конце такте в регистр 3.

На втором такте D-триггер 4 устанавливается в нуль, а D-триггеры 32, 34 и RS-триг5 гер 37 - в единицу, в счетчик 40 заносится значение(п+2)5, 321 с второго входа устройства через коммутатор 10.1 поступает на первые входы коммутаторов 11.1, 12.1 и схемы 13.1 сравнения, на вторые входы которых поступает an с выхода коммутатора

14.1, и если I 311 I I 3211, на выходе схемы 13.1 сравнения появляется единица, которая записывается в D-триггер 20.1 (признак перестановки строк V2i). В противном случае на выходе схемы 13.1 сравнения остается ноль. Пусть в нашем случае 1а21 I lanl. Тогда ноль с выхода схемы 13.1 (V21 0) записывается в D-триггер 20.1 и поступает на управляющие входы коммутаторов 11.1 и 12.1, и они пропускают на свои выходы соответственно 321 и an, после чего 321 записывается в первый регистр блока 22.1 элементов задержки, а ац в регистр 16.1, и появляется на третьем информационном выходе модуля 1.1. Кроме того, в регистр 3 записывается ai2.

В третьем такте триггеры 31,28, 30 и 38 устанавливаются в единицу, а 32 и 34 - в ноль, в счетчик 36 записывается значение (п+1)4, аз1 с третьего входа устройства через коммутатор 10.2 поступает на входы коммутаторов 11.2, 12.2 и схемы 13.2 сравнения, на вторые входы которых поступает ац из регистра 16.1 (через коммутатор 14.2), и происходит сравнение элементов а.ц и азт энзлогично второму такту. Пусть I ац I аз11. Тогда единица с выхода схемы 13.2 сравнения (Vsi 1) записывается в D-триггер 20.2 и поступает нэ упрзвляющие входы коммутаторов 11.2 и 12.2, в результате чего ац ззписывэется в первый регистр блока 22.2, а аз - в регистр 16.2, и появляется на втором выходе устройстве, причем аз1 Un. В этом же такте V21 из D-триггера 20.1 проходит через первый вход коммутатора 18.1 на его выходи записывается в регистр 19.1, 322 с второго входа устройства проходит через коммутаторы 10.1 и 11.1 и записывается в первый регистр блока 22.1, а 21 из первого регистра блока 22.1 переписывается в его второй регистр. Кроме того, ai2 из третьего регистра проходит через коммутаторы 14.1 и 12.1 и записывается в регистр 16.1, в третий регистр записывается ai3, счетчик 40 уменьшает свое значение на единицу.

В четвертом такте триггеры 23, 27, 43 и 33 устанавливаются в единицу, а триггеры 31 и 28 - в ноль, в счетчики 39 и 26 записываются соответственно значения ( и (п+2)5, счетчики 40 и 36 уменьшает свое состояние на единицу, аз2 поступает с третьего входа устройства, записывается в регистр 16,2 и появляется на втором выходе устройства, причем 332 Ui2, ац из первого регистра блока 22.2 переписывается во второй регистр блока 22.2, а в первый регистр блока 22.2 записывается ai2 из регистра 16.1,321 и 322 из второго и первого регистров блока 22.1 переписываются соответственно в третий и второй регистры блока 22.1, а в

его первый регистр записывается 323, поступающее с второго входа устройства, /21 из регистра 19.1 переписывается в регистр 17.1, азт из регистра 16.2 переписывается в регистр 15.1, а в регистр 16.1 записывается

313.

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

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

5 блока 22.1 через коммутатор 21.1), и результат деления (-321/asi) 121 принимэется в регистр 6,1. В этом же тэкте аз1 переписывается в регистр 15.2, в регистр 15.1 ззписы- вается аз2, а в регистр 16.2 - эзз, причем эзз0 Ui3. Кроме того, в третий и второй регистры блокэ 22.1 записываются соответственно 322 и 323, V21 из регистра 17.1 переписывается в регистр 19.2, в регистры 3, 2 и первый блок 22.2 записывэются соот5 ветственно ац, 312 и 313.

В шестом такте триггеры 29 и 25 уста- нзвливэются в единицу, а триггеры 35, 30 и 24 - в ноль, счетчики 36, 40 и 39 вновь уменьшают свои значения на единицу, и их

0 содержимое стэновится равным соответственно 1,1 и 0, на выходе отрицательного переноса счетчика 39 появляется единица, 331 из регистре 15.2 поступэет на первый вход блока 5.1, на второй вход которого по5 ступает ац (с выхода блока 22.2), и результат деления (-ац/зз1) 1з1 принимэется в регистр 6.2. В этом же тэкте эз2 из регистрз 15.1 поступэет на первый вход блока 5.1, нз второй вход которого поступэет (-321/asi) из

0 регистра 6.1, результат умножения поступает на первый вход сумматора 7.1, на второй вход которого поступает 322 (с выходе блока 22.1), и окончательный результат 322 - аз2х Х321/эз1 322 принимзется в регистр 8.1,121

5 из регистра 6.1 переписывается в регистр 19.1, аз2 переписывается в регистр 15.2, а азз - в регистр 15.1. Кроме того, третий и второй регистры блокз 22.2 записываются соответственно 312 и ais, а в третий регистр

0 блока 22.1 - 323, V21 переписывзется из ре- гистрз 19.2 в регистр 17.2 и появляется нэ первом выходе устройства, Vsi переписывается из триггера 20.2 в регистр 19.2.

В седьмом тзкте триггер 23 устзнавли5 вэется в единицу, а триггеры 42, 25 и 36 - в ноль, в счетчик 39 записывается знэчение (п-1)2 в двоичном коде, счетчики 40 и 36 уменьшэют свои знэчения нэ единицу, и на их выходэх отрицзтельного переноса появляется единица, аз2 из регистра 15.2 поступает на блок 5.2, туда же поступает (-aii/a3i) из регистра 6.2, результат умножения поступает на сумматор 7.2 и с его выхода значение ai2 - аз2-ац/аз1 ai2 принимается в регистр 8.2. В этом же такте азз из регистра 15.1 переписывается в регистр 15.2, а также поступает на блок 5.1, туда же подается содержимое регистра 6.1, а на сумматор 7.1 - значение ааз из третьего регистра блока 22.1, и с выхода сумматора 7.1 знэчение 323-эзз-а21/аз1 Э231 принимается в регистр 8.1, а 3221 переписывается в регистр 9.1. Кроме того, в третий регистр блока 22.2 записывается ais, N/31 переписывается из регистра 19.2 в регистр 17.2 и появляется на первом выходе устройства, 121 из регистра 19.1 переписывается в регистр 17.1.

В восьмом такте триггеры 24 и 28 устанавливаются в единицу, а триггеры 23, 38, 24 - в ноль, счетчики 39 и 40 уменьшают свои значения на единицу, в счетчик 36 записывается значение (п+1)4, азз из регистра 15.2 поступает на блок 5.2, туда же подается (-эц/аз1), результат умножения поступает на сумматор 7.2 с выхода которого значение ais - азз эп/азт ai3 принимается в регистр 8.2, a ai21 переписывается в регистр 9.2, а также поступает на первый вход коммутатора 10.2, с его выхода - на первые входы коммутаторов 11.2,12.2 и схемы 13.2 сравнения, на вторые входы которых поступает Э221 из регистра 9.1 (через коммутатор 14.2) и происходит их сравнение. Пусть I 3221 I 1Э121 I. Тогда единица с выхода схемы 13.2 сравнения (V23 1) записывается в D-триггер 20.2, 322 записывается в первый регистр блока 22.2, a ai21 - в регистр 16.2 и появляется на втором выходе устройства, причем ai21 U22. В этом же такте 121 переписывается из регистра 17.1 в регистр 19.2, а 3231 - регистра 8.1 в регистр 9.1. В этом же такте возможно начало обработки следующей входной матрицы. Для этого на вход запуска устройства необходимо вновь подать единичный импульс, который устанавливает в единицу D-триггер 4. Кроме того, элемент ац следующей матрицы необходимо подать на первый вход устройства, и тогда он запишется в регистр 3 (в этом же такте).

В девятом такте триггеры 25, 32, 37, 34 и 33 устанавливаются в единицу, э триггеры 28, 24 и 4 - в ноль, счетчики 39, 26, 36 уменьшают свои знэчения на единицу, причем нз выходе отрицзтельного переноса счетчика 39 появляется единица, в счетчик 40 записывается значение (п+2)5,1з1 из регистра 6.2 переписывзется в регистр 19.2, V23 из D-триггерэ 20.2 переписывается в

регистр 19,2. В этом же такте ais из регистра 8.2, пройдя через коммутаторы 10.2 и 12.2, переписывается в регистр 16.2 и появляется на выходе устройства, причем ais

1)23, 3231 из регистра 9.1 переписывается в первый регистр блока 22.2 (пройдя через коммутаторы 14.2 и 11.2), аз221 переписыва- ется во второй регистр этого блокэ, 1)22 из регистрэ 16.2 переписывается в регистр

0 15.1, 121 появляется на выходе устройства. Кроме того, в этом такте продолжается обработка следующей входной матрицы аналогично второму такту, т.е. элемент следующей матрицы 321 с второго входа ус5 тройства поступает на первые входы коммутаторов 11.1, 12.1 и схемы 13.1 сравнения, на вторые входы которых поступает из регистра 3, и происходит их сравнение, в результате которого один из элементов

0 записывается в регистр 16.1, а другой. - в первый регистр блока 22.1. Кроме того, в регистр 3 записывается ai2, а в D-триггер 20.1 - признак V21.

В десятом такте триггеры 23, 38, 35, 30,

5 28 и 31 устанавливаются в единицу, триггеры 32, 34, 33, 25 - в ноль, счетчики 40 и 26 уменьшают свои значения на единицу, и их содержимое становится равным соответствен но 4 и 4, всчетчикиЗЭиЗбзаписывэются

0 соответственно значения 2 и 4, V23 и |з1 из регистра 19.2 переписывэются в регистр 17.2 и появляются на выходе устройства, ai21 U22H ais1 и23записывэются соответственно в регистры 15.2 и 15.1, 322 и 323

5 записываются соответственно в третий и второй регистры блока 22.2.

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

0 В одиннадцатом такте триггеры 23, 24, 27, 29, 43, 33 уста на вливаются в единицу, триггеры 35, 28 и 31 - в ноль, счетчики 40,36 уменьшают свои значения на единицу, в счетчики 39 и 26 записываются соответст5 венно значения 2 и 5, U22 из регистра 15.2 поступает на блок 5.2, туда же выдается 3221 из третьего регистра блока 22.2, и результат деления 1з2 (-322 /U22) записывается в регистр 6.2, Э231 переписывается в третий ре0 гистр блокэ 22.2, U23 переписывается в регистр 15.1. Действия над элементэми очередной матрицы производятся аналогично четвертому такту.

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

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

сумматор 7.2, с выхода которого результат 3231 - U23 322/U22 Uss принимается в регистр 8.2, |з2 из регистра 6.2 переписывается в регистр 19.2. Действия над элементами очередной матрицы производятся аналогично пятому такту.

В тринадцатом такте 1з2 переписывается в регистр 17.2 и появляется на первом выходе устройства, а Узз переписывается в регистр 9.2 и появляется на третьем выходе устройства. Действия над элементами очередной матрицы производятся аналогично шестому такту.

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

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

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

четвертым и пятым управляющими входами j-ro вычислительного модуля, выход D-триг- гера соединен с четвертым управляющим входом первого вычислительного модуля, причем в каждом вычислительном модуле

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

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

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

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

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

5 соединен с информационным входом седьмого регистра, выход которого соединен с информационным входом шестого регистра, выход схемы сравнения соединен с входом D-триггера, выход которого соединен с

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

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

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

(ji-t-i) -

d

4/

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолических устройств, предназначенных для решения систем линейных алгебраических уравнений. Целью изобретения является снижение аппаратурных затрат. Устройство для треугольного разложения матриц содержит вычислительные блоки 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 со