Search

Owing to the considerations of cell density and low static power consumption, nonvolatile random-access memory (NVRAM) has been a promising candidate for collaborating with a dynamic random-access memory (DRAM) as the main memory in modern computer systems. As NVRAM also brings technical challenges (e.g., limited endurance and high writing cost) to computer system developers, the concept of write reduction becomes the famous doctrine in NVRAM-based system design. Unfortunately, a well-known machine learning algorithm, random forest, will generate a massive amount of write traffic to the main memory space during its construction phase. In other words, a random forest hits the Achilles’ heel of NVRAM-based systems. For remedying this pain, our work proposes an NVRAM-friendly random forest algorithm, namely, Amine, for an NVRAM-based system. The design principle of Amine is to replace write operations with read accesses without raising the read complexity of the random forest algorithm. According to experimental results, Amine can effectively decrease the latency of random forest construction by 64%, compared with the original random forest algorithm. [ABSTRACT FROM AUTHOR]

With the increasing demand of massive/big data applications, nonvolatile memory (NVM), such as phase-change memory (PCM), has become a promising candidate to replace DRAM because of its low leakage power, nonvolatility, and high density. However, most of the existing memory read/write intensive algorithms and data structures are not aware of the PCM write heterogeneity in terms of both energy consumption and latency. In particular, self-balancing binary search trees, which are widely used to manage massive data in the big-data era, were designed without the consideration of PCM characteristics. Thus, the multiple rotations of the tree balancing process would degrade the memory performance. This work explores the relations among nodes and analyzes tree operations, and the node indexing and address mapping are redesigned to reduce the tree management overhead on single-level cell (SLC) PCM by decreasing the number of bit flips of tree rotations. When multilevel cell (MLC) PCM is included, our address mapping algorithm is developed to reduce the total energy consumption and latency with considerations of the heterogeneous write operations of different cell states. Experimental results show that our solution significantly outperforms the original implementation of a self-balancing binary search tree when the amount of data is large. [ABSTRACT FROM AUTHOR]

Recently, nonvolatile random-access memory (NVRAM) has been regarded as the most up-and-coming main memory technology in embedded and Internet-of-Things (IoT) systems due to its attractive features: zero-static power consumption and high memory cell density. However, the endurance issue as a “nightmare” always haunts NVRAM system developers. Worse still, NVRAM’s lifespan will wear out soon in embedded applications because their data management systems usually utilize an indexing scheme to maintain small data. Plus, a node structure within the indexing scheme will be frequently updated because of data creation and deletion. Therefore, many previous works rethink B+-tree indexing scheme on an NVRAM-based system. The most previous studies focused on reducing the amount of write traffic to memory. Unfortunately, they are failed to extend the NVRAM lifespan because their solution cannot evenly distribute the amount of write traffic to each memory cell. Additionally, prior solutions have not considered that all nodes within B+-tree indexing structure have different update frequencies. Based on such the observation, this work proposes a wear-leveling-aware B+-tree design, namely, waB+-tree, to consider the update frequency of each node within the B+-tree structure, so as to evenly scatter the amount of write traffic to the NVRAM cells. According to our experiments, the proposed waB+-tree shows the encouraging results of endurance improvement. [ABSTRACT FROM AUTHOR]

Nonvolatile random access memory (NVRAM) has been regarding a promising technology to replace DRAM as the main memory in embedded systems owing to its nonvolatility and low idle power consumption. However, due to the asymmetric read/write costs and limited lifetime of NVRAM, most of the existing fundamental algorithms are not NVRAM-friendly with their write pattern and write intensiveness. Thus, existing fundamental algorithms for NVRAM embedded devices has been revealed. For instance, as the sorting algorithm is one of the most fundamental algorithms, most of the existing sorting algorithms are not NVRAM-friendly because they impose heavy write traffic [i.e., $\mathcal {O}(n\lg {n})$ ] on main memory, where $n$ is the number of unsorted elements. To resolve this issue, this article proposes a write-once sorting algorithm, namely B*-sort, to reduce the amount of write traffic on NVRAM-based main memory. B*-sort adopts a brand-new concept, i.e., tree-based sort, inspired by the binary-search-tree structure to achieve the write-once property which can guarantee the optimal endurance during the sorting process. According to the experimental results, B*-sort can achieve significant performance improvement for sorting on NVRAM-based systems. [ABSTRACT FROM AUTHOR]

The virtual memory technique provides a large and cheap memory space by extending the memory space with storage devices. It applies context switch to asynchronously swapping pages between memory and storage devices for hiding the long response time of storage devices when a page fault occurs. However, the overall context switch overhead is high because the context switch itself is a complex function and would further incur TLB shootdown/flush and compulsory CPU cache misses after context switches. On the contrary, as the rapid responsiveness improvement of high-end storage devices, we observe that the response time of high-end storage devices catches up and gradually becomes smaller than the overall context switch overhead. At this turning point, to further enhance the system responsiveness, we advocate adopting synchronous swapping rather than context switch in response to page faults. Meanwhile, we propose a strategy, called shadow huge page management, to further improve the overall system performance by minimizing the overall time overheads caused by page faults and page swappings. Evaluation results show that the proposed system can efficiently reduce the total CPU wasting time. [ABSTRACT FROM AUTHOR]

Modern nonvolatile memories (NVMs) are widely recognized as energy-efficient replacements of classical memory/storage media, such as SRAM, DRAM, and mechanical hard disk. Among the popular NVMs, the skyrmion racetrack memory (SK-RM) is well known for its high storage density and unique supports of insert/delete operations. However, the existing algorithms designed for classical media might experience serious performance degradation when working on the SK-RM, due to the distinct characteristics of SK-RM. Thus, the existing algorithms should be redesigned to adapt to the brand-new memory model based on the SK-RM, so as to fully reveal the potentials of SK-RM. In particular, many existing algorithms tend to access the in-memory data in a random-hopping fashion, which generates many time-consuming shift operations of SK-RM. It is therefore crucial for the existing algorithms to eliminate unnecessary shift operations of SK-RM to boost the performance of the algorithms. In many modern applications, such as multimedia and data analysis, it is a common operation to process two or more arrays/vectors of data to perform certain computation tasks. In the arrays/vectors, an appropriate data placement strategy is critical for avoiding unnecessary shift operations of SK-RM. The observation thus motivates this work in proposing a recursive back-to-back data placement manner to effectively reduces the shift operations of SK-RM. To demonstrate the back-to-back data placement, we take sorting algorithms as a case study, and propose a novel shift-limited sorting algorithm for SK-RM. Analytical studies show that the shift-limited sort effectively enhances the time complexity of classical merge sort from $\mathcal {O}(dn\lg n)$ to $\mathcal {O}(n\lg n)$ , where $d$ is the bit distance between adjacent access ports on the nanotracks of the SK-RM. After that, the efficacy of the proposed shift-limited sort is then verified by experimental studies, where the results are encouraging. [ABSTRACT FROM AUTHOR]

Due to the ever-growing demands of larger capacity of flash storage devices, various new manufacturing techniques have been proposed to provide high-density and large-capacity NAND flash devices. Among these new techniques, 3-D NAND flash is regarded as one of the most promising candidates for the next-generation flash storage devices. 3-D NAND flash brings high bit density and significant cost saving via stacking memory cells vertically. However, the read/write and erase units of 3-D NAND flash also grow larger than those of traditional planner flash devices. This growing trend of read/write and erase units for 3-D NAND flash imposes significant management difficulties, such as the grown size of mapping information, decreased garbage collection efficiency, and worsened write amplification issue. To alleviate these negative impacts of the growing read/write and erase units, this paper proposes a multiregional space management design to achieve subpage-level management while adaptively adjusting mapping granularity by considering the user behaviors. The proposed design was evaluated by a series of experiments, and results show that the access performance can be improved by 64%. [ABSTRACT FROM AUTHOR]

Nonvolatile random access memory (NVRAM) is becoming a popular alternative as the memory and storage medium in battery-powered embedded systems because of its fast read/write performance, byte-addressability, and nonvolatility. A well-known example is phase-change memory (PCM) that has much longer life expectancy and faster access performance than NAND flash. When NVRAM is considered as both main memory and storage in battery-powered embedded systems, existing page cache mechanisms have too many unnecessary data movements between main memory and storage. To tackle this issue, we propose the concept of “union page cache,” to jointly manage data of the page cache in both main memory and storage. To realize this concept, we design a partial page cache strategy that considers both main memory and storage as its management space. This strategy can eliminate unnecessary data movements between main memory and storage without sacrificing the data integrity of file systems. A series of experiments was conducted on an embedded platform. The results show that the proposed strategy can improve the file accessing performance up to 85.62% when PCM used as a case study. [ABSTRACT FROM AUTHOR]

At present, nonvolatile random access memory (NVRAM) is widely considered as a promising candidate for the next-generation storage medium due to its appealing characteristics, including short read/write latency, byte addressability, and low idle energy consumption. In addition, to provide a higher bit density, multilevel-cell (MLC) NVRAM has also been proposed. Nevertheless, when compared with conventional single-level-cell (SLC) NVRAM, MLC NVRAM has longer write latency and higher energy consumption. Hence, the performance of MLC NVRAM-based storage systems could be degraded due to the lengthened write latency. The performance degradation is further magnified by existing journaling file systems (JFS) on MLC NVRAM-based storage devices due to the JFS’s fail-safe policy of writing the same data twice. Such observations motivate us to propose multiwrite-mode JFSs (mwJFSs) to alleviate the drawbacks of MLC NVRAM and boost the performance of MLC NVRAM-based JFS. The proposed mwJFS differentiates the data retention requirement of journaled data and applies different write modes to enhance the access performance with lower energy consumption. A series of experiments was conducted to demonstrate the capability of mwJFS on MLC NVRAM-based storage systems. [ABSTRACT FROM AUTHOR]

In the big data era, data-intensive applications have growing demand for the capacity of DRAM main memory, but the frequent DRAM refresh, high leakage power, and high unit cost bring serious design issues on scaling up DRAM capacity. To address this issue, a nonvolatile dual inline memory module (NVDIMM), which is a hybrid memory module, becomes a possible alternative to replace the DRAM as main memory in some data-intensive applications. The NVDIMM that consists of a small-sized high-speed DRAM and a large-sized low-cost nonvolatile memory (i.e., flash memory) has the serious performance issue on accessing data stored in the flash memory because of the huge performance gap between the DRAM and the flash memory. However, there is limited room to adopt a complex caching algorithm for using the DRAM as the cache of flash memory in the NVDIMM main memory, because a complex caching algorithm itself would already cause too much performance degradation on handling each request to access the NVDIMM main memory. In this paper, we present a lightweight caching algorithm to boost NVDIMM performance by minimizing the cache management overhead and reducing the frequencies to access flash memory. A series of experiments was conducted based on popular benchmarks, and the results demonstrate that the proposed algorithm can effectively improve the performance of the NVDIMM main memory. [ABSTRACT FROM AUTHOR]

Non-volatile random-access memory (NVRAM) becomes a mainstream storage device in embedded systems due to its favorable features, such as small size, low power consumption, and short read/write latency. Unlike dynamic random access memory (DRAM), NVRAM has asymmetric performance and energy consumption on read/write operations. Generally, on NVRAM, a write operation consumes more energy and time than a read operation. Unfortunately, current mobile/embedded file systems, such as EXT2/3 and EXT4, are very unfriendly for NVRAM devices. The reason is that current mobile/embedded file systems employ a journaling mechanism for increasing its data reliability. Although a journaling mechanism raises the safety of data in a file system, it also repeatedly writes data to a data storage while data is committed and checkpointed. Though several related works have been proposed to reduce the amount of write traffic to NVRAM, they still cannot effectively minimize the write amplification of a journaling mechanism. Such observations motivate us to design a two-phase write reduction journaling file system called wrJFS. In the first phase, wrJFS classified data into two categories: Metadata and user data. As the size of metadata is usually very small (few bytes), byte-enabled journaling strategy will handle metadata during commit and checkpoint stages. In contrast, the size of user data is very large relative to metadata; thus, user data will be processed in the second phase. In the second phase, user data will be compressed by hardware encoder to reduce the write size and managed compressed-enabled journaling strategy to avoid the write amplification on NVRAM. Moreover, we analyze the overhead of wrJFS and show that the overhead is negligible. According to the experimental results, the proposed wrJFS outperforms other journaling file systems even though the experiments include the overhead of data compression. [ABSTRACT FROM AUTHOR]

The high-density, low-cost triple-level-cell (TLC) flash memory has gradually dominated the flash storage market because of the fast-growing demand for storage capacity. However, the advances of manufacturing technologies also make TLC flash memory suffer serious performance degradation compared with the low-density, high-performance single-level-cell (SLC) flash memory. To address this issue, some vendors enable blocks of TLC flash memory to work as high-performance, low-density SLC blocks. In contrast to the past research that allocates a fixed number of TLC blocks as SLC blocks to improve the device performance to a certain degree, we propose a utilization-aware self-tuning design to trade more unused storage capacity for better system performance. The introduced design dynamically adjusts and maximizes the number of SLC blocks according to the amount of data stored in the storage device at runtime. With the self-tuning design, a flash storage device can not only achieve high access performance but also provide enough storage capacity. The performance and capability of proposed design were evaluated by a series of experiments, and the results are very encouraging. [ABSTRACT FROM PUBLISHER]

The papers in this special section focus on emerging non-volatile memory technologies (NVM). Emerging NVM technologies have attracted significant interest in recent years because of the fast-growing performance and capacity demands on memory and storage in the big data era. Well known examples include the 3D XPoint memory and various NVDIMM hybrid memory technologies. They have shown potential towards larger memory and storage capacities with nearly zero leakage power, while extending memory/ system architecture design approaches. The unique characteristics of NVM technologies not only introduce new opportunities, but simultaneously create challenges to the designs at multiple levels of abstraction in computer systems, including those of device management, CPU cache management, memory/storage architecture, and system design. Furthermore, emerging NVM technologies also drive the development of techniques which perform computing operations in memory, i.e., processing-in-memory (PIM), by taking advantage of crossbar-based accelerators using NVMs. Thus, for the emerging NVM technologies, there is an urgent need for technology innovation, modeling, analysis, design, and application, ranging from the device-level to the system-level. [ABSTRACT FROM AUTHOR]

The high cell density, multilevel-cell programming, and manufacturing process variance force the new coming flash memory to have large bit-error-rate variance among blocks and pages, where a flash chip consists of multiple blocks and each block consists of a fixed number of pages. In order to avoid storing the crucial user data in more fragile pages, conventional flash management software tends to aggressively discard the high bit-error-rate area in the unit of a block. However, together with the aggressive discarding strategies and the enlarging sizes of pages/blocks of next generation flash memory, the available space of flash devices might encounter a very sharp degradation and therefore result in rapidly-shortened device lifespan. Thus, we advocate the concept of “graceful space degradation” to mitigate this problem by discarding the high bit-error-rate (or worn-out) area in the unit of pages (instead of blocks). To furthermore realize this concept, we are the pioneer to put forward an “uneven space management” to manage flash blocks containing different number of bad pages. Our design especially focuses on placing data with different access behaviors to make the best uses of blocks with different available space so as to ultimately prolong the device lifespan with good access performance. The experiments were conducted based on representative realistic workloads, and the results reveal that the proposed design can extend the device lifetime by at least 2.38 times of that of existent approaches, with very limited performance overheads. [ABSTRACT FROM PUBLISHER]

Recently, phase change memory (PCM) has become a promising candidate to replace dynamic RAM as main memory due to its low power consumption, fast I/O performance, and byte addressability. Accompanied with the merits, the adoption of PCM may suffer from its physical characteristic of limited write endurance. Wear leveling is a well-known approach to address this issue. For PCM main memory, the design of wear leveling should stress operation efficiency and overhead reduction. Nevertheless, conventional designs are usually dedicated to prolonging the lifetime of PCM in the best effort. In this paper, we propose a novel perspective that, instead of valuing PCM lifetime exploitation as the first priority, we turn to satisfy the product warranty period. With such a paradigm shift, the management overhead of wear-leveling mechanisms could be reduced so as to achieve further enhancement of operation efficiency. To this end, we propose a warranty-aware page management design that introduces novel criteria used to determine the state of a page by taking both the product warranty period and the write cycles of a page into consideration. Theoretical analysis is also conducted to investigate the properties and performance of the proposed management. To show the effectiveness of the proposed design, we collected real traces by running SPEC2006 benchmarks with different write intensity workloads. The experimental results showed that our design reduced the overhead to one-third that of the state-of-the-art designs while still providing the same level of performance. [ABSTRACT FROM PUBLISHER]

Even though 3D flash memory presents a grand opportunity to huge-capacity non-volatile memory, it suffers from serious program disturbance problems. In contrast to the past efforts in error correction codes and the work in trading the space utilization for reliability, we propose a disturbance-relaxation scheme that can alleviate the negative effects caused by program disturbance inside a physical block. This scheme does not introduce any extra overheads on encoding or storing of extra redundant data. In particular, a methodology is proposed to reduce the data error rate by distributing unavoidable disturbance errors to the flash-memory space of invalid data, with the considerations of the physical organization of 3D flash memory. A series of experiments was conducted based on real multi-layer 3D flash chips, and it showed that the proposed scheme could significantly enhance the reliability of 3D flash memory. [ABSTRACT FROM AUTHOR]

Address mapping for flash storage devices has been a challenging design issue for controllers because of rapidly growing device capacity. In contrast with existing mapping methods, this study proposes a capacity-independent address mapping method to decouple the required on-device RAM space from the capacity of a flash storage device. Especially, the required RAM size of the proposed method depends only on the user accessed data set, which is also referred to as the working set, while the page-level performance can be nearly achieved. In addition, a simple but practical wear-leveling design is proposed with the capability in lifetime estimation of flash storage devices. Experiments of the proposed scheme obtained encouraging results. [ABSTRACT FROM AUTHOR]

Motivated by the needs to enhance the performance of garbage collection in low-cost flash storage devices, we propose a victim block selection design to efficiently identify the blocks for erases and reclaim the space of invalid data without extensively scanning flash memory for the data status stored in the storage, so as to improve the garbage collection performance on reclaiming the space of invalid data. Moreover, this design could easily identify and reclaim the space released by file systems. Experiments based on benchmark traces show significant performance improvement of garbage collection with limited system overheads. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel multi-version B^+-tree index structure, called block-based multi-version B^+-tree ( BbMVBT), for indexing multi-versions of data items in an embedded multi-version database (EMVDB ) on flash memory. An EMVDB needs to support streams of update transactions and version-range queries to access different versions of data items maintained in the database. In BbMVBT, the index is divided into two levels. At the higher level, a multi-version index is maintained for keeping successive versions of each data item. These versions are allocated consecutively in a version block. At the lower level, a version array is used to search for a specific data version within a version block. With the reduced index structure of BbMVBT, the overhead for managing the index in processing update operations can be greatly reduced. At the same time, BbMVBT can also greatly reduce the number of accesses to the index in processing version-range queries. To ensure sufficient free blocks for creating version blocks for efficient execution of BbMVBT, in this paper, we also discuss how to perform garbage collection using the purging-range queries for reclaiming “old” versions of data items and their associated entries in the index nodes. Analysis of the performance of BbMVBT is presented and verified with performance studies using both synthetic and real workloads. The performance results illustrate that BbMVBT can significantly improve the read and write performance to the multi-version index as compared with MVBT even though the sizes of the version blocks are not large. [ABSTRACT FROM PUBLISHER]

Cost has been a major driving force in the development of the flash-memory technology. Because of this, serious challenges are now faced for future products on reliability and performance requirements. In this work, we propose a management strategy to resolve the reliability and performance problems of many flash-memory products. A three-level address translation architecture with an adaptive block mapping mechanism is proposed to accelerate the address translation process with a limited amount of the RAM usage. Parallelism of operations over multiple chips is also explored with the considerations of the write constraints of advanced multilevel cell flash-memory chips. The capability of the proposed approach is analyzed with reliability considerations and evaluated by experiments over realistic workloads with respect to the reliability and performance improvement. [ABSTRACT FROM AUTHOR]