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

陈佳楠 等:基于多核 CPU 的表约束并行传播模式研究 2779

Table 2 Average results to solve instances from different series (STRbit and PSTRbit)
表 2 不同实例集的平均实验结果(STRbit 和 PSTRbit)
Parallel (PSTRbit)
Serial (STRbit)
Series # p=2 p=4 p=6
Time Filt Avg. Time Filt Speed Time Filt Speed Time Filt Speed
rand-3-20-fcd 50 17.57 121.86 1.44 13.79 171.90 1.27 11.66 176.44 1.51 14.23 177.60 1.23
rand-3-20 50 36.96 244.96 1.51 26.90 345.07 1.37 22.74 354.55 1.63 27.70 356.85 1.33
rand-5-12 50 1.98 2.41 8.21 1.18 3.33 1.68 0.86 3.38 2.30 0.80 3.41 2.47
rand-8-20 20 19.30 30.34 6.36 15.08 42.67 1.28 12.83 44.31 1.50 14.62 44.85 1.32
rand-10-60 32 58.77 4.89 120.14 32.31 7.24 1.82 28.89 8.01 2.03 28.38 8.65 2.07
half 19 240.38 605.16 3.97 181.89 836.02 1.32 123.37 852.54 1.95 133.33 864.64 1.80
MDD0.7 8 94.14 139.41 6.75 57.99 194.72 1.62 39.71 199.09 2.37 38.73 202.30 2.43
MDD0.9 9 8.14 7.91 10.29 4.79 11.11 1.70 3.05 11.35 2.67 2.73 11.53 2.98
bddSmall 35 8.69 10.29 8.44 6.15 15.21 1.41 4.18 15.28 2.08 3.83 15.34 2.27
uk 42 15.21 8.56 17.77 10.09 11.34 1.51 7.24 11.59 2.10 7.18 11.85 2.12
ogd 43 6.79 2.24 30.25 4.80 3.08 1.41 3.54 3.17 1.92 3.22 3.27 2.11
lex 62 1.69 4.03 4.20 1.35 5.62 1.25 1.21 5.76 1.40 1.49 5.92 1.13
words 65 5.06 10.36 4.88 3.85 14.44 1.31 3.31 14.80 1.53 4.16 15.30 1.22
tsp-20 15 3.26 35.92 0.91 2.74 46.24 1.19 2.52 46.58 1.29 3.21 46.57 1.02
tsp-25 15 52.22 649.16 0.80 47.99 820.89 1.09 40.42 825.40 1.29 47.91 824.96 1.09
jnhSat 16 0.50 8.69 0.58 0.42 10.92 1.19 0.31 10.88 1.61 0.36 10.91 1.39
jnhUnsat 34 0.23 3.38 0.68 0.21 4.28 1.10 0.15 4.26 1.53 0.15 4.27 1.53
modR 25 8.06 75.80 1.06 9.81 101.58 0.82 13.56 104.95 0.59 17.48 104.58 0.46
aim-50 24 0.02 0.73 0.27 0.08 0.95 0.25 0.14 0.95 0.14 0.18 0.95 0.11
aim-100 16 0.15 4.44 0.34 0.39 5.83 0.38 0.69 5.81 0.22 0.92 5.82 0.16
aim-200 8 12.57 355.71 0.35 18.66 465.44 0.67 20.77 465.68 0.61 28.77 465.94 0.44
dubois 3 20.08 591.96 0.34 138.03 1 008.12 0.15 286.92 1 008.00 0.07 330.55 1 008.59 0.06
并行传播模式在多数实例集上取得了较好的加速比,但是没有实现线性加速(加速比与并行度相等),原因
主要有两点.
• 在求解实例的过程中,并行过滤算法被调用的平均次数 filt 多于串行过滤算法被调用的平均次数 filt.
虽然并行传播模式有多个线程并行执行过滤算法,但其工作总量并不与串行传播模式的工作总量相等,而
是随着线程的增多而增加.这是因为在并行传播模式下,线程之间不能相互通信.对表约束 c 执行并行过滤算法
c
的线程只在初始时更新变量 x∈scp(c)在 c 中的局部中间论域 bitdom (x),到算法结束前不再获取最新的
bitdom(x).那么在此过程中,如果其他线程删除了 bitdom(x)中的值,c 需要被重新执行一次并行过滤算法以获取
最新的 bitdom(x).这种现象在过滤算法被顺次执行的串行传播模式中是不存在的.
例 5:现有两个表约束 c 1 和 c 2 ,其中,scp(c 1 )={x,y},scp(c 2 )={x,z,u}.假设取值(y,a)和(z,a)被其他表约束删除,这
导致 c 1 和 c 2 被执行过滤算法.在串行传播模式下,首先线程 t 对 c 1 执行串行过滤算法,t 从 bitdom(x)中删除了(x,a);
之后,在 t 对 c 2 执行串行过滤算法时,(x,a)的移除导致 t 从 bitdom(u)中删除了(u,a).在并行传播模式下,c 1 和 c 2 同
c1 c2
时被两个线程 t 1 和 t 2 分别执行并行过滤算法:首先,bitdom (x)和 bitdom (x)被更新至最新的 bitdom(x);之后,t 1
c2
从 bitdom(x)中删除了(x,a),但(x,a)仍存在于 bitdom (x)中,因此 t 2 没有从 bitdom(u)中删除(u,a);因为(x,a)的删除,
c2
c 1 和 c 2 需要再次被 t 1 和 t 2 分别执行并行过滤算法,其中,t 2 将 bitdom (x)更新至最新的 bitdom(x),进而从 bitdom(u)
中删除了(u,a).过程如图 4 所示,同样的情况下,串行过滤算法被执行了 2 次,而并行过滤算法被执行了 4 次.

delete delete
串行 t enforceGAC(c 1) (x,a) t enforceGAC(c 2) (u,a)

delete
t 1 enforceGAC(c 1) (x,a) t 1 enforceGAC(c 1)
并行 delete
enforceGAC(c 2) enforceGAC(c 2) (u,a)
t 2 t 2

Fig.4 An example of serial propagation mode versus parallel propagation mode
图 4 串行传播模式与并行传播模式的对比实例
• 并行传播进程中线程利用率并不总是 100%.