January 20, 2023
Software stacks and optimizations have been designed targeting regular programs — programs that operate over regular data structures such as arrays and matrices using loops with statically characterizable control flow — for a very long time. The general consensus in the past was that regular programs are the common ones. But irregular programs — programs that traverse over irregular or pointer-based data structures such as sparse matrices, trees and graphs using a mix of recursion and loops with statically hard to predict control flow — also appear in many essential applications such as simulation codes, data mining, graphics etc. There is a swath of research on scheduling transformations for optimizing regular programs and loop transformation frameworks are good examples. Scheduling transformations for irregular programs are ad-hoc. In the past, compile-time scheduling transformations for irregular programs were considered on the horizon by loop transformation frameworks. Even the few existing ones were applied in isolation and composability of these transformations were out of the question.
In this talk, we will explore frameworks that perform composable scheduling transformations for irregular programs. Composability of these transformations is very important because not all of them are correct; In a sequence of transformation there might be individually incorrect transformations, but the sequence of transformation is correct and yields better performance. Hence, it is important to reason about the correctness of a composed sequence of transformations. First, I will discuss different parts of a scheduling transformation framework and how they fit well together by different abstractions. We will see this in the case of PolyRec, a composable scheduling transformation framework for nested recursion and loops. After that, we will look into some gaps in these abstractions which we can fill up in the case of another framework called UniRec.
About Kirshanthan Sundararajah
Kirshanthan Sundararajah is a PhD candidate in the Elmore Family School of Electrical and Computer Engineering. His research interests lie in the areas of compilers, programming languages and high-performance computing. He is particularly interested in working with the performance transparency issues of irregular programs.