Устройство для матричных операций Советский патент 1992 года по МПК G06F15/347 

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

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

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

модулей и решающее систему Ах7 b за время 4п2 + п + 2 тактов (см. Многофункциональные систологические структуры, под ред. Я.А.Дуброва. Препринт № 20 - 89, Львов - 1989. ин-т прикладных проблем механики и математики АН УССР, с.38). Недостатком этого устройства является невозможность реализации на нем Ш-раз- ложения матриц.

Наиболее близким к изобретению является устройство для Ш-разложения матриц, содержащее (п - 1) операционных блоков и блок синхронизации, и ориентированные на реализацию в виде систолической СВИС 2 Оно выбрано в качестве прототипа.

Недостатком прототипа является невозможность реализации хода алгоритма Гаусса решения системы Ах Ь, т.е. решения системы b и с треугольными матрицами L и U.

ч

NJ VJ

-

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

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

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

выходами и связаны с синхровходами всех пычислительных модулей и блоков устройства, первый выход блока 5 подключен ко входу установки блока 3.

Вычислительный модуль 1.1 (i 1, (п - 1)

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

5 входом вычислительного модуля, первый выход которого подключен к выходу первого регистра 12, вход которого связан с выходом коммутатора 11, со входом данных узла памяти 13 и входом второго регистра 14,

0 выход которого подключен ко второму входу коммутатора 10, выход которого является первым входом блока 8, второй вход которого связан с выходом узла 13, адресный вход которого подключен к информационному

5 выходу счетчика 15, выход отрицательного переноса которого подключен ко входу первого D-триггера 16, к первому входу элемента И 17, и является четвертым выходом вычислительного модуля, вход признака на0 чала ввода столбца которого подключен ко входу второго D-триггера 18, S- входу RS - триггера 19, и входу установки в нуль D- триггера 16, выход которого связан с управляющим входом коммутатора 10, со входом

5 выбора режима блока 8, входом пропуска операнда вычитателя 9, с управляющим входом регистра 14, входом третьего D-триггера 20 и R-входом RS-триггера 19, выход которого является входом чтения-записи уз0 ла 13 и подключен к первым входам первого 21 и второго 22 элементов ИЛИ, вторые входы которых подключены соответственно, к выходам D-триггера 20 и элемента И 17, второй вход которого является входом при5 знака номера вычислительного модуля, вход синхронизации ввода элементов матрицы которого является входом выбора режима счетчика 15, информационный вход которого связан со входом (п -1) устройства,

0 выход вычитателя 9 подключен ко второму входу коммутатора 1, управляющий вход которого является выходом элемента ИЛИ 22, второй и третий выходы вычислительного модуля подключены к выходам соответст5 венно D-триггера 18 и элемента ИЛИ 21.

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

25 и является вторым информационным входом блока 4, первый информационный вход которого подключен к первому входу третьего коммутатора 26 и ко второму входу узла 23. выход которого подключен к перво- му входу вычитателя 27, выход которого связан со вторым входом коммутатора 26 и входом данных узла памяти 28, выход которого подключен ко вторым входам коммутаторов 24 и 25, третий вход коммутатора 24 является выходом первого регистра 29i, вход которого связан с выходом коммутатора 26, со входом второго регистра 292, и является первым выходом блока 4, второй выход которого подключен к выходу перво- го RS-триггера 30 и управляющему входу коммутатора 25, выход которого подключен ко второму входу вычитателя 27, вход начальной установки блока 4 подключен к первому входу первого 31 и второго 32 элементов ИЛИ, ко входу первого D-тригге- ра 33, и ко входу выбора режима первого счетчика 34, информационный выход которого подключен к информационному входу второго счетчика 35. выход отрицательного переноса которого подключен к S-входу второго RS-триггера 36, выход которого связан со входом разрешения записи регистра 292 и является третьим выходом блока 4, информационные входы первого 34, третьего 37 и четвертого38 счетчиков соединены соответственно со входами 1, п и (п - 1) устройства. выход D-триггера 33 подключен к S-входу RS-триггера 30 и к первому управляющему входу коммутатора 24, второй управляющий вход которого связан со входами выбора режима блока 23 и вычитателя 27, с управляющим входом коммутатора 26, со входом разрешения приема кода регистра 29i, и с выходом второго D-триггера 39. вход кото- рого подключен к выходу элемента ИЛИ 32 и ко входу выбора режима счетчика 37, выход отрицательного переноса которого соединен со вторым входом элемента ИЛИ 32 и с R-входом RS-триггера 30, R-вход тригге- ра 36 является выходом элемента И 40. первый вход которого подключен ко входам выбора режима счетчиков 35 и 38. и к выходу элемента ИЛИ 31. второй вход которого подключен к инкрементирующему входу счетчика 34 и к выходу отрицательного переноса счетчика 38, информационный выход которого является адресным входом узла 28, второй вход элемента И 40 и вход чтения - записи узла 28 подключены к выхо- ду 6 блока 2, выход D-триггера 33 является четвертым выходом блока 4.

Первый вычислительный блок 3 содержит умножитель 41, выход которого подключен к первому входу коммутатора 42, второй

вход которого подключен к пераому iy умножителя 41 и является информацией ным входом блока 3, выход которого подключен ко второму входу умножителя 41 и к выходу регистра 43, вход которого связан с выходом сумматора-вычитателя 44 и со входом данных узла памяти 45, выход которого подключен к первому входу сумматора- вычитателя 44, второй вход которого является выходом коммутатора 42, управляющий вход которого соединен со входом признака вычитания сумматора-вычитателя 44, со входом управления записью регистра 43 и с выходом элемента И 46, первый вход которого подключен к выходу первого 471 и ко входу второго 48 D-триггера. инверсный выход которого подключен ко второму входу элемента И 46, вход D-триггера 471 соединен с выходом элемента ИЛИ 49 и со входом выбора режима первого счетчика 50, выход отрицательного переноса которого связан с первым входом элемента ИЛИ 49 и с декре- ментирующим входом второго счетчика 51, вход выбора режима которого подключен ко второму входу элемента ИЛИ 49, ко входу установки в нуль D-триггера 48 и является входом установки блока 3, вход управления пропускном операнда которого связан через третий D-триггер 472 со входом у п равле- нияпропускомоперанда

сумматора-вычитателя 44, вход (п - 1) устройства связан с информационным входом счетчика 51, выход которого подключен к информационному входу счетчика 50, информационный выход которого является адресным входом узла 45, вход чтения-записи которого подключен к выходу 6 блока 2.

Блок синхронизации 2 содержит генератор синхроимпульсов 52 с инвертором, т.е. с прямым 6 и инверсным 7 тактовыми выходами, счетчик 53, декрементирующий вход которого подключен к первому входу первого элемента ИЛ И 54 и является входом признака окончания ввода столбца блока 2, первый выход которого связан со вторым входом элемента ИЛИ 54, с выходом D-триггера 55 и со входом выбора режима (параллельное занесение или счет в режиме вычитания) счетчика 53, информационный вход которого соединен со входом п устройства, выход отрицательного переноса счетчика 53 подключен к первому входу второго элемента ИЛИ 56, второй вход которого является входом запуска устройства.

Блок 5 памяти объемом п (п + 1) слов содержит два блока памяти объемом п (п + 1)/2 слов, имеющих одинаковую структуру В состав блока 5 входят блоки оперативной памяти 57i, 572, входы и выходы данных которых объединены и являются, соответственно, информационным входом и вторым выходом блока 5, коммутаторы 58i, 682, выходы которых являются адресными входами блоков 57. входы выбора которых подключены к выходам элементов ИЛИ 591, 592, и ко входам элементов сложения по модулю два 60ь 602. выходы которых подключены к син- хровходам счетчиков 611, 612, входы установки в нуль которых соединены с выходами элементов И621, 622, входы чтения-записи блоков 571 и 572, связаны, соответственно с управляющими входами коммутаторов 58i и 582, с первыми входами элементов ИбЗт и 632, элементов И 621 и 622 входами выбора режима (счет в режиме вычитания или суммирования) счетчиков 61 т и 612 и являются прямым и инверсным выходами jk-триггера 64, j-вход которого подключен ко входу логической единицы устройства, а k-вход - к прямому выходу триггера, синхровход которого является входом обнуления адреса блока 5 и связан со вторыми входами элементов 60, 62 и со входом D-триггера 652, выход которого является первым выходом блока 5. При этом подразумевается, что выходы блока 57 переходят в третье состояние, если блок не выбран (на выходе элемента 59-единица), или блок выбран, но не находится в режиме записи (на входе чтения-записи нуль), вход D-триггера 65i является входом синхронизации чтения блока 5.

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

Устройство для решения систем линейных алгебраических уравнений раскладывает исходную квадратную матрицу Асистемы Ах В размерности п, на нижнюю левую L ltj и верхнюю правую U Uij (у которой на главной диагонали стоят единицы) так, что Ш А, Шх - b согласно следующим формулам прямого хода алгоритма исключения Гаусса:

я W a..(k-D. ajjk 1 ) (k-i) я..(о)

aij a.jrk | aik , a,j - aij

a kx

k 1.n. I, j k + l.k + 2n;

Ukj aicj Vakk01 1 . k Cn; j k, k + 1n;

lik a,k(), k Гп, i k, k + 1n.

Затем устройство реализует обратный ход алгоритма Гаусса, который заключается в решении системы Ly b no формулам:

1 - 1

У (bi- 2 ikyiO/ ii. i 1, п к 1

и системы Ux b по формулам:

Х|

У1- 2 U.kXk, i n, n- 11.

к i+ 1

При этом прямой ход алгоритма выполняет вычислительные модули 1.1, а решение системы Ly b и Ux у выполняют соответственно блоки 4 и 3 устройства. Устройство позволяет выполнять как разложение потока

матриц, таки решение потока систем Ах Б с периодом п2 тактов. Однако в связи с тем, что корни Xi нельзя начинать вычислять до получения всех yi, в устройство введен блок 5, включенный таким образом, что пока блок4

вычисляет значения у системы Akxi bkH заполняет одну половину блока 5, блок 3 вычисляет значения х системы Ak-ix k-1 bk-1 (т.е. той, которая обрабатывалась перед ней), работая с другой половиной блока 5.

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

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

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

По сигналу Запуск и положительному

перепаду синхроимпульса с выхода 7 D- триггер 55 устанавливается в единицу, которая появляется на первом и втором выходах блока 2 синхронизации, а также поступает на

вход выбора режима счетчика 53, в который записывается значение п в двоичном коде, и на выходе отрицательного переноса которого появляется нуль независимо от состояния сигнала на декрементирующем входе счетчика 53. Кроме того, D-триггер 16.1 и R-S триггер 19.1 вычислительного модуля 1.1 устанавливаются, соответственно, в нуль и единицу,

В первом такте по положительному перепаду синхроимпульса с выхода 6 в счетчик

15.1 записывается значение (п -1), т.е. 3. на выходе отрицательного переноса счетчика 15.1 появляется нуль. На вход устройства подается значение an. которое поступает на первый вход коммутатора 11.1, и с его выхода записывается в узел памяти 13.1 по адресу 3, и в регистр 12.1. В этом же такте единица из D-триггера 55, переписывается в D-триггер 18.1, а D-триггер 55 сбрасывается в нуль. Таким образом, на обеих управляющих выходах модуля 1.1 находятся единицы, а на управляющих входах - нули, D-триггер 16.2 и RS-триггер 19.2 модуля 1.2 устанавливаются в нуль и единицу соответственно.

Во втором такте счетчик 15.1 уменьшает свое содержимое на единицу, на вход вычислительного модуля 1,2 подается аи , которое поступает на первый вход коммутатора 11,2, и с его выхода записывается в узел памяти 13.2 по адресу 3 и в регистр 12.2. В том же такте 321 подается на вход устройства и записывается в узел памяти 13.1 по адресу 2 и в регистр 12.1, пройдя через коммутатор 11.1, единица из D-триггера 18.1 переписывается в D-триггер 18.2, RS-триггер 16.3 и RS-триггер 19.3 устанавливаются в нуль и единицу соответственно.

В третьем такте счетчик 15.1 уменьшает свое значение на единицу, на вход модуля 1.3 подается an In, которое записывается в узел памяти 13.3 (по адресу 3), в регистр 12.3 появляется на первом выходе устройства и первом входе блока 4, 321 поступает на вход модуля 1.2 и записывается в узел памяти 13.2 по адресу 3, на вход устройства поступает аз1 и записывается в узел памяти 13.1 по адресу 1 и в регистр 12.1; единица из D-триггера 18.2 переписывается в D- триггер 18.3 и поступает на управляющий вход блока 4.

В четвертом такте счетчик 15.1 уменьшает свое значение на единицу, т.е. до нуля, и на его выходе отрицательного переноса появляется единица, которая поступает на декрементирующий вход счетчика 53, и уменьшает его состояние на единицу, на вход модуля 1.3 подается 321 121. которое записывается в узел памяти 13.3 (по адресу 3), в регистр 12.3 и появляется на первом выходе устройства. аз1 переписывается из регистра 12.1 в регистр 12.2, на вход устройства поступает 341 и записывается в узел памяти 13.1 по адресу ;(г , и в регистр 12.1, на вход выбора режима счетчика 15.1 также поступает единица.

В пятом такте D-триггер 16.1 устанавливается в единицу, RS-триггер 19.1 - в нуль, всчетчик 15.1 вновьзаписывыетсязначение

(п - 1), т.е. 3, аз1 1з1 перепг.с зетсч и.1 регистра 12.2 в регистр 12.3 и появляется на первом выходе устройства, а-ц переписывается из регистра 12.1 в регистр 12.2, аг2 5 поступает со входа устройства через коммутатор 10.1 на первый вход блока 8.1, на второй вход которого поступает an из узла памяти 13.1 (из ячейки с адресом 3), блок 8.1 выполняет операцию деления, и с его выхог

0 да ai2/an 1112 поступает на первый вход вычитателя 9.1, который осуществляет пропуск операнда, и ui2 записывается в регистры 12.1 и 14.1.

В шестом такте an Ui переписывается

5 из регистра 12.2 в регистр 12.3 и появляется на первом выходе устройства, ui2 из регистра 12.1, переписывается в регистр 12.2, D- триггеры 16.1 и 20.1 устанавливаются, соответственно, в нуль и единицу, счетчик

0 15.1 уменьшает свое значение на единицу. 322 поступает со входа устройства на второй вход вычитателя 9.1, коммутатор 10.1 пропускает U12 из регитсра 14.1 на первый вход блока 8.1, на второй вход которого поступа5 ет 321 из ячейки с адресом 2 узла памяти 13.1, блок 8.1 выполняет умножение, вычи- татель 9.1 - вычитание, и с его выхода результат 322-321 ui2 I22 принимается в регистр 12.1, пройдя через коммутатор 11.1

0В седьмом такте im из регистра -1 2

переписывается в регистр 12.3 и появляется на первом выходе устройства, счетчик 15.1 уменьшает свое значение на 1, в счетчик 15.2 записывается значение (п - 1), т.е. 3,

5 D-триггер 20.1 сбрасывается в нуль, I22 из регистра 12.1 переписывается в регистр 12.2 и записывается в узел пэмяти 13.2 по адресу 3, аз2 поступает со входа устройства на второй вход вычитателя 9.1, U12 из реги0 стра 14.1 поступает на первый вход блока 8.1, на второй вход которого поступает азт из ячейки с адресом 1 узла памяти 13.1 и результат аз2-аз -и12 1з2 с выхода вычитателя 9.1 принимается в регистр 12.1.

5 В восьмом такте 122 из регистра 12.2 переписывается в регистр 12.3 и появляется на первом выходе устройства, счетчики 15.1 и 15.2 уменьшают свое значение на единицу, на выходе отрицательного переноса

0 счетчика 15.1 появляется единица, которая уменьшает содержимое счетчика 53 и появляется на входе выбора режима счетчика 15.1, 1з2 из регистра 12.1 переписывается в регистр 12.2 и записывается в узел памяти

5 13.2 по адресу 2, 342 поступает со входа устройства на второй вход вычитателя 9.1, а 12 поступает на первый вход блока 8.1, на второй вход его поступает из ячейки Ј узла памяти 13.1 и результат a42-34i-ui2 U2 принимается в регистр 12.1.

В девятом такте 1з2 из регистра 12.2 переписывается в регистр 12.3 и появляется на первом выходе устройства, далее, аняло- гично пятому такту, D-триггера 16.1 устанавливается в единицу, в счетчик 15.1 вновь записывается значение (п -1), 142 переписывается в регистр 12.2 и записывается в узел памяти 13,2 по адресу 1, ai3 поступает со входа устройства на первый вход блока 8.1, на второй вход которого поступает аи из ячейки 3 узла памяти 13.1, блок 8.1 выполняет деление и результат а1з/ац тз, пройдя без изменений через вычитатель 9.1, записывается в регистры 12.1 и 14.1.

В десятом такте 42 из регистра 12.2 пе- реписывается в регистр 12.3 и появляется на первом выходе устройства, счетчики 15.1 и 15.2 уменьшают свое значение на единицу, на выходе отрицательного переноса счетчика 15.2 появляется единица, которая поступает через элемент И 17.2 на второй вход элемента ИЛИ 22.2, ичз из регистра

12.1переписывается в регистр 12,2, D-триг- гер 20.1 устанавливается в единицу, a D- триггер 16.1 - в нуль, 323 поступает со входа устройства на второй вход вычитагеля 9.1 U13 из регистра 14.1 поступает на первый вход блока 8.1, на второй вход его поступает 321 из ячейки 2 узла 13.1, и с выхода вычита- теля 9.1 значение Э23-и1з а21 Э231 прини- мается в регистр 12.1.

В одиннадцатом такте щз из регистра

12.2переписывается в регистр 12.3, счетчик

15.1уменьшает свое значение на единицу, D-триггер 16.2 и RS-триггер 19.2 устанавли- вэются, соответственно, в единицу и нуль, в счетчик 15.2 записывается значение (п - 1), 323 из регистра 12,1 поступает на первый вход блока 8.2, на второй вход которого поступает I22 из ячейки 3 узла памяти 13.2 блок 8.2 выполняет деление, вычитатель 9.2 - пропуск операнда, и результат U23 323/122 записывается в регистры 12.2 и 14.2. В этом же такте азз поступает со входа устройства на второй вход вычитателя 9.1, итз из регистра 14.1 поступает на первый вход блока 8.1, на второй вход его поступает эз1 из ячейки 1 узла памяти 13.1, и результат азз ui3 аз1 азз принимается в регистр 12.1.

В двенадцатом такте D-триггеры 16.2 и

20.2устанавливаются, сооответственно, в нуль и единицу, счетчики 15.1 и 15.2 уменьшают свое значение не единицу, на выходе отрицательного переноса счетчика 15.1 по- является единица, которая уменьшает содержимое счетчика 53 и появляется на входе выбора режима счетчика 15.1, U25 переписывается в регистр 12.3 и появляется на первом выходе устройства, азз из регистра

12.1 поступает на второй вход вычитателя 9.2 на первый вход блока 8.2 поступает U23 из регистра 14,2, на второй его вход - 1з2 из ячейки 2 узла памяти 13.2, и результат азз- -U23 1з2 зз принимается в регистр 12.2. В этом же такте 343 поступает со входа устройства на второй вход вычитателя 9.1, щз умножается на блоке 8.1 на а/п из ячейки / УП 13.1 и результат 343-и 13 341 343 принимается в регистр 12.1.

В тринадцатом такте в счетчики 15.3 и

15.1записывается значение (п - 1), т.е. 3, D-триггер 20.2 сбрасывается в нуль, счетчик

15.2уменьшает свое значение на единицу, D-триггер 16.1 устанавливается в единицу, зз записывается в регистр 12.3 и в узел памяти 13.3 по адресу 3, 343 из регистра 12.1 поступает на второй вход вычитателя 9.2, на первый вход блока 8.2 поступает U23, на второй его вход - U2 из ячейки I узла памяти 13.2 и результат Э4з 1 U23 U2 Цз записывается в регистр 12.2. В этом же такте ai4 поступает со входа устройства на первый вход блока 8.1, на второй вход которого поступает аи из ячейки 3 узла памяти

13.1,блок 8.1 выполняет деление, и результат аи/аи U24 записываемся в регистры 12.1 и 14.1.

В четырнадцатом такте счетчики 15.1 и

15.2,15.3 уменьшают свое значение на единицу, на выходе отрицательного переноса счетчика 15,2 появляется единица, которая поступает через элементы И 17.2 и ИЛ И 22.2 на управляющий вход коммутаторэ 11.2, D- триггер 20.1 устанавливается в единицу, а D-триггер 16.1 - в нуль, Мз из регистра 12.2 переписывается в регистр 12.3 и записывается в узел 13.3 по адресу 2, m/j из регистра 12.1 переписывается в регистр 12,2. пройдя через коммутатор 11.2, 324 поступает со входа устройства на второй вход вычитателя 9.1, на первый вход блока 8.1 поступает U14. на второй его вход - 321 из ячейки 2 узла памяти 13.1, и результат a24-ui4«a2i 324 принимается в регистр 12.1.

В пятнадцатом такте счетчики 151 и

15.3уменьшают свое значение на единицу, в счетчик 15.2 записывается значение (п -1), D-тригггер 16.2 устанавливается в единицу, ui4 переписывается из регистра 12.2 в регистр 12,3 и появляется на первом выходе устройства, 324 из регистра 12.1 поступает на первый вход блока 8.2. на второй вход которого поступает I22 из ячейки 3 узла 13.2, блок 8.2 выполняет деление, вычитатель 9.2 - пропуск операнда, и результат a24(1Vl22 U24 зэписывается в регистры 12.2 и 14.2. В этом же такте аз4 поступает со входа устройства на второй вход вычитэтеля 9.1, ui4 из регистра 14.1 поступает на первый вход блока 8.1, на второй вход его поступает азт из ячейки I узла памяти 13.1 и результат азф-ин аз1 принимается в регистр 12.1,

В шестнадцатом такте счетчики 15.1, 15.2,15.3. уменьшают свое значение на еди- ницу, на выходах отрицательного переноса счетчиков 15.3 и 15.1 появляются единицы, D-триггер 20.2 также устанавливается в единицу, U24 переписывается из регистра 12.2 в регистр 12.3 и появляется на первом выходе устройства, счетчик 53 уменьшает свое значение на единицу (и его содержимое становится равным нулю), и на его выходе отрицательного переноса появляется единица, которая записывается в D-триггер 55 по переднему фронту синхросигнала с выхода 7. Таким образом, устройство подготавливается к обработке элементов следующей матрицы. В этом же такте аз4 из регистра 12.1 поступает на вычитатель 9.2, на первый вход блока 8.2 поступает U24, на второй его вход - 1з2 из ячейки 2 узла памяти 13.2, и результат аз4 - U24 I32 эз4 записывается в регистр 12.2, 344 со входа устройства поступает на вычитатель 9.1. на первый вход бло- ка 8.1 поступает сщ. на второй его вход поступает 341 из ячейки ; узла памяти

13.1и результат а44 ui4 341 а/и принимается в регистр 12.1. В этом же такте после установки в единицу D-триггера 55, D-триг- rep 16.1 и RS-триггер 19.1 устанавливаются соответственно, в нуль и единицу, а в счетчик 53 записывается п.

В семнадцатом такте в счетчики 15.1 и 15.3 записывается значение (п -1), D-триггер

20.2сбрасывается в нуль, счетчик 15.2 уменьшает свое значение нв 1, D-триггеры 16.1 и 16.3 устанавливаются в единицу RS- триггер 19.3 сбрасывается в нуль, аз4 из регистра 12.2 поступает на первый вход бло- ка 8.3, на второй вход которого поступает зз

из ячейки 3 узла памяти 13.3, блок 8.3 выполняет деление, и результат из4 записывается в регистры 12.3 и 14.3 и поступает на первый выход устройства, 344 из регистра 12.1 поступает на вычитатель 9.2, на первый вход блока 8.2 поступает U24, на второй его вход - 142 из ячейки I узла памяти 13.2, и результат ад4 U24 I42 344 записывается в регистр 12.2, на вход устрой- ства поступает элемент an следующей матрицы, при этом действия выполняются аналогично первому такту.

В восемнадцатом такте D-триггер 16.3 сбрасывается в нуль. 344 из регистра 12.2 поступает на вычитатель 9.3. счетчик 15.3 уменьшает свое значение на 1. на первый вход блока 8,3 поступает из4. на второй его вход - 143 из ячейки 2 узла памяти 13.3, и результат Э44-- из4 Мз U4 принимается в

регистр 12.3 и погоняется н серягч вы ,ле устройства. По отношение к элементам следующей матрицы действия выполняются аналогично второму такту.

Далее работа устройства продолжается аналогично с периодом п2 тактов

Таким образом, время LU-рэзложенип матрицы в поточном режиме равно п тактов.

Продолжим рассмотрение работы устройства. При реализации обработного хода алгоритма Гаусса все ранее принятые условия продолжают иметь силу. Поступление исходных для блока 4 данных соответствует поступлению элементов ц, Uij на выход модуля 1.3. Таким образом, элемент hi поступает в блок 4 в четвертом такте. 121 в пчтом, и т.д. Элементы bi(i -- 1 п) вектора b системы Ах Ьпоступают, начиная с четвертого такта (по одному за такт и порядке возрастания i), со второго информационного входа устройства.

Как уже отмечалось выше, в третьем так- ге D-триггср 18.3 устаналивается в единицу, которяя, поступая на управляющий вход блока 4, поступает на входы выбора режима счетчиков 35, 37 и 38 (через элементы ИЛИ 31 и 32). на входы D-триггеров 33 и ЗР. ни первый вход элемента И 40, и на вход оь бо- ра режима счетчика 34, в которой cpasv же записывается единица. Таким образом поо- исходит начальная установка блока 4.

В четвертом такте по переднему фронту синхросигнала с выхода б в счетчики 35, 37 и 38 записывается, соответственно, значения 1, п и (п - 1), D-трпггеры 33 и Я9 устанавливаются в единицу, а RS-григгеры 30 и 36 -соответственно, ведичицу и нуль, единица с выхода D-триггера 33 поступает но первый управляющий вход блока 5, сбрасывая в нуль один из счетчиков 61 (в зависимости от состояния jk-триггера 64). Пусть, например, при подаче единицы на вход выбора режима счетчика 61, он работает в режиме вычитания единицы, а при подаче нуля - в режиме суммирования единицы, и пусть jk- триггер 64 находится в единице, Тогда сбрасывается в нуль счетчик 611, с его выхода нулевой адрес через коммутатор 58i поступает на адресный вход блока памяти 57i, счетчик 612 не меняет своего состояния, поскольку на выходе элемента И 622 - нуль, а единица на синхровходесчетчика 612 блокируется (остается) единицей на первом управляющем входе блока 5. В этом же такте 1ц с выхода вычислительного модуля 1.3 поступает на второй вход блока 23, на первый вход которого поступает h со второго входа устройства (через коммутатор 24), блок 23 выполняет деление, вычитатель 27 - пропуск операнда, и через коммутатор 26 значение i/ln yi принимается в регистры 29 и записывается в узел памяти 28 (по адресу 3) по нулевому уровню сигнала чтения-записи (поступающего с выхода 6), а также посту- паетна входы данных блоков571, 57.. Кроме того, D-триггер 65i сбрасывается в нуль, а 652 устанавливается в единицу, которая поступает на вход установки блока 3, устанавливая D-триггер 48 в нуль, и записывая в счетчик значение (п - 1).

В пятом такте по переднему фронту синхросигнала с выхода 6 триггер 64 сбрасывается в 0, по нулевому уровню синхросигнала с выхода 7 происходит запись в блок памяти 57ч о ячейку 0 значения yi, из блока 57z из ячейки с предыдущим адресом (т.к. счетчик 61а не поменял свое состояние) считывается на вход блочка 3 значение у4 предыдущей системы Ly b, т.е. последнее вычисленное значение предыдущей системы. Таким образом, как уже отмечалось выше, jk-триггер 64 (который включен так, что работает кзк Т-триггер) с началом обработки каждой новой матрицы меняет свое состояние на про- тивоположное, и переводит одну половину блока 5 в режим записи результатов обработки блоком 4 текущей матрицы, а вторую половину блока 5 - в режим выдачи предыдущих результатов блока 4 для дальней- шей обработки на блоке 3, либо наоборот. В этом же такте 121 с выхода вычислительного модуля 1.3 поступает на второй вход блока 23, на первый вход которого поступает yi из регистра 29, D-триггеры 33 и 39 сбрасыва- ются в нуль, счетчики 38, 35. 37 уменьшают свое значение на единицу, блок 23 выполняет умножение, на второй вход вычитателя 27 со второго входа устройства поступает bz, на выходе отрицательного переноса счетчи- ка 35 появляется единица, которая устанавливает в единицу RS-триггер 36, с выхода вычитателя 27 значение (Ь2 - 121 yi) записывается в узел памяти 28 по адресу 2. В этом же такте в счетчик 50 блока 3 записывается значение (п - 1) из счетчика 51, D-триггеры 47i и 472 устанавливаются в единицу, которая через элемент И 46 (на инверсном выходе D-триггера 48 - единица) поступает на управляющие входы коммутатора 42, сум- матора - вычитателя 44 и регистра 43, элемент у4 предыдущей системы Ly - b поступает через коммутатор 42 на сумма- тор-вычитатель 44, который производит пропуск операнда, и значение - хз запи- сывается в регистр 43 и узел памяти 45 (по адресу 3) по нулевому уровню синхросигнала с выхода 6 блока 3 и поступает на второй выход устройства.

В шестом такге 1з1 со входа блока 4 поступает на второй вход блока 23. на первый вход которого поступает yi из регистра 29, на второй вход вычитателя 27 со второго входа устройства поступает Ьз, и с выхода вычитателя 27 значение Ьз-1з1 yi записывается в узел памяти 28 по адресу 1. В этом же такте элемент из4 предыдущей матрицы U из ячейки 8 блока 572 поступает на умножитель 41, на второй вход которого поступает Х4 из регистра 43, сумматор-вычитатель 44 делает пропуск операнда и с его выхода значение U34 Х4 записывается в узел памяти 45 в ячейку 2.

В седьмом такте Ui со входа блока 4 поступает на блок 23, на первый вход которого поступает yi, а на второй вход вычитателя 27 - Ь4, значение Ы l-ii yi записывается в узел памят и 28 по адресу 0. В этом же такте U24 из ячейки 7 блока 572 поступает на умножитель 41, а на второй его вход поступает Х4, и с выхода сумматора-вычитателя 44 записывается в узел памяти 45 по адресу 1.

В восьмом такте и 12 со входа блока 4 поступает на первый вход коммутатора 26, с выхода которого записывается в регистр 292, из ячейки 6 блока 572 поступает на умножитель 41, на второй em вход подается Х4 и результат (ищ м) записывается в узел памяти 45 по адресу 0.

В девятом такте 22 со входа блока 4 поступает на второй вход блока 23, на первый вход которого из узла памяти 28 по адресу 2 считывается (Ь2 121 yi). и результат (b2-bi yi)/l22 записывается в регистры 29 и в узел памяти 28 по адресу 2, ui2 из регистра 292 переписывается в блок 57- блока 5 по адресу 1. В этом же такте уз предыдущей системы из ячейки 5 блока 572 поступает на второй вход сумматора-вычислителя 44, на первый вход которого из узла памяти 45 поступает (из ячейки 2) usi , и результат уз U34 х.1 - хз принимается в регистр 43 и появляется на втором выходе устройства.

В десятом такте у2 записывается в блок 571 по адресу 2. 1з2 со входа блока 4 поступает на блок 23, умножается на нем на у2 и прозведение посыпает на вычитатель 27, на второй вход которого из ячейки 1 узла памяти 28 выдается значение Ьз 1з1 yi, и с выхода вычитателя результат Ь -1зьу1-1з2 У2 принимается в узел памяти 28 в ячейку 1. В этом же такте U23 предыдущей системы из ячейки блока 572 поступает на умножитель 41, на второй вход которого поступает хз из регистра 43, произведение поступает на сумматор-вычитатель 44, на первый вход которого подается U24 X4 из ячейки 1. и результат и2Ф

Х4 4 иазхз принимается в узел памяти 45 по адресу 1.

В одиннадцатом такте U2 поступает на блок 23, умножается на у2, и произведение поступает на вычитатель 27, с выхода кото- рого значение D4-Ui yi-Ua У2 записывается в узел памяти 28 по адресу 0. В этом же такте и 13 предыдущей системы из ячейки 3 блока 57а поступает на умножитель 41, умножается на хз, произведение поступает на сумма- тор-вычитатель 44, с выхода которого результат щз хз + ui4 Х4 записывается в узел памяти 45 по адресу 0.

В двенадцатом тзкте щз со входа блока 4 принимается в регистр 292, У2 предыдущей системы поступает на второй вход суммато- ра-вычитателя 44, на первый вход которого выдается информация из ячейки 1 узла памяти 45, и результат у2-1Ш хз -U24 Х4 Х2 принимается в регистр 43 и поступает на выход устройства,

В тринадцатом такте щз записывается в ячейку 3 блока 57i, U23 со входа блока 4 принимается в регистр 292, и 12 предыдущей системы из ячейки 1 блока 572 поступает на умножитель 41, где умножается на Х2,далее произведение поступает на сумматор-вычи- татель 44, с выхода которого результат U12 Х2 + un хз + им Х4 записывается в узел памяти 45 по адресу 0.

В четырнадцатом такте U23 записывается в ячейку 4 блока 57i, со входа блока 4 поступает на второй вход блока 23, на первый вход которого из узла памяти 28 по адресу 1 считывается (Ьз-Ы уч-1з2 У2) и ре- зультат (Ьз-lai уНз2 у2)/1зз уз записывается в регистры 29, В этом же такте yi предыдущей системы поступает на второй вход сумматора вычитателя 44. на первый вход которого выдается информация из ячейки 0 узла памяти и результат V1-U12 X2-U13 X3-U14 Х4 xi принимается в регистр 43 и поступает на выход устройства. На этом блок 3 заканчивает обработку предыдущей системы. Поскольку блок 3 ра- ботает не п тактов, как все остальные блоки и модули, а п(п+1)/2 тактов, для согласования режима его работы с остальными блоками оставшиеся п(п-1)/2 тактов регистр 43 не принимает новой информации. Установка блока в исходное состояние (подготовка к обработке следующей системы) происходит, как указывалось выше, по единичному сигналу на его входе установки.

В пятнадцатом такте уз записывается в ячейку 5 блока 57i. поступает на блок 23, умножается на уэ и полученное произведение поступает на вычитатель 27, на второй вход которого выдается информация из ячейки 0 узла памяти 28 и результэт( yi-Ц У2 Ui.y) с,гмоыр 1Р1 Р узел памяти 28 по адресу 0.

В шестнадцатом такте и-и со входа блока 4 принимается в регистр 292, в семнадцатом такте U14 записывается в блок 57i по адресу 6, а в регистр 292 записывается U24. которое в восемнадцатом такте записывается в блок памяти 57i по адресу 7, а в регистр 292 записывается из4.

В девятнадцатом такте из4 переписывается в блок 57i по адресу 8, U4CO входа блока 4 поступает на второй вход блока 23, на первый вход которого считывается информация из ячейки 0 узла памяти 28 и результат (b4-Ui yi-U2 у2-Мз уз) У4 записывается в регистры 29. В этом же такте на вход начальной установки блока 4 подается единичный сигнал. На этом работа блока 4 заканчивается.

В двадцатом такте у4 записывается в блок памяти 57i по адресу 9 и здесь же подается единичный сигнал начальной установки блока 5 на его вход обнуления адреса и блока 3 на его вход установки. Далее работа устройства продолжается аналогично.

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

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

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

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

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

Ъ

. Z

фиг. 5

Фиг 6

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения систем линейных алгебраических уравнений. Цель изобретения - расширение функциональных возможностей за счет решения систем линейных алгебраических уравнений с треугольными матрицами и сокращение аппаратурных затрат при построении вычислительных модулей. Устройство содержит п-1 вычислительных модулей (п - равномерность исходной матрицы), блок синхронизации, два вычислительных блока и блок памяти. Устройство выполняет разложение квадратной матрицы А на нижнюю левую L и верхнюю правую U так, что LU А согласно прямому ходу алгоритма исключения Гаусса. Реализуя обратный ход алгоритма исключения Гаусса, решаются системы линейных уравнений Ux у, то есть решается система вида Ь. В устройстве реализованы указанные операции над потоками матриц. 6 ил. 1 з.п. ф-лы.