Step 1: Fetch

Read time: 18 minutes (4714 words)

The first step in building our simulator focuses on fetching a single instruction from the instruction memory. This machine we are building needs to have a way of figuring out where that instruction lives in the memory used to store code. We will create a simple register, which we will call the Program Conter, PC for short, to hold that piece of data.

At this point the development of our machine, we do not really care what an instruction looks like. In the attiny85, all instructions are 16-bits wide. The chip we are focusing on has eight kilobytes (four kilowords) of instruction memory. The program counter needs to generate an address big enough to span this entire memory area, which means it needs to be at least 12 bits big. The AVR family uses 16-bit registers, and some AVR chips have much more memory. The Arduino for example, has 32 kilobytes of memory available. (You will be surprised in what you can do with just 4096 instructions in the machine.)

Note

You Windows programmers probably have never constructed a real program this small, because actually interfacing with the OS takes a lot of code. Oh well, that is why we have gigabytes of RAM these days!

Lets start off with a simple register which will be our Program Counter:

Note

That small triangle at the bottom of this component indicates that this is a “clocked” component, one that does its work only when the clock “tick” signal is received. This is a “sequential” component. Any component not showing this triangle is a “combinational” component, one that simply does its internal work when input signals change.

The Program Counter is a simple register, meaning that when the clock tick comes along, what is on the input side (next addr) is copied, untouched, to the output side (next addr). We already know that the output from the PC register passes on to the instruction memory unit to retrieve the next instruction to process.

We need to consider what comes in on that input side. Obviously, that will be the next address to be fetched. For most instructions in our attiny85 chip, that instruction is the next “word” in the instruction memory. Since we will address out instruction memory in “word” chinks (not bytes) that means we need to increment the current address and put it back into the next address input. How we do this depends on how we want to design the machine.

Building an increment unit, which is a very simple ALU that only knows one trick, is so easy, it is common to put such a device near to the PC so that next address calculation can happen quickly, even on the same clock tick.

So, we could build something like this:

This arrangement is fine if all instructions are exactly the same size. However, we know that some instructions are two words in size, so this will not work. Even worse, to allow for branches, we need to allow the PC to be updated from some incoming source, probably determined further down the processing chain.

Let’s introduce an incoming address and allow a control signal to determine if we simply increment, or use the new value. This is a job for a multiplexor, controlled by a control signal.

The addition of a “branch address” input requires a control signal that decides if we use the “next address” calculated by the increment component, or this new address signal coming from elsewhere in the system. The “multiplexor” will select the correct “next address” source based on the control signal “branch”.

To complete this setup, we need to add in the “instruction memory” unit. Since this is a read only unit (at this point), it can be treated like a combinational unit, meaning that we feed in an address and it immediately (well close) delivers a new instruction.

A high level view of this entire setup looks like this:

Note

We will not actually build this unit this way, since we need to work through how to construct the machine out of very simple parts.

Building a “Real” Fetch Unit

Hardware designers do not think in terms of electrical circuits much these days. Instead, they think in code. The languages used for this kind of design work are called Hardware Description Languages, or HDL. One of the most popular languages used for designing digital systems today is Verilog. This language is close enough to C/C++ that you should be able to read it, even if you have never seen anything written in the language.

Here is a chunk of Verilog code used in a real digital system:

fetch unit
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
module fetch(clk, baddr, inst, reset);
    output reg [15:0] inst = 0;
    input wire signed [15:0] naddr;
    input wire clk, reset;

    always @(posedge clk) begin
        if (reset) begin
            $display("reset")
            out <= 0;
        end else begin
            $display("pc = %d", naddr);
            out <= naddr;
        end
    end
endmodule

Notice there is one more signal in this code, not shown in the diagram. A reset line is typically added to allow the PC to be set to zero, which for the AVR family, is where all code starts.

Building the Fetch Unit

We have enough of a definition for this stage to build the fetch unit. Your next lab project will begin building this unit by setting up a program counter register.