USING DATA-FLOW ANALYSIS TECHNIQUES TO REDUCE OWNERSHIP OVERHEAD IN CACHE COHERENCE PROTOCOLS

In this article we explore the potential of classical dataflow analysi s techniques in removing overhead in write-invalidate cache coherence protocols for shared-memory multiprocessors. We construct three compil er algorithms with varying degree of sophistication that detect loads followed by stores to the same address. Such loads are marked and cons titute a hint to the cache to obtain an exclusive copy of the block so that the subsequent store does not introduce access penalties. The si mplest of the three compiler algorithms analyzes the existence of load -store sequences within each basic block of code whereas the other two analyze load-store sequences across basic blocks at the intraprocedur al level. The algorithms have been incorporated into an optimizing C c ompiler, and we have evaluated their efficiencies by compiling and exe cuting seven parallel programs on a simulated multiprocessor. Our resu lts show that the detection efficiency of the most aggressive algorith m is 96% or higher for four of the seven programs studied. We also com pare the efficiency of these static algorithms with that of dynamic ha rdware-based algorithms that reduce ownership overhead. We find that t he static analysis using classical dataflow analysis results in simila r performance improvements as dynamic hardware-based approaches.