| 返回入门教程首页 | 主页 | 开发工具 | 应用芯片 | 核心模块 |
|
|||||||
|
|
||||||
|
|||||||
第六章 理解堆栈计算机在前面的章节中，我们已经抽象地描述了一个堆栈计算机，还具体地描述了几个实际的堆栈计算机例子。我们现在要讨论的是：为什么这些计算机要这样设计？为什么堆栈计算机与传统的计算机相比有其固有的优点？ 本章使用了三个不同的计算机设计方法作为参照点。第一个参照是复杂集指令计算机 CISC ，最典型的是 VAX 系列和个人计算机上使用的微处理器；第二个参照是精简集指令计算机 RISC ，典型的是 Berkeley RISC 项目 (Sequin & Patterson 1982) 和 Stanford MIPS 项目 (Hennesy 1984) ；第三个就是我们在前几章已经讨论过的堆栈计算机。 6.1 讨论了在过去的许多年里，那些鼓吹基于寄存器的计算机、基于堆栈的计算机和存储器到存储器计算机人之间的争论，以及最近关于在 CISC 上实现高级语言和 RISC 体系结构的争论。 6.2 讨论了堆栈计算机的优点。堆栈计算机程序尺寸小、硬件复杂度低、系统性能高，在许多应用环境中比其它处理器执行的平滑性更好。 6.3 给出了 Forth 程序中指令执行频率的研究结果。我们一点儿都不奇怪的是：子程序调用指令在 Forth 程序中占了很大的比重。 6.4 给出了对堆栈进行访问模拟而得到的堆栈管理结果，结果显示对许多应用程序来说，最小需要 32 个堆栈元素空间。这里还讨论了处理堆栈溢出问题所采用的 4 个不同方法：使用很大的堆栈、请求式堆栈管理、分页的堆栈管理和使用联想式 CACHE 存储器进行堆栈管理。 6.5 考察了在堆栈计算机上中断和多任务的成本，一个模拟结果显示在许多环境中，上下文切换是次要的成本。而通过一些方法，堆栈缓冲区上下文切换的成本将进一步降低，这些方法包括：适当地编程中断、使用轻量级的任务、分配堆栈存储器到多个小的缓冲区。 6.1 历史的回顾使用硬件支持堆栈计算机和其它体系结构设计者之间的争论已经有很长的历史了，这种争论可以分成两个主要的领域：在基于寄存器和非寄存器设计者之间的争论，高级语言机器设计者和 RISC 设计者之间的争论。我们不能够给这些争论一个进一步肯定的答案，参考文献中给出的思想值得有兴趣的读者考虑。 6.1.1 寄存器和非寄存器计算机在设计计算机时是不是应该把寄存器显式地提供给程序员？这种设计决策可以回到 1950 年。现存的基于堆栈的 KDF.9 计算机（ Haley 1962 ）证明了在采用基于寄存器的设计方法的许多年之前就已经开始思考改变了。 对于是不是使用基于寄存器计算机的争论导致了几个解决方法：纯的基于堆栈的计算机、单操作数基于堆栈的计算机（也称为堆栈 / 累加器计算机）和存储器到存储器计算机。 纯的堆栈计算机是 SS0、 MS0 和 SL0 和 ML0 分类之一，它们都非常简单。喜爱基于堆栈计算机的一个明显论点就是表达式一类的计算需要使用类似堆栈的结构， 而基于寄存器的计算机在计算表达式时需要花一些时间来模拟堆栈行为。当然，纯的堆栈计算机可能需要多于堆栈/累加器计算机的指令（SS1、MS1、SL1、 ML1 分类），因为它们不能够同时读取一个值并对这个值执行算术操作。聪明的读者可能已经注意到了第 5 章讨论的堆栈计算机使用多操作数指令比如 Variable @ + 以便在很大程序上弥补这一缺陷。 在存储器到存储器计算机体系结构中，所有的操作数都在存储器中，这看起来对运行 C 或者 PASCAL 一类的高级语言很有价值。原因是这样：在这些高级语言中，大多数的赋值表达式在赋值操作符的右边都只有一个或者两个变量，这就意味着许多表达式都可以用单个指令处理，不再需要把数据在寄存器内外搬来运去。 CRISP 体系结构 (Ditzel et al. 1987a, 1987b) 是一个存储器到存储器处理器的例子。 在争论中最经常被引用的一些观点可以在这些论文中见到 Computer Architecture News: Keedy (1978a), Keedy (1978b), Keedy (1979), Myers (1977), Schulthess & Mumprecht (1977), and Sites (1978)，这些论文并没有涉及所有的问题而且某些方面已经过时了，但是它们为那些有兴趣研究这些争论历史的人提供了一个好的起点。 6.1.2 是高级语言还是 RISC 计算机一个相关的争论是使用高级语言计算机还是使用 RISC 哲学来进行计算机设计。 高级语言计算机可以作为 CISC 哲学的进化。这些计算机有潜在的非常复杂的指令可以直接映射到一个或者多个高级语言的函数，在某些情况下，一个编译器前端用于产生可以被机器直接执行的中间代码，比如用于 PASCAL 的 P- 代码或者用于 MODULA-2 的 M- 代码。这种哲学的极限扩展可能是 SYMBOL 项目（ itzel & Kwinn 1980 ），它用硬件实现了全部的系统功能，包括源程序编辑和编译。 高级语言支持的 RISC 体系的哲学是为编译器提供最简单、可能的构造块进行综合高级语言的操作。这通常包括装入、存储和算术操作的代码序列以实现每个高级语言语句，RISC 设计者宣称他们所选择的代码序列可以运行得比 CISC 计算机上等效的复杂集指令要快。 堆栈计算机设计哲学在某种程序上位于高级语言设计和 RISC 设计之间，堆栈计算机提供非常简单的原语，它们可以在单存储器周期中执行完成，符合 RISC 哲学的精神。然而，堆栈计算机上高效率的应用程序代码是通过廉价的子程序调用完成的，这些子程序的选择可以看成是一个虚拟指令集，它们被裁剪成适合高级语言编译器的需要，不需要复杂的硬件支持。 关于高级语言和 RISC 计算机之间的争论可以参考 Cragon (1980), Ditzel & Patterson (1980), Kavipurapu & Cragon (1980), Kavi et al. (1982), Patterson & Piepho (1982), and Wirth (1987). 6.2 与传统计算机的体系结构差异堆栈计算机和传统计算机之间的明显差异是前者使用0操作数堆栈寻址取代后者的寄存器或者存储器寻址，当这种差异与快速子程序调用相结合的时候，就使得堆栈计算机在下列方面超过了传统计算机：程序大小、处理器复杂度、系统复杂度、处理器性能和程序执行的一致性。 6.2.1 程序尺寸人们常说：“存储器很便宜”。这样说是因为他们看到了存储器尺寸快速增长的历史，知道随着时间的增加，芯片可用存储器的大小可以得到梦幻般的增加。 问题是在芯片容量增加的同时，人们使用计算机解决问题的尺寸也在一致性地增加，这就意味着程序和数据集的尺寸比可用存储器容量增加得更快。这种情况随着人们在各个程序设计阶段广泛使用高级语言而变得更为严重，这种结果当然是巨大的程序，但是也提高了程序生产率。 不奇怪，程序复杂性的爆发看起来有些矛盾，有人说“让程序扩展到填满整个存储器，然后再使用其中的一部分”。程序可用存储器的数量对于一个应用程序来说是固定的，这完全是出于对存储器芯片成本、印刷电路板面积等等经济性方面的考虑，它也受到机械性能方面的影响，比如功耗、散热和系统中扩展槽的限制（这也是出于经济性方面的考虑）。就算不考虑成本和预算，电气负荷和连线延迟速度等等方面最终将限制处理器可用存储器芯片的数量。小的程序尺寸能够降低存储器成本、元件数量、电源要求，通过把成本高效率地分配给更小的、更高速度的存储器芯片来提高系统的速度。附加的收益包括：在虚拟存储器环境中性能的改进 (Sweet & Sandman 1982, Moon 1985) ；只需要很少的 CACHE 芯片就可以提高命中率。某些应用场合、特别是嵌入式处理器应用场合，对印刷电路板空间和存储器芯片非常苛刻，因为这些资源是所有系统成本中固定不变的那一部分 (Ditzel et al. 1987b). 面对不断增加的程序尺寸，传统的解决办法是使用分层的存储器器件作一系列的容量/成本/访问时间的折衷。层次组成包括（从最廉价/最大/最慢到最昂贵/最小/ 最快）：磁带、光盘、硬盘，动态存储器、片外 CACHE 和片上指令缓冲存储器。所以，对“存储器很便宜”这句话更为准确的说法应该是：“慢速的存储器很便宜，但快速的存储器却真的死贵”。 存储器问题最后归结于以处理器所能支付的合理的价格为处理器提供一个数量足够多、速度足够快的存储器，这是通过把大多数程序安排到最快的存储器层次中来完成的。 管理最快速存储器层次的通常办法是使用 CACHE 存储器。 CACHE 存储器的工作原理是：一小段程序在一定的时间内会被使用多次，这样，当这一小段程序第一次被引用时，它就被从慢速的存储器复制到 CACHE 中并在其中保存供以后使用，这为第二次和以后的连续访问减少了延迟。因为 CACHE 的容量是有限的， CACHE 中的指令在它的位置被用于最新的取指时可能被替换， CACHE 的问题是它必须足够大以便为偶尔的重用保留足够长的代码片段。 CACHE 存储器足够大到保存一定数量的指令称为“工作集”，可以有效地改进系统的性能。程序的大小如何影响程序性能的提高呢？假设我们在工作集中给出一定数量的高级语言操作，考虑提高代码紧缩性后的影响。直觉告诉我们，如果完成一个高级语言语句的代码序列在 A 机器上比在 B 机器上更紧缩，则 A 机器就需要比 B 机器更小的 CACHE 字节就可以保存下同样代码产生的指令。这就意味着 A 机器只需要较小的 CACHE 就可以得到相同的存储器响应时间。 Davidson and Vaughan (1987) 通过实际的例子提出建议，对于相同的程序， RISC 使用的 CACHE 大小应该是 CISC 的 2.5 倍（尽管其它的来源特别是 RISC 开发商，把这个数目说成是 1.5 倍多一点儿）。他们也建议为了得到相同的性能， RISC 计算机需要 CISC 体系结构 2 倍的 CACHE 。进一步说， RISC 计算机需要 2 倍于 CISC 机器的 CACHE 仍然会产生 2 倍的 CACHE 非命中率（因为对于 2 倍的 CACHE 访问，固定的非命中率导致 2 倍的非命中），结果为了得到同样的性能就需要更快速的主存储器器件，于是我们有这样的规则：运行于 10MIPS 的 RISC 处理器对于满意的性能需要 128K 字节的的 CACHE 存储器，而高端的 CISC 处理器典型地只需要不多于 64K 字节的 CACHE 。 堆栈计算机与 RISC 和 CISC 相比，其程序尺寸更小，堆栈计算机的程序大约比 CISC 代码小 2.5 至 8 倍（ (Harris 1980, Ohran 1984, Schoellkopf 1980) ，尽管后面的讨论会对这个结论做出一些限制。这意味着为了得到相当的存储器响应时间， RISC 处理器的 CACHE 存储器大小与堆栈处理器的全部程序存储器一样大！这是真的吗？我们考虑这样的情况：就在 RISC 处理器上的 UNIX/C 程序员面对 8M 到 16M 字节的存储器和 128K 字节的 CACHE 而闷闷不乐的时候， Forth 程序程序却在热烈地争论着堆栈计算机上的程序是不是真的需要多于 64K 字节空间。 堆栈计算机小的程序尺寸不仅节省存储器芯片进而减少了系统成本，同时它也实际提高了系统的性能。这是由于提高了指令在需要时就驻留在高速存储器中的机会，而有可能的是把全部的程序都放到快速存储器中去。 堆栈计算机为什么只需要这么小的存储器呢？有两个因素说明在堆栈计算机上做到极小的程序尺寸是可能的。一个比较明显的因素也是在论文中经常引用的，堆栈计算机的指令格式小，传统的体系结构不仅需要在每个指令中指定一个操作，而且需要指定操作数和寻址模式。例如，一个典型的把两个数相加的操作在基于寄存器的计算机是是这样的： ADD R1,R2 这个指令不仅需要指定 ADD 操作码，而且还要说明相加的两个寄存器，它们是 R1 和 R2. 相反，基于堆栈的指令集只需要指定 ADD 操作，因为操作数隐含地就是指当前的栈顶，只有在执行一个装入或者存储指令或者把一个立即数放到栈上的操作时才需要指定操作数。 WISC CPU/16 和 Harris RTX 32P 分别使用 8 位和 9 位的操作码，保留的很多操作码为有效地运行程序提供了空间。本书中讨论的其它处理器比如 Novix NC4016 使用宽松的编码指令，可以把 2 个或者多个操作包装在一个指令中，这可以在一定程度上弥补面向字节代码密度的损失。 堆栈计算机能够更紧缩代码的一个不太明显但是更重要的原因是它们能有效地支持高频率子程序的重用编码，常常被称为串线编码（ Bell 1973, Dewar 1975 ）。当这些代码运行在传统的计算机上时，其执行速度将大受影响。事实上， RISC 和 CISC 大多数基本的编译器优化就是把过程调用编译成内嵌的宏。另外，许多程序员也有这样的经验：在传统计算机上过多的过程调用将损害程序的性能，这些都导致传统计算机上的程序明显过大。 相反，堆栈计算机能够有效地支持过程调用。因为所有的工作参数都在堆栈上，过程调用的开销最小，不需要为参数传递而花费存储器周期。在许多堆栈处理器上，过程调用只需要一个时钟周期，而子程序返回在大多数情况下可以与其它操作组合而不需要任何时钟周期。 在说明堆栈计算机代码比其它计算机紧缩的时候我们有几个条件，特别是像我们这样没有给出一个全面的研究结果的情况下。程序的尺寸很大程序上依赖于所使用的程序设计语言、编译器、程序设计风格和处理器所使用的指令集。同时， Harris 、 Ohran 和 Schoellkopf 对堆栈计算机的研究主要是基于可变长度的指令，而本书中描述的处理器都是 16 或者 32 位的固定长度指令。 考虑固定指令长度下面这样一个事实：运行 Forth 的处理器比其它堆栈计算机的程序更小。程序更小是因为它们更经常地使用子程序调用，允许在一个单一的应用程序中进行高度的代码再用。同时，我们在后面部分还可以看到：即使是 32 位的处理器比如 RTX32P ，也不像通常大家所想象的那样占用许多存储器空间。 6.2.2 处理器和系统复杂度当我们考察一个计算机的复杂度时，重要的是两个级别：处理器的复杂度和系统的复杂度。处理器的复杂度是处理器核心中实际用于计算的逻辑单元数量（用芯片面积、晶体管数等来度量）；系统的复杂度是考虑嵌入一个全功能系统的处理器，同时也包括电路、存储器和软件。 CISC 计算机这些年来已经变得极端复杂，这种复杂性来源于要求它们能同时很好地满足许多功能。一个很大的复杂性就是要求使用许多指令格式对各种不同的指令进行紧密的编码，其它的复杂性来自于它们对多个编程和数据模型的支持。没有一个机器能同时有效地支持所有这样的应用：在一个时间片内既处理 COBOL 的 PACKED十进制数，又进行 FORTRAN 的浮点矩阵操作，还要处理 LISP 的专家系统，什么都想做到，那当然是极端地复杂了。 CISC 的复杂性一部分是为了保持程序较小而进行编码的结果。它的目标是缩小高级语言和机器指令的语义间隙，并产生更高效的代码。不幸的是，这样就使得几乎所有的芯片可用面积都用来实现控制和数据通道了（比如 Motorola 680x0 和 Intel 80x86 产品）。 所以， RISC 的设计者总是说 CISC 设计者可能是“赔了性能，又折了尺寸”。 某些 CISC 处理器所具有的极端复杂性看起来有些不可思义，但它们却来自于一个普遍的和良好的目标：在硬件和软件之间建立起一个一致的和简单的接口。其成功可以从 IBM SYSTEM/370 产品线上见到，这种计算机系列包含了各种不同的性能和价格，从个人计算机插卡到超级计算机都使用同样的汇编语言指令集。 软件和硬件在汇编语言级清晰一致的接口意味着编译器不需要很复杂就能够产生各方面可接受的代码，它们也可以在同一系列的不同机器上共用。 CSIC 的另一个优点是：因为代码非常紧缩，它们不需要为提高系统性能而使用大容量的 CACHE ，也就是说，CISC 通过提高处理器复杂度而减少了系统复杂度。 RISC 计算机背后的概念是通过减少它的复杂度而使处理器运行得更快。在这一点上，实际的处理器内部比 CISC 使用更少的晶体管用于控制电路，它的实现是使用简单的指令格式和低语义内容的指令，每条指令不做太多的工作，但是只需要很少的时间就可以完成。指令格式通常以适合运行某种特殊程序设计语言和任务的需要而进行选择，典型地是 C 程序设计语言的整数运算。 减少处理器的复杂度并不是没有成本的，许多 RISC 处理器使用巨大的寄存器体来保证经常访问的数据能够快速地重用，这些寄存器必须是双端口存储器（以便允许两个不同地址能够同时访问）来实现每个周期的两个源的读取。更进一步，由于这些指令都是低语义内容的， RISC 处理器必须有更高速的存储器带宽以保证进入 CPU 的指令流。这意味着为了得到应有的性能，片上和系统中固定的资源必须是 CACHE 存储器。同时， RISC 处理器的特点之一就是内部的流水线，这意味着需要有更多的硬件和编译技术来管理流水线。在中断处理时，应该特别注意并使用额外的硬件资源来确保流水线状态被正确地保存和恢复。 最后，不同的 RISC 实现策略对编译器提出了更高的要求：调度流水线以避免竞争冒险、填充分支延迟时隙、管理寄存器体的分配和溢出。在减少处理器复杂度以便更容易地得到没有 BUG 的硬件的同时，把更多的复杂性推给了编译器，这就使得编译器更加复杂，开发和调试成本更高。 减少 RISC 处理器的复杂度导致了偏向于（甚至可能更为严重地）增加了系统的复杂度。 堆栈计算机努力改善处理器复杂度和系统复杂度之间的平衡。堆栈计算机设计者认识到处理器的简单性不仅受限于指令的数量，更受限于指令可能操作的数据：所有的操作都是对堆栈顶部元素的。从这个意义上说，堆栈计算机不应该是“减少了指令集的计算机”，而应该是“减少了操作数集的计算机”。 限制操作数选择而不是指令做多少操作的观点确实有几个优点，指令可以非常紧缩，因为它们只需要指定实际的操作，而不需要指定源是从哪里来的。片上堆栈存储器可以是单端口的，因为每个时钟周期只有一个元素需要进行堆栈的 PUSH 或者 POP 操作（假设栈顶的两个元素保存在寄存器中）。更重要的是，因为已经知道所有下一步的操作数都是堆栈元素，所以不需要使用流水线进行操作数预取。操作数总是在栈顶寄存器中因而是立即可用的，作为一个例子，我们可以考虑 NC4016 设计中的 T 和 N 寄存器，并把它们与数以十计甚至数以百计的 RISC 计算机中可随机访问的寄存器相比较一下。 选择隐含的操作数也简化了指令格式，就算是 RISC 计算机也有多种指令格式。然而，堆栈计算机只有很少的指令格式，甚至更极端的比如 RTX32P 只有一种指令格式，限制指令格式的种类简化了指令译码逻辑，加快了系统的操作速度。 堆栈计算机格外地简单：16位堆栈计算机的核心典型地只使用 20000到35000个晶体管。比较 Intel 80386 芯片有275000 晶体管，Motorola 68020 有200000 晶体管。就算 80386 和 68020 是 32 位的计算机，这其中的差异也是明显的。 堆栈计算机的编译器也很简单，因为指令的格式和操作选择是一致的。事实上，寄存器计算机的编译器通过一个像堆栈一样的表达式视图用于表达式计算，然后把这些信息映射到寄存器集中。堆栈计算机的编译器在进行堆栈方式的源程序版本映射到汇编语言时只需要做很少的工作。 Forth 编译器的简单和灵活是众所周知的。 堆栈计算机系统总体上也非常简单，因为堆栈程序是如此之小，以至于为了高性能而进行 CACHE 控制的方法是多余的，典型的程序可以全部放到 CACHE 速度的存储器中，而不需要复杂的 CACHE 控制电路。 在程序和/或者数据太大而不能放到存储器的情况下，可以使用软件管理的存储器分层：经常使用的子程序和程序段可以放到高速存储器中，不经常使用的程序段放到慢速存储器中。对高速存储器进行成本低廉的单周期调用使得这种技术非常有效。 数据堆栈在许多场合可以作为一个数据 CACHE 看待，比如过程的参数传递，数据元素可以在软件的控制下按需要从高速存储器中移入和移出。虽然传统的数据 CACHE 、或者多多少少地扩展一下成指令 CACHE，的确能够改进一些速度，但堆栈计算机在运行小的或者是中等规模的应用时是不要求甚至是不需要CACHE的。 因此，堆栈计算机通过限制指令可用的操作数而降低了处理器的复杂度。这样做并没有强制性减少可用的指令数，也没有引起支持处理器运行的硬件和软件发生大的改变。这种减少复杂度的结果是堆栈计算机为片上程序存储器和片上专用硬件留下了更多的空间，一个隐见的影响是：堆栈计算机的程序是如此之小以至于许多应用程序可以完全放到片上。这种片上存储器比片外的 CACHE 更快，它也将省去复杂的控制电路而没有任何速度方面的牺牲。 6.2.3 处理器的性能处理器的性能是一个很难说清楚的方面，数不清的功夫耗费在争论哪一个处理器比另一个更好，但这些功夫常常基于粗略的、明显可疑的测试程序，其热情也主要来自于自己的兴趣和对具体产品的忠心（或者是存在购买关系）。 之所以难于进行比较的原因主要是应用领域的问题，使用整数算术运算的测试程序并不能适合浮点性能、商业应用或者符号处理。最好也不过是使用测试程序说明在给定的硬件（相关联的 CACHE 、存储器、硬盘、时钟速率等）、使用给定的操作系统、使用给定的编译器、使用相同的编程语言的情况下， A 处理器比 B 处理器更好，但这也只是测试程序的结果。很明显，测试不同的计算机性能是很困难的。 测试完全不同的体系结构就更加困难。困难的核心是单个指令做多少工作。因为 VAX 计算机上多项式运行指令所作的工作量与 RISC 上寄存器到寄存器间移动的指令是大不相同的，“每秒指令数”的概念往最好里说也只能是精细（甚至当归一化到标准指令测试、使用同样的测试程序，我们还是不能真的相信）。另外的问题是不同的处理器使用不同的技术实现（双极性、ECL、SOS、NMOS 和 CMOS 将有不同的尺寸）和不同的设计实现策略（昂贵的全定制布线、标准单元自动布线、门阵列布线）。然而，非常概念地比较不同的体系结构就要求扣除不同的实现技术的影响。更进一步，执行的软件对性能有非常大的影响，问题是在真实的世界中，一个指定计算机的效率并不仅仅决定于处理器的速度，也要受到系统硬件、操作系统、程序语言和编译器性能和质量的影响。 所有这些困难给了读者一个结论：精确性能测试的问题不可能在这里解决。相反，我们集中讨论一些原因：为什么堆栈计算机可以比其它种类的计算机每个指令都快？为什么堆栈计算机有良好的系统性能特点？它最适合于运行哪一类的程序？ 6.2.3.1 指令执行的速率
图 6.1A 指令阶段的重叠 -- 原始指令阶段 最诡辩的 RISC 处理器宣称它们有最高的执行速率 -- 一个时钟一条指令。它们是通过流水线完成的，把指令分成几个序列：地址发生、指令读取，数据存储周期，如图 6.1A 所示。这种在指令流上的加速削弱了指令的执行，同时也产生了一些问题，最明显的就是为了避免由数据依赖引起的竞争，当一条指令依赖于前面指令的结果时就会产生这样的问题。因为第二条指令在读取它的操作数时必须等待第一条指令把结果存入。有几个硬件和软件策略可以减轻数据依赖的影响，但是没有一个能够完全解决这个问题。 堆栈计算机可以把程序执行得和 RISC 一样快，由于没有数据依赖问题而可能更快。有一种说法是寄存器计算机由于能够使用流水线而比不能使用流水线的堆栈计算机执行得有效，这是由于事实上每条指令都依赖于前面的指令在堆栈上的影响。但现在的问题，堆栈计算机不需要流水线就可以和 RISC 一样快。 考虑 RISC 计算机的指令流水线在用于堆栈计算机时如何设计。两种机器都需要读取指令，两种机器都可以与前面的指令并行执行。为了方便，我们的把这些与指令译码一同考虑，由于堆栈计算机比如 RTX32P 不需要执行条件操作以从指令中分出参数字段或者选择使用哪种格式，所以它比 RISC 计算机更简单。 在流水线的下一步操作中，主要的差别开始变得明显。 RISC 计算机必须花费一个流水线阶段来访问指令后面的操作数（至少某些情况是这样）才能完成译码。一个 RISC 指令指定两个或者多个寄存器作为 ALU 操作的输入。而堆栈计算机不需要读取数据；它们在需要时等待栈顶数据。这就意味着在最小的情况下，堆栈计算机可以省去流水线的操作数读取部分。实际上，堆栈访问也可以做得比寄存器访问更快，这是由于单端口的堆栈存储器可以做得很小，也当然就比双口寄存器存储器更快。 RISC 和堆栈计算机的指令执行部分可以认为是相同的，因为同样的 ALU 可以用于两种系统中。但就是在这种情况下，堆栈计算机也可以有 RISC 所没有的优点，比如在 M17 堆栈计算机上，ALU 功能可以在指令译码之前对栈顶元素进行操作。 操作数存储阶段在某些 RISC 设计中需要占用存储器的另一个周期，因为结果必须写回寄存器文件。这种写回与新指令的读是有冲突的，需要延迟或者用一个三口的寄存器文件。这也可能要求 ALU 把输出保持在一个寄存器中，然后这个寄存器在下一时钟周期里作为寄存器文件写操作的源。相反，堆栈计算机只是简单地把 ALU 输出的结果放到栈顶寄存器中就完成了。另外的一个问题是 RISC 处理器需要附加的前向数据逻辑以保证在 ALU 的输出作为下一个指令的 ALU 输入时结果写入了寄存器。而堆栈计算机 ALU 输出总是可用的，它作为 ALU 的一个隐含的输入。
图 6.1B 指令阶段重叠 -- 典型的 RISC 计算机
图 6.1C 指令阶段重叠 -- 典型的堆栈计算机 图 6.1B 显示出， RISC 处理器需要至少3个或者4个流水线阶段以维持相同的吞吐率：指令读取、操作数据读取、指令执行 / 操作数读取。同时，我们也注意到 RISC 设计方法与生俱来的几个问题比如数据依赖和资源争夺在堆栈计算机中都非常简单地“不存在”。图 6.1C 给出了堆栈计算机只需要两级流水线：指令读取和指令执行。 所有这些都意味着堆栈计算机没有理由比 RISC 处理器在执行指令时更慢，而使用相同的工艺，堆栈计算机只会比 RISC 计算机更快、也更简单。 6.2.3.2 系统性能系统性能可能比原始的处理器性能更难于度量，它不仅包括每秒钟能执行多少直线编码的指令，也包括处理中断的速度、上下文切换的速度和由于条件分支、子程序调用引起的性能降低。一些方法比如三维计算机性能 (Rabbat et al. 1988) 比原始的指令数据更能反映计算机的系统性能。 RISC 和 CISC 计算机都是用来执行正常情况下的直线编码，在这些机器上执行很多的过程调用将严重影响它们的性能。调用过程的成本不仅包括保存程序指针和读取不同的指令流，也包括保存和恢复寄存器、安排参数和可能发生的流水线破坏。而一个称为返回栈的实际数据结构在堆栈计算机上对于控制流结构比如过程调用来说非常重要，因为堆栈计算机在硬件上保存了所有的工作变量，在把参数传送给子程序时所要求的时间就非常少，通常只需要一个DUP 或者OVER 指令。 对于所有种类的处理器来说，处理条件分支都是很困难的，其中的原因是指令的预取机制和流水线机制的前提是指令不被中断，这样才能保持繁忙，而条件分支将使得分支在未决时被迫等待。唯一的一个选择是在可能的路径之前预测以希望在等待分支时进行非破坏性的工作。 RISC 机器使用“分支延迟时隙” (McFarling & Hennesy 1986) 并放置一个非破坏性指令或者是 NOOP ，它在分支之后总是执行。 堆栈计算机以不同的方法处理分支，它能够在单周期内实现分支而不需要要延迟时隙，也不需要增加编译器的复杂性。 NC4016 和 RTX2000 通过指定存储器周期比处理器周期更短来处理这个问题，这就意味着在处理器周期中有时间为条件分支产生一个地址，并且还能够在时钟周期的尾部读取指令。这种方法工作得很好，但问题是半导体工艺的进步总是使得处理器速度的提高远远高于程序存储器速度的提高。 FRISC3 为条件分支产生一个分支指令，并和下个指令一同完成分支。这是一个非常聪明的办法，因为在任何机器上大多数的分支指令之前总是需要一个比较或者其它操作。除了比较操作之外（通常是一个减法），FRISC3 也指定哪一个条件是下一条分支指令所关心的。这就把大部分的分支决策工作交给了比较指令，而在随后执行条件分支时只需要测试一个单独的位。 RTX32P 使用微码把比较和条件分支组合到两个指令周期中，它们与比较指令后随一个条件分支的时间相同。例如， = 0BRANCH 可以合为一个单个的 4 微码周期（两个指令周期）的操作中。 对于中断处理，堆栈计算机比 RISC 和 CISC 计算机都简单。在 CISC 计算机中，复杂的指令使用多个周期才能完成，所以它们需要被中断。这就要求大量的处理开销，以及在指令的中间保存控制逻辑和恢复机器状态。 RISC 计算机也好不到哪儿去，因为它们有一个流水线，需要在每个中断中保存和恢复。它们也还有寄存器需要保存和恢复以便于中断服务程序得到工作所需要的资源。在 RISC 和 CISC 机器上，通常需要几百微秒来响应一个中断。 另一方面，堆栈计算机处理中断的时间典型地只需要几个时钟周期。中断作为由硬件执行的子程序调用来处理，不需要清除和恢复流水线，处理器处理中断需要做的唯一事情就是把中断响应地址作为一个子程序调用插入到指令流中，把堆栈掩码寄存器 PUSH 到堆栈上（以防止对中断服务子程序的递归调用）。一但进入中断服务程序，则不需要保存任何寄存器，因为新的子程序只需要简单地把它的数据 PUSH 到栈顶。为了说明堆栈处理器有多快的中断处理速度，我们看一个例子： RTX2000在中断响应确认和中断服务程序的第一条指令执行之间只需要花费 4 个时钟周期（400 ns）。 人们可能会认为堆栈计算机的上下文切换比其它处理器慢，但我们后面会看到，事实并不是这样。 堆栈计算机的最后一个优点是：它们的简单性为客户在微处理器中实现应用指定硬件留下了许多空间。例如， HARRIS RTX2000 有一个片上的硬件乘法器，其它的应用指定硬件包括 FFT 地址发生器、A/D、 D/A 或者是通讯接口。这样的硬件可以有效地减少最终系统中元件的数量，并能够极大地减少程序执行时间。 6.2.3.3 堆栈计算机最适合哪些程序运行？能够在堆栈计算机上有效执行的程序包括子程序调用敏感的程序、有大量控制流结构的程序、执行符号计算（通常使用堆栈结构和递归来解决问题）的程序、设计用来处理高频率中断的程序、在有限存储器上运行的程序。 6.2.4 程序执行的一致性先进的 RISC 和 CISC 处理器依赖于许多特殊的技术，它们能够在一个相当长的时间段里达到静态的高性能，但是并没有办法保证在短时间内的高性能。它们使用的技术包括：指令预取队列、复杂的流水线、记分牌、 CACHE 存储器、分支目标缓冲区、分支预测缓冲区。当然，现在的问题是这些技术都不能保证处理器在任何特定时间里的瞬时高性能。外部事件或者内部数据一个不合适的序列可能导致 CACHE 存储器完全失配、队列刷新和其它的延迟。当然，平均的高性能也可以为某些程序所接受，但是对于许多实时应用来说，可预测的连续一致高性能更为重要。 堆栈计算机没有使用任何一种前面列出的动态加速技术，但是却得到了优秀的系统性能。堆栈计算机程序执行的简单性，得到了在任何时间度量中都非常一致的性能。我们在第 8 章中可以看到，这对实时控制应用程序的执行有巨大的影响。 6.3 Forth 指令频率研究我们已经对堆栈计算机与其它计算机的区别有了一个概念性的理解，现在我们可以对堆栈计算机的执行给出一些数量上的统计结果。测试基于堆栈计算机和基于寄存器的计算机的指令指令频率和代码大小的工作包括： Blake (1977), Cooke & Donde (1982), Cooke & Lee (1980), Cragon (1979), Haikala (1982), McDaniel (1982), Sweet & Sandman (1982), and Tanenbaum (1978)) 。不巧的是，许多结果都是从传统语言编写的程序中得到的，而不是基于天生就是基于堆栈的语言 Forth 。 Hayes et al. (1987) 给出了一个 Forth 程序的执行统计，我们将对此加以扩展。 本章的结果都是基于 Forth 编写的程序，这样可以利用堆栈计算机的大多数优点。注意测试程序都是静态的，所以这些结果应该视为“TRUTH”的近似（无论你怎么理解）。 下面部分引用了 6 个不同的测试程序。除了另有说明，所有的程序都是用 16 位 Forth 编写的。它们是： Frac: 一个分形图表产生程序，它使用一个随机数发生器。它总是使用相同的初始值作为种子来产生图形 (Koopman 1987e, Koopman 1987f) Life: Conway的生命游戏在80列25行字符显示器上的简单实现。每个程序都计算机一个全屏幕移动的10代。 Math: 一个32位的浮点程序包，完全用高级Forth代码编写，没有使用诸如归一划一类的机器原语，每个程序运行用以产生1-10度整数的正弦、余弦、正切函数表。 (Koopman 1985) Compile: 一个脚本用于编译Forth程序，测试Forth编译器本身的执行。 Fib: 使用递归过程方法计算24th Fibonacci 数，也称为"dumb" Fibonacci. Hanoi: Hanoi 塔问题，编写成一个递归过程，每个程序运行计算12个盘子。 Queens: N 皇后问题 (从8皇后问题导出)，编写成递归过程。程序找到N x N 棋盘上的第一个可接受的位置,每个程序运行计算N = 12 皇后。 有三个程序最好地代表了不同应用领域的混合，它们是： Math -- 它使用了密集的堆栈操作以便在 16 位堆栈计算机上管理 32 位数（还有一个 48 位的中间浮点格式）；Life -- 通过许多条件分支对存储器单元的矩阵进行管理； Frac -- 它进行图形画线和基本的图形映射。 编译器测试程序也是有用的，它反映了编译器的行为，它必须对输入流进行 TOKEN 化并进行标识符搜索。 6.3.1 动态指令频率
NAMES FRAC LIFE MATH COMPILE AVE CALL 11.16% 12.73% 12.59% 12.36% 12.21% EXIT 11.07% 12.72% 12.55% 10.60% 11.74% VARIABLE 7.63% 10.30% 2.26% 1.65% 5.46% @ 7.49% 2.05% 0.96% 11.09% 5.40% 0BRANCH 3.39% 6.38% 3.23% 6.11% 4.78% LIT 3.94% 5.22% 4.92% 4.09% 4.54% + 3.41% 10.45% 0.60% 2.26% 4.18% SWAP 4.43% 2.99% 7.00% 1.17% 3.90% R> 2.05% 0.00% 11.28% 2.23% 3.89% >R 2.05% 0.00% 11.28% 2.16% 3.87% CONSTANT 3.92% 3.50% 2.78% 4.50% 3.68% DUP 4.08% 0.45% 1.88% 5.78% 3.05% ROT 4.05% 0.00% 4.61% 0.48% 2.29% USER 0.07% 0.00% 0.06% 8.59% 2.18% C@ 0.00% 7.52% 0.01% 0.36% 1.97% I 0.58% 6.66% 0.01% 0.23% 1.87% = 0.33% 4.48% 0.01% 1.87% 1.67% AND 0.17% 3.12% 3.14% 0.04% 1.61% BRANCH 1.61% 1.57% 0.72% 2.26% 1.54% EXECUTE 0.14% 0.00% 0.02% 2.45% 0.65% Instructions: 2051600 1296143 6133519 447050 表 6.1. 重要 Forth 原语的动态指令执行频率 表 6.1 给出了许多常用 Forth 原语的执行频率： Frac、Life、Math 和 Compile。动态指令执行频率就是在一个程序运行过程中一个指令的执行次数。附录 C 给出了对应表 6.1 完整的结果。AVE 列为四个测试程序的加权平均结果，这可以看成是大多数 Forth 程序的近似结果，选择表中 Forth 字的原则是：它们或者是 AVE 列的前10 位，或者是一个特殊程序的前 10 位。例如， EXECUTE 在 AVE 中只占 0.65% ，但是在编译中占 2.45% ，它在编译测试中列第 10 位。 这些数字中最明显的一件事就是子程序调用和返回操作远远多于其它操作，这也很好地说明了为什么源自于 Forth 的堆栈处理器都特别强调子程序调用/返回与其它指令组合的影响。子程序返回的数量比子程序调用要少，因为某些 Forth 操作直接弹出返回栈元素进而返回两级子程序调用 -- 这是执行一个子程序调用的条件返回。 消耗在堆栈处理原语上的时间也很有趣。在所有的样例指令中，大约有25%花在处理堆栈上。这初看起来很高，然而，我们应该想到，因为堆栈处理器都有把堆栈处理和其它工作组合起来的能力 (比如组合 OVER -) ，这个数应该比我们所看到的要高得多。而这25%由于浮点数学包在处理 32 位数需要使用 R 操作而增大了 5% 。这种代价在 32 位处理器或者使用快速访问用户存储器空间（比如 NC4016 和 RTX2000 ）的 16 位机器上不会存在。 另一个有趣的方面是为了准备处理而把数据读取到堆栈上的过程也非常重要（这个过程包括在 VARIABLE、@、LIT 、 CONSTANT 和 USER 中）。幸运的是，堆栈计算机可以把这些指令与其它操作组合在一起。 最后一个结论是：许多在附录C 中列出的指令其动态执行频率都少于1% ，但是，并不能因此就认为这些指令是不重要的，其中许多指令如果没有硬件支持，则执行时就会耗费很长的时间，所以不能仅仅依靠执行频率来决定一个指令是否重要。 6.3.2 静态的指令频率
表 6.2 给出了 Frac 、 Life 和 Math 在许多编译原语中的静态编译频率和在 Compile测试程序中被编译程序最常使用的原语（包括 Frac 、 Queens 、 Hanoi 和 Fib ）。一个指令的静态频率是它在源程序中出现的次数,AVE 列给出了4个测试程序的加权平均，它可以看成是大多数 Forth 程序编译的大致结果。这里列出的 Forth 字是 AVE 列的前10 名，或者是位于某个特殊程序的前 10 位。 在这种静态结果中，子程序调用非常频繁，大约占全部编译指令的1/4 。注意 Frac 由于包含在 Compile 中而被计算了两次，所以实际的子程序调用数应该略低于表中所列的值。 6.3.3 RTX32P 的指令压缩由于子程序调用是如此普遍，我们也就不奇怪为什么大多数堆栈处理器都有把子程序调用指令与其它指令组合的机制。一个关注点是，在源代码中子程序调用比子程序返回更加普遍，把它与其它指令结合就更有吸引力。 在第5章中讨论的 RTX32P 有一个独特之处是它有单一的指令格式，把操作码与子程序调用/子程序返回/无条件转移组合起来。这初看起来好象浪费了存储器空间，但实际上是性能大大提高而存储器成本也相对较低。不幸的的，这种单一指令格式只能用于 32 位的处理器，因为16 位处理器指令中没有足够的位来组合操作码和大的地址字段。 表 6.3 和 6.4 是利用 32 位优点编写的 Frac、Life 和 Math 程序的执行和编译结果统计。 6.3.3.1 执行速度的收益表 6.3 是专门为 RTX32P 优化的动态程序执行的4 个统计结果。表 (A) 给出的是没有把操作码和子程序压缩在一起、没有窥孔优化（操作码组合）的程序执行结果。 表 6.3. RTX32P 指令类型的动态指令执行频率
FRAC LIFE MATH AVE
OP 57.54% 46.07% 49.66% 51%
CALL 19.01% 26.44% 19.96% 22%
EXIT 10.80% 12.53% 16.25% 13%
OP+CALL 0.00% 0.00% 0.00% 0%
OP+EXIT 0.00% 0.00% 0.00% 0%
CALL+EXIT 0.00% 0.00% 0.00% 0%
OP+CALL+EXIT 0.00% 0.00% 0.00% 0%
COND 5.89% 9.95% 6.56% 7%
LIT 6.76% 5.01% 7.57% 6%
LIT-OP 0.00% 0.00% 0.00% 0%
VARIABLE-OP 0.00% 0.00% 0.00% 0%
VARIABLE-OP-OP 0.00% 0.00% 0.00% 0%
Instructions: 8381513 1262079 940448
OP-OP 0.00% 0.00% 0.00% 0%
表 6.3(a) 关闭指令压缩和操作码组合
FRAC LIFE MATH AVE
OP 50.92% 42.22% 45.94% 46%
CALL 17.81% 28.31% 21.42% 23%
EXIT 12.48% 13.42% 17.45% 14%
OP+CALL 0.00% 0.00% 0.00% 0%
OP+EXIT 0.00% 0.00% 0.00% 0%
CALL+EXIT 0.00% 0.00% 0.00% 0%
OP+CALL+EXIT 0.00% 0.00% 0.00% 0%
COND 6.82% 10.66% 7.05% 8%
LIT 2.60% 1.94% 2.53% 2%
LIT-OP 5.21% 3.43% 5.59% 5%
VARIABLE-OP 2.67% 0.00% 0.01% 1%
VARIABLE-OP-OP 1.49% 0.00% 0.01% 1%
Instructions: 7250149 1178235 875882
OP-OP 4.72% 3.68% 1.76% 3%
表 6.3(b) 关闭指令压缩，进行操作码组合 ON.
表的 B 部分是把常用的操作码序列（比如 SWAP、DROP、OVER、+、Variable、 @ 和 Variable @ + ）组合在一个指令中而产生的影响。标记为 OP-OP 的列是把两个操作按单一的操作码对待，包括 OP 、 OP-CALL 、 OP-EXIT 和 OP-CALL-EXIT 。 LITERAL + 、 LITERAL AND 等等是特殊情况，全部标记为 LITERAL-OP ，而 Variable @ 和 Variable ! 标记为 VARIABLE-OP. @ + 和 Variable @ - 标记为 VARIABLE-OP-OP 。所有的常数和变量的特殊情况都需要一个完整的指令来保持一个操作码和地址，没有同其它指令组合。对于例子程序，操作码的窥孔优化可以减少 10% 的指令执行。
FRAC LIFE MATH AVE
OP 48.84% 31.26% 40.81% 40%
CALL 8.46% 22.20% 15.53% 15%
EXIT 4.57% 0.00% 4.80% 3%
OP+CALL 13.93% 11.47% 6.68% 11%
OP+EXIT 7.71% 15.96% 12.90% 12%
CALL+EXIT 0.80% 0.00% 2.04% 1%
OP+CALL+EXIT 0.15% 0.00% 0.03% 0%
COND 7.23% 12.69% 7.99% 9%
LIT 8.31% 6.39% 9.22% 8%
LIT-OP 0.00% 0.00% 0.00% 0%
VARIABLE-OP 0.00% 0.00% 0.00% 0%
VARIABLE-OP-OP 0.00% 0.00% 0.00% 0%
Instructions: 6827482 990313 772865
OP-OP 0.00% 0.00% 0.00% 0%
表 6.3(c) 打开指令压缩，关闭操作码组合
表 C 给出了用指令压缩代替操作码组合的影响，这意味着只要可能，操作码就与后面的子程序调用和返回合并在一起。子程序调用后随一个返回则组合成一个无条件转移，结果是总数的 24% 能够实现操作码与子程序调用/返回组合。这使得源程序中的40% 子程序调用是“免费的”，而几乎所有的子程序返回都是免费的。除了特殊的指令，比如常数和返回栈处理指令，它们无法与子程序返回相组合。
FRAC LIFE MATH AVE
OP 39.05% 24.91% 39.19% 34%
CALL 6.75% 24.27% 15.94% 16%
EXIT 6.54% 0.01% 10.78% 6%
OP+CALL 12.71% 12.53% 6.87% 11%
OP+EXIT 6.78% 17.44% 7.40% 11%
CALL+EXIT 0.95% 0.01% 2.10% 1%
OP+CALL+EXIT 0.09% 0.00% 0.03% 0%
COND 7.84% 13.86% 8.21% 10%
LIT 3.00% 2.52% 2.95% 3%
LIT-OP 6.00% 4.45% 6.51% 6%
VARIABLE-OP 3.08% 0.00% 0.01% 1%
VARIABLE-OP-OP 1.72% 0.00% 0.01% 1%
Instructions: 6294109 906469 752257
OP-OP 5.44% 4.79% 2.05% 4%
表 6.3(d) 指令压缩打开，操作码组合打开 表 D 给出了同时进行操作码组合和指令压缩的影响。结果是比原始的程序小了 25%。这种性能的提升几乎不需要软件和硬件的扩展，因为在子程序调用和操作码之间有天生的并行性。 有趣的一点是， Math 测试程序从16位系统上的610万指令减少到在 RTX32P 上的 94 万指令，说明32位处理器对于浮点计算是很有必要的。Life 测试程序（它几乎都是使用 8 位和数据处理）在各个系统上几乎相同。 Frac 测试程序增加了 4 倍，但是这是由于 32 位版本的 Frac 使用了更高的图形分辨率，有 4 倍的点数需要计算，所以需要大约 4 倍的指令。 6.3.3.2 存储器尺寸的成本把子程序调用与操作码结合对性能的提升是值得的，特别是由于它本质上不需要在处理器中增加硬件。事实上，它通过只用一种指令格式而简化了硬件。现在还有一个问题需要解决：它的存储器成本如何？ 幸运的是，Forth 程序的静态子程序调用频率比动态频率更高。这为操作码/子程序调用组合提供了一个成熟的机会。表 6.4 给出了静态程序尺寸的的差异：没有经过压缩的原始程序和同时进行指令组合和代码压缩的程序。 表 6.4. RTX 32P 指令类型的静态指令频率
FRAC LIFE MATH AVE
OP 48.40% 51.46% 44.72% 48%
CALL 28.48% 33.01% 35.64% 32%
EXIT 5.12% 6.41% 7.55% 6%
OP+CALL 0.00% 0.00% 0.00% 0%
OP+EXIT 0.00% 0.00% 0.00% 0%
CALL+EXIT 0.00% 0.00% 0.00% 0%
OP+CALL+EXIT 0.00% 0.00% 0.00% 0%
COND 3.52% 4.46% 4.04% 4%
LIT 14.48% 4.66% 8.05% 9%
LIT-OP 0.00% 0.00% 0.00% 0%
VARIABLE-OP 0.00% 0.00% 0.00% 0%
VARIABLE-OP-OP 0.00% 0.00% 0.00% 0%
Instructions: 1250 515 2422
OP-OP 0.00% 0.00% 0.00% 0%
表 6.4(a) 指令压缩关闭，操作码组合关闭
FRAC LIFE MATH AVE
OP 33.71% 35.78% 37.05% 36%
CALL 17.33% 21.94% 27.03% 22%
EXIT 1.47% 2.87% 2.39% 2%
OP+CALL 11.65% 21.15% 10.54% 14%
OP+EXIT 3.78% 4.70% 1.73% 3%
CALL+EXIT 1.05% 1.04% 4.02% 2%
OP+CALL+EXIT 0.42% 0.00% 1.17% 1%
COND 4.62% 6.00% 4.98% 5%
LIT 16.17% 4.18% 8.61% 10%
LIT-OP 2.83% 2.08% 1.32% 2%
VARIABLE-OP 5.46% 0.26% 1.01% 2%
VARIABLE-OP-OP 1.47% 0.00% 0.15% 1%
Instructions: 952 383 1965
OP-OP 2.73% 5.22% 1.98% 3%
表 6.4(b) 指令压缩打开，操作码组合关闭 RTX32P 使用 9 位的操作码、21 位的地址、2 位的控制字段。如果我们想假设一种优化的封装指令格式，我们可以如下设计：使用 11 位来指定操作码，有一个单独的子程序返回位，再有一个 23 位的子程序调用/ 返回格式。同样，如果我们假设这种指令格式可以通过把子程序返回与操作码结合或者通过用 JUMP 来代替子程序调用而使所有的子程序返回没有任何花费，那么这种假设的机器应该有 11 位或者 23 位可变字长度。但我们不用担心，因为这只是我们理论计算而得到的最小数值。 在优化的格式中，三个程序一起由 1952 位操作码组成（所有都是 11 位）， 1389 子程序调用（每个 23 位）， 565 个结合操作码 / 地址位（ 34 位），它们之和是 72640 位。 现在让我们来考虑一下在 RTX32P 上优化编译的程序，考虑每个指令都使用 32 位的固定长度编码，则有一些没有使用的余量，全部指令是 32 位的 3300 条，总计105600 位，存储器开销是 32960 位，或者比理论计算的结果要“浪费” 31% 的存储器。 当然，设计一个使用 11 位操作码和 23 位子程序调用的计算机是很整洁的。但更实际地考虑，我们应该看到在压缩版本中的程序“空白”操作码是 766 位（每个 9 位），“空白”子程序调用是 917 （每个 23 位），总数是 27985 位 -- 仅用 27% 的浪费就换来了 25% 执行指令的减少。所以我们说，就算是与可变长度指令相比，我们也是用相对低的成本就得到了很大的性能提升。 这一部分的测试中还有一个小问题，就是用于测试的程序都相对较小，程序执行了很复杂的操作，所以可以看到堆栈计算机程序是紧缩的，问题是很大的 Forth 程序难以得到。不过，所选择的程序包括了通常 Forth 代码的相关部分，从作者的观点看，如果能够得到更大的程序，结果也是可信的。 当然，我们也有一个办法来得到更大的程序，那就是使用传统的高级语言编译器的输出，但是，这类代码有完全不同的特点，因为程序员解决问题的方法在 Forth 和 C 、 FORTRAN 中是不同的，我们可以在第 7 章中再讨论这个问题。 6.4 堆栈管理策略由于堆栈计算机依赖于每个指令中对高速堆栈存储器的访问，所使用的堆栈存储器的特点就是至关重要的了。特别是随着处理器越来越快，问题就产生了：为了得到高性能，需要在片上安排多少堆栈存储器？对这个问题的回答是至关重要的，因为它决定了把存储器放到芯片上的这样一类高端堆栈处理器的成本和性能。 一个同等重要的问题是：如何管理程序存储器，特别是在多任务的环境中？ 6.4.1 评估堆栈尺寸：一个试验第一个问题是需要多少片上存储器作为堆栈，最好通过对不同的程序用不同大小的存储器来仿真。这种仿真测量的是由于堆栈上下溢出而产生的与存储器进行数据交换的数量。上溢时需要从硬件堆栈上拷贝数据元素到存储器，下溢时需要把数据元素从堆栈缓冲存储器拷贝回来。
FRAC LIFE MATH FIB HANOI QUEENS
# INSTRUCTIONS 2051600 1296143 6133519 880997 235665 140224
MAX STACK DEPTH 44 6 23 25 52 29
# STACK OPERANDS 3670356 1791638 11786764 1483760 446642 257320
# STACK SPILLS
FOR BUFFER SIZE:
0 3670356 1791638 11786764 1483760 446642 257320
2 838960 148448 3919622 370940 155656 41426
4 202214 4098 1313566 92732 69608 9216
8 39040 0 238020 13526 32752 512
12 10236 0 28300 1970 8184 196
16 3580 0 800 284 4088 64
20 1532 0 280 38 2040 22
24 636 0 0 2 1016 10
28 220 0 0 0 504 2
32 92 0 0 0 248 0
36 36 0 0 0 120 0
40 10 0 0 0 56 0
44 0 0 0 0 24 0
48 0 0 0 0 8 0
52 0 0 0 0 0 0
表 6.5. 花费在数据堆栈分裂上的存储器扩展周期
图 6.2 数据栈分裂 表 6.5 和图 6.2 给出了一个仿真结果，它对程序 Life、Hanoi、Frac、Fib 、 Math 和 Queens 花在数据堆栈分裂和恢复的存储器周期数进行监控。“TOY” 程序中的 Hanoi 和 Queens 不代表典型的程序，它们都是深度递归的，可以看成是堆栈程序的最坏情况。 分裂算法就是在堆栈缓冲区满时进行 PUSH 操作的情况下，每次从堆栈中分裂出一个数据元素和在堆栈空时执行 READ/POP 的情况下每次读出一个数据元素到堆栈中。仿真假设硬件自动地处理堆栈，并以每个存储器周期读或者写一个元素的代价完成。使用 RTX32P 指令集进行这个仿真，每个指令相当于那些硬连线处理器比如 RTX2000 的 2 倍复杂度，测量的周期数是存储器周期。仿真的目的是显示所期望的最佳行为，当然，在大多数实现中都需要约 3-4 倍的因子。 令人惊奇的是， Frac 程序几乎与 Hanoi 程序一样坏, 这是由于 Frac 在进行大量的定点除法的子除步骤时，每次都把6个元素 PUSH 到堆栈上。很明显，所有的递归程序都会在堆栈上产生大量的数据元素。 关于堆栈尺寸的好消息是对所有的应用程序，堆栈的上下溢出的存储器交换以指数方式减少。在堆栈缓冲区尺寸为 24 时，甚至 Hanoi 程序所产生的堆栈溢出也只有指令的 1% 。实际上，如果堆栈的尺寸达到 32 个元素时，几乎所有的程序都不会出现堆栈溢出情况。
FRAC LIFE MATH FIB HANOI QUEENS
# INSTRUCTIONS 2051600 1296143 6133519 880997 235665 140224
MAX STACK DEPTH 14 7 30 22 14 39
# STACK OPERANDS 725224 680676 3199170 185472 41056 53722
# STACK SPILLS
FOR BUFFER SIZE:
0 725224 680676 3199170 185472 41056 53722
2 326778 135608 1235678 57312 12310 26070
4 179938 118 642798 21890 2048 13306
8 27932 0 273686 3192 128 1158
12 132 0 57262 464 8 572
16 0 0 13442 66 0 314
20 0 0 1062 8 0 154
24 0 0 382 0 0 62
28 0 0 42 0 0 32
32 0 0 0 0 0 16
36 0 0 0 0 0 8
40 0 0 0 0 0 0
表 6.6. 用于返回栈分裂的存储器同期
图 6.3 返回栈分裂 表 6.6 和图 6.3 给出同样程序的返回栈分裂和恢复仿真结果。结果相似， Math 程序需要大量的返回栈。这是由于数学包为了在不同的系统之间保持可移植而严格地采用模块化方式编写，所以使用了大量的深层次的子程序嵌套。同时，Math 程序使用返回栈来存储大量的临时变量以便能在16位处理器上处理 48 位数据。 6.4.2 溢出处理现在我们已经考察了在程序执行时是如何发生堆栈上溢和下溢的，问题是如何处理它们呢？处理堆栈分裂有 4 个可能的方法：保证溢出永不发生；把它们作为灾难性的系统崩溃；使用按需请求的堆栈控制器；使用页式堆栈控制逻辑或者使用一个数据 CACHE 存储器。每种方法都有它自己的优势和弱势。 6.4.2.1 一个非常大的堆栈存储器解决堆栈问题的最简单的方法就是假设堆栈溢出从来都不会发生。这种方法初看起来好象很愚蠢，但它也有一些优点，使用这种策略的最好结果就是系统性能完全可以预测（没有堆栈分裂来减慢系统），也不需要任何的堆栈管理硬件。 这种方法使用大量的堆栈存储器以避免溢出。MISC 的 M17 就使用了这种方法，它只在程序存储器容量耗尽时才发生堆栈溢出。 NC4016 使用的方法是高速的片外存储器，它可以容纳几千个数据元素，这些处理器都是简单地忽略溢出问题。使用这种方法的价格是在片外存储器大小/速度和处理器速度之间的一个折衷。 在使用小容量片外存储器的情况下，这种方法把溢出作为一个系统崩溃的灾难性事件。在程序进行调试时，可以简单地告诉程序员说堆栈只能有 X 个元素，程序员有责任不超过这个限制。如果编写的程序很小、很简单， X 的值又大于 16 或者 32 ，这种方法也很实用。 WISC CPU/16 使用这种方法，把堆栈元素设为 256 ，这样就可以保持堆栈简单。 6.4.2.2 请求式单元素堆栈管理器让堆栈的溢出按一定的规则发生，处理这个问题最概念性的办法是使用一个请求式堆栈管理器，它按需要在堆栈和存储器之间移动单个元素。 为了实现这个策略，堆栈缓冲区按环形缓冲区构建，并有头和尾指针。另外还需要一个指向存储器的指针用于记录存储器中堆栈的栈顶位置。只要堆栈溢出，栈底缓冲区驻留的元素就被复制到存储器中，释放一个缓冲区位置。如果下溢，就从存储器中复制一个元素到缓冲区。这种技术只有在绝对需要时才由处理器移动元素，保持了堆栈流量的最小。 对这种技术可以做一些小的改进，堆栈管理器可以总是保持堆栈中几个元素的空或者满。这种管理可以利用空闲的存储器周期，并减少由于溢出而暂停的次数。不幸的是，这种小的改进在真正的堆栈计算机上可能没有什么价值，因为处理器总是用 100% 的时间使用程序存储器访问指令和数据，并没有给堆栈管理器剩下带宽。 请求式堆栈管理的好处是堆栈缓冲区元素总是可用的。因此，它适合于那些有芯片空间可以用于堆栈缓冲区的系统中。作为一个附加的好处，堆栈的上下溢出在整个程序的执行过程的每个指令中最大只有 2 次，这就是数据栈分裂同时子程序返回溢出。这种高性能的代价是相对复杂的硬件控制电路和每个堆栈都需要三个计数器来实现这个策略。 FRISC3 的堆栈管理策略与请求式策略很像。这个系统对此有了深入的研究，一个通用化的算法称为 cutback-K algorithmwas 由 Hasegawa & Shigei (1985)提出， Stanley & Wedig (1987) 也讨论了 RISC 计算机的栈顶元素缓冲管理策略。 6.4.2.3 页式堆栈管理与请求式堆栈管理策略不同的一种方法是在堆栈上溢或者下溢时产生一个中断，然后用软件来管理堆栈分裂。这种方法比请求式管理所使用的硬件要少，但是要求更大一些的堆栈缓冲区来减少中断的频率。 这种方法的一个通常做法是使用“限制寄存器”来指向堆栈缓冲区空间顶部和底部的的附近位置。当一个指令引起堆栈指针小于下溢指针时，相当于全部缓冲区一半的元素将从程序存储器中复制到堆栈中。当一个指令引起堆栈指针越过上溢指针时，相当于堆栈尺寸一半的元素被复制到程序存储器中。 页式请求策略允许大堆栈存储器的任意尺寸段在一个时间片中用于不同的过程。由此，堆栈存储器作为特殊存储器的一段出现，而不作为环形缓冲区的方式出现。因此在实际应用中，一个堆栈溢出实际上是复制缓冲区的一半到存储器中，然后在堆栈缓冲区的开始位置重新定位另一半。 页式管理方法的成本按消耗于移动元素的存储器周期计算是请求式管理的2倍。缓冲区的尺寸也应该是请求式的2倍才能保证在上溢和下溢之间有相同的 PUSH 和 POP 数，不过在实际应用中这种增大的尺寸几乎没有什么价值。 使用这种方法有趣的一点是程序上下溢出的编程风格不太可能受到欢迎，因为如果堆栈的大小是 32 个元素，则就完全不再需要它们。对于那些超过了它们缓冲区尺寸的程序，这种方法提供了一种降级。依靠这种方法，一个病态的程序也可以运行（尽管很慢），而操作系统可以产生一个警告信息来指示错误的程序。 RTX2000 和 RTX32P 都使用了页式方法进行堆栈管理。 6.4.2.4 联合 CACHE许多传统处理器管理程序堆栈的方法是使用一个传统的数据 CACHE ，通常映射到程序存储器空间。这种方法与我们前面讨论的堆栈计算机相比，应用了非常复杂的硬件，但是并没有提供任何优点，因为堆栈计算机并不经常随意地访问它的元素。对于可变长度的数据结构比如串和记录，当这些内容像 C 或者 ADA 程序环境定义的那样 PUSH 到“堆栈”上时也能提供一些好处。 其它有关堆栈管理的有趣论文是： Blake (1977), Hennesy (1984), Prabhala & Sethi (1977), and Sites (1979). 6.5 中断和多任务中断处理的性能有三个组成部分：第一个是处理器收到中断和处理器开始执行中断服务程序之间的时间，这个延迟称为中断潜伏。 第二中断处理的性能组成部分是中断处理时间，这个时间量是处理器实际花费的保存中断任务机器状态并开始执行中断服务程序的时间。通常需要保存的机器状态都很少，假设中断服务程序可以通过只保存那些准备使用的寄存器而使开销最小。有时，我们见到术语“interrupt latency”，它通常是指前面两项之和。 中断服务性能的第三个部分是我们所说的状态保存开销。这些是为了保存那些没有被机器中断处理逻辑自动存储的、但是在中断服务程序中必须使用的机器寄存器的时间。状态保存可以差异很大，依赖于中断服务程序的复杂度。在极端的情况下，状态保存开销需要切换多任务的全部上下文。 当然，恢复这些机器状态并退出中断服务程序的开销也决定着系统的性能。我们不在这里明确地讨论，因为它们差不多等于状态保存时间（因为保存的每样东西都必须恢复），但是它们对中断响应的时间要求并不重要。 6.5.1 中断响应延迟CISC 计算机可以有需要花费很长时间才能完成的指令，极大地延长了中断的响应。堆栈计算机像 RISC 计算机一样可以有很快的中断响应延迟，这是由于许多堆栈计算机指令只是单周期长，所以按最坏的情况来考虑，在中断识别和中断处理之间只有几个时钟的延迟。 然而，一但中断被处理， RISC 和堆栈计算机的差异就开始表现出来。 RISC 计算机必须通过一个流水线来保存识别中断时的过程，在返回时恢复过程流水线，以避免丢失特别指令的信息。另一方面，堆栈计算机没有指令执行流水线，所以只需要保存正在执行的下一条指令的地址。这意味着可以把中断视为一个由硬件产生的过程调用。当然，因为过程调用很快，所以中断处理时间很短。 6.5.1.1 指令重新启动堆栈响应延迟可能有一个问题，这就是流化指令和微码循环。 流化指令用于重复执行一个操作比如写栈顶元素到存储器中。这些指令使用 NC4016 和 RTX2000 的重复指令、 M17 的指令缓冲、 CPU/16 RTX32 的微码循环来编写。这些原语非常有用，它们可以用来构建高效率的字符串处理原语和堆栈上下溢出服务子程序。现在的问题是在多数情况下，这些指令也是不可中断的。 一个解决办法是通过外部中断逻辑使得这些指令可中断，它只是很少地增加了处理器的复杂性。一个潜在的硬件问题是非堆栈处理器也用这种解决方法来保存中间结果，对于一个堆栈处理器没有任何问题，因为中间结果保存在堆栈上，它是一个在中断期间保存状态的理想机制。 堆栈处理器的另一个方法是使用软件限制用于流指令的重复次数。这就意味着如果有效100 个字符的块需要在存储器中移动，可以通过每组8个字符的几个组来完成。这就使得在不牺牲性能的情况下满足断响应时间的要求。这是在绝对计算机效率（使用长的流指令）和中断响应时间之间的一个折衷。 在微码机器中，折衷与此相似，然而，在 RTX32P 的商业版本中，有一个非常简单的微码策略做得更好。这种策略是使用一个微码可见的条件位指示是否有中断未决。在每个微码循环的迭代中都要测试这个中断未决位，但是这并不消耗任何执行时间。如果没有未决的中断，则进行一次循环。如果有中断未决，流指令的地址就被 PUSH 到返回栈上作为中断返回的地址并允许中断程序执行。只要流指令所有的状态都保存在堆栈上（它只是一个简单的操作比如字符块移动），则这种方法在处理中断时只有很小的开销，而在正常的指令执行时却没有任何开销。 6.5.2 轻量级中断让我们考察不同的中断所需要的保存状态的程度：快速中断、多任务的轻量级线程中断和完全的上下文切换。 快速中断是运行时最常见到的中断。这些中断做的事情是为时间计数器增加几个毫秒，或者从输入口拷贝几个字节到存储器。传统的计算机处理这种中断时，它们通常都需要保存两、三个寄存器到程序存储器以便在寄存器文件中腾出工作空间。在堆栈计算机上，没有任何状态信息需要保存，中断服务程序可以简单地把它的信息 PUSH 到栈顶而不干扰被中断程序的信息。所以对于快速中断来说，堆栈计算机的状态信息保存开销为0。 轻量级线程是多任务系统中的任务，它的执行策略与我们刚才描述的中断相同。它们可以得到多任务的收益而不需要全过程的开始和结束成本。一个堆栈处理器可以简单地要求每个任务执行很短的指令序列来简单地实现轻量级线程，这可以被称为非剥夺或者是协同的任务管理。如果每个任务在它的操作期间都不把参数留在堆栈上，则在任务之间就没有上下文切换的开销。这种方法的多任务成本本质上是 0 ，因为一个任务只是在程序的一个逻辑转换点上把控制交给任务管理器，那里堆栈应该是空的。 从这两个例子可以看出，在堆栈计算机上，中断处理和轻量级线程多任务是非常廉价的。留下的唯一问题是需要上下文切换才能完成的全过程的、可剥夺的多任务。 6.5.3 上下文切换上下文切换开销是大家常说的“堆栈计算机不能很好地运行多任务”的一个问题。这种观点背后的的原因通常是基于这样的想法：需要把大量的堆栈缓冲区保存到程序存储器中。但是说堆栈计算机在运行多任务时比其它计算机机性能更差的说法是可笑的。 上下文切换对所有的任务系统来说都是潜在的开销，在使用 CACHE 的 RISC 和 CISC 计算机中，上下文切换的开销可能比厂商说的更昂贵，上下文切换之后还有一个隐藏的结果是由于 CACHE 失配而带来的性能恶化。 RISC 计算机还有很大的寄存器文件，它们也严格地需要面对堆栈计算机的同样问题。而 RISC 计算机的一个缺点是由于它们对寄存器的访问是随机的，所以每次必须保存所有的寄存器（或者加入复杂的硬件来检测哪个寄存器正在使用），但是堆栈计算机却可以只保存堆栈缓冲区的活动记录。 6.5.3.1 一个上下文切换的实验表 7 给出了从追踪驱动仿真器得到的数据，它是 Forth 程序在一个上下文切换的环境中花费在保存和恢复数据堆栈元素的存储器器周期数。程序仿真 Queen、 Hanoi和 Quick-sort 。对于 Queen 和 Hanoi 使用小的 N 值以保持仿真时间合理。堆栈上下溢出和上下文切换的影响同时被测量，因为在这样的环境中它们是严重地交织在一起的。 表 6.7 对于不同频率上下文切换和不同堆栈尺寸分裂的存储器扩展周期
Combination of Queens, Qsort, Hanoi
# Instructions = 36678
Average stack depth = 12.1
Maximum stack depth = 36
Buffer
Size timer=100 timer=500 timer=1000 timer=10000
2 17992 16334 16124 15916
4 12834 9924 9524 9214
8 8440 3950 3430 2910
12 10380 3944 3068 2314
16 11602 2642 1620 632
20 12886 3122 1846 626
24 13120 2876 1518 330
28 14488 3058 1584 242
32 15032 3072 1556 124
36 15458 3108 1568 82
表 6.7(a) 页式缓冲区管理 BufferSize timer=100 timer=500 timer=1000 timer=10000 2 26424 24992 24798 24626 4 11628 8912 8548 8282 8 7504 3378 2762 2314 12 6986 1930 1286 630 16 7022 1876 1144 322 20 7022 1852 1084 180 24 7022 1880 1066 124 28 7022 1820 1062 90 32 7022 1828 1060 80 36 7022 1822 1048 80 表 6.7(b) 请求式缓冲区管理
图 6.4 页式堆栈管理的开销 图 6.4 – 页式管理的开销 表 6.7A 和图 6.4 给出了页式管理的结果。文字"xxx CLOCKS/SWITCH" 指示在上下文切换之间的时钟数，在上下文切换之间的时钟为 100 时，用在管理堆栈上的存储器周期随着缓冲区尺寸的增加而减少。这是由于在程序访问堆栈的同时减少了分裂速率的结果。然而，在堆栈尺寸增加到 8 个元素时，存储器交换的流量增加，因为随着缓冲区的增大，在上下文切换时的存储器复制是一个常数。 注意程序在上下文切换之间为 500 个时钟周期的行为，甚至在这种相对高的速率下（它对应于在 10MHZ 的处理器上每秒 20 000 次的上下文切换 -- 在实际应用中这个速率是太高了），对于堆栈缓冲区尺寸大于 12 个元素情况下，花在上下文切换上的成本也仅仅只有每个指令 0.08 个时钟周期。因为在实际的经验中，每个指令没有上下文切换开销时平均 1.688 个时钟周期，这只有 4.7% 的开销。在上下文切换之间达到 10000 个时钟时（ 1 毫秒一次上下文切换），开销小于 1% 。 怎么可能有这样低的开销呢？一个原因是执行这三个深度递归的的程序时，平均堆栈深度只有 12.1 个元素。这就意味着堆栈从来就不会有很多的信息，在上下文切换只需要保存很少的信息。事实上，与 12 个寄存器的 CISC 计算机相比，在这个实验中的堆栈计算机仿真实际在上下文切换中需要保存的状态比 CISC 更少。
图 6.5 请求式堆栈管理的开销 表 6.7B 和图 6.5 给出了运行请求式堆栈管理算法时的仿真结果。在这些结果中，多于 12 元素的 100- 周期间隔曲线的抬升在堆栈缓冲区中是不存在的。这是由于当恢复机器状态时，堆栈并不需要重新填充，而只是在程序执行时以请求的方式填充。对于合理的上下文切换频率（少于每秒 1000 次），请求式策略比页式管理略好，但并不是压倒性的。 6.5.3.2 为多任务而有多个堆栈空间堆栈计算机还可以使用一种方法处理上下文切换，甚至对任何成本都可以接受。所有的程序不是使用单一的巨大的堆栈，而是为高优先级/时间紧迫的程序部分提供它们自己的堆栈。这意味着每个过程都使用一个堆栈指针和堆栈界限寄存器来创建一个它自己使用的堆栈。考虑上下文切换，过程管理只是简单地保存当前的堆栈指针，因为它已经知道了堆栈的界限。当新的堆栈指针值和堆栈限制寄存器装入时，新的过程就做好了准备。不需要为复制堆栈元素而花费任何时间。 在典型的情况下，大多数程序所需要的堆栈存储器都非常小，通过设计很小的、时间短而紧迫的过程可以进一步保证。所以，就算是一个适度合理的 128 个元素的堆栈缓冲区也可以按每 32 个元素分配成 4 个堆栈。如果一个多任务系统需要多于4个过程，其中的一个可以设计成低优级堆栈缓冲区，它在多个低优级任务之间通过存储器复制而共享。 从这些讨论中我们可以看到，堆栈处理器的概念之大以至于不能用一句话来说明多任务的高效率。事实上，在许多情况下，堆栈处理器可以比其它的传统计算机在多任务和中断处理方面做得更好。 Hayes and Fraeman (1988) 已经独立地得到了 FRISC3 上堆栈分裂和上下文切换的结果，它与本章的结果相似。
|
||||||
|
||||||
