In this chapter, we have focused on the software engineering question of developing a parallel algorithm design from a given problem specification. We have assumed some familiarity with program design---from, for example, previous study in sequential programming. A classic article by Parnas and Clements  describes the benefits (and difficulties) of a rational design process. The chapter notes in Chapters 3 and 4 provide additional references to material on the related topics of performance analysis and modularity.
Relatively few authors have addressed the particular problems that arise when designing algorithms for realistic scalable parallel computers. Numerous books discuss parallel algorithm design in the context of the idealized PRAM model; see, for example, Akl , Gibbons and Reitter , and JáJá . However, these techniques are for the most part not directly applicable to multicomputers. The books by Fox et al. [111,113] and Kumar et al.  provide relevant material. Carriero and Gelernter  give an introduction to parallel program design in the Linda language. They distinguish between agenda, result, and specialist parallelism, which can be thought of as domain decomposition and two different forms of functional parallelism, respectively. See also the references in Chapter 12.
The mapping problem has received considerable attention in the computer science and scientific computing literature. Bokhari shows that it is NP -complete . The recursive coordinate bisection algorithm is due to Berger and Bokhari , and the unbalanced recursive bisection algorithm is due to Jones and Plassmann . A related algorithm is the recursive spectral bisection algorithm of Pothen, Simon, and Liou , which uses connectivity information to identify partitions of unstructured meshes with low communication requirements, at the cost of an eigenvalue computation. This algorithm has proven very effective, although more expensive than the other recursive algorithms. Simon  and Williams  compare different algorithms for partitioning unstructured meshes, including coordinate bisection, graph bisection, and spectral bisection. Barnard and Simon  describe a less expensive multilevel version of spectral bisection. The mesh in Figure 2.9 is generated using the finite octree technique of Shephard and Georges . Fox et al.  and Nicol and Saltz  describe the use of cyclic decompositions. Lin and Keller  describe a local algorithm. The local algorithm described in the text is termed a receiver-initiated strategy. In an alternative sender-initiated strategy, workers with excess work send it to other workers. Tantawi and Towsley  compare sender-initiated and receiver-initiated strategies and show that the former gives better performance if workers are often idle and that the latter performs better when load is heavy. Other relevant papers include those by Berman and Snyder ; Chowdhury ; Cybenko ; Hac ; Heath, Rosenberg, and Smith ; Kumar, Grama, and Rao ; Lo ; and Sadayappan and Ercal . Dijkstra, Feijen, and Gasteren , Rokusawa et al. , and Kumar et al.  describe distributed termination-detection algorithms.
Real atmosphere models are of course more complex than the system considered in Section 2.6. Washington and Parkinson  provide a good introduction to the numerical methods and algorithms used in climate modeling on sequential computers. A workshop held at the European Center for Medium-range Weather Forecasting surveyed issues involved in executing weather and climate models on parallel computers . The parallel version of the Community Climate Model is described by Drake et al. . Michalakes  analyzes load imbalances in climate models and Foster and Toonen  describe load-balancing algorithms.
Banerjee  describes parallel algorithms for VLSI design. Wimer et al.  and Arvindam et al.  describe branch-and-bound search algorithms and domain-specific optimizations that can improve performance on floorplanning problems. Reinefeld and Schnecke  describe the algorithm variant in which workers redundantly expand several tree levels before selecting nodes for local expansion. Kumar et al. [179,181,239] provide a wealth of material on the design, implementation, and analysis of parallel search algorithms. Quinn  also examines branch-and-bound search and describes and analyzes the performance of four different load balancing strategies. For a general introduction to search algorithms, see Nilsson , Pearl , and Kumar and Kanal .
Hehre et al.  provide an introduction to ab initio quantum chemistry. Feyereisen and Kendall  describe a replicated data algorithm for the Fock matrix construction problem. Colvin et al.  describe an algorithm based on domain decomposition techniques. An algorithm that uses distributed data structures and a centralized task scheduler is described by Harrison et al. [108,135].
Here is a Web Tour providing access to additional information on parallel program design and software engineering.
© Copyright 1995 by Ian Foster