Effective caching for multithreaded processors
David May, J. David Irwin, Henk Muller, Daniel R. Page · Bristol Research (University of Bristol) · 2000
Multithreaded architectures have been developed as a way to hide latencies in memory access, communication, and long pipelines. Caches have been developed to hide latencies and reduce memory bandwidth requirements. Caches do not work well in multithreaded environments, because threads unintentionally evict each others data and instructions. To enable effective use of caches in a multithreaded environ- ment (giving high execution speed even in the context of high memory latencies), we propose to use a cache architecture where the cache can be divided into partitions. Each thread is assigned a set of partitions which are used to cache a view of data structures, or part of the instruction stream. The partition assignment is completely automated in the compiler. With our compiler and architecture, all forms of interfer- ence are eliminated and predictable execution of multithreaded programs is achieved in moderately sized caches. 1 Microprocessor Caches Currently, both uniprocessor and multiprocessor computer architectures rely heavily on the use of caches. A cache is a small area of fast memory placed between the processor and main memory. The cache aims to exploit temporal and spatial locality of the application code and its data. A limiting problem in multithreaded architectures is cache interference between threads of execution. As accesses to data objects are interleaved the location of several data objects (and instruction segments) may map to the same area of the cache, the threads will compete for cache space and each thread may displace information that is useful elsewhere. This inter- ference will result in degraded performance, a problem that is exacerbated by the increasing speed-gap between memory and processor. Intuitive steps to solve this problem such as in- creasing the cache size or associativity are not always effective and seldom scale well as task complexity increases. The following two programs are a faithful example of how interference occurs. Depend- ing on how the data objects are arranged in memory, it is possible for them to compete for cache space with data objects referenced in the same thread, and with objects referenced in other threads. As the number and complexity of threads increases, this effect becomes harder to predict and model.