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

 

О П И С А Н И Е ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Социалистических

Весну (61) Дополнительное к авт. свид-еу (22) Заявлено 18,1176 (21) 2421568/18-24 (51)М. Кл. с присоединением заявки Йо

G F 7/38

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

СССР оо делам изобретений и открытий (23) Приоритет(53) УДК 681.325 (088.8}

Опубликовано 15,0579. Бюллетень М 18

Дата опубликования описания 15д 579 (72) Авторы

МЗобрЕТЕНИя А.H.Ëoërîëåíêo, Л.Н.Корчинская и Г.М.Луцкий (71) Заявитель киевский ордена ленина политехнический институт им.50-летия Великой Октябрьской социалистической революции (54 ) КОНВЕЙЕРНОЕ УСТРОЙСТВО ДЛЯ ОДНОВРЕМЕННОГО

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

НАД МНОЖЕСТВОМ и-РАЗРЯДНЫХ ЧИСЕЛ

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

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

Наиболее близким по технической сущности к данному изобреТению явля» ется устройство, выполненное иэ однотипных блоков, каждый 1 -й (1=?+и) 20 блок содержит регистр частичного результата, регистр сомножителя,(n+6) входовой блок формирования частичного результата, первый управляющий триггер, первый элемент И, первый триггер, шину тактовых импульсов, причем выходы регистра частичного результата и регистра сомножителя соединены со входами блока .формирования частичного результата, входы регистра

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

Основным недостатком данного, устройства является низкое быстродействие.

Целью изобретения является повышение быстродействия.

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

3 66293, дом шифратора, выходы (n+5) старших разрядов i-ro блока формирования частичного результата подключены ко входам регистра частичного результата (i+1)-ro блока и ко входам шифратора

1-го блока, первый и второй выходыкоторого соединены соответственно со

-" входамй установки в единичное и ну " левое состояние первого триггера (i+1) -ro блока и третьего триггера

i-го блока, а третий и четвертый выходы шифратора i-ro блока соединены lO co входами установки в единичное и нулевое состояние второго триггера (i+1) -ro блока и четвертого триггера

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

"взводы" которого соединены соответствен"но с единичным выходом четвертого триггера (i+1) -го блока и "нулевйм выходом четвертого триггера i-го блока, . единичный выход первого управЛяющего,. триггера соединен со входом третьего элемента И, второй .и третий входы ко" торого соединенй соответственно с единичным выходом третьего триггера (1+1)-ro блока" и нулевым вйходом третьего триггера i-ro блока, выход второго элемента И соединен со входамй установки в единичное и нулевое соос- ... тояние, соответственно, третьего . I триггера (1+1)-ro блока и четвертого триггера (i+1}-го блока и с Первым входом .первого элемента И, к другому входу которого подключен единичный ныход третьего триггера, а также с йервым входом четвертого элемента И, второй вход которого подключен к ну- 40 левому выходу третьего триггера, а выход .третьего элемента И соединен со фхздами установки в едиййчйое и нулевое состояние соответственйо чет вертого триггера (1+1)-ro блока и 45 третьего триггера (1+1)-ro блока и

" " с "первйм входом пятого элемента И, второй вход которого подключен к единичному выходу четвертого триггера, а т акже с первым входом шестого эле- 0 мента И, второй вход которого подключен к нулевому выходу четвертого триггера выходы двухвходовых схем первого, четвертого, пятого и шестоцр.элементов И соединены соответственно со входом установки в нулевое состояние первого триггера (i+1)-ro блоKа и третьего триггера i-го блока, со- входом установки в единичное состояние второго триггера (i+1)-го бло"ка и четвертого триггера i-го блока, 60 со входом -установки в нулевое состояние второго триггера (1+1)-ro блока и четвертого триггера 1-ro блока и со входом установки в единичное состояйище первого триггера (i+1)-ro блока у

5 4 и третьего триггера i-го блока, выходы второго управл яюще го три ггера i- ro блока соединены со входами второго управляющего триггера (1+1) -го блока.

На чертеже изображена функциональная схема i-ro и (i+1)-го блоков предлагаемого устройстна.

Каждый i-й блок устройства состо» ит из первого управляющего тригге ра li, первого триггера 2i, второ.го триггера 3i, третьего триггера

4i, четвертого триггера 5i регистра частичного результата ái регистра сомножителя 7i, второго управляющего триггера Si, блока формирования частичного результата 91, элементов И

10i,1li,12i, шифратора 13i, элементов

И 14i,151, 16i.

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

Первый операнд последовательности, представленный дополнительным модифицированным двоичным „кодом, имеющим три знаковые разряда, принимается на регистр 6, на регистр 7i и триггер

1(с помощью устройства управления записывается код 0, а на триггер

8(, также с помощью устройства управлЕйия, записывается код 1, Во втором такте содержимое регистра 6 передается через блок 9 в регистр 6 + со сдвигом на один разряд влево, содержимое регистра 7(- в регистр 7;,g, содержимое триггеров 1; и 8 соотн тственно - в триггеры 1;+ и, 8; .На регистры б„ и 7;, - также на триггеры 1 и 8; с помощью устройства управления записывается код 0 . B результате передачи информации с первого блока на второй произойдут следующие преобразования: к содержимому регистра 6 прибавится, или вычтется

1 из него при помощи блока 9 содержимое регистра 7;, причем выполненная операция между содержимым регистров

6 q и 7j будет зависеть от управляющих входов блока 9(, связанных с триггерами 4 ) и 5, кроме того, содержимое триггеров 4 и 5j может быть таким, что содержимое регистра 7 вообще не передастся на схему 9 . Одновременно с этим в зависимости от управляющих входов схемы 9.<, связанных с триггерами 2; и 3<, произойдет аналогичная операция между содержимым триггера 8,причем код 1,записанный в триггере 8;, может вычесть .ся или сложиться с содержимым (n+4)»

ro разряда регистра 6„;схемой 13,", в Соответствии с табл.1, выделится старшая цифра очередного частичного результата, представляющая собой цифру избыточного квазиканонического кода с цифрами (7,0,%), и запишется, в соответствии с табл.l, в .триггеры 2 и 3.

Таблица 1

6629 35

Значени пяти ра схемы 9

0 0 О

0 О

0 1

О 1

О 1

О 1

О 0

О

1 0

Е О

I 0

IIOII

IIOI0

II00I

II00O

I0III

I0II0

Х

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

Сложение содержимого регистра б с содержимым регистра 7» произойдет, если в триггерах 4; и 5; записан код Х ; вычитание » если в триггерах

4; и 5;. записан код -Х, содер- жимое регистра 7; не будет передано на схему 9;, если в триггерах 4 и

5 записан код О . Сложение содержимого триггера 8< с содержимым (n+4) .-го разряда регистра б произойдет в том случае, если в триггерах

2, и 3(.записан код -I ) вычитанйе - если в триггерах 2; и 3 за00000

00001

00011

00101

00111

О1000

01001

l1lll

11101

11100 писан код I ; содержимое триггера 8< не будет передано на схему 9, если в триггерах 2; и 3; записан код О . Таким образом, пооле окончания второго такта в третьем и четвертом триггерах первого блока, а также в первом и втором триггерах второго блока окажется код старшей цифры первого частичного результата (код знака первого частичного результата), представленный в избыточном квазиканоническом коде. (Поскольку мы приняли еще только один операнд послеб62935 довательности, то код, записанный в вышеупомянутые триггеры, будет предствалять собой значение старшего разряда первого операнда, представленного избыточным квазиканоническим кодом, . т.е. в результате проход- первого операнда через блоки устройства происходит перевод его в избыточный квазика. ионический код, причем значение 4.-го старшего разряда первого операнда получается в i-м блоке и остается в третьем и четвертом триггерах i-го 10 блока, а также в первом и втором триггерах (i+1)-го блока.

В третьем такте содержимое регистров и триггеров второго блока передается аналогично описанному вь»ше на 15 регистры и триггеры третьего блока, содержимое регистров и триггеров первого блока переписывается таким же образом на регистры и триггерй второго блока, а на регистры бi и 7», а также на триггер 8; с помощью устройства управления эайосится код 0 ; в триггер 1,, при этом также c помощью устройства управления ЭаптМсывагется код 1 . После окончания третьего такта в триггерах 4;„и 5»,», а также в триггерах 2;+>и 3;+, окажется код второго старшего разряда первого операнда, представленного йзбйточным .

Т а блица 2.

Содержимое тр еобразов мое триггеров зеобразования

r5;,ð г3»Фя г5; ТГ4

Тг5»

0 0 Х 0

0 0 I

0 I I 0 0

0 0

0 0 0 I 0

0 I 0 тоМу, что ооотоииие триггеров 4;,,5» г 2» у 3»+1 у 4» 1.у 5»»j. «»2 и

3» у изменится в соответствии с двумя вышеупомянутыми нижними строками

@ табл.2 Вследствие этого произойдет преобразование кодов двух соседних цифр астйчного результата вида 01 и

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

6О Для того, чтобы возможно было выполнять операции умножения нац мно- л жеством чисел со старших разрядов, необходимо, чтобы частичный результат, представленный в избыточном кваэика65 ионическом коце, имел вид записи, I 0 0 Х 0

При этом, если в триггерах 4», 5;, 4»+», 5»tg находится такая же информация-, как в двух первых строках табл.2,- то благбдаря"йалйчию кодар 1 в триггере 1,, откроется схема .14» и связанные с ее выходами схемы

l5; и 16». Это приведет к тому, что состояние триггеров 4», 5;, 2»,», 3»,»,4,, 5» f 2»+ и 3» изменится в с рответствии с первыми двумя строками табл.2. Вследствие этого произойдет преобразование коДов двух соседних цифр частичного результата вида 01 и 11 соответственно в коды

11 и Îl. Если же в триггерах 4, 5(, 4»+1 и 5» 1 находится такая же информация, как в двух нижних строках табл.2, то благодаря наличию кода 1 в триггере 1», откроется схема 104 и связанные с ее выходами схемы 11» и 12» . Это приведет к (квазиканоническим кодом, а содержимое триггеров 4» и 5», а также 2»».» и 3;+» остается прежним, поскольку схема 13; заперта кодом 0, записанным в триггере 8» .

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

При этом на регистр б» и триггер l» с помощью устройства управления заносится код 0, а на триггер 8» также с по»4ощью устройства управления записывается код 1 . После окончания четвертого такта в триггерах 4»+,и 5»».у, а также триггерах

2;+> и 3;-+>-, окажется код третьего старшего разряда первого операнца, представленного избыточным квазиканоническим кодом, а содержимое триггеров 2»,, 3»+< 4» »,, 5 +2. 2»+L

3»+ у, 4; и 5, изменится в зависимости от содержимого триггеров 4 j, 5», 4„е1 и 5;«в соответствии с табл,2,.

- - 9 662 при которой как можно ближе влево расположены -1, если число положительно, или l, если число отрицательно, Описанная последовательность »»g трех тактов повторится для каждого из

m блоков для Я операндов. После пода- 6 чи i-го операнда (1+1) ûé операнд последовательности можно принимать на вход устройства через два такта, причем последовательность из трех тактов для i-го операнда, где i »; (2,3,4,. »О ... Я-l, Ej будет отличаться от последовательности из трех тактов для первого операнда тем, что этот операнд будет пРиниматься регистром 7», а в регистр б; с помощью устройства управления будет заноситься код 0, в отличие or первого операнда последовательности, который принимается на регистр 6», а в регистр 7» заносится .код 0 .

Для формирования результата необходимо в регистр 6» и в триггеры 1; и

8» с помощью устройства управления записать код 0, а в регистр 7» подать код 000.0000. . ° 001 . В каждом следующем такте содержимое регист1 ра 7j будет передаваться в регистр

7» g и, в зависимости от содержимого триггеров 4» и 5»,складываясь или вычитаясь с содержимым регистра 6», через (и+5) тактов достигнет выходов; @ регистра сомножителя из конвейерного устройства. При этом на выходах из конвейерного устройства, связанных со схемой формирования частичного результата, окажутся знаковый и 35 (n+4) старших разряда кода результата, переведенного в результате описанной операций из квазиканонического избыточного кода в дополнительныйдвоичный код. 40

Старшие (n+4) разряда произведения

Я чисел могут быть получены при помо« щи заявляемого устройства через (3 Ьп+б) тактов, при этом в (Зф+2)-м такте можно принимать новую последовательность чисел.

С помощью предложенного устройства возможно выполнение умножения и суммирования последовательности чисел, а также вычисления полинома

Р (х) = а»»„+ а, Х +... ах+ QQ u

К-1 некоторых других операций, причем выполнение операцйи суммирования 2 чисел будет отличаться от операции умножений 8 чисел тем, что каждый

i-й операнд, где i »; (2, 3, 4,... f-l, 2), необходимо принимать на Регистр 61 ° а в регистр 7» с помощью устройства управления записывается код 001.000...00 . При этом частичный результат при выполнении операции 60 сложения можно не преобразовывать, а это значит, что после подачи i-го операйда в следующем такте можно принимать для суммирования (1+1)-й операнд последовательности и, сле35 10 довательно, (n+4) старшие разряда суммы f n-разрядных чисел могут быть иолучены за (8+и+6) тактов., Вычисле. ние указанного полинома отличается от операц»ли умножения С чисел, при. условии, что К=8-1 тем, что, начи- " ная со второй последовательности из трех тактов, на регистр 6» будет заноситься не код 0, а код а,, при этом на регистр 7» будет заноситься код Х .

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

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

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

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

662935

11 частичного результата, регистра сомножителя, первого триггера управления и первого триггера, о т л и ч а ю щ е» е с я тем, что, с целью повышения быстродействия, в каждый i-й блок введены дополнительно второй, третий и четв ертый триггеры, шифратор, вт о- 5 рой, третий, четвертый, пятый и шестой элементы И, второй управляющий триггер, причем единичные выходы второго, третьего и четвертого триггеров соединены с управляющими входаьж бло-10 ка формирования частичного результата;,. нулевой выход второго управляющего триггера соединен с управляющим входом шифратора, выходы (и+5) старших разрядов .i-ro блоха формирования час-)5 тичного результата подключены ко входам регистра частичного результата . (1+1);го блока и ко входам шифратора

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

i-ro блока, а третий и четвертый вы-. ходы шифратора i-ro блока соединены со входами установки в единичное и @ нулевое состояние второго триггера (i+1) -ro блока и четвертого триггера

i-ro блока соответственно, единичный чыход второго управляющего триггера соединен с (n+5)-м входом блока фор.мирования частичного результата, а единичный выход первого управляющего триггера соединен с первым входом второго элемента И, второй и третий входы которого соединены соответст- М венно с единичным выходом четвертого триггера (.i+1)-го блока и нелувым выходом четвертого триггера i-ro блока, единичный выход первого управляющего триггера соединен со входом 40 третьего элемента И, второй и третий входы которого соединены соответственно q, единичным выходом третьего триггера (1+1)-го блока и нулевым выходом третьего триггера i-ro блока, выход 41 второго элемента И соединен со входами установки в единичное и нулевое состояние, соответственно, третьего триггера (i+1)-го блока и четвертого триггера (i+1) -го блока и с первым входом первого элемента И, к другому входу которого подключен единичный выход третьего триггера, а также с первым входом четвертого элемента И, второй вход которого подключен к нулевому выходу третьего триггера, а выход третьего элемента И соединен со входами установки в единичное и нулевое состояние, соответственно четвертого триггера (i+1)-го блока и третьего триггера (1+1)-го блока и с первым входом пятого элемента И, второй вход которого подключен к единичному выходу четвертого триггера, а также с первым входом шестого элемента И, второй вход которого подключен к нулевому выходу четвертого триггера, выходы двухвходовых схем первого, четвертого, пятого и шестого элементов И соединены соответственно со входом установки в нулевое состояние первого триггера (i+1)-го блока и третьего триггера i-го блока, со входом установки в единичное состояние второго триггера (i+1)-ro блока и четвертОго триггера i-ro блока, со входом установки в нулевое состояние второго триггера (i+1)-ro блока и четвертого триггера i-ro блока и со входом установки в единичное состояние первого триггера (i+I)-ro блока и третьего триггера i-го блока, выходы второго управляющего триггера

i-ãî блока соединены со входами второго управляющего триггера (i+1) -ro блока.

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

1. Самофалов К.Г. и др. Структуры

ЭЦВМ четвертого поколения, М., Техника, с.89.248, 2. Авторское свидетельство СССР

9 479111, кл G 06 F 7/52, 1974.

Составитель E...уткин

Редактор Н.Веселкина Техред Э.Чужик Корректор A. Гриценко

Заказ 2701/50 Тираж 779 . Подписное

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

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП Патент, г.ужгород, ул.Проектная,4