Subject: contexts examples/problems 1-3

From: [email-masked]
Date: Mon, 12 Apr 93 10:40:28 PDT

Folks,

As Tony Skjellum noted, I am organizing a set of test cases & issues
to be addressed by the various context proposals.  I have formulated
these as a set of "problems" such as might be found on an essay test.

Here are draft versions of the first three "problem statements"
for the context proposals.

I anticipate that at least one more problem will be submitted.

Please tell me about defects and inadequacies in these problems.

If you have a favorite concern, now is the time to get it
reflected in the problem set.

Thanks,
--Rik Littlefield

BACKGROUND INFO

. Be sure that your point-to-point and group/context control calls
  are specified elsewhere in your proposal.

PROBLEM 1 (simple):

. Specify your calling sequence for an MPI circular-shift routine
  that operates on a contiguous buffer of double precision float
  values.

  E.g. you might specify

    MPI_CSHIFTB (inbuf,outbuf,datatype,len,group,shift)

    where  IN inbuf        input buffer
           OUT outbuf      output buffer
           IN datatype     symbolic constant MPI_DOUBLE
           IN len          length of inbuf (# of elements)
           IN group        handle to group descriptor
           IN shift        number of processes to shift
           
. Assume that a user desires to write a new collective
  communication routine with the same calling sequence as cshift,
  but with different semantics.  

  To be definite, this routine exchanges data in the pattern needed
  for one stage in a butterfly.  I.e., the process of rank i exchanges
  data with the process of rank i+shift*(1-2*(i%(2*shift)/shift).

  Call this routine bflyexchange.

. Show an implementation of bflyexchange in terms of your
  point-to-point and group/context control calls.

. Specify the conditions necessary to ensure correct operation of
  this implementation.

  E.g., you might say "safe under all conditions", "safe if and
  only if no other routine issues wildcard receives in the same
  group/context", "safe if and only if context and tag are
  unique", or something like that.

  Making these conditions simple and broad is good.  
  Getting caught stating conditions that are too broad is bad.

. Discuss the performance of this implementation.  

  Note that the semantics of bflyexchange require only a single send
  and receive per process.  Explain how this level of performance can
  be achieved or approached by your implementation.  

  If you assert that group control operations can be done without
  communications, explain how this works and what implications it has
  on other system parameters, e.g., the number and range of context
  values.

PROBLEM 2 (medium)

. Write a "guidelines for library developers and users" document
  that explains how to write and call libraries in order to maintain
  message-passing isolation between the various libraries and
  between the libraries and the user program.  Be sure to explain
  how to achieve good efficiency.

  Be complete, but brief.

  (Long explanations can be interpreted as indicating a complex
  design.)

  You may wish to describe two or more self-consistent strategies,
  along the lines of Lyndon's "ClassA" and "ClassB" libraries as
  discussed earlier on mpi-context.

PROBLEM 3 (hard?)

This problem is paraphrased from one posed by Jon Flower.  The task
is to simulate the host-node programming model through the use of
"host" and "node" groups.  This is interesting both for backward-
compatibility and for its inter-group communication requirements.

As stated by Jon, this problem really spans subcommittees.  For
the sake of the present discussion, I have reformulated it in
terms of an SPMD programming model in which a black-box function
is used to tell each process whether it's the host or a node.
Note in particular that nodes don't know the id of the host.

Here is pseudo-code for the desired program:

    main()
    {
      if (I_am_the_host())
        host ();
      else
        node ();
    }

    host ();
    /*
     * Form two groups containing:
     *     i)  only the host process.
     *     ii) the node processes.
     */
	host_group = mpi_...;
	node_group = mpi_...;
    /*
     * Broadcast from host to all nodes; using "ALL" group.
     * (It would be nice to have inter-group broadcast for
     *  this since that is more like "current practice".)
     */
	myrank = mpi_...;
	mpi_bcast( ...., myrank, MPI_GROUP_ALL, ...);
    /*
     * Send individual message to each node in turn.
     */
	for(node=0; node < MPI_ORDER(node_group); node++) {
	    mpi_send( ..., (node_group, node), ...);
	}
    /*
     * Receive result from node 0.
     */
	mpi_recv( ..., (node_group, 0), ...);
    }

    node()
    {
    /*
     * Form two groups containing:
     *     i)  only the host process.
     *     ii) the node processes.
     */
	host_group = mpi_...;
	node_group = mpi_...;
    /*
     * Receive bcast from host using ALL group.
     */
	host_rank = mpi_...;
	mpi_bcast(..., host_rank, MPI_GROUP_ALL, ...);
    /*
     * Receive single message from host.
     */
	mpi_recv(..., 0, host_group, ...);
    /*
     * Send point-to-point messages in node group.
     */
        myrank = mpi_... (node_group);
        nnodes = mpi_... (node_group);
        sendhandle = mpi_isend( ..., 
         (node_group,(myrank+1)%nnodes), ...);
        mpi_recv ( ...,
         (node_group,(myrank-1+nnodes)%nnodes), ...);
        mpi_complete (sendhandle);
    /*
     * Compute global sum in nodes only.
     */
	mpi_reduce(...  , node_group, MPI_SUM_OP, ...);
    /*
     * Node 0 sends sum to host.
     */
	 if(myrank == 0) mpi_send(..., 0, host_group, ...);
    }

. Show how to implement this pseudo-code using your point-to-point
  and group calls.  Note that this code wants to think of node
  processes in terms of their rank in the node_group, not the
  ALL group.  Be sure to show all details of any translations
  that are required.

. Discuss how the collective comms and point-to-point messages
  are kept separate, even if the point-to-point calls are
  changed to used wildcards.

----------------------------------------------------------------------
[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