Introduction to Parallel Computing Second Edition

1 [ Team LiB ] Table of ContentsIntroduction to Parallel Computing , Second EditionBy Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar Publisher: Addison WesleyPub Date: January 16, 2003 ISBN: 0-201-64865-2 Pages: 856 Increasingly, Parallel processing is being seen as the only cost-effective method for the fastsolution of computationally large and data-intensive problems. The emergence of inexpensiveparallel computers such as commodity desktop multiprocessors and clusters of workstations orPCs has made such Parallel methods generally applicable, as have software standards forportable Parallel programming. This sets the stage for substantial growth in Parallel applications such as transaction processing and information retrieval, datamining and analysis and multimedia services have provided a new challenge for the moderngeneration of Parallel platforms.

2 Emerging areas such as computational biology andnanotechnology have implications for algorithms and systems development, while changes inarchitectures, programming models and applications have implications for how parallelplatforms are made available to users in the form of grid-based book takes into account these new developments as well as covering the more traditionalproblems addressed by Parallel possible it employs an architecture-independent view of the underlying platforms and designs algorithms for an abstract Passing Interface (MPI), POSIX threads and OpenMP have been selected asprogramming models and the evolving application mix of Parallel Computing is reflected invarious examples throughout the book.[ Team LiB ][ Team LiB ] Table of ContentsIntroduction to Parallel Computing , Second EditionBy Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar Publisher: Addison WesleyPub Date: January 16, 2003 ISBN: 0-201-64865-2 Pages: 856 Increasingly, Parallel processing is being seen as the only cost-effective method for the fastsolution of computationally large and data-intensive problems.

3 The emergence of inexpensiveparallel computers such as commodity desktop multiprocessors and clusters of workstations orPCs has made such Parallel methods generally applicable, as have software standards forportable Parallel programming. This sets the stage for substantial growth in Parallel applications such as transaction processing and information retrieval, datamining and analysis and multimedia services have provided a new challenge for the moderngeneration of Parallel platforms. Emerging areas such as computational biology andnanotechnology have implications for algorithms and systems development, while changes inarchitectures, programming models and applications have implications for how parallelplatforms are made available to users in the form of grid-based book takes into account these new developments as well as covering the more traditionalproblems addressed by Parallel possible it employs an architecture-independent view of the underlying platforms and designs algorithms for an abstract Passing Interface (MPI)

4 , POSIX threads and OpenMP have been selected asprogramming models and the evolving application mix of Parallel Computing is reflected invarious examples throughout the book.[ Team LiB ][ Team LiB ] Table of ContentsIntroduction to Parallel Computing , Second EditionBy Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar Publisher: Addison WesleyPub Date: January 16, 2003 ISBN: 0-201-64865-2 Pages: 856 Copyright Pearson Education Preface Acknowledgments Chapter 1. Introduction to Parallel Computing Section Motivating Parallelism Section Scope of Parallel Computing Section Organization and Contents of the Text Section Bibliographic Remarks Problems Chapter 2. Parallel Programming Platforms Section Implicit Parallelism: Trends in Microprocessor Architectures* Section Limitations of Memory System Performance* Section Dichotomy of Parallel Computing Platforms Section Physical Organization of Parallel Platforms Section Communication Costs in Parallel Machines Section Routing Mechanisms for Interconnection Networks Section Impact of Process-Processor Mapping and Mapping Techniques Section Bibliographic Remarks Problems Chapter 3.

5 Principles of Parallel Algorithm Design Section Preliminaries Section Decomposition Techniques Section Characteristics of Tasks and Interactions Section Mapping Techniques for Load Balancing Section Methods for Containing Interaction Overheads Section Parallel Algorithm Models Section Bibliographic Remarks Problems Chapter 4. Basic Communication Operations Section One-to-All Broadcast and All-to-One Reduction Section All-to-All Broadcast and Reduction Section All-Reduce and Prefix-Sum Operations Section Scatter and Gather Section All-to-All Personalized Communication Section Circular Shift Section Improving the Speed of Some Communication Operations Section Summary Section Bibliographic Remarks Problems Chapter 5.

6 Analytical Modeling of Parallel Programs Section Sources of Overhead in Parallel Programs Section Performance Metrics for Parallel Systems Section The Effect of Granularity on Performance Section Scalability of Parallel Systems Section Minimum Execution Time and Minimum Cost-Optimal Execution Time Section Asymptotic Analysis of Parallel Programs Section Other Scalability Metrics Section Bibliographic Remarks Problems Chapter 6. Programming Using the Message-Passing Paradigm Section Principles of Message-Passing Programming Section The Building Blocks: Send and Receive Operations Section MPI: the Message Passing Interface Section Topologies and Embedding Section Overlapping Communication with Computation Section Collective Communication and Computation Operations Section Groups and Communicators Section Bibliographic Remarks Problems Chapter 7.

7 Programming Shared Address Space Platforms Section Thread Basics Section Why Threads? Section The POSIX Thread API Section Thread Basics: Creation and Termination Section Synchronization Primitives in Pthreads Section Controlling Thread and Synchronization Attributes Section Thread Cancellation Section Composite Synchronization Constructs Section Tips for Designing Asynchronous Programs Section OpenMP: a Standard for Directive Based Parallel Programming Section Bibliographic Remarks Problems Chapter 8. Dense Matrix Algorithms Section Matrix-Vector Multiplication Section Matrix-Matrix Multiplication Section Solving a System of Linear Equations Section Bibliographic Remarks Problems Chapter 9.

8 Sorting Section Issues in Sorting on Parallel Computers Section Sorting Networks Section Bubble Sort and its Variants Section Quicksort Section Bucket and Sample Sort Section Other Sorting Algorithms Section Bibliographic Remarks Problems Chapter 10. Graph Algorithms Section Definitions and Representation Section Minimum Spanning Tree: Prim's Algorithm Section Single-Source Shortest Paths: Dijkstra's Algorithm Section All-Pairs Shortest Paths Section Transitive Closure Section Connected Components Section Algorithms for Sparse Graphs Section Bibliographic Remarks Problems Chapter 11. Search Algorithms for Discrete Optimization Problems Section Definitions and Examples Section Sequential Search Algorithms Section Search Overhead Factor Section Parallel Depth-First Search Section Parallel Best-First Search Section Speedup Anomalies in Parallel Search Algorithms Section Bibliographic Remarks Problems Chapter 12.

9 Dynamic Programming Section Overview of Dynamic Programming Section Serial Monadic DP Formulations Section Nonserial Monadic DP Formulations Section Serial Polyadic DP Formulations Section Nonserial Polyadic DP Formulations Section Summary and Discussion Section Bibliographic Remarks Problems Chapter 13. Fast Fourier Transform Section The Serial Algorithm Section The Binary-Exchange Algorithm Section The Transpose Algorithm Section Bibliographic Remarks Problems Appendix A. Complexity of Functions and Order Analysis Section Complexity of Functions Section Order Analysis of Functions Bibliography[ Team LiB ] [ Team LiB ] CopyrightPearson Education LimitedEdinburgh GateHarlowEssex CM20 2 JEEnglandand Associated Companies throughout the worldVisit us on the World Wide Web at: published by The Benjamin/Cummings Publishing Company, Inc.

10 1994 Second Edition published 2003 The Benjamin/Cummings Publishing Company, Inc. 1994 Pearson Education Limited 2003 The rights of Ananth Grama, Anshul Gupta, George Karypis and Vipin Kumar to be identified asauthors of this work have been asserted by them in accordance with the Copyright, Designs andPatents Act rights reserved. No part of this publication may be reproduced, stored in a retrieval system,or transmitted in any form or by any means, electronic, mechanical, photocopying, recording orotherwise, without either the prior written permission of the publisher or a licence permittingrestricted copying in the United Kingdom issued by the Copyright Licensing Agency Ltd, 90 Tottenham Court Road, London W1T programs in this book have been included for their instructional value.