A fault-tolerant last level cache for CMPs operating at ultra-low voltage

Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. Journal of Parallel and Distributed Computing xxx (xxxx) xxx Contents lists available at ScienceDirect J. Parallel Distrib. Comput. journal homepage: www.elsevier.com/locate/jpdc Q1 A fault-tolerant last level cache for CMPs operating at ultra-low voltage Alexandra Ferrerón a,c,1,Jesús Alastruey-Benedé a,c,∗,Darío Suárez Gracia a,c, Teresa Monreal Arnal b,c,Pablo Ibáñez Marín a,c,Víctor Viñals Yúfera a,c Q2 aDepartamento de Informática e Ingeniería de Sistemas, Instituto de Investigación en Ingeniería de Aragón, Universidad de Zaragoza, Spain bUniversitat Politècnica de Catalunya, BarcelonaTech, Spain cHiPEAC European Network of Excellence, Belgium highlights •Fault-Tolerant Last Level Cache for CMPs Operating at Ultra-Low Voltage. •Mechanism that exploits redundancy and reuse to enhance block disabling performance. •Fault-aware LLC management that maps critical blocks to operative cache entries. •Detailed evaluation of block disabling techniques in a shared-memory coherent CMP. article info Article history: Received 19 December 2017 Received in revised form 23 July 2018 Accepted 22 October 2018 Available online xxxx Keywords: Near-threshold voltage SRAM reliability Fault-tolerance On-chip caches Cache management abstract Voltage scaling to values near the threshold voltage is a promising technique to hold off the manycore power wall. However, as voltage decreases, some SRAM cells are unable to operate reliably and show a behavior consistent with a hard fault. Block disabling is a micro-architectural technique that allows low-voltage operation by deactivating faulty cache entries, at the expense of reducing the effective cache capacity. In the case of the last-level cache, this capacity reduction leads to an increase in offchip memory accesses, diminishing the overall energy benefit of reducing the voltage supply. In this work, we exploit the reuse locality and the intrinsic redundancy of multi-level inclusive hierarchies to enhance the performance of block disabling with negligible cost. The proposed fault-aware lastlevel cache management policy maps critical blocks, those not present in private caches and with a higher probability of being reused, to active cache entries. Our evaluation shows that this fault-aware management results in up to 37.3 and 54.2% fewer misses per kilo instruction (MPKI) than block disabling for multiprogrammed and parallel workloads, respectively. This translates to performance enhancements of up to 13% and 34.6% for multiprogrammed and parallel workloads, respectively. Q3 ©2018 Elsevier Inc. All rights reserved. 1. Introduction1 For recent CMOS technologies, power density is the main per-2 formance limiting factor across most computing segments. Moore’s3 law continues to hold, with a doubling of the number of transis-4 tors and integration density in each new process generation, but5 Dennard scaling no longer applies, and we are not able to keep6 a constant power density across technology generations. Power7 budgets prevent us from utilizing all the available transistors,8 leading to dark silicon [44].9 ∗Corresponding author at: Departamento de Informática e Ingeniería de Sistemas, Instituto de Investigación en Ingeniería de Aragón, Universidad de Zaragoza, Spain. E-mail address: [email protected] (J. Alastruey-Benedé). 1Now at Google. For years, industry has relied on scaling the supply voltage 10 (Vdd) to reduce power consumption, but this trend has dramatically 11 slowed since the 90 nm generation because of leakage. Reducing 12 operating voltages to values near the threshold voltage (Vth) would 13 minimize leakage and switching power consumption. The result14 ing power reduction could be used to activate more chip resources 15 and potentially achieve performance improvements [14]. 16 Unfortunately, Vdd scaling is limited by the tight margins of the 17 on-chip cache SRAM transistors. Excessive parameter variations 18 in SRAM cells limit the voltage scaling of memory structures to a 19 minimum voltage, Vddmin , below which SRAM cells may not operate 20 reliably. Vddmin usually determines the minimum voltage of the 21 whole processor, and in current technologies is typically of the 22 order of 0.7–1.0 V, when regular 6T SRAM cells are employed. 23 In the literature, various solutions have been proposed to enable 24 reliable cache operation at low voltages. At the circuit level, the use 25 https://doi.org/10.1016/j.jpdc.2018.10.010 0743-7315/©2018 Elsevier Inc. All rights reserved. © 2018 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ YJPDC: 3966 Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. 2A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al. / Journal of Parallel and Distributed Computing xxx (xxxx) xxx of larger transistors or more transistors (assist circuitry) improves1 SRAM cell resilience [29,47]. The main drawbacks of this approach2 are the associated increases in area and power consumption. First-3 level caches in chip multiprocessors (CMPs) occupy little area, and4 their access time often determines the processor cycle time. Com-5 mercial processors, such as the Intel Nehalem family, use robust 8T6 SRAM cells to build reliable first-level caches, since this represents7 an affordable overhead [30]. In contrast, last-level caches (LLCs) are8 usually shared and have larger sizes and associativity, accounting9 for much of the die area [9]. Hence, for LLCs, minimum-geometry10 6T cells are preferred to achieve higher densities.11 At the architectural level, fault-tolerant cache designs rely on12 disabling faulty resources at different granularities [32], or correct-13 ing defective bits through either error correction codes (ECCs) [13]14 or a distributed duplication of blocks [5,45]. Block Disabling (BD)15 is a simple technique that disables a cache entry when a defective16 bit is found [42]. It is already implemented in modern processors17 to protect against hard faults [9]. However, due to the random18 distribution of defective cells, the capacity of the cache is rapidly19 compromised. Complex techniques based on ECCs or the combi-20 nation of faulty resources are able to rescue more cache capacity,21 but incur large storage overheads and sometimes require complex22 remapping that penalizes the cache access latency.23 In our work, we have developed a new approach to mitigate the24 impact of SRAM failures in LLCs due to parameter variations, based25 on BD but also relying on the underlying structures already present26 in CMPs. We identify a natural source of on-chip data redundancy27 that arises because of the replication of blocks in inclusive multi-28 level cache hierarchies and exploit this redundancy through a29 smart fault-aware cache management policy.30 In this paper, we make the following contributions. First, we31 provide an evaluation of BD techniques in a shared-memory co-32 herent CMP running parallel and multiprogrammed workloads33 with a complete and detailed memory model, exploring SRAM34 cells with different probabilities of failure. Second, we introduce a35 technique that keeps the tags of the LLC and, therefore, the tracking36 capabilities of the coherence directory operational. This way, a37 block not physically stored in the LLC can reside in the private38 level and be made available to other cores. As an alternative to39 main memory supply, we set up a cache-to-cache copy service to40 support code or data sharing (thread migration, operating system,41 or parallel workloads). Finally, we propose a fault-aware cache42 management policy that predicts the usefulness of a block based43 on its use pattern, and guides the allocation of blocks to faulty44 and non-faulty cache entries, adding no overhead to the original45 replacement policy.46 Our fault-aware cache management policy is able to decrease47 the LLC misses per kilo instruction (MPKI) by up to 37.3%, with48 respect to BD, which translates to speedup improvements of 249 to 13% for multiprogrammed workloads. For parallel workloads,50 the MPKI values decrease by 5 to 54.2%, with respect to BD, for51 the different SRAM cells considered, improving performance up to52 34.6%.53 This paper extends our previous work [16] in several significant54 ways: (i) a new fault-aware cache management policy aiming at55 caches operating at low voltages, (ii) a detailed implementation of56 block disabling with operational tags (BDOT) technique, (iii) a more57 realistic SRAM fault model, improving the accuracy of the results,58 and (iv) a more detailed evaluation including multi-programmed59 workloads and cache capacity/energy analysis.60 The rest of the paper is organized as follows. Section 2intro-61 duces the problem of process variations and its effect on SRAM cell62 reliability. Section 3comments on BD and its impact on large cache63 structures. In Section 4, we describe how to take advantage of the64 coherence infrastructure to operate at low Vdd. Section 5introduces65 a fault-aware cache management policy for LLC operating at low66 Table 1 Area relative to cell C1 and percentage of non-faulty 64-byte entries in a cache operating at 0.5 V, for the 6 bit cells introduced in [47]. Cell type C1 C2 C3 C4 C5 C6 Relative area 1.00 1.12 1.23 1.35 1.46 1.58 % non-faulty 0.0 9.9 27.8 35.8 50.6 59.9 voltages. Section 6describes the methodology. Section 7presents 67 our evaluation. Section 8discusses the system impact. In Section 68 9, we comment on related work, and in Section 10, we outline our 69 conclusions. 70 2. Process variations in SRAM cells 71 SRAM structures are especially vulnerable to failures due to 72 process variations, as they are aggressively sized to meet high 73 density requirements, and because of the vast number of cells 74 that comprise on-chip SRAM structures [7]. In particular, intra-die 75 random dopant fluctuations (RDFs) are the main cause of threshold 76 voltage variation [43]. The stochastic nature of the ion implan77 tation process leads to a distribution of Vth values across a chip, 78 which reduces the already tight transistor margins. Hence, SRAM 79 structures have a minimum voltage, Vddmin , to guarantee reliable 80 operation, which is typically of the order of 0.7–1.0 V in current 81 process generations, when 6T cells are used. 82 The robustness of SRAM cells under the Vddmin range has been 83 extensively analyzed in the literature [5,13,29,31,45]. Zhou et al. 84 studied six different sizes of 6T SRAM cells in 32 nm technology, 85 and their probabilities of failure as Vdd decreases [47]. According 86 to that study, at 0.5 V, the probability of failure of an SRAM cell 87 (Pfail) is between 10-3 and 10-2. The use of larger cells reduces the 88 probability of failure, as non-uniformities average out, increasing 89 read and write margins and resulting in more robust devices. 90 However, large cells reduce the density and increase power and 91 energy consumption. 92 Table 1 describes the six SRAM cells of Zhou’s study (C1, C2, C3, 93 C4, C5, and C6) in terms of their area relative to the smallest cell 94 (C1), and lists the percentage of non-faulty entries in caches built 95 from these cells operating at 0.5 V, assuming 64-byte cache entries. 96 An entry is considered faulty if it contains at least one defective bit. 97 As Table 1 shows, less than 10% of the cache entries are non98 faulty for the small cells C1 and C2 at 0.5 V. If the cache is imple99 mented with the more robust C6 cells, however, the percentage 100 of non-faulty cache entries rises to 60%, but at the cost of a 58% 101 increase in area (relative to C1), and the consequent increase in 102 leakage, which is not a suitable option for a large structure such 103 as an on-chip LLC. 104 In this work, we take Zhou’s reliability study as a reference to 105 test our proposals on a wide range of failure probabilities. We will 106 only consider C2 to C6 operating at 0.5 V (our target near-threshold 107 Vdd), as at this voltage, a cache built with C1 cells would have all its 108 capacity compromised. 109 3. Impact of block disabling on large shared caches at ultra-low 110 voltages 111 A simple approach to handling hard faults is the disabling of 112 faulty elements. BD deactivates resources at block (cache entry2)113 granularity: when a fault is detected at a given cache entry, that 114 entry is marked as defective and it can no longer store a cache 115 2In this work, we differentiate between cache block and cache entry: block refers to the transfer unit, the content per se, while entry refers to the physical group of cells that store a block. YJPDC: 3966 Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al. / Journal of Parallel and Distributed Computing xxx (xxxx) xxx 3 Fig. 1. Available associativity of a 16-way set associative block disabling cache (64-byte block) made up of cells ∧ C6–C1 operating at 0.5 V. block [42]. This technique is implemented in modern processors1 to enable them to tolerate hard faults [9].2 BD has also been studied for operation at low voltages because3 of its easy implementation and low overhead [31]. From the im-4 plementation perspective, only one bit per entry suffices to mark5 the entry as faulty. The main drawback of this approach is that6 the amount of capacity dramatically falls when the probability7 of failure increases, as shown in Table 1. Even if the total count8 of faulty cells in the cache is less than 1%, the effective cache9 capacity is strongly affected because of the random distribution of10 faulty cells. BD results in caches with variable associativity per set,11 determined by the number and distribution of faults in the cache.12 The interaction between BD and a system’s cache organization13 also plays an important role. Modern commercial processors, such14 as the Intel Core i7, implement inclusive hierarchies to facilitate15 coherence management. Inclusive hierarchies require that all the16 blocks cached in a private cache are also stored in the shared LLC.17 The coherence information is embedded in the LLC; i.e., the sharing18 state and a bit vector to represent the current sharers are added to19 each block. To force inclusion, when a block is evicted from the LLC,20 explicit back invalidations are required to remove the copies of the21 private cache blocks, if present (inclusion victims) [6].22 Inclusive hierarchies perform poorly when the aggregated size23 of the private caches is similar to the size of the LLC [23], and BD24 exacerbates the problem because of the substantial associativity25 and capacity degradation in the LLC. Fig. 1 shows the available26 associativity in a 16-way set associative cache bank with 64-byte27 blocks, when built with cells ∧ C1–C6 (Table 1) operating at 0.5 V.28 The number of faulty ways per set follows a binomial distribution29 B(n,p), where nis the associativity, and pdenotes the probability of30 failure of a cache entry. Fig. 1 shows how the associativity degrades31 as more faulty cells appear on the cache structure. On average,32 50% of the ways are faulty if the cache is built with C5 cells, and33 this percentage rises to 90% when using C2 cells. The associativity34 loss directly translates to a significant increase in the number35 of inclusion victims. For instance, the number of invalidations in 36 a cache built with C3 cells is 10 times larger than in a cache 37 implemented with fault-free SRAM cells. 38 This finding suggests that inclusive hierarchies are not partic39 ularly suitable for systems that implement BD in the presence of 40 a significant number of faults. From the coherence management 41 perspective, however, only directory inclusion is required: blocks 42 present in the private levels have to be tracked only in the shared 43 level tag array, without the need for a replica in the data array [6]. 44 This observation is the basis for the techniques we propose in this 45 paper. 46 Our proposal has been designed for inclusive memory hierar47 chies, but most of the proposed ideas could benefit non-inclusive 48 and exclusive hierarchies as well. The objectives of our replace49 ment and promotion algorithms are to assign the non-faulty en50 tries to blocks with reuse and to blocks that are not present in the 51 private caches. On the one hand, these objectives are still valid in 52 a non-inclusive hierarchy; however, their relative importance is 53 different, and our algorithms should consider different priorities 54 for allocation and promotion decisions. On the other hand, our 55 proposal alleviates a specific problem of inclusive hierarchies, such 56 as the need to invalidate a block in a private cache when it is evicted 57 from the shared cache. This problem does not exist in non-inclusive 58 hierarchies, and therefore our proposal is not applicable in this 59 specific aspect. 60 Note on Fig. 1 that, when using cell types C3 and C2, 0.6% and 61 18.9% of the sets have no operative ways, respectively. To be able 62 to offer a complete comparison with BD, we assume that at least 63 one of the ways in each set is non-faulty, although this is not a 64 requirement for the techniques we present in this paper, and the 65 LLC is able to operate even when all the ways of a set are faulty. 66 4. Exploiting inclusive hierarchies to enable ultra-low voltage 67 operation: Block Disabling with Operational Tags 68 The BD scheme simply assumes one extra bit per entry to 69 identify faulty cache entries in the data array (one or more faulty 70 YJPDC: 3966 Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. 4A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al. / Journal of Parallel and Distributed Computing xxx (xxxx) xxx Table 2 Main characteristics of the CMP system. Cores 8, Ultrasparc III Plus, in-order, 1 instr./cycle, single-threaded, 1 GHz at Vdd 0.5 V Coherence protocol MESI, directory-based (full-map) distributed among LLC cache banks Consistency model Sequential L1 cache Private, 64 KB data and instr. caches, 4-way, 64 B block size, LRU, 2-cycle hit access time LLC cache Shared, inclusive, interleaved by line address, 1 bank/tile, 1 MB/bank, 16-way, 64 B block size, NRU replacement 8-cycle hit access time (4-cycle tag access + 4-cycle data access) Memory 2 memory controllers, located at the edges of the chip; 1333 MHz DDR3 2 channels, 8 Gb/channel, 8 banks, 8 KB page size, open page policy; raw access time 50 cycles NoC Mesh, 2 virtual networks (VNs): requests and replies; 2 virtual channels per VN; 16-byte flit size 1-cycle latency hop, 2-stage routing cells). Faulty data entries are excluded from tag search and replace-1 ment, involving a net reduction in associativity, and a consequent2 increase in inclusion victims. From the coherence management3 perspective, however, tracking blocks in the shared level tag array4 suffices to ensure directory inclusion. This is the basis of our pre-5 vious work, [16], and the starting point of the first technique we6 propose: Block Disabling with Operational Tags (BDOT).7 Assuming a two-level inclusive hierarchy, to force directory8 inclusion, we turn on the tags of faulty entries in the LLC, including9 them in the conventional operations of search and replacement.10 The tag of a faulty entry, if valid, tracks a cache block that might11 be present in the private caches, but that cannot be stored in the12 shared cache. Enabling the tags of the faulty entries restores the13 associativity of the shared cache as seen by the first-level private14 caches, eliminating the problem of the increase in the number of15 inclusion victims caused by the loss in associativity.16 In this situation, two kinds of LLC entries have to be distin-17 guished: tag-only (T), where the associated data entry is faulty18 and only the tag is stored, and tag-data (D), where the associated19 data entry is non-faulty and both tag and data are stored. From20 the implementation perspective, one resilient bit still suffices to21 indicate whether the entry is faulty or not. The coherence protocol22 needs to be adapted to this new situation, where a Tentry only23 stores the block tag and directory state. Whenever a request to a24 block stored in a Tentry arrives to the LLC bank, the request needs25 to be sent to the next level (in this case, the off-chip memory) to26 recover the block, and the same occurs with dirty blocks, which27 need to be written back to memory after being evicted from a28 private cache.29 To fully exploit this scheme, no failures should occur in the cells30 of the tag array. This can be accomplished, for example, by using31 robust cells (e.g., increasing the number of transistors per cell) or32 increasing the strength of the ECC. Tags occupy very little area in33 comparison to the data array (around 6% for our configuration,34 see Table 2 in Section 6), and increasing the cell size by 33%35 (assuming 8T SRAM cells [10]) will only increase the total area of36 a cache bank by 2%. Since using sophisticated ECCs could increase37 the access latency of the tag array, while using resilient tag cells38 involves little overhead, we opt for the latter. This approach is also39 consistent with prior work [5,45]. Moreover, many of today’s CPUs40 use different cell types for tag and data arrays [26]. Contrary to41 other proposals, our mechanism works even when all entries of a42 set are faulty. Contrary to other proposals, our mechanism works43 even when all entries of a set are faulty. The LLC saves the tags44 for both faulty and non-faulty entries, maintaining the coherence45 status of all the blocks, and allowing blocks to be stored in the46 private levels without the need of a data replica in the shared level.47 Hence, it is possible to store a block in the private caches even if all48 the data ways of the corresponding LLC set are faulty.49 4.1. BDOT limitations 50 BDOT, as described above, has two potential limitations, both 51 related to the allocation of blocks to faulty entries. 52 First, BDOT always forwards requests to blocks allocated to 53 faulty entries to the off-chip memory. However, a block allocated 54 to a faulty entry might be present on-chip, if it is being used by a 55 private cache (L1). This situation is common in parallel workloads, 56 which share data and instructions. In this case, the directory infor57 mation can be used to orchestrate cooperation among L1 caches. 58 When the directory protocol receives an L1 request to a shared 59 block mapped to a T entry, it forwards the request to one of the 60 sharers of the block, namely, the L1 cache closest to the requester in 61 terms of Manhattan distance. That L1 will serve the block through 62 a cache-to-cache transfer. 63 Cache-to-cache transfers are already implemented in the base64 line coherence protocol for exclusively owned blocks. Hence, no 65 additional hardware is required and a slight modification of the 66 directory protocol suffices to trigger a shared block transfer. So 67 from now on, we assume that BDOT includes this feature. 68 The second limitation comes from allocating blocks to LLC en69 tries without taking into account their Tor Dnature. Unfortunately, 70 this blind allocation can result in heavily reused blocks being 71 attached to faulty entries. Indeed, if a particular block of the LLC is 72 required repeatedly from an L1 cache (i.e., the block shows reuse), 73 any replacement algorithm will tend to protect it, reducing its 74 eviction chances. Thus, if a block with reuse is initially allocated 75 to a Tentry, unless replicated in other cores, all L1 cache misses 76 will be forwarded off-chip by the LLC. 77 In the next section, we introduce a specific allocation and real78 location policy for BDOT caches that differentiates between Tand 79 Dentries. 80 5. Fault-aware cache management policy for BDOT caches 81 Conventional cache management policies assume that every 82 cache entry can store a block, while BDOT breaks this assumption: 83 each set in an N-way set associative cache contains Tentries that 84 store only tags, and Dentries that store tags and data. Keeping in 85 mind the main goal of improving the overall LLC performance un86 der BDOT, this section introduces a fault-aware cache management 87 policy that takes into account the distinct nature of Tand Dentries, 88 and the reuse pattern of the reference stream. In particular, we seek 89 to achieve the following two goals: 90 1. To allocate blocks that are mostlikely to be used in the future 91 to Dentries. 92 2. To maximize the amount of on-chip data by giving greater 93 priority (higher chances of being allocated to Dentries) to 94 blocks that are not present in private cache levels. 95 YJPDC: 3966 Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al. / Journal of Parallel and Distributed Computing xxx (xxxx) xxx 5 Fig. 2. Reuse and inclusion states for a block in LLC. NR, R, C, and NC represent: NonReused, Reused, Cached (in L1), and Non-Cached (in L1), respectively. Replacement and coherence transitions are not shown. Prior work has shown that reuse is a very effective predictor of1 the usefulness of a given block in the LLC [4,11]. Reuse locality can2 be described as follows: lines accessed at least twice tend to be3 reused many times in the near future, and recently reused lines4 are more useful than those reused earlier [4]. Therefore, seeking5 to achieve our first goal, we exploit reuse locality to predict which6 blocks should be allocated to Dentries. With respect to our second7 goal, a request to a block allocated to a Tentry and present in L18 can be serviced through a cache-to-cache transaction, whilst if the9 block is not present in L1, the request will always be forwarded10 to the off-chip memory, incurring a penalty in access time and11 energy. Therefore, it is preferable to dedicate Dentries to blocks12 not available on the L1 caches.13 These goals may be added to any management policy. In this14 work, we will build on top of a state-of-the-art reuse-based re-15 placement algorithm: Not-Recently Reused (NRR) [4]. Next, we16 describe the baseline replacement in some depth and then we add17 awareness of the existence of faulty entries.18 5.1. Baseline NRR replacement algorithm19 The NRR algorithm requires four states per LLC block, as de-20 picted in Fig. 2. When a block not present in the LLC is requested21 by the processor (1st use: L1 request), it is stored in the L1 and22 the LLC (to force inclusion), its state being in the LLC NR-C (Non-23 Reused, Cached). When the block is evicted from the private cache24 (L1 eviction), its LLC state changes to NR-NC (Non-Reused, Non-25 Cached). On a new request (2nd use: L1 request), a copy of the block26 is stored again in L1, and its LLC state is R-C (Reused, Cached). At27 this point, the block has shown reuse in the LLC and, very likely,28 it will be reused many times in the near future. Finally, when the29 block is evicted again from the L1, the state becomes R-NC (Reused,30 Non-Cached). Subsequent requests and evictions switch between31 the R-NC and R-C states.32 Having LLC blocks classified this way, the replacement policy33 can exploit L1 temporal locality and LLC reuse. In an inclusive hier-34 archy, the replacement of a block in the LLC forces the invalidation35 of its copies in the private caches, if any, and this usually implies 36 performance degradation, assuming that blocks in L1 are being 37 actively used [23]. Therefore, the highest priority (protection) is 38 given to blocks stored in private caches. As a secondary objective, 39 the highest priority is given to blocks that have shown reuse in 40 the LLC. Hence, NRR selects victims in the following order: NR-NC,41 R-NC,NR-C,R-C. Reuse recency is taken into account by resetting 42 the reuse bit when all the non-cached blocks are marked as reused 43 (transition from R-NC to NR-NC). This way, more recently reused 44 blocks become more protected. 45 The implementation of NRR only requires one reuse bit per 46 block. The protection of private copies can be implemented in 47 various different ways [23], but one simple solution is to use the 48 presence bit-vector of the coherence directory, assuming non49 silent tag evictions of clean blocks. 50 5.2. Reused-based and fault-aware management for BDOT caches 51 Seeking to guarantee that valuable blocks remain in the LLC, 52 we devise a fault-aware management policy by distinguishing 53 between Tand Dentries. One option is to promote blocks by 54 reallocating them from Tto Dentries, if needed, to improve the 55 overall cache performance. The design choices include where the 56 promoted data comes from and which victim is chosen as a target 57 of the consequent demotion. At the same time, we want to continue 58 exploiting reuse in the simple and efficient way offered by an NRR59 like replacement algorithm, which is unaware of faulty entries. 60 Thus, our goal is to design a comprehensive cache management 61 policy, merging reuse exploitation and faulty entry management. 62 Below, we elaborate on the two mechanisms that are key to achiev63 ing this, namely block insertion/replacement and block promo64 tion/demotion. 65 5.2.1. Insertion and replacement of blocks 66 On a first insertion (LLC miss), an incoming block has not shown 67 reuse, and hence allocating it to a Tentry seems a reasonable idea. 68 Fig. 3(a) shows an example of a cache block to be inserted in a 69 4-way cache set with two Tentries (those storing qand rtags) and 70 two Dentries (those storing pand stags and the corresponding P71 and Sdata). A victim is selected among the blocks allocated to T72 entries. The baseline replacement policy dictates which of those 73 blocks (Qand R) is selected for replacement. This is equivalent to 74 predicting that the incoming block Xis not going to be reused. 75 If the reuse pattern of the block is mispredicted, block Xshould 76 be reallocated to a Dentry, to reduce its access time and transfer 77 energy in future L1 misses. This reallocation will be performed 78 using the promotion mechanism we detail in the next subsection. 79 Dealing with first insertions this way is very simple but has a 80 clear disadvantage, related to the distribution of Tand Dentries, 81 with respect to the percentage of reused and non-reused blocks. 82 For example, if the number of Tentries is small, the insertion 83 policy would place considerable pressure on these scarce entries. 84 Fig. 3. Insertion and promotion actions for a fault-aware cache management policy example in a cache set with two faulty cache entries. Lowercase and capital letters indicate tag and data, respectively. YJPDC: 3966 Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. 6A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al. / Journal of Parallel and Distributed Computing xxx (xxxx) xxx Blocks would be unavoidably forced to leave the LLC before having1 had enough time to show a reuse pattern, even though there2 are many available Dentries. In an extreme case, when all the3 entries in a set are Dtype, this cache management policy could4 not be implemented. Solving this problem is not easy. We explored5 various adaptive mechanisms in which some Dentries are used6 as T. However, it is difficult to determine the optimal number7 of Tentries, this being highly dependent on the workload. After8 carrying out several experiments (data not shown in Section 7, for9 the sake of brevity), the performance returns were disappointing10 given the required complexity.11 Given that our promotion mechanism reallocates reused blocks12 to Dentries and non-reused ones to Tentries (as we will see in the13 following subsection), we realized that the baseline NRR replace-14 ment policy itself suffices to achieve our initial goals because it pro-15 tects reused blocks. Since NRR gives lower priority to non-reused16 blocks, blocks allocated to Tentries will have more chances to be17 evicted. This implies that, with a balanced distribution between T18 and Dentries, an incoming block will have a higher probability of19 being inserted in a Tentry than in a Dentry. If the number of T20 entries in a set is very low, and even if there are no Tentries in21 a set, the mechanism still works correctly. NRR periodically resets22 the reuse bit of those blocks not present in private caches, so some23 Dentries become replacement candidates with the same priority24 as T entries. Hence, the initial insertion does not necessarily have25 to consider the nature of the entry, and our implementation relies26 only on the baseline replacement policy to select the victim block.27 5.2.2. Promotion and demotion of blocks28 A blind allocation of blocks to cache entries may result in29 valuable blocks (i.e., those with reuse) being initially allocated to30 Tentries, and vice versa. However, this undesirable situation can31 be tracked on the fly through the reuse footprint, and reversed by32 swapping a Tentry with a Dentry: when a block allocated to a33 Tentry shows reuse, we will promote ittoaDentry. Promotion34 involves a complementary demotion of the block stored in the35 selected Dentry.36 To select which block is demoted, we also rely on reuse and L137 presence information. Reused blocks should be kept in the LLC, but38 unlike in the baseline replacement policy, block demotion does not39 involve an LLC tag eviction. Furthermore, if the block is present in L1,40 losing the contents of the LLC is not critical, because there is at least41 one on-chip copy of the block, which can be supplied by a cache-to-42 cache transaction. Thus, to maximize the amount of on-chip data,43 the demotion algorithm will select the victim block among those44 present in L1. Among the blocks in L1, non-reused ones should have45 more chances of being demoted.46 Note that the promotion of a block can be performed at two47 different times: at reuse detection (i.e., on a second L1 request48 to a block stored in a Tentry) or after the second eviction from49 L1 (i.e., on eviction after reuse). Performing the promotion after50 the second request from L1 duplicates the content, as a copy of51 the block is also stored in a private cache, whilst performing the52 promotion after the L1 eviction meets the goal of maximizing the53 amount of on-chip data. Therefore, we opt for the latter and trigger54 promotions only after L1 evictions, non-silent block data evictions55 being necessary.56 The promotion/demotion process is illustrated in Fig. 3(b).57 When block R, which is stored in a Tentry, is evicted from the L158 cache and selected for promotion (i.e., its reuse bit is set), we select59 a victim among the demotion candidates (Pand Sin Fig. 3(b)).60 Once the victim is selected (Pin our example), we swap the cache61 contents in three steps: 1 discard the data entry P, writing back62 the data to memory, if dirty; 2 swap pand rtags; and 3 copy63 the data (R) to the available Dentry, which was occupied by the64 demoted block (P).65 Fig. 4. Reuse and inclusion states for a block in LLC with BDOT. 5.2.3. Summary and implementation 66 Fig. 4 illustrates the implementation of the aforementioned 67 ideas. The states of the baseline replacement algorithm shown in 68 Fig. 2 are now superstates split into Tand Dstates. The initial 69 allocation of blocks (1st use: L1 request in Fig. 4) does not take into 70 account the nature of the entry, and it solely depends on the victim 71 selection arising from reuse and L1 presence; i.e., it only depends 72 on the baseline replacement algorithm. After insertion, blocks will 73 move along NR-C,NR-NC,R-C, and R-NC superstates as they would 74 do in a cache without considering faulty entries. 75 To guarantee that high value ∧ blocks – those showing ∧ reuse – 76 remain in the LLC, the policy reallocates them from Tto Dentries 77 when they are evicted from the L1 and reside in a faulty LLC entry: 78 R-C-T state. After L1 eviction, blocks in R-C-T trigger a promotion, 79 which results in the transition to an R-NC-D state and reallocation 80 toaDentry, with the consequent demotion of another block within 81 the set to a Tentry. A block being demoted can be in any of the 82 superstates, and according to the victim selection algorithm, we 83 first demote blocks that are present in the private levels, in order 84 to maximize the amount of data available in the on-chip hierarchy. 85 As a secondary objective, the policy attempts to first demote low 86 priority blocks, that is, those without reuse. In particular, it selects 87 blocks in the following order: NR-C-D,R-C-D,NR-NC-D, and R88 NC-D.89 This reuse-based, fault-aware policy adds no extra storage over90 head to the baseline reuse-based replacement policy, as only the 91 bit indicating reuse and the presence bit vector are needed to 92 orchestrate the replacement and promotion decisions. Moreover, 93 swapping blocks only requires some extra control logic to perform 94 the following actions: first, the logic reads the demoted victim and 95 inserts the promoted block, as for conventional block insertion, 96 and, then, it writes back the tag of the demoted block. Promoting 97 blocks after L1 eviction implies non-silent eviction of data blocks. 98 This overhead does not affect latency, as L1 replacements are 99 not in the critical path, and has a negligible impact on energy 100 consumption. 101 YJPDC: 3966 Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al. / Journal of Parallel and Distributed Computing xxx (xxxx) xxx 7 Fig. 5. Modeled 8-core CMP. The fault-aware cache management technique here presented1 could be implemented on top of other replacement algorithms2 (such as LRU or NRU). We decided to rely on NRR because of its3 simple, yet efficient implementation, and because it fits the general4 principles behind our ideas. Finally, and regarding the reallocation5 from Tto Dentries and vice versa, other policies are also possible.6 For example, instead of relying on the reuse information of the7 blocks, a future use predictor [46] could be utilized to decide which8 blocks should be allocated to Dentries, or a dead block predic-9 tor [27] could be used to indicate which blocks may be demoted10 to Tentries, but these solutions add complexity to the cache logic11 as well as requiring more storage overhead.12 6. Methodology13 6.1. Overview of the system14 Our baseline system consists of a tiled CMP, with an inclusive15 two-level cache hierarchy, where the second level cache or LLC16 is shared and distributed among the processor cores. Tiles are17 interconnected by means of a mesh. Each tile has a processor core18 with a private first level cache (L1) split into instructions and data,19 and a bank of the shared LLC, both connected to the router (Fig. 5).20 Similarly to most CMP, the write-policy for L1 data caches is write-21 back because other policies, such as write-through, may collapse22 the interconnection network [19]. The mesh will have to convoy23 every single store from the cores to the LLC banks to guarantee24 content inclusion. The CMP includes two memory controllers lo-25 cated at the edges of the chip. Table 2 shows the parameters of26 the baseline processor, memory hierarchy, and interconnection27 network.28 We assume it runs at a frequency of 1 GHz with an operat-29 ing voltage of 0.5 V. Note that the DRAM module voltage is not30 scaled like the rest of the system, and hence, the relative speed31 of main memory with respect to the chip increases as the voltage32 decreases. This model is consistent with prior work [5,45].33 Our baseline coherence protocol relies on a full-map directory34 with Modified, Exclusive, Shared, Invalid (MESI) states. We use35 explicit eviction notification of both shared and exclusively owned36 blocks. L1 caches are built with robust SRAM cells that can run37 reliably at low or near-threshold voltages, while LLC data banks38 are built with conventional 6T SRAM cells and, therefore, they are39 sensitive to failures [30].40 As in previous studies [5,45], we assume that the LLC tag arrays41 are hardened by using upsized cells such as 8T [10]. The baseline42 LLC replacement policy is Not-Recently Used (NRU) [37] extended43 with private copy protection [23]. We implement this protection44 by using coherence directory information updated by non-silent45 L1 block evictions.46 6.2. Experimental set-up 47 Regarding our experimental set-up, we model the CMP system 48 described in Table 2. We use Simics [34] in combination with 49 GEMS [36] to simulate the on-chip memory hierarchy and inter50 connection network, and DRAMSim2 [40] to simulate the DDR3 51 DRAM in detail. To obtain timing, area, and energy consumption, 52 we use the McPAT framework [33] for the on-chip components, 53 and DRAMSim2 for the DRAM module. We extend the Ruby module 54 (GEMS) to simulate the cache swaps in detail in order to take into 55 account their dynamic energy overhead. 56 We use a set of 20 multiprogrammed workloads built as random 57 combinations of the 29 SPEC CPU 2006 applications [21], with no 58 special distinction between integer and floating point programs. 59 Each application appears on average 5.5 times with a standard 60 deviation of 2.5. Programs were run on a real machine until com61 pletion with the reference inputs. Hardware counters were used to 62 locate the end of the initialization phase. Every multiprogrammed 63 mix was run for as many instructions as the longest initialization 64 phase, and a checkpoint was created at this point. We then run 65 cycle-accurate simulations including 300 million cycles to warm 66 up the memory hierarchy and 700 million cycles for data collection. 67 We also include a selection of shared-memory parallel ap68 plications from PARSEC [8] with a significant memory footprint 69 (MPKILLC ≥1.0) when running the sim-large input in the baseline 70 system: canneal (MPKILLC =4.3), ferret (1.6), streamclus71 ter (1.0), and vips (1.2). We proceed in a similar way to that 72 used for multiprogrammed workloads3and run 300 million cycles 73 to warm up the memory structures once the parallel phase has 74 started, and then collect statistics for 700 million cycles. 75 One challenge for analyzing fault mitigation techniques is the 76 large set of required simulations. Running all workloads and simu77 lated models combinations for a single fault map can lead to wrong 78 results, as other authors have described [20,41]. For example, if 79 all the faults affect to the most/least frequently accessed cache 80 sets, the observed speed-up would be much lower/higher than in 81 reality. 82 To address this issue, we rely on statistical sampling to generate 83 random fault maps and run Monte Carlo experiments to guarantee 84 a 5% margin of error with a confidence level of 95% [22]. In other 85 words, the number of samples is increased as necessary to reach 86 the target margin of error within the desired level of confidence. 87 For our workloads, simulated models, metrics, margin of error and 88 confidence level, each point of the design space has to be simulated 89 between 20 and 30 times, each one with a different fault map. 90 We pick the 5% margin of error and the 95% confidence level as a 91 good trade-off between simulation time and accuracy, increasing 92 both has a large impact in the required number of simulations. 93 To ensure all simulations have similar numbers of faults but at 94 different locations, we compute the faultiness of each memory 95 cell randomly and independently of other cells [2,12]. Finally, we 96 consider that the number and location of faulty cells do not change 97 during workload execution. 98 7. Evaluation 99 This section evaluates the effectiveness of the proposed BDOT 100 management technique for LLC caches in terms of MPKI, adding 101 up the misses in all LLC banks and dividing by the aggregated 102 instruction count of all cores. Later, in Section 8, we analyze the 103 impact on system performance, area, and energy. 104 3We observed that no OS activity appeared when our parallel applications were run and the ratio of CPU utilization between the different threads was practically constant across the simulations. YJPDC: 3966 Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. 8A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al. / Journal of Parallel and Distributed Computing xxx (xxxx) xxx Fig. 6. Normalized MPKI (average for SPEC mixes) with respect to Robust for the different proposals and cell types. Average MPKI for Robust: 5.09. To assess the effectiveness of our proposals, we include sev-1 eral additional configurations. First, as an upper bound in per-2 formance, a robust cache built with unrealistically robust cells3 (Robust); i.e., cells that operate at ultra-low voltages with neither4 failures nor power or area overheads, which corresponds to a5 perfect unattainable solution. Then, we also include block disabling6 (BD), as our proposal emerges from it. Finally, we add results for7 word disabling (WD) [45]. Word disabling is a more complex tech-8 nique that combines consecutive faulty cache entries to recreate9 fully functional ones, at the cost of reducing the cache capacity.10 Section 9presents a comprehensive discussion of this and other11 techniques versus our proposals.12 In summary, we consider the following configurations:13 •Robust: reference system; the LLC is built with unrealistically14 robust cells. All data are presented with respect to this sys-15 tem.16 •BD: system implementing block disabling, as presented in17 Section 3, with NRU replacement.18 •BDOT-NRU: system implementing block disabling with oper-19 ational tags, as presented in Section 4, with NRU replacement.20 •BDOT-NRR: system implementing BDOT with NRR replace-21 ment, as presented in Section 5.1.22 •BDOT-NRR-FA: system implementing BDOT with fault-aware23 NRR replacement, as presented in Section 5.2.24 •WD: system implementing word disabling with NRU replace-25 ment [45].26 As in the case of NRR, the NRU implementation also includes27 private copy protection. Our detailed results include multipro-28 grammed workloads (the 20 SPEC CPU 2006 mixes) and parallel29 workloads (the 4 selected PARSEC applications), for the five cell30 types considered (C6, C5, C4, C3, and C2).31 7.1. Multiprogrammed workloads32 Fig. 6 shows the LLC MPKI results for the multiprogrammed33 workloads.34 BD is a valid solution for a cache with few defective entries,35 like one built with C6 cells, where the average MPKI penalization36 is 23.9%. However, this penalization increases rapidly with the37 number of faulty entries, reaching 136% for C2. Using the tags of the38 defective LLC entries to keep the coherence state of blocks stored39 in L1 allows BDOT-NRU to incur fewer MPKI than BD for C2, but40 it does not offer any advantage (the MPKI value increases) for the41 rest of the cells.42 To differentiate and quantify the benefit of a reuse-based re43 placement and our fault-aware cache management policy, we first 44 implement NRR on top of BDOT (BDOT-NRR), without taking into 45 account the nature of cache entries (faulty or non-faulty). This 46 naive implementation offers a slight improvement with respect to 47 BDOT-NRU for all cell types, but it is still worse than BD, except for 48 C2, as in the case of BDOT-NRU. The explanation for this behavior 49 is the blind allocation of blocks to entries, without taking into 50 account whether the entry can store only the tag (T) or both the 51 tag and the data (D). Allocating a block that shows reuse to a T52 entry implies that all the requests to that block are forwarded to 53 the next level (in this case, off-chip). Besides, due to the reused54 based policy, this block will remain in the defective entry of the 55 LLC, protected by the replacement algorithm. However, blocks with 56 reuse allocated to Dentries are also protected from replacement, 57 and that explains why the relative differences between BDOT-NRR 58 and BDOT-NRU are larger when using larger cells (i.e., with less 59 faults, like C6 and C5). 60 BDOT-NRR-FA addresses this issue, adding the information of 61 defective entries to the cache management policy. The penalization 62 in terms of MPKI is 14.6%, 15.1%, 16%, 18.3%, and 37.3% lower than 63 with BD for C6, C5, C4, C3, and C2, respectively. If we compare 64 BDOT-NRR-FA with BDOT-NRR, there are 20% fewer MPKI, irre65 spective of the cell type, demonstrating the goodness of the design. 66 Regarding WD, although there are significant differences in 67 terms of the number of defective entries among the cell types 68 considered (Table 1), the MPKI for the different configurations is 69 almost constant. Two reasons explain this behavior: (i) a single 70 defective cell forces the entry to be classified as faulty, and (ii) 71 the number of defective cells per entry is usually small (three on 72 average for the smallest cell: C2 [15]) and, therefore, very often 73 blocks are successfully stored by combining two consecutive en74 tries. Thus, the average number of ways per set in our system when 75 implementing WD is eight across the different cell configurations. 76 Compared to BD, WD obtains better results when the average 77 number of defective entries is greater than half, which is the case 78 of cells C4, C3, and C2, as shown in Table 1. BDOT-NRR-FA lowers 79 the MPKI with respect to WD by 20%, 16.1%, 8.5%, and 3.4%, for 80 C6, C5, C4, and C3, respectively. WD only beats BDOT-NRR-FA in 81 caches with a high number of defective cells (C2, where on average 82 90% of the entries are faulty). However, BDOT-NRR-FA requires no 83 additional overhead, whilst WD requires additional storage and 84 logic to reconstruct blocks. 85 7.2. Parallel workloads 86 Fig. 7 shows the relative LLC MPKI for the parallel workloads, 87 with respect to the baseline. As with multiprogrammed workloads, 88 BDOT-NRR-FA has a lower average MPKI than BD and non fault89 aware implementations of BDOT. In particular, BDOT-NRR-FA im90 proves MPKI with respect to BD by 5%, 5%, 9.6%, 19.2%, and 54.2% on 91 average for C6, C5, C4, C3, and C2, respectively. Comparing with the 92 multiprogrammed workloads, the relative MPKI numbers shown in 93 Fig. 7 are larger, moving away from the Robust system to a greater 94 extent for all cell types, even for the winning alternatives (WD 95 and BDOT-NRR-FA). But it is worth noting that the absolute MPKI 96 values for the parallel applications considered are low (Section 6), 97 which makes the relative increases appear more substantial. 98 Upon closer examination of the results, we can make some 99 interesting observations. Fig. 8 shows the LLC MPKI analysis per 100 application for the different cell types. BD is better than plain 101 BDOTs (BDOT-NRU, BDOT-NRR) in ∧ C6–C3 cells (C3 in canneal 102 is an exception), while in cell C2 the trend clearly reverses. On 103 the contrary, BDOT-NRR-FA is better than BD in most cases, being 104 vips the only exception (cells ∧ C6–C3), and giving very noticeable 105 reductions in the smallest cell C2. For vips, BDOT-NRR-FA only 106 YJPDC: 3966 Please cite this article as: A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al., A fault-tolerant last level cache for CMPs operating at ultra-low voltage, Journal of Parallel and Distributed Computing (2018), https://doi.org/10.1016/j.jpdc.2018.10.010. A. Ferrerón, J. Alastruey-Benedé, D. Suárez Gracia et al. / Journal of Parallel and Distributed Computing xxx (xxxx) xxx 9 Fig. 7. Normalized MPKI (average for PARSEC) with respect to Robust for the different proposals and cell types. Average MPKI for Robust: 2.01. beats BD in C2 because its image processing algorithm shows1 very little reuse with a small working set. In such non-demanding2 environment, BD can store the vips working set.3 Finally, the costly WD shows a similar tendency to that ob-4 served with multiprogrammed workloads, with a relatively5 constant performance independently of the cell type. In this case, 6 BDOT-NRR-FA beats WD when using C6 or C5 (12.7% and 6.6% 7 lower MPKI values, respectively), but it cannot reach WD perfor8 mance for C4, C3, or C2 (5.5%, 12.4%, and 33.3% higher MPKI values, 9 respectively). 10 8. System impact 11 This section analyzes the impact of our proposals on the system 12 in terms of performance, area, and energy consumption. As in the 13 previous section, we present results relative to the Robust system 14 and compare with the BD and WD mechanisms. 15 8.1. Performance 16 Fig. 9 shows the performance relative to the robust cell for both 17 multiprogrammed and parallel workloads. 18 For multiprogrammed workloads (Fig. 9(a)), performance fol19 lows the same trend as MPKI, BDOT-NRR-FA being the best design 20 option except in the case of C2 cells, for which WD outperforms 21 BDOT-NRR-FA by 2.2%. In particular, BDOT-NRR-FA shows a perfor22 mance degradation with respect to the Robust reference system of 23 1.3%, 2%, 3.4%, 4.3%, and 6.9% for C6, C5, C4, C3, and C2, respectively, 24 or, in other words, a performance improvement with respect to BD 25 of 2%, 2.2%, 2.7%, 3.6%, and 13.1%. 26 Fig. 8. Per-application normalized MPKI (PARSEC) with respect to Robust for the different proposals and cell types. Average MPKIs for Robust: 4.26, 1.59, 1.0 and 1.19, for canneal,ferret,streamcluster, and vips, respectively.