Here we discuss the trade off between message-passing and data-parallel languages from the problem architecture point of view developed in Chapter 3.
We return to Figure 3.4, which expressed computation as
a sequence of maps. We elaborate this in Figure 13.2,
concentrating on the map of the (numerical formulation of the) problem
onto the computer 
. This map could be
performed in several stages reflecting the different software levels.
Here, we are interested in the high-level software map 
. One often refers to 
as the
virtual machine (VM), since one can think of it
as abstracting the specific real machine into a generic VM. One could
perhaps more accurately consider it as a virtual problem, since one is
expressing the details of a particular problem in the language of a
general problem of a certain class. Naively, one can say in
Figure 13.2 that 
is ``nearer'' the problem
than the computer. One often thought of CMFortran as a language for
SIMD machines. This is not accurate-rather, it is a language for
synchronous problems (i.e., a particular problem architecture) which
can be executed on all machine architectures. This is illustrated by
the use of CMFortran on the MIMD CM-5 and the HPF (FortranD) discussion
of the previous subsection. These issues are summarized in
Table 13.5. Generally, we believe that high-level software
systems should be based on a study of problems and their architectures
rather than on machine characteristics.
Figure 13.2: Architecture of ``Virtual Problem'' Determines Nature of
High-Level Language
Figure 13.3 (Color Plate) illustrates the map of problem onto machine,
emphasizing the different architectures of both. Here we regard
message passing as a (low-level 
) paradigm that is
naturally associated with a particular machine architecture, that is, it
does reflect a virtual machine-the generic
MIMD architecture. One has a trade off in languages between features
optimized for a particular problem class against those optimized for
particular machine architectures. This figure is also drawn so as to
emphasize that HPF corresponds to a 
``near'' the
problem and Fortran-plus message passing is a paradigm ``near'' the
computer.
Figure 13.3: Problem architectures mapped into machine
architectures.
Figure 13.4 (Color Plate) illustrates the compilation and migration processes from this point of view. HPF is a language that reflects the problem structure. It is difficult but possible to produce a compiler that maps it onto the two machine (SIMD and MIMD) architectures in the figure. Fortran-plus message passing expresses the MIMD computer architecture. It is typically harder for the user to express the problem in this paradigm than in the higher level HPF. However, it is quite easy for the operating system to map explicit message passing efficiently onto a MIMD architecture. However, this is not true if one wishes to map message passing to a different architecture (such as a SIMD machine) where one must essentially convert (``compile'') the message passing back to the HPF expression of the problem. This is typically impossible as the message-passing formulation does not have all the necessary information contained in it. Expressing a problem in a specific language often ``hides'' information about the problem that is essential for parallelization. This is why much of the existing Fortran 77 sequential code cannot be parallelized. Critical information about the underlying problem cannot be discovered except at run time when it is hard to exploit. We discuss this point in more detail in the following subsection.
Figure 13.4: migration and compilation in the map of
problems to computers.
Table 13.5: Message Passing, Data-Parallel Fortran, Problem
Architectures