3

我正在探索 Intel Thread Building Blocks 中的 Parallel_Scan 组件,该组件用于关联操作,我发现 Parallel_Scan 占用的时间是串行执行的 10 倍。

我写来检查的代码是:

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "tbb/task_scheduler_init.h"
#include "tbb/blocked_range.h"
#include "tbb/parallel_scan.h"
#include "tbb/tick_count.h"

using namespace std;
using namespace tbb;

template <class T>
class Body 
{
    T reduced_result;
    T* const y;
    const T* const x;

    public:

    Body( T y_[], const T x_[] ) : reduced_result(0), x(x_), y(y_) {}

    T get_reduced_result() const {return reduced_result;}

    template<typename Tag>
    void operator()( const blocked_range<int>& r, Tag ) 
    {
        T temp = reduced_result;

        for( int i=r.begin(); i<r.end(); ++i ) 
        {
            temp = temp+x[i];
            if( Tag::is_final_scan() )
            y[i] = temp;
        }

        reduced_result = temp;
    }

    Body( Body& b, split ) : x(b.x), y(b.y), reduced_result(10) {}

    void reverse_join( Body& a ) 
    {
        reduced_result = a.reduced_result + reduced_result;
    }

    void assign( Body& b ) 
    {   
        reduced_result = b.reduced_result;
    }
};


template<class T>
float DoParallelScan( T y[], const T x[], int n) 
{
    Body<int> body(y,x);
    tick_count t1,t2,t3,t4;
    t1=tick_count::now();
    parallel_scan( blocked_range<int>(0,n), body , auto_partitioner() );
    t2=tick_count::now();
    cout<<"Time Taken for parallel scan is \t"<<(t2-t1).seconds()<<endl;
    return body.get_reduced_result();
}


template<class T1>
float SerialScan(T1 y[], const T1 x[], int n)
{
    tick_count t3,t4;

    t3=tick_count::now();
    T1 temp = 10;

    for( int i=1; i<n; ++i ) 
    {
        temp = temp+x[i];
        y[i] = temp;
    }
    t4=tick_count::now();
    cout<<"Time Taken for serial  scan is \t"<<(t4-t3).seconds()<<endl;
    return temp;

}


int main()
{
    task_scheduler_init init1;

    int y1[100000],x1[100000];

    for(int i=0;i<100000;i++)
        x1[i]=i;

    cout<<fixed;

    cout<<"\n serial scan output is \t"<<SerialScan(y1,x1,100000)<<endl;

    cout<<"\n parallel scan output is \t"<<DoParallelScan(y1,x1,100000)<<endl;

    return 0;
} 

请帮助我找出哪里出错了。

4

2 回答 2

15

我是 tbb::parallel_scan 的原作者。

在使用“大核”的多核系统上从并行扫描中获得加速可能很困难。原因是并行扫描本质上是一种两遍算法。如果数据不适合外层缓存,则并行扫描必须从内存中读取两次数据,而串行算法只需执行一次。对于像整数加法这样简单的运算,内存流量,而不是 ALU,通常是“大核”的瓶颈,“大核”将大量硬件资源用于快速串行执行。如果数据确实适合外层缓存,则可能没有足够的工作来分摊并行开销。

通过以下更改和条件,我能够为您的示例获得一些并行加速(大约 2 倍):

  • 我在循环之前将 r.end() 的读取提升到一个局部变量中,如下所示:

    int rend = r.end();
    for( int i=r.begin(); i<rend; ++i )
    

    这样做有助于编译器生成更好的代码,因为它知道 rend 是循环不变的。如果没有提升,编译器必须假设写入 y[i] 可能会覆盖 r.end() 读取的 r 字段。类似地将字段 x 和 y 的读取提升到局部变量中可能会有所帮助,尽管编译器应该能够从基于类型的别名消歧中判断出对 y[i] 的写入不会影响这些字段。

  • 我将输入数组增加到了 10,000,000 个元素,因此还有更多工作要做,从而更好地摊销并行调度开销。为了避免堆栈溢出,我在堆中分配了数组。

  • 我预热了 TBB 运行时。一般来说,在做这种计时练习时,最好先做一个“扔掉”的跑步,这样一次性的启动成本就不会被计算在内。为了进行预热(对于串行和并行代码),我在时序逻辑周围包裹了一个三行程循环,如下所示:

    for( int k=0; k<3; ++k ) {
        cout<<"\n serial scan output is \t"<<SerialScan(y1,x1,n)<<endl;
    
        cout<<"\n parallel scan output is \t"<<DoParallelScan(y1,x1,n)<<endl;
    }
    

    这是我对大多数计时实验所做的事情,因此我可以查看首次成本是否很大,或者是否存在其他感兴趣的变化。

  • 我用“gcc -O2 -ltbb”编译。

  • 我在带有两个“Sandy Bridge”芯片的 16 核系统上运行。

查看内存带宽影响的一种方法是将示例中的 T 更改为更小的类型。当我编辑示例以将 T 从 int 更改为 char(从而将内存带宽需求减少约 4 倍)时,并行加速增加了。(旁白:示例中有一个“Body<int>”应该是“Body<T>”。)

查看内存带宽影响的另一种方法是在具有许多小内核的系统上尝试该示例。我在具有高内存带宽和许多小内核的 Intel(R) Xeon Phi(TM) 上尝试了该示例,该示例按照前面对 int 类型的描述进行了修改。我可以获得 4 到 7 倍的并行加速。将问题规模提高到 100,000,000 使我的速度提高了 10 到 20 倍。

总结一下:多线程扫描只有在并行计算的好处可以超过两次遍历数据的开销时才能得到回报。

于 2013-05-16T17:51:19.553 回答
0

总共需要多长时间?也许您的输入太小了,因此上下文切换主导了并行版本的运行时间。如果增加问题集,它会如何表现?如果你做一些计算密集度更高的事情,比如你现在做的简单求和,它会如何表现?

于 2013-05-15T09:37:28.217 回答