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);
}

与串行执行相比，并行执行需要更多时间。在此并行执行中花费了 2500 秒，而串行花费了大约 167 秒。有人可以解释一下原因吗？

4

4 回答 4

6

高架。

当您的实际任务是轻量级时，协调/通信占主导地位，您不会（自动）从并行执行中获益。这是一个很常见的问题。

而是尝试串行计算 M 个斐波那契数（成本足够高），然后并行计算它们。你应该看到收获。

于 2013-03-14T14:31:29.507 回答
2

将 Cutoff 更改为 12，在（Linux 上的 -O；Windows 上的 /O2）上进行优化编译，您应该会看到显着的加速。

示例中有很多并行性。问题在于，在 Cutoff=2 的情况下，有用的并行计算的各个单元被调度开销所淹没。提高截止值应该可以解决问题。

这里是分析。分析并行性有两个重要时刻：

  • work - 计算工作的总量。
  • 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平方）。每个此类任务的结果用于将斐波那契数相加。

首先，这里没有实际的并行执行（可能除了两个独立的递归计算）。每个任务都依赖于它的子任务的结果，并且不能真正并行地做任何事情。另一方面，您正在执行大量工作来设置每个任务。你没有看到任何好处一点也不奇怪）

现在，如果您要通过迭代计算斐波那契数 1 .. 50，并且您开始，例如，系统中每个处理器内核执行一个任务，并将其与仅使用单个循环的迭代解决方案进行比较，我敢肯定会显示出更好的改进。

于 2013-03-14T14:35:05.800 回答