Участник:Vagabond/Алгоритм быстрого дискретного пребразования Фурье - История изменений

Kronberg в 14:20, 29 ноября 2016

2016-11-29T14:20:56Z

← Предыдущая версия		Версия от 14:20, 29 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|IgorS}}		{{Assignment\|IgorS\|Kronberg}}
	'''Автор''': Данилишин А.Р.		'''Автор''': Данилишин А.Р.
	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =

IgorS в 09:36, 21 ноября 2016

2016-11-21T09:36:25Z

← Предыдущая версия		Версия от 09:36, 21 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|IgorS}}
	'''Автор''': Данилишин А.Р.		'''Автор''': Данилишин А.Р.
	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =

Vagabond в 19:15, 19 ноября 2016

2016-11-19T19:15:23Z

@@ Строка 1: / Строка 1: @@
+{{Assignment}}
 '''Автор''': Данилишин А.Р.
 = ЧАСТЬ. Свойства и структура алгоритмов =
@@ Строка 231: / Строка 231: @@
 == Возможные способы и особенности параллельной реализации алгоритма ==
 == Масштабируемость алгоритма и его реализации ==
 [[file:масш.jpg|center|thumb|1000px|Рисунок 3. Параллельная реализация алгоритма. Изменение эффективности(%)в зависимости от числа процессоров и размера области.]]
-Как описывалось выше, каждый процессор получает достаточно низкий объем работы, что приводит к неэффективному распараллеливанию алгоритма (высокие затраты на передачу данных между процессорами по сравнению с вычислениями на них). Поэтому необходимо находить оптимальное количество процессоров для каждой отдельно взятой задачи. В данном примере, при размерности входного сигнала менее 262144, оптимальное количество процессоров составляет 1. При размерности 262144-4194304 оптимум достигался при 8 процессорах. И при размерности более 4194304- 16 процессоров. Вычисления проводились на суперкомпьютере «Ломоносов».
+Как описывалось выше, каждый процессор получает достаточно низкий объем работы, что приводит к неэффективному распараллеливанию алгоритма (высокие затраты на передачу данных между процессорами по сравнению с вычислениями на них). Поэтому необходимо находить оптимальное количество процессоров для каждой отдельно взятой задачи. В данном примере, при размерности входного сигнала менее 262144, оптимальное количество процессоров составляет 1. При размерности 262144-4194304 оптимум достигался при 8 процессорах. И при размерности более 4194304- 16 процессоров.
 == Динамические характеристики и эффективность реализации алгоритма ==
 == Выводы для классов архитектур ==

IgorS в 11:38, 18 ноября 2016

2016-11-18T11:38:44Z

← Предыдущая версия		Версия от 11:38, 18 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|IgorS}}~~
	'''Автор''': Данилишин А.Р.		'''Автор''': Данилишин А.Р.
	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =

IgorS в 10:58, 17 ноября 2016

2016-11-17T10:58:33Z

← Предыдущая версия		Версия от 10:58, 17 ноября 2016
Строка 1:		Строка 1:
			{{Assignment\|IgorS}}
	'''Автор''': Данилишин А.Р.		'''Автор''': Данилишин А.Р.
	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =

Vagabond в 12:57, 16 ноября 2016

2016-11-16T12:57:05Z

← Предыдущая версия		Версия от 12:57, 16 ноября 2016
Строка 4:		Строка 4:

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
			Пусть <math>X=(x_{1},...,x_{n-1})^{T}</math> - исходный сигнал, который необходимо преобразовать умножением на тензор второго ранга <math>E_{pk}=e^{\frac{-2kpi\pi}{n}} </math>. Результатом данного преобразования (<math>E*X</math>) будет вектор <math>Y=(y_{1},...,y_{n-1})^{T}</math>, где <math> y_{p}=\sum_{k=0}^{n-1}x_{k}e^{\frac{-2kpi\pi}{n}}, p=\overline{0,n-1}</math>. Данная формула является классической формулой ДПФ. Известно, что в общем случае умножение матрицы на вектор требует <math>O(n^{2})</math> арифметических операций, поэтому возникает вопрос о сокращении данного количества.

	Главная идея БПФ состоит в сокращении многочисленных повторов сложения и умножения, которые выполняются в ДПФ (повторяющиеся множители: <math>e^{\frac{-2kpi\pi}{n}}</math> Например при условии, что <math>(pk)mod(n)=const</math>, при всех <math>k=\overline{0,n-1}</math> и <math>p=\overline{0,n-1}</math>		Главная идея БПФ состоит в сокращении многочисленных повторов сложения и умножения, которые выполняются в ДПФ (повторяющиеся множители: <math>e^{\frac{-2kpi\pi}{n}}</math> Например при условии, что <math>(pk)mod(n)=const</math>, при всех <math>k=\overline{0,n-1}</math> и <math>p=\overline{0,n-1}</math>

	~~Напомним формулу ДПФ:~~		За счет использования данного факта, происходит значительное сокращение количества вычислительных операций. В данной статье используется алгоритм Cooley – Tukey, который предполагает собой разбиение исходного множества входных сигналов на два равных подмножества. При этом множество входных сигналов должно быть степенью двойки. Далее операция деления множества продолжается для образовавшихся подмножеств, и так далее. В результате над каждым из полученных подмножеств выполняется БПФ. Данные вычисления можно выполнять независимо друг от друга. Этот факт используется для реализации параллельной версии алгоритма.

	~~<math> y_{p}~~=~~\sum_{k~~=~~0}^{n-1}x_{k}e^{\frac{-2kpi\pi}{n}}, p~~=~~\overline{0,n-1}</math>~~		== Математическое описание алгоритма ==

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

	* Преобразование входного массива данных (бит-реверсирование).
	* Вычисление БПФ.
	~~Приведем более детальное описание БПФ (математическое описание):~~
	*Пусть <math>e^{\frac{-2kpi\pi}{n}}</math> = <math>\omega _{n}^{kp}</math>.		*Пусть <math>e^{\frac{-2kpi\pi}{n}}</math> = <math>\omega _{n}^{kp}</math>.
	*Разобьем исходный сигнал <math>x(n)</math> на два подмножества, с четными <math>x_{1}(2n)</math> и нечетными <math>x_{2}(2n+1)</math> номерами.		*Разобьем исходный сигнал <math>x(n)</math> на два подмножества, с четными <math>x_{1}(2n)</math> и нечетными <math>x_{2}(2n+1)</math> номерами.
Строка 29:		Строка 25:
	Так как: <math>\omega_{\frac{n}{2}}^{\frac{kn}{2}}=e^{\frac{-4kni\pi}{2n}}=e^{-2ki\pi}=1</math>		Так как: <math>\omega_{\frac{n}{2}}^{\frac{kn}{2}}=e^{\frac{-4kni\pi}{2n}}=e^{-2ki\pi}=1</math>

	Далее необходимо определить <math>y(p)</math> при <math>p\geq \frac{n}{2}</math>. Теперь воспользуемся свойством периодичности обнаруженными нами ранее: <math>y(p+\frac{n}{2})=y_{1}(p+\frac{n}{2})+\omega_{n}^{(p+\frac{n}{2})}y_{2}(p+\frac{n}{2})</math>. Воспользуемся вторым свойством омеги: <math>y(p)=y_{1}(p)-\omega_{n}^{p}y_{2}(p)</math>.		Далее необходимо определить <math>y(p)</math> при <math>p\geq \frac{n}{2}</math>. Теперь воспользуемся свойством периодичности обнаруженными нами ранее: <math>y(p+\frac{n}{2})=y_{1}(p+\frac{n}{2})+\omega_{n}^{(p+\frac{n}{2})}y_{2}(p+\frac{n}{2})</math>. Воспользуемся вторым свойством омеги: <math>y(p)=y_{1}(p)-\omega_{n}^{p}y_{2}(p)</math>. Все выкладки, приведенные выше, относятся ко второму этапу алгоритма Cooley – Tukey, который был использован в данной статье. Последующие шаги данного этапа делят подмножества полученные на предыдущем шаге вычисления БПФ.

	В конечном итоге ~~мы пришли~~ к конечной формуле для первого этапа вычисления БПФ. Дальнейшие этапы делят подмножества полученные на предыдущим этапе вычисления БПФ.		В конечном итоге вышеупомянутый алгоритм сводится к двум этапам:

	~~== Математическое описание алгоритма ==~~

	'''Бит-реверсирование'''		'''Бит-реверсирование'''
Строка 41:		Строка 35:
	'''Вычисление БПФ'''		'''Вычисление БПФ'''

	После выполнения этапа бит-реверсирования выполняются вычисления проиллюстрированные ''на рисунке 2'' в разделе [[#Информационный граф\|Информационный граф]]. Рисунок 2 приведен для случая четырехмерного входного сигнала. Он предполагает совершение двух этапов. В общем же количество этапов равно <math>log_{2}n</math>. Каждый этап содержит в себе вычисление одной и той же операции "бабочки", где на вход подаются два числа <math>a</math> и <math>b</math>, на выходе же получаются <math>a+bU</math> и <math>a-bU</math>, где <math>U</math>- это ''коэффициент поворота''. Общая формула для коэффициента поворота: <math>e^{\frac{-ji\pi}{k}}</math>, где <math>k</math>- размер шага "бабочки", <math>j</math>- номер итерации вычислений над группой элементов, размером <math>2k</math> <math>(0\leq j < k )</math>.		После выполнения этапа бит-реверсирования выполняются вычисления проиллюстрированные ''на рисунке 1'' в разделе [[#Информационный граф\|Информационный граф]]. Рисунок 1 приведен для случая четырехмерного входного сигнала. Он предполагает совершение двух этапов. В общем же количество этапов равно <math>log_{2}n</math>. Каждый этап содержит в себе вычисление одной и той же операции "бабочки", где на вход подаются два числа <math>a</math> и <math>b</math>, на выходе же получаются <math>a+bU</math> и <math>a-bU</math>, где <math>U</math>- это ''коэффициент поворота''. Общая формула для коэффициента поворота: <math>e^{\frac{-ji\pi}{k}}</math>, где <math>k</math>- размер шага "бабочки", <math>j</math>- номер итерации вычислений над группой элементов, размером <math>2k</math> <math>(0\leq j < k )</math>.


	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==
Строка 54:		Строка 49:
	*<math>n</math> комплексных сложений		*<math>n</math> комплексных сложений
	*снова преобразование Фурье		*снова преобразование Фурье
			Также необходимо заметить, что количеством рекурсий будет количество этапов выполнения БПФ, то есть глубина рекурсии будет равняться <math>log_{2}n</math>

	== Схема реализации последовательного алгоритма ==		== Схема реализации последовательного алгоритма ==
Строка 237:		Строка 233:
	[[file:масш.jpg\|center\|thumb\|1000px\|Рисунок 3. Параллельная реализация алгоритма. Изменение эффективности(%)в зависимости от числа процессоров и размера области.]]		[[file:масш.jpg\|center\|thumb\|1000px\|Рисунок 3. Параллельная реализация алгоритма. Изменение эффективности(%)в зависимости от числа процессоров и размера области.]]
	Как описывалось выше, каждый процессор получает достаточно низкий объем работы, что приводит к неэффективному распараллеливанию алгоритма (высокие затраты на передачу данных между процессорами по сравнению с вычислениями на них). Поэтому необходимо находить оптимальное количество процессоров для каждой отдельно взятой задачи. В данном примере, при размерности входного сигнала менее 262144, оптимальное количество процессоров составляет 1. При размерности 262144-4194304 оптимум достигался при 8 процессорах. И при размерности более 4194304- 16 процессоров. Вычисления проводились на суперкомпьютере «Ломоносов».		Как описывалось выше, каждый процессор получает достаточно низкий объем работы, что приводит к неэффективному распараллеливанию алгоритма (высокие затраты на передачу данных между процессорами по сравнению с вычислениями на них). Поэтому необходимо находить оптимальное количество процессоров для каждой отдельно взятой задачи. В данном примере, при размерности входного сигнала менее 262144, оптимальное количество процессоров составляет 1. При размерности 262144-4194304 оптимум достигался при 8 процессорах. И при размерности более 4194304- 16 процессоров. Вычисления проводились на суперкомпьютере «Ломоносов».
			Код исследуемой программы представлен в разделе [[#Существующие реализации алгоритма\|Существующие реализации алгоритма]]
	== Динамические характеристики и эффективность реализации алгоритма ==		== Динамические характеристики и эффективность реализации алгоритма ==
	== Выводы для классов архитектур ==		== Выводы для классов архитектур ==

IgorS в 10:51, 16 ноября 2016

2016-11-16T10:51:27Z

← Предыдущая версия		Версия от 10:51, 16 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|IgorS}}~~
	'''Автор''': Данилишин А.Р.		'''Автор''': Данилишин А.Р.
	= ЧАСТЬ. Свойства и структура алгоритмов =		= ЧАСТЬ. Свойства и структура алгоритмов =

Kronberg: /* Математическое описание алгоритма */

2016-11-11T11:07:28Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 11:07, 11 ноября 2016
Строка 41:		Строка 41:
	'''Вычисление БПФ'''		'''Вычисление БПФ'''

	После выполнения этапа бит-реверсирования выполняются вычисления проиллюстрированные ''на рисунке 2'' в разделе [[#Информационный граф\|Информационный граф]]. Рисунок 2 приведен для случая четырехмерного входного сигнала. Он предполагает совершение двух этапов. В общем же количество этапов равно <math>log_{2}n</math>. Каждый этап содержит в себе вычисление одной и той же операции "бабочки", где на вход подаются два числа <math>a</math> и <math>b</math>, на выходе же получаются <math>a+bU</math> и <math>a-bU</math>, где <math>U</math>- это ''коэффициент поворота''. Общая формула для коэффициента поворота: <math>e^{\frac{-ji\pi}{k}}</math>~~. Где~~ <math>k</math>- размер шага "бабочки", <math>j</math>- номер итерации вычислений над группой элементов, размером <math>2k</math> <math>(0\leq j < k )</math>.		После выполнения этапа бит-реверсирования выполняются вычисления проиллюстрированные ''на рисунке 2'' в разделе [[#Информационный граф\|Информационный граф]]. Рисунок 2 приведен для случая четырехмерного входного сигнала. Он предполагает совершение двух этапов. В общем же количество этапов равно <math>log_{2}n</math>. Каждый этап содержит в себе вычисление одной и той же операции "бабочки", где на вход подаются два числа <math>a</math> и <math>b</math>, на выходе же получаются <math>a+bU</math> и <math>a-bU</math>, где <math>U</math>- это ''коэффициент поворота''. Общая формула для коэффициента поворота: <math>e^{\frac{-ji\pi}{k}}</math>, где <math>k</math>- размер шага "бабочки", <math>j</math>- номер итерации вычислений над группой элементов, размером <math>2k</math> <math>(0\leq j < k )</math>.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

Kronberg: /* Математическое описание алгоритма */

2016-11-11T11:07:00Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 11:07, 11 ноября 2016
Строка 41:		Строка 41:
	'''Вычисление БПФ'''		'''Вычисление БПФ'''

	После выполнения этапа бит-реверсирования выполняются вычисления проиллюстрированные ''на рисунке 2'' в разделе [[#Информационный граф\|Информационный граф]]. Рисунок 2 приведен для случая четырехмерного входного сигнала. Он предполагает совершение двух этапов. В общем же количество этапов равно <math>log_{2}n</math>. Каждый этап содержит в себе вычисление одной и той же операции "бабочки", где на вход подаются два числа <math>a</math> и <math>b</math>, на выходе же получаются <math>a+bU</math> и <math>a-bU</math>~~. Где~~ <math>U</math>- это ''коэффициент поворота''. Общая формула для коэффициента поворота: <math>e^{\frac{-ji\pi}{k}}</math>. Где <math>k</math>- размер шага "бабочки", <math>j</math>- номер итерации вычислений над группой элементов, размером <math>2k</math> <math>(0\leq j < k )</math>.		После выполнения этапа бит-реверсирования выполняются вычисления проиллюстрированные ''на рисунке 2'' в разделе [[#Информационный граф\|Информационный граф]]. Рисунок 2 приведен для случая четырехмерного входного сигнала. Он предполагает совершение двух этапов. В общем же количество этапов равно <math>log_{2}n</math>. Каждый этап содержит в себе вычисление одной и той же операции "бабочки", где на вход подаются два числа <math>a</math> и <math>b</math>, на выходе же получаются <math>a+bU</math> и <math>a-bU</math>, где <math>U</math>- это ''коэффициент поворота''. Общая формула для коэффициента поворота: <math>e^{\frac{-ji\pi}{k}}</math>. Где <math>k</math>- размер шага "бабочки", <math>j</math>- номер итерации вычислений над группой элементов, размером <math>2k</math> <math>(0\leq j < k )</math>.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

Kronberg: /* Математическое описание алгоритма */

2016-11-11T11:06:35Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 11:06, 11 ноября 2016
Строка 41:		Строка 41:
	'''Вычисление БПФ'''		'''Вычисление БПФ'''

	После выполнения этапа бит-реверсирования выполняются вычисления проиллюстрированные ''на рисунке 2'' в разделе [[#Информационный граф\|Информационный граф]]. Рисунок 2 приведен для случая четырехмерного входного сигнала. Он предполагает совершение двух этапов. В общем же количество этапов равно <math>log_{2}n</math>. Каждый этап содержит в себе вычисление одной и той же операции "бабочки"~~. Где~~ на вход подаются два числа <math>a</math> и <math>b</math>, на выходе же получаются <math>a+bU</math> и <math>a-bU</math>. Где <math>U</math>- это ''коэффициент поворота''. Общая формула для коэффициента поворота: <math>e^{\frac{-ji\pi}{k}}</math>. Где <math>k</math>- размер шага "бабочки", <math>j</math>- номер итерации вычислений над группой элементов, размером <math>2k</math> <math>(0\leq j < k )</math>.		После выполнения этапа бит-реверсирования выполняются вычисления проиллюстрированные ''на рисунке 2'' в разделе [[#Информационный граф\|Информационный граф]]. Рисунок 2 приведен для случая четырехмерного входного сигнала. Он предполагает совершение двух этапов. В общем же количество этапов равно <math>log_{2}n</math>. Каждый этап содержит в себе вычисление одной и той же операции "бабочки", где на вход подаются два числа <math>a</math> и <math>b</math>, на выходе же получаются <math>a+bU</math> и <math>a-bU</math>. Где <math>U</math>- это ''коэффициент поворота''. Общая формула для коэффициента поворота: <math>e^{\frac{-ji\pi}{k}}</math>. Где <math>k</math>- размер шага "бабочки", <math>j</math>- номер итерации вычислений над группой элементов, размером <math>2k</math> <math>(0\leq j < k )</math>.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==