基于FPGA的聚类算法的加速平台的研究与设计

发布时间：2017-09-19 11:22

  本文关键词：基于FPGA的聚类算法的加速平台的研究与设计

  更多相关文章： 聚类算法 加速平台 片外访存 加速比 能效比

【摘要】：聚类分析在人类工作生活中扮演着越来越重要的角色,目前已被广泛运用于许多不同的领域,如市场调研、模式识别、数据挖掘、图像处理、客户分割、Web文档分类等。随着互联网和电子商务的飞速发展,各行各业采集、积累或急需处理的数据呈现海量式的增长。海量的数据大大降低了聚类分析的效率,针对各种聚类算法加速的研究成为了人们探讨的重要课题。不同的应用领域以及不同类型的数据集需要使用不同的聚类算法才能够获得较好的聚类效果,由此可见高效实现多种聚类算法是很有必要的。目前聚类算法的加速平台主要有云计算平台和硬件加速平台,其中硬件加速平台主要有GPU、FPGA以及ASIC。云计算平台采用集群的方式将应用进行划分,然后将划分后的任务分配到各个PC节点,各个节点处理任务并将计算结果汇总到总机。这种加速方式需要多个PC机,而且算法的加速最终受限于网络带宽；硬件加速平台利用硬件自身速度快的特点,使用硬件来代替软件或者CPU来实现具体功能逻辑,而且大量的内置硬件逻辑部件使得硬件加速平台可以更好地采用并行和流水的方式加速算法的执行。硬件加速平台的加速效果好、不受限于带宽而且相比云计算平台加速成本更低。综上,硬件加速平台是算法加速的一种有效的加速平台。目前,硬件加速器的设计大多针对单一特定的算法,对加速器的通用性和灵活性的研究很少。虽然GPU提供了解决通用性和灵活性的方法,但是对通用性和灵活性的支持使得GPU带来了高能耗的问题,而FPGA会获得更好的节能效果。但是目前基于FPGA的加速器都是针对特定算法设计特定的硬件加速模块的,使得该硬件加速器仅支持一种算法,大大限制了硬件加速器的通用性和灵活性。能否设计一种基于FPGA的硬件加速器,使之能够支持多种聚类算法呢?本文采用软硬件结合的方式实现了一个基于FPGA的硬件加速系统平台,它能够支持K-means、PAM、SLINK、DBSCAN四种聚类算法和两种相似度度量标准。基于对算法的热点代码和局部性的分析,加速器解决了频繁的片外访存问题,最后通过提取热点代码的公共算子,最大化地平衡了加速器的通用性以及灵活性和加速性能之间的关系,使得加速器支持通用性和灵活性的同时又兼顾了加速器的加速性能。为了评估加速器的性能,将加速器分别与CPU和GPU作了比较,给出了相应的加速比和能效比,并测试与分析了影响加速器加速性能的因素。
【关键词】：聚类算法 加速平台 片外访存 加速比 能效比
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13
【目录】：

• 摘要5-6
• ABSTRACT6-15
• 第1章 绪论15-21
• 1.1 课题背景及意义15-16
• 1.2 国内外研究现状16-18
• 1.3 本文研究内容18-19
• 1.4 论文的组织安排19-21
• 第2章 相关基础知识简介21-27
• 2.1 算法介绍21-25
• 2.1.1 K-means算法21-22
• 2.1.2 PAM算法22-23
• 2.1.3 SLINK算法23-24
• 2.1.4 DBSCAN算法24-25
• 2.2 硬件加速技术介绍25-26
• 2.3 本章小结26-27
• 第3章 加速系统的软硬件功能划分27-37
• 3.1 软硬件协同设计的设计流程27-29
• 3.2 热点代码分析29-35
• 3.2.1 K-means算法的热点分析30
• 3.2.2 PAM算法的热点分析30-31
• 3.2.3 SLINK算法的热点分析31-32
• 3.2.4 DBSCAN算法的热点分析32
• 3.2.5 算法软硬件划分的结果32-35
• 3.3 相同代码的提取和局部性分析35-36
• 3.3.1 相同代码的提取35
• 3.3.2 局部性分析35-36
• 3.4 本章小结36-37
• 第4章 硬件加速器的设计与实现37-51
• 4.1 加速器的框架结构介绍37-39
• 4.1.1 加速器的基本框架37-38
• 4.1.2 执行单元的内部结构38-39
• 4.2 加速方案的选择39-42
• 4.2.1 并行方式的加速方案39-40
• 4.2.2 流水方式的加速方案40-41
• 4.2.3 加速方案的分析与比较41-42
• 4.3 硬件逻辑单元的设计42-48
• 4.3.1 指令集的设计42-45
• 4.3.2 指令集的硬件实现45-48
• 4.4 频繁片外访存的解决方案48-50
• 4.5 本章小结50-51
• 第5章 软件子系统的设计51-57
• 5.1 加速器的操作系统模式51-54
• 5.1.1 操作系统模式下加速器的工作流程51-53
• 5.1.2 数据填充53-54
• 5.2 面向用户的接口设计54-56
• 5.3 本章小结56-57
• 第6章 加速平台的性能测试与分析57-69
• 6.1 实验环境57-58
• 6.2 加速器的性能评估58-64
• 6.2.1 硬件加速器的加速效果58-62
• 6.2.2 加速器的能耗评估62-64
• 6.3 影响加速器加速比的因素的测试与分析64-67
• 6.3.1 数据集规模VS加速效果64-66
• 6.3.2 向量维度VS加速效果66
• 6.3.3 簇的个数VS加速效果66-67
• 6.4 误差分析67-68
• 6.5 本章小结68-69
• 第7章 总结和展望69-73
• 7.1 工作总结69-70
• 7.2 未来工作展望70-73
• 参考文献73-77
• 致谢77-79
• 在读期间参加的科研项目79-81
• 在读期间的学术论文81

【参考文献】

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

1 郎为民;陈凯;张国峰;;无监督学习在认知网络中的应用研究[J];电信快报;2014年02期

2 周涛;陆惠玲;;数据挖掘中聚类算法研究进展[J];计算机工程与应用;2012年12期

3 赵旭;郝莉;;基于FPGA的实时视频采样控制器设计[J];成都信息工程学院学报;2008年03期

4 孙吉贵;刘杰;赵连宇;;聚类算法研究[J];软件学报;2008年01期

5 贺玲;吴玲达;蔡益朝;;数据挖掘中的聚类算法综述[J];计算机应用研究;2007年01期

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

1 白冬艳;数据挖掘在煤炭综合统计系统的应用研究[D];河北工程大学;2010年

，

本文编号：881344