THE HARDWARE/SOFTWARE INTERFACE
`
`COMPUTER
`ORGANIZATION
`AND DESIGN
`
`Red eeN L. HENNESSY
`
`a/ ES
`
`DAVID A. PATTERSON
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 1
`
`

`

`ACKNOWLEDGEMENTS
`
`Figures 1.9, 1.15 Courtesy ofIntel.
`
`Computersin the Real World:
`
`Figure 1.11 Courtesy of Storage Technology Corp.
`
`Photoof “A Laotianvillager,” courtesy of David Sanger.
`
`Figures 1.7.1, 1.7.2, 6.13.2 Courtesy of the Charles BabbageInstitute,
`University of Minnesota Libraries, Minneapolis.
`
`Figures 1.7.3, 6.13.1, 6.13.3, 7.9.3, 8.11.2 Courtesy of IBM.
`
`Figure 1.7.4 Courtesy ofCray Inc.
`
`Figure 1.7.5 Courtesy of Apple Computer, Inc.
`
`Figure 1.7.6 Courtesy of the Computer History Museum.
`
`Figure 7.33 Courtesy of AMD.
`
`Photoof an “Indianvillager,” property of Encore Software, Ltd., India.
`
`Photos of “Block and students” and “a pop-up archival satellite tag,”
`courtesy of Professor Barbara Block. Photos by Scott Taylor.
`
`Photos of “Professor Dawson and student” and “the Mica micromote,”
`courtesy of AP/World Wide Photos.
`
`Photos of “images of pottery fragments” and “a computer reconstruc-
`tion,” courtesy of Andrew Willis and David B. Cooper, Brown University,
`Division of Engineering.
`
`Figures 7.9.1, 7.9.2 Courtesy of MuseumofScience, Boston.
`
`Photo of“the Eurostar TGV train,” by Jos van der Kolk.
`
`Figure 7.9.4 Courtesy of MIPS Technologies, Inc.
`
`Photoof“the interior of a Eurostar TGVcab,” by AndyVeitch.
`
`Figure 8.3 © Peg Skorpinski.
`
`Photo of“firefighter Ken Whitten,” courtesy of World Economic Forum.
`
`Figure 8.11.1 Courtesy of the Computer Museum of America.
`
`Figure 8.11.3 Courtesy of the Commercial Computing Museum.
`
`Figures 9.11.2, 9.11.3 Courtesy of NASA Ames Research Center.
`
`Figure 9.11.4 Courtesy of Lawrence Livermore National Laboratory.
`
`Graphic of an “artificial
`Reprinted by permission.
`
`retina,’ © The San Francisco Chronicle.
`
`Image of “A laser scan of Michelangelo’s statue of David,” courtesy of
`Marc Levoy and Dr. Franca Falletti, director of the Galleria dell'Acca-
`demia, Italy.
`
`IR image
`“An image from the Sistine Chapel,” courtesy of Luca Pezzati.
`recorded using the scannerfor IR reflectography of the INOA (National
`Institute for Applied Optics, http://arte.ino.it) at the Opificio delle Pietre
`Durein Florence.
`
`
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 2
`
`

`

`
`
`Senior Editor
`Publishing Services Manager
`Editorial Assistant
`Cover Design
`Cover and Chapter Illustration
`Text Design
`Composition
`Technical Illustration
`Copyeditor
`Proofreader
`Indexer
`Interior printer
`Cover printer
`
`Denise E. M. Penrose
`Simon Crump
`SummerBlock
`Ross Caron Design
`Chris Asimoudis
`GGS Book Services
`Nancy Logan and Dartmouth Publishing,Inc.
`Dartmouth Publishing,Inc.
`Ken DellaPenta
`Jacqui Brownstein
`Linda Buskus
`Courier
`Courier
`
`Morgan KaufmannPublishers is an imprint ofElsevier.
`500 Sansome Street, Suite 400, San Francisco, CA 94111
`
`This book is printed onacid-free paper.
`
`© 2005 by Elsevier Inc. All rights reserved.
`
`Designations used by companies to distinguish their products are often claimed as trademarks orregistered
`trademarks.In all instances in which Morgan Kaufmann Publishers is aware ofa claim, the product names
`appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies
`for more complete information regarding trademarks and registration.
`
`
`No part ofthis publication maybe reproduced, storedin a retrieval system, or transmitted in any form or
`by any means—electronic, mechanical, photocopying, scanning, or otherwise—without prior written per-
`mission ofthe publisher.
`
`Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford,
`UK; phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail: permissions@elsevier.com.uk. You may
`also complete your request on-line via the Elsevier homepage (http://elsevier.com) by selecting “Customer
`Support”and then “Obtaining Permissions.”
`
`Library of Congress Cataloging-in-Publication Data
`Application submitted
`
`ISBN: 1-55860-604- 1
`
`For information on all Morgan Kaufmannpublications,
`visit our Web site at www.mkp.com.
`
`Printed in the United States of America
`04 05 06 07 08
`54321
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 3
`
`

`

`Contents
`
`
`Contents
`
`Preface
`
`ix
`
`CHAPTERS
`
`Computer Abstractions and Technology 2
`
`Introduction
`3
`Below Your Program 11
`Under the Covers
`15
`Real Stuff: Manufacturing Pentium 4 Chips
`Fallacies andPitfalls
`33
`Concluding Remarks
`35
`Historical Perspective and Further Reading
`Exercises
`36
`
`28
`
`36
`
`~~
`
`ce
`
`
`
`Introduction
`48
`49
`Operations of the Computer Hardware
`52
`Operands of the Computer Hardware
`Representing Instructions in the Computer
`Logical Operations
`68
`72
`Instructions for Making Decisions
`Supporting Procedures in Computer Hardware
`Communicating with People
`90
`MIPS Addressing for 32-Bit Immediates and Addresses
`Translating and Starting a Program 106
`How Compilers Optimize
`116
`How Compilers Work: An Introduction
`
`—epeeeeeeetUm&he
`NMNMNMNNNNMNNNNWNfh
`
`COMPUTERS IN THE REAL WORLD
`
`Information Technology for the 4 Billion without IT 44
`
`Instructions: Language of the Computer 46
`
`60
`
`79
`
`121
`
`95
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 4
`
`

`

`vi
`Contents
`
`
`CS
`
`6S
`
`121
`2.13 AC Sort Example to Put It AllTogether
`2.14
`Implementing an Object-Oriented Language
`2.15 Arrays versus Pointers
`130
`2.16 Real Stuff: |A-32 Instructions
`
`134
`
`130
`
`143
`2.17 Fallacies andPitfalls
`145
`2.18 Concluding Remarks
`2.19 Historical Perspective and Further Reading
`2.20 Exercises
`147
`
`147
`
`COMPUTERS IN THE REAL WORLD
`
`Helping Save Our Environment with Data 156
`
`Arithmetic for Computers 158
`
`160
`
`160
`Introduction
`3.1
`Signed and Unsigned Numbers
`3.2.
`3.3 Addition and Subtraction
`170
`3.4 Multiplication
`176
`3.5 Division
`183
`189
`3.6
`Floating Point
`3.7.
`Real Stuff: Floating Point in the [A-32
`3.8
`Fallacies and Pitfalls
`220
`3.9 Concluding Remarks
`225
`3.10 Historical Perspective and Further Reading
`3.11 Exercises
`229
`
`217
`
`229
`
`COMPUTERS IN THE REAL WORLD
`
`Reconstructing the Ancient World 236
`
`Assessing and Understanding Performance 238
`
`4.1
`
`4.2.
`4.3
`4.4
`
`Introduction
`
`240
`
`CPU Performance andIts Factors
`Evaluating Performance
`254
`Real Stuff: Two SPEC Benchmarks and the Performance of Recent
`
`246
`
`Intel Processors
`259
`266
`Fallacies and Pitfalls
`4.5
`270
`4.6 Concluding Remarks
`4.7 Historical Perspective and Further Reading
`4.8
`Exercises
`272
`
`272
`
`COMPUTERS IN THE REAL WORLD
`
`Moving People Faster and More Safely 280
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 5
`
`

`

`Contents
`vii
`
`The Processor: Datapath and Control 282
`
`284
`Introduction
`5.1
`Logic Design Conventions
`5.2
`Buildinga Datapath
`292
`5.3
`5.4 ASimple Implementation Scheme
`5.5
`A Multicycle Implementation
`318
`5.6
`Exceptions
`340
`346
`5.7. Microprogramming: Simplifying Control Design
`5.8 An Introduction to Digital Design Using a Hardware Design
`Language
`346
`Real Stuff: The Organization of Recent Pentium
`Implementations
`347
`5.10 Fallacies andPitfalls
`350
`5.11 Concluding Remarks
`352
`5.12 Historical Perspective and Further Reading
`5.13 Exercises
`354
`
`289
`
`300
`
`353
`
`5.9
`
`COMPUTERS IN THE REAL WORLD
`
`Empowering the Disabled 366
`
`Enhancing Performancewith Pipelining 368
`
`An OverviewofPipelining
`6.1
`A Pipelined Datapath
`384
`6.2
`Pipelined Control
`399
`6.3
`6.4 Data Hazards and Forwarding
`6.5 Data Hazardsand Stalls
`413
`
`370
`
`402
`
`6.6
`6.7
`
`Branch Hazards
`416
`Using a Hardware Description Language to Describe and Model a
`Pipeline
`426
`Exceptions
`427
`6.8
`AdvancedPipelining: Extracting More Performance
`6.9
`6.10 Real Stuff: The Pentium 4 Pipeline
`448
`6.11 Fallacies and Pitfalls
`451
`6.12 Concluding Remarks
`452
`6.13 Historical Perspective and Further Reading
`6.14 Exercises
`454
`
`432
`
`454
`
`COMPUTERS IN THE REAL WORLD
`
`Mass Communication without Gatekeepers 464
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 6
`
`

`

`Contents
`viii
`
`
`Large and Fast: Exploiting Memory Hierarchy 466
`
`7.1
`
`Introduction
`
`468
`
`7.2.
`The Basics of Caches
`473
`7.3. Measuring and Improving Cache Performance
`7.4 Virtual Memory
`511
`538
`7.5
`A Common Framework for Memory Hierarchies
`7.6
`Real Stuff: The Pentium P4 and the AMD Opteron Memory
`Hierarchies
`546
`
`492
`
`550
`Fallacies andPitfalls
`7.7.
`552
`7.8 Concluding Remarks
`7.9 Historical Perspective and Further Reading
`7.10 Exercises
`555
`
`555
`
`COMPUTERS IN THE REAL WORLD
`
`Saving the World's Art Treasures 562
`
`Storage, Networks, and Other Peripherals 564
`
`8.5
`
`8.6
`
`569
`
`603
`
`566
`Introduction
`8.1
`Disk Storage and Dependability
`8.2
`8.3. Networks
`580
`8.4
`Buses and Other Connections between Processors, Memory,andI/O
`Devices
`58]
`Interfacing I/O Devices to the Processor, Memory, and Operating
`System 588
`I/O Performance Measures: Examples from Disk andFile
`Systems
`597
`8.7. Designingan I/O System 600
`8.8
`Real Stuff: A Digital Camera
`8.9
`Fallacies andPitfalls
`606
`8.10 Concluding Remarks
`609
`8.11 Historical Perspective and Further Reading
`8.12 Exercises
`61]
`
`611
`
`COMPUTERS IN THE REAL WORLD
`
`Saving Lives through Better Diagnosis 622
`
`Multiprocessors and Clusters 9-2
`
`
`
`9-4
`Introduction
`9.1
`9-8
`Programming Multiprocessors
`9.2
`9.3. Multiprocessors Connected by a Single Bus
`
`9-11
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 7
`
`

`

`
`
`Contents
`
`
`9-20
`
`9.4 Multiprocessors Connected by a Network
`9.5
`Clusters
`9-25
`9-27
`9.6
`Network Topologies
`9.7. Multiprocessors Inside a Chip and Multithreading
`9.8
`Real Stuff: The Google Cluster of PCs
`9-34
`9.9
`Fallacies andPitfalls
`9-39
`9.10 Concluding Remarks
`9-42
`9.11 Historical Perspective and Further Reading
`9.12 Exercises
`9-55
`
`9-47
`
`9-30
`
`APPENDICES
`
` Assemblers, Linkers, and the SPIM Simulator A-2
`
`A.1
`
`Introduction A-3
`
`A.2. Assemblers A-10
`
`Linkers A-18
`A.3
`AA Loading A-19
`A.S Memory Usage A-20
`A.6
`Procedure Call Convention A-22
`A.7
`Exceptions and Interrupts A-33
`A.8
`Inputand Output A-38
`A.9
`SPIM A-40
`A.10 MIPS R2000 Assembly Language A-45
`A.11 Concluding Remarks A-81
`A.12 Exercises A-82
`
` The Basics of Logic Design B-2
`
`Introduction B-3
`B.1
`B.2 Gates, Truth Tables, and Logic Equations B-4
`B.3. Combinational Logic B-8
`B.4 Using a Hardware Description Language B-20
`B.5 Constructing a Basic Arithmetic Logic Unit B-26
`B.6
`Faster Addition: Carry Lookahead B-38
`B.7_ Clocks B-47
`B.8 Memory Elements: Flip-flops, Latches, and Registers B-49
`B.9 Memory Elements: SRAMs and DRAMs_ B-57
`B.10 Finite State Machines B-67
`B.11 Timing Methodologies B-72
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 8
`
`

`

`Contents
`
`
`
`
`
`B.12
`
`B.13
`
`B.14
`
`Field Programmable Devices B-77
`Concluding Remarks B-78
`Exercises B-79
`
`Mapping Control to Hardware C-2
`
`lant€)©qanNnnoDnWweWHeK
`
`oaLa ~I
`
`Introduction C-3
`Implementing Combinational Control Units C-4
`Implementing Finite State Machine Control C-8
`Implementing the Next-State Function with a Sequencer C-21
`Translating a Microprogram to Hardware C-27
`Concluding Remarks C-31
`Exercises C-32
`
`A Survey of RISC Architectures for Desktop, Server,
`and Embedded Computers D-2
`
`D,1
`
`D.2
`
`D.3
`
`D4
`
`DS
`
`Introduction D-3
`Addressing Modes andInstruction Formats D-5
`Instructions: The MIPS Core Subset D-9
`Instructions: Multimedia Extensionsof the Desktop/Server RISCs D-16
`Instructions: Digital Signal-Processing Extensions ofthe
`Embedded RISCs_
`D-19
`
`D9
`
`D.10
`
`D.11
`
`D.12
`
`D.13
`
`
`
`Instructions: Common Extensions to MIPS Core D-20
`D.6
`Instructions Unique to MIPS64=D-25
`D.7
`Instructions Unique to Alpha D-27
`D.8
`Instructions Unique to SPARC v.9 D-29
`Instructions Unique to PowerPC D-32
`Instructions Unique to PA-RISC 2.0 D-34
`Instructions Unique to ARM D-36
`Instructions Unique to Thumb D-38
`Instructions Unique to SuperH D-39
`Instructions Unique to M32R_ D-40
`Instructions Unique to MIPS16 D-41
`Concluding Remarks D-43
`Acknowledgments D-46
`References D-47
`
`D.14
`
`D.15
`
`D.16
`
`D.17
`
`D.18
`
`D.19
`
`Index
`I-1
`@ Glossary G-1
`@ Further Reading
`
`FR-1
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 9
`
`

`

`
`
`Computer
`Abstractions
`
`and Technology
`
`Civilization advances by extending
`the numberof important operations
`which we can perform without
`thinking about them.
`
`Alfred North Whitehead
`
`AnIntroduction to Mathematics, 1911
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 10
`
`

`

`This Page Intentionally Left Blank
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 11
`
`

`

`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`1.6
`
`Introduction 3
`
`Below Your Program ||
`
`Under the Covers
`
`15
`
`Real Stuff: Manufacturing Pentium 4 Chips
`
`28
`
`Fallacies and Pitfalls
`
`33
`
`Concluding Remarks
`
`35
`
`6 1.7
`
`Historical Perspective and Further Reading 36
`
`1.8
`
`Exercises
`
`36
`
`
`
`Introduction
`
`Welcome to this book! We’re delighted to have this opportunity to convey the
`excitement of the world of computer systems. This is not a dry and dreary field,
`where progressis glacial and where newideas atrophy from neglect. No! Comput-
`ers are the productof the incredibly vibrant information technology industry,all
`aspects of which are responsible for almost 10%ofthe gross national product of
`the United States. This unusual industry embraces innovation at a breathtaking
`rate. Since 1985 there have been a numberof new computers whose introduction
`appeared to revolutionize the computing industry; these revolutions were cut
`short only because someone else built an even better computer.
`This race to innovate has led to unprecedented progress since the inception of
`electronic computingin the late 1940s. Had the transportation industry kept pace
`with the computer industry, for example, today we could travel coast to coast in
`about a second for roughly a few cents. Take just a moment to contemplate how
`such an improvement would change society—living in Tahiti while working in
`San Francisco, going to Moscowfor an eveningat the Bolshoi Ballet—and you can
`appreciate the implications of such a change.
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 12
`
`

`

`Chapter 1 Computer Abstractions and Technology
`
`Computers haveled to a third revolutionfor civilization, with the information
`revolution taking its place alongside the agricultural and the industrial revolu-
`tions. The resulting multiplication of humankind’s intellectual strength and reach
`naturally has affected our everyday lives profoundly and also changed the waysin
`which the search for new knowledgeis carried out. There is now a newvein ofsci-
`entific investigation, with computational scientists joining theoretical and experi-
`mental scientists in the exploration of new frontiers in astronomy, biology,
`chemistry, physics, ...
`The computer revolution continues. Each time the cost of computing improves
`by another factor of 10, the opportunities for computers multiply. Applications
`that were economically infeasible suddenly become practical. In the recent past,
`the following applications were “computer sciencefiction.”
`
`m Automatic teller machines; A computer placed in the wall of banks to dis-
`tribute and collect cash would have been a ridiculous concept in the 1950s,
`whenthe cheapest computercostat least $500,000 and was the size of a car.
`
`m= Computers in automobiles: Until microprocessors improved dramatically in
`price and performancein the early 1980s, computer control ofcars was ludi-
`crous. Today, computers reduce pollution and improve fuel efficiency via
`engine controls and increase safety through the prevention of dangerous
`skids and throughthe inflation of air bags to protect occupants in a crash.
`
`m Laptop computers: Who would have dreamed that advances in computer
`systems would lead to laptop computers, allowing students to bring com-
`puters to coffeehouses and on airplanes?
`
`= Human genomeproject: The cost of computer equipment to mapand ana-
`lyze human DNAsequences is hundreds of millions of dollars. It's unlikely
`that anyone would have considered this project had the computer costs been
`10 to 100 times higher, as they would have been 10 to 20 years ago.
`
`m World Wide Web: Not in existence at the time of the first edition of this
`book, the World Wide Web has transformed our society. Amongits uses are
`distributing news, sending flowers, buying from online catalogues, taking
`electronic tours to help pick vacation spots, finding others who share your
`esoteric interests, and even more mundane topics like finding the lecture
`notes of the authors of your textbooks.
`
`Clearly, advancesin this technology nowaffect almost every aspect of our society.
`Hardware advances have allowed programmersto create wonderfully useful soft-
`ware, and explain why computers are omnipresent. Tomorrow’s science fiction
`computer applications are the cashless society, automated intelligent highways,
`and genuinely ubiquitous computing: no one carries computers because they are
`available everywhere.
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 13
`
`

`

`1.1 Introduction
`
`Classes of Computing Applications and Their
`Characteristics
`
`Although a commonset of hardware technologies (discussed in Sections 1.3 and
`1.4) is used in computers ranging from smart home appliances to cell phones to
`the largest supercomputers,
`these different applications have different design
`requirements and employ the core hardware technologies in different ways.
`Broadly speaking, computers are used in three different classes of applications.
`Desktop computers are possibly the best-known form of computing and are
`characterized by the personal computer, which most readers of this book have
`probably used extensively. Desktop computers emphasize delivering good perfor-
`manceto a single user at low cost and usually are used to execute third-party soft-
`ware, also called shrink-wrap software. Desktop computing is one of the largest
`markets for computers, and the evolution of many computing technologies is
`driven bythis class of computing, which is only about 30 years old!
`Servers are the modern form of what was once mainframes, minicomputers,
`and supercomputers, and are usually accessed only via a network. Serversare ori-
`ented to carrying large workloads, which may consist of either single complex
`applications, usually a scientific or engineering application, or handling many
`small jobs, such as would occur in building a large Web server. These applications
`are often based on software from another source (such as a database or simulation
`system), but are often modified or customized for a particular function. Servers
`are built from the same basic technology as desktop computers, but provide for
`greater expandability of both computing and input/output capacity. As we will see
`in the Chapter 4, the performance of a server can be measured in several different
`ways, depending on the application of interest. In general, servers also place a
`greater emphasis on dependability, since a crash is usually more costly than it
`would be ona single-user desktop computer.
`Servers span the widest range in cost and capability. At the low end, a server
`maybe little more than a desktop machine without a screen or keyboard and with
`a cost of a thousand dollars. These low-end servers are typically used forfile stor-
`age, small business applications, or simple web serving. At the other extreme are
`supercomputers, which at the present consist of hundreds to thousands of pro-
`cessors, and usually gigabytes to terabytes of memory and terabytes to petabytes
`of storage, and cost millions to hundreds of millions of dollars. Supercomputers
`are usually used for high-end scientific and engineering calculations, such as
`weather forecasting, oil exploration, protein structure determination, and other
`large-scale problems. Although such supercomputers represent the peak of com-
`puting capability, they are a relatively small fraction of the servers and arelatively
`small fraction of the overall computer market in termsoftotal revenue.
`Embedded computers are the largest class of computers and span the widest
`range of applications and performance. Embedded computers include the micro-
`processors found in your washing machine and car, the computersin a cell phone
`
`desktop computer A com-
`puter designed for use by an
`individual, usually incorporat-
`ing a graphics display, keyboard,
`and mouse.
`
`Server A computer used for
`running larger programs for
`multiple users often simulta-
`neously and typically accessed
`only via a network.
`
`supercomputerA class of
`computers with the highest per-
`formance andcost; they are
`configured as servers and typi-
`cally cost millions ofdollars.
`
`terabyte Originally
`1,099,511,627,776 (27°) bytes,
`although some communications
`and secondarystorage systems
`have redefined it to mean
`1,000,000,000,000 (10'*) bytes.
`
`embedded computer A com-
`puter inside another device used
`for running one predetermined
`application or collection of soft-
`ware.
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 14
`
`

`

`Chapter 1 Computer Abstractions and Technology
`
`or personaldigital assistant, the computers in a video game or digital television,
`and the networks of processors that control a modern airplane or cargo ship.
`Embedded computing systems are designed to run one application or one set of
`related applications, which is normally integrated with the hardware and delivered
`as a single system; thus, despite the large number of embedded computers, most
`users neverreally see that they are using a computer!
`Embedded applications often have unique application requirements that com-
`bine a minimumperformance with stringent limitations on cost or power. For
`example, consider a cell phone: the processor need only be as fast as necessary to
`handle its limited function, and beyond that, minimizing cost and power are the
`most important objectives. Despite their low cost, embedded computers often
`have the least tolerancefor failure, since the results can vary from upsetting (when
`your newtelevision crashes) to devastating (such as might occur when the com-
`puter in a plane or car crashes). In consumer-oriented embedded applications,
`such as a digital home appliance, dependability is achieved primarily through
`simplicity—the emphasis is on doing one function, as perfectly as possible. In
`large embeddedsystems, techniques of redundancy, which are used in servers,are
`often employed. Although this book focuses on general-purpose computers, most
`of the concepts apply directly, or with slight modifications, to embedded comput-
`ers. In several places, we will touch on someof the unique aspects of embedded
`computers.
`Figure 1.1 shows that during the last several years, the growth in the number of
`embedded computers has been much faster (40% compounded annual growth
`rate) than the growth rate among desktop computers and servers (9% annually).
`Note that the embedded computers include cell phones, video games, digital TVs
`and set-top boxes, personal digital assistants, and a variety of such consumer
`devices. Note that this data does not include low-end embedded control devices
`that use 8-bit and 16-bit processors,
`
`Elaboration: Elaborations are short sections used throughout the text to provide
`more detail on a particular subject, which may be of interest. Disinterested readers
`may skip over an elaboration, since the subsequent material will never depend on the
`contents of the elaboration.
`
`Many embedded processors are designed using processor cores, a version of a pro-
`cessor written in a hardware description language such as Verilog or VHDL. The core
`allows a designer to integrate other application-specific hardware with the processor
`core for fabrication on a single chip. The availability of synthesis tools that can gener
`ate a chip from a Verilog specification, together with the capacity of modern silicon
`chips, has made such special-purpose processors highly attractive. Since the core can
`be synthesized for different semiconductor manufacturing lines, using a core provides
`flexibility in choosing a manufacturer as well. In the last few years, the use of cores has
`
`
`
`
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 15
`
`

`

`1.1 Introduction
`
`1200
`
`1100
`1000
`
`900
`
`800
`
`700
`
`600
`
`500
`
`400
`
`300
`
`200
`
`Millionsofcomputers
`
`
`
`__| Embedded computer
`8 Desktops
`LJ Servers
`
`
`
`100
`
`1998
`
`1999
`
`2000
`
`2001
`
`2002
`
`FIGURE 1.1 The numberof distinct processors sold between 1998 and 2002. These counts
`are obtained somewhat differently, so some caution is required in interpreting the results. For example, the
`totals for desktops and servers count complete computer systems, because some fraction of these include
`multiple processors, the number of processors sold is somewhat higher, but probably by only 10-20%in
`total (since the servers, which may average more than one processor per system, are only about 3%ofthe
`desktopsales, which are predominantlysingle-processor systems). The totals for embedded computers actu-
`ally count processors, many of which are not even visible, and in some cases there may be multiple proces-
`sors perdevice.
`
`been growing very fast. For example, in 1998 only 31% of the embedded processors
`were cores. By 2002, 56% of the embedded processors were cores. Furthermore,
`while the overall growth rate in the embedded market has been 40% per year, this
`growth has been primarily driven by cores, where the compounded annual growth rate
`has been 63%!
`
`Figure 1.2 shows the major architectures sold in these markets with counts for
`each architecture, across all
`three types of products (embedded, desktop, and
`server). Only 32-bit and 64-bit processors are included, although 32-bit proces-
`sors are the vast majority for most ofthe architectures.
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 16
`
`

`

`Chapter 1 Computer Abstractions and Technology
`
`[| Other
`@ sPARC
`W Hitachi SH
`§) PowerPC
`||Motorola 68K
`[) mies
`[] 14-32
`W@ ARM
`
`
`
`Millionsofprocessors
`
`zation.
`
`Successful programmers have always been concerned about the performance of
`their programs because getting results to the user quickly is critical in creating
`successful software. In the 1960s and 1970s, a primary constraint on computer
`performance was the size of the computer's memory. Thus programmers often
`followed a simple credo: Minimize memory space to make programsfast. In the
`last decade, advances in computer design and memory technology have greatly
`reduced the importance of small memory size in most applications other than
`those in embedded computing systems.
`Programmers interested in performance now need to understand the issues
`that have replaced the simple memory modelof the 1960s:
`the hierarchical nature
`of memories and the parallel nature of processors. Programmers who seek to
`build competitive versions of compilers, operating systems, databases, and even
`applications will therefore need to increase their knowledge of computer organi-
`
`1999
`
`2000
`
`2001
`
`2002
`
`FIGURE 1.2 Sales of microprocessors between 1998 and 2002 by instruction set archi-
`tecture combining all uses. The “other” category refers to processors that are either application-
`specific or customizedarchitectures, In the case of ARM, roughly 80%ofthe sales are for cell phones, where
`an ARMcore is used in conjunction with application-specific logic on a chip.
`
`What You Can Learnin This Book
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 17
`
`

`

`1.1 Introduction
`
`We are honored to have the opportunity to explain what’s inside this rev-
`olutionary machine, unraveling the software below your programand the hard-
`ware under the covers of your computer. By the time you complete this book, we
`believe you will be able to answer the following questions:
`
`m Howare programswritten in a high-level language, such as C or Java, trans-
`lated into the language of the hardware, and how does the hardware execute
`the resulting program? Comprehending these concepts forms the basis of
`understanding the aspects of both the hardware and software thataffect pro-
`gram performance.
`
`gm What is the interface between the software and the hardware, and how does
`software instruct the hardware to perform needed functions? These con-
`cepts are vital to understanding how to write manykindsofsoftware.
`
`@ What determines the performance of a program, and how can a program-
`mer improve the performance? As wewill see, this depends onthe original
`program, the software translation of that program into the computer’s lan-
`guage, and the effectiveness of the hardwarein executing the program.
`
`m What techniques can be used by hardware designers to improve perfor-
`mance? This book will introduce the basic concepts of modern computer
`design. The interested reader will find much more material onthis topic in
`our advanced book, A Computer Architecture: A Quantitative Approach.
`
`Without understanding the answers to these questions, improving the perfor-
`mance of your program on a modern computer, or evaluating what features might
`make one computer better than another for a particular application, will be a
`complex process of trial and error, rather than a scientific procedure driven by
`insight and analysis.
`This first chapter lays the foundation for the rest of the book.It introduces the
`basic ideas and definitions, places the major components ofsoftware and hard-
`ware in perspective, and introduces integrated circuits, the technology that fuels
`the computer revolution. In this chapter, and later ones, you will likely see a lot of
`new words, or words that you may have heard, but are not sure what they mean.
`Don’tpanic! Yes, there is a lot of special terminology used in describing modern
`computers, but the terminology actually helps since it enables us to describe pre-
`cisely a function or capability. In addition, computer designers (including your
`authors) love using acronyms, whichare easy to understand once you know what
`the letters stand for! To help you rememberand locate terms, we have included a
`highlighted definition of every term, the first time it appears in the text. After a
`short time of working with the terminology, you will be fluent, and your friends
`
`acronym A word constructed
`bytaking the initial letters of
`string of words. For example:
`RAM is an acronym for Ran-
`dom Access Memory, and CPU
`is an acronym for Central Pro-
`cessing Unit.
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 18
`
`

`

`10
`
`Chapter 1 Computer Abstractions and Technology
`
`will be impressed as you correctly use words such as BIOS, DIMM, CPU,cache,
`DRAM, ATA,PCI, and manyothers.
`To reinforce how the software and hardware systemsused to run a program will
`affect performance, we use a special section, “Understanding Program Perfor-
`mance,” throughout the book,with the first one appearing below. These elements
`summarize important insights into program performance.
`
`
`
`Understanding
`Program
`Performance
`
`The performance of a program depends on a combinationof the effectiveness of
`the algorithmsused in the program, the software systems used to create and trans-
`late the program into machine instructions, and the effectiveness of the computer
`in executing those instructions, which may include I/O operations. The following
`table summarizes how the hardware and softwareaffect performance.
`
`Where is this
`Hardware or software mMregtro
`
`
`atiditePere elias topic covered?
`| Algorithm
`Determines both the number of source-level
`Other books!
`statements and the number of |/O operations
`executed
`
`Programming language, Determines the number of machine instructions|Chapters 2 and 3
`
`compiler, and architecture
`for each source-level statement
`
`
`
`
`
`Processor and memory
`system
`
`Determines how fast instructions can be
`executed
`
`Chapters 5, 6,
`and 7
`
`Check
`Yourself
`
`Chapter 8&
`Determines how fast I/O operations may be
`|/O system (hardware and
`
`operating system) executed
`
`
`
`“Check Yourself” sections are designed to help readers assess whether they have
`comprehended the major concepts introduced in a chapter and understand the
`implications of those concepts. Some “Check Yourself” questions have simple
`answers; others are for discussion among a group. Answers to the specific ques-
`tions can be found at the end of the chapter. “Check Yourself” questions appear
`only at the end ofa section, makingit easy to skip them if you are sure you under-
`stand the material,
`
`1. Section 1,1 showed that the number of embedded processors sold every
`year greatly outnumbers the number of desktop processors. Can you con-
`firm or denythis insight based on your own experience? Try to count the
`number of embedded processors in your home. How does it compare with
`the number of desktop computers in your home?
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 19
`
`

`

`1.2 Below Your Program
`
`As mentioned earlier, both the software and hardware affect the perfor-
`mance of a program. Can youthink of examples where each of the follow-
`ing is the right place to look for a performance bottleneck?
`
`language statements.
`
`A typical application, such as a word processor or a large database system, may
`consist of hundreds of thousandsto millionsof lines of code and rely on sophisti-
`cated software libraries that
`implement complex functions in support of the
`application. As we will see, the hardware in a computer can only execute extremely
`simple low-level instructions. To go