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

UNIFYING AND OPTIMIZING linear algebra algorithms

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1993年第12期4卷 1382-1397页

作者： ANGELACCIO, M COLAJANNI, M Dipartimento di Ingegneria Elettronica Universitià di Roma Tor Vergata Rome Italy

This paper addresses two issues in linear algebra algorithms for multicomputers: first, how to unify parallel implementations of the same algorithm in a decomposition-independent way;and second, how to optimize naive parallel programs maintaining the decomposition independence. Several matrix decompositions are viewed as instances of a more general allocation function called Subcube Matrix Decomposition. By this meta-decomposition, we define a programming environment characterized by general primitives that allow us to design meta-algorithms independent from a particular decomposition. For example, we apply such a framework to the parallel solution of dense matrices, thus demonstrating that most of the existing algorithms can be derived by suitably setting the primitives used in the meta-algorithm. A further original application of this programming style concerns the optimization of parallel algorithms. The idea to overlap communication and computation has been extended from 1-D decompositions to 2-D decompositions;thus, we provide a first attempt toward a decomposition-independent definition of such optimization strategies.

关键词： COMMUNICATION/COMPUTATION OVERLAPPING STRATEGIES linear algebra algorithms MULTICOMPUTERS PARALLEL PROGRAM UNIFICATION RESTRUCTURING PARALLEL algorithms SUBCUBE MATRIX DECOMPOSITION

来源：评论

学校读者我要写书评

暂无评论

Performance and energy analysis of OpenMP runtime systems with dense linear algebra algorithms

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2019年第3期33卷 431-443页

作者： Ferreira Lima, Joao Vicente Rais, Issam Lefevre, Laurent Gautier, Thierry Univ Fed Santa Maria Santa Maria RS Brazil Univ Claude Bernard Lyon 1 Univ Lyon INRIA CNRSENS LyonLIP Lyon France

In this article, we analyze performance and energy consumption of five OpenMP runtime systems over a non-uniform memory access (NUMA) platform. We also selected three CPU-level optimizations or techniques to evaluate their impact on the runtime systems: processors features Turbo Boost and C-States, and CPU Dynamic Voltage and Frequency Scaling through Linux CPUFreq governors. We present an experimental study to characterize OpenMP runtime systems on the three main kernels in dense linear algebra algorithms (Cholesky, LU, and QR) in terms of performance and energy consumption. Our experimental results suggest that OpenMP runtime systems can be considered as a new energy leverage, and Turbo Boost, as well as C-States, impacted significantly performance and energy. CPUFreq governors had more impact with Turbo Boost disabled, since both optimizations reduced performance due to CPU thermal limits. An LU factorization with concurrent-write extension from libKOMP achieved up to 63% of performance gain and 29% of energy decrease over original PLASMA algorithm using GNU C compiler (GCC) libGOMP runtime.

关键词： OpenMP task parallelism linear algebra algorithms NUMA energy efficiency

来源：评论

学校读者我要写书评

暂无评论

A Test for FLOPs as a Discriminant for linear algebra algorithms 34

A Test for FLOPs as a Discriminant for Linear Algebra Algori...

引用

34th IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)

作者： Sankaran, Aravind Bientinesi, Paolo RWIH Aachen Univ IRTG MIP Aachen Germany Umea Univ Dept Comp Sci Umea Sweden

ISBN: (数字)9781665451550

ISBN: (纸本)9781665451550

linear algebra expressions, which play a central role in countless scientific computations, are often computed via a sequence of calls to existing libraries of building blocks (such as those provided by BLAS and LAPACK). A sequence identifies a computing strategy, i.e., an algorithm, and normally for one linear algebra expression many alternative algorithms exist. Although mathematically equivalent, those algorithms might exhibit significant differences in terms of performance. Several high-level languages and tools for matrix computations such as Julia, Armadillo, Linnea, etc., make algorithmic choices by minimizing the number of Floating Point Operations (FLOPs). However, there can be several algorithms that share the same (or have nearly identical) number of FLOPs;in many cases, these algorithms exhibit execution times which are statistically equivalent and one could arbitrarily select one of them as the best algorithm. It is however not unlikely to find cases where the execution times are significantly different from one another (despite the FLOP count being almost the same). It is also possible that the algorithm that minimizes FLOPs is not the one that minimizes execution time. In this work, we develop a methodology to test the reliability of FLOPs as discriminant for linear algebra algorithms. Given a set of algorithms (for an instance of a linear algebra expression) as input, the methodology ranks them into performance classes;i.e., multiple algorithms are allowed to share the same rank. To this end, we measure the algorithms iteratively until the changes in the ranks converge to a value close to zero. FLOPs are a valid discriminant for an instance if all the algorithms with minimum FLOPs are assigned the best rank;otherwise, the instance is regarded as an anomaly, which can then be used in the investigation of the root cause of performance differences.

关键词： Performance Analysis linear algebra algorithms Algorithm ranking Mathematical software performance

来源：评论

学校读者我要写书评

暂无评论

MINIMIZING COMMUNICATION IN NUMERICAL linear algebra

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2011年第3期32卷 866-901页

作者： Ballard, Grey Demmel, James Holtz, Olga Schwartz, Oded Univ Calif Berkeley Dept Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Math Berkeley CA 94720 USA Univ Calif Berkeley CS Div Berkeley CA 94720 USA Tech Univ Berlin Berlin Germany

In 1981 Hong and Kung proved a lower bound on the amount of communication (amount of data moved between a small, fast memory and large, slow memory) needed to perform dense, n-by-n matrix multiplication using the conventional O(n(3)) algorithm, where the input matrices were too large to fit in the small, fast memory. In 2004 Irony, Toledo, and Tiskin gave a new proof of this result and extended it to the parallel case (where communication means the amount of data moved between processors). In both cases the lower bound may be expressed as Omega(#arithmetic operations/root M), where M is the size of the fast memory (or local memory in the parallel case). Here we generalize these results to a much wider variety of algorithms, including LU factorization, Cholesky factorization, LDLT factorization, QR factorization, the Gram-Schmidt algorithm, and algorithms for eigenvalues and singular values, i.e., essentially all direct methods of linear algebra. The proof works for dense or sparse matrices and for sequential or parallel algorithms. In addition to lower bounds on the amount of data moved (bandwidth cost), we get lower bounds on the number of messages required to move it (latency cost). We extend our lower bound technique to compositions of linear algebra operations (like computing powers of a matrix) to decide whether it is enough to call a sequence of simpler optimal algorithms (like matrix multiplication) to minimize communication, or whether we can do better. We give examples of both. We also show how to extend our lower bounds to certain graph-theoretic problems. We point out recently designed algorithms that attain many of these lower bounds.

关键词： linear algebra algorithms bandwidth latency communication-avoiding lower bound

来源：评论

学校读者我要写书评

暂无评论

Optimizing Sparse linear algebra for Large-Scale Graph Analytics

引用

COMPUTER 2015年第8期48卷 26-34页

作者： Buono, Daniele Gunnels, John A. Que, Xinyu Checconi, Fabio Petrini, Fabrizio Tuan, Tai-Ching Long, Chris IBM TJ Watson Res Ctr High Performance Analyt Grp Yorktown Hts NY 10598 USA IBM TJ Watson Res Ctr Data Centr Syst Grp Yorktown Hts NY USA Univ Maryland Lab Phys Sci College Pk MD USA US Dept Def Arlington VA USA

Emerging data-intensive applications attempt to process and provide insight into vast amounts of online data. A new class of linear algebra algorithms can efficiently execute sparse matrix-matrix and matrix-vector multiplications on large-scale, shared memory multiprocessor systems, enabling analysts to more easily discern meaningful data relationships, such as those in social networks.

关键词： graph theory mathematics computing matrix multiplication multiprocessing systems sparse matrices vectors data relationships data-intensive applications large-scale graph analytics large-scale-shared memory multiprocessor systems linear algebra algorithms matrix-vector multiplications online data social networks sparse linear algebra optimization sparse matrix-matrix multiplications Concurrent programming Data analysis Data-intensive applications Memory management Multiprocessors Software engineering Sparse matrices concurrent programming data analysis graph analytics irregular applications shared memory multiprocessor systems software software engineering sparse linear algebra system performance

来源：评论

学校读者我要写书评

暂无评论

Floating-Point Calculations on a Quantum Annealer: Division and Matrix Inversion

引用

FRONTIERS IN PHYSICS 2020年 8卷

作者： Rogers, Michael L. Singleton, Robert L., Jr. SavantX Santa Fe NM 87501 USA Univ Leeds Sch Math Leeds W Yorkshire England

Systems of linear equations are employed almost universally across a wide range of disciplines, from physics and engineering to biology, chemistry, and statistics. Traditional solution methods such as Gaussian elimination are very time consuming for large matrices, and more efficient computational methods are desired. In the twilight of Moore's Law, quantum computing is perhaps the most direct path out of the darkness. There are two complementary paradigms for quantum computing, namely, circuit-based systems and quantum annealers. In this paper, we express floating point operations, such as division and matrix inversion, in terms of a quadratic unconstrained binary optimization (QUBO) problem, a formulation that is ideal for a quantum annealer. We first address floating point division, and then move on to matrix inversion. We provide a general algorithm for any number of dimensions, and, as a proof-of-principle, we demonstrates results from the D-Wave quantum annealer for 2 x 2 and 3 x 3 general matrices. In principle, our algorithm scales to very large numbers of linear equations;however, in practice the number is limited by the connectivity and dynamic range of the machine.

关键词： quantum computing matrix inversion quantum annealing algorithm linear algebra algorithms D-wave

来源：评论

学校读者我要写书评

暂无评论

ARCHITECTURAL APPROACH TO THE IBM-3090E VECTOR PERFORMANCE

引用

PARALLEL COMPUTING 1990年第1期13卷 47-59页

作者： WEBERPALS, H Gesellschaft für Wissenschaftliche Datenverarbeitung Göttingen Am Fassberg D-3400 Göttingen FRG

To lay the foundations of a quantitative understanding of the IBM 3090E vector performance we review the architecture of the vector facility and the three-level memory hierarchy, we derive timing formulae for the basic arithmetic, load, and store instructions and we pinpoint the influence of the cache design. As an application we explain the impact which the architecture imposes on the vector performance of algorithms from linear algebra.

关键词： IBM 3090E linear algebra algorithms memory hierarchy Vector architecture vector performance

来源：评论

学校读者我要写书评

暂无评论

An Efficient Solution to Structured Optimization Problems using Recursive Matrices

引用

COMPUTER GRAPHICS FORUM 2019年第8期38卷 33-39页

作者： Rueckert, D. Stamminger, M. Univ Erlangen Nurnberg Erlangen Germany

We present a linear algebra framework for structured matrices and general optimization problems. The matrices and matrix operations are defined recursively to efficiently capture complex structures and enable advanced compiler optimization. In addition to common dense and sparse matrix types, we define mixed matrices, which allow every element to be of a different type. Using mixed matrices, the low- and high-level structure of complex optimization problems can be encoded in a single type. This type is then analyzed at compile time by a recursive linear solver that picks the optimal algorithm for the given problem. For common computer vision problems, our system yields a speedup of 3-5 compared to other optimization frameworks. The BLAS performance is benchmarked against the MKL library. We achieve a significant speedup in block-SPMV and block-SPMM. This work is implemented and released open-source as a header-only extension to the C+ + math library Eigen.

关键词： CCS Concepts center dot Computing methodologies -> Symbolic and algebraic algorithms linear algebra algorithms Optimization algorithms

来源：评论

学校读者我要写书评

暂无评论

Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization

引用

FRONTIERS IN PHYSICS 2024年 12卷

作者： Castro, Erick R. Martins, Eldues O. Sarthour, Roberto S. Souza, Alexandre M. Oliveira, Ivan S. Ctr Brasileiro Pesquisas Fis Rio De Janeiro RJ Brazil Petr Brasileiro SA Ctr Pesquisas Leopoldo Miguez de Mello Rio De Janeiro Brazil

Recent advancements in quantum computing and quantum-inspired algorithms have sparked renewed interest in binary optimization. These hardware and software innovations promise to revolutionize solution times for complex problems. In this work, we propose a novel method for solving linear systems. Our approach leverages binary optimization, making it particularly well-suited for problems with large condition numbers. We transform the linear system into a binary optimization problem, drawing inspiration from the geometry of the original problem and resembling the conjugate gradient method. This approach employs conjugate directions that significantly accelerate the algorithm's convergence rate. Furthermore, we demonstrate that by leveraging partial knowledge of the problem's intrinsic geometry, we can decompose the original problem into smaller, independent sub-problems. These sub-problems can be efficiently tackled using either quantum or classical solvers. Although determining the problem's geometry introduces some additional computational cost, this investment is outweighed by the substantial performance gains compared to existing methods.

关键词： linear algebra algorithms quadratic unconstrained binary optimization formulation digital annealing conjugate geometry approach convergence analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：