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

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

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

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

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

Недостатком известного устройства явля тся его сравнительно небольшие функциональные возможности.

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

(/

С

sj

со сп

00 0 00

{

В, где AJjnunj, , и - матрицы (в частном случае, при Н 1, р 1 матрицы С, В и матрица D могут быть векторами размерностью п и скаляром соответственно).На фиг.1 представлена структурная схема устройства для операций над матрицами; на фиг.2 - структурная , схема блока синхронизации на фиг.З и 4 - структурная схема вычислительного модуля соответственно первого и второго типа.

Устройство для операций над матрицами содержит вычислительные модули 1.1 - 1.п первого типа и 2.1 - 2.М второго типа и блок 3 синхронизации, причем вход запуска устройства подключен к одноименному входу блока 3, выход которого соединен с синхровхо- дом вычислительного модуля 1.1, выход синхронизации, выход признака перестановки строк и информационный вьдсрд вычислительного модуля 1 .К (К - ) подключены соответственно к синхровходу, входу, признака перестановки строк и первому информационному входу вычислительного модуля 1.СК-Н), второй информационный вход вычислительного модуля 1.Р (Р 1,п) является Р-м информационным входом устройства, синхровход, вход признак перестановки строк и первый информационный вход вычислительного модуля 2. г (г 1,М) подключены к одноименным выходам вычислительного модуля 2.(г-1), вторые информационные вход и выход вычислительного модуля 2.г являются, соответственно (п+г)-м информационным входом и r-м выходом устройства.

I

Вычислительный модуль 1.Р содержи

блок 4.Р умножения-деления, первый вход которого подключен к выходу первого регистра 5,Р, вход которого подключен к выходу первого коммутатора 6.Р и к входу второго регистра 7.Р, выход которого соединен с первыми входами первого 6.Р и второго 8.Р коммутаторов и схемы 9.Р сравнения, второй вход которой подключен к вторым входам коммутаторов б.Р и 8.Р и к выходу третьего коммутатора 10.Р, первый вход которого является вторым информационным входом вычислительног модуля, первый информационный вход которого связан с первыми входами четвертого 11.Р и пятого 12.Р коммутаторов, второй вход Последнего под15

20

25

ключен к выходу блока 4.Р и к первому входу сумматора 13.Р, второй вход ко- торого связан с вторым входом коммутатора 11.Р и с первым выходом перво-} го блока 14.Р элементов задержки, второй выход которого связан с входом первого D-триггера 15.Р, выход которого подключен к управляющему входу

«д регистра 5.Р, к декрементирующему входу первого счетчика 23.Р и к входу обнуления синхронного RS-триггера 16.Р, выход которого подключен к первым входам первого элемента ИЛИ 17.Р и элемента И 18.Р, второй вход которого является выходом схемы 9.Р сравнения, а выход его подключен к второму входу шестого коммутатора 19.Р, первый вход которого является входом признака перестановки строк вычислительного модуля, первый и второй входы которого подключены к входам соответственно второго 20.Р и третьего 21.Р D-триггеров, выход последнего подключен к первому входу второго элемента ПЛИ 22, к второму входу блока 14.Р, входу установки триггера 16.Р, декрементирующему входу второго счетчика 24.Р и является вторым раз- рядо1ч выхода синхронизации вычислительного модуля, первый разряд которого подключен к выходу триггера 20.Р, к управляющему входу коммутатора 10.Р и к входу выбора режима (параллельное занесение информации или

35 счет) счетчиков 23.Р и 24.Р, выход счетчика 23.Р подключен к управляющему входу блока 14.Р, первый вход которого связан с выходом коммутатора 8.Р, управляющие входы коммутаторов

40 6.Р и 8.Р объединены и подключены к выходу элемента ИЛИ 22, второй вход которого связан с входом четвертого D-триггера 25.Р и с выходом коммутатора 19.Р, управляющий вход которого

45 подключен к выходу отрицательного переноса счетчика 24.Р и к второму входу элемента ИЛИ 17.Р, выход которого подключен к входу выбора режима блока 4.Р и к управляющим входам комму50 таторов 11.Р и 12.Р, выход коммутатора 12.Р подключен к входу регистра 26.Р, выход которого является первым информационным выходом вычислительного модуля, выход признака перестаногв55 ки строк которого подключен к выходу D-триггера 25.Р, выход коммутатора 11.Р подключен к второму входу блока 4.Р, выход сумматора 13.Р - к входу блока 27.Р, выход которого связан с

30

вторым входом коммутатора 10.Р, управляющий вход блока 27.Р связан с входом Р устройства.

Вычислительный модуль 2.К содержит умножитель 28.К, первый (К 1,11) вход которого связан с выходом первого регистра 29.К, вход которого подключен к выходу первого коммутатора 30.К и к входу второго регистра 31.К, выход которого подключен к первым входам первого 30.К и второго 32.К коммутаторов, вторые входы которых подключены к выходу третьего коммутатора 33.К, перзый вход которого является вторым информационным входом модуля, первый и второй разряды синхровхода и вход признака перестановки строк вычислительного модуля являются соответственно входами первого 34.К, второго 35.К и третьего 35.К D-триггеров, выходы которых являются соответственно первым и вторым разрядами выхода

ляюций вход блока 40.К связан с-вхот дом Р устройства.

Устройство для операций над матрицами предназначено для вычисления с помощью алгоритма фаддеева выражения вида X В + D, где в общем случае Л - ajj , В - {b;K , С - сеД , D - матрицы, представленные в виде объединенной матрицы, причем суть алгоритма сводится к тому, что , после обнуления в объединенной матрице нижнего левого квадранта (т.е. элементов матрицы -С), в правом ния- нец, ква дранте (на месте матрицы D) получают искомый результат Xfpxlfj:

20

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных матричных вычислителях. Цель изобретения - расширение функциональных возможностей за счет вычисления выражений вида X СА В + D. Цель достигается тем, что в устройство введены II вычислительных модулей (М - число столбцов матрицы С) со связями. Устройство работает в соответствии с алгоритмом Фадцевва с частичным выбором ведущего элемента. 4 ил.

синхронизации и выходом признака пе- 25 сколькими (или одной, в зависимости

рестановки строк вычислительного мо- дуля, второй и первый информационные выходы которого подключены соответственно к выходам третьего 37.К и четвертого 38.К регистров, вход последнего является первым информационным входом модуля и подключен к второму входу умножителя 28.К, выхрд которого связан с первым входом сумматора 39.К, выход которого подключен к входам регистра 37.К и первого блока 40.К элементов задержки, выход которого является вторым входом коммутатора 33.К, управляющий вход которого подключен к выходу D-триггера 34.К и к входу выбора режима (параллельное занесение информации или счет) счетчика 41.К, выход которого является управляющим входом второго блока 42.К элементов задержки, первые выход и вход которого подключены соответственно к второму входу сумматора 39.К и к выходу коммутатора 32.К, управляющие входы коммутаторов 30.К и 32.К объединены и подключены к выходу элемента ИЛИ 43.К, первый и второй 50 входы которого подключены соответственно к входу триггера 36.К и к выходу триггера 35.К, управляющий вход регистра 29.К подключен к декрементиот размерности В) правыми частями:

t, D 0; обращение

X при С

матрицы X А при , умножение матриц (или матрицы) на

-п вектор в зависимости от размерности В: X С-В при А - I, D 0; умножение со сложением матриц X - С1В + D при А I; задача адаптивной фильтрации, которая использует выражение X + D при В I, где I - единнч35 ная матрица.

Обнуление нижнего левого квад- ранта объединенной матрицы можно осуществить, применяя к ней исключение Гаусса, до приведения матрицы А

40 к верхнетреугольному виду. Тогда автоматически на месте матрицы -С получается нулевая матрица. При этом с целью обеспечения численной устойчивости вычислений преобразование мат-i

45 рицы А выполняется по алгоритму исключения Гаусса с частичным выбором ведущего элемента по столбцу. Что оэ- начает, что на i-м шаге (i 1, п-1У алгоритма Гаусса исключению элементов a1. (j i+1, п), принадлежащих исходной матрице А А (при ) частично преобразованной матрице А1 (при i 1), предшествует последовательное сравнение их с элеменрующему входу счетчика 41.К и к выхо- S5 то аЬ если очередной элемент ду четвертого D-триггера 44.К, вход la}il |a ;;i .осуществляется переста- которого является вторым выходом бло-} новка j-й и i-й строк, т.е. i-я строка становится j-й и наоборот. В про-, тивном случае перестановки строк не

ка 42.К, второй вход которого соединен с выходом D-триггера 35.К, управ-

0

от размерности В) правыми частями:

t, D 0; обращение

X при С

матрицы X А при , умножение матриц (или матрицы) на

п вектор в зависимости от размерности В: X С-В при А - I, D 0; умножение со сложением матриц X - С1В + D при А I; задача адаптивной фильтрации, которая использует выражение X + D при В I, где I - единнч5 ная матрица.

Обнуление нижнего левого квад- ранта объединенной матрицы можно осуществить, применяя к ней исключение Гаусса, до приведения матрицы А

0 к верхнетреугольному виду. Тогда автоматически на месте матрицы -С получается нулевая матрица. При этом с целью обеспечения численной устойчивости вычислений преобразование мат-i

5 рицы А выполняется по алгоритму исключения Гаусса с частичным выбором ведущего элемента по столбцу. Что оэ- начает, что на i-м шаге (i 1, п-1У алгоритма Гаусса исключению элементов a1. (j i+1, п), принадлежащих исходной матрице А А (при ) частично преобразованной матрице А1 (при i 1), предшествует последовательное сравнение их с элемен5 то аЬ если очередной элемент la}il |a ;;i .осуществляется переста- новка j-й и i-й строк, т.е. i-я строто аЬ если очередной элемент la}il |a ;;i .осуществляется переста- новка j-й и i-й строк, т.е. i-я строка становится j-й и наоборот. В про-, тивном случае перестановки строк не

1

происходит. Только после окончания всех (на данном шаге) операций срав- нения и перестановок (т.е. процесса выбора ведущего элемента) начинаете

и

процесс исключения элементов a.j преобразования строк с (1+1)й по n-ю,матрицы А (а в нашем случае еще и В ), заключающийся в попарном суммировании каждой из этих строк с 1-й строкой (объединенной матрицы в нашем случае), предвзрительноумноженной на коэффициент т:; -а. /а 7., . Однако, поскольку в объединенной матрице под матрицей А находится матрица -С, которую необходимо привести к нулевой матрице, никаких перестаново строк матриц С и D со строками матри А и В производить нельзя. Вследствие этого устройство осуществляет выбор ведущего элемента среди элементов 1-го столбца матрицы А1 (на i-м шаге а процесс исключения осуществляет элементов 1-го столбца матриц А1 и С , т.е среди элементов 1-го столбца всей объединенной матрицы I(i - 1, )„ Все признаки переста- новки строк запоминаются и передают- 1ся между модулями в качестве элементов нижней треугольной матрицы перестановок V fUj;} За (п-1) шаг алгоритма Гаусса обнуляется (п-1) столбцов объединенной матрицы. Однак для получения правильного результата необходимо обнулить и n-й столбец матрицы С. Поэтому в данном случае алгоритм Гаусса имеет и n-й шаг, на котором отсутствует процесс выбора ведущего элемента (элемент аЦ сразу становится ведущим, так как его не с чем сравнивать), а процесс исключени производится аналогично предыдущим шагам алгоритма.

Поступление исходных данных организовано следующим образом. На 1-й вход устройства (i 1,п) каждый так поступает элемент i-го столбца объединенной матрицы, начиная сГ элемента а (; и заканчивая -С-р; , на (п+К)-й вход устройства (К 1,К) - аналогично, начиная с элемента Цк и заканчивая dpK. В свою очередь, элементы каэдого столбца объединенной матрицы поступают «на соответствующие входы устройства со сдвигом на один такт, т.е. элемент поступает на 1-й вход устройства в 1-м такте его работы, а элемент - в (п+К)-м такте работы устройства.

8

Устройство работает следующим образом.

Положим п 3, р М 2. Условим4- ся, что прием информации во все регистры, в том числе в регистры блоков задеркки, в D-триггеры 25 и 36 всех вычислительных модулей осуществляется по заднему фронту синхроимпульса,

т.е. в конце такта, а во все остальные триггеры и счетчик 46 - по переднему оронту«синхроимпульса, т.е. в начале такта, Условимся также, что изменение состояния счетчиков 23 и 41

r происходит по положительному, а счетчиков .24 - по отрицательному перепаду сигнала на их декрементирующих входах. Считаем, что перед началом вычислений (т+1)-е разряды всех регистров блока 14.1 установлены в нулевое состояние (п - разрядность операндов) .

Импульс пуска, поступающий на вход запуска устройства, устанавливает в

5 единицу RS-триггер 47, а также поступает на вход выбора режима счетчика 45, в который записывается значение (п+р-1) 4, и через элемент ИЛИ 48 на вход выбора режима счетчика 46.

В первом такте по переднему фронту синхросигнала в счетчик 46 записывается информация с выхода счетчика 45, т.е. (п+р-1), на выходе отрицательного переноса счетчика 46 - нуль, а также устанавливаются в единицу D5 триггеры 20.1 и 21.1, после чего в счетчики 23.1 и 24.1 записываются значения (п-1) 2 и Ц-1) 0. Кроме того, элемент а( а исходной матрицы поступает на второй информацион0 ный вход модуля 1.1 и, пройдя через коммутаторы 10.1 и 6.1, записывается в коние такта в регистр 7.1 (на управляющих входах обоих коммутаторов - единицы), а единица с выхода триггера

5 21.1 записывается в (т+1)-й разряд Р1 блока 14.1, на инверсном выходе счетчика 24.1 - нуль.

Во втором такте счетчик 46 уменьшает свое значение на единицу, на вы0 ходах триггеров 16.1, 20.2 и 21.2 появляются единицы, а на выходе тригге.10

ра 21.1 - нуль, элемент а

12

по

ступает на вход модуля 1.2 и записывается в регистр 7.2, а единица с в ы- 5 хода триггера 21,2 записывается в (т-М)-й разряд Р1 блока 14.2, а « а поступает через коммутатор 10.1 на входы коммутаторов 6.1 и 8.1 и схемы 9.1 сравнения, на другие входы

которых поступает а

тусгь

«,Ј

5 |a,| . Тогда нуль (UЈ, 0) с выхода схемы 9.1 сравнения (признак отсутствия перестановки строк) поступа- ет через элементы 18.1, 22.1 и коммутатор 19.1 (на его управляющем входе имеется нуль) на управляющие входы .коммутаторов 6.1 и 8.1, вследствие чего а, перезаписывается в регистр

14

7.1, а а. записывается в Р1 блока 14.1. Кроме того, единица из (т+1)-го разряда Р1 блока 14.1 переписывается в Р2 блока 14.1 и появляется на его выходе, записывается в триггер25.1и появляется на входе признака перестановки строк модуля 1.2, в счетчики 23.2 и 24.2 записываются значения соответственно (п-1) и 1, и на инверсном выходе отрицательного переноса счетчика 24.2 - единица, которая находится там до тех пор, пока содержимое счетчика 24.2 не станет равным нулю.

В третьем такте счетчик 46 умень- шает свое значение на единицу, на выходах триггеров 16.2,20ч 3,21.3 и 15.1 появляются единицы, а на выходе тригге- ра 21,2 - нуль, элемент а поступает на вход модуля 1.3 и записывается в регистр 7.3, а единица с выхода триггера 21.3 - в (m+O-й разряд Р1 блока 14.3, aL поступает на вход модуля 1.2, поскольку на выходе счетчика 24.2 находится единица, коммутатор

в Р1 блока 14.2, а а« перезаписывается в регистр 7.2. Кроме того, а( поступает на входы коммутаторов 6.1, 8.1 и схемы 9.1 сравнения, на другие входы которых поступает а,,, . Пусть

|а „|с ( . Тогда единица (U3( с выхода схемы 9.1 записывается в триггер 25.1 и управляет коммутаторами1 6.1 и 8.1, вследствие чего а, записывается в Р1 блока 14.1 (а переписывается в Р2 блока 14.1), а а51 записывается в регистры 7.1 и 5.1. Кроме того, единица из (т+1)-го разряда Р1 блока 14.2 переписывается в Р2 блока 14.2, на выходе счетчика 24.3 находится единица, счетчики 23.1, 24.1 не меняют своего состояния, поскольку на их управляющем .входе остается единица (режим параллель ного занесения информации).

1)

1

7358681°

В четвертом такте счсмчнк 46 уменьшает свое значение на единицу, а в счетчик 41.1 записывается (), на выходах триггеров 16.3, 34.1, 35.1 и 15.2 появляется единица, на выходе триггеров 16.1 и 21.3 - нуль, Ь

Ш

15

25

bt поступает на вход модуля 2.1 и записывается в регистр 31.1, а единица с входа триггера 35.1 - в (т+1)-й разряд Р1 блока 42.1, поступает на вход модуля 1.3 и, поскольку на коммутаторы 6.2 и 8.2 поступает 1)г, 0, записывается в Р1 блока 14,3, U 2, записывается в триггер 25.3, а а перезаписывается в регистр 7.3. Кроме того, а 32 поступает на вход модуля 1.2, и, поскольку U 3{ 1, записывается в Р1 блока 14.2, a al, - JQ в регистры 7.2 и 5.2. Кроме того, единица из (m+1)-ro разряда Р1 блока 14.3 переписывается в Р2 блока 14.3, 1-${ переписывается в триггер 25.2, -С( поступает на входы коммутаторов 6.1 и 8.1 и, поскольку на выходе элемента И 18.1 (независимо от выхода схемы 9.1 сравнения) нуль, -С ( записывается в Р1 блока 14.1, а 2 через коммутатор 11.1 поступает на второй вход блока 4.1 умножения-деления, на

ЧПоt

первый вход которого поступает а из регистра 5.1, блок 4 выполняет деление и результат тг( принимается в регистр 26.1, пройдя через коммутатор 12.1 (па выходе элемента .

35 ИЛИ 17.1 нуль).

В пятом такте в счетчик 41.2 записывается (п-1), счетчик 46 уменьшает свое значение на единицу, его содержимое становится равным нулю и на

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

,

) 45 и этом же такте на выходах триггеров 34.2, 35.2 и 15.3 появляется единица, на выходе триггеров 16.2 и 35.1 - нуль, b|u поступает на вход модуля 2.2 и записывается в регистр 31.2, а 50 единица с выхода триггера 35.2 - в (т+1)-й разряд Р1 блока 42.2, b поступает на вход модуля 2.1 и, поскольку Ugt 0, записывается в Р1 блока 42.1, Ugj записывается в триггер 36.1, а Ь1 перезаписывается в регистр 31.1. Кроме того, а, поступает на вход модуля 1.3 и, так как U s t, а записывается в Р1 блока 14.3 (а 23 переписывается в Р2 блока

55

11

поступает alz из Р2 блока

, « зультат а 2 -ип t, У а 52

V2

г

ся в Р1 блока 27.2, а ш ется в регистр 26.2 (на выходе элемента ИЛИ 17.2 единица). В этом же такте -Сщ поступает на входы коммутаторов 6.1 и 8.1 и записывается в Р1 блока 14.1, -С переписывается в Р2 блока 14.1, a j поступает на бло 4.1, с выхода которого значение

. -а (| /а Ј{ m принимается в регистр 26.1.

, /

В цветом такте в счетчик 46 записывается (п+р-2) 3 с выхода счетчика 45, триггеры 21.1 и 20.1 устанавливаются соответственно в единицу и нуль, единица с выхода триггера 21.1 записывается в конце такта в .(т+1)-й разряд Р1 блока (аналогично первому такту), триггер 44.1 устанавливается в единицу, а триггеры 15.3, 16.3 и 35.2 - в нуль, поступает на вход модуля 2.2 и записывается в Р1 блока 42.2, записывается в . триггер 36.2, b} перезаписывается в регистр 31.2, bjj поступает на вхо модуля 2,1 и (U 31 1)

записывается

в регистры 31.1 и 29.1, а Ь14 - в Р1

блока 42.1, коммутаторов

поступает на.входы 6.3 и 8.3 и, поскольку

на выходе элемента И 18.3 нуль,

записывается реписывается

в Р1 блока 14.3, пе- в Р2 блока 14.3, гог{ поступает на блок 4.3, который выполняет умножение, на второй вход сумматора 13.3 поступает a|j и результат а2з+пг,«аэз а|3 принимаемся в Р1 блока 27.3-, а тг переписывается в регистр 26.3. В этом же такте -С поступает на вход модуля 1.2 и записывается в Р1 блока 14.2, Cw переписывается в Р2 блока 14.2, m э -а{, , поступает на блок 4.2, ко торый выполняет умножение, на вход сумматора 13.2 поступает яз Р2 блока 14.2, и результат aja

m

Я2

а32

принимается в Р1

ы.

блока

«Я i5

переписывается в регистр 26.2,

735868

-С

10

15

20

«

поступает на

12

блок 4.1, с выхода С« /аэг a 4{ прйкоторого значение

нимается в регистр 26.1, -Cj переписывается в Р2 блока 14.1.

В седьмом такте аналогично второму такту триггеры 20.2, 44.1 и 21.1 устанавливаются в нуль, триггеры - 44.2, 21.2 и 16.1 - в единицу счетчик уменьшает свое состояние на единицу (до.минус единицы), но на его инверсном выходе остается нуль, единица с выхода триггера 21.2 записывается в (т+О-й разряд Р1 блока 14.2, поступает на вход модуля 2,2 и записывается в регистры 31.2, 29.2, a bf2 - блока , b2i переписывается в Р2 блока 42.2, U3 запив

сывается в триггер ет на вход модуля в Р1 блока 42.1

в Р2 блока 42.1),

m

2

Ј

/4

повто-.

ступает на умножитель 28.1, на

рой вход сумматора 39.1 поступает Ь

и результат bЈ{ +И2 bj( b

ется в Р1 блока 40.1, a m

вается

те -С

тельного модуля

2

принима- переписыв регистр 38.1. В этом же так- 2$ поступает на вход вычисли1.3 и записывается в

5

5

0

5

0 Р1 блока 14.3,

ш

3f

поступает на блок

вход сумматора

N3

и

принимается

в Р1 блока 27.3, а переписывается в Р2 блока 27.3, га3 - в регистр 26.3. В этом же такте -С переписывается в Р2 блока 14.2, т4 С /а поступает на блок 4.2, который выполняет умножение, на вход сумматора 13.2 поступает из Р2 блока 14.2 и результат С|а принимается в Р1 блока 27.2, а| принимается в Р2 блока 27.2, а|г из Р2 блока 27.2 через коммутатор 10.2 поступает на входы коммутаторов 8.2 и 6.2 и записывается в регистр 7.2, т4, переписывается в регистр 26.2, -С, по-1 ступает на блок 4.1, с выхода которого значение Сг, /ajf т$( принимается в регистр 26.1.

В восьмом такте триггеры 20.3, 21.2 устанавливают в нуль, триггеры 21.3, 15.1 - в единицу, счетчик 24.2 уменьшает свое значение на единицу, и на его инверсном выходе появляется нуль, единица с выхода триггера 21.3 записывается в (и+1)-й разряд Р1 блока 14.3, dte поступает на вход модуля 2.2 и записывается в Р1 блока

,2, -2, .2,

Ъ

m

42

42

28

принимается

13

переписывается в Р2 блока поступает на умножитель

- на второй вход суммато результат +тг,- Ь,г Ь2 40.2,

m

переписываетсяже такте d2j 2.1

г В этом

в Р1 блока в регистр 38.2. поступает на вход модуля 2.1 и записывается в Р1 блока 42.1, d( переписывается в Р2 блока 42.1, поступает на умножитель 28., на сумматор поступает Ьм и рна

зультат Ъм b в PI блока 40.1, га в регистр 3S.1.

-4i

принимает Л переписывается В этом же такте -Cg-j переписывается в Р2 блока 14.3, Ш4 поступает на блок 4.3 который выполняет умножение, на

4

Р

4

«

сумматор 13.3 поступает и результат ,-аэ5 принимается в Р1 блока 27.3, а2 через

Э

коммутатор 10.3 поступает на входы коммутаторов 8.3 и 6.3 и записываетс в регистр 7.3, т,

41

переписывается в - в регистр 26.2,

регистр 26.3, та5| а также поступает на блок 4.2, который выполняет умножение, на сумматор 13.2 поступает -С и результат

С22 принимается переписывается в через коммутатор

.в Р1 блок Р2 блока 10.3 по+го5,- аза.

27,2, а|г

ступает на входы схемы 9.2 сравнения

где сравнивается с а|2.

Пусть |а|г| |а|2| . Тогда единица (J™ 1 с выхода схемы 9.2 управляет коммутаторами 8.2 и 6.2 так, что а|2 записывается в регистры 7.2 и 5.2, а|г - в Р1 блока 14.2. Кроме того, счетчик 23.1 уменьшает свое значение на единицу, и длина блока 14.1 становится равной единице.

В девятом такте с входа модуля 2.2 записывается в Р1 блока 42.2, d,2 переписывается в Р2 блока 42.2, с выхода сумматора 39.2 результат . b|z принимается в Р1 блока 40,2, raj, переписывается в регистр 38.., переписывается в Р2 блока 42.1, с выхода сумматора 39.1

1 - d4 принима- 40.1, а Ь| записывается в регистр 31.1, с выхода сумматора 13.3 результат -Cgj-Hn5|« a, С|- принимается в Р1 блока 27.3, С, переписывается в Р2 блока 27.3, принимается в регистры 7.3 и 5,3

результат

ется в Р1 блока

d« +m4i b3i

Я2 &М

а а| - в Р1 блока 14.3, С записывается в Р1 блока 14.2, блок 4.2 вы- полняет деление, и результат -a|2/a|j, принимается в регистр 26.2

1735868

14

блока тель

мматора Ь2

пегэтом

модукаблока ель и реимаетсяается такте ока к 4.3, на

Р

4

«

принирез

ходы ывается

тся в 26.2,

котомматорт +

1 блока блока 3 повнения,

диница авляет то а|2 5.2, ого, че14.1

моду42.2, 42.2, тат в Р1 в рев Р2 39.1

инима- исывасумма, 7.3, 7.3, и 5,3,

писы.2 вы- г 26.2

10

15

20

25

30

35

40

4S

50

55

нимается в Р1 блока 40.2, Ь| мается в регистр 31.2, п

В десятом такте dg- переписывается в Р2 блока 42.2, с выхода сумматора 39.2 результат d j d2 припринирегистр 31.2, п5| переписывается в регистр 38.1, с выхода сумматора 39.1 результат dZ(+m5(b91

принимается в Р1 блока 40.1, записывается в регистры 31.1 и 29. 1, Cfa - в PI блока 14.3, с выхода сумматора 13.3 результат а| +n)-jj. a2

Ь «

«

аЭ

а

«

принимается в Р1 блока 27.3,

блок i 4.2 выполняет деление, и результат-, , принимается в регистр 26.2.

В одиннадцатом такте с выхода сумматора 39.2 результат da2+mj|«bja « d2 принимается в Р1 блока 40.2, Ь| принимается в регистры 31.2, 29.2, с выхода сумматора 39.1 результат b|( +т$г-Ъ л b3 принимается в Р1 блока 40.1, d 41 переписывается в Р1 блока 42.1, а3,, - в Р2 блока 27.3, С|3 - в Р1 блока 14.3, с выхода сумматора 13.3 результат а2,, CL принимается в Р1 блока 27.3,блок 4.2 выполняет деление, и результат m g -С|2/а|, принимается в регистр 26.2, т4г переписывается в регистр 26.3.

В двенадцатом такте с выхода сумматора 39.2 результат b2,+тзг эг

Ь|г

принимается в Р1 блока 40.2, переписывается в Р2 блока 40.2, с выхода сумматора 39.1 результат d +m42- b2,, d принимается в Р1 блока 40.1, ( принимается в Р1 блока 42.1, с выхода сумматора.13.3 результат С2,, +тп-2. а2. принимает глблока 27.3,

аЬ

49

принимается

Р1 блока 40.2,

выхода сумся в Р1 в регистр

В тринадцатом такте с выхода сумматора 39.2 значение d2t +m42- b|t d;L принимается в d2,z - в Р1 блока 42.1, с матора 39.1 значение d2 , « d| принимается в Р1 блока 40.1, Ъ3„ - в регистр 31.1, длина блока 14.3 уменьшается на единицу и становится равной нулю (т.е. данные проводят с его входа на выход без задержки) , С3- поступает на вход блока 4.3, он выполняет деление, и результат п43 /а33з принимается в регистр 26.3.

В четырнадцатом такте с выхода сумматора 39.2 значение d +mw bja « ет dL принимается в Р1 блока 40;2,

1517

- в регистр 31,2, длина блока 42. I становится равной нулю, и с выхода сумматора 39.1 значение d-}f + +11143 Ь3з1 « принимается в Р1 блока

m 53 сгэ/а1з принимается в регистр 26.3, а пцэ - в регистр 38.1.

Г пятнадцатом такте длина блока

в регистр 37.1 и появляется на первом выходе устройства.

В последнем шестнадцатом такте с выхода сумматора 39.2 значение d|2+ +т,уз Ъ3эг Хг принимается в регистр 37.2 и появляется на втором выходе

устройства. На этом вычисление элементов результирующей матрицы X СА В + D заканчивается. Таким образом, полное время реализации алгоритма Т n()/2+n(p+1)+p+2+M-1 тактов, причем элементы результирую- щей матрицы X выдаются на выходы устройства последние р+М-1 тактов, причем с r-го выхода устройства вьщается r-й столбец матрицы X (г 1,М) аналогично поступлению исходных элемен- тов матриц В и D на соответствующие входы устройства. Однако в случае решения потока аналогичных задач период работы устройства составляет t Т - - (п+М-1) тактов, . n()/2+p(n+ И)+11-1 тактов. Это означает, что первый элемент а( очередной объеди- .ценной матрицы можно подавать через t тактов после подачи элемента а предыдущей объединенной мгтрицы. В нашем случае Т 16, t 12 тактов, следовательно, элементы следующей матрицы можно начинать подавать на вход устройства (вместе с импульсом запуска) с тринадцатого такта.

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

16

Q

j

0

5

0 jc 40 е м

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

четвертого и пятого коммутаторов и входу выбора блока умножения- деления, первый и второй информационные входы которых подключены соответственно к выходам четвертого коммутатора и первого регистра, информационный вход которого соединен с информационным входом второго регистра и выходом первого коммутатора, первый и второй информационные входы вычислительного модуля подключены к первым информационным входам соответственно четвертого и третьего коммутаторов, вторые информационные входы которых подключены соответственно к выходам второго и первого блоков элементов задеркки, входы управления которых подключены соответственно к выходу первого счетчика и входу Р устройства, информационный выход вычислительного модуля соединен с выходом третьего регистра, информационный вход которого подключен к выходу пятого коммутатора, первый и второй информационные входы которого соединены со- ответственно с первым информационным входом четвертого коммутатора и объе-- диненными первым входом сумматора и выходом блока умножения-деления, выход сумматора подключен к информационному входу первого блока элементов задержки, входы установки первого и второго счетчиков подключены соответ-1 ственно к входам п-1 и Р-1 устройства, отличающееся гем, что, с целью расширения функциональных возможностей за счет вычисления выражений вида X СА Г- + D, в уст

ройство введены М вычислительных модулей (М - число столбцов матрицы В), каждый из которых содержит умножитель, сумматор, два блока элементов задержки, счетчик, элемент ИЛИ, четыре триггера, четыре регистра и два коммутатора, причем синхровход, вход признака перестановки строк и первый инсЬормационный вход r-го вычислительного модуля (г п+1 , m+М) подключены к одноименным выходам (г-1) вычислительного модуля, вторые информационные вход и выход r-го вычислительного модуля являются соответственно (п+ +г)-м информационным входом и r-м выходом устройства, причем в каждом г-м вычислительном модуле первый и второй разряды синхровхода подключены соот-- ветственно к информационным входам первого и второго триггеров, выходы которых являются соответственно jrep

0

5

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

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

коммутатора и выходу третьего регистра, информационный вход которого подключен к выходу сумматора и информационному входу первого блока элементов задержки, выход которого подклюQ чён к второму информационному входу третьего коммутатора, выход которого подключен к объединенным первым информационным входам первого и второго коммутаторов, объединенные вторые ин Формационные входы которых подключены к выходу второго регистра, информационный вход которого подключен к выходу первого коммутатора и информационному входу первого регистра, выход которого подключен к первому входу умножителя, второй вход и выход которого подключены соответственно к информационному входу четвертого регистра и первому входу сумматора, второй вход которого подключен к второму

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

0

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

. W Ц