© Copyright 1989,
Philip Koopman,
All Rights Reserved.
Stack Computers: the new wave
© Copyright 1989,
Philip Koopman,
All Rights Reserved.
Chapter 6. Understanding Stack Machines
The debate between designers of machines with hardware supported stacks and other designers has a long history. This debate can be split into two major areas: the debate between register-based and non-register-based machine designers, and the debate between high level language machine designers and RISC designers. While we can not hope to put forth definitive answers to the questions raised in these debates, the ideas presented in the references given are worthy of consideration by the interested reader.
The debate on whether to design a machine that makes registers explicitly available to the assembly language programmer dates back to design decisions made in the late 1950s. The existence of the stack-based KDF.9 computer (Haley 1962) is evidence that computer architects had begun thinking of alternatives to the standard register-based way of designing computers many years ago.
The debate on whether or not to use register-based machines involves a number of alternatives. These alternatives include: pure stack based machines, single-operand stack based machines (also called stack/accumulator machines), and storage-to-storage machines.
The pure stack machines, which fall into the SS0, MS0, SL0, and ML0 taxonomy categories, are exceedingly simple. An obvious argument in favor of stack-based machines is that expression evaluation requires the use of a stack-like structure. Register-based machines spend some of their time emulating a stack-based machine while evaluating expressions. However, pure stack machines may require more instructions than a stack/accumulator machine (SS1, MS1, SL1, ML1 taxonomy categories) since they cannot fetch a value and perform an arithmetic operation upon that value at the same time. The astute reader will notice that the 32-bit stack machines discussed in Chapter 5 use multiple-operation instructions such as "Variable @ +" to compensate for this problem to a large degree.
Storage-to-storage machines, in which all instruction operands are in memory, are seen as being valuable in running high level languages such as C and Pascal. The reason given for this is that most assignment statements in these languages have only one or two variables on the right hand side of the assignment operator. This means that most expressions can be handled with a single instruction. This eliminates instructions which otherwise would be required to shuffle data into and out of registers. The CRISP architecture (Ditzel et al. 1987a, 1987b) is an example of a sophisticated storage-to-storage processor.
Some of the most frequently cited references in this debate are a sequence of articles that appeared in Computer Architecture News: Keedy (1978a), Keedy (1978b), Keedy (1979), Myers (1977), Schulthess & Mumprecht (1977), and Sites (1978). These articles do not address all the issues and are dated in some respects. Nonetheless, they form a good starting point for those who are interested in the historical roots of this ongoing debate.
A related debate is that between proponents of high level language machines and the RISC philosophy of machine design.
High level language machines may be thought of as one of the advanced evolutionary paths of the CISC philosophy. These machines have potentially very complex instructions that map directly onto the functions of one or more high level languages. In some cases, the output of the front end of a compiler is used to generate an intermediate level code that is executed directly by the machine, such as P-code for Pascal or M-code for Modula-2. The ultimate extension of this philosophy is probably the SYMBOL project (Ditzel & Kwinn 1980) which implemented all system functions in hardware, including program editing and compilation.
The RISC philosophy of high level language support is one of providing the simplest possible building blocks for the compiler to use in synthesizing high level language operations. This usually involves code sequences of loads, stores, and arithmetic operations to implement each high level language statement. RISC proponents claim that these collections of code sequences can be made to run faster on a RISC machine than equivalent complex instructions on a CISC machine.
The stack machine design philosophy falls somewhere in between the philosophies of high level language machine design and RISC design. Stack machines provide very simple primitives which may be executed in a single memory cycle, in the spirit of the RISC philosophy. However, efficient programs on stack machines make extensive use of application specific code that is accessed via cheap subroutine calls. This collection of subroutines may be thought of as a virtual instruction set that is tailored to the needs of high level language compilers, without requiring complicated hardware support.
A good sampling of references on the topic of high level language machines versus RISC machines is: Cragon (1980), Ditzel & Patterson (1980), Kavipurapu & Cragon (1980), Kavi et al. (1982), Patterson & Piepho (1982), and Wirth (1987).
Phil Koopman --
koopman@cmu.edu
NEXT SECTION