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

Pennsylvania State Univ University Park, University Park PA

Investigators

Abstract

Toward a Linear Time Sparse Solver with Locality-Enhanced Scalable Parallelism Padma 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.