Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin990556295.pdf (634.7 KB)

ETD Abstract Container

Abstract Header

REDUCING MEMORY SPACE FOR COMPLETELY UNROLLED LU FACTORIZATION OF SPARSE MATRICES

THIYAGARAJAN, SANJEEV
http://rave.ohiolink.edu/etdc/view?acc_num=ucin990556295

Abstract Details

2001, MS, University of Cincinnati, Engineering : Computer Engineering.
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.
Dr. Harold W. Carter (Advisor)
97 p.
compression; LU factorization; loop unrolling

Recommended Citations

Citations

  • THIYAGARAJAN, S. (2001). REDUCING MEMORY SPACE FOR COMPLETELY UNROLLED LU FACTORIZATION OF SPARSE MATRICES [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin990556295

    APA Style (7th edition)

  • THIYAGARAJAN, SANJEEV. REDUCING MEMORY SPACE FOR COMPLETELY UNROLLED LU FACTORIZATION OF SPARSE MATRICES. 2001. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin990556295.

    MLA Style (8th edition)

  • THIYAGARAJAN, SANJEEV. "REDUCING MEMORY SPACE FOR COMPLETELY UNROLLED LU FACTORIZATION OF SPARSE MATRICES." Master's thesis, University of Cincinnati, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin990556295

    Chicago Manual of Style (17th edition)

ucin990556295
545
© 2001, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.