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

`

`ACKNOWLEDGEMENTS
`
`Figures 1.9. I. [5 L‘ourtesv of Intel.
`
`Computers in the Real \Vorld:
`
`Figure [.1] Courtesy of Storage Technology Corp.
`
`Photo of “A Laotian villager," courtesy of David Sanger.
`
`Figures. III. [3.2. (‘.I3.2 (Itmrtesv of the (_.harles Itablmge Inttitute.
`L'ttiversitv of Minnesota Libraries. Minneapolis.
`
`Figures 1.7.3. (.1. I 3. l, {3. I 5.3. 7.9.3. 3.11.2 Courtesy of IBM.
`
`Figure [.14 Cmtrtearrr ul‘Cruy Inc.
`
`Figure [3.5 Courtesy oprple ( Iumputer, Inc.
`
`Figure lit» t inurresv of the t Zmnputer History Museum.
`
`Figure 7.53 Courtesy of AMI).
`
`Photo of an “Indian villager," propertyr ul‘Iincore Software, l_1:.I.. India.
`
`Photos of “Block and students." and “a pop-up archival satellite tag."
`courtesy of Prufessur Barbara Black. Photos by Scott Taylor.
`
`Photo» of “Professor Dawson and student" and “the Mic-.1 micromote.h
`
`courtesy of Al’fWorld \Vide Photos.
`
`l‘holus of “images of pottery fragments" and “a computer recunslruc-
`tiun,"cuurle5_v ol'Andrew \Villis and David It. Cooper, Brown L'niversitv.
`Division of Engineering.
`
`Figures 7.9.1. 7.9.2 Courtesv of Museum of Science. Boston.
`
`Photo of "the EurostanGV train," by his van der Kolk.
`
`Figure 7.951 Curtl‘leznur of MIPS Technologies, Inc.
`
`l‘hulu (ll-“”16 interior oI‘al Eul‘oslar TGV cab," by And)“ Veilcll.
`
`Figure 8.3 -¢"=l’eg, Skorpimki.
`
`Photo of "firefighter Ken Whine-n." courtesy,r oHVorhI Economic Forum.
`
`Figure 3.1].l (Iourtesv uflhe (Imuputer Museum ot'r‘um-rica.
`
`Figure 3.1 1.5 tjourtesy ofthe Commercial Llomputing NILISL‘UIT'I.
`
`Figures EH [.3. 9.| L3 Courtesy of NASA Ames Research Center.
`
`Figure 9.1 II-I Courtesy of Lawrence Livermore National Laboratory.
`
`Graphic of an “artificial
`Reprinted by permission.
`
`retina." 4" The San Francisco (Throuicle.
`
`Image of “A laser scan of L-Iichelnngelo’n alatue of David," courtesy of
`Marc Levov and Dr. Franca Falletti. director of the tiaileria dell‘Acca-
`demiu, Italy.
`
`111 image
`“An image From the Sistine Chapel." courtesy of Luca l’euati.
`recorded using the scanner for IR retlectography of the [NUA {National
`Institute for Applied Optics. httpfllarteanmit) at the Opilicin delle Pietre
`Dure in Florence.
`
`
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 2
`
`

`

`
`
`Senior Editor
`
`Denise E. M. l’enrose
`
`Publishing Services Manager
`Iiditorial Assistant
`Cover Design
`timer and Chapter Illustration
`'l‘ext Design
`Composition
`'l'echnical Illustration
`Copyeditor
`Proofreader
`indexer
`
`Simon Crump
`Summer Block
`Ross Caron Design
`[Chris Asimondis
`HUS Book Services
`Nancy Logan and Dartmouth Publishing. inc.
`llartnit'iulh Publishing, inc.
`Ken Dellal’enta
`lacqui Brownstein
`[.inda littskus
`
`Interior printer
`Cover printer
`
`Courier
`tjourier
`
`.\-'lorg,an Kauhnann Publishers is an imprint of Elsevier.
`Stilt Sansome Street, Suite 4““. San Francisco, t IA 9-H t]
`
`This book is printed on acidei'ree paper.
`
`'<"- 2005 by Elsevier Inc. All rights reserved.
`
`Designatitms used by companies to distinguish their products are often claimed as trademarks or registered
`trademarks. In all instances in which Morgan Kaufmann Publishers is aware of a claim. the product names
`appear in initial capital or all capital letters. Readers, however. should contact the appropriate companies
`lot more complete information regarding trademarks and registration.
`
`
`No part of this publication may be reproduced. stored in a retrieval system. or transmitted in any form or
`by any means
`electronic, mechanical. photocopying. scanning, or ratherwise—withoul prior written per—
`mission of the publisher.
`
`Permissions may he sought directly from Elsevier's Science &' Technology Rights Department in Oxford.
`UK: phone: (till lBoS 843830. fax: tt-N) [SoS 85.5333. e-mail: permissiunsGT'elsevier.comark. You may
`also complete your request tun—line via the Iilseyier homepage ihttp:Helseyier.com) hy selecting “Customer
`Support" and then “Obtaining Permissions."
`
`Library of t Iongress t lataioging—in—l’ulslication Data
`Application submitted
`
`ISBN: l‘SEli‘ihU-{fill‘l‘l
`
`For information on all Morgan Kaolinann publications.
`visil nLlr “"eh site at www.mlip.corl‘t.
`
`Printed in the United States of America
`04 {15 06 U? [18
`5 4 3 2
`I
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 3
`
`

`

`
`
`Contents
`
`
`
`
`Contents
`
`Preface
`
`ix
`
`C H A P T E R S
`
`a Computer Abstractions and Technology 2
`
`1.1
`
`introduction
`
`3
`
`Below Your Program I
`1.2
`1.3 Under the Covers
`15
`
`l
`
`1.4
`1.5
`
`Real Stuff: Manufacturing Pentium {1 Chips
`Fallacies and Pitfalls
`33
`
`28
`
`I
`
`35
`Lo Concluding Remarks
`1.? Historical Perspective and Further Reading
`1.8
`Exercises
`3o
`
`36
`
`COMPUTERS IN THE REAL WORLD
`
`Information Technology for the 4 Billion without IT 44
`
`a Instructions: Language of the Computer 46
`
`2.1
`
`Introduction
`
`48
`
`49
`2.2 Operations of'the Computer Hardware
`52
`2.3 Operands ot‘the Computer l-lardware
`2.4
`Representing Instructions in the Computer
`2.5
`Logical Operations
`(18
`72
`2.6
`Instructions for Making Decisions
`2.?
`Sttpporting Procedures in Computer Hardware
`2.8 Communicating with People
`90
`2.9 MIPS Addressing for 32—Bit lmmediates and Addresses
`2.10 'l'ranslating and Starting, a Program 106
`2.l I How (It'mtpilers Optimize
`I lo
`"3
`.I2 How Compilers Work: An Introduction
`
`60
`
`F'9
`
`95
`
`I2[
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 4
`
`

`

`Contents
`
`.13 A C Sort Example to Put It All 'I'ogether
`
`121
`
`Implementing an Object-Oriented Language
`.14
`.15 Arrays versus Pointers
`130
`.16 Real Stuff: Iii—32 Instructions
`
`I34
`
`130
`
`.17 Fallacies and Pitfalls
`
`143
`
`145
`.18 Concluding Remarks
`.19 Historical Perspective and Further Reading
`.20 Exercises
`14?
`
`14?
`
`totototototomta)
`
`COMPUTERS IN THE REAL WORLD
`
`I'Iehing Save Our Environment with Data 156
`
`a Arithmetic for Computers 158
`
`3.l
`
`Introduction
`
`160
`
`Signed and Unsigned Numbers
`3.2
`3.3 Addition and Subtraction
`120
`
`160
`
`3.4 Multiplication
`5.5 Division
`183
`
`176
`
`3.6
`3.?
`3.8
`
`189
`Floating Point
`Real Stuff: Floating, Point in the lA—32
`Fallacies and Pitfalls
`220
`
`21?
`
`I
`
`225
`3.9 Concluding Remarks
`3.11) Historical Perspective and Further Reading
`3.1 1 Exercises
`229
`
`229
`
`COMPUTERS IN THE REAL WORLD
`
`Reconstructing the Ancient World 236
`
`n Assessing and Understanding Performance 238
`
`4.|
`
`4.2
`
`4.3
`4.4
`
`Introduction
`
`240
`
`CPU Performance and Its Factors
`
`246
`
`254
`Evaluating Performance
`Real Stuff: Two SPEC Benchmarks and the Performance of Recent
`
`Intel Processors
`
`259
`
`4.5
`
`Fallacies and Pitfalls
`
`266
`
`I
`
`2?”
`4.6 Concluding Remarks
`4.? 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
`V"
`
`'I'he Processor: Datapath and Control 282
`
`5.1
`
`Introduction
`
`284
`
`289
`
`301)
`
`Logic Design Conventions
`5.2
`Buildinga Datapath
`293.
`5.3
`A Simple Implementation Scheme
`5.4
`A Mullicvcle Implementation
`318
`5.5
`Exceptions
`340
`5.0
`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 and Pitfalls
`350
`
`5.9
`
`352
`5.11 Concluding Remarks
`5.12 Historical Perspective and Further Reading
`5.13 Exercises
`354
`
`353
`
`COMPUTERS IN THE REAL WORLD
`
`Empowering the Difllell 383
`
`Enhancing Performance with Pipelining 368
`
`An Overview of Pipelining
`6.1
`A Pipelined Datapath
`384
`6.2
`Pipeiined Control
`399
`6.3
`6.4 Data Hazards and Forwarding
`[3.5 Data Hazards and Stalls
`413
`
`370
`
`402
`
`6.6
`
`Branch Hazards
`
`416
`
`(3.?
`
`Using :1 Hardware Description Language to Describe and Model a
`Pipeline
`426
`Exceptions
`43?
`{LS
`6.9 Advanced Pipelining: Exiracling More Performance
`6.10 Real Stuff: The Pentium 4 Pipeline
`448
`5.11 Fallacies and Pitfalls
`451
`
`432
`
`h.12 Concluding Remarks
`
`453
`
`6.13 Historical Perspective and Further Reading
`6.14 Exercises
`454
`
`45.4
`
`cOMPUTERS IN THE REAL WORLD
`
`Mass Communication without Gatekeepers 4B4
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 6
`
`

`

`Contents
`will
`
`
`Large and Fast: Exploiting Memory Hierarchy 466
`
`7.1
`
`7.2
`
`Introduction
`
`468
`
`The Basics ol'Caches
`
`473
`
`7.3 Measuring and Improving Cache Performance
`7.4 Virtual Memory
`511
`538
`7.5
`A Common Framework for M emory Hierarchies
`7.6
`Real Stuff: The Pentium P4 and the AMD Opteron Memoryr
`Hierarchies
`546
`
`492
`
`7 7
`
`Fallacies and Pitfalls
`
`550
`
`7.8 Concluding Remarks
`
`552
`
`7.9 Historical Perspective and Further Reading
`7.10 Exercises
`555
`
`555
`
`COMPUTERS IN THE REAL WORLD
`
`Savlng the World's Art Treasures 582
`
`Storage, Networks, and Other Peripherals 564
`
`8.1
`
`Introduction
`
`560
`
`Disk Storage ant11)epend;ihilily
`8.2
`8..3 Networks
`580
`
`569
`
`8.4
`
`Buses and Other Connections between Processors, Memory, and [IO
`Devices
`581
`
`8.5
`
`Interfacing 1/0 Devices to the Processor, Memory. and Operating
`System 588
`8.6 NO Performance Measures: Examples from Disk and File
`
`597
`Systems
`8.? Designing an 1/0 System out)
`8.8
`Real Stuff: A Digital Camera
`8.9
`Fallacies and Pitfalls
`(506
`
`603
`
`(709
`8.11) Concluding Remarks
`8.11 Historical Perspective and Further Reading,
`8.12 Exercises
`(111
`
`611
`
`cOMPUTERS IN THE REAL WORLD
`
`Saving Lives throng: Better Diagnosis 622
`
`
`
`Multiprocessors and clusters 9-2
`
`9.1
`
`Introduction
`
`9—4
`
`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.4 Multiprocessors Connected by a NetWork
`9.5
`Clusters
`9-25
`
`9-20
`
`9.6
`9.?
`9.8
`9.9
`
`9—2?
`Network 'l'opologies
`M ultiprocessors Inside a Chip and Multithreading
`Real Stuff: The Google Cluster of PCS
`9—34
`Fallacies and Pitfalls
`9-39
`
`9—30
`
`9-42
`9.10 Concluding Remarks
`9.11 Historical Perspective and Further Reading
`9.12 Exercises
`9-55
`
`9-4?
`
`APPENDI¢E$
`
` Assemblers, Linkers, and the SPIM Simulator A-2
`
`A.1
`
`Introduction
`
`A—3
`
`A“? Assemblers
`
`A—lU
`
`A3
`
`Linkers A-18
`
`AA Loading A—l9
`
`Ax": Memory Usage A-20
`Ab
`Procedure Call Convention A-EE
`
`A]
`A.8
`A59
`
`Exceptions andlnterrupts A-33
`lnpntand Output
`A—38
`SPLVI
`A—40
`
`£1.10 MIPS R2000 Assembly Language
`AJ] ConcludingRemarks
`A—S]
`A.12 Exercises A-Sl
`
`91—45
`
`
`
`The Basics of Logic Design 3-2
`
`8.1
`
`Introduction
`
`8-3
`
`8.2 Gates, Truth Tables. and Logic Equations
`8.3 Combinational Logic 88
`8.4 Using a Hardware Description Language
`8.5 Constructing a Basic Arithmetic Logic Unit
`8.6:
`Faster Addition: Carry Lookahead
`8-38
`8.? Clocks
`8—4?
`
`8—4
`
`8—20
`B—2b
`
`8.8 M emory Elements: Flip-flops. Latches, and Registers
`
`8-49
`
`8.9 Memory Elements: SRAMS and DRAMS
`8.10 Finite State N'Iachines
`8-67
`
`8-57
`
`8.1] Timing k-lethodologies
`
`8—?2
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 8
`
`

`

`Contents
`
`
`
`
`
`13.12 Field Programmable Devices
`
`13-7?
`
`8.13 Concluding Remarks
`15.14 Exercises BJ‘)
`
`8-78
`
`Mapping Control to Hardware
`
`c-2
`
`C.l
`
`Introduction
`
`(3-3
`
`(1-4
`Implementing Combinational Control Units
`(1.2
`(3-8
`Implementing Finite State Machine Control
`C.3
`Implementing the Next-State Function with a Sequencer C-El
`(1.4
`Cf: Translating a h-Iicroprogram to Hardware
`(2-27
`Ci: Concluding Remarks
`C—31
`(L? Exercises
`(232
`
`A Survey of nlsc Architectures for Desktola, Server,
`and Embedded Computers 0-2
`
`13.1
`
`Introduction
`
`13-3
`
`D.2 Addressing Modes and Instruction Formats
`11.3
`Instructions: The MIPS Core Subset
`I)-9
`
`13—5
`
`DA Instructions: Multimedia Extensions ofthe Desktop/Server RISCs
`D5
`Instructions: Digital Signal—Processing Extensions ofthe
`Embedded RISCs
`D-19
`
`[31— lo
`
`13.6
`
`Instructions: Common Extensions to MIPS Core
`
`13-30
`
`1).?
`[18
`
`Instructions Unique to MlPStiLt
`Instructions Unique to Alpha
`
`D-25
`IJ-ZT
`
`17-29
`Instructions Unique to SPARC v.9
`17.9
`D.10 Instructions Unique to PowerPC D—32
`113.11
`Instructions Unique to PA—RISC 2.0
`0—34
`1.3.1.2 Instructions Unique to ARM 17—36
`D.13 Instructions Unique to Thumb
`D—38
`D.l4 Instructions Unique to SuperH D-39
`1).]5 Instructions Unique to M32R 13-40
`1.3.16 Instructions Unique to MlPSlo D-41
`1).]? Concluding Remarks D-43
`17.18 Acknowledgments
`17-46
`13.19 References
`D—47
`
`Index
`
`1—]
`
`I Glossary
`
`(7—!
`
`I Further Reading
`
`FR-I
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 9
`
`

`

`
`
`Computer
`
`Abstractions
`
`and Technology
`
`Civilization advances by extending
`the number of important operations
`which we can perform without
`thinking about them.
`
`Mind North Whltohoad
`
`An Introduction 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
`
`Introduction 3
`
`1.2
`
`1.3
`
`1.4
`
`1.5
`
`Below Your Program II
`
`Under the Covers
`
`15
`
`Real Stuff: Manufacturing Pentium 4 Chips
`
`38
`
`Fallacies and Pitfalls
`
`33
`
`1.6
`
`Concluding Remarks
`
`35
`
`I 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 coatvey the
`excitement of the world of computer systems. This is not a dry and dreary field,
`where progress is glacial and where new ideas atrophy from neglect. No! Comput-
`ers are the product of the incredibly vibrant information technology industry, all
`aspects of which are responsible For almost 10% of the gross national product of
`the United States. This unusual industry embraces innovation at a breathtaking
`rate. Since 1985 there have been a number of 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 computing in the late 19405. 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 Moscow for an evening at the Bolshoi Ballet—and you can
`appreciate the implications of such a change.
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 12
`
`

`

`Ohm!» 1 Comic: Abstractions and Technology
`
`Computers have led to a third revolution for 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 ways in
`which the search for new knowledge is carried out. There is now a new vein of sci-
`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 science fiction.”
`
`I 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 19505,
`when the cheapest c0mputer cost at least $500,000 and was the size of a car.
`
`I Computers in automobiles: Until microprocessors improved dramatically in
`price and performance in the early 19805. computer control of cars was ludi-
`crous. Today, computers reduce pollution and improve fuel efficiency via
`engine controls and increase safety through the prevention of dangerous
`skids and through the inflation of air bags to protect occupants in a crash.
`
`I 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?
`
`l Human genome project: The cost of computer equipment to map and ana—
`lyze human DNA sequences 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.
`
`I Wold Wide irVeit: Not in existence at the time of the first edition of this
`
`book, the World Wide Web has transformed our society. Among its uses are
`distributing news, sending flowers, buying from online catalogues, taking
`electmnic tours to help pick vacatiou 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, advances in this technology now affect almost every aspect of our society.
`Hardware advances have allowed programmers to 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 Introductlon
`
`Classes of computing Applications and Their
`
`Characteristics
`
`Although a common set 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-
`mance to 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 by this 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. Servers are 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 011 software front 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 in put/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 On a Single-user desktop computer.
`Servers span the widest range in cost and capability. At the low end, a server
`may be 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 for file 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 a relatively
`small fraction of the overall computer market in terms of total 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 computers in 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.
`
`supercomputer A class of
`computers with the highest per-
`formance and cost; they are
`configured as servers and typi—
`cally cost millions of dollars.
`
`terabyte Originally
`1,099.51 l,(127,??6 {24”} bytes,
`although some communications
`and secondary storage systems
`have redefined it to mean
`
`1,000.000noonao (10”) bytes.
`
`embedded computer A com-
`puter inside another device used
`for running one predetermined
`application or collection ofsoft-
`wore.
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 14
`
`

`

`
`
`Charter 1 Commuter Abstractions and Technology
`
`or personal digital 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 never really see that they are using a computer!
`Embedded applicatious often have unique application requirements that com»
`bine a minimum performance 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 tolerance for failure, since the results can vary from upsetting (when
`your new television 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 embedded systems, 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 sonie of 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, 3 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 Veritog 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
`
`1190
`
`1 000
`
`
`
`D Embedded computer
`I Desktops
`
`I serers
`
`
`
`Millionsofcomputers
`
`900
`
`800
`
`700
`
`600
`
`100
`
`500
`
`400
`
`300
`
`200
`
`1998
`
`1999
`
`2000
`
`2001
`
`2002
`
`FIGURE 1.1 Tho number of 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 traction of these include
`multiple processors. the number of processors sold is somewhat higher. but probably ht; only Ill 2t|"-n in
`tot-.1] (since the servers. which may average more than one processor per system. are only about 3th: of the
`desktop sales. which are predominantly sirtgleeprocessor systems). The totals for embedded computers actur
`ally count processors, many of which are not even visible. and in some cases there may be multiple proces-
`sors per device.
`
`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 ot‘ the architectures.
`
`Patent Owner, Bot M8 LLC - Ex. 2044, p. 16
`
`

`

`Chapter 1 Col-motor abstractions and technology
`
`I: Other
`
`I SPAHC
`
`I Hitachi SH
`
`I PowerPC
`
`l:l Motorola 88K
`
`
`
`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 19605 and 19705, 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 programs fast. 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 model ofthe 19605:
`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-
`
`1998
`
`1999
`
`2000
`
`2001
`
`2002
`
`FIGURE 1.2 Sales of mlcroprocomn Maroon 1998 and 2002 by Instruction set are!“-
`techno comblnhg all III... The "other" category refers to processors that are either application-
`specilic or customized architectures. In the case ul'ARM. roughly 30% of the sales are for cellphones. where
`an ARM core is used in conjunction with applicatinivspccific logic on a chip.
`
`What You Can Learn in 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 program and 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:
`
`I How are programs written in a high-level language, such as C or lava, 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 ofboth the hardware and software that affect pro-
`gram performance.
`
`I 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 many kinds of software.
`
`I What determines the performance of a program, and how can a program-
`mer improve the performance? As we will see, this depends on the original
`program, the software translation of that program into the computer’s lan-
`guage, and the effectiveness of the hardware in executing the program.
`
`I 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 on this topic in
`our advanced book, A (L'ompuhrr 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 of software 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’t panic! 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) lure using acronyms, which are easy to understand once you know what
`the letters stand for! To help you remember and 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
`by taking the initial letters of
`
`string ofwords. 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
`
`charter :I. Comte: Abetractlone and Technology
`
`will be impressed as you correctly use words such as BIOS, DIMM, CPU, cache,
`DRAM, ATA, PCI, and many others.
`To reinforce how the software and hardware systems used 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 combination of the effectiveness of
`the algorithms used 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 U0 operations. The following
`table summarizes how the hardware and software affect performance.
`
`Where is this
`How this component effect:
`Hardwue or software
`
`
`performancecomponent topic covered?
`
`- Algorithm
`
`Determines both the number of source—levei
`statements and the number of I/O operations
`executed
`
`Other books!
`
`
`
`
`
`Programming language.
`compiler. and architecture
`Processor and memory
`system
`
`Determines the number of machine instructions Chapters 2 and 3
`for each source-level statement
`‘
`Determines how fast instructions can be
`executed
`
`Chapters 5, 6.
`and 7
`
`Chapter 8
`Determines how fast I/O operations may be
`I/D system (hardware and
`
`operating system} executed
`
`
`
`Check
`
`Yourself
`
`“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 diSCUSSlOn 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 of a section, making it easy to skip them if you are sure you under-
`stand the material.
`
`]. 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 deny this 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 Bolow Your Program
`
`As mentioned earlier, both the software and hardware affect the perfor—
`mance of a progr