Computer Organization and Design 4e Appendices C-E (from CD)

C A

P

P

E

N

D

I

I always loved that word, Boolean. Claude Shannon IEEE Spectrum, April 1992 (Shannon’s master’s thesis showed that the algebra invented by George Boole in the 1800s could represent the workings of electrical switches.)

X

The Basics of Logic Design C.1 C.2 C.3 C.4 C.5 C.6 C.7

Introduction C-3 Gates, Truth Tables, and Logic Equations C-4 Combinational Logic C-9 Using a Hardware Description Language C-20 Constructing a Basic Arithmetic Logic Unit C-26 Faster Addition: Carry Lookahead C-38 Clocks C-48

C.8 C.9 C.10 C.11 C.12 C.13 C.14

Memory Elements: Flip-Flops, Latches, and Registers C-50 Memory Elements: SRAMs and DRAMs C-58 Finite-State Machines C-67 Timing Methodologies C-72 Field Programmable Devices C-78 Concluding Remarks C-79 Exercises C-80

C.1

Introduction

This appendix provides a brief discussion of the basics of logic design. It does not replace a course in logic design, nor will it enable you to design significant working logic systems. If you have little or no exposure to logic design, however, this appendix will provide sufficient background to understand all the material in this book. In addition, if you are looking to understand some of the motivation behind how computers are implemented, this material will serve as a useful introduction. If your curiosity is aroused but not sated by this appendix, the references at the end provide several additional sources of information. Section C.2 introduces the basic building blocks of logic, namely, gates. Section C.3 uses these building blocks to construct simple combinational logic systems, which contain no memory. If you have had some exposure to logic or digital systems, you will probably be familiar with the material in these first two sections. Section C.5 shows how to use the concepts of Sections C.2 and C.3 to design an ALU for the MIPS processor. Section C.6 shows how to make a fast adder,

C-4

Appendix C The Basics of Logic Design

and may be safely skipped if you are not interested in this topic. Section C.7 is a short introduction to the topic of clocking, which is necessary to discuss how memory elements work. Section C.8 introduces memory elements, and Section C.9 extends it to focus on random access memories; it describes both the characteristics that are important to understanding how they are used in Chapter 4, and the background that motivates many of the aspects of memory hierarchy design in Chapter 5. Section C.10 describes the design and use of finite-state machines, which are sequential logic blocks. If you intend to read Appendix D, you should thoroughly understand the material in Sections C.2 through C.10. If you intend to read only the material on control in Chapter 4, you can skim the appendices; however, you should have some familiarity with all the material except Section C.11. Section C.11 is intended for those who want a deeper understanding of clocking methodologies and timing. It explains the basics of how edge-triggered clocking works, introduces another clocking scheme, and briefly describes the problem of synchronizing asynchronous inputs. Throughout this appendix, where it is appropriate, we also include segments to demonstrate how logic can be represented in Verilog, which we introduce in Section C.4. A more extensive and complete Verilog tutorial appears elsewhere on the CD.

C.2

asserted signal A signal that is (logically) true, or 1. deasserted signal A signal that is (logically) false, or 0.

Gates, Truth Tables, and Logic Equations

The electronics inside a modern computer are digital. Digital electronics operate with only two voltage levels of interest: a high voltage and a low voltage. All other voltage values are temporary and occur while transitioning between the values. (As we discuss later in this section, a possible pitfall in digital design is sampling a signal when it not clearly either high or low.) The fact that computers are digital is also a key reason they use binary numbers, since a binary system matches the underlying abstraction inherent in the electronics. In various logic families, the values and relationships between the two voltage values differ. Thus, rather than refer to the voltage levels, we talk about signals that are (logically) true, or 1, or are asserted; or signals that are (logically) false, or 0, or are deasserted. The values 0 and 1 are called complements or inverses of one another. Logic blocks are categorized as one of two types, depending on whether they contain memory. Blocks without memory are called combinational; the output of a combinational block depends only on the current input. In blocks with memory, the outputs can depend on both the inputs and the value stored in memory, which is called the state of the logic block. In this section and the next, we will focus

C.2

C-5

Gates, Truth Tables, and Logic Equations

only on combinational logic. After introducing different memory elements in Section C.8, we will describe how sequential logic, which is logic including state, is designed.

Truth Tables Because a combinational logic block contains no memory, it can be completely specified by defining the values of the outputs for each possible set of input values. Such a description is normally given as a truth table. For a logic block with n inputs, there are 2n entries in the truth table, since there are that many possible combinations of input values. Each entry specifies the value of all the outputs for that particular input combination.

combinational logic A logic system whose blocks do not contain memory and hence compute the same output given the same input.

sequential logic A group of logic elements that contain memory and hence whose value depends on the inputs as well as the current contents of the memory.

Truth Tables

Consider a logic function with three inputs, A, B, and C, and three outputs, D, E, and F. The function is defined as follows: D is true if at least one input is true, E is true if exactly two inputs are true, and F is true only if all three inputs are true. Show the truth table for this function. The truth table will contain 23 = 8 entries. Here it is:

A

Inputs B

C

0

0

0

0

0

EXAMPLE

ANSWER

D

Outputs E

F

0

0

0

0

1

1

0

0

1

0

1

0

0

0

1

1

1

1

0

1

0

0

1

0

0

1

0

1

1

1

0

1

1

0

1

1

0

1

1

1

1

0

1

Truth tables can completely describe any combinational logic function; however, they grow in size quickly and may not be easy to understand. Sometimes we want to construct a logic function that will be 0 for many input combinations, and we use a shorthand of specifying only the truth table entries for the nonzero outputs. This approach is used in Chapter 4 and Appendix D.

C-6

Appendix C The Basics of Logic Design

Boolean Algebra Another approach is to express the logic function with logic equations. This is done with the use of Boolean algebra (named after Boole, a 19th-century mathematician). In Boolean algebra, all the variables have the values 0 or 1 and, in typical formulations, there are three operators: ■

The OR operator is written as +, as in A + B. The result of an OR operator is 1 if either of the variables is 1. The OR operation is also called a logical sum, since its result is 1 if either operand is 1.

■

The AND operator is written as · , as in A · B. The result of an AND operator is 1 only if both inputs are 1. The AND operator is also called logical product, since its result is 1 only if both operands are 1.

■

The unary operator NOT is written as A. The result of a NOT operator is 1 only if the input is 0. Applying the operator NOT to a logical value results in an inversion or negation of the value (i.e., if the input is 0 the output is 1, and vice versa).

__

There are several laws of Boolean algebra that are helpful in manipulating logic equations. ■

Identity law: A + 0 = A and A · 1 = A.

■

Zero and One laws: A + 1 = 1 and A · 0 = 0.

■

Inverse laws: A + A = 1 and A · A = 1.

■

Commutative laws: A + B = B + A and A · B = B · A.

■

Associative laws: A + (B + C) = (A + B) + C and A · (B · C) = (A · B) · C.

__

■

__

Distributive laws: A · (B + C) = (A · B) + (A · C) and A + (B · C) = (A + B) · (A + C).

In addition, there are two other useful theorems, called DeMorgan’s laws, that are discussed in more depth in the exercises. Any set of logic functions can be written as a series of equations with an output on the left-hand side of each equation and a formula consisting of variables and the three operators above on the right-hand side.

C.2

C-7

Gates, Truth Tables, and Logic Equations

Logic Equations

Show the logic equations for the logic functions, D, E, and F, described in the previous example. Here’s the equation for D:

ANSWER

D=A+B+C F is equally simple: F=A·B·C E is a little tricky. Think of it in two parts: what must be true for E to be true (two of the three inputs must be true), and what cannot be true (all three cannot be true). Thus we can write E as _______

E = ((A · B) + (A · C) + (B · C)) · (A · B · C) We can also derive E by realizing that E is true only if exactly two of the inputs are true. Then we can write E as an OR of the three possible terms that have two true inputs and one false input: __

__

EXAMPLE

__

E = (A · B · C) + (A · C · B) + (B · C · A) Proving that these two expressions are equivalent is explored in the exercises. In Verilog, we describe combinational logic whenever possible using the assign statement, which is described beginning on page C-23. We can write a definition for E using the Verilog exclusive-OR operator as assign E = (A ^ B ^ C) * (A + B + C) * (A * B * C), which is yet another way to describe this function. D and F have even simpler representations, which are just like the corresponding C code: D = A | B | C and F = A & B & C.

C-8

Appendix C The Basics of Logic Design

Gates gate A device that implements basic logic functions, such as AND or OR.

NOR gate An inverted OR gate.

NAND gate An inverted AND gate.

Check Yourself

Logic blocks are built from gates that implement basic logic functions. For example, an AND gate implements the AND function, and an OR gate implements the OR function. Since both AND and OR are commutative and associative, an AND or an OR gate can have multiple inputs, with the output equal to the AND or OR of all the inputs. The logical function NOT is implemented with an inverter that always has a single input. The standard representation of these three logic building blocks is shown in Figure C.2.1. Rather than draw inverters explicitly, a common practice is to add “bubbles” to the inputs or outputs of a gate to cause the logic value on that input line or output line to_____ __be inverted. For example, Figure C.2.2 shows the logic diagram for the function A + B, using explicit inverters on the left and bubbled inputs and outputs on the right. Any logical function can be constructed using AND gates, OR gates, and inversion; several of the exercises give you the opportunity to try implementing some common logic functions with gates. In the next section, we’ll see how an implementation of any logic function can be constructed using this knowledge. In fact, all logic functions can be constructed with only a single gate type, if that gate is inverting. The two common inverting gates are called NOR and NAND and correspond to inverted OR and AND gates, respectively. NOR and NAND gates are called universal, since any logic function can be built using this one gate type. The exercises explore this concept further. Are the following two logical expressions equivalent? If not, find a setting of the variables to show they are not: __ __ __ ■ (A · B · C) + (A · C · B) + (B · C · A) __

■

__

B · (A · C + C · A)

FIGURE C.2.1 Standard drawing for an AND gate, OR gate, and an inverter, shown from left to right. The signals to the left of each symbol are the inputs, while the output appears on the right. The AND and OR gates both have two inputs. Inverters have a single input.

A B

A B

_______ __ FIGURE C.2.2 Logic gate implementation of A + B using explicit inverts on the __ left and bubbled inputs and outputs on the right. This logic function can be simplified to A · B or in Verilog, A & ~ B.

C.3

C.3

C-9

Combinational Logic

Combinational Logic

In this section, we look at a couple of larger logic building blocks that we use heavily, and we discuss the design of structured logic that can be automatically implemented from a logic equation or truth table by a translation program. Last, we discuss the notion of an array of logic blocks.

Decoders One logic block that we will use in building larger components is a decoder. The most common type of decoder has an n-bit input and 2n outputs, where only one output is asserted for each input combination. This decoder translates the n-bit input into a signal that corresponds to the binary value of the n-bit input. The outputs are thus usually numbered, say, Out0, Out1, . . . , Out2n − 1. If the value of the input is i, then Outi will be true and all other outputs will be false. Figure C.3.1 shows a 3-bit decoder and the truth table. This decoder is called a 3-to-8 decoder since there are 3 inputs and 8 (23) outputs. There is also a logic element called an encoder that performs the inverse function of a decoder, taking 2n inputs and producing an n-bit output.

Out0 Out1

3

Decoder

Inputs 11

10

Out7

Out6

Out5

that has an n-bit input and 2n outputs, where only one output is asserted for each input combination.

Outputs Out4 Out3

Out2

Out1

Out0

0

0

0

0

0

0

0

0

0

0

1

Out2

0

0

1

0

0

0

0

0

0

1

0

Out3

0

1

0

0

0

0

0

0

1

0

0

0

1

1

0

0

0

0

1

0

0

0

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

0

0

0

0

0

Out6

1

1

0

0

1

0

0

0

0

0

0

Out7

1

1

1

1

0

0

0

0

0

0

0

Out4 Out5

a. A 3-bit decoder

12

decoder A logic block

b. The truth table for a 3-bit decoder

FIGURE C.3.1 A 3-bit decoder has 3 inputs, called 12, 11, and 10, and 23 = 8 outputs, called Out0 to Out7. Only the output corresponding to the binary value of the input is true, as shown in the truth table. The label 3 on the input to the decoder says that the input signal is 3 bits wide.

C-10

Appendix C The Basics of Logic Design

A A

B

0 M u x 1

S

C

C B S

FIGURE C.3.2 A two-input multiplexor on the left and its implementation with gates on the right. The multiplexor has two data inputs (A and B), which are labeled 0 and 1, and one selector input (S), as well as an output C. Implementing multiplexors in Verilog requires a little more work, especially when they are wider than two inputs. We show how to do this beginning on page C-23.

Multiplexors

selector value Also called control value. The control signal that is used to select one of the input values of a multiplexor as the output of the multiplexor.

One basic logic function that we use quite often in Chapter 4 is the multiplexor. A multiplexor might more properly be called a selector, since its output is one of the inputs that is selected by a control. Consider the two-input multiplexor. The left side of Figure C.3.2 shows this multiplexor has three inputs: two data values and a selector (or control) value. The selector value determines which of the inputs becomes the output. We can represent the logic function computed by a two-input multiplexor, shown in gate form on the right side of Figure C.3.2, as _ C = (A · S) + (B · S). Multiplexors can be created with an arbitrary number of data inputs. When there are only two inputs, the selector is a single signal that selects one of the inputs if it is true (1) and the other if it is false (0). If there are n data inputs, there will need to be log2n selector inputs. In this case, the multiplexor basically consists of three parts: 1. A decoder that generates n signals, each indicating a different input value 2. An array of n AND gates, each combining one of the inputs with a signal from the decoder 3. A single large OR gate that incorporates the outputs of the AND gates To associate the inputs with selector values, we often label the data inputs numerically (i.e., 0, 1, 2, 3, . . . , n − 1) and interpret the data selector inputs as a binary number. Sometimes, we make use of a multiplexor with undecoded selector signals. Multiplexors are easily represented combinationally in Verilog by using if expressions. For larger multiplexors, case statements are more convenient, but care must be taken to synthesize combinational logic.

C.3

Combinational Logic

C-11

Two-Level Logic and PLAs As pointed out in the previous section, any logic function can be implemented with only AND, OR, and NOT functions. In fact, a much stronger result is true. Any logic function can be written in a canonical form, where every input is either a true or complemented variable and there are only two levels of gates—one being AND and the other OR—with a possible inversion on the final output. Such a representation is called a two-level representation, and there are two forms, called sum of products and product of sums. A sum-of-products representation is a logical sum (OR) of products (terms using the AND operator); a product of sums is just the opposite. In our earlier example, we had two equations for the output E: ________

E = ((A · B) + (A · C) + (B · C)) · (A · B · C) and __

__

__

E = (A · B · C) + (A · C · B) + (B · C · A) This second equation is in a sum-of-products form: it has two levels of logic and the only inversions are on individual variables. The first equation has three levels of logic. Elaboration: We can also write E as a product of sums: _______________________________ __ __ __ __ __

E = (A + B + C) · (A + C + B) · (B + C + A) To derive this form, you need to use DeMorgan’s theorems, which are discussed in the exercises.

In this text, we use the sum-of-products form. It is easy to see that any logic function can be represented as a sum of products by constructing such a representation from the truth table for the function. Each truth table entry for which the function is true corresponds to a product term. The product term consists of a logical product of all the inputs or the complements of the inputs, depending on whether the entry in the truth table has a 0 or 1 corresponding to this variable. The logic function is the logical sum of the product terms where the function is true. This is more easily seen with an example.

sum of products A form of logical representation that employs a logical sum (OR) of products (terms joined using the AND operator).

C-12

Appendix C The Basics of Logic Design

Sum of Products

EXAMPLE

Show the sum-of-products representation for the following truth table for D. Inputs B

A 0 0 0 0 1 1 1 1

ANSWER

0 0 1 1 0 0 1 1

C

Output D

0 1 0 1 0 1 0 1

0 1 1 0 1 0 0 1

There are four product terms, since the function is true (1) for four different input combinations. These are: __ __

A·B·C __

programmable logic array (PLA) A structured-logic element composed of a set of inputs and corresponding input complements and two stages of logic: the first generating product terms of the inputs and input complements, and the second generating sum terms of the product terms. Hence, PLAs implement logic functions as a sum of products.

minterms Also called product terms. A set of logic inputs joined by conjunction (AND operations); the product terms form the first logic stage of the programmable logic array (PLA).

__

A·B·C __

__

A·B·C A·B·C Thus, we can write the function for D as the sum of these terms: __ __

__

__

__

__

D = (A · B · C) + (A · B · C) + (A · B · C) + (A · B · C) Note that only those truth table entries for which the function is true generate terms in the equation. We can use this relationship between a truth table and a two-level representation to generate a gate-level implementation of any set of logic functions. A set of logic functions corresponds to a truth table with multiple output columns, as we saw in the example on page C-5. Each output column represents a different logic function, which may be directly constructed from the truth table. The sum-of-products representation corresponds to a common structuredlogic implementation called a programmable logic array (PLA). A PLA has a set of inputs and corresponding input complements (which can be implemented with a set of inverters), and two stages of logic. The first stage is an array of AND gates that form a set of product terms (sometimes called minterms); each product term can consist of any of the inputs or their complements. The second stage is an array of OR gates, each of which forms a logical sum of any number of the product terms. Figure C.3.3 shows the basic form of a PLA.

C.3

Inputs

Combinational Logic

C-13

AND gates

Product terms

OR gates

Outputs

FIGURE C.3.3 The basic form of a PLA consists of an array of AND gates followed by an array of OR gates. Each entry in the AND gate array is a product term consisting of any number of inputs or inverted inputs. Each entry in the OR gate array is a sum term consisting of any number of these product terms.

A PLA can directly implement the truth table of a set of logic functions with multiple inputs and outputs. Since each entry where the output is true requires a product term, there will be a corresponding row in the PLA. Each output corresponds to a potential row of OR gates in the second stage. The number of OR gates corresponds to the number of truth table entries for which the output is true. The total size of a PLA, such as that shown in Figure C.3.3, is equal to the sum of the size of the AND gate array (called the AND plane) and the size of the OR gate array (called the OR plane). Looking at Figure C.3.3, we can see that the size of the AND gate array is equal to the number of inputs times the number of different product terms, and the size of the OR gate array is the number of outputs times the number of product terms. A PLA has two characteristics that help make it an efficient way to implement a set of logic functions. First, only the truth table entries that produce a true value for at least one output have any logic gates associated with them. Second, each different product term will have only one entry in the PLA, even if the product term is used in multiple outputs. Let’s look at an example.

PLAs

Consider the set of logic functions defined in the example on page C-5. Show a PLA implementation of this example for D, E, and F.

EXAMPLE

C-14

ANSWER

Appendix C The Basics of Logic Design

Here is the truth table we constructed earlier:

A

Inputs B

C

D

Outputs E

F

0

0

0

0

0

0

0

0

1

1

0

0

0

1

0

1

0

0

0

1

1

1

1

0

1

0

0

1

0

0

1

0

1

1

1

0

1

1

0

1

1

0

1

1

1

1

0

1

Since there are seven unique product terms with at least one true value in the output section, there will be seven columns in the AND plane. The number of rows in the AND plane is three (since there are three inputs), and there are also three rows in the OR plane (since there are three outputs). Figure C.3.4 shows the resulting PLA, with the product terms corresponding to the truth table entries from top to bottom.

read-only memory (ROM) A memory whose contents are designated at creation time, after which the contents can only be read. ROM is used as structured logic to implement a set of logic functions by using the terms in the logic functions as address inputs and the outputs as bits in each word of the memory.

programmable ROM (PROM) A form of read-only memory that can be programmed when a designer knows its contents.

Rather than drawing all the gates, as we do in Figure C.3.4, designers often show just the position of AND gates and OR gates. Dots are used on the intersection of a product term signal line and an input line or an output line when a corresponding AND gate or OR gate is required. Figure C.3.5 shows how the PLA of Figure C.3.4 would look when drawn in this way. The contents of a PLA are fixed when the PLA is created, although there are also forms of PLA-like structures, called PALs, that can be programmed electronically when a designer is ready to use them.

ROMs Another form of structured logic that can be used to implement a set of logic functions is a read-only memory (ROM). A ROM is called a memory because it has a set of locations that can be read; however, the contents of these locations are fixed, usually at the time the ROM is manufactured. There are also programmable ROMs (PROMs) that can be programmed electronically, when a designer knows their contents. There are also erasable PROMs; these devices require a slow erasure process using ultraviolet light, and thus are used as read-only memories, except during the design and debugging process. A ROM has a set of input address lines and a set of outputs. The number of addressable entries in the ROM determines the number of address lines: if the

C.3

Combinational Logic

ROM contains 2m addressable entries, called the height, then there are m input lines. The number of bits in each addressable entry is equal to the number of output bits and is sometimes called the width of the ROM. The total number of bits in the ROM is equal to the height times the width. The height and width are sometimes collectively referred to as the shape of the ROM.

Inputs A B C

Outputs D

E F FIGURE C.3.4

The PLA for implementing the logic function described in the example.

A ROM can encode a collection of logic functions directly from the truth table. For example, if there are n functions with m inputs, we need a ROM with m address lines (and 2m entries), with each entry being n bits wide. The entries in the input portion of the truth table represent the addresses of the entries in the ROM, while the contents of the output portion of the truth table constitute the contents of the ROM. If the truth table is organized so that the sequence of entries in the input portion constitutes a sequence of binary numbers (as have all the truth tables we have shown so far), then the output portion gives the ROM contents in order as well. In the example starting on page C-13, there were three inputs and three outputs. This leads to a ROM with 23 = 8 entries, each 3 bits wide. The contents of those entries in increasing order by address are directly given by the output portion of the truth table that appears on page C-14. ROMs and PLAs are closely related. A ROM is fully decoded: it contains a full output word for every possible input combination. A PLA is only partially decoded. This means that a ROM will always contain more entries. For the earlier truth table on page C-14, the ROM contains entries for all eight possible inputs, whereas the PLA contains only the seven active product terms. As the number of inputs grows,

C-15

C-16

Appendix C The Basics of Logic Design

Inputs A

B

AND plane

C

Outputs D OR plane

E F

FIGURE C.3.5 A PLA drawn using dots to indicate the components of the product terms and sum terms in the array. Rather than use inverters on the gates, usually all the inputs are run the width of the AND plane in both true and complement forms. A dot in the AND plane indicates that the input, or its inverse, occurs in the product term. A dot in the OR plane indicates that the corresponding product term appears in the corresponding output.

the number of entries in the ROM grows exponentially. In contrast, for most real logic functions, the number of product terms grows much more slowly (see the examples in Appendix D). This difference makes PLAs generally more efficient for implementing combinational logic functions. ROMs have the advantage of being able to implement any logic function with the matching number of inputs and outputs. This advantage makes it easier to change the ROM contents if the logic function changes, since the size of the ROM need not change. In addition to ROMs and PLAs, modern logic synthesis systems will also translate small blocks of combinational logic into a collection of gates that can be placed and wired automatically. Although some small collections of gates are usually not area efficient, for small logic functions they have less overhead than the rigid structure of a ROM and PLA and so are preferred. For designing logic outside of a custom or semicustom integrated circuit, a common choice is a field programming device; we describe these devices in Section C.12.

C.3

Combinational Logic

C-17

Don’t Cares Often in implementing some combinational logic, there are situations where we do not care what the value of some output is, either because another output is true or because a subset of the input combinations determines the values of the outputs. Such situations are referred to as don’t cares. Don’t cares are important because they make it easier to optimize the implementation of a logic function. There are two types of don’t cares: output don’t cares and input don’t cares, both of which can be represented in a truth table. Output don’t cares arise when we don’t care about the value of an output for some input combination. They appear as Xs in the output portion of a truth table. When an output is a don’t care for some input combination, the designer or logic optimization program is free to make the output true or false for that input combination. Input don’t cares arise when an output depends on only some of the inputs, and they are also shown as Xs, though in the input portion of the truth table.

Don’t Cares

Consider a logic function with inputs A, B, and C defined as follows:

EXAMPLE

■

If A or C is true, then output D is true, whatever the value of B.

■

If A or B is true, then output E is true, whatever the value of C.

■

Output F is true if exactly one of the inputs is true, although we don’t care about the value of F, whenever D and E are both true.

Show the full truth table for this function and the truth table using don’t cares. How many product terms are required in a PLA for each of these? Here’s the full truth table, without don’t cares: A

Inputs B

C

0

0

0

0

0

0

1

0

ANSWER

D

Outputs E

F

0

0

0

1

1

0

1

0

0

1

1

1

1

1

1

0

1

0

0

1

1

1

1

0

1

1

1

0

1

1

0

1

1

0

1

1

1

1

1

0

C-18

Appendix C The Basics of Logic Design

This requires seven product terms without optimization. The truth table written with output don’t cares looks like this: A

Inputs B

C

D

Outputs E

F

0

0

0

0

0

0

0

0

1

1

0

1

0

1

0

0

1

1

0

1

1

1

1

X

1

0

0

1

1

X

1

0

1

1

1

X

1

1

0

1

1

X

1

1

1

1

1

X

If we also use the input don’t cares, this truth table can be further simplified to yield the following: A

Inputs B

C

D

Outputs E

F

0

0

0

0

0

0

0

0

1

1

0

1

0

1

0

0

1

1

X

1

1

1

1

X

1

X

X

1

1

X

This simplified truth table requires a PLA with four minterms, or it can be implemented in discrete gates with one two-input AND gate and three OR gates (two with three inputs and one with two inputs). This compares to the original truth table that had seven minterms and would have required four AND gates. Logic minimization is critical to achieving efficient implementations. One tool useful for hand minimization of random logic is Karnaugh maps. Karnaugh maps represent the truth table graphically, so that product terms that may be combined are easily seen. Nevertheless, hand optimization of significant logic functions using Karnaugh maps is impractical, both because of the size of the maps and their complexity. Fortunately, the process of logic minimization is highly mechanical and can be performed by design tools. In the process of minimization, the tools take advantage of the don’t cares, so specifying them is important. The textbook references at the end of this Appendix provide further discussion on logic minimization, Karnaugh maps, and the theory behind such minimization algorithms.

Arrays of Logic Elements Many of the combinational operations to be performed on data have to be done to an entire word (32 bits) of data. Thus we often want to build an array of logic elements,

C.3

Combinational Logic

which we can represent simply by showing that a given operation will happen to an entire collection of inputs. For example, we saw on page C-9 what a 1-bit multiplexor looked like, but inside a machine, much of the time we want to select between a pair of buses. A bus is a collection of data lines that is treated together as a single logical signal. (The term bus is also used to indicate a shared collection of lines with multiple sources and uses, especially in Chapter 6, where I/O buses were discussed.) For example, in the MIPS instruction set, the result of an instruction that is written into a register can come from one of two sources. A multiplexor is used to choose which of the two buses (each 32 bits wide) will be written into the Result register. The 1-bit multiplexor, which we showed earlier, will need to be replicated 32 times. We indicate that a signal is a bus rather than a single 1-bit line by showing it with a thicker line in a figure. Most buses are 32 bits wide; those that are not are explicitly labeled with their width. When we show a logic unit whose inputs and outputs are buses, this means that the unit must be replicated a sufficient number of times to accommodate the width of the input. Figure C.3.6 shows how we draw a multiplexor that selects between a pair of 32-bit buses and how this expands in terms of 1-bit-wide multiplexors. Sometimes we need to construct an array of logic elements where the inputs for some elements in the array are outputs from earlier elements. For example, this is how a multibit-wide ALU is constructed. In such cases, we must explicitly show how to create wider arrays, since the individual elements of the array are no longer independent, as they are in the case of a 32-bit-wide multiplexor. Select

A

B

Select

32

32

M u x

A31 32

C B31

A30

B30

M u x

M u x

C31

C30 .. .

.. . A0

B0

a. A 32-bit wide 2-to-1 multiplexor

M u x

C0

b. The 32-bit wide multiplexor is actually an array of 32 1-bit multiplexors

FIGURE C.3.6 A multiplexor is arrayed 32 times to perform a selection between two 32-bit inputs. Note that there is still only one data selection signal used for all 32 1-bit multiplexors.

C-19

bus In logic design, a collection of data lines that is treated together as a single logical signal; also, a shared collection of lines with multiple sources and uses.

C-20

Appendix C The Basics of Logic Design

Check Yourself

Parity is a function in which the output depends on the number of 1s in the input. For an even parity function, the output is 1 if the input has an even number of ones. Suppose a ROM is used to implement an even parity function with a 4-bit input. Which of A, B, C, or D represents the contents of the ROM? Address

A

B

C

D

0

0

1

0

1

1

0

1

1

0

2

0

1

0

1

3

0

1

1

0

4

0

1

0

1

5

0

1

1

0

6

0

1

0

1

7

0

1

1

0

8

1

0

0

1

9

1

0

1

0

10

1

0

0

1

11

1

0

1

0

12

1

0

0

1

13

1

0

1

0

14

1

0

0

1

15

1

0

1

0

C.4 hardware description language A programming language for describing hardware, used for generating simulations of a hardware design and also as input to synthesis tools that can generate actual hardware.

Verilog One of the two most common hardware description languages. VHDL One of the two most common hardware description languages.

Using a Hardware Description Language

Today most digital design of processors and related hardware systems is done using a hardware description language. Such a language serves two purposes. First, it provides an abstract description of the hardware to simulate and debug the design. Second, with the use of logic synthesis and hardware compilation tools, this description can be compiled into the hardware implementation. In this section, we introduce the hardware description language Verilog and show how it can be used for combinational design. In the rest of the appendix, we expand the use of Verilog to include design of sequential logic. In the optional sections of Chapter 4 that appear on the CD, we use Verilog to describe processor implementations. In the optional section from Chapter 5 that appears on the CD, we use system Verilog to describe cache controller implementations. System Verilog adds structures and some other useful features to Verilog. Verilog is one of the two primary hardware description languages; the other is VHDL. Verilog is somewhat more heavily used in industry and is based on C, as opposed to VHDL, which is based on Ada. The reader generally familiar with C will

C.4

Using a Hardware Description Language

find the basics of Verilog, which we use in this appendix, easy to follow. Readers already familiar with VHDL should find the concepts simple, provided they have been exposed to the syntax of C. Verilog can specify both a behavioral and a structural definition of a digital system. A behavioral specification describes how a digital system functionally operates. A structural specification describes the detailed organization of a digital system, usually using a hierarchical description. A structural specification can be used to describe a hardware system in terms of a hierarchy of basic elements such as gates and switches. Thus, we could use Verilog to describe the exact contents of the truth tables and datapath of the last section. With the arrival of hardware synthesis tools, most designers now use Verilog or VHDL to structurally describe only the datapath, relying on logic synthesis to generate the control from a behavioral description. In addition, most CAD systems provide extensive libraries of standardized parts, such as ALUs, multiplexors, register files, memories, and programmable logic blocks, as well as basic gates. Obtaining an acceptable result using libraries and logic synthesis requires that the specification be written with an eye toward the eventual synthesis and the desired outcome. For our simple designs, this primarily means making clear what we expect to be implemented in combinational logic and what we expect to require sequential logic. In most of the examples we use in this section and the remainder of this appendix, we have written the Verilog with the eventual synthesis in mind.

C-21

behavioral specification Describes how a digital system operates functionally.

structural specification Describes how a digital system is organized in terms of a hierarchical connection of elements.

hardware synthesis tools Computer-aided design software that can generate a gatelevel design based on behavioral descriptions of a digital system.

Datatypes and Operators in Verilog There are two primary datatypes in Verilog: 1. A wire specifies a combinational signal. 2. A reg (register) holds a value, which can vary with time. A reg need not necessarily correspond to an actual register in an implementation, although it often will. A register or wire, named X, that is 32 bits wide is declared as an array: reg [31:0] X or wire [31:0] X, which also sets the index of 0 to designate the least significant bit of the register. Because we often want to access a subfield of a register or wire, we can refer to a contiguous set of bits of a register or wire with the notation [starting bit: ending bit], where both indices must be constant values. An array of registers is used for a structure like a register file or memory. Thus, the declaration reg [31:0] registerfile[0:31]

specifies a variable registerfile that is equivalent to a MIPS registerfile, where register 0 is the first. When accessing an array, we can refer to a single element, as in C, using the notation registerfile[regnum].

wire In Verilog, specifies a combinational signal.

reg In Verilog, a register.

C-22

Appendix C The Basics of Logic Design

The possible values for a register or wire in Verilog are ■

0 or 1, representing logical false or true

■

X, representing unknown, the initial value given to all registers and to any wire not connected to something

■

Z, representing the high-impedance state for tristate gates, which we will not discuss in this appendix

Constant values can be specified as decimal numbers as well as binary, octal, or hexadecimal. We often want to say exactly how large a constant field is in bits. This is done by prefixing the value with a decimal number specifying its size in bits. For example: ■ 4’b0100

specifies a 4-bit binary constant with the value 4, as does 4’d4.

specifies an 8-bit constant with the value −4 (in two’s complement representation)

■ – 8 ‘h4

Values can also be concatenated by placing them within { } separated by commas. The notation {x {bit field}} replicates bit field x times. For example: ■ {16{2’b01}}

creates a 32-bit value with the pattern 0101 . . . 01.

■ {A[31:16],B[15:0]}

creates a value whose upper 16 bits come from A and whose lower 16 bits come from B.

Verilog provides the full set of unary and binary operators from C, including the arithmetic operators (+, −, *. /), the logical operators (&, |, ~), the comparison operators (= =, !=, >, <, <=, >=), the shift operators (<<, >>), and C’s conditional operator (?, which is used in the form condition ? expr1 :expr2 and returns expr1 if the condition is true and expr2 if it is false). Verilog adds a set of unary logic reduction operators (&, |, ^) that yield a single bit by applying the logical operator to all the bits of an operand. For example, &A returns the value obtained by ANDing all the bits of A together, and ^A returns the reduction obtained by using exclusive OR on all the bits of A.

Check Yourself

Which of the following define exactly the same value? 1. 8’b11110000 2. 8’hF0 3. 8’d240 4. {{4{1’b1}},{4{1’b0}}} 5. {4’b1,4’b0}

C.4

Using a Hardware Description Language

Structure of a Verilog Program A Verilog program is structured as a set of modules, which may represent anything from a collection of logic gates to a complete system. Modules are similar to classes in C++, although not nearly as powerful. A module specifies its input and output ports, which describe the incoming and outgoing connections of a module. A module may also declare additional variables. The body of a module consists of: ■ initial ■

constructs, which can initialize reg variables

Continuous assignments, which define only combinational logic

■ always

constructs, which can define either sequential or combinational

logic ■

Instances of other modules, which are used to implement the module being defined

Representing Complex Combinational Logic in Verilog A continuous assignment, which is indicated with the keyword assign, acts like a combinational logic function: the output is continuously assigned the value, and a change in the input values is reflected immediately in the output value. Wires may only be assigned values with continuous assignments. Using continuous assignments, we can define a module that implements a half-adder, as Figure C.4.1 shows. Assign statements are one sure way to write Verilog that generates combinational logic. For more complex structures, however, assign statements may be awkward or tedious to use. It is also possible to use the always block of a module to describe a combinational logic element, although care must be taken. Using an always block allows the inclusion of Verilog control constructs, such as if-then–else, case statements, for statements, and repeat statements, to be used. These statements are similar to those in C with small changes. An always block specifies an optional list of signals on which the block is sensitive (in a list starting with @). The always block is re-evaluated if any of the listed module half_adder (A,B,Sum,Carry); input A,B; //two 1-bit inputs output Sum, Carry; //two 1-bit outputs assign Sum = A ^ B; //sum is A xor B assign Carry = A & B; //Carry is A and B endmodule FIGURE C.4.1

A Verilog module that defines a half-adder using continuous assignments.

C-23

C-24

sensitivity list The list of signals that specifies when an always block should be re-evaluated.

Appendix C The Basics of Logic Design

signals changes value; if the list is omitted, the always block is constantly re-evaluated. When an always block is specifying combinational logic, the sensitivity list should include all the input signals. If there are multiple Verilog statements to be executed in an always block, they are surrounded by the keywords begin and end, which take the place of the { and } in C. An always block thus looks like this: always @(list of signals that cause reevaluation) begin Verilog statements including assignments and other control statements end

blocking assignment In Verilog, an assignment that completes before the execution of the next statement. nonblocking assignment An assignment that continues after evaluating the right-hand side, assigning the left-hand side the value only after all right-hand sides are evaluated.

Reg variables may only be assigned inside an always block, using a procedural assignment statement (as distinguished from continuous assignment we saw earlier). There are, however, two different types of procedural assignments. The assignment operator = executes as it does in C; the right-hand side is evaluated, and the left-hand side is assigned the value. Furthermore, it executes like the normal C assignment statement: that is, it is completed before the next statement is executed. Hence, the assignment operator = has the name blocking assignment. This blocking can be useful in the generation of sequential logic, and we will return to it shortly. The other form of assignment (nonblocking) is indicated by <=. In nonblocking assignment, all right-hand sides of the assignments in an always group are evaluated and the assignments are done simultaneously. As a first example of combinational logic implemented using an always block, Figure C.4.2 shows the implementation of a 4-to-1 multiplexor, which uses a case construct to make it easy to write. The case construct looks like a C switch statement. Figure C.4.3 shows a definition of a MIPS ALU, which also uses a case statement. Since only reg variables may be assigned inside always blocks, when we want to describe combinational logic using an always block, care must be taken to ensure that the reg does not synthesize into a register. A variety of pitfalls are described in the elaboration below.

Elaboration: Continuous assignment statements always yield combinational logic, but other Verilog structures, even when in always blocks, can yield unexpected results during logic synthesis. The most common problem is creating sequential logic by implying the existence of a latch or register, which results in an implementation that is both slower and more costly than perhaps intended. To ensure that the logic that you intend to be combinational is synthesized that way, make sure you do the following: 1. Place all combinational logic in a continuous assignment or an always block. 2. Make sure that all the signals used as inputs appear in the sensitivity list of an always block. 3. Ensure that every path through an always block assigns a value to the exact same set of bits. The last of these is the easiest to overlook; read through the example in Figure C.5.15 to convince yourself that this property is adhered to.

C.4

Using a Hardware Description Language

C-25

module Mult4to1 (In1,In2,In3,In4,Sel,Out); input [31:0] In1, In2, In3, In4; /four 32-bit inputs input [1:0] Sel; //selector signal output reg [31:0] Out;// 32-bit output always @(In1, In2, In3, In4, Sel) case (Sel) //a 4->1 multiplexor 0: Out <= In1; 1: Out <= In2; 2: Out <= In3; default: Out <= In4; endcase endmodule FIGURE C.4.2 A Verilog definition of a 4-to-1 multiplexor with 32-bit inputs, using a case statement. The case statement acts like a C switch statement, except that in Verilog only the code associated with the selected case is executed (as if each case state had a break at the end) and there is no fall-through to the next statement.

module MIPSALU (ALUctl, A, B, ALUOut, Zero); input [3:0] ALUctl; input [31:0] A,B; output reg [31:0] ALUOut; output Zero; assign Zero = (ALUOut==0); //Zero is true if ALUOut is 0; goes anywhere always @(ALUctl, A, B) //reevaluate if these change case (ALUctl) 0: ALUOut <= A & B; 1: ALUOut <= A | B; 2: ALUOut <= A + B; 6: ALUOut <= A – B; 7: ALUOut <= A < B ? 1:0; 12: ALUOut <= ~(A | B); // result is nor default: ALUOut <= 0; //default to 0, should not happen; endcase endmodule FIGURE C.4.3 A Verilog behavioral definition of a MIPS ALU. This could be synthesized using a module library containing basic arithmetic and logical operations.

C-26

Appendix C The Basics of Logic Design

Check Yourself

Assuming all values are initially zero, what are the values of A and B after executing this Verilog code inside an always block? C=1; A <= C; B = C;

ALU n. [Arthritic Logic Unit or (rare) Arithmetic Logic Unit] A random-number generator supplied as standard with all computer systems. Stan Kelly-Bootle, The Devil’s DP Dictionary, 1981

C.5

Constructing a Basic Arithmetic Logic Unit

The arithmetic logic unit (ALU ) is the brawn of the computer, the device that performs the arithmetic operations like addition and subtraction or logical operations like AND and OR. This section constructs an ALU from four hardware building blocks (AND and OR gates, inverters, and multiplexors) and illustrates how combinational logic works. In the next section, we will see how addition can be sped up through more clever designs. Because the MIPS word is 32 bits wide, we need a 32-bit-wide ALU. Let’s assume that we will connect 32 1-bit ALUs to create the desired ALU. We’ll therefore start by constructing a 1-bit ALU.

A 1-Bit ALU The logical operations are easiest, because they map directly onto the hardware components in Figure C.2.1. The 1-bit logical unit for AND and OR looks like Figure C.5.1. The multiplexor on the right then selects a AND b or a OR b, depending on whether the value of Operation is 0 or 1. The line that controls the multiplexor is shown in color to distinguish it from the lines containing data. Notice that we have renamed the control and output lines of the multiplexor to give them names that reflect the function of the ALU. The next function to include is addition. An adder must have two inputs for the operands and a single-bit output for the sum. There must be a second output to pass on the carry, called CarryOut. Since the CarryOut from the neighbor adder must be included as an input, we need a third input. This input is called CarryIn. Figure C.5.2 shows the inputs and the outputs of a 1-bit adder. Since we know what addition is supposed to do, we can specify the outputs of this “black box” based on its inputs, as Figure C.5.3 demonstrates. We can express the output functions CarryOut and Sum as logical equations, and these equations can in turn be implemented with logic gates. Let’s do CarryOut. Figure C.5.4 shows the values of the inputs when CarryOut is a 1. We can turn this truth table into a logical equation: CarryOut = (b · CarryIn) + (a · CarryIn) + (a · b) + (a · b · CarryIn)

C.5

Constructing a Basic Arithmetic Logic Unit

Operation a

0 Result 1

b FIGURE C.5.1

The 1-bit logical unit for AND and OR.

CarryIn

a +

Sum

b

CarryOut FIGURE C.5.2 A 1-bit adder. This adder is called a full adder; it is also called a (3,2) adder because it has 3 inputs and 2 outputs. An adder with only the a and b inputs is called a (2,2) adder or half-adder.

Inputs

Outputs

a

b

CarryIn

CarryOut

Sum

Comments

0

0

0

0

0

0 + 0 + 0 = 00two

0

0

1

0

1

0 + 0 + 1 = 01two

0

1

0

0

1

0 + 1 + 0 = 01two

0

1

1

1

0

0 + 1 + 1 = 10two

1

0

0

0

1

1 + 0 + 0 = 01two

1

0

1

1

0

1 + 0 + 1 = 10two

1

1

0

1

0

1 + 1 + 0 = 10two

1

1

1

1

1

1 + 1 + 1 = 11two

FIGURE C.5.3

Input and output specification for a 1-bit adder.

C-27

C-28

Appendix C The Basics of Logic Design

If a · b · CarryIn is true, then all of the other three terms must also be true, so we can leave out this last term corresponding to the fourth line of the table. We can thus simplify the equation to CarryOut = (b · CarryIn) + (a · CarryIn) + (a · b) Figure C.5.5 shows that the hardware within the adder black box for CarryOut consists of three AND gates and one OR gate. The three AND gates correspond exactly to the three parenthesized terms of the formula above for CarryOut, and the OR gate sums the three terms. Inputs a

b

CarryIn

0

1

1

1

0

1

1

1

0

1

1

1

FIGURE C.5.4

Values of the inputs when CarryOut is a 1.

CarryIn

a

b

CarryOut FIGURE C.5.5 Adder hardware for the CarryOut signal. The rest of the adder hardware is the logic for the Sum output given in the equation on this page.

The Sum bit is set when exactly one input is 1 or when all three inputs are 1. The _ Sum results in a complex Boolean equation (recall that a means NOT a): __ _______

_

_______

_ __

Sum = (a · b · CarryIn) + (a · b · CarryIn) + (a · b · CarryIn) + (a · b · CarryIn) The drawing of the logic for the Sum bit in the adder black box is left as an exercise for the reader.

C.5

Constructing a Basic Arithmetic Logic Unit

Figure C.5.6 shows a 1-bit ALU derived by combining the adder with the earlier components. Sometimes designers also want the ALU to perform a few more simple operations, such as generating 0. The easiest way to add an operation is to expand the multiplexor controlled by the Operation line and, for this example, to connect 0 directly to the new input of that expanded multiplexor. Operation CarryIn a

0

1

b

1

Result

2

CarryOut FIGURE C.5.6

A 1-bit ALU that performs AND, OR, and addition (see Figure C.5.5).

A 32-Bit ALU Now that we have completed the 1-bit ALU, the full 32-bit ALU is created by connecting adjacent “black boxes.” Using xi to mean the ith bit of x, Figure C.5.7 shows a 32-bit ALU. Just as a single stone can cause ripples to radiate to the shores of a quiet lake, a single carry out of the least significant bit (Result0) can ripple all the way through the adder, causing a carry out of the most significant bit (Result31). Hence, the adder created by directly linking the carries of 1-bit adders is called a ripple carry adder. We’ll see a faster way to connect the 1-bit adders starting on page C-38. Subtraction is the same as adding the negative version of an operand, and this is how adders perform subtraction. Recall that the shortcut for negating a two’s complement number is to invert each bit (sometimes called the one’s complement) and then add 1.__ To invert each bit, we simply add a 2:1 multiplexor that chooses between b and b, as Figure C.5.8 shows. Suppose we connect 32 of these 1-bit ALUs, as we did in Figure C.5.7. The added multiplexor gives the option of b or its inverted value, depending on Binvert, but

C-29

C-30

Appendix C The Basics of Logic Design

Operation CarryIn

a0 b0

a1 b1

a2 b2 .. .

CarryIn ALU0 CarryOut

Result0

CarryIn ALU1 CarryOut

Result1

CarryIn ALU2 CarryOut

Result2

.. .

.. .

CarryIn ALU31

a31 b31

Result31

FIGURE C.5.7 A 32-bit ALU constructed from 32 1-bit ALUs. CarryOut of the less significant bit is connected to the CarryIn of the more significant bit. This organization is called ripple carry.

this is only one step in negating a two’s complement number. Notice that the least significant bit still has a CarryIn signal, even though it’s unnecessary for addition. What happens if we set this CarryIn to 1 instead of 0? The adder will then calculate a + b + 1. By selecting the inverted version of b, we get exactly what we want: __

__

a + b + 1 = a + (b + 1) = a + (−b) = a − b The simplicity of the hardware design of a two’s complement adder helps explain why two’s complement representation has become the universal standard for integer computer arithmetic.

C.5

Constructing a Basic Arithmetic Logic Unit

Binvert

Operation CarryIn

a

0

1

b

0

1

Result

2

1

CarryOut __

FIGURE __C.5.8 A 1-bit ALU that performs AND, OR, and addition on a and b or a and b. By selecting b (Binvert = 1) and setting CarryIn to 1 in the least significant bit of the ALU, we get two’s complement subtraction of b from a instead of addition of b to a.

A MIPS ALU also needs a NOR function. Instead of adding a separate gate for NOR, we can reuse much of the hardware already in the ALU, like we did for subtract. The insight comes from the following truth about NOR: _____ _ __ ( a + b) = a · b That is, NOT (a OR b) is equivalent to NOT a AND NOT b. This fact is called DeMorgan’s theorem and is explored in the exercises in more depth. Since we have AND and NOT b, we only need to add NOT a to the ALU. Figure C.5.9 shows that change.

Tailoring the 32-Bit ALU to MIPS These four operations—add, subtract, AND, OR—are found in the ALU of almost every computer, and the operations of most MIPS instructions can be performed by this ALU. But the design of the ALU is incomplete. One instruction that still needs support is the set on less than instruction (slt). Recall that the operation produces 1 if rs < rt, and 0 otherwise. Consequently, slt will set all but the least significant bit to 0, with the least significant bit set according to the comparison. For the ALU to perform slt, we first need to expand the three-input

C-31

C-32

Appendix C The Basics of Logic Design

Ainvert

Operation Binvert

a

CarryIn

0 0

1

1

b

0

!

Result

2

1

CarryOut __

__

FIGURE C.5.9 A 1-bit ALU __ that performs AND, OR, and addition on a and b or a and b. By _ selecting a (Ainvert = 1) and b (Binvert = 1), we get a NOR b instead of a AND b.

multiplexor in Figure C.5.8 to add an input for the slt result. We call that new input Less and use it only for slt. The top drawing of Figure C.5.10 shows the new 1-bit ALU with the expanded multiplexor. From the description of slt above, we must connect 0 to the Less input for the upper 31 bits of the ALU, since those bits are always set to 0. What remains to consider is how to compare and set the least significant bit for set on less than instructions. What happens if we subtract b from a? If the difference is negative, then a < b since (a − b) < 0 ⇒ ((a − b) + b) < (0 + b) ⇒a
C.5

Constructing a Basic Arithmetic Logic Unit

Operation

Ainvert Binvert a

CarryIn

0

0

1 1 Result b

0

2

!

1 Less

3

CarryOut

Operation

Ainvert Binvert a

CarryIn

0

0

1 1 Result b

0

!

2

1 Less

3 Set Overflow detection

Overflow

__

FIGURE C.5.10 (Top) A 1-bit ALU that performs AND, OR, and addition on a and b or b, and (bottom) a 1-bit ALU for the most significant bit. The top drawing includes a direct input that is connected to perform the set on less than operation (see Figure C.5.11); the bottom has a direct output from the adder for the less than comparison called Set. (See Exercise C.24 at the end of this Appendix to see how to calculate overflow with fewer inputs.)

C-33

C-34

Appendix C The Basics of Logic Design

Operation

Binvert Ainvert CarryIn

a0 b0

CarryIn ALU0 Less CarryOut

Result0

a1 b1 0

CarryIn ALU1 Less CarryOut

Result1

a2 b2 0

CarryIn ALU2 Less CarryOut

Result2

.. .

. .. . . .. .. a31 b31 0

.. . CarryIn CarryIn ALU31 Less

.. . Result31 Set Overflow

FIGURE C.5.11 A 32-bit ALU constructed from the 31 copies of the 1-bit ALU in the top of Figure C.5.10 and one 1-bit ALU in the bottom of that figure. The Less inputs are connected to 0 except for the least significant bit, which is connected to the Set output of the most significant bit. If the ALU performs a − b and we select the input 3 in the multiplexor in Figure C.5.10, then Result = 0 . . . 001 if a < b, and Result = 0 . . . 000 otherwise.

Thus, we need a new 1-bit ALU for the most significant bit that has an extra output bit: the adder output. The bottom drawing of Figure C.5.10 shows the design, with this new adder output line called Set, and used only for slt. As long as we need a special ALU for the most significant bit, we added the overflow detection logic since it is also associated with that bit.

C.5

Constructing a Basic Arithmetic Logic Unit

Alas, the test of less than is a little more complicated than just described because of overflow, as we explore in the exercises. Figure C.5.11 shows the 32-bit ALU. Notice that every time we want the ALU to subtract, we set both CarryIn and Binvert to 1. For adds or logical operations, we want both control lines to be 0. We can therefore simplify control of the ALU by combining the CarryIn and Binvert to a single control line called Bnegate. To further tailor the ALU to the MIPS instruction set, we must support conditional branch instructions. These instructions branch either if two registers are equal or if they are unequal. The easiest way to test equality with the ALU is to subtract b from a and then test to see if the result is 0, since (a − b = 0) ⇒ a = b Thus, if we add hardware to test if the result is 0, we can test for equality. The simplest way is to OR all the outputs together and then send that signal through an inverter: Zero = (Result31 + Result30 + . . . + Result2 + Result1 + Result0)

Figure C.5.12 shows the revised 32-bit ALU. We can think of the combination of the 1-bit Ainvert line, the 1-bit Binvert line, and the 2-bit Operation lines as 4-bit control lines for the ALU, telling it to perform add, subtract, AND, OR, or set on less than. Figure C.5.13 shows the ALU control lines and the corresponding ALU operation. Finally, now that we have seen what is inside a 32-bit ALU, we will use the universal symbol for a complete ALU, as shown in Figure C.5.14.

Defining the MIPS ALU in Verilog Figure C.5.15 shows how a combinational MIPS ALU might be specified in Verilog; such a specification would probably be compiled using a standard parts library that provided an adder, which could be instantiated. For completeness, we show the ALU control for MIPS in Figure C.5.16, which is used in Chapter 4, where we build a Verilog version of the MIPS datapath. The next question is, “How quickly can this ALU add two 32-bit operands?” We can determine the a and b inputs, but the CarryIn input depends on the operation in the adjacent 1-bit adder. If we trace all the way through the chain of dependencies, we connect the most significant bit to the least significant bit, so the most significant bit of the sum must wait for the sequential evaluation of all 32 1-bit adders. This sequential chain reaction is too slow to be used in time-critical hardware. The next section explores how to speed-up addition. This topic is not crucial to understanding the rest of the appendix and may be skipped.

C-35

C-36

Appendix C The Basics of Logic Design

Operation

Bnegate Ainvert a0 b0

CarryIn ALU0 Less CarryOut

a1 b1 0

CarryIn ALU1 Less CarryOut

a2 b2 0

CarryIn ALU2 Less CarryOut .. .

. .. . .. .. .

Result1 .. .

Zero

Result2

.. . CarryIn

.. .

.. .

Result31

CarryIn ALU31 Less

a31 b31 0

FIGURE C.5.12

Result0

Set Overflow

The final 32-bit ALU. This adds a Zero detector to Figure C.5.11.

ALU control lines

Function

0000

AND

0001

OR

0010

add

0110

subtract

0111

set on less than

1100

NOR

FIGURE C.5.13 The values of the three ALU control lines, Bnegate, and Operation, and the corresponding ALU operations.

C.5

Constructing a Basic Arithmetic Logic Unit

ALU operation

a Zero ALU

Result Overflow

b

CarryOut FIGURE C.5.14 The symbol commonly used to represent an ALU, as shown in Figure C.5.12. This symbol is also used to represent an adder, so it is normally labeled either with ALU or Adder.

module MIPSALU (ALUctl, A, B, ALUOut, Zero); input [3:0] ALUctl; input [31:0] A,B; output reg [31:0] ALUOut; output Zero; assign Zero = (ALUOut==0); //Zero is true if ALUOut is 0 always @(ALUctl, A, B) begin //reevaluate if these change case (ALUctl) 0: ALUOut <= A & B; 1: ALUOut <= A | B; 2: ALUOut <= A + B; 6: ALUOut <= A - B; 7: ALUOut <= A < B ? 1 : 0; 12: ALUOut <= ~(A | B); // result is nor default: ALUOut <= 0; endcase end endmodule FIGURE C.5.15

A Verilog behavioral definition of a MIPS ALU.

C-37

C-38

Appendix C The Basics of Logic Design

module ALUControl (ALUOp, FuncCode, ALUCtl); input [1:0] ALUOp; input [5:0] FuncCode; output [3:0] reg ALUCtl; always case (FuncCode) 32: ALUOp<=2; // add 34: ALUOp<=6; //subtract 36: ALUOP<=0; // and 37: ALUOp<=1; // or 39: ALUOp<=12; // nor 42: ALUOp<=7; // slt default: ALUOp<=15; // should not happen endcase endmodule FIGURE C.5.16

Check Yourself

The MIPS ALU control: a simple piece of combinational control logic.

Suppose you wanted to add the operation NOT (a AND b), called NAND. How could the ALU change to support it? 1. No You can calculate NAND quickly using the current ALU since ____change. _ __ (a˙b) = a + b and we already have NOT a, NOT b, and OR. 2. You must expand the big multiplexor to add another input, and then add new logic to calculate NAND.

C.6

Faster Addition: Carry Lookahead

The key to speeding up addition is determining the carry in to the high-order bits sooner. There are a variety of schemes to anticipate the carry so that the worstcase scenario is a function of the log2 of the number of bits in the adder. These anticipatory signals are faster because they go through fewer gates in sequence, but it takes many more gates to anticipate the proper carry. A key to understanding fast-carry schemes is to remember that, unlike software, hardware executes in parallel whenever inputs change.

Fast Carry Using “Infinite” Hardware As we mentioned earlier, any equation can be represented in two levels of logic. Since the only external inputs are the two operands and the CarryIn to the least

C.6

Faster Addition: Carry Lookahead

significant bit of the adder, in theory we could calculate the CarryIn values to all the remaining bits of the adder in just two levels of logic. For example, the CarryIn for bit 2 of the adder is exactly the CarryOut of bit 1, so the formula is CarryIn2 = (b1 . CarryIn1) + (a1 . CarryIn1) + (a1 . b1) Similarly, CarryIn1 is defined as CarryIn1 = (b0 . CarryIn0) + (a0 . CarryIn0) + (a0 . b0) Using the shorter and more traditional abbreviation of ci for CarryIni, we can rewrite the formulas as c2 = (b1 . c1) + (a1 . c1) + (a1 . b1) c1 = (b0 . C0) + (a0 . c0) + (a0 . b0) Substituting the definition of c1 for the first equation results in this formula: c2 = (a1 . a0 . b0) + (a1 . a0 . c0) + (a1 . b0 . c0) + (b1 . a0 . b0) + (b1 . a0 . c0) + (b1 . b0 . c0) + (a1 . b1) You can imagine how the equation expands as we get to higher bits in the adder; it grows rapidly with the number of bits. This complexity is reflected in the cost of the hardware for fast carry, making this simple scheme prohibitively expensive for wide adders.

Fast Carry Using the First Level of Abstraction: Propagate and Generate Most fast-carry schemes limit the complexity of the equations to simplify the hardware, while still making substantial speed improvements over ripple carry. One such scheme is a carry-lookahead adder. In Chapter 1, we said computer systems cope with complexity by using levels of abstraction. A carry-lookahead adder relies on levels of abstraction in its implementation. Let’s factor our original equation as a first step: ci + 1 = (bi . ci) + (ai . ci) + (ai . bi) = (ai . bi) + (ai + bi) . ci If we were to rewrite the equation for c2 using this formula, we would see some repeated patterns: c2 = (a1 . b1) + (a1 + b1) . ((a0 . b0) + (a0 + b0) . c0) Note the repeated appearance of (ai . bi) and (ai + bi) in the formula above. These two important factors are traditionally called generate (gi) and propagate (pi):

C-39

C-40

Appendix C The Basics of Logic Design

gi = ai . bi pi = ai + bi Using them to define ci + 1, we get ci + 1 = gi + pi . ci To see where the signals get their names, suppose gi is 1. Then ci + 1 = gi + pi . ci = 1 + pi . ci = 1 That is, the adder generates a CarryOut (ci + 1) independent of the value of CarryIn (ci). Now suppose that gi is 0 and pi is 1. Then ci + 1 = gi + pi . ci = 0 + 1 . ci = ci That is, the adder propagates CarryIn to a CarryOut. Putting the two together, CarryIni +1 is a 1 if either gi is 1 or both pi is 1 and CarryIni is 1. As an analogy, imagine a row of dominoes set on edge. The end domino can be tipped over by pushing one far away, provided there are no gaps between the two. Similarly, a carry out can be made true by a generate far away, provided all the propagates between them are true. Relying on the definitions of propagate and generate as our first level of abstraction, we can express the CarryIn signals more economically. Let’s show it for 4 bits: c1 = g0 + (p0 . c0) c2 = g1 + (p1 . g0) + (p1 . p0 . c0) c3 = g2 + (p2 . g1) + (p2 . p1 . g0) + (p2 . p1 . p0 . c0) c4 = g3 + (p3 . g2) + (p3 . p2 . g1) + (p3 . p2 . p1 . g0) + (p3 . p2 . p1 . p0 . c0) These equations just represent common sense: CarryIni is a 1 if some earlier adder generates a carry and all intermediary adders propagate a carry. Figure C.6.1 uses plumbing to try to explain carry lookahead. Even this simplified form leads to large equations and, hence, considerable logic even for a 16-bit adder. Let’s try moving to two levels of abstraction.

Fast Carry Using the Second Level of Abstraction First, we consider this 4-bit adder with its carry-lookahead logic as a single building block. If we connect them in ripple carry fashion to form a 16-bit adder, the add will be faster than the original with a little more hardware.

C.6

Faster Addition: Carry Lookahead

To go faster, we’ll need carry lookahead at a higher level. To perform carry look ahead for 4-bit adders, we need to propagate and generate signals at this higher level. Here they are for the four 4-bit adder blocks: P0 = p3 . p2 . p1 . p0 P1 = p7 . p6 . p5 . p4 P2 = p11 . p10 . p9 . p8 P3 = p15 . p14 . p13 . p12 That is, the “super” propagate signal for the 4-bit abstraction (Pi) is true only if each of the bits in the group will propagate a carry. For the “super” generate signal (Gi), we care only if there is a carry out of the most significant bit of the 4-bit group. This obviously occurs if generate is true for that most significant bit; it also occurs if an earlier generate is true and all the intermediate propagates, including that of the most significant bit, are also true: G0 = g3 + (p3 . g2) + (p3 . p2 . g1) + (p3 . p2 . p1 . g0) G1 = g7 + (p7 . g6) + (p7 . p6 . g5) + (p7 . p6 . p5 . g4) G2 = g11 + (p11 . g10) + (p11 . p10 . g9) + (p11 . p10 . p9 . g8) G3 = g15 + (p15 . g14) + (p15 . p14 . g13) + (p15 . p14 . p13 . g12) Figure C.6.2 updates our plumbing analogy to show P0 and G0. Then the equations at this higher level of abstraction for the carry in for each 4-bit group of the 16-bit adder (C1, C2, C3, C4 in Figure C.6.3) are very similar to the carry out equations for each bit of the 4-bit adder (c1, c2, c3, c4) on page C-40: C1 = G0 + (P0 . c0) C2 = G1 + (P1 . G0) + (P1 . P0 . c0) C3 = G2 + (P2 . G1) + (P2 . P1 . G0) + (P2 . P1 . P0 . c0) C4 = G3 + (P3 . G2) + (P3 . P2 . G1) + (P3 . P2 . P1 . G0) + (P3 . P2 . P1 . P0 . c0) Figure C.6.3 shows 4-bit adders connected with such a carry-lookahead unit. The exercises explore the speed differences between these carry schemes, different notations for multibit propagate and generate signals, and the design of a 64-bit adder.

C-41

C-42

Appendix C The Basics of Logic Design

c0

g0 p0 c1 c0

g0

c0 p0 g0

g1

p0 p1 g1

c2

p1

g2 p2

g3 p3 c4 FIGURE C.6.1 A plumbing analogy for carry lookahead for 1 bit, 2 bits, and 4 bits using water pipes and valves. The wrenches are turned to open and close valves. Water is shown in color. The output of the pipe (ci + 1) will be full if either the nearest generate value (gi) is turned on or if the i propagate value (pi) is on and there is water further upstream, either from an earlier generate or a propagate with water behind it. CarryIn (c0) can result in a carry out without the help of any generates, but with the help of all propagates.

C.6

Faster Addition: Carry Lookahead

p0

p1 g0 p2

p3

g1

P0

p1

g2 p2

g3 p3 G0 FIGURE C.6.2 A plumbing analogy for the next-level carry-lookahead signals P0 and G0. P0 is open only if all four propagates (pi ) are open, while water flows in G0 only if at least one generate (gi ) is open and all the propagates downstream from that generate are open.

C-43

C-44

Appendix C The Basics of Logic Design

Both Levels of the Propagate and Generate

EXAMPLE

Determine the gi, pi, Pi, and Gi values of these two 16-bit numbers: a: b:

0001 1010 0011 0011two 1110 0101 1110 1011two

Also, what is CarryOut15 (C4)?

ANSWER

Aligning the bits makes it easy to see the values of generate gi (ai . bi) and propagate pi (ai + bi): a: b: gi: pi:

0001 1110 0000 1111

1010 0101 0000 1111

0011 1110 0010 1111

0011 1011 0011 1011

where the bits are numbered 15 to 0 from left to right. Next, the “super” propagates (P3, P2, P1, P0) are simply the AND of the lower-level propagates: P3 = 1 . 1 . 1 . 1 = 1 P2 = 1 . 1 . 1 . 1 = 1 P1 = 1 . 1 . 1 . 1 = 1 P0 = 1 . 0 . 1 . 1 = 0 The “super” generates are more complex, so use the following equations: G0 = = G1 = = G2 = = G3 = =

g3 + (p3 . g2) + (p3 . p2 . g1) + (p3 . p2 . p1 . g0) 0 + (1 . 0) + (1 . 0 . 1) + (1 . 0 . 1 . 1) = 0 + 0 + 0 + 0 = 0 g7 + (p7 . g6) + (p7 . p6 . g5) + (p7 . p6 . p5 . g4) 0 + (1 . 0) + (1 . 1 . 1) + (1 . 1 . 1 . 0) = 0 + 0 + 1 + 0 = 1 g11 + (p11 . g10) + (p11 . p10 . g9) + (p11 . p10 . p9 . g8) 0 + (1 . 0) + (1 . 1 . 0) + (1 . 1 . 1 . 0) = 0 + 0 + 0 + 0 = 0 g15 + (p15 . g14) + (p15 . p14 . g13) + (p15 . p14 . p13 . g12) 0 + (1 . 0) + (1 . 1 . 0) + (1 . 1 . 1 . 0) = 0 + 0 + 0 + 0 = 0

Finally, CarryOut15 is C4 = G3 + (P3 . G2) + (P3 . P2 . G1) + (P3 . P2 . P1 . G0) + (P3 . P2 . P1 . P0 . c0) = 0 + (1 . 0) + (1 . 1 . 1) + (1 . 1 . 1 . 0) + (1 . 1 . 1 . 0 . 0) = 0+0+1+0+0=1 Hence, there is a carry out when adding these two 16-bit numbers.

C.6

Faster Addition: Carry Lookahead

CarryIn

a0 b0 a1 b1 a2 b2 a3 b3

a4 b4 a5 b5 a6 b6 a7 b7

a8 b8 a9 b9 a10 b10 a11 b11

a12 b12 a13 b13 a14 b14 a15 b15

CarryIn

Result0–3

ALU0 P0 G0

pi gi C1

ci + 1

CarryIn

Carry-lookahead unit

Result4–7

ALU1 P1 G1

pi + 1 gi + 1 C2

ci + 2

CarryIn

Result8–11

ALU2 P2 G2

pi + 2 gi + 2 C3

ci + 3

CarryIn

Result12–15

ALU3 P3 G3

pi + 3 gi + 3 C4

ci + 4

CarryOut FIGURE C.6.3 Four 4-bit ALUs using carry lookahead to form a 16-bit adder. Note that the carries come from the carry-lookahead unit, not from the 4-bit ALUs.

C-45

C-46

Appendix C The Basics of Logic Design

The reason carry lookahead can make carries faster is that all logic begins evaluating the moment the clock cycle begins, and the result will not change once the output of each gate stops changing. By taking the shortcut of going through fewer gates to send the carry in signal, the output of the gates will stop changing sooner, and hence the time for the adder can be less. To appreciate the importance of carry lookahead, we need to calculate the relative performance between it and ripple carry adders.

Speed of Ripple Carry versus Carry Lookahead

EXAMPLE

ANSWER

One simple way to model time for logic is to assume each AND or OR gate takes the same time for a signal to pass through it. Time is estimated by simply counting the number of gates along the path through a piece of logic. Compare the number of gate delays for paths of two 16-bit adders, one using ripple carry and one using two-level carry lookahead. Figure C.5.5 on page C-28 shows that the carry out signal takes two gate delays per bit. Then the number of gate delays between a carry in to the least significant bit and the carry out of the most significant is 16 × 2 = 32. For carry lookahead, the carry out of the most significant bit is just C4, defined in the example. It takes two levels of logic to specify C4 in terms of Pi and Gi (the OR of several AND terms). Pi is specified in one level of logic (AND) using pi, and Gi is specified in two levels using pi and gi, so the worst case for this next level of abstraction is two levels of logic. pi and gi are each one level of logic, defined in terms of ai and bi. If we assume one gate delay for each level of logic in these equations, the worst case is 2 + 2 + 1 = 5 gate delays. Hence, for the path from carry in to carry out, the 16-bit addition by a carry-lookahead adder is six times faster, using this very simple estimate of hardware speed.

Summary Carry lookahead offers a faster path than waiting for the carries to ripple through all 32 1-bit adders. This faster path is paved by two signals, generate and propagate.

C.6

C-47

Faster Addition: Carry Lookahead

The former creates a carry regardless of the carry input, and the latter passes a carry along. Carry lookahead also gives another example of how abstraction is important in computer design to cope with complexity. Using the simple estimate of hardware speed above with gate delays, what is the relative performance of a ripple carry 8-bit add versus a 64-bit add using carrylookahead logic? 1. A 64-bit carry-lookahead adder is three times faster: 8-bit adds are 16 gate delays and 64-bit adds are 7 gate delays. 2. They are about the same speed, since 64-bit adds need more levels of logic in the 16-bit adder. 3. 8-bit adds are faster than 64 bits, even with carry lookahead. Elaboration: We have now accounted for all but one of the arithmetic and logical operations for the core MIPS instruction set: the ALU in Figure C.5.14 omits support of shift instructions. It would be possible to widen the ALU multiplexor to include a left shift by 1 bit or a right shift by 1 bit. But hardware designers have created a circuit called a barrel shifter, which can shift from 1 to 31 bits in no more time than it takes to add two 32-bit numbers, so shifting is normally done outside the ALU.

Elaboration: The logic equation for the Sum output of the full adder on page C-28 can be expressed more simply by using a more powerful gate than AND and OR. An exclusive OR gate is true if the two operands disagree; that is, x ≠ y ⇒ 1 and x = = y ⇒ 0 In some technologies, exclusive OR is more efficient than two levels of AND and OR gates. Using the symbol ⊕ to represent exclusive OR, here is the new equation: Sum = a ⊕ b ⊕ CarryIn Also, we have drawn the ALU the traditional way, using gates. Computers are designed today in CMOS transistors, which are basically switches. CMOS ALU and barrel shifters take advantage of these switches and have many fewer multiplexors than shown in our designs, but the design principles are similar.

Elaboration: Using lowercase and uppercase to distinguish the hierarchy of generate and propagate symbols breaks down when you have more than two levels. An alternate notation that scales is gi..j and pi..j for the generate and propagate signals for bits i to j. Thus, g1..1 is generated for bit 1, g4..1 is for bits 4 to 1, and g16..1 is for bits 16 to 1.

Check Yourself

C-48

Appendix C The Basics of Logic Design

C.7

edge-triggered clocking A clocking scheme in which all state changes occur on a clock edge.

Clocks

Before we discuss memory elements and sequential logic, it is useful to discuss briefly the topic of clocks. This short section introduces the topic and is similar to the discussion found in Section 4.2. More details on clocking and timing methodologies are presented in Section C.11. Clocks are needed in sequential logic to decide when an element that contains state should be updated. A clock is simply a free-running signal with a fixed cycle time; the clock frequency is simply the inverse of the cycle time. As shown in Figure C.7.1, the clock cycle time or clock period is divided into two portions: when the clock is high and when the clock is low. In this text, we use only edge-triggered clocking. This means that all state changes occur on a clock edge. We use an edge-triggered methodology because it is simpler to explain. Depending on the technology, it may or may not be the best choice for a clocking methodology.

clocking methodology The approach used to determine when data is valid and stable relative to the clock.

Falling edge

Clock period

Rising edge

FIGURE C.7.1 A clock signal oscillates between high and low values. The clock period is the time for one full cycle. In an edge-triggered design, either the rising or falling edge of the clock is active and causes state to be changed.

state element A memory element.

synchronous system A memory system that employs clocks and where data signals are read only when the clock indicates that the signal values are stable.

In an edge-triggered methodology, either the rising edge or the falling edge of the clock is active and causes state changes to occur. As we will see in the next section, the state elements in an edge-triggered design are implemented so that the contents of the state elements only change on the active clock edge. The choice of which edge is active is influenced by the implementation technology and does not affect the concepts involved in designing the logic. The clock edge acts as a sampling signal, causing the value of the data input to a state element to be sampled and stored in the state element. Using an edge trigger means that the sampling process is essentially instantaneous, eliminating problems that could occur if signals were sampled at slightly different times. The major constraint in a clocked system, also called a synchronous system, is that the signals that are written into state elements must be valid when the active

C.7

Clocks

clock edge occurs. A signal is valid if it is stable (i.e., not changing), and the value will not change again until the inputs change. Since combinational circuits cannot have feedback, if the inputs to a combinational logic unit are not changed, the outputs will eventually become valid. Figure C.7.2 shows the relationship among the state elements and the combinational logic blocks in a synchronous, sequential logic design. The state elements, whose outputs change only after the clock edge, provide valid inputs to the combinational logic block. To ensure that the values written into the state elements on the active clock edge are valid, the clock must have a long enough period so that all the signals in the combinational logic block stabilize, then the clock edge samples those values for storage in the state elements. This constraint sets a lower bound on the length of the clock period, which must be long enough for all state element inputs to be valid. In the rest of this appendix, as well as in Chapter 4, we usually omit the clock signal, since we are assuming that all state elements are updated on the same clock edge. Some state elements will be written on every clock edge, while others will be written only under certain conditions (such as a register being updated). In such cases, we will have an explicit write signal for that state element. The write signal must still be gated with the clock so that the update occurs only on the clock edge if the write signal is active. We will see how this is done and used in the next section. One other advantage of an edge-triggered methodology is that it is possible to have a state element that is used as both an input and output to the same combinational logic block, as shown in Figure C.7.3. In practice, care must be taken to prevent races in such situations and to ensure that the clock period is long enough; this topic is discussed further in Section C.11. Now that we have discussed how clocking is used to update state elements, we can discuss how to construct the state elements.

State element 1

Combinational logic

State element 2

Clock cycle FIGURE C.7.2 The inputs to a combinational logic block come from a state element, and the outputs are written into a state element. The clock edge determines when the contents of the state elements are updated.

C-49

C-50

Appendix C The Basics of Logic Design

State element

Combinational logic

FIGURE C.7.3 An edge-triggered methodology allows a state element to be read and written in the same clock cycle without creating a race that could lead to undetermined data values. Of course, the clock cycle must still be long enough so that the input values are stable when the active clock edge occurs.

register file A state element that consists of a set of registers that can be read and written by supplying a register number to be accessed.

Elaboration: Occasionally, designers find it useful to have a small number of state elements that change on the opposite clock edge from the majority of the state elements. Doing so requires extreme care, because such an approach has effects on both the inputs and the outputs of the state element. Why then would designers ever do this? Consider the case where the amount of combinational logic before and after a state element is small enough so that each could operate in one-half clock cycle, rather than the more usual full clock cycle. Then the state element can be written on the clock edge corresponding to a half clock cycle, since the inputs and outputs will both be usable after one-half clock cycle. One common place where this technique is used is in register files, where simply reading or writing the register file can often be done in half the normal clock cycle. Chapter 4 makes use of this idea to reduce the pipelining overhead.

C.8

Memory Elements: Flip-Flops, Latches, and Registers

In this section and the next, we discuss the basic principles behind memory elements, starting with flip-flops and latches, moving on to register files, and finishing with memories. All memory elements store state: the output from any memory element depends both on the inputs and on the value that has been stored inside the memory element. Thus all logic blocks containing a memory element contain state and are sequential. R

S

Q

Q

FIGURE C.8.1 A pair of cross-coupled NOR gates value. The value __ can store an internal __ stored on the output Q is recycled by inverting it to obtain Q and then inverting Q to obtain Q. If either R or __ Q is asserted, Q will be deasserted and vice versa.

C.8 Memory Elements: Flip-Flops, Latches, and Registers

C-51

The simplest type of memory elements are unclocked; that is, they do not have any clock input. Although we only use clocked memory elements in this text, an unclocked latch is the simplest memory element, so let’s look at this circuit first. Figure C.8.1 shows an S-R latch (set-reset latch), built__from a pair of NOR gates (OR gates with inverted outputs). The outputs Q and Q represent the value of the stored state and its complement. When neither S nor R are asserted, the cross__ coupled NOR gates act as inverters and store the previous values of Q and Q . For example, if__the output, Q, is true, then the bottom inverter produces a false output (which is Q ), which becomes the input to the top inverter, which produces a true output,__ which is Q, and so on. If S is asserted, then the output Q__ will be asserted and Q will be deasserted, while if R is asserted, then the output Q will be asserted and __ Q will be deasserted. When S and R are both deasserted, the last values of Q and Q will continue to be stored in the cross-coupled structure. Asserting S and R simultaneously can lead to incorrect operation: depending on how S and R are deasserted, the latch may oscillate or become metastable (this is described in more detail in Section C.11). This cross-coupled structure is the basis for more complex memory elements that allow us to store data signals. These elements contain additional gates used to store signal values and to cause the state to be updated only in conjunction with a clock. The next section shows how these elements are built.

Flip-Flops and Latches Flip-flops and latches are the simplest memory elements. In both flip-flops and latches, the output is equal to the value of the stored state inside the element. Furthermore, unlike the S-R latch described above, all the latches and flip-flops we will use from this point on are clocked, which means that they have a clock input and the change of state is triggered by that clock. The difference between a flip-flop and a latch is the point at which the clock causes the state to actually change. In a clocked latch, the state is changed whenever the appropriate inputs change and the clock is asserted, whereas in a flip-flop, the state is changed only on a clock edge. Since throughout this text we use an edge-triggered timing methodology where state is only updated on clock edges, we need only use flip-flops. Flip-flops are often built from latches, so we start by describing the operation of a simple clocked latch and then discuss the operation of a flip-flop constructed from that latch. For computer applications, the function of both flip-flops and latches is to store a signal. A D latch or D flip-flop stores the value of its data input signal in the internal memory. Although there are many other types of latches and flip-flops, the D type is the only basic building block that we will need. A D latch has two inputs and two outputs. The inputs are the data value to be stored (called D) and a clock signal (called C ) that indicates when the latch should read the value on the D input and store it. The outputs are simply the value of the internal state (Q) and

flip-flop A memory element for which the output is equal to the value of the stored state inside the element and for which the internal state is changed only on a clock edge. latch A memory element in which the output is equal to the value of the stored state inside the element and the state is changed whenever the appropriate inputs change and the clock is asserted.

D flip-flop A flip-flop with one data input that stores the value of that input signal in the internal memory when the clock edge occurs.

C-52

Appendix C The Basics of Logic Design

__ its complement (Q). When the clock input C is asserted, the latch is said to be open, and the value of the output (Q) becomes the value of the input D. When the clock input C is deasserted, the latch is said to be closed, and the value of the output (Q) is whatever value was stored the last time the latch was open. Figure C.8.2 shows how a D latch can be implemented with two additional gates added to the cross-coupled NOR gates. Since when the latch is open the value of Q changes as D changes, this structure is sometimes called a transparent latch. Figure C.8.3 shows how this D latch works, assuming that the output Q is initially false and that D changes first. As mentioned earlier, we use flip-flops as the basic building block, rather than latches. Flip-flops are not transparent: their outputs change only on the clock edge. A flip-flop can be built so that it triggers on either the rising (positive) or falling (negative) clock edge; for our designs we can use either type. Figure C.8.4 shows how a falling-edge D flip-flop is constructed from a pair of D latches. In a D flipflop, the output is stored when the clock edge occurs. Figure C.8.5 shows how this flip-flop operates.

C Q

Q D FIGURE C.8.2 A D latch implemented with NOR gates. A NOR gate acts as an inverter if the other input is 0. Thus, the cross-coupled pair of NOR gates acts to store the state value unless the clock input, C, is asserted, in which case the value of input D replaces the value of Q and is stored. The value of input D must be stable when the clock signal C changes from asserted to deasserted.

D

C

Q FIGURE C.8.3 Operation of a D latch, assuming the output is initially deasserted. When the clock, C, is asserted, the latch is open and the Q output immediately assumes the value of the D input.

C-53

C.8 Memory Elements: Flip-Flops, Latches, and Registers

D

D C

D latch

Q

D C

D latch

Q Q

Q Q

C

FIGURE C.8.4 A D flip-flop with a falling-edge trigger. The first latch, called the master, is open and follows the input D when the clock input, C, is asserted. When the clock input, C, falls, the first latch is closed, but the second latch, called the slave, is open and gets its input from the output of the master latch.

D

C

Q FIGURE C.8.5 Operation of a D flip-flop with a falling-edge trigger, assuming the output is initially deasserted. When the clock input (C) changes from asserted to deasserted, the Q output stores the value of the D input. Compare this behavior to that of the clocked D latch shown in Figure C.8.3. In a clocked latch, the stored value and the output, Q, both change whenever C is high, as opposed to only when C transitions.

Here is a Verilog description of a module for a rising-edge D flip-flop, assuming that C is the clock input and D is the data input: module DFF(clock,D,Q,Qbar); input clock, D; output reg Q; // Q is a reg since it is assigned in an always block output Qbar; assign Qbar = ~ Q; // Qbar is always just the inverse of Q always @(posedge clock) // perform actions whenever the clock rises Q = D; endmodule

Because the D input is sampled on the clock edge, it must be valid for a period of time immediately before and immediately after the clock edge. The minimum time that the input must be valid before the clock edge is called the setup time; the

setup time The minimum time that the input to a memory device must be valid before the clock edge.

C-54

Appendix C The Basics of Logic Design

D

Setup time

Hold time

C FIGURE C.8.6 Setup and hold time requirements for a D flip-flop with a falling-edge trigger. The input must be stable for a period of time before the clock edge, as well as after the clock edge. The minimum time the signal must be stable before the clock edge is called the setup time, while the minimum time the signal must be stable after the clock edge is called the hold time. Failure to meet these minimum requirements can result in a situation where the output of the flip-flop may not be predictable, as described in Section C.11. Hold times are usually either 0 or very small and thus not a cause of worry.

hold time The minimum time during which the input must be valid after the clock edge.

minimum time during which it must be valid after the clock edge is called the hold time. Thus the inputs to any flip-flop (or anything built using flip-flops) must be valid during a window that begins at time tsetup before the clock edge and ends at thold after the clock edge, as shown in Figure C.8.6. Section C.11 talks about clocking and timing constraints, including the propagation delay through a flip-flop, in more detail. We can use an array of D flip-flops to build a register that can hold a multibit datum, such as a byte or word. We used registers throughout our datapaths in Chapter 4.

Register Files One structure that is central to our datapath is a register file. A register file consists of a set of registers that can be read and written by supplying a register number to be accessed. A register file can be implemented with a decoder for each read or write port and an array of registers built from D flip-flops. Because reading a register does not change any state, we need only supply a register number as an input, and the only output will be the data contained in that register. For writing a register we will need three inputs: a register number, the data to write, and a clock that controls the writing into the register. In Chapter 4, we used a register file that has two read ports and one write port. This register file is drawn as shown in Figure C.8.7. The read ports can be implemented with a pair of multiplexors, each of which is as wide as the number of bits in each register of the register file. Figure C.8.8 shows the implementation of two register read ports for a 32-bit-wide register file. Implementing the write port is slightly more complex, since we can only change the contents of the designated register. We can do this by using a decoder to generate a signal that can be used to determine which register to write. Figure C.8.9 shows how to implement the write port for a register file. It is important to remember that the flip-flop changes state only on the clock edge. In Chapter 4, we hooked up write signals for the register file explicitly and assumed the clock shown in Figure C.8.9 is attached implicitly. What happens if the same register is read and written during a clock cycle? Because the write of the register file occurs on the clock edge, the register will be

C.8 Memory Elements: Flip-Flops, Latches, and Registers

Read register number 1 Read register number 2 Write register

Register file

Write data

Read data 1

Read data 2

Write

FIGURE C.8.7 A register file with two read ports and one write port has five inputs and two outputs. The control input Write is shown in color.

Read register number 1 Register 0 Register 1 ... Register n – 2

M u

Read data 1

x

Register n – 1

Read register number 2

M u

Read data 2

x

FIGURE C.8.8 The implementation of two read ports for a register file with n registers can be done with a pair of n-to-1 multiplexors, each 32 bits wide. The register read number signal is used as the multiplexor selector signal. Figure C.8.9 shows how the write port is implemented.

C-55

C-56

Appendix C The Basics of Logic Design

Write C

0 1 Register number

Register 0 .. .

n-to-2n decoder

D C Register 1

n–1 n

D .. .

C Register n – 2 D C Register n – 1 Register data

D

FIGURE C.8.9 The write port for a register file is implemented with a decoder that is used with the write signal to generate the C input to the registers. All three inputs (the register number, the data, and the write signal) will have setup and hold-time constraints that ensure that the correct data is written into the register file.

valid during the time it is read, as we saw earlier in Figure C.7.2. The value returned will be the value written in an earlier clock cycle. If we want a read to return the value currently being written, additional logic in the register file or outside of it is needed. Chapter 4 makes extensive use of such logic.

Specifying Sequential Logic in Verilog To specify sequential logic in Verilog, we must understand how to generate a clock, how to describe when a value is written into a register, and how to specify sequential control. Let us start by specifying a clock. A clock is not a predefined object in Verilog; instead, we generate a clock by using the Verilog notation #n before a statement; this causes a delay of n simulation time steps before the execution of the statement. In most Verilog simulators, it is also possible to generate a clock as an external input, allowing the user to specify at simulation time the number of clock cycles during which to run a simulation. The code in Figure C.8.10 implements a simple clock that is high or low for one simulation unit and then switches state. We use the delay capability and blocking assignment to implement the clock.

C.8 Memory Elements: Flip-Flops, Latches, and Registers

reg clock; // clock is a register always #1 clock = 1; #1 clock = 0; FIGURE C.8.10

A specification of a clock.

Next, we must be able to specify the operation of an edge-triggered register. In Verilog, this is done by using the sensitivity list on an always block and specifying as a trigger either the positive or negative edge of a binary variable with the notation posedge or negedge, respectively. Hence, the following Verilog code causes register A to be written with the value b at the positive edge clock: reg [31:0] A; wire [31:0] b; always @(posedge clock) A <= b; module registerfile (Read1,Read2,WriteReg,WriteData,RegWrite, Data1,Data2,clock); input [5:0] Read1,Read2,WriteReg; // the register numbers to read or write input [31:0] WriteData; // data to write input RegWrite, // the write control clock; // the clock to trigger write output [31:0] Data1, Data2; // the register values read reg [31:0] RF [31:0]; // 32 registers each 32 bits long assign Data1 = RF[Read1]; assign Data2 = RF[Read2]; always begin // write the register with new value if Regwrite is high @(posedge clock) if (RegWrite) RF[WriteReg] <= WriteData; end endmodule FIGURE C.8.11 A MIPS register file written in behavioral Verilog. This register file writes on the rising clock edge.

Throughout this chapter and the Verilog sections of Chapter 4, we will assume a positive edge-triggered design. Figure C.8.11 shows a Verilog specification of a MIPS register file that assumes two reads and one write, with only the write being clocked.

C-57

C-58

Appendix C The Basics of Logic Design

Check In the Verilog for the register file in Figure C.8.11, the output ports corresponding to Yourself the registers being read are assigned using a continuous assignment, but the register being written is assigned in an always block. Which of the following is the reason? a. There is no special reason. It was simply convenient. b. Because Data1 and Data2 are output ports and WriteData is an input port. c. Because reading is a combinational event, while writing is a sequential event.

C.9 static random access memory (SRAM) A memory where data is stored statically (as in flip-flops) rather than dynamically (as in DRAM). SRAMs are faster than DRAMs, but less dense and more expensive per bit.

Memory Elements: SRAMs and DRAMs

Registers and register files provide the basic building blocks for small memories, but larger amounts of memory are built using either SRAMs (static random access memories) or DRAMs (dynamic random access memories). We first discuss SRAMs, which are somewhat simpler, and then turn to DRAMs.

SRAMs SRAMs are simply integrated circuits that are memory arrays with (usually) a single access port that can provide either a read or a write. SRAMs have a fixed access time to any datum, though the read and write access characteristics often differ. An SRAM chip has a specific configuration in terms of the number of addressable locations, as well as the width of each addressable location. For example, a 4M × 8 SRAM provides 4M entries, each of which is 8 bits wide. Thus it will have 22 address lines (since 4M = 222), an 8-bit data output line, and an 8-bit single data input line. As with ROMs, the number of addressable locations is often called the height, with the number of bits per unit called the width. For a variety of technical reasons, the newest and fastest SRAMs are typically available in narrow configurations: × 1 and × 4. Figure C.9.1 shows the input and output signals for a 2M × 16 SRAM.

Address

21

Chip select SRAM 2M 3 16

Output enable

16

Dout[15–0]

Write enable Din[15–0]

16

FIGURE C.9.1 A 32K × 8 SRAM showing the 21 address lines (32K = 215) and 16 data inputs, the 3 control lines, and the 16 data outputs.

C.9

Memory Elements: SRAMs and DRAMs

To initiate a read or write access, the Chip select signal must be made active. For reads, we must also activate the Output enable signal that controls whether or not the datum selected by the address is actually driven on the pins. The Output enable is useful for connecting multiple memories to a single-output bus and using Output enable to determine which memory drives the bus. The SRAM read access time is usually specified as the delay from the time that Output enable is true and the address lines are valid until the time that the data is on the output lines. Typical read access times for SRAMs in 2004 varied from about 2–4 ns for the fastest CMOS parts, which tend to be somewhat smaller and narrower, to 8–20 ns for the typical largest parts, which in 2004 had more than 32 million bits of data. The demand for low-power SRAMs for consumer products and digital appliances has grown greatly in the past five years; these SRAMs have much lower stand-by and access power, but usually are 5–10 times slower. Most recently, synchronous SRAMs—similar to the synchronous DRAMs, which we discuss in the next section—have also been developed. For writes, we must supply the data to be written and the address, as well as signals to cause the write to occur. When both the Write enable and Chip select are true, the data on the data input lines is written into the cell specified by the address. There are setup-time and hold-time requirements for the address and data lines, just as there were for D flip-flops and latches. In addition, the Write enable signal is not a clock edge but a pulse with a minimum width requirement. The time to complete a write is specified by the combination of the setup times, the hold times, and the Write enable pulse width. Large SRAMs cannot be built in the same way we build a register file because, unlike a register file where a 32-to-1 multiplexor might be practical, the 64K-to-1 multiplexor that would be needed for a 64K × 1 SRAM is totally impractical. Rather than use a giant multiplexor, large memories are implemented with a shared output line, called a bit line, which multiple memory cells in the memory array can assert. To allow multiple sources to drive a single line, a three-state buffer (or tristate buffer) is used. A three-state buffer has two inputs—a data signal and an Output enable—and a single output, which is in one of three states: asserted, deasserted, or high impedance. The output of a tristate buffer is equal to the data input signal, either asserted or deasserted, if the Output enable is asserted, and is otherwise in a high-impedance state that allows another three-state buffer whose Output enable is asserted to determine the value of a shared output. Figure C.9.2 shows a set of three-state buffers wired to form a multiplexor with a decoded input. It is critical that the Output enable of at most one of the three-state buffers be asserted; otherwise, the three-state buffers may try to set the output line differently. By using three-state buffers in the individual cells of the SRAM, each cell that corresponds to a particular output can share the same output line. The use of a set of distributed three-state buffers is a more efficient implementation than a large centralized multiplexor. The three-state buffers are incorporated into the flip-flops that form the basic cells of the SRAM. Figure C.9.3 shows how a small 4 × 2 SRAM might be built, using D latches with an input called Enable that controls the three-state output.

C-59

C-60

Appendix C The Basics of Logic Design

Select 0 Data 0

Enable In

Select 1 Data 1

Enable In

Select 2 Data 2

Out

Enable In

Select 3 Data 3

Out

Output

Out

Enable In

Out

FIGURE C.9.2 Four three-state buffers are used to form a multiplexor. Only one of the four Select inputs can be asserted. A three-state buffer with a deasserted Output enable has a high-impedance output that allows a three-state buffer whose Output enable is asserted to drive the shared output line.

The design in Figure C.9.3 eliminates the need for an enormous multiplexor; however, it still requires a very large decoder and a correspondingly large number of word lines. For example, in a 4M × 8 SRAM, we would need a 22-to-4M decoder and 4M word lines (which are the lines used to enable the individual flip-flops)! To circumvent this problem, large memories are organized as rectangular arrays and use a two-step decoding process. Figure C.9.4 shows how a 4M × 8 SRAM might be organized internally using a two-step decode. As we will see, the two-level decoding process is quite important in understanding how DRAMs operate. Recently we have seen the development of both synchronous SRAMs (SSRAMs) and synchronous DRAMs (SDRAMs). The key capability provided by synchronous RAMs is the ability to transfer a burst of data from a series of sequential addresses within an array or row. The burst is defined by a starting address, supplied in the usual fashion, and a burst length. The speed advantage of synchronous RAMs comes from the ability to transfer the bits in the burst without having to specify additional address bits. Instead, a clock is used to transfer the successive bits in the burst. The elimination of the need to specify the address for the transfers within the burst significantly improves the rate for transferring the block of data. Because of this capability, synchronous SRAMs and DRAMs are rapidly becoming the RAMs of choice for building memory systems in computers. We discuss the use of synchronous DRAMs in a memory system in more detail in the next section and in Chapter 5.

C.9

Din[1]

Din[1]

D C Write enable

C-61

Memory Elements: SRAMs and DRAMs

D latch

Q

D

D

C

latch

Enable

Enable

D

D

D

D

C

latch

C

latch

Q

0

2-to-4 decoder

Q

Enable

Enable

D

D

D

D

C

latch

C

latch

Q

1

Address

Q

Enable

Q

Enable

2

D C

D latch

Q

Enable

D

D

C

latch

Q

Enable

3

Dout[1]

Dout[0]

FIGURE C.9.3 The basic structure of a 4 × 2 SRAM consists of a decoder that selects which pair of cells to activate. The activated cells use a three-state output connected to the vertical bit lines that supply the requested data. The address that selects the cell is sent on one of a set of horizontal address lines, called word lines. For simplicity, the Output enable and Chip select signals have been omitted, but they could easily be added with a few AND gates.

12 to 4096 decoder 4096

Mux

Dout6

Mux

Dout7

1024

4K " 1024 SRAM

Dout5

Mux

4K " 1024 SRAM

Dout4

Mux

4K " 1024 SRAM

Dout3

Mux

4K " 1024 SRAM

Dout2

Mux

4K " 1024 SRAM

Dout1

Mux

4K " 1024 SRAM

Dout0

Mux

4K " 1024 SRAM

FIGURE C.9.4 Typical organization of a 4M × 8 SRAM as an array of 4K × 1024 arrays. The first decoder generates the addresses for eight 4K × 1024 arrays; then a set of multiplexors is used to select 1 bit from each 1024-bit-wide array. This is a much easier design than a single-level decode that would need either an enormous decoder or a gigantic multiplexor. In practice, a modern SRAM of this size would probably use an even larger number of blocks, each somewhat smaller.

Address [9–0]

Address [21–10]

4K " 1024 SRAM

C-62 Appendix C The Basics of Logic Design

C.9

Memory Elements: SRAMs and DRAMs

DRAMs In a static RAM (SRAM), the value stored in a cell is kept on a pair of inverting gates, and as long as power is applied, the value can be kept indefinitely. In a dynamic RAM (DRAM), the value kept in a cell is stored as a charge in a capacitor. A single transistor is then used to access this stored charge, either to read the value or to overwrite the charge stored there. Because DRAMs use only a single transistor per bit of storage, they are much denser and cheaper per bit. By comparison, SRAMs require four to six transistors per bit. Because DRAMs store the charge on a capacitor, it cannot be kept indefinitely and must periodically be refreshed. That is why this memory structure is called dynamic, as opposed to the static storage in an SRAM cell. To refresh the cell, we merely read its contents and write it back. The charge can be kept for several milliseconds, which might correspond to close to a million clock cycles. Today, single-chip memory controllers often handle the refresh function independently of the processor. If every bit had to be read out of the DRAM and then written back individually, with large DRAMs containing multiple megabytes, we would constantly be refreshing the DRAM, leaving no time for accessing it. Fortunately, DRAMs also use a two-level decoding structure, and this allows us to refresh an entire row (which shares a word line) with a read cycle followed immediately by a write cycle. Typically, refresh operations consume 1% to 2% of the active cycles of the DRAM, leaving the remaining 98% to 99% of the cycles available for reading and writing data. Elaboration: How does a DRAM read and write the signal stored in a cell? The transistor inside the cell is a switch, called a pass transistor, that allows the value stored on the capacitor to be accessed for either reading or writing. Figure C.9.5 shows how the single-transistor cell looks. The pass transistor acts like a switch: when the signal on the word line is asserted, the switch is closed, connecting the capacitor to the bit line. If the operation is a write, then the value to be written is placed on the bit line. If the value is a 1, the capacitor will be charged. If the value is a 0, then the capacitor will be discharged. Reading is slightly more complex, since the DRAM must detect a very small charge stored in the capacitor. Before activating the word line for a read, the bit line is charged to the voltage that is halfway between the low and high voltage. Then, by activating the word line, the charge on the capacitor is read out onto the bit line. This causes the bit line to move slightly toward the high or low direction, and this change is detected with a sense amplifier, which can detect small changes in voltage.

C-63

C-64

Appendix C The Basics of Logic Design

Word line

Pass transistor

Capacitor

Bit line FIGURE C.9.5 A single-transistor DRAM cell contains a capacitor that stores the cell contents and a transistor used to access the cell.

Row decoder 11-to-2048

Address[10–0]

2048 " 2048 array

Column latches

Mux

Dout FIGURE C.9.6 A 4M × 1 DRAM is built with a 2048 × 2048 array. The row access uses 11 bits to select a row, which is then latched in 2048 1-bit latches. A multiplexor chooses the output bit from these 2048 latches. The RAS and CAS signals control whether the address lines are sent to the row decoder or column multiplexor.

C.9

Memory Elements: SRAMs and DRAMs

DRAMs use a two-level decoder consisting of a row access followed by a column access, as shown in Figure C.9.6. The row access chooses one of a number of rows and activates the corresponding word line. The contents of all the columns in the active row are then stored in a set of latches. The column access then selects the data from the column latches. To save pins and reduce the package cost, the same address lines are used for both the row and column address; a pair of signals called RAS (Row Access Strobe) and CAS (Column Access Strobe) are used to signal the DRAM that either a row or column address is being supplied. Refresh is performed by simply reading the columns into the column latches and then writing the same values back. Thus, an entire row is refreshed in one cycle. The two-level addressing scheme, combined with the internal circuitry, make DRAM access times much longer (by a factor of 5–10) than SRAM access times. In 2004, typical DRAM access times ranged from 45 to 65 ns; 256 Mbit DRAMs are in full production, and the first customer samples of 1 GB DRAMs became available in the first quarter of 2004. The much lower cost per bit makes DRAM the choice for main memory, while the faster access time makes SRAM the choice for caches. You might observe that a 64M × 4 DRAM actually accesses 8K bits on every row access and then throws away all but 4 of those during a column access. DRAM designers have used the internal structure of the DRAM as a way to provide higher bandwidth out of a DRAM. This is done by allowing the column address to change without changing the row address, resulting in an access to other bits in the column latches. To make this process faster and more precise, the address inputs were clocked, leading to the dominant form of DRAM in use today: synchronous DRAM or SDRAM. Since about 1999, SDRAMs are the memory chip of choice for most cache-based main memory systems. SDRAMs provide fast access to a series of bits within a row by sequentially transferring all the bits in a burst under the control of a clock signal. In 2004, DDRRAMs (Double Data Rate RAMs), which are called double data rate because they transfer data on both the rising and falling edge of an externally supplied clock, were the most heavily used form of SDRAMs. As we discuss in Chapter 5, these high-speed transfers can be used to boost the bandwidth available out of main memory to match the needs of the processor and caches.

Error Correction Because of the potential for data corruption in large memories, most computer systems use some sort of error-checking code to detect possible corruption of data. One simple code that is heavily used is a parity code. In a parity code the number of 1s in a word is counted; the word has odd parity if the number of 1s is odd and

C-65

C-66

error detection code A code that enables the detection of an error in data, but not the precise location and, hence, correction of the error.

Appendix C The Basics of Logic Design

even otherwise. When a word is written into memory, the parity bit is also written (1 for odd, 0 for even). Then, when the word is read out, the parity bit is read and checked. If the parity of the memory word and the stored parity bit do not match, an error has occurred. A 1-bit parity scheme can detect at most 1 bit of error in a data item; if there are 2 bits of error, then a 1-bit parity scheme will not detect any errors, since the parity will match the data with two errors. (Actually, a 1-bit parity scheme can detect any odd number of errors; however, the probability of having three errors is much lower than the probability of having two, so, in practice, a 1-bit parity code is limited to detecting a single bit of error.) Of course, a parity code cannot tell which bit in a data item is in error. A 1-bit parity scheme is an error detection code; there are also error correction codes (ECC) that will detect and allow correction of an error. For large main memories, many systems use a code that allows the detection of up to 2 bits of error and the correction of a single bit of error. These codes work by using more bits to encode the data; for example, the typical codes used for main memories require 7 or 8 bits for every 128 bits of data. Elaboration: A 1-bit parity code is a distance-2 code, which means that if we look at the data plus the parity bit, no 1-bit change is sufficient to generate another legal combination of the data plus parity. For example, if we change a bit in the data, the parity will be wrong, and vice versa. Of course, if we change 2 bits (any 2 data bits or 1 data bit and the parity bit), the parity will match the data and the error cannot be detected. Hence, there is a distance of two between legal combinations of parity and data. To detect more than one error or correct an error, we need a distance-3 code, which has the property that any legal combination of the bits in the error correction code and the data have at least 3 bits differing from any other combination. Suppose we have such a code and we have one error in the data. In that case, the code plus data will be one bit away from a legal combination, and we can correct the data to that legal combination. If we have two errors, we can recognize that there is an error, but we cannot correct the errors. Let’s look at an example. Here are the data words and a distance-3 error correction code for a 4-bit data item. Data Word

Code bits

Data

Code bits

0000

000

1000

111

0001

011

1001

100

0010

101

1010

010

0011

110

1011

001

0100

110

1100

001

0101

101

1101

010

0110

011

1110

100

0111

000

1111

111

C.10

C-67

Finite-State Machines

To see how this works, let’s choose a data word, say, 0110, whose error correction code is 011. Here are the four 1-bit error possibilities for this data: 1110, 0010, 0100, and 0111. Now look at the data item with the same code (011), which is the entry with the value 0001. If the error correction decoder received one of the four possible data words with an error, it would have to choose between correcting to 0110 or 0001. While these four words with error have only one bit changed from the correct pattern of 0110, they each have two bits that are different from the alternate correction of 0001. Hence, the error correction mechanism can easily choose to correct to 0110, since a single error is a much higher probability. To see that two errors can be detected, simply notice that all the combinations with two bits changed have a different code. The one reuse of the same code is with three bits different, but if we correct a 2-bit error, we will correct to the wrong value, since the decoder will assume that only a single error has occurred. If we want to correct 1-bit errors and detect, but not erroneously correct, 2-bit errors, we need a distance-4 code. Although we distinguished between the code and data in our explanation, in truth, an error correction code treats the combination of code and data as a single word in a larger code (7 bits in this example). Thus, it deals with errors in the code bits in the same fashion as errors in the data bits. While the above example requires n – 1 bits for n bits of data, the number of bits required grows slowly, so that for a distance-3 code, a 64-bit word needs 7 bits and a 128-bit word needs 8. This type of code is called a Hamming code, after R. Hamming, who described a method for creating such codes.

C.10

Finite-State Machines

.

As we saw earlier, digital logic systems can be classified as combinational or sequential. Sequential systems contain state stored in memory elements internal to the system. Their behavior depends both on the set of inputs supplied and on the contents of the internal memory, or state of the system. Thus, a sequential system cannot be described with a truth table. Instead, a sequential system is described as a finite-state machine (or often just state machine). A finite-state machine has a set of states and two functions, called the next-state function and the output function. The set of states corresponds to all the possible values of the internal storage. Thus, if there are n bits of storage, there are 2n states. The next-state function is a combinational function that, given the inputs and the current state, determines the next state of the system. The output function produces a set of outputs from the current state and the inputs. Figure C.10.1 shows this diagrammatically. The state machines we discuss here and in Chapter 4 are synchronous. This means that the state changes together with the clock cycle, and a new state is computed once every clock. Thus, the state elements are updated only on the clock edge. We use this methodology in this section and throughout Chapter 4, and we do not

finite-state machine A sequential logic function consisting of a set of inputs and outputs, a next-state function that maps the current state and the inputs to a new state, and an output function that maps the current state and possibly the inputs to a set of asserted outputs.

next-state function A combinational function that, given the inputs and the current state, determines the next state of a finite-state machine.

C-68

Appendix C The Basics of Logic Design

Next state Current state

Next-state function

Clock Inputs

Output function

Outputs

FIGURE C.10.1 A state machine consists of internal storage that contains the state and two combinational functions: the next-state function and the output function. Often, the output function is restricted to take only the current state as its input; this does not change the capability of a sequential machine, but does affect its internals.

usually show the clock explicitly. We use state machines throughout Chapter 4 to control the execution of the processor and the actions of the datapath. To illustrate how a finite-state machine operates and is designed, let’s look at a simple and classic example: controlling a traffic light. (Chapters 4 and 5 contain more detailed examples of using finite-state machines to control processor execution.) When a finite-state machine is used as a controller, the output function is often restricted to depend on just the current state. Such a finite-state machine is called a Moore machine. This is the type of finite-state machine we use throughout this book. If the output function can depend on both the current state and the current input, the machine is called a Mealy machine. These two machines are equivalent in their capabilities, and one can be turned into the other mechanically. The basic advantage of a Moore machine is that it can be faster, while a Mealy machine may be smaller, since it may need fewer states than a Moore machine. In Chapter 5, we discuss the differences in more detail and show a Verilog version of finite-state control using a Mealy machine. Our example concerns the control of a traffic light at an intersection of a northsouth route and an east-west route. For simplicity, we will consider only the green and red lights; adding the yellow light is left for an exercise. We want the lights to cycle no faster than 30 seconds in each direction, so we will use a 0.033 Hz clock so that the machine cycles between states at no faster than once every 30 seconds. There are two output signals:

C.10

Finite-State Machines

■

NSlite: When this signal is asserted, the light on the north-south road is green; when this signal is deasserted, the light on the north-south road is red.

■

EWlite: When this signal is asserted, the light on the east-west road is green; when this signal is deasserted, the light on the east-west road is red.

In addition, there are two inputs: ■

NScar: Indicates that a car is over the detector placed in the roadbed in front of the light on the north-south road (going north or south).

■

EWcar: Indicates that a car is over the detector placed in the roadbed in front of the light on the east-west road (going east or west).

The traffic light should change from one direction to the other only if a car is waiting to go in the other direction; otherwise, the light should continue to show green in the same direction as the last car that crossed the intersection. To implement this simple traffic light we need two states: ■

NSgreen: The traffic light is green in the north-south direction.

■

EWgreen: The traffic light is green in the east-west direction.

We also need to create the next-state function, which can be specified with a table: Inputs NScar

EWcar

NSgreen

0

0

Next state NSgreen

NSgreen

0

1

EWgreen

NSgreen

1

0

NSgreen

NSgreen

1

1

EWgreen

EWgreen

0

0

EWgreen

EWgreen

0

1

EWgreen

EWgreen

1

0

NSgreen

EWgreen

1

1

NSgreen

Notice that we didn’t specify in the algorithm what happens when a car approaches from both directions. In this case, the next-state function given above changes the state to ensure that a steady stream of cars from one direction cannot lock out a car in the other direction. The finite-state machine is completed by specifying the output function. Before we examine how to implement this finite-state machine, let’s look at a graphical representation, which is often used for finite-state machines. In this representation, nodes are used to indicate states. Inside the node we place a list of the outputs that are active for that state. Directed arcs are used to show the next-state

C-69

C-70

Appendix C The Basics of Logic Design

Outputs NSlite

EWlite

NSgreen

1

0

EWgreen

0

1

function, with labels on the arcs specifying the input condition as logic functions. Figure C.10.2 shows the graphical representation for this finite-state machine. EWcar

NSgreen

EWgreen NSlite

NScar

EWcar

EWlite

NScar

FIGURE C.10.2 The graphical representation of the two-state traffic light controller. We simplified the logic functions on the state transitions. For example, the transition from NSgreen to EWgreen _____ in the next-state table is (NScar · EWcar) + (NScar · EWcar), which is equivalent to EWcar.

A finite-state machine can be implemented with a register to hold the current state and a block of combinational logic that computes the next-state function and the output function. Figure C.10.3 shows how a finite-state machine with 4 bits of state, and thus up to 16 states, might look. To implement the finite-state machine in this way, we must first assign state numbers to the states. This process is called state assignment. For example, we could assign NSgreen to state 0 and EWgreen to state 1. The state register would contain a single bit. The next-state function would be given as ___________

_____

NextState = (CurrentState · EWcar) + (CurrentState · NScar)

C.10

Finite-State Machines

where CurrentState is the contents of the state register (0 or 1) and NextState is the output of the next-state function that will be written into the state register at the end of the clock cycle. The output function is also simple: ___________ NSlite = CurrentState EWlite = CurrentState The combinational logic block is often implemented using structured logic, such as a PLA. A PLA can be constructed automatically from the next-state and output function tables. In fact, there are computer-aided design (CAD) programs

Outputs Combinational logic

Next state

State register

Inputs FIGURE C.10.3 A finite-state machine is implemented with a state register that holds the current state and a combinational logic block to compute the next state and output functions. The latter two functions are often split apart and implemented with two separate blocks of logic, which may require fewer gates.

that take either a graphical or textual representation of a finite-state machine and produce an optimized implementation automatically. In Chapters 4 and 5, finitestate machines were used to control processor execution. Appendix C discusses the detailed implementation of these controllers with both PLAs and ROMs. To show how we might write the control in Verilog, Figure C.10.4 shows a Verilog version designed for synthesis. Note that for this simple control function, a Mealy machine is not useful, but this style of specification is used in Chapter 5 to implement a control function that is a Mealy machine and has fewer states than the Moore machine controller.

C-71

C-72

Appendix C The Basics of Logic Design

module TrafficLite (EWCar,NSCar,EWLite,NSLite,clock); input EWCar, NSCar,clock; output EWLite,NSLite; reg state; initial state=0;

//set initial state

//following two assignments set the output, which is based only on the state variable assign NSLite = ~ state; //NSLite on if state = 0; assign EWLite = state; //EWLite on if state = 1 always @(posedge clock) // all state updates on a positive clock edge case (state) 0: state = EWCar; //change state only if EWCar 1: state = NSCar; //change state only if NSCar endcase endmodule FIGURE C.10.4

Check Yourself

A Verilog version of the traffic light controller.

What is the smallest number of states in a Moore machine for which a Mealy machine could have fewer states? a. Two, since there could be a one-state Mealy machine that might do the same thing. b. Three, since there could be a simple Moore machine that went to one of two different states and always returned to the original state after that. For such a simple machine, a two-state Mealy machine is possible. c. You need at least four states to exploit the advantages of a Mealy machine over a Moore machine.

C.11

Timing Methodologies

Throughout this appendix and in the rest of the text, we use an edge-triggered timing methodology. This timing methodology has an advantage in that it is simpler to explain and understand than a level-triggered methodology. In this section, we explain this timing methodology in a little more detail and also introduce level-sensitive clocking. We conclude this section by briefly discussing the issue

C.11

Timing Methodologies

of asynchronous signals and synchronizers, an important problem for digital designers. The purpose of this section is to introduce the major concepts in clocking methodology. The section makes some important simplifying assumptions; if you are interested in understanding timing methodology in more detail, consult one of the references listed at the end of this appendix. We use an edge-triggered timing methodology because it is simpler to explain and has fewer rules required for correctness. In particular, if we assume that all clocks arrive at the same time, we are guaranteed that a system with edge-triggered registers between blocks of combinational logic can operate correctly without races if we simply make the clock long enough. A race occurs when the contents of a state element depend on the relative speed of different logic elements. In an edgetriggered design, the clock cycle must be long enough to accommodate the path from one flip-flop through the combinational logic to another flip-flop where it must satisfy the setup-time requirement. Figure C.11.1 shows this requirement for a system using rising edge-triggered flip-flops. In such a system the clock period (or cycle time) must be at least as large as tprop + tcombinational + tsetup for the worst-case values of these three delays, which are defined as follows: ■

tprop is the time for a signal to propagate through a flip-flop; it is also sometimes called clock-to-Q.

■

tcombinational is the longest delay for any combinational logic (which by definition is surrounded by two flip-flops).

■

tsetup is the time before the rising clock edge that the input to a flip-flop must be valid.

D

Q Flip-flop

C tprop

D

Combinational logic block tcombinational

Q Flip-flop

C tsetup

FIGURE C.11.1 In an edge-triggered design, the clock must be long enough to allow signals to be valid for the required setup time before the next clock edge. The time for a flipflop input to propagate to the flip-flip outputs is tprop; the signal then takes tcombinational to travel through the combinational logic and must be valid tsetup before the next clock edge.

C-73

C-74

Appendix C The Basics of Logic Design

clock skew The difference in absolute time between the times when two state elements see a clock edge.

We make one simplifying assumption: the hold-time requirements are satisfied, which is almost never an issue with modern logic. One additional complication that must be considered in edge-triggered designs is clock skew. Clock skew is the difference in absolute time between when two state elements see a clock edge. Clock skew arises because the clock signal will often use two different paths, with slightly different delays, to reach two different state elements. If the clock skew is large enough, it may be possible for a state element to change and cause the input to another flip-flop to change before the clock edge is seen by the second flip-flop. Figure C.11.2 illustrates this problem, ignoring setup time and flip-flop propagation delay. To avoid incorrect operation, the clock period is increased to allow for the maximum clock skew. Thus, the clock period must be longer than tprop + tcombinational + tsetup + tskew With this constraint on the clock period, the two clocks can also arrive in the opposite order, with the second clock arriving tskew earlier, and the circuit will work

D Clock arrives at time t

Q Flip-flop

C

Combinational logic block with delay time of ∆

D Clock arrives after t + ∆

Q Flip-flop

C

FIGURE C.11.2 Illustration of how clock skew can cause a race, leading to incorrect operation. Because of the difference in when the two flip-flops see the clock, the signal that is stored into the first flip-flop can race forward and change the input to the second flip-flop before the clock arrives at the second flip-flop.

level-sensitive clocking A timing methodology in which state changes occur at either high or low clock levels but are not instantaneous, as such changes are in edgetriggered designs.

correctly. Designers reduce clock-skew problems by carefully routing the clock signal to minimize the difference in arrival times. In addition, smart designers also provide some margin by making the clock a little longer than the minimum; this allows for variation in components as well as in the power supply. Since clock skew can also affect the hold-time requirements, minimizing the size of the clock skew is important. Edge-triggered designs have two drawbacks: they require extra logic and they may sometimes be slower. Just looking at the D flip-flop versus the level-sensitive latch that we used to construct the flip-flop shows that edge-triggered design requires more logic. An alternative is to use level-sensitive clocking. Because state changes in a level-sensitive methodology are not instantaneous, a level-sensitive scheme is slightly more complex and requires additional care to make it operate correctly.

C.11

C-75

Timing Methodologies

Level-Sensitive Timing In level-sensitive timing, the state changes occur at either high or low levels, but they are not instantaneous as they are in an edge-triggered methodology. Because of the noninstantaneous change in state, races can easily occur. To ensure that a level-sensitive design will also work correctly if the clock is slow enough, designers use two-phase clocking. Two-phase clocking is a scheme that makes use of two nonoverlapping clock signals. Since the two clocks, typically called φ1 and φ2, are nonoverlapping, at most one of the clock signals is high at any given time, as Figure C.11.3 shows. We can use these two clocks to build a system that contains level-sensitive latches but is free from any race conditions, just as the edge-triggered designs were.

Φ1 Φ2

Nonoverlapping periods FIGURE C.11.3 A two-phase clocking scheme showing the cycle of each clock and the nonoverlapping periods.

D Φ1

Q Latch

C

Combinational logic block

D Φ2

Q Latch

C

Combinational logic block

D Φ1

Latch C

FIGURE C.11.4 A two-phase timing scheme with alternating latches showing how the system operates on both clock phases. The output of a latch is stable on the opposite phase from its C input. Thus, the first block of combinational inputs has a stable input during φ2, and its output is latched by φ2. The second (rightmost) combinational block operates in just the opposite fashion, with stable inputs during φ1. Thus, the delays through the combinational blocks determine the minimum time that the respective clocks must be asserted. The size of the nonoverlapping period is determined by the maximum clock skew and the minimum delay of any logic block.

One simple way to design such a system is to alternate the use of latches that are open on φ1 with latches that are open on φ2. Because both clocks are not asserted at the same time, a race cannot occur. If the input to a combinational block is a φ1 clock, then its output is latched by a φ2 clock, which is open only during φ2 when the input latch is closed and hence has a valid output. Figure C.11.4 shows how a system with two-phase timing and alternating latches operates. As in an edgetriggered design, we must pay attention to clock skew, particularly between the two

C-76

Appendix C The Basics of Logic Design

clock phases. By increasing the amount of nonoverlap between the two phases, we can reduce the potential margin of error. Thus, the system is guaranteed to operate correctly if each phase is long enough and if there is large enough nonoverlap between the phases.

Asynchronous Inputs and Synchronizers By using a single clock or a two-phase clock, we can eliminate race conditions if clock-skew problems are avoided. Unfortunately, it is impractical to make an entire system function with a single clock and still keep the clock skew small. While the CPU may use a single clock, I/O devices will probably have their own clock. Chapter 6 described how an asynchronous device may communicate with the CPU through a series of handshaking steps. To translate the asynchronous input to a synchronous signal that can be used to change the state of a system, we need to use a synchronizer, whose inputs are the asynchronous signal and a clock and whose output is a signal synchronous with the input clock. Our first attempt to build a synchronizer uses an edge-triggered D flip-flop, whose D input is the asynchronous signal, as Figure C.11.5 shows. Because we communicate with a handshaking protocol (as we saw in Chapter 6), it does not matter whether we detect the asserted state of the asynchronous signal on one clock or the next, since the signal will be held asserted until it is acknowledged. Thus, you might think that this simple structure is enough to sample the signal accurately, which would be the case except for one small problem.

Asynchronous input

D

Clock

C

Q Flip-flop

Synchronous output

FIGURE C.11.5 A synchronizer built from a D flip-flop is used to sample an asynchronous signal to produce an output that is synchronous with the clock. This “synchronizer” will not work properly!

metastability A situation that occurs if a signal is sampled when it is not stable for the required setup and hold times, possibly causing the sampled value to fall in the indeterminate region between a high and low value.

The problem is a situation called metastability. Suppose the asynchronous signal is transitioning between high and low when the clock edge arrives. Clearly, it is not possible to know whether the signal will be latched as high or low. That problem we could live with. Unfortunately, the situation is worse: when the signal that is sampled is not stable for the required setup and hold times, the flip-flop may go into a metastable state. In such a state, the output will not have a legitimate high or low value, but will be in the indeterminate region between them. Furthermore, the

C.11

flip-flop is not guaranteed to exit this state in any bounded amount of time. Some logic blocks that look at the output of the flip-flop may see its output as 0, while others may see it as 1. This situation is called a synchronizer failure. In a purely synchronous system, synchronizer failure can be avoided by ensuring that the setup and hold times for a flip-flop or latch are always met, but this is impossible when the input is asynchronous. Instead, the only solution possible is to wait long enough before looking at the output of the flip-flop to ensure that its output is stable, and that it has exited the metastable state, if it ever entered it. How long is long enough? Well, the probability that the flip-flop will stay in the metastable state decreases exponentially, so after a very short time the probability that the flip-flop is in the metastable state is very low; however, the probability never reaches 0! So designers wait long enough that the probability of a synchronizer failure is very low, and the time between such failures will be years or even thousands of years. For most flip-flop designs, waiting for a period that is several times longer than the setup time makes the probability of synchronization failure very low. If the clock rate is longer than the potential metastability period (which is likely), then a safe synchronizer can be built with two D flip-flops, as Figure C.11.6 shows. If you are interested in reading more about these problems, look into the references.

Asynchronous input Clock

D

Q

D

synchronizer failure A situation in which a flip-flop enters a metastable state and where some logic blocks reading the output of the flip-flop see a 0 while others see a 1.

Synchronous output

Flip-flop

Flip-flop C

Q

C-77

Timing Methodologies

C

FIGURE C.11.6 This synchronizer will work correctly if the period of metastability that we wish to guard against is less than the clock period. Although the output of the first flip-flop may be metastable, it will not be seen by any other logic element until the second clock, when the second D flip-flop samples the signal, which by that time should no longer be in a metastable state.

Suppose we have a design with very large clock skew—longer than the register propagation time. Is it always possible for such a design to slow the clock down enough to guarantee that the logic operates properly? a. Yes, if the clock is slow enough the signals can always propagate and the design will work, even if the skew is very large. b. No, since it is possible that two registers see the same clock edge far enough apart that a register is triggered, and its outputs propagated and seen by a second register with the same clock edge.

Check Yourself propagation time The time required for an input to a flip-flop to propagate to the outputs of the flip-flop.

C-78

Appendix C The Basics of Logic Design

C.12 field programmable devices (FPD) An integrated circuit containing combinational logic, and possibly memory devices, that are configurable by the end user.

programmable logic device (PLD) An integrated circuit containing combinational logic whose function is configured by the end user.

field programmable gate array (FPGA) A configurable integrated circuit containing both combinational logic blocks and flip-flops.

simple programmable logic device (SPLD) Programmable logic device, usually containing either a single PAL or PLA.

programmable array logic (PAL) Contains a programmable and-plane followed by a fixed or-plane.

antifuse A structure in an integrated circuit that when programmed makes a permanent connection between two wires.

Field Programmable Devices

Within a custom or semicustom chip, designers can make use of the flexibility of the underlying structure to easily implement combinational or sequential logic. How can a designer who does not want to use a custom or semicustom IC implement a complex piece of logic taking advantage of the very high levels of integration available? The most popular component used for sequential and combinational logic design outside of a custom or semicustom IC is a field programmable device (FPD). An FPD is an integrated circuit containing combinational logic, and possibly memory devices, that are configurable by the end user. FPDs generally fall into two camps: programmable logic devices (PLDs), which are purely combinational, and field programmable gate arrays (FPGAs), which provide both combinational logic and flip-flops. PLDs consist of two forms: simple PLDs (SPLDs), which are usually either a PLA or a programmable array logic (PAL), and complex PLDs, which allow more than one logic block as well as configurable interconnections among blocks. When we speak of a PLA in a PLD, we mean a PLA with user programmable and-plane and or-plane. A PAL is like a PLA, except that the or-plane is fixed. Before we discuss FPGAs, it is useful to talk about how FPDs are configured. Configuration is essentially a question of where to make or break connections. Gate and register structures are static, but the connections can be configured. Notice that by configuring the connections, a user determines what logic functions are implemented. Consider a configurable PLA: by determining where the connections are in the and-plane and the or-plane, the user dictates what logical functions are computed in the PLA. Connections in FPDs are either permanent or reconfigurable. Permanent connections involve the creation or destruction of a connection between two wires. Current FPLDs all use an antifuse technology, which allows a connection to be built at programming time that is then permanent. The other way to configure CMOS FPLDs is through an SRAM. The SRAM is downloaded at power-on, and the contents control the setting of switches, which in turn determines which metal lines are connected. The use of SRAM control has the advantage in that the FPD can be reconfigured by changing the contents of the SRAM. The disadvantages of the SRAM-based control are two: the configuration is volatile and must be reloaded on power-on, and the use of active transistors for switches slightly increases the resistance of such connections. FPGAs include both logic and memory devices, usually structured in a twodimensional array with the corridors dividing the rows and columns used for

C.13

Concluding Remarks

global interconnect between the cells of the array. Each cell is a combination of gates and flip-flops that can be programmed to perform some specific function. Because they are basically small, programmable RAMs, they are also called lookup tables (LUTs). Newer FPGAs contain more sophisticated building blocks such as pieces of adders and RAM blocks that can be used to build register files. A few large FPGAs even contain 32-bit RISC cores! In addition to programming each cell to perform a specific function, the interconnections between cells are also programmable, allowing modern FPGAs with hundreds of blocks and hundreds of thousands of gates to be used for complex logic functions. Interconnect is a major challenge in custom chips, and this is even more true for FPGAs, because cells do not represent natural units of decomposition for structured design. In many FPGAs, 90% of the area is reserved for interconnect and only 10% is for logic and memory blocks. Just as you cannot design a custom or semicustom chip without CAD tools, you also need them for FPDs. Logic synthesis tools have been developed that target FPGAs, allowing the generation of a system using FPGAs from structural and behavioral Verilog.

C.13

Concluding Remarks

This appendix introduces the basics of logic design. If you have digested the material in this appendix, you are ready to tackle the material in Chapters 4 and 5, both of which use the concepts discussed in this appendix extensively. Key

Further Reading There are a number of good texts on logic design. Here are some you might like to look into. Ciletti, M. D. [2002]. Advanced Digital Design with the Verilog HDL, Englewood Cliffs, NJ: Prentice Hall. A thorough book on logic design using Verilog. Katz, R. H. [2004]. Modern Logic Design, 2nd ed., Reading, MA: Addison-Wesley. A general text on logic design. Wakerly, J. F. [2000]. Digital Design: Principles and Practices, 3rd ed., Englewood Cliffs, NJ: Prentice Hall. A general text on logic design.

C-79

lookup tables (LUTs) In a field programmable device, the name given to the cells because they consist of a small amount of logic and RAM.

C-80

Appendix C The Basics of Logic Design

C.14

Exercises

C.1 [10] <§C.2> In addition to the basic laws we discussed in this section, there are two important theorems, called DeMorgan’s theorems: _____

__ _

____

__

_

A + B = A · B and A · B = A + B

Prove DeMorgan’s theorems with a truth table of the form __

__

______

0

1

1

1

1

1

1

1

1

0

0

0

1

1

1

0

0

1

0

0

1

1

1

1

0

0

0

0

0

0

A

B

0 0

A

B

A+B

__

__

A·B

______

A · B

__

__

A+B

C.2 [15] <§C.2> Prove that the two equations for E in the example starting on page C-7 are equivalent by using DeMorgan’s theorems and the axioms shown on page C-7. C.3 [10] <§C.2> Show that there are 2n entries in a truth table for a function with n inputs. C.4 [10] <§C.2> One logic function that is used for a variety of purposes (including within adders and to compute parity) is exclusive OR. The output of a twoinput exclusive OR function is true only if exactly one of the inputs is true. Show the truth table for a two-input exclusive OR function and implement this function using AND gates, OR gates, and inverters. C.5 [15] <§C.2> Prove that the NOR gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NOR gate. C.6 [15] <§C.2> Prove that the NAND gate is universal by showing how to build the AND, OR, and NOT functions using a two-input NAND gate. C.7 [10] <§§C.2, C.3> Construct the truth table for a four-input odd-parity function (see page C-65 for a description of parity). C.8 [10] <§§C.2, C.3> Implement the four-input odd-parity function with AND and OR gates using bubbled inputs and outputs. C.9 [10] <§§C.2, C.3> Implement the four-input odd-parity function with a PLA.

C.14

Exercises

C.10 [15] <§§C.2, C.3> Prove that a two-input multiplexor is also universal by showing how to build the NAND (or NOR) gate using a multiplexor. C.11 [5] <§§4.2, C.2, C.3> Assume that X consists of 3 bits, x2 x1 x0. Write four logic functions that are true if and only if ■

X contains only one 0

■

X contains an even number of 0s

■

X when interpreted as an unsigned binary number is less than 4

■

X when interpreted as a signed (two’s complement) number is negative

C.12 [5] <§§4.2, C.2, C.3> Implement the four functions described in Exercise C.11 using a PLA. C.13 [5] <§§4.2, C.2, C.3> Assume that X consists of 3 bits, x2 x1 x0, and Y consists of 3 bits, y2 y1 y0. Write logic functions that are true if and only if ■

X < Y, where X and Y are thought of as unsigned binary numbers

■

X < Y, where X and Y are thought of as signed (two’s complement) numbers

■

X=Y

Use a hierarchical approach that can be extended to larger numbers of bits. Show how can you extend it to 6-bit comparison. C.14 [5] <§§C.2, C.3> Implement a switching network that has two data inputs (A and B), two data outputs (C and D), and a control input (S). If S equals 1, the network is in pass-through mode, and C should equal A, and D should equal B. If S equals 0, the network is in crossing mode, and C should equal B, and D should equal A. C.15 [15] <§§C.2, C.3> Derive the product-of-sums representation for E shown on page C-11 starting with the sum-of-products representation. You will need to use DeMorgan’s theorems. C.16 [30] <§§C.2, C.3> Give an algorithm for constructing the sum-of-products representation for an arbitrary logic equation consisting of AND, OR, and NOT. The algorithm should be recursive and should not construct the truth table in the process. C.17 [5] <§§C.2, C.3> Show a truth table for a multiplexor (inputs A, B, and S; output C ), using don’t cares to simplify the table where possible.

C-81

C-82

Appendix C The Basics of Logic Design

C.18 [5] <§C.3> What is the function implemented by the following Verilog

modules: module FUNC1 (I0, I1, S, out); input I0, I1; input S; output out; out = S? I1: I0; endmodule module FUNC2 (out,ctl,clk,reset); output [7:0] out; input ctl, clk, reset; reg [7:0] out; always @(posedge clk) if (reset) begin out <= 8'b0 ; end else if (ctl) begin out <= out + 1; end else begin out <= out - 1; end endmodule

C.19 [5] <§C.4> The Verilog code on page C-53 is for a D flip-flop. Show the Verilog code for a D latch. C.20 [10] <§§ C.3, C.4> Write down a Verilog module implementation of a 2-to-4 decoder (and/or encoder). C.21 [10] <§§C.3, C.4> Given the following logic diagram for an accumulator,

write down the Verilog module implementation of it. Assume a positive edgetriggered register and asynchronous Rst.

C.14

In

Exercises

!

Adder 16

16

Load Clk

Out

Rst Register Load

C.22 [20] <§§C.3, C.4, C.5> Section 3.3 presents basic operation and possible implementations of multipliers. A basic unit of such implementations is a shiftand-add unit. Show a Verilog implementation for this unit. Show how can you use this unit to build a 32-bit multiplier. C.23 [20] <§§C.3, C.4, C.5> Repeat Exercise C.22, but for an unsigned divider rather than a multiplier. C.24 [15] <§C.5> The ALU supported set on less than (slt) using just the sign bit of the adder. Let’s try a set on less than operation using the values −7ten and 6ten. To make it simpler to follow the example, let’s limit the binary representations to 4 bits: 1001two and 0110two. 1001two – 0110two = 1001two + 1010two = 0011two

This result would suggest that −7 > 6, which is clearly wrong. Hence, we must factor in overflow in the decision. Modify the 1-bit ALU in Figure C.5.10 on page C-33 to handle slt correctly. Make your changes on a photocopy of this figure to save time. C.25 [20] <§C.6> A simple check for overflow during addition is to see if the CarryIn to the most significant bit is not the same as the CarryOut of the most significant bit. Prove that this check is the same as in Figure 3.5 on page 232. C.26 [5] <§C.6> Rewrite the equations on page C-44 for a carry-lookahead logic for a 16-bit adder using a new notation. First, use the names for the CarryIn signals of the individual bits of the adder. That is, use c4, c8, c12, . . . instead of C1, C2, C3, . . . . In addition, let Pi, j mean a propagate signal for bits i to j, and Gi, j mean a generate signal for bits i to j. For example, the equation

C2 = G1 + (P1 · G0) + (P1 · P0 · c0)

C-83

C-84

Appendix C The Basics of Logic Design

can be rewritten as c8 = G7, 4 + (P7, 4 · G3, 0) + (P7, 4 · P3, 0 · c 0) This more general notation is useful in creating wider adders. C.27 [15] <§C.6> Write the equations for the carry-lookahead logic for a 64-bit adder using the new notation from Exercise C.26 and using 16-bit adders as building blocks. Include a drawing similar to Figure C.6.3 in your solution. C.28 [10] <§C.6> Now calculate the relative performance of adders. Assume that

hardware corresponding to any equation containing only OR or AND terms, such as the equations for pi and gi on page C-40, takes one time unit T. Equations that consist of the OR of several AND terms, such as the equations for c1, c2, c3, and c4 on page C-40, would thus take two time units, 2T. The reason is it would take T to produce the AND terms and then an additional T to produce the result of the OR. Calculate the numbers and performance ratio for 4-bit adders for both ripple carry and carry lookahead. If the terms in equations are further defined by other equations, then add the appropriate delays for those intermediate equations, and continue recursively until the actual input bits of the adder are used in an equation. Include a drawing of each adder labeled with the calculated delays and the path of the worst-case delay highlighted. C.29 [15] <§C.6> This exercise is similar to Exercise C.28, but this time calculate

the relative speeds of a 16-bit adder using ripple carry only, ripple carry of 4-bit groups that use carry lookahead, and the carry-lookahead scheme on page C-39. C.30 [15] <§C.6> This exercise is similar to Exercises C.28 and C.29, but this time

calculate the relative speeds of a 64-bit adder using ripple carry only, ripple carry of 4-bit groups that use carry lookahead, ripple carry of 16-bit groups that use carry lookahead, and the carry-lookahead scheme from Exercise C.27. C.31 [10] <§C.6> Instead of thinking of an adder as a device that adds two num-

bers and then links the carries together, we can think of the adder as a hardware device that can add three inputs together (ai, bi, ci) and produce two outputs (s, ci + 1). When adding two numbers together, there is little we can do with this observation. When we are adding more than two operands, it is possible to reduce the cost of the carry. The idea is to form two independent sums, called S′ (sum bits) and C′ (carry bits). At the end of the process, we need to add C′ and S′ together using a normal adder. This technique of delaying carry propagation until the end of a sum of numbers is called carry save addition. The block drawing on the lower right of Figure C.14.1 shows the organization, with two levels of carry save adders connected by a single normal adder. Calculate the delays to add four 16-bit numbers using full carry-lookahead adders versus carry save with a carry-lookahead adder forming the final sum. (The time unit T in Exercise C.28 is the same.)

C.14

a3 b3

a2 b2

a1 b1

a0 b0 A

1

1 e3

f3

s5

s4

s3

1

f1

1

1

a3

1 a2

1 a1

Traditional adder

S

s0

s1

b3 e3 f3 b2 e2 f2 b1 e1 f1 b0 e0 f0

1

Traditional adder

f0

1

s2

E

Traditional adder

e0

1

f2

1

1

e1

1

1

B

1

1

e2

A

B

E

F

Carry save adder

1 a0

Carry save adder 1 s'4 c'3

s'3 c'2

1

1

s'2 c'1

s'1 c'0

1

C'

S'

s'0 Traditional adder

1

1

1

1

s4

s3

s2

s1

S s5

C-85

Exercises

s0

FIGURE C.14.1 Traditional ripple carry and carry save addition of four 4-bit numbers. The details are shown on the left, with the individual signals in lowercase, and the corresponding higher-level blocks are on the right, with collective signals in uppercase. Note that the sum of four n-bit numbers can take n + 2 bits.

C.32 [20] <§C.6> Perhaps the most likely case of adding many numbers at once

in a computer would be when trying to multiply more quickly by using many adders to add many numbers in a single clock cycle. Compared to the multiply algorithm in Chapter 3, a carry save scheme with many adders could multiply more than 10 times faster. This exercise estimates the cost and speed of a combinational multiplier to multiply two positive 16-bit numbers. Assume that you have 16 intermediate terms M15, M14, . . . , M0, called partial products, that contain the multiplicand ANDed with multiplier bits m15, m14, . . ., m0. The idea is to use carry save adders to reduce the n operands into 2n/3 in parallel groups of three, and do this repeatedly until you get two large numbers to add together with a traditional adder.

F

C-86

Appendix C The Basics of Logic Design

First, show the block organization of the 16-bit carry save adders to add these 16 terms, as shown on the right in Figure C.14.1. Then calculate the delays to add these 16 numbers. Compare this time to the iterative multiplication scheme in Chapter 3 but only assume 16 iterations using a 16-bit adder that has full carry lookahead whose speed was calculated in Exercise C.29. C.33 [10] <§C.6> There are times when we want to add a collection of numbers

together. Suppose you wanted to add four 4-bit numbers (A, B, E, F) using 1-bit full adders. Let’s ignore carry lookahead for now. You would likely connect the 1-bit adders in the organization at the top of Figure C.14.1. Below the traditional organization is a novel organization of full adders. Try adding four numbers using both organizations to convince yourself that you get the same answer. C.34 [5] <§C.6> First, show the block organization of the 16-bit carry save adders

to add these 16 terms, as shown in Figure C.14.1. Assume that the time delay through each 1-bit adder is 2T. Calculate the time of adding four 4-bit numbers to the organization at the top versus the organization at the bottom of Figure C.14.1. C.35 [5] <§C.8> Quite often, you would expect that given a timing diagram con-

taining a description of changes that take place on a data input D and a clock input C (as in Figures C.8.3 and C.8.6 on pages C-52 and C-54, respectively), there would be differences between the output waveforms (Q) for a D latch and a D flip-flop. In a sentence or two, describe the circumstances (e.g., the nature of the inputs) for which there would not be any difference between the two output waveforms. C.36 [5] <§C.8> Figure C.8.8 on page C-55 illustrates the implementation of the

register file for the MIPS datapath. Pretend that a new register file is to be built, but that there are only two registers and only one read port, and that each register has only 2 bits of data. Redraw Figure C.8.8 so that every wire in your diagram corresponds to only 1 bit of data (unlike the diagram in Figure C.8.8, in which some wires are 5 bits and some wires are 32 bits). Redraw the registers using D flip-flops. You do not need to show how to implement a D flip-flop or a multiplexor. C.37 [10] <§C.10> A friend would like you to build an “electronic eye” for use

as a fake security device. The device consists of three lights lined up in a row, controlled by the outputs Left, Middle, and Right, which, if asserted, indicate that a light should be on. Only one light is on at a time, and the light “moves” from left to right and then from right to left, thus scaring away thieves who believe that the device is monitoring their activity. Draw the graphical representation for the finite-state machine used to specify the electronic eye. Note that the rate of the eye’s movement will be controlled by the clock speed (which should not be too great) and that there are essentially no inputs. C.38 [10] <§C.10> {Ex. C.37} Assign state numbers to the states of the finite-state

machine you constructed for Exercise C.37 and write a set of logic equations for each of the outputs, including the next-state bits.

C.14

Exercises

C-87

C.39 [15] <§§C.2, C.8, C.10> Construct a 3-bit counter using three D flip-flops and a selection of gates. The inputs should consist of a signal that resets the counter to 0, called reset, and a signal to increment the counter, called inc. The outputs should be the value of the counter. When the counter has value 7 and is incremented, it should wrap around and become 0. C.40 [20] <§C.10> A Gray code is a sequence of binary numbers with the property

that no more than 1 bit changes in going from one element of the sequence to another. For example, here is a 3-bit binary Gray code: 000, 001, 011, 010, 110, 111, 101, and 100. Using three D flip-flops and a PLA, construct a 3-bit Gray code counter that has two inputs: reset, which sets the counter to 000, and inc, which makes the counter go to the next value in the sequence. Note that the code is cyclic, so that the value after 100 in the sequence is 000. C.41 [25] <§C.10> We wish to add a yellow light to our traffic light example on page C-68. We will do this by changing the clock to run at 0.25 Hz (a 4-second clock cycle time), which is the duration of a yellow light. To prevent the green and red lights from cycling too fast, we add a 30-second timer. The timer has a single input, called TimerReset, which restarts the timer, and a single output, called TimerSignal, which indicates that the 30-second period has expired. Also, we must redefine the traffic signals to include yellow. We do this by defining two output signals for each light: green and yellow. If the output NS green is asserted, the green light is on; if the output NSyellow is asserted, the yellow light is on. If both signals are off, the red light is on. Do not assert both the green and yellow signals at the same time, since American drivers will certainly be confused, even if European drivers understand what this means! Draw the graphical representation for the finite-state machine for this improved controller. Choose names for the states that are different from the names of the outputs. C.42 [15] <§C.10> {Ex. C.41} Write down the next-state and output-function tables for the traffic light controller described in Exercise C.41. C.43 [15] <§§C.2, C.10> {Ex. C.42} Assign state numbers to the states in the traffic light example of Exercise C.41 and use the tables of Exercise C.42 to write a set of logic equations for each of the outputs, including the next-state outputs. C.44 [15] <§§C.3, C.10> {Ex. C.43} Implement the logic equations of Exercise C.43 as a PLA.

§C.2, page C-8: No. If A = 1, C = 1, B = 0, the first is true, but the second is false. §C.3, page C-20: C. §C.4, page C-22: They are all exactly the same. §C.4, page C-26: A = 0, B = 1. §C.5, page C-38: 2. §C.6, page C-47: 1. §C.8, page C-58: c. §C.10, page C-72: b. §C.11, page C-77: b.

Answers to Check Yourself

D A

P

P

E

N

D

I

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. Jim McKevit, et al. 8086 design report, 1997

X

Mapping Control to Hardware D.1

Introduction D-3

D.2

Implementing Combinational Control Units D-4

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

Concluding Remarks 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 singlecycle 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.

D.2

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 computeraided 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.3. 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 Operation3. 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

ALUOp

Implementing Combinational Control Units

Funct field

Operation

ALUOp1

ALUOp0

F5

F4

F3

F2

F1

F0

0

0

X

X

X

X

X

X

0010

0

1

X

X

X

X

X

X

0110

1

0

X

X

0

0

0

0

0010

1

X

X

X

0

0

1

0

0110

1

0

X

X

0

1

0

0

0000

1

0

X

X

0

1

0

1

0001

1

X

X

X

1

0

1

0

0111

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.

ALUOp

Function code fields

ALUOp1

ALUOp0

F5

F4

F3

F2

F1

F0

0

1

X

X

X

X

X

X

1

X

X

X

X

X

1

X

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)

ALUOp

Function code fields

ALUOp1

ALUOp0

F5

F4

F3

F2

F1

0

X

X

X

X

X

X

F0 X

X

X

X

X

X

0

X

X

b. The truth table for Operation1 = 1

ALUOp

Function code fields

ALUOp1

ALUOp0

F5

F4

F3

F2

F1

F0

1

X

X

X

X

X

X

1

1

X

X

X

1

X

X

X

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 Operation3=1 because it is always set to 0 in Figure D.2.1. See Appendix C for more background on don’t cares.

D-5

D-6

Appendix D Mapping Control to Hardware

ALUOp ALU control block ALUOp0 ALUOp1

F3 F (5–0)

F2 F1

Operation3

Operation2 Operation1

Operation

Operation0

F0

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 C, 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 C.) 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

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.

Control

Inputs

Outputs

Signal name

R-format

lw

sw

beq

Op5

0

1

1

0

Op4

0

0

0

0

Op3

0

0

1

0

Op2

0

0

0

1

Op1

0

1

1

0

Op0

0

1

1

0

RegDst

1

0

X

X

ALUSrc

0

1

1

0

MemtoReg

0

1

X

X

RegWrite

1

1

0

0

MemRead

0

1

0

0

MemWrite

0

0

1

0

Branch

0

0

0

1

ALUOp1

1

0

0

0

ALUOp0

0

0

0

1

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-7

D-8

Appendix D Mapping Control to Hardware

Inputs Op5 Op4 Op3 Op2 Op1 Op0

Outputs R-format

Iw

sw

beq

RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp1 ALUOp0

FIGURE D.2.5 The structured implementation of the control function as described by the 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.

D.3

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

MemRead ALUSrcA = 0 IorD = 0 IRWrite ALUSrcB = 01 ALUOp = 00 PCWrite PCSource = 00

(Op

= 'L

Execution 8 ALUSrcA = 1 ALUSrcB = 00 ALUOp = 10

Branch completion

(Op = 'LW')

p = ')

W

'S

3

Memory access

5 MemRead IorD = 1

R-type completion 7

MemWrite IorD = 1

RegDst = 1 RegWrite MemtoReg = 0

Write-back step

RegDst = 0 RegWrite MemtoReg = 1

FIGURE D.3.1

The finite-state diagram for multicycle control.

EQ ')

ALUSrcA = 1 ALUSrcB = 00 ALUOp = 01 PCWriteCond PCSource = 01

(O

Memory access

'B

(O

')

6

e)

-typ

R p=

'SW

ALUSrcA = 1 ALUSrcB = 10 ALUOp = 00

4

ALUSrcA = 0 ALUSrcB = 11 ALUOp = 00

(Op = 'J')

or W')

= (Op

1

=

Start

2

Instruction decode/ register fetch

Instruction fetch

0

Memory address computation

D-9

Implementing Finite-State Machine Control

(O p

D.3

Jump completion

9 PCWrite PCSource = 10

Appendix D Mapping Control to Hardware

PCWrite PCWriteCond IorD MemRead MemWrite IRWrite

Control logic

MemtoReg PCSource Outputs

ALUOp ALUSrcB ALUSrcA RegWrite RegDst NS3 NS2 NS1 NS0

S0

S1

S2

S3

Op0

Op1

Op2

Op3

Op4

Inputs

Op5

D-10

State register

Instruction register opcode field

FIGURE D.3.2 The control unit for MIPS will consist of some control logic and a register to hold the state. The state register is written at the active clock edge and is stable during the clock cycle.

the 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.

D.3

Implementing Finite-State Machine Control

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

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

Op

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-11

D-12

Appendix D Mapping Control to Hardware

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

EXAMPLE ANSWER

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

NextState5 = State2 × (Op[5-0]=sw) __ __ __ __

Implementing Finite-State Machine Control

___

___

= 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 datapath 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-13

D-14

Appendix D Mapping Control to Hardware

s3

s2

s1

s0

s3

s2

s1

s0

0

0

0

0

1

0

0

0

1

0

0

1

a. Truth table for PCWrite

b. Truth table for PCWriteCond

s3

s2

s1

s0

0

0

1

1

0

1

0

1

c. Truth table for IorD

s3

s2

s1

s0

s3

s2

s1

s0

s3

s2

s1

s0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

1

1

d. Truth table for MemRead

e. Truth table for MemWrite

f. Truth table for IRWrite

s3

s2

s1

s0

s3

s2

s1

s0

s3

s2

s1

s0

0

1

0

0

1

0

0

1

1

0

0

0

g. Truth table for MemtoReg

h. Truth table for PCSource1

i. Truth table for PCSource0

s3

s2

s1

s0

s3

s2

s1

s0

0

1

1

0

1

0

0

0

j. Truth table for ALUOp1

k. Truth table for ALUOp0

s3

s2

s1

s0

0

0

0

1

0

0

1

0

l. Truth table for ALUSrcB1

s3

s2

s1

s0

s3

s2

s1

s0

s3

s2

s1

s0

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

0

0

m. Truth table for ALUSrcB0

n. Truth table for ALUSrcA

s3

s2

s1

s0

0

1

1

1

o. Truth table for RegWrite

p. Truth table for RegDst

FIGURE D.3.4 The truth tables are shown for the 16 datapath control signals that depend only on the current-state input bits, which are shown for each table. Each truth table row corresponds to 64 entries: one for each possible value of the six Op bits. Notice that some of the outputs are active under nearly the same circumstances. For example, in the case of PCWriteCond, PCSource0, and ALUOp0, these signals are active only in state 8 (see b, i, and k). These three signals could be replaced by one signal. There are other opportunities for reducing the logic needed to implement the control function by taking advantage of further similarities in the truth tables.

D.3

Implementing Finite-State Machine Control

Op5

Op4

Op3

Op2

Op1

Op0

S3

S2

S1

S0

0

0

0

0

1

0

0

0

0

1

0

0

0

1

0

0

0

0

0

1

a. The truth table for the NS3 output, active when the next state is 8 or 9. This signal is activated when the current state is 1.

Op5

Op4

Op3

Op2

Op1

Op0

S3

S2

S1

S0

0

0

0

0

0

0

0

0

0

1

1

0

1

0

1

1

0

0

1

0

X

X

X

X

X

X

0

0

1

1

X

X

X

X

X

X

0

1

1

0

b. The truth table for the NS2 output, which is active when the next state is 4, 5, 6, or 7. This situation occurs when the current state is one of 1, 2, 3, or 6.

Op5

Op4

Op3

Op2

Op1

Op0

S3

S2

S1

S0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

1

1

0

0

0

1

1

0

1

0

1

1

0

0

0

1

1

0

0

0

1

1

0

0

1

0

X

X

X

X

X

X

0

1

1

0

c. The truth table for the NS1 output, which is active when the next state is 2, 3, 6, or 7. The next state is one of 2, 3, 6, or 7 only if the current state is one of 1, 2, or 6.

Op5

Op4

Op3

Op2

Op1

Op0

S3

S2

S1

S0

X

X

X

X

X

X

0

0

0

0

1

0

0

0

1

1

0

0

1

0

1

0

1

0

1

1

0

0

1

0

X

X

X

X

X

X

0

1

1

0

0

0

0

0

1

0

0

0

0

1

d. The truth table for the NS0 output, which is active when the next state is 1, 3, 5, 7, or 9. This happens only if the current state is one of 0, 1, 2, or 6.

FIGURE D.3.5 The four truth tables for the four next-state output bits (NS[3–0]). The next-state outputs depend on the value of Op[5–0], which is the opcode field, and the current state, given by S[3–0]. The entries with X are don’t-care terms. Each entry with a don’t-care term corresponds to two entries, one with that input at 0 and one with that input at 1. Thus an entry with n don’t-care terms actually corresponds to 2n truth table entries.

A ROM Implementation Probably the simplest way to implement the control function is to encode the truth tables in a read-only memory (ROM). The number of entries in the memory for the truth tables of Figures D.3.4 and D.3.5 is equal to all possible values of the inputs

D-15

D-16

Appendix D Mapping Control to Hardware

(the 6 opcode bits plus the 4 state bits), which is 2# inputs = 210 = 1024. The inputs to the control unit become the address lines for the ROM, which implements the control logic block that was shown in Figure D.3.2. The width of each entry (or word in the memory) is 20 bits, since there are 16 datapath control outputs and 4 next-state bits. This means the total size of the ROM is 210 × 20 = 20 Kbits. The setting of the bits in a word in the ROM depends on which outputs are active in that word. Before we look at the control words, we need to order the bits within the control input (the address) and output words (the contents), respectively. We will number the bits using the order in Figure D.3.2, with the next-state bits being the low-order bits of the control word and the current-state input bits being the low-order bits of the address. This means that the PCWrite output will be the highorder bit (bit 19) of each memory word, and NS0 will be the low-order bit. The high-order address bit will be given by Op5, which is the high-order bit of the instruction, and the low-order address bit will be given by S0. We can construct the ROM contents by building the entire truth table in a form where each row corresponds to one of the 2n unique input combinations, and a set of columns indicates which outputs are active for that input combination. We don’t have the space here to show all 1024 entries in the truth table. However, by separating the datapath control and next-state outputs, we do, since the datapath control outputs depend only on the current state. The truth table for the datapath control outputs is shown in Figure D.3.6. We include only the encodings of the state inputs that are in use (that is, values 0 through 9 corresponding to the 10 states of the state machine). The truth table in Figure D.3.6 directly gives the contents of the upper 16 bits of each word in the ROM. The 4-bit input field gives the low-order 4 address bits of each word, and the column gives the contents of the word at that address. If we did show a full truth table for the datapath control bits with both the state number and the opcode bits as inputs, the opcode inputs would all be don’t cares. When we construct the ROM, we cannot have any don’t cares, since the addresses into the ROM must be complete. Thus, the same datapath control outputs will occur many times in the ROM, since this part of the ROM is the same whenever the state bits are identical, independent of the value of the opcode inputs.

Control ROM Entries

EXAMPLE

For what ROM addresses will the bit corresponding to PCWrite, the high bit of the control word, be 1?

D.3

Outputs

Implementing Finite-State Machine Control

D-17

Input values (S[3–0]) 0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

PCWrite

1

0

0

0

0

0

0

0

0

1

PCWriteCond

0

0

0

0

0

0

0

0

1

0

IorD

0

0

0

1

0

1

0

0

0

0

MemRead

1

0

0

1

0

0

0

0

0

0

MemWrite

0

0

0

0

0

1

0

0

0

0

IRWrite

1

0

0

0

0

0

0

0

0

0

MemtoReg

0

0

0

0

1

0

0

0

0

0

PCSource1

0

0

0

0

0

0

0

0

0

1

PCSource0

0

0

0

0

0

0

0

0

1

0

ALUOp1

0

0

0

0

0

0

1

0

0

0

ALUOp0

0

0

0

0

0

0

0

0

1

0

ALUSrcB1

0

1

1

0

0

0

0

0

0

0

ALUSrcB0

1

1

0

0

0

0

0

0

0

0

ALUSrcA

0

0

1

0

0

0

1

0

1

0

RegWrite

0

0

0

0

1

0

0

1

0

0

RegDst

0

0

0

0

0

0

0

1

0

0

FIGURE D.3.6 The truth table for the 16 datapath control outputs, which depend only on the state inputs. The values are determined from Figure D.3.4. Although there are 16 possible values for the 4-bit state field, only ten of these are used and are shown here. The ten possible values are shown at the top; each column shows the setting of the datapath control outputs for the state input value that appears at the top of the column. For example, when the state inputs are 0011 (state 3), the active datapath control outputs are IorD or MemRead.

PCWrite is high in states 0 and 9; this corresponds to addresses with the 4 loworder bits being either 0000 or 1001. The bit will be high in the memory word independent of the inputs Op[5–0], so the addresses with the bit high are 000000000, 0000001001, 0000010000, 0000011001, . . . , 1111110000, 1111111001. The general form of this is XXXXXX0000 or XXXXXX1001, where XXXXXX is any combination of bits, and corresponds to the 6-bit opcode on which this output does not depend.

ANSWER

D-18

Appendix D Mapping Control to Hardware

We will show the entire contents of the ROM in two parts to make it easier to show. Figure D.3.7 shows the upper 16 bits of the control word; this comes directly from Figure D.3.6. These datapath control outputs depend only on the state inputs, and this set of words would be duplicated 64 times in the full ROM, as we discussed above. The entries corresponding to input values 1010 through 1111 are not used, so we do not care what they contain. Figure D.3.8 shows the lower four bits of the control word corresponding to the next-state outputs. The last column of the table in Figure D.3.8 corresponds to all the possible values of the opcode that do not match the specified opcodes. In state 0, the next state is always state 1, since the instruction was still being fetched. After state 1, the opcode field must be valid. The table indicates this by the entries marked illegal; we discuss how to deal with these illegal opcodes in Section 4.9. Not only is this representation as two separate tables a more compact way to show the ROM contents, it is also a more efficient way to implement the ROM. The majority of the outputs (16 of 20 bits) depends only on 4 of the 10 inputs. The number of bits in total when the control is implemented as two separate ROMs is 24 × 16 + 210 × 4 = 256 + 4096 = 4.3 Kbits, which is about one-fifth of the size of a single ROM, which requires 210 × 20 = 20 Kbits. There is some overhead associated with any structured-logic block, but in this case the additional overhead of an extra ROM would be much smaller than the savings from splitting the single ROM. Lower 4 bits of the address

Bits 19–4 of the word

0000

1001010000001000

0001

0000000000011000

0010

0000000000010100

0011

0011000000000000

0100

0000001000000010

0101

0010100000000000

0110

0000000001000100

0111

0000000000000011

1000

0100000010100100

1001

1000000100000000

FIGURE D.3.7 The contents of the upper 16 bits of the ROM depend only on the state inputs. These values are the same as those in Figure D.3.6, simply rotated 90°. This set of control words would be duplicated 64 times for every possible value of the upper six bits of the address.

D.3

Implementing Finite-State Machine Control

Although this ROM encoding of the control function is simple, it is wasteful, even when divided into two pieces. For example, the values of the Instruction register inputs are often not needed to determine the next state. Thus, the next-state ROM has many entries that are either duplicated or are don’t care. Consider the case when the machine is in state 0: there are 26 entries in the ROM (since the opcode field can have any value), and these entries will all have the same contents (namely, the control word 0001). The reason that so much of the ROM is wasted is that the ROM implements the complete truth table, providing the opportunity to have a different output for every combination of the inputs. But most combinations of the inputs either never happen or are redundant! Op [5–0] Current state 000000 S[3–0] (R-format)

000010 (jmp)

000100 (beq)

100011 (lw)

101011 (sw)

Any other value

0000

0001

0001

0001

0001

0001

0001

0001

0110

1001

1000

0010

0010

Illegal

0010

XXXX

XXXX

XXXX

0011

0101

Illegal

0011

0100

0100

0100

0100

0100

Illegal

0100

0000

0000

0000

0000

0000

Illegal

0101

0000

0000

0000

0000

0000

Illegal

0110

0111

0111

0111

0111

0111

Illegal

0111

0000

0000

0000

0000

0000

Illegal

1000

0000

0000

0000

0000

0000

Illegal

1001

0000

0000

0000

0000

0000

Illegal

FIGURE D.3.8 This table contains the lower 4 bits of the control word (the NS outputs), which depend on both the state inputs, S[3–0], and the opcode, Op[5–0], which correspond to the instruction opcode. These values can be determined from Figure D.3.5. The opcode name is shown under the encoding in the heading. The four bits of the control word whose address is given by the current-state bits and Op bits are shown in each entry. For example, when the state input bits are 0000, the output is always 0001, independent of the other inputs; when the state is 2, the next state is don’t care for three of the inputs, 3 for lw, and 5 for sw. Together with the entries in Figure D.3.7, this table specifies the contents of the control unit ROM. For example, the word at address 1000110001 is obtained by finding the upper 16 bits in the table in Figure D.3.7 using only the state input bits (0001) and concatenating the lower four bits found by using the entire address (0001 to find the row and 100011 to find the column). The entry from Figure D.3.7 yields 0000000000011000, while the appropriate entry in the table immediately above is 0010. Thus the control word at address 1000110001 is 00000000000110000010. The column labeled “Any other value” applies only when the Op bits do not match one of the specified opcodes.

D-19

D-20

Appendix D Mapping Control to Hardware

A PLA Implementation We can reduce the amount of control storage required at the cost of using more complex address decoding for the control inputs, which will encode only the input combinations that are needed. The logic structure most often used to do this is a programmed logic array (PLA), which we mentioned earlier and illustrated in Figure D.2.5. In a PLA, each output is the logical OR of one or more minterms. A minterm, also called a product term, is simply a logical AND of one or more inputs. The inputs can be thought of as the address for indexing the PLA, while the minterms select which of all possible address combinations are interesting. A minterm corresponds to a single entry in a truth table, such as those in Figure D.3.4, including possible don’t-care terms. Each output consists of an OR of these minterms, which exactly corresponds to a complete truth table. However, unlike a ROM, only those truth table entries that produce an active output are needed, and only one copy of each minterm is required, even if the minterm contains don’t cares. Figure D.3.9 shows the PLA that implements this control function. As we can see from the PLA in Figure D.3.9, there are 17 unique minterms—10 that depend only on the current state and 7 others that depend on a combination of the Op field and the current-state bits. The total size of the PLA is proportional to (#inputs × #product terms) + (#outputs × #product terms), as we can see symbolically from the figure. This means the total size of the PLA in Figure D.3.9 is proportional to (10 × 17) + (20 × 17) = 510. By comparison, the size of a single ROM is proportional to 20 Kb, and even the two-part ROM has a total of 4.3 Kb. Because the size of a PLA cell will be only slightly larger than the size of a bit in a ROM, a PLA will be a much more efficient implementation for this control unit. Of course, just as we split the ROM in two, we could split the PLA into two PLAs: one with 4 inputs and 10 minterms that generates the 16 control outputs, and one with 10 inputs and 7 minterms that generates the 4 next-state outputs. The first PLA would have a size proportional to (4 × 10) + (10 × 16) = 200, and the second PLA would have a size proportional to (10 × 7) + (4 × 7) = 98. This would yield a total size proportional to 298 PLA cells, about 55% of the size of a single PLA. These two PLAs will be considerably smaller than an implementation using two ROMs. For more details on PLAs and their implementation, as well as the Appendix C. references for books on logic design, see

D.3

Implementing Finite-State Machine Control

Op5 Op4 Op3 Op2 Op1 Op0 S3 S2 S1 S0 PCWrite PCWriteCond IorD MemRead MemWrite IRWrite MemtoReg PCSource1 PCSource0 ALUOp1 ALUOp0 ALUSrcB1 ALUSrcB0 ALUSrcA RegWrite RegDst NS3 NS2 NS1 NS0

FIGURE D.3.9 This PLA implements the control function logic for the multicycle implementation. The inputs to the control appear on the left and the outputs on the right. The top half of the figure is the AND plane that computes all the minterms. The minterms are carried to the OR plane on the vertical lines. Each colored dot corresponds to a signal that makes up the minterm carried on that line. The sum terms are computed from these minterms, with each gray dot representing the presence of the intersecting minterm in that sum term. Each output consists of a single sum term.

D-21

D-22

Appendix D Mapping Control to Hardware

D.4

Implementing the Next-State Function with a Sequencer

Let’s look carefully at the control unit we built in the last section. If you examine the ROMs that implement the control in Figures D.3.7 and D.3.8, you can see that much of the logic is used to specify the next-state function. In fact, for the implementation using two separate ROMs, 4096 out of the 4368 bits (94%) correspond to the next-state function! Furthermore, imagine what the control logic would look like if the instruction set had many more different instruction types, some of which required many clocks to implement. There would be many more states in the finite-state machine. In some states, we might be branching to a large number of different states depending on the instruction type (as we did in state 1 of the finite-state machine in Figure D.3.1). However, many of the states would proceed in a sequential fashion, just as states 3 and 4 do in Figure D.3.1. For example, if we included floating point, we would see a sequence of many states in a row that implement a multicycle floating-point instruction. Alternatively, consider how the control might look for a machine that can have multiple memory operands per instruction. It would require many more states to fetch multiple memory operands. The result of this would be that the control logic will be dominated by the encoding of the next-state function. Furthermore, much of the logic will be devoted to sequences of states with only one path through them that look like states 2 through 4 in Figure D.3.1. With more instructions, these sequences will consist of many more sequentially numbered states than for our simple subset. To encode these more complex control functions efficiently, we can use a control unit that has a counter to supply the sequential next state. This counter often eliminates the need to encode the next-state function explicitly in the control unit. As shown in Figure D.4.1, an adder is used to increment the state, essentially turning it into a counter. The incremented state is always the state that follows in numerical order. However, the finite-state machine sometimes “branches.” For example, in state 1 of the finite-state machine (see Figure D.3.1), there are four possible next states, only one of which is the sequential next state. Thus, we need to be able to choose between the incremented state and a new state based on the inputs from the Instruction register and the current state. Each control word will include control lines that will determine how the next state is chosen. It is easy to implement the control output signal portion of the control word, since, if we use the same state numbers, this portion of the control word will look exactly like the ROM contents shown in Figure D.3.7. However, the method

D.4

Implementing the Next-State Function with a Sequencer

PCWrite PCWriteCond IorD MemRead MemWrite IRWrite

Control unit

PLA or ROM

Outputs

Input

MemtoReg PCSource ALUOp ALUSrcB ALUSrcA RegWrite RegDst

AddrCtl

1 State Adder

Op[5–0]

Address select logic

Instruction register opcode field FIGURE D.4.1 The control unit using an explicit counter to compute the next state. In this control unit, the next state is computed using a counter (at least in some states). By comparison, Figure D.3.2 encodes the next state in the control logic for every state. In this control unit, the signals labeled AddrCtl control how the next state is determined.

for selecting the next state differs from the next-state function in the finite-state machine. With an explicit counter providing the sequential next state, the control unit logic need only specify how to choose the state when it is not the sequentially following state. There are two methods for doing this. The first is a method we have already seen: namely, the control unit explicitly encodes the next-state function. The difference is that the control unit need only set the next-state lines when the designated next state is not the state that the counter indicates. If the number of

D-23

D-24

Appendix D Mapping Control to Hardware

states is large and the next-state function that we need to encode is mostly empty, this may not be a good choice, since the resulting control unit will have lots of empty or redundant space. An alternative approach is to use separate external logic to specify the next state when the counter does not specify the state. Many control units, especially those that implement large instruction sets, use this approach, and we will focus on specifying the control externally. Although the nonsequential next state will come from an external table, the control unit needs to specify when this should occur and how to find that next state. There are two kinds of “branching” that we must implement in the address select logic. First, we must be able to jump to one of a number of states based on the opcode portion of the Instruction register. This operation, called a dispatch, is usually implemented by using a set of special ROMs or PLAs included as part of the address selection logic. An additional set of control outputs, which we call AddrCtl, indicates when a dispatch should be done. Looking at the finite-state diagram (Figure D.3.1), we see that there are two states in which we do a branch based on a portion of the opcode. Thus we will need two small dispatch tables. (Alternatively, we could also use a single dispatch table and use the control bits that select the table as address bits that choose from which portion of the dispatch table to select the address.) The second type of branching that we must implement consists of branching back to state 0, which initiates the execution of the next MIPS instruction. Thus there are four possible ways to choose the next state (three types of branches, plus incrementing the current-state number), which can be encoded in 2 bits. Let’s assume that the encoding is as follows: AddrCtl value

Action

0

Set state to 0

1

Dispatch with ROM 1

2

Dispatch with ROM 2

3

Use the incremented state

If we use this encoding, the address select logic for this control unit can be implemented as shown in Figure D.4.2. To complete the control unit, we need only specify the contents of the dispatch ROMs and the values of the address-control lines for each state. We have already specified the datapath control portion of the control word using the ROM contents of Figure D.3.7 (or the corresponding portions of the PLA in Figure D.3.9). The next-state counter and dispatch ROMs take the place of the portion of the control unit that was computing the next state, which was shown in Figure D.3.8. We are

D.4

Implementing the Next-State Function with a Sequencer

PLA or ROM 1 State Adder 3

Mux 2 1

AddrCtl 0 0

Dispatch ROM 2

Dispatch ROM 1

Op

Address select logic

Instruction register opcode field FIGURE D.4.2

This is the address select logic for the control unit of Figure D.4.1.

only implementing a portion of the instruction set, so the dispatch ROMs will be largely empty. Figure D.4.3 shows the entries that must be assigned for this subset.

Dispatch ROM 1

Dispatch ROM 2

Op

Opcode name

Value

Op

Opcode name

Value

000000

R-format

000010

jmp

0110

100011

lw

0011

1001

101011

sw

000100

beq

1000

0101

100011

lw

0010

101011

sw

0010

FIGURE D.4.3 The dispatch ROMs each have 26 = 64 entries that are 4 bits wide, since that is the number of bits in the state encoding. This figure only shows the entries in the ROM that are of interest for this subset. The first column in each table indicates the value of Op, which is the address used to access the dispatch ROM. The second column shows the symbolic name of the opcode. The third column indicates the value at that address in the ROM.

Now we can determine the setting of the address selection lines (AddrCtl) in each control word. The table in Figure D.4.4 shows how the address control must

D-25

D-26

Appendix D Mapping Control to Hardware

State number

Address-control action

Value of AddrCtl

0

Use incremented state

3

1

Use dispatch ROM 1

1

2

Use dispatch ROM 2

2

3

Use incremented state

3

4

Replace state number by 0

0

5

Replace state number by 0

0

6

Use incremented state

3

7

Replace state number by 0

0

8

Replace state number by 0

0

9

Replace state number by 0

0

FIGURE D.4.4 The values of the address-control lines are set in the control word that corresponds to each state.

be set for every state. This information will be used to specify the setting of the AddrCtl field in the control word associated with that state. The contents of the entire control ROM are shown in Figure D.4.5. The total storage required for the control is quite small. There are 10 control words, each 18 bits wide, for a total of 180 bits. In addition, the two dispatch tables are 4 bits wide and each has 64 entries, for a total of 512 additional bits. This total of 692 bits beats the implementation that uses two ROMs with the next-state function encoded in the ROMs (which requires 4.3 Kbits). Of course, the dispatch tables are sparse and could be more efficiently implemented with two small PLAs. The control ROM could also be replaced with a PLA.

State number

Control word bits 17–2

Control word bits 1–0

0

1001010000001000

11

1

0000000000011000

01

2

0000000000010100

10

3

0011000000000000

11

4

0000001000000010

00

5

0010100000000000

00

6

0000000001000100

11

7

0000000000000011

00

8

0100000010100100

00

9

1000000100000000

00

FIGURE D.4.5 The contents of the control memory for an implementation using an explicit counter. The first column shows the state, while the second shows the datapath control bits, and the last column shows the address-control bits in each control word. Bits 17–2 are identical to those in Figure D.3.7.

D.4

Implementing the Next-State Function with a Sequencer

Optimizing the Control Implementation We can further reduce the amount of logic in the control unit by two different techniques. The first is logic minimization, which uses the structure of the logic equations, including the don’t-care terms, to reduce the amount of hardware required. The success of this process depends on how many entries exist in the truth table, and how those entries are related. For example, in this subset, only the lw and sw opcodes have an active value for the signal Op5, so we can replace the two truth table entries that test whether the input is lw or sw by a single test on this bit; similarly, we can eliminate several bits used to index the dispatch ROM because this single bit can be used to find lw and sw in the first dispatch ROM. Of course, if the opcode space were less sparse, opportunities for this optimization would be more difficult to locate. However, in choosing the opcodes, the architect can provide additional opportunities by choosing related opcodes for instructions that are likely to share states in the control. A different sort of optimization can be done by assigning the state numbers in a finite-state or microcode implementation to minimize the logic. This optimization, called state assignment, tries to choose the state numbers such that the resulting logic equations contain more redundancy and can thus be simplified. Let’s consider the case of a finite-state machine with an encoded next-state control first, since it allows states to be assigned arbitrarily. For example, notice that in the finite-state machine, the signal RegWrite is active only in states 4 and 7. If we encoded those states as 8 and 9, rather than 4 and 7, we could rewrite the equation for RegWrite as simply a test on bit S3 (which is only on for states 8 and 9). This renumbering allows us to combine the two truth table entries in part (o) of Figure D.3.4 and replace them with a single entry, eliminating one term in the control unit. Of course, we would have to renumber the existing states 8 and 9, perhaps as 4 and 7. The same optimization can be applied in an implementation that uses an explicit program counter, though we are more restricted. Because the next-state number is often computed by incrementing the current-state number, we cannot arbitrarily assign the states. However, if we keep the states where the incremented state is used as the next state in the same order, we can reassign the consecutive states as a block. In an implementation with an explicit next-state counter, state assignment may allow us to simplify the contents of the dispatch ROMs. If we look again at the control unit in Figure D.4.1, it looks remarkably like a computer in its own right. The ROM or PLA can be thought of as memory supplying instructions for the datapath. The state can be thought of as an instruction address. Hence the origin of the name microcode or microprogrammed control. The control words are thought of as microinstructions that control the datapath, and the State register is called the microprogram counter. Figure D.4.6 shows a view of the control unit as microcode. The next section describes how we map from a microprogram to microcode.

D-27

D-28

Appendix D Mapping Control to Hardware

Control unit

Microcode memory

Outputs

Input

PCWrite PCWriteCond IorD MemRead MemWrite IRWrite BWrite MemtoReg PCSource ALUOp ALUSrcB ALUSrcA RegWrite RegDst AddrCtl

Datapath

1 Microprogram counter Adder

Op[5–0]

Address select logic

Instruction register opcode field FIGURE D.4.6 The control unit as a microcode. The use of the word “micro” serves to distinguish between the program counter in the datapath and the microprogram counter, and between the microcode memory and the instruction memory.

D.5

Translating a Microprogram to Hardware

To translate a microprogram into actual hardware, we need to specify how each field translates into control signals. We can implement a microprogram with either finite-state control or a microcode implementation with an explicit sequencer. If we choose a finite-state machine, we need to construct the next-state function from

D.5

Translating a Microprogram to Hardware

D-29

the microprogram. Once this function is known, we can map a set of truth table entries for the next-state outputs. In this section, we will show how to translate the microprogram, assuming that the next state is specified by a sequencer. From the truth tables we will construct, it would be straightforward to build the nextstate function for a finite-state machine. Field name

ALU control

SRC1

SRC2

Value

Signals active

Add

ALUOp = 00

Cause the ALU to add.

Subt

ALUOp = 01

Cause the ALU to subtract; this implements the compare for branches.

Func code

ALUOp = 10

Use the instruction’s function code to determine ALU control.

PC

ALUSrcA = 0

Use the PC as the first ALU input.

A

ALUSrcA = 1

Register A is the first ALU input.

B

ALUSrcB = 00

Register B is the second ALU input.

4

ALUSrcB = 01

Use 4 as the second ALU input.

Extend

ALUSrcB = 10

Use output of the sign extension unit as the second ALU input.

Extshft

ALUSrcB = 11

Read

PC write control

Sequencing

Use the output of the shift-by-two unit as the second ALU input. Read two registers using the rs and rt fields of the IR as the register numbers and putting the data into registers A and B.

Write ALU

RegWrite, RegDst = 1, MemtoReg = 0

Write a register using the rd field of the IR as the register number and the contents of ALUOut as the data.

Write MDR

RegWrite, RegDst = 0, MemtoReg = 1

Write a register using the rt field of the IR as the register number and the contents of the MDR as the data.

Read PC

MemRead, IorD = 0, IRWrite

Read memory using the PC as address; write result into IR (and the MDR).

Read ALU

MemRead, IorD = 1

Read memory using ALUOut as address; write result into MDR.

Write ALU

MemWrite, IorD = 1

Write memory using the ALUOut as address, contents of B as the data.

ALU

PCSource = 00, PCWrite

Write the output of the ALU into the PC.

ALUOut-cond

PCSource = 01, PCWriteCond

If the Zero output of the ALU is active, write the PC with the contents of the register ALUOut.

Jump address

PCSource = 10, PCWrite

Write the PC with the jump address from the instruction.

Register control

Memory

Comment

Seq

AddrCtl = 11

Choose the next microinstruction sequentially.

Fetch

AddrCtl = 00

Go to the first microinstruction to begin a new instruction.

Dispatch 1

AddrCtl = 01

Dispatch using the ROM 1.

Dispatch 2

AddrCtl = 10

Dispatch using the ROM 2.

FIGURE D.5.1 Each microcode field translate to a set of control signals to be set. These 22 different values of the fields specify all the required combinations of the 18 control lines. Control lines that are not set, which correspond to actions, are 0 by default. Multiplexor control lines are set to 0 if the output matters. If a multiplexor control line is not explicitly set, its output is a don’t care and is not used.

D-30

Appendix D

Mapping Control to Hardware

Assuming an explicit sequencer, we need to do two additional tasks to translate the microprogram: assign addresses to the microinstructions and fill in the contents of the dispatch ROMs. This process is essentially the same as the process of translating an assembly language program into machine instructions: the fields of the assembly language or microprogram instruction are translated, and labels on the instructions must be resolved to addresses. Figure D.5.1 shows the various values for each microinstruction field that controls the datapath and how these fields are encoded as control signals. If the field corresponding to a signal that affects a unit with state (i.e., Memory, Memory register, ALU destination, or PCWriteControl) is blank, then no control signal should be active. If a field corresponding to a multiplexor control signal or the ALU operation control (i.e., ALUOp, SRC1, or SRC2) is blank, the output is unused, so the associated signals may be set as don’t care. The sequencing field can have four values: Fetch (meaning go to the Fetch state), Dispatch 1, Dispatch 2, and Seq. These four values are encoded to set the 2-bit address control just as they were in Figure D.4.4: Fetch = 0, Dispatch 1 = 1, Dispatch 2 = 2, Seq = 3. Finally, we need to specify the contents of the dispatch tables to relate the dispatch entries of the sequence field to the symbolic labels in the microprogram. We use the same dispatch tables as we did earlier in Figure D.4.3. A microcode assembler would use the encoding of the sequencing field, the contents of the symbolic dispatch tables in Figure D.5.2, the specification in Figure D.5.1, and the actual microprogram to generate the microinstructions. Since the microprogram is an abstract representation of the control, there is a great deal of flexibility in how the microprogram is translated. For example, the address assigned to many of the microinstructions can be chosen arbitrarily; the only restrictions are those imposed by the fact that certain microinstructions must

dispatch table 1

Microcode dispatch table 2

Opcode field

Opcode name

Value

Opcode field

Opcode name

000000

R-format

Rformat1

100011

lw

Value LW2

000010

jmp

JUMP1

101011

sw

SW2

000100

beq

BEQ1

100011

lw

Mem1

101011

sw

Mem1

FIGURE D.5.2 The two microcode dispatch ROMs showing the contents in symbolic form and using the labels in the microprogram.

D.5

Translating a Microprogram to Hardware

occur in sequential order (so that incrementing the State register generates the address of the next instruction). Thus the microcode assembler may reduce the complexity of the control by assigning the microinstructions cleverly.

Organizing the Control to Reduce the Logic For a machine with complex control, there may be a great deal of logic in the control unit. The control ROM or PLA may be very costly. Although our simple implementation had only an 18-bit microinstruction (assuming an explicit sequencer), there have been machines with microinstructions that are hundreds of bits wide. Clearly, a designer would like to reduce the number of microinstructions and the width. The ideal approach to reducing control store is to first write the complete microprogram in a symbolic notation and then measure how control lines are set in each microinstruction. By taking measurements we are able to recognize control bits that can be encoded into a smaller field. For example, if no more than one of eight lines is set simultaneously in the same microinstruction, then this subset of control lines can be encoded into a 3-bit field (log2 8 = 3). This change saves five bits in every microinstruction and does not hurt CPI, though it does mean the extra hardware cost of a 3-to-8 decoder needed to generate the eight control lines when they are required at the datapath. It may also have some small clock cycle impact, since the decoder is in the signal path. However, shaving five bits off control store width will usually overcome the cost of the decoder, and the cycle time impact will probably be small or nonexistent. For example, this technique can be applied to bits 13–6 of the microinstructions in this machine, since only one of the seven bits of the control word is ever active (see Figure D.4.5). This technique of reducing field width is called encoding. To further save space, control lines may be encoded together if they are only occasionally set in the same microinstruction; two microinstructions instead of one are then required when both must be set. As long as this doesn’t happen in critical routines, the narrower microinstruction may justify a few extra words of control store. Microinstructions can be made narrower still if they are broken into different formats and given an opcode or format field to distinguish them. The format field gives all the unspecified control lines their default values, so as not to change anything else in the machine, and is similar to the opcode of an instruction in a more powerful instruction set. For example, we could use a different format for microinstructions that did memory accesses from those that did register-register ALU operations, taking advantage of the fact that the memory access control lines are not needed in microinstructions controlling ALU operations. Reducing hardware costs by using format fields usually has an additional performance cost beyond the requirement for more decoders. A microprogram using a single microinstruction format can specify any combination of operations in a datapath and can take fewer clock cycles than a microprogram made up of restricted microinstructions that cannot perform any combination of operations in a single

D-31

D-32

Appendix D Mapping Control to Hardware

microinstruction. However, if the full capability of the wider microprogram word is not heavily used, then much of the control store will be wasted, and the machine could be made smaller and faster by restricting the microinstruction capability. The narrow, but usually longer, approach is often called vertical microcode, while the wide but short approach is called horizontal microcode. It should be noted that the terms “vertical microcode” and “horizontal microcode” have no universal definition—the designers of the 8086 considered its 21-bit microinstruction to be more horizontal than other single-chip computers of the time. The related terms maximally encoded and minimally encoded are probably better than vertical and horizontal.

D.6

Concluding Remarks

We began this appendix by looking at how to translate a finite-state diagram to an implementation using a finite-state machine. We then looked at explicit sequencers that use a different technique for realizing the next-state function. Although large microprograms are often targeted at implementations using this explicit next-state approach, we can also implement a microprogram with a finite-state machine. As we saw, both ROM and PLA implementations of the logic functions are possible. The advantages of explicit versus encoded next state and ROM versus PLA implementation are summarized below.

BIG

The Picture

Independent of whether the control is represented as a finite-state diagram or as a microprogram, translation to a hardware control implementation is similar. Each state or microinstruction asserts a set of control outputs and specifies how to choose the next state. The next-state function may be implemented by either encoding it in a finite-state machine or using an explicit sequencer. The explicit sequencer is more efficient if the number of states is large and there are many sequences of consecutive states without branching. The control logic may be implemented with either ROMs or PLAs (or even a mix). PLAs are more efficient unless the control function is very dense. ROMs may be appropriate if the control is stored in a separate memory, as opposed to within the same chip as the datapath.

D.7

D.7

Exercises

Exercises

D.1 [10] <§D.2> Instead of using four state bits to implement the finite-state machine in Figure D.3.1 on page C-9, use nine state bits, each of which is a 1 only if the finite-state machine is in that particular state (e.g., S1 is 1 in state 1, S2 is 1 in state 2, etc.). Redraw the PLA (Figure D.3.9). D.2 [5] <§D.3> We wish to add the instruction jal (jump and link). Make any

necessary changes to the datapath or to the control signals if needed. You can photocopy figures to make it faster to show the additions. How many product terms are required in a PLA that implements the control for the single-cycle datapath for jal? D.3 [5] <§D.3> Now we wish to add the instruction addi (add immediate). Add

any necessary changes to the datapath and to the control signals. How many product terms are required in a PLA that implements the control for the single-cycle datapath for addiu? D.4 [10] <§D.3> Determine the number of product terms in a PLA that imple-

ments the finite-state machine for addi. The easiest way to do this is to construct the additions to the truth tables for addi. D.5 [20] <§D.4> Implement the finite-state machine of using an explicit counter

to determine the next state. Fill in the new entries for the additions to Figure D.4.5. Also, add any entries needed to the dispatch ROMs of Figure D.5.2. D.6 [15] <§§D.3–D.6> Determine the size of the PLAs needed to implement the

multicycle machine, assuming that the next-state function is implemented with a counter. Implement the dispatch tables of Figure D.5.2 using two PLAs and the contents of the main control unit in Figure D.4.5 using another PLA. How does the total size of this solution compare to the single PLA solution with the next state encoded? What if the main PLAs for both approaches are split into two separate PLAs by factoring out the next-state or address select signals?

D-33

E A

P

P

E

N

D

I

RISC: any computer announced after 1985.

X

A Survey of RISC Architectures for Desktop, Server, and Embedded Computers Steven Przybylskic A Designer of the Stanford MIPS

E.1

Introduction E-3

E.2

Addressing Modes and Instruction Formats E-5

E.3

Instructions: The MIPS Core Subset E-9

E.4

Instructions: Multimedia Extensions of the Desktop/Server RISCs

E.5

E-16

Instructions: Digital Signal-Processing Extensions of the Embedded RISCs E-19

E.6

Instructions: Common Extensions to MIPS Core E-20

E.7

Instructions Unique to MIPS-64 E-25

E.8

Instructions Unique to Alpha E-27

E.9

Instructions Unique to SPARC v.9 E-29

E.10

Instructions Unique to PowerPC E-32

E.11

Instructions Unique to PA-RISC 2.0 E-34

E.12

Instructions Unique to ARM E-36

E.13

Instructions Unique to Thumb E-38

E.14

Instructions Unique to SuperH E-39

E.15

Instructions Unique to M32R E-40

E.16

Instructions Unique to MIPS-16 E-40

E.17

Concluding Remarks E-43

E.1

Introduction

We cover two groups of reduced instruction set computer (RISC) architectures in this appendix. The first group is the desktop and server RISCs: ■

Digital Alpha

■

Hewlett-Packard PA-RISC

■

IBM and Motorola PowerPC

■

MIPS INC MIPS-64

■

Sun Microsystems SPARC

E-4

Appendix E A Survey of RISC Architectures

The second group is the embedded RISCs: ■

Advanced RISC Machines ARM

■

Advanced RISC Machines Thumb

■

Hitachi SuperH

■

Mitsubishi M32R

■

MIPS INC MIPS-16

Alpha Date announced

MIPS I

PA-RISC 1.1 1986

PowerPC 1993

SPARC v.8

1992

1986

1987

Instruction size (bits)

32

32

32

32

32

Address space (size, model)

64 bits, flat

32 bits, flat

48 bits, segmented

32 bits, flat

32 bits, flat

Data alignment

Aligned

Aligned

Aligned

Unaligned

Aligned

Data addressing modes

1

1

5

4

2

Protection

Page

Page

Page

Page

Page

Minimum page size

8 KB

4 KB

4 KB

4 KB

8 KB

I/O

Memory mapped

Memory mapped

Memory mapped

Memory mapped

Memory mapped

Integer registers (number, model, size)

31 GPR × 64 bits 31 GPR × 32 bits

31 GPR × 32 bits 32 GPR × 32 bits

Separate floating-point registers

31 × 32 or 31 × 64 bits

16 × 32 or 16 × 64 bits

56 × 32 or 28 × 64 bits

32 × 32 or 32 × 64 bits

32 × 32 or 32 × 64 bits

Floating-point format

IEEE 754 single, double

IEEE 754 single, double

IEEE 754 single, double

IEEE 754 single, double

IEEE 754 single, double

31 GPR × 32 bits

FIGURE E.1.1 Summary of the first version of five architectures for desktops and servers. Except for the number of data address modes and some instruction set details, the integer instruction sets of these architectures are very similar. Contrast this with Figure E.17.1. Later versions of these architectures all support a flat, 64-bit address space.

ARM

Thumb

SuperH

M32R

MIPS-16

Date announced

1985

1995

1992

1997

1996

Instruction size (bits)

32

16

16

16/32

16/32

Address space (size, model)

32 bits, flat

32 bits, flat

32 bits, flat

32 bits, flat

32/64 bits, flat

Data alignment

Aligned

Aligned

Aligned

Aligned

Aligned

Data addressing modes

6

6

Integer registers (number, model, size)

15 GPR x 32 bits 8 GPR + SP, LR x 32 bits

I/O

Memory mapped

4

3

2

16 GPR x 32 bits

16 GPR x 32 bits

8 GPR + SP, RA x 32/64 bits

Memory mapped Memory mapped

Memory mapped

Memory mapped

FIGURE E.1.2 Summary of five architectures for embedded applications. Except for number of data address modes and some instruction set details, the integer instruction sets of these architectures are similar. Contrast this with Figure E.17.1.

E.2

Addressing Modes and Instruction Formats

There has never been another class of computers so similar. This similarity allows the presentation of 10 architectures in about 50 pages. Characteristics of the desktop and server RISCs are found in Figure E.1.1 and the embedded RISCs in Figure E.1.2. Notice that the embedded RISCs tend to have 8 to 16 general-purpose registers while the desktop/server RISCs have 32, and that the length of instructions is 16 to 32 bits in embedded RISCs but always 32 bits in desktop/server RISCs. Although shown as separate embedded instruction set architectures, Thumb and MIPS-16 are really optional modes of ARM and MIPS invoked by call instructions. When in this mode, they execute a subset of the native architecture using 16-bit-long instructions. These 16-bit instruction sets are not intended to be full architectures, but they are enough to encode most procedures. Both machines expect procedures to be homogeneous, with all instructions in either 16-bit mode or 32-bit mode. Programs will consist of procedures in 16-bit mode for density or in 32-bit mode for performance. One complication of this description is that some of the older RISCs have been extended over the years. We have decided to describe the latest versions, of the architectures: MIPS-64, Alpha version 3, PA-RISC 2.0, and SPARC version 9 for the desktop/server; ARM version 4, Thumb version 1, Hitachi SuperH SH-3, M32R version 1, and MIPS-16 version 1 for the embedded ones. The remaining sections proceed as follows: after discussing the addressing modes and instruction formats of our RISC architectures, we present the survey of the instructions in five steps: ■

Instructions found in the MIPS core, which is defined in Chapters 2 and 3 of the main text

■

Multimedia extensions of the desktop/server RISCs

■

Digital signal-processing extensions of the embedded RISCs

■

Instructions not found in the MIPS core but found in two or more architectures

■

The unique instructions and characteristics of each of the ten architectures

We give the evolution of the instruction sets in the final section and conclude with a speculation about future directions for RISCs.

E.2

Addressing Modes and Instruction Formats

Figure E.2.1 shows the data addressing modes supported by the desktop architectures. Since all have one register that always has the value 0 when used in address modes, the absolute address mode with limited range can be synthesized using

E-5

E-6

Appendix E A Survey of RISC Architecture

zero as the base in displacement addressing. (This register can be changed by ALU operations in PowerPC; it is always 0 in the other machines.) Similarly, register indirect addressing is synthesized by using displacement addressing with an offset of 0. Simplified addressing modes is one distinguishing feature of RISC architectures. Figure E.2.2 shows the data addressing modes supported by the embedded architectures. Unlike the desktop RISCs, these embedded machines do not reserve a register to contain 0. Although most have two to three simple addressing modes, ARM and SuperH have several, including fairly complex calculations. ARM has an addressing mode that can shift one register by any amount, add it to the other registers to form the address, and then update one register with this new address. References to code are normally PC-relative, although jump register indirect is supported for returning from procedures, for case statements, and for pointer function calls. One variation is that PC-relative branch addresses are shifted left two bits before being added to the PC for the desktop RISCs, thereby increasing the branch distance. This works because the length of all instructions for the desktop RISCs is 32 bits, and instructions must be aligned on 32-bit words in memory. Embedded architectures with 16-bit-long instructions usually shift the PC-relative address by 1 for similar reasons. Addressing mode

Alpha

Register + offset (displacement or based)

X

Register + register (indexed)

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

X

X

X

X

X (FP)

X (Loads)

X

X

Register + scaled register (scaled)

X

Register + offset and update register

X

X

Register + register and update register

X

X

FIGURE E.2.1 Summary of data addressing modes supported by the desktop architectures. PA-RISC also has short address versions of the offset addressing modes. MIPS-64 has indexed addressing for floating-point loads and stores. (These addressing modes are described in Figure 2.24.) Addressing mode

ARM v.4

Thumb

SuperH

M32R

MIPS-16

Register + offset (displacement or based)

X

X

X

X

X

Register + register (indexed)

X

X

X

Register + scaled register (scaled)

X

Register + offset and update register

X

Register + register and update register

X

Register indirect

X

X

Autoincrement, autodecrement

X

X

X

X

PC-relative data

X

X (loads)

X

X (loads)

FIGURE E.2.2 Summary of data addressing modes supported by the embedded architectures. SuperH and M32R have separate register indirect and register + offset addressing modes rather than just putting 0 in the offset of the latter mode. This increases the use of 16-bit instructions in the M32R, and it gives a wider set of address modes to different data transfer instructions in SuperH. To get greater addressing range, ARM and Thumb shift the offset left one or two bits if the data size is halfword or word. (These addressing modes are described in Figure 2.24.)

E.2

Addressing Modes and Instruction Formats

Figure E.2.3 shows the format of the desktop RISC instructions, which include the size of the address. Each instruction set architecture uses these four primary instruction formats. Figure E.2.4 shows the six formats for the embedded RISC machines. The desire to have smaller code size via 16-bit instructions leads to more instruction formats. 31

Register-register

25

20

15

10

Alpha

Op6

Rs15

Rs25

MIPS

Op6

Rs15

Rs25

Rd5

PowerPC

Op6

Rd5

Rs15

Rs25

Op6

Rs15

Rs25

PA-RISC Op2

SPARC

Rd5

Opx6

31 29 31

18

25 Op6

Rd5

MIPS

Const5

15 Const16

Rs15

Rd5

Const16

Rd5

Rs15

Const16

PA-RISC

Op6

Rs25

Rd5

Opx6

31 29 31

Branch

25

18 20

0

15

Op6

Rs15

MIPS

Op6

Rs15

Opx5/Rs25

PowerPC

Op6

Opx6

Rs15

PA-RISC

Op6

Rs25

Rs15

Op2

Const13

1 13 12

Alpha

SPARC

0 Const21 Const16 Const14

Opx3

Const11

Opx11

31

18 25

Opx2

OC

Const19

31 29

Jump/call

Const16 Rs15

24

0 0

Rs15

Op6 Rd5

Rs25 4

Op6

Op2

Rd5

Opx8

0

Register-immediate PowerPC SPARC

Opx6

Opx11

13 12

20

Alpha

0 Rd5

Opx11

Rs15

24

4

Opx11

12

20

1 0 0

Alpha

Op6

MIPS

Op6

PowerPC

Op6

Const24

Opx2

PA-RISC

Op6

Const21

O1 C1

SPARC

Rs15

Const21 Const26

Op2

Const30

31 29

20

Opcode

Register

15

12

1 0

Constant

FIGURE E.2.3 Instruction formats for desktop/server RISC architectures. These four formats are found in all five architectures. (The superscrift notation in this figure means the width of a field in bits.) Although the register fields are located in similar pieces of the instruction, be aware that the destination and two source fields are scrambled. Op = the main opcode, Opx = an opcode extension, Rd = the destination register, Rs1 = source register 1, Rs2 = source register 2, and Const = a constant (used as an immediate or as an address). Unlike the other RISCs, Alpha has a format for immediates in arithmetic and logical operations that is different from the data transfer format shown here. It provides an 8-bit immediate in bits 20 to 13 of the RR format, with bits 12 to 5 remaining as an opcode extension.

E-7

E-8

Appendix E A Survey of RISC Architectures

31

Rs14

Opx4

M32R

Op4

Rd4

Opx4

Rs4

Op5 10

31

M32R

Rd4

Op4

Rd4

15

Rs4

7

4

15 Rs14

Const5

Rs3

Rd4

Rs4

M32R

Op4

Rd4

Opx4

Rs4

Rs3

Const5

Rd3 10

31

7

27

ARM

Opx4

Thumb

Op4

Const8 Const8

Rd3

Op4

M32R

Op4

Const11 Opx4

Const8 Const11

10

31

0

27 Opx4

23 Const24 Const11

Op4

SuperH

0

Op4

Op5

Thumb

0 Const24

Const12

15

ARM

0

23

Op5

MIPS-16

15

Const11

Const24

Op6

MIPS-16

Opx5

Const12 Op8

M32R

Const16

Op4

Op5

SuperH

Rs4

Const8 7

27 Opx4

Thumb

Opx4

Rd4 10

31

0 Const24

Opx4

15

ARM

0

23

Op5

MIPS-16

Const16

Op4

Op4

M32R

0 Const12

Const4

4

Op8

SuperH

11 Rd4

Rd3

Op4

15

Const16 0

19

Op5

0 Const12

Const5

SuperH MIPS-16

Call

Rs3

Op3

Op5

11 Rd4

Const8 Opx4

27 Opx4

Thumb

15

Const8

Rd3 10

31 ARM

Opx2

Rs14

Rd3

Op4

0

Rs24

1 0

19

Op5

MIPS-16

4

Op3

Op5

Thumb

7

27 Opx4

Register-immediate SuperH

Rs13 Rs23

Rd3

3 Opx8

Rs3 Rd3

Rd4

ARM

Jump

Opx4

11 Rd4

Op4

15

Branch

15 Rs14

SuperH MIPS-16

Data transfer

19 Opx4

Op6

Thumb Register-register

27 Opx4

ARM

Const26 25 Opcode

0 Register

Constant

FIGURE E.2.4 Instruction formats for embedded RISC architectures. These six formats are found in all five architectures. The notation is the same as in Figure E.2.3. Note the similarities in branch, jump, and call formats, and the diversity in register-register, register-immediate, and data transfer formats. The differences result from whether the architecture has 8 or 16 registers, whether it is a 2- or 3-operand format, and whether the instruction length is 16 or 32 bits.

E.3

Format: instruction category

E-9

Instructions: the MIPS Core Subset

Alpha

MIPS-64

Branch: all

Sign

Sign

Jump/call: all

Sign

—

Register-immediate: data transfer

Sign

Sign

Register-immedaite: arithmetic

Zero

Register-immediate: logical

Zero

PA-RISC 2.0

PowerPC

SPARC v.9

Sign

Sign

Sign

Sign

Sign

Sign

Sign

Sign

Sign

Sign

Sign

Sign

Sign

Zero

—

Zero

Sign

FIGURE E.2.5 Summary of constant extension for desktop RISCs. The constants in the jump and call instructions of MIPS are not sign-extended, since they only replace the lower 28 bits of PC, leaving the upper 4 bits unchanged. PA-RISC has no logical immediate instructions.

Format: instruction category

Arm v.4

Thumb

SuperH

M32R

MIPS-16 Sign

Branch: all

Sign

Sign

Sign

Sign

Jump/call: all

Sign

Sign/Zero

Sign

Sign

—

Register-immediate: data transfer

Zero

Zero

Zero

Sign

Zero

Register-immedaite: arithmetic

Zero

Zero

Sign

Sign

Zero/Sign

Register-immediate: logical

Zero

—

Zero

Zero

—

FIGURE E.2.6 Summary of constant extension for embedded RISCs. The 16-bit-length instructions have much shorter immediates than those of the desktop RISCs, typically only five to eight bits. Most embedded RISCs, however, have a way to get a long address for procedure calls from two sequencial halfwords. The constants in the jump and call instructions of MIPS are not sign-extended, since they only replace the lower 28 bits of the PC, leaving the upper 4 bits unchanged. The 8-bit immediates in ARM can be rotated right an even number of bits between 2 and 30, yielding a large range of immediate values. For example, all powers of two are immediates in ARM.

Figures E.2.5 and E.2.6 show the variations in extending constant fields to the full width of the registers. In this subtle point, the RISCs are similar but not identical.

E.3

Instructions: the MIPS Core Subset

The similarities of each architecture allow simultaneous descriptions, starting with the operations equivalent to the MIPS core.

MIPS Core Instructions Almost every instruction found in the MIPS core is found in the other architectures, as Figures E.3.1 through E.3.5 show. (For reference, definitions of the MIPS instructions are found in the MIPS Reference Data Card at the beginning of the book.) Instructions are listed under four categories: data transfer (Figure E.3.1); arithmetic/logical (Figure E.3.2); control (Figure E.3.3); and floating point (Figure E.3.4). A fifth category (Figure E.3.5) shows conventions for register usage and pseudoinstructions on

E-10

Appendix E A Survey of RISC Architectures

Data transfer (instruction formats)

R-I

R-I

R-I, R-R

R-I, R-R

R-I, R-R

Instruction name

Alpha

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

Load byte signed

LDBU; SEXTB LB

LDB; EXTRW,S 31,8

LBZ; EXTSB

LDSB

Load byte unsigned

LDBU

LDB, LDBX, LDBS

LBZ

LDUB

Load halfword signed

LDWU; SEXTW LH

LDH; EXTRW,S 31,16 LHA

LDSH

Load halfword unsigned

LDWU

LHU

LDH, LDHX, LDHS

LHZ

LDUH

Load word

LDLS

LW

LDW, LDWX, LDWS

LW

LD

Load SP float

LDS*

LWC1

FLDWX, FLDWS

LFS

LDF

Load DP float

LDT

LDC1

FLDDX, FLDDS

LFD

LDDF

Store byte

STB

SB

STB, STBX, STBS

STB

STB

Store halfword

STW

SH

STH, STHX, STHS

STH

STH

Store word

STL

SW

STW, STWX, STWS

STW

ST

Store SP float

STS

SWC1

FSTWX, FSTWS

STFS

STF

Store DP float

STT

SDC1

FSTDX, FSTDS

STFD

STDF

Read, write special registers

MF_, MT_

MF, MT_

MFCTL, MTCTL

MFSPR, MF_, RD, WR, RDPR, WRPR, MTSPR, MT_ LDXFSR, STXFSR

Move integer to FP register

ITOFS

MFC1/DMFC1 STW; FLDWX

STW; LDFS

ST; LDF

Move FP to integer register

FTTOIS

MTC1/DMTC1 FSTWX; LDW

STFS; LW

STF; LD

LBU

FIGURE E.3.1 Desktop RISC data transfer instructions equivalent to MIPS core. A sequence of instructions to synthesize a MIPS instruction is shown separated by semicolons. If there are several choices of instructions equivalent to MIPS core, they are separated by commas. For this figure, halfword is 16 bits and word is 32 bits. Note that in Alpha, LDS converts single precision floating point to double precision and loads the entire 64-bit register.

each architecture. If a MIPS core instruction requires a short sequence of instructions in other architectures, these instructions are separated by semicolons in Figures E.3.1 through E.3.5. (To avoid confusion, the destination register will always be the leftmost operand in this appendix, independent of the notation normally used with each architecture.) Figures E.3.6 through E.3.9 show the equivalent listing for embedded RISCs. Note that floating point is generally not defined for the embedded RISCs. Every architecture must have a scheme for compare and conditional branch, but despite all the similarities, each of these architectures has found a different way to perform the operation.

Compare and Conditional Branch SPARC uses the traditional four condition code bits stored in the program status word: negative, zero, carry, and overflow. They can be set on any arithmetic or logical instruction; unlike earlier architectures, this setting is optional on each instruction. An explicit option leads to fewer problems in pipelined implementation. Although condition codes can be set as a side effect of an operation, explicit compares are synthesized with a subtract using r0 as the destination. SPARC conditional branches

E.3

E-11

Instructions: the MIPS Core Subset

Arithmetic/logical (instruction formats)

R-R, R-I

R-R, R-I

R-R, R-I

R-R, R-I

R-R, R-I

Instruction name

Alpha

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

ADDL, LD0, ADDI, UADDCM ADDO, ADDIO

Add

ADDL

ADDU, ADDU

Add (trap if overflow)

ADDLV

ADD, ADDI

Sub

SUBL

SUBU

SUB, SUBI

SUBF

SUB

Sub (trap if overflow)

SUBLV

SUB

SUBTO, SUBIO

SUBF/oe

SUBcc; TVS

Multiply

MULL

MULT, MULTU

SHiADD;...; (i=1,2,3)

MULLW, MULLI

MULX

Multiply (trap if overflow)

MULLV

—

SHiADDO;...;

—

—

Divide

—

DIV, DIVU

DS;...; DS

DIVW

DIVX

Divide (trap if overflow)

—

—

—

—

—

And

AND

AND, ANDI

AND

AND, ANDI

AND

Or

BIS

OR, ORI

OR

OR, ORI

OR

Xor

XOR

XOR, XORI

XOR

XOR, XORI

XOR

Load high part register

LDAH

LUI

LDIL

ADDIS

Shift left logical

SLL SRL SRA CMPEQ, CMPLT, CMPLE

SLLV, SLL SRLV, SRL SRAV, SRA SLT/U, SLTI/U

DEPW, Z 31-i,32-i EXTRW, U 31, 32-i EXTRW, S 31, 32-i COMB

RLWINM RLWINM 32-i SRAW CMP(I)CLR

SETHI (B fmt.) SLL SRL SRA SUBcc r0,...

Shift right logical Shift right arithmetic Compare

ADD, ADDI

ADD

ADDO; MCRXR; BC

ADDcc; TVS

FIGURE E.3.2 Desktop RISC arithmetic/logical instructions equivalent to MIPS core. Dashes mean the operation is not available in that architecture, or not synthesized in a few instructions. Such a sequence of instructions is shown separated by semicolons. If there are several choices of instructions equivalent to MIPS core, they are separated by commas. Note that in the “Arithmetic/logical” category, all machines but SPARC use separate instruction mnemonics to indicate an immediate operand; SPARC offers immediate versions of these instructions but uses a single mnemonic. (Of course these are separate opcodes!) Control (instruction formats)

B, J/C

B, J/C

B, J/C

B, J/C

B, J/C

Instruction name

Alpha

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

Branch on integer compare

B_ (<, >, <=, >=, =, not=)

BEQ, BNE, B_Z COMB, COMIB (<, >, <=, >=)

BC

Branch on floating-point compare

FB_(<, >, <=, >=, =, not=)

BC1T, BC1F

FSTWX f0; LDW t; BB t

BC

Jump, jump register

BR, JMP BSR

J, JR JAL, JALR

BL r0, BLR r0 BL, BLE

CALL_PAL GENTRAP CALL_PAL REI

BREAK

BREAK

B, BCLR, BCCTR BA, JMPL r0,... BL, BLA, CALL, JMPL BCLRL, BCCTRL TW, TWI Ticc, SIR

JR; ERET

RFI, RFIR

RFI

Call, call register Trap Return from interrupt

BR_Z, BPcc (<, >, <=, >=, =, not=) FBPfcc (<, >, <=, >=, =,...)

DONE, RETRY, RETURN

FIGURE E.3.3 Desktop RISC control instructions equivalent to MIPS core. If there are several choices of instructions equivalent to MIPS core, they are separated by commas.

E-12

Appendix E A Survey of RISC Architectures

Floating point (instruction formats)

R-R

R-R

R-R

R-R

R-R

Instruction name

Alpha

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

ADDS, ADDT SUBS, SUBT MULS, MULT DIVS, DIVT CMPT_ (=, <, <=, UN)

ADD.S, ADD.D SUB.S, SUB.D MUL.S, MUL.D DIV.S, DIV.D C_.S, C_.D (<, >, <=, >=, =,...)

FADD FADD/dbl FSUB FSUB/dbl FMPY FMPY/dbl FDIV, FDIV/dbl FCMP, FCMP/dbl (<, =, >)

FADDS, FADD FSUBS, FSUB FMULS, FMUL FDIVS, FDIV FCMP

ADDT Fd, F31, Fs CVTST, CVTTS, CVTTQ, CVTQS, CVTQT

MOV.S, MOV.D CVT.S.D, CVT. D.S, CVT.S.W, CVT.D.W, CVT. W.S, CVT.W.D

FCPY FCNVFF,s,d FCNVFF,d,s FCNVXF,s,s FCNVXF,d,d FCNVFX,s,s FCNVFX,d,s

FMV FMOVS/D/Q —, FRSP, —, FSTOD, FDTOS, FCTIW,—, — FSTOI, FDTOI, FITOS, FITOD

Add single, double Subtract single, double Multiply single, double Divide single, double Compare Move R-R Convert (single, double, integer) to (single, double, integer)

FADDS, FADDD FSUBS, FSUBD FMULS, FMULD FDIVS, FDIVD FCMPS, FCMPD

FIGURE E.3.4 Desktop RISC floating-point instructions equivalent to MIPS core. Dashes mean the operation is not available in that architecture, or not synthesized in a few instructions. If there are several choices of instructions equivalent to MIPS core, they are separated by commas. Conventions Register with value 0 Return address register No-op Move R-R integer Operand order

FIGURE E.3.5

Alpha r31 (source) (any)

MIPS-64 r0 r31

LDQ_U r31,... SLL r0, r0, r0 BIS..., r31,... ADD..., r0,... OP Rs1, Rs2, Rd OP Rd, Rs1, Rs2

PA-RISC 2.0 r0 r2, r31

PowerPC

SPARC v.9

r0 (addressing) r0 link (special) r31

OR r0, r0, r0 ORI r0, r0, #0 OR..., r0,... OR rx, ry, ry OP Rs1, Rs2, Rd OP Rd, Rs1, Rs2

SETHI r0, 0 OR..., r0,... OP Rs1, Rs2, Rd

Conventions of desktop RISC architectures equivalent to MIPS core.

test condition codes to determine all possible unsigned and signed relations. Floating point uses separate condition codes to encode the IEEE 754 conditions, requiring a floating-point compare instruction. Version 9 expanded SPARC branches in four ways: a separate set of condition codes for 64-bit operations; a branch that tests the contents of a register and branches if the value is =, not=, <, <=, >=, or <= 0 (see MIPS below); three more sets of floating-point condition codes; and branch instructions that encode static branch prediction. PowerPC also uses four condition codes—less than, greater than, equal, and summary overflow—but it has eight copies of them. This redundancy allows the PowerPC instructions to use different condition codes without conflict, essentially giving PowerPC eight extra 4-bit registers. Any of these eight condition codes can be the target of a compare instruction, and any can be the source of a conditional branch. The integer instructions have an option bit that behaves as if the integer op is

E.3

E-13

Instructions: the MIPS Core Subset

Instruction name

ARM v.4

Thumb

SuperH

M32R

MIPS-16

Data transfer (instruction formats)

DT

DT

DT

DT

DT

LDRSB LDRB LDRSH LDRH LDR STRB STRH STR MRS, MSR

LDRSB LDRB LDRSH LDRH LDR STRB STRH STR —1

MOV.B MOV.B; EXTU.B MOV.W MOV.W; EXTU.W MOV.L MOV.B MOV.W MOV.L LDC, STC

LDB LDUB LDH LDUH LD STB STH ST MVFC, MVTC

LB LBU LH LHU LW SB SH SW MOVE

Load byte signed Load byte unsigned Load halfword signed Load halfword unsigned Load word Store byte Store halfword Store word Read, write special registers

FIGURE E.3.6 Embedded RISC data transfer instructions equivalent to MIPS core. A sequence of instructions to synthesize a MIPS instruction is shown separated by semicolons. Note that floating point is generally not defined for the embedded RISCs. Thumb and MIPS-16 are just 16-bit instruction subsets of the ARM and MIPS architectures, so machines can switch modes and execute the full instruction set. We use —1 to show sequences that are available in 32-bit mode but not 16-bit mode in Thumb or MIPS-16.

followed by a compare to zero that sets the first condition “register.” PowerPC also lets the second “register” be optionally set by floating-point instructions. PowerPC provides logical operations among these eight 4-bit condition code registers (CRAND, CROR, CRXOR, CRNAND, CRNOR, CREQV), allowing more complex conditions to be tested by a single branch. MIPS uses the contents of registers to evaluate conditional branches. Any two registers can be compared for equality (BEQ) or inequality (BNE), and then the branch is taken if the condition holds. The set on less than instructions (SLT, SLTI, SLTU, SLTIU) compare two operands and then set the destination register to 1 if less and to 0 otherwise. These instructions are enough to synthesize the full set of relations. Because of the popularity of comparisons to 0, MIPS includes special compare and branch instructions for all such comparisons: greater than or equal to zero (BGEZ), greater than zero (BGTZ), less than or equal to zero (BLEZ), and less than zero (BLTZ). Of course, equal and not equal to zero can be synthesized using r0 with BEQ and BNE. Like SPARC, MIPS I uses a condition code for floating point with separate floating-point compare and branch instructions; MIPS IV expanded this to eight floating-point condition codes, with the floating point comparisons and branch instructions specifying the condition to set or test. Alpha compares (CMPEQ, CMPLT, CMPLE, CMPULT, CMPULE) test two registers and set a third to 1 if the condition is true and to 0 otherwise. Floating-point compares (CMTEQ, CMTLT, CMTLE, CMTUN) set the result to 2.0 if the condition holds and to 0 otherwise. The branch instructions compare one register to 0 (BEQ, BGE, BGT, BLE, BLT, BNE) or its least significant bit to 0 (BLBC, BLBS) and then branch if the condition holds.

E-14

Appendix E A Survey of RISC Architectures

Arithmetic/logical (instruction formats)

R-R, R-I

R-R, R-I

R-R, R-I

R-R, R-I

R-R, R-I

Instruction name

ARM v.4

Thumb

SuperH

M32R

MIPS-16

Add

ADD

ADD

ADD

ADD, ADDI, ADD3

ADDU, ADDIU

Add (trap if overflow)

ADDS; SWIVS

ADD; BVC .+4; SWI

ADDV

ADDV, ADDV3

—1

Subtract

SUB

SUB

SUB

SUB

SUBU

Subtract (trap if overflow)

SUBS; SWIVS

SUB; BVC .+1; SWI

SUBV

SUBV

—1

Multiply

MUL

MUL

MUL

MUL

Multiply (trap if overflow)

MULT, MULTU —

Divide

—

—

Divide (trap if overflow)

—

—

And

AND

Or

DIV1, DIVoS, DIV, DIVU DIVoU

DIV, DIVU

AND

AND

AND, AND3

AND

ORR

ORR

OR

OR, OR3

OR

Xor

EOR

EOR

XOR

Load high part register

—

—

Shift left logical

LSL3

LSL2

3

2

—

XOR, XOR3

XOR

SETH

—1

SHLL, SHLLn

SLL, SLLI, SLL3

SLLV, SLL SRLV, SRL

Shift right logical

LSR

LSR

SHRL, SHRLn

SRL, SRLI, SRL3

Shift right arithmetic

ASR3

ASR2

SHRA, SHAD

SRA, SRAI, SRA3

SRAV, SRA

Compare

CMP,CMN, TST,TEQ

CMP, CMN, TST

CMP/cond, TST

CMP/I, CMPU/I

CMP/I2, SLT/I, SLT/IU

FIGURE E.3.7 Embedded RISC arithmetic/logical instructions equivalent to MIPS core. Dashes mean the operation is not available in that architecture, or not synthesized in a few instructions. Such a sequence of instructions is shown separated by semicolons. If there are several choices of instructions equivalent to MIPS core, they are separated by commas. Thumb and MIPS-16 are just 16-bit instruction subsets of the ARM and MIPS architectures, so machines can switch modes and execute the full instruction set. We use —1 to show sequences that are available in 32-bit mode but not 16-bit mode in Thumb or MIPS-16. The superscript 2 shows new instructions found only in 16-bit mode of Thumb or MIPS-16, such as CMP/I2. ARM includes shifts as part of every data operation instruction, so the shifts with superscript 3 are just a variation of a move instruction, such as LSR3 .

PA-RISC has many branch options, which we’ll see in Section E.8. The most straightforward is a compare and branch instruction (COMB), which compares two registers, branches depending on the standard relations, and then tests the least significant bit of the result of the comparison. ARM is similar to SPARC, in that it provides four traditional condition codes that are optionally set. CMP subtracts one operand from the other and the difference sets the condition codes. Compare negative (CMN) adds one operand to the other, and the sum sets the condition codes. TST performs logical AND on the two operands to set all condition codes but overflow, while TEQ uses exclusive OR to set the first three condition codes. Like SPARC, the conditional version of the ARM branch instruction tests condition codes to determine all possible unsigned and signed relations.

E.3

Control (instruction formats)

B, J, C

Instruction name

B, J, C

ARM v.4

E-15

Instructions: the MIPS Core Subset

Thumb

B, J, C SuperH

B, J, C

B, J, C

M32R

MIPS-16

Branch on integer compare

B/cond

B/cond

BF, BT

BEQ, BNE, BC, BNC, B__Z BEQZ2, BNEZ2, BTEQZ2, BTNEZ2

Jump, jump register

MOV pc, ri

MOV pc, ri

BRA, JMP

BRA, JMP

B2, JR

Call, call register

BL

BL

BSR, JSR

BL, JL

JAL, JALR, JALX2

Trap

SWI

SWI

TRAPA

TRAP

BREAK

Return from interrupt

MOVS pc, r14

—1

RTS

RTE

—1

FIGURE E.3.8 Embedded RISC control instructions equivalent to MIPS core. Thumb and MIPS-16 are just 16-bit instruction subsets of the ARM and MIPS architectures, so machines can switch modes and execute the full instruction set. We use —1 to show sequences that are available in 32-bit mode but not 16-bit mode in Thumb or MIPS-16. The superscript 2 shows new instructions found only in 16-bit mode of Thumb or MIPS-16, such as BTEQZ2. Conventions

ARM v.4

Thumb

SuperH

M32R

MIPS-16

Return address reg.

R14

R14

PR (special)

R14

RA (special)

No-op

MOV r0, r0

MOV r0, r0

NOP

NOP

SLL r0, r0

Operands, order

OP Rd, Rs1, Rs2

OP Rd, Rs1

OP Rs1, Rd

OP Rd, Rs1

OP Rd, Rs1, Rs2

FIGURE E.3.9

Conventions of embedded RISC instructions equivalent to MIPS core.

As we shall see in Section E.9, one unusual feature of ARM is that every instruction has the option of executing conditionally depending on the condition codes. (This bears similarities to the annulling option of PA-RISC, seen in Section E.8.) Not surprisingly, Thumb follows ARM. The differences are that setting condition codes are not optional, the TEQ instruction is dropped, and there is no conditional execution of instructions. The Hitachi SuperH uses a single T-bit condition that is set by compare instructions. Two branch instructions decide to branch if either the T bit is 1 (BT) or the T bit is 0 (BF). The two flavors of branches allow fewer comparison instructions. Mitsubishi M32R also offers a single condition code bit (C) used for signed and unsigned comparisons (CMP, CMPI, CMPU, CMPUI) to see if one register is less than the other or not, similar to the MIPS set on less than instructions. Two branch instructions test to see if the C bit is 1 or 0: BC and BNC. The M32R also includes instructions to branch on equality or inequality of registers (BEQ and BNE) and all relations of a register to 0 (BGEZ, BGTZ, BLEZ, BLTZ, BEQZ, BNEZ). Unlike BC and BNC, these last instructions are all 32 bits wide. MIPS-16 keeps set on less than instructions (SLT, SLTI, SLTU, SLTIU), but instead of putting the result in one of the eight registers, it is placed in a special register named T. MIPS-16 is always implemented in machines that also have the full 32-bit MIPS instructions and registers; hence, register T is really register 24 in the full MIPS architecture. The MIPS-16 branch instructions test to see if a register is or is not equal to zero (BEQZ and BNEZ). There are also instructions that branch if register T is or is

E-16

Appendix E A Survey of RISC Architectures

Alpha

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

Number of condition code bits 0 (integer and FP)

8 FP

8 FP

8 × 4 both

2 × 4 integer, 4 × 2 FP

Basic compare instructions (integer and FP)

1 integer, 1 FP

1 integer, 1 FP

4 integer, 2 FP

4 integer, 2 FP

1 FP

Basic branch instructions (integer and FP)

1

2 integer, 1 FP

7 integer

1 both

3 integer, 1 FP

Compare register with register/const and branch

—

=, not=

=, not=, <, <=, >, >=, even, odd

—

—

Compare register to zero and branch

=, not=, <, <=, >, >=, even, odd

=, not=, <, <=, >, >=

=, not=, <, <=, >, >=, even, odd

—

=, not=, <, <=, >, >=

FIGURE E.3.10 Summary of five desktop RISC approaches to conditional branches. Floating-point branch on PA-RISC is accomplished by copying the FP status register into an integer register and then using the branch on bit instruction to test the FP comparison bit. Integer compare on SPARC is synthesized with an arithmetic instruction that sets the condition codes using r0 as the destination.

ARM v.4

Thumb

SuperH

M32R

MIPS-16

Number of condition code bits

4

4

1

1

1

Basic compare instructions

4

3

2

2

2

Basic branch instructions

1

1

2

3

2

Compare register with register/const and branch

—

—

=, >, >=

=, not=

—

Compare register to zero and branch

—

—

=, >, >=

=, not=, <, <=, >, >=

=, not=

FIGURE E.3.11

Summary of five embedded RISC approaches to conditional branches.

not equal to zero (BTEQZ and BTNEZ). To test if two registers are equal, MIPS added compare instructions (CMP, CMPI) that compute the exclusive OR of two registers and place the result in register T. Compare was added since MIPS-16 left out instructions to compare and branch if registers are equal or not (BEQ and BNE). Figures E.3.10 and E.3.11 summarize the schemes used for conditional branches.

E.4

Instructions: Multimedia Extensions of the Desktop/Server RISCs

Since every desktop microprocessor by definition has its own graphical displays, as transistor budgets increased it was inevitable that support would be added for graphics operations. Many graphics systems use eight bits to represent each of the three primary colors plus eight bits for the location of a pixel.

E.4

Instructions: Multimedia Extensions of the Desktop/Server RISCs

The addition of speakers and microphones for teleconferencing and video games suggested support of sound as well. Audio samples need more than eight bits of precision, but 16 bits are sufficient. Every microprocessor has special support so that bytes and halfwords take up less space when stored in memory, but due to the infrequency of arithmetic operations on these data sizes in typical integer programs, there is little support beyond data transfers. The architects of the Intel i860, which was justified as a graphical accelerator within the company, recognized that many graphics and audio applications would perform the same operation on vectors of this data. Although a vector unit was beyond the transistor budget of the i860 in 1989, by partitioning the carry chains within a 64-bit ALU, it could perform simultaneous operations on short vectors of eight 8-bit operands, four 16-bit operands, or two 32-bit operands. The cost of such partitioned ALUs was small. Applications that lend themselves to such support include MPEG (video), games like DOOM (3-D graphics), Adobe Photoshop (digital photography), and teleconferencing (audio and image processing). Like a virus, over time such multimedia support has spread to nearly every desktop microprocessor. HP was the first successful desktop RISC to include such support. As we shall see, this virus spread unevenly. The PowerPC is the only holdout, and rumors are that it is “running a fever.” These extensions have been called subword parallelism, vector, or SIMD (singleinstruction, multiple data) (see Chapter 7). Since Intel marketing uses SIMD to describe the MMX extension of the 8086, that has become the popular name. Figure E.4.1 summarizes the support by architecture. From Figure E.4.1, you can see that in general MIPS MDMX works on eight bytes or four halfwords per instruction, HP PA-RISC MAX2 works on four halfwords, SPARC VIS works on four halfwords or two words, and Alpha doesn’t do much. The Alpha MAX operations are just byte versions of compare, min, max, and absolute difference, leaving it up to software to isolate fields and perform parallel adds, subtracts, and multiplies on bytes and halfwords. MIPS also added operations to work on two 32-bit floating-point operands per cycle, but they are considered part of MIPS V and not simply multimedia extensions (see Section E.7). One feature not generally found in general-purpose microprocessors is saturating operations. Saturation means that when a calculation overflows, the result is set to the largest positive number or most negative number, rather than a modulo calculation as in two’s complement arithmetic. Commonly found in digital signal processors (see the next section), these saturating operations are helpful in routines for filtering. These machines largely used existing register sets to hold operands: integer registers for Alpha and HP PA-RISC and floating-point registers for MIPS and Sun. Hence data transfers are accomplished with standard load and store instructions. MIPS also added a 192-bit (3*64) wide register to act as an accumulator for some operations. By having three times the native data width, it can be partitioned to accumulate either eight bytes with 24 bits per field or four halfwords with 48 bits

E-17

E-18

Instruction category

Appendix E A Survey of RISC Architectures

Alpha MAX

MIPS MDMX

PA-RISC MAX2

Add/subtract

8B, 4H

4H

Saturating add/sub

8B, 4H

4H

Multiply

8B, 4H

Compare

8B (>=)

SPARC VIS 4H, 2W

4B/H

8B, 4H (=,<,<=)

4H, 2W (=, not=, >, <=)

Shift right/left

8B, 4H

4H

Shift right arithmetic

4H

4H

Multiply and add

8B, 4H

Shift and add (saturating)

PowerPC

4H

And/or/xor

8B, 4H, 2W

Absolute difference

8B

Max/min

8B, 4W

Pack (2n bits --> n bits)

2W->2B, 4H->4B 2*2W->4H, 2*4H->8B 2*4H->8B

2W->2H, 2W->2B, 4H->4B

Unpack/merge

8B, 4H, 2W

8B, 4H, 2W

2B->2W, 4B->4H

4B->4H, 2*4B->8B

8B

Permute/shuffle Register sets

8B, 4H, 2W

Integer

8B, 4H

2*4B->8B, 2*2H->4H 8B, 4H

4H

Fl. Pt. + 192b Acc.

Integer

Fl. Pt.

FIGURE E.4.1 Summary of multimedia support for desktop RISCs. B stands for byte (8 bits), H for halfword (16 bits), and W for word (32 bits). Thus 8B means an operation on eight bytes in a single instruction. Pack and unpack use the notation 2*2W to mean two operands each with two words. Note that MDMX has vector/scalar operations, where the scalar is specified as an element of one of the vector registers. This table is a simplification of the full multimedia architectures, leaving out many details. For example, MIPS MDMX includes instructions to multiplex between two operands, HP MAX2 includes an instruction to calculate averages, and SPARC VIS includes instructions to set registers to constants. Also, this table does not include the memory alignment operation of MDMX, MAX, and VIS.

per field. This wide accumulator can be used for add, subtract, and multiply/ add instructions. MIPS claims performance advantages of two to four times for the accumulator. Perhaps the surprising conclusion of this table is the lack of consistency. The only operations found on all four are the logical operations (AND, OR, XOR), which do not need a partitioned ALU. If we leave out the frugal Alpha, then the only other common operations are parallel adds and subtracts on four halfwords. Each manufacturer states that these are instructions intended to be used in hand-optimized subroutine libraries, an intention likely to be followed, as a compiler that works well with multimedia extensions of all desktop RISCs would be challenging.

E-19

E.5 Instructions: Digital Signal-Processing Extensions of the Embedded RISCs

E.5

Instructions: Digital Signal-Processing Extensions of the Embedded RISCs

One feature found in every digital signal processor (DSP) architecture is support for integer multiply-accumulate. The multiplies tend to be on shorter words than regular integers, such as 16 bits, and the accumulator tends to be on longer words, such as 64 bits. The reason for multiply-accumulate is to efficiently implement digital filters, common in DSP applications. Since Thumb and MIPS-16 are subset architectures, they do not provide such support. Instead, programmers should use the DSP or multimedia extensions found in the 32-bit mode instructions of ARM and MIPS-64. Figure E.5.1 shows the size of the multiply, the size of the accumulator, and the operations and instruction names for the embedded RISCs. Machines with accumulator sizes greater than 32 and less than 64 bits will force the upper bits to remain as the sign bits, thereby “saturating” the add to set to maximum and minimum fixed-point values if the operations overflow.

ARM v.4

Thumb

SuperH

M32R

MIPS-16

Size of multiply

32B × 32B

—

32B × 32B, 16B × 16B

32B × 16B, 16B × 16B

—

Size of accumulator

32B/64B

—

32B/42B, 48B/64B

56B

—

Accumulator name

Any GPR or pairs of GPRs

—

MACH, MACL

ACC

—

Operations

32B/64B product + 64B accumulate signed/ unsigned

—

32B product + 42B/32B accumulate (operands in memory); 64B product + 64B/48B accumulate (operands in memory); clear MAC

32B/48B product + 64B accumulate, round, move

—

Corresponding instruction names

MLA, SMLAL, UMLAL

—

MAC, MACS, MAC.L, MAC.LS, MACHI/MACLO, CLRMAC MACWHI/MACWLO, RAC, RACH, MVFACHI/ MVFACLO, MVTACHI/ MVTACLO

FIGURE E.5.1

Summary of five embedded RISC approaches to multiply-accumulate.

—

E-20

Appendix E A Survey of RISC Architectures

E.6

Instructions: Common Extensions to MIPS Core

Figures E.6.1 through E.6.7 list instructions not found in Figures E.3.5 through E.3.11 in the same four categories. Instructions are put in these lists if they appear in more than one of the standard architectures. The instructions are defined using the hardware description language defined in Figure E.6.8. Although most of the categories are self-explanatory, a few bear comment:

Name

■

The “atomic swap” row means a primitive that can exchange a register with memory without interruption. This is useful for operating system semaphores in a uniprocessor as well as for multiprocessor synchronization (see Section 2.11 in Chapter 2).

■

The 64-bit data transfer and operation rows show how MIPS, PowerPC, and SPARC define 64-bit addressing and integer operations. SPARC simply defines all register and addressing operations to be 64 bits, adding only special

Definition

Alpha

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

Atomic swap R/M (for locks and semaphores)

Temp<---Rd; Rd<–Mem[x]; LDL/Q_L; Mem[x]<---Temp STL/Q_C

LL; SC

—(see D.8)

LWARX; STWCX

CASA, CASX

Load 64-bit integer

Rd<–64 Mem[x]

LDQ

LD

LDD

LD

LDX

Store 64-bit integer

Mem[x]<---64 Rd

STQ

SD

STD

STD

STX

Load 32-bit integer unsigned

Rd32..63<–32 Mem[x]; Rd0..31<–32 0

LDL; EXTLL

LWU

LDW

LWZ

LDUW

Load 32-bit integer signed

Rd32..63<–32 Mem[x]; 32 Rd0..31<–32 Mem[x]0

LDL

LW

LDW; EXTRD,S 63, 8

LWA

LDSW

Prefetch

Cache[x]<–hint

FETCH, FETCH_M*

PREF, PREFX LDD, r0 LDW, r0

DCBT, DCBTST

PRE-FETCH

Load coprocessor

Coprocessor<– Mem[x]

—

LWCi

CLDWX, CLDWS

—

—

Store coprocessor

Mem[x]<– Coprocessor

—

SWCi

CSTWX, CSTWS

—

—

Endian

(Big/little endian?)

Either

Either

Either

Either

Either

Cache flush

(Flush cache block at this address)

ECB

CP0op

FDC, FIC

DCBF

FLUSH

Shared memory synchronization

(All prior data transfers WMB complete before next data transfer may start)

SYNC

SYNC

SYNC

MEMBAR

FIGURE E.6.1 Data transfer instructions not found in MIPS core but found in two or more of the five desktop architectures. The load linked/store conditional pair of instructions gives Alpha and MIPS atomic operations for semaphores, allowing data to be read from memory, modified, and stored without fear of interrupts or other machines accessing the data in a multiprocessor (see Chapter 2). Prefetching in the Alpha to external caches is accomplished with FETCH and FETCH_M; on-chip cache prefetches use LD_Q A, R31, and LD_Y A. F31 is used in the Alpha 21164 (see Bhandarkar [1995], p. 190).

E-21

E.6 Instructions: Common Extensions to MIPS Core

Name

Definition

Alpha

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

64-bit integer arithmetic ops

Rd<–64Rs1 op64 Rs2

ADD, SUB, MUL

DADD, DSUB ADD, SUB, DMULT, DDIV SHLADD, DS

ADD, SUBF, MULLD, DIVD

64-bit integer logical ops

Rd<–64Rs1 op64 Rs2

AND, OR, XOR

AND, OR, XOR

AND, OR, XOR

AND, OR, XOR AND, OR, XOR

64-bit shifts

Rd<–64Rs1 op64 Rs2

SLL, SRA, SRL

DSLL/V, DSRA/V, DSRL/V

DEPD,Z EXTRD,S EXTRD,U

SLD, SRAD, SRLD

SLLX, SRAX, SRLX

Conditional move

if (cond) Rd<–Rs

CMOV_

MOVN/Z

SUBc, n; ADD

—

MOVcc, MOVr

Support for multiword integer add

CarryOut, Rd <– Rs1 + Rs2 + OldCarryOut

—

ADU; SLTU; ADDC ADDU, DADU; SLTU; DADDU

ADDC, ADDE

ADDcc

Support for multiword integer sub

CarryOut, Rd <– Rs1 Rs2 + OldCarryOut

—

SUBU; SLTU; SUBB SUBU, DSUBU; SLTU; DSUBU

SUBFC, SUBFE SUBcc

And not

Rd <– Rs1 & ~(Rs2)

BIC

—

ANDCM

ANDC

ANDN

Or not

Rd <– Rs1 | ~(Rs2)

ORNOT

—

—

ORC

ORN

—

—

ADDIL (R-I)

ADDIS (R-I)

—

COPi

COPR,i

—

IMPDEPi

Add high immediate Rd0..15<–Rs10..15 + (Const<<16); Coprocessor operations

(Defined by coprocessor) —

ADD, SUB, MULX, S/UDIVX

FIGURE E.6.2 Arithmetic/logical instructions not found in MIPS core but found in two or more of the five desktop architectures. Alpha

MIPS-64

PA-RISC 2.0

PowerPC

SPARC v.9

Optimized delayed branches

Name

(Branch not always delayed)

Definition

—

BEQL, BNEL, B_ZL (<, >, <=, >=)

COMBT, n, COMBF, n

—

BPcc, A, FPBcc, A

Conditional trap

if (COND) {R31<---PC; PC <–0..0#i}

—

T_,,T_I (=, not=, <, >, <=, >=)

SUBc, n; BREAK

TW, TD, TWI, TDI

Tcc

No. control registers

Misc. regs (virtual memory, interrupts, . . .)

6

equiv. 12

32

33

29

FIGURE E.6.3 Control instructions not found in MIPS core but found in two or more of the five desktop architectures.

instructions for 64-bit shifts, data transfers, and branches. MIPS includes the same extensions, plus it adds separate 64-bit signed arithmetic instructions. PowerPC adds 64-bit right shift, load, store, divide, and compare and has a separate mode determining whether instructions are interpreted as 32- or 64-bit operations; 64-bit operations will not work in a machine that only

E-22

Appendix E A Survey of RISC Architectures

Name

Definition

Alpha

MIPS-64

PA-RISC 2.0

PowerPC

Multiply and add

Fd <– ( Fs1 × Fs2) + Fs3

—

MADD.S/D

FMPYFADD sgl/dbl FMADD/S

Multiply and sub

Fd <– ( Fs1 × Fs2) – Fs3

—

MSUB.S/D

FMSUB/S

—

NMADD.S/D

FMPYFNEG sgl/dbl FNMADD/S FNMSUB/S

SPARC v.9

Neg mult and add Fd <– -(( Fs1 × Fs2) + Fs3) Neg mult and sub Fd <– -(( Fs1 × Fs2) – Fs3) Square root Fd <– SQRT(Fs)

—

NMSUB.S/D

SQRT_

SQRT.S/D

FSQRT sgl/dbl

FSQRT/S

FSQRTS/D

Conditional move

if (cond) Fd<–Fs

FCMOV_

MOVF/T, MOVF/T.S/D

FTESTFCPY

—

FMOVcc

Negate

Fd <– Fs ^ x80000000

CPYSN

NEG.S/D

FNEG sgl/dbl

FNEG

FNEGS/D/Q

Absolute value

Fd <– Fs & x7FFFFFFF

—

ABS.S/D

FABS/dbl

FABS

FABSS/D/Q

FIGURE E.6.4 Floating-point instructions not found in MIPS core but found in two or more of the five desktop architectures. Name

Definition

ARM v.4

Thumb

SuperH

SWP, SWPB

—

(see TAS)

Memory management unit Paged address translation

Via coprocessor instructions

—1

LDTLB

Endian

Either

Either

Either

Atomic swap R/M (for semaphores)

Temp<–Rd; Rd<–Mem[x]; Mem[x]<–Temp

(Big/little endian?)

1

M32R LOCK; UNLOCK

MIPS-16

—1 —1

Big

Either

FIGURE E.6.5 Data transfer instructions not found in MIPS core but found in two or more of the five embedded architectures. We use —1 to show sequences that are available in 32-bit mode but not 16-bit mode in Thumb or MIPS-16.

supports 32-bit mode. PA-RISC is expanded to 64-bit addressing and operations in version 2.0. ■

The “prefetch” instruction supplies an address and hint to the implementation about the data. Hints include whether the data is likely to be read or written soon, likely to be read or written only once, or likely to be read or written many times. Prefetch does not cause exceptions. MIPS has a version that adds two registers to get the address for floating-point programs, unlike nonfloating-point MIPS programs.

■

In the “Endian” row, “Big/little” means there is a bit in the program status register that allows the processor to act either as big endian or little endian (see Appendix B). This can be accomplished by simply complementing some of the least significant bits of the address in data transfer instructions.

E-23

E.6 Instructions: Common Extensions to MIPS Core

■

The “shared memory synchronization” helps with cache-coherent multiprocessors: all loads and stores executed before the instruction must complete before loads and stores after it can start. (See Chapter 2.)

■

The “coprocessor operations” row lists several categories that allow for the processor to be extended with special-purpose hardware. Name

Definition

ARM v.4

Thumb

SuperH

M32R

MIPS-16

Load immediate

Rd<---Imm

MOV

MOV

MOV, MOVA

LDI, LD24

Support for multiword integer add

CarryOut, Rd <--- Rd + Rs1 + OldCarryOut

ADCS

ADC

ADDC

ADDX

—1

Support for multiword integer sub

CarryOut, Rd <--- Rd – Rs1 + OldCarryOut

SBCS

SBC

SUBC

SUBX

—1

Negate

Rd <--- 0 – Rs1

NEG2

NEG

NEG

NEG

Not

Rd <--- ~(Rs1)

MVN

MVN

NOT

NOT

NOT

Move

Rd <--- Rs1

MOV

MOV

MOV

MV

MOVE

Rotate right

Rd <--- Rs i, >> Rd0. . . i–1 <--Rs31–i. . . 31

ROR

ROR

ROTC

And not

Rd <--- Rs1 & ~(Rs2)

BIC

BIC

LI

FIGURE E.6.6 Arithmetic/logical instructions not found in MIPS core but found in two or more of the five embedded architectures. We use —1 to show sequences that are available in 32-bit mode but not in 16-bit mode in Thumb or MIPS-16. The superscript 2 shows new instructions found only in 16-bit mode of Thumb or MIPS-16, such as NEG2 . Name

Definition

ARM v.4

Thumb

SuperH

M32R

MIPS-16

No. control registers

Misc. registers

21

29

9

5

36

FIGURE E.6.7

Control information in the five embedded architectures.

One difference that needs a longer explanation is the optimized branches. Figure E.6.9 shows the options. The Alpha and PowerPC offer branches that take effect immediately, like branches on earlier architectures. To accelerate branches, these machines use branch prediction (see Chapter 4). All the rest of the desktop RISCs offer delayed branches (see Appendix B). The embedded RISCs generally do not support delayed branch, with the exception of SuperH, which has it as an option. The other three desktop RISCs provide a version of delayed branch that makes it easier to fill the delay slot. The SPARC “annulling” branch executes the instruction in the delay slot only if the branch is taken; otherwise the instruction is annulled. This means the instruction at the target of the branch can safely be copied into the delay slot, since it will only be executed if the branch is taken. The restrictions are that the target is not another branch and that the target is known at compile time. (SPARC also offers a nondelayed jump because an unconditional branch with the annul bit set does not execute the following instruction.) Later versions of the MIPS

E-24

Appendix E A Survey of RISC Architectures

Notation

Meaning

Example

Meaning

<--

Data transfer. Length of transfer is given by Regs[R1]<--Regs[R2]; the destination’s length; the length is specified when not clear.

Transfer contents of R2 to R1. Registers have a fixed length, so transfers shorter than the register size must indicate which bits are used.

M

Array of memory accessed in bytes. The starting address for a transfer is indicated as the index to the memory array.

Regs[R1]<--M[x];

Place contents of memory location x into R1. If a transfer starts at M[i] and requires 4 bytes, the transferred bytes are M[i], M[i+1], M[i+2], and M[i+3].

<--n

Transfer an n-bit field, used whenever length of transfer is not clear.

M[y]<--16M[x];

Transfer 16 bits starting at memory location x to memory location y. The length of the two sides should match.

Xn

Subscript selects a bit.

Regs[R1]0<--0;

Change sign bit of R1 to 0. (Bits are numbered from MSB starting at 0.)

Xm..n

Subscript selects a field.

Regs[R3]24..31<--M[x];

Moves contents of memory location x into low-order byte of R3.

Xn

Superscript replicates a bit field.

Regs[R3]0..23<--024;

##

Concatenates two fields.

Regs[R3]<--240## M[x]; F2##F3<--64M[x];

Sets high-order three bytes of R3 to 0. Moves contents of location x into low byte of R3; clears upper three bytes. Moves 64 bits from memory starting at location x; 1st 32 bits go into F2, 2nd 32 into F3.

*, &

Dereference a pointer; get the address of a variable.

p*<--&x;

Assign to object pointed to by p the address of the variable x.

<<, >>

C logical shifts (left, right).

Regs[R1] << 5

Shift R1 left 5 bits.

==, !=, >, <, >=, <=

C relational operators; equal, not equal, greater, less, greater or equal, less or equal.

(Regs[R1]== Regs[R2]) & (Regs[R3]!=Regs[R4])

True if contents of R1 equal the contents of R2 and contents of R3 do not equal the contents of R4.

&, |, ^, !

C bitwise logical operations: AND, OR, exclusive OR, and complement.

(Regs[R1] & (Regs[R2]| Regs[R3]))

Bitwise AND of R1 and bitwise OR of R2 and R3.

FIGURE E.6.8

Hardware description notation (and some standard C operators).

(Plain) branch

Delayed branch

Annulling delayed branch

Found in architectures

Alpha, PowerPC, ARM, Thumb, MIPS-64, PA-RISC, SuperH, M32R, MIPS-16 SPARC, SuperH

MIPS-64, SPARC

PA-RISC

Execute following instruction

Only if branch not taken

Only if branch taken

If forward branch not taken or backward branch taken

FIGURE E.6.9

Always

When the instruction following the branch is executed for three types of branches.

E.7 Instructions Unique to MIPS-64

architecture have added a branch likely instruction that also annuls the following instruction if the branch is not taken. PA-RISC allows almost any instruction to annul the next instruction, including branches. Its “nullifying” branch option will execute the next instruction depending on the direction of the branch and whether it is taken (i.e., if a forward branch is not taken or a backward branch is taken). Presumably this choice was made to optimize loops, allowing the instructions following the exit branch and the looping branch to execute in the common case. Now that we have covered the similarities, we will focus on the unique features of each architecture. We first cover the desktop/server RISCs, ordering them by length of description of the unique features from shortest to longest, and then the embedded RISCs.

E.7

Instructions Unique to MIPS-64

MIPS has gone through five generations of instruction sets, and this evolution has generally added features found in other architectures. Here are the salient unique features of MIPS, the first several of which were found in the original instruction set.

Nonaligned Data Transfers MIPS has special instructions to handle misaligned words in memory. A rare event in most programs, it is included for supporting 16-bit minicomputer applications and for doing memcpy and strcpy faster. Although most RISCs trap if you try to load a word or store a word to a misaligned address, on all architectures misaligned words can be accessed without traps by using four load byte instructions and then assembling the result using shifts and logical ORs. The MIPS load and store word left and right instructions (LWL, LWR, SWL, SWR) allow this to be done in just two instructions: LWL loads the left portion of the register and LWR loads the right portion of the register. SWL and SWR do the corresponding stores. Figure E.7.1 shows how they work. There are also 64-bit versions of these instructions.

Remaining Instructions Below is a list of the remaining unique details of the MIPS-64 architecture: ■

NOR—This logical instruction calculates ~(Rs1 | Rs2).

■

Constant shift amount—Nonvariable shifts use the 5-bit constant field shown in the register-register format in Figure E.2.3.

■

SYSCALL—This special trap instruction is used to invoke the operating system.

E-25

E-26

Appendix E A Survey of RISC Architectures

Case 1 Before

Case 2 Before

M[100]

D

A

V

M[200]

100 101 102 103 M[104]

200 201 202 203 M[204]

E 104 105 106 107

R2

After

J

O

H

After

D

A

V

R2

D

A

V

R4

After

After E

V

E

J

O

H

N

LWL R4, 203: R4

N

LWR R2, 104:

A

204 205 206 207

N

LWL R2, 101: R2

D

D

O

H

N

LWR R4, 206: R4

D

A

V

E

FIGURE E.7.1 MIPS instructions for unaligned word reads. This figure assumes operation in big-endian mode. Case 1 first loads the three bytes 101, 102, and 103 into the left of R2, leaving the least significant byte undisturbed. The following LWR simply loads byte 104 into the least significant byte of R2, leaving the other bytes of the register unchanged using LWL. Case 2 first loads byte 203 into the most significant byte of R4, and the following LWR loads the other three bytes of R4 from memory bytes 204, 205, and 206. LWL reads the word with the first byte from memory, shifts to the left to discard the unneeded byte(s), and changes only those bytes in Rd. The byte(s) transferred are from the first byte to the lowest-order byte of the word. The following LWR addresses the last byte, right-shifts to discard the unneeded byte(s), and finally changes only those bytes of Rd. The byte(s) transferred are from the last byte up to the highestorder byte of the word. Store word left (SWL) is simply the inverse of LWL, and store word right (SWR) is the inverse of LWR. Changing to little-endian mode flips which bytes are selected and discarded. (If big-little, left-right, load-store seem confusing, don’t worry; they work!)

■

Move to/from control registers—CTCi and CFCi move between the integer registers and control registers.

■

Jump/call not PC-relative—The 26-bit address of jumps and calls is not added to the PC. It is shifted left two bits and replaces the lower 28 bits of the PC. This would only make a difference if the program were located near a 256 MB boundary.

■

TLB instructions—Translation-lookaside buffer (TLB) misses were handled in software in MIPS I, so the instruction set also had instructions for manipulating the registers of the TLB (see Chapter 7 for more on TLBs). These registers are considered part of the “system coprocessor.” Since MIPS I

E.8

Instructions Unique to Alpha

the instructions differ among versions of the architecture; they are more part of the implementations than part of the instruction set architecture. ■

Reciprocal and reciprocal square root—These instructions, which do not follow IEEE 754 guidelines of proper rounding, are included apparently for applications that value speed of divide and square root more than they value accuracy.

■

Conditional procedure call instructions—BGEZAL saves the return address and branches if the content of Rs1 is greater than or equal to zero, and BLTZAL does the same for less than zero. The purpose of these instructions is to get a PC-relative call. (There are “likely” versions of these instructions as well.)

■

Parallel single precision floating-point operations—As well as extending the architecture with parallel integer operations in MDMX, MIPS-64 also supports two parallel 32-bit floating-point operations on 64-bit registers in a single instruction. “Paired single” operations include add (ADD.PS), subtract (SUB.PS), compare (C.__.PS), convert (CVT.PS.S, CVT.S.PL, CVT.S.PU), negate (NEG.PS), absolute value (ABS.PS), move (MOV.PS, MOVF.PS, MOVT.PS), multiply (MUL.PS), multiply-add (MADD.PS), and multiply-subtract (MSUB.PS).

There is no specific provision in the MIPS architecture for floating-point execution to proceed in parallel with integer execution, but the MIPS implementations of floating point allow this to happen by checking to see if arithmetic interrupts are possible early in the cycle. Normally, exception detection would force serialization of execution of integer and floating-point operations.

E.8

Instructions Unique to Alpha

The Alpha was intended to be an architecture that made it easy to build highperformance implementations. Toward that goal, the architects originally made two controversial decisions: imprecise floating-point exceptions and no byte or halfword data transfers. To simplify pipelined execution, Alpha does not require that an exception act as if no instructions past a certain point are executed and that all before that point have been executed. It supplies the TRAPB instruction, which stalls until all prior arithmetic instructions are guaranteed to complete without incurring arithmetic exceptions. In the most conservative mode, placing one TRAPB per exceptioncausing instruction slows execution by roughly five times but provides precise exceptions (see Darcy and Gay [1996]).

E-27

E-28

Appendix E A Survey of RISC Architectures

Code that does not include TRAPB does not obey the IEEE 754 floating-point standard. The reason is that parts of the standard (NaNs, infinities, and denormals) are implemented in software on Alpha, as they are on many other microprocessors. To implement these operations in software, however, programs must find the offending instruction and operand values, which cannot be done with imprecise interrupts! When the architecture was developed, it was believed by the architects that byte loads and stores would slow down data transfers. Byte loads require an extra shifter in the data transfer path, and byte stores require that the memory system perform a read-modify-write for memory systems with error correction codes, since the new ECC value must be recalculated. This omission meant that byte stores required the sequence load word, replaced the desired byte, and then stored the word. (Inconsistently, floating-point loads go through considerable byte swapping to convert the obtuse VAX floating-point formats into a canonical form.) To reduce the number of instructions to get the desired data, Alpha includes an elaborate set of byte manipulation instructions: extract field and zero rest of a register (EXTxx), insert field (INSxx), mask rest of a register (MSKxx), zero fields of a register (ZAP), and compare multiple bytes (CMPGE). Apparently, the implementors were not as bothered by load and store byte as were the original architects. Beginning with the shrink of the second version of the Alpha chip (21164A), the architecture does include loads and stores for bytes and halfwords.

Remaining Instructions Below is a list of the remaining unique instructions of the Alpha architecture: ■

PAL code—To provide the operations that the VAX performed in microcode, Alpha provides a mode that runs with all privileges enabled, interrupts disabled, and virtual memory mapping turned off for instructions. PAL (privileged architecture library) code is used for TLB management, atomic memory operations, and some operating system primitives. PAL code is called via the CALL_PAL instruction.

■

No divide—Integer divide is not supported in hardware.

■

“Unaligned” load-store—LDQ_U and STQ_U load and store 64-bit data using addresses that ignore the least significant three bits. Extract instructions then select the desired unaligned word using the lower address bits. These instructions are similar to LWL/R, SWL/R in MIPS.

■

Floating-point single precision represented as double precision—Single precision data is kept as conventional 32-bit formats in memory but is converted to 64-bit double precision format in registers.

■

Floating-point register F31 is fixed at zero—To simplify comparisons to zero.

E.9

Instructions Unique to SPARC v.9

■

VAX floating-point formats—To maintain compatibility with the VAX architecture, in addition to the IEEE 754 single and double precision formats called S and T, Alpha supports the VAX single and double precision formats called F and G, but not VAX format D. (D had too narrow an exponent field to be useful for double precision and was replaced by G in VAX code.)

■

Bit count instructions—Version 3 of the architecture added instructions to count the number of leading zeros (CTLZ), count the number of trailing zeros (CTTZ), and count the number of ones in a word (CTPOP). Originally found on Cray computers, these instructions help with decryption.

E.9

Instructions Unique to SPARC v.9

Several features are unique to SPARC.

Register Windows The primary unique feature of SPARC is register windows, an optimization for reducing register traffic on procedure calls. Several banks of registers are used, with a new one allocated on each procedure call. Although this could limit the depth of procedure calls, the limitation is avoided by operating the banks as a circular buffer, providing unlimited depth. The knee of the cost/performance curve seems to be six to eight banks. SPARC can have between 2 and 32 windows, typically using 8 registers each for the globals, locals, incoming parameters, and outgoing parameters. (Given that each window has 16 unique registers, an implementation of SPARC can have as few as 40 physical registers and as many as 520, although most have 128 to 136, so far.) Rather than tie window changes with call and return instructions, SPARC has the separate instructions SAVE and RESTORE. SAVE is used to “save” the caller’s window by pointing to the next window of registers in addition to performing an add instruction. The trick is that the source registers are from the caller’s window of the addition operation, while the destination register is in the callee’s window. SPARC compilers typically use this instruction for changing the stack pointer to allocate local variables in a new stack frame. RESTORE is the inverse of SAVE, bringing back the caller’s window while acting as an add instruction, with the source registers from the callee’s window and the destination register in the caller’s window. This automatically deallocates the stack frame. Compilers can also make use of it for generating the callee’s final return value. The danger of register windows is that the larger number of registers could slow down the clock rate. This was not the case for early implementations. The SPARC architecture (with register windows) and the MIPS R2000 architecture (without)

E-29

E-30

Appendix E A Survey of RISC Architectures

have been built in several technologies since 1987. For several generations, the SPARC clock rate has not been slower than the MIPS clock rate for implementations in similar technologies, probably because cache access times dominate register access times in these implementations. The current-generation machines took different implementation strategies—in order versus out of order—and it’s unlikely that the number of registers by themselves determined the clock rate in either machine. Recently, other architectures have included register windows: Tensilica and IA-64. Another data transfer feature is alternate space option for loads and stores. This simply allows the memory system to identify memory accesses to input/ output devices, or to control registers for devices such as the cache and memory management unit.

Fast Traps Version 9 SPARC includes support to make traps fast. It expands the single level of traps to at least four levels, allowing the window overflow and underflow trap handlers to be interrupted. The extra levels mean the handler does not need to check for page faults or misaligned stack pointers explicitly in the code, thereby making the handler faster. Two new instructions were added to return from this multilevel handler: RETRY (which retries the interrupted instruction) and DONE (which does not). To support user-level traps, the instruction RETURN will return from the trap in nonprivileged mode.

Support for LISP and Smalltalk The primary remaining arithmetic feature is tagged addition and subtraction. The designers of SPARC spent some time thinking about languages like LISP and Smalltalk, and this influenced some of the features of SPARC already discussed: register windows, conditional trap instructions, calls with 32-bit instruction addresses, and multiword arithmetic (see Taylor, et al. [1986] and Ungar, et al. [1984]). A small amount of support is offered for tagged data types with operations for addition, subtraction, and, hence, comparison. The two least significant bits indicate whether the operand is an integer (coded as 00), so TADDcc and TSUBcc set the overflow bit if either operand is not tagged as an integer or if the result is too large. A subsequent conditional branch or trap instruction can decide what to do. (If the operands are not integers, software recovers the operands, checks the types of the operands, and invokes the correct operation based on those types.) It turns out that the misaligned memory access trap can also be put to use for tagged data, since loading from a pointer with the wrong tag can be an invalid access. Figure E.9.1 shows both types of tag support.

E.9

Instructions Unique to SPARC v.9

a. Add, sub, or compare integers (coded as 00)

00

(R5)

00

(R6)

00

(R7)

11

(R4)

TADDcc r7, r5, r6

b. Loading via valid pointer (coded as 11) –

3

LD rD, r4, –3 00

(Word address)

FIGURE E.9.1 SPARC uses the two least significant bits to encode different data types for the tagged arithmetic instructions. a. Integer arithmetic takes a single cycle as long as the operands and the result are integers. b. The misaligned trap can be used to catch invalid memory accesses, such as trying to use an integer as a pointer. For languages with paired data like LISP, an offset of –3 can be used to access the even word of a pair (CAR) and +1 can be used for the odd word of a pair (CDR).

Overlapped Integer and Floating-Point Operations SPARC allows floating-point instructions to overlap execution with integer instructions. To recover from an interrupt during such a situation, SPARC has a queue of pending floating-point instructions and their addresses. RDPR allows the processor to empty the queue. The second floating-point feature is the inclusion of floatingpoint square root instructions FSQRTS, FSQRTD, and FSQRTQ.

Remaining Instructions The remaining unique features of SPARC are as follows: ■ JMPL

uses Rd to specify the return address register, so specifying r31 makes it similar to JALR in MIPS and specifying r0 makes it like JR.

■ LDSTUB

loads the value of the byte into Rd and then stores FF16 into the addressed byte. This version 8 instruction can be used to implement synchronization (see Chapter 2).

■

CASA (CASXA) atomically compares a value in a processor register to a 32-bit (64-bit) value in memory; if and only if they are equal, it swaps the value in memory with the value in a second processor register. This version 9

E-31

E-32

Appendix E A Survey of RISC Architectures

instruction can be used to construct wait-free synchronization algorithms that do not require the use of locks. ■ XNOR calculates the exclusive OR with the complement of the second operand. ■ BPcc, BPr, and FBPcc include a branch prediction bit so that the compiler

can give hints to the machine about whether a branch is likely to be taken or not. ■ ILLTRAP

causes an illegal instruction trap. Muchnick [1988] explains how this is used for proper execution of aggregate returning procedures in C.

■ POPC

counts the number of bits set to one in an operand, also found in the third version of the Alpha architecture.

■

Nonfaulting loads allow compilers to move load instructions ahead of conditional control structures that control their use. Hence, nonfaulting loads will be executed speculatively.

■

Quadruple precision floating-point arithmetic and data transfer allow the floating-point registers to act as eight 128-bit registers for floating-point operations and data transfers.

■

Multiple precision floating-point results for multiply mean that two single precision operands can result in a double precision product and two double precision operands can result in a quadruple precision product. These instructions can be useful in complex arithmetic and some models of floatingpoint calculations.

E.10

Instructions Unique to PowerPC

PowerPC is the result of several generations of IBM commercial RISC machines— IBM RT/PC, IBM Power1, and IBM Power2—plus the Motorola 8800.

Branch Registers: Link and Counter Rather than dedicate one of the 32 general-purpose registers to save the return address on procedure call, PowerPC puts the address into a special register called the link register. Since many procedures will return without calling another procedure, the link doesn’t always have to be saved. Making the return address a special register makes the return jump faster, since the hardware need not go through the register read pipeline stage for return jumps. In a similar vein, PowerPC has a count register to be used in for loops where the program iterates a fixed number of times. By using a special register, the branch

E.10

Instructions Unique to PowerPC

hardware can determine quickly whether a branch based on the count register is likely to branch, since the value of the register is known early in the execution cycle. Tests of the value of the count register in a branch instruction will automatically decrement the count register. Given that the count register and link register are already located with the hardware that controls branches, and that one of the problems in branch prediction is getting the target address early in the pipeline (see Appendix B), the PowerPC architects decided to make a second use of these registers. Either register can hold a target address of a conditional branch. Thus, PowerPC supplements its basic conditional branch with two instructions that get the target address from these registers (BCLR, BCCTR).

Remaining Instructions Unlike most other RISC machines, register 0 is not hardwired to the value 0. It cannot be used as a base register—that is, it generates a 0 in this case—but in base + index addressing it can be used as the index. The other unique features of the PowerPC are as follows: ■

Load multiple and store multiple save or restore up to 32 registers in a single instruction.

■ LSW

and STSW permit fetching and storing of fixed- and variable-length strings that have arbitrary alignment.

■

Rotate with mask instructions support bit field extraction and insertion. One version rotates the data and then performs logical AND with a mask of ones, thereby extracting a field. The other version rotates the data but only places the bits into the destination register where there is a corresponding 1 bit in the mask, thereby inserting a field.

■

Algebraic right shift sets the carry bit (CA) if the operand is negative and any 1 bits are shifted out. Thus, a signed divide by any constant power of two that rounds toward 0 can be accomplished with an SRAWI followed by ADDZE, which adds CA to the register.

■ CBTLZ

will count leading zeros.

■ SUBFIC

computes (immediate – RA), which can be used to develop a one’s or two’s complement.

■

Logical shifted immediate instructions shift the 16-bit immediate to the left 16 bits before performing AND, OR, or XOR.

E-33

E-34

Appendix E A Survey of RISC Architectures

E.11

Instructions Unique to PA-RISC 2.0

PA-RISC was expanded slightly in 1990 with version 1.1 and changed significantly in 2.0 with 64-bit extensions in 1996. PA-RISC perhaps has the most unusual features of any desktop RISC machine. For example, it has the most addressing modes and instruction formats, and, as we shall see, several instructions that are really the combination of two simpler instructions.

Nullification As shown in Figure E.6.9, several RISC machines can choose not to execute the instruction following a delayed branch to improve utilization of the branch slot. This is called nullification in PA-RISC, and it has been generalized to apply to any arithmetic/logical instruction as well as to all branches. Thus, an add instruction can add two operands, store the sum, and cause the following instruction to be skipped if the sum is zero. Like conditional move instructions, nullification allows PA-RISC to avoid branches in cases where there is just one instruction in the then part of an if statement.

A Cornucopia of Conditional Branches Given nullification, PA-RISC did not need to have separate conditional branch instructions. The inventors could have recommended that nullifying instructions precede unconditional branches, thereby simplifying the instruction set. Instead, PA-RISC has the largest number of conditional branches of any RISC machine. Figure E.11.1 shows the conditional branches of PA-RISC. As you can see, several are really combinations of two instructions.

Synthesized Multiply and Divide PA-RISC provides several primitives so that multiply and divide can be synthesized in software. Instructions that shift one operand 1, 2, or 3 bits and then add, trapping or not on overflow, are useful in multiplies. (Alpha also includes instructions that multiply the second operand of adds and subtracts by 4 or by 8: S4ADD, S8ADD, S4SUB, and S8SUB.) The divide step performs the critical step of nonrestoring divide, adding or subtracting depending on the sign of the prior result. Magenheimer, et al. [1988] measured the size of operands in multiplies and divides to show how well the multiply step would work. Using this data for C programs, Muchnick [1988] found that by making special cases, the average multiply by a constant takes 6 clock cycles and the multiply of variables takes 24 clock cycles. PA-RISC has ten instructions for these operations.

E.11 Instructions Unique to PA-RISC 2.0

Name

Instruction

COMB COMIB

Compare and branch

MOVB MOVIB

Move and branch

ADDB ADDIB

Add and branch

BB BVB

Branch on bit

Compare immediate and branch Move immediate and branch Add immediate and branch Branch on variable bit

E-35

Notation if (cond(Rs1,Rs2)) if (cond(imm5,Rs2))

{PC <-- PC + offset12} {PC <-- PC + offset12}

Rs2 <-- Rs1, if (cond(Rs1,0)) Rs2 <-- imm5, if (cond(imm5,0))

{PC <-- PC + offset12} {PC <-- PC + offset12}

Rs2 <-- Rs1 + Rs2, if (cond(Rs1 + Rs2,0)) Rs2 <-- imm5 + Rs2, if (cond(imm5 + Rs2,0))

{PC <-- PC + offset12} {PC <-- PC + offset12}

if (cond(Rsp,0)) if (cond(Rssar,0))

{PC <-- PC + offset12} {PC <-- PC + offset12}

FIGURE E.11.1 The PA-RISC conditional branch instructions. The 12-bit offset is called offset12 in this table, and the 5-bit immediate is called imm5. The 16 conditions are =, <, <=, odd, signed overflow, unsigned no overflow, zero or no overflow unsigned, never, and their respective complements. The BB instruction selects one of the 32 bits of the register and branches depending if its value is 0 or 1. The BVB selects the bit to branch using the shift amount register, a special-purpose register. The subscript notation specifies a bit field.

The original SPARC architecture used similar optimizations, but with increasing numbers of transistors the instruction set was expanded to include full multiply and divide operations. PA-RISC gives some support along these lines by putting a full 32-bit integer multiply in the floating-point unit; however, the integer data must first be moved to floating-point registers.

Decimal Operations COBOL programs will compute on decimal values, stored as four bits per digit, rather than converting back and forth between binary and decimal. PA-RISC has instructions that will convert the sum from a normal 32-bit add into proper decimal digits. It also provides logical and arithmetic operations that set the condition codes to test for carries of digits, bytes, or halfwords. These operations also test whether bytes or halfwords are zero. These operations would be useful in arithmetic on 8-bit ASCII characters. Five PA-RISC instructions provide decimal support.

Remaining Instructions Here are some remaining PA-RISC instructions: ■

Branch vectored shifts an index register left three bits, adds it to a base register, and then branches to the calculated address. It is used for case statements.

■

Extract and deposit instructions allow arbitrary bit fields to be selected from or inserted into registers. Variations include whether the extracted field is sign-extended, whether the bit field is specified directly in the instruction or indirectly in another register, and whether the rest of the register is set to zero or left unchanged. PA-RISC has 12 such instructions.

E-36

Appendix E A Survey of RISC Architectures

■

To simplify use of 32-bit address constants, PA-RISC includes ADDIL, which adds a left-adjusted 21-bit constant to a register and places the result in register 1. The following data transfer instruction uses offset addressing to add the lower 11 bits of the address to register 1. This pair of instructions allows PA-RISC to add a 32-bit constant to a base register, at the cost of changing register 1.

■

PA-RISC has nine debug instructions that can set breakpoints on instruction or data addresses and return the trapped addresses.

■

Load and clear instructions provide a semaphore or lock that reads a value from memory and then writes zero.

■

Store bytes short optimizes unaligned data moves, moving either the leftmost or the rightmost bytes in a word to the effective address, depending on the instruction options and condition code bits.

■

Loads and stores work well with caches by having options that give hints about whether to load data into the cache if it’s not already in the cache. For example, a load with a destination of register 0 is defined to be a softwarecontrolled cache prefetch.

■

PA-RISC 2.0 extended cache hints to stores to indicate block copies, recommending that the processor not load data into the cache if it’s not already in the cache. It also can suggest that on loads and stores, there is spatial locality to prepare the cache for subsequent sequential accesses.

■

PA-RISC 2.0 also provides an optional branch target stack to predict indirect jumps used on subroutine returns. Software can suggest which addresses get placed on and removed from the branch target stack, but hardware controls whether or not these are valid.

■

Multiply/add and multiply/subtract are floating-point operations that can launch two independent floating-point operations in a single instruction in addition to the fused multiply/add and fused multiply/negate/add introduced in version 2.0 of PA-RISC.

E.12

Instructions Unique to ARM

It’s hard to pick the most unusual feature of ARM, but perhaps it is the conditional execution of instructions. Every instruction starts with a 4-bit field that determines whether it will act as a nop or as a real instruction, depending on the condition codes. Hence, conditional branches are properly considered as conditionally executing the unconditional branch instruction. Conditional execution allows

E.12

Instructions Unique to ARM

avoiding a branch to jump over a single instruction. It takes less code space and time to simply conditionally execute one instruction. The 12-bit immediate field has a novel interpretation. The eight least significant bits are zero-extended to a 32-bit value, then rotated right the number of bits specified in the first four bits of the field multiplied by two. Whether this split actually catches more immediates than a simple 12-bit field would be an interesting study. One advantage is that this scheme can represent all powers of two in a 32-bit word. Operand shifting is not limited to immediates. The second register of all arithmetic and logical processing operations has the option of being shifted before being operated on. The shift options are shift left logical, shift right logical, shift right arithmetic, and rotate right. Once again, it would be interesting to see how often operations like rotate-and-add, shift-right-and-test, and so on occur in ARM programs.

Remaining Instructions Below is a list of the remaining unique instructions of the ARM architecture: ■

Block loads and stores—Under control of a 16-bit mask within the instructions, any of the 16 registers can be loaded or stored into memory in a single instruction. These instructions can save and restore registers on procedure entry and return. These instructions can also be used for block memory copy—offering up to four times the bandwidth of a single register loadstore—and today, block copies are the most important use.

■

Reverse subtract—RSB allows the first register to be subtracted from the immediate or shifted register. RSC does the same thing, but includes the carry when calculating the difference.

■

Long multiplies—Similar to MIPS, Hi and Lo registers get the 64-bit signed product (SMULL) or the 64-bit unsigned product (UMULL).

■

No divide—Like the Alpha, integer divide is not supported in hardware.

■

Conditional trap—A common extension to the MIPS core found in desktop RISCs (Figures E.6.1 through E.6.4), it comes for free in the conditional execution of all ARM instructions, including SWI.

■

Coprocessor interface—Like many of the desktop RISCs, ARM defines a full set of coprocessor instructions: data transfer, moves between general-purpose and coprocessor registers, and coprocessor operations.

■

Floating-point architecture—Using the coprocessor interface, a floating-point architecture has been defined for ARM. It was implemented as the FPA10 coprocessor.

■

Branch and exchange instruction sets—The BX instruction is the transition between ARM and Thumb, using the lower 31 bits of the register to set the PC and the most significant bit to determine if the mode is ARM (1) or Thumb (0).

E-37

E-38

Appendix E A Survey of RISC Architectures

E.13

Instructions Unique to Thumb

In the ARM version 4 model, frequently executed procedures will use ARM instructions to get maximum performance, with the less frequently executed ones using Thumb to reduce the overall code size of the program. Since typically only a few procedures dominate execution time, the hope is that this hybrid gets the best of both worlds. Although Thumb instructions are translated by the hardware into conventional ARM instructions for execution, there are several restrictions. First, conditional execution is dropped from almost all instructions. Second, only the first eight registers are easily available in all instructions, with the stack pointer, link register, and program counter used implicitly in some instructions. Third, Thumb uses a twooperand format to save space. Fourth, the unique shifted immediates and shifted second operands have disappeared and are replaced by separate shift instructions. Fifth, the addressing modes are simplified. Finally, putting all instructions into 16 bits forces many more instruction formats. In many ways, the simplified Thumb architecture is more conventional than ARM. Here are additional changes made from ARM in going to Thumb: ■

Drop of immediate logical instructions—Logical immediates are gone.

■

Condition codes implicit—Rather than have condition codes set optionally, they are defined by the opcode. All ALU instructions and none of the data transfers set the condition codes.

■

Hi/Lo register access—The 16 ARM registers are halved into Lo registers and Hi registers, with the eight Hi registers including the stack pointer (SP), link register, and PC. The Lo registers are available in all ALU operations. Variations of ADD, BX, CMP, and MOV also work with all combinations of Lo and Hi registers. SP and PC registers are also available in variations of data transfers and add immediates. Any other operations on the Hi registers require one MOV to put the value into a Lo register, perform the operation there, and then transfer the data back to the Hi register.

■

Branch/call distance—Since instructions are 16 bits wide, the 8-bit conditional branch address is shifted by 1 instead of by 2. Branch with link is specified in two instructions, concatenating 11 bits from each instruction and shifting them left to form a 23-bit address to load into PC.

■

Distance for data transfer offsets—The offset is now five bits for the generalpurpose registers and eight bits for SP and PC.

E.14

E.14

Instructions Unique to SuperH

Instructions Unique to SuperH

Register 0 plays a special role in SuperH address modes. It can be added to another register to form an address in indirect indexed addressing and PC-relative addressing. R0 is used to load constants to give a larger addressing range than can easily be fit into the 16-bit instructions of the SuperH. R0 is also the only register that can be an operand for immediate versions of AND, CMP, OR, and XOR. Below is a list of the remaining unique details of the SuperH architecture: ■

Decrement and test—DT decrements a register and sets the T bit to 1 if the result is 0.

■

Optional delayed branch—Although the other embedded RISC machines generally do not use delayed branches (see Appendix B), SuperH offers optional delayed branch execution for BT and BF.

■

Many multiplies—Depending if the operation is signed or unsigned, if the operands are 16 bits or 32 bits, or if the product is 32 bits or 64 bits, the proper multiply instruction is MULS, MULU, DMULS, DMULU, or MUL. The product is found in the MACL and MACH registers.

■

Zero and sign extension—Byte or halfwords are either zero-extended (EXTU) or sign-extended (EXTS) within a 32-bit register.

■

One-bit shift amounts—Perhaps in an attempt to make them fit within the 16-bit instructions, shift instructions only shift a single bit at a time.

■

Dynamic shift amount—These variable shifts test the sign of the amount in a register to determine whether they shift left (positive) or shift right (negative). Both logical (SHLD) and arithmetic (SHAD) instructions are supported. These instructions help offset the 1-bit constant shift amounts of standard shifts.

■

Rotate—SuperH offers rotations by 1 bit left (ROTL) and right (ROTR), which set the T bit with the value rotated, and also have variations that include the T bit in the rotations (ROTCL and ROTCR).

■

SWAP—This instruction either swaps the high and low bytes of a 32-bit word or the two bytes of the rightmost 16 bits.

■

Extract word (XTRCT)—The middle 32 bits from a pair of 32-bit registers are placed in another register.

■

Negate with carry—Like SUBC (Figure E.6.6), except the first operand is 0.

■

Cache prefetch—Like many of the desktop RISCs (Figures E.6.1 through E.6.4), SuperH has an instruction (PREF) to prefetch data into the cache.

E-39

E-40

Appendix E A Survey of RISC Architectures

■

Test-and-set—SuperH uses the older test-and-set (TAS) instruction to perform atomic locks or semaphores (see Chapter 2). TAS first loads a byte from memory. It then sets the T bit to 1 if the byte is 0 or to 0 if the byte is not 0. Finally, it sets the most significant bit of the byte to 1 and writes the result back to memory.

E.15

Instructions Unique to M32R

The most unusual feature of the M32R is a slight VLIW approach to the pairs of 16-bit instructions. A bit is reserved in the first instruction of the pair to say whether this instruction can be executed in parallel with the next instruction— that is, the two instructions are independent—or if these two must be executed sequentially. (An earlier machine that offered a similar option was the Intel i860.) This feature is included for future implementations of the architecture. One surprise is that all branch displacements are shifted left 2 bits before being added to the PC, and the lower 2 bits of the PC are set to 0. Since some instructions are only 16 bits long, this shift means that a branch cannot go to any instruction in the program: it can only branch to instructions on word boundaries. A similar restriction is placed on the return address for the branch-and-link and jump-andlink instructions: they can only return to a word boundary. Thus, for a slightly larger branch distance, software must ensure that all branch addresses and all return addresses are aligned to a word boundary. The M32R code space is probably slightly larger, and it probably executes more nop instructions than it would if the branch address was only shifted left 1 bit. However, the VLIW feature above means that a nop can execute in parallel with another 16-bit instruction so that the padding doesn’t take more clock cycles. The code size expansion depends on the ability of the compiler to schedule code and to pair successive 16-bit instructions; Mitsubishi claims that code size overall is only 7% larger than that for the Motorola 6800 architecture. The last remaining novel feature is that the result of the divide operation is the remainder instead of the quotient.

E.16

Instructions Unique to MIPS-16

MIPS-16 is not really a separate instruction set but a 16-bit extension of the full 32-bit MIPS architecture. It is compatible with any of the 32-bit address MIPS architectures (MIPS I, MIPS II) or 64-bit architectures (MIPS III, IV, V). The ISA mode bit determines the width of instructions: 0 means 32-bit-wide instructions

E.16

Instructions Unique to MIPS-16

and 1 means 16-bit-wide instructions. The new JALX instruction toggles the ISA mode bit to switch to the other ISA. JR and JALR have been redefined to set the ISA mode bit from the most significant bit of the register containing the branch address, and this bit is not considered part of the address. All jump-and-link instructions save the current mode bit as the most significant bit of the return address. Hence, MIPS supports whole procedures containing either 16-bit or 32-bit instructions, but it does not support mixing the two lengths together in a single procedure. The one exception is the JAL and JALX: these two instructions need 32 bits even in the 16-bit mode, presumably to get a large enough address to branch to far procedures. In picking this subset, MIPS decided to include opcodes for some three-operand instructions and to keep 16 opcodes for 64-bit operations. The combination of this many opcodes and operands in 16 bits led the architects to provide only eight easy-to-use registers—just like Thumb—whereas the other embedded RISCs offer about 16 registers. Since the hardware must include the full 32 registers of the 32-bit ISA mode, MIPS-16 includes move instructions to copy values between the eight MIPS-16 registers and the remaining 24 registers of the full MIPS architecture. To reduce pressure on the eight visible registers, the stack pointer is considered a separate register. MIPS-16 includes a variety of separate opcodes to do data transfers using SP as a base register and to increment SP: LWSP, LDSP, SWSP, SDSP, ADJSP, DADJSP, ADDIUSPD, and DADDIUSP. To fit within the 16-bit limit, immediate fields have generally been shortened to five to eight bits. MIPS-16 provides a way to extend its shorter immediates into the full width of immediates in the 32-bit mode. Borrowing a trick from the Intel 8086, the EXTEND instruction is really a 16-bit prefix that can be prepended to any MIPS-16 instruction with an address or immediate field. The prefix supplies enough bits to turn the 5-bit field of data transfers and 5- to 8-bit fields of arithmetic immediates into 16-bit constants. Alas, there are two exceptions. ADDIU and DADDIU start with 4-bit immediate fields, but since EXTEND can only supply 11 more bits, the wider immediate is limited to 15 bits. EXTEND also extends the 3-bit shift fields into 5-bit fields for shifts. (In case you were wondering, the EXTEND prefix does not need to start on a 32-bit boundary.) To further address the supply of constants, MIPS-16 added a new addressing mode! PC-relative addressing for load word (LWPC) and load double (LDPC) shifts an 8-bit immediate field by two or three bits, respectively, adding it to the PC with the lower two or three bits cleared. The constant word or doubleword is then loaded into a register. Thus 32-bit or 64-bit constants can be included with MIPS-16 code, despite the loss of LIU to set the upper register bits. Given the new addressing mode, there is also an instruction (ADDIUPC) to calculate a PC-relative address and place it in a register. MIPS-16 differs from the other embedded RISCs in that it can subset a 64-bit address architecture. As a result it has 16-bit instruction-length versions of 64-bit

E-41

E-42

Appendix E A Survey of RISC Architectures

data operations: data transfer (LD, SD, LWU), arithmetic operations (DADDU/IU, DSUBU, DMULT/U, DDIV/U), and shifts (DSLL/V, DSRA/V, DSRL/V). Since MIPS plays such a prominent role in this book, we show all the additional changes made from the MIPS core instructions in going to MIPS-16: ■

■

Drop of signed arithmetic instructions—Arithmetic instructions that can trap were dropped to save opcode space: ADD, ADDI, SUB, DADD, DADDI, DSUB. Drop of immediate logical instructions—Logical immediates are gone too: ANDI, ORI, XORI.

■

Branch instructions pared down—Comparing two registers and then branching did not fit, nor did all the other comparisons of a register to zero. Hence these instructions didn’t make it either: BEQ, BNE, BGEZ, BGTZ, BLEZ, and BLTZ. As mentioned in Section E.3, to help compensate MIPS-16 includes compare instructions to test if two registers are equal. Since compare and set on less than set the new T register, branches were added to test the T register.

■

Branch distance—Since instructions are 16 bits wide, the branch address is shifted by one instead of by two.

■

Delayed branches disappear—The branches take effect before the next instruction. Jumps still have a one-slot delay.

■

Extension and distance for data transfer offsets—The 5-bit and 8-bit fields are zero-extended instead of sign-extended in 32-bit mode. To get greater range, the immediate fields are shifted left one, two, or three bits depending on whether the data is halfword, word, or doubleword. If the EXTEND prefix is prepended to these instructions, they use the conventional signed 16-bit immediate of the 32-bit mode.

■

Extension of arithmetic immediates—The 5-bit and 8-bit fields are zeroextended for set on less than and compare instructions, for forming a PCrelative address, and for adding to SP and placing the result in a register (ADDIUSP, DADDIUSP). Once again, if the EXTEND prefix is prepended to these instructions, they use the conventional signed 16-bit immediate of the 32-bit mode. They are still sign-extended for general adds and for adding to SP and placing the result back in SP (ADJSP, DADJSP). Alas, code density and orthogonality are strange bedfellows in MIPS-16!

■

Redefining shift amount of 0—MIPS-16 defines the value 0 in the 3-bit shift field to mean a shift of 8 bits.

■

New instructions added due to loss of register 0 as zero—Load immediate, negate, and not were added, since these operations could no longer be synthesized from other instructions using r0 as a source.

E.17

E.17

E-43

Concluding Remarks

Concluding Remarks

This appendix covers the addressing modes, instruction formats, and all instructions found in ten RISC architectures. Although the later sections of the appendix concentrate on the differences, it would not be possible to cover ten architectures in these few pages if there were not so many similarities. In fact, we would guess that more than 90% of the instructions executed for any of these architectures would be found in Figures E.3.5 through E.3.11. To contrast this homogeneity, Figure E.17.1 gives a summary for four architectures from the 1970s in a format similar to that shown in Figure E.1.1. (Imagine trying to write a single chapter in this style for those architectures!) In the history of computing, there has never been such widespread agreement on computer architecture.

IBM 360/370

Intel 8086

Motorola 68000

DEC VAX

Date announced

1964/1970

1978

1980

Instruction size(s) (bits)

16, 32, 48

8, 16, 24, 32, 40, 48

16, 32, 48, 64, 80

1977 8, 16, 24, 32, . . . , 432

Addressing (size, model)

4 + 16 bits, segmented No

24 bits, flat

32 bits, flat

Data aligned?

24 bits, flat/31 bits, flat Yes 360/No 370

16-bit aligned

No

Data addressing modes

2/3

5

9

= 14

Protection

Page

None

Optional

Page

Page size

2 KB & 4 KB

—

0.25 to 32 KB

0.5 KB

I/O

Opcode

Opcode

Memory mapped

Memory mapped

Integer registers (size, model, number)

16 GPR × 32 bits

8 dedicated data × 16 bits

8 data and 8 address × 32 bits

15 GPR × 32 bits

Separate floating-point registers

4 × 64 bits

Optional: 8 × 80 bits

Optional: 8 × 80 bits

0

Floating-point format

IBM (floating hexadecimal)

IEEE 754 single, double, extended

IEEE 754 single, double, extended

DEC

FIGURE E.17.1 Summary of four 1970s architectures. Unlike the architectures in Figure E.1.1, there is little agreement between these architectures in any category.

This style of architecture cannot remain static, however. Like people, instruction sets tend to get bigger as they get older. Figure E.17.2 shows the genealogy of these instruction sets, and Figure E.17.3 shows which features were added to or deleted from generations of desktop RISCs over time. As you can see, all the desktop RISC machines have evolved to 64-bit address architectures, and they have done so fairly painlessly.

E-44

Appendix E A Survey of RISC Architectures

1960 CDC 6600 1963

1965

IBM ASC 1968

1970

1975

1980

Berkeley RISC-1 Stanford MIPS 1981 1982 ARM1 1985

1985

ARM2 1987 1990

1995

IBM 801 1975

Cray-1 1976

SuperH 1992

ARM3 1990

Thumb ARM v.4 1995 M32R 1995 1997

SPARC v.8 1987

SPARC v.9 1994 MIPS-16 1996

MIPS I 1986

PA-RISC 1986

MIPS II Digital PRISM 1988 1989 PA-RISC 1.1 MIPS III 1990 Alpha 1992 1992 MIPS IV 1994 MIPS V 1996

RT/PC 1986

America 1985

Power1 1990

Power2 PowerPC 1993 1993 Alpha v.3 PA-RISC 2.0 1996 1996

2000 2002

MIPS-32 2002

MIPS-64 2002

FIGURE E.17.2 The lineage of RISC instruction sets. Commercial machines are shown in plain text and research machines in bold. The CDC 6600 and Cray-1 were load-store machines with register 0 fixed at 0, and separate integer and floating-point registers. Instructions could not cross word boundaries. An early IBM research machine led to the 801 and America research projects, with the 801 leading to the unsuccessful RT/PC and America leading to the successful Power architecture. Some people who worked on the 801 later joined HewlettPackard to work on the PA-RISC. The two university projects were the basis of MIPS and SPARC machines. According to Furber [1996], the Berkeley RISC project was the inspiration of the ARM architecture. While ARM1, ARM2, and ARM3 were names of both architectures and chips, ARM version 4 is the name of the architecture used in ARM7, ARM8, and StrongARM chips. (There are no ARM v.4 and ARM5 chips, but ARM6 and early ARM7 chips use the ARM3 architecture.) DEC built a RISC microprocessor in 1988 but did not introduce it. Instead, DEC shipped workstations using MIPS microprocessors for three years before they brought out their own RISC instruction set, Alpha 21064, which is very similar to MIPS III and PRISM. The Alpha architecture has had small extensions, but they have not been formalized with version numbers; we used version 3 because that is the version of the reference manual. The Alpha 21164A chip added byte and halfword loads and stores, and the Alpha 21264 includes the MAX multimedia and bit count instructions. Internally, Digital names chips after the fabrication technology: EV4 (21064), EV45 (21064A), EV5 (21164), EV56 (21164A), and EV6 (21264).“EV” stands for “extended VAX.”

E.17

PA-RISC Feature

E-45

Concluding Remarks

SPARC

MIPS

1.0

1.1

2.0

v. 8

v. 9

II

III

IV

1

2

PC

Interlocked loads

X

”

”

X

”

+

”

”

X

”

”

Load-store FP double

X

”

”

X

”

+

”

”

X

”

”

Semaphore

X

”

”

X

”

+

”

”

X

”

”

+

”

”

”

”

”

Square root

X

”

”

X

”

Single precision FP ops

X

”

”

X

”

Memory synchronize

X

”

”

X

”

Coprocessor

X

”

”

X

—

Base + index addressing

X

”

”

X

”

”

Equiv. 32 64-bit FP registers

I

Power

X X

X

”

”

”

”

+

X

X

”

+

”

+

X

Branch prediction bit

+

Conditional move

+

Prefetch data into cache

+

+

64-bit addressing/int. ops

+

+

”

+

Load-store FP quad

Multimedia support

X

+ X

”

”

X

”

”

”

+

X

”

”

”

X

”

”

+

”

”

”

”

”

”

”

”

+

”

”

X

”

”

+

X

”

—

+

X

”

”

+ X

” +

+

”

”

”

+

X

+ X

” +

+

Fused FP mul/add String instructions

”

+

X

+

”

”

”

Branch register contents

32-bit multiply, divide

”

”

+

Annulling delayed branch Big/little endian

+

V

”

”

+

—

X

”

”

X

”

—

X

FIGURE E.17.3 Features added to desktop RISC machines. X means in the original machine, + means added later, ” means continued from prior machine, and—means removed from architecture. Alpha is not included, but it added byte and word loads and stores, and bit count and multimedia extensions, in version 3. MIPS V added the MDMX instructions and paired single floating-point operations.

We would like to thank the following people for comments on drafts of this appendix: Professor Steven B. Furber, University of Manchester; Dr. Dileep Bhandarkar, Intel Corporation; Dr. Earl Killian, Silicon Graphics/MIPS; and Dr. Hiokazu Takata, Mitsubishi Electric Corporation.

Further Reading Bhandarkar, D. P. [1995]. Alpha Architecture and Implementations, Newton, MA: Digital Press. Darcy, J. D., and D. Gay [1996]. “FLECKmarks: Measuring floating point performance using a full IEEE compliant arithmetic benchmark,” CS 252 class project, U.C. Berkeley (see HTTP.CS.Berkeley.EDU/~darcy/ Projects/cs252/). Digital Semiconductor [1996]. Alpha Architecture Handbook, Version 3, Maynard, MA: Digital Press, Order number EC-QD2KB-TE (October).

E-46

Appendix E A Survey of RISC Architectures

Furber, S. B. [1996]. ARM System Architecture, Harlow, England: Addison-Wesley. (See www.cs.man.ac.uk/ amulet/publications/books/ARMsysArch.) Hewlett-Packard [1994]. PA-RISC 2.0 Architecture Reference Manual, 3rd ed. Hitachi [1997]. SuperH RISC Engine SH7700 Series Programming Manual. (See www.halsp.hitachi.com/tech_ prod/ and search for title.) IBM [1994]. The PowerPC Architecture, San Francisco: Morgan Kaufmann. Kane, G. [1996]. PA-RISC 2.0 Architecture, Upper Saddle River, NJ: Prentice Hall PTR. Kane, G., and J. Heinrich [1992]. MIPS RISC Architecture, Englewood Cliffs, NJ: Prentice Hall. Kissell, K. D. [1997]. MIPS16: High-Density for the Embedded Market. (See www.sgi.com/MIPS/arch/MIPS16/ MIPS16.whitepaper.pdf.) Magenheimer, D. J., L. Peters, K. W. Pettis, and D. Zuras [1988]. “Integer multiplication and division on the HP precision architecture,” IEEE Trans. on Computers 37:8, 980–90. MIPS [1997]. MIPS16 Application Specific Extension Product Description. (See www.sgi.com/MIPS/arch/ MIPS16/mips16.pdf.) Mitsubishi [1996]. Mitsubishi 32-Bit Single Chip Microcomputer M32R Family Software Manual (September). Muchnick, S. S. [1988]. “Optimizing compilers for SPARC,” Sun Technology 1:3 (Summer), 64–77. Seal, D. Arm Architecture Reference Manual, 2nd ed, Morgan Kaufmann, 2000. Silicon Graphics [1996]. MIPS V Instruction Set. (See www.sgi.com/MIPS/arch /ISA5/#MIPSV_indx.) Sites, R. L., and R. Witek (eds.) [1995]. Alpha Architecture Reference Manual, 2nd ed. Newton, MA: Digital Press. Sloss, A. N., D. Symes, and C. Wright, ARM System Developer’s Guide, San Francisco: Elsevier Morgan Kaufmann, 2004. Sun Microsystems [1989]. The SPARC Architectural Manual, Version 8, Part No. 800-1399-09, August 25. Sweetman, D. See MIPS Run, 2nd ed, Morgan Kaufmann, 2006. Taylor, G., P. Hilfinger, J. Larus, D. Patterson, and B. Zorn [1986]. “Evaluation of the SPUR LISP architecture,” Proc. 13th Symposium on Computer Architecture (June), Tokyo. Ungar, D., R. Blau, P. Foley, D. Samples, and D. Patterson [1984]. “Architecture of SOAR: Smalltalk on a RISC,” Proc. 11th Symposium on Computer Architecture (June), Ann Arbor, MI, 188–97. Weaver, D. L., and T. Germond [1994]. The SPARC Architectural Manual, Version 9, Englewood Cliffs, NJ: Prentice Hall. Weiss, S., and J. E. Smith [1994]. Power and PowerPC, San Francisco: Morgan Kaufmann.