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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4847777/24 (22) 09.07,90 (46) 30.12.92. ьюл. М 48 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) Р.Выжиковски, Ю.С.Каневский, M.Ê.Êëèìåíêî и О.В.Масленников (56) 1. Авторское свидетельство СССР

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

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

М 1226484, кл. 6 06 F 15/347, 1986. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

МАТРИЦАМИ

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

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

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

„,5U„„1784997 А1 (57) Устройство для операций над матрицами относится к автоматике и вычислительной технике и может быть использовано при построении специализированных, в том числе и систолическйх устройств. Целью изобретения является расширение функциональных возможностей за счет частичного выбора ведущего элемента при вычислении выражений вида СА В+ D (с помощью ал-1 горитма Фаддеева), где A(n Х n), B(n,К г), С(р $ n). D(p 5 r) вЂ” матрицы. Устройство для операций над матрицами содержит и Нг операционных блоков и блок синхронизации, а ил, Наиболее близким к предлагаемому изобретению по технической сущности является устройство для умножения матрицы на вектор, содержащее и последовательно соединенных процессорных элементов и блок управления, соединенный с первым 4 процессорным элементом (2). Оно выбрано CO в качестве прототипа. Фь

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

СА В + D, где A(n g n), Bfn gr), С(р n) и

D(p Х г) вЂ” матрицы (в част н ом случае, и ри г = 1, р = 1 матрицы С, В и матрица D могут быть векторами размерностью и и скаляром соответственно).

На фиг. 1 представлена структурная схема устройства для операций над матрицами; на фиг. 2 вЂ” структурная схема первого операционного блока (ОБ); на фиг. 3 вЂ” структур1784997 .наясхема1-гооперационногоблока(1=2,й+г); подключен к первому информационному на фиг. 4 вЂ” структурная схема возможного входу коммутатора 8, выход которого подварианта построения блока синхрониза- ключен к первым информационным входам ции. второго коммутатора 11, третьего коммутаустройство для операций над матрица- 5 тора 12 и узла сравнения 10, выход которого ми содержит ОБ 1.1-1.(n+ r) и блок синхро- подключен к первому входу элемента И 13, низации 2, причем вход запуска устройства выход которого подключен к первому входу подключен ко входу запуска блока синхро- элемента ИЛИ 5, выход которого > подклюнизации2,первыйивторойвйходыкоторого чен к управляющим входам коммутаторов подключены соответственно к первому и вто- 10 11 и 12 и ко входу третьего элемента задерp6t4y управляющим входам первого ОБ, с жки14,выходкотброгоподключенковтороперввго no (n+ r)-й входы элементов обрабо- му выходу ОБ 1 1, выход коммутатора 11 тываемыуматриц устройства подключены со- подключен к информационному входу узла ответственно к первым йнформационным задержки6, первыйвыходкоторогоподклювходам ОБ 1.1-1.(n + i), первый, второй и 15 чен ко входу четвертого элемента задержки третий выходы ОБ 1.а (где а - 1, ..., n+ r - 1) 17, выход которого. пбдключен iкки 7, счетчика 9, приэтом каждый ОБ1l(i=2, n+r) первый коммутатор 8, счетчик 9; узел срав- содержит первый элемент задержки 20; нения 10, второй 11 и третий 12 коммутато- первый 21 и второй 22 коммутаторы, второй ры, элемейт И 13, третий элемент задержки 45 элемент задержки 23, первый. узел задерж14, второй регистр 15, делитель 16, четвер- ки 24, второй 25 и первый 26 регистры, третый элемент задержки 17, первый фетистр тий элемент задержки 27, счетчик 28, 18,третий регистр19, причем первыйуправ- сумматор 29, умножитель 30, четвертый реляющий вход ОБ 1.1 подключен. ко входу гистр 31, третий коммутатор 32, четвертый первого элемента задержки 3, выход кото- 50 элемент задержки 33, второй узел задержки рого .. подключен к информационному входу 34, третий регистр 35, причем в каждом ОБ триггера 4, к первому входу элемента ИЛИ . 1.l первый управляЮщий вход ОБ подклю5, к первому управляющему входу узла за- чен ко входу первого элемента задержки 20, держки 6 и к первому выходу ОБ 1,1, второй выход которого подключен к первомууправуправляющий вход которого подключен ко 55 зияющему входу первого узла задержки 24 и входу второго элемента задержки 7, выход к первому: выходу ОБ 1,1, второй управляюкоторого подключен к управляющему входу щий вход которого подключен к управляюпервого коммутатора 8, ко входу режима щим входам первого 21 и второго 22 счетчика 9 и к четвертому выходу ОБ 1.1, коммутатора и ко входу второго элемента 23 первый информационный вход которого задержки, выход которого подключен ко

1784997

2) обращение матрицы

40 регистров 25, 31 и 35

50 второму выходу ОБ 1Л, первый информационный вход которого подключен к первому информационному входу третьего коммутатора 32, выход которого подключен к первым информационным входам коммутаторов 21 и 22, выход коммутатора 21 подключен к информационному входу узла задержки 24, первый и второй выходы которого подключены соответственно к первому информационному входу сумматора 29 и ко входу третьего элемента задержки 27, выход которого подключен ко входу записи/считывания первого регистра 26 и ко входу декремента счетчика 28, информационный выход которого подключен ко второму управляющему входу узла задержки 24, выход коммутатора 22 подключен к информационному входу регистра 26 и к информационному входу второго регистра 25, выход которого подключен ко вторым информационным входам коммутаторов 21 и 22, выход регистра 26 подключен к первому информационному входу умножителя 30, выход которого подключен ко второму информационному входу сумматора 29, информационный выход которого подключен к информационным входам третьего регистра 35 и второго узла задержки 34, второй информационный вход

ОБ 1.i подключен ко второму информационному входу умножителя 30 и к информационному входу четвертого регистра 31, выход которого подключен к третьему выходу ОБ

1,i, третий, четвертый и пятый информационные входы которого подключены соответственно. ко второму информационному входу коммутатора 32, к информационному входу счетчика 28 и к управляющему входу узла задержки 34, выход которого подключен к шестому выходу ОБ 1.!„четвертый выход и третий управляющий вход которого подключены соответственно к выходу регистра 35 и ко входу четвертого элемента задержки 33, выход которого подключен к управляющему входу коммутатора 32, ко входу режима счетчика 28 и к пятому выходу

ОБ 1.i, вход синхронизации которого подключен ко входам синхронизации узлов задержки, сумматора, умножителя, счетчика и регистра 26 и ко входам записи/считывания

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

A(nХп)={ац), В=(n )(rj={Ьи,), С(р gnj-{сц), D(p Х n) - {б1к) вЂ” матрицы, представленные в виде объединенной матрицы: причем суть алгоритма сводится к тому, что после обнуления в объединенной матрице нижнего левого квадранта (т.е. элементов матрицы вЂ” С), в правом нижнем квадранте (на месте матрицы Р) получаем искомый результат Х(р 3. r) (см. J,G, Nash, S.Hansen, modified algorithm for c0ncurrent execution

of linear algebra operations // lEEE Trans.

Comp., v. 37, N. 2, Febr. 1988, р. 130)..

Фактически это выражение К - СА B + D позволяет решать дополнительно еще несколько задач, а именно;

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

X=A B при C= t, D-0;

Х= А при С = В = j, Р = 0;,3) умножение матриц (или матрицы на вектор, в зависимости от размерности В) Х= С В при А=), D=0;

4) умножение со сложением матриц

X=C В+Р при А=1;

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

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

Обнуление нижнего левого квадранта объединенной матрицы можно осуществить, применяя исключение Гаусса, до приведения матрицы А к верхнетреугольному виду. Тогда автоматически на место матрицы -С получится нулевая матрица. При этом, с целью обеспечения численной устойчиво5 сти вычислений, преобразование матрицы А выполняется по алгоритму исключения Га усса с частичным выбором ведущего элемента по столбцу. Это означает, что íà i-м шаге (l - 1, n - 1) алгоритма Гаусса исключению элементов ale (i = i + 1, n), принадлежа-! щих исходной матрице А = А (при i = 1) или уже частично преобразованной матрице А (при! > 1), предшествует последовательное сравнение их с элементом а;, и,если оче..I

5 редной элемент I ail I > 1 аи I, осущестi I вляется перестановка j-й и I-й строк. т.е, i-я строка становится j-й, и наоборот. В противном случае перестановка строк не происходит, Только после окончания всех (на данном

1784997 шаге) операций сравнения и перестановок блока 2 вЂ” по переднему фронту синхроим(т.е. процесса выбора ведущего элемента) пульса, т.е. в начале такта. Условимся также, начинается процесс исключения элементов что изменение состояния счетчиков 9 и 28

ale и преобразования строк с (I+ 1)-й по п-ю происходит по положительному перепаду матрицы А (а в нашем случае еще и В), 5 сигнала на их декрементирующих входах, I заключающийся в попарном суммировании Считаем, что перед началом вычислений каждой из этих строк с I-й строкой (объеди- (m + 1)-е, в разряды всех регистров узла 6.1 ненной матрицы в нашем случае), пред- установлены в нулевое состояние, варительно умноженной на коэффициент

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

my - -аи /ац. Однако поскольку в объединен- 10 запуска устройства, устанавливает в едининой матрице под матрицей А находится мат- цу RS-триггер 40, а также поступает на вход рица -С, которую необходимо привести к режима счетчика 36, в который записываетнулевой матрице, никаких перестановок ся значение (n+ р - 1) - 4, и (через элемент строк матриц С и 0 со строками матриц А и ИЛИ 39) на вход режима счетчика 37.

В производить нельзя. Вследствие этого ус- 15 В первом такте по переднему фронту тройствоосуществляет выбор ведущегоэле- синхроимпульса в счетчик 37 записываетмента среди элементов I-ro столбца ся информация с выхода счетчика 36, т.е. матрицы А (йа I-м шаге), а процесс исключе- (n + р - 1), и:на выходе отрицательногоо ния осуществляетсреди элементов 1-го стол- . переноса счетчика 37 вЂ” единица а также

1 ! бца матриц А и С, т.е. среди элементов 20 устанавливаются в единицу элементы эаI-ro столбца асей объединенной матрицы держки 3,1, 7.1 и 14Л, после чего в счетчик (I = 1, л -1). Отметим также, что все признаки 9.1 записцвается значение (и - 1) =.2. Кроме перестановки строк запоминаются и пере- того, элемент а 1 = ац. исходной матрицы даются между ОБ в качестве элементов поступает на первый вход блока 1.1 и, пройнижйей треугольной матрицы перестановок 25 дя через коммутаторы l1,1 и 12,1, записываV=(v>ij. Отметим также, что за и-1 шагов, ется в конце такта в регистр 19.1 (на алгоритма Гаусса обнуляются и -1 столбцОв управляющих входах обоих коммутаторовобъединенной матрицы. Однако для пол- единицы), а единица с выхода элемента за учения правильного результата необходи- держки 3.1 записывается в (m+ 1)-й разряд, мо обнулить и п-й столбец матрицы С. 30 первого регистра (Р1) узла 6,1.

Поэтому в данном случае алгоритм Гаусса Во втором такте Счетчик 37 уменьшает имеет и-й шаг, на котором отсутствует про- . свое значение на единицу; В блоке 1,1 нэ цесс выбора ведущего элемента (элемент выходе элемента, задержки 3.1 вЂ” нуль, на а " сразу становится ведущим, т.K. årîéåñ" выходе триггера 4Л,появляется единица, чем сравнивать), а процесс. исключения про-: 35 содержимое (m+ 1)-ro разряда Р1 узла 6.1 изводится аналогично предыдущим шагам переписывается в Р2 узла 6.1. Элемент алгоритма; а2 = a2 поступает. через коммутатор 8.1 на .1

Поступление исходных данных органи- входы коммутаторов 11.1 и 1Ц.,и узла сравзовано следующим. образом, На I-й вход нения 10.1,:на другие входы которых постуустройства {I = 1, flj каждый такт поступает 40 лает а11 . пусть I аи 1 t а211 I. Тогда элемент l-.го столбца обьединенной матри" "нуль с выхода узла сравнения 10.1 (признак цы,начинаясэлементааяизакенчивая-Cpi, перестановки строк) поступает через элена (n + k)-й вход устройства (k 1, I/) -.. менты 13.1 и 5Л в элемент задержки I4.1 и аналогично, начиная с элемента Ьь и закан- на управляющие входы коммутаторов 11.1 и чивая ярк. В свою очередь, элементы столб- 45 12.1. вследствие чего а11 переписываетс в яв ца объединеннои матрицы постуйают на регистр 19.1, а а записывается в Р1 узла соответствующие входы устройства со сдви- 6Л. В блоке 1.2 в счетчик 28;2.записывается гом один такт, т.е. элемент a1i поступает на значение п-1,элементы задержки 20;2,23.2

I-й вход устройства в i-м такте его работы, а и 33.2 устанавливаются в единицу. На перэлемент beak вЂ” в(л+ k) ì такте работы устрой- 50 вый информационный вход блока 1.2 поступает элемент ац - ад и. пройдя через

Рассмотрим работу устройства. Для коммутатор 32.2, поступает на входы коммупростоты описания и без потери общности таторов 21,2 и 22.2 и в конце такта записыположим n - 3, р = r = 2, Условимся, что вается в регистр 25.2. прием информации во все регйстры, в том 55 В третьем такте счетчик 37 уменьшает числе в регистры узлов задержки, в элемент- свое значение на единицу. В блоке 1.1 на ты задержки 14 и 27 всех: операционных выходе элемента задержки 17.1 появляетблоков осуществляется по заднему фронту ся единица. Элемент аз - аз поступает синхроимлульса, т.е, в конце такта, а во все: через коммутатор 8Л на входы коммутатоостальные триггеры всех 05 и счетчик 37 . ров 11.1 и 12,1 и узла сравнения 10.1, на

1784997

10 другие входы которых поступаета(1(:. Пусть рого поступает агг с Р2 узла 24.2 и сумма

I аз1 I I a11 I . тогда единица с выхода Iz1 азг + azz = агг поступает в регистр 35.2 узла сравнения 10.1 записывается в эле- и узел 34.2. Элемент-С12- -C12 поступает

1 мент задержки 14.1 и управляет коммутато- на входы коммутаторов 21.2 и 22.2 и записырами 11.1 и 13.1, вследствиЕ чего à111 5 вается в Р1 узла 24.2. В блоке 1.3 элемент записывается в Р1 узла 6.1 (а21 переписы- задержки 27.3 устанавливается в единицу.

1 вается в Р2 узла 6.1), а а31 записывается в Элемент азз = азз поступает на вход комму-"

1 регистры 18.1 и 19,1. В блоке 1.2 единица из татара 32.3 и записывается в регистры 25.3 (m+ 1)-го разряда Р1 узла 24,2 переписыва- и 26.3, а23 переписывается в Р2 узла 24.3, ется в Р2узла24.2. Элементагг=агг посту- 10 а1з записывается вР1узел24,5. В блоке1.4

1 1 пает на вход коммутатора 32.2, с выхода элемент Ь21= b21 поступает на вход комму1 которого поступает на входы коммутаторов татора 32.4 и записывается в Р1 узла 24. 4, а

21.2 и 22,2 и в конце такта записывается в Ь11 перезаписывается в Р2 узла 24.4. В регистр 25,2 (а12 переписывается в Р1 узла блоке 1 5 в счетчик 28.5 записывается зна1

24.1). В блоке 1.3 элементы задержки 20.3, 15 чение n - 1. Элемент Ь12 = Ь12 поступает на

23.3 и 33.3 устанавливаются в единицу, в вход коммутатора 32 5 и, пройдя коммутасчетчик 28,3 записывается значение n - 1. тор 21.5, записывается в узел 24.5..

На первый вход ОБ 1.3 поступает элемент В шестом такте аггг из узла.34.2 постуа13=.а1з и, пройдя через коммутаторы 32.3, . пает на первый вход блока 1,1 и через ком1

21.2 и 22.2, в конце такта записывается в 20 мутатор 12.1 записывается в регистр 19.1. регистр 25.3, Ha вход делителя 16 1 поступает -С11 и а31

В четвертом такте счетчик 37 уменьшает и результат С111/a31 = 141поступает на вход свое значение на единицу. В блоке 1.1 триг- регистра 15.1. В блоке 1.2 на вход умножигер 4.1 устанавливается в нуль. На входы ком- теля 30,2 поступает I34 и азг, умножается Й

1 мутаторов 11.1 и 12,1 поступает -C1 = -С11 и 25 поступает на второй вход сумматора 29.2, на записывается в Р1 узла 6.1, а . . вЂ” пережи- первый вход которого с выхода узла 24.2 1(1 сывается в Р2 узла 6.1, а21 поступает на поступает а12 и сумма l31 азг +а12 -a32 первый вход делйтеля 16.1, на второй вход передается на выход регистра 35,2 и запикоторого поступает а31 из регистра 18.1.: сывается в 34.2. На вход коммутатора 32,2

Делитель 1.6.1 выполняет деление и резуль- 30 поступает -Czz = -Czz . В блоке 1.3 на входы

1 . тат -а21 /аз1 = lZ1, пройдя регистр 15.1, по- умножителя 30.3 поступает l21и азз1, резуль1 1 ступаетнаеговыход. В блоке1.2 на выходе тат поступает на второй вход сумматора злементазадержки27.2-единица. Элемент 29.3, на первый вхор которого поступает а32 = а32 поступает на Вход коммутатора . а23 и сумма 121 333 + а23 а23 записы

1 :.1

32.2 и, пройдя коммутатор 22.2., записывает- 35 вается в регистр 35;3 и в узел" 34,3. На ся в регистры 25.2 и 26.2. В блоке 1.3 на. вход коммутатора 32.3 поступает элевыходе элемента задержки 20,3 вЂ” нуль. На мент-C13=-С13 В блоке 1.4 на вход коммувход коммутатора 32.3 поступает элемент татара 32.4 поступает элемент Ь31 = Ьз1 и, 1 а23 =,а23 и, пРойдя коммутатор 21.3, зепи- пройдя коммутатор 22.4, записывается в ресывается в Р1 узла 24.3. В блоке 1„4 на 40 гистры25,4 и 26.4, В блоке1.5на вход коммувыходе элементов задержки 20.4, 23.4 и 33.4 татора 32,5 поступает Ьгг = Ьг21и записывается устанавливается единица. В счетчик 28,4 за- " в Р1 узла 24.5. писывается зйачение и -1. Элемент Ь11= Ь11 В седьмом такте в блоке 1.1 на входы

1 поступаетнавхадкоммутатора32.4и, прой-: делителя 16;1 поступает -C21 и аз1 и редя коммутатор22.4,записывается aðåãèñòð 45 зультат С21 /a31 = 151 поступает на выход

1 1

25.4, регистра 15.1. На вход коммутатора 8.1 поВ пятом такте счетчик 37 уменьшает ступаетазг и всхемесравнения происходит

2 свое значение йа единицу, В блоке 1.1 на сравнение вгг и азгг. пусть 1 азгг I > I azz (, 2 входы коммутаторов 11.1 и 12.1 поступает.. тогда азг записывается в регистры 18.1 и элемент "C21 -C21 и записывается в Р1 50 19.1, à azz вЂ” в Р1 узла 6.1. В блоке 1.2 на

1 г узла 6.1 а -С11 переписывается в Р2 узла входы умножителя 30.2 поступает l41 и азг

6.1. На вход делителя 16 1 поступают а11 и и результат подается на второй вход сумма1 аз1 и результатделения -а11 /a31 "l31 по- тора 29.2 и сумма l41 азг - Сц = С12 1 1 1 ступает на выход регистра 151, с выхода записывается в регистр 35.2 и в узел 34.2. которого121поступаетна входблока1.2 и на 55 На вход коммутатора 32.2 поступает элевторой вход умножителя 30.2, на первый мент агз, В блоке 1.3 на входы умножителя вход которого поступает азг с выхода реги- 30.3 поступает l31 и азз, результат поступа1 - 1 стра 26.2, результат l21 a32" поступает на ет на второй вход сумматора 29.3, сумма второй сумматор 29.2, на первый вход кото- l31 аЗз" +a131=-а33 поступаЕт в региСтР 35.3 .

1784997 и в узел 34.3. На вход коммутатора 32.3 пает б21 и результат 151 Ь31 + б21 = dz12

1 1

: поступает -C23 и через коммутатор 21,3 за- записывается в регистр 35,4 и в узел 34.4. В 1 писывается в узел 24.3. В блоке 1.4 на входы блоке 1.5 на входы умножителя 30.5 постуумножи еля 30.4 поступает 121 и b31, резуль- пает 141 и b32 и результат поступает на вто-:

1 1 тат поступает на второй вход сумматора, 5 рой вход сумматора 29.5, на первый вхоф сумма 121 Ь31+ Ь21 = b21 поступает на которого поступает б12 и результат 141

1 2 коммутатора 32.4 поступает элемент узел 34.5. б11 = d11 и, пройдя коммутатор 21.4, запи- - В одиннадцатом такте в блоке 1.1 на

1 сывается в узел 24.4, В блоке 1.5 на вход 10 входы делителя 16,1 поступает С133 и аззз и коммутатора 32.5 поступает элемейт результат-С1з /азз -143поступаетнавыход

3 з

b32 - Ь32 и зайисывается в регистры 25.5 и регистра 15,1, на входы умножителя 30.2

26.5, -: .: -.: поступает 152 и азз и результат поступает

В восьмом такте в блоке 1Л на входы на второй вход сумматора 29.2, на первый делителя 16.1 поступаетazz и а32 и резуль- 15 вход которого поступает Сгзг и результат

2 2 тат àzz /а32 = 132 поступает на выход реги- 152 азз + С2з Сгз поступает в регистр г 2 2 2 стра 15.1. В блоке 1.2 на входы умножителя 35,2 и в узел 34.2. На вход коммутатора 32.2

1 з

30.2 поступает 151и эзг :, результат йоступа- поступает b31 и записывается в регистры ет на второй вход сумматора 29.2 и сумма 25.2 и 26.2. В блоке 1.3 на входы умножителя

151 . à3z --,C22 = C22 записывается в узел 20.30.3 постуйает 142 и Ьз12 и результат посту- . г

34.2. В блоке 1.3 на входы умножителя 30.3 пает на второй вход сумматора 29,3, на перпоступает 141 и а33 и результат умножения вый вход котооого поступает.б112 pl поступает йа второй вход сумматора 29.3, на .. результат 112 b31 + d11 б11 записывается

1 - первый вход которого поступает-С13 и сум- - в регистр 25.3 и узел 34;3. В блоке 1.4 на ма Ьц азз. - C13 = C13 принимается в 25 входы умножителя 30,4 поступает 13z и b3zг

1 2 регистр 35.3 и узел 34.3. На второй вход и результат поступает на второй вход сумкоммутатора 32.3 с выхода узла 34.4 посту- матора 29.4, на первый вход которого поступавет элемент Ь21 и, проидя коммутатор пает dzz и результат 151 . b31 + бгг" = dzz

2 1 . 1

21.3, записывается в узел 24.3. В блоке 1.4 записывается в регистр 35.4 и в узел 4.4. В на входы умножителя 30.4 поступает 131 и 30 .блоке 1,5 нэ входы умножителя 30.5постуЬз1 и результат поступает на второй вход пает 151 и b31 и результат поступает на сумматора 29,4, на первый вход которого по- второй вход сумматора 29.5, на первый ступаетЬ11 ирезультат131 Ь31 +Ь11 =Ьз1: вход которого поступает d221 и результат

1 2 записывается в регистр 35.4 и в Р1 узла 34.4, 151 b31 + бгг = бгг записывается в регистр

В блоке 1.5 на вход умножителя 30.5 посту- 35 35.5 и:в узел 34.5. пает 121 и b33 и Рвэультат пОСтУпает на В двенадцатом такте в блоке 1.1 на вхо.1 второй. вход сумматора 295. нэ первый ды делителя .16Л поступает Сгзз и а333 и вход которого поступает b22 и результат результат-С23 /азз =153 поступает на выход

121 032 + Ьгг "Ьгг записывается в регистр регистра 15,1, В блоке 1.2 на входы умножи1 1 2

35.5 и в узел 34.4. 40 теля 30,2 поступают 143 и Ь313 и результат

В десятом такте в блоке 1 1 на входы поступает на-второй входсумматора29.2, на. делителя 16Л поступает Czzг и а32 и резуль- первый вход которого" .поступает б: и тат-Сгг /азг - bsz постуйает на выход реги- результат 14з b31 + б11 - d11 =х11записыг г . 3 з ". 4 4 стра 15.1. На второй вход коммутатора 8Л вается в узел 23.2 и появляется на первом поступает азз и записывается в регистры 45 выходе устройства. В блоке 1.3-на входы:

18Л и19Л. В блоке1.2 на входыумнбжителя умножителя 30.3 поступают lsz и b312 йрепоступают I42 и а332 и результат поступает зультат поступает на второй вход сумматора на второй вход сумматора 292, на первый 29.3, нэ первый вход которого поступает вход которого йоступает С13 и результат бг1 и результатl52 b31 +dz1 -б213посту142 аззг + С13 = C13 поступает в регистр 50 йает в узел"34,3 и в регистр 35.3. На.вход .г 335.2 и узел 34.2. В блоке 1.3 на входы умно- коммутатора 32.3 поступает b323 и"записыжителя 30.3 поступает 132 и b312 и результат вается в регистры 25.3 и 26.3. В блоке 1.4 на поступает на второй вход сумматора 29.3, на вхбды умножителя 30.4 поступают 142 и b322 первый вход которого поступает bz1 и ре- и результат поступает на второй вход сум2 зультат Iзг Ьз1 + bz1 = b31 записывается 55 матора29.4, наепрвыйвходкоторогопосту2 2» 3

: в регистр 35.3 и узел 34.3. В блоке 1,4 на пает б12 и результат 142 ° Ь122+ б122 = б123 входй умножителя 30,4 поступает 151 и Ь311 записывается в 34.4 и в регистр 35.4. и результат поступает на второй вход Сум- В тринадцатом такте в блоке 1.2 на вхоматора29.4, на первый входкоторого посту- ды умножйтеля 30.2 поступает 153 и Ь313 и

1784997 результат поступает нэ второй вход сумматора 29.2, на первый вход котооого поступает d21, и сумма!5з Ьз1 + d21 = dг1 = X21 записывается в узел 34.2 и появляется на первом выходе устройства. В блоке 1.3 на 5 входы умножителя 30.3 поступают 14з и Ьзгз и результат поступает на второй вход сумматора 29.3, на первый вход которого поступает

dQ и результат !43 Ьзг + d12 = d12 X12 записывается в узел 34.3 и появляется на 10 втором выходе устройства. B блоке 1.4 на входы умножителя 30.4 поступает )s2 и Ьзг и результат поступает на второй. вход сумматора 29.4, на первый вход которого поступает огг и результат l52< Ьзг + огг = огг 15 поступает в узел 34,4 и в регистр 35.4.

В четырнадцатом такте в блоке 1.3 на входы умножителя поступают tm u Ьзг и результат поступает на второй вход сумма- . тора 29.3, на первый вход которого поступа- 20 ет бггз и результат Ьз Ьзг + бгг = бгг - Хгг

3 4 появляется на втором выходе устройства.

На этом вычисление элементов результирующей матрицы X = СА "В + О заканчивается. Таким образом, полное 25 время реализации.алгоритма T=2n+,г+

nA вЂ” 1

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

- 1,тактов (при этом с k-ro выхода устрой(;тва выдается k-й столбец матрицы X (k = 1, r)) . аналогично поступлению исходных элемен- тов матриц В и D нэ соответствующие входы устройства. Однако в случае решения пото- 35 ка аналогичных задач, период работы устройства составляет с = Т - (р + r - 1) тактов, пГп вЂ” 11 т.е.2п+1+(р-1) (n-2)+ вЂ” тактов, Ф

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

Устройство для операций над матрицами, содержащее n+ rоперационных блоков,,50 где и и r вЂ” порядки обрабатываемых матриц, и блок синхронизации, причем вход запуска устройства подключен к входу запуска блока синхронизации, первый и второй выходы которого подключены соответственно к 55 первому и второму управляющим входам первого операционного блока, с первого по (n + г)-й входы элементов обрабатываемых матриц устройства подключены,соответственно к первым информационным входам операционных блоков с первого по (n + r)-й, первый, второи и третий выходы а-го операционного блока(где а = 1, ..., и + r - 1) подключены соответственно к первому управляющему, второму управляющему и к второму информационному входам (а + 1)-го операционного блока, четвертые выходы операционных блоков с второгоо по (n+ r)-й подключены соответственно к выходам с первого по(п+ r-1)-й результата устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет частичного выбора ведущего элемента при вычислении выражений вида (СА. В + D). где А - матрица размерностью(п хг), В вЂ”. матрица размерностью (и Ф r), С вЂ” матрица размерностью (р

X n), 0 вЂ” матрица размерностью (р Х r), в нем пятый выход Ь-го операционного блока (где

Ь = 2...„п + r - 1) подключен к третьему управляющему входу (Ь + 1)-го операционного блока, четвертый выход первого операционного блока подключен к третьему управляющему входу второго оперэционнбго блока, шестой выход С-го операционного блока (где С = 3, ..., и + r) .подключен к третьему информационному входу (С - 1)-ro операционного, блока, шестой выход второго операционного блока подключен к второму информационному входу первого операционного блока, первый вход константы устройства подключен к третьему информационному входу первого операционного блока и к четвертым информационным входам операционных блоков с второго по (п + г)-й, второй вход константы устройства подключен к пятым информационным входам оперЩионных блоков с второго по (и + r)-й, третий выход блока синхронизации подключен к входам синхронизации операционных блоков с первого по (n + г)-й, при этом первый операционный блок содержит три коммутатора, счетчик, триггер, делитель, четыре элемента задержки, узел задержки, узел сравнения, три регистра, элемент И и элемент ИЛИ, причем первый управляю- щий вход первого операционного блока подключен к входу первого элемента задержки, выход которого подключен к информационному входу триггера, к первому входу элемента ИЛИ, к первому управляющему входу узла задержки и к первому выходу первого операционного блока, второй управляющий. вход которого подключен к входу второго элемента задержки, выход которого подключен к управляющему входу первого коммутатора, к входу режима счетчика и к четвертому выходу первого операционного блока, первый информационный

1784997

16 вход которого подключен к первому информационному входу первого коммутатора, выход которого подключен к первым информационным входам второго коммутатора, третьего коммутатора и узла сравнения, выход которого подключен к первому входу элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к управляющим входам второго и третьего коммутаторов и к входу третьего элемента задержки, выход которого подключен к второму выходу первого операционного блока, выход второго коммутатора подключен к информационному входу узла задержки, первый выход которого подключен к входу четвертого элемента задержки, выход которого подключен к входу записи-считывания первого регистра, к входу декремента счетчика и к входу установки в "0" триггера, выход которого подключен к второму входу элемента И, второй и третий информационные входы первого операционного блока подключены соответственно к второму информационному входу первого коммутатора и к информационному входу счетчика, информационный выход которого подключен к второму управляющему входу узла задержки, второй выход которого подключен к первому информационному входу делителя, выход которого подключен к информационному входу второго регистра, выход которого подключен к третьему выходу первого операционного блока, выход третьего коммутатора подключен к информационному входу третьего регистра и к информационному входу первого регистра, выход которого подключен к второму информационному входу делителя, выход третьего регистра подключен к вторым информационным входам второго коммутатора, третьего коммутатора и узла сравнения, вход синхронизации перво о операционного блока подключен к входам синхронизации триггера, узла .задержки, первого регистра и счетчика и к входам записи-считывания второго и третьего регистров, при этом каждый операционный блок с второго по (n + г -й содержит три коммутатора, счетчик, два узла задержки. сумматор, умножитель, четыре регистра и четыре элемента задержки, причем в каждом операционном блоке с второго по (n+ r)-й первый управляющий вход операционного блока подключен к входу первого элемента задержки, Выход которого подключен к nepso y упрааляющему входу первого узла задержки и к первому выходу операционного блока, втого коммутатора, выход которого подключен к первым информационным входам перво10 ro и второго коммутаторов, выход первого

20 управляющему входу первого узла задерж30

40 соответст вен но к второму информацион но50

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

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

Редактор M,Кузнецова Тех е М,Мо гентал К иг, р д р орректор П,Гереши

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

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

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

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

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

Патент 1784997