Date of Award


Document Type


Degree Name

Master of Science (MS)


Computer Science

Committee Chair

Joshua Booth

Committee Member

Huaming Zhang

Committee Member

Mark Pekker


Heuristic algorithms, Loops (Computer science), High performance computing


Irregular algorithms (i.e., algorithms that make irregular memory accesses) are notorious for being difficult to optimize on parallel architectures due to load imbalance in the number of computational operations and memory access overheads. However, they are critically important as they include algorithms for sparse linear algebra and graph algorithms. Common optimizations include schedulers, orderings, and data structures that try to mitigate workload imbalance across computational units. Many current mitigations of this problem necessitate expert tuning by high-performance engineers. Methods for autotuning, which do not require an expert, are developing a trend towards large complex heuristics that are expensive in both needed memory and computation time. This thesis presents a case for cheaper and simpler autotuning heuristics via case studies of sparse matrix-vector multiplication and loop scheduling, and demonstrates that scaled-down heuristics can lower startup costs and still provide excellent performance.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.