摘要：分层分布式狄利克雷分布（HDLDA）算法是一个对潜在狄利克雷分布（LDA）进行改进的基于概率增长模型的文本分类算法，与只能在单机上运行的LDA算法相比，可以运行在分布式框架下，进行分布式并行处理。Mahout在Hadoop框架下实现了HDLDA算法，但是因为单节点算法的计算量大，仍然存在对大数据分类运行时间太长的问题。而大规模文本集合分散到多个节点上迭代推导，单个节点上文档集合的推导仍是顺序进行的，所以处理大规模文本集合时仍然需要很长时间才能完成全部文本的分类。为此，提出将Hadoop与图形处理器（GPU）相结合，将单节点文本集合的推导过程转移到GPU上运行，实现单节点多个文档并行推导，利用多台并行的GPU对HDLDA算法进行加速。应用结果表明，使用该方法能使分布式框架下的HDLDA算法对大规模文本集合处理达到7倍的加速比。

　　关键词：分层分布式狄利克雷分布；潜在狄利克雷分布；文本分类；分布式框架；并行图形处理器

　　中图分类号： TP311 文献标志码：A

　　0引言

　　潜在狄利克雷分布（Latent Dirichlet Allocation，LDA）是Blei等[1]提出的对离散数据集（如文档集）分类的概率增长模型，是一个三层贝叶斯模型。LDA将文本表示为固定主题上的概率分布，可以利用Gibbs抽样算法与最大期望（ExpectationMaximization，EM）推理算法进行推导，间接计算模型参数，获取文本在主题集上的概率分布，从而确定文本属于哪个主题，达到分类效果。随着LDA算法的研究与应用，经过不断的改进，出现了各种不同硬件环境下运行的LDA算法。Newman等[2]提出了近似分布式狄利克雷分布（Approximate Distributed LDA，ADLDA）算法与分层分布式狄利克雷分布（Hierarchical Distributed LDA，HDLDA）算法，可以运行在分布式环境中；Chen等用Message Passing Interface（MPI）和MapReduce的方法实现ADLDA算法[3-4]；Mahout（Mahout作为Apache Software Foundation旗下的一个开源项目，提供一些可扩展的机器学习领域经典算法的实现）也已经用MapReduce的方法实现了HDLDA算法。除此之外，Masada等[5]实现了可以在单图形处理器（Graphic Processing Unit， GPU）上运行的LDA算法，Yan等[6]实现了可以在单GPU上运行的ADLDA算法，相对于单机CPU上运行的LDA，都达到了很高的加速比。可以看出，对于大数据以及大计算量的情况，出现了分布式计算与GPU计算两种不同趋势的研究。无论是在集群上对大数据进行分布式运算还是在单个GPU上对数据进行并行运算，都是为了提高LDA算法的并行化程度，从而减少算法的运行时间。但是，大数据情况下，对于HDLDA算法，分布式集群中单个节点上计算量很大。单GPU因为显存空间有限，需要将大数据分割成小数据，顺序地从CPU传递到GPU进行计算，并从GPU传递回CPU，传输数据的时间占了很大一部分比例。为了解决这些问题，提出将Hadoop与GPU结合的方法——HGPU，既保证大数据分布式计算的优势，又能利用GPU并行计算的优势。

　　Hadoop是一个能够对大规模数据进行分布式处理的软件框架，因其可靠、高效、可伸缩的特性在大数据处理方面得到广泛应用。GPU计算是最近出现的运用GPU搭配CPU来加速通用科学和工程应用程序的一种计算模式。一个GPU拥有大量并行线程处理器和高速访问内存，并使用Single Program Multiple Threads（SPMT）处理模式，在浮点运算、并行计算等计算方面，可以提供数十倍乃至上百倍于CPU的性能[7]。

　　Mahout已经在Hadoop框架下实现HDLDA算法，可以对大规模文本集合进行分类。但是处理大规模文本集合时，单个节点上的文本集合是顺序处理的，计算量很大，建立模型的时间很长，如果将单个节点上的文本集合推导过程转移到GPU运行，并行推导，则整个文本集合分类的处理速度将大大提升。

　　1.1LDA模型

　　LDA的推理算法主要有EM算法和Gibbs抽样算法。

　　EM算法是求参数极大似然估计的一种方法，主要有两种基本的计算步骤：

　　通过交替使用这两个步骤，EM算法逐渐改进模型的参数，使参数和训练样本的似然概率逐渐增大，最后终止于一个极大点。EM算法可以看作一个逐渐逼近的算法，事先不知道模型的参数，可以随机地选择一套参数或是粗略地给出某个初始参数值，确定出对应于这组参数的最可能的状态，计算每个训练样本的可能结果的概率，在当前状态下再由样本对参数修正，重新估计参数，并在新的参数下重新确定模型的状态[9-10]。这样，通过多次迭代循环直至某个收敛条件满足为止，这可以使得模型参数逐渐逼近真实参数。

　　Gibbs抽样算法是马尔可夫链蒙特卡洛（Markov Chain Monte Carlo，MCMC）方法的一种简单实现形式，其目的是构造收敛于某目标概率分布的Markov链[11]，并从链中抽取被认为接近该概率分布值的样本。Gibbs以其实现简单、通用性强得到了广泛地应用。

　　与Gibbs抽样算法相比，EM算法不仅简单、稳定，而且在LDA算法的应用上，能获得比Gibbs抽样并行程度更高的效果。

　　1.2HDLDA模型

　　HDLDA将大规模文本集合进行分布式并行计算，相对于单机LDA算法，缩短了整个数据集进行分类的时间。

　　1.3HDLDA执行过程

　　Mahout使用EM推理算法对HDLDA进行推导。HDLDA算法迭代执行EStep与MStep：EStep推导每个文档的主题单词概率分布以及每个文档的主题概率分布；MStep则更新全局的模型状态，即所有文档的主题单词概率分布。 　　HDLDA的EStep与MStep对应Hadoop中的Map任务和Reduce任务。通过Map任务计算每个文档的主题单词概率分布φd（w，k）以及文档的主题概率分布θ（d，k），Reduce任务则将所有文档的主题单词概率分布合并，更新全局主题单词概率分布φ（w，k）。每次迭代，各节点上Map任务使用相同的全局数据φ（w，k），即全局的主题单词概率分布。

　　HDLDA算法在Hadoop框架下的具体执行过程为：

　　1）将“对所有文档进行一次EM推导”作为一个Job提交给Hadoop，迭代多次执行Job任务，直到φ（w，k）与θ（d，k）收敛。Hadoop将Job的输入数据以块为单位存储到Hadoop分布式文件系统（Hadoop Distributed File System， HDFS）文件系统，分布到各个Slave节点。Job任务执行的具体过程如下：

　　a）Hadoop为单个节点上存储的本地数据分片，每一个分片启动一个Map任务。

　　b）假设某个节点i上分配到Di个文档，对某个文档d，在Map任务中循环多次计算该文档主题单词分布φd（w，k），直到φd（w，k）收敛。对Di集合中所有文档，顺序计算其主体单词概率分布，直到所有文档计算完毕。

　　c）所有Map任务完成后，启动Reduce任务，合并所有Slave节点上的文档的主题单词概率分布φd（w，k），更新全局数据φ（w，k）。

　　d）判断φ（w，k）是否收敛，如果收敛，EM迭代结束，执行步骤2）；否则，继续迭代，执行步骤a）。

　　2）利用收敛后的数据φ（w，k），计算文档的主题分布θ（d，k）。

　　迭代过程中，φd（w，k）与φ（w，k）相互作用，趋于收敛，步骤b）过程中，Di个文档顺序进行φd（w，k）推导，这是HDLDA算法在Hadoop环境下运行消耗时间最多的地方，将近占据全部运行时间的56%，所以提出HGPU方法，利用GPU的并行计算优势，对多个文档并行推导φd（w，k），以提高HDLDA算法的运行速度。

　　2HGPU框架下HDLDA的设计与实现

　　2.1HGPU框架

　　一般Hadoop框架主要是由CPU承担程序计算能力，而HGPU框架中则主要由GPU承担程序的计算能力。整个HGPU的框架如图1所示。

　　Hadoop将大规模文本集合分块存储在HDFS里，分散到各个Slave节点，然后为每个节点上的数据集分片启动一个Map任务，Map任务执行HDLDA的EStep推导过程。如果Slave节点安装有可以并行计算的GPU，Map任务就会通过JCuda的驱动函数启动统一计算架构（Compute Unified Device Architecture，CUDA）编写的Kernel函数，并将文档的单词频率信息以及全局状态矩阵等信息传递给GPU，于是Map任务的执行将从CPU转移到GPU。当GPU完成推导过程，便将计算结果即每个文档的主题单词概率分布传递回CPU，并通过排序存储在本地文件系统。当全部的Map任务执行结束，Reduce任务便将所有文档的主题单词概率分布合并，更新φ（w，k）作为下一次迭代Map任务的全局主题单词概率分布使用。

　　为了能将GPU和Hadoop框架相结合，Map任务中的计算密集型函数Inference将使用CUDA重写，作为Kernel函数运行在GPU上，Hadoop使用JCuda启动Kernel函数。JCuda是基于Java的Cuda开发包，JCuda库允许Java与CUDA程序运行时和驱动Application Programming Interface（API）交互。

　　2.2GPU数据结构设计

　　CUDA运行时启动核函数的多个并行副本，每一个并行副本就是一个线程块（Block），GPU硬件限制了线程块的启动数量最多不超过65535。每个线程块可以包含多个线程（Thread）同时执行命令，一个线程块内最多包含512个线程[12]。在每一次迭代过程中，GPU的一个Block负责一个文档的推导过程，多个文档同时进行。由于GPU显存有限，本实验环境中最大不超过1.5GB，根据文本集合中平均每篇文档的大小，可以调整M（每个GPU并行处理的文档数目）值，最大不超过500。

　　使用数组doc[M][N][2]存储文档中N个单词的ID以及频率，doc数据以一维数组的形式存储在GPU的global memory，每个文档对应一个Block，每个单词对应一个Thread，因为每个Block内最多为512个Thread，对于N>512的情况，需要循环多次进行Thread与单词的对应。文档、单词、Block以及Thread的对应关系如图2所示。

　　2.3HDLDA具体实现

　　HDLDA运行在HGPU环境中，主要修改Map函数，修改之后的Map任务执行过程为：

　　1）收集M个文档的信息，包括文档长度和单词在文档中出现的频率，存储到数组doc[M][N][2]，与全局状态数据φ（w，k）一起传递给GPU，因为GPU的显存容量有限，所以M值限制在500以内。如果文档数量超过M，则分成多次收集并传递给GPU计算。

　　2）GPU上运行的Kernel函数主要包含Inference_GPU，对应CPU上运行的函数Inference，每个Block推导一个文档，多个Block同时推导，则GPU可以对M个文档同时计算φd（w，k），并将结果传递回CPU。

　　3性能测试

　　实验在Mahout 0.5上进行修改测试，数据集合为Reuters21578，包含21578个文档[7]。为了测试大数据的情况，将Reuters21578数据集自拷贝100次，达到2.8GB，作为一个数据集交给Hadoop处理。 　　实验环境为：5台配置GPU的PC构成Hadoop集群的Slave节点，1台没有配置GPU的PC作为Hadoop集群的Master节点；JCuda版本0.4.1，CUDA版本4.0，集群配置信息如表1。

　　分别进行两次实验，对比修改前后Mahout的运行时间（单位：min）。Mahout修改之前，HDLDA运行在Hadoop的环境下；Mahout修改之后，HDLDA运行在HGPU的环境下。实验中M值表示每个GPU可以同时推导的文档数目，P表示集群里面Slave节点的数目。

　　实验1为P值固定，M不同情况下的实验对比，可以验证HDLDA算法在HGPU框架下，每台GPU的并行化程度M对算法运行速度的影响，实验结果如图3所示；实验2为M值固定，P不同情况下的实验对比，可以验证HDLDA算法在HGPU框架下，并行GPU的数目对算法运行速度的影响，实验结果如图4所示。

　　选定一台Slave1节点，GPU型号为Geforce GTX480，CPU型号为Intel Core i7950，根据GPU满载时功耗和CPU加压满载时的功率[13]计算Slave1节点运行未修改的Mahout以及修改之后M值分别设定为100、200、300、400、500的Mahout功耗，计算结果如表2所示。

　　3.1M值的对比实验

　　GPU数目P值固定，每个GPU处理的文档数目M分别设置成100、200、300、400、500，对比EM推导过程中平均迭代一次的时间，实验结果如图3所示。

　　通过图3发现，与一般Hadoop框架下的HDLDA算法相比，HGPU框架下的HDLDA在M=100时的加速比为3，随着M值的增大，HDLDA算法在HGPU框架上运行的时间逐渐缩短，并在M=500时的加速比达到7。M值越大，每台GPU可同时推导的文档数目越多，并行化程度越高，则每次迭代时间就会越短。

　　3.2P值的对比实验

　　设定M=500，设置Slave节点的数目P分别为2、3、4、5，由于实验条件有限，Hadoop框架下Slave节点的数目最大只能设置到5。对比EM推导过程中平均迭代一次的时间，实验结果如图4所示。

　　通过图4发现，随着Slave节点数目P的增加，HDLDA算法在Hadoop和HGPU框架下平均一次的迭代时间都逐渐减少，P越大，数据集分散程度越高，每个节点上处理的子数据集越小，相应每次的迭代时间越短。但HDLDA算法在HGPU框架下的运行时间始终比Hadoop框架下的运行时间少得多。在P=5时，HDLDA能在5台并行GPU的框架下运行，相比于只有2台并行GPU的情况，速度提高了1倍。

　　3.3单节点的功耗对比

　　X轴A表示修改之前Mahout迭代一次的功耗，其余B～F依次表示修改之后Mahout在M分别设定为100，200，300，400，500时迭代一次的功耗。

　　通过图5发现，随着M值的增大，因为HDLDA迭代一次的时间逐渐减少，相应GPU运行的时间占据整个程序运行时间的比例增大，所以Slave1迭代一次的功耗相比原程序不断减少。

　　表2表示在Slave 1节点上，修改之前Mahout迭代一次，以及修改之后Mahout在M分别设定为100、200、300、400、500时迭代一次，CPU与GPU共同消耗的电能量，单位为kJ。

　　通过表2可以看出，随着M值的增大，因为HDLDA迭代一次的时间逐渐减少，相应GPU运行的时间占据整个程序运行时间的比例增大，所以Slave1迭代一次的功耗相比原程序不断减少。

　　以上实验证明，在大计算量与大数据情况下，将GPU与Hadoop与结合，能充分利用并行计算与分布式的优势。HDLDA算法在HGPU环境下运行的速度比Hadoop环境下快的原因主要是：

　　1）从文档集合来说，单个节点上文档处理过程不再是顺序执行，而是并行执行；

　　2）对于单个文档的推导过程，GPU上运行的Inference_GPU函数比CPU上运行的Inference函数的并行化程度更高。

　　4结语

　　本文描述了如何通过Hadoop与GPU结合对HDLDA算法进行加速，利用Hadoop的分布式计算优势以及GPU的并行计算优势，可以快速、高效地处理大数据，同时解决单节点顺序处理文档的问题。但是将Hadoop与GPU结合使用，也存在一定的弊端。因为GPU的显存空间有限，GPU可以同时处理的文档数目受到限制。JCuda启动GPU的Kernel函数，从CPU到GPU以及GPU到CPU之间的数据传递都会有额外的时间耗损，所以对于不同算法，需要根据其计算量以及并行程度来决定是否采用Hadoop与GPU相结合的方式。

　　关于单节点上CPU与GPU之间的数据传递所带来的时间耗损，可以采用CUDA Stream的处理方式。利用不同流的异步操作，当GPU对一部分数据进行并行计算时，CPU可以将另外一部分数据传递到GPU上，或是进行反向传递。这将作为下一阶段的研究重点进行实验。

　　将GPU应用在Hadoop框架中不仅仅适用于LDA算法，还适用于其他多种机器学习算法；不仅可以应用在文本分类、图片分类，还可以应用在图像检索等系统中。

　　参考文献：

　　[1]BLEI D M， NG A Y， JORDAN M I. Latent Dirichlet allocation [J]. Journal of Machine Learning Research， 2003， 3（4/5）： 993-1022.

　　[2]NEWMAN D， ASUNCION A， SMYTH P， et al. Distributed inference for latent Dirichlet allocation [C]// NIPS 2007： Proceedings of the 2007 TwentyFirst Annual Conference on Neural Information Processing System. [S.l.]： NIPS， 2007： 1081-1088. 　　[3]CHEN WY， CHU JC， LUAN J， et al. Collaborative filtering for orkut communities： discovery of user latent behavior [C]// WWW 09： Proceedings of the 18th International Conference on World Wide Web. New York： ACM， 2009：681-690.

　　[4]WANG Y， BAI H J， STANTON M， et al. PLDA： Parallel Latent Dirichlet Allocation for largescale applications [C]// AAIM 09： Proceedings of the 5th International Conference on Algorithmic Aspects in Information and Management. Berlin： SpringerVerlag， 2009： 301-314.

　　[5]MASADA T， HAMADA T， SHIBATA Y， et al. Accelerating collapsed variational Bayesian inference for latent Dirichlet allocation with Nvidia CUDA compatible devices [C]// IEA/AIE 09： Proceedings of the 22nd International Conference on Industrial， Engineering and Other Applications of Applied Intelligent Systems： NextGeneration Applied Intelligence， LNCS 5579. Berlin： SpringerVerlag， 2009： 491-500.

　　[6]YAN F， XU N， QI Y. Parallel inference for latent Dirichlet allocation on graphics processing units [C]// NIPS 2009： Proceedings of the 2009 22nd Annual Conference on Neural Information Processing System. [S.l.]： NIPS， 2009： 2134-2142

　　[7]LU M， BAI G， LUO Q， et al. Accelerating topic model training on a single machine [C]// APWeb13： Proceedings of the 2013 Fifteenth International AsiaPacific Web Conference， LNCS 7808. Berlin： SpringerVerlag， 2013： 184-195.

　　[8]JIANG Y J， WEN H L， GAO Z C. A method of accelerating LDA program with GPU [C] // ICNDC 2012： Proceedings of the 2012 Third International Conference on Networking and Distributed Computing. Washington， DC： IEEE Computer Society， 2012：26-29.

　　[9]崔凯。基于LDA的主题演化研究与实现[D].长沙：国防科技大学，2010.

　　[10]姚全珠，宋志理，彭程。基于LDA模型的文本分类研究[J].计算机工程与应用，2011，47（13）：150-152.

　　[11]董元元，陈基漓，唐小侠。基于潜在狄里克雷模型和互信息的无监督特征选取法[J].计算机应用，2012，32（8）：2250-2252.

　　[12]SANDERS J， KANDROT E.GPU高性能编程CUDA实战[M].聂雪军，译。1版。北京：机械工业出版社，2011：33-45.

　　[13]功耗测试[EB/OL]. [2013-07-30]. http：//www.pcpop.com/doc/0/649/649665_all.shtml#p4.