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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик оп 972503(51 М. Кп.з С 06 Г 7/544 Государственный комитет СССР по дедам изобретений и открытий.,( Киевский ордена Ленина политехнический инс т тут . ЙГ;.:2,");,1 им . 5 д-летия Великой Октябрьской социалис тичЖлтой- революции(54) КОНВЕЙЕРНОЕ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯЦЕПНЬИ ДРОБЕЙ 10 Изобретение относится к вычислительной технике, в частности к области выполнения арифметических операций в многорегистровых арифметических устройствах, выполненных иа узлах с . большой .степенью интеграции, и может быть использовано в вычислительных системах в качестве высокопроизводительного блока.Известно устройство, с помощью которого можно вычислять цепные дро, аМ аим а 2 алби вида +- + .++"1Ь, Ьтич Ь г. Ь 1 15 состоящее из основного канала, содержащего три интегратора и сумматора, и а дополнительных каналов, каждый из которых состоит из четырех интеграторов и сумматоров ).1). 20 Вычисление звеньев цепной дроби в устройстве осуществляется путем, решения систем неоднородных разност-. ных уравнений, что наряду с большими аппаратурными затратами и зависимостью количества каналов от числа звеньев цепной дроби, обусловливает недостатки указанного устройства.Известны конвейерные устройства, которые позволяют выполнять арифме-,тические операции в режиме совмеще=ния и, следовательно, обладают вы-.соким быстродействием )2),Эти устройства непосредственнодля вычисления уепных дробей не предназначенЫ.Наиболее близким является конвейерное устройство, позволяющее одновременно выполнять арифметическиеоперации над множеством о-разрядныхчйсел и состоящее из множества однотипных вычислительных блоков. Каждыйвычислительный блок устройства содержит первый и второй триггеры, регистрчастичного. результата, регистр сомножителя, первый и второй сумматоры,шифратор, регистр делителя, четырегруппы (и+3) двухвходовых элементов И, две группы из (и+3) двухвходовых элементов ИЛИ 31.С помощью этого устройства возможно вычисление в режиме совмещенияарифметических выражений и выполнение арифметических операций"х", "/". При этом операции выполняются начиная со старших разрядовв полуавтономном режиме вычисленийс представлением промежуточных результатов в избыточной квазиканонической системе счисления. Для вычис 9725031 10 11 20 21 30 о 31 40 рованием разрядов одного из операндов по мере поступления разрядоврезультатов выполнения предыдущей операции. Такой принцип вычисленийпредполагает использование для представления промежуточных результатовизбыточной квазиканонической системысчисления.На фиг. 1 изображена структурнаясхема двух смежных вычислительныхблоков устройства; на фиг. 2 - связи И 60 между блоками устройства.11 аждый к-й вычислительный блок 1устройства к=1,2,3п,п+1) состоит из первого, второго и третьеготриггеров 2-4, четырех (п+4) - разрядленин цепной дроби из и звеньев при помощи известного устройства необходимо и+(и+8) (а) + 7 тактов работы устройства, где п - разрядость оп рандов. При этом устройство должно состоять из (и+4) блоков.Цель изобретения - повышение быстродействия.Поставленная цель достигается тем что конвейерное устройство для вычисления цепных дробей, содержащее (п+1) вычислительных блоков (и-раэ" рядность операндов, причем каждый к-й вычислительный блок (к = 1 п+1) содержит первый и второй триггеры, регистр частичного остатка, регистр делителя, регистр результата, два сумматора-вычитателя, шифратор, элементы И, при этом выход первого триггера соединен с первым вхо" дом первого элемента И, выход второго триггера соединен с первым входом второго элемента И, выходы первого и второго элементов И соединены с управляющими входами первого сумматора-вычитателя, выходы восьми старших разрядов которого соединены с входами шифратора, выходы разрядоврегистра частичного остатка соединены с первыми информационными входами разрядов первого сумматора-вычитателя соответственно, выходы шифратора соединены с входами первого и второг триггеров ( к-го вычислительного блока и с управляющими входами второго сумматора-вычитателя, первые информационные входы разрядов которого соединены с выходами разрядов первого сумматора-вычитателя выходыЭ (и+3) младших разрядов второго сумматора-вычитателя соединены с входами (и+3) старших разрядов регистра частичного остатка (к+1)-го вычислительного блока, младший разряд регистра частичного остатка соединен с шиной значения логического нуля устройства, выходы (и+1) старших разрядов регистра результата соединены с вторыми информационными входами (и+1) младших разрядов первого сумматора-вычитателя, вторые информационные входы трех старших разрядов первого сумматора-вычитателя соединены с шиной значения логического нуля устройства, тактовые ,входы всех регистров и триггера сое,динены с шиной тактовых импульсов устройства, каждый к-и вычислительный блок содержит третий триггер, третий и четвертый сумматоры-вычитатели, регистр веса, причем выход третьего триггера соединен с вторыми виодами первого и второго элементов и входом третьего триггера (к+1)-го вычислительного блока, управляющиео входы третьего сумматора-вычитателя соединены с выходами первого и второ го элементов И, первые информационные входы разрядов третьего сумматора-вычитателя соединены с выходами разрядов регистра делителя, выходы разрядов третьего сумматора-вычитателя соединены с входами разрядов регистра делителя (к+1)-го вычислительного блока, управляющие входы сумматора-вычитателя соединены с выходами шифратора, первые информационные входы разрядов четвертого сумматора-вычитателя соединены с выходами разрядов регистра результата, выходы разрядов четвертого сумматоравычитателя соединены с входами разря" дов регистра результата (к+1)-го вычислительного блока, выходы разрядов регистра веса соединены с вторыми информационными входами разрядов четвертого сумматора-вычитателя, выходы (п+1)-го разряда регистра веса соединены с вторыми информационными входами разрядов четвертого сумматора вычитателя, выход (п+1) -го разряда регистра веса соединен с вторым информационным входом (и+1)-го разряда третьего сумматора-вычитателя, вторые информационные входы трех старших разрядов третьего сумматора-вычитателя соединены с шиной значения логического нуля устройства, выходы (и+3) старших разрядов регистра веса соединенй с входами (и+3) младших разрядов регистра веса (к+1)-го вычислительного блока, вход старшего разряда регистра веса соединен с шиной значения логического нуля устройства, выходы разрядов третьего сумматора-вычитателя соединены с вторыми1информационными входами разрядов второго сумматора-вычитателя, выходы разрядов регистра результата пятоговычислительного блока Соединены свторыми информационнными входами разрядов третьего сумматора-вычитателя первого вычислительного блока.Высокая скорость вычислений в устройстве достигается за счет использования полуавтономного принципа вычислений, отличающегося от классического тем, что операция над операндами выполняется одновременно с форми,ных регистров 5-8 делителя веса,частичного остатка и результата, первого и второго элемента И 9 и 10, четырех комбинационных (и+4)-разрядных сумматоров-вычитателей 11-14 и восьмивходового шифратора 15, имеющего два выхода. 5Указанные узлы связанымежду собой следующим образом: выход первоготриггера 2 - с входом первого элемента И 9, выход второго триггера 3 свходом второго элемента И 10, выход )О третьего триггера 4 - с входами первого и второго элементов И 9 и 10 и с входом третьего триггера 4 последующего блока 1, выходы разрядов регистра 5 делителя - с входами разрядов сумматора-вычитателя 11, выходы разрядов регистра 8 веса - с входаМи разрядов сумматора-вычитателя 12,выходы (и+3) старших разрядов регистра б веса - с входами (д+3) младших щ разрядов регистра 6 веса последующего блока 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, выходы 45 шифратора 15 - с управляющими входами сумматоров-вычитателей 12 и 14 и с входами первого и второго триггеров 2 и 3 (к)-го блока, выходы (и+1) младших разрядов сумматора О вычитателя 14 - с входами (в+1) старших разрядов регистра 7.частичного остатка последующего блока 1, выходы разрядов сумматора-вычитателя 12- с входами разрядов регистра 8 Результата последующего блока 1, вход младшего разряда регистра частичного остатка (к+1) -с логическим нулем, старший разряд регистра 8 веса - с шиной логического нуля, выходы разрядов регистра 8 результата пятогоблока 1 - с входами разрядов сумматора-вычитателя 11 первого блока. Сумматоры-вычитатели 11-14 представляют собой параллельные комбинационные сумматоры-вычитатели счастично групповыми переносами.Шифратор 15 представляет собойпостоянное запоминающее устройство(ПЗУ), прошивка которого осуществля.ется в соответствии с табл. 2,Выполнение ариФметических опера- .ций в устройстве осуществляется вдвоичной системе числения, начинаясо старших раэрядов с представлением промежуточных результатов внутриустройства избыточным кваэиканоническим кодом 1,0,1. Для кодированияцифр результата используются триггеры к.2 и к.3 в соответствии с табл.1.В устройстве при продвижении информации с первого блока 1 на (о+1)-йблок 1 последовательно в каждом к-мблоке 1 определяется разряд с весом2+ очередного звена цепной дроби.Для формирования делителя очередного звена цепной дроби каждый блок 1содержит сумматор-вычитатель 11. Длякомпенсации ошибок, возникающих привыполнении деления в полуавтономном .режиме, каждый блок содержит сумматор-вычитатель 13.Перевод цифр результата из квазиканонической системы счисления в двоично-позиционную осуществляется спомощью сумматора-вьмитателя 12.Рассмотрим работу устройства.Устройство работает с нормализованными положительными числами а,Ь. Я(1/2, 1) . На первом такте работй устройства в первом блоке 1 навходы триггеров 2 и 3 подаютсясоответственно логические "1" и пО",на вход триггера 4 - логический фОф,на входы регистра 5 делителя - кодчисла Ь, на входы регистра б веса -код 000100, на входы регистрачастичного остатка - код числа а.,на входы регистра 8 результата -" нули.Все числа представляются двоичнымикодами с четырьмя знаковыми разрядами (0000, ХХХХ).После приема операндов на указан-ные узлы содержимое регистра 5 дели.теля поступает на входы сумматоравычитателя 11, на другие входы которого поступает содержимое регистра 8результата пятого блока. ОДновремен-.но содержимое регистра 7 частичногоостатка поступает на входы сумматора-вычитателя 13, на другие входыкоторого поступает содержимое регистра 8 результата. В зависимости отзначений на выходах элементов И 9и 10 на сумматорах-вычитателях 11.и 13 осуществляется либо сложениеоперандов, либо их вычитание, либопередача первого операнда без измекения в соответствии с табл. 3.Значения восьми старших разрядоввыходов сумматора-вьгитателя 13 являются входами шифратора 15, в за,висимости от значения которых на.с табл. 2 Формируется код разрядачастного весом. 2 и в кваэиканонической системе счисления, который эатемпоступает на входы триггеров 2 и 3( к) -го блока 1 и на управляющиевходы сумматоров-вычитателей 12 и 14,Затем содержимое с выходов сумматора-вычитателя .11 поступает на входы сумматора-вычитателя 14, на другие входы которого поступает содержимое с выходов сумматора-вычитателя 13. ОДновременно на входы сумматора-вычитателя 12 поступает садержймое выходов регистра 8 результата,на другие входы сумматора-вычитателя 12 поступает, содержимое регистра б.В сумматорах-вычитателях 14 и 12в зависимости от значений на выходахшифратора 15 осуществляется либосложение, либо вычитание операндов,1либо пропуск операнда без изменениян.соответствии с табл 4,На втором такте работы устройстваосуществляется передача информации .на регистр следующего (второго) блока 1. На триггеры 2 и 3 поступает содержимое с выходов шифратора пятогоблока, на триггер 4 поступает содержимое с выхода триггера 4 первогоблока. На входы регистра 5 делителяпоступает, содержимое ухода;сумматора-вычитателя 11 первого блока, на. входы - регистра б веса - содержимоерегистра.б. веса первого блока 1, сдвинутое . вправо на один разряд, на входы регистра 7 частичного остатка пос тупает содержимое сумматора-вычитателя 14 первого блока, сдвинутое влевона один разряд, на входы регистра 8результата поступает содержимоевы-.ходов сумматора-вычитателя 12 первогоблока 1.Так как при полуавтономном принципе выполнения операции деления необходимо предварительное накопление.старших цифр делителя, перед пос,туплением .очередных операндов осуществляется задержка на четыре такта дляполучения четырех старших разрядов .первого частного.,На пятом такте на входы устройстваподаются следующие элементы цепной.дроби: .на входы триггеров 2 и 3 нер-.вого блока 1 - соответственно "1"и "0".; на.вход триггера 4 - логический "1", на входы регистра 5 делите,ля - код числа Ь , на входы регистра 6 веса - число 000100 О, навходы регистра 7 частичного остатка -код числа а, на входы регистра 8результата - нулевые значения.На девятом такте на входы устройства осушествляется подача операндов Ьи аъ.В дальнейшем описанные преобра 10 зевания повторяются для каждого иэблоков устройства и на (и+4 е)-мтакте на выходе сумматора-вычитателя 12 (и+1)-го блока 1 формируетсярезультат вычисления цепной дрОби,15 Время вычисления при этом составити+4(в)+1 тактов работы устройства,На (4 а)-м такте на входные регистры устройства можно подаватьоперайды новой цепной дроби. Следощ вательно, основное преимуществоконвейерного способа обработки инфоРмации заключается в эффективном использовании аппаратуры многорегист-,ровых устройств, и сохраняется в данном устройстве,При разрядности операндов и = 16и количестве звеньев цепной дробиа10 вычисление цепной дробипри помощи предлагаемого устройстваосуществляется эа 53 такта. При реа-.лизации данного устройства на микро-.)схемах серии К 155 и К 556 длительностьтакта работь 1 блокой устройства составит около 120 нс, т.е. время вычисления указанной цепной дроби состаЗ вит 6,.36 мкс.В качЕстве базового объекта выбран процессор СМ 2104 управляющеговычислительного комплекса СМ 4. Времявычисления указанной цепной дроби в46 базовом.объекте составит 157 мкс.Кроме того, предлагаемое устройство обладает по сравнению с базовымобъектом более высокой произвоДительностью. Так, для вычисления двух. цеп 45 ных дробей по 10 звенвев (и = 16)необходимо 11,16.мкс по сравнениюс 314 мкс в базовом объектеСтоимость одного блока устройства при его реализации на микросхемах серии К 155 и К 556 составит 57 руб. При числе блоков устройства, равном 17, стоимость устройства составит 969 руб. а стоимость базового объекта равна 4900 руб.972503 Таблица 1 0 О 0 0 О Т а бл и ц а 2 Цифра чаатного Входы шифратора 15 0000.0000 0000.0001 0 0 0 0 0 0 0000.0010 70000.00110000.0100 ОООО,0101 0000.0110 0000,0111 0000.1000 Состояние триггероа Выходы шифратора 151972503 12 Продолжение табл. 2 Входы шифратора 15 Цифра частного Выход шифратора 15 1 2ш0 О 0 0 О О О Таблица 3 Значения Иа выходах элементов И 9 И 10соответственно 0 0 0 0 П р и м е ч а н и е. М - передача первого операнда без изменения. Таблица 4ат тЗначения на выходах шифратора 15 0 0 0 Формула изобретения первого и второго элементов И соединены с управляющими входами первого сумматора-вычитателя, выходы восьми старших разрядов которого соединены с входами шифратора, выходы разрядов регистра частичного остатка соединены с первыми информационными входами разрядов первого сумматора-вычитателя соответственно, выходы шифратора соединены с входами перво го и второго триггеров (к)-го вычислительного блока,и с управляющими входами второго сумматор-вычитателя, первые информационные входы разрядов которого соединены с выходами разря 4 ф дов первого сумматора-вычитателя, вы 1111.1011 11111100 1111,1101 1111.1110 1111.1111 Конвейерное устройство для вычисления цепных дробей, содержащее (и+3) вычислительных блоков (д-раз рядность операндов, причем каядый к Й вычислительный. блок к - 1 ру и+1) содержит первый и второй триггеры, регистр частичного остатка, регистр делителя, регистр результата, два сумматора-вычислителя, шифратор, элементы И, при этом выход первого триггера соединен с первым входом первого элемента И, выход второго триггера соединен с первым входом второго элемента И, выходы Операции, выполняемые в сумматорахвычитателях 11 и 13 соответственно Операции,. выполняемые в сумматорахвычитателях 11 и 12 соответственно20 ходы (и+3) младших разрядов второго сумматора-вычитателя соединены с входами (п+3) старших разрядов регистра частичного остатка (к+1)-го вычислительного блока, младший разряд регистра частичного остатка соединен 5 с шиной значения логическОго нуля устройства, выходы (и+1) старших разрядов регистра результата соединены с вторыми информационными входами (и+1) ьйадших разрядов первого сум матора-вычитателя, вторые информацион ные входы трех старших разрядов первого сумматора-вычитателя соединены с шиной значения логического нуля "устройства, тактовые входы всех 5 регистров и триггеров соединены с шиной тактовых импульсов устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, каждый к-й вычислительный блок содержит третий триггер, третий и четвертый сумматоры-вычитатели, регистр веса, причем выход третьего триггера соединен с вторыми входами первого и второго элементов И и входом третьего триггера (к+1)-го вычислительного блока, управляющие входы третьего сумматора-вычитателя соединены с выходами первогои второго элементов И, первые информационные входы разрядов третьего сумматоравычитателя соединены с выходами разрядов регистра делителя, выходы разрядов третьего сумматора-вычитателя соединены с входами разрядов регистра делителя (к+1)-го вычислитель- З 5 ного блока, управляющие входы сумматора вычитателясоединейы с выходами шифратора, первые информационные входы разрядов четвертого сумматоравычитателя соединены с выходами раз рядов регистра результата, выходы разрядов четвертого сумматора-вычитателя соединены с входами разрядов ре гистра результата (к+1)-го вычислительного блока, выходы разрядов регистра веса соединены с вторыми инФормационными входами разрядов четвертого сумматора-вычитателя, выходы (и+1)-го разряда регистра веса соединены с вторыми информационными входами разрядов четвертого сумматора-вычитателя, выход (и+1)-го разряда регистра веса соединен с вторым инФормационным входом (и+1)-го разряда третьего сумматора-вычитателя, вторые информационные входы трех старших разрядов третьего сумматора-вычитателя соединены с шиной значения логического нуля устройства, выходы (п+3) старших разрядов регистра ве- . са соединены с входами (о+3) младших разрядов регистра веса (к+1)-го вычислительного блока, вход старшего разряда регистра веса соединен с шиной значения логического нуля устройства, выходы разрядов третьего сумматора-вычитателя соединены с вторыми информационнными входами разрядов второго сумматора-вычитателя, выходы разрядов регистра результата пятого вычислительного блока соединены с вторыми информационными входами разрядов третьего сумматора-вычитателя первого вычислительного блока.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 608181, кл. 6 06 Г 1/02, 1978.2. Самофалов К.Г. и др. Структурыи организация функционирования ЭВИи систем. Киев,фВища школа", 1978,с. 109-137,3, Авторское свидетельство СССРпо заявке М 2882565/18-24,кл . 0 06 Г 7/38, 1980 (прототип).972503 Фиг. г аказ 8518/41 исноВНИИПИ Го Рпо дел113035, М д. 4/ Тираж 731 Подлсударственного комитета СССам изобретений и открытийосква, Ж, Раушская наб.,иал ППП "Патент", г.ужгород, ул.Проектная,Составитель В.Березкинедактор А.Козориз Техред М.Гергель Корректор В.Бутяга