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

16th Annual IEEE Symposium on Field-Programmable Custom Computing Machines

作者： DuBois, David DuBois, Andrew Connor, Carolyn Poole, Steve Los Alamos Natl Lab Los Alamos NM 87545 USA Oak Ridge Natl Lab Oak Ridge TN USA

ISBN: (纸本)9780769533070

Double precision floating point sparse matrix-vector multiplication (SMVM) is a critical computational kernel used in iterative solvers for systems of spare linear equations. The poor data locality exhibited by sparse matrices along with the high memory bandwith requirements of SMVM result in poor performance on general purpose processors. Field Programmable Gate Arrays (FPGAs) offer a possible alternative with their customizable and application-targeted memory sub-system and processing elements.

关键词： FPGA sparse matrix-vector multiplication Reconfigurable hardware Iterative methods

来源：评论

学校读者我要写书评

暂无评论

sparse matrix-vector multiplication on a Reconfigurable Supercomputer with Application

引用

ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS 2010年第1期3卷 2-2页

作者： Dubois, David Dubois, Andrew Boorman, Thomas Connor, Carolyn Poole, Steve Los Alamos Natl Lab Los Alamos NM 87545 USA Oak Ridge Natl Lab Oak Ridge TN 37831 USA

Double precision floating point sparse matrix-vector multiplication (SMVM) is a critical computational kernel used in iterative solvers for systems of sparse linear equations. The poor data locality exhibited by sparse matrices along with the high memory bandwidth requirements of SMVM result in poor performance on general purpose processors. Field Programmable Gate Arrays (FPGAs) offer a possible alternative with their customizable and application-targeted memory sub-system and processing elements. In this work we investigate two separate implementations of the SMVM on an SRC-6 MAPStation workstation. The first implementation investigates the peak performance capability, while the second implementation balances the amount of instantiated logic with the available sustained bandwidth of the FPGA subsystem. Both implementations yield the same sustained performance with the second producing a much more efficient solution. The metrics of processor and application balance are introduced to help provide some insight into the efficiencies of the FPGA and CPU based solutions explicitly showing the tight coupling of the available bandwidth to peak floating point performance. Due to the FPGAs ability to balance the amount of implemented logic to the available memory bandwidth it can provide a much more efficient solution. Finally, making use of the lessons learned implementing the SMVM, we present a fully implemented non-preconditioned Conjugate Gradient Algorithm utilizing the second SMVM design.

关键词： Performance Algorithms Design Accelerator architecture reconfigurable hybrid computing FPGA conjugate gradient sparse matrix-vector multiplication reconfigurable hardware iterative methods

来源：评论

学校读者我要写书评

暂无评论

A hybrid format for better performance of sparse matrix-vector multiplication on a GPU

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2016年第1期30卷 103-120页

作者： Guo, Dahai Gropp, William Olson, Luke N. Univ Illinois Natl Ctr Supercomp Applicat 1205 West Clark St Urbana IL 61801 USA Univ Illinois Dept Comp Sci 1304 W Springfield Ave Urbana IL 61801 USA

In this paper, we present a new sparse matrix data format that leads to improved memory coalescing and more efficient sparse matrix-vector multiplication for a wide range of problems on high-throughput architectures such as a GPU. The sparse matrix structure is constructed by sorting the rows based on the row length (defined as the number of non-zero elements in a matrix row) followed by a partition into two ranges, short rows and long rows. Based on this partition, the matrix entries are then transformed into ELLPACK or vectorized compressed sparse row format. In addition, the number of threads are adaptively selected by their row length, in order to balance the workload for each graphics processing unit thread. Several computational experiments are presented to support this approach and the results suggest a notable improvement over a wide range of matrix structures.

关键词： sparse matrix-vector multiplication graphics processing unit EVC-HYB format adaptive memory coalescing

来源：评论

学校读者我要写书评

暂无评论

An I/O Bandwidth-Sensitive sparse matrix-vector multiplication Engine on FPGAs

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2012年第1期59卷 113-123页

作者： Sun, Song Monga, Madhu Jones, Phillip H. Zambreno, Joseph Iowa State Univ Dept Elect & Comp Engn Ames IA 50010 USA

sparse matrix-vector multiplication (SMVM) is a fundamental core of many high-performance computing applications, including information retrieval, medical imaging, and economic modeling. While the use of reconfigurable computing technology in a high-performance computing environment has shown recent promise in accelerating a wide variety of scientific applications, existing SMVM architectures on FPGA hardware have been limited in that they require either numerous pipeline stalls during computation (due to zero padding) or excessive input preprocessing during run-time. For large-scale sparse matrix scenarios, both of these shortcomings can result in unacceptable performance overheads, limiting the overall value of using FPGAs in a high-performance computing environment. In this paper, we present a scalable and efficient FPGA-based SMVM architecture which can handle arbitrary matrix sparsity patterns without excessive preprocessing or zero padding and can be dynamically expanded based on the available I/O bandwidth. Our experimental results using a commercial FPGA-based acceleration system demonstrate that our reconfigurable SMVM engine is highly efficient, with benchmark-dependent speedups over an optimized software implementation that range from 3.5x to 6.5x in terms of computation time.

关键词： FPGA reconfigurable computing sparse matrix-vector multiplication

来源：评论

学校读者我要写书评

暂无评论

High-Level Strategies for Parallel Shared-Memory sparse matrix-vector multiplication

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2014年第1期25卷 116-125页

作者： Yzelman, Albert-Jan Nicholas Roose, Dirk Intel Labs Europe Flanders ExaSci Lab B-3001 Louvain Belgium Katholieke Univ Leuven Dept Comp Sci B-3001 Heverlee Belgium

The sparse matrix-vector multiplication is an important computational kernel, but is hard to efficiently execute even in the sequential case. The problems-namely low arithmetic intensity, inefficient cache use, and limited memory bandwidth-are magnified as the core count on shared-memory parallel architectures increases. Existing techniques are discussed in detail, and categorized chiefly based on their distribution types. Based on this, new parallelization techniques are proposed. The theoretical scalability and memory usage of the various strategies are analyzed, and experiments on multiple NUMA architectures confirm the validity of the results. One of the newly proposed methods attains the best average result in experiments on a large set of matrices. In one of the experiments it obtains a parallel efficiency of 90 percent, while on average it performs close to 60 percent.

关键词： sparse matrix-vector multiplication shared-memory parallelism cache-oblivious sparse matrix partitioning matrix reordering Hilbert space-filling curve high-performance computing NUMA architectures

来源：评论

学校读者我要写书评

暂无评论

CUDA-enabled sparse matrix-vector multiplication on GPUs using atomic operations

引用

PARALLEL COMPUTING 2013年第11期39卷 737-750页

作者： Dang, Hoang-Vu Schmidt, Bertil Johannes Gutenberg Univ Mainz Inst Informat D-55128 Mainz Germany

Existing formats for sparse matrix-vector multiplication (SpMV) on the GPU are outperforming their corresponding implementations on multi-core CPUs. In this paper, we present a new format called Sliced COO (SCOO) and an efficient CUDA implementation to perform SpMV on the GPU using atomic operations. We compare SCOO performance to existing formats of the NVIDIA Cusp library using large sparse matrices. Our results for single-precision floating-point matrices show that SCOO outperforms the COO and CSR format for all tested matrices and the HYB format for all tested unstructured matrices on a single GPU. Furthermore, our dual-GPU implementation achieves an efficiency of 94% on average. Due to the lower performance of existing CUDA-enabled GPUs for atomic operations on double-precision floating-point numbers the SCOO implementation for double-precision does not consistently outperform the other formats for every unstructured matrix. Overall, the average speedup of SCOO for the tested benchmark dataset is 3.33 (1.56) compared to CSR, 5.25 (2.42) compared to COO, 2.39 (1.37) compared to HYB for single (double) precision on a Tesla C2075. Furthermore, comparison to a Sandy-Bridge CPU shows that SCOO on a Fermi GPU outperforms the multi-threaded CSR implementation of the Intel MKL Library on an i7-2700 K by a factor between 5.5 (2.3) and 18 (12.7) for single (double) precision. (C) 2013 Elsevier B.V. All rights reserved.

关键词： GPU computing CUDA sparse matrices sparse matrix-vector multiplication Scientific programming

来源：评论

学校读者我要写书评

暂无评论

Optimization of Large-Scale sparse matrix-vector multiplication on Multi-GPU Systems

引用

ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION 2024年第4期21卷 1-24页

作者： Gao, Jianhua Ji, Weixing Wang, Yizhuo Beijing Normal Univ Sch Artificial Intelligence Beijing Peoples R China Beijing Inst Technol Sch Comp Sci & Technol Beijing Peoples R China

sparse matrix-vector multiplication (SpMV) is one of the important kernels of many iterative algorithms for solving sparse linear systems. The limited storage and computational resources of individual GPUs restrict both the scale and speed of SpMV computing in problem-solving. As real-world engineering problems continue to increase in complexity, the imperative for collaborative execution of iterative solving algorithms across multiple GPUs is increasingly apparent. Although the multi-GPU-based SpMV takes less kernel execution time, it also introduces additional data transmission overhead, which diminishes the performance gains derived from parallelization across multi-GPUs. Based on the non-zero elements distribution characteristics of sparse matrices and the tradeoff between redundant computations and data transfer overhead, this article introduces a series of SpMV optimization techniques tailored for multi-GPU environments and effectively enhances the execution efficiency of iterative algorithms on multiple GPUs. First, we propose a two-level non-zero elements-based matrix partitioning method to increase the overlap of kernel execution and data transmission. Then, considering the irregular non-zero elements distribution in sparse matrices, a long-row- aware matrix partitioning method is proposed to hide more data transmissions. Finally, an optimization using redundant and inexpensive short-row execution to exchange costly data transmission is proposed. Our experimental evaluation demonstrates that, compared with the SpMV on a single GPU, the proposed method achieves an average speedup of 2.00x and 1.85x on platforms equipped with two RTX 3090 and two Tesla V100-SXM2, respectively. The average speedup of 2.65x is achieved on a platform equipped with four Tesla V100-SXM2.

关键词： Multi-GPU system sparse matrix-vector multiplication data transmission hiding sparse matrix partitioning

来源：评论

学校读者我要写书评

暂无评论

Efficient sparse matrix-vector multiplication using cache oblivious extension quadtree storage format

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2016年 54卷 490-500页

作者： Zhang, Jilin Wan, Jian Li, Fangfang Mao, Jie Zhuang, Li Yuan, Junfeng Liu, Enyi Yu, Zhuoer Hangzhou Dianzi Univ Sch Comp Sci & Technol Hangzhou 310018 Zhejiang Peoples R China Minist Educ Key Lab Complex Syst Modeling & Simulat Beijing Peoples R China Zhejiang Prov Engn Ctr Media Data Cloud Proc & An Hangzhou 310018 Zhejiang Peoples R China Hangzhou Dianzi Univ Sch Mech Engn Hangzhou 310018 Zhejiang Peoples R China

In this paper, we elaborate on improving the sparse matrix storage format to optimize the data locality of sparse matrix-vector multiplication (SpMVM) algorithm, and its parallel performance. First of all, we propose a cache oblivious extension quadtree storage structure (COEQT), in which the sparse matrix is recursively divided into sub-regions that can well fit into cache to improve the data locality. Later on, we present a COEQT based SpMVM algorithm and optimize its performance through manual vectorization. With this storage format, the original SpMVM is divided into computations of relatively independent small matrices. In addition, this region-based computation framework is also suitable for high performance computing in distributed computing environment. So, we finally present a parallel SpMVM algorithm based on the proposed COEQT. Extensive and comprehensive experiments show that the sparse matrix-vector multiplication using the COEQT storage format achieves on average 1.1-1.5x speedup compared with CSR format and further higher performance through instruction level optimization techniques. The experiment in Lenovo Deepcomp 7000 demonstrates that this method achieves on average 1.63x speedup compared with the Intel Cluster Math Kernel Library implementation. (C) 2015 Elsevier B.V. All rights reserved.

关键词： sparse matrix-vector multiplication sparse matrix storage Data locality Cache oblivious Extension quadtree Distributed parallelism

来源：评论

学校读者我要写书评

暂无评论

A Performance Modeling and Optimization Analysis Tool for sparse matrix-vector multiplication on GPUs

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2014年第5期25卷 1112-1123页

作者： Guo, Ping Wang, Liqiang Chen, Po Univ Wyoming Dept Comp Sci Dept 3315 Laramie WY 82071 USA Univ Wyoming Dept Geol & Geophys Dept 3006 Laramie WY 82071 USA

This paper presents a performance modeling and optimization analysis tool to predict and optimize the performance of sparse matrix-vector multiplication (SpMV) on GPUs. We make the following contributions: 1) We present an integrated analytical and profile-based performance modeling to accurately predict the kernel execution times of CSR, ELL, COO, and HYB SpMV kernels. Our proposed approach is general, and neither limited by GPU programming languages nor restricted to specific GPU architectures. In this paper, we use CUDA-based SpMV kernels and NVIDIA Tesla C2050 for our performance modeling and experiments. According to our experiments, for 77 out of 82 test cases, the performance differences between the predicted and measured execution times are less than 9 percent;for the rest five test cases, the differences are between 9 and 10 percent. For CSR, ELL, COO, and HYB SpMV CUDA kernels, the average differences are 6.3, 4.4, 2.2, and 4.7 percent, respectively. 2) Based on the performance modeling, we design a dynamic-programming based SpMV optimal solution auto-selection algorithm to automatically report an optimal solution (i.e., optimal storage strategy, storage format(s), and execution time) for a target sparse matrix. In our experiments, the average performance improvements of the optimal solutions are 41.1, 49.8, and 37.9 percent, compared to NVIDIA's CSR, COO, and HYB CUDA kernels, respectively.

关键词： Performance modeling sparse matrix-vector multiplication GPU CUDA

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of the sparse matrix-vector multiplication on modern architectures

引用

JOURNAL OF SUPERCOMPUTING 2009年第1期50卷 36-77页

作者： Goumas, Georgios Kourtis, Kornilios Anastopoulos, Nikos Karakasis, Vasileios Koziris, Nectarios Natl Tech Univ Athens Comp Syst Lab Sch Elect & Comp Engn Zografos 15780 Greece

In this paper, we revisit the performance issues of the widely used sparse matrix-vector multiplication (SpMxV) kernel on modern microarchitectures. Previous scientific work reports a number of different factors that may significantly reduce performance. However, the interaction of these factors with the underlying architectural characteristics is not clearly understood, a fact that may lead to misguided, and thus unsuccessful attempts for optimization. In order to gain an insight into the details of SpMxV performance, we conduct a suite of experiments on a rich set of matrices for three different commodity hardware platforms. In addition, we investigate the parallel version of the kernel and report on the corresponding performance results and their relation to each architecture's specific multithreaded configuration. Based on our experiments, we extract useful conclusions that can serve as guidelines for the optimization process of both single and multithreaded versions of the kernel.

关键词： sparse matrix-vector multiplication Multicore architectures Scientific applications Performance evaluation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：