11.3.1 IntroductionIn general, the design of the processor's control goes hand-in-hand with the design of the data-path interconnect. We can summarize the step-by-step as:
- Start by developing the state diagram and associated register transfer
operations for the processor control unit, assuming that point-to-point
connections are supported by the data-path.
- Next, identify the register interconnections that are not used at
the same time in any control state. You can now replace these by bus-structured
- Revise the state diagram to reflect the register transfer operations
supported by the modified data-path.
- Finally, determine how to implement the register transfer operations by detailed control signal sequences. Revise the state diagram to assert these signals in the desired sequences.
Processor Specification To a first approximation, a computer is de-scribed by its instruction set and programmer-visible registers. Ours is a single accumulator machine. Its instruction format and encoding are shown in Figure 11.14.
The processor's instructions are:
- Load from Memory
LD XXX: Memory
- Store to Memory
ST XXX: AC --> Memory
- Add from Memory
ADD XXX: AC
- Branch if Accumulator Negative
BRN XXX: IF AC<15>
=1 THEN XXX --> PC;
11.3.2 Deriving the State Diagram and DatapathThe state diagram of Figure 11.16 provides only a rough beginning for the detailed state machine. For example, fetching an instruction involves a memory access, and this requires several states. And, as pointed out in the previous section, the details of the data-path interconnections affect the number of cycles required to execute the instruction. The final state diagram will contain several more states than we have shown.
Refining the State Diagram: Overview We start by decomposing the state diagram into its three major components: instruction fetch, operation decode, and operation execution. Throughout this section, we will refine each of these.
To begin, we must decide between a Moore or Mealy style of implementation. Let's choose the latter and assume that our controller will be a synchronous Mealy machine. Control outputs are now associated with transitions rather than states. Asserted control signals take effect when entering the next state.
Reset State It is a good idea to make Reset
)the first state. This starts the machine in a known state when the reset signal is asserted. Also, it provides the place in the state diagram from which a control signal can be asserted to force parts of the data-path to known starting values. Perhaps the most important register to set at Reset is the program counter. In our machine, we will set the PC to 0. The Memory Request line should also be driven to its unasserted value on start-up.
Instruction Fetch Reset
)is followed by a sequence of states to fetch the first instruction from memory
(IF0, IF1, IF2
). The PC is moved to the MAR, followed by a memory read sequence. Revising the Moore machine state fragment of Figure 11.7, we obtain the four-state Mealy sequence shown in Figure 11.17.
Once the Reset signal is no longer asserted, the machine advances to state IF0. On this transition, the control signals to transfer the PC to the MAR are asserted. This is as good a place as any to increment the PC, setting it to point to the next sequential instruction. You should remember that register transfer statements are not like statements in a conventional programming language. The PC increment takes place on the same clock edge that causes the MAR to be loaded with the old value of the PC. Assuming edge-triggered devices, the setup/hold times and propagation delays guarantee that the old value of the PC is transferred to the MAR. We will reexamine these timing considerations in the next sub-section.
Figure 11.7 showed that the four-cycle handshake with memory can begin only when the memory Wait signal is asserted. So we loop in state IF0 until this Wait is asserted.
Once memory is ready to accept a request and Wait is asserted, we can begin a read memory sequence to obtain the instruction. On the transition to state IF1, we set up control signals to gate the MAR to the Memory Address Bus and assert the Read and Request signals.
Once we have entered IF1, the instruction address has been presented to memory and a memory read request has been made. As long as the Wait signal is asserted, these must remain asserted.
We advance to state IF2 when memory finally unasserts Wait, signaling that data is available on the Memory Databus. On this transition it is safe to transfer the values on the memory bus into the MBR. This transition also unasserts the Request signal, indicating to memory that the processor is ready to end the memory cycle. The four-cycle handshake keeps us in this state until the Wait signal is again asserted. On this exit transition, the MBR can be transferred to the IR to begin the next major step in the state machine: operation decode.
Operation Decode Because of the simplicity of our instruction set, the decode stage is simply a single state that tests the op code bits of the instruction register to determine the next state. This is shown in Figure 11.18.
=00, the next state is LD0.
Instruction Execution: LOAD Now we examine the execution sequences for the four instructions, starting with LD. The load execution sequence is given in Figure 11.19.
Instruction Execution: STORE The store execution sequence is shown in Figure 11.20. In essence, it is a memory write sequence that is similar to the load's read sequence. On the transition from the decode state, the address portion of the current instruction is transferred to the MAR while the AC is moved to the MBR. If memory is ready to accept a new request, we begin a write cycle by gating MAR and MBR to the appropriate memory buses while asserting and Request. These signals remain asserted until Wait is unasserted. At this point, the processor resets the handshake and waits for the memory to do the same.
Instruction Execution: BRANCH NEGATIVE
Simplification of the State Diagram Since the instruction fetch sequence already checks whether memory is ready to receive a new request by verifying that Wait is asserted, we can eliminate state ST2. For the same reason, we can eliminate the loop/Wait exit of states LD2 and AD2. Similarly, since the IF2 state completes the processor-memory handshake, we can eliminate the loop back and exit conditions for states LD0, ST0, and AD0. Figure 11.23 gives the complete state diagram, but does not show the detailed register transfer operations.
- Control Signal and Conditional Inputs: Reset
- Control Signal Outputs: 0 --> PC
+1 --> PC
- PC --> MAR
- MAR --> Memory Address Bus
- Memory Data Bus --> MBR
- MBR --> Memory Data Bus
- MBR --> IR
- MBR --> AC
- AC --> MBR
+MBR --> AC
- IR<13:0> --> MAR
- IR<13:0> --> PC
- 1 --> Read/
- 0 --> Read/
- 1 --> Request
11.3.3 Register Transfer Operations and Datapath ControlIn deriving the state diagram of the previous subsection, we assumed there was a direct path between any source and destination of a register transfer operation that we needed. Figure 11.25 shows the implications of this assumption for our data-path. We label the connections with the instruction type
(Load, Store, Add, Branch
(Fetch, Decode, Execute
)that makes use of the path.
We must now determine which of these point-to-point connections can be combined into shared buses. We can combine connections when they are never
)used in the same state.
+MBR --> AC in a single state. Otherwise we would need to revise the portion of the state diagram for the ADD execution sequence to reflect the true sequence of transfers needed to implement this -operation.
In Figure 11.26 the AC is the only register connected to more than one bus
(it can be loaded from the Result Bus or the Memory Bus
). This is called a dual-ported configuration, and it requires additional hardware. It is useful to try to reuse existing connections whenever possible. By using an ALU component that has the ability to pass its B input through to the output, we can implement the load path from the MBR to the AC in the same manner as the add path. We simply instruct the ALU to PASS B rather than ADD A and B. This yields the three-bus architecture introduced in Figure 11.13, eliminating the extra data-path complexity associated with a dual-ported AC. We assume this organization throughout the rest of this subsection.
Implementation of the Register Transfer Operations Now that we have settled on the detailed connections supported by the data-path, we are ready to examine how register transfer operations are implemented. A data-path control point is a signal that causes the data-path to perform some operation when it is asserted. Some control operations, such as ADD, PASS B, 0 --> PC, PC
+1 --> PC, are implemented directly by the ALU and PC functional units. For other operations, such as PC --> MAR, we have to assert more than one control point within the data-path. These more detailed control signals are often called microoperations. Thus, we can decompose a register transfer operation into one or more microoperations, and there is one microoperation for each control point
(for example, a register load or tri-state enable control input
)in the data-path.
As an example, let's examine the register transfer operation PC --> MAR. To implement this, the PC must be gated to the Address Bus while the MAR is loaded from the same bus. In terms of microoperations, PC --> MAR is decomposed into PC --> ABUS and ABUS --> MAR.
Timing of Register Transfer Operations
The Reset signal is captured by a synchronizing flip-flop on the first rising edge in the figure. A propagation delay later, the synchronized version of the reset signal is presented as an input to the control. No matter what state the machine is in, the next state is RES if Reset is asserted. The 0 --> PC microoperation is hardwired to the synchronized Reset signal. The synchronous counter CLR input takes effect at the next rising edge. This coincides with the transition into state RES.
Once we are in state RES, we assume that the Reset input becomes unasserted. Otherwise we would loop in the state, continuously setting the PC to 0 until Reset is no longer asserted. With Reset unasserted, IF0 is the next state and the microoperations PC
+1 --> PC, PC --> ABUS, and ABUS --> MAR are asserted.
Because of the way they are implemented in the data-path, some of these operations take place immediately while others are delayed until the next clock edge/entry into the next state. For example, asserting PC --> ABUS turns on a tri-state buffer. This takes place immediately. Microoperations like PC
+1 --> PC
)and ABUS --> MAR
)are synchronous and therefore are deferred to the next clock event.
In the waveform, soon after entry into RES with Reset removed, we gate the PC onto the ABUS. Even though the PC count signal is asserted, it will not take effect until the next rising edge, so the ABUS correctly receives 0.
On the next rising edge, the MAR latches the ABUS and the PC is incremented. Because the increment propagation delay exceeds the hold time on the MAR load signal, the 0 value of the PC is still on the ABUS at the time the load is complete. When a bus is a destination, the microoperation usually takes place immediately; if a register is a destination, the microoperation's effect is usually delayed.
Tabulation of Register Transfer Operations and Microoperations The relationships between register transfer operations and microoperations are:
This leads us to the revised microoperation signal flow of Figure 11.29.