This chapter contains some of the hardest applications we developed within CP at Caltech. The problems are still ``just'' data-parallel with the natural ``massive'' (i.e., large scale as directly proportional to the number of data elements or problem size) loosely synchronous parallelism summarized in Figure 12.1. However, the irregularity of the problem-both static and dynamic-makes the implementation technically hard. Interestingly, after this hard work, we do find very good speedups, that is, this problem class has as much parallelism as the simpler synchronous problems of Chapters 4 and 6. In fact, one finds that it is in this class of problems that parallel machines most clearly outperform traditional vector supercomputers [Fox:89i;89n;90o]. The (dynamic) irregularity makes the parallelism harder to expose, but it does not remove it; however, the irregularity of a problem can make it impossible to get good performance on (SIMD) vector processors.
Figure 12.1: Data Parallelism
The problems contained in this chapter are also typical of the hardest challenges for parallelizing compilers. These applications are not easy to write in a high-level language, such as High Performance Fortran of Chapter 13, in a way that compilers can efficiently extract the parallelism. This area is one of major research activity with interesting contributions from the groups at Yale [Bhatt:92a] and Stanford [Singh:92a] for the N-body problem described in Section 12.4.
The applications in this chapter can be summarized as follows:
We suggest that Chapters 12, 14, and 18 contain some of those applications which should be studied by computer scientists developing new software tools and parallel languages. This is where the application programmer needs help! We have separated off Chapter 14, as the violation of the loose synchronization condition in this chapter produces different complications from the dynamic irregularity that characterizes the applications of Chapter 12. Chapter 18 contains compound metaproblems combining all types of problem structure.