Performance critical transaction and storage systems require fast persistence of write data. Typically, a non-volatile RAM (NVRAM) is employed on the datapath to the permanent storage, to temporarily and quickly store write data before the system acknowledges the write request. NVRAM is commonly implemented with battery-backed DRAM. Unfortunately, battery-backed DRAM is small and costly, and occupies a precious DIMM slot. In this paper, we make a case for dual, byte- and block-addressable solid-state drive (2B-SSD), a novel NAND flash SSD architecture designed to offer a dual view of byte addressability and traditional block addressability at the same time. Unlike a conventional storage device, 2B-SSD allows accessing the same file with two independent byte- and block-I/O paths. It controls the data transfer between its internal DRAM and NAND flash memory through an intuitive software interface, and manages the mapping of the two address spaces. 2B-SSD realizes a wholly different way and speed of accessing files on a storage device; applications can access them directly using memory-mapped I/O, and moreover write with a DRAM-like latency. To quantify the benefits of 2B-SSD, we modified logging subsystems of major database engines to store log records directly on it without buffering them in the host memory. When running popular workloads, we measured throughput gains in the range of 1.2X and 2.8X with no risk of data loss.

This work is dedicated to eliminating the overhead required for guaranteeing the storage order in the modern IO stack. The existing block device adopts a prohibitively expensive approach in ensuring the storage order among write requests: interleaving the write requests with Transfer-and-Flush . For exploiting the cache barrier command for flash storage, we overhaul the IO scheduler, the dispatch module, and the filesystem so that these layers are orchestrated to preserve the ordering condition imposed by the application with which the associated data blocks are made durable. The key ingredients of Barrier-Enabled IO stack are Epoch-based IO scheduling , Order-Preserving Dispatch , and Dual-Mode Journaling . Barrier-enabled IO stack can control the storage order without Transfer-and-Flush overhead. We implement the barrier-enabled IO stack in server as well as in mobile platforms. SQLite performance increases by 270% and 75%, in server and in smartphone, respectively. In a server storage, BarrierFS brings as much as by 43 × and by 73× performance gain in MySQL and SQLite, respectively, against EXT4 via relaxing the durability of a transaction.

Recently, in-memory big data processing frameworks have emerged, such as Apache Spark and Ignite, to accelerate workloads requiring frequent data reuse. With effective in-memory caching these frameworks eliminate most of I/O operations, which would otherwise be necessary for communication between producer and consumer tasks. However, this performance benefit is nullified if the memory footprint exceeds available memory size, due to excessive spill and garbage collection (GC) operations. To fit the working set in memory, two system parameters play an important role: number of data partitions (Npartitions) specifying task granularity, and number of tasks per each executor (Nthreads) specifying the degree of parallelism in execution. Existing approaches to optimizing these parameters either do not take into account workload characteristics, or optimize only one of the parameters in isolation, thus yielding suboptimal performance. This paper introduces WASP, a workload-aware task scheduler and partitioner, which jointly optimizes both parameters at runtime. To find an optimal setting, WASP first analyzes the DAG structure of a given workload, and uses an analytical model to predict optimal settings of Npartitionsand Nthreadsfor all stages based on their computation types. Taking this as input, the WASP scheduler employs a hill climbing algorithm to find an optimal Nthreadsfor each stage, thus maximizing concurrency while minimizing data spills and GCs. We prototype WASP on Spark and evaluate it using six workloads on three different parallel platforms. WASP improves performance by up to 3.22× and reduces the cluster operating cost on cloud by up to 40%, over the baseline following Spark Tuning Guidelines and provides robust performance for both shuffle-heavy and shuffle-light workloads.

Storage I/O performance remains a key factor that determines the overall user experience of a computer system. This is especially true for mobile systems as users commonly browse and navigate through many high-quality pictures and video clips stored in their device. The appetite for more appealing user interface has continuously pushed the mobile storage interface speed up; emerging UFS 2.0 standard provisions a maximum bandwidth of as high as 1,200 MB/s. In this work, we propose, design, and implement a mobile storage architecture that leverages the high-speed DRAM interface for communication, thus substantially expanding the storage performance headroom. In order to effectively turn the existing DRAM interface into a storage interface, we design a new storage protocol that runs on top of the DRAM interface. Our protocol builds on a small host interface buffer structure mapped to the system's memory space. Based on this protocol, we develop and fabricate a storage controller chip that natively supports the LPDDR3 interface. We also develop a host software stack (Linux device driver and boot loader) and a host platform board. Finally we show the feasibility of our proposal by constructing a full Android system running on the developed storage device and platform. Our detailed evaluation shows that the proposed storage architecture has very low protocol handling overheads and compares favorably to a UFS 2.0 device. The proposed architecture obviates the need for implementing a separate host-side storage controller on a mobile CPU chip.

Data-intensive queries are common in business intelligence, data warehousing and analytics applications. Typically, processing a query involves full inspection of large in-storage data sets by CPUs. An intuitive way to speed up such queries is to reduce the volume of data transferred over the storage network to a host system. This can be achieved by filtering out extraneous data within the storage, motivating a form of near-data processing. This work presents Biscuit, a novel near-data processing framework designed for modern solid-state drives. It allows programmers to write a data-intensive application to run on the host system and the storage system in a distributed, yet seamless manner. In order to offer a high-level programming model, Biscuit builds on the concept of data flow. Data processing tasks communicate through typed and data-ordered ports. Biscuit does not distinguish tasks that run on the host system and the storage system. As the result, Biscuit has desirable traits like generality and expressiveness, while promoting code reuse and naturally exposing concurrency. We implement Biscuit on a host system that runs the Linux OS and a high-performance solid-state drive. We demonstrate the effectiveness of our approach and implementation with experimental results. When data filtering is done by hardware in the solid-state drive, the average speed-up obtained for the top five queries of TPC-H is over 15x.

This paper presents YourSQL , a database system that accelerates data-intensive queries with the help of additional in-storage computing capabilities. YourSQL realizes very early filtering of data by offloading data scanning of a query to user-programmable solid-state drives. We implement our system on a recent branch of MariaDB (a variant of MySQL). In order to quantify the performance gains of YourSQL, we evaluate SQL queries with varying complexities. Our result shows that YourSQL reduces the execution time of the whole TPC-H queries by 3.6×, compared to a vanilla system. Moreover, the average speed-up of the five TPC-H queries with the largest performance gains reaches over 15×. Thanks to this significant reduction of execution time, we observe sizable energy savings. Our study demonstrates that the YourSQL approach, combining the power of early filtering with end-to-end datapath optimization, can accelerate large-scale analytic queries with lower energy consumption.

Phase-change memory (PCM) has emerged as a candidate that overcomes the physical limitations faced by DRAM and NAND flash memory. While PCM has desirable properties in terms of scalability and density, it suffers from limited endurance. Repeated writes cause PCM cells to wear out and get permanently stuck at a specific value. Recovering from stuck-at faults through a proactive error correcting scheme is essential for the widespread adoption of PCM. In this paper, we propose Symbol Shifting as a practical technique to increase the number of faults that an error correcting code can cover in single and multilevel cells memory chips. Since stuck-at cells can still be read, errors are manifested only when a worn-out cell is to be programmed with a symbol value different than the value it is stuck at. After a write operation fails for a given block of data, another write operation is attempted with all original data symbols shifted to another memory level. Shifting the data is likely to bring the number of errors within the nominal capability of the deployed error correcting code. Requiring only one additional auxiliary cell, Symbol Shifting can increase the number of faults that an error correcting code can cover by up to double the nominal capability and extends the lifetime by up to 37 percent.

This tutorial overviews flash memory solid-state drive technologies and recent advances in the field.

With their potential for high scalability and density, resistive memories are foreseen as a promising technology that overcomes the physical limitations confronted by charge-based DRAM and flash memory. Yet, a main burden towards the successful adoption and commercialization of resistive memories is their low cell reliability caused by process variation and limited write endurance. Typically, faulty and worn-out cells are permanently stuck at either ‘0’ or ‘1’. To overcome the challenge, a robust error correction scheme that can recover from many hard faults is required. In this paper, we propose and evaluate RDIS , a novel scheme to efficiently tolerate memory stuck-at faults. RDIS allows for the correct retrieval of data by recursively determining and efficiently keeping track of the positions of the bits that are stuck at a value different from the ones that are written, and then, at read time, by inverting the values read from those positions. RDIS is characterized by a very low probability of failure that increases slowly with the relative increase in the number of faults. Moreover, RDIS tolerates many more faults than the best existing scheme—by up to 95 percent on average at the same overhead level.

Maintaining coherence in large-scale chip multiprocessors (CMPs) embodies tremendous design trade-offs in meeting the area, energy and performance requirements. Sparse directory organizations represent the most energy-efficient and scalable approach towards many-core coherence. However, their limited associativity disallows the one-to-one correspondence of directory entries to cached blocks, rendering them inadequate in tracking all cached blocks. Unless the directory storage is generously over-provisioned, conflicts will force frequent invalidations of cached blocks, severely jeopardizing the system performance. As the chip area and power become increasingly precious with the growing core count, over-provisioning the directory storage becomes unsustainably costly. Stash Directory is a novel sparse directory design that allows directory entries tracking private blocks to be safely evicted without invalidating the corresponding cached blocks. By doing so, it improves system performance and increases the effective directory capacity, enabling significantly smaller directory designs. To ensure correct coherence under the new relaxed inclusion property, stash directory delegates to the last level cache the responsibility to discover hidden cached blocks when necessary, without however raising significant overhead concerns. Simulations on a 16-core CMP model show that Stash Directory can reduce space requirements to 1/8 of a conventional sparse directory, without compromising performance.

Non-volatile memory (NVM) technologies support both byte addressability (like DRAM) and non-volatility (like disks). This characteristic makes it feasible for NVM to be employed at any layer of the memory hierarchy including CPU cache, main memory, file cache, storage, and hybrid memory. In this paper, we explore new challenges and opportunities that arise when NVM is introduced as a file cache in the memory hierarchy. One opportunity is that cache does not require long-term non-volatility since data are replaced when working sets are changed. This feature is well matched with NVM, which has limited retention time. In addition, the retention time of NVM is inverse proportional to the write latency, giving a chance to optimize the write performance. However, the limited retention time raises a new challenge that it may cause the hit ratio reduction and lead to cache performance degradation. To tackle this challenge, we propose a new inter-reference gap (IRG) based cache management scheme that writes data with different retention times according to their IRGs. Our proposal builds on the fact that block accesses of typical workloads show unique and regular patterns in terms of access intervals. Experimental results show that our scheme enhances system performance by up to 42% (33% on average), compared with the conventional LRU based cache management scheme.

DRAM stores information in electric charge. Because DRAM cells lose stored charge over time due to leakage, they have to be “refreshed” in a periodic manner to retain the stored information. This refresh activity is a source of increased energy consumption as the DRAM density grows. It also incurs nontrivial performance loss due to the unavailability of memory arrays during refresh. This paper first presents a comprehensive measurement-based characterization study of the cell-level data retention behavior of modern low-power DRAM chips. About 99.7% of the cells could retain the stored information for longer than 1 s at a high temperature. This average cell retention behavior strongly indicates that we can deeply reduce the energy and performance penalty of DRAM refreshing with proper system support. The second part of this paper, accordingly, develops two practical techniques to reduce the frequency of DRAM refresh operations by excluding a few leaky memory cells from use and by skipping refreshing of unused DRAM regions. We have implemented the proposed techniques completely in the Linux OS for experimentation, and measured performance improvement of up to 17.2% with the refresh operation reduction of 93.8% on smartphone like low-power platforms.

Today’s computers have gigabytes of main memory due to improved DRAM density. As density increases, smaller bit cells become more susceptible to errors. With an increase in error susceptibility, the need for memory resiliency also increases. Self-testing of memory health can proactively check for errors to improve resiliency. This paper describes a software-only self-test to continuously test memory. We present the challenges and design for an approach, called Continuous Online Memory Testing with Multi-threading Extension (COMeT+), that targets chip multiprocessors. COMeT+ tests memory health simultaneously with execution of single and multi-threaded applications in anticipation of allocation requests. The approach guarantees that memory is tested within a fixed time interval to limit exposure to lurking errors. We developed and evaluated an implementation of COMeT+. On the SPEC CPU2006 and the PARSEC benchmarks, COMeT+ has a low 4% average performance overhead. On the PARSEC benchmarks, the effect of TLB shootdowns on application performance due to additional page migrations caused by COMeT+ was insignificant. When emulated errors were injected into physical memory, applications executed 1.13x to 4.41x longer with COMeT+ than without it.

Intelligent solid-state drives (iSSDs) allow execution of limited application functions (e.g., data filtering or aggregation)on their internal hardware resources, exploiting SSD characteristics and trends to provide large and growing performance and energy efficiency benefits. Most notably, internal flash media bandwidth can be significantly (2-4x or more) higher than the external bandwidth with which the SSD is connected to a host system, and the higher internal bandwidth can be exploited within an iSSD. Also, SSD bandwidth is projected to increase rapidly over time, creating a substantial energy cost for streaming of data to an external CPU for processing, which can be avoided via iSSD processing. This paper makes a case for iSSDs by detailing these trends, quantifying the potential benefifits across a range of application activities, describing how SSD architectures could be extended cost-effectively, and demonstrating the concept with measurements of a prototype iSSD running simple data scan functions. Our analyses indicate that, with less than a 2% increase in hardware cost over a traditional SSD, an iSSD can provide 2-4x performance increases and 5-27x energy efficiency gains for a range of data-intensive computations.

This paper addresses new system design issues that will occur when a large quantity of emerging persistent RAM (PRAM) is put on the main memory bus of a platform. First, we anticipate that continued technology advances will enable us to integrate (portions of) the system storage within the PRAM modules on a system board. This change calls for comprehensive re-examination of the system design concepts that assume "slow" disk and the block I/O concept. Next, we propose Memorage, a system architecture that virtually manages all available physical resources for memory and storage in an integrated manner. Memorage leverages the existing OS virtual memory (VM) manager to improve the performance of memory-intensive workloads and achieve longer lifetime of the main memory.

Phase-change memory (PCM) has emerged as a candidate that overcomes the physical limitations faced by DRAM and NAND flash memory. While PCM has desirable properties in terms of scalability and energy, it suffers from limited endurance. Repeated writes cause PCM cells to wear out and get permanently stuck at either 0 or 1. Recovering from stuck-at faults through a proactive error correction scheme is essential for the widespread adoption of PCM. In this paper, we propose data inversion as a practical technique to increase the number of faults that an error correction code can cover. Since stuck-at cells can still be read, errors are manifested only when a worn-out cell is programmed with a bit value different than the value it is stuck at. After a write operation fails for a given block of data, data inversion attempts another write operation with all original data bits inverted. Inverting the data is likely to bring the number of errors within the nominal capability of the deployed error correction code. Requiring only one additional auxiliary bit, data inversion can double the capability of an error correction code and extends the lifetime by up to 34.5%.

With their potential for high scalability and density, resistive memories are foreseen as a promising technology that overcomes the physical limitations confronted by charge-based DRAM and flash memory. Yet, a main burden towards the successful adoption and commercialization of resistive memories is their low cell reliability caused by process variation and limited write endurance. Typically, faulty and worn-out cells are permanently stuck at either `0' or `1'. To overcome the challenge, a robust error correction scheme that can recover from many hard faults is required. In this paper, we propose and evaluate RDIS, a novel scheme to efficiently tolerate memory stuck-at faults. RDIS allows for the correct retrieval of data by recursively determining and efficiently keeping track of the positions of the bits that are stuck at a value different from the ones that are written, and then, at read time, by inverting the values read from those positions. RDIS is characterized by a very low probability of failure that increases slowly with the relative increase in the number of faults. Moreover, RDIS tolerates many more faults than the best existing scheme-by up to 95% on average at the same overhead level.

This paper explores high-bandwidth data cache designs for a coarse-grained reconfigurable architecture processor family capable of achieving a high degree of instruction level parallelism. To meet stringent power, area and time-to-market constraints, we take an architectural approach rather than circuit-level multi-porting approaches. We closely examine two design choices: single-level banked cache (SLC) and two-level cache (TLC). A detailed simulation study using a set of microbenchmarks and industry-strength benchmarks finds that both SLC and TLC offer a reasonably competitive performance at a small implementation cost compared with a hypothetical cache with perfect ports and a multi-bank scratchpad memory.

Predicting target processors that a coherence request must be delivered to can improve the miss handling latency in shared memory systems. In directory coherence protocols, directly communicating with the predicted processors avoids costly indirection to the directory. In snooping protocols, prediction relaxes the high bandwidth requirements by replacing broadcast with multicast. In this work, we propose a new run-time coherence target prediction scheme that exploits the inherent correlation between synchronization points in a program and coherence communication. Our workload-driven analysis shows that by exposing synchronization points to hardware and tracking them at run time, we can simply and effectively track stable and repetitive communication patterns. Based on this observation, we build a predictor that can improve the miss latency of a directory protocol by 13%. Compared with existing address- and instruction-based prediction techniques, our predictor achieves comparable performance using substantially smaller power and storage overheads.

This paper describes Cache Equalizer (CE), a novel distributed cache management scheme for large-scale chip multiprocessors (CMPs). Our work is motivated by large asymmetry in cache sets' usages. CE decouples the physical locations of cache blocks from their addresses for the sake of reducing misses caused by destructive interferences. Temporal pressure at the on-chip last-level cache is continuously collected at a group (comprised of cache sets) granularity, and periodically recorded at the memory controller to guide the placement process. An incoming block is consequently placed at a cache group that exhibits the minimum pressure. Simulation results using a full-system simulator demonstrate that CE achieves an average L2 miss rate reduction of 13.6% over a shared NUCA scheme and by as much as 46.7% for the benchmark programs we examined. Furthermore, evaluations showed that CE outperforms related cache designs.

The number of cores in a single chip multiprocessor is expected to grow in coming years. Likewise, aggregate on-chip cache capacity is increasing fast and its effective utilization is becoming ever more important. Furthermore, available cores are expected to be underutilized due to the power wall and highly heterogeneous future workloads. This trend makes existing L2 cache management techniques less effective for two problems: increased capacity interference between working cores and longer L2 access latency. We propose a novel scalable cache management framework called CloudCache that creates dynamically expanding and shrinking L2 caches for working threads with fine-grained hardware monitoring and control. The key architectural components of CloudCache are L2 cache chaining, inter- and intra-bank cache partitioning, and a performance-optimized coherence protocol. Our extensive experimental evaluation demonstrates that CloudCache significantly improves performance of a wide range of workloads when all or a subset of cores are occupied.

It has been foreseen that some of the roles assumed by conventional rotating hard disk drives (HDDs) will migrate to solid-state drives (SSDs) and emerging persistent RAM storages. New persistent RAM storages have critical advantages over HDDs and even SSDs in terms of performance and power. Persistent RAM technologies are flexible enough to be used for both storage and main memory - in future platforms, this flexibility will allow tighter integration of a system's memory and storage hierarchy. On the other hand, designers are faced with new technical issues to address to fully exploit the benefits of persistent RAM technologies and hide their downsides. In this paper, we introduce PRISM (PeRsIstent RAM Storage Monitor) - our novel infrastructure that enables exploring various design trade-offs of persistent RAM storage. PRISM allows designers to examine a persistent RAM storage's low-level behavior and evaluate its various architectural organizations while running realistic workloads, as well as storage activities of a contemporary off-the-shelf OS. PRISM builds on kernel source code level instrumentation and the standard Linux device driver mechanism to generate persistent RAM storage traces. Moreover, PRISM includes a storage architecture simulator to faithfully model major persistent RAM storage hardware components. To illustrate how and with what PRISM can help the user, we present a case study that involves running an OLTP (on-line transaction processing) workload. PRISM successfully provides the detailed performance analysis results, while incurring acceptable overheads. Based on our experience, we believe that PRISM is a versatile tool for exploring persistent RAM storage design choices ranging from OS-level resource management policy down to chip-level storage organization.

Trace-driven simulation is a widely practiced simulation method. However, its use has been typically limited to modeling of in-order processors because of accuracy issues. In this work, we propose and explore In-N-Out, a fast approximate simulation method to reproduce the behavior of an out-of-order superscalar processor with a reduced in-order trace. During trace generation, we use a functional cache simulator to capture interesting processor events such as uncore accesses in the program order. We also collect key information about the executed program. The prepared in-order trace then drives a novel simulation algorithm that models an out-of-order processor. Our experimental results demonstrate that In-N-Out produces reasonably accurate absolute performance (7% difference on average) and fast simulation speeds (115x on average), compared with detailed execution-driven simulation. Moreover, In-N-Out was shown to preserve a processor's dynamic uncore access patterns and predict the relative performance change when the processor's core- or uncore-level parameters are changed.

Software simulation is the primary tool used for evaluation of processor design. Simulation offers better accuracy than analytical models and is an important evaluation step before actually fabricating a chip. Unfortunately, simulator speeds are slow -- a conventional cycle-accurate simulator will be unable to keep up with increasing core counts in modern processor design. Parallel simulation is one method for improving simulation speeds. Two major areas of parallel simulation research are multithreaded simulators and FPGAs as simulation accelerators. Multithreaded simulators can only extract coarse-grained parallelism and must sacrifice accuracy in order to scale well. FPGA-based simulators can extract fine-grained parallelism, but are expensive and difficult to program. We propose using GPUs for architectural simulation, which can take advantage of a high degree of fine-grained parallelism. In addition, they are inexpensive and easier to program compared to FPGAs. To demonstrate our ideas, we implement a trace-driven many-cache simulator using NVIDIA's CUDA toolkit. GPU-accelerated cache simulation displays remarkable scaling with number of simulated caches when compared to serial CPU-only simulation.

Processor cores in a chip multiprocessor (CMP) typically share a large last-level cache and the off-chip memory bandwidth. Previous studies demonstrate that explicit cache capacity and off-chip bandwidth partitioning can yield better overall system performance than without partitioning. However, little work has been done to study the interaction between cache capacity partitioning and off-chip bandwidth allocation. This paper develops a hybrid analytical model that takes into account the two partitioning problems together in order to capture their inter-dependence. With an elaborate case study, we show that an optimal resource management strategy would require a coordinated allocation of the cache and the off-chip bandwidth resources.

Today's computers have gigabytes of main memory due to improved DRAM density. As density increases, smaller bit cells become more susceptible to errors. With an increase in error susceptibility, the need for memory resiliency also increases. Self-testing of memory health can proactively check for errors to improve resiliency. This paper describes a software-only self test to continuously test memory. We present the challenges and design for an approach, called Continuous Online Memory Testing (COMeT), that targets chip multiprocessors. COMeT tests memory health simultaneously with application execution in anticipation of allocation requests. The approach guarantees that memory is tested within a fixed time interval to limit exposure to lurking errors. We developed and evaluated an implementation of COMeT. On the SPEC CPU2006 benchmarks, COMeT has a low 4% average performance overhead. When emulated errors were injected into physical memory, applications executed 1.13× to 4.41× longer with COMeT than without it.

Advances in deep submicron technology call for a careful review of existing cache designs and design practices in terms of yield, area, and performance. This article presents a Design and Evaluation Framework for defect-tolerant Cache Memories (DEFCAM), which enables processor architects to consider yield, area, and performance together in a unified framework. Since there is a complex, changing trade-off among these metrics depending on the technology, the cache organization, and the yield enhancement scheme employed, such a design flow is invaluable to processor architects when they assess a design and explore the design space quickly at an early stage. We develop a complete framework supporting the proposed DEFCAM design flow, from injecting defects into a wafer to evaluating program performance of individual processors on the wafer. Using DEFCAM, interesting interactions between architectural, organizational, and layout/defect related parameters can be easily evaluated. Moreover, we propose practical set remapping schemes to contain hard faults in cache memory. In a set remapping scheme, accesses that would go to an unusable faulty set are directed to a sound set. Case studies are presented to demonstrate the effectiveness of the proposed design flow and developed tools. Experimental results show that a set remapping is the most efficient fault covering method among prevailing strategies.

This paper presents a study on macro data load, a novel mechanism to increase the amount of loaded data reuse within a processor. A macro data load brings into the processor a maximum-width data the cache port allows. In a 64-bit processor, for example, a byte load will bring a full 64-bit data from cache and save it in an internal hardware structure, while using for itself only the specified byte out of the 64-bit data. The saved data can be opportunistically reused by later loads internally, reducing relatively more expensive cache accesses. We present a comprehensive availability study using a generalized memory data reuse table (MDRT) to quantify available memory data reuse opportunities in a set of benchmark programs drawn from the SPEC2k and MiBench suites, and to demonstrate the efficacy of the proposed scheme. The macro data load mechanism is shown to open up significantly more loaded data reuse opportunities than previous schemes with no support for spatial locality. We observe 15.1 percent (SPEC2k integer), 20.9 percent (SPEC2k floating-point), and 45.8 percent (MiBench) more load-to-load forwarding instances when a 256-entry MDRT is used. We also describe a modified load store queue design as a possible implementation of the proposed concept. Our quantitative study using a realistic processor model shows that 21.3 percent, 14.8 percent, and 23.6 percent of L1 cache accesses in the SPEC2k integer, floating-point, and MiBench programs can be eliminated, resulting in a related energy reduction of 11.4 percent, 9.0 percent, and 14.3 percent on average, respectively.

This poster describes an intra-tile cache set balancing strategy that exploits the demand imbalance across sets within the same L2 cache bank. This strategy retains some fraction of the working set at underutilized sets so as to satisfy far-flung reuses. It adapts to phase changes in programs and promotes a very flexible sharing among cache sets referred to as many-from-many sharing. Simulation results using a full system simulator demonstrate the effectiveness of the proposed scheme and show that it compares favorably with related cache designs on a 16-way tiled CMP platform.

Technology advances continuously shrink on-chip devices. Consequently, the number of cores in a single chip multiprocessor (CMP) is expected to grow in coming years. Unfortunately, with smaller device size and greater integration, chip yield degrades significantly. Guaranteeing that all chip components function correctly leads to an unrealistically low yield. Chip vendors have adopted a design strategy to market partially functioning processor chips to combat this problem. The two major components in a multicore chip are compute cores and on-chip memory such as L2 cache. From the viewpoint of the chip yield, the compute cores have a much lower yield than the on-chip memory due to their logic complexity and well-established memory yield enhancing techniques. Therefore, future CMPs are expected to have more available on-chip memories than working cores. This paper introduces a novel on-chip memory utilization scheme called StimulusCache, which decouples the L2 caches of faulty compute cores and employs them to assist applications on other working cores. Our extensive experimental evaluation demonstrates that StimulusCache significantly improves the performance of both single-threaded and multithreaded workloads.

Phase-change random access memory (PRAM) is a promising storage-class memory technology that has the potential to replace flash memory and DRAM in many applications. Because individual cells in a PRAM can be written independently, only data cells whose current values differ from the corresponding bits in a write request need to be updated. Furthermore, when a block write request is received, the PRAM may contain many free blocks that are available for overwriting, and these free blocks will generally have different contents. For this reason, the number of bit programming operations required to write new data to the PRAM (and consequently power consumption and write bandwidth) depends on the location that is chosen to be overwritten. This paper describes a block placement algorithm for reducing PRAM bit writes based on the idea of indexing free blocks using a content-based signature; computing the signature value of a new block of data to be written allows a free block with similar contents to be located quickly. While the benefit that can be realized by the use of any block placement algorithm is heavily dependent on the workload, our evaluation results show that block placement using content-based signatures is able to reduce the number of PRAM bit programming operations by as much as an order of magnitude.

Abstract Simulation is indispensable in computer architecture research. Researchers increasingly resort to detailed architecture simulators to identify performance bottlenecks, analyze interactions among different hardware and software components, and measure the impact of new design ideas on the system performance. However, the slow speed of conventional execution‐driven architecture simulators is a serious impediment to obtaining desirable research productivity. This paper describes a novel fast multicore processor architecture simulation framework calledTwo‐Phase Trace‐driven Simulation(TPTS), which splits detailed timing simulation into a trace generation phase and a trace simulation phase. Much of the simulation overhead caused by uninteresting architectural events is only incurred once during the cycle‐accurate simulation‐based trace generation phase and can be omitted in the repeated trace‐driven simulations. We report our experiences withtsim, an event‐driven multicore processor architecture simulator that models detailed memory hierarchy, interconnect, and coherence protocol based on the TPTS framework. By applying aggressive event filtering,tsimachieves an impressive simulation speed of 146 millions of simulated instructions per second, when running 16‐thread parallel applications. Copyright © 2010 John Wiley & Sons, Ltd.

The number of CPUs in chip multiprocessors is growing at the Moore's Law rate, due to continued technology advances. However, new technologies pose serious reliability challenges, such as more frequent occurrences of degraded or even nonoperational devices, and they threaten the cost-effectiveness and dependability of future computing systems. This work studies how to protect the on-chip coherence directory from fault occurrences. In a chip multiprocessor, cache coherence mechanisms such as directory memory are critical for offering consistent data view to all CPUs. We propose a novel online fault detection and correction scheme to enhance yield and resilience to runtime errors at a small performance cost. The proposed scheme uses smart encoding and coherence protocol adaptation strategies to salvage faulty directory entries. We also develop an online error recovery scheme that protects the directory memory from soft errors. We call our fault-tolerant directory memory architecture PERFECTORY. Evaluation results show that PERFECTORY achieves very high fault resilience: Over 99 percent chip yield at 0.05 percent hard error ratio and 1,934 years MTTF at 1,000 FIT using a 100-processor cluster configuration. PERFECTORY limits performance degradation to less than 1 percent at 0.05 percent hard error ratio and requires significantly smaller area overheads than existing redundancy approaches.

This paper derives simple, yet fundamental formulas to describe the interplay between parallelism of an application, program performance, and energy consumption. Given the ratio of serial and parallel portions in an application and the number of processors, we derive optimal frequencies allocated to the serial and parallel regions in an application to either minimize the total energy consumption or minimize the energy-delay product. The impact of static power is revealed by considering the ratio between static and dynamic power and quantifying the advantages of adding to the architecture capability to turn off individual processors and save static energy. We further determine the conditions under which one can obtain both energy and speed improvement, as well as the amount of improvement. While the formulas we obtain use simplifying assumptions, they provide valuable theoretical insights into energy-aware processor resource management. Our results form a basis for several interesting research directions in the area of energy-aware multicore processor architectures.

This paper proposes a new software-oriented approach for managing the distributed shared L2 caches of a chip multiprocessor (CMP) for latency-oriented multithreaded applications. The conventional shared cache scheme loses performance due to the blind distribution of data predominantly accessed by a single thread. SOS, our software-oriented distributed shared cache management approach, infers a programpsilas data affinity hints through a novel machine learning based analysis of its L2 cache access behavior. The OS utilizes the hints to guide proper data placement in the L2 cache with page coloring. The derived hints are independent of the program input and can be used for multiple runs. By off-loading the cache management task onto software, SOS deviates substantially from previously proposed hardware based strategies and opens up a new opportunity for the CMP cache optimization. Our experimental results demonstrate that SOS is very effective in reducing the number of remote cache accesses. By using the hints for guiding page coloring alone, SOS achieves an average speedup of 10% and up to 23% over the shared cache scheme. When hints are used to direct data replication, SOS secures an additional performance gain of 9%, performing 19% better than the shared cache scheme on average.

As the Internet grows, both the number of rules in packet filtering databases and the number of prefixes in IP lookup tables inside the router are growing. The packet processing engine is a critical part of the Internet router as it is used to perform packet forwarding (PF) and packet classification (PC). In both applications, processing has to be at wire speed. It is common to use hash-based schemes in packet processing engines; however, the downside of classic hashing techniques such as overflow and worst case memory access time, has to be dealt with. Implementing hash tables using set associative memory has the property that each bucket of a hash table can be searched in one memory cycle outperforming the conventional Ternary CAMs in terms of power and scalability.

This paper proposes DCC (Dynamic Cache Clustering), a novel distributed cache management scheme for large-scale chip multiprocessors. Using DCC, a per-core cache cluster is comprised of a number of L2 cache banks and cache clusters are constructed, expanded, and contracted dynamically to match each core's cache demand. The basic trade-offs of varying the on-chip cache clusters are average L2 access latency and L2 miss rate. DCC uniquely and efficiently optimizes both metrics and continuously tracks a near-optimal cache organization from many possible configurations. Simulation results using a full-system simulator demonstrate that DCC outperforms alternative L2 cache designs.

Trace-driven simulation of superscalar processors is particularly complicated. The dynamic nature of superscalar processors combined with the static nature of traces can lead to large inaccuracies in the results, especially when traces contain only a subset of executed instructions for trace reduction. The main problem in the filtered trace simulation is that the trace does not contain enough information with which one can predict the actual penalty of a cache miss. In this paper, we discuss and evaluate three strategies to quantify the impact of a long latency memory access in a superscalar processor when traces have only L1 cache misses. The strategies are based on models about how a cache miss is treated with respect to other cache misses: (1) isolated cache miss model, (2) independent cache miss model, and (3) pairwise dependent cache miss model. Our experimental results demonstrate that the pairwise dependent cache miss model produces reasonably accurate results (4.8% RMS error) under perfect branch prediction. Our work forms a basis for fast, accurate, and configurable multicore processor simulation using a pre-determined processor core design.

The phase-change random access memory (PRAM) technology is fast maturing to production levels. Main advantages of PRAM are non-volatility, byte addressability, in-place programmability, low-power operation, and higher write endurance than that of current flash memories. However, the relatively low write bandwidth and the less-than-desirable write endurance of PRAM remain room for improvement. This paper proposes and evaluates Flip-N-Write, a simple microarchitectural technique to replace a PRAM write operation with a more efficient read-modify-write operation. On a write, after quick bit-by-bit inspection of the original data word and the new data word, Flip-N-Write writes either the new data word or the "flipped" value of it. Flip-N-Write introduces a single bit associated with each PRAM word to indicate whether the PRAM word has been flipped or not. We analytically and experimentally show that the proposed technique reduces the PRAM write time by half, more than doubles the write endurance, and achieves commensurate savings in write energy under the same instantaneous write power constraint. Due to its simplicity, Flip-N-Write is straightforward to implement within a PRAM device.

The slow speed of conventional execution-driven architecture simulators is a serious impediment to obtaining desirable research productivity. This paper proposes and evaluates a fast manycore processor simulation framework called two-phase trace-driven simulation (TPTS), which splits detailed timing simulation into a trace generation phase and a trace simulation phase. Much of the simulation overhead caused by uninteresting architectural events is only incurred once during the trace generation phase and can be omitted in the repeated trace-driven simulations. We design and implement tsim, an event-driven manycore processor simulator that models detailed memory hierarchy, interconnect, and coherence protocol models based on the proposed TPTS framework. By applying aggressive event filtering, tsim achieves an impressive simulation speed of 146 MIPS, when running 16-thread parallel applications.

This paper presents a two-part study on managing distributed NUCA (non-uniform cache architecture) L2caches in a future many core processor to obtain high single thread program performance. The first part of our study is a limit study where we determine data to cache slice mappings at the memory page granularity based on detailed inter-page conflict information derived from program's memory reference trace. By considering cache access latency and cache miss rate simultaneously when mapping data to L2 cache slices, this "oracle" scheme outperforms the conventional shared caching scheme by up to 208% with an average of 45% on a sixteen-core processor. In the second part of the study, we propose and evaluate a dynamic cache management scheme that determines the home cache slice and cache bin for memory pages without any static program information. The dynamic scheme outperforms the shared caching scheme by up to 191% with an average of 32%, achieving much of the performance we observed in the limit study. We also find that the proposed dynamic scheme adapts to multiprogrammed workloads' behavior well and performs significantly better than both the private caching scheme and the shared caching scheme.

This research investigates the impact of a microarchitectural technique called vertical interleaving in multi-banked caches. Unlike previous multi-banking and interleaving techniques to increase cache bandwidth, the proposed vertical interleaving further divides memory banks in a cache into vertically arranged sub-banks, which are selectively accessed based on the memory address. Under this setting, we are particularly interested in how accesses to instruction cache are dispersed toward different cache banks. We quantitatively analyze the memory access pattern seen by each cache bank and establish the relationship between important cache parameters and the access patterns. Our study shows that the vertical interleaving technique distributes accesses among different banks with tightly bounded run lengths. We then discuss possible applications that utilize the presented concept, including power density reduction. Very simple interleaving configurations can lead to as much as 67% reduction of maximum power density under a realistic machine configuration. Our study suggests that the idea of vertically interleaving cache lines has potential for optimizing memory accesses in a number of interesting ways.

The deployment of future deep submicron technology calls for a careful review of existing cache organizations and design practices in terms of yield and performance. This paper presents a cache design flow that enables processor architects to consider yield, area, and performance (YAP) together in a unified framework. Since there is a complex, changing trade-off between these metrics depending on the technology, the cache organization, and the yield enhancement scheme employed, such a design flow becomes invaluable to processor architects when they assess a design and explore the design space quickly at an early stage. We develop a complete set of tools supporting the proposed design flow, from injecting defects into a wafer to evaluating program performance of individual processors in the wafer. A case study is presented to demonstrate the effectiveness of the proposed design flow and developed tools.

This paper proposes a specialized memory structure called CA-RAM (content addressable random access memory) to accelerate search operations present in many important real-world applications. Search operations can occupy a significant portion of total execution time and energy consumption, while posing a difficult performance problem to tackle using traditional memory hierarchy concepts. In essence, CA-RAM is a direct hardware implementation of the well-known hashing technique. Searchable records are stored in CA-RAM at a location determined by a hash function, defined on their search key. After a database has been built, looking up a record in CA-RAM typically involves a single memory access followed by a parallel key matching operation. Compared with a conventional CAM (content addressable memory) solution, CA-RAM capitalizes on dense SRAM and DRAM designs, and achieves comparable search performance while occupying much smaller area and consuming significantly less power. This paper presents detailed design aspects of CA-RAM, to be integrated in future general-purpose and application-specific processors and systems. To further motivate and justify our approach, we present two real examples of using CA-RAM to build a high-performance search accelerator targeting: IP address lookup in core routers and trigram lookup in a large speech recognition system

Doubling the number of processing cores on a single processor chip with each technology generation has become conventional wisdom. While future manycore processors promise to offer much increased computational throughput under a given power envelope, sharing critical on-chip resources, such as caches and core- to-core interconnects, poses challenges to guaranteeing predictable performance to an application program. This paper focuses on the problem of sharing on-chip caching capacity among multiple programs scheduled together, especially at the L2 cache level. Specifically, two design aspects of a large shared L2 cache are considered: (1) non-uniform cache access latency and (2) cache contention. We observe that both the aspects have to do with where, among many cache slices, a cache block is mapped to, and present an OS-based approach to managing the on-chip L2 cache memory by carefully mapping data to a cache at the page granularity. We show that a reasonable extension to the OS memory management subsystem and simple architectural support enable enforcing high-level policies to achieve application performance isolation and improve program performance predictability thereof.

This paper presents a study on macro data load, an efficient mechanism to enhance loaded value reuse. A macro data load brings into the processor a maximum-width data value the cache port allows, saves it in an internal structure, and facilitates reuse by later loads. A comprehensive limit study using a generalized memory value reuse table (MVRT) shows the significantly increased reuse opportunities provided by macro data load. We also describe a modified load store queue design as an implementation of the proposed concept. Our quantitative study shows that over 35% of L1 cache accesses in the SPEC2k integer and MiBench programs can be eliminated, resulting in a related energy reduction of 24% and 35% on average, respectively.

This paper presents and studies a distributed L2 cache management approach through OS-level page allocation for future many-core processors. L2 cache management is a crucial multicore processor design aspect to overcome non-uniform cache access latency for good program performance and to reduce on-chip network traffic and related power consumption. Unlike previously studied hardware-based private and shared cache designs implementing a "fixed" caching policy, the proposed OS-micro architecture approach is flexible; it can easily implement a wide spectrum of L2 caching policies without complex hardware support. Furthermore, our approach can provide differentiated execution environment to running programs by dynamically controlling data placement and cache sharing degrees. We discuss key design issues of the proposed approach and present preliminary experimental results showing the promise of our approach

Lowering power consumption in microprocessors, whether used in portables or not, has now become one of the most critical design concerns. On-chip cache memories tend to occupy dominant chip area in microprocessors, and it becomes increasingly important to design power-efficient cache memories. This paper describes an experimental low-power on-chip cache system designed for a 32-bit processor core called CalmRISC/sup TM-/32. A number of architectural optimizations were applied to the instruction and data caches, which significantly decrease the number of tag and data memory accesses and the amount of memory traffic to and from off-chip memory. Implemented in a 0.18 /spl mu/m CMOS technology, the presented instruction and data caches consume 90 /spl mu/A/MHz and 72 /spl mu/A/MHz at 1.8 V, respectively.

Providing adequate data bandwidth is extremely important for a future wide-issue processor to achieve its full performance potential. Adding a large number of ports to a data cache, however, becomes increasingly inefficient and can add to the hardware complexity significantly. This paper takes an alternative or complementary approach for providing more data bandwidth, called data decoupling. This paper especially studies an interesting, yet less explored, behavior of memory access instructions, called access region locality, which is concerned with each static memory instruction and its range of access locations at runtime. Our experimental study using a set of SPEC95 benchmark programs shows that most memory access instructions reference a single region at runtime. Also shown is that it is possible to accurately predict the access region of a memory instruction at runtime by scrutinizing the addressing mode of the instruction and the past access history of it. We describe and evaluate a wide-issue superscalar processor with two distinct sets of memory pipelines and caches, driven by the access region predictor. Experimental results indicate that the proposed mechanism is very effective in providing high memory bandwidth to the processor, resulting in comparable or better performance than a conventional memory design with a heavily multiported data cache that can lead to much higher hardware complexity.

Providing adequate data bandwidth is extremely important for a wide-issue superscalar processor to achieve its full performance potential. Adding a large number of ports to a data cache however becomes increasingly inefficient and can add to the hardware complexity significantly. This paper takes an alternative or complementary approach for providing more data bandwidth, called the data-decoupled architecture. The approach, with support from the compiler and/or hardware, partitions the memory stream into two independent streams early in the processor pipeline, and feeds each stream to a separate memory access queue and cache. Under this model, the paper studies the potential of decoupling memory accesses to program's local variables that are allocated on the run-time stack. Using a set of integer and floating-point programs from the SPEC95 benchmark suite, it is shown that local variable accesses constitute a large portion of all the memory references, while their reference space is very small, averaging around 7 words per (static) procedure. To service local variable accesses quickly, two optimizations fast data forwarding and access combining, are proposed and studied. Some of the important design parameters, such as the cache size, the number of cache ports, and the degree of access combining, are studied based on simulations. The potential performance of the proposed scheme is measured using various configurations, and it is concluded that the scheme can become a viable alternative to building a single multi-ported data cache.

This paper studies an interesting yet less explored behavior of memory access instructions, called access region locality. Unlike the traditional temporal and spatial data locality that focuses on individual memory locations and how accesses to the locations are inter-related, the access region locality concerns with each static memory instruction and its range of access locations at run time. We consider program's data, heap, and stack regions in this paper. Our experimental study using a set of SPEC95 benchmark programs shows that most memory reference instructions access a single region at run time. Also shown is that it is possible to accurately predict the access region of a memory instruction at run time by scrutinizing the addressing mode of the instruction and the past access region history of it. A simple run-time access region predictor is developed that is similar to a branch predictor in structure. We describe and evaluate a superscalar processor with two distinct sets of memory pipelines, driven by the access region predictor. Experimental results indicate that the proposed mechanism is very effective in providing high memory bandwidth to the processor, resulting in comparable or better performance than a conventional memory design with a heavily multi-ported data cache that can lead to much higher hardware complexity.

We propose a new universal High-Level Information (HLI) format to effectively integrate front-end and back-end compilers by passing front-end information to the back-end compiler. Importing this information into an existing back-end leverages the state-of-the-art analysis and transformation capabilities of existing front-end compilers to allow the back-end greater optimization potential than it has when relying on only locally-extracted information. A version of the HLI has been implemented in the SUIF parallelizing compiler and the GCC back-end compiler. Experimental results with the SPEC benchmarks show that HLI can provide GCC with substantially more accurate data dependence information than it can obtain on its own. Our results show that the number of dependence edges in GCC can be reduced by an average of 48% for the integer benchmark programs and an average of 54% for the floating-point benchmark programs studied, which provides greater flexibility to GCC's code scheduling pass. Even with the scheduling optimization limited to basic blocks, the use of HLI produces moderate speedups compared to using only GCC's dependence tests when the optimized programs are executed on MIPS R4600 and R10000 processors.

DICE is a shared-bus multiprocessor based on a distributed shared-memory architecture, known as Cache-Only Memory Architecture (COMA). Unlike previous COMA proposals for large-scale multiprocessing, DICE utilizes the COMA to effectively decrease the gap between modern high-performance microprocessors and the bus. As microprocessors become faster and demand more bandwidth, the already limited scalability of a shared bus decreases even further. DICE tries to optimize the COMA for a shared-bus medium, in particular to reduce detrimental effects of the cache coherence and the "last memory block" problem on replacement. In this paper, we present a global bus design for a bus-based COMA multiprocessor using the IEEE Futurebus+ standard backplane bus and the Texas Instruments chip-set. Our design demonstrates that necessary bus transactions for DICE can be done efficiently with existing standard bus signals. Considering the benefits of the COMA and the little design complexity it adds to the conventional shared-bus multiprocessor design, a bus-based COMA multiprocessor such as DICE can be become a viable candidate for future shared-bus multiprocessor designs.