Accelerating scientific computations with mixed precision algorithms
Accelerating scientific computations with mixed precision algorithms
复制标题
DOI：
10.1016/j.cpc.2008.11.005
复制
发表时间：
2009-12-01
影响因子：
6.3
通讯作者：
Tomov, Stanimire
中科院分区：
文献类型：
--
作者：
Baboulin, Marc;Buttari, Alfredo;Tomov, Stanimire
在现代架构上，32位运算的性能通常至少是位运算的两倍。通过组合使用32位和位浮点运算，许多密集和稀疏线性代数算法的性能可以显著提高，同时保持所得到解的位精度。本文提出的方法不仅适用于传统处理器，而且还适用于其他技术，如现场可编程门阵列(FPGA)、图形处理单元(CPU)和STI Cell BE处理器。程序摘要程序标题：ITER-REF目录识别符：AECO_v1_0程序摘要网址：http://cpc.cs.qub.ac.Lik/summaries/AECO-vl-O.htmlProgram可从皇后大学CPC程序图书馆获得。爱尔兰贝尔法斯特许可条款：标准CPC许可证，http://cpc.cs.qub.ac.uk/licence/licence.htmlNo.分布式程序中的行，包括测试数据等：7211号分布式程序中的字节数，包括测试数据等：41862分布格式：tar.gz编程语言：Fortran 77计算机：台式机，服务器操作系统：Unix/LinuxRAM：512MB分类：4.8外部例程：偏置(可选)问题的性质：在现代体系结构上，32位操作的性能通常至少是位操作的性能的两倍。通过组合使用32位和位浮点运算，许多稠密和稀疏线性代数算法的性能可以显著提高，同时保持所得到解的位精度。解决方法：混合精度算法源于这样的观察：在许多情况下，问题的单精度解可以被细化到双精度精度的点。无论是稠密的还是稀疏的，求解线性系统的一种常见方法是使用高斯消去法对系数矩阵进行LU分解。首先，系数矩阵A被分解成下三角矩阵L和上三角矩阵U的乘积。通常使用部分行旋转来提高数值稳定性，从而得到因式分解PA=LU，其中P是置换矩阵。系统的解首先通过求解Ly=Pb(前向替换)，然后再求解Ux=y(后向替换)来实现。由于四舍五入误差，计算解x带有被系数矩阵A的条件数放大的数值误差。为了改进计算解，可以应用迭代过程，其在每次迭代时对计算解产生校正。然后产生通常被称为迭代精化算法的方法。在系统条件不太恶劣的情况下，该算法产生一个正确的解，以满足工作精度。运行时间：秒/分钟，爱思唯尔公司出版。
On modern architectures, the performance of 32-bit operations is often at least twice as fast as the performance of 64-bit operations. By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many dense and sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution. The approach presented here can apply not only to conventional processors but also to other technologies such as Field Programmable Gate Arrays (FPGA), Graphical Processing Units (CPU), and the STI Cell BE processor. Results on modern processor architectures and the STI Cell BE are presented.Program summaryProgram title: ITER-REFCatalogue identifier: AECO_v1_0Program summary URL: http://cpc.cs.qub.ac.Lik/summaries/AECO-vl-O.htmlProgram obtainable from: CPC Program Library, Queen's University. Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. oflines in distributed program, including test data, etc.: 7211No. of bytes in distributed program, including test data, etc.: 41862Distribution format: tar.gzProgramming language: FORTRAN 77Computer: desktop, serverOperating system: Unix/LinuxRAM: 512 MbytesClassification: 4.8External routines: BIAS (optional)Nature of problem: On modern architectures, the performance of 32-bit operations is often at least twice as fast as the performance of 64-bit operations. By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many dense and sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution.Solution method: Mixed precision algorithms stem from the observation that, in many cases, a single precision solution of a problem can be refined to the point where double precision accuracy is achieved. A common approach to the solution of linear systems, either dense or sparse, is to perform the LU factorization of the coefficient matrix using Gaussian elimination. First, the coefficient matrix A is factored into the product of a lower triangular matrix L and an upper triangular matrix U. Partial row pivoting is in general used to improve numerical stability resulting in a factorization PA = LU, where P is a permutation matrix. The solution for the system is achieved by first solving Ly = Pb (forward substitution) and then solving Ux = y (backward substitution). Due to round-off errors, the computed solution, x, carries a numerical error magnified by the condition number of the coefficient matrix A. In order to improve the computed solution, an iterative process can be applied, which produces a correction to the computed solution at each iteration. which then yields the method that is commonly known as the iterative refinement algorithm. Provided that the system is not too ill-conditioned, the algorithm produces a solution correct to the working precision.Running time: seconds/minutes Published by Elsevier B.V.