Casanova H., Legrand A., Robert Y. Parallel Algorithms

CRC Press, 2008. — 355 p.Parallel computing has undergone a stunning evolution, with high points (e.g., being able to solve many of the grand-challenge computational problems outlined in the 80’s) and low points (e.g., the demise of countless parallel computer vendors). Today, parallel computing is omnipresent across a large spectrum of computing platforms. At the “microscopic” level, processor cores have used multiple functional units in concurrent and pipelined fashion for years and multiple-core chips are now commonplace with a trend toward rapidly increasing numbers of cores per chip. At the “macroscopic” level, one can now build clusters of hundreds to thousands of individual (multi-core) computers. Such distributed-memory systems have become mainstream and affordable in the form of commodity clusters. Furthermore, advances in network technology and infrastructures have made it possible to aggregate parallel computing platforms across wide-area networks in so-called “grids”.
The aim of this book is to provide a rigorous yet accessible treatment of parallel algorithms, including theoretical models of parallel computation, parallel algorithm design for homogeneous and heterogeneous platforms, complexity and performance analysis, and fundamental notions of scheduling. The focus is on algorithms for distributed-memory parallel architectures in which computing elements communicate by exchanging messages. While such platforms have become mainstream, the design of efficient and sound parallel algorithms is still a challenging proposition. Fortunately, in spite of the “leaps and bounds” evolution of parallel computing technology, there exists a core of fundamental algorithmic principles. These principles are largely independent from the details of the underlying platform architecture and provide the basis for developing applications on current and future parallel platforms. This book identifies and synthesizes fundamental ideas and generally applicable algorithmic principles out of the mass of parallel algorithm expertise and practical implementations developed over the last decades.
The target audience for this book is graduate students and post-graduate researchers in computer science and related fields. Each chapter is organized in three parts: (i) lecture material with many proofs, examples and case-studies; (ii) a set of exercises; and (iii) solution sketches for exercises marked with a ◊. This book should be ideally suited for teaching a course on parallel algorithms, or as a complementary text for teaching a course on high-performance computing. Importantly, although most of the content of the book is about algorithm design and analysis, it is nevertheless a sound basis for teaching applied parallel programming. Many of the included examples, case studies, and exercises are natural starting points for hands-on homework assignments.Part I Models
PRAM Model
Sorting Networks
Networking
Part II Parallel Algorithms
Algorithms on a Ring of Processors
Algorithms on Grids of Processors
Load Balancing on Heterogeneous Platforms
Part III Scheduling
Scheduling
Advanced Scheduling