c++ - 使用英特尔线程构建模块 (TBB) 的 Parallel_Scan 组件未实现加速

Question

我正在探索英特尔线程构建模块中用于关联操作的 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;
} 

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

Answer 1

我是 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”，应该是“Body”。)

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

总而言之:只有当并行计算的好处超过对数据进行两次传递的开销时，多线程扫描才有返回。