A case for simple, low-cost autotuning heuristics for efficient performance of irregular algorithms
Date of Award
Master of Science (MS)
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.
Lane, Phillip Allen, "A case for simple, low-cost autotuning heuristics for efficient performance of irregular algorithms" (2022). Theses. 384.