Search

Sparse matrix-vector multiplication (SpMV) has always been a hot topic of research for scientific computing and big data processing, but the sparsity and discontinuity of the nonzero elements in a sparse matrix lead to the memory bottleneck of SpMV. In this paper, we propose aligned CSR (ACSR) and aligned ELL (AELL) formats and a parallel SpMV algorithm to utilize NEON SIMD registers on ARM processors. We analyze the impact of SIMD instruction latency, cache access, and cache misses on SpMV with different formats. In the experiments, our SpMV algorithm based on ACSR achieves 1.18x and 1.56x speedup over SpMV based on CSR and SpMV in PETSc, respectively, and AELL achieves 1.21x speedup over ELL. The deviations between the theoretical results and experimental results in the instruction latency and cache access are 10.26% and 10.51% in ACSR and 5.68% and 2.91% in AELL, respectively.

In big data scenarios, matrix factorization (MF) is widely used in recommendation systems as it can offer high accuracy and scalability. However, when using MF to process large-scale implicit feedback data, the following two problems arise. One is that it is difficult to effectively obtain negative feedback information, which causes relatively poor recommendation accuracy. The other is that the limited resources of a single machine make the model training inefficient, and in particular, the acquisition of negative feedback information further increases the time complexity of model training. In order to solve the above two problems, we first propose a user-activity and item-popularity weighted matrix factorization (UIWMF) recommendation algorithm, which assigns every missing data different weight based on user activity and item popularity, gets negative feedback information more realistically, and leads to better recommendation accuracy. Meanwhile, in order to reduce the additional computational overhead caused by the weight strategy, we develop a fast optimization strategy to enhance the efficiency. In order to break the resource constraints of a single machine, we propose a distributed UIWMF (DUIWMF) algorithm based on Spark, which adopts an efficient parallel learning algorithm to train the model and utilizes cached in-block and out-block information to effectively reduce the communication overhead in a distributed environment. We conduct experiments on three public datasets, and the experimental results demonstrate that, comparing with the baseline MF methods, DUIWMF model has comparable performance in terms of recommendation accuracy and model training efficiency.

Tensors have drawn a growing attention in many applications, such as physics, engineering science, social networks, recommended systems. Tensor decomposition is the key to explore the inherent intrinsic data relationship of tensor. There are many sparse tensor and vector multiplications (SpTV) in tensor decomposition. We analyze a variety of storage formats of sparse tensors and develop a piecewise compression strategy to improve the storage efficiency of large sparse tensors. This compression strategy can avoid storing a large number of empty slices and empty fibers in sparse tensors, and thus the storage space is significantly reduced. A parallel algorithm for the SpTV based on the high-order compressed format based on slices is designed to greatly improve its computing performance on graphics processing unit. Each tensor is cut into multiple slices to form a series of sparse matrix and vector multiplications, which form the pipelined parallelism. The transmission time of the slices can be hidden through pipelined parallel to further optimize the performance of the SpTV.

Multifrontal QR algorithm, which consists of symbolic analysis and numerical factorization, is a high-performance algorithm for orthogonal factorizing sparse matrix. In this work, a graph convolutional network (GCN) for adaptively selecting the optimal reordering algorithm is proposed in symbolic analysis. Using our GCN adaptive classifier, the average numerical factorization time is reduced by 20.78% compared with the default approach, and the additional memory overhead is approximately 4% higher than that of prior work. Moreover, for numerical factorization, an optimized tasks stream parallel processing strategy is proposed and a more efficient computing task mapping framework for NUMA architecture is adopted in this paper, which called STM-Multifrontal QR factorization. Numerical experiments on the TaiShan Server show average 1.22x performance gains over the original SuiteSparseQR. Nearly 80% of datasets have achieved better performance compared with the MKL sparse QR on Intel Xeon 6248.