УСТРОЙСТВО НОРМИРОВКИ ВЕКТОРА
VECTOR NORMALISING APPARATUS

Изобретение относится к вычислительной (процессорной) технике и может быть использовано:
1) в высокопроизводительных вычислительных системах,
2) в персональных компьютерах в качестве средства повышения их производительности, реализуемого как подсхема в составе арифметического процессора или же в составе отдельного устройства (спецпроцессора).
а
a
а
а
а
а
1
n1
Высокопроизводительные вычислительные системы имеют в своем составе n умножителей, которые предназначены прежде всего для быстрого выполнения операции умножения компонент n-мерного вектора на произвольное число, поэтому эту совокупность умножителей называют векторным умножителем [1]. На первый вход i-го умножителя подается i-я компонента вектора x (i=1, n), на второй вход каждого умножителя подается произвольное число , на выходе векторного умножителя получают вектор y=x, причем вычисления на всех умножителях производятся параллельно (одновременно). На векторном умножителе можно выполнять и операцию векторного деления. Для этого все умножители переводятся в режим деления, на первый вход i-го умножителя подается i-я компонента вектора x, на второй вход каждого умножителя подается произвольное число b, на выходе векторного умножителя получают вектор y=[x/b…x/b]. Однако операция деления на умножителе выполняется медленнее, чем умножение на порядок числа m, где m - число разрядов, отводимых под мантиссу машинных чисел. В математике умножение вектора x на произвольное число  называется нормировкой вектора. В вычислительной математике операция нормировки вектора выполняется очень часто (является так называемой базовой операцией), при этом, к сожалению, обычно известен не нормирующий множитель , а число b, связанное с  равенством =1/b, поэтому в этом случае чтобы выполнить нормировку вектора, приходиться переводить векторный умножитель в режим деления. Известно другое устройство (Cordic) [2], в котором осуществляется нормировка двумерного вектора. Это устройство предназначено для осуществления поворота двумерного вектора. Устройство Cordic реализует два этапа вычислений: 1) этап псевдовращений и 2) этап нормировки. На первом этапе выполняются вычисления по формулам:
m-1
m-1
а
Реализация последних формул выполняется в блоке псевдовращений. Второй этап осуществляет нормировку вектора [x, y] с целью устранения растяжения исходного вектора [x, y], обусловленного этапом псевдовращений. Коэффициент растяжения  определяется формулой
Вычисления второго этапа состоят в следующем
а
а
m-1
m-1
Они обусловлены представлением инверсии числа а в виде произведения  Такое представление является простой задачей, так как число  фиксировано. Как мы видим, в устройстве Cordic при осуществлении нормировки вектора удалось избежать трудоемкой операции деления компонент вектора [x, y] на число . Технически формулы (2) реализуются в блоках нормировки, каждый из которых представляет цепочку пар (регистр сдвига, вычитатель), причем выход вычитателя i-й пары соединен с первым входом вычитателя i+1-й пары, а также с входом регистра сдвига i+1-й пары, кроме того, выход регистра сдвига i+1-й пары соединен со вторым входом вычитателя i+1-й пары. Таким образом, устройство Cordic состоит из трех блоков: блока псевдовращений и двух блоков нормировки, причем первый и второй выходы блока псевдовращений соединены соответственно с входами первого и второго блоков нормировки. На вход устройства подается вектор [x, y], на выходе получают вектор [u, ν], компоненты которого связаны с вектором [x, y] соотношениями (1) и (2). Другие устройства, в которых реализуется операция нормировки вектора, а также специализированные устройства нормировки вектора автору неизвестны.
Наиболее близким по технической сущности к заявляемому изобретению является блок нормировки, входящий в состав устройства вращения плоскости (Cordic). Недостатком этого блока является узость решаемой им задачи: 1) размерность нормируемого вектора фиксирована и равна двум, 2) делитель является фиксированным числом. С другой стороны, осуществление деления компонент вектора на умножителях дорого и недостаточно быстро (значительно медленнее умножения).
Приведенные выше характеристики аналогов и определяют цель изобретения: создание специализированного высокопроизводительного устройства нормировки n-мерного вектора, в котором вычисления выполнялись бы по формулам, структура которых указана в (2), при этом делитель был бы произвольным числом.
а
a
a
a
a
а
1
i
1
n
1
n
Поставленная цель достигается включением в состав заявляемого устройства специально разработанного блока инверсии числа. На его вход поступает делитель . Этот блок реализует вычисления по формулам: =,  i=1, [m/2], где [m/2] - целая часть числа m/2, σ∈{-1, 0, 1}. Кроме этого блока в состав устройства входят n блоков нормировки. На входы блоков нормировки поступают компоненты вектора x=[x…x]. Блоки нормировки реализуют формулы: , , i=1, [m/2], , j=1, n. На выходе устройства нормировки получают вектор u=[x/…x/]. Блок инверсии числа и блоки нормировки представляют собой цепочки последовательно соединенных каскадов. Каждый каскад блока инверсии (кроме последнего) содержит схему формирования кода сдвига, схему сдвига, схему формирования кода установления режима работы сумматора-вычитателя и сумматор-вычитатель. Внутрикаскадные соединения: выход схемы формирования кода сдвига соединен со вторым входом схемы сдвига, выход схемы сдвига соединен со вторым входом сумматора-вычитателя, выход схемы формирования кода установки режима работы сумматора-вычитателя соединен с входом установки режима работы сумматора-вычитателя. Межкаскадные соединения: первый вход сумматора-вычитателя, вход схемы формирования кода сдвига, первый вход схемы сдвига и вход схемы формирования кода установки режима работы сумматора-вычитателя i+1-го каскада соединены с выходом сумматора-вычитателя i-го каскада. На первый вход сумматора-вычитателя, вход схемы формирования кода сдвига, первый вход схемы сдвига и вход схемы формирования кода установки режима работы сумматора-вычитателя 1-го каскада подается число . Последний каскад (его номер [m/2]) содержит схему формирования кода сдвига и схему формирования кода установления режима работы. Входы этих схем соединены с выходом сумматора-вычитателя предпоследнего каскада. Каждый каскад блока нормировки имеет схему сдвига и сумматор-вычитатель. Внутрикаскадные соединения: выход схемы сдвига соединен со вторым входом сумматора-вычитателя. Межкаскадные соединения: первый вход сумматора-вычитателя и первый вход схемы сдвига i+1-го каскада соединены с выходом сумматора-вычитателя i-го каскада. Наконец, межблочные соединения: все блоки нормировки соединены с блоком инверсии, причем выход схемы формирования кода сдвига i-го каскада блока инверсии соединен со вторым входом схемы сдвига i-го каскада каждого блока нормировки, а выход схемы формирования кода установления режима работы сумматора-вычитателя i-го каскада блока инверсии соединен с входом установки режима работы сумматора-вычитателя i-го каскада каждого блока нормировки.
Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается как составом, так и способом соединения вычислительных элементов.
Таким образом, заявляемое устройство соответствует критерию «новизна».
Сравнение заявляемого технического решения не только с прототипом, но и с другими техническими решениями позволяет сделать вывод о соответствии заявляемого технического решения критерию «существенные отличия».
Изобретение поясняется структурной схемой, изображенной на рис.1.
Устройство нормировки вектора содержит блок инверсии и n блоков нормировки. Блок инверсии представляет собой цепочку из [m/2] каскадов, каждый из которых, за исключением последнего, содержит схему формирования кода сдвига 1, схему сдвига 2, схему формирования кода установления режима работы сумматора-вычитателя 3 и сумматор-вычитатель 4, соединенных как показано на рис.1. Последний каскад содержит схему формирования кода сдвига 1 и схему формирования кода установления режима работы сумматора-вычитателя 3. Каждый блок нормировки также представляет собой цепочку из m/2 каскадов, каждый из которых содержит схему сдвига 2 и сумматор-вычитатель 4 (см. рис.1).
1
n
1…
n
i
i
а
Устройство спроектировано для 32-разрядных чисел, представленных в формате с плавающей запятой (24 разряда отведено под мантиссу и 8 - под порядок). На вход заявляемого устройства подаются число а и компоненты вектора x=(x…x), где n≥2. На выход устройства подаются компоненты вектора u=(uu), определяемые соотношениями u=x/.
Для обеспечения точности выходных величин промежуточные вычисления осуществлялись на (m+r)-разрядных сумматорах, где r - число дополнительных младших разрядов, выделяемых под мантиссу. При r=5 погрешность вычисления выходных величин не превышает цены их младшего разряда.
Для обеспечения сходимость процесса вычислений в состав каждого блока нормировки входит всего лишь [m/2] сумматоров. Всего же в состав устройства входит  сумматоров.
При n=2 устройство было аппаратно реализовано на программируемой логической интегральной схеме (ПЛИС) "EP1K50FC484-1" семейства АСЕХ1K производства фирмы "Altera".
а
2
Деление компонент вектора x на число  можно произвести и на устройстве, состоящем из n умножителей, каждый из которых содержит m m-разрядных сумматоров. Таким образом, цена такого устройства будет определяться числом nm (схемы сравнения не учитываются). Цена заявляемого устройства определяется числом (n+1)(m+r)[m/2]. Сопоставляя эти числа, мы видим, что заявляемое устройство приблизительно в 2 раза дешевле устройства, выполняемого на умножителях.
Сравним быстродействие этих устройств.
а
Алгоритм деления числа x на число  состоит в следующем:
1. ,
2. ,
3.
4. .
cp
п
c
cp
п
cp
п
c
2
Введем обозначения: t - время задержки сигнала элементарной ячейкой сравнения, t - время задержки сигнала переноса элементарного сумматора, t - время задержки сигнала суммы элементарного сумматора. На i-ом шаге алгоритма деления одного числа на другое происходит задержка сигнала, равная m(t+t). Так как алгоритм состоит из m шагов, то время выполнения операции деления оценится величиной m(t+t). Считая время выполнения пункта 2 приближенно равным времени выполнения пункта 3, мы можем время выполнения операции деления на прототипе охарактеризовать числом  (задержка сигнала t не учитывается, так как осуществляется всего m суммирований, что в m меньше чем число переносов).
а
З
Определить формулой время срабатывания заявляемого устройства затруднительно, так как разным  могут соответствовать разные последовательности сдвигов, поэтому мы представим верхнюю грань определяемой величины. Установлено, что время срабатывания заявляемого устройства Т (верхняя грань) определяется соотношениями:
1
i
i-1
N=0, N=N+2(i-1), i=2, [m/2],
пp
п
з
п
с
c
п
з
п
При m=24 и r=5 T=1152t, Т=151t+12t. Учитывая, что t≈2t, мы можем записать Т≈175t. Отсюда следует, что  Таким образом, мы видим, что в данном случае (m=24 и r=5) заявляемое устройство по быстродействию более чем в 7.6 раза превосходит устройство, выполненное на умножителях.
Источники информации
1. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991.
2. Сверхбольшие интегральные схемы и современная обработка сигналов. Под ред. С. Гуна, Х. Уайтхауса, Т. Кайлата. М.: Радио и связь, 1989, стр.269-272.