Устройство для умножения с накоплением Советский патент 1984 года по МПК G06F7/52 

нены с входами соответствующих разрядов накопительного регистра, выходы накопительного регистра подключены к выходам соответствующих разрядов результата умножения-накопления усТ ройства, выходы л младших разрядов накопительного регистра соединены с входами соответствующих разрядов второго слагаемого сумматора с последовательным переносом, отличающееся тем, что, с целью повышения быстродействия, в него введен (N+L)-разрядный параллельный сумматор с ускоренным формированием переносов, причем выход (М+1)-го разряда суммы сумматора с последовательным переносом соединен с входом первого разряда первого слагаемого параллельного сумматора, выход переноса W-ro cy лмaтopa блока сумматоров

соединен с входом (W+i)-ro разряда первого слагаемого параллельного сумматора, выходы суммы сумматоров блока сумматоров соединены с входами соответствующих N-1 младших разрядов второго слагаемого параллель-, ного сумматора, выход каждого U-го разряда суммы параллельного сумматора соединен (,2,...,N+L) с первым входом соответствующего (U+M)го разряда коммутатора, выход Z-ro разряда накопительного регистра соединен с входом третьего слагаемого соответствующего (Z-М)-го сумматор.1 блока сумматоров (Z M-t-l, . . , ,) , выход d-ro разряда накопительного регистра соединен с входом соответствующего (d-M)-го разряда второго слагаемого параллельного сумматора (d M+N,..., M+N+1).

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ С НАКОПЛЕНИЕМ, содержащее матрицу умножения, состоящую из М строк по N узлов в каждой, причем узлы матрицы содержат друхвходовый элемент И, (N-1) первых узлов (М-1) последних строк матрицы содержат одноразрядные сумматоры, блок сумматоров, состоящий из (N-1) одноразрядных сумматоров, 1А-разрядный сумматор с последовательным переносом, (N+L+M)-разрядный коммутатор, (N+U+W)-разрядный накопительный регистр, причем первые входы элементов И узлов каждого столбца матрицы объединены и подключены к входу соответствующего разряда множимого устройства/ вторые входы элементов И узлов каждой строки матрицы объединены и подключены к входу соответствующего разряда множителя устройства, выход элемента И первого узла первой строки матрицы соединен с входом первого разряда первого слагаемого сумматора с последовательным переносом, выход элемента И (N-1) первых узлов (М-1) последних строк матрицы соединен с первым входом одноразрядного сумматора этого ж у.ла матрицы, выход элемента И j го узла -ой Строки матрицы соединен со вторым входом одноразрядного сумматора (J-1)-го узла

Изобретение относится к вычислительной технике и может быть использовано в арифметических устройс вах высокопроизводительных ЭВМ и в вычислительных системах, работающих в реальном масштабе времени. Известно устройство для вычисления суммы пртэизведений, содержащее два регистра сомножителей, -два сумматора, регистры суммы и разности, ко 1№1утатор, многовходовой сумматор, регистр хранения результатов tl. Недостаткам такого устройства яв ляется низкое быстродействие, что связано с последовательной и многотактной организацией обработки информации , Наиболее близким по технической сущности к изобретению является уст ройство для умножения с накоплением принятое за прототип. Данное устрой ство предназначено для параллельного умножения в двоичном коде N-раз рядного множимого на М-разрядный мн житель и последующего сложения произведения с накопленным (N+L-f-M)-раз рядным результатом и содержит матрицу умножения, состоящую из двухвходовых логических элементов И и {N-l)xM одноразрядных сумматоров, (N+L+M)-разрядные сумматор с послед нательным переносом, коммутатор с двух направлений в одно и накопител ный регистр, причем входы матрицы умножения подключены к входам разря дов входных сомножителей устройства выходы матрицы умножения соединены с входами разрядов первого слагаемо го сумматора с последовательным переносом, выходы которого соединены с первыми входами коммутатора, вторые входы коммутатора подключены к входам предварительно загружаемого в устройство операнда, выходы коммутатора соединены с входами накопительного регистра, выходы которого соединены с входами второго слагаемого сумматора с последовательным переносом и с выходами результата умножениянакопления устройства 2. Однако данное устройство характеризуется недостаточно высоким быстродействием,что связано с поочередным , выполнением операций умножения входных сомножителей и сложения полученного произведения с содержимым накопительного регистра, а также с использованием в устройстве многоразрядного сумматора с последовательным переносом. . Целью изобретения является повышение быстродействия устройства для умножения с накоплением. Поставленная цель достигается тем, что в устройство для умножения с накоплением, содержащее матрицу умножения, состоящую из М строк по Ы узлов в каждой, причем узлы матрищл содержат двухвходовый элемент И, (N-1) первых узлов (М-1) последних строк матрицы содержат одноразрядные сумматоры, блок сумматоров, состоящий из (N-1) одноразрядных сумматоров, Мразрядный сумматсф с последовательным переносом, (N+L+M)-разрядный ком-; мутатор, (Ы+Ы-М)-разрядный накопительный регистр причем первые входы элементов И узлов каждого столбца матрицы объединены и подключены к входу соответствующего разряда множимого устройства, вторые входы элементов И узлов каждой строки матрицы объединены и подключены к входу соот ветствующего разряда множителя устройства выход злемента И первого узла первой строки матрицы соединен С входом первого разряда первого сла гаемого сумматора с-последовательным переносом, выход элемента И (N-1) первыхузлов (М-1) последних строк матрицы соединен с первым входом одноразрядного сумматора этого же узла матрицы, выход элемента И j-ro узла 1-ой строки матрицы соединен со вторым входом одноразрядного сумматора (j-l)-ro узла (1+1)-ой строки матрицы ( ,3,,..,N), выход элемента И К-го узла 1-ой строки матрицы соединен со вторым входом одноразрядного сумматора (K-l)-ro узла (И-1)-ой строки матрицы (,3,..., М-1, ), выход элемента И последнего узла последней строки матрицы соединен с первым входом (N-l)-ro сумматора блока сумматоров, третьи входы всех одноразрядных сумматоров узлов второй строки матрицы соединены с шиной логического нуля, выход , суммы одноразрядного сумматора q-ro узла р-ой строки матрицы соединен со вторым входом одноразрядного сумматора (q-l)-ro узла (р-И)-ой строки матрицы (р 2,3, ... М-1, и ,3 , . , . N-1), ВЫХОД суммы сумматора г-го узла S-ой строки матрицы соединен с входом S-ro разряда первого слагаемого суммат ора с последовательным пе реносом (,3,..., М и ), выход суммы сумматора q-ro ysha t-ой строки матрицы соединен с первым входом (q-l)-ro сумматора блока сумматоров (), выход переноса одноразрядного сумматора W-ro узла р-ой строки мат рицы соединен с третьим входом сумматора W-ro узла (р+1)-ой строки мат рицы (,2,...,N-1), выход переноса одноразрядного сумматора W-ro узла t-ой строки соединен со вторым входом W-ro сумматора блока сумматоров, выход М разрядов суммы сумматора с последовательным переносом соединен с первыми входами соответствующих М младших разрядов коммутатора, вторые входы которого подключены к входам с ответствующих разрядов предварительно загружаемого в устройство операнда, управляющий вход коммутатора под ключен к входу управления предварительной загрузкой устройства, вход синхронизации которого подключен к тактовому входу накопительного регис ра, выходы коммутатора соединены с входами соответствующих разрядов накопительного регистра, выходы накопительного регистра подключены к вых дам соответствующих разрядов результата умножения-накопления устройства выходы М младших разрядов накопитель кого регистра соединены с входами соответствующих разрядов второго слагаемого сумматора с последовательным переносом,, введен (N+L)-разрядный парашлельный сумматор с ускоренным формированием переносов, причем выход .(М+1)-го разряда суммы сумматора с последовательным переносом соединен с входом первого разряда первого слагаемого параллельного сумматора, выход переноса W-ro сумматора блока сумматоров соединен с входом(W+l)-ro разряда первого слагаемого параллельного сумматора,выходы суммл сумматоров блока сумматоров соединены с входами соответствующих N-1 младших разрядов второго слагаемого параллельного сумматора, выход каждого и-го разряда сумкы параллель него сумматора соединен (,2,..., N+L) с первым входом соответствующего (U+M)-го разряда коммутатора, выход Z-ro разряда накопительного регистра соединен с входом третьего ела гаемого соответствующего (Z-М)-го сумматора блока сумматоров (,,. M+N-1), выход d-ro разряда накопительного регистра соединен с входом соответствующего (d-М)-го разряда второго слагаемого параллельного сумматора (,...,M+N+L). На фиг. I приведена блок-схемаустройства для умножения с накоплением на фиг. 2 - схемы матрицы формирования и поразрядного сложения частичных произведений входных сомножителей и блока сумматоров. Устройство содержит матрицу 1 умножения, состоящую из М строк по N узлов в каждой, причем все узлы матрицы 1 содержат по одному двухвходовому логическому элементу И 2, а (N-1) первых узлов (М-1) последних строк матрицы 1 содержат также по одному одноразрядному сумматору 3, блок сумматоров 4, состоящий из (N-1) одноразрядных сумматоров 5, причем каждый одноразрядный сумматор 3 и 5 как матрицы 1, так и блока сумматоров 4, имеет три входа слагаемых и по одному выходу сумквл и-переноса, Мразрядный сумматор с последовательным переносом 6, имеющий по М входов разрядов первого и второго слагаемых . и М+1 выходов разрядов суМмы, (N+L)- разрядный параллельный сумматор 7 с ускоренным формированием переносов; имеющий (N+L) входов разрядов первого слагаемого 8, N входов разрядов второго слагаемого 9 и (N+L-) выходов разрядов суммы, причем N младших разрядов данного сумматора 7 имеют по два входа слагаемых, (N+L+M)-разрядный коммутатор 10 с двух направлений в одно, имеющий один общий управ- . ляющий вход и по два информацйрнных входа и одному информационному выходу в каждом разряде, синхронизируемый

фронтом тактового импульса (N+L+M)разрядный накопительный регистр 11, имеющий общий тактовый вход и по одному информационному входу и выходу в каждом разряде, N входов разрядов . множимого 12, М входов разрядов множителя 13, (N+L+M) входов разрядов предварительно загружаемого операнда 14, вход управления предварительной загрузкой 15, входсинхронизации 16, (N+L4-M) выходов разрядов результата умножения-накопления 17, шину логического нуля 18. Первые входы всех лгических элементов 2 каждого столбца матрицы 1 объединены и подключены к входу соответствующего разряда мно жимого 12, а вторые входы всех логических элементов 2 каждой строки матрицы 1 объединены и подключены к Bxoiiy соответствующего разряда множителя 13, выход логического элемента 2 каждого узла матрицы 1, содержащего cyNwaTOp 3, соединен с входом первого слагаемого сумматора 3 этого же элемента матриць 1, выход логического элемента 2 каждого j-ro узла з.-ой строки матрицы 1 соединен при и ,3,...,N, а также при i 2,3,..,,М-1 и с входом второго слагаемого сумматора 3 соответствующего (j -1) -го узла (И-1)-ой строки матрицы 1, выход логического элемента 2 последнего узла последней строки матрицы 1 соединен с входом второго слагаемого (N-l)-ro сумматора 5 блока сумматоров 4, входы третьего слагаемого всех сумматоров 3 второй строки матрицы 1 подключены к шине логического нуля 18; выход суммы сумматора 3 каждого j-ro узла iой строки матрицы 11 соединен при ,3,...,М-1 и j 2,3,...,N-l с вхо дом второгослагаемого сумматора 3 соответствующего (j-l)-ro узла (i+1)ой строки матрицы 1, а при и j 2,3,...,N-1 с входом второго слагаемого соответствующего (j-l)-ro сумматора 5 блока сумматоров 4, выход переноса сумматора 3 каждого j-ro узла i-ой строки матрицы 1 соединен при ,3,.,.,М-1 и ,2,...N-l с входом третьего слагаемого сумматора 3 соответствующего j-ro узла (1+1)ой строки матрицы 1, а при и j 1,2,...,N-1 с входом третьего слагаемого соответствующего j-ro сумматора 5 блока сумматоров 4, выход логического элемента 2 первого узла первой строки матрицы 1 и выходы суммы сумматоров 3 первого столбца матрицы 1 составляют выходы 19 матрицы 1, соединенные с входами соответствующих разрядов первого слагаемого сумматора с последовательным переносом 6; выходы суммы 20 сумматоров 5 блока сумматоров 4 соединены с входами соответствующих (N-1) младших разрядов первого слагаемого параллельного сумматора 7, выходы переноса 21 сумматоров 5 блока сумматоров 4 соединены с входами (N-1) старацих разрядов второго слагаемого параллельного сумматора 7 таким образом, что выход переноса каждого 1-го сумматора 5 блока 4 соединен при ,2,..,,N-1 с входом соответствующего (1+1)-го разряда второго слагаемого параллельного сумматора 7; выход (М+1)-го разряда суммы сумматора с последовательным переносом б соединен с входом первого разряда второго слагаемого параллельного сумматора 7, М младших разрядов суммы сумматора б соединены с первыми входами 22 соответ- сЗтвующих М младших разрядов коммутатора 10, выход каждого 1-го разряда

суммы параллельного сумматора 7 соединен при ,2,,..,N+L с первым входом 22 соответствующего (1+М)-го разряда коммутатора 10, вторые входы разрядов коммутатора 10 подключены к входам 14 соответствующих разрядов предварительно загружаемого операнда, управляющий вход коммутатора 10 подключен к входу 15 управления предварительной загрузкой, вход синхронизации 16 подключен к тактовому входу накопительного регистра 11, выходы разрядов коммутатора 10 соединены с входами соответствующих разрядов накопительного регистра 11, выходы М младших разрядов накопительного регистра 11 соединены с входами соответствующих разрядов второго слапаемого сумматора б, выход каждого 1-го разряда накопительного регистра 11 соединен при , М+2,...,M+N-1 с выходом первого слагаемого 23 соответствующего (i-M)-ro сумматора 5 блока сумматоров 4, а при 1 M-i-N, M+N+l,... M-NL - с входом соответствующего (i-M)-ro разряда первого слагаемого параллельного сумматора 7, выходы всех разрядов накопительного регистра 11 подключены также к выходам 17 соответствующих разрядов результата умножения-накопления.

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

Разряды х, Xj, .... X множимого с входом 12 и разряды у, У, ..., Удд множителя с входом 13 поступают соответственно на первые йторые входы соответствующих логических элементов 2 матрицы 1, реализующих булевую функцию И. При этом на выходах логических элементов 2, каждой j-ol строки (при ,2,...,M) матрицы 1 формируется N-разрядное частичное произведение Sj, равное произведению N разрядов множимого на один j-ый разряд множителя .

Сумма всех частичных произведений равна произведению входных сомножителей. Частичные .произведения, сформированные на параллельно вКлюченных логических элементах 2 матрицы 1, поступают с выходов этих элементов на соответствующие входы сумматоров 3 матрицы 1. С помощью сумматоров 3 осуществляется поразрядное сложение частичных произведений, в основу которого положена работа линейки параллельно включенных однораз рядных полных сумматоров, Линейка, состоящая из п паргшлельно включенных одноразрядных полных сумматоров позволяет путем поразрядного сложени трех п-разрядных слагаемых, подавабмых на соответствующие входы суммато ров, формировать два п-разрядных числа, одно из которых формируется на выходах суммы, а другое - на выходах переноса сумматоров линейки. Причем поскольку на входы каждого су матора Линейки подаются разряды с одинаковыми весовыми коэффициентами о сумма двух чисел, формируемых на выходах линейки, равна,сумме трех чи сел, подаваемых на входы линейки. В предлагаемом устройстве межсоединения сумматоров 3 в матрице 1 выполнены таким образом, что сумматоры 3 каждой строки матрицы образуют линейку из (N-1) параллельно включенных одноразрядных полных сум маторов, а все сумматоры 3 данной . матрицы - (М-1) последовательно включенных линеек. Сумматоры 3 каждой строки матрицы 1 при 1 «2,3,...,М составляют линейку сумматоров, на которой к результатам, по лученным на выходах элементов ) ой строки матрицы 1 поразрядно прибавляется частичное произведение, сформиррванное на логических элемен тах 2 i-ой строки матрицы 1. В результате поразрядного сложения частичных произведений на выходах 19 матрицы 1 формируется М млгщших раз рядов произведения входных сомножителей, а на выходах узлов последней строки матрицы 1 формируется два (N-1) разрядных числа, сумма которы равна N старяиим разрядам произведения. Сложение результатов поразрядног сложения частичных произведений, сформированных на выходах матрицы 1 с содержимым накопительного регистр 11 осуществляется с помощью блока су маторов 4, сум1 атора б и параллельного сумматора 7. При этом сумматор б выполняет сложение М младших разр дов произведения входных сомножителей, которые поступают с выходов 19 матрицы 1 на входы разрядов первого слагаемого данного сумматора б, с содержимым М младд1их разрядов накопителЬного регистра 11, которое пос тупает на входы разрядов второго сл гаемого сумматора б. Причем формирование М младших разрядов результат умножения-накопления осуществляется на су 1маторе 6 одновременно с поразрядным сложением, выполняемым сумматорами 3 матрицы 1. ;БЛОК сумматоров 4 СОСТО1Л: из (N-1) параллельно включенных одноразрядных полных сумматоров 5 и выполняет поразрядное сложение (N-1)-разрядного числа, сформированного на выходах переноса сумматоров 3 последней строки матрицы i и поступающего на входы третьего слагаемого сумматоров 5 блока 4, (N-1)разрядного числа, сформированного на выходах cyMNftj сумматоров 3 со второго по {N-1)-ый узел и на выходе логического элемента 2 последнего узла последней строки матрицы 1 и поступающего на входы второго слагаемого сумматоров5 блока 4, и содержимого (N-1)-разрядов (с (М+1)-го по (M+N)ный) накопительного регистра 11, поступающего на входэл 23 первого слагаемого сумматоров 5 блока 4. Результаты поразрядного сложения, получаемые на выходах переноса 21 сумматоров 5 рлока 4, и сигнал с (М-И)-го разряда. суммы сумматора б поступают на входи 9 соответствующих разрядов второго слагаемого параллельного сумматора 7, а результаты поразрядного сложения, получаемые на выходах суммы 20 сумматоров 5 блока 4, и содержимое (L-1-1) стараих разрядов накопительного регистра 11 поступают на входы 8 соответствующих разрядов первого слагаемого параллельного сумматора 7. На выходах разрядов суммы параллельного сумматора 7 формируются (N+L) старших разрядов результата умножения-накопления. Таким образом, на выходах сумматора б и параллельного сумматора 7 формируется результат умножения-накопления . npejviaraeMoe устройство имеет два режима работы. В режиме предварительной загрузки накопительного регистра 11 на вход 15 управления предварительной загрузкой устройства подается сигнал, имеющий значение логической единицы, который поступает с входа 15 на управляющий вход коммутатора 10. В этом режиме коммутатор 10 пропускает на входы накопительного регистра 11 информацию со своих вторых входов, котоЕЯле пoдклioчены к входам предварительно загружаемого операнда 14. В режиме умножения-накопления на вход 15 устройства подается сигнал, имеющий значение логического нуля, который поступает с входа 15 на управляющий вход коммутатора 10. В этом режиме коммутатор 10 пропускает на входы накопительного регистра 11 информацию со своих первых входов 22, на которые поступает результат умножения-накопления с выходов сумматоров б и 7.

В накопительном регистре 11 осуществляется запись и хранение информации, поступгиощей с выходов коммутатора 10. Запись информации выполняется при поступлении фронта тактового импульса на вход синхронизации 16. Выдача результата умножения-накопления из регистра 11 происходит на выходы 17 устройства.

Изобретение обеспечивает повьвиение быстродействия устройства для умножения накоплением за счет того, что прибавление (N+L) старших разрядов содержимого накопительного регистра осуществляется к результатам

12

о

М

/3,

N1

N-t

f3i

5

го

г1

f

/V-/

1 fj-j

..-I tl.

..J

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

Время умножения-накопления в предлагаемом устройстве уменьшено ориентировочио на (N+L-4)xt, где t -задержка переключения одноразрядного cyivwaTopa, по сравнению с устройством для умножения с накоплением, принятым за прототип.

Af

A/

.

a

//

iW

+ f

J6

Л/

/V-/

i

fpuf.t