改进的基于FPGA平台的COVID-19案例的KNN分类算法的优化实现

¼ð···Þ第十章沙特国王大学学报使用英特尔FPGA平台优化实现改进的KNN分类算法：Covid-19案例研究Walaa R. Abedalmuhdi AlmomanyAyyad，Amin JarrahYarmouk大学Hijjawi工程技术学院计算机工程系，Irbid 21163，Jordan阿提奇莱因福奥文章历史记录：2022年1月1日收到2022年4月9日修订2022年4月9日接受2022年4月19日网上发售保留字：FPGADCT-KNNHLSHDL开放A B S T R A C T基于类别贡献和特征加权的改进的k-最近邻（KNN）算法（DCT-KNN）是一种高精度的方法。然而，它需要复杂的计算步骤，这消耗了大量的时间用于分类过程。现场可编程门阵列（FPGA）可以用来解决这个缺点。然而，使用传统的硬件描述语言（HDL）来实现基于FPGA的加速器需要很长的设计时间。幸运的是，开放计算语言（OpenCL）的高级并行编程工具，允许快速和有效的设计基于FPGA的硬件加速器。在这项研究中，OpenCL已被用来检查加快DCT-KNN算法的FPGA并行计算平台上，通过应用大量的并行化和优化技术。改进KNN的优化方法可用于各种需要高速分类过程的工程COVID-19疾病的分类是用于检查这项工作的案例实验结果表明，DCT-KNN算法在FPGA平台（采用IntelDe 5a-net Arria-10器件）上的实现与传统的基于单核CPU的实现相比，具有非常高的性能我们的优化设计的FPGA加速器上的执行时间是44倍的速度比常规的基于CPU的计算平台上实现的设计。©2022作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍1.1. 传统的KNN分类器k近邻（KNN）是一种监督机器学习算法，用于分类和回归问题（Guo et al.，2003年）。KNN被应用于多个应用中，例如文本分类（ Chen ， 2018 ） ， 农 业 （ Meivel 和 Maheswari ， 2020 ） ， 医 学（Xing和Bei，2019），金融（Uludag和Gürsoy，2020），面部识别（Sugiharti和Putra，2020），经济预测（Kück和Freitag，2021）和心脏病诊断（Pawlovsky，2018）。KNN通过计算每个未标记数据点与数据集中所有其他点之间的距离来对未标记数据进行分类。然后，通过在数据集中找到模式，将每个未标记的数据点分配给最相同标记的数据类（Ray，2019）。直线距离（也称为欧氏距离）公式是KNN中最常用的距离计算方法。每个测试样品之间的距离x和训练数据点X，其中xi=1;x2;x3：···;x n= 1，X iX1;X;X3：;X n可以使用Eq. （1）（张例如， 2017年）。vutX*通讯作者。dx;X¼1/1 xi-Xið1Þ电 子 邮 件 地 址 ： emomani@yu.edu.jo （ A.Almomany ） ， amin. yu.edu.jo（A.Jarrah）。Almomany，A.，Ayyad，W. R.，&Jarrah，A.（2022年）。使用英特尔FPGA平台优化实现改进的KNN分类算法：Covid-19案例研究。沙特国王大学学报-计算机与信息科学。分类是基于k-最近邻（最小距离）完成的，其中k是多数投票过程中涉及的最近邻的数量（Zhang，2016）。分配给测试样本的类标签根据等式n通过其k-最近邻居的多数票（k中具有最大成员的类）来分类。（2）（杜和李，2019）。C xiarg maxkXj€KNNC.Xj;YK2https://doi.org/10.1016/j.jksuci.2022.04.0061319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comA. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3816。ΣP我P我wix1i-x2iNJ NJ其中xi是一个测试对象，Xj是它在训练集中的k个最近邻居之一，C Xj;YK表示Xj是否属于类别YK。 经典的k-最近邻算法的伪代码在图中给出。1.一、KNN算法具有许多功能，使其成为一个强大的其他分类方法的竞争者。这些包括简单性、可理解性和对噪声数据的鲁棒性。此外，它给出了相对高的性能（Wu等人，2017年）。一般来说，KNN分类器有许多缺点，例如执行时间慢，对大数据集敏感，对参数K值敏感，以及计算步骤高（Lamba和Kumar，2016）。因此，由于这些限制，研究人员已经实施了修改，以提高KNN算法的性能。在文献中已经提出的克服其约束的KNN算法的改进版本是SVM KNN（Zhang等人，2006）、模糊KNN（Keller等人，1985）、KNN与遗传 算 法 （ Suguna 和 Thanushkodi ， 2010 ） 、 KNN 与 K-Means（Buana等人，2012）、权重调整的KNN（Han等人，2001年）及其他。1.2. 基于类别贡献和特征加权的改进KNN（DCT-KNN）基于类别贡献算法的加权KNN（DCT-KNN）是传统KNN的改进版本（Huang等人，2018年）。DCT-KNN通过为检查数据集中的每个特征赋予权重来提高分类精度。为了衡量各特征对分类方程准确性的重要性，（3）可以使用（Huang等人， 2018年）。碟盘1/4-碟盘预压盘3/4样本数量的值和样本到k-最近邻的距离是被考虑用于根据等式找到类别贡献（CT）的因素（6）（Huang等人， 2018年）。CTJ¼k1XdX;YJ 6其中k是最近的邻居，NJ是k个邻域中第j类的样本数，并且是k个邻域中所有样本之间的距离之和。选择CTJ的最小值作为试验样品的最终类别。判别式在Eqn中给出。（7）（Huang等人，2018年）。图2示出了改进的DCT-KNN算法的详细过程。Cx1/4indesof最小值为1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000根据DCT-KNN算法，通过考虑每个特征的权重来计算每个测试点与数据集中所有其他点此外，k邻域中每个类别的样本的总和用于找到每个类别的CT。最后，CT的最小值的索引将被标记为相应的类（类别）。已经注意到，DCT-KN需要复杂的计算步骤。因此，它们消耗更多的时间，特别是在对大数据进行分类的情况1.3. FPGA平台可以利用诸如FPGA、图形处理单元（GPU）和多核的高计算处理平台来减少延迟并提高整体性能（Mittal和Vetter，2015）。FPGA是高速计算平台，其中pret是在5折交叉验证条件下，当参数k为3，5和7时，传统kNN算法的精度和的平均值，Prei是传统KNN算法对数据的相同和，但没有第i个特征。根据DCT-KNN，重要性程度依赖于准确性的差异，其中差异越小，特征越重要。接下来，通过基于等式（1）对i维特征进行归一化来获取对应的权重（wi）（4）（Huang等人，2018），其中n是特征的数量。光盘我可以针对所提出的应用进行定制（Kuon等人，2007年）。FPGA包含通过不同配置连接的逻辑块。这些块提供了可以用于执行不同过程的逻辑门的物理阵列。逻辑块包括简单的门，如AND，OR，NAND，NORXOR和XNOR（Trimberger，2012）。与多核CPU和GPU相比，FPGA提供节能的可编程硬件资源（Abedalmuhdi等人， 2017年）。此外，FPGA具有利用CPU的复杂计算能力和GPU的高速并行计算能力的独特结构（Almomany等人，2020年）。关于我们ni¼1光盘我ð4Þ在Intel FPGA器件中，该结构通常包含自适应逻辑模块（ALM）、RAM块和大量数字信号此外，来自Eq. （4）用于基于等式（5）找到加权欧几里德距离。（5）（Song等人，2019年）。vutX1/1处理（DSP）块。FPGA还可以携带其他类型的模块，例如锁相环（PLL），它可以调整内部时钟频率。ALM包含至少一个查找表（LUT），每个查找表由一个或多个触发器（FF）组成这些ALM在整个FPGA结构中是分散的，使得FPGA非常受欢迎。能够进行时间并行（脉动或流水线）计算，可以应用于垄断SEV中的循环级并发Fig. 1. 经典k-近邻算法的伪代码。地址：广东省广州市天河区ð5ÞA. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3817图二、改进的DCT-KNN算法程序。一般应用。本研究中使用的设备-即英特尔De 5a-net Arria-10，该设备具有足够的资源，可以有效地利用这些资源来合成各种复杂应用程序中的用户目标FPGA具有427，200个用于实现多个硬件电路功能的ALM，1518个DSP块以确保多个浮点运算符的有效实现，以及2713个RAM块以存储用于综合设计的数据。传统的FPGA编程方法是使用硬件描述语言（HDL），如VHDL和Verilog。然而，HDL是一种低级语言，要求程序员对底层硬件架构 有深 入的 了 解（ Grewal ， 2018 ） 。 因此 ， 引入 的高 级合 成（HLS），例如Vivado（Jarrah et al.， 2021）和OpenCL，对于在FPGA上实现拟议的设计变得更加常见，因为它通常抽象了许多硬件细节（Nane，2015）。使用HLS简化了硬件实现，并通过减少和简化整体所需步骤来加快设计过程（Alqudah和Jarrah，2020）。1.4. 开放计算语言（OpenCL）开放计算语言（OpenCL）高级并行编程工具允许在异构并行设备（例如，CPU、GPU和FPGA）（Howes和Munshi，2015年）。OpenCL降低了编程难度、执行时间和异构设备上并行计算的硬件成本。然而，当使用OpenCL时，程序员不需要硬件设计语言（诸如VHDL）的深入知识，因为OpenCL能够综合高级语言规范以产生优化的硬件加速器（Oninda等人， 2019年）。此外，OpenCL提供了功能的可移植性。因此，允许在多个支持的设备上执行代码只需要对主机代码进行一些修改（Munshi，2021年7月1日。）. OpenCL的设计流程，如图所示。 三是包括三个基本阶段。 这些包括仿真阶段、性能调优和执行阶段（Waidyasooriya等人，2018年）。在仿真阶段，代码在CPU上执行以进行代码验证。接下来是性能调优阶段，在此阶段将分析编译报告和配置文件信息，以通过消除性能瓶颈来提高性能。最后，在OpenCL内核代码在FPGA设备上执行的执行阶段评估实际性能（Owaida等人，2011年）。一般来说，使用OpenCL工具对图三. OpenCL的设计流程在这项研究中，我们设计了一个高效的并行实现的DCT-KNN在英特尔FPGA设备上使用OpenCL并行编程语言来加速DCT-KNN算法。这FPGA在电路尺寸方面优于使用硬件描述语言如然而，整体表现彼此接近（Bispo和Cardoso，2017）。优化的基于FPGA的分类实现可以用于许多需要高速分类的分类问题冠状病毒病A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3818利用分类来评估优化实现的有效性。许 多 研 究 已 经 讨 论 了 改 进 DCT-KNN 算 法 或 类 似 方 法 的 过 程（Huang等人，2018; Wang等人，2021年）。然而，这些研究大多集中在改善分类过程的准确性。本文不仅关注COVID-19疾病预过滤数据集分类过程的准确性，还讨论了高速FPGA架构的性能调整过程，以创建高效的硬件设计。本文的贡献可以概括如下：1）引入了并行高级计算语言OpenCL来调整常用的高计算量分类算法的性能，使其能够在高速Intel FPGA技术上运行。从速度和精度两个方面对所设计的硬件进行了效率评估;实验结果表明，在FPGA平台上实现DCT-KNN算法具有极高的加速比性能和较高的精度。2)介绍了一种混合排序方法（MK排序），该方法受益于FPGA计算架构，以改善实现最接近的K个对象到引用查询对象的过程。3)使用OpenCL HLS工具评估使用高性能FPGA器件的性能，并就可能需要增加哪种资源以提高此类应用的整体性能提供建议。本文的其余部分组织如下：第2讨论了许多国家的最先进的有关加速KNN算法。接下来，第3节提供了方法。然后，在第4节中讨论了实验结果最后，第5节提出了结论。2. 相关工作在过去的几十年里，大量关于机器学习分类算法（如KNN分类器）的研究工作已经得到了充分的讨论。然而，大多数研究集中在加速KNN算法在异构计算系统，以及降低功耗和硬件资源的成本本文献综述部分展示了与基于FPGA的KNN算法相关的大量研究，该算法可提高加速性能。简要介绍了每项研究我们的研究是由本节所涵盖的主题推动的。在（Pu等人， 2015），作者使用HLS在FPGA平台上实现KNN内核，以最大限度地减少外部存储器访问的影响。低精度数据表示和基于主成分分析的过滤（PCAF）是使用的两种数据访问减少方法利用 FPGA 的 特 点 ， 提 出 了 一 种 优 化 的 PCAF-KNN （ Memory-efficient PCAF-KNN）算法。然而，MPCAF-KNN方法测试了几个设置，结果表明，该方法优于传统的分类方法的执行时间和功率效率。由于KNN算法是最重要的分类技术之一，作者在（Peng et al.，2016）提出了一种使用OpenCL在FPGA平台上实现时加速KNN的有效方法。FPGA平台具有并行流水线结构等特点。此功能有助于优化KNN算法，通过设计一个特定的气泡排序方法。结果表明，当使用基于冒泡排序算法的KNN时，该实现的速度超过Intel Core i7-3770 k CPU的148倍。相比之下，FPGA的速度（Tang，2016）比Intel Core i7- 3770 k CPU快142倍，利用OpenCL并行编程工具实现了基于KNN的排序算法。此外 ， KNN 在 FPGA 上的 另一 种实 现在 （ Vestias 和 Neto ，2014）中提出。实验结果表明，FPGA比Xeon E5- 2637 V3 CPU快15倍。然而，一些并行平台，如GPU，适合于执行机器学习算法。GPU消耗大量电力，因为需要昂贵的冷却系统来处理热量浪费。另外，在GPU上实现部分算法结构的并行化是一个难点。此外，CPU和 GPU 之 间 的 数 据 传 输 所 消 耗 的 时 间 会 导 致 高 开 销 成 本（Stamoulias和Manolakos，2013）。在（Hussain等人，2012年），在Xilinx Vertex 5 FPGA上实现大数据的KNN分类器比在早期 （ 2008 年 ） GeForce 8800GTX GPU 上 慢 10 倍 。另 一方 面，FPGA实现比GPU实现更节能，后者超过CPU速度100倍。其他研究人员从FPGA中提供的并行化功能中受益，k-近邻分类器对数据库的大小和参数K敏感，参数K是最近邻的数量当数据集很大时，该算法工作缓慢。此外，参数K的值影响性能。因此，研究人员（Liu和Khalid，2018）试图解决这两个问题。因此，提出了两种KNN的FPGA实现，并与通用处理器（GPP）上运行的类似架构进行了比较。第一架构（A1）实现了GPP架构的高达76倍的速度，而第二实现（A2）实现了GPP架构的68倍的速度。在 （ Muslim 等 人 ， 2017 ） ， 英 特 尔 FPGA SDK for OpenCL（IFSO）用于检查KNN算法在FPGA设备上实现时的加速情况。为了提高KNN的性能，使用了双调排序算法。一个旧的CPU实现的性能进行了比较与优化的方法。采用两个FPGA器件实现了优化设计。其中包括Intel Stratix A7和Intel Arria 10 GX。结果表明，两种基于FPGA的加速器的执行时间提高了80倍，功耗降低了83%。在（Theerthagiri等人，2021年）。算法在GPU和FPGA平台上使用OpenCL工具实现。对GPU和FPGA实现进行了不同性能指标的比较。其中包括功耗和执行时间。实验结果表明，FPGA在速度和功耗方面优于GPU.这是因为FPGA受益于OpenCL编程风格，并使用不同的HLS指令。一些研究还讨论了在高速计算FPGA上加速KNN算法的机会在这些研究中，有一项研究侧重于使用等效加速设备（Terrace DE5），并使用OpenCL框架工具（Tang，2016）提出了一种优化的基于KNN FPGA的实现。加速因子高达142;然而，与MATLAB编写的 参 考 软 件 相 比 ， 这 种 加 速 比 可 能 比 C/C++ 编 译 器 慢 十 倍（Andrews，2012; Liu和Khalid，2018）。它还在较低或半时钟频率下消耗更多资源。Liyuan和Khalid还讨论了使用英特尔OpenCL框架（Sinhashthita和Jearanaitanakij，2020）在可比的英特尔FPGA设备上加速KNN，加速因子在50和80次。然而，使用的参考CPU（Xeon E5-2620）比本拟议研究中使用的CPU慢，并且不清楚该软件用作在CPU平台上运行的参考。A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3819在过去两年中，COVID-19疾病由于其对人类的负面影响而成为热门研究趋势，数百万人因感染该病毒而死亡。在（Xiaoming，2014）中，研究了几种分类机器学习算法，其目标是预测可能的感染。利用不同的性能指标来检查不同机器学习算法预测的有效性。结果得出结论，对于所使用的COVID-19数据集，KNN算法在预测准确性、精确度、召回率、均方误差、混淆矩阵和Kappa得分方面在回顾与我们的工作相关的几项研究的最新技术水平时，得出的结论是，研究人员专注于改进KNN分类算法以克服其限制。本研究提出了一种有效的，优化的DCT-KNN算法的实现通过利用FPGA平台的并行化和优化特性，使用OpenCL工具在FPGA器件上实现了该设计，从而加快了执行时间COVID-19数据集用于调查我们优化实现的性能3. 拟议的工作和方法在文献中，有许多改进的KNN方法可以提高分类的准确性，例如（ Xiao 和 Duan ， 2013; xxxx ） 。 然 而 ， 在 （ Huang 等 人 ，2018），与（Xiao和Duan，2013; xxxx）中的方法相比，基于类别贡献和特征加权的改进KNN算法（DCT-KNN）实现了更高的准确性。人们注意到DCT-KNN算法需要复杂的算术运算，因此在分类过程中消耗大量的时间本文利用OpenCL工具对FPGA计算平台进行并行化和优化，加快了改进的DCT-KNN的执行速度该方法的流程图如图1所示。 四、为了对我们的优化实现进行性能验证，使用了COVID-19疾病的预过滤数据集COVID- 19数据集来自著名的网站Kaggle，该网站提供了许多用于数据科学和机器学习研究的公共数据集。所考虑的数据集是根据2020年3月世界卫生组织提供的症状指南综合创建的（Booshehri et al.， 2013年）。该数据集包括COVID-19的常见症状和可能原因。由此产生的结果决定了一个人是否感染了COVID-19。通过数据预处理和数据清洗方法对所研究的数据集进行清洗，从而可以有效地用于我们的分类算法中。然而，DCT-KNN算法用于根据症状将患者分类为健康或患病建议的数据集大小为5430x21，其中数据集中的样本数量为5430，具有21个特征。所有的数据都是数字（ 0和10）。高速接口连接或外围组件快速互连（PCIe）连接目标设备和主机CPU，从而提供在计算单元之间非常快速地传输数据的机会。为了进行性能评估，该算法在单核CPU和英特尔FPGA设备。然后，在基于FPGA的实现中应用不同的优化技术，以达到可接受的分类速度基于CPU的实现的代码是使用C++编写的+语言，而OpenCL并行编程工具用于基于FPGA的实现。然而，OpenCL用于执行的并行模型是一个单一的工作项，也称为任务并行模型。单工作项内核在执行期间只能处理一个工作项然而，外-见图4。 方法流程图。循环迭代的部分是重叠的。在理想的情况下，每个迭代的循环是通过创建一个有效的流水线电路在仅仅一个时钟周期执行 在循环流水线中，计算步骤被划分为多个操作重叠的阶段（并行执行），如图所示。 五、以这种方式，时钟周期的数量减少了两倍。然而，在高数据依赖性的情况下，离线编译器可能无法创建流水线数据路径。因此，它提高了初始化间隔（II）。这实现了两个连续循环迭代之间的周期数（午餐延迟）（理想情况下，II应等于1）或降低时钟频率。因此，系统的性能将下降。在内核代码的编译期间（例如，code.cl），英特尔FPGA编译器会生成多个文件。优化报告文件是这些文件中的一个，包含非常有用的信息，如启动间隔（II），展开信息，流水线信息和瓶颈。通过分析这些信息，我们可以修改所创建的设计，以创建一个更有效的流水线设计，以获得更好的性能。总之，检查优化报告的总体目标是：为所有循环生成高效的流水线数据路径。在开发的内核中，为每个循环实现等于或接近1的启动间隔（II）。在我们的研究中，串行代码在单核CPU中的执行时间约为3.31 min（198.71 s）。在第一步中，在应用任何优化方法（传统设计）之前，修改设计以在Intel FPGA器件（Intel De 5a-net Arria-10）上进行综合。这花费了大约108.249秒，这对于分类来说是很长的时间。根据第一次循环分析报告（优化前），如表1所示，对于某些情况，II接近10●●A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3820图五. FPGA编译器生成流水线数据通路。步骤，因为循环迭代之间的数据依赖性。此外，英特尔FPGA编译器无法为某些循环生成流水线路径，因为循环迭代顺序错误。因此，不同的优化技术已被应用于性能调整。下面列出了我们主要在单工作项内核中使用的性能改进技术，以实现性能调优目标：避免由于数据依赖而导致的串行执行由于读-修改-写操作而忽略循环携带的依赖关系。● 缩短启动间隔（II）。● 使用移位寄存器的概念。● 使用循环展开技术。● 使用循环合并技术。● 使用循环内联技术。3.1. 循环展开技术表1中的报告指出了编译器没有对循环进行流水线处理的问题我们试图通过使用循环展开技术来解决这个问题当循环计算之间不存在数据依赖性时，可以应用循环展开在循环展开技术中，基于循环展开因子N复制HW资源（Davidson和Jinturkar，1995）。然而，循环展开以HW资源为代价增加了每个时钟周期的工作量（Kuznetsov等人， 2012年）。在我们的代码中，循环展开使用了几次不同的展开因子。例如，当在步骤4中计算平均距离时，如如图2所示，使用展开因子2将循环迭代减少到一半。 六、由于循环展开增加了资源利用率和存储带宽，因此需要通过测试仔细考虑展开因子N例如，如果展开因子大，则时钟频率可能由于大的资源利用而降低因此，我们需要在低时钟频率的情况下减小展开因子N此外，循环展开不能实现的情况下，内核不适合FPGA由于大量的资源利用率。3.2. 循环合并技术当有多个顺序循环具有相同的循环边界时，就会发生这种情况执行这些循环会消耗额外的不必要时钟周期并增加开销，这会对性能产生负面影响（Suganuma等人， 2002年）。因此，在这种情况下可以应用循环合并技术。循环合并技术将具有相同边界的相邻循环体合并为一个循环。在我们的代码中，我们重新安排了一些满足循环合并要求的循环结构，使其成为一个大循环。通过这种方式，合并的循环被并发执行因此，循环迭代的数量图7展示了循环合并技术的概念 图7(a)显示每次循环迭代需要一个时钟周期。这包括一个时钟周期进入循环A，四个时钟周期执行循环A，一个时钟周期退出循环A和进入循环B，四个时钟周期执行循环B，最后，一个时钟周期退出循环B。结果，执行两个循环（循环A和循环B）总共需要11个时钟周期。图7（b）示出了在将循环A和B合并成一个大循环之后如何减少表1图3中步骤3、4和5的回路分析报告。 2优化前。●●A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3821见图6。 使用图2中的步骤4的循环展开技术来减少时钟周期的数量。见图7。 循环合并技术。3.3. 函数内联技术内联技术是一种在编译后的源代码运行时通过用源代码的主体代码替换调用函数来优化源代码的方法。这有助于减少函数调用的开销（Qian andHenrique，2005）。当调用内联函数时，内联函数的整个代码将在内联函数调用点插入或替换。该插入由编译器在编译时实现（Hill等人，2015年）。在我们的代码中，加权欧氏距离函数（图2中的步骤3）被替换为在编译期间调用时，它的主体的副本版本，如图8所示。因此，减少了函数的调用开销。3.4. 移位寄存器技术创建具有接近或等于1的II的有效流水线电路是一个挑战。然而，移位寄存器的概念可以用来创建一个完美的流水线结构，其中程序员试图删除所有数据依赖性。通过这种方式，离线编译器可以创建一个深度管道，II接近1.然而，移位寄存器阵列是通过展开循环来创建的，使得寄存器阵列的数据可以被并行访问。因此，整个系统的性能将得到改善。根据表1所示的先前环路分析报告，图2中步骤3（计算加权距离）的II接近7。因此，下一次循环迭代需要在前一次迭代完成其执行之前等待7个时钟周期，如见图9。这是因为变量s的数据依赖性，如图10（a）所示。因此，如图10（b）所示，使用移位寄存器概念来解决这个问题。我们创建移位寄存器阵列（Huang等人，2018），其中数据在局部变量中累积。然后，通过完全展开循环，使用单个时钟周期将所有值的总和存储在不同的外部变量（sm）中。以这种方式，离线编译器可以生成深度流水线数据路径，其中II等于1。3.5. 忽略由于读-修改-写操作而导致的循环携带的依赖关系当下一次循环迭代不需要将前一次循环迭代的更新数据送入时，则下一次循环迭代不需要等待前一次迭代将其数据写入全局存储器（无数据依赖性）。在这种情况下，可以使用#pragma ivdep指令来指示编译器忽略由于全局内存更新引起的数据依赖性。然后，离线编译器可以优化循环。总之，通过使用优化技术，成功地加快了DCT-KNN算法的执行时间实验结果将在下一章中讨论。3.6. 距离向量与排序技术距离计算是完全并行的，因为在执行查询实体和引用实体之间的距离计算时不存在引入的依赖性。几个距离A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3822见图8。图3中步骤3的内联技术。二、图9.第九条。利用移位寄存器的概念降低了I值在每个时钟周期计算，因为通过使用循环展开技术，函数单元的数量被复制若干次，并且移位寄存器技术被用于解决所创建的流水线电路中的依赖性，并且增加工作时钟频率。在获得距离矢量之后，下一阶段是对距离向量中的这些距离进行排序，以定位新的未标记数据点周围的所有最近邻居，从而预测它属于什么类。为了提高性能和减少存储器访问时间，整个距离矢量存储在快速访问本地存储器中。由于传统冒泡排序的成本使性能显著降低，甚至比传统通用计算单元的执行时间更差，因此根据下面图11中所示的描述修改排序函数新采用的排序算法称为MK排序，其中距离向量范围被划分为M个子向量。所有子向量使用奇偶排序算法并行排序，其中每个子向量由单独的线程处理;使用奇偶排序技术可以创建一个有效的流水线结构，初始间隔为1，如相关研究所证明的那样排序的下一阶段是从每个子向量中选择最小的K个元素，并将它们组合以生成一个大小为MxK个元素的最后，因为我们需要K个最小距离，所以对小的新数组进行排序，然后获取最小的K个距离我们还需要提到，所有讨论的技术都是一起工作以创建所提出的有效设计来运行DCT_KNN算法。总之，我们可以强调这些事实：i. 将最慢的冒泡排序修改为新的并行MK排序技术，提高了显著的加速比（超过50倍）。图10个。图3步骤3中移位寄存器概念的使用。 二、A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3823见图11。 距离向量的并行排序技术使用MK排序包含N个ii. 通过使用局部存储器和移位寄存器来解决和减少相关性，提高了时钟频率，减少了存储器访问时间，提高了数倍的iii. 循环展开技术通过创建许多逻辑和算术函数并在仅仅一个时钟周期内执行几个复杂的操作来增加每个时钟周期的工作量这将整体加速比提高了十倍以上。4. 实验结果与讨论在这项研究中，使用预过滤的COVID-19数据集来研究我们提出的方法的性能。所考虑的数据集是根据2020年3月世界卫生组织提供的症状指南综合创建的（Booshehri et al.，2013年）。如图12所示，该数据集包括常见的COVID-19症状、慢性疾病和导致COVID-19感染的日常生活活动。KNN算法使用图12所示的数据作为输入来进行预测。通过搜索整个训练集的k-最近邻，对每个新的测试样本进行预测。所得分类结果根据输入值确定该人是否患有COVID- 19。分类结果如图13所示。正确和错误预测的百分比如图14所示。正确预测的数量是5311，而错误预测的数量是119。因此，实现的分类准确率为97.8%。为了总结算法的预测结果，混淆矩阵在图15中提供。该测试集有4333个真阳性，978个真阴性，70个假阴性，49个假阳性，准确率为97.8%。DCT-KNN算法的性能评估是在单核CPU和FPGA加速器中实现时的一致性。CPU采用Intel Corei7-6700@3.4 GHz，16 GB的内存用于运行串行代码。具有O3标准优化级别的GNU编译器集合（GCC/G++）用于编译。使用Intel De 5a-net Arria-10器件实现优化的并行代码。表2给出了执行时间和时钟频率方面的性能指标。串行代码在CPU上的执行时间比优化前在FPGA上实现相同代码（FPGA上的传统设计）快16倍。比较优化前在FPGA上实现par-code.par的执行时间（在FPGA上进行常规设计）与优化后的执行时间，发现时间慢了700倍。其原因是由于循环之间的高数据依赖性，离线编译器无法生成流水线数据路径。因此，如前一节所述，许多优化方法被应用于加速系统作为优化的结果，整个系统的速度提高了45倍，因为我们实现了相同的分类精度的串行代码（97.8%）。此外，在优化设计时应考虑频率，因为它可能会在某些点上降低。因此，我们应该妥协的设计，以获得一个可接受的更高的频率。以这种方式，每个时钟周期可以执行增加的工作量（指令数）。 因此，提高了整体系统性能。所提出的设计是运行在英特尔De 5a-net FPGA器件在255.5 MHz的时钟频率。系统的面积分析报告显示了估计面积利用率的值。这些资源包括自适应循环表（UART）、触发器（FF）、RAM存储器块和DSP块。优化前后的资源利用率比较如表3所示。优化后，可再生能源利用率提高了71%，而可再生能源利用率提高了19%。此外，RAM的使用量增加了112%，而DSP的使用量也增加了91%。因此，我们可以得出结论，优化系统会增加资源A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3824见图12。 COVID-19数据集分析。图十三. DCT-KNN分类结果。使用.因此，延迟和设计复杂度可能增加。因此，我们需要折衷整体系统性能。此外，需要注意的是，在使用基于FPGA的OpenCL时会预留一些资源，如表4所示。这被认为是使用OpenCL时的资源使用开销。相反，使用VHDL或Verilog语言时，所有资源都是免费的。另一个可以用来比较我们系统性能的指标是时间复杂度。时间复杂度是用来估计算法在速度方面的性能。时间复杂度的一般定义是度量算法执行每行代码所消耗的时间，作为输入大小的函数。在我们的研究中，大O符号被用来计算算法的复杂度，其运行时间的基础上，随着输入n的大小增加。O是增长率函数，而n是输入的长度在应用不同的优化技术（如循环展开和移位寄存器技术）后，某些步骤的时间复杂度降低，如表5所示。在DCT-KNN算法的运行时间期间，欧几里得距离函数被调用N次以计算训练数据集中每个数据点与所有其他点这会产生很高的调用开销，因此，一个大的exaculation-灰时间。优化前的DCT-KNN算法中欧氏距离的时间复杂度为O（N2），其中N为训练集的大小。优化后的算法消除了数据依赖性，复杂度降低到O（N）。时间复杂度为O（N2）。这是在应用循环展开技术之后，其中内部循环迭代在相同的时钟周期执行，这意味着时间复杂度降低到O（N）。时间复杂度为O（N），时间复杂度为O（N）。A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报3825见图14。 DCT-KKN分类的准确性。表4FPGA中保留资源的数量和百分比资源保留资源保留百分比（%）BMPs40,6509FFS52,9766RAM块28311表5DCT-KNN算法的时间复杂度。优化前的工艺复杂性优化后的复杂性图十五岁DCT-KNN算法的混淆矩阵计算欧氏距离O（N2）O（N）时间复杂度O（N）表2在CPU和FPGA上实现设计的性能指标。寻找类贡献（CT）时间复杂度O（1）性能度量CPU的常规设计基于FPGA的常规设计FPGA优化设计执行时间CLK频率（MHZ）3400 207.5 255.5利用移位寄存器的概念消除数据相关性，并采用循环展开技术，使该步的速度提高到O（1）。总之，计算优化前后的DCT-KNN算法的时间复杂度证明了使用FPGA加速器来加快所提出的系统执行时间的可行性，这是我们在这项研究中的主要动机表6中介绍了不同性能测量结果的总结，这些性能测量结果证实了使用FPGA加速器加速繁重计算的DCT-KNN算法的有效性。当比较我们的表6使用英特尔De 5a-net Arria-10实施时的性能比较。性能传统设计的优化设计参数FPGAFPGA执行时间3108.2494.45CLK频率（MHZ）207.5255.5BMPs80,441121,573FFS63,201125,035RAM块1,3931,807优化设计与（Vestias和Neto，2014）中的相关工作相比，我们的优化设计超过了（Vestias和Neto，2014）中提出的设计3倍，其中（Vestias和Neto，2014）中实现的速度提高了15倍。表3英特尔De 5a-net Arria-10资源利用率。资源系统优化系统优化资源利用利用率%资源利用利用率%BMPs121,5731080,4416FFS125,035563,2013公羊1,807731,39334DSPs153,5579.53A. Almomany，W.R.Ayyad和A.Jarrah沙特国王大学学报38265. 结论本文提出了一种优化的性能调整方法，以确认使用FPGA加速器技术来加速计算复杂的DCT-KNN算法的