1. 项目概述FPGA实现的离散模拟分岔算法架构在资源分配、物流调度等实际场景中组合优化问题Combinatorial Optimization, CO的求解往往面临NP难问题的指数级复杂度挑战。传统CPU在处理这类问题时随着问题规模扩大计算时间会呈爆炸式增长。这就像要在所有可能的路线中找到最短路径当城市数量超过30个时传统计算机可能需要数年才能完成计算。模拟分岔机器Simulated Bifurcation Machines, SBMs作为一种新型硬件加速器通过模拟非线性参量振荡器网络的分岔现象为组合优化问题提供了高效的解决方案。其核心优势在于算法的高度并行性特别适合FPGA等可编程硬件实现。离散模拟分岔discrete Simulated Bifurcation, dSB算法作为最新变体通过离散化处理进一步减少了模拟误差同时保持了良好的硬件友好性。我们开发的这个开源硬件架构采用SystemVerilog语言描述主要特点包括支持dSB算法及其加热机制变体三级并行化设计矩阵运算的行/列并行及模块复制可配置的并行度参数Pc/Pr/Pb固定点数表示法优化资源利用兼容max-cut和背包问题等通用伊辛模型在AMD Kria KV260这款入门级FPGA上我们成功实现了256变量规模的实时求解。这个开发板虽然属于低端型号搭载Zynq UltraScale MPSoC但通过架构优化其性能已能满足许多实际应用需求。提示选择dSB算法而非aSB或bSB变体主要基于三点考量1) 离散化处理消除了模拟误差2) 省去了乘法器资源直接使用符号位3) 与加热机制兼容。这使得在同等硬件资源下可以实现更高程度的并行化。2. 技术背景与算法原理2.1 伊辛模型与组合优化伊辛模型最初用于描述磁性材料中的自旋相互作用其哈密顿量表示为$$ H(s) -\frac{1}{2}\sum_{i1}^N\sum_{j1}^N J_{ij}s_is_j - B\sum_{i1}^N h_i s_i $$其中$s_i \in {-1, 1}$ 表示第i个自旋状态$J_{ij}$ 为自旋间相互作用矩阵$h_i$ 为外部磁场影响这个模型与组合优化中的二次无约束二进制优化QUBO问题等价两者可通过简单线性变换相互转换。例如在max-cut问题中将图节点划分为两个子集的操作正好对应自旋的±1状态。2.2 模拟分岔算法演进模拟分岔算法的发展经历了三个阶段绝热模拟分岔aSB模拟非线性Kerr振荡器的绝热演化过程通过缓慢增加泵浦信号$a(t)$使系统发生分岔。其哈密顿量包含四次项 $$ H_{SB} \sum_{i1}^{n_{spin}} \left[ \frac{\Delta}{2}y_i^2 \frac{K}{4}x_i^4 \frac{\Delta-a(t)}{2}x_i^2 \right] - \frac{c_0}{2}\sum_{i1}^{n_{spin}}\sum_{j1}^{n_{spin}} J_{ij}x_i x_j $$弹道模拟分岔bSB引入$x_i\pm1$处的完全非弹性墙消除四次项的同时减少模拟误差。当振荡器位置超出±1范围时强制将其设置为最近的边界值。离散模拟分岔dSB在bSB基础上进一步离散化用符号函数替代位置变量 $$ f_i \sum_{j1}^{n_{spin}} J_{ij} \cdot \text{sgn}(x_j) $$ 这种处理虽然违反能量守恒但能有效逃离局部极小值。图1展示了三种算法在2节点max-cut问题中的轨迹差异。可以看到dSB的离散特性使其能快速收敛到最优解附近。2.3 加热机制与参数选择加热机制通过在动量更新中加入随机扰动项$\gamma y_i(t_n)\Delta t$帮助系统跳出局部最优。这类似于模拟退火中的温度参数但实现成本更低。关键参数的选择策略$c_0$根据J矩阵的最大特征值$\lambda_{MAX}$设定通常取$c_0 \Delta/\lambda_{MAX}$$\Delta t$dSB建议取1.0bSB取0.5$n_{steps}$在精度和速度间权衡一般$10^4$步可取得较好效果$\gamma$加热系数过大导致收敛慢过小则无法逃离局部最优表1比较了不同算法变体在100物品背包问题上的表现算法类型固定点位数达到最优解概率dSB10-bit78%bSB10-bit65%HbSB15-bit82%3. 硬件架构设计3.1 整体架构我们的设计采用模块化结构图2核心组件包括并行计算单元MMTE每个MMTE模块包含矩阵-向量乘法器MM处理$J_{ij}\cdot\text{sgn}(x_j)$计算时间演化单元TE更新$x_i$和$y_i$状态本地存储器存储当前块的自旋状态全局存储器XMEM/YMEM存储所有振荡器的位置和动量SGNXMEM存储$\text{sgn}(x_i)$的符号位J-MEM分块存储相互作用矩阵控制逻辑线性更新器控制泵浦信号$a(t)$的渐变调度器协调MM和TE的流水线执行3.2 三级并行化策略为突破冯·诺依曼架构的串行瓶颈我们设计了三个层次的并行列级并行Pc单行计算中同时处理Pc个矩阵元素。例如Pc4时每个周期可完成 $$ \text{acc}i J{i,j}\text{sgn}(x_j) J_{i,j1}\text{sgn}(x_{j1}) J_{i,j2}\text{sgn}(x_{j2}) J_{i,j3}\text{sgn}(x_{j3}) $$行级并行Pr同时计算Pr行的矩阵乘法。需要复制Pr个乘法累加器MAC每个负责一行计算。模块级并行Pb将整个系统划分为Pb个独立子块每个子块由单独的MMTE模块处理。各模块通过共享总线同步状态。这种设计的优势在于计算复杂度从$O(n_{spin}^2)$降至$O(n_{spin}^2/(Pc \cdot Pr \cdot Pb))$资源消耗线性增长而性能呈多项式提升可根据目标FPGA资源灵活调整并行度3.3 流水线优化通过分析算法流程我们发现MM和TE阶段存在天然的流水线机会时钟周期 | 1 | 2 | 3 | 4 | 5 | ... MM | 行1计算 | 行2计算 | 行3计算 | ... TE | 行1更新 | 行2更新 | ...要实现完美流水线需满足 $$ \frac{n_{spin}}{Pc} \geq Pr $$ 这保证了MM计算下一批行的时间足够TE完成当前行的更新。在256-spin系统中选择Pr16和Pc16可满足该条件。3.4 固定点数优化软件模拟表明10位固定点数表示已能满足dSB的精度需求图3。这带来两大优势资源节省相比32位浮点10位定点数DSP块使用减少75%存储器带宽需求降低68%加法器延迟缩短40%频率提升简化后的数据路径使时序更宽松。在KV260上固定点设计可稳定运行在250MHz而浮点版本仅达150MHz。具体位宽分配整数部分3位覆盖[-4,4]范围小数部分7位精度1/128≈0.0084. 实现细节与优化4.1 矩阵存储优化J矩阵的对称性和稀疏性带来优化空间对称性压缩只存储上三角元素节省近50%存储空间。计算时if (i j) J_val J_mem[j][i]; // 读取转置位置 else J_val J_mem[i][j];块状存储将矩阵划分为16x16子块每个块连续存储。这提高突发传输效率降低存储器访问延迟。稀疏矩阵处理对零元素占比高的场景采用COO格式存储非零元素typedef struct { uint8_t row; uint8_t col; int8_t val; } J_entry;4.2 加热机制实现加热项$\gamma y_i(t_n)\Delta t$的硬件实现需注意随机数生成采用32位LFSR产生伪随机序列经缩放后得到$\gamma$值always (posedge clk) begin lfsr {lfsr[30:0], lfsr[31] ^ lfsr[21] ^ lfsr[1]}; gamma $signed(lfsr[15:0]) * GAMMA_SCALE; end动量更新TE单元中的更新逻辑修改为y_new y_old ( (a0 - a)*x c0*acc )*dt gamma*y_old*dt;4.3 参数化设计通过SystemVerilog参数实现灵活配置module dSB_core #( parameter N_SPIN 256, parameter PC 16, parameter PR 16, parameter PB 4, parameter FIXED_WIDTH 10, parameter FIXED_FRAC 7 ) ( input clk, input rst_n, // ...其他接口 );这种设计允许用户根据目标FPGA资源调整并行度参数Pc/Pr/Pb问题规模N_SPIN数值精度FIXED_WIDTH/FIXED_FRAC5. 实现结果与验证5.1 资源利用率在KV260Artix-7架构上的资源占用资源类型使用量总量利用率LUT28,421154,00018%FF36,752308,00012%DSP484836013%BRAM124163%配置参数Pc16, Pr16, Pb4, 10-bit定点5.2 性能指标求解256-spin max-cut问题G-set G7的性能指标数值时钟频率250 MHz单次迭代周期数68 cycles总迭代步数10,000总计算时间2.72 ms能量效率12 pJ/spin/step相比同平台上的bSB实现dSB展现出速度提升1.8倍精度提高15%功耗降低22%5.3 验证案例我们测试了两个经典问题Max-cut问题使用G-set标准测试集在G7图800节点上的切割值达到2000接近已知最优解2016。背包问题100物品实例中最优解发现率78%平均误差2%。图4展示了不同算法随迭代步数的收敛曲线。6. 使用指南与扩展建议6.1 快速部署步骤环境准备git clone https://github.com/your_repo/dSB-FPGA cd dSB-FPGA vivado -mode batch -source scripts/synth_kv260.tcl参数配置修改include/params.svh中的关键参数define N_SPIN 256 define PC 16 define USE_HEATING 1问题输入准备J矩阵和h向量CSV格式通过Python脚本转换from utils import convert_problem convert_problem(maxcut_G7.csv, formatdSB)6.2 常见问题排查收敛速度慢检查$c_0$是否按$\lambda_{MAX}$正确设置尝试增大$\gamma$值0.3~0.7范围确保初始$x_i$在$[-0.1,0.1]$随机分布结果不理想增加$n_{steps}$到20000以上尝试多次运行取最优解验证J矩阵和h向量的符号是否正确时序违例降低时钟频率10%~20%减少Pc/Pr参数值插入流水线寄存器6.3 扩展方向混合精度计算对J矩阵采用8-bit内部累加用16-bit平衡精度和资源。动态加热策略随迭代步数衰减$\gamma$值模拟退火效果 $$ \gamma(t) \gamma_0 \cdot e^{-t/\tau} $$多FPGA扩展通过高速串行链路如Aurora连接多块FPGA使用图分割算法分配计算任务。这个开源项目为组合优化提供了灵活的硬件加速方案。通过调整并行度参数可以在各类FPGA平台上实现从边缘计算到数据中心的部署。我们期待社区共同完善这一架构推动伊辛机器在实际应用中的发展。