Конвейерное устройство для выполне-Ния АРифМЕТичЕСКиХ ОпЕРАций НАдМНОжЕСТВОМ чиСЕл Советский патент 1981 года по МПК G06F7/38 

(54) КОНВЕЙЕРНОЕ УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ НАД МНОЖЕСТВОМ ЧИСЕЛ

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

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

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

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

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

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

+

10

.+ .,

+ kx + е

+ сх

представленного в следующем виде:

(..СоХ4Ь)-Х-ь...Х+К), (t)

15

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

Количество тактов, необходимое для вычисления арифметического выражения зависит в основном от количест25ва операндов, так как независимо от того, сколько разрядов необходимо получить на выходе арифметического устройства, арифметическое выражение в нем вычисляется всегда с К п 30

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

Недостатком известного устройства является то, что арифметическое выЛ1,

V

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

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

Поставленная цель достигается тем, что в устройстве, содержащем п каскадов (п-разрялность чисел), причем каждый каскад содержит первый регистр частичного результата,первый регистр сомножителя, первый сумматор первый управлякядий триггер, первый триггер, причем выходы первого регистра частичного результата соединены с входами первого .сумматора., первая шина тактовых импульсов устройства соединена с тактовыми входами этих триггеров и регистров, каждый каскад устройства содержит второй регистр частичного результата, первый и второй регистры переносов, второй регистр сомножителя, первый и второй регистры делителя, второй сумматор, первый и второй блоки постоянной памяти, первый и второй преобразователи прямого кода в дополнительный,элемент ИЛИ, одиннадцать триггеров, второй управляющий триггер, причем выхо.ды первого, второго, третьего и четвертого триггеров соединены соответственно с входами седьмого, восьмого девятого и десятого триггеров , выходы пятого и шестого триггеров подключены к управляющим входам первого преобразователя прямого кода в дополнительный, входы старших разрядов которого соединены с выходами первог регистра сомножителя, а вход младшего разряда - с выходом элемента ИЛИ, входы которого соединены с выходом младшего р.азряда первого регистра сомножителя и выходом первого управляющего триггера, который подключен также к управляющему входу первого блока постоянной памяти, входы которго соединены с выходами четырех старших разрядов первого сумматора, а выходы .- с входами одиннадцатого и двенадцатого триггеров,входыпервого сумматора соединены с выходами первого регистра переносов и выхбдаМи первого преобразователя прямого кода в дополнительный, выходы первог сумматора соединены с входами второго регч1стра частичного результата и второго регистра переносов, выходы первого регистра делителя соединены с входами второго регистраделителя, .выходы которого соединены с входами первого регистра делителя следующего каскада устройства и входами старших разрядов второго преобразователя прямого кода в дополнительный, вход млади1его разряда которого соединен с выходом второго управляющего триггера,; а управляющие входы - с выходами одиннадцатого и двенадцатого триггеров, выходы второго преобразователя прямого кода в дополнительный соединены с входами второго сумматора, другие входы которого соединены с выходами второго регистра переносов и второго регистра частичного результата, выходы переносов (п+2) младших разрядов второго сумматора соединены с входами (п+2) старших разрядов первого регистра переносов следующего каскада, выходы суммы (п+2) младших разрядов второго сумматора соединены с входами (п+2) старших разрядов первого регистра частичного результата следующего каскада, выходы седьмого, восьмого, девятого, десятого, одиннадцатого и двенадцатого триггеров подключены к входам второго .блока постоянной памяти, выходы которого соединены соответственно с входами пятого и шестого триггеров каскада,предшествующедго предыдущему и первого, второго, третьего и четвертого триггеров следующего каскада, выход .-первого управляющего триггера соединен с входом второго управляющего триггера, выход которого подключен к входу первого управляющего триггера следующего каскада, выходы первого регистра сомножителя подключены к входам второго регистра сомножителя, выходы которого подключены к входам первого регистра сомножителя следующего каскада, тактовые входы второго третьез о, четвертого, пятого и шестого триггеров, первого регистра переносов и первого регистра делителя соединены с первой шиной тактовых импульсов устройства, тактовые входы седьмого, восьмого, девятого, десятого, одиннадцатого и двенадцатого триггеров, BTopoi:o регистра сомножителя, второго регистра частичного результату, второго регистра делимого и второго управляющего триггера соединены с ВТОРО.Й шиной тактовых импульсов устройства.

На чертеже изображена функциональная схема первых двух каскадов устройства. Первый каскад устройства состоит из первого 1, второго 2, третьего 3, четвертого , пятого 5-, и шес того 6, триггеров первого регистра 7 переносов, первого регистра 8 частичного результата, первого регистра 9 сомножителя, первого регистра 10 -делителя, первого управл щего триггера 11, первого преобраз вателя 12 прямого кода в дополнител ный, элемента 13-1 ИЛИ, первого блок 14-, постоянной памяти, первого сумматЪра 15х., седьмого триггера 16 , восьмого триггера 17, девятого три гера 18, десятого триггера 19,, одиннадцатого триггера 20, двенадц того триггера 21, второго регистра 22 переносов, второго регистра 23 частичного результата второго регист ра 24 сомножителя второго регистра 25 делителя, второго управляющего триггера 26, второго преобразователя 27, прямого кода в дополнительный второго блока 28., постоянной памяти и второго сумматора 29 . Выходы триггеров 1, 2., 3 и 4 связаны соответственно с входами триггеров 16 , 17, 18 и 19 , выходы триггеров 5 и 6 - с управляющи ми входами преобразователя 12-j, выходы регистра 7 - с первыми входами сумматора 15 , выходы регистра 8 | - с вторыми, входами сумматора 15 выходы регистра 9, - с (п+3) старшими разрядами (п+4) разрядного преобразователя 12. , а также с входами регистра 24 , выходы регистра 10 - с входами регистра 25.-|, выход триггера 11.., - с вторым входом элемента 13 ИЛИ, а также с входом триг гера 26 и управляющим входом блока 14 памяти, выход элемента 13, ИЛИ с входом младшего разряда преобразователя 12-,, (п+3) старших выхода преобразователя 12 с третьими входа ми сумматора 15, выход младшего разряда преобразователя 12-1 - с четвертым входом младшего разряда сумматора 15 , выходы четырех старших разрядов сумматора 15 - с входами блока 14, первые выходы (переноса) сумматора 15 - с входами регистра 22 , вторые выходы (суммы) сумма-тора 15 - с входами регистра 23, первый выход блока 14 - с входом триггера 20.,, второй выход блока 14 с входом триггера 21, выходы триггеров - с первыми четырьмя входами блока 28 , выходы триггеров 20,, и 21 - с управляющими входами преобразователя 27 , а также, соответственно, с пятым и шестым входом блока 28, выходы регистра 32., - с входами сумматора 29., выходы регистра 24.., - с входами регистра 9/ следующего каскада, выходы регистра 25 - с входами (п+3) разрядов (п+4) разрядного преобразователя 27, п входами регистра 10а, выход тригге- ; ра 2б-( - с входом младшего разряда преобразователя 27 и входом триггера , (п + З) старших выхода преобразователя 27 - с входами сумматора 29,, выход младшего разряда преобразователя 27 - с входами сумматора 29 , выход младшего разряда преобразователя с входом младшего разряда сумматора 29 , первые выходы (п+2) младших разряда суммахора 29 - с входами (п+2) старших разрядов регистра 1, вторые выходы (п+2) младших разрядов сум|матора 29, - с входами (п+2) старших разрядов регистра 8, первый выход блока 28 -.с входами триггера 6, второй выход блока 28-, - с входами триггера третий, четвертый, пятый, шестой выходы блока 28-, - соответственно с входами триггеров 1, 3, б и 4, Тактовые входы триггеров 1-6 и 11 и регистров 7-10 каждого каскада соединены с первой шиной тактовых импульсов устройства, тактовые входы триггеров 16-21 и 26 и регистров 22-25 каждого каскада соединены с второй шиной тактовых импульсов устройства. Разрядность всех регистров и сумматоров равна (п+3), где п - разрядность операндов. При помощи устройства возможно вычислениеполинома P...(((i-x.,.Vb,).)...,(a) при условии, что операнды у - норализованные положительные коды. На первом полутакте первого така числа а представенные дополнительным модифицированным двоичным кодом, имеющим три знаовых разряда, принимаются соответтвенно на регистры 7, 8, 9.., и 10 триггеры 5., , 6 и 11 заносится од 1. Триггеры 5 и 6 служат ля хранения очередной цифры частичого результата, представленного изыточным квазиканоническим кодом с ифрами 0,1,IJ (ПОЭТОМУ занесению ода 1 на триггеры 5 и 6-) соотетствует установление их в состояия, находящиеся в соответствии с абл.1. Таблица

На втором полутакте первого такта содержимое триггера 11. передается на триггер 26, содержимое регистров 10 и 9-1 .- соответственно на регистры 25 и 24., , а содержимое регистров 8 и 7 413рез сумматор 15-, на регистры 22 и 2J, причем в зависимости от содержимого триггеров 5 и 6 к содержимому регистров 7 и 8 может быть прибавлено.или вычтено из него содержимое регистра 9-, . Прибавление содержимого регистра 9 к содержимому регистров 8 происходит в том хзлучае, если в триггерах 5., и б-, за(писан код 1, вычитание - если в триггерах 5 и 6,, записан код 1. Требуемая операция обеспечивается преобразователем 12, который осуществляет в зависимости от управляющих входов передачу на сумматор 15 содержимого регистра 9 или же дополнительного кода содержимого регистра 9 . Одновременно блоком 14 в- зависимости от вь1ходов четырех старших разрядов сумматора 15 и при условии, что в триггере 11 записан код 1, вьщеляется старшая цифра частичного результата в соответствии с табл.2, код которой на втором полутакте первого такта записывается

в триггерах 20i и 211.

Таблица 2

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

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

В течение первого полутакта второго такта осуществляется передача содержимого триггеров и 26 и регистров , на соответствующие триггеры и 11 и регистры 7-2-102 второго каскада. В процессе этой передачи осущес;гвляется деление цифры частичного результата, полученной на предыдущем полутакте на число. Хранившееся до этого в регистре 2Ь . Преобразователь 27-, Обеспечивает передачу содержимого регистра 25 на сумматор 29, если в триггерах 20- и 21,, записан код 1, и дополнительного кода содержимого этого регистра, если в триггерах 20 и 21 записан код 1. В течепие этого же полутакта на регистры заносится код О.

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

В первом полутакте четвертого такта содержимое регистров триггера 26 -j передается на регистры Од и триггер 11-, г а на регистры

у,. При этом

ХдИ

коды чисел а

Я

на триггер 11 заносится код 1, а на триггеры 5 и 6 заносится с блока 283 первая преобразованная цифра частичного результата.

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

Цифры частичного результата до преобразоВания

уь. ит,7 ,Zl-

1 1

О 1

1 1 Примечание. Описанная последовательность из трех тактов повторяется для каждого из п каскадов.для четверок операндо Для формирования результата необ ходимо в регистры 7, , 8 , и lOi , а также в триггер 11., с помощью устройства управления записать код О а в регистр 9 подать код 000,000.. На каждом следующем такте содержимо регистра 9,- подается в регистр 9-;+,, и., в зависимости от содержимого геров 3 « и складываясь или вычитаясь с содержимым регистров 7j и 8-, через (п+2) такта достигает выходов регистра сомножителя из конвейерного устройства, при этом на . выходах устройства, связанных с сум матором 29 , окажутся одинаковыми (п+2) старших разряда кода результата, переведенного в результате-опе рации из квазиканоничеокого избыточ ного кода в дополнительный двоичный код. При этом результат получается в виде двух чисел: суммы и переноса Если же результат необходим в виде одного числа, он может быть получен путем дополнительного прохода через устройство. Старшие (п+2) разрядов арифметического выражения вида (2),содерЬкащего 4& чисел, могут быть получены при помощи устройства через (36+П+2) такта, при этом на (Зе.+2)-о также можно принимать новую последовательность чисел.

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

Цифры частичного результата после преобразования

(%У 1 ii

.

о

1 о

1 А и В - числа из множеств а О - числа из множества числа из множества o, жества 1,0,1:}, С и тва l,0j , Е и F При помощи устройства возможно вычисление выражения (2) последовательно, при помощи его возможно вычисление любого арифметического выражения, связанного операциями умножения, сложения, вычитания и деления. На следующем такте после подачи тактга формирования результата можно принимать новую последовательность чисел. Предлагаемое устройство, вычисляя одно и тоже арифметическое выражение за гораздо меньшее количество тактов, чем известное,обладает значительно большей производительностью-и при этом может состоять из гораздо меньшего количества однотипных блоков. Кроме того, отпадает необходимость в том, чтобы все операнды выражения, подлежащего вычислению, были обязательно положительными дробями. Формула изобретения Конвейерное устройство для выполнения арифметических операций над множеством чисел, сЬдержащее п кадкадов (п-разрядность чисел), причем каждый каскад содержит первый регистр частичного результата, первыйрегистр сомножителя, первый сумматор, первый управляющий триггер, первый риггер, причем выходы первого регистра частичного результата соединены с входами первого сумматора, первая шина тактовых импульсов устройства соединена с тактовыми входами триггеров и регистров, от л ич а ю щ е с я тем, что, с целью увеличения скорости вычисления арифметических выражений, каждый каскад устройства содержит второй регистр частичного результата, первый и второй регистры переносов, второй ре.гистр сомножителя, первый и второй регистры делителя, второй сумматор, первый и-второй блоки постоянной памяти, первый и второй преобразователи прямого кода в дополнительный, элемент ИЛИ, одиннадцать триггеров, второй управляющий триггер, причем выходы первого, второго, третьего и четвертого триггеров соединены соответственно с входами седьмого, восьмого, девятого и десятого триггеров, выходы пятого и шестого триггеров подключены к управляющим входам первого преобразователя прямого кода в дополнительный, входы старших разрядов которого соединены с выходами первого регистра сомножителя, а вход младшего разряда - с выходом элемента ИЛИ, входы которого соединены с выходом младшего разряда первого регистра сомножителя и выходом первого управляющего триггера, который подключен также к управляющему входу первого блока постоянной памяти, входы котооого соединены с выходами четырех старших разрядов первого сумматора, а выходы - с входами одиннадцатого и двенадцатого триггеров, входы первого сумматора соединены с выходами первого регистра переносов и выходами первого преобразователя прямого кода в дополнительный, выходы первого сумматора соединены с входами второго регистра частичного результата и второго регистра переносов, выходы первого регистра делителя соединены с входамл второго регистра делителя выходы которого соединены с входами первого регистра делителя.следующего каскада устройства и входами старших разрядов второго преобразова теля прямого кода в дополнительный, вход младшего разряда которого соединен с выходом второго управляющего триггера, а управляющие входы г с выходами одиннадцатого и двенадцатого триггеров, выходы

. . i

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

o разрядов второго сумматора соединены с входами (п+2) старших разрядов первого регистра частичного результата следующего каскада, выходы седьмого, восьмого, девятого,

5 десятого, одиннадцатого и двенадцатого триггеров подключены к входам второго блока постоянной памяти, выходы которого соединены соответственно с входами пятого и шестого

0 триггеров каскада, предшествующего предыдущему и первого, второго, третьего и четвертого триггеров следующего каскада, выход первого упра вллющего триггера соединен с входом второго управляющего триггера, выход

5 которого подключен к входу первого управляющего триггера следующего каскада, выходы первого регистра сомножителя подключены к входам второго регистра сомножителя, выходы ко0торого подключены к входам первого регистра сомножителя следующего каскада, тактовые входы второго, третьего, четвертого, пятого и шестого триггеров, первого регистра переносов

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

5

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

3.Авторское свидетельство СССР 479111, кл. G 06F 7/52, 1973 (йрототип).