并行计算提升32K*32K点(32位浮点数) FFT计算速度(4核八线程E3处理器)

时间:2024-08-03 22:33:50

  对32K*32K的随机数矩阵进行FFT变换,数的格式是32位浮点数。将产生的数据存放在堆上,对每一行数据进行N=32K的FFT,记录32K次fft的时间。

比较串行for循环和并行for循环的运行时间。

//并行计算
//调用openmp,通过g++ -fopenmp test.cpp -o out 编译程序
#pragma omp parallel for
for(int i=;i<LEN;i++)
fft(num[i],LEN,);

最终的运行时间:247,844,013 us

而串行fft,不调用openmp,它的运行时间为: 779,387,651 us

测试了,将32k*32k float型矩阵存储在堆上和栈上,并对比运行时间: 几乎没有区别。

查阅资料:栈的大小为1M, 大数组应该放在堆上,或者通过定义成全局变量/静态变量放在静态存储区。

fft算法:(该fft算法,不适合并行化处理,将来会寻找能够进行并行化的fft算法,继续改进)

void fft(complex<float> *x, int n, int inv)
{
complex<float> u, w, t, tt;
int m, nv2, nm1, l, le1, le, i, j, k, ip;
m = int(log(double(n)) / log(2.) + 0.5);
nv2 = n / 2;
nm1 = n - 1;
j = 0;
for (i = 0; i<nm1; i++)
{
if (i >= j) goto a;
tt = x[j];
x[j] = x[i];
x[i] = tt; a: k = nv2; b:
if (k>j) goto c;
j = j - k;
k = k / 2;
goto b; c: j = j + k;
}
for (l = 1; l <= m; l++){
le = int(pow(2.0, double(l)));
le1 = le / 2;
u = complex<float>(1.0 , 0.0);
w = complex<float>((float)cos(pi / le1), -(float)sin(pi / le1));
if (inv != 0) w = conj(w);
for (j = 0; j<le1; j++){
for (i = j; i<n; i = le + i){
ip = i + le1;
t = x[ip] * u;
x[ip] = x[i] - t;
x[i] = x[i] + t;
}
u = u*w;
}
}
if (inv != 0) {
for (i = 0; i<n; i++){
x[i] = x[i] / float(n);
}
}
}