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

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

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

На фиг. 1 представлена структурная схема устройства для разложения матриц; на фиг. 2 - структурная схема блока синхронизации; на фиг. 3 - структурная схема i-ro операционного блока.

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

СП

со со со

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

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

Казкдый операционньш блок содержит первый коммутатор 3, блок 4 умножителя-деления, вычитатель 5, второй 6 и третий 7 коммутаторы, регистр 8, блок 9 памяти объемом 2N-1 слов, пер вый D-триггер 10, первьй элемент И 11, первый счетчик 12, пятьй элемент ШШ 13, схему 14 сравнения, второй элемент И 15, второй D-триггер 16, третий элемент ИЛИ 17, первый элемент ИЛИ 18, RS-триггер 19, второй элемент ШШ 20, второй счетчик 21, третий 22 и четвертый 23 D-триг- геры, четвертый элемент ИЛИ 24.

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

Запоминающее устройство объемом 2N-1 представляет собой блок регистров, аналогичный примененному в микропроцессорной секции 1804ВС1, ко- торьй имеет два адресных входа, один из которых работает только на чтение, два выхода данных и один вход для 3 аписи данных. В нашем случае адресньй вход А секции ВС1 является первым адресным входом запоминающего устройства, а адресный вход В, допускающий как чтение, так и запись, является вторым адресным входом запоминающего устройства. Выкод А секции ВС1 является вторым выходом запоминающего устройства, а выход В - первым выходом запоминающего устройства. Управляющий вход чтения- записи, таким образом, относится толко к адресному входу В.

Блок 2 синхронизации (фиг. 2) со держит генератор 25 синхронизйрую- Щ1-1Х импульсов, выход которого соединен с синхровходами всех регистров, ЛЗУ, счетчиков и D-триггеров устрой- ства (не показано) и с синхровходом счетчика 26, вьпсоды которого подключены к первой группе входов схемы 27 сравнения, на вторую группу входов Ткоторой постоянно подается значение

5

N в двоичном коде, а выход ее связан с S-входом RS-триггера 28, R-вход которого является входом запуска устройства, выход последнего связан с К-входом счетчика 26 и является выходом блока синхронизации, а инкре- ментирующий вход счетчика 26 является входом признака блока синхронизации.

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

(fc) а,.а

{.-О V

J

(k-i) а,-ь

где а

а.м

,

,...,N, , k+2,...,N;

. где k.l,...,N; , k-H,...N;

-I., „((- ;

I k 1 k

k+I,...,N.

где ,...,N; .

:Q

5

0

5

Рассмотрим работу устройства. Предположим . Тогда прием информации во все регистры и блок памяти осуществляется по заднему фронту синхроимпульса, т.е. в конце такта, а в счетчики и D-триггеры - по переднему фронту синхроимпульса, т.е. в начале такта. Поступление исходных данных организовано следующим образом. На вход устройства каждьй такт последовательно поступают элементы матрицы jno столбцам, т.е. первые N тактов - элементы первого столбца матрицы А (в первом такте а, во втором а,,и т.д.).

вторые N тактов - элементы второго столбца и т.д.

В исходном состоянии счетчики 12, 21 и 26, и D-тригге.ры 10 и 16 нахог дятся в нулевом состоянии, а RS-триг- геры 19 и 28 и D-триггеры 22 и 23 установлены в единицу, на выходах схем 14 сравнения - нуль.

После сигнала Запуск RS-триг- с гер 28 устанавливается в нулевое состояние, в первом такте D-триггер IP.l устанавливается в единицу На вход устройства подается значение , Kotopoe поступает на второй

вход вычитателя 3.1 и вторые входы коммутаторов 3.1 и 6.1. Вычитатель

5.1производит пропуск операнда (на выходе элемента ИЛИ 17 единица), ком- мутатрр 7.1 пропускает .выхол вычитателя на вход регистра 8.1

(на выходе элемента ИЛИ 24 единица )и по заднему фронту синхросигнала a,j записывается в регистр 8.1. Это же значение через коммутатор 6.1 поступает на вход записи данных блока памяти 9.1 и записывается (на выходе элемента ИЛИ 20 единица) в ячейку с нулевым адресом, поступаюим с выхода счетчика 21, а D-триг- гер 22.1 сбрасывается в нуль. .

Во втором такте а,,1,, с выхода регистра 8.1 поступает на информа- ционньгй вход процессорного элемента, Вычитатель 5.2 осуществляет пропуск операнда и 1 записывается в конце такта в регистр 8.2, пройдя через коммутатор 7.2. В этом же такте содержимое счетчиков 12.1 и 21.1 увеличивается на единицу, а поступает на вход устройства и далее записывается в блоке 9.1 памяти по адресу (001) (пройдя через коммутатор 6.1) и.в регистр 8.1 (пройдя без изменений через вычитатель 5.1 и коммутатор 7.1), D-триггер 22.2 сбрасывается в нуль.

В третьем такте 1, из регистра

8.2переписывается в регистр 8.3, пройдя через вычитатель 5.. 3 и коммутатор 7,3, и появляется на выходе устройства. В этом же такте а 1 „

11

из регистра 8.1 переписывается в регистр 8.2, пройдя через вычитатель 5.2 и коммутатор 7.2. Кроме того, в этом же такте содержимое счетчиков 12.1 и 21.1 снова увеличивается на единицу, а поступает на вход устройства и далее записывается в блок памяти 9.1 по адресу (010) и в регистр 8.1, D-триггер 22.3 сбрасывается в нуль.

В четвертом такте 1 из регистра 8.2 переписывается в регистр.8.3 и появляется на выходе устройства, J., переписьшаеТся из регистра 8.1 в регистр 8.2, содержимое счетчиков 12.1 и 21.1 увеличивается на единицу, на выходе схемы 14.1 сравнения появляется единица, а 41 поступает на вход устройства и записывается в блок 9.1 памяти по адресу (01 Оо. и в регистр 8.1.

09933

В пятом такте 1 из регистра 8,2 переписывается в регистр 8.3 и появляется на выходе устройства, а, из регистра 8.1 переписывается в регистр 8.2, содержимое счетчиков и 26 увеличивается на единицу , D-триггер 16.1, устанавливается в единицу, RS-триггер 19.1 сбрасывается в нуль, счетчик 12.1 и схема 14.1 сравнения также сбрасываются в нулевое состояние, а jпоступает с входа устройства через коммутатор 3.1 (на выходе элемента ИЛИ 13о1 - 15 нуль) на второй вход блока 4.1, на первьй вход которого выдается из блока 9.1 памяти из ячейки с адресом (000) ,2. поступающим с выхода счетчика 12.1, значение а.., блок 4.1 выпол10

20 няет операцию деления, и с его выхода а,,|/а,и,4, пройдя через коммутатор 7.1 (на выходе элемента ИЛИ 24.1 - нуль), записывается в регистр 8.1, и, пройдя через коммутатор 6.1 (на выхо25 де RS-тригтера 19.1 - нуль), записывается в блок 9.1 памяти по адресу (100), поступающему со счетчика 21.1 .

В шестом такте l, из регистра 8.2

0

0

переписывается в регистр 8.3 и появляется на выходе устройства, из регистра 8.1 переписывается в регистр 8.2, р-триггер 16.1 сбрасывается в нуль, содержимое счетчика

12.1 увеличивается на единицу, а

счетчика 21.1 не меняется, а„.поступает с входа устройства на второй вход вычитателя 5.1, с первого выхода блока 9.1 памяти (на выходе элемента ИЛИ 20..1 - нуль) на первый вход коммутатора 3.1 вьщается U (из ячейки с адресом (100),j, поступающим с выхода счетчика 21 о 1), коммутатор 3.1 выдает второй вход блока 4.1 (единица на выходе элемента ИЛИ 13.1), на первьй вход блока 4.1, которьй выполняет умножение, поступает а,из блока 9.1 памяти (из ячейки с адресом (001) 2, поступающим с выхода счетчика 12.1), и с выхода блока 4.1 полученное произведение поступает на вычитатель, с выхода которого xU,l принимается в регистр 8. Г, пройдя через коммутатор 7.1. В этом

5 же такте D-триггер 23.1 сбрасывается в нуль (т.е, на его инверсном выхо- де - единица).

В седьмом такте и.,,из регистра 8.2- переписывается в регистр 8.3 и появ-

5

0

гг 21

71509933 . 8

ляется на выходе устройства, письшается в блок 9.1 памяти по ад- регистра 8.1 переписывается в регистр ресу (101),,, поступающему со счетчи- 8.2 и в блок 9.2 памяти (по адресу (000),, поступающему с выхода счетчика 21.2). Содержимое счетчика 12.1 увеличивается на единицу, а счетчика

ка 21.1.

В десятом такте регистра 8.2 переписывается в регистр 8.3 и появляется на выходе устройства, из регистра 8.1 Переписывается в регистр 8.2, счетчики 12.2; 21.2 и

,21.1 - не меняется, а поступает с входа устройства на второй вход выписьшается в блок 9.1 памяти по ад- ресу (101),,, поступающему со счетчи-

ка 21.1.

В десятом такте регистра 8.2 переписывается в регистр 8.3 и появляется на выходе устройства, из регистра 8.1 Переписывается в регистр 8.2, счетчики 12.2; 21.2 и

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Предложенное устройство позволяет сократить аппаратурные затраты за счет уменьшения количества процессорных элементов и связей их с блоком синхронизации. Сущность работы устройства состоит в том, что оно раскладывает квадратную матрицу A = [A_IJ] размерности N на две треугольные: нижнюю левую L и верхнюю правую U, такие, что LU = A. ПРИЧЕМ НА ГЛАВНОЙ ДИАГОНАЛИ МАТРИЦЫ U СТОЯТ ЕДИНИЦЫ. ПРЕОБРАЗОВАНИЕ МАТРИЦЫ A ВЫПОЛНЯЕТСЯ ПО АЛГОРИТМУ ИСКЛЮЧЕНИЯ ГАУССА, В ПРОЦЕССЕ КОТОРОГО ПОЛУЧАЮТСЯ ЭЛЕМЕНТЫ L_IJ И U_IJ. 3 ИЛ.

читателя 5.1, с первого выхода блока д 12.1 увеличивают свое состояние на памяти (через коммутатор 3.1) на единицу, на выходе схемы 14.2 сравнения появляется с входа устройства на вход вычитателя 5.1, с первого

вход блока А.1 вьщается а„, а с втовыхода блока 9.1 памяти через комрого выхода блока 9.1 памяти выдается а, (из ячейки с адресом (010), с выхода блока 4.1 полученное произве- 15 мутатор 3.1 на вход блока 4.1 посту- дение поступает на вычитатель 5.1, пает (no адресу (101), поступающему со счетчика 21.1), на первый вход блока 4.1 поступает из ячейки.

с выхода которого j,-U ,1 Р нимается в регистр 8.1. В этом же такте D-триггер 10.2 устанавливается в единицу.

В восьмом такте регистра 8„2 переписывается в регистр 8.3 и появляется на выходе устройства, счетчики 12.1; 12.2 и 21.2 увеличивают свое состояние на единицу, 1 25 из регистра 8.1 переписывается в регистр 8.2 и записывается в блок 9.2 памяти по адресу (001 )«i, на выходе схемы 14.1 сравнения - единица, .

с адресом (001)2 значения а,, блок

20 4.1 выполняет умножение, на выходе вычитателя 5.1 получают значение a, ,j-a , , которое принимается в регистр 8.1, пройдя через коммутатор 7.1 ..

В одиннадцатом так.те U,j из регистра 8.2 переписывается в регистр 8.3 и появляется на выходе устройства, счетчики 12.1 и 21.2 увеличивают свое состояние на единицу, D-триггер

В одиннадцатом так.те U,j из регистра 8.2 переписывается в регистр 8.3 и появляется на выходе устройства, счетчики 12.1 и 21.2 увеличивают свое состояние на единицу, D-триггер

поступает с входа устройства на30 16.2 устанавливается в единицу, а I вход вычитателя 5.1, с первого счетчик 12.2 и RS-триггер 19.2 сбра- выхода блока 9.1 памяти на сываются в нуль, а из регистра 8.1 вход .блока 4.1 выдается U, , а поступает через коммутатор 3.2 на с. второго выхода блока 9.1 памяти вы- второй вход блока 4.2, на первый

дается а 4,(из ячейки с адресом35 вход из блока 9.2 памяти выдается (011),с выхода блока 4.1 полученное произведение поступает на вычитатель 5.1, с выхода которого а 4-г

1 пру ккмается в регистр 8,1

значение 1(из ячейки с адресом (000) ,j, поступающим со счетчика 12.2), блок 4.2 выполняет деление.

и с его выхода а /l i U записыва23 гг

В девятом такте 1„переписывает- 40 ется в регистр 8.2 и, пройдя через

ся из регистра 8.2 в регистр 8.3 и появляется на выходе устройства, счетчики 12.2; 26; 21.1;.21.2 увеличивают свое состояние на единицу.

коммутатор 6.2, записывается в блок 9,2 памяти, по адресу (lOO)j., поступающему с выхода счетчика 21,2.В этом же такте а поступает с входа

коммутатор 6.2, записывается в блок 9,2 памяти, по адресу (lOO)j., поступающему с выхода счетчика 21,2.В этом же такте а поступает с входа

регистра 8.1 переписывается в дз устройства на вход вычитателя 5.1, с

регистр 8.2 и записывается в блок 9.2 памяти по адресу (010), D-триггер 16.1 устанавливается в единицу, счетчик 12.1 и схема 14.1 сравнения сбрасьшаются в нуль, поступает с входа устройства через коммутатор 3.1 на второй вход блока 4о1, на первый вход которого из блока 9.1 памяпервого выхода блока 9.1 памяти на второй вход блока 4.1 поступает U,, на первый вход его из блока 9,1 памяти выдается ячейки с адресом 50 (OlO)j, блок 4о1 вьшолняет умножение, и на выходе вычитателя 5,1 получают зна чение aai-Uij-aj, , которое принимается в регистр 8.1.

первого выхода блока 9.1 памяти на второй вход блока 4.1 поступает U,, на первый вход его из блока 9,1 памяти выдается ячейки с адресом 50 (OlO)j, блок 4о1 вьшолняет умножение, и на выходе вычитателя 5,1 получают зна чение aai-Uij-aj, , которое принимается в регистр 8.1.

В двенадцатом такте регистти вьщается (из ячейки с адресом

(OOO)i) значение а,, блок 4,1 выпол- 55ра 8,2 переписьюается в регистр 8.3,

няет операцию деления, и с его выхо-D-триггеры 16.2 и 23.2 сбрасываются

да а,/а -, и,j, пройдя через крймута-в нуль, счетчики 12,2 и 12.1 увелитор 7.1, записывается в регистр 8,1,чивают свое состояние на единицу,

и, пройдя через коммутатор 6,1, за-aVjHS регистра 8,1 поступает на вход

выхода блока 9.1 памяти через коммутатор 3.1 на вход блока 4.1 посту пает (no адресу (101), поступающему со счетчика 21.1), на первый вход блока 4.1 поступает из ячейки.

с адресом (001)2 значения а,, блок

В одиннадцатом так.те U,j из регист ра 8.2 переписывается в регистр 8.3 и появляется на выходе устройства, счетчики 12.1 и 21.2 увеличивают свое состояние на единицу, D-триггер

вход из блока 9.2 памяти выдается

значение 1(из ячейки с адресом (000) ,j, поступающим со счетчика 12.2), блок 4.2 выполняет деление.

и с его выхода а /l i U записыва23 гг

ется в регистр 8.2 и, пройдя через

коммутатор 6.2, записывается в блок 9,2 памяти, по адресу (lOO)j., поступающему с выхода счетчика 21,2.В этом же такте а поступает с входа

устройства на вход вычитателя 5.1, с

первого выхода блока 9.1 памяти на второй вход блока 4.1 поступает U,, на первый вход его из блока 9,1 памяти выдается ячейки с адресом (OlO)j, блок 4о1 вьшолняет умножение, и на выходе вычитателя 5,1 получают зна чение aai-Uij-aj, , которое принимается в регистр 8.1.

В двенадцатом такте регистра 8,2 переписьюается в регистр 8.3,

вычитателя 5.2, с первого выхода блока 9.2 памяти, через коммутатор 3.2 на вход блока 4.2 поступает , на первый вход блока 4.1 поступает из блока 9.2- памяти Ijj , блой 4.2 выполняет умножение, и на выходе вычитателя 5.2 получают значение аjj-Ujj-12 1зд, которое записывается в регистр 8.2. В этом же такте а поступает с входа устройства на вход вычитателя 5.1, с первого выхода блока 9.1 памяти, на второй вход блока 4.1 поступает U,, на первый

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

вход блока 4.1 поступает из блока 9 памяти а, , блок 4.1 выполняет умножение , и на выходе вычитателя 5.1 получают значение a, , jQ которое принимается в регистр 8.1.

В пятнадцатом такте D-триггер 16.2 устанавливается в единицу, счетчик 12.2 и RS-триггер 19.2 сбра .сьшается в нуль. Счетчики 12.3;

вход его из блока 9.1 памяти вьщается 15 21.3; 21.2 и 12.1 увеличивают свое

блок 4.1 выполняет умножение, и на выходе вычитателя 5.1 получают значение а ,,, а. -а, которое принимается в регистр 8.1. В этом же такте D-триггер 23.2 сбрасывается в 20 нуль, а на выходе схемы 14.1 сравнения появляется единица.

В тринадцатом такте D-триггер 10.3 устанавливается в единицу, Ijj из регистра 8.2 переписывается в ре- 25 блок 9.2 памяти по адресу (101). В

состояние на единицу, U, из регистра 8.2 переписывается в регистр 8.3. В этом же такте а Диз регистра 8.1 поступает через коммутатор 3.2 на второй вход блока 4.2, на первый вход которого из блока 9.2 памяти выдается Iji, блок 4.2 выполняет деление, и с его выхода значение а./ /1,,24записьгоается в регистр 8.2 и

гистр 8.3 и, пройдя через .коммутатор 6.3, записывается в блок 9.3 памяти по адресу (000). В этом же такте счетчики 21.1; 12.2 и 26 увеличивают свое состояние на единицу, а счетчик 12.1 сбрасывается в нуль, а/ из ое- гистра 8.1 поступает на вход вычитателя 5.2 с первого выхода блока 9.2 памяти на второй вход блока 4.2 поступает , на первый вход его из блока 9.2 памяти поступает 141 блок 4.2, вьшолняет умножение, и на выходе вычитателя 5.2 получают значение i l42 l vi которое записывается в регистр 8.2. В этом же такте а,поступает на второй вход блока 4.1, на первый вход которого из блока 9.1 памяти вьщается значение а ,, ,. блок 4.1 выполняе т операцию деления, и с его выхода записывается в регистр 8.1 и, пройдя через коммутатор 6.1 - в блок 9.1 памяти по адресу (МО), поступающему со счетчика 21.1.

В четырнадцатом такте счетчики 12.3; 21.3; 12.2 и12.1 увеличивают свое состояние на единицу, единица -появляется на выходе схемы 14.. 2 сравнения, 145из регистра 8.2 переписывается в регистр 8.3 и, пройдя через коммутатор 6.3, записьшается в блок 9.3 памяти по адресу (00О. В этом же такте U из регистра 8.1 переписьшается в регистр 8.2,

этом же такте входа устройства поступает на вход вычитателя 5.1, с первого выхода блока 9.1 памяти на второй вход блока 4.1 поступает 30 на первый вход блока 4.1 поступает из блока 9.1 памяти а 31 , блок 4.1 вы полняет умножение, и на выходе вычи- тателя 5.1 получают значение а,л-и..

(ч

31 i-f

40

которое принимается в ре„ гистр 8.1.

В шестнадцатом такте счетчики 12.3; 21.3; 12.2 и 12.1 увеличивают свое состояние на единицу, на выходах схем 14.1 и 14.3 сравнения тоже единицы, переписывается из регистра 8.2 в регистр 8.3. В этом же такте а из регистра 8.1 поступает на вход вычитателя 5.2, с первого выхода блока 9.2 памяти на второй

д5 вход блока 4.2 поступает U, на пер вьй вход блока 4.2 поступает из блока 9.2 1за блок 4.2 выполняет умножение, и на выходе вычитателя 5.2

получают значение -я - 3,,

5Q которое принимается в регистр 8.2.В этом же такте входа устройства поступает на вход вычитателя 5.1, с первого выхода блока памяти на вто рой вход блока 4.1 поступает U , , на

ее первый вход блока 4.1 поступает из

блока 9.1 памяти а

41

блок 4.1 вьшол

няет умножение, и на выходе вычитате ля 5.1 получают значение .4, 344 которое принимается в регистр.8

150993310

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

вход блока 4.1 поступает из блока 9. памяти а, , блок 4.1 выполняет умножение , и на выходе вычитателя 5.1 получают значение a, , jQ которое принимается в регистр 8.1.

В пятнадцатом такте D-триггер 16.2 устанавливается в единицу, счетчик 12.2 и RS-триггер 19.2 сбра- .сьшается в нуль. Счетчики 12.3;

блок 9.2 памяти по адресу (101). В

состояние на единицу, U, из регистра 8.2 переписывается в регистр 8.3. В этом же такте а Диз регистра 8.1 поступает через коммутатор 3.2 на второй вход блока 4.2, на первый вход которого из блока 9.2 памяти выдается Iji, блок 4.2 выполняет деление, и с его выхода значение а./ /1,,24записьгоается в регистр 8.2 и

этом же такте входа устройства поступает на вход вычитателя 5.1, с первого выхода блока 9.1 памяти на второй вход блока 4.1 поступает 0 на первый вход блока 4.1 поступает из блока 9.1 памяти а 31 , блок 4.1 выполняет умножение, и на выходе вычи- тателя 5.1 получают значение а,л-и.. х

(ч

31 i-f

0

которое принимается в регистр 8.1.

В шестнадцатом такте счетчики 12.3; 21.3; 12.2 и 12.1 увеличивают свое состояние на единицу, на выходах схем 14.1 и 14.3 сравнения тоже единицы, переписывается из регистра 8.2 в регистр 8.3. В этом же такте а из регистра 8.1 поступает на вход вычитателя 5.2, с первого выхода блока 9.2 памяти на второй

5 вход блока 4.2 поступает U, на пер- вьй вход блока 4.2 поступает из блока 9.2 1за блок 4.2 выполняет умножение, и на выходе вычитателя 5.2

получают значение -я - 3,,

Q которое принимается в регистр 8.2.В этом же такте входа устройства поступает на вход вычитателя 5.1, с первого выхода блока памяти на второй вход блока 4.1 поступает U , , на

е первый вход блока 4.1 поступает из

блока 9.1 памяти а

41

блок 4.1 вьшолняет умножение, и на выходе вычитателя 5.1 получают значение .4, 344 которое принимается в регистр.8„1.

Формула изобретени} - 1. Устройство для LU-разложения

ных блоков и блок синхронизации, вы, ход которого подключен к первому управляющему входу первого операционустройства, информационный вход i-ro операционного блока (, ti-l) подключен к информационному выходу

20

П150993312

.I

В семнадцатом такте счетчик 26 увеличивает свое состояние на единицу, на выходе схемы 27 сравнения появляется единица, RS-триггер 28 устанав- матриц, содержащее п-1 (п - размер- ливается в единицу, счетчики 26, 12.1 ность разлагаемой матрицы) операцион- и 21.1 и D-триггеры 10.1 и 16.1 устанавливаются в нулевое состояние, таким образом происходит подготовка к обработке следующей исходной матри- 10 ного блока, информационньй вход коды. В этом же такте счетчик 12.3 сбра- . торого является информационным уходом сьшается в нуль, счетчики 21.3 и 12. увеличивают свое состояние на единицу, а -Д из регистра 8.2 поступает через коммутатор 3.3 на второй 15 (i-l)-ro операционного блока, а ин- вход блока 4.3, на первьш вход кото- формационный выход (п-1)-го операционного блока является выходом устройства, отличающе. еся тем, что, с целью сокращения аппаратурных затрат, первый и второй управляющие входы i-ro операционного блока подключены соответственно к первому и второму управляющим выходам (i-l)-ro операционного блока, 25 второй и третий управляющие входы первого операционного блока подключены соответственно к входам логической единицы и логического нуля устройства, а третьи управляющие вхо- 30 ды остальных операционных блоков подключены к входу логической единицы устройства, третий управляющий выход первого операционного блока подключен к первому входу блока синх- 35 ронизации, второй вход которого является управляющим входом устройства.

Б последнем (восемнадцатом) такте D-триггер 22.1 и RS-триггер 19.2 устанавливаются в единицу, сяетчик 12.3 увеличивает свое состояние на единицу, а .счетчики 12,2 и 21.2 и D-триггеры 10.2 и 16.2 сбрасываются в нуль. В этом же такте регистсостояние на единицу, с первого да блока 9.3 на второй вход блока

На этом разложение квадратной матрицы-А Са,-j размерности заканчивается. Поскольку каждьй элемент входной матрицы А используется в каждом данном процессорном элементе

только один раз, можно выполнять LU- ду второго коммутатора и к информа- разложение потока матриц. Каждую ционному входу операционного блока,

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

Формула изобретени} - 1. Устройство для LU-разложения

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

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

устройства, информационный вход i-ro операционного блока (, ti-l) подключен к информационному выходу

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

13

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

дж

2

509933

ключены к входам пятого элемента ИЛИ,

первому адресному входу блока памяти и к входам первой группы схемы сравнения, входы второй группы кото- рой соединены с входом задания N-1 в двоичном коде блока, выход схемы сравнения соединен с первым входом второго элемента И, входом второго .

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

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

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

30 которого соединен с вторым адресным входом блока памяти.

Фие.1