Конвейерное устройство для одновременного выполнения арифметических операций над множеством чисел Советский патент 1982 года по МПК G06F7/38 

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

НАД МНОЖЕСТВОМ ЧИСЕЛ I2

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

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

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

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

жащее последовательно соединенные ярусы, каждый из которых содержит регистр частичного результата, регистр сомножителя, сумматор частим-кого результата, первый управляющий триггер, элемент И и первый тригrepj причем выходы регистра частичного результата соответственно соединены с входами первой группы сумматора частичного результата выход регистра сомножителя соединен соответственно с входами регистра сомножителя последующего яруса, выходы первого управляющего триггера соединены соответственно с входами первого управляющего триггера последующего яруса, шина тактовых им- . ПУЛЬСОВ устройства соединена с входами установки триггеров и регистров,

С помощью этого устройства возможно вычисление полинома + .. .+kx+1 , представленного в следующем виде ;

(.0.(ах+Ь)х+..o)x+k)x+1. (1)

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

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

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

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

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

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

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

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

также информационный вход первого преобразователя прямого кода в дополнительный, выходы первого и второго преобразователей прямого кода в дополнительный соединены с входами второй группы сумматора частичного результата, входы третьей группы которого подключены к выходам регистра переносов соответственно, единичный выход первого управляющего триггера соединен с первым входом второго элемента И, второй вход которого соединен с единичным выходом четвертого триггера, единичный выход первого управляющего триггера подключен к.первому входу третьего элемента И второй вход которого соединен с нуле вым выходом третьего триггера, третьи входы второго и третьего элементов И соединены с нулевыми выходами соответственно четвертого и третьего триггеров последующего яруса устройства, выход второго элемента И соеди нен с входами установки в единичное и нулевое состояние соответственно третьего и четвертого триггеров по-, следующего яруса устройства., а также с первым входом первого элемента И, второй вход которого соединен с единичным выходом третьего триггера и с первым входом четвертого элемента И, второй вход которого соединен с нулевым выходом третьего триггера, выход третьего элемента И соединен с входами установки в единичное и нулевое состояния соответственно четвертого и третьего триггеров последующего яруса устройства, а также с первым входом пятого элемента И, второй вход которого соединен с единичным выходом четвертого триггера и с первым входом шестого элемента И, второй вход которого подключен к нулевому выходу четвертого триггера , выходы первого, четвертого, пятого и шестого элементов И соединены соответственно,с входами установки в нулевое состояние первого триггера последующего яруса и третьего триггера данного яруса устройства, с входами установки в единичное состояние второго триггера последующего яруса и чет- вертого триггера данного яруса устройства, с входами установки в нулевое состояние второго триггера последующего яруса и четвертого триг гера данного яруса устройства и с входами установки в единичное состояние первого триггера последующего яруса и третьего триггера данного яруса устройства, выходы второго управляющего триггера соединены соответственно с входами второго управляющего триггера последующего яруса устройства. На чертеже представлена функциональная схема двух ярусов устройства. Устройство состоит из г ярусов, каждый из которых содержит шину тактовых импульсов, первый управляющий триггер 1, первый, второй, третий и четвертый триггеры 2 - 5|регистр6 переносов регистр 7 частичного результата, регистр 8 сомножителя, второй управляющий триггер 9, преобразователи 10 и 11 прямого кода в дополнительный, элементы И 12 - k, сумматор 15 частичного результата, элементы И 16 - 18, узел 13 выделения старшей цифры частичного результата.Устройство работает следующим образом. Первый операнд последовательно, . представленный дополнительным модифицированным двоичным кодом, имеющим три знаковых разряда, принимз ется на регистр 6, регистр 7 и регистр 8, на триггер 1 с помощью устройства управления записывается О, а на триггер 9 также с помощью устройства управления записывается код 1. Во втором операнде содержимое регистров 6 -| и 7i передается через сумматор 15 соответственно в регистры ( 7,, содержимое регистра 8- - в регистр 8(j, содержимое триггеров 9- - соответственно в триггеры 1(2 и 9(j а на регистры 6. , 7-1 и 8, а также на триггеры 1 и 9 с помощью устройства управления записывается код О. Сумматор представляет собой (п + +6) -разрядный,параллельный комбинационный сумматор, причем выполненный таким образом, что значение пяти старших разрядов суммы и переноса в старший разряд имеет место для любого другого разряда, а в виде разрядной суммы, полученной распределением переносов возникших, - начиная с (пч-1)-го разряда сумматора 15-,. В результате передачи информации с первого блока на второй происходят следующие преобразования: к содержимому регистров 6 и 7 прибавляется или вычитается из него при помощи сумматора 15 содержимое регистра 8, причем выполнение операции зависит от управляющих входов преобразователя 10, связанных с триггера-ми 2 и 3.,, кроме того, содержимое триггеров k и S может быть таким, что содержимое регистра 8.-I вообще не передается на сумматор одновременное этим, в зависимости от. управляющих входов преобразователя 11i, связанных с триггерами 2.-, и 3, происходит аналогичная операция между содержимым

регистра 7 и содержимым триггера 9 , причем код 1, записанный в триггере , может вычитаться или складываться с содержимым (п +) -го разряда регистра узлом 19 выделяется старшая цифра очередного частичного результата, представляющая собой цифру избыточного квазиканонического кода с цифрами 1, О,Т и записывается в триггеры k и 5 , а также в триггеры 2. и Зо. Сложение содержиюго регистров 6 и 7-, с содержимым регистра 8 происходит, если в триггерах А и 5 записана цифра, вычитание - если в триггерах k и 5- записана цифра 1, содержимое регистра 8-,1не .передается на сумматор 15,,, если в триггерах k и 5- записана цифра О. Требуемая операция обеспечивается тем, что при сложении содержимое регистра 8 передается через преобразователь 10-, без изменения на сумматор 15, а при вычитании на сумматор 15 содержимое регистра 8 передается с инверсией, и, кроме того, код 1 из триггера 9-, через тот же преобразователь 10 подается на второй суммирующий вход младшего разряда сумматора 15л обеспечивая тем самым подачу на входы сумматора 15-1 дополнительного кода содержимого регистра 8. Сложение содержимого триггера 9i с содержимым ()- го разряда регистра 7,, происходит в том случае, если в триггерах 2- и 3,, записана цифра 1, при этом содержимое триггера 9 будет на выходе преобразователя 11.,, связанного с входом (л+5)-го разряда сумматора 15) , вычитание - если в триггерах 2 и 3 записана цифра 1, при этом содержимое триггера 9;, будет как на выходе преобразователя 11.,,. связанного с входом (п+5)-го разряда сумматора 15,,, так и на выходе связанного с входом (п + +6)-го разряда сумматора 15-,, содержимое триггера 9-, не передается на сумматор 15/, если в триггерах 2/, и 3i записана цифра О,

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

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

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

J5 в триггерах третьем и четвертом i-ro яруса, а также триггерах первом и втором (i+1)-го яруса.

В третьем такте содержимое регистров и триггеров второго яруса передается аналогично описанному на регистры и триггера третьего яруса, содержимое регистров и триггеров первого яруса переписывается таким же образом на регистры и триггера второго яруса, а на регистры 6, 7 и 8-J, а также на триггер 9-i с помощью устройства управления заносится код О, в триггер 1-, при этом, также с помощью устройства управления, записывается код 1. После окончания третьего такта в триггерах (и 5я, а также триггерах За оказывается код второго старшего разряда первого операнда, представленного избыточным квазиканоническим кодом, а содержимое триггеров х, и 5-i, а такие 2 Зп остается прежним из-за кода О на схеме запрета, записанного в триггере 9- .

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

также на триггер 1 -, с помощью устройства управления заносится код О, а на триггер 9 также с помощью устройства управления - код 1. . После окончания четвертого тэкта в триггерах Ц и 5з з также в триггерах 34 оказывается код третьего старшего разряда первого операнда, представленного избыточным

992272610

квазиканоническим кодом, а содер-мости от содержимого триггеров л,

жимое триггеров 2 , З, а 5), 2,, , и 5 j jcoeYeeTCTBMn с табли% 1 изменяется в зависи-цей.

При этом, если в триггерах k, 5-11 ( 5 rj находится информация такая же, как в двух первых строках таблицы, то благодаря наличию. кода 1 в триггере 1,, открывается схема 16. и связанные с ее входами схемы 17-1 и 18-1 это приводит к тому, что состояние триггеров t, 5v Ч 3ij Ч 5т-, 2 Зз изменяется в соответствии с упомянутыми двумя строками таблицы. Тем самым происходит преобразование кодов двух соседних-ЦИ0Р частичного результата виуца 01 и 11, соответственно коды .11 и 01, Если же информация такая, как в двух вторых строках таблицы, то благодаря наличию кода 1 в триггере 1, сработает элемент 12 и связанные с его выходами элементы 13-i и ,, а следовательно состояние триггеров 4, 5, 2,, 3q, q, 5ri 2j изменится в соответствии с упомянутыми двумя строками таблицы. Тем самым, происходит преобразование кодов двух . соседни.х цифр частичного результата вида 01 и Тт соответственно в коды iT и оТ. Описанные преобразования двух соседних цифр частичного результата приводят к тому, что, ввиду избыточности квазиканонической системы, частичный результат преобразовывается к виду, допускающему умножение его на очередной операнд последовательности. Для того , чтобы возможно было выполнять операции умножения над множеством чисел со старших разрядов, необходимо, чтобы частичный результат, представленный в избыточной квазиканонической системе, имел вид за0писи, при которой как можно ближе влево расположены Т, если число положительное, или 1, если число .отрицательное.

Описанная последовательность из

5 трех тактов повторяется для каждого из m блоков для t операндов. После подачи i-го операнда последовательности на вход устройства (+1)-й операнд последовательности можно .

0 принимать через два такта, причем последовательность из трех тактов для i-ro операнда, где i е {2, 3, ,0.., &-1 ,в , отличается от последовательности из трех тактов для

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

5 помощью устройства управления записать код О, а в регистр 8 подать код 000, 0000,,.001. На каждом следующем такте содержимое регистра 8 передается в регистр 8-. и,

0 а зависимости от содержимого триггеров tjj и 5 складывается или вы иуается с содержимым регистров 6 и 7:;, через п+5 тактов достигает выходов регистра сомножителя из конвей

5 ерного устройства-, при этом на выходах конвейерного устройства, связанных со схемой формирования час тичного результата, оказываются зна11 .|й и старшие разряды кода ре зультЗТа-у тереведенного в результат описанной сэгтерацрж-из вазиканониче кого избыточного кода (ЗпО7житель ный двоичный код. При этом резулР - тат получается в виде двух чисел: частичного результата и переносов ЕСЛИ же результат необходим в виде одного числа, то он может быть получен путем дополнительного прохода через предлагаемое устройство. Стар шие п+4 разряды произведения чисе могут быть получены при помощи пред лагаемого устройства через 3f+n+6 тактов, при этом на (ЗР+2)-ом такте можно принимать новую последователь ность чисел. С помощью предлагаемого устройства возможно выполнение умножения последовательности чисел, суммирования последовательности чисел, а также вы сления полинома Р(х)а-х , +а - х+а о и некоторые другие операции, причем выполнение суммирования IE чисел отличается от операции умножения чисел тем, что , каждый i-ый операнд, где i б 2, 3, 4,.о.,Е-1, , необходимо принимать на регистр 7, а в регистр 8 с помощью устройства управлений записывать код ООКООО.оОО, при этом частичный результат при выполнении сложения можно не преобразовывать, а это значит, что после подачи i-ro операнда в следующем такте можно принимать для суммирования (i+1)-и операнд последовательности, и, следовательно, (п+4) старших раз рядов суммы Вп-разрядных чисел может быть получено за (+п+6) тактов Вычисление указанного номинала отли чается от операции умножения чисел при условии, что k В - 1, тем, что начиная со второй последозательносна регистр 7 зати из трех тактов, 11 II О носится не код О, а код а- , при этом на регистр 8 / записывается код х. На следующем такте после подами такта формирования результата можно принимать -новую последовательность чисел о Следовательно, основное преимущество конвейерного метода обработки информации заключается в эффективном использовании аппаратуры многорегистровых устройств и в данном случае сохраняется. 6 Таким образрм, в предлагаемом устройстве производится вычисление арифметического выражения за сравнительно небольшое количество такт ов стройство обладает значительной проРгэводихельностью и при этом может состоять из е льшого количества однотипных ярусо -кр оме того, из-за примененной в устройстве схемы перемножения в дополнительных кодах отпадает необходимость в том, чтобы все операнды выражения, подлежащего вычислению, были обязательно положительными дробями. Увеличение скорости вычисления арифметического выражения достигается путем вычислежя его на меньшее количество.тактов, по сравнению с известным устройством, но также и благодаря тому., что длительность такта в устройстве является гораздо меньшей, что обеспечивается нахождением частичного результата по схеме без распространения переносов. Формула изобретения Конвейерное устройство для одновременного выполнения арифметических операций над множеством чисел, содержащее последовательно соединенные ярусы, каждый из которых содержит регистр частичного результата, регистр сомножителя, сумматор частичного результата, первый управляющий триггер, элемент И и первый триггер, причем выходы регистра частичного результата соответственно соединены с входами первой группы сумматора частичного результата, выходы регистра сомножителя соединены соответственно с входами регистра сомножителя последующего яруса, выходы первого управляющего триггера соединены соответственно с входами первого управляющего три1- гера последующего яруса, шина тактовых импульсов устройства соединена .с вх9Дами установки триггеров и регистров, отличающееся тем, что, с целью повышения быстродeйctвия, каждый ярус устройства содержит регистр переносов, второй, третий и четвертый триггеры, узел выделения старшей цифры частичного результата, первый и второй узлы преобразования прямого кода в дополнительныи, второй, третий, четвертый, пятый и шестой элементы И, вт рой управляющий триггер, причем еди ничные выходы первого и второго три геров соединены с управляю1ди| 1 входами первого преобразователя прямог кода в дополнительный, единичные вы ходы третьего и четвертого триггеров соединены с управляющими входам второго преобразователя прямого код в дополнительный соответственно, ну левой выход второго управляющего триггера соединен с управляющим вхо дом узла выделения старшей цифры частичного результата, выходы (fi+5) младших разрядов сумматора частично го результата (п - разрядность операндов) подключены соответственно к входам регистра частичного произведения последующего яруса устройства выходы пяти старших разрядов сумматора частичного результата соединены соответственно с информационными входами узла выделения старшей цифры частичного результата, первый и второй выходы которого соединены соответственно с входами установки в единичное и нулевое состояния соответственно первого триггера последующего яруса и третьего триггера данного яруса устройства, третий и четвертый выходы узла выделения старшей цифры частичного р$зультата соединены с входами установки в единичное и нулевое состояние соответственно второго триггера последующего яруса и четвертого триггера данного яруса устройства, выходы переносов разрядов сумматора частичного результата с второго по п-и сое динены соответственно с входами регистра переносов последующего яруса устройства, выходы регистра cor множителя соединены с информационными входами (п +6) старших разрядов второго преобразователя прямого ког да в дополнительный, к информационному входу младшего разряда которого подключен единичный выход второго управляющего триггера, а также информационный вход первого преобразователя прямого кода в дополнительный, выходы первого и второго преобразователей прямого кода в дополнительный соединены с входами второй группы сумматора мастичного результата, входы третьей группы которого подключены к выходам регистпа переносов соответственно, единичный выход первого управляющего триггера соединен с первым входом второго элемента И, второй вход которого соединен с единичным выходом четвертого триггера, единичный выход первого управляющего триггера подключен к первому входу третьего элемента И, второй вход которого соединен с нулевым выходом третьего триггера, третьи входы второго-и третьего элементов И соединены с нулевыми выходами соответственно четвертого и . третьего триггеров последующего яруса устройства, выход второго элемента И соединен с входами установки в единичное и нулевое состояния соответственно третьего и четвертого триггеров последующего яруса устройства, а также с первым входом первого элемента И, второй вход которого соединен с единичным выходом третьего триггера и с первым входом четвертого элемента И, второй вход которого соединен с нулевым выходом третьего триггера, выход третьего элементам соединен с входами установки в единичное и нулевое состояния соответственно четвертого и третьего триггеров последующего яруса устройства,а также с первым входом пятого элемента И, второй вход которого соединен с единичным выходом четвертого триггера и с первым входом шестого элемента И, второй вход которого подключен к нулевому выходу четвертого триггера, выходы первого, четвертого, пятого и шестого элементов И соединены соответственно с входами установки в нулевое состояние первого триггера последующего яруса и третьего триггера данного яруса устройства, с входами установки в единичное состояние второго триггера последующего яруса и четвертого триггера данного яруса устройства, с входами установки в нулевое состояние второго триггера последующего яруса и четвертого триггера данного яруса устройства и с входами установки в единичное состояние первого триггера последующего яруса и третьего триггера данного яруса устройства, выходы второго управляющего триггера соединены соответственно с входами второго управляющего триггера последующего яруса устройства. Источники информации, принятые во внимание при экспертизе

. 1592272616

ры ЭЦВМ четвертого поколения. Киев, № 79111, кл. GОб F 7/52,1973 (про Техника, 197, с. 89-2if8. тотип).