c++ - 如何使用 TBB 多线程 "tail call"递归

Question

我正在尝试使用 tbb 对现有的递归算法进行多线程处理。单线程版本使用尾调用递归，从结构上看是这样的:

void my_func() {
    my_recusive_func (0);
}

bool doSomeWork (int i, int& a, int& b, int& c) {
    // do some work
}

void my_recusive_func (int i) {
    int a, b, c;
    bool notDone = doSomeWork (i, a, b, c);
    if (notDone) {
        my_recusive_func (a);
        my_recusive_func (b);
        my_recusive_func (c);
    }
}

我是一个 tbb 新手，所以我第一次尝试使用 parallel_invoke 函数:

void my_recusive_func (int i) {
    int a, b, c;
    bool notDone = doSomeWork (i, a, b, c);
    if (notDone) {
        tbb::parallel_invoke (
                [a]{my_recusive_func (a);},
                [b]{my_recusive_func (b);},
                [c]{my_recusive_func (c);});
    }
}

这确实有效，并且比单线程版本运行得更快，但它似乎不能很好地扩展内核数量。我的目标机器有 16 个内核(32 个超线程)，因此可扩展性对于这个项目非常重要，但这个版本在该机器上最多只能获得大约 8 倍的加速，并且许多内核在算法运行时似乎处于空闲状态。

我的理论是 tbb 正在等待子任务在 parallel_invoke 之后完成，所以可能有很多任务闲置等待不必要的？这可以解释空闲核心吗？有没有办法让父任务返回而不等待 child ？我在想也许是这样的，但我对调度程序的了解还不够，不知道这是否可行:

void my_func()
{
    tbb::task_group g;
    my_recusive_func (0, g);
    g.wait();
}

void my_recusive_func (int i, tbb::task_group& g) {
    int a, b, c;
    bool notDone = doSomeWork (i, a, b, c);
    if (notDone) {
        g.run([a,&g]{my_recusive_func(a, g);});
        g.run([b,&g]{my_recusive_func(b, g);});
        my_recusive_func (c, g);
    }
}

我的第一个问题是 tbb::task_group::run() 是线程安全的吗？我无法从文档中弄清楚这一点。另外，有没有更好的方法来解决这个问题？也许我应该改用低级调度程序调用？

(我在没有编译的情况下输入了这段代码，所以请原谅打字错误。)

Answer 1

这里确实有两个问题:

1. task_group::run 的 TBB 实现是线程安全的吗？是的。 (我们应该更清楚地记录这一点)。
2. 让多个线程在相同 task_group 上调用方法 run() 是否可扩展？不。(我相信 Microsoft 文档在某处提到了这一点。)原因是 task_group 成为了一个集中的争论点。这只是实现中的获取和添加，但最终仍然无法扩展，因为受影响的缓存行必须反弹。

通常最好从 task_group 中生成少量任务。如果使用递归并行，给每个级别它自己的 task_group。尽管性能可能不会比使用 parallel_invoke 好多少。

低级 tbb::task 接口(interface)是最好的选择。您甚至可以在其中编写尾递归代码，使用 tasK::execute 返回指向尾调用任务的指针的技巧。

但我有点担心空闲线程。我想知道是否有足够的工作来保持线程忙碌。考虑做 work-span analysis第一的。如果您使用的是 Intel 编译器(或 gcc 4.9)，您可以先尝试使用 Cilk 版本进行试验。如果这不会加速，那么即使是低级 tbb::task 接口(interface)也不太可能提供帮助，并且需要检查更高级别的问题(工作和跨度)。