使用英特尔 TBB 的低效斐波那契数列比非线程实现慢得多

Question

令人惊讶的是，我的斐波那契实现的并行版本（低效，只是为了比较库的性能）比正常的低效率实现慢得多，即使在使用了我的 i7 的所有 8 个逻辑内核之后-6700HQ 处理器。处理器风扇开始失控，与非并行实施相比，处理时间非常慢。

例子直接来自intel上的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。毫无疑问，它对于并行性来说是低效的。当子问题被认为对于并行化而言太小时，可以使用 "cutoff" 条件来改进该示例。假设并行计算前 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 and The Task Scheduler 的文章。

P.S。 Intel TBB 使用基于任务的并行方法。方法 tbb::task_group::run 创建一个任务（不是线程），当线程池中的一个线程可用时执行该任务。所以系统中有多少任务并不重要——线程的数量总是有限的。

使用英特尔 TBB 的低效斐波那契数列比非线程实现慢得多

Inefficient fibonacci series using intel TBB much slower than non-threaded implementation

c++

parallel-processing

multithreading

tbb