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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных машинах и устройствах обработки данных для обращения плотных (N<SP POS="POST">.</SP>N) - матриц. Цель изобретения - повышение быстродействия устройства. Цель достигается за счет алгоритмических и структурных решений, реализованных в данном устройстве. Устройство содержит N<SP POS="POST">2</SP> операционных блоков двух типов и N регистров, причем операционный блок первого типа содержит умножитель, узел вычисления обратной величины числа, два регистра, два триггера, два элемента И, две группы элементов И, элемент ИЛИ - НЕ, группу элементов ИЛИ, а операционный блок второго типа содержит умножитель, сумматор, три регистра, четыре триггера, группу элементов И, два элемента И. Особенностями функционирования устройства является параллельно-поточная организация вычислений. 4 ил., 2 табл.

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

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

РЕСПУБЛИК (191 (111

А1 (51) 4 С 06 F 15/347

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

Н А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГННТ СССР (21) 4365978/24-24 (22) 11.12.87 (46) 07.12.89. Бюл. М 45 (72) В.П. Якуш, С,Г. Седухин, П.И. Соболевский и Н.А. Лиходед (53) 681.3(088.8) (56) Авторское свидетельство СССР и 1211754, кл. G 06 F 15/347, 1984.

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

У 1444820, кл. G 06 F 15/347, 13,01.87. (54) УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных машинах и устройствах обработки данных для обращения плотных (пкп)-матриц.

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

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

Устройство для п 2 содержит информационные входы 1, и 1, операционные блоки 2 (, 2, 2, и 2«, регистры Зэ, и 3, синхровход 4 и выходы 5, и 5<, 2 действия устройства, Цель достигается за счет алгоритмических и структурных решений, реализованных в данном устройстве..Устройство содержит и операционных блоков двух типов и и регистров, причем операционный блок первого типа содержит умножитель, узел вычисления обратной величины числа, два регистра, два т иггера, два элемента И, две группы элементов И, элемент HJIH-HE, группу элементов ИЛИ, а операционный блок второго типа содержит умножитель, сумматор, три регистра, четыре триггера, группу элементов И, два элемента И.

Особенностями функционирования устройства является параллельно-поточная организация вычислений ° 4 ил., 2 табл.

С:

Операционный блок первой группы

2„; (j=l,n) содержит (фиг, 2) пер вую группу входов 6, синхровход 7, умножитель 8, узел 9 вычисления обратной величины числа, регистры 10 и 11, триггеры 12 и 13, элементы И

14 и 15, группы 16 и 17 элементов И, элемент ИЛИ-НЕ 18, группу 19 элементов ИЛИ, первую группу выходов 20.

Операционный блок второй группы

2, (i2,п, j l п) содержит (фиг,3) первую группу входов 21, вторую группу входов 22, синхровход 23, регистры 24-26, умножитель 27, сумматор 28, триггеры 29-32, группу 33 элементов И, элементы И 34 и 35, первую группу выходов 36, вторую группу выходов 37.

3 15?7643 4

30

H ос1и1иу работы устройств» для об— ращения м,1трицы Л=(а; ) положен метод, ири котором расширенная (п12п)матрица LA, е1 сводится к (n12n) мат- 1 -1 рице tF., Л 1 по рекуррентным соотношением для: (a1 а, =а,1, i,j=l,n; k l,n;

При описании работы устройства в

I I11 обозначении а индекс в скобках

\I указывает номер рекуррентного шак га, в обозначении а индекс k ука1) зывает номер такта.

Операционный блок первой группы

2,;(j=l,n) работает следующим образом.

На вход 6 подаются m-разрядные

К элементы а вместе с (m+1)-м и

1 ) (m+2) ì дополнительными разрядами, принимающими значения 0 или 1. В исходном состоянии регистры 10 и 11 и триггеры 12 и 13 устанавливаются в нулевое состояние ° На i-м такте

25 ири подаче на вход 6 элемента а с (ш+1) -м разрядом 1 и с (m+2) ì разрядом О, на выходе элемента И 15 формируется единичный сигнал, который разрешает запись элемента а в регистр 11, триггер 12 устанавливается н единичное состояние, на выходы

201„„,1 и 201,1, 1 подаются соответственно единичный и нулевой сигналы.

На (i+1) м такте на вход 6 подаются щ-разряпный элемент Ь, (т+1)-й разряд О и (m+2)-й разряд 1, При этом в регистре 10 записывается элемент Ь (так как на выходе элемен та И 14 формируется единичный сигнал)

40 триггер 13 устанавливается в единичное состояние, а триггер 12 — в нулевое состояние, на выходе узла 9 Dbl числения обратной величины числа формируется значение 1/а, а на выходе

45 умножителя 8 — значение — b/à (с выхода регистра 10 элемент Ь" (снимается с противоположным знаком), которое через открытые элементы И группы 16 подается íà входы элементов

ИЛИ группы 19 с выходов которых

s0 подается на выход 20 операционного блока с (m+1)-м разрядом 0 и с (m+2)-м разрядом 1.

На (i+2) — ì такте на вход 6 подается нулевое m-разрядное значение с (m+1)-м 5 разрядом О и с (m+2)-м разрядом О.

При этом триггеры 12 и !3 устанавливаются в нулевое состояние, Hà вых 1де эиемсита ИJIИ-НЕ 18 формируется единичный сиги 1J1, который < ткрывает элементы И группы 17, через которые с учла 9 вычисления обратной величины

1/а подается на входы элементов ИЛИ группы I9, с выходов которых значение

1/а с (m+1)-м разрядом 0 и с (m+2)-м разрядом 0 подается на выход 20, Операционный блок второй группы

2, ; (i=2, п; j=1, n) работает следующим образом.

Ч исходном состоянии регистры 2426 и триггеры 29-32 устанавливаются в нученое состояние. На i-м такте на вход 21 подается т-разрядный элемент

Ь, à (m+1) и разряд 1 и (m+2) é разряд О подаются соответственно на входы 22„„, и 22,„+ . При этом триггер

29 устанавливается н единичное состояние, на выходе элемента И 34 формируется единичный сигнал,,который разрешает запись элемента Ь в регистр

25, на выходы 37,, и 37, подают— ся соответственно единичный и нулевой сигналы, На (i+1)-м такте подается на вход 21 элемент с, на вход 22 элемент а + с (m+1)-м разрядом О и с (m+2) ì разрядом !. При этом триггер 29 ус-.анавливается в нулевое состояние, а триггеры 30 и 31 — в единичное состояние, в регистр 24 запи1 11 сывается элемент а, на выходе элемента И 35 формируется единичный сигнал, котооый разрешает запись элемен1+1 та с в регистр 26, элементы И группы 33 открываются (триггер 31 устанавливаетс я в единичное состояние), на выходе умножителя 27 формируется значение axb, а на выходе сумматора

28 — значение а1Ь+с, которое подается на выход 36,, На выходы 36 „„+ и 36„, подаются соответственно единичный и нулевой сигналы> на выход

371,„, — значение а, на выходы 37,„„ и 37„„+ — соответственно нулевой и единичный сигналы,На (i+2)-м такте подается на вход 21 нулевое m-разрядное значение, на вход 22<,„элемент а, на входы 22 1, и 22щ, нулевые разряды. При этом триггеры

30 и 31 устанавливаются в нулевое состояние, а триггер 32 — в единичное состояние, элементы И группы 33 закрыты, на выходе умножителя 27 формируется значение а Ь, на выходе сумматора 28 — значение, которое подается на выход 36, . На выходы 36

m 1е 1-1

5 1527643 6 и 36„;,+г подаются соответственно ну- На седьмом такте в регистр 3 эа(21

)г левои и единичный сигналы, на выход писывается значение Ь которое (z Ф р пода37(°,„ — значение а, а на выходы 37 (Ы .( ется на выход 5 и 37,„1. — нулевые сигналы.

В табл. 1 и 2 представленалогика Фо р мул а и з о б ре те ни я

5 работы операционных блоков соответст- Ус тройство для обращения матриц, венно первой и второй групп. содержащее и операционных блоков

Работу устройства рассмотрим иа первой группы (n-размерность матриг примере обращения одной матрицы А 10 В цы) п -n операционных блоков второй для n=2, группы и и регистров, которые обраВ исходном состоянии регистры 10> зуют матрицу (n+1)1(п, операционные

Il и 24-26 и триггеры 12, 13 и 29- блоки первой и второй групп распо32 устанавливаются в нулевое состоя- ложены в позипиях соответственно ние. )5 (l,j)-х и (2.,))-х (jlп; i=2,п),региНа нулевом такте на вход 1, пода- стгы расположены в позициях (и+!sj) в о ется m-разрядный элемент ан и допол- j é информационный вход устройства нительные (m+1)-й разряд 1 и (m+2)-й подключен к первому информационному разряд О. При этом в операционном входу (j, 1)-го операционного блоблоке 2«в регистр 11 записывается 20 ка, первый информационный вход (1, элемент а „. р)-ro операционного блока (1 2,п

На первом такте на вход 1 подается p=I и-1) подключен к первому инфор(. элемент а, (m+1 )-й разряд О и (m+2)-й мационному входу (1-1, p+I)-го операзряд 1, на вход 1< — элемент а, I рационного блока, а информационный

При этом в операционном блоке 2„25 выход (1, j)-го операционного бло(%) (01 (о) формируется значение Ьг, ---à, /a(((), в ка — к второму информационному входу операционном блоке 2«в регистр 25 (2, j ) -го операц1(онного блока, второй записывается элемент а <, информационный выход (k, j ) -ro опеНа втором такте на вход 1(подается рационного блока (k 2, и-1) подклюнулевое m-разрядное число, (m+1)-й 30 чен к второму информационному входу разряд О и (m+2)-й разряд О, на вход (k+1, j)-го операционного блока, вто1 — элемент а, При этом в операци- рой информационный выход (n, j)-ro онном блоке 2„, формируется значение операционного блока подключен к ин (i 1())

b(, =-1/а „, в операционном блоке 2 — формационному входу (и+1, j)-го ре(<) «) (о) g (a) (о) значение а =а г — (а,, а „) а,, гистра, выход (n+1, р)-ro регистра

На третьем такте на вход I пода- подключен к первому информационному ется нулевое m-разрядное число, при входу (n, р+1)-го операционного блоэтом в операционном блоке 2« форми- ка, первый информационный выход (1, руется значение а, =а г /а н, в опера- n)-ro огерационного блока является (() ционнь(й блок 2 1 в регистр 11 записы- (1-1)-ì выходом устройства а выход ()

t вается значение а, в регистр 3 > — (и+1 и)-го регистра — n-м выходом (il 21

1 Э значение b г,, устройства, группа настроечных вхона четвертом такте в регистр Зэ(дов которого подключена к группе назаписывается .значение Ь,, в опера( строечных входов (I, 1)-го операциционном блоке 2,< формируется значе- онного блока, первая группа настро((.) (i I 45 ние Ь,q =-а, /а,, в операционном блоке е«-ных выходов (2, i)-ro операцион2 в регистр 25 записывается эначе- ного блока подключена к группе на((7 ние Ь г . строечных входов (1, i+I)-го операНа пятом такте в операционном блоке ционного блока, а группа настроеч2 о ф рмируется значение Ь =1/а z 2 50 ных выходов (I, j)-го операционного (Я1 (11 в операционном блоке 2 — значение блока — к группе настроечных входов (г((i) g (1) g (il (i)

Ь, b(,-(b < /а ) а,, которое подается (2, j) -го операционного блока, на выход 5(устройства. группа настроечных входов (k+1, j)-го

На шестом такте в операционном бло- операционного блока подключена к втоке 2 формируется значение з 1 =Ь /а ., рой группе настроечных выходов (k

1(l= () l()

55 в регистр 3,)2 записывается значение j)-ro операционного блока, синхро(2) (И (х)

Ь +. При этом значения Ь, и b«пода- вход устройства подключен к синхроются соответственно на вы:.оды 5(и входам всех операционных блоков, 5<„ причем операционный блок первой груп1527 643 пы содержит первый и второй регистры, первый элемент И, первый триггер и узел вычисления обратной величины числа вход которого соединен с выхо1

5 дом второго регистра, информационный вход которого соединен с первым информационным входом операционного блока первой группы и с информационным входом первого регистра, синхровход которого соединен с выходом первого элемента И, первый и второй входы которого соединены соответственно с синхровходом и первым входом группы настроечных входов операционного блока первой группы, вход первого триггера соединен с вторым входом первого элемента И, синхровход операционного блока первой группы соединен с синхровходом первого триггера, выход которого соединен с первым выходом группы настроечных выходов операционного блока первой группы, причем операционный блок второй группы содержит первый, второй 25 и третий регистры, первый триггер, умножитель и сумматор, первый информационный вход которого соединен информационными входами второго и третьего регистров, а второй инфор- gp мационный вход с информационным входом первого регистра, выход которого соединен с первым входом умножителя, второй вход которого соединен с выходом второго регистра, а выход— с первым входом сумматора, синхровход операционного блока второй группы соединен с синхровходами первого регистра и первого триггера, вход

Ф которого соединен с первым входом 4О группы настроечных входов операционного блока второй группы, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия, в операционный блок первой группы введены ум- 45 ножитель, второй элемент И, первая и вторая группы элементов И, элемент

ИЛИ-НЕ, группа элементов И, второй триггер, вход которого подключен к второму входу группы настроечных входов операционного блока первой группы и к первому входу второго элемента И, выход которого соединен с синхровходом второго регистра, а второй вход — с синхровходами операционного блока первой группы и второго триггера, выход которого подключен к второму выходу группы настроечных выходов операционного блока первой группы, к первому входу элемента ИЛИ-НЕ, второй вход которого соединен с выходом первого триггера, а выход— с первыми входами элементов И второй группы, выходы которых соединены с первыми входами соответствующих элементов KIH группы, выходы которой являются информационным выходом операционного блока первой группы, а вторые входы соединены с выходами соответс.твующих элементов И первой группы, вторые входы которых подключены к выходу умножителя„ первый и второй входы которого подключены соответственно к выходу первого регистра и выходу узла вычисления обратной величины числа, соединенному также с вторыми входами элементов И второй группы, в операционный блок второй группы введены второй, третий и четвертый триггеры, группа элементов И, первый и второй элементы И, первые входы которых соединены с синхровходами операционного блока второй группы, второго, третьего и четвертого триггеров, а вторые входы — соответственно с первым и вторым входами группы настроечных входов операционного блока второй группы, вход третьего триггера соединен с вторым входом группы настроечных входов операционного блока второй группы, а выход — с входом четвертого триггера, выход первого триггера соединен с входом второго триггера и первым выходом второй группы информационных выходов, Второй выход которой соединен с выходом третьего триггера, первый и второй выходы первой группы настроечных выходов операционного блока второй группы соединены соответственно с выходами второго и четвертого триггеров, первый информационный выход операционного блока второй группы соединен с выходом сумматора, а второй информационный выход — с выходом первого регистра, выхоц первого элемента И соединен с синхровходом второго регистра, выход второго элемента И соединен с синхровходом третьего регистра, выход которого соединен с первыми входами элементов И группы, вторые входы которых соединены с выходом первого регистра, а выходы — с вгорым входом сумматора, 1527643!

Таблица 1

Входы 20

Входы 6

Такт

Таблица 2 ход Входы 36 Входы 37

Такт Входы 22

21 в-.. m ш+ 1 m+2 1-, m m+ 1 ш+2

1 —;m m+ m+2

0 0 0 Ь 0 0

1 а 0 1 с 0 1

2 а 0 1 с 1 1

3 а 0 1 с 1 1

4 а 0 0 0 1 0

5 0 1 0 Ь 0 0

6 а 0 1 с 0 1

7 а 0 1 с 1 1

1; m m+1 m+2 1-:m ш+ m+2

0 1

-Ъ/а 0

-Ь/а 0

-Ь/а 0

1/а 0

0 1

0 а 1 0 0

1 Ь 0 1 1

2 Ь 0 1 1

3 b 0 1 1

4 0 0 0 0

5 а 1 0 0

0 0 аЬ+с 1 аЪ+с 0 аЬ+с 0 аЬ 0

0 0 аЬ+с 1 аЬ+с 0

0 1 а 0 а 0 а 0 а 0

0 1 а 0 а 0! 527643

1527643

Составитель К. Кухаренко

Техред Л.Сердюкова Корректор A. Обручар

Редактор В, Петраш

Заказ 7511/53

Тираж 668 Подписное

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

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

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