Sparse matrix–vector multiplication (SpMV) kernel dominates the computing cost in numerous applications. Most of the existing studies dedicated to improving this kernel have been targeting just one type of processing units, mainly multicore CPUs or graphics processing units (GPUs), and have not explored the potential of the recent, rapidly emerging, CPU-GPU heterogeneous platforms. To take full advantage of these heterogeneous systems, the input sparse matrix has to be partitioned on different available processing units. The partitioning problem is more challenging with the existence of many sparse formats whose performances depend both on the sparsity of the input matrix and the used hardware. Thus, the best performance does not only depend on how to partition the input sparse matrix but also on which sparse format to use for each partition. To address this challenge, we propose in this article a new CPU-GPU heterogeneous method for computing the SpMV kernel that combines between different sparse formats to achieve better performance and better utilization of CPU-GPU heterogeneous platforms. The proposed solution horizontally partitions the input matrix into multiple block-rows and predicts their best sparse formats using machine learning-based performance models. A mapping algorithm is then used to assign the block-rows to the CPU and GPU(s) available in the system. Our experimental results using real-world large unstructured sparse matrices on two different machines show a noticeable performance improvement.
26 April 2022 in IEEE Transactions on Parallel and Distributed Systems
Binary Sparse Matrix-Vector Multiplication (SpMV) is a heavy computational kernel in weblink analysis, integer factorization, compressed sensing, spectral graph theory, and other domains. Testing several popular GPU-based SpMV implementations on 400 sparse matrices, we observed that data transfer to GPU memory accounts for a large part of the total computation time. The transfer of constant value 1s can be easily eliminated for binary sparse matrices. However, compressing index arrays has always been a great challenge. This paper proposes a new compression format TaiChi to further reduce index data copies and improve the performance of SpMV, especially for diagonally dominant binary sparse matrices. Input matrices are firstly partitioned into relatively dense and ultra-sparse areas. Then the dense areas are encoded inversely by marking ``0"s, while the ultra-sparse area is encoded by marking ``1"s. We also designed a new SpMV algorithm only using addition and subtraction for binary matrices based on our partition and encoding format. Evaluation results on real-world binary sparse matrices show that our hybrid encoding for binary matrix significantly reduces the data transfer and speeds up the kernel execution. It achieves the highest transfer and kernel execution speedups of 5.63x and 3.84x on GTX 1080 Ti, 3.39x and 3.91x on Tesla V100.
For the heterogeneous big data parallel computing model, two levels of parallelism between nodes are not considered, resulting in low efficiency of heterogeneous big data parallel computing and bandwidth to send and receive information, high communication overhead, long model running time and small computational volume. In the paper, we propose an optimization model of heterogeneous big data parallel computing based on a hybrid Multi Point Interface (MPI)/Open Multi-Processing (OpenMP) and Sensor Networks. First, the processor characteristics of heterogeneous big data architecture is analyzed, the parallel tasks among processors are divided, collect the heterogeneous big data to be computed and cluster them, and use the processing results as the input items of the model. Then, a parallel load balancing mechanism is established to optimally divide the parallel computing load of heterogeneous big data, and a parallel computing optimization program is written by combining the hybrid programming mode of MPI and OpenMP and using the hybrid MPI/OpenMP, and finally, the parallel computing optimization of heterogeneous big data is realized by optimizing the parallel communication and determining the model parameters. The results show that the proposed model has a communication bandwidth of 510Mbps, a computational volume of 1.16GB, a model runtime of 24s, and an improved network bandwidth utilization of 93%, which can effectively reduce the communication overhead, and improve the efficiency of parallel computing and bandwidth sending and receiving information in sensor networks, and shorten the model running time.
Data races are increasingly seen as concurrency bugs and they are difficult to reproduce and diagnose in parallel programs. Linux kernel is a large-scale software system, in which intensive thread-level parallelism and non-deterministic thread interleaving are more prone to race conditions. This paper conducts an investigation of real Linux kernel data races in recent 5 years. Our results show that there are about 500 real kernel data races reported and fixed in recent 5 years. File systems and drivers among all modules hold a much higher percentage of race conditions than other modules. We also conduct a case-bycase study on data races and graphically show how these data races are triggered with specific thread interleaving. Our analysis results are of interest to researchers and engineers who are committed to kernel data race detection and kernel development.
The WK-recursive network well conforms to implementation of large distributed systems due to its many favorable properties. In this paper, we employ the concept S3 group to establish an efficient look-ahead routing algorithm for the triplet-based WK-recursive network. Remarkably, we introduce a data flow model to categorize message traffic as six flow models. For the sake of simplicity, we further leverage the permutation group S3 to transform different flow models to one model and hence routing computing can be performed in the same model. It is demonstrated that our proposed design can achieve better network performance.