Comparing Data Forwarding and Prefetching for Communication-Induced Misses in Shared-Memory MPs

Abstract As the difference in speed between processor and memory system continues to increase, it is becoming crucial to develop and refine techniques that enhance the effectiveness of cache hierarchies. Two such techniques are data prefetching and data forwarding. With prefetching, a processor hides the latency of cache misses by requesting the data before it actually needs it. With forwarding, a producer processor hides the latency of communication-induced cache misses in the consumer processors by sending the data to the caches of the latter. These two techniques are complementary approaches to hiding the latency of communication-induced misses. This paper compares the effectiveness of data forwarding and data prefetching to hide communication-induced misses. Although both techniques require comparable hardware support, forwarding usually has a lower instruction overhead. We evaluate prefetching and forwarding algorithms in a parallelizing compiler using execution-driven simulations of a sharedmemory multiprocessor. Both data forwarding and prefetching reduce the execution time of applications significantly (30- 40 % on average). Forwarding performs better on average, while prefetching is more robust to changes in cache and memory parameters. Finally, we propose two ways of integrating the two techniques. The integration of the two techniques reduces the execution time even more (43-48 % on average) and is very robust. 1 Introduction As increases in processor speed continue to outstrip increases in memory system speed, it becomes crucial to develop and refine techniques that enhance the effectiveness of cache hierarchies. An important reason why cache hierarchies are sometimes ineffective in multiprocessors is the intrinsic interprocessor communication required by applications. To tolerate this communication, popularly known as data sharing, techniques that overlap processor computation with the communication have been proposed. Two of these techniques are data forwarding and data prefetching. In data forwarding [1, 8, 10], producer processors send the data to the caches of the processors that will use the dat