5. Дискретное преобразование Фурье и его параллельная реализация.

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

Основная проблема вычисления ДПФ - это уменьшение времени обработки.

Чтобы это осуществить, для базовых алгоритмов ДПФ в форме алгоритмов БПФ оказывается естественным использовать параллелизм, присущий этим алгоритмам, и, тем самым, предложить два пути его использования:

1. применение однородной распределённой вычислительной сети.

2. построение специализированного вычислителя.

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

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

5.1. Основные соотношения и алгоритмы ДПФ.

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

k=(0,n-1)

где n - число точек ;

- комплексное число , а - вещественная и мнимая части соответственно

- комплексная экспонента

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

Вычислительные графы обоих методов при n=16 приведены на рис.5.1 Из приведенных графов отчетливо просматриваются стадий вычислений.

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

а

Рис.5.1

лгоритмам БПФ присуще свойство параллельности в различных представлениях.

Формульное описание алгоритмов БПФ можно найти в различных источниках.

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

5

.2. Алгоритмы ДПФ для однородных распределённых вычислительных структур.

Гиперкубы различной размерности.

Параллельная реализация ДПФ далеко продвинута для числа точек n=2^m применительно к однородным распределённым вычислительным структурам, содержащим p процессоров, соединенных в r - мерный бинарный гиперкуб и максимальное рассояние равно log₂p

В таком r - мерном гиперкубе содержится p=2^r процессоров (размерность гиперкуба определяется числом линков у процессора); каждый процессор соответствует вершине куба и бинарные номера соседних вершин отличаются только на один бит. На рис.5.2 приведены примеры гиперкубов.

Покажем организацию вычислений для двух схем алгоритмов.

Вариант 1 (рис.5.1)

П

Рис. 5.3

оложим , где целое число. Входные данные на алгоритм поступают в прямом битовом порядке, выходные данные , т.е. результат преобразования, получаются в обратном битовом порядке. Примем для определенности n=16 и p=4 , q=4. Тогда в рассматриваемом варианте БПФ имеет следующую схему выполнения в параллельном режиме (рис.5.3)

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

Фаза начального распределения данных разделяет исходный вектор входных данных последовательно на групп с номерами из q/2 комплексных чисел каждая и присваивает i-му процессору группы i и (i+p) . Тем самым каждому i-му процессору передается свой вектор данных, содержащий элемент входной последовательности и , 0i<p, 0k< .

На стадиях расчета выполняются комплексные вычисления над данными, однотипные для всех процессоров, в соответствии с графом (рис 5.1,5.3). Элементарный граф также приведен на этом же рис 5.1,5.3. Вычисления каждой стадии на всех процессорах выполняются параллельно. Однако в определенные моменты времени процессоры должны обмениваться данными, чтобы существовал непрерывный процесс вычислений.

В конце первых r стадий расчета, где r - размерность гиперкуба процессоры обмениваются данными: q/2 комплексных чисел посылаются от каждого процессора и q/2 принимаются каждым процессором. Выбор процессора, которому пересылаются данные основывается на анализе бинарного представления их номеров; каждый номер содержит r бинарных разрядов. Старший бит соответствует 1-ой стадии, и т.д. , а младший бит соответствует r-ой заключительной стадии. Анализ битов выполняется, начиная со старшего.

Если i-ый бит в номере процессора равен 0 , то q/2 последовательно расположенных комплексных чисел в нижней группе данных посылается к процессору, у которого i-ый бит равен 1.

Иначе q/2 последовательно расположенных комплексных чисел в верхней группе данных посылается к процессору, у которого i-ый бит равен 0.

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

После заключительной стадии расчета результаты работы каждого i-ого процессора содержат q комплексных чисел в последовательном порядке, т.е. имеющих номера i*q+k, 0<i<p, 0<k<q.

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

В

Рис.5.4

ариант 2 (рис.5.1). В силу большой схожести с предыдущем вариантом подчеркнем только принципиальные отличия, что наглядно проявляется на рис.5.4 при n=16, p=4, q=4.

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

Межпроцессорные обмены осуществляются на последних стадиях.

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

На фазе сбора все результаты просто объединяются в один вектор обычным линейным переносом.

Между двумя основными вариантами 1 и 2 существует и ряд промежуточных [9] , которые отличаются от основных способов сбора и распределения данных, способом вычисления комплексной экспоненты¸ порядком следования операции на стадии. Это делается на предмет получения большего быстродействия.

Вычисление комплексной экспоненты - один из характерных моментов в работе алгоритмов. С тем, чтобы не вычислять каждый раз значения тригонометрических функций sin и cos , используют предварительно вычисленную таблицу n-значений функции sin и обращения к ней. Так как экономия памяти всегда является предметом заботы , то чаще всего ограничиваются не полноразмерной sin-функций, а её меньшем размером, обычно n/4.

В качестве примера рассмотрим параллельную реализацию алгоритма БПФ вариант 1 (приводится в работе [9]). В таблице 1 приведены данные по абсолютным временам расчета для одного(fft1_c), двух(dis_dif (vers 1;p=2)) и трех(dis_dif (vers 1;p=4)) процессоров.

Таблица 1

Программа	Число точек
	64	128	256	512	1k	2k	4k	8k
fft1_c	0.095	0.21	0.467	1.03	2.259	9.181	19.994	43.26
dis_dif (vers 1;p=2)	0.071	0.145	0.305	0.651	1.394	2.981	---	---
dis_dif (vers 1;p=4)	0.055	0.101	0.197	0.413	0.859	1.76	3.705	---

На рис.5.5 приведены данные, характеризующие ускорение, получаемое при использовании параллельного алгоритма в функции числа точек. Под ускорением понимают отношение времени расчета при использовании одного процесса (fft1_c) и нескольких процессоров р=2 (dis_dif (vers 1;p=2)) и р=4 (dis_dif (vers 1;p=4)).

Р

ис.5.5

Рис5.6

На рис.5.6 приведена эффективность параллельного алгоритма, как отношение ускорения к числу процессоров, в функции числа точек.

Литература.

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х томах. Т.1 Синтаксический анализ - М.: Мир, 1978.- 612 с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979.- 536 с.

3. G. W. Irwin, P. J. Fleming Real-Time Control Application of Transputers. Transputer Applications - Progress and Prospects. Procuding of the Closing Symposium of the SERC/DTI Initiative in the Engineering Application of Transputers. Edited by M.R.Jane, R.J.Fawcett and T.P.Mawby p.26-39.

4. Ершов Н.М. Математические модели и методы обработки информации многопроцессорными вычислительными системами. Диссертация на соискание учёной степени кандидата технических наук. МГУ им. М.В.Ломоносова. М., 1994. 73 с.

5. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику. М.; Наука, 1990

6. Пупков К.А., Карпенко А.П. Моделирование динамических систем на транспьютерных сетях. - М., Биоинформ, 1995. - 73 с.

7. J.P.E.Sunter, E.C.Koenders, A.W.P.Bakkers Post-Game Analysis on Transputers. Proceedings of Transputing ’91, p.330-341.

8. Пупков К.А., Дудоладов В.А., Карпенко А.П. Исследование эффективности динамической балансировки загрузки многопроцессорных систем методами теории автоматического регулирования: Методические указания к лабораторным работам. - М.: МГТУ,1996.-19 с.

9. Parallel 1-D FFT Implementation With TMS320C4x DSPs . Application Report. Rose Marie Piedra. Digital Signal Processing – Semiconductor Group, SPRA 108, February 1994. Texas Instruments.

10. Воеводин В.В. Математические модели и методы в параллельных процессах. - М., Наука 1986

69