1

私はTBBでのタスクの実装を研究しており、フィボナッチ数列の並列計算と直列計算のコードを実行しています。

コードは次のとおりです。

#include <iostream>
#include <list>
#include <tbb/task.h>
#include <tbb/task_group.h>
#include <stdlib.h>
#include "tbb/compat/thread"
#include "tbb/task_scheduler_init.h"
using namespace std;
using namespace tbb;

#define CutOff 2

long serialFib( long n ) {
if( n<2 )
return n;
else
return serialFib(n-1) + serialFib(n-2);
}


class FibTask: public task 
{
    public:
    const long n;
    long* const sum;

    FibTask( long n_, long* sum_ ) : n(n_), sum(sum_) {}

    task* execute() 
    {
        // cout<<"task id of thread is \t"<<this_thread::get_id()<<"FibTask(n)="<<n<<endl;  // Overrides virtual function task::execute    
                // cout<<"Task Stolen is"<<is_stolen_task()<<endl;
        if( n<CutOff ) 
        {
            *sum = serialFib(n);
        }
         else
         {
            long x, y;
            FibTask& a = *new( allocate_child() ) FibTask(n-1,&x);
            FibTask& b = *new( allocate_child() ) FibTask(n-2,&y);
            set_ref_count(3); // 3 = 2 children + 1 for wait // ref_countis used to keep track of the number of tasks spawned at                            the current level of the task graph
            spawn( b );
                      // cout<<"child id of thread is \t"<<this_thread::get_id()<<"calculating n ="<<n<<endl;
            spawn_and_wait_for_all( a ); //set tasks for execution and wait for them
            *sum = x+y;
        }
        return NULL;
    }
};


long parallelFib( long n ) 
{
    long sum;
    FibTask& a = *new(task::allocate_root()) FibTask(n,&sum);
    task::spawn_root_and_wait(a);
    return sum;
}


int main()
{     
     long i,j;
     cout<<fixed;

     cout<<"Fibonacci Series parallelly formed is "<<endl;
      tick_count t0=tick_count::now();
     for(i=0;i<50;i++)
     cout<<parallelFib(i)<<"\t";
    // cout<<"parallel execution of Fibonacci series for n=10 \t"<<parallelFib(i)<<endl;

     tick_count t1=tick_count::now();
     double t=(t1-t0).seconds();
     cout<<"Time Elapsed in Parallel Execution is  \t"<<t<<endl;
     cout<<"\n Fibonacci Series Serially formed is "<<endl;
     tick_count t3=tick_count::now();

     for(j=0;j<50;j++)
     cout<<serialFib(j)<<"\t";
     tick_count t4=tick_count::now();
     double t5=(t4-t3).seconds();
     cout<<"Time Elapsed in Serial  Execution is  \t"<<t5<<endl;
     return(0);
}

並列実行は、シリアル実行に比べて時間がかかります。この並列実行では、シリアル実行に約 167 秒かかりましたが、この並列実行には 2500 秒かかりました。誰でもこの理由を説明できますか?

4

4 に答える 4

6

オーバーヘッド。

実際のタスクが軽量の場合、調整/コミュニケーションが支配的であり、並列実行から (自動的に) 利益を得ることはありません。これはかなり一般的な問題です。

代わりに、(十分に高いコストの) M 個のフィボナッチ数をシリアルに計算してから、それらを並列に計算してみてください。利益が見られるはずです。

于 2013-03-14T14:31:29.507 に答える
2

Cutoff を 12 に変更し、最適化をオン (Linux では -O、Windows では /O2) でコンパイルすると、大幅なスピードアップが見られるはずです。

この例には多くの並列処理があります。問題は、Cutoff=2 の場合、有用な並列計算の個々のユニットがスケジューリング オーバーヘッドによって圧倒されることです。カットオフ値を上げると、問題が解決するはずです。

これが分析です。並列処理を分析するには、次の 2 つの重要な時期があります。

  • 仕事 - 計算作業の総量。
  • span - クリティカル パスの長さ。

利用可能な並列処理は作業/スパンです。

fib(n) の場合、n が十分に大きい場合、作業は fib(n) にほぼ比例します [はい、それ自体が記述されています!]。スパンはコール ツリーの深さで、おおよそ n に比例します。したがって、並列度は fib(n)/n に比例します。したがって、n=10 の場合でも、一般的な 2013 年のデスクトップ マシンの動作を維持するのに十分な並列処理が利用できます。

問題は、TBB タスクの作成、実行、同期、および破棄に時間がかかることです。Cutoff を 2 から 12 に変更すると、作業が小さすぎてスケジューリングのオーバーヘッドがそれを圧倒してしまう場合に、シリアル コードが引き継ぐことができます。これは、再帰的並列処理の一般的なパターンです。連続して実行したほうがよい作業のチャンクになるまで、並列で再帰します。他の並列フレームワーク (OpenMP や Cilk Plus など) にも同じ問題があります。TBB より多かれ少なかれ、タスクのオーバーヘッドがあります。変更されるのは、最適なしきい値が何であるかだけです。

カットオフを変えてみてください。値を小さくすると、並列処理が増えますが、スケジューリングのオーバーヘッドが増えます。値が大きいほど、並列処理は少なくなりますが、スケジューリングのオーバーヘッドは少なくなります。その間に、適切なスピードアップを実現する値の範囲が見つかる可能性があります。

于 2013-03-15T01:35:39.650 に答える
0

それ以上の情報がなければ、それを伝えるのは難しいでしょう. 確認する必要があります: お使いのコンピューターにはいくつのプロセッサーがありますか? それらのプロセッサを利用した可能性のある他のプログラムはありましたか? (真の) 並列で実行してパフォーマンス上の利点を得るには、オペレーティング システムが少なくとも 2 つの空きプロセッサを割り当てることができる必要があります。また、小さなタスクの場合、スレッドの割り当てとその結果の収集のオーバーヘッドが、並列実行の利点を超える可能性があります。

于 2013-03-14T14:32:54.503 に答える
0

各タスクがそうであると考えているのは正しいresult of fib(n-1) + result of fib(n-2)ですか-基本的に、タスクを開始すると、タスクが非常に多くなるまで別のタスクが開始されます(すべてを数えようとして少し迷いました-nだと思います)二乗）。そして、そのような各タスクの結果は、フィボナッチ数を合計するために使用されます。

まず第一に、ここでは実際の並列実行はありません (おそらく 2 つの独立した再帰計算を除いて)。すべてのタスクはそのサブタスクの結果に依存しており、実際には何も並行して行うことはできません。一方で、各タスクを設定するために非常に多くの作業を実行しています。何の利益も見られないことはまったく驚くべきことではありません）

ここで、フィボナッチ数 1 .. 50 を反復によって計算する場合、たとえば、システムのプロセッサ コアごとに 1 つのタスクを開始し、それを 1 つのループだけを使用する反復ソリューションと比較すると、はるかに優れた改善を示します。

于 2013-03-14T14:35:05.800 に答える