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

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

过滤时间较长的实例上相对串行传播模式能够取得较为明显的加速;若 T<<S p ,那么 O(er max d max (S p +T)/p)≈
O(er max d max S p /p),即并行传播模式在平均过滤时间较短的实例上会慢于串行传播模式.
4 实验结果

我们在 22 组 CSP 实例集上使用 MAC 算法分别测试了串行传播模式和并行传播模式.在串行传播模式下,
串行过滤算法分别使用 CT 和 STRbit;在并行传播模式下,并行过滤算法分别使用 PCT 和 PSTRbit,线程池的并
行度 p 依次被置为 2,4 和 6.MAC 算法采用 dom/ddeg 变量启发式和 min 值启发式,dom/ddeg 是稳定的变量启发
式,能让两种传播模式在求解同一实例时拥有相同的变量选取顺序,进而实现公平的效率对比.每个实例的搜索
时间上限为 900 秒.实验环境为 Intel Core i7 3.40GHz(4 cores) 8GB RAM Windows10 64bit OS,程序编写语言是
Java11.0.3 和 Scala2.12.8.所有的实例集均来自 http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html,我们的测
试代码可在 https://github.com/amtfjlsj/lotus 上获取.
表 1 和表 2 给出了不同实例集的平均实验结果,实例集中,未超时的实例个数用#表示.time 表示求解实例所
需的平均传播时间(单位 s),每个实例集对应的最短平均传播时间被加粗;filt 表示在求解实例的过程中过滤算
法被调用的平均次数(单位 10 万);avg 表示执行一次串行过滤算法的平均时间(单位μs),即实例集的平均过滤时
间,我们使用串行传播模式下 time 与 filt 的比值作为 avg 的近似值;speed 是并行传播模式相对于串行传播模式
的平均传播时间加速比,即串行平均传播时间与并行平均传播时间的比值.
首先,我们比较一下串行传播模式和并行传播模式的实验结果.在 17 组实例集上,并行传播模式要快于串
行传播模式,而且在多数实例集上取得了从 1.4~3.4 不等的加速比;在另外 5 组实例集上,并行传播模式的表现不
如串行传播模式.从各实例集在串行传播模式下的平均过滤时间 avg 可以看出:取得较好加速比的实例集,其
avg 普遍较大,如 rand-10-60,ogd,uk 和 MDD0.9 等;并行传播效果不好的实例集,其 avg 普遍较小,如 aim-50,
aim-100 和 dubois等.这与第 3.3 节性质 6 的分析相一致.因此,我们提出的并行传播模式适用于平均过滤时间 avg
较大的实例.
Table 1 Average results to solve instances from different series (CT and PCT)
表 1 不同实例集的平均实验结果(CT 和 PCT)
Parallel (PCT)
Serial (CT)
Series # p=2 p=4 p=6
Time Filt Avg. Time Filt Speed Time Filt Speed Time Filt Speed
rand-3-20-fcd 50 14.06 121.86 1.15 10.39 171.78 1.35 9.65 176.26 1.46 12.03 176.77 1.17
rand-3-20 50 29.58 244.96 1.21 21.50 344.79 1.38 19.51 353.97 1.52 24.09 355.33 1.23
rand-5-12 50 0.85 2.41 3.52 0.43 3.33 1.98 0.27 3.38 3.15 0.25 3.41 3.40
rand-8-20 20 4.67 30.34 1.54 4.11 42.37 1.14 4.50 43.38 1.04 6.03 43.04 0.77
rand-10-60 32 9.10 4.89 18.60 5.40 7.10 1.69 3.70 7.59 2.46 3.84 8.03 2.37
half 19 95.64 605.16 1.58 65.93 833.86 1.45 54.85 845.03 1.74 67.60 849.79 1.41
MDD0.7 8 31.22 139.41 2.24 20.27 194.18 1.54 15.55 197.26 2.01 17.75 198.91 1.76
MDD0.9 9 1.47 7.91 1.86 1.01 11.08 1.46 0.80 11.26 1.84 0.94 11.34 1.56
bddSmall 35 2.66 10.29 2.58 1.55 15.20 1.72 0.95 15.26 2.80 0.90 15.31 2.96
uk 42 10.35 8.56 12.09 5.53 11.35 1.87 4.01 11.56 2.58 4.07 11.77 2.54
ogd 43 5.80 2.25 25.83 3.28 3.07 1.77 2.18 3.13 2.66 2.17 3.20 2.67
lex 62 1.56 4.03 3.87 1.03 5.63 1.51 1.01 5.81 1.54 1.32 5.96 1.18
words 65 4.44 10.36 4.29 2.93 14.48 1.52 2.88 14.91 1.54 3.56 15.38 1.25
tsp-20 15 2.49 35.92 0.69 2.17 46.19 1.15 2.07 46.53 1.20 2.63 46.45 0.95
tsp-25 15 44.08 649.17 0.68 37.34 819.74 1.18 33.58 824.59 1.31 41.29 823.70 1.07
jnhSat 16 0.53 8.70 0.61 0.35 10.92 1.51 0.28 10.88 1.89 0.31 10.92 1.71
jnhUnsat 34 0.21 3.39 0.62 0.14 4.27 1.50 0.11 4.24 1.91 0.12 4.26 1.75
modR 25 6.48 75.80 0.85 8.18 102.57 0.79 12.14 104.88 0.53 15.95 104.03 0.41
aim-50 24 0.03 0.73 0.41 0.08 0.95 0.38 0.14 0.95 0.21 0.17 0.94 0.18
aim-100 16 0.15 4.44 0.34 0.34 5.83 0.44 0.61 5.81 0.25 0.83 5.81 0.18
aim-200 8 15.51 355.72 0.44 16.22 465.04 0.96 19.58 465.14 0.79 27.32 465.69 0.57
dubois 3 22.49 591.96 0.38 112.77 1 007.99 0.20 275.14 1 008.04 0.08 310.58 1 010.59 0.07