Rahul Bera

Konstantinos Kanellopoulos

Shankar Balachandran

David Novo

Ataberk Olgun

Mohammad Sadrosadati

Onur Mutlu

Long-latency load requests continue to limit the performance of modern high-performance processors. To increase the latency tolerance of a processor, architects have primarily relied on two key techniques: sophisticated data prefetchers and large on-chip caches. In this work, we show that: (1) even a sophisticated stateof-the-art prefetcher can only predict half of the o -chip load requests on average across a wide range of workloads, and (2) due to the increasing size and complexity of on-chip caches, a large fraction of the latency of an o -chip load request is spent accessing the on-chip cache hierarchy to solely determine that it needs to go o -chip.

The goal of this work is to accelerate o -chip load requests by removing the on-chip cache access latency from their critical path. To this end, we propose a new technique called Hermes, whose key idea is to: (1) accurately predict which load requests might go o -chip, and (2) speculatively fetch the data required by the predicted o -chip loads directly from the main memory, while also concurrently accessing the cache hierarchy for such loads.

To enable Hermes, we develop a new lightweight, perceptronbased o -chip load prediction technique that learns to identify o -chip load requests using multiple program features (e.g., sequence of program counters, byte o set of a load request). For every load request generated by the processor, the predictor observes a set of program features to predict whether or not the load would go o -chip. If the load is predicted to go o -chip, Hermes issues a speculative load request directly to the main memory controller once the load's physical address is generated. If the prediction is correct, the load eventually misses the cache hierarchy and waits for the ongoing speculative load request to nish, and thus Hermes completely hides the on-chip cache hierarchy access latency from the critical path of the correctly-predicted o -chip load. Our extensive evaluation using a wide range of workloads shows that Hermes provides consistent performance improvement on top of a state-of-the-art baseline system across a wide range of con gurations with varying core count, main memory bandwidth, high-performance data prefetchers, and on-chip cache hierarchy access latencies, while incurring only modest storage overhead.

Introduction

Long-latency load requests signi cantly limit the performance of high-performance out-of-order (OOO) processors. A load request that misses in the on-chip cache hierarchy and goes to the o -chip main memory (i.e., an o -chip load) often stalls the processor core by blocking the instruction retirement from the reorder bu er (ROB), thus limiting the core's performance [START_REF] Mutlu | Techniques for E cient Processing in Runahead Execution Engines[END_REF][START_REF] Mutlu | Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-order Processors[END_REF][START_REF] Mutlu | Runahead Execution: An E ective Alternative to Large Instruction Windows[END_REF]. To increase the latency tolerance of a core, computer architects primarily rely on two key techniques. First, they employ increasingly sophisticated hardware prefetchers that can learn complex memory address patterns and fetch data required by future load requests before the core demands them [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF][START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF][START_REF] Bera | DSPatch: Dual Spatial Pattern Prefetcher[END_REF][START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF][START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF]. Second, they signi cantly scale up the size of the on-chip cache hierarchy with each new generation of processors [START_REF]Golden Cove -Microarchitectures -Intel[END_REF][START_REF]Golden Cove Microarchitecture (P-Core) Examined[END_REF][START_REF]Intel Details Golden Cove[END_REF].

Key problem. Despite recent advances in processor core design, we observe two key trends in new processor designs that leave a signi cant opportunity for performance improvement on the table. First, even a sophisticated state-of-the-art prefetcher can only predict half of the long-latency o -chip load requests on average across a wide range of workloads (see §2). This is because even the most sophisticated prefetchers cannot easily learn the irregular access patterns in programs. Second, a large fraction of the latency of an o -chip load request is spent on accessing the multi-level on-chip cache hierarchy. This is primarily due to the increasing size of the on-chip caches [START_REF]Intel Core i5-12600K DDR4 Alder Lake CPU Review[END_REF][START_REF]Surprisingly High Latency Discovered in Alder Lake[END_REF][START_REF]The Intel 12th Gen Core i9-12900K Review[END_REF]. To cater to workloads with ever increasing data footprints, on-chip caches in recent processors are growing in size and complexity [START_REF] Beckmann | Managing Wire Delay in Large Chip-Multiprocessor Caches[END_REF][START_REF] Hardavellas | Reactive NUCA: Near-Optimal Block Placement and Replication in Distributed Caches[END_REF][START_REF] Wang | Stream Floating: Enabling Proactive and Decentralized Cache Optimizations[END_REF]. A larger onchip cache, on the one hand, improves a core's performance by reducing the fraction of load requests that go o -chip [START_REF] Jaleel | High Performance Cache Replacement Using Re-Reference Interval Prediction (RRIP)[END_REF][START_REF] Qureshi | Adaptive Insertion Policies for High Performance Caching[END_REF][START_REF] Wu | SHiP: Signature-based Hit Predictor for High Performance Caching[END_REF]. On the other hand, a larger cache comes with longer cache access latency, which increases the latency of each ochip load request [START_REF]L3 Cache Latency Comparison at Base Frequency[END_REF].

Our goal in this work is to accelerate long-latency o -chip load requests by removing on-chip cache access latency from their critical path. To this end, we introduce a new technique called Hermes, whose key idea is to predict which load requests might go o -chip and start fetching their corresponding data directly from the main memory, while also concurrently accessing the cache hierarchy for such a load. 1 By doing so, Hermes hides the on-chip cache access latency under the shadow of the main memory access latency (as illustrated in Fig. 1), thereby signi cantly reducing the overall latency of an o -chip load request. Hermes works in tandem with any hardware data prefetcher and reduces the long memory access 1 arXiv:2209.00188v3 [cs.AR] 30 Sep 2022 latency of o -chip load requests that otherwise could not have been prefetched by sophisticated state-of-the-art prefetchers.

L1 L2 LLC Main Memory

Main Memory

L1 L2 LLC

Processor is stalled Latency tolerance limit of ROB

Saved stall cycles

Baseline

Start fetching data from main memory a6ter physical address is available

Hermes

Predict whether the load will go o=f-chip Key challenge. Although Hermes can potentially improve performance by removing the on-chip cache access latency from the critical path of a correctly-predicted o -chip load request, its performance gain signi cantly depends on how accurately it can identify the o -chip load requests. This is because a false-positive o -chip prediction (i.e., a load request that is predicted to go o -chip but hits in the cache) generates an unnecessary main memory request, incurring additional main memory bandwidth and latency overheads, which can easily diminish the performance bene t gained by the load latency reduction.

We identify two key challenges in designing an accurate o -chip load prediction mechanism. First, in a system with state-of-the-art high-performance prefetchers, only 1 out of 20 load requests generated by a program on average eventually goes o -chip (see §3.2). Such a small fraction of o -chip loads makes it di cult for an o -chip load predictor to accurately and robustly learn from program behavior to produce highlyaccurate predictions. Second, the accuracy of the o -chip prediction of a load can change in the presence of sophisticated prefetching techniques, making it even harder for an o -chip load predictor to learn from both the program's and the prefetcher's behavior.

Limitations of prior works. Several prior works [START_REF] Jalili | Reducing Load Latency with Cache Level Prediction[END_REF][START_REF] Memik | Just Say No: Bene ts of Early Cache Miss Determination[END_REF][START_REF] Sembrant | The Direct-to-Data (D2D) Cache: Navigating the Cache Hierarchy with a Single Lookup[END_REF][START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF] propose predicting the cache level that would serve a given load request to enable various performance optimizations (e.g., better instruction scheduling). However, most of these works su er from two key limitations that make them unsuitable for o -chip load prediction. First, prior predictors su er from low prediction accuracy (i.e., the fraction of predicted o -chip load requests that actually went o -chip) [START_REF] Memik | Just Say No: Bene ts of Early Cache Miss Determination[END_REF][START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF], which increases the bandwidth overhead in main memory. As a result, they often lose the performance bene t gained by the load latency reduction and might lower performance than the baseline system (see §8.1.1 and §8.2.2). Second, prior o -chip load prediction mechanisms often incur impractical metadata overhead (e.g., an operating-system-managed metadata storage inside the physical main memory [START_REF] Jalili | Reducing Load Latency with Cache Level Prediction[END_REF], extending each TLB and cache entry with additional metadata for tracking cache residence and coherence of data [START_REF] Sembrant | The Direct-to-Data (D2D) Cache: Navigating the Cache Hierarchy with a Single Lookup[END_REF][START_REF] Sembrant | A Split Cache Hierarchy for Enabling Data-Oriented Optimizations[END_REF]), which hinders adoption in commercial processors.

Key mechanism. To enable Hermes, we introduce a new lightweight perceptron-based o -chip predictor, called POPET, that learns to identify o -chip load requests using multiple program features (e.g., sequence of program counters, byte o set of a load request). For every load generated by the processor, POPET observes a set of program features to predict whether or not the load would go o -chip. If the load is predicted to go o -chip, Hermes issues a speculative load request (called a Hermes request) directly to the main memory controller once the load's physical address is generated. This Hermes request is serviced by the main memory controller concurrently with the regular load request (i.e., the load issued by the processor that generated the Hermes request) that accesses the on-chip cache hierarchy. If the prediction is correct, the regular load request eventually misses the cache hierarchy and waits for the ongoing Hermes request to nish, and thus Hermes completely hides the on-chip cache hierarchy access latency from the critical path of a correctly-predicted o -chip load.

Results summary. We evaluate Hermes with a diverse set of 110 single-core and 220 multi-core workloads spanning SPEC CPU2006 [START_REF]SPEC CPU[END_REF], SPEC CPU2017 [START_REF]SPEC CPU[END_REF], PARSEC [START_REF]PARSEC[END_REF], Ligra [START_REF] Shun | Ligra: A Lightweight Graph Processing Framework for Shared Memory[END_REF] graph processing workloads, and commercial workloads [START_REF]Second Championship Value Prediction (CVP-2)[END_REF]. Our evaluation yields ve key results that demonstrate Hermes's e ectiveness. First, POPET achieves on average 77.1% accuracy and 74.3% coverage (i.e., the fraction of o -chip load requests of a workload that are successfully predicted), both of which are signi cantly higher (1.6× higher accuracy, 3.3× higher coverage) than that of the prior best-accuracy o -chip predictor, HMP [START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF]. Second, Hermes improves performance on average by (up to) 5.4% (23.4%), 5.1% (25.7%), and 6.2% (32.2%) in single-core, eight-core, and bandwidth-constrained system con guration, on top of the best-performing state-of-the-art data prefetcher Pythia [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF]. Third, Hermes consistently improves performance when combined with any baseline hardware data prefetcher. When implemented combined with four recently-proposed highperformance prefetchers (SPP [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF][START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF], Bingo [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF], MLOP [START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF], and SMS [START_REF] Somogyi | Spatial Memory Streaming[END_REF]) in single-core system, Hermes improves performance on average by (up to) 5.1% (27%), 6.2% (22.4%), 7.6% (26.7%), and 7.7% (25.7%). Fourth, Hermes provides better performance-to-overhead bene t than traditional prefetchers due to its highly-accurate o -chip predictions. For every 1% performance increase, Hermes increases the main memory requests by only 0.5%, whereas Pythia increases them by 2%. Fifth, all of Hermes's bene ts come at a very modest storage overhead of only 4 KB per core, while the state-of-the-art prefetcher Pythia consumes 25.5 KB per core.

We make the following contributions in this paper: • We identify two key opportunities for performance improvement in modern processors: (1) a signi cant fraction of the load requests continues to go o -chip even in the presence of sophisticated data prefetchers, and (2) an increasing fraction of the o -chip load latency is spent accessing on-chip caches due to the increasing size of the on-chip cache hierarchy.

Motivation

High main memory access latency continues to limit the performance of modern out-of-order (OOO) processors. A load request that misses the on-chip cache hierarchy and goes to ochip main memory often blocks instruction retirement from the reorder bu er (ROB), preventing the processor from allocating new instructions into the ROB [START_REF] Hashemi | Continuous Runahead: Transparent Hardware Acceleration for Memory Intensive Workloads[END_REF][START_REF] Mutlu | Techniques for E cient Processing in Runahead Execution Engines[END_REF][START_REF] Mutlu | Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-order Processors[END_REF][START_REF] Mutlu | Runahead Execution: An E ective Alternative to Large Instruction Windows[END_REF], limiting performance.

To tolerate long memory latency, recent high-performance OOO cores have primarily relied on two key techniques. First, modern cores have signi cantly scaled up their on-chip cache size (e.g., each Intel Alder Lake core [START_REF]Golden Cove -Microarchitectures -Intel[END_REF] employs 4.3MB onchip cache (including L1, L2 and a per-core last-level cache (LLC) slice), which is 1.88× larger than the on-chip cache in the previous-generation Skylake core [START_REF]6th Generation Intel® Processor Family[END_REF]). Second, modern cores employ increasingly sophisticated hardware prefetchers [START_REF]Golden Cove Microarchitecture (P-Core) Examined[END_REF][START_REF]Intel Details Golden Cove[END_REF] that can more e ectively predict the addresses of load requests in advance and fetch their corresponding data to onchip caches before the program demands it, thereby completely or partially hiding the long o -chip load latency for a fraction of o -chip loads [START_REF]Golden Cove Microarchitecture (P-Core) Examined[END_REF][START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF][START_REF] Bera | DSPatch: Dual Spatial Pattern Prefetcher[END_REF][START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF].

Despite these advances, we observe two key trends in processor design that leave a signi cant performance improvement opportunity on the table : (1) a large fraction of load requests continues to go o -chip even in the presence of state-of-the-art prefetchers, and (2) an increasing fraction of the latency of an o -chip load request is spent accessing the increasingly larger on-chip caches.

A large fraction of loads is still uncovered by state-ofthe-art prefetchers. Over the past decades, researchers have proposed many hardware prefetching techniques that have consistently pushed the limits of performance improvement (e.g., [26, 32, 33, 35, 37, 45, 46, 56, 70, 75-77, 79, 85, 94, 98, 106, 107, 110, 111]). We observe that state-of-the-art prefetchers provide a large performance gain by accurately predicting future load addresses. Yet, a large fraction of o -chip load requests cannot be predicted even by the most advanced prefetchers. These uncovered requests limit the processor's performance by blocking instruction retirement in the ROB. Fig. 2 shows a stacked graph of total number o -chip load requests in a no-prefetching system and a system with the recently-proposed hardware data prefetcher Pythia [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF], normalized to the no-prefetching system, across 110 workload traces categorized into ve workload categories. 2 Each bar further categorizes load requests into two classes: loads that block instruction retirement from the ROB (called blocking) and loads that do not (called non-blocking). §7 discusses our evaluation methodology. The distribution of ROB-blocking and non-blocking load requests (on the left y-axis), and LLC misses per kilo instructions (on the right y-axis) in the absence and presence of a state-of-the-art hardware data prefetcher [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF].

We make two key observations from Fig. 2. First, on average, Pythia accurately prefetches nearly half of all o -chip load requests in the no-prefetching system, thereby improving the overall performance (not shown here; see §8.2.1). Second, the remaining half of the o -chip loads are not prefetched even by a sophisticated prefetcher like Pythia. 71.4% of these nonprefetched o -chip loads block instruction retirement from the ROB, signi cantly limiting performance. We conclude that, state-of-the-art prefetchers, while e ective at improving performance, still leave a signi cant performance improvement opportunity on the table.

An increasing fraction of o -chip load latency is spent accessing the on-chip cache hierarchy. We observe that the on-chip cache hierarchy has not only grown tremendously in size but also in design complexity (e.g., sliced last-level cache organization [START_REF] Beckmann | Managing Wire Delay in Large Chip-Multiprocessor Caches[END_REF][START_REF] Hardavellas | Reactive NUCA: Near-Optimal Block Placement and Replication in Distributed Caches[END_REF][START_REF] Kim | An Adaptive, Non-Uniform Cache Structure for Wire-Delay Dominated On-Chip Caches[END_REF]) in recent processors, in order to cater to workloads with large data footprints. A larger on-chip cache hierarchy, on the one hand, improves a core's performance by preventing more load requests from going ochip. On the other hand, all on-chip caches need to be accessed to determine if a load request should be sent o -chip. As a result, on-chip cache access latency signi cantly contributes to the total latency of an o -chip load. With increasing on-chip cache sizes, and the complexity of the cache hierarchy design and the on-chip network [START_REF] Besta | Slim NoC: A Low-diameter On-chip Network Topology for High Energy Efciency and Scalability[END_REF][START_REF] Wang | Stream Floating: Enabling Proactive and Decentralized Cache Optimizations[END_REF], the on-chip cache access latency is increasing in processors [START_REF]Intel Core i5-12600K DDR4 Alder Lake CPU Review[END_REF][START_REF]L3 Cache Latency Comparison at Base Frequency[END_REF]. An analysis of the Intel Alder Lake core suggests that the load-to-use latency of an LLC access has increased to 14 ns (which is equivalent to 55 cycles for a core running at 4 GHz) [START_REF]Intel Core i5-12600K DDR4 Alder Lake CPU Review[END_REF][START_REF]Surprisingly High Latency Discovered in Alder Lake[END_REF][START_REF]The Intel 12th Gen Core i9-12900K Review[END_REF].

To demonstrate the e ect of long on-chip cache access la-tency on the total latency of an o -chip load, Fig. 3 plots the average number of cycles a core stalls due to an o -chip load blocking any instruction from retiring from the ROB, averaged across each workload category in our baseline system with Pythia. Each bar further shows the average number of cycles an o -chip load spends for accessing the on-chip cache hierarchy. Our simulation con guration faithfully models an Intel Alder Lake performance-core with a large ROB, large on-chip caches and publicly-reported cache access latencies (see §7). As Fig. 3 shows, an o -chip load stalls the core for an average of 147.1 cycles. 40.1% of these stall cycles (i.e., 58.9 cycles) can be completely eliminated by removing the on-chip cache access latency from the o -chip load's critical path. We conclude that a large and complex on-chip cache hierarchy is directly responsible for a large fraction of the overall stall cycles caused by an o -chip load request. We envision that this problem will only get exacerbated with new processor designs as on-chip caches continue to grow in size and complexity [START_REF]L3 Cache Latency Comparison at Base Frequency[END_REF].

Our Goal and Key Idea

Our goal is to improve processor performance by removing the on-chip cache access latency from the critical path of ochip load requests.

The Key Idea and Potential Bene ts

To this end, we propose a new technique called Hermes, whose key idea is to predict which load requests might go o -chip and start fetching their corresponding data directly from the main memory, while also concurrently accessing the cache hierarchy for such a load. To understand the potential performance bene ts of Hermes, we model an Ideal Hermes system in simulation where we reduce the main memory access latency of every o -chip load request by the post-L1 on-chip cache hierarchy access latency (which includes L2 and LLC access, and interconnect latency). In other words, in the Ideal Hermes system, we (1) magically and perfectly know if a load request would go o -chip after its physical address is available (i.e., after the translation lookaside bu er access, which happens in parallel with the L1 data cache access in modern processors [START_REF] Basu | Reducing Memory Reference Energy with Opportunistic Virtual Caching[END_REF][START_REF] Cekleov | Virtual-Address Caches. Part 1: Problems and Solutions in Uniprocessors[END_REF][START_REF] Patterson | Computer Organization and Design: The Hardware Software Interface[END_REF][START_REF] Wood | An In-Cache Address Translation Mechanism[END_REF]), and (2) directly access the o -chip main memory for such a load, eliminating the non-L1-cache related on-chip cache hierarchy access latency from such a load's total latency. Fig. 4(a) shows the speedup of Ideal Hermes by itself and when combined with Pythia normalized to the no-prefetching system in single-core workloads. We make two key observations from Fig. 4(a). First, Ideal Hermes combined with Pythia outperforms Pythia alone by 8.3% on average across all workloads. Second, Ideal Hermes by itself provides nearly 80% of the performance improvement that Pythia provides. Fig. 4(b) shows the speedup of Ideal Hermes when combined with four other recently-proposed high-performance prefetchers: Bingo [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF], SPP [START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF] (with perceptron lter [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF]), MLOP [START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF], and SMS [START_REF] Somogyi | Spatial Memory Streaming[END_REF]. Ideal Hermes improves performance by 9.4%, 8.2%, 10.9%, and 13.3% on top of four state-of-the-art prefetchers Bingo, SPP, MLOP, and SMS, respectively. Based on these results, we conclude that Hermes has high potential performance bene t not only when implemented alone but also when combined with a wide variety of high-performance prefetchers. Ideal Hermes when combined with four recently-proposed prefetchers: Bingo [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF], SPP [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF][START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF], MLOP [START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF], and SMS [START_REF] Somogyi | Spatial Memory Streaming[END_REF].

Key Challenge

Even though Hermes has a signi cant potential to improve performance, Hermes's performance gain heavily depends on the accuracy (i.e., the fraction of predicted o -chip loads that actually go o -chip) and the coverage (i.e., the fraction of ochip loads that are successfully predicted) of the o -chip load prediction. A low-accuracy o -chip load predictor generates useless main memory requests, which incur both latency and bandwidth overheads, and causes interference to the useful requests in the main memory. A low-coverage predictor loses opportunity to improve performance. We identify two key challenges in designing an o -chip load predictor with high accuracy and high coverage. First, only a small fraction of the total loads generated by a workload goes o -chip in presence of a sophisticated data prefetcher. As shown in Figure 5, on average 7.9 loads per kilo instructions miss the LLC and go o -chip in our baseline system with Pythia.

However, these loads constitute only 5.1% of the total loads generated by a workload. This small fraction of o -chip loads makes it di cult for an o -chip load predictor to accurately learn from the workload behavior to produce highly-accurate predictions. Second, the o -chip predictability of a workload can change in the presence of modern sophisticated data prefetchers. This is because in the presence of a sophisticated prefetcher, the likelihood of a load request going o -chip not only depends on the program behavior but also on the prefetcher's ability to successfully prefetch for the load.

In this work, we overcome these two key challenges by designing a new o -chip load prediction technique, called POPET, based on perceptron learning [START_REF] Jiménez | Neural Methods for Dynamic Branch Prediction[END_REF][START_REF] Mcculloch | A Logical Calculus of the Ideas Immanent in Nervous Activity[END_REF][START_REF] Rosenblatt | The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain[END_REF]. By learning to identify o -chip loads using multiple program features (e.g., sequence of program counters, byte o set of a load request, page number of the load address), POPET provides both higher accuracy and coverage than a prior cache hit-miss prediction technique [START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF] and higher accuracy than another o -chip load prediction technique that we develop (see §7.2), in the presence of modern sophisticated prefetchers, without requiring large metadata storage overhead. With small changes to the existing on-chip datapath design, we demonstrate that Hermes with POPET signi cantly outperforms the baseline system with a state-of-the-art prefetcher across a wide range of workloads and system con gurations.

Key Related Works

The key idea of load hit-miss prediction (HMP) was proposed in [START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF] and demonstrated as a method to improve the instruction scheduler e ciency and performance. By predicting which load instructions will miss the L1 data cache, 3 HMP enables the instruction scheduler to delay the scheduling of dependent instructions until the data is fetched. This scheduler optimization improves processor performance by scheduling a load-dependent instruction to execute at the time when the data in available. Even though Hermes leverages o -chip load prediction in a very di erent way than HMP, we compare the accuracy and coverage of our perceptron-based o -chip load predictor POPET, against those of HMP in §8.1.1 and show that Hermes with POPET greatly outperforms Hermes with HMP in §8.2.2.

Cache-level hit/miss prediction (i.e., predicting which cache level a load might hit) has also been explored in three works: Direct-to-Data cache (D2D [START_REF] Sembrant | The Direct-to-Data (D2D) Cache: Navigating the Cache Hierarchy with a Single Lookup[END_REF]), Direct-to-Master cache (D2M [START_REF] Sembrant | A Split Cache Hierarchy for Enabling Data-Oriented Optimizations[END_REF]), and Level Prediction (LP [START_REF] Jalili | Reducing Load Latency with Cache Level Prediction[END_REF]). All three works employ di erent mechanisms to track cacheline addresses present in the cache hierarchy along with the cache-level(s) a cacheline is present in. For a given load, these works predict which cache-level the load would likely hit. If the cache-level hit/miss prediction is correct, the processor fetches the data of the correctly-predicted load by only accessing the predicted memory level (L1, L2, LLC, or the main memory) and bypassing all other memory levels. By doing so, a cache-level hit/miss predictor reduces the latency of a correctly-predicted load and improves the processor's energy e ciency. However, if the predictor incorrectly bypasses a memory level that has more up to date data (e.g., if the data is present in L2, but the predictor suggests fetching the data from LLC), the processor needs to detect such mispredictions and access the correct memory level to maintain correct execution, which comes with performance overhead and additional complexity. Hermes di ers from all these prior works in three major ways:

Prediction via tracking addresses vs. learning from program context. To make accurate cache-level prediction, D2D, D2M, and LP rely on tracking cacheline addresses present in the on-chip caches by using e ciently-managed metadata structures. For example, D2D and D2M extend each translation look-aside bu er (TLB) entry (called eTLB) to keep additional cache-level-related metadata. LP manages the cache-level metadata as an in-memory table and caches the metadata on-chip using a metadata prefetching mechanism. These metadata structures need to be updated for almost all cache operations (e.g., cache insertions, evictions) in order to faithfully track the cache contents and to provide accurate cache-level predictions. In contrast, POPET is built on the insight that the correlation between di erent types of program context information and o -chip loads can be accurately learned without tracking cache contents. As a result, POPET does not explicitly track addresses present in the cache hierarchy, but learns to predict o -chip loads by aggregating various program context information.

Lower complexity and hardware overhead. To enable accurate cache-level hit/miss prediction and to recover from a misprediction, prior works need relatively intrusive changes to multiple components on the on-chip datapath. Both D2D and D2M cache designs require extending the TLB and operating system support to store the way and cache-level information for every cacheline within the reach of eTLB. LP requires 2-bit metadata for every 64B chunk of the physical main memory. LP manages this metadata as an in-memory table in the systemreserved physical main memory space [START_REF] Jalili | Reducing Load Latency with Cache Level Prediction[END_REF], which necessitates support from the operating system. In the worst case, to make a cache-level hit/miss prediction, LP needs to fetch the metadata from main memory, which can take longer than the cache lookup LP is designed to avoid. In contrast, POPET incurs a very modest (4 KB) total storage overhead and small changes to the existing datapath.

No misprediction detection and recovery. LP requires cache level misprediction detection and recovery to prevent the program from using any stale, incoherent data from the memory subsystem. On the other hand, Hermes never brings any data to the on-chip cache hierarchy unless the data is required by a LLC miss request (see §6.2.2). Hence, Hermes does not require any misprediction detection and recovery mechanism to maintain correct execution.

We design an address tag-tracking based o -chip load predictor (called TTP; see §7.2) inspired by these prior works [START_REF] Jalili | Reducing Load Latency with Cache Level Prediction[END_REF][START_REF] Loh | E ciently Enabling Conventional Block Sizes for Very Large Die-Stacked DRAM Caches[END_REF][START_REF] Sembrant | The Direct-to-Data (D2D) Cache: Navigating the Cache Hierarchy with a Single Lookup[END_REF] and evaluate it against POPET (see §8). TTP tracks address tags present in the entire cache hierarchy in its metadata structure (see §7.2) and predicts that a load would go o -chip if the tag of the load address is not present in its metadata structure. We open-source the implementation of TTP in our repository [START_REF]Hermes GitHub repository[END_REF]. Our results show that POPET provides both higher accuracy and higher performance than TTP (see §8.1.1 and §8.2.1).

Hermes: Design Overview

Fig. 6 shows a high-level overview of Hermes. POPET is the key component of Hermes that is responsible for making highlyaccurate o -chip load predictions. For every demand load request generated by the processor, POPET predicts whether or not the load request would go o -chip [START_REF]2nd Cache Replacement Championship[END_REF]. If the load is predicted to go o -chip, Hermes issues a speculative memory request (called a Hermes request) directly to the main memory controller once the load's physical address is generated to start fetching the corresponding data from the main memory ( 2 ). This Hermes request is serviced by the main memory controller concurrently with the regular load request (i.e., the load issued by the processor that generated the Hermes request) that accesses the on-chip cache hierarchy. If the prediction is correct, the regular load request to the same address eventually misses the LLC and waits for the ongoing Hermes request to nish, thereby completely hiding the on-chip cache hierarchy access latency from the critical path of the correctly-predicted o -chip load ( 3 ). If a Hermes request returns from the main memory but there has been no regular load request to the same address, Hermes drops the request and does not ll the data into the cache hierarchy. By doing so, Hermes keeps the on-chip cache hierarchy fully coherent even in case of a misprediction. For every regular load request returning to the core, Hermes trains POPET based on whether or not this load has actually gone o -chip ( 4 ).

Hermes: Detailed Design

We rst describe the design of POPET in §6.1, followed by the changes introduced by Hermes to the on-chip cache access datapath in §6.2.

POPET Design

The purpose of POPET is to accurately predict whether or not a load request generated by the processor will go o -chip. We design POPET using the multi-feature perceptron learning mechanism [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF][START_REF] Garza | Bit-level Perceptron Prediction for Indirect Branches[END_REF][START_REF] Jimenez | Dynamic Branch Prediction with Perceptrons[END_REF][START_REF] Jiménez | Fast Path-Based Neural Branch Prediction[END_REF][START_REF] Jiménez | Neural Methods for Dynamic Branch Prediction[END_REF][START_REF] Jiménez | Multiperspective Reuse Prediction[END_REF][START_REF] Rosenblatt | The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain[END_REF][START_REF] Teran | Perceptron Learning for Reuse Prediction[END_REF]. What is perceptron learning? Perceptron learning, whose roots are in [START_REF] Mcculloch | A Logical Calculus of the Ideas Immanent in Nervous Activity[END_REF] and was demonstrated by Rosenblatt [START_REF] Rosenblatt | The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain[END_REF], is a simpli ed learning model to mimic biological neurons. Fig. 7 shows a single-layer perceptron network where each input is connected to the output via an arti cial neuron. Each arti cial neuron is represented by a numeric value, called weight. The perceptron network as a whole iteratively learns a binary classi cation function f (x) (shown in Eq. 1), a function that maps the input X (a vector of n values) to a binary output.

f (x) = 1 if w 0 + n i=1 w i x i > 0 0 otherwise (1)
The perceptron learning algorithm starts by initializing the weight of each neuron and iteratively trains the weights using each input vector from the training dataset in two steps. First, for an input vector X, the perceptron network computes a binary output using Eq. 1 and the current weight values of its neurons. Second, if the computed output di ers from the desired output for that input vector provided by the dataset, the weight of each neuron is updated [START_REF] Rosenblatt | The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain[END_REF]. This iterative process is repeated until the error between the computed and desired output falls below a user-speci ed threshold. Jimenez et al. [START_REF] Jiménez | Neural Methods for Dynamic Branch Prediction[END_REF] have applied the perceptron learning algorithm to design a lightweight, high-performance branch predictor in a processor core. Today, multiple commercial processors also use perceptron learning for making various microarchitectural predictions (e.g., Samsung Exynos [START_REF] Grayson | Evolution of the Samsung Exynos CPU Microarchitecture[END_REF], and AMD Ryzen [START_REF]AMD Gives More Zen Details: Ryzen[END_REF]).

We design POPET using an existing microarchitectural perceptron model, known as the hashed perceptron [START_REF] Tarjan | Merging Path and Gshare Indexing in Perceptron Branch Prediction[END_REF]. A hashed perceptron model hashes multiple feature values to retrieve weights of each feature from small tables. If the sum of these weights exceeds a threshold, the model makes a positive prediction. Hashed perceptron, as compared to other perceptron models, is lightweight and easy to implement in hardware. Prior works successfully apply hashed perceptron for various microarchitectural predictions, e.g., branch outcome [START_REF] Garza | Bit-level Perceptron Prediction for Indirect Branches[END_REF][START_REF] Jiménez | Fast Path-Based Neural Branch Prediction[END_REF][START_REF] Jiménez | Neural Methods for Dynamic Branch Prediction[END_REF], LLC reuse [START_REF] Jiménez | Multiperspective Reuse Prediction[END_REF][START_REF] Teran | Perceptron Learning for Reuse Prediction[END_REF], prefetch usefulness [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF]. This is the rst work that applies hashed perceptron to o -chip load prediction.

Why perceptron? We choose to design POPET based on perceptron learning for two key reasons. First, by learning using multiple program features, perceptron learning can provide highly accurate predictions that could not be otherwise provided by simple history-based learning prediction (e.g., HMP [START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF], described in §4). Second, perceptron learning can be implemented with low storage overhead, without requiring any impractical metadata support (e.g., extending TLB [START_REF] Sembrant | The Direct-to-Data (D2D) Cache: Navigating the Cache Hierarchy with a Single Lookup[END_REF][START_REF] Sembrant | A Split Cache Hierarchy for Enabling Data-Oriented Optimizations[END_REF] or in-memory metadata storage [START_REF] Jalili | Reducing Load Latency with Cache Level Prediction[END_REF], described in §4).

POPET overview. POPET is organized as a collection of one-dimensional tables (each called a weight table ), where each table corresponds to a single program feature. Each table entry stores a weight value, implemented using a 5-bit saturating signed integer, that represents the correlation between the corresponding program feature value and the true outcome (i.e., whether a given load actually went o -chip). A weight value saturated near the maximum (i.e., +15) or the minimum (i.e., -16) value represents a strong positive or negative correlation between the program feature value and the true outcome, respectively. A weight value closer to zero signi es a weak correlation. The weights are adjusted during training (step 4 in Fig. 6) to update POPET's prediction with the true outcome. Each weight table is sized di erently based on its corresponding program feature (see Table 3).

6.1.1. Making a Prediction. During load queue (LQ) allocation for a load generated by the core (step 1 in Fig. 6), POPET makes a binary prediction on whether or not the load request would go o -chip. The prediction happens in three stages as shown in Fig. 8. In the rst stage, POPET extracts a set of program features from the current load request and a history of prior requests ( §6.1.3 shows the list of program features used by POPET). In the second stage, each feature value is hashed and used as an index to retrieve a weight value from the weight table of the corresponding feature. In the third stage, all weight values from individual features are accumulated to generate the cumulative perceptron weight (W σ ). If W σ exceeds a predened threshold (called the activation threshold, τ act ), POPET makes a positive prediction (i.e., it predicts that the current load request would go o -chip). Otherwise, POPET makes a negative prediction. The hashed feature values, the cumulative perceptron weight W σ , and the predicted outcome are stored in the LQ entry to be reused to train POPET when the load request returns to the processor core (step 4 in Fig. 6). list of feature sets, each containing n features, at every iteration n in the following way. In the rst iteration, we design POPET with each of the 16 initial program features and test its prediction accuracy in 10 randomly-selected workload traces (called testing workloads). We select the top-10 features that produce the highest prediction accuracy for the second iteration. In the second iteration, we create 160 two-combination feature sets (meaning, each feature set contains two initial features from Table 1) by combining each of the 16 initial features with each of the 10 winning feature sets from the last iteration, and test the prediction accuracy on the testing workloads. We select the top-10 two-combination feature sets that produce the highest prediction accuracy for the third iteration. This iterative process repeats until the maximum prediction accuracy gets saturated (i.e., the di erence in accuracy of two successive iterations is less than 3%). 4 Table 2 shows the nal list of program features selected by the automated feature selection process. Rationale for selected features. Each selected feature correlates with the likelihood of observing an o -chip load request with a di erent program context information. We explain the rationale for each selected feature below.

(1) PC ⊕ cacheline o set. This feature is computed by XOR-ing the load PC value with the cacheline o set of the load address in the virtual page of the load request. The goal of this feature is to learn the likelihood of a load request going o -chip when a given load PC touches a certain cacheline o set in a virtual page. The use of cacheline o set information, instead of load virtual address or virtual page number, enables this feature to apply the learning across di erent virtual pages.

(2) PC ⊕ cacheline byte o set. This feature is computed by XOR-ing the load PC with the byte o set of the load cacheline address. This feature is particularly useful in accurately predicting o -chip load requests when a program has a streaming access pattern over a linearly allocated data structure. For example, when a program streams through a large array of 4B integers, every 16 th load (as a 64B cacheline stores 16 integers) generated by a load PC that is iterating over the array will go o -chip, and the remaining loads will hit in on-chip caches. In this case, this feature learns to identify only those loads that have a byte o set of 0 to go o -chip.

(3) PC + rst access. This feature is computed by leftshifting the load PC and adding the rst access hint at the most-signi cant bit position. The rst access hint is a binary value that represents whether or not a cacheline has been recently touched by the program. The hint is computed using a small 64-entry bu er (called the page bu er) that tracks the demanded cachelines from last 64 virtual pages. Each page bu er entry holds two pieces of information: a virtual page tag, and a 64-bit bitmap, where each bit represents one cacheline in the virtual page. During every load request generation, POPET searches the page bu er with the virtual page number of the load address. If a matching entry is found, POPET uses the value of the bit corresponding to the cacheline o set in the matching page bu er entry's bitmap as the rst access hint. If the bit is set (or unset), it signi es that the corresponding cacheline has (not) been recently accessed by the program. If the bit is unset, POPET sets the bit in the page bu er entry's bitmap. The rst access hint provides a crude estimate of a cacheline's reuse in a short temporal window. However, it alone cannot determine the cacheline's residency in on-chip caches, as the memory footprint tracked by the page bu er is much smaller than the total cache size.

(4) Cacheline o set + rst access. This feature is similar to the PC + rst access feature, except that it learns the likelihood of a load request going o -chip when a given cacheline o set is recently touched by the program.

(5) Last-4 load PCs. This feature value is computed as a shifted-XOR of last four load PCs. It represents the execution path of a program and correlates it with the likelihood of observing an o -chip load request whenever the program follows the same execution path.

6.1.4. Parameter Threshold Tuning. POPET has three tunable parameters: negative and positive training thresholds (T N and T P , respectively), and the activation threshold (τ act ). Properly tuning the values of all these three parameters is also critical to POPET's performance, since both POPET's accuracy and coverage are sensitive to parameter values.

We employ a three-step grid search technique to tune each of the three parameters separately. In the rst stage, we uniformly sample values from a parameter's range. For example, τ act can take values in the range [-80, 75]. 5 We uniformly sample values from this range with a grid size of 5. In the second stage, we run Hermes with the randomly-selected 10 test workloads (as mentioned in §6.1.3) for each of the sampled values and pick the top-10 values that provide the highest performance gain. In the third stage, we run Hermes with all single-core workload traces using the selected 10 parameter values from the second stage. We nally select the value that provides the highest average performance gain. Table 2 shows the selected threshold values of each parameter.

Hermes Datapath Design

In this section, we describe the key changes introduced to the existing well-optimized on-chip cache access datapath to incorporate Hermes. First, we show how the core issues a Hermes request directly to the main memory controller if POPET predicts the load would go o -chip and how a regular load request that misses the LLC waits for an ongoing Hermes request (see § 6.2.1). Second, we discuss how the data fetched from main memory is properly sent back to the core in presence of Hermes while maintaining cache coherence (see §6.2.2).

Issuing a Hermes Request.

For every load request predicted to go o -chip, Hermes issues a Hermes request directly to the main memory controller (step 2 in Fig. 6) once the load's physical address is generated. The main memory controller enqueues the Hermes request in its read queue (RQ) and starts fetching the corresponding data from the main memory as dictated by its scheduling policy, while the regular load request is concurrently accessing the on-chip cache hierarchy. If the o -chip prediction is correct, the regular load request eventually misses the LLC and checks the main memory controller's RQ for any ongoing main memory access to the same load address (step 3 ). If the address is found, the regular load request waits for the ongoing Hermes request to nish before sending the Hermes-fetched data back to the core.

Hermes's performance gain depends on the latency to directly issue a Hermes request to the main memory controller (called Hermes request issue latency). Although a Hermes request experiences a signi cantly shorter latency to arrive at the main memory controller than its corresponding regular load request because a Hermes request bypasses the cache hierarchy and on-chip queueing delays, a Hermes request nonetheless pays for a latency to route through the on-chip network. We model two variants of Hermes using an optimistic and a pessimistic estimate of Hermes request issue latency to take into account a wide range of potential di erences in on-chip interconnect designs (see §7.2). In §8.4.3, we also evaluate Hermes with a wide range of Hermes request issue latencies (from 0 cycle to 24 cycles) and show that Hermes consistently provides performance bene t even with the most pessimistic Hermes request issue latency. 6.2.2. Returning Data to the Core. For every Hermes request returning from main memory, Hermes checks the RQ of the main memory controller and returns the fetched data back to the LLC if there is a regular load request already waiting for the same load address. If there is no regular load request waiting for the completed Hermes request, Hermes drops the request and does not ll the data into the cache hierarchy, which keeps the on-chip cache hierarchy internally coherent.

Storage Overhead

Table 3 shows the total storage overhead of Hermes. Hermes requires only 4 KB of metadata storage per processor core. POPET consumes 3.2 KB, whereas the metadata stored in LQ for POPET training consumes 0.8 KB.

Methodology

We use the ChampSim trace-driven simulator [START_REF]ChampSim[END_REF] to evaluate Hermes. We faithfully model the latest-generation Intel Alder Lake performance-core [START_REF]Golden Cove Microarchitecture (P-Core) Examined[END_REF] with its large ROB, large caches with publicly-reported on-chip cache access latencies [START_REF]L3 Cache Latency Comparison at Base Frequency[END_REF][START_REF]Surprisingly High Latency Discovered in Alder Lake[END_REF][START_REF]The Intel 12th Gen Core i9-12900K Review[END_REF], and the state-of-the-art prefetcher Pythia [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF] at the LLC. Table 4 shows the key microarchitectural parameters. For single-core simulations, we warm up the core using 100M instructions and simulate the next 500M instructions. For multiprogrammed simulations, we use 50M and 100M instructions from each workload for warmup and simulation, respectively. If a core nishes early, the workload is replayed until every core has nished executing at least 100M instructions. The source code of Hermes, along with all workload traces and scripts to reproduce our results are freely available at [START_REF]Hermes GitHub repository[END_REF].

Workloads

We evaluate Hermes using a wide range of memory-intensive workloads spanning SPEC CPU2006 [START_REF]SPEC CPU[END_REF], SPEC CPU2017 [START_REF]SPEC CPU[END_REF], PARSEC [START_REF]PARSEC[END_REF], Ligra graph processing workload suite [START_REF] Shun | Ligra: A Lightweight Graph Processing Framework for Shared Memory[END_REF], and commercial workloads from the 2nd data value prediction championship (CVP [START_REF]Second Championship Value Prediction (CVP-2)[END_REF]). For SPEC CPU2006 and SPEC CPU2017 workloads, we reuse the instruction traces provided by the 2nd and the 3rd data prefetching championships (DPC [START_REF]2nd Data Prefetching Championship[END_REF][START_REF]3rd Data Prefetching Championship[END_REF]). For PARSEC and Ligra workloads, we reuse the instruction traces open-sourced by Pythia [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF]. The CVP workload traces are collected by the Qualcomm Datacenter Technologies and capture complex program behavior from various integer, oating-point, cryptographic, and server applications in the eld. We only consider workload traces in our evaluation that have at least 3 LLC misses per kilo instructions (MPKI) in the no-prefetching system. In total, we evaluate Hermes using 110 single-core workload traces from 73 workloads, which are summarized in Table 5. All these traces can be freely downloaded using a script as mentioned in Appendix A.5. For multiprogrammed simulations, we create both homogeneous and heterogeneous trace mixes. For an eight-core homogeneous multi-programmed simulation, we run eight copies of each trace from our single-core trace list, one trace in each core. For heterogeneous multi-programmed simulation, we randomly select any eight traces from our single-core trace list and run one trace in each core. In total, we evaluate Hermes using 110 homogeneous and 110 heterogeneous eight-core workloads.

Evaluated System Con gurations

For a comprehensive analysis, we compare Hermes with various o -chip load prediction mechanisms, as well as in combination with various recently proposed prefetchers. Table 6 compares the storage overhead of all evaluated mechanisms.

(1) Various o -chip prediction mechanisms. We compare POPET against two cache hit/miss prediction techniques: (1) HMP, proposed by Yoaz et al. [START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF], and (2) a simple cacheline tag-tracking based predictor, called TTP, which we design. HMP uses three predictors similar to a hybrid branch predictor: local [START_REF] Yeh | Two-level Adaptive Training Branch Prediction[END_REF], gshare [START_REF] Mcfarling | Combining Branch Predictors[END_REF][START_REF] Yeh | Two-level Adaptive Training Branch Prediction[END_REF], and gskew [START_REF] Michaud | Trading Con ict and Capacity Aliasing in Conditional Branch Predictors[END_REF], each of which individually predicts o -chip loads using a di erent prediction mechanism. For a given load, HMP consults each individual predictor and selects the majority prediction. We design TTP by taking inspiration from prior cacheline address trackingbased mechanisms [START_REF] Jalili | Reducing Load Latency with Cache Level Prediction[END_REF][START_REF] Loh | E ciently Enabling Conventional Block Sizes for Very Large Die-Stacked DRAM Caches[END_REF][START_REF] Sembrant | The Direct-to-Data (D2D) Cache: Navigating the Cache Hierarchy with a Single Lookup[END_REF] (see §4). TTP tracks partial tags of cacheline addresses that are likely to be present in the entire on-chip cache hierarchy in a separate metadata structure. For every cache ll (LLC eviction), the partial tag of the lled (evicted) cacheline address is inserted into (evicted from) TTP's metadata. To predict whether or not a given load would go o -chip, TTP searches the metadata structure with the partial tag of the load address. If the tag is not present in the metadata structure, TTP predicts the load would go o -chip. We open-source TTP in our repository [START_REF]Hermes GitHub repository[END_REF].

(2) Various data prefetchers. We evaluate Hermes combined with ve recently-proposed high-performance prefetch-ing techniques: Pythia [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF], Bingo [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF], SPP [START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF] (with perceptron lter [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF]), MLOP [START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF], and SMS [START_REF] Somogyi | Spatial Memory Streaming[END_REF]. As mentioned in Table 4, Pythia is incorporated in our baseline system. Pythia [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF] with the same con guration in [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF] 25.5 KB Bingo [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF] with the same con guration in [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF] 46 KB SPP [START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF] with perceptron-based prefetch lter [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF] 39.3 KB MLOP [START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF] with the same con guration in [START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF] 8 KB SMS [START_REF] Somogyi | Spatial Memory Streaming[END_REF] with the same con guration in [START_REF] Somogyi | Spatial Memory Streaming[END_REF] 20 KB

Hermes with POPET (this work)

KB

We evaluate two variants of Hermes: Hermes-O and Hermes-P. These two variants di er only in Hermes request issue latency. Hermes-O (i.e., the optimistic Hermes) and Hermes-P (i.e., the pessimistic Hermes) use a request issue latency of 6 cycles and 18 cycles, respectively. Unless stated otherwise, Hermes represents the optimistic variant Hermes-O. 9 shows the comparison of POPET's o -chip load prediction accuracy and coverage against those of HMP and TTP in the baseline system. The key takeaway is that POPET has signi cantly higher accuracy and coverage than HMP. POPET provides 77.1% accuracy with 74.3% coverage on average across all single-core workloads, whereas HMP provides 47% accuracy with 22.3% coverage. TTP, with a metadata budget of 1.5 MB, provides the highest coverage (94.8%) but with a signi cantly lower accuracy (16.6%). POPET's superior accuracy and coverage directly translates to performance bene ts both in single-core and eight-core system con guration (see §8.2 and §8.3). 8.1.2. E ect of Di erent POPET Features. Fig. 10 shows the accuracy and coverage of POPET using the ve selected program features used individually and in various combinations. We make two key observations. First, each program feature individually produces predictions with a wide range of accuracy and coverage. The PC ⊕ cacheline o set feature produces the lowest-quality predictions with only 53.4% accuracy and 14.5% coverage, whereas the cacheline o set + rst access feature produces the highest-quality predictions with 70.6% accuracy and 48.1% coverage. Second, by stacking multiple features together, the nal POPET design achieves both higher accuracy and coverage than those provided by any single individual program feature. We conclude that POPET is capable of learning from multiple program features to achieve both higher o -chip load prediction accuracy and coverage than any individual program feature can provide. , where no single program feature individually provides the highest coverage across all workloads. This large variability of accuracy/coverage with di erent features in di erent workloads warrants learning using all features in unison to provide higher accuracy and coverage than any individual program feature across a wide range of workloads. 8.2. Single-core Performance Analysis 8.2.1. Performance Improvement. Fig. 12 shows performance of Hermes (O and P), Pythia, and Hermes combined with Pythia normalized to the no-prefetching system in single-core workloads. We make three key observations. First, Hermes provides nearly half of the performance bene t of Pythia with only 1 5 × the storage overhead. On average, Hermes-O improves performance by 11.5% over a no-prefetching system, whereas Pythia improves performance by 20.3%. Second, Hermes-O (Hermes-P) combined with Pythia outperforms Pythia by 5.4% (4.3%). Third, Hermes combined with Pythia consistently outperforms Pythia in every workload category. To better understand Hermes's performance improvement, Fig. 13 shows the performance line graph of Hermes, Pythia, and Hermes combined with Pythia for every single-core workload trace. The traces are sorted in ascending order of performance gains by Hermes combined with Pythia over the no-prefetching system. We make four key observations from Fig. 13. First, Hermes combined with Pythia outperforms the no-prefetching system in all but three single-core workload traces. The compute _ int _ 539 and 605.mcf _ s-782B traces experience the highest and the lowest speedup (2.3× and 0.8×, respectively). Second, unlike Pythia, Hermes always improves performance over the no-prefetching system in every workload trace. Third, Hermes outperforms Pythia by 7.9% on average in 51 traces (e.g., streamcluster-6B, Ligra _ PageRank-79B).

Evaluation

In the remaining 59 traces, Pythia outperforms Hermes by 26% on average. Fourth, Hermes combined with Pythia consistently outperforms both Hermes and Pythia alone in almost every workload trace.

Based on our performance results, we conclude that, Hermes provides signi cant and consistent performance improvements over a wide range of workloads both by itself and when combined with the state-of-the-art prefetcher Pythia. 14 shows the performance of Hermes with POPET, Hermes-HMP, Hermes-TTP, and the Ideal Hermes (see §3.1) combined with Pythia normalized to the no-prefetching system in singlecore workloads. We make two key observations. First, Hermes with POPET outperforms both Hermes-HMP and Hermes-TTP. On average, Hermes-HMP, Hermes-TTP, and Hermes with POPET combined with Pythia provide 0.8%, 1.7%, and 5.4% performance improvement over Pythia, respectively. Second, Hermes-POPET provides nearly 90% of the performance improvement provided by the Ideal Hermes that employs an ideal o -chip load predictor with 100% accuracy and coverage. We conclude that Hermes provides performance gains due to both the high o -chip load prediction accuracy and coverage of POPET. Thus, designing a good o -chip predictor is critical for Hermes to improve performance. 8.2.3. E ect on Stall Cycles. Fig. 15(a) plots the distribution of the percentage reduction in stall cycles due to o -chip load requests in a system with Hermes over the baseline system in single-core workloads as a box-and-whiskers plot. 6 The key observation is that Hermes reduces the stall cycles caused by o -chip loads by 16.2% on average (up to 51.8%) across all workloads. PARSEC workloads experience the highest average stall cycle reduction of 23.8%. 90 out of 110 workloads experience at least 10% stall cycle reduction. We conclude that Hermes considerably reduces the stall cycles due to o -chip load requests, which leads to performance improvement. shows the percentage increase in main memory requests in Hermes, Pythia, and Hermes combined with Pythia over the no-prefetching system in all single-core workloads. We make two key observations. First, Hermes increases main memory requests by only 5.5% (on average) over the no-prefetching system, whereas Pythia by 38.5%. This means that, every 1% performance gain (see Fig. 12) comes at a cost of only 0.5% increase in main memory requests in Hermes, whereas nearly 2% increase in main memory requests in Pythia. We attribute this result to the highly-accurate predictions made by POPET, as compared to less-accurate prefetch decisions made by Pythia. Second, Hermes combined with Pythia further increases main memory requests by only 5.9% over Pythia. This means that, every 1% performance bene t by Hermes on top of Pythia comes at a cost of only 1% overhead in main memory requests. We conclude that, Hermes, due to its underlying high-accuracy prediction mechanism, adds considerably lower overhead in main memory requests while providing signi cant performance improvement both by itself and when combined with Pythia.

Eight-core Performance Analysis

Fig. 16 shows the performance of Pythia, Hermes-HMP, Hermes-TTP, and Hermes-POPET combined with Pythia normalized to the no-prefetching system in all eight-core workloads. The key takeaway is that due to the highly-accurate predictions by POPET, Hermes-POPET combined with Pythia consistently outperforms Pythia in every workload category. On average, Hermes-HMP, Hermes-TTP, and Hermes-POPET combined with Pythia provide 0.6%, -2.1%, and 5.1% higher performance on top of Pythia, respectively. Due to its inaccurate predictions, TTP generates many unnecessary main memory requests, which reduce the performance of Hermes-TTP combined with Pythia as compared to Pythia alone in the bandwidth-constrained four-core con guration. We conclude that Hermes provides signi cant and consistent performance improvement in the bandwidth-constrained eight-core system due to its highly-accurate o -chip load prediction. Pythia over the no-prefetching system in single-core workloads by scaling the main memory bandwidth. We make two key observations. First, Hermes combined with Pythia consistently outperforms Pythia in every main memory bandwidth con guration from 1 16 × to 4× of the baseline system. Hermes combined with Pythia outperforms Pythia alone by 6.2% and 5.5% in the main memory bandwidth con guration with 200 and 12800 million transfers per second (MTPS), respectively. Second, Hermes by itself outperforms Pythia in highly-bandwidth-constrained con gurations. This is due to the highly-accurate o -chip load predictions made by POPET, which incurs less main memory bandwidth overhead than the aggressive, less-accurate prefetching decisions made by Pythia. Hermes outperforms Pythia by 2.8% and 8.9% in 400 and 200 MTPS con gurations, respectively. 8.4.2. E ect of the Baseline Prefetcher. We evaluate Hermes combined with four recently-proposed data prefetchers: Bingo [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF], SPP [START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF] (with perceptron lter [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF]), MLOP [START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF], and SMS [START_REF] Somogyi | Spatial Memory Streaming[END_REF]. For each experiment, we replace the baseline LLC prefetcher Pythia with a new prefetcher and measure the performance improvement of the prefetcher by itself and Hermes combined with the prefetcher. Fig. 17(b) shows the performance of the baseline prefetcher, and Hermes-P/O combined with the baseline prefetcher, normalized to the no-prefetching system in single-core workloads. The key takeaway is that Hermes combined with any baseline prefetcher consistently outperforms the baseline prefetcher by itself for all four evaluated prefetching techniques. Hermes+prefetcher outperforms the prefetcher alone by 6.2%, 5.1%, 7.6%, and 7.7%, for Bingo, SPP, MLOP, and SMS as the baseline prefetcher.

8.4.3. E ect of the Hermes Request Issue Latency. To analyze the performance bene t of Hermes over a wide range of processor designs with simple or complex on-chip datapath, we perform a performance sensitivity study by varying the Hermes request issue latency. Fig. 17(c) shows the performance of Hermes combined with Pythia normalized to the no-prefetching system in single-core workloads as Hermes request issue latency varies from 0 cycles to 24 cycles. The dashed-line represents the performance of Pythia alone. We make two key observations. First, the speedup of Hermes combined with Pythia decreases as the Hermes request issue latency increases. Second, even with a pessimistic Hermes request issue latency of 24 cycles, Hermes combined with Pythia outperforms Pythia. Pythia+Hermes outperforms Pythia by 5.7% and 3.6% with 0-cycle and 24-cycle Hermes request issue latency, respectively. 8.4.4. E ect of the On-chip Cache Hierarchy Access Latency. We evaluate Hermes by varying the on-chip cache hierarchy access latency. For each experiment, we keep the L1 and L2 cache access latencies unchanged and vary the LLC access la-tency from 25-cycles to 50-cycles, to mimic the access latencies of a wide range of sliced LLC designs with simple or complex on-chip networks. Fig. 17(d) shows the performance of Pythia, and Hermes (O and P) combined with Pythia, normalized to the no-prefetching system in single-core workloads. We make two key observations. First, Hermes combined with Pythia consistently outperforms Pythia for every on-chip cache hierarchy latency. Hermes-O combined with Pythia outperforms Pythia alone by 3.6% and 6.2% in system with 40-cycle and 65-cycle on-chip cache hierarchy access latency, respectively. Second, the performance improvement by Hermes combined with Pythia increases as the on-chip cache hierarchy access latency increases. Thus, we posit that Hermes can provide even higher performance bene t in future processors with longer on-chip cache access latencies. 8.4.5. E ect of the Activation Threshold. We evaluate the impact of the activation threshold (τ act ) on Hermes's performance by varying τ act . Fig. 17 shows POPET's accuracy and coverage (as line graphs on the left y-axis) and the performance of Hermes combined with Pythia over the no-prefetching system (as a bar graph on the right y-axis) across all single-core workloads as τ act varies from -38 to 2. The key takeaway from Fig. 17 is that POPET's accuracy (coverage) increases (decreases) as τ act increases. However, Hermes's performance gain peaks near τ act = -26, which favors higher coverage by trading o accuracy. As POPET's accuracy directly impacts Hermes's main memory request overhead (and hence its performance in bandwidth-constrained con gurations), we set τ act = -18 in POPET. Doing so simultaneously optimizes both POPET's accuracy and coverage.

Power Overhead

To accurately estimate Hermes's dynamic power consumption, we model our single-core con guration in McPAT [START_REF] Li | Mc-PAT: An Integrated Power, Area, and Timing Modeling Framework for Multicore and Manycore Architectures[END_REF] and compute processor power consumption using statistics from performance simulations. Fig. 18 shows the runtime dynamic power consumed by Hermes, Pythia, and Hermes combined with Pythia, normalized to the no-prefetching system for all single-core workloads. We make two key observations. First, Hermes increases processor power consumption by only 3.6% on average over the no-prefetching system, whereas Pythia increases power consumption by 8.7%. Second, Hermes combined with Pythia incurs only 1.5% additional power overhead on top of Pythia. We conclude that Hermes incurs only a modest power overhead and is more e cient than Pythia alone.

Other Related Work

To our knowledge, this is the rst work that proposes (1) a lightweight perceptron-based o -chip load predictor (POPET) that makes accurate predictions without having large metadata overhead, and (2) a mechanism (Hermes) that takes advantage of such a predictor to improve processor performance by eliminating on-chip cache access latency from the critical path of a correctly-predicted o -chip load. We have already quantitatively and qualitatively compared (1) POPET with HMP [START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF] and (2) Hermes with multiple state-of-the-art hardware data prefetchers: Pythia [START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF], Bingo [START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF], SPP [START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF][START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF], MLOP [START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF], and SMS [START_REF] Somogyi | Spatial Memory Streaming[END_REF]. In this section, we discuss other related works.

Hit/miss prediction. Peir et al. [START_REF] Peir | Bloom Filtering Cache Misses for Accurate Data Speculation and Prefetching[END_REF] propose a Bloom-lterbased hit/miss predictor to optimize instruction scheduling in an out-of-order processor. Memik et al. [START_REF] Memik | Just Say No: Bene ts of Early Cache Miss Determination[END_REF] propose ve di erent heuristics to keep track of cache contents using simple tables. Prior works [START_REF] Loh | E ciently Enabling Conventional Block Sizes for Very Large Die-Stacked DRAM Caches[END_REF][START_REF] Qureshi | Fundamental Latency Trade-o in Architecting DRAM Caches: Outperforming Impractical SRAM-Tags with a Simple and Practical Design[END_REF] also explore hit/miss prediction in DRAM caches. Loh and Hill [START_REF] Loh | E ciently Enabling Conventional Block Sizes for Very Large Die-Stacked DRAM Caches[END_REF] propose MissMap, which uses bitvectors to track the residency of cachelines in a large DRAM cache. Adapting MissMap to o -chip load prediction poses two key challenges. First, MissMap can have high falsepositive prediction rate (as discussed in [START_REF] Jalili | Reducing Load Latency with Cache Level Prediction[END_REF]). Second, the size of MissMap can grow very large, leading to large latency and storage overheads. POPET, on the other hand, requires only 4 KB of storage overhead, while producing highly-accurate o -chip load predictions.

Cache bypassing. High-performance cache management policies (e.g., [38, 43, 48, 53, 58, 63, 65-68, 72, 73, 80, 97, 101, 102, 114, 115, 120, 122]) dynamically bypass cache levels during a cache ll operation if the incoming cacheline is not expected to be used by the program in the future. This expectation (i.e., reuse prediction) can be provided by either a hardware-based reuse prediction mechanism [START_REF] Dybdahl | Enhancing Last-Level Cache Performance by Block Bypassing and Early Miss Determination[END_REF][START_REF] Jain | Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement[END_REF][START_REF] Jiménez | Dead Block Replacement and Bypass with a Sampling Predictor[END_REF][START_REF] Jiménez | Multiperspective Reuse Prediction[END_REF][START_REF] Khan | Sampling Dead Block Prediction for Last-Level Caches[END_REF][START_REF] Kharbutli | Counter-Based Cache Replacement and Bypassing Algorithms[END_REF][START_REF] Liu | Cache Bursts: A New Approach for Eliminating Dead Blocks and Increasing Cache E ciency[END_REF][START_REF] Piquet | Exploiting Single-Usage for E ective Memory Management[END_REF][START_REF] Rivers | Reducing Con icts in Direct-Mapped Caches with a Temporality-Based Design[END_REF][START_REF] Rivers | Utilizing Reuse Information in Data Cache Management[END_REF][START_REF] Wong | Modi ed LRU Policies for Improving Second-level Cache Behavior[END_REF] or a software hint [START_REF]Caching of Temporal vs[END_REF][START_REF]MOVNTI -x86 ISA[END_REF][START_REF] Chi | Improving Cache Performance by Selective Cache Bypass[END_REF][START_REF] Tyson | A Modi ed Approach to Data Cache Management[END_REF][START_REF] Tyson | Managing Data Caches using Selective Cache Line Replacement[END_REF], e.g., non-temporal load instructions employed by modern processors [START_REF]Caching of Temporal vs[END_REF][START_REF]MOVNTI -x86 ISA[END_REF]. The goal of these cache bypassing techniques is to better utilize the cache space by avoiding the insertion of useless cachelines into the cache. Hermes's goal is di erent and orthogonal to these techniques: to reduce the latency of a long-latency o -chip load by eliminating the on-chip cache hierarchy access latency from its critical path. As such, Hermes can be combined with any cache bypassing technique.

Data prefetching. Prior prefetching techniques can be broadly categorized into three classes: (1) precomputationbased prefetchers that pre-execute program code to generate future loads [START_REF] Dundas | Improving Data Cache Performance by Pre-executing Instructions Under a Cache Miss[END_REF][START_REF] Hashemi | Continuous Runahead: Transparent Hardware Acceleration for Memory Intensive Workloads[END_REF][START_REF] Hashemi | Filtered Runahead Execution with a Runahead Bu er[END_REF][START_REF] Iacobovici | E ective Stream-Based and Execution-Based Data Prefetching[END_REF][START_REF] Mutlu | Address-Value Delta (AVD) Prediction: Increasing the E ectiveness of Runahead Execution by Exploiting Regular Memory Allocation Patterns[END_REF][START_REF] Mutlu | Techniques for E cient Processing in Runahead Execution Engines[END_REF][START_REF] Mutlu | E cient Runahead Execution: Power-E cient Memory Latency Tolerance[END_REF][START_REF] Mutlu | On Reusing the Results of Pre-Executed Instructions in a Runahead Execution Processor[END_REF][START_REF] Mutlu | Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-order Processors[END_REF][START_REF] Mutlu | Runahead Execution: An E ective Alternative to Large Instruction Windows[END_REF][START_REF] Naithani | Vector Runahead[END_REF], (2) temporal prefetchers that predict future load addresses by memorizing long sequence of demanded cacheline addresses [27, 31, 39-41, 44, 54, 57, 69, 71, 109, 117-119, 123, 124], and (3) spatial prefetchers that predict future load addresses by learning program access patterns over di erent memory regions [26, 28, 32, 33, 35, 37, 46, 56, 70, 75-77, 85, 94, 98, 106, 107, 110, 111]. As we show in §8.4.2, Hermes can be combined with any baseline prefetcher to provide higher performance than just the prefetcher alone.

Conclusion

We introduce Hermes, a technique that accelerates longlatency o -chip load requests by eliminating the on-chip cache hierarchy access latency from their critical path. To enable Hermes, we propose a perceptron-learning based o -chip load predictor (POPET) that accurately predicts which load requests might go o -chip. Our extensive evaluations using a wide range of workloads and system con gurations show that Hermes provides signi cant performance bene ts over a baseline system with a state-of-the-art prefetcher. As on-chip cache hierarchy continues to grow in size and complexity in future processors, we believe and hope that Hermes's key observation and o -chip load prediction mechanism would inspire future works to explore a multitude of other memory system optimizations. 19 shows the performance of Hermes, Pythia, and Hermes combined with Pythia normalized to the no-prefetching system in singlecore workloads as the size of reorder bu er (ROB) varies from 256 entries to 1024 entries. The key takeaway is that Hermes combined with Pythia outperforms Pythia alone in every ROB size con guration. Pythia+Hermes outperforms Pythia by 6.7% and 5.3% in a system with 256-entry and 1024-entry ROB.

B.2. Performance Sensitivity to LLC Size

Fig. 19 shows the performance of Hermes, Pythia, and Hermes combined with Pythia normalized to the no-prefetching system in singlecore workloads as the per-core last-level cache (LLC) size varies from 3 MB to 24 MB. The key takeaway is that Hermes combined with Pythia outperforms Pythia alone in every LLC size con guration. Even in a system with a 12 MB and 24 MB LLC per core, Pythia+Hermes provides 2.5% and 1.3% performance bene t over Pythia alone, respectively. We make two key observations. First, POPET's accuracy and coverage varies widely based on the baseline data prefetcher. When combined with Pythia, Bingo, SPP, MLOP, and SMS, POPET provides accuracy of 77.3%, 78.1%, 73.4%, 79.9%, and 76.0%, while providing coverage of 74.2%, 77.6%, 65.9%, 81.7%, and 84.7%, respectively. Second, in a system without any baseline data prefetcher, POPET provides signi cantly higher accuracy (88.9%) and coverage (93.6%) than any con guration with a baseline prefetcher. This shows that, the prefetch requests generated by a sophisticated data prefetcher interfere with the o -chip load prediction. This is why POPET's accuracy and coverage increases in absence of a data prefetcher. Fig. 22 shows the percentage increase in the main memory requests over the no-prefetching system by di erent types of data prefetchers alone, and in combination with Hermes in all single-core workloads.

Combining Hermes with the baseline prefetcher increases the main memory request overhead by 5.9%, 7.6%, 5.9%, 8.6%, and 15.6% for the baseline prefetchers Pythia, Bingo, SPP, MLOP, and SMS, respectively.

1 2Figure 1 :

 11 Figure 1: Comparison of the execution timeline of an o -chip load request in a conventional processor and in Hermes.

Figure 2 :

 2 Figure2: The distribution of ROB-blocking and non-blocking load requests (on the left y-axis), and LLC misses per kilo instructions (on the right y-axis) in the absence and presence of a state-of-the-art hardware data prefetcher[START_REF] Bera | Pythia: A Customizable Hardware Prefetching Framework Using Online Reinforcement Learning[END_REF].

Figure 3 :

 3 Figure 3: The average number of cycles a core stalls due to an o -chip load blocking any instruction from retiring from the ROB across all workload categories. The dark portion in each bar shows the cycles that can be completely eliminated by removing the on-chip cache access latency from an o -chip load's critical path.

Figure 4 :

 4 Figure 4: (a) Speedup of Ideal Hermes by itself and when combined with Pythia in single-core workloads. (b) Speedup ofIdeal Hermes when combined with four recently-proposed prefetchers: Bingo[START_REF] Bakhshalipour | Bingo Spatial Data Prefetcher[END_REF], SPP[START_REF] Bhatia | Perceptron-Based Prefetch Filtering[END_REF][START_REF] Kim | Path Con dence Based Lookahead Prefetching[END_REF], MLOP[START_REF] Shakerinava | Multi-Lookahead O set Prefetching[END_REF], and SMS[START_REF] Somogyi | Spatial Memory Streaming[END_REF].

Figure 5 :

 5 Figure 5: Percentage of loads that miss the LLC and goes ochip (on the left y-axis) and the LLC MPKI (on the right y-axis) in the baseline system with Pythia.

4Figure 6 :

 6 Figure 6: Overview of Hermes

Figure 7 :

 7 Figure 7: Overview of a single-layer perceptron model. Each blue circle denotes an input and the green circle denotes the output of the perceptron.

Feature 1

 1

Figure 8 :

 8 Figure 8: Stages to make a prediction by POPET 6.1.2. Training the Predictor. POPET training is invoked when a demand load request returns to the core and prepares to release its corresponding LQ entry (step 4 in Fig. 6). Every demand load that misses the LLC and goes to the main memory controller is marked as a true o -chip load request. This true o -chip outcome, along with the predicted outcome stored in the LQ entry of the demand load, are used to appropriately train the feature weights of POPET. The training happens in two stages. In the rst stage, the W σ (computed during prediction) is retrieved from the LQ entry. If W σ is neither positively nor negatively saturated (i.e., W σ lies within a negative and a positive training threshold, T N and T P , respectively), the weight training is triggered. This saturation check prevents the individual feature weight values from getting over-saturated, thereby helping POPET to quickly adapt its learning to program phase changes. In the second stage, if the weight training is triggered, the weights for each individual program feature are retrieved from their corresponding weight table using the hashed feature indices stored in the LQ entry. If the true outcome is positive (meaning the load actually went o -chip), the weight value for each feature is incremented by one. If the true outcome is negative, the weight values are decremented by one. This simple weight update mechanism moves each individual feature weight towards the direction of the true outcome, thus gradually increasing the prediction accuracy.

8. 1 .

 1 POPET Prediction Analysis 8.1.1. Accuracy and Coverage of POPET. Fig.

Figure 9 :

 9 Figure 9: Comparison of (a) accuracy and (b) coverage of POPET against those of HMP [126] and TTP.

Figure 10 :

 10 Figure 10: The accuracy and coverage of POPET using each program feature individually and in various combinations.

Figure 11 :

 11 Figure 11: Line graph of POPET's (a) accuracy and (b) coverage using each of the ve program features individually across all 110 single-core workloads. No single feature can provide the best accuracy or coverage across all workloads.

Figure 12 :

 12 Figure 12: Speedup in single-core workloads

Figure 14 :

 14 Figure 14: Speedup of Hermes with three o -chip load predictors (HMP, TTP, and POPET) and the Ideal Hermes.

Figure 15 :

 15 Figure 15: (a) Reduction in stall cycles caused by o -chip loads. (b) Overhead in the main memory requests. 8.2.4. Overhead in Main Memory Requests. Fig. 15(b) shows the percentage increase in main memory requests in Hermes, Pythia, and Hermes combined with Pythia over the

Figure 16 :

 16 Figure 16: Speedup in eight-core workloads

  (a) shows the speedup of Hermes, Pythia, and Hermes combined with

Figure 17 :

 17 Figure17: Performance sensitivity to (a) main memory bandwidth, (b) di erent prefetching techniques, (c) Hermes request issue latency, and (d) on-chip cache hierarchy access latency. The baseline system con guration is highlighted in green. Other highlighted con gurations closely match with various commercial processors[START_REF]AMD Ryzen Threadripper 3990X[END_REF][START_REF]AMD Zen2 EPYC 7702P[END_REF][START_REF]Intel Xeon Gold 6258R[END_REF].

Figure 17 :

 17 Figure 17: E ect of the activation threshold on POPET's accuracy and coverage (on the left y-axis) and Hermes's speedup (on the right y-axis) for all single-core workloads.

Fig.

  Fig.19shows the performance of Hermes, Pythia, and Hermes combined with Pythia normalized to the no-prefetching system in singlecore workloads as the size of reorder bu er (ROB) varies from 256 entries to 1024 entries. The key takeaway is that Hermes combined with Pythia outperforms Pythia alone in every ROB size con guration. Pythia+Hermes outperforms Pythia by 6.7% and 5.3% in a system with 256-entry and 1024-entry ROB.

Figure 19 :

 19 Figure 19: Performance sensitivity to reorder bu er size. The baseline con guration is marked in green.

Figure 20 :

 20 Figure 20: Performance sensitivity to LLC size. The baseline con guration is marked in green. B.3. Variation of Prediction Accuracy and Coverage with Di erent Prefetchers

Fig. 21 shows

 21 Fig.21shows the o -chip load prediction accuracy and coverage when Hermes is combined with di erent baseline data prefetchers. We make two key observations. First, POPET's accuracy and coverage varies widely based on the baseline data prefetcher. When combined with Pythia, Bingo, SPP, MLOP, and SMS, POPET provides accuracy of 77.3%, 78.1%, 73.4%, 79.9%, and 76.0%, while providing coverage of 74.2%, 77.6%, 65.9%, 81.7%, and 84.7%, respectively. Second, in a system without any baseline data prefetcher, POPET provides signi cantly higher accuracy (88.9%) and coverage (93.6%) than any con guration with a baseline prefetcher. This shows that, the prefetch requests generated by a sophisticated data prefetcher interfere with the o -chip load prediction. This is why POPET's accuracy and coverage increases in absence of a data prefetcher.

Figure 21 :

 21 Figure 21: Variation of o -chip load prediction accuracy and coverage with di erent data prefetchers.

  concurrently accessing the on-chip cache hierarchy for such loads.• We design a new perceptron-based o -chip load predictor, called POPET, that accurately identi es and predicts the o -chip load requests using multiple program features. • We show that Hermes signi cantly improves performance across a wide range of workloads and system con gura-

	tions with varying core count, main memory bandwidth,
	high-performance data prefetchers, and on-chip cache ac-
	cess latencies.
	• We open-source Hermes and all necessary traces and scripts
	to reproduce results in https://github.com/CMU-SAFARI/
	Hermes.

• We introduce Hermes, a new technique that reduces long memory access latency by predicting o -chip load requests and fetching their corresponding data directly from the main memory, while

# Weight Table 1 hash index Feature 2 # Weight Table 2 hash index

 Weight1index2Weight2index

	Stage 1		Stage 2		Stage 3
					weight 1
					weight 2	≥ τact ≥ τact	Predict to go o8f-chip
	. . . . .			. . .	weight n	Sum weights	Activation
	Feature N	#	index	Weight Table N
		hash

(e.g., PC + o8fset)

Table 1 :

 1 6.1.3. Automated Feature Selection. The selection of the program features used to make the o -chip load prediction is critical to POPET's performance. A carefully-crafted and selected set of features can signi cantly improve the accuracy and the coverage of POPET. In this section we propose an automated, o ine, performance-driven methodology to nd a set of program features for POPET.We initially select a set of 16 individual program features using our domain expertise that can correlate well with a load going o -chip. Table1shows the initial feature set.The automated feature selection process happens o ine during the design time of POPET. The process starts with the initial set of 16 individual program features and iteratively creates a The initial set of program features used for automated feature selection. ⊕ represents a bitwise XOR operation.

	Features without control-ow	Features with control-ow
	information	information
		8. Load PC
	1. Load virtual address	9. PC ⊕ load virtual address
	2. Virtual page number	10. PC ⊕ virtual page number
	3. Cacheline o set in page	11. PC ⊕ cacheline o set
	4. First access	12. PC + rst access
	5. Cacheline o set + rst access	13. PC ⊕ byte o set
	6. Byte o set in cacheline	14. PC ⊕ word o set
	7. Word o set in cacheline	15. Last-4 load PCs
		16. Last-4 PCs

Table 2 :

 2 POPET con guration parameters

		• PC ⊕ cacheline o set
		• PC ⊕ byte o set
	Selected features	• PC + rst access
		• Cacheline o set + rst access
		• Last-4 load PCs

Threshold values τact = -18, TN = -35, TP = 40

Table 3 :

 3 Storage overhead of Hermes

	Structure	Description	Size
		• Perceptron weight tables
		-PC ⊕ cacheline o set: 1024 × 5b
		-PC ⊕ byte o set: 1024 × 5b
	POPET	-PC + rst access: 1024 × 5b	3.2 KB
		-Cacheline o set + rst access: 128 × 5b
		-Last-4 load PCs: 1024 × 5b
		• Page bu er: 64 × 80b
	LQ Metadata	Hashed PC: 128 × 32b; Last-4 PC: 128 × 10b; 128 × 5b; prediction: 128 × 1b First access: 128 × 1b; perceptron weight:	0.8 KB
	Total		4.0 KB

Table 4 :

 4 Simulated system parameters

		1 and 8 cores, 6-wide fetch/execute/commit, 512-entry ROB,
	Core	128/72-entry LQ/SQ, Perceptron branch predictor [61] with
		17-cycle misprediction penalty
	L1/L2	Private, 48KB/1.25MB, 64B line, 12/20-way, 16/48 MSHRs,
	Caches	LRU, 5/15-cycle round-trip latency [25]
	LLC	3MB/core, 64B line, 12 way, 64 MSHRs/slice, SHiP [122], 55-cycle round-trip latency [24, 25], Pythia prefetcher [32]
		1C: 1 channel, 1 rank per channel; 8C: 4 channels, 2 ranks
	Main	per channel; 8 banks per rank, DDR4-3200 MTPS, 64b data-
	Memory	bus per channel, 2KB row bu er per bank, tRCD=12.5ns,
		tRP=12.5ns, tCAS=12.5ns
	Hermes	Hermes-O/P: 6/18-cycle Hermes request issue latency

Table 5 :

 5 Workloads used for evaluation

	Suite	#Workloads	#Traces	Example Workloads
	SPEC06	14	22	gcc, mcf, cactusADM, lbm, ...

SPEC17 11 23 gcc, mcf, pop2, fotonik3d, ... PARSEC 4 12 canneal, facesim, raytrace, ... Ligra 11 20 BFS, PageRank, Radii, ... CVP 33 33 integer, oating-point, server, ...

Table 6 :

 6 Storage overhead of all evaluated mechanisms HMP[START_REF] Yoaz | Speculation Techniques for Improving Load Related Instruction Scheduling[END_REF] with local, gshare, and gskew predictors 11 KB TTP with a metadata budget similar to the L2 cache 1536 KB

  Figure 13: Single-core performance of all 110 workloads 8.2.2. E ect of the O -chip Load Prediction Mechanism.Fig.

	Speedup over the No-prefetching system	1.50 1.75 2.00 2.25 2.50	Hermes-O 623.xalancbmk_s-10B Pythia (baseline) streamcluster-6B Ligra_PageRank-79B Ligra_Components-22B compute_int_264 Pythia + Hermes-O server_612 605.mcf_s-782B Ligra_Triangle-25B			compute_int_539 602.gcc_s-2226B
			1	4	7	10	13	16	19	22	25	28	31	34	37	40	43	46	49	52	55	58	61	64	67	70	73	76	79	82	85	88	91	94	97	100	103	106	109
																		Workload number

  2. If you have copied the CSV le using an CSV application that already automatically separates the columns, then go to Step 4. 3. Immediately after pasting, convert the comma-separated rows into columns by going to Data → Text-to-Columns → Select comma as a delimiter. This replaces the already existing data in the sheet with the newly collected data. 4. Refresh each pivot table in each sheet by clicking on them and then clicking Pivot-Table-Analyse → Refresh. The reader can also use any other data processor (e.g., Python pandas) to reproduce the same result. A.8. Expected Results • Accuracy and coverage comparison. POPET should show 77.1% accuracy, whereas HMP and TTP should show 46.8% and 16.6% accuracy, respectively. POPET should show 74.4% coverage, whereas HMP and TTP should show 22.3% and 94.8% coverage, respectively. • Performance comparison with Pythia. Hermes-P, Hermes-O, Pythia, Pythia+Hermes-P, and Pythia+Hermes-O should provide 8.9%, 11.5%, 20.5%, 24.7%, and 25.6% geomean performance improvement, respectively, across all single-core workloads. • Performance comparison with prior predictors. Pythia, Pythia+Hermes-HMP, Pythia+Hermes-TTP, and Pythia+Hermes-POPET should provide 20.5%, 21.1%, 22.09%, and 25.6% geomean performance improvement, respectively, across all singlecore workload traces. • Performance comparison with varying prefetchers. Both Hermes-P and Hermes-O improves performance than the prefetcher by itself for every baseline prefetcher type: Pythia, Bingo, SPP, MLOP, and SMS. The con guration of each prefetcher can be customized by changing the ini les inside the config directory. • The exp les can be customized to run new experiments with di erent prefetcher combinations. More experiment les can be found inside experiments/extra directory. One can use the same instructions mentioned in Appendix A.6.1 to launch experiments.Please check the FAQ section in GitHub (https://github.com/ CMU-SAFARI/Hermes#frequently-asked-questions) for quick troubleshooting tips.

	A.11. Methodology
	Submission, reviewing and badging methodology:
	• https://www.acm.org/publications/policies/
	artifact-review-badging
	• http://cTuning.org/ae/submission-20201122.html
	• http://cTuning.org/ae/reviewing-20201122.html
	B. Extended Results
	B.1. Performance Sensitivity to ROB Size

A.9. Experiment Customization

• A.10. Quick Troubleshooting

Hence named after Hermes, the Olympian deity[START_REF]Hermes -Wikipedia[END_REF] who can quickly move between the realms of the divine (i.e., the processor) and the mortals (i.e., the main memory).

We select Pythia as the baseline prefetcher as it provides the highest prefetch coverage and performance bene t among the ve contemporary prefetchers considered in this paper (see §7.2 and §8.4.2). Nonetheless, our qualitative observation holds equally true for other prefetchers considered in this work (see §7.2).

Even though HMP was originally proposed to predict loads that miss L1 data cache, it can be extended to predict loads that miss the entire multi-level on-chip cache hierarchy.

For simplicity, our automated feature selection process optimizes for accuracy. A more comprehensive feature selection process can also include coverage or directly optimize for performance (i.e., execution time).

As POPET uses ve program features (see §6.1.3), the sum of all ve weights (each represented by a 5-bit saturating signed integer as described in §6.1) can take a maximum and minimum value of 75 and -80, respectively.

Each box is lower-bounded by the rst quartile (i.e., the middle value between the lowest value and the median value of the data points) and upperbounded by the third quartile (i.e., the middle value between the median and the highest value of the data points). The inter-quartile range (IQR) is the distance between the rst and the third quartile (i.e., the length of the box). Whiskers extend an additional 1.5 × IQR on the either side of the box. Any outlier values that falls outside the range of whiskers are marked by dots. The cross marked value within each box represents the mean.

This appendix focuses on reproducing four key results mentioned here. Nonetheless, the artifact contains les and necessary scripts to reproduce all results mentioned in the paper.

Acknowledgments

We thank Anant Nori and Sreenivas Subramoney for their valuable feedback on this work. We thank the anonymous reviewers of MICRO 2022 for their encouraging feedback. We thank the SAFARI Research Group members for providing a stimulating intellectual environment. We acknowledge the generous gifts from our industrial partners: Google, Huawei, Intel, Microsoft, and VMware. This work is supported in part by the Semiconductor Research Corporation and the ETH Future Computing Laboratory. The rst author thanks his departed father, whom he lost in COVID-19 pandemic.

A. Artifact Appendix

A.1. Abstract

We implement Hermes using the ChampSim simulator [START_REF]ChampSim[END_REF]. In this artifact, we provide the source code of Hermes and necessary instructions to reproduce its key performance results. 7 We identify four key results to demonstrate Hermes's novelty: • Comparison of accuracy and coverage of POPET against HMP and TTP (Fig. 9). • Workload category-wise performance comparison in singlecore workloads (Fig. 12). • Workload category-wise performance comparison of Hermes with POPET with Hermes-HMP and Hermes-TTP in singlecore workloads (Fig. 14). • Performance sensitivity to di erent prefetching techniques (Fig. 17(b)).

The artifact can be executed in any machine with a generalpurpose CPU and 36 GB disk space. However, we strongly recommend running the artifact on a compute cluster with slurm [START_REF] Yoo | Slurm: Simple Linux Utility for Resource Management[END_REF] support for bulk experimentation.

A.2. Artifact Check-list (Meta-information)

• Compilation: GCC 6.3.0 or above.

• Data set: Download traces using the supplied script. [START_REF]Hermes GitHub repository[END_REF] or Zenodo [START_REF]Hermes Zenodo repository[END_REF].

A.3.2. Hardware Dependencies. Hermes can be run on any system with a general-purpose CPU and at least 36 GB of free disk space.

A.3.4. Data Sets. The ChampSim traces required to evaluate Hermes can be downloaded using the supplied script. Our implementation of Hermes is fully compatible with prior ChampSim traces that are used in previous cache replacement (CRC-2 [START_REF]2nd Cache Replacement Championship[END_REF]), data prefetching (DPC-3 [START_REF]3rd Data Prefetching Championship[END_REF]) and value-prediction (CVP-2 [START_REF]Second Championship Value Prediction (CVP-2)[END_REF]) championships.

A.4. Installation

A.6. Experimental Work ow

This section describes the steps to generate and execute necessary experiments. We recommend the reader to follow script/README.md to know more about each script used in this section.

A.6.1. Launching Experiments. The following instructions enable launching all experiments required to reproduce key results in a local machine. We strongly recommend using a compute cluster with slurm support to e ciently launch experiments in bulk. To launch experiments using slurm, please provide -local 0 (tested using slurm v16.05.9).

Create the job le for the experiments as follows:

$ cd $HERMES _ HOME/experiments $ perl $HERMES _ HOME/scripts/create _ jobfile.pl -exe $HERMES _ HOME/bin/glc-perceptron-nomulti-multi-multi-multi-1core-1ch -tlist MICRO22 _ AE.tlist -exp MICRO22 _ AE.exp -local 1 > jobfile.sh 2. Please make sure the paths used in tlist and exp les are appropriately changed before creating the job le.

3. If you are creating jobs for slurm, please set the slurm partition name appropriately (set as slurm _ part by default). You might also want to set some key parameters for slurm con guration as follows: (a) max memory per node: 2 GB, (b) timeout: 12 hours.

Finally, launch the experiments as follows:

$ cd $HERMES _ HOME/outputs/ $ source ../jobfile.sh A.6.2. Rolling-up Statistics. The rollup.pl script parses a set of output les of a given experiment and dumps all statistics in a commaseparated-value (CSV) format.

To automate the roll-up process, we use the following set of instructions which enable the creation of four CSV les in experiments directory. These CSV les are later used for comparison in Appendix A.7.

$ cd $HERMES _ HOME/experiments $ bash automate _ rollup.sh

A.7. Evaluation

We use three metrics for comparing Hermes with previous works: (1) performance, (2) accuracy and (3) coverage of the o -chip predictor.

The performance gain of a simulation con guration is measured with respect to the no-prefetching system using Eq. 2.

We measure the accuracy and coverage of each evaluated o -chip prediction mechanism using Eq. 3 and 4.

AccuracyX = T P T P + F P

(3)

Here, TP represents the number of predicted o -chip requests that actually go o -chip, FP represents the number of predicted o -chip requests that do not go o -chip, and FN represents the number of requests that are not predicted by the o -chip predictor but go ochip.

To easily calculate the metrics, we provide a Microsoft Excel template to post-process the rolled-up CSV les generated in Appendix A.6.2. The template has ve sheets. The rst sheet (named metadata) contains the metadata to identify the category of each workload trace and experiment. Each of the remaining sheets shares the same name of the rolled-up CSV le. Each of these sheets is already populated with our collected results, necessary formulas, pivot tables, and charts to reproduce the results presented in the paper. Only the blue-highlighted columns in each sheet need to be populated by your own CSV les. Please follow these instructions to reproduce the results from your own CSV statistics les: 1. Copy and paste each CSV le into its corresponding sheet's top left corner (i.e., cell A1).