【读书报告】VLIW技术论：打碎软硬件的边界

注：本文是高等计算机体系结构课程的作业，因为觉得作业不能白写，而且读书报告似乎被我写成了科普向的文章，所以打算把这些作业发在 blog 上 \_(:з」∠)_

微处理器的结构曾经有过几次重大的革新：流水线和 RISC 概念的诞生，使得处理器的性能和指令吞吐量大幅度提升；多发射、超标量技术的诞生，使得指令级并行性得到了进一步的开发；乱序执行技术的推出，使得处理器的动态调度能力达到了新的顶峰。而在微结构发展的历史中，曾出现过很多让人耳目一新的设计：前有 Cray 设计的向量处理机，后有本文提出的超长指令字架构。

VLIW 之优劣

超长指令字，又称 VLIW，是一种在一条指令内部编码多个操作，使得处理器可以直接在一个周期内尽可能同时并行地执行所有操作，从而提升指令级并行性的手段。这种结构相对于乱序超标量结构，硬件上的复杂程度要低很多，因为它只是简单的执行指令中的操作，而几乎不需要在硬件上实现任何的相关性判断。但这也导致了一个问题：VLIW 代码的质量，往往直接决定了硬件执行时的性能。在文章作者所处的时代，编译技术还不那么发达，所以 VLIW 结构并没有被广泛的使用。而当时已经存在的 VLIW 机器，极度依赖于人类手工的编码，这无疑提高了编程的难度，却并不能显著提高代码质量，这就使得这么做的投入和产出往往不成正比。

不过 VLIW 相比当时流行的向量处理机，依然存在一些优势。向量机在编程上直接操作一个数组，或者叫做一个向量，它可以对向量的每一个元素高效的执行相同的操作，从而提升性能。向量机虽然很快，但文章的作者认为，它在通用的科学计算上其实并没有太大的用处。因为使用向量机编程，必须将代码中的数据结构变成符合机器要求的形式——这一点是很困难的。对于编译器来说，这需要相当复杂的算法对代码进行变换；而对人来说，这需要编程者足够聪明，意识到应该如何用向量的思维描述问题。但无论如何，很多科学计算问题可能都无法用向量来描述。此外，最重要的一点是，对于嵌套循环的程序，向量处理机只能加速最内层的循环，性能提升相当有限。

作者之高见

文章的作者认为，VLIW 架构具备相当高的可用性，但这需要有同样强大的编译技术的支持才可以实现。作者提出了一种名为踪迹调度（trace scheduling）的编译技术，来实现代码的调度，利用编译器自动生成高度并行化的 VLIW 程序，避免人工的干预。那么什么是踪迹调度技术呢？

踪迹调度技术最初由本文的作者 Fisher 在其 1981 年的文章中提出，该技术原本是是为微码压缩设计的。根据原始论文，微码压缩的目标是，把一系列顺序执行的微码，压缩成更有效率的并行执行形式的微码，实现更高效的控制逻辑。前者通常被称为 “垂直微码”，后者通常为成为 “水平微码”。作者还提到，这种手段并不会试图做常规意义上的 “编译优化”，而重点着眼于压缩微码的体积。

在作者的那个年代，处理器内使用微码来实现指令的操作和控制逻辑是一件很常见的事情。在早期的处理器中，高速存储器成本很高，而且存储器本身受技术的制约并不能做到很大，所以人们会尽量将微码实现为垂直的形式。垂直微码和普通的机器指令类似，这种形式下，每个微操作都需要用一种特定的编码来表示，执行微码时必须有一个单独的部件对其译码才能将微码变为实际的控制信号。可想而知这样做处理器的速度是很慢的，但这种独立编码的方式胜在占用的存储空间小，可以省下很多的晶体管来实现处理器本身。

相对于垂直微码，还有一种微码的格式成为水平微码，后者会直接对功能部件的控制信号进行编码，处理器可以直接读取微码，然后将其送往不同的信号线，实现控制逻辑。水平微码往往可以将若干个不相干的微操作放在同一个微码里，这样就相当于在一个周期内同时更新多个部件的控制信号，并行性和性能显然更好。但水平微码最大的缺点是设计复杂，而且通常会占用更多的存储器空间。

作者之前的的工作就是利用踪迹调度，将垂直微码的序列，压缩为高效的水平微码序列，以求在提高性能的同时降低存储器的占用。而回到这篇文章所做的研究中，作者凭借其天才般的的洞察力，敏锐地发现，水平微码和 VLIW 在风格上是类似的——它们都是为了增大执行时的并行性，只不过 VLIW 相对更加宏观。那么，为什么不把踪迹调度技术运用在 VLIW 程序的编译之中呢？

踪迹调度之原理

踪迹调度，听起来似乎是一种基于动态分析的指令调度策略。但实际上，它背后的思想其实十分的精妙。踪迹调度运行于程序的流图之上，在处理时，其会打破基本块的边界，然后将流图划分为若干个代码流，然后将它们视作新的基本块进行块内的代码调度，最后加入一些用于恢复的代码来处理例外情况。具体来说，踪迹调度会进行如下操作：

1. 选取一段不包含循环的代码。也就是说，选取的流图中应当不包含回边。
2. 利用一些动态的信息，在编译时进行转移指令的预测，从而从程序中选取一条执行概率最高的执行流。文章中称这条被选中的执行流为一条 “踪迹”。
3. 在这条踪迹上进行一些预处理，以防止调度器在进行代码移动时，破坏踪迹中的某些活跃变量。预处理所做的事情，实际上是插入了一些特殊的边，来让调度算法不要对处理过的部分进行过度的优化。
4. 调度器将整条踪迹视作一个大型的基本块，然后对其中的代码进行移动。移动时，调度器会直接忽略踪迹内到踪迹外的转移指令，以防这些指令限制调度器开发踪迹间代码的并行性。
5. 完成调度后，算法会执行后处理过程。此时算法会在踪迹的入口和出口处插入正确的跳转，并且添加恢复代码，对调度后踪迹内代码所改变的机器状态进行恢复，防止其影响踪迹外的原有代码，保证程序的正确性。
6. 算法会回到第二步，重新考察修改过后的代码，找到第二条执行概率最高的执行流，并继续用上述流程对其进行迭代式的调度。

从上述的算法流程中我们可以发现，踪迹调度实际上借助了动态信息，然后将通常的指令调度流程运用在了某条执行路径的内部。不过，在这个过程中，算法还会产生一部分冗余代码，用于恢复执行流的状态。但据作者所说，这部分代码的量很少，而且由于其不位于踪迹内，所以它的执行概率也非常的低。如果有对代码体积的特殊需求，调度器甚至可以使用更保守的策略来调度踪迹内的代码，从而避免产生任何恢复代码。

踪迹调度还可以很方便的处理循环。区别于传统的软流水算法，踪迹调度只需要先将循环展开若干次，然后用调度器在其上进行多次迭代即可。在展开后的循环中，原先循环的回边会退化为条件跳转，所以调度器可以在其上直接进行踪迹调度。

编译器之实现

作者提出的踪迹调度算法并非虚无缥缈，作者已经实现了一个利用该算法进行指令调度的编译器，名为 Bulldog。Bulldog 中实现了一些更为细致的调度策略，比如关于访存反相关的处理。如果在程序中，前一条语句和后一条语句分别读和写了相同的内存地址，则编译器不能交换这两条语句的位置，否则会发生 WAR 冲突。不过，如果两条语句分别对同一个数组的某两个元素做了读写操作，那其实这两条语句还是有调度的余地的。如果数组的下标不同，则它们的位置就可以被交换。

Bulldog 中，编译器会使用到达定值分析算法，来处理数组的下标，试图缩小下标表达式的范围。从而尽可能地筛选出不相同的下标，实现正确的访存调度。作者表明，目前他们已经实现了反相关的调度策略，并且可以生成功能正确的代码。在实验中，调度后代码的速度可以提升至原来的五到十倍，但人工检查时发现，代码中依然存在一些没有访存相关的地方，这些内容无法被算法识别出来。如果调度器能识别出所有无内存相关的代码，然后对其进行充分的调度，则程序的理论性能还能更高。

作者在文章中提出的检查反相关的方式，在当时的条件下可谓慢得离谱。但在 21 世纪 20 年代的今天，我们知道，编译器可以通过指针分析或者别名分析的技术来解决这个问题，并且可以通过牺牲速度的方式追求更高的精度。甚至，如果程序符合 SSA 形式，指针分析算法的速度还可以进一步提升。也许在今天的硬件性能条件和软件算法的条件下，作者实现的这个编译器可以产生出更高效的代码。

VLIW 机器之构建

作者不仅在文章中提出了一种适用于 VLIW 指令调度的解决方案，而且还提出了一个可执行 VLIW 指令的真实硬件，它的名字叫做 ELI-512，其中，ELI 指的是 “Enormously Longword Instructions”，而 512 指的是，这种机器的指令长度超过了 500 位（512 只是作者的一个小目标）。理想情况下，ELI-512 可以在一个周期执行一条指令，也就是 10 到 30 个 RISC 操作，这种程度的指令级并行性即便放到现在也是十分强悍的。ELI-512 在硬件组成上分成了 16 个 cluster，每个 cluster 代表不同的功能部件，具体细节可参考论文，此处不再赘述。

由于之前从来没有人做过像 ELI-512 这种规模的 VLIW 机器，所以作者在实现硬件的过程中遇到了两大问题：其一是如何安排指令里分支操作的数量，使得性能提升的同时，不会让硬件实现过于复杂；其二是如何安排指令里访存操作的数量，使得性能提升的同时，不会让硬件的运行速度过于缓慢。作者在文章中着重对这两个问题进行了探讨。

为了在一个周期内打包大量操作，从而实现大幅提升并行度的目标，处理器必须支持在同一个周期执行多个分支操作。作者的研究表明，如果目标机器支持一种特殊的分支机制，使得可以在一条指令中进行 n 个并行的分支操作，然后跳转到 n+1 个分支目标，踪迹调度就可以对代码进行高效的处理。这种机制实际上相当于做了一个 n 路的 if-else 条件判断，n 个测试条件对应前 n 个分支目标；当所有条件都不满足的时候，就跳转到最后一个分支目标。作者在进一步的实验中发现，n 的数值选在 3 到 5 之间比较合适。所以，ELI-512 就支持了这种多路分支的执行方式。

关于内存，我们都知道：内存在实现上通常会分为多个 bank，而同一个 bank 不能同时进行多个访问操作。因此，作者指出 VLIW 指令不能简单的包含多个内存操作，因为可能会发生两件事：一个是，在当时的硬件条件下，获取访存地址可能需要很长时间，这就导致执行这些操作也会花费大量时间。另一个是，如果所有的操作都有极大的概率访问同一个内存 bank，那么这个时候就必须花很长时间去等待指令的执行，机器也就毫无并行性可言了。

所以，为了同时执行多个访存操作，编译器应该具备预测内存访问时具体 bank 的能力，并且能正确的处理数组引用带来的地址别名问题。作者实现的编译器在进行踪迹调度的过程中，会在展开循环的同时处理内部的数组操作，使得在同一个周期内执行的多个访存操作尽可能不会相互冲突。同时，ELI-512 在硬件上也支持了包含内存 bank 预测在内的相关机制。

文章之局限

作为 VLIW 的鼻祖，ELI-512 并不是完整的通用处理器，而是类似于协处理器的硬件。这是因为作者所处年代的局限性。ELI-512 必须依附于一个通用处理器才能运行，而且只用做科学计算代码的加速。此外，ELI-512 的软硬件只实现了过程内的 VLIW 化，而没有处理过程间调用的情况。作者认为，通用的代码在任何 VLIW 结构上都可能表现的很差，比如一些系统控制类的代码和通用计算的代码。这种观点在现在看来无疑是无比正确的——如今的 VLIW 结构，大多被实现在了 DSP 而非 CPU 内，这在很大程度上是由于控制流的原因。

笔者之感想

这篇文章开篇重点探讨了一种名为 “踪迹调度” 的编译技术。而在后续的内容中，作者基于这种技术，陆续实现了适用于 VLIW 的编译器，甚至还做出了具备高可用性的、能执行真正意义上的 VLIW 指令的硬件。我认为这篇文章所做的研究，才可以称得上是名副其实的 “软硬件协同设计”。如同著名计算机科学家 Alan Kay 所说：“people who are really serious about software should make their own hardware”，作者身体力行地做到了这一点。

另外，虽然如今 VLIW 架构的硬件早已和微处理器无关，但我依然认为，动态二进制翻译和 VLIW 相结合的技术路线是可行的。可能熟悉我的老师已经听我说过无数遍这样的话，所以我就不再把我幼稚的想法写在这篇读书报告里了。但市场上已经有足够多的案例证明了这件事的可行性，前有 Transmeta 的 Crusoe，后有英伟达的 Denver，这些处理器都将动态二进制翻译技术用在了代码优化而非解决兼容性问题之上。如果文章的作者晚几十年做出这个研究，相信他也一定会将踪迹调度技术和动态二进制翻译相结合，做出更理想的硬件的。

而说到理想的硬件，如我的导师所说，未来的理想硬件应该长的像个 JIT 编译器，具备动态优化的能力。我对此深以为然。但目前存在的问题是，运行速度与编程成本这两者是不可得兼的。软件的编程成本极低，但运行速度显然不如专用硬件快；专用硬件运行速度极快，但如果硬件具备可重编程能力，那它的编程成本是相当高的。如果说我们要在处理器中嵌入一个 FPGA，那在其上运行的软件也许就可以附带一个 bitstream，将自己的一部分功能迁移到硬件上，来实现硬件的动态变化，达到硬件加速的目的。但就算如此，这种方法也是十分不现实的，因为烧录 FPGA 是需要时间的，而这些软件如果要跑在操作系统里，就要受操作系统的调度——这会使得进程切换的成本过高，从而降低操作系统的性能。种种因素，从根本上制约了这种理想机器的诞生。

不过，我们也许能找到一种合适的划分，使得硬件可以具备一定的可重编程能力，又能让重编程后的硬件足够通用——至少能组合成各种不同形态的处理器——还可保持硬件的运行速度。这可能算一种粗粒度的 FPGA，虽然也曾有人做过相关的研究工作，但并未掀起太大的波澜。总之，这种设想的发展需要各方的努力。也许在经过一番研究之后，我们可以找到一种合适的划分方法，将足以构成 CPU、GPU、NPU、各种 PU 的电路，划分成一个个粗粒度的基本组件，就像找到一种合适的指令系统，将程序要执行的复杂操作划分为一条条基础指令一样。然后使用这些基本组件构成一个类似动态流水线，或者干脆是小型 FPGA 的结构，使其可被嵌入到处理器内部，实现可编程的处理单元，服务于这种动态调度。这个设想也许可行，我期待他会发生在不久的将来。

总结

我总觉得微处理器结构的发展和手机形态的变化在某种意义上有着惊人的相似：在最初的时候，所有的手机都差不多一个样子——又贵又笨重，还很不堪用。后来，随着技术的进步，手机越做越小，越做越快，人们也在不停地探索手机形态的新方向。此时出现了许多看起来完全不像手机的手机，比如长得像摄像机的手机、长得像游戏机的手机、长得像掌上电脑的手机、翻盖的滑盖的旋转屏的全键盘的手机，百花齐放。而现在，智能化的浪潮席卷全球，智能手机的性能越来越快，配置越来越强劲，而它们的形态也越来越趋于同质化——因为各种事实表明，大屏幕就应该是手机的发展方向。

处理器也和手机一样，中间曾出现过百家争鸣的时代。而现在，至少所有高性能通用处理器的微结构都已经几乎趋同，因为历史证明， ILP 已经被开发到了极限，乱序超标量、多核和 SIMD 才是正确的发展方向。VLIW 结构的出现就像处理器发展史中平静水面上的涟漪，它带给人耳目一新的感觉，却又在某种意义上与通用计算的需求相悖，最终退出舞台。但我始终相信，VLIW 架构总能在合适的场景发挥作用，而且有了其他技术的加持，它一定能在更广泛的领域大展风采。就像现在，当人们厌倦了手机一成不变的外观时，升降摄像头、机械结构、折叠屏的手机横空出世。

老技术很有可能会在新产品上绽放新的光芒——在这件事情上，我永远持乐观态度。