Page 156 - 《软件学报》2021年第9期

2780 Journal of Software 软件学报 Vol.32, No.9, September 2021

线程利用率是活跃线程数与并行度的比率,活跃线程是指正在运行任务的线程.我们在求解一个实例的并
行传播(并行度 p 为 4)进程中获取了活跃线程的数目,其随时间点的关系如图 5 所示:一方面,并行传播模式也存
在串行分量,比如算法 6 除第 9 行~第 11 行之外的部分,在执行这部分串行分量时,活跃线程只有 1 个,线程利用
率为 25%;另一方面,当线程池中的并行过滤任务数小于并行度时,活跃线程数将等于任务数,线程利用率小于
100%.

活跃线程数

并行传播进程
Fig.5 Number of active threads in a parallel propagation process
图 5 并行传播进程中的活跃线程数

最后,我们对比一下并行传播模式在不同并行度 p 下的平均传播时间.p 为 4 的并行传播模式在大多数实例
集上均快于 p 为 2 的并行传播模式,但 p 为 6 的并行传播模式在多数实例集上却不如 p 为 4 的并行传播模式.
我们认为:实验环境的 CPU 为 4 核处理器,因此当并行度高于核数时,并行传播进程中会出现多个线程抢占同一
个核的情况,从而导致平均传播时间变长.

5 总 结

在本文中,首先,我们提出了维持表约束网络 TGAC 的并行传播模式,该模式基于多核 CPU,由并行传播算
法和并行过滤算法两部分组成,并行传播算法利用线程池并行执行维持表约束 TGAC 的并行过滤算法;之后,我
们给出了并行传播模式的可靠性证明,即并行传播模式也维持表约束网络 GAC;另外,通过对并行传播模式的
最坏时间复杂度分析,我们认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式,最终的实验
结果也验证了这一结论.
基于本文的思路,我们认为未来的研究可从以下 3 个方面继续开展.
1) 我们在实验分析中给出了两点关于并行传播模式没有实现线性加速的原因,因此未来的研究可尝试
通过减少并行传播模式的工作总量或提高线程利用率,来进一步提升并行传播的效率;
2) 维持表约束 GAC 的串行过滤算法研究除了基于简单表缩减,还有很多基于其他设计思想的成果,比
如泛型过滤算法系列(GAC2001 [18] ,GAC3 rm[19] ,GAC4R [20] 等)和压缩表示过滤算法系列(MDDc [21] ,
MDD4R [20] ,AdaptiveMDDc [11] 等),这些串行过滤算法均可转化成维持表约束 TGAC 的并行过滤算法;
3) 在相容性理论方面,删值能力强于 GAC 的相容性被称为高阶相容性,如最大限制成对相容性(max
restricted pairwise consistency,简称 maxRPWC)和成对相容性(pairwise consistency,简称 PWC).维持表
约束网络高阶相容性的串行传播模式设计受到了很多研究工作的关注 [22−24] ,因此未来的研究可尝试
设计实现维持表约束网络高阶相容性的并行传播模式.

References:
[1] Hamadi Y, Sais L. Parallel Constraint Programming. Handbook of Parallel Constraint Reasoning, Chapter 9. Springer-Verlag, 2018.
337−379.