Конвейерное вычислительное устройство

 

Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных ЦВМ. Цель изобретения - расширение функциональных возможностей за счет возможности вычисления сумм произведени. Конвейерное вычислительное устройство содержит сумматор 1, п вычислительных блоков 3, п блоков 4 коррекции и блок 12 формирова- . НИН управляющих сигналов. 2 ил.,, 5 табл. (Л

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (51)4 G 06 F 77544

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ВСЕжмцн %

ОПИСАНИЕ ИЗОБРЕТЕНИЯ К А ВТОРСКОМ У СВИДЕТЕЛЬСТВУ (Риг. f (21) 4224404/24-24 (22) 06.04.87 (46) 23.10.88. Бюл. № 39 (71) Киевский институт инженеров гражданской авиации им. 60-летия СССР (72) Л.Я.Нагорный, И.А.Жуков (SU) и Д.Сингх (?И) (53) 681.325.5(088.8) (56) Байков В.Д., Смолов В.Б. Специализированные процессоры. Итерационные алгоритмы и структуры. — M.: Радио и связь, 1985, с. t14.

Andreus M. and Eggerding D.À.

А pipelined. computer architecture for цп Ы14 . elementary function evaluation. — Comput. Elect. Eng., 1978, v. 5, р. 194 . (прототип).,. SU 1432512 А 1 (54) KOHBEAEPHOE ВЫЧИСЛИТЕЛЬНОЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных ЦВМ. Цель изобретения — расширение функциональных возможностей за счет возможности вычисления сумм произведений. Конвейерное вычислительное устройство содержит сумматор

1, п вычислительных блоков 3, и блоков 4 коррекции и блок 12 формирования управляющих сигналов. 2 ил., 5 табл.

1432512

Изобретение относится к вычислительной технике и предназначено для построения на его основе специализированных ЦВМ.

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

На фиг.1 представлена функциональ- 1О ная схема конвейерного вычислительно,го устройства на фиг.2 — функцио-нальная схема блока коррекции.

Конвейерное вычислительное устрой- 1» тво (фиг. 1) содержит сумматор 1, ход 2 первого операнда, и вычисли ельных блоков 3, где и - разрядность операндов, и блоков 4 коррекции, вход второго операнда, вычислительный блок содержит регистры 6 и 7, сумматоры-вычитатели 8 и 9, коммутаторы 0 и 11, блск 12 формирования управК

У У ) э х + у2 к т уг1 хг gyes г

Операция умножения скаляра на скаляр выполняется по унифицированному алгоритму Волдера по формулам (3) х;+„ х;.

Операция умножения вектора на ска" ляр выполняется по унифицированному

4О алгоритму Волдера по формулам х;,„=х;+Я., х,2

1 1 (4) у, =. у Я; у; 2)1.

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

11-1 1

К; = П (1+ 2 ) . (5)

»О

Таким образом, полученные значения х „ и у„ (после (n"1)-й итерации) в

К раэ больше истинных координат вектора после поворота, поэтому необходима коррекция полученных результа1 1 тов, т.е. надо найти х„ —, у„. —.

М

Существуют различные методы ком" пенсации. х+ К(х cos (Ш + у sin9) y+ K(y ° cos Π— х ° sin9) у

О = arctg(--)

У где х, у — координаты исходного вектора х+, y+ — координаты вектора, повернутого на угол Я)

К вЂ” коэффициент удлинения вектора.

Вычисление выражения (1) в предлагаемом устройстве осуществляется по унифицированному алгоритму Волдера. х ° — х - .у -2

1+1 1 1 1 (г) у;+ = у;+E zt 2 где g, = +1 — функция, указывающая направление поворота, заранее вычислена и хранится в дешифраторе: (0,1,2,..., и-1) - номер итерации.

Отличие алгоритма Волдера от пред-. лагаемого унифицированного алгоритма Волдера состоит в том, что алгоритм Волдера предполагает вычисление на каждой итерации, а унифицированный алгоритм Волдера — не на каждой итерации. Значение f, вычисляют заранее и хранят в дешифраторе, так как угол поворота векторов заранее известен. ляющих сигналов, вход 13 управления устройства.

Блок коррекции (фиг.2} содержит триггеры 14 и 15, регистр 16 делителя, регистр 17 веса, регистр 18 частичного остатка, регистр 19 результата, элементы И 20 и 21, сумматорывычитатели 22-25, шифратор 26, триггер 27.

Ф

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

Пусть необходимо умножить вектор с координатами х„ и у1 на вектор с координатами х и у . Вначале с помощью операции "вектор" определяют угол

QH= arctg(y /x ) ° Затем выполнив операцию "поворот вектора" на угол® с учетом разложения векторов на составляющие, получают

143?512

В предлагаемом устройстве каждый следующий шаг итерации алгоритма Волдеря начинается сразу после получения одной новой цифры результата пос- 5 ледовательно с делением его на К, в полуавтономном режиме вычислений. Высокая скорость вычислений в устройстве достигается за счет использова-, ния полуавтономного принципа вычис- 1ð лений, отличающегося от классического тем, что операция над операндами выполняется одновременно с формированием разрядов результата выполнения предыдущей операции. Такой принцип вычислений предполагает использование для представления промежуточных результатов избыточной квазиканонической системы счисления.

2Р

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

В первом такте на первые входы блока 3 поступают первые операнды множимого x). Ha вторые входы блока 3 25 поступают вторые операнды множителя у . Блок 3 осуществляет арифметические операции с операндами по формуле унифицированного алгоритма Волдера. В результате первая цифра полученного произведения передается в блок 4 коррекции, так как при вращении происходит удлинение промежуточного результата внутри блока 3. Результат без удлинения поступает в

35 сумматор 1, где запоминается. Во втором такте в блок 3 поступают соответственно следующие коды множимого х и множителя у, которые после выполнения арифметических операций с вто- 4р рыми операндами в блоке 3 передаются в блок 4 коррекций. Результат без удлинения поступает в сумматор 1.

Аналогично описанному выполняются следующие арифметические операции с соответствующими операндами.

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

Таблица

ВыполняеДвойное кодирование цифры

Цифра квазиканонического мая операция кода

01

=А+ В

Блок 3 работает следующим образом.

В первом такте поступают соответственно коды множимого х, и коды множителя у, в регистры 6 и 7. С начала очередной итерации коммутаторы 10 и

11 соединяют соответствующие выходы регистров 6 и 7 с входами сумматороввычитателей 8 и 9 таким образом, что на их входы поступают соответственно величины х,. 2 " и у, 2 . Кроме того, на вторые входы сумматоров-вычитателей 8 и 9 поступают величины х и у,, полученные на выходах сумматоров-вычитателей 8 и 9. Величины х и у

14 Eá1 поступают в блок 4 коррекции, где анализируется деформация поворота вектора.

Работа сумматоров-вычитателей 8 и 9 управляется по величинам Я, хранящимся в блоке 12, который выдает очередное значение E по номеру

1 итерации i. Номер итерации i используется для управления работой коммутаторов 10 и 11.

Во втором такте производится запись результатов вычислений из первого блока 4 коррекций во второй блок

3, т.е. значения х . и у;,, без уд1+1 линения полученных из первого блока коррекций 4 записывается в регистры

6 и 7 второго блока 3 соответственно.

Одновременно в регистры 6 и 7 первого блока 3 поступает код второй пары чисел (множимого х „ и множителя у,l).

В первом блоке 3 производится выполнение первой итерации над вторым операндом, аналогичное итерации в первом такте над первым операндом, а во втором блоке 3 выполняется вторая итерация над первым операндом.

В третьем такте производится запись результатов вычислений из первого и второго блоков 4 коррекций во второй и третий блоки 3 соответственно, и одновременно в регистр 6 и регистр 7 первого блока 3 вычисления

1432512

Таблица 2

Значения на выходах элементов И 20 и 21 соответствен но перации, выполнямые в сумматорахычитателях 22 и

4 соответственно

0

0 0

5 итерации поступает третий операнд (код множимого х> и множителя у ) .

В первом блоке 3 выполняется первая итерация над третьими операндом, во втором - вторая итерация над вто5 рым операндом, в третьем - третья итерация над первым операндом.

В дальнейшем результаты предыдущих блоков поступают в последующие блоки, в первый блок поступает новый опеанд и т.д.

При подаче на вход 13 блока 12 коа номера первой итерации на выход ервой схемы И подается сигнал "t™, оответствующий Е„ +1, при подаче а вход 13 блока 12 кода второй итеации на выходе блока 13 появляется игнал "0", соответствующий E<= -1. 2р

:аким образом, на выходе дешифратора озникает развернутая во времени небходимая последовательность значеий Е;, 25

Работа блока 4 коррекций.

На первом такте работы устройства в первом блоке 4 блока коррекций на входы триггеров 27 и 14 подаются со о1тветственно логические "1" и "0", З0

Йа вход триггера.15 - логический "0"

9 на входы регистра 16 делителя — код

1 пасха — = Ь прп i О аа пхпаы

К у и

I регистра 17 веса — код 00010...0, на 35 в оды регистра 18 частичного остатка — код числа х;+, = а „и у;+, = с „ п и i = О, а на входы регистра 19 результата — нули. Все числа представляются с четырьмя знаковыми разря- 4О дами (0000, ХХ...Х).

После приема операндов на указанные узлы содержимое регистра 16 делителя поступает на входы сумматора-вы- 45 читателя 22, на другие входы которого поступает содержимое регистра 19 результата. Одновременно содержимое регистра 18 частичного остатка поступает на входы сумматора-вычитателя 50

24, на другие входы которого поступа"" ет содержимое регистра 19 результата. ,В зависимости от значений на входах элементов И 20 и 2 1, на сумматорахвычитателях 22 и 24 осуществляется либо сложение операндов, либо их вычитание, либо передача первого операнда без изменения в соответствии с табл. 2.

П р и м е ч а н и е. "4" - передача первого операнда без изменения.

Значения восьми старших разрядов выхода сумматора-вычитателя 24 являются входами шифратора 26, в зависимости от значения которых на выходах шифратора 26 в соответствии с табл. 3 формируется код разряда частного весом 2 в квазиканонической системе счисления (1,0, 1), который затем поступает на входы триггеров 27 и 14 и на управляющие входы сумматоров-вычитателей 23 и 25.

Т а б л и ц а 3

Пифра избыточного Состояние триггеквазиканонического ров кода

13 14

Затем содержимое с выходов сумма= тора-вычитателя 22 поступает на входы сумматора-вычитателя 25, на другие входы которого поступает содержимое с выходов сумматора-вычитателя 24.

Одновременно на входы сумматора-вычитателя 23 поступает содержимое выходов регистра 19 результата, на другие входы сумматора-вычитателя 23 поступает содержимое регистра 17.

В сумматорах-вычитателях 25 и 23 в зависимости от значений на выходах шифратора 26 осуществляется либо сложение, либо вычитание операндов, либо пропуск операнда без изменения в соответствии с табл. 4.

512

Значения на выходах шифратора 2 соответственно

0 0

1432

Т а б л и ц а 4

Операции, выполняеte в сумматорах5 иитателях 25 и 23 гистра 18 частичного остатка код числа х;+, = а и у;„= с при . = 2, на входы регистра 19 реэультата— нулевые значения.

На девятом такте на входы устройства осуществляется подача операндов

;,— = Ьз ° х;., = a3 и у = сзпри

3. В дальнейшем описанные преобразования повторяются для каждого из блоков устройства и на n + 4 - 3 такП р и м е ч а н и е. "x" — переда-15 ча первого операнда без измене- 2р ния.

На втором такте работы устройства осуществляется передача информации на регистр следующего (второго) блока 4. На триггеры 27 и 14 поступает 25 содержимое с выходов шифратора 26. На триггер 15 поступает содержимое с выхода триггера 15 первого блока 4. На входы регистра 16 делителя поступает содержимое выхода сумматора-вычитате- Зр ля 22 первого блока 4, на входы регистра 17 веса — содержимое регистра

17 веса первого блока 4, сдвинутое вправо на один разряд, на входы регистра 18 частичного остатка поступа- ет содержимое сумматора-вычитателя

25 первого блока 4, сдвинутое влево на один разряд, на входы регистра 19 результата поступает содержимое выходов сумматора-вычитателя 23 перво- 40

ro блока 4.

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

На устройства 5р подаются следующие элементы итерации: на входы триггеров 2? и 14 первого блока 4 соответственно "1" и "0", на вход триггера 15 логическая "1", на

1 55

;входы регистра 16 делителя — = Ь

К; при i = 1, на входы регистра 17 веса число 000100...00, на входы рех;+ те (з — количество звеньев —, и

Ki у1 1 — — ), на выходе сумматора-вычитате1 ля 12 (и+1)-ro блока 4 формируется результат вычисления. Время вычисления при этом составит n+4(m-1)+1 вычисления.

Сумматоры-вычитатели 22-25 представляют собой параллельные комбинационные сумматоры-вычитатели с частичными групповыми переносами.

Шифратор 26 представляет собой постоянное запоминающее устройство (ПЗУ), прошивка которого осуществляется в соответствии с табл. 5.

Выполнение арифметических операций в устройстве осуществляется в избыточном квазиканоническом коде (1,0, 1).

Для кодирования цифр результата используются триггеры 27 и 14 в соответствии с табл. 3.

В устройстве при продвижении информации с первого блока 4 на (п+1)-й блок 4 последовательно в каждом блоК+1 ке 4 определяется разряд весом 2 очередного звена итерации.

Для формирования делителя (†)

К; очередной итерации каждый блок 4 содержит сумматор-вычитатель 22. Для устранения ошибок, возникающих при выполнении деления в полуавтономном режиме, каждый блок содержит сумматор-вычитатель 24.

Перевод цифр результата иэ квазиканонической системы счисления н двоично-позиционную осуществляется с помощью сумматора-вычитателя 23.

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

1432512

Таблица5

Входы шифратора 26

1 2

0000 0000 О

0000 0001 О

О

О

0000 0010 О

0000 0011 О

О

0000 0100 О

ОООО 0101 1

0000 0110 i

О

0000 0111 1

0000 1000 1 !

° O Ф 4 а °

0111 1110 1

° ° °

° ° Э

0111 1111 1 l000 ОООО 1

1000 0001 -1

О

Э ° °

О

О

О

О

О

О

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

Конвейерное вычислительное устройство, содержащее и вычислительных блоко::, где n — - разрядность операндов, причем каждый вычислительный блок содержит первый, второй суммато55

1000 0010

° е °

1111 1000

1111 1001

1111 1010

1111 1011

1111 1100

1111 1 l01

1111 1110

1111 1111

Цифра Выходы шифрачастного тора 26

30 ры-вычитатели и первый, второй р истры, причем входы первого и второго регистров 1-го вычислительного блока, где = 1,п, соединены соответственно с входами первого и второго операндов устройства, выходы младших разрядов первого и второго регистров

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

11 t4 триггера последующего блока коррекции, первый информационный вход первого сумматора-вычитателя i-ro блока коррекции соединен с выходом регистра делителя i-ro блока коррекции, выход первого сумматора-вычитателя

i-ro блока коррекции соединен с входом регистра делителя последующего блока коррекции, выход регистра, веса

i-ro блока коррекции соединен с первым информационным входом второго сумматора-вычитателя i-ro блока коррекции, выходы (n+3)-х старших разрядов регистра веса i-ro блока коррекции соединены с входами (п+3)-х младших разрядов регистра веса последующего блока коррекции, выходы (и+1)-х старших разрядов регистра веса i-ro блока коррекции соединены с входами (и+1)-х младших разрядов первого сумматора-вычитателя -го блока коррекции, выход регистра частичного остатка i-ro блока коррекции соединен с первым .информационным входом третьего сумматора-вычитателя i-го блока коррекции, выход регистра результата

i-го блока коррекции соединен с вторым информационным входом второго сумматора-вычитателя i-ro блока коррекции, выходы (и+1)-х старших разрядов регистра результата i-го блока коррекции соединены с вторыми информационными входами (й+1)-х младших разрядов третьего сумматора-вычитате32512 12 ля 1-го блока коррекции, выходы первого и второго элементов И i-ro блока коррекции соединены соответственно

5 с первым и вторым управляющими входами третьего сумматора-вычитателя данного блока коррекции, выход первого сумматора-вычитателя i-ro блока коррекции соединен с входом регистра

1О делителя последующего блока коррекции, первым информационным входом четвертого сумматора-вычитателя i-го блока коррекции, выход старшего разряда третьего сумматора-вычитателя

i-го блока коррекции соединен с входами шифратора, второй выход третьего сумматора-вычитателя -го блока коррекции соединен с вторым информационным входом четвертого сумматора-вычитателя i-го блока коррекции, выходы шифратора, первый и второй, соединены соответственно с первым и вторым управляющими входами второго и четвертого сумматоров-вьгчитателей -го бло25 ка коррекции и с входами первого и второго триггеров i-го блока коррекции, выходы (п+1)-х младших разрядов четвертого сумматора-вычитателя (i-ro блока коррекции соединены с входами (и+1)-х старших разрядов регистра частичного остатка, выход второго сумматора-вычитателя i-ro блока коррекции соединен с входом регистра результата последующего блока коррекции.

1432512

Составитель М.Есенина

Техред Л.Сердюкова Корректор М.Пожо

Редактор Е.Папп

Заказ 5441/41

Тираж 704 Подписное

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

1!3035, Москва, Ж-35, Рауй ская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4