SU1115049A1 - Устройство дл реализации алгоритма Волдера - Google Patents

Abstract

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

Description

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

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

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

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

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

и три сдвигател , а п-   чейка содержит два сумматора, три регистра и два сдвигател . Устройство работает по конвейерному принципу. В каждой его  чейке,  вл ющейс  ступенью конвейера , реализуетс  одна итераци  алгоритма Волдера. При обработке массивов чисел быстродействие устройства достигает времени I СМ KW t рг где tf, tц(А - задержка информации соответственно n разр дным сумматором и коммутатором; tpr - врем  записи информации в регистр. Затраты оборудовани ,на устройство составл ют (ЛмЧЗп).м, где первое, второе и третье слагаемые - соответственно число триггеров одноразр дных сумматоров и коммутаторов . В устройстве производитс  обрабо ка данных, представленных полноразр дным кодами. Во многих случа х эти данные поступанэтг в цифровое утсройство поразр дно, что позвол ет производить их перезар дную обработку 2. Недостатком устройства  вл етс  большие затраты оборудовани  при поразр дном поступлении обрабатываемых данных. Цоль изобретени  - сокращение затрат оборудовани . Поставленна  цель достигаетс  тем что в устройство дл  реализации алгоритма Волдера, содержащее-п последовательно соединенных  чеек, где П разр дность устройства, кажда  из которых содержит первый, второй и третий регистры, первый, второй и третий сумматоры-вычитатели, первый второй и третий коммутаторы, причем выходы младших разр дов первого, вто рого и третьего регистров соединены с первыми информационными входами соответственно первого, второго и третьего сумматоров-вьгчитателей, выходы первого и второго коммутаторов соединены с вторыми информационными входами соответственно первого и второго сумматоров-вычитателей, выходы первого, второго и третьего сумматоров-вычитателей i-й  чейки (где i 1, 2, 3, ..., n) соединены с информа ционными входами соответственно первого , второго и третьего регистров (i+1)-1  чейки, входы первого, второ го регистров первой  чейки соединены соответственно с первым, вторым и третьим входами записи операндов устройства, информационные выходы первого и второго сумматоров-вычита1 94 тёлей п-й  чейки соединены соответственно с первым .и вторьм выходами результата устройства, введен блок управлени , ка}кда   чейка содержит кольцевой регистр, с первого по шестой триггеры, причем единичные входы первого, второго и третьего триггеров соединены с выходами перекоса соответственно первого, второго и третьего сумматоров-вычитателей, управл ющие входы которых соединены с информационным выходом третьего коммутатора, третьи информационные входы первого, второго и третьего сумматоров-вьгчитателей соединены с 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

Claims (1)

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

   SU,.„ 1115049 (i+1)-ro разряда соответственно второго и первого регистров, первый управляющий вход второго коммутатора соединен с вторым’ управляющим входом первого коммутатора, первый управляющий вход которого соединен с вторым управляющим входом второго коммутатора, второй информационный вход третьего коммутатора соединен с выходом пятого триггера, причем блок управления содержит генератор тактовых импульсов, триггер, элемент НЕ, сдвиговый регистр и элемент И, причем управляющий вход генератора тактовых импульсов соединен с входом запуска устройства и вторым установочным входом сдвигового регистра, первый установочный вход которого соединен с выходом первого разряда сдвигового регистра, инверсный выход первого разряда которого соеди·нен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов и входом элемента НЕ, выход которого соединен с синхронизирующим входом сдвигового регистра, информационный вход триггера соединен с входом выбора операции устройства, инверсный выход триггера соединен с вторым управляющим входом третьего коммутатора <-й ячейки, прямой выход триггера блока управления соединен с первым управ ляющим входом третьего коммутатора 1 —й ячейки, причем управляющие входы всех регистров и единичные входы перового, второго и третьего триггеров 1-й ячейки соединены с выходом генератора тактовых импульсов блока управления, первый и второй управляющие входы третьего коммутатора i -й ячейки соединены соответственно с прямым и инверсным выходами триггера кода операций блока управления, первый управляющий вход первого коммутатора и-второй управляющий вход второго коммутатора i-й ячейки соединены с прямым выходом 1 -го разряда сдвигового регистра блока управления, инверсный выход i-го разряда которого соединен с вторым управляющим входом первого коммутатора и первым управляющим входом второго коммутатора i-й ячейки, вход (п-1)-го разряда сдвигового регистра блока управления соединен с источником сигнала Г' и с первым и вторым управляющими входами соответственно второго и первого коммутаторов первой ячейки, а второй и первый управляющие входы второго и первого коммутаторов первой ячейки подключены к шияе нулевого потенциала,информационный выход третьего сумматоравычитателя η-й ячейки соединен с третьим выходом результата устройства.