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

Изобретение относится к вычислительной (процессорной) технике и может быть использовано:
1) в высокопроизводительных вычислительных системах,
2) в системах управления быстро протекающими процессами,
3) в персональных компьютерах в качестве средства повышения их производительности, реализуемого как подсхема в составе арифметического процессора или же в составе отдельного устройства (спецпроцессора).
a
a
a
a
a
a
1
n
Высокопроизводительные вычислительные системы имеют в своем составе n умножителей, которые предназначены прежде всего для быстрого выполнения операции умножения компонент n-мерного вектора на произвольное число, поэтому эту совокупность умножителей называют векторным умножителем [1]. На первый вход i-го умножителя подается i-я компонента вектора х (i=1, n), на второй вход каждого умножителя подается произвольное число , на выходе векторного умножителя получают вектор y=x, причем вычисления на всех умножителях производятся параллельно (одновременно). На векторном умножителе можно выполнять и операцию векторного деления. Для этого все умножители переводятся в режим деления, на первый вход i-го умножителя подается i-я компонента вектора х, на второй вход каждого умножителя подается произвольное число b, на выходе векторного умножителя получают вектор y=[x/b…x/b]. Однако операция деления на умножителе выполняется медленнее, чем умножение на порядок числа m, где m - число разрядов, отводимых под мантиссу машинных чисел. В математике умножение вектора x на произвольное число  называется нормировкой вектора. В вычислительной математике операция нормировки вектора выполняется очень часто (является так называемой базовой операцией), при этом, к сожалению, обычно известен не нормирующий множитель , а число b, связанное с  равенством =1/b, поэтому в этом случае, чтобы выполнить нормировку вектора, приходится переводить векторный умножитель в режим деления. С другой стороны, осуществление деления компонент вектора на умножителях дорого и недостаточно быстро (значительно медленнее умножения).
Известно устройство (Cordic) [2], в котором осуществляется нормировка двумерного вектора. Это устройство предназначено для осуществления поворота двумерного вектора. Устройство Cordic реализует два этапа вычислений: 1) этап псевдовращений и 2) этап нормировки. На первом этапе выполняются вычисления по формулам:
m-1
m-1
Реализация последних формул выполняется в блоке псевдовращений. Второй этап осуществляет нормировку вектора [xy] с целью устранения растяжения исходного вектора [x, y], обусловленного этапом псевдовращений. Коэффициент растяжения b определяется формулой . Вычисления второго этапа состоят в следующем
m-1
m-1
m-1
m-1
Они обусловлены представлением инверсии числа b в виде произведения . Такое представление является простой задачей, так как число b фиксировано. Как мы видим, в устройстве Cordic при осуществлении нормировки вектора удалось избежать выполнения двух операций: извлечения квадратного корня  и деления компонент вектора [x, y] на число b. Технически формулы (2) реализуются в блоках нормировки, каждый из которых представляет цепочку пар (регистр сдвига, сумматор-вычитатель), причем выход сумматора-вычитателя i-й пары соединен с первым входом сумматора-вычитателя i+1-й пары, а также с входом регистра сдвига i+1-й пары, кроме того, выход регистра сдвига i+1-й пары соединен со вторым входом сумматора-вычитателя i+1-й пары. Таким образом, устройство Cordic состоит из трех блоков: блока псевдовращений и двух блоков нормировки, причем первый и второй выходы блока псевдовращений соединены соответственно с входами первого и второго блоков нормировки. На вход устройства подается вектор [x, y], на выходе получают вектор [u, ν], компоненты которого связаны с вектором [x, y] соотношениями (1) и (2). Недостатком описанного блока нормировки является узость решаемой им задачи: 1) размерность нормируемого вектора фиксирована и равна двум, 2) делитель  является фиксированным числом.
Часто в вычислительной математике нормировка состоит в реализации формулы  (базовая операция), где x - n-мерный вектор. Чтобы осуществить нормировку, определяемую последней формулой, в вычислительной практике прибегают к реализации операции извлечения квадратного корня (алгоритм Герона), а затем - к применению векторного умножителя, переводя последний в режим деления. Недостатком такого способа нормировки является предварительное применение очень медленной процедуры извлечения квадратного корня, которая осуществляется программно [3] и, предшествуя по времени операции деления компонент вектора x на делитель b , дополнительно замедляет процесс рассматриваемой нормировки.
Наиболее близким по технической сущности к заявляемому изобретению является блок нормировки, входящий в состав устройства вращения плоскости (Cordic).
a
Приведенные выше характеристики аналогов и определяют цель изобретения: создание специализированного высокопроизводительного устройства нормировки n-мерного вектора, в котором вычисления выполнялись бы по формулам, структура которых указана в (2), при этом число  было бы произвольным.
a
a
a
a
1
i
1
n
Поставленная цель достигается включением в состав заявляемого устройства специально разработанного блока инверсии радикала. На его вход поступает число . Этот блок реализует вычисления по формулам: =, , i=1 [m/2], где [m/2] - целая часть числа m/2, σ∈{-1,0,1}. Кроме этого блока в состав устройства входят n блоков нормировки. На входы блоков нормировки поступают компоненты вектора x=[x…x]. Блоки нормировки реализуют формулы: , i=1 [m/2], , j=1, n. На выходе устройства нормировки получают вектор . Блок инверсии радикала и блоки нормировки представляют собой цепочки последовательно соединенных каскадов. Каждый каскад блока инверсии радикала (кроме последнего) содержит схему формирования кода сдвига, схему сдвига, схему формирования кода установления режима работы сумматора-вычитателя и сдвоенный сумматор-вычитатель. Внутрикаскадные соединения: выход схемы формирования кода сдвига соединен со вторым входом схемы сдвига, выход схемы сдвига соединен со вторым входом сумматора-вычитателя, выход схемы формирования кода установки режима работы сумматора-вычитателя соединен с входом установки режима работы сумматора-вычитателя. Межкаскадные соединения: первый вход сумматора-вычитателя, вход схемы формирования кода сдвига, первый вход схемы сдвига и вход схемы формирования кода установки режима работы сумматора-вычитателя 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 и сумматор-вычитатель 5 (см. рис.1).
a
1
n
1
n
Устройство спроектировано для 32-разрядных чисел, представленных в формате с плавающей запятой (24 разряда отведено под мантиссу и 8 - под порядок). На вход заявляемого устройства подаются число  и компоненты вектора x=(x…x), где n≥2. На выходе устройства получают компоненты вектора u=(u…u), определяемые соотношениями .
Для обеспечения точности выходных величин промежуточные вычисления осуществлялись на (m+r)-разрядных сумматорах, где r - число дополнительных младших разрядов, выделяемых под мантиссу. При r=5 погрешность вычисления выходных величин не превышает цены их младшего разряда.
Для обеспечения сходимости процесса вычислений в состав каждого блока нормировки входит всего лишь [m/2] сумматоров. Всего же в состав устройства входит  сумматоров.
При n=2 устройство было аппаратно реализовано на программируемой логической интегральной схеме (ПЛИС) "EP1K50FC484-1" семейства ACEX1K производства фирмы "Altera". Технические характеристики этого устройства:
7
1) максимально допустимая тактовая частота - 2.78·10 Гц,
7
2) пиковая производительность - 5.56·10 операций в сек,
-9
3) время отклика (заполнения конвейера) - 432·10 сек.
Источники информации
1. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М., Мир.
2. Сверхбольшие интегральные схемы и современная обработка сигналов. Под ред. С.Гуна, X.Уайтхауса, Т.Кайлата, М., Радио и связь, 1989, стр.269-271.
3. Годунов С.К., Антонов А.Г., Кирилюк О.П., Костин В.И. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. Новосибирск, Наука, 1988.