Recently-proposed processor microarchitectures for high Memory Level Parallelism (MLP) promise substantial performance gains. Unfortunately, current cache hierarchies have Miss-Handling Architectures (MHAs) that are too limited to support the required MLPthey need to be redesigned to support 1-2 orders of magnitude more outstanding misses. Yet, designing scalable MHAs is challenging: designs must minimize cache lock-up time and deliver high bandwidth while keeping the area consumption reasonable. This paper presents a novel scalable MHA design for high-MLP processors. Our design introduces two main innovations. First, it is hierarchical, with a small MSHR file per cache bank, and a larger MSHR file shared by all banks. Second, it uses a Bloom filter to reduce searches in the larger MSHR file. The result is a highperformance, area-efficient design. Compared to a state-of-the-art MHA on a high-MLP processor, our design speeds-up some SPECint, SPECfp, and multiprogrammed workloads by a geometric mean of 32%, 50%, and 95%, respectively. Moreover, compared to two extrapolations of current MHA designs, namely a large monolithic MSHR file and a large banked MSHR file, all consuming the same area, our design speeds-up the workloads by a geometric mean of 1-18% and 10-21%, respectively. Finally, our design performs very close to an unlimited-size, ideal MHA. A flurry of recent proposals for novel superscalar microarchitectures claim to support very high numbers of in-flight instructions and, as a result, substantially boost performance [1, 3, 7, 12, 16, 22, 25] . These microarchitectures typically rely on processor checkpointing, long speculative execution, and sometimes even speculative retirement. They often seek to overlap cache misses by using predicted values for the missing data, by buffering away missing loads and their dependents, or by temporarily using an invalid token in lieu of the missing data. Not surprisingly, these microarchitectures require dramatic increases in Memory Level Parallelism (MLP) -broadly defined as the number of concurrent memory system accesses supported by the memory subsystem [5] . For example, one of these designs assumes support for up to 128 outstanding L1 misses at a time [22] . To reap the benefits of these microarchitectures, cache hierarchies have to be designed to support this level of MLP. * This work was supported in part by the National Science Foundation under grants EIA-0072102, EIA-0103610, CHE-0121357, and CCR-0325603; DARPA under grant NBCH30390004; DOE under grant B347886; and gifts from IBM and Intel. Luis Ceze was supported by an IBM Ph.D. Fellowship. Current cache hierarchy designs are woefully unsuited to support this level of demand. Even in designs for high-end processors, the norm is for L1 caches to support only a very modest number of outstanding misses at a time. For example, Pentium 4 only supports 8 outstanding L1 misses at a time [2] . Unless the architecture that handles misses (i.e., the Miss Handling Architecture (MHA)) is redesigned to support 1-2 orders of magnitude more outstanding misses, there will be little gain to realize from the new microarchitectures. A brute-force approach to increasing the resources currently devoted to handling misses is not the best route. The key hardware structure in the MHA is the Miss Status Holding Register (MSHR), which holds information on all the outstanding misses for a given cache line [9, 13] . Supporting many, highly-associative MSHRs in a unified structure may end up causing a bandwidth bottleneck. Alternatively, if we try to ensure high bandwidth by extensively banking the structure, we may run out of MSHRs in a bank, causing cache bank lock-up and eventual processor stall. In all cases, since the MHA is located close to the processor core, it is desirable to use the chip area efficiently. To satisfy the requirements of high bandwidth and low lock-up time in an area-efficient manner, this paper presents a new, scalable MHA design for the L1 cache. More specifically, the paper makes the following three contributions. First, it shows that state-of-the-art MHAs are unable to leverage the new high-MLP processor microarchitectures. Second, it proposes a novel, scalable MHA design for these microarchitectures that delivers the highest performance for a given area consumption. The proposed organization, called Hierarchical, introduces two main innovations. First, it is a hierarchical design, composed of a small per-cache-bank MSHR file, and a larger MSHR file shared by all the cache banks. The per-bank files provide high bandwidth, while the shared one minimizes cache lock-up in the presence of cross-bank access imbalances in an area-efficient manner. The second innovation is a Bloom filter that eliminates the large majority of unnecessary accesses to the shared MSHR file, therefore removing a possible bottleneck. Third, the paper evaluates Hierarchical in the context of a high-MLP processor for some SPECint, SPECfp, and multiprogrammed workloads. Compared to a state-of-the-art MHA similar to that of Pentium 4, Hierarchical speeds-up the workloads by a geometric mean of 32%, 50%, and 95%, respectively. We also compare Hierarchical to two intuitive extrapolations of current MHA designs, namely a large monolithic MSHR file and a large banked MSHR file. For the same area consumption, Hierarchical is faster by a geometric mean of 1-18% and 10-21%, respectively. Finally, Hierarchical performs very close to an unlimited-size, ideal MHA. The paper is organized as follows: Section 2 presents a background and motivation; Section 3 assesses the new MHA challenges; The 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'06) 0-7695-
REF The Adaptive Miss Handling Architecture (AMHA)
Scalable Cache Miss Handling for High Memory-Level Parallelism
2006 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'06)
2006 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'06)
Computer Science