Subject: mpi-pt2pt: ready receiver

From: L J Clarke <[email-masked]>
Date: Thu, 8 Apr 93 12:33:28 BST

Dear MPI colleagues.

This is  the  promised "ready-receiver"  follow  up  to my  "mpi-comm:
various (long)" message. It is not so long :-) The first part follows
through from the mentioned letter. The second part is more thoughts on
ready receiver unrelated to the mentioned letter.

			o--------------------o

I begin  by describing  ready-receiver  communication  for  secure and
insecure contexts.  For an insecure context this is exactly as we have
discussed in  the  meetings.  For a secure context I suggest  that the
ready-reciever is exactly the same as an insecure-context, except that
send  gets  an acknowledge  from the receiver  MPI  saying whether the
ready-receiver message  is accepted  or discarded (although I am happy
to drop the suggested acknowledge for  secure ready-receiver in  which
case it really does become less than secure.)

			o--------------------o

Now I wish to make  a more general comment about  ready-receiver which
is not in any way related to the secure/insecure context suggestion.

My understanding  of the argument for ready-receiver is that,  if used
in  MPI  user  software,  will provide  performance  benefit  on  some
machines  (where  ready-receiver  is  implemented  with essentially no
protocol)  and  will  not  incur  penalty  on  other  machines  (where
ready-receiver is implemented as regular). I claim that on  the latter
machines  software written with ready-receiver will actually go slower
than equivalent software written without ready-receiver. The reason
for this claim is quite simple, here is an example.

Consider a "classic" case where ready-receiver can optimise a program,
a fan-in and fan-out algorithm over a binary tree. Each node in the
tree, which is not a leaf and not the root, executes the following in
versions with ready-receive and without ready-receive.

With Ready-receiver               |   Without Ready-receiver  
-------------------               |   ----------------------           
                                  |                                    
regular receive from each child   |   regular receive from each child  
                                  |                                    
process child messages            |   process child messages           
                                  |                                    
start nbrecv from parent          |   
                                  |                                    
send to parent                    |   send to parent                   
                                  |                                    
wait for nbrecv from parent       |   recv from parent      
                                  |                                    
ready-receiver send to each child |   send to each child

When ready-receiver is  implemented as send, the version  on the  left
(written with ready-receiver) is slower  than the version on the right
(written  without ready-receiver) since  the  node  must perform  more
operations, and in  particular  may  have  to hit  the system one more
time, as the diagram clearly shows. 

The summary of this is that we can expect actual use of ready-receiver
to  sometimes  make  software go faster and sometimes make software go
slower.  I guess we beg the questions:

A) How much faster  is  the  left version  than the right version when
ready-receiver is not the same as regular?

B) How much  slower  is the left  version than the right version  when
ready-receiver is the same as regular?

			o--------------------o

Comments, questions, (flames :-) please?

Best Wishes
Lyndon

         /--------------------------------------------------------\
    e||) | Lyndon J Clarke    Edinburgh Parallel Computing Centre | e||) 
    c||c | Tel: 031 650 5021  Email: [email-masked]  | c||c 
         \--------------------------------------------------------/