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

Одной из важных задач в сфере изучения Земли из космоса является трехмерное моделирование фрагментов земной поверхности, как динамичных (например, поверхность океана), так и медленно меняющихся со временем. Ряд исследователей предлагает для формирования моделей методы, основанные на использовании дискретного преобразования Фурье (ДПФ). При этом, особенно в случае динамических моделей, критичным становится время вычисления преобразования. Его снижение позволяет увеличить размеры формируемого фрагмента, повысить качество и достоверность модели. Бурное развитие многопроцессорных систем, которые стали повседневной реальностью, а также появление современных видеокарт, сопровождаемых технологией параллельного программирования Cuda приводит к тому, что наиболее естественным способом снижения времени работы алгоритмов становится их параллельная реализация. Однако, несмотря на быстрое развитие теории параллельных алгоритмов в отношении многомерных дискретных преобразований, в литературе, в основном, по-прежнему, предлагаются только различные варианты распределения данных по процессорам. Чаще всего речь идет о построчно-столбцовом алгоритме с параллельным выполнением одномерных ДПФ по строкам и столбцам. Основная идея авторских алгоритмов заключается в погружении входных данных в специальную алгебраическую структуру. Это позволяет полноценно учитывать вещественность данных, а так же выполнять распараллеливание вычислений на уровне операций над элементами алгебры. Кроме того, независимо от способа представления данных, возможно распараллеливание в рамках стандартной двумерной схемы Кули-Тьюки. В настоящей работе производится сравнение этого подхода с авторскими параллельными алгоритмами двумерного ДПФ, показано влияние ускорения вычислений на качество модели.

Работа выполнена при финансовой поддержке РФФИ, проекты №№ 12-07-00751, 12-01-00822, 11-07-12060, 11-07-12059.