Матричное вычислительное устройство

 

МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО, состоящее из матрицы вычислительных ячеек, причем первый и второй управляющие входы вычислительной ячейки в i-й строке и j-м столбце (i 1, 2, ..., п, j 1, 2,...,п, где п - разрядность устройства ) соединены соответственно с первым и вторым управляющими выходами вычислительной ячейки в этой же строке и (j-l)-M столбце, второй управляющий вход каждой вычислительной ячейки в первом столбце соединен через инвертор с первым управляющим входом этой же вычислительной ячейки и является входом первой группы входов матрицы, первый и второй входы переноса вычислительной ячейки в i-й строке и j-м столбце соединены соответственно с первым и вторым выходами переноса вычислительной ячейки в этой же строке и (j + 1)-м столбце, первый и второй входы переноса каждой вычислительной ячейки последнего столбца соединены соответственно с первым и вторым управляющими выходами этой же вычислительной ячейки, первый и второй входы слагаемого-вычитаемого вычислительной ячейки в i-й строке и j-м столбце соединены соответственно с вторым и первым выходами суммы вычислительной ячейки в (i-1)-й строке и (j-i+1)-M столбце, первый и второй входы слагаемого-вычитаемого вычислительных ячеек в i-й строке и j-м столбце, начиная с первого и последовательно до i-ro, соединены соответственно с вторым и первьм вмходами суммы вычислительной ячейки в (i-1)-й строi ке и первом столбце, первый и втоСЛ рой входы слагаемого вычислительной ячейки в i-й строке и j-м столбце соединены соответственно с первым и вторым выходами суммы вычислительной ячейки в (i-1)-й строке и этом же столбце, первый и второй входы слагаемого каждой вычислительной ячейки первой строки соединены соответсо го ственно с вторым и первым входами слагаемого-вычитаемого этой же вы4 числительной ячейки и являются вхоСО дами второй и третьей группы входов матрицы соответственно, первый и второй выходы суммы каждой вычислительной ячейки последней строки являются соответственно выходами первой и второй группы выходов матрицы , отличающееся тем, что, с целью повышения быстродействия , первой и второй выходы суммы вычислительной ячейки матрицы в И-и строке и j-м столбце, где равно наибольшему целому от половины номера последнего столбца.

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

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

РЕСПУБЛИН (19) (11) 3(51) С Oe F 7/548

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

H ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3538977/18-24 (22) 17.01.83 (46) 15.05.84. Вюл. )1 18 (72) Л.А. Шумилов, А.И. Суейдан (Иордания), И.С. Зуев и А.М. Турсунканов (71) Ленинградский ордена Ленина электротехнический институт им. В.И. Ульянова (Ленина) (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

Ф 913826, кл. G 06 F 7/548, 1979.

2. Авторское свидетельство СССР по заявке N - 3302495, кл. G 06 F 7/548, 1982 (прототип). (54)(57) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ

УСТРОЙСТВО, состоящее из матрицы вычислительных ячеек, причем первый и второй управляющие входы вычислительной ячейки в i-й строке и j ì столбце (i = 1, 2, ..., и, j = 1, 2,...,n где n — разрядность устройства) соединены соответственно с первым и вторым управляющими выходами вычислительной ячейки в этой же строке и (j-1)-м столбце, второй управляющий вход каждой вычислительной ячейки в первом столбце соединен через инвертор с первым управляющим входом этой же вычислительной ячейки и является входом первой группы входов матрицы, первый и второй входы переноса вычислительной ячейки в i-й строке и j ì столбце соединены соответственно с первым и вторым выходами переноса вычислительной ячейки в этой же строке и (j + 1)-м столбце, первый и второй входы переноса каждой вычислительной ячейки последнего столбца соединены соответственно с первым и вторым управляющими выходами в этой же вычислительной ячейки, первый и второй входы слагаемого-вычитаемого вычислительной ячейки в

i-й строке и j ì столбце соединены соответственно с вторым и первым выходами суммы вычислительной ячейки в (i-1)-й строке и (j-i+1)-м столбце, первый и второй входы слагаемого-вычитаемого вычислительных ячеек в i-й строке и j è столбце, начиная с первого и последовательно до i-ro соединены соответственно с вторым и первым выходами суммы вычислительной ячейки в (i-1)-й строке и первом столбце, первый и второй входы слагаемого вычислительной ячейки в i — и строке и j ì столбце соединены соответственно с первым и вторым выходами суммы вычислительной ячейки в (i-1)-й строке и этом же столбце, первый и второй входы слагаемого каждой вычислительной ячейки первой строки соединены соответственно с вторым и первым входами слагаемого-вычитаемого этой же вычислительной ячейки и являются входами второй и третьей группы входов матрицы соответственно, первый и второй выходы суммы каждой вычислительной ячейки последней строки являются соответственно выходами первой и второй группы выходов матрицы, отличающееся тем, что, с целью повышения быстродействия, первой и второй выходы суммы вычислительной ячейки матрицы в 0 -й строке и j ì столбце, где 1 равно наибольшему целому от половины номера последнего столбца, 109 497 це. где соединены соответственно с вторым и первым входами слагаемого-вычитаемого вычислительных ячеек в ((+K) é строке и (E +K+j — 1)-м столбце

И (к = 1, 2, 3, ...,.т, где W< 2), а первый и второй входы слагаемоговычитаемого вычислительных ячеек

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

Известны матричные вычислительные устройства, вычисляющие функции

sin9 и cos Ч по методу "цифра за цифрой и состоящие из двух матриц.

Алгоритм вычисления функций sin 9 и cos 9 по методу- "цифра за цифрой" имеет вид

Этап 1 9, д, р дгс 2-1

Этап 2 х = х — 2" у

У q ++q= У; + где х. — у. — текущие координаты вектора; х„, у — конечные координаты вектора, n — число итераций.

Начальные условия: 6 о = 9, х =1 !1

Уо

Матричные вь1числительные устройства для вычисления функций я пМ и cos (состоят иэ двух мат— риц. Первая матрица вычислительных ячеек выполняет первый этап алгоритма и вырабатывает значения управляющих сигналов . Поэтому ее це11 лесообраэно назвать управляющей.

Вторая матрица вычислительных ячеек выполняет второй этап алгоритма, т ° е. вычисляет значения х = cos 4 и и у „= sin (, и ее целесообразно назвать вычисляющей. управляющая и вычисляющая матрицы могут иметь в (9+К)-й строке и.столбце, начиная с первого последовательно до (0+K+j-1)-го,„соединены соответственно с вторым и первым выходами суммы вычислительной ячейки в - -й строке и первом столб2 различные варианты исполнения, причем каждый вариант у множества управляющих матриц может быть объединен с одним из вариантов из множест—

5 ва матриц, вычисляющих в матричное вычислительное устройство (1 |и 1.2).

Недостатком этих устройств является их низкое быстродействие.

Наиболее близким к изобретению по технической сущности является матричное вычислительное устройство Г 2 1

Основным недостатком этого матричного вычислительного устройства является малое быстродействие ее вычисляющей матрицы.

Цель изобретения — повышение быстродействия вычисляющей матрицы матричного вычислительного устройства.

Поставленная цель достигается тем, что матричное вычислительное устройство, состоящее из матрицы вычислительных ячеек, причем первый и второй управляющие входы вычислительной ячейки в 1-й строке и

j è столбце соединены соответственно с первым и вторым управляющими выходами вычислительной ячейки в этой же строке и (j — 1)-м столбце, 30 второй управляющий вход каждой вычислительной ячейки в первом столбце соединен через инвертор с первым управляющим входом этой же вычислительной ячейки и является входом

З5 первой группы входов матрицы, первый и второй входы переноса вычислительной ячейки в 1-й строке и

j-м столбце соединены соответственно с первым и вторым выходами перено40 са вычислительной ячейки в этой же строке и (1+1)-м столбце, первый и второй входы переноса каждой вычислительной ячейки последнего столб10924

5

3 ца соединены соответственно с первым и вторым управляющими выходами этой же вычислительной ячейки, первый и второй входы слагаемого †вычитаемого вычислительной ячейки в

i-й стрбке и j-м столбце соединены соответственно с вторым и первым выходами суммы вычислительной ячейки в (i-1)-й строке и (j-i+1)-м столбце, первый и второй входы слагаемого-вычитаемого вычислительных ячеек в i-й строке и j-м столбце, начиная с первого и последовательно до i-го, соединены соответственно с вторым и первым выходами суммы вычислительной ячейки в (i-1)-й строке и первом столбце, первый и второй входы слагаемого вычислительной ячейки в i é строке и j ì столбце соединены соответственно с первым и вторым выходами суммы вычислительной ячейки в (i-i)-й строке и этом же столбце, первый и второй входы слагаемого каждой вычислительной ячейки первой строки соединены соответственно с вторым и первым входами слагаемого-вычитаемого этой же вычислительной ячейки и являются входами второй и третьей группы входов матрицы соответственно, пер30 вый и второй выходы суммы каждой вычислительной ячейки последней строки являются соответственно выходами первой и второй группы выходов матрицы, в вычислительной матрице первый и второй выходы суммы вычислительной ячейки в -й строке и

j-м столбце, где 0 равно наибольшему целому от половины номера последнего столбца, соединены соответственно

40 с вторым и первым входами слагаемого-вычитаемого вычислительных ячеек в (Я+К)-й строке и (0+K+j-t)-м столбце, а первый и второй входы слагаемого-вычитаемого вычислительных ячеек в ((+К)-й строке и столбце, на45 чиная с первого последовательно до (11+К+)-1) -ro, соединены соответственно с вторым и первым выходами суммы вычислительной ячейки в -й строке и первом столбце.

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

Вычисляющая матрица (фиг. 1 и 2) содержит вычислительные ячейки 1, первую — третью группы входов 2, 3

97 4 и 4, выходы 5 и 6, первую и вторую группы выходов 7 и 8.

Согласно варианту исполнения вычислительная ячейка 1 содержит два сумматора 9 и 10 по модулю два, два сумматора 11 и 12, входы 13-20, выходы 21-26.

Вход 14 вычислительной ячейки

1 в i-й строке и первом столбце соединен череэ инвертор с входом 13 этой же вычислительной ячейки с входом группы входов 2 вычисляющей матрицы. Входы 17 и 18 каждой вычислительной ячейки первой строки соединены соответственно с входами

16 и 15 этой же вычислительной ячейки и соответственно с входами групп входов 3 и 4 вычисляющей матрицы, входы 13 и 14 вычислительной ячейки в -й строке и 1-м столбце соединены соответственно с выходами

21 и 22 вычислительной ячейки в этой же строке и (j-1)-м столбце, входы 19 и 20 вычислительной ячейки в i-й строке и j ì столбце соединены соответственно с выходами 23 и 24 вычислительной ячейки в этой же строке и (j+ 1) ì столбце, входы 19 и 20 каждой вычислительной ячейки последнего столбца соединены соответственно с выходами 2 1 и 22 этой вычислительной ячейки, входы 15 и 16 вычислительной ячейки в 1-й строке (i c Х, 1 — наибольшее целое от половины номера последнего столбца) и j-м столбце соединены соответственно с выходами 26 и 25 вычислительной ячейки в (i-1)-й строке в (j-i+1) — м столбце, входы 15 и 16 вычислительных ячеек в i-й строке (i 6I) и столбце, начиная с первого последовательно до i — ro соединены соответственно с выходами 26 и 25 вычислительной ячейки в (i-1)-й строке и первом столбце, входы 17 и 18 вычислительной ячейки в i-й строке и j-и столбце соединены соответственно с выходами 25 и 26 вычислительной ячейки в (i-1)-й строке и этом же столбце, выходы 25 и 26 вычислительной ячейки в L -й строке и j-м столбце соединены соответственно с входами 16 и 15 вычислительных яче— ,ек в (0+К)-й строке и (Я+к+1-1)-м столбце, входы 15 и 16 вычислительных ячеек в (8+к)-й строке и столбце, начиная с первого последовательно до (1+к+3 †)-го, соединены соответственно с выходами 26 и 25 вы109221

8,)0 е -1 в (О

< 1

Этап 2 х. =х. - 2

i+1 1 1 1

7) 30

1+2

37 где

5 числительной ячейки в 0 -й строке и первом столбце, выходы 25 и 26 каждой вычислительной ячейки последней строки соединены соответственно с выходами 7 и 8 групп выходов вычисляющей матрицы.

Вычисляющая матрица входит в состав матричного вычислительного устройства, вычисляющего элементарные функции sin4 и cos 9 по методу 10 цифра за цифрой".

Рекуррентные соотношения, описывающие алгоритм "цифра за цифрой" для функций sin Чи cosA следующие:

Этап 1 „ „=В; -а С1 7 2

% и, число шагов итерации, z . .м, — текущие координаты векто1. И1 ра; у„ — конечные координаты вектора.

Начальные условия 8 = M „ xo

=1/К; у = О, где К вЂ” коэффициент деформации вектора, зависящий только от числа шагов итераций.

Результаты вычислений у и = з п (, х„= cos ет

Вычисляющая матрица выполняет второй этап алгоритма и работает сле10 дующим образом.

На входы 17 и 18 вычислительных ячеек 1 первой строки матрицы подаются соответственно значения начальных условий у и х, на вход 14 о о 4.7 вычислительных ячеек 1 первого столбца подаются управляющие сигналы вырабатываемые управляющей матрицей матричного вычислительного устройства. Каждая строка вычислительных ячеек матрицы выполняет две опера50 ции алгебраического суммирования.

Как видно из алгоритма вычисления, на выходах 25 и 26 вычислительных ячеек -й строки получаются соответственно значения sin4 и cos< с точностью до 2 (1). Следовательно, на выходах 25 и 26 вычислительи Г ных ячеек 0 = 1 — 1 строки получают.1ZL ся значения Йпе и cos Y с точностью до 2 . Таким образом, после

К-й итерации (на выходах f?-й строки) получаются первые 0 — правильные разряды значений вычисляе1ых функций, где первый разряд знаковый.

Поэтому будет справедливо соотношение

-(1 -1l

У д+ К = Уе7+ К-1+ Е+ К-1 2 "e

- е -ч

Хl7+l = Xе7+К 1 (g+К уе где C=) — "(,К = 1, 2, . ° .

Исходя из этого, входы 15 и 16 вычислительной ячейки в д-й строке (i ) X) и j ì столбце можно соединить соответственно с входами 15 и 16 вычислительной ячейки в 1 -й строке и (j-i+1)-м столбце, а входы

15 и 16 вычислительных ячеек в

i-й строке (i 9 ) и j ì столбце (1 < j (i) соединить соответственно с выходами 26 и 25 вычислительной ячейки в Р -й строке и первом столбце. С учетом того, что управляющие сигналы, „, ° . °, „,на вычисляющую матрицу прототипа приходят одновременно, временные затраты на вычисляющую матрицу сокращаются на величину п-1- и+0+1

lit =(n«L ) t +(n-0) t - и-Е -1-t}t - --е)(п-е1р -<е- lt

1 п время формирования суммы одноразрядным двоичным сумматором; время формирования переноса одноразрядным двоичным сумматором; разрядность операндов, Очевидно, что временные затраты вычисления матричным вычислительным устройством, состоящим из данной вычисляющей матрицы и управляющей матрицы матричного вычислительного устройства f 2) сокращаются на величину Д t, равную

Dt=P 1n-е1 1е-tlt (-4

Матричное вычислительное устройство, содержащее предлагаемую вычисляющую матрицу, эффективнее всего реализовывать в виде БИС. В настоящее время в СССР нет БИС, вычисляющих

7 функции s in 9 и cos М . Поэтому в качестве базового объекта для определения эффективности изобретения взят CORDIC, Арифметический процессор на кристалле (CAP-кристалл), созданный фирмой NOSC (NavaI Ocean

Systems Centre) CAP-кристалл вычисляет функции вида sin Ðи cosV по методу "цифра эа цифрой" (алгоритм

Волдера).

Время вычисления функций вида sin 9 и cos Q CAP-кристаллом для двадцатичетырехраэрядных данных (и = 24) составляет величину 7сдр= 23 (tcpg + tc) + 48 (t . +

+ tc) = 7t tc*6+ 71 с, А где C*S — время сдвига на разрядов вправо; — время суммирования двух двадцатичетырехразрядных операторов °

Матричное вычислительное устройство, состоящее из управляющей матрицы устройства E 2 3 и предлагаемой вычисляющей матрицы, вычисляет значения sin u cos за время, равное

1092497

8 Твв = 206 п +. 135 з + 5 нн+

+ 5 м

1 где t< — время формирования сигнала переноса одноразрядным

5 сумматором;

t — время формирования сигнала суммы одноразрядным сумматором;

С„н- время инвертирования сигIO нала;

t®<- время формирования суммы по по модулю два.

Время сс paBHO t с = 23 t „+ t> °

Значит TCAp= 71t CAB+ 1633tп+71tS

Так как t „ О, 5 t>, можно заключить, что CAP-кристалл вычисляет значения функций з пЧ и cosV не менее чем в 4 раза медленнее матричного вычислительного устройства, состоящего из предлагаемой вычисляющей матрицы и управляющей матрицы устройства Г 23.

Эффективность изобретения заключается в существенном повышении скорости вычислений значений функций sinY u cosт"

1092497

1092497

Заказ 3255/32 Тираж 699

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

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

Подписное

Филиал НПП "Патент", г. Ужгород, ул. Проектная, 4

Составитель В. Венцель

Редактор Л. Алексеенко Техред И.Метелева Корректор С. Шекмар