Конвейерное устройство для вычисления цепных дробей Советский патент 1982 года по МПК G06F7/544 

ления цепной дроби из m звеньев при помощи известного устройства необходимо n+(n+S) (m-1) + 7 тактов рабо ты устройства, где п - разрядость on рандов. При этом устройство должно состоять из (п+4) блоков, Цель изобретения - повышение быстродействия. Поставленная цель достигается тем что конвейерное устройство для вычисления цепных дробей, содержащее (п+1) вычислительных блоков (п-разрядность операндов, причем каждый к-й вычислительный блок (к 1,.,., п+1) содержит первый и второй триггеры, регистр частичного остатка, регистр делителя, регистр результата, два сумматора-вычитателя, шифратор, элементы И, при этом выход первого триггера соединен с первым входом первого элемента И, выход второго триггера соединен с первым входом Btoporo элемента И, выходы первого и второго элементов И соединены с управляющими входами первого сумматора-вычитателя, выходы восьми старших разрядов которого соединены с вxoдa ли шифратора, выходы разрядов регистра частичного остатка соединены с первыми информационными входами разрядов первого сумматора-вычитателя соответственно, выходы шифратора соединены с входами первого и второг TjiHrrepoB (к-3))-го вычислительного блока и с управляющими входами второго сумматора-вычитателя, первые информационные входы разрядов которого соединены с выходами разрядов первого сумматора-вычитателЯд выходы (п+3) младших разрядов второго сумматора-вычитателя соединены с входами (п+3) старших разрядов регистра частичного остатка (к+1)-го вычислительного блока, младший разряд регистра частичного остатка соединен с шиной .значения логического нуля устройства, выходы (п+1) старших разрядов регистра результата соединены с вторыми информационными входами (п + 1) млад:р11их разрядов первого сумматора-вычитателя, вторые информационные входы трех старших разрядов первого сумматора-вычитателя соединены с шиной значения логического нуля устройства, тактовые ;входы всех регистров и триггера сое :динены с шиной тактовых импульсов устройства, каждый к-й вычислительный блок содержит третий триггер, третий и четвертый сумматоры-вычита тели, регистр веса, причем выход третьего триггера соединен с вторыми виодами первого и второго элементов и входом третьего триггера ( вычислительного ,блока, управляющиео входы третьего сумматора-вычитателя соединены с выходами первого и втор го элементов И, первые .информационные входы разрядов третьего сумматора-вычитателя соединены с выходами разрядов регистра делителя, выходы разрядов третьего сумглатора-вычитателя соединены с входами разрядов регистра делителя (к+1)-го вычислительного блока, управляющие входы сумматора-вычитателя соединены с выходами шифратора, первые информационные входы разрядов четвертого сумматора-вычитателя соединены с выходами разрядов регистра результата, выходы разрядов четвертого сумматоравычитателя соединены с входами разрядов регистра результата (к+1)-го вычислительного блока, выходы разрядов регистра веса соединены с вторыми информационными входами разрядов четвертого сумматора-вычитателя, выходы (п+1)-го разряда регистра веса соединены с вторыми информационными входами разрядов четвертого сумматора вычитателя, выход (п+1)-го разряда регистра веса соединен с вторы информационным входом (п+1)-го разряда третьего сумматора-вычитателя, вторые информационные входы трех старших разрядов третьего сумматора-вычитателя соединены с шиной значения логического нуля устройства, выходы (п+З) старших разрядов регистра веса соединены с входами (п+3) младших разрядов регистра веса (к+1)-го вычислительного блока, вход старшего разряда .регистра веса соединен с шиной значения логического нуля устройства, выходы разрядов третьего сумматора-вычитателя соединены с вторыми информационными входами разрядов второго сумматора-вычитателя, выходы разрядов регистра результата пятого вычислительного блока соединены с вторыми информационнными входами разрядов третьего сумматора-вычитателя первого вычислительного блока. Высокая скорость вычислений в устройстве достигается эа счет использования полуавтономного принципа вычислений, отличающегося от классического тем, что операция над операндами выполняется одновременно с формированием разрядов одного из операндов по мере поступления разрядов результатов выполнения предыдущей операции. Такой принцип вычислений предполагает использование для пред- . ставления промежуточных результатов избыточной квазиканонической системы счисления. На фиг. 1 изображена структурная схема двух смежных вычислительных блоков устройства; на фиг. 2 - связи между блоками устройства. Каждый к-й вычислительный блок 1 устройства ,2,3,....п,п+1) состоит из первого, второго и третьего триггеров 2-4, четырех (n+t) - разряд1НЫХ регистров 5-8 делителя веса. частичного остатка и результата, пер вого и второго элемента И 9 и 10, четыре,х комбинационных ()-разрядных сумматоров-вычитателей 11-14 и восьмивходового шифратора 15, имеющего два выхода. Указанные узлы связаны;между собой следующим образом: выход первого триггера 2-е входом первого элемента И 9, выход второго триггера 3 свходом второго элемента И 10, выхо третьего триггера 4 - с входами пер (Вого и второго элементов И 9 и 10 и с входом третьего триггера 4 после дующего блока 1, выходы разрядов регистра 5 дели1еля - с входами разрядов сумматора-вычитателя 11, выходы разрядов регистра 8 веса - с входаМи разрядов сумматора-вычитателя 12 выходы (п+3) старших разрядов регист ра 6 веса - с входами (п+3) младших разрядов регистра б веса последующего блока 1, выходы (п+1) старших ра рядов-- регистра б веса - с входами (л+1) младших разрядов сумматора-вы читателя 11, выходы разрядов регйстра 7 частичного остатка - с входами разрядов сумматора-вычитателя 13, выходы разрядов регистра 8 - с входа ми разрядов сумматора-вьгчитателя 12, выходы (п+1) старших разрядов регист ра 8 результата - с входами (п+1) младших разрядов сумматора-вычитателя 13, выходы элементов И 9 и 10,с управляющими входами сумматороввычитателей 11 и 13, входы трех стар ших разрядов сумматоров-вычитателей 11 и 13 - с шиной логического ну ля, выходы разрядов суглматора-вычита теля 11 - с входами разрядов регистра 5 делителя последующего блока 1 и входами разрядов сумматора-вычитателя 14, выходы восьми старших разрядов сумматора-вьгчитателя 13 - с входами шифратора 15, выходы суммато ра-вычитателя 13 - с входами разрядов сумматора-вычитателя 14, выходы шифратора 15 - с управляющими входами сумматоров-вычитателей 12 и 14 и с входами первого и второго триггеров 2 и 3 (к-)-го блока, выходы (п+1) младших разрядов сумматоравычитателя 14 - с входами (п+1) ста ших разрядов регистра частичного остатка после;оющего блока 1, выходы разрядов сумматора-вычитателя 12с входами разрядов регистра 8 результата последующего блока 1, -вход младшего разряда регистра частичного остатка (к+1) логическим нулем, старший разряд регистра 8 веса - с шиной логическоз о нуля, выходы разрядов регистра 8 результата пятого j блока 1 - р входами разрядов сумматора-вычитателя 11 первого блока Сумматоры-вычитатели 11-14 предч ставлакзз собой параллельные комбинационные суг маторы-вычитатели с частично групповы1«1и переносами, Шифратор 15 представляет собой постоянное запоминающее устройство (ПЗУ), прошивка которого осуществляется в соответствии с табл. 2. Выполнение арифметических опера- .ций в устройстве осуществляется в двоичной системе числения, начиная со старших разрядов с представлением промежуточных результатов внутри устройства избыточным квазиканоническим кодом 1,0,1. Для кодирования цифр результата используются триггеры к.2 и к.З в соответствии с табл.1. В устройстве при продвижении информации с первого блока 1 на (п+1)-й блок 1 последовательно в каждом к-м блоке 1 определяется разряд с весом очередного звена цепной дроби. Для формирования делителя очередного звена цепной дроби каждый блок 1 содержит сумматор-вычитатель 11. Для компенсации ошибок, возникающих при выполнении деления в полуавтономнои . режиме, каждый блок содержит сумматор-внчитатель 13. Перевод цифр результата из квазиканонической системы счисления в двоично-позиционную осуществляется с помощью сумматора-вычитателя 12. Рассмотрим работу устройства. Устройство работает с нормализованными полохсительными числами , ell/2, Ij . На первом такте работы устройства в первом блоке 1 на входы триггеров 2 и 3 подаются соответственно логические 1 и О, на вход триггера 4 - логический О, на входы регистра 5 делителя - код числа Ь,-, на входы регистра 6 веса код 00010...О, на входы регистра частичного остатка - код числа а., на входы регистра 8 результата -нули. Все числа представляются двоичными кодами с четырьмя знаковыми разрядами (0000, XXX...X). После приема операндов на указанные узлы содержимое регистра 5 делителя поступает на входы сумматоравычитателя 11, на другие входы которого поступает содержимое регистра 8 результата пятого блока, одновременно содержимое регистра 7 частичного остатка поступает на входы сумматора-вычитателя 1J, на другие входы которого поступает содержимое регистра 8 результата. В зависимости от значений на выходах элементов И 9 и 10 на сумматорах-вычитателях 11 и 13 осуществляется либо сложение операндов, либо их вычитание, либо передача первого операнда без изменения в соответствии с табл. 3. Значения восьми старших разрядов ыходов суммдтора-вьр1итателя 13 явяются входами шифратора 15, в заисимости от значения которых ни

выходах ишфратора 15 в соответствии с табл. 2 формируется код разряда частного весом 2 в кваэиканонической системе счисления, который эатем поступает на входы триггеров 2 и 3 (к-З)-гоблока 1 и на управляющие входы сумматоров-Бычитателей 12 и 14. Затем содержимое с выходов .сумма тора-вычитателя .11 поступает на входы сумматора-вычитателя 14, на другие входы которого поступает содержимое с выходов сумматора-вычитателя13. одновременно на входы сумма-, тора-вычи1ателя 12 поступает содержимое выходов регистра 8 результата/

на другие входы сумматора-вычитате- ля 12 поступает, содержимое регистра б.

В сумматорах-вычитателях 14 тл 12 в зависимости от значений на выходах шифратора 15 осуществляется либо .

сложение, либо вычитание операндов, либо пропуск операнда без изменения в-соответствии с табл. 4,

о

На втором такте работы устройства осуществляется передача информации нарегистр Следующего Х ТОРОГО) блока 1. На .триггеры 2 и 3 поступает содержимое с выходов шиф1ратора пятого блока, на триггер 4/Поступаёт содержимое с выхода триггера 4 первого блока. На входы регистра 5 делителя поступает содержимое дахода сумматоратвычитазселя 11 первого блока, на

. входы - регистра -б веса - содержимое ре-гистра б веса первого блока 1, сдвинутое вправо на один разряд на входы регистра. 7 частичного остатка nodтупает. содержимое сумматора-вычитателя 14 первого блока, сдвинутое- влево на один разряд, на входы регистра 8 результата поступает содержимое вы-, .ходов сумматора-вычитателя 12 первого блока. 1.. ,, . ;: . . ...

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

получения четырех старших разрядов . .первого частного.

,На пятом, такте на входы устройства подаются следующие элементы цепной .дробив .на входы триггеров. 2 и 3 пер-. Bofo блока 1 - соответственно 1 .и О,- на вход триггера 4 - логичес.кий 1, на входы регистра 5 делите.ля - код числа Ь,; на входы регистра 6 веса - число 000100,,. О, на входы регистра 7 частичного остатка код числа а.2, на входы регистра 8 результата - нулевые значения.

На девятом такте на входы устройства осуществляется подача операндов Ь ;и а,,. . .

В дальнейшем описанные преобразования повторяются для каждого из блоков устройства и на ()-м такте на выходе сумматора-вычитателя 12 {п+1)-го блока 1 формируется результат вычисления цепной дроби Бремя вычисления при этом составит n+tCm-l ) + 1 { тактов работы устройства

На {ип-2)-м такте на входные регистры устройства можно подавать операнды новой цепной дроби. Следовательно, основное преимущество конвейерного способа обработки инфо мации заключается в эффективном ис-; пользовании аппаратуры многорегист- ; ровых устройств, и сохр аняется в ДаИ ном устройстве.

При разрядности операндов п 16 и количестве звеньев цепной дроби m ь 1о вычисление цепной дроби при помощи предлагаемого устройства осуществляется за 53 такта. При реализации данного устройства на микро-j jCxeMax серии К155 и К556 длительность такгга работы блокой устройства составит около 120 НС, т.е. время вычисления указанной цепной дроби составит б.36 МКС.

В качестве базового объекта выбран процессор СМ 2104 управлякнцего вычислительного комплекса СМ4. Время вычисления указанной цепной дроби в базовом .объекте составит 157 икс. Кроме того, предлагаемое устройство обладает по сравнению с базовыгл объектом более высокой производительностью. Так, для вычисления двух.цепных дробей по 10 звеньев () необходимо 11,16.МКС по сравнению с 314 МКС в базовом объекте.

Стоимость одного блока устройства при его реализации на микросхемах серии К155 и К556 составит 57 руб. При числе блоков устройства, равном 17, стоимость устройства составит 969 руб., а стоимость базового объек. та равна 4900 руб. .

Таблица 1

1111.3.000 1111.1001 1111.1010

1 1 1

О

о

о

Значения на выходах элементов И 9 И 10 соответственно П р и м е ч а н и е. X - передача первого

Значения на выходах шифратора 15

Формула изобретения

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

Таблица 3

Операции, вьшЬлняемые. в сумматорахвычитателях 11 и 13 соответственно

Операции-, выполняемые в сумматорахвычитателях 14 и12 соответственно

первого и второго элементов И соединены с управляющими входами первого сумматора-вычитателя, выходы восьми старишх разрядов которого соединены с входами шифратора, выходы разрядов регистра частичного остатка соединены с первыми информа1ц онными входами разрядов первого сумматора-вычитателя соответственно, выходы шифратора соединены с входами первого и второго триггеров (к-З)-го вычислительного блока.и с управляющими входами второго сумиатор-вычитателя, первые информационные входы разрядов которого соединены с выходами разря5(Дов первого сумматора-вычитателя выоперанда без изменения, Т« а б л и ц а 4

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

теля соединены с входами разрядов ре гистра результата (к+1)-го вычислительного блока, выходы разрядов регистра веса соединены с вторыми информационными входами разрядов чет- ,

5 вертого сумматора-вычитателя, выходы (п+1)-го разряда регистра веса соединены с вторыми информационными входами разрядов четвертого сумматора-вычитателя, выход (п+1)-го разряда

0 регистра веса соединен с вторым информационным входом (п+1)-го разряда третьего сумматора-вычитателя, вторые информационные входы трех старших разрядов третьего сумматора-вычи5 тателя соединены с шиной значения логического нуля устройства, выходы (п+З) старших разрядов регистра ве- . са соединены с входами (п+З) младших разрядов регистра веса (к+1)-го вы числительного блока, вход старшего разряда регистра веса соединен с шиной значения логического нуля устройства, выходы разрядов третьего сумматора-вычитателя соединены с вто- рыми информационнными входами разрядов второго сумматора-вычитателя, выходы разрядов регистра результата пятого вычислительного блока соединены с вторыми информационными входами разрядов третьего сумматора-вы0 читателя первого вычислительного блока.

Источники информации, принятые во внимание при экспертизе

и систем. Киев Вита школа, 1978, с. 109-137.

0 3. Авторское свидетельство СССР по заявке № 2882565/18-24, кл. G 06 F 7/38, 1980 (прототип).

Фиг. f

т

фф А Ж ф

фф ф ф Ф

LI

JbJT

/ I

ф Ф 1

фф ф/л Ж

т f фр /JV

лч /л { Г Т ф /1

«г.2