algorithm - map reduce算法的并行效率计算公式是什么？

Question

有没有公式可以告诉我们map reduce算法的并行效率？ (换句话说，我如何在数学上证明 MR 算法 A 优于 MR 算法 B)

我用谷歌搜索，但我只能在 wiki 上找到并行算法的加速和效率的定义。但如果有人能展示这些公式如何应用于 MR 算法，那就太好了

Answer 1

看看维基 for Bulk Synchronous Parallel in short BSP.

Rob Bisselings 的论文中包含另一个复杂度计算

Parallel Scientific Computation: A Structured Approach Using BSP and MPI

BSP 是对 MapReduce 的抽象，在链接底部包含复杂度/成本分析公式。

所以您需要做的是，将您的MapReduce 算法转换为BSP 版本。屏障同步是例如 Map 和 Reduce 阶段之间的转换或新的 MapReduce 作业。消息(通信)是您在 Map 和 Reduce 函数中发送到文件系统的内容。