A sparse LU factorization based on Gaussian elimination with partial pivoting (GEPP) is important to many scientific applications, but it is still an open problem to develop a high performance GEPP code on distributed memory machines. The main difficulty is that partial pivoting operations dynamically change computation and nonzero fill-in structures during the elimination process. This paper presents an approach called S* for parallelizing this problem on distributed memory machines. The S* approach adopts static symbolic factorization to avoid run-time control overhead, incorporates 2D L/U supemode partitioning and amalgamation strategies to improve caching performance, and exploits irregular task parallelism embedded in sparse LU using asynchronous computation scheduling. The paper discusses and compares the algorithms using 1D and 2D data mapping schemes, and presents experimental studies on Cray-T3D and T3E. The performance results for a set of nonsymmetric benchmark matrices are very encouraging, and S* has achieved up to 6.878 GFLOPS on 128 T3E nodes. To the best of our knowledge, this is the highest performance ever achieved for this challenging problem and the previous record was 2.583 GFLOPS on shared memory machines.
展开▼
机译：基于带有部分枢轴的高斯消去（GEPP）的稀疏LU分解对于许多科学应用很重要，但是在分布式存储机器上开发高性能GEPP代码仍然是一个未解决的问题。主要的困难在于，部分透视操作会在消除过程中动态更改计算和非零填充结构。本文提出了一种称为S *的方法，用于在分布式存储机器上并行化此问题。 S *方法采用静态符号分解以避免运行时控制开销，并结合了2D L / U超模划分和合并策略以提高缓存性能，并利用异步计算调度利用稀疏LU中嵌入的不规则任务并行性。本文讨论和比较了使用1D和2D数据映射方案的算法，并提供了有关Cray-T3D和T3E的实验研究。一组非对称基准矩阵的性能结果令人鼓舞，S *在128个T3E节点上达到了6.878 GFLOPS。据我们所知，这是解决该难题的最高性能，先前的记录是共享存储计算机上的2.583 GFLOPS。
展开▼
