МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

Кафедра Вычислительной Техники 
 
 
 
 
 
 

Реферат

По дисциплине «Испытание и квалиметрия информационных систем»

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

                                   Факультет: АВТ

                                   Группа:  АММ-09

                                   Студент:  Е.Ю. Скоморохов

Проверил:    Хайретдинов М.С., Пискунов С.В.  
 
 
 

Новосибирск 2010 

Содержание

Введение 3

1 Вейвлет преобразование 4

1.1 Организация модуля 8

1.2 Фильтрация на CPU 10

1.3 Фильтрация на GPGPU 11

1.4 Проблемы распараллеливания 14

1.5 Методы оптимизации 14

Работа с памятью 15

Реорганизация вычислений 22

1.6 Исследование производительности 24

Заключение 28

Список использованных источников 29

Приложение А. Исходный код Вейвлет преобразования на GPGPU 30

dwt_kernel_float.cu — ядра GPGPU 30

dwt_float.cu — промежуточный слой между CPU и GPU слоями 32

dwt_float.h — заголовочный файл с описание ядер и их параметров 35

wavelet_denoise.cpp – общий ход Вейвлет преобразования 36

Приложение Б. Характеристики сопроцессора на основе GPGPU 38

Приложение В. Запуск теста вейвлет преобразования 39

Приложение Г. Калькулятор использования ресурсов устройства GPGPU 40 
 

 

Введение

 

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

     Первое  ДВП было придумано венгерским математиком  Альфредом Хааром. Для входного сигнала, представленного массивом 2n чисел, вейвлет-преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно (в случае чётной длины последовательности сумм) для образования следующего уровня разложения. В итоге получается 2n−1 разность и 1 общая сумма.

     Это простое ДВП иллюстрирует общие  полезные свойства вейвлетов. Во-первых, преобразование (один уровень) можно  выполнить за O(n) операций. Во-вторых, оно не только раскладывает сигнал на некоторое подобие частотных полос (путём анализа его в различных масштабах), но и представляет временную область, то есть моменты возникновения тех или иных частот в сигнале. Вместе эти свойства характеризуют быстрое вейвлет-преобразование — альтернативу обычному быстрому преобразованию Фурье.

     Самый распространенный набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши (Ingrid Daubechies) в 1988 году. Он основан на использовании рекуррентных соотношений для вычисления всё более точных выборок неявно заданной функции материнского вейвлета с удвоением разрешения при переходе к следующему уровню (масштабу). В своей основополагающей работе Добеши выводит семейство вейвлетов, первый из которых является вейвлетом Хаара. С тех пор интерес к этой области быстро возрос, что привело к созданию многочисленных потомков исходного семейства вейвлетов Добеши.

В ходе данной работы запланировали достичь целей:

• повысить производительность, чтобы получить эффект интерактивности и при необходимости иметь возможность реализовать обработку в реальном времени;
• получить единые средства для вейвлет преобразования с любым ядром (Добеши, Хаара и другие);
• получить бесплатное средство обработки сигналов;
• проверить на практике эффективность GPGPU.

1 Вейвлет преобразование

 

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

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

     Таким образом, в отличие от традиционно  применяемого для анализа сигналов преобразования Фурье, вейвлет-преобразование обеспечивает двумерную развертку исследуемого одномерного сигнала, при этом частота и координата рассматриваются как независимые переменные. В результате, появляется возможность анализировать свойства сигнала одновременно в физическом (время-координата) и в частотном пространствах.

     Интегральное вейвлет-преобразование записывается следующим образом:

     

где 

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

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

     Формула материнского вейвлета задается следующим способом: 

где

M – целое число коэффициентов h, 

     Для дискретного вейвлет-преобразования Добеши 4-го порядка (при ) коэффициенты h_k имеют следующие значения: h₀=0.48, h₁=0.84, h₂=0.22, h₃=-0.129 (рисунок 1).

     На  рисунке 1 приведены вейвлеты семейства Добеши 2-го, 4-го, 5-го, 8-го и 10-го порядков. С повышением порядка (число нулевых моментов) повышается гладкость функций. Таким образом, подбором порядка материнского вейвлета можно добиться наилучшего приближения.

Рисунок 1 - Семейство вейвлетов Добеши

     Для шумоподавления возьмем вейвлет Добеши 8.

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

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

     ДВП сигнала x получают применением набора фильтров. Сначала сигнал пропускается через низкочастотный (low-pass) фильтр с импульсным откликом g, и получается свёртка: 

     Одновременно  сигнал раскладывается с помощью  высокочастотного (high-pass) фильтра h. В результате получаются детализирующие коэффициенты (после ВЧ-фильтра) и коэффициенты аппроксимации (после НЧ-фильтра). Эти два фильтра связаны между собой и называются квадратурными зеркальными фильтрами (QMF).

     Так как половина частотного диапазона  сигнала была отфильтрована, то, согласно теореме Котельникова, отсчёты сигналов можно проредить в 2 раза: 
 

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

Рисунок 2 – Свертка и прореживание сигнала

Схема разложения сигнала в ДВП

     С помощью оператора прореживания  

     вышеупомянутые  суммы можно записать короче: 
 
 

     Каскадирование и банки фильтров.

     Это разложение можно повторить несколько  раз для дальнейшего увеличения частотного разрешения с дальнейшим прореживанием коэффициентов после  НЧ и ВЧ-фильтрации. Это можно представить в виде двоичного дерева, где листья и узлы соответствуют пространствам с различной частотно-временной локализацией. Это дерево представляет структуру банка (гребёнки) фильтров.

Рисунок 3 - Трехуровневый банк фильтров

     На  каждом уровне вышеприведённой диаграммы  сигнал раскладывается на низкие и  высокие частоты. В силу двукратного  прореживания длина сигнала должна быть кратна 2ⁿ, где n — число уровней разложения.

     Например, для сигнала из 32 отсчётов с частотным  диапазоном от 0 до f_n трёхуровневое разложение даст 4 выходных сигнала в разных масштабах:

Таблица 1– Трехуровневое разложение сигнала размером в 32 отсчета

 

Рисунок 4 - Представление ДВП в частотной области 

     Вейвлет-фильтрация состоит из следующих действий: