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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУ БЛИН рр С 06 F 15/347

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

H asXOpCvOVv cs Pemn cxsv

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

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

ПРИ ГКНТ СССР (21) 4811405/24 (22) 09.04.90 (46) 23.05.92. Бюл. K - 19 (71) Киевский политехнический институт (72) Роман Выжиковски (РЕ.),- Ю.С.Ка-. невский и О.В.Масленников (SU) (53) 681.3 (088.8) (56) Авторское свидетельство СССР

Р 1443003, кл. G 06 F 15/348, 1988.

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

Р 1226484, кл. С 06 F 15/31, 1986.

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

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

Гаусса с периодом 2п тактов...SU„„1735868 A 1 2 (54) УСТРОЙСТВО ПНЯ ОПЕРАЦИЙ НАД ИАТ-.

РИЦА2Ш (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных матричных вычислителях. Цель изобретения — расширение функциональных возможностей за счет вычисления выражений вида Х = СА " В + D. Цель достигается тем, что в устройство введены И вычислительных модулей (Мчисло столбцов матрицы С) со связями.

Устройство работает в соответствии с алгоритмом Фаддеева с частичньи выбором ведущего элемента. 4 an.

С:

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

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

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

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

5868 4

173

+ 9, где. Л van), В 1;кМ, Cfp>n) и

9 p@If) — матрицы (в частном случае, при И = 1, р = 1 матрицы С, В и матрица D могут быть векторами размерностью и и скаляром соответственно) . °

Иа фиг,1 представлена структурная схема устройства для операций над матрицами, на фиг.2 — структурная схема блока синхронизации, на фиг.3 и 4 — структурная схема вычислительного модуля соответственно первого и второго типа.

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

1.1 - 1.п первого типа и 2.1 — 2.If второго типа и блок 3 синхронизации, причем вход запуска устройства подключен к одноименному входу блока 3, выход которого соединен с синхровходом вычислительного модуля 1.1, выход синхронизации, выход признака перестановки строк и информационный .выход вычислительного модуля 1.1i (К =

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

1.(К+1), второи информационный вход вычислительного модуля 1.P (P = 1,и) является Р-м информационным входом устройства, синхровход, вход признака перестановки строк и первый информационный вход вычислительного модуля

2.r (r = 1,If) подключены к одноименным выходам вычислительного модуля

2.(r-1), вторые информационные вход и выход вычислительного модуля 2.r являются. соответственно (n+r)-м информационным входом и r-м выходомустройства.!

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

10 !

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

16.Р, выход которого подключен к первым входам первого элемента ИЛИ 17.P и элемента И 18.Р, второй вход которого является выходом схемы 9.P сравнения, а выход его подключен к второму входу шестого коммутатора 19.Р, первый вход которого является входом признака перестановки строк вычислительного модуля, первый и второй входы которого подключены к входам соответственно второго 20.Г и третьего

21.Г D-триггеров, выход последнего подключен к первому входу второго элемента ИЛИ 22, к второму входу блока 14.Р, входу установки триггера

16.Г, декрементирующему входу второго счетчика 24.Р и является вторым раз- . рядом выхода синхронизации вычислительного модуля, первьпЪ разряд кото- рого подключен к выходу триггера

20.Г, к управляющему входу коммутатора 10.Р и к входу выбора режима (параллельное занесение информации или счет) счетчиков 23.Р и 24.Р, выход счетчика 23.Р подключен к управляющему входу блока 14.P первый вход которого связан с выхопом коммутатора

8.Г, управляющие входы коммутаторов

6.P и В.Г объединены и подключены к выходу элемента ИЛИ 22, второй вход которого связан с входом четвертого

D-триггера 25.P и с выходом коммутатора 19.Г, управляющий вход которого подключен к выходу отрицательного переноса счетчика 24.P и к второму входу элемента ИЛИ 17.Р, выход которого подключен к входу выбора режима блока 4.Р и к управляющим входам коммутаторов 11.Р и 12.P выход коммутатора 12.P подключен к входу регистра

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

П-триггера 25.Р, выход коммутатора .

11.Р подключен к второму входу блока

4.Р,.выход сумматора 13.Р - к входу блока 27.Р,. выход которого связан с

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

Вычислительный модуль 2.К содержит умнонитель 28.К, первый (К

1,И) вход которого связан с выходом первого регистра 29.К, вход которого подключен к выходу первого коммутатора ЗО.K и к входу второго регистра 31.К, выход которого подключен, к первым входам первого ЗО.К и второго 32.К коммутаторов, вторые входы которых подключены к выходу третьего коммутатора ЗЗ.К, первый .вход которого является вторым информационным входом модуля, первый и второй разряды аинхровхода и вход признака перестановки строк вычислительного модуля являются соответственно входами первого 34.К, второго

35.K и третьего 35.К D-триггеров, выходы которых являются соответственно первым и вторым разрядами выхода синхронизации и выходом признака перестановки строк вычислительного мо дуля, второй и первый информационные выходы которого подключены соответственно к выходам третьего 37.К и четвертого 38.K регистров, вход последнего является первым информационным входом модуля и подключен к второму входу умножителя 28.K, abmpp которого связан с первым входом сумматора

39.К, выход которого подключен к входам регистра 37.I: и первого блока

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

42.K элементов задержки, первые выход и вход которого подключены соответственно к второму входу сумматора

39.K и к выходу коммутатора 32.К, управляющие входы коммутаторов ЗО.К и

32еК объединены и подключены к выходу элемента ИЛИ 43.К, первый и второй входы которого подключены соответственно к входу триггера 36.K и к выходу триггера 35.К, управляющий вход регистра 29.К подключен к декрементирующему входу счетчика 41.K и к выходу четвертого В-триггера 44.К, вход которого является вторым выходом .бло- ка 42.К, второй вход которого соединен с выходом D-триггера 35.К,- управ-"

5868 6

А В А В

55 ляюций вход блока 40.K связан с вхо» дом Р устройства. .Устройство для операций над матрицами предназначено для вычисления с помощью алгоритма фаддеева выражения вида Х CA 1 В + D где в общем случае Л (а1Д,. В 1Ь;а1, С (ep>1„

D - f d Д вЂ” матрицы, йредставленные

s виде оЬъединенной матрицы, причем суть алгоритма сводится к тому, что, после обнуления в объединенной матрице нижнего левого квадранта (т.е. элементов матрицы -С), в правом нижнец квадранте (на месте матрицы D) получают искомый результат XjpxII): фактически это выражение позволяет реыать дополнительно еще несколько задач, а именно: решение системы линейных алгебраических уравнений с несколькими (или одной, в зависимости от размерности В) правыми частями:

Х = Л В при С = Х, D-= 0; обращение матрицы Х- = Л" при С = В = Х, D = P; умножение матриц (или матрицы) на вектор в зависимости от размерности

В: Х = С.В при Ь = Х, D = 0; умножение со сложением матриц Х = С В + D при Л = I; задача адаптивной фильтрации, которая использует выражение Х

= СЛ + D при В = Х, где Х вЂ” единичная матрица.

Обнуление нижнего левого квад- ранта объединенной матрицы можно осуществить, применяя к ней исключение Гаусса, до приведения матрицы А к верхнетреугольному виду. Тогда автоматически на месте матрицы -С получается нулевая матрица. При этом с .целью обеспечения численной устойчивости вычислений преобразование матрицы А выполняется по алгоритму исключения Гаусса с частичным выбором ведущего элемента по столбцу. Это означает, что на е-м шаге (i = 1, а-1Ã алгоритма Гаусса исключению элементов а . (j = i+1, и)., принадлежащих исходной матрице A = At (при i = 1) или уже частично преобразованной матрице A (при i > 1), предшествует по-. следовательное сравнение их с элемен- том а „, и, если очередной элемент а .;Iy (а . j, осуществляется переста-, новка j-й a i-й строк, т.е. i-я стро» ка становится j-й и наоборот. В про-, тивном случае перестановки строк не

173 происходит. Только после окончания всех (на данном шаге) операций срав- Ф пения и перестановок (т.е, процесса выбора ведущего элемента) начинается процесс исключения элементов а. и ! 1 преобразования строк с (i+1)-й по п-ю,матрицы А (а в нашем случае еще и В ), заключающийся в попарном суммировании каждой из этих строк с i-u строкой (объединенной матрицы в на-. шем случае), предварительно,умноженной на коэффициент m " "= -à ja, .

51 31 11

Однако, поскольку .в объединенной матрице под матрицей А находится матрица -С, которую необходимо привести к нулевой матрице, никаких перестановок строк матриц С и D со строками матриц

А и Б производить нельзя. Вследствие этого устройство осуществляет выбор ведущего элемента среди элементов

i-го столбца матрицы Л (на i-м .шаге), а процесс исключения осуществляет среди элементов i-ro столбца матриц

Л и С, т.е среди элементов i-го

1 столбца всей объединенной матрицы . (i = 1, и-1) . Все признаки перестаl новки строк запоминаются и передают ся между модулями в качестве элементов нижней треугольной матрицы перестановок V = Б Д; За (и-1) шаг алгоритма Гаусса обнуляется (и-1) столбцов объединенной матрицы. Однако для получения правильного результата, необходимо обнулить и и-й столбец матрицы С. Поэтому в данном случае алгоритм Гаусса имеет и и-й шаг, на котором отсутствует процесс выбора ведущего элемента (элемент a „„ cpasy

Ц становится ведущим, так как его не с чем сравнивать), а процесс исключения производится аналогично предыдущим в|агам алгоритма.

Поступление исходных данных организовано следующим образом. На i-u вход устройства (i = 1,n) каждый такт поступает элемент i-ro столбца объединенной матрицы, начиная с элемента а <, и заканчивая -Gt,, на (и+К)-й вход устройства (К 1,J ) — аналогично, начиная с элемента Ь,|„ и. заканчивая d „. В свою очередь, элементы каждого столбца объединенной матрицы поступают на .соответствующие входы устройства со сдвигом на один такт, т.е, элемент а<, поступает на i-u вход устройства в х-и такте его работы, а элемент Ь„К вЂ” в (и+К)-м такте работы устройства.

5868

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

Положим и = 3, р = М = 2. Условим ся, что прием информации во все регистры, в том числе в регистры блоков задержки, в D-триггеры 25 и 36 всех вычислительных модулей осуществляется по заднему фронту синхроимпульса, т.е. в конце такта,,а во все остальные триггеры и счетчик 46 - по переднему фронту .синхроимпульса, т.е. в начале такта. Условимся также, что изменение состояния счетчиков .23 и 41 происходит по положительному, а счетчиков .24 — по отрицательному перепаду сигнала на их декрементирующих входах. Считаем, что перед началом вычислений (я+1)-е разряды всех регистров блока t4.1 установлены в нулевое состояние (m — разрядность операндов) .

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

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

В первом такте по переднему фронту синхросигнала в счетчик 46 записывается информация с выхода счетчика

45, т.е. (п+р-1), на выходе отрицательного переноса счетчика 46 .нуль, а также устанавливаются в единицу DЗ5 триггеры 20.1 и 21.1, после чего в счетчики 23. 1 и 24.1 записываются значения (п-1) = 2 и (i-.1) = О. Кроме того, элемент а < = а исходной матрицы поступает на второй информацион4Q ный вход модуля 1.1.и, пройдя через коммутаторы 10.1 и 6. 1, записывается в конце такта в регистр 7.1 (на управляющих входах обоих коммутаторов— единицы), а единица с выхода триггера

4g 21.1 записывается в (m+1)-й разряд

Р1 блока 14,1, на инверсном выходе счетчика 24.1 — нуль.

Во втором такте счетчик 46 уменьшает свое значение на единицу, на вы50 ходах триггеров 16.1, 20.2 и 21.2 появляются единицы, а на выходе триггера 21. t — нуль, элемент а,< = а, по1ступает на вход модуля t 2 и записывается в регистр 7.2, а единица с выхода триггера 21.2 записывается в (н+1)-й разряд Р1 блока 14.2, а (= а поступает через коммутатор 10.1 ! на входы коммутаторов 6.1 и 8.1 и схемы 9,1 сравнения, на другие входы

1 735868

10 которых поступает a« . усть а«, > а . Тогда нуль (U2 = О) с вьтхода схемы 9. 1 сравнения (признак отсутствия перестановки строк) поступз-.l

5 ет через элементы 18.1, 22.1 и коммутатор 19.1 (на его управляющем входе имеется нуль) на управляющие входы . коьа»утаторов 6.1 и 8.1, вследствие чего а перезаписывается в регистр

И

7 1 а а записывается в Р1 блока

2»

14.1. Кроме того, единица из (m+1)-го разряда Р1 блока 14.1 переписывается в Р2 блока 14.1 и появляется на его выходе, U записывается в триггер

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

В третьем такте счетчик 46 уменьщает свое значение на единицу, на выходахтриггеров 16.2,20.3,21.3и 15.1 появляются единицы а на выходе триггеФ

l ра 21.2 — нуль, элемент а4 поступает на вход модуля 1.3 и записывается в ЗО регистр 7.3, а единица с выхода триггера 21.3 — в (»и+1)-й разряд Р1 блока 14 3 а поступает на вход моду22 ля 1.2, поскольку на выходе счетчика

24.2 находится единица, коммутатор

19.2 передает на свой выход U< = О, которое переписывается в регистр

25.2 и управляет работой коммутаторов

6.2 и 8.2 так, что а записывается, в Р1 блока 14.2, а а», перезаписывается в регистр 7.2. Кроме того, а, поступает на входы коммутаторов 6.1, 8. 1 и схемы 9. 1 сравнения, на другие входы которых поступает а„ . Пусть à"» j c I à I . Тогда единица « i = 1) S

« с выхода схеиы 9.1 записывается в триггер 25.1 и управляет коммутаторами 6.1 и 8.1, вследствие чего а » записывается в Pl блока 14.1 (а переписывается в Р2 блока 14.1), а а » щ( записывается в регистры 7. 1 и 5.1.

Кроме того, единица из (m+1)-ro разряда Р1 блока 14.2 переписывается в

Р2 блока 14.2, на выходе счетчика

24.3 находится единица, счетчики

23.1, 24.1 не меняют своего состояния, поскольку на их управляющем .входе остается единица (режим параллель» ного занесения информации).

В четвертом такте счетчик 46 уиеньпает свое значение на единицу, а в счетчик 41.1 записывается (n-1), на выходах триггеров 16. 3, 34, 1, 35. 1 и 15.2 появляется единица, на выходе триггеров 16.1 и 21.3 — нуль, Ъ« !

= Ъ поступает на вход модуля 2.1 и записывается в регистр 31.1, а единица с входа триггера 35.1 — в (m+1)-й

f разряд Р1 блока 42.1, а поступает на вход модуля 1.3 и, поскольку на коммутаторы 6.2 и 8.2 поступает Ug(=

= О, записывается в Р1 блока 14.3, U2 записывается в триггер 25.3, я а перезаписывается в регистр 7.3.

Кроме того, а поступает на вход мо4 дуля 1. 2, и, поскольКу U >< = 1, а»2 записывается в Г1 блока 14.2, а а" в регистры 7.2 и 5.2. Кроме того, единица из (тп+1)-ro разряда Р1 блока

14.3 переписывается в Р2 блока 14.3, Ug» переписывается в триггер 25.2Ä

-С поступает на входы коммутаторов

» (<

6.1 и 8.1 и, поскольку на выходе элемента И 18.1 (независиио от выходя

i схемы 9. 1 сравнения) нуль, -Г «запи» сывается в Р1 блока 14. 1 а через коммутатор 11 ° 1 поступает на второй вход блока 4. 1 умножения-деления, ня

» первый вход которого поступает а из регистра 5.1, блок 4 выполняет деление и результат -G gi /а yi = ти, принимается в регистр 26.1, пройдя через коимутатор 12. 1 (па выходе элемента

ПЛИ 17.1 нуль).

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

В этом z

34.2, 35.2 и 15.3 появляется единица, на выходе триггеров 16.2 и 35.1 нуль Ъ поступает на вход модуля J Д

2.2 i» записывается в регистр 31.2, а единица с выхода триггера 35.2 — в

1 (m+1)-й разряд Р1 блока 42.2, Ь, поступает на вход модуля 2.1 и, поскольку UZ» = О, записывается в

Р1 блока 42.1, Upi записывается в триггер 36. 1 а Ъ перезаписывается н » в регистр 31.1.. Кроме того, а поступает на вход модуля 1.3 и, так как

1 а записывается в Р1 блока ( 3f

14.3 (а переписывается в Р2 блока

735868

12

-C поступает на блок 4. 1, с выхода которого значенйе С,{ /а у{ m4{ принимается в регистр 26.1, -С { переписывается в Р2 блока 14 ° 1.

11

14.3), а а записывается в регистры

f 7.3 и 5.3. Кроме того, U>{ переписывается в регистр 25,3, -С поступает на входы коммутаторов 6.2 и 8.2 и, поскольку на выходе элемента И 18.2 нудь, записывается в Р1 блока 14.2

° ф а { переписывается в Р2 блока 14.2, . m «через коммутатор 11. 2 поступает на блок 4.2, который выполняет умножение, на второй вход сумматора 13.2 поступает а<< из Р2 блока 14.2, и pef зультат а +ш, ° а = а принимает l { 3 ся в Р1 блока 27.2, а ш переписывая{ ется в регистр 26.2 (на выходе элемента ИЛИ 17.2 единица) . В этом же такте -Cg{ поступает на входы коммутаторов 6.1 и 8.1 и записывается в

Р1 блока 14.1, -С{{ переписывается в

Р2 блока 14.1, а«поступает на блок

4.1, с выхода которого значение .-а{{ /а, = ms{ принимается в регистр

26. 1.

; I

В шестом такте в счетчик 46 записывается (и+р-2) = 3 с выхода счетчика 45, триггеры 21.1 и 20.1. устанавливаются соответственно в единицу и нуль, единица с выхода триггера 21.1 записывается в конце такта в (ш+1)-й разряд Р1 блока 14 1 (аналогично первому такту), триггер 44.1 устанавливается в единицу, а триггеры 15.3, I

16.3 и 35.2 —. в нуль, b поступает на вход модуля 2.2 и записывается в

Р1 блока 42.2, Uq{ записывается в

{ триггер 36. 2, Ь {g .перезаписывается в регистр 31.2, Ь < поступает на вход модуля 2.1 и (Us{ = 1) записывается в регистры 31..1 и 29.1 а Ь - в Р1

{

Э {{ блока 42.1, -С„> поступает на. входы коммутаторов 6.3 и 8.3 и, поскольку на выходе элемента И 18.3 нуль, записывается в Р1 блока 14. 3 а { пе° р пе реписывается в Р2 блока 14. 3 m noО ступает на блок 4.3, который выполняет умножение, на второй вход сумматора 13.3 поступает а и результат

{ а +ш«а э = а принимается в Р1 блока 27.3; а ш{ переписывается в регистр 26.3. В этом же такте -С га цоступает на вход модуля 1.2 и записывается в Р1 блока 14 ° 2, -С{ переписывается в Р2 блока 14.2, ш { =

{ .= .-a« /а { поступает на блок 4.2, ко . торый выполняет умножение, на вход сумматора 13.2 поступает а из Р2 .блока 14.2, и результат а +m " а

{ М s2

= а принимается в Р1 блока 27.2, m переписывается в регистр 26.2, В седьмом такте аналогично второму такту триггеры 20.2, 44.1 и 21.1 устанавливаются в йуль, триггеры

1Î

44.2, 21.2 н 16.1 — в единицу счетчик 24.1 уменьшает свое состояние на единицу (до минус единицы), .но на его инверсном выходе остается нуль, единица с выхода триггера 21.2 записыва15 ется в (m+t)-й разряд Р1 блока 14.2

° Я

Ъ поступает на вход модуля 2.2 и записывается в регистры 31.2, 29.2, а b« - P1 блока 42.2, Ь перепи{ сывается в Р2 блока 42.2, Us{ записывается в триггер 36.2, д{{ поступает на вход модуля 2.1 и записывается

4 . в Р1 блока 42. 1 (Ь {{ переписывается в Г2 блока 42. 1), m = -а, /а { поступает на умножитель 28.1 на втоФ ф

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

{ { 2. г{ и результат Ь +m2{ b3{ =Ъ, принимается в Р1 блока 40.1, a m { переписывается в регистр 38.1. В этом же такте -С поступает на вход вычисли тельного моцуля 1.3 и записывается в

ЗО Р1 блока 14.3, m поступает на блок

4.3, который выполняет умножение, на вход сумматора 13.3 поступает а и

{9 результат a{S+m { ass =а принимается

55 в Р1 блока 27.3, а переписывается в Р2 блока 2 7. 3, m >, — в регистр

26.3. В этом же такте -С переписы{ вается в Р2 блока 14.2 m4 = С /а

4{ {g Р поступает на блок 4.2, который. выполняет умножение, на вход сумматора

13.2 поступает -С нз Р2 блока 14.2 и результат -С, +m4 ° а = С прини{

I Зй= мается в Р1 блока 27.2 а принимаsz ется в Р2 блока 27.2, а2 из Р2 блока 27.2 через коммутатор 1.0.2 посту„, пает на входы коммутаторов 8.2 и 6.2 и записывается в регистр 7.2 m neУ 4,( реписывается в регистр 26.2 -С по-, ° в ступает на блок 4.1, с выхода которог о значение С { /а { = ms{ принимается

{ { в регистр 26.1.

В восьмом такте триггеры 20., 21.2 устанавливают в нуль, триггеры

21.3, 15. 1 -. в единицу, счетчик 24.2 уменьшает свое значение на единицу, и на его инверсном выходе появляется нуль, единица с выхода .триггера 21.3 записывается в (и+1)-й разряд Р1 бло- ф ка 14.3, d поступает на вход модуля 2.2 и записывается в Р1 блока

1 735868

42,2, Ь переписывается в Р2 блока

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

28.2, Ь вЂ” на второй вход сумматора гя

39.2, РеэУльтат Ь г+пг, Ь г = Ьг принимается в Р1 блока 40.2, ш пе, реписывается в регистр 38. 2. В этом же такте d поступает на вход моду( ля 2 ° 1 и записывается в Р1 блока

42.1, d)t переписывается: в Р2 блока

42.1, шз поступает на умножитель

28.1, на сумматор поступает Ь и результат b«+m>, Ьэ = Ь г принимается в Р1 блока 40.1, m>< переписывается в регистр 38.1. В этом же .такте

-С переписывается в Р2 блока

14. 3, т4 поступает на блок 4. 3, который выполняет умножение, на сумматор 13.3 поступает -С ! и результат -С +m < ° а = С принимается в Р1 блока 27.3, а через. коммутатор 10.3 поступает на входы коммутаторов 8.3 и 6.3 и записывается в регистр 7.3, m< переписывается в регистр 26.3, m>, — в регистр 26.2, а также поступает на блок 4.2, который выполняет умножение, на сумматор

13.2 поступает -Сг и результат -С г+

+m51 азу = C z принимается.в Р1 блок

27.2, С, переписывается в Р2 блока

27,2, а через коммутатор 10.3 поступает на входы cxe b! 9.2 сравнения, где сравнивается с а

Пусть а I () а . Тогда единица гг зг

U = 1 с выхода схемы 9.2 управляет

Зг

2 коммутаторами 8.2 и 6.2 так, что а записывается в регистры 7.2 и 5.2, аг — в Р1 блока 14.2. 1;роме того, гг счетчик 23.1 уменьшает свое значение на единицу, и длина блока 14.1 становится равной единице.

В девятом такте d с входа модуля 2.2 записывается в Р1 блока 42.2, I д, переписывается в Р2 блока 42.2, с вьмода сумматора 39.2 результат

Ь +m> Ъ = Ъ, принимается в Р1 (Я. блока 40,2, m> переписывается в регистр 38.2, d << переписывается в Р2 блока 42.1, с вьмода сумматора 39.1 (( результат d«+m«, Ь, = с1«принимается . в Р1 блока 40. 1, а Ь- "эаписыва2 ется в регистр 31.1, с выхода сумматора 13.3 результат -С »+ш аН

{ (= С » принимается в Р1 блока 27.3, С . переписывается в Р2 блока 27.-3; а принимается в регистры 7.3 и 5,3, а az - в Р1 блока 14.3, С записывается в Р1 блока 14.2, блок 4..2 выполняет деление, и результат in.yz, -а »/а принимается в регистр 26.2.

14

В десятом такте д переписывается в Р2 блока 42.2, с выхода сумматора

39.2 результат 1 +ш b>z 1г npvнимается в Р1 блока 40.2, bz принииается .в регистр 31.2, и йереписьвается в регистр 38.1, с выхода сум1 матора 39.1 результат d><+ш Ь

= с1, принииается в Р1 блока 40.1, Ь записывается в регистры 31.1 и

29.1, С,> — в Р1 блока 14.3, с выхода сумматора 13.3 результат а +ш ° a2

УЭ

= а принимается в Р1 блока 27.3, блок 42 выполняет деление, и результат п г -С, /а » принимается в регистр 26.2.

В одиннадцатом такте с выхода сум-! ( матора 39.2 результат d +ш Ь »

= dz принимается в Р1 блока 40.2, Ь принимается в регистры 31.2, 29.2, с выхода сумматора 39.1 результат Ь +m z-Ь, = Ь?, принимается в

Р1 блока 40.1, и « йереписывается в

Р1 блока 42. 1, а — в Р2 блока 27. 3, С вЂ” в Р1 блока 14.3, с вьмода сумматора 13.3 результат C„>+m

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

4.2 выполняет .деление, и результат

- m g< = -С /а принииается в регистр гг 52

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

26.3.

В двенадцатом такте с выхода сумматора 39.2 результат Ь +m>z Ь

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

35 с1 переписывается в Р2 блока 40.2, с выхода сумматора 39.1 результат

d «+m

40 ° 1, 1гг npHHeMaeTcsr s P1 бло ка 42.1, с вьмода сумматора. 13.3 ре40 эультат Cz>+m

В тринадцатом такте с выхода сумматора 39.2 значение d<< +m

45 .= d принимается в Р1 блока 40.2, 42.

d. — в Р1 блока 42.1, с выхода суматора 39.1 значение аа2, +шз» ЬЗ21= <1 принимается в Р1 блока 40.1, 2!

Ь „, — в регистр 31 1 длина блока

gp 14.3 уменьшается на единицу и стано.вится равной нулю (т.е. данные проводят с его входа на вьмод без задержки), Сз поступает на вход блока 4.3, 1Ъ он выполняет деление, и результат

55 4э

m4> = -С ь/а принимается в регистр

26.3.

В четырнадцатом такте с выхода .Сумматора 39 ° 2 значение Й +mä Ь »

= и принимается в Р1 блока 40;2, 1 735868 16

Ь вЂ” в регистр 31.2, длина блока м

42.1 становится равной нулю, и с выхода сумматора 39.1 значение d << +

+m4 Ъ Х принимается в Р1 блока

4ь м

40.1 и в регистр 37.1 и появляется на перйом выходе устройства, С - rrocòóпает на вход блока 4.3 и результат

= -С /а принимается в регистр

%9 23 зз

26.3, а m — в регистр 38.1.

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

42.2 становится равной нулю, .с выхода сумматора 39. 2 значение d<<+m<> Ь .

Х принимается в регистр 37.2 и яъ1 появляется на втором выходе устройства сР переписывается в Р2 блока

2г

40.2, с выхода сумматора 39.1 значение dÐ2 + m Ь31 X2 I принимается

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

В последнем шестнадцатом такте с выхода сумматора 39..2 значение d>< +

+т Ь = Х принимается в регистр зг гг

37.2 и появляется на втором выходе устройства. На этом вычисление элементов результируюцей матрицы Х =

= СА В + D заканчивается. Таким образом, полное время реализации алгоритма Т =- n(n-1) /2+п(р+1)+р+2+И-1 тактов, причем элементы результирующей матрицы Х вьдаются на выходы устройства последние p+N-1 тактов, причем с r-ro выхода устройства вьдается г-й столбец матрицы Х (r 1,И) аналогично поступлению исходных элементов матриц В и D на соответствующие входы устройства. Однако в случае решения потока аналогичных задач период работы устройства составляет t = Т— (n+N-1) тактов, .т.е. n(n-1) /2+р(п+

+1)+H-1.тактов. Это означает, что первый элемент а очередной объеди,ненной матрицы можно подавать через

t тактов после подачи элемента а предыдущей объединенной матрицы. В нашем случае Т = 16, t = 12 тактов, следовательно, элементы следующей матрицы можно начинать подавать на вход устройства (вместе с импульсом запуска) с тринадцатого такта.

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

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

10 информационный выход К-го вычислительногО модуля (К = I, л-1J лоднлючены соответственно к синхровходу, входу признака перестановки строк и первому информационному входу .(К+1)15

ro вычислительного модуля, второй информационный вход Р-го вычислительного модуля (Р = 1,n) является Р- м информационным входом устройства, в каждом вычислительном модуле первый и второй разряды синхровхода соединены соответственно с информационными входами второго и третьего триггеров, выходы которых являются соответственно первым и вторым разрядами выхода синхронизации вычислительного модуля, 25 вход и выход признака перестановки строк которого соединены соответственно с первым информационным входом шестого коммутатора и выходом четвертого триггера, информационный вход

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

17 четвертого и пятого коммутаторов и

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

«( выражений вида Х = СА В + D, в устройство введены .N вычислительных модулей О1 — число столбцов матрицы В); каждый из которых содержит умножитель, сумматор, два блока элементов задержки, счетчик, элемент ИЛИ, четыре триггера, четыре регистра и два коммутатора, причем синхровход, вход . признака перестановки строк и первый информационный вход г-го вычислительного модуля (г = ое1, т 11) лоднлюоенн к одноименным выходам (r 1) вычислительного модуля, вторые информационные вход и выход r-го вычислительного модуля являются соответственно (n+

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

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

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

4Q вход которого подключен к управляющему входу первого коммутатора и выходу элемента ИЛИ, первый и второй входы которого подключены соответственно к информационному входу третьего триг45 гера и выходу второго триггера, выход первого триггера подключен к управ-; ляющему входу третьего коммутатора и входу разреыения счета счетчика., выход которого подключен к управляющему

5О входу второго блока элементов задержки, первый выход которого подключен

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

° ° °

° °

° 4 °

° ° °

4 ° °

° °

° °

° ° °

° ° °

° ° °

1735868

Составитель О.Масленников

Редактор И.ймакова Техред К.Дидык Корректор И.Самборская

Заказ 1817 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГЕНТ СССР

113035, Москва, Ж 35 ° Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101