| Data prefetching is one paradigm to hide the memory latency in modern computer systems. Prefetch completeness requires that a prefetching mechanism achieves high coverage of the program would-be misses with high prefetching accuracy and timeliness. Achieving prefetch completeness has been successful for memory accesses associated with regular data structures like arrays because of the spatial regularity of these memory accesses. Modern applications that use Linked Data Structures (LDS) exhibit a lesser degree of spatial regularity in their theory accesses. Thus, other characteristics of the memory accesses associated with LDS leave been exploited by previous prefetching mechanisms. Unfortunately limited success has been reported for prefetching LDS, therefore a significant opportunity remains to improve the performance of modern computer systems by improving prefetch completeness for LDS memory accesses.; This dissertation proposes a coordinated approach consisting of three components to improve prefetch completeness for LDS. These components are: (1) a rigorous approach that offers metrics to quantify the exploitable characteristics of the memory accesses, (2) a coordinated software and hardware approach that benefits from the static characteristics facilitated by the global view of the compiler combined with the dynamic characteristics accessible via profiling and runtime monitoring, and (3) simultaneous coordination of several mechanisms that exploit different characteristics of the LDS memory accesses.; The proposed coordinated approach is illustrated in this dissertation by extending the understanding of three exploitable characteristics of LDS memory accesses: spatial regularity, temporal regularity, and topology. Metrics are offered to enable the identification of these characteristics, and prefetching mechanisms to exploit them are designed in a coordinated fashion to benefit from the offered metrics.; Simulation results indicate that the proposed approach can improve prefetch completeness by improving prefetch coverage for would-be misses of the program memory accesses using accurate and timely prefetches. |
