近年来,随着大数据、云计算以及人工智能等相关领域研究和应用的不断深入,导致需要计算的数据体量急剧增长。诸如数据库、智能算法、深度学习、在线预测以及无人驾驶等各种计算密集型应用对计算能力的需求已远远超出了传统通用处理器(CPU)的处理能力。从上个世纪60年代开始,人们就对可并行的计算问题提出了用并行计算(Parallel Computating)的方法来对算法进行加速,以实现更高的计算性能,从而提升解决问题的效率。伴随着CPU处理能力和相关技术的不断迭代,并行计算系统的计算能力不断提升。然而,近几年半导体技术几乎达到了物理极限,摩尔定律几近失效,但数据量的增长对计算能力的要求却仍在不断提升。进入21世纪,人们开始探索用异构计算(Heterogeneous Computation)等新的计算形态来提升计算能力。FPGA是一种可编程芯片,它将算法逻辑直接翻译为晶体管电路的组合,在计算速度、延时和功耗等方面优于通用处理器。因而,其在众多应用场景中有着重要地位,并成为异构计算领域的研究热点。然而,FPGA的硬件架构虽然为其带来了很高的计算性能,但却使基于FPGA的算法设计方法面临挑战:(1)基于FPGA的算法设计是面向电路结构的,这需要设计者深入了解FPGA结构和数字电路。目前的算法开发人员大部分是软件人员,缺乏对硬件的了解,且基于FPGA的算法设计工具链不够完善,导致FPGA平台上的实际开发效率较低。(2)现有算法设计和性能优化方法多是针对通用处理器架构的,由于FPGA与通用处理器在硬件架构上的差异,使得这些方法不能充分发挥FPGA的特性,从而不能在FPGA上获得较好的算法性能提升效果。目前仍然缺少适合FPGA的算法设计及性能优化方法。(3)在FPGA上实现具体算法时,需要结合FPGA硬件架构特点针对算法特征对算法实现进行深度优化。现有优化思路多是从算法模型角度出发的,缺少对算法要解决的问题和FPGA的硬件架构的考虑。基于以上问题,本文主张通过提出适合于FPGA硬件架构的算法设计和性能优化方法来提升算法在FPGA上实现的性能,主要工作介绍如下:(1)提出了基于FPGA的高性能算法实现设计模式和计算性能评价标准。在FPGA上,算法的控制逻辑和运算操作被转化为电路逻辑单元的连接,待操作的数据则按照电路的连接方式流过FPGA,产生最终的运算结果。电路的组合方式影响数据的流动方式,并最终影响计算性能。因此,针对FPGA上的算法实现的性能优化应该以构造高效的数据流为目标。本文提出以构造算法的流式数据为目标的算法实现设计模式,通过将高效的电路模型抽象为算法实现的数据流模型,为设计者屏蔽硬件结构细节,提升开发效率。设计者只要参照设计模式进行算法实现就更容易提升算法在FPGA上实现的性能。另外,设计模式只是一种设计参考,不需要特定的编程语言或者综合工具的支持,具有很强的通用性。本文提出的设计模式分为三个层面:在算法整体框架层面,以构造流式数据为目标,包括多级流水“映射-归并”框架和脉动式线性框架;在算法功能级层面,针对典型的算法结构,包括复杂数据类型高效流水求和树和并行比较向量;在算法逻辑层面,包括多种以简化控制逻辑和降低运算强度为目标的性能提升方法。此外,对FPGA上的算法实现的性能评价不能单纯以程序执行时间为标准,要兼顾延时、频率、吞吐量、芯片利用率和功耗等多个方面。因此,本文提出了针对FPGA上算法实现的相关性能评价方法,包括加速比评价方法和针对HLS(High Level Synthesis)方法的综合结果性能评价方程。本文所提出的设计模式和性能评价标准对提升FPGA上的算法实现的性能有重要意义。(2)提出了一种针对FPGA结构的基于扩展非严格偏序序列的线性排序算法,并将其在FPGA上应用脉动式线性框架设计模式实现为可配置线性排序器。排序问题是一个被广泛研究的算法问题。现有FPGA上的排序算法实现多为将经典排序算法通过并行化设计后移植到FPGA上,虽然降低了排序延时,但在资源占用率等方面的性能有待提升。本文针对FPGA的结构特点,首先基于数学中的序理论,将非严格偏序关系扩展为基于n元组的非严格偏序关系,并在此基础之上提出了线性排序算法。该算法具有4N/n时间复杂度,可以通过调整n的值来调整算法的带宽和比较操作的数量。基于该算法在FPGA上实现的排序器具有资源占用率相对较低,电路连接复杂度不高,输入带宽、排序延时等参数可配置等特点。从而可以根据具体排序问题的需要在延时和资源占用率等性能之间做出权衡,提升FPGA上解决排序问题的总体性能。由于该算法是针对FPGA硬件架构进行设计的,因此,本文使用绝对加速比来评价算法的性能。实验结果表明,该算法相比在CPU上实现的快速排序算法有更好的计算效率。(3)提出了基于HLS的群智能算法实现通用框架。群智能算法(Swam Intelligence Algorithms,SIAs)主要用于解决优化问题,属于计算密集型算法。现有计算性能优化工作一般仅从提升群智能算法的空间并行性角度出发。这会导致FPGA实现的吞吐量不高和求解规模有限。本文提出的框架应用多级流水“映射-归并”框架设计模式,并充分考虑硬件平台的存储器架构,将算法数据流与硬件结构相匹配,从而进一步提升算法实现的并行特性和吞吐量。框架基于HLS,使用C++语言进行描述,可以部署在不同硬件平台(FPGA,GPU和Multi-core CPU)上。在具体实现时,本文针对每种平台硬件架构特点对框架进行了深度优化,以提升存储器的访问效率,并以量子行为粒子群优化算法(Quantum Behaved Particle Swam Optimization,QPSO)为例对框架进行测试。在性能评价上,使用相对加速比方法,将框架在不同平台上的计算性能进行对比。实验结果表明框架实现了比现有工作更优的性能,并且,在FPGA的实现具有比其他平台上实现更好的计算效率。