Матричное вычислительное устройство
Патент 824195
Авторы
Классы МПК
Матричное вычислительное устройство
Иллюстрации
Реферат
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Ссчсз Советски
Социалистическим
Республик
<111 824195 (61) ???????????????????????????? ?? ??????. ????????-????????” (22) ???????????????? 2506.79 (21) 2789832>
G 06 F 7/38 с присоединением заявки ¹â€”
Государственный комитет
СССР по делам изобретений н открытий (23) Приоритет
Опубликовано 23,04.81,Бюллетень N9 15 (З) УАК 681.325 (088.8) Дата опубликования описания 23,0431
Л.A. Шумилов, Али Абдалла Абдалла Дау
А.И. Суейдан и К.В. Декусар
1 :
)
Ленинградский ордена Ленина злектрот хничйский, институт имени В.И. ульянова (ЛениЖ)1
"-ч,,„ф, (72) Авторы изобретения (71) 3 а яв и тель (54 ) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО
Изобретение относится к вычислительной технике и может быть использовано в быстродействующих процессорах и специализированных. вычислительных устройствах.
Известны матричные вычислительные устройства для выполнения операции деления двоичных чисел (1).
Недостатками матричных вычислитель- О ных устройств являются ограниченные функциональные возможности при данном наборе узлов и связей между ними.
Наиболее близким к предлагаемому 15 по технической сущности является матричное вычислительное устройство для выполнения операции деления двойчных чисел, содержащее матрицу вычислительных ячеек, каждая из которых со- .20 держит сумматор по модулю два и одноразрядный сумматор (2 ).
Недостатком известного матричного устройства является ограниченные функциональные возможности, обеспечи- 25 вающие выполнение лишь одной арифметической операции деления двоичных чисел.
Цель изобретения - расширение функциональных возможностей устройства эа за счет вычисления дополнительных функций и=1 х з, з=ч!к, и =(х з 2/v, z = х-ят/у.
Поставленная цель достигается тем, что в матричное вычислительное устройство, содержащее матрицу вычислительных ячеек, каждая из которых содержит сумматор по модулю два и одноразрядный сумматор, причем в каждой вычислительной ячейке первый и второй входы вычислительной ячейки соединены соответственно с первым и вторым, входами сумматора по модулю два, выход которого соединен с первым входом одноразрядного сумматора, первый вход вычислительной ячейки соединен с первым выходом вычислительной ячей ки, третий и четвертый входы вычислительной ячейки соединены соответственно со вторым и третьим входами одноразрядного сумматора, первый выход которого соединен со вторым выходом вычислительной ячейки, а второй выход одноразрядного сумматорас третьим выходом вычислительной ячейки, второй вход вычислительной ячейки соединен с четвертым выходом вычислительной ячейки, причем первые
824195 выходы вычислительных ячеек каждого столбца матрицы соединены соответственно с первыми входами вычислительных ячеек предыдущего столбца тех же строк матрицы, вторые выходы вычислительных ячеек каждой строки матрицы соединены соответственно с третьими входами вычислительных ячеек последующей строки тех же столбцов матрицы, третьи выходы вы числительных ячеек каждого столбца матрицы .соединены соответственно с четвертыми входами вычислительных ячеек последующего столбца. тех же строк матрицы, четвертые выходы вычислительных ячеек каждой строки матрицы соединены соответственно со вторыми входами вычислительнЫх ячеек последующей строки предыдущих столбцов матрицы, первый выход и четвертый вход вычислительной ячейки младшего разряда каждой строки матрицы соеди- 20 иены между собой, причем вторые входы вычислительных ячеек первой строки матрицы соединены с первыми входами устройства, третьи входы, вычислительных ячеек первой строки матрицы соединены со вторыми входами устройства, дополнительно введены п элементов НЕ и вторая матрица вычислительных ячеек, причем первый вход вычислительной ячейки старшего разря- З да каждой строки первой матрицы соединен с входом соответствующего элемента НЕ и с третьим выходом вычислительной ячейки старшего разряда предыдущей строки второй матрицы, выходы элеэлементов НЕ соединены с первыми выходами соответствующих вычислительных ячеек старшего разряда последующей строки второй матрицы, причем вторые и третьи входы вычислительных ячеек первой строки второй матрицы 40 соединены соответственно с третьими и четвертыми входами устройства, первый вход вычислительной ячейки старшего разряда первой строки первой матрицы вычислительных ячеек соеди- 4 нен с пятым входом устройства, вторые входы вычислительных ячеек старших разрядов каждой, кроме первой, строки первой и второй матрицы соединены входами устройства, вторые yi выходы вычислительных ячеек последней строки первой матрицы соединены с выходами устройства, причем число строк первой и второй матрицы равно числу их столбцов °
Матричное вычислительное устройство выполняет операцию деления и вы числения следующих функций
u =zx(v, v =ibex, u =(x ч piv, z=(x-ч) /v 60 и работают по разностно вЂ,итерацион-. ному методу.
Для реализации операции u=z ° х/у подбирается для знаменателя и одного из сомножителей такой общий для них множитель — (<+< ) о
I что он приблизит значения знаменателя к величине, равной второму сомножителю числителя, и во столько же раз изменит значение числителя ° В результате имеют место следующие равенства
ao -(i+%)
3„. =ч ч Y.q- 2,., Ф
Ограничиваясь первыми членами ряда суммы и пренебрегая погрешностью аУ<2 ("+1) можем считать, что на (i+1)-й итерации преобразованный знаменатель У(+1 окажется равным 2.
Тогда значение т.. 2 (+1) ч найден ное из (1 ) и подставленное в (2), даст х. = z —.
Х
Таким образом, следствием устремления Y Z является устремление х - о.
Итерационный процесс проводится по следующему алгоритму
Х;., = X, +q. x g
-(11-1)
1.8,ÅÑËÞ „ О, -1,есаул „« останов,ест „=о
-(":+1)
%„ч с начальными условиями Х, =х,у =V, y = 2-Ч. "
Для реализации операции у=1/х подбирается для х такой множитель
W= + Z,q,.2 ("" . о который при соответствующем подборе операторов ц; а -1,+1) устремляет значение аргумента х к величине, равной единице
Воздействовав этим же итерационным процессом с тем же законом изменения знака оператора q. на изменение ве1 личины функции и приняв за ее начальное значение Y--1, получим следующее выражение для приближения искомой функции. ч„-.q+ g+,-(+ ) (ц
О 1
Ограничиваясь первыми членами ряда суммы и пренебрегая погрешностью
824195 у1 Ч Х 1 Е у 2 (s) Требуя, чтобы limx> =2 у, приближение ойеранда стремится принять эна10 чение, равное искомой зависимости, т.е. 1im y z. Алгоритм вычисления зависимости вытекает из (7) и !8) и описывается следующими соотношениями
Х =Х.-Ч У2 (1+
1+1
У„+„=Ч„.+% Х2 1 +1=. -„-Ф„Ч 2 " ", с начальными условиями х =х, у„1, z =1-х о
Я
Для реализации операции О=(А-у )/у подбираются к операндам х и у такие коэффициенты 20
4,(Ч Е 2 (i11) о 1
1, 11 «Ь - -(1«1)
25 которые смогли бы .в ходе итерационного процесса приблизить операнд х нулю с наперед заданной погрешностью дх42 ", где п — число итераций.
Значения операндов с учетом выбран-З0 ных коэффициентов .kx u kz могут быть выражены соотношениями
Х =Х-у тс(,2 (1+", (5)
Ч„. =У+ Х Z, 2 <11+ 11 3 (6) 35 о
Определяя значение суммы в (5) из условия х - О и подставляя результат в (6), приходим к выводу, что следствием стремления х. Î является у -«и=(х +40 1
1 1
+у )/у. Здесь необходимо выполнение условия у О.
Итерационный процесс вычисления данной операции описывается следующими соотношениями — (1+1) х1«1=Х„- „Ч 2, Хн-во, .".— .Ч2-(11 " бб 1
- »„,.....,.. останов,клн z „. =о с начальными условиями х х ч =ч;. о о @ x ° 55
Для реализаций операции z (x-у) уу наложим на итерационный процесс изменения операндов х и у закон изменения равных множителей вида
У- „=Ч-++. X2. М = =4-2с -2
1-1 +1 а 5
Приближение операнда х будем.рассматривать как сумку исходного значения операнда х и приближения операн» 65 ах 2 ", можно считать, что на («1)-й итерации преобразованное значение аргумента х окажется равным единице. Тогда значение коэффициента, найденное из (3) и подставленное в (4), дает у=1/х.
Итерационный процесс вычисления данной операции описывается следующими соотношениями
У -,„=Ч„« .Ч2 (1+1) х =х-+-.-x2 ("")
"+1 1 у«
q; = Ь1Р, . =1« е » 1; -О, (-4,если z„.<о, т ° =х.-%.х2 (" 1>
1+1 1 %1 да Y а приближение операнда как разность исходного значения операнда Y и приближения операнда х.
1 бб. =Х. I(1- Ксб. 2- "" (б ) «1,если ц О, и 1 Ы И
-1,еслч ц <О, останов, если f<. =о с начальными условиями х =x+y, у о о
=y x =0,5 x y
На фиг. 1 изображена структурная схема вычислительной ячейки устройства, на фиг. 2 — блок-схема матрич ного вычислительного устройства .
Каждая вычислительная ячейка содержит сумматор 1 по модулю два, одноразрядный сумматор 2, первый, второй, третий и четвертый входы 3-6, первый, второй, третий и четвертый выходы 7-10. Матричное вычислительное устройство содержит первую и вторую матрицы 11 и 12 вычислительных ячеек, вычислительные ячейки 13, и элементов НЕ второй матрицы .14, первые и вторые входы 15 и 16 устройства, третьи и четвертые входы 17 и 18 устройства, пятый вход 19 устройства и выходы 20 устройства, шестые входы
21 устройства.
Матричное вычислительное устройство работает следующим образом.
Каждая из матриц выполняет вычисление по рекуррентному отношению типа б где х и у - операнды, поступающие на входы матрицы;
q. — элемент, определяющий тип выполняемой операции (сложе-. ние или вычитание). образуется на третьем выходе вычислительной ячейки старшего разряца i-й строки второй матрицы 12 и определяет тип выполняемой операции в последующей строке обеих матриц.
Если ц =О, то в последующей строке
:т Ф первоЦ матрицы выполняется операция вычитания, а в последующей строке второЯ матрицы — операция сложения и наоборот, если <ц =1, то в последующей строке второй матрицы выполня824195 ется операция сложения, а в последующей строке первой матрицы — операция вычитания. Сдвиг одного из операндов вправо на (i+1) разрядов (что соответствует умножению на 2 ("»" ) осуществляется
5 внутриматричными соединениями..
При выполнении всех перечисленных зависимостей устройство работает по единому алгоритму и отличие состоит только в начальных условиях.
При вычислении зависимости uz,х/у на входы 15-18 устройства подаются соответственно значения операндов 0,5хо; хо, 0,5уо 4о х> х, уо у, Цуа-.у, На вход 19 подается потенциал, соответствующий знаку Я>, т.е. если знак 5
Я> отрицателен, то подается единичный потенциал, и если знак положительный, то подается нулевой потенциал. На выходе 20 получаем значение результата 0 x/у. Операция деления 20
lsz/у выступает как частный случай вычисления зависимости U =X г/у. Для этого нужно взять х--0,5, а значение
Y взять как 0,5у, в результате полу чаем значение )= /у. 25
Для вычисления зависимости У=1/х. на входы 15-18 подаются соответственно следующие значения 0 5у ; у,, О 5хо о где у О 5 хо=х; z+0>5-х °
На вход., 19 подается потенциал, соответствующий знаку 7о . На выходе 20 получаем значение результата ч =1/х.
Для вычисления зависимости u=(x +
+у )/у на входы 15-18 подаются соответственно значения 0,5хо, уо, 0,5x ° о "о=x уо=у о=х. На вход
19 подается сигнал, соответствующий знаку zp. На выходе 20 получаем значение результата u = (xz+y. ) /у, . Для вычисления зависимости z (x-у) /у на входы 15-18 подаются сост- 40 ветственно значения О, 5х ;у; О, 5уо,. хо=х+у;у0 =у-х; z =0,5-у. На вход 19 подается потенциал, соответствующий знаку zo. Ha выходе 20 получаем значение результата z=(x-y)z/y.
На входы 21 всегда подается нулевой потенциал.
Эффективность изобретения заключается в расширении функциональных возможностей матричного вычислительного устройства по сравнению с известным за счет выполнения вычислений дополнительных операций и=zK(Jj >ч/к; ц=(Ду )(ч;
2 =(Х-S) /У- 55 формула изобретения
Матричное вычислительное устройство, содержащее матрицу вычислитель ных ячеек, каждая из которых содер1 ит сумматор по модулю два и однораз- д) рядный сумматор, причем в каждой вычислительной ячейке первый и второй входы вычислительной ячейки соединены соответственно с первым и вторым входами сумматора по модулю два, выход которого соединен с первым входом одноразрядного сумматора, первый вход вычислительной ячейки соединен с перВЫМ ВЫХОДОМ ВЫЧИСЛИ.ЫЛЬНОй яЧЕйКИ, третий и четвертый входы вычислительной ячейки соединены соответственно со вторым и третьим входами одноразрядного сумматора, первый выход которого соединен со вторым выходом вычислительной ячейки, а второй выход одноразрядного сумматора - с третьим выходом вычислительной ячейки, второй вход вычислительной ячейки соединен. с четвертым выходом. вычислительной ячейки, причем первые выходы вычислительных ячеек каждого столбца матрицы соединены соответственно с первыми входами вычислительных ячеек предыдущего столбца тех же строк матрицы, вторые выходы вычислитель.ных ячеек каждой строки матрицы соединены соответственно с третьими входами вычислительных ячеек последующей строки тех же столбцов матрицы, третьи выходы вычислительных ячеек каждого столбца матрицы соединены соответственно с четвертыми входами вычислительных ячеек последующего столбца тех же строк матрицы, четвертые выходы вычислительных ячеек каждой строки матрицы соединены соответственно со вторыми входами. вычислительных ячеек последующей строки предыдущих столбцов матрицы, первый выход и четвертый вход вычислительной ячейки младшего разряда каждой строки матрицы соединены между собой, причем вторые входы вычислительных ячеек первой строки матрицы соединены с первыми входами устройства, третьи входы вычислительных ячеек первой строки матрицы соединены со вторыми входами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей матричного вычислительного устройства за счет вычисления дополнительных функций вида
2.Х!у, >/Х, (X +у )/у, (х- >) I y в него дополнительно введены о элементов НЕ и вторая матрица вычислительных . ячеек, причем первый вход вычислительной .ячейки старшего разряда каждой строки первой матрицы соединен со входом соответствующего эле" мента НЕ и с третьим выходом вычислительной ячейки старшего разряда предыдущей строки второй матрицы, выходы элементов НЕ соединены с первыми выходами соответствующих вычислительных ячеек старшего разряда последующей строки второй матрицы, причем вторые и третьи входы вычислительных ячеек первой строки второй матрипь> соединены соответственно с третьим и четвертым входами устройст10
8?4195
Фиа!! б 16
Фиг. Г
Составитель В. Венцель
Редактор A. Шишкина Техред А. Ач Корректор Н. Вабинец
Заказ 2112/71 Тираж 745 Подписное, ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 ва, первый вход вычислительной ячейки старшего разряда первой строки пер- вой матрицы вычислительных ячеек соединен с пятым входом устройства, вторые входы вычислительных ячеек старших разрядов каждой, кроме первой, строки первой и второй матрицы соеди нены с шестыми входами устройства, вторые выходы вычислительных ячеек последней строки первой матрицы соединены с выходами устройства, причем число строк первой и второй матрицы равно числу их столбцов.
Источники инФормации, принятые во внимание при экспертизе
1. Guild Н. Same Cellular Logic
Arrays for Non-Restoiing Вinary Di vision, "The Radio and Electronic Eng", 1970, 39, Р б, р. 345-348.
2. Najithi а T,Ñ, Nourestorinq
Binary Division Usinq à Cellular Array, "Eiectronic Letters", 1970, б, М 10, р. 303-309 (прототип).