英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
用于支持向量机分类的新型级联FPGA加速器
Markos Papadonikolakis和Christos-Savvas Bouganis，IEEE会员
摘要 - 支持向量机（SVM）是一种功能强大的机器学习工具，为许多分类问题提供了最先进的准确性。然而，支持向量机分类是一个计算复杂的任务，它受到支持向量数量和问题维数的线性依赖。本文提出了一种用于加速SVM分类的完全可扩展的现场可编程门阵列（FPGA）体系结构，该体系结构利用了设备异质性和数据集属性间的动态范围差异。提出了一种自适应且完全定制的处理单元，其针对问题的特征利用现代FPGA器件的可用异构资源以有效的方式利用。实施结果证明了异构体系结构的效率，与CPU实施相比，提高了2-3个数量级的加速因子。所提出的体系结构胜过其他提出的FPGA和图形处理器单元方法超过七倍。此外，基于异构体系结构的特殊性质，本文首次介绍了面向FPGA的级联SVM分类器方案，该方案利用了FPGA的可重构性，加强了异构体系结构的定制算法性能。结果表明，所提出的级联方案能够进一步提高异构分类器吞吐量，而不会对资源利用率造成任何损失。
关键字 - 级联分类器，分类，现场可编程门阵列（FPGA），并行处理，支持向量机（SVM）。
- 引言
支持向量机（SVM）[1]是最受欢迎的监督学习实例之一，它们被认为是一种有效的机器学习方法，为广泛的回归和分类任务提供了良好的泛化性能[2]。 监督学习方法由两个谨慎的阶段组成，即训练和分类（或者在系统输出连续的情况下进行回归）。 SVM训练阶段负责识别这些数据点，称为支持向量（SVs），它可以最好地为这些类建立分离模型。 这些矢量然后用于预测分类阶段期间任何未来数据点的类别。
基于已知训练矢量数据库的SVM训练可以在线或离线执行，具体取决于应用。 SVM分类主要在新获得的数据中执行。 应用程序（如人脸检测，语音识别，生物信息学或地统计分析）通常需要在线分类并具有实时限制。 然而，SVM分类是一个计算量很大的任务，线性依赖于分类负载，SVs总数和问题的维数。 在需要解决大规模问题或必须维持高分类吞吐量的情况下，分类任务变得非常耗时，并且迫切需要加速。
根据目标问题，数据集可以表征为同质或异质。同构数据集经常在成像中得到满足，如人脸检测或识别[3]。在同质数据集中，数据集特征间的精度要求相同。例如，MNIST [4]由每个训练样本28 28个8位图像组成，并且它是同质问题，因为其样本的所有784个属性都需要8位表示。尽管如此，其他真实世界的数据集在其维度的动态范围内呈现出显着的多样性。这些异构数据集的属性可以是连续的，索引，分类或布尔值。例如，Adult [5]数据集的属性包括年龄，性别和婚姻状况等，这些属性可以分别表示为连续的，布尔型的和分类的，并且它们之间出现不同的精度要求。人们只需要一位来表示布尔属性，而根据数据集规范，婚姻状态分为七个不同的类别，三位表示就足够了。
通过自定义使用可用计算资源来考虑输入数据的性质，可以最大化SVM的性能。这是在计算设备上定位SVM分类器的强大动力，它可以利用定制精度算法（如FPGA）的潜力。 FPGA是半导体器件，包含可编程逻辑元件和多层可编程互连。现在，FPGA还包含粗粒器件，如存储器模块和嵌入式乘法器或数字信号处理模块（DSP）。
将硬件逻辑（例如乘法器）植入到可编程结构中使FPGA器件能够提高其性能效率。现代FPGA器件提供了大量的DSP模块和不同存储器大小的层次结构，提供了高度的灵活性和大量的并行计算能力。此外，它们的可移植性允许它们在应用程序受到带宽限制的情况下用作临时解决方案[6]。针对尺寸，维度和动态范围限制可能不同的不同分类问题，FPGA可重新配置可针对特定应用的标准产品和专用集成电路提供显着优势。 此外，现代FPGA器件能够以比通用图形处理单元更低的功耗提供相同或更好的性能。
分类任务复杂性的线性相关性表明，通过减少决策函数中使用的SV的数量可以提高执行时间。 进一步考虑这个想法，像[7] - [9]这样的工作提出了使用级联方案，以加速SVM分类任务。 这些体系结构将分类器以层叠的方式组合在一起，其中后续的分类器基于前一分类器的输出来生成分类决策。
本文提出了一种新的面向FPGA的加速SVM分类的方案。 该方案的新颖之处在于利用了FPGA的定制算法的潜力，以便在不同的算术精度下利用级联链的分类器。 首先，提出了一种完全可扩展的异构FPGA架构，其目标是利用该问题属性的精度要求，以便以最有效的方式使用现代FPGA器件的可用资源。 SVM训练处理器的最大并行化因子是通过维持DSP与逻辑资源之间的器件比例来实现的。 与以前的FPGA和图形处理单元（GPU）架构相比，所提出的FPGA架构结果显示了7和8的加速因子。
更进一步，所提出的级联分类器增强了异构分类器的特性，并以更高效的方式利用了精度和资源利用率之间的关系。 此外，所提出的级联架构采用FPGA的可重构性并扩展了架构的可能设计空间，以便针对由于其资源限制而不允许完全展开的级联方案的问题。 实施结果表明，在可用资源预算不允许全精度，完全展开实现或需要额外吞吐量的情况下，可以获得吞吐量或资源使用的显着增益。
本文的主要贡献如下。
1）一种新的FPGA架构的SVM分类，这充分利用了FPGA异构资源的并行处理能力，呈现优于以往的FPGA和GPU加速剂，并提供可扩展性和适应性的目标分类问题的性质相对于可用的资源限制。
2）在文献中引入了第一个级联SVM分类器，该分类器利用了FPGA器件的自定义算术电位，以便进一步提高SVM分类时间。
3）为了扩大级联方案的可能设计空间并增加其针对资源预算不允许完全级联实现的大规模问题的潜力，对级联分类器采用了FPGA可重构性。
本文的其余部分安排如下。第二部分给出了SVM的理论背景。在第三节中，描述了用于SVM分类器的异构FPGA实现，而在第四节中提出了所提出的级联分类器体系结构。第五部分提供了实施结果，本文在第六部分总结。
- 支持向量机
- 培训
SVM训练建立了一个能够基于训练数据集获得的SV来区分任何未来数据的所属类别的模型。 在一个两级分类问题上，SVM的目标是构建一个分离超平面w x-b=0，以实现类间的最大分离，如图1所示。类的超平面与分离平面平行，位于 每边。 两个超平面之间的欧几里得距离为2/||w||，因此SVM的目标是最大化类之间超平面之间的距离，或者换言之，最小化||w||
(1)
其中（）表示内积，是训练数据，标号表示数据的所属类别并且取值-1,1，w是到超平面方向的垂直向量，b是到原点的偏移，以及 N是训练集大小。SVM训练阶段侧重于SV的识别，SV是最接近超平面并确定其方向的训练样本。
通过使用方形编程（QP）技术来解决SVM训练问题是一项计算上昂贵的任务，特别是对于大型高维数据集。 因此，已经提出了许多算法来将QP问题分解为更小的问题，如顺序最小优化[10]，SVMLIGHT [11]或SVMPERF [12]。 其他一些作品[13]，[14]从几何角度来解决这个问题。 这些解决方案最重要的方面是，对于每次迭代，需要计算数据与所有其他数据集点之间的点积。
在许多现实世界的分类问题中，线性分离原始空间中的数据通常是不可行的。 SVM采用更复杂或高性能空间的特性对于其广泛的适用性而言是微不足道的。每当训练数据在输入空间中不能线性分离时，输入空间就映射到一个更高维的输入空间，在那里线性分离是可行的。 然而，对于所有数据点而言，这种高维空间映射的显式构造是一项计算量大的任务，特别是在大规模问题中，甚至是不可行的，因为空间的维度可能是无限的。支持向量机可以通过使用核函数K（xi，xj）来替代优化问题（1）中的内积，
在许多可能的核函数中，特别感兴趣的是满足Mercer条件[15]的那些函数，并且可以表示为高维空间中的内积。 通过应用内核，不需要将数据显式映射到更高维的空间[16]。
- 分类
与针对SVM训练问题提出的各种算法求解器不同，SVM分类函数是通用且直接的。 在分类阶段，任何新的数据x根据决策函数的输出进行分类
其中|NSV|是训练阶段确定的一组SV的基数。 很容易推导出，非线性SVM分类任务的计算时间线性依赖于分类数据集的大小，SV群体NSV和问题的维数。 对于线性支持向量机，核K（xi，x）被内积代替，利用其分布性，分类复杂度不依赖于NSV。然而，对于非线性支持向量机，决策函数F需要大量数据集的大量矩阵向量运算。然而，矩阵向量计算提供了显着的并行化潜力，这可以被FPGA器件的并行硬件资源利用。
- SVM分类器的硬件映射
本节介绍了基于SVM级联分类器的基于异构FPGA的SVM分类器，它是级联方案的基础工作。 首先，提供了基于硬件的SVM分类器的相关工作，随后概述了异构FPGA体系结构以及对超结构的深入分析，这是FPGA体系结构的异构处理元件。 最后一节介绍了hypertile的设计流程，并演示了所提出的体系结构如何利用任何目标SVM分类问题的动态范围多样性，以最高资源效率并因此最大化并行化的分类加速器。
- 硬件映射SVM分类的相关工作
本节概述了以前的一些关于SVM分类的FPGA或GPU映射工作。在文献[17]中介绍了一种用于SVM训练的基于FPGA的同构架构，其结果可能会加速SVM分类。另一项同构工作在文献[18]中提出，其中使用目标器件的可用DSP单元提出并行FPGA协处理器用于内积计算。内核计算由主机CPU执行，与[17]不同，内核函数使用浮点流水线。 [18]中的集成解决方案针对大型FPGA器件，并成功加速了SVM分类。尽管如此，本文并没有充分利用现代FPGA器件的异构性和完全定制算法的潜力，也没有针对训练问题的精度要求。乘法器仅由硬逻辑DSP模块实现，大量的FPGA软逻辑没有得到有效利用。文献[19]的工作在Xilinx Virtex II器件上对其SVM训练架构进行了深入分析。本文可能会被用于分类解决方案。但是，由于目标器件的资源限制，它没有利用现代FPGA的并行化潜力。在[20]中，提出了一种基于对数系统（LNS）的新型实现。 基于LNS的SVM内核的实现也在[21]中被采用，以产生一种硬件友好的方法。这些工作更关注使用LNS解决SVM问题的可能性，而不是加速问题，因为目标设备很小，并且所有点积评估都只使用一个Multiply-AC累积（MAC）单元。 文献[22]中提出的FPGA架构采用硬件友好的方法来进行基于CORDIC算法的内核评估，而没有关注FPGA逻辑资源的最大利用率以加速SVM分类。SVM分类用于[23]中的视频狗屎边界检测。仅针对线性SVM，并将FPGA器件用于SVM算法的点积映射。
其他作品，如[24]和[25]，使用NVidia的计算统一设备架构[26]编程环境，将SVM分类问题映射到GPU的并行计算资源。 它们的主要区别与内核计算所选择的浮点精度以及用于处理内核评估某些部分的主机CPU的使用有关，因为在这些数据馈入GPU之前。 此外，[27]中的GPU工作的目标是基于Gilbert算法[28]的SVM训练问题的几何解释[14]，而分类实现类似于[24]和[25]。
SVM分类器的FPGA体系结构
总而言之，可以看出，以前所提供的任何工作都没有着眼于针对目标问题的本质，精度要求和特性探索FPGA器件上可用的庞大异构资源。大部分工作都是针对特定应用的，并且在任何目标问题的限制下利用硬件资源的有效方法都未得到充分研究。此外，GPU是浮点设备，这意味着当针对GPU设备进行SVM分类时，无法采用基于自定义算法的资源优化。作为结论，到目前为止，还没有向作者的最佳知识提出工作，即利用数据集属性中的异质性并研究可充分利用此属性的分类器体系结构。此外，文献中还没有可用的工作来讨论级联的可能性，即基于FPGA或基于精度的SVM分类加速。
- SVM异构分类器的FPGA体系结构
SVM分类器设计背后的基本原理是利用FPGA异构资源提供的并行计算能力以及FPGA内部存储器以最有效的方式提供的高内存带宽，以加速决策功能（ 3）。F（x）的计算涉及矩阵向量运算，这是高度可并行化的。 因此，问题可以分割成更小的问题，并行单元可以实例化处理每个子问题。
所提出的SVM分类器的FPGA架构如图2所示.SV被加载到内部FPGA存储器中，而分类数据集被加载到FPGA板的可靠性和可维护性研讨会（RAM）上， In，主机和FPGA之间的先出单元。数据点被传送到FPGA中并馈送给每个分类器hypertile，这是架构的处理单元。每个hypertile正在处理整个分类函数的一个片段。 hypertile输出内核评估K，然后并行添加。当（3）的总和完成时，每个数据的类别由系统流出。在SV无法装入FPGA RAM块的情况下，通过流出中间结果并使用下一个SV子集重新加载FPGA RAM来将分类分为多个步骤。图3显示了用于多周期分类任务的内部和外部FPGA存储器的并行存储器访问。与FPGA IO相关的访问以灰色着色，而内部FPGA存储器访问为白色。 出于说明的原因，该图显示仅处理四个测试数据。 对于大规模分类问题，核心投影更加耗时，下一个SV子集重新加载的空闲空间变得可以忽略不计。
所提出的FPGA架构的存储器访问时序流程。 读写RAM操作分别缩写为“rd”和“wr”，中间结果记为“temp”
-
分类器
全文共15726字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15833]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
