并行计算导论（英文版·第2版） (2008 年度畅销榜NO.6909 )

在快速解决计算量大、数据密集型问题时，人们越采越认识到并行处理是惟一节省成本的方法。价格低廉的并行计算机(如商用桌面多处理机和工作站机群)的出现，使得这种并行方法的适用范围越来越广。现在已经为可移植的并行程序设计制定了专门的软件标准，为并行软件的大幅度发展打好了基础。\r\n\r\n 事务处理。信息检索．数据挖掘和分析以及多媒体服务等数据密集型应用已经为当代的并行平台提供了新的挑战。计算生物学和纳米技术等新兴的领域对并行计算的算法和系统开发提供了前瞻性的启示，而体系结构，编程模型和应用中的变化对如何使用户以网格服务形式得到并行平台也提供了一些启发。\r\n\r\n 本书讨论了这些新技术的发展，也覆盖了并行计算机处理的较传统的问题．本书尽可能采用与体系结构无关的观点来对待抽象模型的底层平台和设计算法。书中选择MPI(Message Passing Interface)、POSIX线程和Open MP作为编程模型，并在不同例子中反映了并行计算的不断变化的应用组合。\r\n\r\n本书的主要特点：\r\n\r\n 全面介绍并行计算的每个方面(体系结构，编程范型。算法和标准)既讲述传统的计算机科学算法(排序，搜索。图和动态编程算法)，也讲述科学计算算法(矩阵计算、FFT)\r\n\r\n介绍MPI、Pthreads和OpenMP这三个应用最广泛的编写可移植并行程序的标准适合作为高等院校并行计算。并行编程，并行算法的设计和分析以及高性能计算课程的本科生和研究生的教材\r\n\r\n 作者简介\r\n\r\n Ananth Grama普度大学计算机科学系的副教授，研究领域是并行和分布式系统和应用的不同方面。\r\n\r\nAnshuI GUpta IBM T．J．Watson Research Center的研究人员，研究领域是并行算法和科学计算．George Karypis明尼苏达大学计算机科学和工程系的副教授，研究领域是并行算法设计、数据挖掘和生物信息学等。\r\n\r\nVipin Kumar明尼苏达大学计算机科学和工程系的教授和军用高性能计算研究中心的主管．研究领域是高性能计算。用子科学计算问题和数据挖掘的并行算法。\r\n
\r\n

Introduction to Parallel Computing \r\n\r\n 1.1 Motivating Parallelism \r\n\r\n 1.2 Scope of Parallel Computing \r\n\r\n 1.3 Organization and Contents of the Text \r\n\r\n 1.4 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 2 \r\n\r\n Parallel Programming Platforms \r\n\r\n 2.1 Implicit Parallelism: Trends in Microprocessor Architectures \r\n\r\n 2.2 Limitations of Memory System Performance* \r\n\r\n 2.3 Dichotomy of Parallel Computing Platforms \r\n\r\n 2.4 Physical Organization of Parallel Platforms \r\n\r\n 2.5 Communication Costs in Parallel Machines \r\n\r\n 2.6 Routing Mechanisms for Interconnection Networks \r\n\r\n 2.7 Impact of Process-Processor Mapping and Mapping Techniques \r\n\r\n 2.8 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER \r\n\r\n Principles of Parallel Algorithm Design \r\n\r\n 3.1 Preliminaries \r\n\r\n 3.2 Decomposition Techniques \r\n\r\n 3.3 Characteristics of Tasks and Interactions \r\n\r\n 3.4 Mapping Techniques for Load Balancing \r\n\r\n 3.5 Methods for Containing Interaction Overheads \r\n\r\n 3.6 Parallel Algorithm Models \r\n\r\n 3.7 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 4 \r\n\r\n Basic Communication Operations \r\n\r\n 4.1 One-to-All Broadcast and All-to-One Reduction \r\n\r\n 4.2 All-to-All Broadcast and Reduction \r\n\r\n 4.3 All-Reduce and Prefix-Sum Operations \r\n\r\n 4.4 Scatter and Gather \r\n\r\n 4.5 All-to-All Personalized Communication \r\n\r\n 4.6 Circular Shift \r\n\r\n 4.7 Improving the Speed of Some Communication Operations \r\n\r\n 4.8 Summary \r\n\r\n 4.9 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 5 \r\n\r\n Analytical Modeling of Parallel Programs \r\n\r\n 5.1 Sources of Overhead in Parallel Programs \r\n\r\n 5.2 Performance Metrics for Parallel Systems \r\n\r\n 5.3 The Effect of Granularity on Performance \r\n\r\n 5.4 Scalability of Parallel Systems \r\n\r\n 5.5 Minimum Execution Time and Minimum Cost-Optimal Execution Time \r\n\r\n 5.6 Asymptotic Analysis of Parallel Programs \r\n\r\n 5.7 Other Scalability Metrics \r\n\r\n 5.8 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 6 \r\n\r\n Programming Using the Message-Passing \r\n\r\n Paradigm \r\n\r\n 6.1 Principles of Message-Passing Programming \r\n\r\n 6.2 The Building Blocks: Send and Receive Operations \r\n\r\n 6.3 MPI: the Message Passing Interface \r\n\r\n 6.4 Topologies and Embedding \r\n\r\n 6.5 Overlapping Communication with Computation \r\n\r\n 6.6 Collective Communication and Computation Operations \r\n\r\n 6.7 Groups and Communicators \r\n\r\n 6.8 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 7 \r\n\r\n Programming Shared Address Space \r\n\r\n Platforms \r\n\r\n 7.1 Thread Basics \r\n\r\n 7.2 Why Threads? \r\n\r\n 7.3 The POSIX Thread API \r\n\r\n 7.4 Thread Basics: Creation and Termination \r\n\r\n 7.5 Synchronization Primitives in Pthreads \r\n\r\n 7.6 Controlling Thread and Synchronization Attributes \r\n\r\n 7.7 Thread Cancellation \r\n\r\n 7.8 Composite Synchronization Constructs \r\n\r\n 7.9 Tips for Designing Asynchronous Programs \r\n\r\n 7.10 OpenMP: a Standard for Directive Based Parallel Programming \r\n\r\n 7.11 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 8 \r\n\r\n Dense Matrix Algorithms \r\n\r\n 8.1 Matrix-Vector Multiplication \r\n\r\n 8.2 Matrix-Matrix Multiplication \r\n\r\n 8.3 Solving a System of Linear Equations \r\n\r\n 8.4 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 9 \r\n\r\n Sorting \r\n\r\n 9.1 Issues in Sorting on Parallel Computers \r\n\r\n 9.2 Sorting Networks \r\n\r\n 9.3 Bubble Sort and its Variants \r\n\r\n 9.4 Quicksort \r\n\r\n 9.5 Bucket and Sample Sort \r\n\r\n 9.6 Other Sorting Algorithms \r\n\r\n 9.7 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 10 \r\n\r\n Graph Algorithms \r\n\r\n 10.1 Definitions and Representation \r\n\r\n 10.2 Minimum Spanning Tree: Prim's Algorithm \r\n\r\n 10.3 Single-Source Shortest Paths: Dijkstra's Algorithm \r\n\r\n 10.4 All-Pairs Shortest Paths \r\n\r\n 10.5 Transitive Closure \r\n\r\n 10.6 Connected Components \r\n\r\n 10.7 Algorithms for Sparse Graphs \r\n\r\n 10.8 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 11 \r\n\r\n Search Algorithms for Discrete Optimization \r\n\r\n Problems \r\n\r\n 11.1 Definitions and Examples \r\n\r\n 11.2 Sequential Search Algorithms \r\n\r\n 11.3 Search Overhead Factor \r\n\r\n 11.4 Parallel Depth-First Search \r\n\r\n 11.5 Parallel Best-First Search \r\n\r\n 11.6 Speedup Anomalies in Parallel Search Algorithms \r\n\r\n 11.7 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 12 \r\n\r\n Dynamic Programming \r\n\r\n 12.1 Overview of Dynamic Programming \r\n\r\n 12.2 Serial Monadic DP Formulations \r\n\r\n 12.3 Nonserial Monadic DP Formulations \r\n\r\n 12.4 Serial Polyadic DP Formulations \r\n\r\n 12.5 Nonserial Polyadic DP Formulations \r\n\r\n 12.6 Summary and Discussion \r\n\r\n 12.7 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n CHAPTER 13 \r\n\r\n Fast Fourier Transform \r\n\r\n 13.1 The Serial Algorithm \r\n\r\n 13.2 The Binary-Exchange Algorithm \r\n\r\n 13.3 The Transpose Algorithm \r\n\r\n 13.4 Bibliographic Remarks \r\n\r\n Problems \r\n\r\n APPENDIX A \r\n\r\n Complexity of Functions and Order Analysis \r\n\r\n A. 1 Complexity of Functions \r\n\r\n A.2 Order Analysis of Functions \r\n\r\n Bibliography \r\n\r\n Author Index \r\n\r\n Subject Index \r\n
\r\n

Since the 1994 release of the text "Introduction to Parallel Computing: Design and Anal-ysis 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. Pro-gramming 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 process-ing formed dominant applications a decade back. These applications continue to chal-lenge the current generation of parallel platforms. However, a variety of new applications have also become important. These include data-intensive applications such as transac-tion processing and information retrieval, data mining and analysis, and multimedia ser-vices. 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 implemen-tation 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 hyper-cubes, 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 Chap-

ters 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 pri-marily 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 sup-plement 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 ad-

vanced 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. booksi res. 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 in-teraction 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.