Конвейерное устройство для вычисления цепных дробей

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

«о972503 (61) Дополнительное к авт. свид-ву (22) Заявлено 0805.81 (21) 3287605/18-24

I с присоединением заявки М " (23) Приоритет

Опубликовано 071182. Бюллетень М41

Дата опубликования описания 071182 (51) М. Кп.з

G 06 F 7/544

Государственный комитет

СССР по делам изобретений и открытий (53) УДК 681.3 (088.8) Г.M.Ëóöêèé, A.Â.Êoðo÷êèí, A.Н.Долголенко и О.И.Пенчев (НРБ), C

Киевский ордена Ленина политехнический инст тут 6," Л;,,...7 ;„. ии. 56-летия Великой Октябрьской социалистичЖлтойреволюции (72) Авторы изобретения (71) Заявитель (54) КОНВЕЙЕРНОЕ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ЦЕПНЬИ ДРОБЕЙ

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

Известно устройство, с помощью которого можно вычислять цепные дро. аМ анм а2 ал би вида + + о„„,„ состоящее из основного канала, содержащего три интегратора и сумматора, и m дополнительных каналов, каждый из которых состоит из четырех интеграторов и сумматоров (1g .

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

Известны конвейерные устройства, которые позволяют выполнять арифметические операции в режиме совмеще= ния и, следовательно, обладают вы- ° соким быстродействием $2J .

Эти устройства непосредственно для вычисления цепных дробей не предназначенЫ.

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

С помощью этого устройства возможно вычисление в режиме совмещения арифметических выражений и выполнение арифметических операций

"x", "/". При этом операции выполняются начиная со старших разрядов в полуавтономном режиме вычислений с представлением промежуточных результатов в избыточной квазиканонической системе счисления. Для вычис- .

972503

P -

1

30 о

40

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

На фиг. 1 изображена структурная схема двух смежных вычислительных блоков устройства; на фиг. 2 — связи

И 60 между блоками устройства.

1(аждый к-й вычислительный блок 1 устройства к=1,2,3,....и,и+1) состоит из первого, второго и третьего триггеров 2-4, четырех (и+4) — разрядленин цепной дроби из m звеньев при помощи известного устройства необходимо и+(и+8) (m-1) + 7 тактов работы устройства, где п — разрядость оп рандов. При этом устройство должно состоять из (n+4) блоков.

Цель изобретения — повышение быстродействия.

Поставленная цель достигается тем что конвейерное устройство для вычисления цепных дробей, содержащее (n+l) a HO»HTp aH 5TIOKOB (n"ÐàÝрядность операндов, причем каждый к-й вычислительный блок (к = 1,..., и+1) содержит первый и второй триггеры, регистр частичного остатка, регистр делителя, регистр результата, два сумматора-вычитателя, шифратор, элементы И, при этом выход первого триггера соединен с первым входом первого элемента И, выход второгс триггера соединен с первым входом второго элемента И, выходы первого и второго элементов И соединены с управляющими входами первого сумматора-вычитателя, выходы восьми старших разряд(ов которого соединены с входами шифратора, выходы разрядов регистра частичного остатка соединены с первыми информационными входами разрядов первого сумматора-вычитателя соответственно, выходы шифратора соединены с входами первого и второг триггеров (к-3))-го вычислительного блока и с управляющими входами второго сумматора-вычитателя, первые информационные входы разрядов которого соединены с выходами разрядов первого сумматора-вычитателя выходы

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

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

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

Высокая скорость вычислений в устройстве достигается за счет использования полуавтономного принципа вычислений, отличающегося от классического тем, что операция над операндами выполняется одновременно с форми,ных регистров 5-8 делителя веса, 972503 частичного остатка и результата, первого и второго элемента И 9 и 10, четырех комбинационных (n+4) †ðàçðÿäных сумматоров-вычитателей 11-14 и восьмивходового шифратора 15, имеющего два выхода. 5

Указанные узлы связаны между собой следующим образом: выход первого триггера 2 — с входом первого элемента И 9, выход второго триггера 3 с .входом второго элемента И 10, выход 10 третьего триггера 4 — с входами пер 1вого и второго элементов И 9 и 10 и с входом тРетьего триггера 4 последующего блока 1, выходы разрядов регистра 5 делителя — с входами разрядов сумматора-вычитателя 11, выходы разрядов регистра 8 веса — с входами разрядов сумматора-вычитателя 12, выходы (n+3) старших разрядов регистра б веса — с входами (и+3) младших щ разрядов регистра б веса последующего блока 1, выходы (n+1) старших разрядов: регистра б веса — с входами (n+1) младших разрядов сумматора-вычитателя 11, выходы. разрядов регистра 7 частичного остатка — с входами раэрядон сумматора-вычитателя 13, выходы разрядов регистра 8 — с входами разрядов сумматора-вычитателя 12, выходы (и+1) старших разрядов регистра 8 результата - c входами (n+1) младших разрядов сумматора-вычитателя 13, ныходы элементов И 9 и 10,— с управляющими входами сумматороввычитателей 1.1 и 13, входы трех стар-. ших разрядов сумматоров-вычитателей 11 и 13 — с шиной логического нуля, выходы разрядов сумматора-вычитателя 11 — c входами разрядов регистра 5 делителя последующего блока 1 и входами разрядов сумматора-нычита- 40 теля 14, выходы восьми старших разрядов сумматора-вычитателя 13 - с входами шифратора 15, выходы сумматора-вычитателя 13 — с входами разрядов сумматора-вычитателя 14, выходы 45 шифратора 15 — с управляющими входами сумматоров-вычитателей 12 и 14 и с входами первого и второго триггеров 2 и 3 (к-4)-ro блока, выходы (и+1) младших разрядов сумматора- 5О вычитателя 14 — с входами (n+1) старших разрядов регистра 7 частичного остатка последующего блока 1, выходы разрядов сумматора-нычитателя 12с входами Разрядов Регистра 8 Ðå- 55 зультата последующего блока 1, .вход младшего разряда регистра частичного остатка (к+1) с логическим нулем, старший разряд регистра 8 веса — с шиной логического нуля, выходы раз-! рядов регистра 8 результата пятого

I блока 1 — с входами разрядов сумматора-вычитателя 11 первого блока.

Сумматоры-вычитатели 11-14 представляют собой параллельные комби- 65 национные сумматоры-вычитатели с частично групповыми переносами.

Шифратор 15 представляет собой постоянное запоминающее устройство (ПЗУ), прошивка которого осуществляется в соответствии с табл. 2.

Выполнение арифметических опера- .ций в устройстве осуществляется в двоичной системе числения, начиная со старших раэрядов с представлением промежуточных результатов внутри устройства избыточным кваэиканоническим кодом 1,0,1(1. Для кодирования цифр результата используются триггеры к.2 и к.3 в соответствии с табл.1.

В устройстве при продвижении информации с первого блока 1 на (и+1)-й блок 1 последовательно в каждом к-м блоке 1 определяется разряд с весом 2 +" очередного звена цепной дроби.

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

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

Рассмотрим работу устройства.

Устройство работает с нормализованными положительными числами а„., b„ E.(1/2, 1j . На первом такте работй устройства в первом блоке 1 на входы триггеров 2 и 3 подаются соответственно логические "1" и "0", на вход триггера 4 — логический "0", на входы регистра 5 делителя — код числа b, на входы регистра б веса— код 00010...0, на входы регистра частичного остатка — код числа а., на входы регистра 8 результата -" нули.

Все числа представляются двоичными кодами с четырьмя знаковыми разрядаMH (0000, ХХХ...Х).

После приема операндов на указан- ные узлы содержимое регистра 5 дели.теля поступает на входы сумматоравычитателя 11, на другие входы которого поступает содержимое регистра 8 результата пятого блока. ОДновремен-. но содержимое регистра 7 частичного остатка поступает на входы сумматора-вычитателя 13, на другие входы которого поступает содержимое регистра 8 результата. B зависимости от значений на выходах элементов И 9 и 10 на сумматорах-вычитателях 11 .и 13 осуществляется либо сложение операндов, либо их вычитание, либо передача первого операнда без изме» кения s соответствии с табл. 3.

Значения восьми старших разрядов выходов сумматора-ны4итателя 13 яв ляются входами шифратора 15, в за,нисимости от значения которых на !

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

Затем содержимое с выходов сумма» тора-вычитателя .11 поступает на входы сумматора-вычитателя 14, на другие входы которого поступает содержимое с выходов сумматора-вычитателя 13. ОДновременно на входы сумматора-вычитателя 12 поступает садержймое выходов регистра 8 результата, на другие входы сумматора-вычитате-; ля 12 поступает, содержимое регистра б.

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

На втором такте работы устройстваосуществляется передача информации . на регистр следующего (второго) блока 1. На триггеры 2 и 3 поступает содержимое с выходов шифратора пятого блока, на триггер 4 поступает содержимое с выхода триггера 4 первого блока. На входы регистра 5 делителя поступает, содержимое выхода,сумматора-.вычитателя 11 первого блока-, на . входы — регистра б веса — содержимое регистра.б. веса первого блока 1, сдвинутое . вправо на один разряд,.на входы регистра 7 частичного остатка пос тупает содержимое сумматора-вычитателя 14 первого блока, сдвинутое влево на один разряд, на входы регистра 8 результата поступает содержимое вы-. .ходов сумматора-вычитателя 12 первого блока 1.

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

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

На девятом такте на входы устройства осушествляется подача операндов Ь и а>, В дальнейшем описанные преобра10 зования повторяются для каждого из блоков устройства и на (n+4m-3)-м такте на выходе сумматора-вычитателя 12 (n+1)-го блока 1 формируется результат вычисления цепной дрОби.

15 Время вычисления при этом составит

n+4(m-1)+1 тактов работы устройства, На (4m-2)-м такте на входные регистры устройства можно подавать операйды новой цепной дроби. Следо20 вательно, основное преимущество конвейерного способа обработки инфоРмации заключается в эффективном использовании аппаратуры многорегист-; ровых устройств, и сохраняется в дан ном устройстве.

При разрядности операндов и = 16 . и количестве звеньев цепной дроби

m + 10 вычисление цепной дроби при помощи предлагаемого устройства осуществляется за 53 такта. При реализации данного устройства на микро схемах серии К155 и К556 длительность такта работь1 блоков устройства составит около 120 нс, т.е. время вычисления указанной цепной дроби состаЗ вит 6..36 мкс.

В качЕстве базового объекта выбран процессор СМ 2104 управляющего вычислительного комплекса СМ4. Время вычисления указанной цепной дроби в

46 базовом. объекте составит 157 мкс.

Кроме того, предлагаемое устройство обладает по сравнению с базовым объектом более высокой производительностью. Так, для вычисления двух цеп45 ных дробей по 10 звенвев (n = 16) необходимо 11,16.мкс по сравнению с 314 мкс в базовом объекте °

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

При числе блоков устройства, равном

17, стоимость устройства составит

969 руб> а стоимость базового объекта равна 4900 руб. 972503

Таблица 1

0

Таблица 2

Цифра чаатного

Входы шифратора 15

0000 ° 0000

0000 ° 0001

0

0000.0010 7 0000 ° 0011

0

0

0

0111.1110 .0111 ° 1111

1000.0000

1000.0001

100.0. 0010

1111. 000

1111.1001

1111.1010 Цифра избыточного квазиканонического кода

0000.0100

ОООО.0101

0000.0110

0000,0111

0000 ° 1000

Состояние триггерон з

Выходы шифратора 15 (972503

Продолжение табл. 2

Входы шифратора 15 Цифра частного

Выход шифратора 15

1 2 б

0

Таблица 3

Значения Иа выходах элементов И 9 И 10 соответственно

0

П р и м е ч а и и е. М вЂ” передача первого операнда без изменения.

Таблица 4

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

0 формула изобретения первого и второго элементов И соединены с управляющими входами первого сумматора-вычитателя, выходы восьми старших разрядов которого соединены с входами шифратора, выходы разрядов регистра частичного остатка соединены с первыми информационными входами разрядов первого сумматора-вычитателя соответственно, выходы шифратора соединены с входами перво46 го и второго триггеров (к-3)-ro вычислительного блока,и с управляющими входами второго сумматор-вычитателя, .первые информационные входы разрядов .которого соединены с выходами разря дов первого сумматора-вычитателя, вы1111.1011

1111 ° 1100

1111.1101

1111.1110

1111.1111

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

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

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

972503

20 ходы (n+3) младших разрядов второго сумматора-вычитателя соединены с входами (п+3) старших разрядов регистра частичного остатка (к+1)-го вычислительного блока, младший разряд регистра частичного остатка соединен 5 с шиной значения логическОго нуля устройства, выходы (n+1) старших

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

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

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

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

Р 608181, кл. G 06 F 1/02, 1978.

2. Самофалов К.Г. и др. Структуры и организация функционирования ЭВМ и систем. Киев,"Вища школа", 1978, с. 109-137.

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

972503

Составитель В.Березкин

Техред М.Гергель Корректор В.Бутяга

Редактор A.Êîýîðèç

Филиал ППП "Патент", r.Óæãîðoä, ул.Проектная, 4

Заказ 8518/41 Тираж 731 Подпис ное

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

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