Устройство для умножения

 

Изобретение относится к вычислительной технике и может быть использовано для построения быстродействующих устройств для обработки информации, работающих в масштабе реального времени. Цель изобретения - повышение быстродействия. Устройство содержит (3N<SP POS="POST">2</SP>+N/2) однобитовых умножителей (ОУ) 1, где N - разрядность сомножителей, образующих матрицу, каждый J-й столбец которой содержит N+J, где J=1,...,N, однобитовых умножителей 1, N портов ввода битов первого сомножителя, 2N портов ввода битов второго сомножителя, 2N портов вывода битов результата, шину 2 нулевого сигнала. Каждый ОУ выполнен в виде матрицы простых логических и коммутационных элементов размерностью 4<SP POS="POST">.</SP>5. 2 ил.

СОЮЗ COBKTCHHX

СОЦИМИСТИЧЕСНИХ

РЕа1УБЛИН (19 (И) А1 р1)5 О 06 F 7/52

ГО

П0

ПР

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

ti

us

El пр

gi е»

«и q

4z а у(2 (2 (4 (7 ту (7 (5 (5

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

ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ГННТ СССР

) 4402823/24-24

) 04.04,88

) 23.11.90, Бюл, У 43

) Марийский политехнический инстиим. А.М. Горького

) Н.М. Кравцова и С.Г. Кравцов

) 681.325(088.8)

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

0436 42, кл. 0 06 Г 7/52, )983 °

Мс Саппу 1,V. et al. Implementan of signal processing functions

ng I — bit systolic arrays.

ctron. Lett., 1982, 18. р.241-243.

2 (54) YCTPOACTBO gHR YNHOEEHHR (57) Изобретение отнбсится к вычислительной технике и может быть использовано для построения быстродействующих устройств для обработки информации, работающих в масштабе реального времени. Цель изобретения - повышение быстродействия. Устройство содержит (3n +n)/2 однобитовых умножителей (0У) 1 где n - разрядность сомножителей, образующих матрицу, каждый j-й столбец которой содержит n+j, где

j=1 ° ° .,и, одиобитовых умножителей 1, у 9 9 Ф

1608649 п .п о р тTо в8. ввода битов первого сомножителя, 2п портов ввода битов второго сомножителя, 2п портов вывода битов результата, шину 2 нулевого сигнала.

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

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

На фиг.1 представлена структурная схема устройства для умножения; на фиг;2 — функциональная схема однобитового умнржителя, Устройство для умнс"«ения состоит из образующих матрицу однобитовых умно жителей (ОУ) 1 и содержит шину 2 нулезого сигнала, умножители 1 соединены между собой так, что входы 3 и 4 строк и входы 5-7 столбцов ОУ. 1< соединены с выходами 8 H 9 строк ОУ

<,<-! с выходами 10-12 столбцов ОУ,, выходы .8 и 9 строк ОУ 1, соединены с входами 3 и 4 строк ОУ 1; +<, выходы

10-12 столбцов ОУ 1, < соединены с входами 5-7 столбцов ОУ;+<> . Входы 3 строк, граничных с ОУ 1, являются портами ввода битов второго сомножителя: для бита Х < — первого бита второго сомножителя — вход 3 ОУ 11<, для би га Х вЂ” второго бита второго сомножителя — вход 3 ОУ 1д < и т.д., для бита Xn-ro бита и-разрядного вто- 40 рого сомножителя — вход 3 ОУ n < для нулевых битов Х „„...Х „ соответственно битов второго сомножителя, учитывающих расширение произведения двух и-разряд- 45 ных операндов — входы 3 ОУ 1<1,<<, °

° ° °,ОУ 1 „„. Входы 5 ОУ 1 первой

1 строки матрицы — порты ввода битов первого сомножителя, причем вход

5 ОУ 1<,< — порт для ввода первого бита У< первого сомножителя, вход 5

ОУ 1<, — порт ввода второго бита У первого сомножителя и т.д., вход 5

ОУ 1<<. — порт ввода и-го бита У п-разрядного первого сомножителя, Входы 6 и 7 ОУ 1 первой строки матрицы и..входы 4 строк граничных ОУ

,4 ° юо ОУ 1< << ОУ 1< < а ° ° СУ 1д< соединены с шиной 2 для осуществлеКаждый ОУ выполнен в виде матрицы простых!логических и коммутационных элемейтов размерностью 4ч5. 2,ил. ния установки нуля входных переносов и частичных произведений. Выходы 9 строк ОУ 1 последнего столбца матрицы являются портами вывода результата произведения удвоенной точности: выход 9 ОУ 1 <1 --порт вывода первого бита и < произведения, выход 9 ОУ

1 „ — порт вывода бита п произведения и т.д., выход 9 ОУ 1 „ „ - порт вывода 2п-ro бита и произведения п удвоенной точности.

ОУ 1 (фиг.2) содержит матрицу из двадцати синхронно управляемых логических и коммутационных элементов 1332, причем элементы 13,16 и 24 — коммутаторы "столбец-столбец и столбецстрока", элементы 14 и 29 — коммутаторы "столбец-строка и строка-столбец", элементы 15 и 17 — коммутаторы "строка-столбец", элементы 18, 20, 21, 22 и 28 — коммутаторы "столбец" столбец и строка-строка", элементы

19 и 26 — элементы И с выводом результата в столбец и коммутацией

"строка †стро", элемент 23 — коммутатор "столбец-столбец", элемент

25 — элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с выводом результата в строку и коммутацией "столбец-столбец", элементы 27 и 31 — элементы ИСКЛЮЧАЮЩЕЕ ИЛИ с выводом результата в столбец, элемент 30 — элемент И с выводом результата в строку, элемент 32 — коммутатор "столбец-строка".

Элементы ОУ 1 соединены между собой локально так, что выход строки элемента 13 соединен с входом строки элемента 14, выход строки которого соединен с входом строки элемента 15, выход строки элемента 16 соединен с входом строки элемента 17, выход строки элемента 18 соединен с входом строки элемента 19, выход строки которого соединен с входом строки элемента 21, выход строки которого соединен с входом строки элемента 22.

Выход строки элемента 24 соединен с входом строки элемента 25, выход строки которого соединен с входом строки элемента 26, выход строки которого с

В с с с т с с ц г т н с б с б ч с б с б

;1 ! д

1 д п т

5 16 единен с входом строки элемента 27, )ход строки элемента 28 соединен входом строки элемента 29, выход роки которого соединен с входом роки элемента 30, выход строки корого соединен с входом строки элента 31. Выход столбца элемента 13 единен с входом столбца элемента ,выход столбца которого соединен входОм столбца элемента 23, выход олбца которого соединен с входом олбца элемента 28. Выход столбца емента 14 соединен с входом столбэлемента 19, выход столбца которосоединен с входом столбца элемен24, выход столбца которого соедин с входом столбца элемента 29, ход столбца элемента 15 соединен входом столбца элемента 20, выход олбца которого соединен с входом олбца элемента 25, выход столбца торого соединен с входом столбца емента 30.

Выход столбца элемента 16 соединен входом столбца элемента 21, выход олбца которого соединен с входом олбца элемента 26, выход столбца торого соединен с входом столбца емента 31. Выход столбца элемен17 соединен с входом столбца элента 22, выход столбца которого соенен с входом столбца элемента 27, ход столбца которого соединсн с одом столбца элемента 32. Вход 5 олбца элемента 13 является входом та первого сомножителя, вход 6 олбца элемента 14 является входом та частичного произведения, вход 7 олбца элемента 16 является входом реноса, вход строки 3 элемента 18 яется входом бита второго сомнотеля, вход 4 строки элемента 28 ляется входом транзитного бита стичного произведения, выход 8. роки элемента 22 является выходом та второго сомножителя, выход 9 роки элемента 32 является выходом та частичного произведения, выход столбца элемента 28 является выхом бита первого сомножителя, выход столбца элемента 29 является выхом транзитного бита частичного оизведения, выход 12 столбца элента 31 является выходом переноса следующий разряд. Задержка на один кт в каждом логическом и коммутаонном элементе осуществляется

08649 6

D-триггером, установленным на выходе.

Работа устройства заключается в

5, следующем. Биты первого сомножителя У,,У ...,,У поступают на порты ввода первого сомножителя, начиная со старшего бита, поступающего в первый слева столбец на вход 5 .ОУ 1< в первый временной интервал, который равен пяти тактам. Поступление очередных битов на соответстзуюг ие порты происходит с задержкой, равной пяти тактам, по одному такту на один столбец матрицы ОУ l. Биты первого сомножителя продвигаются по матрице сверху вниз по столбцам и в каждом очередном ОУ l столбца взаимодействуют с битам r второго сомножителя.

2р Биты второго сомножителя X,Х ...,,Х у поступают на порты ввода второго сомножителя, начиная с младшего бита

Х», поступающего в первую верхнюю строку матрицы на вход 3 ОУ 1< в

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

30 строку матрицы ОУ 1. Биты второго сомножителя синхронно продвигаются по матрице слева направо по строкам и в каждом очередном ОУ 1 взаимодействуют с битами первого сомножите35

Таким образом, в первый временной интервал в ОУ 1<, взаимодействуют биты Х и У, нулевой бит переноса и нулевые биты частичного произведе40 ния. Во второй временной интервал бит Х переходит в ОУ I,<, куда в этот же временной интервал поступает бит У „ 3 нулевой бит переноса, нулевой бит частичного произведения-вход45 ной транзитный бит частичного произведения от ОУ I „ . Во второй интервал времени бит У переходит в ОУ

1 „, куда в этот же временной интервал поступает бит Х, бит переноса в

50 следующий разряд от ОУ 1,,, нулевой бит частичного произведения и тран- .. зитный бит от ОУ 1, . В третий вре-. менной интервал бит Х, переходит в

ОУ 1 для взаимодействия с битом

55 У „ и т.д. В и-й временной интервал бит X поступает в ОУ 1„„, где иразрядность операндов, для взаимодействия с битом второго сомножителя У», .нулевым входным битом переноса, би1 6086 том частичного произведения, также равным нулю (входной бит), бит частичного произведения от ОУ 1, „,, который-транзитом проходит через ОУ 1,„ для взаимодействия с соответствующими битами в ОУ lg,я Ь(п+1)-й временной иитервап. В (и+1)-й временной интервал на порте вывода результата выход ,8 ОУ 1,> появляется первый бит произведения п,бит У взаимодействует с битом Х, битом переноса от ОУ 1, битом частичного произведения от

ОУ 1 „ < поступающим транзитом через

ОУ l „., а бит частичного произведения от ОУ 1 „ транзитом проходит через ОУ 1< „ для взаимодействия с соответствующими битами в ОУ 1,д .в (и+2)-й временной интервап и т.д, В (Зп+1)-й интервал последний бит п < появляется на порте вывода результата .— выход 8 ОУ 1 „ .

Рассмотрим процесс взаимодействия битов в ОУ I, В первый временной такт на вход столбца элемента 13 по- 25 ступает бит первого сомножителя 7 „, во второй такт этот бит поступает соответственно на вход строки элемен,та 14 и вход столбца элемента 18, в третий такт транзитом. через выход столбца элемента 14 поступает на вход столбца элемента 19 для взаимодейст вия с битом второго сомножителя Х;, который во второй временной такт поступает на вход строки элемента 18, а в третий - на вход строки элемента 19, Бит частичного произведения поступает во второй временной такт на вход столбца элемента 14 и транзитом через выход строки элемента 14 в тре- 40 тий временной такт поступает на вход строки элемента 15. Бит первого сомножителя в третий временной такт поступает на вход столбца элемента 23.

В четвертый такт на вход столбца эле-4 мента 16 поступает бит переноса от предыдущего ОУ 1, бит частичного произведения от элемента 15 — на вход столбца элемента 20, на вход строки элемента 15 — транзитный бит второго сомножителя от элемента 19, на вход столбца элемента 24 - результат логического умножения от элемента )9, на вход столбца элемента 28 — бит второго сомножителя Y без изменения про.двигающийся по столбцу матрицы ОУ 1 °

В пятый такт бит переноса поступает на вход строки элемента 17 от элемента 16, который он минует без измене"

49 . 8 ния, на вход элемента 21 поступает бит переноса также без изменения, на вход столбца элемента 25 для сложения по модулю "2" поступает бит частичного произведения, а на вход строки — бит результата логического умножения от элемента 19, без изменения переданный элементом 24 через выход строки, бит второго сомножителя покидает ОУ 1

1 через выход столбца элемента 28 и переходит на вход столбца элемента 13

ОУ 1<,,,, транзитный бит частичного, произведения, который в четвертый такт поступил на вход строки элемента 29 для передачи его через выход столбца элемента 29 в шестом такте на вход столбца элемента 14 ОУ

1„, . В шестой временной такт бит переноса поступает на вход столбца . элемента 22 и на вход столбца элемента 26, на вход строки элемента 22 поступает транзитный бит первого сомножителя, на вход строки элемента 26 поступает результат сложения по модулю "2" от элемента 25, на вход столбца элемента 25 поступает бит частичного произведения от элемента 20, а на вход строки — бит результата логического умножения от элемента 19, без изменения переданный через выход строки элемента 29. В седьмой временной такт бит первого сомножителя Х °

1 покидает ОУ 1, „ через выход строки элемента 22 для по ступл ения на вход строки элемента 18 ОУ 1, ... бит пеI реноса от элемента 22 поступает на вход столбца элемента 27, на вход строки которого поступает бит результата сложения по модулю "2" передан) ный без изменения через выход строки элемента 26, бит результата логического умножения от элемента 26 поступает на вход столбца элемента 31, на вход строки которого поступает результат логического .умножения от элемента 30 через выход его строки. В восьмой временной такт бит переноса покидает матрицу ОУ 1, через выход

1,1 столбца элемента 31, результат сложения по модулю "2" от элемента 27 по-: ступает на вход столбца элемента 32 для передачи его на девятом временном такте на выход строки элемента.32 и на вход строки элемента 22, OV l q>.

Одновременно в ОУ 1 находятся биты восьми пар сомножителей, последовательно поступающие в каждый очередной такт и синхронно продвигаю1608649

10 щи то од за за на та ро та по ся по элементам матрицы с частотактирования. Если длительность ого такта равна К и соответственно ержке одного элемента ОУ 1 то ержка ОУ 1 составит ЯК, а началь5 задержка матрицы умножения сосит (3n-1) 8К тактов. При умножедвух векторов размерностью М азрядные числа полное время форми- 10 ания результата произведения сосит (3n-1) 8К+ИК при условии, что дая пара сомножителей векторов тупает в матрицу в каждый такт.

l5 рмула изобретения жащ леи обр бец одн ды та умн ди вог рен жит тел ля со ум со са мат со (i мат со ум вто бит . бит од ди ти би та од ди в жи би о

Устройство для умножения, содерЗтР+и е (, ) однобитовых умножите2

20 (n — разрядность сомножителей), зующих матрицу, каждый j-й столкоторой (j=l,...,n) содержит n+j битовых умножителей, причем вхоервого сомножителя и входного би- 25 ереноса (i,j)-ro однобитового жителя матрицы (i=l,...,n+j) соеены соответственно с выходами персомножителя и выходного бита песа (i-l,j)-го однобитового умноеля матрицы выход второго сомножи(i,j)-ro аднобитового умножитеатрицы соединен с входом второго ожителя (i j+I)-го однобитового ожителя матрицы, выходы первого ожителя и выходного бита перено- (i,j)-ro однобитового умножителя ицы соединены с входами первого ожителя и входного бита переноса

l,j)-го однобитового умножителя ицы соответственно, выход второго ножителя (i,j)-го однобитового ожителя матрицы соединен с входом

oro сомножителя (i,j+1)-го одноового умножителя матрицы, выход а частичного произведения (i,j)-го обитового умножителя матрицы соеен. с выходом транзитного бита часного произведения (i-l,j)-го одноового умножителя матрицы, вход бичастичного произведения (i,j)-го обитового умножителя матрицы соеен с выходом бита частичного произения (а,1-1)-го однобитового умноеля матрицы, выход транзитного а частичногс произведения (i,j)-го. обитового умножителя матрицы соеен с входом бита частичного произения (i+1,j)-го однобитового умно1 жителя матрицы, вход бита частичного произведения {i,j)-го однобитового умножителя матрицы соединен со входом транзитного бита частичного произведения (i,j+I)-го однобитового умножителя матрицы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, каждый однобитовый умножитель выполнен B виде матрицы размернос1ью 4 5 из синхронно управляемых логических и коммутационных элементов, первый столбец которой содержит первый коммутатор "Столбец — столбец и столбец - строка", второй коммутатор "Столбец †столбец и строка— строка", третий коммутатор "Столбец— столбец", четвертый коммутатор "Столбец — столбец и строка — строка", второй столбец содержит пятый коммутатор "Столбец — строка и строка— столбец", первый элемент И с выводом результата в столбец и коммутацией

"Строка — строка", шестой коммутатор

"Столбец — строка и столбец — столбец, седьмой коммутатор "Столбец— сгрока и строка — столбец", третий столбец содержит восьмой коммутатор

"Столбец — строка", девятый коммутатор "Столбец — столбец" и строка— строка", первый элемент ИСКЛ?0ЧА ОЩЕЕ

ИЛИ с выводом результата в строку и коммутацией "Столбец — столбец", второй элемент И с выводом результата в столбец и коммутацией "Строка— строка", четвертый столбец содержит десятый коммутатор "Столбец— строка и столбец — столбец", одиннадцатый Коммутатор "Столбец — столбец и строка — строка", третий элемент

И с выводом реузльтата в строку и второй элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с выводом результата в столбец, пятый столбец содержит двенадцатый коммутатор "Столбец - строка", тринадцатый коммутатор "Столбец — столбец и строка — строка", третий элемент

ИСК1ПОЧАИЦЕЕ ИЛИ с выводом результата в столбец и четырнадцатый коммутатор "Столбец — строка", при этом связи в матрице однобитового умножителя локальные в направлении строк и столбцов, вход столбца первого коммутатора является входом бита первого сомножителя, вход строки второго коммутатора является входом бита второго сомножителя, вход столбца десятого коммутатора является входам переноса, вход столбца пятого коммутатора

ll

l608649 12 ,является входом бита частичного про- теля, выход строки четырнадцатого изввдения, вход строки четвертого коммутатора является выходом бита коммутатора является входом транзит- частичного произведения, выход столбного бита частичного произведения, ца. второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ выход столбца четвертого коммутатора является выходом переноса, выход является выходом бита первого сомно- столбца седьмого коммутатора является жителя, выход тринадцатого коммутато- выходом транзитного бита частичного ра является выходом второго сомножи- произведения. х, Составитель В. Березкин

Редактор А. Шандор Техред М.Ходанич Корректор М. Самборская .

Заказ 3611 Тираж 563 Иодаисное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина,301