2 Программная реализация
Полный код программы:
1 #include <iomanip>
2 #include <iostream>
3 #include <cmath>
4 #include <complex>
5 #include <time.h>
6 using namespace std;
7
8 #define PI (3.14159265358979323846)
9 // Функция для простой инициализации элементов входного сигнала
10 void DummyDataInitialization(complex<double>∗ mas, int size) {
11 for ( int i = 0; i < size ; i++)
12 mas[i] = 0;
13 mas[size − size / 4] = 1;
14 }
15
16 // Функция случайной инициализации элементов объектов
17 void RandomDataInitialization (complex<double>∗ mas, int size)
18 {
19 srand(unsigned(clock() ) ) ;
20 for ( int i = 0; i < size ; i++)
21 mas[i] = complex<double>(rand() / 1000.0, rand () / 1000.0);
22 }
23
24
25 // Функция выделения памяти и инициализации данных
26 void ProcessInitialization (complex<double>∗ &inputSignal,
27 complex<double>∗ &outputSignal, int &size) {
28 // Установка размера сигналов
29 do
30 {
31 cout << "Введите длину входного сигнала: ";
32 cin >> size ;
33 if ( size < 4)
34 cout << "Длина входного сигнала должна быть >= 4" << endl;
35 else
36 {
37 int tmpSize = size ;
38 while (tmpSize != 1)
39 {
40 if (tmpSize % 2 != 0)
41 {
42 cout << "Длина входного сигнала должна быть равна степени двойки" << endl;
43 size = −1;
44 |
|
break |
45 |
|
} |
46 |
|
tmpSize /= 2; |
47 |
} |
|
;
48 }
49 } while ( size < 4) ;
50 cout << "Длина входного сигнала = " << size << endl;
51 inputSignal = new complex<double>[size];
52 outputSignal = new complex<double>[size];
53
54 // Инициализация элементов входного сигнала−тесты
55 // DummyDataInitialization( inputSignal , size ) ;
56
57 // Вычислительные эксперименты
58 RandomDataInitialization ( inputSignal , size ) ;
59 }
60
61 // Функция для моделирования вычислительного процесса
62 void ProcessTermination (complex<double>∗ &inputSignal, complex<double>∗ &outputSignal) {
63 delete [] inputSignal ;
64 inputSignal = NULL;
65 delete [] outputSignal ;
66 outputSignal = NULL;
67 }
68
69 // функция для перестановки элементов массива с помощью бит−реверсирования
70 void SerialBitReversing (complex<double> ∗inputSignal, complex<double> ∗outputSignal, int
size ) {
71 int j = 0, i = 0;
72 while ( i < size )
73 {
74 if ( j > i )
75 {
76 outputSignal [ i ] = inputSignal [ j ];
77 outputSignal [ j ] = inputSignal [ i ];
78 }
79 else
80 if ( j == i )
81 outputSignal [ i ] = inputSignal [ i ];
82 int m = size >> 1;
83 while (( m >= 1) && (j >= m))
84 {
85 j −= m;
86 m = m >> 1;
87 }
88 j += m;
89 i++;
90 }
91 }
92
93 // параллельная версия
94 void ParallelBitReversing (complex<double> ∗inputSignal, complex<double> ∗outputSignal,
int size ) {
95 int j = 0, i = 0;
96 #pragma parallel
97 while ( i < size ){
98 if ( j > i ){
99 outputSignal [ i ] = inputSignal [ j ];
100 outputSignal [ j ] = inputSignal [ i ];
101 }
102 else if ( j == i )
103 outputSignal [ i ] = inputSignal [ i ];
104 int m = size >> 1;
105 while (( m >= 1) && (j >= m)){
106 j −= m;
107 m = m >> 1;
108 }
109 j += m;
110 i++;
111 }
112 }
113
114 inline void Butterfly (complex<double> ∗signal, complex<double> u, int offset , int
butterflySize ) {
115 complex<double> tem = signal[ offset + butterflySize ] ∗ u;
116 signal [ offset + butterflySize ] = signal [ offset ] − tem;
117 signal [ offset ] += tem;
118 }
119
120 void SerialFFTCalculation (complex<double> ∗signal, int size ) {
121 int m = 0;
122 for ( int tmp_size = size ; tmp_size > 1; tmp_size /= 2, m++);
123 for ( int p = 0; p < m; p++)
124 {
125 int butterflyOffset = 1 << (p + 1) ;
126 int butterflySize = butterflyOffset >> 1;
127 double coeff = PI / butterflySize ;
128 for ( int i = 0; i < size / butterflyOffset ; i++)
129 for ( int j = 0; j < butterflySize ; j++)
130 Butterfly ( signal , complex<double>(cos(−j ∗ coeff),
131 sin(−j ∗ coeff ) ) , j + i ∗ butterflyOffset , butterflySize ) ;
132 }
133 }
134
135 void ParallelFFTCalculation (complex<double> ∗signal, int size ) {
136 int m = 0;
137 #pragma parallel for
138 for ( int tmp_size = size ; tmp_size > 1; tmp_size /= 2, m++);
139 #pragma parallel for
140 for ( int p = 0; p < m; p++)
141 {
142 int butterflyOffset = 1 << (p + 1) ;
143 int butterflySize = butterflyOffset >> 1;
144 double coeff = PI / butterflySize ;
145 for ( int i = 0; i < size / butterflyOffset ; i++)
146 for ( int j = 0; j < butterflySize ; j++)
147 Butterfly ( signal , complex<double>(cos(−j ∗ coeff), sin(−j
∗ coeff ) ) , j + i ∗ butterflyOffset , butterflySize ) ;
148 }
149 }
150 // Вычисление БПФ − быстрого преобразования Фурье
151 void SerialFFT(complex<double> ∗inputSignal, complex<double> ∗outputSignal, int size ) {
152 SerialBitReversing ( inputSignal , outputSignal , size ) ;
153 SerialFFTCalculation ( outputSignal , size ) ;
154 }
155
156 // параллельная версия вычислений БПФ
157 void ParallelFFT (complex<double> ∗inputSignal, complex<double> ∗outputSignal, int size ) {
158 #pragma parallel for
159 ParallelBitReversing ( inputSignal , outputSignal , size ) ;
160 #pragma parallel for
161 ParallelFFTCalculation ( outputSignal , size ) ;
162 }
163
164 // печать результата
165 void PrintSignal (complex<double> ∗signal, int size ) {
166 cout << "Result signal " << endl;
167 for ( int i = 0; i < size ; i++)
168 cout << signal [ i ] << endl;
169 }
170
171 void TestResult (complex<double> ∗inputSignal, complex<double> ∗outputSignal, int size ) // тестовая функция для проверки правильности ответа
172 {
173 // Буфер для хранения результата последовательного БПФ
174 complex<double> ∗ testSerialSignal ;
175 double Accuracy = 1.e−6; // Точность сравнения
176 // Флаг, который показывает, идентичны ли векторы
177 int equal = 0;
178 int i ; // Loop variable
179 testSerialSignal = new complex<double>[size];
180 SerialFFT( inputSignal , testSerialSignal , size ) ;
181 for ( i = 0; i<size ; i++)
182 {
183 if (abs( outputSignal [ i ] − testSerialSignal [ i ]) >= Accuracy)
184 equal = 1;
185 }
186 if ( equal == 1)
187 printf ("The results of serial and parallel algorithms are NOT identical . Check your code.") ;
188 else
189 printf ("The results of serial and parallel algorithms are identical . ") ;
190 delete [] testSerialSignal ;
191 }
192 |
|
|
193 |
int main() { |
|
194 |
|
setlocale (LC_ALL, "RUS"); |
195 |
|
complex<double> ∗ inputSignal = NULL; |
196 |
complex<double> ∗ outputSignal = NULL; |
197 |
int size = 0; |
198 |
|
199 |
const int repeatCount = 16; |
200 |
double startTime ; |
201 |
double duration ; |
202 |
double minDuration = DBL_MAX; |
203 |
|
204 |
cout << "Fast Fourier Transform" << endl; |
205 |
// Выделение памяти и инициализация данных |
206 |
ProcessInitialization ( inputSignal , outputSignal , size ) ; |
207 |
for ( int i = 0; i < repeatCount; i++) |
208 |
{ |
209 |
startTime = clock () ; |
210 |
// Вычисление БПФ |
211 // SerialFFT( inputSignal , outputSignal , size ) ;// последовательный алгоритм
212 ParallelFFT ( inputSignal , outputSignal , size ) ; // параллельный
213 duration = ( clock () − startTime) / CLOCKS_PER_SEC;
214 if ( duration < minDuration)
215 minDuration = duration ;
216 }
217 cout << setprecision (6) ;
218 cout << "Execution time is " << minDuration << " s . " << endl;
219 // печать результата
220 // PrintSignal ( outputSignal , size ) ;
221 // Завершение вычислительного процесса
222 ProcessTermination ( inputSignal , outputSignal ) ;
223 system("pause") ;
224 return 0;
225 }
Заполним таблицу:
-
Номер теста
Размер входного
сигнала
Мин. время работы последовательного
приложения (сек)
Мин. время работы параллельного
приложения (сек)
Ускорение
1
32768
0.194
0.095
2.042
2
65536
0.415
0.189
2.196
3
131072
0.880
0.445
1.978
4
262144
1.869
0.914
2.045
5
524288
3.970
1.953
2.033
Очевидно, что параллельная версия выигрывает по времени у последо-
вательной примерно в 2 раза.