Due to high percent of data is represented as N - dimensional arrays or other array - based structures, especially in scienti c applications, access to this data will have regular pattern, consequently regular pattern prefetchers work e ectively for a wide range of tasks. Main advantages of regular pattern prefetchers are low o - chip tra c, hardware simplicity, consequently low power consumption, compact area on the chip and low incremental memory bus load, caused by prefetching. This paper introduces AR2P - adaptive regular pattern prefetcher. The key ideas of AR2P are adaptive prefetch depth that depends on spatial locality of data, late prefetch detection, and decreasing power consumption as compared with RPT prefetcher due to ip - op switch reduce. We evaluate AR2P using cycle accurate single core MARSS - RISCV simulator and TACLE benchmark set. AR2P shows 95% coverage on the average on benchmarks with regular access pattern and 37% for complex patterns.
Instruction and Data prefetchers are critical modules of modern computing systems, due to DRAM-memory is a bottleneck and one memory access costs nearly 100 machine cycles, consequently cache misses signi cantly in uence on task execution time. Prefetching data and instructions into cache before demand is designed to reduce cache misses and increase performance.
Now microprocessors usually contain several prefetchers, for caches of di erent levels and di erent memory access patterns. For example, Intel microarchitectures: Ivy Bridge, Broadwell and other have two prefetchers for L2 cache and two prefetchers for L1 data cache. For L1 data cache there is an adjacent line prefetcher and PC - localized prefetcher. ARM cores have similar prefetching subsystem.
Prefetchers can take place in memory subsystem as shown on Figure 1 as a variant.
Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Main questions, that arise in design process of L1 prefetching subsystem are: { Is it possible to adapt prefetcher for various access patterns dynamically? { What is optimal for designed system, large L1 cache and simple prefetcher, or small L1 cache and complex accurate prefetcher? { Where is e ective to keep prefetched data, in cache or in on-chip prefetch bu ers? { Which event triggers prefetching?
Cache misses LLC access
Prefetced data hits { How do con ict misses in not fully - associative caches depend on prefetching?
There is a trade o between accuracy, coverage and hardware complexity,
although recent researches[
This section introduces analysis of various regular pattern prefetchers and correlated prefetchers for irregular patterns, that are used in today computing systems. 2.1
The simplest regular pattern prefetcher is next N line prefetcher. On triggering
event on address X, prefetcher puts into cache memory N lines next to accessed
line. If memory virtualization is used, prefetcher should stop on physical page
bounds. On sequential access patterns like matrix operations with primitive data
types or for instruction cache next N line prefetchers are rather e ective. Jamison
D. shows in his research that next N line prefetcher can have accuracy and
coverage more 90 % on hydro and about 75% on mgrid benchmarks [
Other simple prefetcher is a stride prefetcher. On triggering event on address X, prefetcher puts into cache memory words from X + S to X + (S + N) addresses in common case, where S is the stride. Prefetcher detects if stride repeats necessary times, it predicts that next stride will be same and prefetches data. In common case, stride prefetchers are e ective on operations with arrays of structures and matrix rows and columns. Now microprocessors usually use RPT prefetcher. To introduce RPT prefetcher consider situation, presented on Figure 2.
There is a cycle, where each element of array C should be summed up with appropriate elements of arrays A and B. On each step of the cycle A[i], B[i], C[i] are fetched: Stride 1 : address A[i] - address C[i-1] Stride 2 : address B[i] - address A[i] Stride 3 : address C[i] - address B[i]
Due to this stride is various, consequently clearly discernible stride does not
exist and stride prefetcher is ine ective here. The solution to the problem is
an on chip table, where prefetcher keeps last memory access address , detected
stride and con dence counter. On triggering event for de ned PC current access
address is compared with last address. If stride is the same, con dence counter
updates, else stride eld of table updates with new value. If con dence counter
value is more than reference value, prefetch occurs on current address with added
stride. Main metrics: accuracy - percent of prefetch hit and coverage - percent
of cache misses, prevented by prefetcher, are 90% for art benchmark, and 30 %
and 23 % for gcc [
Correlated prefetchers are e ective on non-stride or irregular memory access patterns as processing linked list or graph elements. Common principle of correlated prefetcher is memorizing sequential streams of memory accesses, and on prefetching next stream part on triggering event.
Markov Table. Markov table is one of early solutions to organize temporary
correlated access pairs spatially, by table, indexed by physical address[
Domino Domino prefetcher[
MISB ARM introduced Managed Irregular Stream Bu er (MISB) prefetcher
in 2019. The main idea of MISB is to create a new structural address space
in which correlated physical addresses are kept in sequence. The key point is
that in this structural address space, streams of correlated memory addresses
are both temporally ordered and spatially ordered. The mapping from physical
to structural addresses and vise versa is performed at a cache line granularity
by two spatially indexed on-chip address metadata caches whose contents can
be easily synchronized with that of the TLB[
Today's microprocessors usually have separate L1 caches for instructions and data. If there are no branches, instruction are fetched sequentially from memory, consequently for L1 instruction cache next N line prefetcher can be e ectively used with branch predictor interaction.
For L1 data cache there is a solution to modify localized PC data prefetcher by improving prefetch stride scale and prefetch depth prediction mechanism for regular patterns. The second modi cation is unlike RPT prefetcher updates Last address eld for all entries of it's on-chip metadata table, our solution updates Last address for speci ed PC entry. This reduces power consumption due to eld last address ip- op switch decrease.
In common case for stride prefetcher if stride is close to the current demand, next demand may occur before necessary data be prefetched, that defeats purpose of prefetching. If stride is large, prefetching occurs too early, prefetched data can be evicted from cache. RPT prefetcher potentially su ers of late prefetches. This problem can be solved by detecting that demand was occurred before data was prefetched. If this repeats several times sequentially, prefetcher decides to increment stride . If stride doesn't change for several times, prefetcher assumes that it is a vector or matrix, calculates prefetch depth. Organization of prefetcher is shown on Figure 4. At the rst moment stride is detected as di erence between last address base + o set and current address. O set indicates position in prefetched vector, when prefetch depth more than 1. Further if di erence is equal stride, con dence counter increments. Prefetch depth can be calculated as di erence between condence counter and reference repeat value. When current address become equal last address base + prefetch depth, last address base changed to current address and new data is prefetched. If stride changes, scale, con dence counter, late counter are reset. On late prefetch event late counter increments. If late counter over ows, stride is increased by itself, scale increments. Algorithm of proposed prefetcher is shown on Figure 5
Figure 5 - Proposed algorithm
For value evaluation of proposed method was used cycle accurate simulator MARSS - RISCV with following con guration: { core : out of order, single core { L1 data cache size : 32 KB ways : 8 eviction policy : LRU { L2 shared cache size : 512 KB . ways : 8 eviction policy : LRU
The evaluation uses TACLE benchmarks to explore prefetcher e ciency on regular access patterns and Linux launch for complex pattern exploration. To make sure that results given by MARSS - RISCV simulator are adequate, benchmarks were simulated on MARSS-RISCV without prefetcher and results of simulation were compared to RTL simulation of RISC-V core with the same con guration. The di erence in measurements was not more than 0,9%.
Models of AR2P, stride prefetcher, adjacent line prefetcher and Domino prefetcher were simulated. Single core results are presented on the Figure 6.
p c = 1 ; (1)
m where c - coverage, p - misses with prefetcher, m - misses without prefetcher.
On diagram Tacle benchmarks bsort and matrix1 have mainly regular access patterns, Tacle powerwindow and countnegatives have complex regular and irregular patterns. Linux launch has more irregular than regular memory access patterns.
AR2P shows 95% coverage on the average on Tacle benchmark set with mainly regular patterns, that is 30% more e ective than stride prefetcher and 20% more e ective than adjacent line prefetcher. On complex patterns as Linux launch AR2P shows 37% coverage, that is 25% less e ective than Domino because of con ict evictions from reference prefetch table and non clear stride.
At the moment vector of attention is directed on: { The ability to dynamically adapt to irregular and complex patterns. The main idea is to detect, if clear stride does not exist and con ict evictions occur frequently, prefetcher assumes, that memory access pattern is irregular and uses reference prefetch table as miss history table. { The dependence of e ciency of prefetcher on associativity of reference prefetch table/miss history table. 5
Researches[