Monday, March 12, 2012

The Little Man Computer

The Little Man Computer presents a simplification of the modern computer architecture. This post will go through the LMC model and from there we'll infer what goes on inside the common computer when a program is executed. 

A Hypothetical Task for LM

We'll skip any formalities and deal with them later. Imagine if a little man, LM, is charged with the task of adding a given number x, no more than 3 digits, to an arbitrary number, say 22, then add their sum to another given number y. 
That is, performing x + 22 + y, where x and y are numbers we supply to LM. 

Set up LM an Office

Let's imagine the setting that must be provided to LM for him to do his job.

  1. he'll need a box to get the most recent number given from his user - an "In Basket"
  2. since LM reads one instruction at a time, he needs a set of boxes to help him store data and instructions alike - "100 Mailboxes" labelled from 00 to 99
  3. something to help him do the arithmetic - a "Calculator"
  4. an indicator, which can be reset, to let LM know which mailbox to look for the next instruction or data - an "Instruction Counter"
  5. a box that he could present the result to the user - an "Out Basket"

So we have an environment set up shown schematically like this:

What to Instruct LM

Now we turn our attention to instructing LM to carry out the addition of numbers. The following is the steps that we wish him to follow:

  1. LM fetches the number x, which we'd supply, and keys in x on the Calculator
  2. fetch the arbitrary number 22 which we stored in a mailbox and add it to x; this is feasible since the value of x is still on the Calculator
  3. LM stores the sum to a mailbox for later reference
  4. we'd supply LM with another number, y, which LM keys in on the Calculator
  5. LM retrieves the value of x+22 from the mailbox which he previously stored in step #4 and add it to y on the Calculator;  note the value of y was already entered in step #5
  6. LM puts the total sum of 3 number, x, y, and 22, to the Out Basket
  7. LM can now go on a coffee break

Note that step #4 is needed since in step #5 LM would punch in the value of y hence erasing the sum of x + 22. Each instruction is placed in its respective mailbox and LM will rely on the Instruction Counter to know which mailbox to go to next. Let's review the above instructions schematically:

How to Instruct LM

At this point, we know what instructions to give LM to do the job; here, we'll need to translate these steps into instructions that LM can understand.

For our simple task here we'll only need a subset of the complete LMC instructions available. Note that different implementations of the LMC exist so the instruction set varies as well. The table below summarizes the instructions needed to tell our LM to do his job:

Operation Mnemonic Machine Code
Coffee Break

Note: The x's for Add and Store refer to the mailbox numbers. x's for Data is the actual data value we wish to store in the next available mailbox

Machine code is understood by LM but tedious for people to memorize or write. So the operation codes (opcode) are expressed in mnemonics as shown in the table. We can now write the task instructions as follows:

IN              #copy the number x we supplied in In Basket onto the Calculator
ADD 07    #add the number, 22, which we stored in mailbox 7 to x
STO 08    #store the the result of x+22 to mailbox 8
IN              #copy the number y we supplied in In Basket onto the Calculator
ADD 08    #add the value we stored in mailbox 8 to the number y
OUT         #copy the value of y from the Calculator to the Out Basket
COB         #take a well deserved coffee break, ie. halt
DAT 22    #we place the arbitrary number 22 in the next available mailbox, 
                 #in this case, box 7 is available after all the instructions have taken up box 0 to 6

Give LMC a Test Run

Now that we have an imagination of how the LMC works, let's give the instructions a run on a LMC Simulator Applet, courtesy of University of Minnesota Duluth.

We'll now give LMC a run:
  1. type in the mnemonic instructions in the LMC Editor
  2. press the Assemble button to generate the machine code in the LMC Assembler window
  3. click the Load button in the LMC Computer window. Notice the machine code is displayed under the Memory field. Accumulator refers to LM's calculator. 
  4. click Step to follow the execution of our instructions. Notice the arbitrary number 22 is stored in box 7 and the sum of 22 and the first input, in this case 133, is stored in box 8, which is coherent with our instructions given.

Inference to the Common Computer Architecture

From the LMC model, we can take away some key points to help us to understand the common computer architecture (Von Neumann architecture).

Let's first map the LMC terms to their corresponding parts in a common computer:
1. The Little Man> The Control Unit
2. Calculator / Accumulator > Arithmetic Logic Unit
3. Instruction Counter > Program Counter
4. Mailboxes  > Main Memory
5. In Basket + Out Basket > I/O

The common computer components have the same roles to their LMC counter parts. The Control Unit and the Arithmetic Logic Unit (ALU) together make up the CPU. A simplified schematic diagram of a common computer is as such:

Under this architecture:
  1. both programs(instructions) and data are stored in memory
  2. ALU holds data temporarily until calculation is carried out
  3. program counter is incremented each time an instruction is fetched; the order of execution is sequential unless branching (we'll look into this in a post to follow) occurs
  4. Control Unit oversees the machine cycle: Fetch, Decode, and Execute. For instance, performing instruction 107 (mnemonic: ADD 07) stored in mailbox 01, upon reading the program counter for his next step to take, LM goes to mailbox 1 to retrieve the instruction 107, decoding 107 as 1 (the add operation) followed by the mailbox number 07, then execute the instruction (adding the data value stored in mailbox 7 to the value currently keyed in on the calculator).
We've just tapped into the concepts of LMC and how it models the common computer we so heavily rely on everyday. In later posts, let's look at how to get LMC to do more interesting things using branching etc. 

No comments:

Post a Comment