Эффективность вейвлет фильтрации сигнала на GPGPU

Содержание
Введение. 3
1 Вейвлет преобразование. 3
1.1 Организация модуля. 3
1.2 Фильтрация на CPU.. 3
1.3 Фильтрация на GPGPU.. 3
1.4 Проблемы распараллеливания. 3
1.5 Методы оптимизации. 3
Работа с памятью.. 3
Реорганизация вычислений. 3
1.6 Исследование производительности. 3
Заключение. 3
Список использованных источников. 3
Приложение А. Исходный код Вейвлет преобразования на GPGPU.. 3
dwt_kernel_float.cu — ядра GPGPU.. 3
dwt_float.cu — промежуточный слой между CPU и GPU слоями. 3
dwt_float.h — заголовочный файл с описание ядер и их параметров. 3
wavelet_denoise.cpp – общий ход Вейвлет преобразования. 3
Приложение Б. Характеристики сопроцессора на основе GPGPU.. 3
Приложение В. Запуск теста вейвлет преобразования. 3
Приложение Г. Калькулятор использования ресурсов устройства GPGPU.. 3

Введение
В численном и функциональном анализе дискретные вейвлет-преобразования (ДВП) относятся к вейвлет-преобразованиям, в которых вейвлеты представлены дискретными сигналами (выборками).
Первое ДВП было придумано венгерским математиком Альфредом Хааром. Для входного сигнала, представленного массивом 2n чисел, вейвлет-преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно (в случае чётной длины последовательности сумм) для образования следующего уровня разложения. В итоге получается 2n−1 разность и 1 общая сумма.
Это простое ДВП иллюстрирует общие полезные свойства вейвлетов. Во-первых, преобразование (один уровень) можно выполнить за O(n) операций. Во-вторых, оно не только раскладывает сигнал на некоторое подобие частотных полос (путём анализа его в различных масштабах), но и представляет временную область, то есть моменты возникновения тех или иных частот в сигнале. Вместе эти свойства характеризуют быстрое вейвлет-преобразование — альтернативу обычному быстрому преобразованию Фурье.
Самый распространенный набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши (Ingrid Daubechies) в 1988 году. Он основан на использовании рекуррентных соотношений для вычисления всё более точных выборок неявно заданной функции материнского вейвлета с удвоением разрешения при переходе к следующему уровню (масштабу). В своей основополагающей работе Добеши выводит семейство вейвлетов, первый из которых является вейвлетом Хаара. С тех пор интерес к этой области быстро возрос, что привело к созданию многочисленных потомков исходного семейства вейвлетов Добеши.
В ходе данной работы запланировали достичь целей:
· повысить производительность, чтобы получить эффект интерактивности и при необходимости иметь возможность реализовать обработку в реальном времени;
· получить единые средства для вейвлет преобразования с любым ядром (Добеши, Хаара и другие);
· получить бесплатное средство обработки сигналов;
· проверить на практике эффективность GPGPU.
1 Вейвлет преобразование
Вейвлеты успешно применяются в задачах, связанных с обработкой информации, таких как очистка сигнала, от помех, сжатие данных, выявление кратковременных и глобальных закономерностей. В данной работе этот инструмент применяется для очистки сейсмического сигнала от шума.
Вейвлет-преобразование одномерного сигнала состоит в его разложении по базису, сконструированному из обладающей определенными свойствами солитоноподобной функции (вейвлета) посредством масштабных изменений и переносов. Каждая из функций этого базиса характеризует как определенную пространственную (временную) частоту, так и ее локализацию в физическом пространстве (времени).
Таким образом, в отличие от традиционно применяемого для анализа сигналов преобразования Фурье, вейвлет-преобразование обеспечивает двумерную развертку исследуемого одномерного сигнала, при этом частота и координата рассматриваются как независимые переменные. В результате, появляется возможность анализировать свойства сигнала одновременно в физическом (время-координата) и в частотном пространствах.
Интегральное вейвлет-преобразование записывается следующим образом:
где
То есть базис функционального пространства может быть построен с помощью непрерывных масштабных преобразований и переносов вейвлета с произвольными значениями базисных параметров – масштабного коэффициента s и параметра сдвига .
Выбор анализирующего вейвлета, как правило, определяется тем, какую информацию необходимо извлечь из сигнала. Каждый вейвлет имеет характерные особенности во времени и в частотном пространстве. При этом наиболее подходящими для аппроксимации сейсмических сигналов являются вейвлеты Добеши.
Формула материнского вейвлета задается следующим способом:
где
M – целое число коэффициентов h,
Для дискретного вейвлет-преобразования Добеши 4-го порядка (при ) коэффициенты hk имеют следующие значения: h0 =0.48, h1 =0.84, h2 =0.22, h3 =-0.129 (рисунок 1).
На рисунке 1 приведены вейвлеты семейства Добеши 2-го, 4-го, 5-го, 8-го и 10-го порядков. С повышением порядка (число нулевых моментов) повышается гладкость функций. Таким образом, подбором порядка материнского вейвлета можно добиться наилучшего приближения.
Рисунок 1 ‑ Семейство вейвлетов Добеши
Для шумоподавления возьмем вейвлет Добеши 8.
В качестве парадигмы шумоподавления была использована парадигма Донохо-Джонстона. Данная парадигма является достаточно простой для реализации, экономичной в вычислительном отношении, поскольку подразумевает использование лишь быстрых алгоритмов вейвлет-преобразования, и содержит три шага, которые, будучи последовательно примененные к исходному сигналу, создают эффект шумоподавления.
В частности, на первом шаге данной парадигмы отыскивается одно-двухуровневое или более глубокое разложение сигнала, затем, на втором шаге, к каждому из коэффициентов детализации уровня j , а иногда коэффициентам аппроксимации того же уровня, применяется процедура трешолдинга, и, наконец, в заключении восстанавливается сигнал, характеризуемый, как ожидается, более высоким значением отношения сигнал/шум.
ДВП сигнала x получают применением набора фильтров. Сначала сигнал пропускается через низкочастотный (low-pass) фильтр с импульсным откликом g , и получается свёртка:
Одновременно сигнал раскладывается с помощью высокочастотного (high-pass) фильтра h . В результате получаются детализирующие коэффициенты (после ВЧ-фильтра) и коэффициенты аппроксимации (после НЧ-фильтра). Эти два фильтра связаны между собой и называются квадратурными зеркальными фильтрами (QMF).
Так как половина частотного диапазона сигнала была отфильтрована, то, согласно теореме Котельникова, отсчёты сигналов можно проредить в 2 раза:
Однако каждый из получившихся сигналов представляет половину частотной полосы исходного сигнала, так что частотное разрешение удвоилось.
Рисунок 2 – Свертка и прореживание сигнала
Схема разложения сигнала в ДВП
С помощью оператора прореживания
вышеупомянутые суммы можно записать короче:
Каскадирование и банки фильтров.
Это разложение можно повторить несколько раз для дальнейшего увеличения частотного разрешения с дальнейшим прореживанием коэффициентов после НЧ и ВЧ-фильтрации. Это можно представить в виде двоичного дерева, где листья и узлы соответствуют пространствам с различной частотно-временной локализацией. Это дерево представляет структуру банка (гребёнки) фильтров.
Рисунок 3 - Трехуровневый банк фильтров
На каждом уровне вышеприведённой диаграммы сигнал раскладывается на низкие и высокие частоты. В силу двукратного прореживания длина сигнала должна быть кратна 2n , где n — число уровней разложения.
Например, для сигнала из 32 отсчётов с частотным диапазоном от 0 до fn трёхуровневое разложение даст 4 выходных сигнала в разных масштабах:
Таблица 1– Трехуровневое разложение сигнала размером в 32 отсчета
Уровень
Частоты
Длина сигнала
3
0 … fn / 8
4
fn / 8 … fn / 4
4
2
fn / 4 … fn / 2
8
1
fn / 2 … fn
16
Рисунок 4 - Представление ДВП в частотной области
Вейвлет-фильтрация состоит из следующих действий:
1. прямое дискретное вейвлет преобразование;
2. пороговая обработка коэффициентов, связанная с оценкой средних значений вейвлет коэффициентов на каждом из уровней разложения и последующим пороговым обнулением коэффициентов отражающих слабые импульсные свойства сигнала;
3. обратное вейвлет преобразование.
1.1 Организация модуля
На рисунке ниже приведем предполагаемую схему организации работы программы.
Рисунок 5 — Организация Вейвлет преобразования.
На рисунке 5 мы видим модуль основной программы, модуль библиотеки gsl, модуль, реализующий параллельное вейвлет преобразование.
Основная программа формирует сигнал, подготавливает материнский вейвлет с помощью модуля GSL и выполняет параллельное Вейвлет-преобразование с помощью модуля cudaDwt.
Рисунок 6 – Ход вейвлет преобразования.
Исходя из целей, необходимо разработать модуль, который можно будет использовать без перекомпиляции на платформах одного типа и обладающий переносимостью на уровне компиляции при переносе с платформы на платформу (например, linux/Windows).
Опишем характеристики каждого из модулей:
Модуль CudaDwt — исполняемая статическая/динамическая библиотека, переносимость на уровне исходных кодов между платформами ОС.
Модуль GSL — свободно распространяемая библиотека для научных вычислений, переносимость на уровне исходных кодов между платформами ОС.
Требования:
CPU: intel-совместимый универсальный процессор не ниже i386.
GPU: NVIDIA видеокарта с поддержкой CUDA начиная с 8000-ой серии.
ОС: Windows XP и выше, Linux, Mac OS.
1.2 Фильтрация на CPU
Вейвлет преобразование выполняет свертку сигнала с фильтрами. Что и обуславливает длительную обработку при последовательной реализации.
Рассмотрим подробнее каждый из этапов.
Прямое преобразование
Выполняется сверка целевого сигнала с низкочастотным и высокочастотными фильтрами с одновременным прореживанием, что при последовательном выполнении дает трудоемкость кратную N/2.
Но так как данную операцию на исходной последовательности данных нужно проводить Log2 (N) раз, каждый раз уменьшая размерность на 2, то получаем трудоемкость:
Трешолдинг
При пороговой обработке необходимо дважды пройти полученную свертку с низкочастотным и высокочастотными фильтрами и произвести отсечение по уровням. Таким образом, имеем трудоемкость:
Обратное преобразование.
Обратное преобразование производится аналогично прямому и имеет ту же трудоемкость:
При использовании любых последовательных средств вычислений мы сталкиваемся с жесткой зависимостью от объема входных данных, выраженную в трудоемкости:
1.3 Фильтрация на GPGPU
GPGPU – сопроцессор к центральному процессору для массово параллельных вычислений. Теоретически при использовании данного устройства для алгоритмов, допускающих мелкозернистый параллелизм, будет отсутствовать сильная связь с объемом входных данных. То есть при любом объеме мы будем получать результат за ограниченное время.
Перечислим возможности GPGPU как массивно параллельного устройства вычисления:
· множество процессоров виртуально может быть представлено в любой конфигурации с тремя с измерениями;
· каждый процессор имеет уникальный идентификатор;
· процессоры разделены на сильно связные компоненты – потоки в блоках, и слабосвязные – блоки в сетке;
· для оптимизации работы реализована иерархия памяти, технологии группового чтения данных, кэшированного чтения данных;
· одновременно можно запустить на выполнение множество тысяч потоков.
Представим каждую из трех частей в параллельном виде, доступном для запуска на массивно параллельном вычислителе.
Прямое вейвлет преобразование.
При прямом вейвлет преобразовании выполняется свертка и для каждого значения ряда сигнала вычисляется новое значение в соответствии с массивами коэффициентов.
Так как значение свертки для отсчета не зависит от вычисления других, то все вычисления можно распараллелить по номеру отсчета.
Поэтому всё что нужно, это, используя необходимые CUDA расширения языка Си, переписать исходный код последовательной реализации, убрать конструкцию цикла, и сделать вычисление адреса текущего элемента во входной последовательности через уникальные идентификаторы процессора потока.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию