УСТРОЙСТВО НОРМИРОВКИ ВЕКТОРА Российский патент 2013 года по МПК G06F17/16 

Изобретение относится к вычислительной (процессорной) технике и может быть использовано:

1) в высокопроизводительных вычислительных системах,

2) в системах управления быстро протекающими процессами,

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

Высокопроизводительные вычислительные системы имеют в своем составе n умножителей, которые предназначены прежде всего для быстрого выполнения операции умножения компонент n-мерного вектора на произвольное число, поэтому эту совокупность умножителей называют векторным умножителем [1]. На первый вход i-го умножителя подается i-я компонента вектора х (i=1, n), на второй вход каждого умножителя подается произвольное число a, на выходе векторного умножителя получают вектор y=ax, причем вычисления на всех умножителях производятся параллельно (одновременно). На векторном умножителе можно выполнять и операцию векторного деления. Для этого все умножители переводятся в режим деления, на первый вход i-го умножителя подается i-я компонента вектора х, на второй вход каждого умножителя подается произвольное число b, на выходе векторного умножителя получают вектор y=[x₁/b…x_n/b]. Однако операция деления на умножителе выполняется медленнее, чем умножение на порядок числа m, где m - число разрядов, отводимых под мантиссу машинных чисел. В математике умножение вектора x на произвольное число a называется нормировкой вектора. В вычислительной математике операция нормировки вектора выполняется очень часто (является так называемой базовой операцией), при этом, к сожалению, обычно известен не нормирующий множитель a, а число b, связанное с a равенством a=1/b, поэтому в этом случае, чтобы выполнить нормировку вектора, приходится переводить векторный умножитель в режим деления. С другой стороны, осуществление деления компонент вектора на умножителях дорого и недостаточно быстро (значительно медленнее умножения).

Известно устройство (Cordic) [2], в котором осуществляется нормировка двумерного вектора. Это устройство предназначено для осуществления поворота двумерного вектора. Устройство Cordic реализует два этапа вычислений: 1) этап псевдовращений и 2) этап нормировки. На первом этапе выполняются вычисления по формулам:

Реализация последних формул выполняется в блоке псевдовращений. Второй этап осуществляет нормировку вектора [x_m-1y_m-1] с целью устранения растяжения исходного вектора [x, y], обусловленного этапом псевдовращений. Коэффициент растяжения b определяется формулой . Вычисления второго этапа состоят в следующем

Они обусловлены представлением инверсии числа b в виде произведения . Такое представление является простой задачей, так как число b фиксировано. Как мы видим, в устройстве Cordic при осуществлении нормировки вектора удалось избежать выполнения двух операций: извлечения квадратного корня и деления компонент вектора [x_m-1, y_m-1] на число b. Технически формулы (2) реализуются в блоках нормировки, каждый из которых представляет цепочку пар (регистр сдвига, сумматор-вычитатель), причем выход сумматора-вычитателя i-й пары соединен с первым входом сумматора-вычитателя i+1-й пары, а также с входом регистра сдвига i+1-й пары, кроме того, выход регистра сдвига i+1-й пары соединен со вторым входом сумматора-вычитателя i+1-й пары. Таким образом, устройство Cordic состоит из трех блоков: блока псевдовращений и двух блоков нормировки, причем первый и второй выходы блока псевдовращений соединены соответственно с входами первого и второго блоков нормировки. На вход устройства подается вектор [x, y], на выходе получают вектор [u_m-1, ν_m-1], компоненты которого связаны с вектором [x, y] соотношениями (1) и (2). Недостатком описанного блока нормировки является узость решаемой им задачи: 1) размерность нормируемого вектора фиксирована и равна двум, 2) делитель является фиксированным числом.

Часто в вычислительной математике нормировка состоит в реализации формулы (базовая операция), где x - n-мерный вектор. Чтобы осуществить нормировку, определяемую последней формулой, в вычислительной практике прибегают к реализации операции извлечения квадратного корня (алгоритм Герона), а затем - к применению векторного умножителя, переводя последний в режим деления. Недостатком такого способа нормировки является предварительное применение очень медленной процедуры извлечения квадратного корня, которая осуществляется программно [3] и, предшествуя по времени операции деления компонент вектора x на делитель b , дополнительно замедляет процесс рассматриваемой нормировки.

Наиболее близким по технической сущности к заявляемому изобретению является блок нормировки, входящий в состав устройства вращения плоскости (Cordic).

Приведенные выше характеристики аналогов и определяют цель изобретения: создание специализированного высокопроизводительного устройства нормировки n-мерного вектора, в котором вычисления выполнялись бы по формулам, структура которых указана в (2), при этом число a было бы произвольным.

Поставленная цель достигается включением в состав заявляемого устройства специально разработанного блока инверсии радикала. На его вход поступает число a. Этот блок реализует вычисления по формулам: a ₁=a, , i=1 [m/2], где [m/2] - целая часть числа m/2, σ_i∈{-1,0,1}. Кроме этого блока в состав устройства входят n блоков нормировки. На входы блоков нормировки поступают компоненты вектора x=[x₁…x_n]. Блоки нормировки реализуют формулы: , i=1 [m/2], , j=1, n. На выходе устройства нормировки получают вектор . Блок инверсии радикала и блоки нормировки представляют собой цепочки последовательно соединенных каскадов. Каждый каскад блока инверсии радикала (кроме последнего) содержит схему формирования кода сдвига, схему сдвига, схему формирования кода установления режима работы сумматора-вычитателя и сдвоенный сумматор-вычитатель. Внутрикаскадные соединения: выход схемы формирования кода сдвига соединен со вторым входом схемы сдвига, выход схемы сдвига соединен со вторым входом сумматора-вычитателя, выход схемы формирования кода установки режима работы сумматора-вычитателя соединен с входом установки режима работы сумматора-вычитателя. Межкаскадные соединения: первый вход сумматора-вычитателя, вход схемы формирования кода сдвига, первый вход схемы сдвига и вход схемы формирования кода установки режима работы сумматора-вычитателя i+1-го каскада соединены с выходом сумматора-вычитателя i-го каскада. На первый вход сдвоенного сумматора-вычитателя, вход схемы формирования кода сдвига, первый вход схемы сдвига и вход схемы формирования кода установки режима работы сумматора-вычитателя 1-го каскада подается число a. Последний каскад (его номер [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).

Устройство спроектировано для 32-разрядных чисел, представленных в формате с плавающей запятой (24 разряда отведено под мантиссу и 8 - под порядок). На вход заявляемого устройства подаются число a и компоненты вектора x=(x₁…x_n), где n≥2. На выходе устройства получают компоненты вектора u=(u₁…u_n), определяемые соотношениями .

Для обеспечения точности выходных величин промежуточные вычисления осуществлялись на (m+r)-разрядных сумматорах, где r - число дополнительных младших разрядов, выделяемых под мантиссу. При r=5 погрешность вычисления выходных величин не превышает цены их младшего разряда.

Для обеспечения сходимости процесса вычислений в состав каждого блока нормировки входит всего лишь [m/2] сумматоров. Всего же в состав устройства входит сумматоров.

При n=2 устройство было аппаратно реализовано на программируемой логической интегральной схеме (ПЛИС) "EP1K50FC484-1" семейства ACEX1K производства фирмы "Altera". Технические характеристики этого устройства:

1) максимально допустимая тактовая частота - 2.78·10⁷ Гц,

2) пиковая производительность - 5.56·10⁷ операций в сек,

3) время отклика (заполнения конвейера) - 432·10^-9 сек.

Источники информации

1. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М., Мир.

2. Сверхбольшие интегральные схемы и современная обработка сигналов. Под ред. С.Гуна, X.Уайтхауса, Т.Кайлата, М., Радио и связь, 1989, стр.269-271.

3. Годунов С.К., Антонов А.Г., Кирилюк О.П., Костин В.И. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. Новосибирск, Наука, 1988.

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

Устройство нормировки n-мерного вектора, содержащее блок инверсии радикала и n блоков нормировки, причем каждый блок представляет собой цепочку из [m/2] последовательно соединенных каскадов, при этом каждый каскад блока инверсии радикала (кроме последнего) содержит схему формирования кода сдвига, схему сдвига, схему формирования кода установления режима работы сумматора-вычитателя и сдвоенный сумматор-вычитатель, а каждый каскад блока нормировки - схему сдвига и сумматор-вычитатель, при этом элементы устройства соединены следующим образом: внутрикаскадные соединения блока инверсии радикала: выход схемы формирования кода сдвига соединен со вторым входом схемы сдвига, выход схемы сдвига соединен со вторым входом сумматора-вычитателя, выход схемы формирования кода установки режима работы сумматора-вычитателя соединен с входом установки режима работы сумматора-вычитателя; межкаскадные соединения блока инверсии радикала: первый вход сумматора-вычитателя, вход схемы формирования кода сдвига, первый вход схемы сдвига и вход схемы формирования кода установки режима работы сумматора-вычитателя i+1-го каскада соединены с выходом сумматора-вычитателя i-го каскада; на первый вход сумматора-вычитателя, вход схемы формирования кода сдвига, первый вход схемы сдвига и вход схемы формирования кода установки режима работы сумматора-вычитателя l-го каскада подается число α; последний каскад (его номер [m/2]) содержит схему формирования кода сдвига и схему формирования кода установления режима работы, причем входы этих схем соединены с выходом сумматора-вычитателя предпоследнего каскада; внутрикаскадные соединения блока нормировки: выход схемы сдвига соединен со вторым входом сумматора-вычитателя; межкаскадные соединения блока нормировки: первый вход сумматора-вычитателя и первый вход схемы сдвига i+1-го каскада соединены с выходом сумматора-вычитателя i-го каскада; межблочные соединения: все блоки нормировки соединены с блоком инверсии радикала, причем выход схемы формирования кода сдвига i-го каскада блока инверсии радикала соединен со вторым входом схемы сдвига i-го каскада каждого блока нормировки, а выход схемы формирования кода установления режима работы сумматора-вычитателя i-го каскада блока инверсии радикала соединен с входом установки режима работы сумматора-вычитателя i-го каскада каждого блока нормировки; на первый вход сумматора-вычитателя и первый вход схемы сдвига 1-го каскада j-го блока нормировки (j=1, n) подается j-я компонента нормируемого вектора х, а на выходе последнего каскада j-го блока нормировки (его номер [m/2]) получают j-ю компоненту нормированного вектора u.