Introduction to Parallel Computing: Design and Analysis of Parallel Algorithms / Edition 5

Introduction to Parallel Computing: Design and Analysis of Parallel Algorithms / Edition 5

by Vipin Kumar, Ananth Grama, Anshul Gupta, George Karypis
     
 

ISBN-10: 0805331700

ISBN-13: 9780805331707

Pub. Date: 11/28/1993

Publisher: Addison-Wesley

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

Overview

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 ComputerScience and Computer Engineering majors
Professional/Reference
Courses:
Distributed Computing
Parallel Programming
Parallel Algorithms
Prerequisites:
Operating Systems and Analysis of Algorithms

Product Details

ISBN-13:
9780805331707
Publisher:
Addison-Wesley
Publication date:
11/28/1993
Edition description:
Older Edition
Pages:
597
Product dimensions:
6.69(w) x 9.57(h) x 1.28(d)

Table of Contents

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 andBibliographic 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.

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >