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

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

所有的约束.约束满足问题(constraint satisfaction problem,简称 CSP)确定一个约束网络 N 是否有解.
例 1:变量 x 和 y 的初始论域分别为 D(x)={3,4,5}和 D(y)={3,4},约束 x>y 可用表约束 c 表示,即 scp(c)={x,y},
rel(c)={(4,3),(5,3),(5,4)}.
τ=(a 1 ,a 2 ,...,a r )是约束 c 中的一个元组,其第 i 个值被表示为τ[x i ].元组τ∈rel(c)是有效的当且仅当∀i∈{1,...,r},
τ[x i ]∈dom(x i );否则,τ是无效的.如果元组τ是有效的,则称τ是约束 c 的一个支持.进一步地,如果元组τ是约束 c 的
一个支持且τ[x]=a,则称τ是 c 中对(x,a)的一个支持.
定义 1(广义弧相容(GAC)).
• 取值(x,a)是 GAC 的当且仅当∀c∈sbp(x),c 中至少存在一个对(x,a)的支持;
• 约束 c 是 GAC 的当且仅当∀x∈scp(c),∀a∈dom(x),c 中至少存在一个对(x,a)的支持;
• 约束网络 N 是 GAC 的当且仅当∀c∈C,c 是 GAC 的.
[3]
为了降低并行传播过程中不同线程同时访问同一变量论域的频率,Rolf 等人 提出了局部中间论域,对于
c
变量 x∈scp(c),局部中间论域 dom (x)是 dom(x)在约束 c 中的副本.我们称元组τ∈rel(c)是临时有效的当且仅当
c
∀i∈{1,...,r},τ[x i ]∈dom (x i );否则,τ是无效的.如果元组τ是临时有效的,则称τ是约束 c 的临时支持.进一步地,如果
元组τ是约束 c 的临时支持且τ[x]=a,则称τ是 c 中对(x,a)的临时支持.
接下来,我们给出临时广义弧相容的定义和性质.
定义 2(临时广义弧相容(TGAC)).
• 取值(x,a)是 TGAC 的当且仅当∀c∈sbp(x),c 中至少存在一个对(x,a)的临时支持;
c
• 约束 c 是 TGAC 的当且仅当∀x∈scp(c),∀a∈dom (x),c 中至少存在一个对(x,a)的临时支持;
• 约束网络 N 是 TGAC 的当且仅当∀c∈C,c 是 TGAC 的.
c
性质 1. 取值(x,a)是 GAC 的,且∀c∈sbp(x),∀y∈scp(c),dom (y)=dom(y),那么(x,a)是 TGAC 的.
证明:因为取值(x,a)是 GAC 的,所以∀c∈sbp(x),c 中存在对(x,a)的支持τ c .又因为∀c∈sbp(x),∀y∈scp(c),
c
dom (y)=dom(y),所以∀c∈sbp(x),τ c 是 c 中对(x,a)的临时支持,故(x,a)是 TGAC 的.证毕. □
c
性质 2. 约束 c 是 GAC 的,且∀x∈scp(c),dom (x)=dom(x),那么 c 是 TGAC 的.
c
证明:因为约束 c 是 GAC 的,所以∀x∈scp(c),∀a∈dom(x),c 中存在对(x,a)的支持τ c .又因为∀x∈scp(c),dom (x)=
c
dom(x),所以∀x∈scp(c),∀a∈dom (x),τ c 是 c 中对(x,a)的临时支持,故 c 是 TGAC 的.证毕. □
c
性质 3. 约束网络 N 是 GAC 的,且∀c∈C,∀x∈scp(c),dom (x)=dom(x),那么 N 是 TGAC 的.
c
证明:因为约束网络 N 是 GAC 的,所以∀c∈C,c 是 GAC 的.又因为∀c∈C,∀x∈scp(c),dom (x)=dom(x),由性质
2 可知∀c∈C,c 是 TGAC 的,故 N 是 TGAC 的.证毕. □
1.2 线程池

线程池是一种多线程处理形式,管理一组线程,以便并行处理大量任务.在需要多次使用线程的并行程序
中,单独创建与销毁线程会增加运行开销,从而影响程序的整体性能.而线程池通过限制线程的数量和重用线
程,能够避免创建与销毁线程的代价,还可以提高程序的稳定性.
本文使用的是工作窃取线程池,其中每个线程都有一个独立的任务队列,主线程将任务分配到各个线程的
任务队列中.工作窃取是指如果某个线程完成了其队列中的所有任务,而其他线程的队列中还有未处理任务,那
么空闲线程可以窃取其他线程的未处理任务,从而改善了并行程序的负载均衡.

1.3 位向量
位向量是由若干个位(bit)组成的向量,具有存储空间占用少和处理速度快的特点.在构建一个 CP 求解器时,
[8]
[9]
位向量是变量论域的重要表示方式之一 [13] .另外,维持表约束 GAC 的串行过滤算法 STRbit 和 CT 正是通过
使用位向量才得以大幅度地加快过滤速度.
为了便于说明位向量的数据结构及其操作,我们用 v 表示位向量.位向量 v 由 m 个位组成,其第 i 个位由 v[i]
表示.特别地,0b 和 1b 分别表示位的二进制取值.