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

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

提交至 tableMask 的操作及结果如图 2 所示.

tableMask 0 0 0 0 0 0 0 0
bitSbp(x) 0 0 0 1 0 0 0 1
bitSbp(x) 0 0 0 1 0 0 0 1

tableMask:ൌtableMask|bitSbp(x)

bitSbp(y) 1 0 0 0 0 0 0 1
tableMask 0 0 0 1 0 0 0 1
Fig.2 Bit subscriptions and their submission operations
图 2 位订阅及其提交操作

如前文所述,串行传播算法根据变量传播集合顺次执行对相关约束的过滤任务(算法 1 第 7 行、第 8 行),
我们将这一操作并行化,提出了并行传播算法.并行传播算法使用约束位标识 tableMask 标记相关的表约束,对
这些表约束的过滤任务被动态提交至线程池中并行执行,直到发生了论域删空事件或者没有新的过滤任务.具
体见算法 6.
算法 6. parallelPropagate(X evt :set of variables):Boolean.
begin
1 tableMask:=0
2 for each variable x∈X evt do
3 tableMask:=tableMask|bitSbp(x)
4 inconsistent:=false
5 do
6 submitMask:=tableMask
7 tableMask:=0
8 varChanged:=false
9 for each constraint c of which submitMask[c]=1b do
10 pool.submit(enforeTGAC(c))
11 pool.wait(⋅)
12 if inconsistent then
13 return false
14 while varChanged
15 return true
end
算法 6 的传入参数 X evt 同样是引发初始传播的变量集合,其中的变量被用于初始化约束位标识 tableMask
(第 2 行、第 3 行).submitMask 是一个保存 tableMask 的局部临时标识(第 6 行),因为 tableMask 会被动态更新,
所以算法 6 根据 submitMask 向线程池 pool 提交在约束 c 上维持 TGAC 的并行过滤任务(第 9 行、第 10 行),
之后需要等待它们完成(第 11 行).在并行过滤任务的执行期间,当一个变量的论域被删值后,论域改变标识
varChanged 被置为 true,并且 tableMask 被更新,以在算法 6 的下次循环中向线程池 pool 提交新的并行过滤任务;
如果有一个变量的论域被删空,不相容标识 inconsistent 被置为 true,之后会被识别出(第 12 行),这表明传播失败
(第 13 行),当前表约束网络无解,MAC 算法发生回溯.如果所有的并行过滤任务被执行完成后,varChanged 仍为
flase,即没有发生删值事件,那么循环结束,这表明传播成功(第 15 行),当前表约束网络是 TGAC 的,MAC 算法继
续搜索.

3.2 并行过滤算法
我们对维持表约束 GAC 的串行过滤算法进行扩展,得到了维持表约束 TGAC 的并行过滤算法(算法 7),如