Microcanonical simulated annealing: Massively parallel Monte Carlo simulations with sporadic random-number generation

本文提出了一种通用的微正则模拟退火（MicSA）形式体系，该体系大幅降低了大规模并行蒙特卡洛模拟中随机数生成的计算负担，并通过在 GPU 和 Janus II 超级计算机上对三维伊辛自旋玻璃进行的严格基准测试，证明了其有效性及其与标准方法的动力学等价性。

要点

想象你正试图在广阔而迷雾笼罩的群山中找到最低点。这是物理学和计算机科学中的一个经典问题：在数百万种可能性中寻找“最佳”解（即最低能量态）。为此，科学家使用一种称为模拟退火的方法，其原理类似于摇晃一盒弹珠，帮助它们落入最深的坑洞中。

然而，这里有一个陷阱。摇晃盒子的标准方法（称为蒙特卡洛模拟）需要海量的随机数。你可以将这些随机数视为决定弹珠是移动还是静止的“掷骰子”结果。

问题：掷骰子瓶颈

在现代超级计算机中，尤其是那些拥有数千个处理器并行工作（大规模并行）的计算机，计算机花费大量时间进行这些数字“掷骰子”，以至于忘记了实际移动弹珠。这就像一条工厂流水线，工人们 90% 的时间都在掷骰子，只有 10% 的时间在制造产品。随着计算机速度的提升，这种“掷骰子”过程反而成了整个流程中最慢的部分，浪费了巨大的计算能力。

解决方案：“微正则”技巧

本文作者提出了一种运行这些模拟的巧妙新方法，称为微正则模拟退火（MicSA）。

他们使用以下类比来解释它：
想象弹珠（即自旋）连接着名为“小电池”或“行走者”的微型能量电池。

• 旧方法：每次你想移动一颗弹珠时，都要掷一颗新骰子来决定是否允许移动。
• 新方法（MicSA）：你根本不需要掷骰子。相反，你检查电池。如果弹珠移动并损失能量，该能量会瞬间转移到电池中。如果电池有足够的电量，移动就会发生；否则，移动不会发生。

由于系统的总能量（弹珠 + 电池）保持不变，你无需掷骰子来检查移动是否“随机”允许。你只需检查数学计算。这意味着你可以同时移动数百万颗弹珠，而无需停下来掷骰子。

“刷新”机制

这里有一个问题：如果你从不掷骰子，电池可能会变得过满或过空，导致系统陷入某种奇怪的状态。为了解决这个问题，作者采用了一种非常特定的调度方案：

• 他们让系统长时间运行，期间不掷任何骰子。
• 然后，非常罕见地（例如每几千步一次），他们“刷新”电池。他们丢弃旧的电池电量水平，并仅为电池生成一组全新的随机数。
• 由于这种情况发生得极其罕见，计算机几乎 100% 的时间都用于移动弹珠，而几乎 0% 的时间用于掷骰子。

结果：它有效吗？

该团队在一个非常困难的问题上测试了这种新方法：三维自旋玻璃（一种极其难以模拟的复杂磁性材料）。他们使用两台不同的超级计算机，将新的“无骰子”方法与标准的“掷骰子”方法进行了比较：

1. Janus II：专为解决此问题而定制的超级计算机。
2. GPU：标准显卡（如游戏计算机中的显卡），运行他们的新型代码。

发现：

• 准确性：当系统稳定下来（达到平衡）时，两种方法给出的结果完全相同。
• 速度：由于新方法不会因生成随机数而受阻，它在标准 GPU 上的运行速度极快。
• 时间重标度：唯一的区别在于，“无骰子”方法在“步数”意义上的移动速度稍慢或稍快。但如果你简单地调整时钟（重标度时间），两种方法就能完美匹配。这就像观察两名跑步者：一名每 10 秒跑一步，另一名每 11 秒跑一步，但如果你调整秒表，他们的跑步节奏实际上是相同的。

为何这很重要

该论文声称，这种方法使科学家能够在标准的、现成的硬件（如你游戏电脑中的 GPU）上运行大规模模拟，而这些模拟以前只能在昂贵、定制的超级计算机上实现。它解决了“掷骰子”瓶颈，使得无需发明新硬件就能更高效地模拟复杂系统成为可能。

简而言之：他们找到了一种模拟复杂物理问题的方法，用智能的能量转移系统取代了持续的随机掷骰子，从而使普通计算机能够完成过去需要专用超级计算机才能完成的工作。

技术摘要

技术摘要：微正则模拟退火（MicSA）

问题陈述
蒙特卡洛模拟对于研究自旋玻璃等复杂系统以及求解组合优化问题至关重要。然而，在大规模并行实现（例如在 GPU 或定制硬件上）中，一个关键的瓶颈在于高质量伪随机数的生成。随着硬件复杂度的提升，用于随机数生成的计算时间占比日益增加，对于专用平台而言已变得难以承受。作者指出了一个冲突：并行更新需要海量的独立随机数流，而生成这些数字在计算上却非常密集。

方法论
作者提出了一种**微正则模拟退火（MicSA）**形式体系，旨在极度节省随机数的使用，同时保持与大规模并行计算的完全兼容。该方法在三维 Edwards-Anderson Ising 自旋玻璃模型上进行了基准测试。

算法的核心包含以下组件：

1. 扩展构型空间： 系统通过引入与每个自旋关联的辅助自由度（称为“恶魔”或“游走者”，记为 $n_{x,\alpha}$）进行扩充。总哈密顿量为 $H = H_{EA} + H_{aux}$，其中 $H_{aux}$ 是这些辅助变量的总和。
2. Creutz 类移动： 作者改进了 Creutz 算法，而不是积分掉辅助变量（这将破坏并行更新所需的可分离性）。提出一个自旋翻转，并通过更新一个辅助变量（$n_{x,\alpha} \to n_{x,\alpha} - \Delta H_{EA}$）来补偿自旋能量的变化（$\Delta H_{EA}$）。此移动不需要随机数，并保持了扩展系统的总能量守恒。
3. 可分离性与并行性： 为了实现并行更新，晶格被分解为偶数和奇数子晶格（棋盘分解）。算法同时更新具有相同奇偶性的所有自旋。
4. 恶魔与游走者：
   • 恶魔： 绑定到特定晶格位置的辅助变量。
   • 游走者： 允许在晶格中游走的辅助变量。作者实施了一种“游走”过程，其中游走者以特定模式（例如沿 X、Y、Z 轴的前向/后向）在相邻位置之间交换数值，以避免导致动力学变慢的局部守恒定律。
5. 微正则模拟退火： 为了达到正则平衡分布，系统必须被冷却。算法在特定的时间间隔内，通过从其正则分布（公式 11）中抽取新值来“刷新”恶魔/游走者的构型。
   • 关键在于，刷新时间表是对数级的（在时间 $t_s = 2^s$ 时）。这最大限度地减少了随机数生成的频率，因为自旋玻璃的能量弛豫是缓慢的（幂律或对数级）。
   • 刷新有效地降低了系统的总能量，模拟了标准模拟退火的冷却过程，但仅作用于辅助变量。

主要贡献

• 算法创新： 一种通用形式体系，将随机数生成减少为零星事件（随时间呈对数级），同时保持正则模拟的统计特性。
• 大规模并行适配： 该方法专为并行架构（GPU）设计，利用多自旋编码，并避免了先前微正则系综（如 Lustig 的系综）中发现的非线性耦合问题。
• 动态可重标度性： 作者证明，MicSA 的非平衡动力学可以通过简单的重标度因子（$k^*$）映射到标准正则 Metropolis 动力学上。

结果
作者将 MicSA 模拟（在 Nvidia GPU 上执行）与针对三维 Ising 自旋玻璃执行的高精度标准 Metropolis 模拟（在 Janus II 定制超级计算机上执行）进行了比较。

• 动力学的等价性： 在顺磁相（$T > T_c$）和自旋玻璃相（$T < T_c$）中，应用时间重标度 $t_{plot} = k^* \times t_{MicSA}$ 后，通过 MicSA 获得的能量弛豫 $e(t)$ 和相干长度 $\xi_{12}(t)$ 与正则结果无法区分。
• 重标度因子： 最佳重标度因子 $k^*$ 取决于每个自旋的游走者/恶魔数量（$\gamma$）。对于 $\gamma=6$ 的“游走者”变体，$k^* \approx 6.034$，这与每个时间步每自旋的更新次数几乎相同。这表明一个 MicSA 步骤等价于 $\gamma$ 次 Metropolis 扫描，而无需随机数。
• 性能： 在 Nvidia H100 GPU 上，MicSA 算法（包括游走过程）实现了每自旋约 0.4 皮秒的自旋更新时间。这显著快于标准 Metropolis 中的随机数生成步骤（后者在标准算法中消耗了约 72% 的时间）。
• 平衡验证： 在附录 C 中，作者证明结合并行退火的 MicSA 能够成功复现具有高斯耦合的小系统的平衡值，从而确认了其在平衡研究中的有效性。

意义与主张
该论文声称，MicSA 为大规模蒙特卡洛模拟中的随机数瓶颈提供了一个“广泛可用”的解决方案。

• 效率： 通过将对数级刷新带来的随机数需求降低数个数量级，该方法使得在高端 GPU 和潜在专用集成电路（ASIC）上的大规模并行模拟更加高效。
• 通用性： 该方法不仅限于自旋玻璃；作者认为它适用于任何成本函数（能量）离散变化或可通过辅助变量处理的问题，包括组合优化。
• 验证： 作者断言，动态重标度性质在不同温度和算法变体（恶魔与游走者）之间均成立，证实 MicSA 属于与标准 Metropolis 动力学相同的动态普适类。

作者在范围上保持谦逊，指出对于非常小的系统或具有连续分布能量变化（例如高斯耦合）的问题，需要特定的适配（连续游走者），且最佳刷新率可能因具体问题和硬件而异。他们并不声称 MicSA 解决了自旋玻璃的 NP 完全性问题，而是提供了一种研究它们的高效计算工具。