大规模并行排序学习算法研究

发布时间：2017-04-28 19:06

  本文关键词：大规模并行排序学习算法研究，由笔耕文化传播整理发布。

【摘要】：搜索引擎可以帮助用户查找相关的信息,搜索引擎返回的搜索结果决定了搜索引擎的质量,因此,如何获得最优的搜索结果,以使得用户得到与自己所请求的数据最相关的结果就显得尤其重要,排序学习的出现为解决这一问题提供了新的思路,它可以通过对用户所要检索的信息进行必要的排序,按与用户的请求的相关度输出相关信息。虽然传统的排序学习算法可以很好地解决小规模文本的排序问题,然而由于互联网行业的快速发展,互联网信息总量不断地膨胀,传统的排序学习算法无法有效实时地处理大规模数据,因此,本文使用两种并行编程模式分别对排序学习算法进行加速。本文的主要研究内容如下:(1)选择OpenCL(Open Computing Language)并行计算模型来加速本文算法,同时介绍了排序支撑矢量机算法(Ranking Support Vector Machine,RSVM)以及序贯最小化算法(Sequential Minimal Optimization,SMO)的相关知识并详细分析SMO算法的具体步骤,根据GPU(Graphic Processing Unit)硬件架构的特点分析串行算法,设计了相应的并行算法流程,对算法中的可并行部分采用OpenCL进行编程加速,实验结果表明与串行排序支撑矢量机算法相比,并行排序支撑矢量机算法的加速性能最高提升了90多倍。同时为了验证OpenCL程序的可移植性,将OpenCL并行程序移植到多种异构设备中,并对基于OpenCL的并行排序学习算法在各个设备的性能差异进行了详细分析。(2)将基于OpenCL的并行排序支撑矢量机算法扩展到多GPU下运行,同时对多GPU实施过程中的同步问题进行了详细分析,运用一种有效的同步方式减少了多个设备之间的同步开销,在多GPU上运行的结果表明并行算法的加速性能相对于单GPU又有了进一步的提升。(3)利用多线程并行编程模式OpenMP(Open Multiple Processing)将排序支撑矢量机算法并行化,并在多核CPU和Intel MIC(Many Integrated Core)上进行实验,结果表明基于OpenMP的并行排序支撑矢量机算法在多核CPU与MIC上都取得了优异的加速效果。同时比较了基于OpenCL和OpenMP的并行排序支撑矢量机算法在多核CPU与MIC上的性能,分析了两种编程模式的差异。
【关键词】：排序学习 并行计算 OpenCL OpenMP 可移植性
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP391.3;TP18
【目录】：

• 摘要5-6
• ABSTRACT6-10
• 符号对照表10-11
• 缩略语对照表11-14
• 第一章 绪论14-20
• 1.1 相关研究背景14-15
• 1.2 国内外研究现状15-18
• 1.2.1 排序学习算法的研究现状15-16
• 1.2.2 国内外并行计算研究现状16-18
• 1.3 本文主要研究内容18-19
• 1.4 本文组织架构19-20
• 第二章 并行排序学习算法相关知识概述20-32
• 2.1 排序学习算法20-25
• 2.1.1 排序学习概念20-22
• 2.1.2 排序支撑矢量机22-24
• 2.1.3 排序学习评价指标24-25
• 2.2 并行硬件架构25-27
• 2.2.1 GPU架构25-26
• 2.2.2 Intel MIC众核架构26-27
• 2.3 并行编程模型27-29
• 2.3.1 OpenCL模型27-29
• 2.3.2 OpenMP模型29
• 2.4 本章小结29-32
• 第三章 基于GPU的OpenCL并行排序学习算法32-52
• 3.1 序贯最小化算法的并行性分析32-35
• 3.2 基于单GPU的并行排序支撑矢量机算法35-38
• 3.3 基于单GPU的PRSVM算法实验结果与分析38-44
• 3.3.1 LETOR数据集38-39
• 3.3.2 实验环境39-40
• 3.3.3 单GPU上的实验结果分析40-41
• 3.3.4 OpenCL程序可移植性实验分析41-44
• 3.4 基于多GPU的并行排序支撑矢量机44-50
• 3.4.1 基于多GPU的PRSVM算法实施细节44-47
• 3.4.2 多设备间的线程同步47-48
• 3.4.3 多GPU上的实验结果分析48-50
• 3.5 本章小结50-52
• 第四章 基于多核与众核的OpenMP并行排序学习算法52-62
• 4.1 基于多核CPU的OpenMP并行排序支撑矢量机实施细节52-54
• 4.2 基于MIC的Open MP并行排序支撑矢量机实现与优化54-55
• 4.3 实验结果与分析55-61
• 4.3.1 实验环境55-56
• 4.3.2 基于多核CPU与MIC的实验结果分析56-59
• 4.3.3 基于OpenCL和OpenMP的PRSVM算法性能比较分析59-61
• 4.4 本章小结61-62
• 第五章 总结与展望62-64
• 5.1 本文工作总结62-63
• 5.2 未来工作展望63-64
• 参考文献64-68
• 致谢68-70
• 作者简介70-71

【相似文献】

中国期刊全文数据库 前10条

1 朱锐;徐友云;蔡跃明;;低密度奇偶校验码的构造[J];军事通信技术;2005年04期

2 刘星成;程浩辉;;基于PEG算法的准循环LDPC码构造方法研究[J];电路与系统学报;2009年04期

3 郑斌;李涓子;;一种基于FP-Growth的改进算法[J];平顶山工学院学报;2008年04期

4 朱延广;梅珊;赵雯;朱一凡;;支持复杂产品总体优化设计的多算法协作优化框架研究[J];系统仿真学报;2007年11期

5 白洪涛,孙吉贵,焦洋,徐长青;网络优化算法的实现与比较[J];吉林大学学报(信息科学版);2002年02期

6 刘康,余玲;蚁群算法及其连续优化算法初析[J];四川轻化工学院学报;2004年01期

7 黄琪;李丹;汪洋;张钦宇;;一种优化LDPC码环分布的改进算法[J];通信技术;2010年05期

8 徐艳;董涛;;一种防火墙规则冲突快速检测算法[J];计算机技术 与发展;2013年09期

9 张磊;沈夏炯;韩道军;安广伟;;基于同义概念的概念格纵向合并算法[J];计算机工程与应用;2007年02期

10 谢廷婷;;频繁集挖掘算法研究[J];计算机与现代化;2007年03期

中国重要会议论文全文数据库 前2条

1 潘志明;郑骏;钱卫宁;周傲英;;构造XML相似相关结构库的一种有效方法[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

2 林景亮;董槐林;姜青山;吴书;;一种基于新增阈值的频繁模式挖掘算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

中国博士学位论文全文数据库 前6条

1 张磊;基于概念格的角色工程相关算法研究[D];哈尔滨工业大学;2015年

2 孟静;新型Krylov子空间算法及其应用研究[D];电子科技大学;2015年

3 唐益明;（1，，2，2）型异蕴涵泛三I算法及其应用研究[D];合肥工业大学;2011年

4 牛云云;求解计算困难问题的膜计算模型与算法研究[D];华中科技大学;2012年

5 李冬冬;基因组序列标注的算法与理论研究[D];国防科学技术大学;2004年

6 周琨;航空公司航班运行调度模型与算法研究[D];南京航空航天大学;2012年

中国硕士学位论文全文数据库 前10条

1 闫铭;基于度量学习的不完整数据聚类方法研究[D];哈尔滨工业大学;2015年

2 张小琼;基于改进萤火虫群优化算法的BP神经网络研究[D];广西大学;2015年

3 李俊杰;基于蚁群算法的聚类区分器设计研究[D];电子科技大学;2014年

4 艾慧;天波雷达电离层污染校正与测高算法研究[D];电子科技大学;2015年

5 陈红强;大规模并行排序学习算法研究[D];西安电子科技大学;2014年

6 白鹭;基于自适应人工免疫进化的网格聚类算法研究[D];沈阳大学;2010年

7 纪彤坤;概念格Chein算法的研究与改进[D];华南理工大学;2012年

8 钱伟强;一种基于改进粒子群和K均值结合的聚类算法[D];西安电子科技大学;2011年

9 张菲;蜂群混合算法[D];西安电子科技大学;2013年

10 陆丽娟;强跳跃显露模式挖掘算法及其应用[D];湖南大学;2011年

  本文关键词：大规模并行排序学习算法研究，由笔耕文化传播整理发布。

本文编号：333373