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}到'收集'流程;
• 运行*dfs_mod*为Unvisited_neighbours当前的Vertex一个新的进程 ;
• 继续运行*dfs_mod*与其余提供的顶点(Other_vertices);
• 当没有更多顶点要访问时 - 发送{self(), done}到收集器进程并终止;

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

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

---

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

以下是我对这种糟糕表现的看法:

• 我将有向图传递Graph给每个运行*dfs_mod*的新进程.也许digraph:out_neighbours(Graph)从多个进程中反对一个有向图会导致这种缓慢？
• 我在列表中累积当前路径并将其传递给每个新生成的*dfs_mod*进程,也许传递这么多列表是问题？
• 每次访问新顶点并将其添加到路径时,我都会使用ETS表来保存路径.ETS属性是([bag, public,{write_concurrency, true}),但也许我做错了什么？
• 每次我访问一个新的顶点并将其添加到路径时,我检查一个带有自定义函数的路径fun1()(它基本上检查路径是否在带有"m"的顶点之前出现标有字母"n"的顶点,并true/false根据结果返回).也许这fun1()减缓了事情的进展？
• 我试图在没有收集done和wait消息的情况下运行*dfs_mod*,但是htop在*dfs_mod*ok在shell中返回后很长一段时间内显示了很多Erlang活动,所以我不认为活动消息传递会减慢速度.

---

如何让我的并行dfs_mod比顺序对应的更快？

编辑:当我运行并行*dfs_mod*时,pman根本不显示任何进程,但htop显示所有4个CPU线程都忙.

Answer 1

没有代码,没有快速的方法可以知道,但这里有一个快速列表,说明为什么这可能会失败:

• 您可能会混淆并行性和并发性.Erlang的模型是无共享的,并且首先针对并发性(独立运行不同的代码单元).并行性只是对此的优化(同时运行一些代码单元).通常,并行性将采用更高级别的形式,比如你想在50种不同的结构上运行排序功能 - 然后你决定运行50个顺序排序函数.

• 您可能遇到同步问题或顺序瓶颈,有效地将并行解决方案更改为顺序解决方案.

• 复制数据,上下文切换等方面的开销使得并行性方面的收益相形见绌.前者尤其适用于大数据集,您可以分解为子数据集,然后再加入大数据集.后者尤其适用于高度顺序的代码,如过程环基准所示.

如果我想优化它,我会尽量减少消息传递和数据复制.

如果我是那个人,我会保留顺序版本.它完成它应该做的事情,并且当一个更大的系统的一部分,只要你有比核心更多的进程,并行性将来自对sort函数的多次调用而不是sort函数的分支.从长远来看,如果服务器或服务的一部分,使用顺序版本N次应该没有比并行更多的负面影响,最终创建许多,更多的进程来执行相同的任务,并且风险使系统更多的风险.