Toward a Linear Time Sparse Solver with Locality-Enhanced Scalable Parallelism

Padma Raghavan许多计算科学模拟都涉及使用隐式或半隐式方法求解偏微分方程的数值解。 这种模拟通常涉及非线性系统，其中主要成本是稀疏线性系统解决方案的成本。 稀疏解算器对当前和未来一代多核芯片多处理器架构及其网络集成到大规模并行处理系统中提出了一系列性能挑战。寻求一种新的结构化混合算法，以实现可靠和可扩展的解决方案。 一个内-外树结构的计划制定利用几何撕裂和交织的系数矩阵的图形。研究问题涉及可扩展的并行性，硬件延迟掩蔽映射的数据，和几何机制来传达系数矩阵的数值属性，以加速解决方案的过程。

Toward a Linear Time Sparse Solver with Locality-Enhanced Scalable ParallelismPadma Raghavan Many computational science simulations concern the numeric solution of partial differential equations using implicit or semi-implicit methods. Such simulations often involve nonlinear systems where the dominant costs are those for sparse linear system solution. Sparse solvers present an array of performance challenges on current and future generation multicore chip-multiprocessor architectures, and their networked ensembles into massively parallel processing systems. A new structured hybrid algorithm is sought to enable reliable and scalable solution. An inner-outer tree-structured scheme is formulated by exploiting geometry for tearing and interlacing of the graph of the coefficient matrix. Research issues concern scalable parallelism, hardware latency-masking mapping of data, and geometric mechanisms to convey numeric properties of the coefficient matrix to accelerate the solution process.