Cache Coherence Requirements for Interprocess Rendezvous

Multiprocessors in which a shared bus is used by the processors to com-municate with common memory are an emerging class of machines where there is a need to support parallel programming languages. A language construct that is found in a number of parallel programming languages to support syn-chronization and communication i the interprocess rendezvous. Shared-bus multiprocessors require a protocol to keep the date in their caches coherent. There are two major categories ofthese protocols: invalidation and write-broad-cast. This paper examines the requirements for cache coherence protocols to support efficient interprocessor rendezvous. The approach taken is to examine the memory referencing patterns to the run-time data structures during rendez-vous execution. The appropriate coherence protocol is shown to be a function of the processor scheduling strategy used by the run-time system at synchroniza-tion points during the rendezvous. When processes migrate freely as a result of the scheduling strategy, invalidation protocols are found to he more eff• When migration is restricted by the scheduler, write-broadcast protocols are more efficient. KEY WORDS: Cache coherence; rendezvous; run-time systems; process migration; concurrent programming languages. 1