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 内存子系统设计：为向量化计算量身定制
硬件设计的首要挑战是如何高效存储和访问庞大的问题数据。对于一个n=255, m=128的最大支持规模，缓存矩阵H就是一个255x128的矩阵，每个元素32位，这本身就需要超过1MB的存储。再加上F、D矩阵，数据量非常可观。
我们的策略是深度定制片上SRAM（M20K块）的配置：
- 矩阵的“切片”存储：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个提议被接受时，第k+1到k+11个提议可能还在流水线中计算，但它们是基于旧的系统状态，已经无效了。我们的处理方法是：一旦某个提议被接受，控制器立即向流水线发出“清空”信号，废弃后续所有未完成的提议计算，然后跳转到更新阶段。
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-95），MOCQA比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板卡互联以支持更大规模的问题（n>1024），或者将RPC设计用ASIC实现以获得更高的频率和能效，都是值得研究的方向。此外，当前稀疏模式的支持还比较基础，未来可以设计更通用的稀疏矩阵处理单元，以支持更广泛的低密度问题。
最后，分享一个在调试负载均衡策略时踩过的坑。最初我们让所有RPC严格运行相同迭代次数，结果发现低温核心早早完工后空转，严重拖累整体吞吐量。改为“任一完成即同步”的策略后，整体性能提升了近40%。这个经验告诉我们，在并行系统中，木桶的短板有时不是最慢的那个核心，而是同步机制带来的空闲时间。让快的核心带动慢的核心，而不是被慢的核心拖住，是提升整体效率的关键。
