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

 

Изобретение относится к вычислительной технике и может быть использовано при создании специализированных вычислительных устройств..Целью изобретения является расширение функциональных возможностей устройства за счет умножения кватернионов. Устройство содержит блок 1 управления, регистр 6 множителя, четыре мультиплексора 7-10, три сумматора 11, 14, 15, регистр 19 результата и четыре умножителя 20-23. Цель изобретения достигается за счет введения дополнительных . каналов параллельной обработки компонент вектора, причем каждый канал обработки имеет двухтактный конвейер, и изменения алгоритма функционирования блока управления. 1 з. п. ф-лы, 2 табл., 3 ил.

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

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

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

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

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

ПРИ ГКНТ СССР

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

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

Фиг./ (21) 4798974/24 (22) 05.03.90 (46) 07.03.92. Бюл. ¹ 9 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) И. И. Дражан, Я.А. Калиновский, M. В. Синьков, В. П. Тарасенко и Е. М. Швец (53) 681.325(088.8) (56) 1, Рабинер Л., Гоулд Б, Теория и применение цифровой обработки сигналов. М.;

Мир, 1978, с. 572, рис, 8,30.

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

¹ 399859, кл, G 06 F 7/38, 1973, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ВЕКТОРОВ

„„Я2 „„1718213 А1 (57) Изобретение относится к вычислительной технике и может быть использовано при создании специализированных вычислительных устройств..Целью изобретения является расширение функциональных возможностей устройства за счет умножения кватернионов. Устройство содержит блок 1 управления, регистр 6 множителя, четыре мультиплексора 7 — 10, три сумматора

11, 14, 15, регистр 19 результата и четыре умножителя 20 — 23. Цель изобретения достигается за счет введения дополнительных каналов параллельной обработки компонент вектора, причем каждый канал обработки имеет двухтактный конвейер, и изменения алгоритма функционирования блока управления. 1 з, п. ф-лы, 2 табл., 3 ил.

1718213 второго сумматора и четвертым выходом 55

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

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

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

Известные устройства не позволяют выполнять операции над четырехмерными векторами, которыми являются кватернионы (гиперкомплексные числа).

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

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

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

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

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

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

2 — функциональная схема блока управления; на фиг, 3 — временная диаграмма работы предлагаемого устройства, Устройство для умножения векторов содержит блок 1 управления, входы синхронизации, запуска и сброса которого соединены соответственно с входами синхронизации 2, запуска 3 и сброса 4 устройства, а первый выход 5 подключен к входу синхронизации регистра 6 множителя, первый, второй, третий и четвертый выходы которого соединены соответственно с первыми, вторыми, третьими и четвертыми информационными входами первого 7, второго 8, третьего 9 и четвертого 10 мульти1718213 плексоров. Первый управляющий вход мультиплексора 7 соединен с управляющим входом первого сумматора 11, первым управляющим входом мультиплексора 9 и вторым выходом 12 блока 1 управления, третий выход 13 которого подключен к второму управляющему входу мультиплексора 7, управляющему входу третьего сумматора 14 и второму управляющему входу мультиплексора 8. Первый управляющий вход последнего соединен с вторым управляющим входом мультиплексора 10, управляющим входом второго сумматора 15 и четвертым выходом 16 блока управления, пятый выход

17 которого соединен с вторым управляющим входом мультиплексора 9 и первым управляющим входом мультиплексора 10.

Шестой выход18 блока управления подключен к входу синхронизации регистра 19 результата и входам синхронизации первого

20, второго 21, третьего 22 и четвертого 23 умножителей, входы первых сомножителей которых соединены соответственно с первым 24, вторым 25, третьим 26 и четвертым

27 информационными входами устройства, а входы вторых сомножителей — соответственно с выходами мультиплексоров 7, 8, 9 и

10. Входы первого и второго слагаемых сумматора 11 соединены соответственно с выходами умножителей 20 и 21, выходы умножителей 22 и 23 соединены соответственно с входами первого и второго слагаемых сумматора 15. Выходы сумматоров 11 и

15 соединены соответственно с входами первого и второго слагаемых сумматора 14, выход которого соединен с информационным входом регистра 19 результата, выход которого соединен с выходом устройства, Вход 2 блока 1 управления соединен с первым входом элемента ИЛИ 28 (фиг. 2), второй вход которого подключен к входу 3 блока управления, Вход 4 последнего соединен с установочным входом счетчика 29, первым и вторым входами элемента И—

ИЛИ вЂ” НЕ 30 и входом первого элемента НЕ

31, выход которого соединен с установочным входом первого триггера 32. Синхровход С триггера 32 соединен с выходом элемента ИЛИ 28, входом второго элемента

НЕ 33, и первым входом элемента ИЛИ-HE

34, а инверсный выход — с вторым входом элемента ИЛИ вЂ” НЕ 34, выход которого соединен с выходом 18 блока 1.управления и счетным входом счетчика 29. Первый выход счетчика 29 соединен с выходом 12 блока управления, входом третьего элемента НЕ

35 и третьим входом элемента И-ИЛИ вЂ” НЕ

30, выход которого соединен с установочным входом второго триггера 36. Синхровход триггера 36 соединен с выходом второго

60 элемента H Е 33, а выход — с выходом 5 блока управления, выход 13 которого соединен с вторым выходом счетчика 29, входом четвертого элемента не 37 и четвертым входом элемента И вЂ” ИЛИ-НЕ 30, а выходы 16 и 17 блока соединены соответственно с выходами элементов HE 35 и 37, На фиг, 3 приняты следующие обозначения, 2 — синхросигнал на входе 2 блока 1 управления, 3 — сигнал запуска на вхОде 3, 4 — слгнал сброса на входе 4, 32 — сигнал на выходе триггера 32, 5, 12, 13, 18 — сигналы на соответствующих выходах блока 1 управления, 19 — сигналы на выходе регистра 19 результата, Устройство работает следующим образом, В исходном состоянии по сигналу 4 сброса (логическая "1") счетчик 29 и триггеры 32, Зб обнуляются, соответственно на выходах 5, 12, 13, 18 будет логический "0", а на выходах 16. 17 — логическая "1". При снятии сигнала сброса и при отсутствии сигнала 3 запуска устройство остается в исходном состоянии, Выдача сигнала 3 запуска по отрицательному фронту синхросигнала (логический "О") разрешает прохождение тактового импульса через элемент ИЛИ 28. По отрицательному фронту этого импульса устанавливается в единицу второй триггер 36, записывая в регистр 6 множителя компоненты вектора (кватерниона) аг, Ьг, сг, бг, установленные на входах 27, 26, 25, 24. По переднему фронту сигнала с выхода элемента ИЛИ 28 триггер 32 перебрасывается в едлничное состояние, и на его инверсном выходе появляется логический "0", разрешая прохо>кдение тактового сигнала через элемент ИЛИ вЂ” Н Е 34, В этот же момент времени изменяется состояние счетчика 29, что приводит к изменению выходных управляющих сигналов 12, 13. 16, 17, 18.

Для объяснения алгоритма работы блока 1 управления рассмотрим алгоритм операции умножения кватернионов.

Кватернион как разновидность гиперкомплексного числа имеет четыре компонента: одну вещественную и три мнимых, т,е. он мо>хет быть представлен в виде четырехмерного вектора s=a+b MI+dq, Пусть

s1 а1+Ь1 +с1)+б lk и s2=аг+Ь21+с )+бган, тогда

s3=s I+s2=e к-Ь1Ь2 с1сг — б1б 2+(e1ьг+ ь q аг+с1 бгб1сг» + (а;сг — Ь1бг+с1аг+б 1Ь2)Яа1бг+Ь1сг-с1Ь2с Ьг+б1аф.

Второй вектор s2 заносится в регистр 6 умножителя, а первый вектор s1 считывается из памяти (или другого устройства) четыре раза, Так как каждый из четырех каналов обработки имеет двухтактный конвейер, то вся операция умножения занимает пять так1718213

Таблица 1 тов. Если обрабатываются несколько векторов друг за другом, то это время уменьшается до четырех тактов. Результатом операции умножения является выдача четырех компонент результирующего вектора

s3=33+t)3i+c3j+cI3k. Счетчик 29 предназначен для определения такта выполнения и соответственно для формирования сигналов управления. В табл. 1 приведены режимы работы сумматоров 11, 15, 14 в зависимости от нулевого состояния счетчика 29.

B табл. 2 приведены состояния выходов мультиплексоров 7, 8, 9, 10 в зависимости от состояния счетчика 29.

Таблица2

Все сигналы управления формируются в соответствии с табл. 1 и 2. Управляющий сигнал 18 является сигналом синхронизации конвейерных регистров: первый конвейерный регистр — внутренние выходные регистры умножителей 20, 21, 22, 23, а второй — регистр результата. Информация в эти регистры заносится по переднему фронту синхросигнала. Сигнал 5 записи в регистр множителя выдается (переход из "0" в "1") блоком 1 управления с появлением очередного отрицательного фронта синхросигнала (выход элемента ИЛИ 28) при условии предварительного сброса триггера 36 в нулевое состояние. Триггер 36 сбрасывается в ноль при появлении сигнала 4 сброса или всех единиц на выходе счетчика 29.

Режим функционирования подтверждает временная диаграмма, показанная на фиг. 3.

Форма представления чисел в предлагаемом устройстве фиксирования запятая.

Разрядность чисел может быть наращиваемой. В устройстве могут быть использованы следующие микросхемы: регистр 6 множителя и регистр 19 результата — 1533 РИ23, 15

55 мультиплексоры 7, 8, 9, 10 — 1533 КП2, умножители 20, 21, 22, 23 — 1802 В Р5, сумматоры

11, 14, 15 — 1533 ИПЗ и 1533 ИП4, счетчик 29 — 155 ИЕ7, остальные элементы — микросхемы серии 155 или 555.

Предположим, что разрядность обрабатываемых чисел равна 16, При условии использования выше указанных микросхем ориентировочное время такта конвейера можно определить из следующих выражений:

1=1ф+ tr + t а :+ „,. где 1ф — время формирования управляющих сигналов, tr — время задержки сигналов на регистре; tea — время коммутации на мультиплексорах; AM — время умножения, t=ty+tetcM, где tr — время задержки на регистре умножителя; tcM — время суммирования.

Ориентировочно: t=50+18+22+140= 220 нс, t=50+18+100=170 нс.

Таким образом, принимаем время такта равным 220 нс, При непрерывном потоке входной информации предлагаемое устройство обеспечивает производительность 1,2

Моп/с (под операцией подразумевается операция умножения двух кватернионов, время выполнения которой равно 880 нс).

Переход на более быстродействующую серию микросхем (531) обеспечивает производительность (при такте 190 нс) порядка

1,3 Моп/с, т,е. существенного выиграша в быстродействии не происходит, Это связано с тем, что в основном время такта определяет время умножения.

Заявляемое устройство может реализовать и операцию умножения двух комплексных чисел (такую же, как и прототип), при этом третие и четвертые компоненты исходных векторов равны О).

Одним из аналогов предлагаемого устройства является серийная микроЭВМ МС

1212, которая программным способом может реализовать рассмотренную выше операцию умножения. Для такой реализации необходимо последовательно выполнить 16 операций умножения и 12 операций сложения чисел с фиксированной запятой. Так как операция умножения выполняется за 24,5 мкс, а операция суммирования — за 1,7 мкс, то время выполнения операции умножения двух кватернионов равно 412 мкс. Таким образом, выигрыш в быстродействии более чем в 400 раз. Необходимо отметить, что экономический эффект от применения данного устройства зависит не только от быстродействия, но и от характера решаемых задач, а именно от частоты появления таких операций и периодичности обработки, 1718213

10

30

40

55

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

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

2. Устройство по п. 1, о т л и ч а ю щ е ес я тем, что блок управления содержит элемент ИЛИ, элемент ИЛИ вЂ” НЕ, счетчик, два триггера, элемент И вЂ” ИЛИ вЂ” НЕ и Четыре элемента НЕ, при этом вход синхронизации блока соединен с первым входом элемента

ИЛИ, второй вход которого соединен с входом запуска блока, вход сброса которого соединен с установочным входом счетчика, первым и вторым входами элемента И—

ИЛИ вЂ” HE и входом первого элемента НЕ, выход которого соединен с установочным входом первого триггера, синхровход которого соединен с выходом элемента ИЛИ, первым входом элемента ИЛИ вЂ” НЕ и входом второго элемента НЕ, а инверсный выход— с вторым входом элемента ИЛИ вЂ” НЕ, выход которого соединен с шестым выходом блока и счетным входом счетчика, первый выход которого соединен с вторым выходом блока, входом третьего элемента НЕ и третьим входом элемента И-ИЛИ-НЕ, выход которого соединен с установочным входом второго триггера, синхровход которого соединен с выходом второго элемента НЕ, а выход — с первым выходом блока, третий выход которого соединен с вторым выходом счетчика, входом четвертого элемента НЕ и четвертым входом элемента И вЂ” ИЛИ вЂ” НЕ, а четвертый и пятый выходы блока соединены соответственно с выходами третьего и четвертого элементов Н Е.

1718213

Щ/г2

Щр.5

Составитель И,Дражан

Редактор Т.Юрчикова,Техред М.Моргентал Корректор М,Пожо

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

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

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

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