基于共享內(nèi)存的并行LDA算法

楊　?！陨睢¤础澜ǚ?/p>

(蘇州大學計算機科學與技術(shù)學院　江蘇 蘇州 215006)

?

基于共享內(nèi)存的并行LDA算法

楊希劉曉升楊璐嚴建峰*

(蘇州大學計算機科學與技術(shù)學院江蘇 蘇州 215006)

現(xiàn)有的共享內(nèi)存的并行潛在狄利克雷分配(LDA)主題模型，通常由于數(shù)據(jù)分布的原因，線程之間一般存在等待導(dǎo)致效率低下。針對線程等待問題進行研究，提出一種基于動態(tài)的線程調(diào)度方案。該方案能夠根據(jù)線程的數(shù)量進行分塊，在此基礎(chǔ)上及時為空閑的線程動態(tài)地分配任務(wù)，從而減少線程間等待時間。實驗表明，這種新的調(diào)度方案能夠有效地解決線程等待問題。該方案不僅在保證收斂精度的同時能夠獲得加速比25%的提升，還能顯著提高向上擴展比。對于大規(guī)模分布式集群上單個節(jié)點的并行LDA算法來說，這種調(diào)度可以更有效地利用計算資源。

潛在狄利克雷分配共享內(nèi)存并行動態(tài)調(diào)度

0　引　言

潛在狄利克雷分配(LDA)是現(xiàn)下非常流行的一種概率主題模型，自從2003年由Blei[1]等人提出以后，在文本挖掘，計算機視覺以及計算生物學等方面有著很好的應(yīng)用。LDA已經(jīng)被認為是分析大規(guī)模的非結(jié)構(gòu)化文檔集合的最有效的工具。LDA常用的近似推理方法有三種，吉布斯采樣GS(GibbsSampling)[2]、變分貝葉斯VB(VariationalBayes)[3]、置信傳播BP(BeliefPropagation)[4]，其中精度最好的就是置信傳播算法。隨著近年來大數(shù)據(jù)的普及，單機單核版本的計算已經(jīng)無法滿足日益增加的數(shù)據(jù)處理需求，而并行計算就是最好的解決方案之一。而并行計算可以分為共享內(nèi)存以及非共享內(nèi)存兩個方面。對于共享內(nèi)存我們有多線程并行計算的OpenMP等，對于非共享內(nèi)存的我們有消息傳遞機制MPI(MessagePassingInterface)，以及hadoop，spark等平臺。相對于非共享內(nèi)存的并行計算，共享內(nèi)存并行計算具有在多核或多CPU結(jié)構(gòu)上效率高、內(nèi)存開銷小的優(yōu)勢。通常大規(guī)模的分布式集群就是將非共享內(nèi)存與共享內(nèi)存的并行算法進行混合編程，實現(xiàn)多主機與單機之間的優(yōu)勢互補。但是由于內(nèi)存的共享，導(dǎo)致不同線程之間存在著讀取寫入的沖突，而通過“鎖”這種方式雖然能夠一定程度上解決沖突問題，但是依然會導(dǎo)致線程之間相互等待的問題。

本文基于共享內(nèi)存的方式，在LINUX操作系統(tǒng)使用g++的編譯環(huán)境，利用std中的thread模塊來靈活地調(diào)動線程，通過動態(tài)調(diào)度線程來消除線程等待時間，實驗表明，動態(tài)調(diào)度的線程能夠顯著提高算法的效率以及并行的加速比。

1　相關(guān)工作

非共享內(nèi)存與共享內(nèi)存這兩種不同的并行框架，其本質(zhì)的區(qū)別的就是對于內(nèi)存的使用。對于非共享內(nèi)存的方法，相對來說已經(jīng)非常成熟了，從Newman等人提出近似分布LDA(AD-LDA)[5]開始，異步通信的異步分布LDA(AS-LDA)[6]，使用MapReduce實現(xiàn)的Parallel-LDA(PLDA)[7]，以及與AS-LDA完全不同的PLDA+[8]、Mr.LDA[9]的相繼提出，非共享內(nèi)存的LDA計算方法上得到了很好的擴充。

而對于共享內(nèi)存的LDA，2007年的Yan[10]等人提出了將數(shù)據(jù)進行二維切分。這種分割方式，讓數(shù)據(jù)能夠在小內(nèi)存的GPU上進行計算。通過這種數(shù)據(jù)流的方式來避免數(shù)據(jù)的沖突，從而實現(xiàn)了共享內(nèi)存的并行LDA計算。GPU使得共享內(nèi)存的LDA使用成百上千線程進行并行計算變成了可能，但是GPU的核心只能處理簡單的計算，而且GPU本身的成本相對較高。而后，Yahoo!LDA[11]提出了一種黑板結(jié)構(gòu)的memcached技術(shù)，通過分布式的共享緩存服務(wù)，使得LDA的參數(shù)矩陣保存共享狀態(tài)。同時通過加鎖的方式來解決兩個或兩個以上訪問同一個內(nèi)存塊會導(dǎo)致嚴重的訪問沖突。但是加鎖的方式依舊會導(dǎo)致線程間會產(chǎn)生等待的問題。

2　LDA模型

LDA模型是一個無監(jiān)督的概率生成模型[2]。模型假設(shè)文檔集合是由有D篇文檔組成的，該集合共有K個隱含的主題，其文檔的生成過程如下：

θd～Dir(α)φk～Dir(β)

(1)

首先我們從β的狄利克雷分布中獲得每個主題上單詞的概率分布φk，重復(fù)K次。

圖1　LDA圖模型

然后對于每一篇文檔d，我們從α的狄利克雷分布中獲取文檔d上主題的概率分布θd，而zn是滿足概率分布為θd的多項式分布的，我們可以通過θd中采樣獲得該文檔的一個主題zn。在這里zn就是φk中的k，而我們知道wn是滿足φk的多項式分布的，我們可以通過φk獲得單詞wn。重復(fù)以上過程N次，就是LDA中一篇文檔的生成過程。其圖模型如1所示。

3　基于共享內(nèi)存的并行LDA

圖2　互不沖突的塊

對于一般的共享內(nèi)存的并行LDA算法解決內(nèi)存沖突的辦法就是分塊(blocks)，通過為每一個線程劃分出處理的范圍，從而達到互不干擾的目的。如GPU-LDA中就是將文檔劃分為J={1，z,…，D}，將單詞劃分為V={1，z,…，W}，將互不沖突的塊，分配給不同的線程。如圖2所示。

我們可以看到，在這里的每個塊，都是互不沖突的。即相互之間不存在相同的單詞或者文檔序列。

本文主要選取了BP算法作為主要的比較對象的原因是，BP算法在精度上有較大的優(yōu)勢，同時BP算法中不同文檔之間是完全獨立的。 另外一個原因是BP算法有相應(yīng)的在線版本OBP(Online Belief Propagation)，以及主動版本ABP(Active Belief Propagation)[12]等，有利于本文中調(diào)度方法后續(xù)的擴展。

在這里我們將一般的并行LDA算法稱為PBP(Parallel Belief Propagation)。其中μw,d表示文檔d中單詞w的主題分布。具體算法過程如下：

算法1并行LDA(PBP)重復(fù):1. Forl=0toT-1do:2. ForeachthreadTinparalleldo:3. 獲取文檔集d=Jt⊕l,獲取單詞集w=Vt⊕l4. 通過全局的θd,?w更新μw,d5. Endfor6. Endfor7. 同步,更新全局的θ,?直到達到停止條件

對于每一次迭代，不同的線程之間是并行計算的。這里t⊕l表示t+lmodT，這保證了各個線程之間是相互獨立不發(fā)生數(shù)據(jù)上的沖突的。在每個線程中都可以獨立更新那一部分的μw,d，當所有的分塊都計算完畢之后，我們再同步更新全局的θ和φ。當然在這里我們可以把中間的步驟換成任何一個LDA近似推斷的方法也是可以的。

4　并行算法的調(diào)度優(yōu)化

可以發(fā)現(xiàn)，傳統(tǒng)的調(diào)度方法是通過為每個線程分配固定的非沖突任務(wù)來實現(xiàn)線程獨立，進而來避免讀寫數(shù)據(jù)沖突。然而這種方法在數(shù)據(jù)分布不均勻時(大部分時候數(shù)據(jù)的分布并不是均勻的)，就會造成不同線程之間任務(wù)的分配不均勻。這樣最終導(dǎo)致的后果就是同步更新時，大多數(shù)線程需要等待某個任務(wù)最重(運行時間最長)的線程。

對此我們首先對數(shù)據(jù)進行隨機洗牌[13]，即對單詞以及文檔的序列進行隨機的調(diào)換位序，這樣可以一定程度上使得數(shù)據(jù)分布均勻(本文所有數(shù)據(jù)都由隨機洗牌進行預(yù)處理)。另外就是不再為每個線程安排固定的任務(wù)，每當有線程呈現(xiàn)空閑狀態(tài)的時候，可以通過調(diào)度獲得與當前運行線程不產(chǎn)生沖突的任務(wù)塊，直到當前次迭代任務(wù)完結(jié)需要進行同步更新為止，這種動態(tài)的調(diào)度處理，可以讓每個線程在當前迭代過程中均為滿負載運算。

圖3是2個線程的動態(tài)調(diào)度示例，也就是我們動態(tài)調(diào)度的基本原理。將數(shù)據(jù)進行隨機洗牌后，我們將數(shù)據(jù)分割成4P2塊。當某個線程完成當前數(shù)據(jù)塊的計算之后，能夠迅速為空閑的線程找到一個與其他當前運行線程不會產(chǎn)生讀寫沖突的塊，將之分配給該線程之后進行計算。例如：我們開始將1號塊分給1號線程，而將6號塊分給2號線程。當2號線程結(jié)束在6號塊的計算時，1號線程還在進行1號塊的計算。此時我們?yōu)?號線程分配了8號塊，這是個與1號塊不會產(chǎn)生沖突的塊。當1號塊的計算完畢之后，我們又為1號線程分配了14號塊，此時2號線程依然在進行8號塊的計算，依次類推直到所有的塊都計算完畢。

圖3　動態(tài)調(diào)度的線程

我們可以看到，2個線程在整個過程中沒有等待時間的滿負載運行。同時我們也可以注意到，不同的數(shù)據(jù)塊，由于數(shù)據(jù)分布的問題，其計算時間也是不同的。比如，1和9號塊，其計算時間差不多相差一倍。如果還是通過硬性分配的話，線程之間的等待時間無疑會是一個巨大的浪費。我們通過線程之間的動態(tài)調(diào)度，消除了等待時間。

我們稱動態(tài)調(diào)度的并行算法為DPBP(DynamicParallelBeliefPropagation)，其中R為訓練數(shù)據(jù)集，P為線程數(shù)，其余變量與算法1中相同，其計算方法如下：

算法2加速優(yōu)化并行LDA(DPBP)將數(shù)據(jù)R分為4P2塊{R0,...,R4P2-1}重復(fù):1. While(notallblocksfinished)2. Getonefreethreaddo:3. GetonefreeblockRi4. 由Ri獲取文檔集d=Ji,獲取單詞集w=Vi5. 通過全局的θd,?w更新μw,d6. Endfor7. Endfor8. 同步,更新全局的θ,?直到達到停止條件

5　實驗分析

5.1實驗環(huán)境與數(shù)據(jù)集

本文基于單機多核服務(wù)器進行實驗，該服務(wù)器有2個IntelXeonX5690 3.47GHz的CPU，每個CPU有6個核，總計12個核，140GB內(nèi)存。在這里，為了保證并行效率，我們最多使用了12個線程進行實驗。本文使用的兩個數(shù)據(jù)集，分別是ENRON和NYTIMES，具體統(tǒng)計，概括統(tǒng)計實驗用的三個數(shù)據(jù)集，這里D是文檔的總數(shù)目，W是單詞表的大小，NNZ表示總共有多少條記錄，也就是非零數(shù)據(jù)的數(shù)量。具體如下：

表1　數(shù)據(jù)集

實驗先驗參數(shù)初始化都設(shè)置為α=0.01，β=0.01，由于主題數(shù)對我們并行LDA實驗沒有任何影響，故我們在這里統(tǒng)一將主題數(shù)K設(shè)置為100。本文中所有實驗都是以主題數(shù)為100來進行計算的。

我們的實驗將表1中的數(shù)據(jù)切割出1/5文檔作為測試集，其余部分作為訓練集。實驗將表1中的數(shù)據(jù)在訓練集上求得模型，在測試集上得到測試混淆度結(jié)果。同時為了滿足向上擴展比的計算，本文將相對較大的數(shù)據(jù)集NYTIMES另外分出10到120MB(10，20，40，60，80，100，120)不同大小的7個小的數(shù)據(jù)集，而ENRON則是另外分出1到12MB(1，2，4，6，8，10，12)的7個數(shù)據(jù)集。

本文對基于共享內(nèi)存的并行LDA即PBP進行線程調(diào)度上的優(yōu)化，新的算法記為DPBP。

5.2評價標準

本文主要采用了混淆度，加速比以及縱向擴展比來評價算法的效果。其中混淆度，經(jīng)常被用于語言模型之中，用來衡量語料庫建模能力的好壞，混淆度的計算公式如下:

(2)

此處xw,d表示文檔d中單詞w的詞頻。其余變量與前文相同。越低的混淆度表示越好的泛化能力。

加速比通常用于評價并行的能力，加速比越高，說明并行能力越好。加速比其實也可以認為是并行資源的利用率。

縱向擴展比則是，在數(shù)據(jù)大小發(fā)生變化時，通過增加相應(yīng)的線程，對并行算法效率的提升，也可以說是算法的泛化能力的一種比較。比如使用1個線程計算1MB的數(shù)據(jù)的時間和10個線程計算10MB數(shù)據(jù)的時間肯定是有差距的，其比值就是縱向擴展比?？v向擴展比越小，其泛化能力越好。

5.3實驗結(jié)果分析

(1) 收斂效果比較

圖4和圖5是DPBP與PB在NYTIMES數(shù)據(jù)集以及ENRON數(shù)據(jù)集上收斂曲線的比較。

圖4　DPBP與PBP在NYTIMES　　數(shù)據(jù)集上的收斂比較

圖5　DPBP與PBP在ENRON　　數(shù)據(jù)集上的收斂比較

表2是我們在2個數(shù)據(jù)集上的綜合比較，表示的是2個算法在不同的數(shù)據(jù)集的測試集上的收斂精度。

表2　DPBP與PBP的訓練集集收斂時間與測試集收斂的混淆度

可以較明顯的看出，DPBP算法不僅具有更快的收斂速度，同時其收斂精度與原算法并沒有太大的差別。相對于PBP，DPBP并不會在本質(zhì)上改變算法，只是通過調(diào)度改變了數(shù)據(jù)的計算順序，通過減少調(diào)度時間，DPBP不僅能夠?qū)炔划a(chǎn)生影響并且能夠顯著地提升收斂速度。

(2) 加速比與向上擴展比

圖6和圖7是DPBP與PBP在NYTIMES數(shù)據(jù)集以及ENRON數(shù)據(jù)集上加速比的比較。當我們使用12個線程的時候在NYTIMES數(shù)據(jù)集上，DPBP相對于PBP的加速比提高了25%，而在ENRON數(shù)據(jù)集上，我們的DPBP要比PBP的加速比提高了18%。這是由于我們的調(diào)度算法可以更加有效地調(diào)度線程，使線程的利用更加的高效。當線程數(shù)量增加得越多、分塊粒度越小，DPBP在加速比上的優(yōu)勢就更加明顯。

圖6　DPBP與PBP在NYTIMES數(shù)據(jù)集上的加速比

圖7　DPBP與PBP在ENRON數(shù)據(jù)集上的加速比

圖8　DPBP與PBP在NYTIMES數(shù)據(jù)集上的向上擴展比

圖9　DPBP與PBP在ENRON數(shù)據(jù)集上的向上擴展比

圖8和圖9是DPBP與PBP分別在NYTIMES以及ENRON上關(guān)于向上擴展比的比較。我們可以看到當使用12個線程的時候，在NYTIMES上，我們的DPBP在向上擴展度方面，要比PBP提高了57%。而在數(shù)據(jù)集相對較小的ENRON數(shù)據(jù)集上，使用相應(yīng)的線程數(shù)，我們的PDBP要比PBP提高51%。這是由于我們DPBP分割線程的粒度更小，使得數(shù)據(jù)量越是增加，線程之間負載越是均勻，DPBP的效率優(yōu)勢自然是越大。從而可以看出我們的DPBP在處理更大數(shù)據(jù)的時候有著更好的適應(yīng)能力。

6　結(jié)　語

本文介紹了基于共享內(nèi)存的并行LDA的一般構(gòu)架，提出了通過動態(tài)調(diào)度實現(xiàn)的并行LDA算法。通過改進線程的調(diào)度，提高了線程的利用率，使得算法的運行更有效率，從而改善了基于共享內(nèi)存的LDA算法。通過實驗的比較，動態(tài)的線程調(diào)度，不僅在保證精度沒有太大變化的同時，使得并行LDA的收斂速度以及加速比明顯的提高，而且也使得算法的向上擴展比也得到了顯著的提升。PDBP能夠使并行LDA算法更加適用于海量的數(shù)據(jù)，以及大規(guī)模分布式集群并行算法的單機擴展。

[1] Blei D M,Ng A Y,Jordan M I.Latent dirichlet allocation[J].Journal of machine Learning research,2003,3(1):993-1022.

[2] Heinrich G.Parameter estimation for text analysis[R].Fraunhofer IGD Darmstadt,2005.

[3] Teh Y W,Newman D,Welling M.A collapsed variational Bayesian inference algorithm for latent Dirichlet allocation[C]//Advances in neural information processing systems.2006:1353-1360.

[4] Zeng J,Cheung W K,Liu J.Learning topic models by belief propagation[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2013,35(5):1121-1134.

[5] Newman D,Smyth P,Welling M,et al.Distributed inference for latent dirichlet allocation[C]//Advances in neural information processing systems.2007:1081-1088.

[6] Smyth P,Welling M,Asuncion A U.Asynchronous distributed learning of topic models[C]//Advances in Neural Information Processing Systems.2009:81-88.

[7] Wang Y,Bai H,Stanton M,et al.Plda:Parallel latent dirichlet allocation for large-scale applications[M].AAIM,2009:301-314.

[8] Liu Z,Zhang Y,Chang E Y,et al.Plda+:Parallel latent dirichlet allocation with data placement and pipeline processing[J].ACM TIST,2011,2(3):26.

[9] Zhai K,Boyd Graber J,Asadi N,et al.Mr.LDA:A flexible large scale topic modeling package using variational inference in mapreduce[C]//Proceedings of the 21st international conference on World Wide Web.ACM,2012:879-888.

[10] Yan F,Xu N,Qi Y.Parallel inference for latent dirichlet allocation on graphics processing units[C]//NIPS,2009:2134-2142.

[11] Smola A,Narayanamurthy S.An architecture for parallel topic models[J].Proceedings of the VLDB Endowment,2010,3(1-2):703-710.MLA.

[12] Zeng J.A topic modeling toolbox using belief propagation[J].The Journal of Machine Learning Research,2012,13(1):2233-2236.MLA.

[13] Zhuang Y,Chin W S,Juan Y C,et al.A fast parallel SGD for matrix factorization in shared memory systems[C]//Proceedings of the 7th ACM Conference on Recommender Systems.ACM,2013:249-256.

PARALLELLDAALGORITHMBASEDONSHAREDMEMORY

YangXiLiuXiaoshengYangLuYanJianfeng*

(School of Computer Science and Technology,Soochow University,Suzhou 215006,Jiangsu,China)

ExistingtopicalmodelofparallellatentDirichletallocation(LDA)withsharedmemoryneedstowaitbetweenthreadsasaruleusuallyduetotheunbalancedistributionofdata,whichleadstolowefficiency.Inthispaperwestudytheproblemofthreadwaitingandproposeadynamic-basedthreadsschedulingscheme.Theschemecanpartitionthedatatoblocksaccordingtothenumberofthreadsanddynamicallyallocatestaskstoidlethreadstimelyonthisbasis,soastoreducethewaitingtimebetweenthreads.Experimentshowsthatsuchnewschedulingschemecaneffectivelysolvethreadswaitingproblem.Itcanachievea25%raiseinspeedupswhileensuringconvergenceaccuracy,besides,itcanalsoremarkablyimprovetheupwardexpansionratio.ForparallelLDAalgorithmofasinglenodeinlarge-scaledistributedcluster,theschedulingcanmoreeffectivelyutilisethecomputingresource.

LatentDirichletallocationSharedmemoryParallelDynamicscheduling

2014-10-29。國家自然科學基金項目(61373092,61033013,61272449,61202029);江蘇省教育廳重大項目(12KJA520004);江蘇省科技支撐計劃重點項目(BE2014005);廣東省重點實驗室開放課題(SZU-GDPHPCL-2012-09)。楊希，碩士生，主研領(lǐng)域：機器學習。劉曉升,博士生。楊璐，副教授。嚴建峰，副教授。

TP3

ADOI:10.3969/j.issn.1000-386x.2016.03.059