基于MapReduce的K-means聚类算法的FPGA加速研究

摘要

大数据时代，互联网每天都会产生大量的数据，利用数据挖掘算法可以从中分析出有价值的数据。在聚类分析方法中，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相关实现相对比，分析实验结果，验证新架构的可行性和和性能优势。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 课题研究背景和意义

1.2 国内外研究概况

1.3 论文研究内容与结构安排

2 相关技术介绍

2.1 K-means聚类算法

2.2 MapReduce计算框架

2.3 本章小结

3 基于MapReduce的K-means算法的FPGA设计

3.1 系统整体架构

3.2 K-means算法的MapReduce并行化设计

3.3 Map加速器的总体设计方案

3.4 Reduce加速器的总体设计方案

3.5 本章小结

4 基于MapReduce的K-means算法的FPGA实现

4.1 加速器整体框架

4.2 加速器接口部分逻辑实现

4.3 Map加速器计算部分逻辑实现

4.4 Reduce加速器计算部分逻辑实现

4.5 本章小结

5 功能模块仿真

5.1 Map加速器功能模块仿真

5.2 Reduce加速器功能模块仿真

5.3 本章小结

6 实验及结果分析

6.1 实验环境与评价方法

6.2 系统集成测试与结果分析

6.3 本章小结

7 总结与展望

7.1 全文总结

7.2 研究展望

致谢

参考文献

附录1 攻读硕士学位期间申报的发明专利目录