Repositorio Institucional de Documentos

2013 74 Jorge Albericio Latorre Improving the SLLC Efficiency by exploiting reuse locality and adjusting prefetch Departamento Director/es Informática e Ingeniería de Sistemas Ibáñez Marín, Pablo Enrique Llaberia Griñó, José María Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Jorge Albericio Latorre IMPROVING THE SLLC EFFICIENCY BY EXPLOITING REUSE LOCALITY AND ADJUSTING PREFETCH Director/es Informática e Ingeniería de Sistemas Ibáñez Marín, Pablo Enrique Llaberia Griñó, José María Tesis Doctoral Autor 2013 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Improving the SLLC efficiency by exploiting reuse locality and adjusting prefetch Author: Jorge Albericio Latorre Supervisors: Dr. Pablo Ibáñez Marín Dr. José María Llabería Griñó Dissertation Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Universidad de Zaragoza Grupo de Arquitectura de Computadores Dpto. de Informática e Ingeniería de Sistemas Instituto de Investigación en Ingeniería de Aragón Universidad de Zaragoza Marzo 2013 EXECUTIVE SUMMARY Chip-Multiprocessors (CMP) are nowadays commonplace from embedded to supercomputer markets. Due to the existing gap, between cpu and main memory speeds, a hierarchy of cache memories is included in the chip with the aim of reducing the average memory access latency. Commercial CMPs include a hierarchy with two or three levels of cache memories, where the Last-level cache (LLC) is usually shared among all the cores in the system and comprises several megabytes of storage that fill up to a half of the total chip die area. Moreover, the LLC hit ratio critically affects performance since being the last storage inside the chip, any miss at the LLC provokes an expensive off-chip access to the main memory, penalizing the average memory access latency. The whole CMP efficiency passes through the SLLC efficiency. This thesis makes contributions comprising the SLLC efficiency on two different directions: 1) its performance and 2) its hardware storage. 1) In order to improve SLLC performance, two aspects are tackled during this thesis: hardware prefetching effectivity and replacement policy. The contribution to optimize hardware prefetching is a lowcost controller, called ABS, that relies on a hill-climbing approach to infer the optimal combination of prefetching aggressiveness associated to the different cores of the CMP. This controller achieves better results than state of the art with a lower cost. Regarding to the replacement policy, this thesis proposes to base the SLLC replacement algorithm on a property called reuse locality that will be stated during this dissertation. Two new replacement policies are proposed. As it will be shown during the evaluation, our algorithms achieve better performance than the state of the art with a lower hardware complexity. 2) In order to reduce SLLC hardware storage, this thesis proposes a SLLC design called reuse cache. This design relies on the reuse locality property to only store data that has shown reuse. The tag array is used to detect reuse and maintain coherence. The experimental evaluation will show that this contribution allows drastic reductions of iii the SLLC hardware storage cost while maintaining the overall system performance. iv RESUMEN EJECUTIVO Los chips multiprocesador (CMP) están presentes en la actualidad en todos los segmentos de mercado, desde los teléfonos móviles hasta los superordenadores. Debido a la gran diferencia que existe entre la velocidad del procesador y la de la memoria principal, los CMPs en la actualidad están provistos de una jerarquía de memorias cache que tiene dos o tres niveles. Cada fallo en el último nivel de esa jerarquía (SLLC) provoca un acceso a la memoria principal que se encuentra fuera del chip. Además la memoria principal está hecha de chips de DRAM. Ambos factores incrementan su latencia de acceso, latencia que se suma a cada uno de los accesos que falla en la SLLC, penalizando a la vez la latencia media de acceso a memoria. Por lo tanto, la tasa de aciertos de la SLLC es un factor crítico para lograr una latencia media de acceso a memoria óptima. Esta tesis fija su atención en la eficiencia de la SLLC y concretamente, en la eficiencia de la prebúsqueda y la explotación de la localidad de reúso. Para mejorar la eficiencia de la prebúsqueda se propone un controlador de bajo coste llamado ABS capaz de ajustar la agresividad de la prebúsqueda asociada a cada uno de los núcleos de un CMP pero con el ánimo de mejorar el rendimiento general del sistema. El controlador funciona de manera aislada en cada uno de los bancos de la SLLC y recoge métricas locales. Para optimizar el rendimiento global del sistema busca la combinación óptima de valores de la agresividad de prebúsqueda. Para inferir cuál es esa combinación óptima usa una estrategia de búsqueda hill-climbing. En esta tesis se caracteriza la propiedad de localidad de reúso y se realizan contribuciones que tienen por finalidad última una mayor explotación de dicha propiedad. En concreto, se proponen dos algoritmos de reemplazo capaces de explotar la localidad de reúso, Leastrecently reused (LRR) yNot-recently reused (NRR). Estos algoritmos son modificaciones de otros dos muy bien conocidos: Leastrecently used (LRU) yNot-recently used (NRU). Diseñados para explotar la localidad temporal, mientras que los propuestos en esta tesis explotan la localidad de reúso. Las modificaciones propuestas no suponen ninguna sobrecarga hardware respecto a los algoritmos base y al mismo tiempo v muestran ser capaces de incrementar el rendimiento de la SLLC de manera consistente. Además se propone un diseño para la SLLC llamado Reuse Cache. En este diseño solamente se almacenan en el array de datos aquellos bloques que hayan mostrado reúso. El array de etiquetas se usa para detectar reúso y mantener la coherencia. Esta estructura permite reducir el tamaño del array de datos de manera drástica. Como ejemplo, una Reuse Cache con un array de etiquetas equivalente al de una cache convencional de 4MB y un array de datos de 1MB, tiene el mismo rendimiento medio que una cache convencional de 8MB, pero con un ahorro de almacenamiento de en torno al 84%. vi 1.1 context and background 5 L1D L1I Core L2 L1D L1I Core L2 Interconnect to main memory (a) Private L1D L1I Core L2 L1D L1I Core Interconnect to main memory (b) Shared Figure 1.2: Last-level cache organizations shared In a shared organization of the Last-level cache (SLLC), all the cores share the complete LLC available storage (Figure 1.2b). The size of the SLLC is bigger than in the private design, so the access latency is also larger. Given the LLC storage is shared among all the cores, the activity of the applications running in the system may harm each other. On the other hand, only one copy of the data used by more than one core is stored in the SLLC, maximizing the effective SLLC available storage. In addition, a SLLC can suffice at the same time the requirements of two very different applications. SLLC are internally split in banks which are accessed through one port. This organization provides at the same time layout flexibility and increased access bandwidth. This thesis follows the general trend in both industry and academy, choosing a shared design (SLLC) as the LLC organization where contributions are proposed and evaluated. 1.1.2 Inclusivity A hierarchy of cache memories (L1-L2) is said to be inclusive when the L2 stores the contents of all the L1s. In other words, the L2 contents are always a superset of the L1 caches contents [3]. In order to maintain this property, two actions have to be consistently performed: 1. When a cache line is inserted in some L1, it must be also inserted in the L2 if it is not present. 2. When a L2 line is evicted, invalidation messages are sent to all the L1 copies, if any. 6introduction An inclusive hierarchy simplifies coherence maintenance [42]. As the SLLC knows about the contents of the cache levels closer to the processor, a mechanism to maintain the coherence installed at this level is able to take decisions without sending look-up messages to the local caches. Many commercial CMPs present an inclusive hierarchy [20]. A hierarchy of cache memories (L1-L2) is said to be exclusive when the contents of the L2 and the L1s are always disjoint sets. Meaning that when a cache line is inserted in some L1, it must be removed from the L2 if it is present. In this type of hierarchy, two basic schemes can be considered to maintain the system coherent. This information can be present at the SLLC as an updated copy of the L1s tags, or be obtained by sending look-up messages to the L1s every time some situation requires it. When neither inclusion nor exclusion are enforced, the hierarchy is said to be non-inclusive/non-exclusive. There exist a broad range of options to define this intermediate scheme [69,53]. This thesis considers an inclusive SLLC organization as the baseline design where contributions are proposed and evaluated. 1.1.3 Hardware Data Prefetching Hardware prefetching is a technique that tries to load into the cache, contents the processor will use in the future. The decision on what to prefetch has relayed on plenty of prediction schemes, from simple to very sophisticated ones. All of those schemes revolve around a property programs show, called spatial locality. This property says that a program will reference in the future, memory addresses that are close to memory addresses it referenced recently in the past. In other words, programs are kind of predictable in their stream of references accessing to memory. The hardware prefetcher installed at some cache level observes the stream of references arriving to that cache with the intention of generating prefetches that bring data into the cache which will be referenced in the near future. A basic type of prefetcher trying to exploit spatial locality is the stride prefetcher. This prefetcher calculates the difference between the addresses of the cache lines referenced by two consecutive misses and it generates a prefetch request based on such difference, e. g. misses are observed over the cache lines corresponding to the ad- 1.1 context and background 7 dresses Aand A+m, thus the stride prefetcher will generate a request for the address A+2m. The basic case of stride is when m is equal to 1, a prefetcher considering always this kind of pattern is called sequential prefetcher. A parameter associated to the prefetcher is its aggressiveness. The aggressiveness of a prefetcher defines how much (degree), and also, depending on the type of prefetcher, how far (distance) the prefetcher will follow its prediction in order to bring data to the cache. E.g. on the stride prefetcher, the degree defines how many cache lines will be brought into the cache per triggering event, for the example before, if we define degree as equal 3, consecutive misses to Aand A+m will generate prefetches of A+2m,A+3m, and A+4m. Aggressiveness of a prefetcher should adapt to application and memory system characteristics. Adaptive mechanisms to dynamically adjust the prefetching aggressiveness has been previously proposed and are presented in Section 2.2. If a CMP system with a SLLC is considered new tradeoffs, which are presented in the next Section, appear. 1.1.4 Replacement Policy When a miss is observed by the cache and there is no free cache entries, one cache line has to be selected as victim. The replacement policy decides which is the cache line that will be evicted to make place for another incoming. Three basic schemes of replacement traditionally considered are: 1) Random. 2) FIFO. 3) LRU. random The random replacement policy, as its name indicates, randomly chooses a victim among the elements present in the set. Its implementations normally uses a pseudo-random periodical function. It does not need any additional storage. first-in-first-out The First-In-First-Out (FIFO) replacement policy orders the elements of a set following their arrival order. Only a pointer is needed to implement this policy, the pointer has to indicate the element entered the furthest in the past. The storage needed to implement this policy is log2(associativity) bits per set. The lifespan of a line in a N-way associative cache is exactly the time for the set to observe N misses. A spread variant of the FIFO policy is the CLOCK algorithm. It was originally proposed for the management of pages in a virtual memory 8introduction management system [12]. It has been used in caches or buffers with a high associativity. It uses one bit per cache line to record if the element has been referenced during its stay in the structure or not. When an element has to be evicted, the element entered the first one is selected as victim, if its bit is set, the bit will be reset and the next element will be considered as possible victim. least-recently used The least-recently used (LRU) replacement algorithm is oriented to exploit a property called temporal locality that programs show when running. Temporal locality assumes that a recently used cache line will be used again in the near future. All the elements in a cache set conform a chain and are ordered following the use order; the most recently referenced elements are at the beginning of the chain, while the end of the chain is occupied by the least recently referenced element. On a miss, a cache line has to be chosen as victim, the last one is selected. Every cache line increases its position by one and the new line is inserted at the beginning of the chain. On a hit, the hit line is situated at the beginning of the chain while all the lines that were occupying positions over the hit line see decremented their position by one. There is a plenty of options to implement the LRU policy, each one representing different tradeoffs in terms of storage cost and logic complexity. Sudarshan et al. made a review of different implementations in [60]. True LRU can be implemented with low cost when small associativities are considered, e.g. to implement LRU in a 4-way associative cache is 8 bits per set. But when higher associativities are considered (1632-, or 48-way associative caches), as the ones we can find in a SLLC, true LRU gives way to alternative policies that try to mimic LRU performance with a lower hardware cost. These policies are called pseudo-LRU policies. There is a broad variety of this kind of policies and what they have in common is the use of partial information to maintain an approximation to the LRU order inside the set. Normally, all of them try to avoid to evict the most-recently used element while they keep some kind of order among the rest of the elements of a set. An example of pseudo-LRU policy is Not-recently used (NRU) [43]. As Figure 1.3 shows, this policy employs one bit for each cache line (NRU-bit), the bit is zero when the line is inserted into the set. All the NRU-bits but the one corresponding 1.1 context and background 9 I LRU chain NRU stateref I I IIa ba III a I I I b a I Ic c b a Ia a c b Ic miss miss miss hit hit c a b Ie miss e c a bf miss f e c a 0 a0b0 b0c0 a0 b0c0 a0 b0c0 a0 b1c1 a1e0 b1c1 f1e0 miss miss miss hit hit miss miss 1111 II I 111 I I 1 1 I1 I1 I1 NRU bits Figure 1.3: Example of LRU and NRU replacement policies to the just inserted line will be reset in case of all the NRU-bits are equal to zero. When a victim has to be selected, the first cache line with the NRU-bit equal to one is evicted. The search of the line with NRU-bit equal to one can be started from the position indicated by a global pointer (Sun T2) or from the way 0 (intel i7). In Figure 1.3, we can observe an example of the behavior of LRU and NRU replacement policies. Each line represents the state of the set before the reference that appears on the left column accesses the cache. For LRU, elements are ordered forming a chain, while for NRU each element is at its corresponding way and the NRU bit appears along the address. Next to state, for both algorithms, we can observe if a determined reference is a hit or a miss. Consecutive lines of the figure show consecutive states of the set; the second line of any pair shows the state of the set after the reference ("ref" on the figure) of the first line makes its access effective. Section 2.3 presents recent research on replacement algorithms for the SLLC. These works have shown replacement policies for the SLLC should not be based on temporal locality and the next section will expose the problem. 10 introduction 1.2 problem Every SLLC miss provokes an access to the main memory. The main memory is out of the chip and made of DRAM memory chips, adding a long latency to every access that misses in the SLLC and penalizing the average memory access time. Thus, the SLLC hit ratio is a critical factor to achieve an optimal average memory hierarchy access latency. Technological innovations aside, two aspects that can be tackled to improve the SLLC hit ratio are the efficiency of both prefetching and replacement policy. 1.2.1 Hardware Data Prefetching Hardware prefetching tries to load data into the cache time ahead of the processor references it. This technique has been broadly shown as good to reduce the average access memory latency. Prefetching performs specially well in mono-processor memory hierarchies where only one stream of data flows from main memory to the caches closer to the core. However, when prefetching is used in the SLLC of a multicore system where different applications are running at the same time, prefetches associated to one core may interfere with the data placed into the cache by other core, evicting contents of other application and harming its performance. A control mechanism to regulate the prefetching aggressiveness associated to each core is desired. This mechanism should target the overall system performance. In section 2.2, we feature previous work on hardware data prefetching aggressiveness adjustment for monoand multi-processor systems, and in Section 4.2 we explain in detail the aforementioned inter-core prefetching interference problem. 1.2.2 Replacement policy The replacement policy critically influences the cache memory hit ratio. In a CMP fitted with a hierarchy of cache memories, temporal locality is squeezed by the cache levels closer to the core. Thus, many of the lines inserted in the SLLC are single use, meaning that they will not experiment any hit during their lifespan at the SLLC. However, cache lines that experiment one hit in the SLLC are normally experimenting many hits. Therefore, to assume that the replacement 1.3 contributions 11 algorithm has to base its decisions on the temporal locality exploitation is no longer valid at the SLLC. On the contrary, this behavior indicates the SLLC replacement policy should be based on reuse instead of temporal locality. Section 5.2 goes over SLLC replacement problematics with more detail. 1.3 contributions These are the main contributions of this thesis: 1.3.1 The ABS controller A low-cost controller able to adjust the prefetching aggressiveness associated to each core in the CMP with the aim of improving the overall system performance. The controller runs stand-alone at each SLLC bank and gathers local metrics. Using a hill-climbing approach whose target function is the overall system performance, the ABS controller tries to infer the optimal combination of prefetching aggressiveness values for the applications that are running in the system. 1.3.2 Reuse locality Observing the stream of references accessing to the SLLC, we state a property called Reuse locality that says that i) Cache lines used more than one time will be highly likely used many times in the future. ii) Cache lines recently reused are more useful than lines reused before. We claim that SLLC access pattern shows reuse locality. 1.3.3 Replacement algorithms to exploit the reuse locality Two replacement algorithms able to exploit the reuse locality are proposed, Least-recently reused (LRR) and Not-recently reused (NRR). These algorithms are modifications of two very well known algorithms based on the use, to be based on the reuse. The base algorithms are Least-recently used (LRU) and Not-recently used (NRU), our transformations do not add any hardware to them. We will show that 12 introduction these two new algorithms consistently improve the performance of their predecessors. 1.3.4 Reuse cache A novel design for the SLLC of a CMP is proposed. On this design tag and data arrays are decoupled. Only those cache lines that have shown reuse are stored in the data array. The tag array is used to detect reuse and maintain coherence. This scheme allows to drastically reduce the size of the data array. As an example, a reuse cache with a tag array equivalent to a conventional 4MB cache and a data array of 1MB achieves the same average performance that a conventional 8MB cache 1.4 thesis organization This dissertation is organized in four parts. The first part contains Chapters 1, 2, and 3. These chapters introduce the topics of the dissertation, present background and previous works, and discuss the experimental framework followed during this thesis. Second part includes only Chapter 4 that explains our contribution to adjust prefetching aggressiveness. Third part comprises Chapters 5 and 6, which explains our contributions to improve the SLLC efficiency by the better exploitation of reuse locality. Finally, fourth part concludes this dissertation. chapter 2 presents previous works related with the contributions presented on this thesis. Related work includes research regarding the exploitation of reuse locality, works where decoupled structures are proposed or used, prefetch engines with the aim of improving CMP performance, and in mechanisms to adjust the prefetching aggressiveness in monoand multi-processors. chapter 3 explains the experimental setup that has been used to evaluate our proposals. Including the simulator characteristics, the baseline system we consider, and the workloads whose behavior have been analyzed during this thesis. 1.4 thesis organization 13 chapter 4 presents the ABS controller and its evaluation. The evaluation includes the use of particular metrics that will be justified. A comparison with the state of the art is also presented. chapter 5 states the reuse locality and presents two replacement policies that exploit such property. This chapter also shows the evaluation of our policies and their comparison with both base algorithms and state of art. chapter 6 presents the reuse cache and its rationale and design are explained. That chapter also shows a broad evaluation from different design points and a comparison with the state of the art. The chapter finishes suggesting further improvements or future lines for the reuse cache. chapter 7 concludes the dissertation summarizing the work done and discusses about possible future research lines. 2.3 reuse locality 21 Lai et al. [31] proposed Block Predictors, predictors that accurately identify if a cache line is dead. The mechanism evicts those cache lines detected as dead and prefetchs data into them. Instead of using PCs to predict wether a cache line is dead, Liu et al. [36] predict dead blocks based on bursts of accesses to a cache block. A cache burst begins when a block becomes MRU and ends when it becomes nonMRU. The authors claim that cache bursts are more predictable than individual references because they hide the irregularity of individual references. The underlying behavior of lines assumed in dead-block prediction and reuse-based replacement is the same: a big fraction of cache lines is dead at any moment. However, the opportunity that shows up is exploited in different ways. Our mechanisms classify a priori all lines entering the SLLC as dead (since we realize most of them are indeed touched once). A line becomes alive once it is referenced a second time during its stay in the SLLC. 2.3.4 Replacement on inclusive hierarchies In inclusive hierarchies, the core caches absorb most of the temporal locality and the hot lines may lose positions in the LRU stack of the SLLC, up to the point of being evicted. A recent paper shows ways to solve this problem by identifying lines in the core caches and preventing their replacement in the SLLC [22]. Three ways are proposed: sending hints to the SLLC about the core accesses (TLH), identifying temporal locality by early invalidation of lines in the core caches (ECI), or querying the core caches about the presence of the victim lines (QBS). We also address this problem by using the information present in the coherence directory, assuming non-silent eviction of clean blocks in the private caches. However, our main contribution is the design of two replacement algorithms that exploit reuse locality with the same hardware cost than those used in commercial processors. 22 related work 2.4 how to decouple the sllc tag and data arrays? In recent years, there have been many innovations for improving the performance of the SLLC. In spite of this huge quantity of research, most of innovations only achieve to improve system performance within 5%. One of the contributions of this thesis, the reuse cache, targets the SLLC efficiency in a different way, proposing to downsize the SLLC data array while maintaining the average performance. In order to achieve that objective, our proposal relays on a decoupled tag and data arrays. Next we show works used similar types of decoupled designs. Using pointer indirection appears as a natural solution when tag/- data decoupling is required. Several authors have used this idea for different purposes. Regarding sectored caches, a common idea is to share a number of data subsectors among a set of tag sectors, instead of the conventional 1:1 mapping between a tag sector and its data subsectors. Seznec suggests decoupling to conciliate a low tag implementation cost with a low miss ratio [52], while the decoupling proposed by Rothman et al. aims to reduce cache space requirements [50]. Chishti et al. propose the NuRAPID cache, that decouples tag lookup and data placement in order to reduce the average access latency in dynamic non-uniform cache architectures [9]. Tag/data decoupling has also been proposed in the V-way cache by Qureshi et al. to achieve a high associativity and reduce the number of conflict misses in the non-inclusive last level cache of a singleprocessor system [48]. The V-way cache stores the same number of items in tag and data arrays and inserts into the cache all the data requested by the lower level caches. However, V-way relies on additional tag space to reduce conflicts in the set associative tag array. In the data array, V-way requires a global replacement policy based on use frequency. In contrast, the reuse cache objective is to reduce the cache size while keeping performance and inclusion benefits. It stores more tags than data lines and tries to only retain lines showing reuse. The additional tag space in the reuse cache allows to maintain inclusion and track reuse. Furthermore, its data array does not require a global replacement algorithm. Two recent works are directly related with our reuse cache contribution [37,69]. The cache organization relies in tag/data decoupling 2.4 how to decouple the sllc tag and data arrays? 23 to retain tags inclusion property and to use a selective allocation policy of lines in a cache miss. NCID uses additional tags in order to maintain tag inclusion of the private caches, though the data lines of those private caches are not necessarily present in the data array. So, NCID allows SLLC data to be non-inclusive or exclusive while retaining the inclusion property on tags. Moreover, many NCID architectural options are presented and evaluated. One of them uses NCID to support a selective allocation policy to address transient data. Selective allocation allocates tag and data for a randomly chosen 5% of the lines and only tag for the remaining 95%. Set dueling is proposed to select between normal fill or selective fill policies. Instead of random selection, the reuse cache data array selects lines with potential for reuse. In the reuse cache, tags without allocated data are indeed used to maintain inclusion, but also to detect reuse. Once a line experiences such a reuse it is written in the data array. Both, the replacement algorithms of tag and data arrays are designed with the objective of identifying and prioritizing reused lines. Set dueling is not needed. Lodde et al. [37] use cache line state and coherence messages to classify lines as private or shared. Such information is used to selectively allocate only shared lines in the data array in order to reduce data array size. This organization requires to move tags within the tag array when the classification of a line changes. The information used by the selective allocation policy does not take reuse into account. Thus, transient private cache lines are put into the shared data array, increasing required data array size. Our proposal relies in reuse locality detection, independently of which private cache requests the line. Thus shared lines are implicitly allocated in the data array and private lines are only allocated if reuse locality is detected. 3 EXPERIMENTAL FRAMEWORK summary In order to evaluate each of the contributions of this thesis, the associated mechanisms were faithfully modeled and these models incorporated to a simulator. The simulator was then used to run a set of benchmarks and the results of that simulations were employed to infer the validity of the hypotheses. The experimental framework is explained on this chapter: baseline system, simulator, workloads, and metrics. 25 26 experimental framework 3.1 introduction This chapter explains the experimental framework used during this thesis. Here it is shown the common part of this experimental framework, meaning that in the evaluation of some of our contributions the configuration of the considered system varied, workloads were built in an alternative way, or the metrics used to evaluate our proposals were different or enlarged. In such points, this document explains the corresponding changes. The remaining of this chapter is organized as follows. Section 3.2 shows the baseline CMP system has been considered along this thesis. Section 3.3 presents the Simics full-system simulator and ruby, a plugin for Simics by the University of Wisconsin Madison which allowed us to model the memory hierarchy of our system. And finally Section 3.4 discusses about the types of workloads used in this thesis and the different metrics used to evaluate them. 3.2 baseline system Figure 3.1 shows the CMP system we have used during this thesis. It comprises eight in-order SPARC V9 cores and a hierarchy of memory composed by three levels of cache. The first level is private to each core and it is composed by split instruction and data cache memories. The second level is private and unified (data and instructions). And last, the third level is shared among all the cores in the system. All the three cache levels are write-back write-allocate. Table 3.1 shows remarkable parameters of the considered hierarchy. core 0 Local caches crossbar core 7 Local caches bank 0 bank 3 SLLC MC to memory Figure 3.1: Baseline system overview 3.3 simulator 27 The third is the last level of our hierarchy of cache memories. We consider an 8 MB LLC, split in four banks which are shared among all the cores in the CMP. The banks are cache line interleaved to facilitate a homogeneous share of accesses, excepting on the ABS prefetching proposal, where they were interleaved using operating system page size to avoid inter-bank interference. The SLLC is accessible through a crossbar that connects the eight L2s to the four SLLC banks. Inclusion is enforced at the SLLC, meaning that a cache line is inserted at the SLLC when it is inserted into some L1 or L2, and when a cache line is evicted from the SLLC, it is also removed from any L1 or L2 that could have a copy. An invalidation directory-based MOSI coherence protocol is implemented to maintain the private caches coherent. The directory is distributed among the SLLC banks, containing its information along with the tag of each cache line. The memory system comprises 4GB of DDR3 DRAM per core which are accessed trough one memory channel. The memory runs at one quarter of the frequency of the processor. 3.3 simulator In order to perform experimental evaluations of our proposals, we used the Simics simulation platform [40]. Simics provides functional models of all the devices included in a system (i/o, network, hard disks, etc...), allowing full-system simulation of multi-processor systems. At the same time it is able to simulate a wide range of cpus Private L1 I/D 32 KB, 4-way LRU replacement, 64 B line size, 1-cycle access latency Private unified L2 256 KB, 8-way LRU replacement, 64 B line size, 7-cycle access latency Shared L3 8 MB inclusive (4 banks of 2 MB each), 64 B interleaving, 64 B line size. Each bank: 16-way, LRU replacement, 10-cycle access latency. 16 demand MSHR DRAM 1 rank, 16 banks, 4 KB page size, Double Data Rate (DDR3 1333Mhz). 92-cycle raw access latency DRAM bus 667Mhz, 8 B wide bus, 4 DRAM cycles/line, 16 processor cycles/line Table 3.1: Baseline system configuration 28 experimental framework at the instruction set level, e.g. ARM, SPARC, x86, MIPS, and Alpha. Simics run with hypervisor privileges, allowing to execute unmodified real operating systems; during this thesis, the evaluated systems were managed by the Solaris 10.0 operating system. To accurately simulate the memory hierarchy of a CMP model we used the ruby plugin from the GEMS Multifacet toolset [41], publicly available thanks to the University of Wisconsin. This plugin is loaded into the Simics simulator to capture all the memory access operations, modeling their latency with cycle accuracy. Ruby provides faithful models of all the memory hierarchy components from the cache controllers to the switches of the Network-on-chip interconnect. Buffering and blocking of components due to lack of resources are always considered. During this thesis many of the components of ruby have been modified or enlarged to faithfully model each one of our proposals; including a model of the memory controller that implements the DRAM DDR3 protocol. During the implementation of our ABS controller this model was fundamental in order to accurately model the overhead that prefetching provoked on the memory hierarchy. The model reflected the status of every page of memory, queues, bus occupancy, and the scheduling policy, to observe how they were affecting each memory operation. Other modifications we included in GEMS are clarified and explained at the methodological part of each chapter of this dissertation. 3.4 workloads and performance evaluation In order to evaluate how our proposals affect the behavior of a wide range of CMP systems, two different types of workloads have been set up. A first group of workloads is composed by multiprogrammed workloads made of sequential applications from the SPEC CPU 2006 suite of benchmarks. A second group of workloads is composed by parallel applications from the suites PARSEC [5] and SPLASH-2 [66]. 3.4.1 Multiprogrammed In a multiprogrammed workload, as many sequential applications as cores the system has, are running at same time. This kind of work- 3.4 workloads and performance evaluation 29 loads represents scenarios we can find from our desktop, where a web browser is running at the same time that a video player, to a server, where applications of very different nature run at the same time. The employed multiprogrammed workloads are composed by applications from among all the 29 included in the SPEC CPU 2006 benchmark suite. Applications were firstly run until completion in a native machine. Their initialization phases where identified by using hardware counters. Groups of eight applications were randomly chosen to form workload mixes. Once in simics, the applications forming a workload mix were executed together, binding each application to a core in order to avoid migration effects. A number of instructions as long as the longest initialization phase of the applications composing the workload mix was fast-forwarded. At that point a checkpoint was taken. The average number of MPKI each application shows at the moment of taking the checkpoint at each cache level of the hierarchy is shown in Table 3.2, it is the average for all the mixes where each application appears. In order to evaluate a microarchitectural proposal in a given workload mix, its corresponding checkpoint is read from Simics. Then, the ruby module is loaded with the configuration which mimics the proApplication L1 L2 LLC Application L1 L2 LLC perlbench 3.7 0.8 0.6 povray 11.0 0.3 0.3 bzip2 8.2 4.3 2.1 calculix 13.8 3.7 1.5 gcc 21.8 7.1 6.2 hmmer 2.9 2.2 1.7 bwaves 20.3 19.6 19.6 sjeng 4.2 0.5 0.5 gamess 75.3 46.2 28.6 GemsFDTD 25.8 25.7 21.6 mcf 22.9 22.2 18.1 libquantum 36.6 36.6 36.6 milc 21.6 21.6 21.5 h264ref 3.5 0.7 0.6 zeusmp 12.3 6.4 6.3 tonto 4.88 0.86 0.52 gromacs 8.71 5.91 5.91 lbm 68.1 39.2 39.2 cactusADM 13.9 1.4 0.7 omnetpp 7.3 4.4 1.2 leslie3d 29.5 18.1 17.7 astar 6.9 0.9 0.7 namd 1.4 0.2 0.1 wrf 4.1 1.6 0.5 gobmk 9.5 0.5 0.4 sphinx3 13.8 8.0 6.3 dealII 2.3 0.3 0.3 xalancbmk 8.2 7.0 6.4 soplex 6.7 5.8 4.8 Table 3.2: Average MPKI at each cache level 30 experimental framework posal to study. The whole hierarchy is then warmed, normally during 300M cycles, after that, statistics are cleaned and performance accounting starts. The duration of the simulation is given in system cycles, during this thesis we have normally used 700M cycles long simulations. The metric considered to evaluate the behavior of the different proposals when multiprogrammed workloads are employed is the geometric mean of the speedup of each application appearing in the workload mix. Given that duration of simulations is fixed and equal for all the proposals, what is employed in order to calculate speedups are the number of executed instructions. Equation 3.1 formally shows this metric. Speedup =n v u u t n Y i=1 IA i Ibase i (3.1) IPCA i: Number of executed instructions of program i when run in system A IPCbase i: Number of executed instructions of program i when run in baseline system 3.4.2 Parallel The parallel applications evaluated in this thesis are five applications of SPLASH-2 [66] and PARSEC [5] suites. The first one is a very well known benchmark suite of scientific parallel programs, while the second focuses on emerging workloads and was designed to be representative of next-generation shared-memory programs for chipmultiprocessors. Table 3.3 gathers the applications we selected for our evaluation. They are those applications from both suites having more than 1 MPKI in a 8-MB SLLC. Each application spawns in its parallel phase as many threads as processors are in the system. We utilize simmedium input set for PARSEC applications and a 1026x1026 grid for Ocean. Performance statistics are only taken in the parallel phases. Parallel applications should be run until completion when meaningful results are desired, or at least some work-oriented metric should be considered [1]. In our simulations we have observed that no 4.1 introduction 37 To the best of our knowledge, our contribution is the first work where prefetch is studied in a multicore system fitted with a banked shared LLC, see Figure 4.1b. We assume an LLC organized in independent cache banks with an access port each, and an interconnection network attaching cores to cache banks (a crossbar is assumed, but other topologies can be considered) [28,30]. Each bank is internally sub-banked in order to provide a higher throughput. This kind of SLLC is already mainstream because independent banks add layout flexibility and increase access bandwidth. Commercial processors from AMD, Sun, Intel, or IBM are using this design [11,28,30,32]. In this scenario, we introduce the ABS controller, an Adaptive controller for prefetch in a Banked Shared LLC. ABS controllers are installed in all the LLC banks which are already fitted with a prefetch engine. Each ABS controller runs autonomously and gather local statistics to set the prefetch aggressiveness for each core in the bank it controls in order to maximize the overall system performance using a hill-climbing approach. Therefore, a given core is allowed to prefetch with different aggressiveness on different banks of the LLC. Isolation between banks is a key factor of our proposal, meaning that both the ABS controller and the prefetcher in a bank are not influenced by their peers at other banks. Bank isolation achieves two essential benefits, namely i) the prefetches generated from a given bank target itself, and it will always be possible to filter useless prefetches by looking up in the bank, thus saving memory bandwidth, and ii) communicating prefetchers or ABS controllers among banks is not required, removing the need for a dedicated interconnection network or extra traffic in the existing one. As discussed in Section 4.5.2, bank isolation can be achieved by selecting a proper address interleaving among banks or by adjusting the prefetch distance. Our results show that an eight-core system with ABS controllers running multiprogrammed SPEC2K6 workloads improves in both user-oriented metrics and system-oriented metrics over a baseline system with a fixed degree sequential prefetch. The results are consistent when varying the number of cores or LLC sizes. ABS control can be applied to other prefetch engines as long as they are able to operate at different aggressiveness levels. Specifically, we introduce ABScontrolled sequential streams. A comparison with HPAC-controlled sequential streams, such as that proposed by Ebrahimi et al. [15], shows higher performance at a very small fraction of the cost. Furthermore, when running multithreaded workloads from SPLASH-2 38 abs prefetching [66] and PARSEC [5], the ABS controllers also reduce the execution time and the consumed bandwidth over the baseline system. The remaining of the chapter is structured as follows. Section 4.2 describes the motivation behind the work. Section 4.3 gives some background and reviews related work. Section 4.4 introduces the ABS controller. Section 4.5 presents the prefetch framework. Section 4.6 shows the methodological differences respect to what was presented in Chapter 3. Section 4.7 shows the results when ABS controllers are evaluated in a variety of situations, and Section 4.8 discusses and summarizes the contribution. 4.2 motivation Figure 4.2 shows instructions per cycle (IPC) for eight SPEC2K6 applications running on a system with eight cores and a 4MB shared LLC. The simulation details are shown in Section 4.6. The figure shows four bars for each application. The first two bars represent programs running alone in the system, either without prefetch or with an aggressive (degree 16) sequential tagged prefetch (see Section 4.3). The last two bars represent the eight applications running together, either all without prefetch or all with the former aggressive prefetch turned on. When comparing the systems with prefetch (second and fourth bars), significant performance losses appear when resources are shared among cores. Note that prefetch involves virtually no performance loss in any application when running alone (first and second bars), while it causes losses in 5 out of 8 applications when running all together (third and fourth bars). Therefore, in order to boost the shared LLC performance by means of prefetch, a mechanism to control aggressiveness is called for. Such a mechanism should consider global metrics to realize when the prefetch activity of a core harms the overall system performance and it should be decreased in spite of the improvement achieved by that core. As figure 4.2 highlights, the benefit obtained by an application due to prefetch can decrease or even turn into losses if prefetch is simultaneously active in all cores. Therefore, our goal is to design a mechanism that dynamically controls the prefetch aggressiveness of each core in order to maximize system performance. The impact on system performance can be assessed using global indexes such as aggregated IPC or shared LLC miss ratio. Both are 4.3 background and related work 39 Figure 4.2: IPC for eight SPEC2K6 applications (mix2) running on an 8-core system with a shared LLC obtained by adding quantities that are distributed in the cores or the cache banks, respectively. So, a centralized design of the prefetch aggressiveness control requires sending information from the places where events are counted to the centralized control point. Alternatively, we propose to place an ABS controller in each LLC bank. The controller uses bank-local information (i.e. bank miss ratio) to improve bank performance. Improving the performance of every bank will thus improve the system performance. 4.3 background and related work This section provides with material will be useful in next sections. First, Section 4.3.1 explains the concept prefetching aggressiveness that will be used in next sections. And second, Section 4.3.2 presents the Hierarchical Prefetcher Aggressiveness Control (HPAC), to the best of our knowledge, the only proposal in the literature with the aim of controlling the prefetching aggressiveness associated to each core in a CMP. 4.3.1 Prefetch aggressiveness Prefetch aggressiveness is often defined in terms of degree and/or distance. Let us consider a stream of references a processor is going to demand (ai,ai+1,ai+2, ...), where address aihas just been issued. A prefetcher can be designed to produce the next kaddresses following ai(ai+1, ...ai+k), calling kthe prefetch degree. Alternatively, or in addition, it can also be designed to produce a single address of a far reference (ai+d), calling dthe prefetch distance. As an example, we recall the sequential tagged prefetcher with degree k[14]. If reference 40 abs prefetching aihaving the line address Vis going to trigger a burst of prefetches (aimisses or is the first use of a prefetched line), then the prefetcher will issue the following request burst (V+1,V+2, ..., V+k). Another example of a prefetch engine using aggressiveness is the sequential streams as presented in [58]. In that work, aggressiveness was defined as a combination of distance and degree. 4.3.2 Hierarchical Prefetcher Aggressiveness Control (HPAC) To our knowledge, only the Hierarchical Prefetcher Aggressiveness Control (HPAC) presented by Ebrahimi et al. [15] has faced the problem of adjusting prefetch aggressiveness on a shared LLC. We notice four main differences between that work and the present one: 1. While HPAC resorts on computing the prefetching aggressiveness by means of a set of rules applied to several system variables (a kind of fuzzy controller), while ABS relies on a local search method (a variant of hill-climbing) to minimize a single system variable, the bank miss ratio. 2. HPAC was proposed for a centralized LLC with a single access port (see Figure 4.1a). We propose ABS for a cache organized in banks, each one with an access port (see Figure 4.1b). 3. HPAC throttles auto-regulated prefetch engines attached to each core. In the original paper, HPAC is evaluated using Feedback Directed Prefetching as the auto-regulated prefetch engine [58]. However, ABS controllers set directly the aggressiveness level of the local prefetchers. 4. HPAC uses four global metrics and FDP (as part of HPAC) uses three more local metrics. All these metrics are monitored and compared to ten thresholds (4 for HPAC + 6 for FDP). In contrast, ABS only samples two system variables and only considers one threshold. A performance and complexity comparison between HPAC and ABS is presented in Section 4.7.4. 4.4 the abs controller 41 4.4 the abs controller An ABS controller is an adaptive mechanism that sets dynamically the aggressiveness associated to each core on the prefetcher installed in a bank of a banked shared LLC. Every LLC bank has an ABS controller commanding the prefetcher of that bank. Thus the ABS controller of an LLC bank is able to associate different levels of prefetch aggressiveness to each core, and conversely ABS controllers in different banks can associate to the same core different levels of prefetch aggressiveness. ABS control relies on a hill-climbing approach for finding the minimum of a function (the miss ratio of a bank1) that we assume to be dependent on a set of variables namely, the prefetching aggressiveness of each core in the bank. Time is divided into regular intervals called epochs. In each epoch, in order to establish a cause-effect relationship between change in aggressiveness and change in performance, the aggressiveness of only one core (the probed core) is varied. The point is that at each epoch, the observed change in the bank miss ratio is only due to a single aggressiveness change. At the end of the epoch an aggressiveness value is established for the currently probed core and this value remains unchanged until it is probed again. Furthermore, ABS controllers force the prefetch aggressiveness associated to a core to be decreased if its accuracy falls under a given threshold. The operation of ABS controllers involves two aspects: i) selection of the core to probe and temporal sampling, and ii) adaptive per-core aggressiveness control. core selection and temporal sampling At the beginning of each epoch a core is chosen in a round-robin fashion2and its current prefetch aggressiveness is changed. Then, at the end of the epoch, the effect of the change is evaluated by comparing the bank miss ratios observed during the current epoch and a reference epoch (Figure 4.3a). The change is undone if the current bank miss ratio is greater than the reference one. Otherwise, the change is confirmed and the current epoch is set as the new reference. So, the core se1 Ratio of bank demand misses to demand requests coming from all cores. Other performance indexes were also tested as the target function, such as global miss ratio, MPKI, or IPC. Although results were similar, these other indexes were discarded because they are more expensive to compute in terms of communication and hardware cost. 2 A random order was also tested achieving slightly worse results. 42 abs prefetching lection and temporal sampling guarantee that there is always only one prefetch aggressiveness change between reference and current epochs. That change corresponds to the probed core at each epoch. At the end of an epoch, an aggressiveness value is established for the currently probed core and this remains unchanged until the core is probed again. Note that if an application remains in a stable phase the ABS controller reaches a steady state only broken by the glitches involved in testing sub-optimal configurations. Hill-climbing processes usually deals with functions that are not time-dependent. Thus, the process stops when no change can be found to improve the value reached. However, we know miss ratio is time-dependent because applications change their behavior over time. This has two important implications for the design of ABS. 1. Our algorithm never stops. The combination of aggressiveness able to minimize the miss ratio changes over time and ABS continually seeks that combination. 2. When the miss ratio reaches the global minimum in the corresponding program phase, ABS will set the current epoch as the reference epoch and the current miss ratio as the rate to beat. So, as a lower miss ratio will no longer appear, ABS will never change the control actions, and worse, a similar behavior may occur during long program phases after reaching a local minimum. In order to remedy this situation, the number of epochs elapsed without updating the reference epoch is counted. When this count is equal to the number of cores, the mechanism sets the last epoch as the new reference. Updating the reference epoch in this way ensures that a new value is taken after probing all cores without experiencing a miss ratio decrease. We use epochs of 32K cycles. Other durations were tested without significant variation. Epochs based on counting a given number of events, like cache misses, were also tested without significant variations. adaptive per-core miss-gradient aggressiveness control In an ABS controller, every core has a state which consists of a prefetch aggressiveness degree and a prefetch aggressiveness trend (downward or upward). At the beginning of the epoch in which a core is being probed, the state changes to eval-downward or eval-upward 4.4 the abs controller 43 (a) Core selection and temporal sampling (b) Finite state machine controlling the per-core prefetch aggressiveness Figure 4.3: ABS controller operations (Figure 4.3b). Note that to probe a core, ABS only changes the aggressiveness following the trend associated with the core, instead of testing both possibilities (downward and upward) as they would do other implementations of hill-climbing. Four events are locally counted in each LLC bank during each epoch, namely: 1) bank accesses from all cores, 2) misses from all cores, 3) prefetches issued by the core being probed, and 4) hits from the core being probed on prefetched lines. Sequential tagged prefetch uses a bit per cache line to tag the prefetched lines. This bit is set when a line is loaded in the LLC by a prefetch, and it is reset when the line is used for the first time. We use this bit to count the hits of the probed core on prefetched lines. At the end of an epoch two ratios are computed: bank miss ratio (bank misses / bank accesses) and prefetch accuracy for the core being probed (hits from the core in prefetched lines / prefetches from the core). Then the computed bank miss ratio is compared with the bank miss ratio of the reference epoch. If it has increased, the state changes to the reverse trend (from eval-downward to upward or from eval-upward to downward). 44 abs prefetching Otherwise, the state changes to the initial trend and the reference bank miss ratio is updated. Accuracy is involved in the transitions that leave the eval-x states. It is required that the probed core has an accuracy higher than a threshold to go to the upward state. The rationale of this requirement is to avoid the increase in the aggressiveness of one core whose prefetches are almost useless. We have observed that the optimal threshold depends on the intrinsic accuracy of the prefetch engine. Aggressive prefetch engines such as sequential tagged need a higher threshold (more restrictive) than other more conservative prefetch engines like sequential streams. We use an accuracy threshold of 0.6 when controlling sequential tagged with variable degree and of 0.3 when controlling sequential streams. 4.4.1 Example Figure 4.4 shows an example of how an ABS controller works in an LLC bank of a system with four cores. The degree scale (0, 1, 4, 8, 16) represents the prefetch aggressiveness. Time moves from left to right and is divided into fixed length intervals as shown in the Epoch row. The four rows designated as degree & trend (P0, P1, P2 and P3) show the level of prefetch degree and trend associated with each core at each epoch. For instance, 4↑means prefetch degree of 4 and upward trend. The core identifier and its trend over the dashed arrows indicate the change applied between two consecutive epochs. For example, from E0 to E1 the degree of P1 is changed from 4 to 1. The bank miss ratio accounting row shows the miss ratio at each epoch. The last row shows the comparison result between the reference and the current bank miss ratios. Next we show the positive and the negative cases. positive aggressiveness change At the beginning of E1, aggressiveness of the P1 core is changed from degree 4 to 1 following its downward trend. The question mark next to the degree of P1 at E1 epoch (1?) means that the change is being evaluated. At the end of E1 we observe a decrease in the bank miss ratio (a>b) with respect to the reference epoch (a). Therefore, the change in degree and the current trend of P1 are confirmed. E1 becomes the new reference epoch. The same happens at the epochs E2 and E5. 4.4 the abs controller 45 Figure 4.4: Example of ABS controller working in an LLC bank of a 4-core system negative aggressiveness change White circles surround negative evaluations. At the beginning of E3, the P3 degree is changed from 4 to 8 following its upward trend. At the end of E3, an increase in the bank miss ratio (c<d) is observed, therefore the change in the P3 degree is undone, becoming 4, and its trend is reversed to downward. The reference epoch is not changed. At the beginning of E4, the P0 degree is changed from 1 to 4. Note that E2 is the reference epoch in E4. They only differ in the degree of P0, which is the one under evaluation in E4. At the end of E4 the bank miss ratio is also higher than it was at E2. Therefore, the change in the P0 degree is undone, the trend is reversed, and E2 remains as the reference in E5. 4.4.2 Miss ratio as a good metric to guide aggressiveness Prefetch related metrics such as coverage, accuracy, timeliness, pollution or consumed bandwidth have often been proposed to evaluate the quality of a prefetch engine because an aggregate figure such as the miss ratio does not allow the net effect of individual prefetches to be distinguished [46,63]. These same metrics were subsequently used in other works to guide prefetch aggressiveness [14,15,58]. However, these metrics are not directly related with system performance. Moreover, in the context of a banked LLC they pose two important problems: i) some of them are hard to compute online, and ii) they are difficult to aggregate in a single number in order to take a decision. In this contribution we use the LLC bank miss ratio as the main metric to guide prefetch aggressiveness. The penalty of the off-chip misses is large in processor cycles and so a miss ratio decrease has a great potential to reduce Cycles per Instruction (CPI) and improve performance. Therefore, we expect the LLC miss ratio to be a good measure of performance. Moreover, the ABS controller associated 46 abs prefetching with each LLC bank can locally count the number of misses in the bank. In consequence, our proposal establishes the feedback loop without requiring communication among LLC banks. From a performance standpoint, the prefetch related metrics are highly correlated with the miss ratio. In fact, some of these metrics are only valuable when they really correlate with the miss ratio. For instance, a prefetched line is considered useful if it is used along its lifetime in a cache, and useless otherwise (accuracy metric). However, a useful prefetch does not always have a positive impact on performance. Indeed, it will only increase performance if it gets a reduction in the miss ratio. In particular, if the line evicted by the prefetch is referenced before the prefetched line itself, despite having a useful prefetch, the miss ratio does not change and therefore no performance increase will be seen. 4.4.3 ABS controller hardware cost The hardware cost of our proposal is low. In each bank, an ABS controller needs 4 bits per core in order to keep its prefetch state (1 bit for trend + 3 bits for aggressiveness level). It also needs four 16-bit counters (bank misses, bank accesses, prefetch requests, and hits on prefetched blocks). Additionally, it needs a 3-bit counter (4 bits in a 16core system) to maintain the reference epoch age (number of epochs without changing the reference). The reference and the current miss ratios are stored in 16-bit registers. Finally, a 15-bit counter is needed to divide time into 32K-cycle epochs. For instance, in an 8-core multiprocessor each ABS controller needs 146 bits. Thus, in our baseline system fitted with 4 LLC banks, 584 bits are needed. If we consider a 16-core system with the same memory hierarchy, 716 bits are needed by the four ABS controllers. Most prefetchers add to every cache line a tag bit in order to detect first use after prefetch and then react based on the prefetchless miss stream3[45,54]. For instance, sequential tagged prefetch uses the tag bit to trigger new prefetches on the first use of a prefetched line. The ABS controller uses the same tag bit to count hits on prefetched lines, and so we ignore that bit in the ABS costs. 3 Given two equal caches, with and without prefetch, note that the miss stream outgoing from the prefetch cache differs from that of the prefetchless cache. However, it is possible to rebuild the prefetchless miss stream in a prefetch cache by joining the actual miss stream with the first-use stream of prefetched blocks. 4.6 methodology 53 In order to evaluate the performance of the system when it is controlled by our ABS controllers, we use two system-oriented performance indexes, namely weighted speedup (eq. 4.1) [39], and main memory bandwidth consumption, and two user-oriented performance indexes, namely harmonic mean of speedups (eq. 4.2) [55], and fairness (eq. 4.3) [44]. Next, these metrics are shown with more detail. First, we define IPCSP i: IPC of program i running alone in the system and with fixed degree-16 sequential tagged prefetch. IPCMP i: IPC of program i when other applications run in the rest of the cores weighted speedup (ws)It quantifies the number of jobs completed per unit of time [16]. Here it represents the sum of slowdowns that each of applications experiments because the competition. It is expected that all the terms in the summation are lower than 1, thus the value of the metric is between 0and n, and the higher the better. WS = n X i=1 IPCMP i IPCSP i (4.1) harmonic mean of speedups (hs)It is the inverse of the average normalized turnaround time [16]. Apart from adding the speedups that each of applications experiments, it captures the effects of competition, reflecting fairness more intensely than WS. It is expected that all the terms in the summation are higher than 1, thus the value of the metric is between 0and 1, and the higher the better. HS =n Pn i=1 IPCSP i IPCMP i (4.2) memory bandwidth It is accounted in order to know how much the different prefetch control schemes stress the links with main memory. We express it as a fraction between 0and 1reflecting the average occupancy of the links between the SLLC and the main memory. 54 abs prefetching fairness (fa)To determine whether the co-execution in the multicore system benefits or harms some programs more than others we use the fairness index (FA) [44]. The value of the metric is between 0and 1, and the higher the better. FA =min(IS1,IS2,...,ISn) max(IS1,IS2,...,ISn),where ISi=IPCMP i IPCSP i (4.3) 4.6.4 Prefetch specific metrics Next sections will also show how well prefetching is performing, thus specific metrics will be used. Concretely, our interest will focus on two different metrics: coverage (eq. 4.4) and accuracy (eq. 4.5). As these metrics are used in an example to gain insight on the prefetch behavior, both will be only used in a per-application way within a multiprogrammed context. Next, these metrics are shown with more detail. First, we define Fi=First hit on lines prefetched by application i coverage (cov)It represents the fraction of misses prefetch is able to avoid. Equation 4.4 shows the definition of coverage for the prefetch associated to application i. The value of the metric is between 0and 1, and the higher the better. Covi=Fi Fi+Mi ,(4.4) Where, Mi=Misses of application i accuracy (acc)It expresses the fraction of prefetches that are actually used by the processor. Equation 4.5 shows the definition of accuracy for the prefetch associated to application i. The value of the metric is between 0and 1, and the higher the better. Acci=Fi Pi (4.5) Where, Pi=number of prefetches issued by application i 4.7 results 55 4.7 results In this Section we evaluate the ABS controllers. Section 4.7.1 analyzes ABS controlling sequential tagged prefetch in the baseline system. Section 4.7.2 shows results for 16-core systems. In Section 4.7.3 we increase the LLC size. In Section 4.7.4 ABS controllers are compared with a previous proposal, and in Section 4.7.5 they are evaluated using parallel applications. 4.7.1 Results for the 8-core baseline system Figure 4.6 shows the results of ABS controlling prefetch aggressiveness of the mix2 described in Section 4.2. The 8 programs run simultaneously and the bars corresponding to execution without prefetch (8apps no pref) and with fixed-degree (16) aggressive prefetch (8apps pref) are kept. A new bar corresponding to ABS prefetch (ABS) is added. ABS controlled prefetch increases performance compared with the aggressive fixed degree prefetch in all programs. IPC improvement ranges from 23% in sphinx3 to 40% in milc. With regard to the system without prefetch, ABS control only slightly affects the performance of deall and povray, while the aggressive prefetch leads to significant losses in five of the eight programs. In contrast, in six of the eight programs ABS control outperforms the system without prefetch, achieving improvements between 3% in omnetpp and 225% in lbm. Global measures such as IPC do not allow us to find out how prefetching is working. To give insight into prefetching behaviour, Figure 4.7a and Figure 4.7b show prefetch coverage and accuracy, reFigure 4.6: IPC for eight SPEC2K6 applications (mix2) running on an 8-core system with a shared LLC 56 abs prefetching (a) Prefetch accuracy (b) Prefetch coverage Figure 4.7: Prefetch accuracy and coverage of sequential tagged prefetching with fixed degree of 16, and variable ABS-controlled degree (mix2). spectively, comparing fixed degree (8apps pref) with ABS-controlled degree (ABS). Prefetch coverage is very uneven across applications, ranging from about 0.1 in povray to more than 0.9 in cactus. ABS, despite being less aggressive, gets coverage similar or even higher than the fixed 16-degree prefetcher. ABS coverage is clearly better in five of the eight applications, and is clearly worse in two. As for accuracy, it is also uneven across applications, being very close to zero in povray and very close to one in cactus. But here ABS is the clear winner, achieving higher accuracy in all applications, highlighting the cases of milc,povray,tonto,omnetpp and sphinx3. The combination of both metrics, similar coverage and better accuracy, explains the performance improvement obtained by ABS. It is interesting to delve into how different the aggressiveness computed in each bank by the replicated ABS controllers can be. Figure 4.8 plots a temporal trace of the prefetch degree for application milc in the mix2, in a prefetch system under ABS control in two of the four LLC banks (bank 0 and bank 1). The failed tests (glitches), accounting for 1/ 8 of the total time in the worst case, have been removed to smooth the plot. 4.7 results 57 Figure 4.8: Evolution of the prefetching aggressiveness level for the milc application (mix2) in two of the four LLC banks during 160 tests In the plotted sample, both ABS controllers usually take different control decisions; e.g. at time 1180, bank 0 prefetchs with degree 2, while bank 1 uses degree 8. The plot shows the flexibility of the distributed ABS control: a particular core may issue a miss stream with a different pattern into each LLC bank. Figure 4.9 shows HS, WS, FA and consumed bandwidth for systems without prefetch (no pref), with fixed-degree aggressive prefetch (aggr pref), and under ABS control (ABS) for the ten mixes shown in Table 4.1. In each plot the rightmost bar group is the average of the 30 mixes (AVG30). The HS values show a nonuniform pattern across the different mixes (Figure 4.9a). Aggressive prefetch increases by 4% the average HS with respect to no prefetch, but causes losses in six of the 10 mixes. Under ABS control, prefetch improves in 9 of the 10 mixes (up to 60% in mix6) and produces small losses in the other mix (0.5% in mix9). Also, ABS control always increases performance compared to no prefetch, between 20% and 50% in mix3 and mix6, respectively. On average, prefetch under ABS control, improves the system without prefetch by 35%. In terms of WS (Figure 4.9b), aggressive prefetch causes losses in seven of the 10 mixes and performs on average 3% worse than the system without prefetch. ABS control improves aggressive prefetch in 9 of the 10 mixes (up to 47% in mix4) and produces negligible losses in the other mix (1% in mix9). On the other hand, prefetch under ABS control improves the system without prefetch in 9 of the 10 mixes, with improvements ranging from 14% in mix9 to 27% in mix3. In mix5, 58 abs prefetching (a) Harmonic mean of speedups (b) Weighted speedup (c) Fairness (d) Bandwidth consumed Figure 4.9: Results for ten mixes of SPEC2K6 applications running on an 8core system with a shared LLC 4.7 results 59 WS results in a reduction of 0.3%. On average, prefetch controlled by ABS improves the system without prefetch by 18%.6 Figure 4.9c plots the FA values, showing that the system with aggressive prefetch is significantly more fair than the system without prefetch. This is because the performance indexes use as reference a system with prefetch as we have seen in Section 4.6.3. Therefore, in the system without prefetch we see the unfairness introduced by the lack of prefetch itself, plus the unfairness due to the interferences among the eight cores. In Figure 4.9c, we observe the low fairness of mix2 in the system without prefetch. As the HS index includes some notion of fairness in its definition and WS is a pure throughput index, the previous issue about mix2 becomes clear. On average, the system using ABS controllers is more fair than the system with aggressive prefetch (0.62 and 0.56, respectively). ABS controllers make the system more fair in 6 of the 10 mixes (differences between 1% and 140%), and less fair in the remaining 4 (differences between -3% and -30%). Finally, in Figure 4.9d we see that the main memory bandwidth consumption of the system without prefetch is very uneven among the different mixes, varying between 18% and 55% of the maximum bandwidth. However, the common pattern is that aggressive prefetch greatly increases bandwidth consumption with respect to the system without prefetch (on average, from 40% to 85% of maximum bandwidth), and ABS removes a significant portion of that increase lowering it to 70% of maximum bandwidth. Summarizing, in an 8-core chip with a shared 4-MB LLC, the use of ABS controllers improves the system that is using uncontrolled aggressive prefetch. On average, throughput (WS), the inverse of the turnaround time (HS), and fairness (FA) increase 27%, 23% and 11%, respectively while memory bandwidth consumption decreases by 18%. 4.7.2 Results for a 16-core system In this section we analyze the behaviour of prefetch in a 16-core system. The LLC is not modified, so that the increase in the number of cores results in an increased pressure on the LLC. However, commu6 Notice that the performance indexes HS and WS do not always correlate; in mix2, for instance, the HS index indicates that aggressive prefetch is better than no prefetch while the WS index indicates the contrary. The discussion on fairness will give a deeper insight into what is happening. 60 abs prefetching (a) System-oriented metrics (b) User-oriented metrics Figure 4.10: ABS performance on a 16-core system nication with the main memory is expanded from one to two DDR3 channels. We run 30 mixes of 16 applications randomly selected among the 21 SPEC CPU 2006 shown in Table 4.1. We only present the average of each index over the 30 mixes of 16 programs each. Figure 9.a combines in a single Y-X plot the system-oriented metrics, WS and bandwidth, while Figure 9.b combines the user-oriented metrics, HS and FA. In a system with 16 processors, fixed-degree (16) aggressive prefetch (aggr pref) produces losses compared to no prefetch (no pref) in terms of throughput (WS decreases 9%) and turnaround time (HS decreases 4%). The memory bandwidth consumption greatly increases from 36% to 85%. Only fairness improves from 0.28 without prefetch to 0.36 with aggressive prefetch. Controlling aggressiveness leads to improvements in all metrics. Compared to aggressive prefetch, ABS control (ABS) increases the HS index by 27% (22% compared to no prefetch), increases the FA index to 0.48, and also improves the system throughput index with a WS increase of 25% (14% compared to no prefetch). The bandwidth consumption decreases significantly compared to aggressive prefetch, from 85% to 62% of the maximum, but it is still greater than without prefetch which only requires 36% of the maximum. Summarizing, in a 16-core chip with a shared 4-MB LLC, ABS improves the system in all indexes. Comparing between 16 and 8 cores, the increase in the WS index is similar but the improvement in the rest of the indexes, HS, fairness and memory bandwidth, is much higher. This result is consistent because the pressure on the memory hierarchy in a 16-core chip is larger than in an 8-core, resources are more scarce, and therefore controlling the prefetch aggressiveness becomes more important. 4.7 results 61 (a) System-oriented metrics (b) User-oriented metrics Figure 4.11: ABS performance on an 8-core system with an 8MB LLC 4.7.3 Doubling the LLC size In this section we analyze the behaviour of prefetch in the 8-core baseline system when doubling the LLC size to 8 MB. We only show average indexes computed over the 30 mixes already used in section 4.7.1. The system-oriented metrics WS and bandwidth, are shown in Figure 10.a, while Figure 10.b shows the user-oriented metrics HS and Fairness. In an 8-core chip with a shared 8-MB LLC, the use of ABS controllers also improves the behavior of uncontrolled aggressive prefetch. On average, throughput (WS), the inverse of the turnaround time (HS), and fairness (FA) increase 18%, 24% and 38%, respectively while memory bandwidth consumption decreases 14%. When increasing the cache size, controlling the prefetch aggressiveness becomes less important for improving performance, but it improves fairness and saves bandwidth. Thus, when increasing from 4 to 8 MB, ABS improvements over uncontrolled prefetch change from 27% to 18% in WS, from 11% to 38% in FA, and from 18% to 14% in BW. As for HS, the results are similar. 4.7.4 HPAC comparison Next we compare the ABS control with the Hierarchical Prefetcher Aggressive Control mechanism (HPAC) introduced in [15]. To the best of our knowledge, this was the only work to date on adjusting prefetch aggressiveness in a shared LLC. 62 abs prefetching HPAC works in a centralized LLC with a single access port although internally it is organized in banks to support several concurrent accesses. The proposal uses sequential streams as the prefetch engine and a local control of aggressiveness for each core: FeedbackDirected Prefetching (FDP) [58]. HPAC adds a global interference feedback in order to coordinate the prefetchers of the different cores and throttle their aggressiveness. Since we assume autonomous LLC banks, possibly placed at distant die locations, distributing HPAC is not straightforward. We choose a distributed implementation giving HPAC as much knowledge and control as possible, namely each core has an FDP per LLC bank, and each LLC bank has an HPAC controlling the corresponding FDP. So, the distributed HPAC/FDP we test requires 32 FDPs (8 FDPs per bank ×4 banks = 32 FDPs), and 4 HPACs (1 HPAC per bank ×4 banks = 4 HPACs). Besides other local bank metrics, HPACs gather statistics from one/two memory controllers (8/16 core systems), and the communication among HPACs and the memory controllers is modelled in an ideal way (zero-delay/no BW limitations). We have used the thresholds indicated in the published proposals for both mechanisms. We simulate 32 streams per core and LLC bank (32 streams ×8 cores ×4 banks = 1024 streams). Each stream launches sequential prefetches with a degree and distance from a starting address. We implement five levels of aggressiveness that correspond to degrees 1, 1, 2, 4, and 4 and distances 1, 4, 16, 32, and 64, respectively. The aggressiveness control mechanism (HPAC/FDP or ABS) decides the aggressiveness level associated to each core. Figure 4.12 plots the results for HPAC and ABS on an 8-core system. Both mechanisms use sequential streams as the prefetch engine. Performance indexes have been computed using as references the IPCs of the programs running alone on a system with a sequential stream prefetcher with a fixed level of aggressiveness (distance 64 and degree 4). We only show average indexes computed over the 30 mixes already used in Section 4.7.1. Figure 4.12a shows the system-oriented metrics, WS and BW, while Figure 4.12b shows the user-oriented metrics, HS and Fairness. ABS control obtains better results than HPAC in all metrics except in the consumed bandwidth. ABS improves WS index by 8%, HS index by Part III EXPLOITING REUSE LOCALITY This third part of the dissertation treats the reuse locality at the SLLC. It comprises two chapters: Chapter 5states the reuse locality property and presents two replacement algorithms that exploit such property. Chapter 6presents the reuse cache, an innovative solution to improve the SLLC efficiency. Employing the reuse locality, the reuse cache is able to dramatically downsize the SLLC data array, but maintaining at the same time CMP average performance untouched. 5 REUSE LOCALITY summary Optimization of the replacement policy used for shared last-level cache (SLLC) management in a chip-multiprocessor (CMP) is critical for avoiding off-chip accesses. Temporal locality is exploited by first levels of private cache memories, thus it is slightly exhibited by the stream of references arriving at the SLLC. Therefore, traditional replacement algorithms based on recency are bad choices to govern SLLC replacement. Recent proposals involve SLLC replacement policies that attempt to exploit reuse either by segmenting the replacement list or improving the re-reference interval prediction. On the other hand, inclusive SLLCs are commonplace in the CMP market, but the interaction between replacement policy and the enforcement of inclusion has been barely discussed. After analyzing that interaction, this chapter introduces two simple replacement policies exploiting reuse locality and targeting inclusive SLLCs: Least Recently Reused (LRR) and Not Recently Reused (NRR). NRR and LRR have the same implementation cost that NRU and LRU, respectively. Our proposals are evaluated by simulating multiprogrammed workloads in an 8-core system with two private cache levels and a SLLC. LRR outperforms LRU by 4.5% (performing better in 97 out of 100 mixes) and NRR outperforms NRU by 4.2% (performing better in 99 out of 100 mixes). We also show our mechanisms outperform re-reference interval prediction, a recently proposed SLLC replacement policy and similar conclusions can be drawn by varying the associativity or the SLLC size. 71 72 reuse locality 5.1 introduction In order to reduce the average latency of memory accesses, a hierarchy of cache levels is essential. In a multicore chip, the memory hierarchy usually contains one or two levels of private cache and a shared last-level cache (SLLC). A key task of the cache hierarchy is to exploit the locality usually found during program execution. Specifically, under a demand-fetch policy, the exploitation of locality is directly related to the replacement algorithm at every level of the hierarchy. Traditionally, each of all the memory hierarchy levels employs algorithms that consider temporal locality in order to select the cache line to replace. In particular, least-recently used (LRU) is a widespread replacement algorithm. It predicts that a recently accessed line (either hit or miss) will be used again soon. LRU gives good results on firstlevel caches because the complete stream of references from the processor is observed but, as many previous authors have shown, it has poor performance as a replacement policy for SLLCs [21,35,47,59]. Private caches exploit short-distance reuses. Frequently, they even satisfy all the accesses to a given line and, in this cases, the SLLC only receives the initial miss request. From the SLLC standpoint these are single-use lines. Therefore, using a recency-based replacement policy such as LRU is not efficient in the SLLC: in spite of retaining singleuse lines is useless, LRU will insert those lines in the most recently used (MRU) stack position, maximizing their stay. Moreover, in the case of a multicore chip running a multiprogrammed workload the replacement inefficiency may be amplified by interference between programs. A program with a harmful memory access pattern (i.e., a burst of single-use lines) may prevent other programs exploiting reuse opportunities and there may be large accumulated losses in performance. Although the reference stream observed by the SLLC may exhibit little temporal locality in the conventional sense, it does exhibit reuse locality. The concept underlying this type of locality can be described as follows: lines accessed at least twice tend to be reused many times in the near future and, moreover, recently reused lines are more useful than those reused earlier. That is, in reuse locality future references are only expected after the first hit to a line. In contrast, with temporal locality there is an expectation of future references straight after the first reference to a line, a miss. However, only a few lines in the SLLC have reuse locality. Indeed, most lines in the SLLC are dead, 5.1 introduction 73 and they will not receive any further references during their lifetime [25,31,47,68]. Reuse locality has been identified and exploited in cache memories for disks. A representative proposal modified the LRU algorithm in order to protect reused pages against access patterns that result in poor performance such as thrashing or scanning [24]. On the other hand, recent research in SLLC replacement policies relies on predicting the re-reference interval [17,23,26,67]. According to the predicted rereference interval, the utility assigned to each line in these schemes can take one of several values. In contrast, as the reuse locality is a binary property, the derived replacement policies will only require two utility1values: to keep or not to keep. In addition, most proposals consider non-inclusive SLLCs [17,21,26, 47,67], meaning that the lines present in the private caches may or may not reside in the SLLC [3]. Several commercial processors have instead an inclusive SLLC that always keeps a superset of the contents of private caches [20]. This choice greatly simplifies the cache coherence protocol, and is usually implemented by invalidation. When an SLLC line is evicted, inclusion is enforced by sending invalidation messages to all the copies present in the private caches, if any [3,8]. However, another replacement inefficiency arises when the replacement of an inclusive SLLC is managed by an LRU-based policy: a heavily referenced line with a short reuse distance may remain in private caches for a long time. During this time this hot line, despite being actively accessed by the core, may move down in the LRU stack of the SLLC, to the point of being evicted. This will force invalidation of the line in the private cache, though the processor will request the line again producing a new SLLC miss [22]. In this chapter, we show that recency-based replacement algorithms such as LRU and NRU can be adapted with minor modifications to take advantage of reuse locality rather than temporal locality. Our work introduces two replacement policies for inclusive SLLCs: least recently reused (LRR) and not recently reused (NRR). They try to retain in the SLLC the lines present in the private caches and the reused lines. Both policies are built upon two simple assumptions about line behavior. First, lines present in the private caches are being used by the running programs. Thus, these lines will be the last to be evicted. Second, a small subset of lines have reuse locality. Therefore, 1 Utility in this context is associated with the probability of a line being used in the future. 74 reuse locality these lines are valuable and, when it is necessary to select a victim among them, the reuse order will provide a basis for the selection. With the LRR and NRR policies, lines are replaced as follows: first, lines neither present in the private caches nor showing reuse (nonreused lines) are evicted at random; if there are none of these, a line not present in the private caches but reused (reused lines) is evicted; and, finally, if there are none of these, a victim line is selected from the private caches (being-used lines), this last case occurring relatively rarely. Under the LRR policy, the lines are ordered depending on their last hit. That is, a least recently reused stack of lines is maintained in each SLLC set. Thus, lines belonging to the reused group are totally ordered (following the LRR order), while there is no relative order among the elements of the non-reused group. The LRR policy has the drawback of the implementation cost increasing with the square of the set associativity. Also based on recency, the not recently used (NRU) algorithm is an inexpensive alternative to LRU ordering [43]. Indeed, it is used in the SLLC of commercial processors, such as the Intel Itanium or Sun SPARC T2, and by using only one bit per line, the NRU cost increases linearly with the set associativity. The NRR policy we propose adapts the NRU algorithm for tracking reuse in SLLC sets. Under this NRR policy, every line is provided with a NRR bit. In contrast with NRU, the reuse bit will be unset only on hits, not on line refilling. Accordingly, all the not recently reused lines are victim candidates (NRR bit set) and the remaining lines are not. The proposals are evaluated in an eight-core system with two private cache levels and an inclusive SLLC. By running a rich set of multiprogrammed workloads, we show that LRR outperforms LRU by 4.5%, and NRR outperforms NRU by 4.2% with exactly the same cost. We also show that our mechanisms outperform re-reference interval prediction (RRIP) [23], a recently proposed SLLC replacement policy. Similar conclusions can be drawn for a range of associativity values and SLLC sizes. The chapter is structured as follows. Section 5.2 presents experimental evidence of reuse locality and the usefulness of not evicting the SLLC lines present in private caches. Section 5.3 presents a state of art proposal that is evaluated along our contributions and compared with them. Section 5.4 explains the LRR and NRR replacement 5.2 motivation 75 milc wrf dealII hmm. dealII omn. libq. gob. APKI - 1 app 27.41 0.98 0.15 2.09 0.14 4.26 30.77 0.36 MPKI - 1 app 27.37 0.03 0.01 0.02 0.01 1.90 30.77 0.08 APKI - 8 apps 27.64 1.16 0.33 2.15 0.31 4.31 30.77 0.65 MPKI - 8 apps 27.63 0.53 0.27 1.14 0.27 3.38 30.77 0.46 Table 5.1: Number of SLLC accesses and misses per kilo-instruction of each application in the #91 mix, APKI and MPKI, respectively policies, giving details of the implementation and associated costs. Section 5.5 reports and discusses the evaluation of our contributions, and finally, Section 5.6 discusses about the contributions exposed on this chapter. 5.2 motivation In this section, we analyze the behavior of an example application from one of the evaluated workload mixes (mix #91) running in the hierarchy of a multicore chip made up of an SLLC and private caches. We highlight three effects, namely, i) by sharing the SLLC space, the working set of an application spreads towards distances greater than the cache associativity; ii) the principle of inclusion may force hot lines in the private levels to be invalidated, but private caches will request the line again straight away; and iii) most SLLC hits come from sustained reuse among a small subset of lines. The selected mix is composed of eight applications of the SPEC CPU 2006 benchmark suite and runs in an eight-core CMP system with an inclusive SLLC. The first two rows of the Table 5.1 show the number of SLLC accesses and misses per thousand instructions, when the programs run alone. We can observe very different behaviors. For instance, dealII seems to fit well in the private caches and barely access the SLLC (0.15 APKI) and hmmer almost always hits in the SLLC (2.09 APKI and only 0.02 MPKI), while milc and libquantum access the SLLC many times (27.41 and 30.77 APKI, respectively) and almost always miss. Figure 5.1 plots the number of wrf hits in a set-associative SLLC as a function of the LRU stack distance under three different boundary conditions (gray or black bars). The horizontal axis represents 64 LRU stack distances in the SLLC; the first 16 distances belong to real cache storage while the next 48 distances are tracked using shadow tags. 76 reuse locality the working set may spread beyond the available storage In a CMP, different applications share the SLLC and compete for placing their working set into the cache. The lines of an application are displaced in the LRU stack by the lines inserted into the same set by other applications. Figure 5.1a shows the LRU stack when wrf runs alone in the CMP (it has the whole SLLC to itself). It can be observed that all the hits arise at a distance of 1 to 8 (0.95 HPKI overall), and there are no additional hits that a larger cache could capture. Now let us consider Figure 5.1b, which plots the hit distances of wrf when it runs along with the other seven applications shown in Table 5.1. We can see that the bars are smaller and spread over much longer LRU distances than before (from distance 1 to 16, 0.63 HPKI overall). This is because other applications such as libquantum or milc load a large number of lines which in turn displace the wrf 0 10 20 30 40 50 60 Stack distance 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 HPKI wrf alone (a) 0 10 20 30 40 50 60 Stack distance 0 0.05 0.1 0.15 HPKI wrf in mix 91 (b) 0 10 20 30 40 50 60 Stack distance (reused) 0 0.05 0.1 0.15 HPKI wrf in mix 91 (c) Figure 5.1: Distribution of hits along the LRU stack (HPKI = hits per thousand instructions) in three experiments; the vertical line signals the associativity of the used SLLC cache: a) wrf running alone in the CMP, b) wrf running with 7 other applications in an inclusive (bars) and in a non-inclusive (solid line) SLLC, and c) wrf running with 7 other applications in a non-inclusive SLLC (reuse stack) 5.3 re-reference interval prediction (rrip) 77 lines (see LLC MPKIs in Table 5.1). Consequently, the MPKI of wrf in a 16-way associative SLLC increases from 0.03 when running alone to 0.53 when running together with other applications. cache inclusion plus high sllc miss ratios mean hot line thrashing Hot lines, those lines with a sustained core reuse remain silently in private caches for a long time and, therefore, they may become stale in the LRU stack of the SLLC. Before replacing a hot line in the SLLC, the copies present in the private caches are invalidated, but as they are being used by the core, misses will occur and the private caches will request these lines again straight after the invalidation. In Figure 5.1b, we can see a peak at a distance of 17 followed by significant number of references at 17-20, meaning that the core is requesting recently invalidated lines. The solid line crossing the aforementioned peak is the distribution of LRU stack distances for a non-inclusive SLLC (from distance 1 to 16, 0.71 HPKI overall). The non-inclusive SLCC performs better because, even though it may be evicting the same hot lines as the inclusive counterpart, they are not invalidated in the private levels. the reused lines fit within the associativity Figure 5.1c shows the distribution of the LRU stack distances for a noninclusive SLLC calculated in the following way. LRU stack entries are tagged as reused lines when the first hit occurs, and all the remaining lines (non-reused) are ignored when calculating the stack distance. By doing this, we can see how the distance distribution of the reused lines concentrates at the top positions, without exceeding a distance of 10. This indicates that if the SLLC replacement policy were focussed on keeping the cache lines that can be expected to be reused, SLLC performance would be significantly improved. 5.3 re-reference interval prediction (rrip) Jaleel et al. [23] proposed Re-reference interval prediction (RRIP); a state of art SLLC replacement policy. It involves a modified LRU that considers a chain of segments where all the cache lines in a segment are supposed to have the same re-reference interval value (RRPV) . This RRPV is represented by an N-bit counter which is associated to each cache line to classify it into one of 2Nsegments. 78 reuse locality RRPV 0 RRPV 1 RRPV 2n-2 RRPV 2n-1 insertion victim promotion on hit (a) Overview SRRIP state II II a2 a2b2 b2c2 a2 b2c2 a0 b2c0 a0 b2c0 a0e2 f2c1 a1e3 miss miss miss hit hit miss miss 3333 I I I 333 I I 3 3 I3 I3 I3 RRPV ref a b c a c e f (b) Example Figure 5.2: Static re-reference interval prediction (SRRIP) replacement algorithm The authors of the mechanism proposed two versions of the algorithm: Static-RRIP (SRRIP) and Dynamic-RRIP (DRRIP). In Static-RRIP (Figure 5.2a), new lines are inserted into the segment corresponding to intermediate re-reference interval (segment with a RRPV equal to 2N-2) making the algorithm scan-resistant. When a line has a to be selected as victim, a line with RRPV equal to 2N-1 is randomly chosen, if there is no any, the RRPVs of all the elements are increased by one and the search is performed again. Figure 5.2b shows the behavior of the SRRIP algorithm when an example stream (a, b, c, a, c, e, and f) of references arrives to a determined set of the cache. Each row represents the state of the set before the reference in column ref accesses the cache. We can observe the content of each element of the set along with its RRPV value and if the access was either a hit or a miss. As an example of the algorithm behavior, we will examine the last line of the figure. Let’s have a look first at the previous line, the penultimate, faccesses to the cache, resulting on a miss. Looking to the last line of the example again, we can observe three different things, i) the RRPV values of all the elements in the set have increased by one, ii) bwas evicted and iii) fhas been inserted with a RRPV equal to 2. Dynamic-RRIP uses set dueling to select between SRRIP and Bimodal. Bimodal is a Thrash-resistant policy that inserts lines with long re-reference interval (segment with a RRPV equal to 2N-1) but a small fraction of randomly chosen lines that are introduced with 5.5 evaluation 85 Figure 5.4a shows NRU, TA-DRRIP, TA-DRRIP+, NRR, and LRR performance relative to LRU for the program mix used as an example in Section 5.2. The rightmost group of bars is the geometric mean of individual speedups. LRR improves LRU performance for all the applications in the mix, while NRR has the same effect with respect to NRU. TA-DRRIP is the only algorithm that causes losses in some applications (milc), while TA-DRRIP+ is better than TA-DRRIP in six of the eight applications and eliminates losses. On average in this mix, our proposals perform better than the other algorithms tested. Figure 5.4b shows, for each application in the example mix, the percentage reduction in the number of misses achieved for each mechanism relative to LRU replacement. As it can be observed in the figure, LRR achieves the greatest reduction in all applications. NRR is the second best mechanism in six of the eight applications, and DRRIP in the other two (hmmer and omnetpp). Furthermore, DRRIP is the most irregular mechanism. First, it gets a much smaller reduction in the two instances of the application deall. Also, DRRIP does not achieve any reduction in milc and libquantum. These two applications have high miss ratios, pointing to a possible thrashing behavior. DRRIP correctly recognizes the lack of reuse and acts easing the eviction of their cache lines. However, our mechanisms work with a finer grain, identifying the few lines showing reuse, and giving them higher priority than the rest. As a result, NRR and LRR manage to reduce misses even in these applications (LRR eliminates 1.8% and 2.7% of misses, while NRR eliminates 0.5% and 1.6% in libquantum and milc, respectively). Figure 5.5a plots all the 100 mixes on the horizontal axis. The different mixes are sorted by the LRR speedup over LRU. In the same way, Figure 5.5b plots NRR performance relative to NRU. LRR outperforms LRU in 97 mixes out of 100, while NRR is better than NRU in all but one of the mixes. Figure 5.6 shows the mean performance of NRU, TA-DRRIP, TADRRIP+, NRR, and LRR relative to LRU for the one hundred workload mixes. On average, LRR improves LRU performance by 4.5%, while NRR outperforms NRU by 4.2%. On the other hand, TA-DRRIP and TA-DRRIP+ increase LRU performance by 3% and 3.3%, respectively. 86 reuse locality 0 20 40 60 80 100 0.95 1.00 1.05 1.10 1.15 Performance over LRU LRR performance for all the mixes (a) LRR compared to LRU 0 20 40 60 80 100 0.95 1.00 1.05 1.10 1.15 Performance over NRU NRR performance for all the mixes (b) NRR compared to NRU Figure 5.5: Relative performance for all the mixes evaluated NRU TA-DRRIP TA-DRRIP+ NRR LRR 0.95 1.0 1.05 1.1 Speedup over LRU Figure 5.6: Summary of speedups 5.5 evaluation 87 0 10 20 30 40 50 60 Set Stack position 0.00 0.02 0.04 0.06 0.08 0.10 HPKI mix 91 - wrf Figure 5.7: Stack profile for wrf with LRR as replacement policy 5.5.2 LRR/NRR behavior LRR and NRR are intended to cause lines that will not be reused to be removed from the cache. It is interesting to explore the degree to which this expectation is met, and also to understand how the dynamic evolution among line groups explains the observed behavior. Therefore, we consider below the resulting stack profile under LRR, and the temporal evolution of the classification of lines in a sample set of the SLLC. Figure 5.7 shows again the stack profile of Section 5.2 for mix #91 under LRR. As can be seen, hits are concentrated towards the top of the stack, almost always at a distance of less than 16. Thus, by applying LRR, the SLLC is effectively keeping the cache lines likely to be reused, and this is why the SLLC performance improves. The NRR policy, not illustrated in the figure produces a similar behavior. Figures 5.8 and 5.9 plot the evolution of the number of lines classified as being-used, non-reused, and reused (from bottom to top) in a sample SLLC set, over a short period of execution of mix #91, with LRR and NRR as replacement policies, respectively. Under LRR, the boundary between reused and non-reused lines moves down each time a line is reused for the first time. As we pointed out in Section 5.4.1, this single-direction movement is counteracted every time a hit occurs on a reused block (the block moves to the being-used group), and each time a new block is loaded into the cache set (miss) and all the non-reused lines in that cache set are also being-used. 88 reuse locality 0! 2! 4! 6! 8! 10! 12! 14! 16! 1! 201! 401! 601! 801! reused! non-reused! being-used! Figure 5.8: Temporal evolution of the group sizes in a cache set when LRR is used 0! 2! 4! 6! 8! 10! 12! 14! 16! 1! 201! 401! 601! 801! reused! non-reused! being-used! Figure 5.9: Temporal evolution of the group sizes in a cache set when NRR is used 5.5 evaluation 89 Under NRR, when all the not-being-used lines become reused, the replacement algorithm itself converts all of them but one to nonreused lines. That is to say, when all the not-being-used lines have the reused bit set, then NRR unsets it for all of them except the line receiving the last hit. This behavior can be clearly seen at times 201 and 601 in Figure 5.9. 5.5.3 Individual applications analysis To obtain insight into how the replacement algorithms affect individual applications, Figure 5.10 shows the distribution of speedups by application. The number of mixes in which each application appears is shown along the top of the graph. For each replacement policy (TA-DRRIP, LRR and NRR) five speedups are plotted, namely the minimum, the first quartile, the median, the third quartile, and the maximum. For the mix #91, we saw (in Figure 5.4) how TA-DRRIP improved the performance of several applications, but also reduced it in one case (milc). In Figure 5.10, we note that this behavior is quite common. In 24 out of the 29 applications, TA-DRRIP performs worse than LRU in some multiprogrammed mixes, whereas LRR and NRR reduce this number to 12. Therefore, it can be concluded that reuse-based replacement is more fair than TA-DRRIP. The imbalance introduced by TA-DRRIP may be due to the control mechanism deciding which replacement algorithm is used for each application. Specifically, TA-DRRIP uses Set Dueling [47] to identify the best suited replacement policy for each application, dynamically choosing between scan-resistant SRRIP and thrash-resistant BRRIP [23]. That is, if an application greatly reduces its miss rate with a given configuration, even at the cost of increasing the misses of other applications, the configuration that benefits itself will prevail. On the other hand, the average speedup we obtain with DRRIP seems to be lower than that reported by the authors. We believe that the explanation may lie in the different methodological approaches used. They model a four-core system with a 4 MB SLLC, executing a varied workload, among which there is only a subset of five SPEC 2006 applications. Therefore, in the next experiment we simulate that system and run the five mixes of four applications resulting 90 reuse locality 1.0 1.1 1.2 1.3 27 27 35 32 23 30 35 30 19 28 20 28 33 28 25 30 29 26 16 25 31 30 24 30 31 31 23 28 26 1.50 0.88 0.84 0.89 0.73 0.89 2.14 2.05 1.57 1.0 1.1 1.2 1.3 2.00 1.98 1.51 perlbench bzip2 gcc bwaves gamess mcf milc zeusmp gromacs cactusADM leslie3d namd gobmk dealII soplex povray calculix hmmer sjeng GemsFDTD libquantum h264ref tonto lbm omnetpp astar wrf sphinx3 xalancbmk 1.0 1.1 1.2 1.3 1.92 1.94 LRR NRR TA-DRRIP Figure 5.10: Distribution of speedups relative to LRU for all applications 5.5 evaluation 91 NRU TA-DRRIP NRR LRR 0.95 1.0 1.05 1.1 Speedup over LRU Figure 5.11: Performance comparison for five mixes of a SPEC2K6 subset in a four-core system from combining the applications of the same SPEC 2006 workload (cactusADM,sphinx3,hmmer,mcf and bzip2). Figure 5.11 shows the average speedup of NRU, TA-DRRIP, NRR and LRR over LRU for the five aforementioned mixes. Notably, in comparison to Figure 5.6, TA-DRRIP increases its speedup the most (from 1.02 to 1.04). 5.5.4 Hardware complexity The NRR algorithm requires one bit per cache line (as shown in Subsection 5.4.3), while DRRIP requires N bits per cache line, being N the number of bits required to classify lines in segments. The aging logic for NRR is simpler than that of DRRIP. DRRIP aging requires incrementing the counters of all the lines in a set, whereas NRR aging only requires resetting the reuse bits to the lines not present in the private caches (using the presence bit vector). Moreover, TA-DRRIP requires a per-thread policy selection counter, and the logic for choosing a set dueling monitor. This logic decides whether a miss occurs or not in the (sampled) sets belonging to the monitor of the corresponding thread. 92 reuse locality 8-assoc 16-assoc 32-assoc 0.96 0.98 1.00 1.02 1.04 Performance over LRU a) Cache associativity sensivity 4MB 8MB 16MB 0.96 0.98 1.00 1.02 1.04 Performance over LRU b) Cache size sensivity NRU TA-DRRIP TA-DRRIP+ NRR LRR Figure 5.12: Sensitivity to the cache associativity and cache size 5.5.5 Sensitivity to the SLLC associativity In this section, we explore the sensitivity of reuse-based replacement to cache associativity, testing the values 8, 16 and 32. The cache size is kept constant at 8 MB. Figure 5.12a shows three groups of bars for the three cache associativities. Each group have five bars which represent NRU, TA-DRRIP, TA-DRRIP+, NRR and LRR mean performance relative to LRU. The speedup with respect to LRU decreases with increasing associativity. LRR shows the best performance in all the associativities, while the low-cost proposal, NRR, is the second best option for associativities 16 and 32. 5.5.6 Sensitivity to the cache size In this section, we consider the sensitivity of reuse-based replacement to cache size, testing the values 4, 8 and 16 MB. The cache associativity is kept constant at 16. 5.6 concluding remarks 93 Figure 5.12b shows three groups of bars for the three cache sizes. Each group have five bars which represent the mean performance of NRU, TA-DRRIP, TA-DRRIP+, NRR and LRR relative to LRU. The speedup with respect to LRU decreases for both 4 and 16 MB cache sizes. Moreover, for a 4 MB cache, all replacement algorithms lead to poorer performance than LRU except LRR. LRR gives the best performance in all the cache sizes, while the low-cost proposal, NRR, is better than TA-DRRIP for 4 MB and 8 MB caches. 5.6 concluding remarks Private cache levels filter short-distance reuses, and thus the SLLC of a CMP observes a stream of references that may have very little temporal locality. On the other hand, these references may have reuse locality. The concept of reuse locality can be described as follows: lines accessed at least twice tend to be reused many times in the near future and, moreover, recently reused lines are more useful than those reused earlier. Further, a heavily referenced line with a short reuse distance may remain in private caches for a long time, steadily losing position in the LRU stack and eventually being evicted. Thus, if an SLLC follows an inclusive scheme such hot lines will be invalidated and fetched again and again. Consequently, traditional replacement algorithms based on recency such as LRU and NRU are poor choices for inclusive SLLCs. In this chapter, we have shown how to adapt these algorithms to take advantage of reuse locality rather than temporal locality. We have proposed two simple replacement policies for inclusive SLLCs that exploit reuse locality: least recently reused (LRR) and not recently reused (NRR). Both policies are intended to retain in the SLCC the lines present in the private caches as well as the reused lines. In contrast with previous studies that select the application subset sensitive to the replacement algorithm, our proposals have been evaluated by running a rich set of multiprogrammed workloads created from all SPEC CPU 2006 applications. For an eight-core system with two private cache levels and an inclusive SLLC, we have found that LRR outperforms LRU by 4.5% (97 out of 100 mixes) and NRR outperforms NRU by 4.2% (99 out of 100 mixes). A detailed comparison with RRIP [23], a recent SLLC replace- 94 reuse locality ment proposal, indicates that LRR and NRR give 1.5% and 0.89% better performance, respectively. Additionally, we have shown that our algorithms are more fair than TA-DRRIP and that similar conclusions can be drawn considering a range of different associativity values and SLLC sizes. Unlike previous proposals, which require prediction mechanisms or use several algorithms and dynamically select the best one through techniques such as set-dueling, LRR and NRR have costs similar to replacement algorithms implemented in commercial processors. NRR has the same implementation cost as NRU, and LRR only adds one bit per line to the LRU cost. 6.3 the reuse cache design 101 will be loaded in the data array. On the other hand, tag replacement is designed to protect both private cache lines and recently reused lines. In the following sections, we discuss the reuse cache organization and replacement policies, present an example coherence protocol, and discuss the hardware costs of our proposal. 6.3.1 Organization The reuse cache breaks the implicit one-to-one mapping between tag and data found in conventional caches. Previous work proposes to decouple tag and data arrays having the same [9], or different number of entries [48,50,52,69]. Decoupling with the same number of entries allows both arrays to be shaped differently, for instance enabling the concept of distance associativity [9]. In any case, all proposals rely on relating the entries of both arrays by means of pointers. Some proposals need only forward pointers from the tag array to the corresponding data lines, if any [9,50,69]. Other proposals need only a reverse pointer which links each data line to the corresponding tag [52], while some others require both kind of pointers [48]. An alternative organization, which allows to eliminate pointers, uses the same number of sets in tag and data arrays and associates data to only a few tags for each set. The association between tags and data is fixed (for instance, only the tag in way 0 has an associated data). This organization involves moving tags between the ways with and without data [37,69]. In the reuse cache, a tag may have an associated data line or not. A particular coherence state identifies every possible situation, and aforward pointer and a reverse pointer relate one other the entries of both arrays. Figure 6.2 shows an overview of the reuse cache organization. As the forward pointer indicates the exact position of a line in the data array, no additional lookup in the data array is required. Thus, the data array can be as associative as desired. The data array associativity is only related to the replacement in the data array. By increasing associativity, the replacement algorithm has more options to choose a victim. The data array associativity also has a small impact 102 reuse cache = = hit? tag Way-0 Way-n set # tag physical address byte hit? set Way-0 Way-n statetag fwd. pointer valid rev. pointer repl. bit Data TAG ARRAY DATA ARRAY Figure 6.2: Reuse cache overview on hardware cost. By increasing associativity, the size of the pointers stored in tag and data arrays also increases. Section 6.3.3 will detail the data array organization and Section 6.3.5 and Section 6.4.1 analyzes the influence of the data array associativity in the reuse cache size and performance, to conclude that the impact of data array associativity is very limited both in cost and performance. 6.3.2 Tag Replacement Policy A key benefit of decoupling is to specialize replacement, that is, to order and evict tags and data separately on the basis of their different roles. Any replacement policy may work in the reuse cache tag array if it fosters the presence of reused lines and takes into account inclusion and the tradeoffs it brings [22]. In this contribution we adopt not recently reused (NRR) (Section 5.4.2), a replacement policy based on not recently used (NRU) [43]. Both have the same implementation cost, one bit per line. In NRR, the Non-Recently Reused NRR bit, distinguishes recently reused lines from not recently reused ones. When a line is loaded into the SLLC due to a miss, its NRR bit is set (it has not been recently reused). When there is a hit (a reuse), the NRR bit is unset. NRR uses the full-map directory bits to distinguish among lines present or not in the private caches. Victim lines are randomly selected among lines having the NRR-bit set and not included in the private caches. 6.3 the reuse cache design 103 Name Cache Memory Data I Invalid or not present - No S Unmodified up-to-date Yes M Modified stale Yes TO Only tag, no data up-to-date or stale No (a) States of TO-MSI protocol Event name Description GETS Data read or fetch request GETX Write request UPG Upgrade request PUTS Eviction notification (clean) PUTX Eviction notification (dirty) DataRepl Eviction in the Data array (b) Events of TO-MSI protocol Table 6.1: States and events of the TO-MSI example coherence protocol 6.3.3 Data array: organization and replacement policy The data array associativity is only related to the replacement in the data array. An associative search in the data array is never necessary because the forward pointer in the tag array indicates the set and way in the data array. We assume a number of sets in the tag array greater or equal than in the data array, using in both arrays the least significant bits of the line address as set index. Therefore, a forward pointer only has to indicate the way of the data array where the line is, while a reverse pointer has to show the way of the tag array as well as the bits of the tag array index not included in the data array index (log2the number of tag array sets bits - log2the number of data array sets bits). For instance, a data array with only one set (fully associative) requires for each forward pointer log2the number of data array entries bits. Reverse pointers require log2the number of tag array entries bits. Only reused lines are allocated in the data array. Thus, in order to exploit reuse locality, replacement should rely on recency. Given our low-cost design goal, we use NRU as the data array replacement algorithm. However, the NRU performance decreases for high associativities. Thus, for the fully associative case, a suitable alternative we have tested is the low-cost Clock algorithm introduced by Cor- 104 reuse cache ITO S GETS M GETX UPG GETX DataRepl Stable states New stable states Transitions inserting a line into the data array Transitions not affecting the data array *A tag replacement always finishes at I state Transitions removing a line from the data array DataRepl GETS GETX GETX GETS PUTX GETS PUTS Tag-only state Tag+data states UPG PUTX PUTS Figure 6.3: Functional description of the TO-MSI example coherence protocol bató [12]. The implementation cost of both NRU and Clock is one bit per line. Under Clock replacement the data array of the reuse cache works as a circular queue2. Each line in the circular queue has an associated bit called the used bit. This bit is unset when the line is inserted into the data array and it is set when the line is read (the line receives ahit). When a line is inserted into the data array, the replacement algorithm selects the oldest line as the victim. If the circular queue is full and the victim line is valid and has the used-bit set, this line is promoted to the first position and its used bit is unset. This operation only requires the queue pointer to be incremented and it can be carried out in the background after an insertion. We observed that normally there is a small number3of victim lines to promote but the victim search can be stopped if an insertion arrives before finding a victim. When evicting a data line, the corresponding forward pointer in the tag array has to be invalidated. This corresponding tag array entry is located by following the reverse pointer of the just invalidated line (Figure 6.2). 2 Given that tag array replacement may force the invalidation of data array entries, "holes" may appear in our simple circular queue implementation. The effect of these has been measured and is minimal. 3 This number is, on average, lower than 2. 6.3 the reuse cache design 105 6.3.4 TO-MSI: an example coherence protocol Conventional coherence protocols assume that each line present in a cache has an entry in both the tag and data arrays. However, a reuse cache needs a coherence protocol able to deal with lines that have entries in the tag array but not in the data array. Figure 6.3 outlines an example coherence protocol based on the MSI protocol4[13], which is able to work with decoupled tag and data arrays. Table 6.1 explains the states and events of the protocol. In this description, neither replacement nor the external requests are represented. In every state except I, private caches may have copies of the line or not. This information is stored in a full-map directory by using a presence bit vector. Two different groups of states can be considered: tag+data states contain lines in the data array; and tag-only (a single state in this simplified version of the protocol) contains lines that are not present in the data array. Transitions between both groups always imply lines getting in or out of the data array. 1) From tag-only to tag+data. When the first SLLC hit (reuse) is observed the state changes from tag-only to a state of the tag+data group. These transitions are represented by dash-dotted arrows in the figure and are caused by GETS and GETX events when the state of the line is TO. 2) From tag+data to tag-only. When a line is evicted from the data array the state changes from the tag+data group to tag-only. Replacing a line in the data array requires the protocol to record that the tag no longer has associated data. The dashed arrows labelled with the DataRepl event, coming out of M and S, represent these state transitions. 4 For the sake of clarity, a simple protocol is shown here. In our evaluation, we rely on a MSI-MOSI protocol with seven stable states. This protocol allows interconnection between several CMPs. The reuse cache needs three additional stable states to track the tag-only situations. 106 reuse cache Component Conv. 8MB RC-4/1 Fullyassoc. RC-4/1 16assoc. Tag 21 22 22 Coherence 4 5 5 Full-map vector 8 8 8 Replacement 1 1 1 Fwd. pointer - 14 4 Total tag entry (bits) 34 50 40 Data 512 512 512 Valid - 1 1 Replacement - 1 1 Reverse pointer - 16 6 Total data entry (bits) 512 530 520 Tag array (K entries) 128 64 64 Data array (K entries) 128 16 16 Total size (Kbits) 69888 11680 10880 Reduction 83.3% 84.4% Table 6.2: Hardware cost 6.3.5 Hardware Cost In this section, we compute the reduction in the total number of bits, by taking into account both the tag/data array reduction and the increase due to the forward and reverse decoupling pointers. As an example, for an eight-core system we detail a 8 MB conventional cache and a reuse cache with a 1:8 scaling in the data array and a 1:2 scaling in the tag array. We consider a 16-way and a fully associative data array organizations for the reuse cache. The conventional cache is 16-way associative, and has 64-byte lines. Further, the conventional cache requires 34 bits per line in the tag array: 21-bit tags (assuming 40 bits of physical address space in a 64bit architecture), 12-bit coherent state (4-bit state and 8-bit presence vector) and 1 bit for replacement (NRU algorithm5). The data array requires 512 bits per line. Overall, the conventional cache needs 69888 Kb (see Table 6.2). 5 Although LRU has been used as the replacement policy of the conventional cache in Section 6.4, NRU has been considered here to not bias the comparison. 6.4 evaluation 107 The reuse cache has a 1 MB data array and a tag array with the same number of entries than a 4 MB conventional cache (RC-4/1 in the Table 6.2 headings). A tag array entry requires the same fields as a conventional cache plus a forward pointer per line and one additional bit for the coherence state6. The forward pointer requires 14 bits for the fully associative (16K-line) data array but only 4 bits for the 16-way data array. Each data array entry requires 512 bits of data, a reverse pointer, one bit for the replacement policy (Clock/NRU), and one valid bit per entry. The reverse pointer requires 16 bits for the fully associative data array (4 and 12 bits to store way and set, respectively) but only 6 bits for the 16-way data array (4 and 2 bits to store way and set index, respectively). Overall, the reuse cache (4 MB tag array / 1 MB data array) with fully associative data array needs 11680 Kb while the reuse cache with 16-way data array needs 10880 Kb. Thus, the set-associative organization of the data array requires a 6.8% less bits than the fully associative. Regarding the 8MB conventional cache, the example reuse cache with fully associative data array would require only a 16.7% of its storage capacity (15.6%, considering the set-associative data array). 6.4 evaluation In order to perform the evaluation, we have employed the methodology showed in Chapter 3. Concretely, next sections show results for 100 multiprogrammed workload mixes and the parallel applications were shown in Section 3.4.2. We first compare the performance of the reuse cache varying the data array size and associativity. We then study the optimal size ratio between tag and data arrays. In Section 6.4.3 and Section 6.4.4 we give insight into the reuse cache behavior by analyzing the percentage of lines not entering in the data array and the number of live lines when reducing the reuse cache size. Next, in Section 6.4.5 we compare the reuse cache with DRRIP [23], a state of the art replacement algorithm, and NCID [69], a recent proposal of a decoupled tag-data cache. Finally, in Section 6.4.6 we analyze the behavior of the reuse cache when running parallel applications. 6 We consider the coherence protocol that supports our proposal roughly doubles the original in number of states, and thus add on one additional bit. 108 reuse cache Throughout this section, results are expressed as speedups of the different reuse cache configurations relative to a baseline SLLC. The baseline SLLC considered is an 8 MB, 16-way conventional cache with LRU replacement. When describing the reuse cache tag array, we use MBeq as the tag array equivalent to that of a 1 MB conventional cache. We always maintain a tag array associativity of 16 and a line size of 64 bytes. For instance, a 4 MBeq tag array has 64K tags (4 MB / 64) organized in 4K sets (64K tags / 16). We use RC-x/y to refer to a reuse cache with a tag array equal to that of a x MB conventional cache (x MBeq) and a data array of y MB. As an example, RC-4/1 is the reuse cache outlined in Table 3, having a tag array equivalent to a 4 MB conventional cache with 1 MB data array. With respect to a conventional cache with the same number of sets, the access time of the tag array increases due to the added forward pointer and the mux to select the pointer, see Figure 6.2. However, when comparing reuse and conventional caches, both the tag and data arrays of reuse caches are always smaller than those of conventional caches7. Thus, we consider that the access time of the evaluated reuse cache configurations does not increase with respect to the conventional cache with which it is compared. Also, we assume the same latency in all reuse cache configurations, although the access time decreases significantly as the sizes of the tag and data arrays decrease. 6.4.1 Data array size and associativity Figure 6.4 shows performance of a reuse cache with 8 MBeq tag array and varying the data array size from 4 MB (RC-8/4) to 512 KB (RC8/.5) and the data array associativity among 16, 32, 64, 128 and fully associative. Each bar represents average performance relative to the baseline for the 100 workloads mixes. In general, performance varies very slightly and unevenly for associativities between 16 and 128. The reuse cache with fully associative data array achieves better results for all sizes. However, the differences are not significant. For instance, the difference between a 167 In the performance comparisons we vary the number of tag sets, and only one of the cases shows a number of sets equal for the reuse and conventional caches. However, this case has never been chosen as a suitable design point. 6.4 evaluation 109 RC-8/4 RC-8/2 RC-8/1 RC-8/0.5 0.9 0.95 1.0 1.05 1.1 Perf. over conv. 8MB 16-assoc 32-assoc 64-assoc 128-assoc FullyAssoc Figure 6.4: Average speedup over the baseline for reuse caches of various data array sizes and associativities. Tag array size and associativity are 8 MBeq and 16, respectively. way associative and fully associative varies from -0.1% for RC-16/8 and +1% for RC-4/1. We can conclude that the fully associative and the set-associative organizations are very similar both in cost and performance. It is important to remember that the fully associative organization is easy to implement because it never needs associative lookups. Further, the clock replacement algorithm is really simple, being even cheaper than NRU in a set-associative organization with a high associativity. Unless noted, the remaining experiments are carried out with fully associative data arrays. Regarding the size of the data array, a reuse cache with one quarter the capacity of the baseline cache (RC-8/2) shows on average even better performance than the baseline cache (+ 2.4%). A further reduction in the data array, RC-8/1, marks a turning point with the reuse cache performing slightly worse than the baseline cache (-0.5%). 6.4.2 Tag array size In this section we study the tag array size that achieves the best performance for each size of the data array. Figure 6.5 shows the relative performance of a reuse cache with respect to the baseline 8 MB cache. For each size of the data array (X axis), we consider several different sizes of the tag array. In each configuration, the tag array must have more entries than the maximum of the data array and the sum of entries in the private caches (8x256 KB). In order to extend the comparison to a 16 MB conventional cache, we will also include a reuse cache with a 8 MB data array. 110 reuse cache RC-X/8 RC-X/4 RC-X/2 RC-X/1 RC-X/0.5 0.9 0.95 1.0 1.05 1.1 1.15 Perf. over conv. 8MB 8 163264 4 8 1632 2 4 8 16 2 4 8 16 2 4 8 16 conv. 16MB conv. 8MB conv. 4MB Figure 6.5: Average speedup over the baseline for reuse caches variyng the tag and data array sizes. Tag array associativity is 16. 0%! 20%! 40%! 60%! 80%! 100%! 120%! RC-16/8!RC-8/4!RC-8/2!RC-4/1!RC-4/0.5! Hardware cost respect to conv. 8MB! Figure 6.6: Storage budget of the best reuse caches, relative to a conventional 8 MB cache. For a given data array size, increasing the size of the tag array beyond a certain limit is not worthwhile, because it only leads to identifying a larger reuse working set, whose size is beyond the capacity of the data array. The optimum data-tag ratio is always 4 except for a 512 KB data array, where a ratio of 4 requires a 2 MBeq tag array, which is the minimum for tracking the aggregated 2 MB of private caches. Besides, the small performance advantage of RC-32/8 over RC-16/8 would not justify selecting the 32 MBeq tag array. The same holds true between RC-16/4 and RC-8/4. Hence, for the remaining sections, the reference sizes of the reuse cache replacing a conventional 8 MB cache will be: RC-8/4, RC-8/2, RC-4/1 and RC-4/0.5. Figure 6.6 shows the total number of bits of those reuse caches relative to a conventional 8 MB cache; RC-16/8 has been added for completeness. We can choose RC-4/1 as the smaller reuse cache performing better than a conventional 8 MB cache; indeed, RC-4/1 requires half the tags, one-eighth the data, and only spends 16.7% storage of the conventional 8 MB cache. 6.5 concluding remarks 117 blackscholes canneal ferret fluidanimate ocean 0.85 0.9 0.95 1.0 1.05 1.1 Speedup over baseline RC-8/4 RC-8/2 RC-4/1 RC-4/0.5 Figure 6.12: Speedup of reuse cache over the baseline for five parallel applications, with data array sizes from 4 MBytes (RC-8/4) to 512 KBytes (RC-8/0.5) suites which have more than 1 MPKI in the baseline SLLC. Specifically, the selected applications are blackscholes,canneal,ferret, and fluidanimate from PARSEC and ocean from SPLASH-2; their MPKIs are 4.5, 3.5, 1.3, 1.7, and 13.4, respectively. We utilize the simmedium input set for PARSEC applications and a 1026x1026 grid for Ocean. For PARSEC applications a checkpoint is created in the parallel phase. The cycle-accurate simulation starts at those checkpoints, warming the memory hierarchy for 300 million cycles, and then collecting statistics for the next 700 million cycles. Ocean is run to completion but performance statistics are only taken in the parallel phase. Figure 6.12 shows, for the five parallel applications, the relative performance of the reuse cache with data array sizes from 4 MBytes (RC-8/4) to 512 KBytes (RC-8/0.5) with respect to the baseline SLLC. Only ferret suffers a loss in performance when using a reuse cache with respect to the baseline cache. This loss varies between 1% with RC-8/4 and 11% with RC-8/0.5. However, in the other four applications even RC-8/0.5 achieves better performance than the baseline cache (canneal and ocean show speedups of more than 10%). 6.5 concluding remarks The reference stream observed by the SLLC of a CMP exhibits little temporal locality but, instead, it exhibits reuse locality. As a consequence, a dominant fraction of the SLLC lines is useless because the lines will not be requested again before being evicted, and most hits observed by the SLLC come from a small subset of already reused lines. In this paper we propose the reuse cache, a SLLC with a very selective data allocation policy intended to track and keep that small 118 reuse cache subset of lines showing reuse. In a reuse cache, the tag and the data arrays are decoupled. On the one hand, the size of data array can be dramatically reduced without negatively affecting performance. On the other hand, the tag array tracks the reuse order of recently referenced lines, and has the size required to store the tag of the lines in the data array and private caches. We have evaluated our proposal by simulating an eight-core CMP system running multiprogrammed and multithreaded workloads. The results show that a reuse cache can achieve the same performance as a conventional cache with a much lower hardware cost. For instance, a reuse cache with the tag array equivalent to a conventional 4 MB cache but with only 1 MB of data array, gives the same average performance as an 8 MB conventional cache. That reuse cache would require only a 16.7% of the storage budget of the conventional cache. We have illustrated the usefulness of the reuse cache concept with a case study: reducing space and maintaining performance. Evidently, the reuse cache could also be used in other settings, or for other reasons, seeking to meet other design goals in relation to some chip area, performance or energy tradeoff. Part IV CONCLUSION This last part of the thesis only includes one chapter. This chapter includes the general conclusions of this thesis, future work continuing the contributions presented during this dissertation and the publications where such contributions appeared. 7 CONCLUSIONS summary This last chapter exposes general conclusions about the contributions shown during the present dissertation. The chapter also shows the publications where the contributions of this thesis have been published and highlights future directions to continue with work of this thesis. 121 122 conclusions 7.1 conclusions The speed gap between cpu and main memory has been increasing during the last forty years and nothing says this tendency is going to change in the near future. In order to mitigate such speed gap a hierarchy of cache memories has been traditionally included between the main memory and the cpus. This hierarchy relies on temporal and spatial locality to provide the cpus with data and instructions, the goal is to offer this information with a low average latency. In the multi-/manycore scenario where we are now, hierarchies of memory are more complex than ever, including some levels of cache accessible only by each core and, as we have been seeing during this dissertation, a last level that is shared among all the cores present in the system. Moreover, Moore’s law is still strictly complied providing the architects with a bunch of new transistors to spend on the next processor generation. New silicon is precisely employed in many of the new designs to amply each of all the levels of the memory hierarchy. This hierarchy is already occupying an important part of the chip die, e.g. the last-level cache of an intel i7 processor takes away roughly the 50% of the total chip die area. Until now, last-level caches were including a constant, or even increasing, number of megabytes of shared last-level cache per core, but such tendency is not likely to continue in designs with some dozens of cores if the access latency to this last level wants to be maintained reasonable. Thus the way to design the hierarchies of the future devices has to pass through improving the efficiency of such hierarchies. This thesis has focused on improving the efficiency of the shared last-level cache, exploring the way on two different directions: 1) improving performance and 2) reducing hardware storage. 1) Regarding performance, this dissertation makes contributions to improve the performance of two mechanisms that critically affect the cache performance: hardware prefetching and replacement. Hardware prefetching may harm the system performance when it is used in an uncontrolled manner in the hierarchy of memory of a CMP. Prefetches issued by one core can evict contents of other cores affecting their performance. Given the broad ecosystem of applications can be found running in a CMP, prefetching should be controlled but controlled in a per-core fashion, always with maximum fairness and overall system performance as objectives. A low- 7.2 publications 123 cost controller has been proposed with such objectives. This controller is able to improve system performance by 27% (harm. mean of speedups) respect to a system with uncontrolled prefetching. This dissertation has stated a property called reuse locality, which is linked to the stream of references arriving to the SLLC and says that i) if a line receive a hit on the SLLC is highly likely that line will receive another hit in the future, and ii) recently reused lines are more useful than lines reused before. Reuse locality is used to propose two new replacement algorithms for the SLLC, which are transformations of two standard ones. These standard algorithms, LRU and NRU, were designed to exploit temporal locality while ours, LRR and NRR, are designed to exploit reuse locality. This dissertation has shown during evaluation sections that our contributions are consistently better than both base algorithms and a proposal, DRRIP, from the state of the art. 2) Finally, this dissertation proposes a new SLLC organization that relying on the reuse locality implements a very restrictive data array insertion policy. This insertion policy only stores into the SLLC data array, data that has shown reuse. Evaluation has shown this design is able to offer drastic reductions on the SLLC hardware storage requirements, achieving to reduce up to 84% of the SLLC hardware storage while maintaing average performance untouched. 7.2 publications This section shows the publications of this thesis, which have already been referenced in the corresponding sections. •J. Albericio, R. Gran, P. Ibáñez, V. Viñals, and J.M. Llabería. "ABS: A low-cost adaptive controller for prefetching in a banked shared LLC". ACM Transactions on Computer Architecture and Optimization (TACO): Special Issue on "HighPerformance and Embedded Architectures and Compilers". Volumen: 8, Issue 4. Pp. 1-19. January, 2012. •J. Albericio, P. Ibáñez, V. Viñals, and J. M. Llabería. "Exploiting reuse locality on inclusive shared last-level caches". ACM Transactions on Computer Architecture and Optimization (TACO). Volumen: 9, Issue 4. Article 38. January, 2013. 124 conclusions •J. Albericio, P. Ibáñez, V. Viñals, and J. M. Llabería. "The Reuse Cache: downsizing the shared Last-level cache". University of Zaragoza, technical report TR-12-02. 7.3 future work 7.3.1 Replacement inclusiveness In spite of everything suggests reuse locality property will be present in all kind of SLLC, the behavior of our replacement policies, NRR and LRR, would have in a hierarchy with different inclusion properties is a evaluation still to perform. partial information Our replacement policies have been only evaluated in a hierarchy with a full-map directory. An interesting study would be to observe if the performance of the replacement policies is affected because of the use of a coherence system that considers partial information, meaning that directory information is not necessarily updated. This interaction arises due to our replacement schemes take information about the presence of lines directly from the full-map directory. prefetch and replacement Only a recent work [Martonosi + Jean Wu] has studied the interaction between replacement and prefetch. Moreover, this previous work only focuses on a multiprogrammed scenario, thus a scenario where parallel applications run is still something to study, sharing and replacement The interaction between sharing and replacement is still something to study. Most of research about replacement policies has focused on multiprogrammed scenarios where unbalance and competition between different applications are the problem to solve. In a different scenario where parallel applications run (alone or running along other), proposed techniques may not be valid anymore or at least they should be reviewed and evaluated. 7.3 future work 125 7.3.2 Reuse Cache Regarding to future work relying on the reuse cache design: dynamic data array size Dynamic total size To have a decoupled organization offers an additional flexibility that could be employed to different things. One of these things is that data array becomes a candidate to switch some of its parts off. Instead of being the total SLLC storage the target, a reuse cache without data array downsizing (or minimum) could be employed as base design. Then, parts of the data array could be arbitrarily switch on/offdepending on the system load. The level of system load could be easily detected by using the SLLC tags. Dimensions of the data array could be downsized by cutting the set associativity or by reducing the total number of sets. dynamic tag array size The evaluation of the reuse cache showed that different applications require a different reuse detection capacity. The optimal reuse detection capacity depends not only on the application but also on the data array size where the reused data are stored. This topic has still to be studied but classical dynamic optimization approaches like hill-climbing or/and set-dueling can be applied. These dynamic schemes may be employed to vary the number of elements in tag array sets. two misses Given that in the reuse cache, if not predictor is used, all the hits will pay two misses in advance, some kind of reuse predictor could be used. Wu et al. [67] proposed some predictors to improve the re-reference interval prediction of the RRIP mechanism [23]. Taking into account those policies and ours have the same last goal, it seems reasonable that such predictors are highly likely to work well on the reuse cache scheme. variable grain A recent work [Amoeba] proposes to implement the cache as a contiguous vector of non-constant-size elements. Each element has included along its tag, what is the size of the data field. Taking this concept to the end, such elements could include empty data fields and only to include the data when the element has shown reuse. At the same time, the reuse locality property could be studied in a sub-block fashion. The reuse cache as it is proposed on this dissertation considers inclusion enforcement in both tags and data. Given that, the reuse 126 conclusions cache is proposed for a low cache-per-core ratio, in order to maximize SLLC storage, it seems reasonable to think in an exclusive reuse cache scheme. This inclusion enforcement could be relaxed in one or both tags and data arrays. On the reuse cache proposed in previous sections, once a data has been classified as reused, it will be inserted at the same time into the SLLC reuse data and into the local caches. exclusivity:data array If we considered to implement local caches and SLLC to be disjoint sets, a cache line would be only put into the SLLC data array once this data has shown reuse at the SLLC and such cache line has been evicted from the local caches. Considering this scheme, tags array would still maintain inclusion, simplifying coherence but maximizing at the same time the SLLC data array storage. Besides, an exclusive data array would require some mechanism to send information from one local cache to another when a sharing behavior is found. exclusivity:tag and data arrays A further step would be to implement exclusivity at the same time on both tags and data arrays. This scheme would increase the reuse detection capacity of the reuse cache. At the same time this scheme would complicate coherence maintenance and its worthiness would have to be carefully studied. (dynamic) exclusivity As most of previously shown possible future lines, exclusivity implementation may be considered in a dynamic manner. Sim et al. [53] have recently shown how to adapt this property and such kind of adaptation could be also employed in any of the exclusive schemes here proposed. bibliography 133 [37] Mario Lodde, Jose Flich, and Manuel E. Acacio. Dynamic lastlevel cache allocation to reduce area and power overhead in directory coherence protocols. In Euro-Par, pages 206–218, 2012. [38] P. Lotfi-Kamran, B. Grot, M. Ferdman, S. Volos, O. Kocberber, J. Picorel, A. Adileh, D. Jevdjic, S. Idgunji, E. Ozer, and B. Falsafi. Scale-out processors. In Proc. 39th Annual Int. Symp. on Computer Architecture (ISCA), 2012, pages 500 –511, june 2012. doi: 10.1109/ISCA.2012.6237043. URL http://dl.acm. org/citation.cfm?id=2337217. [39] Kun Luo, J. Gummaraju, and M. Franklin. Balancing thoughput and fairness in smt processors. In Proc. ISPASS Performance Analysis of Systems and Software 2001 IEEE Int. Symp, pages 164– 171, 2001. doi: 10.1109/ISPASS.2001.990695. [40] P. S. Magnusson, M. Christensson, J. Eskilson, D. Forsgren, G. Hallberg, J. Hogberg, F. Larsson, A. Moestedt, and B. Werner. Simics: A full system simulation platform. Computer, 35(2):50– 58, 2002. doi: 10.1109/2.982916. [41] M. Martin, D. Sorin, B. Beckmann, M. Marty, Min Xu, A. Alameldeen, K. Moore, M. Hill, and D. Wood. Multifacetśgeneral execution-driven multiprocessor simulator (gems) toolset. SIGARCH Comput. Archit. News, 33:2005, 2005. [42] M. Martin, M. Hill, and D. Sorin. Why on-chip cache coherence is here to stay. To appear in Communications of the ACM, July, 2012, 2012. [43] Sun Microsystems. UltraSPARC T2 supplement to the UltraSPARC architecture 2007. Draft D1.4.3, 19 Sep 2007, 2007. [44] O. Mutlu and T. Moscibroda. Stall-time fair memory access scheduling for chip multiprocessors. In Proc. 40th Annual IEEE/ACM Int. Symp. Microarchitecture MICRO 2007, pages 146– 160, 2007. doi: 10.1109/MICRO.2007.21. [45] K. J. Nesbit and J. E. Smith. Data cache prefetching using a global history buffer. 25(1):90–97, 2005. doi: 10.1109/MM.2005.6. [46] S. Palacharla and R. E. Kessler. Evaluating stream buffers as a secondary cache replacement. In Proc. 21st Annual Int Computer Architecture Symp, pages 24–33, 1994. doi: 10.1109/ISCA. 1994.288164. 134 bibliography [47] M. Qureshi, A. Jaleel, Y. Patt, S. Steely, and J. Emer. Adaptive insertion policies for high performance caching. In Proceedings of the 34th annual international symposium on Computer architecture, ISCA ’07, pages 381–391, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-706-3. doi: 10.1145/1250662.1250709. URL http://doi.acm.org/10.1145/1250662.1250709. [48] Moinuddin K. Qureshi, David Thompson, and Yale N. Patt. The v-way cache: Demand based associativity via global replacement. In Proceedings of the 32nd annual international symposium on Computer Architecture, ISCA ’05, pages 544–555, Washington, DC, USA, 2005. IEEE Computer Society. ISBN 0-7695-2270-X. doi: 10.1109/ISCA.2005.52. URL http://dx.doi.org/10.1109/ ISCA.2005.52. [49] Luis M. Ramos, José Luis Briz, Pablo E. Ibáñez, and Víctor Viñals. Multi-level adaptive prefetching based on performance gradient tracking. J. Instruction-Level Parallelism, 13, 2011. [50] Jeffrey B. Rothman and Alan Jay Smith. The pool of subsectors cache design. In Proceedings of the 13th international conference on Supercomputing, ICS ’99, pages 31–42, New York, NY, USA, 1999. ACM. ISBN 1-58113-164-X. doi: 10.1145/305138.305156. URL http://doi.acm.org/10.1145/305138.305156. [51] Vivek Seshadri, Onur Mutlu, Michael A. Kozuch, and Todd C. Mowry. The evicted-address filter: a unified mechanism to address both cache pollution and thrashing. In Proceedings of the 21st international conference on Parallel architectures and compilation techniques, PACT ’12, pages 355–366, New York, NY, USA, 2012. ACM. ISBN 978-1-4503-1182-3. doi: 10.1145/2370816.2370868. URL http://doi.acm.org/10.1145/2370816.2370868. [52] A. Seznec. Decoupled sectored caches: conciliating low tag implementation cost. In Proceedings of the 21st annual international symposium on Computer architecture, ISCA ’94, pages 384– 393, Los Alamitos, CA, USA, 1994. IEEE Computer Society Press. ISBN 0-8186-5510-0. doi: http://dx.doi.org/10.1145/192007.192072. [53] Jaewoong Sim, Jaekyu Lee, Moinuddin K. Qureshi, and Hyesoon Kim. Flexclusion: balancing cache capacity and on-chip bandwidth via flexible exclusion. In Proceedings of the 39th Annual International Symposium on Computer Architecture, ISCA ’12, pages 321–332, Washington, DC, USA, 2012. IEEE Computer Society. ISBN 978-1-4503-1642-2. URL http://dl.acm.org/ citation.cfm?id=2337159.2337196. bibliography 135 [54] Alan Jay Smith. Cache memories. ACM Comput. Surv., 14:473– 530, September 1982. ISSN 0360-0300. doi: http://doi.acm.org/ 10.1145/356887.356892. URL http://doi.acm.org/10.1145/ 356887.356892. [55] A. Snavely and D. Tullsen. Symbiotic jobscheduling for a simultaneous multithreaded processor. SIGARCH Comput. Archit. News, 28:234–244, November 2000. ISSN 0163-5964. doi: http:// doi.acm.org/10.1145/378995.379244. URL http://doi.acm.org/ 10.1145/378995.379244. [56] Stephen Somogyi, Thomas F. Wenisch, Anastassia Ailamaki, Babak Falsafi, and Andreas Moshovos. Spatial memory streaming. In Proceedings of the 33rd annual international symposium on Computer Architecture, ISCA ’06, pages 252–263, Washington, DC, USA, 2006. IEEE Computer Society. ISBN 0-76952608-X. doi: http://dx.doi.org/10.1109/ISCA.2006.38. URL http: //dx.doi.org/10.1109/ISCA.2006.38. [57] Stephen Somogyi, Thomas F. Wenisch, Anastasia Ailamaki, and Babak Falsafi. Spatio-temporal memory streaming. In Proceedings of the 36th annual international symposium on Computer architecture, ISCA ’09, pages 69–80, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-526-0. doi: http://doi.acm.org/ 10.1145/1555754.1555766. URL http://doi.acm.org/10.1145/ 1555754.1555766. [58] S. Srinath, O. Mutlu, Hyesoon Kim, and Y. N. Patt. Feedback directed prefetching: Improving the performance and bandwidthefficiency of hardware prefetchers. In Proc. IEEE 13th Int. Symp. High Performance Computer Architecture HPCA 2007, pages 63– 74, 2007. doi: 10.1109/HPCA.2007.346185. [59] R. Subramanian, Y. Smaragdakis, and G. H. Loh. Adaptive caches: Effective shaping of cache behavior to workloads. In Proc. MICRO-39 Microarchitecture 39th Annual IEEE/ACM Int. Symp, pages 385–396, 2006. doi: 10.1109/MICRO.2006.7. [60] T. S. B. Sudarshan, Rahil Abbas Mir, and S. Vijayalakshmi. Highly efficient LRU implementations for high associativity cache memory. [61] Myoung Kwon Tcheun, Hyunsoo Yoon, and Seung Ryoul Maeng. An adaptive sequential prefetching scheme in shared-memory multiprocessors. In Proc. Int Parallel Processing Conf, pages 306– 313, 1997. doi: 10.1109/ICPP.1997.622660. 136 bibliography [62] A. Valero, J. Sahuquillo, S. Petit, P. López, and J. Duato. Combining recency of information with selective random and a victim cache in last-level caches. ACM Trans. Archit. Code Optim., 9(3):16:1–16:20, October 2012. ISSN 1544-3566. doi: 10.1145/2355585.2355589. URL http://doi.acm.org/10.1145/ 2355585.2355589. [63] D. Wallin and E. Hagersten. Miss penalty reduction using bundled capacity prefetching in multiprocessors. In Proc. Int. Parallel and Distributed Processing Symp, 2003. doi: 10.1109/IPDPS. 2003.1213088. [64] T. F. Wenisch, S. Somogyi, N. Hardavellas, Jangwoo Kim, A. Ailamaki, and Babak Falsafi. Temporal streaming of shared memory. In Proc. 32nd Int. Symp. Computer Architecture ISCA ’05, pages 222–233, 2005. doi: 10.1109/ISCA.2005.50. [65] T. F. Wenisch, M. Ferdman, A. Ailamaki, B. Falsafi, and A. Moshovos. Practical off-chip meta-data for temporal memory streaming. In Proc. IEEE 15th Int. Symp. High Performance Computer Architecture HPCA 2009, pages 79–90, 2009. doi: 10.1109/HPCA.2009.4798239. [66] S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The splash-2 programs: characterization and methodological considerations. In Proc. Symp. nd Annual Int Computer Architecture, pages 24–36, 1995. [67] C.-J. Wu, A. Jaleel, W. Hasenplaugh, M. Martonosi, S. C. Steely, and J. Emer. SHiP: signature-based hit predictor for high performance caching. In Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-44 ’11, pages 430–441, New York, NY, USA, 2011. ACM. ISBN 978-14503-1053-6. doi: 10.1145/2155620.2155671. URL http://doi. acm.org/10.1145/2155620.2155671. [68] Y. Xie and G. Loh. PIPP: promotion/insertion pseudopartitioning of multi-core shared caches. In Proceedings of the 36th annual international symposium on Computer architecture, ISCA ’09, pages 174–183, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-526-0. doi: 10.1145/1555754.1555778. URL http: //doi.acm.org/10.1145/1555754.1555778. [69] Li Zhao, Ravi Iyer, Srihari Makineni, Don Newell, and Liqun Cheng. NCID: a non-inclusive cache, inclusive directory architecture for flexible and efficient cache hierarchies. In Pro- bibliography 137 ceedings of the 7th ACM international conference on Computing frontiers, CF ’10, pages 121–130, New York, NY, USA, 2010. ACM. ISBN 978-1-4503-0044-5. doi: 10.1145/1787275.1787314. URL http://doi.acm.org/10.1145/1787275.1787314.