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

Question

当我的并行版本的斐波那契实现(效率低下，只是为了比较库的性能)比正常的低效实现慢得多时，即使在使用了我的 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 .

附言Intel TBB 使用基于任务的并行方法。方法tbb::task_group::run创建一个任务(不是线程)，当线程池中的一个线程可用时执行该任务。因此，系统中有多少任务并不重要——线程的数量总是有限的。