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

sparse cholesky factorization ON A LOCAL-MEMORY MULTIPROCESSOR

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING 1988年第2期9卷 327-340页

作者： GEORGE, A HEATH, MT LIU, J NG, E OAK RIDGE NATL LAB MATH SCI SECTOAK RIDGETN 37830 YORK UNIV DEPT COMP SCIDOWNSVIEW M3J 1P3ONTARIOCANADA

This article deals with the problem of factoring a large sparse positive definite matrix on a multiprocessor system. The processors are assumed to have substantial local memory but no globally shared memory. They communicate among themselves and with a host processor through message passing. Our primary interest is in designing an algorithm which exploits parallelism, rather than in exploiting features of the underlying topology of the hardware. However, part of our study is aimed at determining, for certain sparse matrix problems, whether hardware based on the binary hypercube topology adequately supports the communication requirements for such problems. Numerical results from experiments conducted on a hypercube multiprocessor are included.

关键词： 65F 65W sparse cholesky factorization elimination trees local-memory multiprocessors hypercube

来源：评论

学校读者我要写书评

暂无评论

Supernodal sparse cholesky factorization on graphics processing units

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2014年第16期26卷 2713-2726页

作者： Zou, Dan Dou, Yong Guo, Song Li, Rongchun Deng, Lin Natl Univ Def Technol Sch Comp Changsha Hunan Peoples R China

sparse cholesky factorization is the most computationally intensive component in solving large sparse linear systems and is the core algorithm of numerous scientific computing applications. A large number of sparse cholesky factorization algorithms have previously emerged, exploiting architectural features for various computing platforms. The recent use of graphics processing units (GPUs) to accelerate structured parallel applications shows the potential to achieve significant acceleration relative to desktop performance. However, sparse cholesky factorization has not been explored sufficiently because of the complexity involved in its efficient implementation and the concerns of low GPU utilization. In this paper, we present a new approach for sparse cholesky factorization on GPUs. We present the organization of the sparse matrix supernode data structure for GPU and propose a queue-based approach for the generation and scheduling of GPU tasks with dense linear algebraic operations. We also design a subtree-based parallel method for multi-GPU system. These approaches increase GPU utilization, thus resulting in substantial computational time reduction. Comparisons are made with the existing parallel solvers by using problems arising from practical applications. The experiment results show that the proposed approaches can substantially improve sparse cholesky factorization performance on GPUs. Relative to a highly optimized parallel algorithm on a 12-core node, we were able to obtain speedups in the range 1.59x to 2.31x by using one GPU and 1.80x to 3.21x by using two GPUs. Relative to a state-of-the-art solver based on supernodal method for CPU-GPU heterogeneous platform, we were able to obtain speedups in the range 1.52x to 2.30x by using one GPU and 2.15x to 2.76x by using two GPUs. Concurrency and Computation: Practice and Experience, 2013. Copyright (c) 2013 John Wiley & Sons, Ltd.

关键词： GPU sparse cholesky factorization supernodal method

来源：评论

学校读者我要写书评

暂无评论

ON THE MINIMUM FLOPS PROBLEM IN THE sparse cholesky factorization

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2014年第1期35卷 1-21页

作者： Luce, Robert Ng, Esmond G. TU Berlin Inst Math D-10623 Berlin Germany Univ Calif Berkeley Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA 94720 USA

Prior to computing the cholesky factorization of a sparse symmetric positive definite matrix, a reordering of the rows and columns is computed so as to reduce both the number of fill elements in cholesky factor and the number of arithmetic operations (FLOPs) in the numerical factorization. These two metrics are clearly somehow related and yet it is suspected that these two problems are different. However, no rigorous theoretical treatment of the relation of these two problems seems to have been given yet. In this paper we show by means of an explicit, scalable construction that the two problems are different in a very strict sense: no ordering is optimal for both fill and FLOPs in the constructed graph. Further, it is commonly believed that minimizing the number of FLOPs is no easier than minimizing the fill (in the complexity sense), but so far no proof appears to be known. We give a reduction chain that shows the NP hardness of minimizing the number of arithmetic operations in the cholesky factorization.

关键词： sparse cholesky factorization minimum fill minimum operation count computational complexity

来源：评论

学校读者我要写书评

暂无评论

Accelerating sparse cholesky factorization on Sunway Manycore Architecture

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2020年第7期31卷 1636-1650页

作者： Li, Mingzhen Liu, Yi Yang, Hailong Luan, Zhongzhi Gan, Lin Yang, Guangwen Qian, Depei Beihang Univ Sino German Joint Software Inst Sch Comp Sci & Engn Beijing 100191 Peoples R China Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China

To improve the performance of sparse cholesky factorization, existing research divides the adjacent columns of the sparse matrix with the same nonzero patterns into supernodes for parallelization. However, due to the various structures of sparse matrices, the computation of the generated supernodes varies significantly, and thus hard to optimize when computed by dense matrix kernels. Therefore, how to efficiently map sparse Choleksy factorization to the emerging architectures, such as Sunway many-core processor, remains an active research direction. In this article, we propose swcholesky, which is a highly optimized implementation of sparse cholesky factorization on Sunway processor. Specifically, we design three kernel task queues and a dense matrix library to dynamically adapt to the kernel characteristics and architecture features. In addition, we propose an auto-tuning mechanism to search for the optimal settings of the important parameters in swcholesky. Our experiments show that swcholesky achieves better performance than state-of-the-art implementations.

关键词： Sunway architecture sparse cholesky factorization performance optimization

来源：评论

学校读者我要写书评

暂无评论

TASK-SCHEDULING FOR PARALLEL sparse cholesky factorization

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1989年第4期18卷 291-314页

作者： GEIST, GA NG, E OAK RIDGE NATL LAB MATH SCI SECTOAK RIDGETN 37831

This paper presents a solution to the problem of partitioning the work for sparse matrix factorization to individual processors on a multiprocessor system. The proposed task assignment strategy is based on the structure of the elimination tree associated with the given sparse matrix. The goal of the task scheduling strategy is to achieve load balancing and a high degree of concurrency among the processors while redu?ing the amount of processor-to-processor data comnication, even for arbitrarily unbalanced elimination trees. This is important because popular fill-reducing ordering methods, such as the minimum degree algorithm, often produce unbalanced elimination trees. Results from the Intel iPSC/2 are presented for various finite-element problems using both nested dissection and minimum degree orderings.

关键词： Parallel computing sparse cholesky factorization task scheduling

来源：评论

学校读者我要写书评

暂无评论

Performance of panel and block approaches to sparse cholesky factorization on the iPSC/860 and Paragon multicomputers

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 1996年第3期17卷 699-713页

作者： Rothberg, E INTEL CORP SUPERCOMP SYST DIV BEAVERTON OR 97006 USA

sparse cholesky factorization has historically achieved extremely low performance on distributed-memory multiprocessors. We believe that three issues must be addressed to improve this situation: (1) parallel factorization methods must be based on more efficient sequential methods;(2) parallel machines must provide higher interprocessor communication bandwidth;and (3) the sparse matrices used to evaluate parallel sparse factorization performance should be more representative of the sizes of matrices people would factor on large parallel machines. This paper demonstrates that all three of these issues have in fact already been addressed. Specifically, (1) single node performance can be improved by moving from a column-oriented approach, where the computational kernel is level 1 BLAS, to either a panel- or block-oriented approach, where the computational kernel is level 3 BLAS;(2) communication hardware has improved dramatically, with new parallel computers (the Intel Paragon system) providing one to two orders of magnitude higher communication bandwidth than previous parallel computers (the Intel iPSC/860 system);and (3) several larger benchmark matrices are now available, and newer parallel machines offer sufficient memory per node to factor these larger matrices. The result of addressing these three issues is extremely high performance on moderately parallel machines. This paper demonstrates performance levels of 650 double-precision Mflops on 32 nodes of the Intel Paragon system, 1 Chop on 64 nodes, and 1.7 Chops on 128 nodes. This paper also does a direct performance comparison between the iPSC/860 and Paragon systems, as well as a comparison between panel- and block-oriented approaches to parallel factorization.

关键词： sparse cholesky factorization parallel machines sparse matrices scalability

来源：评论

学校读者我要写书评

暂无评论

PARALLEL sparse cholesky factorization ON A SHARED MEMORY MULTIPROCESSOR

引用

PARALLEL COMPUTING 1992年第9期18卷 1009-1022页

作者： ZHANG, G ELMAN, HC UNIV MARYLAND INST ADV COMP STUDIESCOLL PKMD 20742 UNIV MARYLAND DEPT COMP SCICOLL PKMD 20742

Parallel implementations of cholesky factorization for sparse symmetric positive definite matrices are considered on a shared memory multiprocessor computer. Two column-oriented schemes, known as the column-cholesky algorithm and the fan-in algorithm, along with enhancements of each, are implemented and discussed. High parallel efficiency of the column-cholesky algorithm and its enhancement is demonstrated for test problems. A detailed investigation of the performance of the fan-in algorithm and its enhancement, the compute-ahead fan-in algorithm, is made to study the effects of overhead associated with the fan-in based schemes.

关键词： PARALLEL ALGORITHMS sparse cholesky factorization LINEAR ALGEBRA SHARED MEMORY MULTIPROCESSOR

来源：评论

学校读者我要写书评

暂无评论

Parallel sparse cholesky factorization on a Heterogeneous Platform

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2013年第4期E96A卷 833-834页

作者： Zou, Dan Dou, Yong Li, Rongchun Natl Univ Def Technol Natl Lab Parallel & Distribut Proc Changsha 410073 Hunan Peoples R China

We present a new approach for sparse cholesky factorization on a heterogeneous platform with a graphics processing unit (GPU). The sparse cholesky factorization is one of the core algorithms of numerous computing applications. We tuned the supernode data structure and used a parallelization method for GPU tasks to increase GPU utilization. Results show that our approach substantially reduces computational time.

关键词： sparse cholesky factorization supernodal method GPU

来源：评论

学校读者我要写书评

暂无评论

Two-dimensional block partitionings for the parallel sparse cholesky factorization

引用

NUMERICAL ALGORITHMS 1997年第1期16卷 17-38页

作者： Dumitrescu, B Doreille, M Roch, JL Trystram, D Univ Politehn Bucuresti Dept Automat Control & Comp Bucharest 77206 Romania Imag Lab Grenoble LMC F-38041 Grenoble France Lab Modelisat & Calcul Grenoble France

This paper presents a discussion on 2D block mappings for the sparse cholesky factorization on parallel MIMD architectures with distributed memory. It introduces the fan-in algorithm in a general manner and proposes several mapping strategies. The grid mapping with row balancing, inspired by Rothberg's work (1994), is proved to be more robust than the original fan-out algorithm. Even more efficient is the proportional mapping, as shown by the experiments on a 32 processor IBM SP1 and on a Gray T3D. Subforest-to-subcube mappings are also considered and give good results on the no.

关键词： sparse cholesky factorization parallel algorithms fan-in communication 2D block partitioning proportional mapping

来源：评论

学校读者我要写书评

暂无评论

AN EFFICIENT ALGORITHM TO COMPUTE ROW AND COLUMN COUNTS FOR sparse cholesky factorization

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 1994年第4期15卷 1075-1091页

作者： GILBERT, JR NG, EG PEYTON, BW OAK RIDGE NATL LAB MATH SCI SECTOAK RIDGETN 37831

Let an undirected graph G be given, along with a specified depth-first spanning tree T. Almost-linear-time algorithms are given to solve the following two problems. First, for every vertex v, compute the number of descendants w of v for which some descendant of w is adjacent (in G) to v. Second, for every vertex v, compute the number of ancestors of v that are adjacent (in G) to at least one descendant of v. These problems arise in cholesky and QR factorizations of sparse matrices. The authors' algorithms can be used to determine the number of nonzero entries in each row and column of the triangular factor of a matrix from the zero/nonzero structure of the matrix. Such a prediction makes storage allocation for sparse matrix factorizations more efficient. The authors' algorithms run in time linear in the size of the input times a slowly growing inverse of Ackermann's function. The best previously known algorithms for these problems ran in time linear in the sum of the nonzero counts, which is usually much larger. Experimental results are given demonstrating the practical efficiency of the new algorithms.

关键词： sparse cholesky factorization sparse QR factorization SYMBOLIC factorization GRAPH ALGORITHMS CHORDAL GRAPH COMPLETION DISJOINT SET UNION COLUMN COUNTS ROW COUNTS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：