An Introduction to Parallel Computing: Design and Analysis of Algorithms, Second Edition

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

Introduction to Parallel Computing, Second Edition

Ananth Grama

Anshul Gupta

George Karypis

Vipin Kumar

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.

* Provides a complete end-to-end source on almost every aspect of parallel computing (architectures, programming paradigms, algorithms and standards).

* Covers both traditional computer science algorithms (sorting, searching, graph, and dynamic programming algorithms) as well as scientific computing algorithms (matrix computations, FFT).

* Covers MPI, Pthreads and OpenMP, the three most widely used standards for writing portable parallel programs.

* The modular nature of the text makes it suitable for a wide variety of undergraduate and graduate level courses including parallel computing, parallel programming, design and analysis of parallel algorithms and high performance computing.

Ananth Grama is Associate Professor of Computer Sciences at Purdue University, working on various aspects of parallel and distributed systems and applications.

Anshul Gupta is a member of the research staff at the IBM T. J. Watson Research Center. His research areas are parallel algorithms and scientific computing.

George Karypis is Assistant Professor in the Department of Computer Science and Engineering at the University of Minnesota, working on parallel algorithm design, graph partitioning, data mining, and bioinformatics.

Vipin Kumar is Professor in the Department of Computer Science and Engineering and the Director of the Army High Performance Computing Research Center at the University of Minnesota. His research interests are in the areas of high performance computing, parallel algorithms for scientific computing problems and data mining.

Fuzzy Control Systems explores one of the most active areas of research involving fuzzy set theory. The contributors address basic issues concerning the analysis, design, and application of fuzzy control systems. Divided into three parts, the book first devotes itself to the general theory of fuzzy control systems. The second part deals with a variety of methodologies and algorithms used in the analysis and design of fuzzy controllers. The various paradigms include fuzzy reasoning models, fuzzy neural networks, fuzzy expert systems, and genetic algorithms. The final part considers current applications of fuzzy control systems. This book should be required reading for researchers, practitioners, and students interested in fuzzy control systems, artificial intelligence, and fuzzy sets and systems.

Introducation to Parallel Computing is a complete end-to-end source of information on almost all aspects of parallel computing from introduction to architectures to programming paradigms to algorithms to programming standards. It is the only book to have complete coverage of traditional Computer Science algorithms (sorting, graph and matrix algorithms), scientific computing algorithms (FFT, sparse matrix computations, N-body methods), and data intensive algorithms (search, dynamic programming, data-mining). This text discusses the theory, methodologies and algorithms of fuzzy control systems. It considers various applications of fuzzy control systems, including real-time applications, and describes current research interests in fuzzy control systems