Устройство для реализации алгоритма волдера

 

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМА ВОЛДЕРА, содержащее п последовательно соединенных ячеек, где п разрядность устройства, каждая из которых содержит первыр, второй и третий регистры, первый, второй и третий сумматоры-вычитатели, первый, второй и третий коммутаторы, причем выходы младших разрядов первого,второго и третьего регистров соединены с первыми информационными входами соответственно первого, второго и третьего сумматоров-вычитателей, выходы первого и второго.коммутаторов соединены с вторыми информационными входами соответственно первого и второго сумматоров-вычитателей, выходы первого , второго и третьего сумматоров-вычитателей 1 -и ячейки (где 1, 2, 3, ...,п) соединены с информационными входами соответственно первого, второго и третьего регистров

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

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

РЕСПУБЛИН (19) (11) 3©g G 06 F 7/544

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

К ABTOPCHOMV СВИДЕТЕЛЪСТВУ

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

r10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3559838/18-24 (22) 24. 02. 83 (46) 23.09.84. Бюл. N 35 (72) А.А.Мельник (53) 681.3(088.8) (56) 1. Оранский А.И. "Аппаратные методы в цифровой вычислительной технике". Минск, 1977, БГУ, с. 132, рис. 5. 19.

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

1(- 813423, кл. G 06 F 7/548, 1981 (прототип). (54)(57) УСТРОйСтВО дЛя РБАпичА1дд

АЛГОРИТМА ВОЛДЕРА содержащее и последовательно соединенных ячеек, где и разрядность устройства, каждая из которых содержит первый, второй и третий регистры, первый, второй и тр етий сумматоры-вычитатели, первый, второй и третий коммутаторы, причем выходы младших разрядов первого, второго и третьего регистров соединены с первыми информационными входами соответственно первого, второго и третьего сумматоров-вычитателей, выходы первого и второго. коммутаторов соединены с вторыми информационными входами соответственно первого и второго сумматоров-вычитателей, выходы первого, второго и третьего сумматоров-вычитателей < -й ячейки (где 1=1, 2, 3, ...,и) соединены с информационными входами соответственно первого, второго и третьего регистров (1+1)-й ячейки, входы первого, второго и третьего регистров первой ячейки соединены соответственно с первым, вторым и третьим входами записи операндов устройства, информационные выходы первого и второго сумматоров-вычитателей п и ячейки соединены соответственно с первым и вторым выходами результата устройства, о т л и ч а ющ е е с я тем, что, с целью с окращения затрат оборудования, устройство содержит блок управления, каждая ячейка содержит кольцевой регистр, с первого по шестой триггеры, причем единичные входы первого, второго и третьего триггеров соединены с выходами переноса соответственно первого, второго и третьего сумматоров †вычитателей, управляющие входы которых соединены с информационным выходом третьего коммутатора, третьи информационные входы первого, второго и третьего сумматоров-вычитателей соединены с единичными выходами соответственно первого, второго и третьего триггеров, единичные входы которых соединены с управляющими входами пер вого, второго регистров и кольцевого регистра, информационный вход которого соединен с выходом младшего разряда кольцевого регистра и вторым информационным входом третье го сумматора-вычитателя, установочные входы первого, второго и третьего триггеров соединены с нулевыми входами четвертого, пятого и шестого триггеров, единичные входы которых соединены с информационными входами соответственно первого, второго и третьего регистров, единичные выходы четвертого, пятого и шестого триггеров соединены с первыми информационными входами соответственно второго, первого и третьего коммутаторов, вторые информационные входы первого и второго коммутаторов соединены с выходом

1115049 (1+1)-го разряда соответственно вто. рого и.первого регистров, первый управляющий вход второго коммутатоФ ра соединен с вторым управляющим входом первого коммутатора, первый управляющий вход которого соединен с вторым управляющим входом второго коммутатора, второй информационный вход третьего коммутатора соединен с выходом пятого триггера, причем блок управления содержит генератор тактовых импульсов, триггер, элемент

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

1-й ячейки, причем управляющие входь, всех регистров и единичные входы пер» вого, второго и третьего триггеров 1 é ячейки соединены с выходом генератора тактовых импульсов блока управления, первый и второй управляющие входы третьего коммутатора 1 -й ячейки соединены соответственно с прямым и инверсным выходами триггера кода операций блока управления, первый управляющий вход первого коммутатора и второй управляющий вход второго коммутатора 1 -й ячейки соединены с прямым выходом 1 -ro разря- да сдвигового регистра блока управления, инверсный выход 1-ro разряда которого соединен с вторым управляющим входом первого коммутатора и первым управляющим входом второго коммутатора i-й ячейки, вход (n-1)-го разряда сдвигового регистра блока управления соединен с источником сигнала 1" и с пер— вым и вторым управляющими входами соответственно второго и первого коммутаторов первой ячейки, а второй и первый управляющие входы второго и первого коммутаторов первой ячейки подключены к шияе нулевого потенциала,информационный выход третьего сумматоравычитателя и-й ячейки соединен с третьим выходом результата устройства.

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

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

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

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

1р и три сдвигателя, à и-я ячейка содержит два сумматора, три регистра и два сдвигателя. Устройство работает по конвейерному принципу. В каждой

его ячейке, являющейся ступенью кон15 вейера, реализуется одна итерация алгоритма Волдера. При обработке массивов чисел быстродействие устройства достигает времени

1115049

1. г.м 1 км рг, где,„,, t — задержка информации соответственно п разрядным сумматором и коммутатором;

I — время записи информации в регистр.

Затраты оборудования .на устройство составляют

10 где первое, второе и третье слагаемые — соответственно число триггеров, одноразрядных сумматоров и коммута15 торов.

В устройстве производится обработка данных, представленных полнораэрядным кодами. Во многих случаях эти данные поступают в цифровое утс20 ройство поразрядно, что позволяет производить их переэарядную обработку (2).

Недостатком устройства является

25 большие затраты оборудования при по— разрядном поступлении обрабатываемых данных.

Цель изобретения — сокращение затрат оборудования.

Поставленная цель достигается тем

I что в устройство для реализации алгоритма Волдера, содержащее и после— довательно соединенных ячеек, где

П разрядность устройства, каждая из которых содержит первый, второй и 35 третий регистры, первый, второй и третий сумматоры-вычитатели, первый, второй и третий коммутаторы, причем выходы младших разрядов первого, второго и третьего регистров соединены 40 с первыми информационными входами соответственно первого, второго и третьего сумматоров-вычитателей, выходы первого и второго коммутаторов соединены с вторыми информационными 45 входами соответственно первого и второго сумматоров-вычитателей, выходы первого, второго и третьего сумматоров-вычитателей i-й ячейки (где

1, 2, 3, ..., n) соединены с информа- 50 ционными входами соответственно первого, второго и третьего регистров

1 (i+1)-1 ячейки, входы первого, второго регистров первой ячейки соединены соответственно с первым, вторым и 55 третьим входами записи операндов

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

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

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

10 входом третьего коммутатора i-й ячейки, прямой выход триггера блока управления соединен с первым управляющим входом третьего коммутатора

i-й ячейки, причем управляющие входы 15 всех регистров и единичные входы первого, второго и третьего триггеров i-й ячейки соединены с выходом генератора тактовых импульсов блока управления, первый и второй управляю- 20 щие входы третьего коммутатора 1 и ячейки соединены соответственно с прямым и инверсным выходами триггера кода операций блока управления, первый управляющий вход первого коммута- 2 тора и второй управляющий вход второго коммутатора 1-й ячейки соединены с прямым выходом i — ro разряда сдвигового регистра блока управления, инверсный выход х-го разряда которого Зр соединен с вторым управляющим входом первого коммутатора и первым управляющим входом второго коммутатора

i-й ячейки, вход (n-1) — ro разряда сдвигового регистра блока управления соединем с источником сигнала "1" и с первым и вторым управляющими входами соответственно второго и первого коммутаторов первой ячейки, а второй и первый управляющие входы второ-40

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

На фиг. 1 представлена блок-схема устройства для реализации алгоритма

Волдера; на фиг. 2 — функциональная схема i-й ячейки устройства; на фиг. 3 — функциональная схема блока управления; на фиг. 4 — временная диаграмма работы устройства.

Устройство (фиг. 1).содержит и последовательно соединенных ячеек 1 с входами 2-10, выходами 11-13, блок

14 управления с входами 15 и 16.

Каждая ячс.йка 1 ус тройс тва (фиг. 2} соде1>жит суммаTоры-вь>читатели 1 7-19, триггеры 20-25, с(и>игоньн регистры

26-28, кольцеp(й регистр 29, коммутаторы 30-32.

Блок 14 управленц» (фиг. 3) содержит генератор 33 тактовых импульсов, элемент HL, инвертор 34, сдвиговый регистр 35, триггер 36 кода операции, элемент И 37.

Входы 6 — 8 первой ячейки 1 соединены с входами устройства, выходы

11 — 13 каждой предыдущей ячейки соединены соответственно с входами 6 — 8 каждой последующей ячейки, входы

6 — 8 каждой ячейки соединены с входами соответственно триггера 23 и регистра 26, триггера 24 и регистра 27, триггера 25 и регистра 28, выходы регистров 26 — 28 соединены соответственно с первыми входами сумматоров

17 — 19, третьи входы которых соеди— иены с выходами триггеров 20 — 22, входы которых соединены с выходами данных сумматоров, вторые входы сумматоров, вторые входы сумматоров 17 и 18 соединены с выходами соответственно коммутаторов 30 и 31, первые информационных входы которых соединены с выходами триггеров 24 и 23, а вторые — с выходами i-х разрядов регистров 26 и 27, первые и вторые управляющие вход > коммутаторов 3 1 и 30 соединены соответственно с вхо.дами 10„, а коммутаторы 30 и 31 с входами 9„ ячейки, выходы триггеров

24 и 25 соединены с вторым и первым информационными входами коммутатора 32, выход которого соединен с управляющими входами сумматоров

17 — 19, второй вход сумматора 19 соединен с выходом и входом кольцевого регистра, управляющие входы триггеров 20-22 и регистров 26-29 соединены с входом ячейки 2, управляющие входы триггеров 23-25 соеди1 иены с входом ячейки 5 и с входами сбросов триггеров 20 — 22, первый и второй управляющие входы коммутатора 32 соединенны с входами ячеек

4-3, выходы данных сумматороо 17 — 19 соединены с выходами ячеек 11 — 13, выход генератора 33 тактовых импульсов соединен с входами 2 всех ячеек

1 устройства, с входом схемы 37 И и с входом инвертора 34, выход которого соединен с входом синхронизации сдвигового регистра 35, прямой! 115049 и инверсный выходы i-го разряда которого соединены соотнеTcTBeííî с входами 9 и 10 1-й ячейки 1 (i=-2, 3, ..., п), выход 1-го разряда сдвигового регистра 35 также соединен с 5 входом регистра, второй вход сброса которого соединен с входом генератора 33 и входом.15 устройства, вход

16 устройства соединен с входом триггера 36 кода операции, прямой и инверсный выходы которого соединены с входами 3 и 4 каждой ячейки 1 устройства, инверсный выход первого разряда регистра 35 соединен с вторым входом схемы 37 И, выход которой

1 соединен с входами 5 всех ячеек устройства, вход 9 первой ячейки соединен с источником "1", а вход 10 — с источником 0

В устройстве реализуется алгоритм

Волдера следующими соотношениями:

41.1. -1.

30 разом.

По входу 16 триггер 36 кода операции устанавливается в состояние 0 или "1". Если триггер 36 устанавливается в состояние "0", то в устрой в 45 стве будут выполняться операции, реализуемые по алгоритму Волдера, в котором „ зависит от знака f если же в со тояние "1" — от знака у,.

По входу 15 поступает сигнал, запус- 50 кающий генератор 15 тактовых импульсов. Импульсы из генератора 33 поступают на регистры и триггеры устройства. С каждым импульсом информация в регистрах устройства сдвигается на один разряд.

После поступления первых п импульсов в регистры 26 — 28 первой ячей1„c 1i

1 где g 1 — двоичные операторы, принимающие значения 11 или -1, которые зависят либо от знака у„-, либо от знака Т„

С; — ко нс та нты, вид которых определяется типом вычисляемых функций (для тригонометрических функций

С„=агсСд 2, для гиперболических 35

-1

C<=arth 2, для логарифмических и

-( зкспоненциальных с; =1п(1+2 );

i=1, 2, ..., и) (n — разрядность представления чисел).

Устройство работает следующим об- 40 ки 1 поразрядно, младшими разрядами вперед записынаются начальные значения х„, у„, Уо, вид которых определяется выполняемой операциеи. Сигнал поступающий по шине 9 с выхода первого разряда регистра 35, подключает входы сумматоров 17 и 18 через коммутаторы 30 и 3 1 к выходам соответственно регистров 27 и 26. На суммаTорах 17 — 19 производится сложение или вычи1ание (в зависимости от сиг нала, поступающего с выхода коммутатора 32), на их управляющие входы.

Данный сигнал зависит либо от содер— жимого триггера 24, либо от содержимого триггера 75, н которых записа— ны знаки соответственно у, и Ч „. За— лись знаковых ра зр ядов в указа нные триггеры производится импул ьсом, поступающим по шинс 5 (фиг. 3) .

На сумматоре 7 выполняется опера ция сложения (или вычитания) и-го разряда регистра 26 с разряло . регистра 27, на сумматоре 18 и -га разряда регистра 27 с разрядом регистра 26, на сумматоре 19 соответственно и -x разрядов регистров 28 и 29.

С приходом (и+1) -го импульса на управляющие входы регистров и триггеров устройства значения л чадших ра зрядов сумм, полученные на сумматорах 17 — 19 запишутся в первые разряды соответственно регистров 26 — 28 второй ячейки 1, а значения переносов из данных сумматоров запишутся соответственно в триггеры 20 и 22.

Одновременно в регистрах 26 — 28 произойдет сдвиг информации на один разряд вправо, а в их старшие разряды запишутся младшие разряды следующих операторов, подлежащие обработке. На сумматорах 17 вЂ,19 производится сложение (n-1)-х разрядов соответствую щих операндов и переносов из и-х разрядов.

С приходаи (п+2) -ro импульса в регистрах 26 — 28 второй ячейки 1 производится сдвиг информации на разряд вправо, полученные на сумматорах 17 — 19 значения записываются в пергые разряды регистров второй ячейки 1, а в регистрах первой ячейки 1 производится сдвиг информации на разряд вправо и запись вторых разрядов следующих операндов. Таким образом, на сумматорах !7 — 19 первой ячейки реализуются соответственно первое, второе и третье управле1115049

40 ния первой итерации алгоритма Волдера. При этом значение константы с„, предварительно записано в регистр 29 и поступает младшими разрядами вперед на сумматор 19 с циклическим 5 сдвигом в каждом такте.

После поступления в устройство

2 и импульсов результаты первой итерации над первыми операндами будут находиться в регистрах 26 — 28 второй ячейки 1, а в регистрах первой ячейки будут находиться вторые операнды. Во второй ячейке над первыми операциями поразрядно будет выполняться вторая итерация, аналогично первой, с тем отличием, что последние разряды значений х „ и у„ будут суммироваться соответственно со знаковыми разрядами у „ и х„. Это объясняется сдвигом приращения на разряд вправо. Знаковые разряды поступают на сумматоры 17 и 18 через коммутаторы 30 и 31 по сигналу 10 (фиг. 4).

В регистре 29 второй ячейки записана вторая константа. Поскольку данный регистр является кольцевым, то после поступления импульсов разряды константы в нем займут прежнее положение, В это время в первой ячейке над вторыми операциями выполняется первая ЗО итерация, результаты которой поразрядно поступают во вторую ячейку, на которой результаты второй итерации над первыми операндами поразрядно поступают в третью ячейку. 35

После поступления 3 и импульсов в третьей ячейке будет выполняться третья итерация над вторыми операн— дами, а- в первой ячейке — первая итерация над третьими операндами.

При этом в регистре третьей ячейки записана третья константа, а два последних разряда значений регистров

27 и 26 суммируются с содержимым соответственно триггеров 24 и 23, 45 в которые записаны по сигналам знаковые разряды значений у и х соответственно поступающим по шине 5 (фиг. 4).

В дальнейшем после поступления каждых последующих импульсов результаты из предыдущей ячейки 1 переписы.ваются в последующую ячейку 1.,При этом в каждой i-й ячейке 29 записана

i-я константа, а последние i разрядов (i=0,1, ...,n-1) регистров 26 и 27 суммируются соответственно с содержимым триггеров 24 и 23.

Для исключения влияния переносов, хранимых в триггерах 20-22, на резуль— таты сложения последующих операндов по шине 5 производится их сброс каждым п-м импульсов.

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

В блоке 14 управления после поступления и импульсов происходит сброс регистра 35, что позволяет на его выходах получать периодические сигналы.

Сигнал записи, поступающий по шине 5, формируется схемой 37 И, через которую сигналом 10 разрешается прохождение каждого -ro тактового импульса.

Такт работы устройства определяется временем си км 1- qr, где t < — время сложения на одноразрядном сумматоре; задержка информации коммутатора; время записи информации в регистр.

Быстродействие устройства равно

Т= nt.

Затраты оборудования на устройство определяются по соотношению

<=(" ")рг (Зп)см+Оп м, Как видим, на предлагаемое ус тройство требуется меньше одноразрядных сумматоров и в и раз меньше одноразрядных коммутаторов и лишь на

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

Пусть п=32, т. е. обработке подлежат массивы 32 разрядных чисел. Для реализации известного устройства на элементах 155 серии потребуется

768 микросхем 155ТМ8, 768 микросхем

155ИПЗ, 288 микросхем 155ИП4, 1536 микросхем 155ЛР1; всего 3360 микросхем.

Для реализации предлагаемого устройства на той же элементной базе и

1115049 при foA же разрядности потребуется

816 микросхем 155TMS, 48 микросхем

155ИПЗ, 48 микросхем 155ЛРТ, 8 микросхем 155РЕЗ, для хранения констант; всего 920 микросхем.

Как видно, имеется выигрыш по оборудованию в 3,65 раза.!

Высокая однородность структуры устройства и очень малое число внеш них связей делают его перспективный для изготовления в виде БИС.

Эффективность изобретения заключается в сокращении оборудования за счет поразрядной обработки в процессе времени.

Фиг. 7

1 1 1 50l 9

1115049

91

701

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

Редактор Е.Лушникова Техред С.Легеза Корректор Г.Решетник

Заказ 6771/35 Тираж 698 Подписное

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

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

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