论文部分内容阅读
大数据时代,互联网每天都会产生大量的数据,利用数据挖掘算法可以从中分析出有价值的数据。在聚类分析方法中,K-means聚类算法是应用最广泛的一种划分方法。该算法简单,且收敛速度快,但面对大数据集时,通用处理器遇到运算量大的瓶颈,基于单核单机的串行程序已经无法满足要求。针对这些问题,基于Hadoop2.0,采用CPU和FPGA的集群架构,提出了一种大数据量下基于MapReduce的K-means聚类算法的FPGA加速系统,利用并行处理技术以提高大数据量下K-means聚类算法的处理速度。首先,分析K-means聚类算法,找出该算法中最耗时的计算过程。利用MapReduce并行编程模型的优点,对K-means算法进行并行化设计,确定map过程和reduce过程的任务。为了减少中间结果的回传,在map过程后设立一个combine过程。在单个计算节点上通过PCI-express总线连接若干个FPGA加速卡,利用驱动程序将MapReduce过程中最耗时的计算任务发往FPGA上进行计算,利用FPGA片上功能模块间流水化、功能模块内并行化优势,大幅提高了系统的运算速度。Map加速器处理逻辑包括接口部分和计算部分,其中接口部分包括PCIe接口模块、硬件平台接口模块、数据接收模块和数据发送模块;计算部分包括map报文解析模块、多个map计算模块、调度模块以及combine计算模块。Reduce加速器处理逻辑的接口部分和Map加速器使用的相同;计算部分包括Reduce报文解析模块、文档数累加模块以及文档向量累加模块。利用Verilog描述语言实现了Map加速器和Reduce加速器的处理逻辑。最后,对在FPGA上实现的所有功能模块进行仿真,整体联合仿真通过后,将整个处理逻辑下载到FPGA上进行验证,实验结果表明实现的处理逻辑正确。对整个系统进行集成测试,与传统Hadoop2.0平台下的K-means相关实现相对比,分析实验结果,验证新架构的可行性和和性能优势。