提出新型硬件优化的随机模拟退火算法，大幅降低FPGA内存占用并提速超百倍。
Memory-Efficient FPGA Implementation of Stochastic Simulated Annealing
- 设计硬件感知的随机模拟退火算法，减少中间结果存储需求。
- 在G-set数据集上比传统算法快114倍，内存效率提升6倍。
- 适合需要高速低内存的组合优化硬件部署场景。
模拟退火（SA）是求解组合优化问题的经典算法，但随着问题规模增大，计算时间迅速增加。近期提出的随机模拟退火（SSA）算法收敛速度更快。本文提出一种面向硬件的SSA（HA-SSA）算法，实现内存高效的FPGA部署。该算法在保持SSA计算速度的同时，显著减少中间结果存储需求。在最大割问题（G-set数据集）上的实验表明，HA-SSA相比传统SA算法最快可提速114倍。在Xilinx Kintex-7 FPGA上实现，相比传统SSA内存效率提升最高达6倍，同时保持优化解的质量。
原文摘要 · Abstract (English)
Simulated annealing (SA) is a well-known algorithm for solving combinatorial optimization problems. However, the computation time of SA increases rapidly, as the size of the problem grows. Recently, a stochastic simulated annealing (SSA) algorithm that converges faster than conventional SA has been reported. In this paper, we present a hardware-aware SSA (HA- SSA) algorithm for memory-efficient FPGA implementations. HA-SSA can reduce the memory usage of storing intermediate results while maintaining the computing speed of SSA. For evaluation purposes, the proposed algorithm is compared with the conventional SSA and SA approaches on maximum cut combinatorial optimization problems. HA-SSA achieves a convergence speed that is up to 114-times faster than that of the conventional SA algorithm depending on the maximum cut problem selected from the G-set which is a dataset of the maximum cut problems. HA-SSA is implemented on a field-programmable gate array (FPGA) (Xilinx Kintex-7), and it achieves up to 6-times the memory efficiency of conventional SSA while maintaining high solution quality for optimization problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。