Устройство для одновременного вычисления двух многочленов

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик(11 М Кп 3 С Об Г 7/52 Государственный комитет СССР по делам изобретений,и открытий(72) Авторыизобретения Г.М. Луцкий, В.В, Коваленко, А.Н. Долголенко и Т.А. Блинова г."; ,.йКиевский ордена Ленина политехнический инсти тим. 50-летия Велииой Октябрьской социалистическореэолюции(54) УСТРОЙСТВО ДЛЯ ОДНОВРЕМЕННОГО ВЫЧИСЛЕНИЯ ДВУХ МНОГОЧЛЕНОВИзобретение относится к вычислительной технике, в частности к области выполнения арифметических операций в многорегистровых арифметических устройствах, выполненных на узлах с большой степенью интеграции,Известно устройство, с помощью которого можно выполнять арифмети-. ческие операции над последовательностью чисел, в котором описано матричное устройство для ЦВМ. Устройство содержит блоки сложения и вы; читания с шунтирующим управлением. Каждый блок имеет два входа операндов, вход переносов, управляющие входы для сложения, вычитания или шунтирования и выходы переноса, а также выход суммы или разности (1,Известно многовходовое двоичное суммирующее устройство, которое содержит ряд многовходовых двоичных суммирующих секций, каждая из которых охватывает ряд суперсумматоров. Секция такого двоичного сумматора может содержать контур для опережающего переноса, который также постро" ен на схемах сумматоров 2.ОднакО известные устройства обладают низким уровнем совмещений при выполнении арифметических операций и, следовательно, обладают низкойпроизводительностью.Известно устройство для одновременного выполнения арифметическихопераций над множеством чисел, устройство состоит из множества однотипных блоков, Каждый ( -ый блок устройства состоит из двух регистров, 10 комбинационного сумматора, двух триггеров и двухвходовой схемы И. С помощью этого устройства возможно вычисление многочлеаах + Ьх + сх" ++ )сх +, (1)представленного схемой Горнера 15(ах + Ь)х +)х + )с)х+ Р (2)При помощи этого устройства возможно вычисление любого арифметического выражения, содержащего операции.сложения и умножения, причем чемменьше арифметическое выражение поддается распараллеливанию, тем сбольшей эффективностью оно можетбыть вычислено (3.Основной недостаток известногоустройства заключается в том, чтоарифметические операции в нем выполняются с младших разрядов. Этоприводит к существенному снижениюбыстродействия, Так, например дляполучения и старших разрядов произ 926650веденияи-разрядных чисел в устройстве проделывается весь комплексдействий, связанный с получением1 и-разрядного произведения. На опе.ранды, входящие в выражение (2),накладываются следующие ограничения: 5все они должны быть положительнымичислами, десятичная точка должнабыть фиксирована после последнегозначащего разряда, (В случае выполнения только суммирования последовательности чисел десятичная точкаможет быть фиксирована в любом месте. Из-за возможности выполнениясложения последовательности чисел вдополнительных кодах операнды, подлежащие сложению, могут быть такжеи отрицательными числами),Наиболее близким к предлагаемомуявляется конвейерное устройство,содержащееоднотипных вычислительных блоков= 1,2+ 2, гдеи - разрядность операндов), каждыйиз которых содержит регистр сомножителя, регистр частичного результата, комбинационный сумматор-вычитатель, блок памяти, первый, второй,третий триггеры, причем в каждомвычислительном блоке тактовые входыпервого, второго, третьего триггеров, регистра сомножителя и регистрачастичного результата объединены иподключены к тактовой шине устройства, вымод первого триггера подключен к управляющему входу комбинационного сумматора-вычитателя, четырестарших разряда которого соединеныс адресным входом блока памяти, выходы регистра сомножителя-го вычислительного блока соответственносоединены с информационными входамирегистра сомножителя ( +1)-го вычислительного блока,Все операции и этом устройствевыполняются над числами, представленными дополнительными кодами,т.е. операнды, входящие в выражение 45(2), могут быть как положительными,так и отрицательными, Десятичнаяточка может быть фиксирована в любом месте, Выполнение арифметическихопераций в устройстве происходитв полуавтономном режиме вычислений,начиная со старших разрядов., приэтом достигается глубина перекрытияциклов работы блоков устройства привыполнении арифметических операцийв один такт (4,Однако очередная пара операндов принимается на входы устройства не на каждом такте, а через два такта на третьем после подачи предыдущей 60 пары операндов арифметического выраженияДва промежуточных такта связаны с необходимостью преобразования промежуточного результатавычисления арифметического выражения,65 представленного в избыточной квазиканонической системе счисления сцифрами 1,0,1 .Цель изобретения - повышениебыстродействия устройства.Поставленная цель достигаетсятем, что в каждый-й вычислительный блок дополнительно введен коммутатор, причем информационные входыкоммутатора соответственно соединены с выходами регистра сомножителя,первый управляющий вход коммутаторасоединен с выходом второго триггера,второй управляющий вход коммутаторасоединен с выходом третьего триггера, выходы регистра частичного результата соединены с соответствующими входами первой группы комбинационного сумматора-вычитателя, четыре старших входа второй группы которого соединены с выходом старшегоразряда коммутатора, (и+1)-ый младший вход второй группы комбинационного сумматора-вычитателя соответственно соединен с (и+1)-ми младшимиразрядами коммутатора, третий по(и+3)-ий информационные входы регистра частичного результата (+1)-говычислительного блока соответственносоединены с (и+1)-ми младшими разрядами комбинационного сумматора-вычитателя-го вычислительного блока,а два старших информационных входа -соответственно с первым и вторымвыходами блока памяти, четвертый,пятый и шестой выходы которого соответственно соединены с информацион-ными входами первого, третьего ивторого триггеров.На чертеже представлена структурная схема двух первых вычислительных блоков устройства,Каждый вычислительный блок устройства содержит (и+5)-разрядный регистр 1.частичного результата,комбинационный сумматор-вычитатель2. , коммутатор 3.(, (и+1) -разрядный регистр 4. сомножителя, первый, второй и третий триггеры 5.,б.), 7), блок 8.памяти,В устройстве тактовые входы триггеров 5 б 7., регистра 4, сомножителя и регистра 1. частичного результатаобъединены и подключены к тактовой шине устройства, выход триггера 5. подключен к управляющему входу комбинационного суье 4 атора-вычитателя 2 четыре старших разряда которого соединены с адресным входом блока 8. памяти, выходы регистра 4,сомножителя -го вычислительного блока соответственно соединены с информационными входами регистра 4. сомножителя ( +1) -го вычислительного блока, информационные входы коммутатора З. соответственно соединены с выходамирегистра 4( сомножителя, первый управляющий вход коммутатора 3. соединен с выходом триггера 6., вто. рой управляющий вход коммутатора 3. соединен с выходом триггера 7., выходы регистра 1.1 частичного результата соединены с соответствующими входами первой группы комбинационного сумматора-вычитателя 2., четыре старших входа второй группы которого соединены с выходом старшего разряда коммутатора 3.(, (и+1) - ый младший вход второй группы комбийационного сумматора-вычитателя 2. соответственно соединены с (и+1)-ми младшими разрядами коммутатора 3., третий по (и+3)-ий информационные входы регистра 1. частичного результата ( +1)-го вычислительного блока соответственно соединены с (и+1)-ми младшими разрядами комбинационного сумматора-вычитателя 2.1 1-го блока, а два старших информационных входа соответственнос первым и вторым выходами блока памяти 8,1, четвертый, пятый и шестой выходы которого соответственно соединены с информационными входами триггеров 5., 71 и 6.1. Комбинационный сумматор-вычитатель 2представляет собой параллельный комбинационный сумматор-вычитатель с частично групповым переносом. Он может быть реализован на микросхемах типа К 155 ИПЗ, совместно с микросхемами типа К 155 ИП 4Коммутатор 3. содержит (и+2)-разрядную группу элементов 2 И-ИЛИ. Значения старших четырех разря 65 дов сумматора-вычитателя 2.1 являютУстройство работает следующим образом.Максимальная производительность устройства при вычислении п-разрядных чисел будет в том случае, если устройство состоит из - +2 блоков,Ч.Все блоки устройства однотипны за исключением последнего, который со- держит только узлы 1.1, 8., при этом регистр частичного остатка 1 состоит только из четырех старших разрядов и выходы всех этих разрядов должны быть соединены со входами блока 8, памяти. Регистры 1.( всех блоков, кроме первого, могут состоять не из (и+5)-ти триггеров, а из (и+3)-х триггеров, при этом к первым входам двух младших разрядбв сумматора-вычитателя 2,(.вместо выходов двух младших разрядов регистра 11 должен быть подведен логический нульВыполнение арифметических операций в устройстве происходит в двоичной системе счисления, начиная со старших разрядов, с представлением промежуточных результатов внутри устройства избыточным квазиканоническим кодом с цифрами 2,1,0,1,2. При помощи устройства возможноодновременное вычисление двух многочленов по схеме Горнера (2), либоодновременное вычисление двух другихарифметических выражений, вытекающих5 из схемы Горнера. При этом по нечетным тактам на входы устройства принимаются операнды первой схемы Горнера, а по четным - второй,Рассмотрим работу устройства на10 примере вычисления одной схемы Горнера.В первом такте на входы регистрачастичного остатка 1.1 первого блока подается код числа а, представ 15 ленный дополнительным двоичным кодом, имеющим пять знаковых разрядов(например, код 1111.ХХХХХ в случае, если бО), а на входы регистра сомножителя 4.1 первого блока записывается код числа О, После приема операндов указанными узлами первого блока содержимое регистра 1.1поступает на входы сумматора-вычитателя 2.1, а на другие входы этогосумматора-вычитателя, в зависимостиот содержимого триггеров 5,1 и 6.1,поступает число из регистра 4.1 либопоступает удвоенное содержимое регистра 4.1, либо содержимое регистра4.1 на сумматор-вычитатель 2.1 непередается вовсе (в триггерах 5.и 6. находится двоично-кодированнаяциФра избыточного квазиканоническогокода с цифрами 2,1,0,1,2) (смтаблицу) представляющая собой цифрупромежуточного результата, причем втриггерах 5. и 6.1 находится абсолютная величина цифры промежуточного результата, а ее знак содержитсяв триггере 7.). Если триггер 5.140 находится в единице, а триггер 6.1в нуле, то на сумматор-вычислитель2.1 через коммутатор 3.1 передаетсяудвоенное содержимое регистра 4.1,Если триггер 5,1 находится в нуле,45 а триггер 6.1 в единице, то черезкоммутатор 3.1 на сумматор-вычитатель передается содержимое регистра4.1. Если оба эти триггера находятся в нуле, то содержимое регистра50 41 не будет передано на сумматорвычитатель 2.1, При помощи сумматоравычитателя 21 в зависимости от триггера 7.1 к содержимому регистра 1.1прибавляется либо вычитается из55него содержимое регистра 4.1. Приэтом, если триггер 7.1 находится внуле, что соответствует положительной цифре промежуточного результата (см. таблицу), то осуществляетсясуммирование. Если триггер 7.1 находится в единице, что соответствуетотрицательной цифре промежуточногорезультата, производится вычитание.(в случае если А - дробь), то длявосстановления остатка необходимопроизвести его сдвиг на два разрядавлево, что и осуществляется приемом 25на следующем такте содержимого первого и второго выходов блока 8.1памяти и содержимого (и+1) младшихразрядов сумматора-вычитателя 2,1на регистр 1.2. 30На второМ такте вместе с приемомрегистром 1.2 первого частичного остатка на регистр 4.2 передается содержимое регистра 4.1. Через некоторое время, в результате аналогичных описанных ниже преобразований, на третьем, четвертом и пятом выходах блока 8.2 памяти появляется код второй старшей цифры промежуточного Результата, 40 Выполнение арифметических операций в предлагаемом устройстве обеспечивается имеющимися жесткими связями между узлами устройства и не требует дополнительно никакого управления, кроме йодачи синхронизирующих импульсов. Выполнение требуемой арифметической операции над операндами обеспечивается путем подачи этих операндов на соответствующие входы устройства, что обеспечивается внешними по отношению к ся адресом выборки для блока 8.1памяти. В зависимости от адреса навыходах блока памяти, в соответствиис таблицей, появляется код первойстаршей цифры промежуточного результата, представленного избыточным квазиканоническим кодом с цифрами(12012) а также значение остатка, представляющее собой значениедвух старших разрядов первого частичного остатка от деления промежуточного результата на 4. Таким образом, перевод промежуточного результата в избыточный код происходитв результате деления промежуточногорезультата на 4 по схеме с восстановлением остатка. Так как число Ав выбранной избыточной системе,счисНа третьем такте содержимое регистра 4.2 передается на регистр 4,3, а на регистр 1,3 записывается второй частичный остаток. В этом такте на триггеры 5.1, 6.1 и 7145 принимается вторая старшая цифра промежуточного результата. Первая старшая цифра для формирования нового промежуточного результата не используется и поэтому никуда не записывается. Она может быть использована для фиксации переполнения разрядной сетки. На этом же такте в регистры 1.1 и 4,1 принимаются соответственно, числа Ъ и х выражения (2), представленные дополнительными 55 двоичными кодами, причем код числа Ь должен содержать пять знаковых . разрядов. В дальнейшем описанные преобразования повторяются для каждого из бЛоков устройства в течение 60 2 К тактов и, таким образом, на (2)+1) -ом такте на входные узлы первого блока принимаются два последние операнда вычисляемой схемы Горнера. 65 Для формирования результата вычисления полинома на (21+3)-ем такте на регистр 1,1. необходимо подать код 0 а на регистр 4.1 записать код ф 0,00001 фф, В этом же такте на триггеры 5.1, 6,1 и 7,1 принимается код старшей цифры конечного результата. На каждом следующем такте содержимое регистра 4.1 передается в регистр 4,( +1) и, в зависимости от содержимого триггеров 5,1 6. и 7.1складывается или вычитается с содержимым регистров 1,1, На (2)с+ +3)-ем такте на выходах, связанных с сумматором-вычитателем (-+1)-го блока устройстива, оказываются пять знаковых и п старших разрядов округленного результата, переведенного в результате описанной операции из квазиканонического избыточного кода в дополнительный двоичный код.На следующем нечетном такте, после подачи такта считывания результата, на входы устройства можно подавать операнды новой схемы Горнера. В то же время по четным тактам в устройстве может происходить вычисление другой схемы Горнера. Следовательно, основное преимущество конвейерного метода обработки информации, заключающееся в эффективном использовании аппаратуры многорегистровых устройств, в данном случае сохраняетсяТаким образом, наряду с существенным увеличением быстродействия при вычислении одного и того же арифметичес)ого выражения типа схемы Горнера за (2 с+ - +3) такта при помощи.ипредлагаемого устройства по сравнению с (31+и+6) тактами при помощи известного также имеет место и снижение аппаратурных затрат, а именно, предлагаемое устройство должно состоять из (.+2)-х блоков, в то время как известйое из (и+5) блоков, при приблизительно одинаковой сложности блоков, Следует также отметить, что из-за возможности одновременного вычисления двух схем Горнера фактическое быстродействие устройства следуетсчитать равным (К2) так 4 там.926650 5(Т точног О 1 О 2 Х О О 1 1 1 1 1 1 О 1 1 1 О О О 2 Х ние О либоультата в и 2, то знач повторяетазрядов, пос Когдабыточм Х подраз цифра пром представля а выходе б мевается знач ежуточного ре т собой 2 либ ока 8.1 памят х из четырехпамяти. знак една коде тка ение на в и е: имеч н бойупаюзн ШИ двух младшоды блока Формула изобретен ционнотыре с невы с выходы вычисл ,соедин регист устройству аппаратными средствами.Таким образом, предлагаемое устройство предназначено в основном для Устройство для одновременного вычисления двух многочленов, содержащее 1 однотипных вычислительных блоков (1 =1,2.+2, где и - разрядность операндов), каждый из которых содержит регистр сомножителя, регистр час."ичного результата, комбинационный сумматор-вычитатель, блок памяти, первый, второй, третий триггеры, причем в каждом вычислительном блоке тактовые входы первого, второго, третьего триггеров, регистра сомножителя и регистра часгичного результата объединены и юдключены к тактовой шине устройства, выход первого триггера подключен к управляющему входу комбинаго сумматора-вычитателя, четарших разряда которого соедиадресным входом блока памяти,регистра сомножителя 1 -гоительного блока соответственноенй с инФормационными входамира сомножителя (1+1)-го вычисиспользования его в вычислительныхсистемах в качестве специализированного арифметического блока. лительного блока, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в каждый 1-й вычислительный блок устройства дополнительно введен коммутатор, причем информационные входы коммутатора соответственно соединены с выходами регистра сомножителя, первый управляющий вход коммутатора соединен с выходом второго триггера, второй управляющий вход коммутатора соединен с выходом третьего триггера, выходы регистра частичного результата соединены с соответствующими входами первой группы комбинационного сумматора-вычитателя, четыре старших входа второй группы которого соединены с выходом старшего разряда коммутатора, (и+1)-ый младший вход второй группы комбинационного сумма 60 тора-вычитателя соответственно соединен с (и+1)-ми младшими разрядами коммутатора, третий по (и+3)-ий информационные входы регистра частичного результата (1+1)-го вычисли тельного блока соответственно сое9 26650 ставитель Л. Медведевахред Ж. КастелевичКорректор А, Дзятко едактор Н. Кешеля аказ 2982/4 Тираж 732ИГосударственного комитета делам изобретений и открыти осква, Ж, Раушская наб.,писноеСР ВНИ 4/5 113035,иал ППП П нт, г, Ужгород, ул. Проектная, 4 динены с (и+1)-ми младшими разрядамикомбинационного сумматора-вычитателят-го вычислительного блока, а двастарших информационных входа - соответственно с первым и вторым выходами блока памяти, четвертый, пятый ишестой выходы которого соответственно соединены с информационными входами первого, третьего и второготриггеров,Источники информации,принятые во внимание при экспертизе 1. Патент ФРГ Ф 2034841,кл. С 06 Г 7/38, опублик. 1974, 2, Патент США 9 3535502,5 кл, С 06 Г 7/385, опублик. 1976,3. Авторское свидетельство СССРР 479111, кл, С 06 Г 7/52, 1973, .4. Авторское свидетельство СССР0Р 662935, кл, С 06 Г 7/38, 1976