Справочник вопросов и ответов
QUOR - электронный справочник

Многомерный DSP с ускорением GPU - Multidimensional DSP with GPU Acceleration

Тег: Другие предметы

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

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

Содержание

  • 1 Мотивация
  • 2 Существующие подходы
    • 2.1 Более низкая частота дискретизации
    • 2.2 Цифровые сигнальные процессоры
    • 2.3 Поддержка суперкомпьютера
    • 2.4 Ускорение GPU
  • 3 Вычисления GPGPU
  • 4 языка программирования GPU
    • 4.1 CUDA
    • 4.2 OpenCL
    • 4.3 C ++ AMP
    • 4.4 OpenACC
  • 5 Примеры программирования GPU для многомерного DSP
    • 5,1 умножение матриц m × m
    • 5.2 Многомерное свертка
    • 5.3 Многомерное дискретное временное преобразование Фурье (MD DTFT)
  • 6 Реальные приложения
    • 6.1 Разработка цифрового фильтра
    • 6.2 Восстановление и анализ радиолокационного сигнала
    • 6.3 Беспилотные автомобили
    • 6.4 Медицинское изображение обработка
  • 7 Ссылки

Мотивация

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

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

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

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

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

Процессоры цифровых сигналов

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

Поддержка суперкомпьютера

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

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

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

вычисления GPGPU

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

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

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

Языки программирования GPU

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

CUDA

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

OpenCL

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

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

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

C ++ AMP

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

OpenACC

OpenACC - стандарт программирования для параллельных вычислений, разработанный Cray, CAPS, NVIDIA и PGI. OpenAcc нацелен на программирование для гетерогенных систем CPU и GPU с расширениями C, C ++ и Fortran.

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

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

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

A = (A 11 A 12 ⋯ A 1 m A 21 A 22 ⋯ A 2 m ⋮ ⋮ ⋱ ⋮ A m 1 A m 2 ⋯ A mm), B = (B 11 B 12 ⋯ B 1 м B 21 B 22 ⋯ B 2 m ⋮ ⋮ ⋱ ⋮ B m 1 B m 2 ⋯ B мм) {\ displaystyle \ mathbf {A} = {\ begin {pmatrix} A_ {11} A_ {12 } \ cdots A_ {1m} \\ A_ {21} A_ {22} \ cdots A_ {2m} \\\ vdots \ vdots \ ddots \ vdots \\ A_ {m1} A_ {m2} \ cdots A_ {mm} \\\ end {pmatrix}}, \ quad \ mathbf {B} = {\ begin {pmatrix} B_ {11} B_ {12} \ cdots B_ {1m} \\ B_ {21} B_ {22} \ cdots B_ {2m} \\\ vdots \ vdots \ ddots \ vdots \\ B_ {m1} B_ {m2} \ cdots B_ {mm} \\\ end {pmatrix}}}{\ displaystyle \ mathbf {A} = {\ begin {pmatrix } A_ {11} A_ {12} \ cdots A_ {1m} \\ A_ {21} A_ {22} \ cdots A_ {2m} \\\ vdots \ vdots \ ddots \ vdots \\ A_ { m1} A_ {m2} \ cdots A_ {mm} \\\ end {pmatrix}}, \ quad \ mathbf {B} = {\ begin {pmatrix} B_ {11} B_ {12} \ cdots B_ {1m } \\ B_ {21} B_ {22} \ cdots B_ {2m} \\\ vdots \ vdots \ ddots \ vdots \\ B_ {m1} B_ {m2} \ cdots B_ {mm} \\\ end {pmatrix}}}

C = A × B = (C 11 C 12 ⋯ C 1 м C 21 C 22 ⋯ C 2 м ⋮ ⋮ ⋱ ⋮ C m 1 C m 2 ⋯ C мм), C ij = ∑ k = 1 m A ik B kj {\ displaystyle \ mathbf {C} = \ mathbf {A} \ times \ mathbf {B} = {\ begin {pmatrix} C_ {11} C_ {12} \ cdots C_ {1m} \\ C_ {21 } C_ {22} \ cdots C_ {2m} \\\ vdots \ vdots \ ddots \ vdots \\ C_ {m1} C_ {m2} \ cdo ts C_ {mm} \\\ end {pmatrix}}, \ quad C_ {ij} = \ sum _ {k = 1} ^ {m} A_ {ik} B_ {kj}}{\ displaystyle \ mathbf {C} = \ mathbf {A} \ times \ mathbf {B} = {\ begin {pmatrix} C_ {11} C_ {12} \ cdots C_ {1m} \\ C_ {21} C_ {22} \ cdots C_ {2m} \\\ vdots \ vdots \ ddots \ vdots \\ C_ {m1} C_ {m2} \ cdots C_ {mm} \\\ end {pmatrix}}, \ quad C_ {ij} = \ sum _ {k = 1} ^ {m} A_ {ik} B_ {kj}}

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

1 // Умножение матрицы MxM в C 2 void matrixMul (3 float * A, / / input matrix A 4 float * B, // input matrix B 5 float * C, // output matrix C 6 int size) // size of the matrix 7 {8 // N x N x N iterations 9 for (int row = 0; row < size; row++) { 10 for (int col = 0; col < size; col++) { 11 int id = row * size + col; 12 flot sum = 0.0; 13 14 for (int m = 0; m < size; m++) { 15 sum += (A[row * size + m] * B[m * size + col]); 16 } 17 18 C[id] = sum; 19 } 20 } 21 }
1 // Умножение матрицы MxM в OpenCL 2 __kernel void matrixMul (3 __global float * A, // входная матрица A 4 __global float * B, // входная матрица B 5 __global float * C, // output matrix C 6 __global int size) // размер матриц 7 {8 size_t id = get_global_id (0); // каждый поток работает с элементом 9 size_t row = id / size; 10 size_t col = id% size; 11 float sum = 0.0; 12 13 // N итераций 14 for (int m = 0; m < size; m++) { 15 sum += (A[row * size + m] * B[m * size + col]); 16 } 17 18 C[id] = sum; 19 }

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

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

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

y (n 1, n 2) = x (n 1, n 2) ∗ ∗ h (n 1, n 2) = ∑ k 1 = 0 m - 1 ∑ К 2 знак равно 0 м - 1 Икс (К 1, К 2) час (N 1 - К 1, N 2 - К 2) {\ Displaystyle y (n_ {1}, n_ {2}) = x (n_ {1}, n_ {2}) ** h (n_ {1}, n_ {2}) = \ sum _ {k_ {1} = 0} ^ {m-1} \ sum _ {k_ {2} = 0} ^ {m-1} x (k_ {1}, k_ {2}) h (n_ {1} -k_ {1}, n_ {2} -k_ {2})}{\ displaystyle y (n_ {1}, n_ {2}) = x (n_ {1}, n_ {2}) ** h (n_ {1}, n_ {2}) = \ sum _ {k_ {1} = 0} ^ {m-1} \ sum _ {k_ {2} = 0} ^ {m-1} x (k_ {1}, k_ {2}) h (n_ {1} -k_ {1}, n_ {2} -k_ {2})}

1 // 2 -D реализация свертки в OpenCL 2 __kernel void convolution (3 __global float * x, // входной сигнал x 4 __global float * h, // фильтр h 5 __global float * y, // выходной сигнал y 6 __global int size) // размер ROS входного сигнала и фильтра 7 {8 size_t id = get_global_id (0); // каждый поток работает с элементом 9 size_t row = size + size - 1; // количество строк выходного сигнала 10 size_t col = size + size - 1; // количество столбцов выходного сигнала 11 size_t n1 = id / row; 12 size_t n2 = id% col; 13 float sum = 0,0; 14 15 // N x N итераций 16 for (int k1 = 0; k1 < size; k1++) { 17 for (int k2 = 0; k2 < size; k2++) { 18 sum += (x[k1 * row + k2] * h[(n1 * row - k1) + (n2 - k2)]); 19 } 20 } 21 22 C[id] = sum; 23 }

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

Уравнение MD-свертки:

y (n 1, n 2,.., ns) = x (n 1, n 2,..., ns) ∗ ∗ h (n 1, n 2,..., ns) = ∑ k 1 = 0 m 1 - 1 ∑ k 2 = 0 m 2 - 1... ∑ ks = 0 ms - 1 x (k 1, k 2,..., ks) h (n 1 - k 1, n 2 - k 2,..., ns - ks) {\ displaystyle y (n_ {1}, n_ {2},..., n_ {s}) = x (n_ {1}, n_ {2},..., n_ {s}) ** h ( n_ {1}, n_ {2},..., n_ {s}) = \ sum _ {k_ {1} = 0} ^ {m_ {1} -1} \ sum _ {k_ {2} = 0 } ^ {m_ {2} -1}... \ sum _ {k_ {s} = 0} ^ {m_ {s} -1} x (k_ {1}, k_ {2},..., k_ {s}) h (n_ {1} -k_ {1}, n_ {2} -k_ {2},..., n_ {s} -k_ {s})}{\ displaystyle y (n_ {1}, n_ {2},..., n_ {s}) = x (n_ {1}, n_ {2},..., n_ {s}) ** h (n_ {1}, n_ {2},..., n_ {s}) = \ sum _ {k_ {1} = 0} ^ {m_ {1} -1} \ sum _ {k_ {2} = 0} ^ {m_ {2} -1}... \ sum _ {k_ {s} = 0} ^ {m_ {s} -1} x (k_ {1}, k_ {2},..., k_ {s}) h (n_ {1} - k_ {1}, n_ {2} -k_ {2},..., n_ {s} -k_ {s})}

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

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

X (Ω 1, Ω 2,..., Ω s) = ∑ n 1 = 0 m 1 - 1 ∑ n 2 = 0 m 2 - 1... ∑ нс знак равно 0 мс - 1 Икс (N 1, N 2,..., Нс) е - J (Ом 1 n 1 + Ом 1 n 1 +.. + Ω sns) {\ Displaystyle X (\ Omega _ {1}, \ Omega _ {2},..., \ Omega _ {s}) = \ sum _ {n_ {1} = 0} ^ {m_ {1} -1} \ sum _ {n_ {2 } = 0} ^ {m_ {2} -1}... \ sum _ {n_ {s} = 0} ^ {m_ {s} -1} x (n_ {1}, n_ {2},..., n_ {s}) e ^ {- j (\ Omega _ {1} n_ {1} + \ Omega _ {1} n_ {1} +... + \ Omega _ {s} n_ {s}) }}{\ displaystyle X (\ Omega _ {1}, \ Omega _ {2},..., \ Omega _ { s}) = \ sum _ {n_ {1} = 0} ^ {m_ {1} -1} \ sum _ {n_ {2} = 0} ^ {m_ {2} -1}... \ sum _ {n_ {s} = 0} ^ {m_ {s} -1} x (n_ {1}, n_ {2},..., n_ {s}) e ^ {- j (\ Omega _ {1} n_ {1} + \ Omega _ {1} n_ {1} +... + \ Omega _ {s} n_ {s})}}

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

1 // DTFT в OpenCL 2 __kernel void convolution (3 __global float * x_re, 4 __global float * x_im, 5 __global float * X_re, 6 __global float * X_im, 7 __global int size) 8 {9 size_t id = get_global_id (0); // каждый поток работает с элементом 10 X_re [id] = 0.0; 11 X_im [id] = 0,0; 12 13 for (int i = 0; i < size; i++) { 14 X_re += (x_re[id] * cos(2 * 3.1415 * id / size) - x_im[id] * sin(2 * 3.1415 * id / size)); 15 X_im += (x_re[id] * sin(2 * 3.1415 * id / size) + x_im[id] * cos(2 * 3.1415 * id / size)); 16 } 17 }

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

Разработка цифрового фильтра

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

Восстановление и анализ радиолокационного сигнала

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

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

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

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

Для точного диагноза используются двумерные или трехмерные медицинские сигналы, такие как ультразвук, Рентген, МРТ и КТ часто требуют очень высокой частоты дискретизации и разрешения изображения для восстановления изображений. Было показано, что за счет применения превосходной вычислительной мощности GPGPU мы можем получать медицинские изображения более высокого качества

Ссылки

6