388
`
`Chapter s The Processor: Datapath and Control
`
`5.4 A Multicycle Implementation
`
`389
`
`4. Memory access or R-type instruction completion step
`During this step, a load or store instruction accesses memo~y and an
`arithmetic-logical instruction writes its result. When a value is retn~ved from
`memory it is stored into the memory data register (MDR), where it must be
`used on the next clock cycle.
`
`Memory reference:
`MOR= Memory [ALUOut] ;
`
`or
`
`Memory [ALUOutJ = B;
`Operation: If the instruction is a load, a data word is retrieved from ~emo~y
`and is written into the MDR. If the instruction is a store, then the data is w~it(cid:173)
`ten into memory. In either case, the address used is the one computed durm_g
`the previous step and stored in ALUOut. For a store, the s?urce operand is
`saved in B. (B is actually read twice, once in step 2 and once m stef 3. _Luckily,
`the same value is read both times, since the register number-which is s~ored
`in IR and used to read from the register file-does not change.) The signal
`MemRead (for a load) or Mem Write (for store) will need to be asserted. In
`addition, for loads and stores, the signal IorD is set to 1 to force. the ~emory
`address to come from the ALU, rather than the PC. Since MDR is wntten on
`every clock cycle, no explicit control signal need be asserted.
`
`Arithmetic-logical instruction (R-type):
`Reg[IR[15 - ll]J = ALUOut ;
`Operation: Place the contents of ALUOut, ':"hich corresponds _to the outp_ut of
`the ALU operation in the previous cycle, mto the Result register. The signal
`RegDst must be set to 1 (to force the rd (bits 15-11) field to be used to select
`the register file entry to write). RegWrite must be asserted, and MemtoReg
`must be set to O (so that the output of the ALU is written, as opposed to the
`memory data output).
`
`s. Memory read completion step
`During this step, loads complete by writing back the value from memory.
`
`Load:
`Reg[IR[Z0 -16]] = MDR ;
`Operation: Write the load data, which was stored into MDR in t_he previous
`cycle, into the register file. To do this, we set M_emtoReg = 1 (to wnte the ~esult
`from memory), assert RegWrite (to cause a wnte), and we make RegDst - 0 to
`choose the rt (bits 20-16) field as the register number.
`
`Step name
`
`Instruction fetch
`
`Instruction
`decode/ register fetch
`
`Execution , address
`computation, branch/
`jump completion
`Memory access or R-type
`completion
`
`Memory read completion
`
`Action for R•type
`instructions
`
`Action for memory•
`reference instructions
`
`Action for
`branches
`
`Action for
`jumps
`
`ALUOut = A op B
`
`Reg [IR[15-11]] =
`ALU Out
`
`IR = Memory(PC]
`PC = PC+4
`A = Reg [IR[25-21]]
`B = Reg [IR[20-16]]
`ALUOut = PC + (sign-extend (IR[15-0]) « 2)
`ALUOut = A + sign-exte nd
`if (A == B) then
`(IR[15-0])
`PC = ALUOut
`
`Load: MOR = Memory[ALUOut]
`or
`Store: Memory [ALUOut] = B
`Load: Reg(IR[20- 16]] = MDR
`
`I
`
`-
`
`- - -
`PC= PC [31- 28] II
`(IR[25-0]« 2)
`
`I
`
`~
`
`-
`
`-
`
`I
`I
`
`~ 7
`
`-
`
`- -~
`
`FIGURE 5.35 Summary of the steps taken to execute any inst ruction class. Instructi ons ta ke from three to five exe(cid:173)
`cution steps. The first two steps are independent of the instruction class. After th ese steps, an instruction ta kes fro m one to
`three more cycles to complete, d epending on the instruction class. The empty entries for the Mem ory access step or the
`Memory read completion step indicate that th e particular instruction class ta kes fewer cycles. In a multicycle im plemen ta(cid:173)
`tion, a new instruction will be started as soon as the current ins tru cti on completes, so these cycles are not id le or wasted.
`As mentioned earlier, the register file actually reads every cycle, but as long as th e IR d oes not cha nge, the va lues read from
`the register file are identical. In particular, the value read into register B durin g th e Instru cti on decod e stage, for a branch or
`R-type instruction, is the same as the value stored into B during th e Execution stage a nd th en used in the Memory access
`stage for a store w ord instruction.
`
`This five-step sequence is summarized in Figure 5.35. From this sequence
`we can determine what the control must do on each clock cycle.
`
`..
`Defining the Control
`
`Now that we have determined what the control signals are and when they
`must be asserted, we can implement the control unit. To design the control
`unit for the single-cycle datapath, we used a set of truth tables that specified
`the setting of the control signals based on the instru ction class. For the multi(cid:173)
`cycle datapath, the control is more complex because the instruction is exe(cid:173)
`cuted in a series of steps. The control for the multicycle da ta path must specify
`both the signals to be set in any step and the next step in the sequence.
`In this subsection and in section 5.5, we will look a t two different techniques
`to specify the control. The first technique is based on finite state machines that
`are usually represented graphically. The second technique, called J11icropro(cid:173)
`gramming, uses a programming representation for control. Both of these
`techniques represent the control in a form that allows the detailed implemen(cid:173)
`tation-using gates, ROMs, or PLAs-to be synthesized by a CAD system. In
`this chapter, we will focus on the design of the control and its representation in
`these two forms. If you are interested in how these control specifica tions are
`
`INTEL - 1012
`
`

`

`390
`
`Chapter 5 The Processor: Datapath and Control
`
`5.4 A Multicycle Implementation
`
`391
`
`translated into actual hardware, Appendix C continues the development of
`this chapter, translating the multicycle control unit to a detailed hardware im(cid:173)
`plementation. The key ideas of control can be grasped from this chapter with(cid:173)
`out examining the material in Appendix C. However, if you want to get down
`to the bits, Appendix C can show you how to do it!
`The first method we use to specify the multicycle control is a finite state ma-
`chine. A finite state machine consists of a set of states and directions on how to
`change states. The directions are defined by a next-state function, which maps
`the current state and the inputs to a new state. When we use a finite state ma(cid:173)
`chine for control, each state also specifies a set of outputs that are asserted
`when the machine is in that state. The implementation of a finite state machine
`usually assumes that all outputs that are not explicitly asserted are deasserted.
`The correct operation of the datapath depends on the fact that a signal that is
`not explicitly asserted is deasserted, rather than acting as a don't care. For ex(cid:173)
`ample, the RegWrite signal should be asserted only when a register file entry
`is to be written; when it is not explicitly asserted, it must be deasserted.
`Multiplexor controls are slightly different, since they select one of the inputs
`whether they are O or 1. Thus, in the finite state machine, we always specify the
`setting of all the multiplexor controls that we care about. When we implement
`the finite state machine with logic, setting a control to O may be the default and
`thus may not require any gates. A simple example of a finite state machine ap(cid:173)
`pears in Appendix B, and if you are unfamiliar with the concept of a finite state
`machine, you may want to examine Appendix B before proceeding.
`The finite state control essentially corresponds to the five steps of execution
`shown on pages 385 through 388; each state in the finite state machine will take
`1 clock cycle. The finite state machine will consist of several parts. Since the
`first two steps of execution are identical for every instruction, the initial two
`states of the finite state machine will be common for all instructions. Steps 3
`through 5 differ, depending on the opcode. After the execution of the last step
`for a particular instruction class, the finite state machine will return to the
`initial state to begin fetching the next instruction.
`Figure 5.36 shows this abstracted representation of the finite state machine.
`To fill in the details of the finite state machine, we will first expand the instruc(cid:173)
`tion fetch and decode portion, then we will show the states (and actions) for
`the different instruction classes.
`We show the first two states of the finite state machine in Figure 5.37 using
`a traditional graphic representation. We number the states to simplify the ex(cid:173)
`planation, though the numbers are arbitrary. State 0, corresponding to step 1,
`is the starting state of the machine.
`The signals that are asserted in each state are shown within the circle repre-
`senting the state. The arcs between states define the next state and are labeled
`
`Start
`
`!
`
`!
`Instruction fetch/decode and register fetch
`(Figure 5.37)
`
`l
`
`Memory access
`instructions
`(Figure 5.38)
`I
`
`l
`
`l
`
`l
`
`R-type instructions
`(Figure 5.39)
`I
`
`Branch instruction
`(Figure 5.40)
`I
`
`Jump instruction
`(Figure 5.41)
`
`I
`
`..
`.
`t
`
`FIGURE 5.36 The hi gh level view of the fm1te state ma hi
`·
`dent of the instruction class· then a series of se
`c ne con rol. The first steps are indepen-
`complete each instruction class After com
`_quences that depend on the instruction opcode are used to
`returns to fetch a new instruc;ion Each J~etm~~~e ;.chons needed for that instruction class, the control
`labeled Start marks the state in which to beg~:n his th1gufi~e m_ay represent one to several states. The arc
`1 w en
`e rst mstruchon 1s to be fetched.
`
`0
`
`'S t a r t - - - -
`
`Instruction decode/
`Register fetch
`
`Memory-reference FSM
`(Figure 5.38)
`
`R-type FSM
`(Figure 5.39)
`
`Branch FSM
`(Figure 5.40)
`
`Jump FSM
`(Figure 5.41)
`
`5 36 I h i structlon Is identic~I. These states correspond to
`FIGURE 5.37 The Instruction fetch and decode portion of ever in
`·~t t ;
`the top box in the abstract finite state machine in Fig
`read an instruction and write it into the Instruction ur~ t.
`rst state we assert two signals to cause the memory to
`as the address source. The signals ALUSrcA ALU~eg~s ~{uim ;~~a~d IRWrite), and we set lorD to Oto choose the PC
`P,
`nte, and PCSource are set to compute PC+ 4 and
`store it into the PC. (It will also be stored i 't AL~; ' b
`branch target address by setting ALUSrcB ton1~ (causinu\heu:hn~v~r u:d. from there.). In the nex_t state, we compute the
`the ALU), setting ALUSrcA to 0 and ALUO
`t 00·
`g
`I e an . sign-extended lower 16 bits of the IR to be sent to
`, we store the result m the ALUOut
`· t
`h. h ·
`·
`P o
`eye e. There are four next states that depend on the I
`.
`.
`.
`.
`reg1s er, w ic
`is wntten on every
`f th
`1
`unit input, called Op, is used to determine which of ~h::: :res ;01~i:;::,10n, which is known during this state. The control
`
`·
`
`INTEL - 1012
`
`

`

`392
`
`Chapter 5 The Processor: Datapath and Control
`
`5.4 A Multicycle lmplementatlon
`
`393
`
`with conditions that select a specific next state when multiple next states are
`possible. After state 1, the signals asserted depend on the class of instruction.
`Thus, the finite state machine has four arcs exiting state 1, corresponding to the
`four instruction classes: memory reference, R-type, branch on equal, and
`jump. This process of branching to different states depending on the instruc(cid:173)
`tion is called decoding, since the choice of the next state, and hence the actions
`that follow, depend on the instruction class.
`Figure 5.38 shows the portion of the finite state machine needed to imple(cid:173)
`ment the memory-reference instructions. For the memory-reference instruc(cid:173)
`tions, the first state after fetching the instruction and registers computes the
`memory address (state 2). To compute the memory address, the ALU input
`multiplexors must be set so that the first input is the A register, while the sec(cid:173)
`ond input is the sign-extended displacement field; the result is written into the
`ALUOut register. After the memory address calculation, the memory should
`be read or written; this requires two different states. If the instruction opcode
`is l w, then state 3 (corresponding to the step Memory access) does the memory
`read (MemRead is asserted). The output of the memory is always written into
`MOR. If it is sw, state 5 does a memory write (MemWrite is asserted). In states
`3 and 5, the signal IorD is set to 1 to force the memory address to come from
`the ALU. After performing a write, the instruction s w has completed execution,
`and the next state is state 0. If the instruction is a load, however, another state
`(state 4) is needed to write the result from the memory into the register file.
`Setting the multiplexor controls MemtoReg = 1 and RegDst = 0 will send the
`loaded value in the MOR to be written into the register file, using rt as the reg(cid:173)
`ister number. After this state, corresponding to the Memory read completion
`step, the next state is state 0.
`To implement the R-type instructions requires two states corresponding to
`steps 3 (Execute) and 4 (R-type completion). Figure 5.39 shows this two-state
`portion of the finite state machine. State 6 asserts ALUSrcA and sets the ALUS(cid:173)
`rcB signals to 00; this forces the two registers that were read from the register
`file to be used as inputs to the ALU. Setting ALUOp to 10 causes the ALU con(cid:173)
`trol unit to use the function field to set the ALU control signals. In state 7, Reg(cid:173)
`Write is asserted to cause the register file to write, RegDst is asserted to cause
`the rd field to be used as the register number of the destination, and MemtoReg
`is deasserted to select ALUOut as the source of the value to write into the reg(cid:173)
`ister file.
`For branches, only a single additional state is necessary, because they com(cid:173)
`plete execution during the third step of instruction execution. During this
`state, the control signals that cause the ALU to compare the contents of regis(cid:173)
`ters A and B must be set, and the signals that cause the PC to be written condi(cid:173)
`tionally with the address in the ALUOut register are also set. To perform the
`
`i
`
`.,
`~
`I'
`
`' '
`
`I,
`I
`I
`
`2
`
`From state 1
`
`(Op= 'LW') or (Op= 'SW')
`
`Memory address computation
`
`----
`
`MemWrite
`lorD = 1
`
`--~Memory read completion step
`
`4
`
`RegWrite
`MemtoReg = 1
`RegDst = o
`
`To state O
`(Figure 5.37)
`
`FIGURE 5.38 The finite state machine for controlling memory-reference Instructions has
`four states. These states correspond to the box labeled "Memory access instructions" in
`Figure 5.36. After performing a memory address calculation, a separate sequence is needl•d for
`load and for store. The setting of the control signals ALUSrcA, ALUSrcB, and ALUOp is used to
`cause the memory address computation in state 2. Loads require an extra state to write the result
`from the MOR (where the result is written in state 3) into the register file.
`
`comparison requires that we assert ALUSrcA and set ALUSrcB to 00, and set
`the ALUOp value to 01 (forcing a subtract). (We use only the Zero output of the
`ALU, not the result of the subtraction.) To control the writing of the PC, we as(cid:173)
`sert PCWriteCond and set PCSource = 01, which will cause the value in the
`
`INTEL - 1012
`
`

`

`394
`
`Chapter 5 The Processor: Datapath and Control
`
`From state 1
`(Op= R-type)
`
`Execution
`
`T
`
`I
`
`'. I
`
`To state 0
`(Figure 5.37)
`
`FIGURE 5.39 R-type instructions can be Implemented with a simple two-state finite
`state machine. These states correspond to the box labeled "R-type instructions" in Figure 5.36.
`The first state causes the ALU operation to occur, while the second state causes the ALU result
`(which is in ALUOut) to be written in the register file. The three signals asserted during state 7
`cause the contents of ALUOut to be written into the register file in the entry specified by the rd
`field of the Instruction register.
`
`ALUOut register (containing the branch address calculated in state 1, Figure
`5.37 on page 391) to be written into the PC if the Zero bit out of the ALU is as(cid:173)
`serted. Figure 5.40 shows this single state.
`The last instruction class is jump; like branch, it requires only a single state
`(shown in Figure 5.41) to complete its execution. In this state, the signal
`PCWrite is asserted to cause the PC to be written. By setting PCSource to 10,
`the value supplied for writing will be the lower 26 bits of the Instruction
`register with 00two added as the low-order bits concatenated with the upper 4
`bits of the PC.
`We can now put these pieces of the finite state machine together to form a
`specification for the control unit, as shown in Figure 5.42. In each state, the sig(cid:173)
`nals that are asserted are shown. The next state depends on the opcode bits of
`the instruction, so we label the arcs with a comparison for the corresponding
`instruction opcodes.
`
`I
`
`'
`
`1
`
`5.4 A Multlcycle Implementation
`
`395
`
`From state 1
`(Op= 'BEQ')
`
`ALUSrcA = 1
`ALUSrcB = 00
`ALUOp = 01
`PCWriteCond
`PCSource = 01
`
`To state o
`(Figure 5.37)
`
`FIGURE 5.40 The branch Instruction requires a slngle state. The first three outputs that
`are asserted cause the ALU to c~mpare the registers (ALUSrcA, ALUSrcB, and ALUOp), while
`'.he signals _PCSource and PCWnteCond perform the conditional write if the branch condition
`1s true. Notice that we do not use the value written into ALUOut; instead, we use only the Zero
`output of the ALU. The branch target address is read from ALUOut, where it was saved at the
`end of state 1.
`
`From state 1
`
`To state 0
`(Figure 5.37)
`
`FIGURE 5.41 The Jump Instruction requires a single state that asserts two control sig(cid:173)
`nals to write the PC with the lower 26 bits of the Instruction register shifted left 2 bits
`and concatenated to the upper 4 bits of the PC of this instruction.
`
`Given this implei:nentation, and the knowledge that each state requires 1
`clock cycle, we can fmd the CPI for a typical instruction mix.
`
`INTEL - 1012
`
`

`

`396
`
`Chapter 5 The Processor: Datapath and Control
`
`5.4 A Multicycle Implementation
`
`397
`
`Instruction decode/
`register fetch
`
`=-'
`C. s Jump
`com pletion
`
`Start
`
`Instruction fetch
`
`0
`
`MemRead
`ALUSrcA = 0
`lorD = 0
`IRWrite
`ALUSrcB = 01
`ALUOp = 00
`PCWrite
`
`Memory address
`
`2
`
`ALUSrcA = 1
`ALUSrcB = 10
`ALUOp = 00
`
`r~
`
`~
`
`'5'~
`_)
`
`Meinory
`access
`
`3:
`=-'
`s
`
`C.
`
`MemRead
`lorD = 1
`
`Meinory read
`___ c_ornpletion step
`
`RegDst=0
`RegWrite
`MemtoReg=1
`
`R-type coinpletion
`
`7
`
`RegDst = 1
`RegWrite
`MemtoReg = 0
`
`FIGURE 5.42 The complete finite state machine control for the datapath shown In Figure 5.33. The labels on the
`arcs are conditions that are tested to determine which state is the next state; when the next state is unconditional, no label is
`given. The labels inside the nodes indicate the output signals asserted during that state; we always specify the setting of a
`multiplexor control signal if the correct operation requires it. Hence, in some states a multiplexor control will be set to 0. In
`Appendix C, we examine how to turn this finite state machine into logic equations and look at how to implement those
`logic equations.
`
`Example
`
`Answer
`
`CPI In a Multicycle CPU
`
`Using the control shown in Figure 5.42 and the gee instruction mix shown
`in Figure 4.54 on page 311, what is the CPI, assuming that each state re(cid:173)
`quires 1 clock cycle?
`
`The mix is 23% loads (1 % load byte+ 1 % load halfword+ 21 % load word),
`13% stores (1 % store byte+ 12% store word), 19% branches (9% BEQ, 8%
`BNE, 1 % BLTZ, 1 % BGEZ), 2% jumps (1 % jal + 1 % jr), and 43% ALU (all
`the rest of the mix) . From Figure 5.42, the number of clock cycles for each
`instruction class is the following:
`(cid:127) Loads: 5
`(cid:127) Stores: 4
`(cid:127) ALU instructions: 4
`(cid:127) Branches: 3
`(cid:127)
`Jumps: 3
`
`The CPI is given by the following:
`
`CPU clock cycles _ "Instruction count; x CPI,
`CPI=----~-'---
`£..,;
`Instruction count -
`Instruction count
`
`I Instruction count;
`
`.
`Instruction count
`
`x CPI
`'
`
`=
`
`The ratio
`
`Instruction count;
`Instruction count
`
`is simply the instruction frequency for the instruction class i. We can there(cid:173)
`fore substitute to obtain
`
`CPI= 0.23 x 5 + 0.13 x 4 + 0.43 x 4 + 0.19 x 3 + 0.02 x 3 = 4.02
`
`This CPI is better than the worst-case CPI would have been if all the in(cid:173)
`structions took the same number of clock cycles (5).
`
`INTEL - 1012
`
`

`

`398
`
`Chapter 5 The Processor: Datapath and Control
`
`5.5 Microprogramming: Simplifying Control Design
`
`399
`
`Combinational
`control logic
`
`Datapath control outputs
`
`Outputs
`
`Inputs
`
`Inputs from instruction State register
`register opcode field
`
`Next state
`
`FIGURE 5.43 Finite state machine controllers are typically Implemented using a block
`of comblnatlonal loglc and a register to hold the current state. The outputs of the combina(cid:173)
`tional logic are the next-state number and the control signals to be asserted for the curren_t state.
`The inputs to the combinational logic are the current state and any inputs used to determm~ the
`next state. In this case, the inputs are the instruction register opcode bits. NotICe that m the firute
`state machine used in this chapter, the outputs depend only on the current state, not on the
`inputs. The following elaboration explains this in more detail.
`
`A finite state machine can be implemented with a temporary register that
`holds the current state and a block of combinational logic that determines both
`the datapath signals to be asserted as well as the next state. Figure 5.43 shows
`how such an implementation might look. Appendix C describes in detail how
`the finite state machine is implemented using this structure. In section C.3, the
`combinational control logic for the finite state machine of Figure 5.42 is imple(cid:173)
`mented both with a ROM (read-only memory) and a PLA (programmable log(cid:173)
`ic array). (Also see Appendix B for a description of these logic elements.) In the
`next section of this chapter, we consider another way to represent control. Both
`of these techniques are simply different representations of the same control in(cid:173)
`formation.
`
`Elaboration: The style of finite state machine in Figure 5.43 is called a Moore
`machine, after Edward Moore. Its identifying characteristic is that the output depends
`only on the current state. For a Moore machine, the box labeled combinational control
`logic can be split into two pieces. One pi ece has the control output and only the state
`input, wh ile the other has on ly the next-state output.
`
`(cid:127)
`
`An alternative style of machine is a Mealy machine, named after George Mealy. The
`Mealy machine allows both the input and the current state to be used to determine the
`output. Moore machines have potential implementation advantages in speed and size
`of the control unit. The speed advantages arise because the control outputs, which are
`needed early in the clock cycle, do not depend on the inputs , but only on the current
`state. In Appendix C, when the implementation of this finite state machine is taken
`down to logic gates, the size advantage can be clearly seen.The potential disadvantage
`of a Moore machine is that it may require additional states. For example, in situations
`where there is a one-state difference between two sequences of states, the Mealy
`machine may unify the states by making the outputs depend on the inputs.
`
`Microprogramming:
`Simplifying Control Design
`For the control of our simple MIPS subset, a graphical representation of the
`finite state machine, as in Figure 5.42, is certainly adequate. We can draw such
`a diagram on a single page and translate it into equations (see Appendix C)
`without generating too many errors. Consider instead an implementation of
`the full MIPS instruction set, which contains over 100 instructions (see
`Appendix A). In one implementation, instructions take from 1 clock cycle to
`over 20 clock cycles. Clearly, the control function will be much more complex.
`Or consider an instruction set with more instructions of widely varying
`classes: The control unit could easily require thousands of states with hun(cid:173)
`dreds of different sequences. For example, the Intel 80x86 instruction set has
`many more addressing mode combinations, as well as a much larger set of
`opcodes.
`In such cases, specifying the control unit with a graphical representation
`will be cumbersome, since the finite state machine can contain hundreds to
`thousands of states, and even more arcs! The graphical representation-al(cid:173)
`though useful for a small finite state machine-will not fit on a page, let alone
`be understandable, when it becomes very large. Programmers know this phe(cid:173)
`nomenon quite well: As programs become large, additional structuring tech(cid:173)
`niques (for example, procedures and modules) are needed to keep the
`programs comprehensible. Of course, specifying complex control function s di(cid:173)
`rectly as equations, without making any mistakes, becomes essentially impos(cid:173)
`sible.
`Can we use some of the ideas from programming to help create a method of
`specifying the control that will make it easier to understand as well as to de(cid:173)
`sign? Suppose we think of the set of control signals that must be asserted in a
`state as an instruction to be executed by the datapath. To avoid confusing the
`instructions of the MIPS instruction set with these low-level control instruc(cid:173)
`tions, the latter are called microinstructions. Each microinstruction defines the
`
`INTEL - 1012
`
`

`

`400
`
`Chapter 5 The Processor: Datapath and Control
`
`5.5 Microprogramming: Simplifying Control Design
`
`401
`
`.....
`
`set of data path control signals that must be asserted in a given state. Executing
`a microinstruction has the effect of asserting the control signals specified by the
`microinstruction.
`In addition to defining which control signals must be asserted, we must
`also specify the sequencing-what microinstruction should be executed next?
`In the finite state machine shown in Figure 5.42 on page 396, the next state is
`determined in one of two different ways. Sometimes a single next state follows
`the current state unconditionally. For example, state 1 always follows state 0,
`and the only way to reach state 1 is via state 0. In other cases, the choice of the
`next state depends on the input. This is true in state 1, which has four different
`successor states.
`When we write programs, we also have an analogous situation. Sometimes
`a group of instructions should be executed sequentially, and sometimes we
`need to branch. In programming, the default is sequential execution, while
`branching must be indicated explicitly. In describing the control as a program,
`we also assume that microinstructions written sequentially are executed in se(cid:173)
`quence, while branching must be indicated explicitly. The default sequencing
`mechanism can still be implemented using a structure like the one in
`Figure 5.43 on page 398; however, it is often more efficient to implement the
`default sequential state using a counter. We will see how such an implementa(cid:173)
`tion looks at the end of this section.
`Designing the control as a program that implements the machine instruc(cid:173)
`tions in terms of simpler microinstructions is called microprogramming. The key
`idea is to represent the asserted values on the control lines symbolically, so that
`the microprogram is a representation of the microinstructions, just as assembly
`language is a representation of the machine instructions. In choosing a syntax
`for an assembly language, we usually represent the machine instructions as a
`series of fields (opcode, registers, and offset or immediate field); likewise, we
`will represent a microinstruction syntactically as a sequence of fields whose
`functions are related.
`
`Defining a Microinstruction Format
`The microprogram is a symbolic representation of the control that will be
`translated by a program to control logic. In this way, we can choose how
`many fields a microinstruction should have and what control signals are
`affected by each field . The format of the microinstruction should be chosen so
`as to simplify the representation, making it easier to write and understand the
`microprogram. For example, it is useful to have one field that controls the
`ALU and a set of three fields that determine the two sources for the ALU
`operation as well as the destination of the ALU result. In addition to read(cid:173)
`ability, we would also like the microprogram format to make it difficult or
`impossible to write inconsistent microinstructions. A microinstruction is
`inconsistent if it requires that a given control signal be set to two different val(cid:173)
`ues. We will see an example of how this could happen shortly.
`
`To avoid a format that allows inconsistent microinstructions, we can make
`each field of the microinstruction responsible for specifying a nonoverlapping
`set of control signals. To choose how to make this partition of the control
`signals for this implementation into microinstruction fields, it is useful to re(cid:173)
`examine two previous figures:
`(cid:127) Figure 5.33, on page 383, which shows all the control signals and how
`they affect the data path
`(cid:127) Figure 5.34, on page 384, which shows the function of each data path
`control signal
`Signals that are never asserted simultaneously may share the same field.
`Figure 5.44 shows how the microinstruction can be broken into seven fields
`and defines the general function of each field. The first six fields of the micro(cid:173)
`instruction control the data path, while the Sequencing field (the seventh field)
`specifies how to select the next microinstruction.
`Microinstructions are usually placed in a ROM or a PLA (both described in
`Appendix Band used to implement control in Appendix C), so we can assign
`addresses to the microinstructions. The addresses are usually given out se(cid:173)
`quentially, in the same way that we chose sequential numbers for the states in
`the finite state machine. Three different methods are available to choose the
`next microinstruction to be executed:
`
`--
`
`1. Increment the address of the current microinstruction to obtain the
`address of the next microinstruction. This sequential behavior is indi(cid:173)
`cated in the microprogram by putting Seq in the Sequencing field . Since
`sequential execution of instructions is encountered often, many micro(cid:173)
`programming systems make this the default.
`
`Field name
`
`ALU control
`
`SRCl
`SRC2
`Register control
`Memory
`
`PCWrite control
`Sequencing
`
`Function of field
`
`Specify the operation being done by the ALU during this clock; the result is
`always written in ALUOut.
`Specify the source for the first ALU operand.
`Specify the source for the second ALU operand.
`Specify read or write for the register file , and the source of the value for a write.
`Specify read or write, and the source for the memory. For a read , specify the
`destination register.
`Specify the writing of the PC.
`Specify how to choose the next microinstruction to be executed.
`
`FIGURE 5.44 Each microinstruction cont ains these seven fields. The valu es for each field
`are shown in Figure 5.45.
`
`INTEL - 1012
`
`

`

`402
`
`Chapter 5 The Processor: Datapath and Control
`
`5.5 Microprogramming: Simplifying Control Design
`
`403
`
`Field name
`
`Values for field
`
`Function of field with specific value
`
`Used to specify labels to control microcode sequencing. Labels that end in a 1 or
`2 are used for dispatching with a jump table that is indexed based on the opcode.
`Other labels are used as direct targets in the microinstruction sequencing. Labels
`do not generate control signals directly but are used to define the contents of
`dispatch tables and generate control for the Sequencing field.
`Cause the ALU to add.
`
`Cause the ALU to subtract; this implements the compare for branches.
`Use the instruction 's funct field to determine ALU control .
`Use the PC as the first ALU input.
`Register A is the first ALU input.
`Register B is the second ALU input.
`Use 4 for the second ALU input.
`
`Label
`
`Any string
`
`ALU control
`
`SRC1
`
`SRC2
`
`Register control
`
`Memory
`
`PCWrite control
`
`Sequencing
`
`Add
`Subt
`Fune code
`PC
`A
`B
`4
`Extend
`Extshft
`Read
`
`Wr ite ALU
`
`Write MOR
`
`Read PC
`Read ALU
`Wr ite ALU
`ALU
`"'ALUOut -co nd
`
`Jump address
`Seq
`Fetch
`Dispatch i
`
`2. Branch to the microinstruction that begins execution of the next MIPS
`instruction. We will label this initial microinstruction (corresponding to
`state 0) as Fetch and place the indicator Fetch in the Sequencing field
`to indicate this action.
`
`3