Memory disaggregation introduces new challenges for application reliability, as compute server or interconnection failures can interrupt execution and lead to data inconsistency in the memory server. This paper presents Fanmem, a novel failure-atomic transaction system designed specifically for disaggregated memory architectures. Fanmem ensures data consistency in the presence of failures, drawing inspiration from persistent memory transactions while tailored for memory disaggregation. The key innovations of Fanmem include an asynchronous transaction model and the integration of a processing unit within the switch, enabling the offloading of time-consuming log persistency operations to the switch processing unit and significantly reducing the overhead on the compute servers. Evaluation confirms the effectiveness of Fanmem on two representative memory-disaggregated architectures. Compared to the state-of-the-art persistent memory transaction system, Fanmem achieves an average performance improvement of 1.2X and 1.7X on the respective architectures.

Graph pattern mining is essential for analyzing dynamic networks, where graphs evolve over time. To accommodate these changes, existing solutions update match sets incrementally, avoiding the need to re-mine the entire graph and achieving significant performance improvements. However, these methods suffer from inefficiencies due to redundant set intersection operations across subgraph instances, causing performance degradation.

Transformer-based large language models (LLMs) exhibit remarkable generative capabilities, but their inference throughput is limited by the autoregressive decoding process, which generates only one token per iteration. Speculative decoding mitigates this bottleneck by using a lightweight draft language model (DLM) to generate multiple draft tokens, which are then verified in parallel by a more accurate target language model (TLM). To accommodate the differing computational patterns of the DLM and TLM, prior work has leveraged heterogeneous systems combining xPUs and processing-in-memory (PIM) units to offload compute- and memory-intensive operators, respectively. However, existing systems often adopt a fixed draft sequence length, leading to excessive rejection of draft tokens during verification-especially under large-batch scenarios-resulting in redundant computation and reduced efficiency. This paper proposes a runtime adaptive draft length adjustment technique that dynamically tailors the draft length for each request by monitoring cumulative acceptance probabilities, thereby minimizing the generation and verification of invalid tokens. Yet, integrating adaptive draft lengths into existing PIM-enabled heterogeneous systems introduces two new challenges: (1) sequential execution of the DLM and TLM becomes inefficient due to synchronization bubbles caused by request-wise variability in draft lengths, and (2) static operator mappings become suboptimal as draft length variability alters operator arithmetic intensities dynamically. To address these issues, we introduce SADDLE, a PIM-enabled heterogeneous system designed to exploit adaptive draft lengths effectively. SADDLE incorporates two key mechanisms: (1) an asynchronous speculative decoding pipeline that decouples DLM prediction and TLM verification to reduce idle time, and (2) an arithmetic intensity-aware operator scheduler that dynamically assigns operators to the most suitable hardware units. Experimental results show that SADDLE achieves average speedups of$\mathbf{2. 8 8} \times$over a state-of-the-art GPU-only solution and$\mathbf{1. 7 1} \times$over the best-performing GPU+PIM baseline.

Mining temporal motifs in temporal graphs is essential for many critical applications. Although several solutions have been proposed to handle temporal motif mining, they still suffer from substantial inefficiencies due to significant redundant graph traversals and fragmented memory access, both caused by irregular search tree expansions across different motif matching tasks. In this work, we observe that data accesses issued by these tasks exhibit strong spatial similarity and temporal monotonicity. Based on these observations, this paper proposes an efficient data-centric temporal motif mining system DTMiner, which introduces a novel Load-Explore-Synchronize (LES) execution model to efficiently regularize data accesses to the common temporal graph data among different tasks. Specifically, DTMiner enables the temporal graph chunks to be sequentially loaded into the cache in temporal order and then triggers all relevant tasks to explore only these loaded data for search tree expansions in a fine-grained synchronization mechanism. In this way, different tasks can share the graph traversal corresponding to the same chunks, while fragmented memory accesses are restricted to the graph data residing in the cache, significantly reducing data access overhead. Experimental results demonstrate that DTMiner achieves 1.14×-11.98× performance improvement in comparison with the state-of-the-art temporal motif mining solutions.

Retrieval-Augmented Generation (RAG) enhances Large Language Models (LLMs) by leveraging external knowledge, where retrieval accuracy directly affects generation quality. However, dense retrievers, commonly employed in RAG, suffer degraded performance in evolving corpora where new documents arrive continuously and distribution shifts accumulate over time. In such settings, continually updating retrievers is crucial, yet conventional retraining is computationally expensive and often impractical. To address this challenge, we propose FlowRAG, a lightweight and effective method for continual retriever adaptation in evolving corpora. FlowRAG augments the encoder with Layer-wise Prompt Embeddings and introduces a Cross-Layer Fusion mechanism to capture hierarchical semantic representations. In addition, a novel Generator-Guided Loss aligns retriever scores and intermediate representations with the LLM's generation likelihoods, encouraging retrieval decisions that are both semantically relevant and beneficial for generation. Experiments on datasets spanning four domains demonstrate that FlowRAG, which updates only about 0.64% of the total model parameters, consistently outperforms strong baselines in retrieval accuracy, generation quality, and robustness to forgetting in non-stationary settings.

Efficient processing of streaming graphs is crucial to improve system performance. Due to the highly irregular and frequent access to data in streaming graph processing, existing cache management methods are difficult to accurately predict cache behavior, resulting in serious cache misses. To address the issues, we propose CEGraph, an efficient cache management approach for streaming graph processing. Specifically, for graph data, we propose a cache replacement policy based on vertex importance. This policy accurately evaluates the importance of vertices in the incremental processing of streaming graphs from our proposed three factors: the association degree of affected state of a vertex, the path distance of a vertex, and whether a vertex will be updated. Vertices with high importance are identified and kept in the cache to reduce cache thrashing. Experimental results reveal that compared with LRU, DRRIP and Grasp, CEGraph reduces the LLC misses by an average of 22.93% (maximum 34.27%), 20.87% and 11.91%, respectively. Compared with the state-of-the-art cache management method P-OPT, CEGraph reduces the LLC misses by 6.46% on average, therefore demonstrating the effectiveness of CEGraph.

Breast cancer remains a leading cause of mortality among women, with millions of new cases diagnosed annually. Early detection through screening is crucial. Using neural networks to improve the accuracy of breast cancer screening has become increasingly important. In accordance with radiologists' practices, we proposed using images from the unaffected side to create adversarial samples with critical medical implications in our adversarial learning process. By introducing beneficial perturbations, this method aims to reduce overconfidence and improve the precision and robustness of breast cancer classification. Our proposed framework is an adversarial quadruple-view classification network (NaFV-Net) incorporating images from both affected and unaffected perspectives. By comprehensively capturing local and global information and implementing adversarial learning from four mammography views, this framework allows for the fusion of features and the integration of medical principles and radiologist evaluation techniques, thus facilitating the accurate identification and characterization of breast tissues. Extensive experiments have shown the high effectiveness of our model in accurately distinguishing between benign and malignant findings, demonstrating state-of-the-art classification performance on both internal and public datasets.

Tackling temporal path problems in temporal graphs is essential for time-sensitive applications. Although many solutions have been proposed to handle temporal path problems, due to the intrinsic time constraints, these solutions require the vertices of the temporal graph to be sequentially handled along the time-dependent chains (i.e., the temporal dependencies between these vertices) to form the temporal path. This sequential temporal nature poses the challenges of poor parallelism and slow convergence speed, preventing existing solutions from fully leveraging the massive parallelism and high internal bandwidth of GPU to handle temporal path problems. To overcome these challenges, this paper proposes TempGraph, an efficient chain-driven GPU-based temporal graph computing framework. Specifically, it transforms the temporal graph into a set of disjoint time-dependent chains that can elegantly expose the temporal dependency between the vertices while facilitating the fast path exploration along these chains over GPU. Furthermore, TempGraph employs a novel Generate-Activate-Compute execution model to decouple the temporal dependency between different chains through maintaining a set of shortcuts for them, which enables multiple chains to be concurrently handled by massive GPU threads, achieving fast convergence speed and high parallelism on the GPU. Experiments on an A100 GPU show that TempGraph outperforms the state-of-the-art GPU-based solutions by 3.0-16.2×. Besides, TempGraph on an A100 GPU gains 33.9-368.9× speedups compared to the cutting-edge CPU-based system TeGraph on a 128-core CPU machine.

Approximate nearest neighbor search (ANNS) is crucial in many applications to find semantically similar matches for user queries. Especially with the development of large language models (LLMs), ANNS is becoming increasingly important in retrieval-augmented generation (RAG). An in-depth analysis of ANNS reveals that its diverse operations, from extensive memory access to intensive sorting, are key performance bottlenecks, imposing significant strain on both the memory system and computing resources. Based on these observations, we present SeIM, a hierarchical in-memory architecture to accelerate ANNS. SeIM is designed to accommodate the diverse operational characteristics of ANNS. Specifically, SeIM offloads highly parallel memorybound operations to the memory bank level and introduces a unified execution model to reuse hardware units, requiring only lightweight modifications to standard DRAM architecture. Additionally, SeIM places compute-bound sorting operations, which require cross-unit data access, at the memory controller level and employs an adaptive transmission filtering technique to reduce unnecessary data transfers and processing during sorting. Our evaluation shows that SeIM achieves $268 \times 22 \times$, and $5 \times$ higher throughput, $306 \times 59 \times$, and $4 \times$ lower latency, and $3081 \times$, $287 \times$, and $2 \times$ higher power efficiency than state-of-the-art CPU-, GPU-, and ASIC-based ANNS solutions.

Adaptive Radix Tree (ART) is a widely used tree index structure prevalent in various domains such as databases and key-value stores. Despite many solutions have been proposed to improve the performance of ART, they still suffer from significant redundant tree traversals and serious synchronization cost when concurrently performing the operations (e.g., read/write) over ART. In this work, we observe that most operations of realworld workloads tend to target a small subset of ART nodes frequently, exhibiting strong temporal and spatial similarities among the operations. Based on this observation, we propose a data-centric hardware accelerator, called DCART, to efficiently support the operations over ART. Specifically, DCART proposes a novel data-centric processing model into the accelerator design to coalesce the operations associated with the same ART nodes and adaptively cache the frequently traversed ART nodes and their search results, thereby fully exploiting the similarities among the operations for lower tree traversal and synchronization overhead. We implemented DCART on the Xilinx Alveo U280 FPGA card and compared it with the cutting-edge solutions, DCART achieves $21.1 \times-44.2 \times$ speedups and $71.1 \times-148.9 \times$ energy savings.

Hypergraph Pattern Mining (HPM) aims to identify all the instances of user-interested subhypergraphs (patterns) in hypergraphs, which has been widely used in various applications. However, existing solutions either need significant enumeration overhead because they extend subhypergraphs at the granularity of vertices, or suffer from massive redundant computations because they often need to repeatedly fetch and process the same incident hyperedges for different vertices. This paper presents an overlap-centric system named OHMiner to efficiently support HPM. OHMiner proposes an overlap-centric execution model to determine the subhypergraphs isomorphism through computing and comparing overlaps among hyperedges using set operations. This model aims to efficiently handle the vertices that collectively share the same incident hyperedges. To automatically and precisely retrieve an arbitrary pattern's overlapping semantics without performing redundant set computations, OHMiner further proposes a redundancy-free compiler, which constructs an Overlap Intersection Graph (OIG) for the pattern, optimizes the OIG, and generates an overlap-centric execution plan to guide the procedure of HPM. Moreover, OHMiner designs an overlap-centric parallel execution engine, which adopts an incremental overlap-pruned approach to fast validate candidates for HPM. Additionally, it proposes a degree-aware data store to support efficient generation of candidates. Through evaluating OHMiner on a broad range of real-world hypergraphs with various patterns, our experimental results show that OHMiner outperforms the state-of-the-art HPM system by 5.4×-22.2×.

Heterogeneous Graph Neural Networks (HGNNs) are pivotal for extracting semantic and structural information from heterogeneous graphs. Traditional HGNN implementations often grapple with the challenges of excessive metapath instances, requiring substantial storage or incurring high instance-matching overhead. These methods typically suffer from redundant instance encoding and costly semantic graph construction. Addressing these issues, we introduce an advanced Metapath Graph (MG) abstraction that encapsulates the structural information of all metapath instances within a compact representation. This approach significantly reduces storage demands, eliminates redundant instance encodings, and foregoes the need for constructing semantic graphs, thereby facilitating rapid HGNN inference. Our software-based system, MetaHG, leverages layerwise encoding and aggregation to avoid redundancies without the necessity of semantic graphs. It incorporates a fast, lightweight partitioning method to efficiently manage large graphs. Distinctively, MetaHG seamlessly integrates with both dynamic HGNNs and homogeneous GNNs, unlike conventional systems. Comparative evaluations demonstrate that MetaHG surpasses the state-of-the-art BFS- and DFS-based HGNN systems, MAGNN and the software implementation of MetaNMP, by 42.5× and 4.53×, respectively, on average.

Hypergraph Neural Networks (HGNNs) are increasingly utilized to analyze complex inter-entity relationships. Traditional HGNN systems, based on a hyperedge-centric dataflow model, independently process aggregation tasks for hyperedges and vertices, leading to significant computational redundancy. This redundancy arises from recalculating shared information across different tasks. For the first time, we identify and harness implicit dataflows (i.e., dependencies) within HGNNs, introducing the microedge concept to effectively capture and reuse intricate shared information among aggregation tasks, thereby minimizing redundant computations. We have developed a new microedge-centric dataflow model that processes shared information as fine-grained microedge aggregation tasks. This dataflow model is supported by the Read-Process-Activate-Generate execution model, which aims to optimize parallelism among these tasks. Furthermore, our newly developed MeHyper, a microedge-centric HGNN accelerator, incorporates a decoupled pipeline for improved computational parallelism and a hierarchical feature management strategy to reduce off-chip memory accesses for large volumes of intermediate feature vectors generated. Our evaluation demonstrates that MeHyper substantially outperforms the leading CPUbased system PyG-CPU and the GPU-based system HyperGef, delivering performance improvements of $1,032.23 \times$ and $10.51 \times$, and energy efficiencies of $1,169.03 \times$ and $9.96 \times$, respectively.

By integrating external knowledge bases, Retrieval-augmented Generation (RAG) enhances natural language generation for knowledgeintensive scenarios and specialized domains, producing content that is both more informative and personalized.RAG systems typically consist of two fundamental stages: retrieval and generation.The retrieval stage experiences low bandwidth utilization due to its random and irregular memory access patterns.Meanwhile, the generation stage is also constrained by memory bandwidth limitations, which arise from involving a significant number of General Matrix-Vector Multiplications (GEMV) operations.These two stages collectively lead to memory bottlenecks within RAG systems.Recent efforts leverage HBM-based Processing-in-Memory (PIM) to accelerate conventional Large Language Models (LLMs).However, the retrieval stage incurs substantial storage overhead due to the need to maintain large-scale knowledge bases, resulting in a capacity bottleneck.Solely relying on HBM-based PIM in RAG is both costly and insufficient to meet the capacity demands.Fortunately, DIMM-based PIM provides a low-cost, high-capacity alternative that complements HBM.In this work, we propose HeterRAG, a novel heterogeneous PIM acceleration system for RAG.It combines

Graph Convolutional Networks (GCNs) are a fundamental approach to deep learning on graph-structured data. However, they face a significant challenge in training efficiency due to the high computational cost of Sparse-Dense Matrix Multiplication (SpMM). This paper presents StraGCN, the first GPU-accelerated SpMM implementation based on Strassen’s algorithm particularly designed for GCN training. First, we propose a horizontal fusion model for GPU kernels as an alternative to the commonly used multi-stream CUDA model, significantly improving data locality of on-chip shared memory for Strassen’s SpMM. Second, StraGCN exploits the immutability of the adjacency matrix in GCNs to reuse intermediate results from submatrix operations, substantially reducing redundant computations. Third, we propose a two-stage matrix partitioning scheme to mitigate load imbalance caused by the irregular distribution of non-zero elements. We evaluate StraGCN with fifteen benchmark datasets. Experimental results show that StraGCN achieves performance speedups of 2.1 ×, 2.6 ×, and 3.3 × compared with state-of-the-art GCN frameworks–GNNA, PyG, and DGL, respectively.

The emerging Mixture-of-Experts (MoE) model mitigates the high compute cost of large-scale LLMs by sparsely activating a subset of experts during inference. However, MoE requires storing massive expert parameters, creating a severe memory bottleneck on resource-constrained GPUs. Existing approaches offload parameters to host memory and prefetch activated experts to GPU memory with sophisticated policies, but these solutions are tailored to single-batch inference and suffer from communication bottlenecks at larger batch sizes, limiting throughput. We identify two forms of locality in expert activation: a small set of experts are frequently invoked across inference (global locality), while others recur within short decoding bursts (temporal locality). To exploit this, we propose Diff-MoE, which introduces a differential cache hierarchy in GPU memory. Globally hot experts reside in per-layer high-priority caches, locally hot ones are dynamically managed in per-layer medium-priority caches under a priority-driven replacement policy, and the remaining cold experts are cached temporarily and evicted on demand. Moreover, Diff-MoE incorporates a lightweight predictor that prefetches experts likely needed in the next MoE layer, overlapping migration with computation to further reduce latency. Our evaluation shows that Diff-MoE improves inference throughput by 2.74 ×, 2.22 ×, and 1.55 × over DeepSpeed, Pre-gated MoE, and MoE-Infinity, respectively.

Queries on linked data structures, such as trees and graphs, often suffer from frequent cache misses and significant performance loss due to dependent and random pointer-chasing memory accesses. In this article, we propose a software-hardware co-designed solution for accelerating linked data structures implemented in strongly typed languages. The solution incorporates a compiler extension and a hardware prefetcher. The compiler extension extracts type information from the code, annotates each load instruction, and forwards the type information to the hardware prefetcher. The prefetcher leverages the type information to fetch the referred objects and identify the associated pointers in advance. By doing so, the program can find these objects in the cache when it follows the prefetched pointers, thus minimizing cache misses. In the evaluation, the proposed solution achieves an average speedup of 1.37× over a set of memory-intensive benchmarks.

Graph pattern mining is essential for deciphering complex networks. In the real world, graphs are dynamic and evolve over time, necessitating updates in mining patterns to reflect these changes. Traditional methods use fine-grained incremental computation to avoid full re-mining after each update, which improves speed but often overlooks potential gains from examining inter-update interactions holistically, thus missing out on overall efficiency improvements. In this article, we introduce Cheetah, a dynamic graph mining system that processes updates in a coarse-grained manner by leveraging exploration domains . These domains exploit the community structure of real-world graphs to uncover data reuse opportunities typically missed by existing approaches. Exploration domains, which encapsulate extensive portions of the graph relevant to updates, allow multiple updates to explore the same regions efficiently. Cheetah dynamically constructs these domains using a management module that identifies and maintains areas of redundancy as the graph changes. By grouping updates within these domains and employing a neighbor-centric expansion strategy, Cheetah minimizes redundant data accesses. Our evaluation of Cheetah across five real-world datasets shows it outperforms current leading systems by an average factor of 2.63×.

Graph processing has become a central concern for many real-world applications and is well-known for its low compute-to-communication ratios and poor data locality. By integrating computing logic into memory, resistive random access memory (ReRAM) tackles the demand for high memory bandwidth in graph processing. Despite the years’ research efforts, existing ReRAM-based graph processing approaches still face the challenges of redundant computation overhead . It is because the vertices of many subgraphs are ineffectively and repeatedly processed over the ReRAM crossbars for lots of iterations so as to update their states according to the vertices of other subgraphs regardless of the dependencies among the subgraphs. In this article, we propose ASGraph , a dependency-aware ReRAM-based graph processing accelerator that overcomes the aforementioned performance bottlenecks. Specifically, ASGraph dynamically constructs the subgraph based on the dependencies between vertices’ states and then detects constructed subgraph that owns high value (it is likely that it has accumulated many state propagations from its neighbors and is able to affect more other neighbors) to be preferentially processed. In this way, it makes the vertex states propagate along the dependencies between vertices as much as possible to reduce the redundant computation. Besides, ASGraph employs a hybrid processing scheme to accelerate the state propagations of the tightly connected subgraph, thereby minimizing the redundant computations. Experimental results show that ASGraph achieves 25.5× and 4.8× speedup and 70.8× and 2.2× energy saving on average compared with the state-of-the-art ReRAM-based graph processing accelerators, that is, GraphR and GaaS-X, respectively.

Graph processing is pivotal in deriving insights from complex data structures but faces performance limitations due to the irregular nature of graphs. Traditional general-purpose processors often struggle with low instruction-level parallelism and energy inefficiency when handling graph data. In response, modern graph accelerators have embraced an intra-edge-parallel model to enhance parallelization, significantly outperforming conventional processors. However, the indiscriminate processing of edges in existing systems results in substantial computational redundancy, negatively impacting overall efficiency. This article introduces PRAGA, an innovative graph accelerator designed to optimize efficiency by selectively processing edges that significantly contribute to final results while preserving high computational parallelism. PRAGA utilizes an intra-edge-sequential model, prioritizing edge processing to capitalize on coarse-grained vertex-level parallelism and minimize unnecessary computations. It incorporates a hot-value manager to alleviate network-on-chip congestion and a memory-aware coalescer to minimize redundant data accesses. Our experimental results, obtained using a Xilinx Alveo U280 FPGA accelerator card, demonstrate that PRAGA achieves speedups of 17.88× and 5.86× over state-of-the-art accelerators ScalaGraph and GraphDyns, respectively, and outperforms the advanced GPU-based system Gunrock by 22.52× on average. This substantial improvement underscores PRAGA’s potential to redefine performance benchmarks in graph processing.

Decentralized Applications (DApps) have garnered significant attention due to their decentralization, anonymity, and data autonomy. However, these systems face potential privacy challenge. The privacy challenge arises from the necessity for external service providers to collect and process user interaction data. The untrustworthiness of these providers may lead to privacy breaches, compromising the overall security of such DApp environments. To address this challenge, we model the interaction data in the DApp environments as dynamic graphs and propose a dynamic graph publication method named HMG (Hidden Markov Model for Dynamic Graphs). HMG estimates the interaction probabilities between users by extracting the temporal information from historically collected data and constructs an optimized model to generate synthetic graphs. The synthetic graphs can preserve the dynamic topological characteristics of the interaction processes within DApp environments while effectively protecting user privacy, thus assisting external service providers in performing effective analyses. Finally, we evaluate the performance of HMG using real-world datasets and benchmark it against commonly used graph metrics. The results demonstrate that the synthetic graphs preserve essential features, making them suitable for analysis by service providers.

Hyperdimensional computing (HDC) is a human brain-inspired computing paradigm that processes neural activity patterns with high dimensional vectors. Existing HDC accelerators usually utilize different hardware architectures to process encoding phases and comparison phases of HDC applications separately. They are unable to adapt to dynamic workloads for various datasets, resulting in resource underutilization. In this article, we propose a resistive random access memory (ReRAM)-based HDC accelerator called ReHDC for general HDC. We abstract the computing paradigms in encoding and comparison phases, and provide uniform primitive operators to efficiently process these two phases with the same hardware architecture. In the unified processing engine, ReHDC utilizes analog crossbar arrays to accelerate accumulation operations, and digital crossbar arrays to speed up high-dimensional element-wise operations (xor). Experimental results show that ReHDC can accelerate the HDC training by$69.4\times $and$1.93\times $, and can also improve the energy efficiency by$51.5\times $and$2.2\times $, compared with NVIDIA Tesla P100 GPU and the ReRAM-based HDC accelerator DUAL, respectively. Moreover, the performance speedup and energy efficiency for HDC inference are similar to that of HDC training.

Graph data analysis has been used in various real-world applications to improve services or scientific research, which, however, may expose sensitive personal information. Differential privacy (DP) has become the gold standard for publishing graph data while still protecting personal privacy. However, most existing studies over differentially private graph data publication mainly focus on static unweighted graphs. As interactions between entities in real systems are often dynamically changing and associated with weights, it is desirable to consider the more general scenario of continuous weighted graph publication under DP in the temporal dimension. Therefore, we investigate the problem of publishing weighted graphs satisfying DP under continuous monitoring. Specifically, we consider a server that continuously monitors user data and publishes a sequence of weighted graph snapshots. We propose SwgDP, a novel framework that leverages historical graph data to guide current snapshot generation. SwgDP consists of four key components: node adaptive sampling, dynamic weight optimization, prediction-based community detection and weighted graph generation. We demonstrate that SwgDP satisfies DP, and comprehensive experiments on four real-world datasets and four commonly used graph metrics show that SwgDP can effectively synthesize weighted graph at any time step.

Pipeline parallelism has emerged as an indispensable technique for training large deep neural networks. While existing asynchronous pipeline systems address the time bubbles inherent in synchronous architectures, they continue to suffer frominefficiencyandsusceptibilitytovolatilehardware environment due to their suboptimal andstaticconfigurations. In this paper, we propose DynPipe, aninterference-awareasynchronous pipeline framework to optimize theend-to-endtraining performance in highlydynamiccomputing environments. By characterizing thenon-overlappedcommunication overheads andconvergencerate conditioned on stage-wise staleness, DynPipe carefully crafts an optimized pipeline partition that harmonizes the hardware speed with statistical convergence. Moreover, DynPipe deploys anon-intrusiverandom forest model that utilizes runtime stage statistics to evaluate the impact of environmental changes, such as task interference and network jitter, on the training efficiency. Following the evaluation guidance, DynPipe adaptivelyadjustspartition plan to restore both intra and inter-stage load balancing, thereby facilitating seamless pipeline reconfiguration in dynamic environments. Extensive experiments show that DynPipe outperforms state-of-the-art systems, accelerating the time-to-accuracy by1.5-3.4×.

The memory-intensive embedding layer in recommendation model continues to be the performance bottleneck. While prior works have attempted to improve the embedding layer performance by exploiting the data locality to cache the frequently accessed embedding vectors and their partial sums. However, these solutions rely on the static cache, which is inapplicable in the embedding training scenario where the embedding vectors are updated frequently. To this end, this paper proposes ReFree, a redundancy-free near-memory processing (NMP) solution for recommendation model training. Specifically, ReFree identifies the reusable data in realtime for both embedding layer forward and backward stages and leverages a lightweight NMP architecture to enable redundancy-free near-memory acceleration of the entire embedding training process. Evaluation results on real-world datasets show that ReFree outperforms the state-of-the-art solutions by 10.9× and reduces 5.3× energy consumption on average.

Memory disaggregation, facilitated by Smart Network Interface Cards (SmartNICs), has emerged as a cost-effective approach for sharing memory resources in data centers. However, current SoC-based SmartNICs face several challenges for supporting near-data processing (NDP) in disaggregated memory (DM) systems effectively, such as inefficient resource allocation for SmartNICs employed in NDP, and the lack of collaboration between SmartNICs on data nodes and CPUs on compute nodes. To address these issues, we propose TIGA, an efficient NDP framework for SmartNICs-based disaggregated memory systems. We propose an adaptive resource allocator to fully utilize the SoC cores among NDP engines automatically, and a SmartNIC-CPU cooperative computing mechanism to schedule NDP tasks among CPUs and SmartNICs. We prototype TIGA with FPGAs and evaluate it with several typical workloads. Experimental results show that TIGA significantly improves the efficiency of NDP tasks in DM systems compared with state-of-the-art SmartNIC-based co-processing schemes.

Sparse general matrix-matrix multiplication is widely used in data mining applications. Its irregular memory access patterns limit the performance of general-purpose processors, thus motivating many FPGA-based hardware innovations in recent years. Nevertheless, existing accelerators fail to efficiently support heterogeneous input matrix sparsity, which is universal in various real-world applications. With in-depth experimental analysis, we observe that their performance is bottlenecked by their fixed tiling mechanisms, which only alleviate the irregularity of one input matrix. Based on the observation, we propose SpaHet, a software/hardware co-design to accelerate heterogeneous-sparsity based sparse matrix multiplication. SpaHet adopts a dual-adaptive sliding window mechanism to cover the reuse characteristics of both input matrices simultaneously. With a specialized exploration algorithm, the window-based mechanism can automatically find the optimal tiling strategy instead of applying a fixed one based on empirical experience. A sparsity-aware merge tree is also proposed to maximize the output matrix reuse via accumulating intermediate results thoroughly. Our results on a Xilinx Alveo U280 accelerator card show that SpaHet outperforms state-of-the-art CPU-, GPU- and FPGA-based solutions by 7.71×, 1.1×, and 2.74× in performance, respectively.

With the merits of high productivity and ease of use, highlevel synthesis (HLS) tools bring hope to fast FPGA-based architecture development. However, their usability and popularity are still limited due to lack of support for dynamic memory management (DMM). Though HLS-compatible DMM solutions have been proposed recently, nevertheless, based on our investigation, none of them can hit high performance (i.e., minimal memory (de-)allocation latency) and resource efficiency (i.e., managing arbitrarily sized memory with minimal FPGA resource consumption) with one stone, seriously limiting their practicality. In response, we propose HeroDMM, a high-performance and resource-efficient dynamic memory manager for HLS. Specifically, HeroDMM organizes the managed memory area with a novel cartesian-like tree (CT) structure, a key to resolving the dilemma between (de-)allocation latency and resource efficiency standing in front of prior efforts. With the CT structure, HeroDMM further devises a delicate memory management algorithm and specializes the hardware implementation for achieving ever-higher performance while ensuring resource efficiency. Results show that HeroDMM outperforms state-of-the-art HLS-compatible DMM solutions by 61.69%~99.99% in performance improvement and 23.79%~97.22% in resource consumption savings.

Asynchronous Graph Neural Network (AGNN) has attracted much research attention because it enables faster convergence speed than the synchronous GNN. However, existing software/hardware solutions suffer from redundant computation overhead and excessive off-chip communications for AGNN due to irregular state propagations along the dependency chains between vertices. This paper proposes a chain-driven asynchronous accelerator, CDA-GNN, for efficient AGNN inference. Specifically, CDA-GNN proposes a chain-driven asynchronous execution approach into novel accelerator design to regularize the vertex state propagations for fewer redundant computations and off-chip communications and also designs a chain-aware data caching method to improve data locality for AGNN. We have implemented and evaluated CDA-GNN on a Xilinx Alveo U280 FPGA card. Compared with the cutting-edge software solutions (i.e., Dorylus and AMP) and hardware solutions (i.e., BlockGNN and FlowGNN), CDA-GNN improves the performance of AGNN inference by an average of 1,173x, 182.4x, 10.2x, and 7.9x and saves energy by 2,241x, 242.2x, 12.4x, and 8.9x, respectively.

Temporal Graph Neural Network (TGNN) has attracted much research attention because it can capture the dynamic nature of complex networks. However, existing solutions suffer from redundant computation overhead and excessive off-chip communications for TGNN inference because they often rely on redundant graph sampling and repeatedly fetching the features and vertex memory. This paper proposes a redundancy-free accelerator, RTGA, for high-performance TGNN inference. Specifically, RTGA proposes a redundancy-aware execution approach with temporal tree into a novel accelerator design to effectively eliminate unnecessary data processing for fewer redundant computations and off-chip communications and also designs a temporal-aware data caching method to improve data locality for TGNN. We have implemented and evaluated RTGA on a Xilinx Alveo U280 FPGA card. Compared with cutting-edge software solutions (i.e., TGN and TGL) and hardware solutions (i.e., BlockGNN and FlowGNN), RTGA improves the performance of TGNN inference by an average of 473.2x, 87.4x, 8.2x, and 6.9x and saves energy by 542.8x, 102.2x, 9.4x, and 8.3x, respectively.

On FPGAs, customizing data parallelism can significantly improve performances of applications. However, a large number of applications, such as sparse matrix multiplication, exhibit irregular memory access patterns, for which further improvements are limited by their low memory access efficiency. It is challenging to solve using traditional caches due to the massive cache misses. To address this, prior research efforts are dedicated to developing non-blocking caches withMiss Status Holding Registers (MSHRs) to manage the cache misses and mitigate stalls caused by the misses. However, exsiting approaches allocate dedicatedBlock RAMs (BRAMs) for implementing MSHRs. It introduces complexities in MSHR configurations and potential resource inefficiencies, as MSHR demand is highly dynamic when solving real-world problems. In this paper, we present MiCache, an MSHR-inclusive non-blocking cache design where cache entries and MSHR entries share the same storage spaces to support the dynamic demand for MSHRs during the executions of applications. We design a consistent storage structure for cache and MSHR entries, ensuring a unified and efficient mechanism for cache/MSHR lookup and data access. To further improve the performance, we design a parallel dual pipeline, one of which processes the requests from processing elements, and the other processes the responses from off-chip memory. We implement and evaluate our proposal on a Xilinx Alveo U280 board. Evaluation results show that, compared to the state-of-the-art non-blocking cache design on FPGAs, with equivalent cache configurations, MiCache reduces the BRAM consumption by up to 17%. When using the same amount of BRAM resources, MiCache achieves up to 1.56x performance improvement.

Recently, Graph Neural Networks (GNNs) have emerged as powerful tools for data analysis, surpassing traditional algorithms in various applications. However, the growing size of real-world datasets has outpaced the capabilities of centralized CPU or G PU - based systems. To address this challenge, numerous distributed systems have been proposed. However, these systems suffer from low hardware utilization due to slow network data exchange. While SSDs provide a promising alternative with large capacity and improved access latency, SSD-based G NN training on a single computer is bottlenecked by slow PCIe bus data transfer. This bottleneck leads to low CPU and G PU utilization, as confirmed by our experiments. Moreover, the design of in-SSD GNN training is hindered by slow access to flash memory. FlashGNN is a proposed solution that overcomes the PCIe bottleneck, fully utilizes I/O parallelism in flash chips, and maximizes data reuse from fetched flash memory chunks for efficient GNN training. We achieve this by designing the SSD firmware to coordinate data movements and hardware unit access. To address design challenges arising from slow flash memory and limited resources, we propose a novel node-wise GNN training method, an efficient scheduling algorithm for flash requests, and a high-performance subgraph generation method. Experimental results demonstrate that FlashGNN outperforms Ginex, a state-of-the-art SSD-based GNN training system, with a speed-up ratio ranging from 4.89× to 11.83 × and achieves energy savings of 57.14 × to 192.66 × for four typical real-world graph datasets. Additionally, FlashGNN is up to 23.17 × more efficient than the enhanced state-of-the-art in-storage accelerator, SmartSAGE+.

Transactional stream processing engines (TSPEs) have gained increasing attention due to their capability of processing real-time stream applications with transactional semantics. However, TSPEs remain susceptible to system failures and power outages. Existing TSPEs mainly focus on performance improvement, but still face a significant challenge to guarantee fault tolerance while offering high-performance services. We revisit commonly-used fault tolerance approaches in stream processing and database systems, and find that these approaches do not work well on TSPEs due to complex data dependencies. In this paper, we propose a novel TSPE called MorphStreamR to achieve fast failure recovery while guaranteeing low performance overhead at runtime. The key idea of MorphStreamR is to record intermediate results of resolved dependencies at runtime, and thus eliminate data dependencies to improve task parallelism during failure recovery. MorphStreamR further mitigates the runtime overhead by selectively tracking data dependencies and incorporating workload-aware log commitment. Experimental results show that MorphStreamR can significantly reduce the recovery time by up to 3.1 x while experiencing much less performance slowdown at runtime, compared with other applicable fault tolerance approaches.

Personalized recommendation systems have become one of the most important Internet services nowadays. A critical challenge of training and deploying the recommendation models is their high memory capacity and bandwidth demands, with the embedding layers occupying hundreds of GBs to TBs of storage. The advent of memory disaggregation technology and Compute Express Link (CXL) provides a promising solution for memory capacity scaling. However, relocating memory-intensive embedding layers to CXL memory incurs noticeable performance degradation due to its limited transmission bandwidth, which is significantly lower than the host memory bandwidth. To address this, we introduce ReCXL, a CXL memory disaggregation system that utilizes near-memory processing for scalable, efficient recommendation model training. ReCXL features a unified, hardwareefficient NMP architecture that processes the entire embedding training within CXL memory, minimizing data transfers over the bandwidth-limited CXL and enhancing internal bandwidth. To further improve the performance, ReCXL incorporates softwarehardware co-optimizations, including sophisticated dependencyfree prefetching and fine-grained update scheduling, to maximize hardware utilization. Evaluation results show that ReCXL outperforms the CPU-GPU baseline and the naïve CXL memory by $7.1 \times \sim 10.6 \times(9.4 \times$ on average) and $12.7 \times \sim 31.3 \times(22.6 \times$ on average), respectively.

Nowadays, high-level synthesis (HLS) has gained prominence for FPGA-based architecture prototyping, enhancing productivity significantly. Despite this advancement, HLS tools are impeded by a critical drawback: they lack support for dynamic memory management (DMM), leading to static mem-ory allocation and suboptimal use of memory resources. In response, numerous efforts have been made to develop DMM solutions compatible with HLS. However, our analysis indicates that existing solutions fail to concurrently meet the desired trifecta of scalability (efficient management of memory of any size), efficiency (minimal latency in memory (de-)allocation), and robustness (low allocation failure rates). This limitation hampers their applicability in real-world scenarios. In this paper, we introduce GraDMM, a “three-birds-one- stone” solution that comprehensively enhances the scalability, efficiency, and robustness of DMM. The key insight is to formulate memory (de-)allocation as graph analytics and lever-age sophisticated FPGA-based graph processing techniques. To achieve scalability, GraDMM specializes a simplified pipeline that significantly suppresses resource utilization expansion caused by managed memory scaling. This is crucial for managing arbitrarily sized memory on resource-limited FPGA platforms. For efficiency, GraDMM implements a data-centric concurrent traversal scheme and a shortcut-assisted fast traversal policy to accelerate (de-)allocation-guided graph traversal, reducing mem-ory (de-)allocation latency. To enhance robustness, GraDMM incorporates an adaptive memory defragmenter that defragments managed memory to minimize fragmentation-induced allocation failures. GraDMM is encapsulated as a library, providing high- level interfaces for users and ensuring synthesizability with Vi- vado HLS. Experimental results demonstrate that GraDMM out-performs three state-of-the-art HLS-compatible DMM solutions by significant margins: 56.71 %-85.59% in resource consumption savings, 78.94 % -99.99 % in (de-)allocation latency improvement, and 10.71 %-65.75% in allocation failure reduction.

Hypergraph Neural Network (HyperGNN) has emerged as a potent methodology for dissecting intricate multilateral connections among various entities. Current software/hardware solutions leverage a sequential execution model that relies on hyperedge and vertex indices for conducting standard matrix operations for HyperGNN inference. Yet, they are impeded by the dual challenges of redundant computation and irregular memory access overheads. This is primarily due to the frequent and repetitive access and updating of a number of feature vectors corresponding to the same hyperedges and vertices. To address these challenges, we propose the first redundancy-aware accelerator, RAHP, which enables high performance execution of HyperGNN inference. Specifically, we present a redundancy-aware asynchronous execution approach into the accelerator design for HyperGNN to reduce redundant computations and off-chip memory accesses. To unveil opportunities for data reuse and unlock the parallelism that existing HyperGNN solutions fail to capture, it prioritizes vertices with the highest degree as roots, prefetching other vertices along the hypergraph structure to capture the common vertices among multiple hyperedges, and synchronizing the computations of hyperedges and vertices in real-time. By such means, this facilitates the concurrent processing of relevant hyperedge and vertex computations of the common vertices along the hypergraph topology, resulting in smaller redundant computations overhead. Furthermore, by efficiently caching intermediate results of the common vertices, it curtails memory traffic and off-chip communications. To fully harness the performance potential of our proposed approach in the accelerator, RAHP incorporates a topology-driven data loading mechanism to minimize off-chip memory accesses on the fly. It is also endowed with an adaptive data synchronization scheme to mitigate the effects of conflicting updates of both hyperedges and vertices. Moreover, RAHP employs the similarity-based data caching strategy to further mitigate the overhead of redundant data transfers. We have implemented and assessed RAHP on a Xilinx Alveo U280 FPGA card. Experimental evaluations demonstrate that RAHP achieves average speedups of 439.2x and 64.7x for HyperGNN inference, alongside average energy savings of 542.8x and 84.2x, compared to the cutting-edge software-based HyperGNN implementations on Intel Xeon CPUs and NVIDIA A100 GPUs, respectively. Additionally, in the realm of HyperGNN inference, RAHP secures average speedups of 7.8x, 5.4x, and 3.8x, and average energy savings of 10.2x, 8.9x, and 6.5x over the foremost GNN accelerators, i.e., FlowGNN, LL-GNN, and ReGNN, respectively.

Abstract Modern recommendation systems integrate graph convolution neural networks (GCN) for enhancing embedding representation. Compared with widely deployed neural network-based models, the extra message propagation layer of GCN-based recommendation is featured with extensive computations and irregular memory access. However, architecture designs for prevailing deep neural network recommendation models assume simple pooling in the embedding layer. ReRAM-based GCN accelerators are specialized for graph-related operations. However, they are designed for general graphs, while GCN-based recommendation models mainly operate on the user-item graph. In this paper, we proposed a resistive random accessed memory (ReRAM) based processing-in-memory (PIM) accelerator, ReGCNR, for GCN-based recommendation. ReGCNR is featured with three key innovations. First, we exploit the 3-dimensional (3-D) stacked heterogeneous ReRAM to fit with the large-size embedding table and user-item graph. Then, we propose a joint degree mapping schema that maximizes the efficiency of the execution pipeline. After that, ReGCNR assembles a well-coordinated pipeline and hardware scheduling design to boost overall system performance. Results show that ReGCNR outperforms GPU by 69.83 $$\times$$ × and 56.67 $$\times$$ × in terms of average speedup and energy saving, respectively. In addition, ReGCNR outperforms state-of-the-art ReRAM-based solutions by 11.13 $$\times$$ × speedups and 7.22 $$\times$$ × energy savings on average.

There are usually a large number of concurrent graph queries (CGQs) requirements in streaming graphs. However, existing graph processing systems mainly optimize a single graph query in streaming graphs or CGQs in static graphs. They have a large number of redundant computations and expensive memory access overhead, and cannot process CGQs in streaming graphs efficiently. To address these issues, we propose PMGraph , a software-hardware collaborative accelerator for efficient processing of CGQs in streaming graphs. First, PMGraph centers on fine-grained data, selects graph queries that meet the requirements through vertex data, and utilizes the similarity between different graph queries to merge the same vertices they need to process to address the problem of a large amount of repeated access to the same data by different graph queries in CGQs, thereby reducing memory access overhead. Furthermore, it adopts the update strategy that regularizes the processing order of vertices in each graph query according to the order of the vertex dependence chain, consequently effectively reducing redundant computations. Second, we propose a CGQs-oriented scheduling strategy to increase the data overlap when different graph queries are processed, thereby further improving the performance. Finally, PMGraph prefetches the vertex information according to the global active vertex set Frontier of all graph queries, hiding the memory access latency. It also provides prefetching for the same vertices that need to be processed by different graph queries, reducing the memory access overhead. Compared with the state-of-the-art concurrent graph query software systems Kickstarter-C and Tripoline, PMGraph achieves average speedups of 5.57× and 4.58×, respectively. Compared with the state-of-the-art hardware accelerators Minnow, HATS, LCCG, and JetStream, PMGraph achieves the speedup of 3.65×, 3.41×, 1.73×, and 1.38× on average, respectively. Experimental results show that our proposed PMGraph outperforms the state-of-the-art concurrent graph processing systems and hardware accelerators.

ReRAM-based Processing-In-Memory (PIM) architectures have been increasingly explored to accelerate various Deep Neural Network (DNN) applications because they can achieve extremely high performance and energy-efficiency for in-situ analog Matrix-Vector Multiplication (MVM) operations. However, since ReRAM crossbar arrays’ peripheral circuits– analog-to-digital converters (ADCs) often feature high latency and low area efficiency, AD conversion has become a performance bottleneck of in-situ analog MVMs. Moreover, since each crossbar array is tightly coupled with very limited ADCs in current ReRAM-based PIM architectures, the scarce ADC resource is often underutilized. In this article, we propose ReHarvest, an ADC-crossbar decoupled architecture to improve the utilization of ADC resource. Particularly, we design a many-to-many mapping structure between crossbars and ADCs to share all ADCs in a tile as a resource pool, and thus one crossbar array can harvest much more ADCs to parallelize the AD conversion for each MVM operation. Moreover, we propose a multi-tile matrix mapping (MTMM) scheme to further improve the ADC utilization across multiple tiles by enhancing data parallelism. To support fine-grained data dispatching for the MTMM, we also design a bus-based interconnection network to multicast input vectors among multiple tiles, and thus eliminate data redundancy and potential network congestion during multicasting. Extensive experimental results show that ReHarvest can improve the ADC utilization by 3.2×, and achieve 3.5× performance speedup while reducing the ReRAM resource consumption by 3.1× on average compared with the state-of-the-art PIM architecture–FORMS.

Data deduplication technologies are widely exploited to reduce capacity demands for storage. Previous chunk-based offline deduplication technologies often cause serious performance overhead due to data chunking and indexing. Particularly, they are not efficient fornon-volatile memory(NVM) based storage systems because they cannot fully exploit the byte-addressability feature of NVMs for fine-grained deduplication. In this paper, we proposeI/O Causality based In-line Deduplication(ICID) to maximize the deduplication ratio for NVM-based storage systems. Unlike previous inline deduplication schemes that use hash indexes to identify duplicate data slices, ICID records memory-copy operations in a B-tree structure to achieve causality-based inline deduplication. We propose two novel techniques to manage memory-copy records in the B-tree efficiently. First, to speed up the B-tree lookup, we group memory-copy records targeted to the same page in a B-tree node to improve data locality. Second, we exploit the spatial locality of memory accesses to identify outdated memory-copy records, and delete them in time to reduce memory consumption of the B-tree. We evaluate ICID in a system equipped with Intel Optane DC Persistent Memory Modules. For a typical KV store–LevelDB, our experimental results show that ICID achieves up to 16higher deduplication ratio and reduces the time cost of data deduplication by 47% on average compared with state-of-the-art deduplication schemes.

The attention-based neural network attracts great interest due to its excellent accuracy enhancement. However, the attention mechanism requires huge computational efforts to process unnecessary calculations, significantly limiting the system’s performance. To reduce the unnecessary calculations, researchers propose sparse attention to convert some dense-dense matrices multiplication (DDMM) operations to sampled dense-dense matrix multiplication (SDDMM) and sparse matrix multiplication (SpMM) operations. However, current sparse attention solutions introduce massive off-chip random memory access since the sparse attention matrix is generally unstructured. We propose CPSAA, a novel crossbar-based processing-in-memory (PIM)-featured sparse attention accelerator to eliminate off-chip data transmissions. First, we present a novel attention calculation mode to balance the crossbar writing and crossbar processing latency. Second, we design a novel PIM-based sparsity pruning architecture to eliminate the pruning phase’s off-chip data transfers. Finally, we present novel crossbar-based SDDMM and SpMM methods to process unstructured sparse attention matrices by coupling two types of crossbar arrays. Experimental results show that CPSAA has an average of 89.6×, 32.2×, 17.8×, 3.39×, and 3.84× performance improvement and 755.6×, 55.3×, 21.3×, 5.7×, and 4.9× energy-saving when compare with GPU, FPGA, SANGER, ReBERT, and ReTransformer.

Graph Convolutional Networks (GCNs) hold great promise in facilitating machine learning on graph-structured data. However, the sparsity of graphs often results in a significant number of irregular memory accesses, leading to inefficient data movement for existing GCNs accelerators. With the advancement of 3D stacked technology, the processing-in-memory (PIM) architecture has emerged as a promising solution for graph processing. Nevertheless, existing PIM accelerators are confronted with the challenges of irregular remote access in the aggregation phase of GCNs and dynamic workload variations between phases. In this paper, we present GCNim, a PIM accelerator based on 3D stacked memory, which features two key innovations in terms of the computation model and hardware designs. First, we present a PIM-based hybrid computation model, which employs a remote merging strategy to achieve the outer product in aggregation and the row-wise product in combination. Second, GCNim builds a three-stage aggregation and combination pipeline and integrates unified processing elements (PEs) supporting these three stages at the bank level, achieving load balance among PEs through a lightweight data placement algorithm. Compared with the state-of-the-art software frameworks running on CPUs and GPUs, GCNim achieves an average speedup of 3,736.06× and 76.56×, respectively. Moreover, GCNim outperforms the state-of-the-art GCN hardware accelerators, I-GCN, PEDAL, FlowGNN, and GCIM, with average speedups of 3.35×, 8.97×, 2.24×, and 5.58×, respectively.

Hypergraph processing has emerged as an effective approach to analyze complex multilateral relationships in real-world scenarios. Existing hypergraph processing solutions based on conventional architectures are severely bottlenecked by off-chip memory accesses. In this paper, we propose the first Processing-In-Memory (PIM)-featured ReRAM-based hypergraph accelerator, dubbed PhGraph, which facilitates performance-and energy-efficient hypergraph processing. On the hardware level, PhGraph integrates analog memristor-based PIM (with high matrix-grained parallelism) and digital memristor-based PIM (for high bipartite-edge-grained efficiency) into one standalone solution. On the software level, an overlap-aware hypergraph partitioning mechanism is proposed to polarize hypergraph workloads into matrix-formatted dense and bipartite-edge-formatted sparse partitions for performance acceleration using analog memristor-based PIM and digital ones, respectively. In addition, PhGraph is equipped with load-balanced partition scheduling and algorithm mapping co-designs to boost hardware utilization and efficiency. Experimental results show that PhGraph outperforms the state-of-the-art CPU-, FPGA-, and ASIC-based solutions by up to 4,309.81×, 547.13×, and 166.76× in terms of performance, and 36,416.11×, 924.12×, and 41.44× in terms of energy-savings, respectively.

The deep neural networks are envisaged for the early disease diagnosis from medical images. However, in the early stage of the disease, the medical images of patients and healthy people have only subtle visual differences. Distinguishing the medical images for early diagnosis belongs to the Fine-Grained Visual Classification (FGVC) task. Many recent works are based on a standard FGVC learning paradigm: locate the discriminative regions first and then classify by fusing the information of these regions. However, it is still not enough for medical images. Because the shape and size of the lesions are variable, and the relationship between lesions and the background is complex. In order to solve these problems, we propose a fine-grained lesion classification framework for early auxiliary diagnosis. We first locate and extract multiple lesions with different sizes and shapes from the original image and then fuse the feature of lesion and background based on attention mechanism. As shown by experiment results in two real-world clinical data sets, our model can locate accurately and perform better.

The introduction of High Bandwidth Memory (HBM) to the FPGA chip makes it possible for an FPGA-based accelerator to leverage the huge memory bandwidth of HBM to improve its performance when implementing a specific algorithm, which is especially true for the Breadth-First Search (BFS) algorithm that demands a high bandwidth for accessing the graph data stored in memory. Different from traditional FPGA-DRAM platforms where memory bandwidth is the precious resource due to the limited DRAM channels, FPGA chips equipped with HBM have much higher memory bandwidths provided by the large quantities of HBM channels, but still a limited amount of logic (LUT, FF, and BRAM/URAM) resources. Therefore, the key to design a high-performance BFS accelerator on an HBM-enhanced FPGA chip is to efficiently use the logic resources to build as many as possible Processing Elements (PEs) and configure them flexibly to obtain as high as possible effective memory bandwidth that is useful to the algorithm from the HBM, rather than partially emphasizing the absolute memory bandwidth. To exploit as high as possible effective bandwidth from the HBM, ScalaBFS2 conducts BFS in graphs in a vertex-centric manner and proposes designs, including the independent module (HBM Reader) for memory accessing, multi-layer crossbar, and PEs that implement hybrid mode (i.e., capable of working in both push and pull modes) algorithm processing, to utilize the FPGA logic resources efficiently. Consequently, ScalaBFS2 is able to build up to 128 PEs on the XCU280 FPGA chip (produced with the 16 nm process and configured with two HBM2 stacks) of a Xilinx Alveo U280 board and achieves performance of 56.92 Giga Traversed Edges Per Second (GTEPS) by fully using its 32 HBM memory channels. Compared with the state-of-the-art graph processing system (i.e., ReGraph) built on top of the same board, ScalaBFS2 achieves 2.52x~4.40x performance speedups. Moreover, when compared with Gunrock running on an Nvidia A100 GPU that is produced with the 7 nm process and configured with five HBM2e stacks, ScalaBFS2 achieves 1.34x~2.40x speedups on absolute performance, and 7.35x~13.18x speedups on power efficiency.

Due to the high complexity of constructing exact k -nearest neighbor graphs, approximate construction has become a popular research topic. The NN-Descent algorithm is one of the representative in-memory algorithms. To effectively handle large datasets, existing state-of-the-art solutions combine the divide-and-conquer approach and the NN-Descent algorithm, where large datasets are divided into multiple partitions, and a subgraph is constructed for each partition before all the subgraphs are merged, reducing the memory pressure significantly. However, such solutions fail to address inefficiencies in large-scale k -nearest neighbor graph construction. In this paper, we propose L-FNNG, a novel solution for accelerating large-scale k -nearest neighbor graph construction on CPU-FPGA heterogeneous platform. The CPU is responsible for dividing data and determining the order of partition processing, while the FPGA executes all construction tasks to utilize the acceleration capability fully. To accelerate the execution of construction tasks, we design an efficient FPGA accelerator, which includes the Block-based Scheduling (BS) and Useless Computation Aborting (UCA) techniques to address the problems of memory access and computation in the NN-Descent algorithm. We also propose an efficient scheduling strategy that includes a KD-tree-based data partitioning method and a hierarchical processing method to address scheduling inefficiency. We evaluate L-FNNG on a Xilinx Alveo U280 board hosted by a 64-core Xeon server. On multiple large-scale datasets, L-FNNG achieves, on average, 2.3× construction speedup over the state-of-the-art GPU-based solution.

Intraoperative hypotension (IOH) events warning plays a crucial role in preventing postoperative complications, such as postoperative delirium and mortality. Despite significant efforts, two fundamental problems limit its wide clinical use. The well-established IOH event warning systems are often built on proprietary medical devices that may not be available in all hospitals. The warnings are also triggered mainly through a predefined IOH event that might not be suitable for all patients. This work proposes a composite multi-attention (CMA) framework to tackle these problems by conducting short-term predictions on user-definable IOH events using vital signals in a low sampling rate with demographic characteristics. Our framework leverages a multi-modal fusion network to make four vital signals and three demographic characteristics as input modalities. For each modality, a multi-attention mechanism is used for feature extraction for better model training. Experiments on two large-scale real-world data sets show that our method can achieve up to 94.1% accuracy on IOH events early warning while the signals sampling rate is reduced by 3000 times. Our proposal CMA can achieve a mean absolute error of 4.50 mm Hg in the most challenging 15-minute mean arterial pressure prediction task and the error reduction by 42.9% compared to existing solutions.

We present MioDB, a novel LSM-tree based key-value (KV) store system designed to fully exploit the advantages of byte-addressable non-volatile memories (NVMs). Our experimental studies reveal that the performance bottleneck of LSM-tree based KV stores using NVMs mainly stems from (1) costly data serialization/deserialization across memory and storage, and (2) unbalanced speed between memory-to-disk data flushing and on-disk data compaction. They may cause unpredictable performance degradation due to write stalls and write amplification. To address these problems, we advocate byte-addressable and persistent skip lists to replace the on-disk data structure of LSM-tree, and design four novel techniques to make the best use of fast NVMs. First, we propose one-piece flushing to minimize the cost of data serialization from DRAM to NVM. Second, we exploit an elastic NVM buffer with multiple levels and zero-copy compaction to eliminate write stalls and reduce write amplification. Third, we propose parallel compaction to orchestrate data flushing and compactions across all levels of LSM-trees. Finally, MioDB increases the depth of LSM-tree and exploits bloom filters to improve the read performance. Our extensive experimental studies demonstrate that MioDB achieves 17.1× and 21.7× lower 99.9th percentile latency, 8.3× and 2.5× higher random write throughput, and up to 5× and 4.9× lower write amplification compared with the state-of-the-art NoveLSM and MatrixKV, respectively.

Crash consistency overhead is a long-standing barrier to the adoption of byte-addressable persistent memory in practice. Despite continuous progress, persistent transactions for crash consistency still incur a 5.6X slowdown, making persistent memory prohibitively costly in practical settings. This paper introduces speculative logging, a new method that forgoes most memory fences and reduces data persistence overhead by logging data values early. This technique enables a novel persistent transaction model, speculatively persistent memory transactions (SpecPMT). Our evaluation shows that SpecPMT reduces the execution time overheads of persistent transactions substantially to just 10%.

Genome graphs analysis has emerged as an effective means to enable mapping DNA fragments (known as reads) to the reference genome. It replaces the traditional linear reference with a graph-based representation to augment the genetic variations and diversity information, significantly improving the quality of genotyping. The in-depth characterization of genome graphs analysis uncovers that it is bottlenecked by the irregular seed index access and the intensive alignment operation, stressing both the memory system and computing resources.Based on these observations, we propose MeG2, a lightweight, commodity DRAM-compliant, processing-in-memory architecture to accelerate genome graphs analysis. MeG2is specifically integrated with the capabilities of both near-memory processing and bitwise in-situ computation. Specifically, MeG2leverages the low access latency of near-memory processing with the index-centric offload mechanism to alleviate the irregular memory access in the seeding procedure, and harnesses the row-parallel capacity of in-situ computation with the distance-aware technique to exploit the intensive computational parallelism in the alignment process. Results show that MeG2outperforms the CPU-, GPU-, and ASIC-based genome graphs analysis solutions by 502× (30.2×), 272× (15.1× ), and 5.5× (8.3×) for short (long) reads, while reducing energy consumption by 1628× (85.6×), 1443× (77.1×), and 7.8× (11.7×), respectively. We also demonstrate that MeG2offers significant improvements over existing PIM-based genome sequence analysis accelerators.

Streaming graph processing needs to timely evaluate continuous queries. Prior systems suffer from massive redundant computations due to the irregular order of processing vertices influenced by updates. To address this issue, we propose ACGraph, a novel streaming graph processing approach for monotonic graph algorithms. It maintains dependence trees during runtime, and makes affected vertices processed in a top-to-bottom order in the hierarchy of the dependence trees, thus normalizing the state propagation order and coalescing of multiple propagation to the same vertices. Experimental results show that ACGraph reduces the number of updates by 50% on average, and achieves the speedup of 1.75~7.43× over state-of-the-art systems.

Temporal graph processing is used to handle the snapshots of the temporal graph, which concerns changes in graph over time. Although several software/hardware solutions have been designed for efficient temporal graph processing, they still suffer from serious irregular data access due to the uncoordinated graph traversal. To overcome these limitations, this paper proposes SaGraph, a domain-specific hardware accelerator to support the efficient processing of temporal graph. Specifically, temporal graph processing shows strong data access similarity, i.e., most graph accesses of the processing of different snapshots are the same and usually refer to a small fraction of vertices. SaGraph can dynamically coordinate the graph traversals and adaptively cache the vertex states to fully exploit the data access similarity for smaller data access overhead. We implemented and evaluated SaGraph on a Xilinx Alveo U280 FPGA card. Compared with the cutting-edge software and hardware solutions, SaGraph achieves 8.5×-157.3×, 4.2×-16.1× speedups and 34.7×-423.6×, 5.3×-14.7× energy savings, respectively.

The k-nearest neighbor graph has emerged as the key data structure for many critical applications. However, it can be notoriously challenging to construct k-nearest neighbor graphs over large graph datasets, especially with a high-dimensional vector feature. Many solutions have been recently proposed to support the construction of k-nearest neighbor graphs. However, these solutions involve substantial memory access and computational overheads and an architecture-level solution is still absent. To address these issues, we architect FNNG, the first FPGA-based accelerator to support k-nearest neighbor graph construction. Specifically, FNNG is equipped with the block-based scheduling technique to exploit the inherent data locality between vertices. It divides the vertices that are close in space into blocks and process the vertices according to the granularity of the blocks during the construction process. FNNG also adopts the useless computation aborting technique to identify superfluous useless computations. It keeps the existing maximum similarity values of all vertices inside the computing unit. In addition, we propose an improved architecture in order to fully utilize both techniques. We implement FNNG on the Xilinx Alveo U280 FPGA card. The results show that FNNG achieves 190x and 2.1x speedups over the state-of-the-art CPU and GPU solutions, running on Intel Xeon Gold 5117 CPU and NVIDIA GeForce RTX 3090 GPU, respectively.

Log creation, maintenance, and its persist ordering are known to be performance bottlenecks for durable transactions on persistent memory. Existing hardware persistent memory transactions overlook an important opportunity for improving performance: some persistent data is algorithmically redundant such that it can be recovered from other data, removing the need for logging such data. The paper presents an ISA extension that enables selective logging for hardware persistent memory transactions for the first time. The ISA extension features two novel components: fine-grain logging and lazy persistency. Fine-grain logging allows hardware to log updates on data in the granularity of words without lengthening the critical path of data accesses. Lazy persistency allows updated data to remain in the cache after the transaction commits. Together, the new hardware persistent memory transaction outperforms the state-of-the-art hardware counterpart by 1.8× on average.

Multi-version graph processing has been widely used to solve many real-world problems. The process of the multi-version graph processing typically includes: (1) a history graph version switching at a specific time and (2) graph processing on this history graph. Existing multi-version graph systems assume ideally that every request for a particular graph version at a particular time will have a corresponding snapshot available. However, in most cases, this is not true. Then existing solutions usually have to settle with an "approximating" version as a substitute, leading to unexpected results for the underlying graph algorithm and thus reducing the practicality of a multi-version graph system for many application scenarios significantly.In this paper, we observe that only a few graph updates have a great impact on the final results. We therefore present AFaVS, a novel multi-version graph system that can improve accuracy effectively in both time- and memory-efficient manners. The cornerstone of AFaVS lies in a novel concept "value" that characterizes the importance of graph updates. AFaVS proposes differential management of updates based on their values and achieves higher accuracy while preserving processing and memory efficiency. AFaVS is also equipped with value-guided version switching and locality-aware optimizations to boost its overall efficiency. Our results on a variety of real-world datasets show that AFaVS outperforms four state-of-the-art multi-version graph systems by 74.35%~95.72% in terms of accuracy improvement and 57.03%~90.44% in terms of memory reduction while introducing less than 2.96% extra computing time. We have deployed AFaVS in a disaster recovery system on the production cluster of Alibaba, achieving 78.8%~90.1% fewer error rates than advanced systems at a comparable efficiency.

Federated learning (FL) enables massive clients to collaboratively train a global model by aggregating their local updates without disclosing raw data. Communication has become one of the main bottlenecks that prolongs the training process, especially under large model variances due to skewed data distributions. Existing efforts mainly focus on either single momentum-based gradient descent, or random client selection for potential variance reduction, yet both often lead to poor model accuracy and system efficiency. In this paper, we propose FedMoS, a communication-efficient FL framework with coupled double momentum-based update and adaptive client selection, to jointly mitigate the intrinsic variance. Specifically, FedMoS maintains customized momentum buffers on both server and client sides, which track global and local update directions to alleviate the model discrepancy. Taking momentum results as input, we design an adaptive selection scheme to provide a proper client representation during FL aggregation. By optimally calibrating clients' selection probabilities, we can effectively reduce the sampling variance, while ensuring unbiased aggregation. Through a rigid analysis, we show that FedMoS can attain the theoretically optimal O(T - 2/3) convergence rate. Extensive experiments using real-world datasets further validate the superiority of FedMoS, with 58%-87% communication reduction for achieving the same target performance compared to state-of-the-art techniques. © 2023 IEEE.

Metapath-based heterogeneous graph models (MHGM) show excellent performance in learning semantic and structural information in heterogeneous graphs. Metapath matching is an essential processing step in MHGM to find all metapath instances, bringing significant overhead compared to the total model execution time. Even worse, in dynamic heterogeneous graphs, metapath instances require to be rematched while graph updated. In this paper, we observe that only a small fraction of metapath instances change and propose GraphMetaP, an efficient incremental metapath maintenance method in order to eliminate the matching overhead in dynamic heterogeneous graphs. GraphMetaP introduces a novel format for metapath instances to capture the dependencies among the metapath instances. The format incrementally maintains metapath instances based on the graph updates to avoide the rematching metapath overhead for the updated graph. Furthermore, GraphMetaP uses the fold way to simplify the format in order to recover all metapath instances faster. Experiments show that GraphMetaP enables efficient maintenance of metapath instances on dynamic heterogeneous graphs and outperforms 172.4X on average compared to the matching metapath method.

Modern storage systems typically replicate data on multiple servers to provide high reliability and availability. However, most commercially-deployed datastores often fail to offer low latency, high throughput, and strong consistency at the same time. This paper presents Whale, a Remote Direct Memory Access (RDMA) based primary-backup replication system for in-memory datastores. Whale achieves both low latency and strong consistency by decoupling metadata multicasting from data replication for all backup nodes, and using an optimistic commitment mechanism to respond to client write requests earlier. Whale achieves high throughput by propagating writes from the primary node to backup nodes asynchronously via RDMA-optimized chain replication. To further reduce the cost of data replication, we design a log-structured datastore to fully exploit the advantages of one-sided RDMA and Persistent Memory (PM). We implement Whale on a cluster equipped with PM and InfiniBand RDMA networks. Experimental results show that Whale achieves much higher throughput and lower latency than state-of-the-art replication protocols.

Heterogeneous graph neural networks (HGNNs) based on metapath exhibit powerful capturing of rich structural and semantic information in the heterogeneous graph. HGNNs are highly memory-bound and thus can be accelerated by near-memory processing. However, they also suffer from significant memory footprint (due to storing metapath instances as intermediate data) and severe redundant computation (when vertex features are aggregated among metapath instances). To address these issues, this paper proposes MetaNMP, the first DIMM-based near-memory processing HGNNs accelerator with reduced memory footprint and high performance. Specifically, we first propose a cartesian-like product paradigm to generate all metapath instances on the fly for heterogeneous graphs. In this way, metapath instances no longer need to be stored as intermediate data, avoiding significant memory consumption. We then design a data flow for aggregating vertex features on metapath instances, which aggregates vertex features along the direction of the metapath instances dispersed from the starting vertex to exploit shareable aggregation computations, eliminating most of the redundant computations. Finally, we integrate specialized hardware units in DIMM to accelerate HGNNs with near-memory processing, and introduce a broadcast mechanism for edge data and vertex features to mitigate the inter-DIMM communication. Our evaluation shows that MetaNMP achieves the memory space reduction of 51.9% on average and the performance improvement by 415.18× compared to NVIDIA Tesla V100 GPU.

The memory-intensive embedding layers of the personalized recommendation systems are the performance bottleneck as they demand large memory bandwidth and exhibit irregular and sparse memory access patterns. Recent studies propose near memory processing (NMP) to accelerate memory-bound embedding operations. However, due to the load imbalance caused by the skewed access frequency of the embedding data, existing NMP solutions that exploit fine-grained memory parallelism fail to translate the increasingly massive internal bandwidth to performance improvements, leading to resource underutilization and hardware overhead.

Computing-in-Memory (CIM) architectures using Non-volatile Memories (NVMs) have emerged as a promising way to address the “memory wall” problem in traditional Von Neumann architectures. CIM accelerators can perform arithmetic or Boolean logic operations in NVMs by fully exploiting their high parallelism for bit-wise operations. These accelerators are often used in cooperation with general-purpose processors to speed up a wide variety of artificial neural network applications. In such a heterogeneous computing architecture, the legacy software should be redesigned and re-engineered to utilize new CIM accelerators. In this article, we propose a compilation tool to automatically migrate legacy programs to such heterogeneous architectures based on the low-level virtual machine (LLVM) compiler infrastructure. To accelerate some computations such as vector-matrix multiplication in CIM accelerators, we identify several typical computing patterns from LLVM intermediate representations , which are oblivious to high-level programming paradigms. Our compilation tool can modify accelerable LLVM IRs to offload them to CIM accelerators automatically, without re-engineering legacy software. Experimental results show that our compilation tool can translate many legacy programs to CIM-supported binary executables effectively, and improve application performance and energy efficiency by up to 51× and 309×, respectively, compared with general-purpose x86 processors.

Dynamic Graph Neural Network (DGNN) has recently attracted a significant amount of research attention from various domains, because most real-world graphs are inherently dynamic. Despite many research efforts, for DGNN, existing hardware/software solutions still suffer significantly from redundant computation and memory access overhead, because they need to irregularly access and recompute all graph data of each graph snapshot. To address these issues, we propose an efficient redundancy-aware accelerator, RACE , which enables energy-efficient execution of DGNN models. Specifically, we propose a redundancy-aware incremental execution approach into the accelerator design for DGNN to instantly achieve the output features of the latest graph snapshot by correctly and incrementally refining the output features of the previous graph snapshot and also enable regular accesses of vertices’ input features. Through traversing the graph on the fly, RACE identifies the vertices that are not affected by graph updates between successive snapshots to reuse these vertices’ states (i.e., their output features) of the previous snapshot for the processing of the latest snapshot. The vertices affected by graph updates are also tracked to incrementally recompute their new states using their neighbors’ input features of the latest snapshot for correctness. In this way, the processing and accessing of many graph data that are not affected by graph updates can be correctly eliminated, enabling smaller redundant computation and memory access overhead. Besides, the input features, which are accessed more frequently, are dynamically identified according to graph topology and are preferentially resident in the on-chip memory for less off-chip communications. Experimental results show that RACE achieves on average 1139× and 84.7× speedups for DGNN inference, with average 2242× and 234.2× energy savings, in comparison with the state-of-the-art software DGNN running on Intel Xeon CPU and NVIDIA A100 GPU, respectively. Moreover, for DGNN inference, RACE obtains on average 13.1×, 11.7×, 10.4×, and 7.9× speedup and 14.8×, 12.9×, 11.5×, and 8.9× energy savings over the state-of-the-art Graph Neural Network accelerators, i.e., AWB-GCN, GCNAX, ReGNN, and I-GCN, respectively.

With the increasing need for graph analysis, massive Concurrent iterative Graph Processing (CGP) jobs are usually performed on the common large-scale real-world graph. Although several solutions have been proposed, these CGP jobs are not coordinated with the consideration of the inherent dependencies in graph data driven by graph topology. As a result, they suffer from redundant and fragmented accesses of the same underlying graph dispersed over distributed platform, because the same graph is typically irregularly traversed by these jobs along different paths at the same time. In this work, we develop GraphTune , which can be integrated into existing distributed graph processing systems, such as D-Galois, Gemini, PowerGraph, and Chaos, to efficiently perform CGP jobs and enhance system throughput. The key component of GraphTune is a dependency-aware synchronous execution engine in conjunction with several optimization strategies based on the constructed cross-iteration dependency graph of chunks. Specifically, GraphTune transparently regularizes the processing behavior of the CGP jobs in a novel synchronous way and assigns the chunks of graph data to be handled by them based on the topological order of the dependency graph so as to maximize the performance. In this way, it can transform the irregular accesses of the chunks into more regular ones so that as many CGP jobs as possible can fully share the data accesses to the common graph. Meanwhile, it also efficiently synchronizes the communications launched by different CGP jobs based on the dependency graph to minimize the communication cost. We integrate it into four cutting-edge distributed graph processing systems and a popular out-of-core graph processing system to demonstrate the efficiency of GraphTune. Experimental results show that GraphTune improves the throughput of CGP jobs by 3.1∼6.2, 3.8∼8.5, 3.5∼10.8, 4.3∼12.4, and 3.8∼6.9 times over D-Galois, Gemini, PowerGraph, Chaos, and GraphChi, respectively.

Graph convolutional networks(GCNs) are promising to enable machine learning on graph data. GCNs show potential vertex-level and intra-vertex parallelism for GPU acceleration, but their irregular memory accesses arising in aggregation operations and the inherent sparsity for vertex features of graphs cause inefficiencies on the GPU. In this paper, we present gPIM, which aims to accelerate GCNs inference through aprocessing-in-memory(PIM) enabled architecture. gPIM is expected to perform compute-intensive combination on the GPU while aggregation and memory-bound combination are offloaded to the PIM-featuredhybrid memory cubes(HMCs). To maximize the efficiency of such GPU-HMC architecture, gPIM is novel with two key designs: 1) A GCN-induced graph partitioning that minimizes communication overheads between cubes, 2) A programmer-transparent performance estimation mechanism that predicts the performance bound of operations accurately for workload offloading. Experimental results show that gPIM significantly outperforms Intel Xeon E5-2680v3 CPU (8,979.52×), NVIDIA Tesla V100 GPU (96.01×), and a state-of-the-art GCN accelerator AWB-GCN (4.18×).

The advent of byte-addressable persistent memory opens an important opportunity for document databases to read and write durable data fetching them into DRAM. Reaping the benefit of persistent memory is not straightforward, as existing document databases are tailored for disk storage. They assume that the disk and DRAM data movement dominates the performance. However, this paper points out that data indexing becomes the performance bottleneck when porting document databases to persistent memory. The paper proposes PMLiteDB, the first persistent memory document database with streamlined access paths. PMLiteDB introduces two techniques,direct readingandselective caching.Direct readingstreamlines the translation from document IDs to the address of documents whenever possible by swizzling the IDs intopersistent memory references. It guarantees to use only up-to-datepersistent memory referenceswhen document movements invalidate associated references.Selective cachingreduces data movements between DRAM and persistent memory by selectively caching only frequently accessed persistent memory data pages with a DRAM buffer. For other pages, the database loads data on them directly without caching. Compared to the design that adopts persistent memory as a fast disk without exploiting the byte-addressability, PMLiteDB achieves 2.33× on average and up to 6.18× speedup.

The hardware description of circuits usually contains many loops. Register transfer level (RTL) simulation is a critical step to verify the correctness of circuits and is time consuming. Thus, it is necessary to speed up its process. However, the speedup of existing RTL simulation acceleration techniques is usually small. Although the speedup of hardware acceleration is large, the hardware cost is high. Some methods utilize performance models without performing RTL simulation to obtain rough simulation performance and have a large speedup. However, they do not support functional verification. In order to address the problems, we propose a loop-oriented RTL simulation acceleration approach based on code instrumentation for designs synthesized by high-level synthesis. Our approach reduces the RTL simulation time by skipping a large number of repeated loop iterations, and maintains high accuracy for the prediction of the number of cycles by reserving some loop iterations. We establish a performance prediction model and an interval value formula for skipping loop iterations. We conduct experiments on the MachSuite benchmark. The results show that for the RTL simulation of single data processing and batch data processing, the average speedup of our approach can reach$7.49\times $and$43.3\times $, respectively, and the average prediction errors of the number of cycles are 1.71% and 1.06%, respectively. It also reveals that the interval value obtained by our approach for skipping loop iterations can quickly and effectively balance between the accuracy of prediction of the number of cycles and speedup. Compared to the state-of-the-art approach ESSENT, the speedup of our approach is better and the accuracy of prediction of the number of cycles remains at the same level as that of performance models.

In many applications of the analysis of dynamic graph, manyTiming iterative Graph Processing(TGP) jobs usually need to be generated for the processing of the corresponding snapshots of the dynamic graph to obtain the results at different points of time. For high throughput of such applications, it is expected to run the TGP jobs on the GPU concurrently. Although many GPU-based systems have been recently developed, for out-of-GPU-memory dynamic graph processing, this concurrent way suffers from significant data access overhead due to a large volume of data transfer between CPU and GPU and the interference between these concurrently running jobs, which eventually incurs low GPU utilization ratio. In this work, we observed that the TGP jobs have strong temporal and spatial similarity when they access different snapshots for their own processing as most parts of the snapshots are the same and only a few parts are changing with time. It creates ideal opportunities for efficient concurrent execution of the TGP jobs by dramatically reducing CPU-GPU graph data transfer cost. Based on this observation, we develop the first GPU-based dynamic graph processing systemEGraph, which can be integrated into the existing out-of-GPU-memory static graph processing systems to enable them to efficiently support concurrent execution of TGP jobs on dynamic graphs with the help of GPU accelerators. Different from the existing approaches, we propose in EGraph an effectiveLoading-Processing-Switching(LPS) execution model. It is able to effectively reduce the overhead of CPU-GPU data transfer and ensures a higher GPU utilization ratio for efficient execution of the TGP jobs by fully utilizing the data access similarity between the TGP jobs. Experimental results show that the existing GPU-accelerated systems achieve performance improvements of 2.3-3.5 times after being integrated with EGraph.

In data deduplication systems, chunking has a significant impact on the deduplication ratio and throughput. ExistingContent-Defined Chunking(CDC) approaches exploit a sliding window to calculate rolling hashes of the input data stream byte-by-byte, and then determine chunk cut-points if the rolling hash satisfies a given cut-condition. Since previous CDC approaches are extremely costly, it often significantly degrades the throughput of data deduplication systems. In this paper, we argue that calculating and checking the rolling hashes byte-by-byte is unnecessary. To reduce the CPU overhead of CDC, we propose ajump-based chunking(JC) approach. The key idea is to introduce a jump-condition, and the sliding window can jump over a specific length of the input data stream if the rolling hashes satisfy the jump-condition. Moreover, we also explore the impact of the cut-condition and the jump-condition on the chunk size. Our theoretic studies demonstrate the effectiveness and efficiency of JC, without compromising the deduplication ratio. Experimental results show that JC improves the throughput of chunking by about 2× on average compared with the state-of-the-art CDC approaches while still guaranteeing high deduplication ratio.

Non-volatile Memories (NVMs) usually demonstrate vast endurance variation due to Process Variation (PV). They are vulnerable to an Inconsistent Write Attack (IWA) which reverses the write intensity distribution in two adjacent wear leveling windows. In this paper, we propose CLIMBER, a defense mechanism to neutralize IWA for NVMs. CLIMBER dynamically changes harmful address mappings so that intensive writes to weak cells are still redirected to strong cells. CLIMBER also conceals weak NVM cells from attackers by randomly mapping cold addresses to weak NVM regions. Experimental results show that CLIMBER can reduce maximum page wear rate by 43.2% compared with the state-of-the-art Toss-up Wear Leveling and prolong NVM lifetime from 4.19 years to 7.37 years with trivial performance/hardware overhead.

Approximate string matching (ASM) functions as the basic operation kernel for a large number of string processing applications. Existing Von-Neumann-based ASM accelerators suffer from huge intermediate data with the ever-increasing string data, leading to massive off-chip data transmissions. This paper presents a novel ASM processing-in-memory (PIM) accelerator, namely ReSMA, based on ReCAM- and ReRAM-arrays to eliminate the off-chip data transmissions in ASM. We develop a novel ReCAM-friendly filter-and-filtering algorithm to process the q-grams filtering in ReCAM memory. We also design a new data mapping strategy and a new verification algorithm, which enables computing the edit distances totally in ReRAM crossbars for energy saving. Experimental results show that ReSMA outperforms the CPU-, GPU-, FPGA-, ASIC-, and PIM-based solutions by 268.7×, 38.6×, 20.9×, 707.8×, and 14.7× in terms of performance, and 153.8×, 42.2×, 31.6×, 18.3×, and 5.3× in terms of energy-saving, respectively.

Graph Neural Networks (GNNs) have both graph processing and neural network computational features. Traditional graph accelerators and NN accelerators cannot meet these dual characteristics of GNN applications simultaneously. In this work, we propose a ReRAM-based processing-in-memory (PIM) architecture called ReGNN for GNN acceleration. ReGNN is composed of analog PIM (APIM) modules for accelerating matrix vector multiplication (MVM) operations, and digital PIM (DPIM) modules for accelerating non-MVM aggregation operations. To improve data parallelism, ReGNN maps data to aggregation sub-engines based on the degree of vertices and the dimension of feature vectors. Experimental results show that ReGNN speeds up GNN inference by 228x and 8.4x, and reduces energy consumption by 305.2x and 10.5x, compared with GPU and the ReRAM-based GNN accelerator ReGraphX, respectively.

Graph convolutional networks (GCNs) are promising to enable machine learning on graphs. GCNs exhibit mixed computational kernels, involving regular neural-network-like computing and irregular graph-analytics-like processing. Existing GCN accelerators obey a divide-and-conquer philosophy to architect two separate types of hardware to accelerate these two types of GCN kernels, respectively. This hybrid architecture improves intra-kernel efficiency but considers little inter-kernel interactions in a holistic view for improving overall efficiency.In this paper, we present a new GCN accelerator, RE-FLIP, with three key innovations in terms of architecture design, algorithm mappings, and practical implementations. First, ReFlip leverages PIM-featured crossbar architectures to build a unified architecture for supporting the two types of GCN kernels simultaneously. Second, ReFlip adopts novel algorithm mappings that can maximize potential performance gains reaped from the unified architecture by exploiting the massive crossbar-structured parallelism. Third, ReFlip assembles software/hardware co-optimizations to process real-world graphs efficiently. Compared to the state-of-the-art software frameworks running on Intel Xeon E5-2680v4 CPU and NVIDIA Tesla V100 GPU, ReFlip achieves the average speedups of 6,432× and 86.32× and the average energy savings of 9,817× and 302.44×, respectively. In addition, ReFlip also outperforms a state-of-the-art GCN hardware accelerator, AWB-GCN, by achieving an average speedup of 5.06× and an average energy saving of 15.63×.

Beyond ordinary graphs, hypergraphs are a graph representation to flexibly express complex multilateral relationships between entities. Hypergraph processing can be used to solve many real-world problems, e.g., machine learning, VLSI design, and image retrieval. Existing hypergraph processing systems handle a hypergraph in order of its hyperedge and vertex indices. This makes processing hypergraphs on generalpurpose architectures suffer significantly from excessive offchip memory accesses, most of which however are redundant in frequently accessing overlapped hyperedges and vertices, but the index-ordered scheduling destroys this potential locality.In this paper, we propose a novel Generate-Load-Apply (GLA) execution model to improve locality in hypergraph processing. The key insight of GLA is to use a concept of chain to characterize the overlapped feature of a hypergraph, exposing data reuse opportunities missed in existing hypergraph systems. The precondition of driving GLA model is to generate expected chains on the fly, but the software solution is so expensive that its overheads may outweigh the benefits achieved from the chain-driven scheduling. We further present ChGraph, the first hardware-accelerated hypergraph processing engine near each core. ChGraph is specialized in accelerating the chain generation and the chain-guided data loading (to hide memory access latency) while the general-purpose cores are responsible only for handling the apply operations of GLA. We evaluate ChGraph against a state-of-the-art hypergraph processing system Hygra on six hypergraph algorithms using five large real-world hypergraphs. Results on a simulated 16core system show that ChGraph reduces the number of offchip memory accesses by up to 4.56× and achieves up to 4.73× speedup while introducing only 0.26% area overhead.

Graph processing is promising to extract valuable insights in graphs. Nowadays, emerging 3D-stacked memories and silicon technologies can provide over terabytes per second memory bandwidth and thousands of processing elements (PEs) to meet the high hardware demand of graph applications. However, this leap in hardware capability does not result in a huge increase but even a degradation sometimes in performance for graph processing. In this paper, we discover that the centralized on-chip memory hierarchy adopted in existing graph accelerators is the villain causing poor scalability due to its quadratic increase of hardware overheads with respect to the number of PEs.We present a novel distributed on-chip memory hierarchy by leveraging the network-on-chip (NoC) to enable massively parallel graph processing. We architect ScalaGraph, a brand new graph processing accelerator, to exploit this insight. ScalaGraph adopts a software-hardware co-design to minimize NoC communication overheads via an efficient row-oriented dataflow mapping and runtime aggregation. A specialized scheduling mechanism is also proposed to improve load imbalance. Our results on a Xilinx Alveo U280 FPGA card show that ScalaGraph on a modest configuration of 512 PEs achieves 2.2× and 3.2× speedups over a state-of-theart graph accelerator GraphDyns and a GPU-based graph system Gunrock, respectively. Moreover, ScalaGraph enables supporting at least 1,024 PEs with nearly linear performance scaling while GraphDyns fails to work.

Low-latency I/O services are essential for latency-sensitive workloads when they co-run with throughput-oriented workloads in cloud data centers. Although advanced SSDs such as Intel Optane SSDs can offer ultra-low latency at the device layer, I/O interference among various workloads through the I/O stack can still significantly enlarge I/O latency. It is still an open problem to best utilize ultra-low latency SSDs in cloud computing environments.

Processing-in-memory (PIM) is promising to solve the well-known data movement challenge by performing in-situ computations near the data. Leveraging PIM features is pretty profitable to boost the energy efficiency of applications. Early studies mainly focus on improving the programmability for computation offloading on PIM architectures. They lack a comprehensive analysis of computation locality and hence fail to accelerate a wide variety of applications. In this paper, we present a general-purpose instruction-level offloading technique for near-DRAM PIM architectures, namely IOTPIM, to exploit PIM features comprehensively. IOTPIM is novel with two technical advances: 1) a new instruction offloading policy that fully considers the locality of the whole on-chip cache hierarchy, and 2) an offloading performance benefit prediction model that directly predicts offloading performance benefits of an instruction based on the input dataset characterizes, preserving low analysis overheads. The evaluation demonstrates that IOTPIM can be applied to accelerate a wide variety of applications, including graph processing, machine learning, and image processing. IOT-PIM outperforms the state-of-the-art PIM offloading techniques by 1.28×-1.51× while ensuring offloading accuracy as high as 91.89% on average.

Graph random walk is widely used in the graph processing as it is a fundamental component in graph analysis, ranging from vertices ranking to the graph embedding. Different from traditional graph processing workload, random walk features massive processing parallelisms and poor graph data reuse, being limited by low I/O efficiency. Prior designs for random walk mitigate slow I/O operations. However, the state-of-the-art random walk processing systems are bounded by slow disk I/O bandwidth, which is confirmed by our experiments with real-world graphs. To address this issue, we propose FlashWalker, an in-storage accelerator for random walk that moves walk updating close to graph data stored in flash memory, by exploiting significant parallelisms inside SSD. Featuring a heterogeneous and parallel processing system, FlashWalker includes a board-level accelerator, channel-level accelerators, and chip-level accelerators. To address challenges posed by the tight resource constraints for processing large-scale graphs, we propose novel designs: storing a few popular subgraphs in accelerators, the pre-walking for dense walks, two optimizations to search the subgraph mapping table, and a subgraph scheduling algorithm. We implement FlashWalker in RTL, showing small circuit area overhead. Our evaluation shows FlashWalker reduces the execution time of random walk algorithms by up to 660.50×, compared with GraphWalker, which is the state-of-the-art system for random walk algorithms.

Many solutions have been recently proposed to support the processing of streaming graphs. However, for the processing of each graph snapshot of a streaming graph, the new states of the vertices affected by the graph updates are propagated irregularly along the graph topology. Despite the years' research efforts, existing approaches still suffer from the serious problems of redundant computation overhead and irregular memory access, which severely underutilizes a many-core processor. To address these issues, this paper proposes a topology-driven programmable accelerator TDGraph, which is the first accelerator to augment the many-core processors to achieve high performance processing of streaming graphs. Specifically, we propose an efficient topology-driven incremental execution approach into the accelerator design for more regular state propagation and better data locality. TDGraph takes the vertices affected by graph updates as the roots to prefetch other vertices along the graph topology and synchronizes the incremental computations of them on the fly. In this way, most state propagations originated from multiple vertices affected by different graph updates can be conducted together along the graph topology, which help reduce the redundant computations and data access cost. Besides, through the efficient coalescing of the accesses to vertex states, TDGraph further improves the utilization of the cache and memory bandwidth. We have evaluated TDGraph on a simulated 64-core processor. The results show that, the state-of-the-art software system achieves the speedup of 7.1~21.4 times after integrating with TDGraph, while incurring only 0.73% area cost. Compared with four cutting-edge accelerators, i.e., HATS, Minnow, PHI, and DepGraph, TDGraph gains the speedups of 4.6~12.7, 3.2~8.6, 3.8~9.7, and 2.3~6.1 times, respectively.

Heterogeneous memory systems have become increasingly popular in recent years. Because heterogeneous storage media often show significantly different characteristics in terms of bandwidth, latency, capacity, and energy consumption, it is still challenging to best utilize them for cost-efficient and energy-efficient heterogeneous memory systems. In this paper, we propose a simulation framework for multi-tiered heterogeneous memory architectures based on GEM5 and DRAMsim3 simulators. We design a heterogeneous memory controller to architect Non-Volatile Memory (NVM) as main memory, and architect both Dynamic Random Access Memory (DRAM) and High-Bandwidth Memory (HBM) as a hybrid cache of NVM. Specifically, HBM, DRAM, and NVM are managed in a single (flat) address space. However, we use an address remapping table to maintain the mappings between NVM pages and HBM/DRAM pages, and logically manage HBM/DRAM/NVM as a three-tiered hybrid memory system. We also design a hardware-supported hot page monitor based on Majority Element Algorithm (MEA) to identify the hottest pages in the DRAM, and a dynamic threshold adjustment scheme for hot page migration to balance the memory bandwidth between DRAM and HBM. Our multi-tiered heterogeneous memory architecture can take advantage of the large capacity of NVM, the low latency of DRAM, and the high bandwidth of HBM concurrently. Experimental results show that our tiered memory architecture can improve application performance by an average of$2.5\times$compared with an NVM-only architecture, and up to 57.4% compared with a DRAM-only architecture. Moreover, the performance gap between our HBM/DRAM/NVM architecture and a HBM-only architecture is less than 10%.

Hypergraph processing has emerged as a powerful approach for analyzing complex multilateral relationships among multiple entities. Past research on building hypergraph systems suggests that changing the scheduling order of bipartite edge tasks can improve the overlap-induced data locality in hypergraph processing. However, due to the complex intertwined connections between vertices and hyperedges, it is almost impossible to find a locality-optimal scheduling order. Thus, these task-centric hypergraph systems often suffer from substantial off-chip communications. In this paper, we first propose a novel data-centric Load-Trigger-Reduce (LTR) execution model to exploit fully the locality in hypergraph processing. Unlike a task-centric model that loads the required data along with a task, our LTR model invokes tasks as per the data used. Specifically, once the hypergraph data is loaded into the on-chip memory, all of its relevant computation tasks will be triggered simultaneously to output intermediate results, which are finally reduced to update the final results. Our LTR model enables all hypergraph data to be accessed once in each iteration. To fully exploit the LTR performance potential, we further architect an LTR-driven hypergraph accelerator, XuLin, which features with an adaptive data loading mechanism to minimize the loading cost via chunk merging at runtime. XuLin is also equipped with a priority-based differential data reduction scheme to reduce the impact of conflicting updates on performance. We have implemented XuLin both on a Xilinx Alveo U250 FPGA card and using a cycle-accurate simulator. The results show that XuLin outperforms the state-of-the-art hypergraph processing solutions Hygra and ChGraph by $20.47 \times$ and $8.77 \times$ on average, respectively.

Existing streaming graph processing systems typically adopt two phases of refinement and recomputation to ensure the correctness of the incremental computation. However, severe redundant memory accesses exist due to the unnecessary synchronization among independent edge updates. In this paper, we present GraphFly, a high-performance asynchronous streaming graph processing system based on dependency-flows. GraphFly features three key designs: 1) Dependency trees (D-trees), which helps quickly identify independent graph updates with low cost; 2) Dependency-flow based processing model, which exploits the space-time dependent co-scheduling for cache efficiency; 3) Specialized graph data layout, which further reduces memory accesses. We evaluate GraphFly, and the results show that GraphFly significantly outperforms state-of-the-art systems KickStarter and GraphBolt by 5.81× and 1.78× on average, respectively. Also, GraphFly scales well with different sizes of update batch and compute resources.

This article points out an important threat that application-level Garbage Collection (GC) creates to the use of non-volatile memory (NVM). Data movements incurred by GC may invalidate the pointers to objects on NVM and, hence, harm the reusability of persistent data across executions. The article proposes the concept of movement-oblivious addressing (MOA), and develops and compares three novel solutions to materialize the concept for solving the addressability problem. It evaluates the designs on five benchmarks and a real-world application. The results demonstrate the promise of the proposed solutions, especially hardware-supported Multi-Level GPointer, in addressing the problem in a space- and time-efficient manner.

Checkpoint/recovery has been widely used in many high available and reliable systems. This paper proposesShadow, an application-transparent and in-memory checkpointing mechanism based on hybrid memory system composed of DRAM and emerging Non-volatile Memory (NVM).Shadowadopts a pre-copy based checkpointing mechanism to reduce the system downtime. It supports fine-grained and incremental checkpointing at frequencies up to 100 times per second. Under this context, the checkpointing can significantly degrade application performance due to memory contention between applications and the checkpointing process. Previous checkpointing mechanisms on hybrid memory systems have focused on the performance of checkpointing, and have overlooked the impact of memory contention on the application performance. In this paper, we mitigate the memory contention at the bank level by carefully scheduling memory requests to fully leverage the idle time slots of different memory banks. Moreover, if bank conflicts are unavoidable,Shadowpromotes the priority of applications’ memory requests to lessen their access latencies. By redesigning the memory controllers of DRAM and NVM, we implement a hardware-assisted checkpointing mechanism that can directly transfer data from working memory to the checkpoint in NVM, without any intervention of CPUs. Our evaluation shows that Shadow can reduce memory bank conflicts between applications and checkpointing by 75 percent, and decrease applications’ memory read request latency by 28 percent on average compared to the pre-copy based checkpointing. Moreover, Shadow can also reduce checkpointing overhead by 42 and 16 percent on average compared to the stop-and-copy and pre-copy based checkpointing approaches, respectively.

Many iterative graph processing systems have recently been developed to analyze graphs. Although they are effective from different aspects, there is an important issue that has not been addressed yet. A real-world graph follows the power-law property, in which a small number of vertices have high degrees (i.e., are connected to most other vertices in the graph). These vertices are calledhot-verticesand usually require more iterations to converge. In the existing solutions, these hot-vertices may be allocated to many or even all graph partitions along with other vertices that are easy to converge. As the result, the partitions with hot-vertices have to be loaded repeatedly (and consequently the system suffers from high data access cost), although perhaps only a few vertices in these partitions are active. To cope with this issue, we develop an efficient open source graph partition manager, called GGraph, which can be integrated into the existing graph processing systems to efficiently support iterative graph processing, by taking into account the power-law property of the graph structure. It uses a novel graph repartitioning scheme with low overhead to dynamically partition the hot-vertices together, so as to avoid loading the inactive vertices in the same partition as the repeatedly processed hot-vertices. By such means, it not only enables less data access cost, but also enables the privileged processing of the hot-vertices. In order to further increase the convergence speed, a scheduling algorithm is further proposed in this work to prioritize the processing of the hot-vertices with low overhead. To demonstrate the efficiency of GGraph, we plug it into four state-of-the-art graph processing systems, i.e., Gemini, GraphChi, Chaos, and GridGraph, and experimental results show that GGraph improves their performance by up to 3.2 times, 3.8 times, 3.9 times, 3.5 times, respectively.

Multi-FPGA architectures have gained great interests in accelerating large-scale graph processing with great potential on high throughput and energy efficiency. As a beneficial complement, work stealing functions effectively to balance the computational workload on different FPGAs dynamically. Unfortunately, existing graph partitioning schemes originally designed in distributed settings potentially mismatch the work stealing-enabled multi-FPGA situations, where the computation is balanced while the communication overhead is unprecedentedly significant. In this paper, we present a 2-dimension balanced graph partitioning for work stealing assisted graph systems on multi-FPGAs, which can reduce communication overhead while preserving the optimal performance of work stealing. Our approach is novel by 1) exploring the tradeoff between load balance dimension and communication dimension in work-stealing-enabled graph processing system for the optimal performance, and 2) optimizing the memory access sequences to improve the granularity of graph partitioning for high-throughput graph analytics. Our experimental results show that our approach achieves 1.63x$\sim$2.56x speedups compared with state-of-the-art FPGA-based graph processing systems.

With the huge demand for graph analytics in many real-world applications, massive iterative graph processing jobs are concurrently performed on the same graphs and suffer from significant high data access cost. To lower the data access cost toward high performance, several out-of-core concurrent graph processing solutions are recently designed to handle concurrent jobs by enabling these jobs to share the accesses of the same graph data. However, the set of active vertices in each partition are usually different for various concurrent jobs and also evolve with time, where some high-degree ones (or calledhub-vertices) of these active vertices require more iterations to converge due to the power-law property of real-world graphs. In consequence, existing solutions still suffer from much unnecessary I/O traffic, because they have to entirely load each partition into the memory for concurrent jobs even if most vertices in this partition are inactive and may be shared by a few jobs. In this paper, we propose an efficient structure-aware storage system, called GraphSO, for higher throughput of the execution of concurrent graph processing jobs. It can be integrated into existing out-of-core graph processing systems to promote the execution efficiency of concurrent jobs with lower I/O overhead. The key design of GraphSO is a fine-grained storage management scheme. Specifically, it logically divides the partitions of existing graph processing systems into a series of small same-sized chunks. At runtime, these small chunks with active vertices are judiciously loaded by GraphSO to construct new logical partitions (i.e., each logical partition is a subset of active chunks) for existing graph processing systems to handle, where the most-frequently-used chunks are preferentially loaded to construct the logical partitions and the other ones are delayed to wait to be required by more jobs. In this way, it can effectively spare the cost of loading the graph data associated with the inactive vertices with low repartitioning overhead and can also enable the loaded graph data to be fully shared by concurrent jobs. Moreover, GraphSO also designs a buffering strategy to efficiently cache the most-frequently-used chunks in the main memory to further minimize the I/O traffic by avoiding repeated load of them. Experimental results show that GraphSO improves the throughput of GridGraph, GraphChi, X-Stream, DynamicShards, LUMOS, Graphene, and Wonderland by 1.4-3.5 times, 2.1-4.3 times, 1.9-4.1 times, 1.9-2.9 times, 1.5-3.1 times, 1.3-1.5 times, and 1.3-2.7 times after integrating with them, respectively.

Dynamic graph convolutional networks (DGCNs) have emerged as an effective approach to analyzing graph data that is constantly changing. The typical DGCNs incorporate not only graph convolutional networks (GCNs) to extract the structural information but also with recurrent neural networks (RNNs) to capture the temporal information from evolving graph data. These two alternative execution kernels of DGCNs impose unique architecture challenges for both types of kernels to be implemented efficiently. The presence of complex execution patterns of DGCNs renders existing architectures unsuitable. In this article, we present the first DGCN accelerator with an integrated architecture, named ReaDy, to accelerate DGCNs based on emerging PIM-featured ReRAM architectures. ReaDy is novel with an integrated architecture that enables running the GCN and RNN kernels of DGCNs simultaneously. Specifically, ReaDy is equipped with a redundancy-free scheduling mechanism to alleviate intrinsic dynamic irregularity for the GCN kernel, improving hardware utilization. In addition, ReaDy also includes a locality-aware dataflow strategy to exploit the inherent intervertex data locality for the RNN kernel, reducing superfluous data accesses to vertices and weight parameters. In a holistic view, ReaDy further enhances the entire system via an interkernel pipeline to reduce the off-chip accesses of intermediate results, boosting the overall efficiency of DGCNs significantly. Compared to the state-of-the-art software framework, PyGT, running on Intel Xeon E5-2680v4 CPU and NVIDIA Ampere A100 GPU, ReaDy achieves the average speedups of$955\times $and$27.33\times $, and the average energy savings of 1$093\times $and$80.21\times $, respectively. In addition, ReaDy outperforms ReFlip-ERA, which is obtained by combining a state-of-the-art GCN accelerator ReFlip and RNN accelerator ERA-LSTM, by an average speedup of$8.30\times $and an average energy saving of$7.29\times $.

Memristor-based accelerator (MBA) has demonstrated its capability in accelerating matrix-vector multiplication (MVM) with high performance and energy efficiency. However, it is hard to determine whether and how well an application can benefit from MBAs in a heterogeneous computing architecture. In this article, we propose a simulation framework called MHSim to evaluate the energy efficiency and performance of applications running with both MBAs and CPUs. MHSim provides flexible system-level interfaces and circuit-level simulation models for designers to configure heterogeneous computing architectures. We design a general-purpose MBA which enables floating-point computation models for general matrix-matrix multiplication (GEMM). Our simulation framework can quantify the performance and energy efficiency of different MBA architectures for various applications. We validate our simulation framework with SPICE and evaluate the accuracy and performance of MBAs via several case studies. Experimental results demonstrate that the deviations of energy consumption and latency are only 0.47% and 0.49% on average compared with SPICE-based simulation.

Pruning deep neural networks (DNNs) can reduce the model size and thus save hardware resources of a resistive-random-access-memory (ReRAM)-based DNN accelerator. For the tightly coupled crossbar structure, existing ReRAM-based pruning techniques prune the weights of a DNN in a structured manner, thereby attaining low pruning ratios. This article presents a novel pruning technique, SegPrune, for pruning the weights of a DNN flexibly on crossbar architectures in order to maximize the pruning ratio achieved while preserving crossbar efficiency. We observe that different filters of a weight matrix share a large number of matrix subcolumns (in the same rows), called segments, that can be pruned by using the same segment shape in the sense that the weights at the same column position of these segments are either simultaneously accuracy-sensitive (and should thus be reserved) or simultaneously accuracy-insensitive (and can thus be pruned). Due to the bit-line exchangeability in the crossbar, segments with the same pruning shape can be assembled together into the same crossbar to ensure crossbar execution efficiency. We propose a projection-based shape voting algorithm to select suitable segment shapes to drive the weight pruning process. Accordingly, we also introduce a low-overhead data path that can be easily integrated into any existing ReRAM-based DNN accelerator, achieving a high pruning ratio and a high execution efficiency. Our evaluation shows that SegPrune outperforms the state-of-the-art, Hybrid-P, and FORMAS, by up to$14.6\times $and$3.6\times $in pruning ratio,$13.9\times $and$3.4\times $in inference speedup, and$12.5\times $and$3.1\times $in energy reduction, respectively, while achieving an even higher accuracy at the cost of less than 0.27% extra hardware area overhead.

Processing-In-Memory (PIM) has emerged as a high-performance and energy-efficient computing paradigm for accelerating convolutional neural network (CNN) applications. Resistive random access memory (ReRAM) has been widely used in PIM architectures due to its extremely high efficiency for accelerating matrix-vector multiplications through analog computing. However, because CNN training usually requires high-precision computation in the backward propagation (BP) stage, the limited precision of analog PIM accelerators impedes their adoption in CNN training. In this paper, we propose ReHy, a hybrid PIM accelerator to support CNN training in ReRAM arrays. It is composed of Analog PIM (APIM) and Digital PIM (DPIM) modules. ReHy uses APIM to accelerate the feed-forward propagation (FP) stage for high performance, and DPIM to process the BP stage for high accuracy. We exploit the capability of ReRAM for Boolean logic operations to design the DPIM architecture. Particularly, we design floating-point multiplication and addition operators to support matrix multiplications in ReRAM arrays. We also propose a performance model to offload high-precision matrix multiplications to DPIM according to the data parallelism. Experimental results show that ReHy can speed up CNN training by 18.8 and 2.3, and reduce energy consumption by 21.2 and 3.2, compared with CPUs and state-of-the-art FloatPIM, respectively.

The emergingGraph Convolutional Network(GCN) has been widely used in many domains, where it is important to improve the efficiencies of applications by accelerating GCN trainings. Due to the sparsity nature and exploding scales of input real-world graphs, state-of-the-art GCN training systems (e.g., GNNAdvisor) employ graph processing techniques to accelerate the message exchanging (i.e., aggregations) among the graph vertices. Nevertheless, these systems treat both the aggregation stages of forward and backward propagation phases as all-active graph processing procedures that indiscriminately conduct computations on all vertices of an input graph. In this article, we first point out that in a GCN training problem with a given training set on an input graph, its aggregation stages of backward propagation phases (called asbackward aggregationsin this article) can be equivalently converted to partially-active graph processing procedures, which conduct computations on only partial vertices of the input graph. By leveraging such a finding, we propose an execution path preparing method that collects and coalesces the graph data used during different training layers of backward aggregations, and constructs their corresponding sub-graphs (called asexecution pathsin this article) as inputs to conduct the backward training on GPUs. Further, we propose a structural-aware strategy for the execution paths to compute their optimal group sizes, so as to gain as high as possible performances on GPUs during the backward aggregations. The experiment results by conducting GCN training in typical real-world graphs show that compared with GNNAdvisor, our approach improves the performance of backward aggregations by up to 5.68x on NVIDIA P100 GPU, and up to 6.57x on NVIDIA V100S GPU

Graph mining aims to explore interesting structural information of a graph. Pattern-centric systems typically transform a generic-purpose graph mining problem into a series of subgraph matching problems for high performance. Existing pattern-centric mining systems reduce the substantial search space towards a single pattern by exploring a highly-optimized matching order, but inherent computational redundancies of such a matching order itself still suffer severely, leading to significant performance degradation. The key innovation of this work lies in a general redundancy criterion that characterizes computational redundancies arising in not only handing a single pattern but also matching multiple patterns simultaneously. In this paper, we present SumPA, a high-performance pattern-centric graph mining system that can sufficiently remove redundant computations for any complex graph mining problems. SumPA features three key designs: (1) a pattern abstraction technique that can simplify numerous complex patterns into a few simple abstract patterns based on pattern similarity, (2) abstraction-guided pattern matching that completely eliminates (totally and partially) redundant computations during subgraph enumeration, and (3) a suite of system optimizations to maximize storage and computation efficiency. Our evaluation on a wide variety of real-world graphs shows that SumPA outperforms the two state-of-the-art systems Peregrine and GraphPi by up to 61.89× and 8.94×, respectively. For many mining problems on large graphs, Peregrine takes hours or even days while SumPA finishes in only a few minutes.

Hybrid memory systems composed of DRAM and Non-Volatile Memory (NVM) can offer very large memory capacity for data-intensive applications such as graph processing. The performance of parallel graph processing is often affected by straggler tasks due to asymmetrical graph partitioning and sub-graph processing. In hybrid memory systems, the significant difference of performance between DRAM and NVM may exacerbate the load imbalance of parallel graph processing. Traditional load balancing schemes that only aim to balance computing loads among multiple processors are no longer effective in hybrid memory systems.In this paper, we first explore how hybrid memory systems affect the efficiency of existing graph processing systems. We make two observations: 1) Traditional work-stealing schemes may be not efficient enough in hybrid memory systems. Data migration combining with work-stealing can further improve the efficiency of parallel graph processing; 2) Interleaving accesses to different graph partitions due to data dependency have a significant impact on the effectiveness of data migration. To address these problems, we propose NVMGraph, a parallel graph processing scheme to mitigate memory access imbalance among partitions in hybrid memory systems. We first recognize data dependency among all partitions according to graph algorithms and then coalesce the randomly-accessed data required by a working thread in a single partition to mitigate data dependency. To reduce migration cost while still speeding up the straggler task, we only migrate randomly-accessed data blocks in the most frequently-accessed partition from NVM to DRAM. We implement NVMGraph based on Ligra and evaluate it in a hybrid memory system using real NVM devices. Experimental results demonstrate that NVMGraph can improve the performance of graph processing by up to 40.3% compared with the state-of-the-art Ligra and Polymer.

Hybrid memories exacerbate the asymmetry of memory access latencies in Non-Uniform Memory Access (NUMA) systems due to the vast performance gap between DRAM and Nonvolatile Memory (NVM). Since most graph processing systems have not considered the memory heterogeneity of NUMA nodes, they have sub-optimal performance due to improper data placement and access strategies. This paper proposes HNGraph, a graph processing framework for hybrid memory based NUMA systems. It mainly focuses on performance improvement by reducing random accesses to both local and remote NVM nodes. First, HNGraph assembles most random memory accesses in DRAM by exploiting a degree-aware partitioning strategy, which distributes high-degree and low-degree vertices to DRAM and NVM nodes, respectively. Second, we propose an adaptive graph processing model, which uses a hybrid inter-node communication mechanism to adapt to the asymmetric access latency between NVM and DRAM nodes. In DRAM nodes, we exploit a message passing communication model for remote random NVM updates. In NVM nodes, we use shared memory primitives to access remote DRAM directly. We evaluate the performance of HNGraph using different graph algorithms on typical datasets. Experimental results show that HNGraph can improve the application performance by 43.8% and 30.6% on average compared with the state-of-the-art graph processing systems GBBS and Polymer, respectively.

High Bandwidth Memory (HBM) provides massive aggregated memory bandwidth by exposing multiple memory channels to the processing units. To achieve high performance, an accelerator built on top of an FPGA configured with HBM (i.e., FPGA-HBM platform) needs to scale its performance according to the available memory channels. In this paper, we propose an accelerator for BFS (Breadth-First Search), named as ScalaBFS, which decouples memory accessing from processing to scale its performance with available HBM memory channels. Moreover, by configuring each HBM memory channel with multiple processing elements, ScalaBFS sufficiently exploits the memory bandwidth of HBM. We implement the prototype system of ScalaBFS and conduct BFS in both real-world and synthetic scale-free graphs on Xilinx Alveo U280 Data Center Accelerator card (real hardware). The experimental results show that ScalaBFS scales its performance almost linearly according to the available memory pseudo channels (PCs) from the HBM2 subsystem of U280. By fully using the 32 PCs and building 64 processing elements (PEs) on U280, ScalaBFS achieves a performance up to 19.7 GTEPS (Giga Traversed Edges Per Second). When conducting BFS in sparse real-world graphs, ScalaBFS achieves equivalent GTEPS to Gunrock running on the state-of-art Nvidia V100 GPU that features 64-PC HBM2 (twice memory bandwidth than U280).

Existing FPGA-based graph accelerators, typically designed for static graphs, rarely handle dynamic graphs that often involve substantial graph updates (e.g., edge/node insertion and deletion) over time. In this paper, we aim to fill this gap. The key innovation of this work is to build an FPGA-based dynamic graph accelerator easily from any off-the-shelf static graph accelerator with minimal hardware engineering efforts (rather than from scratch). We observe \em spatial similarity of dynamic graph updates in the sense that most of graph updates get involved with only a small fraction of vertices. We therefore propose an FPGA library, called GraSU, to exploit spatial similarity for fast graph updates. GraSU uses a differential data management, which retains the high-value data (that will be frequently accessed) in the specialized on-chip UltraRAM while the overwhelming majority of low-value ones reside in the off-chip memory. Thus, GraSU can transform most of off-chip communications arising in dynamic graph updates into fast on-chip memory accesses. Our experiences show that GraSU can be easily integrated into existing state-of-the-art static graph accelerators with only 11 lines of code modifications. Our implementation atop AccuGraph using a Xilinx Alveo#8482; \ U250 board outperforms two state-of-the-art CPU-based dynamic graph systems, Stinger and Aspen, by an average of 34.24× and 4.42× in terms of update throughput, improving further overall efficiency by 9.80× and 3.07× on average.

Many graph processing systems have been recently developed for many-core processors. However, for iterative graph processing, due to the dependencies between vertices' states, the propagations of new states of vertices are inherently conducted along graph paths sequentially and are also dependent on each other. Despite the years' research effort, existing solutions still severely underutilize many-core processors to quickly propagate the new states of vertices, suffering from slow convergence speed. In this paper, we propose a dependency-driven programmable accelerator, DepGraph, which couples with the core architecture of the many-core processor and can fundamentally alleviate the challenge of dependencies for faster state propagation. Specifically, we propose an effective dependency-driven asynchronous execution approach into novel microarchitecture designs for faster state propagations. DepGraph prefetches the vertices for the core on-the-fly along the dependency chains between their states and the active vertices' new states, aiming to effectively accelerate the propagations of the active vertices' new states and also ensure better data locality. Through transforming the dependency chains along the frequently-used paths into direct ones at runtime and maintaining these calculated direct dependencies as a set of fast shortcuts, called hub index, DepGraph further accelerates most state propagations. Also, many propagations do not need to wait for the completion of other propagations, which enables more propagations to be effectively conducted along the paths with higher degree of parallelism. The experimental results show that for iterative graph processing on a simulated 64-core processor, a cutting-edge software graph processing system can achieve 5.0-22.7 times speedup after integrating with our DepGraph while incurring only 0.6% area cost. In comparison with three state-of-the-art hardware solutions, i.e., HATS, Minnow, and PHI, DepGraph improves the performance by up to 3.0-14.2, 2.2-5.8, and 2.4-10.1 times, respectively.

Efficiently retrieving data is essential for key-value store applications. A major part of the retrieving time is on data addressing, that is, finding the location of the value in memory that corresponds to a key. This paper introduces an address-centric approach to speed up the addressing by creating a shortcut for the translation of a key to the physical address of the value. The new technique is materialized with a novel in-memory table, STLT, a virtual-physical address buffer, and two new instructions. It creates a fast path for data addressing and meanwhile opens up opportunities for the use of simpler and faster hash tables to strike a better tradeoff between hashing conflicts and hashing overhead. Together, the new technique brings up to 1.4× speedups on key-value store application Redis and up to 13× speedups on some widely used indexing data structures, consistently outperforming prior solutions significantly.

Byte-addressable Non-volatile Memory (NVM) technologies promise higher density and lower cost than DRAM. They have been increasingly employed for data center applications. Despite many previous studies on using NVM in a single machine, there remain challenges to best utilize it in a distributed data center environment. This paper presents Gengar, an RDMA-enabled Distributed Shared Hybrid Memory (DSHM) pool with simple programming APIs on viewing remote NVM and DRAM in a global memory space. We propose to exploit semantics of RDMA primitives to identify frequently-accessed data in the hybrid memory pool, and cache it in distributed DRAM buffers. We redesign RDMA communication protocols to reduce the bottleneck of RDMA write latency by leveraging a proxy mechanism. Gengar also supports memory sharing among multiple users with data consistency guarantee. We evaluate Gengar in a real testbed equipped with Intel Optane DC Persistent DIMMs. Experimental results show that Gengar significantly improves the performance of public benchmarks such as MapReduce and YCSB by up to 70 % compared with state-of-the-art DSHM systems.

As mainstream computing is poised to embrace the advent of byte-addressable non-volatile memory (NVM), an important roadblock has remained largely unnoticed, support of legacy libraries on NVM. Libraries underpin modern software everywhere. As current NVM programming interfaces all designate special types and constructs for NVM objects and references, legacy libraries, being incompatible with these data types, will face major obstacles for working with future applications written for NVM. This paper introduces a simple approach to mitigating the issue. The novel approach centers around user-transparent persistent reference, a new concept that allows programmers to reference a persistent object in the same way as reference a normal (volatile) object. The paper presents the implementation of the concept, carefully examines its soundness, and describes compiler and simple architecture support for keeping performance overheads very low.

In modern data centers, massive concurrent graph processing jobs are being processed on large graphs. However, existing hardware/-software solutions suffer from irregular graph traversal and intense resource contention. In this paper, we propose LCCG, a Locality-Centric programmable accelerator that augments the many-core processor for achieving higher throughput of Concurrent Graph processing jobs. Specifically, we develop a novel topology-aware execution approach into the accelerator design to regularize the graph traversals for multiple jobs on-the-fly according to the graph topology, which is able to fully consolidate the graph data accesses from concurrent jobs. By reusing the same graph data among more jobs and coalescing the accesses of the vertices' states for these jobs, LCCG can improve the core utilization. We conduct extensive experiments on a simulated 64-core processor. The results show that LCCG improves the throughput of the cutting-edge software system by 11.3~23.9 times with only 0.5% additional area cost. Moreover, LCCG gains the speedups of 4.7~10.3, 5.5~13.2, and 3.8~8.4 times over state-of-the-art hardware graph processing accelerators (namely, HATS, Minnow, and PHI, respectively).

The advent of Persistent Memory (PM) necessitates an evolution of Remote Direct Memory Access (RDMA) technologies for supporting remote data persistence. Previous software-based solutions require remote CPU intervention and postpone the visibility of remote persistence. In this paper, we design several hardware-supported RDMA primitives to flush data from the volatile cache of RDMA Network Interface Cards (RNICs) to the PM. We also propose durable RPCs based on the proposed RDMA Flush primitives to support remote data persistence and fast failure recovery. We emulate the performance of RDMA Flush primitives through other RDMA primitives, and compare our proposals with several state-of-the-art RPCs in a real testbed equipped with PM and InfiniBand networks. Experimental results show that our proposals can improve the throughput of RPCs by up to 90%, and reduce the 99th percentile latency by up to 49%. The experimental studies also provide instructive guidelines for designing RDMA-based distributed PM systems.

Many out-of-GPU-memory systems are recently designed to support iterative processing of large-scale graphs. However, these systems still suffer from long time to converge because of inefficient propagation of active vertices’ new states along graph paths. To efficiently support out-of-GPU-memory graph processing, this work designs a system LargeGraph . Different from existing out-of-GPU-memory systems, LargeGraph proposes a dependency-aware data-driven execution approach , which can significantly accelerate active vertices’ state propagations along graph paths with low data access cost and also high parallelism. Specifically, according to the dependencies between the vertices, it only loads and processes the graph data associated with dependency chains originated from active vertices for smaller access cost. Because most active vertices frequently use a small evolving set of paths for their new states’ propagation because of power-law property, this small set of paths are dynamically identified and maintained and efficiently handled on the GPU to accelerate most propagations for faster convergence, whereas the remaining graph data are handled over the CPU. For out-of-GPU-memory graph processing, LargeGraph outperforms four cutting-edge systems: Totem (5.19–11.62×), Graphie (3.02–9.41×), Garaph (2.75–8.36×), and Subway (2.45–4.15×).

Most of existing graph processing systems essentially follow pull-based computation model to handle compute-intensive parts of graph iteration for high parallelism. Considering all vertices and edges are processed in each iteration, pull model may suffers from a large number of invalid (vertex/edge) operations that do not contribute to graph convergence, leading to potential performance degradation. In this paper, we have the insight that these invalid operations can be filtered by leveraging a small fraction of critical information. However, most of critical information are often beyond the visibility of active vertices being processed. We present two novel filtration approaches to (cooperatively) identify out-of-visibility critical information with boundary-cut heuristics and speculative prediction for many graph algorithms. We have integrated both approaches and their hybrid solution into three state-of-art graph processing systems (including Ligra, Gemini, and Polymer). Experimental results using a wide variety of graph algorithms on both real-world and synthetic graph datasets show that neither of these approaches can have an absolute win for all graph algorithms. Boundary-cut, predictive, and hybrid approaches can improve the performance by 115.1, 38.1, and 136.6 percent on average.

Existing studies on indoor navigation often require such a pre-deployment as floor map, localization system and/or additional (customized) hardwares, or human motion traces, making them prohibitive when the situation deviates from these requirements (e.g., navigating a crowd of panicking people where no localization system or motion traces are available). The main observation inspiring our work without reliance on such pre-deployment is that when there are sufficient participants (e.g., a crowd of panicking people), the WiFi signatures collected by participants can serve as the fingerprints (referred to as location fingerprints) of their unknown locations. By computing relative positions of these location fingerprints we can connect them to form a global map. Such a map reflects the topology of the underlying walkable space and thus holds the potential of offering a navigation path for any intended users. Based on this observation, we design Fly-Navi, a crowdsourcing based indoor navigation system via on-the-fly map generation, and primarily designed for indoor environments with rectilinear and narrow corridors. Specifically, each participant uploads sensory data, and the server then generates a global map (on-the-fly map) through a series of operations such as local map generation, local map stitch and edge computation. On top of the global map, Fly-Navi computes a navigation path to the given destination and tracks the progress. We implement the prototype of Fly-Navi and our experiments show that Fly-Navi can quickly generate a correct global map with the 80-percentile of between-fingerprint distance error less than 3 meters, which is important for computing turning points of the map and hereon offering turn-by-turn instructions, and correctly navigate the intended users to their destinations.

Fingerprinting technique for indoor positioning based on 5G system has attracted attention. Kalman filter (KF) is used as preprocessing of raw data to reduce the disturbance of Received Signal Strength (RSS) values. After preprocessing, Universal Kriging (UK) algorithm is adopted to reduce the efforts of establishing a fingerprinting database by Spatial Interpolation. A machine learning algorithm named K‐Nearest Neighbour (KNN) is used to calculate user equipment’s position. Real experiments are setup with 5G signals over the air. Two indoor scenarios are considered depending whether the base station is located in the same room with user equipment or not. In test room A, the proposed KF and UK algorithms achieve 53% positioning accuracy improvement. In test room B, 43% performance improvement is obtained by the proposed algorithm. 1.44‐meter positioning error is observed as the best case for 80% test samples.

The persistent memory (PM) requires maintaining the crash consistency and encrypting data, to ensure data recoverability and data confidentiality. The enforcement of these two goals does not only put more burden on programmers but also degrades performance. To address this issue, we propose a hardware-assisted encrypted persistent memory system. Specifically, logging and data encryption are assisted by hardware. Furthermore, we apply the counter-based encryption and the cipher feedback (CFB) mode encryption to data and log respectively, reducing the encryption overhead. Our primary experimental results show that the transaction throughput of the proposed design outperforms the baseline design by up to 34.4%.

Resistive random access memory (ReRAM) addresses the high memory bandwidth requirement challenge of graph analytics by integrating the computing logic in the memory. Due to the matrix-structured crossbar architecture, existing ReRAM-based accelerators, when handling real-world graphs that often have the skewed degree distribution, suffer from the severe sparsity problem arising from zero fillings and activation nondeterminism, incurring substantial ineffectual computations.In this paper, we observe that the sparsity sources lie in the consecutive mapping of source and destination vertex index onto the wordline and bitline of a crossbar. Although exhaustive graph reordering improves the sparsity-induced inefficiency, its totally-random (source and destination) vertex mapping leads to expensive overheads. This work exploits the insight in a mid-point vertex mapping with the random wordlines and consecutive bitlines. A cost-effective preprocessing is proposed to exploit the insight by rapidly exploring the crossbar-fit vertex reorderings but ignores the sparsity arising from activation dynamics. We present a novel ReRAM-based graph analytics accelerator, named Spara, which can maximize the workload density of crossbars dynamically by using a tightly-coupled bank parallel architecture further proposed. Results on real-world and synthesized graphs show that Spara outperforms GraphR and GraphSAR by 8.21 × and 5.01 × in terms of performance, and by 8.97 × and 5.68× in terms of energy savings (on average), while incurring a reasonable (<; 9.98%) pre-processing overhead.

Processing-In-Memory (PIM) is an emerging technology that addresses the memory bottleneck of graph processing. In general, analog memristor-based PIM promises high parallelism provided that the underlying matrix-structured crossbar can be fully utilized while digital CMOS-based PIM has a faster single-edge execution but its parallelism can be low. In this paper, we observe that there is no absolute winner between these two representative PIM technologies for graph applications, which often exhibit irregular workloads. To reap the best of both worlds, we introduce a new heterogeneous PIM hardware, called Hetraph, to facilitate energy-efficient graph processing. Hetraph incorporates memristor-based analog computation units (for high-parallelism computing) and CMOS-based digital computation cores (for efficient computing) on the same logic layer of a 3D die-stacked memory device. To maximize the hardware utilization, our software design offers a hardware heterogeneity-aware execution model and a workload offloading mechanism. For performance speedups, such a hardware-software co-design outperforms the state-of-the-art by 7.54 ×(CPU), 1.56 ×(GPU), 4.13× (memristor-based PIM) and 3.05× (CMOS-based PIM), on average. For energy savings, Hetraph reduces the energy consumption by 57.58× (CPU), 19.93× (GPU), 14.02 ×(memristor-based PIM) and 10.48 ×(CMOS-based PIM), on average.

Serverless computing, also known as “Function as a Service (FaaS)”, is emerging as an event-driven paradigm of cloud computing. In the FaaS model, applications are programmed in the form of functions that are executed and managed separately. Functions are triggered by cloud users and are provisioned dynamically through containers or virtual machines (VMs). The startup delays of containers or VMs usually lead to rather high latency of response to cloud users. Moreover, the communication between different functions generally relies on virtual net devices or shared memory, and may cause extremely high performance overhead. In this paper, we propose Unikernel-as-a-Function (UaaF), a much more lightweight approach to serverless computing. Applications are abstracted as a combination of different functions, and each function are built as an unikernel in which the function is linked with a specified minimum-sized library operating system (LibOS). UaaF offers extremely low startup latency to execute functions, and an efficient communication model to speed up inter-functions interactions. We exploit an new hardware technique (namely VMFUNC) to invoke functions in other unikernels seamlessly (mostly like inter-process communications), without suffering performance penalty of VM Exits. We implement our proof-of-concept prototype based on KVM and deploy UaaF in three unikernels (MirageOS, IncludeOS, and Solo5). Experimental results show that U aaF can significantly reduce the startup latency and memory usage of serverless cloud applications. Moreover, the VMFUNC-based communication model can also significantly improve the performance of function invocations between different unikernels.

Graph mining is becoming increasingly important due to the ever-increasing demands on analyzing complex structures in graphs. Existing graph accelerators typically hold most of the randomly-accessed data in an on-chip memory to avoid off-chip communications. However, graph mining exhibits substantial random accesses from not only vertex dimension but also edge dimension (with the latter being excessively more complex than the former), leading to significant degradations in terms of both performance and energy efficiency.We observe that the most random memory requests arising in graph mining come from accessing a small fraction of valuable (vertex and edge) data when handling real-world graphs. To exploit this extension locality with maximum parallelism, we architect GRAMER, the first graph mining accelerator. GRAMER contains a specialized memory hierarchy, where the valuable data (precisely identified through a cost-efficient heuristic) is permanently resident in a high-priority memory while others are maintained in a cache-like memory under a lightweight replacement policy. The specific pipelined processing units are carefully designed to maximize computational parallelism. GRAMER is also equipped with a work-stealing mechanism to reduce load imbalance. We have implemented GRAMER on a Xilinx Alveo U250 accelerator card. Compared with two state-of-the-art CPU-based graph mining systems, Fractal and RStream, running on a 14-core Intel E5-2680 v4 processor, GRAMER achieves not only considerable speedups (1.11 × ~ 129.95 ) but also significant energy savings (5.79 × ~ 678.34×)

Graph computing now is popular in many areas, including social network and gene sequence alignment. Graph computing system and algorithm have a history prior to the use of graph databases and have a future that is not necessarily entangled with typical database concerns. With the data's increasing size, many distributed graph-computing systems have been developed in recent years to process and analyze massive graphs. Researchers pay more attention on the graph partition schemes on distributed environment. However, other researchers think a single system can avoid the network overhead and may have better performance even if the data size is too big for the memory space. With the rapid development of coprocessors, some researchers think it is promising to build a domain specific computer, just for graph computing. The proposed special issue of Concurrency and Computation: Practice and Experience contains revised and extended versions of selected best papers with respect to graph computing at the 21st IEEE International Conference on Parallel and Distributed Systems (ICPADS’16), which was held at Wuhan, China, on December 13-16, 2016. Established in 1992, ICPADS has been a major international forum for scientists, engineers, and users to exchange and share their experiences, new ideas, and latest research results on all aspects of parallel and distributed computing systems. The purpose of this special issue is to provide a comprehensive view into recent advances in systems software, algorithms, partition schemes, and even graph computer based on new advances in computer architecture and applications. The five selected papers are summarized as follows. The first paper, titled “An efficient iterative graph data processing framework based on bulk synchronous parallel model” by Liu et al,1 presents an efficient computational framework for graph data processing based on the bulk synchronous parallel model. Existing Pregel-like graph processing systems remains in its early stage, and there still exist many challenges with prohibitive superstep-synchronized overhead. Furthermore, the graph data partition strategy in these earlier graph systems fails to support load balancing, therefore causing the increase of network I/O overhead as the scale of graph data grows. Thus, this paper leverages a global synchronization mechanism to enhance the performance of graph computation. Meanwhile, a balanced hash-based graph partition mechanism is presented to optimize the large-scale graph data processing. The work has a real implementation upon on Pregrel system, which can better support a variety of graph analytics applications. The second paper, titled “An efficient iterative graph data processing framework based on bulk synchronous parallel model” by Linchen Yu,2 proposes an optimized scheduling system for parallelizing the programs in the Xen. Virtualization challenges the traditional CPU scheduling, leading that the spin lock in virtualized environment can be preempted by the VMM, increasing synchronization overhead and decreasing the performance of parallel programs. Many studies have proposed the co-scheduling to alleviate this problem. However, these earlier attempts are not suitable to non-parallel workloads with the CPU fragmentation problem as well. Therefore, a simultaneous optimization scheduling system, called CCHybrid, is proposed in the Xen virtualized environment. Results show the efficiency of CCHybrid over the traditional Xen Credit scheduler. The third paper, titled “ms-PoSW: A multi-server aided proof of shared ownership scheme for secure deduplication in cloud” by Xiong et al,3 introduces a novel concept of the Proof for securing client-side deduplication of the shared files. With the rapid development of cloud computing and big data technologies, collaborative cloud applications are inextricably linked to our daily life and, therefore, produce a large number of shared files, which is challenging for secure access and data duplication in cloud. This paper proposes a novel multiserver-aided PoSW scheme for collaborative cloud applications and propose a hybrid PoSW scheme to reduce the computational cost of the shared owner's client. Furthermore, a hybrid PoSW scheme is constructed to address the secure proof of hybrid cloud architectures. The fourth paper, titled “Sparse random compressive sensing based data aggregation in wireless sensor networks” by Yin et al,4 introduces a compressive data aggregation scheme. In wireless sensor networks, the increasingly expanding data volume has high spatial-temporal correlation. Although some earlier studies attempt to eliminate data redundancy, few can handle energy consumption and latency simultaneously. In this paper, the authors a delay-minimum energy-balanced data aggregation method, which can eliminate the redundancy among the readings and prolong the network lifetime. A sparse random matrix is adopted as a measurement matrix to balance communication cost. Particularly, each measurement can form an aggregation tree with minimum delay. Furthermore, a novel scheduling method is used to avoid information interference as well. The fifth paper, titled “Dynamic cluster strategy for hierarchical rollback-recovery protocols in MPI HPC applications” by Liao et al,5 proposes a dynamic cluster strategy to adapt to the runtime variation of communication pattern by using a prediction scheme. The idea comes from a fact that Hierarchical rollback-recovery protocols provide failure containment and reduce the amount of message to be logged, making it an attractive and scalable solution for fault tolerance even at a large scale. This paper shows how the communication pattern changes with the stages of application because MPI HPC applications scale up and become more complex. Therefore, to further increase the efficiency of hierarchical rollback-recovery protocols, the authors propose a dynamic cluster strategy (DCS) to adapt to the change of communication pattern. In contrast to the existing static process partition algorithms, this strategy adopts a prediction mechanism by using the clusters of processes obtained from prior part of applications in the succeeding part. Detailed experiments are then performed to evaluate the effectiveness and efficiency DCS at an extremely large scale. We hope that the readers would find the contents of this special issue interesting and further inspire them to look ahead into the challenges of designing, exploring, and exploiting graph analytics applications.

Summary Fault tolerance in parallel computing becomes increasingly important with a significant rise in high‐performance computing systems. Coordinated checkpointing and message logging protocols are commonly used fault tolerance mechanisms for message‐passing applications. However, these mechanisms are insufficient because of their severe drawbacks. Hierarchical rollback‐recovery protocols, combining coordinated checkpointing with message logging, are a better solution. However, such protocols may not obtain the appropriate efficiency because the communication pattern in different stages of applications may vary at runtime. In an effort to improve the efficiency of hierarchical rollback‐recovery protocols, we propose a dynamic cluster strategy to adapt to the runtime variation of communication pattern by using a prediction scheme. Finally, the efficiency and scalability of the dynamic cluster strategy are evaluated using 2 static process partition algorithms on the High‐Performance Linpack benchmark.

FPGA-based graph processing accelerators are nowadays equipped with multiple pipelines for hardware acceleration of graph computations. However, their multi-pipeline efficiency can suffer greatly from the considerable overheads caused by the read/write conflicts in their on-chip BRAM from different pipelines, leading to significant performance degradation and poor scalability. In this article, we investigate the underlying causes behind such inter-pipeline read/write conflicts by focusing on multi-pipeline FPGAs for accelerating Sparse Matrix Vector Multiplication (SpMV) arising in graph processing. We exploit our key insight that the problem of eliminating inter-pipeline read/write conflicts for SpMV can be formulated as one of solving a row- and column-wise tiling problem for its associated adjacency matrix. However, how to partition a sparse adjacency matrix obtained from any graph with respect to a set of pipelines by both eliminating all the inter-pipeline read/write conflicts and keeping all the pipelines reasonably load-balanced is challenging. We present a conflict-free scheduler, WaveScheduler, that can dispatch different sub-matrix tiles to different pipelines without any read/write conflict. We also introduce two optimizations that are specifically tailored for graph processing, “degree-aware vertex index renaming” for improving load balancing and “data re-organization” for enabling sequential off-chip memory access, for all the pipelines. Our evaluation on Xilinx®Alveo™ U250 accelerator card with 16 pipelines shows that WaveScheduler can achieve up to 3.57 GTEPS, running much faster than native scheduling and two state-of-the-art FPGA-based graph accelerators (by 6.48× for “native,” 2.54× for HEGP, and 2.11× for ForeGraph), on average. In particular, these performance gains also scale up significantly as the number of pipelines increases.

Recently, iterative graph algorithms are proposed to be handled by GPU-accelerated systems. However, in iterative graph processing, the parallelism of GPU is still underutilized by existing GPU-based solutions. In fact, because of the power-law property of the natural graphs, the paths between a small set of important vertices (e.g., high-degree vertices) play a more important role in iterative graph processing’s convergence speed. Based on this fact, for faster iterative graph processing on GPUs, this article develops a novel system, called AsynGraph , to maximize its data parallelism. It first proposes an efficient structure-aware asynchronous processing way . It enables the state propagations of most vertices to be effectively conducted on the GPUs in a concurrent way to get a higher GPU utilization ratio through efficiently handling the paths between the important vertices. Specifically, a graph sketch (consisting of the paths between the important vertices) is extracted from the original graph to serve as a fast bridge for most state propagations. Through efficiently processing this sketch more times within each round of graph processing, higher parallelism of GPU can be utilized to accelerate most state propagations. In addition, a forward-backward intra-path processing way is also adopted to asynchronously handle the vertices on each path, aiming to further boost propagations along paths and also ensure smaller data access cost. In comparison with existing GPU-based systems, i.e., Gunrock, Groute, Tigr, and DiGraph, AsynGraph can speed up iterative graph processing by 3.06–11.52, 2.47–5.40, 2.23–9.65, and 1.41–4.05 times, respectively.

Hybrid memory systems composed of emerging non-volatile memory (NVM) and DRAM have drawn increasing attention in recent years. To fully exploit the advantages of both NVM and DRAM, a primary goal is to properly place application data on the hybrid memories. Previous studies have focused on page migration schemes to achieve higher performance and energy efficiency. However, those schemes all rely on online page access monitoring (costly), and data migration at the page granularity may cause additional overhead due to DRAM bandwidth contention and maintenance of cache/TLB consistency. In this article, we present Object-level memory Allocation and Migration (OAM) mechanisms for hybrid memory systems. OAM exploits a profiling tool to characterize objects' memory access patterns at different execution phases of applications, and applies a performance/energy model to direct the initial static memory allocation and runtime dynamic object migration between NVM and DRAM. Based on our newly-developed programming interfaces for hybrid memory systems, application source codes can be automatically transformed via static code instrumentation. We evaluate OAM on an emulated hybrid memory system, and experimental results show that OAM can significantly reduce system energy-delay-product by 61 percent on average compared to a page-interleaving data placement scheme. It can also significantly reduce data migration overhead by 83 and 69 percent compared to the state-of-the-art page migration scheme CLOCK-DWF and 2PP, respectively, while improving application performance by up to 22 and 10 percent.

Current DRAM-based memory systems face the scalability challenges in terms of memory density, energy consumption, and monetary cost. Hybrid memory architectures composed of emerging nonvolatile memory (NVM) and DRAM is a promising approach to large-capacity and energy-efficient main memory. However, hybrid memory systems pose a new challenge to on-chip cache management due to the asymmetrical penalty of memory access to DRAM and NVM in case of cache misses. Cache hit rate is no longer an effective metric for evaluating memory access performance in hybrid memory systems. Current cache replacement policies that aim to improve the cache hit rate are not efficient either. In this article, we take into account the asymmetry of the cache miss penalty on DRAM and NVM, and advocate a more general metric, average memory access time (AMAT), to evaluate the performance of hybrid memories. We propose a miss penalty aware LRU-based cache replacement policy (MALRU) for hybrid memory systems. MALRU is aware of the source (DRAM or NVM) of missing blocks and preserves high-latency NVM blocks as well as low-latency DRAM blocks with good temporal locality in the last level cache. The experimental results show that MALRU can improve system performance by up to 22.8% and 13.1%, compared to LRU and the state-of-the-art hybrid memory aware cache partitioning technique policy, respectively.

The huge amount of data enforces great pressure on the processing efficiency of database systems. By leveraging the in-situ computing ability of emerging nonvolatile memory, processing-in-memory (PIM) technology shows great potential in accelerating database operations against traditional architectures without data movement overheads. In this article, we introduce ReSQM, a novel ReCAM-based accelerator, which can dramatically reduce the response time of database systems. The key novelty of ReSQM is that some commonly used database queries that would be otherwise processed inefficiently in previous studies can be in-situ accomplished with massively high parallelism by exploiting the PIM-enabled ReCAM array. ReSQM supports some typical database queries (such as SELECTION, SORT, and JOIN) effectively based on the limited computational mode of the ReCAM array. ReSQM is also equipped with a series of hardware-algorithm co-designs to maximize efficiency. We present a new data mapping mechanism that allows enjoying in-situ in-memory computations for SELECTION operating upon intermediate results. We also develop a count-based ReCAM-specific algorithm to enable the in-memory sorting without any row swapping. The relational comparisons are integrated for accelerating inequality join by making a few modifications to the ReCAM cells with negligible hardware overhead. The experimental results show that ReSQM can improve the (energy) efficiency by 611x (193x ), 19x (17x ), 59x (43x ), and 307x (181x) in comparison to a 10-core Intel Xeon E5-2630v4 processor for SELECTION, SORT, equi-join, and inequality join, respectively. In contrast to state-of-the-art CMOS-based CAM, GPU, FPGA, NDP, and PIM solutions, ReSQM can also offer 2.2x 39x speedups.

Emerging Non-Volatile Memory (NVM) technologies promise much higher memory density and energy efficiency than DRAM, at the expense of higher read/write latency and limited write endurance. Hybrid memory systems composed of DRAM and NVM have the potential to provide very large capacity of main memory for in-memory key-value (K-V) stores. However, there remains challenges to directly deploy DRAM-based K-V stores in hybrid memory systems. The performance and energy efficiency of K-V stores on hybrid memory systems have not been fully explored yet. In this paper, we propose HMCached, an in-memory K-V store built on a hybrid DRAM/NVM system. HMCached utilizes an application-level data access counting mechanism to identify frequently-accessed (hotspot) objects (i.e., K-V pairs) in NVM, and migrates them to fast DRAM to reduce the costly NVM accesses. We also propose an NVM-friendly index structure to store the frequently-updated portion of object metadata in DRAM, and thus further mitigate the NVM accesses. Moreover, we propose a benefit-aware memory reassignment policy to address the slab calcification problem in slab-based K-V store systems, and significantly improve the benefit gain from the DRAM. We implement the proposed schemes with Memcached and evaluate it with Zipfian-like workloads. Experiment results show that HMCached significantly reduces NVM accesses by 70 percent compared to the vanilla Memcached running on a DRAM/NVM hybrid memory system without any optimizations, and improves application performance by up to 50 percent. Moreover, compared to a DRAM-only system, HMCached achieves 90 percent of performance and 46 percent reduction of energy consumption for realistic (read-intensive) workloads while significantly reducing the DRAM usage by 75 percent.

Graph processing is one of the important research topics in the big-data era. To build a general framework for graph processing by using a DRAM-based FPGA board with deep memory hierarchy, one of the reasonable methods is to partition a given big graph into multiple small subgraphs, represent the graph with a two-dimensional grid, and then process the subgraphs one after another to divide and conquer the whole problem. Such a method (grid-graph processing) stores the graph data in the off-chip memory devices (e.g., on-board or host DRAM) that have large storage capacities but relatively small bandwidths, and processes individual small subgraphs one after another by using the on-chip memory devices (e.g., FFs, BRAM, and URAM) that have small storage capacities but superior random access performances. However, directly exchanging graph (vertex and edge) data between the processing units in FPGA chip with slow off-chip DRAMs during grid-graph processing leads to limited performances and excessive data transmission amounts between the FPGA chip and off-chip memory devices. In this article, we show that it is effective in improving the performance of grid-graph processing on DRAM-based FPGA hardware accelerators by leveraging the flexibility and programmability of FPGAs to build application-specific caching mechanisms, which bridge the performance gaps between on-chip and off-chip memory devices, and reduce the data transmission amounts by exploiting the localities on data accessing. We design two application-specific caching mechanisms (i.e., vertex caching and edge caching ) to exploit two types of localities (i.e., vertex locality and subgraph locality ) that exist in grid-graph processing, respectively. Experimental results show that with the vertex caching mechanism, our system (named as FabGraph) achieves up to 3.1× and 2.5× speedups for BFS and PageRank, respectively, over ForeGraph when processing medium graphs stored in the on-board DRAM. With the edge caching mechanism, the extension of FabGraph (named as FabGraph+) achieves up to 9.96× speedups for BFS over FPGP when processing large graphs stored in the host DRAM.

Many systems are recently proposed for large-scale iterative graph analytics on a single machine with GPU accelerators. Despite of many research efforts, for iterative directed graph processing over GPUs, existing solutions suffer from slow convergence speed and high data access cost, because many vertices are ineffectively reprocessed for lots of rounds so as to update their states according to other active vertices regardless of their dependencies. In this paper, we propose a novel and efficient iterative directed graph processing system on a machine with the support of multiple GPUs. Compared with existing systems, the unique feature of our system is that it takes advantage of the dependencies between vertices in three novel ways. First, it represents a directed graph into a set of disjoint hot/cold directed paths and takes the path as the basic parallel processing unit, so as to help efficient vertex state propagation along the paths over GPUs for faster convergence speed and higher utilization ratio of the loaded data. Second, it tries to dispatch the paths to GPUs for parallel processing according to the topological order of the dependency graph of them. Many paths then converge along such an order after processing them for exactly once, getting lower reprocessing overhead. Third, a path scheduling strategy is further developed on each streaming multiprocessor to enable the privileged execution of the paths (e.g., the hot paths) with greater impacts on vertex state propagation for shorter convergence time according to vertex dependency. Experimental results show that our approach speeds up iterative directed graph processing by up to 3.54 times in comparison with the state-of-the-art systems.

With the maturity of monolithic 3D integration, 3D ReRAM provides impressive storage-density and computational-parallelism with great opportunities for parallel-graph processing acceleration. In this paper, we present RAGra, a 3D ReRAM-based graph processing accelerator, which has two significant technical highlights. First, monolithic 3D ReRAM usually has the complexly-intertwined feature with shared input wordlines and output bitlines for different layers. We propose novel mapping schemes, which can guide to apply different graph algorithms into 3D ReRAM seamlessly and correctly for exposing the inherently-irregular parallelism of 3D ReRAM. Second, consider the sparsity of real-world graphs, we further propose a row- and column-mixed execution model, which can filter invalid subgraphs for exploiting the massive parallelism of 3D ReRAM. Our evaluation on 8-layer stacked ReRAM shows that RAGra outperforms state-of-the-art planar (2D) ReRAM based graph accelerator GraphR by 6.18× performance improvement and 2.21 ×energy saving, on average. In particular, RAGra significantly outperforms Grid-Graph (a typical CPU-based graph system) by up to 293.12×.

In recent years, graph processing attracts lots of attention due to its broad applicability in solving real-world problems. With the flexibility and programmability, FPGA platforms provide the opportunity of processing the graph data with high efficiency. On FPGA-DRAM platforms, the state-of-art solution of graph processing (i.e., ForeGraph) attaches each pipeline with local vertex buffers to cache the source and destination vertices during processing. Such one-level vertex caching mechanism, however, results in excessive amounts of vertex data transmissions that consume the precious DRAM bandwidth, and frequent pipeline stalls that waste the processing power of the FPGA. In this paper, we propose a two-level vertex caching mechanism to improve the performance of graph processing on FPGA-DRAM platforms by reducing the amounts of vertex data transmissions and pipeline stalls during the execution of graph algorithms. We build a system, named as FabGraph, to implement such two-level vertex caching mechanism by using available on-chip storage resources, including BRAM and UltraRAM. Experimental results show that: FabGraph achieves up to 3.1x and 2.5x speedups over ForeGraph for BFS and PageRank respectively, on the FPGA board with relatively large BRAM; and up to 3.1x and 3.0x speedups over ForeGraph for BFS and PageRank respectively, on the FPGA board with small BRAM but large UltraRAM. Our experience in this paper suggests that the two-level vertex caching design is effective in improving the performance of graph processing on FPGA-DRAM platforms.

Non-uniform memory access (NUMA) architectures feature asymmetrical memory access latencies on different CPU nodes. Hybrid memory systems composed of non-volatile memory (NVM) and DRAM further diversify memory access latencies due to the relatively large performance gap between NVM and DRAM. Traditional NUMA memory management policies fail to manage hybrid memories effectively and may even hurt application performance. In this paper, we present HiNUMA, a new NUMA abstraction for memory allocation and migration in hybrid memory systems. HiNUMA advocates NUMA topologyaware hybrid memory allocation policies for the initial data placement. HiNUMA also proposes a new NUMA balancing mechanism called HANB for memory migration at runtime. HANB considers both data access frequency and memory bandwidth utilization to reduce the cost of memory accesses in hybrid memory systems. We evaluate the performance of HiNUMA with several typical workloads. Experimental results show that HiNUMA can effectively utilize hybrid memories, and deliver much higher application performance than conventional NUMA memory management policies and other state-of-the-art work.

With the rapidly growing demand of graph processing in the real world, a large number of iterative graph processing jobs run concurrently on the same underlying graph. However, the storage engines of existing graph processing frameworks are mainly designed for running an individual job. Our studies show that they are inefficient when running concurrent jobs due to the redundant data storage and access overhead. To cope with this issue, we develop an efficient storage system, called GraphM. It can be integrated into the existing graph processing systems to efficiently support concurrent iterative graph processing jobs for higher throughput by fully exploiting the similarities of the data accesses between these concurrent jobs. GraphM regularizes the traversing order of the graph partitions for concurrent graph processing jobs by streaming the partitions into the main memory and the Last-Level Cache (LLC) in a common order, and then processes the related jobs concurrently in a novel fine-grained synchronization. In this way, the concurrent jobs share the same graph structure data in the LLC/memory and also the data accesses to the graph, so as to amortize the storage consumption and the data access overhead. To demonstrate the efficiency of GraphM, we plug it into state-of-the-art graph processing systems, including GridGraph, GraphChi, PowerGraph, and Chaos. Experiments results show that GraphM improves the throughput by 1.73~13 times.

We are living in a world where massive end devices perform computing everywhere and everyday. However, these devices are constrained by the battery and computational resources. With the increasing number of intelligent applications (e.g., augmented reality and face recognition) that require much more computational power, they shift to perform computation offloading to the cloud, known as mobile cloud computing (MCC). Unfortunately, the cloud is usually far away from end devices, leading to a high latency as well as the bad quality of experience (QoE) for latency-sensitive applications. In this context, the emergence of edge computing is no coincidence. Edge computing extends the cloud to the edge of the network, close to end users, bringing ultra-low latency and high bandwidth. Consequently, there is a trend of computation offloading toward edge computing. In this paper, we provide a comprehensive perspective on this trend. First, we give an insight into the architecture refactoring in edge computing. Based on that insight, this paper reviews the state-of-the-art research on computation offloading in terms of application partitioning, task allocation, resource management, and distributed execution, with highlighting features for edge computing. Then, we illustrate some disruptive application scenarios that we envision as critical drivers for the flourish of edge computing, such as real-time video analytics, smart “things” (e.g., smart city and smart home), vehicle applications, and cloud gaming. Finally, we discuss the opportunities and future research directions.

Superpages have long been used to mitigate address translation overhead in large-memory systems. However, superpages often preclude lightweight page migration, which is crucial for performance and energy efficiency in hybrid memory systems composed of DRAM and non-volatile memory (NVM). In this article, we propose a novel memory management mechanism called Rainbow to bridge this fundamental conflict between superpages and lightweight page migration. Rainbow manages NVM at the superpage granularity, and uses DRAM to cache frequently accessed (hot) small pages within each superpage. Correspondingly, Rainbow utilizes split TLBs to support different page sizes. By introducing an efficient hot page identification mechanism and a novel NVM-to-DRAM address remapping mechanism, Rainbow supports lightweight page migration without splintering superpages. Experiment results show that Rainbow can significantly reduce applications’ TLB misses by 99.9%, and improve application performance (in terms of IPC) by up to 2.9× (45.3% on average) when compared to a state-of-the-art memory migration policy without a superpage support.

Virtual machine image (VMI) management has become one of the key infrastructure components in Infrastructure as a Service (IaaS) cloud systems. Any “good” VMI management system should support flexible and efficient VMI services to cloud users, and offer scalable, easy-to-maintain and efficient VMI management for cloud providers. While there have been a number of systems and optimizations for VMI management, this paper investigates a declarative and data-centric approach to VMI management for both cloud users and providers. Specifically, by viewing VMI management as a data-intensive application, we propose Hemera, a novel VMI management system prototype based on relational database systems. Hemera adopts a data-centric approach to VMI management system design, where a VMI is modeled as structured data. With the data-centric approach, the key operations of VMI management can be recast naturally as programs based on SQL language. Moreover, Hemera embraces a series of automatic optimization opportunities with their root from databases. We have developed a system prototype based on MySQL. Our experimental results show the efficiency and feasibility of our declarative and data-centric approach to VMI Management.

Distributed graph processing platforms usually need to handle massive Concurrent iterative Graph Processing (CGP) jobs for different purposes. However, existing distributed systems face high ratio of data access cost to computation for the CGP jobs, which incurs low throughput. We observed that there are strong spatial and temporal correlations among the data accesses issued by different CGP jobs, because these concurrently running jobs usually need to repeatedly traverse the shared graph structure for the iterative processing of each vertex. Based on this observation, this article proposes a distributed storage and processing system CGraph for the CGP jobs to efficiently handle the underlying static/evolving graph for high throughput. It uses a data-centric load-trigger-pushing model, together with several optimizations, to enable the CGP jobs to efficiently share the graph structure data in the cache/memory and their accesses by fully exploiting such correlations, where the graph structure data is decoupled from the vertex state associated with each job. It can deliver much higher throughput for the CGP jobs by effectively reducing their average ratio of data access cost to computation. Experimental results show that CGraph improves the throughput of the CGP jobs by up to 3.47× in comparison with existing solutions on distributed platforms.

Time-evolving stream datasets exist ubiquitously in many real-world applications where their inherent hot keys often evolve over times. Nevertheless, few existing solutions can provide efficient load balancing on these time-evolving datasets while preserving low memory overhead. In this paper, we present a novel load balancing mechanism (named FISH), which can provide the efficient time-evolving stream processing at scale through recent hot keys identification and worker assignment. The key insight of this work is that the keys of time-evolving stream data can have a skewed distribution within the bounded distance of time interval. This enables to accurately identify the recent hot keys for the real-time load balancing within a bounded scope. We therefore propose an epoch-based recent hot key identification with specialized intra-epoch frequency counting (for maintaining low memory overhead) and inter-epoch hotness decaying (for suppressing superfluous computation). We also propose to heuristically infer the accurate information of remote workers through computation rather than communication for cost-efficient worker assignment. We have integrated our approach into Apache Storm. Our results on a cluster of 128 nodes for both synthetic and real-world stream datasets show that FISH significantly outperforms state-of-the-arts with the average and the 99th percentile latency reduction by 87.12 and 76.34 percent (versus W-Choices), and memory overhead reduction by 96.66 percent (versus Shuffle Grouping).

Existing data race detectors can witness race conditions for their occurrence but few can also identify the fundamental reasons for their understanding. In this paper, we present a new debugging framework for providing a concise schedule that can help not only witness but also understand data race. The key innovation of this work is to integrate dynamic slicing into constraint solving technique. We propose to use race manifestation (a fraction of memory accesses) to characterize buggy behaviors arising from data races. By encoding race manifestation constraints, existing constraint solving system is enabled to generate the buggy-behavior-exposing schedule, which is further simplified to a minimum as root cause via a tailored data race slicing technique further proposed.

Graph-specific computing with the support of dedicated accelerator has greatly boosted the graph processing in both efficiency and energy. Nevertheless, their data conflict management is still sequential when certain vertex needs a large number of conflicting updates at the same time, leading to prohibitive performance degradation. This is particularly true and serious for processing natural graphs.

Existing constraint-solving-based technique enables an efficient and high-coverage concurrency debugging. Yet, there remains a significant gap between the state of the art and the state of the programming practices for scaling to handle long-running execution of programs.

Frequent itemsets mining (FIM) plays an important role in many data mining areas. With the explosion of data scale, a number of parallel FIM algorithms have been proposed. Although existing solutions have outstanding scalability, they suffer from high consumption of CPU and memory for recursively mining frequent itemsets based on a tree-structure. In this paper, we propose a novel parallel algorithm, named PNPFI. It employs three novel key optimizations. In detail, the itemsets are stored by the N-list structure, which is more compact than existing tree-based structure. It uses a new structure, called P-Subsume, to generate some frequent itemsets without the process of N-list intersection. In addition, PNPFI proposes a new load balancing strategy, which intelligently divides a large-scale FIM problem into a set of tasks based on the profiled load of each item. Compared with the state-of-the-art algorithms, experimental results show that PNPFI gets a performance improvement of 39% on average (max to 79%), and reduces the memory usage by 58% on average (max to 90%).

Emerging non-volatile memory (NVM) technologies have been widely studied in recent years. Those studies mainly rely on cycle-accurate architecture simulators because the commercial NVM hardware is still unavailable. However, current simulation approaches are either too slow, or cannot simulate complex and large-scale workloads. In this paper, we propose a DRAM-based hybrid memory emulator, called HME, to emulate the performance characteristics of NVM devices. HME exploits hardware features available in commodity Non-Uniform Memory Access (NUMA) architectures to emulate two kinds of memories: fast, local DRAM, and slower, remote NVM on other NUMA nodes. HME can emulate a wide range of NVM latencies by injecting software-created memory access delays on the remote NUMA nodes. To evaluate the impact of hybrid memories on the application performance, we also provide application programming interfaces to allocate memory from NVM or DRAM regions. We evaluate the accuracy of the read/write delay injection models by using SPEC CPU2006 and compare the results with a state-of-the-art NVM emulator Quartz. Experimental results demonstrate that the average emulation errors of NVM read and write latencies are less than 5% in HME, which is much lower than Quartz. Moreover, the application performance overhead in HME is one order of magnitude lower than Quartz.

Theta join is commonly employed in real practices. Although SPARQL is a popular RDF query language, SPARQL does not define the specification of theta join until 2013. After that, few RDF stores except the stores based on RDBMS or key-value stores can process theta join. However, processing theta join on RDBMS or key-value stores is costly due to lack of RDF-native optimization. Efficient solutions to process theta join queries on RDF graph directly have not been fully explored. Here, we present ThetaStore to parallel process SPARQL theta join queries on large RDF graphs. First, a uniform SPARQL query graph model for theta join queries and equi-join queries is defined. Second, each subject, predicate, and object of RDF triples are mapped into order-preserving IDs instead of an random integer as most of RDF stores do. By this way, the engine does not need to translate theta join into a set of equi-joins. Finally, the engine employs decomposition and segment-oriented parallelization to execute SPARQL queries. The engine decomposes query into several star sub-queries and the intermediate results matching each pattern are divided into segments. Extensive experiments are conducted on large RDF data sets and experimental results show that ThetaStore outperforms state-of-the-art systems in both theta joins and equi-joins.

Existing graph processing essentially relies on the underlying iterative execution with synchronous (Sync) and/or asynchronous (Async) engine. Nevertheless, they both suffer from a wide class of inherent serialization arising from data interdependencies within a graph. In this article, we present SymGraph, a judicious graph engine with symbolic iteration that enables the parallelism of dependent computation on vertices. SymGraph allows using abstract symbolic value (instead of the concrete value) for the computation if the desired data is unavailable. To maximize the potential of symbolic iteration, we propose a chain of tailored sophisticated techniques, enabling SymGraph to scale out with a new milestone of efficiency for large-scale graph processing. We evaluate SymGraph in comparison to Sync, Async, and a hybrid of Sync and Async engines. Our results on 12 nodes show that SymGraph outperforms all three graph engines by 1.93x (vs. Sync), 1.98x (vs. Async), and 1.57x (vs. Hybrid) on average. In particular, the performance for PageRank on 32 nodes can be dramatically improved by 16.5x (vs. Sync), 23.3x (vs. Async), and 12.1x (vs. Hybrid), respectively. The efficiency of SymGraph is also validated with at least one order of magnitude improvement in contrast to three specialized graph systems (Naiad, GraphX, and PGX.D).

Graph algorithm is pervasive in many applications ranging from targeted advertising to natural language processing. Recently, Asynchronous Graph Processing (AGP) is becoming a promising model to support graph algorithm on large-scale distributed computing platforms because it enables faster convergence speed and lower synchronization cost than the synchronous model for no barrier between iterations. However, existing AGP methods still suffer from poor performance for inefficient vertex state propagation. In this paper, we propose an effective and low-cost forward and backward sweeping execution method to accelerate state propagation for AGP, based on a key observation that states in AGP can be propagated between vertices much faster when the vertices are processed sequentially along the graph path within each round. Through dividing graph into paths and asynchronously processing vertices on each path in an alternative forward and backward way according to their order on this path, vertex states in our approach can be quickly propagated to other vertices and converge in a faster way with only little additional overhead. In order to efficiently support it over distributed platforms, we also propose a scheme to reduce the communication overhead along with a static priority ordering scheme to further improve the convergence speed. Experimental results on a cluster with 1,024 cores show that our approach achieves excellent scalability for large-scale graph algorithms and the overall execution time is reduced by at least 39.8 percent, in comparison with the most cutting-edge methods.

Most of dynamic data race detection essentially relies on the underlying happens-before orders to yield the precise reports. They are notoriously prone to a prohibitively basic overhead. Although there exist a wealth of research advances that succeed in significantly reducing the analysis overhead on memory accesses, there remains an open problem in handling a great deal of fundamentally unscalable synchronization overhead, which can be particularly serious for the large, lock-intensive programs with a long running time and a large number of threads. In this paper, we revisit the synchronization problem of off-the-shelf race detection with a comprehensive study. The key insight of this work is that a full collection of partial orders for synchronization operations in prior work is not necessarily tracked and analyzed from a new perspective of “global clock” representation. We therefore develop this insight into a novel pending-period based approach, aiming at reducing the overhead of monitoring and analysis on unnecessary synchronization operations. Further, we also enable a significant improvement for enhancing the efficiency of existing sampling techniques, in which synchronization operations are often conservatively identified. Our experimental results on a wide variety of programs show that our approach outperforms state-of-the-art by 5.85x (versus FastTrack), 3.51x (versus ThreadSanitizer) and 1.34x (versus IFRit) program execution slowdown improvement on average, which can be more significant as the number of threads is increasing. Particularly for the lock-intensive programs (e.g., barnes), our approach can be 26.04x faster than FastTrack. Further, our pending period extended sampling is more efficient than Pacer (with up to 31.28 percent improvement in the case of 10 percent sampling rate).

Recently, there have been many disk-based systems proposed for iterative graph processing. In the popular vertex/edge-centric systems, an iterative directed graph algorithm needs to reprocess many partitions so as to update their vertices' states according to other non-convergent vertices for the unawareness of their dependencies. As a result, it induces high data access cost and a long time to converge. To tackle this problem, we propose a novel system for iterative directed graph processing with taking advantage of the strongly connected component (SCC) structure. It stores a directed graph into a directed acyclic graph (DAG) sketch, with each node representing a SCC in the original data graph. During execution, the SCCs are loaded into memory for processing in a parallel way according to the topological order of the DAG sketch, and the vertices in each SCC are tried to be handled along the directed paths. In this way, each SCC is able to reach convergence in order and needs to be loaded into the main memory for exactly once, getting much lower data access cost and faster convergence. Besides, the vertices of each SCC need fewer updates for convergence. We further develop a lightweight approach to maintain the DAG sketch and handle SCCs in an incremental way for evolving graphs. Compared with the state-of-the-art methods, experimental results show that our approach achieves a performance improvements of 1.46-8.37 times for static graphs, and can reduce the execution time by 61.4-72.7 percent for evolving graphs.

Current DRAM based memory systems face the scalability challenges in terms of storage density, power, and cost. Hybrid memory architecture composed of emerging Non-Volatile Memory (NVM) and DRAM is a promising approach to large-capacity and energy-efficient main memory. However, hybrid memory systems pose a new challenge to on-chip cache management due to the asymmetrical penalty of memory access to DRAM and NVM in case of cache misses. Cache hit rate is no longer an effective metric for evaluating memory access performance in hybrid memory systems. Current cache replacement policies that aim to improve cache hit rate are not efficient either. In this paper, we take into account the asymmetry of cache miss penalty on DRAM and NVM, and advocate a more general metric, Average Memory Access Time (AMAT), to evaluate the performance of hybrid memories. We propose a miss penalty-aware LRU-based (MALRU) cache replacement policy for hybrid memory systems. MALRU is aware of the source (DRAM or NVM) of missing blocks and prevents high-latency NVM blocks as well as low-latency DRAM blocks with good temporal locality from being evicted. Experimental results show that MALRU improves system performance against LRU and the state-of-the-art HAP policy by up to 20.4% and 11.7% (11.1% and 5.7% on average), respectively.

Existing graph processing frameworks greatly improve the performance of memory subsystem, but they are still subject to the underlying modern processor, resulting in the potential inefficiencies for graph processing in the sense of low instruction level parallelism and high branch misprediction. These inefficiencies, in accordance with our comprehensive micro-architectural study, mainly arise out of a wealth of dependencies, serial semantic of instruction streams, and complex conditional instructions in graph processing. In this paper, we propose that a fundamental shift of approach is necessary to break through the inefficiencies of the underlying processor via the dataflow paradigm. It is verified that the idea of applying dataflow approach into graph processing is extremely appealing for the following two reasons. First, as the execution and retirement of instructions only depend on the availability of input data in dataflow model, a high degree of parallelism can be therefore provided to relax the heavy dependency and serial semantic. Second, dataflow is guaranteed to make it possible to reduce the costs of branch misprediction by simultaneously executing all branches of a conditional instruction. Consequently, we make the preliminary attempt to develop the dataflow insight into a specialized graph accelerator. We believe that our work would open a wide range of opportunities to improve the performance of computation and memory access for large-scale graph processing.

It has been well recognized that network transmission constitutes a large portion of smartphone energy consumption, mainly because of the tail energy caused by cellular network interface. Traffic offloading has been proposed to reduce energy by letting a smartphone offload network traffic to its neighbors in vicinity via low-power direct connections (e.g., WiFi Direct or Bluetooth). Our experiments conducted in a realistic environment reveal that energy efficiency cannot be improved or even deteriorates without a carefully designed offloading strategy. In this paper, we propose a selective traffic offloading scheme implemented as a smartphone middleware in a software-defined fashion, which consists of a packet classifier and a traffic scheduler. Using a light-weight machine learning approach exploiting unique smartphone context information, the packet classifier identifies packets generated on the fly as offloadable or not with substantially improved efficiency and feasibility on resource limited smartphones compared to traditional approaches. Both testbed and simulation based experiments are conducted and the results show that our proposal always attains the superior performance on a number of comparison metrics.

Non-Volatile Memory (NVM) has recently emerged for its nonvolatility, high density and energy efficiency. Hybrid memory systems composed of DRAM and NVM have the best of both worlds, because NVM can offer larger capacity and have near-zero standby power consumption while DRAM provides higher performance. Many studies have advocated to use DRAM as a cache to NVM. However, it is still an open problem on how to manage the DRAM cache effectively and efficiently. In this paper, we propose a novel Hardware/Software Cooperative Caching (HSCC) mechanism that organizes NVM and DRAM in a flat address space while logically supporting a cache/memory hierarchy. HSCC maintains the NVM- to-DRAM address mapping and tracks the access counts of NVM pages through a moderate extension to page tables and TLBs. It significantly simplifies the hardware design and offers several optimization opportunities for cache management in software layers. We thus propose utility-based cache filtering policies to improve the efficiency of DRAM cache. Experimental results show that HSCC improves system performance by up to 9.6X (77.2% on average) and reduces energy consumption by 34.3% on average, compared to a hardware-assisted DRAM/NVM memory system. HSCC also presents 15.4% and 14.5% performance improvement against a flat- addressable memory architecture and a Row Buffer Locality Aware (RBLA) caching policy for hybrid memories, respectively.

Cloud gaming is promising to provide high-quality game services by outsourcing game execution to cloud so that users can access games via thin clients (e.g., smartphones or tablets). However, existing cloud gaming systems su er from low GPU utilization in the virtualized environment. Moreover, GPU resources are scheduled in units of virtual machines (VMs) and this kind of coarse-grained scheduling at the VM-level fails to fully exploit GPU processing capacity. In this paper, we present ShareRender, a cloud gaming sys- tem that o oads graphics workloads within VMs directly to GPUs, bypassing GPU virtualization. For each game running in a VM, ShareRender starts a graphics wrapper to intercept frame rendering requests and assign them to render agents responsible for frame rendering on GPUs. Thanks to the exible workload assignment among multiple render agents, ShareRender enables ne-grained resource sharing at the frame-level to signi cantly improve GPU utilization. Further more, we design an online algorithm to determine workload assignment and migration of render agents, which considers the tradeo between minimizing the number of active server and low agent migration cost. We conduct experiments on real deployment and trace-driven simulations to evaluate the performance of ShareRender under di erent system settings. The results show that ShareRender outperforms the existing video-streaming-based cloud gaming system by over 4 times.

For large-scale graph analysis on a single PC, asynchronous processing methods are known to converge more quickly than the synchronous approach, because of more efficient propagation of vertices state. However, current asynchronous methods are still very suboptimal in propagating state across different graph partitions. This presents a bottleneck for cross-partition state update and slows down the convergence of the processing task. To tackle this problem, we propose a new method, named the HotGraph, to faster graph processing by extracting a backbone structure, called hot graph, that spans all the partitions of the original graph. With this approach, most cross-partition state propagations in traditional solutions now take place within only a few hot graph partitions, thus removing the cross-partition bottleneck. We also develop a partition scheduling algorithm to maximize the hot graph's effectiveness by keeping it in memory and assigning it the highest priority for processing as much as possible. A forward and backward sweeping execution strategy is then proposed to further accelerate the convergence. Experimental results show that HotGraph can reduce the number of vertex state updates processed by 51.5 percent, compared with state-of-the-art schemes. Applying our optimizations further reduces this number by 72.6 percent and the execution time by 80.8 percent.

Social network analysis is used to extract features of human communities and proves to be very instrumental in a variety of scientific domains. The dataset of a social network is often so large that a cloud data analysis service, in which the computation is performed on a parallel platform in the could, becomes a good choice for researchers not experienced in parallel programming. In the cloud, a primary challenge to efficient data analysis is the computation and communication skew (i.e., load imbalance) among computers caused by humanity's group behavior (e.g., bandwagon effect). Traditional load balancing techniques either require significant effort to re-balance loads on the nodes, or cannot well cope with stragglers. In this paper, we propose a general straggler-aware execution approach, SAE, to support the analysis service in the cloud. It offers a novel computational decomposition method that factors straggling feature extraction processes into more fine-grained sub-processes, which are then distributed over clusters of computers for parallel execution. Experimental results show that SAE can speed up the analysis by up to 1.77 times compared with state-of-the-art solutions.

Big data analytics has attracted close attention from both industry and academic because of its great benefits in cost reduction and better decision making. As the fast growth of various global services, there is an increasing need for big data analytics across multiple data centers (DCs) located in different countries or regions. It asks for the support of a cross-DC data processing platform optimized for the geo-distributed computing environment. Although some recent efforts have been made for geo-distributed big data analytics, they cannot guarantee predictable job completion time, and would incur excessive traffic overthe inter-DC network that is a scarce resource shared by many applications. In this paper, we study to minimize the inter-DC traffic generated by MapReduce jobs targeting on geo-distributed big data, while providing predicted job completion time. To achieve this goal, we formulate an optimization problem by jointly considering input data movement and task placement. Furthermore, we guarantee predictable job completion time by applying the chance-constrained optimization technique, such that the MapReduce job can finish within a predefined job completion time with high probability. To evaluate the performance of our proposal, we conduct extensive simulations using real traces generated by a set of queries on Hive. The results show that our proposal can reduce 55 percent inter-DC traffic compared with centralized processing by aggregating all data to a single data center.

Cache pollution, by which weak-locality data unduly replaces strong-locality data, may notably degrade application performance in a shared-cache multicore machine. This paper presents NightWatch, a cache management subsystem that provides general, transparent and low-overhead pollution control to applications. NightWatch is based on the observation that data within the same memory chunk or chunks within the same allocation context often share similar locality property. NightWatch embodies this observation by online monitoring current cache locality to predict future behavior and restricting potential cache polluters proactively. We have integrated NightWatch into two popular allocators, tcmalloc and ptmalloc2. Experiments with SPEC CPU2006 show that NightWatch improves application performance by up to 45 percent (18 percent on average), with an average monitoring overhead of 0.57 percent (up to 3.02 percent).

The critical sections with the lock protection greatly limit the concurrency of multi-threaded applications. The prior lock elision based technique is presented to exploit the parallelism between critical sections accessing the disjoint shared data, but still fails to notice and expose a high degree of concurrency between critical sections that contend for the same shared data, i.e., conflicting critical sections (CCS). This paper focuses on exploiting the CCS parallelism. The key insight of this work is that, for each running CCS, a large proportion (>73.4% ) of parallelism between CCSs can be exploited as fully as possible by simply allowing the parallel execution of their first conflict-free code fragment at runtime. We therefore present BSOptimizer, a new microarchitecture, to perform the partial reversion integrated with a series of sophisticated hardware and software strategies for the CCS parallelization. We complement the off-the-shelf cache coherency protocol to perceive the conflict location of CCS, present a predictive checkpoint mechanism to register and predict the concerned conflict point in a lightweight and accurate fashion, and redefine the traditional mutual exclusive semantics with a binary relationship. With these collaborative techniques, each CCS can be scheduled in parallel. Our experimental results on a wide variety of real programs and PARSEC benchmarks show that, compared to the native execution and two state-of-the-art lock elision techniques (including SLE and SLR), BSOptmizer can dramatically improves the performance of programs with a slight (<;0.8% ) energy consumption and (<;3.9% ) extra runtime overhead. Our evaluation on a micro-benchmark with software based optimization also verifies that BSOptimizer can accurately exploit the CCS parallelism as promised.

Intra prediction in HEVC is much more complex compared to the one in H.264 because of the more diversifications of the block sizes and prediction modes. The state-of-the-art researches for its parallelization only focus on block-level methods, which only take very limited advantage of GPUs. It is still a big challenge to implement fine-grained parallelism on GPU in consideration of the HEVC branch instructions and the different prediction formulae. We present a novel pixel-level parallelism method for the intra prediction of HEVC based on GPU combined with mode-level parallelism. By unifying not only the prediction formulae between angular mode and planar mode but also a predictor array, an algorithm based on look-up table is proposed to greatly reduce branches and improve prediction efficiency. With the help of look-up table algorithm, each pixel in a block can obtain the offset of corresponding reference pixels and find the value in the unifying predictor array at the same time which makes it possible to predict all pixels in parallel regardless of their relative positions in the block. The experimental results show that the proposed algorithm outperforms previous work and can reduce encoding time effectively.

Sampled microarchitectural simulation of single-threaded applications is mature technology for over a decade now. Sampling multithreaded applications, on the other hand, is much more complicated. Not until very recently have researchers proposed solutions for sampled simulation of multithreaded applications. Time-Based Sampling (TBS) samples multithreaded application execution based on time—not instructions as is typically done for single-threaded applications—yielding estimates for a multithreaded application’s execution time. In this article, we revisit and analyze previously proposed TBS approaches (periodic and cantor fractal based sampling), and we obtain a number of novel and surprising insights, such as (i) accurately estimating fast-forwarding IPC , that is, performance in-between sampling units, is more important than accurately estimating sample IPC , that is, performance within the sampling units; (ii) fast-forwarding IPC estimation accuracy is determined by both the sampling unit distribution and how to use the sampling units to predict fast-forwarding IPC; and (iii) cantor sampling is more accurate at small sampling unit sizes, whereas periodic is more accurate at large sampling unit sizes. These insights lead to the development of Two-level Hybrid Sampling (THS) , a novel sampling methodology for multithreaded applications that combines periodic sampling’s accuracy at large time scales (i.e., uniformly selecting coarse-grain sampling units across the entire program execution) with cantor sampling’s accuracy at small time scales (i.e., the ability to accurately predict fast-forwarding IPC in-between small sampling units). The clustered occurrence of small sampling units under cantor sampling also enables shortened warmup and thus enhanced simulation speed. Overall, THS achieves an average absolute execution time prediction error of 4% while yielding an average simulation speedup of 40 × compared to detailed simulation, which is both more accurate and faster than the current state-of-the-art. Case studies illustrate THS’ ability to accurately predict relative performance differences across the design space.

In cloud gaming systems, the game program runs at servers in the cloud, while clients access game services by sending input events to the servers and receiving game scenes via video streaming. In this paradigm, servers are responsible for all performance-intensive operations, and thus suffer from poor scalability. An alternative paradigm is called graphics streaming, in which graphics commands and data are offloaded to the clients for local rendering, thereby mitigating the server's burden and allowing more concurrent game sessions. Unfortunately, this approach is bandwidth-consuming, due to large amounts of graphic commands and geometry data. In this paper, we present LiveRender, an open-source gaming system that remedies the problem by implementing a suite of bandwidth optimization techniques including intraframe compression, interframe compression, and caching, establishing what we call compressed graphics streaming. Experiments results show that the new approach is able to reduce bandwidth consumption by 52%-73% compared to raw graphics streaming, with no perceptible difference in video quality and reduced response delay. Compared to the video streaming approach, LiveRender achieves a traffic reduction of 40%-90% with even improved video quality and substantially smaller response delay, while enabling higher concurrency at the server.

The in-network data storage and retrieval are fundamental functions of sensor networks. Among many proposals, geographical hash table GHT is perhaps most appealing as it is very simple yet powerful with low communication cost, where the key is to correctly define the bounding box. It is envisioned that the skeleton has the power to facilitate computing a precise bounding box. In existing works, the focus has been on skeleton extraction algorithms targeting for 2D sensor networks, which usually deliver a 1-manifold skeleton consisting of 1D curves. It faces a set of non-trivial challenges when 3D sensor networks are considered, in order to properly extract the surface skeleton composed of a set of 2-manifolds and possibly 1D curves. In this paper, we study the problem of surface skeleton extraction in 3D sensor networks. We propose a scalable and distributed connectivity-based algorithm to extract the surface skeleton of 3D sensor networks. First, we propose a novel approach to identifying surface skeleton nodes by computing the extended feature nodes such that it is robust against boundary noise, etc. We then find the maximal independent set of the identified skeleton nodes and triangulate them to form a coarse-grained surface skeleton, followed by a refining process to generate the fine-grained surface skeleton. Furthermore, we design an efficient updating scheme to react to the network dynamics caused by node failure, insertion, etc. We also investigate the impact of boundary incompleteness and present a scheme to extract the surface skeleton under incomplete boundary. Finally, we apply the extracted surface skeleton to facilitate the design of data storage protocol and curve skeleton extraction algorithm. Extensive simulations show the robustness of the proposed algorithm to shape variation, node density, node distribution, communication radio model and boundary incompleteness, and its effectiveness for data storage and retrieval application with respect to load balancing.

Efficient in-network information storage and retrieval is of paramount importance to sensor networks and has attracted a large number of studies while most of them focus on 2D fields. In this paper, we propose novel Reeb graph based information storage and retrieval schemes for 3D sensor networks. The key is to extract the line-like skeleton from the Reeb graph of a network, based on which two distance-sensitive information storage and retrieval schemes are developed: one devoted to shorter retrieval path and the other devoted to more balanced load. Desirably, the proposed algorithms have no reliance on the geographic location or boundary information, and have no constraint on the network shape or communication graph. The extensive simulations also show their efficiency in terms of sensor storage load and retrieval path length.

Locks have been widely used as an effective synchronization mechanism among processes and threads. However, we observe that, a large number of false inter-thread dependencies (i.e., unnecessary lock contentions) exist during the program execution on multicore processors, incurring significant performance overhead. This paper presents a performance debugging framework, PERFPLAY, to facilitate the identification of unnecessary lock contentions and to guide programmers to improve the program performance by eliminating the unnecessary lock contentions. Since the performance debugging of unnecessary lock contentions is input-sensitive, we first identify the representative inputs for performance debugging. Next, PERFPLAY quantifies the performance impact of unnecessary lock contention code regions for each candidate input. Taking into account conflicting attribute of performance impact and input coverage in the real world, we finally make the tradeoff between performance impact and input coverage to recommend the optimal unnecessary lock contention code regions. Our final results on five real-world programs and PARSEC benchmarks demonstrate the significant performance overhead of unnecessary lock contentions, and the effectiveness of PERFPLAY in troubleshooting the target unnecessary lock contention code regions with the consideration of both performance impact and input coverage.

Locks have been widely used as an effective synchronization mechanism among processes and threads. However, we observe that a large number of false inter-thread dependencies (i.e., unnecessary lock contentions) exist during the program execution on multicore processors, thereby incurring significant performance overhead. This paper presents a performance debugging framework, PerfPlay, to facilitate a comprehensive and in-depth understanding of the performance impact of unnecessary lock contentions. The core technique of our debugging framework is trace replay. Specifically, PerfPlay records the program execution trace, on the basis of which the unnecessary lock contentions can be identified through trace analysis. We then propose a novel technique of trace transformation to transform these identified unnecessary lock contentions in the original trace into the correct pattern as a new trace free of unnecessary lock contentions. Through replaying both traces, PerfPlay can quantify the performance impact of unnecessary lock contentions. To demonstrate the effectiveness of our debugging framework, we study five real-world programs and PARSEC benchmarks. Our experimental results demonstrate the significant performance overhead of unnecessary lock contentions, and the effectiveness of PerfPlay in identifying the performance critical unnecessary lock contentions in real applications.

It has been recognized that cellular network interfaces are not energy efficient because of tail energy after each transmission. Although many research efforts have been made to reduce tail energy, they ignore the dynamic of link quality caused by user mobility or network congestion, which would lead to limited improvement without quality-of-experience guarantee. In this paper, we study to minimize energy consumption of the cellular network interface with a sequence of download/upload requests. Given accurate estimation of achievable link rate, we design a dynamic-programming (DP) based algorithm to obtain the optimal solution. Without the knowledge of dynamic link quality and future requests, an online algorithm is proposed to approximate the optimal solution. Finally, we conduct extensive simulations using real traces to evaluate the performance of our proposals, and the results show that 29% energy can be saved by using our algorithm under typical network settings.

Warm up is a crucial issue in sampled micro architectural simulation to avoid performance bias by constructing accurate states for micro-architectural structures before each sampling unit. Not until very recently have researchers proposed Time-Based Sampling (TBS) for the sampled simulation of multi-threaded applications. However, warm up in TBS is challenging and complicated, because (i) full functional warm up in TBS causes very high overhead, limiting overall simulation speed, (ii) traditional adaptive functional warm up for sampling single-threaded applications cannot be readily applied to TBS, and (iii) check pointing is inflexible (even invalid) due to the huge storage requirements and the variations across different runs for multi-threaded applications. In this work, we propose Shorter On-Line (SOL) warm up, which employs a two-stage strategy, using 'prime' warm up in the first stage, and an extended 'No-State-Loss (NSL)' method in the second stage. SOL is a single-pass, on-line warm up technique that addresses the warm up challenges posed in TBS in parallel simulators. SOL is highly accurate and efficient, providing a good trade-off between simulation accuracy and speed, and is easily deployed to different TBS techniques. For the PARSEC benchmarks on a simulated 8-core system, two state-of-the-art TBS techniques with SOL warm up provide a 7.2× and 37× simulation speedup over detailed simulation, respectively, compared to 3.1× and 4.5× under full warm up. SOL sacrifices only 0.3% in absolute execution time prediction accuracy on average.

Code offloading has been proposed to improve the performance and energy-efficiency of mobile devices by sending heavy computation tasks to resourceful cloud, instead of executing all tasks on local mobile devices. Unfortunately, current code offloading techniques are not efficient enough because of high communication cost. In this paper, we propose a novel code offloading strategy with cellular traffic aggregation that aggregates offloaded codes to several mobile devices before sending them to cloud, which can significantly reduce tail energy effect. With the objective of minimizing the total cost of computation and communication, we propose an optimization framework by jointly considering code partition and traffic aggregation. Due to the hardness of this problem, we design an efficient heuristic algorithm and evaluate its performance via extensive simulations. Simulation results demonstrate that the proposed algorithm significantly outperforms existing schemes.

The key technology of next generation network, IP Multimedia Subsystem (IMS), lacks of scalability, reliability and load balancing ability because of its traditional centralized control architecture. Using P2P (peer-to-peer) technology to transform architecture of the traditional IMS core network is a feasible solution, while the function separation and independent operation requirements of IMS network elements in telecommunication career level can not be met. In this paper, we present a multi-domain and multi-overlay framework of P2P IMS core network based on cloud infrastructure. In this framework, various network elements (NEs) are divided into different domains and overlay of the core network. Experimental results indicate that this framework can be deployed in the actual operating core network and provides core functions. Besides, the service capacity grows linearly as the number of serving nodes increases. The load can be automatically distributed on each element in a balanced way and the maximum load difference between elements is no more than 16%. Moreover, the response time of redesigned procedures is much smaller than the original procedures.

In cloud computing, companies usually use high-end storage systems to guarantee the I/O performance of virtual machines (VM). These storage systems cost a lot of energy for their high performance. In this paper, we propose an EEVS, a deduplication-based energy efficiency storage system for VM storage. We firstly investigate some VM image files with general operating systems. With the analysis result, we find there are many redundant data blocks that bring extra energy cost VM storage. Therefore, in the EEVS, we design an online-deduplication mechanism to reduce these redundant data without service interruption, while traditional deduplication technology is used for offline backup. Based on the system design, we implement an EEVS with the existing cloud platform. Since this mechanism needs considerable computing resources, we design a deduplication selection algorithm such that the storage energy consumption is minimized for a given set of VMs with limited resources for deduplication. Experiment results in a para-virtualization environments of the EEVS show that energy consumption is reduced by even up to 66% with negligible performance degradation.

Summary The nonuniform memory access (NUMA) architecture has been used extensively in data centers. Most of the previous works used single‐threaded multiprogrammed workloads to study the performance of NUMA systems, which mainly focus on two classes of problems: resource contention and data locality. However, when running multi‐threaded programs on NUMA systems, the critical thread of these programs significantly influences the system performance and brings new challenges that are different from those in a single‐threaded situation. In particular, an additional scheduling scheme is desired to avoid the performance degradation caused by the critical thread of multi‐threaded programs running on NUMA systems. This work presents a scheduler,Symmetrical Scheduler, which successfully solves the lagging problem by balancing the number of the costly remote shared data accesses for threads on NUMA systems. To the best of our knowledge, little work has been conducted to examine the performance impacted by the critical thread of multi‐threaded programs on NUMA systems. By running thePARSECbenchmark on such systems, our methodology can improve the program performance by a factor of 6% on average and achieve maximally 25.3% improvement compared with Linux kernel scheduling mechanism. Copyright © 2015 John Wiley & Sons, Ltd.

In sensor networks, skeleton extraction has emerged as an appealing approach to support many applications such as load-balanced routing and location-free segmentation. While significant advances have been made for 2D cases, so far skeleton extraction for 3D sensor networks has not been thoroughly studied. In this paper, we conduct the first work of a unified framework providing a connectivity-based and distributed solution forline-likeskeleton extraction in both 2D and 3D sensor networks. We highlight its practice as: 1) it has linear time/message complexity; 2) it provides reasonable skeleton results when the network has low node density; 3) the obtained skeletons are robust to shape variations, node densities, boundary noise and communication radio model. In addition, to confirm the effectiveness of the line-like skeleton, a 3D routing scheme is derived based on the extracted skeleton, which achieves balanced traffic load, guaranteed delivery, as well as low stretch factor.

Time-stepped applications are pervasive in scientific computing domain but perform poorly in the cloud because these applications execute in discrete time-step or tick and use logical synchronization barriers at tick boundaries to ensure correctness. As a result, the accumulated computational skew and communication skew that were unsolved in each tick can slow down time-stepped applications significantly. However, the existing solutions have focused only on the skew in each tick and thus cannot resist the accumulation of skew. To fill in this gap, an efficient approach to resisting the accumulation of skew is proposed in this paper via fully exploiting parallelism among ticks. This new approach allows the user to decompose much computational part (also called asynchronous part) of the processing for an object, into several asynchronous sub-processes which are dependent on one data object. Each sub-process from different ticks can then proceed in advance using the idle time whenever the needed data object is available, redressing the negative effects caused by accumulated unsolved computational and communication skew. To efficiently support such an approach, a data-centric programming model and also a runtime system, namely AsyTick, coupled with an ad hoc scheduler are developed. Experimental results show that the proposed approach can improve the performance of time-stepped applications over a state-of-the-art computational skew-resistant approach up to 2.53 times.

To minimize the amount of data-shuffling I/O that occurs between the pipeline stages of a distributed data-parallel program, its procedural code must be optimized with full awareness of the pipeline that it executes in. Unfortunately, neither pipeline optimizers nor traditional compilers examine both the pipeline and procedural code of a data-parallel program so programmers must either hand-optimize their program across pipeline stages or live with poor performance. To resolve this tension between performance and programmability, this paper describes PeriSCOPE, which automatically optimizes a data-parallel program's procedural code in the context of data flow that is reconstructed from the program's pipeline topology. Such optimizations eliminate unnecessary code and data, perform early data filtering, and calculate small derived values (e.g., predicates) earlier in the pipeline, so that less data - sometimes much less data - is transferred between pipeline stages. PeriSCOPE further leverages symbolic execution to enlarge the scope of such optimizations by eliminating dead code. We describe how PeriSCOPE is implemented and evaluate its effectiveness on real production jobs.

In virtualization environments, static memory allocation for virtual machines (VMs) can lead to severe service level agreement (SLA) violations or inefficient use of memory. Dynamic memory allocation mechanisms such as ballooning and memory hotplug were proposed to handle the dynamics of memory demands. However, these mechanisms so far have not been quantitatively or comparatively studied. In this paper, we first develop a runtime system called U-tube, which provides a framework to adopt memory hotplug or ballooning for dynamic memory allocation. We then implement fine-grained memory hotplug in Xen. We demonstrate the effectiveness of U-tube for dynamic memory management through two case studies: dynamic memory balancing and memory overcommitment. With these two case studies, we make a quantitative comparison between memory hotplug and ballooning. The experiments show that there is no absolute winner for different scenarios. Our findings can be very useful for practitioners to choose the suitable dynamic memory management techniques in different scenarios.

WiFi and cellular networks are pervasively provided for mobile Internet access. Although most existing mobile devices are equipped with both WiFi and cellular network interfaces, concurrent data transmissions over these interfaces for improved throughput are not provided. In this paper, a bandwidth aggregation prototype, named Application Layer Protocol based Aggregation (ALP-A), is developed for easy use by simply installing an application in mobile devices without modifying their operating systems or drivers. It provides desired quality-of-experience (QoE), i.e., acceptable response delay to users, learned from application characteristics and users behaviors. Furthermore, we propose an online algorithm of traffic scheduling over WiFi and cellular interfaces with the objective of minimizing energy consumption while guaranteeing the QoE. Over the prototype implemented on Andriod-based smartphones, we conduct extensive experiments to show that ALP-A outperforms existing schemes significantly.

Large-scale behavioral simulations are widely used to study real-world multi-agent systems. Such programs normally run in discrete time-steps or ticks, with simulated space decomposed into domains that are distributed over a set of workers to achieve parallelism. A distinguishing feature of behavioral simulations is their frequent and high-volume group migration, the phenomenon in which simulated objects traverse domains in groups at massive scale in each tick. This results in continual and significant load imbalance among domains. To tackle this problem, traditional load balancing approaches either require excessive load re-profiling and redistribution, which lead to high computation/communication costs, or perform poorly because their statically partitioned data domains cannot reflect load changes brought by group migration. In this paper, we propose an effective and low-cost load balancing scheme, named Inc-part, based on a key observation that an object is unlikely to move a long distance (across many domains) within a single tick. This localized mobility property allows one to efficiently estimate the load of a dynamic domain incrementally, based on merely the load changes occurring in its neighborhood. The domains experiencing significant load changes are then partitioned or merged, and redistributed to redress load imbalance among the workers. Experiments on a 64-node (1,024-core) platform show that Inc-part can attain excellent load balance with dramatically lowered costs compared to state-of-the-art solutions.

As multi-core platforms with hundreds or even more quantities of cores are popular, system optimization issues, including lock contentions, start to puzzle programmers who work on multi-core platforms. Locks are more convenient and clear than lock-free operations (for example, transactional memory) for multi-core programmers. However, lock contention has been recognized as a typical impediment to the performance of shared-memory parallel programs. This paper mainly discusses two important reasons that cause lock contention, including large critical sections and frequent lock requests. For current solutions, it is hard for programmers to find the locations of large critical sections and good scheme to reduce lock contentions on hot critical sections. This paper proposes FFlocker, a series of runtime solutions that reduce lock contention caused by the two issues. FFlocker includes a profiling algorithm to find the locations of large critical sections. Based on the profiling scheme, it binds the threads acquiring the same locks onto the same core. We evaluate our techniques with three benchmarks. The results show that FFlocker offers better performance than Function Flow and OpenMP.

Deterministic multithreading (DMT) system is well-known to eliminate the harmful program behaviors caused by nondeterminism, i.e., always proceeding the program execution into the same thread schedule for the same given input. To achieve this goal, two kinds of schedules are enforced by existing DMT systems. 1) A mem-based schedule ensures the determinism with the total order of the shared memory accesses, and 2) A sync-based schedule makes it by only enforcing the total order of the synchronization operations. Mem-schedule achieves full determinism but suffers from prohibitive overhead; while sync-schedule mitigates this overhead but cannot ensure the determinism for the race schedules, i.e., part determinism. Much recent research is devoted to the hybrid schedule combining the determinism of mem-schedule and efficiency of sync-schedule. However, they suffer from the practicability and scalability problems due to the defects of their technical characteristics, such as trace collection in advance and huge schedule memoization. To address the above problem, this paper proposes esDMT, an efficient and scalable DMT system using a new technique of memory isolation. It can improve the efficiency by proceeding the execution of each thread in parallel within its private virtual memory, and defers the determinism guarantee by updating private memory into shared memory in a deterministic order according to deterministic lock algorithm, thus further reducing the overhead of inter-thread waiting. In contrast to the previous hybrid work avoiding the nondeterminism of race schedules offline based on the enormous historical records, our key insight is to eliminate the nondeterminism of race schedules online at runtime. Our experimental results on PARSEC benchmarks show that esDMT eliminates the nondeterminism successfully, almost gains the same performance as the sync-schedule (with <;18% slowdown compared with pthread library at most), and manifests good scalability on an 8-core machine.

In cloud gaming systems, the game program runs at servers in the cloud, while clients access game services by sending input events to the servers and receiving game scenes via video streaming. In this paradigm, servers are responsible for all performance-intensive operations, and thus suffer from poor scalability. An alternative paradigm is called graphics streaming, in which graphics commands and data are offloaded to the clients for local rendering, thereby mitigating the server's burden and allowing more concurrent game sessions. Unfortunately, this approach is bandwidth consuming, due to large amounts of graphic commands and geometry data. In this paper, we present LiveRender, an open source gaming system that remedies the problem by implementing a suite of bandwidth optimization techniques including intra-frame compression, inter-frame compression, and caching, establishing what we call compressed graphics streaming. Experiments results show that the new approach is able to reduce bandwidth consumption by 52-73% compared to raw graphics streaming, with no perceptible difference in video quality and reduced response delay. Compared with the video streaming approach, LiveRender achieves a traffic reduction of 40-90% with even improved video quality and substantially smaller response delay, while enabling higher concurrency at the server.

In-network data storage and retrieval are fundamental functions of sensor networks. Among many proposals, geographical hash table (GHT) is perhaps most appealing as it is very simple yet powerful with low communication cost, where the key is to correctly define the bounding box. It is envisioned that the skeleton has the power to facilitate computing a precise bounding box. In existing works, the focus has been on skeleton extraction algorithms targeting for 2D sensor networks, which usually delivers a 1-manifold skeleton consisting of 1D curves. It faces a set of non-trivial challenges when 3D sensor networks are considered, in order to properly extract the surface skeleton composed of a set of 2-manifolds and possibly 1D curves.

IP Multimedia Subsystem (IMS) has been accepted as the core control platform by 3GPP. It has been recognized as the vision beyond GSM for the Next Generation Network (NGN). The IMS framework delivers IP multimedia to mobile users through Session Initiation Protocol (SIP) and supports heterogeneous networks access. In this paper, we propose a virtualization-based cloud platform for the IMS core network, with a novel load-balance and disaster recovery policy. Experimental results indicate that the proposed mechanism improves system performance by dynamic allocating resources according to current load. The proposed cloud infrastructure is able to recover from a disaster in seconds by using live migration of virtual machines.

Modern Cloud Service Providers (CSPs) equip their Datacenter Power Supply System (DPSS) with multisources to mitigate power cost, carbon emission, and power outage: (1) multi-markets grid with time-varying energy prices, (2) finite capacity of Uninterrupted Power Supply (UPS), and (3) certain volumes of intermittent renewable energy. With the presence of uncertain renewable sources and datacenter power demand, CSPs have a critical challenge: how to design systematical online control policies that best utilize different characteristics of multisources in a complementary manner to deliver reliable energy to datacenters while minimizing DPSS operation cost. Based on a stochastic optimization model that captures characteristics of DPSS, we apply two-stage Lyapunov optimization to design and analyze an online DPSS control algorithm (OnDPSS). OnDPSS makes decisions on fully utilizing renewable energy, two-timescales power purchasing, and UPS charging/discharging without requiring substantial statistics of system dynamics. Our mathematical analyses and one-month trace-driven simulations have demonstrated both the optimality (in terms of tradeoff between minimization of DPSS operational cost and constraint satisfaction on datacenter availability and UPS lifetime) and system stability (in terms of robustness to time-varying power demand and supply) achieved by OnDPSS algorithm.

Mobile devices with multihoming capabilities have gained large-scale popularity in recent years. However, these network interfaces cannot be fully utilized in most applications. In this paper, we propose a concurrent transmission method that allows mobile applications to fully use multiple interfaces simultaneously in a transparent manner. Using this method, applications benefit from network enhancement, including minimum transmission delay and maximum throughput. Our experimental results show that we achieve a bandwidth aggregation efficiency of 90% on throughput and reduce 28% transmission delay. In addition, we analyze the lowest power consumption according to our model.

Mobile devices have already been widely used to access the Web. However, because most available web pages are designed for desktop PC, it is inconvenient to browse these large web pages on a mobile device with a small screen. In this paper, we propose a new web page transforming scheme to facilitate navigation on a small-form-factor device based on cloud computing. Different with other existing schemes, our approach is based on page segmentation and template-rendering. The semantic structure of a web page is extracted by DOM (Document Object Model) analyzing. Such semantic structure is hierarchical. Each node is corresponded to a block area of one web page and is in charge of reconstructing the whole web page. According to different content styles, the template-rendering scheme generates different display modes. Experimental results show good experience.

Mobile video editing systems need efficient streaming transmission and interactive operations. Rather than using a specialized protocol and stream format, the video editing system makes use of a generic mechanism based on chunks in the cloud computing environment. Chunks are in fixed-size and contains a mixture of scalar data and references to other chunks. Chunks allow programmers to expose large, but fine-grained, data structures over the network. The video editing system organizes video clips with simple data types including linked lists and search trees, allowing a client to retrieve. The mobile video editing system supports resource adaptive play-back and "live" streaming of real-time video as well as fast, frame-accurate seeking, bandwidth-efficient high-speed play-back, and compilation of editing decisions from a set of clips. All the editing functions are completed in the cloud center and the editing results are showed on the mobile devices. Evaluations indicate that our system uses less bandwidth than HTTP Live Streaming while providing better support for editing primitives.

Applications in the cloud computing era have the emergent requirement of fast I/O support. Compared with a hard drive disk, a solid state disk (SSD) has low delay, low energy consumption, high throughput and other advantages. However, the semantics of an SSD cannot be recognized by current virtual machine monitors. The trim instruction, which plays an important role in space management of an SSD, cannot be passed to the underlying SSD device in a virtualized environment. So, how to bridge the semantics gap between the application layer and virtualization layer for SSD devices should be an important problem. We propose Vtrim to solve the above problem in this paper. Vtrim monitors the operations in the virtual machine and sends the SSD semantics to the Domain 0 immediately. And then the semantics are translated into the operations of Domain 0, which can trigger the SSD's local instructions. To improve the write performance in multiple guest operating systems, we set a Vtrim cache to buffer all instructions from the guests and flush them into an SSD in a well-scheduled way. Experiment results in the para-virtualization environments with Vtrim show that the random write performance is improved by even up to 100% and the average response time is reduced by up to 40%.

SUMMARY Beyond the traditional BitTorrent, a new genre of peer‐to‐peer communications protocol for worldwide file sharing is rapidly evolving towards private BitTorrent (PT). In recent years, a proliferation of PT communities have emerged. To enhance the user experience, account‐based share‐ratio enforcement (SRE) has been developed and widely adopted. Whereas existing studies mainly take SRE as an incentive, we discover that it also plays a critical role in selecting and filtering users. In addition to SRE, a rich set of user management rules, such as registration management, banning policies, and user caste system, are also studied in this paper. This includes to explore their effects on user behavior, download performance, content availability, and system scalability. The measurement results presented in this paper are based on large‐scale experiments conducted over six representative PT sites for over a year. We find that the stricter registration will lead to fewer new users, resulting in a scalability problem, which is critical for the PT communities because the download performance and content availability depend on not only the contribution of users but also the population of the community. Our measurement and analysis pose a direction for the design of new incentive mechanisms that take the difficulty of enrollment into the consideration.Copyright © 2012 John Wiley & Sons, Ltd.

Computer architects rely heavily on microarchitecture simulation to evaluate design alternatives. Unfortunately, cycle-accurate simulation is extremely slow, being at least 4 to 6 orders of magnitude slower than real hardware. This longstanding problem is further exacerbated in the multi-/many-core era, because single-threaded simulation performance has not improved much, while the design space has expanded substantially. Parallel simulation is a promising approach, yet does not completely solve the simulation challenge. Furthermore, existing sampling techniques, which are widely used for single-threaded applications, do not readily apply to multithreaded applications as thread interaction and synchronization must now be taken into account. This work presents PCantorSim , a novel Cantor set (a classic fractal)--based sampling scheme to accelerate parallel simulation of multithreaded applications. Through the use of the proposed methodology, only less than 5% of an application's execution time is simulated in detail. We have implemented our approach in Sniper (a parallel multicore simulator) and evaluated it by running the PARSEC benchmarks on a simulated 8-core system. The results show that PCantorSim increases simulation speed over detailed parallel simulation by a factor of 20×, on average, with an average absolute execution time prediction error of 5.3%.

In a traditional virtualized cloud environment, using asynchronous I/O in the guest file system and synchronous I/O in the host file system to handle an asynchronous user disk write exhibits several drawbacks, such as performance disturbance among different guests and consistency maintenance across guest failures. To improve these issues, this paper introduces a novel disk I/O model for virtualized cloud system called HypeGear, where the guest file system uses synchronous operations to deal with the guest write request and the host file system performs asynchronous operations to write the data to the hard disk. A prototype system is implemented on the Xen hypervisor and our experimental results verify that this new model has many advantages over the conventional asynchronous-synchronous model. We also evaluate the overhead of asynchronous I/O at host, which is brought by our new model. The result demonstrates that it enforces little cost on host layer.

Gaming services are attractive for Internet users. How to broadcast live gaming services to large-scale Internet users is still a big problem. Traditional schemes, based on Peer-to-Peer (P2P) live-streaming and based on TV shows, have poor user experiences (good graphic quality with high resolution) and need big bandwidth or TV set support. In order to avoid network congestion, a small number of solutions propose an alternative approach based on game data content instead of video content to provide game live services. At present, all of them who use client/server framework do not emphasize the design of system architecture, so the number of users is constrained and the system is hard to expand. In this paper, we introduce PKTV, a P2P game battle observing system, which is now optimized specially for War craft 3. PKTV system broadcasts game data content to reduce bandwidth overhead, maintains a P2P overlay for each gaming channel and uses a reliable UDP protocol to break the limitation of the TCP connections, decentralizes servers to enhance system's availability and scalability. Furthermore, tests and simulations show that PKTV also have robust functionality and good performance: low-latency, low bandwidth consumption and very considerable bandwidth savings for servers.

Server consolidation using virtualization technologies allow cloud-scale datacenters to improve resource utilization and energy efficiency. However, most existing consolidation strategies solely focused on balancing the tradeoff between service-level-agreements (SLAs) desired by cloud applications and energy costs consumed by hosting servers. With the presence of fluctuating workloads in datacenters, the lifetime and reliability of servers under dynamic power-aware consolidation could be adversely impacted by repeated on-off thermal cycles, wear-and-tear and temperature rise. In this paper, we propose a Reliability-Aware server Consolidation stratEgy, named RACE, to address when and how to perform energy-efficient server consolidation in a reliability-friendly and profitable way. The focus is on the characterization and analysis of this problem as a multi-objective optimization, by developing an utility model that unifies multiple constraints on performance SLAs, reliability factors, and energy costs in a holistic manner. An improved grouping genetic algorithm is proposed to search the global optimal solution, which takes advantage of a collection of reliability-aware resource buffering, and virtual machines-to-servers re-mapping heuristics for generating good initial solutions and improving the convergence rate. Extensive simulations are conducted to validate the effectiveness, scalability and overhead of RACE in improving the overall utility of datacenters while avoiding unprofitable consolidation in the long term - compared with pMapper and PADD strategies for server consolidation.

Transactional memory (TM) is a parallel programming concept which reduces challenges in parallel programming. Existing distributed transactional memory system consumes too much bandwidth and brings high latency. In this work, we present Transactional Memory System for Cluster (Clustm), a generalized and scalable distributed transactional memory system. Our system addresses several open issues posed by this domain, including transactional memory consistency protocol, cache consistency protocol, and the distribution strategy of the metadata of shared data across the cluster. Then, we evaluate our design with several workloads, and the results demonstrate outstanding performance.

Peer-to-peer (P2P) live video streaming systems have recently received substantial attention, with commercial deployment gaining increased popularity in the internet. It is evident from our practical experiences with real-world systems that, it is not uncommon for hundreds of thousands of users to choose to join a program in the first few minutes of a live broadcast. Such a severe flash crowd phenomenon in live streaming poses significant challenges in the system design. In this paper, for the first time, we develop a mathematical model to: 1) capture the fundamental relationship between time and scale in P2P live streaming systems under a flash crowd, and 2) explore the design principle of population control to alleviate the impact of the flash crowd. We carry out rigorous analysis that brings forth an in-depth understanding on effects of the gossip protocol and peer dynamics. In particular, we demonstrate that there exists an upper bound on the system scale with respect to a time constraint. By trading peer startup delays in the initial stage of a flash crowd for system scale, we design a simple and flexible population control framework that can alleviate the flash crowd without the requirement of otherwise costly server deployment.

Live migration of virtual machine (VM) provides a significant benefit for virtual server mobility without disrupting service. It is widely used for system management in virtualized data centers. However, migration costs may vary significantly for different workloads due to the variety of VM configurations and workload characteristics. To take into account the migration overhead in migration decision-making, we investigate design methodologies to quantitatively predict the migration performance and energy cost. We thoroughly analyze the key parameters that affect the migration cost from theory to practice. We construct two application-oblivious models for the cost prediction by using learned knowledge about the workloads at the hypervisor (also called VMM) level. This should be the first kind of work to estimate VM live migration cost in terms of both performance and energy in a quantitative approach. We evaluate the models using five representative workloads on a Xen virtualized environment. Experimental results show that the refined model yields higher than 90% prediction accuracy in comparison with measured cost. Model-guided decisions can significantly reduce the migration cost by more than 72.9% at an energy saving of 73.6%.

Live migration of virtual machines (VM) across physical hosts provides a significant new benefit for administrators of data centers and clusters. Previous memory-to-memory approaches demonstrate the effectiveness of live VM migration in local area networks (LAN), but they would cause a long period of downtime in a wide area network (WAN) environment. This paper describes the design and implementation of a novel approach, namely, CR/TR-Motion, which adopts checkpointing/recovery and trace/replay technologies to provide fast, transparent VM migration for both LAN and WAN environments. With execution trace logged on the source host, a synchronization algorithm is performed to orchestrate the running source and target VMs until they reach a consistent state. CR/TR-Motion can greatly reduce the migration downtime and network bandwidth consumption. Experimental results show that the approach can drastically reduce migration overheads compared with memory-to-memory approach in a LAN: up to 72.4 percent on application observed downtime, up to 31.5 percent on total migration time, and up to 95.9 percent on the data to synchronize the VM state. The application performance overhead due to migration is kept within 8.54 percent on average. The results also show that for a variety of workloads migrated across WANs, the migration downtime is less than 300 milliseconds.

Abstract Virtualization is being widely used now as an emerging trend. Rapid improvements in network bandwidth, ubiquitous security hazards and high total cost of ownership of personal computers have created a growing market for desktop virtualization. Much like server virtualization, virtualizing desktops involves separating the physical location of a client device from its logical interface. But, the performance and usability of some traditional desktop frameworks do not satisfy end‐users. Other solutions, including WebOS, which needs to rebuild all daily‐used applications into Client/Server mode, cannot be easily accepted by people in a short time. We present LVD, a system that combines the virtualization technology and inexpensive personal computers (PCs) to realize a lightweight virtual desktop system. Comparing to the previous desktop systems, LVD builds an integrated novel desktop environment, which can support the backup, mobility, suspending and resuming of per‐user's working environment, and support synchronous using of incompatible applications on different platforms and achieves great saving in power consumption. We have implemented LVD in a cluster with Xen and compared its performance against widely used commercial approaches, including Microsoft RDP, Citrix MetaFrameXP and Sun Ray. Experimental results demonstrate that LVD is effective in performing the functions while imposing little overhead. Copyright © 2009 John Wiley & Sons, Ltd.

Virtual desktop environment (VDE) provides a real virtual working environment in which users could personally customize and update the application list from application template libraries. The heterogeneous applications actually running in the remote application servers could cooperatively communicate with each other. It is a thin client approach to mobility in which the perfect combination of VM technology and DFS technology are the keys to the rapid seamless resuming of the usage scenarios. Usage scenarios are incrementally suspended including the user's documents and the running applications. The usage data stored in data center provides a unified view for the users through historical scenario manager and ensures the data's security and reliability at the same time. This paper explores the building policy of a real virtual working environment and the suspending/resuming policy of usage scenarios. Experiments demonstrate and evaluate VDE's efficiency and effectiveness.

Live migration of virtual machines (VM) across distinct physical hosts provides a significant new benefit for administrators of data centers and clusters. Previous migration schemes focused on transferring the runtime memory state of the VM. Those approaches employed memory pre-copy algorithm to synchronize the migrating VM states, which make VM live migration cost much network traffic and application downtime, especially for memory intensive workloads. This paper describes the design and implementation of a novel approach CR/TR-Motion that adopts checkpointing/recovery and trace/replay technology to provide fast, transparent VM migration. With execution trace logged on the source host, a synchronization algorithm is performed to orchestrate the running source and target VM until they get a consistent state. We also give a formalized characterization about the migration evaluation metrics and make a mathematical analysis about our algorithm. Our scheme can greatly reduce the migration downtime and network bandwidth consumption. Experimental measurements show that our approach can drastically reduce migration overheads compared with pre-copy algorithm: up to 72.4% on application observed downtime, up to 31.5% on total migration time and up to 95.9% on the data to synchronize the VM state, while the application performance overhead due to migration is less than 8.54% on average.

Operating system debugging and system security are two important issues which are attracted more and more attentions. However, traditional solutions of software debugging can not make an integrated replay towards the status of operating system. Moreover, most intrusion detection methods all depend on the operating system excessively, but operating system ex-poses so many interfaces to outside that it can not ensure its own security and is attacked vulnerably. Therefore, a para-virtualized model based full system replay is developed in this paper. According to the para-virtualized device model pro-vided by Xen, this system captures the non-deterministic events in the target operating system through a real-time monitoring module, and saves the data and time point of these events occurrence as log file elaborately. Using these data, we can make a full-system replay to the target operating system accurately. Compared with the previous replay systems, this system is more efficient and has two prominent advantages: no need to modify the target operating system, and no need to reboot the target operating system before executing replay.

During the development of a distributed application, programmers usually involve many programs. These programs have different IP addresses and different ports. Sometimes, they even have a same port. For instance, in P2P environment, peers usually use the same port to communicate with each other. We often need tens of computers to develop such a distributed application. Unfortunately, not each one owns as many computers as the developing plan needs. Even if he has enough computers, it is difficult for him to manage these computers efficiently. We propose VirtualNet, a middleware, to solve this problem. When using this virtual network, users can start different programs or processes on it as if in a real distributed environment. Every application that runs on such middleware regards it running on an exclusive computer. Since all the applications are started by the middleware and run on the same computer, it is easy to control them and collect logs for debugging. Moreover, after being tested in such a virtual network and running through the TCP/IP stack, the applications can be immediately deployed in a real environment without any modifications.

Traversing Network Address Translation (NAT) for Peer-to-Peer (P2P) communication has become a hot topic recently. Compared to UDP, establishing TCP connections for hosts behind different NATs is more complex. Thus, many TCP-based applications do not address TCP traversal through NATs. Some solutions suggest using delegates to relay all communications, or tunneling TCP over UDP. However, they require a big reform to network architecture, or using a non-standard TCP/IP stack. In this paper, we present a novel idea called TCPBridge. TCPBridge converts TCP traversal to UDP traversal without modifying any binaries of the TCP-based applications. Our design can be integrated with those P2P applications which have not solved TCP traversal problem, and extends them to support direct communications between NAT hosts. It deals with the problem of TCP traversal, so as to improve the usability of applications. We have implemented TCPBridge in several existing P2P systems. Statistics prove that TCPBridge is scalable and robust, and we believe it will benefit many other existing P2P applications.

The concept of green computing has attracted much attention recently in cluster computing. However, previous local approaches focused on saving the energy cost of the components in a single workstation without a global vision on the whole cluster, so it achieved undesirable power reduction effect. Other cluster-wide energy saving techniques could only be applied to homogeneous workstations and specific applications. This paper describes the design and implementation of a novel approach that uses live migration of virtual machines to transfer load among the nodes on a multilayer ring-based overlay. This scheme can reduce the power consumption greatly by regarding all the cluster nodes as a whole. Plus, it can be applied to both the homogeneous and heterogeneous servers. Experimental measurements show that the new method can reduce the power consumption by 74.8% over base at most with certain adjustably acceptable overhead. The effectiveness and performance insights are also analytically verified.

Large-scale stream media delivery over Internet is one hot and hard problem. Three main solutions have been developed for this purpose. Content delivery network (CDN) can provide high quality streaming service with high cost. Server-based proxies are cost-effective but not scalable due to the limited proxy capacity and its centralized control. Peer-to-peer (P2P) network is scalable but does not guarantee high quality streaming service due to its self-restrained characteristic. This paper proposes a new chunk-based scalable and reliable proxy scheme for P2P network. Clients are self-organized in unstructured P2P VoD system GridCast and requests for media contents that are not found in P2P overlay from proxy servers. This scheme can address the limitations of server-based proxy model and client-based P2P model. The proposed scheme is evaluated by trace-driven simulations from logs collected in GridCast. The results show that the approach proposed significantly improves the quality of media streaming and the system scalability.

Virtualization technology has attracted much attention in recent years. This paper describes the vision and mission of ChinaV, which is the national fundamental research program for virtualization technology in China. Furthermore, related topics about single host virtualization, multiple VM management schemes and desktop virtualization will be introduced. We first describe a remote memory virtualization scheme and a VCPU management scheme for efficient use of physical resource. Then we describe a novel live VM migration approach based on deterministic replay with execution trace. Multiple VM management schemes are also introduced for multi-VM virtualization. In desktop virtualization field, we present the LVD, a system that combines the virtualization technology and inexpensive personal computers to realize a lightweight virtual desktop system. All of those schemes and systems are good practices of virtualization solution and they have become a strong foundation of our future work.

There has been significant progress in the development and deployment of peer-to-peer (P2P) live video streaming systems. However, there has been little study on the security aspect in such systems. Our prior experiences in Anysee exhibit that existing systems are largely vulnerable to intermediate attacks, in which the content pollution is a common attack that can significantly reduce the content availability, and consequently impair the playback quality. This paper carries out a formal analysis of content pollution and discusses its implications in P2P live video streaming systems. Specifically, we establish a probabilistic model to capture the progress of content pollution. We verify the model using a real implementation based on Anysee system; we evaluate the content pollution effect through extensive simulations. We demonstrate that (1) the number of polluted peers can grow exponentially, similar to random scanning worms. This is vital that with 1% polluters, the overall system can be compromised within minutes; (2) the effective bandwidth utilization can be sharply decreased due to the transmission of polluted packets; (3) Augmenting the number of polluters does not imply a faster progress of content pollution, in which the most influential factors are the peer degree and access bandwidth. We further examine several techniques and demonstrate that a hash-based signature scheme can be effective against the content pollution, in particular when being used during the initial phase.

In Peer-to-Peer (P2P) file sharing systems, the attributes of resource description can influence the user behavior, especially on resource selection. However, this has been only qualitatively speculated but lacks of quantitative analysis. In this paper, we carry out a systematically quantitative stu

Peer-to-peer (P2P) live video streaming has been widely used in distance education applications to deliver the captured video courses to a large number of online students. By allowing peers serving each other in the network, P2P technology overcomes many limitations in the traditional client-server paradigm to achieve user and bandwidth scalabilities. However, existing systems do not perform well when the number of online students increases, and the system performance degrades seriously. One of the reasons is that the construction of the peer overlay in existing P2P systems has not considered the underlying physical network topology and can cause serious topology mismatch between the P2P overlay network and the physical network. The topology mismatch problem brings great link stress (unnecessary traffic) in the Internet infrastructure and greatly degrades the system performance. In this article, we address this problem and propose a locality-aware P2P overlay construction method, called Nearcast , which builds an efficient overlay multicast tree by letting each peer node choose physically closer nodes as its logical children. We have conducted extensive simulations to evaluate the performance of Nearcast in comparison with the existing RTT and NICE protocols. Also, Nearcast has been deployed on a wide-area network testbed to delivery video coursed to about 7200 users distributed across 100 collages in 32 cities in China. The experimental results show that Nearcast leads to lower link stress and shorter end-to-end latencies compared with the RTT and NICE protocols.

Video-on-Demand (VoD) is a compelling application, but costly. VoD is costly due to the load it places on video source servers. Many have proposed using peer-to-peer (P2P) techniques to shift load from servers to peers. Yet, nobody has implemented and deployed a system to openly and systematically evaluate how these techniques work. This article describes the design, implementation and evaluation of GridCast, a real deployed P2P VoD system. GridCast has been live on CERNET since May of 2006. It provides seek, pause, and play operations, and employs peer sharing to improve system scalability. In peak months, GridCast has served videos to 23,000 unique users. From the first deployment, we have gathered information to understand the system and evaluate how to further improve peer sharing through caching and replication. We first show that GridCast with single video caching (SVC) can decrease load on source servers by an average of 22% from a client-server architecture. We analyze the net effect on system resources and determine that peer upload is largely idle. This leads us to changing the caching algorithm to cache multiple videos (MVC). MVC decreases source load by an average of 51% over the client-server. The improvement is greater as user load increases. This bodes well for peer-assistance at larger scales. A detailed analysis of MVC shows that departure misses become a major issue in a P2P VoD system with caching optimization. Motivated by this observation, we examine how to use replication to eliminate departure misses and further reduce server load. A framework for lazy replication is presented and evaluated in this article. In this framework, two predictors are plugged in to create the working replication algorithm. With these two simple predictors, lazy replication can decrease server load by 15% from MVC with only a minor increase in network traffic.

Peer-to-peer (P2P) networks have been shown to be a promising approach to providing large-scale video-on-demand (VoD) services over the Internet for their potential scalability. However, how to efficiently support VCR functions for VoD services in such networks remains a major challenge. In this paper we propose a novel ring-assisted overlay topology, called RINDY, to address this issue. In RINDY, a peer can implement fast relocation of random seeks by maintaining some near neighbors and remote neighbors in a set of concentric rings with power law radii. We explore several key problems in RINDY including ring organization, neighbor placement over rings and neighbor lookup for random seeks. We evaluate its performance through simulations and compare it with some existing approaches. The experimental results show that RINDY outperforms previous schemes in terms of control overhead, latency and quality of streaming, especially under frequent VCR operations.

In order to provide scalable live-streaming services, we propose an Inter-Overlay Optimization scheme, IOO. Instead of selecting better paths in the same overlay, IOO constructs efficient paths using peers in different overlays, so as to (i) improve global resource utilization of P2P streaming networks; (ii) assign resources based on their locality and delay; (iii) guarantee streaming service quality by using the nearest peers, even when such peers might belong to different overlays; and (iv) balance the load among the group (streaming overlay) members. We compare the performance of IOO with existing approaches through trace driven simulations. Results show that IOO outperforms previous schemes in terms of resource utilization and the QoS of streaming services. IOO scheme has been implemented in an Internet based live streaming system, called AnySee. AnySee was successfully released in the summer of 2004 in CERNET of China. Over 60,000 users enjoy massive entertainment programs, including TV programs, movies, and academic conferences videos.

Abstract — Efficient and scalable live-streaming overlay construction has become a hot topic recently. In order to improve the performance metrics, such as startup delay, source-to-end delay, and playback continuity, most previous studies focused on intra-overlay optimization. Such approaches have drawbacks including low resource utilization, high startup and source-to-end delay, and unreasonable resource assignment in global P2P networks. Anysee is a peer-to-peer live streaming system and adopts an inter-overlay optimization scheme, in which resources can join multiple overlays, so as to (1) improve global resource utilization and distribute traffic to all physical links evenly; (2) assign resources based on their locality and delay; (3) guarantee streaming service quality by using the nearest peers, even when such peers might belong to different overlays; and (4) balance the load among the group members. We compare the performance of our design with existing approaches based on comprehensive trace driven simulations. Results show that AnySee outperforms previous schemes in resource utilization and the QoS of streaming services. AnySee has been implemented as an Internet based live streaming system, and was successfully released in the summer of 2004 in CERNET of China. Over 60,000 users enjoy massive entertainment programs, including TV programs, movies, and academic conferences. Statistics prove that this design is scalable and robust, and we believe that the wide deployment of AnySee will soon benefit many more Internet users.

A locality-aware overlay network for high performance computing, GTapestry, is proposed in this paper. GTapestry assembles physically neighboring nodes in the Internet into self-organized groups. The routing mechanism of GTapestry is divided into inter-group routing, used by groups that communicate with others through their leaders, and intra-group routing, used by group members to communicate with each other directly. Compared with Tapestry, the performance of GTapestry, including the routing efficiency and the maintenance cost for stability, is evaluated in theory and via simulation. It indicates that GTapestry can be the substrate of peer-to-peer based HPC systems for applications with task-level parallelism.

Summary form only given. Among the schemes providing efficient CPU allocation for coexisting multimedia applications and nonreal time tasks, proportional share scheduling is widely used for its flexibility and fairness. However, this method faces the challenge of setting reasonable shares for a set of tasks with dynamically changing resource requirements. Existing solutions for this problem either ignore the needs of important tasks or are complex to realize. This paper proposes an IMAC, an importance-level based adaptive CPU scheduling scheme, to solve the problems. It adjusts the CPU allocation shares among different application classes not only using history information as feedback, but also considering the different importance-levels of applications. It can adapt to the changing workload rapidly, allocate the CPU time efficiently, and furthermore, guarantee that tasks with higher level of importance get better QoS (quality of service). The experiment results show that the proposed IMAC scheme can significantly improve the efficiency of CPU utilization compared with the traditional adaptive proportional share scheduling policies.

In This work we present a thorough study of the topological properties of the Gnutella network, which provides insight into the nature of the underlying system, helps us design high performance algorithms and generates more realistic topologies for simulation experiments. We compare two theoretical models of growing networks with the present real data of the Gnutella network.

In this paper, we propose and implement a new scalable video server with distributed recording services using intelligent network attached storage based on cluster architectures. For this recording server, we propose a new distributed recording protocol. The recorder can also provide video-on-demand streaming services. With this facility, clients can access media data being recorded randomly, which are distributed on all selected storage nodes of the cluster. Compared with other recording servers, the system has better load balance performance and clients have better interactivities.