Computer Science and Engineering Handbook

Computer Science Handbook: Second Edition 1 Preface to the Second Edition 3 Editor-in-Chief 5 Contributors 6 Contents 10 Chapter 1: Computer Science:The Discipline and its Impact 18 1.1 Introduction 18 1.2 Growth of the Discipline and the Profession 19 1.2.1 Curriculum Development 20 1.2.2 Growth of Academic Programs 21 1.2.3 Academic R&D and Industry Growth 22 1.3 Perspectives in Computer Science 23 1.4 Broader Horizons: From HPCC to Cyberinfrastructure 24 1.5 Organization and Content 27 1.5.1 Algorithms and Complexity 28 1.5.2 Architecture 28 1.5.3 Computational Science 29 1.5.4 Graphics and Visual Computing 29 1.5.5 Human–Computer Interaction 29 1.5.6 Information Management 30 1.5.7 Intelligent Systems 30 1.5.8 Net-Centric Computing 30 1.5.9 Operating Systems 31 1.5.10 Programming Languages 31 1.5.11 Software Engineering 31 1.6 Conclusion 32 References 32 Chapter 2: Ethical Issues for Computer Scientists 34 2.1 Introduction: Why a Chapter on Ethical Issues? 34 2.2 Ethics in General 36 2.2.1 Utilitarianism 36 2.2.2 Deontological Theories 37 2.2.3 Social Contract Theories 38 2.2.4 A Paramedic Method for Computer Ethics 39 2.2.5 Easy and Hard Ethical Decision Making 40 2.3 Professional Ethics 40 2.4 Ethical Issues That Arise from Computer Technology 42 2.4.1 Privacy 43 2.4.2 Property Rights and Computing 44 2.4.3 Risk, Reliability, and Accountability 44 2.4.4 Rapidly Evolving Globally Networked Telecommunications 45 2.5 Final Thoughts 45 References 45 Section I: Algorithms and Complexity 46 Chapter 3: Basic Techniques for Design and Analysis of Algorithms 48 3.1 Introduction 48 3.2 Analyzing Algorithms 48 3.2.1 Linear Recurrences 49 3.2.2 Divide-and-Conquer Recurrences 51 3.3 Some Examples of the Analysis of Algorithms 52 3.3.1 Sorting 52 3.3.2 Priority Queues 54 3.4 Divide-and-Conquer Algorithms 57 3.5 Dynamic Programming 59 3.6 Greedy Heuristics 64 References 68 Chapter 4: Data Structures 69 4.1 Introduction 69 4.1.1 Containers, Elements, and Positions or Locators 69 4.1.2 Abstract Data Types 70 4.1.3 Main Issues in the Study of Data Structures 70 4.1.3.1 Static vs. Dynamic 70 4.1.3.2 Implicit vs. Explicit 70 4.1.3.3 Internal vs. External Memory 70 4.1.3.4 Space vs. Time 70 4.1.3.5 Theory vs. Practice 71 4.1.4 Fundamental Data Structures 71 4.1.4.1 Sequence 71 4.1.4.2 Priority Queue 71 4.1.4.3 Dictionary 71 4.1.5 Organization of the Chapter 72 4.2 Sequence 72 4.2.1 Introduction 72 4.2.2 Operations 72 4.2.3 Implementation with an Array 73 4.2.4 Implementation with a Singly Linked List 73 4.2.5 Implementation with a Doubly Linked List 73 4.3 Priority Queue 74 4.3.1 Introduction 74 4.3.2 Operations 74 4.3.3 Realization with a Sequence 75 4.3.3.1 Unsorted Sequence 75 4.3.3.2 Sorted Sequence 75 4.3.3.3 Sorting 75 4.3.4 Realization with a Heap 76 4.3.4.1 Operation INSERT 77 4.3.4.2 Operation REMOVEMAX 78 4.3.4.3 Operation REMOVE 78 4.3.4.4 Time Complexity 79 4.3.4.5 Sorting 79 4.3.5 Realization with a Dictionary 80 4.4 Dictionary 80 4.4.1 Operations 80 4.4.2 Realization with a Sequence 81 4.4.2.1 Unsorted Sequence 81 4.4.2.2 Sorted Sequence 81 4.4.2.3 Sorted Array 82 4.4.3 Realization with a Search Tree 83 4.4.3.1 Operation FIND 83 4.4.3.2 Operation INSERT 84 4.4.3.3 Operation REMOVE 85 4.4.4 Realization with an 85 4.4.4.1 Insertion 86 4.4.4.2 Deletion 88 4.4.4.3 Complexity 88 4.4.5 Realization with an AVL-Tree 88 4.4.5.1 Insertion 90 4.4.5.2 Rebalancing 91 4.4.5.3 Deletion 91 4.4.5.4 Complexity 93 4.4.6 Realization with a Hash Table 93 4.4.6.1 Bucket Array 93 4.4.6.2 Hashing 93 Acknowledgments 95 Defining Terms 95 References 95 Further Information 97 Chapter 5: Complexity Theory 98 5.1 Introduction 98 5.2 Models of Computation 99 5.2.1 Computational Problems and Languages 99 5.2.2 Turing Machines 100 5.2.3 Universal Turing Machines 101 5.2.4 Alternating Turing Machines 102 5.2.5 Oracle Turing Machines 102 5.3 Resources and Complexity Classes 102 5.3.1 Time and Space 103 5.3.2 Complexity Classes 120 5.4 Relationships between Complexity Classes 105 5.4.1 Constructibility 105 5.4.2 Basic Relationships 106 5.4.3 Complementation 107 5.4.4 Hierarchy Theorems and Diagonalization 107 5.4.5 Padding Arguments 108 5.5 Reducibility and Completeness 109 5.5.1 Resource-Bounded Reducibilities 111 5.5.2 Complete Languages 111 5.5.3 Cook-Levin Theorem 111 5.5.4 Proving NP-Completeness 112 5.5.5 Complete Problems for Other Classes 114 5.6 Relativization of the P vs. NP Problem 114 5.7 The Polynomial Hierarchy 115 5.8 Alternating Complexity Classes 116 5.9 Circuit Complexity 117 5.10 Probabilistic Complexity Classes 119 5.11 Interactive Models and Complexity Classes 120 5.11.1 Interactive Proofs 120 5.11.2 Probabilistically Checkable Proofs 122 5.12 Kolmogorov Complexity 122 5.13 Research Issues and Summary 123 Further Information 126 Acknowledgments 124 Defining Terms 124 References 124 Chapter 6: Formal Models and Computability 128 6.1 Introduction 128 6.2 Computability and a Universal Algorithm 129 6.2.1 Some Computational Problems 130 6.2.1.1 Table Lookup 132 6.2.1.2 Bounding the Search Domain 132 6.2.1.3 Use of Subroutines 132 6.2.2 A Universal Algorithm 133 6.3 Undecidability 134 6.3.1 Diagonalization and Self-Reference 134 6.3.2 Reductions and More Undecidable Problems 136 6.4 Formal Languages and Grammars 138 6.4.1 Representation of Languages 139 6.4.2 Hierarchy of Grammars 143 6.4.3 Context-Free Grammars and Parsing 145 6.5 Computational Models 149 6.5.1 Finite Automata 149 6.5.2 Turing Machines 154 6.5.2.1 Time and Space Complexity 156 6.5.2.2 Other Computing Models 157 Acknowledgment 158 Defining Terms 158 References 159 Further Information 160 Chapter 7: Graph and Network Algorithms 162 7.1 Introduction 162 7.2 Tree Traversals 163 7.3 Depth-First Search 164 7.3.1 The Depth-First Search Algorithm 164 7.3.2 Sample Execution 165 7.3.3 Analysis 165 7.3.4 Directed Depth-First Search 166 7.3.5 Sample Execution 166 7.3.6 Applications of Depth-First Search 166 7.4 Breadth-First Search 167 7.4.1 Sample Execution 167 7.4.2 Analysis 168 7.5 Single-Source Shortest Paths 168 7.5.1 Dijkstra’s Algorithm 168 7.5.1.1 Sample Execution 169 7.5.1.2 Analysis 169 7.5.2 Bellman–Ford Algorithm 169 7.6 Minimum Spanning Trees 170 7.6.1 Prim’s Algorithm 170 7.6.1.1 Analysis 171 7.6.2 Kruskal’s Algorithm 171 7.6.2.1 Analysis 171 7.7 Matchings and Network Flows 172 7.7.1 Matching Problem Definitions 172 7.7.2 Applications of Matching 173 7.7.3 Matchings and Augmenting Paths 173 7.7.4 Bipartite Matching Algorithm 174 7.7.4.1 High-Level Description 174 7.7.4.2 Sample Execution 175 7.7.4.3 Analysis 175 7.7.5 Assignment Problem 175 7.7.5.1 High-Level Description 177 7.7.6 B-Matching Problem 177 7.7.7 Network Flows 178 7.7.8 Network Flow Problem Definitions 179 7.7.9 Blocking Flows 180 7.7.10 Applications of Network Flow 181 7.8 Tour and Traversal Problems 181 Acknowledgments 181 Defining Terms 182 References 182 Further Information 183 Chapter 8: Algebraic Algorithms 185 8.1 Introduction 185 8.2 Matrix Computations and Approximation of Polynomial Zeros 185 8.2.1 Products of Vectors and Matrices, Convolution of Vectors 186 8.2.2 Some Computations Related to Matrix Multiplication 187 8.2.3 Gaussian Elimination Algorithm 188 8.2.4 Singular Linear Systems of Equations 188 8.2.5 Sparse Linear Systems (Including Banded Systems), Direct and Iterative Solution Algorithms 189 8.2.6 Dense and Structured Matrices and Linear Systems 189 8.2.7 Parallel Matrix Computations 189 8.2.8 Rational Matrix Computations, Computations in Finite Fields and Semirings 190 8.2.9 Matrix Eigenvalues and Singular Values Problems 190 8.2.10 Approximating Polynomial Zeros 192 8.2.11 Fast Fourier Transform and Fast Polynomial Arithmetic 193 8.3 Systems of Nonlinear Equations and Other Applications 194 8.3.1 Resultant Methods 194 8.3.2 Grobner Bases 196 8.4 Polynomial Factorization 198 8.4.1 Polynomials in a Single Variable over a Finite Field 199 8.4.2 Polynomials in a Single Variable over Fields of Characteristic Zero 200 8.4.3 Polynomials in Two Variables 201 8.4.4 Polynomials in Many Variables 202 Acknowledgment 203 Defining Terms 203 References 203 Further Information 208 Chapter 9: Cryptography 209 9.1 Introduction 209 9.2 Cryptographic Notions of Security 210 9.2.1 Information-Theoretic Notions of Security 210 9.2.2 Toward a Computational Notion of Security 211 9.2.3 Notation 212 9.3 Building Blocks 212 9.3.1 One-Way Functions 213 9.3.2 Trapdoor Permutations 214 9.3.2.1 RSA 214 9.3.2.2 A Trapdoor Permutation Based on Factoring [42] 215 9.4 Cryptographic Primitives 215 9.4.1 Pseudorandom Generators 216 9.4.2 Pseudorandom Functions and Block Ciphers 217 9.4.3 Cryptographic Hash Functions 218 9.5 Private-Key Encryption 219 9.6 Message Authentication 222 9.7 Public-Key Encryption 223 9.8 Digital Signature Schemes 225 Defining Terms 228 References 228 Further Information 230 Chapter 10: Parallel Algorithms 232 10.1 Introduction 232 10.2 Modeling Parallel Computations 233 10.2.1 Multiprocessor Models 233 10.2.1.1 Network Topology 234 10.2.1.2 Primitive Operations 237 10.2.2 Work-Depth Models 238 10.2.3 Assigning Costs to Algorithms 239 10.2.4 Emulations Among Models 239 Theorem 10.1 (Brent’s theorem) 239 10.1 239 Theorem 10.2 240 10.2.5 Model Used in This Chapter 241 10.3 Parallel Algorithmic Techniques 242 10.3.1 Divide-and-Conquer 242 10.3.2 Randomization 244 10.3.2.1 Sampling 244 10.3.2.2 Symmetry Breaking 244 10.3.2.3 Load Balancing 244 10.3.3 Parallel Pointer Techniques 244 10.3.3.1 Pointer Jumping 245 10.3.3.2 Euler Tour 245 10.3.3.3 Graph Contraction 245 10.3.3.4 Ear Decomposition 245 10.3.4 Other Techniques 245 10.4 Basic Operations on Sequences, Lists, and Trees 245 10.4.1 Sums 246 10.4.2 Scans 246 10.4.3 Multiprefix and Fetch-and-Add 247 10.4.4 Pointer Jumping 247 10.4.5 List Ranking 247 10.4.6 Removing Duplicates 248 10.4.6.1 Approach 1: Using an Array of Flags 248 10.4.6.2 Approach 2: Hashing 249 10.5 Graphs 250 10.5.1 Graphs and Their Representation 250 10.5.2 Breadth-First Search 251 10.5.3 Connected Components 253 10.5.3.1 Random Mate Graph Contraction 253 10.5.3.2 Deterministic Graph Contraction 255 10.5.3.3 Improved Versions of Connected Components 257 10.5.3.4 Extensions to Spanning Trees and Minimum Spanning Trees 257 10.6 Sorting 259 10.6.1 QuickSort 259 10.6.2 Radix Sort 259 10.7 Computational Geometry 260 10.7.1 Closest Pair 261 10.7.2 Planar Convex Hull 262 10.7.2.1 QuickHull 263 10.7.2.2 MergeHull 264 10.8 Numerical Algorithms 266 10.8.1 Matrix Operations 267 10.8.2 Fourier Transform 267 10.9 Parallel Complexity Theory 268 Defining Terms 268 References 269 Chapter 11: Computational Geometry 273 11.1 Introduction 273 11.2 Problem Solving Techniques 274 11.2.1 Incremental Construction 274 Theorem 11.1 274 11.2.2 Plane Sweep 275 Theorem 11.2 276 11.2.3 Geometric Duality 276 11.2.4 Locus 277 11.2.5 Divide-and-Conquer 277 Theorem 11.3 278 11.2.6 Prune-and-Search 279 Theorem 11.4 280 11.2.7 Dynamization 280 Definition 11.1 280 Theorem 11.5 281 Corollary 11.1 281 11.2.8 Random Sampling 281 11.3 Classes of Problems 282 11.3.1 Convex Hull 283 11.3.1.1 Convex Hulls in Two and Three Dimensions 283 11.3.1.2 Convex Hulls in 284 11.3.2 Proximity 284 11.3.2.1 Closest Pair 284 11.3.2.2 Bichromatic Closest Pair 285 11.3.2.3 Voronoi Diagrams 286 11.3.2.4 Farthest-Neighbor Voronoi Diagram 287 11.3.2.5 Weighted Voronoi Diagrams 287 11.3.2.6 Other Generalizations 289 11.3.3 Point Location 289 11.3.4 Motion Planning: Path Finding Problems 290 11.3.4.1 Path Finding in Two Dimensions 290 11.3.4.2 Path Finding in Three Dimensions 291 11.3.4.3 Motion Planning of Objects 291 11.3.5 Geometric Optimization 292 11.3.5.1 Minimum Cost Spanning Trees 292 11.3.5.2 Minimum Diameter Spanning Tree 292 11.3.5.3 Minimum Enclosing Circle Problem 292 11.3.5.4 Largest Empty Circle Problem 293 11.3.5.5 Minimum Annulus Covering Problem 293 11.3.6 Decomposition 293 11.3.6.1 Triangulation 293 11.3.6.2 Other Decompositions 294 11.3.7 Intersection 295 11.3.7.1 Intersection Detection Problems 295 11.3.7.2 Intersection Reporting/Counting Problems 295 11.3.7.3 Intersection Computation 296 11.3.8 Geometric Searching 296 11.3.8.1 Range Searching Problems 297 11.3.8.2 Other Range Searching Problems 297 11.4 Conclusion 298 Acknowledgment 298 References 298 Further Information 303 Chapter 12: Randomized Algorithms 304 12.1 Introduction 304 12.2 Sorting and Selection by Random Sampling 305 12.2.1 Randomized Selection 306 12.3 A Simple Min-Cut Algorithm 307 12.3.1 Classification of Randomized Algorithms 309 12.4 Foiling an Adversary 309 12.5 The Minimax Principle and Lower Bounds 310 12.5.1 Lower Bound for Game Tree Evaluation 311 12.6 Randomized Data Structures 312 12.7 Random Reordering and Linear Programming 316 12.8 Algebraic Methods and Randomized Fingerprints 318 12.8.1 Freivalds’ Technique and Matrix Product Verification 318 12.8.2 Extension to Identities of Polynomials 319 12.8.3 Detecting Perfect Matchings in Graphs 322 Defining Terms 323 References 323 Further Information 324 Chapter 13: Pattern Matching and Text Compression Algorithms 326 13.1 Processing Texts Efficiently 326 13.2 String-Matching Algorithms 327 13.2.1 Karp--Rabin Algorithm 328 13.2.2 Knuth--Morris--Pratt Algorithm 329 Example 13.2 329 13.2.3 Boyer--Moore Algorithm 330 Example 13.3 331 Example 13.4 331 Example 13.5 331 Example 13.6 332 13.2.4 Quick Search Algorithm 333 Example 13.7 334 13.2.5 Experimental Results 335 13.2.6 Aho--Corasick Algorithm 335 Example 13.8 338 13.3 Two-Dimensional Pattern Matching Algorithms 339 13.3.1 Zhu--Takaoka Algorithm 339 13.3.2 Bird/Baker Algorithm 340 Example 13.10 341 13.4 Suffix Trees 342 13.4.1 McCreight Algorithm 345 13.5 Alignment 345 13.5.1 Global alignment 348 13.5.2 Local Alignment 350 13.5.3 Longest Common Subsequence of Two Strings 352 13.5.4 Reducing the Space: Hirschberg Algorithm 353 13.6 Approximate String Matching 354 13.6.1 Shift-Or Algorithm 355 13.6.2 String Matching with k Mismatches 356 13.6.3 String Matching with k Differences 357 13.6.4 Wu–Manber Algorithm 359 13.7 Text Compression 361 13.7.1 Huffman Coding 361 13.7.1.1 Encoding 361 13.7.1.2 Decoding 364 13.7.2 Lempel–Ziv–Welsh (LZW) Compression 365 13.7.2.1 Compression Method 366 13.7.2.2 Decompression Method 366 13.7.2.3 Implementation 367 13.7.3 Mixing Several Methods 368 13.7.3.1 Run Length Encoding 368 13.7.3.2 Move To Front 369 13.7.3.3 Integrated Example 369 13.8 Research Issues and Summary 370 Defining Terms 371 References 372 Further Information 373 Chapter 14: Genetic Algorithms 374 14.1 Introduction 374 14.2 Underlying Principles 374 14.3 Best Practices 377 14.3.1 Function Optimization 378 14.3.2 Ordering Problems 379 14.3.3 Automatic Programming 380 14.3.4 Genetic Algorithms for Making Models 382 14.4 Mathematical Analysis of Genetic Algorithms 382 14.5 Research Issues and Summary 385 Acknowledgments 385 Defining Terms 386 References 387 Further Information 388 Chapter 15: Combinatorial Optimization 389 15.1 Introduction 389 15.2 A Primer on Linear Programming 391 15.2.1 Algorithms for Linear Programming 393 15.2.1.1 Fourier’s Scheme for Linear Inequalities 393 15.2.1.2 Simplex Method 395 15.2.1.3 The Ellipsoid Algorithm 397 15.2.1.4 Semidefinite Programming 398 15.2.1.5 Minimizing Submodular Set Functions 399 15.2.1.6 Interior Point Methods 399 15.3 Large-Scale Linear Programming in Combinatorial Optimization 401 15.3.1 Cutting Stock Problem 402 15.3.1.1 Column Generation 402 15.3.2 Decomposition and Compact Representations 403 15.4 Integer Linear Programs 403 15.4.1 Example Formulations 403 15.4.1.1 Covering and Packing Problems 403 15.4.1.2 Packing and Covering Problems in a Graph 404 15.4.1.3 Plant Location Problems 405 15.4.1.4 Satisfiability and Inference Problems: 405 15.4.1.5 Multiprocessor Scheduling 406 15.4.2 Jeroslow’s Representability Theorem 407 15.4.3 Benders’s Representation 407 15.5 Polyhedral Combinatorics 408 15.5.1 Special Structures and Integral Polyhedra 408 15.5.2 Matroids 411 15.5.2.1 Matroid Optimization 411 15.5.2.2 Matroid Intersection 412 15.5.3 Valid Inequalities, Facets, and Cutting Plane Methods 412 15.5.3.1 The Cutting Plane Method 413 15.5.3.2 The b-Matching Problem 414 15.5.3.3 Other Combinatorial Problems 414 15.6 Partial Enumeration Methods 415 15.6.1 Branch and Bound 415 15.6.1.1 Initialization 415 15.6.1.2 Selection/Removal 415 15.6.1.3 Relaxation 416 15.6.1.4 Fathoming 416 15.6.1.5 Separation/Branching 416 15.6.2 Branch and Cut 417 15.7 Approximation in Combinatorial Optimization 418 15.7.1 LP Relaxation and Randomized Rounding 419 15.7.2 Primal–Dual Approximation 419 15.7.3 Semidefinite Relaxation and Rounding 420 15.7.4 Neighborhood Search 421 15.7.5 Lagrangian Relaxation 422 15.8 Prospects in Integer Programming 423 Defining Terms 424 References 424 Section II: Architecture and Organization 430 Chapter 16: Digital Logic 432 16.1 Introduction 432 16.2 Overview of Logic 433 16.3 Concept and Realization of a Digital Gate 433 16.3.1 CMOS Binary Logic Is Low Power 435 16.3.2 CMOS Switching Model for NOT, NAND, and NOR 436 16.3.3 Multiple Inputs and Our Basic Primitives 437 16.3.4 Doing It All with NAND 437 16.4 Rules and Objectives in Combinational Design 438 16.4.1 Boolean Realization: Half Adders, Full Adders, and Logic Minimization 439 16.4.2 Axioms and Theorems of Boolean Logic 441 16.4.3 Design, Gate-Count Reduction, and SOP/POS Conversions 442 16.4.4 Minimizing with Don’t Cares 446 16.4.5 Adder/Subtractor 446 16.4.6 Representing Negative Binary Numbers 448 16.5 Frequently Used Digital Components 450 16.5.1 Elementary Digital Devices: ENC, DEC, MUX, DEMUX 450 16.5.1.1 ENC 450 16.5.1.2 DEC 450 16.5.1.3 MUX 451 16.5.1.4 DEMUX/DECODER 452 16.5.1.5 Priority Encoder 453 16.5.2 The Calculator Arithmetic and Logical Unit 453 16.6.2.1 The SR Latch: Set, Reset, Hold, and Muddle 455 16.6.2.2 The Transparent 456 16.6.2.3 Master--Slave DFF to Eliminate Transparency 457 16.6 Sequential Circuits 454 16.6.1 Concept of a Sequential Device 454 16.6.2 The Data Flip-Flop and the Register 455 16.6.2.1 The SR Latch: Set, Reset, Hold, and Muddle 455 16.6.2.2 The Transparent D-Latch 456 16.6.2.3 Master–Slave DFF to Eliminate Transparency 457 16.6.3 From DFF to Data Register, Shift Register, and Stack 458 16.6.3.1 A Stack for Holding Data 458 16.6.4 Datapath for a 4-bit Calculator 459 16.7 ASICs and FPGAs — Faster, Cheaper, More Reliable Logic 461 16.7.1 FPGA Architecture 462 16.7.1.1 The Configurable Logic Block 463 16.7.1.2 Interconnect 464 16.7.1.3 The Xilinx Input/Output Block 465 16.7.1.4 Mapping the Simple Calculator to an FPGA 466 16.7.2 Higher Levels of Complexity 467 Acknowledgment 467 Defining Terms 467 References 468 Further Information 469 Chapter 17: Digital Computer Architecture 470 17.1 Introduction 470 17.1.1 The Processor-Program Interface 470 17.2 The Instruction Set 471 17.2.1 ALU Instructions 472 17.2.2 Memory and Memory Referencing Instructions 472 17.2.3 Control Transfer Instructions 473 17.3 Memory 474 17.3.1 Register File 474 17.3.2 Main Memory 475 17.3.3 Cache Memory 475 17.3.4 Memory and Architecture 475 17.3.5 Secondary Storage 476 17.4 Addressing 476 17.4.1 Addressing Format 476 17.4.2 Physical and Virtual Memory 477 17.5 Instruction Execution 478 17.5.1 Instruction Fetch Unit 480 17.5.2 Instruction Decode Unit 480 17.5.3 Execution Unit 480 17.5.4 Storeback Unit 480 17.6 Execution Hazards 481 17.6.1 Data Hazards 481 17.6.2 Control Hazards 483 17.6.3 Structural Hazards 484 17.7 Superscalar Design 484 17.8 Very Long Instruction Word Computers 484 17.9 Summary 485 Defining Terms 485 References 485 Further Information 486 Chapter 18: Memory Systems 487 18.1 Introduction 487 18.2 Memory Hierarchies 488 18.3 Cache Memories 490 18.4 Parallel and Interleaved Main Memories 493 18.5 Virtual Memory 496 18.6 Research Issues 498 18.7 Summary 499 Defining Terms 500 References 501 Further Information 501 Chapter 19: Buses 502 19.1 Introduction 502 19.2 Bus Physics 503 19.2.1 Transmission-Line Concepts 503 19.2.2 Signal Reflections 505 19.2.3 Wire-OR Glitches 505 19.2.4 Signal Skew 506 19.2.5 Cross-Coupling Effects 506 19.3 Bus Arbitration 506 19.3.1 Centralized Arbitration 506 19.3.2 Decentralized Arbitration 507 19.4 Bus Protocol 508 19.4.1 Asynchronous Protocol 508 19.4.2 Synchronous Protocol 509 19.4.3 Split-Transaction Protocol 509 19.5 Issues in SMP System Buses 510 19.5.1 Cache Coherence Protocols 512 19.5.2 Bus Arbitration 513 19.5.3 Bus Bandwidth 514 19.5.4 Memory Access Latency 515 19.5.5 Synchronization and Locking 515 19.6 Putting It All Together — CCL-XMP System Bus 516 19.7 Historical Perspective and Research Issues 518 Defining Terms 520 References 520 Further Information 522 Chapter 20: Input/Output Devices and Interaction Techniques 523 20.1 Introduction 523 20.2 Interaction Tasks, Techniques, and Devices 524 20.3 The Composition of Interaction Tasks 525 20.4 Properties of Input Devices 525 20.5 Discussion of Common Pointing Devices 528 20.6 Feedback and Perception — Action Coupling 529 20.7 Keyboards, Text Entry, and Command Input 530 20.8 Modalities of Interaction 532 20.8.1 Voice and Speech 532 20.8.2 Pen-Based Gestures and Hand Gesture Input 532 20.8.3 Bimanual Input 533 20.8.4 Passive Measurement: Interaction in the Background 533 20.9 Displays and Perception 534 20.9.1 Properties of Displays and Human Visual Perception 534 20.10 Color Vision and Color Displays 536 20.11 Luminance, Color Specification, and Color Gamut 536 20.12 Information Visualization 538 20.12.1 General Issues in Information Coding 538 20.12.2 Color Information Coding 538 20.12.3 Integrated Control/Display Objects 539 20.12.4 Three-Dimensional Graphics and Virtual Environments 540 20.12.5 Augmented Reality 540 20.13 Scale in Displays 540 20.13.1 Small Displays 540 20.13.2 Multiple Displays 541 20.13.3 Large-Format Displays 541 20.14 Force and Tactile Displays 542 20.15 Auditory Displays 543 20.15.1 Nonspeech Audio 543 20.15.2 Speech Output 543 20.15.3 Spatialized Audio Displays 544 20.16 Future Directions 544 References 545 Chapter 21: Secondary Storage Systems 555 21.1 Introduction 555 21.1.1 Roadmap to the Chapter 558 21.2 Single Disk Organization and Performance 558 21.2.1 Disk Organization 559 21.2.2 Disk Arm Scheduling 561 21.2.2.1 Disk Scheduling for Continuous Data Requests 564 21.2.3 Methods to Improve Disk Performance 564 21.2.3.1 Disk Arm Prepositioning 564 21.2.3.2 Disk Reorganization and Defragmentation 565 21.2.3.3 Log-Structured File Systems (LFS) 565 21.2.3.4 Active Disks and Free-Block Scheduling 565 21.3 RAID Disk Arrays 566 21.3.1 Motivation for RAID 566 21.3.2 RAID Concepts 567 21.3.2.1 Striping 567 21.3.3 RAID Fault-Tolerance and Classification 568 21.3.4 Caching and the Memory Hierarchy 570 21.3.5 RAID Reliability Modeling 570 21.4 RAID1 or Mirrored Disks 571 21.4.1 Request Scheduling with Mirrored Disks 571 21.4.2 Scheduling of Write Requests with an NVS Cache 572 21.4.3 Mirrored Disk Layouts 572 21.5 RAID5 Disk Arrays 573 21.5.1 RAID5 Operation in Normal Mode 573 21.5.2 RAID5 Operation in Degraded Mode 574 21.5.3 RAID5 Operation in Rebuild Mode 574 21.6 Performance Evaluation Studies 575 21.6.1 Single Disk Performance 575 21.6.2 RAID Performance 576 21.6.3 Analysis of RAID5 Systems 577 21.6.3.1 Fork-Join Synchronization 577 21.6.3.2 Vacationing Server Model for Rebuild 578 21.7 Data Allocation and Storage Management in Storage Networks 579 21.7.1 Requirements of a Storage Network 579 21.7.2 Storage Management 580 21.8 Conclusions and Recent Developments 580 Acknowledgments 581 Defining Terms 581 References 582 Further Information 588 Chapter 22: High-Speed Computer Arithmetic 589 22.1 Introduction 589 22.2 Fixed Point Number Systems 589 22.2.1 Two’s Complement 590 22.2.2 Sign Magnitude 590 22.2.3 One’s Complement 591 22.3 Fixed Point Arithmetic Algorithms 592 22.3.1 Fixed Point Addition 592 22.3.1.1 Full Adder 592 22.3.1.2 Ripple Carry Adder 593 22.3.1.3 Carry Lookahead Adder 594 22.3.1.4 Carry Skip Adder 595 22.3.1.5 Carry Select Adder 598 22.3.2 Fixed Point Subtraction 599 22.3.3 Fixed Point Multiplication 600 22.3.3.1 Sequential Booth Multiplier 600 22.3.3.2 Sequential Modified Booth Multiplier 601 22.3.3.3 Array Multipliers 601 22.3.3.4 Wallace Tree/Dadda Fast Multiplier 601 22.3.4 Fixed Point Division 603 22.3.4.1 Nonrestoring Divider 603 22.3.4.2 Newton–Raphson Divider 604 22.4 Floating Point Arithmetic 606 22.4.1 Floating Point Number Systems 606 22.4.1.1 Floating Point Addition 606 22.4.1.2 Floating Point Multiplication 607 22.4.1.3 Floating Point Division 607 22.4.1.4 Floating Point Rounding 608 22.5 Conclusion 608 Acknowledgments 609 References 609 Chapter 23: Parallel Architectures 611 23.1 Introduction 611 23.2 The Stream Model 611 23.3 SISD 612 23.4 SIMD 615 23.4.1 Array Processors 615 23.4.2 Vector Processors 616 23.5 MISD 618 23.6 MIMD 618 23.7 Network Interconnections 621 23.8 Afterword 622 Defining Terms 623 References 623 Further Information 624 Chapter 24: Architecture and Networks 625 24.1 Introduction 625 24.2 Underlying Principles 626 24.2.1 LANs, WANs, MANs, and Topologies 626 24.2.2 Circuit Switching and Packet Switching 627 24.2.3 Protocol Stacks 627 24.2.4 Data Representation: Baseband Methods 629 24.2.5 Data Representation: Modulation 629 24.2.5.1 Multiplexing 631 24.3 Best Practices: Physical Layer Examples 632 24.3.1 Media 632 24.3.2 Repeaters and Regenerators 633 24.3.3 Voice Modems 633 24.3.4 Cable Modems 634 24.3.5 DSL 634 24.3.6 Hubs and Other LAN Switching Devices 635 24.4 Best Practices: Data-Link Layer Examples 637 24.4.1 Network Interface Cards 637 24.4.2 An Example: Ethernet NIC 637 24.4.3 Bridges and Other Data-Link Layer Switches 638 24.5 Best Practices: Network Layer Examples 638 24.6 Research Issues and Summary 639 Defining Terms 639 References 640 Further Information 642 Chapter 25: Fault Tolerance 643 25.1 Introduction 643 25.2 Failures, Errors, and Faults 644 25.2.1 Failures 644 25.2.2 Errors 645 25.2.3 Faults 645 25.3 Metrics and Evaluation 646 25.3.1 Metrics 646 25.3.2 Evaluation 647 25.4 System Failure Response 648 25.4.1 Error on Output 648 25.4.2 Error Masking 649 25.4.3 Fault Secure Techniques 650 25.4.3.1 Duplication 651 25.4.3.2 Parity Prediction 651 25.4.3.3 Residue Codes 652 25.4.3.4 Application-Specific Techniques 652 25.4.4 Fail-Safe Techniques 653 25.5 System Recovery 653 25.6 Repair Techniques 654 25.6.1 Built-in Self-Test and Diagnosis 654 25.6.2 Fail-Soft Techniques 654 25.6.3 Self-Repair Techniques 655 25.6.3.1 Standby Spares 655 25.6.3.2 Hybrid Redundancy 655 25.6.3.3 Self-Purging Redundancy 656 25.6.3.4 Reconfigurable Systems Self-Repair 656 25.7 Common-Mode Failures and Design Diversity 656 25.8 Fault Injection 656 25.9 Conclusion 657 25.10 Further Reading 658 References 658 Section III: Computational Science 663 Chapter 26: Geometry-Grid Generation 665 26.1 Introduction 665 26.1.1 Structured Grids 666 26.1.2 Unstructured Grids 668 26.1.2.1 Hybrid Grid 668 26.1.3 Generation Process 668 26.2 Underlying Principles 669 26.2.1 Terminology and Grid Characteristics 669 26.2.2 Geometry Preparation 671 26.2.3 Structured Grid Generation 672 26.2.3.1 Algebraic Generation Methods 672 26.2.3.2 Elliptic Generation Method 673 26.2.3.3 Hyperbolic Generation Method 674 26.2.3.4 Multiblock Systems 674 26.2.3.5 Chimera Grids 675 26.2.3.6 Adaptive Grid Generation 675 26.2.4 Unstructured Grid Generation 676 26.2.4.1 The Delaunay Triangulation 676 26.2.4.2 Advancing Front Procedure 676 26.2.4.3 Grid Adaption Methods 677 26.3 Best Practices 679 26.3.1 Structured Grid Generation 679 26.3.1.1 Transfinite Interpolation Method 680 26.3.1.2 Elliptic Grid Generation 682 26.3.2 The Delaunay Algorithm 683 26.3.2.1 Point Creation by the Use of Sources 685 26.3.2.2 Point Creation Controlled by a Background Mesh 685 26.3.2.3 Boundary Integrity 685 26.3.2.4 Edge Swapping 686 26.3.2.5 Boundary Edge Recovery 686 26.3.2.6 Boundary Face Recovery 686 26.3.2.7 Removal of Added Points 687 26.3.3 Hybrid Grid Generation 687 26.3.3.1 Grid Adaption: Construction of Weight Functions 688 26.4 Grid Systems 689 26.5 Research Issues and Summary 690 References 691 Further Information 693 Chapter 27: Scientific Visualization 694 27.1 Introduction 694 27.2 Historic Overview 694 27.2.1 The Motivation for Computer-Generated Visualization 695 27.2.2 The Process of Computational Science in Relation to Visualization 696 27.2.3 What Exactly Is Scientific Visualization? 697 27.2.4 Other Modes of Presenting Information 697 27.2.5 Application Areas 697 27.2.6 Evolution of Scientific Visualization 698 27.3 Underlying Principles 698 27.3.1 The Goal of Scientific Visualization 698 27.3.2 The Basic Steps of the Scientific Visualization Process 699 27.3.2.1 Data Filtering 699 27.3.2.2 Representation Issues 699 27.3.2.3 Accuracy 700 27.3.2.4 Human Perception 701 27.4 The Practice of Scientific Visualization 701 27.4.1 Representation Techniques 701 27.4.1.1 Realism Continuum 702 27.4.1.2 Color 702 27.4.1.3 Form 703 27.4.1.3.1 Two-Dimensional Plane 703 27.4.1.3.2 Height 704 27.4.1.3.3 Volume Rendering 704 27.4.1.3.4 Vectors: Arrows, Tracers, Streamlines, etc. 704 27.4.1.3.5 Isosurfaces 706 27.4.1.3.6 Forms from Traditional Science 707 27.4.1.3.7 Cutting Plane 707 27.4.1.3.8 Alpha Shapes 707 27.4.1.4 Motion 708 27.4.1.5 Transparency 709 27.4.1.6 Combining Techniques 709 27.4.2 The Visualization Process 709 27.4.2.1 Still Imagery 710 27.4.2.2 Animation 711 27.4.2.3 Interaction 711 27.4.2.4 Interactive Steering 712 27.4.3 Visualization Tools 712 27.4.3.1 Plotting Libraries 713 27.4.3.2 Turnkey Visualization Packages 713 27.4.3.3 Dataflow Packages 714 27.4.3.4 Animation 715 27.4.3.5 WYOS: Write Your Own Software 716 27.4.3.6 Tools Summary 717 27.4.4 Examples of Scientific Visualizations 717 27.4.4.1 The Study of a Severe Thunderstorm 717 27.4.4.1.1 Evolution of Atmospheric Simulations and Visualization 717 27.4.4.1.2 What Does the Scientist Use Today? 720 27.4.5 Visualizing Smog 721 27.5 Research I