Details

REDUCING MEMORY SPACE FOR COMPLETELY UNROLLED LU FACTORIZATION OF SPARSE MATRICES

by THIYAGARAJAN, SANJEEV

Abstract (Summary)
Complete Loop Unrolling (CLU) is a possible approach for improving the execution time of Sparse Lower/Upper (LU) factorization. The amount of memory space occupied by the interpretive code generated using CLU technique is usually traded off for better execution gain. But in some problem domains such as analog circuit simulation, a large number of factorizations are required to solve sparse matrices and the storage space occupied by interpretive code for such problems are large and easily consumes the available memory(or exceeds it!). This thesis investigates compression techniques to reduce storage space for the interpretive code sequence. In particular, we present the investigation of a combination of four compression approaches namely 1) Delta Encoding 2) Clustering the interpretive code 3) Reordering the data elements in memory and the general compression method 4) LZW compression. The clustering method is unique to our study for which a greedy partitioning technique is proposed and analyzed. Two other partitioning schemes, random partitioning and partitioning on divide instructions were implemented and compared with the greedy partitioning approach. The results show that the greedy approach is better than the other two. Experiments demonstrate that the greedy partitioning technique applied on delta-encoded sequence is effective in decreasing the storage space of interpretive code sequence. We also explored the possibility of cost minimization by reordering the data elements in memory such that the delta distance between adjacent operands is decreased. Compression improvement was seen for matrices 300 X 300 and smaller.
Bibliographical Information:

Advisor:

School:University of Cincinnati

School Location:USA - Ohio

Source Type:Master's Thesis

Keywords:compression lu factorization loop unrolling

ISBN:

Date of Publication:01/01/2001

© 2009 OpenThesis.org. All Rights Reserved.