Subject: DRAFT cacheing section

From: [email-masked]
Date: Mon, 6 Sep 93 23:27:30 PDT

Folks,

Here is a DRAFT rewrite of the cacheing section of the contexts chapter.
I think that the content is pretty much as I wish, although there are
still some typos & syntax errors in the example.

One aspect that I am very concerned about is the interaction between
cacheing and copying.  I have taken a conservative position in this
proposal.  If you are a fan of copying, please check what I have done
and propose enhancements.

--Rik
----------------------------------------------------------------------
[email-masked] (alias 'd39135')   Rik Littlefield
Tel: 509-375-3927                         Pacific Northwest Lab, MS K1-87
Fax: 509-375-6631                         P.O.Box 999, Richland, WA  99352

% -----------------------------------------------------------------

\section{Cacheing}

MPI provides a ``cacheing'' facility that allows an application
to attach arbitrary pieces of
information, called {\em attributes}, to group and
communicator descriptors.  More precisely, the cacheing facility 
allows a portable library to:
\begin{itemize}
\item 
  pass information between calls by associating it
  with an MPI descriptor, 
\item quickly retrieve that information, and 
\item 
 be guaranteed that out of date information is never retrieved, even if
 the descriptor is freed and its handle reused by MPI.  
\end{itemize}
These
capabilities, in some form, are required by built-in MPI 
routines such as collective
communication and virtual topology.  Defining an interface to
these capabilities as part of the MPI standard 
is valuable because it permits routines like 
collective communication and virtual topology to be implemented as
portable code, and also because it makes MPI more extensible by
allowing user-written routines to use standard MPI calling sequences.

\subsection{Functionality}

Attributes are local to the process and specific to
the descriptor to which they are attached.  They are not
propagated by MPI from one descriptor to another except
when the descriptor is exactly copied (by \func{...\_DUP}, and even then
the application must give specific permission for the attribute
to be copied.  Attributes are scalar values, equal in size or larger than
a C-language pointer.

The cacheing interface defined here represents that attributes are
stored by MPI in some sort of opaque data structure called an
{\em attribute set}.  Accessor functions are provided for
groups and communicators, that return a handle to the associated
attribute set.  Further accessor functions, acting on the
attribute set, are provided to:
\begin{itemize}
\item
 obtain a key value (used to identify an attribute);
\item
 store and retrieve the value of an attribute;
\item
 specify ``callback'' functions by which MPI informs the application
 when the group or communicator is destroyed (by \func{...\_FREE}) or
 copied (by \func{...\_DUP}).
\end{itemize}

\discuss{At the August MPI meeting, concern was expressed that
any form of the cacheing facility might trigger unpleasant 
interactions between memory management in system and user
spaces.  As discussed on the reflectors by Jim Cownie, the
cacheing and callback functions are only called synchronously,
in response to explicit application request.  Because of this
restriction, the memory management concern is considered to be
resolved.}

\discuss{The choice of key values is under control of MPI.  This allows
MPI to optimize its implementation of attribute sets.  It also avoids
conflict between independent modules cacheing information on the same
groups and communicators.}

\discuss{At the August MPI meeting, it was noted that a much
smaller interface, consisting of just 
a callback facility, would allow
the entire cacheing facility to be implemented by portable code.  
Defining such a
minimal interface would have the pleasant effect of making the
MPI specification and implementation smaller.  However, it would
also imply lower efficiency.  With the minimal callback interface,
some form of table searching is implied by the
need to handle arbitrary group and communicator handles.
In contrast, the more complete
interface defined here permits rapid access to attributes 
through the use of pointers in group and communicator descriptors
(to find the attribute table) and cleverly chosen key values (to
retrieve individual attributes).  In light of the efficiency hit
from the minimal interface, the more complete interface proposed
here is felt to be superior.}

\discuss{Also at the August MPI meeting, it was suggested that
a somewhat larger interface would permit attribute tables to be 
used independently of group
and communicator descriptors, and that this would be a good
tradeoff because it would be a relatively cheap way of providing
extra functionality.  It turns out that the increase in size, to
provide a fully consistent interface, is larger than was
suggested at the meeting.
(For example, if callbacks are supposed to be meaningful in isolation,
then in addition to a mechanism for defining them, there must also
be mechanisms for finding out that callbacks have been defined
and for invoking them at appropriate times.)
Accordingly, this proposal defines attribute tables only in
connection with groups and communicators.}

MPI provides the following services related to cacheing.  They are
all process-local. 

% These belong to the suggested ``larger'' interface
% \begin{funcdef}{MPI\_ATTRIBUTE\_ALLOC(n,handle\_array,len)}
% \funcarg {\IN}{ n}{  number of handles to allocate}
% \funcarg {\OUT}{ handle\_array}{ pointer to array of opaque attribute handling structure}
% \funcarg {\OUT}{ len}{ length of each opaque structure}
% \end{funcdef}
% Allocates a new attribute, so user programs and functionality layered
% on top of MPI can access attribute technology.
%  
% \begin{funcdef}{MPI\_ATTRIBUTE\_FREE(handle\_array,n)}
% \funcarg {\IN}{ handle\_array}{ array of pointers to opaque attribute handling structures}
% \funcarg {\IN}{ n}{ number of handles to deallocate}
% \end{funcdef}
% Frees attribute handle.

\begin{funcdef}{MPI\_GROUP\_ATTR (group,attribute\_set)}
\funcarg {\IN}{group}{handle to group descriptor}
\funcarg {\OUT}{attribute\_set}{handle to attribute set}
\end{funcdef}
Given a group, returns that group's attribute set.

\begin{funcdef}{MPI\_COMM\_ATTR (comm,attribute\_set)}
\funcarg {\IN}{comm}{handle to communicator descriptor}
\funcarg {\OUT}{attribute\_set}{handle to attribute set}
\end{funcdef}
Given a communicator, returns that communicator's attribute set.

\begin{funcdef}{MPI\_GET\_ATTRIBUTE\_KEY(keyval)}
\funcarg {\OUT}{ keyval}{ Provide the integer key value for future storing.}
\end{funcdef}
Generates a new attribute key.

\begin{funcdef}
  {MPI\_PUT\_ATTRIBUTE\_VALUE(attribute\_set, keyval, attribute\_val)}
\funcarg{\IN}{attribute\_set}{handle to attribute set}
\funcarg{\IN}{ keyval}
  {integer key value, as returned by MPI\_GET\_ATTRIBUTE\_KEY}
\funcarg{\IN}{ attribute\_val}{attribute value}
\end{funcdef}
Stores attribute value for subsequent retrieval by
\func{MPI\_GET\_ATTRIBUTE\_VALUE} .

\begin{funcdef}
{MPI\_GET\_ATTRIBUTE\_VALUE(attribute\_set,keyval,attribute\_val,found)}
\funcarg{\IN}{attribute\_set}{handle to attribute set}
\funcarg{\IN}{ keyval}{integer key value}
\funcarg{\OUT}{ attribute\_val}{attribute value, unless 
    found = \cconst{MPI\_NOT\_FOUND}}
\funcarg{\OUT}{found}{\cconst{MPI\_FOUND} or \cconst{MPI\_NOT\_FOUND},
    depending on whether the attribute value has been put into this
attribute set}
\end{funcdef}
Retrieves attribute value by key.

\begin{funcdef}{MPI\_PUT\_ATTRIBUTE\_DESTRUCTOR\_CALLBACK
                   (attribute\_set, keyval, 
                   attribute\_destructor\_routine)}
\funcarg{\IN}{attribute\_set} {handle to attribute set}
\funcarg{\IN}{keyval}{key value}
\funcarg{\IN}{attribute\_destructor\_routine}{routine to be called by MPI}
\end{funcdef}
When the group or communicator is freed, MPI calls the destructor
routine for each attribute that has one defined.  The calling
sequence is 
\func{attribute\_destructor\_routine(attribute\_set,keyval,attribute\_val)}.

\begin{funcdef}{MPI\_PUT\_ATTRIBUTE\_COPIER\_STRATEGY
                   (attribute\_set, keyval, strategy,
                   attribute\_copier\_routine)}
\funcarg{\IN}{attribute\_set} {handle to attribute set}
\funcarg{\IN}{keyval}{key value}
\funcarg{\IN}{strategy}{one of \cconst{MPI\_ATTR\_COPY\_FREELY},
       \cconst{MPI\_ATTR\_COPY\_NEVER}, or \cconst{MPI\_ATTR\_COPY\_CALLBACK}}
\funcarg{\IN}{attribute\_copier\_routine}{routine to be called by MPI,
     if strategy = \cconst{MPI\_ATTR\_COPY\_CALLBACK}}
\end{funcdef}
Defines how MPI propagates an attribute when the
group or communicator is copied (via \func{...\_DUP}).  The default
is \cconst{MPI\_ATTR\_COPY\_NEVER}, which means that MPI must
not copy that attribute.  For \cconst{MPI\_ATTR\_COPY\_FREELY},
MPI will copy the attribute and not inform the application.  For
\cconst{MPI\_ATTR\_COPY\_CALLBACK}, MPI copies the value of the
attribute and then calls the copier routine as
\func{attribute\_copier\_routine(attribute\_set,keyval,attribute\_val)}.
The copier routine can, but does not have to, replace the copied value by
doing an explicit 
\func{MPI\_PUT\_ATTRIBUTE\_VALUE(attribute\_set,keyval,new\_value)}.
The most common use of the copy callback mechanism is expected to be to
maintain reference counts on extra storage associated with the 
attribute.

% \begin{funcdef}{MPI\_DELETE\_ATTRIBUTE(handle, keyval)}
% \funcarg{\IN}{ handle}{ opaque attribute handle}
% \funcarg{\IN}{ keyval}{ The integer key value for future storing.}
% \end{funcdef}
% Delete attribute from cache by key.

\subsubsection{Example}
This example shows how to write a collective communication operation
that uses cacheing to be more efficient after the first call.
The coding style assumes that MPI function results return only
error statuses.

\begin{verbatim}
   static int gop_key_assigned = 0;    /* 0 only on first entry */
   static int gop_key;        /* key for this module's stuff */

   typedef struct {
      int ref_count;          /* reference count */
      /* other stuff, whatever else we want */
   } gop_stuff_type;

   Efficient_Collective_Op (comm, ...)
   MPI_comm comm;
   {
     gop_stuff_type *gop_stuff;
     MPI_Group group;
     MPI_Attribute_Set attr_set;
     MPI_Flag foundflag;

     MPI_COMM_GROUP(comm,&group);

     if (!gop_key_assigned)     /* get a key on first call ever */
     { gop_key_assigned = 1;
       if ( ! MPI_GET_ATTRIBUTE_KEY(&gop_key)) {
         mpi_abort ("Insufficient keys available");
       }
     }

     MPI_GROUP_ATTR(group,&attr_set);
     MPI_GET_ATTRIBUTE_VALUE (attr_set,gop_key,&gop_stuff,&foundflag);
     if (foundflag == MPI_FOUND)     
     { /* This module has executed in this group before.
          We will use the cached information */
     }
     else
     { /* This is a group that we have not yet cached anything in.
          We will now do so.
        */

       /* First, allocate storage for the stuff we want,
          and initialize the reference count */

       gop_stuff = (gop_stuff_type *) malloc (sizeof(gop_stuff_type));
       if (gop_stuff == NULL) { /* abort on out-of-memory error */ }
       gop_stuff -> ref_count = 1;

       /* Second, fill in *gop_stuff with whatever we want.
          This part isn't shown here */

       /* Third, store gop_stuff as the attribute value */

       MPI_PUT_ATTRIBUTE_VALUE (attr_set,gop_key,gop_stuff);

       /* Fourth, tell MPI that it can copy the attribute, but has
          to call us back when it does so. */

       MPI_PUT_ATTRIBUTE_COPIER_STRATEGY 
          (attr_set,gop_key,MPI_ATTR_COPY_CALLBACK,gop_stuff_copier);

       /* Fifth, install the destructor routine */

       MPI_PUT_ATTRIBUTE_DESTRUCTOR_CALLBACK
          (attr_set,gop_key,gop_stuff_destructor);
     }
     /* Then, in any case, use contents of *gop_stuff
        to do the global op ... */
    }

    /* The following routine is called by MPI when a group is freed */

    gop_stuff_destructor (attr_set,keyval,gop_stuff)
    MPI_Attribute attr_set;
    int keyval;    
    gop_stuff_type *gop_stuff;
    {
      if (keyval != gop_key) { /* abort -- programming error */ }

      /* The group's being freed removes one reference to this gop_stuff */
      gop_stuff -> ref_count -= 1;

      /* If no references remain, then free the storage */

      if (gop_stuff -> ref_count == 0) {
        free((void *)gop_stuff);
      }
    }

    /* The following routine is called by MPI when a group is copied */

    gop_stuff_copier (attr_set,keyval,gop_stuff)
    MPI_Attribute attr_set;
    int keyval;    
    gop_stuff_type *gop_stuff;
    {
      if (keyval != gop_key) { /* abort -- programming error */ }

      /* The new group adds one reference to this gop_stuff */
      gop_stuff -> ref_count += 1;
    }
\end{verbatim}

\discuss{The cache facility could also be provided for other descriptors, but
it is less clear how such provision would be useful. It is suggested
that this issue be reviewed in reference to Virtual Topologies.}

%----------------------------------------------------------------------

---

From: Ian Glendinning <[email-masked]>
Date: Tue, 7 Sep 93 20:17:30 BST

> still some typos & syntax errors in the example.

I have read Rik's proposal, and it seems pretty sensible to me.  In any case,
regardless of the precise set of routines provided, I would like to add my
voice to Rik and Jim's in support of the general principle of having caching
built into the standard.  Unfortunately I can't attend the next meeting, so
I thought I'd take the opportunity to `bang the drum' while I can.
   Ian
--
[email-masked]        Ian Glendinning
Tel: +44 703 593368                  Dept of Electronics and Computer Science
Fax: +44 703 593045                  University of Southampton SO9 5NH England