Tag matching

Tag matching

Messages sent from task A to task B are normally received in order. However, the USING TAG clause enables a program to enforce a particular order on message reception. USING TAG takes a tag as an argument. This tag can be either an <expr> or a <string>. In the latter case, coNCePTuaL will automatically hash the string to an <expr>. A message sent with a given tag tag is received only by a RECEIVE statement that also specifies tag tag. If the USING TAG clause is omitted, tag defaults to ‘0’.

As an example of the difference USING TAG can make, consider the following code that does not use tags:

TASK 0 SENDS A MESSAGE TO UNSUSPECTING TASK 1 THEN
TASK 0 SLEEPS FOR 2 SECONDS THEN
TASK 0 SENDS A MESSAGE TO UNSUSPECTING TASK 1 THEN
TASK 1 RECEIVES A MESSAGE FROM TASK 0 THEN
TASK 1 SLEEPS FOR 2 SECONDS THEN
TASK 1 RECEIVES A MESSAGE FROM TASK 0

In that example, the first send matches the first receive, then both tasks simultaneously sleep for two seconds, and finally the second send matches the second receive. The total execution time should therefore be just over two seconds. Now consider the following variation that uniquely tags each of the messages:

TASK 0 SENDS A MESSAGE USING TAG 123 TO UNSUSPECTING TASK 1 THEN
TASK 0 SLEEPS FOR 2 SECONDS THEN
TASK 0 SENDS A MESSAGE USING TAG "stuff" TO UNSUSPECTING TASK 1 THEN
TASK 1 RECEIVES A MESSAGE USING TAG "stuff" FROM TASK 0 THEN
TASK 1 SLEEPS FOR 2 SECONDS THEN
TASK 1 RECEIVES A MESSAGE USING TAG 123 FROM TASK 0

The first message is sent with tag ‘123’ while the second message is sent with tag ‘"stuff"’. Task 1 receives the messages in the reverse order: first the ‘"stuff"’ message and then the ‘123’ message. Consequently, task 1’s first RECEIVE cannot complete until task 0 has sent its first message, slept for two seconds, and sent its second message. Task 1 can then receive a message, sleep for two seconds, and receive its other message. The total execution time should therefore be just over four seconds, as the new message ordering forces a serialization on the two SLEEPS.

The following are a few things to keep in mind when using message tags:

1. Using strings for tag values can benefit program readability and is recommended for programs that utilize a small, fixed set of tags, while using numerical expressions for tag values supports the implementation of a variety of sophisticated communication patterns.
2. <string> tags are hashed, not coerced, to numerical values. Hence, a message sent ‘USING TAG 42’ will not be matched by a message received ‘USING TAG "42"’.
3. Different backends place different restrictions on the range of accceptable tag values. For example, the c_mpi backend is limited by MPI’s tag values, which range from 0 to at least 32,767—but usually more. (The range [0, 2^{31}-1] is probably typical.) coNCePTuaL will automatically map any <expr> or <string> used as a tag value into whatever range the backend supports. One implication is that different tags in a coNCePTuaL program can map to the same tag at run time. For example, if a backend limits tag values to the range [0, 32,767], then ‘USING TAG 131068’ is equivalent to ‘USING TAG 0’—or even not using any tag at all. Also, in that case, two arbitrary strings have a 0.003% chance of mapping to the same tag (or 0.00000005% in the more typical case for c_mpi), which is unlikely but not impossible.