Computing near the source of data has been proven effective in terms of energy conservation, latency improvement, and privacy preservation. With this, edge intelligence refers to local CNN inference in embedded edge devices. Because edge devices are highly resource-constrained, in practice they store CNN model(s) in external flash memory and load them (or part of) during runtime inference. However, flash memory is subject to time-related retention errors, and thus a dilemma is that without error correction, a CNN model in flash memory quickly deteriorates and becomes useless. On the other hand, strong error correction involves extra read sensing and read retrying. Due to the concern of reliability, the lineup of embedded serial flash memory offers low-density solutions only. In this study, we investigate graceful degradation of CNN models in uncorrected high-density flash storage for edge intelligence. Inspired by the observation that in popular CNN models, the majority of CNN weight parameters share a few monotonic bit patterns in their high-order bits, we propose mapping the frequent bit patterns to low flash-cell voltage levels for protection against retention errors. Furthermore, as CNN layers show different levels of tolerance to bit errors, we also propose using adaptive cell-bit density to provide non-uniform error protection among layers. We conducted experiments on popular CNN designs, including VGG16, ResNet50, and InceptionV3, under realistic effects of flash aging. Results show that with prior methods, the inference accuracy of ResNet50 degrades to 70.7% in just three months; by contrast, with our approach, the degradation is less than 1% and the accuracy remains at 91.6% after one year of retention.

Energy harvesting enables long-running sensing applications on tiny Internet of Things (IoT) devices without a battery installed. To overcome the intermittency of ambient energy sources, system software creates intermittent computation using checkpoints. While the scope of intermittent computation is quickly expanding, there is a strong demand for data storage and local data processing in such IoT devices. When considering data storage options, flash memory is more compelling than other types of nonvolatile memory due to its affordability and availability. We introduce iFKVS, a flash-based key-value store for multisensor IoT devices. In this study, we aim at supporting efficient key-value operations while guaranteeing the correctness of program execution across power interruptions. For indexing of multidimensional sensor data, we propose a quadtree-based structure for the minimization of extra writes from splitting and rebalancing; for checkpointing in flash storage, we propose a rollback-based algorithm that exploits the capabilities of byte-level writing and one-way bit flipping of flash memory. Experimental results based on a real energy-driven testbed demonstrate that with the same index structure design, our rollback-based approach obtains a significant reduction of 45% and 84% in the total execution time compared with checkpointing using write-ahead logging (WAL) and copying on write (COW), respectively.

NAND-based Solid-State Disks (SSDs) have become the mainstream storage solution thanks to their high I/O performance and data persistency. Modern SSDs boost their storage capacity by increasing the flash cell-bit density, resulting in severe leakage-induced bit errors over time. Low-Density Parity-Check (LDPC) is a common error correcting code for flash memory, which features incremental decoding strength levels through adding extra voltage sensing levels. However, when bit error rate becomes high, LDPC decoding with strong correction will be very slow. In this study, we identify that the read latency is strongly correlated with the method of bit labeling on cell threshold-voltage states, and based on this finding we propose using adaptive bit labeling to optimize the SSD read latency. Specifically, our method employ 2-3-2 Gray Coding as the default mode, and frequently-read data will be switched to using the least-significant page and center-significant page with 1-2-4 Gray Coding for fast reading. Our experimental results show that our design greatly outperforms static bit labeling and a state-of-the-art method.

A crucial design factor for users of smart mobile devices is the latency of graphical interface interaction. Switching a background app to foreground is a frequent operation on mobile devices and the latency of this process is highly perceivable to users. Based on an Android smartphone, through analysis of memory reference generated during the app-switching process, we observe that file (virtual) pages and anonymous pages are both heavily involved. However, to our surprise, the amounts of the two types of pages in the main memory are highly imbalanced, and frequent I/O operations on file pages noticeably slows down the app-switching process. In this study, we advocate to improve the app-switching latency by rectifying the skewed kernel page reclaiming. Our approach involves two parts: proactive identification of unused anonymous pages and adaptive balance between file pages and anonymous pages. As mobile apps are found inflating their anonymous pages, we propose identifying unused anonymous pages in sync with the app-switching events. In addition, Android devices replaces the swap device with RAM-based zram, and swapping on zram is much faster than file accessing on flash storage. Without causing thrashing, we propose swapping out as many anonymous pages to zram as possible for caching more file pages. We conduct experiments on a Google Pixel phone with realistic user workloads, and results confirm that our method is adaptive to different memory requirements and greatly improves the app-switching latency by up to 43% compared with the original kernel.

Optane Persistent Memory (PM) is a pioneering solution to byte-addressable PM for commodity systems. However, the performance of Optane PM is highly workload-sensitive, rendering many prior designs of Key-Value (KV) store inefficient. To cope with this reality, we advocate rethinking KV store design for Optane PM. Our design follows a principle of Single-stream Writing with managed Multi-stream Reading (SWMR): Incoming KV pairs are written to PM through a single write stream and managed by an ordered index in DRAM. Through asynchronously sorting and rewriting large sets of KV pairs, range queries are handled with a managed number of concurrent streams. YCSB results show that our design improved upon existing ones by 116% and 21% for write-only throughput and read-write throughput, respectively.

3D NAND flash is prone to bit errors due to severe charge leakage. Modern SSDs adopt LDPC for bit error management, but LDPC can incur a high read latency through iterative adjustment to the reference voltage. Bit scrambling helps reduce inter-cell interference, and with it, ones and zeros equally contribute to raw data. We observed that as bit errors develop, the 0-bit ratio in raw data deviates from 50%. Inspired by this property, we propose a method for fast adjustment to the reference voltage, involving a placement step and a fine-tuning step. Our method uses only a few hundreds of bytes of RAM but improves the average read latency upon existing methods by up to 24%.

Developing toward battery-less, energy-harvesting designs is a promising direction for sensor-scale devices. The recent introduction of byte-addressable, nonvolatile memory (NVRAM) enables intermittent computing, which preserves as much program progress across power interruptions as possible using fine-grained checkpoints. Sensing applications strongly demand local storage for near-data processing, and there is no exception for intermittent computing devices. While checkpointing on program progress is being studied recently, there is little work regarding how sensor file systems support intermittent computing. On power recovery, although the program progress is reverted to the latest checkpoint, the storage state stays at the instant of power loss. To remedy this problem, we present a lightweight file system for efficient operations on files and checkpoints. Our design exploits the byte addressability of NVRAM and uses as much in-place byte writing as possible while guaranteeing the safety of checkpoint operations. We evaluated our design against two prior checkpoint-enabled file systems, and results show that on average, our design reduced the total time overhead and energy consumption by 77% and 78%, respectively.

Log-structured-merge (LSM) trees are a highly write-optimized data structure for lightweight, high-performance key-value (KV) stores. Furthermore, solid-state drives (SSDs) are a crucial component for I/O acceleration. Conventional LSM-over-SSD designs involve multiple software layers, including the LSM tree, host file system, and flash translation layer (FTL), which introduce cascading write amplifications. To manage the write amplifications from different layers, we propose KVSSDs, which are a close integration of LSM trees and the FTL. KVSSDs exploit the FTL mapping mechanism to implement copy-free compaction of LSM trees, and they enables direct data allocation in flash memory for efficient garbage collection. Our design also uses a fine-grained, dynamic striping policy to fully exploit the rich internal parallelism of multichip SSDs. The experimental results indicated that our LSM-SSD integrated design reduced the write amplification by 86% and improved the throughput by 383% compared with a conventional LSM-over-SSD design.

Android apps become increasingly memory-demanding as software vendors add more and more new features to their apps. In the mean time, Android users often launch multiple apps and conveniently switch back and forth among the apps. Although running multiple apps imposes a high pressure on memory management, virtual-memory swap, an essential feature to improve the degree of multitasking, is disabled in fear of premature retirement of flash-based storage devices. Instead, Android employs a termination-based, process-level memory reclaiming method. We observed that process killing is, unfortunately, not effective in memory reclaiming and is highly negative to user experience. In this study, we advocate re-thinking using swap in Android for improved user experience with managed write stress on flash storage. Based on a series of empirical analyses of swap activities, we propose an enhanced page replacement policy and a page-compressing frontswap module. The proposed page replacement policy jointly considers page activeness and compressibility to boost the compression ratio of swap writes. A sampled-based method for page compressibility prediction is introduced so that decisions on page replacement can be made without compressing every page. We also design a frontswap module that strategically organizes compressed pages in the swap space for reducing the overhead of swap I/O operations. Experimental results showed that compared with process killing, our method improved the app launching time and energy consumption by 58% and 19%, respectively; compared with the original swap, our approach reduced the swap write stress by 65%.

Solid state disks (SSDs) employ internal parallelism to boost their input/output (I/O) performance, but a high degree of flash parallelism inevitably consumes a high level of current. To budget power or support multiple power sources, system software may force an SSD into a new power mode that has a specific current supply limit. This paper introduces a firmware approach to optimize SSD internal parallelism subject to a current supply limit. The proposed method involves two steps. First, we constructed current models of flash operations on the basis of real-world measurement results. Second, we designed a firmware scheduler to determine the actual starting time of each flash operation. The proposed scheduler accounted for flash aging, process variation, and internal resource contention, and it avoided any current cap violation by checking a few time points instead of every unit of time. Our experimental results indicated that the proposed approach outperformed existing methods with respect to I/O response time and throughput under realistic workloads.

3-D NAND flash has become the mainstream in modern SSD designs because it offers superior bit storage density. However, while enjoying the large capacity, 3-D NAND flash is highly prone to bit errors due to its cylindrical cell structure. Modern SSDs employ the low-density parity-check (LDPC) error-correcting code to manage bit errors in 3-D NAND flash. Strong LDPC error correction is subject to a high time overhead, because it may require many sensing levels on read to obtain sufficiently confident bit input information. By exploiting the bit-error rate variation among vertical layers of 3-D NAND flash, we propose diluting bit errors of cells at error-prone, lower layers by mixing them with bit data of cells from reliable, upper layers. Cells at reliable layers provide highly confident bit input information that helps reduce the number of sensing levels on cell at error-prone layers. Our experimental results showed that the proposed approach improved the read throughput by 29% and reduced the read latency by 43% compared with a conventional multichip SSD design.

While the computing power of mobile devices has been quickly evolving in recent years, the growth of mobile storage capacity is, however, relatively slower. A common problem shared by budget-phone users is that they frequently run out of storage space. This article conducts a deep inspection of file usage of mobile applications and their potential implications on user experience. Our major findings are as follows: First, mobile applications could rapidly consume storage space by creating temporary cache files, but these cache files quickly become obsolete after being re-used for a short period of time. Second, file access patterns of large files, especially executable files, appear highly sparse and random, and therefore large portions of file space are never visited. Third, file prefetching brings an excessive amount of file data into page cache but only a few prefetched data are actually used. The unnecessary memory pressure causes premature memory reclamation and prolongs application launching time. Through the feasibility study of two preliminary optimizations, we demonstrated a high potential to eliminate unnecessary storage and memory space consumption with a minimal impact on user experience.

I/O activities of mobile storage are highly synchronous. Flash garbage collection activities in mobile storage introduce extra delay to write requests and negatively impact on user perceived-latency. Runtime write demand is subject to correlation between multiple parameters, such as network connectivity, GPS coordinates, and current time. We propose predicting write demand with a learning algorithm, XGBoost, and conducting background, rate-based garbage collection to optimize write latency without premature, excessive flash erasure. Our method reduced the 99-th percentile write latency by 56% compared to on-demand garbage collection and decreased flash erase count by 51% compared to unconditional background garbage collection.

No abstract available.

Mobile devices, such as smartphones, have become a necessity in our daily life. However, users may notice that after being used for a longtime, mobile devices begin to exhibit a sluggish response. Based on an empirical study on a collection of aged smartphones, this work identified that file fragmentation is among the key factors that contribute to the progressive degradation of response time. This study takes a three-step approach: First, this study designed a set of reproducible file-system aging processes based on User-Interface (UI) script replay. Through the aging processes, it confirmed that file fragmentation quickly emerged, and SQLite files were among the most severely fragmented files. Second, based on the workloads of a selection of popular mobile applications, this study observed that file fragmentation did have an impact on user-perceived latencies. Specifically, the launching time of Chrome on an aged file system was 79 percent slower than it was on a pristine file system. Third, this study evaluated existing treatments of file fragmentation, including space preallocation, persistent journal, and file defragmentation to understand their efficacies and limitations. This study also evaluated a state-of-the-art copyless defragmenter, janusd, to show its advantage over the existing methods.

Log-Structured-Merge (LSM) trees are a write-optimized data structure for lightweight, high-performance Key-Value (KV) store. Solid State Disks (SSDs) provide acceleration of KV operations on LSM trees. However, this hierarchical design involves multiple software layers, including the LSM tree, host file system, and Flash Translation Layer (FTL), causing cascading write amplifications. We propose KVSSD, a close integration of LSM trees and the FTL, to manage write amplifications from different layers. KVSSD exploits the FTL mapping mechanism to implement copy-free compaction of LSM trees, and it enables direct data allocation in flash memory for efficient garbage collection. In our experiments, compared to the hierarchical design, our KVSSD reduced the write amplification by 88% and improved the throughput by 347%.

Read disturbance is a circuit-level noise induced by flash read operations. Read refreshing employs data migration to prevent read disturbance from corrupting useful data. However, it costs frequent block erasure under read-intensive workloads. Inspired by software-controlled cell bit-density, we propose to reserve selected threshold voltage levels as guard levels to extend the tolerance of read disturbance. Blocks with guard levels have a low cell bit-density, but they can store frequently read data without frequent read refreshing. We further propose to convert a high-density block into a low-density one using in-place reprogramming to reduce the need for data migration. Our approach reduced the number of blocks erased due to read refreshing by up to 85% and the average read response time by up to 22%.

NAND flash memory has been the default storage component in embedded systems. One of the key technologies for flash management is the address mapping scheme between logical addresses and physical addresses, which deals with the inability of in-place-updating in flash memory. Demand-based page-level mapping cache is often applied to match the cache size constraint and performance requirement of embedded storage systems. However, recent studies showed that the management overhead of mapping cache schemes is sensitive to the host I/O patterns, especially when the mapping cache is small. This paper presents a novel I/O scheduling scheme, called MAP+, to alleviate this problem. The proposed scheduling approach reorders I/O requests for performance improvement from two angles. Prioritizing the requests that will hit in the mapping cache, and grouping requests with related logical addresses into large batches. Batches of requests are reordered to further optimize request waiting time. Experimental results show that MAP+ improved upon traditional I/O schedulers by 48% and 18% in terms of read and write latencies, respectively.

Recently, smartphone users are becoming reluctant to replace their devices, so providing reliable data storage throughout the increasingly long smartphone replacement cycle is an imminent challenge. We advocate an integrated approach to data deduplication, which involves the host I/O stack and the storage firmware, to reduce the write stress of mobile storage for lifespan extension. First, we identified that the SQLite library produces a large amount of copy-induced duplicate data, which can be fully revealed to the mobile storage through proper file format alignment. Second, inspired by the short flash read latency, we present a firmware-based method to efficiently identify duplicate data without any hardware support. Third, we enhance the flash garbage collector with the awareness of data deduplication. Based on a selection of popular mobile applications, our simulation results show that prior methods, which employ data compression or differential logging, are ineffective for encrypted mobile storage. Compared to flash management without deduplication, our lightweight, integrated approach reduced the total flash-block erase count by 48.7%, average write response time by 43.8%, and total energy consumption by 25.1% on average under the workloads of all the selected mobile applications.

Non-Volatile Memory Express (NVMe) is a specification for next-generation solid-state disks (SSDs). Benefited from the massive internal parallelism and the high-speed PCIe bus, NVMe SSDs achieve extremely high data transfer rates, and they are an ideal solution of shared storage in virtualization environments. Providing virtual machines with Service Level Objective (SLO) compliance on NVMe SSDs is a challenging task, because garbage collection activities inside of NVMe SSDs globally affect the I/O performance of all virtual machines. In this study, we introduce a novel approach, called parallelism reservation, which is inspired by the rich internal parallelism of NVMe SSDs. The degree of parallelism stands for how many flash chips are concurrently active. Our basic idea is to reserve sufficient degrees of parallelism for read, write, and garbage collection operations, making sure that an NVMe SSD delivers stable read and write throughput and reclaims free space at a constant rate. The stable read and write throughput are proportionally distributed among virtual machines for SLO compliance. Our experimental results show that our parallelism reservation approach delivered satisfiable throughput and highly predictable response to virtual machines.

Solid state disks (SSDs) employ internal parallelism for high throughput, but concurrent flash operations can draw a high instantaneous current. Due to power budgeting or power-source changing, SSDs could be forced into a new operation mode with a lower current supply limit. This study presents a flash scheduling algorithm to optimize the SSD internal parallelism subject to the current limit. Based on realistic flash current models, our scheduler decides the actual starting times of every flash operation, and it efficiently examines the peak current only at a few time points. Our experiments show that our approach outperformed existing methods, and its feasibility had been verified on the OpenSSD platform.

Building self-healing SSDs is proven feasible by recent studies. When the stress of a block becomes critical, it can be healed to remove part of the stress. However, with wear leveling, all blocks are evenly worn and have similar stress, and all blocks could undergo the healing process within a short period of time. The intensive heal operations, called heal storms, cause highly unpredictable I/O performance and storage reliability. Inspired by the even distribution of erase counts under wear leveling, we propose to operate wear leveling on virtual erase counts instead of real erase counts. When the balance among virtual erase counts is achieved through wear leveling, all real erase counts become evenly dispersed in a controlled interval. In this way, blocks will undergo healing at different times. Virtual erase counts are progressively adjusted such that all blocks reach their endurance limit when the SSD permanently retires. Our results show that our approach successfully resolved the heal storm problem without impacting on the SSD lifespan.

Flash storage has been a standard component in Android devices. Recent research has reported that application data management in Android involves frequent fsync() operations. The current fsync() implementations, including those of ext4 and F2FS, have several common drawbacks. Specifically, ext4 commits a transaction every time to sync a file, whereas F2FS commits a checkpoint to sync a directory. Committing a transaction or checkpoint flushes all dirty data from the page cache to the flash storage via many small, random block write requests. The resultant high I/O frequency and excessive write traffic cause a high fsync() latency. This study presents an efficient fsync() method, called eager synching, which is based on a simple idea: write less, and write sequentially. To sync a file, eager synching writes only a subset of all dirty data in the page cache to a sequential log space using a few sequential block write requests. It does not involve transaction or checkpoint committing. We successfully implemented eager synching in ext4 and F2FS, and our experimental results show that, compared with the original fsync() methods of ext4 and F2FS, eager synching reduced the average and maximum fsync() latencies by up to 72% and 91%, respectively, block-level write traffic by up to 35%, and I/O frequency by up to 66%. Through enhanced crash recovery procedures, eager synching can successfully recover all previously synched files while still guaranteeing the file system integrity. We also conducted live application replays using the proposed eager synching approach and observed that this approach significantly improved the application frame updating rate and application execution time.

Data compression is beneficial to flash storage lifespan. However, because the design of mobile flash storage is highly cost-sensitive, hardware compression becomes a less attractive option. This study investigates the feasibility of data compression on mobile flash storage. It first characterizes data compressibility based on mobile apps, and the analysis shows that write traffic bound for mobile storage volumes is highly compressible. Based on this finding, a lightweight approach is introduced for firmware-based data compression in mobile flash storage. The controller and flash module work in a pipelined fashion to hide the data compression overhead. Together with this pipelined design, the proposed approach selectively compresses incoming data of high compressibility, while leaving data of low compressibility to a compression-aware garbage collector. Experimental results show that our approach greatly reduced the frequency of block erase by 50.5% compared to uncompressed flash storage. Compared to unconditional data compression, our approach improved the write latency by 10.4% at a marginal cost of 4% more block erase operations.

NAND flash memory has been the default storage component in mobile systems. One of the key technologies for flash management is the address mapping scheme between logical addresses and physical addresses, which deals with the inability of in-place-updating in flash memory. Demand-based page-level mapping cache is often applied to match the cache size constraint and performance requirement of mobile storage systems. However, recent studies showed that the management overhead of mapping cache schemes is sensitive to the host I/O patterns, especially when the mapping cache is small. This paper presents a novel I/O scheduling scheme, called MAP, to alleviate this problem. The proposed scheduling approach reorders I/O requests for performance improvement from two angles: Prioritizing the requests that will hit in the mapping cache, and grouping requests with related logical addresses into large batches. Experimental results show that MAP improved upon traditional I/O schedulers by 30% and 8% in terms of read and write latencies, respectively.

Commodity solid state drives (SSDs) have recently begun involving the adoption of powerful controllers for multichannel flash management at the page level. However, many of these models still use primitive garbage-collection algorithms, because previous approaches are subject to poor scalability with high-capacity flash memory. This study presents Stable Greedy for garbage collection in page-mapping multichannel SSDs. Stable Greedy identifies page-accurate data hotness using block-level information, and jointly considers block space utilization and block stability for victim selection. Its design considers flash wear leveling for SSD lifetime enhancement at the block level as well as at the channel level. Stable Greedy runs at a constant time, and requires limited RAM space. The simulation results revealed that Stable Greedy outperformed previous methods considerably under various workloads and multichannel architectures. Stable Greedy was successfully implemented on the OpenSSD platform, and the actual performance measurements were consistent with the simulation results.

Advanced solid-state disks (SSDs) have been equipped with page-mapping flash translation layers and multichannel architectures. The SSDs employ a RAM-based write buffer, which delays write requests for reducing write traffic, reorders requests for mitigating garbage-collection overhead, and produces parallel page writes for improving channel time utilization. This work presents a novel write buffer algorithm that exploits temporal and spatial correlations among buffer pages. The write-buffer groups temporally or spatially correlate buffer pages and then write the grouped buffer pages to the same flash block. In this way, when the correlated page data are updated in the future, flash blocks will receive bulk page invalidations and become good candidates for garbage collection. With multichannel architectures, the write buffer adaptively disperses read-most sequential data over channels for high page-level parallelism of sequential reads, while clustering write-most sequential data in the same channel for a reduced cost of garbage collection. We evaluated the proposed method and previously proposed buffer algorithms. Our method was shown to outperform the existing methods by up to 134%. We also implemented our buffer design on the OpenSSD platform; the time and space overheads of our design were reported to be very low.

A promising technique to improve the write performance of solid-state disks (SSDs) is to use a disk write buffer. The goals of a write buffer is not only to reduce the write traffic to the flash chips but also to convert host write patterns into long and sequential write bursts. This study proposes a new buffer design consisting of a replacement policy and a write-back policy. The buffer monitors how the host workload stresses the flash translation layer upon garbage collection. This is used to dynamically adjust its replacement and write-back strategies for a good balance between write sequentiality and write randomness. When the garbage collection overhead is low, the write buffer favors high write sequentiality over low write randomness. When the flash translation layer observes a high overhead of garbage collection, the write buffer favors low write randomness over high write sequentiality. The proposed buffer design outperformed existing approaches by up to 20% under various workloads and flash translation algorithms, as will be shown in experiment results.

No abstract available.

Solid-state disks use multichannel architectures to boost their data transfer rates. Because realistic disk workloads have numerous small write requests, modern flash-storage devices adopt a write buffer and a set of independent channels for better parallelism in serving small write requests. When a channel is undergoing garbage collection, it stops responding to inbound write traffic and accumulates page data in the write buffer. This results in contention for buffer space and creates idle periods in channels. This study presents a channel-management strategy, called garbage-collection advancing , which allows early start of garbage collection in channels for increasing the overlap among channel activities of garbage collection and restoring the balance of buffer-space usage among channels. This study further introduces cycle filling , which is a version of garbage-collection advancing tailored for the operation model of flash planes. Experimental results show that the proposed methods greatly outperformed existing designs of multichannel systems in terms of response and throughput. We also successfully implemented the proposed methods in a real solid-state disk and proved their feasibility in real hardware.

Welcome to Taipei, Taiwan, and the IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2013). RTCSA has been a prestigious technical conference sponsored by the IEEE Technical Committee on Real-Time Systems for years. The objective of the conference is to bring together academic researchers and industry developers for intensive discussion of recent advances in the field of embedded systems, real-time systems, and cyber-physical systems.

Multilevel flash memory cells double or even triple storage density, producing affordable solid-state disks for end users. As flash memory endures only limited program-erase cycles, solid-state disks employ wear-leveling methods to prevent any portions of flash memory from being retired prematurely. Modern solid-state disks must consider wear evenness at both block and channel levels. This study first presents a block-level wear-leveling method whose design has two new ideas. First, the proposed method reuses the intelligence available in flash-translation layers so it does not require any new data structures. Second, it adaptively tunes the threshold of block-level wear leveling according to the runtime write pattern. This study further introduces a new channel-level wear-leveling strategy, because block-level wear leveling is confined to a channel, but realistic workloads do not evenly write all channels. The proposed method swaps logical blocks among channels for achieving an eventually-even state of channel lifetimes. A series of trace-driven simulations show that our wear-leveling method outperforms existing approaches in terms of wear evenness and overhead reduction.

In the recent years, commodity solid-state disks have started adopting powerful controllers and implemented page-level mapping for flash management. However, many of these models still use primitive garbage-collection algorithms, because prior approaches do not scale up with the dramatic increase of flash capacity. This study introduces Dual Greedy for garbage collection in page-level mapping. Dual Greedy identifies page-accurate data hotness using only block-level information, and adaptively switches its preference of victim selection between block space utilization and block stability. It can run in constant time and use very limited RAM space. Our experimental results show that Dual Greedy outperforms existing approaches in terms of garbage-collection overhead, especially with large flash blocks.

Using device write buffers is a promising technique to improve the write performance of solid-state disks. The write buffer not only reduces the write traffic to the flash but also produces large and sequential write bursts to the underlying flash translation layer. This study proposes a new buffer design consisting of a replacement policy and a write-back policy. This buffer monitors how the host workload stresses the flash translation layer upon garbage collection, and dynamically adjusts its replacement and write-back strategies for a good balance between write sequentiality and traffic reduction. Experimental results show that the proposed buffer design outperformed existing approaches by up to 20% under various workloads and flash translation algorithms.

Multilevel flash memory cells double or even triple storage density, producing affordable solid-state disks for end users. However, flash lifetime is becoming a critical issue in the popularity of solid-state disks. Wear-leveling methods can prevent flash-storage devices from prematurely retiring any portions of flash memory. The two practical challenges of wear-leveling design are implementation cost and tuning complexity. This study proposes a new wear-leveling design that features both simplicity and adaptiveness. This design requires no new data structures, but utilizes the intelligence available in sector-translating algorithms. Using an on-line tuning method, this design adaptively tunes itself to reach good balance between wear evenness and overhead. A series of trace-driven simulations show that the proposed design outperforms a competitive existing design in terms of wear evenness and overhead reduction. This study also presents a prototype that proves the feasibility of this wear-leveling design in real solid-state disks.

Solid-state disks use flash memory as their storage medium, and adopt a firmware layer that makes data mapping and wear leveling transparent to the hosts. Even though solid-state disks emulate a collection of logical sectors, the I/O delays of accessing all these logical sectors are not uniform because the management of flash memory is subject to many physical constraints of flash memory. This work proposes a collection of black-box tests can detect the geometry inside of a solid-state disk. The host system software can arrange data in the logical disk space according to the detected geometry information to match the host write pattern with the device characteristic for reducing the flash management overhead in solid-state disks.

Replacing power-hungry disks with NAND-flash-based solid-state disks (SSDs) is a recently emerging trend in flash-memory applications. One important SSD design issue is achieving a good balance between cost, performance, and lifetime. This study introduces a hybrid approach to large SSDs that combines MLC NAND flash and SLC NAND flash. Each of these flash architectures has its own drawbacks and benefits, and this study proposes that the two can complement each other. However, there are technical challenges pertaining to data placement, data migration, and wear leveling in heterogeneous NAND flash. The experimental results of our study show that combining 256 MB SLC flash with 20 GB MLC flash produces a hybrid SSD. This hybrid SSD is 1.8 times faster than a purely MLC-flash-based SSD in terms of average response time and improves energy consumption by 46 percent. The proposed hybrid SSD costs only four percent more than a purely MLC-flash-based SSD. The extra cost of a hybrid SSD is very limited and rewarding.

Efficient data indexing is significant to embedded devices, because both CPU cycles and energy are very precious resources. Soft lists, a new index structure for embedded devices with NOR flash, are proposed. The challenge of data indexing over NOR flash is that data update and pointer update may recursively trigger each other. Our approach is to allow a bounded number of probes when a pointer is de-referenced. By this way update and garbage collection is largely simplified, because data can be moved around physical locations without invalidating any pointers. Even better, search with soft lists is very fast, because the probes provide opportunities of forward random skips. Soft lists are evaluated and compared against tree-based index, and soft lists are shown simple but efficient.

On-line task scheduling is a very challenging issue for dual-core real-time embedded systems, because to control priority inversion and to manage system utilization are fundamentally at odds with each other. We propose an on-line dual-core scheduling framework for dynamic workloads with real-time constraints. The processor and the co-processor are dedicated to separate schedulers with different scheduling policies, and precedence constraints among tasks are dealt with the interaction between the two schedulers. We have shown that our proposed scheduling can achieve a good balance between high system utilization and stable task response under realistic workloads.

Solid-state disks (SSDs) are storage devices that emulate hard drives with flash memory. They have been widely deployed in mobile computers as disk drive replacements. Flash memory is organized in terms of erase blocks. With the current technology, a block can reach the end of its lifetime after thousands of erasure operations. Wear leveling is a technique to evenly erase the entire flash memory so that all blocks remain alive as long as possible. This study introduces a new wear-leveling algorithm based the observation that, under a real-life mobile PC's workload, most erasure operations are contributed by a small fraction of blocks. Our key ideas are 1) moving rarely updated data to a block that is extraordinarily worn and 2) avoiding repeatedly involving a block in wear-leveling activities. This study presents a successful implementation of the proposed wear-leveling algorithm using about 200 bytes of RAM in an SSD controller rated at 33 MHz. Evaluation results show that this algorithm achieves even wear of the entire flash memory while reducing the overheads of extra flash-memory operations.

NAND-flash-based SSDs (solid-state disks) are recently used in embedded computers to replace power-hungry disks. This paper presents a hybrid approach to large SSDs, which combines MLC flash and SLC flash. The idea is to complement the drawbacks of the two kinds of NAND flash with each other’s advantages. The technical issues of the design of a hybrid SSD pertain to data placement and wear leveling over heterogeneous NAND flash. Our experimental results show that, by adding a 256 MB SLC flash to a 20 GB MLC-flash array, the hybrid SSD improves over a conventional SSD by 4.85 times in terms of average are improved by 17 % and 14%, respectively. The hybrid SSD is only 2% more expensive than a purely MLC-flash-based SSD, for which the extra cost is limited and very rewarded.

Flash memory has been widely considered as a good alternative for storage system implementations because it offers superior vibration tolerance and power efficiency, compared to hard-disks. Because of its unique characteristics, direct applications of disk management methods over flash memory might result in performance degradation and even the reducing of the lifetime. The management issues become even more challenging, especially when the capacity of flash memory increases significantly in the past few years. In this paper, we summarize our work on several important issues in flash memory management, where system performance and management overheads are considered. The capability of the proposed methodology was evaluated by a series of experiments to provide more insights in system designs

Hot data identification for flash memory storage systems not only imposes great impacts on flash memory garbage collection but also strongly affects the performance of flash memory access and its lifetime (due to wear-levelling). This research proposes a highly efficient method for on-line hot data identification with limited space requirements. Different from past work, multiple independent hash functions are adopted to reduce the chance of false identification of hot data and to provide predictable and excellent performance for hot data identification. This research not only offers an efficient implementation for the proposed framework, but also presents an analytic study on the chance of false hot data identification. A series of experiments was conducted to verify the performance of the proposed method, and very encouraging results are presented.

While flash memory has been widely adopted for storage systems for various embedded systems, issues of performance and reliability have started receiving growing attention in recent years. How to provide efficient roll back and quick mounting for flash-memory file systems has become an important research topic in recent years, in addition to the work on effective garbage collection and superb runtime performance. Such an observation motivates our work on the investigation of efficient initialization and crash recovery of flash-memory file systems based on log structures. A methodology is proposed for the acceleration of mounting and crash recovery for log-based file systems. A system prototype based on a well-known flash-memory file system, YAFFS, was implemented with performance evaluation. Experimental results show that the proposed methodology can reduce mounting time significantly, regardless of whether the file system is properly unmounted.

Many existing approaches on flash-memory management are based on RAM-resident tables in which one single granularity size is used for both address translation and space management. As high-capacity flash memory is becoming more affordable than ever, the dilemma of how to manage the RAM space or how to improve the access performance is emerging for many vendors. In this article, we propose a tree-based management scheme which adopts multiple granularities in flash-memory management. Our objective is to not only reduce the run-time RAM footprint but also manage the write workload, due to housekeeping. The proposed method was evaluated under realistic workloads, where significant advantages over existing approaches were observed, in terms of the RAM space, access performance, and flash-memory lifetime.

Flash-memory technology is becoming critical in building embedded systems applications because of its shock-resistant, power economic, and nonvolatile nature. With the recent technology breakthroughs in both capacity and reliability, flash-memory storage systems are now very popular in many types of embedded systems. However, because flash memory is a write-once and bulk-erase medium, we need a translation layer and a garbage-collection mechanism to provide applications a transparent storage service. In the past work, various techniques were introduced to improve the garbage-collection mechanism. These techniques aimed at both performance and endurance issues, but they all failed in providing applications a guaranteed performance. In this paper, we propose a real-time garbage-collection mechanism, which provides a guaranteed performance, for hard real-time systems. On the other hand, the proposed mechanism supports non-real-time tasks so that the potential bandwidth of the storage system can be fully utilized. A wear-leveling method, which is executed as a non-real-time service, is presented to resolve the endurance problem of flash memory. The capability of the proposed mechanism is demonstrated by a series of experiments over our system prototype.

For many applications with spatial data management such as Geographic Information Systems (GIS), block-oriented access over flash memory could introduce a significant number of node updates. Such node updates could result in a large number of out-place updates and garbage collection over flash memory and damage its reliability. In this paper, we propose a very different approach which could efficiently handle fine-grained updates due to R-tree index access of spatial data over flash memory. The implementation is done directly over the flash translation layer (FTL) without any modifications to existing application systems. The feasibility of the proposed methodology is demonstrated with significant improvement on system performance, overheads on flash-memory management, and energy dissipation.

Many computer systems, such as those for open system environments or multimedia services, need an efficient schedulability test for online admission control of new jobs. Although various polynomial time schedulability tests have been proposed, they often fail to decide the schedulability of the system precisely when the system is heavily loaded. On the other hand, most precise schedulability tests proposed to date have a high complexity and may not be suitable for online tests. We present new efficient online schedulability tests for both the periodic process model [C. L. Liu et al., (1973)] and the multiframe process model [A. K. Mok et al., (1997)] in uniprocessor environments. The schedulability tests are shown to be more precise and efficient than any existing polynomial-time schedulability tests. Moreover, the tests can be done incrementally as each new task arrives at the system. Our proposed tests can also be used for the multiframe model where a task may have different computation times in different periods. We show the performance of the proposed schedulability tests in several simulation experiments.