From: [email-masked] (C.A. Thole)
Date: Thu, 7 May 92 15:16:49 GMT

This paper is an extended version of my statement on the April HPFF
working meeting in DALLAS.
It is also an responce on Chuck Koelbel's contribution about different
kinds of DO parallelism.

	          A vote for explicit MIMD support
         Clemens-August Thole, GMD I1.T, D-5205 St. Augustin
                        [email-masked]
 
                      Version of May 08, 1992

1.  MIMD parallelism is important

Although the CM-2, the AMT DAP and the Maspar machines have proven their
usefulness for many applications, it is important to exploit MIMD parallelism 
for many applications. In its introduction of loosly synchronous applications 
Fox [1] gives many examples of data parallel applications, which are not of
SIMD-type. Just for reference I would like to introduce three examples
from different areas:

1.1  Finite Element computations

The setup of element matrices is one of the four computations steps during
the treatment of finite element problems. (The f(ix) = f(ix) + delta example
corresponds to the assembly phase of such programs). All the element 
matrices can be computed in parallel, but the code for the element depends
on its type. Usual finite-element program support a lot of different types
(about 100?) and several of them are usually used for the solution of one
specific problem.

For each type of an element a different Fortran subroutine is used to set-up 
the element matrices.

Example for basic code structure:

	do 10 i=1, number_of_elements
           goto (101, 102, ............, 199), type_of_element(i)
           ...... error condition for illegal type ......

101        call sub_101( element_data(i))
           goto 10

102        call sub_102( element_data(i))
           goto 10

           .....

199        call sub_199( element_data(i))
           goto 10
10      continue

1.2 CFD computations

During the integration of a flow around the body of an air plane all the 
grid points can be treated in parallel. The actual code for various
grid points is different due to the treatment of:

    -  different types of boundary conditions
    -  use of special wall functions near the boundary
    -  treatment of shocks
    -  treatment of areas with sub-sonic or super-sonic flow 
    -  use of different basic models in different areas 
       (Potential Equation, Euler Equations, Navier Equations in different
        Areas)

A simple example is the treatment of a O-Net around an wing with
special treatment of the friction a near the wing:

      grid_data (0:L+1, 0:M+1, 0:N+1)

C.....boundary conditions for the far field and for the symmetry plane

      call outer_bc1 ( grid_data) updates grid_data( 1:L, 1:M, N+1)
      call outer_bc2 ( grid_data) updates grid_data(   0, 1:M, 1:N)
      call outer_bc3 ( grid_data) updates grid_data( L+1, 1:M, 1:N)

C.....boundary conditions for the wing surface and the contact surface
C.....at the side of the wing
      call plane_bc1 ( grid_data) updates grid_data( 1:L1, 1:M, 0)
      call plane_bc2 ( grid_data) updates grid_data( L1+1:L, 1:M, 0)

C.....boundary conditions for the cut after the wing
      call cut_bc    ( grid_data) updates grid_data( 1:L,   0, 1:N) and
                                          grid_data( 1:L, M+1, 1:N)

C.....treatment of inner point except the area near the wing
      call inner     ( grid_data) updates grid_data( 1:L, 6:M, 1:N)
                             different code is used depending on the 
                             size of the local Reynolds-number

C.....treatment of the area near the wing with special wall functions
      call wall_func ( grid_data) updates grid_data( 1:L, 1:5, 1:N)

1.3   ab initio computation in chemistry

This computation requires the evaluation of integrals for each pair of
the set of basic functions. For bundles of this pairs of integrals
it is determined first, whether the values contributed significantly
to the result. If not the evaluation of these integrals is skipped.

If the integrals for a bundle have to be evaluated, special cubature procedures
are used, which depend on the type of currently used basic function and
the required accuracy.

2. Different Modes of Computations for these examples

2.1  SIMD - mode

TMC has shown in their examples, that each of these cases can be done on an
SIMD architecture with some overhead. Different type of boundary conditions,
for example, can be treated as special cases of one generalized boundary 
condition.

In the end, each of the different remaining cases of computation (for example
the generalized boundary condition or the treatment of the wall functions) 
has to be evaluated for any grid point and not only for a small subset. 
In the CFD case, for example, the treatment of the wall functions or certain 
boundary condition involves much more operations per grid point than inner 
point. A performance penalty is the result. 

2.2 MIMD - non parallel mode

If on an MIMD architecture the compiler does not recognize, that the different
cases of updates can be treated in parallel the Finite Element example would
be executed sequentially. For the CFD example each subroutine would be
executed one after the other. In the later case the execution will be faster
than in the SIMD mode, because computations will be executed only for the
grid-points involved. Because each node will contain inner points and boundary 
points, boundary conditions will only be done for a fractions of its grid points.
This results in faster execution than in the SIMD mode. 

In the case of highly parallel architectures for a subset of nodes the 
ratio of "irregular" and "regular" grid points for example will become
very unfavorate, which results in load balancing problems. 

A solution of this load-balancing problem by overlapping the treatment of
"regular" and various kinds of "irregular" points cannot be achived.

2.3 MIMD - parallel mode

The MIMD - parallel mode allows the overlapping of the treatment of different 
kinds of data elements like grid points at boundaries, the wall function area 
and the regular interior of the computational domain.

3. Conclusion

1. The discussions above indicate that a parallel treatment of data elements
   of large data objects but with varying functionals is common in different
   scientific areas.

2. The treatment of different subsets of the data objects is quite often
   encapsulated in subroutines or each alternative requires large parts of code. 
   It cannot be expected to be detected automatically in most cases. 

3. Comparing assertions and commands for the expression of MIMD parallelism
   the command-type approach has the risk of large overhead for copying and
   merging data objects. The compiler technology necessary to avoid this
   overhead is the same as needed for the detection of parallelism. Passing
   array sections to subroutines and specifying the intend of use in 
   subroutine interface blocks helps but the CFD example shows, that the
   compiler needs very good technology in order to determine, that the 
   different subsets of the data objects are disjoint with each other.

   The assertion-type of expressing parallelism is therefore the much
   faster way to garanty high-performance.

4. Some kind of parallel sections should be supported. 

5. It should be possible to nest parallelism. 

6. An ON clause using sections should be allowed to describe which subset
   of processors execution an instance of a parallel construct.

7. A basic question is whether all data used in an parallel instance and
   therefore possibly inside a subroutine must be local to the set of
   processors assigned to executed the parallel instance or whether this
   restriction can be avoided. 

   This questions implies a decision about the question, whether communication
   between processors is assumed to be able to generate interrupts at the 
   destination processor. (see also Guy Steele's remark on the implementation of 
   CALL ARRAY_FETCH in his Proposal for local program units in HPF, version of 
   March 25, 1992.)

References:

[1]	Fox: Parallel problem architectures and their implication for
	portable parallel software systems. CRPC-TR91120. February 1991.
	(and further references in that paper)