Subject: Re: A suggestion for a multi-level MPI

From: "Chuck Simmons <[email-masked]>" <[email-masked]>
Date: Wed, 3 Feb 93 03:17:14 PST

In-Reply-To: WRPYR:[email-masked]'s message of 02-03-93 00:40

Rusty, Bill --

I do view the interface as being layered, but I would organize the layers
differently.  And I have a couple of arguments that I haven't tried out
yet against some of the send/recv routines.

First, it sounds to me like you are suggesting that the 72 routines
be implemented as 72 simple routines that each make a small number of
subroutine calls to very simple routines.  And then the do_send routine
would do a lot.  I guess the do_send routine on a typical machine might
look like:

	/* convert the data into a vector of buffers */
	if (options & MPI_OPT_ONEBUF) {
		iovlen = 1;
		iovp = bufp;
	}
	else if (options & MPI_OPT_STRIDED) {
		/* malloc local buffer, gather data, set up iovlen and iovp */
	}

	/* translate the data */
	if (options & MPI_OPT_HETER) {
		/* malloc new buffer, translate data into new buffer */
	}

	/* send the data non-blocking and unreliable */
	if (options & MPI_OPT_RR) {
		sendrr (...);
	}
	else send (...);

	/* block if so requested */
	if (options & MPI_OPT_BLOCK) {
		block (...);
	}

My view of the layering is:

	basic functionality:
		non-blocking vector send
		non-blocking vector receive

	easy-to-use basic functionality:
		non-blocking single buffer send
		non-blocking single buffer receive

	reliable:
		synchronous vector send
		synchronous vector receive

	easy and reliable:
		synchronous single buffer send
		synchronous single buffer receive

In the above, each of the later listed routines can be implemented
on top of an earlier listed routine.

I would then examine each of the remaining aspects of the functionality:
heterogeneity, ready-receiver, strided messages, and blocking non-synchronous
messages.

For heterogeneity, I would argue that it is wrong to put the datatype
translation filter in the communications channel.  In your model, it
is relatively easy to do things like:

	bsendh (dest, tag, buf, FLOAT, 1);

or even:

	bsendh (dest, tag, buf, ARRAY|FLOAT, nitems);

but what about

	bsendh (dest, tag, buf, rpc_t, 1);

where 'rpc_t' is some user defined data structure?  Thus, this model
lacks generality.  Only certain simple messages can be heterogeneously
sent efficiently through the interface.  A completely different paradigm
must be used if you want to send a structure instead of an array.

Further, consider how the "bsendh (dest, tag, buf, ARRAY|FLOAT, nitems);"
routine is going to be implemented on a typical machine:

	buflen = sizeof (net_float) * nitems;
	sendbuf = (net_float *) malloc (buflen);
	if (!sendbuf) return ENOMEM;

	for (i = 0; i < nitems; i++) {
		sendbuf[i] = float2netfloat (buf[i]);
	}

	bsend (dest, tag, (void *)sendbuf, buflen);
	free (sendbuf);

(In the above, we assume that a "net_float" holds the network normalized
format of a floating point number.)

It would be as efficient to implement the translation routines completely
separate from the communications routines.

But, wait, you say, our machine is not typical and we can implement this
as:

	bsend (dest, tag, &header, sizeof (header));
	for (i = 0; i < nitems; i++) {
		bsend (dest, tag, float2netfloat (buf[i]), sizeof (net_float));
	}

where 'bsend' is assumed to be a machine instruction.

My argument against this is that the gain in efficiency is sufficiently
small that it's not clear its worth the added complexity.  In both
implementations, the cpu time will be dominated by the data conversion.
In the "typical" implementation, there is an additional cost for moving
data between two buffers, but that data movement occurs at the speed of
local memory access which is likely to be much higher than network bandwidth.
Thus, it is much easier for the hardware to DMA the first implementation and
run some other process while that DMA is in progress.  In the second
implementation, the sending process is essentially hogging the cpu for the
full time it takes to transmit each piece of the message.

Obviously, if there exists a standard for network normal formats of datatypes,
and if hardware vendors implement the data translation facilities in hardware,
then we could DMA out the whole message heterogeneously.  But surely there
are other things that we would rather have hardware vendors implementing for
us.

The above is essentially the same argument that I'm going to use for
strided messages.   Strided messages are only efficient if you have
hardware that can DMA the strided vector, and then its not so efficient
that it's obviously worth the effort.

For ready-receiver, I'm going to argue that the communications subsystem
should always assume the receiver is ready and then handle the case where
this isn't true.  If the application has set things up so that this is
true, that application will run efficiently whether or not the sender
specifies that the receiver is ready.  If the application isn't being careful,
it will run slowly in your model, but in my model, it will usually run quickly
since memory is usually availabe in the receiver, and my model will run
as slowly as your model when congestion is present at the receiver.

Implementing the ready-receiver places strong semantics on the sender
and receiver.  The sender has to know whether or not the receiver was
implemented in a fashion that allows the sender to assume that the receiver
is ready.

Finally, let's consider synchronous messages versus blocking messages.
For most applications, you want reliability.  Implementing blocking
non-synchronous messages doesn't help you implement this.  You can't
reuse the buffer being sent until you know that it has been received
at the other side.  So you might as well either send the message synchronously,
or send it non-blocking and go off and do something else while you're
waiting to see if you'll need to retransmit the buffer.

[Hmmm...  I did mention, didn't I, that I was still trying out a couple
of these arguments...]

This reduces the number of interface routines to 8.  I could probably
be convinced that adding 4 more interface routines to support strided
messages doesn't overly complicate the interface.

-- Chuck

*** We use Oracle*Mail running on Oracle V6.2 and an nCUBE2 supercomputer. ***

---- Included Message ----

From: WRPYR:[email-masked]
To: [email-masked] 
Subject: A suggestion for a multi-level MPI
Reply-To: WRPYR:[email-masked]

At the last meeting, it became apparent that many people were uncomfortable
with the large number of routines (1024 sends?) that we seemed to be going
towards.  There are good reasons for the standard not to be incomprehensibly
complex.  There are good reasons also for it not to be crippled by lack of
functionality.  Are we stuck?

There are two ways to deal with this problem.  This note is a proposal that we
adopt both of them.

The reason the problem can be solved is that the sets of options that we have
been considering (blocking or not, contiguous buffer or not, heterogeneous
machines or not, etc.) are orthogonal, and one of a large number of possible
send routines can thus be specified simply and without extra parameters.  In
addition, certain subsets of the set of all operations can be identified and
packaged for ease of use.

Here is a suggestion for how to organize the routines and end up with a
powerful, flexible, yet easy-to-use library of point-to-point functions.
(We assume that these will all be renamed to have an MPI prefix, to avoid
name-space pollution)

Level 4 (very restrictive, very simple):

    send(dest,tag,buf,len)
    recv(dest,tag,buf,len)

Both of these block until the operation is locally complete.  The buffer is a
contiguous sequence of bytes. No special protocols or translation for
heterogeneous machines.

This level is enough to express lots of parallel algorithms.  The main reason
we need more is for efficiency and control.  We now add these in steps.

Level 3 (still simple, but allows for overlap of computation and communication
         and better buffer management, and allows heterogeneous machines to
         communicate.) 

    bsend(tag,dest,bufadd,buflen)
    nsend(tag,dest,bufadd,buflen)
    bsendh(tag,dest,bufadd,datatype,numitems)
    nsendh(tag,dest,bufadd,datatype,numitems)
    brecv(tag,dest,bufadd,buflen)
    nrecv(tag,dest,bufadd,buflen)
    brecvh(tag,dest,bufadd,datatype,numitems)
    nrecvh(tag,dest,bufadd,datatype,numitems)

Here the n or b selects block or nonblocking operations, h specifies
translation for heterogeneous machines.  The restrictions (which allow the
parameter lists to be short and the number of routines to be small) are: no
noncontiguous buffers, data in message all the same type, no globally
synchronized, CSP-like send-receive, and no special protocol (like the
ready-receiver protocol discussed at the last meeting).

In order to emphasize the orthogonality, we might organize these routine names
in a diagram like this:

   [n][send][ ]
   [b][recv][h]

That is, one makes a choice in each column.

Level 2 (access to almost all MPI functionality via a large number of
orthogonally named routines):

   [c][n][send][ ][  ]
   [s][b][recv][h][rr]
   [g][s] 

the first column designates the buffer type (contiguous, strided, general
gather/scatter), the second is the termination type (nonblocking, blocking,
synchronized), then send or receive, "h" or not for heterogeneous
communication, "rr" or not for "ready-receiver" protocol.  This is a lot of
routines (3 x 3 x 2 x 2 x 2 = 72) but because of orthogonality it is easy to
understand. 

The only restriction here is that there are no "channels":  the initialization
of a send operation is combined with initiating it.

Level 1 (full MPI functionality, in a small, flexible set of routines)

   handle = init_send(tag,dest)
            mod_send(handle,option,value)
            do_send(handle)
            free_send(handle)

along with the corresponding receive routines.

The idea is that the "init" routines will set up a usable set of defaults for
all the options, specifying only minimal parameters, and then the "mod"
routine can be repeatedly called to specify all the options with regard to 
buffer type, termination type, etc.

The point is that at this level we can offer not only all possible options,
with a small number of routines, and include the "setup" routines proposed by
Marc for increased efficiency, but we also allow room for growth in the
standard through the addition of more values for "option" in the "mod" calls.

So here's how it might look, this time from the bottom up:

Level 1:  full functionality, small number of routines, channel setup

Level 2:  sequences of Level 1 calls of the form

            init...
            mod...
            mod...
            mod...
            do...
      
are given specific names in an organized way.  This promotes ease of use and
also efficiency (fewer calls).

Level 3: several of the Level 2 routines are renamed and promoted to this
level to provide a useful subset of MPI functionality in a small number of
routines, each having the minimal number of parameters.

Level 4:  ultra-simple interface

All four levels would be part of the standard and it would be possible to mix
levels in the same program.

We have not considered carefully yet how this interacts with groups and
contexts, but similar ideas might be useful there, where there are similar
problems in providing both functionality and simplicity.

Comments?

Rusty Lusk and Bill Gropp

---

From: [email-masked] (John Kapenga)
Date: Wed, 3 Feb 93 18:35:11 EST

James Cownie remarks on needing a seperate send routine for 
each data type in the Fortran Binding.

For both the C and Fortran versions there could be seperate 
calls setting up the Data Addresses (no Data need be moved)
and then a single send could take the value returned by the
Data Address Setup Call. No system call required on the 
Data Setup Call. 

This might require that the array passed to the Data Setup
Call not be modified before the send call is made, to avoid
recopying it.

This also allows later extensions to other Data Addressing
modes, without changing the send/recieve syntax.

This reduces the number of calls by almost a factor of three,
uncouples the data location from the send/recieve syntax and
allows arguement types on all calls to be correct and fixed. 

It does make a bit more processing (trival) and the need for
the user to mamage the Data Setup return value and not modify
the address array (two of its bad points).

john

---

From: [email-masked] (Tom Henderson)
Date: Thu, 4 Feb 93 13:29:24 MST

I especially like "Level 1" of Rusty and Bill's proposal.  I would like to see 
more detail in this section, like examples of mod_xxx() and do_xxx() 
routines.  I think there will be a good deal of support for Level 1 with all 
the talk that's been going on about handles/invoices/envelopes (of course 
there's that annoying syntax thing...).  

I am concerned about how heterogeneous communications are handled (or avoided) 
in Levels 3 and 4.  I would be a lot more comfortable if ALL send() and recv() 
routines were heterogeneous.  Here's a slight modification to the original 
proposal:  

Level 4 ("novice users"):

    send(dest,tag,bufadd,datatype,numitems)
    recv(dest,tag,bufadd,datatype,numitems)

Level 3 ("dangerous users" [like me :) ]):

    bsend(tag,dest,bufadd,datatype,numitems)
    nsend(tag,dest,bufadd,datatype,numitems)
    brecv(tag,dest,bufadd,datatype,numitems)
    nrecv(tag,dest,bufadd,datatype,numitems)
or
   [n][send]
   [b][recv]
in Bill and Rusty's shorthand.  

Level 2 ("really frightening users"):

   [c][n][send][  ]
   [s][b][recv][rr]
   [g][s] 

Here's the arguments:  

- I don't like the idea of having to tell novice users that they must change 
  all the MPI communication routine calls in their code before their program 
  will run on a heterogeneous system.  I think a lot of novice users will be 
  using heterogeneous workstation networks.  The current proposal forces these 
  folks to learn at least two versions of send() and recv().  

- I don't think there are any significant performance reasons for having 
  separate heterogeneous versions of these calls, as long as we require a 
  receiving process to know what incoming message contents will be (which 
  seems to be consistent with the original proposal).  

- I don't think that the additional "datatype" argument reduces "ease of use" 
  very much.  An incorrect datatype should be no more difficult to debug than 
  an incorrect "bufadd" or "buflen" (and should be easier than a bad "tag" or 
  "dest", especially if deadlock results!).  In FORTRAN77, "numitems" should 
  be easier to code portably than "buflen".  Even in C, there is little 
  difference in complexity between portable calls to heterogeneous and 
  non-heterogeneous versions:  

(non-heterogeneous)
    float mybuf[NUMITEMS];
...
    send(dest, tag, mybuf, NUMITEMS * sizeof(float));

(heterogeneous)
    send(dest, tag, mybuf, MPI_FLOAT, NUMITEMS);

- This gets rid of a whole bunch of send() and recv() variant routines (at 
  least 22).  

- If we really want non-heterogeneous communication, it could be stuck in 
  Level 1 with all the other stuff that's really dangerous for "novices".  
  Another option would be to allow a MPI_BYTE datatype (not sure how this 
  would work in FORTRAN).  This may be useful for library developers.  I think 
  it's a good idea to keep "raw bytes" away from novice users (especially in 
  FORTRAN).  

Tom Henderson
[email-masked]

---

From: Tony Skjellum <[email-masked]>
Date: Thu, 4 Feb 93 14:47:56 CST

Tom,

It is an artificial requirement to restrict heterogeneous messages to a single
 data type.
- Tony

---

From: [email-masked] (Tom Henderson)
Date: Thu, 4 Feb 93 13:51:27 MST

> It is an artificial requirement to restrict heterogeneous messages to a single

I agree.  My interpretation of Rusty and Bill's proposal is that messages that 
contain multiple data types would be constructed using the Level 1 routines-- 
something similar to Zipcode's invoices.  

Tom