1

I have tried with OpenMP and Cilk Plus. The result is the same, multithreading works slower. I don't know what I'm doing wrong. I did what the guy did in this tutorial

His code works better in parallel, while the situation in mine is like this:

PARALLEL: Fibonacci number #42 is 267914296
Calculated in 33.026 seconds using 8 workers

SERIAL: Fibonacci number #42 is 267914296
Calculated in 2.110 seconds using 8 workers

I exactly copied the source code of the tutorial.

I also tried it with OpenMP, the same thing happens there too. I check the usage of CPU cores during the execution. They all work, it is fine.

I tried to change the number of workers with this command:

export CILK_NWORKERS=4

It appears as the number of workers increases, the algorithm runs slower. But sometimes it doesn't. I implemented Cilk codes on both C and C++. No difference.

This is the sequential Fibonacci function:

int fib_s(int n)
{
    if (n < 2)
        return n;
    int x = fib_s(n-1);
    int y = fib_s(n-2);

    return x + y;
}

This is the parallel Fibonacci function:

int fib(int n)
{
    if (n < 2)
        return n;
    int x = cilk_spawn fib(n-1);
    int y = fib(n-2);
    cilk_sync;
    return x + y;
}

And I calculate running time like this in main() function:

clock_t start = clock();
int result = fib(n);
clock_t end = clock();
double duration = (double)(end - start) / CLOCKS_PER_SEC;

Can anyone help me?

4

2 回答 2

2

您问题的正确答案取决于硬件。许多因素通常会影响代码的性能：可以应用不同的软件策略来加速执行。然而，它们中的一些比另一些更有效，这取决于 (1) 所选的特定应用程序和 (2) 所选的特定硬件平台。我想建议对您的应用程序进行概要分析。

在这里，您可以找到软件分析的一般介绍，而在这里，您可以找到可以帮助您完成此任务的软件工具列表。

在此链接和此其他链接中，您可以找到用于分析 OpenMP 应用程序的信息（您的问题的情况）。

了解和理解幕后发生的事情始终是一个好习惯。这将允许您定位著名的 tris 应用程序/代码/硬件的瓶颈。

于 2020-01-10T10:58:12.747 回答
2

问：谁能帮助我？

是的。您会看到，这fib( 42 )可能比25 [us]单工作者解释（！）代码中花费的时间更少

鉴于上面的PARALLEL代码已被报告用于处理，如果设计正确~33 [s]，编译代码可以fib( ~ 1,700,000 )在同一期间计算 a。~33 [s]

解决方案 ：

任何递归公式化的问题描述都是老数学家的罪过：

虽然它在纸面上看起来很酷，
但它在堆栈上的缩放比例很丑，并且为任何更深层次的递归阻塞了非常多的资源......
让所有“以前的”级别等待大部分时间时间，
直到两者return 2都return 1发生在它们的所有后代路径
中，并且递归公式算法的累积阶段开始从深度递归潜水的所有深度返回到顶部。

这种依赖树等于计算的纯（一个接一个）进程，任何注入处理编排的[SERIAL]尝试都只会增加处理成本（添加所有附加开销） ，而不会改进纯-序列依赖驱动的结果累积。{ [CONCURENT] | [PARALLEL] }[SERIAL]

让我们看看，到底有多糟糕cilk_spawn fib( N )：

f(42)
   |
   x=--> --> --> --> --> --> --> --> --> --> --> -- --> --> --> --> --> --> --> --> --> --> --> --> --> -->f(41)
   |                                                                                                          |
   y=f(40)                                                                                                    x=--> --> --> --> --> --> --> --> --> -->  f(40)
   ~    |                                                                                                     |                                             |
   ~    x=--> --> --> --> --> --> --> --> --> f(39)                                                           y=f(39)                                       x=--> --> --> --> --> --> --> --> -->  f(39)
   ~    |                                        |                                                            ~    |                                        |                                         |   
   ~    y=f(38)                                  x=--> --> --> --> --> --> f(38)                              ~    x=--> --> --> --> f(38)                  y=f(38)                                   x=--> --> --> --> --> --> f(38)
   ~    ~    |                                   |                            |                               ~    |                    |                   ~    |                                    |                            |
   ~    ~    x=--> --> f(37)                     y=f(37)                      x=--> --> f(37)                 ~    y=f(37)              x=--> --> --> f(37) ~    x=--> --> f(37)                      y=f(37)                      x=--> --> f(37)
   ~    ~    |            |                      ~    |                       |            |                  ~    ~    |               |                |  ~    |            |                       ~    |                       |            |
   ~    ~    y=f(36)      x=--> --> f(36)        ~    x=--> --> f(36)         y=f(36)      x=-->f(36)         ~    ~    x=--> --> f(36) y=f(36)          x= ~    y=f(36)      x=--> --> f(36)         ~    x=--> --> f(36)         y=f(36)      x=--> --> f(36)
   ~    ~    ~    |       |            |         ~    |            |          ~    |       |       |          ~    ~    |            |  ~    |           |  ~    ~    |       |            |          ~    |            |          ~    |       |            |
   ~    ~    ~    x=-->f  y=f(35)      x=-->f    ~    y=f(35)      x=-->f(35) ~    x=-->f  y=f(35) x=-->f     ~    ~    y=f(35)      x= ~    x=-->f(35)  y= ~    ~    x=-->f  y=f(35)      x=-->f(35) ~    y=f(35)      x=-->f(35) ~    x=-->   y=f(35)      x=-->f(35)
   ~    ~    ~    |       ~    |       |         ~    ~    |       |       |  ~    |       ~    |  |          ~    ~    ~    |       |  ~    |       |   ~  ~    ~    |       ~    |       |       |  ~    ~    |       |       |  ~    |       ~    |       |       |
   ~    ~    ~    y=f(34) ~    x=-->f  y=f(34)   ~    ~    x=-->f  y=f(34) x= ~    y=f(34) ~    x= y=f(34)    ~    ~    ~    x=-->f  y= ~    y=f(34) x=  ~  ~    ~    y=f(34) ~    x=-->f  y=f(34) x= ~    ~    x=-->f  y=f(34) x= ~    y=f(34) ~    x=-->f  y=f(34) x=-->f
   ~    ~    ~    ~    |  ~    |       ~    |    ~    ~    |       ~    |  |  ~    ~    |  ~    |  ~    |     ~    ~    ~    |       ~  ~    ~    |  |   ~  ~    ~    ~    |  ~    |       ~    |  |  ~    ~    |       ~    |  |  ~    ~    |  ~    |       ~       |
   ~    ~    ~    ~    x= ~    y=f(33) ~    x=   ~    ~    y=f(33) ~    x= y= ~    ~    x= ~    y= ~    x=    ~    ~    ~    y=f(33) ~  ~    ~    x= y=  ~  ~    ~    ~    x= ~    y=f(33) ~    x= y= ~    ~    y=f(33) ~    x= y= ~    ~    x= ~    y=f(33) ~       y=f(33)
   ~    ~    ~    ~    |  ~    ~    |  ~    |    ~    ~    ~    |  ~    |  ~  ~    ~    |  ~    ~  ~    |     ~    ~    ~    ~    |  ~  ~    ~    |  ~   ~  ~    ~    ~    |  ~    ~    |  ~    |  ~  ~    ~    ~    |  ~    |  ~  ~    ~    |  ~    ~    |  ~       ~    |
   ~    ~    ~    ~    y= ~    ~    x= ~    y=   ~    ~    ~    x= ~    y= ~  ~    ~    y= ~    ~  ~    y=    ~    ~    ~    ~    x= ~  ~    ~    y= ~   ~  ~    ~    ~    y= ~    ~    x= ~    y= ~  ~    ~    ~    x= ~    y= ~  ~    ~    y= ~    ~    x= ~       ~    x=-->f
   ~    ~    ~    ~    ~  ~    ~    |  ~    ~    ~    ~    ~    |  ~    ~  ~  ~    ~    ~  ~    ~  ~    ~     ~    ~    ~    ~    |  ~  ~    ~    ~  ~   ~  ~    ~    ~    ~  ~    ~    |  ~    ~  ~  ~    ~    ~    |  ~    ~  ~  ~    ~    ~  ~    ~    |  ~       ~    |
   :    :    :    :    :
   :    :    :    :     
   :    :    :
   ~    ~  --SYNC-----------f(36)+f(37)
   ~    ~ <--RET x+y // <-- f(38)
   ~  --SYNC----------------f(38)+f(39)
   ~ <--RET x+y      // <-- f(40)
 --SYNC---------------------f(40)+f(41)
<--RET x+y           // <-- f(42)

算一算，自上而下运行的递归方法有多少次已经完全重新计算了每个和相应的值- 是的，你一次又一次地计算一个相同的东西，只是由于“数学”-递归方法的惰性：Fib( N )N

fib( N == 42 ) was during recursion calculated .........1x times...
fib( N == 41 ) was during recursion calculated .........1x times...
fib( N == 40 ) was during recursion calculated .........2x times...
fib( N == 39 ) was during recursion calculated .........3x times...
fib( N == 38 ) was during recursion calculated .........5x times...
fib( N == 37 ) was during recursion calculated .........8x times...
fib( N == 36 ) was during recursion calculated ........13x times...
fib( N == 35 ) was during recursion calculated ........21x times...
fib( N == 34 ) was during recursion calculated ........34x times...
fib( N == 33 ) was during recursion calculated ........55x times...
fib( N == 32 ) was during recursion calculated ........89x times...
fib( N == 31 ) was during recursion calculated .......144x times...
fib( N == 30 ) was during recursion calculated .......233x times...
fib( N == 29 ) was during recursion calculated .......377x times...
fib( N == 28 ) was during recursion calculated .......610x times...
fib( N == 27 ) was during recursion calculated .......987x times...
fib( N == 26 ) was during recursion calculated ......1597x times...
fib( N == 25 ) was during recursion calculated ......2584x times...
fib( N == 24 ) was during recursion calculated ......4181x times...
fib( N == 23 ) was during recursion calculated ......6765x times...
fib( N == 22 ) was during recursion calculated .....10946x times...
fib( N == 21 ) was during recursion calculated .....17711x times...
fib( N == 20 ) was during recursion calculated .....28657x times...
fib( N == 19 ) was during recursion calculated .....46368x times...
fib( N == 18 ) was during recursion calculated .....75025x times...
fib( N == 17 ) was during recursion calculated ....121393x times...
fib( N == 16 ) was during recursion calculated ....196418x times...
fib( N == 15 ) was during recursion calculated ....317811x times...
fib( N == 14 ) was during recursion calculated ....514229x times...
fib( N == 13 ) was during recursion calculated ....832040x times...
fib( N == 12 ) was during recursion calculated ...1346269x times...
fib( N == 11 ) was during recursion calculated ...2178309x times...
fib( N == 10 ) was during recursion calculated ...3524578x times...
fib( N ==  9 ) was during recursion calculated ...5702887x times...
fib( N ==  8 ) was during recursion calculated ...9227465x times...
fib( N ==  7 ) was during recursion calculated ..14930352x times...
fib( N ==  6 ) was during recursion calculated ..24157817x times...
fib( N ==  5 ) was during recursion calculated ..39088169x times...
fib( N ==  4 ) was during recursion calculated ..63245986x times...
fib( N ==  3 ) was during recursion calculated .102334155x times...
fib( N ==  2 ) was during recursion calculated .165580141x times...
fib( N ==  1 ) was during recursion calculated .102334155x times...

快速和资源的高效处理 - 灵感：

虽然原始的递归计算称为535,828,591时间（!!!）同样微不足道fib()（通常是一个，已经在其他地方已经计算过
----有些甚至数亿次已经〜102,334,155x次......作为fib( 3 )），产卵多达-代码执行块，267,914,295 只[CONCURRENT]为 8 个工作人员排队，大部分时间都在等待，但因为他们已经将他们产生的孩子潜入了尽可能深的地方，后来除了添加一对return 1然后return 2返回的数字之外什么也不做并且从昂贵的自己的进程中返回，“直接”处理方法是毫无疑问的更聪明和更快的方式：

int fib_direct( int n ) // PSEUDO-CODE
{   assert(  n > 0      && "EXCEPTION: fib_direct() was called with a wrong parameter value" );
    if (  n == 1
       || n == 2
          ) return n;
 // ---------------------------- .ALLOC + .SET 
    int fib_[ max(4,n) ];
        fib_[3] = 3;
        fib_[4] = 5;
 // ---------------------------- .LOOP LESS THAN N-TIMES
    for(           int i = 5; i <= n; i++ )
    {   fib_[i] = fib_[i-2]
                + fib_[i-1];
        }
 // ---------------------------- .RET
    return fib_[n];
    }

一个更有效的实现（仍然只是一个线程并且仍然只是解释）设法轻松地计算出fib_direct( 230000 )比2.1 [s]您编译的代码运行时更少的时间fib( 42 )。

于 2020-01-14T19:38:36.033 回答