如何使用TBB多线程"尾调用"递归

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之后完成子任务,所以可能有许多任务闲置等待不必要？这会解释空闲核心吗？有没有办法让父任务返回而不等待孩子？我当时想的可能是这样的,但我对调度程序还不了解,但还不知道这是否正常:

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 成为争论的中心点。这只是实现中的获取和添加，但这最终仍然是不可扩展的，因为受影响的缓存行必须反弹。

通常最好从一个任务组中生成少量任务。如果使用递归并行性，请为每个级别指定其自己的任务组。尽管性能可能不会比使用parallel_invoke更好。

低级 tbb::task 接口是最好的选择。您甚至可以使用 tasK::execute 返回指向尾调用任务的指针的技巧来编写尾递归。

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