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

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

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

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

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

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

Вычисления второго этапа состоят в следующем

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

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

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

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

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

Деление компонент вектора x на число а можно произвести и на устройстве, состоящем из n умножителей, каждый из которых содержит m m-разрядных сумматоров. Таким образом, цена такого устройства будет определяться числом nm² (схемы сравнения не учитываются). Цена заявляемого устройства определяется числом (n+1)(m+r)[m/2]. Сопоставляя эти числа, мы видим, что заявляемое устройство приблизительно в 2 раза дешевле устройства, выполняемого на умножителях.

Сравним быстродействие этих устройств.

Алгоритм деления числа x на число а состоит в следующем:

1. ,

2. ,

3.

4. .

Введем обозначения: t_cp - время задержки сигнала элементарной ячейкой сравнения, t_п - время задержки сигнала переноса элементарного сумматора, t_c - время задержки сигнала суммы элементарного сумматора. На i-ом шаге алгоритма деления одного числа на другое происходит задержка сигнала, равная m(t_cp+t_п). Так как алгоритм состоит из m шагов, то время выполнения операции деления оценится величиной m²(t_cp+t_п). Считая время выполнения пункта 2 приближенно равным времени выполнения пункта 3, мы можем время выполнения операции деления на прототипе охарактеризовать числом (задержка сигнала t_c не учитывается, так как осуществляется всего m суммирований, что в m меньше чем число переносов).

Определить формулой время срабатывания заявляемого устройства затруднительно, так как разным а могут соответствовать разные последовательности сдвигов, поэтому мы представим верхнюю грань определяемой величины. Установлено, что время срабатывания заявляемого устройства Т_З (верхняя грань) определяется соотношениями:

N₁=0, N_i=N_i-1+2(i-1), i=2, [m/2],

При m=24 и r=5 T_пp=1152t_п, Т_з=151t_п+12t_с. Учитывая, что t_c≈2t_п, мы можем записать Т_з≈175t_п. Отсюда следует, что Таким образом, мы видим, что в данном случае (m=24 и r=5) заявляемое устройство по быстродействию более чем в 7.6 раза превосходит устройство, выполненное на умножителях.

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

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

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

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

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