HOME > Detail View

Detail View

Introduction to parallel computing : design and analysis of algorithms

Introduction to parallel computing : design and analysis of algorithms (Loan 5 times)

Material type
단행본
Personal Author
Kumar, Vipin 1956-
Title Statement
Introduction to parallel computing : design and analysis of algorithms / Vipin Kumar ... [et al.].
Publication, Distribution, etc
Redwood City, Calif. :   Benjamin/Cummings Pub. Co. ,   c1994.  
Physical Medium
xv, 597 p. : ill. ; 25 cm.
ISBN
0805331700
Bibliography, Etc. Note
Includes bibliographical references and indexes.
Subject Added Entry-Topical Term
Parallel processing (Electronic computers) Parallel algorithms.
000 00885camuu2200253 a 4500
001 000045288454
005 20060825160507
008 930826s1994 caua b 001 0 eng
010 ▼a 93034230 //r982
020 ▼a 0805331700
035 ▼a (KERIS)REF000004756261
040 ▼a DLC ▼c DLC ▼d DLC ▼d WaU ▼d 211009
050 0 0 ▼a QA76.58 ▼b .I58 1994
082 0 4 ▼a 004.35 ▼2 22
090 ▼a 005.2 ▼b I61
245 0 0 ▼a Introduction to parallel computing : ▼b design and analysis of algorithms / ▼c Vipin Kumar ... [et al.].
260 ▼a Redwood City, Calif. : ▼b Benjamin/Cummings Pub. Co. , ▼c c1994.
300 ▼a xv, 597 p. : ▼b ill. ; ▼c 25 cm.
504 ▼a Includes bibliographical references and indexes.
650 0 ▼a Parallel processing (Electronic computers)
650 0 ▼a Parallel algorithms.
700 1 ▼a Kumar, Vipin ▼d 1956-
945 ▼a KINS

Holdings Information

No. Location Call Number Accession No. Availability Due Date Make a Reservation Service
No. 1 Location Science & Engineering Library/Stacks 1(Western Books)/ Call Number 005.2 I61 Accession No. 121131325 Availability Available Due Date Make a Reservation Service B M

Contents information

Table of Contents


CONTENTS
Preface = xiii
CHAPTER 1 Introduction = 1
Introduction = 1
 1.1 What is parallel Computing? = 2
 1.2 The Scope of Parallel Computing = 3
 1.3 Issues in Parallel Computing = 4
 1.4 Organization and Contents of the Text = 5
 1.5 Bibliographic Remarks = 8
Problems = 9
References = 10
CHAPTER 2 Models of Parallel Computers = 15
 2.1 A Taxonomy of Parallel Architectures = 16
  2.1.1 Control Mechanism = 16
  2.1.2 Address-Space Organization = 18
  2.1.3 Interconnection Networks = 22
  2.1.4 Processor Granularity = 22
 2.2 An Idealized Parallel Computer = 23
 2.3 Dynamic Interconnection Networks = 24
  2.3.1. Crossbar Switching Networks = 24
  2.3.2 Bus-Based Networks = 25
  2.3.3 Multistage Interconnection Networks = 26
 2.4 Static Interconnection Networks = 30
  2.4.1 Types of Static Interconnection Networks = 30
  2.4.2 Evaluating Static Interconnection Networks = 37
 2.5 Embedding Other Networks into a Hypercube = 39
  2.5.1 Embedding a Linear Array into a Hypercube = 39
  2.5.2 Embedding a Mesh into a Hypercube = 41
  2.5.3 Embedding a Binary Tree into a Hypercube = 42
 2.6 Routing Mechanisms for Static Networks = 42
 2.7 Communication Costs in Static Interconnection Networks = 45
  2.7.1 Store-and-Forward Routing = 45
  2.7.2 Cut-Through Routing = 46
 2.8 Cost-Performance Tradeoffs = 48
 2.9 Architectural Models for Parallel Algorithm Design = 49
 2.10 Bibliographic Remarks = 51
 Problems = 54
 References = 60
CHAPTER 3 Basic Communication Operations = 65
 3.1 Simple Message Transfer between Two Processors = 66
 3.2 One-to-All Broadcast = 66
  3.2.1 Store-and-Forward Routing = 67
  3.2.2 cut-Through Routing = 75
 3.3. All-to-all Broadcast, Reduction, and Prefix Sums = 77
  3.3.1 Store-and-Forward Routing = 78
  3.3.2 Cut-Through Routing = 86
 3.4 One-to-All Personalized Communication = 88
 3.5 All-to-All Personalized Communication = 90
  3.5.1 Store-and-Forward Routing = 90
  3.5.2 Cut-Through Routing = 95
 3.6 Circular Shift = 98
  3.6.1 Store-and-Forward Routing = 98
  3.6.2 Cut-Through Routing = 101
 3.7 Faster Methods for Some Communication Operations = 101
  3.7.1 Routing Messages in Parts = 102
  3.7.2 All-Port Communication = 104
  3.7.3 Special Hardware for Global Operations = 105
 3.8 Summary = 106
 3.9 Bibliographic Remarks = 107
 Problems = 108
 References = 114
CHAPTER 4 Performance and Scalability of Parallel Systems = 117
 4.1 Performance Metrics for Parallel Systems = 117
  4.1.1 Run Time = 117
  4.1.2 Speedup = 118
  4.1.3 Efficiency = 120
  4.1.4 Cost = 120
 4.2 The Effect of Granularity and Data Mapping on Performance = 121
 4.3 The Scalability of Parallel Systems = 126
 4.4 The Isoefficiency Metric of Scalability = 128
  4.4.1 Problem Size = 129
  4.4.2 The Overhead Function = 129
  4.4.3 The Isoefficiency Function = 130
  4.4.4 Cost-Optimality and the Isoefficiency Function = 133
  4.4.5 A Lower Bound on the Isoefficiency Function = 134
  4.4.6 The Degree of Concurrency and the Isoefficiency Function = 134
 4.5 Sources of Parallel Overhead = 135
  4.5.1 Interprocessor Communication = 135
  4.5.2 Load Imbalance = 135
  4.5.3 Extra Computation = 136
 4.6 Minimum Execution Time and Minimum Cost-Optional Execution Time = 136
 4.7 Other Scalability Metrics and Bibliographic Remarks = 139
 Problems = 141
 References = 146
CHAPTER 5 Dense Matrix Algorithms = 151
 5.1 Mapping Matrices onto Processors = 151
  5.1.1 Striped Partitioning = 151
  5.1.2 Checkerboard Partitioning = 152
 5.2 Matrix Transposition = 153
  5.2.1 Checkerboard Partitioning = 154
  5.2.2 Striped Partitioning = 159
 5.3 Matrix-Vector Multiplication = 160
  5.3.1 Rowwise Striping = 160
  5.3.2 Checkerboard Partitioning = 163
 5.4. Matrix Multiplication = 168
  5.4.1 A Simple Parallel Algorithm = 169
  5.4.2 Cannon's Algorithm = 171
  5.4.3 Fox's Algorithm = 173
  5.4.4 The DNS Algorithm = 174
 5.5 Solving a System of Linear Equations = 178
  5.5.1 A Simple Gaussian Elimination Algorithm = 179
  5.5.2 Gaussian Elimination with Partial Pivoting = 192
  5.5.3 Solving a Triangular System :Back-Substitution = 195
  5.5.4 Numerical Considerations in Solving Systems of Linear Equations = 196
 5.6 Bibliographic Remarks = 197
 Problems = 198
 References = 204
CHAPTER 6 Sorting = 209
 6.1 Issues in Sorting on Parallel Computers = 210
  6.1.1 Where the Input and Output Sequences Are Stored = 210
  6.1.2 How Comparisons Are Performed = 210
 6.2 Sorting Networks = 212
  6.2.1 Bitonic Sort = 214
  6.2.2 Mapping bitonic Sort onto a Hypercube and a Mesh = 216
 6.3 Bubble Sort and Its Variants = 224
  6.3.1 Odd-Even Transposition = 225
  6.3.2 Shellsort = 227
 6.4 Quicksort = 229
  6.4.1 Parallelizing Quicksort = 231
  6.4.2 A Comparison of Quicksort Formulations = 243
 6.5 Other Sorting Algorithms = 243
  6.5.1 Enumeration Sort = 243
  6.5.2 Bucket Sort = 244
  6.5.3 Sample Sort = 245
  6.5.4 Radix Sort = 247
 6.6 Bibliographic Remarks = 247
 Problems = 250
 References = 254
CHAPTER 7 Graph Algorithms = 257
 7.1 Definitions and Representation = 257
 7.2 Minimum Spanning tree :Prim's Algorithm = 260
 7.3 Single-Source Shortest Paths :Dijkstra's Algorithm = 265
 7.4 All-Pairs Shortest Paths = 266
  7.4.1 Matrix-Multiplication Based Algorithm = 266
  7.4.2 Dijkstra's Algorithm = 268
  7.4.3 floyd's algorithm = 271
  7.4.4 Performance Comparisons = 276
 7.5 Transitive Closure = 276
 7.6 Connected Components = 278
  7.6.1 A Depth-First Search Based Algorithm = 278
 7.7 Algorithms for Sparse Graphs = 281
  7.7.1 Single-Source Shortest Paths = 284
 7.8 Bibliographic Remarks = 290
 Problems = 293
 References = 295
CHAPTER 8 Search Algorithms for Discrete Optimization Problems = 299
 8.1 Definitions and Examples = 299
 8.2 Sequential Search Algorithms = 304
  8.2.1 Depth-First Search Algorithms = 304
  8.2.2 Best-First Search Algorithms = 308
 8.3 Search Overhead Factor = 308
 8.4 Parallel Depth-First Search = 310
  8.4.1 Important Parameters of Parallel DFS = 313
  8.4.2 A General Framework for Analysis of Parallel DFS = 315
  8.4.3 Analysis of Load-Balancing Schemes for Hypercubes = 318
  8.4.4 Analysis of Load-Balancing Schemes for a Network of Workstations = 320
  8.4.5 Termination Detection = 321
  8.4.6 Experimental Results = 325
  8.4.7 Parallel Formulations of Depth-First Branch-and-Bound Search = 328
  8.4.8 Parallel Formulations of IDA* = 328
  8.4.9 Parallel DFS on SIMD Computers = 329
 8.5 Parallel Best-First Search = 332
 8.6 Speedup Anomalies in Parallel Search Algorithms = 336
  8.6.1 Analysis of Average Speedup in Parallel DFS = 338
 8.7 Bibliographic Remarks = 340
 Problems = 343
 References = 348
CHAPTER 9 Dynamic Programming = 355
 9.1 Serial Monadic DP Formulations = 357
  9.1.1 The Shortest-Path Problem = 358
  9.1.2 The 0/1 Knapsack Problem = 360
 9.2 Nonserial Monadic DP Formulations = 362
  9.2.1 The Longest-Common-Subsequence Problem = 363
 9.3 Serial Polyadic DP Formulations = 365
  9.3.1 Floyd's All-Pairs Shortest-Paths Algorithm = 365
 9.4 Nonserial Polyadic DP Formulations = 366
  9.4.1 The Optimal Matrix-Parenthesization Problem = 366
 9.5 Summary and Discussion = 369
 9.6 Bibliographic Remarks = 370
 Problems = 371
 References = 375
CHAPTER 10 Fast Fourier Transform = 377
 10.1 The Serial Algorithm = 377
 10.2 The Binary-Exchange Algorithm = 382
  10.2.1 Hypercube = 383
  10.2.2 Mesh = 388
  10.2.3 Extra Computations in Parallel FFT = 390
 10.3 The Transpose algorithm = 393
  10.3.1 Two-Dimensional Transpose Algorithm = 393
  10.3.2 The Generalized Transpose Algorithm = 396
 10.4 Cost-Effectiveness of Meshes and Hypercubes for FFT = 400
 10.5 Bibliographic Remarks = 403
 Problems = 404
 References = 405
CHAPTER 11 Solving Sparse Systems of Linear Equations = 407
 11.1 Basic Operations = 409
  11.1.1 Storage Schemes for Sparse Matrices = 409
  11.1.2 Vector Inner Product = 412
  11.1.3 Sparse Matrix-Vector Multiplication = 413
 11.2 Iterative Methods for Sparse Linear Systems = 426
  11.2.1 Jacobi Iterative Method = 427
  11.2.2 Gauss-Seidel and SOR Methods = 429
  11.2.3 The Conjugate Gradient Method = 433
 11.3 Finite Element Method = 446
 11.4 Direct Methods for Sparse Linear systems = 454
  11.4.1 Ordering = 455
  11.4.2 Symbolic Factorization = 458
  11.4.3 Numerical Factorization = 458
  11.4.4 Solving a Triangular system = 468
 11.5 Multigrid Methods = 468
 11.6 Bibliographic Remarks = 474
 Problems = 477
 References = 482
CHAPTER 12 Systolic Algorithms and their Mapping onto Parallel Computers = 491
 12.1 Examples of Systolic Systems = 493
  12.1.1 Convolution = 493
  12.1.2 Banded Matrix-Vector Multiplication = 496
  12.1.3 Matrix Multiplication = 499
  12.1.4 Optimal Matrix Parenthesization = 501
 12.2 General Issues in Mapping Systolic Systems onto Parallel Computers = 505
  12.2.1 Architectural Differences between Systolic Arrays and Parallel Computers = 505
  12.2.2 Absolute Efficiency of Systolic Systems = 506
 12.3 Mapping One-Dimensional Systolic Arrays = 507
  12.3.1 Virtual Processors = 508
  12.3.2 Block-Striped Mapping = 508
  12.3.3 Other One-Dimensional Mappings = 511
 12.4 Mapping Two-Dimensional Systolic Arrays = 513
  12.4.1 Block-Checkerboard Mapping = 514
  12.4.2 Cyclic-Checkerboard Mapping = 516
  12.4.3 Summary of Two-Dimensional Mappings = 518
 12.5 Bibliographic Remarks = 518
 Problems = 520
 References = 521
CHAPTER13 Parallel Programming = 525
 13.1 Parallel Programming Paradigms = 525
  13.1.1 Explicit versus Implicit Parallel Programming = 525
  13.1.2 Shared-Address-Space versus Message-Passing = 526
  13.1.3 Data Parallelism versus Control Parallelism = 527
 13.2 Primitives for the Message-Passing Programming Paradigm = 529
  13.2.1 Basic Extensions = 529
  13.2.2 nCUBE2 = 531
  13.2.3 iPSC860 = 532
  13.2.4 CM-5 = 533
  13.2.5 Example Program = 535
 13.3 Data-Parallel Languages = 538
  13.3.1 Data Partitioning and Virtual Processors = 539
  13.3.2 C* = 540
  13.3.3 CM Fortran = 549
 13.4 Primitives for the Shared-Address-Space Programming Paradigm = 551
  13.4.1 Primitives to Allocate Shared Variables = 552
  13.4.2 Primitives for Mutual Exclusion and Synchronization = 552
  13.4.3 Primitives for Creating Processes = 553
  13.4.4 Sequent Symmetry = 553
  13.4.5 Example Programs = 554
 13.5 Fortran D = 558
  13.5.1 Problem Mapping = 559
  13.5.2 Machine Mapping = 561
  13.5.3 Example Program = 562
 13.6 Bibliographic Remarks = 564
 References = 566
APPENDIX A Complexity of Functions and Order Analysis = 571
Author Index = 575
Subject Index = 583


New Arrivals Books in Related Fields

Zumstein, Felix (2022)