Solving Systems of Linear Equations on the CELL Processor Using Cholesky Factorization
Solving Systems of Linear Equations on the CELL Processor Using Cholesky Factorization
复制标题
使用 Cholesky 分解在 CELL 处理器上求解线性方程组
DOI：
10.1109/tpds.2007.70813
复制
发表时间：
2008
影响因子：
5.3
通讯作者：
J. Dongarra
中科院分区：
文献类型：
--
作者：
J. Kurzak;A. Buttari;J. Dongarra
Sony/Toshiba/IBM（STI）CELL处理器在处理器架构中引入了开创性的解决方案。同时也给数值算法的发展提出了新的挑战。一个是有效利用单精度和双精度运算速度之间的差异，另一个是有效的短向量SIMD核之间的并行化。第一个挑战是解决利用众所周知的技术迭代细化的解决方案的一个稠密的对称正定线性方程组，从而在一个混合精度的算法，它提供了双精度的精度，同时执行大部分的工作在单精度。本文的主要贡献在于解决第二个挑战，成功的线程级并行化，利用细粒度的任务粒度和轻量级的分散同步。计算密集型部分的实现达到峰值浮点性能的90%以内，而内存密集型部分的实现达到峰值内存带宽的90%以内。该算法在单CELL处理器上，单精度求解对称正定线性方程组的速度超过170 Gflop/s，双精度求解速度超过150 Gflop/s。
The Sony/Toshiba/IBM (STI) CELL processor introduces pioneering solutions in processor architecture. At the same time it presents new challenges for the development of numerical algorithms. One is effective exploitation of the differential between the speed of single and double precision arithmetic; the other is efficient parallelization between the short vector SIMD cores. The first challenge is addressed by utilizing the well known technique of iterative refinement for the solution of a dense symmetric positive definite system of linear equations, resulting in a mixed-precision algorithm, which delivers double precision accuracy, while performing the bulk of the work in single precision. The main contribution of this paper lies in addressing the second challenge by successful thread-level parallelization, exploiting fine-grained task granularity and a lightweight decentralized synchronization. The implementation of the computationally intensive sections gets within 90 percent of peak floating point performance, while the implementation of the memory intensive sections reaches within 90 percent of peak memory bandwidth. On a single CELL processor, the algorithm achieves over 170~Gflop/s when solving a symmetric positive definite system of linear equation in single precision and over 150~Gflop/s when delivering the result in double precision accuracy.