Устройство для матричных операций

Устройство для матричных операций

Иллюстрации

Показать все

Реферат

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4774647/24 (22) 26.12.89 (46) 23.11.92. Бюл. ¹ 43 (71) Киевский политехнический институт (72) Роман Выжиковски (PL), Ю,С.Каневский и О.В.Масленников (SU) (56) Авторское свидетельство СССР № 1265793, кл. G 06 F 15/324, 1986.

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

М 1509933, кл. G 06 Г 15/347, 1988. (54) УСТРОЙСТВО ДЛЯ МАТРИЧНЫХ ОПЕРАЦИЙ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения систем линейных алгебраических уравнений. Цель изобретенияя — расши рен ие фун кцио н ал ьн ы х возможностей за счет решения систем линейных

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

Известно устройство для решения систем линейных алгебраических уравнений, содержащее и блоков вычисления разрядов и n(m - 1) вычислительных блоков, где п— размерность системы, m — разрядность операндов, причем каждый вычислительный блок содержит блок вычисления разрядов и блок восстановления остатка, и позволяющее решать систему уравнений Ах = b-за время переходного процесса в нем (1). Недостатком этого устройства является его сложность. . Известно также устройство для решения систем линейных алгебраических уравнений, содержащее (и + 1) вычислительных Ы 1777154 А1 алгебраических уравнений с треугольными матрицами и сокращение аппаратурных затрат при построении вычислительных модулей. Устройство содержит и-1 вычислительных модулей (и — равномерность исходной матрицы), блок синхронизации, два вычислительных блока и блок памяти. Устройство выполняет разложение квадратной матрицы А на нижнюю левую L и верхнюю правую Uтак,,что LU = А согласно прямому ходу алгоритма исключения Гаусса. Реализуя обратный ход алгоритма исключения Гаусса, решаются системы линейных уравнений Ly = b u Ux = у, то есть решается система вида Ах = Ь; В устройстве реализованы указанные операции над потоками матриц. 6 ил. 1 э.п. ф-лы. модулей и решающее систему Ах = b за время 4п + n + 2 тактов (см. "Многофункциональные систологические структуры", под ред. Я.А.Дуброва. Препринт № 20 — 89, Львов — 1989, ин-т прикладных проблем механики и математики АН УССР, с.38). Недостатком этого устройства является невозможность реализации на нем LU-разложения матриц, Наиболее близким к изобретению является устройство для LU-разложения матриц, содержащее (n - 1) операционных блоков и блок синхронизации, и ориентированные на реализацию в виде систолической СВИС (2)

Оно выбрано в качестве прототипа.

Недостатком прототипа является невозможность реализации хода алгоритма

Гаусса решения системы Ах = Ь, т.е. решения системы Ly = b и Ud= у с треугольными матрицами L u U.

1777154

20

30

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

На фиг,1 представлена структурная схема устройства для матричных операций; на фиг.2 — структурная схема блока синхронизации; на фиг,3 — структурная схема i-ro вычислительного модуля; на фиг.4 — структурная схема второго вычислительного блока; на фиг.5 — структурная схема блока памяти; на фиг.6 — структурная схема первого вычислительного блока, Устройстводля матричных операций содержит вычислительные модули 1Л, где i = 1, n - 1 (и — размерность исходной матрицы) блок 2 синхронизации, вход запуска которого является входом запуска устройства, информационный вход вычислительного модуля 1.! (i = 2, и -1) подключен к первому выходу вычислительного модуля 1. (i - 1), информационный вход первого вычислительного модуля является первым информационным входом устройства, первый выход вычислительного модуля 1. (n - 1) является первым выходом устройства, вход признака начала ввода столбца и вход синхронизации ввода элементов матрицы вычислительного модуля 1,i (i = 2, „(n - 1)) подключены соответственно ко второму и третьему выходам вычислительного модуля 1.(I - 1), вход при.знака номера вычислительного модуля 1,1 подключен ко входу логического нуля устройства, входы признака номера остальных вычислительных модулей подключены ко входу логической единицы устройства, четвертый выход вычислительного модуля 1,1 является входом признака окончания ввода столбца блока 2, первый и второй выходы которого подключены соответственно ко входу признака начала ввода столбца и входу синхронизации ввода элементов матриBbl ll1cлительного Mop/ 1B 1.1, первого вычислительного блока 3 является выходом устройства, первый выход вычислительного модуля 1.(n - 1) подключен к первому информационному входу второго вычислительного блока 4, второй информационный вход которого является вторым информационным входом устройства, второй вход вычислительного модуля 1, (n - 1)связан со входом начальной установки блока 4, четвертый выход которого связан со входом управления пропуском операнда блока 3, информационный вход которого является вторым выходом блока 5 памяти. информационный вход, вход синхронизации чтения и вход обнуления адреса которого подключены соответственно к первому, третьему и второму выходам блока 4, третий 6 и четвертый 7 выходы блока 2 являются, соответственно, прямым и инверсным тактовыми выходами и связаны с синхровходами всех вычислительных модулей и блоков устройства, первый выход блока 5 подключен ко входу установки блока 3, Вычислительный модуль 1.1 (i = 1, (п - 1) содержит блок 8 умножения-деления, выход которого подключен к первому входу вычитателя 9, второй вход которого подключен к первым входам первого 10 и второго 11 коммутаторов и является информационным входом вычислительного модуля, первый выход которого подключен к выходу первого регистра 12, вход которого связан с выходом коммутатора 11, со входом данных узла памяти 13 и входом второго регистра 14, выход которого подключен ко второму входу коммутатора 10, выход которого является первым входом блока 8, второй вход которого связан с выходом узла 13, адресный вход которого подключен к информационному выходу счетчика 15, выход отрицательного переноса которого подключен ко входу первого D-триггера 16, к первому входу элемента И 17, и является четвертым выходом вычислительного модуля, вход признака начала ввода столбца которого подключен ко входу второго D-триггера 18, $ — входу RS— триггера 19, и входу установки в нуль Dтриггера 16, выход которого связан с управляющим входом коммутатора 10, со входом выбора режима блока 8, входом пропуска операнда вычитателя 9, с управляющим входом регистра 14, входом третьего D-триггера 20 и R-входом RS-триггера 19, выход которого является входом чтения-записи узла 13 и подключен к первым входам первого

21 и второго 22 элементов ИЛИ, вторые входы которых подключены соответственно, к выходам О-триггера 20 и элемента И 17, второй вход которого является входом признака номера вычислительного модуля, вход синхронизации ввода элементов матрицы которого является входом выбора ре>кима счетчика 15, информационный вход которого связан со входом (n -1) устройства, выход вычитателя 9 подключен ко второму входу коммутатора 1, управляющий вход которого является выходом элемента ИЛИ 22, второй и третий выходы вычислительного модуля подключены к выходам соответственно 0-триггера 18 и элемента ИЛИ 21, Второй вычислительный блок 4 содер>кит узел 23 умножения-деления, первый вход которого является выходом первого коммутатора 24, первый вход которого связан с первым входом второго коммутатора

1777154

10

30

40

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

RS-триггера 30 и к первому управляющему входу коммутатора 24, второй управляющий вход которого связан со входами выбора режима блока 23 и вычитателя 27, с управляющим входом коммутатора 26, со входом разрешения приема кода регистра 291, и с выходом второго 0-триггера 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, второй вход которого подключен к первому вхо,: у умножителя 41 и является информацион ным входом блока 3, выход которого подключен ко второму входу умножителя 41 и к выходу регистра 43, вход которого связан с выходом сумматора-вычитателя 44 и со входом данных узла памяти 45, выход которого подключен к первому входу сумматоравычитателя 44, второй вход которого является выходом коммутатора 42, управляющий вход которого соединен со входом признака вычитания сумматора-вычитателя

44, со входом управления записью регистра

43 и с выходом элемента И 46, первый вход которого подключен к выходу первого 47> и ко входу второго 48 D-триггера, инверсный выход которого подключен ко второму входу элемента И 46, вход D-триггера 47> соединен с выходом элемента ИЛИ 49 и со входом выбора режима первого счетчика 50, выход отрицательного переноса которого связан с первым входом элемента ИЛИ 49 и с декрементирующим входом второго счетчика 51, вход выбора режима которого подключен ко второму входу элемента ИЛИ 49, ко входу установки в нуль 0-триггера 48 и является входом установки блока 3, вход управления пропускном операнда которого связан .через третий О-триггер 472 со входом уп равления пропуском операнда сумматора-вычитателя 44, вход (n - i) устройства связан с информационным входом счетчика 51, выход которого подключен к информационному входу счетчика 50, информационный выход которого является адресным входом узла 45, вход чтения-записи которого подключен к выходу б блока 2.

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

1)/2 слов, имеющих одинаковую структуру.

В состав блока 5 входят блоки оперативной памяти 57ъ 572, входы и выходы данных которых объединены и являются, соответст1777154 венно, информационным входом и вторым выходом блока 5, коммутаторы 581, 582, выходы которых являются адресными входами блоков 57, входы выбора которых подключены к выходам элементов ИЛИ 591, 592, и ко 5 входам элементов сложения по модулю два

601, 602, выходы которых подключены к синхровходам счетчиков 611, 612, входы установки в нуль которых соединены с выходами элементов И621; 622, входы чтения-записи 10 блоков 571 и 572. связаны, соответственно с управляющими входами коммутаторов 581 и

582, с первыми входами элементов. И631 и

632, элементов И 621 и 622 входами выбора режима (счет в режиме вычитания или сум- 15 мирования) счетчиков 611 и 612 и являются прямым и инверсным выходами jk-триггера

64,)-вход которого подключен ко входу логической единицы устройства, а k-вход — к прямому выходу триггера, синхровход кото- 20 рого является входом обнуления адреса блока 5 и связан со вторыми входами элементов 60, 62 и со входом 0-триггера 65>, выход которого является первым выходом блока 5. При этом подразумевается, что вы- 25 ходы блока 57 переходят в третье состояние, если блок не выбран (на выходе элемента

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

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

Устройство для решения систем линейных алгебраических уравнений раскладывает исходную квадратную матрицу А системы 40

Ах = Ь размерности и, на нижнюю левую (= (jill и верхнюю правую 0 =(0))(у которой на главной диагонали стоят единицы) так, что Ш = А, LUx - b согласно следующим формулам прямого хода алгоритма исключе- 45 ния Гаусса: а; =а1) (Ц (k 1)а1,,(-1) .,(0)

Bik,а;; =а) а 50

k=1,й, i,)=k+ i, k+2, „., n, Ukl = akj(- /а - ), k = 1, n; ) = К k+ 1 „,,и;

1 k = а; (), k = 1,n, i = К k+ 1,...,n. Затем устройство реализует обратный ход алгоритма Гаусса, который заключается в решении системы Ly =. Ь по формулам:

i — 1.

yi =(bi-, likyk)/1и. i =1, и

К=1

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

xI = у1 -,>, Uik Xk, i = и, ii - 1,...,1.

К =i+1

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

b с периодом п2 тактов. Однако в связи стем, что корни х нельзя начинать вычислять до получения всех yi, в устройство введен блок 5, включенный таким образом, что пока блок4 вычисляет значения у системы А х = Ь и заполняет одну половину блока 5, блок 3 вычисляет значения х системы Амх -1= Ь -1 (т.е. той, которая обрабатывалась перед ней), работая . с другой половиной блока 5.

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

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

На вход устройства каждый такт последовательно поступают элементы матрицы А = (а11) по столбцам, т.е. первые и тактов на вход устройства поступают элементы первого столбца матрицы А (в первом такте — а11, во втором — аг1 и т.д.), вторые и тактов — элементы второго столбца и т.д;

По сигналу "Запуск" и положительному перепаду синхроимпульса с выхода 7 Dтриггер 55 устанавливается в единицу, которая появляется на первом и втором выходах блока 2 синхронизации, а также поступает на вход выбора режима счетчика 53, в который записывается значение и в двоичном коде, и на выходе отрицательного переноса которого появляется нуль независимо от состояния сигнала на декрементирующем входе счетчика 53. Кроме того, D-триггер 16.1 и R-Я триггер

19.1 вычислительного модуля 1.1 устанавливаются, соответственно, в нуль и единицу.

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

1777154

20

40

3), в регистр 12.3 и появляется на первом выходе устройства. а31 переписывается из регистра 12.1 в регистр 12.2, на вход устройства поступает ан и записывается в узел памяти 13.1 по адресу;, и в регистр 12.1, 55 на вход выбора режима счетчика 15.1 также поступает единица.

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

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

15.1 появляется нуль. На вход устройства подается значение 811. которое поступает на первый вход коммутатора 11.1, и с его выхода записывается в узел памяти 13.1 по адресу 3, и в регистр 12.1. 8 этом же такте единица из D-триггера 55, переписывается в 0-триггер 18.1. а D-триггер 55 сбрасывается в нуль. Таким образом, на обеих управля. ющих выходах модуля 1.1 находятся единицы, а на управляющих входах — нули, D-триггер 16.2 и RS-триггер 19.2 модуля 1.2 устанавливаются в нуль и единицу соответственно, . Во втором такте счетчик 15.1 уменьшает свое содержимое на единицу, на вход вычислительного модуля 1,2 подается 811, которое поступает на первый вход коммутатора 11,2, и с его выхода записывается в узел памяти 13.2 по адресу 3 и в регистр 12.2. В том же такте а21 подается на вход устройства и записывается в узел памяти 13.1 по адресу 2 и в регистр 12.1, пройдя через коммутатор 11.1, единица из

D-триггера 18.1 переписывается в 0-триггер

18.2, RS-триггер16.3и RS-триггер 19.3устанавливаются в нуль и единицу соответственно.

В третьем такте счетчик 15.1 уменьшает свое значение на единицу, на вход модуля

1.3 подается a>1=111, которое записывается в узел памяти 13.3 (по адресу 3), в регистр

12.3 появляется на первом выходе устройства и первом входе блока 4, 82 поступает на вход модуля 1.2 и записывается в узел памяти 13.2 по адресу 3, на вход устройства поступает 831 и записывается в узел памяти

13.1 по адресу 1 и в регистр 12,1; единица из О-триггера 18.2 переписывается в Dтриггер 18.3 и поступает на управляющий вход блока 4.

В четвертом такте счетчик 15.1 уменьшает свое значение на единицу, т.е, до нуля, и нэ его выходе отрицательного переноса появляется единица, которая поступает на декрементирующий вход счетчика 53, и уменьшает его состояние на единицу, на вход модуля 1,3 подается 821 = l21 которое записывается в узел памяти 13.3 (по адресу

35 (n - 1), т.е. 3, а31 =- I31 перепис;,,ьается и. регистра 12.2 в регистр 12.3 и появляетсч на первом выходе устройства, а4 переписывается из регистра 12.1 в регистр 12.2, аг2 поступает со входа устройства через коммутатор 10.1 на первый вход блока 8.1, на второй вход которого поступает а1 из узла памяти 13.1 (из ячейки с адресом 3), блок 8,1 выполняет операцию деления, и с его выхо; да 8 2/811 = ui2 поступает на первый вход вычитателя 9.1, который осуществляет пропуск операнда. и u>2 записывается в регистры 12.1 и 14,1.

В шестом такте а> l = 14l переписывается из регистра 12.2 в регистр 12.3 и появляется на первом выходе устройства, и12 из регистра 12.1, переписывается в регистр 12.2, Dтриггеры 16.1 и 20,1 устанавливаются, соответственно, в нуль и единицу, счетчик

15,1 уменьшает свое значение на единицу, 822 поступает со входа устройства на второй вход вычитателя 9.1, коммутатор 10.1 пропускает 012 из регитсра 14.1 на первый вход блока 8.1, на второй вход которого поступает а21 из ячейки с адресом 2 узла памяти

13.1, блок 8.1 выполняет умножение, вычитатель 9.1 — вычитание, и с его выхода результат 822-821 u12 = l22 принимается в регистр 12.1, пройдя через коммутатор 11.1.

В седьмом такте и>2 из регистра -12,2 переписывается в регистр 12.3 и появляется на первом выходе устройства, счетчик 15.1 уменьшает свое значение на 1, в счетчик

15.2 записывается значение (n — 1), т.е. 3, D-триггер 20.1 сбрасывается в нуль, 22 из регистра 12,1 переписывается в регистр

12.2 и записывается в узел памяти 13,2 по адресу 3. а32 поступает со входа устройства на второй вход вычитателя 9.1, и>2 из регистра 14.1 поступает на первый вход блока

8.1, на второй вход которого поступает 83> из ячейки с адресом 1 узла памяти 13.1 и результат 832-831.U12 = l32 с выхода вычитателя 9.1 принимается в регистр 12.1.

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

15.1, 132 из регистра 12.1 переписывается в регистр 12,2 и записывается s узел памяти

13.2 по адресу 2, а42 поступает со входа устройства на второй вход вычитателя 9,1, 812 поступает н8 первый вход блока 8.1, на второй вход его поступает а41 из ячейки узла памяти 13.1 и результат а42-841 U12 =!42 принимается в регистр 12.1.

1777154

В девятом такте 132 из регистра 12.2 переписывается в регистр 12.3 и появляется на первом выходе устройства, далее, аналогично пятому такту, D-триггера 16.1 устанавливается.в единицу, в счетчик 15,1 вновь записывается значение (n - 1), 142 переписывается в регистр 12.2 и записывается в узел памяти 13,2 по адресу 1. а13 поступает со входа устройства на первый вход блока 8.1, на второй вход которого поступает а11 иэ ячейки 3 узла памяти 13.1, блок 8.1 выполняет деление и результат а13/а11 = u13, пройдя без изменений через вычитатель 9.1, записывается в регистры 12.1 и 14.1, В десятом такте 142 из регистра 12.2 переписывается в регистр 12.3 и появляется на первом выходе устройства, счетчики 15.1 и 15.2 уменьшают свое значение на единицу, на выходе отрицательного переноса счетчика 15,2 появляется единица, которая поступает через элемент И 17,2 на второй вход элемента ИЛИ 22.2, и13 из регистра

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

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

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

15.1 уменьшает свое значение на единицу, 0-триггер 16.2 и RS-триггер 19.2 устанавливаются, соответственно, в единицу и нуль, в счетчик 15.2 записывается значение (n — 1), a23 ) иэ регистра 12,1 поступает на первый вход блока 8.2, на второй вход которого поступает 122 из ячейки 3 узла памяти 13.2 блок

8.2 выполняет деление, вычитатель 9.2— прд(1уск операнда, и результат и23 а23 /122 записывается в регистры 12.2 и

14.2, В этом же такте а33 поступает со входа устройства на второй вход вычитателя 9.1, и13 иэ регистра 14.1 поступает на первый вход блока 8.1, нэ второй вход его поступает а31 иэ ячейки 1 узла памяти 13.1, и результат азз и13 а31 =- а33(принимается в регистр (1

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

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

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

9.2 на первый вход блока 8.2 поступает и23 из регистра 14,2, на второй его вход — 132 и ячейки 2 узла памяти 13.2, и результат а33(5 -и23 132 = 133 принимается в регистр 12.2. В этом же такте а43 поступает со входа устройства на второй вход вычитателя 9.1, и13 ум35 триггер 20,1 устанавливается в единицу, а

0-триггер 16,1 — sн»у л ь, 143 из регистра 12.2 переписывается в регистр 12.3 и записывается в узел 13.3 по адресу 2, и14 из регистра

12.1 переписывается в регистр 12.2. пройдя через коммутатор 11.2, а24 поступает со входа устройства нэ второй вход вычитателя

9.1, »а первый вход блока 8,1 поступает и14. на второй его вход — a21 из ячейки 2 узла памяти 13.1, и результат а24-и14 a21 = а24

{1)

45 принимается в регистр 12.1, В пятнадцатом такте счетчики 15,1 и

15.3 уменьшают свое значение»э единицу, в счетчик 15.2 записывается значение (и - 1), 0-тригггер 16,2 устанавливается о единицу, 50 и14 переписывается из регистра 12.2 в регистр 12.3 и появляется на первом выходе устройства, а24 из регистра 12,1 поступает (1) на первый вход блока 8.2, на второй вход которого поступает 122 из ячейки 3 узла 13.2, 55 блок 8.2 выполняет деление, вычитатель

9.2 — пропуск операнда, и результат а24 /122 (1)

= u24 записывается в регистры 12.2 и 14.2. В этом же такте а34 поступает со входа устройства на второй вход вычитателя 9.1, и14 из регистра 14.1 поступает нэ первый вход бло-. ножается на блоке 8 1 íà à41 из ячейки УП 13,1 и результат а43-u13 (1)

10 а41 = а43 принимается в регистр 12,1, В тринадцатом такте в счетчики 15,3 и

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

15.2 уменьшает свое значение на единицу, 15 D-триггер 16.1 устанавливается в единицу, 133 записывается в регистр 12.3 и в узел памяти 13,3 по адресу 3, a43() из регистра (1)

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

9.2, на первый вход блока 8.2 поступает и23, 20 на второй его вход — 142 из ячейки 1 узла памяти 13,2 и результат а43{ и23 142 = 143 (1) записывается в регистр 12.2. В этом же такте а14 поступает со входа устройства на первый вход блока 8.1, »а второй вход кото25 рого поступает а11 иэ ячейки 3 узла памяти

13.1, блок 8.1 выполняет деление, и результат а14/a11 = u24 записывается о регистры

12.1 и 14,1.

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

30 15.2, 15,3 уменьшают свое значение на единицу, на выходе отрицательного переноса счетчика 15,2 появляется единица. которая поступает через элементы И 17.2 и ИЛ И 22.2 на управляющий вход коммутатора 11.2, 013

1777154

14 ка 8.1. на второй вход его поступает а31 из ячейки узла памяти 13.1 и результат а34-ц14 .аз! = a34 принимается в регистр 12.1, В шестнадцатом такте счетчики 15.1, 15.2, 15.3. уменьшают свое значение на еди- 5 ницу, на выходах отрицательного переноса счетчиков 15.3 и 15.1 появляются единицы, D-триггер 20.2 также устанавливается в единицу, иг4 переписывается из регистра 12.2 в регистр 12.3 и появляется на первом выходе 10 устройства. счетчик 53 уменьшает свое значение на единицу (и его содержимое становится равным нуле), и на его выходе отрицательного переноса появляется единица, которая записывается в D-триггер 55 15 по переднему фронту синхросигнала с выхода 7. Таким образом, устройство подготавливается к обработке элементов следующей матрицы, В этом же такте а34(иэ регистра (1

12.1 поступает на вычитатель 9.2, на первый 20 вход блока 8,2 поступае и24, на второй его вход — )зг из ячейки 2 узла памяти 13.2, и результат аз4(иг4.)32 = а34 за и исы вается в (!) (г) регистр 12.2, а44 со входа устройства поступает на вычитатель 9.1, на первый вход бло- 25 ка 8.1 поступает и14, на второй его вход поступает а41 из ячейки „ узла памяти

13.1 и результат а44 и!4 а41 = а44 принимаЙ ется в регистр 12,1. Б этом же такте после установки в единицу D-триггера 55, D-триг- 30 гер 16.1 и RS-триггер 19.1 устанавливаются соответственно, в нуль и единицу, а в счетчик 53 записывается и.

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

15,3 записывается значение (n - 1), 0-триггер 35

20.2 сбрасывается в нуль, счетчик 15.2 уменьшает свое значение на 1, G-триггеры

16,1 и 16.3 устанавливаются в единицу RSтриггер 19.3 сбрасывается в нуль, а34() из регистра 12.2 поступает на первый вход бло- 40 ка 8.3, на второй вход которого поступает )33 из ячейки 3 узла памяти 13,3, блок 8.3 выполняет деление, и результат а34 /133 = U34 заг) писывается в регистры 12,3 и 14.3 и поступает на первый выход устройства, 45 а44 из регистра 12.1 поступает на вычита11 тель 9.2, на первый вход блока 8.2 поступает и24, на второй его вход — l42 из ячейки I уз1 а памяти 13.2, и результат а и о24 )42 = а44 (1 2) записывается в регистр 12.2, на вход устрой- 50 ства поступает элемент а11 следующей матрицы, при этом действия выполняются аналогично первому такту.

В восемнадцатом такте D-триггер 16.3 . сбрасывается в нуль, а44 ) из регистра 12.2 55 (2) поступает на вычитатель 9.3, счетчик 15.3 уменьшает свое значение на 1. на первый вход блока 8,3 поступает и34, на второй его вход — (43 из ячейки 2 узла памяти 13.3, и результат а44 U34 )43 = I44 принимается в регистр 12.3 и появляется на i ерво-1 вы.:..;л: устройства. По отношению v элемс н Tам с;,едующей матрицы действия выполняются аналогично второму такту, Далее работа устройства продолжается аналогично с периодом и тактов.

Таким образом, время (Л)-разложения матрицы в паточном режиме равно и так2 тов.

Продолжим рассмотрение работы устройства. При реализации обрабо1ного хода алгоритма Гаусса все ранее принятые условия продолжают иметь силу. Поступление исходных для блока 4 данных соответствует поступлению элементов I I, щ! на выход модуля 1.3. Таким образом. элемен; I11 поступает в блок 4 в четвертом такте, I 1 — в пятом, и т.д. Элементы Ь (! =- 1,п) вектора Ь системы Ах = Ьпоступают, начиная с четвертого такта (no одному за такт в порядке возрастания I), со второго информационного входа устройства.

Как уже отмечалось выше. в третьем такте D-триггер 18.3 устаналивается в единицу, которая, поступая на управляющий вход блока 4, поступает на входы выбора режима счетчиков 35, 37 и 38 (через элементы ИГ! И

31 и 32), на входы 0-триггеров 33 и 39. на первый вход элемента И 10, и на вход вь.ánpa режима счетчика 34, в которой сра3 жс записывается единица. Таким образом происходит начальная установка блока 4.

В четвертом такт» по переднему фронту синхросигнала с выхода 6 в счетчики 35, 37 и 38 записывается, оответственно. значения 1, и и (fl — 1), 0-триггеры 33 и 39 усганавливаются в единицу, à RS-григгеры 30 и 36 — соответственно, в единоuy и нуль, единица с выхода D-триггера 33 поступает на первый управляющий вход блока 5, сбрасывая в нуль один из счетчиков 61 (в зависимости от состояния jk-триггера 64), Пусть, например, при подаче единицы на вход выоора режима счетчика 61, он работает в режиме вычитания единицы, а при подаче нуля — в режиме суммирования единицы, и пусть jkтриггер 64 находится в единице, Тогда сбрасывается в нуль счетчик 611, с его выхода нулевой адрес через коммутатор 581 поступает на адресный вход блока памяти 571, счетчик 612 не меняет своего состояния, поскольку на выходе элемента И 622 — нуль, а единица на синхровходе счетчика 612 блокируется (остается) единицей на первом управляющем входе блока 5. B этом же такте

l11 с выхода вычислительного модуля 1.3 поступает на второй вход блока 23, на первый вход которого поступает I1 со второго входа устройства (через коммутатор 24), блок 23 выполняет деление, вычитатель 27 — про15

1777154

15

40

55 пуск операнда, и через коммутатор 26 значение l1/l!1 = у! принимается в регистры 29 и записывается в узел памяти 28 (по адресу

3) по нулевому уровню сигнала чтения-записи(поступающего с выхода 6), а также поступает на входы данных блоков 571, 572. Кроме того, 0-триггер 651 сбрасывается в нуль, а

652 устанавливается в единицу, которая поступает на вход установки блока 3, устанавливая D-триггер 48 в нуль, и записывая в счетчик значение (n - 1), В пятом такте по переднему фронту синхросигнала с выхода 6 триггер 64 сбрасывается в О, по нулевому уровню синхросигнала с выхода 7 происходит запись в блок памяти

571 в ячейку 0 значения у1, из блока 572 из ячейки с предыдущим адресом (т.к. счетчик

612 не поменял свое состояние) считывается на вход блока 3 значение у4 предыдущей системы l у = Ь, т,е, последнее вычисленное значение предыдущей системы. Таким образом, как уже отмечалось выше, jk-триггер

64 (который включен так, что работает как

T-триггер) с началом обработки каждой новой матрицы меняет свое состояние на противоположное, и переводит одну половину блока 5 в режим записи результатов обработки блоком 4 текущей матрицы, а вторую половину блока 5 — в режим выдачи предыдущих результатов блока 4 для дальнейшей обработки на блоке 3, либо наоборот. В этом же такте l21 с выхода вычислительного модуля 1.3 поступает на второй вход блока

23, на первый вход которого поступает у! из регистра 29, D-триггеры 33 и 39 сбрасываются в нуль, счетчики 38, 35. 37 уменьшают свое значение на единицу, блок 23 выполняет умножение, на второй вход вычитателя 27 со второго входа устройства поступает Ь2, на выходе отрицательного переноса счетчика 35 появляется единица, которая устанавливает в единицу RS-триггер 36, с выхода вычитателя 27 значение (b2 - 121 у1) 3".ïèñûвается в узел памяти 28 по адресу 2, В этом же такте в счетчик 50 блока 3 записывается значение (n — 1) из счетчика 51, D-триггеры

471 и 472 устанавливаются в единицу, которая через элемент И 46(на инверсном выходе D-триггера 48 — единица) поступает на управляющие входы коммутатора 42, сумматора — вычитателя 44 и регистра 43, элемент у4 предыдущей системы у =- Ь поступает через коммутатор 42 íà сумматор-вычитатель 44, который производит пропуск операнда, и значение у4 --- х4 записывается в регистр 43 и узел памяти 45 (по адресу 3) по нулевому уровн а синхрасигнала с выхода 6 блока 3 и поступает на второй выход устройства.

В шестом такте !31 со входа блока 4 поступает на второй вход блока 23, на первый вход которого поступает у! из регистра

29, на второй вход вычитателя 27 со второго входа устройства поступает Ьз, и с выхода вычитателя 27 значение Ь3-131 у! записывается в узел памяти 28 по адресу 1. В этом же такте элемент и34 предыдущей матрицы U из ячейки 8 блока 572 поступает на умножитель

41, на второй вход каторога поступает х4 из регистра 43, сумматор-вычитатель 44 делает пропуск операнда и с его выхода значение и34 х4 записывается в узел памяти 45 в ячейку 2.

В седьмом такте I41 со входа блока 4 поступает на блок 23, на первый вход которого поступает у1, а на второй вход вычитателя 27 — !э4, значение Ь1I41 у1 записывается в узел памяти 28 по адресу О. В этом >ке такте и24 из ячейки 7 блока 572 поступает на умножитель 41, а на второй его вход поступает х4, и с выхода сумматора-вычитателя 44 и31, х4 записывается в узел памяти 45 по адресу

1.

В BocI.»IIol такте UI12 со входа блока 4 поступает на первый вход кол1мутатора 26, с выхода которого записывается в регистр

292, из ячейки 6 блока 572 поступает на умно>китель 41, на второй его вход падается х4 и результат (u14 х4) записывается в узел памяти 45 по адресу О.

В девятом такте l22 со входа блока 4 поступает на второй вход блока 23, на первый вход которого из узла памяти 28 по адресу 2 считывается (Ь2 l21 у1), и результат (Ь2-!21 у1)/!22 записывается в регистры 29 и в узел г1амяти 28 по адресу 2, и12 из регистра

292 переписывается в блок 571 блока 5 по адресу 1. В этом >ке такте у3 предыдущей системы из ячейки 5 блока 572 поступает на второй вход сумматора-вычислителя 44, на первый вход которого из узла памяти 45 поступает (из ячейки 2) ы31 х1, и результат узи34 х1= хз принимается в регистр 43 и появляется на втором выходе устройства.

В десятом такте у2 записывается в блок

571 па адресу 2. !32 со входа блока 4 поступает на блок 23, умножается на нем на у2 и прозведение поступает на вычитатель 27, на второй вход которого из ячейки 1 узла памяти 28 выдается значение Ьз !31 yI, и с выхода вычитателя pe3yëьтат Ь3 l31 ° у1 l32 у2 прини мается в узел памяти 28 в ячейку 1. В этом же такте о23 предыдущей системы из ячейки блока 572 поступает на умножи. ель 41, на второй вход котарага по