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

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

PSTR2,PSTR3,PSTRbit 和 PCT,并进行了一般化总结,它们同样主要由更新表(算法 8)和过滤论域(算法 9)两部分
组成.
算法 7. enforceTGAC(c).
begin
1 if inconsistent then
2 return
3 for each x∈scp(c) do
c
4 bitdom (x):=bitdom(x)
5 updateTTable(c)
6 filterTDomains(c)
end
算法 8. updateTTable(c).
begin
1 for each τ∈rel(c) do
2 for each x∈scp(c) do
c
3 if bitdom (x)[τ[x]]=0b then
4 rel(c):=rel(c)\{τ}
5 break
end
算法 9. filterTDomains(c).
begin
1 for each x∈scp(c) do
c
2 for each a of which bitdom (x)[a]=1b do
3 if a doesn’t have a temporary support then
c
4 bitdom (x)[a]:=0b
c
5 if bitdom (x) has been filtered then
c
6 bitdom(x):=bitdom(x)&bitdom (x) //non-blocking synchronization
7 if bitdom(x)=0 then
8 inconsistent:=true
9 return
10 varChanged:=true
11 tableMask:=tableMask|bitSbp(x) //non-blocking synchronization
end
与算法 3 不同的是,算法 7 首先判断不相容标识 inconsistent 是否为真:如果为真,算法 7 返回,即所有的线程
c
能够及时终止并行过滤任务;如果为假,算法 7 将每个变量 x∈scp(c)在 c 中的局部中间论域 bitdom (x)更新至最
新的 bitdom(x);然后,算法 7 更新表,即移除无效的元组(算法 8 第 4 行);最后,算法 7 过滤论域,即先从局部中间论
c
c
域 bitdom (x)中删除在该约束上不存在临时支持的值(算法 9 第 4 行).若局部中间论域 bitdom (x)被删值,算法 9
c
c
便将 bitdom(x)与 bitdom (x)的按位与结果赋值给 bitdom(x),即从 bitdom(x)中删除不存在于 bitdom (x)中的值(算
法 9 第 6 行).进一步地,如果 bitdom(x)被删空,即 bitdom(x)的每个位均为 0b,全局不相容标识 inconsistent 被置为
true(算法 9 第 8 行),并行过滤算法结束;否则,论域改变标识 varChanged 被置为 true(算法 9 第 10 行),并且变量 x
的位订阅 bitSbp(x)被提交至约束位标识 tableMask 上(算法 9 第 11 行),即与 x 有关的约束 c 需要参与下一次并
行传播.