Subject: Message ordering promises

From: [email-masked] (Marc Snir)
Date: Wed, 29 Sep 93 09:02:41 -0500

------- Forwarded Message

Date: Tue, 28 Sep 93 22:38:32 PDT
From: [email-masked]
Subject: RE: Order semantics, yet again
To: [email-masked], [email-masked]
Cc: [email-masked], [email-masked]
Message-Id: <[email-masked]>
X-Envelope-To: [email-masked]

Marc Snir asks:

> Anybody feeling strongly that we should not weaken the order
> requirement (in the sense provided by the alternative definition)?
> Any other implementor feeling a weaker requirement would make its
> life simpler (or faster)?  Anybody cares?

and Paul Pierce writes:

> We (Intel) have an implementation that will work better with the relaxed
> ordering requirement, and proposed implementations that would be even more
> sensitive. I support making the rules such that order is guaranteed only for
> exactly matching destination, tag, and communicator parameters.

I care, and I urge us to be very cautious here.

Consider:

   process 0

   MPI_isend(a,1, MPI_REAL, 1, 0, MPI_WORLD)
   MPI_isend(b,1, MPI_REAL, 1, 0, MPI_WORLD)

   process 1: scenario A

   MPI_irecv(a,1, MPI_REAL, 0, MPI_ANYTAG, MPI_WORLD)
   MPI_irecv(b,1, MPI_REAL, 0, MPI_ANYTAG, MPI_WORLD)

   process 1: scenario B

   MPI_irecv(a,1, MPI_REAL, 0, 0, MPI_WORLD)
   MPI_irecv(b,1, MPI_REAL, 0, 0, MPI_WORLD)

By the weaker ordering spec, scenario B would have guaranteed order,
while scenario A would not.  Note that both scenarios are simple
point-to-point.

****
**  Both scenarios would have a guaranteed order, since in each case
** both receives have identical parameters.  The scenario with no
** guaranteed order is:

process 1: scenario C

MPI_irecv(a,1, MPI_REAL, 0, MPI_ANY_TAG, MPI_WORLD)
MPI_irecv(a,1, MPI_REAL, 0, 0, MPI_WORLD)

** i.e., two receives that match the same message, but have
** distinct matching parameters.

** The overhead is at least one additional test if no wildcard receive
** is posted, and some (significant?) additional work if a wildcard
** receive is posted, even when it does not match the incoming
** message.
** Practically, the current semantics probably means using a linear
** search structure, rather than a hash table.
** On the other hand, the current semantics are cleaner, no doubt.

I personally find this counterintuitive and suspect that it would
be the source of some portability Heisenbugs that would be very
hard to find.

I also am not convinced that the penalty for forced ordering is
large enough to worry about.

I think it should be a matter of one test for the receive handler
to find out whether there are wildcard receives posted.  Zero
tests, in fact, if you go to the trouble to install one handler
for the general case and another for when there are no wildcards
posted.

Why is this not correct?  (I.e., can the vendors convince me that
the extra cost is significant, and cannot be eliminated in the
common case by being a bit more clever?)

Thanks,
- --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

------- End of Forwarded Message

---

From: James Cownie <[email-masked]>
Date: Wed, 29 Sep 1993 15:14:14 +0100

Marc writes
** Practically, the current semantics probably means using a linear
** search structure, rather than a hash table.
** On the other hand, the current semantics are cleaner, no doubt.
You can still use a hash structure to match where you know the tag.
However you ALSO have to chain messages (and receives) in arrival
order so that the wildcard receive can get the first one. This is not
TOO bad, it costs a doubly linked list insertion and removal on each
receive. 

Of course the best implementation choice is highly dependent on such 
(unknown, or highly program dependent) parameters as
1) How many unreceived messages are pending ?
2) How many unmatched receives are pending ?

I seem to remember Tony claiming that the answer to 1 is "less than
six". If both numbers are small , then a linear search structure will
win every time despite its poor scaling properties.

I'd keep the current semantics, mostly because I don't want to have to
explain the other semantics to a naive user !

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