使用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

需要多長時間？也許你的輸入太小，因此上下文切換主宰了並行版本的運行時間。如果你增加問題集，它的行爲如何？如果你做更多的計算密集型的事情，它現在的行爲如何呢？