MskProdComputing
All A Level 17 65 min read 10 question quiz 22 exam marks

Build a Processor: the Little Man Computer

Write a working processor in Python. Build a Little Man Computer emulator with the real registers, run the fetch-decode-execute cycle, write assembly programs with loops and decisions, build the assembler that turns labels into addresses, then add addressing modes and see how pipelining overlaps instructions.

Inside the processor: fetch, decode, execute

A processor does one thing, over and over, billions of times a second: it fetches an instruction from memory, decodes it to see what it means, and executes it. This is the fetch-decode-execute cycle. To follow it you need to know the places where the processor keeps things, called registers:

RegisterNameHolds
PCProgram counterthe address of the next instruction
MARMemory address registerthe address in memory about to be read or written
MDRMemory data registerthe data just read from memory, or about to be written
CIRCurrent instruction registerthe instruction being decoded and executed
ACCAccumulatorthe result of the most recent calculation

The control unit directs the cycle, and the ALU (arithmetic logic unit) does the arithmetic and comparisons. Addresses travel on the address bus, data on the data bus, and the read and write signals on the control bus.

The cycle, as register transfers:

  1. Fetch. The address in the PC is copied to the MAR.
  2. The instruction stored at that address in memory is copied to the MDR.
  3. The PC is incremented, so it already points to the next instruction.
  4. The instruction is copied from the MDR to the CIR.
  5. Decode. The control unit splits the instruction into an opcode (what to do) and an operand (what to do it to).
  6. Execute. The instruction is carried out, which may use the ALU, move data, or change the PC.

You can watch each transfer with a few lines of Python. Here the memory holds one instruction, 505, which means load the number in mailbox 5 into the accumulator:

Python
memory = [0] * 100
memory[0] = 505          # opcode 5 (load), operand 5 (the address)
memory[5] = 42           # the data
pc, acc = 0, 0

print("FETCH")
mar = pc
print("PC -> MAR          MAR =", mar)
mdr = memory[mar]
print("memory[MAR] -> MDR MDR =", mdr)
pc = pc + 1
print("PC + 1 -> PC       PC  =", pc)
cir = mdr
print("MDR -> CIR         CIR =", cir)

print("DECODE")
opcode, operand = divmod(cir, 100)
print("opcode", opcode, "operand", operand)

print("EXECUTE")
acc = memory[operand]
print("memory[", operand, "] -> ACC   ACC =", acc)
Instructions are just numbers

The processor has no idea which numbers in memory are instructions and which are data. It treats the number the PC points at as an instruction. Hold the program and its data in the same memory, as here, and you have the von Neumann architecture.

The fetch stage in the processor: PC, MAR, MDR and CIR, with the buses to memoryA processor and main memory. The processor holds four registers and some units. The program counter, PC, holds 0, the address of the next instruction. Step 1: the address in the PC is copied to the memory address register, MAR. The address travels along the address bus to memory, and step 2: the contents of address 0, the number 505, which means load the number in mailbox 5, comes back along the data bus to the memory data register, MDR. Step 3: the PC is increased by 1 so that it points to the next instruction. Step 4: the instruction is copied from the MDR to the current instruction register, CIR. The control unit then decodes the instruction in the CIR, and it is executed, using the ALU and the accumulator, ACC.the processormain memoryPC0MAR0MDR505CIR50514+ 13ALUadds, comparesACC0control unitdecodes the CIRdecode, then executeaddress busdata bus0505LDA 51106ADD 62307STA 73000HLT5042dataaddress, contents, meaning2
  1. PC to MAR: the address of the next instruction is copied into the memory address register.
  2. Memory at that address is read along the data bus into the MDR.
  3. The PC is incremented so that it already points to the next instruction.
  4. MDR to CIR: the instruction is copied into the current instruction register, ready to be decoded and executed.
Fetch is the same for every instruction. What differs is what the control unit does after it has decoded the CIR.

The Little Man Computer

The Little Man Computer (LMC) is a deliberately tiny processor with the same parts as a real one:

  • 100 mailboxes, numbered 0 to 99, each holding a number. This is the memory (RAM).
  • an accumulator and a program counter
  • an input and an output
  • a very small instruction set, each instruction a three digit number: the first digit is the opcode and the last two are the operand, an address.
MnemonicCodeWhat it does
ADD xx1xxadds the number in mailbox xx to the accumulator
SUB xx2xxsubtracts the number in mailbox xx from the accumulator
STA xx3xxstores the accumulator in mailbox xx
LDA xx5xxloads the number in mailbox xx into the accumulator
BRA xx6xxbranch always: sets the PC to xx
BRZ xx7xxbranches to xx only if the accumulator is zero
BRP xx8xxbranches to xx only if the accumulator is zero or positive
INP901waits for an input and puts it in the accumulator
OUT902outputs the accumulator
HLT000stops
DATnonenot an instruction: sets aside a mailbox for data

Programs are written in assembly language: one mnemonic per instruction, with labels instead of addresses. The assembler turns that into numbers. Here is a complete emulator: an assembler and a processor. Read the run function with the table above, and the register names in the previous section.

Python
CODES = {"ADD": 100, "SUB": 200, "STA": 300, "LDA": 500, "BRA": 600,
         "BRZ": 700, "BRP": 800, "INP": 901, "OUT": 902, "HLT": 0}

def assemble(source):
    lines, labels = [], {}
    for raw in source.strip().split("\n"):
        words = raw.split("//")[0].split()          # drop comments
        if not words:
            continue
        if words[0] not in CODES and words[0] != "DAT":
            labels[words[0]] = len(lines)           # pass 1: remember the address of each label
            words = words[1:]
        lines.append(words)
    memory = [0] * 100
    for address, words in enumerate(lines):         # pass 2: turn each line into a number
        name = words[0]
        operand = words[1] if len(words) > 1 else None
        if name == "DAT":
            memory[address] = int(operand) if operand else 0
        elif name in ("INP", "OUT", "HLT"):
            memory[address] = CODES[name]
        else:
            if operand in labels:
                operand = labels[operand]
            memory[address] = CODES[name] + int(operand)
    return memory

NAMES = {1: "ADD", 2: "SUB", 3: "STA", 5: "LDA", 6: "BRA", 7: "BRZ", 8: "BRP"}

def describe(cir):
    if cir in (0, 901, 902):
        return {0: "HLT", 901: "INP", 902: "OUT"}[cir]
    opcode, operand = divmod(cir, 100)
    return NAMES[opcode] + " " + str(operand)

def run(memory, inputs, trace=False, limit=2000):
    memory = list(memory)
    pc = acc = cycles = 0
    inputs, outputs = list(inputs), []
    if trace:
        print("cycle  MAR  MDR  instruction  PC  ACC")
    while cycles < limit:
        mar = pc                          # fetch
        mdr = memory[mar]
        pc = pc + 1
        cir = mdr
        opcode, operand = divmod(cir, 100)    # decode
        cycles = cycles + 1
        if cir == 0:                          # execute
            if trace:
                print(str(cycles).ljust(7), str(mar).ljust(4), str(mdr).ljust(4), "HLT")
            break
        elif opcode == 1:
            acc = acc + memory[operand]
        elif opcode == 2:
            acc = acc - memory[operand]
        elif opcode == 3:
            memory[operand] = acc
        elif opcode == 5:
            acc = memory[operand]
        elif opcode == 6:
            pc = operand
        elif opcode == 7:
            if acc == 0:
                pc = operand
        elif opcode == 8:
            if acc >= 0:
                pc = operand
        elif cir == 901:
            acc = inputs.pop(0)
        elif cir == 902:
            outputs.append(acc)
        if trace:
            print(str(cycles).ljust(7), str(mar).ljust(4), str(mdr).ljust(4), describe(cir).ljust(12), str(pc).ljust(3), acc)
    return outputs

adder = '''
      INP
      STA first
      INP
      ADD first
      OUT
      HLT
first DAT
'''

machine_code = assemble(adder)
print(machine_code[:7])
print("output:", run(machine_code, [7, 5], trace=True))

The assembled program is just 901 306 901 106 902 0 0: seven numbers in the first seven mailboxes. The label first became address 6, and STA first became 306.

The Little Man Computer: mailboxes, the instruction format, the registers and the input and output traysThe Little Man Computer is a simple model of a processor and memory. The memory is a set of numbered mailboxes, each holding a three digit number that is either an instruction or data. In this program mailbox 00 holds 901, which is INP, mailbox 01 holds 107, which is ADD 07, mailbox 02 holds 902, which is OUT, mailbox 03 holds 000, which is HLT, and mailbox 07 holds the data 5. An instruction is a number split in two: the first digit is the opcode, which says what to do, and the last two digits are the operand, which says which mailbox, so 107 is 1, ADD, with mailbox 07. The processor has a program counter, here 01, which holds the next address, an instruction register, here 107, holding the instruction being carried out, and an accumulator, here 12, which holds the working number. There is an input tray, here 7, and an output tray, here 12.Mailboxes: the memory100901INP01107ADD 0702902OUT03000HLT04050607005DAT 50809programdataA mailbox holds a three digit number: an instruction or data.2Reading an instruction107the number1opcode07operand1 = ADD07 = mailbox 07Registers and trays3Program counter01next addressInstruction register107what it is doingAccumulator12the working numberInput7Output12
  1. Memory is a row of numbered mailboxes. Each holds a three digit number, an instruction or data.
  2. An instruction is an opcode, the first digit, and an operand, the last two digits. 107 means ADD with mailbox 07.
  3. The program counter, instruction register and accumulator do the work, and the input and output trays connect to the outside.
The little man does fetch, decode, execute: read the program counter, fetch that mailbox, then carry out the instruction.

Writing assembly programs

There is no if or while in assembly. Selection and iteration are built from the branch instructions. A BRA is a goto; a BRZ or BRP is a conditional one. Subtracting a number and then testing the sign is how every comparison is made.

Here are three classics in one run. The emulator is the same as before, shortened by taking out the trace.

Python
CODES = {"ADD": 100, "SUB": 200, "STA": 300, "LDA": 500, "BRA": 600,
         "BRZ": 700, "BRP": 800, "INP": 901, "OUT": 902, "HLT": 0}

def assemble(source):
    lines, labels = [], {}
    for raw in source.strip().split("\n"):
        words = raw.split("//")[0].split()
        if not words:
            continue
        if words[0] not in CODES and words[0] != "DAT":
            labels[words[0]] = len(lines)
            words = words[1:]
        lines.append(words)
    memory = [0] * 100
    for address, words in enumerate(lines):
        name = words[0]
        operand = words[1] if len(words) > 1 else None
        if name == "DAT":
            memory[address] = int(operand) if operand else 0
        elif name in ("INP", "OUT", "HLT"):
            memory[address] = CODES[name]
        else:
            if operand in labels:
                operand = labels[operand]
            memory[address] = CODES[name] + int(operand)
    return memory

def run(memory, inputs, limit=2000):
    memory = list(memory)
    pc = acc = cycles = 0
    inputs, outputs = list(inputs), []
    while cycles < limit:
        cir = memory[pc]
        pc = pc + 1
        opcode, operand = divmod(cir, 100)
        cycles = cycles + 1
        if cir == 0:
            break
        elif opcode == 1:
            acc = acc + memory[operand]
        elif opcode == 2:
            acc = acc - memory[operand]
        elif opcode == 3:
            memory[operand] = acc
        elif opcode == 5:
            acc = memory[operand]
        elif opcode == 6:
            pc = operand
        elif opcode == 7 and acc == 0:
            pc = operand
        elif opcode == 8 and acc >= 0:
            pc = operand
        elif cir == 901:
            acc = inputs.pop(0)
        elif cir == 902:
            outputs.append(acc)
    return outputs, cycles

# 1. Countdown: a loop built from BRP
countdown = '''
      INP
loop  OUT
      SUB one
      BRP loop        // still zero or positive: go round again
      HLT
one   DAT 1
'''

# 2. Selection: output the larger of two numbers
larger = '''
          INP
          STA first
          INP
          STA second
          SUB first        // second - first
          BRP secondbig    // zero or positive: second is at least as big
          LDA first
          OUT
          HLT
secondbig LDA second
          OUT
          HLT
first     DAT
second    DAT
'''

# 3. Multiplication by repeated addition: a loop with a counter
multiply = '''
        INP
        STA a
        INP
        STA count
        BRZ done          // multiplying by zero
loop    LDA total
        ADD a
        STA total
        LDA count
        SUB one
        STA count
        BRZ done
        BRA loop
done    LDA total
        OUT
        HLT
a       DAT
count   DAT
total   DAT 0
one     DAT 1
'''

print("countdown from 5:", run(assemble(countdown), [5]))
for first, second in [(3, 8), (9, 4)]:
    print("larger of", first, "and", second, ":", run(assemble(larger), [first, second]))
for a, b in [(6, 7), (5, 0), (9, 1)]:
    result, cycles = run(assemble(multiply), [a, b])
    print(a, "x", b, "=", result[0], "in", cycles, "cycles")

Look at the cycle counts. Multiplying is slow because the processor can only add: 6 x 7 means seven trips round the loop. Real processors have hardware multipliers for exactly this reason.

Turning a flowchart into assembly

A decision becomes a conditional branch past the code it guards. A loop becomes a branch back to its start. Always give the branch a label: you never work out an address yourself.

High-level ideaAssembly pattern
if x >= 0:load x, then BRP to the code for the true case
if x == 0:load x, then BRZ
while count > 0:at the bottom, subtract 1, test, and branch back
elseBRA over the else code at the end of the true case
variablea labelled DAT
Trace with a table

In an exam, trace LMC with columns for the PC, the accumulator, and any mailbox that changes, one row per instruction. Write the output when OUT runs, not at the end.

The assembler: from labels to numbers

Why have an assembler at all? The processor can only run numbers. Writing 306 instead of STA first would be painful and fragile: add one instruction near the top and every address after it moves. The assembler does the bookkeeping.

An assembler runs in two passes over the source:

  1. Pass one. Read every line, counting instructions. Whenever a line starts with a label, record the address it has reached in a symbol table.
  2. Pass two. Translate each line into a number, replacing every label with the address from the symbol table.

It needs two passes because a branch may refer to a label that appears later in the program, which has no address yet when the branch is read.

Python
CODES = {"ADD": 100, "SUB": 200, "STA": 300, "LDA": 500, "BRA": 600,
         "BRZ": 700, "BRP": 800, "INP": 901, "OUT": 902, "HLT": 0}

def first_pass(source):
    lines, symbols = [], {}
    for raw in source.strip().split("\n"):
        words = raw.split("//")[0].split()
        if not words:
            continue
        if words[0] not in CODES and words[0] != "DAT":
            symbols[words[0]] = len(lines)
            words = words[1:]
        lines.append(words)
    return lines, symbols

def second_pass(lines, symbols):
    memory = []
    for address, words in enumerate(lines):
        name = words[0]
        operand = words[1] if len(words) > 1 else None
        if name == "DAT":
            memory.append(int(operand) if operand else 0)
        elif name in ("INP", "OUT", "HLT"):
            memory.append(CODES[name])
        else:
            if operand in symbols:
                operand = symbols[operand]
            elif operand is None or not operand.isdigit():
                raise ValueError("line " + str(address) + ": no label called " + str(operand))
            memory.append(CODES[name] + int(operand))
    return memory

program = '''
      INP
loop  OUT
      SUB one
      BRP loop
      HLT
one   DAT 1
'''

lines, symbols = first_pass(program)
print("symbol table:", symbols)
print("addr  code  source")
for address, (words, code) in enumerate(zip(lines, second_pass(lines, symbols))):
    print(str(address).ljust(5), str(code).rjust(3).ljust(5), " ".join(words))

try:
    second_pass(*first_pass("LDA nowhere\nHLT"))
except ValueError as problem:
    print("error:", problem)

The assembler also reports mistakes before anything runs, such as a branch to a label that does not exist.

Levels of language

LevelExampleTranslator
Machine code901 306 901 106none: the processor runs it directly
Assembly languageSTA firstassembler, one assembly instruction for one machine instruction
High-level languagetotal = first + secondcompiler or interpreter, one statement for many instructions

Assembly is machine specific: an LMC program will not run on any other processor, and ARM assembly is different from x86. It is used where speed or size is critical, such as embedded systems and device drivers.

Addressing modes and the pipeline

An instruction's operand is not always an address. The addressing mode says how to find the data the operand points to. The LMC only has one, but real processors have several:

ModeOperand is...ExampleUsed for
Immediatethe data itselfLDA #10 loads the number 10constants
Directthe address of the dataLDA 10 loads the number held in mailbox 10variables
Indirectthe address of the address of the dataLDA (11): mailbox 11 holds 10, so loads from mailbox 10pointers
Indexeda base address, plus the index registerLDA 12,X with X = 2 loads from mailbox 14arrays, lists
Python
memory = [0] * 20
memory[10] = 42                     # a value
memory[11] = 10                     # a pointer: it holds the address 10
memory[12:15] = [100, 200, 300]     # an array

def operand_value(mode, operand, index=0):
    if mode == "immediate":
        return operand
    if mode == "direct":
        return memory[operand]
    if mode == "indirect":
        return memory[memory[operand]]
    if mode == "indexed":
        return memory[operand + index]

print("immediate 10 ->", operand_value("immediate", 10))
print("direct 10    ->", operand_value("direct", 10))
print("indirect 11  ->", operand_value("indirect", 11))
for x in range(3):
    print("indexed 12 with X =", x, "->", operand_value("indexed", 12, x))

Indexed addressing is why an array is fast: element i is at the start of the array plus i, found in one step.

The pipeline

In the cycle so far, the processor finishes one instruction before starting the next, so the fetch hardware sits idle while the ALU works. A pipeline overlaps them: while instruction 1 is being executed, instruction 2 is being decoded and instruction 3 fetched. Each stage always has something to do.

Python
stages = "FDE"                 # fetch, decode, execute
count = 5
width = count + len(stages) - 1

print("without a pipeline:", count * len(stages), "cycles")
print("with a pipeline:   ", width, "cycles")
print()
for i in range(count):
    print("instruction", i + 1, "." * i + stages + "." * (count - 1 - i))

Five instructions take 15 cycles one after another and 7 with a pipeline. Over millions of instructions the pipeline completes close to one instruction every cycle. A single instruction still takes three cycles. It is the throughput that improves, not the time for one instruction.

The pipeline has weaknesses. A branch means the instructions already fetched behind it may be the wrong ones, and must be thrown away (the pipeline is flushed), wasting cycles. An instruction that needs the result of the one before it may have to wait.

Other things that affect performance

FactorEffect
Clock speedmore cycles each second, so more instructions each second
Number of coresseveral instructions streams at once, if the software can use them
Cachesmall, fast memory close to the processor holding recently used data, saving slow trips to RAM

Von Neumann and Harvard

The LMC and most computers use the von Neumann architecture: one memory for instructions and data, so one bus. It is simple, but instruction fetches and data transfers compete for it. A Harvard architecture has separate memories and buses for instructions and data, so both can be fetched at once. It is used in many embedded systems and in the caches of modern processors.

Four addressing modes loading from memory: immediate, direct, indirect and indexedFour ways an instruction can find its data. In immediate addressing, LDA hash 5, the operand is the data itself, so the accumulator gets 5. In direct addressing, LDA 5, the operand is the address of the data: memory address 5 holds 42, so the accumulator gets 42. In indirect addressing, LDA in brackets 5, the operand is the address of the address: memory address 5 holds 8, which is the address of the data, and memory address 8 holds 42. In indexed addressing, LDA 5 comma X, the address is the operand plus the index register: with X equal to 3 the address is 8, which holds 42.Immediate1LDA #5the operand is the data5ACC = 5Direct2LDA 5the operand is theaddress of the data45426789ACC = 42Indirect3LDA (5)the operand is theaddress of the address458678429ACC = 42Indexed4LDA 5,Xaddress = operand +index register (X = 3)45678429X = 35 + 3 = 8
  1. Immediate: the operand is the data.
  2. Direct: the operand is the address of the data.
  3. Indirect: the operand is the address of the address of the data.
  4. Indexed: add the index register to the operand to get the address, which is useful for arrays.
Say what the operand means in each mode: the value, an address, an address of an address, or a base address plus an index.
Three instructions with and without a pipeline: nine cycles against fivePipelining shown on a grid of clock cycles. Every instruction has three stages: fetch, decode and execute. Without a pipeline, instruction 1 finishes all three stages before instruction 2 starts, and so on, so three instructions take 9 cycles. With a pipeline the stages overlap: in cycle 2 instruction 1 is being decoded while instruction 2 is fetched, and in cycle 3 instruction 1 executes while instruction 2 is decoded and instruction 3 is fetched. All three instructions finish in 5 cycles, which saves 4. One instruction still takes three cycles, so the gain is in throughput, close to one instruction per cycle. When a conditional jump is taken, the instructions already in the pipeline are the wrong ones and are discarded, which is a pipeline flush, so processors use branch prediction.No pipeline: one at a timecycle123456789Instruction 1FetchDecodeExecuteInstruction 2FetchDecodeExecuteInstruction 3FetchDecodeExecute9 cycles in allWith a pipeline: stages overlapcycle123456789Instruction 1FetchDecodeExecuteInstruction 2FetchDecodeExecuteInstruction 3FetchDecodeExecute5 cycles in all4 cycles saveda taken branch flushes it,so branches are predicted123
  1. Without a pipeline each instruction finishes fetch, decode and execute before the next one starts: 3 instructions take 9 cycles.
  2. With a pipeline the stages overlap, so while one instruction executes the next is decoded and the one after is fetched: 5 cycles.
  3. One instruction still takes 3 cycles. The gain is throughput. A taken branch flushes the pipeline, which is why branches are predicted.
Pipelining does not make one instruction faster. It raises throughput by keeping every stage busy at once.

Key terms you must be able to define

Fetch-decode-execute cycle
The repeated cycle in which the processor fetches an instruction from memory, decodes it and carries it out.
Program counter (PC)
The register holding the address of the next instruction to be fetched.
Memory address register (MAR)
The register holding the address of the memory location about to be read or written.
Memory data register (MDR)
The register holding the data that has just been read from, or is about to be written to, memory.
Current instruction register (CIR)
The register holding the instruction that is being decoded and executed.
Accumulator (ACC)
The register that holds the results of calculations made by the ALU.
Opcode and operand
The two parts of an instruction: what to do, and the data or address to do it to.
Assembly language
A low-level language in which each instruction is a mnemonic that matches one machine code instruction.
Assembler
A translator that converts assembly language into machine code.
Addressing mode
The way the operand of an instruction is used to find the data: immediate, direct, indirect or indexed.
Pipelining
Overlapping the stages of several instructions, so that fetching, decoding and executing happen at the same time.
Von Neumann architecture
A design in which instructions and data are stored in the same memory.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

DefineFetch-decode-execute cycle
AnswerThe repeated cycle in which the processor fetches an instruction from memory, decodes it and carries it out.
DefineProgram counter (PC)
AnswerThe register holding the address of the next instruction to be fetched.
DefineMemory address register (MAR)
AnswerThe register holding the address of the memory location about to be read or written.
DefineMemory data register (MDR)
AnswerThe register holding the data that has just been read from, or is about to be written to, memory.
DefineCurrent instruction register (CIR)
AnswerThe register holding the instruction that is being decoded and executed.
DefineAccumulator (ACC)
AnswerThe register that holds the results of calculations made by the ALU.
DefineOpcode and operand
AnswerThe two parts of an instruction: what to do, and the data or address to do it to.
DefineAssembly language
AnswerA low-level language in which each instruction is a mnemonic that matches one machine code instruction.

Reach the top grade on this topic

Fetch-decode-execute is asked every year, and the marks go to the order and to the register names.

  • Describe the cycle as register transfers: PC to MAR, memory to MDR, PC incremented, MDR to CIR
  • Say what happens at decode (the opcode and operand are separated) and at execute (the instruction is carried out)
  • When tracing assembly, keep a column for every register and variable that changes
  • For addressing modes, give a one line example of the operand and what ends up in the accumulator
  • For pipelining, say throughput improves while the time for one instruction does not, and name the branch problem

Mistakes that cost marks here

Avoid these
  • Saying the PC holds the current instruction. It holds the address of the next one, and is incremented during the fetch.
  • Confusing the MAR, which holds an address, with the MDR, which holds data.
  • Writing the stages in the wrong order, or leaving out that the PC is incremented.
  • Mixing up BRZ (branch only if zero) and BRP (branch if zero or positive).
  • Saying a pipeline makes each instruction faster. It lets more instructions complete in the same time.
Fun fact

The Little Man Computer was invented in 1965 by Stuart Madnick at MIT to teach how a computer works. A little man sits in a room of 100 numbered mailboxes with a calculator, and follows instructions one at a time. It is still used for teaching because every part of a real processor has a matching part in the room.

Knowledge check

0 of 10 answered
1What does the program counter hold?
2In the fetch stage, what is the first thing that happens?
3Which register holds the data that has just been read from memory?
4What is the job of the ALU?
5In the LMC, what does the instruction 'BRP loop' do?
6What is the machine code for 'LDA 05' in the LMC?
7Why does an assembler need two passes?
8Which addressing mode treats the operand as the data itself?
9Which addressing mode is most useful for stepping through the items in an array?
10What is the main benefit of pipelining?
Score 0 / 10

Exam-style questions

Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.

22 marks
1Describe the fetch stage of the fetch-decode-execute cycle, naming the registers that are used.4 marks
Describe

Mark scheme0 / 4
  • LThe address in the program counter (PC) is copied to the memory address register (MAR)
  • LThe instruction at that address is fetched from memory (via the data bus) into the memory data register (MDR)
  • LThe program counter is incremented
  • LThe instruction is copied from the MDR to the current instruction register (CIR)
Model answer

The address held in the program counter is copied to the memory address register. The instruction stored at that address is then fetched from memory, along the data bus, into the memory data register. The program counter is incremented so that it points to the next instruction. Finally the instruction is copied from the memory data register to the current instruction register, ready to be decoded.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
2The Little Man Computer program shown is run with the input 7. State the values that are output.3 marks
State
        INP
        STA num
loop    OUT
        LDA num
        SUB two
        STA num
        BRP loop
        HLT
num     DAT
two     DAT 2

Mark scheme0 / 3
  • LOutputs 7 first (the input value)
  • LEach time round the loop 2 is subtracted from the value, so 5 and 3 are output
  • LThe loop ends when the value becomes negative, after 1 has been output: 7, 5, 3, 1
Model answer

The outputs are 7, 5, 3 and 1. The input 7 is stored in num and output. Each time round the loop two is subtracted from num and, while the result is zero or positive, the new value is output. After 1 has been output, subtracting 2 gives -1, which is negative, so BRP does not branch and the program halts.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
3Write a Little Man Computer program that inputs two numbers and outputs the larger of the two. You may assume that the numbers are different. Use labels for the branch targets and the data locations.5 marks
Write

Mark scheme0 / 5
  • LInputs both numbers and stores them (INP, STA) in labelled locations
  • LSubtracts one from the other (SUB) to compare them
  • LUses a conditional branch (BRP) on the result of the subtraction
  • LLoads and outputs the correct number in each case (LDA, OUT)
  • LHLT at the end of each path, and DAT used to define the variables
Model answer
        INP
        STA first
        INP
        STA second
        SUB first
        BRP secondbig
        LDA first
        OUT
        HLT
secondbig LDA second
        OUT
        HLT
first   DAT
second  DAT

Both numbers are input and stored. The first is subtracted from the second. If the result is positive the second is larger, so the program branches to secondbig, which loads and outputs it. Otherwise the first is larger and is output. Each path ends with HLT.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
4Explain the difference between immediate addressing and direct addressing. Give an example of each.4 marks
Explain

Mark scheme0 / 4
  • LImmediate: the operand is the data itself
  • LExample of immediate, such as LDA #10 loads the number 10
  • LDirect: the operand is the address of the data (a memory location)
  • LExample of direct, such as LDA 10 loads the contents of address 10
Model answer

In immediate addressing the operand is the data itself, so LDA #10 loads the number 10 into the accumulator. In direct addressing the operand is the address of the data, so LDA 10 loads the number that is stored at memory address 10 into the accumulator.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
5Discuss how pipelining improves the performance of a processor, and the problems it can introduce.6 marks
Discuss

Mark scheme0 / 6
  • LPipelining overlaps the stages of different instructions, so that one is fetched while another is decoded and another executed
  • LThe processor can complete close to one instruction per cycle, increasing throughput
  • LEach stage of the processor is kept busy rather than waiting
  • LA branch instruction means that the instructions already fetched may be wrong, so the pipeline must be flushed
  • LAn instruction may depend on the result of a previous one, causing delays (stalls)
  • LA reasoned conclusion: the benefits outweigh the problems, and so all modern processors use pipelines
Model answer

Pipelining overlaps the stages of consecutive instructions, so that while one instruction is being executed the next is being decoded and the one after that is being fetched. Each part of the processor is kept busy instead of waiting, and the processor can complete close to one instruction every clock cycle, so the throughput increases greatly, although an individual instruction takes the same time as before. There are problems. When there is a branch instruction the instructions already fetched behind it may be the wrong ones, so the pipeline has to be flushed and cycles are wasted. An instruction may also need the result of one in front of it, so it has to wait. Overall, however, the improvement in throughput outweighs these problems, and so all modern processors use pipelines.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
Machine mark 0 / 22