收藏本站
《上海交通大学》 2013年
加入收藏

CUDA图形处理器对聚类算法的加速实现

马仁骏  
【摘要】:近些年来,伴随着信息处理以及通信技术的快速发展,促进了许多领域输出以及获取数据能力的进一步提高,这给我们带来了海量有待处理的数据信息。如今,GB或是TB数量级的数据已经十分常见。因此,传统串行化的数据挖掘技术已无法有效地对这些数据进行处理,取而代之的就是并行化的数据挖掘技术。如今,多核CPU(Central Processing Unit)作为并行化数据挖掘的计算平台已经十分普遍。但是,随着数据规模逐渐增大,数据挖掘所涉及算法的复杂度越来越高,其所带来的高密度数据运算将会耗费处理器大量的运算时间,这对整个系统的性能以及功耗是十分不利的。为了降低这部分大规模数据的运算量,我们需要选择一个更加适合这类运算的计算处理单元来减轻系统的负荷。而图形处理器——GPU(Graphics Processing Unit),凭借其特殊的体系结构,十分适合大规模高密度数据的并行计算。在设计之初,GPU的设计者们就为其配置了大量的数据计算单元以及较高内存访问带宽以应对日益苛刻的图形处理以及电子游戏等应用的要求。特别是自从NVIDIA在2007年推出CUDA(Compute Unified Device Architecture)架构的GPU产品及其配套的开环境后,使得基于GPU平台的开发与基于CPU平台的开发十分相似,让开发者能够快速地开始基于CUDA架构的GPU进行开发。目前,在很多领域,如科学计算、金融工程、数据挖掘等,开发者们都在尝试使用CUDA架构GPU来提升系统的运算能力。除了在传统的单机环境中实现GPU运算,同时对于GPU在分布式环境中应用也有了越来越多的研究。本论文将选取两种数据挖掘领域中普遍使用的聚类算法,k均值聚类以及单链合并式分层聚类,并基于一款NVIDIA GTX260系列CUDA架构的GPU分别对两种聚类算法进行并行化的实现,从而论证了GPU对于聚类算法性能提升的有效性及可行性。最后本文将结合企业客户关系管理系统(Customer Relationship Management,CRM)的实际需求,实现Hadoop框架下的GPU聚类运算。聚类是数据挖掘过程中一个十分常用的操作,其主要目的是将随意散开的对象根据某种约定的相似性或相关度将其聚集在一起,形成一个或多个簇。本论文所实现的k均值聚类算法,主要是指将N个待聚集的对象或称节点按照其空间欧式距离的远近将其划分到距离最近的簇中,数次迭代后,最终形成K个簇。作为一种经典的聚类算法,该算法已被广泛使用于数据挖掘、生物信息、图像识别、人工智能等领域。其中著名的Apache Mahout就在其聚类运算中用到k均值聚类算法。对于实验中所实现的另一种聚类算法——合并式分层聚类,首先将N个独立的数据对象初始化为N个独立的子簇,然后以欧式距离作为子簇间相似度的度量标准,将距离最近的子簇进行合并,多次迭代后,以整个数据集中所有数据对象都包含于一个簇中作为算法的结束。虽然其所实现的操作与最终结果都与k均值有所不同,但是算法中都包含了大规模的数据运算,并且计算之间有较高的独立性,正是因为这种共性,使我们能够利用多核CPU和GPU对聚类算法进行并行化处理,从而大幅缩减其程序运行时间及提高了数据的吞吐量。由于企业CRM需要运行于分布式计算环境中,从而选择了开源软件Hadoop。Haoop框架可以让用户将普通性能的计算机组成集群进行大规模数据的分布式计算,同时提供了很强的容错性及可靠性。目前,诸如Google、Facebook等公司都在使用基于Hadoop框架的分布式计算。本论文的实验中,分别设计了三组不同规模的输入数据及目标聚类数进行k均值运算。同时由于硬件条件所限,对于分层聚类算法,设计了较k均值聚类小一些的数据规模。根据CUDA的编程模型,程序分为两部分,其中非高密度计算的程序运行在CPU端,而聚类运算所涉及到的大规模浮点数数学运算则运行在GPU端,这种模型也被称为CPU+GPU的异构计算。同时我们也将相同的实验对象基于多核CPU进行运算。最后通过对比两种实现方式的运算耗时,获得基于GPU实现的加速比。最后本文将实现基于Hadoop框架的GPU聚类运算,其中的实现方法及结果可以作为企业CRM设计的原型与参考。
【关键词】:多核CPU 并行计算 GPU CUDA 数据挖掘 k均值算法 单链 分层聚类 Hadoop MapReduce
【学位授予单位】:上海交通大学
【学位级别】:硕士
【学位授予年份】:2013
【分类号】:TP311.13
【目录】:
  • 摘要3-5
  • ABSTRACT5-10
  • 1 绪论10-12
  • 2 多核处理器与并行计算12-20
  • 2.1 微处理器的发展12-13
  • 2.2 多核CPU处理器13-15
  • 2.3 GPU——图形处理器15-17
  • 2.4 并行计算的编程方式17-20
  • 3 GPU高性能计算20-27
  • 3.1 GPU的高性能计算20-23
  • 3.1.1 传统GPU体系结构20-22
  • 3.1.2 可编程的GPU22-23
  • 3.2 GPU通用计算23-24
  • 3.3 CUDA架构的GPU通用计算24-27
  • 4 聚类算法的研究27-33
  • 4.1 数据挖掘27-29
  • 4.1.1 数据挖掘介绍27-28
  • 4.1.2 知识发现与数据挖掘28-29
  • 4.2 聚类分析29-33
  • 4.2.1 k均值算法的程序设计30-32
  • 4.2.2 分层聚类算法的程序设计32-33
  • 5 基于CUDA的聚类算法实现33-49
  • 5.1 CUDA编程模型33-38
  • 5.1.1 线程模型33-35
  • 5.1.2 内存模型35-37
  • 5.1.3 CPU与GPU的协作37-38
  • 5.1.4 CUDA编程环境38
  • 5.2 聚类算法实现38-46
  • 5.2.1 环境搭建38-39
  • 5.2.2 k均值聚类算法的程序设计及实现39-43
  • 5.2.3 单链合并式分层聚类算法的程序设计及实现43-46
  • 5.3 实验结果分析46-49
  • 6 GPU聚类的分布式计算实现49-56
  • 6.1 分布式的CRM系统设计49-50
  • 6.2 HADOOP框架中的GPU聚类实现50-55
  • 6.2.1 Map/Reduce模式的程序设计50-53
  • 6.2.3 分布式环境执行53-55
  • 6.3 结论与分析55-56
  • 7 结论与展望56-57
  • 参考文献57-59
  • 致谢59-60
  • 攻读学位期间发表的学术论文目录60-63
  • 附件63

【相似文献】
中国期刊全文数据库 前10条
1 ;NVIDIA GeForce FX被评为2002年最佳图形处理器[J];CAD/CAM与制造业信息化;2003年Z1期
2 李海燕;张春元;李礼;任巨;;图形处理器的流执行模型[J];计算机工程;2008年22期
3 ;MathWorks为MATLAB提供GPU支持[J];电子与电脑;2010年10期
4 杨毅;郭立;史鸿声;郭安泰;;面向移动设备的3D图形处理器设计[J];小型微型计算机系统;2009年08期
5 ;MathWorks为MATLAB提供GPU支持[J];电信科学;2010年10期
6 ;MathWorks为MATLAB提供GPU支持[J];中国电子商情(基础电子);2010年10期
7 ;MathWorks为MATLAB提供GPU支持[J];电信科学;2010年S2期
8 韩俊刚;刘有耀;张晓;;图形处理器的历史现状和发展趋势[J];西安邮电学院学报;2011年03期
9 ;产品推介[J];电子产品世界;2012年09期
10 ;产业信息[J];单片机与嵌入式系统应用;2013年12期
中国重要会议论文全文数据库 前7条
1 张春燕;;一种基于图形处理器的数据流计算模式[A];全国第19届计算机技术与应用(CACIS)学术会议论文集(下册)[C];2008年
2 徐侃;陈如山;杜磊;朱剑;杨阳;;可编程图形处理器加速无条件稳定的Crank-Nicolson FDTD分析三维微波电路[A];2009年全国微波毫米波会议论文集(下册)[C];2009年
3 周国亮;冯海军;何国明;陈红;李翠平;王珊;;基于图形处理器的Cuboid算法[A];第26届中国数据库学术会议论文集(B辑)[C];2009年
4 毕文元;陈志强;;利用可编程图形处理器加速CT重建与体数据的绘制[A];第十一届中国体视学与图像分析学术会议论文集[C];2006年
5 刘伟峰;杨权一;曹邦功;孟凡密;周洁;;基于GPU的高度并行Marching Cubes改进算法[A];2008年全国开放式分布与并行计算机学术会议论文集(上册)[C];2008年
6 林旭生;田绪红;冯志炜;陈茂资;;GPU加速的蚁群算法在HP模型中的应用[A];第十四届全国图象图形学学术会议论文集[C];2008年
7 方建文;于金辉;陈海英;;三维卡通水与物体交互作用的动画建模[A];中国计算机图形学进展2008--第七届中国计算机图形学大会论文集[C];2008年
中国重要报纸全文数据库 前10条
1 乐山 乐水;图形处理技术的全球专利布局形势[N];中国知识产权报;2010年
2 严威川;明明白白显卡“芯”[N];中国电脑教育报;2007年
3 ;NEC图形处理器每秒运行50.2G条指令[N];计算机世界;2003年
4 游讯;图形处理器GPU[N];人民邮电;2011年
5 本报记者 姜姝;AMD嵌入式技术为波音飞机保驾护航[N];中国信息化周报;2014年
6 均儿;人人都有台超级计算机[N];电脑报;2008年
7 ;AMD启动“Fusion”企业品牌推广计划[N];人民邮电;2008年
8 本报记者 田梦;Adobe CS4全面支持GPU加速[N];计算机世界;2009年
9 赵欣;“玩”3D,笔记本也行![N];中国计算机报;2003年
10 ;HP Compaq Evo D210教育信息化的好帮手[N];中国计算机报;2003年
中国博士188bet全文数据库 前7条
1 祖渊;基于图形处理器的高速并行算法研究[D];中国科学技术大学;2014年
2 李雪;基于图形处理的多点地质统计算法及模型评价[D];中国科学技术大学;2016年
3 曹小鹏;图形处理器关键技术和光线追踪并行结构研究[D];西安电子科技大学;2015年
4 杨珂;基于图形处理器的数据管理技术研究[D];浙江大学;2008年
5 穆帅;针对不规则应用的图形处理器资源调度关键技术研究[D];清华大学;2013年
6 夏健明;基于图形处理器的大规模结构计算研究[D];华南理工大学;2009年
7 黄涛;基于GPU的多点地质统计逐点模拟并行算法的研究[D];中国科学技术大学;2013年
中国硕士188bet全文数据库 前10条
1 刘锐;GPU在FD-OCT系统数据处理及实时图像显示中的应用[D];北京理工大学;2015年
2 彭欢;基于GPU的二维FDTD加速算法研究[D];西安电子科技大学;2013年
3 徐蔚;基于图形处理器的窗口系统的研究[D];西安工程大学;2015年
4 孙修宇;基于GPU的三维图像重建方法研究[D];中国民航大学;2011年
5 刘伍锋;基于PCI总线的主设备功能仿真与验证[D];西安电子科技大学;2016年
6 李天骥;图形处理器存储系统的高精度System Verilog模型与自动化仿真验证[D];西安电子科技大学;2016年
7 陈贵华;基于RDMA高性能通信库的设计与实现[D];华中科技大学;2015年
8 马仁骏;CUDA图形处理器对聚类算法的加速实现[D];上海交通大学;2013年
9 黄伟钿;面向移动平台的3D图形处理器的设计[D];华南理工大学;2011年
10 王旭;图形处理器的仿真验证[D];哈尔滨工业大学;2007年
 快捷付款方式  订购知网充值卡  订购热线  帮助中心
  • 400-819-9993
  • 010-62791813
  • 010-62985026