Design

Coert Vonk

Presents a CPU Design for LC-3 instruction set, that we later implement using Verilog HDL. The illustrations help visualize the design. The instruction set is based on the book Introduction to Computer Systems by Patt and Partel. For this text we push the simplicity of this little microprocessor (LC-3) even further as described in Instruction Set.

Design

The microprocessor consists of a Data Path and a Control Unit. Together they implement the various instruction phases.

This section describes an architecture for the LC-3. It aims at staying true to the von Neumann architecture and instruction cycle names. However, here we assume the program counter and instruction register are in the data path.

Data Path

The schematic below shows the Data Path.

own work
LC3 data path

We use the following conventions

  • The shaded blocks are modules that implement various functionality. The module names have been chosen to reflect the instruction phases.
  • Signals connect the blocks. A signal can be a single wire, or a collection of wires such as the 16 bits that represent the value of the program counter. Signal names are chosen to overlap with operand names where possible.
  • The microprocessor connects to an external memory through the external interface.

Modules

Module Description
UpdatePC Maintains the program counter, pc.
Fetch Initiates the bus cycle, to read the instruction pointed to by pc.
Decode Reads the instruction from the memory bus and extracts its operands.
Registers Maintains the register values and processor status register.
ALU Performs arithmetic and logical operations.
Address Calculates memory address for memory or control instructions.
MemoryIF Initiates the external memory bus cycle to read or write data.
DrMux Destination register multiplexor, selects the value that will be written to the destination register.
BusDriver Simple arbiter for memory read requests from Fetch and MemoryIF.

Signals

Group Signal Description
Program counters pc Program Counter
nPC Next program counter (always has the value pc+1)
tPC Target program counter, for JMP / BR*.
Operands sr1ID Source register 1 identifier.
Also used as baseRID for JMP / LDR / STR
sr2ID Source register 2 identifier.
Also used as srID for ST / STI / STR.
imm Immediate value
offset Memory address offset
Register values sr1 Value of the register identified by signal sr1ID
sr2 Value of the register identified by sr2ID
dr Value written to the register identified by drID
psr Value of the processor status register
Intermediate values uOut Result of the ALU operation
aOut=addr=tPC Result of the address calculation
External bus eADDR Memory address
eDIN Instruction/data being read from memory
eDOUT Data being written from memory
eWEA Write enable signal going to memory.
Value 0 for read, 1 for write.
Internal bus iBR0, IBR1 Internal bus request signals
iADDR0, iADDR1 Internal memory addresses
iWEA0, iWEA1 Internal write enable signals

Examples

Read memory

Assume: the instruction at address 3000 is 201F.

Assigning the label LDv to memory location 3020, this instruction decodes to

Address Value Label Mnemonic
x3000 x201F LD r0, LDv
x3020 x1234 LDv

Issuing a reset, triggers the following sequence of events:

# Module Action Signals
1. UpdatePC Resets the program counter to its initial value pc=3000, nPC=3001
2. Fetch Starts a read cycle for the instruction br0=1, iADDR0=3000, iWEA0=0
3. BusDriver Forwards the read cycle to the external memory bus eADDR=3000, eWEA=0
4. ExtMemory Responds with the instruction eDIN=201f
5. Decode Extracts the operands offset=1f, drID=0
6. Address Adds the offset to nPC addr=3020
7. MemoryIF Starts a read cycle for the data iBR1=1, iADDR1=3020, iWEA1=0
8. BusDriver Forwards the read cycle to the external memory bus eADDR=3020, eWEA=0
9. ExtMemory Responds with the data eDIN=1234
10. DrMux Selects the eDIN input dr=1234
11. Registers Writes the value dr to the register identified by drID

ALU operation

Assume: pc=3003, the register R0=1234 and R1=4321. The instruction at the next address 3004 is 1801.

This instruction decodes to

Address Value Label Mnemonic
x3004 x1801 ADD R4, R0, R1

The following sequence of events will happen:

.
# Module Action Signals
1. UpdatePC Increments the program counter pc=3004
2. Fetch Starts a read cycle for the instruction iBR0=1, iADDR0=3004, iWEA0=0
3. BusDriver Forwards the read cycle to the external memory bus eADDR=3004, eWEA=0
4. ExtMemory Responds with the instruction eDIN=1801
5. Decode Extracts the operands sr1ID=0, sr2ID=1, drID=4
6. Registers Supplies the values for the registers identified by sr1ID and sr2ID sr1=1234, sr2=4321
7. ALU Calculates the sum of sr1 and sr2 uOut=5555
8. DrMux Selects the uOut input. dr=5555
9. Registers Writes the value dr to the register identified by drID

Write memory

Assume: pc=3007, register R4=AAAA and the label STIa refers to data address 3024 containing the value 3028. The instruction at the next address 3008 is B81D.

This instruction decodes to

Address Value Label Mnemonic
x3008 xB81D STI R4, STIa
x3024 x3028 STIa
x3028 xBAD0

The following sequence of events will happen:

.
# Module Action Signals
1. UpdatePC Increments the program counter pc=3008, nPC=3009
2. Fetch Starts a read cycle for the instruction. iBR0=1, iADDR0=3008, iWEA0=0
3. Bus driver Forwards the read cycle to the external memory bus. eADDR=3008, eWEA=0
4. ExtMemory Responds with the instruction. eDIN=b81f
5. Decode Extracts the operands (sr2ID represents the SR operand) sr2ID=4, offset=1d
6. Registers Supplies the value for the register identified by sr2ID sr2=aaaa
7. Address Adds the offset to nPC addr=3024
8. MemoryIF Starts a read cycle to retrieve the address where to store the value. iBR1=1, iADDR1=3024, iWEA1=0
9. BusDriver Forwards the read cycle to the external memory bus. eADDR=3024, eWEA=0
10. ExtMemory Responds with the value eDIN=3028
11. MemoryIF Starts a write cycle to write the value of register R4 to address 3028 iBR1=1, iADDR1=3028, iWEA1=1
12. BusDriver Forwards the write cycle to the external memory bus. eADDR=3028, eWEA=1

Control unit

Instructions can be broken up into micro instructions. These can be implemented using a finite state machine (FSM), where each state corresponds to one micro instruction.

The finite state machine can be visualized as shown in the figure below.

  • circles, represent the states identified by a unique number and name.
  • double circle, represents the initial state.
  • arrows, represent state transitions. Labels represent the condition that must be met for the transition to occur.
  • shading, is used to identify the implementation modules.
  • eREADY, indicates that the external memory finished a read or write operation.
  • iType, maType, indType refer to the generalized instruction types generated by Decoder.

State diagram

own work
LC3 finite state machine

Details

  • Policies:
    • State transitions, are only possible during the falling edge of the clock signal (from 1 to 0);
    • Outputs, to the external memory interface, are driven in response to state transitions;
    • Inputs, from the external memory interface, are sampled on the rising edge of the clock signal (from 0 to 1);
    • Control signals, change only during the falling edge of the clock signal to minimize glitches.
  • Each state:
    • depends on both input signals and the previous state’
    • generates control signals control signals for the data path (with the help of the Decode module).
  • The control unit consists of two modules:
    • State, implements the state machine, and generates state specific control signals.
    • Decode, generalizes the instruction for the state machine, and generates state independent control signals.

Schematic for the control unit

own work
LC3 control unit

The next section describes the signals for the control unit in the CPU Design for LC-3 instruction set.

Signals for the control unit

Group Signal Description
External interface eREADY==1 Indicates that the external memory finished a read or write operation.
clock External supplied clock
Internal to the State module state Current state
nState Next state as determined by the combinational logic
Generalized instruction types (bundled into cCtrl) iType Instruction type
maType Memory access type
indType Indirect memory access type
Data path control pNext Signals UpdatePC to change the program counter to tPC
pEn Enables UpdatePC to change the program counter.
fEn Enable Fetch to start external memory bus cycle to read the instruction.
dEn Enables Decode to read the instruction from the external memory bus.
rWe Enables Registers to store the value of dr in the register identified by drID.
uOp Chooses the operation and inputs of the ALU
aOp Chooses the operation and inputs of the Address calculation.
mOp Chooses the memory operation to be performed by MemoryIF.
drSrc Selects the destination register source input on DrMux

The next section gives a detailed description of the modules for the CPU Design for LC-3 instruction set.

Modules (detailed description)

Module Description
State Generates the state specific control signals for each micro instruction being executed. Refer to the signals described above for details.
UpdatePC Updates the program counter, pc, at the end of each instruction cycle. The new value is:
  • 3000 if reset is asserted, or
  • the value of the tPC input, when a JMP or BR* instruction was executed (and its condition was met), or
  • otherwise, the previous value of pc+1.
Fetch
  • Initiates the external bus cycle (iBR0, iADDR0, iWEA0) to read the instruction from the memory location pointed to by pc.
  • The control unit will maintain this state until the external memory reports that the data is available (eREADY).
Decode
  • Finishes the external bus cycle by reading the instruction from the external memory bus (eDIN).
  • Decodes the instruction:
    • Based on the opcode (ir[15:11], it generalizes the instruction type for the State module (cCtrl).
    • Based on the operands (ir[10:0]), it configures the data path using state independent control signals:
      • For ALU instructions, uOp, sr1ID, sr2ID, drSrc, drID
      • For memory instructions, aOp, sr1ID (BaseR for LDR / STR), sr2ID (sr for ST / STI / STR), offset, drID
      • For control instructions, pNext, sr1 (BaseR for JMP).
Registers
  • Maintains the general purpose register (R0..R7).
  • Supplies the values for the registers identified by sr1ID, sr2ID.
  • Updates the register specified by drID to the value dr when rWe is asserted.
ALU
  • The input uOp selects both the operation type and inputs.
    • For ADD do if ir[5]==1 then uOut=sr1+imm5, else uOut=sr1+sr2.
    • For AND do if ir[5]==1 then uOut=sr1&imm5, else uOut=sr1&sr2.
    • For NOT do uOut=~sr1.
Address
  • Input aOp selects both the calculation type and inputs.
    • For BR* do aOut=nPC+offset9.
    • For LD / LDI / LEA / ST / STI, do aOut=nPC+offset9.
    • For JMP / LDR / STR, do aOut=sr1+offset6.
  • Note that aOut is connected to the addr input on MemoryIF, and the tPC input on FetchPC.
MemoryIF
  • Input mOp selects the memory access mode and inputs.
    • For LDI / STI, under the direction of the Control Unit, it first initiates a memory read cycle for addr (aOut). The Control Unit will maintain this state until the external memory reports that the data is available (eREADY). It then takes the value read from memory (eDIN), and
      • for LDI, it initiates a read cycle for address eDIN;
      • for STI, it initiates a write cycle to write the value sr2 to address eDIN.
    • For the other instructions, it takes the address, and
      • for LD / LDR, read the value from addr (aOut);
      • for LEA, do nothing;
      • for ST / STR, write the value sr2 to addr (aOut).
    • The control unit will maintain this state until the external memory reports that the data is available (eREADY).
DrMux*
  • Input drSrc selects the value that will be written to the destination register.
    • For ADD / AND / NOT do forward uOut to dr.
    • For LD / LDR / LDI do forward deign to dr.
    • For LEA do forward aOut to dr.

*) DrMux is an abbreviation for Destination Register Multiplexor.

To continue this CPU Design for LC-3 instruction set, read about its implementation on the next page.