Search

The memory hierarchy has a high impact on the performance and power consumption in the system. Moreover, current embedded systems, included in mobile devices, are specifically designed to run multimedia applications, which are memory intensive. This increases the pressure on the memory subsystem and affects the performance and energy consumption. In this regard, the thermal problems, performance degradation and high energy consumption, can cause irreversible damage to the devices. We address the optimization of the whole memory subsystem with three approaches integrated as a single methodology. Firstly, the thermal impact of register file is analyzed and optimized. Secondly, the cache memory is addressed by optimizing cache configuration according to running applications and improving both performance and power consumption. Finally, we simplify the design and evaluation process of general-purpose and customized dynamic memory manager, in the main memory. To this aim, we apply different evolutionary algorithms in combination with memory simulators and profiling tools. This way, we are able to evaluate the quality of each candidate solution and take advantage of the exploration of solutions given by the optimization algorithm. We also provide an experimental experience where our proposal is assessed using well-known benchmark applications.

Nowadays, embedded systems are provided with cache memories that are large enough to influence in both performance and energy consumption as never occurred before in this kind of systems. In addition, the cache memory system has been identified as a component that improves those metrics by adapting its configuration according to the memory access patterns of the applications being run. However, given that cache memories have many parameters which may be set to a high number of different values, designers are faced with a wide and time-consuming exploration space. In this paper, we propose an optimization framework based on Grammatical Evolution (GE) which is able to efficiently find the best cache configurations for a given set of benchmark applications. This metaheuristic allows an important reduction of the optimization runtime obtaining good results in a low number of generations. Besides, this reduction is also increased due to the efficient storage of evaluated caches. Moreover, we selected GE because the plasticity of the grammar eases the creation of phenotypes that form the call to the cache simulator required for the evaluation of the different configurations. Experimental results for the Mediabench suite show that our proposal is able to find cache configurations that obtain an average improvement of 62 % versus a real world baseline configuration.

Most modern multi-core processors provide a shared last level cache (LLC) where data from all cores are placed to improve performance. However, this opens a new challenge for cache management, owing to cache pollution. With cache pollution, data with weak temporal locality can evict other data with strong temporal locality when both are mapped into the same cache set. In this article, we propose page reusability-based cache partitioning (PRCP) for multi-core systems to maximize cache utilization by minimizing cache pollution. To achieve this, PRCP divides pages into two groups: (1) highly-reused pages and (2) lowly-reused pages. The reusability of each page is collected online via periodic page table scans. PRCP then dynamically partitions the shared cache into two corresponding areas using page coloring technique. We have implemented PRCP in Linux kernel and evaluated it using SPEC CPU2006 benchmarks. The results show that our scheme can achieve comparable performance to the optimal offline MRC-guided process-based cache partitioning scheme without a priori knowledge of workloads.

Observational models enable the analysis of information flow properties against side channels. Relational testing has been used to validate the soundness of these models by measuring the side channel on states that the model considers indistinguishable. However, unguided search can generate test states that are too similar to each other to invalidate the model. To address this we introduce observation refinement, a technique to guide the exploration of the state space to focus on hardware features of interest. We refine observational models to include fine-grained observations that characterize behavior that we want to exclude. States that yield equivalent refined observations are then ruled out, reducing the size of the space. We have extended an existing model validation framework, Scam-V, to support refinement. We have evaluated the usefulness of refinement for search guidance by analyzing cache coloring and speculative leakage in the ARMv8-A architecture. As a surprising result, we have exposed SiSCLoak, a new vulnerability linked to speculative execution in Cortex-A53.

Στην παρούσα διατριβή προτείνονται μέθοδοι διαχείρισης των κοινόχρηστων πόρων σε υπολογιστικά συστήματα όπου πολλαπλοί επεξεργαστές μοιράζονται το ίδιο ολοκληρωμένο (Chip Multiprocessors - CMPs). Ενώ μέχρι πρόσφατα ο σχεδιασμός ενός υπολογιστικού συστήματος στόχευε στην ικανοποίηση των απαιτήσεων μόνο μιας εφαρμογής ανά χρονική περίοδο τώρα πια απαιτείται και η εξισορρόπηση των απαιτήσεων διαφορετικών εφαρμογών που ανταγωνίζονται για την κατοχή των ίδιων πόρων. Σε πολλές περιπτώσεις όμως αυτό δεν αρκεί από μόνο του. Ακόμη και αν επιτευχθεί κάποιος ιδανικός διαμοιρασμός του πόρου, αν δεν βελτιστοποιηθεί ο τρόπος με τον οποίο χρησιμοποιούν οι επεξεργαστές τον κοινόχρηστο πόρο, δεν θα καταφέρει να εξυπηρετήσει ικανοποιητικά το αυξημένο φορτίο. Για να αντιμετωπιστούν τα προβλήματα που πηγάζουν από τον διαμοιρασμό των κοινοχρήστων πόρων στην παρούσα εργασία προτείνονται τρεις εναλλακτικοί μηχανισμοί διαχείρισης. Η πρώτη μεθοδολογία εισάγει μια νέα θεωρητική μοντελοποίηση του διαμοιρασμού της κρυφής μνήμης η οποία μπορεί να χρησιμοποιηθεί παράλληλα με την εκτέλεση των προγραμμάτων που διαμοιράζονται την κρυφή μνήμη. Η μεθοδολογία αξιοποιεί στην συνέχεια αυτήν την μοντελοποίηση για να ελέγξει τον διαμοιρασμό της κρυφής μνήμης και να επιτύχει δικαιοσύνη στο πως κατανέμεται ο χώρος της κρυφής μνήμης μεταξύ των επεξεργαστών. Η δεύτερη μεθοδολογία παρουσιάζει μια νέα τεχνική για την πρόβλεψη της τοπικότητας των προσπελάσεων της κρυφής μνήμης. Καθώς η τοπικότητα είναι η βασική παράμετρος που καθορίζει την χρησιμότητα των δεδομένων της κρυφής μνήμης χρησιμοποιώντας αυτήν την τεχνική πρόβλεψης μπορούν να οδηγηθούν μηχανισμοί διαχείρισης που βελτιώνουν την αξιοποίηση του χώρου της κρυφής μνήμης. Στα πλαίσια της μεθοδολογίας παρουσιάζουμε έναν τέτοιο μηχανισμό, ο οποίος στοχεύει στην ελαχιστοποίηση των αστοχιών της κρυφής μνήμης μέσω μιας νέας πολιτικής αντικατάστασης. Η τελευταία μεθοδολογία που παρουσιάζεται είναι μια μεθοδολογία για την μείωση της κατανάλωσης ενέργειας της ουράς εντολών που είναι μια από τις πιο ενεργειακά απαιτητικές δομές του επεξεργαστή. Στα πλαίσια της μεθοδολογίας δείχνεται ότι το κλειδί για την αποδοτική μείωση της κατανάλωσης ενέργειας της ουράς εντολών βρίσκεται στην αλληλεπίδρασή της με το υποσύστημα μνήμης. Με βάση αυτό το συμπέρασμα παρουσιάζουμε έναν νέο μηχανισμό δυναμικής διαχείρισης του μεγέθους της ουράς εντολών ο οποίος συνδυάζει επιθετική μείωση της κατανάλωσης ενέργειας του επεξεργαστή με διατήρηση της υψηλής απόδοσης του.

Efficient system-wide memory management is an important challenge for over-commitment based hosting in virtualized systems. Due to the limitation of memory domains considered for sharing, current deduplication solutions simply cannot achieve system-wide deduplication. Popular memory management techniques like sharing and ballooning enable important memory usage optimizations individually. However, they do not complement each other and, in fact, may degrade individual benefits when combined. We propose $\mathsf{Synergy}$Synergy, a hypervisor managed caching system to improve memory efficiency in over-commitment scenarios. $\mathsf{Synergy}$Synergy builds on an exclusive caching framework to achieve, for the first time, system-wide memory deduplication. $\mathsf{Synergy}$Synergy also enables the co-existence of the mutually agnostic ballooning and sharing techniques within hypervisor managed systems. Finally, $\mathsf{Synergy}$Synergy implements a novel file-level eviction policy that prevents hypervisor caching benefits from being squandered away due to partial cache hits. $\mathsf{Synergy}$Synergy's cache is flexible with configuration knobs for cache sizing and data storage options, and a utility-based cache partitioning scheme. Our evaluation shows that $\mathsf{Synergy}$Synergy consistently uses 10 to 75 percent lesser memory by exploiting system-wide deduplication as compared to inclusive caching techniques and achieves application speedup of 2x to 23x. We also demonstrate the capabilities of $\mathsf{Synergy}$Synergy to increase VM packing density and support for dynamic reconfiguration of cache partitioning policies.

We consider a basic caching system, where a single server with a database of N files (e.g. movies) is connected to a set of K users through a shared bottleneck link. Each user has a local cache memory with a size of M files. The system operates in two phases: a placement phase, where each cache memory is populated up to its size from the database, and a following delivery phase, where each user requests a file from the database, and the server is responsible for delivering the requested contents. The objective is to design the two phases to minimize the load (peak or average) of the bottleneck link. We characterize the rate-memory tradeoff of the above caching system within a factor of 2.00884 for both the peak rate and the average rate (under uniform file popularity), where the best proved characterization in the current literature gives a factor of 4 and 4.7 respectively. Moreover, in the practically important case where the number of files (N) is large, we exactly characterize the tradeoff for systems with no more than 5 users, and characterize the tradeoff within a factor of 2 otherwise. We establish these results by developing novel information theoretic outer-bounds for the caching problem, which improves the state of the art and gives tight characterization in various cases.

Automotive and, especially, the aerospace industry requires reducing the size, weight, and power (SWaP) of the embedded electronics. Additionally, both industries demand an increment of the embedded electronics’ power capability and low data transfer latency. Multi-core processors’ (MCP) advent allows integrating multiple applications in the same System on Chip (SoC) in high-performance computers. The usage of MCP processor in safety-critical systems such as Flight Control Computers and Autonomous Driving depends on solving determinism issues related to the processor’s resource contention. The usage of a resource from one core can impact the other cores, preventing the delivery of the algorithm output at a specific time, and this failure can lead to a catastrophic event. This paper introduces an analysis of interference paths to map the possible resource contention in MCP and presents an approach to mitigate the low-level cache (LLC) contention using the page coloring technique.

Consolidating hard real-time systems onto modern multi-core Systems-on-Chip (SoC) is an open challenge. The extensive sharing of hardware resources at the memory hierarchy raises important unpredictability concerns. The problem is exacerbated as more computationally demanding workload is expected to be handled with real-time guarantees in next-generation Cyber-Physical Systems (CPS). A large body of works has approached the problem by proposing novel hardware redesigns, and by proposing software-only solutions to mitigate performance interference.Strong from the observation that unpredictability arises from a lack of fine-grained control over the behavior of shared hardware components, we outline a promising new resource management approach. We demonstrate that it is possible to introduce Programmable Logic In-the-Middle (PLIM) between a traditional multi-core processor and main memory. This provides the unique capability of manipulating individual memory transactions. We propose a proof-of-concept system implementation of PLIM modules on a commercial multi-core SoC. The PLIM approach is then leveraged to solve long-standing issues with cache coloring. Thanks to PLIM, colored sparse addresses can be re-compacted in main memory. This is the base principle behind the technique we call Cache Bleaching. We evaluate our design on real applications and propose hypervisor-level adaptations to showcase the potential of the PLIM approach.

On modern multi-core machines, page coloring has been used to alleviate the competition at Last Level Cache (LLC). However, the latest development of CPU architecture has brought new issues to page coloring. Firstly, in the case of three-level cache, previous works about page coloring did not discuss the impact on L2 cache of color allocation and the competition for L2 cache is not considered concurrently under hyper-threading. In addition, as the last level cache structure is changed from shared to slice-based and undocumented hash function is applied, page coloring is more complex and slice information is also not fully utilized. This paper presents solutions to these issues. Firstly, by making small changes to the traditional page coloring, the problem that page coloring may waste L2 cache is alleviated. At the same time, we rethink the vertical allocation of L2 cache and LLC in page coloring under hyper-threading, and discuss the impact of color allocation on programs, especially those with different sensitivity to L2 cache and LLC. Finally, we make full use of slice information and propose Partial Conflict Color (PCC). At the same time, we also propose a fast method to obtain PCC. Experiments show that using PCC can improve system performance when the number of colors is insufficient.

One of the biggest challenges in multicore platforms is shared cache management, especially for data-dominant applications. Two commonly used approaches for increasing shared cache utilization are cache partitioning and loop tiling. However, state-of-the-art compilers lack efficient cache partitioning and loop tiling methods for two reasons. First, cache partitioning and loop tiling are strongly coupled together, and thus addressing them separately is simply not effective. Second, cache partitioning and loop tiling must be tailored to the target shared cache architecture details and the memory characteristics of the corunning workloads. To the best of our knowledge, this is the first time that a methodology provides (1) a theoretical foundation in the above-mentioned cache management mechanisms and (2) a unified framework to orchestrate these two mechanisms in tandem (not separately). Our approach manages to lower the number of main memory accesses by an order of magnitude keeping at the same time the number of arithmetic/addressing instructions to a minimal level. We motivate this work by showcasing that cache partitioning, loop tiling, data array layouts, shared cache architecture details (i.e., cache size and associativity), and the memory reuse patterns of the executing tasks must be addressed together as one problem, when a (near)-optimal solution is requested. To this end, we present a search space exploration analysis where our proposal is able to offer a vast deduction in the required search space.

Considering cache enabled networks, optimal content placement minimizing the total cost of communication in such networks is studied, leading to a surprising fundamental 0–1 law for non-redundant cache placement strategies, where the total cache sizes associated with each file does not exceed the file size. In other words, for such strategies, we prove that any non-redundant cache placement strategy can be transformed, with no additional cost, to a strategy in which at every node, each file is either cached completely or not cached at all. Moreover, we obtain a sufficient condition under which the optimal cache placement strategy is in fact non-redundant. This result together with the 0–1 law reveals that situations exist, where optimal content placement is achieved just by uncoded placement of whole files in caches.

Cache replacement policies and cache partitioning are well-known cache management techniques which aim to eliminate inter- and intra-application contention caused by co-running applications, respectively. Since replacement policies can change applications’ behavior on a shared last-level cache, they have a massive impact on cache partitioning. Furthermore, cache partitioning determines the capacity allocated to each application affecting incorporated replacement policy. However, their interoperability has not been thoroughly explored. Since existing cache partitioning methods are tailored to specific replacement policies to reduce overheads for characterization of applications’ behavior, they may lead to suboptimal partitioning results when incorporated with the up-to-date replacement policies. In cache partitioning, miss curve estimation is a key component to relax this restriction which can reflect the dependency between a replacement policy and cache partitioning on partitioning decision. To tackle this issue, we propose a replacement policy adaptable miss curve estimation (RME) which estimates dynamic workload patterns according to any arbitrary replacement policy and to given applications with low overhead. In addition, RME considers asymmetry of miss latency by miss type, thus the impact of miss curve on cache partitioning can be reflected more accurately. The experimental results support the efficiency of RME and show that RME-based cache partitioning cooperated with high-performance replacement policies can minimize both inter- and intra-application interference successfully.

Reuse distance is an important metric for analytical estimation of cache miss rate. To find the miss rate of a particular cache, the reuse distance profile has to be measured for that particular level and configuration of the cache. Significant amount of simulation time and overhead can be reduced if we can find the miss rate of higher level cache like L2 cache from the RD profile with respect to a lower level cache (i.e., cache that is closer to the processor) such as L1. The objective of this paper is to give an analytical method to find the miss rate of L2 cache for various configurations from the RD profile with respect to L1 cache. We consider all three types of cache inclusion policies namely (i) Strictly Inclusive, (ii) Mutually Exclusive and (iii) Non-Inclusive Non-Exclusive policy. We first prove some general results relating the RD profile of L1 cache to that of L2 cache. We use probabilistic analysis for our derivations. We validate our model against simulations, using the multi-core simulator Sniper with the PARSEC and the SPLASH benchmark suites.

The world is more connected than it ever has been before, and with our pocket supercomputers and IoT (Internet of Things) future, the next generation of the web might just be delivered in a peer-to...

In recent years, researches focus on addressing the query bottleneck issue using semantic cache. However, the challenges of this method are how to increase cache hit ratio, decrease the query processing time, and address cache consistency issue. In this paper, we construct segment access-aware dynamic semantic cache for relational databases. Some definitions of semantic segment, probe query, and remainder query are proposed to describe the semantic cache. Then, estimation of the query result is proposed. Next, cache access algorithm of our proposed segment access-aware dynamic semantic cache is presented in case of cache exact hit, cache extended hit, cache partial hit and cache miss. Cache item with effective lifecycle tag is proposed to address cache consistency issue. Finally, experimental results show that this approach performs better than regular semantic cache and decisional semantic cache.

The aim of the hierarchical cache memories that are equipped for GPUs is the management of irregular memory access patterns for general purpose workloads. The level-1 data cache (L1D) of the GPU plays an important role for its ability in the provision of high bandwidth and low-latency data accesses. Unfortunately, the GPU L1D may become a performance bottleneck due to facing many performance challenges such as cache contention and resource congestion. These critical issues come from a large number of simultaneous requests from the SIMT cores to the limited-capacity L1D. We observe that many applications have a large number of requests with a very low reuse probability, resulting in the GPU performance degradation. To overcome these challenges, we propose an efficient cache bypassing mechanism that can periodically filter the access stream and make an accurate bypassing decision to improve the efficiency of the L1D. The proposed technique uses a small storage amount to save the tag array of the L1D for the early miss prediction before it makes the bypassing decision. The experiment results reveal that the proposed technique significantly increases the cache efficiency and the GPU performance.

For cache analytical modeling, the stack distance theory is widely utilized to predict LRU-cache behaviors. Typically, the stack distance histogram collecting is implemented by profiling memory references. However, the profiled memory references merely reflect instruction fetching and load/store executions, which only represent the memory accesses to first-level (L1) caches. That is why these traces cannot be applied directly to construct stack distance histograms for downstream (L2 and L3) caches. Therefore, this paper proposes a stack distance probability model to extend the stack distance theory to the multi-level LRU cache behavior predictions. The inputs of our model are the L1 cache stack distance histograms and the multi-level LRU cache configurations. The outputs are the L2 and L3 cache stack distance histograms, with which the conflict misses in L2 and L3 caches can be quantified quickly and precisely. 15 benchmarks chosen from Mobybench 2.0, Mibench I and Mediabench II are used to evaluate the accuracy of our model. Compared to the simulation results from Gem5 in AtomicSimpleCPU mode, the average absolute error of predicting cache misses in the I/D shared L2 cache is less than 5% while that of estimating the L3 cache misses is less than 7%. Furthermore, contrast to the time overhead of Gem5 AtomicSimpleCPU simulations, our model can speed up the cache miss prediction about x100 on average.

With the rapid growth of Internet services in smart cities, large network flow has caused network congestion among users, thereby deteriorating network service quality and user experience. In this study, a distributed proxy cache management platform based on autonomous decision is proposed. The platform realizes highly efficient automatic cache management by taking the advantages of autonomous perception and decision. First, the platform establishes the autonomous management framework of proxy cache on the basis of the idea of feedback loop. Next, the URL is distributed evenly among cache nodes through the hash ring storage mechanism with virtual nodes. Cache status adjustment strategies are made based on historical status sequences and the gray prediction model. A method that is used to predict content hot-rank based on domain name set is proposed to reduce loads of cache nodes. Second, the platform designs a distributed proxy cache management system by depending on the autonomous management framework of proxy cache and the cache management mechanism of autonomous decision, and the Cache Hot Spots Migrate algorithm is suggested for the dynamic migration and integration of virtual nodes on the hash ring. A system knowledge base is established through status sequence and corresponding adjustment strategies. Finally, experimental results on the hash ring, content hot-rank prediction, and adjustment of autonomous decision of cache status are analyzed, thereby confirming that the distributed proxy cache management mechanism based on autonomous decision could manage cache nodes effectively and automatically, and could improve the overall performance of the system.

Flash memory-based SSD-RAIDs are swiftly replacing conventional hard disk drives by exhibiting improved performance and stability, especially in I/O-intensive environments. However, the variations in latency and throughput occurring due to uncoordinated internal garbage collection cripples further boosting of performance. In addition, the unwanted variations in each SSD can influence the overall performance of the entire flash storage adversely. This performance bottleneck can be essentially reduced by an internal write cache in the RAID controller designed prudently by considering the crucial device characteristics. The state-of-the-art cache write for the RAID controller fails to incorporate device characteristics of flash memory-based SSDs and mitigates the performance gain. In this paper, we propose a novel cache design namely Layout-Aware Write Cache (LAWC) to overcome the performance barrier inculcated by independent garbage collections. LAWC implements (i) improved I/O scheduling for logically partitioned write caches, (ii) a destage write synchronization mechanism to allow individual write caches to flush write blocks into the SSD array in a coordinated manner, and (iii) a two-level hybrid cache algorithm utilizing small front level cache for the improved write cache efficiency. LAWC shows significant reduction in response time by 82.39 percent on RAID-0 and 68.51 percent on RAID-5 types of SSDs when compared with state-of-the-art write cache algorithms.

In wireless mobile Ad Hoc networks, cooperative cache management is considered as an efficient technique to increase data availability and improve access latency. This technique is based on coordination and sharing of cached data between nodes belonging to the same area. In this paper, we studied the cooperative cache management strategies. This has enabled us to propose a collaborative cache management scheme for mobile Ad Hoc networks, based on service cache providers (SCP), called cooperative caching based on service providers (CCSP). The proposed scheme enabled the election of some SCPs mobile nodes, which receive cache’s summaries of neighboring nodes. Thus, nodes belonging to the same zone can locate easily cached documents of that area. The election mechanism used in this approach is executed periodically to ensure load balancing. We further provided an evaluation of the proposed solution, in terms of request hit rate, byte hit rate and time gains. Compared with other caching management schemes, the simulation results show that the proposed CCSP scheme improves significantly the cache effectiveness and the network performances. This is achieved by improving data availability and reducing both overall network load and latencies perceived by end users.

To improve the performance of mobile video delivery, caching layered videos at a site near to mobile end users (e.g., at the edge of mobile service provider's backbone) was advocated because cached videos can be delivered to mobile users with a high quality of experience, e.g., a short latency. How to optimally cache layered videos based on caching price, the available capacity of cache nodes, and the social features of mobile users, however, is still a challenging issue. In this paper, we propose a novel edge caching scheme to cache layered videos. First, a framework to cache layered videos is presented in which a cache node stores layered videos for multiple social groups, formed by mobile users based on their requests. Due to the limited capacity of the cache node, these social groups compete with each other for the number of layers they request to cache, aiming at maximizing their utilities while all mobile users in each group share the cost involved in the cache of video contents. Second, a Stackelberg game model is developed to study the interaction among multiple social groups and the cache node, and a noncooperative game model is introduced to analyze the competition among mobile users in different social groups. Third, leveraging the backward induction method, the optimal strategy of each player in the game model is proposed. Finally, simulation results show that the proposed method outperforms the exiting counterparts with a higher hit ratio and lower delay of delivering video contents.

Cache has long been used to minimize the latency of main memory accesses by storing frequently used data near the processor. Processor performance depends on the underlying cache performance. Therefore, significant research has been done to identify the most crucial metrics of cache performance. Although the majority of research focuses on measuring cache hit rates and data movement as the primary cache performance metrics, cache utilization is significantly important. We investigate the application’s locality using cache utilization metrics. Furthermore, we present cache utilization and traditional cache performance metrics as the program progresses providing detailed insights into the dynamic application behavior on parallel applications from four benchmark suites running on multiple cores. We explore cache utilization for APEX, Mantevo, NAS, and PARSEC, mostly scientific benchmark suites. Our results indicate that 40% of the data bytes in a cache line are accessed at least once before line eviction. Also, on average a byte is accessed two times before the cache line is evicted for these applications. Moreover, we present runtime cache utilization, as well as, conventional performance metrics that illustrate a holistic understanding of cache behavior. To facilitate this research, we build a memory simulator incorporated into the Structural Simulation Toolkit (Rodrigues et al. in SIGMETRICS Perform Eval Rev 38(4):37–42, 2011). Our results suggest that variable cache line size can result in better performance and can also conserve power.

In this paper, we present a distributed multi-level cache system based on cloud storage, which is aimed at the low access efficiency of small spatio-temporal data files in information service system of Smart City. Taking classification attribute of small spatio-temporal data files in Smart City as the basis of cache content selection, the cache system adopts different cache pool management strategies in different levels of cache. The results of experiment in prototype system indicate that multi-level cache in this paper effectively increases the access bandwidth of small spatio- temporal files in Smart City and greatly improves service quality of multiple concurrent access in system.

Data-center servers require large capacity main memory to run multiple workloads simultaneously. However, the scalability and power consumption of DRAM limit its capability of constructing large capacity memory. Emerging non-volatile memories (e.g. PCM and STT-RAM) provide better scalability and lower power leakage than DRAM. Especially, hybrid memory consisting of DRAM and NVM is able to exploit advantages of different memory medias. However, NVMs have a few drawbacks, such as relatively longer read and write latency. Cache miss at the shared last level cache (LLC) suffers from longer latency if the missing data resides in NVM. Current LLC policies manage the cache space without being aware of the underlying heterogeneous medias. This results in cache performance degradation if a large number of missing data come from NVM. Taking the asymmetric cache miss cost into account, we first propose a new performance metric -TMPKI, which can exactly reflect the LLC performance on the top of hybrid memories. Then we propose a hybrid memory aware cache partitioning technique (HAP) to dynamically adjust the cache spaces for DRAM and NVM data based on TMPKI. Experimental results show that HAP improves performance against the traditional LRU policy by up to 54.3% (19.6% on average) while it incurs a little storage overhead (0.2%).

Caching is an effective optimization in search engine storage architectures. Many caching algorithms have been proposed to improve retrieval performance. The data selection policy of search engine cache management plays an important role, which carefully places the data in memory or other storage, such as solid state disks (SSDs). Considering that the historical query log has a guiding role for the future query, we present an Efficient Data Selection (EDS) policy for search engine cache management, which views cache media as a knapsack, and views results and posting lists as items. The best benefit of EDS can be computed by greedy algorithms. We carry out a series of experiments to study the essential factors of the data selection in different architectures, including hard disk drive (HDD), SSD, and SSD-based hybrid storage architectures. The hybrid storage architecture is a two-level cache architecture, which uses SSD as a secondary cache for the memory. Our main goal is to improve the performance of the search engines and reduce the cost of the servers on two-level cache architecture. The experimental results demonstrate that our proposed policy improves the hit ratio by 20.04% as well as the retrieval performance on HDD, SSD, and hybrid architecture by 31.98%, 28.72% and 23.24%, respectively.

Guaranteeing functional correctness of cache memories is crucial for computer designs. In the literature, there have been several works addressing this issue. However, fault tolerability of these methods may be limited. In this paper, we present a new cache architecture that has flexible tolerability. Moreover, by using the proposed architecture, both yield and reliability of the cache can be enhanced simultaneously. In our cache, a particular type of cache blocks called tolerable block is further identified among the faulty ones. Such blocks can still be used during cache access in our architecture, while accessing to intolerable blocks will result in additional cache misses, and therefore performance degradation. The number of tolerable cache blocks is thus critical for the achievable yield and reliability enhancement, as well as the incurred cost on performance. In this work, error correcting code (ECC) methods are employed to increase the number of tolerable blocks. In particular, we propose to embed the required check bits in one of the cache ways. Analysis results show that this embedding method only incurs minor performance degradation, while the incurred area overhead due to ECC can thus be significantly reduced from 5.92% to only 0.92%. General applicability of the embedding method to ordinary ECC methods is also investigated. Experimental results show that the performance degradation can be reduced from 16% to only 1.53% by using the proposed cache. This leads to great tolerability improvement, and thus the yield and reliability are enhanced very significantly when compared with the previous work.

Key-value store accelerators based on field-programmable gate arrays (FPGAs) have been proposed to achieve higher performance per watt than software-based processing. However, because their cache capacity is strictly limited by DRAMs implemented on FPGA boards, their application domains are also limited. To address this issue, the authors propose a multilevel NoSQL cache architecture that utilizes both FPGA-based hardware cache and in-kernel software cache in a complementary style. This motivates them to explore various design options. Simulation results show that their design reduces the cache miss ratio and improves the throughput compared to the nonhierarchical design.

In this article, we analyze file access characteristics of smartphone applications and find out that a large portion of file data in smartphones are written only once. This specific phenomenon appears due to the behavior of SQLite, a lightweight database library used in most smartphone applications. Based on this observation, we present a new buffer cache management scheme for smartphone systems that considers non-reusability of write-only-once data that we observe. Buffer cache improves file access performances by maintaining hot data in memory thereby servicing subsequent requests without storage accesses. The proposed scheme classifies write-only-once data and aggressively evicts them from the buffer cache to improve cache space utilization. Experimental results with various real smartphone applications show that the proposed buffer cache management scheme improves the performance of smartphone buffer cache by 5%–33%. We also show that our scheme can reduce the buffer cache size to 1/4 of the original system without performance degradation, which allows the reduction of energy consumption in a smartphone memory system by 27%–92%.

Mobile devices are quickly becoming the most widely used processors in consumer devices. Since their major power supply is battery, energy-efficient computing is highly desired. In this article, we focus on energy-efficient cache design in emerging mobile platforms. We observe that more than 40% of L2 cache accesses are OS kernel accesses in interactive smartphone applications. Such frequent kernel accesses cause serious interferences between the user and kernel blocks in the L2 cache, leading to unnecessary block replacements and high L2 cache miss rate. We first propose to statically partition the L2 cache into two separate segments, which can be accessed only by the user code and kernel code, respectively. Meanwhile, the overall size of the two segments is shrunk, which reduces the energy consumption while still maintaining the similar cache miss rate. We then find completely different access behaviors between the two separated kernel and user segments and explore the multi-retention STT-RAM-based user and kernel segments to obtain higher energy savings in this static partition-based cache design. Finally, we propose to dynamically partition the L2 cache into the user and kernel segments to minimize overall cache size. We also integrate the short-retention STT-RAM into this dynamic partition-based cache design for maximal energy savings. The experimental results show that our static technique reduces cache energy consumption by 75% with 2% performance loss, and our dynamic technique further shows strong capability to reduce cache energy consumption by 85% with only 3% performance loss.

Caches in Content-Centric Networks (CCN) are increasingly adopting flash memory based storage. The current flash cache technology stores all files with the largest possible “expiry date,” i.e., the files are written in the memory so that they are retained for as long as possible. This, however, does not leverage the CCN data characteristics where content is typically short-lived and has a distinct popularity profile. Writing files in a cache using the longest retention time damages the memory device thus reducing its lifetime. However, writing using a small retention time can increase the content retrieval delay, since, at the time a file is requested, the file may already have been expired from the memory. This motivates us to consider a joint optimization wherein we obtain optimal policies for jointly minimizing the content retrieval delay (which is a network-centric objective) and the flash damage (which is a device-centric objective). Caching decisions now not only involve what to cache but also for how long to cache each file. We design provably optimal policies and numerically compare them against prior policies.

Conventional cache tag matching identifies the requested data based on a memory address. However, this address-based tag matching is inefficient because it requires unnecessarily many tag bits. Previous studies show that translation look-aside buffer (TLB) index-based tagging (TLBIT) can be adopted in instruction caches because there are not many different tags at a given moment due to spatial locality, and those tags can be captured by TLBs. For the TLBIT scheme, extra TLB indices are added to each TLB entry and conventional cache tags are replaced with TLB indices to identify the requested data in the cache. TLBIT reduces the number of required tag bits in tag arrays; therefore, the cache energy consumption and area are decreased. In this paper, we show that naively adopting TLBIT for data caches is inefficient, in terms of performance and energy consumption, because of cache line searches and invalidations on TLB misses. To achieve the true potential of TLBIT, we propose four novel techniques: search zone, c-LRU, TLB buffer and demand address fetching. The search zone reduces unnecessary cache line searching and c-LRU reduces the cache line invalidations. The TLB buffer prevents immediate cache line invalidations on TLB misses. Furthermore, we present demand address fetching to reduce energy consumption in the TLB. From our experiments, we observed that the proposed techniques reduce the overall dynamic energy consumption of the data cache by 14.3 percent on average. The overall tag array area and leackage power of the data cache are also reduced by 54 and 45 percent, respectively. The TLB energy consumption is reduced by 22.7 percent. The performance impact is small, less than 0.4 percent on average. We also demonstrate that TLBIT can be applied to large caches, and set-associative TLBs.

In recently emerged Named Data Networking (NDN) technology, each router has a cache to store and provide frequently requested contents. Hence, an efficient cache management scheme is essential for effective content distribution and high cache utilization. As a new cache management scheme, this paper proposes the sharing of cache summaries with neighboring routers to increase the diversity of cached contents in NDN. Our proposed scheme defines a summary packet using a Bloom filter and a method to share the summary. When a Data packet is received, a router makes the decision of whether or not to save the Data depending on query results of the cache summaries of neighboring routers. If any of the neighboring routers have the Data, the Data has not necessarily been saved. When an Interest packet is received, a router can forward the Interest to a neighboring router that has the requested content by checking the summaries. The proposed scheme is evaluated using ndnSIM, which is an NS-3 based Named Data Networking simulator. Simulation results show that the sharing of cache summaries enhances the content diversity and accordingly the cache hit ratio, and reduces the average content delivery time.

Advancement in semiconductor technology increases power density in recent Chip Multi-Processors (CMPs) which significantly increases the leakage energy consumptions of on-chip Last Level Caches (LLCs). Performance linked dynamic tuning in LLC size is a promising option for reducing the cache leakage. This paper reduces static power consumption by dynamically shutting down or turning on cache banks based upon system performance and cache bank usage statistics. Shutting down of a cache bank remaps its future requests to another active bank, called as target bank. The proposed method is evaluated on three different implementation policies, viz (1) The system can decide to shutdown or turn-on some cache banks periodically throughout the process execution. (2) The system allows to shutdown banks initially and once the bank restarting initiates, no more shutdown is permitted further. (3) This policy resizes cache like first policy with some predefined time slices, in which cache cannot be resized. For a 4MB 4 way set associative L2 cache, experimental analysis shows 66% reduction in static energy with 29% gain in Energy Delay Product (EDP) for first strategy; for the second policy, static power is reduced by 59% with 27% savings in EDP. Finally, last policy saves 65% in static power and 30% in EDP with minimal performance penalty.

Dead blocks are handled inefficiently in multi-level cache hierarchies because the decision as to whether a block is dead has to be taken locally at each cache level. This paper introduces runtime-assisted global cache management to quickly deem blocks dead across cache levels in the context of task-based parallel programs. The scheme is based on a cooperative hardware/software approach that leverages static and dynamic information about future data region reuse(s) available to runtime systems for task-based parallel programming models. We show that our proposed runtime-assisted global cache management approach outperforms previously proposed local dead-block management schemes for task-based parallel programs.

In cache-based side channel attacks, a spy that shares a cache with a victim probes cache locations to extract information on the victim's access patterns. For example, in evict+reload, the spy repeatedly evicts and then reloads a probe address, checking if the victim has accessed the address in between the two operations. While there are many proposals to combat these cache attacks, they all have limitations: they either hurt performance, require programmer intervention, or can only defend against some types of attacks. This paper makes the following observation for an environment with an inclusive cache hierarchy: when the spy evicts the probe address from the shared cache, the address will also be evicted from the private cache of the victim process, creating an inclusion victim. Consequently, to disable cache attacks, this paper proposes to alter the line replacement algorithm of the shared cache, to prevent a process from creating inclusion victims in the caches of cores running other processes. By enforcing this rule, the spy cannot evict the probe address from the shared cache and, hence, cannot glimpse any information on the victim's access patterns. We call our proposal SHARP (Secure Hierarchy-Aware cache Replacement Policy). SHARP efficiently defends against all existing cross-core shared-cache attacks, needs only minimal hardware modifications, and requires no code modifications. We implement SHARP in a cycle-level full-system simulator. We show that it protects against real-world attacks, and that it introduces negligible average performance degradation.

In this paper, we propose a cooperative caching scheme for multimedia data via clusters based on peers connectivity in mobile P2P networks. In the proposed scheme, a cluster is organized for cache sharing among mobile peers with long-term connectivity, and metadata are disseminated to neighbor peers for efficient multimedia data search performance. It reduces data duplication and uses cache space efficiently through integrative cache management of peers inside the cluster. The proposed scheme reduces data replacement time in the event of changes in topology or cache data replacement using the concept of temporal cache. It performs data recovery and cluster adjustment through cluster management in the event of an abrupt disconnection of a peer. In this scheme, metadata of popular multimedia data are disseminated to neighbor peers for efficient data searching. In a data search, queries are processed in the order of local cache, metadata, the cluster to which it belongs, and neighbor clusters, in accordance with cooperative caching strategy. Performance evaluation results show that the proposed scheme has a higher cache hit ratio, and lower cost for data replacement and query processing than existing schemes.

Cache locking is a cache management technique to preclude the replacement of locked contents. Cache locking methods have been proposed to improve predictability and worst-case execution time (WCET) previously. Recently, instruction cache locking has also been applied to improve average-case execution time (ACET). However, we observe that the previous ACET-driven instruction cache locking technique shows very limited improvement on performance when applied in data cache. The underlying reason lies in that object similarity of data accesses in data memory blocks are relatively low. This paper presents a data re-allocation enabled cache locking framework where data objects are first re-allocated to enhance data object similarity in memory blocks and then a data cache locking is well motivated. In this way, locking efficiency for data cache can be enhanced and thus system performance can be improved. The experimental results show that the miss rate, memory access cycles and dynamic energy can obtain good improvements across a suite of benchmarks.

Ray tracing is a computationally intensive task required by movie-makers to create the highly realistic images they require for motion pictures. GPUs currently dominate as hardware accelerators in the multi-billion dollar movie industry. However, FPGAs with their flexibility have the potential to be more power efficient accelerators. This paper investigates and proposes an FPGA acceleration platform to easily and efficiently explore parallelism in ray tracing on FPGAs. It is integrated with LuxRender, a modern and open rendering engine. A major focus is on the proposal of a cache architecture, given that memory bandwidth is identified as a bottleneck. For the design of the domain-specific cache, we study the typical memory access patterns to ray tracing data structures, i.e. acceleration hierarchy and scene primitives. The results lead to the proposal of a data structure specific cache (separating nodes from primitives) and a novel node cache replacement policy. We demonstrate that the proposed cache architecture successfully alleviates the memory bandwidth bottleneck and that the novel replacement policy can provide a good performance increase for small cache sizes and may work well as a complimentary cache along side a direct mapped cache. The evaluation further shows that scaling the number of traversal units with a cache provides an increase in performance over all scenes. We also demonstrate the energy and bandwidth efficiency of the proposed platform in comparison to a CPU and a GPU platform.

The last level cache (LLC) in private configurations offer lower latency and isolation but extinguishes the possibility of sharing underutilized cache resources. Cooperative Caching (CC) provides capacity sharing by spilling a line evicted from one cache to another. However, CC proposals did not pay enough attention to the natural problem of private LLC, replication. The static policies either indulging the replicated blocks (replicas) in or excluding them out of LLC invariably are deficient for the complex cache capacity situations in manycore environment. In this paper, we present replication-aware cache management (RACMan) to optimize replication for private configurations. RACMan relies on a novel coarse-grained low-overheard mechanism PBFP that monitors and predicts the replica reusability to dynamically adjust LLC insertion policies giving replicas different positions of LRU chain and chances of survival in LLC according to the prediction. Experiment results show our proposal is competent to optimize replication by performing better than two baseline systems in the respects of L2 Hit Rate, Network Traffics, IPC, and Dynamic Energy. RACMan fulfils the requirements of manycore CMPs with private LLC for increasing system performance, area efficiency, and scalability.

International audience; Cloud computing and Network Function Virtualization (NFV) use cases proposed by ETSI can improve network caching when an adequate optimization algorithm is used. A cache placement algorithm is proposed based on these virtualization tools. Moreover, a cache placement protocol is presented to support the cache migration. Optimal cache and Virtual Machine (VM) placement and migration, and optimal routing based on several new constraints such as system load, network infrastructure, user satisfaction and migration cost is designed. Extensive evaluations and comparison to state of the art techniques are carried out. The results show that our cache techniques outperform other solutions and give better satisfaction to the three constituents: users, network operators and content providers.

Very Long Instruction Word (VLIW) architectures are commonly used in application-specific domains due to their parallelism and low-power characteristics. Recently, parameterization of such architectures allows for runtime adaptation of the issue-width to match the inherent Instruction Level Parallelism (ILP) of an application. One implementation of such an approach is that the event of the issue-width switching dynamically triggers the reconfiguration of the data cache at runtime. In this paper, the relationship between cache resizing and issue-width is well investigated. We have observed that the requirement of the cache does not always correlate with the issuewidth of the VLIW processor. To further coordinate the cache resizing with the changing issue-width, we present a novel feedback mechanism to "block" the low yields of cache resizing when the issue-width changes. In this manner, our feedback cache mechanism has a coordinated effort with the issue-width changes, which leads to a noticeable improvement of the cache performance. The experiments show that there is 10% energy savings as well as a 2.3% cache misses decline on average achieved, compared with the cache without the feedback mechanism. Therefore, the feedback mechanism is proven to have the capability to ensure more benefits are achieved from the dynamic and frequent reconfiguration.

Modern graphical processing units (GPUs) are equipped with general-purpose L1 and L2 caches to reduce the memory bandwidth demand and improve the performance of some irregular general-purpose GPU (GPGPU) applications. However, due to the massive multithreading, GPGPU caches suffer from severe resource contention and low data-sharing which may lead to performance degradation instead. This paper proposes a low-cost streaming-aware conflict-avoiding thrashing-resistant (SACAT) GPGPU cache management scheme that efficiently utilizes the GPGPU cache resources and addresses all the problems associated with GPGPU caches. The proposed scheme employs three orthogonal techniques. First, it dynamically detects and bypasses streaming applications at fine granularity. Second, a dynamic warp throttling via cores sampling (DWT-CS) is proposed to alleviate cache thrashing. DWT-CS runs an exhaustive search over cores to find the best number of warps that achieves the highest performance. Third, it employs pseudo random interleaving cache (PRIC), which is an improved cache indexing function based on polynomial modulus mapping, to mitigate associativity stalls and eliminate conflict misses. Experimental results demonstrate that the proposed scheme achieves a 1.87 $\times$ and a 1.5 $\times$ performance improvement over the cache-conscious wavefront scheduler (CCWS) and the memory request prioritization buffer (MRPB), respectively.

Worst-Case Execution Time (WCET) is an important metric for programs running on real-time systems, and finding precise estimates of a program’s WCET is crucial to avoid wastage of hardware resources and to improve the schedulability of task sets. Caches have a major impact on a program’s execution time, and accurate estimation of a program’s cache behavior can lead to significant reduction in its estimated WCET. The traditional approach to cache analysis generally targets the worst-case cache behavior of individual cache accesses and provides a safe hit-miss classification for every individual access. In this work, we show that these classifications are not sufficient to precisely capture cache behavior, since they apply to individual accesses, and often, more precise predictions can be made about groups of accesses. Further, memory accesses inside loops may show the worst-case behavior only for a subset of the iteration space. In order to predict such behavior in a scalable fashion, we use the fact that the cache behavior of an access mostly depends only on the memory accesses made in the immediate vicinity, and hence we analyze a small, fixed-size neighborhood of every access with complete precision and summarize the resulting information in the form of cache miss paths. A variety of analyses are then performed on the cache miss paths to make precise predictions about cache behavior. We also demonstrate precision issues in Abstract Interpretation-based Must and Persistence cache analysis that can be easily solved using cache miss paths. Experimental results over a wide range of benchmarks demonstrate precision improvement in WCET of multipath programs over previous approaches, and we also show how to integrate our approach with other microarchitectural analysis such as pipeline analysis.

Recently, processors have begun integrating 3D stacked DRAMs with the cores on the same package, and there have been several approaches to effectively utilizing the on-package DRAMs as caches. This article presents an approach that combines the previous approaches in a synergistic way by devising a module called the dirty-block tracker to maintain the dirtiness of each block in a dirty region. The approach avoids unnecessary tag checking for a write operation if the corresponding block in the cache is not dirty. Our simulation results show that the proposed technique achieves a 10.3% performance improvement on average over the state-of-the-art DRAM cache technique.

As the number of on-chip cores and memory demands of applications increase, judicious management of cache resources has become not merely attractive but imperative. Cache partitioning, that is, dividing cache space between applications based on their memory demands, is a promising approach to provide capacity benefits of shared cache with performance isolation of private caches. However, naively partitioning the cache may lead to performance loss, unfairness, and lack of quality-of-service guarantees. It is clear that intelligent techniques are required for realizing the full potential of cache partitioning. In this article, we present a survey of techniques for partitioning shared caches in multicore processors. We categorize the techniques based on important characteristics and provide a bird’s eye view of the field of cache partitioning.