基于多核CPU的表約束并行傳播模式研究?

陳佳楠,李 哲,李占山1,

1(吉林大學(xué) 軟件學(xué)院,吉林 長春 130012)

2(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林 長春 130012)

3(符號計(jì)算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué)),吉林 長春 130012)

約束程序(constraint programming,簡稱CP)是一種求解組合優(yōu)化問題的有效方法,在人工智能、運(yùn)籌學(xué)、圖論等諸多領(lǐng)域都有廣泛的應(yīng)用.并行計(jì)算是在不改變預(yù)期結(jié)果的情況下,同時(shí)對問題的多個(gè)部分進(jìn)行處理的能力.隨著計(jì)算機(jī)并行處理能力的發(fā)展,約束程序與并行計(jì)算的結(jié)合研究已成為被關(guān)注的領(lǐng)域,即并行約束程序.

針對并行約束程序的研究大致可分為以下幾類:并行傳播、搜索空間分割、組合算法和問題分解等[1].其中,并行傳播是指并行執(zhí)行在約束上的過濾算法,其研究意義在于利用并行計(jì)算提高約束傳播的效率.但這種并行化操作并不簡單,會出現(xiàn)變量論域的同步問題,具有一定的挑戰(zhàn)性[2],因此只有少數(shù)有關(guān)并行傳播的研究成果.比如:Rolf 等人[3]提出了維持約束網(wǎng)絡(luò)并行相容性的兩種傳播模型,分別是使用共享中間論域的傳播模型和使用局部中間論域的傳播模型;李哲等人[4]給出了一種適合GPU 運(yùn)算的并行弧相容算法AC4GPU.

由于缺少相應(yīng)的表約束并行過濾算法,Rolf 等人提出的傳播模型不能直接應(yīng)用在對表約束的并行傳播上.根據(jù)我們掌握的資料,目前還沒有針對表約束并行傳播的研究成果被公布.表約束是約束程序中最常用的約束類型之一,也被稱為外延約束,每個(gè)約束在包含的變量集上顯式地列舉出所有支持或禁止的取值組合.表約束理論上可以編碼任何類型的約束,在許多應(yīng)用程序領(lǐng)域中,當(dāng)對組合問題進(jìn)行建模時(shí),常常需要使用它們.

維持表約束網(wǎng)絡(luò)廣義弧相容(generalized arc consistency,簡稱GAC)的串行傳播模式由串行傳播算法和串行過濾算法兩部分組成,串行傳播算法串行執(zhí)行維持表約束GAC 的串行過濾算法.過去的十多年中,維持表約束GAC 的串行過濾算法研究已經(jīng)公布了大量的成果,其中具有代表性的系列成果是基于簡單表縮減的串行過濾算法(若無特殊說明,后文的過濾算法均指基于簡單表縮減的過濾算法).比如:STR(simple tabular reduction)[5]能夠動(dòng)態(tài)地維持表約束的有效元組;在STR 的基礎(chǔ)上,STR2[6]在檢查元組的有效性和收集被支持的取值時(shí)僅考慮相關(guān)的變量子集;STR3[7]通過使用dual table 等數(shù)據(jù)結(jié)構(gòu),避免了不必要的表遍歷;STRbit[8]采用位向量編碼dual table,大幅度地提升了過濾效率;CT(compact table)[9]使用以位向量為基礎(chǔ)的sparse bit-sets,進(jìn)一步加快了過濾速度;STR-N[10]能夠直接作用于負(fù)表約束,其求解效率具有明顯的優(yōu)勢;AdaptiveSTR[11]通過自適應(yīng)地檢測并刪除無效元組,改進(jìn)了STR3,使得算法速度顯著提升;STR2*[12]采用了一種動(dòng)態(tài)維持元組集有效部分的全新方法,擁有比STR2 和STR3 更高的效率.

根據(jù)維持表約束網(wǎng)絡(luò) GAC 的串行傳播模式,我們提出了維持表約束網(wǎng)絡(luò)臨時(shí)廣義弧相容(temporary generalized arc consistency,簡稱TGAC)的并行傳播模式.該模式基于多核CPU,由并行傳播算法和并行過濾算法兩部分組成,并行傳播算法利用線程池并行執(zhí)行維持表約束TGAC 的并行過濾算法.之后,我們給出了并行傳播模式的可靠性證明,即并行傳播模式也維持表約束網(wǎng)絡(luò)GAC.接下來,我們分析了并行傳播模式的最壞時(shí)間復(fù)雜度,并將其與串行傳播模式的最壞時(shí)間復(fù)雜度進(jìn)行對比;經(jīng)過分析對比,我們認(rèn)為,并行傳播模式在平均過濾時(shí)間較長的實(shí)例上要快于串行傳播模式.最終的實(shí)驗(yàn)結(jié)果也驗(yàn)證了上述結(jié)論,而且并行傳播模式在多數(shù)實(shí)例集上取得了從1.4~3.4 不等的加速比.

本文第1 節(jié)介紹相關(guān)的背景知識.第2 節(jié)回顧維持表約束網(wǎng)絡(luò)GAC 的串行傳播模式.第3 節(jié)給出維持表約束網(wǎng)絡(luò)TGAC 的并行傳播模式.第4 節(jié)展示實(shí)驗(yàn)結(jié)果.第5 節(jié)做出工作總結(jié)和未來展望.

1 背景知識

1.1 約束滿足問題

一個(gè)約束網(wǎng)絡(luò)N由一個(gè)變量集X和一個(gè)約束集C組成,其中:X包含n個(gè)變量,C包含e個(gè)約束.每個(gè)變量x有一個(gè)初始論域D(x),D(x)是x的初始取值集合;dom(x)表示在回溯搜索中變量x的當(dāng)前論域(若無特殊說明,后文的論域均指當(dāng)前論域),(x,a)表示變量x在dom(x)中的取值a.每個(gè)約束c都包含一個(gè)有序的變量集合scp(c),scp(c)被稱為c的作用域,是變量集X的子集.相應(yīng)地,每個(gè)變量x有一個(gè)約束訂閱集sbp(x)={c|x∈scp(c)}.約束c的元數(shù)r為|scp(c)|,即c所包含的變量個(gè)數(shù).約束c在語義上由一個(gè)關(guān)系rel(c)定義,rel(c)包含c所允許的元組集合.(正)表約束c通過列出所允許的元組來表示rel(c).約束網(wǎng)絡(luò)N的解是對所有變量的一組賦值,這組賦值滿足所有的約束.約束滿足問題(constraint satisfaction problem,簡稱CSP)確定一個(gè)約束網(wǎng)絡(luò)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)}.

τ=(a1,a2,...,ar)是約束c中的一個(gè)元組,其第i個(gè)值被表示為τ[xi].元組τ∈rel(c)是有效的當(dāng)且僅當(dāng)?i∈{1,...,r},τ[xi]∈dom(xi);否則,τ是無效的.如果元組τ是有效的,則稱τ是約束c的一個(gè)支持.進(jìn)一步地,如果元組τ是約束c的一個(gè)支持且τ[x]=a,則稱τ是c中對(x,a)的一個(gè)支持.

定義1(廣義弧相容(GAC)).

?取值(x,a)是GAC 的當(dāng)且僅當(dāng)?c∈sbp(x),c中至少存在一個(gè)對(x,a)的支持;

?約束c是GAC 的當(dāng)且僅當(dāng)?x∈scp(c),.?a∈dom(x),c中至少存在一個(gè)對(x,a)的支持;

?約束網(wǎng)絡(luò)N是GAC 的當(dāng)且僅當(dāng)?c∈C,c是GAC 的.

為了降低并行傳播過程中不同線程同時(shí)訪問同一變量論域的頻率,Rolf 等人[3]提出了局部中間論域,對于變量x∈scp(c),局部中間論域domc(x)是dom(x)在約束c中的副本.我們稱元組τ∈rel(c)是臨時(shí)有效的當(dāng)且僅當(dāng)?i∈{1,...,r},τ[xi]∈domc(xi);否則,τ是無效的.如果元組τ是臨時(shí)有效的,則稱τ是約束c的臨時(shí)支持.進(jìn)一步地,如果元組τ是約束c的臨時(shí)支持且τ[x]=a,則稱τ是c中對(x,a)的臨時(shí)支持.

接下來,我們給出臨時(shí)廣義弧相容的定義和性質(zhì).

定義2(臨時(shí)廣義弧相容(TGAC)).

?取值(x,a)是TGAC 的當(dāng)且僅當(dāng)?c∈sbp(x),c中至少存在一個(gè)對(x,a)的臨時(shí)支持;

?約束c是TGAC 的當(dāng)且僅當(dāng)?x∈scp(c),?a∈domc(x),c中至少存在一個(gè)對(x,a)的臨時(shí)支持;

?約束網(wǎng)絡(luò)N是TGAC 的當(dāng)且僅當(dāng)?c∈C,c是TGAC 的.

性質(zhì)1.取值(x,a)是GAC 的,且?c∈sbp(x),?y∈scp(c),domc(y)=dom(y),那么(x,a)是TGAC 的.

證明:因?yàn)槿≈?x,a)是 GAC 的,所以?c∈sbp(x),c中存在對(x,a)的支持τc.又因?yàn)?c∈sbp(x),?y∈scp(c),domc(y)=dom(y),所以?c∈sbp(x),τc是c中對(x,a)的臨時(shí)支持,故(x,a)是TGAC 的.證畢.□

性質(zhì)2.約束c 是GAC 的,且?x∈scp(c),domc(x)=dom(x),那么c是TGAC 的.

證明:因?yàn)榧s束c是GAC 的,所以?x∈scp(c),?a∈dom(x),c中存在對(x,a)的支持τc.又因?yàn)?x∈scp(c),domc(x)=dom(x),所以?x∈scp(c),?a∈domc(x),τc是c中對(x,a)的臨時(shí)支持,故c是TGAC 的.證畢.□

性質(zhì)3.約束網(wǎng)絡(luò)N是GAC 的,且?c∈C,?x∈scp(c),domc(x)=dom(x),那么N是TGAC 的.

證明:因?yàn)榧s束網(wǎng)絡(luò)N是GAC 的,所以?c∈C,c是GAC 的.又因?yàn)?c∈C,?x∈scp(c),domc(x)=dom(x),由性質(zhì)2 可知?c∈C,c是TGAC 的,故N是TGAC 的.證畢.□

1.2 線程池

線程池是一種多線程處理形式,管理一組線程,以便并行處理大量任務(wù).在需要多次使用線程的并行程序中,單獨(dú)創(chuàng)建與銷毀線程會增加運(yùn)行開銷,從而影響程序的整體性能.而線程池通過限制線程的數(shù)量和重用線程,能夠避免創(chuàng)建與銷毀線程的代價(jià),還可以提高程序的穩(wěn)定性.

本文使用的是工作竊取線程池,其中每個(gè)線程都有一個(gè)獨(dú)立的任務(wù)隊(duì)列,主線程將任務(wù)分配到各個(gè)線程的任務(wù)隊(duì)列中.工作竊取是指如果某個(gè)線程完成了其隊(duì)列中的所有任務(wù),而其他線程的隊(duì)列中還有未處理任務(wù),那么空閑線程可以竊取其他線程的未處理任務(wù),從而改善了并行程序的負(fù)載均衡.

1.3 位向量

位向量是由若干個(gè)位(bit)組成的向量,具有存儲空間占用少和處理速度快的特點(diǎn).在構(gòu)建一個(gè)CP 求解器時(shí),位向量是變量論域的重要表示方式之一[13].另外,維持表約束GAC 的串行過濾算法STRbit[8]和CT[9]正是通過使用位向量才得以大幅度地加快過濾速度.

為了便于說明位向量的數(shù)據(jù)結(jié)構(gòu)及其操作,我們用v表示位向量.位向量v由m個(gè)位組成,其第i個(gè)位由v[i]表示.特別地,0b 和1b 分別表示位的二進(jìn)制取值.

本文共涉及以下6 種有關(guān)位向量的基本操作.

(1)位賦值操作:將位向量的某個(gè)位賦值為0b 或1b,如v[i]:=0b;

(2)位判等操作:判斷位向量的某個(gè)位是否為0b 或1b,如v[i]=0b;

(3)位向量賦值操作:對位向量的整體進(jìn)行賦值,如v:=0 是將位向量v的每個(gè)位均賦值為0b;又如,v:=v′是將位向量v′整體賦值給位向量v;

(4)位向量判等操作:判斷位向量的整體取值,如v=0 是判斷位向量v中每個(gè)位是否均為0b;

(5)位向量按位或操作:將兩個(gè)位向量的對應(yīng)位進(jìn)行或運(yùn)算,如v|v′;

(6)位向量按位與操作:將兩個(gè)位向量的對應(yīng)位進(jìn)行與運(yùn)算,如v&v′.

例2:位向量v和v′均由8 個(gè)位組成,它們的取值及經(jīng)過v:=v&v′操作的結(jié)果如圖1所示.

Fig.1 Bit vectors and their operations圖1 位向量及其操作

在本文的相關(guān)算法中,我們用位向量bitdom(x)和bitdomc(x)分別表示變量x的論域dom(x)和x在約束c中的局部中間論域domc(x).設(shè)x的初始論域D(x)?[1,M],那么bitdom(x)和bitdomc(x)均由M個(gè)位組成.bitdom(x)[a]為1b 當(dāng)且僅當(dāng)a∈dom(x),bitdom(x)為0 當(dāng)且僅當(dāng)dom(x)為空.同理,bitdomc(x)[a]為1b 當(dāng)且僅當(dāng)a∈domc(x),bitdomc(x)為0 當(dāng)且僅當(dāng)domc(x)為空.

2 串行傳播模式

維持表約束網(wǎng)絡(luò)GAC 的串行傳播模式由串行傳播算法和串行過濾算法兩部分組成,本節(jié)將依次介紹這兩部分算法,并分析串行傳播模式的相關(guān)性質(zhì).

2.1 串行傳播算法

求解CSP 實(shí)例的常用方法是回溯搜索,回溯搜索是一種完整方法,它通過系統(tǒng)地探索實(shí)例的搜索空間,可找到全部的解或者證明無解存在.MAC(maintaining arc consistency)算法[14]是一種在搜索過程中維持約束網(wǎng)絡(luò)GAC 的回溯搜索算法,目前被認(rèn)為是求解CSP 實(shí)例最有效的完整方法.在MAC 算法中,當(dāng)初始化約束網(wǎng)絡(luò)、一個(gè)變量被賦值或者一個(gè)變量被刪值時(shí),串行傳播算法會被調(diào)用執(zhí)行,以維持約束網(wǎng)絡(luò)GAC.

常用的串行傳播算法之一是面向變量的串行傳播算法[15,16],面向變量是指傳播集合中保存引發(fā)傳播的變量.針對不同類型的過濾算法,面向變量的串行傳播算法會有所不同.我們使用的串行傳播算法[17]具體見算法1和算法2.

算法1.serialPropagate(Xevt:set of variables):Boolean.

在算法1 中,Q是一個(gè)變量集合,保存引發(fā)傳播的變量,即:當(dāng)一個(gè)變量的論域被刪值時(shí),該變量會被添加至Q中.串行傳播算法通過使用時(shí)間戳來避免不必要的工作,時(shí)間戳是一個(gè)值,表示某個(gè)事件發(fā)生的時(shí)間.變量x的時(shí)間戳stamp(x)表示最近一次從dom(x)中刪除值的時(shí)間,約束c的時(shí)間戳stamp(c)表示最近一次在c上維持GAC的時(shí)間.時(shí)間通過計(jì)數(shù)器time來模擬.time,stamp(x)和stamp(c)均被初始化為0.

算法1 的傳入?yún)?shù)Xevt是引發(fā)初始傳播的變量集合,其中的變量會被添加至Q中.算法1 第6 行從Q中選出一個(gè)變量x后,對包含x的每個(gè)約束c,如果stamp(x)大于stamp(c),算法1 第8 行會執(zhí)行在c上維持GAC 的串行過濾算法.串行過濾算法會返回由被刪值的變量組成的集合,并且如果有一個(gè)變量的論域被刪空,串行過濾算法會將不相容標(biāo)識inconsistent置為true,之后,inconsistent會在算法1 第9 行被識別出,這表明傳播失敗,當(dāng)前表約束網(wǎng)絡(luò)無解,MAC 算法發(fā)生回溯.當(dāng)Q中的所有變量均被選出傳播后,并且傳播期間沒有變量的論域被刪空,這表明傳播成功,當(dāng)前表約束網(wǎng)絡(luò)是GAC 的,MAC 算法繼續(xù)搜索.

2.2 串行過濾算法

如前文所述,維持表約束GAC 的串行過濾算法研究已經(jīng)公布了大量成果,它們的設(shè)計(jì)實(shí)現(xiàn)雖然有所不同,但主要由更新表(算法4)和過濾論域(算法5)兩部分組成.我們總結(jié)了它們的共同之處,具體見算法3~算法5.

算法3.enforceGAC(c):set of variables.

算法5.filterDomains(c):set of variables.

算法3 中,串行過濾算法首先更新表,即移除無效的元組(算法4 第4 行);進(jìn)而過濾論域,即刪除在該約束上不存在支持的值(算法5 第5 行);最后返回由被刪值的變量所組成的集合.如果有一個(gè)變量x的論域被刪空,即bitdom(x)的每個(gè)位均變?yōu)?b,不相容標(biāo)識inconsistent將被置為true(算法5 第8 行).

2.3 性質(zhì)分析

因?yàn)椴煌拇羞^濾算法有不同的最壞時(shí)間復(fù)雜度,所以它們的最壞時(shí)間復(fù)雜度被統(tǒng)一設(shè)為O(T).另外,我們用rmax和dmax分別表示最大的約束元數(shù)和最大的初始論域大小,即rmax=maxc∈C|scp(c)|,dmax=maxx∈X|D(x)|.

性質(zhì)4.維持表約束網(wǎng)絡(luò)GAC 的串行傳播模式的最壞時(shí)間復(fù)雜度為O(ermaxdmaxT)[17].

證明:串行傳播算法中,初始化變量集合Q的時(shí)間代價(jià)為O(n)(算法1 第2 行、第3 行).對于x∈scp(c),每當(dāng)一個(gè)值(x,a)被刪除后,約束c會被執(zhí)行一次維持GAC 的串行過濾算法,那么約束集C中的所有約束被執(zhí)行串行過濾算法的總次數(shù)最多為ermaxdmax(算法1 第7 行).而執(zhí)行一次串行過濾算法的時(shí)間代價(jià)為O(T)(算法1 第8 行),將串行過濾算法返回的變量集并入Q的時(shí)間代價(jià)為O(rmax)(算法1 第11 行、第12 行),并且其他所有語句的時(shí)間代價(jià)均為O(1),所以串行傳播模式的總體時(shí)間代價(jià)為O(n+ermaxdmax(T+rmax)).又因?yàn)閚=O(ermax),且T>>rmax,故維持表約束網(wǎng)絡(luò)GAC 的串行傳播模式的最壞時(shí)間復(fù)雜度為O(ermaxdmaxT).證畢.□

3 并行傳播模式

在本節(jié)中,我們提出了維持表約束網(wǎng)絡(luò)TGAC 的并行傳播模式,它同樣由并行傳播算法和并行過濾算法兩部分組成.之后,我們分析了并行傳播模式的相關(guān)性質(zhì).

3.1 并行傳播算法

在并行傳播模式中,我們引入了一些新的數(shù)據(jù)結(jié)構(gòu).

?約束位標(biāo)識tableMask:由e個(gè)位組成的位向量,用以標(biāo)記需要執(zhí)行并行過濾算法的表約束,在并行傳播模式中是被動(dòng)態(tài)更新的.其第i個(gè)位用tableMask[ci]表示,tableMask[ci]為1b 當(dāng)且僅當(dāng)約束ci需要被執(zhí)行并行過濾算法;

?位訂閱bitSbp(x):由e個(gè)位組成的位向量,與變量x的約束訂閱集sbp(x)相對應(yīng),第i個(gè)位用bitSbp(x)[ci]表示,bitSbp(x)[ci]為1b 當(dāng)且僅當(dāng)x∈scp(ci).

通過tableMask:=tableMask|bitSbp(x)可將bitSbp(x)提交至tableMask上.

例3:約束網(wǎng)絡(luò)N的約束集C={c1,c2,...,c8},變量x和y的約束訂閱集分別為sbp(x)={c4,c8}和sbp(y)={c1,c8},相應(yīng)的位訂閱bitSbp(x)和bitSbp(y)如圖2所示.約束位標(biāo)識tableMask初始化為0(全部位均為0b),將bitSbp(x)提交至tableMask的操作及結(jié)果如圖2所示.

Fig.2 Bit subscriptions and their submission operations圖2 位訂閱及其提交操作

如前文所述,串行傳播算法根據(jù)變量傳播集合順次執(zhí)行對相關(guān)約束的過濾任務(wù)(算法1 第7 行、第8 行),我們將這一操作并行化,提出了并行傳播算法.并行傳播算法使用約束位標(biāo)識tableMask標(biāo)記相關(guān)的表約束,對這些表約束的過濾任務(wù)被動(dòng)態(tài)提交至線程池中并行執(zhí)行,直到發(fā)生了論域刪空事件或者沒有新的過濾任務(wù).具體見算法6.

算法6.parallelPropagate(Xevt:set of variables):Boolean.

算法6 的傳入?yún)?shù)Xevt同樣是引發(fā)初始傳播的變量集合,其中的變量被用于初始化約束位標(biāo)識tableMask(第2 行、第3 行).submitMask是一個(gè)保存tableMask的局部臨時(shí)標(biāo)識(第6 行),因?yàn)閠ableMask會被動(dòng)態(tài)更新,所以算法6 根據(jù)submitMask向線程池pool提交在約束c上維持TGAC 的并行過濾任務(wù)(第9 行、第10 行),之后需要等待它們完成(第11 行).在并行過濾任務(wù)的執(zhí)行期間,當(dāng)一個(gè)變量的論域被刪值后,論域改變標(biāo)識varChanged被置為true,并且tableMask被更新,以在算法6 的下次循環(huán)中向線程池pool提交新的并行過濾任務(wù);如果有一個(gè)變量的論域被刪空,不相容標(biāo)識inconsistent被置為true,之后會被識別出(第12 行),這表明傳播失敗(第13 行),當(dāng)前表約束網(wǎng)絡(luò)無解,MAC 算法發(fā)生回溯.如果所有的并行過濾任務(wù)被執(zhí)行完成后,varChanged仍為flase,即沒有發(fā)生刪值事件,那么循環(huán)結(jié)束,這表明傳播成功(第15 行),當(dāng)前表約束網(wǎng)絡(luò)是TGAC 的,MAC 算法繼續(xù)搜索.

3.2 并行過濾算法

我們對維持表約束GAC 的串行過濾算法進(jìn)行擴(kuò)展,得到了維持表約束TGAC 的并行過濾算法(算法7),如PSTR2,PSTR3,PSTRbit 和PCT,并進(jìn)行了一般化總結(jié),它們同樣主要由更新表(算法8)和過濾論域(算法9)兩部分組成.

算法7.enforceTGAC(c).

算法8.updateTTable(c).

Table 2 Average results to solve instances from different series(STRbit and PSTRbit)表2 不同實(shí)例集的平均實(shí)驗(yàn)結(jié)果(STRbit 和PSTRbit)

算法9.filterTDomains(c).

與算法3 不同的是,算法7 首先判斷不相容標(biāo)識inconsistent是否為真:如果為真,算法7 返回,即所有的線程能夠及時(shí)終止并行過濾任務(wù);如果為假,算法7 將每個(gè)變量x∈scp(c)在c中的局部中間論域bitdomc(x)更新至最新的bitdom(x);然后,算法7 更新表,即移除無效的元組(算法8 第4 行);最后,算法7 過濾論域,即先從局部中間論域bitdomc(x)中刪除在該約束上不存在臨時(shí)支持的值(算法9 第4 行).若局部中間論域bitdomc(x)被刪值,算法9便將bitdom(x)與bitdomc(x)的按位與結(jié)果賦值給bitdom(x),即從bitdom(x)中刪除不存在于bitdomc(x)中的值(算法9 第6 行).進(jìn)一步地,如果bitdom(x)被刪空,即bitdom(x)的每個(gè)位均為0b,全局不相容標(biāo)識inconsistent被置為true(算法9 第8 行),并行過濾算法結(jié)束;否則,論域改變標(biāo)識varChanged被置為true(算法9 第10 行),并且變量x的位訂閱bitSbp(x)被提交至約束位標(biāo)識tableMask上(算法9 第11 行),即與x有關(guān)的約束c需要參與下一次并行傳播.

多個(gè)線程在并行執(zhí)行對不同表約束的并行過濾算法時(shí),可能會同時(shí)過濾同一個(gè)變量x的論域bitdom(x)(算法9 第6 行),也可能會同時(shí)更新約束位標(biāo)識tableMask(算法9 第11 行),所以我們對這兩種操作采用了非阻塞同步方式,通過比較并替換(compare and swap,簡稱CAS)實(shí)現(xiàn),以確保并行過濾算法的正確性.

例4:表約束c1,c2∈sbp(x)被兩個(gè)線程并行執(zhí)行維持TGAC 的并行過濾算法,兩個(gè)線程同時(shí)過濾變量x的論域bitdom(x),過程及結(jié)果如圖3所示.

Fig.3 Parallel filtering algorithm execution instance圖3 并行過濾算法執(zhí)行實(shí)例

3.3 性質(zhì)分析

首先,我們給出并行傳播模式的可靠性證明.

性質(zhì)5.維持表約束網(wǎng)絡(luò)TGAC 的并行傳播模式也維持表約束網(wǎng)絡(luò)GAC.

證明:一方面,如果取值(x,a)不是GAC 的,即?c0∈sbp(x),c0中沒有對(x,a)的支持,那么當(dāng)c0被執(zhí)行維持TGAC的并行過濾算法時(shí),scp(c0)內(nèi)各變量的局部中間論域均被更新(算法7 第3 行、第4 行),因此c0中也沒有對(x,a)的臨時(shí)支持,(x,a)不是TGAC 的,會被刪除(算法9 第4 行、第6 行).

另一方面,如果取值(x,a)是GAC 的,那么?c∈sbp(x),當(dāng)scp(c)內(nèi)各變量的局部中間論域均被更新后(算法7第3 行、第4 行),有?y∈scp(c),domc(y)=dom(y).由性質(zhì)1 可知,(x,a)是TGAC 的,會被保留.

綜上所述,維持表約束網(wǎng)絡(luò)TGAC 的并行傳播模式也維持表約束網(wǎng)絡(luò)GAC.證畢.□

接下來,我們對并行傳播模式的最壞時(shí)間復(fù)雜度進(jìn)行分析.通過對比串行過濾算法,因?yàn)椴⑿羞^濾算法中所增加的操作語句均有著O(rmax)(算法7 第3 行、第4 行)或O(1)的時(shí)間代價(jià),并且T>>rmax,所以并行過濾算法的最壞時(shí)間復(fù)雜度也為O(T).線程池的并行度用p表示,即線程池內(nèi)存在p個(gè)線程.另外,每個(gè)并行過濾任務(wù)被提交至線程池之后,在線程池中還會有被調(diào)度的時(shí)間代價(jià),我們將其設(shè)為O(Sp),Sp隨著并行度p的增大而增大.

性質(zhì)6.維持表約束網(wǎng)絡(luò)TGAC 的并行傳播模式的最壞時(shí)間復(fù)雜度為O(ermaxdmax(Sp+T)/p).

證明:并行傳播算法中初始化約束位標(biāo)識tableMask的時(shí)間代價(jià)為O(n)(算法6第2 行、第3行)且n=O(ermax).對于x∈scp(c),每當(dāng)一個(gè)值(x,a)被刪除后,約束c會被執(zhí)行一次維持TGAC 的并行過濾算法,那么約束集C中的所有約束被執(zhí)行并行過濾算法的總次數(shù)最多為ermaxdmax(算法6 第9 行).而每個(gè)并行過濾任務(wù)在線程池中被調(diào)度的時(shí)間代價(jià)為O(Sp),執(zhí)行一次并行過濾算法的時(shí)間代價(jià)為O(T)(算法6 第10 行),并且其他所有語句的時(shí)間代價(jià)均為O(1),所以并行過濾任務(wù)的總體時(shí)間代價(jià)為O(ermaxdmax(Sp+T)).又因?yàn)椴⑿羞^濾任務(wù)可被p個(gè)線程并行執(zhí)行,所以維持表約束網(wǎng)絡(luò)TGAC 的并行傳播模式的最壞時(shí)間復(fù)雜度為O(ermaxdmax(Sp+T)/p).證畢.□

當(dāng)并行度p>1 時(shí),通過對比串行傳播模式的最壞時(shí)間復(fù)雜度O(ermaxdmaxT)和并行傳播模式的最壞時(shí)間復(fù)雜度O(ermaxdmax(Sp+T)/p),我們認(rèn)為:若T>>Sp,那么O(ermaxdmax(Sp+T)/p)≈O(ermaxdmaxT/p),即并行傳播模式在平均過濾時(shí)間較長的實(shí)例上相對串行傳播模式能夠取得較為明顯的加速;若T<

4 實(shí)驗(yàn)結(jié)果

我們在22 組CSP 實(shí)例集上使用MAC 算法分別測試了串行傳播模式和并行傳播模式.在串行傳播模式下,串行過濾算法分別使用CT 和STRbit;在并行傳播模式下,并行過濾算法分別使用PCT 和PSTRbit,線程池的并行度p依次被置為2,4 和6.MAC 算法采用dom/ddeg變量啟發(fā)式和min 值啟發(fā)式,dom/ddeg是穩(wěn)定的變量啟發(fā)式,能讓兩種傳播模式在求解同一實(shí)例時(shí)擁有相同的變量選取順序,進(jìn)而實(shí)現(xiàn)公平的效率對比.每個(gè)實(shí)例的搜索時(shí)間上限為900 秒.實(shí)驗(yàn)環(huán)境為Intel Core i7 3.40GHz(4 cores)8GB RAM Windows10 64bit OS,程序編寫語言是Java11.0.3 和Scala2.12.8.所有的實(shí)例集均來自http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html,我們的測試代碼可在https://github.com/amtfjlsj/lotus 上獲取.

表1 和表2 給出了不同實(shí)例集的平均實(shí)驗(yàn)結(jié)果,實(shí)例集中,未超時(shí)的實(shí)例個(gè)數(shù)用#表示.time 表示求解實(shí)例所需的平均傳播時(shí)間(單位s),每個(gè)實(shí)例集對應(yīng)的最短平均傳播時(shí)間被加粗;filt 表示在求解實(shí)例的過程中過濾算法被調(diào)用的平均次數(shù)(單位10 萬);avg 表示執(zhí)行一次串行過濾算法的平均時(shí)間(單位μs),即實(shí)例集的平均過濾時(shí)間,我們使用串行傳播模式下time 與filt 的比值作為avg 的近似值;speed 是并行傳播模式相對于串行傳播模式的平均傳播時(shí)間加速比,即串行平均傳播時(shí)間與并行平均傳播時(shí)間的比值.

首先,我們比較一下串行傳播模式和并行傳播模式的實(shí)驗(yàn)結(jié)果.在17 組實(shí)例集上,并行傳播模式要快于串行傳播模式,而且在多數(shù)實(shí)例集上取得了從1.4~3.4 不等的加速比;在另外5 組實(shí)例集上,并行傳播模式的表現(xiàn)不如串行傳播模式.從各實(shí)例集在串行傳播模式下的平均過濾時(shí)間avg 可以看出:取得較好加速比的實(shí)例集,其avg 普遍較大,如rand-10-60,ogd,uk 和MDD0.9 等;并行傳播效果不好的實(shí)例集,其avg 普遍較小,如aim-50,aim-100 和dubois 等.這與第3.3 節(jié)性質(zhì)6 的分析相一致.因此,我們提出的并行傳播模式適用于平均過濾時(shí)間avg較大的實(shí)例.

并行傳播模式在多數(shù)實(shí)例集上取得了較好的加速比,但是沒有實(shí)現(xiàn)線性加速(加速比與并行度相等),原因主要有兩點(diǎn).

?在求解實(shí)例的過程中,并行過濾算法被調(diào)用的平均次數(shù)filt 多于串行過濾算法被調(diào)用的平均次數(shù)filt.

雖然并行傳播模式有多個(gè)線程并行執(zhí)行過濾算法,但其工作總量并不與串行傳播模式的工作總量相等,而是隨著線程的增多而增加.這是因?yàn)樵诓⑿袀鞑ツＪ较?線程之間不能相互通信.對表約束c執(zhí)行并行過濾算法的線程只在初始時(shí)更新變量x∈scp(c)在c中的局部中間論域bitdomc(x),到算法結(jié)束前不再獲取最新的bitdom(x).那么在此過程中,如果其他線程刪除了bitdom(x)中的值,c需要被重新執(zhí)行一次并行過濾算法以獲取最新的bitdom(x).這種現(xiàn)象在過濾算法被順次執(zhí)行的串行傳播模式中是不存在的.

例5:現(xiàn)有兩個(gè)表約束c1和c2,其中,scp(c1)={x,y},scp(c2)={x,z,u}.假設(shè)取值(y,a)和(z,a)被其他表約束刪除,這導(dǎo)致c1和c2被執(zhí)行過濾算法.在串行傳播模式下,首先線程t對c1執(zhí)行串行過濾算法,t從bitdom(x)中刪除了(x,a);之后,在t對c2執(zhí)行串行過濾算法時(shí),(x,a)的移除導(dǎo)致t從bitdom(u)中刪除了(u,a).在并行傳播模式下,c1和c2同時(shí)被兩個(gè)線程t1和t2分別執(zhí)行并行過濾算法:首先,bitdomc1(x)和bitdomc2(x)被更新至最新的bitdom(x);之后,t1從bitdom(x)中刪除了(x,a),但(x,a)仍存在于bitdomc2(x)中,因此t2沒有從bitdom(u)中刪除(u,a);因?yàn)?x,a)的刪除,c1和c2需要再次被t1和t2分別執(zhí)行并行過濾算法,其中,t2將bitdomc2(x)更新至最新的bitdom(x),進(jìn)而從bitdom(u)中刪除了(u,a).過程如圖4所示,同樣的情況下,串行過濾算法被執(zhí)行了2 次,而并行過濾算法被執(zhí)行了4 次.

Fig.4 An example of serial propagation mode versus parallel propagation mode圖4 串行傳播模式與并行傳播模式的對比實(shí)例

?并行傳播進(jìn)程中線程利用率并不總是100%.

線程利用率是活躍線程數(shù)與并行度的比率,活躍線程是指正在運(yùn)行任務(wù)的線程.我們在求解一個(gè)實(shí)例的并行傳播(并行度p為4)進(jìn)程中獲取了活躍線程的數(shù)目,其隨時(shí)間點(diǎn)的關(guān)系如圖5所示:一方面,并行傳播模式也存在串行分量,比如算法6 除第9 行~第11 行之外的部分,在執(zhí)行這部分串行分量時(shí),活躍線程只有1 個(gè),線程利用率為25%;另一方面,當(dāng)線程池中的并行過濾任務(wù)數(shù)小于并行度時(shí),活躍線程數(shù)將等于任務(wù)數(shù),線程利用率小于100%.

Fig.5 Number of active threads in a parallel propagation process圖5 并行傳播進(jìn)程中的活躍線程數(shù)

最后,我們對比一下并行傳播模式在不同并行度p下的平均傳播時(shí)間.p為4 的并行傳播模式在大多數(shù)實(shí)例集上均快于p為2 的并行傳播模式,但p為6 的并行傳播模式在多數(shù)實(shí)例集上卻不如p為4 的并行傳播模式.我們認(rèn)為:實(shí)驗(yàn)環(huán)境的CPU 為4 核處理器,因此當(dāng)并行度高于核數(shù)時(shí),并行傳播進(jìn)程中會出現(xiàn)多個(gè)線程搶占同一個(gè)核的情況,從而導(dǎo)致平均傳播時(shí)間變長.

5 總結(jié)

在本文中,首先,我們提出了維持表約束網(wǎng)絡(luò)TGAC 的并行傳播模式,該模式基于多核CPU,由并行傳播算法和并行過濾算法兩部分組成,并行傳播算法利用線程池并行執(zhí)行維持表約束TGAC 的并行過濾算法;之后,我們給出了并行傳播模式的可靠性證明,即并行傳播模式也維持表約束網(wǎng)絡(luò)GAC;另外,通過對并行傳播模式的最壞時(shí)間復(fù)雜度分析,我們認(rèn)為并行傳播模式在平均過濾時(shí)間較長的實(shí)例上要快于串行傳播模式,最終的實(shí)驗(yàn)結(jié)果也驗(yàn)證了這一結(jié)論.

基于本文的思路,我們認(rèn)為未來的研究可從以下3 個(gè)方面繼續(xù)開展.

1)我們在實(shí)驗(yàn)分析中給出了兩點(diǎn)關(guān)于并行傳播模式?jīng)]有實(shí)現(xiàn)線性加速的原因,因此未來的研究可嘗試通過減少并行傳播模式的工作總量或提高線程利用率,來進(jìn)一步提升并行傳播的效率;

2)維持表約束GAC 的串行過濾算法研究除了基于簡單表縮減,還有很多基于其他設(shè)計(jì)思想的成果,比如泛型過濾算法系列(GAC2001[18],GAC3rm[19],GAC4R[20]等)和壓縮表示過濾算法系列(MDDc[21],MDD4R[20],AdaptiveMDDc[11]等),這些串行過濾算法均可轉(zhuǎn)化成維持表約束TGAC 的并行過濾算法;

3)在相容性理論方面,刪值能力強(qiáng)于GAC 的相容性被稱為高階相容性,如最大限制成對相容性(max restricted pairwise consistency,簡稱maxRPWC)和成對相容性(pairwise consistency,簡稱PWC).維持表約束網(wǎng)絡(luò)高階相容性的串行傳播模式設(shè)計(jì)受到了很多研究工作的關(guān)注[22?24],因此未來的研究可嘗試設(shè)計(jì)實(shí)現(xiàn)維持表約束網(wǎng)絡(luò)高階相容性的并行傳播模式.