[PAST EVENT] Composable, Sound Transformations for Nested Recursion and Loops

April 28, 2021
12pm - 1pm
McGlothlin-Street Hall, online
251 Jamestown Rd
Williamsburg, VA 23185Map this location

Title: Composable, Sound Transformations for Nested Recursion and Loops


Over the past few decades, extensive research has been done on composing, verifying, and applying scheduling transformations like loop interchange and loop tiling for regular programs that use loops to operate over arrays and matrices. As a result, we have general frameworks such as the polyhedral model to handle transformations for loop-based programs. Irregular programs, in contrast, use recursion and loops to manipulate pointer-based data structures. Irregular programs appear in many essential applications such as scientific simulations, data mining, and graphics rendering. However, there is no analogous framework to the polyhedral model for recursive programs. Prior transformations designed for irregular programs are problem-specific and not easily portable. 

In this talk, I will discuss PolyRec, a unifed general framework that can compose and apply scheduling transformations to nested recursive programs, and reason about the correctness of composed transformations. I will focus on the main components of Polyrec: Representations of the computation schedule, transformations of that schedule, abstractions to capture dependences in the computation, and a method to verify the soundness of transformations in the presence of dependences. I will conclude with my going work on extensions of PolyRec to incorporate new scheduling transformations and related future work.

Short Bio: Kirshanthan Sundararajah is a Ph.D. Candidate in School of Electrical and Computer Engineering at Purdue University, advised by Prof. Milind Kulkarni. His research interests lie in the areas of compilers, programming languages, and high-performance computing. He is particularly interested in optimizing irregular programs that are recursive. He has spent time as an intern at Microsoft Research, Reservoir Labs, and Nvidia working on various problems related to performance engineering. He earned his Bachelor's in Electronics and Telecommunication Engineering at the University of Moratuwa, Sri Lanka.


Bin Ren