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

A Class of communication-avoiding algorithms for Solving General Dense Linear Systems on CPU/GPU Parallel Machines

Procedia Computer Science 2012年 9卷 17-26页

作者： Marc Baboulin Simplice Donfack Jack Dongarra Laura Grigori Adrien Rémy Stanimire Tomov Inria and University Paris-Sud France University of Tennessee USA Oak Ridge National Laboratory USA University of Manchester United Kingdom

We study several solvers for the solution of general linear systems where the main objective is to reduce the communication overhead due to pivoting. We first describe two existing algorithms for the LU factorization on hybrid CPU/GPU architectures. The first one is based on partial pivoting and the second uses a random preconditioning of the original matrix to avoid pivoting. Then we introduce a solver where the panel factorization is performed using a communication-avoiding pivoting heuristic while the update of the trailing submatrix is performed by the GPU. We provide performance comparisons and tests on accuracy for these solvers on current hybrid multicore-GPU parallel machines.

关键词： hybrid multicore/GPU computing dense linear algebra libraries linear system solvers communication-avoiding algorithms LU factorization

来源：评论

学校读者我要写书评

暂无评论

communication-avoiding SYMMETRIC-INDEFINITE FACTORIZATION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2014年第4期35卷 1364-1406页

作者： Ballard, Grey Becker, Dulceneia Demmel, James Dongarra, Jack Druinsky, Alex Peled, Inon Schwartz, Oded Toledo, Sivan Yamazaki, Ichitaro Sandia Natl Labs Livermore CA 94550 USA Univ Tennessee Knoxville TN 37996 USA Univ Calif Berkeley Berkeley CA 94720 USA Oak Ridge Natl Lab Oak Ridge TN 37831 USA Univ Manchester Manchester M13 9PL Lancs England Univ Calif Berkeley Lawrence Berkeley Natl Lab Berkeley CA 94720 USA Tel Aviv Univ IL-69978 Tel Aviv Israel

We describe and analyze a novel symmetric triangular factorization algorithm. The algorithm is essentially a block version of Aasen's triangular tridiagonalization. It factors a dense symmetric matrix A as the product A = (PLTLPT)-P-T, where P is a permutation matrix, L is lower triangular, and T is block tridiagonal and banded. The algorithm is the first symmetric-indefinite communication-avoiding factorization: it performs an asymptotically optimal amount of communication in a two-level memory hierarchy for almost any cache-line size. Adaptations of the algorithm to parallel computers are likely to be communication efficient as well;one such adaptation has been recently published. The current paper describes the algorithm, proves that it is numerically stable, and proves that it is communication optimal.

关键词： symmetric-indefinite matrices communication-avoiding algorithms Aasen's factorization

来源：评论

学校读者我要写书评

暂无评论

avoiding communication IN PRIMAL AND DUAL BLOCK COORDINATE DESCENT METHODS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2019年第1期41卷 C1-C27页

作者： Devarakonda, Aditya Fountoulakis, Kimon Demmel, James Mahoney, Michael W. Univ Calif Berkeley Dept EECS Berkeley CA 94709 USA Univ Calif Berkeley ICSI Berkeley CA 94709 USA Univ Calif Berkeley Dept Stat Berkeley CA 94709 USA Univ Calif Berkeley Math & EECS Dept Berkeley CA 94709 USA

Primal and dual block coordinate descent methods are iterative methods for solving regularized and unregularized optimization problems. Distributed-memory parallel implementations of these methods have become popular in analyzing large machine learning datasets. However, existing implementations communicate at every iteration, which, on modern data center and super-computing architectures, often dominates the cost of floating-point computation. Recent results on communication-avoiding Krylov subspace methods suggest that large speedups are possible by reorganizing iterative algorithms to avoid communication. We show how applying similar algorithmic transformations can lead to primal and dual block coordinate descent methods that only communicate every s iterations where s is a tuning parameter instead of every iteration for the regularized least-squares problem. We show that the communication-avoiding variants reduce the number of synchronizations by a factor of s on distributed-memory parallel machines without altering the convergence rate and attain strong scaling speedups of up to 6.1x over the "standard algorithm" on a Cray XC30 supercomputer.

关键词： primal and dual methods communication-avoiding algorithms block coordinate descent ridge regression

来源：评论

学校读者我要写书评

暂无评论

communication-avoiding Optimizations for Large-Scale Unstructured-Mesh Applications with OP2 23

Communication-Avoiding Optimizations for Large-Scale Unstruc...

引用

52nd International Conference on Parallel Processing (ICPP)

作者： Ekanayake, Suneth D. Reguly, Istvan Z. Luporini, Fabio Mudalige, Gihan R. Univ Warwick Coventry W Midlands England Pazmany Peter Catholic Univ Budapest Hungary Devito Codes London England

ISBN: (纸本)9798400708435

In this paper, we investigate data movement-reducing and communication-avoiding optimizations and their practicable implementation for large-scale unstructured-mesh applications. Utilizing the high-level abstraction of the OP2 DSL for the unstructured-mesh class of codes, we reason about techniques for reduced communications across a consecutive sequence of loops - a loop-chain. The careful trade-off with increased redundant computation in place of data movement is analyzed for distributed-memory parallelization. A new communication-avoiding (CA) back-end for OP2 is designed, codifying these techniques such that they can be applied automatically to any OP2 application. The back-end is extended to operate on a cluster of GPUs, integrating GPU-to-GPU communication with CUDA, in combination with MPI. The new CA back-end is applied automatically to two non-trivial applications, including the OP2 version of Rolls-Royce's production CFD application, Hydra. Performance is investigated on both CPU and GPU clusters on representative problems of 8M and 24M node mesh sizes. Results demonstrate how for select configurations the new CA back-end provides between 30 - 65% runtime reductions for the loop-chains in these applications for the mesh sizes on both an HPE Cray EX system and an NVIDIA V100 GPU cluster. We model and examine the determinants and characteristics of a given unstructured-mesh loopchain that can lead to performance benefits with CA techniques, providing insights into the general feasibility and profitability of using the optimizations for this class of applications.

关键词： communication-avoiding algorithms OP2 Unstructured-mesh

来源：评论

学校读者我要写书评

暂无评论

A communication-avoiding 3D sparse triangular solver 19

A communication-avoiding 3D sparse triangular solver

引用

33rd ACM International Conference on Supercomputing (ICS)

作者： Sao, Piyush Kannan, Ramakrishnan Li, Xiaoye Sherry Vuduc, Richard Oak Ridge Natl Lab POB 2009 Oak Ridge TN 37830 USA Lawrence Berkeley Natl Lab Berkeley CA USA Georgia Inst Technol Atlanta GA 30332 USA

ISBN: (纸本)9781450360791

We present a novel distributed memory algorithm to improve the strong scalability of the solution of a sparse triangular system. This operation appears in the solve phase of direct methods for solving general sparse linear systems, Ax = b. Our 3D sparse triangular solver employs several techniques, including a 3D MPI process grid, elimination tree parallelism, and data replication, all of which reduce the per-process communication when combined. We present analytical models to understand the communication cost of our algorithm and show that our 3D sparse triangular solver can reduce the per-process communication volume asymptotically by a factor of O (n(1/4)) and O (n(1/6)) for problems arising from the finite element discretizations of 2D "planar" and 3D "non-planar" PDEs, respectively. We implement our algorithm for use in SuperLU DIST3D, using a hybrid MPI+OpenMP programming model. Our 3D triangular solve algorithm, when run on 12k cores of Cray XC30, outperforms the current state-of-the-art 2D algorithm by 7.2x for planar and 2.7x for the non-planar sparse matrices, respectively.

关键词： sparse matrix computations distributed-memory parallelism communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

communication-avoiding Parallel Sparse-Dense Matrix-Matrix Multiplication 30

Communication-Avoiding Parallel Sparse-Dense Matrix-Matrix M...

引用

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

作者： Koanantakool, Penporn Azad, Ariful Buluc, Aydin Morozov, Dmitriy Oh, Sang-Yun Oliker, Leonid Yelick, Katherine Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA 94720 USA Univ Calif Berkeley Dept EECS Berkeley CA 94720 USA Univ Calif Santa Barbara Dept Stat & Appl Probabil Santa Barbara CA 93106 USA

ISBN: (纸本)9781509021406

Multiplication of a sparse matrix with a dense matrix is a building block of an increasing number of applications in many areas such as machine learning and graph algorithms. However, most previous work on parallel matrix multiplication considered only both dense or both sparse matrix operands. This paper analyzes the communication lower bounds and compares the communication costs of various classic parallel algorithms in the context of sparse-dense matrix-matrix multiplication. We also present new communication-avoiding algorithms based on a 1D decomposition, called 1.5D, which - while suboptimal in dense-dense and sparse-sparse cases - outperform the 2D and 3D variants both theoretically and in practice for sparsedense multiplication. Our analysis separates one-time costs from per iteration costs in an iterative machine learning context. Experiments demonstrate speedups up to 100x over a baseline 3D SUMMA implementation and show parallel scaling over 10 thousand cores.

关键词： communication-avoiding algorithms Linear algebra Parallel algorithms Sparse-dense matrix-matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

communication-avoiding Recursive Aggregation 25

Communication-Avoiding Recursive Aggregation

引用

25th IEEE International Conference on Cluster Computing (CLUSTER)

作者： Sun, Yihao Kumar, Sidharth Gilray, Thomas Micinski, Kristopher Syracuse Univ Dept Elect Engn & Comp Sci Syracuse NY 13210 USA Univ Illinois Dept Comp Sci Chicago IL USA Univ Alabama Birmingham Dept Comp Sci Birmingham AL 35233 USA

ISBN: (纸本)9798350307924

Recursive aggregation has been of considerable interest due to its unifying a wide range of deductive-analytic workloads, including social-media mining and graph analytics. For example, Single-Source Shortest Paths (SSSP), Connected Components (CC), and PageRank may all be expressed via recursive aggregates. Implementing recursive aggregation has posed a serious algorithmic challenge, with state-of-the-art work identifying sufficient conditions (e.g., pre-mappability) under which implementations may push aggregation within recursion, avoiding the serious materialization overhead inherent to traditional reachability-based methods (e.g., Datalog). State-of-the-art implementations of engines supporting recursive aggregates focus on large unified machines, due to the challenges posed by mixing semi-naive evaluation with distribution. In this work, we present an approach to implementing recursive aggregates on high-performance clusters which avoids the communication overhead inhibiting current-generation distributed systems to scale recursive aggregates to extremely high process counts. Our approach leverages the observation that aggregators form functional dependencies, allowing us to implement recursive aggregates via a high-parallel local aggregation to ensure maximal throughput. Additionally, we present a dynamic join planning mechanism, which customizes join order per-iteration based on dynamic relation sizes. We implemented our approach in PARALAGG, a library which allows the declarative implementation of queries which utilize recursive aggregates and executes them using our MPI-based runtime. We evaluate PARALAGG on a large unified node and leadership-class supercomputers, demonstrating scalability up to 16,384 processes.

关键词： relational algebra aggregation communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

Reconstructing Householder vectors from Tall-Skinny QR

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2015年 85卷 3-31页

作者： Ballard, G. Demmel, J. Grigori, L. Jacquelin, M. Knight, N. Nguyen, H. D. Sandia Natl Labs Livermore CA USA Univ Calif Berkeley Berkeley CA 94720 USA INRIA Paris Rocquencourt Paris France Lawrence Berkeley Natl Lab Berkeley CA USA

The Tall-Skinny QR (TSQR) algorithm is more communication efficient than the standard Householder algorithm for QR decomposition of matrices with many more rows than columns. However, TSQR produces a different representation of the orthogonal factor and therefore requires more software development to support the new representation. Further, implicitly applying the orthogonal factor to the trailing matrix in the context of factoring a square matrix is more complicated and costly than with the Householder representation. We show how to perform TSQR and then reconstruct the Householder vector representation with the same asymptotic communication efficiency and little extra computational cost. We demonstrate the high performance and numerical stability of this algorithm both theoretically and empirically. The new Householder reconstruction algorithm allows us to design more efficient parallel QR algorithms, with significantly lower latency cost compared to Householder QR and lower bandwidth and latency costs compared with communication-avoiding QR (CAQR) algorithm. Experiments on supercomputers demonstrate the benefits of the communication cost improvements: in particular, our experiments show substantial improvements over tuned library implementations for tall-and-skinny matrices. We also provide algorithmic improvements to the Householder QR and CAQR algorithms, and we investigate several alternatives to the Householder reconstruction algorithm that sacrifice guarantees on numerical stability in some cases in order to obtain higher performance. (C) 2015 Elsevier Inc. All rights reserved.

关键词： QR decomposition Dense linear algebra communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

A massively parallel tensor contraction framework for coupled-cluster computations

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2014年第12期74卷 3176-3190页

作者： Solomonik, Edgar Matthews, Devin Hammond, Jeff R. Stanton, John F. Demmel, James Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Texas Austin Dept Chem & Biochem Austin TX 78712 USA Argonne Natl Lab Leadership Comp Facil Argonne IL 60439 USA

Precise calculation of molecular electronic wavefunctions by methods such as coupled-cluster requires the computation of tensor contractions, the cost of which has polynomial computational scaling with respect to the system and basis set sizes. Each contraction may be executed via matrix multiplication on a properly ordered and structured tensor. However, data transpositions are often needed to reorder the tensors for each contraction. Writing and optimizing distributed-memory kernels for each transposition and contraction is tedious since the number of contractions scales combinatorially with the number of tensor indices. We present a distributed-memory numerical library (Cyclops Tensor Framework (CTF)) that automatically manages tensor blocking and redistribution to perform any user-specified contractions. CTF serves as the distributed-memory contraction engine in Aquarius, a new program designed for high-accuracy and massively-parallel quantum chemical computations. Aquarius implements a range of coupled-cluster and related methods such as CCSD and CCSDT by writing the equations on top of a C++ templated domain-specific language. This DSL calls CTF directly to manage the data and perform the contractions. Our CCSD and CCSDT implementations achieve high parallel scalability on the BlueGene/Q and Cray XC30 supercomputer architectures showing that accurate electronic structure calculations can be effectively carried out on top of general distributed-memory tensor primitives. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Coupled-cluster Tensor contractions Matrix multiplication Topology-aware mapping communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

SHIFTED CHOLESKY QR FOR COMPUTING THE QR FACTORIZATION OF ILL-CONDITIONED MATRICES

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2020年第1期42卷 A477-A503页

作者： Fukaya, Takeshi Kannan, Ramaseshan Nakatsukasa, Yuji Yamamoto, Yusaku Yanagisawa, Yuka Hokkaido Univ Sapporo Hokkaido Japan Arup 3 Piccadilly Pl Manchester M1 3BN Lancs England Univ Oxford Math Inst Oxford OX2 6GG England Univ Electrocommun Tokyo Japan Waseda Univ Waseda Res Inst Sci & Engn Tokyo Japan

The Cholesky QR algorithm is an efficient communication-minimizing algorithm for computing the QR factorization of a tall-skinny matrix X epsilon R-mxn, where m >> n. Unfortunately it is inherently unstable and often breaks down when the matrix is ill-conditioned. A recent work [Yamamoto et al., ETNA, 44, pp. 306--326 (2015)] establishes that the instability can be cured by repeating the algorithm twice (called CholeskyQR2). However, the applicability of CholeskyQR2 is still limited by the requirement that the Cholesky factorization of the Gram matrix X-inverted perpendicular X runs to completion, which means that it does not always work for matrices X with the 2-norm condition number kappa(2)(X) roughly greater than u(-1/2), where u is the unit roundoff. In this work we extend the applicability to kappa(2)(X) = O (u(-1)) by introducing a shift to the computed Gram matrix so as to guarantee the Cholesky factorization R-inverted perpendicular R = A(inverted perpendicular) A+sI succeeds numerically. We show that the computed AR(-1) has reduced condition number that is roughly bounded by u(-1/2), for which CholeskyQR2 safely computes the QR factorization, yielding a computed Q of orthogonality vertical bar vertical bar Q(inverted perpendicular) - Q I vertical bar vertical bar(2) and residual vertical bar vertical bar A - QR vertical bar vertical bar(F) / vertical bar vertical bar A vertical bar vertical bar(F) both of the order of u. Thus we obtain the required QR factorization by essentially running Cholesky QR thrice. We extensively analyze the resulting algorithm shiftedCholeskyQR3 to reveal its excellent numerical stability. The shiftedCholeskyQR3 algorithm is also highly parallelizable, and applicable and effective also when working with an oblique inner product. We illustrate our findings through experiments, in which we achieve significant speedup over alternative methods.

关键词： QR factorization Cholesky QR factorization oblique inner product roundoff error analysis communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：