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

Авторы патента:

G06F17/16 - матричные или векторные вычисления

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

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

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

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

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. ,

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-мерного вектора, содержащее блок инверсии делителя и 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.

Способ передачи-приема сигнала в многопользовательской системе радиосвязи с множеством передающих и множеством приемных антенн // 2398359

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

Устройство поиска нижней оценки размещения в полносвязных матричных системах при однонаправленной передаче информации // 2398270

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

Устройство вычисления сумм произведений // 2306595

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

Устройство для сортировки двумерного массива данных // 2279122

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

Устройство для сортировки двумерного массива данных (варианты) // 2252447

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

Способ визуального отображения и анализа аномалий многомерного объекта или процесса // 2200345

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

Способ спектрального анализа квазипериодических сигналов // 2187838

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

Устройство для вычисления собственных значений матриц // 2168760

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

Нейропроцессор, устройство для вычисления функций насыщения, вычислительное устройство и сумматор // 2131145

Ячейка однородной вычислительной среды и устройство для сжатия двоичных векторов на базе ячеек однородной вычислительной среды // 2450327

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

Устройство для моделирования процесса принятия решения в условиях неопределенности // 2468423

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

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

Устройство вращения вектора // 2475830

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

Способ оптимизации алгоритма управления конкретным объектом и/или процессом // 2479864

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

Устройство для моделирования процесса принятия решения в условиях неопределенности // 2534924

Изобретение относится к устройствам принятия решения в условиях неопределенности. Техническим результатом является расширение функциональных возможностей устройства за счет обеспечения возможности ранжирования вариантов принятия решения. Устройство содержит сумматоры 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 ил.

Способ организации арифметического ускорителя для решения больших систем линейных уравнений // 2547618

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

Способ и система для определения границ защиты с полной экстраполяцией на протяжении заданного временного горизонта // 2552160

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

Устройство обращения ковариационной матрицы помеховых сигналов // 2562389

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

Способ устранения пространственных помех // 2575973

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