Page 78 - 《软件学报》2021年第8期

2360 Journal of Software 软件学报 Vol.32, No.8, August 2021

5.4 凸包求解
在一个实数向量空间 V 中,对于给定点集 X,所有包含 X 的凸集的交集 S 被称为 X 的凸包.本文只讨论二维
空间中点集的情况.图 7 中红色连线确定了一个含有 12 个点的平面点集形成的凸包.图 7(a)~图 7(f)分步展示了
该凸包的快速求解算法的递归步骤:首先确定含有最小横坐标值和最大横坐标值的点 a 和 b 并进入递归步骤:
以有向线段 ab 为基准,分别在其两侧进一步确定凸包中的其他点.以 ab 上侧为例,点 c 为距离 ab 最远点,将 c
加入凸包并由此形成有向线段 ac 和 cb.之后分别以 ac 和 cb 为基准线段,分别在它们外侧进一步寻找凸包中
的点.

Fig.7 Demonstration of the recursive convex-hull algorithm
图 7 凸包问题的递归求解算法示意

给定一条基准线段和对应点集,将源任务定义为求在基准线外侧距该基准线段距离最远的点.以源任务
为基础使用 SWAN 可轻易实现并行的凸包求解程序(附录 2).但由图 7 可以看到,在算法的初始阶段,由于有向
基准线段的数量较少导致了程序的并行度很低.但在该阶段,少量的线程需要计算大量的点到基准线段的距
离,因此形成了程序的性能瓶颈.针对这种情况,我们使用 SWAN 的任务挂起和上下文保存功能,使程序在初
始阶段就派生诸多距离计算子任务以使更多的处理核心参与计算.在所有距离计算子任务结束后,由源任务
进行归约产生目标点.如图 8 所示,在初始阶段提高并发度后,凸包求解程序的性能最终达到 MPE 串行版本性
能的 23.6 倍.