文|娱栀
编辑|娱栀
前言
群体智能算法（SIA）在解决优化问题与实际问题时表现出优异的性能，但对于某些复杂问题而言，SIA的计算成本很高，因此需要有效地加速SIA以获得更好的性能。
此次提出了一个加速SIA（FASI）的高性能通用框架，这与之前仅通过增强并行化来加速SIA的工作不同，FASI既考虑了硬件平台的内存架构，又考虑了SIA的数据流，并将SIA的框架重新调度为融合数据流，以提高内存访问效率。
FASI通过将算法框架与硬件架构相匹配，实现了更高的加速能力，并特定硬件平台的特性设计了FASI并行化和收敛的深度优化结构。
以量子行为粒子群优化算法为例来评估FASI，结果显示，FASI通过优化硬件实现提高了SIA的吞吐量并提供了更好的性能。
在实验中，FASI实现了最大290.7Mb/s的吞吐量，并高于几个现有系统，FPGA上的FASI实现了比GPU和多核CPU更好的加速。
SI的介绍
群体智能（SI），源于去中心化和自组织系统的集体行为，典型的SI系统由一群遵循非常简单规则并通过作用于当地环境来相互交互的个体组成。
这些个体之间的相互作用可能导致非常复杂的全球行为的出现，远远超出单个个体的能力，自然SI系统中的例子包括鸟群，蚂蚁觅食和鱼群等。
受自然群体智能的启发，人们已经提出了一系列用于优化问题的算法，例如粒子群优化（PSO），蚁群优化（ACO）。
PSO的灵感来自鸟群或鱼群的社会行为，并广泛用于实参数优化，ACO模拟蚁群的觅食行为，已成功应用于解决各种组合优化问题。
通常，SI算法（SIA）包括三个阶段：（1）分别更新个体;（2）个人的体能评价，（3）所有个人之间的沟通，以实现全球信息共享，这些阶段将迭代多次，直到满足终止条件。
尽管SIA在解决许多传统算术和数值方法表现不佳的实际问题方面取得了不同程度的成功，例如无线传感器网络中的路由设计和路径规划，但它们存在耗时的适应性评估过程导致的密集计算的缺点，这极大地限制了它们的应用。
但其实已经付出了很多努力来提高SIA的性能，基于群体内的相互作用，SIA自然适合并行化。
SIA的这种固有特性使其非常适合部署在具有并行计算能力的硬件平台上，例如多核CPU，图形处理单元（GPU）和现场可编程门阵列（FPGA）。
但是，如果只关注并行化的特性，而没有对硬件平台的属性给予足够的关注，那么性能将没有足够的改进。
除了并行化之外，SIA还具有由所有个体之间的相互作用决定的收敛特征，交互应通过每个个体与唯一具有最佳适应度值的个体之间的比较操作来实现。
如果不能根据特定的硬件平台考虑内存访问效率来组织好比较，则当群体规模较大时，可能会出现内存访问瓶颈和吞吐量限制，从而使算法的性能显著降低。
为了进一步优化SIA的并行化和收敛性能，人们提出了一个在FPGA、GPU和多核CPU上加速SIA（FASI）的通用框架，FASI提供了由C++语言实现的统一框架，可以部署在不同的硬件平台上。
FPGA上的FASI比其他硬件平台达到更高的加速，与多核CPU相比，FPGA在基准功能球体上最高加速123倍，与GPU相比，FPGA在基准函数SchwefelP9.2上达到了最高22倍的加速。
相关工作
加速SIA已被用于解决许多问题，可尽管已经做出了很大努力，但关于加速补充免疫活动的研究仍处于起步和上升阶段，特别好的和令人信服的绩效标准还有待提出。
由于密集计算的特点，加速SIA的直接方法是投入更多的计算单元，特别是更多的硬件内核来构建并行计算环境。
FPGA被认为是并行实现SIA的候选硬件平台之一，可以通过其可定制的硬件结构来加速算法，FPGA不仅提供定制的并行结构，还提供灵活的流水线。
提供的乘数专用于矩阵乘法，在应用于SIA时需要对其进行重大修改，还可以使用FPGA实现的吞吐量来评估加速性能。
关于通过FPGA加速SIA的探索很多，其中最重要的是提出了一种针对QPSO的微架构，QPSO的维度更新部分具有明显的并行化特征，通过并行化计算单元加速，而适应度评估部分仍然是串行的。
与ARM平台相比，这项工作仅实现了加速，而另一项工作更是加速了FPGA上改进的ACO，并将其应用于路径规划，路径规划也由并行维度更新和串行适应度评估组成。
为了更好地利用硬件资源，人们又所提出的PSO加速器将适应度评估功能打包在一个SP模块中，该模块仅计算粒子的适应度值，并由并联群单元模块共享。
由于基准功能的复杂性，适应度评估需要花费更多的FPGA资源，因此共享适应度评估功能模块提供了一种提高并行化程度的经济方法。
当FPGA芯片上的硬件资源有限时，上部加速策略表现良好，考虑到适应度评估消耗了大部分操作资源和时间，又提出了一种硬件/软件协同设计加速器。
加速器在异构架构上实现，算法分为两部分：基准测试功能通过CPU内核中的软件设计以及左侧部分在PFGA中并行部署。
当基准函数发生变化时，这种加速策略是灵活的，并且它可以节省更多的硬件资源，提高并行化程度，然而基准函数和粒子更新之间的通信成为新的性能瓶颈。
为了实现SIA的完全并行化，只好在PSO的完全并行加速器在单个FPGA芯片上开发，每个粒子都有自己的位置更新单元和适应度评估单元。
除全局信息共享外，所有粒子均同时运行，然而，加速器仍然没有达到良好的加速比，主要是因为它们遵循了PSO的原始数据流。
由于群体规模的大小可能会增加，因此制定了多群体策略，粒子被划分为子群，所有子群自行完成迭代过程。
有一个通信控制器，当它收到更好的全局最佳位置请求时，最佳位置将通过通信结构同步到所有其他子群。
此外，在多个FPGA上也实现了并行遗传算法（GA），它们都只是将并行编程模块迁移到FPGA平台，并专注于设备之间的通信，而没有充分考虑FPGA的特性，尤其是可定制的流水线。
GPU是用于并行实现SIA的另一种硬件平台，与FPGA相比，GPU具有更多的RAM，可以加速更大数据规模的SIA。
CUDA架构中的PSO实现，旨在加快处理大量数据的问题的算法，GPU的每个处理核心负责整体处理操作的一部分，并且可以充分利用GPU的并行化能力。
GPU上实现了一组生物启发优化方法（PSO），遗传算法（GA），模拟退火（SA）和模式搜索，这可以成为在GPU上实现SIA的良好指标。但是，没有给出实现细节。
除了以上的算法外，在不同的硬件平台上实现相同的算法并比较实现的性能将为更好地加速算法提供良好的见解。
马尔可夫链蒙特卡洛（MCMC）被实施并进行了深度优化，以便在多核CPU，GPU和FPGA上获得更好的性能，实验结果为如何选择加速平台提供了很好的参考。
在多核CPU、GPU和FPGA上实现了三点维特比译码算法，并讨论了解码吞吐量、编程成本和价格成本等性能。
这两项工作分别加速了每个硬件平台上的算法，较少讨论在不同硬件平台上构建算法的统一并行模块。
FPGA、GPU和多核CPU的特性和编程模型
FPGA接口
FPGA是现场可编程门阵列的缩写，是一种集成电路（IC），制造后可以在现场编程，它根据程序连接，由于这种灵活的硬件架构，FPGA几乎没有总线带宽限制，它提供了门级并行化和深度可改变的流水线。
经典的FPGA芯片由控制逻辑块（CLB）组成，CLB是基本功能单元，负载均衡由触发器和LUT组成，其中触发器负责存储，LUT主要用于算术。
考虑到应用对存储和算术的更高要求，制造商在FPGA中集成了硬核以满足这些需求和更高的集成度，例如用于存储的BRAM和用于算术的DSP。
然而，管理如此丰富的资源并不是一项艰巨的任务，功能模块总是用硬件描述语言（HDL）描述，例如VHDL和Verilog，它们设计用于电路描述，而不是逻辑描述。
程序员必须将算术逻辑转移到电阻晶体管逻辑，这对于使用高级语言的程序员来说具有挑战性。
图形处理器
GPU最近作为通用计算设备变得流行，因为它具有大规模并行架构，并像开发环境提供了改进的可访问性。
GPU由多个相同的计算单元实例组成，称为流多处理器（SM），SM是并行执行一组线程（称为线程块）的计算单元。
每个SM都有一个（或多个）单元来获取指令，多个ALU（即流处理器或CUDA内核）用于并行执行，SM中的所有线程都可以访问的共享内存，以及包含每个硬件线程的专用寄存器集的大型寄存器文件。
线程块的每个线程都在ALU上处理，由于ALU被分组为共享单个指令单元，因此映射到这些ALU上的线程在每个周期中执行相同的指令，但数据不同。
共享相同指令的每个逻辑线程组称为warp，此外，属于不同warps的线程可以在相同的ALU上执行不同的指令，它们虽在不同的时隙中，实际上，ALU在经线之间是分时的。
CUDA提供了一个可访问的编译器和一个具有熟悉的类C结构的API扩展，在CUDA的编程模型中，GPU上的任务是一个网格，其中包含块。
每个线程都有专用本地内存，每个块都有共享内存，对块的所有线程可见，并且与块具有相同的生存期，所有线程都必须访问相同的全局内存。
纹理内存和常量内存是只读的，它们被缓存以便快速访问，不同的内存在带宽上是完全不同的。
本地内存和全局内存是通过GDDR5连接到GPU的片外DRAM，共享内存本质上是容量有限的可编程片上一级高速缓存块。
讨论和结论
FASI是基于算法统一数据流的SIA通用加速框架，大多数SIA具有相同的更新和适应性评估进度，但通信模式不同，FASI将这三个阶段分成专用模块，以便进一步优化。
硬件平台的繁重数据传输和分层内存架构，通信将成为并行化SIA的吞吐量瓶颈，FASI重新调度SIA的数据流，以减少不同内存层次结构之间的数据传输，从而提高整体吞吐量。
由于FPAG的分布式内存架构和定制的深度可变流水线，FPGA上的FASI可实现更好的吞吐量。
FASI的另一个改进是FASI不会同时并行化所有粒子，而是通过考虑处理器的并行内核数量和内存访问的效率将并行粒子分成几组，在并行化和内存带宽之间可能需要权衡;算法的更好加速应该实现更大的整体吞吐量。
参考文献：
基于 GPU 的群体智能算法实现调查，IEEE Trans. Cybern，第 46 卷，第 9 期，2016 年 。
定义粒子群优化的标准，IEEE Swarm Intell. Symp，第 120-127 页，2007 年。
移动自组网中基于群体智能的路由算法综述，第 1-7 页，2017 年。
如果你也喜欢我的文章，不妨点个“关注”吧！小生在此谢过了！
END