并行计算-搜索算法

0

深度优先搜索

搜索到叶子结点或所有子树都搜索完时回溯

分支因子(branching factor)：每个节点平均的孩子数（b叉树）

DFS搜分支因子为\(b\)深度为\(k\)的树，每个节点遍历一次，时间复杂度为\(O(b^k)\)，空间复杂度为\(\Theta(k)\)

并行DFS第一种策略：给每一个处理器一棵子树，\(p=b^k\)，前\(k\)层串行搜索，缺点

状态空间树往往不平衡，无结构的特性往往导致静态调度失效
改进方案：让串行搜索深度更深，每个进程就可以处理更多子树（循环分配）

并行DFS关键在于负载：任务分割(splitting)及动态负载均衡

捐赠(donor)进程：发送任务(work)的进程
接受(recipient)进程：接收任务的进程
半分割(half-split)：理想地，一个stack被分为两块等大
隔断(cutoff)深度：避免发送太小的任务，在给定深度时就不再发送，自己完成

一些可能的策略：

发送处于栈底的结点：均匀分配搜索空间，低分割开销
发送接近隔断深度的结点：结合强启发式算法会有比较好的性能（尝试分配任务给更有可能包含解的搜索空间）
发送一半在底部和隔断深度之间的结点：对于均匀和不规则搜索空间都非常好

动态负载均衡：

整个空间开始时会被指派给一个处理器
当处理器跑完了它的工作就会从其他处理器获得更多的工作
- 消息传递机：工作请求与回复
- 共享地址空间机：锁与工作提取
未探索的状态可以被方便地在处理器中存储为局部栈
一旦一个处理器到达最终状态，所有处理器都会停止

负载均衡策略：设\(V(p)\)为总工作请求数（每个处理器都至少获得一份工作，即\(V(p)\geq p\)）

异步轮询(ARR)：每个进程维护一个计数器，然后以round-robin方式轮询，最差情况\(V(p)=O(p^2)\)
全局轮询(GRR)：系统维护一个全局计数器，然后全局轮询，\(V(p)=p\)
随机轮询(polling)：随机请求一个进程给工作，最差情况无界，考虑平均情况\(V(p)=O(p\log p)\)

总开销\(T_o=pW_p-W\)源于（\(W\)为串行工作，\(pW_p\)为并行工作）

通信：请求与发送工作
空闲时间：等待工作
终止检测
共享资源冲突：如GRR的全局计数器
搜索开销因子：\(s=pW_p/W < p\times 1/s\)，\(W/W_p<1\)是可能的

优先队列全局or局部

单一优先队列：通信开销太大，访问队列将成为瓶颈，且不具有可扩展性
多优先队列：每个进程维护独立的未检测子问题的优先队列，每个进程都从中取出具有最小下界的继续搜索，并时常将未检测的问题发给其他进程

加速比异常(anomalies)：搜索空间是动态生成的，因此实际的工作存在很大区别。

用p个核跑加速比大于p的称为加速异常：一些线程提前完成搜索，剪枝返回
用p个核跑加速比小于p的称为减速异常：目标状态很深，导致大量无效遍历

最佳优先搜索(Best-first search)

采用启发式函数作为评估（当前状态到最优状态的距离）

参考资料