● 摘要
优化算法经历了从传统的经典最优化方法到现代的智能优化算法的发展过程。对求解复杂的优化问题，传统的优化算法不再胜任，而通常采用智能优化算法进行求解。20世纪中期以来，多核处理器、GPU以及计算机集群的发展，极大地推进了优化算法并行加速技术的研究。同时，随着电子科技的发展，FPGA技术得到了广泛的应用，而由于FPGA硬件结构具有高度的并行性，为优化算法的并行研究提供了一种新的设计方式。
目前的智能优化算法主要是采用软件编程的方式在CPU和GPU中运行，而无论采用串行还是并行的编程方式，其运行速度都受限于既有处理器的硬件架构。那么能否设计一种并行执行优化算法的专用硬件结构？而又如何设计这样的硬件结构，最终达到提高优化算法求解效率的目标。基于以上问题，本文围绕“基于FPGA的优化算法并行实现与应用研究”对以下内容进行了研究。
一、构建智能优化算法库，对基本智能优化算法串行实现的原理以及运行机制进行分析，在此基础上进一步对优化算法的并行实现方法加以研究。本文主要研究两种典型并行实现方法：基于多核处理器的OpenMP并行编程方法以及基于GPU的CUDA并行编程方法。通过对这两种并行实现方法的研究，深入探索优化算法的并行设计方法，为采用FPGA设计并行执行优化算法的专用硬件结构做好铺垫。
二、提出基于FPGA的优化算法并行设计方法，在所提出设计方法的基础上，结合Virtex-5系列FPGA芯片的特点，设计基于FPGA的求解函数优化问题的并行粒子群算法和基于FPGA的求解组合优化问题的并行遗传算法。在Xilinx的ISE开发环境中完成优化算法设计，通过Modelsim进行仿真，并在开发板中运行测试。
三、开发串并行优化算法软硬件一体化验证系统，该系统平台集成串行优化算法库、基于多核处理器的OpenMP并行算法程序以及基于GPU的CUDA并行算法程序，同时集成基于FPGA的并行优化算法硬件仿真结果数据。在该系统平台中，能够对各种设计方法得到的结果进行对比，以图形与数据两种形式展现运算过程，分析算法性能。
四、理论分析对比与应用验证。根据所开发的验证系统，对CPU和GPU中的串并行优化算法与基于FPGA的并行优化算法在求解函数优化问题和组合优化问题方面进行对比，从理论上加以分析，总结基于FPGA设计并行优化算法的优势与不足。并进一步对车间调度实际应用问题采用基于FPGA的模拟退火算法予以求解，最终验证本文设计方法。
根据以上四个方面的研究，本文构建了基本的智能优化算法库，探索了基于多核处理器的OpenMP并行编程方法以及基于GPU的CUDA并行编程方法，提出了基于FPGA的优化算法并行设计方法，开发了串并行优化算法软硬件一体化验证系统，并从求解函数优化问题、组合优化问题以及实际应用问题等方面对本文所提出设计方法进行了对比分析与验证。验证结果表明，基于FPGA的优化算法并行设计方法较大地提高优化算法的运行效率。