This chapter reviews features that are found in all modern microprocessors: (i) instruction pipelining and (ii) a main memory hierarchy with caches, including the virtual-to-physical memory translation. It does not dwell on many details – that is what subsequent chapters will do. It provides solely a basis on which we can build later on.

Pipelining

Consider the steps required to execute an arithmetic instruction in the von Neumann machine model, namely:

1. 1. Fetch the (next) instruction (the one at the address given by the program counter).

2. 2. Decode it.

3. 3. Execute it.

4. 4. Store the result and increment the program counter.

In the case of a load or a store instruction, step 3 becomes two steps: calculate a memory address, and activate the memory for a read or for a write. In the latter case, no subsequent storing is needed. In the case of a branch, step 3 sets the program counter to point to the next instruction, and step 4 is voided.

Early on in the design of processors, it was recognized that complete sequentiality between the executions of instructions was often too restrictive and that parallel execution was possible. One of the first forms of parallelism that was investigated was the overlap of the mentioned steps between consecutive instructions. This led to what is now called pipelining.

From Scalar to Superscalar Processors

In the previous chapter we introduced a five-stage pipeline. The basic concept was that the instruction execution cycle could be decomposed into nonoverlapping stages with one instruction passing through each stage at every cycle. This so-called scalar processor had an ideal throughput of 1, or in other words, ideally the number of instructions per cycle (IPC) was 1.

If we return to the formula giving the execution time, namely,

EXCPU = Number of instructions × CPI × cycle time

we see that in order to reduce EXCPU in a processor with the same ISA – that is, without changing the number of instructions, N – we must either reduce CPI (increase IPC) or reduce the cycle time, or both. Let us look at the two options.

The only possibility to increase the ideal IPC of 1 is to radically modify the structure of the pipeline to allow more than one instruction to be in each stage at a given time. In doing so, we make a transition from a scalar processor to a superscalar one. From the microarchitecture viewpoint, we make the pipeline wider in the sense that its representation is not linear any longer. The most evident effect is that we shall need several functional units, but, as we shall see, each stage of the pipeline will be affected.

Parallel processing takes several flavors, depending on the unit of parallelism and the number of processing units. Early on in the development of computer systems, we saw the emergence of multiprogramming (Section 2.3), whereby several (portions of) programs share main memory. When the program currently executing requires some I/O processing, it relinquishes the use of the CPU via a context switch, and another program takes ownership of the CPU. Parallel processing occurs between the program using the CPU and the programs (there may be more than one) executing some I/O-related task. Here, the unit of parallel processing is a program, or process, and the parallelism is at the program level. An efficient implementation of multiprogramming requires the use of an operating system with a virtual memory management component. At the other extreme of the spectrum of granularity, we have the exploitation of instruction-level parallelism. Several instructions of the same program are executing simultaneously. Pipelining (Section 2.1) is the simplest form of the concurrent execution of instructions. Superscalar and EPIC processors (Chapter 3) extend this notion by having several instructions occupying the same stages of the pipeline at the same time. Of course, extra resources such as multiple functional units must be present for this concurrency to happen.

In the previous chapter, we gave a strict definition of multiprocessing, namely, the processing by several processors of portions of the same program.

Modern computer systems built from the most sophisticated microprocessors and extensive memory hierarchies achieve their high performance through a combination of dramatic improvements in technology and advances in computer architecture. Advances in technology have resulted in exponential growth rates in raw speed (i.e., clock frequency) and in the amount of logic (number of transistors) that can be put on a chip. Computer architects have exploited these factors in order to further enhance performance using architectural techniques, which are the main subject of this book.

Microprocessors are over 30 years old: the Intel 4004 was introduced in 1971. The functionality of the 4004 compared to that of the mainframes of that period (for example, the IBM System/370) was minuscule. Today, just over thirty years later, workstations powered by engines such as (in alphabetical order and without specific processor numbers) the AMD Athlon, IBM PowerPC, Intel Pentium, and Sun Ultra SPARC can rival or surpass in both performance and functionality the few remaining mainframes and at a much lower cost. Servers and supercomputers are more often than not made up of collections of microprocessor systems.

It would be wrong to assume, though, that the three tenets that computer architects have followed, namely pipelining, parallelism, and the principle of locality, were discovered with the birth of microprocessors. They were all at the basis of the design of previous (super)computers. The advances in technology made their implementations more practical and spurred further refinements.

Since 2003, the peak frequency at which single processors and chip multiprocessors have operated has remained largely unchanged. One basic reason is that power dissipation effects have limited frequency increases. In addition, difficulties in extracting more parallelism at the instruction level, design complexity, and the effects of wire lengths have resulted in a performance plateau for single processors. We elaborate on some of these issues in this chapter.

While improvements in clock frequency and in ILP exploitation have been stalled, Moore's law is still valid, and the amount of logic that can be laid out on a chip is still increasing. Adding more cache memory to a single processor to fill all the on-chip real estate has reached a point of diminishing return, performancewise. Multithreaded processors, which mitigate the effects of the memory wall, and multiprocessors on a chip (CMP, also called multicores) are the current approach to attaining more performance. A question that is of primary importance to computer architects and to computer users in general is the structure of future CMPs, as mentioned in the previous chapter.

In a conservative evolutionary fashion, future CMPs might look like those we have presented in Chapter 8, with naturally a slightly larger number of cores. Questions of whether there should be many simple cores vs. fewer high-performance ones, and of whether the cores should be homogeneous or not, have already been touched upon previously. Although speed is still the primary metric, other aspects such as reliability and security have gained importance.

Computer architecture is at a turning point. Radical changes occurred in the 1980s when the Reduced Instruction Set Computer (RISC) philosophy, spurred in good part by academic research, permeated the industry as a reaction to the Complex Instruction Set Computer (CISC) complexities. Today, three decades later, we have reached a point where physical limitations such as power dissipation and design complexity limit the speed and the performance of single-processor systems. The era of chip multiprocessors (CMP), or multicores, has arrived.

Besides the uncertainty on the structure of CMPs, it is not known yet whether the future CMPs will be composed of simple or complex processors or a combination of both and how the on-chip and off-chip memory hierarchy will be managed. It is important for computer scientists and engineers to look at the possible options for the modules that will compose the new generations of multicores. In this book, we describe the architecture of microprocessors from simple in-order short pipe designs to out-of-order superscalars with many optimizations. We also present choices and enhancements in the cache hierarchy of single processors. The last part of this book introduces readers to the state-of-the-art in multithreading and multiprocessing, emphasizing single-chip implementations and their cache hierarchy.

The emphasis in this book is on “how things work” at a black box and algorithmic level. It is not as close to the hardware as books that explain features at the register transfer level.

The principal application of switching theory is in the design of digital circuits. The design of such circuits is commonly referred to as logical (or logic) design. Most digital systems are constructed from electronic switching circuits. In this chapter, we describe some components that are typical of the basic building blocks used in constructing digital systems. Switching algebra will be used to describe the logical behavior of networks composed of these building blocks as well as to manipulate and simplify switching expressions, thereby reducing the number of components used in the design. We shall be concerned with the logic functions that a circuit performs rather than with its electronic structure or behavior. Special attention will be given to the design of high-speed binary adders. These examples will introduce us to some practical aspects of logic design in which the speed of operation and area limitations require ingenuity in arriving at a proper compromise.

Design with basic logic gates

Although modern digital systems are composed of a large number of components, they usually employ only a small number of different kinds of elementary circuits, called gates, whose task is to perform logic operations on input signals. In Section 3.2, we showed that in order to implement any switching function, it is necessary to have a set of two-valued switching devices capable of implementing a functionally complete set of operations. The objective of this section is to present some commonly used devices of this type.

We have been concerned with the design of switching circuits constructed of electronic gates or bilateral devices. There exists another type of switching device called a threshold element. With the advent of novel nanotechnologies, threshold elements are attracting attention once again since they form the basic logic primitives in some of these technologies.

Circuits constructed of threshold elements usually consist of fewer components and simpler interconnections than the corresponding circuits implemented with conventional gates. However, while the input–output relations of circuits constructed with conventional gates can be specified by switching algebra, different algebraic means must be developed for threshold circuits. In this chapter, we shall study the properties of threshold elements and present necessary and sufficient conditions for a switching function to be realizable by just a single element. We shall then present a general synthesis procedure for synthesizing switching circuits using only threshold elements. Finally, we shall discuss synthesis methods based on majority or minority logic gates, which are simple threshold elements.

Introductory concepts

The usefulness of threshold logic, or any other new logic in digital system design, is determined by the availability, cost, and capabilities of the basic building blocks, as well as by the existence of effective synthesis procedures. In this section, we shall study the properties of the threshold element, and discuss its limitations and capabilities.

The threshold element

A threshold element, or gate, has n two-valued inputs x1, x2, …, xn and a single two-valued output y.

The second part of this book is devoted to combinational logic and deals with various aspects of the analysis and design of combinational switching circuits. The particular characteristic of a combinational switching circuit is that its outputs are functions of only the present circuit inputs. First, switching algebra is introduced as the basic mathematical tool essential for dealing with problems encountered in the study of switching circuits. Switching expressions are defined and are found to be instrumental in describing the logical properties of switching circuits. Systematic simplification procedures of these expressions are next presented; these lead to more economical circuits. Logical design is studied with special attention to conventional logic, complementary metaloxide semiconductor (CMOS) circuits, and threshold logic. Finally, problems related to the testing of combinational circuits for various fault models, and synthesis-for-testability techniques are discussed.

In the current chapter, after developing a switching algebra from the simplest set of basic postulates we show its applications to the study of switching circuits as well as to the calculus of propositions. Finally, this switching algebra is shown to be a special case of Boolean algebra.

Switching algebra

The basic concepts of switching algebra will be introduced by means of a set of postulates, from which we shall derive useful theorems and develop necessary tools that will enable us to manipulate and simplify algebraic expressions.

Fundamental postulates

The basic postulate of switching algebra is the existence of a two-valued switching variable that can take either of two distinct values, 0 and 1.

The problem of determining whether a digital circuit operates correctly is of both theoretical interest and practical concern. Present-day digital systems may be disabled by almost any internal failure. Failures are caused by faults that are initially manifested as errors and finally as failures. In this chapter, we shall study various fault models, techniques for generating tests, and logic synthesis techniques that ensure testability with respect to various types of fault.

Fault models

In order to alleviate the complexity of test generation, one needs to model the actual defects that may occur in a chip with fault models at higher levels of abstraction. This process of fault modeling considerably reduces the burden of testing because it obviates the need for deriving tests for each possible defect. This is due to the fact that many physical defects map to a single fault at the higher level.

Faults may change the logic values at some internal lines in the integrated circuit, or they may result in a change in the voltage or current levels. They may also change the temporal behavior of the circuit.

Currently, most popular fault models are described at the structure and switch levels of the integrated-circuit design hierarchy. In this section, we shall examine these fault models.

Structural fault models

In structural testing we need to make sure that the interconnections in the given structure are fault-free and are able to carry both 0 and 1 signals. The stuck-at fault model is directly derived from these requirements.

The objective of this chapter is twofold: to develop the properties of partially ordered sets and lattices in an informal manner, and to furnish algebraic concepts necessary for the understanding of later chapters. The chapter develops in an intuitive manner the notions of sets, relations, and partial ordering, which together form the basis for the presentation of some results from lattice theory and, in Chapter 3, Boolean algebras. The chapter is by no means a complete treatment of the subjects but rather a survey of some results that bear upon material presented in later chapters.

Sets

A set S is intuitively defined as a collection of distinct objects. The readers of this book and prime numbers are examples of sets. The objects that form a set are called elements, or members, of that set, and the set is said to contain them. The membership of an element a in a set A is denoted by a ∈ A to mean “a is an element of A.” A set which has no element is called an empty or null set and is denoted φ. The elements contained in a set are either listed explicitly or described by their properties. This is accomplished by placing the elements or the describing property in braces.

Topics in switching and finite automata theory have been an important part of the curriculum in electrical engineering and computer science departments for several decades. The third edition of this book builds on the comprehensive foundation provided by the second edition and adds: significant new material in the areas of CMOS logic; modern two-level and multi-level logic synthesis methods; logic design for emerging nanotechnologies; test generation, design for testability and built-in self-test for combinational and sequential circuits; modern asynchronous circuit synthesis techniques; etc. We have attempted to maintain the comprehensive nature of the earlier edition in providing readers with an understanding of the structure, behavior, and limitations of logical machines. At the same time, we have provided an up-to-date context in which the presented techniques can find use in a variety of applications. We start with introductory material and build up to more advanced topics. Thus, the technical background assumed on the part of the reader is minimal.

This edition maintains the style of the previous edition in providing a logical and rigorous discussion of various topics with minimal formalism. Thus, theorems and algorithms are preceded by several intuitive examples to ease understanding. The original references for various topics are provided. Of course, readers who want to dig deeper into a subject would need to consult later works also.

Linear sequential machines constitute a subclass of linear systems in which the input vector, output vector, and state transitions occur in discrete steps. Consequently, the tools and techniques available for the analysis and synthesis of linear systems can be applied to linear machines as well. The numerous applications of linear machines give further incentive to the investigation of their properties and to the development of efficient synthesis procedures.

In the first few sections we present an intuitive, though well-justified, approach that requires only a limited knowledge of modem algebra. In subsequent sections (i.e., Sections 15.4 through 15.6) a matrix formulation is presented, and methods for minimizing and detecting linear machines are developed.

Introduction

A linear sequential machine (also called a linear machine) is a network that has a finite number of input and output terminals and is composed of interconnections of three types of basic components, to be introduced shortly. The input signals applied to the machine are elements of a finite field GF(p) = {0, 1, …, p – 1}, and the operations performed by the basic components on their inputs are carried out according to the rules of GF(p). A block-diagram representation of a linear machine with l input terminals and m output terminals is shown in Fig. 15.1.

For a machine to be linear, its response to a linear combination of inputs must preserve the scale factor and the principle of superposition.