A Comprehensive Guide to Parallel Computing

Introduction to Parallel Computing: Design and Analysis of Algorithms, 2nd Edition
Ananth Grama, George Karypis, Vipin Kumar, and Anshul Gupta
Addison Wesley
2003
ISBN 0-2016-4865-2
856 pp., US$80.40.

Ananth Grama and his colleagues have done a thorough job in putting together Introduction to Parallel Computing: Design and Analysis of Algorithms, Second Edition. Parallel computing is becoming a more sought-after solution for medium to large enterprises because of decreasing hardware costs. This book provides background and introductory information mixed with theories of parallel systems’ inner workings and a practical guide to the most popular programming frameworks.

The fundamentals of parallel systems

At the book’s beginning, the authors give an overview of parallel systems. This section includes such subjects as trade-offs among communication options, programming options, and platforms and the ever-so-complex topic of parallel algorithms. The authors compare the pros and cons of various parallel-computation options such as multithreading, multiprocessing, and shared-memory systems. They go on to explain how parallel systems’ physical representation can affect their algorithms, platforms, and overall performance. They also cover networking and communication in parallel systems in detail. The book provides thorough discussions and cost analyses of one-to-all, all-to-one, all-to-all, all-reduce, circular shift, and scatter-gather communication patterns. The authors further analyze choosing the right communication model between systems, programming platforms, and hardware setup (memory and processor) in the systems’ 2D, 3D, and higher dimensional physical representations.

Breaking down an algorithm so it can exploit a parallel system is difficult, and sometimes it’s more efficient to simply stick with a procedural way of executing a task. This makes algorithm-efficiency analysis rather important. The authors spend a great deal of time dealing with such issues and discuss the techniques available to algorithm designers, including

*   Data-parallel model. Tasks are statically mapped onto processes, and the similar task is performed on different data.

*   Task-graph model. Tasks are viewed via a task dependency graph.

*   Work-pool model. This involves dynamically mapping tasks onto processes for load balancing.

*   Master-slave model. One or more master generates work for other processes to do.

*   Producer-consumer model. A stream of data passes through numerous processes, and each one performs a task on it.

The authors refer to each of these techniques throughout the book and analyze them case by case. By the introduction’s end, you’ll thoroughly understand how parallel systems work and how best to exploit them.

Practical applications

After they cover the fundamentals, the authors put them to the test by looking at widely available frameworks such as the message passing interface, shared-memory paradigms such as Posix Threads, and a directive-based programming framework called OpenMP. OpenMP is the most interesting because it’s the simplest to use and program with, but you need to know how the other two models work to fully understand it. The authors then further explore the communication and decomposition paradigms that they introduced earlier in the text through examples and working programs.

One of parallel systems’ main advantages is their ability to crunch numbers, and what better way to do it than by matrix manipulation? Linear equations and vector multiplication are probably the most popular parallel algorithm implementations, and the authors cover them in detail. They start by analyzing the best way to approach these two problems and then use pseudocode to show the reader how to do it in the real world. Next, the authors depict and analyze sorting and graphs algorithms. They present sorting algorithms such as quick sort, bucket sort, and radix sort. A discussion of the trade-offs between communication and programming paradigms brings these two topics to a nice close. Grama and his colleagues walk you step-by-step through choosing the right algorithm through analysis and example. They finish by talking about two real-life implementations of parallel algorithms: dynamic programming (shortest path problems, longest subsequence problems, and so on) and fast Fourier transform’s implementation.

Introduction to Parallel Computing: Design and Analysis of Algorithms, 2nd Edition is a comprehensive book that covers parallel programming from theory to practice. It’s a good reference for people in the field and a great learning tool for students and practitioners interested in the growing field of parallel computing.

Art Sedighi is a senior consultant at TIBCO Software and a freelance writer. Contact him at sediga@alum.rpi.edu; www.ArtSedighi.com.