Computer System Design

Michael J. Flynn, Emeritus Professor of Electrical Engineering at Stanford University, is Chairman of the Board and Senior Advisor to Maxeler Technologies. Previously, he worked at IBM in the areas of computer organization and design. His best-known technical work includes the SIMD/MIMD classification of computer organization, and the first detailed discussion of superscalar design. Professor Flynn is a Fellow of the IEEE and a Fellow of the ACM. Wayne Luk is Professor of Computer Engineering in the Department of Computing at Imperial College London, where he teaches computer architecture and custom computing. He leads the Computer Systems Section as well as the Custom Computing Research Group, which is currently focusing on theory and practice of reconfigurable systems and their design automation. He has worked with many companies including Altera, J.P. Morgan, Nokia, Sharp, Sony, and Xilinx. Professor Luk is a Fellow of the IEEE and a Fellow of the BCS.

• Preface xiii List of Abbreviations and Acronyms xvii1 Introduction to the Systems Approach 11.1 System Architecture: An Overview 11.2 Components of the System: Processors, Memories, and Interconnects 21.3 Hardware and Software: Programmability Versus Performance 51.4 Processor Architectures 71.4.1 Processor: A Functional View 81.4.2 Processor: An Architectural View 91.5 Memory and Addressing 191.5.1 SOC Memory Examples 201.5.2 Addressing: The Architecture of Memory 211.5.3 Memory for SOC Operating System 221.6 System-Level Interconnection 241.6.1 Bus-Based Approach 241.6.2 Network-on-Chip Approach 251.7 An Approach for SOC Design 261.7.1 Requirements and Specifi cations 261.7.2 Design Iteration 271.8 System Architecture and Complexity 291.9 Product Economics and Implications for SOC 311.9.1 Factors Affecting Product Costs 311.9.2 Modeling Product Economics and Technology Complexity: The Lesson for SOC 331.10 Dealing with Design Complexity 341.10.1 Buying IP 341.10.2 Reconfi guration 351.11 Conclusions 371.12 Problem Set 382 Chip Basics: Time, Area, Power, Reliability, and Confi gurability 392.1 Introduction 392.1.1 Design Trade-Offs 392.1.2 Requirements and Specifi cations 422.2 Cycle Time 432.2.1 Defi ning a Cycle 432.2.2 Optimum Pipeline 442.2.3 Performance 462.3 Die Area and Cost 472.3.1 Processor Area 472.3.2 Processor Subunits 502.4 Ideal and Practical Scaling 532.5 Power 572.6 Area–Time–Power Trade-Offs in Processor Design 602.6.1 Workstation Processor 602.6.2 Embedded Processor 612.7 Reliability 622.7.1 Dealing with Physical Faults 622.7.2 Error Detection and Correction 652.7.3 Dealing with Manufacturing Faults 682.7.4 Memory and Function Scrubbing 692.8 Confi gurability 692.8.1 Why Reconfi gurable Design? 692.8.2 Area Estimate of Reconfi gurable Devices 702.9 Conclusion 712.10 Problem Set 713 Processors 743.1 Introduction 743.2 Processor Selection for SOC 763.2.1 Overview 763.2.2 Example: Soft Processors 763.2.3 Examples: Processor Core Selection 793.3 Basic Concepts in Processor Architecture 813.3.1 Instruction Set 813.3.2 Some Instruction Set Conventions 823.3.3 Branches 823.3.4 Interrupts and Exceptions 843.4 Basic Concepts in Processor Microarchitecture 863.5 Basic Elements in Instruction Handling 883.5.1 The Instruction Decoder and Interlocks 883.5.2 Bypassing 903.5.3 Execution Unit 903.6 Buffers: Minimizing Pipeline Delays 913.6.1 Mean Request Rate Buffers 913.6.2 Buffers Designed for a Fixed or Maximum Request Rate 923.7 Branches: Reducing the Cost of Branches 933.7.1 Branch Target Capture: Branch Target Buffers (BTBs) 943.7.2 Branch Prediction 973.8 More Robust Processors: Vector, Very Long Instruction Word (VLIW), and Superscalar 1013.9 Vector Processors and Vector Instruction Extensions 1013.9.1 Vector Functional Units 1033.10 VLIW Processors 1073.11 Superscalar Processors 1083.11.1 Data Dependencies 1093.11.2 Detecting Instruction Concurrency 1103.11.3 A Simple Implementation 1123.11.4 Preserving State with Out-of-Order Execution 1163.12 Processor Evolution and Two Examples 1183.12.1 Soft and Firm Processor Designs: The Processor as IP 1183.12.2 High-Performance, Custom-Designed Processors 1183.13 Conclusions 1193.14 Problem Set 1204 Memory Design: System-on-Chip and Board-Based Systems 1234.1 Introduction 1234.2 Overview 1254.2.1 SOC External Memory: Flash 1254.2.2 SOC Internal Memory: Placement 1264.2.3 The Size of Memory 1274.3 Scratchpads and Cache Memory 1284.4 Basic Notions 1294.5 Cache Organization 1304.6 Cache Data 1334.7 Write Policies 1344.8 Strategies for Line Replacement at Miss Time 1354.8.1 Fetching a Line 1364.8.2 Line Replacement 1364.8.3 Cache Environment: Effects of System, Transactions, and Multiprogramming 1374.9 Other Types of Cache 1384.10 Split I- and D-Caches and the Effect of Code Density 1384.11 Multilevel Caches 1394.11.1 Limits on Cache Array Size 1394.11.2 Evaluating Multilevel Caches 1404.11.3 Logical Inclusion 1434.12 Virtual-to-Real Translation 1434.13 SOC (On-Die) Memory Systems 1454.14 Board-based (Off-Die) Memory Systems 1474.15 Simple DRAM and the Memory Array 1494.15.1 SDRAM and DDR SDRAM 1524.15.2 Memory Buffers 1564.16 Models of Simple Processor–Memory Interaction 1564.16.1 Models of Multiple Simple Processors and Memory 1574.16.2 The Strecker-Ravi Model 1584.16.3 Interleaved Caches 1604.17 Conclusions 1614.18 Problem Set 1615 Interconnect 1655.1 Introduction 1655.2 Overview: Interconnect Architectures 1665.3 Bus: Basic Architecture 1685.3.1 Arbitration and Protocols 1705.3.2 Bus Bridge 1715.3.3 Physical Bus Structure 1715.3.4 Bus Varieties 1725.4 SOC Standard Buses 1735.4.1 AMBA 1745.4.2 CoreConnect 1775.4.3 Bus Interface Units: Bus Sockets and Bus Wrappers 1795.5 Analytic Bus Models 1835.5.1 Contention and Shared Bus 1835.5.2 Simple Bus Model: Without Resubmission 1845.5.3 Bus Model with Request Resubmission 1855.5.4 Using the Bus Model: Computing the Offered Occupancy 1855.5.5 Effect of Bus Transactions and Contention Time 1865.6 Beyond the Bus: NOC with Switch Interconnects 1875.6.1 Static Networks 1905.6.2 Dynamic Networks 1925.7 Some NOC Switch Examples 1945.7.1 A 2-D Grid Example of Direct Networks 1945.7.2 Asynchronous Crossbar Interconnect for Synchronous SOC (Dynamic Network) 1965.7.3 Blocking versus Nonblocking 1975.8 Layered Architecture and Network Interface Unit 1975.8.1 NOC Layered Architecture 1985.8.2 NOC and NIU Example 2005.8.3 Bus versus NOC 2015.9 Evaluating Interconnect Networks 2015.9.1 Static versus Dynamic Networks 2025.9.2 Comparing Networks: Example 2045.10 Conclusions 2055.11 Problem Set 2066 Customization and Confi gurability 2086.1 Introduction 2086.2 Estimating Effectiveness of Customization 2096.3 SOC Customization: An Overview 2106.4 Customizing Instruction Processors 2126.4.1 Processor Customization Approaches 2146.4.2 Architecture Description 2156.4.3 Identifying Custom Instructions Automatically 2176.5 Reconfi gurable Technologies 2186.5.1 Reconfi gurable Functional Units (FUs) 2186.5.2 Reconfi gurable Interconnects 2226.5.3 Software Confi gurable Processors 2246.6 Mapping Designs Onto Reconfi gurable Devices 2266.7 Instance-Specifi c Design 2286.8 Customizable Soft Processor: An Example 2316.9 Reconfi guration 2356.9.1 Reconfi guration Overhead Analysis 2356.9.2 Trade-Off Analysis: Reconfi gurable Parallelism 2376.10 Conclusions 2426.11 Problem Set 2437 Application Studies 2467.1 Introduction 2467.2 SOC Design Approach 2467.3 Application Study: AES 2517.3.1 AES: Algorithm and Requirements 2517.3.2 AES: Design and Evaluation 2537.4 Application Study: 3-D Graphics Processors 2547.4.1 Analysis: Processing 2557.4.2 Analysis: Interconnection 2597.4.3 Prototyping 2607.5 Application Study: Image Compression 2627.5.1 JPEG Compression 2627.5.2 Example JPEG System for Digital Still Camera 2647.6 Application Study: Video Compression 2667.6.1 MPEG and H.26X Video Compression: Requirements 2687.6.2 H.264 Acceleration: Designs 2717.7 Further Application Studies 2767.7.1 MP3 Audio Decoding 2767.7.2 Software-Defi ned Radio with 802.16 2797.8 Conclusions 2817.9 Problem Set 2828 What's Next: Challenges Ahead 2858.1 Introduction 2858.2 Overview 2868.3 Technology 2888.4 Powering the ASOC 2898.5 The Shape of the ASOC 2928.6 Computer Module and Memory 2938.7 RF or Light Communications 2938.7.1 Lasers 2948.7.2 RF 2958.7.3 Potential for Laser/RF Communications 2958.7.4 Networked ASOC 2968.8 Sensing 2968.8.1 Visual 2968.8.2 Audio 2978.9 Motion, Flight, and the Fruit Fly 2988.10 Motivation 2998.11 Overview 3008.12 Pre-Deployment 3028.13 Post-Deployment 3078.13.1 Situation-Specifi c Optimization 3088.13.2 Autonomous Optimization Control 3098.14 Roadmap and Challenges 3108.15 Summary 312Appendix: Tools for Processor Evaluation 313References 316Index 329