64 Bits ought to be enough for anybody!
六十四（不止）是一个神奇数字
为什么尝试猜测64位数？现代处理器以64位数量运行，因此64位是魔法数字、文件头和其他标记的自然长度。在模糊测试中，经常遇到与这类64位“魔法值”的比较，但猜测这些值被视为经典不可能问题。幸运的是，无需暴力破解，存在更优方法如移除比较、使用预制输入种子、字典、符号执行和编译时转换。
但暴力猜测问题易于理解和并行化，能有效展示并行化对艰巨任务的威力。此问题还表明，随着硬件提速，新的计算问题变得可行。想象我们利用现代计算全力能实现什么！
然而，我们必须考虑通过尝试所有可能性来猜测64位数的棘手程度。需要多长时间？成本多少？
64位数有多大？
64位数可容纳2^64（即18,446,744,073,709,551,616）个不同值——超过地球沙粒和人体细胞数量（图1）。
| 最小 | 最大 |
|---|---|
| 人体细胞数 | 地球沙粒量 |
| 2^64 | 阿伏伽德罗常数 |
| 宇宙恒星数 | 10^24 |
图1：通过与其他大数比较直观感受2^64的大小。
现代CPU每秒执行约2700亿条指令，因此穷举2^64搜索空间需776天——略超两年。幸运的是，暴力比较是易并行问题，工作可均匀分配至多处理器。若能让每个处理器同时执行多次比较呢？或许有服务能快速提供大量处理器。
突然之间，这变得可行了！
数字计算
免责声明：在深入数字前，强调此为趣味实验而非基准测试。未尝试确保不同处理器或机器的公平对比。此外：
- 生成性能数据的代码用C编写且无测试。
- 可能非最快版本。
- 肯定存在多个错误。
- 事实上，评审中发现严重时间测量错误导致本文延迟数周。
- 欢迎在Github提交修复和建议。
所有测量反映10次试验平均值。两台测试机器为Digital Ocean和Google Cloud的云实例。Digital Ocean（DO）高CPU实例自报为“Intel(R) Xeon(R) Platinum 8168 CPU”运行于2.70 GHz。Google Cloud（GCP）高CPU实例自报为“Intel(R) Xeon(R) CPU”运行于3.10 GHz。这些自报标识均不可信：虚拟化平台可以且通常谎报底层CPU。云机器亦共享，其他租户操作可能影响CPU吞吐量。
物理测试机器中，我的2018 MacBook Pro搭载Intel Core i7 8559U处理器。Xeon E5-2640 v4为2.40 GHz 40核共享服务器。两台机器在测量时同时运行其他软件。Core i3 530运行于2.93 GHz是一台旧机器，原用作脚凳和猫抓柱，因其GPU为本项目复活。
求Pull Requests：您会注意到这些都是x86 CPU。急需ARM系统测量。未包含因项目已耗时过长，且需从头学习ARM的SIMD指令。
朴素for循环
有人说过早优化是万恶之源。因此我们测量通用for循环比较所有2^64值所需时间。图2列出在完整64位范围子集上每毫秒执行操作数（10次运行平均），及尝试所有2^64值的估计时间。
| 设备 | 每毫秒操作数 (ms⁻¹) | 完成年数 (年) |
|---|---|---|
| 2018 MacBook Pro | 4.41E+06 | 132.78 |
| Core i3 530 | 1.45E+06 | 402.46 |
| DO高CPU | 3.50E+06 | 167.30 |
| GCP高CPU | 3.77E+06 | 155.21 |
| Xeon E5-2640 v4 | 3.37E+06 | 173.38 |
图2：通用for循环比较所有2^64值。
最朴素方法需133年。显然等待时间过长，需优化。
向量化for循环
现代处理器可通过SIMD或向量指令同时操作多个64位数量。目前Intel以AVX-512领先，如名所示操作512位向量。这让我们每迭代比较八个64位数量。想了解更多向量指令，康奈尔有优秀入门材料。
向量化是将一次运行一个数量（标量）的代码转换为同时操作多个数量（向量）的过程。向量化是我的首个优化，因我以为clang会自动向量化代码。可惜我错了——clang的自动向量化旨在向量化不依赖循环变量的代码，如矩阵乘法。未依赖编译器，我使用手工精心制作的向量化比较（sse、avx2和avx512）和手动展开循环以最大化利用多向量执行单元。
向量指令持续改进，但非所有x86 CPU支持AVX-512。有些仅支持AVX2（256位向量），其他仅SSE4.1（128位向量），有些甚至不支持。在图3（表）和图4（图）中，我们比较硬件集合中可用的不同向量化方法。
| 设备 | 方法 | 每毫秒操作数 (ms⁻¹) | 完成年数 (年) |
|---|---|---|---|
| 2018 MacBook Pro | Naive | 4.41E+06 | 132.78 |
| 2018 MacBook Pro | SSE | 6.73E+06 | 86.94 |
| 2018 MacBook Pro | AVX2 | 1.51E+07 | 38.85 |
| Core i3 530 | Naive | 1.45E+06 | 402.46 |
| Core i3 530 | SSE | 3.08E+06 | 190.12 |
| DO高CPU | Naive | 3.50E+06 | 167.30 |
| DO高CPU | SSE | 4.86E+06 | 120.44 |
| DO高CPU | AVX2 | 1.09E+07 | 53.57 |
| DO高CPU | AVX512 | 1.41E+07 | 41.44 |
| GCP高CPU | Naive | 3.77E+06 | 155.21 |
| GCP高CPU | SSE | 5.02E+06 | 116.41 |
| GCP高CPU | AVX2 | 1.17E+07 | 49.82 |
| GCP高CPU | AVX512 | 1.35E+07 | 43.37 |
| Xeon E5-2640 v4 | Naive | 3.37E+06 | 173.38 |
| Xeon E5-2640 v4 | SSE | 4.50E+06 | 129.99 |
| Xeon E5-2640 v4 | AVX2 | 1.02E+07 | 57.49 |
图3：向量化和朴素版本64位比较操作性能。非所有硬件平台支持相同向量化方法。
上表为完整性包含；下图相同数据提供更易视觉比较。
图4：图3的图形表示；单核上不同方法比较64位数的性能。
数据中突出几点：
- 向量化总有助。即使考虑值移入移出向量寄存器的设置时间，每迭代比较更多值总是更快。
- AVX2（一次四比较）相对SSE4.1（一次两比较）是大改进。如预期，AVX2约比SSE4.1快两倍。
- 相反，AVX-512（一次八比较）相对AVX2（一次四比较）是小改进。为何？我怀疑这是使用AVX-512指令的鲜为人知副作用：它们使处理器减速高达40%。处理器功率预算不允许全速运行且重度使用AVX-512。
即使有这些改进，单核检查所有64位仍需39年。使用多核能多快？
并行化和向量化
在64位干草堆中找针问题可笑地可并行化，因此多核应提供线性吞吐量增长。下图（图5）数据显示此为真——除非不是！有时性能 plateau 即使添加更多核。为何？
此效应归因于超线程。超线程处理器向操作系统呈现物理核为两个或更多虚拟核。虽然每个超线程显示独立，底层执行单元共享。对计算密集型应用，超线程对性能有显著惊人影响。在超线程环境和CPU密集型工作负载中，使用哪些核可能与核数量几乎同样重要。这对基于云的工作负载尤其重要，其中每个vCPU是物理核上的超线程。
图5：每测试机器每小时操作数 versus 核数，按分配核方法分隔。省略MacBook Pro和Core i3 530结果。
图5显示使用两种方法分配工作者到超线程的多核性能。分离核分配至不同物理核，而共享核分配至相同物理核。
40超线程核Xeon E5-2640机器代表此差异：使用分离核分配，性能峰值在20核——物理核数量——然后稳定。使用共享核分配，吞吐量遵循阶梯函数，随每个新物理核增加。我们还可使用此数据推断云硬件：高CPU GCP实例的16 vCPU可能代表8物理和16超线程核专用于我们工作负载。
DO高CPU机器呈现谜题：未观察到相同效应。假设vCPU来自真实单Xeon Platinum 8168，利用24核后应有差异。未发生，有几种可能解释。首先，vCPU非来自相同物理处理器：Xeon 8168可在8路多处理配置中运行。其次，处理器非Xeon 8168，而是其他芯片。最后，我的线程亲和性或时间测量代码可能有问题。
无论如何，缩放结果展示宝贵教训：使用更多核并非总是更好，且使用哪些核（或vCPU）重要。对此工作负载，当分配多于机器中物理核的工作者时，增益很小或无。性能关键时总是测量。
为完整性，图6列出利用多核时每毫秒操作数和估计完成年数，每核使用最快支持单核方法。对云机器，每核是“vCPU”，约等效于一个超线程核。对物理机器，每核是一个超线程核。
| 设备 | 核数 (超线程) | 每毫秒操作数 (ms⁻¹) | 完成年数 (年) |
|---|---|---|---|
| Xeon E5-2640 v4 | 39 / 40 | 1.57E+08 | 3.73 |
| GCP高CPU | 16 / 16 | 1.24E+08 | 4.71 |
| DO高CPU | 32 / 32 | 2.55E+08 | 2.30 |
| Core i3 530 | 2 / 4 | 6.24E+06 | 93.76 |
| 2018 MacBook Pro | 8 / 8 | 5.14E+07 | 11.38 |
图6：观察的最佳多处理时间，及在多少核。
图6中唯一异常值是Xeon E5-2640，在39/40超线程核表现最佳，和Core i3 530在2/4超线程核表现最佳。为何39核？机器共享且处理其他工作负载；在39核，所有工作负载可放一核。在40核利用，工作负载分散至更多核并占用CPU密集型整数比较的调度时间。
如预期，使用多CPU大幅减少计算时间。然而，仍太慢。我们不能期望等待超两年猜测一数。
进入图形
GPU采取与CPU不同的计算方法。CPU擅长多并发任务；GPU擅长对海量数据执行简单操作。这体现在主要架构差异：高端CPU可能带24个非常复杂核，而高端GPU带5,120个简单核（图7）。
图7：这是NVIDIA的Tesla V100 GPU。它带5,120 CUDA核且是测试中最强大GPU。图形取自NVIDIA Volta架构白皮书。
无意中，我挑选了为GPU优化量身定制的问题。暴力比较易于并行化，涉及无复杂决策，且完全计算受限。感谢GPU在机器学习中的角色，每个大云提供商提供廉价非高峰GPU容量。
弄清楚如何使用GPU计算需一些工作，但绝对值得。仅看图8中的吞吐量！即使我开始时GPU编程和CUDA知识约零，且我的CUDA代码约是我首CUDA教程级优化，仍有数量级性能增益。
| 设备 | GPU数 | 每毫秒操作数 (ms⁻¹) | 完成年数 (年) |
|---|---|---|---|
| GeForce GT 1030 | 1 | 1.60E+08 | 3.66 |
| NVIDIA Tesla K80 | 8 | 2.92E+09 | 0.20 |
| NVIDIA Tesla P100 | 4 | 4.19E+09 | 0.14 |
| NVIDIA Tesla V100 | 4 | 9.08E+09 | 0.06 |
图8：GPU上64位比较吞吐量，及估计搜索所有64位年数。
如图8所示，使用GPU而非CPU将所需时间从年缩短至天。正确平台的差异多大！旧$85显卡（GeForce GT 1030）性能与40核Xeon机器相当。使用4x NVIDIA Tesla V100 GPU，我们可在0.06年或约22天内暴力破解64位比较。
对此问题CPU和GPU计算差异如此戏剧性（单V100约比16高CPU核快18.5倍）以至于使用CPU无意义。添加另一GPU总是比依赖CPU计算更好资源利用。为展示CPU在此问题多差，我制作此方便图形：
图9：选定CPU和GPU上比较64位数时的吞吐量。此特定问题在GPU上可如此快完成以至于使用CPU完全无意义。
现在我们从130年（朴素for循环）到22天（多GPU），能否到小时或分钟？需要多少硬件……成本多少？
展示金钱
我们确立GPU比CPU快得多，但GPU时间也更昂贵。且哪种GPU最佳？不同GPU系列价格相当不同。
使用当前定价（截至2019年11月），我们可见GPU的价格/性能约比CPU好~5倍。虽更昂贵，V100提供比其GPU前辈更好的每美元性能（图10）。
| 所需计算年数 | 每小时成本（可抢占） | 总成本 |
|---|---|---|
| 可抢占CPU GCP [16 vCPU] | 4.71 | $0.20 |
| 可抢占GPU [4x P100] | 0.14 | $1.76 |
| 可抢占GPU [4x V100] | 0.06 | $3.00 |
| 可抢占K80 [8x K80] | 0.20 | $1.12 |
图10：CPU和GPU时间价格需比较值对2^64数，以计算年测量。成本为Google Cloud上可抢占时间。
对开始时看似不可逾越的事物，最终成本触手可及：比较数对2^64值需约$1,700可抢占GPU计算时间。
因问题可如此高效并行化，总计算时间几乎直接可互换为硬件成本和可用性。例如，4x V100 GPU将约22天查看所有2^64数，但2,259x V100 GPU将约一小时查看2^64数，总成本相同。
结论
此愚蠢实验展示理解您的问题、硬件和普通开发者可用计算资源的重要性。
看似完全疯狂的想法结果仅轻度 insane。尝试2^64比较将花费约$1,700计算时间，且可在小时或天内完成。
我们沿途还学到一些事：
- 并行化并非总是容易，但可非常有效。学习一些CUDA让此原不可逾越问题从不可行到“可容忍但昂贵”。
- 使用更多核并非总是更好，且使用哪些核重要。
- 底层硬件可在云抽象下泄漏。
- 云计算提供访问近乎无限按需硬件；只需投入使用。
- 肯定有许多问题看似疯狂且完全不可及，但可通过可并行算法、云计算和公司信用卡组合解决。
我们总是开发方法工作更快更智能。需要帮助您的下个项目？联系我们！
如果您喜欢此文，分享它： Twitter LinkedIn GitHub Mastodon Hacker News