Using Hybrid Schedules to Safely Outperform Classical Polyhedral Schedules

The Polyhedral model is a mathematical framework for programs with affine control loops that enables complex program transformations such as loop permutation and loop tiling to achieve parallelism, data locality and energy efficiency. Polyhedral schedules are widely used by popular polyhedral compilers such as AlphaZ and PLuTo to represent program execution orders. They use barriers to enforce the correct order of execution and usually synchronizations happen more than necessarily. Current research reveals the merit of combining the classical polyhedral schedules and partially ordered schedules manually written by hands with highly target dependent point-wise synchronization mechanisms. However, derivation of a hybrid schedule is tedious and error-prone due to the possibility of deadlocks. Its deviation from any existing standard representation makes program verication the sole responsibility of the programmer. We propose techniques to automate the derivation, verification and code-generation of hybrid schedules. We also demonstrate the convenience and utility of such techniques in resolving the complications associated with current hybrid schedules.