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

sparse matrix partitioning for optimizing SpMV on CPU-GPU heterogeneous platforms

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2020年第1期34卷 66-80页

作者： Benatia, Akrem Ji, Weixing Wang, Yizhuo Shi, Feng Beijing Inst Technol Sch Comp Sci & Technol 5 South Zhongguancun St Beijing 100081 Peoples R China

sparse matrix-vector multiplication (SpMV) kernel dominates the computing cost in numerous applications. Most of the existing studies dedicated to improving this kernel have been targeting just one type of processing units, mainly multicore CPUs or graphics processing units (GPUs), and have not explored the potential of the recent, rapidly emerging, CPU-GPU heterogeneous platforms. To take full advantage of these heterogeneous systems, the input sparse matrix has to be partitioned on different available processing units. The partitioning problem is more challenging with the existence of many sparse formats whose performances depend both on the sparsity of the input matrix and the used hardware. Thus, the best performance does not only depend on how to partition the input sparse matrix but also on which sparse format to use for each partition. To address this challenge, we propose in this article a new CPU-GPU heterogeneous method for computing the SpMV kernel that combines between different sparse formats to achieve better performance and better utilization of CPU-GPU heterogeneous platforms. The proposed solution horizontally partitions the input matrix into multiple block-rows and predicts their best sparse formats using machine learning-based performance models. A mapping algorithm is then used to assign the block-rows to the CPU and GPU(s) available in the system. Our experimental results using real-world large unstructured sparse matrices on two different machines show a noticeable performance improvement.

关键词： sparse matrix-vector multiplication (SpMV) CPU-GPU heterogeneous platforms sparse matrix partitioning

来源：评论

学校读者我要写书评

暂无评论

A parallel direct method circuit simulator based on sparse matrix partitioning

引用

COMPUTERS & ELECTRICAL ENGINEERING 1998年第6期24卷 385-404页

作者： Wu, KY Ng, PKH Jia, XD Chen, RMM Layfield, AM City Univ Hong Kong Dept Elect Engn 83 Tat Chee Ave Kowloon Peoples R China

Solving a system of linear simultaneous equations representing an electrical circuit is one of the most time consuming tasks for large scale circuit simulations. In order to facilitate a multiprocessor implementation of the circuit simulation program SPICE, decomposition algorithms should be employed to partition a sparse matrix equation of the overall circuit into a number of subcircuit equations for parallel processing. In this paper, the performance of a parallel direct method matrix equation solving routine was studied in several contexts: the theoretical lower bound on performance was derived and the tradeoff between parallelism and communication is presented;various implementation and performance tuning issuing is also reported. This routine is written in such a manner that the data structure is compatible with SPICE Version 3c1. The speedup obtained from the simulation of two test circuits on a message passing multiprocessor system built on Transputers will be reported. Finally, the factors affecting the performance of the multiprocessor system are outlined and the overheads affecting the system performance in the implementation are identified. (C) 1998 Elsevier Science Ltd. All rights reserved.

关键词： circuit simulator sparse matrix partitioning sparse matrix equation parallel direct method

来源：评论

学校读者我要写书评

暂无评论

ON TWO-DIMENSIONAL sparse matrix partitioning: MODELS, METHODS, AND A RECIPE

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2010年第2期32卷 656-683页

作者： Catalyurek, Umit V. Aykanat, Cevdet Ucar, Bora Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Bilkent Univ Dept Comp Engn Ankara Turkey Univ Lyon ENS Lyon CNRS Lab Informat ParallelismeUMRINRIAUCBL F-69364 Lyon 7 France

We consider two-dimensional partitioning of general sparse matrices for parallel sparse matrix-vector multiply operation. We present three hypergraph-partitioning-based methods, each having unique advantages. The first one treats the nonzeros of the matrix individually and hence produces fine-grain partitions. The other two produce coarser partitions, where one of them imposes a limit on the number of messages sent and received by a single processor, and the other trades that limit for a lower communication volume. We also present a thorough experimental evaluation of the proposed two-dimensional partitioning methods together with the hypergraph-based one-dimensional partitioning methods, using an extensive set of public domain matrices. Furthermore, for the users of these partitioning methods, we present a partitioning recipe that chooses one of the partitioning methods according to some matrix characteristics.

关键词： sparse matrix partitioning parallel matrix-vector multiplication hypergraph partitioning two-dimensional partitioning combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

Reducing latency cost in 2D sparse matrix partitioning models

引用

PARALLEL COMPUTING 2016年第0期57卷 1-24页

作者： Selvitopi, Oguz Aykanat, Cevdet Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey

sparse matrix partitioning is a common technique used for improving performance of parallel linear iterative solvers. Compared to solvers used for symmetric linear systems, solvers for nonsymmetric systems offer more potential for addressing different multiple communication metrics due to the flexibility of adopting different partitions on the input and output vectors of sparse matrix-vector multiplication operations. In this regard, there exist works based on one-dimensional (1D) and two-dimensional (2D) fine-grain partitioning models that effectively address both bandwidth and latency costs in nonsymmetric solvers. In this work, we propose two new models based on 2D checkerboard and jagged partitioning. These models aim at minimizing total message count while maintaining a balance on communication volume loads of processors;hence, they address both bandwidth and latency costs. We evaluate all partitioning models on two nonsymmetric system solvers implemented using the widely adopted PETSc toolkit and conduct extensive experiments using these solvers on a modern system (a BlueGene/Q machine) successfully scaling them up to 8K processors. Along with the proposed models, we put practical aspects of eight evaluated models (two ID- and six 2D-based) under thorough analysis. To the best of our knowledge, this is the first work that analyzes practical performance of 2D models on this scale. Among evaluated models, the models that rely on 2D jagged partitioning obtain the most promising results by striking a balance between minimizing bandwidth and latency costs. (C) 2016 Published by Elsevier B.V.

关键词： Parallel iterative solvers Nonsymmetric linear systems sparse matrix-vector multiplication sparse matrix partitioning Latency overhead Bandwidth overhead

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Site-Based partitioning and Repartitioning Techniques for Parallel PageRank Computation

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2011年第5期22卷 786-802页

作者： Cevahir, Ali Aykanat, Cevdet Turk, Ata Barla Cambazoglu, B. Tokyo Inst Technol Tokyo 152 Japan Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey Yahoo Res Barcelona Lab Barcelona Spain

The PageRank algorithm is an important component in effective web search. At the core of this algorithm are repeated sparse matrix-vector multiplications where the involved web matrices grow in parallel with the growth of the web and are stored in a distributed manner due to space limitations. Hence, the PageRank computation, which is frequently repeated, must be performed in parallel with high-efficiency and low-preprocessing overhead while considering the initial distributed nature of the web matrices. Our contributions in this work are twofold. We first investigate the application of state-of-the-art sparse matrix partitioning models in order to attain high efficiency in parallel PageRank computations with a particular focus on reducing the preprocessing overhead they introduce. For this purpose, we evaluate two different compression schemes on the web matrix using the site information inherently available in links. Second, we consider the more realistic scenario of starting with an initially distributed data and extend our algorithms to cover the repartitioning of such data for efficient PageRank computation. We report performance results using our parallelization of a state-of-the-art PageRank algorithm on two different PC clusters with 40 and 64 processors. Experiments show that the proposed techniques achieve considerably high speedups while incurring a preprocessing overhead of several iterations (for some instances even less than a single iteration) of the underlying sequential PageRank algorithm.

关键词： PageRank sparse matrix-vector multiplication web search parallelization sparse matrix partitioning graph partitioning hypergraph partitioning repartitioning

来源：评论

学校读者我要写书评

暂无评论

1.5D PARALLEL sparse matrix-VECTOR MULTIPLY

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2018年第1期40卷 C25-C46页

作者： Kayaaslan, Enver Aykanat, Cevdet Ucar, Bora NTENT Inc 1808 Aston Ave Carlsbad CA 92008 USA Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey ENS Lyon CNRS 46 Allee Italie F-69364 Lyon France ENS Lyon CNRS LIP UMR5668INRIAUCBL 46 Allee Italie F-69364 Lyon France

There are three common parallel sparse matrix-vector multiply algorithms: 1D row-parallel, 1D column-parallel, and 2D row-column-parallel. The 1D parallel algorithms offer the advantage of having only one communication phase. On the other hand, the 2D parallel algorithm is more scalable, but it suffers from two communication phases. Here, we introduce a novel concept of heterogeneous messages where a heterogeneous message may contain both input-vector entries and partially computed output-vector entries. This concept not only leads to a decreased number of messages but also enables fusing the input- and output-communication phases into a single phase. These findings are exploited to propose a 1.5D parallel sparse matrix-vector multiply algorithm which is called local row-column-parallel. This proposed algorithm requires a constrained fine-grain partitioning in which each fine-grain task is assigned to the processor that contains either its input vector entry, its output-vector entry, or both. We propose two methods to carry out the constrained fine-grain partitioning. We conduct our experiments on a large set of test matrices to evaluate the partitioning qualities and partitioning times of these proposed 1.5D methods.

关键词： sparse matrix partitioning parallel sparse matrix-vector multiplication directed hypergraph model bipartite vertex cover combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

On partitioning Problems with Complex Objectives

On Partitioning Problems with Complex Objectives

引用

17th International Euro-Par Conference on Parallel Processing

作者： Kaya, Kamer Rouet, Francois-Henry Ucar, Bora CERFACS F-31057 Toulouse France Univ Toulouse INPT ENSEEIHT IRIT Toulouse France CNRS F-75700 Paris France ENS Lyon Lyon France

ISBN: (纸本)9783642297373;9783642297366

Hypergraph and graph partitioning tools are used to partition work for efficient parallelization of many sparse matrix computations. Most of the time, the objective function that is reduced by these tools relates to reducing the communication requirements, and the balancing constraints satisfied by these tools relate to balancing the work or memory requirements. Sometimes, the objective sought for having balance is a complex function of a partition. We mention some important class of parallel sparse matrix computations that have such balance objectives. For these cases, the current state of the art partitioning tools fall short of being adequate. To the best of our knowledge, there is only a single algorithmic framework in the literature to address such balance objectives. We propose another algorithmic framework to tackle complex objectives and experimentally investigate the proposed framework.

关键词： Hypergraph partitioning graph partitioning sparse matrix partitioning parallel sparse matrix computations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：