Introduction to parallel computing: design and analysis of algorithms
1994; Linguagem: Inglês
Autores
Vipin Kumar, Ananth Grama, Anshul Gupta, George Karypis,
Tópico(s)Parallel Computing and Optimization Techniques
ResumoIntroduction. What is Parallel Computing? The Scope of Parallel Computing. Issues in Parallel Computing. Organization and Contents of The Text. Bibliographic Remarks. Problems. References. Models of Parallel Computers. A Taxonomy of Parallel Architectures. An Idealized Parallel Computer. Dynamic Interconnection Networks. Static Interconnection Networks. Embedding Other Networks Into a Hypercube. Routing Mechanisms For Static Networks. Communication Costs in Static Interconnection Networks. Cost-Performance Tradeoffs. Architectural Models For Parallel Algorithm Design. Bibliographic Remarks. References. Basic Communication Operations. Simple Message Transfer Between Two Processors. One-To-All Broadcast. All-To-All Broadcast, Reduction, and Prefix Sums. One-To-All Personalized Communications. All-To-All Personalized Communications. Circular Shift. Faster Methods For Some Communication Operations. Summary. Bibliographic Remarks. Problems. References. Performance and Scalability of Parallel Systems. Performance Metrics For Parallel Systems. The Effect of Granularity and Data Mapping On Performance. The Scalability of Parallel Systems. The Isoefficiency Metric of Scalability. Sources of Parallel Overhead. Minimum Execution Time and Minimum Cost-Optimal Execution Time. Other Scalability Metrics and Bibliographic Remarks. Problems. References. Dense Matrix Algorithms. Mapping Matrices Onto Processors. Matrix Transpositon. Matrix-Vector Multiplication. Matrix Multiplication. Solving a System of Linear Equations. Bibliographic Remarks. Problems. References. Sorting. Issues in Sorting On Parallel Computers. Sorting Networks. Bubble Sort and Its Variants. Quicksort. Other Sorting Algorithms. Bibliographic Remarks. Problems. References. Graph Algorithms. Definitions and Representation. Minimum Spanning Tree: Prim's Algorithm. Single-Source Shortest Paths: Dijkstra's Algorithms. All-Pairs Shortest Paths. Transitive Closure. Connected Components. Algorithms For Sparse Graphs. Bibliographic Remarks. Problems. References. Search Algorithms For Discrete Optimization Problems. Definitions and Examples. Sequential Search Algorithms. Search Overhead Factor. Parallel Depth-First Search. Parallel Best-First Search. Speedup Anomalies in Parallel Search Algorithms. Bibliographic Remarks. Problems. References. Dynamic Programming. Serial Monadic Dp Formulations. Nonserial Monadic Dp Formulations. Serial Polyadic Dp Formulations. Nonserial Polyadic Dp Formulations. Summary and Discussion. Bibliographic Remarks. Problems. References. Fast Fourier Transform. The Serial Algorithm. The Binary-Exchange Algorithm. The Transpose Algorithm. Cost-Effectiveness of Meshes and Hypercubes For Fft. Bibliographic Remarks. Problems. References. Solving Sparse Systems of Linear Equations. Basic Operations. Iterative Methods. Finite Element Method. Direct Methods For Sparse Linear Systems. Multigrid Methods. Bibliographic Remarks. Problems. References. Systolic Algorithms and Their Mapping Onto Parallel Computers. Examples of Systolic Systems. General Issues in Mapping Systolic Systems Onto Parallel Computers. Mapping One-Dimensional Systolic Arrays. Bibliographic Remarks. Problems. References. Parallel Programming. Parallel Programming Paradigms. Primitive For The Message-Passing Programming Paradigm. Data-Parallel Languages. Primitives For The Shared-Address-Space Programming Paradigm. Fortran D. Bibliographic Remarks. References. Appendix A. Complexity of Functions and Order Analysis. Author Index. Subject Index. 0805331700T04062001
Referência(s)