Параллельный сумматор

 

ПАРАЛЛЕЛЬНЬт СУММАТОР, содержёцций элементы задержки и N суммирующих ячеек, каждая из которых содержит одноразрядный сумматор, элемент И и три элемента задержки, выход элемента И соединён с первым входом одноразрядного сумматора, вход первого элемента задержки соединен с перВЕШ входом суммирующей ячейки, а выход с первым входом элемента И и первым выходом суммирукицей ячейки, второй и третий входы котсфюй подключены к соответствующим входам одноразрядного сумматора, выход суммл которого соединен с входом второго элемента задержки и вторым iвыходом суммирующей ячейки, выход переноса одноразрядного сумматора подключен к входу ; третьего элемента задержки, выход которого соединен с третьим выходам суммирующей ячейки, выход второго элемента задержки подключен к второ- . t входу элемента И, первый вход первой суммирующей ячейки подключен к шине запрета формирования суммы параллельного сумматора, первый вход каждой последующей суммирукщей ячейки соединен с первым выходом преда1ду , щей суммирующей ячейки, второй вход каждой суммирующей ячейки, начиная с второй, подключен к третьему выiходу предыдущей суммирующей ячейки, третий вход каждой j-й су1даирующей ячейки (,...N) соединен с выходом I цепочки из (J-1 ) соединенных прследовательно элементов задержки, от л ичающийся тем, что, с целью расширения функциональных возможностей за счет выполнения операций суммирования парных произведений и умножения, дополнительно содержит

(ХНОЗ СОВЕТСНИХ

COUNMI

РЕСПУБЛИН

У5В G 06 F "7 50

J

ОПИСАНИЕ ИЗОБРЕТЕН -:

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbf7344 (21 ) 3272840/18-24 1 (22) 15.01.81 (46 ) 15.05.83. Вюл.. Ю 18 (72) В.В. Балюк, В.A. Яядюра| Ю.М. Зорин, Ю.С. Каневский, В.И. Лозинский и A.Â. Пененко (71 ) Киевский ордена Ленина политехнический .институт им. 50-летия Великой Октябрьской социалистической революции и Производственное объединение "УКРГЕОФИЗИКА" (53) 681.325.5(088.8) (56 ) 1.Авторское свидетельство СССР

М 550637, кл. G 06 F 7/52, 1975.

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

В 603991, кл. G 06 F 7/50, 1976

{прототип ). (54 )(57 ) ПАРАЛЛЕЛЬНЫЙ СУММАТОР, .содержащий элементы задержки и N суммирующих ячеек, каждая из которых содер жит одноразрядный сумматор, элемент

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

„.SUÄÄ 1018114.: A каждой суммирукицей ячейки, начиная с второй, подключен к третьему вы,:ходу предыдущей суммирующей ячейки, третий вход каждой j-й суммирующей ячейки (j= 2, ° ..N ) соединен с выходом цепочки из (3 -1 ) соединенных последовательно элементов задержки, о т л ичающий с я тем, что, с целью расширения функциональных возможнос-. тей за счет выполнения операций суммирования парных произведений и умножения, дополнительно содержит (2N-1 ) триггеров, (2N-1 ) элементов И, элемент HJIH регистр сдвига и (N-1 ) дополнительййх суммирующих ячеек, причем выходы разрядов регистра сдвига соединены с первыми входами соот- Е ветствующих элементов И, вторые входы которых соединены. с выходом элемента ИЛИ, первый вход которого соединен с шиной множителя параллельного сумматора, а второй вход — с шиной режима работы параллельного суммато- Я ра, первый вход первой дополнительной суммирующей ячейки соединен с дополнительной шиной запрета формирования .сумы параллельного сумматора, первый вход каждой последующей дополнительной суммирующей ячейки соединен с третьим выходом предыдущей дополнительной суммирующей ячейки, выходы элементов И с первого no (N-1 )-й соединены с третьими входами соответствующих дополнительных суммирующих ячеек, вторые выходы которых подключены к информационным входам соот ветствуккцих триггеров, тактовые входы которых подключены к первым выходам соответствующих дополнительных суммирующих ячеек, первый и третий выходы (N-1 )-й дополнительной суммирующей ячейки соединены с первым и вторым входами соответственно первой сумми- рующей ячейки, третий вход которой подключен к выходу N-ro элемента И, выходы элементов И с (Ntl )-го по (,2N-1 )-й соединены с входами цепочек.

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

ЭВИ и специализированных вычислительных устройствах, вычисляющих сум- 5 няа парных произведений.

Известно устройство для вычисления сумм парных произведений, содержащее матрицу модулей сложенйя 1 .

Недостатком такого устройства яв- 19 ляются значительные аппаратурные затраты.

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

И, трех элементов задержки и одного 20 одноразрядного сумматора, будем называть суммирующей ячейкой, в которой первый вход одноразрядного сумматора подключен к выходу элемента И, первый вход которого подключен к выходу 25 первого элемента задержки, вход кото.рого подключен к третьему входу суммирующей ячейки, а второй вход элемента И через второй элемент задержки подключен к первому выходу одно-. ЗО разрядного сумматора, второй выход которого подключен ко входу третьего: элемента задержки, выход которого подключен ко второму выходу суммирующей ячейки, второй вход одноразряд 35 ного сумматора подключен к первому входу суммирующей ячейки, третий вход одноразрядного сумматора подключен ко второму входу суммирующей ячейки,,первый выход суммирующей ячейки под-, ключен к первому выходу одноразряд- 40 ного сумматора, а третий выход суммирующей ячейкй подключен к первому входу элемента И, причем суммирующая ячейка i-го разряда (i 1,2, ° ° °, й) первым входом подключена к сооТ- 45 ветствующей входной шине через (i-1 ) элементов задержки, вторым и третьим входами подключена соответственно.ко второму и третьему выходам суммирующей ячейки (i-1 )-го разряда, пеРвым 5g выходом соединена с соответствующей выходной шиной, а вторым и третьим рых подключены к первым выходам суммирующих ячеек с первой по N-ую соответственно, входы разрядов регистра сдвига соединены с входными шинами параллельного сумматора, выходные шины которого подключены к выходам триггеров. выходами соединена соответственно со вторым и третьим входами суммирующей ячейки (i+1 )-го разряда 523.

Данное устройство не позволяет выполнять ни операцию умножения, ни получение сумьы парных произведений вида А В +...+A„„ В., для вычисления которой требуется такой же такт работы сумматора как и при умножении.

Цель изобретения - расширение функциональных возможностей за счет выполнения операций суммирования парных произведений и умножения °

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

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

j-ой суммирующей ячейки (j = 2,3...,, N ) соединен с выходом цепочки из соединенных.последовательно элементов задержки, дополнительно содержит (2N-1 ) триггеров, (2N- 1 ) элементов И, элемент ИЛИ, регистр сдвига и (М-1 ) дополнительных суммирующих ячеек, --"- 1018114 причем выходы разрядов регистра сдви га соединены с первыми входами соот« ветствукщих элементов И, вторые входы которых соединены с выходом элемента ИЛИ, первый вход которого соединен с шиной множителя параллель-. 5 ного сумматора, а второй вход - с шиной режима работы параллельного сум« . матора, первый вход первой дополнительной суммирукщей ячейки соединен с дополнительной шиной запрета формиро - 10 вания суммы параллельного сумматора, первый вход каждой последующей дополнительной суммирующей ячейки соединен с первым выходом предыдущей дополнительной суммирукнцей ячейки, 15 второй вход каждой дополнительной суьв ирующей ячейки соединен с третьим выходом предыдущей дополнительной = .суммирующей ячейки, выходы элементов

И с первого по (N-1 )-й соединены с третьими входами соответствующих дополнительных суммирующих ячеек, вторые выходы которых подключены к-информационным входам соответствующих .триггеров, тактовые входы которых подключены к первым выходам соответствующих дополнительных суммирующих .ячеек„ первый и третий выходы (Ы-1 )-й дополнительной суммирующей ячейки соединены с первым и вторым входами-.соответственно первой суммирующей ячейки, третий вход которой подключен к выходу N-го элемента И, выходы элейентов И с (N+1 )-го по (2N-1 )-й соединены с входами цепочек из по следовательно соединенных элементов 35 задержки с первой по (N-1, -ю соответственно, вторые выходы суммирующих ячеек с первой по N-ю соединены с информационными входами триггеров с (N+1 )-го по (2N-1 )-й соответственно, 4g тактовые входы которых подключены к первым выходам суммирующих ячеек спервой по М-ю соответственно, входы разрядов регистра сдвига соединены с входными шинами параллельного сум- 45 матора, выходные шины которого подключены к выхедам триггеров.

° дом одноразрядного сумматора 21,первый вход которого подключен к выходу элемента И 22, первый вход .которого подключен к.выходу-йервого элемента 23 . .задержки,.--вход которого подключен к третьему входу 10 ячейки..Второй вход

-.14 ячейки подключен к третьему входу одноразрядного сумматора. Первый выход одноразрядного сумматора 21 под ключен к первому выходу ячейки 16 и ко входу второго элемента 24 задержки, выход которого соединен ко второму входу элемента И 22. Второй выход одноразрядного сумматора 21 под= ключен через третий элемент 25 за; держки ко второму выходу 14 суммирующей ячейки 9. Третий выход 11 суммирующей ячейки 9 подключен к выходу первого элемента 23 задержки.

Параллельный сумматор может работать в двух режимах: в режиме сумматора и режиме умножителя. Каждая из этих операций может выполняться либо с накоплением предыдущих результатов, .либо без накопления. длительность задержки иа элементе

7 задержки такова, что сигнал на ее выходе появляется через время Г равное интервалу подачи слагаемых на .входные шины 1. Элементы 24 и 25 за-. держки таковы, что на их выходе сигнал появляется также через время Г, Режим сумматора. В исходном состоянии на входную шину 1 подают нулевой код. В процессе суммирования на М старших разрядов входной шины 1 через интервалы времени, равные, подаются суммирующие числа, а на (Х-1 )-ый младший разряд вхоцной шины 1 подают- ° ся нули. На шину б режима работы поступает сигнал разрешения, открываю,щий элементы И 3.

Через время + первый разряд первого слагаемого проходит через сумматор 21 N-ой суммирующей ячейки 9, На чертеже дана функциональная схема параллельного сумматора.

Сумматор содержит входную шину 1 подключенную к соответствующим входам (2N-1 )-разрядного регистра 2 сдвига, выходы которого соединены с первыми входами (2N-1 )-ro элемента

И 3. Вторые входы всех (2N-1 )-го элементов И соединены с выходом элемента ИЛИ 4, первый вход которого соединен с шиной 5 множителя, а второй вход соединен с шиной б режима работы. Выход i-го элемента И 3 (i .= N.,N+1,...,2N-1 ) подключен через (i-N ) элементов 7 задержки к первому входу 8 i-ой суммирукшей ячейки 9, а выход j-ого элемента 3 (j 1,2, ...,N-1 ) подключен к первому входу

8 j-oN суммирующей ячейки 9. Третий 65 вход 10 каждой k-той (k = 1,2,..., 2N-1 ) суммирукщей ячейки 9 соединен с третьим выходом 11 (k-1 )-ой суммирующей ячейки 9, причем третий вход

10 первой суммирующей ячейки 9 сое динен с дополнительной шиной 12 запре,та формирования сумки, а третий вход .10 k-ой суммирующей ячейки 9 соединен с шиной 13 запрета формирования .суммы. Второй вход 14 каждой k-той

;суммирующей ячейки. 9 соединен со вторым выходом 15 (К -1) -ой сум:мирующей ячейки 9. Первый выход ,16 каждой k-той суммирующей ячейки 9 :соединен с первым входом 17 k-ro так1 тирующего триггера 18, а второй вход

19 k-го трактируемого триггера соединен с третьим выходом 11 k- òîé сум1мирующей ячейки 9 того же разряда. Выходами сумматора 20 являются выхо ды тактируемах триггеров 18. В каж дой k-ой сумвжрукиаей ячейке 9 пер вый вход 8 соединен со вторым вхо1018114. элемент 24 задержки 24 и элемент И

22 этой же суммирующей ячейки и попадает на первый вход сумматора 21.

В это же самое время (p на вход-. ную шину 1 подается новое слагаемое, а на первый вход 8 (N+1 )-ой суммирующей ячейки 9, пройдя элемент 7 задержки, попадает второй разряд первого слагаемого.

В следующем такте (ЙЮпроисходит суммирование в сумматоре 21 N-ой ° 10 суммирующей ячейки 9 первых.разрядов первого и второго слагаемых, и сумма их, через элемент 24 задержки и элемент И 22 N-ой суммирующей ячейки 9 поступает на первый вход сумматоРа 15

20 той же суммирующей ячейки 9 °

В это же время (2 с) второй разряд первого слагаемого просуммируется в (N+1 )-ой суммирующей ячейке 9 с нулем. Перенос, сформированный при суммированиии первых разрядов, через элемент 25 задержки и второй выход

15 N-ой суммирующей ячейки 9 поступает на второй вход 14 (И+1 )-ой суммирующей ячейки 9. Второй разряд второго слагаемого, пройдя элемент

7 задержки., поступает на первый вход

8 той же суммирующей ячейки. Третий разряд первого слагаемого, пройдя два элемента 7 задержки, поступает на первый вход 8 (N+2 )-ой суммирующей ячейки 9.

В каждом последующем такте происходит суммирование одноименных разрядов результата от сложения (m-p ) слагаемых, где р = ж,m-1,...,: 35

2,1 и (п.-р+1 )-ro слагаемого.

Через время (m-1 )Ф в N-ой суммирующей ячейке 9 просуммируются первые разряды (m-1 )-ro слагаемых, а на пеРвый вход 8 этой же суммирующей 40 ячейки поступает первый разряд m-ro. слагаемого. В следукщем такте (m ) происходит суммирование первых разрядов m слагаемых.

Для очистки суммирующих ячеек 9 45 (перед началом суммирования следующего массива чисел ) на шину 13 запрета формирования суммы подается импульс, который, пройдя элемент задержки 23 и элемент И 22, разрывает цепь обратной связи первого выхода сумматора 21 с первым входом этого же сумматора. Этот процесс ,повторяется во всех суммирующих ячей. ках 9. Этот же импульс используется для занесения результата суммирования в триггеры 18.

Таким образом, через время (m+N Q результат суммирования N-тых разря" дов m слагаемых записывается в (2N-1 )-ый тактируемый триггер 18, а на входных шинах 20 появляется ре-. зультат суммирования m N-разрядных слагаемых. В (m+1 ), такте на выходную шину 1 подается слагаемое из следующего массива и начинается на- 65 копление следующей сумма, т . е. на обработку одного слагаемого необходимо затратить (1+М/m ) тактов.

Режим умножения. В исходном состо янии на входных шинах 1 присутствуют нули. Множимое подается на N младших разрядов входной шины 1 и принимается в регистр 2. На шину 5 множителя поступает первый (младший ) разряд множителя, а на шину б режима работы подается нулевой код. На элементах

И 3 формируется частичное произведение множимого на один разряд множителя. В первом такте в N .младших суммирующих ячейках 9 происходит сло. женке частичного произведения множимого на первый разряд множителя, с нулем. В следующем такте (2 Г) . на шину 5 множителя поступает второй разряд множителя, в сдвиговом регистре 2 производится сдвиг множимого на один разряда влево. В (N-1 )-ой суммирующих ячейках 9 происходит суммирование частичного произведения, сформированного в первом такте, с (N-1 )-ым разрядом частичного произведения, сформированного во втором такте. При этом во второй суммирующей ячейке 9 формируется второй разряд результата умножения двух сомножителей. На первый вход 8 (Я+1 )-ой суммирующей ячейки 9, пройдя элемент

7 задержки, поступает старший разряд сформированного в этом такте частичного произведения.

В следующем такте(37. ) на шину 5 множителя поступает третий разряд множителя, в сдвиговом регистре 2 производится сдвиг множимого на один разряд влево. В (N-1 )-ой суммирующих ячейках 9 происходит суммирование накопленной в предыдущих тактах суммы частичных произведений с (N-2 )-мя разрядами частичного произведения, сформированного в этом такте, и стар« шего разряда частичного произведения, сформированного в предыдущем такте.

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

Таким образом, в j-TQM такте (7 1,2, N) на шину 5 множителя поступает j-ый разряд множителя, в сдвиговом регистре 2 производится (j-1 )-ый сдвиг множимого. В j-ой суммируннцей, ячейке 9 формируется

j-ый разряд результата умножения двух сомножителей с учетом переноса 7 -;-1О 181 образовавшегосв при формировании(j -1 )-го разряда результата умноже-, ния этих же сомножителей. Старший разряд сформированного частичного . произведения поступает на вход эле

-.-;мента 7 задержки, выход которого сое динен через (j-2 ) элемента 7,за держки с первым входом 8 (М-j +1 )-ой суммирующей ячейки 9.

В М-ом такте формируется частичное произведение множимого на стар- . 1I ший разряд множителя. В N-ой суммйрующей ячейке 9 формируется N-ый разряд результата умножения двух сомножителей. Через (М-..f ) такт сфор" мируется старший (ZN-1 )-й разряд результата умножения этих же сомножи" :телей.

В (N+f )-ом такте производится прием в сдвиговый регистр 2 нового множкмого. На шину 5 подается первый разряд нового множителя, к про,цесс умножения повторяется только с: той разницей, что в М»разрядном параллельном сумматоре хранится резуль.тат предыдущего умножения к одновременно с вычислением првизведения. двух новых сомножителей происходит суммирование результата умножения предыдущих сомножителей и сомножителей новых.

° . Для очистки параллельного сумма- М тора после вычисления суммы парных произведений вида А,1В + А Ва+...А Р ,й момент времени М(а-1 ) В (одноеременно с приемом в оегистр 2 последнего множимого) на шину 12 запрета формирования сумьМ подается импульс, который через время 1."..производит разрыв цепи Обратной связи в первой суммирующей, ячейке 9 и, поступив с третьего выхода .11 этой ячейМ на ° второй вход 19 первого тактируемого триггера 18, заносит первый разряд результата вычисления сувеая парных произведений в первый триггер 18.

Через (2N-1 )-ый такт результат вычис ления сумма парных произведений по-:

;ступает на выходные вфйы 20, т.е. на вычисление выражения вида .A B +...+ АвВе1гребуетоя:время равное (Nm+N-1 ) . Следовательно, на выпол нение одного умножения и сложения необходимо затратить М(Ф+f/m ) тактов.:

Использование новых элементовдополнительных суммирующих ячеек, элементов И, элемента ИЛИ и регистра

:сдвига дает возможность выполнять не только суммирование и суммирова ние с накоплением, но и операции умно

:жения и вычисления сумвы парных npo"" изведений вида А В +... +Л,„В„,. Это, во-первых, расширяет сферу примене-, ния сумматора, во-вторых, позволяет исключить простои оборудования при выполнении операций умножения и на копления сумм парных произведений, к,в-третьих, устраняет необходимоств создания в вычислительных устройствах отдельных сумматора и умножителя.

1018114

Составитель A. Стейанов

Редактор М. Келемеш Техред Т.фанта Корректор А Ильин

«4в

В Ю ЬЮ Ь

Заказ 3544/47 Тираж 706 Подиисное

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

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

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