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）。
图1：通过与其他大数字比较，直观感受2^64的大小。
| 最小 | 最大 | 人体细胞数量 | 地球沙粒数量 | 2^64 | 阿伏伽德罗常数 | 宇宙中的恒星数量 |
|---|---|---|---|---|---|---|
| 3.72 * 10^13 | 7.5 * 10^18 | 1.84 * 10^19 | 6.02 * 10^23 | 10^24 |
现代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核共享服务器。这两台机器在测量时同时运行其他软件。运行在2.93 GHz的Core i3 530是一台旧机器，在复活用于这个项目之前，它实际上被用作脚凳和猫抓板，这要归功于它的GPU。
请求拉取： 您会注意到这些都是x86 CPU。非常需要ARM系统的测量。我没有包括这些，因为这个项目已经花了太长时间，我必须从头开始学习ARM的SIMD指令。
天真的for循环
有人说过早优化是万恶之源。因此，让我们测量一个通用的for循环比较所有2^64值需要多长时间。下面的图2列出了在完整64位范围的子集上执行的每毫秒操作数（10次运行的平均值），以及尝试所有2^64值所需时间的估计。
图2：对所有2^64值的通用for循环比较。
| 设备 | 每毫秒操作数 (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 |
最天真的方法需要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（图表）中，我们可以比较我们硬件集合中可用的不同向量化方法。
图3：向量化和天真版本的64位比较操作性能。并非所有硬件平台支持相同的向量化方法。
| 设备 | 方法 | 每毫秒操作数 (ms⁻¹) | 完成年数 (年) |
|---|---|---|---|
| 2018 MacBook Pro | 天真 | 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 | 天真 | 1.45E+06 | 402.46 |
| Core i3 530 | SSE | 3.08E+06 | 190.12 |
| DO高CPU | 天真 | 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 | 天真 | 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 | 天真 | 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 |
上表为完整性而包含；下面相同数据的图表提供了更直观的比较。
图4：图3的图形表示；单核上比较64位数字的不同方法性能。
这些数据中突出几点：
- 向量化总是有帮助的。即使考虑了将值移入和移出向量寄存器的设置时间，每次迭代比较更多值总是更快。
- AVX2（一次四个比较）比SSE4.1（一次两个比较）有重大改进。正如预期，AVX2比SSE4.1快约两倍。
- 相反，AVX-512（一次八个比较）比AVX2（一次四个比较）改进很小。怎么会这样？我怀疑这是因为使用AVX-512指令的一个鲜为人知的副作用：它们会使处理器速度降低多达40%。处理器的功率预算不允许它既全速运行又大量使用AVX-512。
即使有这些改进，在单核上检查所有64位仍然需要39年。使用多核我们能走多快？
并行化和向量化
在64位干草堆中找针的问题恰好是极其可并行化的，因此多核应该提供线性的吞吐量增加。下面的数据（图5）显示这是真的——除非不是！有时性能即使添加更多核心也会停滞。怎么会这样？
这种效应是由于超线程。超线程处理器将物理核心呈现为两个或更多虚拟核心给操作系统。虽然每个超线程看起来独立，但底层执行单元是共享的。对于计算密集型应用程序，超线程可能对性能产生显著和令人惊讶的影响。在超线程环境和CPU密集型工作负载中，使用哪些核心可能与核心数量一样重要。这对于基于云的工作负载尤其重要，其中每个vCPU是物理核心上的一个超线程。
图5：每台测试机器的每小时操作数与核心数量的关系，按分配核心的不同方法分开。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”，大致相当于一个超线程核心。对于物理机器，每个核心是一个超线程核心。
图6：观察到的多处理最佳时间，以及在多少核心时。
| 设备 | 核心（超线程） | 每毫秒操作数 (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中唯一的异常值是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教程级别的优化，也有一个数量级的性能增益。
图8：GPU上的64位比较吞吐量，以及搜索所有64位的估计年数。
| 设备 | 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而不是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）。
图10：CPU和GPU时间比较一个值与2^64数字所需的成本，以计算年衡量。成本是Google Cloud上可抢占时间的成本。
| 计算年需求 | 每小时成本（可抢占） | 总成本 |
|---|---|---|
| 可抢占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 |
对于一开始看起来如此不可逾越的事情，最终成本完全在可及范围内：将一个数字与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
页面内容
- 六十四（不止）是一个神奇的数字
- 64位数字有多大？
- 数字计算
- 天真的for循环
- 向量化for循环
- 并行化和向量化
- 进入图形
- 给我看钱
- 结论
最近帖子
- 我们构建了MCP一直需要的安全层
- 利用废弃硬件中的零日漏洞
- 深入EthCC[8]：成为智能合约审计员
- 使用