Конвейерное устройство для одновременного выполнения арифметических операций над множеством чисел

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ К АВТРРСКОМУ СВИДЕТЕЛЬСТВУ

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

Соцмапистнческин

Республик

<и 922726 (61) Дополнительное к авт. свид-ву (22) Заявлено 27. 01. 77 (21) 2447056/18-24 (51)M. Кл.

G 06 F 7/38 с присоединением заявки,%

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

СССР (23) Приоритет

Опубликовано 23 .04 . 82. Бюллетень Рй 15 . Дата опубликования описания 23 04. 82 по делим изееретений н открытий (53) УДК.681. 3 (088. 8) (72) Авторы изобретения

А. Н, Дол голенко и Г. M . .Луц кий

f ( ((: ! (i (Киевский ордена Ленина политехнический институт @й";54 летие .

Великой Октябрьской социалистической революции (7l) Заявитель (54) КОНВЕЙЕРНОЕ УСТРОЙСТВО ДЛЯ ОДНОВРЕМЕННОГО

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

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

Известно устройство, основанное на так называемом конвейерном методе обработки информации Устройство допускает одновременное выполнение арифметических операций над множеством пар операндов и обладает достаточноо бол ьшой произ води тел ьностью (1) „

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

Наиболее близким техническим решением к изобретению является конвейерное уст ройст во для одновременного выполнения арифме1ических операций над множес1впм чисел, содержащее последовательно соединенные ярусы, каждый из которых содержит реестр частичного результата, ре" гистр сомножителя, сумматор частичного результата, первый управляаций триггер, элемент И и первый триг/ гер, причем выходы регистра частичного результата соответственно сое" динены с входами первой группы сумматора частичного результата„ выход регистра сомножителя соединен соответственно с входами регистра сомножителя последующего яруса, выходы первого управляющего триггера соединены соответственно с входами первого управляющего триггера последующего яруса, шина тактовых им- . пудьсов устройства соединена с входами установки триггеров и рег ñTpoB помощью этого устройства вози- можно вычисление полинома ах" +Ьх" +

+сх +...+kx+1, представленного в следующем виде (.. . (ах+Ь) х+... ) x+k) х+1. (1) 922726

15 г0 г5

Таким образом, с помощью этого устройства, как видно из (1), возможно вычисление арифметического выражения, содержащего любую последовательность операций сложения и умножения. При этом М вЂ” разрядное произведение 1 - разрядных чисел может быт ь получено за х 3 (1+ >)+ kx тактов, где %=1,2...3, Как видно из приведенной формулы, количество тактов, необходимое для вычисления арифметического выражения, мало зависит от требуемой точности результата вычислений, а зависит в основном от количества операндов, входящих в арифметическое выражение, и разрядности этих операндов.

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

Вместе с тем, получение 1 -разрядного произведения -разрядных чисел требуется лишь в некоторых специализированных вычислителях, в основном же требуется получение лишь и или

2 старших разрядов произведения (21.

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

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

Поставленная цель достигается тем, что в каждый ярус устройства введены регистр переносов, второй, третий и четвертый триггеры, узел выделения старшей цифры частичного ре-. зультата, первый и второй узлы преобразования прямого кода в дополнительный, второй, третий, четвертый, пя- . тый и шестой элементы И, второй управляющий три гге р, причем единичные выходы первого и второго триггеров соеди нены с упр а вляющими входами первого преобразователя прямого кода в дополнительный, единичные выходы третьего и четвертого триггеров соединены с управляющими входами второго преобразователя прямого кода в дополнительный соответственно, нулевой выход втор ого упра вляюще ro т ри ггера соединен с управляющим входом узла выделения старшей цифры частичного результата, выходы (и+5) младших разрядов сумматора частичного результата (и - разрядность операндов) покпючены соответственно к входам ре гистра частичного произ ведения посл едующе го яруса устройства, выходы пяти старших разрядов сумматора частичного результата соединены соответственно с информационными входами узла выделения старшей цифры частичного результата, первый и второй выходы которого соединены соответственно с входами установки в единичное и нулевое состояния соответственно первого триггера последующего яруса и третьего триггера данного яруса устройство, третий и четвертый выходы узла выделения старшей цифры частично го результата соеди нены с входами установки в единичное и нулевое состояния соответственно второго триггера госледующего яруса и четвертого-триггера данного яруса устройства, выходы переносов разрядов сумматора частичного результата со второго по и-й соединены соответственно с входами регистра переносов последующе го яруса устрой ст ва, выходы реги стр а сомножителя соеди не ны с и нформационными входами (n +6) старших разрядов второго преобразователя прямого кода в дополнительный, к информационному входу младшего разряда которого подключен единичный выход второ го у правляюще ro три г гера, а также информационный вход первого преобразователя прямо го код а в дополнительный, выходы первого и второго преобразователей прямого кода в дополнительный соединены с входами второй группы сумматора частичного результата, входы третьей группы которого подключены к выходам регистра переносов соответственно, единичный выход первого управляющего триггера соединен с первым входом второго элемента И, второй вход которого соединен с. единичным выходом четвертого триггера, единичный выход пер5 9 вого управляющего триггера подключен к. пер вому входу третьего элемента И, второй вход которого соединен с нуле вым выходом третьего триггера, тре. т ьи входы второ го и трет ье го элементов И соединены с нулевыми выхОдами соответственно четвертого и третьего триггеров последующего яруса устройства, выход второго элемента И соединен с входами установки в единичное и нулевое состояние соответственно третьего и четвертого триггеров по-, следующего яруса устройства, а также с первым входом первого элемента И, второй вход которого соединен с единичным вь|ходом третьего триг" гера и с первым входом четвертого элемента И, второй вход которого соединен с нулевым выходом третьего триггера, выход третьего элемента И соединен с входами установки в еди" ничное и нулевое состояния соответственно четвертого и третьего триг" геров последующего яруса устройства, а также с первым входом пятого эле" мента И, второй вход которого соединен с едини.чным выходом четверто" го триггера и с первым входом шестого элемента И, второй вход которого подключен к нулевому выходу четвертого триггера, выходы первого, четвертого, пятого и шестого элементов И соединены соответственно с входами установки в нулевое состояние первого триггера последующего яруса и третьего триггера данного яруса устройства, с входами установки в единичное состояние второго триггера последующего яруса и четвертого триггера данного яруса уст" ройства, с входами установки в нулевое состояние второго триггера последующего яруса и четвертого триггера данного яруса устройства и с входами установки в единичное состояние первого триггера последующего яруса и третьего триггера данного яруса устройства, выходы второго управляющего три ггера соединены соответственно с входами второго управляющего триггера последующего яруса устройст ва.

На чертеже представлена функциональная схема двух ярусов устройства, Устройство состоит из ярусов, каждый из которых содержит шину тактовых импульсов, первый управляющий триггер 1, первый, второй, третий рой управляющий триггер 9, преобра5 зователи 10 и 11 прямого кода в дополнительный, элементы И 12 — 14, сумматор 15 частичного результата, элементы И 16 - 18, узел 19 выделения старшей цифры частичного результата.

Устройство работает следующим образом.

Первый операнд последовательно, представленный дополнительным модифицированным двоичным кодом, имеющим три знаковых разряда, принима" ется на регистр 6, регистр 7„и регистр 8, на триггер 11 с помощью устройства управления записывается код "0", а на триггер 9„также с помощью устройства упра вления записывается код "1". Во втором операнде содержимое регистров 6 „и 7 „передается через сумматор 15„соответственно в регистры 6 и 7, содержимое регистра 8 - в регистр 8, содержимое триггеров 1 „и 9„- соответственно в триггеры 1О и 9, а на регистры 6„, 7 „ и 8, а также на триггеры 1< и 9„ с помощью устройства управления записывается код "0" °

Сумматор 151 представляет собой (П+

+6) -разрядный, параллельный комбинационный сумматор, причем выполненный таким образом, что значение пяти

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

40 с (n+1) -го разряда сумматора 15

8 результате передачи информации с пер ваго блока на второй происходят следующие преобразования: к содержимому регистров 6 „ и 7„ прибавля45 ется или вычитается из него при помощи сумматора 15„ содержимое регистра 81, причем выполнение операции зависит от управляющих входов преобразователя 10„, связанных с

50 триггерами 2 и 3„, кроме того, содержи мое три ггеро в 41 и 5 „может быть таким, что содержимое регистра 8 вообще не передается на сумматор 15„; одновременно с этим, в зависимости от. Управляющих входов преобразователя 11q связанных с триггерами 2:z и 3, происходит аналогичная операция между содержимым

22726

6 и четвертый триггеры 2 - 5,регистр 6 переносов регистр 7 частичного резул ьт ата, ре ги ст р 8 сомножителя, вто"

922726 8

7 регистра 7„и содержимым триггера

9,, причем код "1", записанный в триггере 9„, может вычитаться или складываться с содержимым in +4) -го разряда регистра 7 ; узлом 19„ выделяется старшая цифра очередного частичного результата, представляющая собой цифру избыточного квазиканонического кода с цифрами 1, 0,1, и записывается в триггеры 4 и 5„, а также в триггеры 2.1 и 3 .

Сложение содержимого регистров 6„ и 7„с содержимым регистра S„происходит, если в три ггерах 4 „и 51 записана цифра "1"; вычитание - если в триггерах 4„и 5„записана цифра "1", содержимое регистра 8„не .передается на сумматор 15, если в три ггерах 4 „и 5„за пи сана цифра

"0". Требуемая операция обеспечивается тем, что при сложении содержимое регистра 81 передается через преобразователь 10„ без изменения на сумматор 15„, а при вычитании на сумматор 15„ содержимое регистра 8„ передается с инверсией, и, кроме того, код "1" из триггера 9 через тот же преобразователь 10 подается на второй суммирующий вход младшего разряда сумматора 15 „,обес" печивая тем самым подачу на входы сумматора 15g дополнительного кода содержимого регистра 8 . Сложение содержимого триггера 9„с содержимым (л+4) -го разряда регистра 7„ прои сходит в том слу чае, е сли в триггерах 21 и 3 „записана цифра и1", при этом содержимое триггера 91 будет на выходе преобразователя 11„, связанного с входом (и+5) -го разряда сумматора 15, вычитание — если в триггерах 21 и 3„записана цифра "1", при этом содержимое триггера 9. будет как на выходе преобразо1 вателя 11„, связанного с входом (h+5) -го разряда сумматора 15, так и на выходе связанного с входом (n +

+6)- го разряда сумматора 15, содержимое триггера 9, не передается на . сумматор 15<, если в триггерах 2 и 31 записана цифра "0".

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

15 зо

З5

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

В третьем такте содержимое регистров и триггеров второго яруса передается аналогично описанному на регистры и триггера третьего яруса, содержимое регистров и триггеров первого яруса переписывается таким же образом на регистры и триггера второго яруса, а на регистры 6, 7„и

8, а также на триггер 9„c помощью устройства управления заносится код 0Ð, в триггер 1„при этом, также с помощью устройства управления, записывается код "1". После оконча; ния третьего такта в триггерах 4 и

5, а также триггерах 2 > и 3> оказывается код второго старшего разряда первого операнда, представленного . избыточным квазиканоническим кодом, а содержимое триггеров 4„и 5„, а также 2 и 3 остается прежним из-за кода "0" на схеме запрета, записанного в три ггере 9„.

В четвертом такте содержимое узлов третьего яруса передается на узлы четвертого яруса, содержимое узлов второго яруса на узлы третьего яруса, содержимое узлов первого яруса на узлы третьего яруса, а на регистр З„принимается второй операнд последовательности, представленный дополнительным модифицированным кодом, имеющим три знаковые разряда, при этом на регистры б„и 7„, а также на триггер 1 „с помощью устройства управления заносится код

"0", а на триггер 9„также с помощью устрой ст ва упр авл ени я - код 1".

После окончания четвертого такта в триггерах 4 и 5, а также в триггерах 2 < и 34 оказывается код третьего старшего разряда первого операнда, представл ен ного избыточным

M Содержимое триггеров до Содержимое три ггеров и/и преобразования после преобразования

О, 1

0 1

1 0 0 1 0

2 0 1 1 0 0

3 0 0 0 1 0

1 0 0 1 0 квазиканоническим кодом, а содержимое триггеров 2, 3, 4, 5я, 2, 3, 4.< и 51 изменяется в зависи3

)

При этом, если в триггерах 4

5 41 и 5 1 наход тся информация . такая же, как в двух первых строках таблицы, то благодаря наличию кода "1" в триггере 1 открывается схема 16 и связанные с ее входами схемы 17 и 18 „это приводит к тому, что состояние триггеров 41, 5q 2 3, 4, 5, 2 и 3 изменя" ет ся в соот ветст вии с упомянутыми двумя строками таблицы. Тем самым происходит преобразование кодов двух соседних-цифр частичного результата вида 01 и 11, соответственно коды 11 и 01. Если же информация такая, как в двух вторых строках таблицы, то,благодаря наличию кода "1" в триггере 1, сработает элемент i 2 „и связанные с его выходами элементы 13 и 141, а следовательно состояние триггеров 4, 5, 2 l, 3, 49. 5 1и 23 изменится в соответствии с упомянутыми двумя строками таблицы. Тем самым, происходит преобразование кодов двух . соседних цифр частичного результата вида 0 1 и 11 соответственно в коды 11 u Ol Описанные преобразо" вания двух соседних цифр частичного результата приводят к тому, что, ввиду избыточности квазиканонической системы, частичный результат преобраэовывается к виду, допускающему умножение его на очередной операнд последовательности. Для того, чтобы возможно было выполнять операции умножения над множеством чисел со старших разрядов, необходимо, чтобы частичный результат, представленный в избыточной квази"

922726: 10 мости от содержимоготриггеров 4

5$y 4 q и 5< всоответствии с таблицей. канонической системе, имел вид записи при которой как можно ближе влево расположены "1", если число положительное, или "1", если число .Отрицательное.

Описанная последовательность из трех тактов повторяется для каждого из m блоков для 3 ойерандов. После подачи i--ro операнда последовательности на вход устройства (i+1)-й операнд последовательности можно ., принимать через два такта, причем последовательность иэ трех тактов для i-го операнда, где i е 2, 3, 4,..., E -1, 5f отличается от последовательности иэ трех тактов для

1-го операнда тем, что этот операнд принимается регистром 8„, а в регистры 6 и 7 с помощью устройства управления заносится код "0" в от40 личие от первого операнда последовательности, который принимается на регистр 7, а в регистры б „и 8 за" носится код "0". Для формирования результата необходимо в регистры 6„ и 7, а также в триггеры 1 „и 9„с

45 помощью устройства управления записать код "0", а в регистр 81 подать код "000. 0000...001". На каждом следующем такте содержимое регистра 8; передается в регистр 8;+,1 и, а зависимости от содержимого триггеров 4„и 5,;, складывается или вычитается с содержимым регистров б„и

7, через @+5 тактов достигает выхо1Ю дов регистра сомножителя из конвей" ерного устройства, при этом на выходах конвейерного устройства, связанных со схемой формирования частичного результата, оказываются зна922726

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

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

Если же результат необходим в виде одного числа, то он может быть получен путем дополнительного прохода через предлагаемое устройство. Старшие и+4 разряды произведения чисел могут быть получены при помощи предлагаемого устройства через 3f+n+6 тактов, при этом на (3P+2)-ом такте можно принимать новую последовательность чисел.

С помощью предлагаемого устройст.ва возможно выполнение умножения последовательности чисел, суммиро- вания последовательности чисел, а также вычисления полинома Р(х) =а x"+ и

+а „„х +... +а „- х+а о и некоторые

К-4

25 другие операции, причем выполнение суммирования E чисел отличается от операции умножения чисел тем-, что, каидый i-ый операнд, где i е 2, 3, 4,..., 2-1, 1, необходимо прини- . мать на регистр 7„, а в регистр 81 с помощью устройства управлений за1 писывать код "00 1.000...00", при этом частичный результат при выполнении сложения можно не преобразовывать, а это значит, что после подачи i ãî операнда в следующем такте можно принимать для суммирования (i+1)-й операнд последовательности, и, следовательно, (и+4) старших разрядов суммы Рп-разрядных чисел может быть получено за (3+и+6) тактов.

Вычисление указанного номинала отличается от операции умножения чисел при условии, что 1=  — 1, тем, что, начиная со второй последовательности из трех тактов, на регистр 7 заносится не код "0", а код "а;", при этом на регистр 8 записывается

КОд "хнв

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

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

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

Источники информации, принятые во внимание при экспертизе.13 92272 нительный, второй, третий, четвертый, пятый и шестой элементы И, второй управляющий триггер, причем единичные выходы первого и второго триггеров соединены с управляющими входами первого преобразователя прямого кода в дополнительный, единичные выходы третьего и четвертого триггеров соединены с управляющими входами второго преобразователя прямого кода в дополнительный соответственно, нулевой выход второго управляющего триггера соединен с управляющим входом узла выделения старшей цифры частичного результата, выходы л +51 младших разрядов сумматора частичного результата (л - разрядность операндов) подключены соответственно к входам регистра частичного произведения последующего яруса устройства, выходы пяти старших разрядов сумма" тора частичного результата соедине" ны соответственно с информационными входами узла выделения старшей цифры частичного результата, первый и второй выходы которого соединены соответственно с входами установки в едини чное и нуле вое состояния соответственно первого триггера последующего яруса и третьего триггера данного яруса устройства, третий и четвертый выходы узла выделения старшей цифры частичного резуль" тата соединены с входами установки в единичное и нулевое состояние со35 ответственно второго триггера последующегоо яру са и чет вертого три ггера данного яруса устройства, выходы переносов разрядов сумматора частичного результата с второго по и -й сое" щ динены соответственно с входами регистра переносов последующего яру" са устройства, выходы регистра со". множителя соединены с информационными входами (n +6) старших разрядов второго преобразователя прямого ко-. да в дополнительный, к информационному входу младшего разряда которого подключен единичный выход второго управляющего триггера, а

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

55 второй группы сумматора частичного результ à.f а, входы трет ьей группы которого подключены к выходам регистра переносов соответственно, единичСоставитель 6. Березкин

Редактор В.Данко Техред С. Мигунова Корректор Коста

Заказ 2581/63 Тираж 732. ° Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", с. Ужгород, ул. Проектная, 4 15 922726

1. Самофалов К ° Г. и др. Структу- . ры ЗЦВИ четвертого поколения. Киев, и

"Техника", 1974, с. 89-248. т

16

2 . Авторское свидетельст во CCCP

479111, кл. G 06 F 7/52,1973 (простил).