We present AutoSchemaKG, a framework for fully autonomous knowledge graph construction that eliminates the need for predefined schemas. Our system leverages large language models to simultaneously extract knowledge triples and induce comprehensive schemas directly from text, modeling both entities and events while employing conceptualization to organize instances into semantic categories. Processing over 50 million documents, we construct ATLAS (Automated Triple Linking And Schema induction), a family of knowledge graphs with 900+ million nodes and 5.9 billion edges. This approach outperforms state-of-the-art baselines on multi-hop QA tasks and enhances LLM factuality. Notably, our schema induction achieves 92\% semantic alignment with human-crafted schemas with zero manual intervention, demonstrating that billion-scale knowledge graphs with dynamically induced schemas can effectively complement parametric knowledge in large language models.

We develop a unified mathematical framework for certified Top-$k$ attention truncation that quantifies approximation error at both the distribution and output levels. For a single attention distribution $P$ and its Top-$k$ truncation $\hat P$, we show that the total-variation distance coincides with the discarded softmax tail mass and satisfies $\mathrm{TV}(P,\hat P)=1-e^{-\mathrm{KL}(\hat P\Vert P)}$, yielding sharp Top-$k$-specific bounds in place of generic inequalities. From this we derive non-asymptotic deterministic bounds -- from a single boundary gap through multi-gap and blockwise variants -- that control $\mathrm{TV}(P,\hat P)$ using only the ordered logits. Using an exact head-tail decomposition, we prove that the output error factorizes as $\|\mathrm{Attn}(q,K,V)-\mathrm{Attn}_k(q,K,V)\|_2=τ\|μ_{\mathrm{tail}}-μ_{\mathrm{head}}\|_2$ with $τ=\mathrm{TV}(P,\hat P)$, yielding a new head-tail diameter bound $\|\mathrm{Attn}(q,K,V)-\mathrm{Attn}_k(q,K,V)\|_2\leτ\,\mathrm{diam}_{H,T}$ and refinements linking the error to $\mathrm{Var}_P(V)$. Under an i.i.d. Gaussian score model $s_i\sim\mathcal N(μ,σ^2)$ we derive closed-form tail masses and an asymptotic rule for the minimal $k_\varepsilon$ ensuring $\mathrm{TV}(P,\hat P)\le\varepsilon$, namely $k_\varepsilon/n\approxΦ_c(σ+Φ^{-1}(\varepsilon))$. Experiments on bert-base-uncased and synthetic logits confirm the predicted scaling of $k_\varepsilon/n$ and show that certified Top-$k$ can reduce scored keys by 2-4$\times$ on average while meeting the prescribed total-variation budget.

In-memory key-value storage necessitates a substantial quantity of computation and storage resources for both performance and scalability, thereby diminishing the resources available for user applications. The emergence of programmable network hardware, including SmartNICs and programmable switches, provides the opportunity to offload operations from server CPUs. We present Epiphron, a novel distributed in-memory key-value store architecture that co-designs with off-path SmartNICs and programmable switches. Facing the limited performance of off-path SmartNICs, Epiphron successfully achieves high resource efficiency while keeping load balancing and fault tolerance by$(i)$hybridizing erasure coding with replication in storage management,$(ii)$accelerating read operations with a new data plane design (conflict detection and RDMA-compatible forwarding) on programmable switches,$(iii)$employing a network protocol extended from one-sided RDMA. We evaluate Epiphron on Barefoot Tofino switches, NVIDIA BlueField-2 SmartNICs, and commodity servers. The experimental results demonstrate that compared to existing solutions, Epiphron improves throughput by up to 2.2× and consumes 47% less memory while completely bypassing server CPUs.

Recent popular programmable switches provide programmability in packet processing at the line rate, promising to host various Network Functions (NFs). However, the limitations on the switch programmability make it unable to manage runtime dynamic NF states. In the status quo, on-switch NFs rely on the network controller for dynamic state management, suffering from high first-packet latency. This paper proposes DNF, a hardware-software co-design system for dynamic state management of network functions on programmable switches. DNF designs a dynamic State Table on the switch, which providesopportunisticservice to NF flows and sets upfallbackNFs on the server to handle flows that fail on the switch. DNF proposes a state pre-computation andruntime-bindingmethod for per-flow state initialization, which avoids a flow’s runtime interaction with the controller and the consequent latency. DNF devises astate replacementmethod, which periodically swaps hot flows into the switch. It could maximize the switch resource utilization and the throughput. We prototype DNF on P4 switches, implement six representative NFs, and compare DNF with state-of-the-art solutions. Our experiments show DNF reduces the first-packet latency by up to 98% compared with the controller-assisted architecture and improves the system throughput by up to 4.87 times compared with the software solution.

KVM is the dominant VM hypervisor on Linux, and relies on QEMU to realize the backends of the virtio family of devices such as virtio-blk. However, KVM/QEMU-based paravirtualization prolongs the guest I/O path with multiple context switches. As fast NVMe storage devices have been widely used, the software overhead becomes non-negligible. To shorten the I/O path, virtio-blk’s variations, vhost-kernel-blk and vhost-user-blk, respectively perform all guest I/O processing in kernel and user spaces. Unfortunately, they essentially forsake the collaboration between KVM and QEMU, sacrifice important QEMU features including live migration, snapshots, and flexible image format support. This article presents EXO, an extension of virtio-blk for efficient KVM/QEMU-based storage paravirtualization. The insight is that no matter how complex the QEMU backend’s processing is, to handle a guest I/O request, the host storage stack only needs to know the request’s guest-to-host address mapping. Therefore, we preserve the original slow I/O path of virtio-blk as a fallback, and leverage eBPF to introduce an in-kernel fast path that directly queries the address mapping without switching to the user-space backend processing. Extensive evaluation shows that EXO achieves similar or even higher performance compared to the variations (vhost-kernel-blk/vhost-user-blk) of virtio-blk, while preserving virtio-blk’s flexibility, safety, and compatibility.

High-capacity solid-state drives (SSDs) with expected capacities of one PByte and more will address cloud storage and archiving environments previously dominated by magnetic disks. These new applications are very cost-sensitive, so unnecessary overhead must be reduced as much as possible without sacrificing the performance advantages of SSDs. An expensive component within a scale-up SSD is the on-device memory to map host logical page numbers to flash pages. This article, therefore, proposes HyTorC, which builds on the idea of S-FTL to represent sequentially stored logical pages using bitmaps instead of providing one entry per logical page. HyTorC extends this idea by introducing, for the first time in an FTL, compression of these bitmaps using run-length encoding, and by investigating the effects of background scrubbing to realign randomly written pages into contiguous runs. This background scrubbing allows HyTorC to keep large portions of the mapping table in block mapping mode, further reducing the memory footprint. HyTorC retains the flexibility of the page mapping scheme and supports compression of logical blocks within the SSD, allowing multiple compressed logical pages to be stored within a single physical page. HyTorC is fully implemented in an open-channel SSD. Our tests show that HyTorC can reduce memory consumption by an average of 98.9% over standard page mapping, 95.6% over the DFTL scheme, 87.3% over S-FTL, and 56.5% over the learned index-based approach LeaFTL for the Alibaba Cloud block traces, and by 98.6% over standard page mapping, 95.5% over the DFTL scheme, 84.1% over S-FTL, and 61.5% over LeaFTL for the Microsoft Research Cambridge traces. HyTorC focuses on the memory footprint of the FTL and not on performance. However, the performance evaluation shows that HyTorC achieves similar performance compared to page mapping and FTLs based on learned indexes.

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

Neural Vector Search (NVS) has exhibited superior search quality over traditional key-based strategies for information retrieval tasks. An effective NVS architecture requires high recall, low latency, and high throughput to enhance user experience and cost-efficiency. However, implementing NVS on existing neural network accelerators and vector search accelerators is sub-optimal due to the separation between the embedding stage and vector search stage at both algorithm and architecture levels. Fortunately, we unveil that Product Quantization (PQ) opens up an opportunity to break separation. However, existing PQ algorithms and accelerators still focus on either the embedding stage or the vector search stage, rather than both simultaneously. Simply combining existing solutions still follows the beaten track of separation and suffers from insufficient parallelization, frequent data access conflicts, and the absence of scheduling, thus failing to reach optimal recall, latency, and throughput. To this end, we propose a unified and efficient NVS accelerator dubbed NeuVSA based on algorithm and architecture co-design philosophy. Specifically, on the algorithm level, we propose a learned PQ-based unified NVS algorithm that consolidates two separate stages into the same computing and memory access paradigm. It integrates an end-to-end joint training strategy to learn the optimal codebook and index for enhanced recall and reduced PQ complexity, thus achieving smoother acceleration. On the architecture level, we customize a homogeneous NVS accelerator based on the unified NVS algorithm. Each sub-accelerator is optimized to exploit all parallelism exposed by unified NVS, incorporating a structured index assignment strategy and an elastic on-chip buffer to alleviate buffer conflicts for reduced latency. All sub-accelerators are coordinated using a hardware-aware scheduling strategy for boosted throughput. Experimental results show that the joint training strategy improves recall by 4.6% over the separated strategy and accuracy by 43.5% over LUT-NN. NeuVSA achieves $2.82 \times$ to $416.17 \times$ lower latency over CPU, GPU, DFX+ANNA, and PQA+ANNA, and up to $49.60 \times$ and $10.57 \times$ higher average throughput over CPU and GPU, respectively. NeuVSA also reduces chip area by 65.2% over PQA+ANNA.

Continual Semantic Segmentation (CSS) aims to continuously learn new classes while mitigating catastrophic forgetting. Existing CSS methods primarily address this challenge through knowledge distillation. While they focus on maintaining stability for old classes, this emphasis often restricts plasticity in learning new ones. In this work, we propose two plug-and-play methods to better balance stability and plasticity. First, for feature map distillation, we replace pixel-level constraints with statistical information extraction within a window, improving the learning of new classes while preserving structural integrity to overcome forgetting. Second, we use relative ranks of predictions to replace exact probabilistic values to loosen the constraints in the logit distribution of old classes. Extensive experiments demonstrate that our methods outperform state-of-the-art methods when integrating into several baselines across various CSS scenarios.

Graph stream is a special kind of data stream, where every item coming in sequence represents an edge in a dynamic graph. Graph stream has wide application in many fields, including cyber security, social networks and financial fraud detection. In this paper, we propose HourglassSketch, a two-stage data structure, for high-accuracy graph stream summarization. In Stage 1, HourglassSketch uses a CocoSketch to accurately record a partial collection of large-weight edges. In Stage 2, HourglassSketch integrates a TowerSketch with a TCMSketch to approximately record the statistics of most small-weight edges. In addition, we propose a key technique named Error Funnel to further reduce its error margin. Theoretical analysis and experimental results demonstrate that HourglassSketch supports various kinds of query operation and adapts well to graph stream storage. HourglassSketch achieves up to 100x smaller error and 2.7x higher speed than prior work. We also explore the versatility of HourglassSketch as a hardware-friendly framework by implementing it on FPGA and P4 platforms. We have released our codes on GitHub.

GPU Direct Storage (GDS) plays a vital role in GPU-based training and inference systems, leveraging Peer-to-Peer Direct Memory Access (P2P-DMA) to establish a direct data transfer path between the GPU and the storage device. The direct I/O path reduces GPU storage access latency and CPU overhead, thus improving the efficiency of data transfer. Currently, however, GDS employs a phony buffer in the host memory to interact with the Linux kernel, which results in suboptimal I/O performance, extra resource consumption, and high deployment complexity.

Traditional DRAM-based memory solutions face challenges, including high energy consumption and limited scalability. Non-Volatile Memory (NVM) offers low energy consumption and high scalability. However, security challenges, particularly data remanence vulnerabilities, persist. Prevalent methods such as the Bonsai Merkle Tree (BMT) are employed to ensure data security. However, the consistency requirements for integrity tree updates have led to performance issues. It is observed that compared to a secure NVM system without persistent secure metadata, the average overhead for updating and persisting the BMT root with persistent secure metadata is as high as 2.48 times. Therefore, this paper aims to mitigate these inefficiencies by leveraging the principle of memory access locality. We propose the Dynamic Construction and Adjustment of Skewed Bonsai Merkle Tree (DCAS-BMT). The DCAS-BMT is dynamically built and continuously adjusted at runtime according to access weights, ensuring frequently accessed memory blocks reside on shorter paths to the root node. This reduces the verification steps for frequently accessed memory blocks, thereby lowering the overall cost of memory authentication and updates. Experimental results using the USIMM memory simulator demonstrate that compared to the widely used BMT approach, the DCAS-BMT scheme shows a performance improvement of 34.1%.

Key-value stores in Cloud environments can contain more than 2 45 unique elements and be larger than 100 PByte. B + -Trees are well suited for these larger-than-memory datasets and seamlessly index data stored on thousands of secondary storage devices. Unfortunately, it is often uneconomical to even store all inner tree nodes in memory for these dataset sizes. Therefore, lookup performance is affected by the additional IOs for reading inner nodes. This number of inner nodes can be reduced by increasing the size of leaf nodes. We propose HLN-Trees, which support huge leaf nodes without increasing the IO sizes for individual index operations. They partition leaf nodes in arrays of independent subnodes and combine ideas from BD-trees with rebalancing, learning key deviations, and storing locality predictors. HLN-Trees have been initially designed for uniform random key distributions and support arbitrary key distributions through an additional layer of hashing in leaf nodes. HLN-Trees decrease the number of inner nodes by up to 256× for uniform random key distributions and by 16× to 64× for arbitrary ones compared to B + -Trees, while keeping their performance at the same level even at high concurrency levels. We show analytically and through real-world and synthetic benchmarks that HLN-Trees also outperform state-of-the-art learned indexes for secondary storage.

Nowadays, data centers consolidate latency-critical (LC) tenants and best-effort (BE) tenants on the same cloud platform to increase resource utilization and reduce costs. In such a scenario, the underlying distributed storage systems are responsible for guaranteeing SLOs for LC tenants while maximizing bandwidth for BE tenants. As high-performance NVMe SSDs are widely deployed, how to make full use of their performance capabilities and guarantee SLOs has become an urgent problem. However, current methods restrict the performance capabilities of NVMe SSDs based on a conservative offline model, and also ignore runtime changes in tenant loads and device states, which definitely affect the performance capabilities.

Multi-scale detection based on Feature Pyramid Networks (FPN) has been a popular approach in object detection to improve accuracy. However, using multi-layer features in the decoder of FPN methods entails performing many convolution operations on high-resolution feature maps, which consumes significant computational resources. In this paper, we propose a novel perspective for FPN in which we directly use fused single-layer features for regression and classification. Our proposed model, You Only Look One Hourglass (YOLOH), fuses multiple feature maps into one feature map in the encoder. We then use dense connections and dilated residual blocks to expand the receptive field of the fused feature map. This output not only contains information from all the feature maps, but also has a multi-scale receptive field for detection. The experimental results on the COCO dataset demonstrate that YOLOH achieves higher accuracy and better run-time performance than established detector baselines, for instance, it achieves an average precision (AP) of 50.2 on a standard 3× training schedule and achieves 40.3 AP at a speed of 32 FPS on the ResNet-50 model. We anticipate that YOLOH can serve as a reference for researchers to design real-time detection in future studies. Our code is available at https://github.com/wsb853529465/YOLOH-main.

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

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

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

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

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

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

The write constraints of Multi-Level Cell (MLC) NAND flash memory make most of the existing flash translation layer (FTL) schemes inefficient or inapplicable. In this article, we solve several fundamental problems in the design of MLC flash translation layer. The objective is to reduce the garbage collection overhead to reduce the average system response time. We make the key observation that the valid pages copy is the essential garbage collection overhead. Based on this observation, we propose two approaches, namely, concentrated mapping and postponed reclamation, to effectively reduce the valid pages copy. Besides, we propose a progressive garbage collection that can well utilize the system idle time to reclaim more spaces. We conduct a series of experiments on an embedded developing board with a set of benchmarks. The experimental results show that our scheme can achieve a significant reduction in the average system response time compared with the previous work.

In this paper, we lead the first efforts towards intelligent RDF data management in SSDs. We propose to deeply fuse the RDF data in SSDs. In detail, the operations (e.g., data query) applied to RDF can be directly achieved in SSDs. To this end, we explore two RDF data organizations (e.g., triple-based) with the consideration of the internal structure of SSDs. The experiment is conducted on the Patient Disease Drug (PDD) Graph dataset [11]. The experimental results show that the proposed two strategies achieve the comprehensive, scalable in-SSD computation from different aspects (e.g., space efficiency or query efficiency).

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

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

Time-of-arrival (TOA) is a widely used localization technique in robotic localization systems. However, TOA-based methods require strict time synchronization between the source (target) and sensors (receivers), which significantly influences the localization accuracy. In this paper, we propose an iterative Time-of-arrival (iTOA) localization technique to eliminate the time synchronization error in robotic localization systems. iTOA first measures the distance between the source and sensors according to the travel time of the signal. Then, iTOA constructs the multivariate linear model based on the measured distances, position of sensors, and unknown synchronization error, and uses the least square method to calculate the synchronization error. Finally, by using the constructed model and iteratively subtracting the synchronization error, we obtain the precise source localization with the near-zero synchronization error. For the synchronization error elimination, iTOA can work well in both the two-dimensional (2-D) and 3-D space. We conduct experiments in both a simulation environment and a real sensor system to demonstrate the effectiveness of the proposed scheme. The experimental results show that the accuracy of localization is improved by more than 31% and 26% on average compared with the representative algorithms in the simulation and real environments, respectively.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SMS4 is a block cipher used in the Chinese National Standard for Wired Authentication and Privacy Infrastructure (WAPI). Like other cryptosystems, the SMS4 contains data-intensive computation, whose throughput makes a substantial contribution to the overall system performance. Design and implementation of the SMS4 cryptosystem to meet the real-time requirements of applications are challenge problems, especially for embedded network systems with limited computation resources. In this work, we present a systematic design approach of application-specific instruction-set processor (ASIP) for the SMS4 cryptographic algorithm, which exploits and compromises between the flexibility of software execution and the performance of the application-specific integrated circuit (ASIC) based implementation of the SMS4 cryptosystem. We identify and perform a design space exploration of the custom instructions found for the SMS4 algorithm, and extend the instruction set architecture (ISA) of a standard 32-bit RISC processor to accommodate them. We employ the Electronic System Level (ESL) methodology in the development of the proposed ASIP using the Xilinx Virtex5 LX110T FPGA platform. Results show that compared to the original RISC ISA, our ASIP for SMS4 achieves 2.93 times performance improvement and 52.4% less program memory utilization, with only 28.2% more resource required.