Jump to content

Многомерный DSP с ускорением графического процессора

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

Современные вычисления общего назначения на графических процессорах (GPGPU) обладают превосходной производительностью при векторных операциях и числовых манипуляциях благодаря высокой степени параллельных вычислений. Обработка цифровых сигналов, особенно многомерных сигналов, часто включает в себя серию векторных операций над огромным количеством независимых выборок данных. GPGPU в настоящее время широко используются для ускорения многомерной цифровой обработки сигналов, например, при обработке изображений , видеокодеках , анализе радиолокационных сигналов , обработке гидролокационных сигналов и т. д. ультразвуковое сканирование . Концептуально GPGPU значительно снижают сложность вычислений по сравнению с центральными процессорами (ЦП), процессорами цифровых сигналов (DSP) или другими FPGA ускорителями .

Мотивация

[ редактировать ]

Обработка многомерных сигналов является распространенной проблемой в научных исследованиях и/или инженерных вычислениях. Обычно сложность вычислений задачи DSP растет экспоненциально с увеличением количества измерений. Несмотря на это, из-за высокой сложности времени и хранения чрезвычайно сложно обрабатывать многомерные сигналы в режиме реального времени. множество быстрых алгоритмов (например, БПФ Хотя для одномерных задач ЦОС было предложено ), они все еще недостаточно эффективны для адаптации к задачам ЦОС большой размерности. Поэтому до сих пор трудно получить желаемые результаты вычислений с помощью цифровых сигнальных процессоров. Следовательно, для ускорения многомерных вычислений DSP необходимы более совершенные алгоритмы и аппаратная архитектура.

Существующие подходы

[ редактировать ]

На практике для ускорения многомерной DSP в последние десятилетия были предложены и разработаны некоторые общие подходы.

Более низкая частота дискретизации

[ редактировать ]

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

Цифровые сигнальные процессоры

[ редактировать ]

Цифровые сигнальные процессоры предназначены специально для обработки векторных операций. Они широко использовались в вычислениях DSP на протяжении десятилетий. Однако большинство процессоров цифровых сигналов способны выполнять лишь несколько операций параллельно. Такого рода конструкции достаточно для ускорения обработки звука (одномерные сигналы) и обработки изображений (двумерные сигналы). Однако при большом количестве выборок данных многомерных сигналов это все еще недостаточно мощно для получения результатов вычислений в режиме реального времени.

Суперкомпьютерная помощь

[ редактировать ]

Чтобы ускорить многомерные вычисления DSP, использование выделенных суперкомпьютеров или кластерных компьютеров в некоторых случаях требуется , например, для прогнозирования погоды и военных радаров. Тем не менее, использование суперкомпьютеров, предназначенных просто для выполнения операций DSP, требует значительных денежных затрат и энергопотребления. Кроме того, он непрактичен и подходит для всех многомерных приложений DSP.

ускорение графического процессора

[ редактировать ]

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

Вычисления GPGPU

[ редактировать ]
Рисунок, иллюстрирующий блок SIMD/векторных вычислений в GPGPU.
Модель вычислений GPGPU/SIMD

Современные конструкции графических процессоров в основном основаны на парадигме вычислений SIMD (одна инструкция и несколько данных). [ 2 ] [ 3 ] Этот тип графических устройств называется так называемыми графическими процессорами общего назначения (GPGPU) .

GPGPU могут выполнять операции с несколькими независимыми данными одновременно со своими векторными или функциональными блоками SIMD. Современный GPGPU может создавать тысячи одновременных потоков и обрабатывать все потоки в пакетном режиме. Благодаря такой природе GPGPU можно легко использовать в качестве ускорителей DSP, в то время как многие проблемы DSP можно решить с помощью алгоритмов «разделяй и властвуй» . Крупномасштабную и сложную задачу DSP можно разделить на группу небольших числовых задач и обрабатывать их целиком за один раз, что позволяет значительно снизить общую временную сложность. Например, умножение двух матриц M × M может обрабатываться параллельными потоками M × M на устройстве GPGPU без какой-либо зависимости от выходных данных. Поэтому теоретически за счет ускорения GPGPU мы можем получить ускорение до M × M по сравнению с традиционным ЦП или процессором цифровых сигналов.

Языки программирования графических процессоров

[ редактировать ]

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

CUDA — это стандартный интерфейс для программирования графических процессоров NVIDIA . NVIDIA также предоставляет множество библиотек CUDA для поддержки ускорения DSP на устройствах NVIDIA с графическим процессором. [ 4 ]

OpenCL — это промышленный стандарт, который первоначально был предложен Apple Inc. , а сейчас поддерживается и развивается Khronos Group . [ 5 ] OpenCL предоставляет C++, подобные API-интерфейсы, для универсального программирования различных устройств, включая GPGPU.

Иллюстрация потока выполнения программы/ядра OpenCL
Порядок выполнения программы OpenCL

На следующем рисунке показан поток выполнения запуска программы OpenCL на устройстве графического процессора. ЦП сначала обнаруживает устройства OpenCL (в данном случае графический процессор), а затем вызывает JIT-компилятор для перевода исходного кода OpenCL в целевой двоичный файл. Затем ЦП отправляет данные в графический процессор для выполнения вычислений. Когда графический процессор обрабатывает данные, центральный процессор может обрабатывать свои собственные задачи.

C++ AMP — это модель программирования, предложенная Microsoft . C++ AMP — это библиотека на основе C++, предназначенная для программирования SIMD-процессоров. [ 6 ]

OpenACC — это стандарт программирования для параллельных вычислений, разработанный Cray , CAPS, NVIDIA и PGI. [ 7 ] OpenAcc ориентирован на программирование для гетерогенных систем ЦП и ГП с расширениями C , C++ и Fortran .

Примеры программирования графического процессора для многомерного DSP

[ редактировать ]

m × m умножение матрицы

[ редактировать ]

Предположим, что A и B — две матрицы размера m × m , и мы хотели бы вычислить C = A × B .

Для вычисления каждого элемента в C требуется m умножений и ( m 1 ) сложений. Следовательно, при реализации ЦП временная сложность выполнения этого вычисления равна Θ(n 3 ) в следующем примере C. Однако мы знаем, что элементы в C независимы друг от друга. Следовательно, вычисления могут быть полностью распараллелены процессорами SIMD, такими как устройства GPGPU. При реализации GPGPU временная сложность значительно снижается до Θ(n) за счет развертывания цикла for, как показано в следующем примере OpenCL .

// MxM matrix multiplication in C
void matrixMul(
    float *A,  // input matrix A
    float *B,  // input matrix B
    float *C,  // output matrix C
    int size)  // size of the matrices
{
    // N x N x N iterations
    for (int row = 0; row < size; row++) {
        for (int col = 0; col < size; col++) {
            int id = row * size + col;
            float sum = 0.0;

            for (int m = 0; m < size; m++) {
                sum += (A[row * size + m] * B[m * size + col]);
            }

            C[id] = sum;
        }
    }
}
// MxM matrix multiplication in OpenCL
__kernel void matrixMul(
    __global float *A,  // input matrix A
    __global float *B,  // input matrix B
    __global float *C,  // output matrix C
    __global int size)  // size of the matrices
{
    size_t id = get_global_id(0);   // each thread works on an element
    size_t row = id / size;
    size_t col = id % size;
    float sum = 0.0;

    // N iterations
    for (int m = 0; m < size; m++) {
        sum += (A[row * size + m] * B[m * size + col]);
    }

    C[id] = sum;
}

Многомерная свертка

[ редактировать ]

Свертка — часто используемая операция в DSP. Чтобы вычислить двумерную свертку двух сигналов m × m , требуется m 2 умножения и сложения m × ( m 1 ) для выходного элемента. То есть общая временная сложность равна Θ(n 4 ) для всего выходного сигнала . Как показывает следующий пример OpenCL, при ускорении GPGPU общее время вычислений эффективно уменьшается до Θ(n 2 ), поскольку все выходные элементы не зависят от данных.

Двумерное уравнение свертки:

// 2-D convolution implementation in OpenCL
__kernel void convolution(
    __global float *x,  // input signal x
    __global float *h,  // filter h
    __global float *y,  // output signal y
    __global int size)  // size of ROS of the input signal and filter
{
    size_t id = get_global_id(0);   // each thread works on an element
    size_t row = size + size - 1;   // number of rows of the output signal
    size_t col = size + size - 1;   // number of columns of the output signal
    size_t n1 = id / row;
    size_t n2 = id % col;
    float sum = 0.0;

    // N x N iterations
    for (int k1 = 0; k1 < size; k1++) {
        for (int k2 = 0; k2 < size; k2++) {
            sum += (x[k1 * row + k2] * h[(n1 * row - k1) + (n2 - k2)]);
        }
    }

    C[id] = sum;
}

Обратите внимание: хотя показанный выше пример представляет собой двумерную свертку, аналогичный подход можно применить для системы более высокого измерения. В целом, для свертки SD реализация GPGPU имеет временную сложность Θ(n с ) , тогда как реализация ЦП имеет временную сложность Θ(n 2 с ) .

Уравнение свертки МД:

Многомерное дискретное преобразование Фурье (MD DTFT)

[ редактировать ]

Помимо свертки, преобразование Фурье с дискретным временем (DTFT) в системном анализе часто используется .

На практике, чтобы реализовать MD DTFT, мы можем выполнить M раз 1-D DFTF и транспонировать матрицу по каждому измерению. С помощью одномерной операции DTFT GPGPU может концептуально снизить сложность с Θ(n 2 ) до Θ(n ), как показано в следующем примере реализации OpenCL . То есть MD DTFT сложность GPGPU может быть вычислена на графическом процессоре со сложностью Θ(n 2 ). Хотя некоторые графические процессоры также оснащены внутренними аппаратными ускорителями БПФ, эту реализацию также можно оптимизировать, вызывая API-интерфейсы БПФ или библиотеки, предоставляемые производителем графического процессора. [ 8 ]

// DTFT in OpenCL
__kernel void convolution(
    __global float *x_re,
    __global float *x_im,
    __global float *X_re,
    __global float *X_im,
    __global int size)
{
    size_t id = get_global_id(0);   // each thread works on an element
    X_re[id] = 0.0;
    X_im[id] = 0.0;

    for (int i = 0; i < size; i++) {
        X_re += (x_re[id] * cos(2 * 3.1415 * id / size) - x_im[id] * sin(2 * 3.1415 * id / size));
        X_im += (x_re[id] * sin(2 * 3.1415 * id / size) + x_im[id] * cos(2 * 3.1415 * id / size));
    }
}

Реальные приложения

[ редактировать ]

Конструкция цифрового фильтра

[ редактировать ]

Разработка многомерного цифрового фильтра является большой проблемой, особенно БИХ- фильтров. Обычно для решения разностных уравнений и получения набора приближенных решений используются компьютеры. В то время как вычисления GPGPU становятся популярными, было предложено несколько адаптивных алгоритмов для разработки многомерных КИХ- и/или БИХ- фильтров с помощью GPGPU. [ 9 ] [ 10 ] [ 11 ]

Реконструкция и анализ радиолокационного сигнала

[ редактировать ]

Радиолокационным системам обычно необходимо реконструировать многочисленные выборки трехмерных или четырехмерных данных в режиме реального времени. Традиционно, особенно в военной сфере, для этого необходима поддержка суперкомпьютеров. В настоящее время GPGPU также используются для замены суперкомпьютеров для обработки радиолокационных сигналов. Например, для обработки сигналов радара с синтезированной апертурой (SAR) обычно используются многомерные вычисления БПФ . [ 12 ] [ 13 ] [ 14 ] GPGPU можно использовать для быстрого выполнения FFT и/или iFFT в приложениях такого типа.

Беспилотные автомобили

[ редактировать ]

Многие беспилотные автомобили применяют методы распознавания трехмерных изображений для автоматического управления транспортными средствами. Очевидно, что для того, чтобы приспособиться к быстро меняющейся внешней среде, процессы распознавания и принятия решений должны осуществляться в режиме реального времени. GPGPU — отличные устройства для достижения цели. [ 15 ]

Обработка медицинских изображений

[ редактировать ]

Чтобы поставить точный диагноз, 2-D или 3-D медицинские сигналы, такие как ультразвук , рентген , МРТ и КТ , часто требуют очень высокой частоты дискретизации и разрешения изображения для восстановления изображений. Было показано, что, применяя превосходную вычислительную мощность GPGPU, мы можем получать медицинские изображения более высокого качества. [ 16 ] [ 17 ]

  1. ^ Чу, Сло-Ли; Сяо, Чи-Че (01 сентября 2010 г.). «OpenCL: сделайте возможным повсеместное распространение суперкомпьютеров». 2010 12-я Международная конференция IEEE по высокопроизводительным вычислениям и коммуникациям (HPCC) . стр. 556–561. дои : 10.1109/HPCC.2010.56 . ISBN  978-1-4244-8335-8 . S2CID   14586211 .
  2. ^ Линдхольм, Э.; Николлс, Дж.; Оберман, С.; Монтрим, Дж. (01 марта 2008 г.). «NVIDIA Tesla: унифицированная графическая и вычислительная архитектура» . IEEE микро . 28 (2): 39–55. дои : 10.1109/MM.2008.31 . ISSN   0272-1732 . S2CID   2793450 .
  3. ^ Ким, Хесон ; Вудук, Ричард; Багсорхи, Сара; Чой, Джи; Хву, Вэнь-Мэй В. (2012). Хилл, Марк Д. (ред.). Анализ производительности и настройка графических процессоров общего назначения (GPGPU) . Издательство Морган и Клейпул. дои : 10.2200/S00451ED1V01Y201209CAC020 . ISBN  978-1-60845-954-4 .
  4. ^ «Платформа параллельного программирования и вычислений | CUDA | NVIDIA | NVIDIA» . www.nvidia.com . Архивировано из оригинала 6 января 2014 г. Проверено 5 ноября 2015 г.
  5. ^ «OpenCL — открытый стандарт параллельного программирования гетерогенных систем» . www.khronos.org . 21 июля 2013 года . Проверено 5 ноября 2015 г.
  6. ^ «C++ AMP (C++ ускоренный массовый параллелизм)» . msdn.microsoft.com . Проверено 5 ноября 2015 г.
  7. ^ «Главная страница OpenACC | www.openacc.org» . www.openacc.org . Проверено 5 ноября 2015 г.
  8. ^ «Пример оптимизации OpenCL™ Быстрое преобразование Фурье – Часть II – AMD» . АМД . Проверено 5 ноября 2015 г.
  9. ^ Нехаб, Диего; Максимо, Андре; Лима, Родольфо С.; Хоппе, Хьюз (1 января 2011 г.). «Рекурсивная фильтрация с эффективностью использования графического процессора и таблицы суммированных площадей». Материалы азиатской конференции SIGGRAPH 2011 года . СА '11. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 176:1–176:12. дои : 10.1145/2024156.2024210 . ISBN  978-1-4503-0807-6 . S2CID   3014398 .
  10. ^ Фарр, Мэтт; Фернандо, Рандима (2005). GPU Gems 2: методы программирования для высокопроизводительной графики и вычислений общего назначения . Пирсон Эддисон Уэсли. ISBN  978-0-321-33559-3 .
  11. ^ Хву, Вэнь-мэй В. (2011). GPU Computing Gems Emerald Edition . Morgan Kaufmann Publishers Inc. Сан-Франциско, Калифорния, США: ISBN  978-0-12-385963-1 .
  12. ^ Клементе, К.; Ди Бишелье, М.; Ди Санто, М.; Ранальдо, Н.; Спинелли, М. (1 октября 2009 г.). «Обработка данных синтетического апертурного радара с помощью GPGPU». Семинар IEEE 2009 г. по системам обработки сигналов . стр. 309–314. дои : 10.1109/SIPS.2009.5336272 . ISBN  978-1-4244-4335-2 . S2CID   18932083 .
  13. ^ Лю, Бин; Ван, Кайчжи; Лю, Синчжао; Ю, Вэньсянь (01 октября 2009 г.). «Эффективный процессор SAR на основе графического процессора через CUDA». 2009 2-й Международный конгресс по обработке изображений и сигналов . пп. 1–5. дои : 10.1109/CISP.2009.5304418 . ISBN  978-1-4244-4129-7 . S2CID   18801932 .
  14. ^ Монсурро, П.; Трифилетти, А.; Ланнутти, Ф. (1 июня 2014 г.). «Реализация радарных алгоритмов на оборудовании CUDA». 2014 Материалы 21-й Международной конференции «Смешанное проектирование интегральных схем и систем» (MIXDES) . стр. 455–458. дои : 10.1109/MIXDES.2014.6872240 . ISBN  978-83-63578-05-3 . S2CID   16482715 .
  15. ^ Фанг, Цзяньбинь; Варбанеску, Алабама; Шен, Цзе; Сипс, Х.; Сайгили, Г.; ван дер Маатен, Л. (1 декабря 2012 г.). «Ускорение агрегирования затрат для стереосогласования в реальном времени». 2012 18-я Международная конференция IEEE по параллельным и распределенным системам . стр. 472–481. дои : 10.1109/ICPADS.2012.71 . ISBN  978-1-4673-4565-1 . S2CID   14737126 .
  16. ^ «Медицинская визуализация|NVIDIA» . www.nvidia.com . Проверено 7 ноября 2015 г.
  17. ^ Хэн, Ян; Гу, Лисюй (01 января 2005 г.). «Объемный рендеринг на основе графического процессора для визуализации медицинских изображений». 2005 27-я ежегодная конференция IEEE Engineering в медицине и биологии . Том. 5. С. 5145–5148. дои : 10.1109/IEMBS.2005.1615635 . ISBN  978-0-7803-8741-6 . ПМИД   17281405 . S2CID   17401263 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 7674647773e5fbd0e23bf21656d0a01f__1721507460
URL1:https://arc.ask3.ru/arc/aa/76/1f/7674647773e5fbd0e23bf21656d0a01f.html
Заголовок, (Title) документа по адресу, URL1:
Multidimensional DSP with GPU acceleration - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)