Team LiB 1 NEXT Parallel Computing Table of Contents Introduction to Parallel Computing,Second Edition By Ananth Grama,Anshul Gupta,George Karypis,Vipin Kumar Start Reading Publisher Addison Wesley Pub 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 fast solution of computationally large and data-intensive problems.The emergence of inexpensive parallel computers such as commodity desktop multiprocessors and clusters of workstations or PCs has made such parallel methods generally applicable,as have software standards for portable parallel programming.This sets the stage for substantial growth in parallel software. Data-intensive applications such as transaction processing and information retrieval,data mining and analysis and multimedia services have provided a new challenge for the modern generation of parallel platforms.Emerging areas such as computational biology and nanotechnology have implications for algorithms and systems development,while changes in architectures,programming models and applications have implications for how parallel platforms are made available to users in the form of grid- based services. This book takes into account these new developments as well as covering the more traditional problems addressed by parallel computers.Where possible it employs an architecture-independent view of the underlying platforms and designs algorithms for an abstract model.Message Passing Interface(MPI) POSIX threads and OpenMP have been selected as programming models and the evolving application mix of parallel computing is reflected in various examples throughout the book. Team LiB 1 NEXT
Increasingly, parallel processing is being seen as the only cost-effective method for the fast solution of computationally large and data-intensive problems. The emergence of inexpensive parallel computers such as commodity desktop multiprocessors and clusters of workstations or PCs has made such parallel methods generally applicable, as have software standards for portable parallel programming. This sets the stage for substantial growth in parallel software. Data-intensive applications such as transaction processing and information retrieval, data mining and analysis and multimedia services have provided a new challenge for the modern generation of parallel platforms. Emerging areas such as computational biology and nanotechnology have implications for algorithms and systems development, while changes in architectures, programming models and applications have implications for how parallel platforms are made available to users in the form of gridbased services. This book takes into account these new developments as well as covering the more traditional problems addressed by parallel computers.Where possible it employs an architecture-independent view of the underlying platforms and designs algorithms for an abstract model. Message Passing Interface (MPI), POSIX threads and OpenMP have been selected as programming models and the evolving application mix of parallel computing is reflected in various examples throughout the book. [ Team LiB ] • Table of Contents Introduction to Parallel Computing, Second Edition By Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar Publisher : Addison Wesley Pub Date : January 16, 2003 ISBN : 0-201-64865-2 Pages : 856 [ Team LiB ] Page 1 of 1 file://C:\Documents and Settings\CIC000\Local Settings\Temp\~hhBFDD.htm 2/8/2013
Team LiB 1 4 PREVIOUS NEXT Parallel Computing Table of Contents Introduction to Parallel Computing,Second Edition By Ananth Grama,Anshul Gupta,George Karypis,Vipin Kumar Start Reading Publisher Addison Wesley Pub Date January 16,2003 ISBN :0-201-64865-2 Pages :856 Copyright Pearson Education Preface Acknowledgments Chapter 1.Introduction to Parallel Computing Section 1.1.Motivating Parallelism Section 1.2.Scope of Parallel Computing Section 1.3.Organization and Contents of the Text Section 1.4.Bibliographic Remarks Problems Chapter 2.Parallel Programming Platforms Section 2.1.Implicit Parallelism:Trends in Microprocessor Architectures+ Section 2.2.Limitations of Memory System Performance* Section 2.3.Dichotomy of Parallel Computing Platforms Section 2.4.Physical Organization of Parallel Platforms Section 2.5.Communication Costs in Parallel Machines Section 2.6.Routing Mechanisms for Interconnection Networks Section 2.7.Impact of Process-Processor Mapping and Mapping Techniques Section 2.8.Bibliographic Remarks Problems Chapter 3.Principles of Parallel Algorithm Design Section 3.1.Preliminaries Section 3.2.Decomposition Techniques Section 3.3.Characteristics of Tasks and Interactions Section 3.4.Mapping Techniques for Load Balancing Section 3.5.Methods for Containing Interaction Overheads Section 3.6.Parallel Algorithm Models Section 3.7.Bibliographic Remarks Problems Chapter 4.Basic Communication Operations Section 4.1.One-to-All Broadcast and All-to-One Reduction
[ Team LiB ] • Table of Contents Introduction to Parallel Computing, Second Edition By Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar Publisher : Addison Wesley Pub Date : January 16, 2003 ISBN : 0-201-64865-2 Pages : 856 Copyright Pearson Education Preface Acknowledgments Chapter 1. Introduction to Parallel Computing Section 1.1. Motivating Parallelism Section 1.2. Scope of Parallel Computing Section 1.3. Organization and Contents of the Text Section 1.4. Bibliographic Remarks Problems Chapter 2. Parallel Programming Platforms Section 2.1. Implicit Parallelism: Trends in Microprocessor Architectures* Section 2.2. Limitations of Memory System Performance* Section 2.3. Dichotomy of Parallel Computing Platforms Section 2.4. Physical Organization of Parallel Platforms Section 2.5. Communication Costs in Parallel Machines Section 2.6. Routing Mechanisms for Interconnection Networks Section 2.7. Impact of Process-Processor Mapping and Mapping Techniques Section 2.8. Bibliographic Remarks Problems Chapter 3. Principles of Parallel Algorithm Design Section 3.1. Preliminaries Section 3.2. Decomposition Techniques Section 3.3. Characteristics of Tasks and Interactions Section 3.4. Mapping Techniques for Load Balancing Section 3.5. Methods for Containing Interaction Overheads Section 3.6. Parallel Algorithm Models Section 3.7. Bibliographic Remarks Problems Chapter 4. Basic Communication Operations Section 4.1. One-to-All Broadcast and All-to-One Reduction Page 1 of 3 mk:@MSITStore:F:\Reading\Parallel%20Programming\[Introduction%20to%20Parallel%20Computing,%2... 2/8/2013
Section 4.2.All-to-All Broadcast and Reduction Section 4.3.All-Reduce and Prefix-Sum Operations Section 4.4.Scatter and Gather Section 4.5.All-to-All Personalized Communication Section 4.6.Circular Shift Section 4.7.Improving the speed of Some Communication Operations Section 4.8.Summary Section 4.9.Bibliographic Remarks Problems Chapter 5.Analytical Modeling of Parallel Programs Section 5.1.Sources of Overhead in Parallel Programs Section 5.2.Performance Metrics for Parallel Systems Section 5.3.The Effect of Granularity on Performance Section 5.4.Scalability of Parallel Systems Section 5.5.Minimum Execution Time and Minimum Cost-Optimal Execution Time Section 5.6.Asymptotic Analysis of Parallel Programs Section 5.7.Other Scalability Metrics Section 5.8.Bibliographic Remarks Problems Chapter 6.Programming Using the Message-Passing Paradigm Section 6.1.Principles of Message-Passing Programming Section 6.2.The Building Blocks:Send and Receive operations Section 6.3.MPI:the Message Passing Interface Section 6,4.Topologies and Embedding Section 6.5.Overlapping Communication with Computation Section 6.6.Collective Communication and Computation Operations Section 6.7.Groups and Communicators Section 6.8.Bibliographic Remarks Problems Chapter 7.Programming Shared Address Space Platforms Section 7.1.Thread Basics Section 72.Why Threads? Section 7.3.The POSIX Thread API Section 7.4.Thread Basics:Creation and Termination Section 7.5.Synchronization Primitives in Pthreads Section 7.6.Controlling Thread and Synchronization Attributes Section 7.7.Thread Cancellation Section 7.8.Composite Synchronization Constructs Section 7.9.Tips for Designing Asynchronous Programs Section 7.10.OpenMP:a Standard for Directive Based Parallel Programming Section 7.11.Bibliographic Remarks Problems Chapter 8.Dense Matrix Algorithms Section 8.1.Matrix-Vector Multiplication Section 8.2.Matrix-Matrix Multiplication Section 8.3.Solving a System of Linear Equations Section 8,4.Bibliographic Remarks Problems Chapter 9.Sorting Section 9.1.Issues in Sorting on Parallel Computers Section 9.2.Sorting Networks Section 9.3.Bubble Sort and its Variants Section 9.4.Quicksort Section 9.5.Bucket and Sample Sort
Section 4.2. All-to-All Broadcast and Reduction Section 4.3. All-Reduce and Prefix-Sum Operations Section 4.4. Scatter and Gather Section 4.5. All-to-All Personalized Communication Section 4.6. Circular Shift Section 4.7. Improving the Speed of Some Communication Operations Section 4.8. Summary Section 4.9. Bibliographic Remarks Problems Chapter 5. Analytical Modeling of Parallel Programs Section 5.1. Sources of Overhead in Parallel Programs Section 5.2. Performance Metrics for Parallel Systems Section 5.3. The Effect of Granularity on Performance Section 5.4. Scalability of Parallel Systems Section 5.5. Minimum Execution Time and Minimum Cost-Optimal Execution Time Section 5.6. Asymptotic Analysis of Parallel Programs Section 5.7. Other Scalability Metrics Section 5.8. Bibliographic Remarks Problems Chapter 6. Programming Using the Message-Passing Paradigm Section 6.1. Principles of Message-Passing Programming Section 6.2. The Building Blocks: Send and Receive Operations Section 6.3. MPI: the Message Passing Interface Section 6.4. Topologies and Embedding Section 6.5. Overlapping Communication with Computation Section 6.6. Collective Communication and Computation Operations Section 6.7. Groups and Communicators Section 6.8. Bibliographic Remarks Problems Chapter 7. Programming Shared Address Space Platforms Section 7.1. Thread Basics Section 7.2. Why Threads? Section 7.3. The POSIX Thread API Section 7.4. Thread Basics: Creation and Termination Section 7.5. Synchronization Primitives in Pthreads Section 7.6. Controlling Thread and Synchronization Attributes Section 7.7. Thread Cancellation Section 7.8. Composite Synchronization Constructs Section 7.9. Tips for Designing Asynchronous Programs Section 7.10. OpenMP: a Standard for Directive Based Parallel Programming Section 7.11. Bibliographic Remarks Problems Chapter 8. Dense Matrix Algorithms Section 8.1. Matrix-Vector Multiplication Section 8.2. Matrix-Matrix Multiplication Section 8.3. Solving a System of Linear Equations Section 8.4. Bibliographic Remarks Problems Chapter 9. Sorting Section 9.1. Issues in Sorting on Parallel Computers Section 9.2. Sorting Networks Section 9.3. Bubble Sort and its Variants Section 9.4. Quicksort Section 9.5. Bucket and Sample Sort Page 2 of 3 mk:@MSITStore:F:\Reading\Parallel%20Programming\[Introduction%20to%20Parallel%20Computing,%2... 2/8/2013
Section 9.6.Other Sorting Algorithms Section 9.7.Bibliographic Remarks Problems Chapter 10.Graph Algorithms Section 10.1.Definitions and Representation Section 10.2.Minimum Spanning Tree:Prim's Algorithm Section 10.3.Single-Source Shortest Paths:Dijkstra's Algorithm Section 10.4.All-Pairs Shortest Paths Section 10.5.Transitive Closure Section 10.6.Connected Components Section 10.7.Algorithms for Sparse Graphs Section 10.8.Bibliographic Remarks Problems Chapter 11.Search Algorithms for Discrete Optimization Problems Section 11.1.Definitions and Examples Section 11.2.Sequential Search Algorithms Section 11.3.Search Overhead Factor Section 11.4.Parallel Depth-First Search Section 11.5.Parallel Best-First Search Section 11.6.Speedup Anomalies in Parallel Search Algorithms Section 11.7.Bibliographic Remarks Problems Chapter 12.Dynamic Programming Section 12.1.Overview of Dynamic Programming Section 12.2.Serial Monadic DP Formulations Section 12.3.Nonserial Monadic DP Formulations Section 12.4.Serial Polyadic DP Formulations Section 12.5.Nonserial Polyadic DP Formulations Section 12.6.Summary and Discussion Section 12.7.Bibliographic Remarks Problems Chapter 13.Fast Fourier Transform Section 13.1.The Serial Algorithm Section 13.2.The Binary-Exchange Algorithm Section 13.3.The Transpose Algorithm Section 13.4.Bibliographic Remarks Problems Appendix A.Complexity of Functions and Order Analysis Section A.1.Complexity of Functions Section A.2.Order Analysis of Functions Bibliography Team LiB 1 PREVIOUS NEXT
Section 9.6. Other Sorting Algorithms Section 9.7. Bibliographic Remarks Problems Chapter 10. Graph Algorithms Section 10.1. Definitions and Representation Section 10.2. Minimum Spanning Tree: Prim's Algorithm Section 10.3. Single-Source Shortest Paths: Dijkstra's Algorithm Section 10.4. All-Pairs Shortest Paths Section 10.5. Transitive Closure Section 10.6. Connected Components Section 10.7. Algorithms for Sparse Graphs Section 10.8. Bibliographic Remarks Problems Chapter 11. Search Algorithms for Discrete Optimization Problems Section 11.1. Definitions and Examples Section 11.2. Sequential Search Algorithms Section 11.3. Search Overhead Factor Section 11.4. Parallel Depth-First Search Section 11.5. Parallel Best-First Search Section 11.6. Speedup Anomalies in Parallel Search Algorithms Section 11.7. Bibliographic Remarks Problems Chapter 12. Dynamic Programming Section 12.1. Overview of Dynamic Programming Section 12.2. Serial Monadic DP Formulations Section 12.3. Nonserial Monadic DP Formulations Section 12.4. Serial Polyadic DP Formulations Section 12.5. Nonserial Polyadic DP Formulations Section 12.6. Summary and Discussion Section 12.7. Bibliographic Remarks Problems Chapter 13. Fast Fourier Transform Section 13.1. The Serial Algorithm Section 13.2. The Binary-Exchange Algorithm Section 13.3. The Transpose Algorithm Section 13.4. Bibliographic Remarks Problems Appendix A. Complexity of Functions and Order Analysis Section A.1. Complexity of Functions Section A.2. Order Analysis of Functions Bibliography [ Team LiB ] Page 3 of 3 mk:@MSITStore:F:\Reading\Parallel%20Programming\[Introduction%20to%20Parallel%20Computing,%2... 2/8/2013
Team LiB 1 PREVIOUS NEXT Preface Since the 1994 release of the text "Introduction to Parallel Computing:Design and Analysis of Algorithms"by the same authors,the field of parallel computing has undergone significant changes.Whereas tightly coupled scalable message-passing platforms were the norm a decade ago,a significant portion of the current generation of platforms consists of inexpensive clusters of workstations,and multiprocessor workstations and servers. Programming models for these platforms have also evolved over this time.Whereas most machines a decade back relied on custom APIs for messaging and loop-based parallelism,current models standardize these APIs across platforms.Message passing libraries such as PVM and MPI,thread libraries such as POSIX threads,and directive based models such as OpenMP are widely accepted as standards,and have been ported to a variety of platforms. With respect to applications,fluid dynamics,structural mechanics,and signal processing formed dominant applications a decade back.These applications continue to challenge the current generation of parallel platforms. However,a variety of new applications have also become important.These include data-intensive applications such as transaction processing and information retrieval,data mining and analysis,and multimedia services. Applications in emerging areas of computational biology and nanotechnology pose tremendous challenges for algorithms and systems development.Changes in architectures,programming models,and applications are also being accompanied by changes in how parallel platforms are made available to the users in the form of grid-based services. This evolution has a profound impact on the process of design,analysis,and implementation of parallel algorithms.Whereas the emphasis of parallel algorithm design a decade back was on precise mapping of tasks to specific topologies such as meshes and hypercubes,current emphasis is on programmability and portability,both from points of view of algorithm design and implementation.To this effect,where possible,this book employs an architecture independent view of the underlying platforms and designs algorithms for an abstract model.With respect to programming models,Message Passing Interface(MPI),POSIX threads,and OpenMP have been selected.The evolving application mix for parallel computing is also reflected in various examples in the book. This book forms the basis for a single concentrated course on parallel computing or a two-part sequence.Some suggestions for such a two-part sequence are: 1.Introduction to Parallel Computing:Chapters 1-6.This course would provide the basics of algorithm design and parallel programming. 2.Design and Analysis of Parallel Algorithms:Chapters 2 and 3 followed by Chapters 8-12.This course would provide an in-depth coverage of design and analysis of various parallel algorithms. The material in this book has been tested in Parallel Algorithms and Parallel Computing courses at the University of Minnesota and Purdue University.These courses are taken primarily by graduate students and senior-level undergraduate students in Computer Science.In addition,related courses in Scientific Computation,for which this material has also been tested,are taken by graduate students in science and engineering,who are interested in solving computationally intensive problems Most chapters of the book include (i)examples and illustrations;(ii)problems that supplement the text and test students'understanding of the material;and (iii)bibliographic remarks to aid researchers and students interested in learning more about related and advanced topics.The comprehensive subject index helps the reader locate terms they might be interested in.The page number on which a term is defined is highlighted in boldface in the index.Furthermore,the term itself appears in bold italics where it is defined.The sections that deal with relatively complex material are preceded by a '*'An instructors'manual containing slides of the figures and solutions to selected problems is also available from the publisher (http://www.booksites.net/kumar). As with our previous book,we view this book as a continually evolving resource.We thank all the readers who have kindly shared critiques,opinions,problems,code,and other information relating to our first book.It is our sincere hope that we can continue this interaction centered around this new book.We encourage readers to address communication relating to this book to book-yk@cs.umn,edu.All relevant reader input will be added to the information archived at the site http://www.cs.umn.edu/~parbook with due credit to (and permission of)the sender(s).An on-line errata of the book will also be maintained at the site.We believe that in a highly dynamic field such as ours,a lot is to be gained from a healthy exchange of ideas and material in this manner Team LiB 4FREVIOUS NEXT
[ Team LiB ] Preface Since the 1994 release of the text "Introduction to Parallel Computing: Design and Analysis of Algorithms" by the same authors, the field of parallel computing has undergone significant changes. Whereas tightly coupled scalable message-passing platforms were the norm a decade ago, a significant portion of the current generation of platforms consists of inexpensive clusters of workstations, and multiprocessor workstations and servers. Programming models for these platforms have also evolved over this time. Whereas most machines a decade back relied on custom APIs for messaging and loop-based parallelism, current models standardize these APIs across platforms. Message passing libraries such as PVM and MPI, thread libraries such as POSIX threads, and directive based models such as OpenMP are widely accepted as standards, and have been ported to a variety of platforms. With respect to applications, fluid dynamics, structural mechanics, and signal processing formed dominant applications a decade back. These applications continue to challenge the current generation of parallel platforms. However, a variety of new applications have also become important. These include data-intensive applications such as transaction processing and information retrieval, data mining and analysis, and multimedia services. Applications in emerging areas of computational biology and nanotechnology pose tremendous challenges for algorithms and systems development. Changes in architectures, programming models, and applications are also being accompanied by changes in how parallel platforms are made available to the users in the form of grid-based services. This evolution has a profound impact on the process of design, analysis, and implementation of parallel algorithms. Whereas the emphasis of parallel algorithm design a decade back was on precise mapping of tasks to specific topologies such as meshes and hypercubes, current emphasis is on programmability and portability, both from points of view of algorithm design and implementation. To this effect, where possible, this book employs an architecture independent view of the underlying platforms and designs algorithms for an abstract model. With respect to programming models, Message Passing Interface (MPI), POSIX threads, and OpenMP have been selected. The evolving application mix for parallel computing is also reflected in various examples in the book. This book forms the basis for a single concentrated course on parallel computing or a two-part sequence. Some suggestions for such a two-part sequence are: 1. Introduction to Parallel Computing: Chapters 1–6. This course would provide the basics of algorithm design and parallel programming. 2. Design and Analysis of Parallel Algorithms: Chapters 2 and 3 followed by Chapters 8–12. This course would provide an in-depth coverage of design and analysis of various parallel algorithms. The material in this book has been tested in Parallel Algorithms and Parallel Computing courses at the University of Minnesota and Purdue University. These courses are taken primarily by graduate students and senior-level undergraduate students in Computer Science. In addition, related courses in Scientific Computation, for which this material has also been tested, are taken by graduate students in science and engineering, who are interested in solving computationally intensive problems. Most chapters of the book include (i) examples and illustrations; (ii) problems that supplement the text and test students' understanding of the material; and (iii) bibliographic remarks to aid researchers and students interested in learning more about related and advanced topics. The comprehensive subject index helps the reader locate terms they might be interested in. The page number on which a term is defined is highlighted in boldface in the index. Furthermore, the term itself appears in bold italics where it is defined. The sections that deal with relatively complex material are preceded by a '*'. An instructors' manual containing slides of the figures and solutions to selected problems is also available from the publisher (http://www.booksites.net/kumar). As with our previous book, we view this book as a continually evolving resource. We thank all the readers who have kindly shared critiques, opinions, problems, code, and other information relating to our first book. It is our sincere hope that we can continue this interaction centered around this new book. We encourage readers to address communication relating to this book to book-vk@cs.umn.edu. All relevant reader input will be added to the information archived at the site http://www.cs.umn.edu/~parbook with due credit to (and permission of) the sender(s). An on-line errata of the book will also be maintained at the site. We believe that in a highly dynamic field such as ours, a lot is to be gained from a healthy exchange of ideas and material in this manner. [ Team LiB ] Page 1 of 1 file://C:\Documents and Settings\CIC000\Local Settings\Temp\~hh41E9.htm 2/8/2013