Flash patch and breakpoint unit

This page intentionally left blank

Computer organization and arChiteCture

With Foreword by
Chris Jesshope
Professor (emeritus) University of Amsterdam

Director of Field Marketing: Demetrius Hall
Product Marketing Manager: Bram van Kempen Marketing Assistant: Jon Bryant
Cover Designer: Marta Samsel
Cover Art: © anderm / Fotolia
Full-Service Project Management:
Mahalatchoumy Saravanan, Jouve India
Printer/Binder: Edwards Brothers Malloy
Cover Printer: Lehigh-Phoenix Color/Hagerstown Typeface: Times Ten LT Std 10/12

Senior Specialist, Program Planning and Support:
Maura Zaldivar-Garcia

Pearson Education North Asia Ltd., Hong Kong
Pearson Education Canada, Inc., Toronto
Pearson Education de Mexico, S.A. de C.V.

Pearson Education–Japan, Tokyo
Pearson Education Malaysia, Pte. Ltd.

pages cm
Includes bibliographical references and index.

ISBN 978-0-13-410161-3 — ISBN 0-13-410161-8 1. Computer organization. 2. Computer architecture. I. Title.

This page intentionally left blank

PART ONE INTRODUCTION 1

Chapter 1 Basic Concepts and Computer Evolution 1

1.5 Embedded Systems 29

1.6 Arm Architecture 33

2.2 Multicore, Mics, and GPGPUs 52

2.3 Two Laws that Provide Insight: Ahmdahl’s Law and Little’s Law 53

PART TWO THE COMPUTER SYSTEM 80

Chapter 3 A Top- Level View of Computer Function and Interconnection 80

3.5 Point- to- Point Interconnect 102

3.6 PCI Express 107

4.3 Elements of Cache Design 131

4.4 Pentium 4 Cache Organization 149

Chapter 5 Internal Memory 165

5.1 Semiconductor Main Memory 166

5.6 Key Terms, Review Questions, and Problems 190

Chapter 6 External Memory 194

6.5 Magnetic Tape 222

6.6 Key Terms, Review Questions, and Problems 224

7.4 Interrupt- Driven I/O 239

7.5 Direct Memory Access 248

7.10 Key Terms, Review Questions, and Problems 270

Chapter 8 Operating System Support 275

8.5 Arm Memory Management 309

8.6 Key Terms, Review Questions, and Problems 314

9.3 The Binary System 321

9.4 Converting Between Binary and Decimal 321

10.2 Integer Representation 330

10.3 Integer Arithmetic 335

Chapter 11 Digital Logic 372

11.1 Boolean Algebra 373

11.6 Key Terms and Problems 409

PART FOUR THE CENTRAL PROCESSING UNIT 412

12.4 Types of Operations 425

12.5 Intel x86 and ARM Operation Types 438

13.2 x86 and ARM Addressing Modes 463

13.3 Instruction Formats 469

14.1 Processor Organization 489

14.2 Register Organization 491

14.7 Key Terms, Review Questions, and Problems 530

Chapter 15 Reduced Instruction Set Computers 535

15.5 RISC Pipelining 555

15.6 MIPS R4000 559

Chapter 16 Instruction- Level Parallelism and Superscalar Processors 575

16.1 Overview 576

16.6 Key Terms, Review Questions, and Problems 608

PART FIVE PARALLEL ORGANIZATION 613

17.4 Multithreading and Chip Multiprocessors 628

17.5 Clusters 633

18.1 Hardware Performance Issues 657

18.2 Software Performance Issues 660

18.7 IBM zEnterprise EC12 Mainframe 682

18.8 Key Terms, Review Questions, and Problems 685

19.4 Intel’s Gen8 GPU 701

19.5 When to Use a GPU as a Coprocessor 704

20.2 Control of the Processor 714

20.3 Hardwired Implementation 724

Contents xi

21.3 Microinstruction Execution 745

A.2 Research Projects 771

A.3 Simulation Projects 771

Appendix B Assembly Language and Related Topics 774

B.1 Assembly Language 775

Index 809

Credits 833

at the front of this book.

This page intentionally left blank

Throughout the 1980s and early 1990s research flourished in this field and there was a great deal of innovation, much of which came to market through university start- ups. Iron-ically however, it was the same technology that reversed this trend. Diversity was gradually replaced with a near monoculture in computer systems with advances in just a few instruc-tion set architectures. Moore’s law, a self- fulfilling prediction that became an industry guide-line, meant that basic device speeds and integration densities both grew exponentially, with the latter doubling every 18 months of so. The speed increase was the proverbial free lunch for computer architects and the integration levels allowed more complexity and innovation at the micro- architecture level. The free lunch of course did have a cost, that being the expo-nential growth of capital investment required to fulfill Moore’s law, which once again limited the access to state- of- the- art technologies. Moreover, most users found it easier to wait for the next generation of mainstream processor than to invest in the innovations in parallel computers, with their pitfalls and difficulties. The exceptions to this were the few large insti-tutions requiring ultimate performance; two topical examples being large- scale scientific simulation such as climate modeling and also in our security services for code breaking. For

xiii

These are just some of the questions facing us today. To answer these questions and more requires a sound foundation in computer organization and architecture, and this book by William Stallings provides a very timely and comprehensive foundation. It gives a com-plete introduction to the basics required, tackling what can be quite complex topics with apparent simplicity. Moreover, it deals with the more recent developments in this field, where innovation has in the past, and is, currently taking place. Examples are in superscalar issue and in explicitly parallel multicores. What is more, this latest edition includes two very recent topics in the design and use of GPUs for general- purpose use and the latest trends in cloud computing, both of which have become mainstream only recently. The book makes good use of examples throughout to highlight the theoretical issues covered, and most of these examples are drawn from developments in the two most widely used ISAs, namely the x86 and ARM. To reiterate, this book is complete and is a pleasure to read and hopefully will kick- start more young researchers down the same path that I have enjoyed over the last 40 years!

■ GPGPU [ General- Purpose Computing on Graphics Processing Units (GPUs)]: One of the most important new developments in recent years has been the broad adoption of GPGPUs to work in coordination with traditional CPUs to handle a wide range of applications involving large arrays of data. A new chapter is devoted to the topic of GPGPUs.

■ Heterogeneous multicore processors: The latest development in multicore architecture is the heterogeneous multicore processor. A new section in the chapter on multicore processors surveys the various types of heterogeneous multicore processors.

xv

xvi PreFACe

■ Homework problems: The number of supplemental homework problems, with solu- tions, available for student practice has been expanded.

SUPPORT OF ACM/IEEE COMPUTER SCIENCE CURRICULA 2013

xviii PreFACe

The subtitle suggests the theme and the approach taken in this book. It has always been important to design computer systems to achieve high performance, but never has this requirement been stronger or more difficult to satisfy than today. All of the basic per-formance characteristics of computer systems, including processor speed, memory speed, memory capacity, and interconnection data rates, are increasing rapidly. Moreover, they are increasing at different rates. This makes it difficult to design a balanced system that maxi-mizes the performance and utilization of all elements. Thus, computer design increasingly becomes a game of changing the structure or function in one area to compensate for a per-formance mismatch in another area. We will see this game played out in numerous design decisions throughout the book.

A computer system, like any system, consists of an interrelated set of components. The system is best characterized in terms of structure— the way in which components are interconnected, and function— the operation of the individual components. Furthermore, a computer’s organization is hierarchical. Each major component can be further described by decomposing it into its major subcomponents and describing their structure and function. For clarity and ease of understanding, this hierarchical organization is described in this book from the top down:

PreFACe xix

Throughout the discussion, aspects of the system are viewed from the points of view of both architecture (those attributes of a system visible to a machine language programmer) and organization (the operational units and their interconnections that realize the architecture).

Many, but by no means all, of the examples in this book are drawn from these two computer families. Numerous other systems, both contemporary and historical, provide examples of important computer architecture design features.

PLAN OF THE TEXT

■ The central processing unit

■ Parallel organization, including multicore

xx PreFACe

book’s Companion Web site at WilliamStallings.com/ComputerOrganization. To gain access to the IRC, please contact your local Pearson sales representative via pearsonhighered.com/ educator/replocator/requestSalesRep.page or call Pearson Faculty Services at 1-800-526-0485. The IRC provides the following materials:

■ Test bank: A chapter- by- chapter set of questions.

■ Sample syllabuses: The text contains more material than can be conveniently covered in one semester. Accordingly, instructors are provided with several sample syllabuses that guide the use of the text within limited time. These samples are based on real- world experience by professors with the first edition.

errata sheet for the book.

PreFACe xxi

	To access the Premium Content site, click on the Premium Content link at the Companion Web site or at pearsonhighered.com/stallings and enter the stu-dent access code found on the card in the front of the book.

■ Research projects: A series of research assignments that instruct the student to research a particular topic on the Internet and write a report.

■ Simulation projects: The IRC provides support for the use of the two simulation pack-ages: SimpleScalar can be used to explore computer organization and architecture design issues. SMPCache provides a powerful educational tool for examining cache design issues for symmetric multiprocessors.

This diverse set of projects and other student exercises enables the instructor to use the book as one component in a rich and varied learning experience and to tailor a course plan to meet the specific needs of the instructor and students. See Appendix A in this book for details.

INTERACTIVE SIMULATIONS

ACKNOWLEDGMENTS

This new edition has benefited from review by a number of people, who gave generously of their time and expertise. The following professors and instructors reviewed all or a large part of the manuscript: Molisa Derk (Dickinson State University), Yaohang Li (Old Domin-ion University), Dwayne Ockel (Regis University), Nelson Luiz Passos (Midwestern State University), Mohammad Abdus Salam (Southern University), and Vladimir Zwass (Fair-leigh Dickinson University).

Todd Bezenek of the University of Wisconsin and James Stine of Lehigh University prepared the SimpleScalar problems in the instructor’s manual, and Todd also authored the SimpleScalar User’s Guide.

Finally, I would like to thank the many people responsible for the publication of the book, all of whom did their usual excellent job. This includes the staff at Pearson, par-ticularly my editor Tracy Johnson, her assistant Kelsey Loanes, program manager Carole Snyder, and production manager Bob Engelhardt. I also thank Mahalatchoumy Saravanan and the production staff at Jouve India for another excellent and rapid job. Thanks also to the marketing and sales staffs at Pearson, without whose efforts this book would not be in front of you.

Dr. Stallings holds a PhD from MIT in computer science and a BS from Notre Dame in electrical engineering.

xxiii

Basic conceptsand computer evolution

1.1 Organization and Architecture

1.6 ARM Architecture
ARM Evolution
Instruction Set Architecture
ARM Products

1.7 Cloud Computing
Basic Concepts
Cloud Services

In describing computers, a distinction is often made between computer architec-ture and computer organization. Although it is difficult to give precise definitions for these terms, a consensus exists about the general areas covered by each. For example, see [VRAN80], [SIEW82], and [BELL78a]; an interesting alternative view is presented in [REDD76].

Computer architecture refers to those attributes of a system visible to a pro-grammer or, put another way, those attributes that have a direct impact on the logical execution of a program. A term that is often used interchangeably with com-puter architecture is instruction set architecture (ISA). The ISA defines instruction formats, instruction opcodes, registers, instruction and data memory; the effect of executed instructions on the registers and memory; and an algorithm for control-ling instruction execution. Computer organization refers to the operational units and their interconnections that realize the architectural specifications. Examples of architectural attributes include the instruction set, the number of bits used to repre-sent various data types (e.g., numbers, characters), I/O mechanisms, and techniques for addressing memory. Organizational attributes include those hardware details transparent to the programmer, such as control signals; interfaces between the com-puter and peripherals; and the memory technology used.

In a class of computers called microcomputers, the relationship between archi-tecture and organization is very close. Changes in technology not only influence organization but also result in the introduction of more powerful and more complex architectures. Generally, there is less of a requirement for generation- to- generation compatibility for these smaller machines. Thus, there is more interplay between organizational and architectural design decisions. An intriguing example of this is the reduced instruction set computer (RISC), which we examine in Chapter 15.

This book examines both computer organization and computer architecture. The emphasis is perhaps more on the side of organization. However, because a computer organization must be designed to implement a particular architectural specification, a thorough treatment of organization requires a detailed examination of architecture as well.

■ Function: The operation of each individual component as part of the structure.

In terms of description, we have two choices: starting at the bottom and build-ing up to a complete description, or beginning with a top view and decomposing the system into its subparts. Evidence from a number of fields suggests that the top- down approach is the clearest and most effective [WEIN75].

Both the structure and functioning of a computer are, in essence, simple. In general terms, there are only four basic functions that a computer can perform:

■ Data processing: Data may take a wide variety of forms, and the range of pro-cessing requirements is broad. However, we shall see that there are only a few fundamental methods or types of data processing.

There is remarkably little shaping of computer structure to fit the function to be performed. At the root of this lies the general- purpose nature of computers, in which all the functional specialization occurs at the time of programming and not at the time of design.

Structure

1.2 / struCture and FunCtion 5

CPU

Internal
bus

Control
memory

Figure 1.1 The Computer: Top- Level Structure

Each of these components will be examined in some detail in Part Two. How-ever, for our purposes, the most interesting and in some ways the most complex component is the CPU. Its major structural components are as follows:

■ Control unit: Controls the operation of the CPU and hence the computer.

multicorecomputerstructure As was mentioned, contemporary computers generally have multiple processors. When these processors all reside on a single chip, the term multicore computer is used, and each processing unit (consisting of a control unit, ALU, registers, and perhaps cache) is called a core. To clarify the terminology, this text will use the following definitions.

■ Central processing unit (CPU): That portion of a computer that fetches and executes instructions. It consists of an ALU, a control unit, and registers. In a system with a single processing unit, it is often simply referred to as a processor.

1.2 / struCture and FunCtion 7

I/O chips chip

PROCESSOR CHIP

Arithmetic
Instruction Load/
and logic
logic store logic
unit (ALU)

L1 I-cache L1 data cache

Figure 1.2 shows a processor chip that contains eight cores and an L3 cache. Not shown is the logic required to control operations between the cores and the cache and between the cores and the external circuitry on the motherboard. The figure indicates that the L3 cache occupies two distinct portions of the chip surface. However, typically, all cores have access to the entire L3 cache via the aforemen-tioned control circuits. The processor chip shown in Figure 1.2 does not represent any specific product, but provides a general idea of how such chips are laid out.

Next, we zoom in on the structure of a single core, which occupies a portion of the processor chip. In general terms, the functional elements of a core are:

Keep in mind that this representation of the layout of the core is only intended to give a general idea of internal core structure. In a given product, the functional elements may not be laid out as the three distinct elements shown in Figure 1.2, especially if some or all of these functions are implemented as part of a micropro-grammed control unit.

examples It will be instructive to look at some real- world examples that illustrate the hierarchical structure of computers. Figure 1.3 is a photograph of the motherboard for a computer built around two Intel Quad- Core Xeon processor chips. Many of the elements labeled on the photograph are discussed subsequently in this book. Here, we mention the most important, in addition to the processor sockets:

1.2 / struCture and FunCtion 9

Intel® 3420

2x USB 2.0
Internal
2x USB 2.0
External

Figure 1.3 Motherboard with Two Intel Quad- Core Xeon Processors Source: Chassis Plans, www.chassis-plans.com

Going down one level deeper, we examine the internal structure of a single core, as shown in the photograph of Figure 1.5. Keep in mind that this is a portion of the silicon surface area making up a single- processor chip. The main sub- areas within this core area are the following:

■ ISU (instruction sequence unit): Determines the sequence in which instructions are executed in what is referred to as a superscalar architecture (Chapter 16).

Figure 1.5 zEnterprise EC12 Core layout Source: IBM zEnterprise EC12 Technical Guide, December 2013, SG24-8049-01. IBM, Reprinted by

■ FXU ( fixed- point unit): The FXU executes fixed- point arithmetic operations.

■ BFU (binary floating- point unit): The BFU handles all binary and hexadeci-mal floating- point operations, as well as fixed- point multiplication operations.

■ COP (dedicated co- processor): The COP is responsible for data compression and encryption functions for each core.

■ I- cache: This is a 64-kB L1 instruction cache, allowing the IFU to prefetch instructions before they are needed.

1.3 a BrieF hiStOry OF cOmputerS2

In this section, we provide a brief overview of the history of the development of computers. This history is interesting in itself, but more importantly, provides a basic introduction to many important concepts that we deal with throughout the book.

■ A main memory, which stores both data and instructions5

■ An arithmetic and logic unit (ALU) capable of operating on binary data

12 Chapter 1 / BasiC ConCepts and Computer evolution

Central processing unit (CPU)

Instructions
and data

(M)

Addresses

Figure 1.6 IAS Structure

1.3 / a BrieF history oF Computers 13

It must be observed, however, that while this principle as such is probably sound, the specific way in which it is realized requires close scrutiny. At any rate a central arithmetical part of the device will probably have to exist, and this constitutes the first specific part: CA.

2.6 The three specific parts CA, CC (together C), and M cor-respond to the associative neurons in the human nervous system. It remains to discuss the equivalents of the sensory or afferent and the motor or efferent neurons. These are the input and output organs of the device.

The device must be endowed with the ability to maintain input and output (sensory and motor) contact with some specific medium of this type. The medium will be called the outside record-ing medium of the device: R.

are changed in the following to conform more closely to modern usage; the exam-ples accompanying this discussion are based on that latter text.

The memory of the IAS consists of 4,096 storage locations, called words, of 40 binary digits (bits) each.6 Both data and instructions are stored there. Numbers are represented in binary form, and each instruction is a binary code. Figure 1.7 illustrates these formats. Each number is represented by a sign bit and a 39-bit value. A word may alternatively contain two 20-bit instructions, with each instruction consisting of an 8-bit operation code (opcode) specifying the operation to be performed and a 12-bit address designating one of the words in memory (numbered from 0 to 999).

■ Instruction buffer register (IBR): Employed to hold temporarily the right- hand instruction from a word in memory.

■ Program counter (PC): Contains the address of the next instruction pair to be fetched from memory.

left instruction (20 bits) right instruction (20 bits)

6There is no universal definition of the term word. In general, a word is an ordered set of bytes or bits that is the normal unit in which information may be stored, transmitted, or operated on within a given computer. Typically, if a processor has a fixed- length instruction set, then the instruction length equals the word length.

Start

PC PC + 1

Decode instruction in IR

M(X) = contents of memory location whose address is X (i:j) = bits i through j

Figure 1.8 Partial Flowchart of IAS Operation

■ Data transfer: Move data between memory and ALU registers or between two ALU registers.

■ Unconditional branch: Normally, the control unit executes instructions in sequence from memory. This sequence can be changed by a branch instruc-tion, which facilitates repetitive operations.

1.3 / a BrieF history oF Computers 17

■ Conditional branch: The branch can be made dependent on a condition, thus allowing decision points.

The Second Generation: Transistors

The first major change in the electronic computer came with the replacement of the vacuum tube by the transistor. The transistor, which is smaller, cheaper, and gener-ates less heat than a vacuum tube, can be used in the same way as a vacuum tube to construct computers. Unlike the vacuum tube, which requires wires, metal plates, a glass capsule, and a vacuum, the transistor is a solid- state device, made from silicon.

Also, over the lifetime of this series of computers, the relative speed of the CPU increased by a factor of 50. Speed improvements are achieved by improved electronics (e.g., a transistor implementation is faster than a vacuum tube imple-mentation) and more complex circuitry. For example, the IBM 7094 includes an Instruction Backup Register, used to buffer the next instruction. The control unit fetches two adjacent words from memory for an instruction fetch. Except for the occurrence of a branching instruction, which is relatively infrequent (perhaps 10 to 15%), this means that the control unit has to access memory for an instruction on only half the instruction cycles. This prefetching significantly reduces the average instruction cycle time.

Figure 1.9 shows a large (many peripherals) configuration for an IBM 7094, which is representative of second- generation computers. Several differences from the IAS computer are worth noting. The most important of these is the use of data channels. A data channel is an independent I/O module with its own processor and instruction set. In a computer system with such devices, the CPU does not execute detailed I/O instructions. Such instructions are stored in a main memory to be executed by a special- purpose processor in the data channel itself. The CPU initi-ates an I/O transfer by sending a control signal to the data channel, instructing it to execute a sequence of instructions in memory. The data channel performs its task independently of the CPU and signals the CPU when the operation is complete. This arrangement relieves the CPU of a considerable processing burden.

1.3 / a BrieF history oF Computers 19

Disk

In 1958 came the achievement that revolutionized electronics and started the era of microelectronics: the invention of the integrated circuit. It is the integrated circuit that defines the third generation of computers. In this section, we provide a brief introduction to the technology of integrated circuits. Then we look at perhaps the two most important members of the third generation, both of which were intro-duced at the beginning of that era: the IBM System/360 and the DEC PDP- 8.

microelectronics Microelectronics means, literally, “small electronics.” Since the beginnings of digital electronics and the computer industry, there has been a persistent and consistent trend toward the reduction in size of digital electronic circuits. Before examining the implications and benefits of this trend, we need to say something about the nature of digital electronics. A more detailed discussion is found in Chapter 11.

■ Data processing: Provided by gates.

■ Data movement: The paths among components are used to move data from memory to memory and from memory through gates to memory.

Initially, only a few gates or memory cells could be reliably manufactured and packaged together. These early integrated circuits are referred to as small- scale integration(SSI). As time went on, it became possible to pack more and more com-ponents on the same chip. This growth in density is illustrated in Figure 1.12; it is one of the most remarkable technological trends ever recorded.8 This figure reflects the famous Moore’s law, which was propounded by Gordon Moore, cofounder of Intel, in 1965 [MOOR65]. Moore observed that the number of transistors that could be put on a single chip was doubling every year, and correctly predicted that this pace would continue into the near future. To the surprise of many, including Moore, the pace continued year after year and decade after decade. The pace slowed to a doubling every 18 months in the 1970s but has sustained that rate ever since.

The consequences of Moore’s law are profound:

Packaged
chip

Figure 1.11 Relationship among
Wafer, Chip, and Gate

4. There is a reduction in power requirements.

5. The interconnections on the integrated circuit are much more reliable than solder connections. With more circuitry on each chip, there are fewer inter-chip connections.

10,000

1,000

100 m

10 m

sense that a program written for one model should be capable of being executed by another model in the series, with only a difference in the time it takes to execute.

The concept of a family of compatible computers was both novel and extremely successful. A customer with modest requirements and a budget to match could start with the relatively inexpensive Model 30. Later, if the customer’s needs grew, it was possible to upgrade to a faster machine with more memory without sacrificing the investment in already- developed software. The characteristics of a family are as follows:

■ Increasing memory size: The size of main memory increases in going from lower to higher family members.

■ Increasing cost: At a given point in time, the cost of a system increases in going from lower to higher family members.

24 Chapter 1 / BasiC ConCepts and Computer evolution

The low cost and small size of the PDP- 8 enabled another manufacturer to purchase a PDP- 8 and integrate it into a total system for resale. These other manu-facturers came to be known as original equipment manufacturers (OEMs), and the OEM market became and remains a major segment of the computer marketplace.

semiconductormemory The first application of integrated circuit technology to computers was the construction of the processor (the control unit and the arithmetic and logic unit) out of integrated circuit chips. But it was also found that this same technology could be used to construct memories.

In the 1950s and 1960s, most computer memory was constructed from tiny rings of ferromagnetic material, each about a sixteenth of an inch in diameter. These rings were strung up on grids of fine wires suspended on small screens inside the computer. Magnetized one way, a ring (called a core) represented a one; mag-netized the other way, it stood for a zero. Magnetic- core memory was rather fast; it took as little as a millionth of a second to read a bit stored in memory. But it was

expensive and bulky, and used destructive readout: The simple act of reading a core erased the data stored in it. It was therefore necessary to install circuits to restore the data as soon as it had been extracted.

Then, in 1970, Fairchild produced the first relatively capacious semiconductor memory. This chip, about the size of a single core, could hold 256 bits of memory. It was nondestructive and much faster than core. It took only 70 billionths of a second to read a bit. However, the cost per bit was higher than for that of core.

The 4004 can add two 4-bit numbers and can multiply only by repeated addi-tion. By today’s standards, the 4004 is hopelessly primitive, but it marked the begin-ning of a continuing evolution of microprocessor capability and power.

This evolution can be seen most easily in the number of bits that the processor deals with at a time. There is no clear- cut measure of this, but perhaps the best meas-ure is the data bus width: the number of bits of data that can be brought into or sent out of the processor at a time. Another measure is the number of bits in the accumu-lator or in the set of general- purpose registers. Often, these measures coincide, but not always. For example, a number of microprocessors were developed that operate on 16-bit numbers in registers but can only read and write 8 bits at a time.

About the same time, 16-bit microprocessors began to be developed. How-ever, it was not until the end of the 1970s that powerful, general- purpose 16-bit microprocessors appeared. One of these was the 8086. The next step in this trend occurred in 1981, when both Bell Labs and Hewlett- Packard developed 32-bit, single- chip microprocessors. Intel introduced its own 32-bit microprocessor, the 80386, in 1985 (Table 1.3).

Table 1.3 Evolution of Intel Microprocessors (page 1 of 2)

(c) 1990s Processors

1.4 the evOlutiOn OF the intel x86 architecture

28 Chapter 1 / BasiC ConCepts and Computer evolution

It is worthwhile to list some of the highlights of the evolution of the Intel prod-uct line:

■ 80486: The 80486 introduced the use of much more sophisticated and power-ful cache technology and sophisticated instruction pipelining. The 80486 also offered a built- in math coprocessor, offloading complex math operations from the main CPU.

■ Pentium: With the Pentium, Intel introduced the use of superscalar tech- niques, which allow multiple instructions to execute in parallel.

■ Core: This is the first Intel x86 microprocessor with a dual core, referring to the implementation of two cores on a single chip.

■ Core 2: The Core 2 extends the Core architecture to 64 bits. The Core 2 Quad provides four cores on a single chip. More recent Core offerings have up to 10 cores per chip. An important addition to the architecture was the Advanced Vector Extensions instruction set that provided a set of 256-bit, and then 512-bit, instructions for efficient processing of vector data.

1.5 emBedded SyStemS

The term embedded system refers to the use of electronics and software within a product, as opposed to a general- purpose computer, such as a laptop or desktop sys-tem. Millions of computers are sold every year, including laptops, personal comput-ers, workstations, servers, mainframes, and supercomputers. In contrast, billions of computer systems are produced each year that are embedded within larger devices. Today, many, perhaps most, devices that use electric power have an embedded com-puting system. It is likely that in the near future virtually all such devices will have embedded computing systems.

30 Chapter 1 / BasiC ConCepts and Computer evolution

Figure 1.14 Possible Organization of an Embedded System

reactive system is in continual interaction with the environment and executes at a pace determined by that environment.

■ Efficiency is of paramount importance for embedded systems. They are opti- mized for energy, code size, execution time, weight and dimensions, and cost.

There are several noteworthy areas of similarity to general- purpose computer systems as well:

1.5 / emBedded systems 31

interconnection of smart devices, ranging from appliances to tiny sensors. A domi-nant theme is the embedding of short- range mobile transceivers into a wide array of gadgets and everyday items, enabling new forms of communication between people and things, and between things themselves. The Internet now supports the intercon-nection of billions of industrial and personal objects, usually through cloud systems. The objects deliver sensor information, act on their environment, and, in some cases, modify themselves, to create overall management of a larger system, like a factory or city.

3. Personal technology: Smartphones, tablets, and eBook readers bought as IT devices by consumers (employees) exclusively using wireless connectivity and often multiple forms of wireless connectivity.

4. Sensor/actuator technology: Single- purpose devices bought by consumers, IT, and OT people exclusively using wireless connectivity, generally of a single form, as part of larger systems.

In this subsection, and the next two, we briefly introduce some terms commonly found in the literature on embedded systems. Application processors are defined

32 Chapter 1 / BasiC ConCepts and Computer evolution

A microcontroller chip makes a substantially different use of the logic space available. Figure 1.15 shows in general terms the elements typically found on a microcontroller chip. As shown, a microcontroller is a single chip that contains the processor, non- volatile memory for the program (ROM), volatile memory for input and output (RAM), a clock, and an I/O control unit. The processor portion of the microcontroller has a much lower silicon area than other microprocessors and much higher energy efficiency. We examine microcontroller organization in more detail in Section 1.6.

Also called a “computer on a chip,” billions of microcontroller units are embedded each year in myriad products from toys to appliances to automobiles. For example, a single vehicle can use 70 or more microcontrollers. Typically, especially for the smaller, less expensive microcontrollers, they are used as dedicated proces-sors for specific tasks. For example, microcontrollers are heavily utilized in automa-tion processes. By providing simple reactions to input, they can control machinery, turn fans on and off, open and close valves, and so forth. They are integral parts of modern industrial technology and are among the most inexpensive ways to produce machinery that can handle extremely complex functionalities.

1.6 / arm arChiteCture 33

Processor

literature, you will search the Internet in vain (or at least I did) for a straightfor-ward definition. Generally, we can say that a deeply embedded system has a proces-sor whose behavior is difficult to observe both by the programmer and the user. A deeply embedded system uses a microcontroller rather than a microprocessor, is not programmable once the program logic for the device has been burned into ROM ( read- only memory), and has no interaction with a user.

Deeply embedded systems are dedicated, single- purpose devices that detect something in the environment, perform a basic level of processing, and then do some-thing with the results. Deeply embedded systems often have wireless capability and appear in networked configurations, such as networks of sensors deployed over a large area (e.g., factory, agricultural field). The Internet of things depends heavily on deeply embedded systems. Typically, deeply embedded systems have extreme resource con-straints in terms of memory, processor size, time, and power consumption.

ARM is a family of RISC- based microprocessors and microcontrollers designed by ARM Holdings, Cambridge, England. The company doesn’t make processors but instead designs microprocessor and multicore architectures and licenses them to man-ufacturers. Specifically, ARM Holdings has two types of licensable products: proces-sors and processor architectures. For processors, the customer buys the rights to use ARM- supplied design in their own chips. For a processor architecture, the customer buys the rights to design their own processor compliant with ARM’s architecture.

ARM chips are high- speed processors that are known for their small die size and low power requirements. They are widely used in smartphones and other hand-held devices, including game systems, as well as a large variety of consumer prod-ucts. ARM chips are the processors in Apple’s popular iPod and iPhone devices, and are used in virtually all Android smartphones as well. ARM is probably the most widely used embedded processor architecture and indeed the most widely used processor architecture of any kind in the world [VANC14].

The ARM instruction set is highly regular, designed for efficient implementation of the processor and efficient execution. All instructions are 32 bits long and follow a regular format. This makes the ARM ISA suitable for implementation over a wide range of products.

Augmenting the basic ARM ISA is the Thumb instruction set, which is a re- encoded subset of the ARM instruction set. Thumb is designed to increase the per-formance of ARM implementations that use a 16-bit or narrower memory data bus,

ARM Products

ARM Holdings licenses a number of specialized microprocessors and related tech-nologies, but the bulk of their product line is the Cortex family of microprocessor architectures. There are three Cortex architectures, conveniently labeled with the initials A, R, and M.

cortex- m Cortex- M series processors have been developed primarily for the microcontroller domain where the need for fast, highly deterministic interrupt management is coupled with the desire for extremely low gate count and lowest possible power consumption. As with the Cortex- R series, the Cortex- M architecture has an MPU but no MMU. The Cortex- M uses only the Thumb- 2 instruction set. The market for the Cortex- M includes IoT devices, wireless sensor/actuator networks used in factories and other enterprises, automotive body electronics, and so on.

36 Chapter 1 / BasiC ConCepts and Computer evolution

In this text, we will primarily use the ARM Cortex- M3 as our example embed-ded system processor. It is the best suited of all ARM models for general- purpose microcontroller use. The Cortex- M3 is used by a variety of manufacturers of micro-controller products. Initial microcontroller devices from lead partners already combine the Cortex- M3 processor with flash, SRAM, and multiple peripherals to provide a competitive offering at the price of just $1.

Figure 1.16 provides a block diagram of the EFM32 microcontroller from Sil-icon Labs. The figure also shows detail of the Cortex- M3 processor and core com-ponents. We examine each level in turn.

■ Debug access port (DAP): This provides an interface for external debug access to the processor.

■ Debug logic: Basic debug functionality includes processor halt, single- step, processor core register access, unlimited software breakpoints, and full system memory access.

32-bit bus

Microcontroller Chip

Cortex-M3 Core

divider multiplier

Control Thumb

37

38 Chapter 1 / BasiC ConCepts and Computer evolution

The upper part of Figure 1.16 shows the block diagram of a typical micro-controller built with the Cortex- M3, in this case the EFM32 microcontroller. This microcontroller is marketed for use in a wide variety of devices, including energy, gas, and water metering; alarm and security systems; industrial automation devices; home automation devices; smart accessories; and health and fitness devices. The sil-icon chip consists of 10 main areas:13

■ Core and memory: This region includes the Cortex- M3 processor, static RAM (SRAM) data memory,14 and flash memory15 for storing program instructions and nonvarying application data. Flash memory is nonvolatile (data is not lost when power is shut off) and so is ideal for this purpose. The SRAM stores variable data. This area also includes a debug interface, which makes it easy to reprogram and update the system in the field.

■ Clock management: Controls the clocks and oscillators on the chip. Multiple clocks and oscillators are used to minimize power consumption and provide short startup times.

■ Energy management: Manages the various low- energy modes of operation of the processor and peripherals to provide real- time management of the energy needs so as to minimize energy consumption.

■ 32-bit bus: Connects all of the components on the chip.

■ Peripheral bus: A network which lets the different peripheral module commu-nicate directly with each other without involving the processor. This supports timing- critical operation and reduces software overhead.

There is an increasingly prominent trend in many organizations to move a substantial portion or even all information technology (IT) operations to an Internet- connected infrastructure known as enterprise cloud computing. At the same time, individual users of PCs and mobile devices are relying more and more on cloud computing services to backup data, synch devices, and share, using personal cloud computing. NIST defines cloud computing, in NIST SP- 800-145 (The NIST Definition of Cloud Computing), as follows:

Cloud computing: A model for enabling ubiquitous, convenient, on- demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction.

Cloud networking refers to the networks and network management function-ality that must be in place to enable cloud computing. Most cloud computing solu-tions rely on the Internet, but that is only a piece of the networking infrastructure. One example of cloud networking is the provisioning of high- performance and/or high- reliability networking between the provider and subscriber. In this case, some or all of the traffic between an enterprise and the cloud bypasses the Internet and uses dedicated private network facilities owned or leased by the cloud service pro-vider. More generally, cloud networking refers to the collection of network capa-bilities required to access a cloud, including making use of specialized services over the Internet, linking enterprise data centers to a cloud, and using firewalls and other network security devices at critical points to enforce access security policies.

We can think of cloud storage as a subset of cloud computing. In essence, cloud storage consists of database storage and database applications hosted remotely on cloud servers. Cloud storage enables small businesses and individual users to take advantage of data storage that scales with their needs and to take advantage of a variety of database applications without having to buy, maintain, and manage the storage assets.

42 Chapter 1 / BasiC ConCepts and Computer evolution

infrastructureasaservice (iaas) With IaaS, the customer has access to the underlying cloud infrastructure. IaaS provides virtual machines and other abstracted hardware and operating systems, which may be controlled through a service application programming interface (API). IaaS offers the customer processing, storage, networks, and other fundamental computing resources so that the customer is able to deploy and run arbitrary software, which can include operating systems and applications. IaaS enables customers to combine basic computing services, such as number crunching and data storage, to build highly adaptable computer systems. Examples of IaaS are Amazon Elastic Compute Cloud (Amazon EC2) and Windows Azure.

Review Questions

Assume that the computation does not result in an arithmetic overflow and that X, Y, and N are positive integers with N ≥ 1. Note: The IAS did not have assembly language, only machine language.

a. Use the equation Sum(Y) =

d. Is a PDA (Personal Digital Assistant) an embedded system?

e. Is the microprocessor controlling a cell phone an embedded system?

Chapter

Improvements in Chip Organization and Architecture

2.2 Multicore, MICs, and GPGPUs

Clock Speed

Instruction Execution Rate

2.6 Benchmarks and SPEC

Benchmark Principles

This chapter addresses the issue of computer system performance. We begin with a consideration of the need for balanced utilization of computer resources, which pro-vides a perspective that is useful throughout the book. Next we look at contemporary computer organization designs intended to provide performance to meet current and projected demand. Finally, we look at tools and models that have been devel-oped to provide a means of assessing comparative computer system performance.

■ Speech recognition

■ Videoconferencing

2.1 / DesIgnIng for performanCe 47

providers use massive high-performance banks of servers to satisfy high-volume, high-transaction-rate applications for a broad spectrum of clients.

But the raw speed of the microprocessor will not achieve its potential unless it is fed a constant stream of work to do in the form of computer instructions. Any-thing that gets in the way of that smooth flow undermines the power of the proces-sor. Accordingly, while the chipmakers have been busy learning how to fabricate chips of greater and greater density, the processor designers must come up with ever more elaborate techniques for feeding the monster. Among the techniques built into contemporary processors are the following:

■ Pipelining: The execution of an instruction involves multiple stages of oper-ation, including fetching the instruction, decoding the opcode, fetching oper-ands, performing a calculation, and so on. Pipelining enables a processor to work simultaneously on multiple instructions by performing a different phase for each of the multiple instructions at the same time. The processor over-laps operations by moving data or instructions into a conceptual pipe with all stages of the pipe processing simultaneously. For example, while one instruc-tion is being executed, the computer is decoding the next instruction. This is the same principle as seen in an assembly line.

■ Data flow analysis: The processor analyzes which instructions are dependent on each other’s results, or data, to create an optimized schedule of instruc-tions. In fact, instructions are scheduled to be executed when ready, independ-ent of the original program order. This prevents unnecessary delay.

■ Speculative execution: Using branch prediction and data flow analysis, some processors speculatively execute instructions ahead of their actual appearance in the program execution, holding the results in temporary locations. This ena-bles the processor to keep its execution engines as busy as possible by execut-ing instructions that are likely to be needed.

A system architect can attack this problem in a number of ways, all of which are reflected in contemporary computer designs. Consider the following examples:

■ Increase the number of bits that are retrieved at one time by making DRAMs “wider” rather than “deeper” and by using wide bus data paths.

■ Increase the interconnect bandwidth between processors and memory by using higher-speed buses and a hierarchy of buses to buffer and structure data flow.

Another area of design focus is the handling of I/O devices. As computers become faster and more capable, more sophisticated applications are developed that support the use of peripherals with intensive I/O demands. Figure 2.1 gives some examples of typical peripheral devices in use on personal computers and workstations. These devices create tremendous data throughput demands. While the current generation of processors can handle the data pumped out by these devices, there remains the problem of getting that data moved between processor and peripheral. Strategies here include caching and buffering schemes plus the use of higher-speed interconnection buses and more elaborate interconnection struc-tures. In addition, the use of multiple-processor configurations can aid in satisfying I/O demands.

Figure 2.1 Typical I/O Device Data Rates

50 Chapter 2 / performanCe Issues

■ Increase the size and speed of caches that are interposed between the proces-sor and main memory. In particular, by dedicating a portion of the processor chip itself to the cache, cache access times drop significantly.

■ Make changes to the processor organization and architecture that increase the effective speed of instruction execution. Typically, this involves using parallel-ism in one form or another.

Thus, there will be more emphasis on organization and architectural approaches to improving performance. These techniques are discussed in later chapters of the text.

Beginning in the late 1980s, and continuing for about 15 years, two main strat-egies have been used to increase performance beyond what can be achieved simply by increasing clock speed. First, there has been an increase in cache capacity. There are now typically two or three levels of cache between the processor and main mem-ory. As chip density has increased, more of the cache memory has been incorpor-ated on the chip, enabling faster cache access. For example, the original Pentium

By the mid to late 90s, both of these approaches were reaching a point of diminishing returns. The internal organization of contemporary processors is exceedingly complex and is able to squeeze a great deal of parallelism out of the instruction stream. It seems likely that further significant increases in this direction will be relatively modest [GIBB04]. With three levels of cache on the processor chip, each level providing substantial capacity, it also seems that the benefits from the cache are reaching a limit.

However, simply relying on increasing clock rate for increased performance runs into the power dissipation problem already referred to. The faster the clock rate, the greater the amount of power to be dissipated, and some fundamental phys-ical limits are being reached.

Figure 2.2 Processor Trends

With all of the difficulties cited in the preceding section in mind, designers have turned to a fundamentally new approach to improving performance: placing multiple processors on the same chip, with a large shared cache. The use of multiple proces-sors on the same chip, also referred to as multiple cores, or multicore, provides the potential to increase performance without increasing the clock rate. Studies indicate that, within a processor, the increase in performance is roughly proportional to the square root of the increase in complexity [BORK03]. But if the software can support the effective use of multiple processors, then doubling the number of processors almost doubles performance. Thus, the strategy is to use two simpler processors on the chip rather than one more complex processor.

In addition, with two processors, larger caches are justified. This is important because the power consumption of memory logic on a chip is much less than that of processing logic.

3The observant reader will note that the transistor count values in this figure are significantly less than those of Figure 1.12. That latter figure shows the transistor count for a form of main memory known as DRAM (discussed in Chapter 5), which supports higher transistor density than processor chips.

2.3 / two Laws that provIDe InsIght: ahmDahL’s Law anD LIttLe’s Law 53

Amdahl’s Law

Computer system designers look for ways to improve system performance by advances in technology or change in design. Examples include the use of parallel processors, the use of a memory cache hierarchy, and speedup in memory access time and I/O transfer rate due to technology improvements. In all of these cases, it is important to note that a speedup in one aspect of the technology or design does not result in a corresponding improvement in performance. This limitation is succinctly expressed by Amdahl’s law.

1. When f is small, the use of parallel processors has little effect.

2. As N approaches infinity, speedup is bound by 1/(1 - f ), so that there are diminishing returns for using more processors.

(1 – f )T fT

(2.1)

20

f = 0.5

Number of Processors

56 Chapter 2 / performanCe Issues

In evaluating processor hardware and setting requirements for new systems, per-formance is one of the key parameters to consider, along with cost, size, security, reliability, and, in some cases, power consumption.

It is difficult to make meaningful performance comparisons among different processors, even among processors in the same family. Raw speed is far less import-ant than how a processor performs when executing a given application. Unfortu-nately, application performance depends not just on the raw speed of the processor but also on the instruction set, choice of implementation language, efficiency of the compiler, and skill of the programming done to implement the application.

Operations performed by a processor, such as fetching an instruction, decoding the instruction, performing an arithmetic operation, and so on, are governed by a system clock. Typically, all operations begin with the pulse of the clock. Thus, at the most fundamental level, the speed of a processor is dictated by the pulse frequency pro-duced by the clock, measured in cycles per second, or Hertz (Hz).

Typically, clock signals are generated by a quartz crystal, which generates a constant sine wave while power is applied. This wave is converted into a digital voltage pulse stream that is provided in a constant flow to the processor circuitry (Figure 2.5). For example, a 1-GHz processor receives 1 billion pulses per second. The rate of pulses is known as the clock rate, or clock speed. One increment, or pulse, of the clock is referred to as a clock cycle, or a clock tick. The time between pulses is the cycle time.

58 Chapter 2 / performanCe Issues

Instruction Execution Rate

T = Ic * CPI * t

We can refine this formulation by recognizing that during the execution of an instruction, part of the work is done by the processor, and part of the time a word is being transferred to or from memory. In this latter case, the time to transfer depends on the memory cycle time, which may be greater than the processor cycle time. We can rewrite the preceding equation as

the benchmarking field. In this section, we define these alternative algorithms and comment on some of their properties. This prepares us for a discussion in the next section of mean calculation in benchmarking.

The three common formulas used for calculating a mean are arithmetic, geo-metric, and harmonic. Given a set of n real numbers (x1, x2, …, xn), the three means are defined as follows:

through (2.3) are special cases of the functional mean, as follows:

MD = median
AM = arithmetic mean GM = geometric mean HM = harmonic mean

Figure 2.6 Comparison of Means on Various Data Sets (each set has a maximum data point value of 11)

The AM used for a time-based variable (e.g., seconds), such as program exe-cution time, has the important property that it is directly proportional to the total time. So, if the total time doubles, the mean value doubles.

Harmonic Mean

64 Chapter 2 / performanCe Issues

1. A customer or researcher may be interested not only in the overall average performance but also performance against different types of benchmark pro-grams, such as business applications, scientific modeling, multimedia appli-cations, and systems programs. Thus, a breakdown by type of benchmark is needed as well as a total.

Geometric Mean

(a) Results normalized to Computer A

(b) Results normalized to Computer B

Table 2.4 Another Comparison of Arithmetic and Geometric Means for Normalized Results

(a) Results normalized to Computer A

(b) Results normalized to Computer B

2.6 / BenChmarks anD speC 67

2.6 Benchmarks anD sPec

Benchmark Principles

Another consideration is that the performance of a given processor on a given program may not be useful in determining how that processor will perform on a very different type of application. Accordingly, beginning in the late 1980s and early 1990s, industry and academic interest shifted to measuring the performance of

2. It is representative of a particular kind of programming domain or paradigm, such as systems programming, numerical programming, or commercial programming.

3. It can be measured easily.

Other SPEC suites include the following:

■ SPECviewperf: Standard for measuring 3D graphics performance based on professional applications.

■ SPECvirt_sc2013: Performance evaluation of datacenter servers used in vir-tualized server consolidation. Measures the end-to-end performance of all system components including the hardware, virtualization platform, and the virtualized guest operating system and application software. The benchmark supports hardware virtualization, operating system virtualization, and hard-ware partitioning schemes.

2.6 / BenChmarks anD speC 69

70 Chapter 2 / performanCe Issues
Table 2.6 SPEC CPU2006 Floating-Point Benchmarks

processor-intensive suites from SPEC, replacing SPEC CPU2000, SPEC CPU95, SPEC CPU92, and SPEC CPU89 [HENN07].

To better understand published results of a system using CPU2006, we define the following terms used in the SPEC documentation:

■ Peak metric: This enables users to attempt to optimize system performance by optimizing the compiler output. For example, different compiler options may be used on each benchmark, and feedback-directed optimization is allowed.

■ Speed metric: This is simply a measurement of the time it takes to execute a compiled benchmark. The speed metric is used for comparing the ability of a computer to complete single tasks.

72 Chapter 2 / performanCe Issues

Ratio(prog) =
Tref(prog)/TSUT(prog)

where Trefi is the execution time of benchmark program i on the reference system and Tsuti is the execution time of benchmark program i on the system under test. Thus, ratios are higher for faster machines.

3. Finally, the geometric mean of the 12 runtime ratios is calculated to yield the overall metric:

■ SPECint_rate_base2006: The geometric mean of 12 normalized throughput ratios when the benchmarks are compiled with base tuning.

2.6 / BenChmarks anD speC 73

2.7 key terms, review Questions, anD ProBlems

Key Terms

Review Questions

Problems

Determine the effective CPI, MIPS rate, and execution time for this program.

76 Chapter 2 / performanCe Issues

The final column shows that the VAX required 12 times longer than the IBM mea-sured in CPU time.

c. Which machine is the slowest based on each of the preceding two calculations? d. Repeat the calculations of parts (a) and (b) using the geometric mean, defined in Equation (2.6). Which machine is the slowest based on the two calculations?

2.7 / key terms, revIew QuestIons, anD proBLems 77

b. Figure 2.8c divides the total area into vertical rectangles, defined by the vertical transition boundaries indicated by the dashed lines. Picture sliding all these rect-angles down so that their lower edges line up at N(t) = 0. Develop an equation that relates A, T, and L.

c. Finally, derive L = lW from the results of (a) and (b).

(a) Arrival and completion of jobs N(t)

(b) Viewed as horizontal rectangles

Figure 2.8 Illustration of Little’s Law

2.7 / key terms, revIew QuestIons, anD proBLems 79

Part two The CompuTer
SySTem

Chapter

3.4 Bus Interconnection

3.5 Point-to-Point Interconnect
QPI Physical Layer
QPI Link Layer
QPI Routing Layer
QPI Protocol Layer

At a top level, a computer consists of CPU (central processing unit), memory, and I/O components, with one or more modules of each type. These components are interconnected in some fashion to achieve the basic function of the computer, which is to execute programs. Thus, at a top level, we can characterize a computer system by describing (1) the external behavior of each component, that is, the data and control signals that it exchanges with other components, and (2) the intercon-nection structure and the controls required to manage the use of the interconnec-tion structure.

■ Data and instructions are stored in a single read–write memory.

■ The contents of this memory are addressable by location, without regard to the type of data contained there.

Now consider this alternative. Suppose we construct a general-purpose con-figuration of arithmetic and logic functions. This set of hardware will perform vari-ous functions on data depending on control signals applied to the hardware. In the original case of customized hardware, the system accepts data and produces results (Figure 3.1a). With general-purpose hardware, the system accepts data and control signals and produces results. Thus, instead of rewiring the hardware for each new program, the programmer merely needs to supply a new set of control signals.

How shall control signals be supplied? The answer is simple but subtle. The entire program is actually a sequence of steps. At each step, some arithmetic or logical operation is performed on some data. For each step, a new set of control sig-nals is needed. Let us provide a unique code for each possible set of control signals,

(b) Programming in software

Figure 3.1 Hardware and Software Approaches

One more component is needed. An input device will bring instructions and data in sequentially. But a program is not invariably executed sequentially; it may jump around (e.g., the IAS jump instruction). Similarly, operations on data may require access to more than just one element at a time in a predetermined sequence. Thus, there must be a place to temporarily store both instructions and data. That module is called memory, or main memory, to distinguish it from external storage or peripheral devices. Von Neumann pointed out that the same memory could be used to store both instructions and data.

Figure 3.2 illustrates these top-level components and suggests the interac-tions among them. The CPU exchanges data with memory. For this purpose, it typ-ically makes use of two internal (to the CPU) registers: a memory address register (MAR), which specifies the address in memory for the next read or write, and a memory buffer register (MBR), which contains the data to be written into memory or receives the data read from memory. Similarly, an I/O address register (I/OAR) specifies a particular I/O device. An I/O buffer register (I/OBR) is used for the exchange of data between an I/O module and the CPU.

84 Chapter 3 / a top-LeveL view of Computer funCtion and interConneCtion

I/O AR

At the beginning of each instruction cycle, the processor fetches an instruction from memory. In a typical processor, a register called the program counter (PC) holds the address of the instruction to be fetched next. Unless told otherwise, the processor

always increments the PC after each instruction fetch so that it will fetch the next instruction in sequence (i.e., the instruction located at the next higher memory address). So, for example, consider a computer in which each instruction occupies one 16-bit word of memory. Assume that the program counter is set to memory loca-tion 300, where the location address refers to a 16-bit word. The processor will next fetch the instruction at location 300. On succeeding instruction cycles, it will fetch instructions from locations 301, 302, 303, and so on. This sequence may be altered, as explained presently.

The fetched instruction is loaded into a register in the processor known as the instruction register (IR). The instruction contains bits that specify the action the processor is to take. The processor interprets the instruction and performs the required action. In general, these actions fall into four categories:

An instruction’s execution may involve a combination of these actions.

Consider a simple example using a hypothetical machine that includes the characteristics listed in Figure 3.4. The processor contains a single data register, called an accumulator (AC). Both instructions and data are 16 bits long. Thus, it is convenient to organize memory using 16-bit words. The instruction format provides 4 bits for the opcode, so that there can be as many as 24= 16 different opcodes, and up to 212= 4096 (4K) words of memory can be directly addressed.

(a) Instruction format

0001 = Load AC from memory
0010 = Store AC to memory
0101 = Add to AC from memory

(d) Partial list of opcodes Figure 3.4 Characteristics of a Hypothetical Machine

1. The PC contains 300, the address of the first instruction. This instruction (the value 1940 in hexadecimal) is loaded into the instruction register IR, and the PC is incremented. Note that this process involves the use of a memory address register and a memory buffer register. For simplicity, these intermedi-ate registers are ignored.

2. The first 4 bits (first hexadecimal digit) in the IR indicate that the AC is to be loaded. The remaining 12 bits (three hexadecimal digits) specify the address (940) from which data are to be loaded.

In this example, three instruction cycles, each consisting of a fetch cycle and an execute cycle, are needed to add the contents of location 940 to the contents of 941. With a more complex set of instructions, fewer cycles would be needed. Some older processors, for example, included instructions that contain more than one memory address. Thus, the execution cycle for a particular instruction on such processors could involve more than one reference to memory. Also, instead of memory refer-ences, an instruction may specify an I/O operation.

For example, the PDP-11 processor includes an instruction, expressed symboli-cally as ADD B,A, that stores the sum of the contents of memory locations B and A into memory location A. A single instruction cycle with the following steps occurs:

■ Write the result from the processor to memory location A.

Thus, the execution cycle for a particular instruction may involve more than one reference to memory. Also, instead of memory references, an instruction may specify an I/O operation. With these additional considerations in mind, Figure 3.6 provides a more detailed look at the basic instruction cycle of Figure 3.3. The figure is in the form of a state diagram. For any given instruction cycle, some states may be null and others may be visited more than once. The states can be described as follows:

■ Instruction operation decoding (iod): Analyze instruction to determine type of operation to be performed and operand(s) to be used.

■ Operand address calculation (oac): If the operation involves reference to an operand in memory or available via I/O, then determine the address of the operand.

Also note that the diagram allows for multiple operands and multiple results, because some instructions on some machines require this. For example, the PDP-11 instruction ADD A,B results in the following sequence of states: iac, if, iod, oac, of, oac, of, do, oac, os.

Finally, on some machines, a single instruction can specify an operation to be per-formed on a vector (one-dimensional array) of numbers or a string (one-dimensional

Interrupts are provided primarily as a way to improve processing efficiency. For example, most external devices are much slower than the processor. Suppose that the processor is transferring data to a printer using the instruction cycle scheme of Figure 3.3. After each write operation, the processor must pause and remain idle until the printer catches up. The length of this pause may be on the order of many hundreds or even thousands of instruction cycles that do not involve memory. Clearly, this is a very wasteful use of the processor.

Figure 3.7a illustrates this state of affairs. The user program performs a ser-ies of WRITE calls interleaved with processing. Code segments 1, 2, and 3 refer to sequences of instructions that do not involve I/O. The WRITE calls are to an I/O program that is a system utility and that will perform the actual I/O operation. The I/O program consists of three sections:

5
2a

3a
3 3 3b

= interrupt occurs during course of execution of user program
Figure 3.7 Program Flow of Control without and with Interrupts

3.2 / Computer funCtion 91

•
•
•

M

Interrupts
disabled

3.2 / Computer funCtion 93

(current contents of the program counter) and any other data relevant to the processor’s current activity.

Time

2

4

(b) With interrupts

3

shaded gray. Figure 3.10a shows the case in which interrupts are not used. The pro-cessor must wait while an I/O operation is performed.

Figures 3.7b and 3.10b assume that the time required for the I/O operation is rela-tively short: less than the time to complete the execution of instructions between write operations in the user program. In this case, the segment of code labeled code segment 2 is interrupted. A portion of the code (2a) executes (while the I/O operation is performed) and then the interrupt occurs (upon the completion of the I/O operation). After the inter-rupt is serviced, execution resumes with the remainder of code segment 2 (2b).

3 I/O operation
concurrent with I/O operation; processor executing; processor waits then processor waits

Figure 3.11 Program Timing: Long I/O Wait

3.2 / Computer funCtion 95

The drawback to the preceding approach is that it does not take into account relative priority or time-critical needs. For example, when input arrives from the communications line, it may need to be absorbed rapidly to make room for more input. If the first batch of input has not been processed before the second batch arrives, data may be lost.

A second approach is to define priorities for interrupts and to allow an interrupt of higher priority to cause a lower-priority interrupt handler to be itself interrupted (Figure 3.13b). As an example of this second approach, consider a system with three I/O devices: a printer, a disk, and a communications line, with increasing priori-ties of 2, 4, and 5, respectively. Figure 3.14 illustrates a possible sequence. A user program begins at t = 0. At t = 10, a printer interrupt occurs; user information is placed on the system stack and execution continues at the printer interrupt service routine (ISR). While this routine is still executing, at t = 15, a communications inter-rupt occurs. Because the communications line has higher priority than the printer, the interrupt is honored. The printer ISR is interrupted, its state is pushed onto the stack, and execution continues at the communications ISR. While this routine is exe-cuting, a disk interrupt occurs (t = 20). Because this interrupt is of lower priority, it is simply held, and the communications ISR runs to completion.

Figure 3.12 Instruction Cycle State Diagram, with Interrupts

handler Y

(a) Sequential interrupt processing

(b) Nested interrupt processing

Figure 3.13 Transfer of Control with Multiple Interrupts

I/O Function

Thus far, we have discussed the operation of the computer as controlled by the pro-cessor, and we have looked primarily at the interaction of processor and memory. The discussion has only alluded to the role of the I/O component. This role is dis-cussed in detail in Chapter 7, but a brief summary is in order here.

3.3 interConneCtion struCtures

A computer consists of a set of components or modules of three basic types (pro-cessor, memory, I/O) that communicate with each other. In effect, a computer is a network of basic modules. Thus, there must be paths for connecting the modules.

Write

N words

100 Chapter 3 / a top-LeveL view of Computer funCtion and interConneCtion

is indicated by read and write control signals. The location for the operation is specified by an address.

■ Processor to memory: The processor writes a unit of data to memory.

■ I/O to processor: The processor reads data from an I/O device via an I/O module.

The bus was the dominant means of computer system component interconnection for decades. For general-purpose computers, it has gradually given way to various point-to-point interconnection structures, which now dominate computer system design. However, bus structures are still commonly used for embedded systems, par-ticularly microcontrollers. In this section, we give a brief overview of bus structure. Appendix C provides more detail.

A bus is a communication pathway connecting two or more devices. A key characteristic of a bus is that it is a shared transmission medium. Multiple devices connect to the bus, and a signal transmitted by any one device is available for recep-tion by all other devices attached to the bus. If two devices transmit during the same time period, their signals will overlap and become garbled. Thus, only one device at a time can successfully transmit.

A system bus consists, typically, of from about fifty to hundreds of separate lines. Each line is assigned a particular meaning or function. Although there are many different bus designs, on any bus the lines can be classified into three func-tional groups (Figure 3.16): data, address, and control lines. In addition, there may be power distribution lines that supply power to the attached modules.

The data lines provide a path for moving data among system modules. These lines, collectively, are called the data bus. The data bus may consist of 32, 64, 128, or even more separate lines, the number of lines being referred to as the width of the data bus. Because each line can carry only one bit at a time, the number of lines determines how many bits can be transferred at a time. The width of the data bus is a key factor in determining overall system performance. For example, if the data bus is 32 bits wide and each instruction is 64 bits long, then the processor must access the memory module twice during each instruction cycle.

Control lines

there must be a means of controlling their use. Control signals transmit both com-mand and timing information among system modules. Timing signals indicate the validity of data and address information. Command signals specify operations to be performed. Typical control lines include:

■ Memory write: causes data on the bus to be written into the addressed location.

■ Bus request: indicates that a module needs to gain control of the bus.

■ Bus grant: indicates that a requesting module has been granted control of the bus.

The operation of the bus is as follows. If one module wishes to send data to another, it must do two things: (1) obtain the use of the bus, and (2) transfer data via the bus. If one module wishes to request data from another module, it must (1) obtain the use of the bus, and (2) transfer a request to the other module over the appropriate control and address lines. It must then wait for that second module to send the data.

3.5 point-to-point interConneCt

3.5 / point-to-point interConneCt 103

The following are significant characteristics of QPI and other point-to-point interconnect schemes:

In addition, QPI is used to connect to an I/O module, called an I/O hub (IOH). The IOH acts as a switch directing traffic to and from I/O devices. Typically in newer

104 Chapter 3 / a top-LeveL view of Computer funCtion and interConneCtion

■ Link: Responsible for reliable transmission and flow control. The Link layer’s unit of transfer is an 80-bit Flit (flow control unit).

■ Routing: Provides the framework for directing packets through the fabric.

3.5 / point-to-point interConneCt 105

The form of transmission on each lane is known as differential signaling, or balanced transmission. With balanced transmission, signals are transmitted as a cur-rent that travels down one conductor and returns on the other. The binary value depends on the voltage difference. Typically, one line has a positive voltage value and the other line has zero voltage, and one line is associated with binary 1 and one line is associated with binary 0. Specifically, the technique used by QPI is known as low-voltage differential signaling (LVDS). In a typical implementation, the trans-mitter injects a small current into one wire or the other, depending on the logic level to be sent. The current passes through a resistor at the receiving end, and then returns in the opposite direction along the other wire. The receiver senses the polar-ity of the voltage across the resistor to determine the logic level.

Another function performed by the physical layer is that it manages the trans-lation between 80-bit flits and 20-bit phits using a technique known as multilane distribution. The flits can be considered as a bit stream that is distributed across the data lanes in a round-robin fashion (first bit to first lane, second bit to second lane, etc.), as illustrated in Figure 3.20. This approach enables QPI to achieve very high data rates by implementing the physical link between two ports as multiple parallel channels.

Figure 3.20 QPI Multilane Distribution

an 8-bit error control code called a cyclic redundancy check (CRC). We discuss error control codes in Chapter 5.

2. When a flit is received, B calculates a CRC value for the 72-bit payload and compares this value with the value of the incoming CRC value in the flit. If the two CRC values do not match, an error has been detected.

3. When B detects an error, it sends a request to A to retransmit the flit that is in error. However, because A may have had sufficient credit to send a stream of flits, so that additional flits have been transmitted after the flit in error and

QPI Protocol Layer

In this layer, the packet is defined as the unit of transfer. The packet contents definition is standardized with some flexibility allowed to meet differing market segment require-ments. One key function performed at this level is a cache coherency protocol, which deals with making sure that main memory values held in multiple caches are consistent. A typical data packet payload is a block of data being sent to or from a cache.

A key requirement for PCIe is high capacity to support the needs of higher data rate I/O devices, such as Gigabit Ethernet. Another requirement deals with the need to support time-dependent data streams. Applications such as video-on- demand and audio redistribution are putting real-time constraints on servers too. Many communications applications and embedded PC control systems also pro-cess data in real-time. Today’s platforms must also deal with multiple concurrent

■ Switch: The switch manages multiple PCIe streams.

■ PCIe endpoint: An I/O device or controller that implements PCIe, such as a Gigabit ethernet switch, a graphics or video controller, disk interface, or a communications controller.

3.6 / pCi express 109

■ Data link: Is responsible for reliable transmission and flow control. Data pack-ets generated and consumed by the DLL are called Data Link Layer Packets (DLLPs).

■ Transaction: Generates and consumes data packets used to implement load/ store data transfer mechanisms and also manages the flow control of those packets between the two components on a link. Data packets generated and consumed by the TL are called Transaction Layer Packets (TLPs).

Transaction layer

byte stream

To understand the rationale for the 128b/130b encoding, note that unlike QPI, PCIe does not use its clock line to synchronize the bit stream. That is, the clock line is not used to determine the start and end point of each incoming bit; it is used for other signaling purposes only. However, it is necessary for the receiver to be syn-chronized with the transmitter, so that the receiver knows when each bit begins and ends. If there is any drift between the clocks used for bit transmission and reception of the transmitter and receiver, errors may occur. To compensate for the possibil-ity of drift, PCIe relies on the receiver synchronizing with the transmitter based on the transmitted signal. As with QPI, PCIe uses differential signaling over a pair of wires. Synchronization can be achieved by the receiver looking for transitions in the data and synchronizing its clock to the transition. However, consider that with a long string of 1s or 0s using differential signaling, the output is a constant voltage over a long period of time. Under these circumstances, any drift between the clocks of transmitter and receiver will result in loss of synchronization between the two.

A common approach, and the one used in PCIe 3.0, to overcoming the prob-lem of a long string of bits of one value is scrambling. Scrambling, which does not increase the number of bits to be transmitted, is a mapping technique that tends to make the data appear more random. The scrambling tends to spread out the num-ber of transitions so that they appear at the receiver more uniformly spaced, which is good for synchronization. Also, other transmission properties, such as spectral properties, are enhanced if the data are more nearly of a random nature rather than constant or repetitive. For more discussion of scrambling, see Appendix E.

112 Chapter 3 / a top-LeveL view of Computer funCtion and interConneCtion

128b

The transaction layer (TL) receives read and write requests from the software above the TL and creates request packets for transmission to a destination via the link layer. Most transactions use a split transaction technique, which works in the follow-ing fashion. A request packet is sent out by a source PCIe device, which then waits for a response, called a completion packet. The completion following a request is initiated by the completer only when it has the data and/or status ready for delivery. Each packet has a unique identifier that enables completion packets to be directed to the correct originator. With the split transaction technique, the completion is sep-arated in time from the request, in contrast to a typical bus operation in which both sides of a transaction must be available to seize and use the bus. Between the request and the completion, other PCIe traffic may use the link.

TL messages and some write transactions are posted transactions, meaning that no response is expected.

■ Memory: The memory space includes system main memory. It also includes PCIe I/O devices. Certain ranges of memory addresses map into I/O devices.

■ I/O: This address space is used for legacy PCI devices, with reserved memory address ranges used to address legacy I/O devices.

tlppacketassembly PCIe transactions are conveyed using transaction layer packets, which are illustrated in Figure 3.25a. A TLP originates in the transaction layer of the sending device and terminates at the transaction layer of the receiving device.

Number

Figure 3.25 PCIe Protocol Data Unit Format

3.6 / pCi express 115

PCIe Data Link Layer

The purpose of the PCIe data link layer is to ensure reliable delivery of packets across the PCIe link. The DLL participates in the formation of TLPs and also trans-mits DLLPs.

2. If an error is detected, the DLL schedules an NAK DLL packet to return back to the remote transmitter. The TLP is eliminated.

When the DLL transmits a TLP, it retains a copy of the TLP. If it receives an NAK for the TLP with this sequence number, it retransmits the TLP. When it receives an ACK, it discards the buffered TLP.

2. Add contents of memory location 940.

3. Store AC to device 6.

118 Chapter 3 / a top-LeveL view of Computer funCtion and interConneCtion

cycle, any agent can request control of the bus by lowering its BPRO line. This lowers the BPRN line of the next agent in the chain, which is in turn required to lower its BPRO line. Thus, the signal is propagated the length of the chain. At the end of this chain reaction, there should be only one agent whose BPRN is asserted and whose BPRO is not. This agent has priority. If, at the beginning of a bus cycle, the bus is not busy (BUSY inactive), the agent that has priority may seize control of the bus by asserting the BUSY line.

It takes a certain amount of time for the BPR signal to propagate from the highest-priority agent to the lowest. Must this time be less than the clock cycle? Explain.

4.1 Computer Memory System Overview Characteristics of Memory Systems The Memory Hierarchy

4.2 Cache Memory Principles

120

4.1 / Computer memory SyStem overview 121

4.1 COMPUTER MEMORY SYSTEM OVERVIEW

Characteristics of Memory Systems

Table 4.1 Key Characteristics of Computer Memory Systems

Another distinction among memory types is the method of accessing units of data. These include the following:

■ Sequential access: Memory is organized into units of data, called records. Access must be made in a specific linear sequence. Stored addressing infor-mation is used to separate records and assist in the retrieval process. A shared read– write mechanism is used, and this must be moved from its current loca-tion to the desired location, passing and rejecting each intermediate record. Thus, the time to access an arbitrary record is highly variable. Tape units, dis-cussed in Chapter 6, are sequential access.

■ Associative: This is a random access type of memory that enables one to make a comparison of desired bit locations within a word for a specified match, and to do this for all words simultaneously. Thus, a word is retrieved based on a portion of its contents rather than its address. As with ordinary random- access memory, each location has its own addressing mechanism, and retrieval time is constant independent of location or prior access patterns. Cache memories may employ associative access.

From a user’s point of view, the two most important characteristics of memory are capacity and performance. Three performance parameters are used:

Tn = Average time to read or writenbits

TA = Average access time

Several physical characteristics of data storage are important. In a volatile memory, information decays naturally or is lost when electrical power is switched off. In a nonvolatile memory, information once recorded remains without deterio-ration until deliberately changed; no electrical power is needed to retain informa-tion. Magnetic- surface memories are nonvolatile. Semiconductor memory (memory on integrated circuits) may be either volatile or nonvolatile. Nonerasable memory cannot be altered, except by destroying the storage unit. Semiconductor memory of this type is known as read- only memory (ROM). Of necessity, a practical nonerasa-ble memory must also be nonvolatile.

For random- access memory, the organization is a key design issue. In this con-text, organization refers to the physical arrangement of bits to form words. The obvious arrangement is not always used, as is explained in Chapter 5.

■ Faster access time, greater cost per bit;

■ Greater capacity, smaller cost per bit;

b. Increasing capacity;

c. Increasing access time;

Figure 4.1 The Memory Hierarchy

is item (d): decreasing frequency of access. We examine this concept in greater detail when we discuss the cache, later in this chapter, and virtual memory in Chapter 8. A brief explanation is provided at this point.

memory contain all program instructions and data. The current clusters can be tem-porarily placed in level 1. From time to time, one of the clusters in level 1 will have to be swapped back to level 2 to make room for a new cluster coming in to level 1. On average, however, most references will be to instructions and data contained in level 1.

This principle can be applied across more than two levels of memory, as sug-gested by the hierarchy shown in Figure 4.1. The fastest, smallest, and most expen-sive type of memory consists of the registers internal to the processor. Typically, a processor will contain a few dozen such registers, although some machines contain hundreds of registers. Main memory is the principal internal memory system of the computer. Each location in main memory has a unique address. Main memory is usu-ally extended with a higher- speed, smaller cache. The cache is not usually visible to the programmer or, indeed, to the processor. It is a device for staging the movement of data between main memory and processor registers to improve performance.

Appendix 4A examines the performance implications of multilevel memory structures.

2 Disk cache is generally a purely software technique and is not examined in this book. See [STAL15] for a discussion.

Figure 4.3b depicts the use of multiple levels of cache. The L2 cache is slower and typically larger than the L1 cache, and the L3 cache is slower and typically larger than the L2 cache.

Figure 4.4 depicts the structure of a cache/ main- memory system. Main mem-ory consists of up to 2n addressable words, with each word having a unique n- bit address. For mapping purposes, this memory is considered to consist of a number of fixed- length blocks of K words each. That is, there are M = 2n/K blocks in main memory. The cache consists of m blocks, called lines.3 Each line contains K words,

(b) Three-level cache organization

Figure 4.4 Cache/Main Memory Structure

plus a tag of a few bits. Each line also includes control bits (not shown), such as a bit to indicate whether the line has been modified since being loaded into the cache. The length of a line, not including tag and control bits, is the line size. The line size may be as small as 32 bits, with each “word” being a single byte; in this case the line size is 4 bytes. The number of lines is considerably less than the number of main memory blocks (m V M). At any time, some subset of the blocks of mem-ory resides in lines in the cache. If a word in a block of memory is read, that block is transferred to one of the lines of the cache. Because there are more blocks than lines, an individual line cannot be uniquely and permanently dedicated to a par-ticular block. Thus, each line includes a tag that identifies which particular block is currently being stored. The tag is usually a portion of the main memory address, as described later in this section.

Receive address
RA from CPU

which main memory is reached. When a cache hit occurs, the data and address buff-ers are disabled and communication is only between processor and cache, with no system bus traffic. When a cache miss occurs, the desired address is loaded onto the system bus and the data are returned through the data buffer to both the cache and the processor. In other organizations, the cache is physically interposed between the processor and the main memory for all data, address, and control lines. In this latter case, for a cache miss, the desired word is first read into the cache and then transferred from cache to processor.

A discussion of the performance parameters related to cache use is contained in Appendix 4A.

Data
buffer

Data

Almost all nonembedded processors, and many embedded processors, support vir-tual memory, a concept discussed in Chapter 8. In essence, virtual memory is a facil-ity that allows programs to address memory from a logical point of view, without regard to the amount of main memory physically available. When virtual memory is used, the address fields of machine instructions contain virtual addresses. For reads

4For a general discussion of HPC, see [DOWD98].

to and writes from main memory, a hardware memory management unit (MMU) translates each virtual address into a physical address in main memory.

When virtual addresses are used, the system designer may choose to place the cache between the processor and the MMU or between the MMU and main mem-ory (Figure 4.7). A logical cache, also known as a virtual cache, stores data using

Data

(b) Physical cache

The subject of logical versus physical cache is a complex one, and beyond the scope of this book. For a more in- depth discussion, see [CEKL97] and [JACO08].

Cache Size

Table 4.3 Cache Sizes of Some Processors

i = cache line number

j = main memory block number

B0	b			m lines
Bm–1			Lm–1
	First m blocks of	Cache memory

main memory

b = length of block in bits
t = length of tag in bits

(a) Direct mapping

Figure 4.8 Mapping from Main Memory to Cache: Direct and Associative

of main memory map into the cache in the same fashion; that is, block Bm of main memory maps into line L0 of cache, block Bm+1 maps into line L1, and so on.

4.3 / elementS of CACHe DeSign 137 Main memory address (binary)

The direct mapping technique is simple and inexpensive to implement. Its main disadvantage is that there is a fixed cache location for any given block. Thus, if a program happens to reference words repeatedly from two different blocks that map into the same line, then the blocks will be continually swapped in the cache,

Note that no field in the address corresponds to the line number, so that the number of lines in the cache is not determined by the address format. To summarize,

■ Address length = (s + w) bits
■ Number of addressable units = 2s+w words or bytes■ Block size = line size = 2w words or bytes
■ Number of blocks in main memory =2s+w 2w = 2s

set- associativemapping Set- associative mapping is a compromise that exhibits the strengths of both the direct and associative approaches while reducing their disadvantages.

In this case, the cache consists of number sets, each of which consists of a num-ber of lines. The relationships are

j = main memory block number

m = number of lines in the cache

4.3 / elementS of CACHe DeSign 141

Cache memory–set v–1

(a) v associative–mapped caches

For set- associative mapping, the cache control logic interprets a memory address as three fields: Tag, Set, and Word. The d set bits specify one of v = 2d sets. The s bits of the Tag and Set fields specify one of the 2s blocks of main memory. Figure 4.14 illustrates the cache control logic. With fully associative mapping, the tag in a memory address is quite large and must be compared to the tag of every line in the cache. With k- way set- associative mapping, the tag in a memory address is much smaller and is only compared to the k tags within a single set. To summarize,

■ Address length = (s + w) bits
■ Number of addressable units = 2s+w words or bytes

0 if no match

■ Block size = line size = 2w words or bytes

■ Number of blocks in main memory =2s+w 2w = 2s

In the extreme case of v = m,k = 1, the set- associative technique reduces to direct mapping, and for v = 1,k = m, it reduces to associative mapping. The use of two lines per set (v = m/2,k = 2) is the most common set- associative organization. It significantly improves the hit ratio over direct mapping. Four- way set associative (v = m/4,k = 4) makes a modest additional improvement for a relatively small additional cost [MAYB84, HILL89]. Further increases in the number of lines per set have little effect.

Figure 4.16 shows the results of one simulation study of set- associative cache performance as a function of cache size [GENU04]. The difference in performance between direct and two- way set associative is significant up to at least a cache size of 64 kB. Note also that the difference between two- way and four- way at 4 kB is much less than the difference in going from for 4 kB to 8 kB in cache size. The complexity of the cache increases in proportion to the associativity, and in this case would not be justifiable against increasing cache size to 8 or even 16 kB. A final point to note is that beyond about 32 kB, increase in cache size brings no significant increase in performance.

Replacement Algorithms

Once the cache has been filled, when a new block is brought into the cache, one of the existing blocks must be replaced. For direct mapping, there is only one possible line for any particular block, and no choice is possible. For the associative and set- associative techniques, a replacement algorithm is needed. To achieve high speed, such an algorithm must be implemented in hardware. A number of algorithms have been tried. We mention four of the most common. Probably the most effective is least recently used (LRU): Replace that block in the set that has been in the cache longest with no reference to it. For two- way set associative, this is easily implemented. Each line includes a USE bit. When a line is referenced, its USE bit is set to 1 and the USE bit of the other line in that set is set to 0. When a block is to be read into the set, the line whose USE bit is 0 is used. Because we are assuming that more recently used memory locations are more likely to be referenced, LRU should give the best hit ratio. LRU is also relatively easy to implement for a fully associative cache. The cache mechanism maintains a separate list of indexes to all the lines in the cache. When a line is referenced, it moves to the front of the list. For replacement, the line at the back of the list is used. Because of its simplicity of implementation, LRU is the most popular replacement algorithm.

146 CHApter 4 / CACHe memory

of this technique is that it generates substantial memory traffic and may create a bot-tleneck. An alternative technique, known as write back, minimizes memory writes. With write back, updates are made only in the cache. When an update occurs, a dirty bit, or use bit, associated with the line is set. Then, when a block is replaced, it is written back to main memory if and only if the dirty bit is set. The problem with write back is that portions of main memory are invalid, and hence accesses by I/O modules can be allowed only through the cache. This makes for complex circuitry and a potential bottleneck. Experience has shown that the percentage of memory references that are writes is on the order of 15% [SMIT82]. However, for HPC applications, this number may approach 33% ( vector- vector multiplication) and can go as high as 50% (matrix transposition).

■ Larger blocks reduce the number of blocks that fit into a cache. Because each block fetch overwrites older cache contents, a small number of blocks results in data being overwritten shortly after they are fetched.

■ As a block becomes larger, each additional word is farther from the requested word and therefore less likely to be needed in the near future.

The inclusion of an on- chip cache leaves open the question of whether an off- chip, or external, cache is still desirable. Typically, the answer is yes, and most contemporary designs include both on- chip and external caches. The simplest such organization is known as a two- level cache, with the internal level 1 (L1) and the external cache designated as level 2 (L2). The reason for including an L2 cache is the following: If there is no L2 cache and the processor makes an access request for a memory location not in the L1 cache, then the processor must access DRAM or

Figure 4.17 shows the results of one simulation study of two- level cache perfor-mance as a function of cache size [GENU04]. The figure assumes that both caches have the same line size and shows the total hit ratio. That is, a hit is counted if the desired data appears in either the L1 or the L2 cache. The figure shows the impact of L2 on total hits with respect to L1 size. L2 has little effect on the total number of cache hits until it is at least double the L1 cache size. Note that the steepest part of the slope for an L1 cache of 8 kB is for an L2 cache of 16 kB. Again for an L1 cache of 16 kB, the steepest part of the curve is for an L2 cache size of 32 kB. Prior to that point, the L2 cache has little, if any, impact on total cache performance. The need for the L2 cache to be larger than

0.98

L2 cache size (bytes)

unifiedversussplitcaches When the on- chip cache first made an appearance, many of the designs consisted of a single cache used to store references to both data and instructions. More recently, it has become common to split the cache into two: one dedicated to instructions and one dedicated to data. These two caches both exist at the same level, typically as two L1 caches. When the processor attempts to fetch an instruction from main memory, it first consults the instruction L1 cache, and when the processor attempts to fetch data from main memory, it first consults the data L1 cache.

There are two potential advantages of a unified cache:

The evolution of cache organization is seen clearly in the evolution of Intel micro-processors (Table 4.4). The 80386 does not include an on- chip cache. The 80486 includes a single on- chip cache of 8 kB, using a line size of 16 bytes and a four- way

150 CHApter 4 / CACHe memory

set- associative organization. All of the Pentium processors include two on- chip L1 caches, one for data and one for instructions. For the Pentium 4, the L1 data cache is 16 kB, using a line size of 64 bytes and a four- way set- associative organi-zation. The Pentium 4 instruction cache is described subsequently. The Pentium II also includes an L2 cache that feeds both of the L1 caches. The L2 cache is eight- way set associative with a size of 512 kB and a line size of 128 bytes. An L3 cache was added for the Pentium III and became on- chip with high- end versions of the Pentium 4.

System bus

L2 cache
(512 kB)

bits

Note: CD = 0; NW = 1 is an invalid combination.

The L1 data cache is controlled by two bits in one of the control registers, labe-led the CD (cache disable) and NW (not write- through) bits (Table 4.5). There are also two Pentium 4 instructions that can be used to control the data cache: INVD invalidates (flushes) the internal cache memory and signals the external cache (if any) to invalidate. WBINVD writes back and invalidates internal cache and then writes back and invalidates external cache.

Both the L2 and L3 caches are eight- way set- associative with a line size of 128 bytes.

4.5 / Key termS, review QueStionS, AnD problemS 153

154 CHApter 4 / CACHe memory

c. For the two- way set- associative cache example of Figure 4.15: address length, num-ber of addressable units, block size, number of blocks in main memory, number of lines in set, number of sets, number of lines in cache, size of tag

Figure 4.19 Intel 80486 On- Chip Cache Replacement Strategy

for (j = 0; j 6 10; j+ +)

a[i] = a[i]*j

order. It then repeats this fetch sequence nine more times. The cache is 10 times faster than main memory. Estimate the improvement resulting from the use of the cache. Assume an LRU policy for block replacement.

b. Repeat the calculations assuming insertion of two wait states of one cycle each per memory cycle. What conclusion can you draw from the results?

Ta = Tc + (1- H)Tm

The basis for the performance advantage of a two- level memory is a principle known as locality of reference [DENN68]. This principle states that memory references tend to cluster. Over a long period of time, the clusters in use change, but over a short period of time, the processor is primarily working with fixed clusters of mem-ory references.

Intuitively, the principle of locality makes sense. Consider the following line of reasoning:

Table 4.6 Characteristics of Two- Level Memories

A distinction is made in the literature between spatial locality and temporal locality. Spatial locality refers to the tendency of execution to involve a number of memory locations that are clustered. This reflects the tendency of a processor to access instructions sequentially. Spatial location also reflects the tendency of a pro-gram to access data locations sequentially, such as when processing a table of data. Temporal locality refers to the tendency for a processor to access memory locations that have been used recently. For example, when an iteration loop is executed, the processor executes the same set of instructions repeatedly.

w= 5
Call

Nesting
depth

To express the average time to access an item, we must consider not only the speeds of the two levels of memory, but also the probability that a given reference can be found in M1. We have

Figure 4.2 shows average access time as a function of hit ratio. As can be seen, for a high percentage of hits, the average total access time is much closer to that of M1 than M2.

Performance

We would like Cs ≈ C2. Given that C1 W C2, this requires S1 6 S2. Figure 4.21 shows the relationship.

Relative size of two levels (S2/S1)

Figure 4.21 Relationship of Average Memory Cost to Relative Memory Size for a Two- Level Memory

So we would like M1 to be small to hold down cost, and large to improve the hit ratio and therefore the performance. Is there a size of M1 that satisfies both requirements to a reasonable extent? We can answer this question with a series of subquestions:

■ What value of hit ratio is needed so that Ts ≈ T1?■ What size of M1 will assure the needed hit ratio?

1

r= 1

Hit ratio =H

Figure 4.22 Access Efficiency as a Function of Hit Ratio (r = T2/T1)

So if there is strong locality, it is possible to achieve high values of hit ratio even with relatively small upper- level memory size. For example, numerous studies have shown that rather small cache sizes will yield a hit ratio above 0.75 regardless of the size of main memory (e.g., [AGAR89], [PRZY88], [STRE83], and [SMIT82]). A cache in the range of 1K to 128K words is generally adequate, whereas main

1.0

0.4
No locality

164 CHApter 4 / CACHe memory

memory is now typically in the gigabyte range. When we consider virtual memory and disk cache, we will cite other studies that confirm the same phenomenon, namely that a relatively small M1 yields a high value of hit ratio because of locality.

Internal MeMory

5.1 Semiconductor Main Memory
Organization
DRAM and SRAM
Types of ROM
Chip Logic
Chip Packaging
Module Organization
Interleaved Memory

5.6 Key Terms, Review Questions, and Problems

165

Organization

The basic element of a semiconductor memory is the memory cell. Although a vari-ety of electronic technologies are used, all semiconductor memory cells share certain properties:

5.1 / SeMIConduCtor MaIn MeMory 167

All of the memory types that we will explore in this chapter are random access. That is, individual words of memory are directly accessed through wired-in addressing logic.

Table 5.1 lists the major types of semiconductor memory. The most common is referred to as random-access memory (RAM). This is, in fact, a misuse of the term, because all of the types listed in the table are random access. One distinguishing characteristic of memory that is designated as RAM is that it is possible both to read data from the memory and to write new data into the memory easily and rapidly. Both the reading and writing are accomplished through the use of electrical signals.

168 Chapter 5 / Internal MeMory

dynamic refers to this tendency of the stored charge to leak away, even with power continuously applied.

staticram In contrast, a static RAM (SRAM) is a digital device that uses the same logic elements used in the processor. In a SRAM, binary values are stored using traditional flip-flop logic-gate configurations (see Chapter 11 for a description of flip-flops). A static RAM will hold its data as long as power is supplied to it.

Figure 5.2b is a typical SRAM structure for an individual cell. Four transistors (T1,T2,T3,T4) are cross connected in an arrangement that produces a stable logic

Storage
capacitor

Figure 5.2 Typical Memory Cell Structures

5.1 / SeMIConduCtor MaIn MeMory 169

As the name suggests, a read-only memory (ROM) contains a permanent pattern of data that cannot be changed. A ROM is nonvolatile; that is, no power source is required to maintain the bit values in memory. While it is possible to read a ROM, it is not possible to write new data into it. An important application of ROMs is micro-programming, discussed in Part Four. Other potential applications include

■ Library subroutines for frequently wanted functions

■ The data insertion step includes a relatively large fixed cost, whether one or thousands of copies of a particular ROM are fabricated.

■ There is no room for error. If one bit is wrong, the whole batch of ROMs must be thrown out.

Another variation on read-only memory is the read-mostly memory, which is useful for applications in which read operations are far more frequent than write operations but for which nonvolatile storage is required. There are three common forms of read-mostly memory: EPROM, EEPROM, and flash memory.

The optically erasable programmable read-only memory (EPROM) is read and written electrically, as with PROM. However, before a write operation, all the stor-age cells must be erased to the same initial state by exposure of the packaged chip to ultraviolet radiation. Erasure is performed by shining an intense ultraviolet light through a window that is designed into the memory chip. This erasure process can be performed repeatedly; each erasure can take as much as 20 minutes to perform. Thus, the EPROM can be altered multiple times and, like the ROM and PROM, holds its data virtually indefinitely. For comparable amounts of storage, the EPROM is more expensive than PROM, but it has the advantage of the multiple update capability.

In the memory hierarchy as a whole, we saw that there are trade-offs among speed, density, and cost. These trade-offs also exist when we consider the organiza-tion of memory cells and functional logic on a chip. For semiconductor memories, one of the key design issues is the number of bits of data that may be read/written at a time. At one extreme is an organization in which the physical arrangement of cells in the array is the same as the logical arrangement (as perceived by the pro-cessor) of words in memory. The array is organized into W words of B bits each.

An additional 11 address lines select one of 2048 columns of 4 bits per column. Four data lines are used for the input and output of 4 bits to and from a data buffer. On input (write), the bit driver of each bit line is activated for a 1 or 0 according to the value of the corresponding data line. On output (read), the value of each bit line is passed through a sense amplifier and presented to the data lines. The row line selects which row of cells is used for reading or writing.

RAS CAS WE OE

172 Chapter 5 / Internal MeMory

Because only 4 bits are read/written to this DRAM, there must be multiple DRAMs connected to the memory controller to read/write a word of data to the bus.

Chip Packaging

As was mentioned in Chapter 2, an integrated circuit is mounted on a package that contains pins for connection to the outside world.

■ A ground pin (Vss).

■ A chip enable (CE) pin. Because there may be more than one memory chip, each of which is connected to the same address bus, the CE pin is used to indi-cate whether or not the address is valid for this chip. The CE pin is activated by logic connected to the higher-order bits of the address bus (i.e., address bits above A19). The use of this signal is illustrated presently.

Figure 5.4 Typical Memory Package Pins and Signals

Because the DRAM is accessed by row and column, and the address is multi-plexed, only 11 address pins are needed to specify the 4M row/column combinations (211* 211= 222= 4M). The functions of the row address select (RAS) and col-umn address select (CAS) pins were discussed previously. Finally, the no connect (NC) pin is provided so that there are an even number of pins.

Main memory is composed of a collection of DRAM memory chips. A number of chips can be grouped together to form a memory bank. It is possible to organize the memory

8

Decode 1 of
512 bit-sense

5.2 error correction

A semiconductor memory system is subject to errors. These can be categorized as hard failures and soft errors. A hard failure is a permanent physical defect so that the memory cell or cells affected cannot reliably store data but become stuck at 0 or 1 or

Figure 5.7 illustrates in general terms how the process is carried out. When data are to be written into memory, a calculation, depicted as a function f, is per-formed on the data to produce a code. Both the code and the data are stored. Thus, if an M-bit word of data is to be stored and the code is of length K bits, then the actual size of the stored word is M + K bits.

When the previously stored word is read out, the code is used to detect and possibly correct errors. A new set of K code bits is generated from the M data bits and compared with the fetched code bits. The comparison yields one of three results:

176 Chapter 5 / Internal MeMory

f

Figure 5.7 Error-Correcting Code Function

2K-1 Ú M + K

This inequality gives the number of bits needed to correct a single bit error in a word containing M data bits. For example, for a word of 8 data bits (M = 8), we have

Figure 5.8 Hamming Error-Correcting Code

Thus, eight data bits require four check bits. The first three columns of Table 5.2 lists the number of check bits required for various data word lengths.

To achieve these characteristics, the data and check bits are arranged into a 12-bit word as depicted in Figure 5.9. The bit positions are numbered from 1 to 12. Those bit positions whose position numbers are powers of 2 are designated as check

178 Chapter 5 / Internal MeMory

Each check bit operates on every data bit whose position number contains a 1 in the same bit position as the position number of that check bit. Thus, data bit pos-itions 3, 5, 7, 9, and 11 (D1, D2, D4, D5, D7) all contain a 1 in the least significant bit of their position number as does C1; bit positions 3, 6, 7, 10, and 11 all contain a 1 in is checked by those bits Ci such that a i = n. For example, position 7 is checked by bits in position 4, 2, and 1; and 7 = 4 + 2 + 1.

Let us verify that this scheme works with an example. Assume that the 8-bit input word is 00111001, with data bit D1 in the rightmost position. The calculations are as follows:

Figure 5.9 Layout of Data Bits and Check Bits

C4 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0

C8 = 1 ⊕ 1 ⊕ 0 ⊕ 0 = 0

The code just described is known as a single-error-correcting (SEC) code. More commonly, semiconductor memory is equipped with a single-error-correcting, double-error-detecting (SEC-DED) code. As Table 5.2 shows, such codes require one additional bit compared with SEC codes.

Figure 5.11 illustrates how such a code works, again with a 4-bit data word. The sequence shows that if two errors occur (Figure 5.11c), the checking procedure goes astray (d) and worsens the problem by creating a third error (e). To overcome

180 Chapter 5 / Internal MeMory

Figure 5.11 Hamming SEC-DEC Code

the problem, an eighth bit is added that is set so that the total number of 1s in the diagram is even. The extra parity bit catches the error (f).

In recent years, a number of enhancements to the basic DRAM architecture have been explored. The schemes that currently dominate the market are SDRAM and DDR-DRAM. We examine each of these in turn.

With synchronous access, the DRAM moves data in and out under control of the system clock. The processor or other master issues the instruction and address information, which is latched by the DRAM. The DRAM then responds after a set number of clock cycles. Meanwhile, the master can safely do other tasks while the SDRAM is processing the request.

Figure 5.12 shows the internal logic of a typical 256-Mb SDRAM typical of SDRAM organization, and Table 5.3 defines the various pin assignments. The

BA0

Figure 5.12 256-Mb Synchronous Dynamic RAM (SDRAM)

The mode register and associated control logic is another key feature differen-tiating SDRAMs from conventional DRAMs. It provides a mechanism to custom-ize the SDRAM to suit specific system needs. The mode register specifies the burst length, which is the number of separate units of data synchronously fed onto the bus. The register also allows the programmer to adjust the latency between receipt of a read request and the beginning of data transfer.

The SDRAM performs best when it is transferring large blocks of data sequen-tially, such as for applications like word processing, spreadsheets, and multimedia.

Although SDRAM is a significant improvement on asynchronous RAM, it still has shortcomings that unnecessarily limit that I/O data rate that can be achieved. To address these shortcomings a newer version of SDRAM, referred to as double- data-rate DRAM (DDR DRAM) provides several features that dramatically increase the data rate. DDR DRAM was developed by the JEDEC Solid State Tech-nology Association, the Electronic Industries Alliance’s semiconductor-engineering- standardization body. Numerous companies make DDR chips, which are widely used in desktop computers and servers.

DDR achieves higher data rates in three ways. First, the data transfer is syn-chronized to both the rising and falling edge of the clock, rather than just the rising edge. This doubles the data rate; hence the term double data rate. Second, DDR uses higher clock rate on the bus to increase the transfer rate. Third, a buffering scheme is used, as explained subsequently.

100–150 Mbps

Memory array (100–266 MHz)

Figure 5.14 shows a configuration with two bank groups. With DDR4, up to 4 bank groups can be used.

Operation

Figure 5.15 illustrates the basic operation of a flash memory. For comparison, Fig-ure 5.15a depicts the operation of a transistor. Transistors exploit the properties of semiconductors so that a small voltage applied to the gate can be used to control the flow of a large current between the source and the drain.

Figure 5.15 Flash Memory Operation

Although the specific quantitative values of various characteristics of NOR and NAND are changing year by year, the relative differences between the two types has remained stable. These differences are usefully illustrated by the Kiviat graphs3 shown in Figure 5.17.

Bit line

Bit line

(b) NAND fash structure

Figure 5.16 Flash Memory Structures

5.5 newer nonvolatile Solid-State memory technologieS

The traditional memory hierarchy has consisted of three levels (Figure 5.18):

188 Chapter 5 / Internal MeMory

Increasing performance
and endurance

ReRAM

HARD DISK

Recently, there have been breakthroughs in developing new forms of non-volatile semiconductor memory that continue scaling beyond flash memory. The most promising technologies are spin-transfer torque RAM (STT-RAM), phase-change RAM (PCRAM), and resistive RAM (ReRAM) ([ITRS14], [GOER12]). All of these are in volume production. However, because NAND Flash and to some extent NOR Flash are still dominating the applications, these emerging memories have been used in specialty applications and have not yet fulfilled their original promise to become dominating mainstream high-density nonvolatile memory. This is likely to change in the next few years.

Figure 5.18 shows how these three technologies are likely to fit into the mem-ory hierarchy.

Phase-change RAM (pcram) is the most mature or the new technologies, with an extensive technical literature ([RAOU09], [ZHOU09], [LEE10]).

PCRAM technology is based on a chalcogenide alloy material, which is similar to those commonly used in optical storage media (compact discs and digital versa-tile discs). The data storage capability is achieved from the resistance differences between an amorphous (high-resistance) and a crystalline (low-resistance) phase of the chalcogenide-based material. In SET operation, the phase change material is crystallized by applying an electrical pulse that heats a significant portion of the cell above its crystallization temperature. In RESET operation, a larger electrical current is applied and then abruptly cut off in order to melt and then quench the material, leaving it in the amorphous state. Figure 5.19b illustrates the general configuration.

190 Chapter 5 / Internal MeMory

(a) STT-RAM

Review Questions

5.6 / Key terMS, revIew QueStIonS, and probleMS 193

(b) Truth table

A0
A1
A2
A3
CS

CHAPTER

6.4 Optical Memory
Compact Disk
Digital Versatile Disk
High- Definition Optical Disks

6.5 Magnetic Tape

This chapter examines a range of external memory devices and systems. We begin with the most important device, the magnetic disk. Magnetic disks are the founda-tion of external memory on virtually all computer systems. The next section exam-ines the use of disk arrays to achieve greater performance, looking specifically at the family of systems known as RAID (Redundant Array of Independent Disks). An increasingly important component of many computer systems is the solid state disk, which is discussed next. Then, external optical memory is examined. Finally, magnetic tape is described.

6.1 MAGNETIC DISK

■ Better stiffness to reduce disk dynamics.

■ Greater ability to withstand shock and damage.

196 cHaPteR 6 / exteRnal MeMoRy

Read
current

Recording
medium

Figure 6.1 Inductive Write/Magnetoresistive Read Head

The head is a relatively small device capable of reading from or writing to a portion of the platter rotating beneath it. This gives rise to the organization of data on the platter in a concentric set of rings, called tracks. Each track is the same width as the head. There are thousands of tracks per surface.

Inter-sector gap

Track sector

Figure 6.2 Disk Data Layout

Track

Figure 6.3 Comparison of Disk Layout Methods

Table 6.1 lists the major characteristics that differentiate among the various types of magnetic disks. First, the head may either be fixed or movable with respect to the radial direction of the platter. In a fixed- head disk, there is one read- write head per track. All of the heads are mounted on a rigid arm that extends across all tracks; such systems are rare today. In a movable- head disk, there is only one read- write head. Again, the head is mounted on an arm. Because the head must be able to be positioned above any track, the arm can be extended or retracted for this purpose.

The disk itself is mounted in a disk drive, which consists of the arm, a spindle that rotates the disk, and the electronics needed for input and output of binary data. A nonremovable disk is permanently mounted in the disk drive; the hard disk in a personal computer is a nonremovable disk. A removable disk can be removed and replaced with another disk. The advantage of the latter type is that unlimited amounts of data are available with a limited number of disk systems. Furthermore, such a disk may be moved from one computer system to another. Floppy disks and ZIP cartridge disks are examples of removable disks.

600 bytes/sector

Figure 6.4 Winchester Disk Format (Seagate ST506)

200 cHaPteR 6 / exteRnal MeMoRy

For most disks, the magnetizable coating is applied to both sides of the plat-ter, which is then referred to as double sided. Some less expensive disk systems use single- sided disks.

Some disk drives accommodate multiple platters stacked vertically a fraction of an inch apart. Multiple arms are provided (Figure 6.2). Multiple– platter disks employ a movable head, with one read- write head per platter surface. All of the heads are mechanically fixed so that all are at the same distance from the center of the disk and move together. Thus, at any time, all of the heads are positioned over tracks that are of equal distance from the center of the disk. The set of all the tracks in the same relative position on the platter is referred to as a cylinder. This is illus-trated in Figure 6.2.

Table 6.2 Typical Hard Disk Drive Parameters

The actual details of disk I/O operation depend on the computer system, the oper-ating system, and the nature of the I/O channel and disk controller hardware. A general timing diagram of disk I/O transfer is shown in Figure 6.5.

When the disk drive is operating, the disk is rotating at constant speed. To read or write, the head must be positioned at the desired track and at the beginning of the desired sector on that track. Track selection involves moving the head in a movable- head system or electronically selecting one head on a fixed- head system. On a movable- head system, the time it takes to position the head at the track is known as seek time. In either case, once the track is selected, the disk controller waits until the appropriate sector rotates to line up with the head. The time it takes for the beginning of the sector to reach the head is known as rotational delay, or rotational latency. The sum of the seek time, if any, and the rotational delay equals the access time, which is the time it takes to get into position to read or write. Once the head is in position, the read or write operation is then performed as the sector moves under the head; this is the data transfer portion of the operation; the time required for the transfer is the transfer time.

In some high- end systems for servers, a technique known as rotational pos-itional sensing (RPS) is used. This works as follows: When the seek command has been issued, the channel is released to handle other I/O operations. When the seek is completed, the device determines when the data will rotate under the head. As that sector approaches the head, the device tries to reestablish the communication path back to the host. If either the control unit or the channel is busy with another I/O, then the reconnection attempt fails and the device must rotate one whole revolution before it can attempt to reconnect, which is called an RPS miss. This is an extra delay element that must be added to the timeline of Figure 6.5.

seektime Seek time is the time required to move the disk arm to the required track. It turns out that this is a difficult quantity to pin down. The seek time consists of two key components: the initial startup time, and the time taken to traverse the tracks that have to be crossed once the access arm is up to speed. Unfortunately, the traversal time is not a linear function of the number of tracks, but includes a settling time (time after positioning the head over the target track until track identification is confirmed).

T = transfertime
b = numberof bytes to be transferred
N = numberof bytes on a track
r = rotationspeed, in revolutions per second

Thus the total average read or write time Ttotal can be expressed as

atimingcomparison With the foregoing parameters defined, let us look at two different I/O operations that illustrate the danger of relying on average values. Consider a disk with an advertised average seek time of 4 ms, rotation speed of 15,000 rpm, and 512-byte sectors with 500 sectors per track. Suppose that we wish to read a file consisting of 2500 sectors for a total of 1.28 Mbytes. We would like to estimate the total time for the transfer.

First, let us assume that the file is stored as compactly as possible on the disk. That is, the file occupies all of the sectors on 5 adjacent tracks (5tracks * 500sectors/track = 2500sectors). This is known as sequential organ-ization. Now, the time to read the first track is as follows: