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

ROUNDOFF ERROR ANALYSIS OF THE CHOLESKYQR2 ALGORITHM

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2015年 44卷 306-326页

作者： Yamamoto, Yusaku Nakatsukasa, Yuji Yanagisawa, Yuka Fukaya, Takeshi Univ Electrocommun Tokyo Japan JST CREST Tokyo Japan Univ Tokyo Tokyo 1138656 Japan Waseda Univ Tokyo Japan RIKEN Adv Inst Computat Sci Kobe Hyogo Japan Hokkaido Univ Sapporo Hokkaido 060 Japan JST CREST Tokyo Japan

We consider the QR decomposition of an m x n matrix X with full column rank, where m >= n. Among the many algorithms available, the Cholesky QR algorithm is ideal from the viewpoint of high performance computing since it consists entirely of standard level 3 BLAS operations with large matrix sizes, and requires only one reduce and broadcast in parallel environments. Unfortunately, it is well-known that the algorithm is not numerically stable and the deviation from orthogonality of the computed Q factor is of order O((kappa(2)(X))(2) u), where kappa(2)(X) is the 2-norm condition number of X and u is the unit roundoff. In this paper, we show that if the condition number of X is not too large, we can greatly improve the stability by iterating the Cholesky QR algorithm twice. More specifically, if kappa(2)(X) is at most O(u(-1/2)), both the residual and deviation from orthogonality are shown to be of order 0(u). Numerical results support our theoretical analysis.

关键词： QR decomposition Cholesky QR communication-avoiding algorithms roundoff error analysis

来源：评论

学校读者我要写书评

暂无评论

Applying the swept rule for solving explicit partial differential equations on heterogeneous computing systems

引用

JOURNAL OF SUPERCOMPUTING 2021年第2期77卷 1976-1997页

作者： Magee, Daniel J. Walker, Anthony S. Niemeyer, Kyle E. Oregon State Univ Sch Mech Ind & Mfg Engn Corvallis OR 97331 USA Los Alamos Natl Lab Los Alamos NM 87545 USA

Applications that exploit the architectural details of high-performance computing (HPC) systems have become increasingly invaluable in academia and industry over the past two decades. The most important hardware development of the last decade in HPC has been the general purpose graphics processing unit (GPGPU), a class of massively parallel devices that now contributes the majority of computational power in the top 500 supercomputers. As these systems grow, small costs such as latency-due to the fixed cost of memory accesses and communication-accumulate in a large simulation and become a significant barrier to performance. The swept time-space decomposition rule is a communication-avoiding technique for time-stepping stencil update formulas that attempts to reduce latency costs. This work extends the swept rule by targeting heterogeneous, CPU/GPU architectures representing current and future HPC systems. We compare our approach to a naive decomposition scheme with two test equations using an MPI+CUDA pattern on 40 processes over two nodes containing one GPU. The swept rule produces a factor of 1.9 to 23 speedup for the heat equation and a factor of 1.1 to 2.0 speedup for the Euler equations, using the same processors and work distribution, and with the best possible configurations. These results show the potential effectiveness of the swept rule for different equations and numerical schemes on massively parallel compute systems that incur substantial latency costs.

关键词： Domain decomposition Heterogeneous computing Partial differential equations Computational fluid dynamics communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

Accelerating solutions of one-dimensional unsteady PDEs with GPU-based swept time-space decomposition

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2018年 357卷 338-352页

作者： Magee, Daniel J. Niemeyer, Kyle E. Oregon State Univ Sch Mech Ind & Mfg Engn Corvallis OR 97331 USA

The expedient design of precision components in aerospace and other high-tech industries requires simulations of physical phenomena often described by partial differential equations (PDEs) without exact solutions. Modern design problems require simulations with a level of resolution difficult to achieve in reasonable amounts of time-even in effectively parallelized solvers. Though the scale of the problem relative to available computing power is the greatest impediment to accelerating these applications, significant performance gains can be achieved through careful attention to the details of memory communication and access. The swept time-space decomposition rule reduces communication between sub-domains by exhausting the domain of influence before communicating boundary values. Here we present a GPU implementation of the swept rule, which modifies the algorithm for improved performance on this processing architecture by prioritizing use of private (shared) memory, avoiding interblock communication, and overwriting unnecessary values. It shows significant improvement in the execution time of finite-difference solvers for one-dimensional unsteady PDEs, producing speedups of 2-9 x for a range of problem sizes, respectively, compared with simple GPU versions and 7-300 x compared with parallel CPU versions. However, for a more sophisticated one-dimensional system of equations discretized with a second-order finite-volume scheme, the swept rule performs 1.2-1.9 x worse than a standard implementation for all problem sizes. (C) 2017 Elsevier Inc. All rights reserved.

关键词： GPU computing Partial differential equations Computational fluid dynamics High-performance computing communication-avoiding algorithms Domain decomposition

来源：评论

学校读者我要写书评

暂无评论

Orthogonal Layers of Parallelism in Large-Scale Eigenvalue Computations

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2023年第3期10卷 1-31页

作者： Alvermann, Andreas Hager, Georg Fehske, Holger Univ Greifswald Inst Phys Felix Hausdorff Str 6 D-17489 Greifswald Germany Friedrich Alexander Univ Erlangen Nurnberg Erlangen Natl High Performance Comp Ctr Martensstr 1 D-91058 Erlangen Germany

We address the communication overhead of distributed sparse matrix-(multiple)-vector multiplication in the context of large-scale eigensolvers, using filter diagonalization as an example. The basis of our study is a performance model, which includes a communication metric that is computed directly from the matrix sparsity pattern without running any code. The performance model quantifies to which extent scalability and parallel efficiency are lost due to communication overhead. To restore scalability, we identify two orthogonal layers of parallelism in the filter diagonalization technique. In the horizontal layer the rows of the sparse matrix are distributed across individual processes. In the vertical layer bundles of multiple vectors are distributed across separate process groups. An analysis in terms of the communication metric predicts that scalability can be restored if, and only if, one implements the two orthogonal layers of parallelism via different distributed vector layouts. Our theoretical analysis is corroborated by benchmarks for application matrices from quantum and solid state physics, road networks, and nonlinear programming. We finally demonstrate the benefits of using orthogonal layers of parallelism with two exemplary application cases-an exciton and a strongly correlated electron system-which incur either small or large communication overhead.

关键词： Distributed computing sparse matrix-vector multiplication communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

A Computation- and communication-Optimal Parallel Direct 3-Body Algorithm 14

A Computation- and Communication-Optimal Parallel Direct 3-B...

引用

International Conference on High Performance Computing, Networking, Storage and Analysis

作者： Koanantakool, Penporn Yelick, Katherine Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA Lawrence Berkeley Natl Lab Berkeley CA USA

ISBN: (纸本)9781479955008

Traditional particle simulation methods are used to calculate pairwise potentials, but some problems require 3-body potentials that calculate over triplets of particles. A direct calculation of 3-body interactions involves O(n(3)) interactions, but has significant redundant computations that occur in a nested loop formulation. In this paper we explore algorithms for 3-body computations that simultaneously optimize three criteria: computation minimization through symmetries, communication optimality, and load balancing. We present a new 3-body algorithm that is both communication and computation optimal. Its optional replication factor, c, saves c(3) in latency (number of messages) and c(2) in bandwidth (volume), with bounded loadimbalance. We also consider the k-body case and discuss an algorithm that is optimal if there is a cutoff distance of less than 1/3 of the domain. The 3-body algorithm demonstrates 99% efficiency on tens of thousands of cores, showing strong scaling properties with order of magnitude speedups over the naive algorithm.

关键词： parallel algorithms communication-avoiding algorithms particle methods n-body

来源：评论

学校读者我要写书评

暂无评论

A Supernodal All-Pairs Shortest Path Algorithm 20

A Supernodal All-Pairs Shortest Path Algorithm

引用

25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Sao, Piyush Kannan, Ramakrishnan Gera, Prasun Vuduc, Richard Oak Ridge Natl Lab Oak Ridge TN 37830 USA Georgia Inst Technol Atlanta GA 30332 USA

ISBN: (纸本)9781450368186

We show how to exploit graphs parsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. FLOYD-WARSHALL is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.

关键词： graph algorithm sparse matrix computations shared-memory parallelism communication-avoiding algorithms

来源：评论

学校读者我要写书评

暂无评论

Matrix Multiplication I/O-Complexity by Path Routing 15

Matrix Multiplication I/O-Complexity by Path Routing

引用

27th ACM symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Scott, Jacob Holtz, Olga Schwartz, Oded Univ Calif Berkeley Berkeley CA 94720 USA Hebrew Univ Jerusalem Jerusalem Israel

ISBN: (纸本)9781450335881

We apply a novel technique based on path routings to obtain optimal I/O-complexity lower bounds for all Strassen-like fast matrix multiplication algorithms computed in serial or in parallel, assuming no reuse of nontrivial intermediate linear combinations. Given fast memory of size M, we prove an I/O-complexity lower bound of Omega ((n/root M)(omega 0) .M) for any Strassen-like matrix multiplication algorithm applied to n x n matrices of arithmetic complexity Theta(n (omega 0)) with omega(0) < 3 under this assumption. This generalizes an approach by Ballard, Demmel, Holtz, and Schwartz that provides a tight lower bound for Strassen's matrix multiplication algorithm but which does not apply to algorithms with disconnected encoding or decoding components of the underlying computation graph or algorithms with multiply copied values. We overcome these challenges via a new graph-theoretical approach for proving I/O-complexity lower bounds without the use of edge expansions.

关键词： communication-avoiding algorithms Fast matrix multiplication I/O-complexity

来源：评论

学校读者我要写书评

暂无评论

communication-Optimal Parallel Recursive Rectangular Matrix Multiplication

Communication-Optimal Parallel Recursive Rectangular Matrix ...

引用

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

作者： Demmel, James Eliahu, David Fox, Armando Kamil, Shoaib Lipshitz, Benjamin Schwartz, Oded Spillinger, Omer Univ Calif Berkeley Dept Math Berkeley CA 94720 USA MIT Cambridge MA 02139 USA Univ Calif Berkeley EECS Dept Berkeley CA 94720 USA

ISBN: (纸本)9780769549712

communication-optimal algorithms are known for square matrix multiplication. Here, we obtain the first communication-optimal algorithm for all dimensions of rectangular matrices. Combining the dimension-splitting technique of Frigo, Leiserson, Prokop and Ramachandran (1999) with the recursive BFS/DFS approach of Ballard, Demmel, Holtz, Lipshitz and Schwartz (2012) allows for a communication-optimal as well as cache-and network-oblivious algorithm. Moreover, the implementation is simple: approximately 50 lines of code for the shared-memory version. Since the new algorithm minimizes communication across the network, between NUMA domains, and between levels of cache, it performs well in practice on both shared-and distributed-memory machines. We show significant speedups over existing parallel linear algebra libraries both on a 32-core shared-memory machine and on a distributed-memory supercomputer.

关键词： communication-avoiding algorithms linear algebra matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

A 3D Parallel Algorithm for QR Decomposition 18

A 3D Parallel Algorithm for QR Decomposition

引用

30th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Ballard, Grey Demmel, James Grigori, Laura Jacquelin, Mathias Knight, Nicholas Wake Forest Univ Winston Salem NC 27101 USA Univ Calif Berkeley Berkeley CA 94720 USA INRIA Paris Rocquencourt Paris France Lawrence Berkeley Natl Lab Berkeley CA USA NYU New York NY USA

ISBN: (纸本)9781450357999

Interprocessor communication often dominates the runtime of large matrix computations. We present a parallel algorithm for computing QR decompositions whose bandwidth cost (communication volume) can be decreased at the cost of increasing its latency cost (number of messages). By varying a parameter to navigate the bandwidth/latency tradeoff, we can tune this algorithm for machines with different communication costs.

关键词： communication-avoiding algorithms bandwidth-latency tradeoffs communication-memory tradeoffs

来源：评论

学校读者我要写书评

暂无评论

I/O-Optimal algorithms for Symmetric Linear Algebra Kernels 22

I/O-Optimal Algorithms for Symmetric Linear Algebra Kernels

引用

34th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Beaumont, Olivier Eyraud-Dubois, Lionel Langou, Julien Verite, Mathieu Univ Bordeaux Inria Ctr Bordeaux France Univ Colorado Denver Denver Denver CO USA

ISBN: (纸本)9781450391467

In this paper, we consider two fundamental symmetric kernels in linear algebra: the Cholesky factorization and the symmetric rank-k update (SYRK), with the classical three nested loops algorithms for these kernels. In addition, we consider a machine model with a fast memory of size S and an unbounded slow memory. In this model, all computations must be performed on operands in fast memory, and the goal is to minimize the amount of communication between slow and fast memories. As the set of computations is fixed by the choice of the algorithm, only the ordering of the computations (the schedule) directly influences the volume of communications. We prove lower bounds of 1/3 root 2 N-3/root S for the communication volume of the Cholesky factorization of an N x N symmetric positive definite matrix, and of 1/root 2 (NM)-M-2/root S for the SYRK computation of A center dot A(T), where A is an N x M matrix. Both bounds improve the best known lower bounds from the literature by a factor root 2. In addition, we present two out-of-core, sequential algorithms with matching communication volume: TBS for SYRK, with a volume of 1/root 2 (NM)-M-2/root S + O(NM log N), and LBC for Cholesky, with a volume of 1/3 root 2 N-3/root S + O(N-5/2). Both algorithms improve over the best known algorithms from the literature by a factor root 2, and prove that the leading terms in our lower bounds cannot be improved further. This work shows that the operational intensity of symmetric kernels like SYRK or Cholesky is intrinsically higher (by a factor root 2) than that of corresponding non-symmetric kernels (GEMM and LU factorization).

关键词： communication-avoiding algorithms linear algebra symmetric kernels syrk cholesky

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：