Параллельные алгоритмы двумерного быстрого преобразования Фурье

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

Введение

сигнал параллельный алгоритм процессор

Одним из сопутствующих факторов компьютерной революции оказалось появление совершенно новых областей исследования. С каждым годом по мере увеличения быстродействия, уменьшения стоимости и размеров ИС растут возможности решения задач все возрастающей сложности. К ним относится цифровая обработка многомерных сигналов, требующая значительных объемов цифровой памяти и соответствующего количества арифметических операций. Несмотря на сложность, цифровая обработка сигналов уже позволила найти решение ряда важных задач, начиная с компьютерной томографии (методики, позволяющей по проекциям рентгеновского изображения, полученным при различных ориентациях детекторов, выполнять трехмерную реконструкцию органов человеческого тела) и кончая проектированием полей пассивных акустических датчиков и исследованием ресурсов Земли с помощью спутников. Цифровая обработка многомерных сигналов имеет также прочное математическое обоснование, позволяющее не только понять уже достигнутое, но и эффективно исследовать новые проблемы по мере их возникновения и успешно их решать.

Грубо говоря, сигнал -- это некоторое средство для передачи информации, а целью обработки сигналов является извлечение этой информации. Так, ансамбли изменяющихся во времени электрических потенциалов, плотность зерен серебра фотографической эмульсии или массивы чисел в памяти ЭВМ представляют собой примеры сигналов. Обычно обработка сигналов включает в себя перенос информации с одного сигнала на другой. Независимо от своей физической сущности сигналы представляют интерес только благодаря содержащейся в них информации. Можно сказать, что обработка сигналов включает в себя две основные задачи -- преобразование способа представления информации в сигнале и сокращение ее объема.

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



1. Постановка задачи

1.1 Современное состояние проблемы

На сегодняшний день в вычислении быстрого преобразования Фурье (БПФ) наблюдаются следующие тенденции:

Аппаратное ускорение: использование спецпроцессоров и вычислительной мощности видеокарт.

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

Специализированные векторные возможности (SSE2 и SSE3) для четырехкомпонентных (одинарная точность вычислений с плавающей точкой) и двухкомпонентных (двойная точность) векторов появились в универсальных процессорах из-за возросших требований графических приложений, в первую очередь. Именно поэтому для определённых задач применение GPU выгоднее, ведь они изначально сделаны для них.

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

Самое главное -- эти несколько ядер мультипроцессора в GPU являются SIMD(одиночный поток команд, множество потоков данных) ядрами. И эти ядра исполняют одни и те же инструкции одновременно, такой стиль программирования является обычным для графических алгоритмов и многих научных задач, но требует специфического программирования. Зато такой подход позволяет увеличить количество исполнительных блоков за счёт их упрощения.

Итак, перечислим основные различия между архитектурами CPU и GPU. Ядра CPU созданы для исполнения одного потока последовательных инструкций с максимальной производительностью, а GPU проектируются для быстрого исполнения большого числа параллельно выполняемых потоков инструкций. Универсальные процессоры оптимизированы для достижения высокой производительности единственного потока команд, обрабатывающего и целые числа и числа с плавающей точкой. При этом доступ к памяти случайный [16].

Ещё один вариант ускорения преобразования Фурье - это использование специализированных процессоров, например, HPCx система, применяемая в университете Эдинбурга (the University of Edinburgh), Великобритания. Она состоит из 160 вычислительных и 8 управляющих файловых серверов IBM eServer с 575 узлами. Каждый узел состоит из 16 1.5 Гц POWER5 64-bit RISC процессоров. Вычислительная мощность системы HPCx составляет 15.3 терафлопс.

Процессор POWER5 64-bit RISC это двухядерный процессор с поддержкой одновременной многопоточности с двумя потоками, то есть фактически он реализует 4 логических процессора. Благодаря виртуальной векторной архитектуре, процессор POWER5 может работать как один векторный процессор.

В университете Эдинбурга ведется работа по распараллеливанию одно-, двух-, и трехмерного преобразования Фурье (многомерное преобразование Фурье ведется по строчкам и столбцам) при помощи OpenMP и MPI. Результаты экспериментов представлены в таблице [18].



Таблица 1 - Использование OpenMP, Университет Эдинбурга время в секундах

Число процессов	64*64	128*128	256*256	512*512	1024* 1024	2048* 2048	4096* 4096	8192* 8192
1	0.000119	0.000648	0.003352	0.017743	0.114502	0.599953	3.238710	14.58787
2	0.000073	0.000355	0.001733	0.009318	0.054626	0.328531	1.632488	7.432540
4	0.000047	0.000195	0.000876	0.004702	0.026887	0.184591	0.833760	3.834367
8	0.000038	0.000115	0.000483	0.002515	0.014010	0.101344	0.443282	1.980915
16	0.000029	0.000096	0.000282	0.001589	0.008271	0.057241	0.270873	1.331173

Таблица 2 - Использование MPI, Университет Эдинбурга время в секундах

Размер сигнала	MPI
64*64	0.000034
128*128	0.000092
256*256	0.000406
512*512	0.001570
1024*1024	0.009215
2048*2048	0.042280
4096*4096	0.273670
8192*8192	1.235662

Переход от основания 2 к более высоким (4,8,16, …) при использовании одномерного алгоритма БПФ Кули-Тьюки. Например, схема расчёта БПФ по основанию 16 для сигнала с 256 отсчётами. При использовании основания 2 потребуется 8 рекурсивных шагов, при использовании основания 16 - всего 2 (рисунок 1, 2).



Рисунок 1 - Обобщенный граф вычислений 256-точечного быстрого преобразования Фурье (БПФ-256/FFT-256) по основанию 16

Рисунок 2 - Развернутая схема блока 16-точечного дискретного преобразования Фурье (ДПФ-16/DFT-16)



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

Рисунок 3 - Схема вычисления двумерного преобразования Фурье по строчкам и столбцам

Распараллеливание двумерного преобразования Фурье выполняется на основе указанных выше пунктов.

1.2 Актуальность задачи

Одним из сопутствующих факторов компьютерной революции оказалось появление совершенно новых областей исследования. С каждым годом по мере увеличения быстродействия, уменьшения стоимости и размеров ИС растут возможности решения задач все возрастающей сложности. К ним относится цифровая обработка многомерных сигналов, требующая значительных объемов цифровой памяти и соответствующего количества арифметических операций. Несмотря на сложность, цифровая обработка сигналов уже позволила найти решение ряда важных задач, начиная с компьютерной томографии (методики, позволяющей по проекциям рентгеновского изображения, полученным при различных ориентациях детекторов, выполнять трехмерную реконструкцию органов человеческого тела) и кончая проектированием полей пассивных акустических датчиков и исследованием ресурсов Земли с помощью спутников. Цифровая обработка многомерных сигналов имеет также прочное математическое обоснование, позволяющее не только понять уже достигнутое, но и эффективно исследовать новые проблемы по мере их возникновения и успешно их решать.

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



2. Вводная глава

2.1 Точная постановка задачи

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

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

Реализовать разработанный алгоритм и провести численный эксперимент.

2.2 Преобразование Фурье

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

1) должна быть периодической, т. е

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

2) должна быть по меньшей мере кусочно-непрерывной, причем число разрывов конечно, а скачки - ограниченные.

3) должна иметь конечное число максимумов и минимумов.

Интеграл

должен сходиться, что следует из условия 2.

В общем случае, согласно теореме Фурье функция , имеющая видимый период и удовлетворяющая условиям Дирихле, может быть представлена следующим бесконечным рядом Фурье:

где коэффициенты , рассчитываются по формулам

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

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

абсолютно сходится, т.е.

то ряд Фурье функции сходится в точке к значению

в частности, в точке непрерывности - к значению функции в этой точке [9].

2.3 Двумерное дискретное преобразование Фурье и его обращение

Дискретное прямое и обратное преобразование Фурье допускают непосредственно обобщение и на двумерный случай. Прямое дискретное Фурье-преобразование функции (изображения размерами задается равенством



Как и в одномерном случае, это выражение должно быть вычислено для всех и также для всех Аналогично, по заданному фурье-преобразованию мы можем получить при помощи обратного преобразования Фурье, задаваемого выражением

где и

Элементы Фурье образа в общем случае являются комплексными величинами. Как и в случае комплексных чисел, значение удобно иногда выражать в полярных координатах:

где величина

называется модулем или спектром Фурье-преобразования, а величина



называются фазой или фазовым спектром преобразования.

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

где обозначает преобразование Фурье своего аргумента. Это равенство означает, что начало координат для Фурье-преобразования функции (т.е. та точка, где значение этого преобразования равно F(0,0)) находится в точке с координатами . Другими словами, умножение функции на величину приводит к сдвигу начала координат для ее образа в точку с частотными координатами которая является центром прямоугольной области размером занимаемой двумерным дискретным Фурье-преобразованием. Мы будем говорить об этой области в частотном пространстве как о частотном прямоугольнике. Он простирается от до и от до (напомним, что переменные и и v целые). Для того чтобы обеспечить целочисленность координат после сдвига, будем требовать, чтобы числа и были четными. При компьютерной реализации преобразования Фурье, индексы принимают значения от до и от до . Подлинный центр Фурье-образа тогда находится в точке

Значение преобразования в точке равно



т.е. среднему значению функции . Другими словами, если -- изображение, то значение фурье-преобразования в начале координат равно среднему значению яркости на изображении. Поскольку началу координат отвечают нулевые частоты, величину иногда называют постоянной (dc) составляющей спектра. Эта терминология происходит из электротехники, где «dc» обозначает постоянный ток (т.е. ток нулевой частоты).

Если функция f(x,y) вещественная, то ее Фурье-преобразование обладает симметрией по отношению к операции комплексного сопряжения, а именно

где «*» означает обычное комплексное сопряжение. Отсюда следует равенство

которое говорит о том, что спектр Фурье-преобразования симметричен.

2.4 Вычисление двумерного дискретного преобразования Фурье

Рассмотрим сигнал , который является двумерным периодическим сигналом с периодом по первой и второй координате. Отсчёты задаются, как , где .

Дискретное преобразование Фурье для данного сигнала задаётся формулой

Часто для вычисления дискретного преобразования Фурье (ДПФ) используют алгоритм с применением одномерных дискретных преобразований Фурье - двумерное быстрое преобразование Фурье по строкам и столбцам. Для этого вычисляют в следующем виде

Суммы в квадратных скобках представляют собой одномерные вычисления ДПФ по строкам исходного сигнала . Рассмотрим данный подход с алгоритмом двумерного быстрого преобразования Фурье по аналогу Кули-Тьюки, предложенным ниже.[13]

Во-первых, преобразуем формулу нахождения следующим образом:



где

Можно показать, что обладает свойством симметрии относительно

где

Сумма

является двумерным ДПФ сигнала , то есть сигнала, полученного прореживанием исходного сигнала по чётным отсчётам второй переменной; обозначим данной ДПФ через . Аналогично видно, что сумма



является ДПФ сигнала , полученного из исходного сигнала прореживание по нечётным отсчётам второй переменной; обозначим данное ДПФ, как .

Из (2.20) и (2.21) и введённых выше обозначений получаем, что

где

Таким образом, нахождение двумерного дискретного преобразования Фурье сигнала можно реализовать по следующему алгоритму:

1) Нахождение спектра сигнала , где .

2) Нахождение спектра , где .

3) Домножение отсчётов спектра на дополнительный множитель .

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

Рассмотрим количество комплексных сложений (вычитаний) и умножений в приведенном выше алгоритме. Для сигналов и отсчеты спектров и могут вычислены при помощи комплексных умножений и комплексных сложений (вычитаний).

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

Тогда из алгоритма (4) нахождение спектра сигнала потребует

комплексных умножений и

комплексных сложений.

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

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

Теперь рассмотрим сигнал , который является двумерным периодическим сигналом с периодом по первой и по второй координате. Отсчёты задаются, как , где .

Дискретное преобразование Фурье для данного сигнала задаётся формулой



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

По аналогии можно получить формулу для двумерного быстрого преобразования Фурье по аналогу Кули-Тьюки:

где

Можно показать, что обладает свойством симметрии относительно

где

Сумма



является двумерным ДПФ сигнала , то есть сигнала, полученного прореживанием исходного сигнала по чётным отсчётам второй переменной; обозначим данной ДПФ через . Аналогично видно, что сумма

является ДПФ сигнала , полученного из исходного сигнала прореживание по нечётным отсчётам второй переменной; обозначим данное ДПФ, как .

Из (2.29) и (2.30) и введённых выше обозначений получаем, что

где

Таким образом, нахождение двумерного дискретного преобразования Фурье сигнала можно реализовать по следующему алгоритму:

1) Нахождение спектра сигнала , где .

2) Нахождение спектра , где .

3) Домножение отсчётов спектра на дополнительный множитель .

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

Рассмотрим количество комплексных сложений (вычитаний) и умножений в приведенном выше алгоритме. Для сигналов и отсчеты спектров и могут вычислены при помощи комплексных умножений и комплексных сложений (вычитаний).

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

Тогда из алгоритма нахождение спектра сигнала потребует

комплексных умножений и

комплексных сложений.

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



2.5 Описание библиотеки MPI

Наиболее распространённой технологией программирования для параллельных компьютеров с распределённой памятью в настоящее время является MPI. Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии - Message Passing Interface (интерфейс передачи данных). Стандарт MPI фиксирует интерфейс, который должен соблюдаться как системой программирования на каждой вычислительной платформе, так и пользователем при создании своих программ. Современные реализации чаще всего соответствуют стандарту MPI версии 1.1. В 1997-1998 годах появился стандарт MPI-2.0, значительно расширивший функциональность предыдущей версии. Однако до сих пор этот вариант MPI не получил широкого распространения и в полном объёме не реализован не в одной системе.

Интерфейс MPI поддерживает создание параллельных программ в стиле MIMD (Multiple Instruction Multiple Data), что подразумевает объединение процессов с различными исходными текстами. Однако писать и отлаживать такие программы очень сложно, поэтому на практике программисты гораздо чаще используют SPMD - модель (Single Program Multiple Data) параллельного программирования, в рамках которой для всех параллельных процессов используется один и тот же код.

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

Для локализации взаимодействия параллельных процессов программы можно создать группы процессов, предоставляя им отдельную среду для общения - коммуникатор. Состав образуемых групп произволен. Группы могут полностью совпадать, входить одна в другую, не пересекаться или пересекаться частично. Процессы могут взаимодействовать только внутри некоторого коммуникатора, сообщения, отправленные в разных коммуникаторах, не пересекаются и не мешают друг другу. При старте программы всегда считается, что все порождённые процессы работают в рамках всеобъемлющего коммуникатора, имеющего предопределённое имя - MPI_COMM_WPRLD. Этот коммуникатор существует всегда и служит для взаимодействия всех запущенных процессов MPI-программы. Все взаимодействия протекают в разных коммуникаторах, никак не мешают друг другу.

Каждый процесс MPI-программы имеет в каждой группе, в которую он входит, уникальный атрибут - номер процесса, который является целым неотрицательным числом. В одном и том же коммуникаторе все процессы имеют различные номера. Но процесс может входить в другой коммуникатор, он будет иметь там другой номер. Поэтому два основных атрибута процесса: коммуникатор и номер в коммуникаторе. Если группа содержит n процессов, то номер любого процесса в данной группе лежит в пределах от 0 до n-1.

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

2.6 Комплекс высокопроизводительных вычислений ИКИТ СФУ

В Сибирском Федеральном Университете на базе Института Космических и Информационных технологий развернут мощный комплекс высокопроизводительных вычислений суперкомпьютер ИКИТ СФУ.

Суперкомпьютер ИКИТ СФУ обеспечивает научных сотрудников, преподавателей, аспирантов и студентов современными вычислительными мощностями в проведении исследований и экспериментов. В составе комплекса находятся 224 вычислительных узла IBM Blade HS21. Каждый узел включает в себя 4 Gb оперативной памяти и два четырехядерных процессора Xeon quad core 2.33 GHz; два высокопроизводительных узла IBM System X 3950, объединенные в одну вычислительную систему по четыре четырехядерных процессора и 16 Gb оперативной памяти в каждом узле. Система хранения данных IBM DS3400 представляет собой единое дисковое пространство емкостью 20Tb. Пропускная способность вычислительной сети Infiniband, которая объединяет узлы кластера, достигает 20 Gbit/s.

Производительность комплекса, согласно тесту linpack, составляет 13,057TFlops. Пиковая производительность - 16872,3MFlops. Суперкомпьютер СФУ, на сегодняшний день, занимает 14 место в списке пятидесяти самых мощных компьютеров России.

Комплекс активно используют в научных исследованиях профессорско-преподавательский состав СФУ и других вузов. Приобретается и создается системное и прикладное программное обеспечение, которое позволяет решать сложные задачи в таких областях, как механика твердого тела, жидкости и газа, геология, гео- и гидрофизика, электродинамика, экология, а так же в задачах, связанных с проектированием технических устройств и систем. Суперкомпьютер работает под управлением операционной системы Linux и выполняет задачи на специализированном, кластерном программном обеспечении OpenMPI.

Комплекс Высокопроизводительных вычислений ИКИТ СФУ обладает наибольшей вычислительной мощностью на территории Сибири. Сам комплекс представляет собой специализированное оборудование и программное обеспечение компании IBM (систему мониторинга и управления комплексом), в сочетании со свободным программным обеспечением. Кластер используется научными сотрудниками для расчетов своих прикладных задач и студентами СФУ в образовательных целях.

Рисунок 4 - Комплекс высокопроизводительных вычислений ИКИТ СФУ



3. Основные достигнутые результаты

3.1 Словесное описание алгоритма работы программы

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

Программу можно разбить на несколько смысловых частей:

1) Ввод данных из файла

2) Двумерное быстрое преобразование Фурье по строчкам и столбцам

3) Сохранение результата

4) Ввод данных из файла

5) Двумерное быстрое преобразование Фурье по аналогу Кули-Тьюки

6) Сохранение результата

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

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

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



3.1 Блок-схема алгоритма работы программы

Рисунок 5 - Блок-схема алгоритма работы ропграммы



3.2 Основные трудности, возникшие в процессе работы

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

Способ хранения и обработки комплексных чисел

Первоначальное решение - это использование стандартного класса complex<type>, хранящего пару чисел (вещественную и мнимую части). Основное его преимущество - это готовые операции с комплексными числами (умножение, деление, сложение, вычитание, взятие модуля, сопряжение), а также комплексная экспонента, что заметно упрощает написание программы. Также к преимуществам можно отнести приватность данных (данные можно изменять только через вызов специальных функций, а напрямую нельзя), благодаря чему данные нельзя будет случайно изменить в ходе написания программы. Но это преимущество является и недостатком, так как на вызов функций для изменения данных комплексного числа требуется дополнительное время. Для решения этой проблемы мной было принято решение не использовать класс complex<type>, а хранить реальную и мнимую части числа в двух переменных (массивах) и обращаться к ним напрямую. Однако такой метод заключает в себе некоторые сложности. Одна из них - это отсутствие готовых операций с комплексными числами, их пришлось реализовывать вручную в коде программы в каждом месте, где необходимо сложить (вычесть, умножить, разделить) два комплексных числа (для исключения частых вызовов функций - операций с комплексными числами). Вторая сложность - это отсутствие защиты данных от случайной перезаписи в процессе выполнения/написания кода программы. Обе эти сложности усложнили процесс написания программы, однако такой подход (хранение реальной и мнимой части числа не в структуре, а в двух переменных) увеличил производительность программы в десятки раз.

Выбор типа данных для хранения и обработки двумерного сигнала

Для работы с вещественными числами в языке программирования С++ используются два типа данных: float и double. Тип double - это число с двойной точностью (по сравнению с типом float) , что приводит к большой точности вычислений. К тому же в современных процессорах время выполнения операций умножения и сложения для типов double и float одинаково, что не сказывается на скорости вычислений. Однако для хранения одного числа типа double необходимо выделить 8 байт памяти (например, для сигнала размером 8192*8192 потребуется 512 Мегабайт), для типа float всего 4 байта. Так как использование дискретного входного сигнала заметно снижает точность вычислений, то использование данного типа не скажется на результате. Ещё одним плюсом использования в программе типа данных float является то, что за счет меньшего объёма памяти вероятность попадания в КЭШ-память процессора намного выше, следовательно, происходит меньше обращений к оперативной памяти, что ускоряет работу программы.

Вычисление комплексной экспоненты

Самый простой способ - это прямое вычисление значения экспоненты на каждом шаге. Этот метод имеет наибольшую точность, однако требует больших затрат времени (например, время выполнения операций сложения, умножения вещественных чисел - несколько наносекунд, вычисления же синуса, косинуса занимает несколько микросекунд). Его можно заметно улучшить, если вычислить значения тригонометрических функций один раз и записать их в массив, а затем на каждом шаге обращаться к этому массиву. В данном случае уменьшается общее время вычислений за счет уменьшения числа подсчетов значений синуса и косинуса, а также соблюдается высокая точность вычислений. Однако он имеет небольшой недостаток: необходима дополнительная память для хранения вычисленных значений тригонометрических функций, однако количество требуемой памяти намного меньше размера сигнала. Этот метод можно ускорить двумя способами. Во-первых, можно вычислить лишь значения синуса и косинуса, лежащие в первой четверти, а затем при помощи формул приведения вычислить остальные (получим ускорение около 4 раз). Во-вторых, можно вычислить лишь одно значение синуса и косинуса, а остальные значения можно получить последовательным домножением на первое (поворот текущего значения на минимальных угол). При таком подходе значительно уменьшается общее время вычисления экспонент (порядка N раз при N*N отсчетах сигнала), однако возникает незначительное снижение точности вычислений (ошибка в 8 знаке после запятой при 16777216 отсчетах). Для борьбы с ошибкой можно периодически явно вычислять значение синуса и косинуса, а затем осуществлять операцию поворота над ним.

Способ выделения памяти под двумерный массив

Самый простой в работе - это выделение памяти сначала под столбец указателей, а потом для каждого указателя под строку элементов. Такой метод дает удобную индексацию двумерного массива (строка, столбец), но строки в памяти могут находиться не последовательно, что может привести к частому считыванию данных из оперативной памяти в КЭШ. Однако есть более производительный способ - это выделение памяти под один большой одномерный массив. В нем строки данных будут расположены в памяти последовательно, что уменьшит вероятность не попадания в КЭШ и облегчит задачу распараллеливания. Но у этого способа есть недостаток - сложная индексация двумерного массива при написании программы (однако считается, что вычисление индекса происходит быстрее, чем не попадание в КЭШ в предыдущем случае). К тому же, большая длина одномерного массива может привести к выходу индекса за границу типа целых чисел (максимальное число: 2147483648), поэтому для индексации приходится использовать тип __int64 (максимальное число: 9223372036854775808). Другой способ решения этой проблемы - это выделение одномерного массива как большого цельного куска памяти, выделение памяти под столбец указателей, и распределение указателей на строки по всему одномерному массиву подряд. Этот способ позволяет получить последовательное расположение строк в памяти и удобную двумерную индексацию (строка, столбец), однако несколько усложняет процесс выделения и освобождения памяти.

Пересылка данных между процессами

Первоначальное решение - использование стандартных пересылок типа «точка-точка» (MPI_Send, MPI_Resv). Они позволяют наглядно проследить передачу данными между процессами, но, так как основная модель распараллеливания - это наличие главного процесса, который пересылает и принимает данные от всех других, то происходит задержка при пересылке данных (процессы простаивают до тех пор, пока главный процесс не перешлет данные всем остальным). К тому же приходится вычислять тэг (уникальный номер - идентификатор) для каждого сообщения, чтобы данные не потерялись в процессе пересылки или вовремя достигли нужного процесса. Решение этой проблемы - использование групповых операций передачи данных (MPI_Bcast, MPI_Gather, MPI_Scatter). Данные операции оптимизированы под массовую рассылку данных произвольному число процессов (одинаковых данных всем, части данных каждому процессу, сбор частей данных от каждого процесса). Им не нужно определять тэг для каждого сообщения. Но основное требование к этим функциям - последовательное расположение данных в памяти, поэтому приходиться хранить данные в одномерном массиве и транспонировать его в двумерном БПФ по строчкам и столбцам. В двумерном БПФ по аналогу Кули-Тьюки приходится регистрировать новые типы данных (описывать местоположение начального элемента и сдвиг между элементами) для пересылки процессам строк с произвольным номером.

Увеличение числа процессов при распараллеливании

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

Увеличение частоты пересылки данных

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

3.3 Результаты численного эксперимента

Таблица 3 Размер*Размер, один процессор - 8 ядер время в секундах

Размер	Число процессов	БПФ по строчкам и столбцам	БПФ по аналогу Кули-Тьюки	Ускорение Кули-Тьюки
1024	1	0.490	0.310	~1.6
	2	0.310	0.310	~1.0
	4	0.220	0.270	~0.8
	8	0.180	0.270	~0.7
	16	0.180	0.350	~0.5
2048	1	2.330	1.330	~1.7
	2	1.500	1.260	~1.2
	4	1.060	0.950	~1.1
	8	0.840	0.850	~0.9
	16	0.850	1.000	~0.8
4096	1	9.880	5.850	~1.7
	2	6.240	4.590	~1.4
	4	4.370	3.590	~1.2
	8	3.430	3.060	~1.1
	16	3.740	3.390	~1.1
8192	1	43.210	25.190	~1.7
	2	26.990	19.160	~1.4
	4	18.550	14.870	~1.2
	8	14.520	13.130	~1.1
	16	14.090	11.700	~1.2

Таблица 4 - число отсчетов: Размер*Размер, несколько процессоров - 8 ядер время в секундах

Размер	Число процессов	БПФ по строчкам и столбцам	БПФ по аналогу Кули-Тьюки
		2 процесса	4 процесса	2 процесса	4 процесса
1024	1	0.490	0.480	0.310	0.300
	2	0.610	0.600	1.170	1.150
	4	0.400	0.950	0.830	1.010
	8	0.290	0.330	0.630	0.840
	16	28.710	0.280	96.300	0.730
2048	1	2.330	2.310	1.340	1.320
	2	2.860	2.840	3.740	3.720
	4	2.080	2.420	2.800	3.610
	8	1.620	2.010	2.280	3.170
	16	154.330	1.750	-	71.360
4096	1	9.880	9.860	5.840	5.840
	2	9.730	9.710	13.020	12.970
	4	6.900	7.840	10.500	14.040
	8	5.400	6.480	36.800	120.610
	16	-	5.600	-	189.220
8192	1	43.170	42.950	25.300	26.530
	2	36.910	36.340	49.810	52.320
	4	25.940	29.070	41.810	88.310
	8	20.760	24.310	36.800	228.750
	16	-	35.770	-	-



Заключение

В ходе дипломной работы были закреплены знания, полученные в процессе обучения, приобретены новые знания в области параллельного программирования, разработаны параллельные алгоритмы двумерного быстрого преобразования Фурье, данные алгоритмы реализованы на языке программирования высокого уровня С++ с использованием библиотеки MPI. Цели, поставленные в начале дипломной работы, были достигнуты.



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

1.Алгоритмы быстрого преобразования Фурье FFT (fast Fourier transform). Принцип построения [Электронный ресурс] : 2008. - Режим доступа: www.dsplib.ru. - Загл. с экрана.

2.Антонов, А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие / Антонов, А.С. - М.: Изд-во МГУ, 2004.-71 с.

3.Гонсалес, Р. Цифровая обработка изображений / Гонсалес Р., Вудс Р.: Москва: Техносфера, 2006 - 1072 с., 82-113 c.

4.Гришагин, В.А. Параллельное программирование на основе MPI. Учебное пособие / Гришагин В.А., Свистунов А.Н. - Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2005 -93 с.

5.Даджион, Д. Цифровая обработка многомерных сигналов: Пер. с англ. / Даджион Д., Мерсеро Р.: - М.: Мир, 1988. - 488 с., ил., 231-249.

6.Дубровина, О.В. Исследование алгоритмов быстрого преобразования Фурье двумерных сигналов для параллельных вычислительных систем [Электронный ресурс]: ДонНТУ, 2008. - Режим доступа: http://masters.donntu.edu.ua/2009/fvti/dubrovina/diss/index.htm. - Загл. с экрана.

7.Инструменты параллельного программирования в системах с общей памятью / Корняков К.В., Кустиков В.Д, Мееров И.Б., Сиднев А.А., Сысоев А.В., Шишков А.В.: - Нижегородский государственный университет им. Н.И.Лобачевского, 2010.

8.Комплекс Высокопроизводительных вычислений ИКИТ СФУ [Электронный ресурс]: Красноярск, 2011. - Режим доступа: www.cluster.sfu-kras.ru. - Загл. с экрана.

9.Кудрявцев, Л.Д. Краткий курс математического анализа. Т.2. Дифференциальное и интегральное исчисления функций многих переменных. Гармонический анализ: учебник. / Кудрявцев Л.Д. - 3-е изд. перераб. -Москва: ФИЗМАТЛИТ, 2005. - 254 с., 274-296.

10.Малоземов, В.Н. Основы дискретного гармонического анализа . Ч.2 / Малоземов В.Н., Машарский С.М. - Спб.: НИИММ, 2003.

11.Параллельный алгоритм дискретного преобразования Фурье [Электронный ресурс]: 2010. - Режим доступа: http://www.intuit.ru/department/supercomputing/ppmcp/12/. - Загл. с экрана.

12.Смоляная, Д. В. Исследование эффективной параллельной реализации быстрого преобразования Фурье для цифровых изображений [Электронный ресурс]: ДонНТУ, 2009. - Режим доступа: http://masters.donntu.edu.ua/2009/fvti/smolianaya/diss/index.htm. - Загл. с экрана.

13.Тутатчиков, В.С. Алгоритм параллельного быстрого преобразования Фурье для анализа изображений // XI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям / Тутатчиков В.С., Носков М.В., Старовойтов А.В. - Новосибирск. 2010. 80 с.

14.Bailey, D.H. A High-Performance FFT Algorithm for Vector Supercomputers // International Journal of Supercomputer Applications / Bailey D.H., том.2, №.1, 1988, 82-87 с

15.Cooley, J.W. An algorithm for the machine calculation of complex Fourier series / Cooley J.W., and Tukey J. - Math. Comput. 19, 1965, С. 297-301.

16.CUDA CUFFT Library/ Официальный сайт разработчика [Электронный ресурс]:2010. - Режим доступа: http://developer.download.nvidia.com/compute/cuda/2_1/toolkit/docs/CUFFT_Library_2.1.pdf. - Загл. с экрана.

17.Fast Fourier Transformation [Электронный ресурс]: Красноярск, 2011. - Режим доступа: http://www.fftw.org/. - Загл. с экрана.

Parallel Fourier Transformations using shared memory nodes // Solon Pissis. - 2008. - 78 с.



Приложение

Текст программы

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

#ifndef FOURIER_CPP

#define FOURIER_CPP

#include <math.h>

#include <conio.h>

#include <iostream>

#include <mpi.h>

using namespace std;

const float M_PI = (float)3.1415926535897932384626433832795;

//одномерное преобразование Фурье, N - размер массива, f - исходный вектор, в который пишется преобразование, trig - вычисленные значения cos и sin, oper - направление преобразования Фурье: -1 - прямое, +1 - обратное

void Fure_line_with_trig(int N, int s, float *Real, float *Image, float *Cos, float *Sin, int oper) //массив f - уже реверсирован

{

int x1, x2;

float Exp1_Real, Exp1_Image, Exp2_Real, Exp2_Image;//, temp_Real, temp_Image;

int v, Nv=N, dv=1, dv2, p, l;

int index;

for(v=1;v<=s;v++)

{

dv2=dv*2;

Nv/=2;

for(p=0; p<Nv; p++)

for(l=0; l<dv; l++)

{

x1=l+p*dv2; x2=x1+dv;

Exp1_Real = Real[x1];

Exp1_Image = Image[x1];

index = (N/(2*dv))*l;//l*Nv;

Exp2_Real = Cos[index]*Real[x2] - oper*Sin[index]*Image[x2];

Exp2_Image = Cos[index]*Image[x2] + oper*Sin[index]*Real[x2];

Real[x1] = Exp1_Real + Exp2_Real;

Image[x1] = Exp1_Image + Exp2_Image;

Real[x2] = Exp1_Real - Exp2_Real;

Image[x2] = Exp1_Image - Exp2_Image;

}

dv *= 2;

}

float temp = sqrt((float)N);

for(v=0;v<N;v++)

{

Real[v] = Real[v] / temp;

Image[v] = Image[v] / temp;

}

}

//БПФ по строчкам и столбцам

//для главного процесса передаются данные, для остальных Real = NULL, Image = NULL

void Fure2(int Height, int log2Height, int Width, int log2Width, float **Real, float **Image, bool flag, int rank, int size)

{

int i, j, oper;

float *Real_Array_Height, *Image_Array_Height, *Real_Array_Width, *Image_Array_Width;

if (flag)

oper = 1;

else

oper = -1;

Real_Array_Height = new float[Height];

Image_Array_Height = new float[Height];

Real_Array_Width = new float[Width];

Image_Array_Width = new float[Width];

float *Cos_Height, *Sin_Height, *Cos_Width, *Sin_Width, arg, TempSin, TempCos;//, temp;

Cos_Height = new float[(Height+1)/2]; //проверка при длине массива в 1

Sin_Height = new float [(Height+1)/2]; // [0,Pi]

arg = 2*M_PI/(float)Height;

TempSin = sin(arg);

TempCos = cos(arg);

Cos_Height[0] = 1; //cos(0)=1

Sin_Height[0] = 0; //sin(0) = 0

Cos_Height[1] = TempCos;

Sin_Height[1] = TempSin;

for(i=2;i<Height/2;i++)

{

Cos_Height[i] = Cos_Height[i-1]*TempCos - Sin_Height[i-1]*TempSin;

Sin_Height[i] = Sin_Height[i-1]*TempCos + Cos_Height[i-1]*TempSin;

}

Cos_Width = new float [(Width+1)/2]; //проверка при длине массива в 1

Sin_Width = new float [(Width+1)/2]; // [0,Pi]

arg = 2*M_PI/(float)Width;

TempSin = sin(arg);

TempCos = cos(arg);

Cos_Width[0] = 1; //cos(0)=1

Sin_Width[0] = 0; //sin(0) = 0

Cos_Width[1] = TempCos;

Sin_Width[1] = TempSin;

for(i=2;i<Width/2;i++)

{

Cos_Width[i] = Cos_Width[i-1]*TempCos - Sin_Width[i-1]*TempSin;

Sin_Width[i] = Sin_Width[i-1]*TempCos + Cos_Width[i-1]*TempSin;

}

for(i=0;i<Height;i++) //вызываем одномерное преобразование Фурье для каждой строки

{

for(j=0;j<Width;j++) //заполняем массив a с транспонированием

{

Real_Array_Width[j] = Real[i][j];//[Index_Height[i]][Index_Width[j]];

Image_Array_Width[j] = Image[i][j];//[Index_Height[i]][Index_Width[j]];;

}

Fure_line_with_trig(Width,log2Width,Real_Array_Width,Image_Array_Width,Cos_Width,Sin_Width,oper);

for(j=0;j<Width;j++) //считываем данные

{

Real[i][j] = Real_Array_Width[j];

Image[i][j] = Image_Array_Width[j];

}

}

for(i=0;i<Width;i++) //вызываем одномерное преобразование Фурье для каждой строки

{

for(j=0;j<Height;j++)

{

Real_Array_Height[j] = Real[j][i];//[Index_Width[j]][Index_Height[i]];

Image_Array_Height[j] = Image[j][i];//[Index_Width[j]][Index_Height[i]];

} Fure_line_with_trig(Height,log2Height,Real_Array_Height,Image_Array_Height,Cos_Height,Sin_Height,oper);

for(j=0;j<Height;j++)

{

Real[j][i] = Real_Array_Height[j];

Image[j][i] = Image_Array_Height[j];

}

}

delete[] Cos_Height;

delete[] Sin_Height;

delete[] Cos_Width;

delete[] Sin_Width;

delete[] Real_Array_Height;

delete[] Image_Array_Height;

delete[] Real_Array_Width;

delete[] Image_Array_Width;

}

//модифицированный алгоритм Кули-Тьюки

void Fourier_Kyli_Tuki (int N, int s, float *Real, float *Image, bool flag, int rank, int size)

{

int oper=0, x1, x2, y1, y2;

int i, j;

if(flag)

oper = 1;

else

oper = -1;

float Exe1_Real, Exe1_Image, Exe2_Real, Exe2_Image, Exe0_Real, Exe0_Image, Exe3_Real, Exe3_Image, X1_Real, X1_Image, X2_Real, X2_Image;

int v, Nv, dv, dv2, p1, l1, p2, l2;

int *Counts, *DisplsX1, *DisplsX2; //число элементов и смещение

int *NumberLinesX, LinesPerProcess, *ArrayL1;

LinesPerProcess = (N/2)/size;

Counts = new int [size];

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

Counts[i] = N;

DisplsX1 = new int[size];

DisplsX2 = new int[size];

NumberLinesX = new int[N];

ArrayL1 = new int[N];

float *LineX1Real, *LineX1Image, *LineX2Real, *LineX2Image;

LineX1Real = new float[N];

LineX1Image = new float[N];

LineX2Real = new float[N];

LineX2Image = new float[N];

int index1,index2;

float *Cos, *Sin, arg, CosTemp, SinTemp;

Cos = new float [(N+1)/2]; //проверка при длине массива в 1

Sin = new float [(N+1)/2]; // [0,Pi]

arg = 2*M_PI/(float)N;

float TempSin, TempCos;

TempSin = sin(arg);

TempCos = cos(arg);

Cos[0] = 1; //cos(0)=1

Sin[0] = 0; //sin(0) = 0

if(N!=2)

{

Cos[1] = TempCos;

Sin[1] = TempSin;

}

for(i=2;i<N/2;i++)

{

Cos[i] = Cos[i-1]*TempCos - Sin[i-1]*TempSin;

Sin[i] = Sin[i-1]*TempCos + Cos[i-1]*TempSin;

}

if(N>=4)

{

Cos[N/4] = 0;

Sin[N/4] = 1;

}

dv = 1;

dv2 = dv*2;

Nv = N/dv2;

for(v=1; v<=s; v++)

{

for(p1=0,i=0; p1<Nv; p1++)

for(l1=0; l1<dv; l1++,i+=2) //x - Height

{

//запоминаем нумерацию строк на текущей итерации

NumberLinesX[i] = l1+p1*dv2;

NumberLinesX[i+1] = NumberLinesX[i]+dv;

ArrayL1[i] = l1;

}

for(i=0;i<2*LinesPerProcess;i+=2)

{

//считаем смещение для пересылки

for(j=0;j<size;j++)

{

DisplsX1[j] = NumberLinesX[i]*N;

DisplsX2[j] = NumberLinesX[i+1]*N;

}

//делаем пересылку пар строк

MPI_Barrier(MPI_COMM_WORLD);

MPI_Scatterv(Real, Counts,DisplsX1,MPI_FLOAT,LineX1Real, N,MPI_FLOAT,0,MPI_COMM_WORLD); MPI_Scatterv(Image,Counts,DisplsX1,MPI_FLOAT,LineX1Image,N,MPI_FLOAT,0,MPI_COMM_WORLD);

MPI_Scatterv(Real, Counts,DisplsX2,MPI_FLOAT,LineX2Real ,N,MPI_FLOAT,0,MPI_COMM_WORLD); MPI_Scatterv(Image,Counts,DisplsX2,MPI_FLOAT,LineX2Image,N,MPI_FLOAT,0,MPI_COMM_WORLD);

for(p2=0; p2<Nv; p2++)

for(l2=0; l2<dv; l2++) //y - Width

{

y1=l2+p2*dv2; y2=y1+dv;

Exe0_Real = LineX1Real[y1];

Exe0_Image = LineX1Image[y1];

index1 = (N/(2*dv))*ArrayL1[i];

Exe1_Real = Cos[index1]*LineX2Real[y1] - oper*Sin[index1]*LineX2Image[y1];

Exe1_Image = Cos[index1]*LineX2Image[y1] + oper*Sin[index1]*LineX2Real[y1];

index2 = (N/(2*dv))*l2

Exe2_Real = Cos[index2]*LineX1Real[y2] - oper*Sin[index2]*LineX1Image[y2];

Exe2_Image = Cos[index2]*LineX1Image[y2] + oper*Sin[index2]*LineX1Real[y2];

CosTemp = Cos[index1]*Cos[index2] - Sin[index1]*Sin[index2];

SinTemp = oper*(Sin[index1]*Cos[index2] + Cos[index1]*Sin[index2]);

Exe3_Real = CosTemp*LineX2Real[y2] - SinTemp*LineX2Image[y2];

Exe3_Image = CosTemp*LineX2Image[y2] + SinTemp*LineX2Real[y2];

X1_Real = Exe0_Real + Exe1_Real;

X1_Image = Exe0_Image + Exe1_Image;

X2_Real = Exe2_Real + Exe3_Real;

X2_Image = Exe2_Image + Exe3_Image;

LineX1Real[y1] = X1_Real + X2_Real;

LineX1Image[y1] = X1_Image + X2_Image;

LineX1Real[y2] = X1_Real - X2_Real;

LineX1Image[y2] = X1_Image - X2_Image;

X1_Real = Exe0_Real - Exe1_Real;

X1_Image = Exe0_Image - Exe1_Image;

X2_Real = Exe2_Real - Exe3_Real;

X2_Image = Exe2_Image - Exe3_Image;

LineX2Real[y1] = X1_Real + X2_Real;

LineX2Image[y1] = X1_Image + X2_Image;

LineX2Real[y2] = X1_Real - X2_Real;

LineX2Image[y2] = X1_Image - X2_Image;

}

//отсылаем обратно

MPI_Barrier(MPI_COMM_WORLD);

MPI_Gatherv(LineX1Real, N,MPI_FLOAT,Real, Counts,DisplsX1,MPI_FLOAT,0,MPI_COMM_WORLD); MPI_Gatherv(LineX1Image,N,MPI_FLOAT,Image,Counts,DisplsX1,MPI_FLOAT,0,MPI_COMM_WORLD);

MPI_Gatherv(LineX2Real, N,MPI_FLOAT,Real, Counts,DisplsX2,MPI_FLOAT,0,MPI_COMM_WORLD); MPI_Gatherv(LineX2Image,N,MPI_FLOAT,Image,Counts,DisplsX2,MPI_FLOAT,0,MPI_COMM_WORLD);

}

dv *= 2;

dv2 *= 2;

Nv /= 2;

}

float temp = (float)N;

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