The Execute Phase

Read time: 18 minutes (4517 words)

We have worked through the Fetch and Decode stage, and you should have a fairly good idea how signals flow through those two steps to get the machine prepared for the real work. Unfortunately, the Execute phase is more complex. This is largely due to the number of different kinds of instructions available to be processed.

In the Instruction Decoding phase, we learned that there are many different ways that instructions can reference things to be processed. Basically, it boils down to these:

  • Modify a single register
  • Modify a single bit in a register
  • Combine two registers
  • Combine a register and an immediate piece of data

For each of these kinds of processing, we need to route signals from the decode barrier register to the appropriate unit in the chip for processing. Usually that means ending up in the ALU, but there are many instructions that do not need the ALU at all. These instructions simply move data from one place to another, so they pass through the Execute stage untouched.

Reviewing the Instructions

Not all instructions need to be handled in this phase. Some will be handled by the last stage.

Here is a subset of our instructions, filtered to just those that involve actual processing in this phase:

Mnemonic OP1 OP2 RTL  
SBI PORT b PORT[b] <- 1
CBI PORT b PORT[b] <- 0
LSL Rd   Rd[n+1] <- Rd[n],Rd[0] <- 0
         
RJMP k   PC <= PC + k + 1
BRNE K   if (Z == 1) PC <- PC + k + 1
SBRS Rr b if (Rb[b] == 1) PC <= PC + 2 or 3
SBRC Rr b if(Rr[b] == 0) PC <- PC + 2 or 3
         
DEC Rd   Rd <- Rd + 1
INC Rd   Rd <- Rd - 1
ADD Rd Rr Rd = Rd + Rr
SUB Rd Rr Rd <- Rd - Rr
         
AND Rd Rr Rd <- Rd AND Rr
OR Rd Rr Rd <- Rd OR Rd
EOR Rd Rd Rd <- Rd XOR Rr
COM Rd   Rd <- OxFF - Rd 1(1)

The first two instructions manipulate single bits within a register. These can be implemented using basic logical operations, if we can form the correct “mask” constant. Fortunately, the bit number, encoded in the instruction provides the basis for this mask!

The LSL instruction is a simple shift of the bits in the register. There are specialized digital components that can do this task, and we can include them in our design next tot he conventional ALU. (They might even be combined into the ALU).

The branching instructions all need a bit of basic math to be done using the PC and a simple constant. The ALU can perform this task if we route the appropriate signals to the operands!

The remaining operations are all simple. We route the two operands directly to the ALU, and select the appropriate operation from the decode step.

ALU Processing

Arguably, processing data through the ALU is the most important kind of work the machine does. We have seen that the internal register memory is designed in a special way, so it can deliver two register data items simultaneously to the ALU. That much of the processing is pretty simple. Here is a simplified look at the data flow for this kind of work:

../_images/simple-alu.png

Of course, we will not return the result of the ALU’s work directly in this phase. That will happen in the final stage.

This is the most simple case for an ALU operation. For the more complex instructions, we need to be able to select from a number of other possible operands.

Here are the additional combinations of operands we need:

  • PC + k + 1
  • PC + 2
  • PC + 3
  • Rd + 1
  • Rd - 1
  • 0xFF - Rd

It looks like we should provide a small set of constants, and provide a way for those to be routes to the ALU when needed.

To accomplish this, we need to set up a multiplexor and create constant inputs for those.

That PC + k combination is not going to work this way. We will be obtaining that constant from the instruction stream, and we need to add that to the PC. So, it looks like we need to route the PC into the ALU together witht hat constant.

So, a simple way into the ALU is not going to work. It will be better to multiplex both operands, and leave it to the controller to make things happen correctly. Here is are the combinations we will need:

Op1 Op2 Op
PC k add
PC 2 add
PC 3 add
Rd 1 add
Rd 1 sub
0xff Rd sub

It looks like we may want to route Rd to either operand in this setup.

We can do that by passing Rd to both multiplexors feeding the ALU.

Multiple ALU components

Except for the addition of an arbitrary constant, the operations involving the ALU are pretty simple. Perhaps it would make sense to split out those operations, and set up a simplified ALU that can handle just those operations. This is commonly done, and we have seem some of that design logic in previous diagrams.

Here is am image of our proposed ALU wiring:

../_images/alu-wiring.png

Note

I took this image with my iPhone. Notice that it is a bit dark, and shows shadows. You can clean this up with image processing, but this is fine for now (and for images for your exam project).