Date of Award
2022
Document Type
Thesis
Degree Name
Master of Science (MS)
Department
Computer Science
Committee Chair
Joshua Booth
Committee Member
Huaming Zhang
Committee Member
Mark Pekker
Subject(s)
Heuristic algorithms, Loops (Computer science), High performance computing
Abstract
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.
Recommended Citation
Lane, Phillip Allen, "A case for simple, low-cost autotuning heuristics for efficient performance of irregular algorithms" (2022). Theses. 384.
https://louis.uah.edu/uah-theses/384