During past decades, the capacity of NAND flash memory has been increasing dramatically, leading to the use of nonvolatile flash in the system’s memory hierarchy. The increasing capacity of NAND flash memory introduces a large RAM footprint to store the logical to physical address mapping. The demand-based approach can effectively reduce and well control the RAM footprint. However, extra address translation overhead is also introduced which may degrade the system performance. In this article, we present CDFTL, an adaptive Caching mechanism for Demand-based Flash Translation Layer, for NAND flash memory storage systems. CDFTL adopts both the fine-grained entry-based caching mechanism to exploit temporal locality and the coarse-grained translation-page-based caching mechanism to exploit spatial locality of workloads. By selectively caching the on-demand address mappings and adaptively changing the space configurations of two granularities, CDFTL can effectively utilize the RAM space and improve the cache hit ratio. We evaluate CDFTL under a real hardware embedded platform using a variety of I/O traces. Experimental results show that our technique can achieve an 11.13% reduction in average system response time and a 35.21% reduction in translation block erase counts compared with the previous work.

The density of flash memory chips has doubled every two years in the past decade and the trend is expected to continue. The increasing capacity of NAND flash memory leads to large RAM footprint on address mapping management. This paper proposes a novel Demand-based block-level Address mapping scheme with a two-level Caching mechanism (DAC) for large-scale NAND flash storage systems. The objective is to reduce RAM footprint without excessively compromising system response time. In our technique, the block-level address mapping table is stored in fixed pages (called the translation pages) in the flash memory. Considering temporal locality that workloads exhibit, we maintain one cache in RAM to store the on-demand address mapping entries. Meanwhile, by exploring both spatial locality and access frequency of workloads with another two caches, the second-level cache is designed to cache selected translation pages. In such a way, both the most-frequently-accessed and sequentially accessed address mapping entries can be stored in the cache so the cache hit ratio can be increased and the system response time can be improved. To the best of our knowledge, this is the first work to reduce the RAM cost by employing the demand-based approach on block-level address mapping schemes. The experiments have been conducted on a real embedded platform. The experimental results show that our technique can effectively reduce the RAM footprint while maintaining similar average system response time compared with previous work.

This paper aims to totally remove intercore communication overhead with joint computation and communication task scheduling for streaming applications on Multiprocessor System-on-Chips (MPSoCs). Our basic idea is to let some computation and communication tasks be executed in earlier periods (the added periods are called the prologue) such that intercore data transfer can be finished before the execution of the tasks that need the data to start. In particular, we solve the following problem: how to do rescheduling in such a way that the schedule length can be minimized with the minimum prologue length (the number of periods in the prologue) while the intercore communication overhead can be totally removed? To solve this problem, we first perform schedulability analysis and obtain the upper bound of the times needed to reschedule each computation task. Then we formulate the problem as an Integer Linear Programming (ILP) formulation and obtain an optimal solution. We evaluate our technique with a set of benchmarks from both real-life streaming applications and synthetic task graphs. The experimental results show that our technique can achieve significant reductions in schedule length and energy consumption compared with the previous work.

This paper targets at an embedded system with phase change memory (PCM) and NAND flash memory. Although PCM is a promising main memory alternative and is recently introduced to embedded system designs, its endurance keeps drifting down and greatly limits the lifetime of the whole system. Therefore, this paper presents a block-level flash memory management scheme, WAB-FTL, to effectively manage NAND flash memory while reducing write activities of the PCM-based embedded systems. The basic idea is to preserve each bit in flash mapping table hosted by PCM from being inverted frequently during the process of mapping table update. To achieve this, a new merge strategy is adopted in WAB-FTL to delay the mapping table update, and a tiny mapping buffer is used for caching frequently updated mapping records. Experimental results based on Android traces show that WAB-FTL can effectively reduce write activities when compared with the baseline scheme.

Due to the variable garbage collection latency, NAND flash memory storage systems may suffer long system response time, especially when the flash memory is close to be full. Most of existing flash translation layer (FTL) schemes focus on improving the average response time but ignore to provide a desirable worst case response time upper bound. This paper proposes a Real-time Flash Translation Layer (RFTL) scheme to hide the long garbage collection latency while satisfying a worst case response time upper bound that achieves an ideal case. We achieve this by using a distributed partial garbage collection policy that enables RFTL to reclaim the space and to serve the write requests simultaneously. A new block-level address mapping approach is designed to guarantee enough free space to serve the write request arriving at any time period. Experimental results show that our scheme improves both the worst case system response time and the average system response time compared with previous work.

This paper presents a space reuse strategy for flash translation layers in SLC nand flash storage systems. The basic idea is to prevent a block with many free pages from being erased in a merge operation. The preserved blocks are further reused as replacement blocks. In such a way, the space utilization and the number of erase counts of each block in a nand flash are enhanced. By employing the reuse strategy, we propose a reuse-aware flash translation layer (FTL) called reuse-aware NFTL (RNFTL) to improve the endurance and space utilization of single level cell (SLC) nand flash. We provide the performance analysis of RNFTL for frequent update operations and sequential write operations, and theoretically compare RNFTL with representative FTL schemes. We also discuss the opportunity to apply the reuse strategy in log-block-based FTL schemes. To the best of our knowledge, this is the first work to employ a space reuse strategy in FTLs to improve the space utilization and endurance of nand flash. The experiments have been conducted on a set of traces collected from real workload in daily life. The results show that the space reuse strategy can effectively improve space utilization, block lifetime and wear-leveling compared with the previous work.

The new write constraints of multi-level cell (MLC) NAND flash memory make most of the existing flash translation layer (FTL) schemes inefficient or inapplicable. In this paper, we solve several fundamental problems in the design of MLC flash translation layer. The objective is to reduce the garbage collection overhead so as to reduce the average system response time. We make the key observation that the valid page copy is the essential garbage collection overhead. Based on this observation, we propose two approaches, namely, concentrated mapping and postponed reclamation, to effective reduce the valid page copies. We conduct experiments on a set of benchmarks from both the real world and synthetic traces. The experimental results show that our scheme can achieve a significant reduction in the average system response time compared with the previous work.

NAND flash memory is widely used in embedded systems due to its non-volatility, shock resistance and high cell density. In recent years, various Flash Translation Layer (FTL) schemes (especially hybrid-level FTL schemes) have been proposed. Although these FTL schemes provide good solutions in terms of endurance and wear-leveling, none of them have considered to reuse free pages in both data blocks and log blocks during a merge operation. By reusing these free pages, less free blocks are needed and the endurance of NAND flash memory is enhanced. We evaluate our reuse strategy using a variety of application specific I/O traces from Windows systems. Experimental results show that the proposed scheme can effectively reduce the erase counts and enhance the endurance of flash memory.

The increasing capacity of NAND flash memory leads to large RAM footprint on address mapping in the Flash Translation Layer (FTL) design. The demand-based approach can reduce the RAM footprint, but extra address translation overhead is also introduced which may degrade the system performance. This paper proposes a two-level caching mechanism to selectively cache the on-demand page-level address mappings by jointly exploiting the temporal locality and the spatial locality of workloads. The objective is to improve the cache hit ratio so as to shorten the system response time and reduce the block erase counts for NAND flash memory storage systems. By exploring the optimized temporal-spatial cache configurations, our technique can well capture the reference locality in workloads so that the hit ratio can be improved. Experimental results show that our technique can achieve a 31.51% improvement in hit ratio, which leads to a 31.11% reduction in average system response time and a 50.83% reduction in block erase counts compared with the previous work.

Due to its properties of high density, in-place update, and low standby power, phase change memory (PCM) becomes a promising main memory alternative in embedded systems. On the other hand, NAND flash memory is widely used as a secondary storage and has been integrated into PCM-based embedded systems. Since both NAND flash memory and PCM have limited lifetime, how to effectively manage NAND flash memory in PCM-based embedded systems, while considering the endurance issue is very important. In this paper, we present for the first time a write-activity-aware NAND flash memory management scheme, called PCM-FTL, to effectively manage NAND flash memory and enhance the endurance of PCM-based embedded systems. The basic idea is to preserve each bit in flash mapping table, which is stored in PCM, from being inverted frequently, i.e., we focus on minimizing the number of bit flips in a PCM cell when updating the flash mapping table. PCM-FTL employs a two-level mapping mechanism, which not only focuses on minimizing the write activities of PCM but also considers the access behavior of I/O requests. We evaluate PCM-FTL using a variety of realistic I/O traces. Experimental results show that the proposed technique can achieve an average reduction of 93.10% and a maximum reduction of 98.98% in the maximum number of bit flips for a PCM-based embedded system with 1GB NAND flash memory. We hope this work can serve as a first step towards the design of write-activity-aware FTL for the PCM-based embedded systems via simple and feasible modifications.

In this article, we focus on solving the energy optimization problem for real-time streaming applications on multiprocessor System-on-Chip by combining task-level coarse-grained software pipelining with DVS (Dynamic Voltage Scaling) and DPM (Dynamic Power Management) considering transition overhead, inter-core communication and discrete voltage levels. We propose a two-phase approach to solve the problem. In the first phase, we propose a coarse-grained task parallelization algorithm called RDAG to transform a periodic dependent task graph into a set of independent tasks by exploiting the periodic feature of streaming applications. In the second phase, we propose a scheduling algorithm, GeneS, to optimize energy consumption. GeneS is a genetic algorithm that can search and find the best schedule within the solution space generated by gene evolution. We conduct experiments with a set of benchmarks from E3S and TGFF. The experimental results show that our approach can achieve a 24.4% reduction in energy consumption on average compared with the previous work.

In this paper, we propose a hybrid-level flash translation layer (FTL) called RNFTL (Reuse-Aware NFTL) to improve the endurance and space utilization of NAND flash memory. Our basic idea is to prevent a primary block with many free pages from being erased in a merge operation. The preserved primary blocks are further reused as replacement blocks. In such a way, the space utilization and the number of erase counts for each block in NAND flash can be enhanced. To the best of our knowledge, this is the first work to employ a reuse-aware strategy in FTL for improving the space utilization and endurance of NAND flash. We conduct experiments on a set of traces that collected from real workload in daily life. The experimental results show that our technique has significant improvement on space utilization, block lifetime and wear-leveling compared with the previous work.

In this paper, we jointly optimize computation and communication task scheduling for streaming applications on MPSoC. The objective is to minimize schedule length by totally removing inter-core communication overhead. By minimizing schedule length, the system performance can be improved by adopting a smaller period or exploring the slacks generated for energy reduction with DVS. To guarantee the schedulability of communication tasks, we perform the schedulability analysis, and theoretically obtain the upper bound of the times needed to reschedule each computation task. Based on the analysis, we formulate the scheduling problem as an ILP (Integer Linear Programming) formulation and obtain an optimal solution. We evaluate our technique with a set of benchmarks from both real-life streaming applications and synthetic task graphs. The simulation results show that our technique can achieve a 27.72% reduction in schedule length and a 13.38% reduction in energy consumption on average compared with the previous work.

In this paper, we focus on solving the problem of removing inter-core communication overhead for streaming applications on chip multiprocessors. The objective is to totally remove inter-core communication overhead while minimizing the overall memory usage. By totally removing inter-core communication overhead, a shorter period can be applied and system throughput can be improved. Our basic idea is to let tasks with intra-period data dependencies transform to inter-period data dependencies so as to overlap the execution of computation and inter-core communication tasks. To solve the problem, we first perform analysis and obtain the bounds of the times needed to reschedule each task. Then we formulate the scheduling problem as an integer linear programming (ILP) model and obtain an optimal schedule. We perform simulations on a set of benchmarks from both real-life streaming applications and synthetic task graphs. The simulation results show that the proposed approach can achieve significant reduction in schedule length and improve the memory usage compared with the previous work.