检索结果-内蒙古大学图书馆

Heterogeneous sparse matrix-vector multiplication via compressed sparse row format

PARALLEL COMPUTING 2023年 115卷

作者： Lane, Phillip Allen Booth, Joshua Dennis Univ Alabama 301 Sparkman Dr NW Huntsville AL 35899 USA

sparse matrix-vector multiplication (SpMV) is one of the most important kernels in high-performance computing (HPC), yet SpMV normally suffers from ill performance on many devices. Due to ill performance, SpMV normally requires special care to store and tune for a given device. Moreover, HPC is facing heterogeneous hardware containing multiple different compute units, e.g., many-core CPUs and GPUs. Therefore, an emerging goal has been to produce heterogeneous formats and methods that allow critical kernels, e.g., SpMV, to be executed on different devices with portable performance and minimal changes to format and method. This paper presents a heterogeneous format based on CSR, named CSR-k, that can be tuned quickly and outperforms the average performance of Intel MKL on Intel Xeon Platinum 838 and AMD Epyc 7742 CPUs while still outperforming NVIDIA's cusparse and Sandia National Laboratories' KokkosKernels on NVIDIA A100 and V100 for regular sparse matrices, i.e., sparse matrices where the number of nonzeros per row has a variance <= 10, such as those commonly generated from two and three-dimensional finite difference and element problems. In particular, CSR-k achieves this with reordering and by grouping rows into a hierarchical structure of super-rows and super-super-rows that are represented by just a few extra arrays of pointers. Due to its simplicity, a model can be tuned for a device, and this model can be used to select super-row and super-super-rows sizes in constant time.

关键词： sparse linear algebra sparse matrix vector multiplication GPU Heterogenous OpenMP CUDA

来源：评论

学校读者我要写书评

暂无评论

Conflict-Free Symmetric sparse matrix-vector multiplication on Multicore Architectures 19

Conflict-Free Symmetric Sparse Matrix-Vector Multiplication ...

引用

International Conference for High Performance Computing, Networking, Storage and Analysis (SC)

作者： Elafrou, Athena Goumas, Georgios Koziris, Nectarios Natl Tech Univ Athens Comp Syst Lab Athens Greece

ISBN: (数字)9781450362290

ISBN: (纸本)9781450362290

Exploiting the numeric symmetry in sparse matrices to reduce their memory footprint is very tempting for optimizing the memory-bound sparse matrix-vector multiplication (SpMV) kernel. Despite being very beneficial for serial computation, storing the upper or lower triangular part of the matrix introduces race conditions in the updates to the output vector in a parallel execution. Previous work has suggested using local, per-thread vectors to circumvent this problem, introducing a work-inefficient reduction step that limits the scalability of SpMV. In this paper, we address this issue with Conflict-Free Symmetric (CFS) SpMV, an optimization strategy that organizes the parallel computation into phases of conflict-free execution. We identify such phases through graph coloring and propose heuristics to improve the coloring quality for SpMV in terms of load balancing and locality to the input and output vectors. We evaluate our approach on two multicore shared-memory systems and demonstrate improved performance over the state-of-the-art.

关键词： symmetric sparse matrices sparse linear algebra sparse matrix vector multiplication conjugate gradient

来源：评论

学校读者我要写书评

暂无评论

Adaptive Optimization of sparse matrix-vector multiplication on Emerging Many-Core Architectures 20

Adaptive Optimization of Sparse Matrix-Vector Multiplication...

引用

20th IEEE International Conference on High Performance Computing and Communications (HPCC) / 16th IEEE International Conference on Smart City (SmartCity) / 4th IEEE International Conference on Data Science and Systems (DSS)

作者： Chen, Shizhao Fang, Jianbin Chen, Donglin Xu, Chuanfu Wang, Zheng China Aerodynam Res & Dev Ctr State Key Lab Aerodynam Chengdu Sichuan Peoples R China Natl Univ Def Technol Coll Comp Changsha Hunan Peoples R China Univ Lancaster MetaLab Sch Comp & Commun Lancaster England Northwest Univ Sch Informat Sci & Technol Xian Shaanxi Peoples R China Xian Univ Posts & Telecommun Sch Comp Sci & Technol Xian Shaanxi Peoples R China

ISBN: (纸本)9781538666142

sparse matrix vector multiplication (SpMV) is one of the most common operations in scientific and high-performance applications, and is often responsible for the application performance bottleneck. While the sparse matrix representation has a significant impact on the resulting application performance, choosing the right representation typically relies on expert knowledge and trial and error. This paper provides the first comprehensive study on the impact of sparse matrix representations on two emerging many-core architectures: the Intel's Knights Landing (KNL) XeonPhi and the ARM-based FT-2000Plus (FTP). Our large-scale experiments involved over 9,500 distinct profiling runs performed on 956 sparse datasets and five mainstream SpMV representations. We show that the best sparse matrix representation depends on the underlying architecture and the program input. To help developers to choose the optimal matrix representation, we employ machine learning to develop a predictive model. Our model is first trained offline using a set of training examples. The learned model can be used to predict the best matrix representation for any unseen input for a given architecture. We show that our model delivers on average 95% and 91% of the best available performance on KNL and FTP respectively, and it achieves this with no runtime profiling overhead.

关键词： sparse matrix vector multiplication Performance optimization Many-Cores Performance analysis

来源：评论

学校读者我要写书评

暂无评论

Image Convolution Optimization Using sparse matrix vector multiplication Technique 5

Image Convolution Optimization Using Sparse Matrix Vector Mu...

引用

International Conference on Advances in Computing, Communications and Informatics (ICACCI)

作者： Bipin, B. Nair, Jyothisha J. Amrita Vishwa Vidyapeetham Amrita Sch Engn Dept Comp Sci & Engn Amritapuri Campus Kollam India

ISBN: (纸本)9781509020287

Image convolution is an integral operator in the field of digital image processing. For any operation to be processed in images say whether it is edge detection, image smoothing, image blurring, etc. process of convolution comes into picture. Generally in image processing the convolution is done by using a mask known as the kernel. As the values of the kernel is changed the operation on image also changes. For each operation, the kernel will be different. In the conventional way of image convolution, the number of multiplications are very high. Thereby the time complexity is also high. In this paper, a new and efficient method is proposed to do convolution on the images with lesser time complexity. We exploit the sub matrix structure of the kernel matrix and systematically assign the values to a new H matrix. Since the produced H matrix is a spare matrix, the output is realized here by using sparse matrix vector multiplication technique. Compressed Row Storage format (CSR) is the format that is used here for the sparse matrix vector multiplication (SMVM) technique. Using the CSR format with sparse matrix vector multiplication technique, convolution processes achieves 3.4 times and 2.4 times faster than conventional methods for image smoothing and edge detection operations respectively.

关键词： sparse matrix convolution sparse matrix vector multiplication Compressed Row Storage Format

来源：评论

学校读者我要写书评

暂无评论

Image Convolution Optimization Using sparse matrix vector multiplication Technique

Image Convolution Optimization Using Sparse Matrix Vector Mu...

引用

International Conference on Advances in Computing, Communications and Informatics

作者： Bipin, B. Jyothisha J. Nair Department of Computer Science and Engineering Amrita School of Engineering Amrita Vishwa Vidyapeetham Amritapuri Campus Kollam India

ISBN: (纸本)9781509020300

关键词： sparse matrix Convolution sparse matrix vector multiplication Compressed Row Storage Format

来源：评论

学校读者我要写书评

暂无评论

A High Memory Bandwidth FPGA Accelerator for sparse matrix-vector multiplication 22

A High Memory Bandwidth FPGA Accelerator for Sparse Matrix-V...

引用

22nd IEEE Annual International Symposium on Field-Programmable Custom Computing Machines ((FCCM)

作者： Fowers, Jeremy Ovtcharov, Kalin Strauss, Karin Chung, Eric S. Stitt, Greg Univ Florida Dept Elect & Comp Engn Gainesville FL 32611 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781479951116

sparse matrix-vector multiplication (SMVM) is a crucial primitive used in a variety of scientific and commercial applications. Despite having significant parallelism, SMVM is a challenging kernel to optimize due to its irregular memory access characteristics. Numerous studies have proposed the use of FPGAs to accelerate SMVM implementations. However, most prior approaches focus on parallelizing multiply-accumulate operations within a single row of the matrix (which limits parallelism if rows are small) and/or make inefficient uses of the memory system when fetching matrix and vector elements. In this paper, we introduce an FPGA-optimized SMVM architecture and a novel sparse matrix encoding that explicitly exposes parallelism across rows, while keeping the hardware complexity and on-chip memory usage low. This system compares favorably with prior FPGA SMVM implementations. For the over 700 University of Florida sparse matrices we evaluated, it also performs within about two thirds of CPU SMVM performance on average, even though it has 2.4x lower DRAM memory bandwidth, and within almost one third of GPU SVMV performance on average, even at 9x lower memory bandwidth. Additionally, it consumes only 25W, for power efficiencies 2.6x and 2.3x higher than CPU and GPU, respectively, based on maximum device power.

关键词： sparse matrix vector multiplication FPGA accelerator SPMV SMVM reconfigurable computing HPC

来源：评论

学校读者我要写书评

暂无评论

MPI-CUDA sparse matrix-vector multiplication for the conjugate gradient method with an approximate inverse preconditioner

引用

COMPUTERS & FLUIDS 2014年第0期92卷 244-252页

作者： Oyarzun, G. Borrell, R. Gorobets, A. Oliva, A. Tech Univ Catalonia ETSEIAT Heat & Mass Transfer Technol Ctr Terrassa 08222 Spain Termo Fluids SL Sabadell 08204 Barcelona Spain RAS MV Keldysh Appl Math Inst Moscow 125047 Russia

The preconditioned conjugate gradient (PCG) is one of the most prominent iterative methods for the solution of sparse linear systems with symmetric and positive definite matrix that arise, for example, in the modeling of incompressible flows. The method relies on a set of basic linear algebra operations which determine the overall performance. Therefore, to achieve improvements in the performance, implementations of these basic operations must be adapted to the changes in the architecture of parallel computing systems. In the last years, one of the strategies to increase the computing power of supercomputers has been the usage of Graphics Processing Units (GPUs) as math co-processors in addition to CPUs. This paper presents a MPI-CUDA implementation of the PCG solver for such hybrid computing systems composed of multiple CPUs and CPUs. Special attention has been paid to the sparse matrix-vector multiplication (SpMV), because most of the execution time of the solver is spent on this operation. The approximate inverse preconditioner, which is used to improve the convergence of the CG solver, is also based on the SpMV operation. An overlapping of data transfer and computations is proposed in order to hide the MPI and the CPU-GPU communications needed to perform parallel SpMVs. This strategy has shown a considerable improvement and, as a result, the hybrid implementation of the PCG solver has demonstrated a significant speedup compared to the CPU-only implementation. (C) 2014 Published by Elsevier Ltd.

关键词： MPI-CUDA sparse matrix vector multiplication Conjugate gradient Approximate inverse preconditioner CPU

来源：评论

学校读者我要写书评

暂无评论

Improving the Performance of the Symmetric sparse matrix-vector multiplication in Multicore

Improving the Performance of the Symmetric Sparse Matrix-Vec...

引用

IEEE 27th International Parallel and Distributed Processing Symposium (IPDPS)

作者： Gkountouvas, Theodoros Karakasis, Vasileios Kourtis, Kornilios Goumas, Georgios Koziris, Nectarios Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Natl Tech Univ Athens Sch Elect & Comp Engn Athens Greece ETH Dept Comp Sci Zurich Switzerland

ISBN: (纸本)9780769549712

Symmetric sparse matrices arise often in the solution of sparse linear systems. Exploiting the non-zero element symmetry in order to reduce the overall matrix size is very tempting for optimizing the symmetric sparse matrix-vector multiplication kernel (SpMxV) for multicore architectures. Despite being very beneficial for the single-threaded execution, not storing the upper or lower triangular part of a symmetric sparse matrix complicates the multithreaded SpMxV version, since it introduces an undesirable dependency on the output vector elements. The most common approach for overcoming this problem is to use local, per-thread vectors, which are reduced to the output vector at the end of the computation. However, this reduction leads to considerable memory traffic, limiting the scalability of the symmetric SpMxV. In this paper, we take a two-step approach in optimizing the symmetric SpMxV kernel. First, we introduce the CSX-Sym variant of the highly compressed CSX format, which exploits the non-zero element symmetry for compressing further the input matrix. Second, we minimize the memory traffic produced by the local vectors reduction phase by implementing a non-zero indexing compression scheme that minimizes the local data to be reduced. Our indexing scheme allowed the scaling of symmetric SpMxV and provided a more than 2x performance improvement over the baseline CSR implementation and 83.9% over the typical symmetric SpMxV kernel. The CSX-Sym variant has further increased the symmetric SpMxV performance by 43.4%. Finally, we evaluate the effect of our optimizations in the context of the CG iterative method, where we achieve an 77.8% acceleration of the overall solver.

关键词： sparse matrix vector multiplication symmetric sparse matrices multicore optimization compression SpMV

来源：评论

学校读者我要写书评

暂无评论

AdELL: An Adaptive Warp-Balancing ELL Format for Efficient sparse matrix-vector multiplication on GPUs

AdELL: An Adaptive Warp-Balancing ELL Format for Efficient S...

引用

42nd Annual International Conference on Parallel Processing (ICPP)

作者： Maggioni, Marco Berger-Wolf, Tanya Univ Illinois Dept Comp Sci Chicago IL 60607 USA

ISBN: (纸本)9780769551173

The sparse matrix-vector multiplication (SpMV) is a fundamental computational kernel used in science and engineering. As a result, the performance of a large number of applications depends on the efficiency of the SpMV. This kernel is, in fact, a bandwidth-limited operation and poses a challenge for optimization when the matrix has an irregular structure. The literature on implementing SpMV on throughput-oriented manycore processors is extensive and mostly focuses on matrix formats, proposing different ideas to adapt matrix sparsity to the underlying architecture. In this paper, we propose a novel ELL-based matrix format called Adaptive ELL (AdELL) to improve the state-of-the-art of the SpMV on Graphic Processing Units (GPUs). The AdELL format is based on the idea of distributing working threads to rows according to their computational load, creating balanced hardware-level blocks (warps) that take full advantage of the vectorized execution on Streaming Multiprocessors (SMs). The AdELL data structure is created using a novel warp-balancing heuristic designed to smooth the workload among warps without the need of tuning any parameters. AdELL provides an efficient warp-level synchronization (as opposed to block-level) but can also use atomic operations to distribute very skewed rows over multiple warps. Moreover, we introduce a loop unrolling heuristic that optimizes the SpMV performance by selecting the best unrolling factor based on the warp workload. We tested the proposed AdELL sparse format on a set of conventional benchmarks from heterogeneous application domains. The results show substantial and consistent performance improvements for double-precision calculations, outperforming the state-of-the-art ensemble framework clSpMV. We could observe speedup peaks up to 1.94 and a 25% (geometric) average improvement, which can be potentially increased to 43% introducing a simple 1x2 blocking strategy.

关键词： Adaptive ELL GPU sparse matrix vector multiplication Warp-Balancing

来源：评论

学校读者我要写书评

暂无评论

An asynchronous and parallel row-wise compressed SpMV kernel on heterogeneous CPU-GPU architectures

引用

INTERNATIONAL JOURNAL OF EMBEDDED SYSTEMS 2022年第5期15卷 377-384页

作者： Tan, Huachen Hunan Agr Univ Dept Internet Changsha Hunan Peoples R China

sparse matrix vector multiplication (SpMV) is a fundamental and important algebra used extensively in various fields, such as machine learning, data mining and numerical simulation. Accelerating SpMV benefits the corresponding real-world applications. Meanwhile, heterogeneous CPU-GPU architectures are inevitable to realise high-performance computing. Therefore, this paper designs an asynchronous parallel row-wise compressed SpMV kernel by utilising the heterogeneous CPU-GPU architectures to accelerate applications that use SpMV. First, according to the memory access and control flow of SpMV and the architectural features of the heterogeneous CPU-GPU systems, the heterogeneous parallelisation of the row-wise compressed SpMV based on CSR format is designed. Next, an asynchronous method is designed for the parallel compressed SpMV kernel to create an additional level of parallelism in SpMV execution. The proposed SpMV kernel can obtain up to 8.97% improvement from the asynchronous method on the heterogeneous CPU-GPU architecture and perform the nearly linear speedup across GPU threads.

关键词： heterogeneous CPU-GPU architectures parallel sparse matrix vector multiplication SpMV

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：