3.8 Parallel Computing Works?

The complex system classification introduced in this chapter allows a precise formulation of the lessons of current research.

The majority of large scale scientific and engineering computations have synchronous or loosely synchronous character. Detailed statistics are given in Section 14.1 but we note that our survey suggests that at most 10% of applications are asynchronous. The microscopic or macroscopic temporal synchronization in the synchronous or loosely synchronous problems ensures natural parallelism without difficult computer hardware or software synchronization. Thus, we can boldly state that

for these problems. This quantifies our statement that ``Parallel Computing Works,''

where Equation 3.20 should be interpreted in the sense shown in Figure 3.13(b).

Roughly, loosely synchronous problems are suitable for MIMD and synchronous problems for SIMD computers. We can expand Equation 3.20 and write

The results in Equation 3.21 are given with more details in Tables 14.1 and 14.2. The text of this book is organized so that we begin by studying the simpler synchronous applications, then give examples first of loosely synchronous and finally asynchronous and compound problems. 

The bold statements in Equations 3.20 and 3.21 become less clear when one considers software and the associated software complex system . The parallel software systems CrOS and its follow-on Express were used in nearly all our applications. These required explicit user insertion of message passing, which in many cases is tiresome and unfamiliar. One can argue that, as shown in Figure 3.14, we supported a high-level software environment that reflected the target machine and so could be effectively mapped on it. Thus, we show (CrOS) and (MIMD) close together on Figure 3.14. A more familiar and attractive environment to most users would be a traditional sequential language like Fortran77. Unfortunately,

and so, as shown in Figures 3.13(a) and 3.14, it is highly non-trivial to effectively map existing or new Fortran77 codes onto MIMD or SIMD parallel machines-at least those with distributed memory. We will touch on this issue in this book in Sections 13.1 and 13.2, but it remains an active research area.

We also discuss data parallel languages, such as High Performance Fortran, in Chapter 13 [Kennedy:93a]. This is designed so that

  
Figure 3.14: The Dusty Deck Issue in Terms of the Architectures of Problem, Software, and Computer Complex Systems

We can show this point more graphically if we introduce a quantitative measure M of the difficulty of mapping . We represent M as the difference in heights h,

where we can only perform the map if M is positive

Negative values of M correspond to difficult cases such as Equation 3.22 while large positive values of M imply a possible but hard map. Figure 3.15 shows how one can now picture the process of computation as moving ``downhill'' in the complex system architecture space.

  
Figure 3.15: Two Problems and Five Computer Architectures in the Space-Time Architecture Classification of Complex Systems. An arrow represents a successful mapping and an ``X'' a mapping that will fail without a sophisticated compiler.

This formal discussion is illustrated throughout the book by numerous examples, which show that a wide variety of applications parallelize. Most of the applications chapters start with a computational analysis that refers back to the general concepts developed. This is finally summarized in Chapter 14, which exemplifies the asynchronous applications and starts with an overview of the different temporal problem classes. We build up to this by discussing synchronous problems in Chapters 4 and 6; embarrassingly parallel problems in Chapter 7; loosely synchronous problem with increasing degrees of irregularity in Chapters 8, 9, and 12. Compound problem classes-an asynchronous mixture of loosely synchronous components-are described in Chapters 17 and 18. The large missile tracking and battle management simulation built at JPL (Figure 3.11b) and described briefly in Chapter 18 was the major example of a compound problem  class within CP. Chapters 17 and 19 indicate that we believe that this class is extremely important in many ``real-world'' applications that integrate many diverse functions.