基于共享內存的并行LDA算法

楊　希　劉曉升　楊　璐　嚴建峰

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

?

基于共享內存的并行LDA算法

楊希劉曉升楊璐嚴建峰*

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

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

潛在狄利克雷分配共享內存并行動態調度

0　引　言

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

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

1　相關工作

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

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

2　LDA模型

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

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

(1)

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

圖1　LDA圖模型

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

3　基于共享內存的并行LDA

圖2　互不沖突的塊

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

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

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

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

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

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

4　并行算法的調度優化

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

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

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

圖3　動態調度的線程

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

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

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

5　實驗分析

5.1實驗環境與數據集

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

表1　數據集

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

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

本文對基于共享內存的并行LDA即PBP進行線程調度上的優化，新的算法記為DPBP。

5.2評價標準

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

(2)

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

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

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

5.3實驗結果分析

(1) 收斂效果比較

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

圖4　DPBP與PBP在NYTIMES　　數據集上的收斂比較

圖5　DPBP與PBP在ENRON　　數據集上的收斂比較

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

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

可以較明顯的看出，DPBP算法不僅具有更快的收斂速度，同時其收斂精度與原算法并沒有太大的差別。相對于PBP，DPBP并不會在本質上改變算法，只是通過調度改變了數據的計算順序，通過減少調度時間，DPBP不僅能夠對精度不產生影響并且能夠顯著地提升收斂速度。

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

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

圖6　DPBP與PBP在NYTIMES數據集上的加速比

圖7　DPBP與PBP在ENRON數據集上的加速比

圖8　DPBP與PBP在NYTIMES數據集上的向上擴展比

圖9　DPBP與PBP在ENRON數據集上的向上擴展比

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

6　結　語

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

[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)。楊希，碩士生，主研領域：機器學習。劉曉升,博士生。楊璐，副教授。嚴建峰，副教授。

TP3

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