Устройство для обращения матриц Советский патент 1989 года по МПК G06F17/16 

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

Цель изобретения - повышение быстродействия устройства.

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

Устройство для содержит информационные входы 1 и , операционные блоки 2((, 2 i , 2, и , регистры 3 31 и 3 , синхровход 4 и выходы 5, и 5.

Операционный блок первой группы 2ij () содержит (фиг. 2) пер вую группу входов 6, синхровход 7, умножитель 8, узел 9 вычисления обратной величины числа, регистры 10 и 11, триггеры 12 и 13, элементы И 14 и 15, группы 16 и 17 элементов И, элемент ИЛИ-НЕ 18, группу 19 элементов ИЛИ, первую группу выходов 20. ,

Операционный блок второй группы (i-2,n, , п) содержит (фиг.З) первую группу входов 21, вторую группу входов 22, синхровход 23, регистры 24-26, умножитель 27, сумматор 28, триггеры 29-32, группу 33 элементов И, элементы И 34 и 35, первую группу выходов 36, BTopiTO группу выходов 37.

У1

to

Эд

ю

в основу работы устройства для обращения матрицы положен метод, при котором расширенная (п 2п)- матрица i, Е сводится к ()-мат рице Е, А J по рекуррентным соотношением для:

а ; , ; i,j l ,п; k 1 ,п;

1 1к 0 ; , IK-0

а,: а

,/а Г,, k :jtn+k;

VV ., k j«fk+n.

При описании работы устройства в обозначении а индекс в скобках k указывает номер рекуррентного шага, в обозначении а . индекс k указывает номер такта.

Операционный блок первой группы 2,( ,п) работает следующим образом .

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

элементы а;- вместе с (т+1)-м и (т+2)-м дополнительными разрядами, принимающими значения О или 1. В исходном состоянии регистры 10 и II и триггеры 12 и 13 устанавливаются в нулевое состояние. На i-м такте при подаче на вход 6 элемента а с (т+1)-м разрядом 1 и с (т+2)-м разрядом О, на выходе элемента И 15 формируется единичный сигнал, который разрешает запись элемента а в ре- гистр 11, триггер 12 устанавливается в единичное состояние, на выходы 20,1 и 20(1 подаются соот.чет- ственно единичный и нулевой сигналы. На (i+l)-M такте на вход 6 подаются т-разрядный элемент , (т+О-й разряд О и (т-«-2)-й разряд 1. При зтом в регистре 10 записывается элемент b (так как на выходе элемен - та И 14 формируется единичный сигнал триггер 13 устанавливается в единичное состояние, а триггер 12 - в нулевое состояние, на выходе узла 9 вычислении обратной величины числа формируется значение 1/а, а на выходе умножителя 8 - значение - Ь/а (с выхода регистра 10 элемент (снимается с противоположным знаком), которое через открытые элементы И группы 16 подается на входЬ элементов Ш1И группы 19j с выходов которых подается на выход 20 операционного блока с (т+1)-м разрядом О и с (т+2)-м

разрядом 1.

На (i+2)-M такте на вход 6 подает нулевое т-разрядное значение с (га+1) разрядом О и с (т+2)-м разрядом 0. При этом триггеры 12 и 13 устанавливаются в нулевое состояние, на выход

-

10

jc

5276434

элемента ИЛИ-НЕ 18 формируется единич- СИГЧ.1Л, который открывает элементы И группы 17, через которые с узла 9 вычисления обратной величины 1/а подается на входы элементов ИЛИ группы 19, с выходов которых значение 1/а с (т+1)-м разрядом О и с ()-м разрядом О подается на выход 20,

Операционный блок второй группы 2;; (, п; , п) работает следующим образом.

c

0

5

5 .

5

0

В исходном состоянии регистры 24- 26 и триггеры 29-32 устанавливаются в нулевое состояние. На i-м такте на вход 21 подается т-разрядный элемент Ь , а (т+1)-й разряд 1 и (т+2)-й разряд О подаются соответственно на входы и 22 f,, . При этом триггер

29устанавливается в единичное состояние, на выходе элемента И 34 формируется единичный сигнал, .который разрешает запись элемента b в регистр 25, на выходы 37, и 37 подаются соответственно единичный и нулевой сигналы. На (1+1)-м такте подается

на вход 21 элемент с , на вход 22 - элемент с (т+1)-м разрядом О и с (т+2)-м разрядом 1. При этом триггер 29 устанавливается в нулевое состояние, а триггеры 30 и 31 - в единичное состояние, в регистр 24 записывается элемент а на выходе элемента И 35 формируется единичный сигнал, который разрешает запись элемента в регистр 26, элементы И группы 33 открьшаются (триггер 31 устанавливается в единичное состояние), на выходе умножителя 27 формируется значение ajb, а на выходе сумматора 28 - значение , которое подается на выход 36,.;. На выходь1 36,, и 36,2 подаются соответственно единичный и нулевой сигналы, на выход 37,л,„- значение а, на выходы 37, и 37, - соответственно нулевой и единичный сигналы.На (1+2)-м такте подается на вход 21 нулевое т-разрядное значение, на вход 22,„,- элемент а , на входы 22 нулевые разряды. При этом триггеры

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

1 -; mЛ1 1- 1

Yi4-t mvi

515276436

и Збгл+2 подаются соответственно ну- На седьмом такте в регистр 3,2 а

левой и единичный сигналы, на выход 37 значение а, а на выходы 37, и 37,7, нулевые сигналы.

В табл. 1 и 2 представлена логика - работы операционных блоков соответственно первой и второй групп.

Работу устройства рассмотрим на примере обращения одной матрицы А для .

В исходном состоянии регистры 10, II и 24-26 и триггеры 12, 13 и 29- 32 устанавливаются в нулевое состояние .

10

писывается значение Ь, которое подается на выход 5.

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

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

группы и п регистров, которые образуют матрицу ())(П, операционные блоки первой и второй групп расположены в позициях соответственно ,5 (1 ,j)-x и (i,j)-x (j iTn; ),регистры расположеныв позициях (ii+l,j)x, j-й информационный вход устройства подключен к первому информационному входу (j, 1)-го операционного блоНа нулевом такте на вход « подается т-разрядный элемент а° и дополнительные (т+1)-й разряд I и (т+2)-й { азряд 0. При этом в операционном

писывается значение Ь, которое подается на выход 5.

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

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

группы и п регистров, которые образуют матрицу ())(П, операционные блоки первой и второй групп расположены в позициях соответственно (1 ,j)-x и (i,j)-x (j iTn; ),регистры расположеныв позициях (ii+l,j)x, j-й информационный вход устройства подключен к первому информационному входу (j, 1)-го операционного бло

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

блоке 2, в регистр И записывается 20 информационный вход (I,

р)-го операционного блока (,п

элемент а „ .

На первом такте на вход 1, подаетсяр 1,п-1) подключен к первому инфор- элемент а (т+1)-й разряд О и (т+2)-ймационному входу (1-1, р+1)-го one- разряд 1, на вход 1 - элемент aj. .рационного блока, а информационный При этом в операционном блоке 2,, 25выход (1, j)-ro операционного бло- формируется значение ,- -a l/а ° , вка - к второму информационному входу операционном блоке 2 в регистр 25(2, j)-ro операцИонного блока, второй записьшается элемент а , .информационный вькод (k, j)-ro опеНа втором такте на вход I, подаетсярационного блока (, п-1) подклюнулевое т-разрядное число, (т-ь|)-й Qчей к второму информационному входу

разряд О и (т+2)-й разряд О, на вход(k+1, j)-ro операционного блока, вто- 1 - элемент а , При этом в операционном блоке 2, формируется значение Ь.. -|/а,. , в операционном блоке 2/. - зн ачениеа Л а:1-()а- .

На третьем такте на вход Ij подается нулевое т-разрядное число, привходу (п, р+1)-го операционного бло- этом в операционном блоке 2, форми-ка, первый информационный выход (1, руется значение , в опера-п)-го операционного блока является ционный блок 2 г, в регистр 11 записы- (1-1)-м выходом устройства, а выход

35

рой {шформационный выход (п, j)-ro операционного блока подключен к информационному входу (п+1, j)-ro регистра, выход (п+1, р)-го регистра подключен к первому информационному

вается значение а J , в регистр 3

40

значение

41

31

На четвертом такте в регистр 3

(О

Э

записывается .значение Ь ,, , в опера- циоином блоке 2,i формируется значе(п+1, п)-го регистра - п-м выходом устройства, группа настроечных входов которого подключена к группе настроечных входов (I, 1)-го операционного блока, первая группа настроил v,/ nnwn UJIWAC IX J Jnn у С I п пачс. f jrinvji j , i jriiiia now i | v

ние b,i /aj , в операционном блоке ечных выходов (2, i)-ro операционijj в регистр 25 записывается значение bj, .

На пятом такте в операционном блоке

ного ьлока подключена к группе настроечных входов (1, i+l)-ro операционного блока, а группа настроеч2 формируется значение b l/a2j . CQ ных выходов (I, j)-ro операционного

в операционном блоке 2. значениеблока - к группе настроечных входов

Ь. (b2, /э 42./7 которое подается(2, j) -го операционного блока,

на выход 5 устройства.группа настроечных входов (k+l, j)-ro На шестом такте в операционном бло- операционного блока подключена к втоке 2jj формируется значение ,рой группе настроечных выходов (k,

в регистр . записывается значениеj)-ro операционного блока, синхроЬ . При этом значения Ь , пода-вход устройства подключен к синхроются соответственно на вы;:оды 5 ивходам всех операционных блоков,

5я.причем операционный блок первой групр)-го операционного блока (,п

(k+1, j)-ro операционного блока, вто

входу (п, р+1)-го операционного бло- ка, первый информационный выход (1, п)-го операционного блока является (1-1)-м выходом устройства, а выход

35

рой {шформационный выход (п, j)-ro операционного блока подключен к информационному входу (п+1, j)-ro регистра, выход (п+1, р)-го регистра подключен к первому информационному

входу (п, р+1)-го операционного бло- ка, первый информационный выход (1, п)-го операционного блока является (1-1)-м выходом устройства, а выход

40

(п+1, п)-го регистра - п-м выходом устройства, группа настроечных входов которого подключена к группе настроечных входов (I, 1)-го операционного блока, первая группа настро. f jrinvji j , i jriiiia now i | v

ечных выходов (2, i)-ro операционного ьлока подключена к группе настроечных входов (1, i+l)-ro операционного блока, а группа настроечных выходов (I, j)-ro операционного

ы содержит первый и второй регистры, ервый элемент И, первый триггер и зел вычисления обратной величины исла, вход которого соединен с выхоом второго регистра, информационный вход которого соединен с первым информационным входом операционного блока первой группы и с информацинным входом первого регистра, синх- jg ровход которого соединен с выходом первого элемента И, первый и второй входы которого соединены соответственно с синхровходом и первым входом группы настроечных входов one- j рационного блока первой группы, вход первого триггера соединен с вторым входом первого элемента И, синхро- Бход операционного блока первой группы соединен с синхровходом первого 20 триггера, выход которого соединен с первым выходом группы настроечных операционного блока первой группы, причем операционный блок второй группы содержит первый, второй 25 и третий регистры, первый триггер, умножитель и сумматор, первый информационный вход которого соединен информационными входами второго и третьего регистров, а второй инфор- зО мационный вход с информационным входом первого регистра, выход которого соединен с первым входом умнояси- теля, второй вход которого соединен с выходом второго регистра, а выход - ,, с первым входом сумматора, синхро- вход операционного блока второй группы соединен с синхровходами первого регистра и первого триггера, вход которого соединен с первым входом до группы настроечных входов операционного блока второй группы, отличающееся тем, что, с целью повышения быстродействия, в операционный блок первой группы введены ум- дЗ ножитель, второй элемент И, первая и вторая группы элементов И, элемент Ш1И-НЕ, группа элементов И, второй триггер, вход которого подключен к второму входу группы настроечных вхо- J.Q дов операционного блока первой группы и к первому входу второго элемента И, выход которого соединен с синхровходом второго регистра, а второй вход - с синхровходами операционного блока первой группы и второго триггера, выход которого подключен к второму выходу группы настроечных выходов

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

1527643

Таблица 1

10

CPU г. г