Курова М.Е., Шмаков Ю.Д.

Национальный горный университет, Украина

Использование технологии MPI для реализации  вейвлет-анализа на базе многоядерных процессоров

В последнее время для обработки нестационарных сигналов широкое распространение получили методы вейвлет-анализа (ВА), хорошо описывающие локальные особенности сигналов (скачки, аномальные наблюдения и т.п.).  ВА успешно применяется для фильтрации широкого класса помех,  анализа сложных особенностей сигналов, их объединения и разделения,  а также в задачах сжатия аудио- и видеоинформации. В частности, он является ядром новых международных стандартов по обработке неподвижных изображений и видео – JPEG2000 и MPEG-4. Все это обуславливает его чрезвычайно широкое применение в цифровой обработки сигналов для различных задач информационной обработки во многих областях: связи, радиотехнике, распознавании образов, сжатии информации и т.п. [1].

В основе ВА лежит вейвлет-преобразование (ВП), которое представляет собой особый тип линейного преобразования сигналов и отображаемых этими сигналами физических данных о процессах и свойствах природных сред и объектов. Одной из основных разновидностей ВП является дискретное вейвлет-преобразование (ДВП). Достоинством ДВП является его способность выявлять локальные особенности сигнала и обнаруживать динамику их изменения в зависимости от масштаба[2]. Если резкие изменения информационного  сигнала (например, аварийное отклонение показаний датчика) во многих случаях видны «невооруженным глазом», то взаимодействия событий на мелких масштабах, перерастающие в крупномасштабные явления, увидеть очень сложно. В то же время, сосредоточившись только на мелких деталях, можно не заметить явлений, происходящих на глобальном уровне. ДВП позволяет отслеживать как мелко- так и крупномасштабные изменения обрабатываемого информационного сигнала.

Рис. 1 Вейвлет-функция y, Масштабирующая функции φ

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

Применение ДВП рассмотрим на примере использования вейвлетов Добеши. Эти вейвлеты не имеют аналитического выражения и определяются только фильтрами [3]. Они являются непрерывными функциями, не тождественными нулю и недифференцируемыми на конечном отрезке. на рис. 1 представлен простейший вейвлет второго порядка D2 (M=2) из семейства ортонормальных вейвлетов Добеши (db2). Вид масштабирующей функции и вейвлета Добеши вычисляются методом итераций, а в практических приложениях используются только детализирующие hk и аппроксимирующие gk вейвлет-коэффициенты без вычисления конкретной формы вейвлетов. Вычисленные при M=N детализирующие коэффициенты hk высокочастотного фильтра  и аппроксимирующие коэффициенты gk низкочастотного фильтра и определяют вейвлет Добеши N-порядка.

На рис. 2 и 3 приведены характеристики трех вейвлетов Добеши (db2, db4 и db8) и спектры их коэффициентов соответственно. Как видно из рисунка, по мере увеличения порядка вейвлетов, крутизна среза их частотных характеристик увеличивается, а, соответственно, качество разложения сигналов и их реконструкции также будут улучшаться.

Рис. 2. Характеристика масштабирующих фильтров вейвлетов Добеши (db2, db4 и db8)

Рис. 3 Спектры коэффициентов

вейвлетов Добеши (db2, db4 и db8)

 

Разложение на составляющие по любому из дискретных вейвлетов осуществляется по формулам [4]:

в которых   - коэффициенты аппроксимации и детализации разложения, j - номер уровня разложения, k - порядковый номер коэффициентов, векторы h, g - коэффициенты cкейлинг- и вейвлет-фильтров.

Для максимального использования вычислительных возможностей многоядерных процессоров, необходимо использование методов параллельного программирования, позволяющих обеспечить равномерную загрузку  ядер процессора. Параллельная реализация алгоритма ВА на базе ДВП была реализовано с применением технологии MPI MPICH 2 в среде MS Visual Studio 2005. Для тестирования использована вычислительная система на базе одно-, двух- и четырехядерного процессора AMD Sempron 145, AMD Athlon II X2 245, AMD Athlon X4 635 частотой 2900 MHz.

В качестве примера рассмотрим фрагмент программной реализации параллельного алгоритма ВА ДВП для многоядерных процессоров:

for (i=0; i<RNum; i++)

{

s[i] = 0;// вектор апроксимирующих коэффициентов

d[i] = 0;// вектор детализирующих коэффициентов

                   for (k=0; k<n; k++)

                   {

                      s[i] += pRows[i*n+k]*h[k];// pRows- входной сигнал

                      d[i] += pRows[i*n+k]*g[k];

                   }

}

В программе были использованы следующие функции из библиотеки MPI:

·       Для распределения входного сигнала по процессорам – функция MPI_Scatterv;

·       Для передачи всем процесcорам коэффициентов cкейлинг- и вейвлет-фильтров применяется функция MPI_Bcast;

·       Для объединения результатов расчета и получения полного вектора апроксимирующих и детализирующих коэффициентов используется функция MPI_Allgatherv.

Данный алгоритм более подробно рассмотрен в [5].

Время выполнения вычислений  для выборки из 500 отсчетов сигнала при использовании этих алгоритмов представлены в таблице 1.1.

 

 

 

 

 

Таблица 1.1

Зависимость ускорения при выполнении параллельного алгоритма и времени расчета последовательного алгоритма от порядка вейвлетов Добеши для одно-, двух- и четырехъядерного процессоров представлены на рисунке  4 и 5 соответственно.

Рис. 5. Зависимость времени расчета последовательного алгоритма от порядка вейвлета Добеши

Рис. 4. Зависимость ускорения от порядка вейвлета Добеши

 

Выводы:

1.                 Использование многоядерных процессоров практически не обеспечивает повышение быстродействия ВА основанного на классических последовательных алгоритмах ДВП.

2.                 Применение методов параллельного программирования позволяет более рационально распределить вычислительную нагрузку между ядрами многоядерных процессоров при реализации ВА на основе ДВП. Это позволяет повысить скорость ВА. Так, при использовании двухядерных процессоров быстродействие ВА возрастает примерно в 1.5 раза, а при использовании четырехъядерных - в 1,8..2,0 раза.

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

Литература

1.                 Астафьева Н.М. Вейвлет-анализ: Основы теории и примеры применения// Успехи физических наук, 1996, т.166, № 11, стр. 1145-1170.

2.                 Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. ВУС, 1999, 204 с.

3.                 http://prodav.narod.ru/wavelet/index.html

4.                 http://matlab.exponenta.ru/wavelet

5.                 Курова М.Е., Шмаков Ю.Д. Реализация алгоритма вейвлет-анализа на базе многоядерных процессоров//Інновації та трансфер технологій: від ідеї до прибутку. НГУ, 2011, с. 221-223.