Fill estimation for blocked sparse matrices and tensors

Many sparse matrices and tensors from a variety of applications, such as finite element methods and computational chemistry, have a natural aligned rectangular nonzero block structure. Researchers have designed high-performance blocked sparse operations which can take advantage of this sparse structure to reduce the complexity of storing the locations of nonzeros. The performance of a blocked sparse operation depends on how well a particular blocking scheme, or tiling of the sparse matrix into blocks, reflects the structure of nonzeros in the tensor. Since sparse tensor structure is generally unknown until runtime, blocking-scheme selection must be efficient. The fill is a quantity which, for some blocking scheme, relates the number of nonzero blocks to the number of nonzeros. Many performance models use the fill to help choose a blocking scheme. The fill is expensive to compute exactly, however. This thesis presents a sampling-based algorithm called PHIL that efficiently estimates the fill of sparse matrices and tensors in any format. Much of the thesis will appear in a paper coauthored with Peter Ahrens and Nicholas Schiefer. We provide theoretical guarantees for sparse matrices and tensors, and experimental results for matrices. The existing state-of-the-art fill-estimation algorithm, which we will call OSKI, runs in time linear in the number of elements in the tensor. In contrast, the number of samples PHIL needs to compute a fill estimate is unrelated to the number of nonzeros in the tensor. We compared PHIL and OSKI on a suite of hundreds of sparse matrices and found that on most inputs, PHIL estimates the fill at least 2 times faster and often more than 20 times faster than OSKI. PHIL consistently produced accurate estimates and was faster and/or more accurate than OSKI on all cases. Finally, we found that PHIL and OSKI produced comparable speedups in parallel blocked sparse matrix-vector multiplication.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Xu, Helen Jiang

Advisor dc:contributor.advisor

• Charles E. Leiserson.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/117816

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/117816