3

几个“快速问题”：

  • 在 MapReduce 范式中可以重铸哪些类型/类别的算法？（例如 k-means 有一个 MR 实现）

  • 有没有不能用这种方式表达的？

  • 哪些算法特征使它们在 MR 范式中重铸的吸引力/复杂性降低

提前感谢您的帮助。

最大限度。

4

2 回答 2

2

Map Reduce 范式最适合“令人尴尬地并行”的问题，即任何两个任务之间没有依赖关系。请查看Wikipedia 上的Embarrassingly Parallel文章。

此外，在操作是可交换或关联的情况下，可以轻松优化 MapReduce 程序以获得更好的性能。

于 2012-05-24T18:06:26.813 回答
2

我正在为来自 MPI 世界的大数据算法集合解决这些相同的问题。这是我的看法。

MR 配方的基本管道似乎是扩张/收缩。该映射应用于一个大集合，可能会创建一个更大的集合，然后使用 reduce 对该集合进行排序/组织，以便可以将其聚合成一个合并的数据集，最好是更小的数据集。您需要的 map 和 reduce 的数量是 MR 算法的聪明之处。

作为一种通用的计算方法，您可以使用 MR 解决任何计算问题，但从实际角度来看，MR 的资源利用率偏向于具有高并发 I/O 要求的计算问题。诸如字数统计之类的令人尴尬的并行算法当然适合该法案，但它比这更广泛，例如，您的 k-means 算法是一个约束最小化问题，没有人会将其归类为令人尴尬的并行，但仍然具有有效的 MR 公式。

我目前的正式框架从五个属性方面描述了分布式计算机系统：

  1. 处理器性能
  2. 内存容量（我们可以忽略内存性能，因为它往往由处理器设计人员构建以支持处理器的性能）
  3. 磁盘存储容量
  4. 网络带宽性能
  5. 网络消息延迟

磁盘性能是我仍在努力干净地整合的东西，因为旋转与 SSD 存储技术具有巨大的性能影响，但前提是 SSD 通过 PCIe 集成。如果通过 SAS 或 SATA 集成，那么您会达到接口限制，并且旋转也很容易使该接口饱和。在这种情况下，只有 SSD 出色的延迟才能有助于性能提升，但这只会有利于具有较小数据记录的较小数据集。所以目前，让我们假设我们有一个真正的大数据问题，需要轮换存储来有效地控制数据成本。

MapReduce 在该扩展/收缩流程中使用上述分布式资源列表：它使用处理器+内存+磁盘来执行映射功能，然后在很大程度上依赖于网络的性能来执行 reduce 功能。由于添加服务器将扩展处理器+内存+磁盘资源，不幸的是，网络性能仅在容量上适度增加，但延迟性能降低。由于网络延迟是分布式系统中极难最小化的性能特征，因此 MR 算法对于以带宽为中心的运营商最为有效：即具有数十亿个独立小数据包的算法。

我正在寻找有关 PDE 求解器和优化算法（例如整数规划）是否存在有效 MR 算法的见解。从做 FutureGrid 的人那里找到了一张很棒的图： 算法组织领域

于 2012-05-27T15:21:48.993 回答