E85 Home Work 10 (05 Fall)

1. As discussed in class, the control unit of a multi-cycle processor can be implemented as a finite-state machine (FSM) with each of its states representing one of the steps in the execution of the instructions. The FSM is composed with
   • Internal states: each corresponding one of the steps in execution of the instructions, represented by the circles in figures 7.39;
   • Inputs: the six bits of Op-code field of the instructions;
   • Outputs: the control signals needed for the step represented by the present state;

   
   

   $$\begin{tabular}{c\vert c\vert\vert cccccc} \hline Instruction... ... 1 \\ sw & 43 & 1 & 0 & 1 & 0 & 1 & 1 \hline \end{tabular}$$
   
   

   The hardware implementation of the FSM includes:

   • A set of flip-flops for the states (steps);
   • Next state decoder to generate the next state based on (a) the present state and (b) the inputS, the Op-code field of the current instruction;
   • Output decoder to generate the outputs, the control signals needed for the current step.

   Figure 7.38 shows the 12 states of the FSM control unit that can execute instructions j, addi, as well as R-type instructions, and lw, sw, beq. Fill out the table below (by 0 or 1) to identify which control signals need to be asserted for each of the 12 states. (Control signals for state 0 are given as examples.)

   
   

   $$\begin{tabular}{r\vert l\vert\vert c\vert c\vert c\vert c\ver... ... 16 & RegDst & 0 & & & & & & & & & & & \hline \end{tabular}$$
   
   

   Solution:

   
   

   $$\begin{tabular}{r\vert l\vert\vert c\vert c\vert c\vert c\ver... ...0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \hline \end{tabular}$$
   
   

2. Design, by filling out the table below, the combinational circuit that generates the next state ($NS3$ through $NS0$), based on (a) the present state ($S3$ through $S0$)and (b) the 6-bit Op-code of the current instruction ($Op5$ through $Op0$, inputs to FSM).

   Note that for all states except states 1 and 2 with multiple branches, where the next state depends on the Op-code of the current instruction, the next state only depends on the present state, i.e., the inputs can be treated as ``don't-cares'' marked by x. (The first two rows are filled out as examples.)

   
   

   $$\begin{tabular}{c\vert cccc\vert c\vert cccccc\vert\vert c\ve... ... & 0 & 1 & 1 & x & & & & & & & & & & & \hline \end{tabular}$$
   
   

   Solution:

   
   

   $$\begin{tabular}{c\vert cccc\vert c\vert cccccc\vert\vert c\ve... ... 1 & x & & & & & & & 0 & 0 & 0 & 0 & 0 \hline \end{tabular}$$
   
   

3. To implement the instruction addi, two extra states (9 and 10) were added in figure 7.37, increasing the total number of states of the FSM from 9 to 11. Find an alternative way to implement addi with only one extra state, instead of two. Explain specifically how this can be done.

   Solution: From state 1, same as lw and sw, branch to state 2, which is identical to state 9, and then branch to the newly added state 10 upon seeing addi. The conditional branches in states 1 and 2 need to be modified to accommodate the new instruction addi.

4. The figure below shows a programmable logic array (PLA) composed of an AND array followed by an OR array to implement both the next state decoder and the output decoder of the FSM controller of the MIPS milti-cycle processor. The AND array is already properly connected to form the terms for the states and some other terms needed for the conditional branches in states 1 and 2. Now you need to fill out the AND array that generates the output (control signals) and the next state (NS3 through NS0).

   Note that this is a Moore FSM whose outputs only depend on the state, i.e., the control signals only need to be properly connected to the 12 vertical wires on the left for the states, while the next state (NS3 through NS0) need to be properly connected to not only the wires for states on the left but also the wires on the right for the next state of states 1 and 2, which depends on the input (current instruction) as well as current state.

   In the figure some control signals (such as RegDst and MemToReg) have two bits while you may need only one, ignore the higher bit.

   

   Solution: