Search

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.

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.

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.

Pattern recognition applications such as face recognition and agricultural product detection have drawn a rapid interest on Cyber–Physical–Social-Systems (CPSS). These CPSS applications rely on the deep neural networks (DNN) to conduct the image classification. However, traditional DNN inference models in the cloud could suffer from network delay fluctuations and privacy leakage problems. In this regard, current real-time CPSS applications are preferred to be deployed on edge-end embedded devices. Constrained by the computing power and memory limitations of edge devices, improving the memory management efficacy is the key to improving the quality of service for model inference. First, this study explored the incremental loading strategy of model weights for the model inference. Second, the memory space at runtime is optimized through data layout reorganization from the spatial dimension. In particular, the proposed schemes are orthogonal to existing models. Experimental results demonstrate that the proposed approach reduced the memory consumption by 61.05% without additional inference time overhead.

Battery-powered mobile devices substantially constrain energy resources. Process-level energy profiling tools can identify the most energy-consuming process and detail the energy usage of hardware components. With the help of energy profiling tools, programmers can fine-tune the energy consumption of processes to extend battery lifetime. However, profiling tools are highly dependent on hardware and must be calibrated for each hardware platform. Furthermore, for any new hardware components, new energy estimation formulas must be created. To solve these two problems regarding off-the-shelf products, this work proposes a two-phase calibrating approach. The first phase reconstructs the power table with a power meter, while the second creates new energy estimation formulas using linear regression analysis. The accuracy of the calibrated tool was evaluated in five scenarios and its error ratio is proven to be below 10%, occasionally less than 5%. Hence, this proposed approach to energy consumption profiling represents a major step in off-the-shelf devices.

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.

This research responds to practical requirements in the porting of embedded software over platforms and the well-known multiprocessor anomaly. In particular, we consider the task scheduling problem when the system configuration changes. With mutual-exclusive resource accessing, we show that new violations of the timing constraints of tasks might occur even when a more powerful processor or device is adopted. The concept of scheduler stability and rules are then proposed to prevent scheduling anomaly from occurring in task executions that might be involved with task synchronization or I/O access. Finally, we explore policies for bounding the duration of scheduling anomalies.

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.

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.

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.

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 flashmemory access and its life time (due to wear-levelling). In this research, we propose a highly efficient method for online hot-data identification with limited space requirements. Different from the past work, multiple independent hash functions are adopted to reduce the chance of false identification of hot data and provide predictable and excellent performance for hot-data identification. We not only propose an efficient implementation of the proposed framework but also conduct a series of experiments to verify the performance of the proposed method, in which very encouraging results are presented.

Universal Serial Bus (USB) is a popular standard for PC peripheral devices because of its versatile peripheral interconnection specifications. USB not only provides simplified hardware connectors but also supports for various bus traffics, such as isochronous and bulk transfer activities. Although the USB specifications provide a way for users to specify the upper bound on the number of bytes for each data transfer in a 1ms time frame, little work is done to provide QoS guarantees for devices (e.g., the lower bound on the bytes for each device type in a 1ms time frame) and a mechanism in enforcing the guarantees. In this paper we propose a cyclic-executive-based bandwidth reservation and scheduling method to support QoS guarantees over USB, especially for those isochronous bus activities. The proposed bandwidth reservation and scheduling method could reserve USB bandwidth for devices in an on-demand fashion. The capability of the proposed scheme was shown by the implementation and demonstration of a USB-based surveillance system prototype which adopted the proposed scheme.

Flash memory is among the top choices for storage media in ubiquitous computing. With a strong demand of high-capacity storage devices, the usages of flash memory quickly grow beyond their original designs. The very distinct characteristics of flash memory introduce serious challenges to engineers in resolving the quick degradation of system performance and the huge demand of main-memory space for flash-memory management when high-capacity flash memory is considered. Although some brute-force solutions could be taken, such as the enlarging of management granularity for flash memory, we showed that little advantage is received when system performance is considered. This paper proposes a flexible management scheme for large-scale flash-memory storage systems. The objective is to efficiently manage high-capacity flash-memory storage systems based on the behaviors of realistic access patterns. The proposed scheme could significantly reduce the main-memory usages without noticeable performance degradation.

With a significant growth of the markets for consumer electronics and various embedded systems, flash memory is now an economic solution for storage systems design. For index structures which require intensively fine-grained updates/modifications, block-oriented access over flash memory could introduce a significant number of redundant writes. It might not only severely degrade the overall performance but also damage the reliability of flash memory. In this paper, we propose a very different approach which could efficiently handle fine-grained updates/modifications caused by B-Tree index access over flash memory. The implementation is done directly over the flash translation layer (FTL) such that no modifications to existing application systems are needed. We demonstrate that the proposed methodology could significantly improve the system performance and, at the same time, reduce the overheads of flash-memory management and the energy dissipation, when index structures are adopted over flash memory.

Flash memory is now a critical component in building embedded or portable devices because of its nonvolatile, shock-resistant, and power-economic nature. With the very different characteristics of flash memory, mechanisms proposed for many block-oriented storage media cannot be directly applied to flash memory. Distinct from the past work, we propose an adaptive striping architecture to significantly boost the system performance. The capability of the proposed mechanisms and architecture is demonstrated over realistic prototypes and workloads.

A dynamic-voltage-adjustment method is proposed to reduce the power consumption of a flash memory storage system, depending on the system workload. The usefulness of the proposed method is demonstrated by a series of experiments with very encouraging results.

Embedded and ubiquitous computing is an exciting new paradigm that provides computing and communication services all the time and everywhere. Its systems are now affecting every aspect of our life to the point that they are hidden inside various appliances. This emergence is a natural outcome of research and technological advances in embedded systems, pervasive computing and communications, wireless networks, mobile computing, distributed computing and agent technologies, etc. This special issue has collected best papers presented in the 2007 IFIP International Conference on Embedded and Ubiquitous Computing (EUC 2007), held in Taipei, Taiwan, ROC. These papers present state of the art in the areas of real-time and embedded software, power-aware hardware management, network security, embedded compiler techniques, mobility and security in advanced wireless networks, and data crawling. Best papers in the EUC 2007 conference were invited for submission. All the invited papers had undergone an intensive review process. The Editor-in-Chief agreed with our recommendation of the acceptance of eleven high quality papers. The first four papers focus on software techniques in embedded and ubiquitous systems. The first paper, entitled “Task Scheduling for Context Minimization in Dynamically Reconfigurable Platforms”, by Nei-Chiung Perng et al. describes a real-time approach to reducing the number of FPGA configuration contexts in dynamic reconfigurable systems. The second paper, entitled “Real-Time Embedded Software Design for Mobile and Ubiquitous Systems” by Pao-Ann Hsiung et al., describes a component-based software architecture that supports automatic synthesis and verification, aiming at high software design productivity. The third paper, entitled “SIGMA system: A Multi-OS Environment for Embedded Systems”, by Wataru Kanda et al., introduces a virtualization technique to support multiple operating systems for multi-processor embedded architectures. The fourth paper, entitled “Compiling for Reduced Bit-Width Queue Processors” by Arquimedes Canedo et al., presents a compiler technique for generating compact codes for embedded processors. The next three papers are on hardware management for embedded and ubiquitous computing. The fifth paper in this special issue, entitled “Energy-Efficient Considerations on a Variable-Bitrate PCI-Express Device”, by Jian-Jia Chen et al., presents a dynamic power management (DPM) algorithm for variable-bitrate PCI devices for power saving. The sixth paper, entitled “Design and Synthesis of An Multiprocessor System-on-Chip Architecture for Real-Time Biomedical Signal Processing in Gamma Cameras”, by Kai Sun et al., discusses communication synthesis and areacost reduction for an MPSOC Gamma Camera. The seventh paper, entitled “Variable Length Pattern Matching for Hardware Network Intrusion Detection System”, by Chun Xue et al., presents a high-performance hardware-based network intrusion detection system. The last four papers are related to wireless-network applications. The eighth paper in this special issue, entitled “A Lightweight Authentication Protocol for Low-Cost RFID” by Hung-Yu Chien et al., proposes a lightweight L.-P. Chang (*) Department of Computer Science, National Chiao-Tung University, Hsin-Chu, Taiwan, Republic of China e-mail: lpchang@cs.nctu.edu.tw