Other Optimizations

Two optimizations can be made to the barrier implementation in the previous section:

• Communication computation overlap: The requests sent by a thread need not be sent at the sink statement of a flow dependence arc. A variety of prefetch mechanisms may be used. Communication computation overlap can be achieved by pulling the request statement as far above the receive as possible. Clearly, it cannot be pulled beyond the source statement of the dependence arc. It is also limited by the point at which the owner of the remote data can be anticipated. For example, in Figure 2.10, there is a flow dependence arc from s1 to s3, but the request cannot be pulled up beyond s2. Hence, the lexically later of these two points determines the optimal point at which requests may be placed.

   
  Figure 2.10:  Example in which request cannot be pulled up to source
  

  An important consequence of separating requests from receives is that it is possible for many replies to be present when a receive is executed. The message tag is used to disambiguate replies in these situations. Each flow dependence arc in the synchronization graph is assigned a unique integer tag at compile time. All communication due to that arc uses the integer tag. Hence, at a receive statement for a particular dependence arc, only the reply with the tag corresponding to that dependence arc should be accepted.

• Coalescing messages: Assume there are N threads in the par statement and P processors on which they have to execute. Hence, there are threads per processor. If the threads on a processor execute asynchronously, there will be many messages exchanged between threads across processors. Since message startup is extremely costly, it is very beneficial to coalesce messages. This is done by having all the threads on a processor execute synchronously within a single process, so that at the point of sending a request, the requests of all threads can be collected and sent as one message per remote processor. Hence each message now contains the requests, replies or acknowledgements of many threads.