In our picture shown in Equation 3, software maps problems onto the hardware in one or more stages.
We can understand many of the different software approaches in terms of choices for the virtual machine which is the user's view of the target computer. Essentially all our Caltech work on the hypercube and other MIMD machines used a C (Fortran) plus explicit message passing software model. This corresponds to choosing a virtual machine model that was either a hypercube or more generally a collection of nodes able to exchange messages independent of a particular topology. The latter was called VMLSCS in [10] for Virtual Machine Loosely Synchronous Communication System. This software model was very successful in that as shown in Figure 3, one is able to use it to map essentially all problems onto a MIMD distributed memory multicomputer. Its strengths and weaknesses are a consequence of using a virtual machine model close to a real machine. This allows great generality in problems but produces non-portable code that is specific to one machine class. Further, it is hard work as the user must map the problem a ``long way'' from the original application onto the virtual machine.
Over the last few years, another approach has become popular which corresponds to using a virtual machine model which is close to the problem and not the machine architecture. We view the use of CMFortran in this fashion corresponding to a virtual machine representing data parallel synchronous problems. The two approaches are contrasted in Figure 4. This analysis suggests that data parallel Fortran can be mapped onto both SIMD and MIMD machines. We view CMFortran as supporting a SIMD virtual machine (SIMD problem architecture) and not as the language for just SIMD hardware. For this reason, we prefer to term the ``compiler'' target in Equation 3 as the virtual problem and not the more common description as a virtual machine. This terminology makes it more natural to consider languages like CMFortran as the languages for ``SIMD problems'' (synchronous problems) rather than the languages for SIMD machines.
Table 3: Extensions of FortranD for Different Problem Classes
The Rice and Syracuse groups [15], [16], [17] have proposed FortranD as a data parallel Fortran suitable for distributed memory machines. This generalizes the concepts behind CMFortran in several ways. As shown in Figure 5, FortranD includes Fortran 77D and Fortran 90D with implicit and explicit parallelism respectively; the compiler for Fortran 77D uses dependency analysis to uncover data parallel constructs which are explicit in the array operations and run-time library of Fortran 90D. FortranD targets both SIMD and MIMD machines. Although the initial design for FortranD was largely aimed at synchronous problems, it is flexible enough to include loosely synchronous problems. In fact, we expect that with suitable extensions, FortranD and similar languages should be suitable for the majority of synchronous and loosely synchronous problems. Thinking Machines has pioneered many of these ideas with their adoption of CMFortran for the SIMD CM-2 and MIMD CM-5.
The loosely synchronous extensions to FortranD are designed to handle irregular problems which we already understand how to implement with explicit message passing. However, higher level software models as defined by Figure 6, such as FortranD are I believe essential if parallel processing is to become generally accepted. We have used the ideas behind Parti [18], [19] in the loosely synchronous implementation of FortranD. Table 3 summarizes work in progress with Saltz. We need to divide the loosely synchronous class into subclasses which each have rather different needs in language extensions. We have examined initially some partial differential equation and particle dynamics problems. We see four major subclasses. The simplest case is typified by an unstructured mesh which has a single static irregular data structure. The hardest case is typified by the fast multipole method for particle dynamics [20], [21] where one has an irregular dynamic data structure which is implicitly defined. As we consider further examples such as vision and signal proceedings, we may discover new issues or in our problem architecture language, new loosely synchronous problem architecture characteristics which need to be explicitly recognized in FortranD.