• 论文题目：There’s plenty of room at the Top: What will drive computer performance after Moore’s law?
  • 作者：Charles E. Leiserson, Neil C. Thompson, Joel S. Emer 等
  • 期刊：Science
  • 年份：2020

背景

由于晶体管的物理结构限制，使得其体积难以再度缩小，摩尔定律也随之迎来终结。种种迹象表明，底层的优化空间已经很小，而与之相对的顶层仍有很大的空间。顶层可以分为三层：

  • 硬件架构：执行计算的可编程数字电路。
  • 软件：指示数字电路的计算内容的代码。
  • 算法：组织一个计算的有效的问题解决例程。

底层优化往往可以使得计算机的各个方面同时得到提升，而顶层优化通常只能改善特定的某个方面，并且其收益会受到边际效应递减规律的影响。

边际效应递减规律：在一定时间内，在其他商品的消费数量保持不变的条件下，随着消费者对某种商品消费量的增加，
消费者从该商品连续增加的每一消费单位中所得到的效用增量即边际效用是递减的。

相比于底层，顶层的许多部分是互相依赖的，因此，当一个部分被重组以提高性能时，其他部分常常需要依此进行重新设计，这使得顶层优化具有很高的成本和风险。接下来将从顶层的软件、算法和硬件3个方面阐述可优化的空间，并探讨大型系统组件的优势。

软件

由于在摩尔时代，软件的开发更多聚焦于开发效率而不是产品质量，导致在软件层面存在严重的效率低下，通常被称为软件膨胀。此外，目前的大多数软件并没有很好地利用芯片的体系结构特性，如并行处理器和向量计算单元。因此，在后摩尔时代，需要软件性能工程对软件进行重组，在如上两个方面进行优化，使得程序具有更高的能效。

以2个4096 $\times$ 4096矩阵的乘法为例，python代码如下：

1
2
3
4
for i in xrange(4096):
    for j in xrange(4096):
        for k in xrange(4096):
            C[i][j] += A[i][k] * B[k][j]

但这样的代码完全没有利用到现代计算机的优势。对上面的工作在不同的条件下进行测试，得到如下结果：

实现方法 运行时间（s） 峰值性能占比（%）
Python 25,552.48 0.00
Java 2,372.68 0.01
C 542.67 0.03
并行循环 69.80 0.24
并行分治 3.80 4.33
加入向量化 1.10 14.96
加入AVX内联 0.41 40.45

上表的每一步操作都对原始的Python代码进行了改良。其中，峰值性能占比是运行代码时的GFLOPS相对计算机的峰值GFLOPS的比例，反映了对应策略对计算机性能的利用率。

从上表可以看到，除了编程语言的选择可以使得代码具有更高的性能，对硬件特性的充分利用同样大幅度加快了程序的运行。因此，更加底层的语言的性能工程中可以获得更大的潜在收益。

而对于软件膨胀，一方面是由于程序代码本身的效能低下，另一方面是没有根据底层架构定制代码。此外，软件膨胀还可能来自于开发策略的选择。

比如缩用（reduction）的策略，简单来说就是将一个泛用于一类问题的程序或代码直接用于解决某一个小型的子问题。最大的问题是这样的策略可能会链式进行，这样会使整体效率受到各部分冗余乘算规模的影响。然而，相对于缩用的策略，专门针对特定问题进行软件开发，将会极大增加开发成本和风险。事实上，更高效的代码往往会更加复杂。

抽象地说，软件性能工程可以看作是一个涉及单个循环的简单过程：

  1. 测试程序A的性能。
  2. 对程序A进行修改，以产生一个期望更优的程序A’。
  3. 测试程序A’的性能。
  4. 如果A’优于A，则设置A=A’。
  5. 如果A仍然不够快，返回2。

但是如今的软件系统通常非常复杂，测量需要重复多次，以确保程序的一个版本优于另一个版本。

随着硬件变得越来越专业化和异构化，编写高性能的代码将变得越来越困难，但这对于软件的性能提升是十分必要的。

算法

算法的改进可以使得软件性能获得大幅提升，有时甚至远远超过了处理器速度提高带来的性能提升。但是算法设计依赖于人类的创新性，因此很难预测其发展趋势。

以网络最大流算法的发展为例，虽然在过去20年内并没有更优的算法改善这个问题，但在之前的38年里，最佳算法的性能收益与摩尔定律带来的硬件性能收益几乎持平。综上，我们可以得到如下几个结论：

  • 特定的算法问题的发展是不均衡和不连续的
  • 算法革新的收益与摩尔定律的收益相当
  • 任何问题的算法优化空间都是有上限的

然而，由于这个例子关注的是一个众所周知的问题，所以它忽略了算法在性能工程中加快计算速度的另一个关键方面：为新问题提供高效的解决方案。

因此，尽管对旧问题的研究仍可能会产生边际收益，但算法的大部分进展将来自三个方面：

  • 进军新的问题领域：诸如机器学习、社交网络、游戏理论、视频编码等领域在近些年可能刚刚出现或正在进入发展阶段，新出现的领域正在不断产生对新算法的需求。许多公司因为优秀的算法在市场上取得了竞争优势，许多科学研究的成功也离不开算法的设计。

  • 解决可伸缩性问题：如果要从海量数据（如兆兆级）储存中，找到这些数据的中位数，如果使用传统的读写方式，将会造成大量的读写和计算开销。然而，如果采用取样的方式（如抽取百万级的样本）计算其中位数，这样的计算结果具有很好的代表性，同时大幅减小了问题的复杂度。

  • 定制算法以利用现代硬件：定制一个算法来利用现代硬件可以使其速度更快。目前的大多数算法设计都使用的是串行随机访问机器模型，它假设处理器一次只能做一个操作，并且访问内存的任何部分的成本是相同的。这种算法使用现代硬件往往效率低下，因为它们没有充分利用机器的许多并行处理核心和向量单元，每个时钟周期可以执行许多操作，而且它们不能利用缓存，缓存可以将数据访问速度提高两个数量级。

尽管算法研究已经为现代计算机的显著特征开发了数学模型，如并行和向量处理和缓存层次结构，但算法和实现之间仍然存在较大的差距。问题在于，每个数学模型只倾向于解决某一个方面，然而，为现代计算机定制算法需要理解所有模型。此外，为了尽可能提高性能，一些可能导致可变性和不可预测性的硬件特性（如同步多线程、动态电压和频率缩放、直接映射缓存和各种有特殊用途的指令）实际上更难定制算法硬件。

一种可能的解决方案是自动调优（autotune），该方法搜索可能实现的参数化空间，以找到最快的实现，并可以通过机器学习方法实现更优的效果。但这样的方法会导致巨大的前期成本，并且使得优化后的程序变得难以理解，不利于算法设计者和硬件架构师的深度协作。

硬件架构

在后摩尔时代，硬件架构师将需要采取与之前相反的策略，致力于硬件的流线型化：使用更少的晶体管和更少的硅面积来实现硬件功能，使得具有充分并行性的应用程序将获得最大的好处。

事实表明，微处理器的时钟频率在经过了若干年的增长之后，如今已趋于稳定，而其并行性能相较于串行性能的提升速度明显更快。

除了并行性之外，局部性也是硬件架构优化的重点。

程序的局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。
局部性原理又表现为：时间局部性和空间局部性。
时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。
空间局部性是指一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。
因此，从存储设备读取的数据应在短时内重复使用，而不是重复读写。

对于局部性较小的应用程序，并行性提高会导致芯片外内存的流量成倍增加并且最终超过其通道到内存的带宽，致使应用程序被内存读写阻塞。然而，对于具有良好局部性的应用程序，随着并行性的增加，芯片外内存流量的增长得要慢得多，这使得所有芯片的计算引擎能够在不空转的情况下完成工作。多数应用程序域都包含了大量的局部性和并行性。

硬件简化可以通过其他方式利用本地性。如果应用程序拥有良好的局部性，芯片内部的互连可以变得更简单，消耗更少的功率和面积。

使得处理器提高并行能力的策略包括：处理器简化（Processor Simplification）和领域专门化（Domain Specialization）。

  • 处理器简化：使用含有更少晶体管的核心，并使用分支预测执行（Speculative Execution）等硬件技术进行优化。在相同面积的芯片上，简化程度越高的芯片就可以使用越多的核心数，前提是应用程序拥有足够的并行性，使得多余的核保持繁忙。
  • 领域专门化：为应用程序领域定制的硬件可以更加精简，使用更少的晶体管，使应用程序的运行速度可以快数十到数百倍。如GPU就是针对图形处理专门定制的芯片，尽其时钟周期往往比起CPU更慢，但由于其拥有更强的并行化能力，它的图形处理能力会更加强大。一些为专门的领域定制的设备也在其他领域有用处，如GPU也被广泛应用到了线性代数、深度学习等领域。在后摩尔时代，我们期望拥有更多专门针对不同应用领域的各种硬件设备。

大型系统组件

在后摩尔时代，性能工程、算法的开发和硬件流线化在大型系统组件中将是最有效的。

大型系统组件：指可重用的大型软件（通常有超过100万行代码，如Web浏览器、数据库系统、操作系统、GPU编译器、磁盘存储系统等），或复杂性相当的硬件（如微处理器等），或类似的大型软硬件联合组件。

将代码分解成模块，并将实现隐藏在接口后面，从而使开发速度更快，软件也更健壮，并且各个模块之间互不交叉，使得其开发可以并行进行。同样的，硬件模块可以各自进行内部重构而不影响应用程序编程接口（Application Programming
Interfaces，APIs）。

约靠近底层、对系统影响越大的模块，对整体性能的提升越大。但影响许多模块的大规模重构有较高的风险和成本。如对于微处理器，制造商通常在不更改指令集体系结构（Instruction Set Architecture，ISA）的情况下，通过内部重构来提高性能，以便旧软件继续正常运行。

总结

在后摩尔时代，软件的性能工程、算法的开发和硬件的简化可以继续提高计算机应用程序的运行速度。然而，与底部优化的收益不同，顶部的收益将是随机的、不均匀的、零星的，而且存在边际效应。其中，大型系统组件可以在顶部的性能提升中获得最佳收益，并最大限度地减少外部影响。尽管许多新兴的技术（如超导计算、3D堆叠等）在底层优化具有长久投资价值，但在短期内，大多数应用程序更有希望在底层获得性能提升。