Prefetching is a technique that allows the "consumer" of data to request the data to its cache before it needs them. With multiprocessors, we can think of the "dual" of this technique where the "producer" of the data "evicts" the data from its cache after it is done with them. An extension of such "postflushes" could be to send the data to the next processor that needs the data, in cases where that can be determined.
a. When is prefetching likely to be applicable? When is producer-initiated communication likely to be beneficial? Would producerinitiated communication be applicable in the context of the queuing locks and tree barriers?
b. Assume a shared-memory multiprocessor system that takes 100 cycles for a memory access and 300 cycles for a cache-to-cache transfer. A program running on this machine spends 60% of its time stalled on memory accesses and 20% of its time stalled on synchronization. Of these memory stalls, 20% are due to producer-consumer data access patterns where the writer of data can identify the processor that will read the value next. In these cases, producer-initiated communication can directly transfer data to the cache of the next processor needing the data. This will reduce the latency of these memory accesses from 300 cycles for a cache-to-cache transfer to 1 cycle for a cache hit. Another 30% of the memory stalls are due to migratory data patterns where data move from one processor to another, but the migration path is unclear to the source processor. In this case, a producer-initiated communication primitive, such as "postflush," can reduce the latency of the memory access from 300 cycles to 100 cycles. Further assume that all the synchronization is due to tree barriers and that the tree barrier overhead can be reduced by 40% with producer-initiated communication. Assuming no other overheads, what is the reduction in execution time with producer initiated communication?
c. What memory system and program code changes are required for implementing producer-initiated communication?