Generic Stack Assembly Language Simulation

written by Teresa Carrigan


Top

WHAT IS IT?

This is a model of a generic zero-address computer, also known as a stack machine. The model animates the fetch-execute cycle as well as the stack. The user may choose to have the program show either the numeric contents of each memory location and item on the stack, or the algebraic expression. This allows students to test their stack machine programs to see if the programs correctly implement the assigned expression. When run from a website, the user may choose one of four sample programs, or may type in a program. When run from NetLogo, the user also may browse to select a program saved in a textfile. Please note that "BROWSE" does NOT work from an applet!

Top

HOW IT WORKS

An assembly language program must be assembled, which constucts a symbol table. Memory locations mentioned in the program are shown on the right. The CPU contains a program counter, instruction register, CC register, stack, and a data path that connects the parts of the CPU with each other and to main memory (on the right).

The fetch-execute cycle looks at the contents of the program counter to determine where to look for an instruction, then asks the bus to fetch the instruction in that location. The bus returns with the instruction, placing it in the instruction register. The program counter is incremented, so that it points to the next instruction, and the instruction in the instruction register is decoded to determine what to do with it. If the instruction mentions either a variable in the symbol table or a memory location, then the bus must fetch the operand. Finally, the instruction is executed. If the instruction is not a halt, then the cycle repeats.

A generic stack machine assembly language has only six operations: Push, Pop, Add, Sub, Mul, and Div. Push adds an item to the top of the stack, then increments the stack pointer. Pop removes the item at the top of the stack. This model also allows a Halt operation, to better illustrate the fetch-execute cycle.

Top

HOW TO USE IT

First, choose the program to load. This model comes with four sample programs, but you can choose to type in your own program or load a program that has been saved to a textfile. Please note that an applet can't load a textfile.

The contents of all the memory locations will be randomized, based on the random-memory slider. For example, if the slider is set at 25, each memory location will contain a random number from -25 to +25. Changing this slider only effects the model when setup is pressed.

Click setup to load the program and display the stack machine. You may now click either Step or Run to show the animation.

Step animates the current line of the program loaded. You can press this repeatedly until the program halts or runs out of lines to be executed.

Run animates the remainder of the program loaded. To run it again, you must press Setup.

Interrupt sets an interrupt flag, and when the current fetch-execute cycle finishes, the cycle stops until either the step or run button is clicked. The next instruction will be the one that would have been processed if the interrupt had not occurred.

Reset allows you to clear everything and start from scratch. Setup is supposed to do this for you.

What-to-show lets the user decide what the labels of the turtles and patches will show. For example, if set at "contents" then the memory locations will show their contents, if set at "address" then the memory locations will show their addresses, and if set at "expression" then the stack items and memory locations will show algebraic expressions that have been used to calculate the values stored in them. When you make a change in What-to-show, press the "change what shows" button to activate the change. If you do not press the button, eventually the stack machine will notice and activate the change for you.

The Slow-me-down slider allows the user to adjust the animation speed. At zero, the program runs so fast that you only see the final display. If you are testing a program, then .05 is a good setting. If you are studying the fetch-execute cycle or how a stack machine works, then .1 or higher would be better.

The Console monitor gives messages about what is happening, including any error messages. The Explanation monitor gives the steps of the fetch-execute cycle as they are happening.

Top

THINGS TO NOTICE

Every time you Push an item, the stack gets one more item on top. For every time you Pop, Add, Sub, Mul, or Div, the stack loses one item.

What happens when you try to Pop and the stack is empty? What happens when you have a single item on the stack, and you try to Add? When you press Sub, how does the stack determine which item is subtracted?

When you push a number with a # in front of it, the number gets put on the stack without having to fetch an operand. When there is no # in front of the number, the bus fetches an operand that is the contents of that address, so the number pushed on the stack is probably completely different from what you get if there is #.

Notice that the program counter is incremented as soon as the operand is fetched, before the instruction is executed.

The CC register is updated after execution of each instruction. If the result is positive, then CC is changed to "P +"; if negative, then "N -" and if zero, then "Z 0".

Top

THINGS TO TRY

Load one of the demo programs, then click Run. Watch the fetch-execute cycle working with each line of the program, and what the commands do to the stack. Run the same program twice, once with "What-to-show" set to expression, and again with it set to contents. Write down the values of each variable before running the program, and the values after running, then check against the expression stored; does the program do the calculations correctly?

What happens when you divide and there is a remainder?

What happens when the top of the stack is a zero, and the next command is div?

What happens when there is a Halt command in the middle of a program?

Run a program, and in the middle of it click interrupt. When does the CPU notice the interrupt? When does it stop to handle it?

Write your own program, and test it using the model.

Top

EXTENDING THE MODEL

Add another operator to the possible commands, such as exponentiation, or sin.

Show the memory locations of the lines of the program as well as the variables. Be sure to show the bus stopping at the correct line when it fetches an instruction.

Modify push to limit the number of items that can be pushed on the stack (to prevent wrapping).

Allow labels on lines, so that you can implement the various jump and branch opcodes.

Add MAR and MBR registers, and separate the datapath into the internal bus, address bus, and data bus.

Show the ALU, with the top two items of the stack going into it with the opcode being executed, and the result coming out then going on the top of the stack.

Top

NETLOGO FEATURES

In several places, the bus turtle uses while [ pcolor-of (patch-ahead 1) = red ] [ wait slow-me-down fd 1 ] to follow the datapath in a straight line, slowly enough that the animation can be seen.

The setup-file procedure lets the user browse to find a saved textfile, opens it, and then reads the contents of the file into a list, with each line a separate list item.

upper! converts a string to upper-case.

The four demo programs had to be hard-coded as lists, because an applet won't allow them to be read from textfiles.

Top

RELATED MODELS

Top

CREDITS AND REFERENCES

This model was written by Teresa W. Carrigan, 2004. James Steiner graciously provided the four procedures at the bottom, that allowed easy conversion of a string to either upper or lower case.

Permission to use, modify or redistribute this model is hereby granted, provided that both of the following requirements are followed:

  1. this copyright notice is included.
  2. this model will not be redistributed for profit without permission from Teresa Carrigan.
Contact Teresa Carrigan for appropriate licenses for redistribution for profit.

To refer to this model in academic publications, please use: Carrigan, T. (2004). Generic Stack Assembly Language Simulation model. Blackburn College, Carlinville, IL.

In other publications, please use: Copyright 2004 by Teresa W. Carrigan. All rights reserved.

Top

FOR MORE INFORMATION

For more information on Stack Machines, see one of these textbooks:
  1. Stallings, W. Computer Organization and Architecture: Designing for Performance, Sixth Edition, Prentice Hall, pages 371-376.
  2. Tanenbaum, A. Structured Computer Organization, Fourth Edition, Prentice Hall, pages 338-341.
  3. Null, L. and Lobur, J. Essentials of Computer Architecture, First Edition, Jones & Bartlett. pages 204-207.

For more information on the Fetch-Execute cycle, see one of these textbooks:
  1. Dale, N. and Lewis, J. Computer Science Illuminated, Second Edition, Jones and Bartlett, pages 132-134.
  2. Null, L. and Lobur, J. Essentials of Computer Architecture, First Edition, Jones and Bartlett, pages 28-29, 166-167.

Home

Applets on this website were written by Teresa Carrigan in 2004, for use in computer science courses at Blackburn College, with the exception of the Fireworks applet. The applets made with NetLogo require Java 1.4.1 or higher to run. The applets made with NetBeans require Java 1.4.2 or higher to run. Applets might not run on Windows 95 or Mac OS 8 or 9. You may obtain the latest Java plugin from Sun's Java site.