algorithm - 线程构建 block 中嵌套循环的并行化

标签 algorithm loops nested fft tbb

我不熟悉线程构建 block 并尝试在 TBB 中对 FFT 算法进行编码以获得一些实践经验。在这种算法的情况下,我只能并行化最内层的循环。但是通过这样做,性能已经下降到 Not Acceptable 程度(超过一千次)。我试过数组大小最大为 2^20 但结果相同。我的代码在下面给出

for(stage1=0;stage1 < lim;stage1 ++)
{
    butterfly_index1 = butterfly_index2;
    butterfly_index2 = butterfly_index2 + butterfly_index2; 
    k = -1*2*PI/butterfly_index2;
    k_next = 0.0;
    for(stage2 = 0 ; stage2 < butterfly_index1;stage2++)
    {
        sine=sin(k_next);
        cosine = cos(k_next);
        k_next = k_next + k;
        FFT. sine = &sine;
        FFT.cosine = &cosine;
        FFT.n2 = &butterfly_index2;
        FFT.loop_init = &stage2;
        FFT.n1 = &butterfly_index1;
        parallel_for(blocked_range<int>(
                        stage2,SIZE,SIZE/4),FFT,simple_partitioner()); 
    }
}   

parallel_loop 的主体是

void operator()(const blocked_range<int> &r)const
{
    for(int k = r.begin(); k != r.end(); k++)
    {   
        if(k != *loop_init)
        {
            if((k - (*loop_init))% (* n2)!= 0)
                continue;
        }           
        temp_real = (*cosine) * X[k + *n1].real - (*sine) * X[k + *n1].img;
        temp_img = (*sine)* X[k + *n1].real + (*cosine) * X[k + *n1].img;
        X[k + *n1].real = X[k].real - temp_real;
        X[k + *n1].img = X[k].img - temp_img;
        X[k].real = X[k].real + temp_real;
        X[k].img = X[k].img + temp_img; 
    }
}

如果我用普通循环替换它,那么一切都是正确的。

最佳答案

对于非常短的工作负载,由于线程创建的开销,可能会发生巨大的减速。对于数组中的 2^20 个元素,我认为不会发生如此巨大的性能下降。

性能下降的另一个重要来源是编译器无法在 TBBfied 后优化(特别是矢量化)代码。查看您的编译器是否可以生成矢量化报告,并查找串行版本和 TBB 版本之间的差异。

减速的一个可能来源可能是 parallel_for 主体类的复制构造函数,因为主体被大量复制。但是给定的代码在这方面看起来并不可疑:似乎主体包含一些指针。无论如何,看看它是否有问题。


另一个常见的重大开销来源是太细粒度的并行性,即许多任务每个包含很少的工作。但这里也不是这种情况,因为 blocked_range 的第三个参数中的 grainsize SIZE/4 指定 body 的 operator()() 将根据算法最多调用 4 次。

我建议不要为初始实验指定 simple_partitioner 和 grainsize,而是让 TBB 动态分配工作。如有必要,您可以稍后对其进行调整。

关于algorithm - 线程构建 block 中嵌套循环的并行化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5521954/

相关文章:

r - 如何展平从 jsonlite 返回的嵌套数据帧

javascript - 如何使用 javascript 在嵌套对象中的特定位置添加子节点

ruby - Ruby中压缩给定字符串问题

c++ - 快速等效于 STK 中引用的 DSP 的 sin()

c - 结束这个 while 循环我做错了什么

arrays - 如何在动态数组中使用 OData 过滤器

algorithm - 如何计算 32 位整数中设置的位数?

algorithm - 检查一个值是否属于哈希

c - 用 C 对字母表进行编码打印

java - 使用 Stream 还是 Loop 之间的决定