仓库源文

:Authors: Kenneth Lee :Version: 1.0

从C的for和Python的for聊起

熟悉C的人可能会很看不惯Python的for，因为表达能力其实不如C，比如我要做一个1到10 的循环，用C来表达，就是这样的：::

    for(i=1; i<=10; i++) {
       do_sth_on(i);
    }

很好理解，而用Python，得这样：

    for i in range(1,11):
      do_sth_on(i)

对C的程序员来说，首先为了一个循环创建一个对象(range)就令人不爽。更重要的是，这个控制力不强，你很难在循环中间做动作，比如如果do_sth_on(i)返回错误的时候跳过下一个i的值什么的。

作为脚本语言，Python的综合性能比不上C，但语义表达上从来都是比C好的。所以这里为什么要这样设计？原因是，Python的for和C的for不是一个东西。Python是用while来对应C 的for的，而C的while，根本就是重复的for，所有可以用while的地方，其实都可以用for 来取代。

C的for语句是个循环，而Python的for不是循环，它的原始语义是：“对于集合中的每个成员，执行如下操作”。被C的思维限制住了，你才会觉得这个定义是个循环，但其实它不是，如果你的计算资源足够，你可以并行发动10个计算单元，把do_sth_on([1..10])同时做一遍。这不需要循环。（注3）

C的语法我猜最早也是想表达后面这种意思的（因为英语中for的语义本来就不是循环的意思），但冯诺依曼的思想限制了CPU接口设计，它只能按“说完一码再说一码”的方式给CPU 发命令。但这个“说完一码再说一码”，引入了额外的限制。似乎你要求CPU做完一轮再做一轮。但这并非用户心中的真实需求。这种额外的控制影响了CPU性能和功耗的提升（比如增加OoO逻辑带来的成本）。

所以才有补救式的所谓unrolling算法，把循环分段展开，然后用VLIW，SIMD（注4）指令或者多线程一次同步执行。多线程是把问题交给OS调度器，VLIW/SIMD是把问题交给编译器。也就是，编译器如果知道你循环了多少次，又知道SIMD，VLIW等一次可以同时处理多少个操作，就把这个循环在编译阶段直接unrolling成一个一个batch，这样就能同步更多的执行单元完成复杂的操作了。SIMD现在都是比较简单的操作，很多时候还有较多的通用CPU 成功案例。但VLIW基本上都是非常复杂的组合计算，这个就只能使用在非常专用的领域了（比如DSP）。现在最成功的可能是各种CNN TPU，因为CNN基本上都是向量卷积，这个比较单一，还勉强能做好。

这个主题推广下去，就变成：能否放弃冯诺依曼架构，让程序员不要基于“控制流”来写程序，而是按数据流来写程序了。这样的尝试称为Dataflow Programming。但你看看这种程序的样子：https://en.wikipedia.org/wiki/Hume_(programming_language)。我觉得这就不是给人看的，而是给机器看的，它基本上是张有向图。当然，我们也不是没有过过写给机器看的程序的日子——比如汇编——但汇编时代软件的生产效率如何，这个我们都有经验。

Dataflow Programming的整个问题有点像TPU：我们知道计算的要求和依赖是怎么样的，但这个东西需要编译器根据数据集的大小，内部缓冲的规模，计算单元的能力，重排整个计算过程。这件事情，现在编译器其实做得不那么成功。最终得靠人工干预，但人工干预干预到哪里，就需要一个能被接受的机器抽象才能定义出来，否则辛辛苦苦写的软件，硬件演进一代就废了。

针对Dataflow Program的CPU架构叫EDGE（Explicit Data Graph Execution）。学术界有人把这个看作是RISC ISA架构的下一代。他们认为CISC是第一代，主要是内存昂贵，所以牺牲CPU的连线，把各种访存的复杂度都做到CPU内部了。RISC是第二代，主要简化内存访问的过程（通常只有固定的load和store的操作，不能做复杂寻址）。而EDGE是第三代，这一代的特点主要是从控制依赖变成数据依赖，增加计算单元的数量，给一组计算单元独立的内部存储（注1），然后用SPDI（注2）的发射方式避免多余等待，从而让计算回归计算，减少多余的数据依赖等待。

之所以要拿这个问题出来借题发挥，其实主要是想讨论这个论文的方案：

    http://pages.cs.wisc.edu/~vinay/pubs/isca-hybrid-arch.pdf。

它的概念本身很简单——EDGE的用途摆在那里是有限的，我们的通用计算大部分时候确实是控制流，而不是计算流。既然如此，干脆把EDGE的硬件做成一个和传统超标量通用处理器共存的一个加速器，一般情况下你就用普通的指令集，到你要并行计算的时候，就切换到 EDGE上去执行。从论文的分析上说，对不少具体应用可以获得50%以上的性能或者功耗加成。

硬件设计我不懂，我只是想推演一下这种情况下，软件的方案具体应该是怎么样的。首先，这样的硬件其实很像TPU：有内部Buffer，需要通用CPU负责在内存中准备数据（论文中的机器通用CPU和EDGE加速器共享L1 Cache），然后调用EDGE的例程，这个例程由编译器负责展开特有的指令集到位置上，然后自行搬数据到内部Buffer中，完成并行的计算）。

这样一来，首先预计需要两边都支持的编译器，然后需要把两种指令集粘合的链接辅助程序（比如进行指令模式切换，这有可能可以自动，但我觉得这个对硬件设计要求可能太高了）。然后由于EDGE加速器会本身会有状态，如果过程中发现进程切换，内核需要保存 EDGE的状态。另外，由于EDGE加速器的处理器换代硬件行为会不同，EDGE的二进制可能是需要动态生成的（如果是Python的应用，这样可以做得顺理成章）。

我觉得，一个通用CPU做成这样，实在反人类。你让我做，我宁愿把这个EDGE加速器做成一个外设（但连在系统总线上），然后关联给一个进程，有这个进程独占一个上下文来使用。这样就完全没有保存上下文的问题了。剩下的问题，都交给WarpDrive就行了。这样，我们其实对EDGE有另一个需求：它必须有独立的IOMMU。

这样一来，我们就有这样的结论了：任何计算加速器，只要有一定规模，其实完全没有必要做成CPU的一部分，它就应该是个外设型的加速器（优势是没有任何调度成本）。如果我们基于WarpDrive来做，就是用户进程申请Queue，然后直接准备数据，然后把加速器的程序（在内存中），直接命令发送到加速器，加速器直接访问这个程序，执行……这整个过程，可以完全复用CPU的Cache和内存体系。这些，都要求进程和加速器复用同一个地址空间。所以各位做这个特性的兄弟们，我不管你们怎么做，不能把这个基本要求给我弄丢了。

注1：https://www.cs.utexas.edu/~lin/papers/pact04.pdf

注2：SPDI的概念是来自注1等文献的定义，他们把指令放置（指在内存中的放置）和指令的发射（投入运行），看作是两个动作，然则超标量处理器的模式称为DPDI（动态放置动态发射），因为超标量处理器并不按指令顺序执行的，它们是按OoO来动态放置到处理单元上的。而VLIW是SPSI，因为用户需要静态指定每个指令具体谁来执行，并按这个顺序来发射。而STRIPS这样的EDGE处理器是按SPDI执行，放置是静态的，但发射可以根据数据依赖直接发出去而不需要等待整个节拍的完成。

注3：我没有跟踪这个语法现在的发展，只从它的原始定义上看这个问题。这个问题这样考虑：在C的语法中，i如何变化，是被for的第三部分定义的（而且在循环体中也可以改变），而在Python中，这个i的执行范围，在循环前可以被静态确定，如果是个VLIW机器，有足够资源，我完全可以一次把循环一开始就展开。但C的语法，你不进入每轮循环，你是无法知道如何部署资源的。当然了，编译器完全可以通过收缩语法，提前知道循环体中是否有静态标量从而实施某些行为，这里这是从这两个语法分别更“靠近”什么思路来讨论这个问题而已。

注4：讨论中发现有人对SIMD，VLIW的概念不太清楚，这里速成一下以便对齐讨论空间：从软件的角度其实会觉得这些概念纯属无聊，因为引入这些概念的限制根本就不在软件上，而在硬件设计上。我们觉得做一个除法只是发个指令，但硬件是真的放个除法器的设备在里面的。早期的时候CPU简单，啥计算单元都只有一个，按你指令的要求一个个执行就是了。但后来技术发展了，他们就开始土豪了，死往里塞计算单元，这样他们就要求你一次多给几个计算要求，一种发展思路当然是多CPU多核多线程，但那个太贵了。另一种就是多发射，一次发射多条指令（这就是所谓的超标量计算技术），但数据和控制是有相关性的，很多时候不能同步执行，这就需要软件配合了。一种方法，OoO预测执行，这个几乎不用软件参与，CPU强行给你提前执行，但后面如果发现你不需要这个结果，就把结果扔了。唯一要软件参与的，如果你对某些执行有特别的强制要求，你要主动加Barrier指令来强制等待。第二种方法，SIMD，你把要并行的数据放到指定的寄存器中，一个指令发出去，同步给你做多个一样的动作。比如你有一组128位的浮点数寄存器，每个分成8个16位的浮点数，你可以一次要求8个浮点除法。第三种方法，VLIW，这就是所谓MIMD，多个指令多个数据，你一次说好要同时发射哪几条指令，保证他们各自用不同的计算单元即可。这个对软件的要求就更高了。