As robotic manipulators adopt increasingly higher degrees of freedom (DoFs) to handle complex tasks, the corresponding growth in neural network (NN) size leads to substantial memory and energy demands, making deployment on low-level controllers increasingly impractical. To overcome this challenge, we propose STAR, a novel framework that enables accurate and energy-efficient high-DoF manipulation under strict memory constraints. STAR introduces a spherical task-space approximation strategy to mathematically formulate the manipulator’s reachable space, followed by a memory-aware training algorithm that adaptively divides this space into smaller, manageable regions, with each partition assigned a lightweight NN optimized to satisfy memory capacity while preserving high precision. Specifically, STAR employs deep reinforcement learning (DRL) to learn absolute pose-to-joint mappings, allowing each task to be completed with a single NN load, eliminating the need for large networks or frequent NN switching. Experiments demonstrate that STAR achieves up to 8.09× faster execution and 10.93× lower energy consumption, while reducing memory usage by up to 128× compared to state-of-the-art approaches, all without compromising control accuracy.

Point-based networks achieve high accuracy by preserving the intrinsic spatial structure of point clouds. The spatial information is effectively extracted by set abstraction, a critical module for feature learning in point-based networks. However, set abstraction introduces a computational bottleneck, and naive parallelization often degrades sampling quality, leading to accuracy loss. To address these challenges, we propose Parallel-SA, a framework that accelerates point-based networks by transforming set abstraction from sequential to parallel processing without sacrificing accuracy. Parallel-SA leverages a multi-scale sampling distribution approximation to preserve sampling quality under parallel execution. In addition, it employs distribution-aware balanced partitioning and adaptive load-balancing refinement to further improve efficiency. Experiments show that Parallel-SA achieves an average 2.38× speedup in set abstraction with minimal accuracy degradation.

Numerous data-intensive applications benefit from offloading data processing to storage devices, typically Computational Storage Devices (CSD). Co-locating requests from diverse applications to one CSD offers better performance and power efficiency than dedicating CSDs to a single application. However, current CSD scheduling frameworks struggle to effectively manage contention among CPU, flash I/O, and buffer resources across requests due to less consideration in their inter-dependencies. This paper proposes REMUS, a CSD scheduling framework handling multiple requests for commercial SSD with multiple homogeneous cores. The key idea of REMUS is to allocate workloads across multiple cores based on the distribution of the Logical Block Address (LBA) of requests, and to mitigate stall time by sorting requests according to their urgency for resources, where urgency is quantified by each request’s remaining buffer capacity. Furthermore, a request batching scheme that intelligently groups the requests to be scheduled according to their characteristics is proposed to provide congestion control for REMUS and to minimize the contention it introduces. We conduct experiments on both a simulator and a real CSD platform. The experiment results show that REMUS improved throughput by 1.51× on the simulator and 1.39× on the real platform on average compared to the baselines.

Vector Similarity Search (VSS) on edge devices is increasingly essential for data privacy but faces substantial latency and energy overhead due to frequent data transfers between storage and DRAM. To address these challenges, we propose the Intelligent Cognition Engine (ICE), a fully digital non-volatile in-memory computing (nvIMC) framework designed for integration with commercial 3DnandFlash. ICE avoids the use of analog-digital conversion (ADC/DAC) and reduces data movement by performing vector similarity computation directly withinnandstorage. Key architectural components include a digital page multiplier, a two’s-complement accumulator that supports signed computation with minimal circuit modification, and a hierarchical Top-N search strategy to reduce unnecessary data accesses. The proposed framework is evaluated through a combination of post-layout circuit simulations, representative silicon measurements, and system-level modeling on edge platforms. Experimental results indicate that ICE can achieve 17.8–$122.6\times $speedup and 11.5–$162\times $improvement in energy efficiency compared to conventional von Neumann-based approaches, demonstrating the feasibility and scalability of fully digital 3Dnand-based nvIMC for edge AI workloads.

Tree-based model remains state-of-the-art for many tasks involving tabular data. While these models are favored in resource-constrained environments, the inherent characteristics result in inefficiency during inference, posing significant challenges for conventional accelerators. Recent research has achieved unprecedented acceleration with content-addressable memory (CAM), yet at the cost of overwhelming memory consumption with low utilization, which is impractical for numerous real-world applications. This work addresses these issues by introducing an end-to-end framework RETENTION. RETENTION incorporates (1) a pruning algorithm to minimize model complexity under a user-specified accuracy loss tolerance, and (2) two data placement strategies to enhance memory utilization and further reduce capacity requirement. Experiment results show that space efficiency can be improved from 4.35× to 207.12× with less than 3% accuracy loss.

Neural image compression, necessary in various machine-to-machine communication scenarios, suffers from its heavy encode-decode structures and inflexibility in switching between different compression levels. Consequently, it raises significant challenges in applying the neural image compression to edge devices that are developed for powerful servers with high computational and storage capacities. We take a step to solve the challenges by proposing a new transformer-based edge-computefree image coding framework called Easz. Easz shifts the computational overhead to the server, and hence avoids the heavy encoding and model switching overhead on the edge. Easz utilizes a patch-erase algorithm to selectively remove image contents using a conditional uniform-based sampler. The erased pixels are reconstructed on the receiver side through a transformer-based framework. To further reduce the computational overhead on the receiver, we then introduce a lightweight transformer-based reconstruction structure to reduce the reconstruction load on the receiver side. Extensive evaluations conducted on a realworld testbed demonstrate multiple advantages of Easz over existing compression approaches, in terms of adaptability to different compression levels, computational efficiency, and image reconstruction quality.

As a fundamental perception task, 3D point cloud detection has become essential for applications in autonomous driving and robotics. However, point cloud detection faces significant challenges of high computational cost due to complex point processing operations. To address this issue, we propose DAWN, an acceleration framework for point cloud object detection that identifies partial similarities between adjacent frames and reduces computational cost by filtering redundant points. DAWN uses object-aware partitioning that defines boundaries based on previous detection results for localized similarity analysis. Additionally, it applies axis-sorted point selection to refine partitioning for point clouds with non-uniform distribution. An efficient 3D similarity algorithm then filters redundant points to reduce computational load. DAWN enables flexible latencyaccuracy trade-offs by tuning point filtering ratios. Experimental results show that DAWN achieves a $1.59 \times$ average speedup and up to $1.70 \times$ on state-of-the-art detection networks by filtering more than $50 \%$ of points on average, with negligible impact on accuracy.

The effective utilization of graph structures relies on obtaining high-quality graph embeddings. Traditional embedding algorithms, such as DeepWalk and Node2Vec, which rely on random walk sampling, encounter significant challenges when applied to large-scale graphs due to the substantial data transfer demands between storage and memory. To address these limitations, we propose AridWalk, which enables a Computational Storage Device (CSD) to perform random walks directly at the storage level, minimizing external data transfers by only transferring essential data. To address the constraints of limited computational resources in the CSD, AridWalk is designed to maximize DRAM utilization while significantly reducing internal data movements, specifically between internal DRAM and flash memory. Experimental results demonstrate that AridWalk substantially decreases internal data movement, providing an efficient and scalable solution for conducting in-storage random walks on large graphs.

Ensuring relative consistency in executing temporal queries to access real-time sensor data streams maintained in a database is a challenging problem, particularly when data transmission delays are lengthy and highly variable. Due to the unordered arrivals of sensor data, the databases may contain numerous open data versions (ODVs) with undefined validity intervals. Accessing ODVs may violate the relative consistency requirements of temporal queries, resulting in incorrect results. Although the Re-execution with Every Update (REU) method can resolve this issue, it may introduce heavy re-execution costs and significant delays in query completion. In this article, we study the problem of retrieving data items with temporal consistency requirements in a multi-data-stream database. To balance response time and meet the relative consistency requirements of queries, we introduce an enhanced REU mechanism called Re-Execution with Deadline (RED). Moreover, we propose a novel optional mechanism called Backward Execution Option (BEO) for temporal queries to achieve relative consistency in their execution with quick results by relaxing the data freshness constraints. By combining RED with BEO, we formulate the Repeated BEO (RBEO) to further reduce the query response time. We extend the timestamped key-value store MVLevelDB into MVLevelDB + to implement the proposed mechanisms. To reduce the query re-execution cost as required in RED and REU, we designed the Query Pool with Execution State (QpES) mechanism to achieve relative consistency in query execution with lower checking overhead and only one re-execution. We conducted extensive evaluation experiments on MVLevelDB + using benchmark programs to illustrate their performance characteristics on handling temporal queries in the modeled IoT system.

Guaranteeing reliable deep neural network (DNN) inference despite intermittent power is the cornerstone of enabling intelligent systems in energy-harvesting environments. Existing intermittent inference approaches support static neural networks with deterministic execution characteristics, accumulating progress across power cycles. However, dynamic neural networks adapt their structures at runtime. We observe that because intermittent inference approaches are unaware of this non-deterministic execution behavior, they suffer from incorrect progress recovery, degrading inference accuracy and performance. This work proposes non-deterministic inference progress accumulation to enable dynamic neural network inference on intermittent systems. Our middleware, NodPA, realizes this methodology by strategically selecting additional progress information to capture the non-determinism of the power-interrupted computation while preserving only the changed portions of the progress information to maintain low runtime overhead. Evaluations are conducted on a Texas Instruments device with both static and dynamic neural networks under time-varying power sources. Compared to intermittent inference approaches reliant on determinism, NodPA is less prone to inference non-termination and achieves an average inference speedup of 1.57 times without compromising accuracy, with greater improvements for highly dynamic networks under weaker power.

The program/erase (P/E) cycle is frequently utilized as a yardstick for indicating the wear degree of flash memory. However, this metric exhibits a significant limitation in accuracy. After enduring the same number of P/E cycles, the wear degree of flash memory could vary due to factors such as ambient temperatures and dwell time between two P/E cycles. To reflect the true wear degree of flash memory, this paper proposes an accurate and consistent metric, wearMeter. The proposed metric, independent of wear sources, guarantees accurate offline wear measurement. Moreover, by comparing to the error-correcting capability of the ECC engine, it offers a straightforward assessment of block remaining reliability margins. Leveraging wearMeter, this paper further proposes a novel low-wear Single-Level Cell (SLC) mode, lSLC, which significantly reduces wear compared to the default SLC mode. Experiments show that lSLC demonstrates over 3X the P/E cycles of the default SLC mode under the same conditions, without performance losses.

As the flash-based storage devices age with program/erase (P/E) cycles, they require an increasing number of read retries for error correction, which in turn deteriorates their read performance. The design of read-retry methods is critical to flash read performance. Current flash chips embed pre-defined read retry tables (RRT) for retry, but these tables fail to consider the read granularity and error behaviors. We characterize different types of real flash chips, based on which we further develop models for the correlation among the optimal read offsets of read voltages required for reading each page. By leveraging characterization observations and the models, we propose a methodology to generate a tailored RRT for each flash model. We introduce a dynamic read retry procedure to pick up proper read voltages from the table, followed by a proximity-search method for fine-tuning the read offsets. Experiments on real flash chips show that the proposed methodology can achieve near-zero retries. It reduces the average number of read retries to below 0.003 for data with high retention time at 8K P/E cycles, whereas the state-of-the-art approaches incur over 3 read retries on average once the flash is aged to 3K P/E cycles.

The advent of Ultra-Low-Latency storage devices has narrowed the performance gap between storage and CPU in computing platforms, facilitating synchronous I/O adoption. Yet, this approach introduces substantial busy waiting time and underutilizes computing units. To address this, we propose a light-weighted Idle-Time-Stealing (ITS) design. This involves a self-improving thread conducting prefetching for high-priority processes during synchronous I/O, and an I/O-waiting process continuing subsequent instruction executions when justifiable. Another thread, the self-sacrificing thread, proactively switches low-priority process I/O requests from synchronous to asynchronous mode, prioritizing high-priority executions. Experimental results demonstrate the effectiveness of our ITS design in reducing CPU idle time.

3D NAND flash with charge trap (CT) technology has been developed by stacking multiple layers vertically to boost storage capacity while ensuring reliability and scalability. One of its critical characteristics is the large endurance variation among and inside blocks and layers. With this feature, traditional bad block management (BBM), which determines block lifetime by the page with worst endurance, results in underutilization of solid state drive (SSD) usage. In this paper, a layer variation aware and fault-tolerant bad block management, named LaVA, is proposed to prolong the lifetime of 3D NAND flash storage. The relevant layer, instead of the entire flash block, is discarded at a finer granularity when a page failure is encountered. Experimental results based on real-world workloads show that LaVA can significantly extend the endurance of 3D CT NAND flash (30.6%-62.2%) with a small performance degradation (less than 10% increase of tail I/Oresponse time), compared to the conventional technique.

Large-scale data systems utilize indexes like hash tables and trees for efficient data retrieval. These indexes are stored on disk and loaded into DRAM on demand, where they are post-processed and analyzed by the CPU. This method incurs substantial data 110, especially when optimizations like prefetching is used. This issue is inherent in the von Neumann architecture, where storage systems are dedicated solely to data storage, while CPUs handle all computations. However, data indexing primarily involves filtering tasks, which require only simple equality tests and not the complex arithmetic capabilities of a CPU. This inefficiency in the von Neumann architecture has led to a growing interest in in-memory computing, initially centered on DRAM. Recently, NAND flash-based in-storage computing has gained attention due to its ability to compute over larger working sets without requiring initial memory loading. In response, we propose the Search-in-Memory (SiM) chip, which minimally modifies an existing flash memory chip to allow it to conduct equality tests internally and send only relevant search results, not the entire data page. Specifically, we implement data filtering by using the existing logic gates in a flash memory chip's peripheral circuits for bit-serial equality tests, which processes all bits on a page simultaneously. Additionally, we introduce a versatile SIMD interface with two primary commands: search and gather, making SiM adaptable to different application scenarios. We use “Optimistic Error Correction” to efficiently ensure data accuracy. Our evaluations show that this new architecture could significantly improve throughput over traditional CPU -centric architectures.

High-density 3D NAND flash like QLC (Quad-Level Cell) is prevailing in providing large capacities for data-intensive applications. Because of the structure limitation, a two-step programming with a specific sequence is adopted in 3D QLC flash, where data could become invalid between the two programming steps. This is called invalid programming, as the second-step programming is conducted on partially-invalid wordlines (WLs). By exploiting this phenomenon, this work proposes invalid-data assisted strategies for performance and reliability boosting of valid data in 3D QLC-based flash storage systems. We first propose a high-efficiency re-programming (RP) scheme to reprogram the valid data and a high-reliability not-programming (NP) scheme to program data on the partially-invalid WLs. An adaptive data allocation (ADA) strategy for data management between the SLC and QLC regions is further introduced to reduce the occurrence of invalid programming. The simulator-based experiments show the proposed RP scheme combined with ADA can reduce the execution time for programming by 13.51%, on average. Through real-device evaluations, we present that the NP scheme can reduce the bit error rate of NP-programmed data by 32.8% of the worst page type, thus improving overall reliability, which translates to 12% reduction in refreshing overheads and 30% lifetime extension, on average. Besides, the NP scheme with ADA averagely reduces energy consumption by 4.8%.

Log-Structured-Merge-tree (LSM-tree) has been extensively adopted because of its exceptional write efficiency and high space utilization. Compaction is invoked periodically in LSM-tree based key-value(LSM KV) systems to maintain good system performance. As the size of LSM-KV grows, large-scale compaction is now frequently seen. Compaction throughput significantly degrades with larger inputs, leading to frequent write stalls and decrement in overall write throughput. This paper proposes STEM, a stream-based compaction framework with FPGA to address this issue. A clean-cut algorithm is introduced to enable streaming-based compaction for large-scale data. With a multi-unit pipeline and dynamic pipeline schedule, STEM can handle large-scale compaction tasks efficiently. Based on the experiment result, the compaction throughput of STEM can achieve$27\times$on average and up to$35\times$improvement compared with the current RocksDB compaction,$2.09\times$to$2.27\times$improvement compared with the state-of-the-art FPGA accelerator.

Retrieval-based augmentations (RA) incorporating knowledge from an external database into language models have greatly succeeded in various knowledge-intensive (KI) tasks. However, integrating retrievals in non-knowledge-intensive (NKI) tasks is still challenging. Existing works focus on concatenating retrievals with inputs to improve model performance. Unfortunately, the use of retrieval concatenation-based augmentations causes an increase in the input length, substantially raising the computational demands of attention mechanisms. This paper proposes a new paradigm of RA named \textbf{ReFusion}, a computation-efficient \textbf{Re}trieval representation \textbf{Fusion} with bi-level optimization. Unlike previous works, ReFusion directly fuses the retrieval representations into the hidden states of models. Specifically, ReFusion leverages an adaptive retrieval integrator to seek the optimal combination of the proposed ranking schemes across different model layers. Experimental results demonstrate that the proposed ReFusion can achieve superior and robust performance in various NKI tasks.

DNN models are becoming increasingly large and complex, but they are also being deployed on commodity devices that require low power and latency but lack specialized accelerators. We introduce LUTIN (LUT-based INference), which reduces the amount of matrix multiplication in DNN inference by converting it into table lookups. LUTIN's innovation is its use of hyperparameter optimization to refine the quantization process and vector partitioning, allowing it to run efficiently on a variety of hardware. By reducing off-chip memory lookups and designing a cache-efficient data layout, LUTIN reduces energy consumption while increasing the use of available CPU cache, even on devices with limited processing power. Our approach goes beyond the traditional limitations of 8-bit quantization, investigating lower bit-widths to further reduce LUT size while meeting accuracy requirements. Experimental results show that LUTIN achieves up to a 2.34x speedup in latency and a 2.04x improvement in energy efficiency over full-precision models.

To index the increasing volume of data, modern data indexes are typically stored on solid-state drives and cached in DRAM. However, searching such an index has resulted in significant I/O traffic due to limited access locality and inefficient cache utilization. At the heart of index searching is the operation of filtering through vast data spans to isolate a small, relevant subset, which involves basic equality tests rather than the complex arithmetic provided by modern CPUs. This article demonstrates the feasibility of performing data filtering directly within a NAND flash memory chip, transmitting only relevant search results rather than complete pages. Instead of adding complex circuits, we propose repurposing existing circuitry for efficient and accurate bitwise parallel matching. We demonstrate how different data structures can use our flexible SIMD command interface to offload index searches. This strategy not only frees up the CPU for more computationally demanding tasks, but it also optimizes DRAM usage for write buffering, significantly lowering energy consumption associated with I/O transmission between the CPU and DRAM. Extensive testing across a wide range of workloads reveals up to a$9\times $speedup in write-heavy workloads and up to 45% energy savings due to reduced read and write I/O. Furthermore, we achieve significant reductions in median and tail read latencies of up to 89% and 85%, respectively.

In the era of big data, social network services continuously modify social connections, leading to dynamic and evolving graph data structures. These evolving graphs, vital for representing social relationships, pose significant memory challenges as they grow over time. To address this, storage-class-memory (SCM) emerges as a cost-effective solution alongside DRAM. However, contemporary graph evolution processes often scatter neighboring vertices across multiple pages, causing weak graph spatial locality and high-TLB misses during traversals. This article introduces SCM-Based graph-evolving aware data arranger (GEAR), a joint management middleware optimizing data arrangement on SCMs to enhance graph traversal efficiency. SCM-based GEAR comprises multilevel page allocation, locality-aware data placement, and dual-granularity wear leveling techniques. Multilevel page allocation prevents scattering of neighbor vertices relying on managing each page in a finer-granularity, while locality-aware data placement reserves space for future updates, maintaining strong graph spatial locality. The dual-granularity wear leveler evenly distributes updates across SCM pages with considering graph traversing characteristics. Evaluation results demonstrate SCM-based GEAR’s superiority, achieving 23% to 70% reduction in traversal time compared to state-of-the-art frameworks.

This lightning talk introduces the motivations of the needs of formal properties that can be used modularly to compose safe and tight analysis and optimization for the scheduler design and schedulability test problems for cyber-physical real-time systems. The key challenge is the correct and precise translation from different schedule functions to proper mathematical properties that can be further used for property-based modulable designs.

Deep neural network inference on energy harvesting tiny devices has emerged as a solution for sustainable edge intelligence. However, compact models optimized for continuously-powered systems may become suboptimal when deployed on intermittently-powered systems. This paper presents the pruning criterion, pruning strategy, and prototype implementation of iPrune, the first framework which introduces intermittency into neural network pruning to produce compact models adaptable to intermittent systems. The pruned models are deployed and evaluated on a Texas Instruments device with various power strengths and TinyML applications. Compared to an energy-aware pruning framework, iPrune can speed up intermittent inference by 1.1 to 2 times while achieving comparable model accuracy.

Random forest is a popular ensemble machine-learning algorithm for classification and regression tasks. However, the irregular tree shapes and non-deterministic memory access patterns make it hard for the current von Neumann architecture to handle random forest efficiently. This paper proposes a digital 3D TCAM-based accelerator for the random forest, adopting the idea of processing-in-memory (PIM) to reduce data movement. By utilizing this accelerator, we propose a TCAM-based approach to provide real-time inference with low energy consumption, making it suitable for edge or embedded environments. In the experiments, the proposed approach achieves an average of 3.13 times higher throughput with 22 times more energy saving than the GPU approach.

Memory swapping was considered slow and evil, but swapping to Ultra Low-Latency storage like Optane has become a promising solution to save power and cost, helping densely-populated edge server to overcome its DRAM capacity bottleneck. However, the lack of integration between CPU scheduling and memory paging causes soft real-time tasks running on edge servers to miss deadlines under heavy memory multiplexing. We propose APP (Adaptive Page Pinning), lightweight protection of working set memory to ensure meeting soft real-time task deadlines without starving other non-real-time tasks. Experiments show that APP alleviates thrashing in memory-intensive tasks and upholds soft real-time task deadlines.

The latency and energy consumption incurred by I/O accesses are significant in data-centric computing systems. Computational Storage Drive (CSD) can largely reduce data movement, and thus reduce I/O latency and energy consumption by offloading data-intensive processing to processors inside the storage device. In this paper, we study the problem of how to efficiently utilize the limited processing and memory resources of CSD to simultaneously serve multiple I/O requests from various applications with different real-time requirements. We proposed SERICO, a system of scheduling computational I/O requests in CSD. The key idea of SERICO is to perform admission control of real-time computational I/O requests by online schedulability analysis, to avoid wasting the processing resources and memory capacity of CSD in doing meaningless work for those requests deemed to violate the timing constraints. Each admitted computational I/O request is served in a controlled manner with carefully designed parameters, to meet its timing constraint with minimal memory cost. We evaluate SERICO with both synthetic workloads on simulators and representative applications on realistic CSD hardware. Experiment results show that SERICO significantly outperforms the default method used in the CSD device and the standard deadline-driven scheduling approach.

The complex software stack has become the performance bottleneck of the system with high-speed Non-Volatile Memory (NVM). Memory-mapped I/O (MMIO) could avoid the long-stack overhead by bypassing the kernel, but the performance is limited by existing crash-resilient mechanisms. We propose a Multi-Granularity Shadow Paging (MGSP) strategy, which smartly utilizes the redo and undo logs as shadow logs to provide a light-weight crash-resilient mechanism for MMIO. In addition, a multi-granularity strategy is designed to provide high-performance updating and locking for reducing runtime overhead, where strong consistency is preserved with a lockfree metadata log. Experimental results show that the proposed MGSP achieves 1.1 ~ 4.21× performance improvement with write and 2.56 ~ 3.76× improvement with multi-threads write compared with the underlying file system. For SQLite, MGSP can improve the database performance by 29.4% for Mobibench and 36.5% for TPCC, on average.

In-memory index delivers low-latency responses for data services. It has been ported to high-capacity persistent memory (PM) to accommodate more data. However, read-heavy, extremely-skewed, and highly-dynamic workloads can suffer from degraded performance on PM-based indexes. We present HAPIC, a scalable cache over PM-based indexes to capture the constantly-changing query hotspots in skewed workloads. HAPIC embodies the data access frequency gradient in a hierarchy of hash tables to efficiently identify hotspots and reacts quickly to workload changes with epoch-based promotion. Compared with the state-of-the-art strategy, HAPIC reacts to hotspot shifts significantly faster, with up to 14% higher stable read throughput, 26% lower median latency, and 13% lower P99 latency.

The increasing demand for high-quality graphics on mobile devices necessitates a high frame rate for display refresh. However, current process scheduling and memory management policies fail to consider the computation demands of frame rendering because they are optimized for saving energy and resource utilization. This leads to unresponsive displays for mobile users due to rendering delays. Accurately estimating computation demands is challenging for the mobile operating system, particularly under memory pressure, without display-specific semantics from user space. Moreover, the complexity of frame rendering makes it infeasible to schedule them with real-time policies. To address these issues, we propose a new framework called REFROM that utilizes a history-based frame time estimator to analyze frame time samples from UI threads and predict the computation requirements of upcoming frames. Experimental results demonstrate that REFROM reduces the number of delayed frames by up to 40% and improves up to 4% energy efficiency compared to the existing approaches.

Multiple Instance Learning (MIL) is a crucial weakly supervised learning method applied across various domains, e.g., medical diagnosis based on whole slide images (WSIs). Recent advancements in MIL algorithms have yielded exceptional performance when the training and test data originate from the same domain, such as WSIs obtained from the same hospital. However, this paper reveals a performance deterioration of MIL models when tested on an out-of-domain test set, exemplified by WSIs sourced from a novel hospital. To address this challenge, this paper introduces the Retrieval-AugMented MIL (RAM-MIL) framework, which integrates Optimal Transport (OT) as the distance metric for nearest neighbor retrieval. The development of RAM-MIL is driven by two key insights. First, a theoretical discovery indicates that reducing the input's intrinsic dimension can minimize the approximation error in attention-based MIL. Second, previous studies highlight a link between input intrinsic dimension and the feature merging process with the retrieved data. Empirical evaluations conducted on WSI classification demonstrate that the proposed RAM-MIL framework achieves state-of-the-art performance in both in-domain scenarios, where the training and retrieval data are in the same domain, and more crucially, in out-of-domain scenarios, where the (unlabeled) retrieval data originates from a different domain. Furthermore, the use of the transportation matrix derived from OT renders the retrieval results interpretable at the instance level, in contrast to the vanilla $l_2$ distance, and allows for visualization for human experts. *Code can be found at \url{https://github.com/ralphc1212/ram-mil*.

Nested dropout is a variant of dropout operation that is able to order network parameters or features based on the pre-defined importance during training. It has been explored for: I. Constructing nested nets Cui et al. 2020, Cui et al. 2021: the nested nets are neural networks whose architectures can be adjusted instantly during testing time, e.g., based on computational constraints. The nested dropout implicitly ranks the network parameters, generating a set of sub-networks such that any smaller sub-network forms the basis of a larger one. II. Learning ordered representation Rippel et al. 2014: the nested dropout applied to the latent representation of a generative model (e.g., auto-encoder) ranks the features, enforcing explicit order of the dense representation over dimensions. However, the dropout rate is fixed as a hyper-parameter during the whole training process. For nested nets, when network parameters are removed, the performance decays in a human-specified trajectory rather than in a trajectory learned from data. For generative models, the importance of features is specified as a constant vector, restraining the flexibility of representation learning. To address the problem, we focus on the probabilistic counterpart of the nested dropout. We propose a variational nested dropout (VND) operation that draws samples of multi-dimensional ordered masks at a low cost, providing useful gradients to the parameters of nested dropout. Based on this approach, we design a Bayesian nested neural network that learns the order knowledge of the parameter distributions. We further exploit the VND under different generative models for learning ordered latent distributions. In experiments, we show that the proposed approach outperforms the nested network in terms of accuracy, calibration, and out-of-domain detection in classification tasks. It also outperforms the related generative models on data generation tasks.

Big data applications, such as recommendation system and social network, often generate a huge number of fine-grained reads to the storage. Block-oriented storage devices upon the traditional storage system rely on the paging mechanism to migrate pages to the host DRAM, tending to suffer from these fine-grained read operations in terms of I/O traffic as well as performance. Motivated by this challenge, an efficient fine-grained read framework, Pipette, is proposed in this article as an extension to the traditional I/O framework. With adaptive design for caching, merging, and scheduling, Pipette explores locality and acceleration for fine-grained read requests to establish an efficient byte-granular read path upon the dedicated byte-addressable interface. When the Pipette prototype on an SSD runs popular workloads, we measured throughput gains by up to 50% and 54% with traffic reduction in the range of$41.3\times $and$56.5\times $.

Recently, phase-change memory (PCM) has emerged as a promising memory and storage technology. By storing multiple bits in a PCM cell, multi-level-cell (MLC) PCM further reduces the per-bit cost to improve its competitiveness. However, MLC PCM suffers from the high write latency and energy consumption caused by its complex write operations. Different from the existing works that attempt to improve the write latency and energy efficiency of the physical program & verify strategy for MLC PCM, we propose DTC, a drift-tolerant coding scheme, to apply fast write operation on MLC PCM without sacrificing the data accuracy. By exploiting the resistance drift and asymmetric write characteristics of PCM cells, the proposed DTC can significantly reduce the write latency and energy consumption of MLC PCM. Meanwhile, we propose a segmentation strategy to further improve the write performance with our coding scheme and an elimination methodology to avoid issuing unnecessary update operations. A series of analyses and experiments was conducted to evaluate the capability of the proposed scheme. It is encouraging that the proposed scheme can reduce 16.8%–32.1% energy consumption and 20.1%–32.6% write latency under the representative benchmarks, compared with the existing well-known schemes.

From cloud databases to large-scale data analytics, modern applications exploit solid state drives (SSD)’s low latency to write an enormous amount of short-lived data. These data do not require the strong data protection typical SSDs use to reliably store data for a guaranteed period. In recent years, SSD’s density has been growing rapidly at the cost of degraded reliability, forcing SSD vendors to trade endurance and performance for stronger error protection. An intuitive question to ask is, “What if the SSD can identify these short-lived data to save the tax of over-protection?” In this article, we answer affirmatively with a novel co-design called, ZoneLife, which exposes the data lifetime semantics from applications to the SSD. ZoneLife enables the SSD to select the optimal error-correction code (ECC) out of multiple codes of different strengths. As a result, the SSD can store short-lived data with significantly less resources. ZoneLife efficiently translates the data addresses of different lifetimes with a multigranularity flash-translation-layer (FTL). Existing systems can easily adopt ZoneLife with localized modifications because ZoneLife’s host driver API generalizes Linux’s write hint interface, and its device firmware utilizes the popular Zone Namespace interface. ZoneLife is evaluated with several representative database and cloud workloads, and the results show noticeable improvements in SSD’s endurance and write throughput.

With the advent of the Internet of Things (IoT), more and more wearable devices have been developed and integrated into our daily lives. Energy efficiency is critical for these devices because they are typically run on energy-constrained resources like batteries or energy harvesters. The storage-class memory (SCM) technologies and data compression techniques could improve their energy efficiency via reducing data movements and squeezing the data size, respectively, where data compression is especially important for IoT and embedded systems to reduce the volume of data for the space-constrained memory/storage devices. Nevertheless, both of them cannot be aware of their inherent characteristics for further minimization of energy consumption. To this end, a write-friendly coding scheme is proposed in this work that jointly manages both techniques to yield energy-efficient SCM-based systems. Moreover, a novel design of ignorable bits is presented to partially skip write operations after completing data compression without sacrificing data accuracy. We evaluate the proposed scheme via a series of intensive experiments, the experimental results of which indicate that the proposed coding scheme reduces energy consumption by up to 45% under the investigated benchmarks.

With the strong demand for stable and great quality of service in many network and multimedia services, flash-memory storage systems have been widely adopted in the storage I/O stack in servers and data centers to provide greater access performance. In these services, a huge-size storage system is essential. However, the huge-size flash storage system is very expensive. Flash storage vendors gradually adopt the high-density, low-reliability, and cost-efficient multiple-level cell (MLC) NAND flash memory chip as the major storage medium. Unfortunately, MLC NAND flash memory also brings about the critical issue of the high raw bit error rate. To resolve this issue, vendors adopt the more complex error correction code [such as low-density parity-check (LDPC)]. However, LDPC also results in significant read performance degradation due to its multiple read-retry sensing and decoding steps. To resolve this issue, we proposed a retention-aware read acceleration design (referred to as RRA) for the LDPC-based flash storage system to maintain stable and great read performance without significantly affecting the lifetime. Without significantly modifying the existing flash translation layer (FTL) design, we proposed a retention-aware management module to the existing FTL design. This module can efficiently identify and predict the data access characteristics and precisely allocate the suitable blocks for different data. The proposed design was evaluated with a series of experiments. The experiment results demonstrate that it could effectively reduce average read response time without significantly increasing the number of total live-page copying compared to the typical wear-leveling strategy.

Intermittent deep neural network (DNN) inference is a promising technique to enable intelligent applications on tiny devices powered by ambient energy sources. Nonetheless, intermittent execution presents inherent challenges, primarily involving accumulating progress across power cycles and having to refetch volatile data lost due to power loss in each power cycle. Existing approaches typically optimize the inference configuration to maximize data reuse. However, we observe that such a fixed configuration may be significantly inefficient due to the fluctuating balance point between data reuse and data refetch caused by the dynamic nature of ambient energy. This work proposes DynBal , an approach to dynamically reconfigure the inference engine at runtime. DynBal is realized as a middleware plugin that improves inference performance by exploring the interplay between data reuse and data refetch to maintain their balance with respect to the changing level of intermittency. An indirect metric is developed to easily evaluate an inference configuration considering the variability in intermittency, and a lightweight reconfiguration algorithm is employed to efficiently optimize the configuration at runtime. We evaluate the improvement brought by integrating DynBal into a recent intermittent inference approach that uses a fixed configuration. Evaluations were conducted on a Texas Instruments device with various network models and under varied intermittent power strengths. Our experimental results demonstrate that DynBal can speed up intermittent inference by 3.26 times, achieving a greater improvement for a large network under high intermittency and a large gap between memory and computation performance.

Big data applications, such as recommendation system and social network, often generate a huge number of fine-grained reads to the storage. Block-oriented storage devices tend to suffer from these fine-grained read operations in terms of I/O traffic as well as performance. Motivated by this challenge, a fine-grained read framework, Pipette, is proposed in this paper, as an extension to the traditional I/O framework. With an adaptive caching design, Pipette framework offers a tremendous reduction in I/O traffic as well as achieves significant performance gain. A Pipette prototype was implemented with Ext4 file system on an SSD for two real-world applications, where the I/O throughput is improved by 31.6% and 33.5%, and the I/O traffic is reduced by 95.6% and 93.6%, respectively.

In recent years, the demand for data storage space has increased dramatically due to the exponential growth of data volume. Data compression is of great significance since it saves data storage space and reduces data transfer demand. Compression algorithms based on statistical models have a much higher compression ratio than dictionary-based methods, but the high computational time cost of statistical modeling limits their wider application. In this paper, we introduce pLPAQ, an FPGA-based design of a powerful compression algorithm LPAQ based on statistical models. A novel hardware accelerator is proposed to speed up LPAQ by fully utilizing the parallelism of FPGA. Experimental results show that the proposed design can achieve a throughput of 12 MB/s on Xilinx Virtex Plus UltraScale XCVU9P card, 25x faster than executing on AMD Ryzen R7 4800U at 2.8 GHz and 80x faster compared with the naive FPGA implementation on average.

To meet the strict service level agreement requirements of recommendation systems, the entire set of embeddings in recommendation systems needs to be loaded into the memory. However, as the model and dataset for production-scale recommendation systems scale up, the size of the embeddings is approaching the limit of memory capacity. Limited physical memory constrains the algorithms that can be trained and deployed, posing a severe challenge for deploying advanced recommendation systems. Recent studies offload the embedding lookups into SSDs, which targets the embedding-dominated recommendation models. This paper takes it one step further and proposes to offload the entire recommendation system into SSD with in-storage computing capability. The proposed SSD-side FPGA solution leverages a low-end FPGA to speed up both the embedding-dominated and MLP-dominated models with high resource efficiency. We evaluate the performance of the proposed solution with a prototype SSD. Results show that we can achieve 20-100× throughput improvement compared with the baseline SSD and 1.5-15× improvement compared with the state-of-art.

The incompleteness of speech inputs severely degrades the performance of all the related speech signal processing applications. Although many researches have been proposed to address this issue, they controlled the data missing conditions by simulation with self-defined masking lengths or sizes. Besides, the masking definitions are different among all these experimental settings. This paper presents a novel intermittent speech recovery (ISR) system for real-world self-powered intermittent devices. Three contributive stages: interpolation, enhancement, and combination are applied to the ISR system for speech reconstruction. The experimental results show that our recovery system increases speech quality by up to 591.7%, while increasing speech intelligibility by up to 80.5%. Most importantly, the proposed ISR system improves the WER scores by up to 52.6%. The promising results not only confirm the effectiveness of the reconstruction but also encourage the utilization of these battery-free wearable/IoT devices.

In recent years, quantitative verification concerning network availability has received increasing attention due to its practical importance in network management. Existing work extends upon qualitative verification and tries to answer whether a network would have any link overload under failures and dynamic traffic. The simple yes-or-no question falls short of accurately characterizing the robustness of a network under uncertainties, which the operators are in dire need of. Thus, we argue that it is necessary to design a probabilistic framework to analyze network availability comprehensively. We propose Pita, a novel network analysis framework that outputs the overall probability of the network being unavailable under a range of failure scenarios and traffic demands. We formalize the problem and show that it is #P-hard which does not admit deterministic approximation solutions. We further develop an improved randomized approximation that exploits the structural property of our problem to reduce the computational cost of the so-called boundary oracle procedure, a key bottleneck of the approximation, without any accuracy loss. Evaluation with real topologies shows that Pita provides up to 2.25x speedup over state-of-the-art solutions, and can be effectively used in many network management tasks such as identifying high-risk failure scenarios, and aiding robust traffic engineering design.

Phase-Change Memory (PCM) has emerged as a promising memory and storage technology in recent years, and Multi-Level-Cell (MLC) PCM further reduces the per-bit cost to improve its competitiveness by storing multiple bits in each PCM cell. However, MLC PCM has high energy consumption issue in its write operations. In contrast to existing works that try to enhance the energy efficiency of the physical program&verify strategy for MLC PCM, this work proposes a drift-tolerant coding scheme to enable the fast write operation on MLC PCM without sacrificing any data accuracy. By exploiting the resistance drift and asymmetric write characteristic of PCM cells, the proposed scheme can reduce the write energy consumption of MLC PCM significantly. Meanwhile, a segmentation strategy is proposed to further improve the write performance with our coding scheme. A series of analyses and experiments was conducted to evaluate the capability of the proposed scheme. The results show that the proposed scheme can reduce 6.2–17.1% energy consumption and 3.2–11.3% write latency under six representative benchmarks, compared with the existing well-known schemes.

Vector similarity search (VSS) for unstructured vectors generated via machine learning methods is a promising solution for many applications, such as face search. With increasing awareness and concern about data security requirements, there is a compelling need to store data and process VSS applications locally on edge devices rather than send data to servers for computation. However, the explosive amount of data movement from NAND storage to DRAM across memory hierarchy and data processing of the entire dataset consume enormous energy and require long latency for VSS applications. Specifically, edge devices with insufficient DRAM capacity will trigger data swap and deteriorate the execution performance. To overcome this crucial hurdle, we propose an intelligent cognition engine (ICE) with cognitive 3D NAND, featuring non-volatile in-memory computing (nvIMC) to accelerate the processing, suppress the data movement, and reduce data swap between the processor and storage. This cognitive 3D NAND features digital nvIMC techniques (i. e., ADClDAC-free approach), high-density 3D NAND, and compatibility with standard 3D NAND products with minor modifications. To facilitate parallel INT8/INT4 vector-vector multiplication (VVM) and mitigate the reliability issue of 3D NAND, we develop a bit-error-tolerance data encoding and a two’s complement-based digital accumulator. VVM can support similarity computations (e.g., cosine similarity and Euclidean distance), which are required to search “the most similar data” right where they are stored. In addition, the proposed solution can be realized on edge storage products, e.g., embedded Multi-Media Card (eMMC). The measured and simulated results on real 3D NAND chips show that ICE enhances the system execution time by $17\times to 95\times$ and energy efficiency by $11\times to 140\times$, compared to traditional von Neumann approaches using state-of-the-art edge systems with MobileFaceNet on CASIA-WebFace dataset. To the best of our knowledge, this work demonstrates the first 3D NAND-based digital nvIMC technique with measured silicon data.

The storage of multi-media data can benefit from the advancements in general-purpose lossless compression. The explosive growth of multi-media data volume in data centers demands a higher compression ratio and better compressors' run-time speed. However, recent deep-learning-based compressors with a high compression ratio usually build complicated dependencies on history symbols, leading to a long compression time. This paper investigates the behavior of historical symbols and finds an approximate order of importance. Namely, recent symbols have a substantially larger influence on the probability estimation of the next unknown symbol. This observation guides the designing of an interpretable structure for data compression, rather than learning implicitly from data like Recurrent Neural Network (RNN) and attention. Based on this observation, we disentangle the compression model into order learning and feature learning, which were fused in a large module in previous works. A parameterized ordered mask unit is established to learn the ordered importance of history symbols. A fast Multi-Layer Perceptron (MLP) network is designed for efficient feature learning. The proposed compressor can improve both compression performance and computational efficiency compared with transformer-based or RNN-based compressors. To further enhance computational efficiency, we propose a branch-MLP block to replace the original MLP layer. This block reduces the parameters and the FLOPs of the original MLP to a half, without sacrificing compression performance. Experiments on multi-media data demonstrate that our model improves the compression ratio by 10% on average across data domains while accelerating compression speed by 100% compared with the state-of-the-art. The source code and appendix are released at https://github.com/mynotwo/compressor_via_simple_and_scalable_parameterization.git.

Deep-learning-based compressor has received interests recently due to much improved compression ratio. However, modern approaches suffer from long execution time. To ease this problem, this paper targets on cutting down the execution time of deep-learning-based compressors. Building history-dependencies sequentially (e.g., recurrent neural networks) is responsible for long inference latency. Instead, we introduce transformer into deep learning compressors to build history-dependencies in parallel. However, existing transformer is too heavy in computation and incompatible to compression tasks.

Although log-structured merge trees (LSM-trees) are commonly adopted in many NoSQLs as they can significantly improve the write performance in updating a database, most of the proposed LSM-trees are concentrated on storing a single version of data. On the other hand, in many Internet of Things (IoT) applications, it is important to maintain the old versions of data in addition to the latest version. In this article, we introduce our design and implementation of an enhancement of LevelDB to multiversion LevelDB (called MVLevelDB) with the purpose to efficiently support temporal queries on multiversion data in IoT applications. Based on the temporal consistency, we formulated the log-structured multiversion tree (LSMV-tree) to be implemented into MVLevelDB. In LSMV-tree, each data version is associated with two time-stamps to define its validity interval, and both the data versions and the components are time-sorted to improve the efficiency in searching data in processing temporal queries. To handle the problem of multicomponents data versions, we designed the data version duplication (DvD) method in which a data version will be duplicated in the next component if it is valid while its component is being flushed from the main memory to disk storage. Extensive experiments using a benchmark program have been performed to investigate the performance of MVLevelDB as compared with LevelDB both in writing and reading data.

Recent works on learned index open a new direction for the indexing field. The key insight of the learned index is to approximate the mapping between keys and positions with piece-wise linear functions. Such methods require partitioning key space for a better approximation. Although lots of heuristics are proposed to improve the approximation quality, the bottleneck is that the segmentation overheads could hinder the overall performance. This paper tackles the approximation problem by applying a distribution transformation to the keys before constructing the learned index. A two-stage Normalizing-Flow-based Learned index framework (NFL) is proposed, which first transforms the original complex key distribution into a near-uniform distribution, then builds a learned index leveraging the transformed keys. For effective distribution transformation, we propose a Numerical Normalizing Flow (Numerical NF). Based on the characteristics of the transformed keys, we propose a robust After-Flow Learned Index (AFLI). To validate the performance, comprehensive evaluations are conducted on both synthetic and real-world workloads, which shows that the proposed NFL produces the highest throughput and the lowest tail latency compared to the state-of-the-art learned indexes.

Numerous compression and acceleration strategies have achieved outstanding results on classification tasks in various fields. Nevertheless, the same strategies may yield unsatisfactory performance on regression tasks because the nature between regression and classification tasks differs. In this paper, a novel sign-exponent-only floating-point network (SEOFP-NET) technique is proposed to compress the model size and accelerate the inference time for speech enhancement, a regression task of speech signal processing. The proposed method compressed the sizes of deep neural network (DNN)-based speech enhancement models by quantizing the fraction bits of single-precision floating-point parameters during training. Before inference implementation, all parameters in the trained SEOFP-NET model are adjusted to accelerate the inference time by replacing the floating-point multiplier with an integer-adder. The experimental results indicate that the size of SEOFP-NET models can be significantly compressed by up to 81.249% without noticeably downgrading their speech enhancement performance, and the inference time can be accelerated to 1.212x compared with the baseline models. The results also verify that SEOFP-NET can cooperate with other efficiency strategies to achieve a synergy effect for model compression. In addition, results of a just noticeable difference experiment show that the listeners cannot facilely differentiate between the enhanced speech signals processed by the baseline model and SEOFP-NET. To the best of our knowledge, this study is one of the first works that aims to compress the model size and reduce the inference time of speech enhancement while maintaining satisfactory performance. The promising results confirm the potential applicability of SEOFP-NET to lightweight embedded devices.

The advance of nonvolatile memory in storage technology has presented challenges in redefining the ways in handling the main memory and the storage. This work is motivated by the strong demands in effective handling of page faults over ultralow-latency storage devices. In particular, we propose synchronous and asynchronous prefetching strategies to satisfy process executions with different memory demands in supporting of synchronous page fault handling. An adaptive CPU scheduling strategy is also proposed to cope with the needs of processes in maintaining their working sets in the main memory. Six representative benchmarks and applications were evaluated. It was shown that our strategy can effectively save 12.33% of the total execution time and reduce 13.33% of page faults, compared to the conventional demand paging strategy with nearly no sacrificing of process fairness.

Identifying rare categories is an important data management problem in many application fields, including video surveillance, ecological environment monitoring, and precision medicine. Previously, solutions in the literature require all data instances to be first delivered to the server. Then, the rare category identification algorithms are executed on the pool of data to find informative instances for human annotators to label. This incurs large bandwidth consumption and high latency. To deal with the problems, we propose a lightweight rare category identification framework. At the sensor side, the designed online algorithm filters less informative data instances from the data stream and only sends the informative ones to the servers for annotating. After labeling, the server only sends labels of the corresponding data instances in response. The sensor-side algorithm is extended to enable cooperation between embedded devices for the cases that data are collected in a distributed manner. For enhancing diversity of selected data, a representative selection algorithm is proposed to run during the idle time of the system or after the execution of a rare category identification algorithm. Experiments are conducted to show that our framework dramatically outperforms the baseline. The network traffic is reduced by 75% on average.

Robustness and uncertainty estimation is crucial to the safety of deep neural networks (DNNs) deployed on the edge. The deep ensemble model, composed of a set of individual DNNs (namely members), has strong performance in accuracy, uncertainty estimation, and robustness to out-of-distribution data and adversarial attacks. However, the storage and memory consumption increases linearly with the number of members within an ensemble. Previous works focus on selecting better members, layer-wise low-rank approximation of ensemble parameters, and designing partial ensemble model for reducing the ensemble size, thus lowering storage and memory consumption. In this work, we pay attention to the quantization of the ensemble, which serves as the last mile of network deployment. We propose a differentiable and parallelizable bit sharing scheme that allows the members to share the less significant bits of parameters, without hurting the performance, leaving alone the more significant bits. The intuition is that, numerically, more significant bits (e.g., the bit for the sign) are more useful in distinguishing a member from other members. For real deployment of the bit-sharing scheme, we further propose an efficient encoding-decoding scheme with minimal storage overhead. The experimental results show that, BitsEnsemble reduces the storage size of ensemble for over$22\times $, with only$0.36\times $increase in training latency, and no sacrifice of inference latency. The code is available inhttps://github.com/ralphc1212/bitsensemble.

While the block size of 3-D NAND flash memory increases with the density and capacity, the raw bit-error rates (RBER) of open blocks could be significantly increased. This article conducts a systematic study over reliability issues caused by open blocks, and reports several new observations. We found that the reliability degradation, due to long open time in writing a block, could happen over all layers in a 3-D NAND block, even after the block is closed. To address the reliability issues of open blocks, this article first proposes to adaptively allocate active blocks to serve write requests based on the workload characteristics for open time reduction. We then propose a partial-block refreshing strategy to alleviate the amplified RBER variations in open blocks and, thus, avoid unnecessary refreshing operations in low-RBER layers. Experimental results show that the proposed method can reduce the RBER by 43% through the reduction of the open time by 28% on average, and reduce the extra write operations for refreshing by 23% on average.

Internet of Things (IoT) devices are gradually adopting battery-less, energy harvesting solutions, thereby driving the development of an intermittent computing paradigm to accumulate computation progress across multiple power cycles. While many attempts have been made to enable standalone intermittent systems, little attention has focused on IoT networks formed by intermittent devices. We observe that the computation progress improved by distributed task concurrency in an intermittent network can be significantly offset by data unavailability due to frequent system failures. This article presents an intermittent-aware distributed concurrency control protocol which leverages existing data copies inherently created in the network to improve the computation progress of concurrently executed tasks. In particular, we propose a borrowing-based data management method to increase data availability and an intermittent two-phase commit procedure incorporated with distributed backward validation to ensure data consistency in the network. The proposed protocol was integrated into a FreeRTOS-extended intermittent operating system running on Texas Instruments devices. Experimental results show that the computation progress can be significantly improved, and this improvement is more apparent under weaker power, where more devices will remain offline for longer duration.

Deep neural network (DNN) inference on intermittently powered battery-less devices has the potential to unlock new possibilities for sustainable and intelligent edge applications. Existing intermittent inference approaches preserve progress information separate from the computed output features during inference. However, we observe that even in highly specialized approaches, the additional overhead incurred for inference progress preservation still accounts for a significant portion of the inference latency. This work proposes the concept of stateful neural networks, which enables a DNN to indicate the inference progress itself. Our runtime middleware embeds state information into the DNN such that the computed and preserved output features intrinsically contain progress indicators, avoiding the need to preserve them separately. The specific position and representation of the embedded states jointly ensure both output features and states are not corrupted while maintaining model accuracy, and the embedded states allow the latest output feature to be determined, enabling correct inference recovery upon power resumption. Evaluations were conducted on different Texas Instruments devices under varied intermittent power strengths and network models. Compared to the state-of-the-art, our approach can speed up intermittent inference by 1.3 to 5 times, achieving higher performance when executing modern convolutional networks with weaker power.

In the big data era, a huge number of services has placed a fast-growing demand on the capacity of DRAM-based main memory. However, due to the high hardware cost and serious leakage power/energy consumption, the growth rate of DRAM capacity cannot meet the increased rate of the required main memory space when the energy or hardware cost is a critical concern. To tackle this issue, hybrid main-memory devices/modules have been proposed to replace the pure DRAM main memory with a hybrid main memory module that provides a large main memory space by integrating a small-sized DRAM and a large-sized non-volatile memory (NVM) into the same memory module. Although NVMs have high-density and low-cost features, they suffer from the low read/write performance and low endurance issue, compared to DRAM. Thus, inside the hybrid main-memory module, it also includes a memory management design to use DRAM as the cache of NVMs to enhance its performance and lifetime. However, it also introduces new design challenges in both the OS and the memory module. In this work, we rethink the interactivity of OS and hybrid main-memory module, and propose a cross-layer cache design that (1) utilizes the information from the operating system to optimize the hit ratio of the DRAM cache inside the memory module, and (2) takes advantage of the bulk-size (or block-based) read/write feature of NVM to minimize the time overhead on the data movement between DRAM and NVM. At the same time, this cross-layer cache design is very lightweight and only introduces limited runtime management overheads. A series of experiments was conducted to evaluate the effectiveness of the proposed cross-layer cache design. The results show that the proposed design could improve access performance for up to 88%, compared to the investigated well-known page replacement algorithms.

In this paper, we study the problem of embedding uncertain knowledge graphs, where each relation between entities is associated with a confidence score. Observing the existing embedding methods may discard the uncertainty information, only incorporate a specific type of score function, or cause many false-negative samples in the training, we propose the PASSLEAF framework to solve the above issues. PASSLEAF consists of two parts, one is a model that can incorporate different types of scoring functions to predict the relation confidence scores and the other is the semi-supervised learning model by exploiting both positive and negative samples associated with the estimated confidence scores. Furthermore, PASSLEAF leverages a sample pool as a relay of generated samples to further augment the semi-supervised learning. Experiment results show that our proposed framework can learn better embedding in terms of having higher accuracy in both the confidence score prediction and tail entity prediction.

In the era of the Internet of Things (IoT), wearable IoT devices become popular and closely related to our life. Most of these devices are based on the embedded systems that have to operate on limited energy resources, such as batteries or energy harvesters. Therefore, energy efficiency is one of the critical issues for these devices. To relieve the energy consumption by reducing the total accesses on memory and storage layers, the technologies of storage-class memory (SCM) and data compression techniques are applied to eliminate the data movements and squeeze the data size, respectively. However, the information gap between them hinders the cooperation among the two techniques for achieving further optimizations on minimizing energy consumption. This work proposes a write-friendly arithmetic coding with joint managing both techniques to achieve energy-efficient non-volatile memory (NVM) systems. In particular, the concept of "ignorable bits" is introduced to further skip the write operations while storing the compressed data into SCM devices. The proposed design was evaluated by a series of intensive experiments, and the results are encouraging.

Mission-critical edge applications require both low latency and strict data safety. Although emerging ultra-dense solid-state drives (SSDs) can extend the amount of data edge servers can process, the reduced parallelism can worsen read tail latency and even violate the deadline of mission-critical edge applications. To cut ultra-dense SSDs’ read tail latency, we propose Reptail, a co-design of host OS and SSD, that exploits the inherent redundancy in transactional systems. We use journaling file system to show how exposing SSD’s internals to host OS’s redundancy semantics can improve its read scheduling, thus reducing read tail latency. We evaluate Reptail with diverse workloads and find more than 20% latency improvements in the 95th and 99th percentile.

Future computing platforms are facing a paradigm shift with the emerging resistive memory technologies. First, they offer fast memory accesses and data persistence in a single large-capacity device deployed on the memory bus, blurring the boundary between memory and storage. Second, they enable computing-in-memory for neuromorphic computing to mitigate costly data movements. Due to the non-ideality of these resistive memory devices at the moment, we envision that cross-layer design is essential to bring such a system into practice. In this paper, we showcase a few examples to demonstrate how cross-layer design can be developed to fully exploit the potential of resistive memories and accelerate its adoption for future computing platforms.

The reliability of solid-state drives (SSDs) has become increasingly important as SSDs are now widely applied in data centers. Retention error is a major source of impact on the reliability of SSDs. Even though the common practice in understanding the retention errors of an SSD is done by high-temperature baking processes, their characterization accuracy is not yet rigidly reviewed. In this paper, we first present how the common retention acceleration method goes wrong. Through a one-year study of 3D flash error behaviors, we found that the retention errors through baking with high temperatures have very different characteristics from the real long-retention errors. These differences come from the inherent structure and the materials of 3D NAND flash. Several findings regarding the retention errors characterized through baking are presented, followed by the analysis of the error behaviors. Finally, the retention errors of one year on 3D flash memory are provided with real data.

Aiming to extract the information behind messy data, graph computation is one of the popular big data analysis applications. During running graph computation, large numbers of vertices and edges will be moved between memory and computing units, and these intensive data movements lead to a performance bottleneck. To break the bottleneck, Resistive Random-Access Memory (ReRAM) based crossbar accelerators, which can act as both computing and memory units simultaneously on one chip, are a promising solution to eliminate these data movements. However, running graph computation on crossbar accelerators incurs high power consumption because real-world graphs are too sparse and discrete to unleash the computation capability provided by crossbar accelerators. In contrast to previous works which require extra general-purpose computing units to work with crossbar accelerators, this work proposes a software strategy, called graph-aware crossbar placement strategy, to improve the utilization of crossbar accelerators by clustering graph nodes with strong graph spatial locality. The evaluation results show that the proposed graph-aware crossbar placement strategy can efficiently save the energy consumption of crossbar accelerators.

Read-ahead schemes have been widely used in page cache to improve read performance of Linux systems. As the Android system inherits the Linux kernel, the traditional read-ahead scheme is directly transplanted to mobile devices. However, request sizes and page cache sizes on mobile devices are much smaller, which may degrade read-ahead efficiency and therefore hurt user experience. This article first observes that many pages pre-fetched by read-ahead are unused, which causes frequent page cache eviction. And these evict operations could induce extra access latency, especially when write-back is conducting. Then, this article proposes a new analysis model to characterize the factors that closely relate to the access latency. It is found that there exists a trade-off between read-ahead size and access latency. Finally, this article proposes two optimized read-ahead schemes to exploit this trade-off under different situations. Size-tuning scheme aims to find the proper maximum size of read-ahead according to the characteristics of mobile devices. While MobiRA scheme improves the read-ahead efficiency by dynamically tuning read-ahead size and stop-settings. Experimental results on real mobile devices show that the proposed schemes can increase the efficiency of read-ahead scheme and improve the overall performance of mobile devices.

TRIM is a recommended command to deliver data invalidation information of the file system to flash storage. It is issued on both system level and device level. Since it can reduce the number of data copies during device-level garbage collection (DGC), TRIM has been widely used to improve the endurance and performance of mobile devices. Contrary to the common belief, this work identifies that the default TRIM scheme has both merit and drawback to the performance of mobile devices, especially in flash-friendly file system (F2FS), which is a commonly used file system in mobile devices. On one hand, TRIM can reduce garbage collection migration to prolong the flash lifetime as well as improving I/O throughput; On the other hand, TRIM may induce I/O contentions. This article proposes a new TRIM scheme, iTRIM, to distribute the timing overheads to system idle time. To further reduce I/O contention and improve I/O performance, the design of iTRIM considers the TRIM size, and the logical addresses' pattern of victim invalidated data. Experimental results show that iTRIM can minimize I/O contentions while retaining the benefits of the default TRIM scheme for endurance and performance.

Intermittent systems enable batteryless devices to operate through energy harvesting by leveraging the complementary characteristics of volatile (VM) and non-volatile memory (NVM). Unfortunately, alternate and frequent accesses to heterogeneous memories for accumulative execution across power cycles can significantly hinder computation progress. The progress impediment is mainly due to more CPU time being wasted for slow NVM accesses than for fast VM accesses. This paper explores how to leverage heterogeneous cores to mitigate the progress impediment caused by heterogeneous memories. In particular, a delegable and adaptive synchronization protocol is proposed to allow memory accesses to be delegated between cores and to dynamically adapt to diverse memory access latency. Moreover, our design guarantees task serializability across multiple cores and maintains data consistency despite frequent power failures. We integrated our design into FreeRTOS running on a Cypress device featuring heterogeneous dual cores and hybrid memories. Experimental results show that, compared to recent approaches that assume single-core intermittent systems, our design can improve computation progress at least 1.8x and even up to 33.9x by leveraging core heterogeneity.

NAND flash memory has been widely adopted in storage systems today. The most important issue in flash memory is its reliability, especially for 3D NAND, which suffers from several types of errors. The raw bit error rate (RBER) when applying default read reference voltages is usually adopted as the reliability metric for NAND flash memory. However, RBER is closely related to the way how data is read, and varies greatly if read retry operations are conducted with tuned read reference voltages. In this work, a new metric, valid window is proposed to measure the reliability, which is stable and accurate. A valid window expresses the size of error regions between two neighboring levels and determines if the data can be correctly read with further read retry. Taking advantage of these features, we design a method to reduce the number of read retry operations. This is achieved by adjusting program operations of 3D NAND flash memories. Experiments on a real 3D NAND flash chip verify the effectiveness of the proposed method.

Neural network compression and quantization are important tasks for fitting state-of-the-art models into the computational, memory and power constraints of mobile devices and embedded hardware. Recent approaches to model compression/quantization are based on reinforcement learning or search methods to quantize the neural network for a specific hardware platform. However, these methods require multiple runs to compress/quantize the same base neural network to different hardware setups. In this work, we propose a fully nested neural network (FN3) that runs only once to build a nested set of compressed/quantized models, which is optimal for different resource constraints. Specifically, we exploit the additive characteristic in different levels of building blocks in neural network and propose an ordered dropout (ODO) operation that ranks the building blocks. Given a trained FN3, a fast heuristic search algorithm is run offline to find the optimal removal of components to maximize the accuracy under different constraints. Compared with the related works on adaptive neural network designed only for channels or bits, the proposed approach is applicable to different levels of building blocks (bits, neurons, channels, residual paths and layers). Empirical results validate strong practical performance of proposed approach.

Spatiotemporal super-resolution (SR) aims to upscale both the spatial and temporal dimensions of input videos, and produces videos with higher frame resolutions and rates. It involves two essential sub-tasks: spatial SR and temporal SR. We design a two-stream network for spatiotemporal SR in this work. One stream contains a temporal SR module followed by a spatial SR module, while the other stream has the same two modules in the reverse order. Based on the interchangeability of performing the two sub-tasks, the two network streams are supposed to produce consistent spatiotemporal SR results. Thus, we present a cross-stream consistency to enforce the similarity between the outputs of the two streams. In this way, the training of the two streams is correlated, which allows the two SR modules to share their supervisory signals and improve each other. In addition, the proposed cross-stream consistency does not consume labeled training data and can guide network training in an unsupervised manner. We leverage this property to carry out semi-supervised spatiotemporal SR. It turns out that our method makes the most of training data, and can derive an effective model with few high-resolution and high-frame-rate videos, achieving the state-of-the-art performance. The source code of this work is available at https://hankweb.github.io/STSRwithCrossTask/.

High-density flash-memory chips are under tremendous demands with the exponential growth of data. At the same time, the slow read performance of these high-density flash-memory chips becomes a new challenge. In this work, we analyze the high raw bit error rates (RBER) issue by characterizing the error behaviours of 3D QLC flash-memory chips. A preferred read voltage to a QLC cell could vary among layers and might even change in a short period of time due to the temperature. A sentinel-cell approach is thus proposed to utilize the error characteristics among cells. We propose to infer the optimal read voltages of a wordline based on errors introduced on sentinel cells. An on-line calibration procedure is further presented to resolve the problem of possible non-uniform error distribution on some wordlines. With optimal voltages being inferred, the number of read retries will be significantly reduced. Experiments show that optimal read voltages can be instantly obtained in 94% cases on average over the evaluated QLC flash memory with at most 2 read retries, and with merely 0.2% space overheads for adopting sentinel cells. The number of read retries could be reduced by 82% on average, and the read performance can be improved by 74% on average through a series of extensive experiments over 3D TLC and QLC flash-memory chips.

To provide larger memory space with lower costs, NVDIMM is a production-ready device. However, directly placing NVDIMM as the main memory would seriously degrade the system performance because of the “great memory wall” caused by the fact that in NVDIMM, the slow memory (e.g., flash memory) is several orders of magnitude slower than the fast memory (e.g., DRAM). In this article, we present a joint management framework of host/CPU and NVDIMM to break down the great memory wall by bridging the process information gap between host/CPU and NVDIMM. In this framework, a page semantic-aware strategy is proposed to precisely predict, mark, and relocate data or memory pages to the fast memory in advance by exploiting the process access patterns, so that the frequency of the slow memory accesses can be further reduced. The proposed framework with the proposed strategy was evaluated with several well-known benchmarks and the results are encouraging.

Performance-intensive applications have led both interface and architecture changes of high-end, growing-scale solid-state drives (SSDs). However, we observe that most of the time, the actual drive performance could not be easily scaled or boosted up with the increasing of internal resources of growing-scale SSDs due to the potential congestion of I/O requests. Such observation inspires this article to look for a request flow coordination design to appropriately control and throttle the I/O request over the increasingly-complicated SSD internal organization with manageable coordination overhead. The main objective is to avoid overloading or congesting any sub-module of growing-scale SSDs by making good use of the abundant internal resources, so as to effectively improve the drive performance in terms of the request-response time. The capability of the proposed design was evaluated with realistic and intensive I/O workloads, and the results are very encouraging.

Self-powered intermittent systems typically adopt runtime checkpointing as a means to accumulate computation progress across power cycles and recover system status from power failures. However, existing approaches based on the checkpointing paradigm normally require system suspension and/or logging at runtime. This article presents a design which overcomes the drawbacks of checkpointing-based approaches, to enable failure-resilient intermittent systems. Our design allows accumulative execution and instant system recovery under frequent power failures while enforcing the serializability of concurrent task execution to improve computation progress and ensuring data consistency without system suspension during runtime, by leveraging the characteristics of data accessed in hybrid memory. We integrated the design into FreeRTOS running on a Texas Instruments device. The experimental results show that our design can still accumulate progress when the power source is too weak for checkpointing-based approaches to advance, and significantly improves the computation progress while reducing the recovery time.

Crossbar accelerators with a resistive random-access memory (ReRAM) are a promising solution for accelerating neural network applications. The advantages of achieving high computation throughput per watt make ReRAM-based crossbar accelerators become a potential solution for accelerating inference operations in the Internet of Things and edge devices. Due to the analog variation errors, the launched ReRAM-based crossbar accelerators can only perform well when each ReRAM cell is used to represent a limited number of data bits. To make such ReRAM-based crossbar accelerators applicable in wide application scenarios, several proposed researches target at binary neural networks and focus on the chip designs in relieving the implementation challenges on computation accuracy for realizing single-bit ReRAM-based crossbar accelerators. Even though several small-sized ReRAM-based crossbar accelerators are announced, the scalability issue hinders ReRAM-based crossbar accelerators from being scaled up. That is, when there are more and more wordline in an ReRAM-based crossbar accelerator, the analog variation error is amplified and thus seriously degrades the computation accuracy. In this work, we propose an adaptive data manipulation strategy to substantially reduce analog variation errors so as to fill up the gap on scaling up the ReRAM-based crossbar accelerators. In particular, a weightrounding design is proposed to manipulate data to minimize overlapping variation so that the number of wordlines can be scaled up. In addition, an input subcycling design is proposed to further trade tolerable errors with neural networks' execution time. Moreover, a bitline redundant design is proposed to trade acceptable space overhead for eliminating the analog variation errors. The emulation experiments show that the proposed adaptive data manipulation strategy can improve the accuracy in running MNIST and CIFAR-10 by 1.3× and 2.6× with nearly no management penalty and hardware cost. The experimental results also show the close-to-ideal-case accuracy by substantially reducing analog variation errors.

Background segment cleaning in log-structured file system has a significant impact on mobile devices. A low triggering frequency of the cleaning activity cannot reclaim enough free space for subsequent I/O, thus incurring foreground segment cleaning and impacting the user experience. In contrast, a high triggering frequency could generate excessive block migrations (BMs) and impair the storage lifetime. Prior works address this issue either by performance-biased solutions or incurring excessive memory overhead. In this article, a pruned reinforcement learning-based approach, MOBC, is proposed. Through learning the behaviors of I/O workloads and the statuses of logical address space, MOBC adaptively reduces the number of BMs and the number of triggered foreground segment cleanings. In order to integrate MOBC to resource-constraint mobile devices, a structured pruning method is proposed to reduce the time and space cost. The experimental results show that the pruned MOBC can reduce the worst case latency by 32.5%-68.6% at the 99.9th percentile, and improve the storage endurance by 24.3% over existing approaches, with significantly reduced overheads.

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

Mobile devices today often have multiple applications running simultaneously in the background. These background applications could rapidly consume storage cache resources, thus degrading the performance of foreground applications as well as the user experience. This issue could get worse as modern mobile devices are employing universal flash storage (UFS), which supports faster transmission speed and full-duplex transmission. In this article, a foreground application-aware cache management approach, FOAM, is proposed to address this issue. Through adaptive management of storage cache resources with the awareness of I/O workload patterns, UFS device features, and foreground/background information, I/O performance of foreground application is significantly improved. Experimental results show that the proposed approach could boost the performance of foreground read I/O by 45.9%, foreground write I/O by 18.4% on average compared with the existing approach.

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

In this work, we propose a GPU-accelerated algorithm for frequent pattern(FP) mining without candidate generation. We observe that the existing FP-growth algorithm has critical characteristics unsuitable for GPU, including the tree data structure, deep recursion and heavy dynamic memory allocations. By utilizing iterative execution and collectively allocating memory on GPU, our proposed method significantly reduce the latency caused by large memory allocations of original FP-growth. Experiment results show that our solution outperforms baselines, including sequential FP-growth with CPU only and existing GPU-accelerated Apriori and FP-growth, on various data sets with a significant speedup, from several times to hundred times.

Perceptual similarity measurement allows mobile applications to eliminate unnecessary computations without compromising visual experience. Existing pixel-wise measures incur significant overhead with increasing display resolutions and frame rates. This paper presents an ultra lightweight similarity measure called LSIM, which assesses the similarity between frames based on the transformation matrices of graphics objects. To evaluate its efficacy, we integrate LSIM into the Open Graphics Library and conduct experiments on an Android smartphone with various mobile 3D games. The results show that LSIM is highly correlated with the most widely used pixel-wise measure SSIM, yet three to five orders of magnitude faster. We also apply LSIM to a CPU-GPU governor to suppress the rendering of similar frames, thereby further reducing computation energy consumption by up to 27.3% while maintaining satisfactory visual quality.

Self-powered intermittent systems enable accumulative execution in unstable power environments, where checkpointing is often adopted as a means to achieve data consistency and system recovery under power failures. However, existing approaches based on the checkpointing paradigm normally require system suspension and/or logging at runtime. This paper presents a design which enables failure-resilient intermittently-powered systems without runtime checkpointing. Our design enforces the consistency and serializability of concurrent task execution while maximizing computation progress, as well as allows instant system recovery after power resumption, by leveraging the characteristics of data accessed in hybrid memory. We integrated the design into FreeRTOS running on a Texas Instruments device. Experimental results show that our design achieves up to 11.8 times the computation progress achieved by checkpointing-based approaches, while reducing the recovery time by nearly 90%.

Concurrency control allows multiple tasks that share data objects to be concurrently executed in a serializable order, thus significantly improving computation progress. However, to accumulate forward progress on energy-harvesting intermittent systems while achieving data consistency across power cycles, existing approaches based on the checkpointing paradigm typically require system suspension at runtime. The runtime overheads incurred by suspension will be more manifest when more tasks are suspended and resumed during checkpointing, offsetting the computation progress improved by concurrent task execution. This paper presents a multiversion concurrency control design, which enables concurrent task execution without system suspension during checkpointing, while maintaining the serializability of task execution and ensuring data consistency after system recovery. We integrated our design into FreeRTOS running on a Texas Instruments device. Experimental results show that, at the very best, our design can double computation progress by reducing the runtime overheads incurred by system checkpointing, especially when tasks are executed with high concurrency.

Self-powered intermittent systems waste considerable I/O energy because volatile I/O modules repeatedly issue identical operations under power failure conditions, and also due to the use of the inefficient I/O stack originally developed for battery-powered systems. This paper presents the concept, design, and implementation of autonomous I/O, which can accumulatively and transparently complete I/O operations regardless of power stability. We define its two essential functionalities, separate the general I/O stack to make accumulatively-completed I/O operations transparent to application tasks, and propose an access protocol that allows for energy efficiency and compatibility with the general I/O stack. To evaluate the efficacy, we implement our design and conduct extensive experiments on a Texas Instruments device with commodity sensor and Wi-Fi modules. Experimental results show that autonomous I/O can achieve 1.8 times the throughout achieved with nonvolatile I/O when the power is relatively steady, while reducing the completion time of individual I/O operations by at least 34% with relatively unstable power.

This paper presents a Virtual Persistent Cache design to remedy the long latency behavior and to ultimately improve the write responsiveness of the Host-Aware Shingled Magnetic Recording (HA-SMR) drives. Our design keeps the cost-effective model of the existing HA-SMR drives, but at the same time asks the great help from the host system for adaptively providing some computing and management resources to improve the drive performance when needed. The technical contribution is to trick the HA-SMR drives by smartly reshaping the access patterns to HA-SMR drives, so as to avoid the occurrences of long latencies in most cases and thus to ultimately improve the drive performance and responsiveness. We conduct experiments on real Seagate 8 TB HA-SMR drives to demonstrate the advantages of Virtual Persistent Cache over the real workloads from Microsoft Research Cambridge. The results show that the proposed design can remedy most of the long latencies and improve the drive performance by at least 58.11 percent, under the evaluated workloads.

Neural networks over conventional computing platforms are heavily restricted by the data volume and performance concerns. While non-volatile memory offers potential solutions to data volume issues, challenges must be faced over performance issues, especially with asymmetric read and write performance. Beside that, critical concerns over endurance must also be resolved before non-volatile memory could be used in reality for neural networks. This work addresses the performance and endurance concerns altogether by proposing a data-aware programming scheme. We propose to consider neural network training jointly with respect to the data-flow and data-content points of view. In particular, methodologies with approximate results over Dual-SET operations were presented. Encouraging results were observed through a series of experiments, where great efficiency and lifetime enhancement is seen without sacrificing the result accuracy.

With the low encoding/decoding complexity and the high error correction capability, polar code with the support of list-decoding and cyclic redundancy check can outperform LDPC code in the area of data communication. Thus, it also draws a lot of attentions on how to adopt and enable polar codes in storage applications. However, the code construction and encoding length limitation issues obstruct the adoption of polar codes in flash storage devices. To enable polar codes in flash storage devices, we propose a proactive channel adjustment design to extend the effective time of a code construction to improve the error correction capability of polar codes. This design pro-actively tunes the quality of the critical flash cells to maintain the correctness of the code construction and relax the constraint of the encoding length limitation, so that polar codes can be enabled in flash storage devices. A series of experiments demonstrates that the proposed design can effectively improve the error correction capability of polar codes in flash storage devices.

The increasingly high display resolution of mobile devices imposes a further burden on energy consumption. Existing schemes manage either OLED or GPU power to save energy. This paper presents the design, algorithm, and implementation of a co-managing scheme called Duet, which automatically trades off perceptual quality for energy efficiency in accordance with static and dynamic visual acuity when users interact with mobile applications. The results of experiments conducted on a commercial smartphone with popular interactive apps show that Duet saves more energy while retaining better visual quality, compared with a joint scheme that simultaneously uses dynamic pixel disabling and dynamic resolution scaling to save OLED and GPU energy in isolation.

Mobile devices running augmented reality applications consume considerable energy for graphics-intensive workloads. This paper presents a scheme for the differentiated handling of camera-captured physical scenes and computer-generated virtual objects according to different perceptual quality metrics. We propose online algorithms and their real-time implementations to reduce energy consumption through dynamic frame rate adaptation while maintaining the visual quality required for augmented reality applications. To evaluate system efficacy, we integrate our scheme into Android and conduct extensive experiments on a commercial smartphone with various application scenarios. The results show that the proposed scheme can achieve energy savings of up to 39.1% in comparison to the native graphics system in Android while maintaining satisfactory visual quality.

Real-time computing provides insightful ways to explore the optimization in resource usages, especially from the time point of view. Nevertheless, real-time task scheduling is recognized by its high complexity when there are non-preemptive shared resources and multiple processors. When more and more practical factors in system designs are considered, such as energy consumption and memory allocation, even some sub-problems in real-time task scheduling become intractable. Although people often criticize various artificial assumptions in real-time task scheduling, they have to admit that ideas in real-time computing and their extensions, such as tradeoff in cost, performance, energy, and even the quality of service, can be applied to multi-dimensional optimization in system designs. In this direction, we witness the rapid development of the embedded system industry and join the task force in system designs, especially mobile devices and non-volatile memory systems. Resource management on mobile devices, with a special emphasis on user experience, should not only consider the response time but also the visual perception of users. Non-volatile memory has also blurred the boundary between the memory and the storage. It enables certain unified considerations of the main memory and storage and also in-memory computing. It shows the ways to break the boundaries between hardware and software layers and have better integration of computing and memory/storage units. The advances in mobile systems and memory innovations inspire the evolution of embedded system designs and have also brought us insights to solutions regarding how systems should be restructured and how computing should be done. They might also provide their feedback to real-time computing and even shape the future direction of real-time computing in various innovative ways.

Numerous studies have investigated the effectiveness of neural network quantization on pattern classification tasks. The present study, for the first time, investigated the performance of speech enhancement (a regression task in speech processing) using a novel exponent-only floating-point quantized neural network (EOFP-QNN). The proposed EOFP-QNN consists of two stages: mantissa-quantization and exponent-quantization. In the mantissa-quantization stage, EOFP-QNN learns how to quantize the mantissa bits of the model parameters while preserving the regression accuracy in the least mantissa precision. In the exponent-quantization stage, the exponent part of the parameters is further quantized without any additional performance degradation. We evaluated the proposed EOFP quantization technique on two types of neural networks, namely, bidirectional long short-term memory (BLSTM) and fully convolutional neural network (FCN), on a speech enhancement task. Experimental results showed that the model sizes can be significantly reduced (the model sizes of the quantized BLSTM and FCN models were only 18.75% and 21.89%, respectively, compared to those of the original models) while maintaining a satisfactory speech-enhancement performance.

Users roaming cellular signal coverage with their mobile devices essentially form a mobile cyber-physical system (CPS). By modeling cyber human mentality and physical signal coverage, as well as their interplay, user mobility can be leveraged to improve users' mobile experience with limited wireless bandwidth. Through a real-world case study, we observed that numerous “null zones” and “hot zones” exist in cellular signal coverage areas, where mobile devices cannot obtain sufficiently high data rates for delay-sensitive applications. Over one third of the locations in a crowded area could have weak signal coverage and low bandwidth shares, resulting in poor mobile connectivity experience. This paper considers the practicality of a mobile CPS called Oasis, which guides users to leave those zones and move to nearby locations with better mobile experience. To realize the system, we model and maximize a user's willingness to travel to another location, where the willingness involves the compound impact of the travel distance and the improved perceptual quality. We also develop a prototype system that creates a feedback control loop to allow self-adaptation to users' needs. To evaluate the efficacy, we conducted a series of experiments based on the real data collected in downtown Taipei, Taiwan. The results demonstrate that our mobile CPS can further reduce the average distance per unit of quality improvement achieved with OpenSignalMaps by about 80%, and motivate further research.

Due to the increasing security concerns, the conventional deletion operations in NAND flash memory can no longer afford the requirement of secure deletion. Although existing works exploit secure deletion and scrubbing operations to achieve the security requirement, they also result in performance and disturbance problems. The predicament becomes more severe as the growing of page numbers caused by the aggressive use of 3-D NAND flash-memory chips which stack flash cells into multiple layers in a chip. Different from existing works, this paper aims at exploring a scrubbing-aware secure deletion design so as to improve the efficiency of secure deletion by exploiting properties of disturbance. The proposed design could minimize secure deletion/scrubbing overheads by organizing sensitive data to create the scrubbing-friendly patterns, and further choose a proper operation by the proposed evaluation equations for each secure deletion command. The capability of our proposed design is evaluated by a series of experiments, for which we have very encouraging results. In a 128 Gbits 3-D NAND flash-memory device, the simulation results show that the proposed design could achieve 82% average response time reduction of each secure deletion command.

Resource-constrained devices with convolutional neural networks (CNNs) for image recognition are becoming popular in various Internet of Things and surveillance applications. They usually have a low-power CPU and limited CPU cache space. In such circumstances, nonvolatile memory (NVM) has great potential to replace DRAM as main memory to improve overall energy efficiency and provide larger main-memory space. However, due to the iterative access pattern, performing CNN-based image recognition may introduce some write hot-spots on the NVM main memory. These write hot-spots may lead to reliability issues due to limited write endurance of NVM. In order to improve the endurance of NVM main memory, this paper leverages the CPU cache pinning technique and exploits the iterative access pattern of CNN to resolve the write hot-spot effect. In particular, we present a CNN-aware self-bouncing pinning strategy to minimize the maximal write cycles in NVM cells by proactively fastening CPU cache lines, so as to effectively suppress the write hot-spots to NVM main memory with limited performance degradation. The proposed strategy was evaluated by a series of intensive experiments and the results are encouraging.

Although the multilevel cell (MLC) technique is widely adopted by flash-memory vendors to boost the chip density and lower the cost, it results in serious performance and reliability problems. Different from past work, a new cell programming method is proposed to not only significantly improve chip performance but also reduce the potential bit error rate. In particular, a single-level cell (SLC)-like programming scheme is proposed to better explore the threshold-voltage relationship to denote different MLC bit information, which in turn drastically provides a larger window of threshold voltage similar to that found in SLC chips. It could result in less programming iterations and simultaneously a much less reliability problem in programming flash-memory cells. In the experiments, the new programming scheme could accelerate the programming speed up to 742% and even reduce the bit error rate up to 471% for MLC pages.

In this paper, we propose a method to realize the Barabási-Albert (BA) model for generating large scale-free networks with preferential attachment. To our knowledge, the existing implementations of the BA model are still not very efficient because they failed to manage the temporary data of the network generating process properly by ignoring the inherent power law degree distribution property. To address this problem, we propose to leverage data structures including a prefix sum max heap and index arrays, which can competently manage nodes with different amount of connections. The proposed method is also friendly to the computing system with non-volatile memory (NVM) as main memory. Reducing long-latency write operations is the key to improve the efficiency of NVM, while the proposed method can ultimately save not only read operations but also significant amount of writes. We compare our proposed method with the baseline methods by generating networks of size from 102nodes to 108nodes. Experiment results show that the proposed method can save up to 50% of write counts. Furthermore, when using the phase change memory, a new byte-addressable non-volatile memory, as main memory, the proposed method can be almost two times faster.

This paper presents a Virtual Persistent Cache design to remedy the long latency behavior of the Host-Aware Shingled Magnetic Recording (HA-SMR) drive. Our design keeps the cost-effective model of the existing HA-SMR drives, but at the same time asks the great help from the host system for adaptively providing some computing and management resources to improve the drive performance when needed. The technical contribution is to trick the HA-SMR drives by smartly reshaping the access patterns to HA-SMR drives, so as to avoid the occurrences of long latencies in most cases and thus to ultimately improve the drive performance and responsiveness. We conduct experiments on real Seagate 8 TB HA-SMR drives to demonstrate the advantages of Virtual Persistent Cache over the real workloads from Microsoft Research Cambridge. The results show that the proposed design can remedy most of the long latencies and improve the drive performance by at least 58.11%, under the evaluated workloads.

OLED power management on mobile devices is very challenging due to the dynamic nature of human-screen interaction. This paper presents the design, algorithms, and implementation of a lightweight mobile app called ShiftMask, which allows the user to dynamically shift OLED power to the portion of interest, while dimming the remainder of the screen based on visual acuity. To adapt to the user's focus of attention, we propose efficient algorithms that consider visual fixation in static scenes, as well as changes in focus and screen scrolling. The results of experiments conducted on a commercial smartphone with popular interactive apps demonstrate that ShiftMask can achieve substantial energy savings, while preserving acceptable readability.

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

In a multi-core platform, resources, such as memory banks and buses, are mostly shared among all cores for power, performance, and cost reasons. The access interference on the shared resources poses a major challenge on the analysis of real-time properties, but can be alleviated if task data partition onto memory banks is applied with care. In this paper, we consider to schedule RAS (resource access sporadic) tasks onto a platform consisting of homogeneous cores and capacity-limited memory banks. According to our observation, we should avoid internal data spreading among the memory banks for a task while advocate external data spreading among memory banks for a given task set. We propose a two-phase algorithm with (4 + ρ + 3(2γ+1)/γ) speedup factor and (γ + 1) memory augmentation factor, where ρ γ 0 and ρ ≥ 1. The derived adjustable resource augmentation factors can be useful in terms of system synthesis and schedulability. Moreover, under the premise that a given task set is feasible, we devise a bi-section approach that can derive a schedulable solution requiring the least amount of memory augmentation. According to our experiment results, the proposed algorithm significantly outperformed the state-of-the-art algorithm [15] in terms of schedulability test even when memory augmentation is prohibited.

With the joint considerations of reliability and performance, hybrid error correction code (ECC) becomes an option in the designs of solid-state drives (SSDs). Unfortunately, wear leveling (WL) might result in the early performance degradation to SSDs, which is common with a limited number of P/E cycles, due to the efforts to delay the bit-error-rate growth. In this paper, an anti-WL design is proposed to avoid such a performance problem so that the performance of SSDs with hybrid ECC capability can be improved without sacrificing their reliability. The capability of the proposed design was evaluated by a series of experiments, for which it was shown that the proposed design could greatly improve the read and write performance of SSDs up to 50% without affecting the endurance of the investigated SSDs, compared with traditional approaches.

Application paradigms will increasingly exceed a mobile device's physical boundaries. This paper presents a system solution for a mobile device to mount remote sensors on other devices. Our design is generic to mobile senor stacks, thus supporting unmodified apps and commodity sensors. Furthermore, it uses an asynchronous access model to facilitate semantics passing and data reporting in between. Such semantic information allows the development of an energy-efficient reporting policy for remote sensing applications. The results of experiments conducted on commercial Android smartphones with popular apps demonstrate that our design is very efficient in terms of energy consumption and completion time.

How to tolerate fault is a fundamental requirement to the designs of many cyber-physical systems. Devices or sensors might have different requirements on their levels of reliability and/or timely services in the composition of a cyber-physical system. In this work, a system framework is explored to virtualize devices/sensors and service migration is considered during run time, so that faults are masked and the timeliness in services is enhanced. In particular, a disaster messaging system supporting seamlessly service recovery in small and large scale network is developed and evaluated, where an acceptable level of connectivity in the face of numerous faults for responsive deliveries of information critical to the success of emergency response and rescue operations. The framework also takes into account the energy consumption and reliability of sensing services, while using different types of memory components. Last but not least, augmented sensing using smart phones allows users to receive the sensed information nearby; this is critical when communication infrastructures are damaged.

Energy harvesting wearable sensor nodes offer low maintenance and high mobility, but suffer from unstable power supply and insufficient energy. Featuring low standby power and instant backup and restore operations, nonvolatile processors have emerged as one of the most promising technologies for the improvement of energy harvesting wearable devices. However, device quality of service (QoS) is still limited by lack of sufficient energy. To address this problem, this paper attempts to maximize QoS by optimizing task scheduling for DVFS-enabled nonvolatile processor-based embedded devices. First, we model the task scheduling problem as an optimization problem to maximize the total value (which represents QoS) given available harvested energy and time. We then prove the problem to be NP-hard. In addition, we propose a pseudopolynomial-time optimal algorithm based on dynamic programming, as well as an approximation algorithm that allows for a trade-off between running time and total value. We evaluate algorithm performance on an ultra-lowpower platform produced by Texas Instruments, and conduct extensive simulations with different system models and task sets. The results demonstrate that the platform can execute optimal sequences derived by the dynamic-programming algorithm, with differences between simulation results and real traces of less than 1%. Also, our approximate algorithm executes approximately 10 5 times faster than the dynamic-programming algorithm at a value degradation cost of less than 3%.

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

The market trend of flash memory chips has been toward high density but with low reliability. The rapidly increasing bit error rates and emerging reliability issues of the coming triple-level cell and even three-dimensional flash chips will expose users to extremely high risks for storing data in such low reliability storage media. With these concerns in mind, this paper rethinks the layer design of flash devices and proposes a complete paradigm shift to re-configure physical flash chips of potentially massive parallelism into better “virtual chips”, in order to improve the data recoverability in a modular and low-cost way. The concept of virtual chips is realized by reinforcing the hardware abstraction layer without continually complicating the conventional flash management software of the flash translation layer. The capability and compatibility of the proposed design were verified by both property analysis and a series of experiments with encouraging results.

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

Mobile applications will become progressively more complicated and diverse. Heterogeneous computing architectures like big.LITTLE are a hardware solution that allows mobile devices to combine computing performance and energy efficiency. However, software solutions that conform to the paradigm of conventional fair scheduling and governing are not applicable to mobile systems, thereby degrading user experience or reducing energy efficiency. In this article, we exploit the concept of application sensitivity, which reflects the user’s attention on each application, and devise a user-centric scheduler and governor that allocate computing resources to applications according to their sensitivity. Furthermore, we integrate our design into the Android operating system. The results of experiments conducted on a commercial big.LITTLE smartphone with real-world mobile apps demonstrate that the proposed design can achieve significant gains in energy efficiency while improving the quality of user experience.

Improving PCM endurance is a fundamental issue when it is considered as an alternative to replace DRAM as main memory. Memory-based wear leveling (WL) is an effective way to improve PCM endurance, but its major challenge is how to efficiently determine the appropriate memory pages for allocation or swapping. In this article, we present a constant-cost WL design that is compatible with existing memory management. Two implementations, namely bucket-based and array-based WL, with constant-time (or nearly zero) search cost are proposed to be integrated into the OS layer and the hardware layer, respectively, as well as to trade between time and space complexity. The results of experiments conducted based on an implementation in Android, as well as simulations with popular benchmarks, to evaluate the effectiveness of the proposed design are very encouraging.

This work is motivated by the demand for scheduling tasks upon the increasingly popular island-based many-core architectures. On such an architecture, homogeneous cores are grouped into islands, each of which is equipped with a scratchpad memory module (referred to as local memory). We first show the NP-hardness and the inapproximability of the scheduling problem. Despite the inapproximability, positive results can still be found when different cases of the problem are investigated. A$(3-\frac{1}{F})$- approximation algorithm is proposed for the minimization of the maximum system utilization, where$F$is the number of cores in the platform. When the technique of resource augmentation is considered, this paper further develops a$(\gamma +1)$-memory$\frac{2\gamma -1}{\gamma -1}$-approximation algorithm, where$\gamma$represents the trade-off between CPU utilization and local memory space. On the other hand, a special case is also considered when the ratio of the worst-case execution time of a task without and with using the local memory is bounded by a constant. The capabilities of the proposed algorithms are then evaluated with benchmarks from MRTC, UTDSP, NetBench and DSPstone, where the maximum system utilization can be significantly reduced even when the local memory size is only 5 percent of the total footprint of all of the tasks.

As the endurance of flash memory keeps deteriorating, exploiting wear leveling (WL) techniques to improve the lifetime/endurance of flash memory has become a critical issue in the design of flash storage devices. Nevertheless, the deteriorated access performance of high-density flash memory makes the performance overheads introduced by WL non-negligible. In particular, the existing WL designs usually aggressively distribute the erases to all flash blocks evenly in a regular basis. As a result, a lot of non-negligible unnecessary data migrations would be imposed in the early stages of the device lifespan, and would be further exacerbated if a WL design selects improper victim blocks for erases. In contrast to the existing WL approaches, we propose a progressive WL design to perform WL in a progressive way to prevent any block from being worn out prematurely with minimized performance overheads caused by the unnecessary data migration. The experiments were conducted based on representative realistic workloads to evaluate the efficacy of the proposed design. The results reveal that instead of sacrificing the device lifetime, performing WL in such a progressive way can not only minimize the performance overheads but also have potentials to extend the device lifetime.

Although the Multi-Level-Cell technique is widely adopted by flash-memory vendors to boost the chip density and to lower the cost, it results in serious performance and reliability problems. Different from the past work, a new cell programming method is proposed to not only significantly improve the chip performance but also reduce the potential bit error rate. In particular, a Single-Level-Cell-like programming style is proposed to better explore the threshold-voltage relationship to denote different Multi-Level-Cell bit information, which in turn drastically provides a larger window of threshold voltage similar to that found in Single-Level-Cell chips. It could result in less programming iterations and simultaneously a much less reliability problem in programming flash-memory cells. In the experiments, the new programming style could accelerate the programming speed up to 742% and even reduce the bit error rate up to 471% for Multi-Level-Cell pages.

The market trend of flash memory chips has been going for high density but low reliability. The rapidly increasing bit error rates and emerging reliability issues of the coming triple-level cell (TLC) and even three-dimensional (3D) flash chips would let users take an extremely high risk to store data in such low reliability storage media. With the observations in mind, this paper rethinks the layer design of flash devices and propose a complete paradigm shift to re-configure physical flash chips of potentially massive parallelism into better "virtual chips", in order to improve the data recoverability in a modular and low-cost way. The concept of virtual chips is realized at hardware abstraction layer (HAL) without continually complicating the conventional flash management software (i.e., flash translation layer (FTL)). The capability and compatibility of the proposed design are then verified by a series of experiments with encouraging results.

The replacement of DRAM with non-volatile memory relies on solutions to resolve the wear leveling and slow write problems. Different from the past work in compiler-assisted optimization or joint DRAM-PCM management strategies, we explore a light-weighted software-controlled DRAM cache design for the non-volatile-memory-based main memory. The run-time overheads in the management of the DRAM cache is minimized by utilizing the information from a miss of the translation lookaside buffer (TLB) or the cache. Experiments were conducted based on a series of the well-known benchmarks to evaluate the effectiveness of the proposed design, for which the results are very encouraging.

With the rapidly-increasing capacity demand over flash memory, 3D NAND flash memory has drawn tremendous attention as a promising solution to further reduce the bit cost and to increase the bit density. However, such advanced 3D devices will suffer more intensive program disturbance, compared to 2D NAND flash memory. Especially when multi-level-cell (MLC) technology is adopted, the deteriorated disturbance due to the program operations of intra and inter pages will become even more critical for reliability. In contrast to the past efforts that try to resolve the reliability issue with error correction codes or hardware designs, this work seeks for the redesign of the program operation. A disturb-aware programming scheme is proposed to not only relax the disturbance induced by slow cells as much as possible but also reduce the possibility in requiring a high voltage to program the slow cells. A series of experiments was conducted based on real 3D MLC flash chips, and the results demonstrate that the proposed scheme is extremely effective on reducing the disturbance as well as the bit error rate.

Graphics-intensive mobile games are becoming increasingly popular, but such applications place high demand on device CPUs and GPUs. The design of current mobile systems results in unnecessary energy waste due to lack of consideration of application phases and user attention (a “demand-level” gap) and because each processor administers power management autonomously (a “processor-level” gap). This paper proposes a user-centric CPU-GPU governing framework which aims to reduce energy consumption without significantly impacting the user experience. To bridge the gap at the demand level, we identify the user demand at runtime and accordingly determine appropriate governing policies for the respective processors. On the other hand, to bridge the gap at the processor level, the proposed framework interprets the frequency scaling intents of processors based on the observation of the CPU-GPU interaction and the processor status. We implemented our framework on a Samsung Galaxy S4, and conducted extensive experiments with real-world 3D gaming apps. Experimental results showed that, for an application being highly interactive and frequent phase changing, our proposed framework can reduce energy consumption by 45.1% compared with state-of-the-art policy without significantly impacting the user experience.

The growing popularity of embedded Multi-Media Controllers (eMMCs) presents a unique opportunity to design commodity grade solid-state drives products. This work addresses the essential design issues of such drives and introduces a light-weight FTL design. In particular, access patterns to an eMMC-enabled solid-state drive are reshaped to create sequential access patterns and specific write sizes to better accommodate the characteristics of eMMCs, without resorting to the conventional address translation FTL design. At the same time, garbage collection overheads are minimized with reliability considerations, since eMMCs are usually not equipped with a powerful controller of a sophisticated design. The capability of the proposed design is evaluated by a series of experiments, for which we have very encouraging results.

Improving the performance of storage systems without losing the reliability and sanity/integrity of file systems is a major issue in storage system designs. In contrast to existing storage architectures, we consider a PCM-based storage architecture to enhance the reliability of storage systems. In PCM-based storage systems, the major challenge falls on how to prevent the frequently updated (meta)data from wearing out their residing PCM cells without excessively searching and moving metadata around the PCM space and without extensively updating the index structures of file systems. In this work, we propose an adaptive wear-leveling mechanism to prevent any PCM cell from being worn out prematurely by selecting appropriate data for swapping with constant search/sort cost. Meanwhile, the concept of indirect pointers is designed in the proposed mechanism to swap data without any modification to the file system's indexes. Experiments were conducted based on well-known benchmarks and realistic workloads to evaluate the effectiveness of the proposed design, for which the results are encouraging.

With the increasing number of cores in a computing system, how to coordinate the computing units and heterogeneous memory resources has soon become extremely critical for real-time systems. This paper explores the joint considerations of memory management and real-time task scheduling over island-based multi-core architecture, where the local memory module of an island offers shorter access time than the global memory module does. The objective of this work is to minimize the number of needed islands to successfully schedule real-time tasks. When the required amount of the local memory space is specified for each task, a scheduling algorithm is proposed to provide an asymptotic 299-approximation bound. When there is flexibility in determining the needed local memory space for each task, we propose an algorithm with an asymptotic 4-approximation bound to jointly manage memory resources and allocate computing cores. In addition to the worst-case approximation analysis, the proposed algorithms are also evaluated with 82 real-life benchmarks with the support of a worst-case execution time analyzer. Moreover, extensive evaluations are conducted to show the capability of the proposed approaches when being used with various computing cores and memory resources.

Manufacturers are constantly seeking to increase flash memory density in order to fulfill the ever growing demand for storage capacity. However, this trend significantly reduces the reliability and endurance of flash memory chips. The lifetime degradation worsens as the number of erase cycles grows, even with wear leveling technology being adopted to extend flash memory lifetime by evenly distributing erase cycles to every flash block. To address this issue, self-healing technology is proposed to recover a flash block before the flash block is worn out, but such a technology still has its limitation when recovering flash blocks. In contrast to the existing wear leveling designs, we adopt the self-healing technology to propose a heal-leveling design that evenly distributes healing cycles to flash blocks. Ultimately, heal-leveling aims to extend the lifetime of flash memory without introducing a large amount of live-data copying overheads. We conducted a series of experiments to evaluate the capability of the proposed design. The results show that our design can significantly improve the access performance and the effective lifetime of flash memory without the unnecessary overheads caused by wear leveling technology.

There are many timing unreliable computing components in modern computer systems, which are typically forbidden in hard real-time systems due to the timing uncertainty. In this paper, we propose a computation offloading mechanism to utilise these timing unreliable components in a hard real-time system, by providing local compensations. The key of the mechanism is to decide (1) how the unreliable components are utilized and (2) how to set the worst-case estimated response time. The local compensation has to start when the unreliable components do not deliver the results in the estimated response time. We propose a scheduling algorithm and its schedulability test to analyze the feasibility of the compensation mechanism. To validate the proposed mechanism, we perform a case study based on image-processing applications in a robot system and simulations. By adopting the timing unreliable components, the system can handle higher-quality images and with better performance.

Mobile devices will provide improved computing resources to sustain progressively more complicated applications. However, the design concept of fair scheduling and governing borrowed from legacy operating systems cannot be applied seamlessly in mobile systems, thereby degrading user experience or reducing energy efficiency. In this paper, we posit that mobile applications should be treated unfairly. To this end, we exploit the concept of application sensitivity and devise a user-centric scheduler and governor that allocate computing resources to applications according to their sensitivity. Furthermore, we integrate our design into the Android operating system. The results of extensive experiments on a commercial smartphone with real-world mobile apps demonstrate that the proposed design can achieve significant energy efficiency gains while improving the quality of user experience.

With the rapid growth of mobile data traffic, operators are expected to densely deploy base stations to meet user demands. Recent researches have indicated that the densely deployed base stations lead to the significant increase of the operational expenses of operators due to the electricity bills to maintain their operation, and thus the profit of operators is greatly decreased. Different from the past works in dynamically switching on/off base stations for energy saving, we propose to consider the benefits of users in service fee discounts as a joint optimization process in cutting down the energy consumption of base stations to maximize the total profit of operators. The optimization problem is formulated and shown being NP-hard. We then propose a profit-aware algorithm to switch off base stations, as needed, with the adjustment of the data rates provided to the users who are willing to receive discounts. The simulation results show that the proposed algorithm can significantly increase the total profit of operators and introduce a win-win situation to both users and operators.

This work is motivated by the needs to synchronize task executions where tasks might use semaphores to protect their critical sections and run over accelerators. In particular, the Priority Ceiling Protocol is extended to manage priority inversion caused by accelerator usages. By recognizing the difference between an accelerator and a semaphore, higher-priority tasks are less likely blocked by lower-priority tasks, due to their requests for an accelerator. In particular, blocking that will not contribute to any deadlock and/or chained blocking is allowed in a managed way, with an objective to maximize the utilization of accelerators. A series of experiments is then conducted to derive insights to task synchronization when accelerators might be used.

This work is motivated by the advance of heterogeneous computing and the strong demands of workload acceleration in practice. By considering pipeline workloads over FPGA, this paper explores a systematic methodology to configure the hardware instances of each pipeline stage such that the maximum of the execution time of each stage is minimized, where the FPGA allocation with the memory bandwidth constraint is considered. For the target problem, an algorithm is proposed and proved being optimal, and a real implementation study is conducted. In the experimental results, an image filter FPGA implementation can outperform the CPU, GPU, and baseline FPGA solutions by 460%, 73%, and 1030%, respectively. Extensive simulations were also conducted with a large FPGA size to show the scalability of this work.

As NAND flash memory has become a major choice of storage media in diversified computing environments, the performance issue of flash memory has been extensively addressed in many excellent designs. Among them, an effective strategy is to adopt multiple channels and flash-memory chips to improve the performance on data accesses. However, the degree of data access parallelism cannot be increased by simply increasing the number of channels and chips in the storage device, because it is seriously limited by the maximum current constraint of the bus interface and affected by the access patterns of user data. As a consequence, to maximize the degree of access parallelism, it is of paramount significance to have a proper scheduling strategy to determine the order that read/write requests are served. In this paper, a current-aware scheduling strategy for read/write requests is proposed to maximize the read performance without violating the bus current constraint and without missing (the deadline of) written data. The proposed strategy is then evaluated through a series of experiments, in which the results are quite encouraging.

Summary form only given. As flash memory gains its huge momentum in the storage market, people have high expectation on other potential roles that could be played by non-volatile memory. It has been a grand challenge to position selected non-volatile memory technologies in the memory hierAs flash memory gains its huge momentum in the storage market, people have high expectation on other potential roles that could be played by non-volatile memory. It has been a grand challenge to position selected non-volatile memory technologies in the memory hierarchy. In this talk, I will take flash memory and phased change memory (PCM) as examples to address the challenges and design methodologies for non-volatile memory as a storage medium or to serve as the role of DRAM. The talk will be concluded by moving the discussion forward to the opportunities of non-volatile memory in system designs, such as server cache and data storage in data manipulation.archy. In this talk, I will take flash memory and phased change memory (PCM) as examples to address the challenges and design methodologies for non-volatile memory as a storage medium or to serve as the role of DRAM. The talk will be concluded by moving the discussion forward to the opportunities of non-volatile memory in system designs, such as server cache and data storage in data manipulation.

As cloud computing gains its momentum in big data processing and providing on-line services, there are increasing demands to offer responsive services to users and to improve the effectiveness in server utilization. Most previous work studied the fairness among user requests, the workload balancing among servers, and the support of real-time applications individually. Different from those state-of-the-art work, we focus on the joint considerations of workload balancing and deadline satisfaction in facing user requests for MapReduce. In particular, scheduling algorithms are proposed with a constant approximation bound to balance the server workloads and, at the same time to meet the response time requirements of MapReduce jobs. The proposed scheduling algorithms are then implemented with our proposed resource manager for the open source implementation of Hadoop. We evaluate our design based on performance metrics including balancing server workloads and meeting jobs' response-time requirements. Experimental results show the effectiveness of our design through real testbed implementation.

Recently, storage systems have observed a great leap in performance, reliability, endurance, and cost, due to the advance in non-volatile memory technologies, such as NAND flash memory. However, although delivering better performance, shock resistance, and energy efficiency than mechanical hard disks, NAND flash memory comes with unique characteristics and operational constraints, and cannot be directly used as an ideal block device. In particular, to address the notorious write-once property, garbage collection is necessary to clean the outdated data on flash memory. However, garbage collection is very time-consuming and often becomes the performance bottleneck of flash memory. Moreover, because flash memory cells endure very limited writes (as compared to mechanical hard disks) before they are worn out, the wear-leveling design is also indispensable to equalize the use of flash memory space and to prolong the flash memory lifetime. In response, this paper surveys state-of-the-art garbage collection and wear-leveling designs, so as to assist the design of flash memory management in various application scenarios. The future development trends of flash memory, such as the widespread adoption of higher-level flash memory and the emerging of three-dimensional (3D) flash memory architectures, are also discussed.

Minimizing the booting time of an embedded system has become a major technical issue for the success of many consumer electronics. In this paper, the booting time minimization problem for real-time embedded systems with the joint consideration of DRAM and non-volatile memory is formally formulated. We show this is an NP-hard problem, and propose an optimal but pseudo-polynomial-time algorithm with dynamic programming techniques. In considering polynomial-time solutions, a 0.25-approximation greedy algorithm is provided, and a polynomial-time approximation scheme is developed to trade the optimality of the derived solution for the time complexity according to a user-specified error bound. The proposed algorithms can manage real-time embedded systems consisting of not only real-time tasks, but also initialization tasks that are executed only once during system booting. The proposed algorithms were then evaluated with 65 real benchmarks from the MRTC and DSPstone benchmark suites, and the results showed that all of the proposed algorithms can reduce booting time for each benchmark set by more than 29 percent. Moreover, extensive simulations were conducted to show the capability of the proposed approaches when used with various hardware resources and software workloads.

This work is motivated by the strong demand for flash-friendly index designs to resolve reliability and performance concerns for data manipulation over flash memory. In comparison to previous work, we propose and explore the impact of hot-data access, sibling-link updates, and different workload types to a tree index structure over flash memory. In particular, a flash-friendly${B^ + }$-tree, referred to as an Adaptive Durable${B^ + }$-tree, is proposed to not only improve the endurance but also the performance of a tree index structure. The capability of the proposed methodology and index design is evaluated through a series of experiments, in which significant improvement on endurance was achieved in comparison to previous reports on the subject.

As flash memory emerges as a high-performance and energy-efficient alternative for storage devices, how to accommodate disk-based storage servers with a flash-memory cache might provide a promising solution to resolve the energy-efficiency concerns of storage servers and their data centers. In this work, we propose a cache design method over flash memory without any additional hardware support for storage servers. In particular, a scalable set-associative flash-cache management design is proposed to significantly improve the flash endurance with excellent caching response time and hit rates. The capability of the proposed scheme was evaluated by extensive experiments over Microsoft’s server traces, in which significant improvement on endurance was achieved, compared to existing work.

No abstract available.

Real-time task scheduling becomes even more challenging with the emerging of island-based multi-core architecture, where the local memory module of an island offers shorter access time than the global memory module does. With such a popular architecture design in mind, this paper exploits real-time task scheduling over island-based homogeneous cores with local and global memory pools. Joint considerations of real-time scheduling and memory allocation are presented to efficiently use the computing and memory resources. A polynomial-time algorithm with an asymptotic 4-approximation bound is proposed to minimize the number of needed islands to successfully schedule tasks. To evaluate the performance of the proposed algorithm, 82 benchmarks from the MRTC, MediaBench, UTDSP, NetBench, and DSPstone benchmark suites were profiled by a worst-case-execution-time analyzer aiT and included in the experiments.

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

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

In recent years, reliability has become one critical issue in the designs of flash-memory file/storage systems, due to the growing unreliability of advanced flash-memory chips. In this paper, a version-based design is proposed to effectively and efficiently maintain the consistency among page versions of a file for potential recovery needs. In particular, a two-version one for a native file system is presented with the minimal overheads in version maintenance. A recovery scheme is then presented to restore a corrupted file back to the latest consistent version. The design is later extended to maintain multiple data versions with the considerations of the write constraints of multilevel-cell flash memory. It was shown that the proposed design could significantly improve the reliability of flash memory with limited management and space overheads.

Due to its remarkable access performance, shock resistance, and costs, NAND flash memory is now widely adopted in a variety of computing environments, especially in mobile devices such as smart phones, media players and electronic book readers. For the consideration of costs, low-cost embedded flash storages such as flash memory cards are often employed on such devices. Different from solid-state disks, the RAM buffer equipped on low-cost embedded flash storages are very small, for example, limited under several dozens of kilobytes, despite of the rapidly growing capacity of the storages. The significance of effectively utilizing the very limited on-device RAM buffers of embedded flash storages is therefore highlighted, and a novel design of scalable flash management schemes is needed to tackle the new access constraints of MLC NAND flash memory. In this work, a highly scalable design of the flash translation layer is presented with the considerations of the on-device RAM size, user access patterns, address-mapping-information caching and MLC access constraints. Through a series of experiments, it is verified that, with appropriate settings of cache sizes, the proposed management scheme provides comparable performance results to prior arts with much lower requirements on the on-device RAM. In other words, the proposed scheme suggests a strategy to make better use of the on-device RAM, and is suitable for embedded flash storages.

Simulation is a common approach for assisting system design and optimization. For system-wide optimization, energy and computational resources are often the two most critical limitations. Modeling energy-states of each hardware component and time spent in each state is needed for accurate energy and performance prediction. Tracking software execution in a realistic operating environment with properly modeled input/output is key to accurate prediction. However, the conventional approaches can have difficulties in practice. First, for a complex system such as an Android smartphone, building a cycle-accurate simulation environment is no easy task. Secondly, for I/O-intensive applications, a slow simulation would significantly alter the application behavior and change its performance profile. Thirdly, conventional software profiling tools generally do not work on simulators, which makes it difficult for performance analysis of complicated software, e.g., Java applications executed by the Dalvik virtual machine. Recently, virtual machine technologies are widely used to emulate a variety of computer systems. While virtual machines do not model the hardware components in the emulated system, we can ease the effort of building a simulation environment by leveraging the infrastructure of virtual machines and adding performance and power models. Moreover, multiple sets of the performance and energy models can be selectively used to verify if the speed of the simulated system impacts the software behavior. Finally, performance monitoring facilities can be integrated to work with profiling tools. We believe this approach should help overcome the aforementioned difficulties. We have prototyped a framework and our case studies showed that the information provided by our tools are useful for software optimization and system design for Android smartphones.

Improving the endurance of PCM is a fundamental issue when the technology is considered as an alternative to main memory usage. In the design of memory-based wear leveling approaches, a major challenge is how to efficiently determine the appropriate memory pages for allocation or swapping. In this paper, we present an efficient wear-leveling design that is compatible with existing virtual memory management. Two implementations, namely, bucket-based and array-based wear leveling, with nearly zero search cost are proposed to tradeoff time and space complexity. The results of experiments conducted based on popular benchmarks to evaluate the efficacy of the proposed design are very encouraging.

The popularity of flash memory has triggered the emerging of various products with flash memory as storage medium. More advanced architectures with better hardware resources are now explored by vendors to fit different market needs. Different from the past work, this paper proposes to consider RAM as a storage medium together with flash memory to take advantage of the characteristics of both RAM and flash memory. In particular, an adaptive management strategy is proposed with the considerations of access patterns to improve both the system performance and the system endurance. The capability of the proposed approach is evaluated by a series of experiments, for which we have very encouraging results.

This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2-⁄2M+1)-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, MediaBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm.

A major challenge in the design of multicore embedded systems is how to tackle the communications among tasks with performance requirements and precedence constraints. In this paper, we consider the problem of scheduling real-time tasks over multilayer bus systems with the objective of minimizing the communication cost. We show that the problem is NP-hard and determine the best possible approximation ratio of approximation algorithms. First, we propose a polynomial-time optimal algorithm for a restricted case where one multilayer bus, and the unit execution time and communication time are considered. The result is then extended as a pseudopolynomial-time optimal algorithm to consider multiple multilayer buses with arbitrary execution and communication times, as well as different timing constraints and objective functions. We compare the performance of the proposed algorithm with that of some popular heuristics, and provide further insights into the multilayer bus system design.

As flash memory becomes popular over various platforms, there is a strong demand regarding the performance degradation problem, due to the special characteristics of flash memory. This research proposes the design of a file-system-oriented flash translation layer, in which a filter mechanism is designed to separate the access requests of file-system metadata and file contents for better performance. A recovery scheme is then proposed for maintaining the integrity of a file system. The proposed flash translation layer is implemented as a Linux device driver and evaluated with respect to ext2 and ext3 file systems. Experiments were also done over NTFS by a series of realistic traces. The experimental results show significant performance improvement over ext2, ext3, and NTFS file systems with limited system overheads.

With the growing popularity of 3G-powered devices and their serious energy consumption problem, there are growing demands on energy-efficient data transmission strategies for various embedded systems. Different from the past work in energy-efficient real-time task scheduling, we explore strategies to maximize the amount of data transmitted by a 3G module under a given battery capacity. In particular, we present algorithms under different workload configurations with and without timing constraint considerations. Experiments were then conducted to verify the validity of the strategies and develop insights in energy-efficient data transmission.

In recent years, reliability has become one critical issue in the designs of flash file systems due to the growing unreliability of advanced flash-memory chips. In this paper, a version-based strategy with optimal space utilization is proposed to maintain the consistency among page versions of a file for potential recovery needs with the considerations of the write constraints of multi-level-cell flash memory. A series of experiments was conducted to show that the proposed strategy could improve the reliability of flash file systems with limited management and space overheads.

With the emergence of many-core systems, managing blocking costs effectively will soon become a critical issue in the design of real-time systems. In contrast to previous works on multi-core real-time task scheduling algorithms and synchronization protocols, this paper proposes a dedicated-core framework to separate the executions of application tasks and (system) services over cores such that blocking among tasks can be better explored and managed. The rationale behind the framework is that we can exploit the characteristics of many-core systems to resolve the challenges raised by the systems themselves. We define three core minimization problems with respect to the constraints on core configurations, and present corresponding task allocation algorithms with optimal, approximate, and heuristic solutions. The results of simulations conducted to evaluate the proposed framework provide further insights into task scheduling in many-core real-time systems.

With the strong demands in the fast start-up of many mobile devices, hibernation has shown its clear superiority in such system designs. Different from the past work, a methodology is proposed to downsize the hibernation image without sacrificing the user experience in the resuming procedure of hibernation. Two approximation algorithms with bounds are proposed to remove selected pages from the hibernation image and shift them to page-in activities. The proposed methodology was evaluated over a series of experiments, for which we had more than 10% of improvement on the resuming time for many system configurations.

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

The growing popularity of flash memory is expected to draw attention to the limitations of file-system performance over flash memory. This work was motivated by the modular designs of operating system components such as bus and device drivers. A filter-driver-layered caching design is proposed to resolve the performance gap among file systems and to improve their performance with the considerations of flash memory characteristics. An efficient hybrid tree structure is presented to organize and manipulate the intervals of cached writes. Algorithms are proposed in the merging, padding, and removing of the data of writes. The effectiveness of the proposed approach is demonstrated with some analysis study of FAT-formatted and NTFS-formatted USB flash disks. The proposed cohesive caching policy was implemented as a filter driver in Windows XP/Vista for performance evaluation. In the experiments, a ten-fold or larger performance improvement was usually achieved when the cache size was only 64KB. Other substantial improvements were also observed in the experiments. For example, the proposed design enabled FAT-formatted and NTFS-formatted flash-memory devices to copy Linux image files 93% and 14% faster than conventional flash drives, respectively.

Leakage power consumption contributes significantly to the overall power dissipation for systems that are manufactured in advanced deep sub-micron technology. Different from many previous results, this paper explores leakage-aware energy-efficient scheduling if leakage power consumption depends on temperature. We propose a pattern-based approach which divides a given time horizon into several time segments with the same length, where the processor is in the active (dormant, respectively) mode for a fixed amount of time at the beginning (end, respectively) of each time segment. Computation is advanced in the active mode, whereas the dormant mode helps reduce the temperature via cooling as well as the leakage power consumption. Since the pattern-based approach leads to a steady state with an equilibrium temperature, we develop a procedure to find the optimal pattern whose energy consumption in steady state is the minimum. Compared to existing work, our approach is more effective, has less run-time scheduling overhead, and requires only a simple scheduler to control the system mode periodically. The paper contains extensive simulation results which validate the new models and methods.

Virtualization provides an excellent solution to resolve the portability, maintainability, development, and utilization problems in many system designs. In this paper, we are interested in energy-efficient designs for platform virtualization. In particular, we explore the computing resource mapping and the energy consumption relationship between virtual cores and physical cores when timing constraints in task executions are considered. Real-time and non-real-time task workloads are both considered in the study, where the computing needs of each virtual core are modeled with a computing server. A prototype with dynamic-voltage-scaling support is implemented based on a μ-kernel architecture. The capability and overheads of the proposed design was evaluated, for which we have encouraging results.

The reliability of flash-memory chips has dropped dramatically in recent years. In order to solve this problem, a reliable memory technology device (MTD) design is proposed to address this concern at the device driver layer so as to release the design complexity of flash-memory management software/firmware and to improve the maintainability and portability of flash management designs for existing and future products. The proposed design was evaluated through a series of experiments based on realistic traces to show that the proposed approach could significantly improve the reliability of flash memory with limited overheads.

Multi-dimensional temporal data set is the common format in sensor network applications to store sampled temporal data. As time goes on, the size of the core tables in the data set may increase to enormous size and the tables become not managable. In order to reduce storage space and allow on-line query, how to trade off data compression effectiveness for on-line query performance is a challenge issue. In this paper, we are concerned with an effective framework for temporal data set that does not scarify on-line query performance and is specifically designed for very large sensor network database. The sampled data are compressed using several candidate approaches including dictionary-base compress and lossless vector quantization. In the mean time, on-line queries are conducted without decompressing the compressed data set so as to enhance the query performance. Experiments are conducted on a power meter database and sonoma database to evaluate the proposed methodologies in terms of data compression rate and data query speed. The results show that the compression rate ranges from 70% for numerical data to 20% for character data. In the mean time, the increased overhead for online query is limited up to 2%.

Although solid-state drives seem being excellent alternatives to replace hard disks in mobile devices, serious challenges arise due to performance and reliability concerns. This work targets performance enhancement designs with the considerations of low-cost MLC flash memory. In particular, an efficient flash management design is proposed to manage multi-chipped flash memory with cache support, where a two-level address translation mechanism is presented with an adaptive caching policy. The capability of the proposed approach is evaluated with a SystemC-based solid-state-drive simulator based on realistic workloads and benchmarks. It was shown that the proposed approach could significantly improve the performance of multi-chipped solid-state drives over various hardware configurations.

Motivated by the strong demand for flash memory with enhanced reliability, this work attempts to achieve improved flash-memory endurance without substantially increasing overhead and without excessively modifying popular implementation designs such as the flash translation layer protocol (FTL), NAND flash translation layer protocol (NFTL), and block-level flash translation layer protocol (BL). A wear-leveling mechanism for moving data that are not updated is proposed to distribute wear-leveling actions over the entire physical address space, so that static or rarely updated data can be proactively moved and memory-space requirements can be minimized. The properties of the mechanism are then explored with various implementation considerations. A series of experiments based on a realistic trace demonstrates the significantly improved endurance of FTL, NFTL, and BL with limited system overhead.

While the capacity of flash-memory storage systems keeps increasing significantly, an effective and efficient management of flash-memory space has become a critical design issue. Different granularities in space management impose different management costs and mapping efficiency. In this paper, we will explore an address translation mechanism (AddrTM) that can dynamically and adaptively switch between different granularities in the mapping of logical block addresses into physical block addresses in flash-memory management. The objective is to provide high performance in address mapping and space utilization and, at the same time, to have the main memory requirements, the garbage collection overhead, and the system initialization time under proper management. The experimental results show that the proposed adaptive mechanism can provide better performance improvement and practicability than other well-known coarse-grained management mechanisms over realistic workloads.

In the past decade, energy-efficient real-time task scheduling has been widely explored in the form of various optimization problems. This paper considers energy-efficient real-time task synchronization protocols and the overhead of frequency switching in real systems design. We propose the concept of frequency locking to better manage the cost in frequency switching. To minimize the energy consumption and meet the timing constraints, algorithms are presented to assign tasks base frequencies under existing synchronization protocols which are then extended with the frequency locking concept. Finally, a series of extensive simulations is performed and a real case study is presented to evaluate the proposed methodology and obtain comparison studies using different workloads and protocols.

This work is motivated by a strong market demand for the replacement of NOR flash memory with NAND flash memory to cut down the cost of many embedded-system designs, such as mobile phones. Different from LRU-related caching or buffering studies, we are interested in prediction-based prefetching based on given execution traces of application executions. An implementation strategy is proposed for the storage of the prefetching information with limited SRAM and run-time overheads. An efficient prediction procedure is presented based on information extracted from application executions to reduce the performance gap between NAND flash memory and NOR flash memory in reads. With the behavior of a target application extracted from a set of collected traces, we show that data access to NOR flash memory can respond effectively over the proposed implementation.

Cost has been a major driving force in the development of the flash memory technology, but has also introduced serious challenges on reliability and performance for future products. In this work, we propose a commitment-based management strategy to resolve the reliability problem of many flash-memory products. A three-level address translation architecture with an adaptive block mapping mechanism is proposed to accelerate the address translation process with a limited amount of the RAM usage. Parallelism of operations over multiple chips is also explored with the considerations of the write constraints of multi-level-cell flash memory chips.

With wide applicability of flash memory in various application domains, reliability has become a very critical issue. This research is motivated by the needs to resolve the lifetime problem of flash memory and a strong demand in turning thrown-away flash-memory chips into downgraded products. We proposes a set-based mapping strategy with an effective implementation and low resource requirements, e.g., SRAM. A configurable management design and wear-leveling issue are considered. The behavior of the proposed method is also analyzed with respect to popular implementations in the industry.We show that the endurance of flash memory can be significantly improved by a series of experiments over a realistic trace. Our experiments show that the read performance is even largely improved.

As flash memory became popular over various platforms, there is a strong demand on the performance degradation problem, due to the special characteristics of flash memory. This research proposes the design of a file-system-aware flash translation layer, in which a filter mechanism is designed to separate the access requests of file-system metadata and file contents for better performance. A recovery scheme is then proposed to maintain the integrity of a file system. The proposed flash translation layer is implemented as a Linux device driver and evaluated with respect to ext2 and ext3 file systems. The experimental results show significant performance improvement over ext2 and ext3 file systems with limited system overheads.

As application complexity increases, modern embedded systems have adopted heterogeneous processing elements to enhance the computing capability or to reduce the power consumption. The heterogeneity has introduced challenges for energy efficiency in hardware and software implementations. This paper studies how to partition real-time tasks on a platform with heterogeneous processing elements (processors) so that the energy consumption can be minimized. The power consumption models considered in this paper are very general by assuming that the energy consumption with higher workload is larger than that with lower workload, which is true for many systems. We propose an approximation scheme to derive near-optimal solutions for different hardware configurations in energy/power consumption. When the number of processors is a constant, the scheme is a fully polynomial time approximation scheme (FPTAS) to derive a solution with energy consumption very close to the optimal energy consumption in polynomial-time/space complexity. Experimental results reveal that the proposed scheme is very effective in energy efficiency with comparison to the state-of-the-art algorithm.

Dynamic voltage scaling (DVS) has been widely adopted to reduce the energy consumption resulting from the dynamic power of modern processors. However, while the leakage power resulting from the leakage current becomes significant, how to aggregate the idle time to turn processors to the sleep or dormant modes is crucial in reducing the overall energy consumption. Moreover, for systems with non-DVS components, the execution order of tasks also affects the system-wide energy consumption. With the consideration of the dynamic and leakage power of processors as well as the power consumption resulting from non-DVS components, this paper summarizes our work on energy-efficient real-time task scheduling for both uniprocessor and multiprocessor platforms through procrastination of task executions, preemption control, and proper task assignment.

This research is motivated by the demands of personalized storage devices that fit the quality-of-service needs of each individual user. In particular, the design of a virtual storage device, that consists of multiple heterogeneous storage devices, is proposed with the capability in dynamic reconfiguration to fit the needs of users. A dynamic remapping mechanism is presented with a heap-based data structure to manage the moving of data among component storage devices for performance optimization. A lazy swapping method is then proposed to reduce the mapping overheads. The capability of the proposed design is evaluated with a prototype virtual storage device of a flash drive and a hard drive over an ex2 file system and realistic/generated workloads.

This paper describes an embedded workflow framework (EMWF) that enables flexible personal and home automation and assistive devices and service and social robots (collectively referred to as SISARL) to be built on workflow architecture The process definition language supported by EMWF is called SISARL-XPDL. It consists of a subset of the WfMC standard XML Process Definition Language (XPDL) 2.0, together with elements that implement common mechanisms for robot behavior coordination. SISARL-XPDL definitions of workflows are first translated into standard XPDL and execution directives and then are parsed either directly into binary workflow scripts for execution or into intermediate scripts in C. EMWF provides workflow engines for Linux and Windows CE platforms. The engines are written in C in order to keep their memory footprint and runtime overhead small. Performance data show that the overheads introduced by the engine and workflow data are tolerable for most SISARL devices.

Although energy-efficient real-time task scheduling has attracted a lot of attention in the past decade, most existing results assumed deterministic execution lengths for tasks, or probabilistic lengths with a stable distribution. Such an assumption results in significant difficulty in their application to real problems. In this work, we relax this hypothesis by assuming that the worst case execution number of cycles (WCEC) might be imprecisely known. We present several methods to react to such a situation. We provide simulation results attesting that with a small effort, we can provide very good results, allowing to keep a low deadline miss rate as well as an energy consumption similar to clairvoyant algorithms. The main contribution of this work is to improve the robustness of low-power scheduling algorithms on DVFS (Dynamic Voltage and Frequency Scaling) frame-based platforms.

One major challenging issue in the designs of multi-core embedded systems is to tackle the communication problem among tasks with performance requirements and precedence constraints. This paper targets the problem of scheduling real-time tasks with chain-based precedence constraints over multi-layer bus systems with an objective to minimize the bus cost. We show the NP-hardness of the problem and the best possible approximation ratio of approximation algorithms. A polynomial-time optimal algorithm is first proposed for a restricted case in which one multi-layer bus and unit execution and communication times are considered. The result is then extended as a pseudo-polynomial-time optimal algorithm in the considerations of multiple multi-layer buses and arbitrary execution and communication times. The capability of the proposed algorithm was evaluated to provide more insights in system designs, compared to some popular heuristics.

With the popularity of VoIP, Push-To-Talk (PTT) services over the IP networks have gained their momentum. This research aims at essential design issues for the quality of service of PTT services. We explore the relationship between the speech quality and system design issues. MOS (Mean Opinion Score), which is raised by the ITU-T (International Telecommunication Union) as one of the most common benchmarks, is studied under factors in system designs and implementations. In particular, we focus on the analysis of packet delay, jitter, and packet loss for PTT services. Experiments are designed and executed with the considerations of PTT characteristics. Our goal is to provide more understanding of MOS versus PTT and deliver insights in future PTT system designs.

Routing problems have become highly challenging because of the popularity of mobile devices. This paper targets power-aware routing when network topologies and data traffic may change quickly in an unpredictable way. We propose a distributed algorithm and its realization to maximize the minimum residual energy of all the nodes for each multicast, where no global information is assumed to be efficiently maintained at any node. A transient multicast tree is established on demand and derived based on the autonomous decisions of intermediate nodes. We prove that the derived tree is loop-free and theoretically optimal in the maximization of minimum residual energy. The performance of the proposed protocol was evaluated over NS2 with a series of simulations for which we have very encouraging results.

IEEE-1394 is widely adopted in various commercial products for computing, communication, and entertainment. Although many services with Quality-of-Service (QoS) supports are now available in systems over IEEE-1394, little work is done for QoS-based resource allocation. In this article, we aim at the design of a bandwidth reservation mechanism and its policy for isochronous requests, such as those from cameras. We then address the QoS support issue for asynchronous requests, such as those from disks, and an analytic framework for probability-based QoS guarantees. This work is concluded by the proposing of a topology configuration algorithm for IEEE-1394 devices. The capability of the proposed methodology and the analytic framework are evaluated by a series of experiments over a Linux-based system prototype.

Wireless sensor networks have been extensively adopted in numerous application scenarios. However, increasing environmental constraints and performance requirements has spurred the development of tools to expedite deployment and minimize human intervention. This study extends previous work by the authors in network development and aims at the performance evaluation of applications operating in to-be-deployed networks. We prove that the determination of a ZigBee cluster tree over an underlying network is NP - hard and propose an algorithm for generating tree topology. Based on the proposed algorithm/technologies, an integrated development tool is developed. The capability of the tool is demonstrated by a case study of the system deployed in an office building.

A large-scaled RFID application often needs a highly efficient database system in data processing. This research is motivated by the strong demand of an efficient index structure design for main-memory database systems of RFID applications. In this paper, a signature-based grid index structure is proposed for efficient data queries and storage. An efficient methodology is proposed to locate duplicates and to execute batch deletions and range queries based on application domain knowhow. The capability of the design is implemented in an open source main-memory database system H2 and evaluated by realistic workloads of RFID applications.

Performance and reliability are two major design concerns of flash-memory storage systems, especially for low-cost products. Although various excellent flash- memory management schemes are proposed, there is little work done on how to evaluate the designs or implementations of flash-memory storage systems. Many of the existing evaluation workloads for flash-memory storage systems still rely on those based on hard disks. This work aims at the needs of behavior analysis of flash-memory storage systems and their evaluations. In particular, a set of evaluation metrics and their corresponding access patterns are proposed. The behaviors of flash memory are also analyzed in terms of performance and reliability issues.

Energy-efficiency has been an important system issue in hardware and software designs for both real-time embedded systems and server systems. This research explores systems with probabilistic distribution on the execution time of realtime tasks on homogeneous multiprocessor platforms with the capability of dynamic voltage scaling (DVS). The objective is to derive a task partition which minimizes the expected energy consumption for completing all the given tasks in time. We give an efficient 1.13-approximation algorithm and a polynomial-time approximation scheme (PTAS) to provide worst-case guarantees for the strongly NP-hard problem. Experimental results show that the algorithms can effectively minimize the expected energy consumption.

Energy-efficient real-time task scheduling has been actively explored in the past decade. Different from the past work, this paper considers schedulability conditions for stochastic real-time tasks. A schedulability condition is first presented for frame-based stochastic real-time tasks, and several algorithms are also examined to check the schedulability of a given strategy. An approach is then proposed based on the schedulability condition to adapt a continuous-speed-based method to a discrete-speed system. The approach is able to stay as close as possible to the continuous-speed-based method, but still guaranteeing the schedulability. It is shown by simulations that the energy saving can be more than 20% for some system configurations. © 2008 IEEE.

This paper presents a power-aware secure routing protocol for wireless embedded networks (WENs). We propose an efficient secure relay scheme called ESRS for ad-hoc-based embedded-network communications. ESRS is a two-phase scheme which includes end-to-end secure channel establishment and relay-behavior monitoring. With end-to-end secure channel establishment, the transmitted data will be protected under an end-to-end secure channel. A power-aware secure route will be also provided in this stage. Then attacks of routing are monitored and controlled in the monitoring phase. As the experimental results are shown, ESRS provides an efficient way to relay data securely for ad-hoc-based embedded network communications.

This paper describes a component model and component-based architecture of smart devices and systems that are designed to enhance life quality and well being of elderly individuals. In addition to providing the traditional view of hardware, firmware and software components, the model also provides developers with an operational view. The view enables the developer to specify device-user interactions asexecutable workflows and allows the device operations and user actions to be experimented with and their correctness ascertained throughout the design and development process. The paper also presents a simulation environment for this purpose.

Flash memory is widely adopted in various consumer products for information storage, especially for embedded systems. With strong demands on product designs for overhead control and performance requirements, vendors must have an effective design for the mapping of logical block addresses (LBA's) and physical addresses of data over flash memory. This paper targets such an essential issue by proposing a configurable mapping method that could trade the main-memory overhead with the system performance under the best needs of vendors. A series of experiments is conducted to provide insights on different configurations and the proposed method, compared to existing implementations.

Power-aware and energy-efficient designs play important roles for modern hardware and software designs, especially for embedded systems. This paper targets a scheduling problem on a processor with the capability of dynamic voltage scaling (DVS), which could reduce the power consumption by slowing down the processor speed. The objective of the targeting problem is to minimize the average flow time of a set of jobs under a given energy constraint, where the flow time of a job is defined as the interval length between the arrival and the completion of the job. We consider two types of processors, which have a continuous spectrum of the available speeds or have only a finite number of discrete speeds. Two algorithms are given: (1) An algorithm is proposed to derive optimal solutions for processors with a continuous spectrum of the available speeds. (2) A greedy algorithm is designed for the derivation of optimal solutions for processors with a finite number of discrete speeds. The proposed algorithms are extended to cope with jobs with different weights for the minimization of the average weighted flow time. The proposed algorithms are also evaluated with comparisons to schedules which execute jobs at a common effective speed.

Dynamic voltage scaling (DVS) circuits have been widely adopted in many computing systems to provide tradeoff between performance and power consumption. The effective use of energy could not only extend operation duration for hand-held devices but also cut down power bills of server systems. Moreover, while many chip makers are releasing multi-core chips and multiprocessor system-on-a-chips (SoCs), multiprocessor platforms for different applications become even more popular. Multiprocessor platforms could improve the system performance and accommodate the growing demand of computing power and the variety of application functionality. This paper summarizes our work on several important issues in energy-efficient scheduling for real-time tasks in multiprocessor DVS systems. Distinct from most previous work based on heuristics, we aim at the provision of approximated solutions with worst-case guarantees. The proposed algorithms are evaluated by a series of experiments to provide insights in system designs.

This work is motivated by the strong demand of reliability enhancement over flash memory. Our objective is to improve the endurance of flash memory with limited overhead and without many modifications to popular implementation designs, such as Flash Translation Layer protocol (FTL) and NAND Flash Translation Layer protocol (NFTL). A static wear leveling mechanism is proposed with limited memory-space requirements and an efficient implementation. The propreties of the mechanism are then explored with various implementation considerations. Through a series of experiments based on a realistic trace, we show that the endurance of FTL and NFTL could be significantly improved with limited system overheads.

Many computing systems have adopted the dynamic voltage scaling (DVS) technique to reduce energy consumption by slowing down ope- ration speed. However, the longer a job executes, the more energy in leakage current the processor consumes for the job. To reduce the power/energy consumption from the leakage current, a processor can enter the dormant mode. Existing research results for leakage-aware DVS scheduling perform procrastination of real-time jobs greedily so that the idle time can be aggregated as long as possible to turn off the processor. This paper proposes algorithms for the procrastination deter- mination of periodic real-time tasks in uniprocessor systems. Instead of greedy procrastination, the procrastination procedures are applied only when the evaluated energy consumption is less than not procras- tination. Evaluation results show that our proposed algorithms could derive energy-efficient solutions and outperform existing algorithms.

In this demonstration, the core processing engines of two video applications, 3D video and intelligent video surveillance, are demonstrated. The developed algorithms and its VLSI design results are shown with hardware prototypes processing input video on-the-fly. In addition to the processing engine design, the development tools for efficiently designing these chips are also demonstrated.

This work explores the unique characteristics of flash memory in serving as a cache layer for disks. The experiments show that the proposed management scheme could save up to 20% energy consumption while reduce the read response time by the two third and the write response time by the five sixth of their counterparts. The estimated lifetime of the flash-memory cache is significantly improved as well.

Wireless sensor networks have been widely considered as an effective tool in various application domains. One of the major implementation issues is on the network deployment problem. In this paper, we target issues in the deployment of wireless sensor nodes in three-dimensional indoor environments and with irregular radiation patterns for both message communicating and sensing. Our objective is to develop a more effective way to deploy sensor networks and to minimize the number of deployed nodes. We propose several search-oriented strategies to improve the performance of search algorithms, such as simulated annealing. The capability of the proposed strategies is demonstrated by real-case studies in the deployment of sensor networks in several office flats

Dynamic voltage scaling (DVS) has been adopted in many computing systems to reduce the energy consumption of the processor by slowing down the processor speed. However, for system devices without DVS capability, the longer a task executes, the more energy the task consumes in the required system devices. This paper explores energy-efficient scheduling for periodic hard real-time tasks in a system consisted of a DVS processor and multiple non-DVS system devices. We propose an algorithm for static scheduling which minimizes the system energy consumption of a given set of real-time tasks, provided that each task executes in its worst case. For systems in which some tasks might complete earlier than its estimated worst-case execution time, we develop on-line algorithms to reclaim the slack time to reduce the energy consumption. Compared to existing algorithms, our proposed algorithm can reduce the energy consumption both in the CPU and system devices

While there is a tradeoff between the energy consumption and the satisfaction of task deadlines, the management of the processor temperature is of paramount important to the survival of the processor and the reduction of packing cost. This paper explores the scheduling of periodic real-time tasks with temperature-aware considerations in a uniprocessor or homogeneous multiprocessor environment. By modeling the cooling process approximately according to Fourier's law, a 2.719-approximation algorithm is shown for the minimization of the maximum temperature for processors with continuous processor speeds. When the processor is with discrete speeds only, we extend the 2.719 approximation algorithm to manage the voltage/speed transition so that the maximum temperature can be minimized. For homogeneous multiprocessor systems, we show that the largest-task first strategy has a 3.072-approximation bound in the minimization of the maximum temperature when all of the processors are on a chip. When each processor is on a chip, the approximation bound in the minimization of the maximum temperature is 6.444. When jobs might complete earlier than their worst-case estimation, dynamic scheduling is further explored to reduce the maximum temperature

This work is motivated by the rapid increasing of the design complexity of many embedded systems. It aims at the proposing of solutions to resolve the hardware contention issues of non-preemptive processing elements shared among tasks and the cost optimization. A software solution based on the starting time management is proposed to interleave task executions on processing elements. Algorithms are proposed to determine the required processing elements of selected types, when there is no knowledge on the releasing time of any task: When task release orders are known a priori, an optimal algorithm is presented if processing elements have the same cost; otherwise, a pseudo-polynomial-time algorithm based on dynamic programming is presented for optimal solutions. The performance of the algorithms is also evaluated for general cases

Multiprocessor platforms have been widely adopted in both embedded and server systems. In addition to the performance improvement, multiprocessor systems could have the flexibility in tolerating processor failures via task replication. This paper considers the replication of periodic hard real-time tasks in identical multiprocessor environments. Each task is replicated on K distinct processors, where K is a user-determined integer for fault tolerance to improve system reliability. When the objective is to minimize the maximum utilization in a system with a specified number of processors, we present a greedy algorithm with a 2-approximation ratio, and a polynomial-time approximation scheme is developed. For the minimization of the number of processors required to derive feasible schedules with task replication, we develop greedy algorithms with a 2-approximation ratio and an asymptotic polynomial-time approximation scheme

In the past decade, energy-efficient real-time task scheduling has been widely explored in terms of various optimization problems. With a very different goal, this paper considers real-time task synchronization protocols with the minimization of energy consumption. We propose the concept of frequency locking and extend the priority ceiling protocol by locking the processor frequency in a restricted way so that the cost in frequency switching is better managed. Algorithms are proposed to assign tasks base frequencies in the minimization of the energy consumption and with the consideration of schedulability tests. The capability of the proposed methodology is evaluated by a series of experiments, for which encouraging results were presented.

This work is motivated by a strong market demand in the replacement of NOR flash memory with NAND flash memory to cut down the cost in many embedded-system designs, such as mobile phones. Different from LRU-related caching or buffering studies, we are interested in prediction-based prefetching based on given execution traces of application executions. An implementation strategy is proposed in the storage of the prefetching information with limited SRAM and run-time overheads. An efficient prediction procedure is presented based on information extracted from application executions to reduce the performance gap between NAND flash memory and NOR flash memory in reads. With the behavior of a target application extracted from a set of collected traces, we show that data access to NOR flash memory can be responded effectively over the proposed implementation.

In reality, peripheral devices often make a significant contribution to the power consumption of the entire system. An effective energy-efficient scheduling algorithm should consider not only the energy consumption of the processor but also the usages of devices. In this paper, we explore energy-efficient scheduling of periodic real-time tasks in a system with a dynamic-voltage-scaling (DVS) processor and multiple non-DVS system devices. We consider systems that any device used by a task remains operating while the task is active. We propose scheduling algorithms in the management of task preemption to reduce the energy consumption of devices. Simulation results show that our proposed algorithms could not only reduce the number of task preemption significantly but also minimize the energy consumption, compared to earliest-deadline-first scheduling.

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

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

The energy-aware design for electronic systems has been an important issue in hardware and/or software implementations, especially for embedded systems. This paper targets a synthesis problem for heterogeneous multiprocessor systems to schedule a set of periodic real-time tasks under a given energy consumption constraint. Each task is required to execute on a processor without migration, where tasks might have different execution times on different processor types. Our objective is to minimize the processor cost of the entire system under the given timing and energy consumption constraints. The problem is first shown being NP - hard and having no polynomial-time algorithm with a constant approximation ratio unless NP = P . We propose polynomial-time approximation algorithms with (m + 2) - approximation ratios for this challenging problem, where m is the number of the available processor types. Experimental results show that the proposed algorithms could always derive solutions with system costs close to those of optimal solutions.

IEEE 802.15.4 is a new standard uniquely designed for low-rate wireless personal area networks. It targets ultra-low complexity, cost, and power for low-rate wireless connectivity among inexpensive, portable, and moving devices. IEEE 802.15.4 provides a Guaranteed Time Slots (GTS) mechanism to allocate a specific duration within a superframe for time-critical transmissions. In this paper, we propose an adaptive GTS allocation (AGA) scheme for IEEE 802.15.4 with the considerations of low-latency and fairness. The scheme is designed based on the existing IEEE 802.15.4 medium access control protocol without any modification. A simulation model validated by the developed mathematical analysis is presented to investigate the performance of our AGA scheme. The capability of the proposed AGA scheme is evaluated by a series of experiments. It is shown that the proposed scheme significantly outperforms the existing IEEE 802.15.4 implementations.

Energy-efficiency and power-awareness for electronic systems have been important design issues in hardware and software implementations. We consider the scheduling of periodic hard real-time tasks along with the allocation of processors under a given energy constraint. Each processor type could be associated with its allocation cost. The objective of this work is to minimize the entire allocation cost of processors so that the timing and energy constraints are both satisfied. We develop approximation algorithms for processor types with continuous processor speeds or discrete processor speeds. The capability of the proposed algorithms was evaluated by a series of experiments, and it was shown that the proposed algorithms always derived solutions with system costs close to those of optimal solutions in the experiments.

While the capacity of flash-memory storage systems keeps increasing significantly, effective and efficient management of flash-memory space has become a critical design issue! Different granularities in space management impose different management costs and mapping efficiency. In this paper, we explore an address translation mechanism that can dynamically and adaptively switch between two granularities in the mapping of logical block addresses into physical block addresses in flash memory management. The objective is to provide good performance in address mapping and space utilization and, at the same time, to have the memory space requirements, and the garbage collection overhead under proper management. The experimental results show that the proposed adaptive mechanism could provide significant performance improvement over the well-known coarsegrained management mechanism NFTL (NAND Flash Translation Layer) over realistic workloads.

This work is motivated by the needs of energy-efficient designs for multi-context FPGAs. Dynamic-voltage-scaling-based algorithms are proposed to schedule loading and executing of tasks in a multi-context FPGA. When a task partition over contexts is given, two optimal scheduling algorithms are proposed in minimizing the energy consumption and the maximum time span of task executions. When no task partition is given, two approximation algorithms with approximation ratios 2.371 and 1.540 are presented in the energy-consumption minimization and the maximum-time-span minimization, respectively.

While flash memory has been widely adopted for various embedded systems, space efficiency with reasonable performance has become a critical issue for the design of the flash-memory translation layer. The target of this paper is to improve the performance of existing designs by proposing a search-tree-like caching mechanism for efficient address translation. A replacement strategy with a low time complexity is presented to monitor the access status of recently used LBA's. The proposed caching mechanism and replacement strategy were shown being highly effective in the reducing of the address translation time over popular translation layer designs, such as NAND, where realistic workloads were used for experiments.

As the dynamic voltage scaling (DVS) technique provides system engineers the flexibility to trade-off the performance and the energy consumption, DVS has been adopted in many computing systems. However, the longer a job executes, the more energy in the leakage current the device/processor consumes for the job. To reduce the energy consumption resulting from the leakage current, a system might enter the dormant mode. This paper targets energy-efficient rate-monotonic scheduling for periodic real-time tasks on a uniprocessor DVS system with non-negligible leakage power consumption. An on-line simulated scheduling strategy and a virtually blocking time strategy are developed for procrastination scheduling to reduce energy consumption. The proposed algorithms derive a feasible schedule for real-time tasks with worst-case guarantees for any input instance. Experimental results show that our proposed algorithms could derive energy-efficient solutions.

This research is motivated by the needs of dwell scheduling over multiple transmitters/receivers in many real radar systems. We propose a linear-programmingbased approach with efficient implementations to minimize the number of radar tasks being dropped from the system and to balance workloads over multiple transmitters/ receivers. A priority-based task dropping policy and an incremental version of the task assignment algorithm are proposed for task dropping and on-line implementations. The capability of the proposed algorithm is evaluated by a series of experiments, for which we have encouraging results.

Multiple processing elements are often adopted in the current designs of embedded systems. Such configurations impose challenges on hardware/software co-designs with energy-efficient considerations. This paper targets energy-efficient real-time task scheduling of such popular configurations, in which systems are equipped with a DVS processor and a non-DVS processing element (PE). We consider task scheduling under different power consumption models of the non-DVS PE. When the power consumption of the non-DVS PE is independent on the assigned workload, a fully polynomial-time approximation scheme is developed for energy-efficient scheduling. When the energy consumption of the non-DVS PE depends on the assigned workload, a 0.5-approximation algorithm is developed to maximize the energy saving, compared to the execution of tasks on a DVS processor. Extensive simulations were performed to evaluate the capability of our proposed algorithms. The results show that our algorithms are very effective in energy-efficiency

This paper presents a system prototype to help elder persons being aware of changes in terrain ahead of them. Ultrasonic signal is used for the detection of terrain changes because of its stability in air transmission speed and its simplicity and cost in hardware designs. The prototype is designed and built using commercial-off-the-shelf (COTS) components with an 8051 microprocessor. It can detect obstacles of heights no more than 10 cm three steps away.

A smart pantry holds non-perishable household supplies and automates the purchasing and delivery of their replenishments. By relieving its user from the chore of keeping the home stocked of essentials, it provides convenience and peace of mind not only to elderly individuals but also busy people of all ages. This paper describes two alternative smart pantry designs and tradeoffs. Underlying methods and technologies used for their implementation are also described.

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

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

In recent years, many modern phased-array radars are built with commercial off-the-shelf components, and the functions of many hardware components are also reimplemented by software modules. In such systems, radar tasks could be modeled as distributed real-time tasks which require end-to-end deadline guarantees and have precedence constraints. Different from most previous work on either algorithms with restrictions in resource utilization or heuristics without analytical ways for schedulability guarantees, the objective of this paper is to propose a joint real-time scheduling algorithm for both transmitter/receiver and signal processor workloads with an analytical framework for offline probabilistic analysis and online admission control. The strength of our approach is verified by analysis results and a series of experiments based on a real phased-array radar for air defense frigates

In the recent decade, voltage scaling has become an attractive feature for many system component designs. In this paper we consider energy-efficient real-time task scheduling over a chip multiprocessor architecture. The objective is to schedule a set of frame-based tasks with the minimum energy consumption, where all tasks are ready at time 0 and share a common deadline. We show that such a minimization problem is NP-hard and then propose a 2.371-approximation algorithm. The strength of the proposed algorithm was demonstrated by a series of simulations, for which near optimal results were obtained.

Energy-efficient scheduling is an effective way to balance the system performance and the energy consumption. We design a polynomial-time (1+ε)-approximation algorithm to minimize the energy consumption for periodic real-time tasks over such processors, where ε is the tolerable error given by users (1 ≥ ε > 0). It provides trade-offs between the user's tolerable error and the runtime complexity including the time complexity and the memory space complexity. System engineers could trade performance with implementation constraints.

Strong connectivity has been an important feature explored in many network applications, such as sensor networks. This research focuses on a dual power assignment problem, where each sensor node has two transmission power levels. The objective is to minimize the number of wireless sensor nodes assigned to transmit messages at the high transmission power level, while the resulting sensor network is strongly connected. We propose an efficient 1.75-approximation algorithm for this challenging problem. We not only show that the approximation ratio of the proposed algorithm is tight but also demonstrate the capability of the proposed algorithm in terms of simulation experiments.

In the past decades, a number of research results have been reported for energy-efficient scheduling over uniprocessor and multiprocessor environments. Different from many of the past results on the assumption for task power characteristics, we consider real-time scheduling of tasks with different power characteristics. The objective is to minimize the energy consumption of task executions under the given deadline constraint. When tasks have a common deadline and are ready at time 0, we propose an optimal real-time task scheduling algorithm for multiprocessor environments with the allowance of task migration. When no task migration is allowed, a 1.412-approximation algorithm for task scheduling is proposed for different settings of power characteristics. The performance of the approximation algorithm was evaluated by an extensive set of experiments, where excellent results were reported.

Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both nonpreemptible and preemptible jobs. This paper develops two approximation algorithms for nonpreemptible and preemptible jobs. When jobs are nonpreemptible, algorithm LECF is with a 2-approximation factor; when jobs are preemptible, algorithm LEF is proved being a 3-approximation algorithm. We also show that our analysis on the two algorithms is tight by providing a set of input instances. Simulation results demonstrate that algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms.

Although simultaneous multithreading (SMT) has been shown being an efficient technique to improve processor performance, little work has been done on real-time SMT scheduling. The objective of this paper is to explore realtime SMT scheduling for independent periodic task sets with schedulability guarantees. We propose emulation-based scheduling algorithms with and without task migration to emulate an adjustable SMT processor over a non-adjustable SMT processor. The schedulability tests for the proposed scheduling algorithms are presented. An approximation bound on the average number of tasks running in parallel is also shown. The performance of the proposed algorithms was evaluated by a series of simulation experiments.

The College of Electrical Engineering and Computer Science at the National Taiwan University has identified the area of content science for media-rich life, broadly construed, as one of core areas for the college's future directions. One major aspect of this project is to develop the enabling technology for reconfigurable platforms for multimedia applications. Specifically, the goal is to develop reconfigurable platforms of system-on-a-chip (SoC) components for the applications to support the needs of multi-modal multimedia contents and to provide rapid system prototyping. The faculties in the College of Electrical Engineering and Computer Science have formed a multi-discipline team to develop such technology. Our team includes seven faculties and more than thirty students from the college. This short report describes the reconfigurable platform for content science research activities currently underway by our team. Our current activities include to develop the technology to analyze the critical path for avoiding hardware contention, to minimize the use of logic components, to design the multimedia IPs, to optimally route the bus and place the logic units, to design energy efficient cache, to evaluate the performance and power consumption, to design the algorithm for temporal floor-planning/placement.

This paper is interested in reward maximization of periodic real-time tasks under a given energy constraint, where the reward received depends on how much computation a task runs before its deadline. When voltage scaling could be done at any time, and tasks share the same power consumption function, we propose a greedy algorithm which derives a solution with at least a half of the optimal reward for any input instance. A fully polynomial-time approximation scheme is also proposed by applying the dynamic programming approach so that the ratio of the reward of the derived solution to that of an optimal solution is at least 1 - /spl epsiv/ under polynomial-time complexity in 1//spl epsiv/ for any 0 < /spl epsiv/ < 1, where /spl epsiv/ denotes a user-specified tolerable error to the derived solutions. When voltage scaling could be done only when a task instance arrives or terminates, or tasks might have different power consumption functions, we develop an approximation algorithm based on linear programming, which guarantees to derive a solution with at least 1/3 optimal reward for any input instance. A series of experiments was conducted to show the capability of the proposed algorithms in reward maximization.

A multifunction phased array radar must search and track suspicious targets in its surveillance space in a real-time fashion. With inefficient scheduling implementations in many traditional systems, much radar resource is wasted with a very limited performance gain. This paper targets one of the most important issues in the design of modern phased array radars: real-time dwell scheduling. We formalize the typical workload of a modern phased array radar and propose a rate-based approach to schedule radar dwells in a real-time fashion. We show how to reserve radar resources to guarantee the minimum radar operation without sacrificing the stability of the system. The strength of our approach is verified by a series of simulation experiments based on a real phased array radar for air defense frigates [A. G. Huizing et al. (1996)]. A significant improvement in the performance of phased array radars was shown.

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

In recent years, many modern phased array radars are built with commercial-off-the-shelf components, and the functions of many hardware components are also re-implemented by software modules. In such systems, radar tasks could be modelled as distributed real-time tasks, which require end-to-end deadline guarantees and have precedence constraints. Different from most previous work on either algorithms with restrictions in resource utilization or heuristics without analytical ways for schedulability guarantees, the objective of This work is to propose a joint real-time scheduling algorithm for both transmitter/receiver and signal processor workloads with an analytical framework for off-line probabilistic analysis and online admission control. The strength of our approach is verified by analysis results and a series of experiments based on a real phased array radar for air defense frigates [A. G. Huizing et al. (1996)].

Summary form only given. While excellent research results have been proposed for query optimization, little work has been done for the scheduling of query execution plans. We target the optimization problem of the schedule lengths of query execution plans in a symmetric multiprocessor (SMP) database system. We show the NP-hardness of the optimization problem. A critical-path-based algorithm is proposed to minimize the schedule length of a collection of query execution plans. When each query execution plan has a tree or a directed acyclic graph structure, we show that the approximation ratios of our proposed algorithm are 2 and (3 - 2/M), respectively, where M is the number of processors in the system. When the proposed algorithm is adopted for online usages, the competitive ratio of the algorithm is proven being (3 $2/M). The proposed algorithm is optimal when there is a sufficient number of processors. The performance of the proposed algorithm is evaluated based on the TPC-C benchmark.

As the universal serial bus (USB) 2.0 becomes a major driving force in the peripherals market now, the variety of USB devices and their request types also impose challenging issues on resource allocation of bus bandwidth. This research aims at the proposing of a USB-compliant system architecture and real-time scheduling algorithms for the resource allocation of USB 2.0 and 1.1 device requests jointly in a quality-of-service (QoS) fashion. Periodic requests, such as isochronous and interrupt transfers, are guaranteed with preservation of bus bandwidth and schedulability tests. Sporadic requests, such as control and bulk transfer, are serviced with probabilistic performance guarantees. The capability of this work is demonstrated with performance evaluations over a Linux system prototype, for which we have encouraging results.

The Universal Mobile Telecommunication System (UMTS) adopts WCDMA as the air interface that provides variable transmission rate services. Four traffic classes are identified in UMTS, given as controversial, streaming, interactive, and background classes. To efficiently utilize the radio bandwidth, the shared channel technology is proposed to deliver interactive and background traffics. This paper proposes a "shared-channel assignment and scheduling" (SCAS) algorithm to allocate shared channels to interactive and background connections. We formally prove that the SCAS algorithm can satisfy the transmission rate requirement of each interactive connection and can efficiently utilize the radio bandwidth.

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

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

This paper describes the design of a real-time data dispatching system (RTDDS), which is motivated by the needs of a performance guarantee on real-time data services by front-end clients. RTDDS consists of homogeneous machines with a quality of service performance guarantee. We address the resource allocation problems and consider Bin-Packing algorithms to assign requests to machines of RTDDS. Processes scheduling over each machine is done autonomously by SRP-based algorithms. The goal is to maximize the number of concurrent clients and to meet the individual quality of service requirements of clients at the same time.

In this paper, we study the impacts of checkpointing and write-through procedures, which are critical in maintaining database recoverability and transaction durability, on the performance of a well-known real-time concurrency control protocol, the Read/Write Priority Ceiling Protocol (RWPCP). Although RWPCP can guarantee the schedulability of real-time transactions, it could be unrecoverable, and the priority inversion problems could be unbounded, when transaction commitment is considered. In this paper, we first propose to extend RWPCP with deferred-commitment and extended-locking-period methods to resolve the problems. Then, we study the impacts of different checkpointing granularities and checkpointing methods on the proposed recoverable RWPCP. A detailed simulation study was conducted to evaluate the performance of the recoverable RWPCP with different checkpointing methods under various workloads.

Processes running in a multiple-disk environment may share non-preemptible resources on the processor and, at the same time, request services from disk subsystems. In this paper, we propose a methodology which is efficient and easy to implement for scheduling processes in multiple-disk environments. In other words, our methodology addresses the scheduling of real-time processes which may stop to wait for disk I/O without releasing any locked semaphores. Our proposed methodology is a variation of the well-known priority ceiling protocol to schedule processes running in multiple-disk environments. The capability of the proposed methodology is verified by a series of simulation experiments under different workloads of CPU-bound and I/O-bound processes in multiple-disk environments, for which we have some encouraging experimental results.

While there has been a significant amount of research in real-time concurrency control, little work has been done in logging and recovery for real-time databases. This paper proposes a two-version approach which considers both real-time concurrency control and recovery. We propose a network-server-based architecture and algorithms which can not only reduce the blocking time of higher-priority transactions and improve the response time of client-side read-only transactions, but also provide a diskless runtime logging mechanism and an efficient and predictable recovery procedure. The performance of the algorithms was verified by a series of simulation experiments by comparing the algorithms with the well-known Priority Ceiling Protocol (PCP), the Read/Write PCP, the New PCP, and the 2-version two-phase locking protocol, for which we have very encouraging results. The schedulability of higher-priority transactions and the response time of client-side read-only transactions were all greatly improved.

We propose a class of real-time data access protocols called SSP (similarity stack protocol). The correctness of SSP schedules is justified by the concept of similarity which allows different but sufficiently timely data to be used in a computation without adversely affecting the outcome. SSP schedules are deadlock-free, subject to limited blocking, and do not use locks. We give a schedulability bound for SSP and also report simulation results which show that SSP is especially useful for scheduling real-time data access on multiprocessor systems. Finally, we present a variation of SSP which can be implemented in an autonomous fashion in the sense that scheduling decisions can be made with local information only.

This paper proposes a generic framework to integrate real-time scheduling algorithms, conventional concurrency control algorithms, and aborting algorithms. The schedulability of a transaction system is improved by aborting excessive blocking from lower priority transactions. A schedulability analysis model is proposed to better manage the schedulability of a transaction system.

With the advance of hardware and software technology, modern phased array radars are now built with commercial-off-the-shelf (COTS) components, and it opens up a new era in real-time resource scheduling of digital signal processing. This paper targets the essential issues in building a component-oriented signal processor (SP), which is one of the two major modules in modern phased array radars. We propose a simple but effective task allocation policy and a real-time scheduling algorithm to address the design objectives of SPs. We are able to bound the number of processing units needed for a component-oriented SP in the design time, while everything was done empirically in the past. A series of experiments was done to demonstrate the strength of our methodology.

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

This paper investigates a class of rate-based real-time scheduling algorithms based on the idea of general processor sharing (GPS). We extend the GPS framework of Parekh and Gallager (1993) for periodic and sporadic process scheduling and show the optimality of GPS-based scheduling. In particular, we propose the earliest-completion-time GPS (EGPS) scheduling algorithm to simulate the GPS algorithm with much lower run-time overheads. The schedulability of each process is enforced by a guaranteed CPU service rate, independent of the demands of other processes. We provide a theoretical foundation to assign proper CPU service rates to processes to satisfy their individual stringent response time requirements. We also propose a GPS-based scheduling mechanism for jitter control. Finally, the performance of the proposed algorithms is studied using a generic avionics platform example and simulation experiments on jitter control and mixed soft and hard real-time process scheduling.

Although many high-performance computer systems are now multiprocessor-based, little work has been done in real-time concurrency control of transaction executions in a multiprocessor environment. Real-time concurrency control protocols designed for uniprocessor or distributed environments may not fit the needs of multiprocessor-based real-time database systems because of a lower concurrency degree of transaction executions and a larger number of priority inversions. This paper proposes the concept of a priority cap to bound the maximum number of priority inversions in multiprocessor-based real-time database systems to meet transaction deadlines. We also explore the concept of two-version data to increase the system concurrency level and to explore the abundant computing resources of multiprocessor computer systems. The capability of the proposed methodology is evaluated in a multiprocessor real-time database system under different workloads, database sizes and processor configurations. It is shown that the benefits of the priority cap in reducing the blocking time of urgent transactions are far greater than the losses involved in committing less urgent transactions. The idea of two-version data also greatly improves the system performance because of a much higher concurrency degree in the system.

The emergence of Intelligent I/O (I2O) architecture provides a standard for high-performance I/O subsystems and introduces intelligence at the hardware level. With an embedded processor, I2O adaptors can offload the major I/O processing workload from the CPU and, at the same time, increase the I/O performance. This paper addresses the essential issue in the design of disk scheduling for I2O RAID-0 devices. We explore online real-time multi-disk scheduling for I2O requests and propose highly efficient algorithms to minimize the number of deadline violations and, at the same time, to improve the response times of requests. The proposed methodologies are verified by a series of experiments under realistic and randomly generated workloads.

In broadcast environments, communication bandwidth asymmetry is a distinguishing feature. The low bandwidth available for clients to communicate with the broadcast server makes it expensive and inefficient to maintain global serializability among all the transactions that execute at distributed mobile clients. In this paper, investigation is made to relax the requirements of global serializability among transactions while data consistency is still achieved. The NRS-Algorithm is proposed to process read-only transactions separately from update transactions to reduce the degree of data contention between the two kinds of transactions. Moreover, each read-only transaction running at the clients is guaranteed to read consistent data values autonomously without the need to do validation at the server. This is extremely beneficial to the concurrency control in broadcast environments where the upstream communication capacity is limited. To generalize the idea, two kinds of group consistency requirements for read-only transactions are defined. Group strong consistency requires a group of read-only transactions to be conflict serializable with respect to the update transactions. A weaker form of consistency, group view consistency, is also defined to allow a group of read-only transactions to be view serializable with respect to some update transactions. The NRS-Algorithm is then extended to preserve the two kinds of group consistency within a group of read-only transactions.

An important issue in the design of a mobile computing system is how to manage the real-time locations of mobile clients. In the existing commercial cellular mobile computing systems, a two-tier architecture is used [13]. However, the two-tier architecture is not scalable and is not suitable to the new mobile computing applications. In the literatures [1, 12], a hierarchical database structure is proposed in which the location information of the mobile clients within a cell is managed by the location database responsible for the cell. The location databases of different cells are organized into a tree structure to facilitate the search of mobile clients. Although this architecture can distribute the update and searching workload amongst the location databases in the system, it has the problem of heavy location update overhead and long search delay. Thus, it is not suitable to the system which is supporting real-time queries. In this paper, we study how to generate location update in...

An important mobile application is to provide users information in a real-time fashion over a mobile network, such asthose for news updates and traffic information. The contents of such information are often highly dynamic, and its validity maychange with time rapidly. It is the best benefit of users if the most recent data can be received by users on time. Informationupdates, which capture the most recent status of interested objects in the external environment, must be done continuously andin a real-time fashion to refresh the values of the corresponding data items in the information servers. However, mobilenetworks are often unreliable, and the available bandwidth is usually very limited. If the rate of information update is too high,the total system workload will be very heavy, and, as a result, the completion times of updates and the validity of many dataitems might be seriously affected. On the other hand, if the update rate is low, the uncertainty level of data validity might behigh, and the external consistency cannot be maintained [1]. In addition to the unreliable mobile network, the mobility ofclients complicates the design of a mobile information system. Queries from mobile clients could have some location-dependent properties. For example, the result of a query might depend on the current location of the originating client. Timingconstraints are often implicitly associated with the processing of queries.In this paper, we introduce a system prototype called

There has been growing interest in the performance of transaction systems that have significant response time requirements. These requirements are usually specified as hard or soft deadlines on individual transactions and a concurrency control algorithm must attempt to meet the deadlines as well as preserve data consistency. This paper proposes a class of simple and efficient abort-oriented concurrency control algorithms in which the schedulability of a transaction system is improved by aborting transactions that introduce excessive blockings. We consider different levels of the aborting relationship among transactions and evaluate the impacts of the aborting relationship when the relationship is built in an online or offline fashion. We measure aborting overheads on a system running the LynxOS real time operating system. The strengths of the work are demonstrated by improving the worst-case schedulability of an avionics example, a satellite control system, and randomly generated transaction sets.

Although many high-performance computer systems are now multiprocessor-based, little work has been done in real-time concurrency control of transaction executions in a multiprocessor environment. A real-time concurrency control protocol designed for uniprocessor or distributed environments may not fit the needs of multiprocessor-based real-time database systems because of a lower degree of concurrency of the transaction executions and a larger number of priority inversions. This paper proposes the concept of a priority cap to bound the maximum number of priority inversions in multiprocessor-based real-time database systems to meet transaction deadlines and to explore the abundant computing resources of parallel computer systems. A series of experiments is conducted to evaluate the capability of the proposed methodology in scheduling real-time transactions in a parallel fashion.

Although many efficient concurrency control protocols have been proposed for real-time database systems, they are mainly designed for those systems with a single type of real-time transaction. Due to the very different performance requirements of each type of real-time transaction, these proposed protocols may not be suitable for mixed real-time database systems (MRTDBSs), where different types of real-time transactions, and even non-real-time transactions, may co-exist in the systems at the same time. In this paper, we propose strategies for resolving data conflicts between different types of transactions in a MRTDBS so that their different performance requirements can be achieved and, at the same time, the overall system performance can be improved. The performance of the proposed strategies is evaluated and compared with a real-time optimistic approach. The performance of our proposed conflict resolution methods has also been investigated in a more realistic environment with a limited number of priority levels and disk-resident data items.

Most computer-based systems have hard real-time constraints. Schedulers in complex systems must be designed to manage a set of applications developed and deployed independently. We study an open real-time environment architecture for distributed systems where real-time applications may run concurrently with non-real-time applications. The architecture uses a two-level scheduling scheme. Each application is assigned a sporadic server to schedule the processes in the application. All sporadic servers are then scheduled by a system-wide fixed priority scheduler. Using the proposed open environment architecture, all hard real-time applications are guaranteed to have their reserved CPU utilization in order to meet all their deadlines. The guarantee is independent of the behaviors of all other applications in the same system. We present the schedulability analysis methods on systems with or without shared memory.

With the advance of hardware and software technology, modern phased array radars are now built with commercial off-the-shelf (COTS) components, and it opens up a new era in real-time resource scheduling of digital signal processing. This paper targets the essential issues in building a component-oriented signal processor (SP), which is one of the two major modules in modern phased array radars. We propose a simple but effective task allocation policy and a real-time scheduling algorithm to address the design objectives of SPs. We are able to bound the number of processing units needed for a component-oriented SP in the design time, while everything was done empirically in the past. A series of experiments were done to demonstrate the strength of our methodology.

This paper proposes a real-time concurrency control protocol called the reduced ceiling protocol (RCP) for real-time database systems consisting of hard and soft real-time transactions. The schedulability of hard real-time transactions can be improved by bounding the blocking time from soft real-time transactions. Different concurrency control strategies are proposed to resolve data conflicts between different combinations of hard and soft real-time transactions, and the properties of the RCP schedules are shown. In the RCP, methodologies are proposed to reduce the number of aborts for soft real-time transactions due to data conflicts with hard real-time transactions. Simulation experiments have been performed to study the performance of the RCP as compared with the optimistic concurrency control with wait 50 (OCC wait-50) under different workloads of soft real-time transactions, various ratios of read/write operations and deadline constraints. It has been found that the RCP can not only guarantee the performance of hard real-time transactions but also reduce the number of deadlines missed by the soft real-time transactions under all situations.

How to exploit application semantics to improve the performance of a real-time data-intensive application has been an active research topic in the past few years. Weaker correctness criteria and semantica-based concurrency control algorithms were proposed to provide more flexibility in reordering read and write events. Distinct from past work, this paper exploits the trade-off between data consistency and system workload. The definition of similarity is combined with the idea of transaction skipping to provide a theoretical foundation for reducing the workload of a transaction system. We also propose guidelines to adjust the execution frequencies of a static set of transactions and prove their correctness. The strengths of this work were verified by simulation experiments on an air traffic control example.

This paper formalizes the concept of similarity which has been used on an ad hoc basis by application engineers to provide more flexibility in concurrency control. We show how the usual correctness criteria of concurrency control, namely, final-state, view, and conflict serializability, can be weakened to incorporate similarity. We extend the weakened correctness criteria described previously for real-time applications which may run continually, have concurrent transaction executions, or skip unimportant computations. A semantic approach based on the similarity concept is then taken to propose a sufficient condition for scheduling real-time transactions without locking of data.

Predictable performance in the event of failures is of paramount importance in most safety critical real-time database systems. Our research addresses new crash recovery techniques that accommodate pre-run-time timing analysis and utilize design-time information about transactions' data access patterns to improve performance at run time and system restart time. The schemes we will propose are based on a form of shadowing. In contrast to the shadow version algorithm as described previously our schemes reduce overheads at run time, shorten the blocking duration necessary in the transactions' atomic commitment stage, eliminate dynamic storage allocation and reclamation, and permit very fast and bounded-time recovery after a crash by simply retrieving the master record and system version directory from nonvolatile storage. The data structures and algorithms used by our recovery schemes differ when different concurrency control protocols are used. We analyze their characteristics and their impacts on the performance of real-time database systems. Quantitative evaluation of our technique indicates the schemes are much more efficient than traditional log-based techniques.

The paper proposes methodologies to control the access of B-tree-indexed data in a batch and real time fashion. Algorithms are proposed to insert, query, delete, and rebalance B-tree-indexed data based on non real time algorithms (P.M. Kerttu et al., 1996) and the idea of priority inheritance (L. Sha et al., 1990). We propose methodologies to reduce the number of disk I/Os to improve the system performance without introducing more priority inversion. The performance of our methodologies was evaluated by a series of experiments, for which we have some encouraging results.

This paper extends the useful concept of open systems proposed by W.S. Liu, et al. (1997) in scheduling real-time applications and non-real-time applications, where the schedulability of each real-time application can be validated independently of other applications in the system. We replace the underlying earliest-deadline-first OS scheduler of the open system architecture by W.S. Liu, et al. (1997) with a rate-monotonic OS scheduler. The motivation behind this work is that many existing operating systems may not support the earliest deadline first scheduling very well. We propose to use the idea of sporadic servers to preserve CPU cycles for applications. We also develop schedulability tests for real-time applications which adopt the rate monotonic scheduling algorithm, the earliest deadline first scheduling algorithm, the priority ceiling protocol, and the stack resource policy. We allow tasks in each application to share local and global non-preemptable resources. A global resource synchronization mechanism is proposed. This paper provides a fixed-priority-based alternative for the important open system architecture.

A class of real time scheduling algorithms EGPS is proposed. Using EGPS, the schedulability of each process is enforced by a guaranteed CPU service rate, independent of the demands of other processes. Our research uses a GPS based framework for periodic and sporadic process scheduling, jitter control, service rate adjustment, and mixed scheduling of soft and hard real time processes. We then study the performance of the proposed algorithms by using a generic avionics platform example for our simulation experiments in jitter control and mixed scheduling of soft and hard real time processes.

This paper proposes an integration framework to develop real-time monitor programs based on software reuse. A custom-made real-time monitor program can be quickly built by integrating existing monitor programs in commercial operating systems, where limited real-time system and programming support is provided. We consider issues related to the software control, output re-processing, data age, and interactivities of program executions. The feasibility of this framework is demonstrated by the construction of an integration environment and a soft real-time monitor program consisting of the existing monitor programs PView NT Task Manager, NT Performance Monitor and NT File System Monitor in the Microsoft Windows operating systems. Our experimental results show that the incurred system overheads of this approach are very limited.

How to exploit application semantics to improve the performance of a real-time data-intensive application has been an active research topic in the past few years. Weaker correctness criteria and semantics-based concurrency control algorithms were proposed to provide more flexibility in reordering read and write events. Distinct from the past work, this paper exploits the tradeoff between data consistency and system workload. The definition of similarity is combined with the idea of transaction skipping to provide a theoretical foundation for reducing the workload of a transaction system. We also propose guidelines to adjust the execution frequencies of a static set of transactions and prove their correctness. The strengths of this work were verified by simulation experiments on an air traffic control example (Peng et al., 1997).

We provide a framework for discussing how to adjust load in order to handle periodic processes whose timing parameters vary with time. The schedulability of adjustable periodic processes by a preemptive fixed priority scheduler is formulated in terms of a configuration selection problem for which a PTIME solution is shown. When the list of allowable configurations is implicitly given by a set of scalable periodic processes, the corresponding period assignment problem is shown to be NP-Complete. We present an approximation algorithm for the period assignment problem for which we show some encouraging experimental results.

We propose a class of real-time data access protocols called SSP (Similarity Stack Protocol). The correctness of SSP schedules is justified by the concept of similarity which allows different but sufficiently timely data to be used in a computation without adversely affecting the outcome. SSP schedules are deadlock-free, subject to limited blocking and do not use locks. We give a schedulability bound for SSP and also report simulation results which show that SSP is especially useful for scheduling real-time data access on multiprocessor systems. Finally, we present a variation of SSP which can be implemented in an autonomous fashion in the sense that scheduling decisions can be made with local information only.>

The semantics are discussed of data-intensive real-time applications for which serializability is too recursive for consistency management. By examining the semantics of these applications the authors formalize the concept of similarity which has been used on an ad hoc basis by application engineers to provide more flexibility in concurrency control. Weaker consistency requirements based on the similarity concept are proposed. The concept of similarity is used to extend the usual correctness criteria for transaction scheduling: finite-state, view, conflict serializability to their counterparts of final-state Delta -serializability, view Delta -serializability, and conflict Delta -serializability.>

A framework is given for discussing how to adjust load in order to handle periodic processes whose timing parameters vary with time. The schedulability of adjustable periodic processes by a preemptive fixed priority scheduler is formulated in terms of a configuration selection problem. Specifically, two process transformations are introduced for the purpose of deriving a bound for the achievable utilization factor of processes whose periods are related by harmonics. This result is then generalized so that the bound is applicable to any process set and an efficient algorithm to calculate the bound is provided. When the list of allowable configurations is implicitly given by a set of scalable periodic processes, the corresponding period assignment problem is shown to be NP-complete. The authors present an approximation algorithm for the period assignment problem for which some encouraging experimental results are included.>