あまみや ゆうこ » ASYNC

异步广度优先搜索算法

为什么要异步?

CPU的工艺越来越小,Cannon Lake架构的Intel CPU已经达到10nm技术,因此在面积不变的情况下,核心数可以明显提升。单纯的提升主频将造成发热量大、需要的电压大、功耗大的问题。而传统的算法与数据结构是针对单核心单线程同步而言的,因此,传统的算法无法将CPU利用率达到最大。

广度优先搜索

首先我们先了解一下与之对应的深度优先搜索(DFS),深度优先搜索即像走迷宫时,始终保持左手与左侧墙壁接触,换言之即遇到岔路时永远向左拐,从而寻找出口。而广度优先搜索,则在每个岔路时,变出一个分身,继续前进。

但是,实际上是这样吗?答案是否定的,刚刚已经讲到,传统的算法与数据结构是建立在单线程同步基础上的,因此传统算法只能够模拟分身在同时前进,这时就要引入队列来保存和展开岔路节点(当遇到新岔路时,将这个节点放入队列。队列头部元素进行展开寻找新的岔路并放入队列尾部)。

基于Parallel的并行广度优先搜索

而在并行或异步以及多线程的环境下,我们可以真的让“分身”们同时前进。首先使用并行广度优先搜索的前提是你不在意真的保证了广度是同步的,虽然并行广度优先搜索能够寻找到全部解,但是无法保证同一时刻进行搜索的任务是在同一深度的。

在这一前提下,我们以遍历图为例,首先定义邻接表的数据结构:

更多内容 »

Published on 1/15/2017 9:21:44 AM