1. 项目概述为什么我们需要一个专用的GQAP硬件加速器在物流规划、芯片布局、网络集群调度这些实际工程问题背后常常隐藏着一个共同的数学幽灵广义二次分配问题。简单来说它就像是在玩一个超级复杂的“连连看”加“俄罗斯方块”游戏。你有n个设施比如工厂、服务器、电路模块每个设施都有大小和相互之间的物流成本你还有m个位置比如仓库、机架、芯片上的区域每个位置有容量限制和彼此间的距离。你的任务是把每个设施分配到一个位置上既要让总成本物流成本乘以距离再加上固定的安置费最低又要保证塞进同一个位置的所有设施加起来不超载。这听起来就让人头大对吧更糟的是随着设施和位置数量增加可能的分配方案数量会爆炸式增长成为一个典型的NP难问题。过去十几年我们见证了通用处理器性能的飞跃但面对这类组合优化问题软件求解器依然力不从心。精确求解器需要的内存和计算时间随着问题规模指数级增长很快就不切实际而启发式算法比如模拟退火、遗传算法虽然能找到不错的解但为了在合理时间内得到高质量解往往需要消耗海量的计算资源。与此同时摩尔定律的放缓让我们意识到不能再单纯指望通用CPU/GPU通过制程工艺提升来拯救我们了。于是领域专用硬件加速器的研究成了新的热点。然而当前硬件加速的研究焦点大多集中在一种名为“二次无约束二进制优化”的模型上。QUBO模型很优雅它把问题映射成一个由二进制变量和耦合系数构成的能量函数然后通过模拟物理退火过程寻找最低能量状态。很多专用硬件比如富士通的数字退火器、D-Wave的量子退火机都是为QUBO量身定做的。但问题在于GQAP天然是带整数变量和容量约束的。为了塞进QUBO的框架你必须进行复杂的转换用多个二进制位编码一个整数并引入巨大的惩罚项来模拟约束。这就像是为了用螺丝刀拧螺母非要把螺母先改造成螺丝一样——不仅工具硬件的利用率低下内存需求呈平方增长还把问题本身的地形解空间搞得崎岖不平引入了无数虚假的局部最优解让搜索算法更容易陷入困境。这就是MOCQA诞生的背景。我们问自己既然现有的QUBO硬件在求解GQAP时如此笨拙为什么不直接为GQAP设计一套原生硬件呢我们的目标很明确构建一个专用的多核硬件系统它能够理解GQAP的整数变量和约束直接在其自然的数学形式上高效运作避免所有因格式转换带来的开销和扭曲。这个系统就是MOCQA——一个为约束二次分配问题量身定制的多核优化器。2. 核心思路从算法到硬件的协同设计MOCQA的设计哲学是“算法-硬件协同设计”。我们不是先设计一个通用算法然后想办法把它加速也不是先设计一个硬件然后硬塞一个算法进去。而是从问题本身出发分析其计算核心设计一个能充分利用硬件并行性的算法再根据这个算法的需求定制高效的硬件架构。2.1 算法基石随机局部搜索与并行回火求解GQAP这类难题我们放弃寻找绝对最优解转而使用启发式算法寻找高质量近似解。其中随机局部搜索是核心。它的过程很像一个精益求精的工匠从随机分配开始不断尝试微小的改动比如把一个设施搬到另一个位置或者交换两个设施的位置如果改动能让总成本下降就接受它即使有时改动会让成本暂时上升也以一定的概率接受这是为了跳出局部最优的“山谷”探索更广阔的区域。这个概率由“温度”参数控制温度高时系统活跃容易接受坏改动以广泛探索温度逐渐降低系统变得“贪婪”只接受好改动最终收敛到一个解。但单一的模拟退火对温度调度非常敏感调不好就容易卡住。于是我们引入了并行回火。想象一下你不是让一个工匠在干活而是同时雇佣了32个工匠我们称之为“副本”每个人在一个不同的工作环境温度下工作。高温的工匠大刀阔斧地尝试各种疯狂方案探索性强低温的工匠精雕细琢专注于局部改进。关键技巧在于这些工匠之间会定期“交换工作环境”。如果低温工匠卡在了一个糟糕的局部最优里而高温工匠恰好探索到了一个能通往更好区域的路径那么通过交换温度低温工匠就能瞬间“传送”到那个更有希望的区域继续深耕。这种机制极大地提升了算法逃离局部最优的能力。2.2 硬件加速的关键玻尔兹曼机缓存SLS中90%以上的时间都花在了一件事上计算一次候选改动移动或交换带来的成本变化ΔC。对于一个有n个设施、m个位置的问题一次交换操作的朴素计算需要O(n)次乘加运算。当n成百上千时这个计算量是巨大的。我们的核心创新是引入了玻尔兹曼机缓存。这个概念借鉴了QUBO中“局部场”的思想但将其推广到了整数变量问题。我们为每一个“设施-位置”对预计算并缓存一个值这个值代表了在当前分配下把该设施放在该位置所产生的“潜在成本影响”。具体来说我们维护一个n×m的矩阵H其中H[i][j]就表示在当前状态下设施i被分配到位置j时它对总成本的贡献包含了它与其他所有设施的交互以及自身的偏置成本。这个缓存矩阵H的妙处在于O(1)时间成本评估当提议将设施a从位置φa移动到位置ℓ时成本变化ΔC可以瞬间通过H[a][ℓ] - H[a][φa]计算出来。对于交换操作也只需访问四个H矩阵中的值和一个小的补偿项。这比原始的O(n)求和快了几个数量级。O(nm)时间缓存更新当然天下没有免费的午餐。一旦一个移动被接受整个系统的状态改变了缓存H就必须更新以保持正确性。幸运的是这个更新可以向量化完成。对于一次移动你需要更新的是所有设施关于所有位置的“潜在影响”这听起来是O(nm)的。但通过数学推导我们发现这个更新可以表达为两个向量的克罗内克积然后加到原矩阵上。在硬件上这意味着我们可以用并行的乘加单元来一次性更新一整行或一列的H值将串行的O(nm)操作转化为高度并行的向量操作。这就形成了MOCQA算法硬件的核心交换我们用一次性的、可高度并行化的O(nm)更新开销换来了后续成千上万次迭代中O(1)的瞬时成本评估。在SLS这种需要评估海量候选动作的算法中这笔交易是极其划算的。2.3 系统级架构分而治之的并行王国基于上述算法MOCQA的系统架构就清晰了。整个系统像一个王国国王一个主控制单元。它不参与具体的“搬箱子”计算只负责宏观调度。它初始化所有副本的温度管理一个高质量的随机数生成器为所有副本提供“随机性燃料”并在每轮局部搜索结束后根据各副本的成本和温度决定是否交换副本间的温度执行并行回火操作。工匠32个副本处理核心。每个RPC都是一个独立的“工匠”拥有自己的一份问题数据副本F, D矩阵当前分配φ缓存矩阵H剩余容量U等。它在一个固定的度下持续进行随机局部搜索提议移动或交换用缓存的H矩阵瞬间计算ΔC检查容量约束然后根据温度和随机数决定是否接受这个提议。如果接受则启动向量化流水线更新自己的H矩阵和U向量。RPC之间几乎不需要通信它们只在每轮结束时向MCU报告一下当前找到的最低成本。这种松耦合的架构是硬件实现的福音它避免了复杂且昂贵的内核间通信让每个RPC都能全力进行计算。3. 硬件实现在FPGA上构建一个32核的GQAP求解机器理论很美好但最终要落实到硅片上或者说可编程逻辑单元上。我们选择在Intel Stratix 10 FPGA上实现MOCQA这是一块拥有丰富DSP数字信号处理器和片上存储资源的高性能芯片。3.1 内存子系统设计为向量化计算量身定制硬件设计的首要挑战是如何高效存储和访问庞大的问题数据。对于一个n255, m128的最大支持规模缓存矩阵H就是一个255x128的矩阵每个元素32位这本身就需要超过1MB的存储。再加上F、D矩阵数据量非常可观。我们的策略是深度定制片上SRAMM20K块的配置矩阵的“切片”存储F和D矩阵被合并存储在一个名为FD的定制内存块中。为了匹配DSP单元18x19位乘法的位宽我们将数据精度定为18位。更重要的是我们将每个矩阵的行从中间“切开”分成左半行和右半行分别存储。这样在需要读取一整行数据时我们可以同时访问两个端口来获取左半和右半实现全行带宽在只需要少数几个元素时我们也可以灵活地分别寻址减少了数据通路宽度和逻辑复杂度。H矩阵的转置模式我们发现当设施数量n远大于位置数量m时按行更新H矩阵每次更新n个元素的效率不如按列更新每次更新m个元素。因此我们设计了一个“转置模式”。在此模式下硬件实际存储和操作的是H的转置。RPC的控制器会根据模式调整其内存访问地址序列和更新流水线的控制逻辑而对上层的算法完全透明。这种灵活性让硬件能自适应不同形状的问题最大化计算单元的利用率。稀疏矩阵的“魔法”处理对于一些特殊问题如图聚类、旅行商问题转化来的GQAP距离矩阵D可能非常稀疏且有规律比如只有0和1。为这种稀疏矩阵浪费大量存储空间是愚蠢的。我们设计了“超大规模稀疏模式”此时不存储D矩阵而是用一个轻量级的解码器多路选择器电路根据行列索引实时生成所需的D矩阵元素值0, 1或-1。虽然增加了一些逻辑资源但节省了上MB的宝贵存储空间。3.2 计算流水线吞吐量与延迟的平衡艺术RPC的核心是一个精心设计的12级流水线专门用于处理“提议-评估”循环。提议生成控制器按顺序生成设施对(a, b)用于交换或(设施a, 位置ℓ)用于搬迁。这保证了在每轮搜索中每个可能的动作都能被公平地评估到。数据读取在同一周期内流水线从多个内存块中并行读取所需数据从H矩阵读取H[a][φa],H[a][φb],H[b][φa],H[b][φb]从FD块读取F[a][b]和D[φa][φb]从DI块读取D[φa][φa]和D[φb][φb]从S和U向量读取设施大小和位置剩余容量。成本与约束计算数据进入专用计算单元。一个单元根据公式计算ΔC另一个单元计算设施大小变化ΔS并检查新的容量U[φa]ΔS和U[φb]-ΔS是否都非负即是否违反约束。随机接受判决这是算法的随机性来源。MCU提供的随机阈值θ_acc由温度T乘以随机数的对数生成与ΔC相加。如果结果小于0且无约束违反则接受该提议。这个设计巧妙地将浮点指数运算exp(-ΔC/T)转化为了比较(ΔC T*log(rand)) 0更适合硬件实现。流水线冲突与解决由于流水线很深当第k个提议被接受时第k1到k11个提议可能还在流水线中计算但它们是基于旧的系统状态已经无效了。我们的处理方法是一旦某个提议被接受控制器立即向流水线发出“清空”信号废弃后续所有未完成的提议计算然后跳转到更新阶段。3.3 更新流水线向量化力量的展现当一个提议被接受后真正的“重活”来了——更新缓存矩阵H和容量向量U。这是整个设计中最能体现并行优势的部分。对于一次交换(a, b)更新过程如下生成差值向量计算行差向量ΔD D[φb, :] - D[φa, :]长度为m以及列差向量ΔF F[:, b] - F[:, a]长度为n。注意ΔD的计算可以向量化完成。外积更新H矩阵的更新是H H ΔF ⊗ ΔD。在硬件上我们实现了一个高度并行的乘加阵列。具体来说我们顺序遍历n个设施索引j。每个周期计算出一个标量ΔF[j]然后将这个标量与整个ΔD向量m个元素进行乘法得到一个向量ΔH[j, :]最后将这个向量加到H矩阵的第j行上。资源权衡最初我们尝试用64个DSP块每个支持两个18位乘法来实现这个向量乘法。但在布局布线时遇到了严重的拥堵问题。最终方案是一半的RPC采用原设计另一半的RPC采用一个替代设计该设计使用128个DSP块配置为32位18x19位模式。这种“混合策略”减少了逻辑资源的使用缓解了布线拥堵确保了设计能达到240MHz的目标频率。3.4 负载均衡让32个工匠步调一致并行回火中不同温度的副本其“提议接受率”差异很大。高温副本接受很多坏改动频繁触发耗时的H矩阵更新低温副本则很少接受改动很快就完成了固定次数的迭代。如果让所有副本都必须完成相同次数的迭代才同步那么快副本就会长时间空等慢副本造成严重的负载不均。我们的解决方案是早期终止同步。一旦任何一个RPC完成了它的所有迭代它就向MCU报告。MCU随即向所有RPC广播一个终止信号强制结束本轮搜索。这样所有RPC同时进入温度交换阶段。虽然这导致每个副本实际执行的迭代次数不同但大量实验表明这种策略带来的同步收益远大于迭代次数不均的损失总体上显著缩短了求解时间。4. 性能实测硬碰硬的较量设计是否成功需要用实验数据说话。我们从公开基准库中选取了21个标准GQAP算例和60个二次多背包问题算例可转化为GQAP对MOCQA FPGA系统进行了全面测试。4.1 对比对象与实验设置我们构建了三个基于MOCQA算法的求解器进行对比MOCQA FPGA本文主角在Intel Stratix 10 FPGA上实现的32核硬件系统。BM$-CPU在64核AMD EPYC服务器上运行的多线程软件实现使用OpenMP每个CPU核心处理一个副本。BM$-GPU在NVIDIA Titan V GPU上运行的软件实现利用CUDA将计算任务映射到大量流处理器上。此外我们还与领域内知名的软件求解器进行了对比PMITS针对GQAP的先进并行Memetic迭代禁忌搜索算法。EPR针对二次多背包问题的进化路径重连算法。我们衡量的心指标是求解时间找到已知最优解所需的时间、命中率在多次随机运行中找到最优解的概率、功耗和能效能量功耗×时间。4.2 GQAP基准测试结果在与PMITS的对比中MOCQA展现出了压倒性的速度优势。在全部21个算例上MOCQA FPGA比我们的多核CPU软件实现平均快2.4倍比GPU实现平均快6倍。尤其在一些中等规模的算例上如30-20-95,40-09-95MOCQA比PMITS快了4到5个数量级。即使考虑到PMITS使用的CPU较老将其移植到最新旗舰CPU上性能差距依然在几个数量级。这充分证明了专用硬件架构的威力。4.3 二次多背包问题测试结果QMKP是GQAP的一个特例我们通过附录B中的转换方法将其映射到GQAP格式进行求解。与当前最好的QMKP专用求解器EPR相比MOCQA在绝大多数算例上都取得了更好的平均解质量和更高的命中率。在“最快命中时间”这个指标上MOCQA平均比EPR快3.85倍。需要说明的是EPR是单线程程序运行在较老的Xeon CPU上。我们进行了保守估计即使EPR能完美扩展到40核与MOCQA的32副本可比其并行后的求解时间也大致等于其单次运行的最快命中时间。即便如此MOCQA依然保持了显著的速度优势。4.4 内部对比与能效分析在我们自己的三个实现中MOCQA FPGA在60个QMKP算例中的59个上都取得了最快的求解时间。平均来看FPGA比CPU软件快4.44倍比GPU软件快4.13倍。在命中率上FPGA也普遍高于或等于软件实现。功耗方面FPGA芯片本身的功耗在32W到37W之间整个板卡约70-76W。作为对比满载的64核CPU功耗稳定在280W厂商设定的功耗墙而GPU的功耗在77W到114W之间波动。将时间与功耗结合我们得到最关键的指标能量效率。计算完成一个算例所需的总能量。结果显示MOCQA FPGA的平均能效比CPU软件实现高35.6倍比GPU实现高10.4倍。这意味着在完成相同计算任务时FPGA方案消耗的电能要少一个数量级。这对于数据中心部署或边缘计算场景具有重大意义。5. 经验总结与未来展望回顾整个MOCQA项目从问题分析、算法创新到硬件实现与验证有几个关键点值得与各位同行分享第一拥抱问题的原生结构而不是强迫它适应现有硬件。早期我们也曾尝试将GQAP强行塞进QUBO框架再用现有的QUBO加速器求解结果总是事倍功半。内存爆炸、惩罚项调参、解空间畸变……这些问题让我们最终下定决心为GQAP设计原生硬件。这个决定带来了算法上的简洁直接处理整数和约束和硬件上的高效紧凑的数据结构和直接的计算路径。第二算法与硬件的深度协同是性能飞跃的关键。BM$向量化方案不是一个孤立的算法技巧它直接指导了硬件内存布局H矩阵的存储和计算单元设计并行的外积更新流水线。并行回火算法松耦合的特性则天然适合映射到多核、低通信开销的硬件架构上。这种从计算本质出发的软硬件协同设计是获得数量级性能提升的根本。第三硬件设计必须在灵活性与效率间取得平衡。我们的FPGA实现包含了三种操作模式常规、转置、稀疏以应对不同规模和结构的问题。这增加了控制逻辑的复杂性但换来了更广的适用性。在资源使用上我们采用了混合策略部分RPC用更多DSP换更少逻辑来解决布线拥堵问题。这些都是在实际布局布线中遇到的真实挑战教科书上不会写。第四验证需要全面且公平的基准测试。我们不仅对比了自家软件实现还对比了领域内公认的先进软件求解器。测试集涵盖了标准GQAP和可转化的QMKP证明了架构的通用性。除了速度我们还严格测量了功耗和能效这在“双碳”目标下越来越重要。关于未来MOCQA还有很长的路可以走。下一步我们计划探索更复杂的副本间交互机制例如引入基于遗传算法的种群交叉而不仅仅是温度交换。在硬件层面如何将多个FPGA板卡互联以支持更大规模的问题n1024或者将RPC设计用ASIC实现以获得更高的频率和能效都是值得研究的方向。此外当前稀疏模式的支持还比较基础未来可以设计更通用的稀疏矩阵处理单元以支持更广泛的低密度问题。最后分享一个在调试负载均衡策略时踩过的坑。最初我们让所有RPC严格运行相同迭代次数结果发现低温核心早早完工后空转严重拖累整体吞吐量。改为“任一完成即同步”的策略后整体性能提升了近40%。这个经验告诉我们在并行系统中木桶的短板有时不是最慢的那个核心而是同步机制带来的空闲时间。让快的核心带动慢的核心而不是被慢的核心拖住是提升整体效率的关键。