Highly parallel computing

목차 (Table of Contents)

• CONTENTS
• Part Ⅰ : Foundations = 1
• 1 Overview = 3
• 1.1 Overview and Scope of This Book = 4
• 1.2 Definition and Driving Forces = 5
• 1.2.1 Driving Forces and Enabling Factors = 5
• 1.3 Questions Raised = 6
• 1.4 Emerging Answers = 9
• 1.4.1 Processing Elements : Their Number, Power, and Nature = 9
• 1.4.2 Memory and I／O = 11
• 1.4.3 How Do the Processors Communicate? = 12
• 1.4.4 How Do the Processors Cooperate? = 13
• Synchronization = 13
• The Size of Each Processor's Subtask-Granularity = 13
• How Autonomous Should Each Processor Be? = 18
• How Will the Operating System Coordinate These Efforts? = 20
• 1.4.5 Choosing and Attacking the Problem = 21
• Applications Amenable to Parallel Processing = 21
• What Parallel Computational Models are Available? = 23
• What Algorithms Should Be Used? = 24
• How Much Speedup Can Be Expected? = 24
• 1.4.6 What Will Be the Programmer's View of the Machine? = 30
• Finding and Specifying Parallelism = 30
• What About Reliability, Availability, Serviceability? = 30
• 1.5 Previous Attempts ; Why Success Now? = 31
• 1.6 Conclusions and Future Directions = 33
• 1.7 Exercises = 35
• 2 Sample Applications = 37
• 2.1 Scientific and Engineering Applications = 38
• 2.1.1 Parallel Solutions to Significant Scientific Problems = 38
• 2.1.2 The Weather Code = 39
• Parallelization of the Weather Code = 48
• 2.1.3 Molecular Dynamics = 51
• 2.1.4 Quantum Chromo dynamics = 51
• 2.1.5 Seismic Migration = 51
• The Serial Program = 53
• The Parallel Program = 55
• PVMe and SP1 Results = 57
• Projections for Higher Communication Speed = 57
• Lessons for Highly Parallel Computing = 59
• 2.1.6 Computer-Aided VLSI Design = 62
• 2.1.7 Other Areas = 65
• 2.2 Database Systems = 66
• 2.2.1 Sources of Parallelism in Query Processing = 66
• Parallelism Within and Among Transactions = 66
• The Relational Database Model = 67
• Parallelizing Relational Database Operations(an Example of Parallelism Within A Transaction) = 68
• Parallel Database Machine Terminology = 72
• 2.2.2 The I／O Situation = 73
• 2.3 Artificial intelligence Systems = 74
• 2.3.1 Artificial intelligence = 74
• 2.3.2 Production Systems and Expert Systems = 74
• State-Spate Searching = 76
• Example 1 : Heuristic Search = 77
• Example 2 : AND／OR Graphs = 79
• Example 3 : Resolution and Unification in Prolog = 80
• 2.3.3 Sources of Parallelism in Production Systems = 82
• 2.3.4 Perception and Problem-Solving Systems = 84
• Commonsense Reasoning With Semantic Networks-NETL = 85
• Visual Recognition Systems = 87
• Computing With Connections = 87
• 2.3.5 Computing with Connections in Visual Recognition = 88
• How the Recognition Scheme Works = 91
• 2.4 Summary = 94
• 2.5 Exercises = 96
• 3 Technological Constraints and Opportunities = 99
• 3.1 Processor and Network Technology = 100
• 3.1.1 VLSI Circuit Speed = 102
• Field-Effect Transistors = 102
• Bipolar Transistors = 104
• 3.1.2 Levels of Logic = 108
• 3.1.3 Packaging = 109
• 3.1.4 Gate Delays Per Cycle = 113
• 3.1.5 Cycles Per Instruction(Beyond Technology) = 115
• 3.1.6 The Costs of VLSI = 117
• 3.1.7 Technology and Parallel Processing = 121
• The Headroom Problem = 122
• 3.2 Memory Technology = 125
• 3.2.1 Memory Size : Megabytes／MIPS = 125
• "Dennard's Folly" = 126
• 3.2.2 Memory Speed and Bandwidth = 128
• 3.3 Storage Technology = 129
• 3.3.1 The Amazing Disappearing I／O Bandwidth = 129
• 3.4 Exercises = 132
• 4 Computational Models - and Selected Algorithms = 137
• 4.1 Computational Models-An Operational View = 138
• 4.1.1 What, Where, and When = 138
• 4.1.2 Classifications = 142
• SIMD／MIMD = 142
• Classification by Execution Streams = 143
• Data and Control Mechanisms in MIMD = 144
• Multiple Levels of Parallelism = 145
• Summary = 146
• 4.1.3 Essential Constructs for Parallel Execution = 146
• Defining(Identifying and Specifying) Parallel Subtasks = 147
• Starting and Stepping Parallel Execution = 149
• Coordinating Parallel Execution = 153
• Synchronizing Concurrent Activities-Sequence, Access Control = 155
• Synchronization in Shared-Memory Computation = 156
• Synchronization in Message-Passing Computation = 163
• Remote Procedure Call = L66
• 4.1.4 Quantitative Speedup Discussion = 170
• 4.1.5 Maximum Useful Parallelism = 179
• 4.2 Computational Models-An Analytical View = 182
• 4.2.1 Serial Computational Complexity = 183
• Three Hyperopic Greek Analysts-Omega, Omicron, and Theta-and Their Two Children = 184
• The Complexity of A Problem = 185
• 4.2.2 Random Access Machines(RAMs) = 186
• 4.2.3 From RAMs to PRAMs = 189
• 4.2.4 A Message-Passing Model : MP-RAM = 190
• 4.2.5 Emulating Message-Passing With Shared Memory = 192
• 4.2.6 Parallel Computational Complexity = 193
• Informal Discussion = 193
• Formal Definitions = 199
• 4.3 Selected Parallel Algorithms = 201
• 4.3.1 Issues = 203
• Imprecision in Asymptotic Complexity = 203
• Worst Case vs. Real-World Behavior = 203
• Needed Data Movement = 204
• I／O = 204
• 4.3.2 A Simple Message-Passing Algorithm : Summing = 205
• The Dependent-Size Analysis = 205
• The Independent-Size Analysis = 206
• The Heavily Loaded Limit = 207
• Parallel Prefix = 209
• 4.3.3 Another Message-Passing Algorithm : Permuting = 209
• Permuting is Not Completely Parallelizable = 210
• Permuting Evenly Distributed Data = 212
• 4.3.4 A Shared-Memory Algorithm : Sorting = 212
• 4.3.5 Other Message-Passing : Algorithms = 215
• 4.3.6 Other Shared-Memory Algorithms = 215
• 4.4 Exercises = 220
• Pert Ⅱ : Parallel Software = 223
• Overview of the Software Chapters = 223
• 5 Languages and Programming Environments = 225
• Imperative and Declarative Languages = 226
• Three Scenarios for the Programmer = 227
• 5.1 Review of the Major Serial Languages = 229
• 5.1.1 A Brief History = 230
• 5.1.2 Critique of the von Neumann Languages = 233
• 5.1.3 Shared Variables and Side Effects = 235
• 5.1.4 Evolution of Abstraction in Programming Languages = 236
• 5.1.5 Binding Times = 237
• 5.2 Parallel Imperative Languages and Extensions = 238
• 5.2.1 Data Parallelism, Fortran 90, Fortran D, and HPF = 239
• 5.2.2 Fortran and C Extensions for Shared Memory = 244
• 5.2.3 Multilisp = 245
• 5.2.4 Concurrent Pascal = 246
• 5.2.5 CSP and Occam = 247
• 5.2.6 Express, PVM, and Linda = 249
• 5.3 Declarative Languages = 256
• 5.3.1 Functional and Dataflow Languages = 256
• The "Fat and Flabby" von Neumann Languages = 257
• The FP Functional Programming Language = 259
• Moden Functional Languages-Haskell and Others = 261
• A Lambda Calculus Primer = 262
• Dataflow Languages-VAL, Id, LAU, Sisal = 271
• Functional Languages for Parallel Computing : Pros and Cons = 278
• 5.3.2 Logic Programming Languages = 279
• A Quick Review of Prolog = 279
• OR-Parallelism = 282
• AND-Parallelism = 283
• Concurrent Prolog, Parlog, FGHC, OR-Parallel Prolog = 284
• 5.4 The Programmer's View = 286
• 5.5 Exercises = 290
• 6 Compilers = 295
• 6.1 Serial Compiler Essentials = 297
• 6.2 Parallelizing Compiler Essentials = 301
• 6.2.1 Vectorizers = 305
• 6.2.2 Dependency Graphs and Analysis = 309
• 6.2.3 Parallelism Beyond the Vector Level = 311
• 6.3 Parallelizing Cempiler Examples = 314
• 6.3.1 Parafrase Fortran Reconstructing Compiler = 314
• Related Systems : PFC, PTRAN, MIMDizer = 318
• 6.3.2 Bulldog Fortran Reassembling Compiler = 319
• VLIW Architectures = 321
• Trace Scheduling = 322
• 6.3.3 An APL-Based Approach = 325
• 6.3.4 Dataflow／Functional Language Translators = 331
• 6.4 Summary and Perspective = 335
• 6.5 Exercises = 337
• 7 Operating Systems = 341
• 7.1 Operating Systems for Serial Machines = 343
• 7.1.1 Process Creation, Destruction, and Scheduling = 344
• 7.1.2 Memory Management = 346
• 7.1.3 Input / Output and File Systems = 351
• 7.1.4 Even A Serial OS is Concurrent = 353
• 7.2 Controlling Concurrency = 355
• The Importance of Being Atomic = 356
• The Importance of Being Atomic(Continued) = 357
• 7.2.1 The(Second) Critical Section Problem = 359
• 7.3 Classifying Parallel Operating Systems = 363
• 7.3.1 Separate Supervisors = 360
• 7.3.2 Master-Slave = 360
• 7.3.3 Symmetric = 361
• 7.4 History of Parallel Operating Systems = 363
• 7.4.1 First Steps = 363
• 7.4.2 Higher Levels of Parallelism = 365
• Hydra = 365
• Medusa and StarOS = 366
• Embos = 366
• 7.4.3 UNIX-Based Parallel Systems = 367
• MUNIX and Purdue UNIX = 367
• Tunis = 367
• Dynix and 3B20A UNIX = 368
• Mach and Lightweight Processes = 369
• Symunix and Bottleneck Freedom = 371
• 7.5 Exercises = 374
• Part Ⅲ : Parallel Architectures = 377
• Overview of the Architecture Chapters = 377
• Performance Benchmarks for Some Supercomputers = 379
• 8 Interconnection Networks = 381
• Static vs. Dynamic(i.e., Switching) Networks = 383
• 8.1 Static Connection Topologies = 384
• 8.1.1. Descriptions = 385
• Meshes and Rings = 385
• Stars = 386
• Binary Trees = 386
• Fully Connected Nodes = 386
• Hypercubes = 386
• Cube-Connected Cycles(CCC) = 388
• Shuffle Exchange = 388
• 8.1.2 Routing = 389
• Fully Connected Nodes = 390
• Stars = 390
• Trees = 390
• Meshes and Rings = 390
• Hypercubes = 391
• Cube-Connected Cycles(CCC) = 391
• Shuffle Exchange = 391
• 8.1.3 Cost-Performance Tradeoffs = 391
• 8.2 Dynamic Connection Topologies(Switching Networks) = 394
• 8.2.1 Switching Strategy = 395
• 8.2.2 Crossbars and Buses = 397
• 8.2.3 Multistage Switching Networks = 398
• Omega Networks = 398
• Benes Networks = 401
• Banyan Networks = 402
• 8.2.4 Single-Stage(Recirculating) Switching Networks = 402
• 8.2.5 Dynamic Meshes = 403
• Depopulated Meshes = 403
• 8.2.6 Dynamic(Fat) Trees = 404
• 8.2.7 Added Features : Combining and Fault Tolerance = 405
• 8.3 Exercises = 409
• 9 SIMD Parallel Architectures = 413
• 9.1 Evolution from von Neumann Machines = 414
• 9.2 Vector Processors = 415
• 9.2.1 Vector Processor Performance = 417
• 9.3 Pipelined SIMD Vector Processors = 423
• 9.3.1 CRAY Steries = 423
• 9.3.2 CDC Cyber 205 = 426
• 9.3.3 IBM 3090 and ES／9000 Vector Facility = 427
• 9.3.4 The NEC SX System = 428
• 9.3.5 Comparison of Pipelined Vector Processors = 429
• 9.4 Parallel SIMD Designs = 429
• 9.4.1 UI ILLIACIV = 431
• 9.4.2 IBM GF11 = 436
• Processors = 437
• Disks = 438
• Network = 439
• Controller = 440
• Programming = 441
• The Case for SIMD = 442
• QCD = 444
• Other GF11 Applications = 445
• Other QCD Machines = 446
• 9.4.3 CM-1 Connection Machine(MIT／TMC) = 446
• Processing Elements = 448
• Routing Element and Network = 451
• CM-1 Processor Action While Routing Messages = 452
• Programming Environment = 455
• CM-1 Applications = 456
• Comparisons = 457
• CM-2 = 457
• 9.4.4 Other Arrays of Processors = 458
• The MasPar MP-1 and MP-2 = 458
• Goodyear MPP = 460
• The ICL DAP = 460
• 9.4.5 Systolic Arrays = 461
• CMU／GE Warp = 465
• 9.5 Exercises = 466
• 10 MIMD Parallel Architectures = 469
• 10.1 Stepping Up to MIMD = 470
• 10.1.1 Private Memory(Message Passing) Vs. Shared Memory = 470
• 10.1.2 The Effect of Grain Size = 471
• Macro Dataflow = 471
• Macro Pipelining = 472
• 10.2 Private-Memory(Message-Passing) Designs = 474
• 10.2.1 What to Look for in Private-Memory Designs = 474
• 10.2.2 Clusters of Workstations(Flarms) = 475
• 10.2.3 Hypercubes = 475
• The Caltech Cosmic Cube = 476
• Message-Passing, Shared-Memory Progrems = 480
• Intel IPSC and IPSC／860 = 488
• Floating Point Systems FPS／T = 490
• The NCUBE／ten and NCUBE 2 = 490
• 10.2.4 Meshes = 491
• Intel Paragon and Touchstone Delta = 491
• HSCP PAX = 493
• IBM Victor : A Transputer-based Design = 495
• IBM WRM = 497
• U. Utah Rediflow = 498
• Purdue／UW CHIP = 502
• 10.2.5 Bus-Connected Designs = 503
• Tandem = 503
• 10.2.6 Trees = 504
• The Teradata Database Machine = 504
• The Columbia DADO Production-System Machine = 505
• The TMC Connection Machine CM 5 = 509
• 10.2.7 Multistage Networks = 512
• IBM 9076 SPI = 512
• 10.2.8 Dataflow Machines-Manchester and (Many) Others = 512
• The Manchester Dataflow Machine Prototype = 516
• Design and Efficiency Considerations = 520
• Static and Dynamic Dataflow and Reentrancy = 522
• Data Structures in A Dataflow Machine = 527
• Other Hardware = 534
• Programming and Software = 538
• Conclusions = 539
• 10.3 Shared-Memory MIMD Designs = 540
• 10.3.1 Comparing Shared-Memory Designs-What to Look for = 540
• 10.3.2 Caches and Modest Bus-Based MIMD Systems = 541
• Bus-Based Systems = 542
• Caches = 544
• 10.3.3 Kendall Square Research KSRI = 549
• Hardware = 55O
• ALLCACHE Memory and the Ring of Rings = 551
• Software = 552
• 10.3.4 The Stanford University DASH = 553
• Architecture = 553
• Prototype Hardware = 554
• Performance of the Prototype = 555
• 10.3.5 The MIT Alewife = 556
• 10.3.6 The MIT J-Machine = 557
• 10.3.7 Cray T3D = 559
• 10.3.8 CMU C.mmp = 561
• Hardware = 56L
• Results = 562
• 10.3.9 CMU Cm = 563
• Hardware = 563
• Software = 565
• 10.3.10 Denelcor HEP = 566
• The HEP Architecture = 567
• Progrmming Tole Lief = 571
• The Tera Architecture = 571
• 10.3.11 The NYU Ultracomputer = 572
• Hardware for Coordinating N Processes in Log N Time = 574
• Software : Programming Environment, Operating System = 576
• Recap = 577
• The Power and Cost of Fetch-and-Add = 577
• Enhanced Omega Network With Combining = 580
• Case Study : Semaphores Using Fetch-and-Add = 586
• Case Study : Barriers Using Fetch-and-Add = 587
• Case Study : Parallel Queue Using Fetch-and-Add = 588
• Prototype Hardware = 592
• 10.3.12 The BBN Butterfly = 594
• Architecture and Hardware = 595
• Software and Programming = 576
• Comparisons Anti Controversies = 597
• 10.3.13 The Great Hot Spots Controversy = 598
• 10.3.14 The IBM RP3 = 603
• Architecture and Hardware = 604
• Processing Nodes = 606
• Network = 607
• I／O Subsystem = 608
• Software Ants Programming = 609
• 10.3.15 IBM PVS = 611
• 10.3.16 UL Cedar = 612
• Hardware = 612
• Software and Programming = 616
• Performance = 618
• 10.4 Exercises = 619
• 11 Hybrid Parallel Architectures = 623
• 11.1 VLIW Architectures = 623
• 11.1.1 Multiflow TRACE = 623
• 11.1.2 CHOPP = 625
• 11.1.3 IBM YSE／EVE = 627
• 11.2 MSIMD Tree Machines = 629
• 11.2.1 UNC Cellular Computer = 630
• 11.2.2 Columbia NON-VON = 634
• 11.3 MSIMD Reconfigurable Designs = 635
• 11.3.1 UT TRAC = 635
• 11.3.2 Purdue PASM = 636
• 11.4 Exercises = 637
• Bibliography = 639
• Index = 675