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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4826157/24 (22) 09,04.90 (46) 15.06.92. Бюл. М 22 (71) Киевский политехнический институт им,50-летия Великой Октябрьской социалистической революции (72) P.Âûæèêîâñêè, Ю.С.Каневский, M.Ê,Êëèìåíêo и О,В,Масленников (53) 381,325(088,8) (56) Авторское свидетельство СССР

N 1443003, кл. G 06 F 15/347, 1988.

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

К 1509932, кл. G 06 F 15/347. 1989.

Изобретение относится к вычислительной технике и может быть v ñïoëüçoaàío при построении специализированных. в том числе и систолических устройств. предназначенных для операций над матрицами;

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

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

Наиболее близким к предлагаемому по технической сущности является устройство для решения матричного уравнения вида Ax=

= В, содержащее связанные соответствующим образом и вычислительных блоков первого типа и п(п-1)/2+и г вычислительных. Ы „; 1741153 А1 (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ

ОПЕРАЦИЙ НАД МАТРИЦАМИ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том исле и систолических устройств, предназначенных для выполнения операций над матрицами. Цель изобретения вЂ” расширение функциональных возможностей устройства за счет реализации им алгоритма Фаддеева. Устройство содержит и вычислительных блоков первого типа и и вычислительных блоков второго типа и имеет вход запуска, информационные входы и информационные выходы. 2 з.п. ф-лы. 3 ил. блоков второго типа (где и и г вЂ” размерности матриц).

Недостатком этого устройства являются его ограниченные ф>нкциональные возмо>кности.

Цель изобретения вЂ” расширение функциональных возможностей устройства.

На фиг. 1 изображена структурная схема устройства для случая, когда п = 3. r = 2: на фиг. 2 вЂ” структурная схема вычислительного блока (ВБ) первого типа; на фиг. 3структурная схема BE второго типа.

Устройство для выполнения операций над матрицами содержит (фиг. 1) вычислительные блоки 1.i.i первого типа и 2.ц (i=1, и.

i = i-1, и+г) второго типа, причем вход режима BE 1.1.1 соединен с входом запуска устройства. Первый выход режима ВБ 1.i.j (где

i = j == 1, и-1) соединен с выходом режима ВБ

1,(i+1).(j+1), второй выход режима ВБ 1.а.Ь

1741153

1.5

55 (где а = Ь = 1, n) соединен с входом режима

ВБ 1.а,(Ь+1), выход режима ВБ 1.c(d+k) (где с = d = 1, и; k=1, и+г - с-1) соединен с входом режима ВБ 1,c(d+k+1), информационный вход ВБ 1.1.1 подключен к первому информационному входу устройства, информационный вход ВБ 1.1.j> (где j< = 2, и+и) подключен к j<-му информационному входу устройства, выход результата ВБ 1.i,/+1 (где

i = j, n-1) соединен с информационным входом ВБ 1.(i+1). ()+1), выход результата BE

1.n.(n+k<) (где k1 = 1, r) соединен с k1-м выходом резупьтата устроиства, выход результата ВБ 1 (.(j+kz) (где i = j = 1, и-1; kz = 2, и+г-i) соединен с информационным входом ВБ

1,(i+1).(j+kz). С целью расширения функциональных возможностей устройства за счет реализации им алгоритма Фаддеева выход признака перестановки и выход деления BE

1.а.Ь (где а = Ь = 1, n) соединены с входом признака перестановки и входом деления

ВБ 1.а.(Ь+1), выход признака перестановки и выход деления (с, сье(-то ББ 1.с.(d+k) (rge с = d = 1, n; k = 1, и+г-с-1) соединены с входами признака перестановки и деления

В Б 1,с.(d+k+1).

Вычислительный блок первого типа (фиг. 2) содержит первый 3 и второй 4 элементы задержки, RS-триггер 5, счетчик 6, регистр 7, третий элемент 8 задержки, элемент ИЛИ 9, схему 10 сравнения, первый 11 и второй 12 коммутаторы, четвертый элемент 13 задержки, блок 14 деления, блок 15 элементов задержки. элемент И 16, пятый

17 и шестой 18 элементы задержки, Вход режима вычислительного блока первого типа соединен с входом разрешения счетчика

6, входом установки в н1и триггера 5 и входом элемента 4 задержки, выход которого соединен с первым входом элемента ИЛИ 9.

Выход счетчика 6 соединен с входом установки в и0и триггера 5, входом элемента 3 задержки и входом записи регистра. Выход элемента 8 задержки соединен с первым выходом режима ВБ. выход элемента 3 задержки соединен с входом элемента 8 задержки и вторым выходом режима ВБ.

Выход триггера 5 соединен с первым входом элемента И 16, второй вход которого соединен с выходом элемента ИЛИ 9. Вы- ход элемента И 16 соединен с входом элемента 17 задержки и входами разрешения первого и второго коммутаторов, Выход элемента 17 задержки соединен с выходом признака перестановки ВБ, информационный вход BE подключен к первым информационным входам схемы 10 сравнения, первого 11 и второго 12 коммутаторов, выход схемы 10 сравнения подключен к второму входу элемента ИЛИ 9, Информационный выход коммутатора 11 соединен с входом блока 15 элементов задержки, выход которого соединен с первым информационным входом блока 14 деления, информационный выход которого соединен с входом шестого элемента 18 задержки, выход которого соединен с выходом деления процессорного блока. Второй информационный вход блока 14 деления соединен с информационным выходом регистра 7, информационный вход которого соединен с информационным выходом коммутатора 12 и входом элемента 13 задержки, выход которого соединен с вторыми информационными входами схемы 10 сравнения, первого

11 и второго 12 коммутаторов, информационный вход счетчика 6 соединен с входом константы устройства, Вычислительныи блок второго типа (фиг. 3) содержит первый элемент 19 задержки, первый 20 и второй 21 коммутаторы. второй элемент 22 задержки, регистр 23, третий элемент 24 задержки, блок 25 элементов задержки, сумматор 26. блок 27 умножения, четвертый 28 и пятый 29 элементы задержки. Вход режима ВБ соединен с входом элемента 24 задержки и входом записи регистра 23, информационный выход которого соединен с входом первого сомножителя блока 27 умножения, вход второго сомножителя которого соединен с входом элемента 28 задержки и входом деления В Б.

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

19 задержки и входами разрешения первого

20 и второго 21 коммутаторов. Выход элемента 19 задержки подключен к выходу признака перестановки ВБ, информационный вход которого подключен к первым информационным входам первого 20 и второго 21 коммутаторов. Информационный выход коммутатора 20 соединен с входом блока 25 элементов задержки, выход которого соединен с входом первого слагаемого сумматора

26. информационный выход которого соединен с элементом 29 задер>кки, выход которого соединен с выходом результата ВБ.

Выход блока 27 умно>кения соединен с входом второго слагаемого сумматора 26, информационный выход коммутатора 21 соединен с информационным входом регистра 23 и входом элемента 22 задержки, выход которого соединен с вторыми информационными входами коммутаторов 20 и 21.

Выход элемента 24 задержки подключен к выходу режима ВБ.

Устройство для выполнения операций над матрицами предназначено для вычисления с помощью алгоритма Фаддеева выра1741153 жения вида X = СА B+D, где в общем случае

-1

A(n x n) = (a ij }; В (и х г) = (Ь ц<); C(p x n ) = (cej) и

D(pxr) = (dei<) вЂ” матрицы, представленные в виде объединенной матрицы: причем суть алгоритма сводится к тому, что после обнуления в объединенной матрице нижнего левого квадранта (т.е. элементов матрицы -С), в правом нижнем квадранте (на месте матрицы О) получаем искомый результат X(pxr), Фактически это выражение позволяет решать дополнительно еще несколько задач.

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

X=A 8 при С=1,D=O.

2. Обращение матрицы

X=À" при С=В=1, D=O.

3. Умножение матриц (или матрицы на вектор, в зависимости от размерности В)

Х= СВ при А= 1, 0 =О.

4. Умножение со сложением матриц

Х= СВ+ D при А =1.

5. Задача адаптивной фильтрации, которая использует выражение

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

Обнуление нижнего левого квадранта объединенной матрицы можно осуществить, применяя к ней QR-разложение или, как реализовано в предлагаемом устройстве, исключение Гаусса до приведения матрицы А к верхнему треугольному виду. Тогда автоматически на месте матрицы -С получается нулевая матрица. При этом с целью обеспечения численной устойчивости вычислений преобразование матрицы А выполняется по алгоритму исключения Гаусса с частичным выбором ведущего элеме. та по столбцу, Это означает, что на i-м шаге (i = 1, и-1) алгоритма Гаусса исключению элементов ajii 0 = i+I и), принадлежащих исходной матрице А = А (при i = 1) или уже частично 1. преобразованной матрице А (при i > 1); предшествует последовательное сравнение их с элементом aii и, если очередной элемент I aji I > I a; I, осуществляется перестановка j-й и i-й строк, т.е. i-я строка ставится

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

=-aji /aii . Однако поскольку в объединенной матрице под матрицей А находится матрица

-С, которую необходимо привести к нулевой матрице, никаких перестановок строк мат10

55 риц С и D со строками матриц А и В производить нельзя, Вследствие этого устройство осуществляет выбор ведущего элемента среди элементов i-го столбца матрицы А (на

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

А и С, т.е. среди элементов i-.ãî столбца всей объединенной матрицы (i = 1, и-1). Все признаки перестановки строк запоминаются и передаются между BE в качестве элементов нижней треугольной матрицы перестановок

V = (Vj ), За (n-1)-й шаг алгоритма Гаусса обнуляются (n-1) столбцов объединенной матрицы. Однако для получения правильного результата необходимо обнулить также и-й столбец матрицы -С. Поэтому в данном случае алгоритм Гаусса имееттакже и-й шаг. на котором отсутствует процесс выбора ведущего элемента (элемент апг," соазу становится ведущим. так как его не с чем сравнить), а процесс исключения производится аналогично предыдущим шагам алгоритма.

Поступление исходных данных организовано следующим образом, На i-й H

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

i-й информационный вход устройства в i-м такте его работы, а элемент Ь1;< вЂ” в (n+k)-м такте работы устройства.

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

Для простоты описания и без потери общности положим n = 3, р = r = 2. Условимся. что прием информации во все счетчики. триггеры и элементы 3, 4, 8 и 24 задержки всех BE происходит по переднему фронту синхроимпульса, т.е. вначале такта, а во все регистры, блоки элементов задержки и остальные элементы задержки вЂ” по заднему фронту синхроимпульса;

В первом такте на вход запуска устройства поступает единичный импульс, кото1741153 рый записывается в элемент 4.1.1 задержки, а также поступает на вход разрешения счетчика 6.1.1 и на вход установки триггера

5.1.1, который устанавливается в единицу, которая поступает на первый вход элемента

И 16,1.1, с выхода которого единица поступает на управляющие входы коммутаторов

12,1,1 и 11,1,1 и записывается в элемент

17,1,1 задержки, Кроме того, в счетчик 6.1,1 записывается значение (и-1) = 2 в двоичном коде, на его выходе нулевого состояния находится нуль, На информационный вход ВБ

1.1.1.поступает à11 = à11 и, пройдя через

1 первый вход второго коммутатора 12,1,1, записывается в элемент 13.1.1 задержки.

Во втором такте на первый вход коммутатора 11.1.1 поступает элемент а11 с выхо1 да элемента 13.1.1 задержки, а на первые входы схемы 10.1.1 сравнения и коммутатор

12.1.1 поступает элемент 821 = 821 . В схеме

10.1.1 сравнения происходит сравнение и больший по абсолютному значению элемент записывается в элемент 13.1,1 задержки, а меньший вЂ” в первый регистр блока

15.1.1 элементов задержки, Допустим, что

1а» I >laz1 I. тогда элемент а» снова за 1 1 писывается в элемент 13,1,1 задержки, элемент 821 вЂ” в первый регистр блока 15,1,1

1 элементов задержки. нуль с выхода схемы

10,1.1 сравнения (признак отсутствия перестановки строк) (Vz1 = О) записывается в элемент 17,1,1 задержки, а в элемент 19.1.2 задержки записывается единица. В этом же такте счетчик 6.1.1 уменьшает свое значение на единицу, на его выходе нулевого состояния остается нуль, который там находится до тех пор, пока содержимое счетчика

6,1.1 не станет равным нулю, Кроме того, элемент 812 = 812 поступает на информаци1 онный вход ВБ 1.1,2 и записывается в элемент 22,1.2 задержки (на управляющих входах коммутаторов 20,1.2 и 21.1.2 вЂ” единица), В третьем такте счетчик 6,1.1 уменьшает свое значение до нуля, На информационный вход ВБ 1,1,1 поступает элемент аз1 =

=.аз1 . В схеме 10,1,1 сравнения аз1 сравни1 1 ваЕтСя С а» . ПуСть la» I > )8З1 I (ЧЗ1=0).

Тогда элемент а» записывается в регистр

7,1,1 (на выходе нулевого состояния счетчика 6.1.1 вЂ” единица), а элемент 831 вЂ” в первый

1 регистр блока 15,1,1 элементов задержки, а21 переписывается во второй регистр блока 15.1.1 элементов задержки. В ВБ 1.1.2 значение а12 опять переписывается в эле1 мент 22.1.2 задержки, а новое значение a22=

= a22 вЂ” в первый регистр блока 25.1.1 элементов задержки. Кроме того, в ВБ 1,1,3 через его информационный вход поступает элемент а1з = а1з и записывается в элемент

22.1.3 задержки, единица из элемента 19,1.2 задержки переписывается в 19,1,3, а в элемент 19.1.2 задержки записывается V21 = О.

В четвертом такте в элемент 3.1.1 задержки записывается единица, на выходе счетчика 6.1.1 снова появляетея нуль, триггер

5.1.1 устанавливается в нулевое состояние.

На первый вход делителя 14,1.1 с выхода второго регистра блока 15,1.1 элементов за10 держки поступает а21 а с выхода регистра

7,1,1 вЂ” 8», и результат деления (-821 /а» ):

1 1 1, = lz1 записывается в элемент 18.1.1 задержки. Кроме того, на информационный вход

В Б 1.1.1 поступает элемент -c» = -с11, кото1

15 рый записывается в первый регистр блока

15,1,1 элементов задержки (на выходе элемента 16,1,1 вЂ” нуль). В ВБ 1.1,2 на управляющий вход регистра 23.1.2 поступает единица, и в регистр 23.1.2 записывается

20 а12 с выхода элемента 22.1.2 задержки. На

1 второй вход ВБ 1.1.2 поступает аз2 = аз2 и 1 записывается в первый регистр блока 25.1.2 элементов задержки, а в первый регистр блока 25,1,3 элементов задержки записыва25 ется а2з, поступающее с второго входа ВБ

1.1,3. В элемент 19,1,3 задержки записывается нуль. В элемент 22.1.4 задержки записывается элемент матрицы В вЂ” Ь11 = b11 . В

1 элемент 19,1.4 задержки записывается еди30 ница, В пятом такте 8.1.1 задержки записывается единица, в элемент 3.1.1 вЂ” нуль. На входы делителя 14,1,1 в ВБ 1.1.1 поступают элементы аз1 и а» и результат деления

1 1

35 (-аз1 /а» ) = )з1 записывается в элемент

1 1

18.1.1 задержки, lz1 записывается в элемент

28.1.2 задержки ВБ 1.1.2, а также подается на вход умножителя 27.1.2. Кроме того, на информационный вход ВБ 1.1.1 подается

40 элемент -c21 = -cz1 . который записывается в

1 первый регистр, элемента 13.1.1 задержки, а

-c11 вЂ” во второй регистр блока 15.1.1 эле1 ментов задержки. В ВБ 1.1.2 с выхода регистра 23.1.2 на второй. вход умножителя

45 27.1,2 поступает а12 . В элемент 24.1.2 за1 держки записывается единица. Результат умножения 121 а12 поступает на вход сумма1 тора 26.1.2. где складывается с а22", и сумма

l21 812 + 822 = 822 записывается в элемент г

50 29,1.2 задержки. Кроме того, с второго входа

ВБ 1.1.2 в первый регистр блока 25,1.2 элементов задержки записывается -c12, 832 1 1 переписывается во второй регистр блока

25.1.2 элементов задержки. В ВБ 1,1.3 с

55 выхода элемента 22.1.3 задержки в регистр

23.1.3 записывается 81з, а в первый регистр

1 блока элементов 22,1.3 задержки записывается азз с информационного входа ВБ 1.1.3.

1 .В ВБ 1,1.4 в элемент 19,1.4 задержки записывается нуль, с выхода элемента 22,1.4 за1741153 .

10 держки, пройдя через коммутатор 21.1.4, в него же переписывается. Ь», а в первый

1 регистр блока 25.1.4 элементов задержки записывается значение b21 = b21 поступив1 шее с второго входа BE 1.1.4, B ВБ 1.1.5 в элемент 19.1.5 задержки записывается единица, в элемент 22.1.5 задержки записывается b12= b12 .

В шестом такте управляющие сигналы поступают аналогично первому такту, а именно в элементы 4.2.2 и 17.2.2 задержки записываются единицы, S-триггер 5.2.2 устанавливается в единицу, значение и-2 = 1 записывается в счетчик 6.2.2. На входы делителя 14.1.1 в ВБ 1.1.1 поступают -c» и а», результат деления -c» /а» = 141 запи1 1 1 сывается в элемент 18,1,1 задержки, с выхода которого 131 записывается в элемент

28.1.2 задержки ВБ 1,1,2 и поступает на вход умножителя 27.1,2, На второй вход ВБ

1,1.1 поступает элемент новой матрицы АвЂ” 1 а11 . В ВБ 1.1.2 на входы умножителя 27.1.2 поступают a

1. ад 131 поступает на вход сумматора 26.1,2.

1 1 1

2 куда поступает а32, а сумма1з1 а1г + азг

=азг поступает в элемент 29,1,2 задержки, с выхода которого элемент агг через комму2 татар 21.2.2 поступает в элемент 22.2,2 задержки ВБ 1.2.2. Кроме того, на второй вход

ВБ 1.1,2 поступает элемент (-с22 = -C22 ) и, пройдя через первый коммутатор 20.1,2, записывается в блок 25.1.2 элементов задержки. В ВБ 1.1.3 на входы умножителя 27.1.3 поступают 121 и a<3 . Результат умножения

„1

1. а<3 .12) поступает на вход сумматора 26,1,3, куда поступает элемент а23, а сумма 121 а13 i

1 1, + агз = az3 поступает в элемент 29,1,3 заг держки, Кроме того. на информационный вход ВБ 1.1.3 поступает (-с1з =-с13 ) и, пройдя через первый коммутатор 20.1.3, записы- вается в блок 25.1.3 элементов задержки. В

ВБ 1.1.4 с выхода третьего элемента 22.1,4 задержки через второй коммутатор 21.1.4 в регистр 23.1,4 записывается b» . а через

1 первый коммутатор 20.1.4 с второго входа

ВБ 1,1.4 в-блок 25.1.4 элементов задержки записывается b3< = b3> . В ВБ 1.1.5 в зле) мент 19, 1,5 задержки записывается нуль, с выхода третьего элемента 22.1,5 задержки через второй коммутатор 21.1,5 в него же записывается Ь12, а в блок 25.1.5 элементов

1 задержки записывается b22 = Ь22 с второго 1 входа В Б 1.1.5.

В седьмом такте на входы делителя

14,1,1 в ВБ 1.1.1 поступают (-cz> )и а», и результат деления -сг| /а» = 14> записыва1 1 ется в шестой элемент 18.1,1 задержки, с выхода которого 14 записывается в четвертый элемент 28.1.2 задержки ВБ 1.1.2 и поступает на вход умножителя 27.1.2. В ВБ

1.1.2 на входы умножителя 27.1,2 поступают

141 и а1г . Результат умножения 141 айаг по1 1 ступает на вход сумматора 26.1.2, кура по5 ступает элемент -c12, и сумма 141 э12 вЂ” c12=

1 1 г

= си поступает в элемент 29.1,2 задержки, с выхода которого элемент азг поступает в г

ВБ 1,1.2. На выходе нулевого состояния счетчика 6.2,2 вЂ” единица. В схеме 10.2.2

10 сравнения происходит сравнение, и больший элемент записывается в третий элемент 13.2.2 задержки, а меньший вЂ” в блок

15.2.2 элементов зауержки, допустим, что при сравнении I а32 > I д22 I, тогда эле15 мент a3z записывается а третий элемент

13.2.2 задержки, а элемент a22 вЂ” в блок г

15.2.2 элементов задержки. В умножителе

27.1.3 ВБ 1.1.3 происходит умножение . 1

1з1.а|з и результат поступает нэ вход сум20 матора 26,1.3, куда поступает элемент азз . а сумма 1з1 а1з + азз = азз поступает в г элемент 29.1.3 задержки,с выхода которого

az3 поступает в элемент 22.2.3 задержки В6

1,2.3, Кроме того, на второй вход ВБ 1.1.3

25 поступает -сгз = -сгз и через первый комму1 татор 20.1.3 записывается в блок 25,1.3 элементов задержки, В BE 1.1.4 на входы умножителя 27.1.4 поступают 12 и Ь» и результат 121 Ь11 поступает на вход сумма1

30 тора 26.1.4. куда поступает элемент Ьг и сумма 121 b» + Ь21 вЂ”. b21 .поступает в элег мент 29.1.4 задержки, Кроме того, на второй вход ВБ 1.1.4 поступает элемент матрицы 0 вЂ” d» = d» и через первый коммутатор 20.1,4

1 записывается в блок 25.1.4 элементов задержки. В ВБ 1.1.5 с выхода третьего элемента 22,1,5 задержки bn перезаписывается в регистр 23.1.5, а с информационного входа

ВБ 1,1.5 b32 = Ьзг проходит через первый

40 коммутатор 20.1.5, записывается в блок

25.1.5 элементов задержки, В восьмом такте в ВБ 1.1,2 на входы умножителя 27.1.2 поступает l » и a>z и результат умножения la .а12 поступает на

45 второй вход сумматора 26.1.2, на первый вход которого поступает элемент -сгг и ре1 г зультат t я а1г вЂ” сгг = c22 записывается в элемент 29.1.2 задержки, с выхода которого

2 сд поступает в ВБ 1.2,2 и записывается в блок 15.2.2 элементов задержки, В элемент

3.2.2 задержки записывается единица. На входы делителя 14.2.2 поступает-агг /азг =

==1зг и результат записывается в элемент

18.2.2 задержки, В ВБ 1.1.3 на входы умножителя 27.1.3 поступает 14> и а>3 и результат

l4 а1з поступает на вход сумматора 26.1.3, куда поступает -с1" и сумма 14) a)3 - с13

1 1 1 вЂ”:с1з поступает в элемент 29,1.3 задержки, с выхода которого азз записывается в ВБ

1741153

1.2.3 и через коммутатор 21,2.3 записывается в элемент 22.2.3 задержки. В ВБ 1.1.4 на входы умножителя 27.1.4 поступает 131 и Ь11 и результат умножения 13) b11 поступает на вход сумматора 26.1.4, куда поступает Ь31, и сумма 131 b11 + Ь31 = Ь31 записывается

1 1 2 в элемент 29.1.4 задержки, с выхода которого bzz поступает в BE 1.2,4 и через коммуг татор 21.2.4 записывается в элемент 22.2.4 задержки. Кроме того, на информационный вход В Б 1.1.4 поступает элемент dz< = бг! и

1 через коммутатор 21.1,4 записывается в элемент 22.1,4 задержки, В ВБ 1.1.5 на входы умножителя 27.1.5 поступают 121 и b12 и

1 результат умножения !21 Ь12 поступает на

1 вход сумматора 26.1.5, куда поступает элемент b22 и сумма !21 Ь12 + b22 = Ь22 запи1 сывается в элемент 29.1.5 задержки. Кроме того, на информационный вход ВБ 1,1.5 поступает элемент diaz = d12 и через второй

1 коммутатор 21.1.5 записывается в элемент

22.1.5 задержки, В девятом такте с выхода элемента

29.1.2 задержки ВБ 1.1,2 элемент с22 поступает в ВБ 1,2,2 и записывается в блок 15,2,2 элементов задержки. В элемент 8.2.2 задержки записывается единица. В делителе

14.2.2 происходит деление с12 /а32 = I42 и

2 2 результат записывается в элемент 18.2.2 задержки, с выхода которого 132 поступает в

ВБ 1.2,3, где записывается в элемент задержки 28.2.3 и поступает на вход умножения

27.2.3, где происходит умножение 13г.а33 . г результат умножения поступает на второй вход сумматора 26,2,3, на первый вход которого поступает агз, и сумма 132 а33 + а23 = г

=-а33 записывается в элемент 29.2,3 задерж3 ки. В ВБ 1,1.4 на входы умножителя 27.1.4 поступают 141 и Ь11 и результат умножения

И! Ь поступаетвсумматор26.1.4,сумма

141 b1I +б11 =б11 записывается в элемент .411 1 2

29,1.4 задержки, с выхода которого элемент

Ь31 поступает в ВБ 1.2,4. В ВБ 1.1.5 на

2 входы умножителя 27,1,5 поступает 131 и

b12, где происходит умножение. и результат !31 Ь12 поступает в сумматор 26.1.5 и сумма !31 Ь12 + Ьзг = Ь32 поступает в эле1 1 мент 29.1.5 задержки, с выхода которого сгг поступает в ВБ 1,2.5, Кроме того, на

2 второй вход ВБ 1,1,5 поступает б22 = dã2 и 1 записывается в элемент 22.1.5 задержки.

В десятом такте с выхода элемента

29.1.3 задержки в В Б 1.2.3 поступает сгз . В элементы 4.3.3 и 17.3.3 задержки записывается единица и на выходе нулевого состояния счетчика 6.3.3 появляется единица. На входы умножителя 27.1.4 ВБ 1.1.4 поступают элементы !51 и Ь1! и результат умножения

1 поступает в сумматор 26,1.4, сумма !51 Ь +

;бг! = б21 поступает в элемент 29.1.4 задер1 жки, с выхода которого элемент б11 постуг пает в ВБ 1.2.4. B ВБ 1.1,5 на входы умножителя 27.1,5 поступают элементы !51 b>z", результат поступает в сумматор 26.1,5, сумма

5 !51 Ь12+ бгг = б22 поступает в элемент 29,1,5 г задержки, с выхода которого Ьзг поступает в г

BE 1,2.5 и через коммутатор 21,2.5 записывается в элемент 22,2.5 задержки. В ВБ 1.2,2 на входы делителя 14.2.2 поступают сгг и a32 и г г

10 результат деления с22 /а32 = 152 записывает г ся в элемент 18.2.2 задержки, с выхода которого 142 поступает на входы умножителя 27.2.3 и элемента 28,2,3 задержки. Результат умножения 142 азз с выхода умножителя 27.2.3 г

15 поступает в сумматор 26.2.3, сумма !42 а33 +

-1-с!3 = с1з записывается в элемент 29.2.3 за3 держки, с выхода которого элемент а33 поступает в ВБ 1.3,3 и через коммутатор 12.3.3 записывается в элемент 13.3.3 задержки. В

20 ВБ 1.2,4 на входы умножителя 27.2.4 поступают элементы !Зг и Ь3!, результат умноже2 ния поступает в сумматор 26.2.4, с выхода которого !32 b31 - b21 = b31 записывается г г 3 в элемент 29.2,4 задержки.

В одиннадцатом такте с выхода элемента 19,1,4 задержки элемент бг! поступает в

ВБ 1.2.4 и через коммутатор 21,2,4 записывается в элемент 22.24 задержки. В ВБ 1.1.5 на входы умножителя 27,1.5 поступают l5< и

Ьаг, результат умножения 151 b12ã поступа1 ет в сумматор 26.1.5, и результат суммирования !5! Ь12 + dzz = dzz поступает в

1 1 2 элемент 29.1.5 задержки, с выхода которого элемент б12 поступает в ВБ 1.2,5, где через коммутатор 21,2.5 записывается в элемент

22.2.5 задержки. С выхода ВБ 1.2.2 элемент ! 52 поступает на входы умножителя 27.2,3 и элемента 28.2.3 задержки. Результат умножения 152 а33. ВБ 1.2,3 поступает в сумматор 26,2.3 и сумма l52 а33 + с23 = сгз г поступает в элемент 29.2,3 задержки, с выхода которого с!3 поступает в ВБ 1.3.3 и, пройдя через блок 15.3.3 элементов задержки, поступает на вход делителя 14,3.3, Результат деления с133/азз = 143 записывается в элемент 18,3.3 задержки, В ВБ 1.2.4 на входы умножителя 27.2.4 поступают элементы 142 и b31, результат умножения

2 !

42 Ь31 поступает в сумматор 26.2.4 и сумма г

142 b31 + б112 = d11 записывается в элемент

29.2.4 задержки, с выхода которого элемент

b31 поступает в ВБ 1,3,4. В ВБ 1.2,5 с выхо3 да умножителя 27,2,5 13z.b32 поступает в г сумматор 26.2.5, результат суммирования

132 b32 + b22 = Ь32 записывается в элемент

2 2 3

29,2.5 задержки.

В два .адцатом такте с выхода элемента

29,1,5 задержки элемент бгг поступает в ВБ

1,2,5. " выхода элемента 29,2,3 задержки

1741153

14 элемент с23 поступает в В Б 1.3.3, где, и рой3 дя блок 15.3.3 элементов задержки, поступает на вход делителя 14.3.3 и результат деления !53 записывается в элемент 18,3,3 задержки, с выхода которого элемент !43 поступает в элемент 28.3.4 задержки ВБ 1.3.4 и на вход умножителя 27.3,4, с выхода которого !43 Ь31 поступает в сумматор 26,3,4, с

3 выхода которого сумма !4з b31 + d11 = d11=

= х11 записывается в элемент 29,3,4 задержки. B ВБ 1.2.4 на входы умножителя 27,2,4 поступают I52 и b31, результат умножения г г

l52 b31. поступает в сумматор 26,2,4 и сумма !

52 Ь312+ 021 = 021 записывается в элемент

29.2.4 задержки, с выхода которого элемент

d11 поступает в ВБ 1.3.4. На входы умножи3 теля 27.2.5 ВБ1,2.5 поступают элементы !42 и b32 результат умножения l42 Ь32 посту2 г пает в сумматор 26,2,5, и сумма !42 Ь32 +

j-d12 = d12 поступает в элемент 29,2.5 задер2 3 жки,с выхода которого d12 поступает в ВБ

1.3.5.

В тринадцатом такте из ВБ 1.2,4 элемент cl21 поступает в ВБ 1.3,4, В В Б 1.2.5 на

3 входы умножителя 27.2.5 поступают элементы !32 и b32, результат умножения г

l52 Ь32 поступает в сумматор 26.2.5 и сумма

2 !

52 Ь32 + d22 = d22 поступает в элемент

2 2

29.2.5 задержки, с выхода которого d123 поступает в ВБ 1.3.5, В ВБ 1.3.4 на входы умножителя 27.3.4 поступают !53 и Ь31, результат умножения !53.b31 поступает в сум3 матор 26.3.4 и сумма !53 Ь31 + d21 = с!21

=х21 записывается в элемент 29.3.4 задержки, с выхода которого х21 поступает на первый выход устройства. В,ВБ 1.3.5 на входы умножителя 27 3.5 поступают l43 и b32 . результат умножения !43 Ь32 поступает в

3 сумматор 26.3.5, сумма которого !43 Ь32 +, 3 4

%d12 = cI12 = х12 записывается в элемент

29,3,5 задержки, и х12 поступает на второй выход устройства.

В четырнадцатом такте с выхода ВБ

1.2.5 элемент с!22 поступает в ВБ 1.3.5. С

3 выхода ВБ 1.3.4 на первый выход устройства выдается х21. В ВБ 1.3.5 на входы умножителя 27,3.5 поступают элементы !53 и Ь32, результат умножения 3 Ь32 поступает в

3 сумматор 26.3.5 и сумма !53. Ь32 +d22 = d22== х22 записываЕтся в элемент 29.3,5 задержки, с выхода которого на второй выход устройства выдается х22.

На этом вычисление элементов результирующей матрицы X = СА B+D заканчива-, -1 ется. Таким образом. полное время реализации алгоритма Т = n(n-1)/2+2(n-1) +

=.п + р+ r тактов, причем элементы результирующей матрицы X выдаются на входы устройства последние г+ р + 1 тактов (причем

45 с k-го выхода устройства выдается k-й столбец матрицы Х (k = 1, г) аналогично поступлению исходных элементов матриц В и D на соответствующие входы устройства. Однако в случае решения потока аналогичных задач . период работы устройства составляет т = n +

1-р тактов. Это означает, что первый элемент а11 очередной объединенной матрицы можно подавать через t тактов после подачи элемента а11 предыдущей объединенной матрицы. В нашем случае Т = 14, = 5 тактов. следовательно, элементы следующей матрицы можно начинать подавать на вход устройства (вместе с импульсом запуска) с шестого такта, Таким образом, предлагаемое устройство при примерно равных аппаратурных затратах и временных характеристиках с известным устройством позволяет существенно расширить функциональные возможности последнего. Кроме того, реализация частичного выбора ведущего элемента позволяет в ряде задач значительно повысить устойчивость. а следовательно, и точность вычислительного процесса по сравнению с известным устройством.

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

1. Устройство для выполнения операций над матрицами, содержащее п вычислительных блоков первого типа и (п (n-1)/(2+n г)) вычислительных блоков второго типа (где и и r вЂ” размерности матриц), причем вход пуска первого вычислительного блока первого типа соединен с входом запуска устройства. первый выход режима (ц)-го вычислительного блока первого типа (где i = j = 1. п-1) соединен с входом режима (!+1, j+1)-го вычислительного блока первого типа, второй выход режима (а, Ь)-го вычислительного блока первого типа (где а = Ь = 1, п) соединен с входом режима (а, Ь+1)-го вычислительного блока второго типа, выход режима (с, d+k)-го вычислительного блока второго типа (где с== d = 1, n; k= 1, n+ r с-1) соединен с входом режима (с, d+k+1)-го вычислительного блока второго типа, информационный вход первого вычислительного блока. первого типа подключен к первому информационному входу устройства. информационный вход (1, j1)-го вычислительного блока второго типа (где J1== 2, n+r) подключен к j1-му информационному входу устройства, выход результата вычислительного блока второго типа (где i = j =

=1, и-1) соединен с информационным входом (i+1, j+1)-го вычислительного блока первого типа. выход результата (и, n+k1)-го вычислительного блока второго типа (где k1 = Г соединен с k1-м выходом результата устройства, выход результата (i, j+k2)-го вычислительного блока второго типа(где!= );

55 и-1; k2 = 2, и+г-i) соединен с информационным входом (i+1, )+12)-ro вычислительного блока второго типа, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства за счет реализации им алгоритма Фаддеева, выход признака перестановки и выход деления (а, Ь)-ro вычислительного блока первого типа (где а = b = 1, n) соединены с входом признака перестановки и входом деления (a, b+1)ro вычислительного блока второго типа, выход признака перестановки и выходделения (е, d+k)-го вычислительного блока втолого типа (где с = d = 1, п; k = 1, п+г-с-1) соединены с входами признака перестановки и деления (с, d+k+1)-ro вычислительного блока второго типа.

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

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

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

1741153

К(Л

1741153

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

Техред М.Моргентал Корректор О.Кравцова

Редактор М,Петрова

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

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

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

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

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

Патент 1741153