Parallel Algorithms

Parallel Algorithms

  • Electronic book text
By (author)  , By (author)  , By (author) 

List price: US$99.94

Currently unavailable

We can notify you when this item is back in stock

Add to wishlist

AbeBooks may have this title (opens in new window).

Try AbeBooks


Focusing on algorithms for distributed-memory parallel architectures, Parallel Algorithms presents a rigorous yet accessible treatment of theoretical models of parallel computation, parallel algorithm design for homogeneous and heterogeneous platforms, complexity and performance analysis, and essential notions of scheduling. The book extracts fundamental ideas and algorithmic principles from the mass of parallel algorithm expertise and practical implementations developed over the last few decades. In the first section of the text, the authors cover two classical theoretical models of parallel computation (PRAMs and sorting networks), describe network models for topology and performance, and define several classical communication primitives. The next part deals with parallel algorithms on ring and grid logical topologies as well as the issue of load balancing on heterogeneous computing platforms. The final section presents basic results and approaches for common scheduling problems that arise when developing parallel algorithms. It also discusses advanced scheduling topics, such as divisible load scheduling and steady-state scheduling. With numerous examples and exercises in each chapter, this text encompasses both the theoretical foundations of parallel algorithms and practical parallel algorithm more

Product details

  • Electronic book text | 360 pages
  • Taylor & Francis Ltd
  • Chapman & Hall/CRC
  • London, United Kingdom
  • 500 equations; 9 Tables, black and white; 119 Illustrations, black and white
  • 1584889462
  • 9781584889465

Review quote

"...The authors of the present book, who have extensive credentials in both research and instruction in the area of parallelism, present a sound, principled treatment of parallel algorithms. ... This book is very well written and extremely well designed from an instructional point of view. ... The authors have created an instructive and fascinating text. The book will serve researchers as well as instructors who need a solid, readable text for a course on parallelism in computing. Indeed, for anyone who wants an understandable text from which to acquire a current, rigorous, and broad view of parallel algorithms, including the principles for their design, development, and analysis, this book is highly recommended."-SIAM Review, Vol. 52, No. 1, 2010 "... It extracts the main ideas and principles of parallel algorithms developed over the last few decades. ... the authors perfectly explain not only homogeneous models (which are everyday problems on clusters of identical nodes) but also load balancing on heterogeneous platforms (connecting different clusters or many different workstations). This book can serve as a very good teaching book or a source of useful material for graduate students and researchers in parallel distributed memory architectures. It contains many schemes, diagrams, and pictures for better understanding, including many practical examples, case studies, and exercises."-EMS Newsletter, June 2009 "Parallel Algorithms is a text meant for those with a desire to understand the theoretical underpinnings of parallelism from a computer science perspective. ... [it provides] the tools you need to continue on a rigorous research track into the computer science aspects of parallel computing. ... those motivated to work through the text will be rewarded with a solid foundation for the study of parallel algorithms."-John West, HPCwire, April 2009show more

Table of contents

Preface Models PRAM Model Pointer Jumping Performance Evaluation of PRAM Algorithms Comparison of PRAM Models Sorting Machine Relevance of the PRAM Model Sorting Networks Odd-Even Merge Sort Sorting on a One-Dimensional Network Networking Interconnection Networks Communication Model Case Study: The Unidirectional Ring Case Study: The Hypercube Peer-to-Peer Computing Parallel Algorithms Algorithms on a Ring of Processors Matrix-Vector Multiplication Matrix-Matrix Multiplication A First Look at Stencil Applications LU Factorization A Second Look at Stencil Applications Implementing Logical Topologies Distributed vs. Centralized Implementations Summary of Algorithmic Principles Algorithms on Grids of Processors Logical Two-Dimensional Grid Topologies Communication on a Grid of Processors Matrix Multiplication on a Grid of Processors Two-Dimensional Block Cyclic Data Distribution Load Balancing on Heterogeneous Platforms Load Balancing for One-Dimensional Data Distributions Load Balancing for Two-Dimensional Data Distributions Free Two-Dimensional Partitioning on a Heterogeneous Grid Scheduling Scheduling Introduction Scheduling Task Graphs Solving Pb(â ) Solving Pb(p) Taking Communication Costs into Account Pb(â ) with Communications List Heuristics for Pb(p) with Communications Extension to Heterogeneous Platforms Advanced Scheduling Divisible Load Scheduling Steady-State Scheduling Workflow Scheduling Hyperplane Scheduling (or Scheduling at Compile-Time) Bibliography Index Exercises and Answers appear at the end of each more