使用Intel线程构建模块（TBB）的Parallel_Scan组件无法实现加速

Question

我正在探索用于联合操作情况下的Intel线程构建模块中的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字段。虽然编译器应该能够根据基于类型的别名消歧来判断对y [i]的写入是否不影响这些字段，这可能有助于将字段x和y的读取提升为局部变量。

• 我将输入数组增加到拥有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”进行编译。

• 我在一个16核心系统上运行两个“Sandy Bridge”芯片。

查看内存带宽影响的方法是将示例中的T更改为更小的类型。当我编辑示例将T从int更改为char（从而将内存带宽需求减少约4倍）时，并行加速提高了。 （旁白：存在应该是“身体<牛逼>”的例子“身体<INT>”。）

另一种方式来查看内存带宽的影响是尝试与很多小的系统上的例子核心。在英特尔（R）Xeon Phi（TM）上，我尝试了这个例子，如之前对类型int所描述的那样进行了修改，该例子具有高内存带宽和许多小内核。我可以得到4x-7x的并行加速。将问题大小提升到100,000,000使我的速度提高了10倍-20倍。

总结：多线程扫描可以还清只有当并行计算的好处是可以使超过在数据两遍的开销。

Answer 2

需要多长时间？也许你的输入太小，因此上下文切换主宰了并行版本的运行时间。如果你增加问题集，它的行为如何？如果你做更多的计算密集型的事情，它现在的行为如何呢？