A custom format such as this is slave to the architecture of the hardware and the instruction set it serves. The format must strike a proper compromise between ROM size, ROM-output decoding, circuitry size, and machine execution rate.
Kevit, et al.
8086 design report, 1997
Mapping Control to Hardware
Copyright By PowCoder代写 加微信 powcoder
D.1 Introduction D-3
D.2 Implementing Combinational Control
D.3 Implementing Finite-State Machine
Control D-8
D.4 Implementing the Next-State Function with a
Sequencer D-22
D.5 Translating a Microprogram to Hardware D-28 D.6 ConcludingRemarks D-32
D.7 Exercises D-33
D.1 Introduction
Control typically has two parts: a combinational part that lacks state and a sequential control unit that handles sequencing and the main control in a multicycle design. Combinational control units are often used to handle part of the decode and control process. The ALU control in Chapter 4 is such an example. A single-cycle implementation like that in Chapter 4 can also use a combinational controller, since it does not require multiple states. Section D.2 examines the implementation of these two combinational units from the truth tables of Chapter 4.
Since sequential control units are larger and often more complex, there are a wider variety of techniques for implementing a sequential control unit. The usefulness of these techniques depends on the complexity of the control, characteristics such as the average number of next states for any given state, and the implementation technology.
The most straightforward way to implement a sequential control function is with a block of logic that takes as inputs the current state and the opcode field of the Instruction register and produces as outputs the datapath control signals and the value of the next state. The initial representation may be either a finite-state diagram or a microprogram. In the latter case, each microinstruction represents a state.
D-4 Appendix D Mapping Control to Hardware
In an implementation using a finite-state controller, the next-state function will be computed with logic. Section D.3 constructs such an implementation both for a ROM and a PLA.
An alternative method of implementation computes the next-state function by using a counter that increments the current state to determine the next state. When the next state doesn’t follow sequentially, other logic is used to determine the state. Section D.4 explores this type of implementation and shows how it can be used to implement finite-state control.
In Section D.5, we show how a microprogram representation of sequential control is translated to control logic.
Implementing Combinational Control Units
In this section, we show how the ALU control unit and main control unit for the single clock design are mapped down to the gate level. With modern computer- aided design (CAD) systems, this process is completely mechanical. The examples illustrate how a CAD system takes advantage of the structure of the control function, including the presence of don’t-care terms.
Mapping the ALU Control Function to Gates
Figure D.2.1 shows the truth table for the ALU control function that was developed in Section 4.4. A logic block that implements this ALU control function will have four distinct outputs (called Operation3, Operation2, Operation1, and Operation0), each corresponding to one of the four bits of the ALU control in the last column of Figure D.2.1. The logic function for each output is constructed by combining all the truth table entries that set that particular output. For example, the low-order bit of the ALU control (Operation0) is set by the last two entries of the truth table in Figure D.2.1. Thus, the truth table for Operation0 will have these two entries.
Figure D.2.2 shows the truth tables for each of the four ALU control bits. We have taken advantage of the common structure in each truth table to incorporate additional don’t cares. For example, the five lines in the truth table of Figure D.2.1 that set Operation1 are reduced to just two entries in Figure D.2.2. A logic minimization program will use the don’t-care terms to reduce the number of gates and the number of inputs to each gate in a logic gate realization of these truth tables.
A confusing aspect of Figure D.2.2 is that there is no logic function for Opera- tion3. That is because this control line is only used for the NOR operation, which is not needed for the MIPS subset in Figure 4.12.
From the simplified truth table in Figure D.2.2, we can generate the logic shown in Figure D.2.3, which we call the ALU control block. This process is straightforward
D.2 Implementing Combinational Control Units D-5
Funct field
FIGURE D.2.1 The truth table for the 4 ALU control bits (called Operation) as a function of the ALUOp and function code field. This table is the same as that shown in Figure 4.13.
Function code fields
a. The truth table for Operation2 = 1 (this table corresponds to the second to left bit of the Operation field in Figure D.2.1)
Function code fields
b. The truth table for Operation1 = 1
Function code fields
c. The truth table for Operation0 = 1
FIGURE D.2.2 The truth tables for three ALU control lines. Only the entries for which the output is 1 are shown. The bits in each field are numbered from right to left starting with 0; thus F5 is the most significant bit of the function field, and F0 is the least significant bit. Similarly, the names of the signals corresponding to the 4-bit operation code supplied to the ALU are Operation3, Operation2, Operation1, and Operation0 (with the last being the least significant bit). Thus the truth table above shows the input combinations for which the ALU control should be 0010, 0001, 0110, or 0111 (the other combinations are not used). The ALUOp bits are named ALUOp1 and ALUOp0. The three output values depend on the 2-bit ALUOp field and, when that field is equal to 10, the 6-bit function code in the instruction. Accordingly, when the ALUOp field is not equal to 10, we don’t care about the function code value (it is represented by an X). There is no truth table for when Operation31 because it is always set to 0 in Figure D.2.1. See Appendix B for more background on don’t cares.
D-6 Appendix D Mapping Control to Hardware
ALU control block
Operation3
Operation2 Operation1 Operation0
FIGURE D.2.3 The ALU control block generates the four ALU control bits, based on the function code and ALUOp bits. This logic is generated directly from the truth table in Figure D.2.2. Only four of the six bits in the function code are actually needed as inputs, since the upper two bits are always don’t cares. Let’s examine how this logic relates to the truth table of Figure D.2.2. Consider the Operation2 output, which is generated by two lines in the truth table for Operation2. The second line is the AND of two terms (F1 1 and ALUOp1 1); the top two-input AND gate corresponds to this term. The other term that causes Operation2 to be asserted is simply ALUOp0. These two terms are combined with an OR gate whose output is Operation2. The outputs Operation0 and Operation1 are derived in similar fashion from the truth table. Since Operation3 is always 0, we connect a signal and its complement as inputs to an AND gate to generate 0.
and can be done with a CAD program. An example of how the logic gates can be derived from the truth tables is given in the legend to Figure D.2.3.
This ALU control logic is simple because there are only three outputs, and only a few of the possible input combinations need to be recognized. If a large number of possible ALU function codes had to be transformed into ALU control signals, this simple method would not be efficient. Instead, you could use a decoder, a memory, or a structured array of logic gates. These techniques are described in Appendix B, and we will see examples when we examine the implementation of the multicycle controller in Section D.3.
Elaboration: In general, a logic equation and truth table representation of a logic function are equivalent. (We discuss this in further detail in Appendix B. However, when a truth table only specifies the entries that result in nonzero outputs, it may not completely describe the logic function. A full truth table completely indicates all don’t-care entries. For example, the encoding 11 for ALUOp always generates a don’t care in the output. Thus a complete truth table would have XXX in the output portion for all entries with 11 in the ALUOp field. These don’t-care entries allow us to replace the ALUOp field 10 and
D.2 Implementing Combinational Control Units D-7
01 with 1X and X1, respectively. Incorporating the don’t-care terms and minimizing the logic is both complex and error-prone and, thus, is better left to a program.
Mapping the Main Control Function to Gates
Implementing the main control function with an unstructured collection of gates, as we did for the ALU control, is reasonable because the control function is neither complex nor large, as we can see from the truth table shown in Figure D.2.4. However, if most of the 64 possible opcodes were used and there were many more control lines, the number of gates would be much larger and each gate could have many more inputs.
Since any function can be computed in two levels of logic, another way to implement a logic function is with a structured two-level logic array. Figure D.2.5 shows such an implementation. It uses an array of AND gates followed by an array of OR gates. This structure is called a programmable logic array (PLA). A PLA is one of the most common ways to implement a control function. We will return to the topic of using structured logic elements to implement control when we implement the finite-state controller in the next section.
Signal name
FIGURE D.2.4 The control function for the simple one-clock implementation is completely specified by this truth table. This table is the same as that shown in Figure 4.22.
D-8 Appendix D
Mapping Control to Hardware
Op5 Op4 Op3 Op2 Op1 Op0
ALU Reg RegWrite MemRead MemWrite Branch ALUOp1 ALUOp0
FIGURE D.2.5
truth table in Figure D.2.4. The structure, called a programmable logic array (PLA), uses an array of AND gates followed by an array of OR gates. The inputs to the AND gates are the function inputs and their inverses (bubbles indicate inversion of a signal). The inputs to the OR gates are the outputs of the AND gates (or, as a degenerate case, the function inputs and inverses). The output of the OR gates is the function outputs.
Implementing Finite-State Machine Control
To implement the control as a finite-state machine, we must first assign a number to each of the 10 states; any state could use any number, but we will use the sequential numbering for simplicity. Figure D.3.1 shows the finite-state diagram. With 10 states, we will need 4 bits to encode the state number, and we call these state bits S3, S2, S1, and S0. The current-state number will be stored in a state register, as shown in Figure D.3.2. If the states are assigned sequentially, state i is encoded using the
The structured implementation of the control function as described by the
D.3 Implementing Finite-State Machine Control
Instruction fetch
Instruction decode/ register fetch
MemRead ALUSrcA = 0 IorD = 0 IRWrite ALUSrcB = 01 ALUOp = 00 PCWrite PCSource = 00
ALUSrcA = 0 ALUSrcB = 11 ALUOp = 00
Jump completion
PCWrite PCSource = 10
Memory address computation
Branch completion
ALUSrcA = 1 ALUSrcB = 10 ALUOp = 00
ALUSrcA = 1 ALUSrcB = 00 ALUOp = 10
ALUSrcA = 1 ALUSrcB = 00 ALUOp = 01 PCWriteCond PCSource = 01
MemRead IorD = 1
Write-back step
MemWrite IorD = 1
R-type completion
RegDst = 1 RegWrite MemtoReg = 0
RegDst = 0 RegWrite MemtoReg = 1
FIGURE D.3.1 The finite-state diagram for multicycle control.
(Op = ‘LW’)
(Op = ‘J’)
(Op = R-type)
(Op = ‘BEQ’)
(Op = ‘LW’) or (Op = ‘SW’)
(Op = ‘SW’)
D-10 Appendix D
Mapping Control to Hardware
PCWrite PCWrite D MemRead MemWrite IRWrite MemtoReg PCSource ALUOp ALUSrcB ALUSrcA RegWrite RegDst
NS2 NS1 NS0
Control logic
Instruction register opcode field
State register
FIGURE D.3.2
to hold the state. The state register is written at the active clock edge and is stable during the clock cycle
state bits as the binary number i. For example, state 6 is encoded as 0110two or S3 0, S2 1, S1 1, S0 0, which can also be written as
S3 · S2 · S1 · S0
The control unit has outputs that specify the next state. These are written into the state register on the clock edge and become the new state at the beginning of the next clock cycle following the active clock edge. We name these outputs NS3, NS2, NS1, and NS0. Once we have determined the number of inputs, states, and outputs, we know what the basic outline of the control unit will look like, as we show in Figure D.3.2.
The control unit for MIPS will consist of some control logic and a register
Op5 Op4 Op3 Op2 Op1 Op0
S3 S2 S1 S0
D.3 Implementing Finite-State Machine Control D-11
The block labeled “control logic” in Figure D.3.2 is combinational logic. We can think of it as a big table giving the value of the outputs in terms of the inputs. The logic in this block implements the two different parts of the finite-state machine. One part is the logic that determines the setting of the datapath control outputs, which depend only on the state bits. The other part of the control logic implements the next-state function; these equations determine the values of the next-state bits based on the current-state bits and the other inputs (the 6-bit opcode).
Figure D.3.3 shows the logic equations: the top portion shows the outputs, and the bottom portion shows the next-state function. The values in this table were
Output Current states Op
PCWrite state0 + state9
PCWriteCond state8
IorD state3 + state5
MemRead state0 + state3
MemWrite state5
IRWrite state0
MemtoReg state4
PCSource1 state9
PCSource0 state8
ALUOp1 state6
ALUOp0 state8
ALUSrcB1 state1 +state2
ALUSrcB0 state0 + state1
ALUSrcA state2 + state6 + state8
RegWrite state4 + state7
RegDst state7
NextState0 state4 + state5 + state7 + state8 + state9
NextState1 state0
NextState2 state1 (Op = ‘lw’) + (Op = ‘sw’)
NextState3 state2 (Op = ‘lw’)
NextState4 state3
NextState5 state2 (Op = ‘sw’)
NextState6 state1 (Op = ‘R-type’)
NextState7 state6
NextState8 state1 (Op = ‘beq’)
NextState9 state1 (Op = ‘jmp’)
FIGURE D.3.3 The logic equations for the control unit shown in a shorthand form. Remember that “” stands for OR in logic equations. The state inputs and NextState outputs must be expanded by using the state encoding. Any blank entry is a don’t care.
D-12 Appendix D Mapping Control to Hardware
EXAMPLE ANSWER
determined from the state diagram in Figure D.3.1. Whenever a control line is active in a state, that state is entered in the second column of the table. Likewise, the next-state entries are made whenever one state is a successor to another.
In Figure D.3.3, we use the abbreviation stateN to stand for current state N. Thus, stateN is replaced by the term that encodes the state number N. We use NextStateN to stand for the setting of the next-state outputs to N. This output is implemented using the next-state outputs (NS). When NextStateN is active, the bits NS[3–0] are set corresponding to the binary version of the value N. Of course, since a given next-state bit is activated in multiple next states, the equation for each state bit will be the OR of the terms that activate that signal. Likewise, when we use a term such as (Op ‘lw’), this corresponds to an AND of the opcode inputs that specifies the encoding of the opcode lw in 6 bits, just as we did for the simple control unit in the previous section of this chapter. Translating the entries in Figure D.3.3 into logic equations for the outputs is straightforward.
Logic Equations for Next-State Outputs
Give the logic equation for the low-order next-state bit, NS0.
The next-state bit NS0 should be active whenever the next state has NS0 1 in the state encoding. This is true for NextState1, NextState3, NextState5, NextState7, and NextState9. The entries for these states in Figure D.3.3 supply the conditions when these next-state values should be active. The equation for each of these next states is given below. The first equation states that the next state is 1 if the current state is 0; the current state is 0 if each of the state input bits is 0, which is what the rightmost product term indicates.
NextState1 State0 S3 · S2 · S1 · S0 NextState3 State2 · (Op[5-0]1w)
S3 · S2 · S1 · S0 · Op5 · Op4 · Op3 · Op2 · Op1 · Op0
D.3 Implementing Finite-State Machine Control D-13
NextState5 State2 · (Op[5-0]sw)
S3 · S2 · S1 · S0 · Op5 · Op4 · Op3 · Op2 · Op1 · Op0
NextState7 State6 S3 · S2 · S1 · S0 NextState9 State1 · (Op[5-0]jmp)
S3 · S2 · S1 · S0 · Op5 · Op4 · Op3 · Op2 · Op1 · Op0 NS0 is the logical sum of all these terms.
As we have seen, the control function can be expressed as a logic equation for each output. This set of logic equations can be implemented in two ways: corresponding to a complete truth table, or corresponding to a two-level logic structure that allows a sparse encoding of the truth table. Before we look at these implementations, let’s look at the truth table for the complete control function.
It is simplest if we break the control function defined in Figure D.3.3 into two parts: the next-state outputs, which may depend on all the inputs, and the control signal outputs, which depend only on the current-state bits. Figure D.3.4 shows the truth tables for all the datapath control signals. Because these signals actually depend only on the state bits (and not the opcode), each of the entries in a table in Figure D.3.4 actually represents 64 ( 26) entries, with the 6 bits named Op having all possible values; that is, the Op bits are don’t-care bits in determining the data path control outputs. Figure D.3.5 shows the truth table for the next-state bits NS[3–0], which depend on the state input bits and the instruction bits, which supply the opcode.
Elaboration: There are many opportunities to simplify the control function by observing similarities among two or more control signals and by using the semantics of the implementation. For example, the signals PCWriteCond, PCSource0, and ALUOp0 are all asserted in exactly one state, state 8. These three control signals can be replaced by a single signal.
D-14 Appendix D Mapping Control to Hardware
a. Truth table for PCWrite b. Truth table for PCWriteCond
c. Truth table for IorD
d. Truth table for MemRead
e. Truth table for MemWrite
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com