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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

;,926650

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву (22) Заявлено 230680 (21) 2945091/18-24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 0705.82. Бюллетень ¹ 17

Дата опубликования описания 070582

fg)j Кп 3

G 06 F 7/52

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

СССР по делам изобретений, и открытий (53) УДК 681. 325 (088.8) (72) Авторы изобретения

Г.М. Луцкий, В. В. Коваленко, A.Н. Долголенко и Т.A. Блинова г. ";, .

:й

Киевский ордена Ленина политехнический инсти т им. 50-летия Велииой Октябрьской социалистическо реэолюции ! (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОДНОВРЕМЕННОГО ВЫЧИСЛЕНИЯ

ДВУХ МНОГОЧЛЕНОВ

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

Известно устройство, с помощью которого можно выполнять арифмети-. ческие операции над последовательностью чисел, в котором описано матричное устройство для ЦВМ. Устройство содержит блоки сложения и вы.— читания с шунтирующим управлением.

Каждый блок имеет два входа операндов, вход переносов, управляющие входы для сложения, вычитания или шунтирования и выходы переноса, а также выход суммы или разности (l).

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

Секция такого двоичного сумматора может содержать контур для опережающего переноса, который также построен на схемах сумматоров (2).

Однако известные устройства обладают низким уровнем совмещений при выполнении арифметических операций и, следовательно, обладают низкой производительностью.

Известно устройство для одновременного выполнения арифметических операций над множеством чисел. Устройство состоит из множества однотипных блоков. Каждый i-ый блок устройства состоит из двух регистров, 10 комбинационного сумматора, двух триггеров и двухвходовой схемы И. С помощью этого устройства возможно вычисление многочлен1а ах + Ьхк "+ сх" +.. ° + kx + т., (1) представленного схемой Горнера ((... (ах + b) x +... ) х + k) x+ 0 (2)

При помощи этого устройства возможно вычисление любого арифметического выражения, содержащего операции сложения и умножения, причем чем меньше арифметическое выражение поддается распараллеливанию, тем с большей эффективностью оно может быть вычислено (3).

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

E. n-разрядного произведения ° На опе. ранды, входящие в выражение (2), накладываются следующие ограничения: 5 все они должны быть положительными числами, десятичная точка должна быть фиксирована после последнего значащего разряда. (В случае выполнения только суммирования последо- 10 вательности чисел десятичная точка может быть фиксирована в любом месте. Из-за возможности выполнения сложения последовательности чисел в дополнительных кодах операнды, под- 15 лежащие сложению, могут быть также и отрицательными числами).

Наиболее близким к предлагаемому является конвейерное устройство, содержащее однотипных вычислитель- gg ных блоков ((= 1,2,..., + 2, где

n — разрядность операндов), каждый из которых содержит регистр сомножителя, регистр частичного результата, комбинационный сумматор-вычитатель, блок памяти, первый, второй, третий триггеры, причем в каждом вычислительном блоке тактовые входы первого, второго, третьего триггеров, регистра сомножителя и регистра 30 частичного-результата объединены и подключены к тактовой шине устройства, вымод первого триггера подключен к управляющему входу комбинационного сумматора-вычитателя, четыре старших разряда которого соединены с адресным входом блока памяти, выходы регистра сомножителя -го вычислительного блока соответственно соединены с информационными входами регистра сомножителя (i +1)-го вы- 40 числительного блока.

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

Однако очередная пара операндов принимается на входы устройства не на каждом такте, а через два такта на третьем после подачи предыдущей 60 пары операндов арифметического выражения ° Два промежуточных такта связаны с необходимостью преобразования промежуточного результата вычисления арифметического выражения,65 представленного в избыточной квазиканонической системе счисления с цифрами 11, 0,1) .

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

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

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

На чертеже представлена структурная схема двух первых вычислительных блоков устройства.

Каждый вычислительный блок устройства содержит (n+5)-разрядный регистр 1. частичного результата, комбинационный сумматор-вычитатель

2., коммутатор З.i, (n+1) -разрядный регистр 4.1 сомножителя, первый, второй и третий триггеры 5., 6.i 7. i блок 8. памяти.

В устройстве тактовые входы триггеров 5.i 6.(, 7., регистра 4. сомножителя и регистра 1. частичного результата объединены и подключены к тактовой шине устройства, выход триггера 5. подключен к управляющему входу комбинационного суьп4атора-вычитателя 2., четыре старших разряда которого соединены с адресным входом блока .8. памяти, выходы регистра 4. сомножителя -ro вычислительного блока соответственно соединены с информационными входами регистра 4. сомножителя (i +1) -ro вычислительного блока, информационные входы коммутатора 3. соответственно соединены с выходами

926650 регистра 4.(сомножителя, первый управляющий вход коммутатора 3.i соединен с выходом триггера б.i второй управляющий вход коммутатора

3. соединен с выходом триггера

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

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

2.1 1-го блока, а два старших информационных входа соответственнос первым и вторым выходами блока памяти 8.1, четвертый, пятый и шестой выходы которого соответственно соединены с информационными входами триггеров 5., 7 ° 1 и 6.1. Комбинационный сумматор-вычитатель 2 ° i представляет собой параллельный комбинационный сумматор-вычитатель с частично групповым переносом. Он может быть реализован на микросхемах типа К155ИПЗ, совместно с микросхемами типа К155ИП4.

Коммутатор 3. содержит (п+2)-разрядную группу элементов 2И-ИЛИ.

Значения старших четырех разря$5 дов сумматора-вычитателя 2.1 являютУстройство работает следующим образом.

Максимальная производительность устройства при вычислении п-разрядных чисел будет в том случае, если устройство состоит из — +2 блоков.

Я.

Все блоки устройства однотипны за исключением последнего, который со- держит только узлы 1.1, 8., при этом регистр частичного остатка 1 состоит только из четырех старших разрядов и выходы всех этих разрядов должны быть соединены со входами блока 8. памяти. Регистры 1.i всех блоков, кроме первого, могут состоять не из (n+5)-ти триггеров, а из (n+3)-х триггеров, при этом к первым входам двух младших разрядов сумматора-вычитателя 2.i .вместо выходов двух младших разрядов регистра 1 ° i должен быть подведен логический нуль.

Выполнение арифметических операций в устройстве происходит в двоичной системе счисления, начиная со старших разрядов, с представлением .промежуточных результатов внутри устройства избыточным квазиканоническим кодом с цифрами 2,1,0,1,2}.

При помощи устроиства возможно одновременное вычисление двух многочленов по схеме Горнера (2), либо одновременное вычисление двух других арифметических выражений, вытекающих из схемы Горнера. При этом по нечетным тактам на входы устройства принимаются операнды первой схемы Горнера, а по четным — второй.

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

10 примере вычисления одной схемы Горнера.

В первом такте на входы регистра частичного остатка 1.1 первого блока подается код числа а, представленный дополнительным двоичным кодом, имеющим пять знаковых разрядов (например, код 1111.ХХХ...XX в случае, если б < О), а на входы регистра сомножителя 4.1 первого блока записывается код числа О. После приема операндов указанными узлами первого блока содержимое регистра 1.1 поступает на входы сумматора-вычитателя 2.1, а на другие входы этого сумматора-вычитателя, в зависимости от содержимого триггеров 5.1 и 6.1, поступает число из регистра 4.1 либо поступает удвоенное содержимое регистра 4.1, либо содержимое регистра

4.1 на сумматор-вычитатель 2.1 не передается вовсе (в триггерах 5. и 6. находится двоично-кодированная цифра избыточного квазиканонического кода с цифрами 2,1,0,1,2j (cMi таблицу) представляющая собой цифру промежуточного результата, причем в триггерах 5. и б.i находится абсолютная величина цифры промежуточного результата, а ее знак содержится в триггере 7. ). Если триггер 5.1

40 находится в единице, а триггер 6.1 в нуле, то на сумматор-вычислитель

2.1 через коммутатор 3.1 передается удвоенное содержимое регистра 4.1, Если триггер 5.1 находится в нуле, 45 а триггер 6.1 в единице, то через коммутатор 3.1 на сумматор-вычитатель передается содержимое регистра

4.1. Если оба эти триггера находятся в нуле, то содержимое регистра

50 4.1 не будет передано на сумматорвычитатель 2.1. При помощи сумматоравычитателя 2 ° 1 в зависимости от триггера 7.1 к содержимому регистра 1.1 прибавляется либо вычитается из

55 него содержимое регистра 4.1. При. этом, если триггер 7.1 находится в нуле, что соответствует положительной цифре промежуточного результата (см. таблицу), то осуществляется суммирование. Если триггер 7.1 находится в единице, что соответствует отрицательной цифре промежуточного результата, производится вычитание.

926650 и — г.! ления можно. записывать как д

A=2 (;Ф 20

1=0 (в случае если A — дробь), то для восстановления остатка необходимо произвести его сдвиг на два разряда влево, что и осуществляется приемом 25 на следующем такте содержимого первого и второго выходов блока 8.1 памяти и содержимого (n+1) младших разрядов сумматора-вычитателя 2.1 на регистр 1.2. 30

На втором такте вместе с приемом регистром 1. 2 первого частичного остатка на регистр 4. 2 передается содержимое регистра 4.1. Через некоторое время, в результате аналогичных описанных ниже преобразований, на третьем, четвертом и пятом выходах блока 8.2 памяти появляется код второй старшей цифры промежуточного

Результата. 40

Выполнение арифметических операций в предлагаемом устройстве обеспечивается имеющимися жесткими связями между узлами устройства и не требует дополнительно никакого управления, кроме йодачи синхронизирующих импульсов. Выполнение требуемой арифметической операции над операндами обеспечивается путем подачи этих операндов на соответствующие входы устройства, что обеспечивается внешними по отношению к ся адресом выборки для блока 8.1 памяти. В зависимости от адреса на выходах блока памяти, в соответствии с таблицей, появляется код первой старшей цифры промежуточного результата, представленного избыточным ква- 5 зиканоническим кодом с цифрами (1,2,0,1,21, а также значение остатка, представляющее собой значение двух старших разрядов первого частичного остатка от деления промежуточного результата на 4. Таким образом, перевод промежуточного результата в избыточный код происходит в результате деления промежуточного результата на 4 по схеме с восста- 15 новлением остатка. Так как число A в выбранной избыточной системе,счисНа третьем такте содержимое регистра 4.2 передается на регистр

4,3, а на регистр 1.3 записывается второй частичный остаток. В этом такте на триггеры 5.1, 6.1 и 7 ° 1

45 принимается вторая старшая цифра промежуточного результата. Перв ая старшая цифра для формирования нового промежуточного результата не используется и поэтому никуда не записывается. Она может быть использована для фиксации переполнения разрядной сетки. На этом же такте в регистры 1.1 и 4.1 принимаются соответственно, числа Ъ и х выражения (2), представленные дополнительными двоичными кодами, причем код числа

Ь должен содержать пять знаковых . разрядов. В дальнейшем описанные

-nðåîáðàçования повторяются для каждого из бЛоков устройства в течение 60

2k тактов и, таким образом, на (2k+1) -ом такте на входные узлы первого блока принимаются два последние операнда вычисляемой схемы

Горнера. 65

Для формирования результата вычисления полинома на (2k+3) -ем такте на регистр 1.1. необходимо подать код 0, а на регистр 4.1 записать код 0.000...01, В этом же такте на триггеры 5.1, 6,1 и 7.1 принимается код старшей цифры конечного результата. На каждом следующем такте содержимое регистра

4.i передается в регистр 4. (i+1) и, в зависимости от содержимого триггеров 5 1, 6 i и 7 1, складывается или вычитается с содержимым регистров 1. i. На (2kt +3)-ем такте на

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

На следующем нечетном такте, после подачи такта считывания результата, на входы устройства можно подавать операнды новой схемы Горнера.

В то же: время по четным тактам в устройстве может происходить вычисление другой схемы Горнера. Следовательно, основное преимущество конвейерного метода обработки информации, заключающееся в эффективном использовании аппаратуры многорегистровых устройств, в данном случае сохраняется °

Таким образом, наряду с существенным увеличением быстродействия при вычислении одного и того же арифметического выражения типа схемы Горнера за (2k+ — +3) такта при помощи .и предлагаемого устройства по сравнению с (3k+n+6) тактами при помощи известного также имеет место и снижение аппаратурных затрат, а именно, предлагаемое устройство должно состоять из (1-+2)-х блоков, в то время как известйое из (n+5) блоков, при приблизительно одинаковой сложности блоков, Следует также отметить, что из-за возможности одновременного вычисления двух схем Горнера фактическое быстродействие устройства следует считать равным (k+1+2) так4 там.

926650 устройству аппаратными средствами.

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

5 (T5.i ) точного

О О

О 0

Х Х

О О

О 0

Х Х

П р и м е ч а н и е: Под знаком Х подразумевается значение О либо 1. Когда очередная цифра промежуточного результата в избыточ° ном коде представляет собой 2 либо 2, то значение эстатка на выходе блока 8.i памяти повторяет собой значение двух младших из четырех разрядов, поступающих на входы блока 8.i памяти.

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

О 0 0 1

О О 1 0

О 0 1 1

О 1 Х Х

1 1 1 1

) 1 1 1

1 1 О 1

1 1 О ° О

1 О Х X

Устройство для одновременного вычисления двух многочленов, содержащее 1 однотипных вычислительных блоков (1=1,2,..., <+2, где n — разрядность операндов), каждый из которых содержит регистр сомножителя, регистр частичного результата, комбинационный сумматор-вычитатель, блок памяти, первый, второй, третий триггеры, причем в каждом вычислительном блоке тактовые входы первого, второго, третьего триггеров, регистра сомножителя и регистра часгичного результата объединены и юдключены к тактовой шине устройства, выход первого триггера подключен к управляющему входу комбинационного сумматора-вычитателя, четыре старших разряда которого соединены с адресным входом блока памяти, выходы регистра сомножителя 1 -го вычислительного блока соответственно ,соединена с информационными входами регистра сомножителя (1+1)-го вычислительного блока, о т л и ч а ю щ ее с я тем, что, е целью повышения быстродействия, в каждый -й вычислительный блок устройства дополнительно введен коммутатор, причем информационные входы коммутатора соответственно соединены с выходами регистра сомножителя, первый управляющий вход коммутатора соединен с выходом второго триггера, второй управляющий вход коммутатора соединен с выходом третьего триггера, выходы регистра частичного результата соединены с соответствующими входами первой группы комбинационного сумматора-вычитателя, четыре старших входа второй группы которого соединены с выходом старшего разряда коммутатора, (п+1)-ый младший вход второй группы комбинационного сумматора- вычитателя соответственно соединен с (пФ1)-ми младшими разрядами коммутатора, третий по (п+3)-ий информационные входы регистра частичного результата (i +1)-го вычисли65 тельного блока соответственно сое9 26650

1. Патент ФРГ 9 2034841, кл. G 06 F 7/38, опублик. 1974, Составитель Л. Медведева

Редактор Н. Кешеля Техред Ж. Кастелевич Корректор A. Дзятко

Заказ 2982/41

Тираж 732 Подписное

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

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

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4 динены с (и+1) -ми младшими разрядами комбинационного сумматора-вычитателя т-го вычислительного блока, а два старших информационных входа — соответственно с первым и вторым выходами блока памяти, четвертый, пятый и шестой выходы которого соответственно соединены с информационными входами первого, третьего и второго триггеров.

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

2. Патент США Р 3535502, 5 кл. G 06 F 7/385, опублик. 1976, 3 . Авторское свидетельство СССР

9 479111, кл. G 06 F 7/52, 1973..

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