Stack Computers: the new wave © Copyright 1989, Philip Koopman, All Rights Reserved.

Contents

Foreword

Preface

CHAPTER 1: Introduction and Review

• 1.1 OVERVIEW
• 1.2 WHAT IS A STACK?
  • 1.2.1 Cafeteria tray example
  • 1.2.2 Example software implementations
  • 1.2.3 Example hardware implementations
• 1.3 WHY ARE STACK MACHINES IMPORTANT?
• 1.4 WHY ARE STACKS USED IN COMPUTERS?
  • 1.4.1 Expression evaluation stack
  • 1.4.2 The return address stack
  • 1.4.3 The local variable stack
  • 1.4.4 The parameter stack
  • 1.4.5 Combination stacks
• 1.5 THE NEW GENERATION OF STACK COMPUTERS
• 1.6 HIGHLIGHTS FROM THE REST OF THE BOOK

CHAPTER 2: A Taxonomy of Hardware Stack Support

• 2.1 THE THREE AXIS STACK DESIGN SPACE
  • 2.1.1 Single vs. multiple stacks
  • 2.1.2 Size of stack buffers
  • 2.1.3 0-, 1-, and 2-operand addressing
• 2.2 TAXONOMY NOTATION AND CATEGORIES
  • 2.2.1 Notation
  • 2.2.2 List of the categories in the design space
• 2.3 INTERESTING POINTS IN THE TAXONOMY.

CHAPTER 3: Multiple-stack, 0-operand Machines

• 3.1 WHY THESE MACHINES ARE INTERESTING
• 3.2 A GENERIC STACK MACHINE
  • 3.2.1 Block diagram
    • 3.2.1.1 Data bus
    • 3.2.1.2 Data stack
    • 3.2.1.3 Return stack
    • 3.2.1.4 ALU and top-of-stack register
    • 3.2.1.5 Program counter
    • 3.2.1.6 Program memory
    • 3.2.1.7 I/O
  • 3.2.2 Data operations
    • 3.2.2.1 Reverse Polish Notation
    • 3.2.2.2 Arithmetic and logical operators
    • 3.2.2.3 Stack manipulation operators
    • 3.2.2.4 Memory fetching and storing
    • 3.2.2.5 Literals
  • 3.2.3 Instruction execution
    • 3.2.3.1 Program Counter
    • 3.2.3.2 Conditional branching
    • 3.2.3.3 Subroutine calls
    • 3.2.3.4 Hardwired vs. microcoded instructions
  • 3.2.4 State changing
    • 3.2.4.1 Stack overflow/underflow interrupts
    • 3.2.4.2 I/O service interrupts
    • 3.2.4.3 Task switching
• 3.3 OVERVIEW OF THE FORTH PROGRAMMING LANGUAGE
  • 3.3.1 Forth as a common thread
  • 3.3.2 The Forth virtual machine
    • 3.3.2.1 Stack architecture/RPN
    • 3.3.2.2 Short, frequent procedure calls
  • 3.3.3 Emphasis on interactivity, flexibility

CHAPTER 4: Architecture of 16-bit Systems

• 4.1 CHARACTERISTICS OF 16-BIT DESIGNS
  • 4.1.1 Good fit with the traditional Forth model
  • 4.1.2 Smallest interesting width
  • 4.1.3 Small size allows integrated embedded system
• 4.2 ARCHITECTURE OF THE WISC CPU/16
  • 4.2.2 Block diagram
  • 4.2.3 Instruction set summary
  • 4.2.4 Architectural features
  • 4.2.5 Implementation and featured application areas
• 4.3 ARCHITECTURE OF THE MISC M17
  • 4.3.2 Block diagram
  • 4.3.3 Instruction set summary
  • 4.3.4 Architectural features
  • 4.3.5 Implementation and featured application areas
• 4.4 ARCHITECTURE OF THE NOVIX NC4016
  • 4.4.1 Introduction
  • 4.4.2 Block diagram
  • 4.4.3 Instruction set summary
  • 4.4.4 Architectural features
  • 4.4.5 Implementation and featured application areas
• 4.5 ARCHITECTURE OF THE HARRIS RTX 2000
  • 4.5.1 Introduction
  • 4.5.2 Block diagram
  • 4.5.3 Instruction set summary
  • 4.5.4 Architectural features
  • 4.5.5 Implementation and featured application areas
  • 4.5.6 Standard cell designs

CHAPTER 5: Architecture of 32-bit Systems

• 5.1 WHY 32-BIT SYSTEMS?
• 5.2 ARCHITECTURE OF THE FRISC 3 (SC32)
  • 5.2.1 Introduction
  • 5.2.2 Block diagram
  • 5.2.3 Instruction set summary
  • 5.2.4 Architectural features
  • 5.2.5 Implementation and featured application areas
• 5.3 ARCHITECTURE OF THE RTX 32P
  • 5.3.1 Introduction
  • 5.3.2 Block diagram
  • 5.3.3 Instruction set summary
  • 5.3.4 Architectural features
  • 5.3.5 Implementation and featured application areas
• 5.4 ARCHITECTURE OF THE SF1
  • 5.4.1 Introduction
  • 5.4.2 Block diagram
  • 5.4.3 Instruction set summary
  • 5.4.4 Architectural features
  • 5.4.5 Implementation and featured application areas

CHAPTER 6: Understanding Stack Machines

• 6.1 AN HISTORICAL PERSPECTIVE
  • 6.1.1 Register vs. non-register machines
  • 6.1.2 High level language vs. RISC machines
• 6.2 ARCHITECTURAL DIFFERENCES FROM CONVENTIONAL MACHINES
  • 6.2.1 Program size
  • 6.2.2 Processor and system complexity
  • 6.2.3 Processor performance
    • 6.2.3.1 Instruction execution rate
    • 6.2.3.2 System Performance
    • 6.2.3.3 Which programs are most suitable?
  • 6.2.4 Program execution consistency
• 6.3 A STUDY OF FORTH INSTRUCTION FREQUENCIES
  • 6.3.1 Dynamic instruction frequencies
  • 6.3.2 Static instruction frequencies
  • 6.3.3 Instruction compression on the RTX 32P
    • 6.3.3.1 Execution speed gains
    • 6.3.3.2 Memory size cost
• 6.4 STACK MANAGEMENT ISSUES
  • 6.4.1 Estimating stack size: An experiment
  • 6.4.2 Overflow handling
    • 6.4.2.1 A very large stack memory
    • 6.4.2.2 Demand fed single-element stack manager
    • 6.4.2.3 Paging stack manager
    • 6.4.2.4 An associative cache
• 6.5 INTERRUPTS AND MULTI-TASKING
  • 6.5.1 Interrupt response latency
    • 6.5.1.1 Instruction restartability
  • 6.5.2 Lightweight interrupts
  • 6.5.3 Context switches
    • 6.5.3.1 A context switching experiment
    • 6.5.3.2 Multiple stack spaces for multi-tasking

CHAPTER 7: Software Issues

• 7.1 THE IMPORTANCE OF FAST SUBROUTINE CALLS
  • 7.1.1 The importance of small procedures
  • 7.1.2 The proper size for a procedure
  • 7.1.3 Why programmers don't use small procedures
  • 7.1.4 Architectural support for procedures
• 7.2 LANGUAGE CHOICE
  • 7.2.1 Forth: strengths and weaknesses
  • 7.2.2 C and other conventional languages
  • 7.2.3 Rule-based systems and functional programming
• 7.3 UNIFORMITY OF SOFTWARE INTERFACES

CHAPTER 8: Applications

• 8.1 REAL TIME EMBEDDED CONTROL
  • 8.1.1 Requirements of real time control
  • 8.1.2 How stack machines meet these needs
• 8.2 16-BIT VERSUS 32-BIT HARDWARE
  • 8.2.1 16-Bit hardware often best
  • 8.2.2 32-Bit hardware is sometimes required
• 8.3 SYSTEM IMPLEMENTATION APPROACHES
  • 8.3.1 Hardwired systems vs. microcoded systems
  • 8.3.2 Integration level and system cost/performance
• 8.4 EXAMPLE APPLICATION AREAS

CHAPTER 9: The Future of Stack Computers

• 9.1 SUPPORT FOR CONVENTIONAL LANGUAGES
  • 9.1.1 Stack frames
  • 9.1.2 Aliasing of registers and memory
  • 9.1.3 A strategy for handling stack frames
  • 9.1.4 Conventional language execution efficiency
• 9.2 VIRTUAL MEMORY AND MEMORY PROTECTION
  • 9.2.1 Memory protection is sometimes important
  • 9.2.2 Virtual memory is not used in controllers
• 9.3 THE USE OF A THIRD STACK
• 9.4 THE LIMITS OF MEMORY BANDWIDTH
  • 9.4.1 The history of memory bandwidth problems
  • 9.4.2 Current memory bandwidth concerns
  • 9.4.3 The stack machine solution
• 9.5 TWO IDEAS FOR STACK MACHINE DESIGN
  • 9.5.1 Conditional subroutine returns
  • 9.5.2 Use of the stack for holding code
• 9.6 THE IMPACT OF STACK MACHINES ON COMPUTING

Appendix A: A Survey of Computers with Hardware Stack Support

• AADC
• AAMP
• ACTION PROCESSOR
• AEROSPACE COMPUTER
• ALCOR
• AN ALGOL MACHINE
• AM29000
• APL LANGUAGE
• BUFFALO STACK MACHINE
• BURROUGHS MACHINES
• CALTECH CHIP
• CRISP
• DRAGON
• EM-1
• EULER
• FORTH ENGINE
• FORTRAN MACHINE
• FRISC 3
• G-MACHINE
• GLOSS
• HITAC-10
• HP300 & HP3000
• HUT
• ICL2900
• INTEL 80x86
• INTERNAL MACHINE
• IPL-VI
• ITS (Pascal)
• KDF-9
• KOBE UNIVERSITY MACHINE
• LAX2
• LILITH
• LISP MACHINES
• MCODE
• MESA
• MF1600
• Micro-3L
• MICRODATA 32/S
• MISC M17
• MOTOROLA 680x0
• MU5
• NC4016
• NORMA
• OPA (Pascal)
• PASCAL MACHINE
• PDP-11
• POMP PASCAL
• PSP
• PYRAMID 90X
• QFORTH
• REDUCTION LANGUAGE MACHINE
• REKURSIV
• RISC I
• ROCKWELL MICROCONTROLLERS
• RTX 2000
• RTX 32P
• RUFOR
• SF1
• SOAR
• SOCRATES
• SOVIET MACHINE
• SYMBOL
• TRANSPUTER
• TM
• TREE MACHINE
• VAUGHAN & SMITH'S MACHINE
• WD9000 P-ENGINE
• WISC CPU/16
• WISC CPU/32
• Other references

Appendix B: A Glossary of Forth Primitives

Appendix C: Unabridged Instruction Frequencies

Bibliography

On-Line Supplement (may be under construction)

Publication Notes & Copyright Notice

Phil Koopman -- koopman@cmu.edu