Ethernet-SSDs incorporate built-in Ethernet connectivity, allowing them to function as standalone network-attached storage devices. This architecture enables efficient and scalable disaggregated storage by providing direct network access without host dependencies. Understanding their internal architecture and fine-grained performance interactions is critical for advancing this emerging design, yet is difficult to study on proprietary hardware. In this paper, we present EEMU, a configurable and accurate Ethernet-SSD emulator built on the FEMU framework. EEMU reproduces the end-to-end NVMeoF I/O translation path and models latency across three key components: the Network Interface, the NVMeoF Target Module, and the AXI Bus. It further employs a fine-grained parametric latency model that decomposes end-to-end latency into component-level contributions, enabling systematic exploration of architectural trade-offs via controlled parameterization. Experiments show that EEMU closely matches both component-level behaviors and end-to-end performance across diverse Ethernet-SSD configurations.

QLC NAND flash is widely adopted in modern storage systems. By trading off read/write performance for storage density through a “time-for-space" approach, QLC enables ultra-high storage capacity. To mitigate performance degradation, Gray code and the two-step programming (TSP) algorithm are used. However, Gray code also has limitations: multiple Gray codes incur circuit overhead, while a single Gray code causes extra I/O latency overhead. This paradox seems unsolvable at first glance, requiring an innovative solution that maintains I/O performance without additional circuit overhead. A promising solution lies in selecting an appropriate Gray code and preventing hot data placement on slow physical pages. This paper proposes BDP, a novel Bi-Directional Programming scheme that adopts a single Gray code to fit both traditional (forward) and reverse programming directions based on TSP. The objective of BDP is to resolve the inherent contradiction between I/O performance preservation and implementation overhead. BDP optimizes the system performance through hardware/software co-design. At the hardware level, a fixed Gray code is employed to avoid additional circuit complexity. At the software level, two strategies (i.e. hotness-aware data allocation and background data migration) are proposed to further mitigate the misplacement of hot data on slow pages in QLC SSDs. The experimental results demonstrate that BDP significantly reduces the allocation of hot data to slow pages and enhances overall I/O performance compared to representative schemes.

Spatio-temporal data are continuously generated and grow exponentially with the rapid proliferation of mobile devices. Efficient storage and indexing of spatio-temporal Big Data are crucial for supporting fast queries. Due to their high write throughput and scalability, distributed NoSQL data stores such as HBase are widely adopted as storage engines in spatio-temporal Big Data systems. These systems require a key-value-based storage model to convert one or a group of spatio-temporal data points into a single key-value pair. However, existing techniques cannot govern an inherent dilemma caused by adding a time dimension within spatial information, that is, we can either optimize for space-preferred or time-preferred queries but not both. In this paper, we propose Cymo, a flexible storage model with query-aware indexing that dynamically adapts to varying query patterns across different spatial regions and evolving query behaviors over time. Our key idea is to partition the spatio-temporal space into multiple subspaces, allowing each subspace to optimize its storage model based on its specific query characteristics. Cymo features a learning model that predicts query patterns for each subspace using historical workloads. Additionally, it introduces a virtual layer that abstracts the heterogeneity of different storage models, providing a unified query interface. This design ensures that storage model variations remain transparent to applications while enabling effective query optimization based on diverse query patterns. We have implemented Cymo on HBase and integrated it into GeoMesa, a representative spatio-temporal Big Data system. Experimental results on real taxi datasets demonstrate that Cymo significantly improves query performance, achieving speedups of 1.53× to 10× compared to GeoMesa. The open-source implementation of Cymo has been released for public access.

With the rapid growth of mobile devices and applications, a prodigious number of spatio-temporal data are generated constantly. To process these data for applications like traffic forecasting, existing spatio-temporal systems rely on the move-data-to-computation paradigm. However, this approach incurs significant data movement overhead between hosts and storage devices, particularly when a spatio-temporal query is executed on a non-preferred data layout or when the query has a small result size due to its inherent nature. To address this issue, this work introduces Groundhog, an efficient in-storage computing technique designed specifically for spatio-temporal queries, aimed at reducing unnecessary data movement and computations. Groundhog introduces three key designs for efficient in-storage computing: (i) a self-contained and segment-based storage model, which is lightweight for in-storage computing and enables fine-grained pruning for spatio-temporal queries; (ii) a set of fine-grained techniques to optimize query processing inside storage devices for spatio-temporal queries; and (iii) an in-storage-computing-aware query planner, which offloads spatio-temporal queries in a fine-grained manner using a cost-based approach. We implemented Groundhog on real hardware and demonstrated how to apply fine-grained techniques to accelerate various spatio-temporal queries. Extensive experiments conducted on real-world datasets demonstrate that Groundhog achieves significant performance improvements, with latency reductions of up to$81\%$for widely used spatio-temporal queries compared to host computing solutions.

To manage massive trajectory data, we propose a novel cloud-based trajectory data management technique, Springbok, which leverages cloud storage to balance performance and monetary costs. Unlike existing key-value, relational, and time series databases, Springbok natively models trajectories as first-class data objects via a spatio-temporal series data model, enabling efficient insertion, query processing, and cost-aware storage management in cloud environments. It further employs an optimized indexing scheme that accounts for both the characteristics of trajectory data and the properties of cloud storage, enabling efficient query execution. In addition, Springbok adopts a tiered cloud storage architecture with carefully designed data layouts, flushing, access, and compression policies, guided by cloud storage performance characteristics and pricing models, to jointly optimize performance and cost. We implemented a fully functional prototype of Springbok supporting core trajectory queries, deletion, and crash recovery, and evaluated it using both real-world and synthetic datasets. The results show that Springbok achieves comparable or better performance than state-of-the-art systems in most cases while significantly reducing monetary costs, demonstrating its effectiveness in balancing performance and cost.

SRAM is widely used in computing-in-memory (CIM) neural network accelerators because of its relatively mature technology and good compatibility with complementary metal oxide semiconductor logic process. Digital SRAM-CIM is favored by researchers because of its stability and accuracy. However, the current digital SRAM-CIM macro only supports the weight-stationary dataflows, which means the repeated movement of graph data. Some special deep neural network layers, such as depth-wise, make the utilization of computing resources inside CIM low. To overcome these problems, we propose C-CIM, which can switch between input-stationary and weight-stationary dataflows and support matrix multiplication as well as convolution operations with multiple mainstream convolution kernel sizes (1×1, 3×3, 5×5 and 7×7). The C-CIM achieves an average performance of 27.31TOPS/W@8b at a frequency of 1GHz. Experimental results show that our proposed SRAM-CIM successfully outperforms baseline in terms of performance optimization, achieving up to 7.6× performance speedup and up to 86.84% reduction in activation relocation.

Compressional SSDs can be a mixed blessing. While they offer users expanded logical space beyond the physical capacity, they complicate the Flash Translation Layer (FTL) design by requiring a larger Logical-to-Physical (L2P) address mapping, which places a heavier burden on the limited in-SSD memory, leading to a degraded I/O performance. In this paper, we aim to reduce the memory footprint of the L2P mapping table in compressional SSDs by proposing a novel N-to-1 L2P mapping table design that consolidates multiple logical entries into a single entry. This approach eliminates the duplication of physical page numbers when a physical page contains several compressed logical pages. To accommodate the dynamic compression ratios of real-world workloads, we introduce promotion and demotion that enable mapping table entries to migrate between pages with different compression ratios. Additionally, to address the issue of partial invalidation-where some compressed logical pages within a physical page are invalid due to the N-to-1 mapping-we present a compression-aware garbage collection algorithm aimed at minimizing the number of copy operations for partially invalid physical pages. We have implemented our design in MQsim, a widely used SSD simulator, and have conducted a series of experiments to evaluate the effectiveness of the proposed techniques. The results demonstrate that our approach significantly reduces the mapping table size in compressional SSDs, leading to an improved mapping table cache hit ratio and a reduced I/O latency compared to traditional compressional SSDs.

The rapidly growing mobile market is pushing flash storage manufacturers to expand capacity into the terabyte range. However, this presents a significant challenge for mobile storage management: more logical-to-physical page mappings are desired to be efficiently managed and cached while the available caching space is extremely limited. This motivates us to shift toward a new learning-based paradigm: rather than maintaining mappings for individual pages, the learning-based approach can represent mapping relationships for a set of continuous pages. However, to construct linear models, existing methods that either consume the already-limited memory space or reuse flash garbage collection demonstrate poor model construction capabilities or significantly degrade flash performance, making them impractical for real-world use. In this paper, we propose LFTL, a practical, learning-based on-demand flash translation layer design for flash management in mobile devices. In contrast to prior work that centered around gathering sufficient mappings for linear model construction, our key insight is that linear patterns can be extracted and refined by leveraging the orderly, LPA-aligned write stream typical of mobile devices. By doing this, highly accurate linear models can be constructed regardless of the constraints of mobile device's cache limitation. We have implemented a fully functional prototype of LFTL based on FEMU. Our evaluation results show that LFTL is more adaptable to memory-constrained storage devices than state-of-the-art learning-based approaches.

Gray code, a voltage-level-to-data-bit translation scheme, is widely used in QLC SSDs. However, it causes the four data bits in QLC to exhibit significantly different read and write performance with up to 8 × latency variation, severely impacting the worst-case performance of QLC SSDs. This paper presents BDP, a novel Bi-Directional Programming scheme. Based on a fixed Gray code, BDP combines both the normal (forward) and reverse programming directions to enable runtime programming direction arbitration. Experimental results show that BDP can effectively improve the read and write performance of SSD compared to representative schemes.

In-storage computing (ISC) aims to mitigate the excessive data movement between the host memory and storage by offloading computation to storage devices for in-situ execution. However, ensuring data freshness remains a key challenge for practical ISC. For performance considerations, many data processing systems implement a buffer manager to cache part of the on-disk data in the host memory. While the host applications commit updates to the in-memory cached copies of the data, ISC operators offloaded to the device only have access to the on-disk persistent data. Thus, ISC may miss the most recent updates from the host and produce incorrect results after reading the stale and inconsistent data from the persistent storage. With this limitation, current ISC can only be used in read-only settings where the on-disk data are not subject to concurrent updates. To tackle this problem, we propose a cooperative buffer manager for ISC to transparently provide data freshness guarantees to host applications. Proposed methods allow the device to synchronize with the host buffer manager and decide whether to read the most recent copy of data from host memory or flash memory. We implement our method based on a real hardware platform and perform evaluation with a Bs--tree based key-value store. Experiments show that our method can provide transparent data freshness for host applications with reduced latency.

Massive spatio-temporal data are continuously generated by various moving objects. To process these data for applications such as traffic forecasting, existing spatio-temporal systems all employ the move-data-to-computation paradigm. However, this approach suffers from significant data movement overhead between hosts and drives. To address this issue, this work introduces Groundhog, an efficient in-storage computing technique designed specifically for spatio-temporal queries, aimed at reducing unnecessary data movement and computations. Groundhog introduces three key designs for efficient in-storage computing: (i) a self-contained and segment-based storage model, which is lightweight for in-storage computing and enables fine-grained pruning for spatio-temporal queries; (ii) a set of fine-grained techniques to optimize query processing inside storage devices for spatio-temporal queries; and (iii) an in-storage-computing-aware query planner, which offloads spatio-temporal queries in a fine-grained manner using a cost-based approach. We implemented Groundhog on a real hardware board. Extensive experiments conducted on real-world datasets demonstrate that Groundhog achieves significant performance improvements, with latency reductions of up to 81 % for widely used spatio-temporal queries compared to host computing solutions.

Digital Compute-in-Memory (CIM) macros revolutionize the Von Neumann architecture by significantly reducing data movements between CPU and memory. However, when dealing with lightweight CNNs with various convolution types, existing GEMM (general matrix multiplication)-oriented solutions suffer from underutilization and large activation traffic, leading to unsatisfied energy and area efficiencies. In this context, we propose CAMO, in which the key contributions are: (1) A novel convolution mapping mechanism suitable for CIM macros, that maximizes data reuse and reduces activation traffic. (2) A convolution-capable CIM macro, that also supports small-scale GEMM. (3) A CIM-based architecture that supports multiple computing modes. The experimental results show that CAMO achieves up to 31.49× performance speedup and 77.5% activation traffic reduction compared to the baseline architecture.

Large Language Models (LLMs) for multi-turn conversations suffer from inefficiency: semantically similar queries across different user sessions trigger redundant computation and duplicate memory-intensive Key-Value (KV) caches. Existing optimizations such as prefix caching overlook semantic similarities, while typical semantic caches either ignore conversational context or are not integrated with low-level KV cache management. We propose SmartCache, a system-algorithm co-design framework that tackles this inefficiency by exploiting semantic query similarity across sessions. SmartCache leverages a Semantic Forest structure to hierarchically index conversational turns, enabling efficient retrieval and reuse of responses only when both the semantic query and conversational context match. To maintain accuracy during topic shifts, it leverages internal LLM attention scores—computed during standard prefill—to dynamically detect context changes with minimal computational overhead. Importantly, this semantic understanding is co-designed alongside the memory system: a novel two-level mapping enables transparent cross-session KV cache sharing for semantically equivalent states, complemented by a semantics-aware eviction policy that significantly improves memory utilization. This holistic approach significantly reduces redundant computations and optimizes GPU memory utilization. The evaluation demonstrates SmartCache's effectiveness across multiple benchmarks. On the CoQA and SQuAD datasets, SmartCache reduces KV cache memory usage by up to $59.1\%$ compared to prefix caching and $56.0\%$ over semantic caching, while cutting Time-to-First-Token (TTFT) by $78.0\%$ and $71.7\%$, respectively. It improves answer quality metrics, achieving $39.9\%$ higher F1 and $39.1\%$ higher ROUGE-L for Qwen-2.5-1.5B on CoQA. The Semantic-aware Tiered Eviction Policy (STEP) outperforms LRU/LFU by $29.9\%$ in reuse distance under skewed workloads.

Mobile devices have gained immense popularity in recent years and have become an integral part of people’s daily lives. This surge in usage presents new challenges for energy conservation, particularly concerning the screens of mobile phones. Not only are screens being used for longer durations, but also their adjustment needs to be dynamically conducted during runtime. Existing approaches for display energy optimization mainly focus on the display content while disregarding user interactions. This limitation prevents the full exploitation of opportunities to reduce screen energy consumption during runtime. Detection-based display energy optimization approaches incorporate user interactions to some extent. However, these approaches require additional hardware and offer relatively coarse-grained control. To address these challenges, we propose QLEO, a Q-learning-based runtime display energy optimization scheme for Android systems. QLEO takes both the display and user interaction features into account. By dynamically classifying the user state into active and idle states based on these features, we enable adaptive screen brightness adjustments according to the user’s current state. We formulate display energy optimization as a constrained dynamic optimization problem and propose an integrated Q-learning model to effectively solve it. QLEO is designed as a module within the hardware abstraction layer, capable of obtaining display and user interaction features from the upper Android framework, and directly controlling the screen brightness through the underlying Linux kernel. We have implemented QLEO on real hardware and released the source code for public access. The experimental results demonstrate that QLEO achieves significant energy reduction without compromising the user experience.

As performance demands continue to rise, Shared-Memory Heterogeneous Systems (SMHSs) have been widely adopted for their ability to enable efficient communication and data sharing between different heterogeneous cores. However, existing SMHS face challenges in uneven workload distribution among heterogeneous cores and suboptimal mapping schemes, preventing them from fully leveraging their architectural advantages. To address these issues, this paper proposes a mapping-aware framework for modeling SMHSs called MAP-SIM. By performing performance modeling for CPUs and Systolic Arrays (SAs), and considering rational schemes for the partition and mapping of computational tasks, MAP-SIM aims to evaluate and optimize the computational performance of heterogeneous multicore architectures. The experimental results show that compared to previous work, MAP-SIM can increase simulation speed by 14 to 67 times and can also enhance the computational performance of SMHS by 1.4 to 4.4 times.

Modern SSD firmware is continuously optimized for higher parallelism to match the growing frontend PCIe bandwidth with more backend flash channels. Although a multi-core microprocessor is typically adopted to concurrently process independent NVMe requests from multiple NVMe queues, the existing one-to-many thread-request mapping model with each thread serving one or more incoming I/O requests has poor scalability due to severe lock contention problem, especially in cache management.

With the development of quantum computing, quantum processor demonstrates the potential supremacy in specific applications, such as Grover's database search and popular quantum neural networks (QNNs). For better calibrating the quantum algorithms and machines, quantum circuit simulation on classical computers becomes crucial. However, as the number of quantum bits (qubits) increases, the memory requirement grows exponentially. In order to reduce memory usage and accelerate simulation, we propose a multi-level optimization, namely Mera, by exploring memory and computation redundancy. First, for a large number of sparse quantum gates, we propose two compressed structures for low-level full-state simulation. The corresponding gate operations are designed for practical implementations, which are relieved from the longtime compression and decompression. Second, for the dense Hadamard gate, which is definitely used to construct the superposition, we design a customized structure for significant memory saving as a regularity-oriented simulation. Meanwhile, an ondemand amplitude updating process is optimized for execution acceleration. Experiments show that our compressed structures increase the number of qubits from 17 to 35, and achieve up to$6.9 \times$acceleration for QNN.

Massive trajectory data are continuously generated with the rapid development of location-acquisition devices such as vehicles and smartphones. To provide services for applications such as mobility pattern discovery, how to manage such gigantic trajectory data to support queries in an efficient and cost-effective way becomes vitally important. Due to its low cost, large storage capacity, and reliability, cloud storage such as S3 becomes a new paradigm for storing gigantic data and is used in some general-purpose data management systems to strike a balance between performance and monetary costs. However, few systems exploit the inherent features of cloud storage for trajectory data. In this paper, we propose a novel cloud-based trajectory data management technique, called Springbok, to bridge the gap between massive trajectory data and cloud storage. Springbok is designed to address several key issues related to cloud-based trajectory data management. First, Springbok treats trajectories as first-class citizens using a new spatio-temporal series data model that can benefit insertion, query processing, and storage management in the cloud. Second, a holistic indexing scheme that considers features of trajectory data and cloud storage is designed to facilitate efficient queries. Third, based on performance features and billing models of cloud storage, we design effective data layouts for trajectory data and corresponding data flushing and access policies in a tiered cloud storage architecture for performance improvement and cost reduction. We have implemented a fully functional prototype of Springbok and conducted evaluations using both real-world and synthetic datasets, demonstrating its ability to achieve a good tradeoff between performance and monetary costs. Springbok has been open-sourced for public access.

For enterprise storage systems, users' directory/file and IO access traces are critical for fine-tuning and new designs. However, once these systems are deployed, only trace features with small sizes are allowed to be sent back to vendors. Therefore, it is crucial to develop effective techniques for highly compressed feature extraction and feature-based high-fidelity trace regeneration. Existing works primarily focus on I/O trace modeling and regeneration without considering the directory/file access information. In this paper, we propose a new technique, called Sketcher, that can sketch massive traces into highly compressed “joint features” with both directory/file and I/O characteristics, and then based on these features regenerate high-fidelity traces with a learning-based approach. For trace feature extraction, one key idea is to divide traces into multiple distance-associated segments, where each segment contains all files and IO accesses operating under the same directory and the differences between segments are represented as displacement of segment inside the directory tree. A dynamic weight scaling technique is proposed to further compress features considering feature criticality and the size quota, thereby achieving high compression ratios with critical characteristics (e.g., abnormal IO access patterns). For trace regeneration, a new learning-based RNN model is proposed to regenerate high-fidelity traces from extracted features based on sampling directory trees. We have implemented a fully functional prototype based on typical enterprise storage systems and evaluated Sketcher with real applications and benchmarks on Huawei OceanStor Dorado storage server. Results show that Sketcher can effectively extract features with marginal runtime overheads while achieving compression ratios up to 15.2K and regenerating high-fidelity traces.

The continuously increasing volume of blockchain data presents significant challenges to blockchain traceability. Current tracing approaches, which rely on heuristic analytics directly applied to blockchain data, exhibit degraded tracking accuracy due to the involvement of only partial data. On the other hand, incorporating all blockchain data for analytics is not scalable given the unprecedented data volumes. Interestingly, we observe that despite the vast amount of blockchain data, blockchain tracing primarily focuses on time-related transaction spaces rather than all transactions. This insight motivates us to rethink the blockchain tracing problem to achieve both accuracy and scalability.

When trained Large Language Models (LLMs) become available, it is desirable to carry out LLM inferences at the user end with limited resources. A common belief on LLM inference is that GPU is essentially the only meaningful processor as almost all computation is tensor multiplication that GPU excels in. However, this belief and its practice are challenged by the fact that GPU has insufficient memory and runs at a much slower speed due to constantly waiting for data to be loaded from the CPU memory via a slow PCIe bus. This makes the CPU a processor with meaningful computing power that can be leveraged to accelerate the inference.

Winternitz one-time signature (WOTS) is a quantum-resistant signature mechanism that has been widely used in direct acyclic graph (DAG)-based blockchain systems. However, it needs to generate a unique private/public key pair for each transaction, which severely limits blockchain performance by performing a time-consuming unique address checking process when generating transactions. This article proposes a bloom-filter-based approach, called ABACUS, to optimize the unique address checking process in WOTS. In ABACUS, we separate the large address space into multiple small subspaces and apply bloom filters to perform uniqueness checking for all addresses in one subspace. Specifically, we propose a two-level address space mechanism to strike a balance between the checking efficiency and the memory/storage space overhead of the bloom filter design. A bucket-based scalable bloom filter (SBF) design is proposed to match the growth of used addresses with efficient I/O access by storing all sub-bloom-filters together in one bucket. To further reduce disk I/Os, ABACUS incorporates an in-memory write buffer and a read-only cache. To reclaim wasted addresses, we also propose a layered address recycling mechanism by efficiently checking and reusing unused addresses that were identified as used due to false positives of bloom filters. We have implemented a fully functional prototype of ABACUS and integrated it into IOTA, a widely used DAG-based blockchain system. A series of experiments have been conducted on a private IOTA system. Experimental results show that ABACUS can significantly reduce the transaction generation time by up to four orders of magnitude, and achieve up to$3\times $boost on the system throughput with more than 80% space-saving. We have released the open-source code of ABACUS for public access.

Embedded machine learning applications face challenges related to massive data movement and high computational intensity, exacerbated by the limited performance of mobile devices. Computational storage devices (CSDs) pose huge potential for accelerating both data-intensive and computation-intensive embedded machine learning tasks by effectively reducing data movement and leveraging built-in accelerators. However, existing in-storage-computing (ISC) frameworks either require invasive customization of existing host driver layers or necessitate complex device firmware modifications, hindering the widespread deployment of CSDs. In addition, the lack of file semantics and the constrained internal resources within CSD implicitly compromise system performance and impact normal read/write performance. In this article, we aim to provide a nonintrusive in-storage-computing framework for embedded applications, named NICE. This framework includes an easy-to-use ISC programming interface that bypasses the kernel stack and requires no modification to the host NVMe driver, which is achieved through a novel hyper-addressing-based programming library and a file-aware page data layout within the CSD. In addition, we incorporate a lightweight kernel with coroutine-based command scheduling and several FPGA-based accelerators within the storage device firmware to enhance the performance of embedded machine learning applications while ensuring that the normal I/O performance remains unaffected. NICE is implemented on real CSD hardware integrated with ARM and FPGA. Experimental results demonstrate that our NICE framework can achieve an average latency performance improvement of$43.5\times $($9.32\times $) compared to CPU-(GPU-) based embedded machine learning solutions using the state-of-the-art NVIDIA Jetson NX platform, with$27.5\times $($4.3\times $) higher energy efficiency. NICE also has$34.2\times $less software and I/O performance overheads than state-of-the-art ISC frameworks.

Blockchain systems play an important role in distributed ledgers, database systems, etc. As more and more blocks are mined, the storage burden of blockchain system is significantly increased. The current blockchain system uniformly transforms all its data into key-value (KV) items and stores them to the underlying Log-Structure Merged tree (LSM-tree) storage engine ignoring the software semantics. Consequently, it not only aggravates the write amplification effect of the storage engine, but also increases the redundancy of data query steps, resulting in the performance bottleneck of blockchain system. In this paper, we propose a semantic-integrated LSM-tree based Key-Value storage engine for blockchain systems, called Block-LSM, which significantly improves the data synchronization and data query efficiency of blockchain system. Specifically, we first design a shared prefix scheme to transform blockchain data into ordered KV pairs to alleviate the key range overlaps of different levels in the underlying LSM-tree based storage engine. Moreover, we propose to maintain several semantic-orientated memory buffers to isolate different kinds of blockchain data, and implement memory buffer space management strategy to further improve memory efficiency. To save space overhead, Block-LSM further aggregates multiple blocks into a group and assigns the same prefix to all KV items from the same block group. We also reduce step redundancy in transaction queries by modifying the body data storage format. Finally, we implement Block-LSM in a real blockchain environment and conduct a series of comparative experiments with the typical blockchain system Ethereum. The evaluation results show that Block-LSM significantly reduces up to 7.56× storage write amplification and increases throughput by 8.64× compared with the original Ethereum design. In terms of data lookups (i.e. transaction and account lookup), Block-LSM improves the throughput by 50% compared to the original Ethereum design.

Mobile devices often face runtime configuration changes, such as screen orientation changes, screen resizing, and language switching. The current Android design adopts a restarting-based solution to load the corresponding resources according to the new configuration. Therefore, application developers must explicitly deal with state preservation and restoration brought about by the activity restarting. Otherwise, the runtime change will cause state loss and even app crash issues. To solve the runtime change handling issues, we propose RCHDroid, a transparent runtime change handling approach for apps at the Android system level. When a configuration change occurs, we do not restart the activity, but instead, create a new activity according to the new configuration and migrate states from the old one to the new one, while putting the old activity into an inactive mode. We propose a lazy-migration scheme to handle asynchronous tasks that remain working on the old activity, which migrates the result events when the asynchronous tasks return. We have implemented a prototype of RCHDroid with real hardware and released the source code for public access. Overall, using RCHDroid, existing apps can handle runtime configuration changes without any modifications and save the runtime change handling time by 25.46%.

The Deep Learning Processor (DPU) programmable engine released by the official Xilinx Vitis AI toolchain has become one of the commercial off-the-shelf (COTS) solutions for Convolutional Neural Networks (CNNs) inference on Xilinx FPGAs. While modern FPGA devices generally have enough hardware resources to accommodate multi-DPUs simultaneously, the Xilinx toolchain currently only supports the deployment of multiple homogeneous DPUs engines that running independent inference tasks (task-level parallelism). In this work, we demonstrate that deployment of multiple heterogeneous DPU engines makes better resource efficiency for a given FPGA device. Moreover, we show that pipelined execution of a CNN inference task over heterogeneous multi-DPU engines may further improve overall inference throughput with carefully designed CNN layers-to-DPU mapping and scheduling. Finally, for a given CNN model and an FPGA device, we propose a comprehensive framework that automatically determines the optimal heterogeneous DPU deployment, and adaptively chooses the execution scheme between task-level and pipelined parallelism. Compared with the state-of-the-art solution with homogeneous multi-DPU engines and network-level parallelism, the proposed framework shows an average improvement of 13% (up-to 19%) and 6.6% (up-to 10%) on the Xilinx Zynq UltraScale+ MPSoC ZCU104 and ZCU102 platforms, respectively.

In-storage computing with computational SSDs is emerging as one effective solution for I/O bottlenecks in big data applications such as AI learning model training. Specifically, with in-SSD computing, computation can be pushed down to SSDs and the volume of the output data that will be transferred back to the host can be greatly reduced. However, there are several fundamental issues for applications to fully exploit in-SSD computing with simple and efficient function offloading. In this paper, we present three challenges for in-SSD computing, namely, data model, programming framework, and storage/computing integration, and discuss possible research directions.

Recently, solid-state drives (SSDs) have been used in a wide range of emerging data processing systems. Essentially, an SSD is a complex embedded system that involves both hardware and software design. For the latter, firmware modules such as the flash translation layer (FTL) orchestrate internal operations and flash management, and are crucial to the overall input/output performance of an SSD. Despite the rapid development of new SSD features in the market, the research of flash firmware has been mostly based on simulations due to the lack of a realistic and extensible SSD development platform. In this paper, we propose SoftSSD, a software-oriented SSD development platform for rapid flash firmware prototyping. The core of SoftSSD is a novel framework with an event-driven programming model. With the programming model, new FTL algorithms can be implemented and integrated into a full-featured flash firmware in a straightforward way. The resulting flash firmware can be deployed and evaluated on a hardware development board, which can be connected to a host system via peripheral component interconnect express and serve as a normal non-volatile memory express SSD. Different from existing hardware-oriented development platforms, SoftSSD implements the majority of SSD components (e.g., host interface controller) in software, so that data flows and internal states that were once confined in the hardware can now be examined with a software debugger, providing the observability and extensibility that are critical to the rapid prototyping and research of flash firmware. We describe the programming model and hardware design of SoftSSD. We also perform experiments with real application workloads on a prototype board to demonstrate the performance and usefulness of SoftSSD, and release the open-source code of SoftSSD for public access.

存储系统是计算机的核心,在人工智能、大数据、云计算和物联网等新兴战略产业的可持续发展中起着重要作用。随着处理器和网络设备性能不断提高,存储软件栈成为限制数据密集型系统性能的主要因素。近年来,新型存储设备因其打破“内存墙”的能力而受到广泛关注。这些设备包括支持块寻址的闪存设备、支持字节寻址的非易失性存储器、存算一体化设备以及大容量光存储。构建高吞量、低延迟和高可靠性的大规模存储系统,需要对算法、软件设计和硬件的持续创新。这些创新可以应对大规模、高性能复杂结构系统构建中存在的挑战,还可以增加相关系统的构建和应用经验,加快大数据处理系统的开发速度。 研究人员一直致力于解决“内存墙”问题,并改进相关软硬件生态系统,从而在新型存储系统设计和应用方面取得很大进展,包括但不限于以下方面:

The Log-Structure Merged tree (LSM-tree) based key-value (KV) store has been widely adopted as the storage engine for blockchain systems, such as Ethereum, in which blockchain data are uniformly transformed into randomly distributed KV items for persistence. However, blockchain semantics are ignored during this process, making the blockchain storage suffer from heavy read/write amplification problems. Moreover, as the Ethereum network scales up, tremendous data further exacerbates its storage burden. Until now, most studies have focused on sharding, data archiving, decentralized distributed storage, etc., to mitigate the burden of the storage layer. However, the incompatibility between Ethereum semantics and the characteristics of the storage engine is ignored. In this paper, we present ChainKV, a new semantics-aware storage paradigm to improve the storage management performance for the Ethereum system. Firstly, based on Ethereum blockchain semantics, ChainKV separately stores different types of data in multiple storage zones in the KV store to mitigate the read/write amplification problem. Secondly, following the mechanism of the verification process in the authenticated data structure (ADS), a new ADS data transformer is proposed to exploit the data locality when persisting ADS. Moreover, a new space gaming caching policy is adopted to coordinate the cache space management for two independent storage zones. Finally, we propose an optional lightweight node crash recovery mechanism to eliminate functional redundancy between the Ethereum protocol and the storage engine. The experimental results indicate that ChainKV outperforms the prior Ethereum systems by up to 1.99× and 4.20× for synchronization and query operations, respectively

Timeseries management systems play an important role in IoT and performance monitoring. As the data volume scales up, absorbing data memory efficiently with high throughput becomes a growing requirement for timeseries management systems. However, the designs of the existing systems, especially the in-memory data structures, suffer from two issues. First, they suffer from the trade-off between memory efficiency and performance. Second, they are not scalable because of lock contention where they cannot benefit from parallel insertion and querying. In this paper, we propose ForestTI, a scalable inverted-index-oriented timeseries management system where the balance point between memory efficiency and performance can be flexibly adjusted under the increasing memory pressure. First, we present a two-level inverted index, which is scalable with optimistic lock coupling, and its internal structure can be gradually converted to more memory efficient representations. Second, we propose a two-level pointer swizzling mechanism to actively swap out the cold posting lists and in-memory timeseries objects as the number of timeseries increases. Finally, we further optimize the on-disk data structures (i.e. write-ahead logs and LSM-tree) to adapt to the high insertion throughput from the in-memory components. We prototype ForestTI with C++ from scratch, and compared to the storage engine of Prometheus, ForestTI achieves 1.79x higher insertion throughput, 52.1% lower query latency, and 56.9% lower memory occupation. We have released the open-source code of ForestTI for public access.

LSM-based key-value stores have been leveraged in many state-of-the-art data-intensive applications as storage engines. As data volume scales up, a cost-efficient approach is to deploy these applications on hybrid cloud storage with hot/cold separation, which splits the LSM-tree into two parts and thus brings new challenges on how to split and how to close the significant performance gap between these two parts. Existing LSM-tree key-value stores mainly focus on the optimizations of local storage, which incurs sub-optimal performance when directly applied to hybrid storage. In this paper, we present MirrorKV for efficient compaction and querying on hybrid cloud storage. First, based on the capacities of fast and slow cloud storage, MirrorKV vertically separates hot/cold data of different levels stored in different cloud storage with different compaction mechanisms. To avoid compaction in slow storage being the bottleneck of the write path, MirrorKV proposes a novel virtual split to only compact the metadata during the compaction, which postpones the actual compaction until it reaches deep enough levels. Second, to reduce accessing slow storage during querying, MirrorKV horizontally separates keys and values into two mirrored LSM-trees to differentiate caching priorities; the maintained tree structures preserve the data locality for efficient sequential reading without incurring the overhead of the traditional key-value separation solutions. Finally, MirrorKV leverages cached data to guide the compaction where the hot data is retained in the fast storage while the cold data is compacted to deeper levels in slow storage. Compared with RocksDB-cloud, MirrorKV achieves 2.4× higher random insertion throughput, 29% higher random read throughput, and 99% less compaction time.

Multidisplay Android systems are emerging and require new display management. The current Android design exposes and offloads the multiscreen display management to app developers. As a consequence, apps cannot utilize multiscreen without redevelopment. This article proposes MSA, a novel Android app development framework for transparent multiscreen support. MSA cooperates with existing Android system services to map the single-screen views provided by apps to multiple screens and maps input events backward correspondingly. Following the new framework, the app development of single-screen Android systems and multiscreen Android systems are unified. Thus, both existing apps and future app development can directly utilize multiple screens with single-screen-based techniques, such as multiwindow and resizable-activity, instead of redevelopment through multiscreen-dedicated new methods such as presentation classes. We have implemented an MSA prototype with real hardware and released the source code for public access. Experimental results show that using MSA, without any modifications, existing apps can directly run and fully exploit multiple screens with better performance and less overhead compared with the state-of-the-art multiscreen Android system.

To support nonsequential writes, persistent cache (PC) is constructed in drive managed SMR (DM-SMR) drive. However, PC cleaning introduces drastic performance degradation and enlarges tail latencies. In this article, we propose to utilize reinforcement learning (RL) to mitigate the long-tail latency of PC cleaning. Our scheme uses the lightweight$Q$-learning method to monitor and learn the idle time of I/O workloads, based on which PC cleaning is intelligently guided, thus maximally exploit idle time between requests and hiding tail latency from normal requests. In addition, a multiagent RL scheme with clustering algorithm is adopted to further mitigate the tail latencies and adapt to variable workloads. We emulate a DM-SMR drive inside a Linux device driver to implement our proposed scheme. According to the experimental results, our scheme can effectively reduce the tail latency by 59.45% at the 99.9th percentile and the average latency by 48.75% compared with a typical shingled magnetic recording (SMR) design.

Solid-state drives (SSDs) have been used in a wide range of emerging data processing systems. To fully utilize the massive internal parallelism delivered by SSDs, manufacturers begin to utilize high-performance multi-core microprocessors in scalable flash firmware to process I/O requests concurrently. Designing scalable multi-core flash firmwares requires simulation tools that can model the features of a multi-core environment. However, existing SSD simulators assume a single-threading execution model and are not capable of modelling overheads incurred by multi-threading firmware execution such as lock contentions. In this paper, we propose MCMQ, a novel framework for simulating scalable multi-core flash firmware. The framework is based on an emulated multi-core RISC processor and supports executing multiple I/O traces in parallel through a multi-queue interface. Experiment results show the effectiveness of the proposed framework. We have released the open-source code of MCMQ for public access.

The lightweight AI models are proposed for embedded devices to mitigate computation and memory requirements. However, it still faces the memory wall problem (i.e., data movement between computing units and memory). Many processing-in-memory (PIM) based accelerators have been proposed to conquer this problem. Whereas, in practical deployment, there are still many challenges that need to be addressed.In this paper, we propose an embedded GPU-PIM integrated framework, with a fabricated HBM-PIM device from Samsung, to accelerate lightweight CNN inference. Considering various characteristics of different layers in lightweight CNNs, we first propose a fine-grained roofline model to guide the layer offloading to PIM cores. To fully utilize the computation and bandwidth resources of both GPU and PIM, we model the task allocation into a multi-dimensional knapsack problem (MDKP), which is addressed by a dynamic programming algorithm. Meanwhile, considering some practical issues such as PIM mode switch and memory address interleaving during the offloading, we further introduce a PIM-aware memory layout optimization strategy to reduce unnecessary inter-channel memory accesses and PIM mode switches. Experiment results show that our proposed framework achieves averagely the 5.9X and 37.9% inference performance boosts compared to the original GPU-only approach and the GPU-HBM approach, respectively.

Recently, solid-state drives (SSDs) have been used in a wide range of emerging data processing systems. Essentially, an SSD is a complex embedded system that involves both hardware and software design. For the latter, firmware modules such as the flash translation layer (FTL) orchestrate internal operations and flash management, and are crucial to the overall I/O performance of an SSD. Despite the rapid development of new features of SSDs in the market, the research of flash firmware has been mostly simulation-based due to the lack of a realistic and extensible SSD development platform. In this paper, we propose SoftSSD, a software-defined SSD development platform for rapid flash firmware prototyping. The core of SoftSSD is a novel framework with an event-driven programming model. With the programming model, new FTL algorithms can be implemented and integrated into a full-featured flash firmware in a straightforward way. The resulting flash firmware can be deployed and evaluated on a hardware development board, which can be connected to a host system via PCIe and serve as a normal NVMe SSD. Different from existing hardware-oriented development platforms, SoftSSD implements the majority of SSD components (e.g., host interface controller) in software so that data flows and internal states that were once confined in the hardware can now be examined with a software debugger, providing the observability and the extensibility that are critical to the rapid prototyping and research of flash firmware. This paper describes the programming model and hardware design of SoftSSD. We also perform experiments with real application workloads on a prototype board to demonstrate the performance and usefulness of SoftSSD and released the open-source code of SoftSSD for public access.

Spatio-temporal data are generated continuously and becomes gigantic with the rapid growth of mobile devices and applications. How to store and index spatio-temporal big data is crucial to support efficient queries for effective data management and analytics. With their high write throughput and good scalability, distributed NoSQL data stores such as HBase are widely adopted as storage engines in spatio-temporal big data systems, in which a key-value-based storage model is required so one or a group of spatio-temporal data points can be converted into one key-value pair. However, existing techniques cannot govern an inherent dilemma caused by adding time dimension within spatial information, that is, we can either optimize for space-preferred or time-preferred queries but not both.In this paper, we propose a novel storage model with query-aware indexing, called Cymo, that can adapt different query patterns. Our basic idea is to divide the spatio-temporal space into multiple subspaces so each subspace can effectively exploit its query characteristics to obtain the best storage model. Specifically, Cymo includes a learning model that can predict query patterns for each subspace based on historical workloads. Also, in Cymo, a virtual layer is proposed to hide the heterogeneity of different storage models with a unified query interface, by which different storage models can be hidden and transparent from applications while different query patterns can be effectively exploited in query optimization. We have implemented Cymo based on HBase and further integrated it into GeoMesa, a representative spatio-temporal big data system. Experimental results based on real taxi datasets show that Cymo improves query latencies significantly (1.53× to 10×) compared with GeoMesa. We have released the open source code of Cymo for public access.

Cloud-based performance monitoring timeseries systems are emerging due to cloud’s flexibility and pay-as-you-go capabilities. For such systems, caching is particularly important considering the limited bandwidth and long access latency of the cloud storage. However, existing cache schemes, such as with external cache systems (e.g. Memcached or Redis), are not specially designed for timeseries data and thus provide suboptimal performance.

Modern time series databases come with a tag-based query interface that allows users to select time series, which are essentially sequences of timestamped data values, based on a set of specific tags. A tagging index is an important component that can efficiently provide such tag-based services. However, existing methods store tag information in external databases or time-partitioned data structures, which has a negative impact on query performance. In this paper, we present a novel abstraction for efficient queries of tag information in time series databases: a hybrid tagging index that manages all tags in one place. By managing tag information globally in a single disk-based data structure, we can fundamentally relieve memory pressure and eliminate I/O overhead of duplicate metadata from existing methods. Furthermore, the tagging index is internally partitioned by time to support time range based queries and data retention which are essential to time series databases. We implement the proposed tagging index as a standalone module which can be integrated with time series storage engines. Experiments on the TSBS benchmark show our proposed method can significantly speed up queries by on average 84.0% and 87.2% compared to Prometheus (using a time-partitioned segment method) and Graphite (using an external database for tag management), respectively.

Dual-screen foldable Android smartphones such as Microsoft Surface Duo are emerging. However, due to its internal design, the Android framework cannot support combined mode, by which two screens can be integrated into one, without modifications, thus requiring new display management. Android introduces a new dual-screen display method, called presentation class, to handle this problem; however, existing apps need to be redesigned based on the new class. In this paper, we propose Dual-Screen Android (DSA), a semantics-aware display scheme for dual-screen foldable Android smartphones. DSA is transparent to apps, thus requiring no changes for existing apps, and incurs minimum modification to the Android framework. Specifically, inside Android, DSA duplicates and maps single-screen views provided by apps to dual screens and maps input events backward correspondingly, thus being transparent to apps. DSA also opens the door to store other hardware states (e.g., screen brightness, screen-touch events, etc.), which can be utilized to bridge other software/hardware semantic gaps for further system optimization. To demonstrate this, we design an effective Q-learning energy optimization scheme within DSA to control screen brightness based on predicted users' behaviors. We have implemented DSA based on Android 10 with real hardware and conducted a series of experiments. Experimental results show that based on DSA, without any modifications, existing apps can directly run and fully exploit dual screens with negligible time and memory overheads, and our energy optimization scheme can effectively reduce energy. We have released the open-source code of DSA for public access.

Recently, HBM (High Bandwidth Memory) and PIM (Processing in Memory) integrated technology such as Samsung function-in-memory DRAM opens a new door for memory-intensive PoW acceleration by jointly exploiting GPU, PIM and HBM. In this paper, we for the first time propose a GPU/PIM Co-Mining framework to accelerate memory intensive PoW by fully exploiting HBM-PIM's bandwidth and coordinately scheduling mining tasks in both GPU and PIM. Specifically, we first design a linear programming model to intelligently guide the GPU/PIM task scheduling. An extended finite-state-machine model is designed for the GPU memory controller to switch PIM working mode (compute/memory mode) accordingly. Finally, considering the speed difference between intra-/inter-channel memory accesses, a hybrid memory access method is proposed to minimize inter-channel data movements. We evaluate Co-Mining based on Samsung's HBM2-based function-in-memory architecture. The experimental results show that it can achieve up to 38.5% hashrate improvement compared with the method by directly integrating PIM into PoW acceleration with GPU.

Key-value databases are widely used to store the features or metadata generated from the neural network based video processing platforms. Due to the large volumes of video data, these databases use solid state drives (SSDs) as the primary data storage platform, and user query-based filtering, and retrieval operations on data incur large volume of data movement between the SSD and the host processor. In this paper, we present an in-SSD key-value database which uses the embedded CPU core, and DRAM memory on the SSD to support various queries with predicates and reduce the data movement between SSD and host processor significantly. We augment the SSD flash translation layer with key-value database functions and auxiliary data structures to support the user queries using the embedded core and DRAM memory on SSD. The proposed key-value store prototype on the Cosmos plus OpenSSD board reduces data movement between host processor and SSD by 14.57x, achieves an application-level speedup by 1.16x, and reduced energy consumption by 56% across different types of user queries.

Timeseries management systems have attracted considerable attention during the last decade with the rise of IoT and performance monitoring. With the rapidly increasing data scale in the production environment, deploying timeseries management systems on cloud with cloud storage is a natural trend because of its high availability, reliability, and scalability. However, the state-of-the-art designs are not tailored for cloud environments; they suffer from the limited number of timeseries a single compute node can handle because of the imbalanced resource usage.

Blockchain is starting to be deployed in the Internet of Things (IoT) to enable autonomous device-to-device transactions. However, traditional block-based blockchain techniques, such as Bitcoin and Ethereum, are not suitable for IoT environments due to their low throughput, high computation overhead, and costly transaction fee. To satisfy the requirements of IoT environments, directed-acyclic-graph (DAG)-based approaches, aiming to provide cheap blockchain services with low latency and high throughput, are emerging. This article presents a set of comprehensive experimental studies on IOTA, a representative DAG-based blockchain. We aim to exhibit its unique characteristics mainly from three aspects: 1) performance; 2) security; and 3) system robustness. We have developed a series of benchmark tools and judiciously selected typical configurations to perform experimental examinations with a real private IOTA network. Our studies reveal several interesting findings: 1) the throughput of IOTA is higher than the traditional block-based blockchain but far less than the reported thousands of transactions per second (TPS) in its whitepaper, even with scaling-up configurations; 2) the database query heavily impacts the performance of IOTA, even more than its mining [i.e., Proof of Work (PoW)] process; and 3) the system robustness of IOTA is closely related to the frequency of the incoming transactions while the milestone sent by the centralized coordinator has little effect on the system robustness. We make our benchmark tools public and expect our works can inspire system architects, application designers, and practitioners with new optimization directions and potential application cases for further exploration.

Emerging applications like machine learning in embedded devices (e.g., satellites and vehicles) require huge storage space, which recently stimulates the widespread deployment of large-scale flash memory in IoT devices. However, existing embedded file systems fall short in managing large-capacity storage efficiently for two reasons. First, prior arts store data structures of file systems either in flash or in main memory, which severely magnifies the scarcity of computing and memory resources. Moreover, the fine-grained metadata management in the existing embedded file systems induces significant energy consumption for large-capacity storage. In this paper, we propose a novel embedded file system, ELOFS, to tackle the above issues and manage large-capacity NAND flash on resource-scarce devices. ELOFS is made efficient through three novel techniques. First, we redefine the space management granularity and streamline the metadata to speed up the mounting performance. In addition, we design hybrid file structures to adapt dissimilar access patterns of embedded devices. Furthermore, ELOFS provides opportunities for in-depth cooperation with application-specific systems. We implement ELOFS with Memory Technology Device (MTD) interfaces, and the experimental results show that ELOFS outperforms YAFFS and UBIFS in terms of write, read, and deletions with orders of magnitude reductions on memory footprint and mounting time.

The lifetime of NAND flash cells significantly degrades with feature-size reductions and multilevel cell technology. On the other hand, we have more and more approximate data, such as images and videos that are more error tolerant than regular data like text. In this article, we propose Rebirth-FTL, which reuses faulty blocks that contain uncorrectable errors to store approximate data for lifetime optimization. Rebirth-FTL effectively manages two spaces, namely, the approximate space and the normal space, with an efficient address translator, a coordinated garbage collection, and a differential wear leveler. In addition, we develop an migration times restriction (MTR) policy to restrict the movement of the approximate data in the approximate space. We also develop a scheme to pass approximate information from userland to kernel space in Linux. Finally, a lifetime model is presented for lifetime analysis. Our experimental results show that Rebirth-FTL can extend the lifetime by 41.63% on average.

The rapid adoption of solid-state drives (SSDs) as a major storage component has been made possible, thanks to their ability to export a standard block I/O interface to the file system and application developers. Meanwhile, this high-level abstraction has been shown to limit the utilization of the devices and the performance of applications running on top of them. Indeed, many optimizations of performance-critical applications bypass the standard block interface and rely on low-level control over SSD internal processes. However, the need to directly manage the physical device significantly increases development complexity and cost, and reduces its portability. Thus, application developers must choose between two extreme options, eithereasy developmentoroptimal performance, without a real possibility to balance between these two objectives. To bridge this gap, we propose aflexible storage interfacethat exports the SSD hardware in three levels of abstraction: 1) as a raw flash media with its low-level details; 2) as a group of functions to manage flash capacity; or 3) as a configurable block device. This multilevel abstraction allows developers to choose the degree in which they desire to control the flash hardware in a manner that best suits the applications’ semantics and performance objectives. We demonstrate the usability of this new model withPrism-SSD—a prototype of this interface as a user-level library on the Open-Channel SSD platform. We use each of the interface’s three abstraction levels to modify the I/O module of three representative applications: 1) a key-value cache system; 2) a user-level file system; and 3) a graph processing engine. Prism-SSD improves application performance by 5%–27%, at varying development costs, between 200 and 3500 lines of code.

Resistive random access memory (ReRAM)-based processing-in-memory (PIM) architecture has been designed to accelerate deep neural networks (DNNs) by concurring computation and memory barriers. To further improve memory and computation efficiency, the weight sparsity characteristic has been explored to optimize the ReRAM-based DNN accelerators. However, these designs only focus on compressing zero weights to eliminate ineffectual computation. In this article, we thoroughly analyze the weight distribution characteristics of several typical DNN models and observe many nonzero weight pattern repetitions (WPRs). Therefore, there is an opportunity to further improve the performance and energy efficiency by reusing these WPR. We propose a novel ReRAM-based accelerator—PattPIM, to achieve space compression and computation reuse by exploring DNN WPR based on practical ReRAM crossbars. In PattPIM, we propose a configurable WPR-aware DNN engine and a WPR-to-OU mapping scheme to save both space and computation resources. An intraprocessing engine (PE) pipeline is designed to improve the parallelism of the computation process. Furthermore, we adopt an approximate weight pattern transform algorithm to improve the DNN WPR ratio to enhance the reuse efficiency with negligible accuracy loss. Our evaluation with 6 DNN models shows that the proposed PattPIM delivers significant performance improvement, ReRAM resource efficiency and energy saving.

Blockchain has been widely deployed in various fields, such as finance, education, and public services. Blockchain has decentralized mechanisms with persistency and auditability and runs as an immutable distributed ledger, where transactions are jointly performed through cryptocurrency-based consensus algorithms by worldwide distributed nodes. There have been many survey papers reviewing the blockchain technologies from different perspectives, e.g., digital currencies, consensus algorithms, and smart contracts. However, none of them have focused on the blockchain data management systems. To fill in this gap, we have conducted a comprehensive survey on the data management systems, based on three typical types of blockchain, i.e., standard blockchain, hybrid blockchain, and DAG ( Directed Acyclic Graph )-based blockchain. We categorize their data management mechanisms into three layers: blockchain architecture, blockchain data structure, and blockchain storage engine, where block architecture indicates how to record transactions on a distributed ledger, blockchain data structure refers to the internal structure of each block, and blockchain storage engine specifies the storage form of data on the blockchain system. For each layer, the works advancing the state-of-the-art are discussed together with technical challenges. Furthermore, we lay out several possible future research directions for the blockchain data management systems.

SQLite with JSON (JavaScript Object Notation) format is widely adopted for local data storage in mobile applications such as Twitter and Instagram. With more data are generated and stored, it becomes vitally important to efficiently index and search JSON records in SQLite. However, current methods in SQLite either require full text search (that incurs big memory usage and long query latency) or indexing based on expression (that needs to be manually created by specifying search keys). On the other hand, existing JSON automatic indexing techniques, mainly focusing on big data and cloud environments, depend on a colossal tree structure that cannot be applied in memory-constrained mobile devices.

DM-SMR adopts Persistent Cache (PC) to accommodate non-sequential write operations. However, the PC cleaning process induces severe long-tail latency. In this paper, we propose to mitigate the tail latency of PC cleaning by using Reinforcement Learning (RL). Specifically, a real-time lightweight Q-learning model is built to analyze the idle window of I/O workloads, based on which PC cleaning is judiciously scheduled, thereby maximally utilizing the I/O idle window and effectively hiding the tail latency from regular requests. We implement our technique inside a Linux device driver with an emulated SMR drive. Experimental results show that our technique can reduce the tail latency by 57.65% at 99.9th percentile and the average response time by 46.11% compared to a typical SMR design.

Ethereum as one of the largest blockchain systems plays an important role in the distributed ledger, database systems, etc. As more and more blocks are mined, the storage burden of Ethereum is significantly increased. The current Ethereum system uniformly transforms all its data into key-value (KV) items and stores them to the underlying Log-Structure Merged tree (LSM-tree) storage engine ignoring the software semantics. Consequently, it not only exacerbates the write amplification effect of the storage engine but also hurts the performance of Ethereum. In this paper, we proposed a new Ethereum-aware storage model called Block-LSM, which significantly improves the data synchronization of the Ethereum system. Specifically, we first design a shared prefix scheme to transform Ethereum data into ordered KV pairs to alleviate the key range overlaps of different levels in the underlying LSM-tree based storage engine. Moreover, we propose to maintain several semantic-orientated memory buffers to isolate different kinds of Ethereum data. To save space overhead, Block-LSM further aggregates multiple blocks into a group and assigns the same prefix to all KV items from the same block group. Finally, we implement Block-LSM in the real Ethereum environment and conduct a series of experiments. The evaluation results show that Block-LSM significantly reduces up to 3.7× storage write amplification and increases throughput by 3× compared with the original Ethereum design.

In recent years, Log-Structured Merge Tree (LSMtree) based key-value stores, such as LevelDB and RocksDB, have been widely adopted in data center systems. Though optimized for high-speed write processing, the severe I/O amplification remains a critical constraint that hinders them from reaching their maximum performance potential. Unfortunately, this problem is deeply rooted in the fundamental design of the LSMtree structure. A small number of frequently updated key-value items could quickly pollute the entire tree structure, causing repeated changes in the structure and quickly amplifying the amount of disk IOs across the levels in the tree. In this paper, we present a novel scheme, called Log-assisted LSM-tree (L2SM), to fundamentally address the long-existing I/O amplification problem. L2SM adopts a small-size, multi-level log structure to isolate selected key-value items that have a disruptive effect on the tree structure, accumulates and absorbs the repeated updates in a highly efficient manner, and removes obsolete and deleted key-value items at an early stage. We have prototyped the L2SM structure based on LevelDB. Our evaluation with the YCSB benchmark shows promising results by reducing the amount of disk IOs by up to 40.2%, increasing the throughput by up to 67.4%, and decreasing the average latency by up to 40.1%.

Similarity computation is a core subroutine of many mining tasks on multi-dimensional data, which are often massive datasets at high dimensionality. In these mining tasks, the performance bottleneck is caused by the `memorywall' problem as substantial amount of data needs to be transferred from memory to processors. Recent advances in non-volatile memory (NVM) enable processing-in-memory (PIM), which reduces data transfer and thus alleviates the performance bottleneck. Nevertheless, NVM PIM supports specific operations only (e.g., dot-product on non-negative integer vectors) but not arbitrary operations. In this paper, we tackle the above challenge and carefully exploit NVM PIM to accelerate similarity-based mining tasks on multi-dimensional data without compromising the accuracy of results. Experimental results on real datasets show that our proposed method achieves up to 10.5x and 8.5x speedup for state-of-artkNN classification andk-means clustering algorithms, respectively.

Performance-monitoring timeseries systems such as Prometheus and InfluxDB play a critical role in assuring reliability and operationally. These systems commonly adopt a column-oriented storage model, by which timeseries samples from different time-series are separated, and all samples (with both numeric values and timestamps) in one timeseries are grouped into chunks and stored together. As a group of timeseries are often collected from the same source with the same timestamps, managing timestamps and metrics in a group manner provides more opportunities for query and insertion optimization but posts new challenges as well. Besides, for performance monitoring systems, to support better compression and efficient queries for most recent data that are most likely accessed by users, huge volumes of data are first cached in memory and then periodically flushed to disks. Periodic data flushing incurs high IO overhead, and simply discarding flushed data, which can still serve queries, not only is a waste but also brings huge memory reclamation cost. In this paper, we propose Heracles which integrates two techniques - (1) a new storage model, which enables efficient queries on compressed data by utilizing the shared timestamp column to easily locate corresponding metric values; (2) a novel two-level epoch-based memory manager, which allows the system to gradually flush and reclaim in-memory data while unreclaimed data can still serve queries. Heracles is implemented as a standalone module that can be easily integrated into existing performance monitoring timeseries systems. We have implemented a fully functional prototype with Heracles based on Prometheus tsdb, a representative open-source performance monitoring system, and conducted extensive experiments with real and synthetic timeseries data. Experimental results show that, compared with Prometheus, Heracles can improve the insertion throughput by 171%, and reduce the query latency and space usage by 32% and 30%, respectively, on average. Besides, to compare with other state-of-the-art storage techniques, we have integrated LevelDB (for LSM-tree-based structure) and Parquet (for column stores) into Prometheus tsdb, respectively, and experimental results show Heracles outperform these two integrations. We have released the open-source code of Heracles for public access.

Shingled Magnetic Recording (SMR) Disks are adopted as a high-density, non-volatile media that significantly precedes conventional disks in both the storage capacity and cost. However, inefficient read-modify-writes (RMWs) greatly challenge the management of SMR disks. This article for the first time presents an approach called Tiler to manage SMR disks by dividing the physical space into small autonomous regions (ARs). Each AR can manage its space allocation, address mapping, and cleaning independently. By managing these ARs in a log-structured way, RMWs can be avoided; besides, ARs can also help update data when the adjacent tracks contain no valid data. Tiler is capable of partitioning a large-scale cleaning into self-contained-small-scale cleaning and thus, the data that need to be relocated are limited inside independent ARs, which further minimizes the performance overhead. Our experimental results show that Tiler can shorten the overall system response time by 50.21 percent and reduce the cleaning time by 90.24 percent on average.

Flash-based SSD RAID arrays are increasingly being deployed in data centers. Compared with HDD arrays, SSD arrays drastically enhance I/O performance and density, and reduce power, cooling, and rack space. Nevertheless, SSDs suffer aging issues. Especially, an SSD has limited endurance and needs to be replaced when it reaches to the end of its lifetime. Although prior studies have been conducted to address this disadvantage, effective techniques of RAID/SSD controllers are urgently needed to extend the lifetime of SSD arrays. In this article, we propose a novel RAID architecture, called FreeRAID, to leverage the interplay of RAID and SSD controllers to optimize the lifespan of flash-based SSD arrays. FreeRAID adds a new exploitable phase to the life cycle of flash blocks. In FreeRAID, flash space is separated into normal space and exploitable space, and they are used to serve normal data and approximate data, respectively. We design a dual-space management scheme for RAID controllers to intelligently allocate SSD spaces based on their aging status. Inside an SSD, we propose an adaptive flash translation layer for the SSD controller to maintain the reliability and space efficiency of flash memories. We implemented a prototype of FreeRAID based on an SSD array simulator. Our experiments show that FreeRAID can significantly increase the lifetime by up to 3.07 × compared with conventional SSD-based RAID arrays.

Shingled Magnetic Recording (SMR) disks have been proposed as a promising solution to satisfy the increasing capacity need in the big data era. Drive-Managed SMR (DM-SMR) disk which acts as a traditional block device is favored for providing high compatibility. However, DM-SMR disks suffer from high performance recovery time (PRT) due to the "SMR space reclamation" issue. This paper proposes an optimal cache management named K-Framed Reclamation (KFR) to minimize PRT within the DM-SMR disk. The effectiveness of our proposed design was evaluated with realistic and intensive I/O workloads and the results are encouraging.

Weight sparsity has been explored to achieve energy efficiency for Resistive Random-access Memory (ReRAM) based DNN accelerators. However, most existing ReRAM-based DNN accelerators are based on an overidealized crossbar architecture and mainly focus on compressing zero weights. In this paper, we propose a novel ReRAM-based accelerator — PattPIM, to achieve space compression and computation reuse by studying DNN weight patterns based on practical ReRAM crossbars. We first thoroughly analyze the weight distribution characteristics of several typical DNN models and observe many non-zero weight pattern repetitions (WPRs). Thus, in PattPIM, we propose a WPR-aware DNN engine and a WPR-to-OU mapping scheme to save both space and computation resources. Furthermore, we adopt an approximate weight pattern transform algorithm to improve the DNN WPRs ratio to enhance the reuse efficiency with negligible inference accuracy loss. Our evaluation with 6 DNN models shows that the proposed PattPIM delivers significant performance improvement, ReRAM resources efficiency and energy saving.

Emerging applications like machine learning in embedded devices (e.g., satellite and vehicles) require huge storage space, which recently stimulates the widespread deployment of large-capacity flash memory in IoT devices. However, existing embedded file systems fall short in managing large-capacity storage efficiently for excessive memory consumption and poor booting performance. In this paper, we propose a novel embedded file system, LOFFS, to tackle the above issues and manage large-capacity NAND flash on resource-limited embedded devices. We redesign the space management mechanisms and construct hybrid file structures to achieve high performance with minimum resource occupation. We have implemented LOFFS in Linux, and the experimental results show that LOFFS outperforms YAFFS by 55.8% on average with orders of magnitude reductions on memory footprint.

DAG-based blockchain systems have been deployed to enable trustworthy peer-to-peer transactions for IoT devices. Unique address checking, as a key part of transaction generation for privacy and security protection in DAG-based blockchain systems, incurs big latency overhead and degrades system throughput.

Blockchain has gained a lot of attention from both academia and industry. However, traditional standard blockchains, such as Bitcoin and Ethereum, suffer from low throughput, high computation overhead, and large transaction fee, which is not suitable for Internet of Things (IoT) transactions. Recently, transaction-based approaches, such as Tangle structure which is based on a directed acyclic graph (DAG), have emerged to solve blockchain scalability issues for IoT environment. In transaction-based blockchain, for a transaction, namely, a node, to be attached to the Tangle, it needs to verify two other transactions. However, with the Tangle expanding, this attaching process consumes huge computational resources and energy, which severely limits the performance of the transaction-based blockchain. In this article, we present Re-Tangle, a highly parallelized processing-in-memory (PIM)-based accelerator for transaction-based blockchain. Re-Tangle is composed of a random walking module, a transaction validation module, and a PoW module, to improve the Tangle system performance. These modules transfer Tangle functions, such as fast exponentiation and modular, into ReRAM-based logic analog computation units. In the random walking module, Re-Tangle maintains an exponentiation table to reduce its design complexity and improve its computation efficiency. In the transaction validation module, Re-Tangle further proposes a highly parallel modular unit to accelerate the validation of different tags in a transaction. In the PoW module, we decompose the Curl hash function into basic logic OR, AND, SHIFT, and XOR operations, and map these logic operations to ReRAM crossbars in parallel to accelerate the working process. The experimental results show that Re-Tangle distinguishes itself from other architectures with significant performance improvement and energy saving. The throughput of Re-Tangle is about 22.4× and 2.38× higher compared with CPU and GPU, respectively, and the energy consumption of Re-Tangle is 83.5× and 5.77× less for equal workload.

Modern mobile devices, such as smartphones, maintain a directory cache (DCache) to accelerate directory and file accesses. However, the original DCache recursively walks through all the components of a path name for each directory entry (dentry) lookup operation, leading to low lookup efficiency. In this article, we first investigate intrinsic characteristics of dentry lookup operations in smartphones and make several interesting findings: 1) file path lookup operations are called frequently (up to 104times per second) by mobile applications; 2) file path lookup operations present high temporal and spatial locality; and 3) the latency of a file path lookup is linear to the depth of the path name. Based on our findings, we further propose an efficient directory entry lookup cache architecture, named dynamic skipping cache (DS-Cache), which adopts an ASCII-based hash table to simplify the path lookup complexity. In DS-Cache, a dynamic skip lookup algorithm is proposed to skip the common prefixes of different accessing paths. A rename algorithm and a delete algorithm are designed to promise the consistence of DS-Cache and the backend file system. We also design a prefix-aware cache replacement scheme to optimize the DS-Cache hit ratio. We have implemented and deployed DS-Cache on a Google Nexus 6P smartphone. The experimental results show that we can significantly reduce the latency of invoking system calls by up to 81%, and further reduce the completion time of real-world mobile applications by up to 67%.

Journaling techniques play an important role in addressing the reliability issue of filesystems caused by the volatile dynamic random access memory (DRAM)-based buffer cache. However, journaling techniques introduce a large number of extra storage writes, which greatly degrades system performance, especially for mobile devices. Emerging nonvolatile memory (NVM) technologies bring a new perspective of solving the write amplification issue caused by journaling. By adopting NVM as the buffer cache, the committed data can be maintained in NVM before being written back to the storage, thus, eliminating the journaling overhead. However, simply utilizing NVM as the buffer cache suffers from the limited lifetime and the relatively longer write latency of NVM. In this paper, we present a hybrid buffer cache architecture, named UniBuffer, by combing NVM with dynamic random access memory (DRAM) to reduce the journaling overhead and overcome the inherent constraints of NVM. In UniBuffer, we first propose a journaling-aware page management (JAPM) policy to smartly allocate data to DRAM and NVM pages. JAPM puts infrequently updated data in NVM to reduce the journaling overhead and frequently updated data in DRAM to improve the write performance and lifetime of the hybrid buffer cache. In addition, since data in one journaling transaction may be dispersed in NVM and DRAM simultaneously, different committing policies are required for different storage media, respectively. In order to guarantee the atomicity of the transaction execution in the hybrid cache architecture, a partial in-place commit (PIPC) journaling scheme is proposed to coordinate different committing patterns for NVM and DRAM. We have implemented the proposed techniques on Linux 3.14.52 and measured the performance with representative I/O-intensive benchmarks. The experimental results show that our scheme effectively improves the I/O performance compared with the ext4 filesystem and prolongs the lifetime of the hybrid buffer cache compared with the union of buffer cache and journaling (UBJ) scheme.

The 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 article, we solve several fundamental problems in the design of MLC flash translation layer. The objective is to reduce the garbage collection overhead to reduce the average system response time. We make the key observation that the valid pages copy is the essential garbage collection overhead. Based on this observation, we propose two approaches, namely, concentrated mapping and postponed reclamation, to effectively reduce the valid pages copy. Besides, we propose a progressive garbage collection that can well utilize the system idle time to reclaim more spaces. We conduct a series of experiments on an embedded developing board with a set of benchmarks. The experimental results show that our scheme can achieve a significant reduction in the average system response time compared with the previous work.

Flash-based key-value caching is becoming popular in data centers for providing high-speed key-value services. These systems adopt slab-based space management on flash and provide a low-cost solution for key-value caching. However, optimizing cache efficiency for flash-based key-value cache systems is highly challenging, due to the huge number of key-value items and the unique technical constraints of flash devices. In this article, we present a dynamic on-line compression scheme, called SlimCache , to improve the cache hit ratio by virtually expanding the usable cache space through data compression. We have investigated the effect of compression granularity to achieve a balance between compression ratio and speed, and we leveraged the unique workload characteristics in key-value systems to efficiently identify and separate hot and cold data. To dynamically adapt to workload changes during runtime, we have designed an adaptive hot/cold area partitioning method based on a cost model. To avoid unnecessary compression, SlimCache also estimates data compressibility to determine whether the data are suitable for compression or not. We have implemented a prototype based on Twitter’s Fatcache. Our experimental results show that SlimCache can accommodate more key-value items in flash by up to 223.4%, effectively increasing throughput and reducing average latency by up to 380.1% and 80.7%, respectively.

Blockchain's decentralized and consensus mechanism has attracted lots of applications, such as IoT devices. Blockchain maintains a linked list of blocks and grows by mining new blocks. However, the Blockchain mining consumes huge computation resource and energy, which is unacceptable for resource-limited embedded devices. This paper for the first time presents a ReRAM-based processing-in-memory architecture for Blockchain mining, called Re-Mining. Re-Mining includes a message schedule module and a SHA computation module. The modules are composed of several basic ReRAM-based logic operations units, such as ROR, RSF and XOR. Re-Mining further designs intra-transaction and inter-transaction parallel mechanisms to accelerate the Blockchain mining. Simulation results show that the proposed Re-Mining architecture outperforms CPU-based and GPU-based implementations significantly.

Our modern devices are filled with files, directories upon directories. Applications generate huge I/O activities in mobile devices. Directory cache is adopted to accelerate file lookup operations in the virtual file system. However, the original directory cache recursively walks all the components of a path for each lookup, leading to inefficient lookup performance and lower cache hit ratio. In this paper, we for the first time fully investigate the characteristics of the directory entry lookup in mobile devices. Based on our findings, we further propose a new directory cache scheme, called Dynamic Skipping Cache, which adopts an ASCII-based hash table to simplify the path lookup complexity by skipping the common prefixes of paths. We also design a novel lookup scheme to optimize the directory cache hit ratio. We have implemented and deployed DS-Cache on a Google Nexus 6P smartphone. Experimental results show that we can significantly reduce the latency of invoking system calls by up to 57.4%, and further reduce the completion time of real-world mobile applications by up to 64%.

Deep convolutional neural networks have become the mainstream solution for many artificial intelligence applications. However, they are still rarely deployed on mobile or edge devices due to the cost of a substantial amount of data movement among limited resources. The emerging processing-inmemory neuromorphic architecture offers a promising direction to accelerate the inference process. The key issue becomes how to effectively allocate the processing of inference between computing and storage resources on an edge device.This paper presents Mobile-I, a resource allocation scheme to accelerate the Inference process on Mobile or edge devices. Mobile-I targets at the emerging 3D neuromorphic architecture to reduce the processing latency among computing resources and fully utilize the limited on-chip storage resources. We formulate the target problem as a resource allocation problem and use a software-based solution to offer the cross-platform deployment across multiple mobile or edge devices. We conduct a set of experiments using realistic workloads that are generated from Intel Movidius neural compute stick. Experimental results show that Mobile-I can effectively reduce the processing latency and improve the utilization of computing resources with negligible overhead in comparison with representative schemes.

Blockchain has gained a lot of attentions from both academic and industry. Transaction-based approaches such like Tangle structure, which is based on a DAG (Directed Acyclic Graph), are emerging to solve the blockchain scalability issues for IoT environment. In transaction-based blockchain, for a transaction, namely a node, to be attached to the Tangle, it needs to verify two other transactions. However, with the Tangle expanding, this attaching process consumes huge computational resources and energy, which severely limits the performance of the transaction-based blockchain. In this paper, we present Re-Tangle, a novel transaction-based blockchain acceleration architecture that explores the opportunity of performing massive parallel operations with low hardware and energy cost. Re-Tangle consists of a random walking module and a transaction validation module, which transfer Tangle functions into ReRAM-based logic analog computation units. In the random walking module, Re-Tangle maintains a exponentiation translator to reduce its design complexity and improve its computation efficiency for exponentiation. In the transaction validation module, Re-Tangle further proposes a highly parallel modular unit to accelerate the validation of different tags in a transaction. The experience results show that Re-Tangle distinguishes itself from other architectures, with significant performance improvement and energy saving. The throughput of Re-Tangle is about 19.4× and 2.13× higher compared with CPU and GPU, respectively, and the energy consumption of Re-Tangle is 63.35 × and 4.92 × less.

The rapid adoption of solid-state drives (SSDs) as a major storage component has been made possible thanks to their ability to export a standard block I/O interface to file system and application developers. Meanwhile, this high-level abstraction has been shown to limit the utilization of the devices and the performance of applications running on top of them. Indeed, many optimizations of performance-critical applications bypass the standard block interface and rely on low-level control over SSD internal processes. However, the need to directly manage the physical device significantly increases development complexity and cost, and reduces its portability. Thus, application developers must choose between two extreme options, either easy development or optimal performance, without a real possibility to balance between these two objectives. To bridge this gap, we propose a flexible storage interface that exports the SSD hardware in three levels of abstraction: as a raw flash media with its low-level details, as a group of functions to manage flash capacity, or as a configurable block device. This multi-level abstraction allows developers to choose the degree in which they desire to control the flash hardware in a manner that best suits their applications' semantics and performance objectives. We demonstrate the usability of this new model with Prism-SSD-a prototype of this interface as a user-level library on the Open-Channel SSD platform. We use each of the interface's three abstraction levels to modify the I/O module of three representative applications: a key-value cache system, a user-level file system, and a graph processing engine. Prism-SSD improves application performance by 5% to 27%, at varying development costs, between 200 and 3,500 lines of code.

In this paper, we propose a holistic solution to address several important and challenging issues in storage data management in light of emerging NVDIMM-based architecture: namely, new performance modeling, NVDIMM-based migration, and architectural support for NVDIMMs on migration optimization. In particular, a novel NVDIMM-based heterogeneous storage performance model is proposed to effectively address bus contention issues caused by placing NVDIMMs on the memory bus. We also develop an NVDIMM-based lazy migration scheme to effectively minimize adverse effects caused by memory traffic interferences during storage data management processes. Finally, the NVDIMM-based architectural support for migration optimization is proposed to increase channel parallelism in the destination NVDIMMs and bypass buffer caches in the source NVDIMMs, so that the impact of memory traffic can be alleviated. We present detailed evaluation and analysis to quantify how well our techniques can enhance the I/O performances of big workloads via efficient heterogeneous storage hierarchy management. Our experimental results show that overall the proposed techniques yield up to 98% performance improvement over the state-of-the-art techniques.

NAND flash memory has been widely adopted as the storage medium. As power failure may occur at any time and result in data loss, crash recovery becomes vitally important in NAND flash memory storage systems. Since flash translation layers (FTLs) are used to manage flash memory, the crash recovery problem in NAND flash is how to efficiently and effectively recover FTL metadata with consistency after system crash. In this paper, we present deterministic crash recovery (DCR) that adopts a deterministic approach for crash recovery in NAND flash storage systems. The basic idea is to exploit the determinism of FTLs and reproduce events that happened between the last checkpoint and the crash point during crash recovery. Different from existing approaches that need to scan the whole flash memory chip, DCR can recover the system more efficiently by only checking a limited number of blocks based on deterministic FTL operations. We have implemented DCR in an FTL and compared it with the representative version-based and power loss recovery schemes based on an ARM-based embedded system. Experimental results show that DCR can greatly reduce the recovery time and guarantee the consistency of FTL metadata after recovery.

Shingled magnetic recording (SMR) is a novel technology that can significantly increase the disk capacity and reduce the cost. However, this new technology leads to write constraint that prohibits random writes to SMR disks. In order to solve this, current solutions utilize a persistent cache (PC) to change random writes to sequential ones. By doing this, nevertheless, the hot-data write-back effect will be triggered which inevitably incurs extra read-modify-write (RMW) operations. This paper presents a cache management scheme calleddual-bufferto manage the overall SMR space, by which the PC is partitioned into the persistent buffer and the filter buffer. It leaves hot data in the filter buffer and moves cold data back to the SMR disk so that the hot data write-back effect can be alleviated. Since the PC may contain a large amount of valid data,dual-bufferalso presents a prediction-based dynamic configuration strategy so hot data can be cached as much as possible. We conducted a series of experiments with synthetic traces. Experimental results show that ourdual-bufferscheme can shorten the average response time by 51.66% on average and reduce the total number of RMW operations by 98.76% on average compared to the previous work.

SQLite has been deployed in millions of mobile devices from Web to smartphone applications on various mobile operating systems. However, due to the uncoordinated IO interactions with the underlying file system (e.g., ext4), SQLite is not efficient with low transactions per second. In this paper, we for the first time propose a new SQLite-like database engine, called SQLiteKV, which adopts the LSM-tree-based data structure but retains the SQLite operation interfaces. With its SQLite interface, SQLiteKV can be utilized by existing applications without any modification, while providing high performance with its LSM-tree-based data structure. We separate SQLiteKV into the front-end and back-end. In the front-end, we develop a light-weight SQLite-to-KV compiler to solve the semantic mismatch, so SQL statements can be efficiently translated into KV operations. We also design a novel coordination caching mechanism with memory defragmentation so query results can be effectively cached inside SQLiteKV by alleviating the discrepancy of data management between front-end SQLite statements and back-end data organization. In the back-end, we adopt an LSM-tree-based key-value database engine, and propose a lightweight metadata management scheme to mitigate the memory requirement. We have implemented and deployed SQLiteKV on a Google Nexus 6P smartphone. Experimental results with various workloads show that SQLiteKV outperforms SQLite up to six times.

editorial Free Access Share on Dependability in Cyber-Physical Systems and Applications Authors: Md Zakirul Alam Bhuiyan Fordham University, New York, NY, USA Fordham University, New York, NY, USAView Profile , Sy-yen Kuo National Taiwan University, Taipei, Taiwan National Taiwan University, Taipei, TaiwanView Profile , Damian Lyons Fordham University, New York, NY, USA Fordham University, New York, NY, USAView Profile , Zili Shao The Hong Kong Polytechnic University, Hung Hom, Hong Kong The Hong Kong Polytechnic University, Hung Hom, Hong KongView Profile Authors Info & Claims ACM Transactions on Cyber-Physical SystemsVolume 3Issue 1January 2019 Article No.: 1pp 1–4https://doi.org/10.1145/3271432Published:29 September 2018Publication History 4citation680DownloadsMetricsTotal Citations4Total Downloads680Last 12 Months116Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteView all FormatsPDF

Shingled Magnetic Recording (SMR) disks have been proposed as a high-density, non-volatile media and precede traditional hard disk drives in both storing capacity and cost. However, the intrinsic characteristics of SMR disks raise a major performance challenge named read-modify-write operations (RMWs) that are time-consuming and can significantly degrade the overall system performance. Current designs of SMR disks usually adopt a persistent cache to alleviate the negative effect brought by RMWs and the cache is used as a first-level cache to buffer all the incoming writes of the whole SMR storage system. In this paper, we propose to change the functionality of the cache, that is, the cache will no longer serve as a first-level cache like previous. Incoming data are distinguished according to their different write-back behavior and those data which will incur RMWs will be left in our built-in NAND flash cache called RMW-free Cache (RMW-F) to eliminate the need of RMWs. Besides, RMW-F improves the cleaning efficiency by a model that takes both write-back cost and data popularity into considerations. Our experimental results show that RMW-F can achieve both system performance and cleaning efficiency improvements.

In a reconfigurable battery pack, the connections among cells can be changed during operation to form different configurations. This can lead a battery, a passive two-terminal device, to a smart battery that can reconfigure itself according to the requirement to enhance operational performance. Several hardware architectures with different levels of complexities have been proposed. Some researchers have used existing hardware and demonstrated improved performance on the basis of novel optimization and scheduling algorithms. The possibility of software techniques to benefit the energy storage systems is exciting, and it is the perfect time for such methods as the need for high-performance and long-lasting batteries is on the rise. This novel field requires new understanding, principles, and evaluation metrics of proposed schemes. In this article, we systematically discuss and critically review the state of the art. This is the first effort to compare the existing hardware topologies in terms of flexibility and functionality. We provide a comprehensive review that encompasses all existing research works, starting from the details of the individual battery including modeling and properties as well as fixed-topology traditional battery packs. To stimulate further research in this area, we highlight key challenges and open problems in this domain.

Checkpointing is a key enabler of hibernation, live migration and fault-tolerance for virtual machines (VMs) in mobile devices. However, checkpointing a VM is usually heavyweight: the VM's entire memory needs to be dumped to storage, which induces a significant amount of (slow) I/O operations, degrading system performance and user experience. In this paper, we propose FLIC, a fast and lightweight checkpointing machinery for virtualized mobile devices by taking advantages of recent byte-addressable, non-volatile memory (NVRAM). Instead of saving the VM's entire memory to storage, we store its working set pages in NVRAM, avoiding accessing slow flash memory (compared to server-grade SSDs). To further reduce the write activities to flash memory, we propose an energy-efficient data deduplication to eliminate redundant data in VM snapshot and save storage space. Experimental results based on an Exynos 5250 SoC show that our approach can effectively improve the performance of checkpointing in mobile virutalization and save energy.

Redundancy resolution is a critical problem in the control of manipulators. The dual neural network, as a special type of recurrent neural networks that are inherently parallel processing models, is widely investigated in past decades to control manipulators. However, to the best of our knowledge, existing dual neural networks require a full knowledge about manipulator parameters for efficient control. We make progress along this direction in this paper by proposing a novel model-free dual neural network, which is able to address the learning and control of manipulators simultaneously in a unified framework. Different from pure learning problems, the interplay of the control part and the learning part allows us to inject an additive noise into the control channel to increase the richness of signals for the purpose of efficient learning. Due to a deliberate design, the learning error is guaranteed for convergence to zero despite the existence of additive noise for stimulation. Theoretical analysis reveals the global stability of the proposed neural network control system. Simulation results verify the effectiveness of the proposed control scheme for redundancy resolution of a PUMA 560 manipulator.

SQLite has been deployed in millions of mobile devices from web to smartphone applications on various mobile operating systems. However, SQLite is not efficient with low transactions per second. In this paper, we for the first time propose a new SQLite-like database engine, called SQLiteKV, which adopts the LSM-tree-based data structure but retains the SQLite operation interfaces. With its SQLite interface, SQLiteKV can be utilized by existing applications without any modification, while providing high performance with its LSM-tree-based data structure. In SQLiteKV, we develop a light-weight SQLite to key-value compiler to solve the semantic mismatch, so SQL statements can be efficiently translated into KV operations. We also design a novel coordination caching mechanism so query results can be effectively cached inside SQLiteKV by alleviating the discrepancy of data management between front-end SQLite statements and back-end key-value data organization. We have implemented and deployed SQLiteKV on a Google Nexus 6P smartphone. Experiments results show that SQLiteKV outperforms SQLite up to 6 times.

Convolutional computations implemented in RRAM crossbar-based Computing System (RCS) demonstrate the outstanding advantages of high performance and low power. However, current designs are energy-unbalanced among the three parts of RRAM crossbar computation, peripheral circuits and memory accesses, and the latter two factors can significantly limit the potential gains of RCS. Addressing the problem of high power overhead of peripheral circuits in RCS, this paper proposes a Peripheral Circuit Unit (PeriCU)-Reuse scheme to meet power budgets in energy constrained embedded systems. The underlying idea is to put the expensive ADCs/DACs onto spotlight and arrange multiple convolution layers to be sequentially served by the same PeriCU. In the solution, the first step is to determine the number of PeriCUs which are organized by cycle frames. Inside a cycle frame, the layers are computed in parallel inter-PeriCUs while sequentially intra-PeriCU. Furthermore, a layer retiming technique is exploited to further improve the energy of RCS by assigning two adjacent layers within the same PeriCU so as to bypass the energy consuming memory accesses. The experiments of five convolutional applications validate that the PeriCU-Reuse scheme integrated with the retiming technique can efficiently meet variable power budgets, and further reduce energy consumption efficiently.

In this paper, we propose a reliable video storage architecture in hybrid SLC/MLC storage systems. In this architecture, the video stream is reconstructed as the key cluster and the non-key cluster according to the importance of video restoration. The key cluster is stored in SLC blocks to ensure the reliability, while the non-key cluster is stored in MLC blocks to utilize its capacity. The experimental results show that the proposed scheme can significantly improve the storage reliability of the video files and prolong the lifetime of the storage system 18x.

Flash-based SSD RAID arrays are increasingly being deployed in data centers. Compared with HDD arrays, SSD arrays drastically enhance storage density and I/O performance, and reduce power and rack space. Nevertheless, SSDs suffer aging issues. Though prior studies have been conducted to address this disadvantage, effective techniques of RAID/SSD controllers are urgently needed to extend the lifetime of SSD arrays.

Flash-based key-value caching is becoming popular in data centers for providing high-speed key-value services. These systems adopt slab-based space management on flash and provide a low-cost solution for key-value caching. However, optimizing cache efficiency for flash-based key-value cache systems is highly challenging, due to the huge number of key-value items and the unique technical constraints of flash devices. In this paper, we present a dynamic on-line compression scheme, called SlimCache, to improve the cache hit ratio by virtually expanding the usable cache space through data compression. We have investigated the effect of compression granularity to achieve a balance between compression ratio and speed, and leveraged the unique workload characteristics in key-value systems to efficiently identify and separate hot and cold data. In order to dynamically adapt to workload changes during runtime, we have designed an adaptive hot/cold area partitioning method based on a cost model. Inorder to avoid unnecessary compression, SlimCache also estimates data compressibility to determine whether the data are suitable for compression or not. We have implemented a prototype based on Twitter's Fatcache. Our experimental results show that SlimCache can accommodate more key-value items in flash by up to 125.9%, effectively increasing throughput and reducing average latency by up to 255.6% and 78.9%, respectively.

In mixed-criticality (MC) systems, multiple activities with various certification requirements (thus with different criticality levels) can co-exist on shared hardware platforms, where multicore processors have emerged as the de facto computing engines. In this paper, by using the partitioned earliest-deadline-first with virtual deadlines (EDF-VDs) scheduler for a set of periodic MC tasks running on multicore systems, we derive a criticality-aware utilization bound for efficient feasibility tests and then identify its characteristics. Our analysis shows that the bound increases with increasing number of cores and decreasing system criticality level. We show that, since the utilizations of MC tasks at different criticality levels can vary considerably, the utilization contribution of a task on different cores may have large variations and thus can significantly affect the system schedulability under the EDF-VD scheduler. Based on these observations, we propose a novel and efficient criticality-aware task partitioning algorithm (CA-TPA) to compensate for the inherent pessimism of the utilization bound. In order to improve the system schedulability, the task priorities are determined according to their utilization contributions to the system in CA-TPA. Moreover, by analyzing the utilization variations of tasks at different levels, we develop several heuristics to minimize the utilization increment and balance the workload on cores. The simulation results show that the CA-TPA scheme is very effective in achieving higher schedulability ratio and yielding balanced workloads. The actual implementation in Linux operating system further demonstrates the applicability of CA-TPA with lower run-time overhead, compared to the existing partitioning schemes.

There has been a surge of interest in Non-Volatile Memory (NVM) in recent years. With many advantages, such as density and power consumption, NVM is carving out a place in the memory hierarchy and may eventually change our view of computer architecture. Many NVMs have emerged, such as Magnetoresistive random access memory (MRAM), Phase Change random access memory (PCM), Resistive random access memory (ReRAM), and Ferroelectric random access memory (FeRAM), each with its own peculiar properties and specific challenges. The scientific community has carried out a substantial amount of work on integrating those technologies in the memory hierarchy. As many companies are announcing the imminent mass production of NVMs, we think that it is time to have a step back and discuss the body of literature related to NVM integration. This article surveys state-of-the-art work on integrating NVM into the memory hierarchy. Specially, we introduce the four types of NVM, namely, MRAM, PCM, ReRAM, and FeRAM, and investigate different ways of integrating them into the memory hierarchy from the horizontal or vertical perspectives. Here, horizontal integration means that the new memory is placed at the same level as an existing one, while vertical integration means that the new memory is interleaved between two existing levels. In addition, we describe challenges and opportunities with each NVM technique.

Graph algorithms such as graph traversal have been gaining ever-increasing importance in the era of big data. However, graph processing on traditional architectures issues many random and irregular memory accesses, leading to a huge number of data movements and the consumption of very large amounts of energy. To minimize the waste of memory bandwidth, we investigate utilizing processing-in-memory (PIM), combined with non-volatile metal-oxide resistive random access memory (ReRAM), to improve both computation and I/O performance. We propose a new ReRAM-based processing-in-memory architecture called RPBFS, in which graph data can be persistently stored and processed in place. We study the problem of graph traversal, and we design an efficient graph traversal algorithm in RPBFS. Benefiting from low data movement overhead and high bank-level parallel computation, RPBFS shows a significant performance improvement compared with both the CPU-based and the GPU-based BFS implementations. On a suite of real-world graphs, our architecture yields a speedup in graph traversal performance of up to 33.8×, and achieves a reduction in energy over conventional systems of up to 142.8×.

Key-value caching is crucial to today’s low-latency Internet services. Conventional key-value cache systems, such as Memcached, heavily rely on expensive DRAM memory. To lower Total Cost of Ownership, the industry recently is moving toward more cost-efficient flash-based solutions, such as Facebook’s McDipper [14] and Twitter’s Fatcache [56]. These cache systems typically take commercial SSDs and adopt a Memcached-like scheme to store and manage key-value cache data in flash. Such a practice, though simple, is inefficient due to the huge semantic gap between the key-value cache manager and the underlying flash devices. In this article, we advocate to reconsider the cache system design and directly open device-level details of the underlying flash storage for key-value caching. We propose an enhanced flash-aware key-value cache manager, which consists of a novel unified address mapping module, an integrated garbage collection policy, a dynamic over-provisioning space management, and a customized wear-leveling policy, to directly drive the flash management. A thin intermediate library layer provides a slab-based abstraction of low-level flash memory space and an API interface for directly and easily operating flash devices. A special flash memory SSD hardware that exposes flash physical details is adopted to store key-value items. This co-design approach bridges the semantic gap and well connects the two layers together, which allows us to leverage both the domain knowledge of key-value caches and the unique device properties. In this way, we can maximize the efficiency of key-value caching on flash devices while minimizing its weakness. We implemented a prototype, called DIDACache, based on the Open-Channel SSD platform. Our experiments on real hardware show that we can significantly increase the throughput by 35.5%, reduce the latency by 23.6%, and remove unnecessary erase operations by 28%.

The charging power supply for batteries may be variable under many circumstances, e.g., when using solar panels or air-driven generators as the energy source. The mismatch between the voltages of the power supply and the battery may cause significant charging inefficiency. In this paper, we use reconfigurable batteries to solve this voltage mismatch problem. We develop algorithms to dynamically decide the battery connections, to both minimize the voltage mismatch and maintain SOC balancing among difference batteries. We build a hardware prototype to implement and validate our method and use simulation experiments to empirically evaluate its performance.

Substantially reduced lifetimes are becoming a critical issue in NAND flash memory with the advent of multi-level cell and triple-level cell flash memory. Researchers discovered that heating can cause worn-out NAND flash cells to become reusable and greatly extend the lifetime of flash memory cells. However, the heating process consumes a substantial amount of power, and some fundamental changes are required for existing NAND flash management techniques. In particular, all existing wear-leveling techniques are based on the principle of evenly distributing writes and erases. For self-healing NAND flash, this may cause NAND flash cells to be worn out in a short period of time. Moreover, frequently healing these cells may drain the energy quickly in battery-driven mobile devices, which is defined as the concentrated heating problem. In this paper, we propose a novel wear-leveling scheme called DHeating (Dispersed Heating) to address the problem. In DHeating, rather than evenly distributing writes and erases over a time period, write and erase operations are scheduled on a small number of flash memory cells at a time, so that these cells can be worn out and healed much earlier than other cells. In this way, we can avoid quick energy depletion caused by concentrated heating. In addition, the heating process takes several seconds and has become the new performance bottleneck. In order to address this issue, we propose a lazy heating repair scheme. The lazy heating repair scheme can ease the long time delays caused by the heating via delaying the heating operation and using the system idle time to repair. Furthermore, the flash memory's reliability becomes worse with the flash memory cells reaching the excepted worn-out time. We propose an early heating strategy to solve the reliability problem. With the extended lifetime provided by self-healing, we can trade some lifetimes for reliability. The idea is to start the healing process earlier than the expected worn-out time. We evaluate our scheme based on an embedded platform. The experimental results show that the proposed scheme can effectively prolong the consecutive heating time interval, alleviate the long time delays caused by the heating, and enhance the reliability for self-healing flash memory.

NAND flash memory is the major storage media for both mobile storage cards and enterprise Solid-State Drives (SSDs). Log-block-based Flash Translation Layer (FTL) schemes have been widely used to manage NAND flash memory storage systems in industry. In log-block-based FTLs, a few physical blocks called log blocks are used to hold all page updates from a large amount of data blocks. Frequent page updates in log blocks introduce big overhead so log blocks become the system bottleneck. To address this problem, this paper presents BLog, a block-level log-block management scheme for MLC NAND flash memory storage system. In BLog, with block-level management, the update pages of a data block can be collected together and put into the same log block as much as possible; therefore, we can effectively reduce the associativities of log blocks so as to reduce the garbage collection overhead. We also propose a novel partial merge operation strategy called reduced-order merge by which we can effectively postpone the garbage collection of log blocks so as to maximally utilize valid pages and reduce unnecessary erase operations in log blocks. Based on BLog, we design an FTL called BLogFTL for Multi-Level Cell (MLC) NAND flash. We conduct a set of experiments on a real hardware platform. Both representative FTL schemes and the proposed BLogFTL have been implemented in the hardware evaluation board. The experimental results show that our scheme can effectively reduce the garbage collection operations and reduce the system response time compared to the previous log-block-based FTLs for MLC NAND flash.

Smartphones are getting increasingly high-performance with advances in mobile processors and larger main memories to support feature-rich applications. However, the storage subsystem has always been a prohibitive factor that slows down the pace of reaching even higher performance while maintaining good user experience. Despite today's smartphones are equipped with larger-than-ever main memories, they consume more energy and still run out of memory. But the slow NAND flash based storage vetoes the possibility of swapping-an important technique to extend main memory-and leaves a system that constantly terminates user applications under memory pressure. In this paper, we propose NVM-Swap by revisiting swapping for smartphones with fast, byte-addressable, non-volatile memory (NVM) technologies. Instead of using flash, we build the swap area with NVM, to allow high performance without sacrificing user experience. NVM-Swap supports Lazy Swap-in, which can reduce memory copy operations by giving the swapped out pages a second chance to stay in byte-addressable NVM backed swap area. To avoid fast worn-out of certain NVM, we also propose Heap-Wear, a wear leveling algorithm that distributes writes in NVM more evenly. Evaluation results based on the Google Nexus 5 smartphone show that our solution can effectively enhance smartphone performance and achieve better wear-leveling of NVM.

I/O is becoming one of major performance bottlenecks in NAND-flash-based mobile devices. Novel nonvolatile memories (NVMs), such as phase change memory and spin-transfer torque random access memory, can provide fast read/write operations. In this paper, we propose a unified NVM/flash architecture to improve the I/O performance. A transparent scheme, virtualized flash (vFlash), is also proposed to manage the unified architecture. Within vFlash, interapp and intra-app techniques are proposed to optimize the application performance by exploiting the historical locality and I/O access patterns of applications. Since vFlash is on the bottom of the I/O stack, the application features will be lost. Therefore, we also propose a cross-layer technique to transfer the application information from the application layer to the vFlash layer. The proposed scheme is evaluated based on an Android platform, and the experimental results show that the proposed scheme can effectively improve the I/O performance of mobile devices.

A Semi Random Circle routing for mobile Sink joint Ray Routing for data (SRCRR) scheme is proposed for preserving sink-location privacy with a delay guaranteed. In the SRCRR scheme, the data are directionally routed along ray paths and stored at intermediate nodes probabilistically. The Sink moves in a semirandom circular pattern to collect data from the local nodes occasionally, which guarantees that the data will be collected with an acceptable delay and prevents attackers from predicting their locations and movements. The experimental results indicate that the performance of the SRCRR scheme is better than that of the previous schemes.

We propose a cyber-physical system of unmanned quadcopters to locate air pollution sources in a timely manner. The system consists of a physical part and a cyber part. The physical part includes unmanned quadcopters equipped with multiple sensors. The cyber part carries out control laws. We simplify the control laws by decoupling the quadcopters’ horizontal-plane motion control from vertical motion control. To control the quadcopter’s horizontal-plane motions, we propose a controller that combines pollutant dynamics with quadcopter physics. To control the quadcopter’s vertical motions, we adopt an anti-windup proportional-integral (PI) controller. We further extend the horizontal-plane control laws from a single quadcopter to multiple quadcopters. The multi-quadcopter control laws are distributed and convergent. We implement a prototype quadcopter and carry out experiments to verify the vertical control laws. We also carry out simulations to evaluate the horizontal-plane control laws. With quadcopter parameters set commensurate with our prototype implementation’s, our simulations show that the control laws can drive quadcopters to locate pollution source(s) in a timely way.

Cyber-physical-social systems (CPSS), an emerging computing paradigm, have attracted intensive attentions from the research community and industry. We are facing various challenges in designing secure, reliable, and user-satisfied CPSS. In this article, we consider these design issues as a whole and propose a system-level design optimization framework for CPSS design where energy consumption, security-level, and user satisfaction requirements can be fulfilled while satisfying constraints for system reliability. Specifically, we model the constraints (energy efficiency, security, and reliability) as the penalty functions to be incorporated into the corresponding objective functions for the optimization problem. A smart office application is presented to demonstrate the feasibility and effectiveness of our proposed design optimization approach.

The charging and discharging procedure of a battery is a typical electrochemical process, which can be modeled as a dynamic system. State of charge (SoC) is a commonly used measure to quantify the charge stored in the battery in relation to its full capacity. Recent efforts of optimizing battery performance require more accurate SoC information. The noise in sensor readings makes the estimation even more challenging, especially in battery-operated systems where the supply voltage of the sensor keeps changing. Traditionally used methods of Coulomb counting and extended Kalman filter suffer from the accumulation of noise and common phenomenon of biased noise, respectively. The traditional approach of dealing with ever-increasing demand for accuracy is to develop more complicated and sophisticated solutions, which generally require special models. A key challenge in the adoption of such systems is the inherent requirement of specialized knowledge and hit-and-trial-based tuning. In this paper, we explore a new dimension from the perspective of a self-tuning algorithm, which can provide accurate SoC estimation without error accumulation by creating a negative feedback loop and enhancing its strength to penalize the estimation error. Specifically, we propose a novel method, which uses a battery model and a conservative filter with a strong feedback, which guarantees that worst-case amplification of noise is minimized. We capitalize on the battery model for data fusion of current and voltage signals for SoC estimation. To compute the best parameters, we formulate the linear matrix inequality conditions, which are optimally solved using open-source tools. This approach also features a low computational expense during estimation, which can be used in real-time applications. Thorough mathematical proofs, as well as detailed experimental results, are provided, which highlight the advantages of the proposed method over traditional techniques.

Phase change memory (PCM) is a promising DRAM alternative because of its non-volatility, high density, low standby power and close-to-DRAM performance. These features make PCM an attractive solution to optimize the management of NAND flash memory in embedded systems. However, PCM's limited write endurance hinders its application in embedded systems. Therefore, how to manage flash memory with PCM-particularly guarantee PCM a reasonable lifetime-becomes a challenging issue. In this paper, we propose to partially replace DRAM using PCM to optimize the management of flash memory metadata for better system reliability in the presence of power failure and system crash. To prolong PCM's lifetime, we present a write-activity-aware PCM-assisted flash memory management scheme, called PCM-FTL. By differentiating sequential and random I/O behaviors, a novel two-level mapping mechanism and a customized wear-leveling scheme are developed to reduce writes to PCM and extend its lifetime. We evaluate PCM-FTL with a variety of general-purpose and mobile I/O workloads. Experimental results show that PCM-FTL can significantly reduce write activities and achieve an even distribution of writes in PCM with very low overhead.

Program disturb, read disturb, and retention time noise are identified as three major contributors to multilevel cell (MLC) NAND flash memory bit errors. With program/erase cycling and technology scaling, bit error rate (BER) of MLC NAND flash memory rapidly increases. Previous works revealed that BER is heavily dependent on data patterns. Based on this observation, we propose data-pattern-aware (DPA) error protection technique to extend the lifespan of NAND flash-based storage systems. DPA manipulates the ratios of 0's and 1's in the stored data to reduce the probability of the data patterns, which are susceptible to device noises. By minimizing the vulnerable data patterns, our scheme can effectively reduce the BER and improves the system endurance. Our DPA scheme also incorporates a data management scheme to minimize the redundancy-induced performance overhead. Simulation results show that our scheme can increase flash system life expectancy by up to 4×.

Recently, NVDIMM (Non-Volatile Dual In-line Memory Module) is being widely supported by leading hardware design companies, such as IBM. Nevertheless, existing efforts largely focus on NVDIMM specification and fabrication issues, and the potential performance gains brought by NVDIMM are not fully investigated. In this paper, we present a NVDIMM-based simulator called MCSSim to help study the memory channel storage techniques. MCSSim is a cycle-accurate simulator that is elaborated with the consideration of differences between the memory channel interface and the NAND flash memory features. MCSSim is also implemented with the DRAMSim2 [31] simulator thus enabling the simulation of a variety of hybrid memory systems by combining of DRAM DIMM and NVDIMM. We have done some experiments with MCSSim, and the experimental results show the effectiveness of the proposed simulator.

This paper presents an overview of recent trends in Battery System Management Architectures (BSMAs). After introducing the main characteristics of large battery packs, the state of the art in BSMAs is discussed. Two emerging concepts are in the focus of this contribution. On the one hand, there is a development from centralized battery management architectures with a single control entity towards decentralized management where the computational resources are distributed across the battery pack and, hence, move closer to the individual battery cells. This enables a more scalable and modular battery system architecture, while, at the same time, posing challenges regarding hardware and management algorithm design. On the other hand, the static setup of the series- and parallel-connected cells forming the battery pack may be developed towards a reconfigurable architecture such that the electrical topology of the pack can be adaptively changed. Such reconfigurability could increase the reliability of battery packs and reduce management efforts such as cell balancing. At the same time, limited energy efficiency of the additional hardware poses a challenge. We give an outlook how these two trends could be combined into distributed reconfigurable BSMAs. This introduces a set of challenges which have to be solved in order to benefit from the increased scalability, reliability and safety such designs could offer.

The long I/O latency posts significant challenges for many data-intensive applications, such as the emerging big data workloads. Recently, the NVDIMM (Non-Volatile Dual In-line Memory Module) technologies provide a promising solution to this problem. By employing non-volatile NAND flash memory as storage media and connecting them via DIMM (Dual Inline Memory Module) slots, the NVDIMM devices are exposed to memory bus so the access latencies due to going through I/O controllers can be significantly mitigated. However, placing NVDIMM on the memory bus introduces new challenges. For instance, by mixing I/O and memory traffic, NVDIMM can cause severe performance degradation on memory-intensive applications. Besides, there exists a speed mismatch between fast memory access and slow flash read/write operations. Moreover, garbage collection (GC) in NAND flash may cause up to several millisecond latency. This paper presents novel, enabling mechanisms that allow NVDIMM to more effectively bridge the I/O performance gap for big data workloads. To address the workload heterogeneity challenge, we develop a scheduling scheme in memory controller to minimize the interference between the native and the I/O-derived memory traffic by exploiting both data access criticality and resource utilization. For NVDIMM controller, several mechanisms are designed to better orchestrate traffic between the memory controller and NAND flash to alleviate the speed discrepancy issue. To mitigate the lengthy GC period, we propose a proactive GC scheme for the NVDIMM controller and flash controller to intelligently synchronize and transfer data involving in forthcoming GC operations. We present detailed evaluation and analysis to quantify how well our techniques fit with the NVDIMM design. Our experimental results show that overall the proposed techniques yield 10%~35% performance improvements over the state-of-the-art baseline schemes.

NAND flash memory has become the major storage media in mobile devices, such as smartphones. However, the random write operations of NAND flash memory heavily affect the I/O performance, thus seriously degrading the application performance in mobile devices. The main reason for slow random write operations is the out-of-place update feature of NAND flash memory. Newly emerged non-volatile memory, such as phase-change memory, spin transfer torque, supports in-place updates and presents much better I/O performance than that of flash memory. All these good features make non-volatile memory (NVM) as a promising solution to improve the random write performance for NAND flash memory. In this paper, we propose a non-volatile memory for random access (NVMRA) scheme to utilize NVM to improve the I/O performance in mobile devices. NVMRA exploits the I/O behaviors of applications to improve the random write performance for each application. Based on different I/O behaviors, such as random write-dominant I/O behavior, NVMRA adopts different storing decisions. The scheme is evaluated on a real Android 4.2 platform. The experimental results show that the proposed scheme can effectively improve the I/O performance and reduce the I/O energy consumption for mobile devices. Copyright © 2015 John Wiley & Sons, Ltd.

In this article, we propose formation control of nonholonomic mobile robots avoiding obstacles in a distributed manner for cluttered environments. The introduction of a virtual robot restructures the formation control problem into a tracking control problem between the virtual reference robot and follower robots. A novel obstacle avoidance approach is proposed based upon the scaling of whole (partial) formation corresponding to a centralized (distributed) framework. For the distributed environment with limited communication, our approach utilized proportional-integral average consensus estimators, whereby information from each robot diffuses through the communication network. The theoretical contribution is to determine the time constant involved in the diffusion process, which can affect overall system performance. The asymptotic convergence of follower robots to the position and orientation of the reference robot is ensured using the Lyapunov function. The new technique is tested with complete, limited, and no information availability. Several simulation results are provided that demonstrate the formation control and obstacle avoidance for multirobots using the proposed scheme.

This paper presents a reliability-aware metadata allocation strategy called scatter-single-level cell (SLC) for multiple-level cell (MLC) NAND flash memory storage systems. In scatter-SLC, metadata is kept in least significant bit (LSB) pages and corresponding most significant bit (MSB) pages are bypassed. Without partitioning SLC and MLC blocks, scatter-SLC can eliminate the unbalanced lifetime between SLC and MLC blocks while achieving the similar error rate as the method to store metadata in SLC blocks. We implemented scatter-SLC on a real-hardware platform. The experiment results show that scatter-SLC can reduce uncorrectable page errors by 93.54% while incurring less than 1% time overhead on average compared with the previous work.

Networked robotics are a typical cyber–physical system (CPS). This paper presents the cyber physical interaction model to perform formation control and tracking in the presence of other robots and static obstacles. It discusses how such a model can be effectively utilized to deal with kinodynamic and operation range constraints. The cyber system is also responsible for feasible trajectory generation based upon regional path segments and to ensure that all the robots maneuver through obstacles in a safe manner. The introduction of virtual robot restructures the formation control problem into a tracking control problem between virtual reference robot and follower robots. A novel obstacle avoidance approach is proposed based upon the scaling of whole (partial) formation corresponding to centralized (distributed) framework. The involved CPS has network structure preserving properties that are key to effective distributed decision making. The novel formation control, obstacle avoidance, and trajectory tracking approaches facilitate networked robots to be effectively controlled through the cyber system. We also discuss efficient and optimal implementation of the proposed trajectory generator using computer-aided design for CPSs. Evaluation of the proposed approach is provided that demonstrate the formation control, trajectory tracking, and obstacle avoidance for multirobots using the proposed scheme.

Virtualization offers significant benefits, such as better isolation and security for mobile systems. However, the limited amount of memory and virtualization's memory-demanding nature make it challenging to virtualize mobile systems efficiently. In this paper, we utilize morphable resistive memories to design a high-performance mobile system with an extensible memory space. With morphable resistive memories, a simple and effective page management technique, Balloonfish, is proposed to convert the memory cell state between multilevel and single-level for achieving a balance between performance and memory space. First, an application-specific page allocation is proposed for managing morphable resistive memories in virtualized mobile systems. Besides, we use a balloon-style algorithm to balance memory allocation among multiple virtual machines. Our evaluation based on the Samsung Exynos 5250 system-on-chip with various real Android applications shows that our system achieves 28.63% performance improvement compared with the baseline scheme.

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.

I/O is becoming one of major performance bottlenecks in NAND-flash-based smartphones. Novel NVMs (nonvolatile memories), such as PCM (Phase Change Memory) and STT-RAM (Spin-Transfer Torque Random Access Memory), can provide fast read/write operations. In this paper, we propose an unified NVM/flash architecture to improve the I/O performance. A transparent scheme, vFlash (Virtualized Flash), is also proposed to manage the unified architecture. Within vFlash, inter-app technique is proposed to optimize the application performance by exploiting the historic locality of applications. Since vFlash is on the bottom of the I/O stack, the application features will be lost. Therefore, we also propose a cross-layer technique to transfer the application information from the application layer to the vFlash layer. The proposed scheme is evaluated based on a real Android platform, and the experimental results show that the read and write performance for the proposed scheme is 2.45 times and 3.37 times better than that of the stock Android 4.2 system, respectively.

2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015, Japan, 19-22 January 2015

Virtualization offers significant benefits such as better isolation and security for mobile systems. However, the limited amount of memory and virtualization's memory-demanding nature makes it challenging to virtualize mobile systems efficiently. In this paper, we utilize morphable resistive memories to design a high-performance mobile system with extensible memory space. With morphable resistive memory, we convert the memory cell state between multi-level and single-level to achieve a balance between performance and memory space. Our evaluation based on the Samsung Exynos 5250 SoC with real Android applications shows that our system achieve 27% performance improvement compared with the baseline scheme.

Non-volatile memories (NVMs) such as Phase Change Memory (PCM) have been considered as promising candidates of next generation main memory for embedded systems due to their attractive features. These features include low power, high density, and better scalability. However, most existing NVMs suffer from two drawbacks, namely, limited write endurance and expensive write operation in terms of both time and energy. These problems are worsen when modern high-level languages employ virtual machine with garbage collector that generates a large amount of extra writes on non-volatile main memory. To tackle this challenge, this paper proposes three techniques: Living Objects Remapping (LORE), Dead Object Stamping (DOS), and Smart Wiping with Maximum Likelihood Estimation (SMILE) to reduce the unnecessary writes when garbage collector handles objects. The experimental results show that the proposed techniques not only significantly reduce the writes during each garbage collection cycle but also greatly improve the performance of virtual machine.

With the emergence of many commercial-off-the-shelf (COTS) and/or open-source hardware and software, we can now build cheap Unmanned Aerial Vehicles (UAVs). This will enable a broad spectrum of potential UAV based mobile applications. In this work, we propose a simple open UAV platform: Ard-μ-copter. Ard-μ-copter is a quadcopter built upon the open source ArduPilot [1] infrastructure library and hardware. Comparing to the many existing commercial quadcopters platforms and open source quadcopter platforms, Ard-μ-copter platform is fully open source, simple (i.e. what the "μ" stands for), and with good documentations.

NAND flash has been widely adopted as storage devices in real-time embedded systems. However, garbage collection is needed to reclaim space and introduces a lot of time overhead. As the worst system latency is determined by the worst-case execution time of garbage collection in NAND flash, it is important to optimize garbage collection so as to give a deterministic worst system latency. On the other hand, since the garbage collection does not happen very often, optimizing garbage collection should not bring too much overhead to the average system latency. This paper presents for the first time a worst-case and average-case joint optimization scheme for garbage collection in NAND flash. With our scheme, garbage collection can be postponed to the latest stage so improves the average system latency. By combining partial garbage collection and over-provisioning, our scheme can guarantee that one free block is enough to hold all pages from both write requests and valid-page copies. The experiments have been conducted on a real embedded platform and the results show that our technique can improve both worstcase and average-case system latency compared with the previous works.

Virtual block devices are widely used to provide block interface to virtual machines (VMs). A virtual block device manages an indirection mapping from the virtual address space presented to a VM, to a storage image hosted on file system or storage volume. This indirection is recorded as metadata on the image, also known as a lookup table, which needs to be immediately updated upon each space allocation on the image for data safety (also known as image growth). This growth is common as VM templates for large-scale deployments and snapshots for fast migration of VMs are heavily used. Though each table update involves only a few bytes of data, it demands a random write of an entire block. Furthermore, data consistency demands correct order of metadata and data writes be enforced, usually by inserting the FLUSH command between them. These metadata operations compromise virtual device's efficiency.

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.

Nonvolatile memory (NVM) has many benefits compared to the traditional static RAM, such as improved reliability and reduced power consumption, but it has long write latency and limited write endurance. Scratchpad memory (SPM) is software-managed small on-chip memory for improving system performance and predicability. We consider SPM based on spin-transfer torque RAM, a type of NVM with high performance and good endurance. We present algorithms for allocating data variables to SPM and distribute write activity evenly in the SPM address space, in order to achieve wear-leveling and prolong the lifetime of NVM. We present two optimization algorithms for minimizing system CPU utilization subject to NVM lifetime constraints: 1) an optimal algorithm based on ILP and 2) an efficient heuristic algorithm that can obtain close-to-optimal solutions.

The hybrid memory architecture that contains both on-chip cache and scratchpad memory (SPM) has been widely used in embedded systems. In this article, we explore this hybrid memory architecture by jointly optimizing time performance and temperature for embedded systems with loops. Our basic idea is to adaptively adjust the workload distribution between cache and SPM based on the current temperature. For a problem in which the workload can be estimated a priori, we present a nonlinear programming formulation to optimally minimize the total execution time of a loop under the constraints of SPM size and temperature. To solve a problem in which the workload is not known a priori, we propose a temperature-aware adaptive loop scheduling algorithm called TALS to dynamically allocate data to cache and SPM at runtime. The experimental results show that our algorithms can effectively achieve both performance and temperature optimization for embedded systems with cache and SPM.

Non-volatile memories such as phase change memory (PCM) and memristor are being actively studied as an alternative to DRAM-based main memory in embedded systems because of their properties, which include low power consumption and high density. Though PCM is one of the most promising candidates with commercial products available, its adoption has been greatly compromised by limited write endurance. As main memory is one of the most heavily accessed components, it is critical to prolong the lifetime of PCM. In this article, we present w rite- a ctivity-aware p age t able m anagement (WAPTM), a simple yet effective page table management scheme for reducing unnecessary writes, by redesigning system software and exploiting write-activity-aware features provided by the hardware. We implemented WAPTM in Google Android based on the ARM architecture and evaluated it with real Android applications. Experimental results show that WAPTM can significantly reduce writes in page tables, proving the feasibility and potential of prolonging the lifetime of PCM-based main memory through reducing writes at the OS level.

Due to many attractive and unique properties, NAND flash memory has been widely adopted in mission-critical hard real-time systems and some soft real-time systems. However, the nondeterministic garbage collection operation in NAND flash memory makes it difficult to predict the system response time of each data request. This article presents Lazy-RTGC , a real-time lazy garbage collection mechanism for NAND flash memory storage systems. Lazy-RTGC adopts two design optimization techniques: on-demand page-level address mappings, and partial garbage collection. On-demand page-level address mappings can achieve high performance of address translation and can effectively manage the flash space with the minimum RAM cost. On the other hand, partial garbage collection can provide the guaranteed system response time. By adopting these techniques, Lazy-RTGC jointly optimizes both the average and the worst system response time, and provides a lower bound of reclaimed free space. Lazy-RTGC is implemented in FlashSim and compared with representative real-time NAND flash memory management schemes. Experimental results show that our technique can significantly improve both the average and worst system performance with very low extra flash-space requirements.

Scratchpad memory (SPM) is a software-managed, small, on-chip form of memory. For real-time embedded systems, worst case execution time (WCET) is more important than average-case performance. We address the problem of allocating program data variables between main memory and SPM to minimize the energy consumption due to data variable accesses, while respecting a given upper bound on a program's WCET. We present an optimal branch-and-bound algorithm; and an efficient heuristic algorithm. Our approach provides a flexible framework for the designer to perform tradeoff analysis between the program WCET and the energy consumption based on application requirements.

The recent research reveals that the bit error rate of a NAND flash cell is highly dependent on the stored data patterns. In this work, we propose Data Pattern Aware (DPA) error protection technique to extend the lifespan of NAND flash based storage systems (NFSS). DPA manipulates the ratio of 1's and 0's in the stored data to minimize occurrence of the data patterns which are susceptible to bit error noise. Consequently, the NAND flash cell bit error rate is reduced, leading to system endurance extension. Our simulation result shows that, with marginal hardware and power overhead, DPA scheme can increase the NFSS lifetime by up to 4×, offering a complementing solution to other lifetime enhancement techniques like wear-leveling.

NAND flash memory has long been the dominant storage medium in mobile devices. However, power failure may occur at any time and result in loss of important data. Crash recovery therefore becomes vitally important in NAND flash memory storage systems. As flash translation layer (FTL) directly manages flash memory using various metadata, the problem of FTL crash recovery in NAND flash is how to efficiently and effectively maintain and recover the consistency of FTL metadata after system crash.

Smartphones are getting increasingly high-performance with advances in mobile processors and larger main memories to support feature-rich applications. However, the storage subsystem has always been a prohibitive factor that slows down the pace of reaching even higher performance while maintaining good user experience. Despite today's smartphones are equipped with larger-than-ever main memories, they consume more energy and still run out of memory. But the slow NAND flash based storage vetoes the possibility of swapping---an important technique to extend main memory---and leaves a system that constantly terminates user applications under memory pressure.

SUMMARY Memory accesses introduce big‐time overhead and power consumption because of the performance gap between processors and main memory. This paper describes and evaluates a technique, loop scheduling with memory access reduction (LSMAR), that replaces hidden redundant load operations with register operations in loop kernels and performs partial scheduling for newly generated register operations subject to register constraints. By exploiting data dependence of memory access operations, the LSMAR technique can effectively reduce the number of memory accesses of loop kernels, thereby improving timing performance. The technique has been implemented into the Trimaran compiler and evaluated using a set of benchmarks from DSPstone and MiBench on the cycle‐accurate simulator of the Trimaran infrastructure. The experimental results show that when the LSMAR technique is applied, the number of memory accesses can be reduced by 18.47% on average over the benchmarks when it is not applied. The measurements also indicate that the optimizations only lead to an average 1.41% increase in code size. With such small code size expansion, the technique is more suitable for embedded systems compared with prior work.Copyright © 2013 John Wiley & Sons, Ltd.

Phase change memory (PCM) has been proposed to replace NOR flash and DRAM in embedded systems because of its attractive features. However, the endurance of PCM greatly limits its adoption in embedded systems. As most embedded systems are application-oriented, we can tackle the endurance problem of PCM by exploring application-specific features such as fixed access patterns and update frequencies. In this paper, we propose an application-specific wear leveling technique, called Curling-PCM, to evenly distribute write activities across the whole PCM chip to improve the endurance of PCM in embedded systems. The basic idea is to exploit application-specific features in embedded systems and periodically move the hot region across the whole PCM chip. To reduce the overhead of moving the hot region and improve the performance of PCM-based embedded systems, a fine-grained partial wear leveling policy is proposed for Curling-PCM, by which only part of the hot region is moved during each request handling period. Experimental results show that Curling-PCM can effectively evenly distribute write traffic for a prime application of PCM in embedded systems. We expect this paper can serve as a first step toward the full exploration of application-specific features in PCM-based embedded systems.

The increasing density of NAND flash memory leads to a dramatic increase in the bit error rate of flash, which greatly reduces the ability of error correcting codes (ECC) to handle multibit errors. NAND flash memory is normally used to store the file system metadata and page mapping information. Thus, a broken physical page containing metadata may cause an unintended and severe change in functionality of the entire flash. This paper presents Meta-Cure, a novel hardware and file system interface that transparently protects metadata in the presence of multibit faults. Meta-Cure exploits built-in ECC and replication in order to protect pages containing critical data, such as file system metadata. Redundant pairs are formed at run time and distributed to different physical pages to protect against failures. Meta-Cure requires no changes to the file system, on-chip hierarchy, or hardware implementation of flash memory chip. We evaluate Meta-Cure under a real-embedded platform using a variety of I/O traces. The evaluation platform adopts dual ARM Cortex A9 processor cores with 64 Gb NAND flash memory. We have evaluated the effectiveness of Meta-Cure on the new technology file system file system. Experimental results show that the proposed technique can reduce uncorrectable page errors by 70.38% with less than 7.86% time overhead in comparison with conventional error correction techniques.

Inter-core communication introduces overheads in task schedules on Multiprocessor System-on-Chips (MPSoCs). Inter-core communication overhead not only negatively impacts the timing performance but also significantly degrades the memory usage for streaming applications running on MPSoC architectures. By minimizing inter-core communication overhead, a shorter period can be applied and system performance (e.g., throughput, memory usage) can be improved. In this paper, we focus on solving the problem of minimizing inter-core communication overhead for streaming applications on bus-based MPSoCs. The objective is to minimize inter-core communication overhead while minimizing the overall memory usage. To solve the problem, we first 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. By doing this, inter-core communication overhead can be effectively removed. To minimize the overall memory usage, we then perform schedulability analysis and obtain the bounds of the times needed to reschedule each task. Based on the schedulability analysis, we formulate the scheduling problem as an integer linear programming (ILP) model and obtain an optimal schedule. In addition, we propose a heuristic approach to efficiently obtain a near-optimal solution. We conduct experiments on a set of benchmarks from both real-life streaming applications and synthetic task graphs. The experimental results show that the proposed approach can significantly reduce the schedule length and improve the memory usage compared with the previous work.

The linear scaling down of NAND flash memory is approaching its physical, electrical, and reliability limitations. To maintain the current trend of increasing bit density and reducing bit per cost, 3-D flash memory is emerging as a viable solution to fulfill the ever-increasing demands of storage capacity. In 3-D NAND flash memory, multiple layers are stacked to provide ultrahigh density storage devices. However, the physical architecture of 3-D flash memory leads to a higher probability of disturbance to adjacent physical pages and greatly increases bit error rates. This paper presents a novel physical-location-aware address mapping strategy for 3-D NAND flash memory. It permutes the physical mapping of pages and maximizes the distance between the consecutively logical pages, which can significantly reduce the disturbance to adjacent physical pages and effectively enhance the reliability. The proposed mapping strategy is applied to a representative flash storage system. Experimental results show that the proposed scheme can reduce uncorrectable page errors by 70.16% with less than 10.01% space overhead in comparison with the baseline scheme.

Phase change memory (PCM) has been used as NOR flash replacement in embedded systems with its attractive features. However, the endurance of PCM keeps drifting down and greatly limits its adoption in embedded systems. As most embedded systems are application-oriented, we can better utilize PCM by exploring application-specific features such as fixed access patterns and update frequencies to prolong the lifetime of PCM. In this paper, we propose an application-specific wear leveling technique, called Curling-PCM, to evenly distribute write activities across the PCM chip in order to improve the endurance of PCM. The basic idea is to exploit application-specific features in embedded systems and periodically move the hot region across the whole PCM chip. To further reduce the overhead of moving the hot region and improve the performance of PCM-based embedded systems, a fine-grained partial wear leveling policy is proposed in Curling-PCM, by which only part of the hot region is moved during each request handling period. The experimental results show that Curling-PCM can effectively evenly distribute write traffic in PCM chips compared with previous work. We expect this work can serve as a first step towards the full exploration of application-specific features in PCM-based embedded systems.

Address mapping is one of the major functions in managing NAND flash. With the capacity increase of NAND flash, it becomes vitally important to reduce the RAM print of the address mapping table while not introducing big performance overhead. Demand-based address mapping is an effective approach to solve this problem, in which the address mapping table is stored in NAND flash (called translation pages), and mapping items are cached on-demand in RAM. Therefore, it is critical to manage translation pages in demand-based address mapping. This paper solves two most important problems in translation page management. First, to reduce frequent translation page updates caused by data requests, we propose a page-level caching mechanism to exploit the fundamental property of NAND flash where the basic read/write unit is one page. Second, to reduce the garbage collection overhead from translation pages, we propose a multiple write pointers strategy to group data pages corresponding to the same translation page into one data block, by which, when the data block is reclaimed via the garbage collection, we only need to update one translation page. We evaluate our scheme using a set of benchmarks from both real-world and synthetic traces. Experimental results show that our techniques can achieve significant reduction in the extra translation operations and improve the system response time.

Log-block-based FTL (Flash Translation Layer) schemes have been widely used to manage NAND flash memory storage systems in industry. In log-block-based FTLs, a few physical blocks called log blocks are used to hold all page updates from a large amount of data blocks. Frequent page updates in log blocks introduce big overhead so log blocks become the system bottleneck.

NAND flash memory has been widely used to build embedded devices such as smartphones and solid state drives (SSD) because of its high performance, low power consumption, great shock resistance and small form factor. However, its lifetime and performance are greatly constrained by partial page updates, which will lead to early depletion of free pages and frequent garbage collections. On the one hand, partial page updates are prevalent as a large portion of I/O does not modify file contents drastically. On the other hand, general-purpose cache usually does not specifically consider and eliminate duplicated contents, despite its popularity.

With many advantages like low cost, faster and non-volatile, NAND flash memory has become a critical component in building security-critical real-time embedded devices. In this paper, we are interested in online optimization of security-sensitive storage applications, whose workloads are unpredictable but have explicit deterministic or probabilistic timing constraints and certain security constraints. Sensitive data must be stored before a specific deadline, otherwise it will lose its validity. To address these challenges, this paper presents a Feedback Vulnerability and Utilization Control (FVUC) mechanism. FVUC employs two proportional-integral controllers, the Utilization Controller and Vulnerability Controller, to build a big feedback loop that dynamically monitors the system run-time status as well as decides how many flash pages would be encrypted by a cryptography algorithm. Relied on the accurate model and design, FVUC can make a balance between the utilization and vulnerability, and achieve a better overall performance. The advantages of FVUC are verified by a series of simulation experiments under a broad range of system configurations and run-time uncertainties.

In this paper, we target at the direct-coupled solar energy powered multicore architectures that provide direct power supply between photovoltaic (PV) generation and the load without the adoption of battery. We present Solar-Tune, a real-time scheduling technique with load tuning for sporadic tasks on solar energy powered multicore systems. The objective is to fully utilize the available solar energy while meeting the deadlines of tasks. To solve the problem, we first perform analysis and formulate the scheduling problem in each duration as an integer linear programming (ILP) model to obtain an optimal schedule. Then we present a heuristic algorithm to dynamically refine the task scheduling based on the predictions of the availability of solar energy. We conduct experiments using real-world meteorological data across different geographic sites. The experimental results show that SolarTune can significantly improve the solar energy utilization ratio and reduce the number of deadline misses compared to the conventional task scheduler.

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.

Due to its low power consumption and high density, phase change memory (PCM) becomes a promising main-memory alternative to DRAM in embedded systems. PCM, however, has the endurance problem in which the number of rewrites to each cell is quite limited compared with DRAM. Therefore, it is fundamental to eliminate unnecessary writes in PCM-based embedded systems. This paper presents a simple yet effective scheme to solve this problem, through redesigning existing software to exploit write-activity-aware features provided by underlying hardware. Particularly, we target at page table management, a key kernel component residing in the memory management part of the Linux kernel. We present for the first time a write-activity-aware page table management scheme, WAPTM, accomplished through two modifications to the page table initialization and page frame allocation process. The scheme has been implemented in Google Android 2.3 based on ARM architecture and evaluated with real applications on the Android emulator. The experimental results show that the proposed scheme can significantly reduce write activities to page tables in the new kernel compared with the original Android. We hope this work can serve as a first step towards the design of write-activity-aware operating systems via simple and feasible modifications.

The increasing density of NAND flash memory leads to a dramatic increase in the bit error rate of flash, which greatly reduces the ability of error correcting codes (ECC) to handle multi-bit errors. To ensure the functionality and reliability of flash memory, the pages containing address mapping information and other metadata should be carefully stored in flash memory. This paper presents Meta-Cure, a novel hardware and file system interface that transparently protects metadata in the presence of multi-bit faults. Meta-Cure exploits built-in ECC and replication in order to protect pages containing critical data. Redundant pairs are formed at run time and distributed to different physical pages to protect against failures. Meta-Cure requires no changes to the file system, on-chip hierarchy, or hardware implementation of flash memory chip. Experimental results show that the proposed technique can reduce uncorrectable page errors by 92% with less than 1% space overhead in comparison with conventional error correction techniques.

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.

Three-dimensional (3D) flash memory is emerging to fulfil the ever-increasing demands of storage capacity. In 3D NAND flash memory, multiple layers are stacked to increase bit density and reduce bit cost of flash memory. However, the physical architecture of 3D flash memory leads to a higher probability of disturbance to adjacent physical pages and greatly increases bit error rates. This paper presents 3D-FlashMap, a novel physical-location-aware block mapping strategy for three-dimensional NAND flash memory. 3D-FlashMap permutes the physical mapping of blocks and maximizes the distance between consecutively logical blocks, which can significantly reduce the disturbance to adjacent physical pages and effectively enhance the reliability. We apply 3D-FlashMap to a representative flash storage system. Experimental results show that the proposed scheme can reduce uncorrectable page errors by 85% with less than 2% space overhead in comparison 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.

Loops are the main source of parallelism in many applications. This paper solves the open problem of extracting the maximal number of iterations from a loop to run parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on dependence cycles in two phases. First, we model dependence migration with retiming and formulate this classic loop parallelization into a graph optimization problem, i.e., one of finding retiming values for its nodes so that the minimum nonzero edge weight in the graph is maximized. We present our algorithm in three stages with each being built incrementally on the preceding one. Second, the optimal code for a loop is generated from the retimed graph of the loop found in the first phase. We demonstrate the effectiveness of our optimal algorithm by comparing with a number of representative nonoptimal algorithms using a set of benchmarks frequently used in prior work and a set of graphs generated by TGFF.

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.

Abstract Scratch‐pad memory (SPM), a small, fast, software‐managed on‐chip SRAM (Static Random Access Memory) is widely used in embedded systems. With the ever‐widening performance gap between processors and main memory, it is very important to reduce the serious off‐chip memory access overheads caused by transferring data between SPM and off‐chip memory. In this paper, we propose a novel compiler‐assisted technique, ISOS (Iteration‐access‐pattern‐based Space Overlapping SPM management), for dynamic SPM management with DMA (Direct Memory Access). In ISOS, we combine both SPM and DMA for performance optimization by exploiting the chance to overlap SPM space so as to further utilize the limited SPM space and reduce the number of DMA operations. We implement our technique based on IMPACT and conduct experiments using a set of benchmarks from DSPstone and Mediabench on the cycle‐accurate VLIW simulator of Trimaran. The experimental results show that our technique achieves run‐time performance improvement compared with the previous work. The average improvements are 13.15, 19.05, and 25.52% when the SPM sizes are 1KB, 512 bytes, and 256 bytes, respectively. Copyright © 2010 John Wiley & Sons, Ltd.

In this paper, we propose to implement hybrid operating systems based on two-level hardware interrupts. We analyze and model the worst-case real-time interrupt latency for RTAI and identify the key component for its optimization. Then, we propose our methodology to implement hybrid operating systems with two-level hardware interrupts by combining the real-time kernel and the time sharing OS (Operating System) kernel. Based on the methodology, we discuss the important issues for the implementation. Finally, we implement a hybrid system called RTLinux-THIN (Real-Time LINUX with Two-level Hardware INterrupts) on the ARM architecture by combining ARM Linux kernel 2.6.9 and μC/OS-II. We conduct experiments on a set of real application programs including mplayer, Bonnie, and iperf, and compare the interrupt latency and interrupt task distributions for RTLinux-THIN (with and without cache locking), RTAI, Linux, and Linux with RT patch on a hardware platform based on Intel PXA270 processor. The results show that our scheme not only provides an easy method for implementing hybrid systems but also achieves the performance improvement for both the time sharing and real-time subsystems.

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.

Reducing memory accesses is particularly important for digital signal processing (DSP) applications since they are widely used in embedded systems and need to be executed with high performance and low power consumption. In this paper, we propose a machine-independent loop memory access optimization technique, redundant load exploration and migration (REALM), to explore hidden redundant load operations and migrate them outside loops based on loop-carried data dependence analysis. We implement REALM into IMPACT and Trimaran. To the best of our knowledge, this is the first work to implement the memory access reduction with loop-carried data reuse in real world compilers. We conduct experiments using a set of benchmarks from DSPstone and MiBench on the cycle-accurate VLIW simulator of Trimaran. The experimental results show that our technique significantly reduces the number of memory accesses.

High performance using minimal resources has become a serious problem for digital signal processing (DSP) applications. The number of addressable registers is a significant obstacle for centralized architecture achieving high performance of DSP applications. In this paper, we propose a novel cluster based architecture synthesis algorithm, using minimal resources with time and register constraints, which adds a new cluster rather than inserts memory operations when registers are inadequate. By counting the register, inter-cluster communications and function units requirements during scheduling, the cluster with optimal performance is selected to schedule every instruction of the application. The redundant resources of the initial configuration obtained by our algorithm are further optimized. The experiments demonstrate that, compared with the centralized architecture synthesis, our approach achieves up to 224% improvement in success rate for general cases and up to 369% improvement for cases with tight constraints, and effectively reduces the resources usage.

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.

Abstract In this paper, we propose an effective data pipelining technique, SPDP (Scratch‐Pad Data Pipelining), for dynamic scratch‐pad memory (SPM) management with DMA (Direct Memory Access). Our basic idea is to overlap the execution of CPU instructions and DMA operations. In SPDP, based on the iteration access patterns of arrays, we group multiple iterations into a block to improve the data locality of regular array accesses. We allocate the data of multiple iterations into different portions of the SPM. In this way, when the CPU executes instructions and accesses data from one portion of the SPM, DMA operations can be performed to transfer data between the off‐chip memory and another portion of SPM simultaneously. We perform code transformation to insert DMA instructions to achieve the data pipelining. We have implemented our SPDP technique with the IMPACT compiler, and conduct experiments using a set of loop kernels from DSPstone, Mibench, and Mediabench on the cycle‐accurate VLIW simulator of Trimaran. The experimental results show that our technique achieves performance improvement compared with the previous work. Copyright © 2010 John Wiley & Sons, Ltd.

The widening gap between processor and memory performance is the main bottleneck for modern computer systems to achieve high processor utilization. To hide memory latency, a variety of techniques have been proposed—from intermediate fast memories (caches) to various prefetching and memory management techniques. In this article, we propose a new loop scheduling with memory management technique, Iterational Retiming with Partitioning (IRP), that can completely hide memory latencies for applications with multidimensional loops on architectures like CELL processor. In IRP, the iteration space is first partitioned carefully. Then a two-part schedule, consisting of processor and memory parts, is produced such that the execution time of the memory part never exceeds the execution time of the processor part. These two parts are executed simultaneously and complete memory latency hiding is reached. In this article, we prove that such optimal two-part schedule can always be achieved given the right partition size and shape. Experiments on DSP benchmarks show that IRP consistently produces optimal solutions as well as significant improvement over previous techniques.

With the shrinking of technology feature sizes, the share of leakage in total power consumption of digital systems continues to grow. Traditionaldynamic voltage scaling(DVS) fails to accurately address the impact of scaling on system power consumption as the leakage power increases exponentially. The combination of DVS andadaptive body biasing(ABB) is an effective technique to jointly optimize dynamic and leakage energy dissipation. In this paper, we propose an optimal soft real-time loop scheduling and voltage assignment algorithm,loop scheduling and voltage assignment to minimize energy, to minimize both dynamic and leakage energy via DVS and ABB. Voltage transition overhead has been considered in our approach. We conduct simulations on a set of digital signal processor benchmarks based on the power model of 70 nm technology. The simulation results show that our approach achieves significant energy saving compared to that of the integer linear programming approach.

This paper solves the open problem of extracting the maximal number of iterations from a loop that can be executed in parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on dependence cycles in two phases. First, we model dependence migration with retiming and formulate this classic loop parallelization into a graph optimization problem, i.e., one of finding retiming values for its nodes so that the minimum non-zero edge weight in the graph is maximized. We present our algorithm in three stages with each being built incrementally on the preceding one. Second, the optimal code for a loop is generated from the retimed graph of the loop found in the first phase. We demonstrate the effectiveness of our optimal algorithm by comparing with a number of representative non-optimal algorithms using a set of benchmarks frequently used in prior work.

In this paper, we develop a compiler-assisted thermal-aware data allocation algorithm to improve the reliability of embedded systems with cache and SPM (scratch-pad memory). Our basic idea is to distribute the workload evenly between the cache and SPM in order to alleviate the temperature hot spots in the on-chip memory system. In the algorithm, considering the size of SPM, we first divide the loop iterations into two parts, and put the accessed data of the first part into SPM. Then we perform code transformation based on the partitioning of iterations. By alternatively using the data cache and SPM, the peak temperature is reduced. We implement our technique and simulate them using the Trimaran infrastructure with power models for cache and SPM, and the thermal simulator, HotSpot, on a set of benchmarks from DSPstone and MiBench. The experimental results show that our technique can significantly improve the reliability of the on-chip memory system.

Loops are the most important sections for embedded applications. To achieve high performance, two loop transformation techniques are often applied, namely loop pipelining and loop partitioning, loop pipelining is an effective approach to increase parallelism and reduce schedule length. Loop partitioning with prefetching increases data locality and hides memory latency. However, loop pipelining increases register pressure and loop partitioning increases local memory requirement. As most embedded systems have limited number of registers and limited memory, without careful study, these two techniques can not be applied effectively. In this paper, we propose an effective scheduling framework, Register and Memory Sensitive Partition-ing(RMSP), to minimize average schedule length per iteration under register and memory dual constraints for parallel embedded systems. Experiments show that RMSP reduces schedule length by 14.1% in average compared to previous methods applied directly.

In this paper, we focus on joint energy and performance optimization for streaming applications on multiprocessor systems-on-chip by combining task-level coarse-grained software pipelining with DVS (dynamic voltage scaling)and DPM (dynamic power management) techniques with the considerations of transition overhead, inter-processor 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 based on the retiming technique[19]. In the second phase, we propose a novel scheduling algorithm called SpringS that works like a spring by iteratively adjusting task scheduling and voltage selection by combining DVS and DPM. We conduct experiments with a set of benchmarks from E3S [10] and TGFF [27]. The experimental results show that our technique can achieve 49:8% energy saving on average compared with the approach in [20], that applied DVS and DPM without software pipelining. In addition, given a tight timing constraint, our technique can obtain a feasible solution while the approach in [20] cannot.

As MOSFETs (metal-oxide-semiconductor field effect transistor) dimensions enter the sub-micrometer region, reducing leakage power becomes a significant issue of VLSI industry. In this paper, we propose a novel prediction approach to predict idleness of functional units for leakage energy management. Using a state-based predictor, historical utilization information of functional units is exploited to adjust the state of the predictor so as to enhance the accuracy of prediction. We implement our approach based on SimpleScalar and conduct experiments with a suite of fourteen benchmarks from Trimaran. The experimental results show that our approach achieves the better results compared with the previous work.

Multiple memory banks design is employed in many high performance DSP processors. This architectural feature supports higher memory bandwidth by allowing multiple data memory access to be executed in parallel. Dedicated address generation units (AGUs) are commonly presented in DSPs to perform address arithmetic in parallel to the main datapath. Address assignment, optimization of memory layout of program variables to reduce address arithmetic instruction, has been studied extensively on single memory architecture. Make effective use of AGUs on multiple memory banks is a great challenge to compiler design and has not been studied previously. In this paper, we exploit address assignment with variable partitioning for scheduling on DSP architectures with multiple memory banks and AGUs. Our approach is built on novel graph models which capture both parallelism and serialism demands. An efficient scheduling algorithm, Address Assignment Sensitive Variable Partitioning (AASVP), is proposed to best leverage both multiple memory banks and AGUs. Experimental results show significant improvement compare to existing methods.

As a distributed computing system, a CNC system needs to be operated reliably, dependably and safely. How to design reliable and dependable software and perform effective verification for CNC systems becomes an important research problem. In this paper, we propose a new modeling method called TTM/ATRTTL (Timed Transition Models/All-Time Real-Time Temporal Logics) for specifying CNCsystems. TTM/ATRTTL provides full supports for specifying hard real-time and feedback that are needed for modeling CNC systems. We also propose a verification framework with verification rules and theorems and implement it with STeP and SF2STeP. The proposed verification framework can check reliability, dependability and safety of systems specified by our TTM/ATRTTL method. We apply our modeling and verification techniques on an open architecture CNC (OAC) system and conduct comprehensive studies on modeling and verifying a logical controller that is the key part of OAC. The results show that our method can effectively model and verify CNC systems and generate CNC software that can satisfy system requirements in reliability, dependability and safety.

Minimizing energy consumption is a key issue in designing real-time applications on wireless embedded systems. While a lot of work has been done to manage energy consumption on single processor real-time system, few work addresses network-wide energy consumption management for real-time tasks. Moreover, existing work on network-wide energy consumption assumes that the underlying network is always connected, which is not consistent with the practice in which wireless nodes often turn off their network interfaces in asleep schedule to reduce energy consumption. In this paper, we propose solutions to minimize network-wide energy consumption for real-time tasks with precedence constraints executing on wireless embedded systems. Our solutions take the radio sleep scheduling of wireless nodes into account when adjusting the execution modes of processors. We also propose a runtime dynamic energy management scheme to further reduce energy consumption while guaranteeing the timing constraint. The experiments show that our approach significantly reduces total energy consumption compared with the previous work.

In networked embedded sensor systems, data fusion is a viable solution to significantly reduce energy consumption while achieving real-time guarantee. Emerging data fusion applications demand efficient task allocation and scheduling techniques. However, existing approaches can not be effectively applied concerning both network topology and wireless communications. In this paper, we formally model TATAS, the topology-aware task allocation and scheduling problem for real-time data fusion applications, and show it is NP-complete. We also propose an efficient three-phase heuristic to solve the TATAS problem. We implement our technique and conduct experiments based on a simulation environment. Experimental results show that, as compared with traditional approaches, our technique can achieve significant energy saving and effectively meet the real-time requirements as well.

In this paper, we develop a novel real-time instruction-level loop scheduling technique to reduce leakage energy consumption for applications with loops on VLIW architecture. We first prove that the scheduling problem with the minimum leakage energy consumption within a timing constraint is NP-complete. Then, LEMLS (leakage energy minimization loop scheduling) algorithm is designed to repeatedly regroup a loop based on rotation scheduling (Chao et al., 1997), and decrease leakage energy integrating with leakage power reduction mechanism. We conduct experiments on a set of DSP benchmarks based on the power model of the VLIW processors in (Liao et al., 2002). The results show that our algorithm achieves significant leakage energy saving compared with list scheduling and the algorithm in (You et al., 2006).

In this paper, we propose to implement hybrid operating systems based on two-level hardware interrupts. To separate real-time and non-real-time hardware interrupts by hardware, we show that it is easier to build up hybrid systems with better performance. We analyze and discuss the key issues for implementing a hybrid system based on this and implement a hybrid system called RTLinux-THIN (Real-Time LINUX with Two-level Hardware Interrupts) on the ARM architecture by combining ARM Linux kernel 2.6.9 and muC/OS-II. We conduct experiments on a set of real application programs including mplayer [20], Bonnie [4] and iperf [13] and compare the interrupt latency distributions for RTLinux-THIN (with and without cache locking), RTAI and Linux on a hardware platform based on Intel PXA270processor [12]. The experimental results show that RTLinux-THIN improves real-time interrupt latencies and provides better predictability.

Low energy consumption is an important problem in real-time embedded systems and loop is the most energy consuming part in most cases. Due to the uncertainties in execution time of some tasks, this paper models each varied execution time as a probabilistic random variable. We use rotation scheduling and DVS (Dynamic Voltage Scaling) to minimize the expected total energy consumption while satisfying the timing constraint with a guaranteed confidence probability. Our approach can handle loops efficiently. In addition, it is suitable to both soft and hard real-time systems. And even for hard real-time, we have good results.

With more embedded systems networked, it becomes an important problem to effectively defend embedded systems against buffer overflow attacks. Due to the increasing complexity and strict requirements, off-the-shelf software components are widely used in embedded systems, especially for military and other critical applications. Therefore, in addition to effective protection, we also need to provide an approach for system integrators to efficiently check whether software components have been protected. In this paper, we propose the HSDefender (Hardware/Software Defender) technique to perform protection and checking together. Our basic idea is to design secure call instructions so systems can be secured and checking can be easily performed. In the paper, we classify buffer overflow attacks into two categories and provide two corresponding defending strategies. We analyze the HSDefender technique with respect to hardware cost, security, and performance. We experiment with our HSDefender technique on the simplescalar/ARM simulator with benchmarks from MiBench, an embedded benchmark suite. The results show that our HSDefender technique can defend a system against more types of buffer overflow attacks with less overhead compared with the previous work.

In embedded systems, high-performance DSP needs to be performed not only with high-data throughput but also with low-power consumption. This article develops an instruction-level loop-scheduling technique to reduce both execution time and bus-switching activities for applications with loops on VLIW architectures. We propose an algorithm, SAMLS (Switching-Activity Minimization Loop Scheduling), to minimize both schedule length and switching activities for applications with loops. In the algorithm, we obtain the best schedule from the ones that are generated from an initial schedule by repeatedly rescheduling the nodes with schedule length and switching activities minimization based on rotation scheduling and bipartite matching. The experimental results show that our algorithm can reduce both schedule length and bus-switching activities. Compared with the work of Lee et al. [2003], SAMLS shows an average 11.5% reduction in schedule length and an average 19.4% reduction in bus-switching activities.

This paper addresses high level synthesis for realtime digital signal processing (DSP) architectures using heterogeneous functional units (FUs). For such special purpose architecture synthesis, an important problem is how to assign a proper FU type to each operation of a DSP application and generate a schedule in such a way that all requirements can be met and the total cost can be minimized. In the paper, we propose a two-phase approach to solve this problem. In the first phase, we propose an algorithm to assign proper FU types to applications such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained in the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. The experimental results show that our approach can generate high-performance assignments and schedules with great reduction on total cost compared with the previous work.

Reducing address arithmetic instructions by optimization of address offset assignment greatly improves the performance of DSP applications. However, minimizing address operations alone may not directly reduce code size and schedule length for multiple functional units DSPs. In this paper, we exploit address assignment and scheduling for application with loops on multiple functional unit DSPs. Array transformation is used in our approach to leverage the indirect addressing modes provided by most of the DSP architectures. An algorithm, address instruction reduction loop scheduling (AIRLS), is proposed. The algorithm utilizes the techniques of rotation scheduling, address assignment and array transformation to minimize both address instructions and schedule length. Compared to the list scheduling, AIRLS shows an average reduction of 35.4% in schedule length and an average reduction of 38.3% in address instructions. Compared to the rotation scheduling, AIRLS shows an average reduction of 19.2% in schedule length and 39.5% in the number of address instructions.

This paper addresses high level synthesis for real-time digital signal processing (DSP) architectures using heterogeneous functional units (FUs). For such special purpose architecture synthesis, an important problem is how to assign a proper FU type to each operation of a DSP application and generate a schedule in such a way that all requirements can be met and the total cost can be minimized. We propose a two-phase approach to solve this problem. In the first phase, we solve the heterogeneous assignment problem, i.e., how to assign proper FU types to applications such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained in the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. We prove that the heterogeneous assignment problem is NP-complete. Efficient algorithms are proposed to find an optimal solution when the given DFG is a simple path or a tree. Three other algorithms are proposed to solve the general problem. The experiments show that our algorithms can effectively reduce the total cost compared with the previous work.

Loop fusion is commonly used to improve the instruction-level parallelism of loops for high-performance embedded computing systems. Loop fusion, however, is not always directly applicable because the fusion prevention dependencies may exist among loops. Most of the existing techniques still have limitations in fully exploiting the advantages of loop fusion. In this paper, we present a general loop fusion technique for loops or nested loops based on the loop dependency graph model, retiming, and multi-dimensional retiming concepts. We show that any "J+K" model loop can be legally fused using our legalizing fusion technique. Polynomial-time algorithms are developed to solve the loop fusion problem for "J+K" model loops considering both timing and code size of the final code. Our technique produces the final code and calculates the resultant code size directly from the retiming values. The experimental results show that our loop fusion technique always significantly reduces the schedule length.

Previous approaches for the shortest path tree (SPT) dynamic update have mainly focused on the case of one link state change. Little work has been done on the problem of deriving a new SPT based on its old one for multiple link state decrements in a network that applies link-state routing protocols. The complexity of this problem comes from there being no accurate boundary of nodes to be updated in an updating process and that multiple decrements can be accumulated. Two dynamic algorithms (MaxR, MinD) are proposed to reduce the times for node updating. Compared with other algorithms for the SPT update of multiple edge weight decrements, our algorithms yield fewer times for node updates during the dynamic update process. Such an achievement is attained by the mechanism of part node updating in a branch on the SPT after a particular node selection from a built node list. Simulation results are given to show our improvements.

Software pipelining for nested loops remains a challenging problem for embedded system design. The existing software pipelining techniques for single loops can only explore the parallelism of the innermost loop, so the final timing performance is inferior. While multidimensional (MD) retiming can explore the outer loop parallelism, it introduces large overheads in loop index generation and code size due to transformation. We use MD retiming to model the software pipelining problem of nested loops. We show that the computation time and code size of a software-pipelined loop nest is affected by execution sequence and retiming function. The algorithm of software pipelining for nested loops technique (SPINE) is proposed to generate fully parallelized loops efficiently with the overheads as small as possible. The experimental results show that our technique outperforms both the standard software pipelining and MD retiming significantly.

Summary form only given. In high level synthesis for real-time digital signal processing (DSP) architectures using heterogeneous functional units (FUs), an important problem is how to assign a proper fit type to each operation of a DSP application and generate a schedule in such a way that all requirements can be met and the total cost can be minimized. We propose a two-phase approach to solve this problem. In the first phase, we solve heterogeneous assignment problem, i.e., how to assign a proper FU type to a DSP application such that the total cost can be minimized while the timing constraint is satisfied. In the second phase, based on the assignments obtained from the first phase, we propose a minimum resource scheduling algorithm to generate a schedule and a feasible configuration that uses as little resource as possible. We prove heterogeneous assignment problem is NP-complete and propose several algorithms to solve it. The experiments show that algorithm DFG-assign-repeat is the best that gives a reduction of 25.7% on total cost compared with the previous work.

Buffer over-flow attacks have been causing serious security problems for decades. With more embedded systems networked, it becomes an important research problem to defend embedded systems against buffer overflow attacks. We propose the hardware/software address protection (HSAP) technique to solve this problem. We first classify buffer overflow attacks into two categories (stack smashing attacks and function pointer attacks) and then provide two corresponding defending strategies. In our technique, hardware boundary check method and function pointer XOR method are used to protect a system against stack smashing attacks and function pointer attacks, respectively. Although the focus of the HSAP technique is on embedded systems because of the availability of hardware support, we show that the HSAP technique is applied to any type of processors to defend against buffer overflow attacks. We use four classes of processors to illustrate that the applicability of our technique is independent of architectures. We experiment with our HSAP technique in ARM Evaluator-7T simulation development environments. The results show that our HSAP technique defends a system against more types of buffer overflow attacks with little overhead.

Code size expansion of software-pipelined loops is a critical problem for DSP systems with strict code size constraint. Some ad-hoc code size reduction techniques were used to try to reduce the prologue/epilogue produced by software pipelining. We present the fundamental understanding of the relationship between code size expansion and software pipelining. Based on the retiming concept, we present a powerful Code-size REDuction (CRED) technique and its application on various kinds of processors. We also provide CRED algorithms integrated with the software pipelining process. One advantage of our algorithms is that it can explore the trade-off space between "perfect" software pipelining and constrained code size. That is, the software pipelining process can be controlled to generate a schedule concerned with code size requirement. The experiment results show the effectiveness of our algorithms in both reducing the code size for software-pipelined loops and exploring the code size/performance trade-off space.