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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯК АВТРРСКРМУ СВИДЕТЕЛЬСТВУ Союз СоветскииСоцмапистнческииРеспублик р 922726. Дата опубликования описания 23.04. 82 по делам изебретений и открытий(6 ъ.Киевский ордена Ленина политехнический институт Юй";54 летияВеликой Октябрьской социалистической революции(54) КОНВЕЙЕРНОЕ УСТРОЙСТВО ДЛЯ ОДНОВРЕМЕННОГО ВЫПОЛНЕНИЯ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙНАД МНОЖЕСТВОМ ЧИСЕЛИзобретение относится к вычислительной технике и, в частности,к области выполнения арифметических операций в многорегистровыхарифметических устройствах, выпол 5ненных на узлах с большой степеньюинтеграции,Известно устройство, основанноена так называемом конвейерном мето"де обработки информации Устройстводопускает одновременное выполнениеарифметических операций над множеством пар операндов и обладает достаточно большой производительностью (13Однако при вычислении арифметических выражений, содержащих болеедвух операндов, производительностьустройства снижается.Наиболее близким техническим ре"шением к изобретению является конвейерное уст ройст во для одновременного выполнения арифме 1 ицеских операций над множес 1 впм чисел, содержащее последовательно соединенные ярусы, каждый из которых содержит реестр частичного результата, ре" гистр сомножителя, сумматор частич" ного результата, первый управляоций триггер, элемент И и первый триг/гер, причем выходы регистра частичного результата соответственно сое" динены с входами первой группы сумматора частичного результата выход регистра сомножителя соединен соответственно с входами регистра сомножителя последующего яруса, вы" ходы первого управляющего триггера соединены соответственно с входами первого управляющего триггера последующего яруса, шина тактовых им- . пудьсов устройства соединена с входами установки триггеров и регистров,С помощью этого устройства вози- можно вычисление полинома ах" +Ьх" + +сх Мх+1, представленного в следующем виде0 15 20 г 5 30 35 40 45 50 55 Таким образом, с помощью этогоустройства, как видно из (1), возможно вычисление арифметического выражения, содержащего любую последо"вательность операций сложения и ум"ножения. При этом М - разрядноепроизведение 1 - разрядных чиселможет быт ь получено за х 1 (1+ )+ 1 хтактов, где 1=1,2 3, Как видноиз приведенной формулы, количествотактов, необходимое для вычисленияарифметического выражения, мало зависит от требуемой точности результата вычислений, а зависит в основном от количества операндов, входящих в арифметическое выражение, иразрядности этих операндов.Это объясняется тем, что независимо от того, с кол ь ко разрядов мыхотим получить на выходе арифметического устройства, в устройствеарифметическое выражение вычисляется всегда с -разрядной точностью,так как арифметические операции надмножеством чисел в этом устройствевыполняются с младших разрядов.Вместе с тем, получение 1-разрядного произведения В"разрядных чиселтребуется лишь в некоторых специализированных вычислителях, в основномже требуется получение лишь и или2 старших разрядов произведения (2,Недостатком данного устройстваявляется то, что при его использовании арифметическое выражение вычисляется с точностью до младшего разряда результата, хотя, практическипочти всегда, необходимы только старшие разряды результата, Это приводитк существенному увеличению временивычисления одного арифметического выражения и, таким образом, к значительному уменьшению производительности устройства в целом,Цель изобретения - увеличениебыстродействия устройства.Поставленная цель достигаетсятем, что в каждый ярус устройствавведены регистр переносов, второй,третий и четвертый триггеры, узел выделения старшей цифры частичного ре-.зультата, первый и второй узлы преобразования прямого кода в дополнительный, второй, третий, четвертый, пя- .тый и шестой элементы И, второй управляющий три ггер, причем единичныевыходы первого и второго триггеровсоединены с управляющими входами первого преобразователя прямого кодав дополнительный, единичные выходы третьего и четвертого триггеров соединены с управляющими входами второго преобразователя прямого кода в дополнительный соответственно, нулевой выход втор ого упра вляюще го т ри ггера соединен с управляющим входом узла выделения старшей цифры частичного результата, выходы (и+5) младших разрядов сумматора частичного результата (п - разрядность операндов) покпючены соответственно к входам ре ги стра части чно го произ веде ни я посл едующе го яруса устройства, выходы пяти старших разрядов сумматорачастичного результата соединены соответственно с информационными входами узла выделения старшей цифры частичного результата, первый и второй выходы которого соединены соответственно с входами установки в единичное и нулевое состояния соответственно первого триггера последующего яруса и третьего триггера данного яруса устройство, третий и четвертый выходы узла выделения старшей цифры частичного результата соединены с входами установки в единичное и нулевое состояния соответственно второго триггера госледующего яруса и четвертого триггера данного яруса устройства, выходы переносов разрядов сумматора частичного результата со второго по и -й соединены соответственно с входами регистра переносов последующего яруса устройства, выходы регистра сомножителя соединены с информационными входами ( +6) старших разрядов второго преобразователя прямого кода в дополнительный, к информационному входу младшего разряда которого подключен единичный выход второ го у правляюще го три г гера, атакже информационный вход первого преобразователя прямого кода в дополнительный, выходы первого и второго преобразователей прямого кода в дополнительный соединены с входами второй группы сумматора частичного результата, входы третьей группыкоторого подключены к выходам регистра переносов соответственно, единичный выход первого управляющего триггера соединен с первым входом второго элемента И, второй вход которого соединен с. единичным выходом четвертого триггера, единичный выход пер5 9вого управляющего триггера подключенк. первому входу третьего элемента И,второй вход которого соединен с нулевым выходом третьего триггера, тре. тьи входы второго и третьего элементов И соединены с нулевыми выхОдамисоответственно четвертого и третьеготриггеров последующего яруса устройства, выход второго элемента И соединен с входами установки в единичноеи нулевое состояние соответственнотретьего и четвертого триггеров по-,следующего яруса устройства, а также с первым входом первого элемента И, второй вход которого соединенс единичным вьходом третьего триг"гера и с первым входом четвертогоэлемента И, второй вход которогосоединен с нулевым выходом третьеготриггера, выход третьего элемента Исоединен с входами установки в еди"ничное и нулевое состояния соответственно четвертого и третьего триг"геров последующего яруса устройстваа также с первым входом пятого эле"мента И, второй вход которого соединен с едини.чным выходом четверто"го триггера и с первым входом шестого элемента И, второй вход которогоподключен к нулевому выходу четвертого триггера, выходы первого, четвертого, пятого и шестого элементов И соединены соответственно свходами установки в нулевое состояние первого триггера последующегояруса и третьего триггера данногояруса устройства, с входами установки в единичное состояние второготриггера последующего яруса и четвертого триггера данного яруса уст"ройства, с входами установки в ну"левое состояние второго триггерапоследующего яруса и четвертого триггера данного яруса устройства и свходами установки в единичное состояние первого триггера последующегояруса и третьего триггера данногояруса устройства, выходы второго управляющего три ггера соединены соответственно с входами второго управ"ляющего триггера последующего ярусаустройст ва,На чертеже представлена функциональная схема двух ярусов устройства,Устройство состоит из и ярусов,каждый из которых содержит шину тактовых импульсов, первый управляющийтриггер 1, первый, второй, третий рой управляющий триггер 9, преобра 5зователи 10 и 11 прямого кода в дополнительный, элементы И 12 - 1сумматор 15 частичного результата,элементы И 16 - 18, узел 19 выделения старшей цифры частичного результата,Устройство работает следующимобразом.Первый операнд последовательно,представленный дополнительным модифицированным двоичным кодом, имеющим три знаковых разряда, принима"ется на регистр 6, регистр 7 ирегистр 8 на триггер 11 с помощьюустройства управления записываетсякод "0", а на триггер 9 также спомощью устройства упра вления записывается код "1". Во втором операнде содержимое регистров 6 и 7 передается через сумматор 15 соответст вен но в регистры 6 1 и 7, содержимое регистра 8 - в регистр 8 содержимое триггеров 1 и 9- соответственно в три ггеры 1 и 9ана регистры 6, 7 и 8, а также натриггеры 1и 9 с помощью устройства управления записывается код "0"Сумматор 1 51 представляет собойи ++6) -разрядный, параллельный комбинационный сумматор, причем выполненный таким образом, что значение пяти35старших разрядов суммы и переноса встарший разряд имеет место для любого другого разряда, а в виде разрядной суммы, полученной распределением переносов возникших, - начиная40с о+1) -го разряда сумматора 158 результате передачи информации сперваго блока на второй происходятследующие преобразования: к содержимому регистров 6и 7 прибавля 45ется или вычитается из него при помощи сумматора 15 содержимое регистра 81, причем выполнение операции зависит от управляющих входовпреобразователя 10, связанных с50триггерами 2 и 3, кроме того, содержимое триггеров М 1 и 5 можетбыть таким, что содержимое регистра 8 вообще не передается на сумматор 15; одновременно с этим, взависимости от, управляющих входовпреобразователя 11 связанных стриггерами 2. и 3. происходит аналогичная операция между содержимым 227266и четвертый триггеры 2 - 5,регистр 6переносов, регистр 7 частичного резул ьт ата, ре ги ст р 8 сомножителя, вто"922726 8 55 7регистра 7 и содержимым триггера9 причем код "1", записанный втриггере 9, может вычитаться илискладываться с содержимым +4) -горазряда регистра 7 ; узлом 19 выделяется старшая цифра очередногочастичного результата, представляющая собой цифру избыточного квазиканонического кода с цифрами 1,0,1, и записывается в триггеры 4и 5, а также в триггеры 2.1 и 3.Сложение содержимого регистров 6и 7 с содержимым регистра 8 происходит, если в три ггерах 4 и 5 1записана цифра "1"; вычитание - если в триггерах 4 и 5 записана цифра "1", содержимое регистра 8 не.передается на сумматор 15, если втриггерах 4 и 5 за пи сана цифра"0". Требуемая операция обеспечивается тем, что при сложении содержимое регистра 81 передается черезпреобразователь 10 без измененияна сумматор 15, а при вычитаниина сумматор 15 содержимое регистра 8 передается с инверсией, и,кроме того, код "1" из триггера 9через тот же преобразователь 10подается на второй суммирующий входмладшего разряда сумматора 15 ,обес"печивая тем самым подачу на входысумматора 15 дополнительного кодасодержимого регистра 8. Сложениесодержимого триггера 9 с содержимым (л+4) -го разряда регистра 7прои сходит в том слу цае, е сли втриггерах 21 и 3 записана цифраи 1", при этом содержимое триггера 91будет на выходе преобразователя 11,связанного с входом (п +5) -го разряда сумматора 15; вычитание - еслив триггерах 2 1 и 3 записана цифра "1", при этом содержимое триггера 9. будет как на выходе преобразователя 11,. связанного с входом(и +5) - го разряда сумматора 15 , таки на выходе связанного с входом (и ++6)- го разряда сумматора 15 , содержимое триггера 9, не передается насумматор 15, если в триггерах 2и 3 записана цифра "0",Таким образом, после окончаниявторого такта в триггерах третьеми четвертом первого яруса, а такжев три ггерах первом и втором второго яруса оказывается код старшейцифры первого частицного результатакод з на ка пе р во го части чно го результата,. представленной в избыточ 5 О 35 20 25 30 35 40 45 50ном квазиканоническом коде, поскольку принят еще только один операнд последовательности, то код, записанный в упомянутые триггера, представляет собой значение старшего разряда первого операнда, представ" ленного избыточным квазиканоническим кодом, т.е. в результате прохода первого операнда через блоки устройства происходит перевод его в избыточную квазиканоническую систему, причем энацение -го старшего разряда первого операнда получается в 1-м ярусе и остается в триггерах третьем и четвертом 1- го яруса, а также триггерах первом и втором (1+1)-го яруса.В третьем такте содержимое регистров и триггеров второго яруса передается аналогично описанному на регистры и триггера третьего яруса, содержимое регистров и триггеров первого яруса переписывается таким же образом на регистры и триггера второго яруса, а на регистры 6, 7 и 8, а также на триггер 9 с помощью устройства управления заносится код ЧР, в триггер 1 при этом, также с помощью устройства управления, записывается код "1". После оконца; ния третьего такта в триггерах 4 и 5, а также триггерах 2и 3 оказывается код второго старшего разряда первого операнда, представленного . избыточным квазиканоническим кодом, а содержимое триггеров 4 и 5, а также 2и 3 остается прежним из-за кода "0" на схеме запрета, записанного в три ггере 9.В четвертом такте содержимое узлов третьего яруса передается на узлы четвертого яруса, содержимое узлов второго яруса на узлы третьего яруса, содержимое узлов первого яруса на узлы третьего яруса, а на регистр Зпринимается второй операнд последовательности, представленный дополнительным модифицированным кодом, имеющим три знаковые разряда, при этом на регистры 6 и 7, а также на триггер 1 с помощью устройства управления заносится код "0", а на триггер 9 также с помощью устрой ст ва упр авл ени я - код Ч ", После окончания четвертого такта в триггерах 4 и 5, а также в триггерах 2и 3 А оказывается код третьего старшего разряда первого операнда, представленного избыточным922726 10мости от содержимого триггеров 454 1 и 5 в соответствии с таблицей. У Содержимое триггеров до Содержимое триггерови/и преобразования после преобразования О, 1 0 1 1 0 0 1 0 2 О 1 1 0 0 3 0 0 0 1 0 1 0 0 1 0 3При этом, если в триггерах 4, 5, 4 0 и 5находится информация . такая же, как в двух первых строках таблицы, то благодаря наличию.кода "1" в триггере 1 открываетсясхема 16 и связанные с ее входами схемы 17 1 и 18 это приводит ктому, цто состояние триггеров 41, 51 в 2 3 41 51, 2 и 3 изменяет ся в соот ветст вии с упомянутымидвумя строками таблицы, Тем самымпроисходит преобразование кодовдвух соседних-цифр частицного результата вида 01 и 11, соответственно коды .11 и 01. Если же инфор"мация такая, как в двух вторыхстроках таблицы, то,благодаря нали"зчи ю кода "1" в три г гере 1, сработает элемент 12 и связанные с еговыходами элементы 13 и 141, а следовательно состояние триггеров 4 , 5 21 3, 4,. 51 и 2 изменится в соответствии с упомянутыми двумя строками таблицы. Тем самым, происходит преобразование кодов двух . , соседних цифр частичного результата вида 0 1 и 11 соответственно в коды 11 и 01. Описанные преобразо" вания двух соседних цифр частичного результата приводят к тому, что, ввиду избыточности квазиканонической системы, частичный результат преобраэовывается к виду, допускающему умножение его на очередной операнд последовательности, Для то" го чтобы возможно было выполнять95 операции умножения над множеством чисел со старших разрядов, необходимо, цтобы частичный результат, представленный в избыточной квази" 20,25 30 45 50 квазиканоническим кодом, а содержимое триггеров 2, 3 4 5 2 р 3, 4 и 51 изменяется в зависиканонической системе, имел вид записи при которой как можно ближевлево расположены "1", если числоположительное, или "1", если числоотрицательное,Описанная последовательность изтрех тактов повторяется для каждогоиз в блоков для 3 ойерандов. Послеподачи 1-го операнда последовательности на вход устройства (1+1)-йоперанд последовательности можно .принимать через два такта, причемпоследовательность иэ трех тактовдля 1-го операнда, где 1 е 2, 3,4-1, , отличается от последовательности иэ трех тактов для1-го операнда тем, цто этот операндпринимается регистром 8, а в регистры 6и 7с помощью устройствауправления заносится код "0" в отличие от первого операнда последовательности, который принимается нарегистр 7, а в регистры б и 81 за"носится код "0". Для формированиярезультата необходимо в регистры 6и 7, а также в триггеры 1 и 9 спомощью устройства управления записать код "0", а в регистр 81 податькод "000. 0000001". На каждомследующем такте содержимое регистра 8; передается в регистр 8;и,а зависимости от содержимого триггеров 4 и 5,;, складывается или вычитается с содержимым регистров б и7 , через ю +5 тактов достигает выхо 1 фдов регистра сомножителя из конвей"ерного устройства при этом на выходах конвейерного устройства, связанных со схемой формирования частичного результата, оказываются зназряды кода рео в результате квази канони че ского избыточного кода в дрлэлнитвлкн ныи двоичный код. При этом рвзтлзтат получается в виде двух чисел: частичного результата и переносов. Если же результат необходим в виде одного числа, то он может быть получен путем дополни тель ного прохода через предлагаемое устройство. Старшие и+4 разряды произведениячисел могут быть получены при помощи предлагаемого устройства через 31+и+6 тактов, при этом на (33+2)-ом такте можно принимать новую последовательность чисел.С помощью предлагаемого устройст.ва возможно выполнение умножения последовательности чисел, суммиро- вания последовательности чисел, а также вычисления полинома Р(х) =а х"+и +а х + +а - х+а о и некоторыеКдругие операции, причем выполнение суммирования 1 чисел отличается от операции умножения чисел тем, что,каждый 1-ый операнд, где 1 е 2, 3, 4 -1, 1, необходимо прини-. мать на регистр 7, а в регистр 81 с помощью устройства управления за" 1 писывать код "001,00000 ф, при этом частичный результат при выполнении сложения можно не преобразовывать, а это значит, что после пода чи 1-го операнда в следующем такте можно принимать для суммирования (1+1)-й операнд последовательности, и, следовательно, (и+4) старших разрядов суммы 0 п-разрядных чисел мо- до жет быть получено за (3+и+6) тактов. Вычисление указанного номинала отличается от операции умножения чисел при условии, что 1= 6 - 1, тем, что, начиная со второй последовательнос ти из трех тактов, на регистр 7 заносится не код "0", а код "а;", при этом на регистр 8 ) записывается КОд "хнвНа следующем такте после подачи 50 такта формирования результата можно принимать новую последовательность чисел. Следовательно, основное преимущество конвейерного метода обра-. ботки информации заключается в эф фективном использовании аппаратуры многорегистровых устройств и в данн.эйй случае сохраняет ся, Таким образом в предлагаемом устройстве производится вычисление арифметического выражения за сравнительно небольшое количество так 1 ов устройство обладает значительной пр ельностью и при этом может состоять иэ-небольшого коли" чества однотипных ярусов-;-кроме того, из-за примененной в устройстве схемы перемножения в дополнительных кодах отпадает необходимость в том, чтобы все операнды выражения, подлежащего вычислению, были обязательно положительными дробями,Увеличение скорости вычисления арифметического выражения достигается путем вычисления его на меньшее количество, тактов, по сравнению с известным устройством, но также и благодаря тому, что длительность такта в устройстве является гораздо меньшей, что обеспечивается нахождением частичного результата по схеме без распространения переносов. формула изобретени деиствия, к держит реги третий и .че выделения ст результата, преобразован Конвеиерное устроиство для одновременного выполнения арифметических операций над множеСтвом чисел, содержащее последовательно соединенные ярусы, каждый из которых содержит регистр частичного результата, регистр сомножителя, сумматор частичного результата, первый управляющий триггер, элемент И и первый триггер, причем выходы регистра частичного результата соответственно соединены с входами первой группы сумматора частичного результата, выходы регистра сомножителя соединены соответственно с входами ре" гистра сомножителя последующего яруса, выходы первого управляющего триггера соединены соответственно с входами первого управляющего триггера последующего яруса, шина тактовых импульсов устройства соединена .с входами установки триггеров и регистров, о т л и ч а ю щ е е с я тем, что, с целью повышения быстроаждый ярус устройства состр переносов, второй,твертый триггеры, узеларшей цифры частичногопервый и второй узлыия прямого кода в допол6 14ный выход первого управляющего триггера соединен с первым входом второго элемента И, второй вход которого соединен с единичным выходом четвертого триггера, единичйый выход первого управляющего триггера подключен к первому входу третьего элемента И, второй вход которого соединен с нулевым выходом третьего триггера, третьи входы второго. и третьего элементов И соединены с нулевыми выходами соответственно четвертого и третьего триггеров последующего яруса устройства, выход второго элемента И соединен с входами установки в единичное и нулевое состояния соответственно третьего и четвертого триггеров последующего яруса устройстваа, а также с первым входом перво-. го элемента И, второй вход которого соединен с единичным выходом третьего триггера и с первым входом четвертого элемента И, второй вход которого соединен с нулевь 1 м выходом третьего триггера, выход третьего элемента И соединен с входами установки в единичное и нулевое состояния соответственно четвертого и третьего триггеров последующего яруса устройства, а также с первым входом пятого элемента И, второй вход которого соединен с единичным выходом четвертого триггера и с первым входом шестого элемента И, второй вход которого подключен к нулевому выходу четвертого триггера, выходы первого, четвертого, пятого и шестого . элементов И соединены соответственно с входами установки в нулевое состояние первого триггера последующего яруса и третьего триггера данного яруса устройства, с входами установки в единичное состояние второго триггера последующего яруса и четвертого триггера данного яруса устройства, с входами установки в нулевое состояние второго триггера последующего яруса и четвертого триггера данного яруса устройства и с входами установки в единичное состояние первого триггера последующего яруса и третьего триггера данного яруса устройства, выходы второго уп/равляющего триггера соединены соответственно с входами второго управляющего триггера последующего яруса устройства,Источники информации,принятые во внимание при экспертизе 13 92272 нительный, второй, третий, четвертый, пятый и шестой элементы И, второй управляющий триггер, причем единичные выходы первого и второго триг" геров соединены с управляющими входами первого преобразователя пРямого кода в дополнительный, единичные выходы третьего и четвертого триггеров соединены с управляющими входами второго преобразователя прямого кода в дополнительный соответственно, нулевой выход второго управляющего триггера соединен с управляющим вхо" дом узла выделения старшей цифры частичного результата, выходы л +51 младших разрядов сумматора частичного результата (л - разрядность операндов) подключены соответственно к входам регистра частичного произведения последующего яруса устройства, выходы пяти старших разрядов сумма" тора частичного результата соедине" ны соответственно с информационными входами узла выделения старшей циф" ры частичного результата, первый и второй выходы которого соединены соответственно с входами установки в единичное и нулевое состояния соответственно первого триггера последующего яруса и третьего триггера данного яруса устройства, третий и четвертый выходы узла выделения старшей цифры частичного резуль" тата соединены с входами установки в единичное и нулевое состояние соЭ 5 ответственно второго триггера последующе го яру са и чет верто го т ри г гера данного яруса устройства, выходы переносов разрядов сумматора частичного результата с второго по ю-й сое"4 О динены соответственно с входами регистра переносов последующего яру" са устройства, выходы регистра со" множителя соединены с информационными входами (л +6) старших разрядов второго преобразователя прямого ко-. да в дополнительный, к информационному входу младшего разряда которого подключен единичный выход второго управляющего триггера, а5 О также информационный вход первого преобразователя прямого кода в дополнительный, выходы первого и второго преобразователей прямого кода в дополнительный соединены с входами55 второй группы сумматора частичного результата, входы третьей группы которого подключены к выходам регистра переносов соответственно, единич162 . Авторское свидетельство СССР 479111, кл. 0 Об Г 7/52,1973 (простил). Составитель в. БерезкинТехред С, Мигунова Корректор М.Костаа Ф 14 Редактор В.Данк Тираж 732. ВНИИПИ Государственного ком по делам изобретений и о 035, Москва, Ж, Раушская