Introduction to Parallel Computing
Design Analysis of Parallel Algorithms
Published on 19. January 1994
Book
Paperback/Softback
597 pages
978-0-8053-3170-7 (ISBN)
Description
Take an in-depth look at techniques for the design and analysis of parallel algorithms with this new text. The broad, balanced coverage of important core topics includes sorting and graph algorithms, discrete optimization techniques, and scientific computing applications. The authors focus on parallel algorithms for realistic machine models while avoiding architectures that are unrealizable in practice. They provide numerous examples and diagrams illustrating potentially difficult subjects and conclude each chapter with an extensive list of bibliographic references. In addition, problems of varying degrees of difficulty challenge readers at different levels. Introduction to Parallel Computing is an ideal tool for students and professionals who want insight into problem-solving with parallel computers. Features: *Presents parallel algorithms in terms of a small set of basic data communication operations, greatly simplifying the design and understanding of these algorithms. *Emphasizes practical issues of performance, efficiency, and scalability. *Provides a self-contained discussion of the basic concepts of parallel computer architectures.
*Covers algorithms for scientific computation, such as dense and sparse matrix computations, linear system solving, finite elements, and FFT. *Discusses algorithms for combinatorial optimization, including branch-and-bound, unstructured tree search, and dynamic programming. *Incorporates various parallel programming models and languages as well as illustrative examples for commercially-available computers. Audience: Junior/Senior/Graduate Computer Science and Computer Engineering majors Professional/Reference Courses: Distributed Computing Parallel Programming Parallel Algorithms Prerequisites: Operating Systems and Analysis of Algorithms 0805331700B04062001
*Covers algorithms for scientific computation, such as dense and sparse matrix computations, linear system solving, finite elements, and FFT. *Discusses algorithms for combinatorial optimization, including branch-and-bound, unstructured tree search, and dynamic programming. *Incorporates various parallel programming models and languages as well as illustrative examples for commercially-available computers. Audience: Junior/Senior/Graduate Computer Science and Computer Engineering majors Professional/Reference Courses: Distributed Computing Parallel Programming Parallel Algorithms Prerequisites: Operating Systems and Analysis of Algorithms 0805331700B04062001
More details
Language
English
Place of publication
Upper Saddle River
United States
Target group
College/higher education
Dimensions
Height: 243 mm
Width: 170 mm
Thickness: 30 mm
Weight
960 gr
ISBN-13
978-0-8053-3170-7 (9780805331707)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
New editions
Ananth Grama | George Karypis | Vipin Kumar
Introduction to Parallel Computing
Book
02/2003
2nd Edition
Addison Wesley
€71.79
Shipment within 3-4 weeks
Content
Introduction.
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
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