论文部分内容阅读
大数据时代的到来极大地推动了数据挖掘算法的研究与应用,其中KNN算法和K-means算法作为“十大数据挖掘算法”中分类算法与聚类算法的代表,被广泛应用于文本信息分类、金融预测、生物基因工程、图像信息处理等各个领域。然而随着信息和数据的爆炸式增长,KNN算法与K-means算法的快速实现面临着巨大的挑战,基于FPGA的新型异构计算平台为加速此类算法的实现提供了新的解决方案。与大型工作站或计算机集群相比,基于FPGA的新型异构计算平台具有价格更低、体积更小等优势;与GPU平台相比,FPGA平台具有功耗更低、能量效率更高等优势。因此,本文基于FPGA新型异构计算平台,对KNN和K-means两种数据挖掘算法进行OpenCL异构实现研究。首先,本文基于FPGA异构计算平台的特点,设计了KNN算法的异构实现方案KB-KNN。为了充分发挥异构平台的优势,本文将待分类数据进行分组,并采用设备间流水的并行实现方案,使异构系统中的主机与从机同时参与运算,增加硬件资源的利用率。在FPGA加速内核的设计上,本文改进了KNN算法中传统的一维并行排序方案,采用了更易并行,结构更加简单的K并行冒泡实现结构。为了充分利用FPGA的全局内存带宽,本文使用访存聚合等优化方法,提高了系统的吞吐量。其次,本文设计了基于FPGA异构计算平台的K-means算法实现方案FPKmeans。根据算法的特点,采用FPGA与CPU协同计算的实现方案,增加了硬件资源的利用率。对系统的访存行为进行了优化,减少全局内存的访问,并充分利用私有内存与本地内存提高了数据读取与写入的速度。最后,本文基于FPGA+CPU的异构计算平台,采用不同数据集对KB-KNN和PF-Kmeans异构加速方案进行了实现与测试,并分别与现有的基于GPU平台的方案CU-KNN和CU-Kmeans进行对比。测试结果表明,KB-KNN方案与移植到FPGA平台上的CU-KNN方案相比获得了1.7倍的加速比,与原始CU-KNN方案相比获得了1.5倍的能效比。本文设计的PF-Kmeans方案与移植到FPGA平台上的CUKmeans方案相比获得了2.3倍的加速比,与原始CU-Kmeans方案相比获得了2.1倍的能效比。