The first of a multi-part series on designing parallel algorithms by Ian Foster is up at Dr. Dobb’s. The articles are based on Foster’s well-known text, Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering, a copy of which I used in grad school and which still rests on my shelf, nestled comfortably between Fundamentals of Sequential and Parallel Programming and Dowd’s High Performance Computing. Interestingly, Foster’s book is both online (for free) and in print.
Parallel algorithm design is not easily reduced to simple recipes. Rather, it requires the sort of integrative thought that is commonly referred to as “creativity.” However, it can benefit from a methodical approach that maximizes the range of options considered, that provides mechanisms for evaluating alternatives, and that reduces the cost of backtracking from bad choices. We describe such an approach and illustrate its application to a range of problems. Our goal is to suggest a framework within which parallel algorithm design can be explored. In the process, we hope you will develop intuition as to what constitutes a good parallel algorithm.