algorithm - 所有分而治之的算法都可以利用并行性吗？

Question

我正在上一门算法课，似乎可以利用并行处理来实现分治算法。总是这样吗？

Answer 1

是的，但不一定有效。

分而治之的算法最适合（更容易理解）任务级并行性。这些任务是递归的，递归任务可以解释为任务树层次结构。可以将任务树层次结构视为使用不同参数的函数的多次调用。一些函数调用将等待其他执行（即它的子项），如果异步执行或直接在同步执行中可用（阻塞调用将自动等待结果），则可以在并行行话中作为 *wait*o 或连接使用。所有这些操作实际上在每个并行框架中都可用。

但是并行任务之间的通信可能会很昂贵，具体取决于参数数据大小。如果将您的问题分成更小的部分（通过网络执行多台计算机或在多核计算的进程之间）比执行这些部分花费更多的时间，那么您将不会获得性能提升。你实际上会失去性能。

使用允许任务层次结构的框架，例如 C/C++ 中的 OpenMP 任务或 Python 中的SCOOP（更多可用），将串行分治算法转换为其并行算法更容易。