Subject: Pointers... MPI_APPEND_POINTER

From: [email-masked] (Ricardo Schmutzer von Oldershausen)
Date: Wed, 9 Jun 93 15:04:27 AST

Hello !

In spite of the danger of being flamed (how many people are there in this group
...? ;-), I would like to discuss the possibility to include a 
MPI_APPEND_POINTER function in the MPI standard.

I understand, that the main reason for not including it, is because it would be
necessary to manage buffer memory allocation under MPI.  Therefore a compromise
could be to implement a version of MPI_APPEND_POINTER that does _not_ need any
memory allocation.

The goal of MPI_APPEND_POINTER is basically to simplify the description of
user-types in unbound buffers (see MPI_APPEND_ARRAY and MPI_APPEND_UNION in my
previous post), so that lists and trees may be sent through MPI without too 
much hazzle.

If MPI developes to a successfull standard (I hope it will !),  than sooner or
later, someone will want to use MPI to parallize programs written in other
languages that use pointers or where pointers are essential (just think in lisp
or scheme that are based on list processing).  I think that this capability is
essential, so that MPI may be embraced by a lot of people.

Note that MPI_APPEND_POINTER does not need to be implemented under languages
that do not use pointers, as for example Fortran (as noted by Tony Skjellum).

How could we send a linked list without MPI_APPEND_POINTER ?

struct list {
    my_datatype data;   /* user-type described with an unbound buffer */
    struct list *next;  /* points to next member of the list, last is NULL */
};

All members of the linked list could be copied to a contiguous buffer (otherwise
MPI_APPEND_INDEXED could be used to avoid the copy) and the contiguous buffer is
sent.  At the receiving end, a buffer large enough to hold all members of the
list must be available (through a buffer made with MPI_APPEND_CONTIGUOUS).  
After the members are received, the pointers of each element is set to point 
to the next member in the buffer and the pointer of the last member is set to
NULL.
This isn't very complicated, but sending a list of lists, or a tree can get far
more complex.  The point here, is that the buffer where the list is received 
must be allocated in advance.  Therefore the amount of elements (or the maximum
amount) must be known in advance.

A simpler way to send the linked list could be using MPI_APPEND_POINTER and 
MPI_POINTER_BUFFER defined as follows:

MPI_APPEND_POINTER(buffer, start, size, datatype)

where:
buffer is the MPI_BUFFER,
start is the location of the pointer to a datatype,
size is the amount of bytes needed by datatype,
and datatype is a MPI_BUFFER describing the type where the pointer points to.

MPI_POINTER_BUFFER(buffer, start, size)  must be called before the buffer is
commited and allows to pass a buffer (a piece of memory) starting at start,
and of a length of size bytes (start and size are passed by reference, so
that they may be modified).

When MPI_APPEND_POINTER needs to "allocate memory", it will use the memory
passed by MPI_POINTER_BUFFER.  After the completion of the reception of the
message, start will point after the last byte used and size will reflect the
remaining size of the unused memory.

So, the above example could be implemented as follows:

MPI_BUFFER b, b2;
MPI_BUFFER my_datatype;
struct list my_list;
char *mem;
int memsize;

MPI_CREATE_BUFFER(&b, MPI_PERSISTENCE);
MPI_APPEND_CONTIGUOUS(b, ((list *)0)->data, 1, my_datatype);
MPI_APPEND_POINTER(b, ((list *)0)->next, sizeof(struct list), b);
MPI_COMMIT(b);

MPI_CREATE_BUFFER(&b2, MPI_PERSISTENCE);
MPI_APPEND_CONTIGUOUS(b2, my_list, 1, b);
memsize = sizeof(struct list) * 100;    /* allow to receive 100 elements */
mem = malloc(memsize);	        /* memory allocated by the user, not MPI */
MPI_POINTER_BUFFER(b2, &mem, &memsize);	/* register the memory buffer */
MPI_COMMIT(b2);

Note, that this implementation needs no dynamic memory allocation, because the
memory used by MPI_APPEND_POINTER is already allocated by the user.  In this
respect, we do not have any advantage against the version without MPI_APPEND_
POINTER.  But at least with MPI_APPEND_POINTER it is much simplier to describe
complex structures that use pointers and therefore it is much simplier to send
such user-types through MPI.

Discussion: Eventually MPI_POINTER_BUFFER could be modified to receive an array
of free memory buffers.

Note also, that the receive must have been posted before the message is
received, so that the buffer is available.  A solution to this, could be
to pass a "global" buffer to MPI (passing a MPI_NULL pointer to
MPI_POINTER_BUFFER).

If you ask me, I do not like the restriccions and work-arounds so that
MPI does not need to manage the memory allocation by itself, but between
not being able to describe structures with pointers under C at all, and
a solution similar to the one described here, I'll like the akward
solution.

Ricardo.
-- 
+----------------------+---------------------------------+--------------+
| Ricardo A. Schmutzer | Internet: [email-masked]    | Conectividad |
| PUC, Santiago, Chile |                                 | Distr. Comp. |
+----------------------+---------------------------------+--------------+

---

From: James Cownie <[email-masked]>
Date: Thu, 10 Jun 1993 11:49:54 +0100

I am nervous about introducing indirections into the buffer
description language for the following reasons : -

1) I do not understand how to express the way in which the MPI engine
   should walk an arbitrarily linked structure. In particular is there a
   presumption that the structure contains no cycles ? 
   (Or should MPI be keeping track of visited nodes ?) 
   Is there a presumtion about the value of the NULL pointer ?

2) Introducing pointers has very large implementation implications.
   At present when a buffer is committed the MPI system knows both the
   full type signature of the message, and the absolute store addresses
   of each element. As soon as pointers are introduced, both
   statements cease to be true. (Since the size of the linked
   structure may be different each time.)

I see a strong similarity between sending linked structures and the
mark phase of a garbage collector. This is a non-trivial problem to
solve when the data structures to be traversed are unknown at the time
the traversal code is to be written. 

Therefore I would not like to adopt these proposals in the current
round of MPI. I would however be interested to see further work on
such a system, so that we could better judge the costs and benefits in
later MPI rounds. (I hope that such additions can be made compatible
with the then existing MPI standard).

-- Jim
James Cownie 
Meiko Limited			Meiko Inc.
650 Aztec West			Reservoir Place
Bristol BS12 4SD		1601 Trapelo Road
England				Waltham
				MA 02154

Phone : +44 454 616171		+1 617 890 7676
FAX   : +44 454 618188		+1 617 890 5042
E-Mail: [email-masked]   or    [email-masked]