algorithm - 将 4 步 PCAM（福斯特方法）应用于并行算法设计的示例？

Question

Foster 的方法论有 4 个步骤来设计并行算法

• 分区

• 沟通

• 集聚

• 映射

我遇到的许多例子都采用了非常数学的方法。虽然我可以理解数学是必不可少的，但我想知道是否有一种更简单的方法可以向非计算机科学的人解释 PCAM 方法？

标签： algorithmoptimizationdesign-patternsparallel-processingopenmp

Answer 1

假设您要去超市买些杂货，并且您有一个合作伙伴，在这种情况下，您的计算机有两个处理器或两个线程（您和您的合作伙伴）。

首先，我们将问题划分为任务：

• 创建购物清单
• 开车去超市
• 获取列表中的所有项目
• 支付物品
• 开车回家
• 存放所有物品
• 停车（假设车库离房子很远）

然后你定义通信

• 为了创建购物清单，每个处理器将检查房子是否缺少什么，并会不时聚集在一起以合并清单
• 在超市里，每个加工者都会去拿一些商品，然后聚集在购物车上，从列表中选择另一件商品，这样没有加工者会同时去寻找相同的商品
• 当一个处理器存储物品时，另一个去停车，当处理器回来时，它可能有助于存储仍然剩下的物品

任务的聚集（不幸的是，我已经将它们描述为聚集）

映射

• 你检查一些项目，你的伙伴检查其他
• 任何处理器都开车去超市（但另一个一起去）
• 你去拿一些物品，你的伴侣得到一个不同的物品，直到清单完成
• 任何处理器都为货物付款（希望是您的合作伙伴）
• 任何处理器驱动器返回以将处理器留在家中存储物品
• 驾驶员处理器去停车
• 非司机处理器开始入库
• 驱动处理器返回并检查还剩下哪些货物并帮助存储货物

这完全是非数学的，是我能想到的最好的例子，任何愿意理解该方法的非计算机科学人士都可能掌握这个想法（我希望）。

干杯!