Gather Operations for General-Purpose Microprocessors

Deep cache hierarchies and the latency-tolerating features of modern superscalar microprocessors hide the increasing relative latency of main memory for many applications. However, applications with poor spatial or temporal locality have low cache and TLB hit rates, and thus suffer significant performance degradation due to the cost of main memory accesses. Such applications often have nearly random access patterns, and thus cannot be easily optimized for locality using static compiler techniques. In this paper, we describe Dynamic Cache-line Assembly (DCA), a novel memory controller extension that applications with naturally poor spatial locality can use to create locality by gathering non-contiguous data into dense cache lines. In essence, DCA provides gather memory operations for conventional (non-vector) superscalar microprocessors. We have used DCA to optimize five benchmarks with poor memory locality, and detailed simulation shows that DCA improves performance by a factor of 1.8 to 4.2 on a modern processor, and a factor of 2.4 to 8.1 on a projected processor of 2003. The observed performance improvements are due primarily to improved cache and TLB miss rates.