Устройство для реализации алгоритма Волдера Советский патент 1984 года по МПК G06F7/544 

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

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

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

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

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

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

и три сдвигателя, а п-я ячейка содержит два сумматора, три регистра и два сдвигателя. Устройство работает по конвейерному принципу. В каждой его ячейке, являющейся ступенью конвейера, реализуется одна итерация алгоритма Волдера. При обработке массивов чисел быстродействие устройства достигает времени I СМ KW t рг где tf, tц(А - задержка информации соответственно n разрядным сумматором и коммутатором; tpr - время записи информации в регистр. Затраты оборудования,на устройство составляют (ЛмЧЗп).м, где первое, второе и третье слагаемые - соответственно число триггеров одноразрядных сумматоров и коммутаторов . В устройстве производится обрабо ка данных, представленных полноразрядным кодами. Во многих случаях эти данные поступанэтг в цифровое утсройство поразрядно, что позволяет производить их перезарядную обработку 2. Недостатком устройства является большие затраты оборудования при поразрядном поступлении обрабатываемых данных. Цоль изобретения - сокращение затрат оборудования. Поставленная цель достигается тем что в устройство для реализации алгоритма Волдера, содержащее-п последовательно соединенных ячеек, где П разрядность устройства, каждая из которых содержит первый, второй и третий регистры, первый, второй и третий сумматоры-вычитатели, первый второй и третий коммутаторы, причем выходы младших разрядов первого, вто рого и третьего регистров соединены с первыми информационными входами соответственно первого, второго и третьего сумматоров-вьгчитателей, выходы первого и второго коммутаторов соединены с вторыми информационными входами соответственно первого и второго сумматоров-вычитателей, выходы первого, второго и третьего сумматоров-вычитателей i-й ячейки (где i 1, 2, 3, ..., n) соединены с информа ционными входами соответственно первого, второго и третьего регистров (i+1)-1 ячейки, входы первого, второ го регистров первой ячейки соединены соответственно с первым, вторым и третьим входами записи операндов устройства, информационные выходы первого и второго сумматоров-вычита194 тёлей п-й ячейки соединены соответственно с первым .и вторьм выходами результата устройства, введен блок управления, ка}кдая ячейка содержит кольцевой регистр, с первого по шестой триггеры, причем единичные входы первого, второго и третьего триггеров соединены с выходами перекоса соответственно первого, второго и третьего сумматоров-вычитателей, управляющие входы которых соединены с информационным выходом третьего коммутатора, третьи информационные входы первого, второго и третьего сумматоров-вьгчитателей соединены с I единичными выходами соответственно первого, второго и третьего триггеров, единичные входы которых соединены с управляющими входами первого, второго регистров и кольцевого регистра, информационный вход которого соединен с выходом младшего разряда кольцевого регистра и вторым информационным входом третье.го сумматоравычитателя, установочные входы первого, второго и третьего триггеров соединены с нулевыми входами четвертого, пятого и шестого триггеров, единичные входы которых соединены с информационными входами соответственно первого, второго и третьего регистров , единичные выходы четвертого, пятого и шестого триггеров соединены с первыми информационными входами соответственно второго, первого и третьего коммутаторов, вторые информационные входы первого и второго коммутаторов соединены с выходом (1+1)-го разряда соответственно второго и первого регистров, первый управляющий вход второго коммутатора соединен с вторым управляющим входом первого коммутатора, первый управляющий вход которого соединен с вторым управляющим входом второго коммутатора, второй информационный вход третьего коммутатора соединен с выходом пятого триггера, причем блок управления содержит генератор тактовых импульсов, триггер, элемент НЕ, сдвиговый регистр и элемент И, причем управляюпщй вход генератора тактовых импульсов соединен с входом запуска устройства и вторым установочным входом сдви1осого регистра, первый установочный вход которого соединен с выходом первого разряда сдвигового регистра, инверсный выход первого 51 рагфяда которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов и входом элемента НЕ, выход которого соединен с , синхронизирующим входом сдвигового регистра, информационный вход триггера соединен с входом выбора операции устройства, инверсный выход триг гера соединен с вторым управляющим входом третьего коммутатора i-й ячейки, прямой выход триггера блока управления соединен с первым управляющим входом третьего коммутатора i-й ячейки, причем управляющие входы всех регистров и единичные входы первого, второго и третьего триггеров i-й ячейки соединены с выходом генератора тактовых импульсов блока управления, первый и второй управляю щие входы третьего коммутатора i-й ячейки соединены соответственно с прямым и инверсным выходами триггера кода операций блока управления, г ервый управляющий вход первого коммута тора и второй управляющий вход второ го коммутатора i-й ячейки соединены с прямым выходом i-ro разряда сдвиго вого регистра блока управления, инверсный выход i-ro разряда которого соединен с вторым управляющим входом первого коммутатора и первым управляющим входом второго коммутатора i-й ячейки, вход (п-1)-го разряда сдвигового регистра блока управления соединем с источником сигнала 1 и с первым и вторым управляющими вх дами соответственно второго и первого коммутаторов первой ячейки, а вт рой и первый управляющие входы втор го и первого коммутаторов первой ячейки подключены к шине нулевого потенциала, информационный выход третьего сумматора-вычитателя п-й ячейки соединен с третьим выходом результата устройства. На фиг. 1 представлена блок-схем устройства для реализации алгоритма Волдера; на фиг. 2 - функциональная схема i-й ячейки устройства; на фиг. 3 - функциональная схема блока управления; на фиг. 4 - временная диаграмма работы устройства. Устройство (фиг. 1).содержит п последовательно соединенных ячеек 1 с входами 2-10, выходами 11-13, бло 14 управления с входами 15 и 16. 96 Каждая ячсчжа 1 устройства (фиг. 2) содержит сумматоры-нычитатели 17-19,. триггеры 20-25, сдниговыс регистры 26-26, кольцевой регистр 29, коммутаторы 30-32. Клок 14 управления (фиг. 3) содержит генератор 33 тактовых импульсов, .элемент НЕ, инвертор 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-x разрядов регистров 26 и 27, первые и вторые управляющие вход)1 коммутаторов 31 и 30 соединены соответственно с входами 10, а коммутаторы 30 и 31 с входами ячейки, выходы триггеров 24 и 25 соединены с вторым и первым информационными входами коммутатора 32, выход которого соединен с управляющими входами сумматоров 17 - 19, второй вход сумматора 19 соединен с выходом и входом кольцевого регистра, управляющие входы триггеров 20-22 и регистров 26-29 соединены с входом ячейки 2, управляющие входы триггеров 23-25 соединены с входом ячейки 5 и с входами сбросов триггеров 20-22, первый и второй управляющие входы коммутатора 32 соединенны с входами ячеек 4-3, выходы данных сумматоров 17 - 19 соединены с выходами ячеек 11 - 13, выход генератора 33 тактовых импульсов соединен с входами 2 всех ячеек 1 устройства, с входом схемы 37 И и с входом инвертора 34, выход которого соединен с входом синхронизации сдвигового регистра 35, прямой

и инверсный выходы 1-го разряда которого соединены соотнезтстпепно с входами 9 и 10 i-й ячейки 1 (, 3, . . . , п), выход 1-го разряда сдвигового регистра 35 также соединен с входом регистра, второй вход сброса которого соединен с входом генератора 33 и входом.15 устройства, вход 16 устройства соединен с входом триггера 36 кода операции, прямой и инверсный выходы которого соединены с входами 3 и 4 каждой ячейки 1 устройства, инверсный выход первого разряда регистра 35 соединен с вторым входом схемы 37 И, выход которой соединен с входами 5 всех ячеек устройства, вход 9 первой ячейки соединен с источником 1, а вход 10 - с источником

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

y,(,

ii- .2-, .

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

С - константы, вид которых определяется типом вычисляемых функций (для тригонометрических функций C,arctg 2, для гиперболических 2, для логарифмич еских и экспоненциальных (1+2 } 1 1, 2, ..., п) (п- - разрядьи -тъ представления чисел).

Устройство работает следующим образом.

По входу 16 триггер 36 кода операции устанавливается в состояние О или 1. Если триггер 36 устанавливается в состояние О, то в устройстве будут выполняться операции, реализуемые по алгоритму Волдера, в котором , зависит от знака f,; если же в со-тояиие 1 - от знака у,. По входу 15 поступает сигнал, запускающий генератор 15 тактовых импульсов. Импульсы из генератора 33 поступают на регистры и триггеры устройства. С каждым импульсом информация в регистрах устройства сдвигается

на один разряд.

После поступления первых п импульсов в регистры 26 - 28 первой ячейки 1 поразрядно, младшими разрядами вперед записываются начальные значения Хд, УО, Yg , вид которых определяется выполняемой операцией. Сигнал 5 поступающий по шине 9 с вькода первого разряда регистра 35, подключает входы сумматоров 17 и 18 через коммутаторы 30 и 31 к выходам соответственно регистров 27 и 26. На сумматорах 17 - 19 проиг водится сложение ; или вычитание (в зависимости от сиг нала, поступаюшего с выхода коммутатора 32) , на irx управляющие входы. Данный сигнал зависит либо от содер жимого триггера 24, либо от содержимого триггера 25, и которых записаны знаки соответственно Ур и 4,. Запись знаковых разрядов в указанные триггеры производится импульсом, по0 ступаюиа1м по шин1 5 (фиг. 3).

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

регистра 27 с разрядом регистра 26, на сут-1маторе 19 cooTBeTCTBetiHo П -х разрядов регистров 28 и 29.

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

запишутся младшие разряды следующих операторов, подлежащие обработке. На сумматорах 17 - ,19 прЬизводится сложение (.п-1)-х разрядов соответствую щих операндов и переносов из п-х.

5 разрядов.

С приходам (п+2)-го импульса в регистрах 26 - 28 второй ячейки 1 производится сдвиг информации на разряд вправо, полученные на сумматорах 17 - 19 значения записываются в пергые разряды регистров второй ячейки 1, а в регистрах первой ячейки 1 производится сдвиг информации на разряд вправо и запись вторых раз рядов следующих операндов. Таким образом, на сумматорах 17-19 первой ячейки реализуются соответственно первое, второе и третье управления первой итерации алгоритма Волдера. При этом значение константы с . предварительно записано в регистр 29 и поступает младшими разрядами вперед на сумматор 19 с циклическим сдвигом в каждом такте.

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

После поступления 3 и импульсов в третьей ячейке будет выполняться третья итерация над вторыми операндами, а- в первой ячейке - первая итерация над третьими операндами. При этом в регистре третьей ячейки записана третья константа. а два последних разряда значений регистров 27 и 26 суммируются с содержимым соответственно триггеров 24 и 23, в которые записаны по сигналам знаковые разряды значений у и х соответственно поступающим по шине 5

(фиг. 4).

I

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

и 27 суммируются соответственно с содержимым триггеров 2А и 23.

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

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

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

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

Такт работы устройства определяется временем

..MU,

5)г ,.

где t с/ц - время сложения на одноразрядном сумматоре; t к/л - задержка информации коммутатора;t рг - время записи информации в

регистр.

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

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

W44n%6M)pr4{3n)cMUin),

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

Пусть , т.е. обработке подлежат массивы 32 разрядных чисел. Для реализации известного устройства на элементах 155 серии потребуется 768 микросхем 155ТМ8, 768 микросхем 155ИПЗ, 288 микросхем 155ИП4, 1536 микросхем 155ЛР1; всего 3360 микросхем.

Для реализации предлагаемого устройства на той же элементной базе и при Той же разрядности потребуется 816 микросхем 155ТМ8, 48 микросхем 155ИПЗ, 48 микросхем 155ЛР1, В микросхем 155РЕЗ, для хранения констант; всего 920 микросхем. Как видно, имеется выигрыш по обо-рудованию в 3,65 раза. 1115

Г г т

Фиг.1 Высокая однородность структуры устройства и очень малое число внеш них связей делают его перспективным для изготовления в виде БИС. Эффективность изобретения заключается а сокращении оборудования за счет поразрядной обработки в процессе времени. I Z 3 JlJTJ JT

9c-J

loin

n

n

Фиг. t-I гг. I Z 3 n-l n 1 JTJnjnJIJlJ