Little man computer
From Wikipedia, the free encyclopedia
The Little Man Computer (LMC) was created by Dr. Stuart Madnick as an instructional model. The LMC models a simple von Neumann architecture computer, so it has all of the basic features of a modern computer. The LMC can be programmed in machine (albeit usually in decimal) or assembly code.
Contents |
[edit] LMC architecture
The LMC model is based on the concept of a little man locked in a small room. At one end of the room, there are 100 mailboxes (Memory), numbered 0 to 99, that can each contain a 3 digit instruction. Furthermore, there are two mailboxes at the other end labeled INBOX and OUTBOX which are used for receiving and outputting data. In the center of the room, there is a work area containing a simple 2 function (addition and subtraction) calculator known as the Accumulator and a resetable counter known as the Program Counter. The Program Counter is similar to what a doorperson uses to keep track of how many people have entered a facility -- it can count up 1, or it can be reset to 0. As specified by the von Neumann architecture, memory contains both instructions and data. The user loads data into the mailboxes and then signals the little man to begin execution.
[edit] Execution cycle
The little man performs the following steps to execute a program:
- Check the Program Counter, go to the mailbox with that number and fetch the instruction
- Increment the Program Counter (i.e. add one to the current value so that it now refers to the next mailbox that will be accessed in the next cycle)
- Decode the instruction (which includes determining the action to be performed and the mailbox on which it will be performed)
- Execute the action
- Repeat the cycle
See also: Instruction cycle
[edit] LMC commands: numeric
While the LMC does reflect the actual workings of binary processors, the simplification of decimal numbers was made to minimize the complexity for students who may not be comfortable working in binary/hexadecimal.
Each LMC instruction is a 3 digit decimal number. The first digit represents the command to be performed and the final two digits represent the address of the mailbox affected by the command.
- Instructions
- 1xx - ADD - Take the value stored in mailbox xx and add it to whatever value is currently on the accumulator.
- 2xx - SUBTRACT - Take the value stored in mailbox xx and subtract it from whatever value is currently on the accumulator.
- 3xx - STORE - Take the value from the accumulator (non-destructive) and store it in mailbox xx (destructive).
- 5xx - LOAD - Take the value from mailbox xx (non-destructive) and enter it in the accumulator (destructive).
- 6xx - BRANCH (unconditional) - Reset the program counter to the value xx. That is, xx will be the next instruction executed.
- 7xx - BRANCH IF ZERO - If the accumulator contains the value 0, reset the program counter to the value xx. Otherwise, do nothing.
- 8xx - BRANCH IF POSITIVE - If the accumulator is 0 or positive, reset the program counter to the value xx. Otherwise, do nothing.
- 901 - INPUT - Go to the INBOX, fetch the value from the user, and put it in the accumulator (destructive)
- 902 - OUTPUT - Fetch the value from the accumulator (non-destructive), and put it in the OUTBOX for the user to read.
- 000 - HALT - Stop working.
- A Sample Program
This program takes two numbers as input and outputs the difference.
| Mailbox | Instruction | Notes |
|---|---|---|
| 00 | 901 | INBOX --> ACCUMULATOR fetch first number |
| 01 | 308 | ACCUMULATOR --> MEMORY[08] move it out of the way |
| 02 | 901 | INBOX --> ACCUMULATOR fetch second number |
| 03 | 309 | ACCUMULATOR --> MEMORY[09] move it out of the way |
| 04 | 508 | MEMORY[08] --> ACCUMULATOR now that both inputs are retrieved, move the first back to the accumulator |
| 05 | 209 | ACCUMULATOR = ACCUMULATOR - MEMORY[09] subtract second number |
| 06 | 902 | ACCUMULATOR --> OUTBOX output the result to the user |
| 07 | 000 | HALT We're Done! |
[edit] LMC Commands: mnemonic
LOAD mnemonic - LDA numerical/machine code - 5
Load the contents of the given mailbox onto the accumulator (calculator). Note: the contents of the mailbox are not changed.
STORE mnemonic - STO numerical/machine code - 3
Store the contents of the accumulator (calculator) to the mailbox of the given address. Note: the contents of the accumulator are not changed.
ADD mnemonic - ADD numerical/machine code - 1
Add the contents of the given mailbox onto the accumulator (calculator). Note: the contents of the mailbox are not changed, and the actions of the accumulator are not defined for add instructions that cause sums larger than 3 digits.
SUBTRACT mnemonic - SUB numerical/machine code - 2
Subtract the contents of the given mailbox from the accumulator (calculator). Note: the contents of the mailbox are not changed, and the actions of the accumulator are not defined for subtract instructions that cause negative results -- however, a negative flag will be set so that BRP can be used properly (see below).
INPUT mnemonic - IN numerical/machine code - 901
Copy the value from the "in box" onto the accumulator (calculator).
OUTPUT mnemonic - OUT numerical/machine code - 902
Copy the value from the accumulator (calculator) to the "out box". Note: the contents of the accumlator are not changed.
END mnemonic - HLT numerical/machine code - 000
Causes the Little Man Computer to stop executing your program.
BRANCH IF ZERO mnemonic - BRZ numerical/machine code - 7
If the contents of the accumulator (calculator) are 000, the PC (program counter) will be set to the given address. Note: since the program is stored in memory, data and program instructions all have the same address/location format.
BRANCH IF ZERO OR POSITIVE mnemonic - BRP numerical/machine code - 8
If the contents of the accumulator (calculator) are 000 or positive (i.e. the negative flag is not set), the PC (program counter) will be set to the given address. Note: since the program is stored in memory, data and program instructions all have the same address/location format.
BRANCH ALWAYS mnemonic - BRA numerical/machine code - 6
Set the contents of the program counter to the given address.
DATA mnemonic - DAT numerical/machine code - none
This is an assembler instruction which simply loads the value into the next available mailbox. DAT can also be used in conjunction with labels to declare variables. For example, DAT 984 will store the value 984 into a mailbox.
[edit] Mnemonic use example and LMC simulator
Using the above mnemonics, the assembly language version of the program to subtract two numbers is given below. This program can be compiled and run on the following LMC simulator. This java applet-based simulator includes full instructions and sample programs, a compiler to convert the assembly into machine code, a control interface to execute and monitor programs, and a step-by-step detailed description of each LMC instruction.
IN STO 08 IN STO 09 LDA 08 SUB 09 OUT HLT
[edit] Using labels
The convenience of assembled mnemonics is made apparent from this example — The programmer is no longer required to memorize a set of anonymous numeric codes, and can now program with a set of more memorable instructions. However, the programmer is still required to manually keep track of mailbox locations. Furthermore, if an instruction was to be inserted somewhere in the program, the final HLT instruction would move down to address 08. Suppose the user entered 600 as the first input. This value would overwrite the 000 (HLT) instruction. Since 600 means "Branch to mailbox 0" the program, instead of halting, would get stuck in an endless loop.
To work around this difficulty, most assembly languages (including the LMC) allow the use of labels. A label is simply a word provided as a name to the left of a particular line in the program text, which the assembler will convert to the appropriate address at the time of assembly. When seen to the right of the instruction, labels then take on the value of the address calculated.
Labels are commonly used to:
- identify a particular instruction as a target for a BRANCH instruction
- identify space as a named variable (using DAT)
- load data into the program at assembly time for use by the program.
This use is not obvious until one considers that there is no way of adding 1 to a counter. One could ask the user to input 1 at the beginning, but it would be better to have this loaded at the time of assembly
[edit] Label use example
This program will take a user input, and count down to zero.
IN
LOOP SUB ONE // This address will be called LOOP, Subtract the value stored at ONE
OUT
BRZ QUIT //If we are at 0, then jump to the location QUIT
BRA LOOP //We are not at 0, go back to the start of LOOP
QUIT HLT
ONE DAT 1 //Put the value 1 in this mailbox, and call it ONE (variable declaration)
