Конвейерное устройство для вычисления сумм произведений

 

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

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s G 06 F 7/544

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4688404/24 (22) 05.05.89 (46) 23.10.91. Бюл. М 39 (72) П.Н. Шимбирев (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1137460, кл. G 06 F 7!49, 1983, Авторское свидетельство СССР

М 1072039, кл. G 06 F 7/49, 1981, (54) КОНВЕЙЕРНОЕ УСТРОЙСТВО ДЛЯ

ВЫЧИСЛЕНИЯ СУММ ПРОИЗВЕДЕНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных устройствах цифровой обработки информации. Цель изобретеИзобретение относится к вычислительной технике и может быть использовано в специализированных устройствах цифровой обработки информации, а также в моделирующих комплексах.

Цель изобретения — повышение быстродействия при конвейерном методе вычислений сумм произведений, а также упрощение устройства.

На фиг. 1 представлена структурная схема конвейерного устройства для вычисления сумм произведений; на фиг. 2 — схема вычислительного блока; на фиг. 3 — схема блока управления; на фиг. 4 — временные диаграммы работы устройств, Конвейерное устройство для вычисления сумм произведений (см. фиг, 1) содержит последовательно соединенные m вычислительные блоки (m = и/2, где и — разрядность операндов) 1,1-1m, накапливаю. Ы,, 1686437 А1 ния — повышение быстродействия при конвейерном методе вычислений сумм произведений, а также упрощение устройства.

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

5 управления, при этом первый вход блока

1,1 подключен к нулевой шике, второй и третий входы блока 1.1 подключены к ши- 0 нам 6 и 7 соответственно, выходы блоков

1.1-1(m-1) с первого по третий соединены с Ch первым, вторым и третьим входами после-,фЪ дующего блока 1,2-1.m соответственно, пер- () вый выход блока 1.m соединен с первым с входом сумматора 2, второй вход сумматора

2 соединен с входом регистра 4 и подключен к выходу регистра 3, вход кото рого соединен с выходом сумматора 2, первый и второй выходы блока управления соединены с первыми и вторыми управляющими входами блоков 1,1-1.m. третий выход соединен с входом записи регистра 3, а четвертый — с входом записи регистра 4, вход блока уп равления соединен с шиной 8 пуска, выход регистра 4 соединен с выходной шиной 9

1686437 устройства. В состав каждого из вычислительных блоков (см. фиг. 2) входят регистры

10 и 11, схемы 12,1-12.4 сравнения, блок 13 логики, состоящий из элементов 14.1-14.4 равнозначности и элементов ИЛИ 15.1-15.3, мультиплексоры 16 и !7, сумматор 18, блок

19 инверторов, коммутатор 20, регистры 21 — 23, выходы которых я вл я ются соответственно вторым и первым выходами вычислительного блока, выход регистра 21 является третьим выходом вычислительного блока, входы регистров 10 и 11 являются вторым и третьим входами блока, входы записи регистров 10 и 11 соединены с первым управляющим входом вычислительного блока, входы схемы 12.1 сравнения подключены к прямому и инверсному выходам регистра

10. входы схемы 12.2 сравнения — к прямому и инверсному выходам регистра 11, входы схемы 12.3 — к инверсным выходам регистров 10 и 11, входы схемы 12.4 сравнения — к прямому выходу регистра 11 и инверсному выходу регистра 10. Входы элемента равнозначности 14.1 подключены к прямым выходам схем 12.2, 12.3 сравнения и инверсному выходу схемы сравнения 12,4. Входы элемента 14.2 равнозначности подключены к инверсным выходам схем 12.2, 12.3 сравнения и прямому выходу схемы 12.4 сравнения, Входы элемента 14,3 равнозначности подключены к прямому выходу схемы 12.1 сравнения и инверсным выходам схем 12,3 и 12.4 сравнения, Входы элемента 14,4 равнозначности подключены к инверсному выходу схемы 12.1 сравнения и прямым выходам схем 12.3 и ll2.4 сравнения. Выходы элементов 14.1 и 14,2 равнозначности через элемент ИЛИ 15,1 подключены к первому управляющему входу мультиплексора

16. Выходы элементов 14,1 и 14.3 равнозначности через элемент ИЛИ 15.2 подключены к вторым управляющим входам мультиплексоров 16, 17. Выходы элементов.

14,3 и 14.4 равнозначности через элемент

ИЛИ 15.3 подключены к первому управляющему входу мультиплексора 17. Информационные входы мультиплексоров 16 и 17 подключены к прямым и инверсным выходам регистров 10 и 11, Выход мультиплексора 16 соединен с входом третьего регистра

22 и одним из входов сумматора 18, другой вход которого является первым входом вычислительного блока, а выход соединен с входом четвертого регистра 23, Первый вход коммутатора 20 соединен с выходом мультиплексора 17. Второй вход коммутатора 20 через блок !9 инверторов подключен к выходу мультиплексора 17. Управляющий вход коммутатора каждого J-ro из вычислительных блоков 1.1-1 m подклк>чен к выходу

J-ro разряда мультиплексора 17, а к блоку 19 инверторов подключены выход знакового разряда и выходы разрядов с О+1)-го по п-й, где n — младший разряд кода. Входы записи

5 регистров 21 — 23 подключены к второму управляющему входу вычислительного блока, выходом блока 1.m является выход реги,стра 23. Блок управления (см. фиг. 3) содержит генератор 24 импульсов, выход

10 которого соединен с первым входом элемента 25 равнозначности, второй вход которого соединен с выходом триггера 26, счетчик 27 и постоянное запоминающее устройство (ПЗУ) 28, первый, второй, третий и

15 четвертый выходы котооого являются, соответственно, первым, вторым, третьим и четвертым выходами блока управления, установочный вход триггера 26 является входом блока управления и подключен к ши20 не 8 пуска, вход сброса триггера 26 подключен к четвертому выходу ПЗУ 28, а выход. через формирователь 29 импульсов соединен с входом установки в ноль счетчика 27, выход элемента 25 равнозначности соеди25 нен со счетным входом счетчика 27, выход которого соединен с входом ПЗУ 28.

Конвейерное устройство для вычисления сумм произведений определяет значение

XI yi

1=1 где $ — число суммируемых произведений путем последовательного вычисления част35

zI = х у по следующей формуле

zi = xiyi = g 1/2 о . (2)

j =1 причем ш определяется рекуррентно

40 Uj+1=- макс(мин (Uj, v j); мин (Uj, v j)), (3) чр-! = макс(ш, uj, v 1,v j ), где v j = vj - 1/2!, 45 Uo= xl: Y p = vp = у!„ J = 1, 2, .„, т при вычислении по формуле(2) погрешность не превосходит 1/4т+1, следовательно, для выполнения вычислений с точностью до

1/2п достаточно взять число членов m, рав50 ное и/2.

Устройство работает следующим образом, По сигналу "Пуск (см, фиг. 4а) на шине

8 блока управления устройства сигнал с вы55 хода триггера 26 (см. фиг, 4б) разрешает прохождение импульсов (см. фиг. 4в) генератора 24 через элемент 25 равнозначности на счетчик 27. С помощью ПЗУ 28 код с выхода счетчика преобразуется в последо1686437 вательноети импульсов, представленные на фиг. 4г. д, и, и импульс, представленный на фиг. 4к. Ilo импульсу с первого выхода ПЗУ записывается информация в регистры 10, 11 вычислительных блоков, при этом в регистры блока 1.1 записываются коды сомножителей х(1) и у(1), Вычисление сумм произведений величин Xi, Yi начийается после п/2 тактов по сигналу с третьего выхода

ПЗУ 28.

Общее время Т вычисления суммы произведения равно

Т = (и/2 + S + 1)Т у, где Тву — время выполнения операции в вычислительном блоке.

Формирование произведений z = Х!У! в блоке 1,J осуществляется следующим образом: в блоке 1.1 производится определение величин и! и v>, исходя из исходных значений ио = Х и vo = Y<, переменные Xi u Yi поступают в регистры 10, 11, В регистрах 10 и 11 осуществляется получение инверсных значений величин u< = -Xi и vo = -Yi из кодов у, ч0.

Формирование величин и! и v! производится по формуле (3), При этом реализация непрерывно-логических выражений (НЛВ)

F (ui+!) = макс(мин(щ,vi); мин (щ, vi) )

Р(ч1+!)= макс (щ, щ, v i, v i) производится путем применения гибридных пороговых и депороговых операторов пф) и Ох(а), а также преобразования двоичных векторов P/à в соответствии с табл. 1.

В табл. 1 приведены значения следующих пороговых операторов;

p,= п(ч,,v,); p, = п ц,u; j

p, = ï (U, ÷, ); )ф, = =П (0;, ч, )

=П(U,U )=

4, в Ы;

D,при и (q)

r,=(,,1= О ., . М ;

I (, (, а и Ll)> ; -4- ° )1 0, при U ° .

2 переменные щ, v i, щ, v i закодированы кодами двоичных переменных а !,а 2(для выражения F(ui+>)/, a! и а (для выражения F(vy-!)) следующим образом: щ-+10; v J O; щ-+11; v i 1.

Выполнение пороговых операций по формуле (4) осуществляется на схемах сравнения 12,1, 12,2, 12.3, 12.4 J-го вычислительного блока, причем схема 12.1 сравнения

5 формирует переменнуюф!; 12.2 — переменную Д; 12.3 — переменную j4, а 12.4— переменную Р4. Сформированный в соответствии с табл. 1 код P

15 а 2 =p1p3$4 )Вфф4 а" = PiP@4 А@4 а"z = рьЯЯ4 v /3фз/!4 коды а и а" управляют мультиплексорами

17 и 16, на входы которых подаются переменные щ, v i, v i, щ и выбирают одну из

25 этих величин в соответствии с табл. 1. При определении первого разряда произведения Xi, Yi на выходе мультиплексоров 16 и

17, входящих в блок 1,1, формируются в каждой из ситуаций (см, фиг. 1) следующие величины (см, табл. 2).

Пример. Пусть Xi = u< = 5/8 (код 0101, старший разряд знаковый), Y! = vo = v 0 = 1/4 (код 0010), 35 тогда -X! = -5/8 (код 1010), -У! =- -1/4 (код 1101), т, е, . (ситуация 2 в табл. 1).

На выходах схем сравнения вычислительного блока 1,1 получают

40 3! = 1; Pz = 1; j3g =- О; Р4 = О, а на выходах элементов ИЛИ а"! =- О; a z = 1; а"! = 1; а"2=1.

При этом на выходы мультиплексора 16 проходит код v, а мультиплексора 17 — u<, 45 и! = макс (мин(5/8, 1/4); мин(5/8, -1/4) )=.1/4, v! = макс (5/8, 1/4,-5/8, -1/4 ) = 5/8, v> = F(vi) всегда > О, Первый член приближения u =

= u 1/2 = l/4 1/2 = 1/8 образует разность v = v! — 1/2 = 1/8, разность реализуется на коммутаторе 20; так как uo = 5/8il/2 (код 0101), то l р = 1 и на выход коммутатора

20 разряды 2 и 3 приходят без инверсии, т. е. код 01 () + 1 = 2; и = 3).

На выходах первого блока 1.1 образуются следующие числа: на первом выходе (регистр 23) и = u! 1/2 + О = (uo = vp = 1/4) 1/2 = 1/8, на втором выходе (регистр 22) 1G86437

01=чо= 1/4, на третьем выходе (регистр 21) ч 1 = v) - 1/2 =- 1/8.

Затем процесс осуществляется аналогично на вычислительных блоках 1.2, .„, 1,m.

На втором блоке чр = макс(1/4, 1/8, -1/4, -1/8) -- 1/4

02 = макс(мин(1/4, 1/8); мин(-1/4, -1/8)) =-1/8 и 2 = 02 1/4 + о 1 = 1/32 + " /8 =. z1 = х1у1 (произведение правильное).

Значение переменной и1 поступает с выхода мультиплексора 16 на.вход регистра

22, с выхода которого осуществляется выбор числа щ. Эта величина передается на второй выход вычислительного блока 1.1.

Переменная v1 поступает на коммутатор 20, где осуществляется вычитание константы

1/2", где J = 1, 2, ..., щ.

Вычитание производится путем инвертирования ч1 относительно старшего

Разряда, начиная с (I + 1)-го разряда, одновременно инвертируется знаковь . разряд.

Если J-й разряд равен нулю, то и1-.вертирование не производится и передаются разряды, начиная с (J+ 1)-го, т. е. в первом блоке формируется величина ч 1 = vp — 1/2 (формула 3).

Значение v 1 передается через регистр

21 на первый выход вычислительного блока

1.1. На третий выход передается и-разрядный код (знаковый разряд и (n-1) разрядов мантиссы).

Значение u 1 = u< 1/2; так как на второй вход сумматора 18 подается нулевой константы (в вычислительном блоке 1.1), то этот код щ . 1/2 передается через регистр 23.

Затем производится определение величины v 2, о1, u „âî втором вычислительном блоке 1.2, на входы которого поступают величины v 1, u<, u i из первого вычислительного блока. Процесс формирования v z, щ, u 2 аналогичен тому, как это осуществляется в первом вычислительном блоке, В течение m циклов вычисления переменных и1 Ч1, и2, V2...., Um Чп1(ПОСИГНЭЛЭМС первого и второго выходов блока 5 управления) на сумматорах 18 последовательно образуются суммы переменных 1/2u1,.„, +1/4uz; ... 1/2 urn, из KGTophlx формируется значение прпизеедение з = 1/21и1.

) 2=1

Суммирование всех произведений г (! = 1, 2, „S), входящих в сумму (1), осуществляется конвейерно после S+ 1+(и/2 = m) тактов, поступающих с блока 5 управления.

S тактов суммирования переменных z>, ..., z, осуществляется по сигналу 28,3, передаваемому на регистр 3. В результате на выходе накапливающего сумматора 2 образуется общее значение

z ==- xi yi, 5

) =1 которое по сигналу с третьего выхода блока

5 управления записывается через регистр 3 в выходкой регистр 4, Выходной код поступает на шину 9.

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

1, Конвейерное устройство для вычисления сумм произведений, содержащее последовательно соединенные вычислительные блоки, каждый из которых содержит пять регистров, сумматор, элементы равнозначности и элементы ИЛИ, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия и упрощения устройства, в него введены накапливающий сумматор, шестой и седьмой регистры и блок управления, а в каждый вычислительный блок введены четыре схемы сравнения,два мультиплексора, блок инверторов и коммутатор, причем входы первой и второй схем сравнения соединены соответственно - прямыми и инверсными выходами первого и второго регистров, входы третьей схемы сравнения соединены с инверсными выходами первого и второго регистров, а входы четвертой — с инверсным выходом второго регистра и прямым выходом первого регистра, входы первого элемента и третьей схем сравнения и инверсным выходом четвертой схемы сравнения, входы второго элемента равнозначности соединены с,прямым выходом четвертой схемы сравнения и инверсными выходами третьей и второй схем сравнения, входы третьего элемента равнозначности соединены с прямым выходом первой схемы сравнения и инверсными выходами третьей и четвертой схем сравнения, входы четвертого элемента равнозначности соедииены с прямыми выходами четвертой и третьей схем сравнения и инверсным выхо45 дом первой схемы сравнения, выходы первого и второго элементов равнозначности соединены с входами первого элемента

ИЛИ, входы второго элемента ИЛИ соединены с входами третьего и первого элемен5р тов равнозначности д входы третьего элемента ИЛИ вЂ” с выходами четвертого и третьего элементов равнозначности, выходы первого и второго элементов ИЛИ соединены с управляющими входами первого мультиплексоРа, а выходы третьего и второго элементов WIN соединены с управляющими входами второго мультиплексора, информационные входы обои:; мультиплексоров соединены с прямыми и инверсными выходами первого и второго регистров, вы1686437

Таблица

Ситуация взаимного располо- Г,ц „) F|ч Д, (F (ц,Д

I r.— г з Ф. жения переменных ц, ч, ц, ч с1 (Ы

" Л.

Номер ситуации

v с u ац саv

u v.c v.

1 j — 3 5 ц. ñ ч ч) а ц

3 3 5 ((ч„аu u c v.

f (ч ц сц ач (u. cv av (ц.

1-- 3 ((u i.ч i. ч: r» ц.

v u u ° сv, v 1«0

u i 100 ц 1000

vÄ 001

0001

u 0011

01«

v(0110

01 и1

Ч (У3

О1

10

Ч °

Ъ (t

10

00

01 ход первого мультиплексора соединен с входом третьего регистра и первым входом сумматора, второй вход которого соединен в каждом вычислительном блоке, кроме первого, с первым вь,ходом пред- 5

ыдущего вычислительного блока, в первом вычислительном блоке этот вход соединен с нулевой шиной, выход третьего регистра соединен с вторым выходом вычислительного блока, а выход сумматора со- 10 единен через че вертый регистр с первым выходом вычислительного блока, выходы с () + 1)-го по и-й разрядов второго мультиплексора соединены с первым входом коммутатора (где j — номер вычислительного 15 блока; и — разрядность операндов), второй вход которого соединен с этими же выходами мультиплексора через блок инверторов, управляющий вход коммутатора соединен с выходом J-го разряда второго мульти- 20 плексора, выход коммутатора соединен через пятый регистр с третьим выходом вычислительного блока, входы записи первого и второго регистров в каждом вычислительном блоке соединены с первым 25 выходом блока управления, а входы записи третьего, четвертого и пятого регистров в каждом вычислительном блоке соединены с вторым выходом блока управления, выход четвертого регистра последнего вычисли- 30 тельного блока соединен с первым входом накапливающего сумматора устройства, выход которого через шестой регистр соединен с вторым своим входом, вход записи этого регистра соединен с четвертым выходсм блока управления, а выход этого регистра через седьмой регистр соединен с выходной шиной устройства, вход записи седьмого регистра соединен с третьим выходом блока управления, который связан также с входом внешней шины запроса, вход блока управления соединен с входом ц(, ины пуска, 2, Устройство по и. 1, о т л и ч а ю ще ес я гем, что блок управления содержит генератор импульсов., элсмент равнозначности, счетчик. постоянчое запоминающее устройство, триггер и формирователь импульсов, причем установочнь(й вход триггера является входом блока управления и подключен к шине пуска устройства, выход триггера соединен с входом формирователя импульсов и первь;м входом элемента равнозначности, второй вход которо(о соединен с выходом генератора импульсов, выход элемента равнозначности соединен со счетным входом счетчика, выход формирователя импульсов соединен с кходом установки в нуль счетчика, выход которого соединен с входом постоянного запоминающего устройства, выходы которого с первого по четвертый соединены соответственно с первого по четвертый выходами блока управления, четвертый выход постоянного запоминающего устройства соединен также с входом сброса триггера.

1686437

12

Таблица 2

Ситуация

Фиг 1

1686437

1686437

Запуск

11 0 LLI з 8

LJ L3 и/2+ S

m= и/г и!г+1 и к

Фи2 LF

Составитель Ю. Варакин

Техред M.Ìîðãåíòàë Корректор М, Кучерявая

Редактор Т. Шагова

Производственно-издательский комбина "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 3598 Тираж Подписное

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

113035, Москва, >К-35, Раушская наб„4/5