面向基于图的数据挖掘的FPGA加速方法研究

In the upcoming cloud computing era, data mining and massive data analysis are required to intelligently exploit the huge volumes of available data. The field programmable gate array (FPGA) is a versatile device, which can be programmed to implement virtual any digital processing function. In this project, we propose to employ an FPGA as a coprocessing unit to augment the traditional CPU-based computing platform to significantly improve the energy efficiency (measured by MB data processed per Joule) and performance of key data mining tasks. While various FPGA-based data mining accelerators have been proposed over the past five years, studies on graph-based data mining (GDM), one of the key techniques for knowledge and information discovery, remains largely unexplored. This proposal specifically targets the GDM area. ..The proposed research project includes (a) construction of IPs for the acceleration engine; (b) FPGA architectural customization of the acceleration engine; (c) soft error-aware FPGA architecture and CAD algorithms for GDM applications. Throughout the proposed research, we will simultaneously optimize the throughput and energy efficiency. Upon the completion of the proposed project, we expect to deliver a set of high-performance and energy-efficient macros or Intellectual Property (IP) blocks that support the reliable implementation of GDM algorithms in FPGAs. These macro blocks can be used to simplify the programming model while taking full advantage of the hardware resources provided by FPGAs. In addition, we will also deliver several promising new FPGA architecture options for GDM applications. FPGA vendors will benefit from the results of this research, which should expand the application domain of FPGAs and help guide their design of the next generations of FPGA families.

高效的"数据挖掘"方法在信息爆炸的"云计算"时代显得尤为重要。现场可编程门阵列（FPGA）是一种灵活的半定制电路，可以在流片以后用软件进行功能定制。尽管很多基于FPGA的"数据挖掘"加速算法在过去的五年中已经被提出，"基于图的数据挖掘"（一种在"知识发现"（KDD）领域的重要技术手段）的FPGA加速算法还没有被深入研究。本项目的核心研究内容是利用FPGA对"基于图的数据挖掘"问题进行硬件加速以及相关的基础科学技术问题。本项目的目标包括：针对"基于图的数据挖掘"问题建立一套高性能、高能效的FPGA的加速IP库、优化和设计FPGA体系结构、设计一套考虑"软错误"的容错FPGA体系结构和CAD算法。本项目所建立的IP库将简化编程模型、提高计算效率，很大程度上扩大"基于图的数据挖掘"的实践应用；同时本项目所提出的新的FPGA体系结构和CAD算法将为FPGA厂商设计下一代FPGA提供依据。

高效的“数据挖掘”方法在信息爆炸的“云计算”时代显得尤为重要。在此项目中，我们围绕“基于图的数据挖掘”中的相似度度量算法，动态时间规整（Dynamic Time Warping，DTW），进行了三个方面的研究：基于 FPGA和模拟电路的高性能加速引擎研究，基于CPU+FPGA架构的加速架构研究和面向物联网的应用研究。..在高性能加速引擎研究上， 我们提出了一套可扩展，可配置和高能量效率的基于FPGA 的 DTW 处理平台。相比于已有DTW的FPGA实现，我们提出的FPGA平台在相同性能的基础上能够提供运行中的可配置性，进而能够高效的处理不同特性的数据。我们同时提出了一种基于模拟电路的DTW加速引擎，相比于已有的DTW硬件实现，加速性能可提高2-3个数量级。高性能加速引擎能够加速数据中心的海量数据处理速度，同时提升数据处理的能量效率，对需要处理大量数据的物联网和云计算具有重要意义。..在基于CPU+FPGA架构的加速架构研究上，我们提出了一种CPU+FPGA异构平台的DTW加速架构。相比已有的基于指令集扩展的异构架构，我们提出的异构平台能够获得6.91倍的加速和3.88倍的能量效率提升。基于异构计算的嵌入式平台是物联网中的主要设备，本项目提出的高性能和高能量效率的嵌入式平台将会极大的促进具有移动性和高能效性要求的物联网应用的发展。..在面向物联网的应用研究上，我们将DTW算法应用到智能医疗和智能交通的应用。针对智能医疗，我们提出了一种基于DTW和EMD两种相似度度量的睡姿检测系统。相比于已有的睡姿检测系统，我们提出的睡姿检测算法的正确率提升了8.01%。针对智能交通应用，我们提出了一套交通检测平台，其车辆检测正确率达到88%。智能医疗是智能交通是物联网中的两个重要分支，以上两个应用的成功实现能够推动物联网的应用发展。