SIMPLE COMPILER ALGORITHMS TO REDUCE OWNERSHIP OVERHEAD IN CACHE COHERENCE PROTOCOLS

We study in this paper the design and efficiency of compiler algorithm s that remove ownership overhead in shared-memory multiprocessors with write-invalidate protocols. These algorithms detect loads followed by stores to the same address. Such loads are marked and constitute a hi nt to the cache to obtain an exclusive copy of the block. We consider three algorithms were the first one focuses on load-store sequences wi th each basic block of code and the other two analyse the existence of load-store sequences across basic blocks at the intra-procedural leve l. Since the dataflow analysis we adopt is a trivial variation of live -variable analysis, the algorithms are easily incorporated into a comp iler. Through detailed simulations of a cache-coherent NUMA architectu re using five scientific parallel benchmark programs, we find that the algorithms are capable of removing over 95% of the separate ownership acquisitions. Moreover, we also find that even the simplest algorithm is comparable in efficiency with previously proposed hardware-based a daptive cache coherence protocols to attack the same problem.