Optimal Loop Scheduling for Hiding Memory Latency Based on Two-Level Partitioning and Prefetching

The large latency of memory accesses in modern computers is a key obstacle in achieving high processor utilization. As a result, a variety of techniques have been devised to hide this latency. These techniques range from cache hierarchies to various prefetching and memory management techniques for manipulating the data present in the caches. In DSP applications, the existence of large numbers of uniform nested loops makes the issue of loop scheduling very important. In this paper, we propose a new memory management technique that can be applied to computer architectures with three levels of memory, the scheme generally adopted in contemporary computer architecture. This technique takes advantage of access pattern information that is available at compile time by prefetching certain data elements from the higher level memory before they are explicitly requested by the lower level memory or CPU. It also maintains certain data for a period of time to prevent unnecessary data swapping. In order to take better advantage of the locality of references present in these loop structures, our technique introduces a new approach to memory management by partitioning it and reducing execution to each partition, so that data locality is much improved compared with the usual pattern. These combined approaches { using a new set of memory instructions as well as partitioning the memory { lead to improvements in average execution times of approximately 35 % over the one-level partition algorithm and more than 80 % over list scheduling and hardware prefetching. This work is partially supported by grants NSF MIP95-01006, NSF ACS 96-12028 and JPL 96109