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.

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.

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 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.

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.

Transactional stream processing engines (TSPEs) are central to modern stream applications handling shared mutable states. However, their full potential, particularly in adaptive scheduling, remains largely unexplored. We presentMorphStream, a TSPE designed to optimize parallelism and performance for transactional stream processing on multicores. Through a unique three-stage execution paradigm (i.e.,planning,scheduling, andexecution),MorphStreamenables adaptive scheduling under varying workload characteristics. Building on this foundation,MorphStreamis further enhanced with support for non-deterministic state access, employing a stateful task precedence graph to handle undefined read/write sets at runtime while guaranteeing transaction semantics. Additionally,MorphStreamincorporates a generalized framework for managing window-based operations, enabling efficient tracking and maintenance of overlapping windows using multi-versioned state management. These extensions enhance the system's ability to process dynamic and irregular workloads. Experimental results demonstrate up to 3.4 times higher throughput and 69.1% lower latency compared to state-of-the-art TSPEs, validating its scalability and adaptability in real-world streaming scenarios.

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.

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.

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.

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.

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.

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.

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.

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.

Transactional stream processing engines (TSPEs) differ significantly in their designs, but all rely on non- adaptive scheduling strategies for processing concurrent state transactions. Subsequently, none exploit multicore parallelism to its full potential due to complex workload dependencies. This paper introduces MorphStream, which adopts a novel approach by decomposing scheduling strategies into three dimensions and then strives to make the right decision along each dimension, based on analyzing the decision trade-offs under varying workload characteristics. Compared to the state-of-the-art, MorphStream achieves up to 3.4 times higher throughput and 69.1% lower processing latency for handling real-world use cases with complex and dynamically changing workload dependencies.

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.

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.

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.

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.

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%.

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.

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.

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.

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.

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.

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.

With the emergence of big data applications, stream join systems are widely used in extracting valuable information among multi-source streams. However, providing completeness of processing results in a large-scale distributed stream join system is challenging because it is hard to guarantee the consistency among all instances. We show through experiments that the abnormal result can make the quality of achieved data unacceptable in practice.In this paper, we propose Eunomia, a novel distributed stream join system which leverages an ordered propagation model for efficiently eliminating abnormal results. We design a light-weighted self-adaptive strategy to adjust the structure in the model according to the dynamic stream input rates and workloads. It can improve the scalability and performance significantly. We implement Eunomia and conduct comprehensive experiments to evaluate its performance. The results show that Eunomia eliminates abnormal results to guarantee the completeness, improves the system throughput by 25% and reduces the processing latency by 74% compared to state-of-the-art designs.

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×).

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.

Although GPUs have emerged as the mainstream for the acceleration of convolutional neural network (CNN) training processes, they usually have limited physical memory, meaning that it is hard to train large-scale CNN models. Many methods for memory optimization have been proposed to decrease the memory consumption of CNNs and to mitigate the increasing scale of these networks; however, this optimization comes at the cost of an obvious drop in time performance. We propose a new memory optimization strategy named Layup that realizes both better memory efficiency and better time performance. First, a fast layer-type-specific method for memory optimization is presented, based on the new finding that a single memory optimization often shows dramatic differences in time performance for different types of layers. Second, a new memory reuse method is presented in which greater attention is paid to multi-type intermediate data such as convolutional workspaces and cuDNN handle data. Experiments show that Layup can significantly increase the scale of extra-deep network models on a single GPU with lower performance loss. It even can train ResNet with 2,504 layers using 12GB memory, outperforming the state-of-the-art work of SuperNeurons with 1,920 layers (batch size = 16).

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.

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.

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.

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.

Today, stream data applications represent the killer applications for Edge computing: placing computation close to the data source facilitates real-time analysis. Previous efforts have focused on introducing light-weight distributed stream processing (DSP) systems and dividing the computation between Edge servers and the clouds. Unfortunately, given the limited computation power of Edge servers, current efforts may fail in practice to achieve the desired latency of stream data applications. In this vision paper, we argue that by introducing FPGAs in Edge servers and integrating them into DSP systems, we might be able to realize stream data processing in Edge infrastructures. We demonstrate that through the design, implementation, and evaluation of F-Storm, an FPGA-accelerated and general-purpose distributed stream processing system on Edge servers. F-Storm integrates PCIe-based FPGAs into Edge-based stream processing systems and provides accelerators as a service for stream data applications. We evaluate F-Storm using different representative stream data applications. Our experiments show that compared to Storm, F-Storm reduces the latency by 36% and 75% for matrix multiplication and grep application. It also obtains 1.4x and 2.1x improvement for these two applications, respectively. We expect this work to accelerate progress in this domain.

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.

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.

Cloud datacenters are underutilized due to server over-provisioning. To increase datacenter utilization, cloud providers offer users an option to run workloads such as big data analytics on the underutilized resources, in the form of cheap yet revocable transient servers (e.g., EC2 spot instances, GCE preemptible instances). Though at highly reduced prices, deploying big data analytics on the unstable cloud transient servers can severely degrade the job performance due to instance revocations. To tackle this issue, this paper proposes iSpot, a cost-effective transient server provisioning framework for achieving predictable performance in the cloud, by focusing on Spark as a representative Directed Acyclic Graph (DAG)-style big data analytics workload. It first identifies the stable cloud transient servers during the job execution by devising an accurate Long Short-Term Memory (LSTM)-based price prediction method. Leveraging automatic job profiling and the acquired DAG information of stages, we further build an analytical performance model and present a lightweight critical data checkpointing mechanism for Spark, to enable our design of iSpot provisioning strategy for guaranteeing the job performance on stable transient servers. Extensive prototype experiments on both EC2 spot instances and GCE preemptible instances demonstrate that, iSpot is able to guarantee the performance of big data analytics running on cloud transient servers while reducing the job budget by up to 83.8 percent in comparison to the state-of-the-art server provisioning strategies, yet with acceptable runtime overhead.

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.

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.

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.

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.

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.

This paper presents F2C, a cooperative resource management system for Infrastructure-as-a-Service (IaaS) clouds. Inspired by group-buying mechanisms in real product and service markets, F2C advocates a group of cloud tenants (called tenant coalition) to buy resource capacity in bulk and share the resource pool in the form of virtual machines (VMs). Tenant coalitions leads to vast opportunities for fine-grained resource sharing among multiple tenants. However, resource sharing, especially for multiple resource types, poses several challenging problems in pay-as-you-use cloud environments, such as sharing incentive, free-riding, lying and economic fairness. To address those problems, we propose Reciprocal Resource Fairness (RRF) , a novel resource allocation mechanism to enable fair sharing on multiple resource types within a tenant coalition. RRF is implemented in two complementary and hierarchical mechanisms: inter-tenant resource trading and intra-tenant weight adjustment. RRF satisfies several highly desirable properties to ensure fairness. We implement F2C in Xen platform. The experimental results show F2C is promising for both cloud providers and tenants. For cloud providers, F2C improves VM density and cloud providers' revenue by 2.2X compared to the current IaaS cloud models. For tenants, F2C improves application performance by 45 percent and guarantees 95 percent economic fairness among multiple tenants.

Enabled by virtualization technologies, various multi-tier applications (such as web applications) are hosted by virtual machines (VMs) in cloud data centers. Live migration of multi-tier applications across geographically distributed data centers is important for load management, power saving, routine server maintenance and quality-of-service. Different from a single-VM migration, VMs in a multi-tier application are closely correlated, which results in a correlated VM migrations problem. Current live migration algorithms for single-VM cause significant application performance degradation because intermediate data exchange between different VMs suffers relatively low bandwidth and high latency across distributed data centers. In this paper, we design and implement a coordination system called VMbuddies for correlated VM migrations in the cloud. Particularly, we propose an adaptive network bandwidth allocation algorithm to minimize the migration cost in terms of migration completion time, network traffic and migration downtime. Experiments using a public benchmark show that VMbuddies significantly reduces the performance degradation and migration cost of multi-tier applications.

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.

Fair resource allocation is a key building block of any shared computing system. However, MemoryLess Resource Fairness (MLRF), widely used in many existing frameworks such as YARN, Mesos and Dryad, is not suitable for pay-as-you-use computing. To address this problem, this paper proposes Long-Term Resource Fairness (LTRF), a novel fair resource allocation mechanism. We show that LTRF satisfies several highly desirable properties. First, LTRF incentivizes clients to share resources via group-buying by ensuring that no client is better off in a computing system that she buys and uses individually. Second, LTRF incentivizes clients to submit non-trivial workloads and be willing to yield unneeded resources to others. Third, LTRF has a resource-as-you-pay fairness property, which ensures the amount of resources that each client should get according to her monetary cost, despite that her resource demand varies over time. Finally, LTRF is strategy-proof, since it can make sure that a client cannot get more resources by lying about her demand. We have implemented LTRF in YARN by developing LTYARN, a long-term YARN fair scheduler, and shown that it leads to a better resource fairness than other state-of-the-art fair schedulers.

Resource sharing in virtualized environments have been demonstrated significant benefits to improve application performance and resource/energy efficiency. However, resource sharing, especially for multiple resource types, poses several severe and challenging problems in pay-as-you-use cloud environments, such as sharing incentive, free-riding, lying and economic fairness. To address those problems, we propose Reciprocal Resource Fairness (RRF), a novel resource allocation mechanism to enable fair sharing multiple types of resource among multiple tenants in new-generation cloud environments. RRF implements two complementary and hierarchical mechanisms for resource sharing: inter-tenant resource trading and intra-tenant weight adjustment. We show that RRF satisfies several highly desirable properties to ensure fairness. Experimental results show that RRF is promising for both cloud providers and tenants. Compared to existing cloud models, RRF improves virtual machine (VM) density and cloud providers' revenue by 2.2X. For tenants, RRF improves application performance by 45% and guarantees 95% economic fairness among multiple tenants.

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.

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.

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.

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.