Little Man Computer
The Little Man Computer (LMC) is an instructional model of a computer, created by Dr. Stuart Madnick in 1965.[1] The LMC is generally used to teach students, because it models a simple von Neumann architecture computer - which has all of the basic features of a modern computer. It can be programmed in machine (albeit usually in decimal) or assembly code.
System 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 two function (addition and subtraction) calculator known as the Accumulator and a resettable 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.
Execution cycle
To execute a program, the little man performs these steps:
- check the Program Counter for the mailbox number that contains a program instruction
- fetch the instruction from the mailbox with that number
- Increment the Program Counter (so that it contains the mailbox number of the next instruction)
- decode the instruction (includes finding the mailbox number for the data it will work on)
- fetch the data from the mailbox with the number found in the previous step
- execute the instruction
- store the new data in the mailbox from which the old data was retrieved
- Repeat the cycle or halt
Commands
While the LMC does reflect the actual workings of binary processors, the simplicity of decimal numbers was chosen to minimize the complexity for students who may not be comfortable working in binary/hexadecimal.
Instructions
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.
| Numeric code | Mnemonic code | Instruction | Description |
|---|---|---|---|
| 1xx | ADD | ADD | Add the value stored in mailbox xx to whatever value is currently on the accumulator (calculator).
|
| 2xx | SUB | SUBTRACT | Subtract the value stored in mailbox xx from whatever value is currently on the accumulator (calculator).
|
| 3xx | STA | STORE | Store the contents of the accumulator in mailbox xx (destructive).
|
| 5xx | LDA | LOAD | Load the value from mailbox xx (non-destructive) and enter it in the accumulator (destructive). |
| 6xx | BRA | BRANCH (unconditional) | Set the program counter to the given address (value xx). That is, value xx will be the next instruction executed. |
| 7xx | BRZ | BRANCH IF ZERO (conditional) | If the accumulator (calculator) contains the value 000, set the program counter to the value xx. Otherwise, do nothing.
|
| 8xx | BRP | BRANCH IF POSITIVE (conditional) | If the accumulator (calculator) is 0 or positive, set the program counter to the value xx. Otherwise, do nothing.
|
| 901 | INP | INPUT | Go to the INBOX, fetch the value from the user, and put it in the accumulator (calculator)
|
| 902 | OUT | OUTPUT | Copy the value from the accumulator (calculator) to the OUTBOX.
|
| 000 | HLT | HALT | Stop working. |
| DAT | DATA | 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. |
Examples
Numeric
This program takes two numbers as input and outputs the difference. Notice that execution starts at Mailbox 00 and finishes at Mailbox 07.
| Mailbox | Numeric code |
Instruction | Comments |
|---|---|---|---|
| 00 | 901 | INBOX --> ACCUMULATOR | INPUT the first number, enter into calculator (erasing whatever was there) |
| 01 | 308 | ACCUMULATOR --> MEMORY[08] | STORE the calculator's current value (to prepare for the next step...) |
| 02 | 901 | INBOX --> ACCUMULATOR | INPUT the second number, enter into calculator (erasing whatever was there) |
| 03 | 309 | ACCUMULATOR --> MEMORY[09] | STORE the calculator's current value (again, to prepare for the next step...) |
| 04 | 508 | MEMORY[08] --> ACCUMULATOR | (Now that both INPUT values are STORED in Mailboxes 08 and 09...)
LOAD the first value back into the calculator (erasing whatever was there) |
| 05 | 209 | ACCUMULATOR = ACCUMULATOR - MEMORY[09] | SUBTRACT the second number from the calculator's current value (which was just set to the first number) |
| 06 | 902 | ACCUMULATOR --> OUTBOX | OUTPUT the calculator's result to the user |
| 07 | 000 | HALT | HALT (We're Done!) |
Mnemonic
Using the LMC mnemonic codes, an assembly language version of the program to subtract two numbers is given below.
- This example program can be compiled and run on the LMC simulator[2] available on the website of York University (Toronto, Canada) or on the desktop application written by Matthew Consterdine[3]. Both simulators include full instructions and sample programs, compilers to convert the assembly into machine code, control interfaces to execute and monitor programs, and a step-by-step detailed description of each LMC instruction.
INP STA FIRST INP STA SECOND LDA FIRST SUB SECOND OUT HLT FIRST DAT SECOND DAT
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
Example
This program will take a user input, and count down to zero.
INP
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)
This program will divide two positive numbers. The memory locations for the results are: Dividend (36), Divisor (37), Quotient (38), Remainder (39)
LDA ZERO // Iniatilize for Multiple Program Run
STA QUOTIENT // Clear Any Previous Quotient
STA REMAINDER // Clear Any Previous Remainder
INP // User Provided Dividend
STA DIVIDEND // Store Dividend
INP // User Provided Divisor
STA DIVISOR // Store Divisor
LDA DIVIDEND // Load Dividend
SUB DIVISOR // Subtract Divisor
STA RESULT // Store Result
BRP LABELA // Skip To LABELA If Result is 0 or Positive
ADD DIVISOR // Negative Result + Divisor...
STA REMAINDER // ...Equals Positive Remainder
BRA QUIT // Done, Quotient is 0, Branch to QUIT
LABELA LDA COUNTER // Load 1
ADD QUOTIENT // Add 1 to Quotient
STA QUOTIENT // Store New Quotient
LDA RESULT // Load Result
BRZ QUIT // If Zero, Done, Quotient is 1, Branch to QUIT
LOOP LDA RESULT // Load Result
SUB DIVISOR // Subtract Divisor
STA RESULT // Store Result
BRP LABELB // Skip To LABELB If Result Is Positive
ADD DIVISOR // Negative Result + Divisor...
STA REMAINDER // ...Equals Positive Remainder
BRA QUIT // Done, With Remainder, Branch to QUIT
LABELB LDA COUNTER // Load 1
ADD QUOTIENT // Add 1 to Quotient
STA QUOTIENT // Store New Quotient
LDA RESULT // Load Result
BRZ QUIT // Result is 0, Done, No Remainder, Branch to QUIT
BRA LOOP // More to Do - Go Back to LOOP
QUIT HLT // HALT - Done!
COUNTER DAT 001 // Counter with Constant Value of 1
ZERO DAT 000 // Zero with Constant Value of 0
RESULT DAT 000 // (Dividend - Divisor), Then (Result - Divisor)
DIVIDEND DAT 000 // User Provided Dividend
DIVISOR DAT 000 // User Provided Divisor
QUOTIENT DAT 000 // Computed Quotient
REMAINDER DAT 000 // Computed Remainder
See also
- CARDboard Illustrative Aid to Computation (CARDIAC) A similar instruction set - with simulator - from Bell Laboratories.
- VIC, an extension of LMC from the Interdisciplinary Center Herzliya.
References
- ^ "Little Man Computer". Illinois State University. 2000-05-01. Retrieved 2009-03-08.
- ^ Chen, Stephen Y.; Cudmore, William C. "The Little Man Computer". York University. Retrieved 7 October 2010.
- ^ Consterdine, Matthew R. "The Little Man Computer". Retrieved 18 October 2011.
External links
- Richard J. Povinelli:Teaching:Introduction to Computer Hardware and Software:Little Man Computer
- The "Little Man" Computer