Конвейерное устройство для вычисления сумм произведений Советский патент 1991 года по МПК G06F7/544 

fe

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

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

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

На фиг. 1 представлена структурная схема конвейерного устройства для вычисления сумм произведений; на фиг. 2 - схема вычислительного блока; на фиг. 3 - схема блока управления; на фиг. 4 - временные диаграммы работы устройств

Конвейерное устройство для вычисления сумм произведений (см. фиг. 1) содержит последовательно соединенные m вычислительные блоки (т п/2, где п - разрядность операндов) 1.1-1т, накапливающий сумматор 2, регистры 3 и 4, а также блок 5 управления, при этом первый вход блока

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

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

t

GO VI

устройства. В состав каждого из вычислительных блоков (см. фиг. 2) входят регистры 10 и 11, схемы 12.1-12.4 сравнения, блок 13 логики, состоящий из элементов 1-4.1-14.4 равнозначности и элементов ИЛИ 15.1-15.3, мультиплексоры 16 и 17, сумматор 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 и 12.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 через блок 19 инверторов подключен к выходу мультиплексора 17. Управляющий вход коммутатора каждого j-ro из вычислительных блоков 1.1-1.ГП подключен к выходу

j-ro разряда мультиплексора 17, а к блоку 19 инверторов подключены выход знакового разряда и выходы разрядов с (| + 1}-го по п-й, где п - младший разряд кода. Входы записи

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

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

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

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

i

z Ј xi yi(1)

i 1

где S - число суммируемых произведений путем последовательного вычисления част- ных произведений

г xiyi по следующей формуле

г xiyi 2, 1/2 и)

1

(2)

причем ui определяется рекуррентно 40 uj+i (uj, v j): мин (uj, v j) ,

vj+i макс uj, и), v j,v j ,

(3)

где v j vj - 1/2,

u0 x,: v 0 v0 yi; J 1, 2, ..., m

при вычислении по формуле (2) погрешность не превосходит 1/4т+1. следовательно, для выполнения вычислений с точностью до 1/2п достаточно взять число членов т, равноеп/2.

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

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

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

T (n/2 + S+ 1)Тву,

где ТВу - время выполнения операции в вычислительном блоке.

Формирование произведений zi XiYi в блоке 1.J осуществляется следующим образом: в блоке 1.1 производится определение величин ui и vi, исходя из исходных значений и0 Х0 и v0 Y0; переменные X; и YI поступают в регистры 10, 11.

В регистрах 10 и 11 осуществляется получение инверсных значений величин UQ -Х| и /о -Yi из кодов УО, v0.

Формирование величин щ и vi производится по формуле (3).

При этом реализация непрерывно-логических выражений (НЛВ)

F uj+i (и,У)); мин (tij, vj)

F vj-ц макс uj, Uj, v j, v j производится путем применения гибридных пороговых и депороговых операторов пф) и Dx(«), а преобразования двоичных векторов fi/a в соответствии с табл. 1.

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

переменные uj, v j J uj, v j закодированы кодами двоичных переменных , (для выражения ,ai йог (для выражения ) следующим образом: Uj-HO; v j-K)1.

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

формирует переменную/ 1; 12.2 -- переменную 12.3 - переменную Дз. а 12.4 - переменную. Сформированный в соответствии с табл. 1 код поступает на элементы 14.1-14.4 равнозначности,

которые осуще вляют кодовое преобразование Р/д по табл. 1 в соответствии с логическими выражениями:

cti fhfijp ffhfhfi4

Cf2 Plfl3p4 fhfl3fa

cf -frfiafbtffrfrfa cf z-ptf& fhfijiA

()

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

25 этих величин в соответствии с табл. 1. При определении первого разряда произведения Xi, YI на выходе мультиплексоров 16 и 17, входящих в блок 1.1, формируются вкаж дои из ситуаций (см. фиг. 1) следующие ве30 личины (см. табл. 2).

Пример. Пусть Xi - u0 5/8 (код 0101. старший разряд знаковый),

Yi v0 v 0 1/4 (код 0010), 35 тогда-Xi -5/8 (код 1010),

-Yi- -1/4 (код 1101), т.е. (ситуация 2 в табл. 1).

На выходах схем сравнения вычислительного блока 1.1 получают 40 1;/92 1;/fe-0;/34 0,

а на выходах элементов ИЛ И а 1 -0; 1 ; 1 .

При этом на выходы мультиплексора 16 проходит код v0, а мультиплексора 17 - и0. 45 щ (5/8,1/4); мин(-5/8,-1/4).1/4, vi макс 5/8, 1/4.-5/8, -1/4 5/8,

vj F(VJ) всегда 0.

Первый член приближения u i ui 1/2 1/4 1/2 1/8 образует раз- 50 ность v i vi - 1 /2 1 /8, разность реализуется на коммутаторе 20; так как и0 /2 (код 0101), то 1р 1 и на выход коммутатора 20 разряды 2 и 3 приходят без инверсии, т. е. код 01 0 + 1 2; п 3).

55На выходах первого блока 1.1 образуются следующие числа:

на первом выходе (регистр 23) u i-ui 1/2 + 0 uo v0 1/4 1/2 1/8,

на втором выходе (регистр 22)

ui v0 1/4.

на третьем выходе (регистр 21) v i vi- 1/2 1/8.

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

На втором блоке

v2 - /4, 1 /8, -1 /4, -1 /8 1 /4 иг (1 /4,1 /8); мин(-1 /4, -1 /8) 1 /8 u 2 U2 1/4 + uM 1/32 + 1/8 zi-xiyi (произведение правильное).

Значение переменной ui поступает с выхода мультиплексора 16 на вход регистра 22, с выхода которого осуществляется выбор числа ui. Эта величина передзэтся на второй выход вычислительного блока 1.1. Переменная vi поступает на коммутатор 20, где осуществляется вычитание, константы

1/21, где 1,2rrj.

Вычитание производится путем инвертирования vi относительно старшего разряда, начиная с (j + 1)-го разряда, одновременно инвертируется знаковым разряд. Если j-й разряд равен нулю, то HI вертиро- вание не производится и передаются разряды, начиная с ( + 1)-го, т. е. в первом блоке формируется величина

v i vi - 1 /2 (формула 3). Значение v i передается через регистр 21 на первый выход вычислительного блока 1.1. На третий выход передается п-разряд- ный код (знаковый разряд и (п-1) разрядов мантиссы).

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

Затем производится определение величины v 2, ui, u ,| во втором вычислительном блоке 1.2, на входы которого поступают величины v i, m. u i из первого вычислительного блока. Процесс формирования v 2, 112, u 2 аналогичен тому, как это осуществляется в первом вычислительном блоке. В течение m циклов вычисления переменных

u i, v i, u 2, v 2u m. v m (по сигналам с

первого и второго выходов блока 5 управления) на сумматорах 18 последовательно образуются суммы переменных 1/2ui

+1/4U2; ... 1/2mum, из которых формируется

значение произведения zi Ј 1 /2 uj.

1

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

S тактов суммирования переменных ziZs

осуществляется по сигналу 28.3, передаваемому на регистр 3. В результате на выходе

накапливающего сумматора 2 образуется общее значение

i

г -- 2, xi у, ,

| 1

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

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

Выходной код поступает на шину 9.

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

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

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

е мультиплексора, а выходы третьего и второго элементов ИЛИ соединены с управляющими входами второго мультиплексора, информационные входы обои:; мультиплексоров соединены с прямыми и инверсными выходами первого и второго регистров, выход первого мультиплексора соединен с входом третьего регистра и первым входом сумматора, второй вход которого соединен в каждом вычислительном блоке, кроме первого, с первым выходом пред- ыдущего вычислительного блока, в первом вычислительном блоке этот вход соединен с нулевой шиной, выход третьего регистра соединен.с вторым выходом вычислительного Блока, а выход сумматора со- единен через че1вертый регистр с первым выходом вычислительного блока выходы г. fi + 1)-го по n-й разрядов второго мультиплексора соединены с первым входом ком- мутаторз (где j - номер вычислительного блока; п - разрядность операндов), второй иход коюрого соединен с этими выходами мульти 1лекг.ора через блок инверторов, управляющий РХОД коммуiaTCDd соединен с выходом j-ro разряда второго мульти- плексора, выход коммутатора соединен че рез пятый регистр с третьим выходном вычислительного блока, входы записи первого и второго регистров в каждом вы исли- тельном блоке соединены с первым выходом блока управления а входы записи третьего, четвертого и пятого регистров в каждом вычислительном блоке соединены с вторым выходом блока управлени-л выход четвертого регистра последнего вычисли- тельного блока соединен с первым входом накапливающего сумматора устройства, выход которого через шестой регистр соединен с вторым своим входом, вход записи этого регистра соединен с четвертым выходом блока управления, а выход этого регистра через седьмой регистр соединен с выходной шиной устройства, вход записи седьмого регистра соединен с третьим выходом блока управления, который связан также с входом внешней шины запроса, вход блока управления соединен с входом шины пуска.

Таблица 1

61

Т 1 1

Таблица 2

L 1

Z.rt 9891