Sparse-Dense Matrix Multiplication (SpMM) is a fundamental computational operation in various domains, and leveraging Tensor cores or CUDA cores on GPU to accelerate SpMM has become common practice. While Tensor cores offer notable advantages in dense matrix multiplication, their efficiency significantly decreases when handling sparse matrices. Besides, the computational power of CUDA cores should not be overlooked. Nevertheless, the differences in supported data formats present challenges in effectively leveraging both types of cores to accelerate SpMM. To this end, we propose BRP-SpMM, a block and row partition approach designed for efficient SpMM on GPU. BRP-Sp partitions the sparse matrix into two parts: TC Block and Residual Row part, which are computed on Tensor cores and CUDA cores separately. Meanwhile, a customized storage format is proposed to manage these two distinct parts. Our two GPU kernels incorporate several advanced techniques including load balance, register remapping, and 1-D tiling. BRP-SpMM can achieve higher memory access efficiency and more rational computing resource utilization of GPU. Extensive experiments on modern NVIDIA A800 GPU show that BRPSpMM outperforms SOTA libraries by up to$2.9 \times$(on average$2.1 \times)$. Furthermore, BRP-SpMM accelerates end-to-end GNN training by up to$1.9 \times$compared to popular frameworks.

Graph Neural Networks (GNNs) have achieved remarkable successes in various graph-based learning tasks, thanks to their ability to leverage advanced GPUs. However, GNNs currently face challenges arising from the concurrent use of advanced Tensor Cores (TCs) and CUDA Cores (CDs) in GPUs. These challenges are further exacerbated due to repeated, inefficient, and redundant aggregations in GNN that result from the high sparsity and irregular non-zero distribution of real-world graphs. We propose RT-GNN, a GNN framework based on the fusion of advanced TC and CD units, to eliminate the aforementioned redundancies by exploiting the properties of an adjacency matrix. First, a novel GNN representation technique, hierarchical embedding graph (HEG) is proposed to manage the intermediate aggregation results hierarchically, which can further avoid redundancy in intermediate aggregations elegantly. Next, to address the inherent sparsity of graphs, RT-GNN places the blocks (a.k.a. tiles) in HEG onto TCs and CDs according to their sparsity by a new block-based row-wise multiplication approach, which assembles TCs and CDs to work concurrently. Experimental results demonstrate that HEG outperforms HAG by an average speedup of 19.3× for redundancy elimination performance, especially up to 72× speedup on the dataset of ARXIV. Moreover, for overall performance, RT-GNN outperforms state-of-the-art GNN frameworks (including DGL, HAG, GNNAdvisor, and TC-GNN) by an average factor of 3.1× while maintaining or even improving the task accuracy.

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

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

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

Binary- source code matching plays an important role in many security and software engineering related tasks such as malware detection, reverse engineering and vulnerability assessment. Currently, several approaches have been proposed for binary-source code matching by jointly learning the embeddings of binary code and source code in a common vector space. Despite much effort, existing approaches target on matching the binary code and source code written in a single programming language. However, in practice, software applications are often written in different programming languages to cater for different requirements and computing platforms. Matching binary and source code across programming languages introduces additional challenges when maintaining multi-language and multi-platform applications. To this end, this paper formulates the problem of cross-language binary-source code matching, and develops a new dataset for this new problem. We present a novel approach XLIR, which is a Transformer-based neural network by learning the intermediate representations for both binary and source code. To validate the effectiveness of XLIR, comprehensive experiments are conducted on two tasks of cross-language binary-source code matching, and cross-language source-source code matching, on top of our curated dataset. Experimental results and analysis show that our proposed XLIR with intermediate representations significantly outperforms other state-of-the-art models in both of the two tasks.

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

Hepatoma is the most common type of primary liver cancer with a high mortality rate in the world. The genetic causes of the disease pathology remain largely unknown. Effective discovery of the genes associated with hepatoma has become important in disease prevention, early diagnosis, and therapeutic treatments. With the developments of molecular networks, graph-based methods have been tremendously successful in predicting disease genes based on the hypothesis of guilt-by-association. Network representation learning (NRL) techniques have accelerated disease gene discovery in recent years because of their powerful network feature extraction ability. However, the current network representation learning-based methods for disease gene discovery did not consider the gene features derived from gene ontology annotations, which apriori group genes with similar functions. To fill this gap, here we propose a novel framework to predict hepatoma-related genes based on representation learning from both protein-protein interactions (PPI) network and gene ontology annotations. Our framework has three steps: learning features from PPI network and gene ontologies using NRL techniques, integrating different features based on autoencoder, predicting hepatoma-related genes using machine learning classifiers. Experiments have demonstrated that our framework could accurately predict hepatoma-related genes with AUROC and AUPRC reaching 0.93 and 0.94, respectively. Compared with other methods using only single representation features, our framework also shows superior performance on hepatoma gene prediction.

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

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

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

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

Many data owners are required to release the data in a variety of real world application, since it is of vital importance to discovery valuable information stay behind the data. However, existing re-identification attacks on the AOL and ADULTS datasets have shown that publish such data directly may cause tremendous threads to the individual privacy. Thus, it is urgent to resolve all kinds of re-identification risks by recommending effective de-identification policies to guarantee both privacy and utility of the data. De-identification policies is one of the models that can be used to achieve such requirements, however, the number of de-identification policies is exponentially large due to the broad domain of quasi-identifier attributes. To better control the trade off between data utility and data privacy, skyline computation can be used to select such policies, but it is yet challenging for efficient skyline processing over large number of policies. In this paper, we propose one parallel algorithm called SKY-FILTER-MR, which is based on MapReduce to overcome this challenge by computing skylines over large scale de-identification policies that is represented by bit-strings. To further improve the performance, a novel approximate skyline computation scheme was proposed to prune unqualified policies using the approximately domination relationship. With approximate skyline, the power of filtering in the policy space generation stage was greatly strengthened to effectively decrease the cost of skyline computation over alternative policies. Extensive experiments over both real life and synthetic datasets demonstrate that our proposed SKY-FILTER-MR algorithm substantially outperforms the baseline approach by up to four times faster in the optimal case, which indicates good scalability over large policy sets.

Stochastic Kronecker Graph model is widely used to generate synthetic graphs that simulate real-world graphs. In this model, the initiator matrix decides the degree to which the synthetic graph approximates the real-world graph. The computing of initiator matrix, however, requires that the number of the nodes of input graph is the power of the dimension of the initiator matrix. In order to fulfill such requirement, some methods (e.g., KronFit and Moment) add isolated nodes to the input graph, which damages the input graph's properties. Other method (e.g., KronEM) predicts the links between the nodes after adding isolated nodes. Unfortunately, the prediction dramatically increases the complexity of computing. In this paper, we propose a method named as MomentSA to solve the problems. Our method completes the input graphs by leveraging the law of property changes of graphs, which does not need to predict the links as method KronEM. Simultaneously, our method uses the moment-based estimation and ADAM (Adaptive Moment Estimation) method to compute the initiator matrix, which can compute the initiator matrix quickly. Experiment results on our prototype implementation suggest that the initiator matrix computed from our method is more accurate than existing state-of-art systems, and the speed of computing is about three to four orders of magnitude faster than state-of-art systems.

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

Detecting data races among the threads of a concurrent program is one of the most important debugging issues. However, the data races are never be easily detected due to the inherent concurrency and indeterministic execution of the participating threads. The widely employed dynamic data race detecting methods generally scrutinize one of sampled execution paths of the program, and may thus miss some data races. With improved coverage, static methods detect the data races by analyzing the source code. However, such static methods result in lots of false alarming, and are not of practical use. In this paper, we propose a method that detects the data races by understanding the synchronization relationships among the segments of participating threads. This method can improve the coverage by enumerating all the possible execution paths of the thread phases, and at the same time, reserve the existing merits of dynamic data race detecting methods. The experiment data shows that our prototype detector is comparable in accuracy with the commercial detector Intel Inspector, and other open source detector, such as ThreadSanitizer. At the same time, our detector has less memory consumption for memory intensive benchmarks in NPB suite, which other software tools fail to analyze.

Summary Finding strongly connected components (SCCs) in graphs is one of the important research topics of graph data mining. Traditional SCC‐finding methods need to load the whole graph into main memory before actual processing, which makes them inappropriate to process today's large graphs. Although it is cost‐effective to conductive SCC‐finding in the external memory (EM) graph processing systems, existing EM systems are still inefficient on such workload for 2 reasons: data‐parallel processing model and inefficient graph mutation mechanism. In this paper, we propose a task‐based approach, named as TAS, for finding SCCs in large real‐world graphs. TAS encapsulates individual graph dataset and the SCC‐finding algorithms conducted on it as an independent task. By this strategy, different algorithms can be assigned to different datasets according to the stage of processing or the size of the dataset. By gradually removing unneeded data, ie, the known SCCs, with an efficient graph mutation method, TAS continuously reduces the scale of the problem to accelerate processing. Performance evaluation on large real‐world graphs show that TAS greatly outperforms existing EM solutions on finding SCCs (eg, 55.2x faster than GraphChi and 40.3x faster than X‐Stream).

Finding Strongly Connected Components (SCCs) in graphs is one of the important research topics of graph data mining. Traditional methods of finding SCCs need to fully load the whole graph into the main memory of a computer before actual processing. However, with the rapid growth of real-world graphs, the sizes of graphs easily exceed the main memory space of an ordinary computer. The distributed graph processing system running on a cluster and the out-of-core system utilizing the external memory all can handle that huge graph, but recent evidences (e.g., GridGraph) show that the external memory systems are more cost-effective and efficient than the distributed systems on conducting most graph mining tasks. Existing external memory solutions are inefficient on finding SCCs in large-scale graphs for two reasons: (1) The data-parallel processing model adopted is not efficient to find SCCs in a largescale graph. (2) Their poor support for graph mutation incurs excessively high overhead. In this paper, we study the problem of finding SCCs in big real-world graphs by using the external memory. We propose a task-based approach and an efficient graph mutation method to address the limitations in existing external solutions for finding SCCs. Experiment results show that our approach is orders of magnitude faster than existing external memory solutions.

Graph algorithms are used to implement data mining tasks on graph data-sets. Besides conducting the algorithms by the default deterministic manner, some graph processing frameworks, especially those supporting asynchronous execution model, provide interfaces for the algorithms to be executed in nondeterministic manner, which can improve the scalability and performance of the algorithm's executions. However, is the graph algorithm eligible for nondeterministic execution, and will the execution produce expected results? The literature gives few answers to these questions. In this paper, we study the nondeterministic execution of graph algorithms by considering the scenario where data dependences happen in the edges in graph processing frameworks that employ asynchronous execution model. Our study reveals that only by guaranteeing the atomicity of individual reads and writes, some algorithms (e.g., Graph traversal algorithms) can converge by recovering from corrupted intermediate results with nondeterministic execution, and thus tolerate even write-write conflicts, while some other algorithms (e.g., Fixed point iteration algorithms) can converge but tolerate only read-write conflicts. By conducting graph algorithms on real-world graphs in Graph Chi, and comparing their performances and results with deterministic executions, we find that their performance gains are generally scalable to the available processors with nondeterministic executions, and the results at convergence of fixed point iteration algorithms from nondeterministic executions exhibit larger variances from one run to another than their deterministic executions.

SUMMARY The challenge forSparse Matrix–Vector multiplication(SpMV) performance is memory bandwidth, which mostly depends on input matrices and underlying computing platforms. To solve this challenge, many researchers have explored a variety of optimization techniques. One of the most promising aspects focuses on designing storage formats to represent sparse matrices. However, lots of prior storage formats cannot fully take advantage of the underlying computing platforms, resulting in unsatisfactory performance and large memory footprint. Therefore, a novel storage format, calledSegmented Hybrid ELL + Compressed Sparse Row (CSR)(SHEC for short), is proposed to further improve the throughput and lessen memory footprint onGraphics Processing Unit(GPU). SHEC format employs an interleaved combination pattern, which combines certain amount of compressed rows to form a new SHEC row. Segmentation is brought in to balance load and reduce memory footprint. According to the empirical data, an automatic SHEC‐based SpMV is developed to fit for all the matrices. Experimental results show that SHEC approach outperforms the best results of NVIDIA SpMV library and exhibits a comparable performance with state‐of‐the‐art storage formats on the standard dataset. Copyright © 2012 John Wiley & Sons, Ltd.

Sparse Matrix-Vector multiplication (SpMV) is one of the most significant yet challenging issues in computational science area. It is a memory-bound application whose performance mostly depends on the input matrix and the underlying architecture. Many researchers have paid more attentions on exploring a variety of optimization techniques to SpMV. One of the most promising respects is how to adapt the storage format to satisfy the underlying architecture. Alterative storage formats can largely lessen memory pressure, however, the computational resources are often underutilized. Therefore, a new storage format, which is called Compressed Sparse Row with Segmented Interleave Combination (SIC), is proposed. Stemming from Compressed Sparse Row format (CSR), SIC format employs an interleave combination pattern that combines certain amount of CSR rows to form a new SIC row. In order to further improve performance, segmented processing is also brought in. According to the empirical data, we also develop an automatic SIC-based SpMV suitable for all the matrices. Experimental results show that our approach outperforms the NVIDIA CSR vector kernel, achieving up to 12.6 × speedup. It also demonstrates a comparable performance with the Hybrid format, even with the highest 2.89 × speedup.

Nowadays, it is an important trend in the system domain to use the software-based virtualization technology to build the execution environments (e.g., Clouds) and serve high performance computing (HPC) applications. However, with the extra virtualization layer, the application performance may be negatively affected. Studies revealed that the communication performance of the MPI library, which is widely used by the HPC applications, would suffer a high penalty when a physical host machine becomes overcommitted by virtual processors (VCPU). Unfortunately, the problem has not received enough attention and has not been solved yet in literature. In this paper, we investigate the reasons behind the performance penalty, and propose a solution to improve the communication performance of running MPI applications in the overcommitted virtualized systems. The experimental results show that by our proposal, most HPC applications can gain performance improvement to different extents among the overcommitted systems, depending on their communication patterns and the over committing level.

In a virtual execution environment, dynamic computing resource adjustment technique, configuring the computing resource of virtual machines automatically according to the actual loads generated by applications, is often adopted in virtual machine monitor to improve the resource utilization rate. Traditionally, the simple Additive Increase Subtractive Decrease (AISD) scheme is used as an adjusting rule. However, in some special situations, for example, compiling kernel in a virtual machine, the configuration of virtual machines may change abruptly because of the violent vibration of workload during a short interval, and the threshing can inevitably result in additional overhead under AISD rule. In this paper, we extend the Proportional-Integral-Derivative (PID) algorithm and present a feedback control model for configuring virtual computing resources, and propose an innovative adjusting scheme called Forecasting and Time Delayed Subtraction (FTDS) to reduce the overhead caused by threshing. The FTDS uses both statistic history of resource requests and current utilization of computing resource to predict whether threshing happens and to determine how many and when to adjust the amount of virtual CPUs. Experimental results show that FTDS can effectively reduce the jitter occurred in adjusting and make the performance penalty for threshing decreased from 9% to 0.3% compared with AISD, while maintaining that in non-threshing cases the same as AISD.

With the resurgence of virtual machine technology, vendors build virtualization technology support in the processors. Virtual machines relying on such support are called Hardware-assisted Virtual Machines (HVM guests for short). Although HVM guests have the advantage that they do not need to revise the source code of operating systems running inside, the processing of I/O operations in HVM is much complicated and the performance of such operations are rather low. In this paper, we conduct a performance study on the Web server running inside the HVM guests by using queuing network modeling technique, and analyze the performance bottlenecks of the systems.

In this paper, we propose a scheme that manages the computational resource of virtual machines that are used to host high performance computing applications. Different from the static configuration methodology employed by the state-of-art virtual machine monitors, in our scheme, the virtual machines are automatically configured according to the actual load generated by the applications. NPB, HPL and kernel compilation are chosen as representative high performance computing applications to run inside the virtual machine constructed using our scheme, and the performance of such applications are compared with that obtained from the statically configured virtual machines. The comparison indicates that besides the great flexibility it brings, the performance penalty resulted by our scheme is below 5% in most cases, and the performance of the application running inside the automatically configured virtual machine is even better than that running inside the statically configured ones in some cases.

As an emerging trend, virtualization is more and more widely used in today's computing world. But, the introduc-tion of virtual machines bring trouble for the power man-agement (PM for short), since the operating system can not directly access and control the hardware as before. Solu-tions were proposed to manage the power in the server con-solidation case. However, such solutions are VMM-centric: the VMM gathers the PM decisions of the guests as hints, and makes the final decision to manipulate the hardware. These solutions do not fit well for the virtualized desktop environment, which is highly interactive with the users.

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

Availability of the service provided by the cluster system is greatly emphasized in today's system domain. We proposed a new technique, named redundant TCP stacks (RTS), to enhance the connection-level reliability and availability of the services provided by cluster system. In this paper, we discuss a faster synchronization algorithm, named send when the fastest response (SWFR) to alleviate the overhead introduced by RTS. We evaluate the new algorithm by comparing it with the original algorithm of send when the minimum updated (SWMU) and the traditional TCP communication. By experiments, we find that RTS with SWFR algorithm minimize the sacrifice on network performance. The performance of a cluster with two servers working in RTS scheme is satisfactory enough for practical usage while delivering high availability.

Improving the availability of services of is a key issue for survivability of a cluster system. Lots of schemes are proposed for this purpose. But most of them aim at enhancing only the service-level availability or application specific. In this paper, we propose a scheme called High Availability with Redundant TCP Stacks (HARTs), providing connection-level availability by exploring the redundant TCP stacks for TCP connections at the server side. We present our performance experiment results on our HA cluster prototype. From results, we find the configuration of one primary server with one backup server running on separated 100 Mbps Ethernet has acceptable performance to support the server side applications while delivering high availability.