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

ведения 8.n-разрядных чисел в устройстве проделывается весь комплекс действий, связанный с получением е. п-разрядного произведения. На опе .ранды, входящие в выражение (2), накладываются следующие ограничения все они должны быть положительными числами, десятичная точка должна быть фиксирована после последнего значащего разряда. (В случае выполнения только суммирования последовательности чисел десятичная точка может быть фиксирована в любом мес те. Из-за возможности выполнения сложения последовательности чисел в дополнительных кодах операнды, под леж-ащие сложению, могут быть также и отрицательными числами). Наиболее близким к предлагаемому является конвейерное устройство, содержащее Ч однотипных вычислител ных блоков ( 1 1,2,...,, где п - разрядность операндов , каждый из которых содержит регистр сомножителя, регистр частичного результата, комбинационный сумматор-вычи татель, блок памяти, первый, второй третий триггеры, причем в каждом вычислительном блоке тактовые входы первого, второго, третьего триггеров, регистра сошюжителя и регистр частичного результата объединены и подключены к тактовой шине устройства, выкод первого триггера подклю чен к управляющему входу комбинационного сумматора-вычитателя, четыре старших разряда которого соединены с адресным входом блока памяти, выходы регистра сомножителя i-го вычислительного блока соответственно соединены с информационными входами регистра сомножителя {i+l)-ro вычислительного блока. Все операции в этом устройстве выполняются над числами, представленными дополнительными кодами, т.е. операнды, входящие в выражение (2), могут быть как положительными так и отрицательными. Десятичная точка может быть фиксирована в любом месте. Выполнение арифметически операций в устройстве происходит в полуавтономном режиме вычислений начиная со старших разрядов, при этом достигается глубина перекрытия циклов работы блоков устройства при выполнении арифметических операций в один такт 4 . Однако очередная пара операндов принимается на входы устройства не на каждом такте, а через два такта на третьей после подачи предыдущей пары операндов арифметического выражения. Два промежуточных такта связаны с необходимостью преобразования промежуточного результата вычисления арифметического выражени представленного в избыточной квазиканонической системе счисления с цифрами l,0,i . Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что в каждый i-и вычислительный блок дополнительно введен коммутатор, причем информационные входы коммутатора соответственно соединены с выходами регистра сомножителя, первый управляющий вход коммутатора соединен с выходом второго триггера, второй управляющий вход коммутатора соединен с выходом третьего триггера, выходы регистра частичного результата соединены с соответствуюЕцими входами первой группы комбинационного сумматора-вычитателя, четыре старших входа второй группы которого соединены с выходом старшего разряда коммутатора, (п+1)-ый младший вход второй группы комбинационного сумматора-вычитателя соответственно соединен с (п+1)-ми младшими разрядами коммутатора, третий по (п+3)-ий информационные входы регистра частичного результата (i+l)-ro вычислительного блока соответственно соединены с (п+1)-ми младшими разрядами комбинационного сумматора-вычитателя i-го вычислительного блока, а два старших информационных входа соответственно с первым и вторым выходами блока памяти, четвертый, пятый и шестой выходы которого соответственно соединены с информационными входами первого, третьего и второго триггеров. На чертеже представлена структурная схема двух первых вычислительных блоков устройства. Каждый вычислительный блок устройства содержит .{п+5)-разрядный регистр 1. i частичного результата, комбинационный сумматор-вычитатель 2.-i, коммутатор 3.i, (п+1)-разрядный регистр 4.1 сомножителя, первый, второй и третий триггеры 5.i , 6.1, 7.1, блок 8.1 памяти. В устройстве тактовые входы триггеров 5.1, 6.i, 7.i, регистра 4.i сомножителя и регистра l.i частичного результата объединены и подключены к тактовой шине устройства, выход триггера 5.i подключен к управляющему входу комбинационного cyMNjaTQpa-вычитателя 2.i , четыре старших разряда которого соединены с адресным входом блока -8.1 памяти, выходы регистра 4. i сомножителя i-ro вычислительного блока соответственно соединены с информационными входами регистра 4.i сомножителя (i+i)-ro вычислительного блока, информационные входы коммутатора 3.i соответственно соединены с выходами регистра 4.i сомножителя, первый управляющий вход коммутатора 3.i соединен с выходом триггера 6.i , вт рой управляющий вход коммутатора 3.1 соединен с выходом триггера 7.1 , выходы регистра 1. j частичного результата соединены с соответствую щими входами первой группы комбинационного сумматора-вычитателя 2.-i, четыре старших входа второй группы которого соединены с выходом старшего разряда коммутатора 3., (п+1) ый младший вход второй группы комби йационного сумматора-вычитателя 2. соответственно соединены с {п+1)-ми младшими разрядами коммутатора 3.i третий по (п+3)-ий информационные входы регистра 1.i частичного результата (i+l)-ro вычислительного блока соответственно соединены с (п+1 )-ми младшими разрядами комбинационного сумматора-вычитателя 2.-i i-го блока, а два старших инфор мационных входа соответственно с первым и вторым выходами блока па мяти 8.1 , четвертый, пятый и шестой выходы которого соответственно соединены с информационными входами триггеров 5.1, 7.1 и 6.i . Комбинационный, сумматор-вычитатель 2.1 peдcтaвляeт собой параллельный комбинационный сумматор-вычитатель с частично групповым переносом. Он может быть реализован на микросхемах типа 1с155ИПЗ, совместно с микро схемами типа К155ИП4. Коммутатор 3.1 содержит (п+2)-ра рядную группу элементов 2И-ИЛИ. устройство работает следующим образом. Максимальная производительность устройства при вычислении п-разрядных чисел будет в том случае, если устройство состоит из +2 блоков. Все блоки устройства однотипны за исключением последнего, который содержит только узлы 1.1, 8.1, при атом регистр частичного остатка 1 состоит только из четырех старших разрядов и выходы всех этих разрядо должны быть соединены со входами блока 8.1 памяти. Регистры l.i всех блоков, кроме первого, могут состоять не из (п+5)-ти триггеров, а из (п+3)-х триггеров, при этом к первым входам двух младших разрядов сумматора-вычитателя 2.i вместо выходов двух младших разрядов регистра 1.1 должен быть подведен логический нуль. Выполнение арифметических операций в устройстве происходит в двоич ной системе счисления, начиная со старших разрядов, с представлением промежуточных результатов внутри устройства избыточным квазиканоническим кодом с цифрами 2,1,0,1,2) При помощи устройства возможно одновременное вычисление Двух многочленов по схеме Горнера (2), либо одновременное вычисление двух других арифметических выражений, вытекающих из схемы Горнера. При этом по нечетным тактам на входы устройства принимаются операнды первой схемы Горнера, а по четным - второй. Рассмотрим работу устройства на примере вычисления одной схемы Горнера. В первом такте на входы регистра частичного остатка i.l первого блока подается код числа а, представленный дополнительным двоичным кодом, имеющим пять знаковых разрядов (например, код 1111.ХХХ...XX в случае, если а 0), а на входы регистра сомножителя 4.1 первого блока записывается код числа 0. После приема операндов указанными узлами пер,вого блока содержимое регистра 1.1 поступает на входы сумматора-вычитателя 2.1, а на другие входы этого сумматора-вычитателя, в зависимости от содержимого триггеров 5.1 и 6.1, поступает число из регистра 4.1 либо поступает удвоенное содержимое регистра 4.1, либо содержимое регистра 4.1 на сумматор-вычитатель 2. Г-не передается вовсе (в триггерах 5.i и 6.1 находится двоично-кодированная цифра избыточного квазиканонического кода с цифрами 2,1,0,1,2} (cMi таблицу) представляющая собой цифру промежуточного результата, причем в триггерах 5.i и 6.i находится абсолютная величина цифры промежуточного результата, а ее знак содержится в триггере 7.i). Если триггер 5.1 находится в единице, а триггер 6.1 в нуле, то на сумматор-вычислитель 2.1 через коммута ор 3.1 передается удвоенное содержимое регистра 4.1. Если триггер 5.1 находится в нуле, а триггер 6.1 в единице, то через коммутатор 3.1 на сумматор-вычитатель передается содержимое регистра 4.1. Если оба эти триггера находятся в нуле, то содержимое регистра 4.1 не будет передано на сумматорвычитатель 2.1. При помощи сумматоравычитателя 2.1 в зависимости от триггера 7.1 к содержимому регистра l.l прибавляется либо вычитается из него содержимое регистра 4.1. Приэтом, если триггер 7.1 находится в нуле, что соответствует положительной цифре промежуточного результата (см. таблицу) , то осуществляется суммирование. Если триггер 7.1 находится в единице, что соответствует отрицательной цифре промежуточного результата, производится вычитание. Значения старших четырех разряДов сумматора-вычитателя 2.1 являются адресом выборки для блока 8.1 памяти. В зав1;1симости от адреса на вьоходах блока памяти, в соответстви с таблицей, появляется код первой старшей цифры промежуточного резуль тата, представленного избыточным кв зиканоническим кодом с цифрами l,2,0,i,2i, а также значение остат ка, представляющее собой значение двух старших разрядов первого частичного остатка от деления промежуточного результата на 4. Таким обра зом, перевод промежуточного результата в избыточный код происходит в результате деления промежуточного результата на 4 по схеме с восстановлением остатка. Так как число А в выбранной избыточной системе с ис Ленин можно, записывать как д-.Од (в случае если А - дробь), то для восстановления остатка необходимо произвести его сдвиг на два разряда влево, что и осуществляется приемом на следующем такте содержимого первого и второго выходов блока 8.1 памяти и содержимого (п+1) младших разрядов сумматора-вычитателя 2.1 на регистр 1.2. На втором такте вместе с приемом регистром 1.2 первого частичного ос татка на регистр 4.2 передается содержимое регистра 4.1. Через некоторое время, в результате аналогичных описанных ниже преобразований, на третьем, четвертом и пятом выходах блока 8.2 памяти появляется код второй старшей цифры промежуточного результата.. На третьем такте содержимое регистра 4.2 передается на регистр 4,3, а на регистр 1.3 записывается второй частичный остаток. В этом такте на триггеры 5.1, 6.1 и 7.1 принимается вторая старшая цифра промежуточного результата. Первая старшая цифра для формирования ново го промежуточного результата не используется и позтому никуда не записывается. Она может быть использов на для фиксации переполнения ра рядной сетки. На этом же такте в регистры 1.1 и .4.1 принимаются соот ветственно, числа b и X выражения (2), представленные дополнительными двоичными кодами, причем код числа Ь должен содержать пять знаковых . разрядов. В дальнейшем описанные преобразования псзвторяются для каждого из блоков устройс- ва в течение 2k тактов и, таким образом, на (2k+l)-oM такте на входные узлы первого блока принимаются два последние операнда вычисляемой схемы Горнера. Для формирования результата вы- числения полинома на (2k+3)-eM такте на регистр 1.1. необходимо подать код О, а на регистр 4.1 записать код 0.000.. .01. .В этом же такте на триггеры 5.1, 6,1 и 7.1 принимается код старшей цифры конечного результата. На каждом следs OIцeм такте содержимое регистра 4.1 передается в регистр 4.(i+l) и, в зависимости от содержимого триггеров 5.1, 6.1 и 7.1, складывае,тся или вычитается с содержимым регистров l.i. На ()-eM такте на выходах, связанных с сумматором-вычитателем (+1)-го блока устройства, оказываются пять знаковых и п старших разрядов округленного результата, переведенного в результате описанной операции из квазиканонического избыточного кода в дополнительный двоичный код. На следующем нечетном такте, после подачи такта считывания результата, на входы устройства можно подавать операнды новой схемы Горнера. В то Же: время по четным тактам в устройстве может происходить вычисление другой схемы Горнера. Следовательно, основное преимущество конвейерного метода обработки информации, заключающееся в эффективном использовании аппаратуры многорегистровых устройств, в данном случае сохраняется. Таким образом, наряду с существенным увеличением быстродействия при вычислении одного и того же арифметичес ого выражения типа схемы Горнера за (2k+|+3) такта при помощи предлагаемого устройства по сравнению с {3k+n+6) тактами при помощи известного также имеет место и снижение аппаратурных затрат, а именно, предлагаемое устройство должно состоять из (+2)-х блоков, в то время как известное из (п+5) блоков, при приблизительно одинаковой сложности блоков. Следует также отметить, что из-за возможности одновременного вычисления двух схем Горнера фактическое быстродействие устройства следует (считать равным () тактам. Выполнение арифметических операций в предлагаемом устройстве обеспечивается имеющимися жесткими связями между узлами устройства и не требует дополнительно никакого управления, кроме йодачи синхронизирующих импульсов. Выполнение требуемой арифметической операции над операндами обеспечивается путем подачи этих операндов на соответствующие входы устройства, что обеспечивается внешними по отношению к

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

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

Примечание: Формула изобретения Устройство для одновременного вычисления двух многочленов, содержащее i однотипных вычислительных блоков (i 1, 2, . .. , +2, где п - разрядность операндов), каждый из которых содержит регистр сомножителя, регистр час ичного результата, комбинационный сумматор-вычитатель, блок памяти, первый, второй, третий триггеры, причем в каждом вычислительном блоке тактовые входы первого, второго, третьего триггеров, регистра сомножителя и регистра частичного результата объединены и 1одключены к тактовой шине устройства, выход первого триггера подключен к управляющему входу комбинационного сумматора-вычитателя, четыре старших разряда которого соединены с адресным входом блока памяти выходы регистра сомножителя л-го вычислительного блока соответственно х:оединена с информационными входами регистра сомножителя (т+1)-го вычисПод знаком X подразумевается значение О либо 1-. Когда очередная цифра промежуточного результата в избыточном коде представляет собой 2 либо 2, то значение остатка на выходе блока 8.i памяти повторяет собой значение двух младццих из четырех разрядов, поступающих на входы блока 8, памяти. лительного блока, отличающее с я тем, что, е целью повышения быстродействия, в каждый i-и вычислительный блок устройства дополнительно введен коммутатор, причем информационные входы коммутатора соответственно соединены с выходаи 1И регистра сомножителя, первый управляющий вход коммутатора соединен с выходом второго триггера, второй управляющий вход коммутатора соединен с выходом третьего триггера, выходы регистра частичного результата соединены с соответствующими входами первой группы комбинационного сумматора-вычитателя, четыре старших Входа второй группы которого соединены с выходом старшего разряда коммутатора, (п+1)-ый младший вход второй группы комбинационного сумматора-вычитателя соответственно соединен с (п+1)-ми младшими разрядами коммутатора, третий по {п+3)-ий информационные входы регистра частичного результата (i+l)-ro вычислительного блока соответственно соединены с (п+1)-ми младшими разрядами комбинационного сумматора-вычитателя т-го вычислительного блока, а два старших информационных входа - соответственно с первым и вторым выходами блока памяти, четвертый, пятый и шестой выходы которого соответственно соединены с информационными входами первого, третьего и второго триггеров.

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

4.Авторское свидетельство СССР № 662935, кл. G 06 F 7/38, 1976 (прототип).