Weifeng Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Weifeng Liu has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
Brian Vinter
Niels Bohr Institute University of Copenhagen Copenhagen Denmark
5 shared publicationsAng Li
Pacific Northwest National Lab Richland USA
2 shared publicationsIain S. Duff
Scientific Computing Department STFC Rutherford Appleton Laboratory UK
2 shared publicationsCanqun Yang
1 shared publication- Guangming Tan
Chinese Academy of Sciences
1 shared publication Hao Wang
Dept. of Computer Science, Virginia Tech, Blacksburg, VA, USA
1 shared publication
Latest Publications
- 1 July 2020
- Published by Elsevier in Future Generation Computer Systems
- Vol. 108, 1192-1205
clMF: A fine-grained and portable alternating least squares algorithm for parallel matrix factorization
- 1 July 2020
- Published by Elsevier in Future Generation Computer Systems
- Vol. 108, 1192-1205
clMF: A fine-grained and portable alternating least squares algorithm for parallel matrix factorization
- 1 January 2019
- Published by Springer Nature in International Journal of Parallel Programming
- Vol. 47 (3) , 403-417
Register-Aware Optimizations for Parallel Sparse Matrix–Matrix Multiplication
- 1 January 2019
- Published by Springer Nature in International Journal of Parallel Programming
- Vol. 47 (3) , 403-417
Register-Aware Optimizations for Parallel Sparse Matrix–Matrix Multiplication
- 30 July 2017
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 29 (21)
Fast synchronization‐free algorithms for parallel sparse triangular solves with multiple right‐hand sides
Summary: The sparse triangular solve kernels, SpTRSV and SpTRSM, are important building blocks for a number of numerical linear algebra routines. Parallelizing SpTRSV and SpTRSM on today's manycore platforms, such as GPUs, is not an easy task since computing a component of the solution may depend on previously computed components, enforcing a degree of sequential processing. As a consequence, most existing work introduces a preprocessing stage to partition the components into a group of level‐sets or colour‐sets so that components within a set are independent and can be processed simultaneously during the subsequent solution stage. However, this class of methods requires a long preprocessing time as well as significant runtime synchronization overheads between the sets. To address this, we propose in this paper novel approaches for SpTRSV and SpTRSM in which the ordering between components is naturally enforced within the solution stage. In this way, the cost for preprocessing can be greatly reduced, and the synchronizations between sets are completely eliminated. To further exploit the data‐parallelism, we also develop an adaptive scheme for efficiently processing multiple right‐hand sides in SpTRSM. A comparison with a state‐of‐the‐art library supplied by the GPU vendor, using 20 sparse matrices on the latest GPU device, shows that the proposed approach obtains an average speedup of over two for SpTRSV and up to an order of magnitude speedup for SpTRSM. In addition, our method is up to two orders of magnitude faster for the preprocessing stage than existing SpTRSV and SpTRSM methods.
- 30 July 2017
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 29 (21)
Fast synchronization‐free algorithms for parallel sparse triangular solves with multiple right‐hand sides
Summary: The sparse triangular solve kernels, SpTRSV and SpTRSM, are important building blocks for a number of numerical linear algebra routines. Parallelizing SpTRSV and SpTRSM on today's manycore platforms, such as GPUs, is not an easy task since computing a component of the solution may depend on previously computed components, enforcing a degree of sequential processing. As a consequence, most existing work introduces a preprocessing stage to partition the components into a group of level‐sets or colour‐sets so that components within a set are independent and can be processed simultaneously during the subsequent solution stage. However, this class of methods requires a long preprocessing time as well as significant runtime synchronization overheads between the sets. To address this, we propose in this paper novel approaches for SpTRSV and SpTRSM in which the ordering between components is naturally enforced within the solution stage. In this way, the cost for preprocessing can be greatly reduced, and the synchronizations between sets are completely eliminated. To further exploit the data‐parallelism, we also develop an adaptive scheme for efficiently processing multiple right‐hand sides in SpTRSM. A comparison with a state‐of‐the‐art library supplied by the GPU vendor, using 20 sparse matrices on the latest GPU device, shows that the proposed approach obtains an average speedup of over two for SpTRSV and up to an order of magnitude speedup for SpTRSM. In addition, our method is up to two orders of magnitude faster for the preprocessing stage than existing SpTRSV and SpTRSM methods.
- 9 August 2016
- Published by Springer Nature
- p. 617-630
A Synchronization-Free Algorithm for Parallel Sparse Triangular Solves
- 9 August 2016
- Published by Springer Nature
- p. 617-630
A Synchronization-Free Algorithm for Parallel Sparse Triangular Solves
- Open Access
- 1 June 2016
- Published by Association for Computing Machinery (ACM)
- p. 1-13
Parallel Transposition of Sparse Data Structures
Many applications in computational sciences and social sciences exploit sparsity and connectivity of acquired data. Even though many parallel sparse primitives such as sparse matrix-vector (SpMV) multiplication have been extensively studied, some other important building blocks, e.g., parallel transposition for sparse matrices and graphs, have not received the attention they deserve. In this paper, we first identify that the transposition operation can be a bottleneck of some fundamental sparse matrix and graph algorithms. Then, we revisit the performance and scalability of parallel transposition approaches on x86-based multi-core and many-core processors. Based on the insights obtained, we propose two new parallel transposition algorithms: ScanTrans and MergeTrans. The experimental results show that our ScanTrans method achieves an average of 2.8-fold (up to 6.2-fold) speedup over the parallel transposition in the latest vendor-supplied library on an Intel multi-core CPU platform, and the MergeTrans approach achieves on average of 3.4-fold (up to 11.7-fold) speedup on an Intel Xeon Phi many-core processor.
- 1 June 2016
- Published by Association for Computing Machinery (ACM)
- p. 1-13
Open AccessParallel Transposition of Sparse Data Structures
Many applications in computational sciences and social sciences exploit sparsity and connectivity of acquired data. Even though many parallel sparse primitives such as sparse matrix-vector (SpMV) multiplication have been extensively studied, some other important building blocks, e.g., parallel transposition for sparse matrices and graphs, have not received the attention they deserve. In this paper, we first identify that the transposition operation can be a bottleneck of some fundamental sparse matrix and graph algorithms. Then, we revisit the performance and scalability of parallel transposition approaches on x86-based multi-core and many-core processors. Based on the insights obtained, we propose two new parallel transposition algorithms: ScanTrans and MergeTrans. The experimental results show that our ScanTrans method achieves an average of 2.8-fold (up to 6.2-fold) speedup over the parallel transposition in the latest vendor-supplied library on an Intel multi-core CPU platform, and the MergeTrans approach achieves on average of 3.4-fold (up to 11.7-fold) speedup on an Intel Xeon Phi many-core processor.
- 1 November 2015
- Published by Elsevier in Journal of Parallel and Distributed Computing
- Vol. 85, 47-61
A framework for general sparse matrix–matrix multiplication on GPUs and heterogeneous processors
- 1 November 2015
- Published by Elsevier in Journal of Parallel and Distributed Computing
- Vol. 85, 47-61
A framework for general sparse matrix–matrix multiplication on GPUs and heterogeneous processors
- 1 November 2015
- Published by Elsevier in Parallel Computing
- Vol. 49, 179-193
Speculative segmented sum for sparse matrix-vector multiplication on heterogeneous processors
- 1 November 2015
- Published by Elsevier in Parallel Computing
- Vol. 49, 179-193
Speculative segmented sum for sparse matrix-vector multiplication on heterogeneous processors
- 1 January 2015
- Published by British Machine Vision Association and Society for Pattern Recognition
- p. 28.1-28.13
Unsupervised Behavior-Specific Dictionary Learning for Abnormal Event Detection
- 1 January 2015
- Published by British Machine Vision Association and Society for Pattern Recognition
- p. 28.1-28.13
Unsupervised Behavior-Specific Dictionary Learning for Abnormal Event Detection
- 1 May 2014
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 370-381
An Efficient GPU General Sparse Matrix-Matrix Multiplication for Irregular Data
General sparse matrix-matrix multiplication (SpGEMM) is a fundamental building block for numerous applications such as algebraic multigrid method, breadth first search and shortest path problem. Compared to other sparse BLAS routines, an efficient parallel SpGEMM algorithm has to handle extra irregularity from three aspects: (1) the number of the nonzero entries in the result sparse matrix is unknown in advance, (2) very expensive parallel insert operations at random positions in the result sparse matrix dominate the execution time, and (3) load balancing must account for sparse data in both input matrices. Recent work on GPU SpGEMM has demonstrated rather good both time and space complexity, but works best for fairly regular matrices. In this work we present a GPU SpGEMM algorithm that particularly focuses on the above three problems. Memory pre-allocation for the result matrix is organized by a hybrid method that saves a large amount of global memory space and efficiently utilizes the very limited on-chip scratchpad memory. Parallel insert operations of the nonzero entries are implemented through the GPU merge path algorithm that is experimentally found to be the fastest GPU merge approach. Load balancing builds on the number of the necessary arithmetic operations on the nonzero entries and is guaranteed in all stages. Compared with the state-of-the-art GPU SpGEMM methods in the CUSPARSE library and the CUSP library and the latest CPU SpGEMM method in the Intel Math Kernel Library, our approach delivers excellent absolute performance and relative speedups on a benchmark suite composed of 23 matrices with diverse sparsity structures.
- 1 May 2014
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 370-381
An Efficient GPU General Sparse Matrix-Matrix Multiplication for Irregular Data
General sparse matrix-matrix multiplication (SpGEMM) is a fundamental building block for numerous applications such as algebraic multigrid method, breadth first search and shortest path problem. Compared to other sparse BLAS routines, an efficient parallel SpGEMM algorithm has to handle extra irregularity from three aspects: (1) the number of the nonzero entries in the result sparse matrix is unknown in advance, (2) very expensive parallel insert operations at random positions in the result sparse matrix dominate the execution time, and (3) load balancing must account for sparse data in both input matrices. Recent work on GPU SpGEMM has demonstrated rather good both time and space complexity, but works best for fairly regular matrices. In this work we present a GPU SpGEMM algorithm that particularly focuses on the above three problems. Memory pre-allocation for the result matrix is organized by a hybrid method that saves a large amount of global memory space and efficiently utilizes the very limited on-chip scratchpad memory. Parallel insert operations of the nonzero entries are implemented through the GPU merge path algorithm that is experimentally found to be the fastest GPU merge approach. Load balancing builds on the number of the necessary arithmetic operations on the nonzero entries and is guaranteed in all stages. Compared with the state-of-the-art GPU SpGEMM methods in the CUSPARSE library and the CUSP library and the latest CPU SpGEMM method in the Intel Math Kernel Library, our approach delivers excellent absolute performance and relative speedups on a benchmark suite composed of 23 matrices with diverse sparsity structures.