使用intel TBB的低效fibonacci系列比非線程實現慢得多

Question

當我並行化的fibonacci實現（效率低下，只是爲了比較庫的性能）比正常的低效實現慢得多時，即使在使用我的i7-6700HQ處理器的所有8個邏輯內核之後。與非並行實施相比，處理器風扇開始處理時間非常緩慢。

的例子是直接從TBB教程英特爾 - https://www.threadingbuildingblocks.org/tutorial-intel-tbb-task-based-programming

這裏是我的代碼

#include <tbb/task_group.h> 
#include <chrono> 
#include <iostream> 

#define FIB_NUM 40 

long fib1(int n) 
{ 
    if(n < 2) return n; 

    else 
    { 
     int x, y; 
     tbb::task_group g; 
     g.run([&]{x=fib1(n - 1);}); 
     g.run([&]{y=fib1(n - 2);}); 
     g.wait(); 
     return x + y; 
    } 
} 

long fib2(int n) 
{ 
    return n < 2? n : fib2(n - 1) + fib2(n - 2); 
} 

int main() 
{ 
    auto t1 = std::chrono::high_resolution_clock::now(); 
    std::cout << fib2(FIB_NUM) << std::endl; 
    auto t2 = std::chrono::high_resolution_clock::now(); 
    std::cout << (t2 - t1).count() << std::endl; 
    t1 = std::chrono::high_resolution_clock::now(); 
    std::cout << fib1(FIB_NUM) << std::endl; 
    t2 = std::chrono::high_resolution_clock::now(); 
    std::cout << (t2 - t1).count() << std::endl; 
} 

我不知道我做錯了。如果有人能指出它會有所幫助。

謝謝

Answer 1

該示例的主要問題是小任務。葉子任務（n<2）只計算return n。毫無疑問，並行性是無效的。當子問題被認爲對於並行化來說太小時，可以通過「截斷」條件來改進該示例。讓我們假設是沒有意義的計算並行第12張斐波那契數，我們將使用串行執行，而不是：

long fib1(int n) 
{ 
    // Use a serial implementation for "small" numbers. 
    if(n < 12) return fib2(n); 
    else 
    { 
     int x, y; 
     tbb::task_group g; 
     g.run([&]{x=fib1(n - 1);}); 
     g.run([&]{y=fib1(n - 2);}); 
     g.wait(); 
     return x + y; 
    } 
} 

也許，你想閱讀有關Divide and Conquer和The Task Scheduler文章。

P.S.英特爾TBB使用基於任務的方法進行並行處理。方法tbb::task_group::run創建一個任務（不是線程），當線程池中的一個線程可用時，該任務將被執行。因此，系統中有多少任務並不重要 - 線程的數量總是有限的。