Bouquet of Instruction Pointers: Instruction Pointer ... pointers at the L1 cache level, and issues

  • View

  • Download

Embed Size (px)

Text of Bouquet of Instruction Pointers: Instruction Pointer ... pointers at the L1 cache level, and issues

  • Bouquet of Instruction Pointers: Instruction Pointer Classifier-based Spatial Hardware Prefetching

    Samuel Pakalapati Intel Technology Private Limited

    Birla Institute of Technology and Science, Pilani* Hyderabad, India

    Biswabandan Panda Dept. of Computer Science and Engineering

    Indian Institute of Technology Kanpur Kanpur, India

    Abstract—Hardware prefetching is one of the common off-chip DRAM latency hiding techniques. Though hardware prefetchers are ubiquitous in the commercial machines and prefetching tech- niques are well studied in the computer architecture community, the “memory wall” problem still exists after decades of micro- architecture research and is considered to be an essential problem to solve. In this paper, we make a case for breaking the memory wall through data prefetching at the L1 cache.

    We propose a bouquet of hardware prefetchers that can handle a variety of access patterns driven by the control flow of an application. We name our proposal Instruction Pointer Classifier based spatial Prefetching (IPCP). We propose IPCP in two flavors: (i) an L1 spatial data prefetcher that classifies instruction pointers at the L1 cache level, and issues prefetch requests based on the classification, and (ii) a multi-level IPCP where the IPCP at the L1 communicates the classification information to the L2 IPCP so that it can kick-start prefetching based on this classification done at the L1. Overall, IPCP is a simple, lightweight, and modular framework for L1 and multi-level spatial prefetching. IPCP at the L1 and L2 incurs a storage overhead of 740 bytes and 155 bytes, respectively.

    Our empirical results show that, for memory-intensive single- threaded SPEC CPU 2017 benchmarks, compared to a baseline system with no prefetching, IPCP provides an average perfor- mance improvement of 45.1%. For the entire SPEC CPU 2017 suite, it provides an improvement of 22%. In the case of multi- core systems, IPCP provides an improvement of 23.4% (evaluated over more than 1000 mixes). IPCP outperforms the already high- performing state-of-the-art prefetchers like SPP with PPF and Bingo by demanding 30X to 50X less storage.

    Index Terms—Hardware Prefetching, Caching


    Improved hardware prefetchers at the different levels of cache hierarchy translate to performance gain by reducing the off-chip costly DRAM accesses. Hardware prefetchers such as next-line (NL) and stride based on instruction pointer (IP- stride) [18] are some of the simple, efficient, and light-weight data prefetchers employed at the L1 level. Well-established and recent spatial L2 prefetchers (prefetchers that prefetch within a spatial region) [33], [13], [14], [38], [11], [45] have pushed the limits of data prefetching. Apart from these spatial prefetchers, there are temporal prefetchers [54], [55], [24], [12], [59], [58] that target irregular but temporal accesses. In general, spatial

    * A major part of the work was done through a remote internship, while the author was at BITS Pilani.

    prefetchers demand less storage (closer to tens of KBs, except spatial memory streaming (SMS) [47] and Bingo [11]) as compared to the temporal ones (closer to hundreds of KBs). In the 3rd Data Prefetching Championship (DPC-3) [3], variations of these proposals were proposed1.

    It is well understood that the prefetchers at L1 and L2 would need to be different as the access patterns at the L2 are different from those at the L1 (filtered by the L1). The primary reason being, identifying access patterns at the L2 is not trivial as the L1 prefetcher may cover a few demand misses or may trigger additional inaccurate prefetch requests jumbling the access pattern at the L2. Note that, most of the recent spatial prefetchers are L2 based with prefetchers like NL and IP-stride dominating the space of L1 data prefetching.

    The opportunity: One of the key objectives behind design- ing hardware prefetchers is to break the memory wall by hiding the costly off-chip DRAM accesses. An ideal solution to the memory wall problem would be an L1-D cache (L1-D) hit rate of 100%, with permissible access latency. One of the ways to achieve the same is through L1-D prefetching. Prefetching at the L1-D provides the following benefits (i) unfiltered memory access pattern, (ii) prefetched blocks can get filled into all the levels of cache hierarchy (more importantly, the L1-D), (iii) an ideal L1-D prefetcher can make the L2 prefetcher superfluous.

    The challenges: The benefits mentioned above come with the following challenges. (i) Hardware overhead: an L1- D prefetcher should be light-weight. (ii) Prefetch address generation should meet the lookup latency requirement of L1-D. (iii) An L1-D prefetcher should not probe the L1-D on every prefetch access (to make sure that the address is already not present in the L1 cache) as L1-D is bandwidth starved. (iv) Aggressive hardware prefetching may not be possible at the L1-D because of limited entries at the supporting hardware resources such as prefetch queue (PQ) and miss-status-holding- registers (MSHRs). For example, typically, the #entries in the PQ and MSHR of L1-D is one-half of L2’s. (v) An L1-D prefetcher with low accuracy can pollute the small L1-D.

    The problem: State-of-the-art spatial prefetchers [45] [33], [11], [14], [13] are designed specifically for L2’s access patterns.

    1A preliminary version of bouquet of prefetchers won the 3rd data prefetching championship.


    2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)

    978-1-7281-4661-4/20/$31.00 ©2020 IEEE DOI 10.1109/ISCA45697.2020.00021

  • Prefetchers like SMS [47], [49] and Bingo [11] are capable of prefetching at the L1-D. However, both SMS and Bingo demand hardware overhead closer to 100KB.

    Our goal is to propose a lightweight spatial L1-D prefetcher that can overcome the challenges and seize the opportunities mentioned above without compromising the prefetch accuracy and prefetch coverage.

    Our approach: We propose a prefetching framework in the form of a bouquet of prefetchers based on instruction pointer (IP) classification (driven by the control flow of an application). We cover a wide variety of memory access patterns like (i) only control flow, (ii) control flow predicted data flow, and (iii) control flow coupled with data flow. We find that each IP can be classified into unique IP-classes based on its access patterns, and the resulting classification could be used for better prefetching. We perform IP classification at the L1-D and use it for L1-D prefetching. We also extend our framework to the L2 prefetcher by communicating the IP classification information from the L1-D prefetcher.

    Overall, we make the following key contributions: • We find that spatial access patterns can be correlated with

    the IPs and motivate the need for lightweight spatial L1-D prefetchers (Section III).

    • We propose Instruction Pointer Classification based spatial Prefetching (IPCP) that classifies IPs into three classes and design a tiny prefetcher per class (Section IV). These tiny prefetchers cover more than 60%, 70%, and 80% of the L1, L2, and last-level cache (LLC) demand misses for memory-intensive (LLC MPKI≥1) SPEC CPU 2017 applications, respectively (refer Figure 10).

    • We propose a bouquet of tiny prefetchers that work in harmony with each other through per-class throttling and hierarchical priority (Section V).

    • We also communicate the classification information from L1-D to L2, facilitating multi-level prefetching using the common theme. Overall, IPCP is an extremely lightweight framework that demands 895 bytes (Section V).

    • On average, compared to no prefetching, IPCP provides a performance improvement of 45.1%, 22%, and 23.4% for single-core memory-intensive applications, single-core all applications, and multi-core mixes with 4 and 8-cores, respectively. IPCP provides this performance with 30X to 50X lower hardware overhead when compared to state- of-the-art spatial prefetchers (Section VI).


    Spatial prefetchers: Spatial prefetchers predict strides, streams, or complex strides within a spatial region providing competitive coverage. Prefetchers like variable length delta prefetching (VLDP) [45] and signature path prefetching (SPP) [33] are well known delta prefetchers. VLDP stores the history of deltas to predict future deltas. SPP is a state-of-the- art delta prefetcher that predicts the non-constant (irregular) strides (commonly known as deltas). SPP works based on the signatures (hash of deltas) seen within a physical OS page to index into a prediction table that predicts future delta. It

    dynamically controls the prefetch aggressiveness based on the success probability of future deltas.

    Spatial Memory Streaming (SMS) [47], [49] is a spatial prefetcher that exploits the relationship between the IP of a memory request, and access pattern within a spatial region based on the IP and the first offset within that region. SMS incurs huge storage overhead, which is larger than the L1-D size. A recent work called Bingo [11], uses multiple signatures (like IP, IP+Offset, and memory region) and fuses them into a single hardware table. Bingo provides better coverage than SMS. However, Bingo incurs similar overhead as SMS (around 119KB). There are component prefetchers like division of labor (DOL) [35] that target specific program semantics (like pointer chains, loops, etc.) for prefetching by getting the information of interest from the processor core.

    Offset prefetchers: Offset based prefetchers such as Best- offset Prefetcher (BOP) [38] and Sandbox [42] prefetcher