Устройство нормировки вектора



Устройство нормировки вектора

 


Владельцы патента RU 2449354:

Бабенко Виктор Николаевич (RU)

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

1. ,

2. ,

3.

4. .

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

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

N1=0, Ni=Ni-1+2(i-1), i=2, [m/2],

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

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

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

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

Устройство нормировки 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.



 

Похожие патенты:

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

Изобретение относится к области вычислительной техники и предназначено для моделирования задач при проектировании вычислительных систем (ВС). .

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

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

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

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

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

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

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

Изобретение относится к автоматике и вычислительной технике

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

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

Изобретение относится к области управления и может быть использовано для оптимизации эксплуатационных расходов при работе автоматизированных систем управления различными реальными процессами, систем поддержки принятия решений, моделирования реальных объектов

Изобретение относится к устройствам принятия решения в условиях неопределенности. Техническим результатом является расширение функциональных возможностей устройства за счет обеспечения возможности ранжирования вариантов принятия решения. Устройство содержит сумматоры 11i (i=1,…,m), первый элемент задержки 12, второй элемент задержки 13, третий элемент задержки 14, блок выбора максимального кода (БВМК) 15, матрицу из m*n блоков умножения 8ij, стековую память 16, входные триггеры 10i, (i=1,…,m), элемент И 9ij (i=1,…,m, j=1,…,n), блоки умножения 8ij (i=1,…,m, j=1,…,n), вторые регистры 6j (j=1,…,n), третьи регистры 7ij (i=1,…,m, j=1,…,n), первый элемент И 2, элемент задержки 12, второй элемент задержки 13, сумматоры 11i (i=1,…,m), элементы И 9ij (i=1,…,m, j=1,…,n), стековую память 16, элемент И 17, схему сравнения 5. 1 ил.

Изобретение относится к вычислительной технике и может быть использовано для создания арифметического ускорителя для решения больших систем линейных уравнений. Техническим результатом является уменьшение числа арифметических операций. Способ содержит этапы, на которых: производят доступ к блоку общей памяти одного или более третичных или четвертичных процессоров, выбранных из произвольного множества разнородных процессоров, выявляют свободный первичный процессор, разделяют промежуточный результат на группы, производят индексирование и записывают значения промежуточного результата в каждой группе в блок общей памяти, выявляют свободный третичный процессор и производят ранжирование индексов и по одному из трех последовательных индексов, выбранных из множества индексов, производят быстрое дискретное преобразование Фурье, записывают результаты преобразования в блок общей памяти, выявляют свободный четвертичный процессор, рассматривают значения элементов матрицы для первого индекса последовательно, производят быстрые дискретные преобразования Фурье по двум другим индексам, умножают почленно получившиеся значения по этим двум индексам на Фурье преобразования теплицевой матрицы для этих индексов, производят обратное быстрое дискретное преобразование Фурье по этим двум индексам, результаты преобразований записывают в локальную память четвертичного процессора, производят обратное быстрое дискретное преобразование Фурье по первому индексу, записывают результат в общую память. 1 ил.
Изобретение относится к вычислительной технике. Технический результат заключается в упрощении определения пределов защиты при помощи полной экстраполяции пределов защиты. Способ для определения для будущего момента времени пределов защиты, связанных с навигационными параметрами носителя, в котором оценивают навигационные параметры носителя в настоящий момент времени, формируют статистическую модель ошибок оценки навигационных параметров носителя в настоящий момент времени в виде ковариационной матрицы, экстраполируют статистическую модель ошибок оценки на будущий момент времени, вычисляют предел защиты для будущего момента времени на основе экстраполированной статистической модели, причем для экстраполяции статистической модели ошибок оценки используют применение постоянной положительной матрицы перехода к вектору среднеквадратичных отклонений, сформированному из квадратных корней диагональных элементов ковариационной матрицы с целью распространения на будущий момент времени среднеквадратичных отклонений навигационных параметров, полученных в настоящий момент времени, при этом указанное распространение является независимым от предыдущей динамики носителя. 2 н. и 9 з.п. ф-лы, 5 ил.

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

Изобретение относится к методам цифровых вычислений, предназначенных для специфических функций, а именно к комплексным математическим операциям для матричных или векторных вычислений. Согласно способу сигналы, поступающие с выходов N-элементной антенной системы, оцифровывают в N аналого-цифровых преобразователях, обрабатывают в цифровом вычислителе, где формируют ковариационную матрицу, раскладывают ее на собственные векторы и собственные значения. Далее N сигналов, свободных от J мощных некоррелированных помех, при условии N>J, передают на входы устройств, предназначенных для извлечения полезной информации. Технический результат заключается в удалении помеховой составляющей из каждого приемного канала используемого устройства, обеспечивая сохранение полезной информации в каждом канале. 3 ил.
Наверх