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

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

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

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

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

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

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

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 блоков нормировки, причем каждый блок представляет собой цепочку из [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.

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

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

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

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

Инструкция и логическая схема для выполнения операции скалярного произведения // 2421796

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

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

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

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

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

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

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

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

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

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

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

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

Устройство вращения вектора // 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 ил.

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

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

Способы для аппроксимации операции умножения гессиана на вектор в полной инверсии волнового поля // 2613216

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

Устройство оптимизации алгоритмов адаптации и стабилизации летательного аппарата операторным методом // 2620280

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