<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>RnR: A Software-Assisted Record-and-Replay Hardware Prefetcher</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>10/17/2020</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10200975</idno>
					<idno type="doi"></idno>
					<title level='j'>Proceedings of the 53rd IEEE/ACM International Symposium on Microarchitecture (MICRO)</title>
<idno></idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>Chao Zhang</author><author>Yuan Zeng</author><author>John Shalf</author><author>Xiaochen Guo</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[Applications with irregular memory access patterns do not benefit well from the memory hierarchy as applications that have good locality do. Relatively high miss ratio and long memory access latency can cause the processor to stall and degrade system performance. Prefetching can help to hide the miss penalty by predicting which memory addresses will be accessed in the near future and issuing memory requests ahead of the time. However, software prefetchers add instruction overhead, whereas hardware prefetchers cannot efficiently predict irregular memory access sequences with high accuracy. Fortunately, in many important irregular applications (e.g., iterative solvers, graph algorithms, and sparse matrix-vector multiplication), memory access sequences repeat over multiple iterations or program phases. When the patterns are long, a conventional spatialtemporal prefetcher can not achieve high prefetching accuracy, but these repeating patterns can be identified by programmers.In this work, we propose a software-assisted hardware prefetcher that focuses on repeating irregular memory access patterns for data structures that cannot benefit from conventional hardware prefetchers. The key idea is to provide a programming interface to record cache miss sequence on the first appearance of a memory access pattern and prefetch through replaying the pattern on the following repeats. The proposed Record-and-Replay (RnR) prefetcher provides a lightweight software interface so that the programmers can specify in the application code: 1) which data structures have irregular memory accesses, 2) when to start the recording, and 3) when to start the replay (prefetching). This work evaluated three irregular workloads with different inputs. For the evaluated workloads and inputs, the proposed RnR prefetcher can achieve on average 2.16× speedup for graph applications and 2.91× speedup for an iterative solver with a sparse matrix-vector multiplication kernel. By leveraging the knowledge from the programmers, the proposed RnR prefetcher can achieve over 95% prefetching accuracy and miss coverage.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head>I. INTRODUCTION</head><p>Modern processors have a large processor-memory frequency gap <ref type="bibr">[34]</ref>. Small and fast on-chip caches are beneficial to applications that have good spatial and temporal locality. However, many important applications (e.g., web search <ref type="bibr">[14]</ref>, recommendation system <ref type="bibr">[18]</ref>, machine learning <ref type="bibr">[56]</ref>, and scientific computing <ref type="bibr">[40]</ref>) have large memory footprints and poor locality. As transistor scaling slows down, caching provides limited benefits for these applications. Prefetchers can help to hide long memory access latency and improve performance by predicting which data will be needed and fetching them earlier from the off-chip memory. Various hardware prefetchers have been proposed to predict future memory accesses based on access sequence observed in the past <ref type="bibr">[9]</ref>, <ref type="bibr">[10]</ref>, <ref type="bibr">[25]</ref>, <ref type="bibr">[36]</ref>, <ref type="bibr">[38]</ref>,</p><p>SteMS <ref type="bibr">[52]</ref> Next-line <ref type="bibr">[50]</ref> DROPLET <ref type="bibr">[10]</ref> RnR MISB <ref type="bibr">[59]</ref> Bingo <ref type="bibr">[</ref> </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Miss Coverage</head><p>Prefetching Accuracy Fig. <ref type="figure">1</ref>. Prefetcher coverage and accuracy of PageRank <ref type="bibr">[48]</ref> on amazon graph <ref type="bibr">[32]</ref>. <ref type="bibr">[41]</ref>, <ref type="bibr">[47]</ref>, <ref type="bibr">[52]</ref>, <ref type="bibr">[53]</ref>, <ref type="bibr">[60]</ref>. Commercial high-performance processors have also adopted increasingly sophisticated hardware prefetchers <ref type="bibr">[21]</ref>, <ref type="bibr">[30]</ref>, <ref type="bibr">[51]</ref>.</p><p>Prefetcher designs are typically tailored to common behaviors in application memory access patterns. Regular memory access patterns like streaming or stride are easy to detect and predict using simple hardware prefetchers <ref type="bibr">[45]</ref>, <ref type="bibr">[46]</ref>, <ref type="bibr">[55]</ref>. Irregular memory accesses patterns require complicated hardware designs for recording memory access history or training model parameters to predict future access patterns. In most of the hardware prefetchers, common patterns are recorded in shared tables during the program execution. Because these pattern tables have limited capacity, hardware prefetchers face the challenge of differentiating similar memory accessed patterns <ref type="bibr">[9]</ref>, <ref type="bibr">[25]</ref>, <ref type="bibr">[36]</ref>, <ref type="bibr">[38]</ref>, <ref type="bibr">[41]</ref>, <ref type="bibr">[47]</ref>, <ref type="bibr">[52]</ref>, <ref type="bibr">[53]</ref>. In addition, hardware prefetchers do not know precisely when will the data be needed. One class of hardware prefetcher focus on identifying spatial correlations rather than the order or timing of memory accesses <ref type="bibr">[9]</ref>, <ref type="bibr">[47]</ref>, <ref type="bibr">[53]</ref>. Another class of hardware prefetchers exploit temporal correlations <ref type="bibr">[8]</ref>, <ref type="bibr">[25]</ref>, <ref type="bibr">[38]</ref>, <ref type="bibr">[58]</ref>, <ref type="bibr">[59]</ref>. Meanwhile, commonly used data structures (e.g., graph representations <ref type="bibr">[44]</ref>, <ref type="bibr">[48]</ref> and sparse matrix storage format <ref type="bibr">[23]</ref>) can provide information on which data will be needed in what order. Software prefetchers <ref type="bibr">[5]</ref>, <ref type="bibr">[7]</ref> reply on programmer knowledge or common program behaviors to determine how to issue prefetch instructions. However, software prefetchers adds instructions to generate addresses, which might offset the performance gains from prefetching. Moreover, software prefetchers do not know the runtime dynamics of the systembus congestion and cache contention can cause variable latency for prefetches to return data. Hence, software prefetchers face the challenge of issuing timely prefetches.</p><p>An ideal prefetching mechanism should 1) accurately identify when and which data to prefetch and 2) decouple address generation from processors. In this work, a novel softwareassisted record-and-replay (RnR) hardware prefetcher is pro- posed to allow programmers to control when and which data to prefetch. RnR prefetcher provides light programming interface to identify which data structures and code regions in the applications have repeating memory access patterns.</p><p>The cache misses due to the first appearance of the targeted memory accesses on the predefined data structures will be recorded in memory. Timing information of when will the data be used with respect to the execution of the program is recorded in the metadata for timely prefetches in the future. The prefetcher will be invoked to replay the recorded address sequence and fetch the corresponding data blocks when repeating memory access patterns are expected during the program execution. The prefetching speed is controlled by hardware to enable timely prefetches. The proposed RnR prefetcher is directed by the software. Therefore, it has better knowledge of which data to record, when to record, and when to replay. The proposed RnR prefetcher hence can achieve close to 100% miss coverage and prefetching accuracy for applications with long repeating irregular memory access patterns. Figure <ref type="figure">1</ref> shows the miss coverage and prefetch accuracy comparison of the proposed RnR prefetcher with five existing hardware prefetchers representing different types of prefetchers when running a PageRank application <ref type="bibr">[48]</ref>: a regular pattern prefetcher (Next-line <ref type="bibr">[50]</ref>), a spatial prefetcher (Bingo <ref type="bibr">[9]</ref>), a temporal prefetcher (MISB <ref type="bibr">[59]</ref>), a spatialtemporal prefetcher (SteMS <ref type="bibr">[52]</ref>), and a domain-specific prefetcher (DROPLET <ref type="bibr">[10]</ref>). The contributions of this work are listed below: <ref type="bibr">(1)</ref> This work proposes to separate mixed memory access sequences via programmer-defined temporal and spatial regions. Prior hardware temporal prefetcher designs are trained to recognize common access patterns during the entire execution <ref type="bibr">[38]</ref>, prior spatial prefetcher designs are trained on memory patterns within a pre-defined spatial region (normally OS page) <ref type="bibr">[53]</ref>. These prefetchers differentiate and detect patterns using memory address, offset, program counter (PC), or a combination of them. The proposed work allows programmers to specify static data structures that are accessed repetitively in the same order.</p><p>(2) A new prefetch timing control mechanism is proposed.</p><p>Existing prefetchers issues prefetches triggered by cache access or miss. In this work, the starting point of the replay prefetching is controlled by the software. For the following prefetches, the RnR prefetcher records the timing information as part of the metadata and adjusts the prefetching speed according to the progress of the program execution when issuing replay prefetches.</p><p>(3) A software-assisted record-and-replay prefetcher is proposed, which passes information on spatial and temporal regions of interest through a light hardware-software interface to the hardware prefetcher. the proposed RnR prefetcher can achieve a high accuracy and coverage, as well as timeliness, thus can successfully hide the irregular memory access latency and improve system performance.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>II. MOTIVATION AND KEY IDEA</head><p>The motivation of this work comes from observations on a set of important applications that have repeatitive irregular memory access patterns, which are difficult to predict using conventional hardware prefetchers. Take the Sparse Matrix-Vector multiplication kernel (SpMV) <ref type="bibr">[57]</ref> as an example, when the sparse matrix is stored in a CSR format, the row pointer, column array, and matrix value array are accessed in sequence and have good spatial locality. However, the dense vector array is accessed based on the column array of the matrix, which does not have constant stride or other regular patterns (Figure <ref type="figure">2</ref> (a)). When the SpMV kernel is used in a sparse conjugate gradient (spCG) solver <ref type="bibr">[20]</ref> to get a numerical solution for a partial differential equation, the algorithm starts with an initial guess of the solution and update it according to the conjugate gradients. This process repeats for several iterations until the residual is small enough. This type of iterative solver normally requires tens to hundreds of iterations to converge. In each iteration, the sparse kernel does not change and hence the access sequence to any dense vector that multiplies with the kernel does not change. Similar repeating irregular memory access behaviors are also ubiquitous in iterative graph algorithms (PageRank <ref type="bibr">[39]</ref>, belief propagation <ref type="bibr">[28]</ref>, community detection <ref type="bibr">[31]</ref>, and neighbourhood function approximation <ref type="bibr">[13]</ref>).</p><p>An observation from the above examples is that the repeating patterns is within certain spatial and temporal regions of the program. As shown in Figure <ref type="figure">2</ref> (a), running the spCG or PageRank algorithm produces two kinds of repeating patterns, one type is the regular pattern from reading the matrix array in SpMV, or reading the edge array in PageRank. Another type is the irregular pattern comes from reading the dense vector array in SpMV, or the vertex value (pr curr). These two different patterns are from two different spatial regions (namely s1 and s2 in Figure <ref type="figure">2</ref>) of the program since different arrays are stored at different memory location. The two patterns are repeating at the time domain when the program is executing. In this case, an iteration is the temporal region that contains the unique pattern.</p><p>When the irregular memory access patterns are long (e.g., large graphs and vectors), existing hardware prefetchers are not efficient to prefetch for these applications. An example is shown in Figure <ref type="figure">2 (b)</ref>. Assume a memory access sequence from two spatial regions s1 and s2 are observed when missed in the last level cache (LLC): one with streaming address pattern 1,2,3, another with irregular address pattern 9,12,9,20,1. These memory accesses arrives at the memory controller within a close time window. This type of behavior is common in SpMV and graph algorithms. For example, SpMV touches both matrix and vector when doing the computation. The mixed pattern could repeat many times when the same sparse matrix is used in an iterative algorithm.</p><p>A global history buffer (GHB) <ref type="bibr">[38]</ref> based temporal prefetcher will record the global address correlations and use the address as the index to retrieve the pattern. When an address is followed by different addresses in the sequence (e.g., address 9 is followed by 12 and 20), the prefetcher will pick the most recently used one for the prediction and thus may lead to mis-prediction. What's more, a GHB based approach could not differentiate two mixed patterns, thus may lose prefetching opportunity and result in low miss coverage. More recent works such as ISB <ref type="bibr">[25]</ref> and MISB <ref type="bibr">[59]</ref> utilize PC and address to differentiate different streams and enables efficient metadata management. However, pattern-based prediction faces the fundamental challenge of differentiating similar patterns.</p><p>Existing spatial prefetchers <ref type="bibr">[53]</ref> also do not work well for this type of applications. The spatial region set for the spatial prefetcher to detect pattern is normally an OS page. The page size is small and no ordering information is recorded within a page. Spatial prefetchers are efficient in observing the same spatial patterns among different spatial regions. In a prior spatial-temporal prefetcher <ref type="bibr">[52]</ref>, the access order information are recorded among different sequences, but order information within spatial region is not recorded. In the example in Figure <ref type="figure">2</ref> (a), the repeating patterns are within a spatial region, but across different temporal region. The size of the spatial region could vary for different data structures and could be much larger than a page size.</p><p>The challenges faced by these existing prefetchers can be solved by providing programmer knowledge-if the prefetcher can know when and where will the repeating pattern start and end, it could achieve higher prediction accuracy and prefetch in a timely manner. In this example, if the timing information of when the iteration starts and ends is known by the prefetcher, it could record the cache miss pattern at the first appearance of the sequence, and replay the exactly same sequence for the following repeats. What's more, if the information of the spatial region could be known by the prefetcher (i.e., the address range of the matrix and vector array in this example), the prefetcher could differentiate the streaming pattern from the irregular pattern and thus avoid recording the stream one.</p><p>Another observation is that the existing prefetchers could suffer a lot from ill-timed prefetches. An example is shown in Figure <ref type="figure">2 (d)</ref>. Most of the existing hardware prefetchers trigger the prefetches when a demand miss or access happens. Normally, when a demand miss occurs, the prefetcher will prefetch several recorded address in sequence. However, the actual timing information for two correlated address are unknown, which could lead to either early or late prefetches. Prior prefetchers only record miss order, if the timing information corresponding to recorded memory accesses can be stored as part of the metadata as well, more timely prefetches could be issued.</p><p>Fortunately, the repeating irregular patterns are not difficult to identify in the source code of applications like graph algorithms and iterative solvers with sparse matrix. First, the spatial regions can be identified by knowing which data structures are accessed in a repeating irregular fashion. The temporal regions can be specified by programmers at the start and end of each iterations or evocations. More precise timing information can be estimated by observing miss ratios with respect to progressing time windows during the first occurrence of a target sequence. Besides performance considerations, metadata management is an important issue for prefetcher design, especially for temporal prefetchers that records data correlations. With software assists, metadata could be stored in a contiguous storage region, which makes metadata prefetching fast and efficient. What's more, since the hardware now equipped with the programmer knowledge of the temporal region, the metadata storage space could be released as soon as the target executing phase ends, other than waiting for the entire program to finish. This scheme provides more efficient metadata management as compared to prior works.</p><p>This work proposes a software-assisted record-and-replay prefetcher. The key ideas of this design include: 1) leveraging the software knowledge of when the repeating memory access sequence starts and ends to record the cache misses and prefetch by replay; (2) allowing the software to set regions of interest to reduce recording overhead and focus on irregular patterns; and (3) recording timing information as part of the metadata to enable a more timely prefetching.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>III. DESIGN CHOICES</head><p>While the key ideas are simple, to design an efficient RnR prefetcher many design choices need to be carefully reviewed. RnR targets accurately recording and replay of repeating irregular sequences using software assisted hardware. In this design, a lightweight software interface is provided to allow the software/programmer to communicate to the hardware the temporal/spatial information about when to record, when to replay, and when to stop recording the memory access sequence. A more detailed explanation of the software-hardware interface will be introduced in Section IV. The next question is what to record. A naive approach is to record every data access within the defined range, which is inefficient. Although the sparse structures have poor spatial and temporal locality in general, sometimes locality does exist, such as neighboring vertexes sharing some common neighbors in a social network graph. Recording all of the structure accesses may lead to redundant record and prefetch, and thus waste the storage space and bandwidth. Therefore, the proposed design chooses to record the miss sequence from the private L2 cache in a multi-level cache hierarchy. At this stage, memory accesses that could benefit from locality are filtered by the private L1 and L2 caches. Regarding where to store the recorded information, the proposed design puts these data into a predefined memory space allocated by the programmer using a programming interface that will be introduced in Section IV. Since the access latency to get the recorded metadata is long, RnR uses a metadata prefetching scheme similar to <ref type="bibr">[25]</ref>. Another important question is when to prefetch. Previous designs trigger the prefetch event based on a single cache access, or a single cache miss, or a combination of them with a confidence threshold. RnR starts prefetching at the replay phase. Hardware gets knowledge about the optimal timing and phasing of the prefetch stream through the software interface. Within the replay phase, RnR uses an efficient reply timing-control mechanism to ensure timely prefetching. This is achieved by recording timing information as part of the metadata, which will be introduced in details in Section V-C. Finally, regarding where to put the prefetched data, RnR chooses the private L2 cache. This is based on the observation in DROPLET <ref type="bibr">[10]</ref> that using the L2 cache for this purpose shows negligible influence of cache pollution.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>IV. PROGRAMMING INTERFACE</head><p>This section describes the architectural states and programming interface of the RnR prefetcher (IV-A), an example use case (IV-B), and the operating system supports (IV-C).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A. Architectural States and RnR Functions</head><p>To achieve an effective "Record and Replay" of the memory accesses, the proposed RnR prefetcher requires the following additional architectural states: (1) a address space identifier (ASID) register for permission check, (2) a set of boundary checking address registers <ref type="foot">1</ref> and their associated size and active states (enable vs. disable), (3) a base address register for a Sequence Table, (4) a window size register, (5) a base address register for a window Division Table, and (6) a prefetch state register. The sequence table is used for recording miss sequence. The window size and window division table are used for recording miss ratios during each time window such that this information can be used to control the replay prefetching pace (Section V-C)). Both the sequence table and the window division table are stored in memory spaces allocated by the programmer, hence the registers only need to store the base addresses of these two tables. All of the these architectural states are implemented as special registers per core. All of the address registers store virtual addresses. The ASID register stores the identifier of the process that is currently using the prefetcher.</p><p>The programmer needs to first identify which target data structures to be recorded. The target data structures can be defined at the memory allocation time. By passing down the base addresses and the corresponding sizes to the boundary registers, the prefetcher can recognize whether the access is within the target range or not (Section V-A). Accesses out of the target range will not be recorded or replayed (prefetched).   Moreover, the software also needs to define where will the miss sequence be stored, 2) how large will be the window size for pace control, and 3) where will the window division table be stored. Window size determines the number of structure misses that are recorded in each of the window. To provide the timing information that indicate how long each of the window is, the window division table stores the total number of demand accesses within each of the window, which is used for controlling prefetching aggressiveness (Section V-C).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Record</head><p>The prefetch state is also controlled by the software. 1 At first, the programmer needs to enable the RnR prefetcher to start recording the miss sequence during the first appearance of the sequence. At the end of the recording, a replay function can be invoked to disabled the recording and start the replaying deg+[s] ) 14 return 1 15 <ref type="bibr">16</ref> Procedure PRNormlize(i): RnR.end() 37 return pcurr 2 (start prefetching from the beginning of the stored sequence in the memory). If the repeating sequence is not expected immediately, a pause can be used to stop recording 8 . At the end of each of the replay, either a replay 3 or pause 5 can be used to stop the replay. After all of the repeated iteration finished, and end function can be called 4 to terminate the "Record and Replay" process. The record or replay can be paused 5 8 in the middle and resumed 6 9 from where it is paused to support context switch.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B. An Example of Using the Programming Interface</head><p>The PageRank from Ligra <ref type="bibr">[48]</ref> is used as an example to show an use case of the programming interface (Algorithm 1, RnR related codes are colored in blue). Note that this example includes an out-of-place update for p curr and p next , which means the base pointer will be exchanged at the end of each iteration (line 33). Therefore the full address range of p curr in each iteration is not the same. However, the element in the array can be divided into Base+Offset. Even if the Base changes, the Offset are kept the same. To correctly select which Base to use, the programmer also needs to swap the Base at the end of each iteration. Line 7 initializes the RnR prefetcher by setting internal parameters and allocating memory space for metadata. RnR.init() also sets the Window Size for replay timing controller (described in Section V-C) to a default value. Since the prefetching destination is the L2 cache as described in Section III, the default window size is set to half of the L2 size for double buffering. Line 8-9 defines the virtual address range for p curr and p next , with their corresponding size N (N is the number of vertices in this case). Line 24 enables the address range for p curr before the recording starts. Line 25 starts the recording process. Line 31-33 enable and disable the swapped base address p curr and p next for prefetching the next iteration. Line 35 terminates RnR prefetcher. Line 36 free out the reserved storage for all of the metadata stored in memory.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C. Operating System Supports</head><p>The operating system can schedule a process or thread to different cores to optimize for resource utilization. A process can also be switched out due to long latency events such as page faults. Conventional hardware prefetchers need retraining after context switching. However, RnR does not need retraining if the same access order is expected because the metadata is stored in allocated heap space. During context switch or process migration <ref type="bibr">[22]</ref>, the on-going recording or replaying need to be paused. The corresponding architectural states as well as RnR internal states (Section V) need to be copied to memory. For migration and switching in a process that has paused RnR prefetching, the values of these registers will be copied in before resuming the execution of the process and the prefetching. RnR requires to save/restore a total of 86.5B of additional states (Section V) , which is not expected to add a significant performance overhead. This is because context switching overhead comes from losing register, TLB, branch predictor, and cache states. Cache warmup penalties are typically the bottleneck <ref type="bibr">[26]</ref>, <ref type="bibr">[33]</ref>.</p><p>V. RNR ARCHITECTURE Since the programmer can now define when to start and end the record and replay using the programming interface, the proposed RnR prefetcher executes according to the architectural state diagram in Figure <ref type="figure">3</ref>. In Figure <ref type="figure">4,</ref><ref type="figure">arrow A,</ref><ref type="figure">B,</ref><ref type="figure">C,</ref><ref type="figure">D</ref>, and E are software interfaces that updates RnR architectural states to guide the RnR prefetcher. In addition to the registers that are visible to software, the RnR prefetcher also requires internal registers, which include: (1) a current structure read counter; (2) a 128B buffer for sequence table and a 128B buffer for division table ; (3) length registers for the two tables respectively; (4) current physical addresses to write or read the two tables; (5) a number of prefetcher counters; (6) a current window counter; and (7) a current prefetch pace register that stores the desired number of demand reads per prefetch during the current prefetch window.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>A. Record</head><p>After the prefetch state register is set to 'Record', RnR starts to record the L2 miss sequence of the target data structure. Figure <ref type="figure">4</ref> shows how does the record iteration performed before the programmer stops recording. This provides the miss ratio information of this window, which can be used to guide the prefetch speed during the replay (Section V-C). 7 To minimize the write traffic, the metadata writes are grouped at cache line granularity (write back every 64B). The RnR prefetcher now needs to find the reserved memory space for writing metadata. The virtual address of the metadata head pointer can be calculated by calculating 6 Similar to the 'Record' state, the RnR prefetcher needs to calculate the addresses in order to prefetch for both the sequence table and the division table. One TLB lookup is needed for a 4MB page to perform the virtual to physical address translation. Once the address is generated, the prefetch requests could be issued to LLC based on the prefetch pace. If the request hit in the LLC, the data will be fetched to the L2 cache, otherwise the request goes to the memory. 7</p><p>The prefetching aggressiveness (how much ahead to prefetch) needs to be adjusted to match with the application progress, which can be tuned at the granularity of the prefetching window. The proposed design stores the prefetched blocks into L2 cache, hence the aggressiveness is bounded by the L2 cache size. For the evaluated benchmarks, double buffering (one window ahead) is enough to provide timely prefetches. The RnR prefetcher also adjust the frequency of issuing prefetches within a prefetch window to minimize contention with demand accesses without delaying the prefetches, which will be discussed in Section V-C. When the Cur Struct Read matches with the recorded count for the next window, the current window counter is incremented and the RnR can start to prefetch misses for the next window after finishing all of the prefetches for the current window. The prefetching pace will be hence updated with window switching.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C. Replay Timing Control</head><p>Traditional memory prefetchers can be triggered for different levels of aggressiveness. Nexline prefetch requests the next cache line after each access. Spatial and temporal prefetchers can trigger an new prefetch request when the miss sequence matches with the recorded common pattern. RnR stores one sequence per core to prefetch. As described in Section V-A, RnR also stores the miss ratio information per prefetch window. This allows the RnR prefetcher to match prefetching speed with the progress of the program execution. As shown in the Figure <ref type="figure">5</ref> (a), different window may have different miss ratios according to whether the data region has relatively good locality or not. In this example, Window 1 has a miss ratio of 50%, whereas the window 2 has a miss ratio of 33.3%. If the prefetcher does not consider the miss ratio information and issues a prefetch on every demand access as shown in Figure <ref type="figure">5</ref> (b), the prefetches would be too aggressive and the prefetched data would be easily evicted out of the L2 cache by the time the data is needed. However, if the miss ratio information is stored, the replay prefetch controller can know when to stop. In the example in Figure <ref type="figure">5</ref> (c), after the third prefetch is issued, the RnR prefetcher will wait until the sixth access to the targeted data structure before it issues prefetches of the next window. To further optimize the prefetch traffic, the prefetches can be evenly distributed within a prefetch window to avoid congestion and interference with demand accesses. The frequency of issuing prefetch requests can be calculated by</p><p>This means a prefetch is issued every N Pace structure accesses (Figure <ref type="figure">5 (d)</ref>).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>D. Integrate with Other Prefetchers</head><p>As shown in Figure <ref type="figure">4</ref>, the L2 stream prefetcher excludes the target sparse data structure so that the conventional stream prefetcher <ref type="bibr">[21]</ref>, <ref type="bibr">[30]</ref>, <ref type="bibr">[51]</ref> will be trained by L2 misses outside of the Record-and-Replay address range. The proposed RnR prefetcher can support both regular and irregular memory accesses, but a streaming or stride would be more efficient at predicting regular memory access patterns. The proposed RnR prefetcher can be easily integrated with other hardware prefetchers by filtering out temporal and spatial regions of interest.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>E. Scalability for Multicore Systems</head><p>There are two questions to answer regarding the scalability of this design in a multicore system: 1) how will the hardware overhead grow as the number of cores increases? and 2) how will the metadata storage overhead grow as the number of cores increases? RnR collects the private L2 miss sequences from the target data structure. The special registers to store architectural states and RnR internal states are per core. Therefore, the hardware overhead increases linearly with respect to the core count. Given the fact that the total hardware overhead for each core is small, the hardware area overhead is negligible as compared to the chip area (Section VII-B). The total storage overhead depends on the number of L2 cache misses from the target data structure. For parallel workloads, the data structures of a large problem are typically partitioned and assigned to multiple threads to run on different cores. Accesses to another core's data partition might increase the total number of cache accesses. But when more cores are opted in, the total capacity of private caches is also increased. Hence the total L2 misses might be reduced. Moreover, partitioning algorithms <ref type="bibr">[29]</ref>, <ref type="bibr">[49]</ref> typically aim to improve locality and reduce cross-partition communication. After partitioning the data structure, each worker thread executes on different cores will primarily access their own data partition. The data regions of interest should also be set for each data partition. In such cases, the total storage overhead will not increase significantly when running on multicore systems.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>VI. EXPERIMENTAL SETUP</head><p>This work uses ChampSim <ref type="bibr">[3]</ref>, a trace-based simulation infrastructure, to evaluate the proposed RnR prefetcher. Champ-Sim is adopted in the 3rd Data Prefetching Championship (DPC3) <ref type="bibr">[1]</ref>. The cache subsystem in ChampSim includes FIFO read and prefetch queues. The demand requests have a higher priority than prefetch and metadata requests. The main memory model simulates data bus contention, bank contention, and bus turnaround delays. When there are more contentions, memory access latency is increased. The baseline configuration is shown in Table <ref type="table">II</ref>. Cache sizes and latency are modeled based on Intel i7-6700 <ref type="bibr">[4]</ref>. Cadence Genus Synthesis Solution <ref type="bibr">[15]</ref> is used to analyze the RnR prefetcher hardware area. The area is estimated based on FreePDK45nm <ref type="bibr">[54]</ref> standard cell library, and is scaled to 22 nm. The memory timing constraint comes from Micron MT40A2G4 DDR4-2400-CL17 data sheet <ref type="bibr">[2]</ref>. We mark the region of interest (ROI) of the code and using the PIN tool <ref type="bibr">[35]</ref> to extract the kernel trace for trace-based simulation. 20 million instructions are used to warm up the on-chip caches and at least 500 million instructions of the kernel are simulated.  This work evaluated vertex-centric PageRank algorithm from Ligra <ref type="bibr">[48]</ref>, sparse CG from Adept <ref type="bibr">[23]</ref>, and edgecentric Hyper-anf from x-stream <ref type="bibr">[44]</ref>, which have repeated access trace across different iterations. Graph and sparse matrix inputs of the application are listed in Table <ref type="table">III</ref>, which covers representative inputs with different characteristics (i.e., size, sparsity). Graph algorithm and scientific applications have many different libraries support for parallelization <ref type="bibr">[16]</ref>, <ref type="bibr">[24]</ref>, <ref type="bibr">[43]</ref>. In this work, we implement the applications as Single Program Multiple Data (SPMD) <ref type="bibr">[17]</ref> model (every task executes the same program), which is commonly used in many pull-based graph algorithm <ref type="bibr">[12]</ref> with graph partitioning <ref type="bibr">[29]</ref>, <ref type="bibr">[49]</ref>. The master process initializes the array, sends the partitioning information to worker processes, performs its own share of the computation and wait for all of the worker processes to finish. Each worker process receives the partitioning information, performs its share of computation, and sends results back to the master. We use METIS <ref type="bibr">[29]</ref> to partition graph inputs into four partitions and assign each of the worker processes a partition to run. </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>VII. EVALUATION RESULTS</head><p>The proposed RnR prefetcher is compared against three general-purpose prefetchers and one domain-specific prefetcher for graph algorithm: 1) Next-Line, 2) SteMS <ref type="bibr">[52]</ref>, 3) BINGO <ref type="bibr">[9]</ref>, and 4) DROPLET <ref type="bibr">[10]</ref>. Since DROPLET is designed for graph algorithms, the evaluation results do not include DROPLET when running spCG. 1) Speedup: The proposed RnR prefetcher does not prefetch for the target structure during the recording state. The effective performance of RnR depends on how many times it can reuse the recorded pattern to prefetch. The more replays, the higher speedup the RnR can achieve. For PageRank and HyperAnf, the total number of the iterations depends on the graph inputs and the stopping criteria (e.g., Line 29 in Algorithm 1). For all given inputs and the default value of the benchmark suite, both PageRank and Hyper-Anf take more than a hundred iterations to converge. For spCG, the algorithm converges when the residual is equal or smaller than the default value, which typically takes hundreds of iteration to finish. Therefore, the overhead of the record iteration can easily be amortized by the replay iterations. We use 100 iterations for all tested applications and inputs for simplicity. As shown in Figure <ref type="figure">6</ref>, RnR refers to using the proposed prefetcher for only the irregularly-accessed data structure, RnR-Combined refers to using the RnR prefetcher for the irregularly-accessed data structure and using stream prefetcher (next-line) for all other data. The ideal case is analyzed by having an infinite-sized LLC.</p><p>For graph algorithms, RnR achieves the highest performance improvement for most of the graph inputs and can increase performance significantly for the synthetic graph urand, which has random connections and poor data locality. Generalpurpose prefetchers (next-line, bingo, SteMS) are typically ineffective for the graphs that have many random connections due to the lack of a common spatial or temporal pattern to exploit. DROPLET achieves near zero performance improvement for PageRank with the urand graph input. This is because DROPLET first prefetches the edge data in a streaming fashion and then uses the prefetched edge data to generate vertex addresses to prefetch for indirect accesses. The address generation latency of this extra level of indirection can take away the potential opportunity of timely prefetching for random graph like urand, in which the vertices are lack of spatial locality and hence take longer time to fetch.</p><p>The proposed RnR prefetcher does not have dependencies when generating prefetch addresses. The metadata is prefetched from recording without recomputing. Therefore, the RnR prefetcher is effective for all of the graph inputs and can achieve the highest performance. RoadUSA is a road map and presents a relatively regular connection pattern, so that even the general-purpose prefetchers are effective.</p><p>For spCG, RnR prefetcher can deliver higher speedups because it can separate stream and sparse access patterns. In general, the proposed RnR can achieve 2.11&#215;, 2.23&#215;, and 2.90&#215; performance improvement for PageRank, Hyper-Anf, and spCG kernel respectively. The proposed RnR prefetcher uses the private L2 as the prefetching destination. To create a fair comparison, all of the evaluated prefetchers are prefetching data into the private L2. We believe this does not handicap the other prefetchers as the partitioned graphs utilized for the parallel benchmarks have minimal sharing between threads. As shown in Figure <ref type="figure">7</ref>, the proposed RnR-Combined prefetcher can reduce the demand miss ratio by 97.3%, 94.6%, and 98.9% for PageRank, Hyper-Anf, and spCG kernel respectively. And for graph algorithms with urand and com-orkut as the inputs, the MPKI can still be reduced by more than a half.</p><p>2) Coverage: The miss coverage refers to the total number of misses that the prefetcher can reduce from the baseline, which is a direct indication of the effectiveness of the overall prefetcher design. 100% coverage means the prefetcher can correctly prefetch all of the misses observed in the baseline (i.e., a "perfect" prefetcher). Hence, Coverage = Useful Prefetches Total Baseline Misses . The higher the coverage, the more misses the  prefetcher can detect and correctly prefetch. Spatial-temporal prefetchers reply on the shared common access pattern, which are not as prevalent in the evaluated applications as database and transaction applications. Therefore, only part of the miss sequence can be detected. roadUSA with good locality, the bingo and SteMS can achieve good performance. DROPLET covers the dependent load by using edge data to predict the dependent load of the vertex data, which can achieve better coverage for edge-centric Hyper-Anf as compared to vertexcentric PageRank. The proposed RnR prefetcher can detect all of miss sequences for the target data structure without sharing patterns and data dependencies. Therefore, RnR can achieve on an average of 91.4%, 84.5%, and 88.7% of miss coverage.  3) Accuracy: The prefetching accuracy is the fraction of useful prefetches out of the total issued prefetches. Accuracy = Useful Prefetches Total Prefetches . General purpose prefetchers (bingo and SteMS) have problems with sequence miss-matches for accesses with similar spatial-temporal patterns. Therefore, for applications dominated by irregular memory accesses, general-purpose prefetchers achieve the lowest accuracy. For some inputs with a good spatial locality, for example, roadUSA, they can average nearly 50% accuracy. DROPLET achieves better accuracy as compared to bingo and SteMS. This is because DROPLET is able to capture the data-dependent indirect access for graph algorithms. However, for graph algorithms where the edge array can not be fetched early enough (PageRank-urand), DROPLET will have lower prefetching accuracy.</p><p>RnR can achieve on an average of 97.18% of prefetching accuracy. This is because the replay iteration will have exactly the same miss sequence as the record iteration. By matching prefetching speed with demand access, most of the prefetched data will be used before it is evicted.</p><p>4) Effectiveness of replay timing control: RnR issues timely prefetches by matching the number of prefetches per window (Section V-C). As shown in the Figure <ref type="figure">10</ref>, replay without the window-based control cannot improve performance due to the mismatch of prefetch timing with the demand access (Figure <ref type="figure">5</ref>  blocks before uses. Therefore, the performance is improved significantly (2.31&#215;). For most of the evaluated workload, window control is already good enough for controlling the prefetching speed.  5) Timeliness: Besides coverage and accuracy, timeliness is also essential to the effectiveness of prefetching. Prefetching too early will cause prefetched data to be evicted out of the cache before it is needed. On the other hand, prefetching too late can not help to hide the miss penalty. To understand the timeliness of the proposed RnR prefetcher, we divide the total prefetched data into four categories: 1) on time prefetch, 2) early prefetch (prefetches that are demanded in the corresponding window but are evicted when the accesses arrive), 3) late prefetch (prefetches that are demanded in the corresponding window but are issued later than the accesses arrive L2), 4) out of the window (prefetches that are not demanded in the corresponding window). All of those four categories sum up to the total issued prefetches. As shown in Figure <ref type="figure">11</ref>, most of the applications can match the prefetch speed perfectly with the demand access speed. Only two graph algorithms with urand show 7-8% of prefetches that are either early or late. This is because the off-chip demand access may overtake or delay the prefetch requests since the demand accesses are prioritized over prefetches. Applying pace control on top of window control does not significantly improve the prefetching timeliness. Only for graph algorithms with urand as input, pace control slightly reduce early prefetch by 3-4%.</p><p>6) Record Iteration Overhead: The first recorded iteration will have some performance degradation for metadata management. Given the fact that the write traffic is not on the critical path of the applications, the latency of writing metadata back to memory can be largely hidden using non-temporal (overwriting) stores. The evaluated memory system uses a write queue draining policy, which prioritizes a demand read over the write. Based on our observation, the PageRank with urand incur the largest performance degradation with only 1.75% of IPC lower than the baseline. This is because the total amount of writing traffic depends on the size of metadata. Since the synthetic graph has the highest miss rate, the writing overhead for this application is the highest. On average, the record iteration cost 1.02% of performance slow down as compared to the baseline with no prefetcher.</p><p>7) Additional Off-chip Traffic: The additional off-chip traffic is determined by T otalP ref etch &#215; (1 -Accuracy) + M etadataT raf f ic. On an average, bingo, SteMS, nextline, and MISB generate more than 2&#215; of the total prefetch requests as compared to RnR. The high accuracy of RnR is the main reason for relatively low additional off-chip traffic. Metadata traffic is the main source of RnR's additional offchip traffic. Accessing to metadata is streamed and has good spatial locality, which can efficiently utilize DRAM row buffer and memory internal parallelism. Next-line, bingo, SteMS, MISB, DROPLET, RnR, and RnR-Combined add on average of 45.2%, 67.1%, 58.4%, 19.7%, 12.2%, 12.0%, and 27.6% of additional off-chip traffic respectively. DROPLET and the RnR prefetcher add a similar amount of additional traffic. DROPLET adds additional traffic because of the inaccurate prefetching; whereas the RnR prefetcher adds extra traffic due to metadata prefetching. Inaccurate prefetching may offset the performance gains by polluting the cache space. However, the metadata are not stored in cache. MISB also stores metadata off-chip, and uses on-chip cache storage to reduce metadata traffics. The reason why MISB has a little higher off-chip traffics is also because of lower prefetching accuracy. For graph algorithms with urand as input, the metadata overhead is higher as compared to other inputs, hence incurs higher additional traffic using RnR as compared to MISB and DROPLET. </p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>B. Hardware Overhead</head><p>RnR prefetcher needs architectural state registers (Section IV), internal state registers (Section V), and a modest amount of control logic per core. The total hardware overhead for RnR prefetcher is less than 1KB for each core (2.7E -3 mm 2 ), which consumes less than 0.01% of the total on-chip area (46.19 mm 2 ).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>C. Storage Overhead</head><p>RnR prefetcher requires a sequence table for the recorded miss sequence and a window division table for replay timing control. As compared to the sequence table, the window division table is much smaller as it only needs to store one word per window (thousands of addresses per window in sequence table) Therefore, most of the storage overhead comes from the miss sequence table.</p><p>The total storage overhead for each of the application and inputs depend on how large the inputs are and the data locality.  For example, PageRank with the roadUSA input has good spatial/temporal locality and would require 7.64% of storage overhead of the original input size; whereas PageRank with the urand input needs 22.43% of the storage overhead due to its poor locality. Hyper-Anf with the amazon input has a 4% more storage overhead as compared to PageRank with the same input. This is because Hyper-Anf has a higher miss ratio. On average, RnR requires 12.1%, 13.0%, and 11.58% of the storage overhead for PageRank, spCG, and Hyper-Anf respectively (Figure <ref type="figure">13</ref>). The window size defines the granularity for RnR prefetcher to match the prefetch aggressiveness with the program execution (Section V-C). The smaller the window is, the more frequent the RnR prefetcher can adjust prefetching frequency. However, the smaller the window, the larger the Window Division Table . Because the RnR prefetches into the private L2, the window size should not exceed the half of L2 cache size. We observed that window size between 64 to 2048 cache lines achieves similar speedup as well as storage overhead (Figure <ref type="figure">14</ref>). Window size below 64 will significantly reduce the effectiveness of RnR prefetching and increase storage overhead.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>D. Window Size</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>VIII. RELATED WORK</head><p>To understand the differences of the proposed prefetcher as compared to prior work, Table <ref type="table">IV</ref> summarizes the key design decisions made by four most related designs.</p><p>Temporal prefetchers <ref type="bibr">[8]</ref>, <ref type="bibr">[25]</ref>, <ref type="bibr">[38]</ref>, <ref type="bibr">[58]</ref>, <ref type="bibr">[59]</ref> capture the irregular access pattern by memorizing the temporal address correlations. It is effective for pointer chasing based applications. Because the correlation information grows in proportion to the application's memory footprint, temporal prefetchers normally requires a large amount of metadata to achieve good performance. MISB <ref type="bibr">[59]</ref> stores the metadata off-chip and prefetches them to a near core location before it is needed. MISB needs to lookup the metadata to find the corresponding address to prefetch, which requires 49KB of on-chip storage for metadata caching. RnR does not requires metadata lookup and only neeeds 1KB per core. In terms of prefetching effectiveness, there are three reasons why RnR outperforms MISB: 1) MISB is designed for applications with common temporal patterns. As discussed in Section II , using MISB with PC localization is hard to differentiate similar temporal sequences. However, similar temporal sequences is commonly exists in graph algorithms (e.g., traversing nodes within a cluster). 2) MISB can only prefetch the next few structural addresses (MISB uses a maximum prefetch degree of eight); whereas RnR can start prefetch one window ahead (up to 2048 cachelines). 3) MISB is trained at arbitrary application phase and data, which is difficult to filter out irrelevant accesses.</p><p>Spatial prefetchers <ref type="bibr">[9]</ref>, <ref type="bibr">[47]</ref>, <ref type="bibr">[53]</ref> observe patterns within a spatial region, which are suitable for high-end server applications such as online transaction processing (OLTP) and decision support system (DSS) <ref type="bibr">[42]</ref>. These applications normally utilize data structures that have repetitive layouts, thus recurring patterns emerge in the relative offsets of accessed data. Because the patterns are restricted within a memory region and no temporal order information is recorded, a state-of-the-art spatial prefetcher normally requires a minimal amount of metadata, which could be stored in an on-chip hardware table . 
IMP <ref type="bibr">[60]</ref> is designed for indirect memory accesses to follow the A[B[i]] indirect accesses, which shares some common targets with RnR. However, IMP is a purely hardware design, which generates indirect addresses by predicting the correlated index stream. This approach suffers from low prefetching accuracy and ill-timed prefetches, which leads to low miss coverage. Programmable Prefetcher <ref type="bibr">[6]</ref> focused on indirect memory access (e.g, C[B[A[x]]]), where accessing array A has memory-level parallelism and prefetching array B, C does not need to wait. This technique needs compiler assistance, which offload software prefetches to programmable hardware.</p><p>DROPLET <ref type="bibr">[10]</ref> is a more recent work that targets on indirect memory accesses in graph algorithms. It also has a lightweight software interface to define the targeted data structure (spatial region). DROPLET generates the addresses for an indirectly accessed vertex value by prefetching the edge array. Since DROPLET is equipped with software knowledge, it's accuracy and coverage is higher than IMP. However, the vertex data prefetching is triggered when edge data refills the DRAM read queue, which is often too late. As compared to DROPLET, RnR records the miss address patterns as well as the timing information. Although it requires additional storage space, the RnR improves both the prefetch accuracy and timeliness.</p><p>Software prefetchers <ref type="bibr">[37]</ref> often achieve higher accuracy and coverage as compared to hardware prefetchers. Several related works propose inserting prefetching instructions at an appropriate place through programmer and compiler efforts. However, software prefetching schemes are difficult to migrate to a different microarchitectures because it lacks of the hardware knowledge. Furthermore, it could incur large instruction overhead, which may offset the prefetching benefits.</p><p>Compared to prior work, the novelties and advantages of the proposed RnR prefetcher include: 1) It provides a lightweight software interface to communicate the spatial and temporal information of the prefetch region of interest to the hardware prefetcher, which improves prefetching accuracy and miss coverage. 2) It records the private cache miss addresses and miss ratio in each prefetch window for the targeted data structure, and uses a replay timing control mechanism to achieve timely prefetches. and 3) RnR is not bound to a particular microarchitecture, it is scalable and can co-exist with other prefetchers.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>IX. CONCLUSION</head><p>In this work, a novel software-assisted RnR hardware prefethcer is proposed to improve prefethching accuracy and miss coverage for applications that have long repeating irregular memory access patterns. By allowing programmer to decide when and what to record and replay, the proposed RnR prefetcher can efficiently record miss sequence of the target data structure and prefetch through replay in a timely manner.</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_0"><p>The number of address registers can be variable, two are used in the evaluation.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="2" xml:id="foot_1"><p>Trace sizes for different applications and inputs varies a lot. We simulate the whole record iteration and replay iteration regardless of how large the traces are.</p></note>
		</body>
		</text>
</TEI>
