Contents xi 4.3.2 SEQ Hardware Structure 396g).) 4.3.3 SEQ Timing 400 2子母 4.3.4 SEQ Stage Implementations 404 4.4 General Principles of Pipelining 4121,. 4.4.1 Computational Pipelines 412 4.4.2 A Detailed Look at Pipeline Operation 414 4.4.3 Limitations of Pipelining 416 4.4.4 rPipelining aSystem with Feedback 419 17 4.5 Pipelined Y86-64 Implementations.421 4.5.1 SEQ+:Rearranging the Computation Stages,421 4.5.2 Inserting.Pipeline Registers 422 4.5.3 Rearranging and Relabeling Signals 426 4.5.4 Next PC Prediction 427 4.5.5 Pipeline Hazards 429 4.5.6 Exception Handling 444 4.5.7 PIPE Stage Implementations 447 4.5.8 Pipeline Control Logic 455 4.5.9-Performance Analysis _464 4,5.10 Unfinished Business 468 4.6 Summary 470 4.6.1 Y86-64 Simulators 472 Bibliographic Notes 473 Homework Problems 473 Solutions to Practice Problems 480 5 Optimizing Program Performance:495 5.1 Capabilities and Limitations of Optimizing Compilers 498 5.2 Expressing Program Performance.502 53 Program Example 504 5.4 Eliminating Loop'Inefficiencies 508 5.5 Reducing Procedure Calls 512 .d 5.6 Eliminating Unneeded Memory References,514 5.7 Understanding Modern Processors 517. 5.7.1 Overall Operation 518 5.7.2 Functional Unit Performance 523 5.7.3 An Abstract Model of Processor Operation 525 5.8 Loop Unrolling 53br 59 Enhancing Parallelism 536 5.9.1 Multiple.Accumulators 536 5.9.2 Reassociation Transformation 541
4.3.2 SEQ Hardware Structure 396G0 . ,. '· ' • 1., • ·' 4.3.3 SEQ Timing 400 ·¥. " ,. '! n•J '"" 4.3.4 SEQ Stage Jmplementations 404 11"' ., ' 4.4 General Principles of Pipelining 412 , l" 4.4.1 Coi;nputat~onal Pipelines 412· '(It .t/ 4.4.2 A Detailed Look at Pipeline Operation,. il14l 4.4.3 Limit,atiqns of Pipelining 416 4.4.4 <•,l?ipelihingc.a'System with Feedback· 419 1 , :. 4.5 Pipelined Y86'64 Impleinentations• '421·tJ .·11< 4.5.l SEQ+: Rearranging the Computation Stagesu-.421 4.5.2 Insefting.Pipeline Registers 422 , .fi" 4.5.3 Rearranging and Relabeling Signals 426 4.5.4 Next PC Prediction 427 • > 4.5.5 Pipeline Hazards 429 4.5.6 Exception Handling 444 _, 4.5.7 PIPE Stage Implementations 447 4.5.8 Pipeline Control Logic 455 4.5.9 - Performance Analysis -464. 4,5.10 Unfinisped Business 468 4.6 Summary 470 5 4.6.1 Y86-64 Simulators 472 Bibliographic Notes 473 Homework Problems 473 Solutions to Practice Problems 480 . . ,, Optimizing Program'P'erforniqnc~; 495 5.1 5.2 5.3 5.4 5.5 5.6 5.7 Capabilities and Limitations· of Optimizing Compilers 1198 Expressing Program Performance. ·502 Program Example 504 Eliminating Loop•I:gefficiencies 508 .J• Reducing Procedure Calls 51'.Z.< '" " Eliminating Unneeded Memory Referencesu514 ... Understanding Modern Processors ·517,. 5.7.l Overall Operation 518 5.7.2 Functional Unit Performance 523 5.7.3 An Abstract Model of Processor Operation 525 5.8 Loop Unrolling 53.hr" "' 5.9 Enhanqing Parallelism 536 5.9.l Multiple.Accumulators 536 5.9.2 Reassociation Transformation 541 ~Contents xi
xii Contents 5.10 Summary of Results for Optimizing Combining Code 547 5.11 Some Limiting Factors 548 5.11.1 Register Spilling 548 5.11.2 Branch Prediction and.Misprediction Penalties549 5.12 Understanding Memory Performance 553 5.12.1 Load Performance 554ti 5.12.2 Store Performance 555 r 5.13 Life in the Real World:Performance'Improvement Techniques561 5.14 Identifying and Eliminating Performance Bottlenecks 562 5.14.1 Program Profiling 562 5.14.2 Using a Profiler to Guide Optimization 565 5.15 Summary 568 Bibliographic Notes 569 Homework Problems 570 Solutions to Practice Problems 573 6 The Memory Hierarchy 579 6.1 Storage Technologies 581 6.1.1 Random Access Memory 581 6.1.2 Disk Storage 589 6.1.3 Solid State Disks 600 6.1.4 Storage Technology Trends 602 6.2 Locality 604 6.2.1 Locality of References to Program Data 606 62.Locality of Instruction Fetche 6.2.3 Summary of Locality 608 6.3 The Memory Hierarchy 609 6.3.1 Caching in the Memory Hierarchy 610 6.3.2 Summary of Memory Hierarchy Concepts 614 6.4 Cache Memories 614 6.4.1 Generic Cache Memory Organization 615 6.4.2 Direct-Mapped Caches 617 6.4.3 Set Associative Caches 624 6.4.4 Fully Associative Caches 626 6.4.5 Issues with Writes 630 6.4.6 Anatomy of a Real Cache Hierarchy 631 6.4.7 Performance Impact of Cache Parameters 631 6.5 Writing Cache-Friendly Code 633 6.6 Putting It Together:The Impact of Caches on Program Performance 639
Xii Contents 5.10 Summary of Results for Optimizing Combining Code 547 5.11 Some Limiting Factors 548 5.11.1 Register Spilling 548 5.11.2 Branch Prediction and·Mispredictipn Penalties ·'549 5.12 Understanding Memory Performance 553 ,... •L 5.12.1 Load Performance 554'ri 1 d" 5.12.2 Store Performance 555 5.13 Life in the Real World: Performance"Improvement Techniques • 561 5.14 Identifying and Eliminating Performance Bottlenecks 562 5.14.1 Program Profiling 562 5.14.2 Using a Profiler to Guide Optimization 565 • 5.15 Summary 568 Bibliographic Notes 569 " Homework Problems 570 Solutions to Practice Problems 573 6 The Memory Hierarchy 579 6.1 Storage Technologies 581 6.1.1 Random Access Memory 581 6.1.2 Disk Storage 589 6.1.3 Solid State Disks 600 6.1.4 Storage Technology Trends 602 6.2 Locality 604 6.2.1 Locality of References to Program Data 606 6.2.2 Locality of Instruc,tion Fetche'l , 601 6.2.3 Summary of Locality 608 "' 6.3 The Memory Hierarchy 609 6.3.1 Caching in the Memory Hierarchy 610 6.3.2 Summary of Memory Hierarchy Concepts 614 6.4 Cache Memories 614 6.4.1 Generic Cache Memory Organization '615 6.4.2 Direct-Mapped Caches 617 " 6.4.3 Set Associative Cadres 624 " 6.4.4 Fully Associative Caches 626 6.4.5 Issues with Writes 630 6.4.6 Anatomy of a Real Cache Hierarchy 631 6.4.7 Performance Impact of Cache Parameters 631 6.5 Writing Cache-Friendly Code 633 6.6 Putting It Together: The Impact of Caches on Program Performance 639
Contents xiii 6.6.1 The Memory Mountain 639 6.6.2 Rearranging Loops to Increase Spatial Locality 643 6.6.3 Exploiting Locality in Your Prograrns '647 6.7 Summary 648 Bibliographic Notes 648 Homework Problems 649 Solutions to Practice Problems 660 Part Il Running Programs on a System 7 Linking 669 7.1 Compiler Drivers 671 7.2 Static Linking 672 7.3 Object Files 673 7.4 Relocatable Object Files 674 7.5 Symbols and Symbol.Tables 675 7.6 Symbol Resolution 679 7.6.1 How Linkers Resolve Duplicate Symbol Names 680 7.6.2 Linking with Static Libraries 684 7.6.3 How Linkers Use Static Libraries to Resolve References 688 7.7 Relocation 689 7.7.1 Relocation Entries 690 7.7.2 Relocating Symbol References 691 7.8 0 Executable Object Files 695 7.9 Loading Executable Object Files 697 7.10 Dynamic Linking with Shared Libraries 698 7.11 Loading and Linking Shared Libraries from Application's 701 7.12 Position-Independent Code(PIC)704 7.13 Library Interpositioning 707 7.13.1 Compile-Time Interpositioning 708 7.13.2 Link-Time Interpositioning 708 7.13.3 Run-Time Interpositioning 710 7.14 Tools for Manipulating Object Files 713 715 Summary 713 Bibliographic Notes 714 Homework Problems 714 Solutions to Practice Problems 717
6.6.1 The Memory Mountain 639 6.6.2 Rearranging Loops to Increase Spatial Locality 643 6.6.3 Exploiting Locality in Your Programs '647 6.7 Summary 648 Bibliographic Notes 648 ' Homework' Problems 649 Solutions to Practice Problems 660 ' Part II Running Programs on a System 7 Linking 669 7.1 Compiler Drivers 671 7.2 Static Linking 672 7.3 Object Files 673 7.4 Relocatable Object Files 674 7.5 SY1Pbols and Symbol.Tables 675 7.6 Symbol Resolution 679 7.6.1 How Linkers Resolve Duplicate Symbol Names 680 7.6.2 Linking with Static Libraries 684 7.6.3 How Linkers Use Static Libraries to Resolve References 688 7.7 Relocation 689 7.7.1 Relocation Entries 690 7.7.2 Relocating Symbol References 691 7.8 d Executable Object Files 695 7.9 Loading Executable Object Files 697 7.10 Dynamic Linking with Shared Libraries 698 ' . 7.11 Loading and Linking Shared Libraries from Applications 701 7.12 Position-Independent Code (PIC) 704 7.13 Library Interpositioning 707 7.13.1 Compile-Time Interpositioning 708 7.13.2 Link-Time Interpositioning 708 7.13.3 Run-Time Interpositioning 710 7.14 Tools for Manipulating Object Files 713 7.15 Summary 713 Bibliographic Notes 714 Homework Problems 714 Solutions to Practice Problems 717 Contents xiii
xiv Contents 8 Exceptional Control Flow 721 8.1 Exceptions 723 8.1.1 Exception Handling 724 8.1.2 Classes of Exceptions 726 8.1.3 Exceptions in Linux/x86-64 Systems 729 8.2 Processes 732 8.2.1 Logical Controt Flow 732 8.2.2 Concurrent Flows 733 8.2.3 Private Address Space 734 8.2.4 User and Kernel Modes 734 8.2.5 Context Switches 736 83 System Call Error Handling 737 8.4 Process Control 738 8.4.1 Obtaining Process IDs 739 8.4.2 Creating and Terminating Processes 739 8.4.3 Reaping Child Processes 743 8.4.4 Putting Processes to Sleep 749 8.4.5 Loading and Running Programs 750 8.4.6 Using fork and execve to Run Programs 753 8.5 Signals 756 8.5.1 Signal Terminology 758 8.5.2 Sending Signals 759 8.5.3 Receiving Signals 762 8.5.4 Blocking and Unblocking Signals 764 8.5.5 Writing Signal Handlers 766 9 8.5.6 Synchronizing Flows to Avoid Nasty.Concurrency Bugs 776 8.5.7 Explicitly Waiting for Signals 778 8.6 Nonlocal Jumps 781 8.7 Tools for Manipulating Processes 786 8.8 Summary 787 Bibliographic Notes 787 Homework Problems 788 Solutions to Practice Problems 795 9 Virtual Memory 801 9.1 Physical and Virtual Addressing 803 9.2 Address Spaces 804
xiv Contents 8 Exceptional Control Flow" 721 8.1 8.2 8:3 8.4 8.5 8.6 8.7 8.8 9 Exceptions 723 8.1.1 Exception Handling 724 8.1.2 Classes of Exceptions 726 8.1.3 Exceptions in Linux/x86-64 Systems Processes 732 8·.2.1 Logical ControfFlow 732 8.2.2 Concurrent Flows 733 8.2.3 Private Address Space 734 8.2.4 User and Kernel Modes 734 8.2.5 Context Switches 736 System Call Error Handling 737 Process Control 738 8.4.1 Obtaining Process IDs 739 729 8.4.2 Creating and Terminating Processes 739 8.4.3 Reaping Child Processes 743 8.4.4 Putting Processes to Sleep 749 , 8.4.5 Loading and Running Programs 750 8.4.6 Using fork and execve to Run Programs 753 Signals 756 8.5.1 Signal Terminology 758 8.5.2 Sending Signals 759 8.5.3 Receiving Signals 762 8.5.4 Blocking and Unblocking Signals 764 8.5.5 Writing Signal Handlers 766 11 8.5.6 Synchronizing Flows to Avoid Nasty. Concurrency Bugs 8.5.7 Explicitly Waiting fat Signals 778 Nonlocal Jumps 781 Tools for Manipula\ing Processes. 786 Summary 787 , Bibliographic Notes 787 Homework Problems 788 Solutions to Practice Problems 795 Virtual Memory 801 9.1 Physical and Virtual Addressing 8Q3 9.2 Address Spaces 804 776
Gontents xv 93 VM as a Tool for Caching 805 9.3.1 DRAM Cache Organization 806 9.3.2 Page Tables 806 9.3.3 Page Hits,808 9.3.4 Page Faults808’ 9.3.5 Allocating Pages 810 9.3.6 Locality to the Rescue Again 810 9.4 VM as a Tool for Memory Management 811 9.5 VM as a Tool for Memory Protection .812 9.6 Address Translation 813 .I 9.6.1 Integrating Caches and VM 817 9.6.2 Speeding Up Address Translation with a TLB 817 9.6.3 Multi-Level Page Tables 819 9.6.4 Putting It Together:End-to-End Address Translation 821 9.7 Case Study:The Intel Core i7/Linux Memory System 825 9.7.1 Core i7 Address Translation 826 9.7.2 Linux Virtual Memory System 828 9.8 Memory Mapping 833 9.8.1 Shared Objects Revisited 833 9.8.2 The fork Function Revisited 836 9.8.3 The execve Function Revisited 836 9.8.4 User-Level Memory Mapping with the mmap Function 837 9.9 Dynamic Memory Allocation 839 9.9.1 The malloc and free Functions 840 1 9.9.2 Why Dynamic Memory Allocation?843 9.9.3 Allocator Requirements and Goals 844 9.9.4 Fragmentation 846 9.9.5 Implementation Issues 846 1 9.9.6 Implicit Free Lists 847 9.9.7 Placing Allocated Blocks 849 9.9.8 Splitting.Free Blocks 849 9.9.9 Getting Additional Heap Memory 850 9.9.10 Coalescing Free Blocks 850 9.9.11 Coalescing with Boundary Tags 851 9.9.12 Putting It Together:Implementing a Simple Allocator 854 9.9.13 Explicit Free Lists 862 9.9.14 Segregated Free Lists 863 9.10 Garbage Collection 865' 9.10.1 Garbage Collector Basics 866 9.10.2 Mark&Sweep Garbage Collectors 867 二 9.10.3 Conservative Mark&Sweep for C Programs 869
9.3 VM as a Tool f6r Caching 805 9.3.1 DRAM Cache Organization 806 9.3.2 Page Tables 806 9.3.3 Page Hits, 808 9.3.4 Page Faults 808- 1 9.3.5 Allocating Pages 810 9.3.6 Locality to the Rescue Again 810 9.4 VM as \I Tool fdr Memory Management 811 9.5 VM as a Tool for Mem'ofy Protection .812 9.6 Address Translation 813 9.6.l Integrati~g Caches andYM 817 9.6.2 Speeding Up Address 'Ifanslation with a TLB 817 9.6.3 Multi-Level Page Tables 819 ( ' 9.6.4 Putting It Together: End-to-End Addrl',s~ Trapslation ~21 9.7 Case Study: The Intel Core i7/Linux Memory System 825 9.7.1 Core i7 Address Translation 826 9.7.2 Linux Virtual Memory System 828 9.8 Memory Mapping 833 9.8.1 Shared Objects Revisited 833 9.8.2 The fork Function Revisited 836 9.8.3 The execve Function Revisited 836 9.8.4 User-Level Memory Mapping with the mmap Function 837 9.9 Dynamic Memory Alloqtion 839 9.9.l 9.9.2 9.9.3 9.9.4 9.9.5 9.9.6 9.9.7 9.9.8 9.9.9 9.9.10 9.9.11 9.9.12 9.9.13 9.9.14 The malloc and free Functions ~40 Why Dynamic Memory Allocation? 843 Allocator Requirements and Goals 844 Fragmentation 846 Implementation Issues 846 Implicit Free Lists 847 Pl~cing Allocated Blocks 849 Splitting· Free Blocks -849' 1 L ' Getting Additional Heap Memory '850 Coalescing Free Blocks 850 Coalescing with Boundary Tags 851 Putting It Together: Implementing a Simple Allocator Explicit Free Lists 862 S_egregated Free Lists 863 9.10 Garbage Collection 865' 9.10.l Garbage Collector Basics 866 9.10.2 Mark&Sweep Garbage Collectors 867 · • 9.10.3 Conservative Mark&Sweep for C Programs 869 ., " 854 h ' I .. ~ .. Gontents xv