Институт Государственного управления, Главный редактор - д.э.н., профессор К.А. Кирсанов права и инновационных технологий (ИГУПИТ) тел. для справок: +7 (925) 853-04-57 (с 11⁰⁰ - до 18⁰⁰)

Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013 Опубликовать статью в журнале - http://publ.naukovedenie.ru

Размещено на http://www.allbest.ru/

1

http://naukovedenie.ru 16ТВН313

Институт Государственного управления, Главный редактор - д.э.н., профессор К.А. Кирсанов права и инновационных технологий (ИГУПИТ) тел. для справок: +7 (925) 853-04-57 (с 11⁰⁰ - до 18⁰⁰)

Интернет-журнал «НАУКОВЕДЕНИЕ» №3 2013 Опубликовать статью в журнале - http://publ.naukovedenie.ru

1

http://naukovedenie.ru 16ТВН313

Способы повышения эффективности вычисления быстрого преобразования Фурье

Methods of increasing the efficiency of fast Fourier transform with a multiprocessor system for the problems of digital signal processing

05.13.01 - Системный анализ управление и обработка информации (в промышленности)

Аврамчук Валерий Степанович Национальный исследовательский Томский Политехнический Университет Доцент, к.т.н.

Черемнов Александр Студент

Аннотация

Рассмотрены способы повышения эффективности использования аппаратных ресурсов ЭВМ при вычислении быстрого преобразования Фурье для расчета частотно-временной корреляционной функции на многопроцессорных системах. Адаптировано вычисление быстрого преобразования Фурье с учетом использования технологии CUDA. Экспериментально показано, что графические процессоры превосходят по скорости процессоры общего назначения при решении задач связанных с вычислениями.

Ключевые слова: цифровой сигнал, быстрое преобразование Фурье, корреляционный анализ, частотно-временная корреляционная функция, технология CUDA.

In the article the methods for calculating the efficiency of using hardware resources for fast Fourier transform computing are considered, that were used for calculating the time-frequency correlation function, using multiprocessor systems. It was adapted fast Fourier transform calculation based on the use of technology CUDA. It was experimentally shown that the GPU faster than the general-purpose processors in solving problems related to computing.

Keywords: digital signal, correlation analysis, frequency-time correlation function, fast Fourier transform, CUDA technology.

Введение

В настоящее время дискретное преобразование Фурье (ДПФ) используется практически во всех областях науки - цифровой обработке сигналов (ЦОС), акустике, физике, экономике, биологии, геологии, и многих других. Столь широкое использование преобразования Фурье объясняется хорошей алгоритмизацией, наличием большого числа готовых библиотек алгоритмов, эффективностью. Преобразование Фурье используется для решения различных задач ЦОС, таких как: фильтрация сигналов, вычисление свертки, корреляции, и многих других. Среди многочисленных способов вычисления преобразования Фурье наиболее широкое распространение получили алгоритмы быстрого преобразования Фурье (БПФ). В литературе [1] собрана библиография о более 3400 алгоритмах эффективного вычисления БПФ. Алгоритмы разрабатываются с учетом архитектурных особенностей используемого оборудования, при этом достигается максимальное быстродействие, компактность и эффективность кода.

Стремительное развитие вычислительных мощностей современных ЭВМ, постоянное увеличение объёмов обрабатываемой информации и расширение сфер применения цифровой обработки сигналов способствует созданию совершенно новых алгоритмов обработки сигналов. К создаваемым способам и программному обеспечению предъявляются более жесткие требования по быстродействию, возможности использования в режиме реального времени и точности. Удовлетворение этих требований невозможно без привлечения специализированных технологий. Цель данной работы заключается в исследовании путей повышения эффективности использования аппаратных ресурсов ЭВМ при вычислении быстрого преобразования Фурье при решении задач корреляционного анализа.

Теоретический анализ

Корреляционный анализ сигналов, также как и преобразование Фурье, используется при решении весьма разнообразных задач неразрушающего контроля и диагностики, анализа электрических цепей, идентификации систем, обработке изображений, и многих других [2]. Эффективный способ вычисления корреляционных функций основан на использовании теоремы о корреляции и БПФ [2] и называется быстрой корреляцией. Эффективность вычисления в таком случае зависит от используемого алгоритма БПФ и его реализации. Такой подход позволяет рассчитывать корреляционные функции практически в режиме реального времени. Несмотря на это неоспоримое достоинство, получаемые в результате расчета, корреляционные функции не несут информации о частотных свойствах сигнала. Устранить этот недостаток можно за счет использования метода расчета частотно-временных корреляционных функций [3,4], использование которого позволяет существенно повысить информативность проводимого анализа. Однако применение данного подхода сопряжено с большими вычислительными затратами так как данный метод вычисления требует многократного выполнения процедур БПФ.

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

Для многопроцессорных систем, в которых все вычисления выполняются исключительно на центральном процессоре (CPU), повысить эффективность можно с использованием технологий распараллеливания вычислительных процессов. Например, для достаточно известной среды разработки приложений Delphi используется класс TThread, позволяющий разработчику распараллеливать выполнение программы путем создания потоков, которым можно задать приоритет выполнения [5]. Корпорацией Microsoft разработан универсальный набор инструментов параллельного выполнения заданий ParallelExtensions, входящих в состав набора Microsoft .NET Framework 4.5 [6]. Данный инструментарий позволяет автоматически использовать все доступные процессоры для выделенных блоков кода, пригодных для распараллеливания, в существующем последовательном коде.

Современные центральные процессоры ЭВМ имеют от двух до восьми мощных вычислительных ядер, например, процессор Intel Core i7-3930K 3.2GHz или процессор AMD FX-8350 4.0GHz. Данные процессоры позволяют распараллеливать задачи в рамках «логических» ядер или «нитей» [7, 8], число которых в два раза больше числа физических ядер.

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

В настоящее время активно развивается специализированная технология CUDA (Compute Unified Device Architecture) являющаяся программно-аппаратной архитектурой, позволяющей применять графический процессор компании NVIDIA для неграфических расчетов на основе Runtime API. В литературе [9] отмечено, что приложения, использующие графические процессоры (GPU) NVIDIA для неграфических вычислений, продемонстрировали существенный прирост эффективности вычислений, по сравнению с реализациями, построенными на базе одних лишь центральных процессоров.

Runtime API представляет собой расширение к языку C/C++. Данное расширение позволяет выделять память на GPU, передавать GPU на обработку участки кода, оформленные как функции. Для параллельной обработки массивов данных может быть использован механизм блоков и сеток, позволяющий параллельно обрабатывать элементы массивов. При необходимости отображения результатов расчета в виде графиков поверхностей существует возможность прямого обращения к OpenGL и DirectX [9], это, в свою очередь, является неоспоримым достоинством этой технологии.

Как уже было отмечено выше основным недостатком метода расчета частотно-временных корреляционных функций является многократное вычисление БПФ. Эффективное распараллеливание алгоритма БПФ позволит свести к минимуму этот недостаток. Таким образом, в качестве алгоритма был выбран распространенный алгоритм вычисления БПФ Кули-Тьюки с фиксированным основанием 2, обладающий простотой реализации, наглядностью и поддающийся эффективному распараллеливанию [10]. Необходимо отметить, что вычисление БПФ с использованием механизма потоков на центральном процессоре обеспечивается на уровне итераций цикла.

Реализация выбранного алгоритма с применением технологии CUDA требует незначительной модификации последнего. Прежде всего, это связано с тем, что вычисление каждой единицы данных выполняется отдельным блоком нитей. В случае, когда возникает необходимость обработать массив данных, каждый элемент которого формируется независимо, необходимо разработать функцию, которую исполняют одновременно «нити», сгруппированные в блоки [9]. В рассматриваемой технологии реализован продвинутый механизм определения компилятором номера «нити» при помощи системной переменной tid. В зависимости от номера «нити» определяется, с какими элементами данных «нить» осуществляет работу.

аппаратный ресурс преобразование фурье

Экспериментальная часть

Для оценки эффективности рассмотренных технологий было создано программное обеспечение и поставлены тестовые эксперименты. В рамках экспериментов производилось сравнение времени, затраченного на расчет 1000 преобразований Фурье на выборках следующих размеров: 2048, 4096, 8192, 16384, 32768 отсчетов. Эксперимент проводился на видеоадаптере Nvidia GeForce 9600GT с поддержкой технологии CUDA и центральном процессоре Intel Core i5 имеющего четыре физических вычислительных ядра и поддержку технологии Intel® Hyper-Threading (Intel® HT). Результаты проведенных экспериментов сведены в таблицу и проиллюстрированы на рисунке.

Таблица Результаты экспериментов

Рис. График времени выполнения БПФ

Приложение, созданное в среде Visual Studio 2012, исполняется под управлением программной платформы .NET Framework 4.5. Время выполнения преобразований в среднем на 10% меньше времени, затраченного на преобразования программой, созданной в интегрированной среде разработки Delphi XE3. Увеличение эффективности программ, разрабатываемых в Visual Studio, может быть достигнуто за счёт применения специализированных приемов, таких как: использование адресных переменных, организация работы с массивами, начиная с последнего элемента, отказ от использования сложных типов данных и т.д. [11].

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

Рассмотренные технологии позволяют повысить эффективность использования аппаратных ресурсов ЭВМ при вычислении БПФ за счет использования всех логических ядер CPU, либо GPU. Распараллеливание алгоритма расчета БПФ на CPU реализованное в средах Visual Studio 2012 и в Delphi XE3 показало, что время вычисления БПФ зависит не только от размера выборки, но и от времени создания потока. Это время может быть сопоставимо, а иногда и превосходить, время выполнения преобразования.

В результатах экспериментов с использованием технологии CUDA приведено время вычисление БПФ на GPU без учета и с учетом времени копирования данных из оперативной памяти компьютера в оперативную память графической карты. Копирование данных приблизительно составляет 21% от времени вычисления БПФ.

Выводы

Рассмотрены технологии повышения эффективности вычисления БПФ, учитывающие архитектурные и технические особенности ЭВМ, позволяющие минимизировать основной недостаток метода расчета частотно-временных корреляционных функций.

Эффективность использования технологии параллельной обработки Microsoft .NET Framework и TThread Delphi зависит от числа вычислительных ядер центрального процессора. Для небольших размеров выборок время вычисления БПФ сравнимо или может быть меньше времени создания потоков.

Использование графического процессора в качестве вычислителя приводит к существенному сокращению времени обработки. Это обусловлено специализированной архитектурой данных процессоров и высокими скоростными характеристиками создания сеток и блоков потоков. Однако узким местом применения технологии CUDA является необходимость копирования данных в GPU. Поэтому при использовании данной технологии следует минимизировать передачу данных с центрального процессора на графический и обратно.

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

Литература

1. H.V. Sorensen, C.S. Burrus, M.T. Heideman. Fast Fourier transform database. - Boston: PWS Publishing Co., 1995. - 175 p.

2. Айфичер Э.C., Джервис Б.У. Цифровая обработка сигналов: практический подход. 2-е изд. - М.: Вильямс, 2008. - 992 c.

3. Способ спектрального анализа многочастотных периодических сигналов, представленных цифровыми отсчетами: пат. 2229140 Рос. Федерация. № 2003108753/28; опубл. 20.05.04, Бюл. № 14. - 6 с.

4. Аврамчук В.С., Чан Вьет Тьяу. Частотно-временной корреляционный анализ цифровых сигналов // Известия Томского политехнического университета. - 2009. -Т. 315. - № 5. - С. 112-115.

5. Архангельский А.Я. Приемы программирования в Delphi на основе VCL. - М.: Бином-Пресс, 2009. - 944 с.

6. Рихтер Д. CLR via C#. Программирование на платформе Microsoft .NET

Framework 4.0 на языке C#. 3-е изд. - СПб.: Питер, 2012. - 928 c.

7. Desktop 3rd generation Intel Core Processor Family: http://www.intel.ru/content/www/ru/ru/processors/core/3rd-gen-core-desktopspecification-update.html?wapkw=intel+core+i5-3570k+%D0%B8+i7-3770k - 02.02.2013.

8. AMD FX Processor Model Number and Feature Comparison http://www.amd.com/us/products/desktop/processors/amdfx/Pages/amdfx-modelnumber-comparison.aspx - 02.02.2013.

9. Сандерс Д., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессов. - М.: ДМК Пресс, 2011. - 232 c.

10. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления свертки. - М.: Радио и связь, 1985. - 248 c.

11. Visual Studio. Оптимизация кода. http://msdn.microsoft.com/ru-ru/library/xz7ttk5s%28v=vs.100%29.aspx - 02.02.2013.

Размещено на Allbest.ru