Architectural support for direct sparse LU algorithms

Sparse linear algebra algorithms typically perform poorly on superscalar, general-purpose processors due to irregular data access patterns and indexing overhead. These algorithms are important to a number of scientific c computing domains including power system simulation, which motivates this work. A variety of algorithms and techniques exist to exploit CPU features, but it has been shown that special purpose hardware support can dramatically outperform these methods. However, the development cost and scaling limitations of a custom hardware solution limit widespread use. This work presents an analysis of hardware and software performance during sparse LU decomposition in order to better understand trade-o s and to suggest the most promising approach for future research. Experimental results show that hardware support for indexing operations provides the greatest performance improvement to these algorithms and techniques or hardware that facilitate indexing operations should be explored.M.S., Computer Science -- Drexel University, 201