Lecture 8:Parallel Sparse Methods 1
Lecture 8: Parallel Sparse Methods 1
Objective To learn to regularize irregular data with Limiting variations with clamping Sorting Transposition To learn to write a high-performance SpMV kernel based on JDS transposed format To learn the key techniques for compacting input data in parallel sparse methods for reduced consumption of memory bandwidth Better utilization of on-chip memory Fewer bytes transferred to on-chip memory Better utilization of global memory Challenge:retaining regularity 2
Objective • To learn to regularize irregular data with – Limiting variations with clamping – Sorting – Transposition • To learn to write a high-performance SpMV kernel based on JDS transposed format • To learn the key techniques for compacting input data in parallel sparse methods for reduced consumption of memory bandwidth – Better utilization of on-chip memory – Fewer bytes transferred to on-chip memory – Better utilization of global memory – Challenge: retaining regularity 2
Sparse Matrix Many real-world systems are sparse in nature Linear systems described as sparse matrices Solving sparse linear systems Traditional inversion algorithms such as Gaussian elimination can create too many "fill-in"elements and explode the size of the matrix Iterative Conjugate Gradient solvers based on sparse matrix-vector multiplication is preferred Solution of PDE systems can be formulated into linear operations expressed as sparse matrix- vector multiplication 3
Sparse Matrix • Many real-world systems are sparse in nature – Linear systems described as sparse matrices • Solving sparse linear systems – Traditional inversion algorithms such as Gaussian elimination can create too many “fill-in” elements and explode the size of the matrix – Iterative Conjugate Gradient solvers based on sparse matrix-vector multiplication is preferred • Solution of PDE systems can be formulated into linear operations expressed as sparse matrixvector multiplication 3
Sparse Data Motivation for Compaction Many real-world inputs are sparse/non-uniform Signal samples, mesh models, transportation networks, communication networks,etc. 4
Sparse Data Motivation for Compaction ▪ Many real-world inputs are sparse/non-uniform ▪ Signal samples, mesh models, transportation networks, communication networks, etc. 4
Sparse Matrix in Analytics and Al Recommender systems Natural language processing Predict missing ratings Latent semantic model Group similar users/items Word embedding as input to DNN Complex network Matrix Deep learning Link prediction Factorization Model compression Vertices clustering Embedding layer Web search Tensor decomposition Match query and document In machine learning and HPC applications items X Ratings (R) sasn R NETFLIX n items amazon.com Quora Music Spotify 5
Sparse Matrix in Analytics and AI Predict missing ratings Group similar users/items Match query and document In machine learning and HPC applications Matrix Link prediction Factorization Vertices clustering Latent semantic model Word embedding as input to DNN Recommender systems Complex network Web search Natural language processing Tensor decomposition Model compression Embedding layer Deep learning Ratings (R) n items m users * * * * * * * * ≈ x Users items T x T u v X f f R 5