Computer Science ›› 2013, Vol. 40 ›› Issue (4): 69-72.
Previous Articles Next Articles
ZHANG Wei,ZHANG Gong-xuan,WANG Yong-li,ZHANG Yong-ping and ZHU Zhao-meng
| [1] Atzori L,Iera A,Morabito G．The Internet of Things:A survey[J]．Computer Networks,2010,54:2787-2805 [2] 将解决如下优化问题。 minθ,b,ζ12θTθ＋C∑li=1ζi s.t.12θyi(θT(xi)＋b)≥1－ζi (1) ζi≥0 此处,(xi)将向量xi映射到高维空间,C是正规化参数,C>0。向量变量θ是高维的向量,需要解决下面的问题。 minα12αTQα －eTα s.t.yTα＝0 0≤αi≤C i=1,…,l (2) e＝[1,…,1]T是值全为1的向量,l×l半正定矩阵Q,Qij≡yiyjK( xi,xj),并且K(xi,xj)≡(xi)T(xj)是核函数。 当问题(2)解决时,θ将满足 θ＝∑li=1yiαi(xi)(3) 这样决策函数可以表示为 sgn(θT(x)+b)=sgn(∑li=1yiαiK(xi,x)＋b)(4) 此处参与预测分类的数据有 yiαi i,b。其他的数据还有支持向量 xi、核心函数的参数等。 2.3分类准确度 在Banko的研究中[8],分类的准确度和训练的样本数有很大的相关性。在图5中显示了不同学习算法的学习曲线:memory-based,winnow,nave Bayes, perceptron learner of machine learning algorithms。每一个算法都使用上亿的单词量进行训练。从图5可以看出,算法的准确度随着训练样本数的上升呈现对数上升。 图5学习曲线和训练样本 从图5可以看出,只有对足够多的训练样本进行学习训练后,分类算法才可以达到一个比较理想的分类准确度。所以通过并行算法,提高SVM算法的执行效率,对数据量巨大的物联网应用具有重要的意义。 3SVM算法并行化 LibSVM[2]是一个得到广泛使用的SVM计算工具,具有程序执行速度快、分类效果好的特点。在SVM算法中,主要经过3个阶段:学习阶段、交叉验证阶段和分类预测。而SVM算法在学习阶段是最消耗计算资源的,随着数据量的增加,如何提高数据处理效率是本文主要研究的内容。 CUDA(Compute Unified Device Architecture)[6]是Nvidia公司开发的并行计算框架。开发者通过CUDA提供的虚拟指令可以使用并行计算元素和GPU内存并使用。有了CUDA的支持,开发者可以像使用CPU一样方便地使用Nvidia公司最新版本的GPU[12]。编程人员通过写简单的GPU内核程序,实现并行计算的功能。一个内核程序可以被多个线程并行执行。 多个线程可以组织成一个线程块,线程块内的线程共享内存和寄存器等资源。多个线程块组成一个内核网格,内核网格内的线程块间相互独立地并行执行。我们的SVM算法并行化工作基于LibSVM和CUDA。 在对SVM算法的分析中,根据矩阵x和向量y来计算矩阵Q,Qij ≡ yiyjK(xi,xj)。 Q＝∑li=1lj=1yiyjK(xi,xj)(5) 式中,K为核函数,矩阵Q的计算在CPU中占用大量的计算时间。将算法并行化,在GPU中每一个线程只对矩阵Q的行向量Qi进行计算: Qi＝∑li=1yiyjK(xi,xj)(6) 通过编写GPU内核程序获得较高的并行计算能力。CUDA采用SIMT架构,此架构中指令顺序执行,而且没有分支预测,如果有大量的逻辑判断,则会导致并行性能下降。因此在进行内核程序设计时,每个内核程序只做简单的循环,以提高程序的并行执行能力。 算法1SVM的并行算法P-SVM(Parallel Support Vector Machine) 1．在主存中初始化训练数据集xi∈Rn(i＝1,…,l)和分类指示向量y∈Rl,yi∈{1,－1}； 2．初始化Q,xi,y在GPU中的内存空间； 3．将主存中xi,y复制到GPU内存； 4．在GPU调用内核程序并行计算矩阵Q,实现式(6)的功能； 5．将计算结果从GPU内存复制到主存中； 6．CPU计算αi 和 b等参数； 7．根据参数对测试集进行分类。 为了提高内核程序的运行效率,在数据前期处理时,对训练数据集的样本属性值进行了两种不同的处理:在P-SVM中是普通表示方式,对每个样本向xi进行所有属性值的填充处理,使X为l×m的方阵,l为测试样本数,m为样本的属性数；另一种为数据稀疏表示,只填入样本中不为0的属性值,样本训练集不再是一方阵。 算法2SVM的稀疏并行算法SP-SVM(Sparse Parallel Support Vector Machine) 1．在主存中初始化训练数据集xi ∈ Rn(i＝1,…,l),和分类指示向量y∈Rl,yi ∈ {1,－1},xi为稀疏表示； 2．初始化Q,xi,y在GPU中的内存空间； 3．将主存中xi,y复制到GPU内存； 4．在GPU调用内核程序并行计算矩阵Q,实现式(6)的功能； 5．将计算结果从GPU内存复制到主存中； 6．CPU计算αi 和 b等参数； 7．根据参数对测试集进行分类。 显然,P-SVM适合样本属性值密集的情况,但在样本数据属性值稀疏情况下会导致空间浪费。而SP-SVM适合样本属性值比较稀疏的情况,但在样本数据属性值密集的情况下,由于要增加属性的标识,会导致内存空间的浪费。 对于P-SVM和SP-SVM这两种算法,在实验中采用稀疏数据,对性能进行了分析与比较。 4实验与分析 4.1实验环境 在实验中分别对训练样本数据量对于分类的准确度、并行算法对小数据量的运行效能和并行算法对大数据量的运行效能进行了对比与分析。实验数据采用文献[13]提供的数据。 我们实验的硬件平台是PC机,2.3GHz Intel i5CPU,16GB内存和NVIDIA Tesla C2050GPU。软件环境是Windows 7,Visual studio 2010,CUDA4.0。 4.2训练样本数对准确度的影响 为了分析训练集大小对分类准确度的影响,在实验中,采用不同数据量的训练样本进行测试。可以看出,随着训练样本数据量的增加,对测试样本分类的准确定度也所有提高,如图6所示。 图6训练样本数和准确度 实验采用在数据集上进行分片,模拟不同数据集大小的方式,准确度值的绝对变化范围并不明显。但根据文献[8],随着训练样本数据量增大,对准确定度会有较强的相关性。 由于是在Lib-SVM基础上进行的并行化,因此P-SVM和SP-SVM的分类准确度与Lib-SVM没有本质区别,故实验主要针对训练样本数据和分类准确度之间的关联性进行分析比较。 4.3并行算法性能分析 在CUDA中,计算机主存和GPU内存间的数据传输带宽为4GB/s,其远小于GPU内存144GB/s的带宽。当处理数据量比较小时,由于内核程序运行时间较短,而内存间数据传递占用了大量时间,因此显得并行算法的执行速度明显低于普通的串形算法。 图7小数据量算法性能比较 在图7中,当训练集小于38.5k时,SP-SVM算法执行时间长于Lib-SVM；当训练集小于60.5k时,P-SVM算法执行时间长于Lib-SVM。但当训练集增大时,并行算法的运行效率明显提高。 由于在实验所采用的是稀疏的数据,因此SP-SVM在小数据量时,也明显比P-SVM有更高的执行效率。 从图8可以看出,当训练样本数据集大于110k时,计算机主存和GPU内存间数据传输的时间在计算中所占比例下降,并行算法总的计算时间明显优于串行算法,并且随着数据量的增加,并行算法执行时间保持较小增加。 图8大数据量算法性能比较 结束语随着信息技术的爆炸式发展,大量数据的处理对实时性的要求越来越高。基于GPU的数据并行处理作为一种有效提高数据处理速度、提高应用系统响应实时性的重要技术手段得到了广泛应用。 SVM是物联网、数据挖掘、机器学习等领域非常重要的数据分类技术。本文基于CUDA对SVM算法进行并行化,取得了较高的运行效率,为SVM算法在大规模数据处理中的应用做出了基础性的研究工作。 通过实验,我们对比了Lib-SVM、P-SVM和SP-SVM的运行效率,并对实验数据进行了实验对比与分析,其表明了SVM并行化算法的有效性。 当前关于SVM算法的并行化研究文献[10,11]也做了相关工作。 Thanh的研究[10]对于SVM的样本训练过程也进行了并行化,取得了较高的运行效率。但在文献[10]中直接使用了CUDA1.1提供的CUBLAS函数进行矩阵运算,而在本文的SVM并行化中直接使用CUDA4.0内核函数编程,可更好地对GPU中的线程进行调度与控制。 Qi Li的研究[11]对SVM算法的交叉验证选择参数的算法进行了并行化处理。交叉验证的可并行化程度比较高,取得了很高的执行速度。而样本训练效率较低是SVM占用计算资源最大的一个问题,本文所做研究解决了样本训练并行计算的问题,可以结合文献[11]中的研究成果,进一步提高SVM算法的并行化效果。 (下转第106页) [1]Atzori L,Iera A,Morabito G．The Internet of Things:A survey[J]．Computer Networks,2010,54:2787-2805 [2] Chang C-C,Lin C-J．LIBSVM:a library for support vector machines[J]．ACM Transactions on Intelligent Systems and Technology (TIST) archive, 2011,2(3) [3] Redman T．The impact of poor data quality on the typical enterprise[J]．Commun．ACM,1998,2:79-82 [4] Chandola V,Banerjee A,Kumar V．Anomaly Detection:A Survey[J]．ACM Computing Surveys,2009,41(3):15 [5] Xiao H．Towards parallel and distributed computing in large-scale data mining:A survey[R]．Technical University of Munich,2010:1-30 [6] 是Nvidia公司开发的并行计算框架。开发者通过CUDA提供的虚拟指令可以使用并行计算元素和GPU内存并使用。有了CUDA的支持,开发者可以像使用CPU一样方便地使用Nvidia公司最新版本的GPU[12]。编程人员通过写简单的GPU内核程序,实现并行计算的功能。一个内核程序可以被多个线程并行执行。 多个线程可以组织成一个线程块,线程块内的线程共享内存和寄存器等资源。多个线程块组成一个内核网格,内核网格内的线程块间相互独立地并行执行。我们的SVM算法并行化工作基于LibSVM和CUDA。 在对SVM算法的分析中,根据矩阵x和向量y来计算矩阵Q,Qij ≡ yiyjK(xi,xj)。 Q＝∑li=1lj=1yiyjK(xi,xj)(5) 式中,K为核函数,矩阵Q的计算在CPU中占用大量的计算时间。将算法并行化,在GPU中每一个线程只对矩阵Q的行向量Qi进行计算: Qi＝∑li=1yiyjK(xi,xj)(6) 通过编写GPU内核程序获得较高的并行计算能力。CUDA采用SIMT架构,此架构中指令顺序执行,而且没有分支预测,如果有大量的逻辑判断,则会导致并行性能下降。因此在进行内核程序设计时,每个内核程序只做简单的循环,以提高程序的并行执行能力。 算法1SVM的并行算法P-SVM(Parallel Support Vector Machine) 1．在主存中初始化训练数据集xi∈Rn(i＝1,…,l)和分类指示向量y∈Rl,yi∈{1,－1}； 2．初始化Q,xi,y在GPU中的内存空间； 3．将主存中xi,y复制到GPU内存； 4．在GPU调用内核程序并行计算矩阵Q,实现式(6)的功能； 5．将计算结果从GPU内存复制到主存中； 6．CPU计算αi 和 b等参数； 7．根据参数对测试集进行分类。 为了提高内核程序的运行效率,在数据前期处理时,对训练数据集的样本属性值进行了两种不同的处理:在P-SVM中是普通表示方式,对每个样本向xi进行所有属性值的填充处理,使X为l×m的方阵,l为测试样本数,m为样本的属性数；另一种为数据稀疏表示,只填入样本中不为0的属性值,样本训练集不再是一方阵。 算法2SVM的稀疏并行算法SP-SVM(Sparse Parallel Support Vector Machine) 1．在主存中初始化训练数据集xi ∈ Rn(i＝1,…,l),和分类指示向量y∈Rl,yi ∈ {1,－1},xi为稀疏表示； 2．初始化Q,xi,y在GPU中的内存空间； 3．将主存中xi,y复制到GPU内存； 4．在GPU调用内核程序并行计算矩阵Q,实现式(6)的功能； 5．将计算结果从GPU内存复制到主存中； 6．CPU计算αi 和 b等参数； 7．根据参数对测试集进行分类。 显然,P-SVM适合样本属性值密集的情况,但在样本数据属性值稀疏情况下会导致空间浪费。而SP-SVM适合样本属性值比较稀疏的情况,但在样本数据属性值密集的情况下,由于要增加属性的标识,会导致内存空间的浪费。 对于P-SVM和SP-SVM这两种算法,在实验中采用稀疏数据,对性能进行了分析与比较。 4实验与分析 4.1实验环境 在实验中分别对训练样本数据量对于分类的准确度、并行算法对小数据量的运行效能和并行算法对大数据量的运行效能进行了对比与分析。实验数据采用文献[13]提供的数据。 我们实验的硬件平台是PC机,2.3GHz Intel i5CPU,16GB内存和NVIDIA Tesla C2050GPU。软件环境是Windows 7,Visual studio 2010,CUDA4.0。 4.2训练样本数对准确度的影响 为了分析训练集大小对分类准确度的影响,在实验中,采用不同数据量的训练样本进行测试。可以看出,随着训练样本数据量的增加,对测试样本分类的准确定度也所有提高,如图6所示。 图6训练样本数和准确度 实验采用在数据集上进行分片,模拟不同数据集大小的方式,准确度值的绝对变化范围并不明显。但根据文献[8],随着训练样本数据量增大,对准确定度会有较强的相关性。 由于是在Lib-SVM基础上进行的并行化,因此P-SVM和SP-SVM的分类准确度与Lib-SVM没有本质区别,故实验主要针对训练样本数据和分类准确度之间的关联性进行分析比较。 4.3并行算法性能分析 在CUDA中,计算机主存和GPU内存间的数据传输带宽为4GB/s,其远小于GPU内存144GB/s的带宽。当处理数据量比较小时,由于内核程序运行时间较短,而内存间数据传递占用了大量时间,因此显得并行算法的执行速度明显低于普通的串形算法。 图7小数据量算法性能比较 在图7中,当训练集小于38.5k时,SP-SVM算法执行时间长于Lib-SVM；当训练集小于60.5k时,P-SVM算法执行时间长于Lib-SVM。但当训练集增大时,并行算法的运行效率明显提高。 由于在实验所采用的是稀疏的数据,因此SP-SVM在小数据量时,也明显比P-SVM有更高的执行效率。 从图8可以看出,当训练样本数据集大于110k时,计算机主存和GPU内存间数据传输的时间在计算中所占比例下降,并行算法总的计算时间明显优于串行算法,并且随着数据量的增加,并行算法执行时间保持较小增加。 图8大数据量算法性能比较 结束语随着信息技术的爆炸式发展,大量数据的处理对实时性的要求越来越高。基于GPU的数据并行处理作为一种有效提高数据处理速度、提高应用系统响应实时性的重要技术手段得到了广泛应用。 SVM是物联网、数据挖掘、机器学习等领域非常重要的数据分类技术。本文基于CUDA对SVM算法进行并行化,取得了较高的运行效率,为SVM算法在大规模数据处理中的应用做出了基础性的研究工作。 通过实验,我们对比了Lib-SVM、P-SVM和SP-SVM的运行效率,并对实验数据进行了实验对比与分析,其表明了SVM并行化算法的有效性。 当前关于SVM算法的并行化研究文献[10,11]也做了相关工作。 Thanh的研究[10]对于SVM的样本训练过程也进行了并行化,取得了较高的运行效率。但在文献[10]中直接使用了CUDA1.1提供的CUBLAS函数进行矩阵运算,而在本文的SVM并行化中直接使用CUDA4.0内核函数编程,可更好地对GPU中的线程进行调度与控制。 Qi Li的研究[11]对SVM算法的交叉验证选择参数的算法进行了并行化处理。交叉验证的可并行化程度比较高,取得了很高的执行速度。而样本训练效率较低是SVM占用计算资源最大的一个问题,本文所做研究解决了样本训练并行计算的问题,可以结合文献[11]中的研究成果,进一步提高SVM算法的并行化效果。 (下转第106页) [1]Atzori L,Iera A,Morabito G．The Internet of Things:A survey[J]．Computer Networks,2010,54:2787-2805 [2] Chang C-C,Lin C-J．LIBSVM:a library for support vector machines[J]．ACM Transactions on Intelligent Systems and Technology (TIST) archive, 2011,2(3) [3] Redman T．The impact of poor data quality on the typical enterprise[J]．Commun．ACM,1998,2:79-82 [4]Chandola V,Banerjee A,Kumar V．Anomaly Detection:A Survey[J]．ACM Computing Surveys,2009,41(3):15 [5]Xiao H．Towards parallel and distributed computing in large-scale data mining:A survey[R]．Technical University of Munich,2010:1-30 [6]http://developer.download.nvidia.com/compute/cuda/1_0/NV-IDIA_CUDA_Programming_Guide_1.0.pdf [7] Almasi G S,Gottlieb A．Highly Parallel Computing[M]．Benjamin-Cummings publishers Co.,Inc．Redwood City,CA,USA,1989 [8] ,分类的准确度和训练的样本数有很大的相关性。在图5中显示了不同学习算法的学习曲线:memory-based,winnow,nave Bayes, perceptron learner of machine learning algorithms。每一个算法都使用上亿的单词量进行训练。从图5可以看出,算法的准确度随着训练样本数的上升呈现对数上升。 图5学习曲线和训练样本 从图5可以看出,只有对足够多的训练样本进行学习训练后,分类算法才可以达到一个比较理想的分类准确度。所以通过并行算法,提高SVM算法的执行效率,对数据量巨大的物联网应用具有重要的意义。 3SVM算法并行化 LibSVM[2]是一个得到广泛使用的SVM计算工具,具有程序执行速度快、分类效果好的特点。在SVM算法中,主要经过3个阶段:学习阶段、交叉验证阶段和分类预测。而SVM算法在学习阶段是最消耗计算资源的,随着数据量的增加,如何提高数据处理效率是本文主要研究的内容。 CUDA(Compute Unified Device Architecture)[6]是Nvidia公司开发的并行计算框架。开发者通过CUDA提供的虚拟指令可以使用并行计算元素和GPU内存并使用。有了CUDA的支持,开发者可以像使用CPU一样方便地使用Nvidia公司最新版本的GPU[12]。编程人员通过写简单的GPU内核程序,实现并行计算的功能。一个内核程序可以被多个线程并行执行。 多个线程可以组织成一个线程块,线程块内的线程共享内存和寄存器等资源。多个线程块组成一个内核网格,内核网格内的线程块间相互独立地并行执行。我们的SVM算法并行化工作基于LibSVM和CUDA。 在对SVM算法的分析中,根据矩阵x和向量y来计算矩阵Q,Qij ≡ yiyjK(xi,xj)。 Q＝∑li=1lj=1yiyjK(xi,xj)(5) 式中,K为核函数,矩阵Q的计算在CPU中占用大量的计算时间。将算法并行化,在GPU中每一个线程只对矩阵Q的行向量Qi进行计算: Qi＝∑li=1yiyjK(xi,xj)(6) 通过编写GPU内核程序获得较高的并行计算能力。CUDA采用SIMT架构,此架构中指令顺序执行,而且没有分支预测,如果有大量的逻辑判断,则会导致并行性能下降。因此在进行内核程序设计时,每个内核程序只做简单的循环,以提高程序的并行执行能力。 算法1SVM的并行算法P-SVM(Parallel Support Vector Machine) 1．在主存中初始化训练数据集xi∈Rn(i＝1,…,l)和分类指示向量y∈Rl,yi∈{1,－1}； 2．初始化Q,xi,y在GPU中的内存空间； 3．将主存中xi,y复制到GPU内存； 4．在GPU调用内核程序并行计算矩阵Q,实现式(6)的功能； 5．将计算结果从GPU内存复制到主存中； 6．CPU计算αi 和 b等参数； 7．根据参数对测试集进行分类。 为了提高内核程序的运行效率,在数据前期处理时,对训练数据集的样本属性值进行了两种不同的处理:在P-SVM中是普通表示方式,对每个样本向xi进行所有属性值的填充处理,使X为l×m的方阵,l为测试样本数,m为样本的属性数；另一种为数据稀疏表示,只填入样本中不为0的属性值,样本训练集不再是一方阵。 算法2SVM的稀疏并行算法SP-SVM(Sparse Parallel Support Vector Machine) 1．在主存中初始化训练数据集xi ∈ Rn(i＝1,…,l),和分类指示向量y∈Rl,yi ∈ {1,－1},xi为稀疏表示； 2．初始化Q,xi,y在GPU中的内存空间； 3．将主存中xi,y复制到GPU内存； 4．在GPU调用内核程序并行计算矩阵Q,实现式(6)的功能； 5．将计算结果从GPU内存复制到主存中； 6．CPU计算αi 和 b等参数； 7．根据参数对测试集进行分类。 显然,P-SVM适合样本属性值密集的情况,但在样本数据属性值稀疏情况下会导致空间浪费。而SP-SVM适合样本属性值比较稀疏的情况,但在样本数据属性值密集的情况下,由于要增加属性的标识,会导致内存空间的浪费。 对于P-SVM和SP-SVM这两种算法,在实验中采用稀疏数据,对性能进行了分析与比较。 4实验与分析 4.1实验环境 在实验中分别对训练样本数据量对于分类的准确度、并行算法对小数据量的运行效能和并行算法对大数据量的运行效能进行了对比与分析。实验数据采用文献[13]提供的数据。 我们实验的硬件平台是PC机,2.3GHz Intel i5CPU,16GB内存和NVIDIA Tesla C2050GPU。软件环境是Windows 7,Visual studio 2010,CUDA4.0。 4.2训练样本数对准确度的影响 为了分析训练集大小对分类准确度的影响,在实验中,采用不同数据量的训练样本进行测试。可以看出,随着训练样本数据量的增加,对测试样本分类的准确定度也所有提高,如图6所示。 图6训练样本数和准确度 实验采用在数据集上进行分片,模拟不同数据集大小的方式,准确度值的绝对变化范围并不明显。但根据文献[8],随着训练样本数据量增大,对准确定度会有较强的相关性。 由于是在Lib-SVM基础上进行的并行化,因此P-SVM和SP-SVM的分类准确度与Lib-SVM没有本质区别,故实验主要针对训练样本数据和分类准确度之间的关联性进行分析比较。 4.3并行算法性能分析 在CUDA中,计算机主存和GPU内存间的数据传输带宽为4GB/s,其远小于GPU内存144GB/s的带宽。当处理数据量比较小时,由于内核程序运行时间较短,而内存间数据传递占用了大量时间,因此显得并行算法的执行速度明显低于普通的串形算法。 图7小数据量算法性能比较 在图7中,当训练集小于38.5k时,SP-SVM算法执行时间长于Lib-SVM；当训练集小于60.5k时,P-SVM算法执行时间长于Lib-SVM。但当训练集增大时,并行算法的运行效率明显提高。 由于在实验所采用的是稀疏的数据,因此SP-SVM在小数据量时,也明显比P-SVM有更高的执行效率。 从图8可以看出,当训练样本数据集大于110k时,计算机主存和GPU内存间数据传输的时间在计算中所占比例下降,并行算法总的计算时间明显优于串行算法,并且随着数据量的增加,并行算法执行时间保持较小增加。 图8大数据量算法性能比较 结束语随着信息技术的爆炸式发展,大量数据的处理对实时性的要求越来越高。基于GPU的数据并行处理作为一种有效提高数据处理速度、提高应用系统响应实时性的重要技术手段得到了广泛应用。 SVM是物联网、数据挖掘、机器学习等领域非常重要的数据分类技术。本文基于CUDA对SVM算法进行并行化,取得了较高的运行效率,为SVM算法在大规模数据处理中的应用做出了基础性的研究工作。 通过实验,我们对比了Lib-SVM、P-SVM和SP-SVM的运行效率,并对实验数据进行了实验对比与分析,其表明了SVM并行化算法的有效性。 当前关于SVM算法的并行化研究文献[10,11]也做了相关工作。 Thanh的研究[10]对于SVM的样本训练过程也进行了并行化,取得了较高的运行效率。但在文献[10]中直接使用了CUDA1.1提供的CUBLAS函数进行矩阵运算,而在本文的SVM并行化中直接使用CUDA4.0内核函数编程,可更好地对GPU中的线程进行调度与控制。 Qi Li的研究[11]对SVM算法的交叉验证选择参数的算法进行了并行化处理。交叉验证的可并行化程度比较高,取得了很高的执行速度。而样本训练效率较低是SVM占用计算资源最大的一个问题,本文所做研究解决了样本训练并行计算的问题,可以结合文献[11]中的研究成果,进一步提高SVM算法的并行化效果。 (下转第106页) [1]Atzori L,Iera A,Morabito G．The Internet of Things:A survey[J]．Computer Networks,2010,54:2787-2805 [2] Chang C-C,Lin C-J．LIBSVM:a library for support vector machines[J]．ACM Transactions on Intelligent Systems and Technology (TIST) archive, 2011,2(3) [3] Redman T．The impact of poor data quality on the typical enterprise[J]．Commun．ACM,1998,2:79-82 [4]Chandola V,Banerjee A,Kumar V．Anomaly Detection:A Survey[J]．ACM Computing Surveys,2009,41(3):15 [5]Xiao H．Towards parallel and distributed computing in large-scale data mining:A survey[R]．Technical University of Munich,2010:1-30 [6]http://developer.download.nvidia.com/compute/cuda/1_0/NV-IDIA_CUDA_Programming_Guide_1.0.pdf [7]Almasi G S,Gottlieb A．Highly Parallel Computing[M]．Benjamin-Cummings publishers Co.,Inc．Redwood City,CA,USA,1989 [8]Banko M,Brill E．Scaling to very very large corpora for natural language disambiguation[C]∥ACL ’01Proceedings of the 39th Annual Meeting on Association for Computational Linguistics．Stroudsburg,PA,USA,2001:26-33 [9] Hu W J,Song Q．An accelerated decomposition algorithm for ro-bust support vector Machines[J]．IEEE Transactions on Circuits and Systems II:Express Briefs,2004,51(5):234-240 [10] 对于SVM的样本训练过程也进行了并行化,取得了较高的运行效率。但在文献[10]中直接使用了CUDA1.1提供的CUBLAS函数进行矩阵运算,而在本文的SVM并行化中直接使用CUDA4.0内核函数编程,可更好地对GPU中的线程进行调度与控制。 Qi Li的研究 [11] 对SVM算法的交叉验证选择参数的算法进行了并行化处理。交叉验证的可并行化程度比较高,取得了很高的执行速度。而样本训练效率较低是SVM占用计算资源最大的一个问题,本文所做研究解决了样本训练并行计算的问题,可以结合文献[11]中的研究成果,进一步提高SVM算法的并行化效果。 (下转第106页) [1]Atzori L,Iera A,Morabito G．The Internet of Things:A survey[J]．Computer Networks,2010,54:2787-2805 [2] Chang C-C,Lin C-J．LIBSVM:a library for support vector machines[J]．ACM Transactions on Intelligent Systems and Technology (TIST) archive, 2011,2(3) [3] Redman T．The impact of poor data quality on the typical enterprise[J]．Commun．ACM,1998,2:79-82 [4]Chandola V,Banerjee A,Kumar V．Anomaly Detection:A Survey[J]．ACM Computing Surveys,2009,41(3):15 [5]Xiao H．Towards parallel and distributed computing in large-scale data mining:A survey[R]．Technical University of Munich,2010:1-30 [6]http://developer.download.nvidia.com/compute/cuda/1_0/NV-IDIA_CUDA_Programming_Guide_1.0.pdf [7]Almasi G S,Gottlieb A．Highly Parallel Computing[M]．Benjamin-Cummings publishers Co.,Inc．Redwood City,CA,USA,1989 [8]Banko M,Brill E．Scaling to very very large corpora for natural language disambiguation[C]∥ACL ’01Proceedings of the 39th Annual Meeting on Association for Computational Linguistics．Stroudsburg,PA,USA,2001:26-33 [9]Hu W J,Song Q．An accelerated decomposition algorithm for ro-bust support vector Machines[J]．IEEE Transactions on Circuits and Systems II:Express Briefs,2004,51(5):234-240 [10]Do T-N,Nguyen V-H．A novel speed-up SVM algorithm formassive classification tasks[C]∥Research,Innovation and Vision for the Future,2008．RIVF 2008．IEEE International Conference．July 2008:215-220 [11]Li Qi,Salman R,Test E,et al.Parallel multitask cross validation for Support Vector Machine using GPU[J]．Journal of Parallel and Distributed Computing,2013,73(3):293-302 [12] 。编程人员通过写简单的GPU内核程序,实现并行计算的功能。一个内核程序可以被多个线程并行执行。 多个线程可以组织成一个线程块,线程块内的线程共享内存和寄存器等资源。多个线程块组成一个内核网格,内核网格内的线程块间相互独立地并行执行。我们的SVM算法并行化工作基于LibSVM和CUDA。 在对SVM算法的分析中,根据矩阵x和向量y来计算矩阵Q,Qij ≡ yiyjK(xi,xj)。 Q＝∑li=1lj=1yiyjK(xi,xj)(5) 式中,K为核函数,矩阵Q的计算在CPU中占用大量的计算时间。将算法并行化,在GPU中每一个线程只对矩阵Q的行向量Qi进行计算: Qi＝∑li=1yiyjK(xi,xj)(6) 通过编写GPU内核程序获得较高的并行计算能力。CUDA采用SIMT架构,此架构中指令顺序执行,而且没有分支预测,如果有大量的逻辑判断,则会导致并行性能下降。因此在进行内核程序设计时,每个内核程序只做简单的循环,以提高程序的并行执行能力。 算法1SVM的并行算法P-SVM(Parallel Support Vector Machine) 1．在主存中初始化训练数据集xi∈Rn(i＝1,…,l)和分类指示向量y∈Rl,yi∈{1,－1}； 2．初始化Q,xi,y在GPU中的内存空间； 3．将主存中xi,y复制到GPU内存； 4．在GPU调用内核程序并行计算矩阵Q,实现式(6)的功能； 5．将计算结果从GPU内存复制到主存中； 6．CPU计算αi 和 b等参数； 7．根据参数对测试集进行分类。 为了提高内核程序的运行效率,在数据前期处理时,对训练数据集的样本属性值进行了两种不同的处理:在P-SVM中是普通表示方式,对每个样本向xi进行所有属性值的填充处理,使X为l×m的方阵,l为测试样本数,m为样本的属性数；另一种为数据稀疏表示,只填入样本中不为0的属性值,样本训练集不再是一方阵。 算法2SVM的稀疏并行算法SP-SVM(Sparse Parallel Support Vector Machine) 1．在主存中初始化训练数据集xi ∈ Rn(i＝1,…,l),和分类指示向量y∈Rl,yi ∈ {1,－1},xi为稀疏表示； 2．初始化Q,xi,y在GPU中的内存空间； 3．将主存中xi,y复制到GPU内存； 4．在GPU调用内核程序并行计算矩阵Q,实现式(6)的功能； 5．将计算结果从GPU内存复制到主存中； 6．CPU计算αi 和 b等参数； 7．根据参数对测试集进行分类。 显然,P-SVM适合样本属性值密集的情况,但在样本数据属性值稀疏情况下会导致空间浪费。而SP-SVM适合样本属性值比较稀疏的情况,但在样本数据属性值密集的情况下,由于要增加属性的标识,会导致内存空间的浪费。 对于P-SVM和SP-SVM这两种算法,在实验中采用稀疏数据,对性能进行了分析与比较。 4实验与分析 4.1实验环境 在实验中分别对训练样本数据量对于分类的准确度、并行算法对小数据量的运行效能和并行算法对大数据量的运行效能进行了对比与分析。实验数据采用文献 |
| No related articles found! |
|
||
Home