erlang - Erlang 中的并行深度优先搜索比顺序搜索慢

Question

我正在尝试在 Erlang 中实现修改后的并行深度优先搜索算法(我们称之为 *dfs_mod*)。

我想要得到的只是所有“死胡同”，它们基本上是当 *dfs_mod* 访问没有邻居的顶点或具有已经访问过的邻居的顶点时返回的路径。我将每个路径保存到 ets_table1如果我的自定义函数 fun1(Path)返回 true并到 ets_table2如果 fun1(Path)返回 false (我需要使用一些客户过滤器过滤生成的“死胡同”路径)。

我已经实现了这个算法的一个顺序版本，出于某种奇怪的原因，它比并行算法性能更好。

并行实现背后的想法很简单:

访问 Vertex来自 [Vertex|Other_vertices] = Unvisited_neighbours ,

添加此 Vertex到当前路径；

发送 {self(), wait}到“收集器”过程；

为 Unvisited_neighbours 运行 *dfs_mod*当前Vertex在 新工艺 ;

继续运行 *dfs_mod* 提供的其余顶点( Other_vertices )；

当没有更多的顶点要访问时 - 发送 {self(), done}到收集器进程并终止；

所以，基本上每次我访问一个有未访问邻居的顶点时，我都会产生一个新的深度优先搜索过程，然后继续访问其他顶点。

在产生第一个 *dfs_mod* 进程后，我开始收集所有 {Pid, wait}和 {Pid, done}消息( wait 消息是让收集器等待所有 done 消息)。等待收集器函数在 N 毫秒内返回 ok .

出于某种原因，这种并行实现的运行时间为 8 到 160 秒，而顺序版本仅运行 4 秒(测试是在具有 5 个顶点的全连接有向图上在配备 Intel i5 处理器的机器上完成的)。

以下是我对如此糟糕表现的看法:

我通过有向图 Graph到每个运行 *dfs_mod* 的新进程。也许在做 digraph:out_neighbours(Graph)针对来自多个进程的一个有向图导致这种缓慢？

我在列表中累积当前路径并将其传递给每个新生成的 *dfs_mod* 进程，也许传递这么多列表是问题所在？

每次访问新顶点时，我都会使用 ETS 表来保存路径并将其添加到路径中。 ETS 属性是 ([bag, public,{write_concurrency, true}) ，但也许我做错了什么？

每次访问新顶点并将其添加到路径时，我都会使用自定义函数检查路径 fun1() (它基本上检查路径是否有标有字母“n”的顶点出现在带有“m”的顶点之前，并根据结果返回 true/false)。也许这个 fun1()减慢速度？

我试图运行 *dfs_mod* 而不收集 done和 wait消息，但 htop *dfs_mod* 返回 ok 后很长一段时间内都显示了大量 Erlang 事件在 shell 中，所以我不认为主动消息传递会减慢速度。

我怎样才能让我的并行 dfs_mod 比它的顺序副本运行得更快？

编辑 :当我运行并行 *dfs_mod* 时，pman尽管 htop 根本没有显示任何进程显示所有 4 个 CPU 线程都处于忙碌状态。

Answer 1

没有代码就没有快速知道的方法，但这里有一个快速列表，说明可能会失败的原因:

您可能会混淆并行性和并发性。 Erlang 的模型是无共享的，其目标是首先实现并发(独立运行不同的代码单元)。并行只是对此的优化(同时运行一些代码单元)。通常，并行性会在更高的层次上形成，假设您想在 50 个不同的结构上运行排序函数——然后您决定运行 50 个顺序排序函数。

您可能会遇到同步问题或顺序瓶颈，从而有效地将并行解决方案更改为顺序解决方案。

复制数据、上下文切换等的开销使您在并行性方面的 yield 相形见绌。前者对于将大数据集拆分成子数据集，然后再合并成一个大数据集尤其如此。后者对于高度顺序的代码尤其如此，如流程环基准测试所示。

如果我想对此进行优化，我会尽量减少消息传递和数据复制。

如果我是从事此工作的人，我会保留顺序版本。它会做它应该做的事情，并且当成为更大系统的一部分时，只要您的进程多于核心，并行性将来自对 sort 函数的许多调用，而不是 sort 函数的分支。从长远来看，如果是服务器或服务的一部分，使用顺序版本 N 次应该不会比并行版本产生更多负面影响，后者最终会创建许多进程来执行相同的任务，并有可能使系统过载更多.