前情提要

上两篇专栏“溯游从之，道阻且长”和“溯洄从之，宛在水中央”，分别讲了硬件演化过程受阻于半导体工艺微缩过程中依次出现的内存墙、功耗墙和外设墙等三个物理限制，软件演化过程中指令式、函数式和逻辑式等三条发展路线。计算机体系结构的世界已由软件（应用层、编程语言层）和硬件（微架构层、RTL层）搭好了舞台，下面该编程模型开始表演了。

本节我们将打卡cache与暂存器、超标量处理器指令乱序执行、编译器指令重排序、多核处理器缓存连贯性模型、RDMA语义等设计，回溯编程模型如何作为中间层解决两笔写的保序需求。为了让旅程不那么硬核，我们将以日常生活中“朋友圈点赞”的例子作为这些编程模型的设计动机。在旅程的结尾，我们将给编程模型的“三元悖论”一个合乎理性的解释。希望这趟旅程能帮助各位对原本浑浊的体系结构，形成清晰的、面向编程模型的层次化认知。须知，“狭义的编程模型是应用层到微架构层的层间契约，规定了上层的哪些行为合法，以及这些行为在下层的执行机制。”

05 三元悖论

上一篇4.1节将结构化程序设计和抽象数据类型称为“润物细无声”的设计，因为它们“又通用，又易用，还不会让应用在处理器上的损失过多性能，彻底重构了程序员的思维方式”。反过来说，如今我们会感知到、需要做出取舍的编程模型，一定是无法同时做到应用范围广（通用）、开发效率高（易用）、运行效率高（性能高）的。这就是“编程模型的三元悖论”（Trillema of Programming Models）。

图 1 本节标题“三元悖论”模仿宏观经济学的蒙代尔不可能之三角 (Mundellian Trilemma)。
易用性、通用性和高性能三个指标对应的三条边围成的设计空间中，每个编程模型对应其中的一个点。
一个点越靠近某条边，则该模型相应的指标越优秀。

图1以“不可能之三角”形象地展示了三元悖论。如果我们要在GPU上编写一个卷积神经网络推理的应用，我们可以有以下三个选择：CUDA高性能且通用性好，但非常难开发；以NumPy为代表的高层次函数库，易用且通用，但性能低下；以TensorFlow为代表的定制化深度学习框架，高性能且易用，但兼容性差（只能用来做深度学习，不像NumPy、CUDA还能做数值计算、信号分析等应用）。类似的例子还有很多。我们可以先由此归纳，如果一个应用有多种编程模型可选，那这些编程模型最多只能同时实现两个指标，而放弃另一个指标。

纸上得来终觉浅。要真正理解编程模型三元悖论的来龙去脉，我们还是需要回溯硬件-编程模型-软件的协同演化历程。为了避免各位迷失在编程模型（看似）无序变化的湍流之中，本节将沿着硬件的“三堵高墙”，探究各种编程模型如何满足指令式编程语言的一个重要需求：保持两个赋值语句的先后顺序。

指令式编程语言中的“写内存操作”（即赋值语句）的执行顺序是一个非常棘手的问题。为了让不同背景的读者们都能体会到它的复杂性，本节用日常生活可经历的“朋友圈点赞”的例子，为5.1节至5.4节中的多种编程模型提供设计动机。

想象一对男女朋友。女生发了一条朋友圈，召唤男生来点赞。理想情况如图 2所示。男生点赞后，给女生发消息“点赞啦~”。女生收到消息后，去刷新一下朋友圈，观察到了男生点赞的状态。一切安好。

这里男生和女生可类比为两个线程A和B。男生点赞和发消息这两个事件对应线程A对存储器（可类比微信的服务器）的两笔写操作，而女生收到消息和读朋友圈状态对应线程B对存储器的两笔读操作。

图 2 横虚线是时间线。双向箭头的两个端点对应3个事件的起点和终点。斜向虚线表示了状态的传播。
正常的写传播顺序：“赞+1”的数据之后是“点赞啦”的消息。男生和女生看到的顺序一致。

不太理想的情况如图3所示。也许朋友圈出了点故障，女生看到“点赞啦”消息，早于她能观察到“赞+1”的时间。从女生的视角来看，男生虽然告诉她“点赞啦”，但是男生并没有点赞。男生言行不一致（“骗谁呢”）。类似的，两个线程间观察到不一致的内存操作顺序也可能会导致各种bug。有些不一致引起的后果可是非常严重的啊。

图 3 不正常的写传播顺序：男生和女生体验到了不同的“赞+1”和“点赞啦”的顺序

“赞+1”和“点赞啦”两笔写操作，可以抽象为“写数据”和“写标记”。类似图3的顺序不一致造成的困扰，在程序设计中随处可见。例如，一个生产者线程和一个消费者线程，通过一个消息队列进行通信。消息队列需要维护两个标记：队首标记和队尾标记。生产者将数据放到队尾，然后更新队尾标记；消费者从队首读取数据。为了确保队列非空，消费者线程在读数据之前，需要比较队首标记和队尾标记。假设初始时队列为空。生产者（图3男生）依次发起了写数据（写赞+1）和写队尾标记（写“点赞啦”消息）的请求。之后，如果消费者（图3女生）在能读到数据（能看到赞+1）之前，先读到了更新后的队尾标记（看到“点赞了”消息），那么消费者线程将错误地读到队列中尚未被更新的数据（未能读到赞+1）。

理解了两个线程为什么要观察到一致的“写数据-写标记”顺序，我们就可以开始探索“三堵高墙”下哪些硬件设计会导致“写数据-写标记”发生乱序，以及编程模型是如何演化以解决新硬件机制带来的乱序难题。

硬件设计的起点是内存墙（1985年）之前的冯·诺伊曼架构（3.1节）。“应用程序的执行状态和数据保存在一个处理器内的有限数量的寄存器、以及外部的存储器中。处理器中的寄存器仅仅保存应用程序执行的中间状态。所有的数据最终都要体现在存储器中。”

这里“单一处理器-单一存储器”的硬件设计下，多个线程时分复用地在一个处理器上交替执行，所有线程的所有写操作都可以按照处理器向存储器发起请求的时间先后进行排序（全序集），而且所有线程都能观察到完全一致的写顺序，如图4所示。这一模型下，图3中两个线程观察到不一致的写顺序的情况不会发生。

图 4 “单一处理器-单一存储器”模型下“写数据-写标记”在处理器和存储器都一致

5.1 指令乱序执行：乱序不要怕，硬件来兜底

1985年后内存墙问题变得越来越严重。处理器每一次对外部DRAM存储器的访问都需要花费数十到数百个周期等待存储器的响应。为此架构层引入了高速缓存（Cache）和内存级并行性来缓解内存墙问题（3.2节）。

我们继续用朋友圈点赞的例子阐释这些硬件机制。为了贴合内存墙出现的时代，我们也同样穿越回1990年代，家里只有一台PC可以上网、只有博客没有即时通信软件的时代。故事里的男生和女生只能时分复用地共用一台PC，一人下机后另一人才能上机；类似于90年代单核处理器执行两个线程时，通过线程切换来实现多线程并发。

图 5 内存墙时代乱序执行+cache维持了“单一处理器-单一存储器”的幻象，但硬件设计稍有不慎就会出现乱序带来的bug。

Cache将处理器可能会频繁使用的数据放在处理器芯片上的SRAM里，从而减少片外DRAM的访问开销。类似的，1990年代的男生和女生可以在电脑上贴便签纸来通信，减少去服务器读写消息而花费的ADSL流量费用。图5中男生就在便签纸上给女生留言“点赞啦”。当男生下机，女生上机（线程切换），女生看到留言就可以去博客查询点赞状态。

Cache完全由硬件维护，对于上层的编译器、编程语言而言几乎是一个完全透明的存在，即它们通常无需干预Cache怎么缓存数据的。所以Cache维持了单一存储器的幻象。

但是，从硬件实现上看，层次化的Cache和DRAM是可以并行处理多个存储器访问请求的多个存储体。为了进一步缓解内存墙的压力，处理器可以开发应用中的内存级并行性，使得处理器可以同时存在多笔在途的存储器访问请求。这样虽然不能减少单笔存储器访问请求的处理延迟，但是可以通过重叠多笔存储器访问请求，提高存储系统的实际带宽。

为了提供内存级并行性，处理器引入了多线程并发执行和指令乱序执行。图5中的“线程切换”就是让两个线程（男生和女生）时分复用一个处理器，以发起尽量多的存储器访问请求。

指令乱序执行则是由处理器在执行一个线程时，打乱线程内没有数据依赖关系的指令的执行顺序。例如，当访存指令在cache 中未命中，等待 DRAM 中的数据时，若后续访存指令在 cache 中命中，可以先完成后续访存指令。

指令乱序执行会让处理器硬件设计变得非常复杂。通常处理器中至少要加入renaming buffer和reservation station，其中通过大量的associative tag-matching硬件发现无依赖关系的指令。

图5中男生赞+1的操作需要通过ADSL访问远端服务器（访问芯片外DRAM主存），延迟很大；当男生发现之后的写“点赞啦”消息可以直接写在便签纸上（片上Cache命中），就可以不等赞+1完成，先写便签纸。

这里就可能引入一个乱序带来的bug。如果男生写完便签纸（“写标记”），但赞+1的“写数据”还没有真正写到存储器时，处理器发生了线程切换；女生上机，就会出现顺序不一致bug：女生在便签纸上看到“点赞啦”标记，但未能在服务器查到点赞数据。

为了解决这种bug，架构师们设计了更多复杂的硬件机制。一种解决方法是让处理器在处理每一笔存储器读请求时，去检查所有在途的（比如在store unit, store buffer, MSHR等等）写请求的地址；一旦发现有相同地址的写请求，就将写的数据直接转发给读。类比图5中，女生查询点赞数据时，需要检查从PC到服务器的通路上有没有尚未完成的“写数据”。这些associative tag-matching硬件电路的面积和功耗都非常惊人。

乱序执行需要发现没有依赖关系的指令。发现无依赖关系的指令这一步骤，既可以完全使用硬件机制，在超标量处理器架构（superscalar architecture）执行指令时动态完成（前面提到的那些硬件设计）；又可以使用编译器，在编译时静态开发指令级并行，即 VLIW 体系结构（Very-Long-Instruction-Word architecture）。对于通用处理器而言，由于编译器静态分析难以发掘出足够多的无依赖关系指令，VLIW 架构的性能远逊于超标量架构。因为编译器带来的性能损失，远大于完全由硬件实现带来的面积和功耗开销。所以通用处理器的乱序多发射机制最终舍弃了VLIW，完全由硬件来实现。与cache类似，指令乱序执行完全在微架构层实现，对编译器、编程语言完全透明。

关于指令乱序执行的详细硬件机制，参见《计算机体系结构：量化研究方法》3.5节对Tomasulo算法的分析。Tomasulo算法是1960年代为IBM 360/91设计的，设计动机是让不同类型的指令序列在IBM360上得到类似的、可预期的性能。但直到1990年代，内存墙问题出现，cache成为所有高性能处理器必备机制后，为了解决cache行缺失导致的不定长访存延迟时，Tomasulo算法才被重新挖掘出来成为超标量处理器架构的基石。

5.2 指令重排序/暂存器：谁乱序，谁治理

指令乱序执行将延迟较长的指令挂起，尤其是发生了 cache 未命中的访存指令，先执行之后的指令。虽然超标量处理器的指令重排序缓存（reorder buffer）可以对几十条指令进行乱序执行（最新的Apple M1 reorder buffer可以对630条指令乱序，可谓微架构工程奇观了），但更大范围内的处理器指令乱序执行会导致硬件设计的复杂度急剧上升，边际成本很快就会超过边际效用。因此，大范围（上千条）指令间的乱序，只能依靠编译器在编译期的静态分析完成。

图 6  编译器指令重排序会也会导致两次写请求乱序。将变量y声明为volatile限定词后，
编译器不会将任何对y的赋值语句与其它的存储器读写语句乱序，从而保持了两次写请求的顺序。

内存墙问题出现后，存储器访问指令的执行时间远大于其它指令。因此编译器通常会在一次存储器读指令之后，将与该次读的结果有依赖关系的指令向后移动，这就是编译器指令重排序（Compiler Instruction Reordering）。回到朋友圈点赞的例子。图6左侧用指令式编程语言的方式简单描述了线程1（男生）和线程2（女生）的流程。假设点赞时，线程1要先去存储器读取当前赞数，再将+1后的赞数写到存储器。由于读赞数延迟可能很长，编译器通常（gcc -O2就会做这个优化）会将写“点赞啦”消息y的指令提前到写“点赞数”数据x的指令之前。此时处理器执行两次写请求也会乱序，从而导致了顺序不一致的bug。

为了避免编译器指令重排序产生错误的结果，编程模型需要进一步的演化。由于不同的应用对是否要进行特定指令重排序的需求完全不同，难以用一套编译器静态分析的方法囊括，因此应用开发者需要决定是否要对特定指令进行重排序。

应用开发者可以在定义消息变量y时添加volatile限定词，避免了读写y相关的指令被编译器重排序。但是，volatile的加入也会阻止了很多本来不会造成错误的重排序，可能会造成性能的损失。

Cache、多线程并发执行、指令乱序执行和编译器重排序，都是在内存墙时代通过实践检验后广泛采用的设计。但还有非常多的设计，因为没有找到合适的使用方法，而被埋没在历史之中。

例如，使用完全由程序员控制的暂存器（scrachpad），按需缓存数据，也可以减少对 DRAM 的访问。图7对比了暂存器与cache的异同。由于不需要cache中复杂的微架构机制，暂存器在执行相同的数据流时，性能和功耗都要优于cache。

图 7 通用处理器中cache与scratchpad的对比。它们都是与DRAM主存不同的存储体，通常读写速度比主存要快。
但cache与主存在同一个地址空间，对编程模型透明；而scratchpad与主存分属不同的地址空间，需要由应用开发者或者编译器负责使用

在内存墙时期，新设计都努力避免破坏冯·诺伊曼架构的“单一处理器+单一存储器”的幻象。Cache在原有DRAM的基础上增加了更快的SRAM存储器：这些SRAM只缓存主存DRAM中的拷贝，维持了单一存储器的假象。

但是，暂存器会引入具有不同行为的地址空间，破坏冯·诺伊曼架构单一存储器的幻象。而且，暂存器和主存间的存储器访问序关系将更加棘手。图5中的“便签纸”其实更像暂存器而不是cache，因为图5的“服务器”主存中没有“便签纸”中的数据。不过，图5中的bug对于cache和暂存器都成立。只是暂存器会带来更多的bug。

暂存器要等到十几年后的 GPU 中，随着功耗成为决定性能的主要因素，随着CUDA用shared memory抽象打破单一存储器幻象，才得到了大规模的使用。

5.3 多核处理器：合法乱序是程序员应尽的义务

2005年后出现的“功耗墙”难题，虽然没有停下摩尔定律的脚步，但却摧毁了冯·诺伊曼架构上的单一处理器-单一存储器的抽象。由于片上多核处理器（Chip Multi-Processor）和异构架构逐渐成为主流的硬件设计方法（3.3节），应用开发者被迫直面并行编程模型和异构编程模型。

并行编程模型打破了 “单一处理器”的幻象：一个芯片上多个处理器核需要程序提供线程级并行性，同时单个处理器核内的SIMD向量运算单元需要程序提供数据级并行性。这些需求都对应用开发者提出了极高的要求。

功耗墙之前，并行编程是少数超级计算机程序员才会接触到的rocket science；功耗墙之后，几乎所有程序员都要面临并行编程的挑战。如何降低并行应用开发的难度变成了编程模型研究的核心问题。

异构编程模型打破了 “单一存储器”的幻象：CPU-GPU异构架构首次击碎了处理器面对的唯一的地址空间，应用开发者必须考虑如何让数据在不同的存储体或地址空间之间高效迁移。内存墙时代，暂存器遇到的多地址空间下对程序员友好的数据迁移API设计、虚拟内存重映射等难题，在CPU-GPU异构架构上通过定制化的方式得到了部分解决。这部分内容我们将在专栏第6篇再谈。

多个并行线程和多个并列的存储体间的相互作用使得编程模型愈加复杂性。例如，单芯片多核处理器的出现，结合之前的片上多级cache存储系统，造成芯片上的不同处理器访问相同地址上的数据时，由于不同的cache中数据更新的时机不一致，以至于不同处理器可能会看到不一致的结果。这类问题被统称为cache连贯性模型（cache consistency model）问题。该问题在之后极大地影响了处理器微架构、架构层、编译器和编程语言的设计。

本小节我们继续朋友圈点赞的故事，阐释x86处理器架构的写全序模型（Total-Store Ordering, TSO），RISC-V处理器架构和C++11的释放写模型（Release consistency）。

时间来到2005年后，我们的男女主人公终于把PC换成了手机。两人各用一部手机，类比片上多核处理器上，两个线程在两个核上并行执行。为了提高用户体验，手机中会缓存部分服务器中的数据，因此一部手机可以类比多核处理器中一个核的私有cache。连贯性模型要解决的就是每个手机在每个时间点可以看到什么状态的问题。

图8(a)是不考虑连贯性模型时一种出bug场景：男生写的状态在服务器及女生手机间传播的没有任何时序约束时，两人会看到不一致的写顺序。

(a)   手机类比各个处理器核私有的cache，男生和女生线程各绑定到一个处理器核。
左图是不约定连贯性模型时，男生线程即使没有指令乱序执行和指令重排序（即男生线程的两笔写之间完全没有交叠），
也会因为女生所绑定的处理器核的cache中缓存的旧的点赞数而发生顺序不一致。

（b）写全序模型的一种实现方法，使用写广播协议（write-broadcast）实现cache一致性的写串行化（write-serialization），
即男生线程的写数据（点赞）要确保女生手机收到更新后的数据之后，写数据指令才算完成，之后才可以继续执行写标记（发送消息）指令。
此外还可以采用写失效协议（write-invalidation）实现写串行化。
图 8 缓存连贯性模型为存储器请求的时序提供了约束

连贯性模型的关键问题是解决如何为存储器访问请求添加时序约束。图8(b)展示了一种添加约束的方法：x86处理器架构采用的写全序模型。正如其名，若多核处理器上来自不同核的所有写操作构成集合W，写全序要求的所有核都能观察到一致的W上的全序关系（total ordering）。图8(b)中写数据指令，要等待所有核的私有缓存的拷贝全部得到更新后才算完成；写标记指令，要等待写数据指令完成后才能开始。这样就确保了写全序。

写全序模型将维持两笔写顺序的义务分给了微架构层。这会导致微架构层硬件机制变得非常复杂。图8(b)中一条指令要等待所有cache的更新或失效的确认信号，这极大地加长了写指令所需的处理器时钟周期数。为了在写全序模型下提高写指令的性能，x86处理器架构的cache中又加入了推测执行机制：不需等待其它cache失效的确认信号，处理器核可以假设写指令完成，以推断的方式继续执行后续指令；一旦发现其它cache因为这笔写失效，则该处理器核失效后续推测执行的指令。

可见，多核处理器实现高性能写全序模型需要极其复杂的硬件机制。因此同等半导体工艺下，x86架构的单个芯片的核心数量远远小于采用更松弛连贯性模型的ARMv8, RISC-V等架构。

写全序模型中，虽然微架构层承担了保持写-写顺序的责任，但程序员也不能当甩手掌柜。写全序模型中一个线程的两笔先后执行的写-读存储器请求可能会被乱序，因此程序员应当在需要保序的写-读指令间插入fence指令。

考虑到程序员已经承担了部分保序责任，松弛的连贯性模型为了提高多核处理器的可扩展性（即单个芯片上的核心数量），索性继续把更多的责任交给了程序员。早期的松弛连贯性模型，如IBM PowerPC架构的weak ordering, SPARC架构的partial store ordering等，始终未能找到让程序员容易理解的编程模型。直到C++11标准, ARMv8架构和RISC-V架构共同确认了释放写模型，CPU上才有了对程序员相对友好的连贯性模型。

图9中展示了释放写模型下，程序员需要承担的责任。程序员要将源代码中的所有内存读写语义分为两类。代码中的“写标记”赋值语句被标注为release语义，“读标记”语句被标注为acquire语义。释放写模型规定，如果一个线程A的acquire指令能观察到另一个线程B的release指令的效果，则线程A在acquire之后的指令，都可以观察到线程B在release之前的指令。图9中将读写消息的语句设为acquire-release对后，女生线程一旦acquire读到更新的消息，则一定可以读到更新后的点赞数。

图 9 释放写模型（release consistency）中区分了普通写和释放写（store release），普通读和获取读（load acquire）。
左侧中用C++11的语法改写了“写数据-写标记”程序。
右侧则给出了多核处理器上实现acquire-release语义的一种方法：store-release会向主存储器写回私有cache中缓存的所有写的状态；
load-acquire会失效私有cache中缓存的所有状态（赞=x，表示手机中不再缓存点赞数），
之后读取点赞数时将从服务器上获得男生更新后的状态。

将片上多核处理器缓存连贯性机制以acquire-release的抽象直接开放给对应用开发者，可以充分释放特定应用场景下硬件的性能潜力。同时，微架构层和架构层的设计也被简化，在获得更好性能（处理器执行图9中“点赞”指令比图8(b)测所需的步骤要少很多）的同时，可以减少复杂微架构的面积和功耗开销。当然，释放写模型一方面学习曲线陡峭，另一方面开发成本也很高：当应用开发者直面硬件机制的复杂性时，需要大量的调试和验证才能确保现实中的应用正确运行。

5.4  RDMA定制原语：以魔法打败魔法

2015年外设墙出现后，网络和硬盘的带宽增长速度远大于CPU-DRAM间带宽的增长速度。工业界和学术界开始尝试将越来越多原本CPU的任务，交给网卡和硬盘控制器完成。

而对于我们之前朋友圈点赞的故事，外设墙墙的出现也带来了新的设计空间。例如，目前高性能计算中通常采用Infiniband网络中，提供了RDMA（Remote Direct Memory Access，远程直接内存访问）。RDMA通过让本地CPU通过支持RDMA的网卡，直接读写远端内存，从而绕过远端CPU，从而在一定程度上克服了外设墙墙的阻碍。

如果男生直接用RDMA写给女生点赞+发消息，使用内存读写语义，需要先读当前点赞数，然后写更新后的点赞数，然后待收到上一笔写的确认后，再写消息。总体而言，完成此操作将需要至少4次往返网络，对于当今最快的网络也至少需要4微秒。而且，这个延迟已经逼近受到光电等信号在介质中传输的物理极限，很难再随着技术的进步降低了。

为了解决网络延迟对RDMA的性能影响，我们可以增加更复杂的RDMA语义，减少请求折返的次数。对于点赞数+1的需求，可以在RDMA网卡中增加atomic_add原语；而对于更复杂的单生产者-单消费者消息队列的插入元素操作，一种优化方式是在RDMA中加入“原子追加”的原语，使得生产者所在处理器用一个数据包就可以对远端的消费者完成插入元素的操作。

当然，这些定制化的编程模型需要在架构层修改芯片的设计，即所谓的领域定制架构（Domain-Specific Architecture）。只有当DSA的定制化功能使用频次足够高、收益足够大时，工业界才会量产这些芯片。截至2021年，学术界和工业界对于提供RDMA的DPU到底需要支持哪些定制化原语尚未达成共识。

One more thing， 日常生活中我们解决“朋友圈点赞”问题的方法提供了编程模型之外的一种思路：改变用户习惯，从而改变软件约束。日常生活中女生不会因为没及时看到“赞+1”而焦虑，因为等一下再刷新，eventually会看到的。用户“等一下刷新”这个习惯，就是因为许多分布式系统使用最终一致性模型（eventual consistency）而养成的。

这里的关键在于“朋友圈点赞”“刷论坛留言”等需求的时效性不重要，因此可以采用最弱的最终一致性模型，提高系统对用户行为的响应速度。相反，对于银行转账这种时效性要求很强的场景（想象一下银行app告诉你转账成功，但对方告诉你没收到钱，你的焦虑感），分布式系统则会采用可线性化（Linearizability）一致性保障。但这样的代价是你每次转账后要等待一会，银行app才会告诉你转账完成（有点类似图8(b)中男生线程写数据指令需要更长的时间）。

因此，虽然我们如今有了如此繁杂的编程模型来解决各种问题，但任何系统的设计者的首要任务永远是分析目标场景的需求，恰到好处地在编程模型工具箱中选择合适的工具，既能解决问题，又不会过度设计。

5.5 小结：编程模型，一种权责划分的实践

下表中列举了之前提到的所有技术，从它们的优点和缺点的描述中我们可以看到三元悖论的影子。

所有的技术点都是为了解决硬件演化中的实际问题而被发明的；并且一个技术点带来的新问题，需要发明更多的新技术来解决。Cache是为了掩藏DRAM的访问延迟；指令乱序执行、编译器指令重排序和VLIW技术，都是为了解决cache-DRAM多存储体架构下存储器访问请求的不确定延迟；暂存器是为了解决cache的复杂硬件设计带来的额外面积和功耗开销；缓存连贯性模型是为了解决片上多核处理器上多个cache间数据拷贝的一致性……

图10粗略展示了冯诺依曼架构在遇到硬件的“三堵高墙”后的演化关键节点。整体而言，硬件架构在向着并行化、定制化和异构化的方向发展。在内存墙之前“单一处理器-单一存储器”的时代，程序员大多使用汇编指令，直面各种硬件机制（“在计算机诞生之初，所有的从业者都是‘斜杠青年’：每个人都需要即懂软件又懂硬件。”）但内存墙时代之后，cache、超标量等复杂硬件机制的加入后，人们已经很难说清楚两条写指令的执行顺序在处理器各种情况下的执行细节。于是作为中间层的编程模型就应运而生。引入新的中间层的目的，就是要掩盖其下方中间层的复杂性。

图 10 冯·诺依曼架构遇到三堵高墙后，向着硬件并行化、定制化、分布式的方向演化

第2节中，我们根据开发过程中开发者主要跟哪个中间层打交道，我们将计算产业中的人大致分为四组：硬件开发者、架构设计师、编译设计师、应用开发者。这正是编程模型的三元悖论的来源，如图11所示。按照由谁负责掩盖复杂的硬件机制，可以归纳出三种编程模型的设计路线。

首先，有些硬件机制只需要交给架构设计师考虑，一般不需要编译器的干预。例如，当今流行的DSA，通常都是由架构设计师提供一组简单的API或者专用指令，供上层的编译器和应用开发者直接调用。这些编程模型牺牲了通用性。

然后，有些硬件机制可以交由编译设计师处理，不需要让应用开发者了解。例如，CPU中成百上千个寄存器，都可以由编译器在静态分析中自动完成分配；静态分析确保正确性后，编译器可以对访存指令进行重排序。这些编程模型牺牲了目标硬件机制的性能潜力，因为编译器的静态分析很难充分把握软件在硬件上的运行时状态。

最后，很多硬件机制的性能潜力，必须由程序员根据应用的需求编写程序，才能充分开发。例如，多线程处理器需要程序员使用并行编程语言编写程序；暂存器需要程序员手动管理多个地址空间之间的数据迁移。这些编程模型牺牲了易用性，因为程序员被迫直面底层硬件机制。

图 11 编程模型的三元悖论，来源于硬件设计的复杂性难以在微架构层以下掩藏时，在向上层暴露时的三种选择。
若硬件机制可以被微架构层掩藏（例如cache和指令乱序执行），我们称它对编程模型透明。

有趣的是，上面分析编程模型三条设计路线时，各个中间层对复杂性的承担似乎是一种责任，是一只“看不见的手”的各个中间层间“分锅”。但历史上编程模型的发展过程，是硬件开发者、架构师、编译器、程序员争先恐后地去处理新出现的硬件机制。所有人都将处理复杂性视为一种权力。如今的编程模型是各方相互角力达到平衡的结果。

毕竟权力越大，责任越大（With great power comes great responsibility）。

番外5：当我谈类比时，我谈些什么？

道生一，一生二，二生三，三生万物。

—— 老子，《道德经》42章

数字1代表万物之源，数字2代表物质。数字3是一个“理想数”，因为它包括起点、中间和终点；并且3是用来确定一个平面所需的最少点数。三角形被认为是阿波罗的符号。

—— Wikipedia: 毕达哥拉斯学派

我们的眼光似乎必须透过现象……因此，我们的考察是语法性的考察。这种考察通过清除误解来澄清我们的问题……导致这类误解的一个主要原因是，我们语言的不同区域的表达形式之间有某些类似之处。

—— 维特根斯坦，《哲学研究》90节

在回答“李约瑟难题”（为什么现代科学没有发生在近代中国？）时，一种常见的解释是“西方文化注重演绎，东方文化注重类比。文化类型的差异，形成了逻辑类型的差异。”的确，《周易》《道德经》中几乎全书都在用类比说理。加之近代中国在当代中文语境代表了落后挨打，于是当代中文语境也将类比视为落后于演绎的说理方式，甚至将类比贬为一种不讲道理的修辞学诡计。

但是，西方文化（特指西欧）真的不使用类比吗？遥远的毕达哥拉斯学派将数字视为神谕，用数字与现实世界的类比作为理解世界的本原。即便到了科学革命时代，莱布尼茨在思索虚无0的存在性时，借鉴《周易》的卦象图，将阴爻“- -”视为0，阳爻“一”视为1，发明了二进制。在《单子论》中，莱布尼茨用0和1的二进制类比论证创世论，因为“所有数字可以都由一和无表示”。

抛开这些神学片段，《单子论》的“自虚无生出万物，凭一足以”这句话、以及 “道生一，一生二，二生三，三生万物”，都可以类比到皮亚诺公理系统的第五公理：数学归纳法。用非形式化的语言复习一下数学归纳法：“任意关于自然数的命题，如果证明：它对自然数0是真的，且假定它对自然数a为真时，可以证明对a+1也真。那么，命题对所有自然数都真。”数学归纳法是自然数的基础，而对自然数的形式化研究催生了一阶逻辑和集合论。

为何两千多年前的《周易》《道德经》会如同神谕般地揭示了自然数的基本性质？这要从数学是发现还是发明谈起。理工科从业者通常将数学视为一种先验的真理体系。数学不是经验科学，而是一种人类对世界本质的发现。因此数学的真实性是不用怀疑的。即使计算结果与经验相悖，那一般是前提出错。

然而，稍微反思一下数学史，就会发现数学其实是对日常经验的描述，是一种语言。例如，欧式几何曾被柏拉图主义者视为先验的“理念世界”的代表，是绝对的真理（柏拉图学园门楣上刻着“不懂几何学者不得入内”）。但19世纪罗巴切夫斯基、黎曼等人通过选择不同于欧式几何平行共设的公理，创立了全新的非欧几何。非欧几何的“发明”，实际上是人类为了描述新经验而创造的新语言。大航海时代“地球是圆的”这一事实，越来越深刻地对人类的实践产生影响。人类的直觉不再靠得住（从北京飞到芝加哥，是走太平洋还是走北极最短？）。描述球面上的经验这一需求促使人类放弃平行公设，发明新的公理。

至于数学到底是发现还是发明这个问题，实际是在问语言是发现还是发明。语言中，用来描述经验的概念是发明，概念间相互作用提炼语法规则是发现。数学作为人类的一种语言，需要人类发明公理描述日常经验；确定一组公理后再通过发现定理，从日常向远方跋涉。从这个视角看，人类从日常计数的经验发明了皮亚诺公理系统和一阶逻辑，然后从一阶逻辑推理出经验之外的哥德尔不完备性定理。

有效的类比可以在不同语言间建立桥梁。日常语言、数学语言、编程语言等等，它们是人类的思维对经验的不同表达方式。因此不同语言的概念和语法之间会有共通之处。有效的类比可以将日常经验与抽象概念和形式化语法相勾连，为新发明和发现提供灵感，为相互理解提供引子。这样《道德经》42章与数学归纳法、《周易》与二进制间的联系也就不那么突兀了。它们都是人类计数经验的一体两面。

当然我们也需要警惕无效的类比。如果推理过程仅仅停留在类比，那就很有诡辩的潜质。类比只能为使用语法做出新发现提供方向。真正向远方前进还得靠合乎经验的概念和合乎语法的演绎。

本篇的写作过程极其纠结，尤其是5.3节中缓存连贯性模型的几个例子。相信观众老爷看得也挺纠结。GPU的缓存连贯性模型等问题目前是GPU编程模型中最前沿的问题。本篇中的众多例子也来源于我跟同事们的多次研讨。如果你读完感觉不过瘾，如果你对设计新的编程模型、开拓GPU的应用领域非常感兴趣，那么欢迎加入沐曦。我们一起开疆拓土。

下一篇我们将从图形学的角度回溯GPU到GPGPU的演化历程。