Building the LC-2K

1.0 Summary

EECS 370 hands you one instruction set, the LC-2K, and has you build outward from it across four projects. The projects are cumulative: each one runs on the output of the last, so a bug you leave in Project 1 comes back to find you in Project 4. Written in C, with the assembly programs written in LC-2K itself.

The path runs assembler and simulator, then linker, then a pipelined simulator, then a cache. What follows is that path in order, with the piece of each project that carried the most weight.

2.0 The LC-2K

The LC-2K is deliberately small: eight registers, 32-bit words, and eight opcodes. Three R-type and I-type shapes cover arithmetic (add, nor), memory (lw, sw), control (beq, jalr), and halt / noop. Small is the point: it is simple enough to hold in your head and rich enough that a pipeline built for it has real hazards.

Everything downstream is defined by the 32-bit encoding: opcode in bits 24 to 22, two register fields below it, and a signed 16-bit offset in the low half. Both the assembler that writes that word and the simulator that reads it have to agree on those bit positions exactly.

3.0 Project 1 · Assembler & Simulator

This is where it began. Project 1 is the translator and the interpreter: an assembler that turns LC-2K assembly into machine code, and a simulator that executes that machine code one instruction at a time. Together they let you write a program, assemble it, and watch it run.

The classic test program is a multiply written without a multiply instruction, done the only way the ISA allows, as shift-and-add:

        lw   0 1 mcand    // reg1 = multiplicand
        lw   0 2 mplier   // reg2 = multiplier
        add  0 0 3        // reg3 = result
        lw   0 4 one
loop    nor  2 2 5        // isolate the low bit of the multiplier
        nor  4 4 6
        nor  5 6 5
        beq  5 0 skAdd    // bit clear -> skip the add
        add  3 1 3        // bit set  -> add the shifted multiplicand
skAdd   add  1 1 1        // multiplicand <<= 1
        add  4 4 4        // mask <<= 1
        beq  4 0 done
        beq  0 0 loop
done    halt

4.0 Project 2 · Linker

Project 2 lets a program span several files. The assembler grows sections and symbol tables: a label defined here and used elsewhere is global, a label used here but defined elsewhere is undefined, and every address that will move when files are combined is recorded in a relocation table.

The linker then lays every file's text back to back, then every file's data, and walks the relocation tables fixing each address to where it actually ended up. That relocation step is the whole project:

// a local reference points into this file's own text or data;
// slide it to where that section landed in the combined image
unsigned orig = isFill ? F->data[reloc->offset]
                       : F->text[reloc->offset] & 0xFFFF;

finalAddr = (orig < F->textSize)
          ? F->textStartingLine + orig
          : F->dataStartingLine + (orig - F->textSize);

5.0 Project 3 · Pipelined Simulator

Project 3 is the jump. The simulator stops being one-instruction-at-a-time and becomes a five-stage pipeline: fetch, decode, execute, memory, writeback, with a register between each stage. Five instructions are now in flight at once, which means hazards: an instruction can need a value that an earlier one has computed but not yet written back.

The fix is forwarding. Before an instruction uses a register, check the pipeline registers ahead of it and take the most recent in-flight value instead of the stale one in the register file. Order matters, youngest wins:

// EX/MEM is youngest and wins, then MEM/WB, then WB/END.
// lw's value is not ready in EX/MEM (only the address is), so never
// forward it from there -- that is what forces the load-use stall.
if (isRegWrite(WBEND.instr) && destReg(WBEND.instr) == r) val = WBEND.writeData;
if (isRegWrite(MEMWB.instr) && destReg(MEMWB.instr) == r) val = MEMWB.writeData;
if (opcode(EXMEM.instr) != LW &&
    isRegWrite(EXMEM.instr) && destReg(EXMEM.instr) == r) val = EXMEM.aluResult;

Forwarding handles almost everything except one case it cannot: a lw feeding the very next instruction. Its value is not read from memory until the stage after the one that needs it, so there is nothing to forward and the pipeline has to stall one cycle.

// a lw in EX feeding the instruction now in ID cannot forward in time,
// so hold IF/ID and inject one bubble
if (opcode(IDEX.instr) == LW) {
    int d = destReg(IDEX.instr);
    return srcA(IFID.instr) == d || srcB(IFID.instr) == d;
}

6.0 Project 4 · Cache

Project 4 puts a cache in front of memory. It is set-associative with configurable block size, sets, and ways, tracks LRU per set, and is write-back: a modified block is only pushed to memory when it is evicted, and only if it is dirty.

int idx = find_block_in_set(setIndex, tag);
if (idx != -1) {                       // HIT
    cache.hits++;
    blk->lruLabel = ++cache.lruCounter;
    ...
}
cache.misses++;                        // MISS
int victim = choose_victim_block(setIndex);   // free slot, else lowest LRU
if (victim->valid && victim->dirty)           // dirty eviction
    write_block_back_to_memory(victim);
load_block_from_memory(baseAddr);             // memory -> cache

This is where the cumulative design pays off. The cache sits under a simulator that runs real machine code produced by the assembler and linker, so a cache statistic at the end is the end of a chain that started with a line of assembly text.

7.0 The Arc

Laid end to end the sequence is a whole small computer built by hand: text to machine code (assembler), machine code to behavior (simulator), many files to one image (linker), behavior to timing and hazards (pipeline), and memory to a realistic hierarchy (cache).

The lesson that stuck was that the layers are only as trustworthy as the one beneath them. A sign-extension the assembler got wrong is invisible until the simulator branches to the wrong place; a relocation off by one is invisible until the linked program runs. Building the stack yourself is what makes those seams visible.