third edition i n t r o d u c t i o n t o c o m p u t i n g s y s t e m s f r o m b i t s & g a t e s t o C / C + + & b e y o n d yale n. patt sanjay j. patel introduction to computing systems thirdedition introduction to computing systems from bits & gates to C/C++ & beyond Yale N. Patt TheUniversityofTexasatAustin Sanjay J. Patel UniversityofIllinoisatUrbana-Champaign INTRODUCTIONTOCOMPUTINGSYSTEMS:FROMBITS&GATESTOC/C++&BEYOND,THIRDEDITION PublishedbyMcGraw-HillEducation,2PennPlaza,NewYork,NY10121.Copyright(cid:2)c2020byMcGraw-HillEducation.Allrights reserved.PrintedintheUnitedStatesofAmerica.Previouseditions(cid:2)c2004,and2001.Nopartofthispublicationmaybereproduced ordistributedinanyformorbyanymeans,orstoredinadatabaseorretrievalsystem,withoutthepriorwrittenconsentofMcGraw-Hill Education,including,butnotlimitedto,inanynetworkorotherelectronicstorageortransmission,orbroadcastfordistancelearning. Someancillaries,includingelectronicandprintcomponents,maynotbeavailabletocustomersoutsidetheUnitedStates. Thisbookisprintedonacid-freepaper. 1 2 3 4 5 6 7 8 9 LCR 24 23 22 21 20 19 ISBN978-1-260-15053-7(boundedition) MHID1-260-15053-4(boundedition) ISBN978-1-260-42474-4(loose-leafedition) MHID1-260-42474-X(loose-leafedition) ExecutivePortfolioManager:SuzyBainbridge ProductDeveloper:HeatherErvolino SeniorMarketingManager:ShannonO’Donnell ContentProjectManager:JeniMcAtee Buyer:SandyLudovissy Designer:DavidHash ContentLicensingSpecialist:MelissaHomer CoverImage:FrontCoverComputingart(cid:2)cYaleN.Patt;Abstractimageingreen,orangeandyellow(cid:2)cDesignPics/TimAntoniuk; Abstractimageinorange,greenandyellow(cid:2)cDesignPics/TimAntoniuk;Computerlaptopsonablueabstractbackground(cid:2)cloops7/ GettyImages;Illustrationofstreamsofbinarycode(cid:2)cShutterstock/Tavarius Compositor:Aptara(cid:2)R,Inc. Allcreditsappearingonpageorattheendofthebookareconsideredtobeanextensionofthecopyrightpage. LibraryofCongressCataloging-in-PublicationData Names:Patt,YaleN.,author. Patel,SanjayJ.,author. Title:Introductiontocomputingsystems:frombits&gatestoc/c++& beyond/YaleN.Patt,TheUniversityofTexasatAustin,SanjayJ.Patel, UniversityofIllinoisatUrbana-Champaign. Description:Thirdedition. NewYork,NY:McGraw-Hill,2020. Identifiers:LCCN2018050089 ISBN9781260150537(acid-freepaper) ISBN 1260150534(acid-freepaper) Subjects:LCSH:Computerscience. C(Computerprogramlanguage) Classification:LCCQA76.P3672019 DDC004–dc23LCrecordavailableat https://lccn.loc.gov/2018050089 TheInternetaddresseslistedinthetextwereaccurateatthetimeofpublication.Theinclusionofawebsitedoesnotindicateanendorse- mentbytheauthorsorMcGraw-HillEducation,andMcGraw-HillEducationdoesnotguaranteetheaccuracyoftheinformationpresented atthesesites. mheducation.com/highered Tothememoryofmyparents, AbrahamWalterPattA"HandSarahClaraPattA"H, whotaughtmetovalue“learning” evenbeforetheytaughtmetorideabicycle. Tomylovingfamily, Amita,Kavi,andAman. Contents Preface xv 2.4 ConversionBetweenBinaryandDecimal 31 2.4.1 BinarytoDecimalConversion 31 2.4.2 DecimaltoBinaryConversion 32 2.4.3 ExtendingConversiontoNumberswith 1 Welcome Aboard 1 FractionalParts 33 1.1 WhatWeWillTrytoDo 1 2.5 OperationsonBits—PartI:Arithmetic 34 1.2 HowWeWillGetThere 1 2.5.1 AdditionandSubtraction 34 1.3 TwoRecurringThemes 3 2.5.2 Sign-Extension 36 1.3.1 TheNotionofAbstraction 3 2.5.3 Overflow 36 1.3.2 Hardwarevs.Software 5 2.6 OperationsonBits—PartII:Logical 1.4 AComputerSystem 7 Operations 38 1.4.1 A(Very)LittleHistoryfora(Lot) 2.6.1 ALogicalVariable 38 BetterPerspective 8 2.6.2 TheANDFunction 38 1.4.2 ThePartsofaComputer 2.6.3 TheORFunction 39 System 10 2.6.4 TheNOTFunction 40 1.5 TwoVeryImportantIdeas 11 2.6.5 TheExclusive-ORFunction 40 1.6 ComputersasUniversal 2.6.6 DeMorgan’sLaws 41 ComputationalDevices 12 2.6.7 TheBitVector 42 1.7 HowDoWeGettheElectronstoDo 2.7 OtherRepresentations 43 theWork? 14 2.7.1 FloatingPointDataType(GreaterRange, 1.7.1 TheStatementoftheProblem 14 LessPrecision) 43 1.7.2 TheAlgorithm 16 2.7.2 ASCIICodes 47 1.7.3 TheProgram 16 2.7.3 HexadecimalNotation 48 1.7.4 TheISA 17 Exercises 49 1.7.5 TheMicroarchitecture 18 1.7.6 TheLogicCircuit 19 1.7.7 TheDevices 19 Exercises 20 3 Digital Logic Structures 59 3.1 TheTransistor 59 3.2 LogicGates 61 3.2.1 TheNOTGate(Inverter) 61 2 Bits, Data Types, 3.2.2 ORandNORGates 62 and Operations 25 3.2.3 WhyWeCan’tSimplyConnectP-Type 2.1 BitsandDataTypes 25 toGround 64 2.1.1 TheBitastheUnitofInformation 25 3.2.4 ANDandNANDGates 65 2.1.2 DataTypes 26 3.2.5 GateswithMoreThanTwoInputs 66 2.2 IntegerDataTypes 26 3.3 CombinationalLogicCircuits 67 2.2.1 UnsignedIntegers 26 3.3.1 Decoder 67 2.2.2 SignedIntegers 27 3.3.2 Mux 68 2.3 2’sComplementIntegers 29 3.3.3 AOne-BitAdder(a.k.a.aFullAdder) 69 viii Contents 3.3.4 TheProgrammableLogic 5.1.3 TheInstructionSet 147 Array(PLA) 71 5.1.4 Opcodes 149 3.3.5 LogicalCompleteness 72 5.1.5 DataTypes 149 3.4 BasicStorageElements 73 5.1.6 AddressingModes 150 3.4.1 TheR-SLatch 73 5.1.7 ConditionCodes 150 3.4.2 TheGatedDLatch 74 5.2 OperateInstructions 151 3.5 TheConceptofMemory 75 5.2.1 ADD,AND,andNOT 151 3.5.1 AddressSpace 75 5.2.2 Immediates 152 3.5.2 Addressability 76 5.2.3 TheLEAInstruction(AlthoughNotReally 3.5.3 A22-by-3-BitMemory 76 anOperate) 154 3.6 SequentialLogicCircuits 78 5.3 DataMovementInstructions 155 3.6.1 ASimpleExample:The 5.3.1 PC-RelativeMode 156 CombinationLock 79 5.3.2 IndirectMode 158 3.6.2 TheConceptofState 80 5.3.3 Base+offsetMode 159 3.6.3 TheFiniteStateMachineandIts 5.3.4 AnExample 160 StateDiagram 82 5.4 ControlInstructions 161 3.6.4 TheSynchronousFinite 5.4.1 ConditionalBranches 162 StateMachine 85 5.4.2 TwoMethodsofLoopControl 165 3.6.5 TheClock 86 5.4.3 TheJMPInstruction 169 3.6.6 Example:ADangerSign 87 5.4.4 TheTRAPInstruction 169 3.7 PreviewofComingAttractions:TheDataPath 5.5 AnotherExample:CountingOccurrences oftheLC-3 93 ofaCharacter 170 Exercises 95 5.6 TheDataPathRevisited 173 5.6.1 BasicComponentsofthe DataPath 175 4 The von Neumann Model 121 5.6.2 TheInstructionCycleSpecific 4.1 BasicComponents 121 totheLC-3 176 4.1.1 Memory 122 Exercises 177 4.1.2 ProcessingUnit 123 4.1.3 InputandOutput 124 6 Programming 203 4.1.4 ControlUnit 125 4.2 TheLC-3:AnExamplevon 6.1 ProblemSolving 203 NeumannMachine 125 6.1.1 SystematicDecomposition 203 4.3 InstructionProcessing 127 6.1.2 TheThreeConstructs:Sequential, 4.3.1 TheInstruction 127 Conditional,Iterative 204 4.3.2 TheInstructionCycle(NOTthe 6.1.3 LC-3ControlInstructionstoImplement ClockCycle!) 130 theThreeConstructs 205 4.3.3 ChangingtheSequenceof 6.1.4 TheCharacterCountExamplefrom Execution 132 Chapter5,Revisited 206 4.3.4 ControloftheInstructionCycle 134 6.2 Debugging 210 4.3.5 HaltingtheComputer(theTRAP 6.2.1 DebuggingOperations 211 Instruction) 136 6.2.2 UseofanInteractiveDebugger 212 4.4 OurFirstProgram:AMultiplication Exercises 220 Algorithm 137 Exercises 139 7 Assembly Language 231 7.1 AssemblyLanguageProgramming—Moving 5 The LC-3 145 UpaLevel 231 5.1 TheISA:Overview 145 7.2 AnAssemblyLanguageProgram 232 5.1.1 MemoryOrganization 146 7.2.1 Instructions 233 5.1.2 Registers 146 7.2.2 Pseudo-Ops(AssemblerDirectives) 236 Contents ix 7.2.3 Example:TheCharacterCountExample 9.2 Input/Output 317 ofSection5.5,RevisitedAgain! 238 9.2.1 SomeBasicCharacteristics 7.3 TheAssemblyProcess 240 ofI/O 317 7.3.1 Introduction 240 9.2.2 InputfromtheKeyboard 320 7.3.2 ATwo-PassProcess 240 9.2.3 OutputtotheMonitor 322 7.3.3 TheFirstPass:Creatingthe 9.2.4 AMoreSophisticatedInput SymbolTable 241 Routine 325 7.3.4 TheSecondPass:Generatingthe 9.2.5 ImplementationofMemory-Mapped MachineLanguageProgram 242 I/O,Revisited 326 7.4 BeyondtheAssemblyofaSingleAssembly 9.3 OperatingSystemServiceRoutines LanguageProgram 243 (LC-3TrapRoutines) 327 7.4.1 TheExecutableImage 244 9.3.1 Introduction 327 7.4.2 MorethanOneObjectFile 244 9.3.2 TheTrapMechanism 329 Exercises 245 9.3.3 TheTRAPInstruction 330 9.3.4 TheRTIInstruction:ToReturn ControltotheCalling 8 Data Structures 263 Program 331 8.1 Subroutines 263 9.3.5 ASummaryoftheTrapService 8.1.1 TheCall/ReturnMechanism 265 RoutineProcess 331 8.1.2 JSR(R)—TheInstructionThatCalls 9.3.6 TrapRoutinesforHandlingI/O 333 theSubroutine 266 9.3.7 ATrapRoutineforHalting 8.1.3 SavingandRestoringRegisters 267 theComputer 335 8.1.4 LibraryRoutines 269 9.3.8 TheTrapRoutineforCharacterInput 8.2 TheStack 273 (OneLastTime) 336 8.2.1 TheStack—AnAbstractDataType 273 9.3.9 PUTS:WritingaCharacterStringto 8.2.2 TwoExampleImplementations 273 theMonitor 338 8.2.3 ImplementationinMemory 274 9.4 InterruptsandInterrupt-DrivenI/O 339 8.2.4 TheCompletePicture 278 9.4.1 WhatIsInterrupt-DrivenI/O? 339 8.3 Recursion,aPowerfulTechniqueWhenUsed 9.4.2 WhyHaveInterrupt-DrivenI/O? 340 Appropriately 280 9.4.3 TwoPartstotheProcess 341 8.3.1 BadExampleNumber1:Factorial 280 9.4.4 PartI:CausingtheInterruptto 8.3.2 Fibonacci,anEvenWorse Occur 341 Example 285 9.4.5 PartII:HandlingtheInterrupt 8.3.3 TheMaze,aGoodExample 288 Request 344 8.4 TheQueue 294 9.4.6 AnExample 347 8.4.1 TheBasicOperations:Removefrom 9.4.7 NotJustI/ODevices 349 Front,InsertatRear 295 9.5 PollingRevisited,NowThatWeKnow 8.4.2 Wrap-Around 295 AboutInterrupts 350 8.4.3 HowManyElementsCanWeStore 9.5.1 TheProblem 350 inaQueue? 296 9.5.2 TheSolution 351 8.4.4 TestsforUnderflow,Overflow 297 Exercises 352 8.4.5 TheCompleteStory 298 8.5 CharacterStrings 300 Exercises 304 10 A Calculator 379 10.1 DataTypeConversion 380 9 I/O 313 10.1.1 Example:ABogusProgram: 9.1 Privilege,Priority,andtheMemory 2+3=e 381 AddressSpace 314 10.1.2 InputData(ASCIItoBinary) 381 9.1.1 PrivilegeandPriority 314 10.1.3 DisplayResult(Binary 9.1.2 OrganizationofMemory 316 toASCII) 385