Оптимизация алгоритма быстрого преобразования фурье для микропроцессора эльбрус-3М



Скачать 15.35 Kb.
Дата25.04.2016
Размер15.35 Kb.
ОПТИМИЗАЦИЯ АЛГОРИТМА БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

ДЛЯ МИКРОПРОЦЕССОРА ЭЛЬБРУС-3М

Грабежной А.В.


E-mail: grab_av@mcst.ru


Алгоритм быстрого преобразования Фурье (БПФ) широко применяется при обработке аудио- и видеоинформации (кодирование и декодирование звука, подавление шумов, двумерное преобразование Фурье при обработке изображений и т.д.). Причем на многих задачах именно БПФ определяет асимптотическую сложность всей задачи (алгоритмическая сложность БПФ n*log(n) существенно превосходит обычно линейную по n сложность остальной обработки сигнала). Соответственно задача оптимальной реализации БПФ является актуальной для современных микропроцессоров различной архитектуры.

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

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

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



  • переупорядочивание при записи в память результатов обработки слоя (для равномерного использования кэша данных на каждом слое);

  • совместная обработка нескольких слоев (двух- и трехслойная обработка);

  • использование константных таблиц и рекуррентных соотношений для вычисления sin и cos углов поворота;

  • упаковка 32-битных арифметических операций в 64-битные и переход к 64-битным операциям обращения с памятью;

  • совмещение обработки начальных слоев с битовой инверсией индексов;

  • использование поддерживаемых архитектурой микропроцессора Эльбрус-3М и оптимизирующим компилятором возможностей по конвейеризации циклов.

Полученный в результате проведенных оптимизаций код для микропроцессора Эльбрус-3М позволил продемонстрировать высокую производительность на задаче БПФ.


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница