Invited Talk by Prof. Sanjay Rajopadhye on What is the Polyhedral Model (& Why Should I Care)

Title: What is the Polyhedral Model (& Why Should I Care)  
SpeakerProf. Sanjay Rajopadhye, Colorado State University, USA
Host Faculty:  Dr. Ramakrishna Upadrasta
Room No: 317, Academic block


The hallmark of a good technology it that it is taken it for granted, and no one cares how it works.  As a case in point, the (wo)man in the street has no interest in CDMA or cell towers, but just assumes that ubiquitous wireless communication is universally available.
The polyhedral model is mathematical framework for target agnostic mapping of a narrow domain of “programs” to an optimal “implementation.”  With a thirty year old history, the fact that relatively few people know about it may indicate that it is successful.  In reality, a number of challenges remain (and this is why you should care).

In this talk, I will first review the development of the model, describe some major successes, and identify some of today's challenges: the model remains narrow, our tools are not truly optimal, they are not seamlessly scalable, and target independence in the face of architectural changes driven by Moore’s law is very hard.


Using a recent application for RNA-RNA interaction as an example, I will present some recent results that offer some hope. We improved the performance of a simple surrogate kernel—a “miniapp”) of the complete application—albeit one that was written naively—by two orders of magnitude.  Our performance attained peak L1 cache bandwidth, and there remains a factor of further six gap between the observed performance and the theoretical machine peak.

Speaker bio:

Sanjay Rajopadhye is currently a professor in the Computer Science (CS) and Electrical and Computer Engineering (ECE) departments at Colorado State University. He was educated at IIT Kharagpur (B.Tech, 1980), and the University of Utah (PhD, 1986), and is one of the inventors of the polyhedral model, a mathematical formalism for reasoning about massively parallel, regular computations. His Ph.D. dissertation made three key contributions — scheduling, locality, and closure — to the foundations of the model. It was developed to address the design of early era "hardware accelerators" called systolic arrays, and is now used for automatic parallelization of affine control loops in many productions compilers. His main research contributions revolve around the polyhedral model: code generation, tiling, memory reuse analyses, and recently energy optimization.

Wednesday, March 14, 2018 - 11:00 to 12:00