Конвейерное устройство для выполне-ния арифметических операций надмножеством чисел
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТРРСКРМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
G 06 F 7/38
Государственный комитет
СССР по делан изобретений и открыти и (2З) Приоритет
Опубликовано 230781. Бюллетень Мо27
Дата опубликования описания 23. 07. 81 (53) УДК 681 325 (088.8) (72) Авторы изобретения
Г.М. Луцкий, М.А. Вилкул и A.Н. Долголе
Киевский ордена Ленина политехнический им. 50-летия Великой Октябрьской социа еволю ии (71) Заявитель (54) КОНВЕЙЕРНОЕ УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ
АРИФМЕТИЧЕСКИХ OIIEPAIJHA НАД МНОЖЕСТВОМ
ЧИСЕЛ (...(аХ+Ы X+...)Х+К)Х6, () Изобретение относится к вычисли тельной технике и может быть использовано для выполнения арифметических операций в многорегистровых арифметических устройствах, выполненных на узлах .с большой степенью интеграции.
Известно двоичное суммирующее устройство, которое содержит ряд многовходных двоичных суммирующих секций, каждая из которых .охватывает, ряд суперсумматоров. Секция такого двоичного сумматора может содержать контур для опережающего переноса, который также построен на схемах сумматоров $1) .
Известны также многорегистровые устройства, основанные на так называемом конвейерном методе обработки информации. Эти устройства допускают одновременное выполнение арифметических операций над множеством пар операндов и обладают гораздо большей производителькостью по сравнению с предыдущими 2 .
Однако при вычислении арифметических выражений, содержащих более двух операндов, производительность устройств снижается. 30
Наиболее близким к изобретению является конвейерное устройство для одновременного выполнения арифметических операций над множеством чисел, содержащее регистр сомножителя, регистр частичного результата, сумматор, элемент И и триггеры.
С помощью этого устройства возможно вычисление .полинома ах + Ьх +
n-r
+ скат -+ ... + kx + 0, представленного в следующем виде: т.е. возможно вычисление арифметического выражения, содержащего любую последовательность операций сложения и умножения. При этом kn — разрядное произведение т,и — разрядных чисел может быть получено за (6(n+ )+K) тактов, где k = 1,2,3,...;В.
Количество тактов, необходимое для вычисления арифметического выражения зависит в основном от количества операндов, так как независимо от того, сколько разрядов необходимо получить на выходе арифметического устройства, арифметическое выражение в нем вычисляется всегда с с п
849205 разрядной точностью, так как арифметические операции над множеством чисел выполняются с младших разрядов.
Получение 8 и — разрядного произведения 8 n — разрядных чисел требуется лишь в некоторых специализированных вычислителях,.в основном же требуется получение лишь и, или
2п-старших разряда произведения (3).
Недостатком известного устройства является то, что арифметическое выМ ажение нычисляется с точностью до младшего разряда результата, хотя нам практически почти всегда необходимы только старшие разряды результата. Это приводит к существенному увеличению времени вычисления одного арифметического выражения и значительному уменьшению .производительности устройства.
Цель изобретения — увеличение скорости вычисления арифметических выражений путем выполнения арифметических операций над множестном чисел, начиная со cTàðøèõ разрядов.
Поставленная цель достигается тем, что н устройстве, содержащем и каскадов (и-разрядность чисел), причем каждый каскад содержит первый .регистр частичного результата, первый регистр сомножителя, первый сумматор, первый управляющий триггер„ первый триггер, причем выходы первого регистра частичного результата соединены с входами первого сумматора, первая шина тактовых импульсов устройства соединена с тактовыми входами этих триггеров и регистров, каждый каскад устройства содержит второй регистр частичного результата, первый и второй регистры переносов, второй регистр сомножителя, первый и второй регистры делителя, второй сумматор, первый и второй блоки постоянной памяти, первый и второй преобразонатели прямого кода в дополнительный,элемент ИЛИ, одиннадцать триггеров, второй управляющий триггер, причем выхоцы.первого, второго, третьего и четвертого триггеров соединены соответственно с входами седьмого, восьмого, девятого и десятого триггеров, выходы пятого и шестого триггеров подключены к управляющим входам первого преобразователя прямого кода в дополнительный, входы старших раэрядон которого соединены с выходами первого регистра сомножителя, а вход младшего разряда — с выходом элемента ИЛИ, входы которого соединены с выходом младшего разряда первого регистра сомножителя и выходом первого управляющего триггера, который подключен также к управляющему входу первого блока постоянной памяти, входы которо го соединены с выходами четырех старших разрядов первого сумматора, а выходы — с входами одиннадцатого и двенадцатого триггеров, входы пер5 !
О
ЗО
65 ного сумматора соединены с выходами первого регистра переносов и выходами первого преобразонателя прямого кода в дополнительный, выходы первого сумматора соединены с входами второго регистра частичного результата и второго регистра переносов, выходы перного регистра делителя соединены с входами второго регистра делителя, выходы которого соединены с входами первого регистра делителя следующего аскада устройстна и входами старших . азрядов второго преобразователя прямого кода в дополнительный, вход младшего разряда которого соединен с выходом второго управляющего триггера, а управляющие входы — с выходами одиннадцатого и двенадцатого триггеров, выходы второго преобразователя прямого кода в дополнительный соединены с входами второго сумматора, другие входы которого соединены с выходами второго регистра переносов и второго регистра частичного результата, выходы переносов (и+2) младших разрядов второго сумматора соединены с входами (и+2) старших разрядов первого регистра переносон следующего каскада, выходы суммы (и+2) младших разрядов второго сумматора соединены с входами- (и+2) старших разрядов первого регистра частичного результата следующего каскада, выходы седьмого, восьмого, девятого, десятого, одиннадцатого и двенадцатого триггеров подключены к входам второго .блока постоянной памяти, выходы которого соединены соответственно с входами пятого и шестого триггеров каскада,предшествующего предыдущему и первого, второго, третьего и четвертого триггерон следующего каскада, выход .,первого управляющего триггера соединен с входом второго управляющего триггера, выход которого подключен к входу первого управляющего триггера следующего каскада, выходы первого регистра сомножителя подключены к входам второго регистра сомножителя, выходы которого подключены к входам первого регистра сомножителя следующего каскада, тактовые входы второго, третьего, четвертого, пятого и шестого триггеров, первого регистра переносов и первого регистра делителя соединены с первой шиной тактовых импульсов устройства, тактовые входы седьмого, восьмого, девятого, десятого, одиннадцатого и двенадцатого триггеров, второго регистра сомножителя, второго регистра частичного результата, второго регистра делимого и второго управляющего триг- гера соединены с второй шиной тактовых импульсов устройства.
На чертеже изображена функциональная схема первых двух каскадов уст ройства.
849205
Первый каскад устройства состоит из первого 11, второго 2„, третьего
31, четвертого 4 1, пятого 51 и шестого б, триггеров первого регистра
71 переносов, первого регистра 8„ частичного результата, первого регистра 9 1 сомножителя, первого регистра 101 делителя, первого управляющего триггера 11„, первого преобразователя 12„прямого кода в дополнительный, элемента 131 ИЛИ, первого блока
14 1 постоянной памяти, первого сумматора 15, седьмого триггера 16 восьмого триггера 17„, девятого тригГера 181У десятого триггера 19 одиннадцатого триггера 20 двенадца1 того триггера 211, второго регистра
22 переносов, второго регистра 23
1 частичного результата второго регист1 ра 24„сомножителя, второго регистра
25„. делителя, второго управляющего триггера 26„, второго преобразовате- 20 ля 271 прямого кода в дополнительный второго блока 28„ постоянной памяти и второго сумматора 291 .
Выходы триггеров 1„, 2,, 3 „ и 4., связаны соответственно с входами 25 триггеров 16,, 17, 18 „ и 191, выходы триггеров 5 и 6 — с управляющи1 1 ми входами преобразователя 12„, выходы регистра 7 — с первыми входа1 ми сумматора 15„, выходы регистра
8 „ - с вторыми. входами сумматора 15 выходы регистра 9, — с (n+3) старшими разрядами (и+4) разрядного преобразователя 121, а также с входами регистра 24„, выходы регистра
101 — с входами регистра 25.1, выход триггера 111 — с вторым входом элемента 13„ ИЛИ, а также с входом триггера 26 „ и управляющим входом блока
14„ памяти, выход элемента 13., ИЛИ— с входом младшего разряда преобразо- 40 вателя 12„, (и+3) старших выхода .преобразователя 12„ с третьими входами сумматора 15„, выход младшего разряда преобразователя 12.1 — с четвертым входом младшего рцэр да сум- 45 матора 15, выходы четырех старших разрядов сумматора 15„ - с входами блока 14„, первые выходы (переноса) сумматора 15„ — с входами регистра
22„, вторые выходы (суммы) сумма-. тора 15„ — с входами регистра 23„, первый выход блока 14 — с входом триггера 20„, второй выход блока 14„ с входом триггера 21„, выходы триггеров 16„ -191 — с первыми четырьмя входами блока 28„, выходы триггероВ
201 и 21„ — с управляющими входами преобразователя 27„, а также, сооТветственно, с пятым и шестым входом блока 28, выходы регистра 321 — с входами сумматора 291, выходы регист- N ра 241 - с входами регистра 92 следующего каскада, выходы регистра
25Ä (n+3) разрядов (и+4) разрядного преобразователя 27„, п входами регистра 10 ., выход тригге- 65 ра 26 — с входом младшего разряда преобразователя 27„ и входом триггера 11, (и+3) старших выхода преобразователя 27„ — с входами сумма тора 29„,, выход младшего разряда преобразователя 27 - с входами сум1 матора 29„, выход младшего разряда преобразователя 27„- с входом младшего разряда сумматора 29„, первые выходы (и+2) младших разряда сумма.ора 29„ — с входами (n+2) старших разрядов регистра 7, вторые выходы (n+2) младших разрядов сум:матора 29„ — с входами (и+2) старших разрядов регистра 8, первый выход блока 28„ †. C входами триггера б„ второй выход блока 28, — с входами триггера 5 . третий, четвертый, пятый, шестой выходы блока 281 — соответственно с входами триггеров
2, 3«6 и 4 . Тактовые вхбды триггеров 1-6 и 11 и регистров 7-10 каждого каскада соединены с первой шиной тактовых импульсов устройства, тактовые входы триггеров 16-21 и 26 и регистров 22-25 каждого каскада соединены с второй шиной тактовых импульсов устройства.
Разрядность всех регистров и сумматоров равна (n+3), где n — разрядность операндов.
При помощи устройства возможно вычисление полинома
Р=... (((1. Х +а +Ь ) — + Ь ) — +П, Ь +"- > (О
Хг "ь
2 при условии, что операнды y — нормализованные положительные коды.
На первом полутакте первого такта числа а1, Ь1, х1 и у1, представленные дополнительным модифицированным двоичным кодом, имеющим три знаковых разряда, принимаются соответственно на регистры 7„, 81, 9„ и 101
В триггеры 5„, б„ н 11„ заносится код "1". Триггеры 5 и б служат для хранения очередной цифры частичного результата, представленного избыточным квазиканоническим кодом с цифрами (0,1,1l поэтому занесению кода "1" на трйггеры 51 и б„ соответствует установление их в состояния, находящиеся в соответствии с табл.1.
Таблица 1
849205
0001
0011
0101
1 111
1101
1011
1101
101Я
1110
1
1
0
i
1
Таблица 3
2 „2и7 6, < 7 1;+ Иг 2„+„ т 20. 4 тд2г„
Т 18 иТД Ю1
Т116 и Т л7.
2 1 2
В
На втором полутакте первого такта содержимое триггера 11., передается на триггер 26, содержимое регистров
10 и 9„ . — соответственно на регистры 25„ и 24„, а содержимое регистров
8 „ и 7„ через сумматор 15, на регист. ры 22„ и 23.„, причем в зависимости от содержимого триггеров 5 „ и 6 к содержимому регистров 7„ и 8„ может быть прибавлено или вычтено из него содержимое регистра 9 . Прибавление содержимого регистра 9, к содержимому регистров 7 и 8„ происходит в том лучае, если в триггерах 5., и 6„ записан код "1", вычитание — если в триггерах 5 „ и б„ записан код "1" .
Требуемая операция обеспечивается преобразователем 12„, который осуществляет в зависимости от управляющих входов передачу на сумматор
15„ содержимого регистра 9 или же дополнительного кода содержимого регистра 9г. Одновременно блоком 14, в. зависимости от выходов четырех старших разрядов сумматора 15, и при условии, что в триггере 11, записан код "1", выделяется старшая цифра частичного результата в соответствии с табл.2, код которой на втором полутакте первого такта записывается в триггерах 20 и 21 .
Т а б л и ц а 2
П р и м е ч а н и е..В табл. 2 показаны значения четырех старших разрядов сумматора в виде окончательной суммы, на самом деле каждое иэ значений представляется комбина" цией частичной суммы и переносов.
Цифры частичного результата до преоб разования
Таким образом, в течение второго полутакта первого такта происходит умножение x„ на единицу и прибавление к этому результату значений а: и
Ь„, а также выделение из полученного частичного .результата старшей цифры частичного результата, представляемой избыточным квазиканоническим кодом
В течение. первого полутакта второго такта осуществляется передача содержимого триггеров 16„-21 и
26„ и регистров 22„-25„, на соответствующие триггеры 1 -б и 11 и регистры 72-102 второго каскада. В
1 роцессе этой передачи осуществляется деление цифры частичного результата, полученной на предыдущем полутакте на число, хранившееся до этого в регистре 2Ь.л. Преобразователь 27„
Обеспечивает передачу содержимого регистра 25 на сумматор 29„, если в триггерах 20 и 21< записан код
"1", и дополнительного кода содержимого этого регистра, если в триггерах 20„ и 21„ записан код "1". В течепие этого же полутакта на регистры 7„ -10 „ заносится код "0".
В дальнейшем осуществляются описанные преобразования для первого такта в течение еще двух тактов. В результате этих преобразователей вычисляются еще две старшие цифры частичного результата и информация, при. нятая в первом полутакте первого такта на регистры 7 -10 и триг1 гер 11, достигает регистров 22 -25 и триггера 26 .
В первом полутакте четвертого такта содержимое регистров 22>-25эи триггера 26 передается на регистры
7 -10 и триггер 11„, а на регистры
7 -10„ принимаются соответственно коды чисел a,,b, x и у . При этом
2 на триггер 11 заносится код "1", а на триггеры 5 и 6„ заносится с блока 28з первая преобразованная цифра частичного результата.
Функции блока постоянной памяти заключается в преобразовании трех полученных цифр частичного результата с целью уменьшения ошибки при определении очередной: цифры частич- ного результата в соответствии с табл.3.
Цифры частичного результата пос; ле преобразования
849205
Продолжение табл. 3 т:6. и т. /7
Т <8 и т, 19; р0; "
0.П р и м е ч а н и е. А и  — числа из множества (1,0,Т), С и
0 — числа из множества (1,0), E F числа из множества (0,1) Формула изобретения
Цифры частичного результата до прео разования
Описанная последовательность из трех тактов повторяется для каждого иэ и каскадов.для четверок операндов
Для формирования результата необходимо в регистры 7,, 8, и 10,, а также в триггер 11, с помощью устройства управления записать код "0", а в регистр 9, подать код 000,000...1
На каждом следующем такте содержимое регистра 9; подается в регистр 9"„, 40 и, в зависймости от содержимОго триггеров 5 . и 6 складываясь или вычи1 1 таясь с содержимым регистров 7; и
8;, через (о+2) такта достигает выходов регистра сомножителя из конвейерного устройства, при этом на выходах устройства, связанных с сум- . матором 29, окажутся одинаковыми (n+2) старших разряда кода результата, переведенного в результате опе. рации иэ квазиканонического избыточного кода в дополнительный двоичный код. При этом результат получается в виде двух чисел: суммы и переноса.
Если же результат необходим в виде одного числа, он может быть полу-,. чен путем дополнительного прохода через устройство.
Старшие (n+2) разрядов арифметического выражения вида (2),содер- Щ
1жащего 46 чисел, могут быть получены при помощи устройства через (За+и+2) такта, при этом на (ЗС+2)-ом
1 также можно принимать новую последовательность чисел. 65
Цифры частичного результата после преобразования
При помощи устройства возможно вычисление выражения (2) последовательно, при помощи его возможно вычисление любого арифметического выражения, связанного операциями умножения, сложения, вычитания и-деления.
На следующем такте после подачи такта формирования результата можно принимать новую последовательность
"чисел.
Предлагаемое устройство, вычисляя одно и тоже арифметическое выражение за. гораздо меньшее количество тактов, чем известное, обладает значительно большей производительностью-и при этом может состоять из гораздо меньшего количества однотипных блоков.
Кроме того, отпадает необходимость в том, чтобы все операнды выражения, подлежащего вычислению, были обязательно положительными дробями.
Конвейерное устройство для выполнения арифметических операциИ над множеством чисел, содержащее и каскадов (n-разрядность чисел), причем каждый каскад сОдержит первый регистр частичного результата, первый.регистр сомножителя, первый сумматор, первый управляющий триггер, первый риггер, причем выходы первого ре849205
12 гистра частичного результата соединены с входами первого сумматора, первая шина тактовых импульсов устройства соединена с тактовыми входами триггеров и регистров, о т л ич а ю щ е з с я тем, что, с целью увеличения скорости вычисления арифметических выражений, каждый каскад устройства содержит второй регистр частичного результата, первый и вто-. рой регистры переносов, второй ре.гистр сомножителя, первый и второй регистры делителя, второй сумматор, первый и.второй блоки постоянной памяти, первый и второй преобразователи прямого кода в дополнительный, элемент ИЛИ, одиннадцать триггеров, второй управляющий триггер, причем выходы первого, второго, третьего и .четвертого триггеров соединены соответственно с входами седьмого, восьмого, девятого и десятого триггеров, .выходы пятого и шестого триггеров подключены к управляющим входам первого преобразователя прямого кода в дополнительный, входы старших разрядов которого сое.динены с выходами первого регистра сомножителя, а вход младшего разряда — с выходом элемента ИЛИ, входы которого соединены с выходом младшего разряда первого регистра сомножителя и выходом первого управляющего триггера, который подключен также к управляющему входу первого блока постоянной памяти, входы которого соединены с выходами четырех старших разрядов первого сумматора, а выходы - с входами одиннадцатого и двенадцатого триггеров, входы первого сумматора соединены с выходами первого регистра переносов и выходами первого преобразователя прямого кода в дополнительный, выходы первого сумматора соединены с входами второго регистра частичного результата и второго регистра переносов, выходы первого регистра делителя соединены с входамп второго регистра делителя, выходы которого соединены с входами первого регистра делителя, следующего каскада устройства и входами старших разрядов второго преобразователя прямого кода в дополнительный, вход младшего разряда которого соединен с выходом второго управляющего триггера, а управляющие входы — с выходами одиннадцатого и двенадцатого триггеров, выходы
Источники информации, принятые во внимание при экспертизе
1. Патент США Р 3535502, кл. G 06 F 7/385, 1970.
2. Самофалов К.Г. и др. Структуры ЭЦВМ четвертого поколения. Киев, "Техника", 1974, с. 89-243.
3. Авторское свидетельство СССР
9 479111, кл. G 06 F 7/52, 1973 (прототип).! второго преобразователя прямого код Г в дополнительный соединены с входа-: ми"второго сумматора, другие вхопы которого соединены с выходами второго регистра переносов и второго регистра частичного результата, выходы переносов (n+2). младших разрядов второго сумматора соединены с входами (n+2) старших разрядов первого регистра переносов следующего каскада, выходы суммы (и+2) младших разрядов второго сумматора соединены с входами (n+2) старших разрядов первого регистра частичного результата следующего каскада, выхо1 ды седьмого, восьмого, девятого, десятого, одиннадцатого и двенадцатого триггеров подключены к входам второго блока постоянной памяти, выходы которого соединены соответственно с входами пятого и шестого
20 триггеров каскада, предшествующего предыдущему и первого, второго, третьего и четвертого триггеров следующего каскада, выход первого управляющего триггера соединен с входом второго управляющего триггера,.выход которого подключен к входу первого управляющего триггера следующего каскада, выходы первого регистра сомножителя подключены к входам второго регистра сомножителя, выходы которого подключены к входам первого регистра сомножителя следующего каскада, тактовые входы второго, третьего, четвертого, пятого и шестого триггеров, первого регистра переносов и первого регистра делителя соединены с первой шиной тактовых импульсов устройства, тактовые входы седьмого, восьмого, девятого, десятого, одиннадцатого и двенадцатого триггеров, 40 второго регистра сомножителя, второго регистра частичного результата, второго регистра делимого и второго,уп равляющего триггера соединены с второй шиной тактовых импульсов устрой45
849205
Составитель Г. Слюсарев
Техред T,Ìàòî÷êà Корректор H. Швыдкая
РЕДактОр Г. Кацалап
Филиал ППП "Патент", r. Óæãîðîä, ул. Проектная,4
Заказ 6094/63 Тираж 745 Подписное .
BHHHIIH Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5 .
