multithreading - 将递归分成更细的递归粒度

Question

我考虑过将递归拆分为较小的递归大小，然后想知道它是否有实际用途，同时还要考虑并行性。

为了弄清楚我的意思，下面举一个小例子(合并排序):

而不是做:

...
merge_sort(b, m);
merge_sort(m, e);
merge(b, m, e);  
...

做这样的事情:

...
merge_sort_quad(b, m1);
merge_sort_quad(m1 + 1, m2);
merge_sort_quad(m2 + 1, m3);
merge_sort_quad(m3 + 1, e);
merge_quad(b, m1, m2, m3, e);
...

考虑到一个并行的示例，我没有看到两种方法都有基本的区别，因为它们可能会导致相同的结果:

void foo (..) {
    ...
    //using tbb::prallel_invoke() to call functions in parallel
    tbb::parallel_invoke(foo(..), foo(..)); 
    ...
}

void foo_parallel (..) {
    ...
    tbb::parallel_invoke(foo(..), foo(..), foo(..), foo(..));
    ...
}

我希望你们能向我解释一下这是完全没有用的，不好的，还是依赖于算法并且可能有一定的实际用途。我对此表示怀疑，因为它看起来有点像手动循环展开。

Answer 1

您是正确的，确实是通过merge-sort完成的。您的问题中有几种不同的想法，有些还有进一步的含义，因此让我们将它们分开。我将讨论一些我认为您可能比我更清楚的事情，因为它会使其他阅读它的人得到一个更加连贯的答案。

第一次递归。在逻辑递归中，我们将问题分解为自身的重复版本，直到它们达到琐碎的程度为止(通常，乘以因子乘以当前乘数减去一个乘数直到达到1)，而在函数递归中，我们将问题分解为重复的小版本。通过自身调用函数来对此建模。

逻辑递归是人们解决问题的一种技术。函数递归是一种反射(reflect)它的编程技术。但是，函数递归的成本可能要比迭代等效项高。因此，我们经常使我们的编译器将它们转换为迭代等效项，进行尾调用优化，后者也几乎可以做到这一点(通过消除大部分或全部递归调用的开销)，或者当失败时，自己转换为迭代版本。

现在，在特定类型的递归中，通过合并排序，我们可以在解决问题时增加简单任务的数量。这不是n!成为n × (n - 1)!的单个任务，而是merge-sort成为合并序列的两半以合并的两个任务，然后是合并结果的任务。

您做出了正确的结论，以得出可以导致并行处理的结论。有一些其他功能使它变得有趣。如果像您一样将其分解为4个合并，并将每个合并分配到不同的内核，则每个内核将处理将紧密连接的内存并一起加载到缓存中(紧密数据的方式可以为您提供帮助)我们)，但是一个线程不太可能在另一个线程感兴趣的同一条缓存行中写入数据，并迫使它遭受缓存失效(“错误共享”，因为紧密的数据会对我们造成伤害) )。

这种排序可能只限于CPU和内存，每个内核1个线程或每个虚拟处理器最多1个线程(如果使用超线程)可能不会有太多 yield 。

因此，拆分为单独的函数调用最多可提高虚拟处理器数量的性能。您问题中的示例将是四处理器计算机上的想法。在那之后，一个线程不太可能在结束时从另一个线程窃取工作，从而有很大帮助，因此从那时起，您最好采用迭代方法(无论是手动编码还是循环编码)由编译器导入)。采用功能递归的方法超出了每个处理器具有的功能的范围，这又再次伤害了我们。但是，我们总是有可能会错误地计算出实际需要使用多少个内核(因为其他进程也在使用它们)，因此值得比每个内核功能更进一步，并允许先完成的内核采用剩菜剩饭。

文献中有很多关于并行合并排序的东西，并且一些框架和库都有利用它的合并排序实现。